[PATCH] correction for PPC __compare_and_swap

[PATCH] correction for PPC __compare_and_swap

[brianmc1]

This patch corrects an error in PPC __compare_and_swap.

An isync is necessary after acquisition of a lock to discard all prefetched
instructions.  On page 335 of the The PowerPC Architecture:  A
Specification For A New Family Of RISC Processors book it states the
following:  The "sync" instruction is execution synchronizing.  It is not
context synchronizing, and therefore need not discard prefetched
instructions.  For context synchronization you can see page 371 where the
following instructions rfi, sc and isync can be used.   End of quote.

What can happen is the processor could speculative load values into
registers as it is acquiring the lock and there is an opportunity to have
fetched stale data because another processor still owns the lock and is
modifying data that is protected by the lock.  The processor that is trying
to acquire the lock has speculatively loaded the data the other processor
is modifying.  The processor finally succeeds in acquiring the lock and
continues on with the data it had already loaded.  The sync at the end does
not cause the prefetched data to be discarded.  The isync causes all the
speculative execution to be thrown away and re-executed.

The pthread_lock and pthread_unlock routines really should be writted to
not use compare_and_swap.  Compare_and_swap requires a sync at the
beginning and an isync at the end.  This causes two syncs and two isyncs
for every lock/unlock pair which causes performance and thus scalability
problems with threads.  The pthread_lock routine does not need a sync
before the aquisition but only an isync after acquisition.  The unlock
requires a sync before release of the lock and no isync at the end.
Therefore if written as separate routines then there would only be one sync
and one isync per lock/unlock pair which will give better performance and
thus better scalability.

2001-05-03     Brian McCorkle <brianmc1@us.ibm.com>

*  powerpc/pt-machine.h  (__compare_and_swap):     Change exit sync to
isync to flush completed speculative loads

--- glibc-2.2/linuxthreads/sysdeps/powerpc/pt-machine.h.org  Thu Apr 19
14:38:54 2001
+++ glibc-2.2/linuxthreads/sysdeps/powerpc/pt-machine.h      Mon Apr 23
14:10:15 2001
@@ -51,7 +51,6 @@
 {
   int ret;

-  MEMORY_BARRIER ();
   __asm__ __volatile__ (
        "0:    lwarx %0,0,%1 ;"
        "      xor. %0,%3,%0;"
@@ -59,9 +58,9 @@
        "      stwcx. %2,0,%1;"
        "      bne- 0b;"
        "1:    "
+       "   isync;"
     : "=&r"(ret)
     : "r"(p), "r"(newval), "r"(oldval)
     : "cr0", "memory");
-  MEMORY_BARRIER ();
   return ret == 0;
 }

Re: [PATCH] correction for PPC __compare_and_swap

[Kaz Kylheku]

On Fri, 4 May 2001 brianmc1@us.ibm.com wrote:

> This patch corrects an error in PPC __compare_and_swap.
>
> An isync is necessary after acquisition of a lock to discard all prefetched
> instructions.  On page 335 of the The PowerPC Architecture:  A
> Specification For A New Family Of RISC Processors book it states the
> following:  The "sync" instruction is execution synchronizing.  It is not
> context synchronizing, and therefore need not discard prefetched
> instructions.  For context synchronization you can see page 371 where the
> following instructions rfi, sc and isync can be used.   End of quote.
>
> What can happen is the processor could speculative load values into
> registers as it is acquiring the lock and there is an opportunity to have
> fetched stale data because another processor still owns the lock and is
> modifying data that is protected by the lock.  The processor that is trying
> to acquire the lock has speculatively loaded the data the other processor
> is modifying.  The processor finally succeeds in acquiring the lock and
> continues on with the data it had already loaded.  The sync at the end does
> not cause the prefetched data to be discarded.  The isync causes all the
> speculative execution to be thrown away and re-executed.

If you were to implement the macros READ_MEMORY_BARRIER,
WRITE_MEMORY_BARRIER and MEMORY_BARRIER for the PowerPC, how would you
assign the instructions to these? It seems that isync resembles a read
barrier, whereas sync is more like a write barrier that yet allows
stale reads.  How about a full barrier?

> Therefore if written as separate routines then there would only be one sync
> and one isync per lock/unlock pair which will give better performance and
> thus better scalability.

