This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [RFC 2/2][BZ #12674] Make semaphores race-free.
- From: Rich Felker <dalias at aerifal dot cx>
- To: OndÅej BÃlka <neleai at seznam dot cz>
- Cc: libc-alpha at sourceware dot org
- Date: Fri, 6 Dec 2013 17:33:32 -0500
- Subject: Re: [RFC 2/2][BZ #12674] Make semaphores race-free.
- Authentication-results: sourceware.org; auth=none
- References: <20131206103626 dot GA20423 at domone dot podge> <20131206122402 dot GA19973 at domone dot podge> <20131206203523 dot GF24286 at brightrain dot aerifal dot cx> <20131206221821 dot GB25502 at domone dot podge>
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