RFC: RCU protected page table walking

On a TLB miss, we have got a

TLB = ... -> pgd[i] -> pud[j] -> pmd[k] -> pte[l]

chain to walk.
Some architectures do it in HW (microcode), some others in SW. This page table walking is not atomic, not even on an x86.

Let's consider the following scenario:

CPU #1: CPU #2: CPU #3

Starts walking
Got the ph. addr. of page Y
in internal reg. X
free_pgtables():
sets free page Y
Allocates page Y
Accesses page Y via reg. X

As CPU #1 is still keeping the same ph. address, it fetches an item from a page that is no more its page.

Even if this security window is small, it does exist.
We cannot base our security just on "quick" page table walking.
(How much quick it has to be?)
The probability to hit this bug grows higher on a NUMA machine with lots of CPUs.

If the HW page table walker cannot, the low level assembly routines do not take any lock, then only some "careful programming" in the PUD / PMD / PTE page removal code can help.

I propose an RCU based protection mechanism.
Some minor modifications will be necessary in the architecture dependent parts. I can only give an example for IA64.
I did not spend much effort on optimizing the real freeing routine called "do_free_pte_mpd_pud_pages()" because (among other reasons, see the comments), basically, I wanted to present my RCU based concept.

Thanks,

Zoltan Menyhart

@@ -264,9 +264,129 @@ void free_pgd_range(struct mmu_gather **

		flush_tlb_pgtables((*tlb)->mm, start, end);
}

