BUG/MEDIUM: random: implement a thread-safe and process-safe PRNG
This is the replacement of failed attempt to add thread safety and
per-process sequences of random numbers initally tried with commit
1c306aa84d ("BUG/MEDIUM: random: implement per-thread and per-process
random sequences").
This new version takes a completely different approach and doesn't try
to work around the horrible OS-specific and non-portable random API
anymore. Instead it implements "xoroshiro128**", a reputedly high
quality random number generator, which is one of the many variants of
xorshift, which passes all quality tests and which is described here:
http://prng.di.unimi.it/
While not cryptographically secure, it is fast and features a 2^128-1
period. It supports fast jumps allowing to cut the period into smaller
non-overlapping sequences, which we use here to support up to 2^32
processes each having their own, non-overlapping sequence of 2^96
numbers (~7*10^28). This is enough to provide 1 billion randoms per
second and per process for 2200 billion years.
The implementation was made thread-safe either by using a double 64-bit
CAS on platforms supporting it (x86_64, aarch64) or by using a local
lock for the time needed to perform the shift operations. This ensures
that all threads pick numbers from the same pool so that it is not
needed to assign per-thread ranges. For processes we use the fast jump
method to advance the sequence by 2^96 for each process.
There are multiple benefits to using this method. First, it doesn't
depend anymore on a non-portable API. Second it's thread safe. Third it
is fast and more proven than any hack we could do to try to work around
the breakage of various implementations.
This commit depends on previous patch "MINOR: tools: add 64-bit rotate
operators", both of which will need to be backported at least as far as
version 2.0. It doesn't require to backport the build fixes for circular
include files dependecy anymore.
(cherry picked from commit 52bf839394e683eec2fa8aafff5a0dd51d2dd365)
[wt: minor context adjustments]
(cherry picked from commit d4ac067fe4708e5c7c77d8f356a53d7d376ced40)
[wt: context adjustments, random() appearing at other places]
Signed-off-by: Willy Tarreau <w@1wt.eu>
diff --git a/src/pattern.c b/src/pattern.c
index 90067cd..df915f5 100644
--- a/src/pattern.c
+++ b/src/pattern.c
@@ -2652,7 +2652,7 @@
struct pat_ref *ref, *ref2, *ref3;
struct list pr = LIST_HEAD_INIT(pr);
- pat_lru_seed = random();
+ pat_lru_seed = ha_random();
list_for_each_entry(ref, &pattern_reference, list) {
if (ref->unique_id == -1) {