random: avoid init'ing twice in credit race
Jason A. Donenfeld
maintainerPATCH 1/2 random: avoid init'ing twice in credit race
Since all changes of crng_init now go through credit_init_bits(), we can fix a long standing race in which two concurrent callers of credit_init_bits() have the new bit count >= some threshold, but are doing so with crng_init as a lower threshold, checked outside of a lock, resulting in crng_reseed() or similar being called twice.
In order to fix this, we can use the original cmpxchg value of the bit count, and only change crng_init when the bit count transitions from below a threshold to meeting the threshold.
--- drivers/char/random.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)
drivers/char/random.c +5 -5
@@ -823,7 +823,7 @@ static void extract_entropy(void *buf, size_t nbytes)static void credit_init_bits (size_t nbits) { -unsigned int init_bits, orig, add; +unsigned int new, orig, add;unsigned long flags;if (crng_ready () || !nbits)
@@ -833,12 +833,12 @@ static void credit_init_bits(size_t nbits)do { orig =READ_ONCE (input_pool.init_bits); - init_bits = min_t(unsigned int, POOL_BITS, orig + add); - }while (cmpxchg (&input_pool.init_bits, orig, init_bits) != orig); + new = min_t(unsigned int, POOL_BITS, orig + add); + }while (cmpxchg (&input_pool.init_bits, orig, new) != orig); -if (!crng_ready () && init_bits >=POOL_READY_BITS ) +if (orig <POOL_READY_BITS && new >=POOL_READY_BITS )crng_reseed (); -else if (unlikely (crng_init ==CRNG_EMPTY && init_bits >=POOL_EARLY_BITS )) { +else if (orig <POOL_EARLY_BITS && new >=POOL_EARLY_BITS ) {spin_lock_irqsave (&base_crng.lock, flags);if (crng_init ==CRNG_EMPTY ) {extract_entropy (base_crng.key,sizeof (base_crng.key));
Signature · 1 line
2.35.1
Jason A. Donenfeld
maintainerPATCH 2/2 random: move initialization out of reseeding hot path
Initialization happens once -- by way of credit_init_bits() -- and then it never happens again. Therefore, it doesn't need to be in crng_reseed(), which is a hot path that is called multiple times. It also doesn't make sense to have there, as initialization activity is better associated with initialization routines.
After the prior commit, crng_reseed() now won't be called by multiple concurrent callers, which means that we can safely move the "finialize_init" logic into crng_init_bits() unconditionally.
--- drivers/char/random.c | 43 +++++++++++++++++++------------------------ 1 file changed, 19 insertions(+), 24 deletions(-)
drivers/char/random.c +19 -24
@@ -266,7 +266,6 @@ static void crng_reseed(void)unsigned long flags;unsigned long next_gen;u8 key[CHACHA_KEY_SIZE ]; -bool finalize_init = false;extract_entropy (key,sizeof (key));
@@ -283,28 +282,9 @@ static void crng_reseed(void) ++next_gen;WRITE_ONCE (base_crng.generation, next_gen);WRITE_ONCE (base_crng.birth, jiffies); -if (!crng_ready ()) { - crng_init =CRNG_READY ; - finalize_init = true; - } + crng_init =CRNG_READY ;spin_unlock_irqrestore (&base_crng.lock, flags);memzero_explicit (key,sizeof (key)); -if (finalize_init) { -process_random_ready_list (); -wake_up_interruptible (&crng_init_wait); -kill_fasync (&fasync,SIGIO ,POLL_IN ); -pr_notice ("crng init done\n" ); -if (unseeded_warning.missed) { -pr_notice ("%d get_random_xx warning(s) missed due to ratelimiting\n" , - unseeded_warning.missed); - unseeded_warning.missed =0 ; - } -if (urandom_warning.missed) { -pr_notice ("%d urandom warning(s) missed due to ratelimiting\n" , - urandom_warning.missed); - urandom_warning.missed =0 ; - } - } }/*
@@ -836,10 +816,25 @@ static void credit_init_bits(size_t nbits) new = min_t(unsigned int, POOL_BITS, orig + add); }while (cmpxchg (&input_pool.init_bits, orig, new) != orig); -if (orig <POOL_READY_BITS && new >=POOL_READY_BITS ) -crng_reseed (); -else if (orig <POOL_EARLY_BITS && new >=POOL_EARLY_BITS ) { +if (orig <POOL_READY_BITS && new >=POOL_READY_BITS ) { +crng_reseed ();/* Sets crng_init to CRNG_READY under base_crng.lock. */ +process_random_ready_list (); +wake_up_interruptible (&crng_init_wait); +kill_fasync (&fasync,SIGIO ,POLL_IN ); +pr_notice ("crng init done\n" ); +if (unseeded_warning.missed) { +pr_notice ("%d get_random_xx warning(s) missed due to ratelimiting\n" , + unseeded_warning.missed); + unseeded_warning.missed =0 ; + } +if (urandom_warning.missed) { +pr_notice ("%d urandom warning(s) missed due to ratelimiting\n" , + urandom_warning.missed); + urandom_warning.missed =0 ; + } + }else if (orig <POOL_EARLY_BITS && new >=POOL_EARLY_BITS ) {spin_lock_irqsave (&base_crng.lock, flags); +/* Check if crng_init is CRNG_EMPTY, to avoid race with crng_reseed(). */ if (crng_init ==CRNG_EMPTY ) {extract_entropy (base_crng.key,sizeof (base_crng.key)); crng_init =CRNG_EARLY ;
Signature · 1 line
2.35.1
Re: [PATCH 2/2] random: move initialization out of reseeding hot path
Am Mon, May 09, 2022 at 02:14:09PM +0200 schrieb Jason A. Donenfeld:
Quoted 29 lines
Initialization happens once -- by way of
credit_init_bits()-- and then it never happens again. Therefore, it doesn't need to be incrng_reseed(), which is a hot path that is called multiple times. It also doesn't make sense to have there, as initialization activity is better associated with initialization routines.After the prior commit,
crng_reseed()now won't be called by multiple concurrent callers, which means that we can safely move the "finialize_init" logic intocrng_init_bits()unconditionally.Cc Dominik Brodowski <[email protected]>Signed-off-by Jason A. Donenfeld <[email protected]>--- drivers/char/random.c | 43 +++++++++++++++++++------------------------ 1 file changed, 19 insertions(+), 24 deletions(-)drivers/char/random.c +0
-1@@ -266,7 +266,6 @@ static void crng_reseed(void)unsigned long flags;unsigned long next_gen;u8 key[CHACHA_KEY_SIZE ]; -bool finalize_init = false;extract_entropy (key,sizeof (key));
drivers/char/random.c static void crng_reseed(void) · line 285
Quoted 8 lines
drivers/char/random.c +1
-4@@ -283,28 +282,9 @@ static void crng_reseed(void) ++next_gen;WRITE_ONCE (base_crng.generation, next_gen);WRITE_ONCE (base_crng.birth, jiffies); -if (!crng_ready ()) { - crng_init =CRNG_READY ; - finalize_init = true; - } + crng_init =CRNG_READY ;
Why unconditionally (you revert that bit in the static branch patch and make it conditional again; so I see no reason for that here)?
Otherwise, looks good:
Thanks,
Dominik
Jason A. Donenfeld
maintainerRe: [PATCH 2/2] random: move initialization out of reseeding hot path
Hi Dominik,
Quoted 7 lines · Dominik Brodowski
drivers/char/random.c static void crng_reseed(void) · line 285
Quoted 5 lines
drivers/char/random.c +1
-4-if (!crng_ready ()) { - crng_init =CRNG_READY ; - finalize_init = true; - } + crng_init =CRNG_READY ;Why unconditionally
To avoid a useless branch.
Quoted 2 lines
(you revert that bit in the static branch patch and make it conditional again; so I see no reason for that here)?
With the static branch patch, I can totally remove the branch and the store all together, so we get the best of both worlds.
Jason
RE: [PATCH 2/2] random: move initialization out of reseeding hot path
From: Jason A. Donenfeld
Quoted 11 lines
Sent: 13 May 2022 11:22
Quoted 7 lines · Dominik Brodowski
drivers/char/random.c static void crng_reseed(void) · line 285
Quoted 5 lines
drivers/char/random.c +1
-4-if (!crng_ready ()) { - crng_init =CRNG_READY ; - finalize_init = true; - } + crng_init =CRNG_READY ;Why unconditionally
Quoted 1 line
To avoid a useless branch.
Are you now dirtying a cache line that would
otherwise be clean?
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
Jason A. Donenfeld
maintainerRe: [PATCH 2/2] random: move initialization out of reseeding hot path
Hi David,
Quoted 11 lines · David Laight
From: Jason A. Donenfeld
Quoted 9 lines
Sent: 13 May 2022 11:22
Quoted 6 lines · Dominik Brodowski
Quoted 5 lines
- if (!crng_ready()) {
drivers/char/random.c +1
-3- crng_init =CRNG_READY ; - finalize_init = true; - } + crng_init =CRNG_READY ;
Quoted 6 lines
Quoted 3 lines
Quoted 1 line
Why unconditionally
To avoid a useless branch.
Are you now dirtying a cache line that would
otherwise be clean?
Fair enough. I'll keep the branch.
Jason
Jason A. Donenfeld
maintainerPATCH v2 1/1 random: move initialization out of reseeding hot path
Initialization happens once -- by way of credit_init_bits() -- and then it never happens again. Therefore, it doesn't need to be in crng_reseed(), which is a hot path that is called multiple times. It also doesn't make sense to have there, as initialization activity is better associated with initialization routines.
After the prior commit, crng_reseed() now won't be called by multiple concurrent callers, which means that we can safely move the "finialize_init" logic into crng_init_bits() unconditionally.
---
Changes v1->v2:
- Keep crng_init = CRNG_READY conditional to avoid dirtying cache line.
drivers/char/random.c | 42 +++++++++++++++++++----------------------- 1 file changed, 19 insertions(+), 23 deletions(-)
drivers/char/random.c +19 -23
@@ -265,7 +265,6 @@ static void crng_reseed(void)unsigned long flags;unsigned long next_gen;u8 key[CHACHA_KEY_SIZE ]; -bool finalize_init = false;extract_entropy (key,sizeof (key));
@@ -282,28 +281,10 @@ static void crng_reseed(void) ++next_gen;WRITE_ONCE (base_crng.generation, next_gen);WRITE_ONCE (base_crng.birth, jiffies); -if (!crng_ready ()) { +if (!crng_ready ()) crng_init =CRNG_READY ; - finalize_init = true; - }spin_unlock_irqrestore (&base_crng.lock, flags);memzero_explicit (key,sizeof (key)); -if (finalize_init) { -process_random_ready_list (); -wake_up_interruptible (&crng_init_wait); -kill_fasync (&fasync,SIGIO ,POLL_IN ); -pr_notice ("crng init done\n" ); -if (unseeded_warning.missed) { -pr_notice ("%d get_random_xx warning(s) missed due to ratelimiting\n" , - unseeded_warning.missed); - unseeded_warning.missed =0 ; - } -if (urandom_warning.missed) { -pr_notice ("%d urandom warning(s) missed due to ratelimiting\n" , - urandom_warning.missed); - urandom_warning.missed =0 ; - } - } }/*
@@ -835,10 +816,25 @@ static void credit_init_bits(size_t nbits) new = min_t(unsigned int, POOL_BITS, orig + add); }while (cmpxchg (&input_pool.init_bits, orig, new) != orig); -if (orig <POOL_READY_BITS && new >=POOL_READY_BITS ) -crng_reseed (); -else if (orig <POOL_EARLY_BITS && new >=POOL_EARLY_BITS ) { +if (orig <POOL_READY_BITS && new >=POOL_READY_BITS ) { +crng_reseed ();/* Sets crng_init to CRNG_READY under base_crng.lock. */ +process_random_ready_list (); +wake_up_interruptible (&crng_init_wait); +kill_fasync (&fasync,SIGIO ,POLL_IN ); +pr_notice ("crng init done\n" ); +if (unseeded_warning.missed) { +pr_notice ("%d get_random_xx warning(s) missed due to ratelimiting\n" , + unseeded_warning.missed); + unseeded_warning.missed =0 ; + } +if (urandom_warning.missed) { +pr_notice ("%d urandom warning(s) missed due to ratelimiting\n" , + urandom_warning.missed); + urandom_warning.missed =0 ; + } + }else if (orig <POOL_EARLY_BITS && new >=POOL_EARLY_BITS ) {spin_lock_irqsave (&base_crng.lock, flags); +/* Check if crng_init is CRNG_EMPTY, to avoid race with crng_reseed(). */ if (crng_init ==CRNG_EMPTY ) {extract_entropy (base_crng.key,sizeof (base_crng.key)); crng_init =CRNG_EARLY ;
Signature · 1 line
2.35.1
Am Mon, May 09, 2022 at 02:14:08PM +0200 schrieb Jason A. Donenfeld:
Quoted 5 lines
Since all changes of
crng_initnow go throughcredit_init_bits(), we can fix a long standing race in which two concurrent callers ofcredit_init_bits()have the new bit count >= some threshold, but are doing so withcrng_initas a lower threshold, checked outside of a lock, resulting incrng_reseed()or similar being called twice.
Sidenote: crng_reseed() did manage quite fine if called twice in short order.
Quoted 6 lines
In order to fix this, we can use the original cmpxchg value of the bit count, and only change
crng_initwhen the bit count transitions from below a threshold to meeting the threshold.Cc Dominik Brodowski <[email protected]>Signed-off-by Jason A. Donenfeld <[email protected]>
Thanks,
Dominik
Jason A. Donenfeld
maintainerHi Dominik,
Quoted 9 lines · Dominik Brodowski
Am Mon, May 09, 2022 at 02:14:08PM +0200 schrieb Jason A. Donenfeld:
Quoted 5 lines
Since all changes of
crng_initnow go throughcredit_init_bits(), we can fix a long standing race in which two concurrent callers ofcredit_init_bits()have the new bit count >= some threshold, but are doing so withcrng_initas a lower threshold, checked outside of a lock, resulting incrng_reseed()or similar being called twice.Sidenote:
crng_reseed()did manage quite fine if called twice in short order.
With regards to crng_finialize, it did, but not with regards to prematurely emptying patches and all that. IOW, buggy but not that bad.
Quoted 5 lines
Quoted 5 lines
In order to fix this, we can use the original cmpxchg value of the bit count, and only change
crng_initwhen the bit count transitions from below a threshold to meeting the threshold.
Quoted 7 lines
Quoted 2 lines
Cc Dominik Brodowski <[email protected]>Signed-off-by Jason A. Donenfeld <[email protected]>Reviewed-by Dominik Brodowski <[email protected]>Thanks,
Dominik
Jason