How about having no barriers at all in __compare_and_swap and let
the caller take care of all the memory synchronization?

It's probably best to assume that compare_and_swap() has no
synchronizing properties, only atomic access to one location that is
not ordered with respect to any other. The user of compare_and_swap()
should always use memory barrier macros as appropriate.  Even
compare_and_swap_with_release_semantics can't be counted on to do
anything particular because it's just mapped to compare_and_swap where
not available.

The MEMORY_BARRIER() macro should provide a full fence that no memory
accesses (read or write) can cross.

The WRITE_MEMORY_BARRIER() macro should provides, at the very least,  a
write-write fence, for use in situations like ensuring that the update
to a list node is flushed before the pointer is linked into a list.
I.e. a situation with no read dependencies.

The READ_MEMORY_BARRIER() macro provides, at the very least, a fence
against stale reads, useful in ensuring that dependent reads access
coherent data: example, loading a pointer from one location and then
dereferencing it to gain access to the referenced location should be
divided by a READ_MEMORY_BARRIER().

If no specialized read or write barrier is available, the
corresponding macro is just mapped to MEMORY_BARRIER().

With these macros, the synchronization code in functions like
__pthread_lock() can be constructed to do what is needed without
depending on compare_and_swap() to have built-in fences.

Re: [PATCH] correction for PPC __compare_and_swap

[Geoff Keating]

> From: brianmc1@us.ibm.com
> Date: Fri, 4 May 2001 14:59:00 +0100

> This patch corrects an error in PPC __compare_and_swap.
> 
> An isync is necessary after acquisition of a lock to discard all prefetched
> instructions.  On page 335 of the The PowerPC Architecture:  A
> Specification For A New Family Of RISC Processors book it states the
> following:  The "sync" instruction is execution synchronizing.  It is not
> context synchronizing, and therefore need not discard prefetched
> instructions.  For context synchronization you can see page 371 where the
> following instructions rfi, sc and isync can be used.   End of quote.
> 
> What can happen is the processor could speculative load values into
> registers as it is acquiring the lock and there is an opportunity to have
> fetched stale data because another processor still owns the lock and is
> modifying data that is protected by the lock. 

The Programming Environments Manual says that 'Executing a sync
instruction ensures that all instructions previously initiated appear
to have completed before any subsequent instructions are initiated.'

It's true that the processor can prefetch _instructions_ before a sync
and execute them afterwards, but any memory operations that those
instructions perform must appear to be executed after any memory
operations before the sync, otherwise the processor is not PowerPC
conformant.

> The processor that is trying to acquire the lock has speculatively
> loaded the data the other processor is modifying.  The processor
> finally succeeds in acquiring the lock and continues on with the
> data it had already loaded.  The sync at the end does not cause the
> prefetched data to be discarded.  The isync causes all the
> speculative execution to be thrown away and re-executed.

I'm not sure if the sync should cause the prefetched data to be
discarded (unless there was other bus traffic), but the bus broadcast
of the other processor (the one releasing the lock) caused by the sync
before it releases certainly should.


Are you experiencing real problems, or is all this from code inspection?

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: [PATCH] correction for PPC __compare_and_swap

[Andreas Jaeger]

brianmc1@us.ibm.com writes:

> Ok,
> 
> Our Java guys tried your patch and say it looks good to them, so
> 
> . I would like to go with your patch rather than mine.  I like yours
> better.

Geoff, shall I commit your patch to CVS?

Andreas
-- 
 Andreas Jaeger
  SuSE Labs aj@suse.de
   private aj@arthur.inka.de
    http://www.suse.de/~aj

Re: [PATCH] correction for PPC __compare_and_swap

[brianmc1]

Ok,

Our Java guys tried your patch and say it looks good to them, so

. I would like to go with your patch rather than mine.  I like yours
better.
. I have looked into getting rid of the reservation code on unlock.  I
don't see any practical way to do that.  I would like to drop that issue.
. I think this addresses some of what Kaz was saying, but certainly not
all.  (I'm sorry I didn't respond.  Things got interesting here.)  I have
been reviewing the additional postings forwarded by Alexander.  I would
like to have a separate discussion on that but I'm not clear that this is
the correct forum.  Should that be taken offline?

