Fix race in the accessed/dirty bit handlers

Fix race in the accessed/dirty bit handlers

[Christoph Lameter]

A pte may be zapped by the swapper, exiting process, unmapping or page
migration while the accessed or dirty bit handers are about to run. In that
case the accessed bit or dirty is set on an zeroed pte which leads the VM to
conclude that this is a swap pte. This may lead to

- Messages from the vm like

swap_free: Bad swap file entry 4000000000000000

- Processes being aborted

swap_dup: Bad swap file entry 4000000000000000
VM: killing process ....

Page migration is particular suitable for the creation of this race since
it needs to remove and restore page table entries.

The fix here is to check for the present bit and simply not update
the pte if the page is not present anymore. If the page is not present
then the fault handler should run next which will take care of the problem
by bringing the page back and then mark the page dirty or move it onto the
active list.

Signed-off-by: Christoph Lameter <clameter@sgi.com>

Index: linux-2.6.16-rc5-mm3/arch/ia64/kernel/ivt.S
=================================--- linux-2.6.16-rc5-mm3.orig/arch/ia64/kernel/ivt.S	2006-03-07 09:17:22.000000000 -0800
+++ linux-2.6.16-rc5-mm3/arch/ia64/kernel/ivt.S	2006-03-07 18:53:11.000000000 -0800
@@ -561,11 +561,12 @@ ENTRY(dirty_bit)
 	;;					// avoid RAW on r18
 	mov ar.ccv=r18				// set compare value for cmpxchg
 	or r25=_PAGE_D|_PAGE_A,r18		// set the dirty and accessed bits
+	tbit.z p7,p6 = r18,_PAGE_P_BIT		// Check present bit
 	;;
-	cmpxchg8.acq r26=[r17],r25,ar.ccv
+(p6)	cmpxchg8.acq r26=[r17],r25,ar.ccv	// Only update if page is present
 	mov r24=PAGE_SHIFT<<2
 	;;
-	cmp.eq p6,p7=r26,r18
+(p6)	cmp.eq p6,p7=r26,r18			// Only compare if page is present
 	;;
 (p6)	itc.d r25				// install updated PTE
 	;;
@@ -626,11 +627,12 @@ ENTRY(iaccess_bit)
 	;;
 	mov ar.ccv=r18				// set compare value for cmpxchg
 	or r25=_PAGE_A,r18			// set the accessed bit
+	tbit.z p7,p6 = r18,_PAGE_P_BIT	 	// Check present bit
 	;;
-	cmpxchg8.acq r26=[r17],r25,ar.ccv
+(p6)	cmpxchg8.acq r26=[r17],r25,ar.ccv	// Only if page present
 	mov r24=PAGE_SHIFT<<2
 	;;
-	cmp.eq p6,p7=r26,r18
+(p6)	cmp.eq p6,p7=r26,r18			// Only if page present
 	;;
 (p6)	itc.i r25				// install updated PTE
 	;;
@@ -680,11 +682,12 @@ ENTRY(daccess_bit)
 	;;					// avoid RAW on r18
 	mov ar.ccv=r18				// set compare value for cmpxchg
 	or r25=_PAGE_A,r18			// set the dirty bit
+	tbit.z p7,p6 = r18,_PAGE_P_BIT		// Check present bit
 	;;
-	cmpxchg8.acq r26=[r17],r25,ar.ccv
+(p6)	cmpxchg8.acq r26=[r17],r25,ar.ccv	// Only if page is present
 	mov r24=PAGE_SHIFT<<2
 	;;
