Skip to contentSkip to conversation

Protect PGD...PTE walking in ivt.S

PATCH Zoltan Menyhart 4 participants 5 messages Apr 21, 2006

lore
Share & tools
lore
#0 lore raw

The "rx = ... -> pgd[i] -> pud[j] -> pmd[k] -> pte[l]" chain has to be protected against "free_pgtables()".

"free_pgtables()" is protected by "mmap_sem" taken for write, therefore taking this semaphore for read in the low level assembly routines will provide us with enough protection:
- it can be taken for read almost all the time
- it scales well
- the performance is not degraded (see below)

I prepared a patch for the VHPT miss handler only. Later I can add the rest. Here is how it goes:

0. Only the user region faults are protected.
(You should not try to remove an in-use 0xa000... mapping.)

1. "activate_mm()" remembers the physical address of the "mmap_sem" of the task selected to run in "ar.k2" (IA64_KR_MM_SEM).

2. On entry, "vhpt_miss" takes "mmap_sem" for read:

	while (unlikely(__down_read_trylock(&current->mm->mmap_sem) = 0));

3. If there is no valid PTE => go to "page_fault_sem" (see later).

4. On one hand, as "free_pgtables()" cannot run in the mean time, there is no need to re-read pgd[i] -> pud[j] -> pmd[k].
On the other hand, the swapper is not excluded => we keep re-checking pte[l] and purging the freshly inserted TLB entry if it has been changed.

5. Releasing "mmap_sem" is a bit tricky:

	__up_read(&current->mm->mmap_sem);

On the fast path, we can "rfi".

6. If someone is waiting for "mmap_sem", then we have to switch the translation on, to establish the "C" environment and to call "rwsem_wake()".

7. "page_fault_sem": if we have "mmap_sem", then it is more efficient not to release it, because "ia64_do_page_fault()" would take it. Therefore a new argument, called "mmap_sem_taken_for_read", is added. (This flag is DONT-CARE for the faults from the region 5.)

Non-regression test:

I wrote a "wicked" test that provokes VHPT misses, while all the loads / stores hit the caches L1D / L2.

In order to maximize the number of the TLB entries needed for the virtually mapped PTE pages, only one valid PTE / page will be used (, and a single byte per data page).

8 times more TLB entries will be solicited than what is really available:
512 data pages + 512 PTE pages => systematic VHPT misses.

The innermost loop is as follows:

1: st1 [r15]=r16 // DTLB miss, then L2 hit

    adds r16=1,r16
    ld4 r24=[r18] ;;     // L1D cache hit
    add r15=r15,r24
    br.cloop.sptk.few 1b

The original linux-2.6.16.9 with the missing "srlz.d" added into the VHPT miss handler:

ITC ticks: 615,846,302, # user accesses: 5,120,000, ITC ticks / access: 120 ITC ticks: 593,729,267, # user accesses: 5,120,000, ITC ticks / access: 115 ITC ticks: 558,319,090, # user accesses: 5,120,000, ITC ticks / access: 109 ITC ticks: 596,911,467, # user accesses: 5,120,000, ITC ticks / access: 116 ITC ticks: 558,342,475, # user accesses: 5,120,000, ITC ticks / access: 109 ITC ticks: 602,162,489, # user accesses: 5,120,000, ITC ticks / access: 117 ITC ticks: 558,207,935, # user accesses: 5,120,000, ITC ticks / access: 109 ITC ticks: 612,523,245, # user accesses: 5,120,000, ITC ticks / access: 119 ITC ticks: 615,927,942, # user accesses: 5,120,000, ITC ticks / access: 120 ITC ticks: 595,530,914, # user accesses: 5,120,000, ITC ticks / access: 116

I.e. it takes 109 ... 120 ITC ticks to execute the innermost loop above + the fast path of the VHPT miss handler on a Tiger like machine with CPUs like:

processor : 2
vendor : GenuineIntel
arch : IA-64
family : Itanium 2
model : 2
revision : 1
archrev : 0
features : branchlong
cpu number : 0
cpu regs : 4
cpu MHz : 1700.000554
itc MHz : 1700.554956
BogoMIPS : 2547.71
siblings : 1