brian

Geoff Keating <geoffk@geoffk.org> on 05/10/2001 04:30:53 AM

Please respond to Geoff Keating <geoffk@redhat.com>

To:   David Mehaffy/Austin/IBM@IBMUS
cc:   libc-alpha@sources.redhat.com, Brian Mccorkle/Austin/IBM@IBMUS
Subject:  Re: [PATCH] correction for PPC __compare_and_swap


> From: dmehaffy@us.ibm.com
> X-Lotus-FromDomain: IBMUS
> cc: libc-alpha@sources.redhat.com, brianmc1@us.ibm.com
> Date: Wed, 9 May 2001 20:08:21 -0500
> Content-Disposition: inline
>
> Geoff,
>
> I'll have Brian tryout your patch with our Java people and see if it
solves
> their problem.  Meanwhile I will look at seeing if I can come up with a
> patch that doesn't use __compare_and_swap for the lock release.  I agree
> that we would like to not change machine independent code but I think we
> will have to change a line or two and we can #ifdef powerpc the code
though
> I hope I can find away around that.

The #ifdef should be something like

#ifdef RELEASE_USING_STORE

that is, a generic #define rather than just 'is this powerpc'.  I'm
sure other machines have this same property.

--
- Geoffrey Keating <geoffk@geoffk.org>

Re: [PATCH] correction for PPC __compare_and_swap

[Geoff Keating]

> From: dmehaffy@us.ibm.com
> X-Lotus-FromDomain: IBMUS
> cc: libc-alpha@sources.redhat.com, brianmc1@us.ibm.com
> Date: Wed, 9 May 2001 20:08:21 -0500
> Content-Disposition: inline
> 
> Geoff,
> 
> I'll have Brian tryout your patch with our Java people and see if it solves
> their problem.  Meanwhile I will look at seeing if I can come up with a
> patch that doesn't use __compare_and_swap for the lock release.  I agree
> that we would like to not change machine independent code but I think we
> will have to change a line or two and we can #ifdef powerpc the code though
> I hope I can find away around that.

The #ifdef should be something like

#ifdef RELEASE_USING_STORE

that is, a generic #define rather than just 'is this powerpc'.  I'm
sure other machines have this same property.

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: [PATCH] correction for PPC __compare_and_swap

[dmehaffy]

Geoff,

I'll have Brian tryout your patch with our Java people and see if it solves
their problem.  Meanwhile I will look at seeing if I can come up with a
patch that doesn't use __compare_and_swap for the lock release.  I agree
that we would like to not change machine independent code but I think we
will have to change a line or two and we can #ifdef powerpc the code though
I hope I can find away around that.

Dave

Dr. David W. Mehaffy                                   Senior Technical
Staff Member
AIX System Architecture & Linux Affinity
Voice:  512-838-3476  Tie: 678-3476
B/905-8H006  MS/9586
11400 Burnet Road
Austin, TX 78758

Re: [PATCH] correction for PPC __compare_and_swap

[Geoff Keating]

> From: dmehaffy@us.ibm.com
> cc: brianmc1@us.ibm.com
> Date: Wed, 9 May 2001 16:53:50 -0500
> 
> While this patch technically does not fix an error in PPC
> __compare_and_swap, it does fix a performance problem with lock/unlock in
> pthreads.  This was uncovered when we were fixing bugs in the kernel and
> libraries with Java running on a 4-way SMP Power 3 processor. This change
> in combination with other work did cause Java to function correctly,
> so it may have been a timing issue, but it is easy to argue that this
> change
> should be accepted based on its performance merits alone.

Hmmm.  OK, so it's not a correctness change, it's a performance
change.  I can go for that.

> It is well known that sync's should be avoided whenever possible on PPC  as
> these result in broadcasts to all processor to make sure memory is coherent
> on all processors.  This is very expensive.  The proposed change will get
> rid of two syncs as written.  The isync is local to the processor and does
> not cause any bus traffic between processors and is all that is necessary
> in this case.
> 
> Kaz was on the right track suggesting that the compare and swap should not
> use sync and isync at all but be just an atomic primitive and the calling
> routines should be responsible for doing the sync or isync before or after
> as appropriate.

Yes, I agree with that too.

