Protect PGD...PTE walking in ivt.S

Zoltan Menyhart
2006-04-21T14:12:43Z

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

--- linux-2.6.16.9/arch/ia64/mm/fault.c 2006-04-19 08:10:14.000000000 +0200
+++ new/arch/ia64/mm/fault.c 2006-04-21 11:21:47.000000000 +0200
@@ -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);
+}
+
--- linux-2.6.16.9/arch/ia64/kernel/ivt.S 2006-04-19 08:10:14.000000000 +0200
+++ new/arch/ia64/kernel/ivt.S 2006-04-20 17:52:58.000000000 +0200
@@ -80,6 +80,10 @@

.align 32768 // align on 32KB boundary
.global ia64_ivt
+
+#define pUsr p17 // User regions
+#define pR5 p16 // Region 5 fault
+
ia64_ivt:
/////////////////////////////////////////////////////////////////////////////////////////
// 0x0000 Entry 0 (size 64 bundles) VHPT Translation (8,20,47)
@@ -112,10 +116,13 @@ ENTRY(vhpt_miss)
rsm psr.dt // use physical addressing for data
mov r31=pr // save the predicate registers
mov r19=IA64_KR(PT_BASE) // get page table base address
- shl r21=r16,3 // shift bit 60 into sign bit
+#ifdef CONFIG_SMP
+ mov r30 = IA64_KR(MM_SEM) // &current->mm->mmap_sem
+#endif
+ shl r20=r16,3 // shift bit 60 into sign bit
shr.u r17=r16,61 // get the region number into r17
;;
- shr.u r22=r21,3
+ shr.u r22=r20,3
#ifdef CONFIG_HUGETLB_PAGE
extr.u r26=r25,2,6
;;
@@ -126,20 +133,47 @@ ENTRY(vhpt_miss)
(p8) shr r22=r22,r27
#endif
;;
- cmp.eq p6,p7=5,r17 // is IFA pointing into to region 5?
+ cmp.eq pR5,pUsr=5,r17 // is IFA pointing into to region 5?
shr.u r18=r22,PGDIR_SHIFT // get bottom portion of pgd index bit
;;
-(p7) dep r17=r17,r19,(PAGE_SHIFT-3),3 // put region number bits in place
+(pUsr) dep r17=r17,r19,(PAGE_SHIFT-3),3 // put region number bits in place

srlz.d
- LOAD_PHYSICAL(p6, r19, swapper_pg_dir) // region 5 is rooted at swapper_pg_dir
+ LOAD_PHYSICAL(pR5, r19, swapper_pg_dir) // region 5 is rooted at swapper_pg_dir

- .pred.rel "mutex", p6, p7
-(p6) shr.u r21=r21,PGDIR_SHIFT+PAGE_SHIFT
-(p7) shr.u r21=r21,PGDIR_SHIFT+PAGE_SHIFT-3
+#ifdef CONFIG_SMP
+1: /*
+ * If (pUsr: user region fault){
+ * __s64 r27, r28, *r30 = &current->mm->mmap_sem;
+ *
+ * //
+ * // while (unlikely(__down_read_trylock(&current->mm->mmap_sem) = 0));
+ * //
+ * do {
+ * while (unlikely((r27 = ia64_ld8_bias_nta(&r30->count)) < 0));
+ * r28 = r27 + 1;
+ * } while (unlikely(ia64_cmpxchg8_acq_nta(&r30->count, r28, r27) != r27));
+ * }
+ */
+(pUsr) ld8.bias.nta r27 = [r30]
;;
-(p6) dep r17=r18,r19,3,(PAGE_SHIFT-3) // r17=pgd_offset for region 5
-(p7) dep r17=r18,r17,3,(PAGE_SHIFT-6) // r17=pgd_offset for region[0-4]
+(pUsr) cmp.lt.unc p8, p0 = r27, r0
+(p8) br.cond.spnt.few 1b
+(pUsr) mov.m ar.ccv = r27
+(pUsr) adds r28 = 1, r27
+ ;;
+(pUsr) cmpxchg8.acq.nta r28 = [r30], r28, ar.ccv
+ ;;
+(pUsr) cmp.eq.unc p0, p8 = r28, r27
+(p8) br.cond.spnt.few 1b
+#endif // CONFIG_SMP
+
+ .pred.rel "mutex", pR5, pUsr
+(pR5) shr.u r21=r20,PGDIR_SHIFT+PAGE_SHIFT
+(pUsr) shr.u r21=r20,PGDIR_SHIFT+PAGE_SHIFT-3
+ ;;
+(pR5) dep r17=r18,r19,3,(PAGE_SHIFT-3) // r17=pgd_offset for region 5
+(pUsr) dep r17=r18,r17,3,(PAGE_SHIFT-6) // r17=pgd_offset for region[0-4]
cmp.eq p7,p6=0,r21 // unused address bits all zeroes?
#ifdef CONFIG_PGTABLE_4
shr.u r28=r22,PUD_SHIFT // shift pud index into position
@@ -179,7 +213,7 @@ ENTRY(vhpt_miss)
;;
(p10) itc.i r18 // insert the instruction TLB entry
(p11) itc.d r18 // insert the data TLB entry
-(p6) br.cond.spnt.many page_fault // handle bad address/page not present (page fault)
+(p6) br.cond.spnt.many page_fault_sem // handle bad address/page not present (page fault)
mov cr.ifa=r22

