Tarantool development patches archive
 help / color / mirror / Atom feed
* [Tarantool-patches] [PATCH v4] core: introduce evenly distributed int64 random in range
@ 2020-11-05 12:09 Ilya Kosarev
  2020-11-11 22:07 ` Vladislav Shpilevoy
  0 siblings, 1 reply; 5+ messages in thread
From: Ilya Kosarev @ 2020-11-05 12:09 UTC (permalink / raw)
  To: v.shpilevoy; +Cc: tarantool-patches

Tarantool codebase had at least two functions to generate random
integer in given range and both of them had problems at least with
integer overflow. This patch brings nice functions to generate random
int64_t in given range without overflow while preserving uniform random
generator distribution using unbiased bitmask with rejection method.
It is now possible to use xoshiro256++ PRNG or random bytes as a basis.
Most relevant replacements have been made. Needed tests are introduced.

Closes #5075
---
Branch: https://github.com/tarantool/tarantool/tree/i.kosarev/gh-5075-fine-random-in-range
Issue: https://github.com/tarantool/tarantool/issues/5075

Changes in v2:
 - implemented fine 64-bit random
 - implemented fine range bounding

Changes in v3:
 - added tests
 - fixed some hardcoded sizes
 - fixed potential compilations issues, leading to compilation fail or low performance
 - style fixed
 - added needed comments

 Changes in v4:
 - added more tests
 - style fixes
 - made xoshiro state print more safe

 src/lib/core/CMakeLists.txt |  2 +-
 src/lib/core/random.c       | 85 +++++++++++++++++++++++++++++++++++++
 src/lib/core/random.h       | 43 +++++++++++++++++++
 src/lib/swim/swim.c         | 26 ++----------
 test/unit/CMakeLists.txt    |  2 +
 test/unit/histogram.c       | 12 ++----
 test/unit/random.c          | 56 ++++++++++++++++++++++++
 test/unit/random.result     | 12 ++++++
 test/unit/swim_test_utils.c |  3 +-
 9 files changed, 208 insertions(+), 33 deletions(-)
 create mode 100644 test/unit/random.c
 create mode 100644 test/unit/random.result

diff --git a/src/lib/core/CMakeLists.txt b/src/lib/core/CMakeLists.txt
index 13ed1e7ab..7c62fc5ce 100644
--- a/src/lib/core/CMakeLists.txt
+++ b/src/lib/core/CMakeLists.txt
@@ -39,7 +39,7 @@ endif()
 
 add_library(core STATIC ${core_sources})
 
-target_link_libraries(core salad small uri decNumber ${LIBEV_LIBRARIES}
+target_link_libraries(core salad small uri decNumber bit ${LIBEV_LIBRARIES}
                       ${LIBEIO_LIBRARIES} ${LIBCORO_LIBRARIES}
                       ${MSGPUCK_LIBRARIES} ${ICU_LIBRARIES})
 
diff --git a/src/lib/core/random.c b/src/lib/core/random.c
index f4fa75b1c..3e6810d3c 100644
--- a/src/lib/core/random.c
+++ b/src/lib/core/random.c
@@ -35,10 +35,14 @@
 #include <sys/time.h>
 #include <unistd.h>
 #include <stdlib.h>
+#include "bit/bit.h"
 #include "say.h"
+#include "tt_static.h"
 
 static int rfd;
 
+static uint64_t state[4];
+
 void
 random_init(void)
 {
@@ -63,6 +67,8 @@ random_init(void)
 srand:
 	srandom(seed);
 	srand(seed);
+
+	random_bytes((char *)state, sizeof(state));
 }
 
 void
@@ -97,3 +103,82 @@ rand:
 	while (generated < size)
 		buf[generated++] = rand();
 }
+
+uint64_t
+real_random(void)
+{
+	uint64_t result;
+	random_bytes((char *)&result, sizeof(result));
+	return result;
+}
+
+/**
+ * Helper function for the xoshiro256++ pseudo random generator:
+ * rotate left.
+ */
+static inline uint64_t
+rotl(uint64_t x, int k)
+{
+	return (x << k) | (x >> (64 - k));
+}
+
+/**
+ * xoshiro256++ pseudo random generator.
+ * http://prng.di.unimi.it/
+ * State is initialized with random_bytes().
+ *
+ * It is fast and doesn’t fail any known statistical test.
+ * About 2 times faster than conventional LCG rand() and
+ * mersenne-twister algorithms. Also both of them do fail
+ * some statistical tests.
+ * Here are some other reasons to choose xoshiro over
+ * mersenne-twister: https://arxiv.org/pdf/1910.06437.pdf
+ */
+uint64_t
+xoshiro_random(void)
+{
+	const uint64_t result = rotl(state[0] + state[3], 23) + state[0];
+	const uint64_t t = state[1] << 17;
+	state[2] ^= state[0];
+	state[3] ^= state[1];
+	state[1] ^= state[2];
+	state[0] ^= state[3];
+	state[2] ^= t;
+	state[3] = rotl(state[3], 45);
+	return result;
+}
+
+const char *
+xoshiro_state_str(void)
+{
+	return tt_sprintf("%llu %llu %llu %llu", (unsigned long long)state[0],
+						 (unsigned long long)state[1],
+						 (unsigned long long)state[2],
+						 (unsigned long long)state[3]);
+}
+
+int64_t
+real_random_in_range(int64_t min, int64_t max)
+{
+	assert(max >= min);
+	uint64_t range = (uint64_t)max - min;
+	uint64_t mask = UINT64_MAX >> bit_clz_u64(range | 1);
+	uint64_t result;
+	do {
+		result = real_random() & mask;
+	} while (result > range);
+	return min + result;
+}
+
+int64_t
+pseudo_random_in_range(int64_t min, int64_t max)
+{
+	assert(max >= min);
+	uint64_t range = (uint64_t)max - min;
+	uint64_t mask = UINT64_MAX >> bit_clz_u64(range | 1);
+	uint64_t result;
+	do {
+		result = xoshiro_random() & mask;
+	} while (result > range);
+	return min + result;
+}
diff --git a/src/lib/core/random.h b/src/lib/core/random.h
index 26109b14b..9108eab58 100644
--- a/src/lib/core/random.h
+++ b/src/lib/core/random.h
@@ -32,6 +32,7 @@
  */
 
 #include <stddef.h>
+#include <stdint.h>
 
 #if defined(__cplusplus)
 extern "C" {
@@ -45,6 +46,48 @@ random_free(void);
 void
 random_bytes(char *buf, size_t size);
 
+/**
+ * Just 8 random_bytes().
+ */
+uint64_t
+real_random(void);
+
+/**
+ * xoshiro256++ pseudo random generator.
+ * http://prng.di.unimi.it/
+ * State is initialized with random_bytes().
+ */
+uint64_t
+xoshiro_random(void);
+
+const char *
+xoshiro_state_str(void);
+
+/**
+ * Return a random int64_t number within given boundaries,
+ * including both.
+ *
+ * Instead of blindly calculating a modulo, this function uses
+ * unbiased bitmask with rejection method to provide number in
+ * given boundaries while preserving uniform distribution and
+ * avoiding overflow. It uses random bytes as a basis.
+ */
+int64_t
+real_random_in_range(int64_t min, int64_t max);
+
+/**
+ * Return a pseudo random int64_t number within given boundaries,
+ * including both.
+ *
+ * Instead of blindly calculating a modulo, this function uses
+ * unbiased bitmask with rejection method to provide number in
+ * given boundaries while preserving uniform distribution and
+ * avoiding overflow. It uses xoshiro256++ as an uint64 pseudo
+ * random generator.
+ */
+int64_t
+pseudo_random_in_range(int64_t min, int64_t max);
+
 #if defined(__cplusplus)
 }
 #endif /* extern "C" */
diff --git a/src/lib/swim/swim.c b/src/lib/swim/swim.c
index 396bd7c45..9b5458635 100644
--- a/src/lib/swim/swim.c
+++ b/src/lib/swim/swim.c
@@ -34,6 +34,7 @@
 #include "swim_ev.h"
 #include "uri/uri.h"
 #include "fiber.h"
+#include "random.h"
 #include "msgpuck.h"
 #include "assoc.h"
 #include "sio.h"
@@ -188,25 +189,6 @@ enum {
 	INDIRECT_PING_COUNT = 2,
 };
 
-/**
- * Return a random number within given boundaries.
- *
- * Instead of blindly calculating a modulo, scale the random
- * number down the given boundaries to preserve the original
- * distribution. The result belongs to range [start, end].
- */
-static inline int
-swim_scaled_rand(int start, int end)
-{
-	assert(end >= start);
-	/*
-	 * RAND_MAX is likely to be INT_MAX - hardly SWIM will
-	 * ever be used in such a huge cluster.
-	 */
-	assert(end - start < RAND_MAX);
-	return rand() / (RAND_MAX / (end - start + 1) + 1);
-}
-
 /** Calculate UUID hash to use as a member table key. */
 static inline uint32_t
 swim_uuid_hash(const struct tt_uuid *uuid)
@@ -980,7 +962,7 @@ swim_shuffle_members(struct swim *swim)
 	for (mh_int_t node = mh_first(members), end = mh_end(members);
 	     node != end; node = mh_next(members, node), ++i) {
 		swim->shuffled[i] = *mh_swim_table_node(members, node);
-		int j = swim_scaled_rand(0, i);
+		int j = pseudo_random_in_range(0, i);
 		SWAP(swim->shuffled[i], swim->shuffled[j]);
 	}
 }
@@ -1069,7 +1051,7 @@ swim_encode_anti_entropy(struct swim *swim, struct swim_packet *packet)
 	swim_member_payload_bin_create(&payload_header);
 	struct mh_swim_table_t *t = swim->members;
 	int i = 0, member_count = mh_size(t);
-	int rnd = swim_scaled_rand(0, member_count - 1);
+	int rnd = pseudo_random_in_range(0, member_count - 1);
 	for (mh_int_t rc = mh_swim_table_random(t, rnd), end = mh_end(t);
 	     i < member_count; ++i) {
 		struct swim_member *m = *mh_swim_table_node(t, rc);
@@ -1380,7 +1362,7 @@ swim_send_indirect_pings(struct swim *swim, const struct swim_member *dst)
 {
 	struct mh_swim_table_t *t = swim->members;
 	int member_count = mh_size(t);
-	int rnd = swim_scaled_rand(0, member_count - 1);
+	int rnd = pseudo_random_in_range(0, member_count - 1);
 	mh_int_t rc = mh_swim_table_random(t, rnd), end = mh_end(t);
 	for (int member_i = 0, task_i = 0; member_i < member_count &&
 	     task_i < INDIRECT_PING_COUNT; ++member_i) {
diff --git a/test/unit/CMakeLists.txt b/test/unit/CMakeLists.txt
index 419477748..4be9271c6 100644
--- a/test/unit/CMakeLists.txt
+++ b/test/unit/CMakeLists.txt
@@ -52,6 +52,8 @@ add_executable(base64.test base64.c)
 target_link_libraries(base64.test misc unit)
 add_executable(uuid.test uuid.c)
 target_link_libraries(uuid.test uuid unit)
+add_executable(random.test random.c)
+target_link_libraries(random.test core unit)
 
 add_executable(bps_tree.test bps_tree.cc)
 target_link_libraries(bps_tree.test small misc)
diff --git a/test/unit/histogram.c b/test/unit/histogram.c
index 3056d20fe..ef5cd714f 100644
--- a/test/unit/histogram.c
+++ b/test/unit/histogram.c
@@ -5,6 +5,7 @@
 #include "memory.h"
 #include "unit.h"
 #include "trivia/util.h"
+#include "core/random.h"
 
 static int
 int64_cmp(const void *p1, const void *p2)
@@ -46,13 +47,6 @@ gen_rand_data(size_t *p_len)
 	return data;
 }
 
-static int64_t
-gen_rand_value(int64_t min, int64_t max)
-{
-	assert(max >= min);
-	return min + rand() % (max - min + 1);
-}
-
 static void
 test_counts(void)
 {
@@ -97,7 +91,7 @@ test_discard(void)
 
 	struct histogram *hist = histogram_new(buckets, n_buckets);
 
-	size_t bucket_sz = gen_rand_value(2, 10);
+	size_t bucket_sz = pseudo_random_in_range(2, 10);
 	size_t data_len = (n_buckets + 1) * bucket_sz;
 	int64_t *data = calloc(data_len, sizeof(*data));
 
@@ -105,7 +99,7 @@ test_discard(void)
 		int64_t min = (b == 0 ? INT64_MIN : buckets[b - 1] + 1);
 		int64_t max = (b == n_buckets ? INT64_MAX : buckets[b]);
 		for (size_t i = 0; i < bucket_sz; i++)
-			data[b * bucket_sz + i] = gen_rand_value(min, max);
+			data[b * bucket_sz + i] = pseudo_random_in_range(min, max);
 	}
 
 	for (size_t i = 0; i < data_len; i++)
diff --git a/test/unit/random.c b/test/unit/random.c
new file mode 100644
index 000000000..858ff7867
--- /dev/null
+++ b/test/unit/random.c
@@ -0,0 +1,56 @@
+#include <core/random.h>
+
+#include <stdio.h>
+#include <assert.h>
+
+#include "unit.h"
+
+static void
+test_random_in_range_one(int64_t min, int64_t max)
+{
+	int64_t result = pseudo_random_in_range(min, max);
+	assert(min <= result && result <= max);
+	if (min == max)
+		printf("pseudo_random_in_range(%lld, %lld) = %lld\n",
+		       (long long)min, (long long)max, (long long)result);
+
+	result = real_random_in_range(min, max);
+	assert(min <= result && result <= max);
+	if (min == max)
+		printf("real_random_in_range(%lld, %lld) = %lld\n",
+		      (long long)min, (long long)max, (long long)result);
+}
+
+static void
+test_random_in_range(void)
+{
+	header();
+
+	test_random_in_range_one(INT64_MIN, INT64_MAX);
+	test_random_in_range_one(INT64_MIN, INT64_MIN);
+	test_random_in_range_one(INT64_MAX, INT64_MAX);
+	test_random_in_range_one(-1, -1);
+	test_random_in_range_one(0, 0);
+	test_random_in_range_one(1, 1);
+
+	test_random_in_range_one(INT64_MIN + 1, INT64_MAX - 1);
+	test_random_in_range_one(INT64_MIN / 2, INT64_MAX / 2);
+	test_random_in_range_one(INT64_MIN, INT64_MIN / 2);
+	test_random_in_range_one(INT64_MAX / 2, INT64_MAX);
+	test_random_in_range_one(-2, -1);
+	test_random_in_range_one(1, 2);
+	test_random_in_range_one(-1, 1);
+	test_random_in_range_one(0, 1);
+
+	footer();
+}
+
+int
+main(void)
+{
+	random_init();
+
+	test_random_in_range();
+
+	random_free();
+}
diff --git a/test/unit/random.result b/test/unit/random.result
new file mode 100644
index 000000000..faa898e01
--- /dev/null
+++ b/test/unit/random.result
@@ -0,0 +1,12 @@
+	*** test_random_in_range ***
+pseudo_random_in_range(-9223372036854775808, -9223372036854775808) = -9223372036854775808
+real_random_in_range(-9223372036854775808, -9223372036854775808) = -9223372036854775808
+pseudo_random_in_range(9223372036854775807, 9223372036854775807) = 9223372036854775807
+real_random_in_range(9223372036854775807, 9223372036854775807) = 9223372036854775807
+pseudo_random_in_range(-1, -1) = -1
+real_random_in_range(-1, -1) = -1
+pseudo_random_in_range(0, 0) = 0
+real_random_in_range(0, 0) = 0
+pseudo_random_in_range(1, 1) = 1
+real_random_in_range(1, 1) = 1
+	*** test_random_in_range: done ***
diff --git a/test/unit/swim_test_utils.c b/test/unit/swim_test_utils.c
index 9dbd28a9f..7ac43d82d 100644
--- a/test/unit/swim_test_utils.c
+++ b/test/unit/swim_test_utils.c
@@ -875,7 +875,8 @@ swim_run_test(const char *log_file, fiber_func test)
 	 * Print the seed to be able to reproduce a bug with the
 	 * same seed.
 	 */
-	say_info("Random seed = %llu", (unsigned long long) seed);
+	say_info("Random seed = %llu", (unsigned long long)seed);
+	say_info("xoshiro random state = %s", xoshiro_state_str());
 
 	struct fiber *main_fiber = fiber_new("main", test);
 	fiber_set_joinable(main_fiber, true);
-- 
2.17.1

^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [Tarantool-patches] [PATCH v4] core: introduce evenly distributed int64 random in range
  2020-11-05 12:09 [Tarantool-patches] [PATCH v4] core: introduce evenly distributed int64 random in range Ilya Kosarev
@ 2020-11-11 22:07 ` Vladislav Shpilevoy
  2020-11-13 11:54   ` Ilya Kosarev
  0 siblings, 1 reply; 5+ messages in thread
From: Vladislav Shpilevoy @ 2020-11-11 22:07 UTC (permalink / raw)
  To: Ilya Kosarev; +Cc: tarantool-patches

Hi! Thanks for the fixes!

I hope we will end this eventually :)

See 2 comments below.

> diff --git a/test/unit/random.c b/test/unit/random.c
> new file mode 100644
> index 000000000..858ff7867
> --- /dev/null
> +++ b/test/unit/random.c
> @@ -0,0 +1,56 @@
> +#include <core/random.h>
> +
> +#include <stdio.h>
> +#include <assert.h>
> +
> +#include "unit.h"
> +
> +static void
> +test_random_in_range_one(int64_t min, int64_t max)
> +{
> +	int64_t result = pseudo_random_in_range(min, max);
> +	assert(min <= result && result <= max);
> +	if (min == max)
> +		printf("pseudo_random_in_range(%lld, %lld) = %lld\n",
> +		       (long long)min, (long long)max, (long long)result);
> +
> +	result = real_random_in_range(min, max);
> +	assert(min <= result && result <= max);
> +	if (min == max)
> +		printf("real_random_in_range(%lld, %lld) = %lld\n",
> +		      (long long)min, (long long)max, (long long)result);

1. By using printf as a checker you complicate Sergey's life in scope
of this https://github.com/tarantool/tarantool/issues/5000. Because your
output is not TAP. Better not print anything except via helpers from
unit.h, and use ok()/is()/isnt() for actual tests.

> +}
> diff --git a/test/unit/swim_test_utils.c b/test/unit/swim_test_utils.c
> index 9dbd28a9f..7ac43d82d 100644
> --- a/test/unit/swim_test_utils.c
> +++ b/test/unit/swim_test_utils.c
> @@ -875,7 +875,8 @@ swim_run_test(const char *log_file, fiber_func test)
>  	 * Print the seed to be able to reproduce a bug with the
>  	 * same seed.
>  	 */
> -	say_info("Random seed = %llu", (unsigned long long) seed);
> +	say_info("Random seed = %llu", (unsigned long long)seed);

2. Why did you change this line?

^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [Tarantool-patches] [PATCH v4] core: introduce evenly distributed int64 random in range
  2020-11-11 22:07 ` Vladislav Shpilevoy
