Skip to contentSkip to conversation

What was the problem with quicklists and x86-64?

DISCUSSION Jeremy Fitzhardinge 4 participants 14 messages Dec 12, 2007 – Dec 13, 2007

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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

#1 lore raw
Quoted 7 lines · 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.

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.

include/linux/quicklist.h +0 -8
Index: linux-2.6/include/linux/quicklist.h
===================================================================
@@ -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;
#2 lore raw
Quoted 10 lines · Christoph Lameter
Quoted 7 lines · 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.

Quoted 6 lines

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.

#3 lore raw
Quoted 11 lines · Benjamin Herrenschmidt
Quoted 6 lines

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.

#4 lore raw
Quoted 9 lines · Christoph Lameter
Quoted 7 lines · Benjamin Herrenschmidt
Quoted 6 lines

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).

Quoted 8 lines
Quoted 4 lines

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.

#5 lore raw
Quoted 11 lines · Benjamin Herrenschmidt
Quoted 3 lines

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?

#6 lore raw
Quoted 8 lines · Christoph Lameter
Quoted 2 lines

Ah ok, so that's a NUMA issue due to how the quicklists are

implemented,

Quoted 1 line

I see. Note that the flush isn't necessary a solution on all

platforms.

Quoted 1 line

On powerpc, I -still- need to defer with RCU as we don't do anything

in

Quoted 1 line

flush tlb. Our TLB invalidations are HW broadcast in the first

Quoted 8 lines

place,

Quoted 3 lines

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.

#7 lore raw
Quoted 5 lines · Benjamin Herrenschmidt
Quoted 3 lines

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?

#8 lore raw
Quoted 10 lines · Christoph Lameter
Quoted 5 lines · Benjamin Herrenschmidt
Quoted 3 lines

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.

#9 lore raw
Quoted 2 lines · Benjamin Herrenschmidt

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.

#10 lore raw
Quoted 6 lines · Christoph Lameter
Quoted 2 lines · Benjamin Herrenschmidt

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.

#11 lore raw
In reply to Christoph Lameter
Quoted 6 lines · Christoph Lameter
Quoted 4 lines · 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.

Quoted 8 lines
Quoted 3 lines

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

#12 lore raw
Quoted 11 lines · Suresh B

<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:

(quoted diff) +1 -1
-#define __pte_free_tlb(tlb,pte) tlb_remove_page((tlb),(pte))
+#define __pte_free_tlb(tlb,pte) quicklist_free_page(QUICK_PT, NULL,(pte))
Quoted 2 lines

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.

Quoted 10 lines

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?

include/asm-generic/tlb.h +4 -0
Index: linux-2.6/include/asm-generic/tlb.h
===================================================================
@@ -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 */
#13 lore raw
In reply to Jeremy Fitzhardinge
Quoted 7 lines · 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.

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

Quoted 4 lines

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.

Quoted 5 lines

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