random: use per lcore state
RFC 1/1 random: use per lcore state
Move the random number state into thread local storage. This has a several benefits.
- no false cache sharing from cpu prefetching
- fixes initialization of random state for non-DPDK threads
- fixes unsafe usage of random state by non-DPDK threads
The initialization of random number state is done by the lcore (lazy initialization).
--- lib/eal/common/rte_random.c | 38 +++++++++++++++++++------------------ 1 file changed, 20 insertions(+), 18 deletions(-)
lib/eal/common/rte_random.c +20 -18
@@ -19,13 +19,14 @@ struct rte_rand_state {uint64_t z3;uint64_t z4;uint64_t z5; -} __rte_cache_aligned; +uint64_t seed; +}; -/* One instance each for every lcore id-equipped thread, and one -* additional instance to be shared by all others threads (i.e., all -* unregistered non-EAL threads). -*/ -static struct rte_rand_state rand_states[RTE_MAX_LCORE +1 ]; +/* Global random seed */ +static uint64_t rte_rand_seed; + +/* Per lcore random state. */ +static RTE_DEFINE_PER_LCORE(struct rte_rand_state, rte_rand_state);static uint32_t __rte_rand_lcg32 (uint32_t *seed)
@@ -81,11 +82,7 @@ __rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)void rte_srand (uint64_t seed) { -unsigned int lcore_id; - -/* add lcore_id to seed to avoid having the same sequence */ -for (lcore_id =0 ; lcore_id <RTE_MAX_LCORE ; lcore_id++) -__rte_srand_lfsr258 (seed + lcore_id, &rand_states[lcore_id]); +__atomic_store_n (&rte_rand_seed, seed, __ATOMIC_RELAXED); }static __rte_always_inline uint64_t
@@ -119,15 +116,18 @@ __rte_rand_lfsr258(struct rte_rand_state *state)static __rte_always_inline struct rte_rand_state *__rte_rand_get_state(void) { -unsigned int idx; +struct rte_rand_state *rand_state = &RTE_PER_LCORE (rte_rand_state); +uint64_t seed; - idx =rte_lcore_id (); + seed =__atomic_load_n (&rte_rand_seed, __ATOMIC_RELAXED); +if (unlikely (seed != rand_state->seed)) { + rand_state->seed = seed; -/* last instance reserved for unregistered non-EAL threads */ -if (unlikely (idx ==LCORE_ID_ANY )) - idx =RTE_MAX_LCORE ; + seed +=rte_thread_self ().opaque_id; +__rte_srand_lfsr258 (seed, rand_state); + } -return &rand_states[idx]; +return rand_state; }uint64_t
@@ -227,7 +227,9 @@ RTE_INIT(rte_rand_init) {uint64_t seed; - seed =__rte_random_initial_seed (); +do + seed =__rte_random_initial_seed (); +while (seed ==0 );rte_srand (seed); }
Signature · 1 line
2.39.2
Quoted 59 lines
From: Stephen Hemminger [mailto:[email protected]]
Sent: Wednesday, 6 September 2023 19.20Move the random number state into thread local storage. This has a several benefits.
- no false cache sharing from cpu prefetching
- fixes initialization of random state for non-DPDK threads
- fixes unsafe usage of random state by non-DPDK threadsThe initialization of random number state is done by the lcore (lazy initialization).
Signed-off-by Stephen Hemminger <[email protected]>--- lib/eal/common/rte_random.c | 38 +++++++++++++++++++------------------ 1 file changed, 20 insertions(+), 18 deletions(-)lib/eal/common/rte_random.c +8
-11@@ -19,13 +19,14 @@ struct rte_rand_state {uint64_t z3;uint64_t z4;uint64_t z5; -} __rte_cache_aligned; +uint64_t seed; +}; -/* One instance each for every lcore id-equipped thread, and one -* additional instance to be shared by all others threads (i.e., all -* unregistered non-EAL threads). -*/ -static struct rte_rand_state rand_states[RTE_MAX_LCORE +1 ]; +/* Global random seed */ +static uint64_t rte_rand_seed; + +/* Per lcore random state. */ +static RTE_DEFINE_PER_LCORE(struct rte_rand_state, rte_rand_state);static uint32_t __rte_rand_lcg32 (uint32_t *seed)@@ -81,11 +82,7 @@ __rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)void rte_srand (uint64_t seed) { -unsigned int lcore_id; - -/* add lcore_id to seed to avoid having the same sequence */ -for (lcore_id =0 ; lcore_id <RTE_MAX_LCORE ; lcore_id++) -__rte_srand_lfsr258 (seed + lcore_id, &rand_states[lcore_id]); +__atomic_store_n (&rte_rand_seed, seed, __ATOMIC_RELAXED); }static
__rte_always_inlineuint64_tlib/eal/common/rte_random.c +0
-0@@ -119,15 +116,18 @@ __rte_rand_lfsr258(struct rte_rand_state *state) static __rte_always_inline
lib/eal/common/rte_random.c __rte_rand_lfsr258(struct rte_rand_state *state) · line 124
Quoted 10 lines
lib/eal/common/rte_random.c +4
-2struct rte_rand_state *__rte_rand_get_state (void ) { -unsigned int idx; +struct rte_rand_state *rand_state = &RTE_PER_LCORE (rte_rand_state); +uint64_t seed; - idx =rte_lcore_id (); + seed =__atomic_load_n (&rte_rand_seed, __ATOMIC_RELAXED); +if (unlikely (seed != rand_state->seed)) {
Please note that rte_rand_seed lives in a completely different cache line than RTE_PER_LCORE(rte_rand_state), so the comparison with rte_rand_seed requires reading one more cache line than the original implementation, which only uses the cache line holding rand_states[idx].
This is in the hot path.
If we could register a per-thread INIT function, the lazy initialization could be avoided, and only one cache line accessed.
Quoted 27 lines
lib/eal/common/rte_random.c +5
-4+ rand_state->seed = seed; -/* last instance reserved for unregistered non-EAL threads */ -if (unlikely (idx ==LCORE_ID_ANY )) - idx =RTE_MAX_LCORE ; + seed +=rte_thread_self ().opaque_id; +__rte_srand_lfsr258 (seed, rand_state); + } -return &rand_states[idx]; +return rand_state; }
uint64_tlib/eal/common/rte_random.c +3
-2@@ -227,7 +227,9 @@ RTE_INIT(rte_rand_init) {uint64_t seed; - seed =__rte_random_initial_seed (); +do + seed =__rte_random_initial_seed (); +while (seed ==0 );rte_srand (seed); } --2.39.2
Quoted 11 lines · On Wed, 6 Sep 2023 19:54:32 +0200 Morten Brørup <[email protected]>…
lib/eal/common/rte_random.c __rte_rand_lfsr258(struct rte_rand_state *state) · line 123
Quoted 4 lines
lib/eal/common/rte_random.c +2
-1- idx =rte_lcore_id (); + seed =__atomic_load_n (&rte_rand_seed, __ATOMIC_RELAXED); +if (unlikely (seed != rand_state->seed)) {Please note that
rte_rand_seedlives in a completely different cache line thanRTE_PER_LCORE(rte_rand_state), so the comparison withrte_rand_seedrequires reading one more cache line than the original implementation, which only uses the cache line holding rand_states[idx].
Quoted 4 lines
This is in the hot path.
If we could register a per-thread INIT function, the lazy initialization could be avoided, and only one cache line accessed.
Since rte_rand_seed rarely changes, it will get cached by each cpu. The problem was before there was prefetch cache overlap causing false sharing.
Quoted 17 lines
From: Stephen Hemminger [mailto:[email protected]]
Sent: Monday, 11 September 2023 17.04Quoted 11 lines · On Wed, 6 Sep 2023 19:54:32 +0200 Morten Brørup <[email protected]>…
lib/eal/common/rte_random.c __rte_rand_lfsr258(struct rte_rand_state *state) · line 123
Quoted 4 lines
lib/eal/common/rte_random.c +2
-1- idx =rte_lcore_id (); + seed =__atomic_load_n (&rte_rand_seed, __ATOMIC_RELAXED); +if (unlikely (seed != rand_state->seed)) {Please note that
rte_rand_seedlives in a completely different cache line thanRTE_PER_LCORE(rte_rand_state), so the comparison withrte_rand_seedrequires reading one more cache line than the original implementation, which only uses the cache line holding rand_states[idx].
Quoted 6 lines
Quoted 4 lines
This is in the hot path.
If we could register a per-thread INIT function, the lazy initialization could be avoided, and only one cache line accessed.
Since
rte_rand_seedrarely changes, it will get cached by each cpu.
Agreed. And the point I was trying to convey was that this will consume cache on each CPU. Cache is a scarce resource on some hardware.
If reading rte_rand_seed is gated by (bool) rand_state->initialized, the __rte_rand_get_state() function is less likely to evict other data from the cache to make room for rte_rand_seed in the cache.
Quoted 2 lines
The problem was before there was prefetch cache overlap causing false sharing.
Yes, and my patch also wastes a cache line per state, because of the cache guard.
So far, we have use this simple function for a discussion of principles and design patterns... so let me bring something new into the discussion, which is relevant on both the abstract and the practical level:
We could keep using the rte_module_data[RTE_MAX_LCORE] design pattern generally. But we could make an exception for data structures significantly smaller than a cache line. If we use TLS for those, we would avoid gaps in the memory allocated for those, which is even more cache efficient.
Let's assume that (unsigned int) RTE_PER_LCORE(_lcore_id) is currently the only data in TLS. If we add (struct rte_rand_state) RTE_PER_LCORE(rand_state), it will go into the same cache line as RTE_PER_LCORE(_lcore_id), and effectively only cost a fraction of a cache line.
Quoted 59 lines
From: Stephen Hemminger [mailto:[email protected]]
Sent: Wednesday, 6 September 2023 19.20Move the random number state into thread local storage. This has a several benefits.
- no false cache sharing from cpu prefetching
- fixes initialization of random state for non-DPDK threads
- fixes unsafe usage of random state by non-DPDK threadsThe initialization of random number state is done by the lcore (lazy initialization).
Signed-off-by Stephen Hemminger <[email protected]>--- lib/eal/common/rte_random.c | 38 +++++++++++++++++++------------------ 1 file changed, 20 insertions(+), 18 deletions(-)lib/eal/common/rte_random.c +8
-11@@ -19,13 +19,14 @@ struct rte_rand_state {uint64_t z3;uint64_t z4;uint64_t z5; -} __rte_cache_aligned; +uint64_t seed; +}; -/* One instance each for every lcore id-equipped thread, and one -* additional instance to be shared by all others threads (i.e., all -* unregistered non-EAL threads). -*/ -static struct rte_rand_state rand_states[RTE_MAX_LCORE +1 ]; +/* Global random seed */ +static uint64_t rte_rand_seed; + +/* Per lcore random state. */ +static RTE_DEFINE_PER_LCORE(struct rte_rand_state, rte_rand_state);static uint32_t __rte_rand_lcg32 (uint32_t *seed)@@ -81,11 +82,7 @@ __rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)void rte_srand (uint64_t seed) { -unsigned int lcore_id; - -/* add lcore_id to seed to avoid having the same sequence */ -for (lcore_id =0 ; lcore_id <RTE_MAX_LCORE ; lcore_id++) -__rte_srand_lfsr258 (seed + lcore_id, &rand_states[lcore_id]); +__atomic_store_n (&rte_rand_seed, seed, __ATOMIC_RELAXED); }static
__rte_always_inlineuint64_tlib/eal/common/rte_random.c +0
-0@@ -119,15 +116,18 @@ __rte_rand_lfsr258(struct rte_rand_state *state) static __rte_always_inline
lib/eal/common/rte_random.c __rte_rand_lfsr258(struct rte_rand_state *state) · line 124
Quoted 10 lines
lib/eal/common/rte_random.c +4
-2struct rte_rand_state *__rte_rand_get_state (void ) { -unsigned int idx; +struct rte_rand_state *rand_state = &RTE_PER_LCORE (rte_rand_state); +uint64_t seed; - idx =rte_lcore_id (); + seed =__atomic_load_n (&rte_rand_seed, __ATOMIC_RELAXED); +if (unlikely (seed != rand_state->seed)) {
Please note that rte_rand_seed lives in a completely different cache line than RTE_PER_LCORE(rte_rand_state), so the comparison with rte_rand_seed requires reading one more cache line than the original implementation, which only uses the cache line holding rand_states[idx].
This is in the hot path.
If we could register a per-thread INIT function, the lazy initialization could be avoided, and only one cache line accessed.
Or, simply replace "uint64_t seed" with "bool initialized" in the rte_rand_state structure, so the lazy init only needs to read rte_rand_seed if rand_state->initialized is false.
Quoted 27 lines
lib/eal/common/rte_random.c +5
-4+ rand_state->seed = seed; -/* last instance reserved for unregistered non-EAL threads */ -if (unlikely (idx ==LCORE_ID_ANY )) - idx =RTE_MAX_LCORE ; + seed +=rte_thread_self ().opaque_id; +__rte_srand_lfsr258 (seed, rand_state); + } -return &rand_states[idx]; +return rand_state; }
uint64_tlib/eal/common/rte_random.c +3
-2@@ -227,7 +227,9 @@ RTE_INIT(rte_rand_init) {uint64_t seed; - seed =__rte_random_initial_seed (); +do + seed =__rte_random_initial_seed (); +while (seed ==0 );rte_srand (seed); } --2.39.2
Quoted 8 lines · On Wed, 6 Sep 2023 10:20:13 -0700 Stephen Hemminger…
static
__rte_always_inline
structrte_rand_state*__rte_rand_get_state(void){lib/eal/common/rte_random.c +2
-2-unsigned int idx; +struct rte_rand_state *rand_state = &RTE_PER_LCORE (rte_rand_state); +uint64_t seed; - idx =rte_lcore_id ();
lib/eal/common/rte_random.c __rte_rand_lfsr258(struct rte_rand_state *state) · line 128
Quoted 10 lines
lib/eal/common/rte_random.c +6
-3+ seed =__atomic_load_n (&rte_rand_seed, __ATOMIC_RELAXED); +if (unlikely (seed != rand_state->seed)) { + rand_state->seed = seed; -/* last instance reserved for unregistered non-EAL threads */ -if (unlikely (idx ==LCORE_ID_ANY )) - idx =RTE_MAX_LCORE ; + seed +=rte_thread_self ().opaque_id; +__rte_srand_lfsr258 (seed, rand_state); + }
Not sure about this.
It would change the semantics of rte_srand so that if passed the same value across multiple runs, it would still generate different values because thread_id is not the same. Using rte_lcore() instead would cause repeatablity but then there would still be a bug if two non-EAL threads used random. Both threads would get the same sequence of numbers, but that is true with current code.
Quoted 15 lines · Stephen Hemminger
Quoted 12 lines · On Wed, 6 Sep 2023 10:20:13 -0700 Stephen Hemminger…
static __rte_always_inline struct rte_rand_state *__rte_rand_get_state(void) {lib/eal/common/rte_random.c +5
-2-unsigned int idx; +struct rte_rand_state *rand_state = &RTE_PER_LCORE (rte_rand_state); +uint64_t seed; - idx =rte_lcore_id (); + seed =__atomic_load_n (&rte_rand_seed, __ATOMIC_RELAXED); +if (unlikely (seed != rand_state->seed)) { + rand_state->seed = seed;
Quoted 12 lines
lib/eal/common/rte_random.c __rte_rand_lfsr258(struct rte_rand_state *state) · line 128
Quoted 6 lines
lib/eal/common/rte_random.c +3
-3-/* last instance reserved for unregistered non-EAL threads */ -if (unlikely (idx ==LCORE_ID_ANY )) - idx =RTE_MAX_LCORE ; + seed +=rte_thread_self ().opaque_id; +__rte_srand_lfsr258 (seed, rand_state); + }Not sure about this.
It would change the semantics ofrte_srandso that if passed the same value across multiple runs, it would still generate different values becausethread_idis not the same. Usingrte_lcore()instead would cause repeatablity but then there would still be a bug if two non-EAL threads used random.
If the non-EAL threads register themselves (and thus acquires a lcore id), they will get this kind of repeatability, provided the order of registration is the same. A "big if", no doubt.
Quoted 2 lines
Both threads would get the same sequence of numbers, but that is true with current code.
Quoted 1 line · Stephen Hemminger
Move the random number state into thread local storage.
Me and Morten discussed TLS versus other alternatives in some other thread. The downside of TLS that Morten pointed out, from what I recall, is that lazy initialization is *required* (since the number of threads is open-ended), and the data ends up in non-huge page memory. It was also unclear to me what the memory footprint implications would be, would large per-lcore data structures be put in TLS. More specifically, if they would be duplicated across all threads, even non-lcore threads.
None of these issues affect rte_random.c's potential usage of TLS (except lazy [re-]initialization makes things more complicated).
Preferably, there should be one pattern that is usable across all or at least most DPDK modules requiring per-lcore state.
Quoted 3 lines
This has a several benefits.
- no false cache sharing from cpu prefetching
- fixes initialization of random state for non-DPDK threads
This seems like a non-reason to me. That bug is easily fixed, if it isn't already.
Quoted 2 lines
- fixes unsafe usage of random state by non-DPDK threads
"Makes random number generation MT safe from all threads (including unregistered non-EAL threads)."
With current API semantics you may still register an non-EAL thread, to get MT safe access to this API, so I guess it's more about being more convenient and less error prone, than anything else.
The new MT safety guarantees should be in the API docs as well.
Quoted 47 lines
The initialization of random number state is done by the lcore (lazy initialization).
Signed-off-by Stephen Hemminger <[email protected]>--- lib/eal/common/rte_random.c | 38 +++++++++++++++++++------------------ 1 file changed, 20 insertions(+), 18 deletions(-)lib/eal/common/rte_random.c +8
-11@@ -19,13 +19,14 @@ struct rte_rand_state {uint64_t z3;uint64_t z4;uint64_t z5; -} __rte_cache_aligned; +uint64_t seed; +}; -/* One instance each for every lcore id-equipped thread, and one -* additional instance to be shared by all others threads (i.e., all -* unregistered non-EAL threads). -*/ -static struct rte_rand_state rand_states[RTE_MAX_LCORE +1 ]; +/* Global random seed */ +static uint64_t rte_rand_seed; + +/* Per lcore random state. */ +static RTE_DEFINE_PER_LCORE(struct rte_rand_state, rte_rand_state);static uint32_t __rte_rand_lcg32 (uint32_t *seed)@@ -81,11 +82,7 @@ __rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)void rte_srand (uint64_t seed) { -unsigned int lcore_id; - -/* add lcore_id to seed to avoid having the same sequence */ -for (lcore_id =0 ; lcore_id <RTE_MAX_LCORE ; lcore_id++) -__rte_srand_lfsr258 (seed + lcore_id, &rand_states[lcore_id]); +__atomic_store_n (&rte_rand_seed, seed, __ATOMIC_RELAXED); }static __rte_always_inline uint64_t
lib/eal/common/rte_random.c __rte_rand_lfsr258(struct rte_rand_state *state) · line 119
Quoted 5 lines
lib/eal/common/rte_random.c +1
-1@@ -119,15 +116,18 @@ __rte_rand_lfsr258(struct rte_rand_state *state)static __rte_always_inline struct rte_rand_state *__rte_rand_get_state(void) { -unsigned int idx; +struct rte_rand_state *rand_state = &RTE_PER_LCORE (rte_rand_state);
There should really be a RTE_PER_THREAD, an alias to RTE_PER_LCORE, to cover this usage. Or just use __thread (or _Thread_local?).
lib/eal/common/rte_random.c __rte_rand_lfsr258(struct rte_rand_state *state) · line 125
Quoted 7 lines
lib/eal/common/rte_random.c +4
-1+uint64_t seed; - idx =rte_lcore_id (); + seed =__atomic_load_n (&rte_rand_seed, __ATOMIC_RELAXED); +if (unlikely (seed != rand_state->seed)) { + rand_state->seed = seed;
Re-seeding should restart the series, on all lcores. There's nothing preventing the user from re-seeding the machinery repeatedly, with the same seed. Seems like an unusual, but still valid, use case, if you run repeated tests of some sort.
Use a seqlock? :) I guess you need a seed generation number as well (e.g., is this the first time you seed with X, or the second one, etc.)
Quoted 13 lines
lib/eal/common/rte_random.c +4
-4-/* last instance reserved for unregistered non-EAL threads */ -if (unlikely (idx ==LCORE_ID_ANY )) - idx =RTE_MAX_LCORE ; + seed +=rte_thread_self ().opaque_id; +__rte_srand_lfsr258 (seed, rand_state); + } -return &rand_states[idx]; +return rand_state; }uint64_t
lib/eal/common/rte_random.c RTE_INIT(rte_rand_init) · line 233
Quoted 8 lines
lib/eal/common/rte_random.c +3
-1@@ -227,7 +227,9 @@ RTE_INIT(rte_rand_init) {uint64_t seed; - seed =__rte_random_initial_seed (); +do + seed =__rte_random_initial_seed (); +while (seed ==0 );
Might be worth a comment why seed 0 is not allowed. Alternatively, use some other way of signaling __rte_srand_lfsr258() must be called.
Quoted 2 lines
lib/eal/common/rte_random.c +0
-0rte_srand (seed); }
Quoted 10 lines · On Wed, 6 Sep 2023 22:02:54 +0200 Mattias Rönnblom <[email protected]>…
Quoted 1 line · Stephen Hemminger
Move the random number state into thread local storage.
Me and Morten discussed TLS versus other alternatives in some other thread. The downside of TLS that Morten pointed out, from what I recall, is that lazy initialization is *required* (since the number of threads is open-ended), and the data ends up in non-huge page memory. It was also unclear to me what the memory footprint implications would be, would large per-lcore data structures be put in TLS. More specifically, if they would be duplicated across all threads, even non-lcore threads.
But current method is unsafe on non-lcore threads.
Two non-lcore threads calling rte_rand() will clash on state without any locking protection.
Also, right now the array is sized at 129 entries to allow for the maximum number of lcores. When the maximum is increased to 512 or 1024 the problem will get worse.
Quoted 14 lines · Stephen Hemminger
Quoted 10 lines · On Wed, 6 Sep 2023 22:02:54 +0200 Mattias Rönnblom <[email protected]>…
Quoted 1 line · Stephen Hemminger
Move the random number state into thread local storage.
Me and Morten discussed TLS versus other alternatives in some other thread. The downside of TLS that Morten pointed out, from what I recall, is that lazy initialization is *required* (since the number of threads is open-ended), and the data ends up in non-huge page memory. It was also unclear to me what the memory footprint implications would be, would large per-lcore data structures be put in TLS. More specifically, if they would be duplicated across all threads, even non-lcore threads.
Quoted 4 lines
But current method is unsafe on non-lcore threads.
Two non-lcore threads callingrte_rand()will clash on state without any locking protection.
Sure, just like the API docs say, although the documentation use more precise terminology.
If you want to extend the API MT safety guarantees, it should come with an argument to why this change is needed.
Is this to save the application from calling rte_thread_register() in control plane threads? For convenience? Or for being generally less error prone?
Another reason might be that the application have many threads (more than RTE_LCORE_MAX), so it will run out of lcore ids.
Quoted 3 lines
Also, right now the array is sized at 129 entries to allow for the maximum number of lcores. When the maximum is increased to 512 or 1024 the problem will get worse.
Using TLS will penalize every thread in the process, not only EAL threads and registered non-EAL threads, and worse: not only threads that are using the API in question.
Every thread will carry the TLS memory around, increasing the process memory footprint.
Thread creation will be slower, since TLS memory is allocated *and initialized*, lazy user code-level initialization or not.
On my particular Linux x86_64 system, pthread creation overhead looks something like:
8 us w/o any user code-level use of TLS
11 us w/ 16 kB of TLS
314 us w/ 2 MB of TLS.
So, whatever you put into TLS, it needs to be small.
Putting a large amount of data into TLS will effectively prevent the DPDK libraries from being linked into a heavily multi-threaded app, regardless if those threads calls into DPDK or not.
Again, this doesn't much affect rte_random.c, but does disqualify TLS as a plug-in replacement for the current pattern with a statically allocated lcore id-indexed array.
Quoted 14 lines · On Fri, 8 Sep 2023 09:04:29 +0200 Mattias Rönnblom <[email protected]>…
Quoted 3 lines
Also, right now the array is sized at 129 entries to allow for the maximum number of lcores. When the maximum is increased to 512 or 1024 the problem will get worse.
Using TLS will penalize every thread in the process, not only EAL threads and registered non-EAL threads, and worse: not only threads that are using the API in question.
Every thread will carry the TLS memory around, increasing the process memory footprint.
Thread creation will be slower, since TLS memory is allocated *and initialized*, lazy user code-level initialization or not.
Quoted 6 lines
On my particular Linux
x86_64system, pthread creation overhead looks something like:8 us w/o any user code-level use of TLS
11 us w/ 16 kB of TLS
314 us w/ 2 MB of TLS.
Agree that TLS does cause potentially more pages to get allocated on thread creation, but that argument doesn't make sense here. The rand state is small, and DPDK applications should not be creating threads after startup. Thread creation is an expensive set of system calls.
Quoted 20 lines · Stephen Hemminger
Quoted 17 lines · On Fri, 8 Sep 2023 09:04:29 +0200 Mattias Rönnblom <[email protected]>…
Quoted 3 lines
Also, right now the array is sized at 129 entries to allow for the maximum number of lcores. When the maximum is increased to 512 or 1024 the problem will get worse.
Using TLS will penalize every thread in the process, not only EAL threads and registered non-EAL threads, and worse: not only threads that are using the API in question.
Every thread will carry the TLS memory around, increasing the process memory footprint.
Thread creation will be slower, since TLS memory is allocated *and initialized*, lazy user code-level initialization or not.
On my particular Linux
x86_64system, pthread creation overhead looks something like:
Quoted 6 lines
Quoted 3 lines
8 us w/o any user code-level use of TLS
11 us w/ 16 kB of TLS
314 us w/ 2 MB of TLS.Agree that TLS does cause potentially more pages to get allocated on thread creation, but that argument doesn't make sense here.
Sure. I was talking about the general concept of replacing per-lcore static arrays with TLS.
I find the general applicability of the TLS pattern related because it doesn't make sense to have an ad-hoc, opportunistic way to implement essentially the same thing across the DPDK code base.
Quoted 3 lines
The rand
state is small, and DPDK applications should not be creating threads after startup. Thread creation is an expensive set of system calls.
I agree, and I would add that non-EAL threads will likely be few in numbers, and should all be registered on creation, to assure they can call DPDK APIs which require a lcore id.
That said, if application do create threads, DPDK shouldn't make the thread creation order of magnitudes slower.
06/09/2023 21:02, Mattias Rönnblom пишет:
Quoted 4 lines · Stephen Hemminger
Quoted 1 line
Move the random number state into thread local storage.
Me and Morten discussed TLS versus other alternatives in some other thread. The downside of TLS that Morten pointed out, from what I recall, is that lazy initialization is *required* (since the number of threads is open-ended), and the data ends up in non-huge page memory.
Hmm.. correct me if I am wrong, but with current implementation, rand state is also in non-huge memory:
static struct rte_rand_state rand_states[RTE_MAX_LCORE + 1];
Quoted 10 lines
It was also unclear to me what the memory footprint implications would be,h would large per-lcore data structures be put in TLS. More specifically, if they would be duplicated across all threads, even non-lcore threads.
None of these issues affect rte_random.c's potential usage of TLS (except lazy [re-]initialization makes things more complicated).
Preferably, there should be one pattern that is usable across all or at least most DPDK modules requiring per-lcore state.
Quoted 3 lines
This has a several benefits.
- no false cache sharing from cpu prefetching
- fixes initialization of random state for non-DPDK threads
Quoted 8 lines
This seems like a non-reason to me. That bug is easily fixed, if it isn't already.
Quoted 2 lines
- fixes unsafe usage of random state by non-DPDK threads
"Makes random number generation MT safe from all threads (including unregistered non-EAL threads)."
With current API semantics you may still register an non-EAL thread, to get MT safe access to this API, so I guess it's more about being more convenient and less error prone, than anything else.
I understand that we never guaranteed MT safety for non-EAL threads here, but as a user of rte_rand() - it would be much more convenient, if I can use it from any thread wthout worring is it a EAL thread or not.
About TlS usage and re-seeding - can we use some sort of middle-ground:
extend rte_rand_state with some gen-counter.
Make a 'master' copy of rte_rand_state that will be updated by rte_srand(), and TLS copies of rte_rand_state, so rte_rand() can fist compare its gen-counter value with master copy to decide,
does it need to copy new state from master or not.
Quoted 1 line
The new MT safety guarantees should be in the API docs as well.
Yes, it is an extension to the current API, not a fix.
Quoted 86 lines
Quoted 46 lines
The initialization of random number state is done by the lcore (lazy initialization).
Signed-off-by Stephen Hemminger <[email protected]>---
lib/eal/common/rte_random.c| 38 +++++++++++++++++++------------------1 file changed, 20 insertions(+), 18 deletions(-)lib/eal/common/rte_random.c +7
-6@@ -19,13 +19,14 @@ struct rte_rand_state { uint64_t z3; uint64_t z4; uint64_t z5; -} __rte_cache_aligned; + uint64_t seed; +}; -/* One instance each for every lcore id-equipped thread, and one -* additional instance to be shared by all others threads (i.e., all -* unregistered non-EAL threads). -*/ -static struct rte_rand_state rand_states[RTE_MAX_LCORE +1 ]; +/* Global random seed */ +static uint64_t rte_rand_seed; + +/* Per lcore random state. */ +static RTE_DEFINE_PER_LCORE(struct rte_rand_state, rte_rand_state);static
uint32_t
__rte_rand_lcg32(uint32_t *seed)lib/eal/common/rte_random.c +0
-0@@ -81,11 +82,7 @@ __rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)void
rte_srand(uint64_t seed)
{
- unsigned intlcore_id;
-
- /* addlcore_idto seed to avoid having the same sequence */ - for (lcore_id= 0;lcore_id<RTE_MAX_LCORE; lcore_id++) -__rte_srand_lfsr258(seed + lcore_id, &rand_states[lcore_id]); +__atomic_store_n(&rte_rand_seed, seed, __ATOMIC_RELAXED); }
static__rte_always_inlineuint64_tlib/eal/common/rte_random.c +0
-0@@ -119,15 +116,18 @@ __rte_rand_lfsr258(struct rte_rand_state *state)Quoted 5 lines
static
__rte_always_inline
structrte_rand_state*__rte_rand_get_state(void)
{
- unsigned int idx;
+ structrte_rand_state*rand_state=&RTE_PER_LCORE(rte_rand_state);There should really be a
RTE_PER_THREAD, an alias toRTE_PER_LCORE, to cover this usage. Or just use__thread(or_Thread_local?).Quoted 5 lines
+
uint64_tseed;
- idx =rte_lcore_id();
+ seed =__atomic_load_n(&rte_rand_seed, __ATOMIC_RELAXED); + if (unlikely(seed != rand_state->seed)) {
+rand_state->seed= seed;Re-seeding should restart the series, on all lcores. There's nothing preventing the user from re-seeding the machinery repeatedly, with the same seed. Seems like an unusual, but still valid, use case, if you run repeated tests of some sort.
Use a seqlock? :) I guess you need a seed generation number as well (e.g., is this the first time you seed with X, or the second one, etc.)
Quoted 11 lines
- /* last instance reserved for unregistered non-EAL threads */ - if (
unlikely(idx == LCORE_ID_ANY))
- idx =RTE_MAX_LCORE;
+ seed += rte_thread_self().opaque_id;
+__rte_srand_lfsr258(seed, rand_state);
+ }
- return &rand_states[idx];
+ returnrand_state;
}
uint64_tlib/eal/common/rte_random.c RTE_INIT(rte_rand_init) · line 231
Quoted 6 lines
lib/eal/common/rte_random.c +3
-1@@ -227,7 +227,9 @@ RTE_INIT(rte_rand_init) { uint64_t seed; - seed = __rte_random_initial_seed(); + do + seed = __rte_random_initial_seed(); + while (seed == 0);Might be worth a comment why seed 0 is not allowed. Alternatively, use some other way of signaling
__rte_srand_lfsr258()must be called.Quoted 2 lines
lib/eal/common/rte_random.c +0
-0rte_srand(seed); }
Quoted 10 lines · Konstantin Ananyev
06/09/2023 21:02, Mattias Rönnblom пишет:
Quoted 4 lines · Stephen Hemminger
Quoted 1 line
Move the random number state into thread local storage.
Me and Morten discussed TLS versus other alternatives in some other thread. The downside of TLS that Morten pointed out, from what I recall, is that lazy initialization is *required* (since the number of threads is open-ended), and the data ends up in non-huge page memory.
Hmm.. correct me if I am wrong, but with current implementation, rand state is also in non-huge memory:
static structrte_rand_staterand_states[RTE_MAX_LCORE + 1];
Yes. The current pattern is certainly not perfect.
Quoted 13 lines
Quoted 13 lines
It was also unclear to me what the memory footprint implications would be,h would large per-lcore data structures be put in TLS. More specifically, if they would be duplicated across all threads, even non-lcore threads.
None of these issues affect rte_random.c's potential usage of TLS (except lazy [re-]initialization makes things more complicated).
Preferably, there should be one pattern that is usable across all or at least most DPDK modules requiring per-lcore state.
Quoted 3 lines
This has a several benefits.
- no false cache sharing from cpu prefetching
- fixes initialization of random state for non-DPDK threadsThis seems like a non-reason to me. That bug is easily fixed, if it isn't already.
Quoted 8 lines
Quoted 6 lines
Quoted 2 lines
- fixes unsafe usage of random state by non-DPDK threads
"Makes random number generation MT safe from all threads (including unregistered non-EAL threads)."
With current API semantics you may still register an non-EAL thread, to get MT safe access to this API, so I guess it's more about being more convenient and less error prone, than anything else.
I understand that we never guaranteed MT safety for non-EAL threads here,
Registered non-EAL threads have a lcore id and thus may safely call rte_rand(). Multiple unregistered non-EAL threads may not do so, in parallel.
Quoted 2 lines
but as a user of
rte_rand()- it would be much more convenient, if I can use it from any thread wthout worring is it a EAL thread or not.
Sure, especially if it comes for free. The for-free solution has yet to reveal itself though.
Quoted 8 lines
About TlS usage and re-seeding - can we use some sort of middle-ground:
extendrte_rand_statewith some gen-counter.
Make a 'master' copy ofrte_rand_statethat will be updated byrte_srand(), and TLS copies ofrte_rand_state, sorte_rand()can fist compare its gen-counter value with master copy to decide,
does it need to copy new state from master or not.
Calling threads shouldn't all produce the same sequence. That would be silly and not very random. The generation number should be tied to the seed.
Quoted 92 lines
Quoted 2 lines
The new MT safety guarantees should be in the API docs as well.
Yes, it is an extension to the current API, not a fix.
Quoted 86 lines
Quoted 46 lines
The initialization of random number state is done by the lcore (lazy initialization).
Signed-off-by Stephen Hemminger <[email protected]>---
lib/eal/common/rte_random.c| 38 +++++++++++++++++++------------------1 file changed, 20 insertions(+), 18 deletions(-)lib/eal/common/rte_random.c +7
-6@@ -19,13 +19,14 @@ struct rte_rand_state { uint64_t z3; uint64_t z4; uint64_t z5; -} __rte_cache_aligned; + uint64_t seed; +}; -/* One instance each for every lcore id-equipped thread, and one -* additional instance to be shared by all others threads (i.e., all -* unregistered non-EAL threads). -*/ -static struct rte_rand_state rand_states[RTE_MAX_LCORE +1 ]; +/* Global random seed */ +static uint64_t rte_rand_seed; + +/* Per lcore random state. */ +static RTE_DEFINE_PER_LCORE(struct rte_rand_state, rte_rand_state);static
uint32_t
__rte_rand_lcg32(uint32_t *seed)lib/eal/common/rte_random.c +0
-0@@ -81,11 +82,7 @@ __rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)void
rte_srand(uint64_t seed)
{
- unsigned intlcore_id;
-
- /* addlcore_idto seed to avoid having the same sequence */ - for (lcore_id= 0;lcore_id<RTE_MAX_LCORE; lcore_id++) -__rte_srand_lfsr258(seed + lcore_id, &rand_states[lcore_id]); +__atomic_store_n(&rte_rand_seed, seed, __ATOMIC_RELAXED); }
static__rte_always_inlineuint64_tlib/eal/common/rte_random.c +0
-0@@ -119,15 +116,18 @@ __rte_rand_lfsr258(struct rte_rand_state *state)Quoted 5 lines
static
__rte_always_inline
structrte_rand_state*__rte_rand_get_state(void)
{
- unsigned int idx;
+ structrte_rand_state*rand_state=&RTE_PER_LCORE(rte_rand_state);There should really be a
RTE_PER_THREAD, an alias toRTE_PER_LCORE, to cover this usage. Or just use__thread(or_Thread_local?).Quoted 5 lines
+
uint64_tseed;
- idx =rte_lcore_id();
+ seed =__atomic_load_n(&rte_rand_seed, __ATOMIC_RELAXED); + if (unlikely(seed != rand_state->seed)) {
+rand_state->seed= seed;Re-seeding should restart the series, on all lcores. There's nothing preventing the user from re-seeding the machinery repeatedly, with the same seed. Seems like an unusual, but still valid, use case, if you run repeated tests of some sort.
Use a seqlock? :) I guess you need a seed generation number as well (e.g., is this the first time you seed with X, or the second one, etc.)
Quoted 11 lines
- /* last instance reserved for unregistered non-EAL threads */ - if (
unlikely(idx == LCORE_ID_ANY))
- idx =RTE_MAX_LCORE;
+ seed += rte_thread_self().opaque_id;
+__rte_srand_lfsr258(seed, rand_state);
+ }
- return &rand_states[idx];
+ returnrand_state;
}
uint64_tlib/eal/common/rte_random.c RTE_INIT(rte_rand_init) · line 231
Quoted 6 lines
lib/eal/common/rte_random.c +3
-1@@ -227,7 +227,9 @@ RTE_INIT(rte_rand_init) { uint64_t seed; - seed = __rte_random_initial_seed(); + do + seed = __rte_random_initial_seed(); + while (seed == 0);Might be worth a comment why seed 0 is not allowed. Alternatively, use some other way of signaling
__rte_srand_lfsr258()must be called.Quoted 2 lines
lib/eal/common/rte_random.c +0
-0rte_srand(seed); }
Quoted 60 lines
From: Mattias Rönnblom [mailto:[email protected]]
Sent: Saturday, 9 September 2023 08.45Quoted 7 lines · Konstantin Ananyev
06/09/2023 21:02, Mattias Rönnblom пишет:
Quoted 6 lines · Stephen Hemminger
Quoted 1 line
Move the random number state into thread local storage.
Me and Morten discussed TLS versus other alternatives in some other thread. The downside of TLS that Morten pointed out, from what I recall, is that lazy initialization is *required* (since the number
of
Quoted 6 lines
Quoted 1 line
threads is open-ended), and the data ends up in non-huge page memory.
Hmm.. correct me if I am wrong, but with current implementation, rand state is also in non-huge memory:
static structrte_rand_staterand_states[RTE_MAX_LCORE + 1];Yes. The current pattern is certainly not perfect.
Quoted 2 lines
Quoted 2 lines
It was also unclear to me what the memory footprint implications
would
Quoted 20 lines
Quoted 20 lines
be,h would large per-lcore data structures be put in TLS. More specifically, if they would be duplicated across all threads, even non-lcore threads.
None of these issues affect rte_random.c's potential usage of TLS (except lazy [re-]initialization makes things more complicated).
Preferably, there should be one pattern that is usable across all or at least most DPDK modules requiring per-lcore state.
Quoted 3 lines
This has a several benefits.
- no false cache sharing from cpu prefetching
- fixes initialization of random state for non-DPDK threadsThis seems like a non-reason to me. That bug is easily fixed, if it isn't already.
Quoted 2 lines
- fixes unsafe usage of random state by non-DPDK threads
Quoted 8 lines
Quoted 6 lines
"Makes random number generation MT safe from all threads (including unregistered non-EAL threads)."
With current API semantics you may still register an non-EAL thread, to get MT safe access to this API, so I guess it's more about being more convenient and less error prone, than anything else.
I understand that we never guaranteed MT safety for non-EAL threads
here,
Registered non-EAL threads have a lcore id and thus may safely call
rte_rand(). Multiple unregistered non-EAL threads may not do so, in parallel.
Quoted 7 lines
Quoted 1 line
but as a user of
rte_rand()- it would be much more convenient, if Ican
Quoted 2 lines
use it
from any thread wthout worring is it a EAL thread or not.Sure, especially if it comes for free. The for-free solution has yet to reveal itself though.
We could offer re-entrant function variants for non-EAL threads:
uint64_t rte_rand_r(struct rte_rand_state * const state);
void rte_srand_r(struct rte_rand_state * const state, uint64_t seed); uint64_t rte_rand_max_r(struct rte_rand_state * const state, uint64_t upper_bound); double rte_drand_r(struct rte_rand_state * const state, void);
For this to work, we would have to make struct rte_rand_state public, and the application would need to allocate it. (At least one instance per thread that uses it, obviously.)
Quoted 7 lines
Quoted 3 lines
About TlS usage and re-seeding - can we use some sort of middle-
ground:
Quoted 2 lines
extend
rte_rand_statewith some gen-counter.
Make a 'master' copy ofrte_rand_statethat will be updated by
rte_srand(),
Quoted 8 lines
Quoted 4 lines
and TLS copies of
rte_rand_state, sorte_rand()can fist compare its gen-counter value with master copy to decide,
does it need to copy new state from master or not.Calling threads shouldn't all produce the same sequence. That would be silly and not very random. The generation number should be tied to the seed.
I previously thought about seeding...
We are trying to be random, we are not explicitly pseudo-random.
So I came to the conclusion that the ability to reproduce data (typically for verification purposes) is not a requirement here.
Quoted 109 lines
Quoted 13 lines
Quoted 3 lines
The new MT safety guarantees should be in the API docs as well.
Yes, it is an extension to the current API, not a fix.
Quoted 7 lines
Quoted 7 lines
The initialization of random number state is done by the lcore (lazy initialization).
Signed-off-by Stephen Hemminger <[email protected]>---
lib/eal/common/rte_random.c| 38 +++++++++++++++++++------------------
Quoted 3 lines
Quoted 3 lines
Review
Quoted 3 lines
1 file changed, 20 insertions(+), 18 deletions(-)(quoted diff) +0
-0
b/lib/eal/common/rte_random.cQuoted 4 lines
Quoted 4 lines
Quoted 4 lines
index
53636331a27b..9657adf6ad3b100644lib/eal/common/rte_random.c +0
-0@@ -19,13 +19,14 @@ struct rte_rand_state {Quoted 8 lines
Quoted 8 lines
lib/eal/common/rte_random.c struct rte_rand_state {
Quoted 8 lines
lib/eal/common/rte_random.c +2
-3uint64_t z3; uint64_t z4; uint64_t z5; -} __rte_cache_aligned; + uint64_t seed; +}; -/* One instance each for every lcore id-equipped thread, and one -* additional instance to be shared by all others threads (i.e., all
Quoted 12 lines
Quoted 12 lines
Quoted 12 lines
lib/eal/common/rte_random.c +5
-3-* unregistered non-EAL threads). -*/ -static struct rte_rand_state rand_states[RTE_MAX_LCORE +1 ]; +/* Global random seed */ +static uint64_t rte_rand_seed; + +/* Per lcore random state. */ +static RTE_DEFINE_PER_LCORE(struct rte_rand_state, rte_rand_state);static
uint32_t
__rte_rand_lcg32(uint32_t *seed)lib/eal/common/rte_random.c +0
-0@@ -81,11 +82,7 @@ __rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
void
rte_srand(uint64_t seed)
{
- unsigned intlcore_id;
-
- /* addlcore_idto seed to avoid having the same sequence */ - for (lcore_id= 0;lcore_id<RTE_MAX_LCORE; lcore_id++) - __rte_srand_lfsr258(seed +lcore_id,&rand_states[lcore_id]);
Quoted 4 lines
Quoted 4 lines
lib/eal/common/rte_random.c __rte_rand_lfsr258(struct rte_rand_state
Quoted 4 lines
+
__atomic_store_n(&rte_rand_seed, seed, __ATOMIC_RELAXED); }
static__rte_always_inlineuint64_tlib/eal/common/rte_random.c +0
-0@@ -119,15 +116,18 @@ __rte_rand_lfsr258(struct rte_rand_state*state)
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
static
__rte_always_inline
structrte_rand_state*__rte_rand_get_state(void){
- unsigned int idx;
+ structrte_rand_state*rand_state=
&RTE_PER_LCORE(rte_rand_state);Quoted 2 lines
Quoted 2 lines
There should really be a
RTE_PER_THREAD, an alias toRTE_PER_LCORE,to
Quoted 10 lines
Quoted 10 lines
cover this usage. Or just use
__thread(or_Thread_local?).Quoted 5 lines
+
uint64_tseed;
- idx =rte_lcore_id();
+ seed =__atomic_load_n(&rte_rand_seed, __ATOMIC_RELAXED); + if (unlikely(seed != rand_state->seed)) {
+rand_state->seed= seed;Re-seeding should restart the series, on all lcores. There's nothing preventing the user from re-seeding the machinery repeatedly, with
the
Quoted 5 lines
Quoted 5 lines
same seed. Seems like an unusual, but still valid, use case, if you run repeated tests of some sort.
Use a seqlock? :) I guess you need a seed generation number as well (e.g., is this the first time you seed with X, or the second one,
etc.)
Quoted 12 lines
Quoted 12 lines
Quoted 12 lines
- /* last instance reserved for unregistered non-EAL threads */ - if (
unlikely(idx == LCORE_ID_ANY))
- idx =RTE_MAX_LCORE;
+ seed += rte_thread_self().opaque_id;
+__rte_srand_lfsr258(seed, rand_state);
+ }
- return &rand_states[idx];
+ returnrand_state;
}
uint64_tlib/eal/common/rte_random.c +0
-0@@ -227,7 +227,9 @@ RTE_INIT(rte_rand_init)Quoted 8 lines
Quoted 8 lines
lib/eal/common/rte_random.c RTE_INIT(rte_rand_init) · line 232
Quoted 6 lines
lib/eal/common/rte_random.c +3
-1{ uint64_t seed; - seed = __rte_random_initial_seed(); + do + seed = __rte_random_initial_seed(); + while (seed == 0);Might be worth a comment why seed 0 is not allowed. Alternatively,
use
Quoted 5 lines
Quoted 4 lines
some other way of signaling
__rte_srand_lfsr258()must be called.Quoted 2 lines
lib/eal/common/rte_random.c +0
-0rte_srand(seed); }
Quoted 68 lines · Morten Brørup
Quoted 60 lines
From: Mattias Rönnblom [mailto:[email protected]]
Sent: Saturday, 9 September 2023 08.45Quoted 7 lines · Konstantin Ananyev
06/09/2023 21:02, Mattias Rönnblom пишет:
Quoted 6 lines · Stephen Hemminger
Quoted 1 line
Move the random number state into thread local storage.
Me and Morten discussed TLS versus other alternatives in some other thread. The downside of TLS that Morten pointed out, from what I recall, is that lazy initialization is *required* (since the number
of
Quoted 6 lines
Quoted 1 line
threads is open-ended), and the data ends up in non-huge page memory.
Hmm.. correct me if I am wrong, but with current implementation, rand state is also in non-huge memory:
static structrte_rand_staterand_states[RTE_MAX_LCORE + 1];Yes. The current pattern is certainly not perfect.
Quoted 2 lines
Quoted 2 lines
It was also unclear to me what the memory footprint implications
would
Quoted 20 lines
Quoted 20 lines
be,h would large per-lcore data structures be put in TLS. More specifically, if they would be duplicated across all threads, even non-lcore threads.
None of these issues affect rte_random.c's potential usage of TLS (except lazy [re-]initialization makes things more complicated).
Preferably, there should be one pattern that is usable across all or at least most DPDK modules requiring per-lcore state.
Quoted 3 lines
This has a several benefits.
- no false cache sharing from cpu prefetching
- fixes initialization of random state for non-DPDK threadsThis seems like a non-reason to me. That bug is easily fixed, if it isn't already.
Quoted 2 lines
- fixes unsafe usage of random state by non-DPDK threads
Quoted 8 lines
Quoted 6 lines
"Makes random number generation MT safe from all threads (including unregistered non-EAL threads)."
With current API semantics you may still register an non-EAL thread, to get MT safe access to this API, so I guess it's more about being more convenient and less error prone, than anything else.
I understand that we never guaranteed MT safety for non-EAL threads
here,
Registered non-EAL threads have a lcore id and thus may safely call
rte_rand(). Multiple unregistered non-EAL threads may not do so, in parallel.Quoted 7 lines
Quoted 1 line
but as a user of
rte_rand()- it would be much more convenient, if Ican
Quoted 2 lines
use it
from any thread wthout worring is it a EAL thread or not.Sure, especially if it comes for free. The for-free solution has yet to reveal itself though.
Quoted 9 lines
We could offer re-entrant function variants for non-EAL threads:
uint64_trte_rand_r(struct rte_rand_state * const state);
voidrte_srand_r(struct rte_rand_state * const state, uint64_t seed);uint64_trte_rand_max_r(struct rte_rand_state * const state, uint64_t upper_bound); doublerte_drand_r(struct rte_rand_state * const state, void);For this to work, we would have to make struct
rte_rand_statepublic, and the application would need to allocate it. (At least one instance per thread that uses it, obviously.)
Yes, and that will come at a pretty severe API complexity cost.
Besides the obvious complexities, it may also lead the user to believe the rte_rand() is not MT safe for any thread, since that's how it works in glibc (rand() versus rand_r()).
Quoted 131 lines
Quoted 7 lines
Quoted 3 lines
About TlS usage and re-seeding - can we use some sort of middle-
ground:
Quoted 2 lines
extend
rte_rand_statewith some gen-counter.
Make a 'master' copy ofrte_rand_statethat will be updated by
rte_srand(),Quoted 8 lines
Quoted 4 lines
and TLS copies of
rte_rand_state, sorte_rand()can fist compare its gen-counter value with master copy to decide,
does it need to copy new state from master or not.Calling threads shouldn't all produce the same sequence. That would be silly and not very random. The generation number should be tied to the seed.
I previously thought about seeding...
We are trying to be random, we are not explicitly pseudo-random.
So I came to the conclusion that the ability to reproduce data (typically for verification purposes) is not a requirement here.
Quoted 109 lines
Quoted 13 lines
Quoted 3 lines
The new MT safety guarantees should be in the API docs as well.
Yes, it is an extension to the current API, not a fix.
Quoted 7 lines
Quoted 7 lines
The initialization of random number state is done by the lcore (lazy initialization).
Signed-off-by Stephen Hemminger <[email protected]>--- lib/eal/common/rte_random.c | 38 +++++++++++++++++++------------------
Quoted 3 lines
Quoted 3 lines
Review
Quoted 3 lines
1 file changed, 20 insertions(+), 18 deletions(-)(quoted diff) +0
-0
b/lib/eal/common/rte_random.cQuoted 4 lines
Quoted 4 lines
Quoted 4 lines
index
53636331a27b..9657adf6ad3b100644lib/eal/common/rte_random.c +0
-0@@ -19,13 +19,14 @@ struct rte_rand_state {Quoted 8 lines
Quoted 8 lines
lib/eal/common/rte_random.c struct rte_rand_state {
Quoted 8 lines
lib/eal/common/rte_random.c +2
-3uint64_t z3; uint64_t z4; uint64_t z5; -} __rte_cache_aligned; + uint64_t seed; +}; -/* One instance each for every lcore id-equipped thread, and one -* additional instance to be shared by all others threads (i.e., all
Quoted 12 lines
Quoted 12 lines
Quoted 12 lines
lib/eal/common/rte_random.c +5
-3-* unregistered non-EAL threads). -*/ -static struct rte_rand_state rand_states[RTE_MAX_LCORE +1 ]; +/* Global random seed */ +static uint64_t rte_rand_seed; + +/* Per lcore random state. */ +static RTE_DEFINE_PER_LCORE(struct rte_rand_state, rte_rand_state); static uint32_t __rte_rand_lcg32(uint32_t *seed)@@ -81,11 +82,7 @@ __rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)Quoted 8 lines
Quoted 8 lines
lib/eal/common/rte_random.c __rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)
Quoted 8 lines
lib/eal/common/rte_random.c +0
-5void rte_srand(uint64_t seed) { - unsigned int lcore_id; - - /* add lcore_id to seed to avoid having the same sequence */ - for (lcore_id = 0; lcore_id < RTE_MAX_LCORE; lcore_id++) - __rte_srand_lfsr258(seed + lcore_id,&rand_states[lcore_id]);
Quoted 4 lines
Quoted 4 lines
lib/eal/common/rte_random.c __rte_rand_lfsr258(struct rte_rand_state
Quoted 4 lines
lib/eal/common/rte_random.c +1
-0+ __atomic_store_n(&rte_rand_seed, seed, __ATOMIC_RELAXED); } static __rte_always_inline uint64_t@@ -119,15 +116,18 @@ __rte_rand_lfsr258(struct rte_rand_state*state)
Quoted 5 lines
Quoted 5 lines
lib/eal/common/rte_random.c __rte_rand_lfsr258(struct rte_rand_state *state)
Quoted 5 lines
lib/eal/common/rte_random.c +1
-1static __rte_always_inline struct rte_rand_state *__rte_rand_get_state(void) { - unsigned int idx; + struct rte_rand_state *rand_state =
&RTE_PER_LCORE(rte_rand_state);Quoted 2 lines
Quoted 2 lines
There should really be a
RTE_PER_THREAD, an alias toRTE_PER_LCORE,to
Quoted 10 lines
Quoted 10 lines
cover this usage. Or just use
__thread(or_Thread_local?).lib/eal/common/rte_random.c __rte_rand_lfsr258(struct rte_rand_state *state) · line 124
Quoted 5 lines
lib/eal/common/rte_random.c +4
-1+ uint64_t seed; - idx = rte_lcore_id(); + seed = __atomic_load_n(&rte_rand_seed, __ATOMIC_RELAXED); + if (unlikely(seed != rand_state->seed)) { + rand_state->seed = seed;Re-seeding should restart the series, on all lcores. There's nothing preventing the user from re-seeding the machinery repeatedly, with
the
Quoted 5 lines
Quoted 5 lines
same seed. Seems like an unusual, but still valid, use case, if you run repeated tests of some sort.
Use a seqlock? :) I guess you need a seed generation number as well (e.g., is this the first time you seed with X, or the second one,
etc.)
Quoted 12 lines
Quoted 12 lines
Quoted 12 lines
lib/eal/common/rte_random.c +4
-4- /* last instance reserved for unregistered non-EAL threads */ - if (unlikely(idx == LCORE_ID_ANY)) - idx = RTE_MAX_LCORE; + seed += rte_thread_self().opaque_id; + __rte_srand_lfsr258(seed, rand_state); + } - return &rand_states[idx]; + return rand_state; } uint64_t@@ -227,7 +227,9 @@ RTE_INIT(rte_rand_init)Quoted 8 lines
Quoted 8 lines
lib/eal/common/rte_random.c RTE_INIT(rte_rand_init) · line 232
Quoted 6 lines
lib/eal/common/rte_random.c +3
-1{ uint64_t seed; - seed = __rte_random_initial_seed(); + do + seed = __rte_random_initial_seed(); + while (seed == 0);Might be worth a comment why seed 0 is not allowed. Alternatively,
use
Quoted 5 lines
Quoted 4 lines
some other way of signaling
__rte_srand_lfsr258()must be called.Quoted 2 lines
lib/eal/common/rte_random.c +0
-0rte_srand(seed); }
Quoted 10 lines · On Mon, 11 Sep 2023 11:00:46 +0200 Mattias Rönnblom <[email protected]>…
Quoted 9 lines
uint64_trte_rand_r(struct rte_rand_state * const state); voidrte_srand_r(struct rte_rand_state * const state, uint64_t seed);uint64_trte_rand_max_r(struct rte_rand_state * const state, uint64_t upper_bound); doublerte_drand_r(struct rte_rand_state * const state, void);For this to work, we would have to make struct
rte_rand_statepublic, and the application would need to allocate it. (At least one instance per thread that uses it, obviously.)
Quoted 5 lines
Yes, and that will come at a pretty severe API complexity cost.
Besides the obvious complexities, it may also lead the user to believe the
rte_rand()is not MT safe for any thread, since that's how it works in glibc (rand()versusrand_r()).
Actual rand state implementation could be hidden by having an allocation/create/new function.
Quoted 6 lines · On Sat, 9 Sep 2023 08:45:17 +0200 Mattias Rönnblom <[email protected]>…
Quoted 4 lines
Hmm.. correct me if I am wrong, but with current implementation, rand state is also in non-huge memory:
static structrte_rand_staterand_states[RTE_MAX_LCORE + 1];Yes. The current pattern is certainly not perfect.
There is no good reason to put it in hugepage memory. In fact, hugepage memory is a limited resource and you do want different rand_states for primary and secondary processes.
09/09/2023 07:45, Mattias Rönnblom пишет:
Quoted 30 lines · Konstantin Ananyev
Quoted 10 lines
06/09/2023 21:02, Mattias Rönnblom пишет:
Quoted 4 lines · Stephen Hemminger
Quoted 1 line
Move the random number state into thread local storage.
Me and Morten discussed TLS versus other alternatives in some other thread. The downside of TLS that Morten pointed out, from what I recall, is that lazy initialization is *required* (since the number of threads is open-ended), and the data ends up in non-huge page memory.
Hmm.. correct me if I am wrong, but with current implementation, rand state is also in non-huge memory:
static structrte_rand_staterand_states[RTE_MAX_LCORE + 1];Yes. The current pattern is certainly not perfect.
Quoted 16 lines
Quoted 16 lines
It was also unclear to me what the memory footprint implications would be,h would large per-lcore data structures be put in TLS. More specifically, if they would be duplicated across all threads, even non-lcore threads.
None of these issues affect rte_random.c's potential usage of TLS (except lazy [re-]initialization makes things more complicated).
Preferably, there should be one pattern that is usable across all or at least most DPDK modules requiring per-lcore state.
Quoted 3 lines
This has a several benefits.
- no false cache sharing from cpu prefetching
- fixes initialization of random state for non-DPDK threadsThis seems like a non-reason to me. That bug is easily fixed, if it isn't already.
Quoted 2 lines
- fixes unsafe usage of random state by non-DPDK threads
Quoted 8 lines
Quoted 5 lines
Quoted 3 lines
"Makes random number generation MT safe from all threads (including unregistered non-EAL threads)."
With current API semantics you may still register an non-EAL thread, to get MT safe access to this API, so I guess it's more about being more convenient and less error prone, than anything else.
I understand that we never guaranteed MT safety for non-EAL threads here,
Registered non-EAL threads have a lcore id and thus may safely call
rte_rand().
I am aware about such ability, but for me register/unregister thread just to call rte_rand() seems like way too much hassle.
Quoted 17 lines
Multiple unregistered non-EAL threads may not do so, in parallel.
Quoted 2 lines
but as a user of
rte_rand()- it would be much more convenient, if I can use it from any thread wthout worring is it a EAL thread or not.Sure, especially if it comes for free. The for-free solution has yet to reveal itself though.
Quoted 8 lines
About TlS usage and re-seeding - can we use some sort of middle-ground:
extendrte_rand_statewith some gen-counter.
Make a 'master' copy ofrte_rand_statethat will be updated byrte_srand(), and TLS copies ofrte_rand_state, sorte_rand()can fist compare its gen-counter value with master copy to decide,
does it need to copy new state from master or not.
Quoted 1 line
Calling threads shouldn't all produce the same sequence. That would be silly and not very random. The generation number should be tied to the seed.
Actually, yes you right, probably we don't need a master copy of rte_rand_state itself. It seems that just having a 'master' copy of 'seed' value, plus some counter (to indicate that seed has been updated) is enough here.
Quoted 95 lines
Quoted 95 lines
Quoted 3 lines
The new MT safety guarantees should be in the API docs as well.
Yes, it is an extension to the current API, not a fix.
Quoted 88 lines
Quoted 47 lines
The initialization of random number state is done by the lcore (lazy initialization).
Signed-off-by Stephen Hemminger <[email protected]>---
lib/eal/common/rte_random.c| 38
+++++++++++++++++++------------------1 file changed, 20 insertions(+), 18 deletions(-)lib/eal/common/rte_random.c +7
-6@@ -19,13 +19,14 @@ struct rte_rand_state { uint64_t z3; uint64_t z4; uint64_t z5; -} __rte_cache_aligned; + uint64_t seed; +}; -/* One instance each for every lcore id-equipped thread, and one -* additional instance to be shared by all others threads (i.e., all -* unregistered non-EAL threads). -*/ -static struct rte_rand_state rand_states[RTE_MAX_LCORE +1 ]; +/* Global random seed */ +static uint64_t rte_rand_seed; + +/* Per lcore random state. */ +static RTE_DEFINE_PER_LCORE(struct rte_rand_state, rte_rand_state);static
uint32_t
__rte_rand_lcg32(uint32_t *seed)lib/eal/common/rte_random.c +0
-0@@ -81,11 +82,7 @@ __rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)void
rte_srand(uint64_t seed)
{
- unsigned intlcore_id;
-
- /* addlcore_idto seed to avoid having the same sequence */ - for (lcore_id= 0;lcore_id<RTE_MAX_LCORE; lcore_id++) -__rte_srand_lfsr258(seed + lcore_id, &rand_states[lcore_id]); +__atomic_store_n(&rte_rand_seed, seed, __ATOMIC_RELAXED); }
static__rte_always_inlineuint64_tlib/eal/common/rte_random.c +0
-0@@ -119,15 +116,18 @@ __rte_rand_lfsr258(struct rte_rand_state *state)Quoted 6 lines
static
__rte_always_inline
structrte_rand_state*__rte_rand_get_state(void){
- unsigned int idx;
+ structrte_rand_state*rand_state=&RTE_PER_LCORE(rte_rand_state);There should really be a
RTE_PER_THREAD, an alias toRTE_PER_LCORE, to cover this usage. Or just use__thread(or_Thread_local?).Quoted 5 lines
+
uint64_tseed;
- idx =rte_lcore_id();
+ seed =__atomic_load_n(&rte_rand_seed, __ATOMIC_RELAXED); + if (unlikely(seed != rand_state->seed)) {
+rand_state->seed= seed;Re-seeding should restart the series, on all lcores. There's nothing preventing the user from re-seeding the machinery repeatedly, with the same seed. Seems like an unusual, but still valid, use case, if you run repeated tests of some sort.
Use a seqlock? :) I guess you need a seed generation number as well (e.g., is this the first time you seed with X, or the second one, etc.)
Quoted 11 lines
- /* last instance reserved for unregistered non-EAL threads */ - if (
unlikely(idx == LCORE_ID_ANY))
- idx =RTE_MAX_LCORE;
+ seed += rte_thread_self().opaque_id;
+__rte_srand_lfsr258(seed, rand_state);
+ }
- return &rand_states[idx];
+ returnrand_state;
}
uint64_tlib/eal/common/rte_random.c RTE_INIT(rte_rand_init) · line 231
Quoted 6 lines
lib/eal/common/rte_random.c +3
-1@@ -227,7 +227,9 @@ RTE_INIT(rte_rand_init) { uint64_t seed; - seed = __rte_random_initial_seed(); + do + seed = __rte_random_initial_seed(); + while (seed == 0);Might be worth a comment why seed 0 is not allowed. Alternatively, use some other way of signaling
__rte_srand_lfsr258()must be called.Quoted 2 lines
lib/eal/common/rte_random.c +0
-0rte_srand(seed); }