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: OndÅej BÃlka <neleai at seznam dot cz>
- To: Rich Felker <dalias at aerifal dot cx>
- Cc: libc-alpha at sourceware dot org
- Date: Fri, 6 Dec 2013 23:50:40 +0100
- 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> <20131206223332 dot GJ24286 at brightrain dot aerifal dot cx>
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.