drivers/char/random.c line 728 BUG
Hi,
We saw this oops. Kernel is vanilla 2.6.26.2. Machine is Dell PowerEdge 1750.
I saw one other instance mentioned on kerneloops but the link didn't seem to go to the proper place.
Let me know if you need more information.
Thanks, =a=
------------[ cut here ]------------ kernel BUG at drivers/char/random.c:728! invalid opcode: 0000 [#1] PREEMPT SMP Modules linked in: nfs lockd autofs4 sunrpc firmware_class ohci_hcd usbcore tg3 [last unloaded: x_tables]
Pid: 31251, comm: python Not tainted (2.6.26.2-asb #18)
EIP: 0060:[<c0219cd7>] EFLAGS: 00010206 CPU: 1
EIP is at account+0x1f/0xca
EAX: 00000400 EBX: c03c2f98 ECX: 00000000 EDX: 00001000
ESI: c03c2f98 EDI: 00001000 EBP: 00000000 ESP: f6b8ff38
DS: 007b ES: 007b FS: 00d8 GS: 0033 SS: 0068
Process python (pid: 31251, ti=f6b8e000 task=f790c6c0 task.ti=f6b8e000)
Stack: 3e2efd76 00000000 1ff38c67 32a39c7a 00001000 c03c2f98 c021a215 b76a6000
c021a183 00000000 00000001 b76a6000 c014f8ed 00000000 f71e7a80 b76a6000
c021a215 00001000 c015d9e3 f6b8ffa0 f71e7a80 fffffff7 00000000 f6b8e000
Call Trace:
[<c021a215>] urandom_read+0x0/0xa
[<c021a183>] extract_entropy_user+0x21/0xb3
[<c014f8ed>] do_mmap_pgoff+0x1e7/0x232
[<c021a215>] urandom_read+0x0/0xa
[<c015d9e3>] vfs_read+0x81/0xf4
[<c015dd96>] sys_read+0x3c/0x63
[<c0102bf1>] sysenter_past_esp+0x6a/0x91
[<c0300000>] native_cpu_up+0x2ee/0x63d
=======================
Code: 5f 5d e9 b5 a3 0e 00 5b 5e 5f 5d c3 55 57 56 53 83 ec 10 89 c3 89 d7 89 4c 24 04 8b 6c 24 24 8b 00 8b 00 c1 e0 05 39 43 1c 7e 04 <0f> 0b eb fe 8d 43 14 89 44 24 08 e8 39 a1 0e 00 89 44 24 0c 8b
EIP: [<c0219cd7>] account+0x1f/0xca SS:ESP 0068:f6b8ff38
---[ end trace 275ff84df4f1fc30 ]---Signature · 3 lines
=================== Aaron Straus [email protected]
Hi,
Quoted 1 line · Aaron Straus
kernel BUG at
drivers/char/random.c:728!
OK so that's (outside spinlock):
BUG_ON(r->entropy_count > r->poolinfo->POOLBITS);
in credit_entropy_bits we do (inside spinlock):
r->entropy_count += nbits;
if (r->entropy_count < 0) {
DEBUG_ENT("negative entropy/overflow\n");
r->entropy_count = 0;
} else if (r->entropy_count > r->poolinfo->POOLBITS)
r->entropy_count = r->poolinfo->POOLBITS;I wonder if we got unlucky and did the:
r->entropy_count += nbits
- overflowed the entropy_count THEN
- another thread hits the BUG before this thread reaches
r->entropy_count = r->poolinfo->POOLBITS;
--
I notice before this commit:
commit adc782dae6c4c0f6fb679a48a544cfbcd79ae3dc
Author: Matt Mackall <[email protected]> Date: Tue Apr 29 01:03:07 2008 -0700
random: simplify and rename credit_entropy_store
The credit_entropy_store function looks like this:
spin_lock_irqsave(&r->lock, flags);
if (r->entropy_count + nbits < 0) {
DEBUG_ENT("negative entropy/overflow (%d+%d)\n",
r->entropy_count, nbits);
r->entropy_count = 0;
} else if (r->entropy_count + nbits > r->poolinfo->POOLBITS) {
r->entropy_count = r->poolinfo->POOLBITS;
} else {
r->entropy_count += nbits;
if (nbits)
DEBUG_ENT("added %d entropy credits to %s\n",
nbits, r->name);
}Notice the old version is careful not to overflow r->entropy_count at any point (even within the spinlock). So perhaps that's why we didn't hit this BUG() in the past?
Thanks!
=a=
Signature · 3 lines
=================== Aaron Straus [email protected]
Quoted 55 lines · On Thu, 28 Aug 2008 15:59:24 -0700 Aaron Straus <[email protected]> wrote:
Hi,
Quoted 1 line · Aaron Straus
kernel BUG at
drivers/char/random.c:728!OK so that's (outside spinlock):
BUG_ON(r->entropy_count > r->poolinfo->POOLBITS);in
credit_entropy_bitswe do (inside spinlock):r->entropy_count += nbits; if (r->entropy_count < 0) { DEBUG_ENT("negative entropy/overflow\n"); r->entropy_count = 0; } else if (r->entropy_count > r->poolinfo->POOLBITS) r->entropy_count = r->poolinfo->POOLBITS;I wonder if we got unlucky and did the:
r->entropy_count+= nbits- overflowed the
entropy_countTHEN
- another thread hits the BUG before this thread reachesr->entropy_count = r->poolinfo->POOLBITS;--
I notice before this commit:
commit
adc782dae6c4c0f6fb679a48a544cfbcd79ae3dcAuthor: Matt Mackall <[email protected]> Date: Tue Apr 29 01:03:07 2008 -0700random: simplify and rename
credit_entropy_storeThe
credit_entropy_storefunction looks like this:spin_lock_irqsave(&r->lock, flags); if (r->entropy_count + nbits < 0) { DEBUG_ENT("negative entropy/overflow (%d+%d)\n", r->entropy_count, nbits); r->entropy_count = 0; } else if (r->entropy_count + nbits > r->poolinfo->POOLBITS) { r->entropy_count = r->poolinfo->POOLBITS; } else { r->entropy_count += nbits; if (nbits) DEBUG_ENT("added %d entropy credits to %s\n", nbits, r->name); }
Quoted 4 lines
Notice the old version is careful not to overflow
r->entropy_countat any point (even within the spinlock). So perhaps that's why we didn't hit thisBUG()in the past?
yep, I would agree with all that.
How's this look?
From: Andrew Morton <[email protected]>
Fix a bug reported by and diagnosed by Aaron Straus.
This is a regression intruduced into 2.6.26 by
commit adc782dae6c4c0f6fb679a48a544cfbcd79ae3dc
Author: Matt Mackall <[email protected]>
Date: Tue Apr 29 01:03:07 2008 -0700
random: simplify and rename credit_entropy_store
credit_entropy_bits() does:
spin_lock_irqsave(&r->lock, flags); ... if (r->entropy_count > r->poolinfo->POOLBITS) r->entropy_count = r->poolinfo->POOLBITS;
so there is a time window in which this BUG_ON():
static size_t account(struct entropy_store *r, size_t nbytes, int min,
int reserved)
{
unsigned long flags;
BUG_ON(r->entropy_count > r->poolinfo->POOLBITS);
/* Hold lock while accounting */
spin_lock_irqsave(&r->lock, flags);can trigger.
We could fix this by moving the assertion inside the lock, but it seems safer and saner to revert to the old behaviour wherein entropy_store.entropy_count at no time exceeds entropy_store.poolinfo->POOLBITS.
---
drivers/char/random.c | 17 +++++++++-------- 1 file changed, 9 insertions(+), 8 deletions(-)
drivers/char/random.c renamed from drivers/char/random.c~drivers-char-randomc-fix-a-race-which-can-lead-to-a-bogus-bug +9 -8
@@ -520,6 +520,7 @@ static void mix_pool_bytes(struct entropstatic void credit_entropy_bits (struct entropy_store *r,int nbits) {unsigned long flags; +int entropy_count;if (!nbits)return ;
@@ -527,20 +528,20 @@ static void credit_entropy_bits(struct espin_lock_irqsave (&r->lock, flags);DEBUG_ENT ("added %d entropy credits to %s\n" , nbits, r->name); - r->entropy_count += nbits; -if (r->entropy_count <0 ) { + entropy_count = r->entropy_count; + entropy_count += nbits; +if (entropy_count <0 ) {DEBUG_ENT ("negative entropy/overflow\n" ); - r->entropy_count =0 ; - }else if (r->entropy_count > r->poolinfo->POOLBITS) - r->entropy_count = r->poolinfo->POOLBITS; + entropy_count =0 ; + }else if (entropy_count > r->poolinfo->POOLBITS) + entropy_count = r->poolinfo->POOLBITS;/* should we wake readers? */ -if (r == &input_pool && - r->entropy_count >= random_read_wakeup_thresh) { +if (r == &input_pool && entropy_count >= random_read_wakeup_thresh) {wake_up_interruptible (&random_read_wait);kill_fasync (&fasync,SIGIO ,POLL_IN ); } - + r->entropy_count = entropy_count;spin_unlock_irqrestore (&r->lock, flags); }
_
Quoted 4 lines · On Fri, 29 Aug 2008 12:48:07 -0700 Andrew Morton <[email protected]>…
We could fix this by moving the assertion inside the lock, but it seems safer and saner to revert to the old behaviour wherein entropy_store.entropy_count at no time exceeds
entropy_store.poolinfo->POOLBITS.
The fixed version even generates improved code.
Let's try to avoid repeats:
drivers/char/random.c renamed from drivers/char/random.c~drivers-char-randomc-fix-a-race-which-can-lead-to-a-bogus-bug-fix +1 -1
@@ -407,7 +407,7 @@ struct entropy_store {/* read-write data: */ spinlock_t lock;unsigned add_ptr; -int entropy_count; +int entropy_count;/* Must at no time exceed ->POOLBITS! */ int input_rotate; };
_
Hi,
Quoted 1 line · Andrew Morton
yep, I would agree with all that.
Thanks for responding.
Quoted 1 line
How's this look?
Quick question off list... below
drivers/char/random.c static void credit_entropy_bits(struct e · line 544
Quoted 8 lines
drivers/char/random.c renamed from drivers/char/random.c~drivers-char-randomc-fix-a-race-which-can-lead-to-a-bogus-bug +2
-3-if (r == &input_pool && - r->entropy_count >= random_read_wakeup_thresh) { +if (r == &input_pool && entropy_count >= random_read_wakeup_thresh) {wake_up_interruptible (&random_read_wait);kill_fasync (&fasync,SIGIO ,POLL_IN ); } - + r->entropy_count = entropy_count;
Here you set the entropy_count in the pool *after* waking up the reader. I was a little worried the reader would find the entropy_count unchanged and go back to sleep.
Regards, =a=
Signature · 3 lines
=================== Aaron Straus [email protected]
Quoted 4 lines · On Fri, 29 Aug 2008 15:31:55 -0700 Aaron Straus <[email protected]> wrote:
Quoted 4 lines
(quoted diff) +1
-2- if (r == &input_pool && - r->entropy_count >= random_read_wakeup_thresh) { + if (r == &input_pool && entropy_count >= random_read_wakeup_thresh) { wake_up_interruptible(&random_read_wait);
Quoted 9 lines
Review
Quoted 4 lines
(quoted diff) +1
-1kill_fasync(&fasync, SIGIO, POLL_IN); } - + r->entropy_count = entropy_count;Here you set the
entropy_countin the pool *after* waking up the reader. I was a little worried the reader would find theentropy_countunchanged and go back to sleep.
Probably it doesn't matter because of the coverage of the lock but yes, let's do the assignment first.
drivers/char/random.c renamed from drivers/char/random.c~drivers-char-randomc-fix-a-race-which-can-lead-to-a-bogus-bug-fix-fix +1 -1
@@ -535,13 +535,13 @@ static void credit_entropy_bits(struct e entropy_count =0 ; }else if (entropy_count > r->poolinfo->POOLBITS) entropy_count = r->poolinfo->POOLBITS; + r->entropy_count = entropy_count;/* should we wake readers? */ if (r == &input_pool && entropy_count >= random_read_wakeup_thresh) {wake_up_interruptible (&random_read_wait);kill_fasync (&fasync,SIGIO ,POLL_IN ); } - r->entropy_count = entropy_count;spin_unlock_irqrestore (&r->lock, flags); }
_
Quoted 145 lines · Andrew Morton
Quoted 55 lines · On Thu, 28 Aug 2008 15:59:24 -0700 Aaron Straus <[email protected]> wrote:
Hi,
Quoted 1 line · Aaron Straus
kernel BUG at
drivers/char/random.c:728!OK so that's (outside spinlock):
BUG_ON(r->entropy_count > r->poolinfo->POOLBITS);in
credit_entropy_bitswe do (inside spinlock):r->entropy_count += nbits; if (r->entropy_count < 0) { DEBUG_ENT("negative entropy/overflow\n"); r->entropy_count = 0; } else if (r->entropy_count > r->poolinfo->POOLBITS) r->entropy_count = r->poolinfo->POOLBITS;I wonder if we got unlucky and did the:
r->entropy_count+= nbits- overflowed the
entropy_countTHEN
- another thread hits the BUG before this thread reachesr->entropy_count = r->poolinfo->POOLBITS;--
I notice before this commit:
commit
adc782dae6c4c0f6fb679a48a544cfbcd79ae3dcAuthor: Matt Mackall <[email protected]> Date: Tue Apr 29 01:03:07 2008 -0700random: simplify and rename
credit_entropy_storeThe
credit_entropy_storefunction looks like this:spin_lock_irqsave(&r->lock, flags); if (r->entropy_count + nbits < 0) { DEBUG_ENT("negative entropy/overflow (%d+%d)\n", r->entropy_count, nbits); r->entropy_count = 0; } else if (r->entropy_count + nbits > r->poolinfo->POOLBITS) { r->entropy_count = r->poolinfo->POOLBITS; } else { r->entropy_count += nbits; if (nbits) DEBUG_ENT("added %d entropy credits to %s\n", nbits, r->name); }Quoted 4 lines
Notice the old version is careful not to overflow
r->entropy_countat any point (even within the spinlock). So perhaps that's why we didn't hit thisBUG()in the past?yep, I would agree with all that.
How's this look?
From: Andrew Morton <[email protected]>
Fix a bug reported by and diagnosed by Aaron Straus.
This is a regression intruduced into 2.6.26 by
commit
adc782dae6c4c0f6fb679a48a544cfbcd79ae3dc
Author: Matt Mackall <[email protected]>
Date: Tue Apr 29 01:03:07 2008 -0700random: simplify and rename
credit_entropy_store
credit_entropy_bits()does:spin_lock_irqsave(&r->lock, flags); ... if (r->entropy_count > r->poolinfo->POOLBITS) r->entropy_count = r->poolinfo->POOLBITS;so there is a time window in which this
BUG_ON():static
size_taccount(structentropy_store*r,size_tnbytes, int min,
int reserved){ unsigned long flags; BUG_ON(r->entropy_count > r->poolinfo->POOLBITS); /* Hold lock while accounting */ spin_lock_irqsave(&r->lock, flags);can trigger.
We could fix this by moving the assertion inside the lock, but it seems safer and saner to revert to the old behaviour wherein entropy_store.entropy_count at no time exceeds
entropy_store.poolinfo->POOLBITS.Reported-by Aaron Straus <[email protected]>Cc Matt Mackall <[email protected]>Cc Theodore Ts'o <[email protected]>Cc <[email protected]> [2.6.26.x]Signed-off-by Andrew Morton <[email protected]>---
drivers/char/random.c | 17 +++++++++-------- 1 file changed, 9 insertions(+), 8 deletions(-)diff -puN
drivers/char/random.c~drivers-char-randomc-fix-a-race-which-can-lead-to-a-bogus-bugdrivers/char/random.cdrivers/char/random.c renamed from drivers/char/random.c~drivers-char-randomc-fix-a-race-which-can-lead-to-a-bogus-bug +7
-5@@ -520,6 +520,7 @@ static void mix_pool_bytes(struct entropstatic void credit_entropy_bits (struct entropy_store *r,int nbits) {unsigned long flags; +int entropy_count;if (!nbits)return ;@@ -527,20 +528,20 @@ static void credit_entropy_bits(struct espin_lock_irqsave (&r->lock, flags);DEBUG_ENT ("added %d entropy credits to %s\n" , nbits, r->name); - r->entropy_count += nbits; -if (r->entropy_count <0 ) { + entropy_count = r->entropy_count; + entropy_count += nbits; +if (entropy_count <0 ) {DEBUG_ENT ("negative entropy/overflow\n" ); - r->entropy_count =0 ; - }else if (r->entropy_count > r->poolinfo->POOLBITS) - r->entropy_count = r->poolinfo->POOLBITS; + entropy_count =0 ; + }else if (entropy_count > r->poolinfo->POOLBITS) + entropy_count = r->poolinfo->POOLBITS;/* should we wake readers? */
drivers/char/random.c static void credit_entropy_bits(struct e · line 546
Quoted 10 lines
drivers/char/random.c renamed from drivers/char/random.c~drivers-char-randomc-fix-a-race-which-can-lead-to-a-bogus-bug +2
-3-if (r == &input_pool && - r->entropy_count >= random_read_wakeup_thresh) { +if (r == &input_pool && entropy_count >= random_read_wakeup_thresh) {wake_up_interruptible (&random_read_wait);kill_fasync (&fasync,SIGIO ,POLL_IN ); } - + r->entropy_count = entropy_count;spin_unlock_irqrestore (&r->lock, flags); }
Sorry, just back from being offline for a week.
This fix is bogus - it assumes that r->entropy_count has atomic assignment which is not universally true (witness the existence of atomic_t). So we can still observe partial updates to entropy_count on some architectures. Now it's probably the case that we'll never see a partial update that actually triggers the BUG_ON, but it's still conceptually wrong to do things this way.
The right fix in such a case is simply to never look at such things outside the relevant lock. Especially so in this case, where we take the lock unconditionally one line later - there's absolutely no upside to examining it outside the lock.
I'm fine with using a local for entropy_count as prettification, but not for trying to avoid races. We should do this instead:
Avoid checking lock-protected entropy_count when lock isn't held.
drivers/char/random.c +1 -2
@@ -726,11 +726,10 @@ {unsigned long flags; -BUG_ON (r->entropy_count > r->poolinfo->POOLBITS); -/* Hold lock while accounting */ spin_lock_irqsave (&r->lock, flags); +BUG_ON (r->entropy_count > r->poolinfo->POOLBITS);DEBUG_ENT ("trying to extract %d bits from %s\n" , nbytes *8 , r->name);
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Hi Matt,
Quoted 6 lines · Matt Mackall
This fix is bogus - it assumes that
r->entropy_counthas atomic assignment which is not universally true (witness the existence ofatomic_t). So we can still observe partial updates toentropy_counton some architectures. Now it's probably the case that we'll never see a partial update that actually triggers theBUG_ON, but it's still conceptually wrong to do things this way.
I think Andrew was just being safe by reverting to the old behavior.
Could we still apply his patch for the upcoming stable tree and fix it the "right" way at some point in the future?
Thanks, =a=
Signature · 3 lines
=================== Aaron Straus [email protected]
Quoted 11 lines · Aaron Straus
Hi Matt,
Quoted 6 lines · Matt Mackall
This fix is bogus - it assumes that
r->entropy_counthas atomic assignment which is not universally true (witness the existence ofatomic_t). So we can still observe partial updates toentropy_counton some architectures. Now it's probably the case that we'll never see a partial update that actually triggers theBUG_ON, but it's still conceptually wrong to do things this way.I think Andrew was just being safe by reverting to the old behavior.
Indeed. I've no doubt that his fix works and I'm certainly glad you guys took the time to fix things while I was away. I just think the resulting fix is a little silly.
Quoted 2 lines
Could we still apply his patch for the upcoming stable tree and fix it the "right" way at some point in the future?
I'm not sure what the current state of play is here in terms of the original patch being pushed to stable and mainline, but my patch is both simpler and more correct. If it's not too late, it's the one that should go to both places.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Quoted 7 lines · On Wed, 03 Sep 2008 17:12:00 -0500 Matt Mackall <[email protected]> wrote:
Quoted 2 lines
Could we still apply his patch for the upcoming stable tree and fix it the "right" way at some point in the future?
I'm not sure what the current state of play is here in terms of the original patch being pushed to stable and mainline, but my patch is both simpler and more correct. If it's not too late, it's the one that should go to both places.
It's a fairly minor thing. The post-this-patch code takes care to ensure that ->entropy_count never has an illegal value, so it's OK but aesthetially unpleasing to check its value outside the lock.
And the post-this-patch code generates less .text, so it's a desirable thing from that POV too.
We could/should do both, I guess. I kinda ducked your move-the-BUG patch because I wasn't in a write-yet-another-changelog mood.
Quoted 11 lines · Andrew Morton
Quoted 7 lines · On Wed, 03 Sep 2008 17:12:00 -0500 Matt Mackall <[email protected]> wrote:
Quoted 2 lines
Could we still apply his patch for the upcoming stable tree and fix it the "right" way at some point in the future?
I'm not sure what the current state of play is here in terms of the original patch being pushed to stable and mainline, but my patch is both simpler and more correct. If it's not too late, it's the one that should go to both places.
Quoted 8 lines
It's a fairly minor thing. The post-this-patch code takes care to ensure that ->entropy_count never has an illegal value, so it's OK but aesthetially unpleasing to check its value outside the lock.
And the post-this-patch code generates less .text, so it's a desirable thing from that POV too.
We could/should do both, I guess.
Sure, adding a local variable is fine. Though really, this shouldn't actually improve things, that's just our compiler being sucky. And I think it's a wash in terms of readability.
Quoted 2 lines
I kinda ducked your move-the-BUG
patch because I wasn't in a write-yet-another-changelog mood.
I included one, but it was terse:
Avoid checking lock-protected entropy_count when lock isn't held.
Here's a more expansive version:
Avoid checking lock-protected entropy_count when lock isn't held. This fixes a bug reported by and diagnosed by Aaron Straus.
This fixes a regression introduced into 2.6.26 by
commit adc782dae6c4c0f6fb679a48a544cfbcd79ae3dc
Author: Matt Mackall <[email protected]>
Date: Tue Apr 29 01:03:07 2008 -0700
random: simplify and rename credit_entropy_store
drivers/char/random.c +1 -2
@@ -726,11 +726,10 @@ {unsigned long flags; -BUG_ON (r->entropy_count > r->poolinfo->POOLBITS); -/* Hold lock while accounting */ spin_lock_irqsave (&r->lock, flags); +BUG_ON (r->entropy_count > r->poolinfo->POOLBITS);DEBUG_ENT ("trying to extract %d bits from %s\n" , nbytes *8 , r->name);
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Quoted 5 lines · On Wed, 03 Sep 2008 17:51:37 -0500 Matt Mackall <[email protected]> wrote:
Here's a more expansive version:
___Avoidchecking lock-protectedentropy_countwhen lock isn't held. This fixes a bug reported by and diagnosed by Aaron Straus.
Quoted 7 lines
This fixes a regression introduced into 2.6.26 by
commit
adc782dae6c4c0f6fb679a48a544cfbcd79ae3dc
Author: Matt Mackall <[email protected]>
Date: Tue Apr 29 01:03:07 2008 -0700random: simplify and rename
credit_entropy_store
That regression already got fixed, and the fix is now in mainline and is queued for 2.6.26.x. So we would need a new rationale, please.