Groups > comp.programming.threads > #670

Re: Locking primitives in userspace

Path	csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail
From	Alexander Terekhov <terekhov@web.de>
Newsgroups	comp.programming.threads
Subject	Re: Locking primitives in userspace
Date	Tue, 08 Nov 2011 08:30:10 +0100
Organization	A noiseless patient Spider
Lines	63
Message-ID	<4EB8DA82.120E5D8D@web.de> (permalink)
References	<ihU8Kn.Ndh.Tp3Zo@invalid.invalid>
Reply-To	terekhov@web.de
Mime-Version	1.0
Content-Type	text/plain; charset=us-ascii
Content-Transfer-Encoding	7bit
Injection-Info	mx04.eternal-september.org; posting-host="MCbSEzW5qwGLFMNXJh39IQ"; logging-data="13777"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+Q7dmPv9j9QlpdXnRsyjSbnzC4lzbwARA="
X-Mailer	Mozilla 4.77 [en] (Windows NT 5.0; U)
X-Accept-Language	en
Cancel-Lock	sha1:XILNUS3S1xeDIK10sV2O/E0tkFE=
Xref	x330-a1.tempe.blueboxinc.net comp.programming.threads:670

Show key headers only | View raw

Steve Thompson wrote:
> 
> I've been writing some multi-threaded code and have some question
> about userspace locking primitives and best practices.
> 
> Firstly, I've written my own locking primitives, possibly for no other
> reason than to be familiar with the low-level details.  I've read
> Ulrich Drepper's paper[0] on "fast userspace mutexes", which discusses
> the kernel futex facility and considered the pthread_mutex_* calls
> which one might use.  There are also POSIX semaphores.

Linux's futex interface isn't really optimal for mutexes and condvars 
because the kernel doesn't maintain 'waiters bit' (e.g. 0x80000000) 
indicating that there are queued waiters. 

With waiters bit, mutex would be simply 

  WHILE atomic_bit_test_set_hlb(&lock, 1) // efficient 'acquire' 
    lock_queue_wait(&lock, 1) // wait if locked bit is set 

for lock() and 

   uintptr_t lock_queue; 
   IF atomic_decrement_rel(lock_queue = &lock) 
     THEN lock_queue_wake(lock_queue, 1) 

for unlock (lock_queue uintptr_t pointer may become indeterminate 
by the time of lock_queue_wake() and implementation should handle 
it (spurious wakes are okay)).

Similarly, for semaphore:

sema_lock:

  WHILE !atomic_decrement_if_binand_7FFFFFFF_is_not_zero_rel_hlb(&lock) 
    lock_queue_wait(&lock, 0) // wait if sema value is zero

sema_unlock:

  uintptr_t lock_queue
  IF atomic_increment_rel_hlb(lock_queue = &lock) > 0x80000000
    THEN lock_queue_wake(lock_queue, 1)

(Semaphores need stronger memory barriers because they can be used as
atomic flags/counters with lock() signalling something and unlock()
consuming the signal.)

For condvar, it is better to let the kernel set waiters bit and then
unlock the associated mutex. 

The signal would be simply 

   IF cv_queue 
     THEN cv_queue_wake(&cv_queue, 1) 

and broadcast 

   IF cv_queue 
     THEN cv_queue_wake(&cv_queue, UINT_MAX) 

regards, 
alexander.

Back to comp.programming.threads | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Locking primitives in userspace Steve Thompson <thomps2048@yahoo.ca> - 2011-10-30 16:26 -0400
  Re: Locking primitives in userspace Steve Thompson <thomps2048@yahoo.ca> - 2011-11-06 06:54 -0500
    Re: Locking primitives in userspace Mark <i@dontgetlotsofspamanymore.invalid> - 2011-11-07 11:42 +0000
      Re: Locking primitives in userspace Steve Thompson <thomps2048@yahoo.ca> - 2011-11-10 09:42 -0500
  Re: Locking primitives in userspace Alexander Terekhov <terekhov@web.de> - 2011-11-08 08:30 +0100

csiph-web