+
+/*
+ * RCU protected page table walking.
+ * ---------------------------------
+ *
+ * Page table walking need protection, otherwise:
+ * - A first CPU, having reached somewhere in this chain walking, it has got
+ * the physical address of the next page in the chain in an internal register.
+ * - In the mean time, a second CPU executing "free_pgtables()", frees the page
+ * the first CPU is about to touch.
+ * - Someone re-uses the same page for something else.
+ * - The first CPU fetches an item from a page of someone else.
+ *
+ * PTE, PMD and PUD page usage perfectly fits into the RCU approach:
+ * - Page table walking is the read side
+ * - Allocating and un-mapping these pages is the update side
+ * - Really freeing these pages is the reclaim side
+ * PTE, PMD and PUD pages will be "put aside" by the un-mapping code until all
+ * pre-existing read-side critical sections on all CPUs have completed.
+ *
+ * Page table walking is (logically) carried out as follows:
+ *
+ * rcu_read_lock_bh();
+ * pud_p = rcu_dereference( pgd_p[i] );
+ * pmd_p = rcu_dereference( pud_p[j] );
+ * pte_p = rcu_dereference( pmd_p[k] );
+ * ...
+ * pte = *pte_p;
+ * ...
+ * rcu_read_unlock_bh();
+ *
+ * PTE, PMD and PUD page allocation, initialization and hooking them to their
+ * respective parent pages are carried out under some lock protection.
+ * Releasing this lock provides the required memory fencing semantics =>
+ * there is no need for explicit "rcu_assign_pointer()" usage.
+ *
+ * The "p??_free()" subroutines invoked by "free_pgtables()" indirectly, do not
+ * actually set free the PTE, PMD and PUD pages.
+ * Instead, they "put aside" them in order to give a grace period for the read
+ * sides. "free_pgtables()" kicks off an RCU activated service to reclaim the
+ * PTE, PMD and PUD pages later.
+ *
+ * Notes:
+ * - The life span of the PTE, PMD and PUD pages is rather long:
+ * they are freed when the usage of the memory area ceases, provided no other
+ * map (using the same PTE, PMD and PUD pages) is valid.
+ * - The number of the PTE, PMD and PUD pages is much more smaller that that of
+ * the leaf pages.
+ * Therefore freeing them is not really performance critical.
+ */
+
+#if defined(CONFIG_SMP)
+
+/*
+ * A singly linked ring of the PTE, PMD and PUD pages, which are going to be
+ * reclaimed, is anchored by the "pages" field.
+ * This ring is formed by use of "->lru.next".
+ * Note that "next" points at the next page structure, not at the list head.
+ */
+struct rcu_free_pte_mpd_pud_pages {
+ struct rcu_head rcu;
+ struct page *pages;
+};
+
+#endif
+
+/*
+ * The actual freeing service for the PTE, PMD and PUD pages.
+ *
+ * This is not a performance critical routine:
+ * - these pages are freed much less frequently than the leaf pages are
+ * - the number of these pages are much less than that of the leaf pages
+ */
+void do_free_pte_mpd_pud_pages(struct page * const first_page)
+{
+ struct page *p = first_page;
+ struct page *next;
+
+ do {
+ next = (struct page *)(p->lru.next);
+ free_page((unsigned long) page_address(p));
+// pgtable_quicklist_free(page_address(p));
+ } while ((p = next) != first_page);
+}
+
+#if defined(CONFIG_SMP)
+
+/*
+ * This is the RCU reclaim end of freeing PTE, PMD and PUD pages on SMP systems.
+ */
+void rcu_free_pte_mpd_pud_pages(struct rcu_head *rcup)
+{
+ const struct rcu_free_pte_mpd_pud_pages * const rp =
+ container_of(rcup, struct rcu_free_pte_mpd_pud_pages, rcu);
+
+ do_free_pte_mpd_pud_pages(rp->pages);
+ kfree(rcup);
+}
+
+#endif // #if defined(CONFIG_SMP)
+
+/*
+ * Here comes the comment explaining what "free_pgtables()" does,
+ * why, how, etc. :-)
+ *
+ * This is the RCU update end of freeing the PTE, PMD and PUD pages:
+ * The "p??_free()" subroutines do not actually set free these pages,
+ * instead, they add them onto the list "current->pages_rcu_free".
+ * For a multi-threaded process on SMP systems, the PTE, PMD and PUD pages
+ * will be set free via a "call_rcu_bh()"-activated service.
+ * The currently active reader ends are guaranteed to find their good old
+ * PTE, PMD and PUD pages at their actual physical addresses.
+ * (For kernel processes this protection is not available - you should not
+ * unmap an in-use kernel memory zone.)
+ */
void free_pgtables(struct mmu_gather **tlb, struct vm_area_struct *vma,
unsigned long floor, unsigned long ceiling)
{
+ struct mm_struct * const mm = vma->vm_mm;
+#if defined(CONFIG_SMP)
+ struct rcu_free_pte_mpd_pud_pages *rp;
+#endif
+

	while (vma) {
		struct vm_area_struct *next = vma->vm_next;
		unsigned long addr = vma->vm_start;
@@ -297,6 +417,62 @@ void free_pgtables(struct mmu_gather **t
		}
		vma = next;
	}

+#if defined(CONFIG_SMP)
+ /*
+ * For a multi-threaded process on SMP systems, the PTE, PMD and PUD
+ * pages will be set free via a "call_rcu_bh()"-activated service.
+ * If this is the last thread => no need for this protection.
+ * (For kernel processes, with "mm == &init_mm", this protection is not
+ * available - you should not unmap an in-use kernel memory zone.)
+ * Note that reading "mm_users" below is unsafe.
+ * If the other threads exit in the mean time, than we call the RCU
+ * service and we waste our time in vain.
+ */
+ if (atomic_read(&mm->mm_users) <= 1 || unlikely(mm == &init_mm)){
+ if (current->pages_rcu_free != NULL){
+ do_free_pte_mpd_pud_pages(current->pages_rcu_free);
+ current->pages_rcu_free = NULL;
+ }
+ /* May happen to a multi-threaded process only: */
+ if (unlikely(mm->pages_rcu_free != NULL)){
+ do_free_pte_mpd_pud_pages(mm->pages_rcu_free);
+ mm->pages_rcu_free = NULL;
+ }
+ return;
+ }
+ /*
+ * We get here for the multi-threaded processes only, with
+ * (most likely) more than 1 active threads.
+ */
+ if (likely(mm->pages_rcu_free == NULL)){
+ if (current->pages_rcu_free == NULL)
+ return;
+ mm->pages_rcu_free = current->pages_rcu_free;
+ current->pages_rcu_free = NULL;
+ } else if (current->pages_rcu_free != NULL){
+ /*
+ * Merge the two rings. "->lru.prev" is just a temporary storage.
+ */
+ mm->pages_rcu_free->lru.prev = current->pages_rcu_free->lru.next;
+ current->pages_rcu_free->lru.next = mm->pages_rcu_free->lru.next;
+ mm->pages_rcu_free->lru.next = mm->pages_rcu_free->lru.prev;
+ current->pages_rcu_free = NULL;
+ }
+ /*
+ * If there is no more memory, then try to free these pages later.
+ * At the very latest, "exit_mmap()" will be able to do it.
+ */
+ if (unlikely((rp = kmalloc(sizeof(*rp), GFP_KERNEL)) == NULL))
+ return;
+ rp->pages = mm->pages_rcu_free;
+ mm->pages_rcu_free = NULL;
+ call_rcu_bh(&rp->rcu, rcu_free_pte_mpd_pud_pages);
+#else // #if defined(CONFIG_SMP)
+ if (current->pages_rcu_free != NULL){
+ do_free_pte_mpd_pud_pages(current->pages_rcu_free);
+ current->pages_rcu_free = NULL;
+ }
+#endif // #if defined(CONFIG_SMP)
}