With my patch:

ITC ticks: 768,590,910, # user accesses: 5,120,000, ITC ticks / access: 150 ITC ticks: 727,652,674, # user accesses: 5,120,000, ITC ticks / access: 142 ITC ticks: 743,272,209, # user accesses: 5,120,000, ITC ticks / access: 145 ITC ticks: 747,918,306, # user accesses: 5,120,000, ITC ticks / access: 146 ITC ticks: 743,176,995, # user accesses: 5,120,000, ITC ticks / access: 145 ITC ticks: 728,062,632, # user accesses: 5,120,000, ITC ticks / access: 142 ITC ticks: 745,091,227, # user accesses: 5,120,000, ITC ticks / access: 145 ITC ticks: 733,728,213, # user accesses: 5,120,000, ITC ticks / access: 143 ITC ticks: 747,965,619, # user accesses: 5,120,000, ITC ticks / access: 146 ITC ticks: 728,251,497, # user accesses: 5,120,000, ITC ticks / access: 142

I have 142 ... 150 ITC ticks.

Notes:
- a simple memory access on this test machine costs 340 ITC ticks (and usually we do some memory accesses :-))
- not all the loads / stores provoke TLB misses when executing an average program
- not all the TLB misses provoke VHPT misses

A real life application will not suffer from any performance degradation.

Thanks,

Zoltan

arch/ia64/mm/fault.c +34 -4
@@ -51,8 +51,16 @@ mapped_kernel_page_is_present (unsigned 
 	return pte_present(pte);
 }
 
+/*
+ * The low level handlers take "current->mm->mmap_sem" for read if user region
+ * (0 ... 4) fault has happened, see "mmap_sem_taken_for_read".
+ * This flag is DONT-CARE for the faults from the region 5.
+ * "current->mm->mmap_sem" is never taken by the low level handlers for the
+ * faults from the region 5.
+ */
 void __kprobes
