What was the problem with quicklists and x86-64?

What was the problem with quicklists and x86-64?

[Jeremy Fitzhardinge]

I'm looking at unifying the various pgalloc+pgd_lists mechanisms between
32-bit (PAE and non-PAE) and 64-bit, so I'm trying to understand why
these differences exist in the first place.

Change da8f153e51290e7438ba7da66234a864e5d3e1c1 reverted the use of
quicklists for allocating pagetables, because of concerns about ordering
with respect to tlb flushes.

Some questions about this:

   1. What's the difference between quicklists and normal page
      allocation with respect to tlb flushing?
   2. Why doesn't this also affect i386's use of quicklists?
   3. Is there some way to resolve this tlb interaction so that
      quicklists can be used?
   4. Failing that, what's the cost of reverting i386's use of
      quicklists too?


Thanks,
    J

Re: What was the problem with quicklists and x86-64?

[Christoph Lameter]

On Wed, 12 Dec 2007, Jeremy Fitzhardinge wrote:

> I'm looking at unifying the various pgalloc+pgd_lists mechanisms between
> 32-bit (PAE and non-PAE) and 64-bit, so I'm trying to understand why
> these differences exist in the first place.
> 
> Change da8f153e51290e7438ba7da66234a864e5d3e1c1 reverted the use of
> quicklists for allocating pagetables, because of concerns about ordering
> with respect to tlb flushes.

These issues only exist with NUMA because of the freeing of off node pages 
before the TLB flush was done. There was a discussion about this issue and 
my fix of simply not freeing the offnode pages early was ignored. Instead 
the x86_64 implementation (which has no problems that I know of) was 
pulled leaving the issue open in the core. Benjamin Herrrenschmidt 
wanted to take a look at these issues (CCing him).

Here is the fix again. Could we please reapply the x86_64 quicklist 
patch after applying this one? (I have another patch in testing that 
maintains separate lists for off and on node pages and frees all off node 
pages on flush but that one adds new capabilities).

http://marc.info/?t=119039827700001&r=1&w=2



[NUMA] quicklists: Do not release off node pages early

quicklists must keep even off node pages on the quicklists until the TLB flush
has been completed.

Signed-off-by: Christoph Lameter <clameter@sgi.com>