int __pte_alloc(struct mm_struct *mm, pmd_t *pmd, unsigned long address)

@@ -37,6 +37,28 @@
 *
 * Table is based upon EAS2.6 (Oct 1999)
 */
+/*
+ * RCU protected page table walking.
+ * ---------------------------------
+ *
+ * (For further details see "mm/memory.c".)
+ *
+ * Page table walking is (logically) carried out as follows:
+ *
+ *	rcu_read_lock_bh();
+ *	pud_p = rcu_dereference( pgd_p[i] );
+ *	pmd_p = rcu_dereference( pud_p[j] );
+ *	pte_p = rcu_dereference( pmd_p[k] );
+ *	...
+ *	pte = *pte_p;
+ *	...
+ *	rcu_read_unlock_bh();
+ *
+ * Notes:
+ *	- the RCU read lock semantics is provided by disabling the interrupts
+ *	- "rcu_dereference()" includes "smp_read_barrier_depends()" that is a
+ *	  no-op for ia64
+ */
 

#include <linux/config.h>

@@ -76,6 +76,23 @@ static inline void pgtable_quicklist_fre

	preempt_enable();
}

+/*
+ * The PTE, PMD and PUD pages are not actually set free here.
+ * Instead, they are added onto the singly linked ring anchored by
+ * "current->pages_rcu_free". This ring is formed by use of "->lru.next".
+ * Note that "next" points at the next page structure, not at the list head.
+ */
+static inline void p___free(struct page * const p)
+{
+ if (current->pages_rcu_free == NULL){
+ current->pages_rcu_free = p;
+ p->lru.next = (struct lish_head *) p;
+ } else {
+ p->lru.next = current->pages_rcu_free->lru.next;
+ current->pages_rcu_free->lru.next = (struct lish_head *) p;
+ }
+}
+
static inline pgd_t *pgd_alloc(struct mm_struct *mm)