-ia64_do_page_fault (unsigned long address, unsigned long isr, struct pt_regs *regs)
+ia64_do_page_fault (unsigned long address, unsigned long isr, struct pt_regs *regs,
+							int mmap_sem_taken_for_read)
 {
 	int signal = SIGSEGV, code = SEGV_MAPERR;
 	struct vm_area_struct *vma, *prev_vma;
@@ -60,10 +68,16 @@ ia64_do_page_fault (unsigned long addres
 	struct siginfo si;
 	unsigned long mask;
 
+	if (mmap_sem_taken_for_read && (REGION_NUMBER(address) < 5)){
+		BUG_ON(__pa(&current->mm->mmap_sem) != ia64_get_kr(IA64_KR_MM_SEM));
+		BUG_ON((current->mm->mmap_sem.count & RWSEM_ACTIVE_MASK) = 0);
+	}
 	/*
 	 * If we're in an interrupt or have no user context, we must not take the fault..
 	 */
-	if (in_atomic() || !mm)
+	if (in_atomic())
+		goto no_context_sem;
+	if (!mm)
 		goto no_context;
 
 #ifdef CONFIG_VIRTUAL_MEM_MAP
@@ -82,10 +96,14 @@ ia64_do_page_fault (unsigned long addres
 	 * This is to handle the kprobes on user space access instructions
 	 */
 	if (notify_die(DIE_PAGE_FAULT, "page fault", regs, code, TRAP_BRKPT,
-					SIGSEGV) = NOTIFY_STOP)
+					SIGSEGV) = NOTIFY_STOP){
+		if (mmap_sem_taken_for_read && (REGION_NUMBER(address) < 5))
+			up_read(&mm->mmap_sem);
 		return;
+	}
 
-	down_read(&mm->mmap_sem);
+	if (!mmap_sem_taken_for_read || (REGION_NUMBER(address) = 5))
+		down_read(&mm->mmap_sem);
 
 	vma = find_vma_prev(mm, address, &prev_vma);
 	if (!vma)
@@ -197,6 +215,9 @@ ia64_do_page_fault (unsigned long addres
 		return;
 	}
 
+  no_context_sem:
+  	if (mmap_sem_taken_for_read && (REGION_NUMBER(address) < 5))
+		up_read(&mm->mmap_sem);
   no_context:
 	if ((isr & IA64_ISR_SP)
 	    || ((isr & IA64_ISR_NA) && (isr & IA64_ISR_CODE_MASK) = IA64_ISR_CODE_LFETCH))
@@ -251,3 +272,12 @@ ia64_do_page_fault (unsigned long addres
 		do_exit(SIGKILL);
 	goto no_context;
 }
+
+
+void my_rwsem_wake(struct rw_semaphore *sem)
+{
+	printk("\nmy_rwsem_wake(%p) %p %p\n", sem, current, &current->mm);
+	BUG_ON(&current->mm->mmap_sem != sem);
+	rwsem_wake(sem);
+}
+
arch/ia64/kernel/ivt.S +168 -37

291 lines not on this page · raw message

include/asm-ia64/kregs.h +1 -0
@@ -14,6 +14,7 @@
  */
 #define IA64_KR_IO_BASE		0	/* ar.k0: legacy I/O base address */
 #define IA64_KR_TSSD		1	/* ar.k1: IVE uses this as the TSSD */
+#define	IA64_KR_MM_SEM		2	/* ar.k2: ->mmap_sem address (physical) */
 #define IA64_KR_PER_CPU_DATA	3	/* ar.k3: physical per-CPU base */
 #define IA64_KR_CURRENT_STACK	4	/* ar.k4: what's mapped in IA64_TR_CURRENT_STACK */
 #define IA64_KR_FPU_OWNER	5	/* ar.k5: fpu-owner (UP only, at the moment) */
include/asm-ia64/mmu_context.h +1 -0
@@ -192,6 +192,7 @@ activate_mm (struct mm_struct *prev, str
 	 * handlers cannot touch user-space.
 	 */
 	ia64_set_kr(IA64_KR_PT_BASE, __pa(next->pgd));
+	ia64_set_kr(IA64_KR_MM_SEM, __pa(&next->mmap_sem));
 	activate_context(next);
 }
 
#1 lore raw

The test program:

/*
* This test aims to provoke VHPT misses.
*
* In order to maximize the number of the TLB entries needed for the virtually mapped
* PTE pages, only one valid PTE / page will be used (, and a single byte per data page).
* The TLB pressure will me multiplied by "N" in order not to leave any
* practical chance for a TLB hit.
*
* Remember to allow to over-commit memory: "sysctl -w vm.overcommit_memory=1". *
* ...there is no control over the physical addresses of the user pages... there will
* be some variation of the results from run to run due to some address aliases... *
* ...the interrupts are enabled...
*/

#include <sys/types.h>
#include <stdio.h>
#include <sys/mman.h>

#define N 8 // TLB pressure multiplier
#define N_RUNS 10
#define N_EXTERNAL_LOOPS 10
#define N_INTERNAL_LOOPS 1000

#define CACHE_BYTES 128
#define N_TLB_ENTRIES 128

// Not counting the kernel's DTRs...
#define N_PTE_PAGE_U_PAGE_PAIRS (N_TLB_ENTRIES / 2 * N)
#define PTE_PER_CACHE_BYTES (CACHE_BYTES / sizeof(unsigned long))

unsigned int pagesize;

#define PTES_PER_PAGE (pagesize / sizeof(void *))
#define VA_RANGE_PER_PTE_PAGE (PTES_PER_PAGE * pagesize)

/*
* Cache line "coloring" in order to reduce cache alias problems.
* (Yet as there is no control over the physical addresses of the user pages...)
* The i-th element touched by the innermost loop will be at the offset in the page:
* (i * 2 + 1) * CACHE_BYTES
* The PTE mapping this test data will be at the offset in its page:
* i * 2 * CACHE_BYTES
*/

#define	OFFSET			(VA_RANGE_PER_PTE_PAGE + \
				2 * PTE_PER_CACHE_BYTES * pagesize + \
				2 * CACHE_BYTES)

