Import wiredtiger: ad95cba9b70470b5d301d0bd2ad8bff6c27aa588 from branch mongodb-master

ref: f76f0645bf..ad95cba9b7
for: 7.1.0-rc0

WT-10954 Make convergence less likely for random values

1 files changed, 36 insertions, 11 deletions

diff --git a/src/third_party/wiredtiger/src/support/rand.c b/src/third_party/wiredtiger/src/support/rand.c
index e8c742c1e6f..1c59466ac4b 100644
--- a/src/third_party/wiredtiger/src/support/rand.c
+++ b/src/third_party/wiredtiger/src/support/rand.c
@@ -37,6 +37,10 @@
  * reading/writing the shared state races and uses two different values for m_w or m_z. That can
  * result in a stored value of zero, in which case they will be stuck on zero forever. Take a local
  * copy of the values to avoid that, and read/write in atomic, 8B chunks.
+ *
+ * Please do not modify the behavior of __wt_random when it is used with the default seed. We have
+ * verified that it produces good-quality randomness for our uses within the WiredTiger library, so
+ * we would like to preserve its current behavior.
  */
 #undef M_V
 #define M_V(r) r.v
@@ -48,6 +52,10 @@
 #ifdef ENABLE_ANTITHESIS
 #include "instrumentation.h"
 #endif
+
+#define DEFAULT_SEED_W 521288629
+#define DEFAULT_SEED_Z 362436069
+
 /*
  * __wt_random_init --
  *     Initialize return of a 32-bit pseudo-random number.
@@ -57,8 +65,9 @@ __wt_random_init(WT_RAND_STATE volatile *rnd_state) WT_GCC_FUNC_ATTRIBUTE((visib
 {
     WT_RAND_STATE rnd;
 
-    M_W(rnd) = 521288629;
-    M_Z(rnd) = 362436069;
+    M_W(rnd) = DEFAULT_SEED_W;
+    M_Z(rnd) = DEFAULT_SEED_Z;
+
     *rnd_state = rnd;
 }
 
@@ -72,7 +81,16 @@ __wt_random_init_custom_seed(WT_RAND_STATE volatile *rnd_state, uint64_t v)
 {
     WT_RAND_STATE rnd;
 
+    /*
+     * XOR the provided seed with the initial seed. With high probability, this would provide a
+     * random-looking seed which has about 50% of the bits turned on. We don't need to check whether
+     * W or Z becomes 0, because we would handle it the first time we use this state to generate a
+     * random number.
+     */
     M_V(rnd) = v;
+    M_W(rnd) ^= DEFAULT_SEED_W;
+    M_Z(rnd) ^= DEFAULT_SEED_Z;
+
     *rnd_state = rnd;
 }
 
@@ -99,8 +117,8 @@ __wt_random_init_seed(WT_SESSION_IMPL *session, WT_RAND_STATE volatile *rnd_stat
      * Take the seconds and nanoseconds from the clock together with the thread ID to generate a
      * 64-bit seed, then smear that value using algorithm "xor" from Marsaglia, "Xorshift RNGs".
      */
-    M_W(rnd) = (uint32_t)ts.tv_sec ^ 521288629;
-    M_Z(rnd) = (uint32_t)ts.tv_nsec ^ 362436069;
+    M_W(rnd) = (uint32_t)ts.tv_sec ^ DEFAULT_SEED_W;
+    M_Z(rnd) = (uint32_t)ts.tv_nsec ^ DEFAULT_SEED_Z;
     rnd.v ^= (uint64_t)threadid;
     rnd.v ^= rnd.v << 13;
     rnd.v ^= rnd.v >> 7;
@@ -132,18 +150,25 @@ __wt_random(WT_RAND_STATE volatile *rnd_state) WT_GCC_FUNC_ATTRIBUTE((visibility
     z = M_Z(rnd);
 
     /*
-     * Check if the value goes to 0 (from which we won't recover), and reset to the initial state.
+     * Check if either of the two values goes to 0 (from which we won't recover), and reset it to
+     * the default initial state. This would never happen with the default seed, but we need this
+     * for the other cases.
+     *
+     * We do this one component at a time, so that if the random number generator was initialized
+     * from an explicitly provided seed, it would not reset the entire state and then effectively
+     * result in random number generators from different seeds converging. They would eventually
+     * converge if both W and Z become 0 at the same time, but this is very unlikely.
+     *
      * This has additional benefits if a caller fails to initialize the state, or initializes with a
      * seed that results in a short period.
      */
-    if (z == 0 || w == 0) {
-        __wt_random_init(&rnd);
-        w = M_W(rnd);
-        z = M_Z(rnd);
-    }
+    if (w == 0)
+        w = DEFAULT_SEED_W;
+    if (z == 0)
+        z = DEFAULT_SEED_Z;
 
-    M_Z(rnd) = z = 36969 * (z & 65535) + (z >> 16);
     M_W(rnd) = w = 18000 * (w & 65535) + (w >> 16);
+    M_Z(rnd) = z = 36969 * (z & 65535) + (z >> 16);
     *rnd_state = rnd;
 
     return ((z << 16) + (w & 65535));