#ifdef CONFIG_HUGETLB_PAGE
@@ -197,11 +231,12 @@ ENTRY(vhpt_miss)
;;
#ifdef CONFIG_SMP
/*
- * Tell the assemblers dependency-violation checker that the above "itc" instructions
- * cannot possibly affect the following loads:
+ * We make sure the visibility of itc.* to generated purges (like ptc.ga)
+ * before we re-read the PTE.
+ * Having itc.i-d a new translation, there is no need for srlz.i, the rfi below
+ * will do the serialization.
*/
- dv_serialize_data
-
+(p7) srlz.d
/*
* Re-check pagetable entry. If they changed, we may have received a ptc.g
* between reading the pagetable and the "itc". If so, flush the entry we
@@ -214,25 +249,45 @@ ENTRY(vhpt_miss)
* r29 = *pud
* r20 = *pmd
* r18 = *pte
+ *
+ * There is no need to re-read *pgd, *pud, *pmd because of having "mmap_sem".
+ * The PTE page translation is guaranteed to be correct.
+ * The swapper does not take this semaphore for write => do re-check *pte.
*/
ld8 r25=[r21] // read *pte again
- ld8 r26=[r17] // read *pmd again
-#ifdef CONFIG_PGTABLE_4
- ld8 r19=[r28] // read *pud again
-#endif
- cmp.ne p6,p7=r0,r0
- ;;
- cmp.ne.or.andcm p6,p7=r26,r20 // did *pmd change
-#ifdef CONFIG_PGTABLE_4
- cmp.ne.or.andcm p6,p7=r19,r29 // did *pud change
-#endif
mov r27=PAGE_SHIFT<<2
;;
-(p6) ptc.l r22,r27 // purge PTE page translation
-(p7) cmp.ne.or.andcm p6,p7=r25,r18 // did *pte change
+ cmp.ne p6,p0=r25,r18 // did *pte change?
;;
(p6) ptc.l r16,r27 // purge translation
-#endif
+ /*
+ * Tell the assemblers dependency-violation checker that the above "ptc" instruction
+ * cannot possibly affect the following loads/stores.
+ */
+ dv_serialize_data
+
+1: /*
+ * If (pUsr: user region fault){
+ * __s64 r27, r28, *r30 = &current->mm->mmap_sem;
+ *
+ * //
+ * // __up_read(&current->mm->mmap_sem);
+ * //
+ * r28 = ia64_fetchadd8_rel_nta(&r30->count, -1);
+ * r27 = r28 - 1;
+ * if (unlikely(r28 < 0))
+ * if (unlikely((r27 & RWSEM_ACTIVE_MASK) = 0))
+ * rwsem_wake(sem);
+ * }
+ */
+(pUsr) fetchadd8.rel.nta r28 = [r30], -1
+ ;;
+(pUsr) adds r27 = -1, r28
+(pUsr) cmp.lt.unc p8, p0 = r28, r0
+(p8) br.cond.spnt.few call_sem_wake_up
+ ;;
+back_to_vhpt_miss: // No need to call "rwsem_wake()"
+#endif // CONFIG_SMP

mov pr=r31,-1 // restore predicate registers
rfi
@@ -282,6 +337,60 @@ ENTRY(itlb_miss)
rfi
END(itlb_miss)