unsigned int offset;

#define	TEST_VA_RANGE		((unsigned long) VA_RANGE_PER_PTE_PAGE * \
						N_PTE_PAGE_U_PAGE_PAIRS + \
				/* Cache line "coloring": */ \
				2 * N_PTE_PAGE_U_PAGE_PAIRS * \
						PTE_PER_CACHE_BYTES * pagesize + \
				2 * N_PTE_PAGE_U_PAGE_PAIRS * CACHE_BYTES)

#define MEM_PROT (PROT_READ | PROT_WRITE)
#define MEM_TYPE (MAP_PRIVATE | MAP_ANONYMOUS)

#define GET_ITC() \

({								\
	unsigned long ia64_intri_res;				\
								\
	asm volatile ("mov %0=ar.itc" : "=r"(ia64_intri_res));	\
	ia64_intri_res;						\
})

inline unsigned long test(char *p0, unsigned int n)

{
	int		i, j;
	char		*p;
	unsigned long	itc0 = GET_ITC();

	for (j = 0; j < n; j++)
		for (i = 0, p = p0 + CACHE_BYTES;	// Cache line "coloring"
				i < N_PTE_PAGE_U_PAGE_PAIRS; i++, p += offset)
			*p = i;
	return GET_ITC() - itc0;
}

void main_test(void)

{
	void		*p;
	int		loop;
	unsigned long	tmp, sum = 0;

	p = mmap(NULL, TEST_VA_RANGE, MEM_PROT, MEM_TYPE, -1, 0);
	if (p = MAP_FAILED){
		perror("mmap");
		fprintf(stderr, "Have you allowed to over-commit memory? "
				"Try: \"sysctl -w vm.overcommit_memory=1\"\n");
		exit(1);
	}
	(void) test(p, 1);				// Warm up...
	for (loop = 0; loop < N_EXTERNAL_LOOPS; loop++)
		sum += test(p, N_INTERNAL_LOOPS);
	(void) munmap(p, TEST_VA_RANGE);
	printf("ITC ticks: %ld,%03ld,%03ld,",
				sum / 1000000, sum / 1000 % 1000, sum % 1000);
	tmp = (unsigned long) N_EXTERNAL_LOOPS * N_INTERNAL_LOOPS *
							N_PTE_PAGE_U_PAGE_PAIRS;
	printf(" # user accesses: %ld,%03ld,%03ld, ITC ticks / access: %ld\n",
			tmp / 1000000, tmp / 1000 % 1000, tmp % 1000, sum / tmp);
}

int main(int argc, char *argv[])

{
	int		run;
	unsigned long	tmp;

	pagesize = getpagesize();
	offset = OFFSET;			// Depends on "getpagesize()"
	printf("Page size =\t\t\t%12d\n", pagesize);
	printf("PTEs / page =\t\t\t%12d\n", PTES_PER_PAGE);
	printf("VA range / PTE page =\t\t%12d (%d Mbytes)\n",
				VA_RANGE_PER_PTE_PAGE, VA_RANGE_PER_PTE_PAGE >> 20);
	printf("# PTE-page / user-page pairs =\t%12d\n", N_PTE_PAGE_U_PAGE_PAIRS);
	printf("Test VA range =\t\t\t%12ld (%ld Gbytes)\n",
				TEST_VA_RANGE, TEST_VA_RANGE >> 30);
	tmp = N_PTE_PAGE_U_PAGE_PAIRS * pagesize;
	printf("Resident user memory =\t\t%12ld (%ld Mbytes)\n", tmp, tmp >> 20);
	printf("# PTE + user cache lines =\t%12d (%d Kbytes)\n",
				N_PTE_PAGE_U_PAGE_PAIRS * 2,
				N_PTE_PAGE_U_PAGE_PAIRS * 2 * CACHE_BYTES >> 10);
	printf("\n");
	for (run = 0; run < N_RUNS; run++)
		main_test();
	return 0;
}
#2 lore raw
In reply to Zoltan Menyhart
Quoted 1 line · Zoltan Menyhart