-	cmp.eq p6,p7=r26,r18
+(p6)	cmp.eq p6,p7=r26,r18			// Only if page is present
 	;;
 (p6)	itc.d r25				// install updated PTE
 	/*

Re: Fix race in the accessed/dirty bit handlers

[Robin Holt]

Are you sure this does not lead to a data integrity issue.  What if we
have a clean writable page.  If we get started on the dirty handler and
the pte gets zapped from under us, the page would not get marked as dirty
(pte had not gotten updated yet) and the process would continue running.
If the page never gets dirtied again until the process terminates, we
would never record a need to flush it to backing store.

I can possibly buy the change to the iaccess_bit handler, but I would need
a better explanation of how a race is prevented for the dirty_bit handler.

I think this might be the wrong direction, but I am still not awake
enough to think all the way through this.

Thanks,
Robin


On Tue, Mar 07, 2006 at 07:05:32PM -0800, Christoph Lameter wrote:
> A pte may be zapped by the swapper, exiting process, unmapping or page
> migration while the accessed or dirty bit handers are about to run. In that
> case the accessed bit or dirty is set on an zeroed pte which leads the VM to
> conclude that this is a swap pte. This may lead to
> 
> - Messages from the vm like
> 
> swap_free: Bad swap file entry 4000000000000000
> 
> - Processes being aborted
> 
> swap_dup: Bad swap file entry 4000000000000000
> VM: killing process ....
> 
> Page migration is particular suitable for the creation of this race since
> it needs to remove and restore page table entries.
> 
> The fix here is to check for the present bit and simply not update
> the pte if the page is not present anymore. If the page is not present
> then the fault handler should run next which will take care of the problem
> by bringing the page back and then mark the page dirty or move it onto the
> active list.
> 
> Signed-off-by: Christoph Lameter <clameter@sgi.com>
> 
> Index: linux-2.6.16-rc5-mm3/arch/ia64/kernel/ivt.S
> =================================> --- linux-2.6.16-rc5-mm3.orig/arch/ia64/kernel/ivt.S	2006-03-07 09:17:22.000000000 -0800
> +++ linux-2.6.16-rc5-mm3/arch/ia64/kernel/ivt.S	2006-03-07 18:53:11.000000000 -0800
> @@ -561,11 +561,12 @@ ENTRY(dirty_bit)
>  	;;					// avoid RAW on r18
>  	mov ar.ccv=r18				// set compare value for cmpxchg
>  	or r25=_PAGE_D|_PAGE_A,r18		// set the dirty and accessed bits
> +	tbit.z p7,p6 = r18,_PAGE_P_BIT		// Check present bit
>  	;;
> -	cmpxchg8.acq r26=[r17],r25,ar.ccv
> +(p6)	cmpxchg8.acq r26=[r17],r25,ar.ccv	// Only update if page is present
>  	mov r24=PAGE_SHIFT<<2
>  	;;
> -	cmp.eq p6,p7=r26,r18
> +(p6)	cmp.eq p6,p7=r26,r18			// Only compare if page is present
>  	;;
>  (p6)	itc.d r25				// install updated PTE
>  	;;
> @@ -626,11 +627,12 @@ ENTRY(iaccess_bit)
>  	;;
>  	mov ar.ccv=r18				// set compare value for cmpxchg
>  	or r25=_PAGE_A,r18			// set the accessed bit
> +	tbit.z p7,p6 = r18,_PAGE_P_BIT	 	// Check present bit
>  	;;
> -	cmpxchg8.acq r26=[r17],r25,ar.ccv
> +(p6)	cmpxchg8.acq r26=[r17],r25,ar.ccv	// Only if page present
>  	mov r24=PAGE_SHIFT<<2
>  	;;
> -	cmp.eq p6,p7=r26,r18
> +(p6)	cmp.eq p6,p7=r26,r18			// Only if page present
>  	;;
>  (p6)	itc.i r25				// install updated PTE
>  	;;
> @@ -680,11 +682,12 @@ ENTRY(daccess_bit)
>  	;;					// avoid RAW on r18
>  	mov ar.ccv=r18				// set compare value for cmpxchg
>  	or r25=_PAGE_A,r18			// set the dirty bit
> +	tbit.z p7,p6 = r18,_PAGE_P_BIT		// Check present bit
>  	;;
> -	cmpxchg8.acq r26=[r17],r25,ar.ccv
> +(p6)	cmpxchg8.acq r26=[r17],r25,ar.ccv	// Only if page is present
>  	mov r24=PAGE_SHIFT<<2
>  	;;
> -	cmp.eq p6,p7=r26,r18
> +(p6)	cmp.eq p6,p7=r26,r18			// Only if page is present
>  	;;
>  (p6)	itc.d r25				// install updated PTE
>  	/*
> -
> To unsubscribe from this list: send the line "unsubscribe linux-ia64" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Fix race in the accessed/dirty bit handlers

[Christoph Lameter]

On Wed, 8 Mar 2006, Robin Holt wrote:

> Are you sure this does not lead to a data integrity issue.  What if we
> have a clean writable page.  If we get started on the dirty handler and
> the pte gets zapped from under us, the page would not get marked as dirty
> (pte had not gotten updated yet) and the process would continue running.

No the process would not continue running. The page is not present and 
therefore the page fault handler gets involved next to get the page back. 

The page fault handler gets invoked with the write flag set. So it 
will bring back the page and mark it dirty. Then it will return to the 
process which will perform the write operation.

RE: Fix race in the accessed/dirty bit handlers

[Chen, Kenneth W]

Christoph Lameter wrote on Wednesday, March 08, 2006 7:33 AM
> On Wed, 8 Mar 2006, Robin Holt wrote:
> > Are you sure this does not lead to a data integrity issue.  What if we
> > have a clean writable page.  If we get started on the dirty handler and
> > the pte gets zapped from under us, the page would not get marked as dirty
> > (pte had not gotten updated yet) and the process would continue running.
> 
> No the process would not continue running. The page is not present and 
> therefore the page fault handler gets involved next to get the page back. 
> 
> The page fault handler gets invoked with the write flag set. So it 
> will bring back the page and mark it dirty. Then it will return to the 
> process which will perform the write operation.

What happens to a scenario where you zap the pte right after dirty bit
handler just finished.  Won't you lost that "dirty" information?

- Ken

RE: Fix race in the accessed/dirty bit handlers

[Christoph Lameter]

On Wed, 8 Mar 2006, Chen, Kenneth W wrote:

> What happens to a scenario where you zap the pte right after dirty bit
> handler just finished.  Won't you lost that "dirty" information?

Well zapping is not really what happens. We do an atomic exchange with 
zero. The  dirty bit information is moved to the page_struct (and then
finally the page has a chance to be updated on disk!).
 
See in asm-ia64/pgtable.h

static inline pte_t
ptep_get_and_clear(struct mm_struct *mm, unsigned long addr, pte_t *ptep)
{
#ifdef CONFIG_SMP
        return __pte(xchg((long *) ptep, 0));
#else
        pte_t pte = *ptep;
        pte_clear(mm, addr, ptep);
        return pte;
#endif
}


and from asm-generic/pgtable.h:

#ifndef __HAVE_ARCH_PTEP_CLEAR_FLUSH
#define ptep_clear_flush(__vma, __address, __ptep)                      \
({                                                                      \
        pte_t __pte;                                                    \
        __pte = ptep_get_and_clear((__vma)->vm_mm, __address, __ptep);  \
        flush_tlb_page(__vma, __address);                               \
        __pte;                                                          \
})
#endif


then in mm/rmap.c

/*
 * Subfunctions of try_to_unmap: try_to_unmap_one called
 * repeatedly from either try_to_unmap_anon or try_to_unmap_file.
 */
