What was the problem with quicklists and x86-64?
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
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
da8f153e51290e7438ba7da66234a864e5d3e1c1reverted 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
@@ -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;
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
da8f153e51290e7438ba7da66234a864e5d3e1c1reverted 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_64implementation (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.
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_64implementation (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.
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_64implementation (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.
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?
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.
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?
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.
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.
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.
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
da8f153e51290e7438ba7da66234a864e5d3e1c1reverted 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_64implementation (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
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 markingtlb->need_flush. Which is later used bytlb_flush_mmu(). Withquicklist_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 callsunmap_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()callscheck_pgt_cache()which trims quicklist ]
with out flushing the TLB's.
[ (tlb_finish_mmu()calls thetlb_flush_mmu()but it will not do
much asneed_flushis 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
@@ -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, unstatic 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 */
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
da8f153e51290e7438ba7da66234a864e5d3e1c1reverted 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