- it scales well

mmap_sem is the major performance bottleneck for page faults at this time because it creates a bouncing cacheline. Figure out a way to avoid that to increase performance.

Quoted 4 lines

4. On one hand, as "free_pgtables()" cannot run in the mean time, there is no need to re-read pgd[i] -> pud[j] -> pmd[k].
On the other hand, the swapper is not excluded => we keep re-checking pte[l] and purging the freshly inserted TLB entry if it has been changed.

The walking of pgd/pud/pmd can happen anytime through the mmu on many architectures. It is therefore not protectable by any lock.

free_pgtables() is run when all processes in a mm_struct have terminated or when all vmas from an area have been removed.

There can be no one using the page tables.

#3 lore raw
In reply to Zoltan Menyhart
Quoted 7 lines · Christoph Lameter
Quoted 1 line · Zoltan Menyhart

- it scales well

mmap_sem is the major performance bottleneck for page faults at this time because it creates a bouncing cacheline. Figure out a way to avoid that to increase performance.

Have you got some numbers?
Can I have a copy of your test program, please?

Quoted 7 lines
Quoted 4 lines

4. On one hand, as "free_pgtables()" cannot run in the mean time, there is no need to re-read pgd[i] -> pud[j] -> pmd[k].
On the other hand, the swapper is not excluded => we keep re-checking pte[l] and purging the freshly inserted TLB entry if it has been changed.

The walking of pgd/pud/pmd can happen anytime through the mmu on many architectures. It is therefore not protectable by any lock.

I do not know much about the other architectures.

As TBL loading is not the same mechanism on all the architectures, therefore architecture dependent solutions can be applied.

If PGD...PTE walking does not need protection / cannot be protected on other architectures, then it is not a strong argument about the ia64's behavior.

We were talking about this issue in the thread "accessed/dirty bit handler tuning". I thought we had agreed that this PGD...PTE walking is unsafe.
Locking _is_ a logically correct solution.
Any other suggestion?

Quoted 4 lines

free_pgtables() is run when all processes in a mm_struct have terminated or when all vmas from an area have been removed.

There can be no one using the page tables.

Please refer to "unmap_region()".

Thanks,

Zoltan

#4 lore raw
In reply to Zoltan Menyhart
Quoted 11 lines · Zoltan Menyhart
Quoted 7 lines · Christoph Lameter
Quoted 1 line · Zoltan Menyhart

- it scales well

mmap_sem is the major performance bottleneck for page faults at this time because it creates a bouncing cacheline. Figure out a way to avoid that to increase performance.

Have you got some numbers?
Can I have a copy of your test program, please?

Test program is available from ftp.kernel.org/pub/linux/kernel/people/christoph/ptl/pft.c. See the discussion of my page fault scalability patches on lkml in 2004/2005.

Quoted 4 lines
Quoted 2 lines

The walking of pgd/pud/pmd can happen anytime through the mmu on many architectures. It is therefore not protectable by any lock.

I do not know much about the other architectures.

They are relevant since they determine core linux functionality.

Quoted 3 lines

If PGD...PTE walking does not need protection / cannot be protected on other architectures, then it is not a strong argument about the ia64's behavior.

Of course. This means that the core kernel was designed in such a way to cope with this issue.

Quoted 3 lines

We were talking about this issue in the thread "accessed/dirty bit handler tuning". I thought we had agreed that this PGD...PTE walking is unsafe.

I did?

Quoted 2 lines

Locking _is_ a logically correct solution.
Any other suggestion?

Drop the non issue.

Quoted 6 lines
Quoted 4 lines

free_pgtables() is run when all processes in a mm_struct have terminated or when all vmas from an area have been removed.

There can be no one using the page tables.

Please refer to "unmap_region()".

Only run after the vmas have been removed. Any fault will lead to an access error.