Index: linux-2.6/include/linux/quicklist.h
===================================================================
--- linux-2.6.orig/include/linux/quicklist.h	2007-12-13 11:42:21.000000000 -0800
+++ linux-2.6/include/linux/quicklist.h	2007-12-13 11:42:37.000000000 -0800
@@ -56,14 +56,6 @@ static inline void __quicklist_free(int 
 	struct page *page)
 {
 	struct quicklist *q;
-	int nid = page_to_nid(page);
-
-	if (unlikely(nid != numa_node_id())) {
-		if (dtor)
-			dtor(p);
-		__free_page(page);
-		return;
-	}
 
 	q = &get_cpu_var(quicklist)[nr];
 	*(void **)p = q->page;

Re: What was the problem with quicklists and x86-64?

[Benjamin Herrenschmidt]

On Thu, 2007-12-13 at 11:47 -0800, Christoph Lameter wrote:
> On Wed, 12 Dec 2007, Jeremy Fitzhardinge wrote:
> 
> > I'm looking at unifying the various pgalloc+pgd_lists mechanisms between
> > 32-bit (PAE and non-PAE) and 64-bit, so I'm trying to understand why
> > these differences exist in the first place.
> > 
> > Change da8f153e51290e7438ba7da66234a864e5d3e1c1 reverted the use of
> > quicklists for allocating pagetables, because of concerns about ordering
> > with respect to tlb flushes.
> 
> These issues only exist with NUMA because of the freeing of off node pages 
> before the TLB flush was done. There was a discussion about this issue and 
> my fix of simply not freeing the offnode pages early was ignored. Instead 
> the x86_64 implementation (which has no problems that I know of) was 
> pulled leaving the issue open in the core. Benjamin Herrrenschmidt 
> wanted to take a look at these issues (CCing him).

I don't know how NUMA gets in the picture there, it's probably very x86
specific thing. The issue we have here happens on other platforms
unrelated to NUMA. The fact that is tired to NUMA on x86 might be due to
the way the HW tablewalk operates on these. 

Essentially the problem is a processor walking the page table tree
(either in HW or in SW, but both without any lock) vs. freeing them.

The risk is that if we just clear the PMD entry (or any other level in
fact) and then right away free the PTE page (or any other page level) in
such a way that it can be re-used by something else pretty much
immediately, we have a race where the other processor might have started
to walk the page table tree, sampled the "old" PMD value, and then
starts accessing the PTE page that have been freed or even worse,
re-used.

The race is very hard to trigger, it will mostly happen on very out of
order architectures (such as powerpc) and you'd have to hammer addresses
that you are just unmapping (with is not something that happens in
practice), but it's been seen and can cause very bad results. 

The solution we use on powerpc to avoid it is to defer all page table
page freeing using RCU, since the part that walks the page table is SW
in the hash miss handler. On x86, the IPI & flush after clearing the PMD
entry and before freeing the page guarantees also that no other CPU is
still walking the thing with the old PMD value.

Ben.

Re: What was the problem with quicklists and x86-64?

[Christoph Lameter]

On Fri, 14 Dec 2007, Benjamin Herrenschmidt wrote:

> > These issues only exist with NUMA because of the freeing of off node pages 
> > before the TLB flush was done. There was a discussion about this issue and 
> > my fix of simply not freeing the offnode pages early was ignored. Instead 
> > the x86_64 implementation (which has no problems that I know of) was 
> > pulled leaving the issue open in the core. Benjamin Herrrenschmidt 
> > wanted to take a look at these issues (CCing him).
> 
> I don't know how NUMA gets in the picture there, it's probably very x86
> specific thing. The issue we have here happens on other platforms
> unrelated to NUMA. The fact that is tired to NUMA on x86 might be due to
> the way the HW tablewalk operates on these. 

This is a generic NUMA issue here! Quicklist pages that are not on 
the current node are freed without waiting for the TLB flush. The patch 
that I posted fixes that by requiring that all pages be flushed. 

Re: What was the problem with quicklists and x86-64?

[Siddha, Suresh B]

On Wed, Dec 12, 2007 at 11:14:41AM -0800, Jeremy Fitzhardinge wrote:
> I'm looking at unifying the various pgalloc+pgd_lists mechanisms between
> 32-bit (PAE and non-PAE) and 64-bit, so I'm trying to understand why
> these differences exist in the first place.
> 
> Change da8f153e51290e7438ba7da66234a864e5d3e1c1 reverted the use of
> quicklists for allocating pagetables, because of concerns about ordering
> with respect to tlb flushes.

Main thing to note is, while unmapping linear address space, we should not
free underlying pages, page table pages (for all hierarchies), till we flush
the active TLB caches in all the CPUs.

Violation of this can potentially cause SW failures and hard to debug issues
like
http://www.ussg.iu.edu/hypermail/linux/kernel/0205.2/1254.html

For more info, you can refer 
http://developer.intel.com/design/processor/applnots/317080.pdf

> Some questions about this:
> 
>    1. What's the difference between quicklists and normal page
>       allocation with respect to tlb flushing?

Linus and Christoph went in detail about this.

http://kerneltrap.org/mailarchive/linux-kernel/2007/9/21/271638

There were some preemption and other concerns that Linus mentioned,
and was referring to of integrating quicklists and mmu_gather operations
and not keep them separate.

>    2. Why doesn't this also affect i386's use of quicklists?
>    3. Is there some way to resolve this tlb interaction so that
>       quicklists can be used?
>    4. Failing that, what's the cost of reverting i386's use of
>       quicklists too?

I have to look at i386 code but I don't think it was using quicklists
as extensively as the previous x86_64 code does. Will take a look at it.

thanks,
suresh

Re: What was the problem with quicklists and x86-64?

[Benjamin Herrenschmidt]

On Thu, 2007-12-13 at 12:53 -0800, Christoph Lameter wrote:
> On Fri, 14 Dec 2007, Benjamin Herrenschmidt wrote:
> 
> > > These issues only exist with NUMA because of the freeing of off node pages 
> > > before the TLB flush was done. There was a discussion about this issue and 
> > > my fix of simply not freeing the offnode pages early was ignored. Instead 
> > > the x86_64 implementation (which has no problems that I know of) was 
> > > pulled leaving the issue open in the core. Benjamin Herrrenschmidt 
> > > wanted to take a look at these issues (CCing him).
> > 
> > I don't know how NUMA gets in the picture there, it's probably very x86
> > specific thing. The issue we have here happens on other platforms
> > unrelated to NUMA. The fact that is tired to NUMA on x86 might be due to
> > the way the HW tablewalk operates on these. 
> 
> This is a generic NUMA issue here! Quicklist pages that are not on 
> the current node are freed without waiting for the TLB flush. The patch 
> that I posted fixes that by requiring that all pages be flushed. 

Ah ok, so that's a NUMA issue due to how the quicklists are implemented,
I see. Note that the flush isn't necessary a solution on all platforms.
On powerpc, I -still- need to defer with RCU as we don't do anything in
flush tlb. Our TLB invalidations are HW broadcast in the first place,
but what we need to sync with is the SW hash reload code.

So your solution in the quicklists doesn't solve the problem for us.

Ben.

Re: What was the problem with quicklists and x86-64?

[Christoph Lameter]

On Fri, 14 Dec 2007, Benjamin Herrenschmidt wrote:

> > This is a generic NUMA issue here! Quicklist pages that are not on 
> > the current node are freed without waiting for the TLB flush. The patch 
> > that I posted fixes that by requiring that all pages be flushed. 
> 
> Ah ok, so that's a NUMA issue due to how the quicklists are implemented,
> I see. Note that the flush isn't necessary a solution on all platforms.
> On powerpc, I -still- need to defer with RCU as we don't do anything in
> flush tlb. Our TLB invalidations are HW broadcast in the first place,
> but what we need to sync with is the SW hash reload code.
> 
> So your solution in the quicklists doesn't solve the problem for us.

No this may mean that the problem does not exist on powerpc since it 
seems to be okay to free pages before all processors have flushed the 
TLBs? Or are you deferrring the freeing of the pages via RCU?

Re: What was the problem with quicklists and x86-64?

[Siddha, Suresh B]

On Thu, Dec 13, 2007 at 11:47:29AM -0800, Christoph Lameter wrote:
> On Wed, 12 Dec 2007, Jeremy Fitzhardinge wrote:
> 
> > I'm looking at unifying the various pgalloc+pgd_lists mechanisms between
> > 32-bit (PAE and non-PAE) and 64-bit, so I'm trying to understand why
> > these differences exist in the first place.
> > 
> > Change da8f153e51290e7438ba7da66234a864e5d3e1c1 reverted the use of
> > quicklists for allocating pagetables, because of concerns about ordering
> > with respect to tlb flushes.
> 
> These issues only exist with NUMA because of the freeing of off node pages 
> before the TLB flush was done. There was a discussion about this issue and 
> my fix of simply not freeing the offnode pages early was ignored. Instead 
> the x86_64 implementation (which has no problems that I know of) was 

NUMA  bug might not be the only problem. I think there are more issues
as Linus noticed.

<snip>
Oh, and I see what's wrong: you not only switched "free_page()" to 
"quicklist_free()", you *also* switched "tlb_remove_page()" to 
"quicklist_free()".
</snip>

The above comment is in reference to below portion of code:

-#define __pte_free_tlb(tlb,pte) tlb_remove_page((tlb),(pte))
+#define __pte_free_tlb(tlb,pte) quicklist_free_page(QUICK_PT, NULL,(pte))

tlb_remove_page() was marking tlb->need_flush. Which is later used
by tlb_flush_mmu(). With quicklist_free_page() we loose all that..

Now in a corner case scenario  with a big munmap() which calls unmap_region()
and if it so happens that the region getting unmapped just has page
tables setup but with all PTE's set to NULL, unmap_region() may
potentially free the page table pages
	[ tlb_finish_mmu() calls check_pgt_cache() which trims quicklist ]
with out flushing the TLB's.
	[ (tlb_finish_mmu() calls the tlb_flush_mmu() but it will not do
           much as need_flush is not set ]

Similarly Linus brought pre-emptions issues associated with quicklist usage..

thanks,
suresh

Re: What was the problem with quicklists and x86-64?

[Benjamin Herrenschmidt]

On Thu, 2007-12-13 at 13:33 -0800, Christoph Lameter wrote:
> > 
> > Ah ok, so that's a NUMA issue due to how the quicklists are
> implemented,
> > I see. Note that the flush isn't necessary a solution on all
> platforms.
> > On powerpc, I -still- need to defer with RCU as we don't do anything
> in
> > flush tlb. Our TLB invalidations are HW broadcast in the first
> place,
> > but what we need to sync with is the SW hash reload code.
> > 
> > So your solution in the quicklists doesn't solve the problem for us.
> 
> No this may mean that the problem does not exist on powerpc since it 
> seems to be okay to free pages before all processors have flushed the 
> TLBs? Or are you deferrring the freeing of the pages via RCU?

I'm deferring the freeing with RCU.

Ben.

Re: What was the problem with quicklists and x86-64?

[Christoph Lameter]

On Fri, 14 Dec 2007, Benjamin Herrenschmidt wrote:

> > No this may mean that the problem does not exist on powerpc since it 
> > seems to be okay to free pages before all processors have flushed the 
> > TLBs? Or are you deferrring the freeing of the pages via RCU?
> 
> I'm deferring the freeing with RCU.

The deferral works on a page level or for the whole list of pages that 
have been gathered?

Re: What was the problem with quicklists and x86-64?

[Christoph Lameter]

On Thu, 13 Dec 2007, Siddha, Suresh B wrote:

> <snip>
> Oh, and I see what's wrong: you not only switched "free_page()" to 
> "quicklist_free()", you *also* switched "tlb_remove_page()" to 
> "quicklist_free()".
> </snip>
> 
> The above comment is in reference to below portion of code:
> 
> -#define __pte_free_tlb(tlb,pte) tlb_remove_page((tlb),(pte))
> +#define __pte_free_tlb(tlb,pte) quicklist_free_page(QUICK_PT, NULL,(pte))
> 
> tlb_remove_page() was marking tlb->need_flush. Which is later used
> by tlb_flush_mmu(). With quicklist_free_page() we loose all that..

Aha. So we need to flush if there is a page on the quicklist. Patch 
follows.

> Now in a corner case scenario  with a big munmap() which calls unmap_region()
> and if it so happens that the region getting unmapped just has page
> tables setup but with all PTE's set to NULL, unmap_region() may
> potentially free the page table pages
> 	[ tlb_finish_mmu() calls check_pgt_cache() which trims quicklist ]
> with out flushing the TLB's.
> 	[ (tlb_finish_mmu() calls the tlb_flush_mmu() but it will not do
>            much as need_flush is not set ]
> 
> Similarly Linus brought pre-emptions issues associated with quicklist usage..

AFAICT page table shootdown cannot be preempted. What where the preemption issues?




Index: linux-2.6/include/asm-generic/tlb.h
===================================================================
--- linux-2.6.orig/include/asm-generic/tlb.h	2007-12-13 14:45:38.000000000 -0800
+++ linux-2.6/include/asm-generic/tlb.h	2007-12-13 14:51:07.000000000 -0800
@@ -14,6 +14,7 @@
 #define _ASM_GENERIC__TLB_H
 
 #include <linux/swap.h>
+#include <linux/quicklist.h>
 #include <asm/pgalloc.h>
 #include <asm/tlbflush.h>
 
@@ -85,6 +86,9 @@ tlb_flush_mmu(struct mmu_gather *tlb, un
 static inline void
 tlb_finish_mmu(struct mmu_gather *tlb, unsigned long start, unsigned long end)
 {
+#ifdef CONFIG_QUICKLIST
+	tlb->need_flush += &__get_cpu_var(quicklist)[0].nr_pages != 0;
+#endif
 	tlb_flush_mmu(tlb, start, end);
 
 	/* keep the page table cache within bounds */

Re: What was the problem with quicklists and x86-64?

[Benjamin Herrenschmidt]

On Thu, 2007-12-13 at 14:36 -0800, Christoph Lameter wrote:
> On Fri, 14 Dec 2007, Benjamin Herrenschmidt wrote:
> 
> > > No this may mean that the problem does not exist on powerpc since it 
> > > seems to be okay to free pages before all processors have flushed the 
> > > TLBs? Or are you deferrring the freeing of the pages via RCU?
> > 
> > I'm deferring the freeing with RCU.
> 
> The deferral works on a page level or for the whole list of pages that 
> have been gathered?

We have a separate batch to store page table pages with an RCU head on
it, we fire it off when it's full or when tlb gather is complete.

Ben.

Re: What was the problem with quicklists and x86-64?

[Christoph Lameter]

On Fri, 14 Dec 2007, Benjamin Herrenschmidt wrote:

> We have a separate batch to store page table pages with an RCU head on
> it, we fire it off when it's full or when tlb gather is complete.

full? You need to wait otill the tlb gather is complete.

Re: What was the problem with quicklists and x86-64?

[Benjamin Herrenschmidt]

On Thu, 2007-12-13 at 15:14 -0800, Christoph Lameter wrote:
> On Fri, 14 Dec 2007, Benjamin Herrenschmidt wrote:
> 
> > We have a separate batch to store page table pages with an RCU head on
> > it, we fire it off when it's full or when tlb gather is complete.
> 
> full? You need to wait otill the tlb gather is complete.

No, we fire it off with RCU, we don't need to wait for TLB gather to be
complete. All we care about is sync with other CPUs doing a page table
walk and it's enough for us. We do -not- need to synchronize with TLB
invalidations and we don't use IPIs for those anyway.

Ben.