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 05:33:32PM -0500, Rich Felker wrote:
> 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?
>
No, I understood that claim as that arm does not even have word cas. 


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