[Valgrind-developers] valgrind: r8478 - in branches/PTRCHECK: exp-ptrcheck include

[<sv...@va...>]

Author: sewardj
Date: 2008-07-29 20:01:52 +0100 (Tue, 29 Jul 2008)
New Revision: 8478

Log:
Don't hardwire the value of RAND_MAX in pc_list.c -- it isn't the right
value for VG_(random) and caused "statistically lopsided" skip lists to 
be formed, and also segfaults due to array overruns.



Modified:
   branches/PTRCHECK/exp-ptrcheck/pc_list.c
   branches/PTRCHECK/include/pub_tool_libcbase.h


Modified: branches/PTRCHECK/exp-ptrcheck/pc_list.c
===================================================================
--- branches/PTRCHECK/exp-ptrcheck/pc_list.c	2008-07-29 17:54:49 UTC (rev 8477)
+++ branches/PTRCHECK/exp-ptrcheck/pc_list.c	2008-07-29 19:01:52 UTC (rev 8478)
@@ -57,11 +57,13 @@
  #define my_assert      assert
  #define my_printf      printf
  #define my_random(_x)  random()
+ #define MY_RAND_MAX    RAND_MAX
 #else
  #define my_malloc      VG_(malloc)
  #define my_free        VG_(free)
  #define my_assert      tl_assert
  #define my_printf      VG_(printf)
+ #define MY_RAND_MAX    VG_RAND_MAX
  #define my_random(_x)  VG_(random)(_x)
 #endif
 
@@ -829,10 +831,15 @@
    return x->forward[0];
 }
 
+/* Return a "random" float in the range [0.0 .. 1.0) */
 static float normalizedRandom(void)
 {
-   // Nb: 2147483647 == (2**31 - 1)
-   float f = ((float)my_random(NULL))/ 2147483647.0;
+   //static Int uh = 0, lh = 0;
+   float f = ((float)my_random(NULL))/ (MY_RAND_MAX + 1.0);
+   tl_assert(f >= 0.0);
+   tl_assert(f <= 1.0); /* in fact < and not <=, but we'll overlook that. */
+   //if (f >= 0.5) uh++; else lh++;
+   //VG_(printf)("(%d,%d) %d\n", lh, uh, (Int)(1000.0 * f));
    return f;
 }
 
@@ -840,7 +847,7 @@
 static Int ISList__randomLevel(ISList* o)
 {
    Int levels = 0;
-   while ( P < normalizedRandom() ) levels++;   
+   while ( P <= normalizedRandom() ) levels++;   
    return ( levels <= o->maxLevel ? levels : o->maxLevel+1 );
 }
 

Modified: branches/PTRCHECK/include/pub_tool_libcbase.h
===================================================================
--- branches/PTRCHECK/include/pub_tool_libcbase.h	2008-07-29 17:54:49 UTC (rev 8477)
+++ branches/PTRCHECK/include/pub_tool_libcbase.h	2008-07-29 19:01:52 UTC (rev 8478)
@@ -144,6 +144,7 @@
 // is NULL, it uses its own seed, which starts at zero.  If pSeed is
 // non-NULL, it uses and updates whatever pSeed points at.
 extern UInt VG_(random) ( /*MOD*/UInt* pSeed );
+#define VG_RAND_MAX (1ULL << 32)
 
 #endif   // __PUB_TOOL_LIBCBASE_H