[squid-dev] [PATCH] Crypto-NG: update use of random number generators

Amos Jeffries squid3 at treenet.co.nz
Sun Feb 8 17:10:34 UTC 2015


C++11 brings with it a set of reasonable quality random number
generators and tools to retrieve values for various ranges and types.

This patch C++11 STL <random> features to replace the use of the
varyingly broken, weak or non-standard functions: rand(), random(),
lrand48(), and drand48().

In the process we gain much faster and higher quality randomness in the
auth nonces and event queue scheduling. And more "even" spread for the
ACL random feature.

Amos
-------------- next part --------------
=== modified file 'CREDITS'
--- CREDITS	2014-12-30 10:05:05 +0000
+++ CREDITS	2015-02-08 02:24:48 +0000
@@ -1731,46 +1731,40 @@
  *    documentation and/or other materials provided with the distribution.
  * 3. Neither the name of the University nor the names of its contributors
  *    may be used to endorse or promote products derived from this software
  *    without specific prior written permission.
  *
  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  */
 
 ==============================================================================
 
-lib/drand48.c:
-
-From Linux libc-5.4.46.
-
-==============================================================================
-
 lib/radix.c:
 
  *  Adapted from HTSUtils.c in CERN httpd 3.0 (http://info.cern.ch/httpd/)
  *  by Darren Hardy <hardy at cs.colorado.edu>, November 1994.
 
 ==============================================================================
 
 lib/Splay.cc:
 
  * based on ftp://ftp.cs.cmu.edu/user/sleator/splaying/top-down-splay.c
  * http://bobo.link.cs.cmu.edu/cgi-bin/splay/splay-cgi.pl
 
 ==============================================================================
 
 src/access_log.cc:
 
 mcast_encode() in src/access_log.c is derived from Mark Atkinson's
 (mark_a at cix.compulink.co.uk) "Tiny Encryption Algorithm".
 http://www.io.com/~paulhart/game/algorithms/tea.html
 

=== modified file 'compat/Makefile.am'
--- compat/Makefile.am	2015-01-13 07:25:36 +0000
+++ compat/Makefile.am	2015-02-07 10:44:48 +0000
@@ -11,41 +11,40 @@
 include $(top_srcdir)/src/Common.am
 
 AUTOMAKE_OPTIONS = subdir-objects
 
 # Ideally this would be 100% inline functions and macro wrappers.
 
 # Port Specific Configurations
 
 noinst_LTLIBRARIES = libcompat-squid.la
 libcompat_squid_la_SOURCES = \
 	assert.cc \
 	assert.h \
 	cmsg.h \
 	compat.cc \
 	compat.h \
 	compat_shared.h \
 	cpu.h \
 	cppunit.h \
 	debug.cc \
 	debug.h \
-	drand48.h \
 	eui64_aton.h \
 	eui64_aton.c \
 	fdsetsize.h \
 	getaddrinfo.cc \
 	getaddrinfo.h \
 	getnameinfo.cc \
 	getnameinfo.h \
 	GnuRegex.c \
 	GnuRegex.h \
 	inet_ntop.cc \
 	inet_ntop.h \
 	inet_pton.cc \
 	inet_pton.h \
 	initgroups.h \
 	memrchr.cc \
 	memrchr.h \
 	osdetect.h \
 	psignal.h \
 	shm.cc \
 	shm.h \

=== removed file 'compat/drand48.c'
--- compat/drand48.c	2015-01-13 07:25:36 +0000
+++ compat/drand48.c	1970-01-01 00:00:00 +0000
@@ -1,64 +0,0 @@
-/*
- * Copyright (C) 1996-2015 The Squid Software Foundation and contributors
- *
- * Squid software is distributed under GPLv2+ license and includes
- * contributions from numerous individuals and organizations.
- * Please see the COPYING and CONTRIBUTORS files for details.
- */
-
-#include "squid.h"
-
-/* borrowed from libc/misc/drand48.c in Linux libc-5.4.46 this quick
- * hack by Martin Hamilton <martinh at gnu.org> to make Squid build on
- * Win32 with GNU-Win32 - sorry, folks! */
-
-#if !HAVE_DRAND48
-
-#define N   16
-#define MASK    ((unsigned)(1 << (N - 1)) + (1 << (N - 1)) - 1)
-#define LOW(x)  ((unsigned)(x) & MASK)
-#define HIGH(x) LOW((x) >> N)
-#define MUL(x, y, z)    { long l = (long)(x) * (long)(y); \
-        (z)[0] = LOW(l); (z)[1] = HIGH(l); }
-#define CARRY(x, y) ((long)(x) + (long)(y) > MASK)
-#define ADDEQU(x, y, z) (z = CARRY(x, (y)), x = LOW(x + (y)))
-#define X0  0x330E
-#define X1  0xABCD
-#define X2  0x1234
-#define A0  0xE66D
-#define A1  0xDEEC
-#define A2  0x5
-#define C   0xB
-
-static void next(void);
-static unsigned x[3] = {X0, X1, X2}, a[3] = {A0, A1, A2}, c = C;
-
-double drand48(void);
-
-double
-drand48(void)
-{
-    static double two16m = 1.0 / (1L << N);
-    next();
-    return (two16m * (two16m * (two16m * x[0] + x[1]) + x[2]));
-}
-
-static void
-next(void)
-{
-    unsigned p[2], q[2], r[2], carry0, carry1;
-
-    MUL(a[0], x[0], p);
-    ADDEQU(p[0], c, carry0);
-    ADDEQU(p[1], carry0, carry1);
-    MUL(a[0], x[1], q);
-    ADDEQU(p[1], q[0], carry0);
-    MUL(a[1], x[0], r);
-    x[2] = LOW(carry0 + carry1 + CARRY(p[1], r[0]) + q[1] + r[1] +
-               a[0] * x[2] + a[1] * x[1] + a[2] * x[0]);
-    x[1] = LOW(p[1] + r[0]);
-    x[0] = LOW(p[0]);
-}
-
-#endif /* HAVE_DRAND48 */
-

=== removed file 'compat/drand48.h'
--- compat/drand48.h	2015-01-13 07:25:36 +0000
+++ compat/drand48.h	1970-01-01 00:00:00 +0000
@@ -1,18 +0,0 @@
-/*
- * Copyright (C) 1996-2015 The Squid Software Foundation and contributors
- *
- * Squid software is distributed under GPLv2+ license and includes
- * contributions from numerous individuals and organizations.
- * Please see the COPYING and CONTRIBUTORS files for details.
- */
-
-#ifndef _SQUID_DRAND48_H
-#define _SQUID_DRAND48_H
-
-#if !HAVE_DRAND48
-#define HAVE_DRAND48 1
-SQUIDCEXTERN double drand48(void);
-#endif
-
-#endif
-

