diff options
author | Sean04 <sean.watt@mongodb.com> | 2023-04-28 00:13:43 +0000 |
---|---|---|
committer | Evergreen Agent <no-reply@evergreen.mongodb.com> | 2023-04-28 02:13:44 +0000 |
commit | 121bacad846b0f073ca88671a3eb683592ed08a4 (patch) | |
tree | 8a2734dea0b41a731f87e23fa6c038a7a302a8b8 | |
parent | 45d0a67cd56ab2e49f382397ebf60f46591dd467 (diff) | |
download | mongo-121bacad846b0f073ca88671a3eb683592ed08a4.tar.gz |
Import wiredtiger: ad95cba9b70470b5d301d0bd2ad8bff6c27aa588 from branch mongodb-master
ref: f76f0645bf..ad95cba9b7
for: 7.1.0-rc0
WT-10954 Make convergence less likely for random values
-rw-r--r-- | src/third_party/wiredtiger/import.data | 2 | ||||
-rw-r--r-- | src/third_party/wiredtiger/src/support/rand.c | 47 | ||||
-rw-r--r-- | src/third_party/wiredtiger/test/csuite/random/main.c | 122 | ||||
-rwxr-xr-x | src/third_party/wiredtiger/test/evergreen.yml | 10 |
4 files changed, 169 insertions, 12 deletions
diff --git a/src/third_party/wiredtiger/import.data b/src/third_party/wiredtiger/import.data index 4366d79af5e..c6e2058cbae 100644 --- a/src/third_party/wiredtiger/import.data +++ b/src/third_party/wiredtiger/import.data @@ -2,5 +2,5 @@ "vendor": "wiredtiger", "github": "wiredtiger/wiredtiger.git", "branch": "mongodb-master", - "commit": "f76f0645bfe93a6d17e4c0ae53111dc2e4e79d67" + "commit": "ad95cba9b70470b5d301d0bd2ad8bff6c27aa588" } 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)); diff --git a/src/third_party/wiredtiger/test/csuite/random/main.c b/src/third_party/wiredtiger/test/csuite/random/main.c new file mode 100644 index 00000000000..db7c66a7e09 --- /dev/null +++ b/src/third_party/wiredtiger/test/csuite/random/main.c @@ -0,0 +1,122 @@ +/*- + * Public Domain 2014-present MongoDB, Inc. + * Public Domain 2008-2014 WiredTiger, Inc. + * + * This is free and unencumbered software released into the public domain. + * + * Anyone is free to copy, modify, publish, use, compile, sell, or + * distribute this software, either in source code form or as a compiled + * binary, for any purpose, commercial or non-commercial, and by any + * means. + * + * In jurisdictions that recognize copyright laws, the author or authors + * of this software dedicate any and all copyright interest in the + * software to the public domain. We make this dedication for the benefit + * of the public at large and to the detriment of our heirs and + * successors. We intend this dedication to be an overt act of + * relinquishment in perpetuity of all present and future rights to this + * software under copyright law. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. + * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR + * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, + * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ +#include "test_util.h" + +extern int __wt_optind; + +static const uint32_t EXPECTED_RANDOM[] = {545736098, 2010324742, 2686179461, 3017381033, 410404515, + 3042610605, 893387793, 44244647, 89435757, 1127483053, 1854156410, 2560384123, 3010064238, + 1301488617, 3323393529, 2434747831, 3994507216, 1580311051, 2696652026, 2641292453, 1288576349, + 2355051412, 4276315443, 1777047127, 3932279793, 3621597994, 926735067, 2456119193, 2375585859, + 401207175, 2174557645, 311488597, 1590435109, 1836552166, 174471706}; + +/* + * test_random -- + * Verify that the random number generator produces the expected output. + */ +static void +test_random(bool verbose) +{ + WT_RAND_STATE rnd; + uint64_t count; + uint32_t r; + int i; + + i = 0; + count = 0; + + __wt_random_init(&rnd); + + if (verbose) + printf("%2s %11s %10s\n", "#", "count", "random"); + for (;;) { + count++; + r = __wt_random(&rnd); + + if (count == ((uint64_t)1) << i) { + if (verbose) + printf("%2d %11" PRIu64 " %10" PRIu32 "\n", i, count, r); + + testutil_assert(r == EXPECTED_RANDOM[i]); + + i++; + if ((size_t)i >= sizeof(EXPECTED_RANDOM) / sizeof(EXPECTED_RANDOM[0])) + break; + } + } +} + +static void usage(void) WT_GCC_FUNC_DECL_ATTRIBUTE((noreturn)); + +/* + * usage -- + * Print the usage information. + */ +static void +usage(void) +{ + fprintf(stderr, "usage: %s [-v]\n", progname); + exit(EXIT_FAILURE); +} + +/* + * main -- + * The main function. + */ +int +main(int argc, char *argv[]) +{ + int ch; + bool verbose; + + (void)testutil_set_progname(argv); + +#ifdef ENABLE_ANTITHESIS + if (argv != NULL) { /* Prevent the compiler from complaining about dead code below.*/ + printf("This test is not compatible with Antithesis.\n"); + return (EXIT_SUCCESS); + } +#endif + + verbose = false; + + while ((ch = __wt_getopt(progname, argc, argv, "v")) != EOF) + switch (ch) { + case 'v': + verbose = true; + break; + default: + usage(); + } + argc -= __wt_optind; + if (argc != 0) + usage(); + + test_random(verbose); + return (EXIT_SUCCESS); +} diff --git a/src/third_party/wiredtiger/test/evergreen.yml b/src/third_party/wiredtiger/test/evergreen.yml index 8bbc4aef0cc..84353d05943 100755 --- a/src/third_party/wiredtiger/test/evergreen.yml +++ b/src/third_party/wiredtiger/test/evergreen.yml @@ -1851,6 +1851,16 @@ tasks: vars: test_name: incr_backup + - name: csuite-random-test + tags: ["pull_request"] + depends_on: + - name: compile + commands: + - func: "fetch artifacts" + - func: "csuite test" + vars: + test_name: random + - name: csuite-random-abort-test tags: ["pull_request"] depends_on: |