1 /*-
2 * Public Domain 2014-2018 MongoDB, Inc.
3 * Public Domain 2008-2014 WiredTiger, Inc.
4 *
5 * This is free and unencumbered software released into the public domain.
6 *
7 * Anyone is free to copy, modify, publish, use, compile, sell, or
8 * distribute this software, either in source code form or as a compiled
9 * binary, for any purpose, commercial or non-commercial, and by any
10 * means.
11 *
12 * In jurisdictions that recognize copyright laws, the author or authors
13 * of this software dedicate any and all copyright interest in the
14 * software to the public domain. We make this dedication for the benefit
15 * of the public at large and to the detriment of our heirs and
16 * successors. We intend this dedication to be an overt act of
17 * relinquishment in perpetuity of all present and future rights to this
18 * software under copyright law.
19 *
20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
23 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
24 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
25 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
26 * OTHER DEALINGS IN THE SOFTWARE.
27 */
28
29 #include "wt_internal.h"
30
31 /*
32 * This is an implementation of George Marsaglia's multiply-with-carry pseudo-
33 * random number generator. Computationally fast, with reasonable randomness
34 * properties, and a claimed period of > 2^60.
35 *
36 * Be very careful about races here. Multiple threads can call __wt_random
37 * concurrently, and it is okay if those concurrent calls get the same return
38 * value. What is *not* okay is if reading/writing the shared state races and
39 * uses two different values for m_w or m_z. That can result in a stored value
40 * of zero, in which case they will be stuck on zero forever. Take a local copy
41 * of the values to avoid that, and read/write in atomic, 8B chunks.
42 */
43 #undef M_W
44 #define M_W(r) r.x.w
45 #undef M_Z
46 #define M_Z(r) r.x.z
47
48 /*
49 * __wt_random_init --
50 * Initialize return of a 32-bit pseudo-random number.
51 */
52 void
__wt_random_init(WT_RAND_STATE volatile * rnd_state)53 __wt_random_init(WT_RAND_STATE volatile * rnd_state)
54 WT_GCC_FUNC_ATTRIBUTE((visibility("default")))
55 {
56 WT_RAND_STATE rnd;
57
58 M_W(rnd) = 521288629;
59 M_Z(rnd) = 362436069;
60 *rnd_state = rnd;
61 }
62
63 /*
64 * __wt_random_init_seed --
65 * Initialize the state of a 32-bit pseudo-random number.
66 * Use this, instead of __wt_random_init if we are running with multiple
67 * threads and we want each thread to initialize its own random state based
68 * on a different random seed.
69 */
70 void
__wt_random_init_seed(WT_SESSION_IMPL * session,WT_RAND_STATE volatile * rnd_state)71 __wt_random_init_seed(
72 WT_SESSION_IMPL *session, WT_RAND_STATE volatile * rnd_state)
73 WT_GCC_FUNC_ATTRIBUTE((visibility("default")))
74 {
75 struct timespec ts;
76 WT_RAND_STATE rnd;
77
78 __wt_epoch(session, &ts);
79 M_W(rnd) = (uint32_t)(ts.tv_nsec + 521288629);
80 M_Z(rnd) = (uint32_t)(ts.tv_nsec + 362436069);
81
82 *rnd_state = rnd;
83 }
84
85 /*
86 * __wt_random --
87 * Return a 32-bit pseudo-random number.
88 */
89 uint32_t
__wt_random(WT_RAND_STATE volatile * rnd_state)90 __wt_random(WT_RAND_STATE volatile * rnd_state)
91 WT_GCC_FUNC_ATTRIBUTE((visibility("default")))
92 {
93 WT_RAND_STATE rnd;
94 uint32_t w, z;
95
96 /*
97 * Take a copy of the random state so we can ensure that the
98 * calculation operates on the state consistently regardless of
99 * concurrent calls with the same random state.
100 */
101 rnd = *rnd_state;
102 w = M_W(rnd);
103 z = M_Z(rnd);
104
105 /*
106 * Check if the value goes to 0 (from which we won't recover), and reset
107 * to the initial state. This has additional benefits if a caller fails
108 * to initialize the state, or initializes with a seed that results in a
109 * short period.
110 */
111 if (z == 0 || w == 0) {
112 __wt_random_init(&rnd);
113 w = M_W(rnd);
114 z = M_Z(rnd);
115 }
116
117 M_Z(rnd) = z = 36969 * (z & 65535) + (z >> 16);
118 M_W(rnd) = w = 18000 * (w & 65535) + (w >> 16);
119 *rnd_state = rnd;
120
121 return ((z << 16) + (w & 65535));
122 }
123