>  Because the routine is used for lock and unlock,  it is
> actually better to write them as separate routines, inlining the compare
> and swap which also gets rid of a lwarx/stwcx. pair which are also somewhat
> expensive.   The optimimum way to write the routines is as follows (in
> pseudo code):
> 
> unlock:  sync
>          stw 0, lock_location
>          blr

Yes.

> In the unlock case the sync is all that is  necessary to make all changes
> protected by the lock globally visible.  Note that no lwarx or stwcx. is
> needed.
> 
> lock:
> 1:   lwarx   r5, lock_location
>      cmpiw r5, 0
>      bne 2f:
>      stwcx. 1, lock_location
>      bne 1b
>      isync
>      blr
> 2:   need to indicate the lock is already locked (could spin if you want to
>      in this case or put on a sleep queue)
>      blr
> 
> In the lock case no sync is required at the beginning because all changes
> are visible at this point from the unlocker of the lock.  The isync is
> necessary to make sure the processor has done no speculative loads before
> the actual acquire of the lock. 

Now I see.  The isync is being used as a cheaper, local, sync.  That
makes sense.

> Only the processor that is getting the lock needs to get rid of the
> speculative loads because he has the lock, the other processor don't
> care so there is no need to do a sync which would broadcast the
> results to all processor making them invalidate their data.
> 
> This is the implementation we have been using in AIX since the first
> introduction of PowerPC SMPs.  It has been found to be the most optimal
> path length and cycle count for implementation of locks.  In this form
> there is only one sync and one isync for a lock/unlock pair as compared to
> the 4 syncs (which are very heavy weight) in the current code.  Also there
> is the elimination of a lwarx/stwcx. pair as well which cause bus
> transactions which are expensive because of the reservation protocol.

I can't work out how to get the library to stop using compare_and_swap
to release locks...  Any ideas?  I don't want to touch the
machine-independent part if I can help it.

> I would be happy to supply a formal patch that implements locks this way
> for PPC (though it is very simple to implement from the pseudo code).  Also
> to note this is exactly how the sample lock code supplied in the PowerPC
> Architecture book (page 254) and the PowerPC Microprocessor Family: The
> Programming Environments (page E4) suggest that locks be implemented for
> optimal performance.

I'd be very happy if people could test this patch on an SMP system and
see how it does.

-- 
- Geoffrey Keating <geoffk@geoffk.org>

===File ~/patches/cygnus/glibc-linuxthreads-lesssync.patch===
2001-05-09  Geoff Keating  <geoffk@redhat.com>

	* sysdeps/powerpc/pt-machine.h 
	(HAS_COMPARE_AND_SWAP_WITH_RELEASE_SEMANTICS): Define.
	(__compare_and_swap): Remove memory barriers.
	(__compare_and_swap_with_release_semantics): New function.

Index: linuxthreads/sysdeps/powerpc/pt-machine.h
===================================================================
RCS file: /cvs/glibc/libc/linuxthreads/sysdeps/powerpc/pt-machine.h,v
retrieving revision 1.7
diff -p -u -u -p -r1.7 pt-machine.h
--- pt-machine.h	2000/07/22 02:24:23	1.7
+++ pt-machine.h	2001/05/10 00:06:21
@@ -1,6 +1,6 @@
 /* Machine-dependent pthreads configuration and inline functions.
    powerpc version.
-   Copyright (C) 1996, 1997, 1998, 2000 Free Software Foundation, Inc.
+   Copyright (C) 1996, 1997, 1998, 2000, 2001 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
 
    The GNU C Library is free software; you can redistribute it and/or
@@ -38,20 +38,14 @@ register char * stack_pointer __asm__ ("
 /* Compare-and-swap for semaphores. */
 /* note that test-and-set(x) is the same as !compare-and-swap(x, 0, 1) */
 
-#define HAS_COMPARE_AND_SWAP
+#define HAS_COMPARE_AND_SWAP_WITH_RELEASE_SEMANTICS
 #define IMPLEMENT_TAS_WITH_CAS
 