static int try_to_unmap_one(struct page *page, struct vm_area_struct *vma,
                                int ignore_refs)

....


       /* Nuke the page table entry. */
        flush_cache_page(vma, address, page_to_pfn(page));
        pteval = ptep_clear_flush(vma, address, pte);

        /* Move the dirty bit to the physical page now the pte is gone. */
        if (pte_dirty(pteval))
                set_page_dirty(page);

RE: Fix race in the accessed/dirty bit handlers

[Luck, Tony]

>Page migration is particular suitable for the creation of this race since
>it needs to remove and restore page table entries.

I'm trying to understand why we haven't seen this problem before page
migration was invented.  Surely in the swapout case we have the same
situation ... swapper does "*pte = 0 ... ptc" to zap the pte and nuke
the TLB (in that order), but there is a window in between where the
process might try to update the accessed/dirty bits.

Have we just been lucky?
Is the window much wider for the process migration case?

-Tony

RE: Fix race in the accessed/dirty bit handlers

[Christoph Lameter]

On Wed, 8 Mar 2006, Luck, Tony wrote:

> >Page migration is particular suitable for the creation of this race since
> >it needs to remove and restore page table entries.
> 
> I'm trying to understand why we haven't seen this problem before page
> migration was invented.  Surely in the swapout case we have the same
> situation ... swapper does "*pte = 0 ... ptc" to zap the pte and nuke
> the TLB (in that order), but there is a window in between where the
> process might try to update the accessed/dirty bits.
> 
> Have we just been lucky?

Yes. The window is very small. The zapping must happen between the 
generation of the accessed/dirty fault and the cmpxchg in the 
dirty/accessed bit handlers. It seems also that most HPC machines do not 
use swap making it highly unlikely to encounter this race. The other cases 
where this could occur are probably even rarer.

> Is the window much wider for the process migration case?

Process migration must unmap all ptes in order to migrate a page. The 
testcase here was a loop that continually moves a set of processes 
(aim7) in order to stress page migration and correspondingly the page 
table handling of the VM.

RE: Fix race in the accessed/dirty bit handlers

[Luck, Tony]

>> Have we just been lucky?
>
>Yes. The window is very small. The zapping must happen between the 
>generation of the accessed/dirty fault and the cmpxchg in the 
>dirty/accessed bit handlers. It seems also that most HPC machines do not 
>use swap making it highly unlikely to encounter this race. The other cases 
>where this could occur are probably even rarer.

Thinking about this further ... in most cases the swap path will also
conceal any evidence that this happened, because it will overwrite
the pte with the swap file number and offset of where it stashed
the page ... so "we've been lucky for all these years" theory is
looking quite credible.

-Tony

RE: Fix race in the accessed/dirty bit handlers

[Christoph Lameter]

On Wed, 8 Mar 2006, Luck, Tony wrote:

