Merge pull request #2088 from wiredtiger/rand-strict-alias

SERVER-19340 Avoid type aliasing in the random number generator.
(cherry picked from commit 3ec45a7204e01a5ac176550fdfef30a7402046e8)

18 files changed, 108 insertions, 44 deletions

diff --git a/bench/wtperf/wtperf.c b/bench/wtperf/wtperf.c
index 8780d270664..a4f679ae736 100644
--- a/bench/wtperf/wtperf.c
+++ b/bench/wtperf/wtperf.c
@@ -117,13 +117,13 @@ randomize_value(CONFIG_THREAD *thread, char *value_buf)
 	 * randomly chosen byte (other than the trailing NUL).
 	 * Make sure we don't write a NUL: keep the value the same length.
 	 */
-	i = __wt_random(thread->rnd) % (thread->cfg->value_sz - 1);
+	i = __wt_random(&thread->rnd) % (thread->cfg->value_sz - 1);
 	while (value_buf[i] == '\0' && i > 0)
 		--i;
 	if (i > 0) {
 		vb = (uint8_t *)value_buf;
-		vb[0] = (__wt_random(thread->rnd) % 255) + 1;
-		vb[i] = (__wt_random(thread->rnd) % 255) + 1;
+		vb[0] = (__wt_random(&thread->rnd) % 255) + 1;
+		vb[i] = (__wt_random(&thread->rnd) % 255) + 1;
 	}
 }
 
