Fix sem_post race (bug 14532)

[Torvald Riegel]

On Wed, 2012-09-12 at 15:19 +0000, Joseph S. Myers wrote:
> On Tue, 11 Sep 2012, Torvald Riegel wrote:
> 
> > >    atomic_full_barrier ();
> > 
> > Why do we have the full barrier after the rel barrier?  Is it necessary?

Attached is a draft patch that documents the synchronization used to
build the semaphore.  Please comment whether that is useful for
everyone, or whether we need more details, a different format, or
whatever.  Perhaps we can use the semaphore as a template / example for
how concurrent code should be documented in glibc.

I tried to keep this short enough while still pointing out the
relationships with related code pieces.  I also used the C11/C++11
memory model terminology, even though glibc's sync functions are named
slightly differently.

Also, atomic operations without an _acq or _rel suffix seem to always
default to _acq.  Is this a guarantee (and thus should be documented)?
I'm wondering whether it would be better to use an explicit suffix in
the long-term.

> I wouldn't say we have it after the rel barrier.  Apart from the rel 
> barrier being a barrier before the compare-and-exchange operation, so the 
> barriers are separated by that operation, the formatting of the code 
> implies that the positioning of the barrier is logically "before the code 
> to wake a waiter" rather than "after the code to update the semaphore 
> value", and so the code to wake a waiter is where you should look for the 
> reason for this barrier.

I got confused because I didn't see a counterpart to the full fence
anywhere; so far, I assumed that futex_wait does not imply a full membar
before the read from the futex variable.  But the existing code relies
on this; is this guarantee commonly known to be true on all
architectures (e.g., is a syscall always like a full membar,
everywhere)?


Torvald

-------------- next part --------------
commit 8f909376fea5832ad49bb15756a7015d91a62e48
Author: Torvald Riegel <triegel@redhat.com>
Date:   Thu Sep 13 21:00:10 2012 +0200

    Document semaphore synchronization.

diff --git a/nptl/sysdeps/unix/sysv/linux/sem_post.c b/nptl/sysdeps/unix/sysv/linux/sem_post.c
index 67e8cc5..27ddd6e 100644
--- a/nptl/sysdeps/unix/sysv/linux/sem_post.c
+++ b/nptl/sysdeps/unix/sysv/linux/sem_post.c
@@ -30,6 +30,13 @@ __new_sem_post (sem_t *sem)
 {
   struct new_sem *isem = (struct new_sem *) sem;
 
+  /* Use a CAS loop to increment the semaphore's value.  We need release
+     memory order (MO) on the CAS so that it synchronizes with the other CAS
+     used by threads waiting on the semaphore (which has acquire MO); this
+     ensures that everything we did before posting the semaphore happens
+     before the waiters can continue.  We do not need additional acquire MO
+     here because we do not need additional happens-before guarantees based
+     on other threads' writes to the semaphore's value.  */
   __typeof (isem->value) cur;
   do
     {
@@ -42,6 +49,11 @@ __new_sem_post (sem_t *sem)
     }
   while (atomic_compare_and_exchange_bool_rel (&isem->value, cur + 1, cur));
 
+  /* This seq_cst fence is necessary for the Dekker-style synchronization used
+     here.  This fence and the respective fence in__new_sem_wait() are totally
+     ordered, which in turn prevents cyclic reads-from/sequenced-before
+     dependencies between the store/load pairs;  here, this pair is the prior
+     write to value by the CAS and the following read of nwaiters.  */
   atomic_full_barrier ();
   if (isem->nwaiters > 0)
     {
diff --git a/nptl/sysdeps/unix/sysv/linux/sem_timedwait.c b/nptl/sysdeps/unix/sysv/linux/sem_timedwait.c
index 36e0042..f703483 100644
--- a/nptl/sysdeps/unix/sysv/linux/sem_timedwait.c
+++ b/nptl/sysdeps/unix/sysv/linux/sem_timedwait.c
@@ -51,6 +51,7 @@ sem_timedwait (sem_t *sem, const struct timespec *abstime)
   struct new_sem *isem = (struct new_sem *) sem;
   int err;
 
+  /* See __new_sem_wait() for comments.  */
   if (atomic_decrement_if_positive (&isem->value) > 0)
     return 0;
 
diff --git a/nptl/sysdeps/unix/sysv/linux/sem_trywait.c b/nptl/sysdeps/unix/sysv/linux/sem_trywait.c
index 517ae44..c1a523f 100644
--- a/nptl/sysdeps/unix/sysv/linux/sem_trywait.c
+++ b/nptl/sysdeps/unix/sysv/linux/sem_trywait.c
@@ -34,6 +34,7 @@ __new_sem_trywait (sem_t *sem)
 
   if (*futex > 0)
     {
+      /* See __new_sem_wait() for comments.  */
       val = atomic_decrement_if_positive (futex);
       if (val > 0)
 	return 0;
diff --git a/nptl/sysdeps/unix/sysv/linux/sem_wait.c b/nptl/sysdeps/unix/sysv/linux/sem_wait.c
index ca50f4e..2274b70 100644
--- a/nptl/sysdeps/unix/sysv/linux/sem_wait.c
+++ b/nptl/sysdeps/unix/sysv/linux/sem_wait.c
@@ -57,9 +57,17 @@ __new_sem_wait (sem_t *sem)
   struct new_sem *isem = (struct new_sem *) sem;
   int err;
 
+  /* This decrement operation has acquire memory order so that everything
+     that happens before the posting of the semaphore happens before the code
+     that we return execution to.  */
   if (atomic_decrement_if_positive (&isem->value) > 0)
     return 0;
 
+  /* This increment to nwaiters is part of the Dekker-style synchronization
+     we use here (see __new_sem_post).  The seq_cst fence and the read of
+     isem->value are part of the futex_wait().  Incrementing nwaiters once
+     is sufficient because only waiting threads decrease nwaiters, and only
+     once.  */
   atomic_increment (&isem->nwaiters);
 
   pthread_cleanup_push (__sem_wait_cleanup, isem);