From 52bf839394e683eec2fa8aafff5a0dd51d2dd365 Mon Sep 17 00:00:00 2001 From: Willy Tarreau Date: Sun, 8 Mar 2020 00:42:37 +0100 Subject: [PATCH] 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. Before this patch, the following config: global nbproc 8 frontend f bind :4445 mode http log stdout format raw daemon log-format "%[uuid] %pid" redirect location / Would produce this output: a4d0ad64-2645-4b74-b894-48acce0669af 12987 a4d0ad64-2645-4b74-b894-48acce0669af 12992 a4d0ad64-2645-4b74-b894-48acce0669af 12986 a4d0ad64-2645-4b74-b894-48acce0669af 12988 a4d0ad64-2645-4b74-b894-48acce0669af 12991 a4d0ad64-2645-4b74-b894-48acce0669af 12989 a4d0ad64-2645-4b74-b894-48acce0669af 12990 82d5f6cd-f6c1-4f85-a89c-36ae85d26fb9 12987 82d5f6cd-f6c1-4f85-a89c-36ae85d26fb9 12992 82d5f6cd-f6c1-4f85-a89c-36ae85d26fb9 12986 (...) And now produces: f94b29b3-da74-4e03-a0c5-a532c635bad9 13011 47470c02-4862-4c33-80e7-a952899570e5 13014 86332123-539a-47bf-853f-8c8ea8b2a2b5 13013 8f9efa99-3143-47b2-83cf-d618c8dea711 13012 3cc0f5c7-d790-496b-8d39-bec77647af5b 13015 3ec64915-8f95-4374-9e66-e777dc8791e0 13009 0f9bf894-dcde-408c-b094-6e0bb3255452 13011 49c7bfde-3ffb-40e9-9a8d-8084d650ed8f 13014 e23f6f2e-35c5-4433-a294-b790ab902653 13012 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 attempt to try to work around the deficiencies of the various implementations around. This commit depends on previous patches "MINOR: tools: add 64-bit rotate operators" and "BUG/MEDIUM: random: initialize the random pool a bit better", all 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. --- include/common/standard.h | 15 +++++ src/51d.c | 2 +- src/backend.c | 2 +- src/flt_spoe.c | 6 +- src/flt_trace.c | 6 +- src/haproxy.c | 9 ++- src/memory.c | 2 +- src/pattern.c | 2 +- src/peers.c | 6 +- src/sample.c | 4 +- src/standard.c | 112 ++++++++++++++++++++++++++++++++++++++ 11 files changed, 148 insertions(+), 18 deletions(-) diff --git a/include/common/standard.h b/include/common/standard.h index f9eed961fd..d8bccbafb6 100644 --- a/include/common/standard.h +++ b/include/common/standard.h @@ -1550,6 +1550,21 @@ static inline void *my_realloc2(void *ptr, size_t size) int parse_dotted_uints(const char *s, unsigned int **nums, size_t *sz); +/* PRNG */ +void ha_random_seed(const unsigned char *seed, size_t len); +void ha_random_jump96(uint32_t dist); +uint64_t ha_random64(); + +static inline uint32_t ha_random32() +{ + return ha_random64() >> 32; +} + +static inline int32_t ha_random() +{ + return ha_random32() >> 1; +} + /* HAP_STRING() makes a string from a literal while HAP_XSTRING() first * evaluates the argument and is suited to pass macros. * diff --git a/src/51d.c b/src/51d.c index b00f01844a..42d1929679 100644 --- a/src/51d.c +++ b/src/51d.c @@ -700,7 +700,7 @@ static int init_51degrees(void) free(_51d_property_list); #ifdef FIFTYONEDEGREES_H_PATTERN_INCLUDED - _51d_lru_seed = random(); + _51d_lru_seed = ha_random(); if (global_51degrees.cache_size) { _51d_lru_tree = lru64_new(global_51degrees.cache_size); } diff --git a/src/backend.c b/src/backend.c index 251a7a5a47..87e3b9a1c7 100644 --- a/src/backend.c +++ b/src/backend.c @@ -541,7 +541,7 @@ static struct server *get_server_rnd(struct stream *s, const struct server *avoi do { prev = curr; /* ensure all 32 bits are covered as long as RAND_MAX >= 65535 */ - hash = ((uint64_t)random() * ((uint64_t)RAND_MAX + 1)) ^ random(); + hash = ((uint64_t)ha_random() * ((uint64_t)RAND_MAX + 1)) ^ ha_random(); curr = chash_get_server_hash(px, hash, avoid); if (!curr) break; diff --git a/src/flt_spoe.c b/src/flt_spoe.c index d54fcd4370..bcdec08e78 100644 --- a/src/flt_spoe.c +++ b/src/flt_spoe.c @@ -269,7 +269,7 @@ generate_pseudo_uuid() while (byte < 4) { while (bits < 32) { - last |= (uint64_t)random() << bits; + last |= (uint64_t)ha_random() << bits; bits += rand_max_bits; } rnd[byte++] = last; @@ -3109,10 +3109,6 @@ spoe_init_per_thread(struct proxy *p, struct flt_conf *fconf) struct spoe_config *conf = fconf->conf; struct spoe_agent *agent = conf->agent; - /* Use a != seed per process */ - if (relative_pid > 1 && tid == 0) - srandom(now_ms * pid); - agent->rt[tid].engine_id = generate_pseudo_uuid(); if (agent->rt[tid].engine_id == NULL) return -1; diff --git a/src/flt_trace.c b/src/flt_trace.c index 5a26fabea2..b06ba150b2 100644 --- a/src/flt_trace.c +++ b/src/flt_trace.c @@ -468,7 +468,7 @@ trace_http_payload(struct stream *s, struct filter *filter, struct http_msg *msg unsigned int data = trace_get_htx_datalen(htxbuf(&msg->chn->buf), offset, len); if (data) { - ret = random() % (ret+1); + ret = ha_random() % (ret+1); if (!ret || ret >= data) ret = len; } @@ -536,7 +536,7 @@ trace_tcp_payload(struct stream *s, struct filter *filter, struct channel *chn, unsigned int data = trace_get_htx_datalen(htxbuf(&chn->buf), offset, len); if (data) { - ret = random() % (ret+1); + ret = ha_random() % (ret+1); if (!ret || ret >= data) ret = len; } @@ -554,7 +554,7 @@ trace_tcp_payload(struct stream *s, struct filter *filter, struct channel *chn, else { if (ret && conf->rand_forwarding) - ret = random() % (ret+1); + ret = ha_random() % (ret+1); FLT_STRM_TRACE(conf, s, "%-25s: channel=%-10s - mode=%-5s (%s) - " "offset=%u - len=%u - forward=%d", diff --git a/src/haproxy.c b/src/haproxy.c index ef9010f958..180dbdb435 100644 --- a/src/haproxy.c +++ b/src/haproxy.c @@ -1374,6 +1374,10 @@ static char **copy_argv(int argc, char **argv) * We initialize the current process with the first 32 bits before starting the * polling loop, where all this will be changed to have process specific and * thread specific sequences. + * + * Before starting threads, it's still possible to call random() as srandom() + * is initialized from this, but after threads and/or processes are started, + * only ha_random() is expected to be used to guarantee distinct sequences. */ static void ha_random_boot(char *const *argv) { @@ -1444,6 +1448,7 @@ static void ha_random_boot(char *const *argv) blk_SHA1_Final(boot_seed, &ctx); srandom(read_u32(boot_seed)); + ha_random_seed(boot_seed, sizeof(boot_seed)); } /* considers splicing proxies' maxconn, computes the ideal global.maxpipes @@ -3248,8 +3253,10 @@ int main(int argc, char **argv) protocol_unbind_all(); exit(1); /* there has been an error */ } - else if (ret == 0) /* child breaks here */ + else if (ret == 0) { /* child breaks here */ + ha_random_jump96(relative_pid); break; + } if (pidfd >= 0 && !(global.mode & MODE_MWORKER)) { char pidstr[100]; snprintf(pidstr, sizeof(pidstr), "%d\n", ret); diff --git a/src/memory.c b/src/memory.c index d1aec5925c..0ff3ea8b8f 100644 --- a/src/memory.c +++ b/src/memory.c @@ -628,7 +628,7 @@ int mem_should_fail(const struct pool_head *pool) int n; if (mem_fail_rate > 0 && !(global.mode & MODE_STARTING)) { - int randnb = random() % 100; + int randnb = ha_random() % 100; if (mem_fail_rate > randnb) ret = 1; diff --git a/src/pattern.c b/src/pattern.c index 8dfe3cf29b..3ea1f33d44 100644 --- a/src/pattern.c +++ b/src/pattern.c @@ -2667,7 +2667,7 @@ int pattern_finalize_config(void) struct pat_ref *ref, **arr; struct list pr = LIST_HEAD_INIT(pr); - pat_lru_seed = random(); + pat_lru_seed = ha_random(); /* Count pat_refs with user defined unique_id and totalt count */ list_for_each_entry(ref, &pattern_reference, list) { diff --git a/src/peers.c b/src/peers.c index f5a4f18655..640a99f5e9 100644 --- a/src/peers.c +++ b/src/peers.c @@ -2232,7 +2232,7 @@ switchstate: * retrying otherwise the other end will do the same and we can loop * for a while. */ - curpeer->reconnect = tick_add(now_ms, MS_TO_TICKS(50 + random() % 2000)); + curpeer->reconnect = tick_add(now_ms, MS_TO_TICKS(50 + ha_random() % 2000)); peer_session_forceshutdown(curpeer); } if (maj_ver != (unsigned int)-1 && min_ver != (unsigned int)-1) { @@ -2685,7 +2685,7 @@ static struct task *process_peer_sync(struct task * task, void *context, unsigne ps->reconnect = tick_add(now_ms, MS_TO_TICKS(PEER_RECONNECT_TIMEOUT)); } else { - ps->reconnect = tick_add(now_ms, MS_TO_TICKS(50 + random() % 2000)); + ps->reconnect = tick_add(now_ms, MS_TO_TICKS(50 + ha_random() % 2000)); peer_session_forceshutdown(ps); ps->no_hbt++; } @@ -2741,7 +2741,7 @@ static struct task *process_peer_sync(struct task * task, void *context, unsigne * retrying otherwise the other end will do the same and we can loop * for a while. */ - ps->reconnect = tick_add(now_ms, MS_TO_TICKS(50 + random() % 2000)); + ps->reconnect = tick_add(now_ms, MS_TO_TICKS(50 + ha_random() % 2000)); if (ps->appctx) { peer_session_forceshutdown(ps); } diff --git a/src/sample.c b/src/sample.c index 3c61112240..fd63902a9f 100644 --- a/src/sample.c +++ b/src/sample.c @@ -3124,7 +3124,7 @@ smp_fetch_thread(const struct arg *args, struct sample *smp, const char *kw, voi static int smp_fetch_rand(const struct arg *args, struct sample *smp, const char *kw, void *private) { - smp->data.u.sint = random(); + smp->data.u.sint = ha_random(); /* reduce if needed. Don't do a modulo, use all bits! */ if (args && args[0].type == ARGT_SINT) @@ -3336,7 +3336,7 @@ static int smp_fetch_uuid(const struct arg *args, struct sample *smp, const char while (byte < 4) { while (bits < 32) { - last |= (uint64_t)random() << bits; + last |= (uint64_t)ha_random() << bits; bits += rand_max_bits; } rnd[byte++] = last; diff --git a/src/standard.c b/src/standard.c index 38997d5f48..5ccf44776a 100644 --- a/src/standard.c +++ b/src/standard.c @@ -4528,6 +4528,118 @@ int varint_bytes(uint64_t v) return len; } + +/* Random number generator state, see below */ +static uint64_t ha_random_state[2]; + +/* This is a thread-safe implementation of xoroshiro128** described below: + * http://prng.di.unimi.it/ + * It features a 2^128 long sequence, returns 64 high-quality bits on each call, + * supports fast jumps and passes all common quality tests. It is thread-safe, + * uses a double-cas on 64-bit architectures supporting it, and falls back to a + * local lock on other ones. + */ +uint64_t ha_random64() +{ + uint64_t result; + uint64_t old[2]; + uint64_t new[2]; + +#if defined(USE_THREAD) && (!defined(HA_CAS_IS_8B) || !defined(HA_HAVE_CAS_DW)) + static HA_SPINLOCK_T rand_lock; + + HA_SPIN_LOCK(OTHER_LOCK, &rand_lock); +#endif + + old[0] = ha_random_state[0]; + old[1] = ha_random_state[1]; + +#if defined(USE_THREAD) && defined(HA_CAS_IS_8B) && defined(HA_HAVE_CAS_DW) + do { +#endif + result = rotl64(old[0] * 5, 7) * 9; + new[1] = old[0] ^ old[1]; + new[0] = rotl64(old[0], 24) ^ new[1] ^ (new[1] << 16); // a, b + new[1] = rotl64(new[1], 37); // c + +#if defined(USE_THREAD) && defined(HA_CAS_IS_8B) && defined(HA_HAVE_CAS_DW) + } while (unlikely(!_HA_ATOMIC_DWCAS(ha_random_state, old, new))); +#else + ha_random_state[0] = new[0]; + ha_random_state[1] = new[1]; +#if defined(USE_THREAD) + HA_SPIN_UNLOCK(OTHER_LOCK, &rand_lock); +#endif +#endif + return result; +} + +/* seeds the random state using up to bytes from , starting with + * the first non-zero byte. + */ +void ha_random_seed(const unsigned char *seed, size_t len) +{ + size_t pos; + + /* the seed must not be all zeroes, so we pre-fill it with alternating + * bits and overwrite part of them with the block starting at the first + * non-zero byte from the seed. + */ + memset(ha_random_state, 0x55, sizeof(ha_random_state)); + + for (pos = 0; pos < len; pos++) + if (seed[pos] != 0) + break; + + if (pos == len) + return; + + seed += pos; + len -= pos; + + if (len > sizeof(ha_random_state)) + len = sizeof(ha_random_state); + + memcpy(ha_random_state, seed, len); +} + +/* This causes a jump to (dist * 2^96) places in the pseudo-random sequence, + * and is equivalent to calling ha_random64() as many times. It is used to + * provide non-overlapping sequences of 2^96 numbers (~7*10^28) to up to 2^32 + * different generators (i.e. different processes after a fork). The + * argument is the distance to jump to and is used in a loop so it rather not + * be too large if the processing time is a concern. + * + * BEWARE: this function is NOT thread-safe and must not be called during + * concurrent accesses to ha_random64(). + */ +void ha_random_jump96(uint32_t dist) +{ + while (dist--) { + uint64_t s0 = 0; + uint64_t s1 = 0; + int b; + + for (b = 0; b < 64; b++) { + if ((0xd2a98b26625eee7bULL >> b) & 1) { + s0 ^= ha_random_state[0]; + s1 ^= ha_random_state[1]; + } + ha_random64(); + } + + for (b = 0; b < 64; b++) { + if ((0xdddf9b1090aa7ac1ULL >> b) & 1) { + s0 ^= ha_random_state[0]; + s1 ^= ha_random_state[1]; + } + ha_random64(); + } + ha_random_state[0] = s0; + ha_random_state[1] = s1; + } +} + /* * Local variables: * c-indent-level: 8 -- 2.39.5