> Thinking about this further ... in most cases the swap path will also
> conceal any evidence that this happened, because it will overwrite
> the pte with the swap file number and offset of where it stashed
> the page ... so "we've been lucky for all these years" theory is
> looking quite credible.

Hmm.... What happens for the dirty bit .... zero pte is marked dirty, 
however page is marked not present, thus page fault follows. By the time 
the fault handler checks the pte it is valid again since the 
swapper overwrote with a swap pte (otherwise we would get 
VM: killing process ...), swapper overwrites with swap pte. The 
fault is a write fauklt which restores the page and marks it dirty. Then 
the process writes to the page. So that seems to be okay.

But this only occurs for anonymous pages. If the page is file backed and 
zapped by the swapper then the pte is not rewritten again but the fault 
handler tries to "interpret" the strange pte.

RE: Fix race in the accessed/dirty bit handlers

[Zoltan Menyhart]

[-- Attachment #1: Type: text/plain, Size: 1328 bytes --]

I have got a concern abut the synchronization.
(It is the same for the original code.)
The following sequence:

	itc.d r25             // install updated PTE
	;;
	ld8 r18=[r17]         // read PTE again
	;;
	cmp.eq p6,p7=r18,r25  // is it same as the newly installed

I think is not safe enough.
The ";;" orders dependencies like R-A-W only, not the relatively slow cache
& tlb coherency operations, like "itc".
This is why I think we need my (first) patch.

I can imagine the following scenario:

1. "itc.d r25" is issued.
    It is not globally performed (an external purge request would miss it).

2. "ld8 r18=[r17]" is executed - we read back the good value.
    (Even an L3 cache miss can be quickly prepared on multi core / threaded
    processors by a cache intervention.)

3. Someone tears down the same PTE: s/he clears it, then
4. s/he issues a global purge - we miss it, because our "itc.d r25" still
    has not been globally performed.

5. Finally "itc.d r25" is globally performed (e.g. it is in our DTLB1).

6. "cmp" compares a stale value in r18 and our freshly inserted translation
    has missed the purge.

This is an example for the dirty bit handler, the others are similar.

BTW cannot take we this good opportunity to make the code somewhat more readable?
(See my second patch.)

Thanks,

Zoltan Menyhart

[-- Attachment #2: srlz.d.diff --]
[-- Type: text/plain, Size: 1155 bytes --]

--- old/arch/ia64/kernel/ivt.S	2006-03-09 13:38:21.000000000 +0100
+++ new/arch/ia64/kernel/ivt.S	2006-03-09 13:50:48.000000000 +0100
@@ -571,11 +571,18 @@ ENTRY(dirty_bit)
 (p6)	itc.d r25				// install updated PTE
 	;;
 	/*
-	 * Tell the assemblers dependency-violation checker that the above "itc" instructions
-	 * cannot possibly affect the following loads:
+	 * Make sure that the "itc" has been performed before we re-read the PTE.
+	 * (No, we are not going to use the freshly inserted translation for the next "ld".)
+	 * We have to make sure the freshly inserted translation can be hit by an external
+	 * purge request before we initiate the PTE re-fetch.
+	 * A simple ";;" does not make sure that the purges / invalidations go all the way
+	 * down (in case of page size of 64 K, up to 16 DTL0 entries may be purged and all
+	 * the L1D cache lines brought in via these translations need to be invalidated).
+	 */
+	srlz.d
+	/*
+	 * No need for ";;", the following "ld" can be in the same group as "srlz.d" is.
 	 */
-	dv_serialize_data
-
 	ld8 r18=[r17]				// read PTE again
 	;;
 	cmp.eq p6,p7=r18,r25			// is it same as the newly installed

[-- Attachment #3: spaces.diff --]
[-- Type: text/plain, Size: 2940 bytes --]

--- old/arch/ia64/kernel/ivt.S	2006-03-09 13:50:48.000000000 +0100
+++ new/arch/ia64/kernel/ivt.S	2006-03-09 13:54:37.000000000 +0100
@@ -548,27 +548,27 @@ ENTRY(dirty_bit)
 	 * page table TLB entry isn't present, we take a nested TLB miss hit where we look
 	 * up the physical address of the L3 PTE and then continue at label 1 below.
 	 */
-	mov r16=cr.ifa				// get the address that caused the fault
-	movl r30=1f				// load continuation point in case of nested fault
+	mov	r16 = cr.ifa			// get the address that caused the fault
+	movl	r30 = 1f			// load continuation point in case of nested fault
 	;;
-	thash r17=r16				// compute virtual address of L3 PTE
-	mov r29=b0				// save b0 in case of nested fault
-	mov r31=pr				// save pr
+	thash	r17 = r16			// compute virtual address of L3 PTE
+	mov	r29 = b0			// save b0 in case of nested fault
+	mov	r31 = pr			// save pr
 #ifdef CONFIG_SMP
-	mov r28=ar.ccv				// save ar.ccv
+	mov	r28 = ar.ccv			// save ar.ccv
 	;;
-1:	ld8 r18=[r17]
+1:	ld8	r18 = [r17]
 	;;					// avoid RAW on r18
-	mov ar.ccv=r18				// set compare value for cmpxchg
-	or r25=_PAGE_D|_PAGE_A,r18		// set the dirty and accessed bits
-	tbit.z p7,p6 = r18,_PAGE_P_BIT		// Check present bit
+	mov	ar.ccv = r18			// set compare value for cmpxchg
+	or	r25 = _PAGE_D|_PAGE_A,r18	// set the dirty and accessed bits
+	tbit.z	p7, p6  =  r18, _PAGE_P_BIT	// Check present bit
 	;;
-(p6)	cmpxchg8.acq r26=[r17],r25,ar.ccv	// Only update if page is present
-	mov r24=PAGE_SHIFT<<2
+(p6)	cmpxchg8.acq r26 = [r17], r25, ar.ccv	// Only update if page is present
+	mov	r24 = PAGE_SHIFT << 2
 	;;
-(p6)	cmp.eq p6,p7=r26,r18			// Only compare if page is present
+(p6)	cmp.eq	p6, p7 = r26, r18		// Only compare if page is present
 	;;
-(p6)	itc.d r25				// install updated PTE
+(p6)	itc.d	r25				// install updated PTE
 	;;
 	/*
 	 * Make sure that the "itc" has been performed before we re-read the PTE.
@@ -583,24 +583,24 @@ ENTRY(dirty_bit)
 	/*
 	 * No need for ";;", the following "ld" can be in the same group as "srlz.d" is.
 	 */
-	ld8 r18=[r17]				// read PTE again
+	ld8	r18 = [r17]			// read PTE again
 	;;
-	cmp.eq p6,p7=r18,r25			// is it same as the newly installed
+	cmp.eq	p6, p7 = r18, r25		// is it same as the newly installed
 	;;
-(p7)	ptc.l r16,r24
-	mov b0=r29				// restore b0
-	mov ar.ccv=r28
+(p7)	ptc.l	r16, r24
+	mov	b0 = r29			// restore b0
+	mov	ar.ccv = r28
 #else
 	;;
-1:	ld8 r18=[r17]
+1:	ld8	r18 = [r17]
 	;;					// avoid RAW on r18
-	or r18=_PAGE_D|_PAGE_A,r18		// set the dirty and accessed bits
-	mov b0=r29				// restore b0
+	or	r18 = _PAGE_D | _PAGE_A,r18	// set the dirty and accessed bits
+	mov	b0 = r29			// restore b0
 	;;
-	st8 [r17]=r18				// store back updated PTE
-	itc.d r18				// install updated PTE
+	st8	[r17] = r18			// store back updated PTE
+	itc.d	r18				// install updated PTE
 #endif
-	mov pr=r31,-1				// restore pr
+	mov	pr = r31, -1			// restore pr
 	rfi
 END(dirty_bit)
 

RE: Fix race in the accessed/dirty bit handlers

[Christoph Lameter]

On Thu, 9 Mar 2006, Zoltan Menyhart wrote:

> I think is not safe enough.
> The ";;" orders dependencies like R-A-W only, not the relatively slow cache
> & tlb coherency operations, like "itc".
> This is why I think we need my (first) patch.

Hmm.... maybe I am missing something. What do you mean by "global"? I do 
not have too much experience here. Just looking at the Intel manual. It 
seems that global refers to ptc broadcasting purges to all processors.
 
> I can imagine the following scenario:
> 
> 1. "itc.d r25" is issued.
>    It is not globally performed (an external purge request would miss it).

Right this only affects this processor. itc.d never has a global effect as 
far as I can see.
 
> 2. "ld8 r18=[r17]" is executed - we read back the good value.
>    (Even an L3 cache miss can be quickly prepared on multi core / threaded
>    processors by a cache intervention.)

Thats fine.
 
> 3. Someone tears down the same PTE: s/he clears it, then
> 4. s/he issues a global purge - we miss it, because our "itc.d r25" still
>    has not been globally performed.

itc.d is not globally performed at all. We could theorize that we may miss 
the purge because this processor may perform the itc.d immediately after 
getting the purge broadcast from another processor.

There is this cryptic sentence on page 3:127

"The visibility of the itc instruction to generated purges (ptc.g, ptc.ga) 
must occur before subsequent memory operations. From a software 
perspective, this is similar to acquire semantics. Serialization is still 
required to observe the side-effects of the translation being present."

What does this exactly mean? Guess we need some more details on how these 
purge broadcasts work.
 
> 5. Finally "itc.d r25" is globally performed (e.g. it is in our DTLB1).

The global is throwing me off again here.

> 6. "cmp" compares a stale value in r18 and our freshly inserted translation
>    has missed the purge.

Maybe.
 
> BTW cannot take we this good opportunity to make the code somewhat more
> readable?
> (See my second patch.)

The coding style used throughout seems to not use tabs. Your patch would 
make this piece of code deviate in style. If you want to do this then we 
would need to have agreement on the coding style change and then all asm 
code would have to be changed.

Re: Fix race in the accessed/dirty bit handlers

[Zoltan Menyhart]

Christoph Lameter wrote:
> [...]
> 
> Hmm.... maybe I am missing something. What do you mean by "global"? I do 
> not have too much experience here. Just looking at the Intel manual. It 
> seems that global refers to ptc broadcasting purges to all processors.

The term "globally performed" does not always mean that some info goes
out of a CPU.
A store is globally performed (in cached mode) when the new data is in the
(local) L2 and its status is set accordingly. I.e. any external demand will
find the freshly stored value and the correct cache status response.
If the cache line is in "E" state, then a transition to "M" will not be seen
from external agents, unless they explicitly ask for the data.

I consider an "itc" as globally performed if any external demand (purge)
will not miss our new translation and the HW responds accordingly (see TND#).

If the term "globally performed" is not well chosen, I can use this
longer phrase from the Intel book:
"visibility of the itc instruction to generated purges" is guaranteed.

>>1. "itc.d r25" is issued.
>>   It is not globally performed (an external purge request would miss it).
> 
> Right this only affects this processor. itc.d never has a global effect as 
> far as I can see.

Let's say: the visibility of "itc" to generated purges is not guaranteed
at this point.

>>2. "ld8 r18=[r17]" is executed - we read back the good value.
>>   (Even an L3 cache miss can be quickly prepared on multi core / threaded
>>   processors by a cache intervention.)
> 
> 
> Thats fine.

The problem is here: the algorithm requires that our new translation be
able to catch the external purge request *before* we issue "ld".

As far as I can see, the ";;" dos not delays this "ld" to guarantee that
the TLB entries involved all correctly updated (L1D invalidated, etc.).

>>3. Someone tears down the same PTE: s/he clears it, then
>>4. s/he issues a global purge - we miss it, because our "itc.d r25" still
>>   has not been globally performed.
> 
> 
> itc.d is not globally performed at all. We could theorize that we may miss 
> the purge because this processor may perform the itc.d immediately after 
> getting the purge broadcast from another processor.

Let's say: the visibility of "itc" to generated purges is still
not guaranteed at this point.

> There is this cryptic sentence on page 3:127
> 
> "The visibility of the itc instruction to generated purges (ptc.g, ptc.ga) 
> must occur before subsequent memory operations. From a software 
> perspective, this is similar to acquire semantics. Serialization is still 
> required to observe the side-effects of the translation being present."
> 
> What does this exactly mean? Guess we need some more details on how these 
> purge broadcasts work.

As far as I can see, we have to avoid to feed the memory / cache queues and
the TLB look up unit with new demands until the visibility of the itc
instruction to generated purges can be guaranteed.
In our case, "srlz.d" stalls the exec. pipeline.
This is why a ";;" is not enough.

>>5. Finally "itc.d r25" is globally performed (e.g. it is in our DTLB1).
> 
> 
> The global is throwing me off again here.

I mean the visibility of the itc instruction to generated purges is O.K.

>>6. "cmp" compares a stale value in r18 and our freshly inserted translation
>>   has missed the purge.
> 
> 
> Maybe.

In short: unless we use "srlz.d", how to make sure:
- the visibility of the "itc" instruction to generated purges is
  guaranteed first
- issuing "ld" goes after ?

Thanks,

Zoltan

Re: Fix race in the accessed/dirty bit handlers

[Christoph Lameter]

On Thu, 9 Mar 2006, Zoltan Menyhart wrote:

> In short: unless we use "srlz.d", how to make sure:
> - the visibility of the "itc" instruction to generated purges is
>  guaranteed first
> - issuing "ld" goes after ?

The manual states that serialization is only necessary before a data 
access uses the mapping. We do not use the mapping in the function we are 
discussing and I would think that the rfi is certainly serialization 
enough.

The manual also has a rather complex section on ptc purges.

I think we need to refer to how our purges work under ia64.

What we do in essence from the remote processor is:

1. We invalidate a pte (overwite the entry with zero)

2. We purge the caches (and then broadcast the purge?).

So if the fault handlers run then they will discover that either the pte 
has been zapped or the cmpxchg will fail. In either case we just do 
nothing and redo the fault.

I guess this scheme could fail if the remote processor would 
zap the pte and do the broadcast between the local processors cmpxchg and 
the itc. Thats only two bundles. 

Maybe we need some experts to explain the situation. Ken? David?

Re: Fix race in the accessed/dirty bit handlers

[David Mosberger-Tang]

On 3/9/06, Christoph Lameter <clameter@sgi.com> wrote:

> The manual states that serialization is only necessary before a data
> access uses the mapping. We do not use the mapping in the function we are
> discussing and I would think that the rfi is certainly serialization
> enough.

This is correct.

  --david
--
Mosberger Consulting LLC, http://www.mosberger-consulting.com/

RE: Fix race in the accessed/dirty bit handlers

[Chen, Kenneth W]

Christoph Lameter wrote on Thursday, March 09, 2006 10:28 AM
> On Thu, 9 Mar 2006, Zoltan Menyhart wrote:
> > In short: unless we use "srlz.d", how to make sure:
> > - the visibility of the "itc" instruction to generated purges is
> >   guaranteed first
> > - issuing "ld" goes after ?

Let's go back one step, the guarantee is coming from the fact that
ptc.ga happens after pte change.  And the fault handler guarantees
that by the time 2nd load happens, TLB state is consistent with
what is in the software page table.  It doesn't matter where the
ptc.ga come through.  As long as the TLB state is consistent with
respect to software page table, we are fine.  Considering the
following 3 cases:

CPU A        CPU B       | CPU A       CPU B     | cpu A    cpu B
-----        -----       | -----       -----     | -----    -----
             change pte  |                       |
                         |                       |
read pte                 |read pte               |read pte
insert TLB               |           change pte  |insert
re-read                  |insert                 |re-read
                         |re-read                |          change pte
                         |ptc.l

Global purge doesn't need to come into the picture here.


> I guess this scheme could fail if the remote processor would 
> zap the pte and do the broadcast between the local processors cmpxchg
> and the itc. Thats only two bundles. 

How can that fail?:

cpu A         cpu B
-----         -----
read
cmpxchg
              xchg
              ptc.g
itc
re-read
ptc.l

- Ken

Re: Fix race in the accessed/dirty bit handlers

[Zoltan Menyhart]

> CPU A        CPU B       | CPU A       CPU B     | cpu A    cpu B
> -----        -----       | -----       -----     | -----    -----
>              change pte  |                       |
>                          |                       |
> read pte                 |read pte               |read pte
> insert TLB               |           change pte  |insert
> re-read                  |insert                 |re-read
>                          |re-read                |          change pte
>                          |ptc.l

These scenarii assume that the sequence:

	insert TLB
	;;
	re-read

is executed in the same order for everyone as it is coded.

I think a ";;" not sufficient to make sure that the external
visibility of the "itc" to generated purges is established
first for everyone, before the "re-read" becomes visible.

> The manual states that serialization is only necessary before a data 
> access uses the mapping.

It also states on page 3:127:

"The visibility of the itc instruction to generated purges (ptc.g, ptc.ga) 
must occur before subsequent memory operations. From a software 
perspective, this is similar to acquire semantics. Serialization is still 
required to observe the side-effects of the translation being present."

> We do not use the mapping in the function we are 
> discussing

Agreed.

> and I would think that the rfi is certainly serialization 
> enough.

... for the future user mode accesses.

I consider an "itc" as completed when:
1. The new (local) translation is available for any new load / store request
2. There is no chance any more to miss an external purge request

I think we can agree on the 1st point.

As far as the 2nd one is concerned:
In order not to break our synchronization algorithm,
we need here to make sure that the external visibility of the "itc" to
generated purges is established first for everyone, before the "re-read"
becomes visible.

The only instruction I know of to synchronize with the "itc" mechanism is
the "srlz" instruction.

Thanks,

Zoltan

Re: Fix race in the accessed/dirty bit handlers

[Christian Hildner]

Zoltan Menyhart schrieb:

> The only instruction I know of to synchronize with the "itc" mechanism is
> the "srlz" instruction. 

rfi implies srlz.i (and srlz.d) as well.

Christian

Re: Fix race in the accessed/dirty bit handlers

[Zoltan Menyhart]

Christian Hildner wrote:
> Zoltan Menyhart schrieb:
> 
>> The only instruction I know of to synchronize with the "itc" mechanism is
>> the "srlz" instruction. 
> 
> 
> rfi implies srlz.i (and srlz.d) as well.

You are right as far as the user mode code is concerned.

Yet, we have not got any "rfi" in our

    insert TLB
    ;;
    re-read

sequence. Only a "srlz" can help.:

	itc.d	r25
	;;
	srlz.d
	ld8	r18 = [r17]

Thanks,

Zoltan

RE: Fix race in the accessed/dirty bit handlers

[Luck, Tony]

>	itc.d	r25
>	;;
>	srlz.d
>	ld8	r18 = [r17]

But it does not matter to the "ld8 r18 = [r17]" whether the "itc.d"
is visible or not.  r17 cannot be in the virtual address range that
will be affected by the itc.d, so the serialization here would just
slow things down, and have no effect at all.

-Tony

Re: Fix race in the accessed/dirty bit handlers

[Zoltan Menyhart]

Luck, Tony wrote:

>>	itc.d	r25
>>	;;
>>	srlz.d
>>	ld8	r18 = [r17]
> 
> But it does not matter to the "ld8 r18 = [r17]" whether the "itc.d"
> is visible or not.  r17 cannot be in the virtual address range that
> will be affected by the itc.d, so the serialization here would just
> slow things down, and have no effect at all.

I did say:

>> No, we are not going to use the freshly inserted translation for the next "ld". <<

Please consider the second issue I mentioned about the "itc":
Making sure that an external purge request will not be missed by our new
translation. See also on page 3:127:

"The visibility of the itc instruction to generated purges (ptc.g, ptc.ga) must occur before subsequent memory operations. From a software perspective, this is similar to acquire semantics. Serialization is still required to observe the side-effects of the translation being present."

How to tell if this "visibility of the itc instruction to generated purges"
has already been established?

I think a ";;" is not enough, this is why I propose this sequence:

    itc.d    r25
    ;;
    srlz.d
    ld8    r18 = [r17]

Thanks,

Zoltan

RE: Fix race in the accessed/dirty bit handlers

[Chen, Kenneth W]

Zoltan Menyhart wrote on Friday, March 10, 2006 1:47 AM
> > CPU A        CPU B       | CPU A       CPU B     | cpu A    cpu B
> > -----        -----       | -----       -----     | -----    -----
> >              change pte  |                       |
> >                          |                       |
> > read pte                 |read pte               |read pte
> > insert TLB               |           change pte  |insert
> > re-read                  |insert                 |re-read
> >                          |re-read                |          change pte
> >                          |ptc.l
> 
> These scenarii assume that the sequence:
> 
> 	insert TLB
> 	;;
> 	re-read
> 
> is executed in the same order for everyone as it is coded.

Just for the record, itc has acquire semantics, though this is not
immediately relevant in this discussion with respect to external
ptc.g.

- Ken

RE: Fix race in the accessed/dirty bit handlers

[Luck, Tony]

> Please consider the second issue I mentioned about the "itc":
> Making sure that an external purge request will not be missed by our new
> translation. See also on page 3:127:

While this is true, I'm still not seeing how this can cause
a problem (but I didn't see the problem that Christoph just
found that started this whole thread in six years of looking
at this code, so I'm willing to accept that I may be missing
something).

If another processor has a purge floating out there on the
bus at this time, it would be because that other processor
was making some change to this mapping.  In which case it
would have executed:

 *pte = new_value
 ptc

Are you saying that these events may become visible to the
processor that is executing the dirty_bit handler in either
order, so that you are worried we'll see the old *pte value
when we do the load, but miss the purge because we didn't
wait for the itc.d to complete before we did the load?

-Tony

RE: Fix race in the accessed/dirty bit handlers

[Chen, Kenneth W]

Zoltan Menyhart wrote on Friday, March 10, 2006 9:12 AM
> Please consider the second issue I mentioned about the "itc":
> Making sure that an external purge request will not be missed by our new
> translation. See also on page 3:127:
> 
> "The visibility of the itc instruction to generated purges (ptc.g, ptc.ga) must occur > before subsequent memory operations. From
a software perspective, this is similar to > acquire semantics. Serialization is still required to observe the side-effects of the >
translation being present."
> 
> How to tell if this "visibility of the itc instruction to generated purges"
> has already been established?
> 
> I think a ";;" is not enough, this is why I propose this sequence:
> 
>     itc.d    r25
>     ;;
>     srlz.d
>     ld8    r18 = [r17]

Thinking wild, I think we need a release semantics on the load.  But such
thing isn't available.

- Ken

Re: Fix race in the accessed/dirty bit handlers

[Zoltan Menyhart]

Luck, Tony wrote:

> If another processor has a purge floating out there on the
> bus at this time, it would be because that other processor
> was making some change to this mapping.  In which case it
> would have executed:
> 
>  *pte = new_value
>  ptc
> 
> Are you saying that these events may become visible to the
> processor that is executing the dirty_bit handler in either
> order, so that you are worried we'll see the old *pte value
> when we do the load, but miss the purge because we didn't
> wait for the itc.d to complete before we did the load?

Yes, I should have said in this way.

Thanks,

Zoltan