{
	return pgtable_quicklist_alloc();

@@ -100,7 +117,7 @@ static inline pud_t *pud_alloc_one(struc

static inline void pud_free(pud_t * pud)
{
- pgtable_quicklist_free(pud);
+ p___free(virt_to_page(pud));
}
#define __pud_free_tlb(tlb, pud) pud_free(pud)
#endif /* CONFIG_PGTABLE_4 */
@@ -118,7 +135,7 @@ static inline pmd_t *pmd_alloc_one(struc

static inline void pmd_free(pmd_t * pmd)
{
- pgtable_quicklist_free(pmd);
+ p___free(virt_to_page(pmd));
}

#define __pmd_free_tlb(tlb, pmd) pmd_free(pmd)
@@ -149,9 +166,14 @@ static inline pte_t *pte_alloc_one_kerne

static inline void pte_free(struct page *pte)
{
- pgtable_quicklist_free(page_address(pte));
+ p___free(pte);
}

+/*
+ * The only known usage of this function is in case of a failure in
+ * "__pte_alloc_kernel()", therefore it is not included into the "careful"
+ * page freeing mechanism.
+ */
static inline void pte_free_kernel(pte_t * pte)

{
	pgtable_quicklist_free(pte);

@@ -313,7 +313,10 @@ struct mm_struct {

* together off init_mm.mmlist, and are protected
* by mmlist_lock
*/
-
+ struct page *pages_rcu_free; /* free_pgtables() collects PTE, PMD and
+ * PUD pages - protected by mmap_sem
+ * taken for write
+ */

	/* Special counters, in some configurations protected by the
	 * page_table_lock, in other configurations by being atomic.
	 */
@@ -871,6 +874,8 @@ struct task_struct {
#endif
	atomic_t fs_excl;	/* holding fs exclusive resources */
	struct rcu_head rcu;

+ struct page *pages_rcu_free; /* free_pgtables() collects */
+ /* PTE, PMD and PUD pages */
};

static inline pid_t process_group(struct task_struct *tsk)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

s page table walking is not atomic, not even on an x86.

The page is not freed until all CPUs who had the mm mapped are flushed. See mmu_gather in asm-generic/tlb.h

It doesn't at least on architectures that use the generic tlbflush.h

-Andi

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Those architectures (including i386 and x86_64) which #define their __pte_free_tlb etc. to tlb_remove_page are safe as is. But Zoltan's ia64 #defines it to pte_free, which looks like it may free_page before the TLB flush. But it is surprising if it has actually been unsafe there on ia64 - perhaps Christoph can explain how it is safe?

Hugh

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Sorry but I am in .au right now with spotty high latency connectivity. But the people on linux-ia64 should know. Ken?

Why was linux-ia64 not cced??

Christoph Lameter wrote on Wednesday, May 03, 2006 4:54 PM

A while back ia64 reinstated per-cpu pgtable quicklist, which bypasses tlb_gather/tlb_finish_mmu for page table pages. It should be safe AFAICT
because TLB for user address and vhpt are already flushed by the time
pte_free_tlb() is called.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Right you are, it was using tlb_remove_page until 2.6.12. Forgive me, but that makes me a little more suspicious of whether it is now safe.

I'm ia64-challenged, so VHPT is no more than a name to me; but I can easily believe that on ia64, once the pte has been cleared and the user address flushed from the TLB, then the page tables can be freed without waiting on further flushing.

However, are you sure that the TLB for user address has already been flushed at that point? There is not necessarily any tlb_finish_mmu call in between the last tlb_remove_page of unmap_vmas and the first pte_free_tlb of free_pgtables.

Hugh

Hugh

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Page table walking is in ph. mode, e.g. a PGD access is not sensitive to a TLB purge.

Here is the (simplified) IA64 implementation:

       free_pgtables(&tlb,...):
           free_pgd_range(tlb,...):
               free_pud_range(*tlb,...):
                   free_pmd_range(tlb,...):
                       free_pte_range(tlb,...):
                           pmd_clear(pmd);
                           pte_free_tlb(tlb, page):
                               __pte_free_tlb(tlb, ptep):
/* --> */                           pte_free(pte);
                       pud_clear(pud);
                       pmd_free_tlb(tlb, pmd):
/* --> */                   pmd_free(pmd);
                   pgd_clear(pgd);
                   pud_free_tlb(tlb, pud):
                       __pud_free_tlb(tlb, pudp):
/* --> */                   pud_free(pud);
               flush_tlb_pgtables((*tlb)->mm,...);

Or if you like, from asm-generic/tlb.h:

	tlb_remove_page(tlb, page):
	    if (tlb_fast_mode(tlb)) {
	        free_page_and_swap_cache(page);
	        return;
	    }
	    tlb->pages[tlb->nr++] = page;
	    if (tlb->nr >= FREE_PTE_NR)
	        tlb_flush_mmu(tlb, 0, 0):

	            free_pages_and_swap_cache(tlb->pages, tlb->nr);

As you can see, we do not care for the the eventual page table walkers.

As I showed above, the generic code is unaware of the other CPU's activity.

The problem is:
there is no requirement when we can release a directory page.

What I propose is a way to make sure that the page table walkers will be able to finish their walks in safety; we release a directory page when no more walker can reference the page.

Thanks,

Zoltan

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I cannot agree with you. Here is the generic sequence:

   tlb_remove_page(tlb, page):
       if (tlb_fast_mode(tlb)) {
           free_page_and_swap_cache(page);
           return;
       }
       tlb->pages[tlb->nr++] = page;
       if (tlb->nr >= FREE_PTE_NR)
           tlb_flush_mmu(tlb, 0, 0):

               free_pages_and_swap_cache(tlb->pages, tlb->nr); 

We set free the PTE, PMD and PUD pages either immediately or when tlb->pages[] is full.

What can make sure that there is no active page table walker on another CPU?

Thanks,

Zoltan

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

We don't free the pages until the other CPUs have been flushed synchronously. After the flush the other CPUs don't walk pages anymore. The whole thing is batched because the synchronous flush can be pretty expensive.

-Andi

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Do you mean the TLB entries mapping the leaf pages? If yes, then I agree with you about them.
Yet I speak about the directory pages. Let's take an example:

Assume:
- A process with 2 threads, bound to their respective CPUs
- One of them mapped a file and
this mapping requires a new PMD and a new PTE page
- They read in some data pages
- Time goes by without ever touching any of these pages again
- The swapped removes the data pages (data flush, TLB purge)
- (on IA64: due to the TLB pressure, the TLB entry mapping the PTE page gets killed)

There is no valid TLB entry concerning this mapped zone any more => the TLB purges around "free_pgtables()" can be considered as NO-OP-s. (In addition, walking the page tables in physical mode is insensitive to any TLB purges.)

CPU #1 faults on attempting to touch this mapped zone.
CPU #1 starts to walk the page tables in physical mode.
Assume it has got the address of the PMD page, it is about to fetch "pmd[j]".

CPU #2 executes "free_pgtables()" in the mean time: it sets free the PTE and the PGD pages (without knowing that CPU #1 has already got a PMD pointer).

Someone else allocates these two pages and fills them in with some data.

CPU #1 now fetches "pmd[j]" from a page of someone else. Without noticing anything, CPU #1 uses the illegal value to continue to access the PTE page.

Can you explain please why they do not?
There is a possibility that walking has already been started, but it has not been completed yet, when "free_pgtables()" runs.

Walking the page tables in physical mode is insensitive to any TLB purges, therefore these purges do not make sure that there is no other CPU just in the middle of page table walking.

I do a similar batching of the pages to be set free.
The RCU mechanism makes sure that these pages will not be freed before the already started page table walkers finish their job.

Thanks,

Zoltan

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

x86 uses this for the directory pages too (well for PMD/PUD - PGD never goes away until final exit). Actually x86-64 didn't
fully at some point and it resulted in a nasty to track down bug. But it was fixed then. I really went all over this with a very fine comb back then and I'm pretty sure it's correct now :)

Because the PGD/PMD/PUD has been rewritten and they won't be able to find the old pages anymore. They also don't have it in their TLBs because that has been flushed.

The problem I had on x86-64 was because visible the AMD CPUs internally cached PMD/PGDs.

Yes, that is why we delay the freeing of the pages to prevent anything going wrong.

What do you mean with "physical mode"?

A TLB Flush stops all MMU activity - or rather waits for it to finish.

-Andi

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

ia64 has a software page table walker in ivt.S. It does its work using physical addresses.

Robin

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

The i386 branch:

tlb_remove_page():
// assuming !tlb_fast_mode(tlb)
tlb_flush_mmu():

       tlb_flush():
           flush_tlb_mm():
               __flush_tlb();

free_pages_and_swap_cache();

__flush_tlb():

	"movl %%cr3, %0;
	"movl %0, %%cr3;  # flush TLB

Do I understand correctly that it purges the local TLBs only?

Can you please indicate how the page table walking of the other CPUs is "aborted"?

Can you please point me where it is documented that the HW walkers abort on a TLB flush / purge?

Yet I did verify that it is not (always) the case for the RISC-s.

E.g. arch/ia64/kernel/ivt.S:

ENTRY(vhpt_miss)
...

	// r17 = pmd_offset(pud, addr)

// -->
(p7) ld8 r20=[r17] // get *pmd (may be 0)

Assume we have reached the point indicated by "// -->":
we have got a valid address for the next level. Assume "free_pgtables()" sets free these PMD / PTE pages. The eventual TLB flushes do not do anything to the "ld8" going to be executed.

Can you explain please why you think that walking the

	rx = ... -> pgd[i] -> pud[j] -> pmd[k] -> pte[l]

chain is safe in this condition, too?

Another example in arch/ppc/kernel/head_44x.S:

	/* Data TLB Error Interrupt */
	START_EXCEPTION(DataTLBError)
...
	// r11 -> PGD or PTE page, r12 = index * sizeof(void *)

// -->
lwzx r11, r12, r11 /* Get pgd/pmd entry */

As in the two examples above, the walkers have already picked up references to the next levels, and these references were valid at that moment.

Are you sure this is true for the RISC-s, too?
Even if an architecture does not play with TLB-s before really finding a valid PTE?

Can you explain please why the already-started walks, which do not care for the TLB flushes, can be safe?

Not using any TLB entry (or any HW supported address translation stuff) to translate the data addresses before they go out of the CPU.

This is what I am trying to say: not on all archtectures.

Thanks,

Zoltan

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

__flush_tlb() purges the local TLBs only; but when you found the i386 or x86_64 flush_tlb_mm() calling __flush_tlb() above, you were looking at the #ifndef CONFIG_SMP block of include/asm/tlbflush.h. Go over to arch/{i386,x86_64}/kernel/smp.c to see what CONFIG_SMP flush_tlb_mm does.

I cannot answer for other architectures: you need to ask the specialist list of each architecture for its answer (or hope that a specialist in each is already reading this thread on linux-mm). What's certain is that the issue is _supposed_ to be already covered safely on all arches, hence the care which has gone into include/asm-generic/tlb.h etc. But you may be right that some architectures get it wrong, I cannot tell.

I've CC'ed Ken Chen and linux-ia64 (as Christoph intended to), since that's your first concern; but I'm reluctant to CC lots of different architecture lists together myself.

Hugh