Re: [RFC 2/2][BZ #12674] Make semaphores race-free.

[OndÅej BÃlka <neleai at seznam dot cz>]

On Fri, Dec 06, 2013 at 03:35:23PM -0500, Rich Felker wrote:
> On Fri, Dec 06, 2013 at 01:24:02PM +0100, OndÅej BÃlka wrote:
> > Now we look how fix race condition in semaphores. Earlier thread allows
> > us focus on idea without needlessly going into assembly.
> > 
> > If we look to semaphore layout it is
> > 
> > /* Semaphore variable structure.  */
> > struct new_sem
> > {
> >   unsigned int value;
> >   int private;
> >   unsigned long int nwaiters;
> > };
> > 
> > struct old_sem
> > {
> >   unsigned int value;
> > };
> > 
> > A new_sem is 12 or 16 bytes whether you are on 64-bit system. On x64
> > that is enough as you can update structure atomically by cmpxchg16b.
> > 
> > However our data structure is bit wasteful. Do we really need 64bit
> > nwaiters?
> 
> 64-bit nwaiters is useless because waiters each have a kernel-level
> pid (tid) whose type is int, putting an upper bound on the number that
> can exist.
> 
> > Field private consists of single bit. We could squash that to nwaiters
> > which should be ok until somebody can make machine that could handle 
> > 1000000000 threads.
> 
> Not a problem. The upper few bits of kernel tids are not available for
> use anyway due to the robust mutex API.
> 
> > With this change we fit into 8 bytes which is enough for hardware
> > compare-and-swap on most architectures that matter.
> 
> I don't think so. 8-byte CAS is rare except on 64-bit systems. Many
> ARM systems don't even have any CAS (they use the kernel helper) and
> MIPS32 doesn't have it.
>
These have LL/SC that could be used. As arms are concerned its available
since arm6. 
 
> In any case there's no reason to need CAS on the whole struct. CAS on
> just one field suffices to meet all the requirements including
> self-synchronized destruction; you just have to be a little bit
> clever.
> 
> Rich