@@ -2155,13 +2155,11 @@ start_threads(CONFIG *cfg,
 		 * new RNG state further along in the sequence.
 		 */
 		if (i == 0)
-			__wt_random_init(thread->rnd);
-		else {
-			thread->rnd[0] = (thread - 1)->rnd[0];
-			thread->rnd[1] = (thread - 1)->rnd[1];
-		}
+			__wt_random_init(&thread->rnd);
+		else
+			thread->rnd = (thread - 1)->rnd;
 		for (j = 0; j < 1000; ++j)
-			(void)__wt_random(thread->rnd);
+			(void)__wt_random(&thread->rnd);
 
 		/*
 		 * Every thread gets a key/data buffer because we don't bother
@@ -2283,7 +2281,7 @@ wtperf_rand(CONFIG_THREAD *thread)
 	 * Use WiredTiger's random number routine: it's lock-free and fairly
 	 * good.
 	 */
-	rval = (uint64_t)__wt_random(thread->rnd);
+	rval = (uint64_t)__wt_random(&thread->rnd);
 
 	/* Use Pareto distribution to give 80/20 hot/cold values. */
 	if (cfg->pareto) {
diff --git a/bench/wtperf/wtperf.h b/bench/wtperf/wtperf.h
index 201623c7859..7ae55c5ca19 100644
--- a/bench/wtperf/wtperf.h
+++ b/bench/wtperf/wtperf.h
@@ -209,7 +209,7 @@ typedef struct {
 struct __config_thread {		/* Per-thread structure */
 	CONFIG *cfg;			/* Enclosing configuration */
 
-	uint32_t rnd[2];		/* Random number generation state */
+	WT_RAND_STATE rnd;		/* Random number generation state */
 
 	pthread_t handle;		/* Handle */
 
diff --git a/src/btree/row_srch.c b/src/btree/row_srch.c
index 97f751e0a09..6a8ca5f401c 100644
--- a/src/btree/row_srch.c
+++ b/src/btree/row_srch.c
@@ -491,7 +491,7 @@ restart:
 		WT_ASSERT(session, session->split_gen != 0);
 		WT_INTL_INDEX_GET(session, page, pindex);
 		descent = pindex->index[
-		    __wt_random(session->rnd) % pindex->entries];
+		    __wt_random(&session->rnd) % pindex->entries];
 
 		/*
 		 * Swap the parent page for the child page; return on error,
@@ -526,7 +526,7 @@ restart:
 		WT_ASSERT(session, session->split_gen != 0);
 		WT_INTL_INDEX_GET(session, btree->root.page, pindex);
 		cbt->slot = pindex->entries < 2 ?
-		    __wt_random(session->rnd) % page->pg_row_entries : 0;
+		    __wt_random(&session->rnd) % page->pg_row_entries : 0;
 
 		return (__wt_row_leaf_key(session,
 		    page, page->pg_row_d + cbt->slot, &cbt->search_key, 0));
diff --git a/src/conn/conn_api.c b/src/conn/conn_api.c
index b41cad25914..dacbb0539a9 100644
--- a/src/conn/conn_api.c
+++ b/src/conn/conn_api.c
@@ -1630,7 +1630,7 @@ wiredtiger_open(const char *home, WT_EVENT_HANDLER *event_handler,
 	session = conn->default_session = &conn->dummy_session;
 	session->iface.connection = &conn->iface;
 	session->name = "wiredtiger_open";
-	__wt_random_init(session->rnd);
+	__wt_random_init(&session->rnd);
 	__wt_event_handler_set(session, event_handler);
 
 	/* Remaining basic initialization of the connection structure. */
diff --git a/src/include/btree.i b/src/include/btree.i
index 3b42ded63cf..23cb54a4179 100644
--- a/src/include/btree.i
+++ b/src/include/btree.i
@@ -1163,7 +1163,7 @@ __wt_skip_choose_depth(WT_SESSION_IMPL *session)
 	u_int d;
 
 	for (d = 1; d < WT_SKIP_MAXDEPTH &&
-	    __wt_random(session->rnd) < WT_SKIP_PROBABILITY; d++)
+	    __wt_random(&session->rnd) < WT_SKIP_PROBABILITY; d++)
 		;
 	return (d);
 }
diff --git a/src/include/extern.h b/src/include/extern.h
index 774e3b445ff..a11f3dcd73c 100644
--- a/src/include/extern.h
+++ b/src/include/extern.h
@@ -643,8 +643,8 @@ extern uint32_t __wt_nlpo2(uint32_t v);
 extern uint32_t __wt_log2_int(uint32_t n);
 extern int __wt_ispo2(uint32_t v);
 extern uint32_t __wt_rduppo2(uint32_t n, uint32_t po2);
-extern void __wt_random_init(uint32_t *rnd);
-extern uint32_t __wt_random(uint32_t *rnd);
+extern void __wt_random_init(WT_RAND_STATE volatile *rnd_state);
+extern uint32_t __wt_random(WT_RAND_STATE volatile *rnd_state);
 extern int __wt_buf_grow_worker(WT_SESSION_IMPL *session, WT_ITEM *buf, size_t size);
 extern int __wt_buf_fmt(WT_SESSION_IMPL *session, WT_ITEM *buf, const char *fmt, ...) WT_GCC_FUNC_DECL_ATTRIBUTE((format (printf, 3, 4)));
 extern int __wt_buf_catfmt(WT_SESSION_IMPL *session, WT_ITEM *buf, const char *fmt, ...) WT_GCC_FUNC_DECL_ATTRIBUTE((format (printf, 3, 4)));
diff --git a/src/include/misc.h b/src/include/misc.h
index 12cf2dec375..ba12f00f672 100644
--- a/src/include/misc.h
+++ b/src/include/misc.h
@@ -215,3 +215,11 @@
 #define	__wt_page_swap(session, held, want, flags)			\
 	__wt_page_swap_func(session, held, want, flags)
 #endif
+
+/* Random number generator state. */
+union __wt_rand_state {
+	uint64_t v;
+	struct {
+		uint32_t w, z;
+	} x;
+};
diff --git a/src/include/session.h b/src/include/session.h
index 2c88727c662..3efb8011e3b 100644
--- a/src/include/session.h
+++ b/src/include/session.h
@@ -146,9 +146,9 @@ struct WT_COMPILER_TYPE_ALIGN(WT_CACHE_LINE_ALIGNMENT) __wt_session_impl {
 	 * to clear everything but the fields that persist.
 	 */
 #define	WT_SESSION_CLEAR_SIZE(s)					\
-	(WT_PTRDIFF(&(s)->rnd[0], s))
+	(WT_PTRDIFF(&(s)->rnd, s))
 
-	uint32_t rnd[2];		/* Random number generation state */
+	WT_RAND_STATE rnd;		/* Random number generation state */
 
 					/* Hashed handle reference list array */
 	SLIST_HEAD(__dhandles_hash, __wt_data_handle_cache) *dhhash;
diff --git a/src/include/wt_internal.h b/src/include/wt_internal.h
index 576827bebcd..fa25fc872f4 100644
--- a/src/include/wt_internal.h
+++ b/src/include/wt_internal.h
@@ -265,6 +265,8 @@ struct __wt_upd_skipped;
     typedef struct __wt_upd_skipped WT_UPD_SKIPPED;
 struct __wt_update;
     typedef struct __wt_update WT_UPDATE;
+union __wt_rand_state;
+    typedef union __wt_rand_state WT_RAND_STATE;
 /*
  * Forward type declarations for internal types: END
  * DO NOT EDIT: automatically built by dist/s_typedef.
diff --git a/src/log/log_slot.c b/src/log/log_slot.c
index 06a60f6088a..a08a9aff001 100644
--- a/src/log/log_slot.c
+++ b/src/log/log_slot.c
@@ -116,7 +116,7 @@ __wt_log_slot_join(WT_SESSION_IMPL *session, uint64_t mysize,
 		return (ENOMEM);
 	}
 find_slot:
-	allocated_slot = __wt_random(session->rnd) % WT_SLOT_ACTIVE;
+	allocated_slot = __wt_random(&session->rnd) % WT_SLOT_ACTIVE;
 	slot = log->slot_array[allocated_slot];
 	old_state = slot->slot_state;
 join_slot:
diff --git a/src/lsm/lsm_work_unit.c b/src/lsm/lsm_work_unit.c
index 675e450ce39..4f5e1516f1c 100644
--- a/src/lsm/lsm_work_unit.c
+++ b/src/lsm/lsm_work_unit.c
@@ -109,7 +109,7 @@ __wt_lsm_get_chunk_to_flush(WT_SESSION_IMPL *session,
 	 * enough to trigger checkpoints.
 	 */
 	if (evict_chunk != NULL && flush_chunk != NULL) {
-		chunk = (__wt_random(session->rnd) & 1) ?
+		chunk = (__wt_random(&session->rnd) & 1) ?
 		    evict_chunk : flush_chunk;
 		WT_ERR(__wt_lsm_manager_push_entry(
 		    session, WT_LSM_WORK_FLUSH, 0, lsm_tree));
diff --git a/src/session/session_api.c b/src/session/session_api.c
index 2b6b10971c8..b042e73f7d5 100644
--- a/src/session/session_api.c
+++ b/src/session/session_api.c
@@ -1064,7 +1064,7 @@ __wt_open_session(WT_CONNECTION_IMPL *conn,
 	WT_ERR(__wt_cond_alloc(session, "session", 0, &session_ret->cond));
 
 	if (WT_SESSION_FIRST_USE(session_ret))
-		__wt_random_init(session_ret->rnd);
+		__wt_random_init(&session_ret->rnd);
 
 	__wt_event_handler_set(session_ret,
 	    event_handler == NULL ? session->event_handler : event_handler);
diff --git a/src/support/rand.c b/src/support/rand.c
index bd51b2ea0d5..4d0f90b87dc 100644
--- a/src/support/rand.c
+++ b/src/support/rand.c
@@ -29,19 +29,22 @@
 #include "wt_internal.h"
 
 #undef	M_W
-#define	M_W	(rnd)[0]
+#define	M_W(r)	r.x.w
 #undef	M_Z
-#define	M_Z	(rnd)[1]
+#define	M_Z(r)	r.x.z
 
 /*
  * __wt_random_init --
  *	Initialize return of a 32-bit pseudo-random number.
  */
 void
-__wt_random_init(uint32_t *rnd)
+__wt_random_init(WT_RAND_STATE volatile * rnd_state)
 {
-	M_W = 521288629;
-	M_Z = 362436069;
+	WT_RAND_STATE rnd;
+
+	M_W(rnd) = 521288629;
+	M_Z(rnd) = 362436069;
+	*rnd_state = rnd;
 }
 
 /*
@@ -60,11 +63,32 @@ __wt_random_init(uint32_t *rnd)
  * forever.  Take local copies of the shared values to avoid this.
  */
 uint32_t
-__wt_random(uint32_t *rnd)
+__wt_random(WT_RAND_STATE volatile * rnd_state)
 {
-	uint32_t w = M_W, z = M_Z;
+	WT_RAND_STATE rnd;
+	uint32_t w, z;
+
+	/*
+	 * Take a copy of the random state so we can ensure that the
+	 * calculation operates on the state consistently regardless of
+	 * concurrent calls with the same random state.
+	 */
+	rnd = *rnd_state;
+	w = M_W(rnd);
+	z = M_Z(rnd);
+
+	/*
+	 * Check if the value goes to 0 (from which we won't recover), and reset
+	 * to the initial state. 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_state);
+
+	M_Z(rnd) = z = 36969 * (z & 65535) + (z >> 16);
+	M_W(rnd) = w = 18000 * (w & 65535) + (w >> 16);
+	*rnd_state = rnd;
 
-	M_Z = z = 36969 * (z & 65535) + (z >> 16);
-	M_W = w = 18000 * (w & 65535) + (w >> 16);
-	return (z << 16) + (w & 65535);
+	return ((z << 16) + (w & 65535));
 }
diff --git a/test/checkpoint/workers.c b/test/checkpoint/workers.c
index 393532f8e22..5cd2ef4e97b 100644
--- a/test/checkpoint/workers.c
+++ b/test/checkpoint/workers.c
@@ -172,13 +172,13 @@ real_worker(void)
 {
 	WT_CURSOR **cursors;
 	WT_SESSION *session;
-	uint32_t rnd[2];
+	WT_RAND_STATE rnd;
 	u_int i, keyno;
 	int j, ret, t_ret;
 
 	ret = t_ret = 0;
 
-	__wt_random_init(rnd);
+	__wt_random_init(&rnd);
 
 	if ((cursors = calloc(
 	    (size_t)(g.ntables), sizeof(WT_CURSOR *))) == NULL)
@@ -203,7 +203,7 @@ real_worker(void)
 			    "real_worker:begin_transaction", ret, 1);
 			goto err;
 		}
-		keyno = __wt_random(rnd) % g.nkeys + 1;
+		keyno = __wt_random(&rnd) % g.nkeys + 1;
 		for (j = 0; j < g.ntables; j++) {
 			if ((ret = worker_op(cursors[j], keyno, i)) != 0)
 				break;
diff --git a/test/format/format.h b/test/format/format.h
index f6e7a83470e..a72ad6fc66e 100644
--- a/test/format/format.h
+++ b/test/format/format.h
@@ -159,6 +159,8 @@ typedef struct {
 
 	pthread_rwlock_t backup_lock;		/* Hot backup running */
 
+	WT_RAND_STATE rnd;			/* Global RNG state */
+
 	/*
 	 * We have a list of records that are appended, but not yet "resolved",
 	 * that is, we haven't yet incremented the g.rows value to reflect the
@@ -262,6 +264,8 @@ typedef struct {
 extern GLOBAL g;
 
 typedef struct {
+	WT_RAND_STATE rnd;			/* thread RNG state */
+
 	uint64_t search;			/* operations */
 	uint64_t insert;
 	uint64_t update;
@@ -299,15 +303,18 @@ void	 config_file(const char *);
 void	 config_print(int);
 void	 config_setup(void);
 void	 config_single(const char *, int);
+void	 fclose_and_clear(FILE **);
+void	 key_gen(uint8_t *, size_t *, uint64_t);
+void	 key_gen_insert(WT_RAND_STATE *, uint8_t *, size_t *, uint64_t);
+void	 key_gen_setup(uint8_t **);
 void	 key_len_setup(void);
 void	 key_gen_setup(uint8_t **);
 void	 key_gen(uint8_t *, size_t *, uint64_t, int);
 void	 path_setup(const char *);
-uint32_t rng(void);
-void	 rng_init(void);
+uint32_t rng(WT_RAND_STATE *);
 void	 track(const char *, uint64_t, TINFO *);
-void	 val_gen_setup(uint8_t **);
-void	 value_gen(uint8_t *, size_t *, uint64_t);
+void	 val_gen(WT_RAND_STATE *, uint8_t *, size_t *, uint64_t);
+void	 val_gen_setup(WT_RAND_STATE *, uint8_t **);
 void	 wts_close(void);
 void	 wts_create(void);
 void	 wts_dump(const char *, int);
@@ -324,3 +331,13 @@ void	 die(int, const char *, ...)
 __attribute__((__noreturn__))
 #endif
 ;
+
+/*
+ * mmrand --
+ *	Return a random value between a min/max pair.
+ */
+static inline uint32_t
+mmrand(WT_RAND_STATE *rnd, u_int min, u_int max)
+{
+	return (rng(rnd) % (((max) + 1) - (min)) + (min));
+}
diff --git a/test/format/ops.c b/test/format/ops.c
index 5fd992e9952..84ed02a8750 100644
--- a/test/format/ops.c
+++ b/test/format/ops.c
@@ -191,7 +191,7 @@ wts_ops(int lastrun)
  *	Return the current session configuration.
  */
 static const char *
-ops_session_config(void)
+ops_session_config(WT_RAND_STATE *rnd)
 {
 	u_int v;
 
diff --git a/test/format/util.c b/test/format/util.c
index 186105ae30b..d9bbdbe330f 100644
--- a/test/format/util.c
+++ b/test/format/util.c
@@ -33,7 +33,7 @@
 #endif
 
 static inline uint32_t
-kv_len(uint64_t keyno, uint32_t min, uint32_t max)
+kv_len(WT_RAND_STATE *rnd, uint64_t keyno, uint32_t min, uint32_t max)
 {
 	/*
 	 * Focus on relatively small key/value items, admitting the possibility
@@ -110,10 +110,22 @@ key_gen(uint8_t *key, size_t *sizep, uint64_t keyno, int insert)
 	*sizep = (size_t)len;
 }
 
+void
+key_gen(uint8_t *key, size_t *sizep, uint64_t keyno)
+{
+	key_gen_common(key, sizep, keyno, 0);
+}
+
+void
+key_gen_insert(WT_RAND_STATE *rnd, uint8_t *key, size_t *sizep, uint64_t keyno)
+{
+	key_gen_common(key, sizep, keyno, (int)mmrand(rnd, 1, 15));
+}
+
 static uint32_t val_dup_data_len;	/* Length of duplicate data items */
 
 void
-val_gen_setup(uint8_t **valp)
+val_gen_setup(WT_RAND_STATE *rnd, uint8_t **valp)
 {
 	uint8_t *val;
 	size_t i, len;
@@ -140,7 +152,7 @@ val_gen_setup(uint8_t **valp)
 }
 
 void
-value_gen(uint8_t *val, size_t *sizep, uint64_t keyno)
+val_gen(WT_RAND_STATE *rnd, uint8_t *val, size_t *sizep, uint64_t keyno)
 {
 	/*
 	 * Fixed-length records: take the low N bits from the last digit of
@@ -350,7 +362,7 @@ path_setup(const char *home)
  *	Return a random number.
  */
 uint32_t
-rng(void)
+rng(WT_RAND_STATE *rnd)
 {
 	char buf[64];
 	uint32_t r;
diff --git a/test/thread/rw.c b/test/thread/rw.c
index 08cf63f435a..833e514cf0b 100644
--- a/test/thread/rw.c
+++ b/test/thread/rw.c
@@ -34,6 +34,9 @@ static void *writer(void *);
 
 typedef struct {
 	char *name;				/* object name */
+	u_int nops;				/* Thread op count */
+
+	WT_RAND_STATE rnd;			/* RNG */
 
 	int remove;				/* cursor.remove */
 	int update;				/* cursor.update */