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>
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


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.