This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


On Fri, Dec 06, 2013 at 11:18:21PM +0100, OndÅej BÃlka wrote:
> 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. 

LL/SC works with a single addressed word. I don't see any way you can
magically construct a double-world CAS out of it, but maybe I'm
missing something?

In any case why not just use an implementation that works equally well
with just 32-bit CAS?

Rich


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]