+
+#ifdef CONFIG_SMP
+ /*
+ * Arrivig from "vhpt_miss":
+ *
+ * ...
+ * If (pUsr: user mode fault){
+ * __s64 r27, r28, *r30 = &current->mm->mmap_sem;
+ *
+ * //
+ * // __up_read(&current->mm->mmap_sem);
+ * //
+ * r28 = ia64_fetchadd8_rel_nta(&r30->count, -1);
+ * r27 = r28 - 1;
+ * if (unlikely(r28 < 0))
+ *
+ * //
+ * // *** We are here: ***
+ * //
+ * if (unlikely((r27 & RWSEM_ACTIVE_MASK) = 0))
+ * rwsem_wake(sem);
+ * }
+ * ...
+ */
+call_sem_wake_up:
+ cmp4.eq p0, p8 = 0, r27
+(p8) br.cond.sptk.few back_to_vhpt_miss
+ ;;
+ /*
+ * Call "my_rwsem_wake(IA64_KR(MM_SEM))". Ppredicates are in r31, psr.dt is off.
+ */
+ ssm psr.dt
+ ;;
+ srlz.d
+ ;;
+ SAVE_MIN_WITH_COVER
+ alloc r15 = ar.pfs, 0, 0, 1, 0
+ mov out0 = IA64_KR(MM_SEM) // &current->mm->mmap_sem
+ adds r3=8, r2 // set up second base pointer
+ ;;
+ ssm psr.ic | PSR_DEFAULT_BITS
+ ;;
+ srlz.i // guarantee that interruption collectin is on
+ ;;
+(p15) ssm psr.i // restore psr.i
+ movl r14 = ia64_leave_kernel
+ ;;
+ SAVE_REST
+ mov rp = r14
+ ;;
+ br.call.sptk.many b6 = my_rwsem_wake // ignore return address
+#endif // CONFIG_SMP
+
+
.org ia64_ivt+0x0800
/////////////////////////////////////////////////////////////////////////////////////////
// 0x0800 Entry 2 (size 64 bundles) DTLB (9,48)
@@ -326,6 +434,21 @@ dtlb_fault:
rfi
END(dtlb_miss)

+
+ //-----------------------------------------------------------------------------------
+ // call do_page_fault (predicates are in r31, psr.dt may be off, r16 is faulting address)
+ // We DON'T have "mmap_sem" for read
+ENTRY(page_fault)
+ ssm psr.dt
+ ;;
+ srlz.i
+ ;;
+ SAVE_MIN_WITH_COVER
+ mov r15 = r0 // We DON'T have "mmap_sem" for read
+ br.sptk.few page_fault_common
+END(page_fault)
+
+
.org ia64_ivt+0x0c00
/////////////////////////////////////////////////////////////////////////////////////////
// 0x0c00 Entry 3 (size 64 bundles) Alt ITLB (19)
@@ -499,32 +622,39 @@ ENTRY(ikey_miss)
FAULT(6)
END(ikey_miss)

+
//-----------------------------------------------------------------------------------
// call do_page_fault (predicates are in r31, psr.dt may be off, r16 is faulting address)
-ENTRY(page_fault)
+ // If user region fault has happened => we keep "mmap_sem" for read
+ENTRY(page_fault_sem)
ssm psr.dt
;;
srlz.i
;;
SAVE_MIN_WITH_COVER
- alloc r15=ar.pfs,0,0,3,0
- mov out0=cr.ifa
- mov out1=cr.isr
- adds r3=8,r2 // set up second base pointer
+ add r15 = 1, r0 // If user region fault has happened =>
+ // We have "mmap_sem" for read
+page_fault_common:
+ alloc r14 = ar.pfs, 0, 0, 4, 0
+ mov out0 = cr.ifa
+ mov out1 = cr.isr
+ adds r3 = 8, r2 // set up second base pointer
;;
ssm psr.ic | PSR_DEFAULT_BITS
;;
srlz.i // guarantee that interruption collectin is on
;;
(p15) ssm psr.i // restore psr.i
- movl r14=ia64_leave_kernel
+ movl r14 = ia64_leave_kernel
;;
SAVE_REST
- mov rp=r14
+ mov rp = r14
;;
- adds out2\x16,r12 // out2 = pointer to pt_regs
+ adds out2 = 16, r12 // out2 = pointer to pt_regs
+ mov out3 = r15 // Is "mmap_sem" taken for read?
br.call.sptk.many b6=ia64_do_page_fault // ignore return address
-END(page_fault)
+END(page_fault_sem)
+

.org ia64_ivt+0x1c00
/////////////////////////////////////////////////////////////////////////////////////////
--- linux-2.6.16.9/include/asm-ia64/kregs.h 2006-04-20 10:36:46.000000000 +0200
+++ new/include/asm-ia64/kregs.h 2006-04-20 14:53:14.000000000 +0200
@@ -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) */
--- linux-2.6.16.9/include/asm-ia64/mmu_context.h 2006-04-20 10:36:46.000000000 +0200
+++ new/include/asm-ia64/mmu_context.h 2006-04-20 14:59:18.000000000 +0200
@@ -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);
}