-#if BROKEN_PPC_ASM_CR0
-static
-#else
-PT_EI
-#endif
-int
+PT_EI int
 __compare_and_swap (long int *p, long int oldval, long int newval)
 {
   int ret;
 
-  MEMORY_BARRIER ();
   __asm__ __volatile__ (
 	   "0:    lwarx %0,0,%1 ;"
 	   "      xor. %0,%3,%0;"
@@ -62,6 +56,26 @@ __compare_and_swap (long int *p, long in
 	: "=&r"(ret)
 	: "r"(p), "r"(newval), "r"(oldval)
 	: "cr0", "memory");
+  __asm__ __volatile__ ("isync" : : : "memory");
+  return ret == 0;
+}
+
+PT_EI int
+__compare_and_swap_with_release_semantics (long int *p, 
+					   long int oldval, long int newval)
+{
+  int ret;
+
   MEMORY_BARRIER ();
+  __asm__ __volatile__ (
+	   "0:    lwarx %0,0,%1 ;"
+	   "      xor. %0,%3,%0;"
+	   "      bne 1f;"
+	   "      stwcx. %2,0,%1;"
+	   "      bne- 0b;"
+	   "1:    "
+	: "=&r"(ret)
+	: "r"(p), "r"(newval), "r"(oldval)
+	: "cr0", "memory");
   return ret == 0;
 }
============================================================

Re: [PATCH] correction for PPC __compare_and_swap

[dmehaffy]

While this patch technically does not fix an error in PPC
__compare_and_swap, it does fix a performance problem with lock/unlock in
pthreads.  This was uncovered when we were fixing bugs in the kernel and
libraries with Java running on a 4-way SMP Power 3 processor. This change
in combination with other work did cause Java to function correctly,
so it may have been a timing issue, but it is easy to argue that this
change
should be accepted based on its performance merits alone.

It is well known that sync's should be avoided whenever possible on PPC  as
these result in broadcasts to all processor to make sure memory is coherent
on all processors.  This is very expensive.  The proposed change will get
rid of two syncs as written.  The isync is local to the processor and does
not cause any bus traffic between processors and is all that is necessary
in this case.

Kaz was on the right track suggesting that the compare and swap should not
use sync and isync at all but be just an atomic primitive and the calling
routines should be responsible for doing the sync or isync before or after
as appropriate.  Because the routine is used for lock and unlock,  it is
actually better to write them as separate routines, inlining the compare
and swap which also gets rid of a lwarx/stwcx. pair which are also somewhat
expensive.   The optimimum way to write the routines is as follows (in
pseudo code):

unlock:  sync
         stw 0, lock_location
         blr

In the unlock case the sync is all that is  necessary to make all changes
protected by the lock globally visible.  Note that no lwarx or stwcx. is
needed.

lock:
1:   lwarx   r5, lock_location
     cmpiw r5, 0
     bne 2f:
     stwcx. 1, lock_location
     bne 1b
     isync
     blr
2:   need to indicate the lock is already locked (could spin if you want to
     in this case or put on a sleep queue)
     blr

In the lock case no sync is required at the beginning because all changes
are visible at this point from the unlocker of the lock.  The isync is
necessary to make sure the processor has done no speculative loads before
the actual acquire of the lock.  Only the processor that is getting the
lock needs to get rid of the speculative loads because he has the lock, the
other processor don't care so there is no need to do a sync which would
broadcast the results to all processor making them invalidate their data.

This is the implementation we have been using in AIX since the first
introduction of PowerPC SMPs.  It has been found to be the most optimal
path length and cycle count for implementation of locks.  In this form
there is only one sync and one isync for a lock/unlock pair as compared to
the 4 syncs (which are very heavy weight) in the current code.  Also there
is the elimination of a lwarx/stwcx. pair as well which cause bus
transactions which are expensive because of the reservation protocol.

I would be happy to supply a formal patch that implements locks this way
for PPC (though it is very simple to implement from the pseudo code).  Also
to note this is exactly how the sample lock code supplied in the PowerPC
Architecture book (page 254) and the PowerPC Microprocessor Family: The
Programming Environments (page E4) suggest that locks be implemented for
optimal performance.


Dave

Dr. David W. Mehaffy                                   Senior Technical
Staff Member
AIX System Architecture & Linux Affinity
Voice:  512-838-3476  Tie: 678-3476
B/905-8H006  MS/9586
11400 Burnet Road
Austin, TX 78758