@ 2020-11-13 11:54   ` Ilya Kosarev
  0 siblings, 0 replies; 5+ messages in thread
From: Ilya Kosarev @ 2020-11-13 11:54 UTC (permalink / raw)
  To: Vladislav Shpilevoy; +Cc: tarantool-patches

[-- Attachment #1: Type: text/plain, Size: 1949 bytes --]


Hi!

Sent v5 of the patch with fixes. 
>Четверг, 12 ноября 2020, 1:07 +03:00 от Vladislav Shpilevoy <v.shpilevoy@tarantool.org>:
> 
>Hi! Thanks for the fixes!
>
>I hope we will end this eventually :)
>
>See 2 comments below.
>
>> diff --git a/test/unit/random.c b/test/unit/random.c
>> new file mode 100644
>> index 000000000..858ff7867
>> --- /dev/null
>> +++ b/test/unit/random.c
>> @@ -0,0 +1,56 @@
>> +#include <core/random.h>
>> +
>> +#include <stdio.h>
>> +#include <assert.h>
>> +
>> +#include "unit.h"
>> +
>> +static void
>> +test_random_in_range_one(int64_t min, int64_t max)
>> +{
>> + int64_t result = pseudo_random_in_range(min, max);
>> + assert(min <= result && result <= max);
>> + if (min == max)
>> + printf("pseudo_random_in_range(%lld, %lld) = %lld\n",
>> + (long long)min, (long long)max, (long long)result);
>> +
>> + result = real_random_in_range(min, max);
>> + assert(min <= result && result <= max);
>> + if (min == max)
>> + printf("real_random_in_range(%lld, %lld) = %lld\n",
>> + (long long)min, (long long)max, (long long)result);
>
>1. By using printf as a checker you complicate Sergey's life in scope
>of this  https://github.com/tarantool/tarantool/issues/5000 . Because your
>output is not TAP. Better not print anything except via helpers from
>unit.h, and use ok()/is()/isnt() for actual tests.
Thanks, didn’t really know this one.
>
>> +}
>> diff --git a/test/unit/swim_test_utils.c b/test/unit/swim_test_utils.c
>> index 9dbd28a9f..7ac43d82d 100644
>> --- a/test/unit/swim_test_utils.c
>> +++ b/test/unit/swim_test_utils.c
>> @@ -875,7 +875,8 @@ swim_run_test(const char *log_file, fiber_func test)
>> * Print the seed to be able to reproduce a bug with the
>> * same seed.
>> */
>> - say_info("Random seed = %llu", (unsigned long long) seed);
>> + say_info("Random seed = %llu", (unsigned long long)seed);
>
>2. Why did you change this line? 
Yes, no need to change it
 
--
Ilya Kosarev
 

[-- Attachment #2: Type: text/html, Size: 2876 bytes --]

^ permalink raw reply	[flat|nested] 5+ messages in thread

* [Tarantool-patches] [PATCH v4] core: introduce evenly distributed int64 random in range
@ 2020-11-05 11:14 Ilya Kosarev
  0 siblings, 0 replies; 5+ messages in thread
From: Ilya Kosarev @ 2020-11-05 11:14 UTC (permalink / raw)
  To: v.shpilevoy; +Cc: tarantool-patches

Tarantool codebase had at least two functions to generate random
integer in given range and both of them had problems at least with
integer overflow. This patch brings nice functions to generate random
int64_t in given range without overflow while preserving uniform random
generator distribution using unbiased bitmask with rejection method.
It is now possible to use xoshiro256++ PRNG or random bytes as a basis.
Most relevant replacements have been made. Needed tests are introduced.

Closes #5075
---
Branch: https://github.com/tarantool/tarantool/tree/i.kosarev/gh-5075-fine-random-in-range
Issue: https://github.com/tarantool/tarantool/issues/5075

Changes in v2:
 - implemented fine 64-bit random
 - implemented fine range bounding

Changes in v3:
 - added tests
 - fixed some hardcoded sizes
 - fixed potential compilations issues, leading to compilation fail or low performance
 - style fixed
 - added needed comments

 Changes in v4:
  - added more tests
  - style fixes
  - made xoshiro state print more safe

 src/lib/core/CMakeLists.txt |  2 +-
 src/lib/core/random.c       | 85 +++++++++++++++++++++++++++++++++++++
 src/lib/core/random.h       | 43 +++++++++++++++++++
 src/lib/swim/swim.c         | 26 ++----------
 test/unit/CMakeLists.txt    |  2 +
 test/unit/histogram.c       | 12 ++----
 test/unit/random.c          | 56 ++++++++++++++++++++++++
 test/unit/random.result     | 12 ++++++
 test/unit/swim_test_utils.c |  3 +-
 9 files changed, 208 insertions(+), 33 deletions(-)
 create mode 100644 test/unit/random.c
 create mode 100644 test/unit/random.result

diff --git a/src/lib/core/CMakeLists.txt b/src/lib/core/CMakeLists.txt
index 13ed1e7ab..7c62fc5ce 100644
--- a/src/lib/core/CMakeLists.txt
+++ b/src/lib/core/CMakeLists.txt
@@ -39,7 +39,7 @@ endif()
 
 add_library(core STATIC ${core_sources})
 
-target_link_libraries(core salad small uri decNumber ${LIBEV_LIBRARIES}
+target_link_libraries(core salad small uri decNumber bit ${LIBEV_LIBRARIES}
                       ${LIBEIO_LIBRARIES} ${LIBCORO_LIBRARIES}
                       ${MSGPUCK_LIBRARIES} ${ICU_LIBRARIES})
 
diff --git a/src/lib/core/random.c b/src/lib/core/random.c
index f4fa75b1c..3e6810d3c 100644
--- a/src/lib/core/random.c
+++ b/src/lib/core/random.c
@@ -35,10 +35,14 @@
 #include <sys/time.h>
 #include <unistd.h>
 #include <stdlib.h>
+#include "bit/bit.h"
 #include "say.h"
+#include "tt_static.h"
 
 static int rfd;
 
+static uint64_t state[4];
+
 void
 random_init(void)
 {
@@ -63,6 +67,8 @@ random_init(void)
 srand:
 	srandom(seed);
 	srand(seed);
+
+	random_bytes((char *)state, sizeof(state));
 }
 
 void
@@ -97,3 +103,82 @@ rand:
 	while (generated < size)
 		buf[generated++] = rand();
 }
+
+uint64_t
+real_random(void)
+{
+	uint64_t result;
+	random_bytes((char *)&result, sizeof(result));
+	return result;
+}
+
+/**
+ * Helper function for the xoshiro256++ pseudo random generator:
+ * rotate left.
+ */
+static inline uint64_t
+rotl(uint64_t x, int k)
+{
+	return (x << k) | (x >> (64 - k));
+}
+
+/**
+ * xoshiro256++ pseudo random generator.
+ * http://prng.di.unimi.it/
+ * State is initialized with random_bytes().
+ *
+ * It is fast and doesn’t fail any known statistical test.
+ * About 2 times faster than conventional LCG rand() and
+ * mersenne-twister algorithms. Also both of them do fail
+ * some statistical tests.
+ * Here are some other reasons to choose xoshiro over
+ * mersenne-twister: https://arxiv.org/pdf/1910.06437.pdf
+ */
+uint64_t
+xoshiro_random(void)
+{
+	const uint64_t result = rotl(state[0] + state[3], 23) + state[0];
+	const uint64_t t = state[1] << 17;
+	state[2] ^= state[0];
+	state[3] ^= state[1];
+	state[1] ^= state[2];
+	state[0] ^= state[3];
+	state[2] ^= t;
+	state[3] = rotl(state[3], 45);
+	return result;
+}
+
+const char *
+xoshiro_state_str(void)
+{
+	return tt_sprintf("%llu %llu %llu %llu", (unsigned long long)state[0],
+						 (unsigned long long)state[1],
+						 (unsigned long long)state[2],
+						 (unsigned long long)state[3]);
+}
+
+int64_t
+real_random_in_range(int64_t min, int64_t max)
+{
+	assert(max >= min);
+	uint64_t range = (uint64_t)max - min;
+	uint64_t mask = UINT64_MAX >> bit_clz_u64(range | 1);
+	uint64_t result;
+	do {
+		result = real_random() & mask;
+	} while (result > range);
+	return min + result;
+}
+
+int64_t
+pseudo_random_in_range(int64_t min, int64_t max)
+{
+	assert(max >= min);
+	uint64_t range = (uint64_t)max - min;
+	uint64_t mask = UINT64_MAX >> bit_clz_u64(range | 1);
+	uint64_t result;
+	do {
+		result = xoshiro_random() & mask;
+	} while (result > range);
+	return min + result;
+}
diff --git a/src/lib/core/random.h b/src/lib/core/random.h
index 26109b14b..9108eab58 100644
--- a/src/lib/core/random.h
+++ b/src/lib/core/random.h
@@ -32,6 +32,7 @@
  */
 
 #include <stddef.h>
+#include <stdint.h>
 
 #if defined(__cplusplus)
 extern "C" {
@@ -45,6 +46,48 @@ random_free(void);
 void
 random_bytes(char *buf, size_t size);
 
+/**
+ * Just 8 random_bytes().
+ */
+uint64_t
+real_random(void);
+
+/**
+ * xoshiro256++ pseudo random generator.
+ * http://prng.di.unimi.it/
+ * State is initialized with random_bytes().
+ */
+uint64_t
+xoshiro_random(void);
+
+const char *
+xoshiro_state_str(void);
+
+/**
+ * Return a random int64_t number within given boundaries,
+ * including both.
+ *
+ * Instead of blindly calculating a modulo, this function uses
+ * unbiased bitmask with rejection method to provide number in
+ * given boundaries while preserving uniform distribution and
+ * avoiding overflow. It uses random bytes as a basis.
+ */
+int64_t
+real_random_in_range(int64_t min, int64_t max);
+
+/**
+ * Return a pseudo random int64_t number within given boundaries,
+ * including both.
+ *
+ * Instead of blindly calculating a modulo, this function uses
+ * unbiased bitmask with rejection method to provide number in
+ * given boundaries while preserving uniform distribution and
+ * avoiding overflow. It uses xoshiro256++ as an uint64 pseudo
+ * random generator.
+ */
+int64_t
+pseudo_random_in_range(int64_t min, int64_t max);
+
 #if defined(__cplusplus)
 }
 #endif /* extern "C" */
diff --git a/src/lib/swim/swim.c b/src/lib/swim/swim.c
index 396bd7c45..9b5458635 100644
--- a/src/lib/swim/swim.c
+++ b/src/lib/swim/swim.c
@@ -34,6 +34,7 @@
 #include "swim_ev.h"
 #include "uri/uri.h"
 #include "fiber.h"
+#include "random.h"
 #include "msgpuck.h"
 #include "assoc.h"
 #include "sio.h"
@@ -188,25 +189,6 @@ enum {
 	INDIRECT_PING_COUNT = 2,
 };
 
-/**
- * Return a random number within given boundaries.
- *
- * Instead of blindly calculating a modulo, scale the random
- * number down the given boundaries to preserve the original
- * distribution. The result belongs to range [start, end].
- */
-static inline int
-swim_scaled_rand(int start, int end)
-{
-	assert(end >= start);
-	/*
-	 * RAND_MAX is likely to be INT_MAX - hardly SWIM will
-	 * ever be used in such a huge cluster.
-	 */
-	assert(end - start < RAND_MAX);
-	return rand() / (RAND_MAX / (end - start + 1) + 1);
-}
-
 /** Calculate UUID hash to use as a member table key. */
 static inline uint32_t
 swim_uuid_hash(const struct tt_uuid *uuid)
@@ -980,7 +962,7 @@ swim_shuffle_members(struct swim *swim)
 	for (mh_int_t node = mh_first(members), end = mh_end(members);
 	     node != end; node = mh_next(members, node), ++i) {
 		swim->shuffled[i] = *mh_swim_table_node(members, node);
-		int j = swim_scaled_rand(0, i);
+		int j = pseudo_random_in_range(0, i);
 		SWAP(swim->shuffled[i], swim->shuffled[j]);
 	}
 }
@@ -1069,7 +1051,7 @@ swim_encode_anti_entropy(struct swim *swim, struct swim_packet *packet)
 	swim_member_payload_bin_create(&payload_header);
 	struct mh_swim_table_t *t = swim->members;
 	int i = 0, member_count = mh_size(t);
-	int rnd = swim_scaled_rand(0, member_count - 1);
+	int rnd = pseudo_random_in_range(0, member_count - 1);
 	for (mh_int_t rc = mh_swim_table_random(t, rnd), end = mh_end(t);
 	     i < member_count; ++i) {
 		struct swim_member *m = *mh_swim_table_node(t, rc);
@@ -1380,7 +1362,7 @@ swim_send_indirect_pings(struct swim *swim, const struct swim_member *dst)
 {
 	struct mh_swim_table_t *t = swim->members;
 	int member_count = mh_size(t);
-	int rnd = swim_scaled_rand(0, member_count - 1);
+	int rnd = pseudo_random_in_range(0, member_count - 1);
 	mh_int_t rc = mh_swim_table_random(t, rnd), end = mh_end(t);
 	for (int member_i = 0, task_i = 0; member_i < member_count &&
 	     task_i < INDIRECT_PING_COUNT; ++member_i) {
diff --git a/test/unit/CMakeLists.txt b/test/unit/CMakeLists.txt
index 419477748..4be9271c6 100644
--- a/test/unit/CMakeLists.txt
+++ b/test/unit/CMakeLists.txt
@@ -52,6 +52,8 @@ add_executable(base64.test base64.c)
 target_link_libraries(base64.test misc unit)
 add_executable(uuid.test uuid.c)
 target_link_libraries(uuid.test uuid unit)
+add_executable(random.test random.c)
+target_link_libraries(random.test core unit)
 
 add_executable(bps_tree.test bps_tree.cc)
 target_link_libraries(bps_tree.test small misc)
diff --git a/test/unit/histogram.c b/test/unit/histogram.c
index 3056d20fe..ef5cd714f 100644
--- a/test/unit/histogram.c
+++ b/test/unit/histogram.c
@@ -5,6 +5,7 @@
 #include "memory.h"
 #include "unit.h"
 #include "trivia/util.h"
+#include "core/random.h"
 
 static int
 int64_cmp(const void *p1, const void *p2)
@@ -46,13 +47,6 @@ gen_rand_data(size_t *p_len)
 	return data;
 }
 
-static int64_t
-gen_rand_value(int64_t min, int64_t max)
-{
-	assert(max >= min);
-	return min + rand() % (max - min + 1);
-}
-
 static void
 test_counts(void)
 {
@@ -97,7 +91,7 @@ test_discard(void)
 
 	struct histogram *hist = histogram_new(buckets, n_buckets);
 
-	size_t bucket_sz = gen_rand_value(2, 10);
+	size_t bucket_sz = pseudo_random_in_range(2, 10);
 	size_t data_len = (n_buckets + 1) * bucket_sz;
 	int64_t *data = calloc(data_len, sizeof(*data));
 
@@ -105,7 +99,7 @@ test_discard(void)
 		int64_t min = (b == 0 ? INT64_MIN : buckets[b - 1] + 1);
 		int64_t max = (b == n_buckets ? INT64_MAX : buckets[b]);
 		for (size_t i = 0; i < bucket_sz; i++)
-			data[b * bucket_sz + i] = gen_rand_value(min, max);
+			data[b * bucket_sz + i] = pseudo_random_in_range(min, max);
 	}
 
 	for (size_t i = 0; i < data_len; i++)
diff --git a/test/unit/random.c b/test/unit/random.c
new file mode 100644
index 000000000..858ff7867
--- /dev/null
+++ b/test/unit/random.c
@@ -0,0 +1,56 @@
+#include <core/random.h>
+
+#include <stdio.h>
+#include <assert.h>
+
+#include "unit.h"
+
+static void
+test_random_in_range_one(int64_t min, int64_t max)
+{
+	int64_t result = pseudo_random_in_range(min, max);
+	assert(min <= result && result <= max);
+	if (min == max)
+		printf("pseudo_random_in_range(%lld, %lld) = %lld\n",
+		       (long long)min, (long long)max, (long long)result);
+
+	result = real_random_in_range(min, max);
+	assert(min <= result && result <= max);
+	if (min == max)
+		printf("real_random_in_range(%lld, %lld) = %lld\n",
+		      (long long)min, (long long)max, (long long)result);
+}
+
+static void
+test_random_in_range(void)
+{
+	header();
+
+	test_random_in_range_one(INT64_MIN, INT64_MAX);
+	test_random_in_range_one(INT64_MIN, INT64_MIN);
+	test_random_in_range_one(INT64_MAX, INT64_MAX);
+	test_random_in_range_one(-1, -1);
+	test_random_in_range_one(0, 0);
+	test_random_in_range_one(1, 1);
+
+	test_random_in_range_one(INT64_MIN + 1, INT64_MAX - 1);
+	test_random_in_range_one(INT64_MIN / 2, INT64_MAX / 2);
+	test_random_in_range_one(INT64_MIN, INT64_MIN / 2);
+	test_random_in_range_one(INT64_MAX / 2, INT64_MAX);
+	test_random_in_range_one(-2, -1);
+	test_random_in_range_one(1, 2);
+	test_random_in_range_one(-1, 1);
+	test_random_in_range_one(0, 1);
+
+	footer();
+}
+
+int
+main(void)
+{
+	random_init();
+
+	test_random_in_range();
+
+	random_free();
+}
diff --git a/test/unit/random.result b/test/unit/random.result
new file mode 100644
index 000000000..3d19130bf
--- /dev/null
+++ b/test/unit/random.result
@@ -0,0 +1,12 @@
+	*** test_xoshiro_random_in_range ***
+pseudo_random_in_range(-9223372036854775808, -9223372036854775808) = -9223372036854775808
+real_random_in_range(-9223372036854775808, -9223372036854775808) = -9223372036854775808
+pseudo_random_in_range(9223372036854775807, 9223372036854775807) = 9223372036854775807
+real_random_in_range(9223372036854775807, 9223372036854775807) = 9223372036854775807
+pseudo_random_in_range(-1, -1) = -1
+real_random_in_range(-1, -1) = -1
+pseudo_random_in_range(0, 0) = 0
+real_random_in_range(0, 0) = 0
+pseudo_random_in_range(1, 1) = 1
+real_random_in_range(1, 1) = 1
+	*** test_xoshiro_random_in_range: done ***
diff --git a/test/unit/swim_test_utils.c b/test/unit/swim_test_utils.c
index 9dbd28a9f..7ac43d82d 100644
--- a/test/unit/swim_test_utils.c
+++ b/test/unit/swim_test_utils.c
@@ -875,7 +875,8 @@ swim_run_test(const char *log_file, fiber_func test)
 	 * Print the seed to be able to reproduce a bug with the
 	 * same seed.
 	 */
-	say_info("Random seed = %llu", (unsigned long long) seed);
+	say_info("Random seed = %llu", (unsigned long long)seed);
+	say_info("xoshiro random state = %s", xoshiro_state_str());
 
 	struct fiber *main_fiber = fiber_new("main", test);
 	fiber_set_joinable(main_fiber, true);
-- 
2.17.1

^ permalink raw reply	[flat|nested] 5+ messages in thread

* [Tarantool-patches] [PATCH v4] core: introduce evenly distributed int64 random in range
@ 2020-11-05 11:07 Ilya Kosarev
  0 siblings, 0 replies; 5+ messages in thread
From: Ilya Kosarev @ 2020-11-05 11:07 UTC (permalink / raw)
  To: v.shpilevoy; +Cc: tarantool-patches

Tarantool codebase had at least two functions to generate random
integer in given range and both of them had problems at least with
integer overflow. This patch brings nice functions to generate random
int64_t in given range without overflow while preserving uniform random
generator distribution using unbiased bitmask with rejection method.
It is now possible to use xoshiro256++ PRNG or random bytes as a basis.
Most relevant replacements have been made. Needed tests are introduced.

Closes #5075
---
Branch: https://github.com/tarantool/tarantool/tree/i.kosarev/gh-5075-fine-random-in-range
Issue: https://github.com/tarantool/tarantool/issues/5075

Changes in v2:
 - implemented fine 64-bit random
 - implemented fine range bounding

Changes in v3:
 - added tests
 - fixed some hardcoded sizes
 - fixed potential compilations issues, leading to compilation fail or low performance
 - style fixed
 - added needed comments

 Changes in v4:
  - added more tests
  - style fixes
  - made xoshiro state print more safe

 src/lib/core/CMakeLists.txt |  2 +-
 src/lib/core/random.c       | 85 +++++++++++++++++++++++++++++++++++++
 src/lib/core/random.h       | 43 +++++++++++++++++++
 src/lib/swim/swim.c         | 26 ++----------
 test/unit/CMakeLists.txt    |  2 +
 test/unit/histogram.c       | 12 ++----
 test/unit/random.c          | 56 ++++++++++++++++++++++++
 test/unit/random.result     | 12 ++++++
 test/unit/swim_test_utils.c |  3 +-
 9 files changed, 208 insertions(+), 33 deletions(-)
 create mode 100644 test/unit/random.c
 create mode 100644 test/unit/random.result

diff --git a/src/lib/core/CMakeLists.txt b/src/lib/core/CMakeLists.txt
index 13ed1e7ab..7c62fc5ce 100644
--- a/src/lib/core/CMakeLists.txt
+++ b/src/lib/core/CMakeLists.txt
@@ -39,7 +39,7 @@ endif()
 
 add_library(core STATIC ${core_sources})
 
-target_link_libraries(core salad small uri decNumber ${LIBEV_LIBRARIES}
+target_link_libraries(core salad small uri decNumber bit ${LIBEV_LIBRARIES}
                       ${LIBEIO_LIBRARIES} ${LIBCORO_LIBRARIES}
                       ${MSGPUCK_LIBRARIES} ${ICU_LIBRARIES})
 
diff --git a/src/lib/core/random.c b/src/lib/core/random.c
index f4fa75b1c..3e6810d3c 100644
--- a/src/lib/core/random.c
+++ b/src/lib/core/random.c
@@ -35,10 +35,14 @@
 #include <sys/time.h>
 #include <unistd.h>
 #include <stdlib.h>
+#include "bit/bit.h"
 #include "say.h"
+#include "tt_static.h"
 
 static int rfd;
 
+static uint64_t state[4];
+
 void
 random_init(void)
 {
@@ -63,6 +67,8 @@ random_init(void)
 srand:
 	srandom(seed);
 	srand(seed);
+
+	random_bytes((char *)state, sizeof(state));
 }
 
 void
@@ -97,3 +103,82 @@ rand:
 	while (generated < size)
 		buf[generated++] = rand();
 }
+
+uint64_t
+real_random(void)
+{
+	uint64_t result;
+	random_bytes((char *)&result, sizeof(result));
+	return result;
+}
+
+/**
+ * Helper function for the xoshiro256++ pseudo random generator:
+ * rotate left.
+ */
+static inline uint64_t
+rotl(uint64_t x, int k)
+{
+	return (x << k) | (x >> (64 - k));
+}
+
+/**
+ * xoshiro256++ pseudo random generator.
+ * http://prng.di.unimi.it/
+ * State is initialized with random_bytes().
+ *
+ * It is fast and doesn’t fail any known statistical test.
+ * About 2 times faster than conventional LCG rand() and
+ * mersenne-twister algorithms. Also both of them do fail
+ * some statistical tests.
+ * Here are some other reasons to choose xoshiro over
+ * mersenne-twister: https://arxiv.org/pdf/1910.06437.pdf
+ */
+uint64_t
+xoshiro_random(void)
+{
+	const uint64_t result = rotl(state[0] + state[3], 23) + state[0];
+	const uint64_t t = state[1] << 17;
+	state[2] ^= state[0];
+	state[3] ^= state[1];
+	state[1] ^= state[2];
+	state[0] ^= state[3];
+	state[2] ^= t;
+	state[3] = rotl(state[3], 45);
+	return result;
+}
+
+const char *
+xoshiro_state_str(void)
+{
+	return tt_sprintf("%llu %llu %llu %llu", (unsigned long long)state[0],
+						 (unsigned long long)state[1],
+						 (unsigned long long)state[2],
+						 (unsigned long long)state[3]);
+}
+
+int64_t
+real_random_in_range(int64_t min, int64_t max)
+{
+	assert(max >= min);
+	uint64_t range = (uint64_t)max - min;
+	uint64_t mask = UINT64_MAX >> bit_clz_u64(range | 1);
+	uint64_t result;
+	do {
+		result = real_random() & mask;
+	} while (result > range);
+	return min + result;
+}
+
+int64_t
+pseudo_random_in_range(int64_t min, int64_t max)
+{
+	assert(max >= min);
+	uint64_t range = (uint64_t)max - min;
+	uint64_t mask = UINT64_MAX >> bit_clz_u64(range | 1);
+	uint64_t result;
+	do {
+		result = xoshiro_random() & mask;
+	} while (result > range);
+	return min + result;
+}
diff --git a/src/lib/core/random.h b/src/lib/core/random.h
index 26109b14b..9108eab58 100644
--- a/src/lib/core/random.h
+++ b/src/lib/core/random.h
@@ -32,6 +32,7 @@
  */
 
 #include <stddef.h>
+#include <stdint.h>
 
 #if defined(__cplusplus)
 extern "C" {
@@ -45,6 +46,48 @@ random_free(void);
 void
 random_bytes(char *buf, size_t size);
 
+/**
+ * Just 8 random_bytes().
+ */
+uint64_t
+real_random(void);
+
+/**
+ * xoshiro256++ pseudo random generator.
+ * http://prng.di.unimi.it/
+ * State is initialized with random_bytes().
+ */
+uint64_t
+xoshiro_random(void);
+
+const char *
+xoshiro_state_str(void);
+
+/**
+ * Return a random int64_t number within given boundaries,
+ * including both.
+ *
+ * Instead of blindly calculating a modulo, this function uses
+ * unbiased bitmask with rejection method to provide number in
+ * given boundaries while preserving uniform distribution and
+ * avoiding overflow. It uses random bytes as a basis.
+ */
+int64_t
+real_random_in_range(int64_t min, int64_t max);
+
+/**
+ * Return a pseudo random int64_t number within given boundaries,
+ * including both.
+ *
+ * Instead of blindly calculating a modulo, this function uses
+ * unbiased bitmask with rejection method to provide number in
+ * given boundaries while preserving uniform distribution and
+ * avoiding overflow. It uses xoshiro256++ as an uint64 pseudo
+ * random generator.
+ */
+int64_t
+pseudo_random_in_range(int64_t min, int64_t max);
+
 #if defined(__cplusplus)
 }
 #endif /* extern "C" */
diff --git a/src/lib/swim/swim.c b/src/lib/swim/swim.c
index 396bd7c45..9b5458635 100644
--- a/src/lib/swim/swim.c
+++ b/src/lib/swim/swim.c
@@ -34,6 +34,7 @@
 #include "swim_ev.h"
 #include "uri/uri.h"
 #include "fiber.h"
+#include "random.h"
 #include "msgpuck.h"
 #include "assoc.h"
 #include "sio.h"
@@ -188,25 +189,6 @@ enum {
 	INDIRECT_PING_COUNT = 2,
 };
 
-/**
- * Return a random number within given boundaries.
- *
- * Instead of blindly calculating a modulo, scale the random
- * number down the given boundaries to preserve the original
- * distribution. The result belongs to range [start, end].
- */
-static inline int
-swim_scaled_rand(int start, int end)
-{
-	assert(end >= start);
-	/*
-	 * RAND_MAX is likely to be INT_MAX - hardly SWIM will
-	 * ever be used in such a huge cluster.
-	 */
-	assert(end - start < RAND_MAX);
-	return rand() / (RAND_MAX / (end - start + 1) + 1);
-}
-
 /** Calculate UUID hash to use as a member table key. */
 static inline uint32_t
 swim_uuid_hash(const struct tt_uuid *uuid)
@@ -980,7 +962,7 @@ swim_shuffle_members(struct swim *swim)
 	for (mh_int_t node = mh_first(members), end = mh_end(members);
 	     node != end; node = mh_next(members, node), ++i) {
 		swim->shuffled[i] = *mh_swim_table_node(members, node);
-		int j = swim_scaled_rand(0, i);
+		int j = pseudo_random_in_range(0, i);
 		SWAP(swim->shuffled[i], swim->shuffled[j]);
 	}
 }
@@ -1069,7 +1051,7 @@ swim_encode_anti_entropy(struct swim *swim, struct swim_packet *packet)
 	swim_member_payload_bin_create(&payload_header);
 	struct mh_swim_table_t *t = swim->members;
 	int i = 0, member_count = mh_size(t);
-	int rnd = swim_scaled_rand(0, member_count - 1);
+	int rnd = pseudo_random_in_range(0, member_count - 1);
 	for (mh_int_t rc = mh_swim_table_random(t, rnd), end = mh_end(t);
 	     i < member_count; ++i) {
 		struct swim_member *m = *mh_swim_table_node(t, rc);
@@ -1380,7 +1362,7 @@ swim_send_indirect_pings(struct swim *swim, const struct swim_member *dst)
 {
 	struct mh_swim_table_t *t = swim->members;
 	int member_count = mh_size(t);
-	int rnd = swim_scaled_rand(0, member_count - 1);
+	int rnd = pseudo_random_in_range(0, member_count - 1);
 	mh_int_t rc = mh_swim_table_random(t, rnd), end = mh_end(t);
 	for (int member_i = 0, task_i = 0; member_i < member_count &&
 	     task_i < INDIRECT_PING_COUNT; ++member_i) {
diff --git a/test/unit/CMakeLists.txt b/test/unit/CMakeLists.txt
index 419477748..4be9271c6 100644
--- a/test/unit/CMakeLists.txt
+++ b/test/unit/CMakeLists.txt
@@ -52,6 +52,8 @@ add_executable(base64.test base64.c)
 target_link_libraries(base64.test misc unit)
 add_executable(uuid.test uuid.c)
 target_link_libraries(uuid.test uuid unit)
+add_executable(random.test random.c)
+target_link_libraries(random.test core unit)
 
 add_executable(bps_tree.test bps_tree.cc)
 target_link_libraries(bps_tree.test small misc)
diff --git a/test/unit/histogram.c b/test/unit/histogram.c
index 3056d20fe..ef5cd714f 100644
--- a/test/unit/histogram.c
+++ b/test/unit/histogram.c
@@ -5,6 +5,7 @@
 #include "memory.h"
 #include "unit.h"
 #include "trivia/util.h"
+#include "core/random.h"
 
 static int
 int64_cmp(const void *p1, const void *p2)
@@ -46,13 +47,6 @@ gen_rand_data(size_t *p_len)
 	return data;
 }
 
-static int64_t
-gen_rand_value(int64_t min, int64_t max)
-{
-	assert(max >= min);
-	return min + rand() % (max - min + 1);
-}
-
 static void
 test_counts(void)
 {
@@ -97,7 +91,7 @@ test_discard(void)
 
 	struct histogram *hist = histogram_new(buckets, n_buckets);
 
-	size_t bucket_sz = gen_rand_value(2, 10);
+	size_t bucket_sz = pseudo_random_in_range(2, 10);
 	size_t data_len = (n_buckets + 1) * bucket_sz;
 	int64_t *data = calloc(data_len, sizeof(*data));
 
@@ -105,7 +99,7 @@ test_discard(void)
 		int64_t min = (b == 0 ? INT64_MIN : buckets[b - 1] + 1);
 		int64_t max = (b == n_buckets ? INT64_MAX : buckets[b]);
 		for (size_t i = 0; i < bucket_sz; i++)
-			data[b * bucket_sz + i] = gen_rand_value(min, max);
+			data[b * bucket_sz + i] = pseudo_random_in_range(min, max);
 	}
 
 	for (size_t i = 0; i < data_len; i++)
diff --git a/test/unit/random.c b/test/unit/random.c
new file mode 100644
index 000000000..fe94b1eae
--- /dev/null
+++ b/test/unit/random.c
@@ -0,0 +1,56 @@
+#include <core/random.h>
+
+#include <stdio.h>
+#include <assert.h>
+
+#include "unit.h"
+
+static void
+test_xoshiro_random_in_range_one(int64_t min, int64_t max)
+{
+	int64_t result = pseudo_random_in_range(min, max);
+	assert(min <= result && result <= max);
+	if (min == max)
+		printf("pseudo_random_in_range(%lld, %lld) = %lld\n",
+		       (long long)min, (long long)max, (long long)result);
+
+	result = real_random_in_range(min, max);
+	assert(min <= result && result <= max);
+	if (min == max)
+		printf("real_random_in_range(%lld, %lld) = %lld\n",
+		      (long long)min, (long long)max, (long long)result);
+}
+
+static void
+test_xoshiro_random_in_range(void)
+{
+	header();
+
+	test_xoshiro_random_in_range_one(INT64_MIN, INT64_MAX);
+	test_xoshiro_random_in_range_one(INT64_MIN, INT64_MIN);
+	test_xoshiro_random_in_range_one(INT64_MAX, INT64_MAX);
+	test_xoshiro_random_in_range_one(-1, -1);
+	test_xoshiro_random_in_range_one(0, 0);
+	test_xoshiro_random_in_range_one(1, 1);
+
+	test_xoshiro_random_in_range_one(INT64_MIN + 1, INT64_MAX - 1);
+	test_xoshiro_random_in_range_one(INT64_MIN / 2, INT64_MAX / 2);
+	test_xoshiro_random_in_range_one(INT64_MIN, INT64_MIN / 2);
+	test_xoshiro_random_in_range_one(INT64_MAX / 2, INT64_MAX);
+	test_xoshiro_random_in_range_one(-2, -1);
+	test_xoshiro_random_in_range_one(1, 2);
+	test_xoshiro_random_in_range_one(-1, 1);
+	test_xoshiro_random_in_range_one(0, 1);
+
+	footer();
+}
+
+int
+main(void)
+{
+	random_init();
+
+	test_xoshiro_random_in_range();
+
+	random_free();
+}
diff --git a/test/unit/random.result b/test/unit/random.result
new file mode 100644
index 000000000..3d19130bf
--- /dev/null
+++ b/test/unit/random.result
@@ -0,0 +1,12 @@
+	*** test_xoshiro_random_in_range ***
+pseudo_random_in_range(-9223372036854775808, -9223372036854775808) = -9223372036854775808
+real_random_in_range(-9223372036854775808, -9223372036854775808) = -9223372036854775808
+pseudo_random_in_range(9223372036854775807, 9223372036854775807) = 9223372036854775807
+real_random_in_range(9223372036854775807, 9223372036854775807) = 9223372036854775807
+pseudo_random_in_range(-1, -1) = -1
+real_random_in_range(-1, -1) = -1
+pseudo_random_in_range(0, 0) = 0
+real_random_in_range(0, 0) = 0
+pseudo_random_in_range(1, 1) = 1
+real_random_in_range(1, 1) = 1
+	*** test_xoshiro_random_in_range: done ***
diff --git a/test/unit/swim_test_utils.c b/test/unit/swim_test_utils.c
index 9dbd28a9f..7ac43d82d 100644
--- a/test/unit/swim_test_utils.c
+++ b/test/unit/swim_test_utils.c
@@ -875,7 +875,8 @@ swim_run_test(const char *log_file, fiber_func test)
 	 * Print the seed to be able to reproduce a bug with the
 	 * same seed.
 	 */
-	say_info("Random seed = %llu", (unsigned long long) seed);
+	say_info("Random seed = %llu", (unsigned long long)seed);
+	say_info("xoshiro random state = %s", xoshiro_state_str());
 
 	struct fiber *main_fiber = fiber_new("main", test);
 	fiber_set_joinable(main_fiber, true);
-- 
2.17.1

^ permalink raw reply	[flat|nested] 5+ messages in thread

end of thread, other threads:[~2020-11-13 11:54 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-11-05 12:09 [Tarantool-patches] [PATCH v4] core: introduce evenly distributed int64 random in range Ilya Kosarev
2020-11-11 22:07 ` Vladislav Shpilevoy
2020-11-13 11:54   ` Ilya Kosarev
  -- strict thread matches above, loose matches on Subject: below --
2020-11-05 11:14 Ilya Kosarev
2020-11-05 11:07 Ilya Kosarev

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox