: lockless get_user_pages patchset

From: Nick Piggin <[email protected]>
Date: Fri, 28 Mar 2008 03:55:41 +0100

include/asm-x86/pgtable.h line 45

Quoted 6 lines

include/asm-x86/pgtable.h +2 -0

@@ -40,6 +41,8 @@
 #define _PAGE_UNUSED3	(_AC(1, L)<<_PAGE_BIT_UNUSED3)
 #define _PAGE_PAT	(_AC(1, L)<<_PAGE_BIT_PAT)
 #define _PAGE_PAT_LARGE (_AC(1, L)<<_PAGE_BIT_PAT_LARGE)
+#define _PAGE_SPECIAL	(_AC(1, L)<<_PAGE_BIT_SPECIAL)
+#define __HAVE_ARCH_PTE_SPECIAL

What tests __HAVE_ARCH_PTE_SPECIAL?

include/asm-x86/pgtable.h static inline pte_t pte_mkhuge(pte_t pte · line 173

Quoted 6 lines

include/asm-x86/pgtable.h +1 -1

@@ -167,7 +170,7 @@ static inline pte_t pte_mkhuge(pte_t pte
 static inline pte_t pte_clrhuge(pte_t pte)	{ return __pte(pte_val(pte) & ~(pteval_t)_PAGE_PSE); }
 static inline pte_t pte_mkglobal(pte_t pte)	{ return __pte(pte_val(pte) | _PAGE_GLOBAL); }
 static inline pte_t pte_clrglobal(pte_t pte)	{ return __pte(pte_val(pte) & ~(pteval_t)_PAGE_GLOBAL); }
-static inline pte_t pte_mkspecial(pte_t pte)	{ return pte; }
+static inline pte_t pte_mkspecial(pte_t pte)	{ return __pte(pte_val(pte) | _PAGE_SPECIAL); }

And what calls pte_mkspecial?

I don't see any code that sets the special bit anywhere in these two patches.

What am I missing?

Basically, the pfn-based mapping insertion (vm_insert_pfn, remap_pfn_range) calls pte_mkspecial. And that tells fast_gup "hands off".

From: Nick Piggin <[email protected]>
Date: Fri, 28 Mar 2008 04:31:50 +0100

Quoted 2 lines

Basically, the pfn-based mapping insertion (vm_insert_pfn, remap_pfn_range) calls pte_mkspecial. And that tells fast_gup "hands off".

I don't think it's wise to allocate a "soft PTE bit" for this on every platform, especially for such a limited use case.

Is it feasible to test the page instead? Or are we talking about cases where there may not be a backing page?

If the issue is to discern things like I/O mappings and such vs. real pages, there are ways a platform can handle that without a special bit.

That would leave us with real memory that does not have backing page structs, and we have a way to test that too.

The special PTE bit seems superfluous to me.

BTW. if you are still interested, then the powerpc64 patch might be a better starting point for you. I don't know how the sparc tlb flush design looks like, but if it doesn't do a synchronous IPI to invalidate other threads, then you can't use the x86 approach.

From: Nick Piggin <[email protected]>
Date: Fri, 28 Mar 2008 05:04:42 +0100

Quoted 4 lines

BTW. if you are still interested, then the powerpc64 patch might be a better starting point for you. I don't know how the sparc tlb flush design looks like, but if it doesn't do a synchronous IPI to invalidate other threads, then you can't use the x86 approach.

I have soft bits available on sparc64, that's not my issue.

My issue is that if you implemented this differently, every platform would get the optimization, without having to do anything special at all, and I think that's such a much nicer way.

The other thing is that the "how do I know if I can refcount the page behind this (mm,vaddr,pte) tuple" can be quite arch specific as well. And it is also non-trivial to do because that information can be dynamic depending on what driver mapped in that given tuple.

From: Nick Piggin <[email protected]>
Date: Fri, 28 Mar 2008 05:15:20 +0100

Quoted 4 lines

The other thing is that the "how do I know if I can refcount the page behind this (mm,vaddr,pte) tuple" can be quite arch specific as well. And it is also non-trivial to do because that information can be dynamic depending on what driver mapped in that given tuple.

Those are good points.

Quoted 8 lines · David Miller

From: Nick Piggin <[email protected]>
Date: Fri, 28 Mar 2008 05:04:42 +0100

Quoted 4 lines

BTW. if you are still interested, then the powerpc64 patch might be a better starting point for you. I don't know how the sparc tlb flush design looks like, but if it doesn't do a synchronous IPI to invalidate other threads, then you can't use the x86 approach.

Quoted 5 lines

I have soft bits available on sparc64, that's not my issue.

My issue is that if you implemented this differently, every platform would get the optimization, without having to do anything special at all, and I think that's such a much nicer way.

Oh, they wouldn't. It is completely tied to the low level details of their TLB and pagetable teardown design. That's the unfortunate part about it.

The other thing is that the "how do I know if I can refcount the page behind this (mm,vaddr,pte) tuple" can be quite arch specific as well. And it is also non-trivial to do because that information can be dynamic depending on what driver mapped in that given tuple.

It is *possible*, but not trivial.

Introduce a new "fast_gup" (for want of a better name right now) which is basically a get_user_pages with a less general API (but still tends to be suited to the common case):

+++ linux-2.6/arch/x86/mm/gup.c

(quoted diff) +44 -0

@@ -0,0 +1,198 @@
+/*
+ * Lockless fast_gup for x86
+ *
+ * Copyright (C) 2007 Nick Piggin
+ * Copyright (C) 2007 Novell Inc.
+ */
+#include <linux/sched.h>
+#include <linux/mm.h>
+#include <linux/vmstat.h>
+#include <asm/pgtable.h>
+
+/*
+ * The performance critical leaf functions are made noinline otherwise gcc
+ * inlines everything into a single function which results in too much
+ * register pressure.
+ */
+static noinline int gup_pte_range(pmd_t pmd, unsigned long addr,
+		unsigned long end, int write, struct page **pages, int *nr)
+{
+	unsigned long mask, result;
+	pte_t *ptep;
+
+	result = _PAGE_PRESENT|_PAGE_USER;
+	if (write)
+		result |= _PAGE_RW;
+	mask = result | _PAGE_SPECIAL;
+
+	ptep = pte_offset_map(&pmd, addr);
+	do {
+		/*
+		 * XXX: careful. On 3-level 32-bit, the pte is 64 bits, and
+		 * we need to make sure we load the low word first, then the
+		 * high. This means _PAGE_PRESENT should be clear if the high
+		 * word was not valid. Currently, the C compiler can issue
+		 * the loads in any order, and I don't know of a wrapper
+		 * function that will do this properly, so it is broken on
+		 * 32-bit 3-level for the moment.
+		 */
+		pte_t pte = *ptep;
+		struct page *page;
+
+		if ((pte_val(pte) & mask) != result)
+			return 0;
+		VM_BUG_ON(!pfn_valid(pte_pfn(pte)));

Would this be sufficient to address that comment's conern?

Quoted 2 lines · Peter Zijlstra

Would this be sufficient to address that comment's conern?

It would be nicer to just add a "native_get_pte()" to x86, to match the already-existing "native_set_pte()".

And that "barrier()" should b "smp_rmb()". They may be the same code sequence, but from a conceptual angle, "smp_rmb()" makes a whole lot more sense.

Finally, I don't think that comment is correct in the first place. It's not that simple. The thing is, even *with* the memory barrier in place, we may have:

CPU#1 CPU#2
===== =====

fast_gup:
- read low word

native_set_pte_present:
- set low word to 0
- set high word to new value

- read high word

- set low word to new value

and so you read a low word that is associated with a *different* high word! Notice?

So trivial memory ordering is _not_ enough.

So I think the code literally needs to be something like this

	#ifdef CONFIG_X86_PAE

	static inline pte_t native_get_pte(pte_t *ptep)
	{
		pte_t pte;

	retry:
		pte.pte_low = ptep->pte_low;
		smp_rmb();
		pte.pte_high = ptep->pte_high;
		smp_rmb();
		if (unlikely(pte.pte_low != ptep->pte_low)
			goto retry;
		return pte;
	}

	#else

	#define native_get_pte(ptep) (*(ptep))

	#endif

but I have admittedly not really thought it fully through.

Jeremy, did I get the paravirt stuff right?

Quoted 2 lines · Peter Zijlstra

Jeremy, did I get the paravirt stuff right?

I don't think this is worth it to virtualize.

We access the page tables directly in any number of places, having a "get_pte()" indirection here is not going to help anything.

Just make it an x86-only inline function. In fact, you can keep it inside arch/x86/mm/gup.c, because nobody else is likely to ever even need it, since normal accesses are all supposed to be done under the page table spinlock, so they do not have this issue at all.

The indirection and virtualization thing is just going to complicate matters for no good reason.

Here you go ;-)

Quoted 2 lines · Peter Zijlstra

Here you go ;-)

I think you should _use_ the new functions too ;)

D'0h - clearly not my day today...

Quoted 1 line · Peter Zijlstra

Quoted 1 line

D'0h - clearly not my day today...

Ok, I'm acking this one ;)

And yes, it would be nice if the gup patches would go in early, since I wouldn't be entirely surprised if other architectures didn't have some other subtle issues here. We've never accessed the page tables without locking before, so we've only had races with hardware, never software.

arch/x86/mm/gup.c line 45

Quoted 7 lines · Peter Zijlstra

arch/x86/mm/gup.c +7 -0

+retry:
+	pte.pte_low = ptep->pte_low;
+	smp_rmb();
+	pte.pte_high = ptep->pte_high;
+	smp_rmb();
+	if (unlikely(pte.pte_low != ptep->pte_low))
+		goto retry;

What about using `do { ... } while (...)' instead?

Quoted 6 lines · Linus Torvalds

Quoted 2 lines · Peter Zijlstra

Would this be sufficient to address that comment's conern?

It would be nicer to just add a "native_get_pte()" to x86, to match the already-existing "native_set_pte()".

See, I _knew_ I was missing something obvious :-/

Quoted 44 lines

And that "barrier()" should b "smp_rmb()". They may be the same code sequence, but from a conceptual angle, "smp_rmb()" makes a whole lot more sense.

Finally, I don't think that comment is correct in the first place. It's not that simple. The thing is, even *with* the memory barrier in place, we may have:

CPU#1 CPU#2
===== =====

fast_gup:
- read low word

native_set_pte_present:
- set low word to 0
- set high word to new value

- read high word

- set low word to new value

and so you read a low word that is associated with a *different* high word! Notice?

So trivial memory ordering is _not_ enough.

So I think the code literally needs to be something like this

	#ifdef CONFIG_X86_PAE

	static inline pte_t native_get_pte(pte_t *ptep)
	{
		pte_t pte;

	retry:
		pte.pte_low = ptep->pte_low;
		smp_rmb();
		pte.pte_high = ptep->pte_high;
		smp_rmb();
		if (unlikely(pte.pte_low != ptep->pte_low)
			goto retry;
		return pte;
	}

	#else

	#define native_get_pte(ptep) (*(ptep))

Quoted 4 lines

	#endif

but I have admittedly not really thought it fully through.

Looks sane here; Clark can you give this a spin?

Jeremy, did I get the paravirt stuff right?

Finally, I don't think that comment is correct in the first place. It's not that simple. The thing is, even *with* the memory barrier in place, we may have:

CPU#1 CPU#2
===== =====

fast_gup:
- read low word

native_set_pte_present:
- set low word to 0
- set high word to new value

- read high word

- set low word to new value

and so you read a low word that is associated with a *different* high word! Notice?

So trivial memory ordering is _not_ enough.

So I think the code literally needs to be something like this

	#ifdef CONFIG_X86_PAE

	static inline pte_t native_get_pte(pte_t *ptep)
	{
		pte_t pte;

	retry:
		pte.pte_low = ptep->pte_low;
		smp_rmb();
		pte.pte_high = ptep->pte_high;
		smp_rmb();
		if (unlikely(pte.pte_low != ptep->pte_low)
			goto retry;
		return pte;
	}

Quoted 25 lines · Linus Torvalds

Finally, I don't think that comment is correct in the first place. It's not that simple. The thing is, even *with* the memory barrier in place, we may have:

CPU#1 CPU#2
===== =====

fast_gup:
- read low word

native_set_pte_present:
- set low word to 0
- set high word to new value

- read high word

- set low word to new value

and so you read a low word that is associated with a *different* high word! Notice?

So trivial memory ordering is _not_ enough.

So I think the code literally needs to be something like this

Quoted 17 lines

	#ifdef CONFIG_X86_PAE

	static inline pte_t native_get_pte(pte_t *ptep)
	{
		pte_t pte;

	retry:
		pte.pte_low = ptep->pte_low;
		smp_rmb();
		pte.pte_high = ptep->pte_high;
		smp_rmb();
		if (unlikely(pte.pte_low != ptep->pte_low)
			goto retry;
		return pte;
	}

I think this is still broken. Suppose that after reading pte_high native_set_pte() is called again on another cpu, changing pte_low back to the original value (but with a different pte_high). You now have pte_low from second native_set_pte() but pte_high from the first native_set_pte().

Quoted 42 lines · Avi Kivity

Quoted 40 lines · Linus Torvalds

Finally, I don't think that comment is correct in the first place. It's not that simple. The thing is, even *with* the memory barrier in place, we may have:

CPU#1 CPU#2
===== =====

fast_gup:
- read low word

native_set_pte_present:
- set low word to 0
- set high word to new value

- read high word

- set low word to new value

and so you read a low word that is associated with a *different* high word! Notice?

So trivial memory ordering is _not_ enough.

So I think the code literally needs to be something like this

	#ifdef CONFIG_X86_PAE

	static inline pte_t native_get_pte(pte_t *ptep)
	{
		pte_t pte;

	retry:
		pte.pte_low = ptep->pte_low;
		smp_rmb();
		pte.pte_high = ptep->pte_high;
		smp_rmb();
		if (unlikely(pte.pte_low != ptep->pte_low)
			goto retry;
		return pte;
	}

Quoted 2 lines

I think this is still broken. Suppose that after reading pte_high native_set_pte() is called again on another cpu, changing pte_low back to the original value (but with a different pte_high). You now have pte_low from second native_set_pte() but pte_high from the first native_set_pte().

I think the idea was that for user pages we only use set_pte_present() which does the low=0 thing first.

Quoted 54 lines · Peter Zijlstra

Quoted 45 lines · Avi Kivity

Quoted 25 lines · Linus Torvalds

Finally, I don't think that comment is correct in the first place. It's not that simple. The thing is, even *with* the memory barrier in place, we may have:

CPU#1 CPU#2
===== =====

fast_gup:
- read low word

native_set_pte_present:
- set low word to 0
- set high word to new value

- read high word

- set low word to new value

and so you read a low word that is associated with a *different* high word! Notice?

So trivial memory ordering is _not_ enough.

So I think the code literally needs to be something like this

Quoted 18 lines

	#ifdef CONFIG_X86_PAE

	static inline pte_t native_get_pte(pte_t *ptep)
	{
		pte_t pte;

	retry:
		pte.pte_low = ptep->pte_low;
		smp_rmb();
		pte.pte_high = ptep->pte_high;
		smp_rmb();
		if (unlikely(pte.pte_low != ptep->pte_low)
			goto retry;
		return pte;
	}

Quoted 6 lines

I think this is still broken. Suppose that after reading pte_high native_set_pte() is called again on another cpu, changing pte_low back to the original value (but with a different pte_high). You now have pte_low from second native_set_pte() but pte_high from the first native_set_pte().

Quoted 3 lines

I think the idea was that for user pages we only use set_pte_present() which does the low=0 thing first.

Doesn't matter. The second native_set_pte() (or set_pte_present()) executes atomically:

fast_gup:
- read low word (l0)

native_set_pte_present:
- set low word to 0
- set high word to new value (h1)
- set low word to new value (l1)

- read high word (h1)

native_set_pte_present:
- set low word to 0
- set high word to new value (h2)
- set low word to new value (l2)

- re-read low word (l2)

If l2 happens to be equal to l0, then the check succeeds and we have a splintered pte h1:l0.

Quoted 79 lines · Avi Kivity

Quoted 54 lines · Peter Zijlstra

Quoted 45 lines · Avi Kivity

Quoted 25 lines · Linus Torvalds

Finally, I don't think that comment is correct in the first place. It's not that simple. The thing is, even *with* the memory barrier in place, we may have:

CPU#1 CPU#2
===== =====

fast_gup:
- read low word

native_set_pte_present:
- set low word to 0
- set high word to new value

- read high word

- set low word to new value

and so you read a low word that is associated with a *different* high word! Notice?

So trivial memory ordering is _not_ enough.

So I think the code literally needs to be something like this

Quoted 18 lines

	#ifdef CONFIG_X86_PAE

	static inline pte_t native_get_pte(pte_t *ptep)
	{
		pte_t pte;

	retry:
		pte.pte_low = ptep->pte_low;
		smp_rmb();
		pte.pte_high = ptep->pte_high;
		smp_rmb();
		if (unlikely(pte.pte_low != ptep->pte_low)
			goto retry;
		return pte;
	}

Quoted 6 lines

I think this is still broken. Suppose that after reading pte_high native_set_pte() is called again on another cpu, changing pte_low back to the original value (but with a different pte_high). You now have pte_low from second native_set_pte() but pte_high from the first native_set_pte().

Quoted 3 lines

I think the idea was that for user pages we only use set_pte_present() which does the low=0 thing first.

Doesn't matter. The second native_set_pte() (or set_pte_present()) executes atomically:

fast_gup:
- read low word (l0)

native_set_pte_present:
- set low word to 0
- set high word to new value (h1)
- set low word to new value (l1)

- read high word (h1)

native_set_pte_present:
- set low word to 0
- set high word to new value (h2)
- set low word to new value (l2)

Quoted 5 lines

- re-read low word (l2)

If l2 happens to be equal to l0, then the check succeeds and we have a splintered pte h1:l0.

ok, so lets use cmpxchg8.

That's horrible ;)

Anyway guys you are missing the other side of the equation -- that whenever _PAGE_PRESENT is cleared, all CPUs where current->mm might be == mm have to have a tlb flush. And we're holding off tlb flushes in fast_gup, that's the whole reason why it all works.

Linus's loop I will use for PAE. I'd love to know whether the hardware walker actually does an atomic 64-bit load or not, though.

arch/x86/mm/gup.c new file +17 -0

+static noinline int gup_pte_range(pmd_t pmd, unsigned long addr,
+		unsigned long end, int write, struct page **pages, int *nr)
+{
+	unsigned long mask, result;
+	pte_t *ptep;
+
+	result = _PAGE_PRESENT|_PAGE_USER;
+	if (write)
+		result |= _PAGE_RW;
+	mask = result | _PAGE_SPECIAL;
+
+	ptep = pte_offset_map(&pmd, addr);
+	do {
+		/*
+		 * XXX: careful. On 3-level 32-bit, the pte is 64 bits, and
+		 * we need to make sure we load the low word first, then the
+		 * high. This means _PAGE_PRESENT should be clear if the high

arch/x86/mm/gup.c new file +11 -0

+		VM_BUG_ON(!pfn_valid(pte_pfn(pte)));
+		page = pte_page(pte);
+		get_page(page);
+		pages[*nr] = page;
+		(*nr)++;
+
+	} while (ptep++, addr += PAGE_SIZE, addr != end);
+	pte_unmap(ptep - 1);
+
+	return 1;
+}

Quoted 21 lines · Nick Piggin

arch/x86/mm/gup.c new file +21 -0

+static noinline int gup_pte_range(pmd_t pmd, unsigned long addr,
+		unsigned long end, int write, struct page **pages, int *nr)
+{
+	unsigned long mask, result;
+	pte_t *ptep;
+
+	result = _PAGE_PRESENT|_PAGE_USER;
+	if (write)
+		result |= _PAGE_RW;
+	mask = result | _PAGE_SPECIAL;
+
+	ptep = pte_offset_map(&pmd, addr);
+	do {
+		/*
+		 * XXX: careful. On 3-level 32-bit, the pte is 64 bits, and
+		 * we need to make sure we load the low word first, then the
+		 * high. This means _PAGE_PRESENT should be clear if the high
+		 * word was not valid. Currently, the C compiler can issue
+		 * the loads in any order, and I don't know of a wrapper
+		 * function that will do this properly, so it is broken on
+		 * 32-bit 3-level for the moment.

arch/x86/mm/gup.c line 43

Quoted 6 lines

arch/x86/mm/gup.c new file +6 -0

+		 */
+		pte_t pte = *ptep;
+		struct page *page;
+
+		if ((pte_val(pte) & mask) != result)
+			return 0;

This return path fails to unmap the pmd.

Quoted 23 lines · Peter Zijlstra

Quoted 21 lines · Nick Piggin

arch/x86/mm/gup.c new file +21 -0

+static noinline int gup_pte_range(pmd_t pmd, unsigned long addr,
+		unsigned long end, int write, struct page **pages, int *nr)
+{
+	unsigned long mask, result;
+	pte_t *ptep;
+
+	result = _PAGE_PRESENT|_PAGE_USER;
+	if (write)
+		result |= _PAGE_RW;
+	mask = result | _PAGE_SPECIAL;
+
+	ptep = pte_offset_map(&pmd, addr);
+	do {
+		/*
+		 * XXX: careful. On 3-level 32-bit, the pte is 64 bits, and
+		 * we need to make sure we load the low word first, then the
+		 * high. This means _PAGE_PRESENT should be clear if the high
+		 * word was not valid. Currently, the C compiler can issue
+		 * the loads in any order, and I don't know of a wrapper
+		 * function that will do this properly, so it is broken on
+		 * 32-bit 3-level for the moment.

Quoted 8 lines

arch/x86/mm/gup.c line 43

Quoted 6 lines

arch/x86/mm/gup.c new file +6 -0

+		 */
+		pte_t pte = *ptep;
+		struct page *page;
+
+		if ((pte_val(pte) & mask) != result)
+			return 0;

This return path fails to unmap the pmd.

Ah good catch. As you can see I haven't done any highmem testing ;) Which I will do so before sending upstream.

Quoted 2 lines

Ah good catch. As you can see I haven't done any highmem testing ;) Which I will do so before sending upstream.

Which will be when? We'd really like to see this in mainline as soon as possible and in -mm in the meanwhile.