=== modified file 'configure.ac'
--- configure.ac	2015-02-01 07:05:48 +0000
+++ configure.ac	2015-02-08 09:42:41 +0000
@@ -3311,84 +3311,79 @@
       AC_MSG_NOTICE([disabling poll for $host...])
       ac_cv_func_poll='no'
       ;;
   esac
 fi
 
 dnl Check for library functions
 AC_CHECK_FUNCS(\
 	backtrace_symbols_fd \
 	bcopy \
 	eui64_aton \
 	fchmod \
 	getdtablesize \
 	getpagesize \
 	getpass \
 	getrlimit \
 	getrusage \
 	getspnam \
 	gettimeofday \
 	glob \
-	lrand48 \
 	mallocblksize \
 	mallopt \
 	memcpy \
 	memmove \
 	memrchr \
 	memset \
 	mkstemp \
 	mktime \
 	mstats \
 	poll \
 	prctl \
 	pthread_attr_setschedparam \
 	pthread_attr_setscope \
 	pthread_setschedparam \
 	pthread_sigmask \
 	putenv \
-	random \
 	regcomp \
 	regexec \
 	regfree \
 	res_init \
 	__res_init \
 	rint \
 	sched_getaffinity \
 	sched_setaffinity \
 	select \
 	seteuid \
 	setgroups \
 	setpgrp \
 	setsid \
 	sigaction \
 	snprintf \
 	socketpair \
-	srand48 \
-	srandom \
 	sysconf \
 	syslog \
 	timegm \
 	vsnprintf \
 )
 dnl ... and some we provide local replacements for
 AC_REPLACE_FUNCS(\
-	drand48 \
 	initgroups \
 	psignal \
 	strerror \
 	strtoll \
 	tempnam \
 )
 
 AC_CHECK_DECLS([getaddrinfo,getnameinfo,inet_ntop,inet_pton,InetNtopA,InetPtonA],,,[
 /*
  * BSD requires sys/types.h, sys/socket.h, netinet/in.h, netdb.h, arpa/inet.h
  * Linux requires sys/types.h, sys/socket.h, arpa/inet.h
  * Windows requires sys/socket.h, winsock2.h, ws2tcpip.h
  */
 #if HAVE_SYS_TYPES_H
 #include <sys/types.h>
 #endif
 #if HAVE_NETINET_IN_H
 #include <netinet/in.h>
 #endif
 #if HAVE_SYS_SOCKET_H

=== modified file 'helpers/basic_auth/RADIUS/basic_radius_auth.cc'
--- helpers/basic_auth/RADIUS/basic_radius_auth.cc	2015-01-13 07:25:36 +0000
+++ helpers/basic_auth/RADIUS/basic_radius_auth.cc	2015-02-08 16:51:59 +0000
@@ -46,40 +46,41 @@
  * the ID's of the different programs can start to conflict. I'm not sure it
  * would help anyway. I think the RADIUS server is close by and I don't think
  * it will handle requests in parallel anyway (correct me if I'm wrong here)
  *
  * Marc van Selm <selm at cistron.nl>
  * with contributions from
  * Henrik Nordstrom <hno at squid-cache.org>
  * and many others
  */
 
 #include "squid.h"
 #include "helpers/defines.h"
 #include "md5.h"
 #include "radius-util.h"
 #include "radius.h"
 
 #include <cctype>
 #include <cerrno>
 #include <cstring>
 #include <ctime>
+#include <random>
 #if HAVE_SYS_SOCKET_H
 #include <sys/socket.h>
 #endif
 #if HAVE_NETINET_IN_H
 #include <netinet/in.h>
 #endif
 #if HAVE_UNISTD_H
 #include <unistd.h>
 #endif
 #if HAVE_FCNTL_H
 #include <fcntl.h>
 #endif
 #if _SQUID_WINDOWS_
 #include <io.h>
 #endif
 #if HAVE_UNISTD_H
 #include <unistd.h>
 #endif
 #if HAVE_NETDB_H
 #include <netdb.h>
@@ -188,50 +189,45 @@
     secretlen = strlen(secretkey);
     memcpy(buffer + length, secretkey, secretlen);
     md5_calc(calc_digest, (unsigned char *) auth, length + secretlen);
 
     if (memcmp(reply_digest, calc_digest, AUTH_VECTOR_LEN) != 0) {
         debug("WARNING: Received invalid reply digest from server\n");
         return -1;
     }
     if (auth->code != PW_AUTHENTICATION_ACK)
         return 1;
 
     return 0;
 }
 
 /*
  *    Generate a random vector.
  */
 static void
 random_vector(char *aVector)
 {
-    int randno;
-    int i;
+    static std::mt19937 mt(time(0));
+    static std::uniform_int_distribution<uint8_t> dist;
 
-    srand((time(0) ^ rand()) + rand());
-    for (i = 0; i < AUTH_VECTOR_LEN;) {
-        randno = rand();
-        memcpy(aVector, &randno, sizeof(int));
-        aVector += sizeof(int);
-        i += sizeof(int);
-    }
+    for (int i = 0; i < AUTH_VECTOR_LEN; ++i)
+        aVector[i] = static_cast<char>(dist(mt) & 0xFF);
 }
 
 /* read the config file
  * The format should be something like:
  * # basic_radius_auth configuration file
  * # MvS: 28-10-1998
  * server suncone.cistron.nl
  * secret testje
  */
 static int
 rad_auth_config(const char *cfname)
 {
     FILE *cf;
     char line[MAXLINE];
     int srv = 0, crt = 0;
 
     if ((cf = fopen(cfname, "r")) == NULL) {
         perror(cfname);
         return -1;
     }

=== modified file 'include/squid.h'
--- include/squid.h	2015-01-13 07:25:36 +0000
+++ include/squid.h	2015-02-08 09:43:37 +0000
@@ -49,51 +49,40 @@
 #endif
 
 #if !defined(CACHEMGR_HOSTNAME)
 #define CACHEMGR_HOSTNAME ""
 #else
 #define CACHEMGR_HOSTNAME_DEFINED 1
 #endif
 
 #if SQUID_DETECT_UDP_SO_SNDBUF > 16384
 #define SQUID_UDP_SO_SNDBUF 16384
 #else
 #define SQUID_UDP_SO_SNDBUF SQUID_DETECT_UDP_SO_SNDBUF
 #endif
 
 #if SQUID_DETECT_UDP_SO_RCVBUF > 16384
 #define SQUID_UDP_SO_RCVBUF 16384
 #else
 #define SQUID_UDP_SO_RCVBUF SQUID_DETECT_UDP_SO_RCVBUF
 #endif
 
-#if HAVE_RANDOM
-#define squid_random random
-#define squid_srandom srandom
-#elif HAVE_LRAND48
-#define squid_random lrand48
-#define squid_srandom srand48
-#else
-#define squid_random rand
-#define squid_srandom srand
-#endif
-
 /*
  * Determine if this is a leak check build or standard
  */
 #if PURIFY || WITH_VALGRIND
 #define LEAK_CHECK_MODE 1
 #endif
 
 /* temp hack: needs to be pre-defined for now. */
 #define SQUID_MAXPATHLEN 256
 
 // TODO: determine if this is required. OR if compat/os/mswindows.h works
 #if _SQUID_WINDOWS_ && defined(__cplusplus)
 /** \cond AUTODOCS-IGNORE */
 using namespace Squid;
 /** \endcond */
 #endif
 
 // temporary for the definition of LOCAL_ARRAY
 #include "leakcheck.h"
 

=== modified file 'lib/hash.cc'
--- lib/hash.cc	2015-01-13 07:25:36 +0000
+++ lib/hash.cc	2015-02-08 16:21:03 +0000
@@ -326,46 +326,49 @@
  *  and prints the table again...
  */
 int
 main(void)
 {
     hash_table *hid;
     LOCAL_ARRAY(char, buf, BUFSIZ);
     LOCAL_ARRAY(char, todelete, BUFSIZ);
     hash_link *walker = NULL;
 
     todelete[0] = '\0';
     printf("init\n");
 
     printf("creating hash table\n");
     if ((hid = hash_create((HASHCMP *) strcmp, 229, hash4)) < 0) {
         printf("hash_create error.\n");
         exit(1);
     }
     printf("done creating hash table: %d\n", hid);
 
+    std::mt19937 mt;
+    std::uniform_int_distribution<> dist(0,16);
+
     while (fgets(buf, BUFSIZ, stdin)) {
         buf[strlen(buf) - 1] = '\0';
         printf("Inserting '%s' for item %p to hash table: %d\n",
                buf, buf, hid);
         hash_insert(hid, xstrdup(buf), (void *) 0x12345678);
-        if (random() % 17 == 0)
+        if (dist(mt) == 0)
             strcpy(todelete, buf);
     }
 
     printf("walking hash table...\n");
     for (int i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
         printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
                walker->item);
     }
     printf("done walking hash table...\n");
 
     if (todelete[0]) {
         printf("deleting %s from %d\n", todelete, hid);
         if (hash_delete(hid, todelete))
             printf("hash_delete error\n");
     }
     printf("walking hash table...\n");
     for (int i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
         printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
                walker->item);
     }

=== modified file 'lib/ntlmauth/ntlmauth.cc'
--- lib/ntlmauth/ntlmauth.cc	2015-01-13 07:25:36 +0000
+++ lib/ntlmauth/ntlmauth.cc	2015-02-08 16:40:42 +0000
@@ -1,34 +1,35 @@
 /*
  * Copyright (C) 1996-2015 The Squid Software Foundation and contributors
  *
  * Squid software is distributed under GPLv2+ license and includes
  * contributions from numerous individuals and organizations.
  * Please see the COPYING and CONTRIBUTORS files for details.
  */
 
 /*
  * Inspired by previous work by Andrew Doran <ad at interlude.eu.org>.
  */
 #include "squid.h"
 
 #include <cstring>
+#include <random>
 #if HAVE_STRINGS_H
 #include <strings.h>
 #endif
 
 #include "ntlmauth/ntlmauth.h"
 #include "util.h"       /* for base64-related stuff */
 
 /* ************************************************************************* */
 /* DEBUG functions */
 /* ************************************************************************* */
 
 /** Dumps NTLM flags to standard error for debugging purposes */
 void
 ntlm_dump_ntlmssp_flags(uint32_t flags)
 {
     fprintf(stderr, "flags: %s%s%s%s%s%s%s%s%s%s%s%s%s%s%s%s%s%s%s\n",
             (flags & NTLM_NEGOTIATE_UNICODE ? "Unicode " : ""),
             (flags & NTLM_NEGOTIATE_ASCII ? "ASCII " : ""),
             (flags & NTLM_NEGOTIATE_REQUEST_TARGET ? "ReqTgt " : ""),
             (flags & NTLM_NEGOTIATE_REQUEST_SIGN ? "ReqSign " : ""),
@@ -161,55 +162,50 @@
     memcpy(payload + l, toadd, toadd_length);
 
     hdr->len = htole16(toadd_length);
     hdr->maxlen = htole16(toadd_length);
     const off_t o = l + reinterpret_cast<const ntlmhdr *>(payload) - packet_hdr;
     hdr->offset = htole32(o & 0xFFFFFFFF);
     (*payload_length) += toadd_length;
 }
 
 /* ************************************************************************* */
 /* Negotiate Packet functions */
 /* ************************************************************************* */
 
 // ?
 
 /* ************************************************************************* */
 /* Challenge Packet functions */
 /* ************************************************************************* */
 
 /*
- * Generates a challenge request nonce. The randomness of the 8 byte
- * challenge strings can be guarenteed to be poor at best.
+ * Generates a challenge request nonce.
  */
 void
 ntlm_make_nonce(char *nonce)
 {
-    static unsigned hash;
-    uint32_t r = static_cast<uint32_t>(rand());
-    r = (hash ^ r) + r;
-
-    for (int i = 0; i < NTLM_NONCE_LEN; ++i) {
-        nonce[i] = static_cast<char>(r & 0xFF);
-        r = (r >> 2) ^ r;
-    }
-    hash = r;
+    static std::mt19937 mt(time(0));
+    static std::uniform_int_distribution<uint8_t> dist;
+
+    for (int i = 0; i < NTLM_NONCE_LEN; ++i)
+        nonce[i] = static_cast<char>(dist(mt) & 0xFF);
 }
 
 /**
  * Prepares a challenge packet to be sent to the client
  * \note domain should be upper_case
  */
 void
 ntlm_make_challenge(ntlm_challenge *ch,
                     const char *domain, const char *,
                     const char *challenge_nonce, const int challenge_nonce_len,
                     const uint32_t flags)
 {
     int pl = 0;
     memset(ch, 0, sizeof(ntlm_challenge));  /* reset */
     memcpy(ch->hdr.signature, "NTLMSSP", 8);        /* set the signature */
     ch->hdr.type = htole32(NTLM_CHALLENGE); /* this is a challenge */
     if (domain != NULL) {
         // silently truncate the domain if it exceeds 2^16-1 bytes.
         // NTLM packets normally expect 2^8 bytes of domain.
         const uint16_t dlen = strlen(domain) & 0xFFFF;

=== modified file 'src/acl/Random.cc'
--- src/acl/Random.cc	2015-01-29 19:05:24 +0000
+++ src/acl/Random.cc	2015-02-08 12:51:02 +0000
@@ -1,37 +1,39 @@
 /*
  * Copyright (C) 1996-2015 The Squid Software Foundation and contributors
  *
  * Squid software is distributed under GPLv2+ license and includes
  * contributions from numerous individuals and organizations.
  * Please see the COPYING and CONTRIBUTORS files for details.
  */
 
 /* DEBUG: section 28    Access Control */
 
 #include "squid.h"
 #include "acl/FilledChecklist.h"
 #include "acl/Random.h"
 #include "Debug.h"
 #include "Parsing.h"
 #include "wordlist.h"
 
+#include <random>
+
 ACL *
 ACLRandom::clone() const
 {
     return new ACLRandom(*this);
 }
 
 ACLRandom::ACLRandom(char const *theClass) : data(0.0), class_(theClass)
 {
     memset(pattern, 0 , sizeof(pattern));
 }
 
 ACLRandom::ACLRandom(ACLRandom const & old) : data(old.data), class_(old.class_)
 {
     memcpy(pattern, old.pattern, sizeof(pattern));
 }
 
 ACLRandom::~ACLRandom()
 { }
 
 char const *
@@ -65,54 +67,60 @@
         debugs(28, DBG_PARSE_NOTE(DBG_IMPORTANT), "ACL random missing pattern");
         return;
     }
 
     debugs(28, 5, "aclParseRandomData: " << t);
 
     // seed random generator ...
     srand(time(NULL));
 
     if (sscanf(t, "%[0-9]:%[0-9]", bufa, bufb) == 2) {
         int a = xatoi(bufa);
         int b = xatoi(bufb);
         if (a <= 0 || b <= 0) {
             debugs(28, DBG_CRITICAL, "ERROR: ACL random with bad pattern: '" << t << "'");
             return;
         } else
             data = a / (double)(a+b);
     } else if (sscanf(t, "%[0-9]/%[0-9]", bufa, bufb) == 2) {
         int a = xatoi(bufa);
         int b = xatoi(bufb);
-        if (a <= 0 || b <= 0) {
+        if (a <= 0 || b <= 0 || a > b) {
             debugs(28, DBG_CRITICAL, "ERROR: ACL random with bad pattern: '" << t << "'");
             return;
         } else
             data = (double) a / (double) b;
     } else if (sscanf(t, "0.%[0-9]", bufa) == 1) {
         data = atof(t);
     } else {
         debugs(28, DBG_CRITICAL, "ERROR: ACL random with bad pattern: '" << t << "'");
         return;
     }
 
     // save the exact input pattern. so we can display it later.
     memcpy(pattern, t, min(sizeof(pattern)-1,strlen(t)));
 }
 
 int
 ACLRandom::match(ACLChecklist *)
 {
-    // make up the random value
-    double random = ((double)rand() / (double)RAND_MAX);
+    // make up the random value.
+    // The fixed-value default seed is fine because we are
+    // actually matching whether the random value is above
+    // or below the configured threshold ratio.
+    static std::mt19937 mt;
+    static std::uniform_real_distribution<> dist(0, 1);
+
+    const double random = dist(mt);
 
     debugs(28, 3, "ACL Random: " << name << " " << pattern << " test: " << data << " > " << random << " = " << ((data > random)?"MATCH":"NO MATCH") );
     return (data > random)?1:0;
 }
 
 SBufList
 ACLRandom::dump() const
 {
     SBufList sl;
     sl.push_back(SBuf(pattern));
     return sl;
 }
 

=== modified file 'src/auth/digest/Config.cc'
--- src/auth/digest/Config.cc	2015-01-20 10:29:45 +0000
+++ src/auth/digest/Config.cc	2015-02-08 07:33:25 +0000
@@ -22,40 +22,42 @@
 #include "base64.h"
 #include "cache_cf.h"
 #include "event.h"
 #include "helper.h"
 #include "HttpHeaderTools.h"
 #include "HttpReply.h"
 #include "HttpRequest.h"
 #include "mgr/Registration.h"
 #include "rfc2617.h"
 #include "SBuf.h"
 #include "SquidTime.h"
 #include "Store.h"
 #include "StrList.h"
 #include "wordlist.h"
 
 /* digest_nonce_h still uses explicit alloc()/freeOne() MemPool calls.
  * XXX: convert to MEMPROXY_CLASS() API
  */
 #include "mem/Pool.h"
 
+#include <random>
+
 static AUTHSSTATS authenticateDigestStats;
 
 helper *digestauthenticators = NULL;
 
 static hash_table *digest_nonce_cache;
 
 static int authdigest_initialised = 0;
 static MemAllocator *digest_nonce_pool = NULL;
 
 enum http_digest_attr_type {
     DIGEST_USERNAME,
     DIGEST_REALM,
     DIGEST_QOP,
     DIGEST_ALGORITHM,
     DIGEST_URI,
     DIGEST_NONCE,
     DIGEST_NC,
     DIGEST_CNONCE,
     DIGEST_RESPONSE,
     DIGEST_ENUM_END
@@ -130,64 +132,62 @@
      * reject the request if it did not match the nonce from that header
      * or if the time-stamp value is not recent enough. In this way the
      * server can limit the time of the nonce's validity. The inclusion of
      * the ETag prevents a replay request for an updated version of the
      * resource.  (Note: including the IP address of the client in the
      * nonce would appear to offer the server the ability to limit the
      * reuse of the nonce to the same client that originally got it.
      * However, that would break proxy farms, where requests from a single
      * user often go through different proxies in the farm. Also, IP
      * address spoofing is not that hard.)
      * ====
      *
      * Now for my reasoning:
      * We will not accept a unrecognised nonce->we have all recognisable
      * nonces stored. If we send out unique base64 encodings we guarantee
      * that a given nonce applies to only one user (barring attacks or
      * really bad timing with expiry and creation).  Using a random
      * component in the nonce allows us to loop to find a unique nonce.
      * We use H(nonce_data) so the nonce is meaningless to the reciever.
      * So our nonce looks like base64(H(timestamp,pointertohash,randomdata))
-     * And even if our randomness is not very random (probably due to
-     * bad coding on my part) we don't really care - the timestamp and
-     * memory pointer also guarantee local uniqueness in the input to the hash
-     * function.
+     * And even if our randomness is not very random we don't really care
+     * - the timestamp and memory pointer also guarantee local uniqueness
+     * in the input to the hash function.
      */
+    // NP: this will likely produce the same randomness sequences for each worker
+    // since they should all start within the 1-second resolution of seed value.
+    static std::mt19937 mt(static_cast<uint32_t>(getCurrentTime() & 0xFFFFFFFF));
+    static std::uniform_int_distribution<uint32_t> newRandomData;
 
     /* create a new nonce */
     newnonce->nc = 0;
     newnonce->flags.valid = true;
     newnonce->noncedata.self = newnonce;
     newnonce->noncedata.creationtime = current_time.tv_sec;
-    newnonce->noncedata.randomdata = squid_random();
+    newnonce->noncedata.randomdata = newRandomData(mt);
 
     authDigestNonceEncode(newnonce);
-    /*
-     * loop until we get a unique nonce. The nonce creation must
-     * have a random factor
-     */
 
+    // ensure temporal uniqueness by checking for existing nonce
     while (authenticateDigestNonceFindNonce((char const *) (newnonce->key))) {
         /* create a new nonce */
-        newnonce->noncedata.randomdata = squid_random();
-        /* Bug 3526 high performance fix: add 1 second to creationtime to avoid duplication */
-        ++newnonce->noncedata.creationtime;
+        newnonce->noncedata.randomdata = newRandomData(mt);
         authDigestNonceEncode(newnonce);
     }
 
     hash_join(digest_nonce_cache, newnonce);
     /* the cache's link */
     authDigestNonceLink(newnonce);
     newnonce->flags.incache = true;
     debugs(29, 5, "created nonce " << newnonce << " at " << newnonce->noncedata.creationtime);
     return newnonce;
 }
 
 static void
 authenticateDigestNonceDelete(digest_nonce_h * nonce)
 {
     if (nonce) {
         assert(nonce->references == 0);
 #if UNREACHABLECODE
 
         if (nonce->flags.incache)
             hash_remove_link(digest_nonce_cache, nonce);

=== modified file 'src/auth/digest/Config.h'
--- src/auth/digest/Config.h	2015-01-13 07:25:36 +0000
+++ src/auth/digest/Config.h	2015-02-08 07:33:06 +0000
@@ -15,41 +15,41 @@
 #include "helper/forward.h"
 #include "rfc2617.h"
 
 namespace Auth
 {
 namespace Digest
 {
 class User;
 }
 }
 
 /* Generic */
 typedef struct _digest_nonce_data digest_nonce_data;
 typedef struct _digest_nonce_h digest_nonce_h;
 
 /* data to be encoded into the nonce's b64 representation */
 struct _digest_nonce_data {
     time_t creationtime;
     /* in memory address of the nonce struct (similar purpose to an ETag) */
     digest_nonce_h *self;
-    long randomdata;
+    uint32_t randomdata;
 };
 
 /* the nonce structure we'll pass around */
 
 struct _digest_nonce_h : public hash_link {
     digest_nonce_data noncedata;
     /* number of uses we've seen of this nonce */
     unsigned long nc;
     /* reference count */
     short references;
     /* the auth_user this nonce has been tied to */
     Auth::Digest::User *user;
     /* has this nonce been invalidated ? */
 
     struct {
         bool valid;
         bool incache;
     } flags;
 };
 

=== modified file 'src/dns_internal.cc'
--- src/dns_internal.cc	2015-02-03 21:24:30 +0000
+++ src/dns_internal.cc	2015-02-08 06:05:05 +0000
@@ -23,40 +23,41 @@
 #include "fd.h"
 #include "fde.h"
 #include "ip/tools.h"
 #include "MemBuf.h"
 #include "mgr/Registration.h"
 #include "SquidConfig.h"
 #include "SquidTime.h"
 #include "Store.h"
 #include "tools.h"
 #include "util.h"
 #include "wordlist.h"
 
 #if SQUID_SNMP
 #include "snmp_core.h"
 #endif
 
 #if HAVE_ARPA_NAMESER_H
 #include <arpa/nameser.h>
 #endif
 #include <cerrno>
+#include <random>
 #if HAVE_RESOLV_H
 #include <resolv.h>
 #endif
 
 #if _SQUID_WINDOWS_
 #define REG_TCPIP_PARA_INTERFACES "SYSTEM\\CurrentControlSet\\Services\\Tcpip\\Parameters\\Interfaces"
 #define REG_TCPIP_PARA "SYSTEM\\CurrentControlSet\\Services\\Tcpip\\Parameters"
 #define REG_VXD_MSTCP "SYSTEM\\CurrentControlSet\\Services\\VxD\\MSTCP"
 #endif
 #ifndef _PATH_RESCONF
 #define _PATH_RESCONF "/etc/resolv.conf"
 #endif
 #ifndef NS_DEFAULTPORT
 #define NS_DEFAULTPORT 53
 #endif
 
 #ifndef NS_MAXDNAME
 #define NS_MAXDNAME 1025
 #endif
 
@@ -1041,45 +1042,48 @@
     return -1;
 }
 
 static idns_query *
 idnsFindQuery(unsigned short id)
 {
     dlink_node *n;
     idns_query *q;
 
     for (n = lru_list.tail; n; n = n->prev) {
         q = (idns_query*)n->data;
 
         if (q->query_id == id)
             return q;
     }
 
     return NULL;
 }
 
 static unsigned short
-idnsQueryID(void)
+idnsQueryID()
 {
-    unsigned short id = squid_random() & 0xFFFF;
+    // NP: apparently ranlux are faster, but not quite as "proven"
+    static std::mt19937 mt(static_cast<uint32_t>(getCurrentTime() & 0xFFFFFFFF));
+    unsigned short id = mt() & 0xFFFF;
     unsigned short first_id = id;
 
+    // ensure temporal uniqueness by looking for an existing use
     while (idnsFindQuery(id)) {
         ++id;
 
         if (id == first_id) {
             debugs(78, DBG_IMPORTANT, "idnsQueryID: Warning, too many pending DNS requests");
             break;
         }
     }
 
     return id;
 }
 
 static void
 idnsCallback(idns_query *q, const char *error)
 {
     IDNSCB *callback;
     void *cbdata;
 
     if (error)
         q->error = error;

=== modified file 'src/event.cc'
--- src/event.cc	2015-01-13 07:25:36 +0000
+++ src/event.cc	2015-02-07 12:18:48 +0000
@@ -1,40 +1,40 @@
 /*
  * Copyright (C) 1996-2015 The Squid Software Foundation and contributors
  *
  * Squid software is distributed under GPLv2+ license and includes
  * contributions from numerous individuals and organizations.
  * Please see the COPYING and CONTRIBUTORS files for details.
  */
 
 /* DEBUG: section 41    Event Processing */
 
 #include "squid.h"
-#include "compat/drand48.h"
 #include "event.h"
 #include "mgr/Registration.h"
 #include "profiler/Profiler.h"
 #include "SquidTime.h"
 #include "Store.h"
 #include "tools.h"
 
 #include <cmath>
+#include <random>
 
 /* The list of event processes */
 
 static OBJH eventDump;
 static const char *last_event_ran = NULL;
 
 // This AsyncCall dialer can be configured to check that the event cbdata is
 // valid before calling the event handler
 class EventDialer: public CallDialer
 {
 public:
     typedef CallDialer Parent;
 
     EventDialer(EVH *aHandler, void *anArg, bool lockedArg);
     EventDialer(const EventDialer &d);
     virtual ~EventDialer();
 
     virtual void print(std::ostream &os) const;
     virtual bool canDial(AsyncCall &call);
 
@@ -95,46 +95,46 @@
 {
 }
 
 ev_entry::~ev_entry()
 {
     if (cbdata)
         cbdataReferenceDone(arg);
 }
 
 void
 eventAdd(const char *name, EVH * func, void *arg, double when, int weight, bool cbdata)
 {
     EventScheduler::GetInstance()->schedule(name, func, arg, when, weight, cbdata);
 }
 
 /* same as eventAdd but adds a random offset within +-1/3 of delta_ish */
 void
 eventAddIsh(const char *name, EVH * func, void *arg, double delta_ish, int weight)
 {
     if (delta_ish >= 3.0) {
-        const double two_third = (2.0 * delta_ish) / 3.0;
-        delta_ish = two_third + (drand48() * two_third);
-        /*
-         * I'm sure drand48() isn't portable.  Tell me what function
-         * you have that returns a random double value in the range 0,1.
-         */
+        // Default seed is fine. We just need values random enough
+        // relative to each other to prevent waves of synchronised activity.
+        static std::mt19937 rng;
+        auto third = (delta_ish/3.0);
+        std::uniform_real_distribution<> thirdIsh(delta_ish - third, delta_ish + third);
+        delta_ish = thirdIsh(rng);
     }
 
     eventAdd(name, func, arg, delta_ish, weight);
 }
 
 void
 eventDelete(EVH * func, void *arg)
 {
     EventScheduler::GetInstance()->cancel(func, arg);
 }
 
 void
 eventInit(void)
 {
     Mgr::RegisterAction("events", "Event Queue", eventDump, 0, 1);
 }
 
 static void
 eventDump(StoreEntry * sentry)
 {

=== modified file 'src/fs/ufs/UFSSwapDir.cc'
--- src/fs/ufs/UFSSwapDir.cc	2015-01-13 07:25:36 +0000
+++ src/fs/ufs/UFSSwapDir.cc	2015-02-08 06:22:15 +0000
@@ -16,40 +16,41 @@
 #include "disk.h"
 #include "DiskIO/DiskIOModule.h"
 #include "DiskIO/DiskIOStrategy.h"
 #include "fde.h"
 #include "FileMap.h"
 #include "globals.h"
 #include "Parsing.h"
 #include "RebuildState.h"
 #include "SquidConfig.h"
 #include "SquidMath.h"
 #include "SquidTime.h"
 #include "StatCounters.h"
 #include "store_key_md5.h"
 #include "StoreSearchUFS.h"
 #include "StoreSwapLogData.h"
 #include "tools.h"
 #include "UFSSwapDir.h"
 
 #include <cerrno>
 #include <cmath>
+#include <random>
 #if HAVE_SYS_STAT_H
 #include <sys/stat.h>
 #endif
 
 int Fs::Ufs::UFSSwapDir::NumberOfUFSDirs = 0;
 int *Fs::Ufs::UFSSwapDir::UFSDirToGlobalDirMapping = NULL;
 
 class UFSCleanLog : public SwapDir::CleanLog
 {
 
 public:
     UFSCleanLog(SwapDir *);
     /** Get the next entry that is a candidate for clean log writing
      */
     virtual const StoreEntry *nextEntry();
     /** "write" an entry to the clean log file.
      */
     virtual void write(StoreEntry const &);
     char *cur;
     char *newLog;
@@ -1025,41 +1026,43 @@
 
             if (!UFSSwapDir::IsUFSDir(sd))
                 continue;
 
             UFSSwapDir *usd = dynamic_cast<UFSSwapDir *>(sd);
 
             assert (usd);
 
             UFSDirToGlobalDirMapping[n] = i;
             ++n;
 
             j += (usd->l1 * usd->l2);
         }
 
         assert(n == NumberOfUFSDirs);
         /*
          * Start the commonUfsDirClean() swap_index with a random
          * value.  j equals the total number of UFS level 2
          * swap directories
          */
-        swap_index = (int) (squid_random() % j);
+        std::mt19937 mt(static_cast<uint32_t>(getCurrentTime() & 0xFFFFFFFF));
+        std::uniform_int_distribution<> dist(0, j);
+        swap_index = dist(mt);
     }
 
     /* if the rebuild is finished, start cleaning directories. */
     if (0 == StoreController::store_dirs_rebuilding) {
         n = DirClean(swap_index);
         ++swap_index;
     }
 
     eventAdd("storeDirClean", CleanEvent, NULL,
              15.0 * exp(-0.25 * n), 1);
 }
 
 bool
 Fs::Ufs::UFSSwapDir::IsUFSDir(SwapDir * sd)
 {
     UFSSwapDir *mySD = dynamic_cast<UFSSwapDir *>(sd);
     return (mySD != 0) ;
 }
 
 /*

=== modified file 'src/main.cc'
--- src/main.cc	2015-01-29 16:09:11 +0000
+++ src/main.cc	2015-02-08 09:41:18 +0000
@@ -1367,42 +1367,40 @@
 
     /* call mallopt() before anything else */
 #if HAVE_MALLOPT
 #ifdef M_GRAIN
     /* Round up all sizes to a multiple of this */
     mallopt(M_GRAIN, 16);
 
 #endif
 #ifdef M_MXFAST
     /* biggest size that is considered a small block */
     mallopt(M_MXFAST, 256);
 
 #endif
 #ifdef M_NBLKS
     /* allocate this many small blocks at once */
     mallopt(M_NLBLKS, 32);
 
 #endif
 #endif /* HAVE_MALLOPT */
 
-    squid_srandom(time(NULL));
-
     getCurrentTime();
 
     squid_start = current_time;
 
     failure_notify = fatal_dump;
 
 #if USE_WIN32_SERVICE
 
     WIN32_svcstatusupdate(SERVICE_START_PENDING, 10000);
 
 #endif
 
     mainParseOptions(argc, argv);
 
     if (opt_parse_cfg_only) {
         Debug::parseOptions("ALL,1");
     }
 
 #if USE_WIN32_SERVICE
 

=== modified file 'src/tests/SBufFindTest.cc'
--- src/tests/SBufFindTest.cc	2015-01-13 07:25:36 +0000
+++ src/tests/SBufFindTest.cc	2015-02-08 15:55:09 +0000
@@ -1,68 +1,67 @@
 /*
  * Copyright (C) 1996-2015 The Squid Software Foundation and contributors
  *
  * Squid software is distributed under GPLv2+ license and includes
  * contributions from numerous individuals and organizations.
  * Please see the COPYING and CONTRIBUTORS files for details.
  */
 
 #include "squid.h"
 #include "base/CharacterSet.h"
 #include "SBufFindTest.h"
+
 #include <cppunit/extensions/HelperMacros.h>
 #include <cppunit/Message.h>
 #include <limits>
+#include <random>
 
 /* TODO: The whole SBufFindTest class is currently implemented as a single
    CppUnit test case (because we do not want to register and report every one
    of the thousands of generated test cases). Is there a better way to
    integrate with CppUnit?
  */
 
 SBufFindTest::SBufFindTest():
     caseLimit(std::numeric_limits<int>::max()),
     errorLimit(std::numeric_limits<int>::max()),
-    randomSeed(1),
     hushSimilar(true),
     maxHayLength(40),
     thePos(0),
     thePlacement(placeEof),
     theStringPos(0),
     theBareNeedlePos(0),
     theFindString(0),
     theFindSBuf(0),
     theReportFunc(),
     theReportNeedle(),
     theReportPos(),
     theReportQuote('"'),
     caseCount(0),
     errorCount(0),
     reportCount(0)
 {
 }
 
 void
 SBufFindTest::run()
 {
-    srandom(randomSeed);
-
     for (SBuf::size_type hayLen = 0U; hayLen <= maxHayLength; nextLen(hayLen, maxHayLength)) {
         const SBuf cleanHay = RandomSBuf(hayLen);
 
         const SBuf::size_type maxNeedleLen = hayLen + 10;
         for (SBuf::size_type needleLen = 0U; needleLen <= maxNeedleLen; nextLen(needleLen, maxNeedleLen)) {
             theSBufNeedle = RandomSBuf(needleLen);
 
             for (int i = 0; i < placeEof; i++) {
                 thePlacement = Placement(i);
                 placeNeedle(cleanHay);
 
                 const SBuf::size_type maxArg =
                     max(theSBufHay.length(), theSBufNeedle.length()) + 10;
                 for (thePos = 0; thePos <= maxArg; nextLen(thePos, maxArg))
                     testAllMethods();
 
                 // the special npos value is not tested as the behavior is
                 //  different from std::string (where the behavior is undefined)
                 //  It is ad-hoc tested in testSBuf instead
                 //thePos = SBuf::npos;
@@ -363,53 +362,53 @@
               reportPos << ") returns " << PosToString(theFindSBuf) <<
               " instead of " << PosToString(theFindString) <<
               std::endl <<
               "    std::string(\""  << theStringHay << "\")." << method <<
               "(" << theReportQuote << theReportNeedle << theReportQuote <<
               reportPos << ") returns " << PosToString(theFindString) <<
               std::endl <<
               "    category: " << category << std::endl;
 
     ++reportCount;
 }
 
 /// generates a random string of the specified length
 SBuf
 SBufFindTest::RandomSBuf(const int length)
 {
     static const char characters[] =
         "0123456789"
         "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
         "abcdefghijklomnpqrstuvwxyz";
+
+    static std::mt19937 mt(time(0));
+
     // sizeof() counts the terminating zero at the end of characters
+    // and the distribution is an 'inclusive' value range, so -2
     // TODO: add \0 character (needs reporting adjustments to print it as \0)
-    static const size_t charCount = sizeof(characters)-1;
-
-    char buf[length];
-    for (int i = 0; i < length; ++i) {
-        const unsigned int pos = random() % charCount;
-        assert(pos < sizeof(characters));
-        assert(characters[pos] > 32);
-        buf[i] = characters[random() % charCount];
-    }
+    static std::uniform_int_distribution<uint8_t> dist(0, sizeof(characters)-2);
 
-    return SBuf(buf, length);
+    SBuf buf;
+    buf.reserveCapacity(length);
+    for (int i = 0; i < length; ++i)
+        buf.append(characters[dist(mt)]);
+    return buf;
 }
 
 /// increments len to quickly cover [0, max] range, slowing down in risky areas
 /// jumps to max+1 if caseLimit is reached
 void
 SBufFindTest::nextLen(SBuf::size_type &len, const SBuf::size_type max)
 {
     assert(len <= max);
 
     if (caseCount >= caseLimit)
         len = max+1; // avoid future test cases
     else if (len <= 10)
         ++len; // move slowly at the beginning of the [0,max] range
     else if (len >= max - 10)
         ++len; // move slowly at the end of the [0,max] range
     else {
         // move fast in the middle of the [0,max] range
         len += len/10 + 1;
 
         // but do not overshoot the interesting area at the end of the range

=== modified file 'src/tests/SBufFindTest.h'
--- src/tests/SBufFindTest.h	2015-01-13 07:25:36 +0000
+++ src/tests/SBufFindTest.h	2015-02-08 15:36:01 +0000
@@ -9,41 +9,40 @@
 #ifndef SQUID_SRC_TEST_SBUFFINDTEST_H
 #define SQUID_SRC_TEST_SBUFFINDTEST_H
 
 #include "SBuf.h"
 
 #include <set>
 #include <string>
 
 /// Generates and executes a [configurable] large number of SBuf::*find()
 /// test cases using random strings. Reports detected failures.
 class SBufFindTest
 {
 public:
     SBufFindTest();
 
     void run(); ///< generates and executes cases using configuration params
 
     /* test configuration parameters; can be optionally set before run() */
     int caseLimit; ///< approximate caseCount limit
     int errorLimit; ///< errorCount limit
-    unsigned int randomSeed; ///< pseudo-random sequence choice
     /// whether to report only one failed test case per "category"
     bool hushSimilar;
     /// approximate maximum generated hay string length
     SBuf::size_type maxHayLength;
 
     /// Supported algorithms for placing needle in the hay.
     typedef enum { placeBeginning, placeMiddle, placeEnd, placeNowhere,
                    placeEof
                  } Placement; // placeLast marker must terminate
 protected:
 
     static SBuf RandomSBuf(const int length);
     void nextLen(SBuf::size_type &len, const SBuf::size_type max);
     void placeNeedle(const SBuf &cleanHay);
 
     void testAllMethods();
     void testFindDefs();
     void testFind();
     void testRFindDefs();
     void testRFind();

=== modified file 'test-suite/hash.c'
--- test-suite/hash.c	2015-01-13 07:25:36 +0000
+++ test-suite/hash.c	2015-02-08 16:25:48 +0000
@@ -337,46 +337,49 @@
  */
 int
 main(void)
 {
     hash_table *hid;
     int i;
     LOCAL_ARRAY(char, buf, BUFSIZ);
     LOCAL_ARRAY(char, todelete, BUFSIZ);
     hash_link *walker = NULL;
 
     todelete[0] = '\0';
     printf("init\n");
 
     printf("creating hash table\n");
     if ((hid = hash_create(strcmp, 229, hash_string)) < 0) {
         printf("hash_create error.\n");
         exit(1);
     }
     printf("done creating hash table: %d\n", hid);
 
+    std::mt19937 mt;
+    std::uniform_int_distribution<> dist(0,16);
+
     while (fgets(buf, BUFSIZ, stdin)) {
         buf[strlen(buf) - 1] = '\0';
         printf("Inserting '%s' for item %p to hash table: %d\n",
                buf, buf, hid);
         hash_insert(hid, xstrdup(buf), (void *) 0x12345678);
-        if (random() % 17 == 0)
+        if (dist(mt) == 0)
             strcpy(todelete, buf);
     }
 
     printf("walking hash table...\n");
     for (i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
         printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
                walker->item);
     }
     printf("done walking hash table...\n");
 
     if (todelete[0]) {
         printf("deleting %s from %d\n", todelete, hid);
         if (hash_delete(hid, todelete))
             printf("hash_delete error\n");
     }
     printf("walking hash table...\n");
     for (i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
         printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
                walker->item);
     }

=== modified file 'test-suite/splay.cc'
--- test-suite/splay.cc	2015-01-13 07:25:36 +0000
+++ test-suite/splay.cc	2015-02-08 05:38:19 +0000
@@ -1,42 +1,42 @@
 /*
  * Copyright (C) 1996-2015 The Squid Software Foundation and contributors
  *
  * Squid software is distributed under GPLv2+ license and includes
  * contributions from numerous individuals and organizations.
  * Please see the COPYING and CONTRIBUTORS files for details.
  */
 
 /*
  * based on ftp://ftp.cs.cmu.edu/user/sleator/splaying/top-down-splay.c
  * http://bobo.link.cs.cmu.edu/cgi-bin/splay/splay-cgi.pl
  */
 
 #include "squid.h"
+#include "splay.h"
+#include "util.h"
 
 #include <cstdlib>
 #if HAVE_UNISTD_H
 #include <unistd.h>
 #endif
-
-#include "splay.h"
-#include "util.h"
+#include <random>
 
 class intnode
 {
 
 public:
     intnode() : i(0) {}
 
     intnode (int anInt) : i (anInt) {}
 
     int i;
 };
 
 int
 compareintvoid(void * const &a, void * const &n)
 {
     intnode *A = (intnode *)a;
     intnode *B = (intnode *)n;
     return A->i - B->i;
 }
 
@@ -112,122 +112,123 @@
 
 void
 destint(intnode * &data)
 {
     delete data;
 }
 
 int
 compareintref(intnode const &a, intnode const &b)
 {
     return a.i - b.i;
 }
 
 void
 destintref (intnode &)
 {}
 
 int
 main(int argc, char *argv[])
 {
+    std::mt19937 generator;
+    std::uniform_int_distribution<int> distribution;
+    auto nextRandom = std::bind (distribution, generator);
+
     {
-        int i;
-        intnode *I;
         /* test void * splay containers */
         splayNode *top = NULL;
-        squid_srandom(time(NULL));
 
-        for (i = 0; i < 100; ++i) {
-            I = (intnode *)xcalloc(sizeof(intnode), 1);
-            I->i = squid_random();
+        for (int i = 0; i < 100; ++i) {
+            intnode *I = (intnode *)xcalloc(sizeof(intnode), 1);
+            I->i = nextRandom();
             if (top)
                 top = top->insert(I, compareintvoid);
             else
                 top = new splayNode(static_cast<void*>(new intnode(101)));
         }
 
         SplayCheck::BeginWalk();
         top->walk(SplayCheck::WalkVoid, NULL);
 
         SplayCheck::BeginWalk();
         top->walk(SplayCheck::WalkVoid, NULL);
         top->destroy(destintvoid);
     }
 
     /* test typesafe splay containers */
     {
         /* intnode* */
         SplayNode<intnode *> *safeTop = new SplayNode<intnode *>(new intnode(101));
 
         for ( int i = 0; i < 100; ++i) {
             intnode *I;
             I = new intnode;
-            I->i = squid_random();
+            I->i = nextRandom();
             safeTop = safeTop->insert(I, compareint);
         }
 
         SplayCheck::BeginWalk();
         safeTop->walk(SplayCheck::WalkNode, NULL);
 
         safeTop->destroy(destint);
     }
     {
         /* intnode */
         SplayNode<intnode> *safeTop = new SplayNode<intnode>(101);
 
         for (int i = 0; i < 100; ++i) {
             intnode I;
-            I.i = squid_random();
+            I.i = nextRandom();
             safeTop = safeTop->insert(I, compareintref);
         }
 
         SplayCheck::BeginWalk();
         safeTop->walk(SplayCheck::WalkNodeRef, NULL);
 
         safeTop->destroy(destintref);
     }
 
     /* check the check routine */
     {
         SplayCheck::BeginWalk();
         intnode I;
         I.i = 1;
         /* check we don't segfault on NULL splay calls */
         SplayCheck::WalkNodeRef(I, NULL);
         I.i = 0;
         SplayCheck::ExpectedFail = true;
         SplayCheck::WalkNodeRef(I, NULL);
     }
 
     {
         /* check for begin() */
         Splay<intnode> *safeTop = new Splay<intnode>();
 
         if (safeTop->start() != NULL)
             exit (1);
 
         if (safeTop->finish() != NULL)
             exit (1);
 
         for (int i = 0; i < 100; ++i) {
             intnode I;
-            I.i = squid_random();
+            I.i = nextRandom();
 
             if (I.i > 50 && I.i < 10000000)
                 safeTop->insert(I, compareintref);
         }
 
         {
             intnode I;
             I.i = 50;
             safeTop->insert (I, compareintref);
             I.i = 10000000;
             safeTop->insert (I, compareintref);
         }
 
         if (!safeTop->start())
             exit (1);
 
         if (safeTop->start()->data.i != 50)
             exit (1);
 
         if (!safeTop->finish())



More information about the squid-dev mailing list