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

[Rich Felker <dalias at aerifal dot cx>]

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.

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