Possible memory ordering bug in page reclaim?
Subsystems (4)
Is there anything that prevents PageDirty from theoretically being speculatively loaded before page_count here? (see patch)
It would result in pagecache corruption in the following situation:
1 2find_get_page();
write to page write_lock(tree_lock);SetPageDirty(); if (page_count != 2put_page(); || PageDirty())
Now I'm worried that 2 might see PageDirty *before* SetPageDirty in 1, and page_count *after* put_page in 1.
Or am I seeing things that aren't there?
Thanks,
Signature · 1 line
SUSE Labs, Novell Inc.
mm/vmscan.c +6 -1
@@ -511,7 +511,12 @@ static int shrink_list(struct list_head* PageDirty _after_ making sure that the page is freeable and * not in use by anybody. (pagecache + us == 2) */ -if (page_count (page) !=2 ||PageDirty (page)) { +if (page_count (page) !=2 ) { +write_unlock_irq (&mapping->tree_lock); + goto keep_locked; + } +smp_rmb (); +if (PageDirty (page)) {write_unlock_irq (&mapping->tree_lock); goto keep_locked; }
Quoted 6 lines · Nick Piggin
Is there anything that prevents PageDirty from theoretically being speculatively loaded before
page_counthere? (see patch)It would result in pagecache corruption in the following situation:
Quoted 7 lines
1 2
find_get_page();
write to pagewrite_lock(tree_lock);SetPageDirty(); if (page_count!= 2put_page(); ||PageDirty())Now I'm worried that 2 might see PageDirty *before* SetPageDirty in
page->flags
Quoted 1 line
1, and
page_count*after*put_pagein 1.
I think you're right. But I'm the last person to ask barrier/ordering questions of. CC'ed Ben and Andrea.
Hugh
Quoted 16 lines
mm/vmscan.c +6
-1@@ -511,7 +511,12 @@ static int shrink_list(struct list_head* PageDirty _after_ making sure that the page is freeable and * not in use by anybody. (pagecache + us == 2) */ -if (page_count (page) !=2 ||PageDirty (page)) { +if (page_count (page) !=2 ) { +write_unlock_irq (&mapping->tree_lock); + goto keep_locked; + } +smp_rmb (); +if (PageDirty (page)) {write_unlock_irq (&mapping->tree_lock); goto keep_locked; }
Quoted 13 lines · Hugh Dickins
Quoted 12 lines · Nick Piggin
Is there anything that prevents PageDirty from theoretically being speculatively loaded before
page_counthere? (see patch)It would result in pagecache corruption in the following situation:
1 2
find_get_page();
write to pagewrite_lock(tree_lock);SetPageDirty(); if (page_count!= 2put_page(); ||PageDirty())
Quoted 6 lines
Quoted 1 line
Now I'm worried that 2 might see PageDirty *before* SetPageDirty in
page->flagsQuoted 1 line
1, and
page_count*after*put_pagein 1.I think you're right. But I'm the last person to ask barrier/ordering questions of. CC'ed Ben and Andrea.
yup, now the question is wether PG_Dirty will be visible to CPU 2 before the page count is decremented right ? That depends on put_page, I suppose. If it's doing a simple atomic, there is an issue. But atomics with return has been so often abused as locks that they may have been implemented with a barrier... (On ppc64, it will do an eieio, thus I think it should be ok).
There is also a problem the other way around. Write to page, then set page dirty... those writes may be visible to CPU 2 (that is the page content be dirty) before find_get_page even increased the page count, unless there is a barrier in there too.
Paul, Anton ?
Ben.
Quoted 9 lines · Benjamin Herrenschmidt
Quoted 9 lines
Quoted 8 lines
1 2
find_get_page();
write to pagewrite_lock(tree_lock);SetPageDirty(); if (page_count!= 2put_page(); ||PageDirty())Now I'm worried that 2 might see PageDirty *before* SetPageDirty in
page->flags
Quoted 8 lines
Quoted 1 line
Quoted 1 line
1, and
page_count*after*put_pagein 1.yup, now the question is wether
PG_Dirtywill be visible to CPU 2 before the page count is decremented right ? That depends onput_page, I suppose. If it's doing a simple atomic, there is an issue. But atomics with return has been so often abused as locks that they may have been implemented with a barrier... (On ppc64, it will do an eieio, thus I think it should be ok).
Yes atomic_add_negative should always be a barrier.
Quoted 4 lines
There is also a problem the other way around. Write to page, then set page dirty... those writes may be visible to CPU 2 (that is the page content be dirty) before
find_get_pageeven increased the page count, unless there is a barrier in there too.
find_get_page does a read_unlock_irq after the increment which also serves as a barrier.
Cheers,
Signature · 4 lines
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txtQuoted 11 lines · Herbert Xu
Quoted 6 lines · Benjamin Herrenschmidt
yup, now the question is wether
PG_Dirtywill be visible to CPU 2 before the page count is decremented right ? That depends onput_page, I suppose. If it's doing a simple atomic, there is an issue. But atomics with return has been so often abused as locks that they may have been implemented with a barrier... (On ppc64, it will do an eieio, thus I think it should be ok).Yes
atomic_add_negativeshould always be a barrier.
I disagree. That would be very expensive on anything but x86, where it just happens to be true for other reasons. Atomics do _not_ implement barriers.
Normally, we really don't care about any other decrement than the one that goes to zero, and that one tends to come with its own serialization logic.
In this case, we don't even care.
I agree, however, that it looks like PG_dirty is racy. Probably not in practice, but still.
So I'd suggest adding a smp_wmb() into set_page_dirty, and the rmb where Nick suggested.
So I'd suggest a patch something more like this.. Marking the dirty/count cases unlikely too in mm/page-writeback.c, since we should have tested for these conditions optimistically outside the lock.
Comments? Nick, did you have some test-case that you think might actually have been impacted by this?
Linus
---
mm/page-writeback.c +7 -1
@@ -668,8 +668,14 @@ int fastcall set_page_dirty(struct pagereturn (*spd)(page);return __set_page_dirty_buffers (page); } -if (!PageDirty (page)) +if (!PageDirty (page)) {SetPageDirty (page); +/* +* Make sure the dirty bit percolates out +* to other CPU's before we release the page +*/ +smp_wmb (); + }return 0 ; }EXPORT_SYMBOL (set_page_dirty);
mm/vmscan.c +9 -4
@@ -511,10 +511,11 @@ static int shrink_list(struct list_head* PageDirty _after_ making sure that the page is freeable and * not in use by anybody. (pagecache + us == 2) */ -if (page_count (page) !=2 ||PageDirty (page)) { -write_unlock_irq (&mapping->tree_lock); - goto keep_locked; - } +if (unlikely (page_count (page) !=2 )) + goto cannot_free; +smp_rmb (); +if (unlikely (PageDirty (page))) + goto cannot_free;#ifdef CONFIG_SWAP if (PageSwapCache (page)) {
@@ -538,6 +539,10 @@ free_it:__pagevec_release_nonlru (&freed_pvec);continue ; +cannot_free: +write_unlock_irq (&mapping->tree_lock); + goto keep_locked; + activate_locked:SetPageActive (page); pgactivate++;
From: Linus Torvalds <[email protected]>
Date: Sat, 15 Oct 2005 09:57:47 -0700 (PDT)
Quoted 7 lines · Herbert Xu
Quoted 2 lines
Yes
atomic_add_negativeshould always be a barrier.I disagree. That would be very expensive on anything but x86, where it just happens to be true for other reasons. Atomics do _not_ implement barriers.
When they return values, they are defined to be barriers. It's even on the documentation :-)
Quoted 5 lines · David S. Miller
From: Linus Torvalds <[email protected]>
Date: Sat, 15 Oct 2005 09:57:47 -0700 (PDT)Quoted 2 lines · Herbert Xu
Quoted 1 line
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
Yes
atomic_add_negativeshould always be a barrier.I disagree. That would be very expensive on anything but x86, where it just happens to be true for other reasons. Atomics do _not_ implement barriers.
When they return values, they are defined to be barriers. It's even on the documentation :-)
Ahhh, good to know :)
/me should read the documentation sometimes....
Ben.
Quoted 6 lines · Linus Torvalds
I agree, however, that it looks like
PG_dirtyis racy. Probably not in practice, but still.So I'd suggest adding a
smp_wmb()intoset_page_dirty, and the rmb where Nick suggested.So I'd suggest a patch something more like this.. Marking the dirty/count cases unlikely too in
mm/page-writeback.c, since we should have tested for these conditions optimistically outside the lock.
As Dave suggested, I think there is too much other code that depends on these atomics to be barriers for us to change it (at least not in this patch! :)).
Quoted 2 lines
Comments? Nick, did you have some test-case that you think might actually have been impacted by this?
I guess your vmscan.c hunks are slightly nicer, though I might put 'cannot_free' right at the end, because it will be a very uncommon case.
And no, I don't have a test case. In fact, I wouldn't be surprised if nobody anywhere has ever hit it :) I was just browsing code...
Thanks,
Nick
Signature · 3 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Quoted 21 lines · Benjamin Herrenschmidt
Quoted 9 lines · Hugh Dickins
Quoted 6 lines · Nick Piggin
1 2
find_get_page();
write to pagewrite_lock(tree_lock);SetPageDirty(); if (page_count!= 2put_page(); ||PageDirty())Quoted 8 lines
Quoted 1 line
Now I'm worried that 2 might see PageDirty *before* SetPageDirty in
page->flagsQuoted 1 line
1, and
page_count*after*put_pagein 1.I think you're right. But I'm the last person to ask barrier/ordering questions of. CC'ed Ben and Andrea.
Quoted 7 lines
yup, now the question is wether
PG_Dirtywill be visible to CPU 2 before the page count is decremented right ? That depends onput_page, I suppose. If it's doing a simple atomic, there is an issue. But atomics with return has been so often abused as locks that they may have been implemented with a barrier... (On ppc64, it will do an eieio, thus I think it should be ok).
Well yes, that's on the store side (1, above). However can't a CPU still speculatively (eg. guess the branch) load the page->flags cacheline which might be satisfied from memory before the page->count cacheline loads? Ie. you can still have the correct write ordering but have incorrect read ordering?
Because neither PageDirty nor page_count is a barrier, and there is no read barrier between them.
Nick
Signature · 3 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Quoted 9 lines · Nick Piggin
Well yes, that's on the store side (1, above). However can't a CPU still speculatively (eg. guess the branch) load the
page->flagscacheline which might be satisfied from memory before thepage->countcacheline loads? Ie. you can still have the correct write ordering but have incorrect read ordering?Because neither PageDirty nor
page_countis a barrier, and there is no read barrier between them.
Yes you're right. A read barrier is required here.
I think Ben was actually agreeing with you. He's just questioning whether the corresponding write barrier existed on CPU 1 (the answer to which is affirmative).
Cheers,
Signature · 4 lines
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txtQuoted 12 lines · Herbert Xu
Quoted 8 lines · Nick Piggin
Well yes, that's on the store side (1, above). However can't a CPU still speculatively (eg. guess the branch) load the
page->flagscacheline which might be satisfied from memory before thepage->countcacheline loads? Ie. you can still have the correct write ordering but have incorrect read ordering?Because neither PageDirty nor
page_countis a barrier, and there is no read barrier between them.
Quoted 6 lines
Yes you're right. A read barrier is required here.
I think Ben was actually agreeing with you. He's just questioning whether the corresponding write barrier existed on CPU 1 (the answer to which is affirmative).
Ah, that clears up my misunderstanding.
Yes I agree the write side is OK.
Thanks Ben and Herbert. I guess I should do a proper patch then.
Signature · 1 line
SUSE Labs, Novell Inc.
In mm/vmscan.c, the page reclaim may have the following sequence 2 running concurrently with sequence 1 on another CPU:
1 2find_get_page();
write to page write_lock(tree_lock);SetPageDirty(); if (page_count != 2put_page(); || PageDirty())
/* page dirty or busy */ else /* free it */
The comment indicates that PageDirty must be checked *after* page_count indicates there are no users of this page, which prevents the dirty bit from being lost in the case that that sequence 2 might see the state of PageDirty() *before* SetPageDirty() in 1, but page_count *after* put_page in 1.
However, there is no read memory barrier there, and so nothing to stop a CPU from loading page_count before PageDirty (ie. ->flags). Theoretically, data corruption is possible.
mm/vmscan.c +6 -1
@@ -511,7 +511,12 @@ static int shrink_list(struct list_head* PageDirty _after_ making sure that the page is freeable and * not in use by anybody. (pagecache + us == 2) */ -if (page_count (page) !=2 ||PageDirty (page)) { +if (page_count (page) !=2 ) { +write_unlock_irq (&mapping->tree_lock); + goto keep_locked; + } +smp_rmb (); +if (PageDirty (page)) {write_unlock_irq (&mapping->tree_lock); goto keep_locked; }
Quoted 8 lines · Herbert Xu
Quoted 7 lines · Nick Piggin
Well yes, that's on the store side (1, above). However can't a CPU still speculatively (eg. guess the branch) load the
page->flagscacheline which might be satisfied from memory before thepage->countcacheline loads? Ie. you can still have the correct write ordering but have incorrect read ordering?
Quoted 4 lines
Quoted 2 lines
Because neither PageDirty nor
page_countis a barrier, and there is no read barrier between them.Yes you're right. A read barrier is required here.
Even a write barrier is required on the left side, the read barrier on the right side is useless if there is no write barrier on the left side.
Note that the barrier in atomic_add_negative is useless here because it happens way too late, _after_ the count is decremented (not _before_) so the decreased count could be already visible to the other cpu.
Not all archs are like x86 where a barrier happens implicitly both before and after the instruction, and the way atomic_add_negative is implemented the barrier from a common code point of view is only added _after_ the instruction.
Quoted 4 lines · Andrea Arcangeli
Note that the barrier in
atomic_add_negativeis useless here because it happens way too late, _after_ the count is decremented (not _before_) so the decreased count could be already visible to the other cpu.
Could you please point me to an architecture that does this?
This assumption is in fact made in a number of places in the kernel where constructs such as atomic_add_negative or atomic_dec_and_test are used and assumed to imply a memory barrier.
Thanks,
Signature · 4 lines
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txtQuoted 7 lines · Herbert Xu
Quoted 4 lines · Andrea Arcangeli
Note that the barrier in
atomic_add_negativeis useless here because it happens way too late, _after_ the count is decremented (not _before_) so the decreased count could be already visible to the other cpu.Could you please point me to an architecture that does this?
sure see alpha:
__asm__ __volatile__( "1: ldq_l %0,%1\n" " addq %0,%3,%2\n" " addq %0,%3,%0\n" " stq_c %0,%1\n" " beq %0,2f\n" " mb\n"
the memory barrier is applied way after the write is visible to other cpus, you can even get an irq before the mb and block there for some usec.
Quoted 1 line
From a common code point of view, the barrier you mentioned in
atomic_add_negative is absolutely useless for this specific case (setpagedirty+put_page)
From: Andrea Arcangeli <[email protected]>
Date: Sat, 15 Oct 2005 22:07:01 +0200
Quoted 10 lines
sure see alpha:
__asm__ __volatile__( "1: ldq_l %0,%1\n" " addq %0,%3,%2\n" " addq %0,%3,%0\n" " stq_c %0,%1\n" " beq %0,2f\n" " mb\n"
Quoted 3 lines
the memory barrier is applied way after the write is visible to other cpus, you can even get an irq before the mb and block there for some usec.
For atomic operations returning values, there must be a memory barrier both before and after the atomic operation. This is defined in Documentation/atomic_ops.txt, so Alpha needs to be fixed to add a memory barrier at the beginning of these assembler sequences.
Quoted 17 lines · David S. Miller
From: Andrea Arcangeli <[email protected]>
Date: Sat, 15 Oct 2005 22:07:01 +0200Quoted 10 lines
sure see alpha:
__asm__ __volatile__( "1: ldq_l %0,%1\n" " addq %0,%3,%2\n" " addq %0,%3,%0\n" " stq_c %0,%1\n" " beq %0,2f\n" " mb\n"Quoted 3 lines
the memory barrier is applied way after the write is visible to other cpus, you can even get an irq before the mb and block there for some usec.
Quoted 5 lines
For atomic operations returning values, there must be a memory barrier both before and after the atomic operation. This is defined in
Documentation/atomic_ops.txt, so Alpha needs to be fixed to add a memory barrier at the beginning of these assembler sequences.
My opinion is that we don't need a barrier even _after_ ll/sc sequences on Alpha - it's redundant; perhaps it's just a historical baggage. I strongly believe that ll/sc _does_ imply an SMP memory barrier, as can be seen from instructions timing: a standalone mb takes tens of cycles, the mb before/after ll/sc takes 0 to 1 cycle on ev6 (a bit more on ev56) depending on instruction slotting.
Note that superfluous mb's around atomic stuff still can hurt - Alpha mb instruction also flushes IO write buffers, so it can be _extremely_ expensive under heavy IO...
Ivan.
From: Ivan Kokshaysky <[email protected]>
Date: Sun, 16 Oct 2005 23:36:00 +0400
Quoted 9 lines
My opinion is that we don't need a barrier even _after_ ll/sc sequences on Alpha - it's redundant; perhaps it's just a historical baggage. I strongly believe that ll/sc _does_ imply an SMP memory barrier, as can be seen from instructions timing: a standalone mb takes tens of cycles, the mb before/after ll/sc takes 0 to 1 cycle on ev6 (a bit more on ev56) depending on instruction slotting.
Note that superfluous mb's around atomic stuff still can hurt - Alpha mb instruction also flushes IO write buffers, so it can be _extremely_ expensive under heavy IO...
Even a quick google tells me that on Alpha, LL/SC have implicit barriers only with respect to the locations being acted upon by the LL/SC, but don't have more general barrier properties.
This is in line with how PPC is defined as well.
I truly believe that you would be removing those Alpha memory barriers only at your own peril. :-) And since the PPC and Alpha defined semantics aparently match, I think it would be wise to add the missing memory barriers from the front of the LL/SC sequences which need them, just as PPC does.
I just spent 6 months tracking down a bug that turned out to be a couple of missing memory barriers on sparc64. So, this has taught me to be extra careful in this area :-) I really think this is an area in which it's better to be safe than sorry.
Quoted 3 lines · David S. Miller
Even a quick google tells me that on Alpha, LL/SC have implicit barriers only with respect to the locations being acted upon by the LL/SC, but don't have more general barrier properties.
Argh, you are right - I should have read the manual before posting...
Ivan.
Quoted 2 lines · Ivan Kokshaysky
Note that superfluous mb's around atomic stuff still can hurt - Alpha mb instruction also flushes IO write buffers, so it can
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
That's what needed to implement the wmb on alpha, this is why mb is needed there and we need to add it at the top as well to comply with docs (and especially for atomic_dec_and_test kind of usage like Dave said).
Ivan I assume you'll take care of fixing it, thanks!
Quoted 7 lines
Even a write barrier is required on the left side, the read barrier on the right side is useless if there is no write barrier on the left side.
Note that the barrier in
atomic_add_negativeis useless here because it happens way too late, _after_ the count is decremented (not _before_) so the decreased count could be already visible to the other cpu.
Not on ppc64. Our atomic*return functions have a write barrier before the atomic operation. I think there is just too much code out there that either expects implicit barriers done by atomics (abuse them as locks) or simply written by people who don't understand those ordering issues (to be fair, they can be fairly brain damaging).
I agree this is not a good generic solution though.
Quoted 4 lines
Not all archs are like x86 where a barrier happens implicitly both before and after the instruction, and the way
atomic_add_negativeis implemented the barrier from a common code point of view is only added _after_ the instruction.
From: Benjamin Herrenschmidt <[email protected]>
Date: Sun, 16 Oct 2005 08:16:30 +1000
Quoted 8 lines
Quoted 6 lines
Even a write barrier is required on the left side, the read barrier on the right side is useless if there is no write barrier on the left side.
Note that the barrier in
atomic_add_negativeis useless here because it happens way too late, _after_ the count is decremented (not _before_) so the decreased count could be already visible to the other cpu.Not on ppc64.
Or sparc64, or ppc, or ... any platform that adheres to the rules specified in Documentation/atomic_ops.txt :-)
One really needs the barriers both before and after the atomic operation when you return a value, because this is the only way to get sane semantics for dropping the final reference to some object. When one does:
if (atomic_dec_and_test(&obj->count)) __free_stuff(obj);
All other modifications to object state before the atomic decrement must reach global visibility _first_, and then the atomic decrement itself must be strongly ordered wrt. future memory operations.
That's why it is documented that the memory barriers both before and after the atomic operation are required when the operation returns a result value of some kind.
There is a lot of code in the kernel that depends upon this.