This is the mail archive of the 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: [PATCH 3/3] Update to new generic semaphore algorithm.


I'm aware I'm still discussing the futex API patches with Roland, but
this patch here is the core of this patch set and just needs *some* way
to do futex syscalls.  (IOW, whatever the outcome of the futex API
patch, this patch will not be significantly affected.)

On Fri, 2014-12-05 at 20:24 +0100, Torvald Riegel wrote:
> This changes the generic C implementation of semaphores to use different
> algorithms.  The core issue of the old implementation was that it kept
> two fields for both the value of the semaphore (ie, how many tokens it
> has that can be acquired by sem_wait calls) and the number of threads
> waiting to acquire a token using a futex_wait.  We want to track the
> latter to be able to avoid calling futex_wake if there is actually no
> waiter.  We can't put both of these counters into one 32b field because
> of the number of threads and or tokens we need to support.
> When users try to use sem_wait in the way discussed in
> then one thread calls
> sem_post, and another calls sem_wait *and* expects that once it has the
> token (ie, sem_wait has returned), it can call sem_destroy.
> Therefore, the implementation needs to ensure that sem_post makes no
> access to the semaphore data structure after it has provided a token.
> If we have 64b atomic operations, we can atomically increment the value
> of the semaphore and load the field counting the number of waiters.
> If we just have 32b operations, we need to do something more involved.
> The key here is to track a conservative value for the number of waiters
> in one bit of the value, and use that.  Because it's a conservative
> value, it may be wrong and we may call futex_wake unnecessarily under
> some conditions.  When we reset this bit (ie, speculate that there are
> no other waiters), we can be wrong but can make this misspeculation
> harmless if we wake as many waiters as there are tokens available.  We
> do all these latter steps in sem_wait to still satisfy the requirement
> for sem_post regarding not accessing the semaphore after providing a
> token.
> Detailed comments can be found in the patch itself; see nptl/sem_wait.c.
> The semaphore data structure is adapted accordingly, as are other
> related functions: sem_open, sem_init, sem_getvalue, sem_trywait,
> sem_timedwait.
> because sem_trywait and sem_timedwait are very small, it seemed best to
> simply put them all into sem_wait.c
> I removed nptl/DESIGN-sem.txt because it was outdated and the comments
> in the code provide much more detail.
> The changes to tst-sem11 and tst-sem13 are simple adaptions; they peek
> inside the semaphore data structure.
> The custom assembler implementations on x86, x86_64, and sh have been
> removed.
> alpha and powerpc had custom sem_post implementations, but all that
> those were lacking compared to the generic version was a write barrier
> in sem_post.  The new algorithm is correctly synchronized; for the old
> version of sem_post, I have added a call to atomic_write_barrier
> directly.  This allows us to remove the custom alpha and powerpc
> variants.
> sparc still has its own semaphore implementation.  I'd like to get
> feedback from sparc maintainers regarding what should happen with it.
> Note that this patch set is on top of the patch providing a new internal
> futex API:
> Tested on x86 and x86_64.  I have not tested the old versions
> (__old_sem*) yet.
> 	[BZ #12674]
> 	* nptl/sem_wait.c(__new_sem_wait_fast): New function.  Implement
> 	new semaphore algorithms.
> 	(__new_sem_wait_slow): New function.
> 	(__sem_wait_32_finish): New function.
> 	(__sem_wait_cleanup): Adapt.
> 	(do_futex_wait_inner): Adapt.
> 	(do_futex_wait): Adapt.
> 	(__new_sem_wait): Adapt.
> 	(sem_timedwait): New function.
> 	(__new_sem_trywait): New function.
> 	(__old_sem_trywait): Moved here from nptl/sem_trywait.c.
> 	* nptl/sem_post.c (__new_sem_post): Adapt.
> 	(__old_sem_post): Add release fence.
> 	* nptl/sem_open.c (sem_open): Adapt.
> 	* nptl/sem_init.c (__new_sem_init): Adapt.
> 	* nptl/sem_getvalue.c (__new_sem_getvalue): Adapt.
> 	(__old_sem_getvalue): Add using previous code.
> 	* sysdeps/nptl/internaltypes.h: Adapt.
> 	* nptl/tst-sem13.c (do_test): Adapt.
> 	* nptl/tst-sem11.c (main): Adapt.
> 	* nptl/sem_timedwait.c: Remove.
> 	* nptl/sem_trywait.c: Remove.
> 	* nptl/DESIGN-sem.txt: Remove.
> 	* nptl/Makefile (libpthread-routines): Remove sem_trywait, sem_wait.
> 	(gen-as-const-headers): Remove structsem.sym.
> 	* nptl/structsem.sym: Remove.
> 	* sysdeps/unix/sysv/linux/alpha/sem_post.c: Remove.
> 	* sysdeps/unix/sysv/linux/i386/i486/sem_post.S: Remove.
> 	* sysdeps/unix/sysv/linux/i386/i486/sem_timedwait.S: Remove.
> 	* sysdeps/unix/sysv/linux/i386/i486/sem_trywait.S: Remove.
> 	* sysdeps/unix/sysv/linux/i386/i486/sem_wait.S: Remove.
> 	* sysdeps/unix/sysv/linux/i386/i586/sem_post.S: Remove.
> 	* sysdeps/unix/sysv/linux/i386/i586/sem_timedwait.S: Remove.
> 	* sysdeps/unix/sysv/linux/i386/i586/sem_trywait.S: Remove.
> 	* sysdeps/unix/sysv/linux/i386/i586/sem_wait.S: Remove.
> 	* sysdeps/unix/sysv/linux/i386/i686/sem_post.S: Remove.
> 	* sysdeps/unix/sysv/linux/i386/i686/sem_timedwait.S: Remove.
> 	* sysdeps/unix/sysv/linux/i386/i686/sem_trywait.S: Remove.
> 	* sysdeps/unix/sysv/linux/i386/i686/sem_wait.S: Remove.
> 	* sysdeps/unix/sysv/linux/powerpc/sem_post.c: Remove.
> 	* sysdeps/unix/sysv/linux/sh/sem_post.S: Remove.
> 	* sysdeps/unix/sysv/linux/sh/sem_timedwait.S: Remove.
> 	* sysdeps/unix/sysv/linux/sh/sem_trywait.S: Remove.
> 	* sysdeps/unix/sysv/linux/sh/sem_wait.S: Remove.
> 	* sysdeps/unix/sysv/linux/x86_64/sem_post.S: Remove.
> 	* sysdeps/unix/sysv/linux/x86_64/sem_timedwait.S: Remove.
> 	* sysdeps/unix/sysv/linux/x86_64/sem_trywait.S: Remove.
> 	* sysdeps/unix/sysv/linux/x86_64/sem_wait.S: Remove.

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