Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #661 > unrolled thread

Locking primitives in userspace

Back to article view | Back to comp.programming.threads

Contents

  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

#661 — Locking primitives in userspace

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.

Obviously, I would normally prefer to avoid context switching as much as
possible, and it seems that doing it with hand-written code is the way
to go with that constraint in mind.  Mind you, I'm still in the early
stage of figuring out how I will organize threaded applications, so
nothing is fixed in stone.

My code uses an atomic inc instruction to increment a 32 bit quantity
and checks to see whether the value is what is expected.  If the value
is greater than one, the code knows there is contention and backs off
for a short delay before trying again.  I've dubbed this thing a
semaphore, although it is nothing like a POSIX semaphore.  On top of
this primitive, I have written 'read' and 'write' lock methods.  Write
locks are completely exclusive while read locks exclude only writers,
however the read-lock methods are biased to defer to waiting writers.

This seems to satisfy my general requirements, and it should be fast
because I can control how many times a waiting process will spin on the
semaphore primitive, and the duration that the thread might
nanosleep() if the lock is tied up for a long time by another
process.  Note I've said "process" instead of thread since these locks
ought to work to synchronize both inter-thread and inter-process data
if instantiated in a shared memory segment.  Of course, I don't get
any help from the scheduler this way, and at some point I guess I'll
have data on just how much this matters to an application.

I am interested in comments on this scheme and invite any criticisms
regarding portability or performance that might arise by my avoidance
of operating system-provided locking primitives.

Another issue floating around in the back of my mind concerns hardware
cache-line synchronization in multi-core systems.  My understanding is
that (at least on x86), the 'lock' prefix causes the processor to
share the relevant cache line with all processors in the system in
some way.  I'm not clear on how this works, but I assume there is some
magic that causes memory access delay only in circumstances where two
cores are holding the same cache line because a lock is contended
between threads.

Further reading suggests this is even more critical on NUMA
architectures.  So, if I have a bunch of locks spread throughout an
application, should they be scattered through memory, or might it be
better to manage them as an array of cache-line sized objects?

My experience with x86 assembler is very limited, and the other
systems I've used prior were all much smaller.  Worse, I'm writing my
threaded code 'on spec' from available documentation and anticipate
difficulty proving the correctness of my design.  Any tips on how to
best go about verifying that everything works as intended?  Debugging
threaded applications looks as though it could be very difficult.


[0] http://people.redhat.com/drepper/futex.pdf




Steve Thompson

[toc] | [next] | [standalone]

#667

On Sun, Oct 30, 2011 at 04:26:05PM -0400, 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.
> 
> Obviously, I would normally prefer to avoid context switching as much as
> possible, and it seems that doing it with hand-written code is the way
> to go with that constraint in mind.  Mind you, I'm still in the early
> stage of figuring out how I will organize threaded applications, so
> nothing is fixed in stone.
> 
> My code uses an atomic inc instruction to increment a 32 bit quantity
> and checks to see whether the value is what is expected.  If the value
> is greater than one, the code knows there is contention and backs off
> for a short delay before trying again.  I've dubbed this thing a
> semaphore, although it is nothing like a POSIX semaphore.  On top of
> this primitive, I have written 'read' and 'write' lock methods.  Write
> locks are completely exclusive while read locks exclude only writers,
> however the read-lock methods are biased to defer to waiting writers.
> 
> This seems to satisfy my general requirements, and it should be fast
> because I can control how many times a waiting process will spin on the
> semaphore primitive, and the duration that the thread might
> nanosleep() if the lock is tied up for a long time by another
> process.  Note I've said "process" instead of thread since these locks
> ought to work to synchronize both inter-thread and inter-process data
> if instantiated in a shared memory segment.  Of course, I don't get
> any help from the scheduler this way, and at some point I guess I'll
> have data on just how much this matters to an application.
> 
> I am interested in comments on this scheme and invite any criticisms
> regarding portability or performance that might arise by my avoidance
> of operating system-provided locking primitives.
> 
> Another issue floating around in the back of my mind concerns hardware
> cache-line synchronization in multi-core systems.  My understanding is
> that (at least on x86), the 'lock' prefix causes the processor to
> share the relevant cache line with all processors in the system in
> some way.  I'm not clear on how this works, but I assume there is some
> magic that causes memory access delay only in circumstances where two
> cores are holding the same cache line because a lock is contended
> between threads.
> 
> Further reading suggests this is even more critical on NUMA
> architectures.  So, if I have a bunch of locks spread throughout an
> application, should they be scattered through memory, or might it be
> better to manage them as an array of cache-line sized objects?
> 
> My experience with x86 assembler is very limited, and the other
> systems I've used prior were all much smaller.  Worse, I'm writing my
> threaded code 'on spec' from available documentation and anticipate
> difficulty proving the correctness of my design.  Any tips on how to
> best go about verifying that everything works as intended?  Debugging
> threaded applications looks as though it could be very difficult.
> 
> 
> [0] http://people.redhat.com/drepper/futex.pdf
> 

No comments?  The implementation has interesting properties that I was
looking forward to discussing, as well as any remarks concerning
scalability or interactions with the scheduler.




Steve Thompson

[toc] | [prev] | [next] | [standalone]

#669

On Sun, 06 Nov 2011 06:54:37 -0500, Steve Thompson
<thomps2048@yahoo.ca> wrote:

>On Sun, Oct 30, 2011 at 04:26:05PM -0400, 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.
>> 
>> Obviously, I would normally prefer to avoid context switching as much as
>> possible, and it seems that doing it with hand-written code is the way
>> to go with that constraint in mind.  Mind you, I'm still in the early
>> stage of figuring out how I will organize threaded applications, so
>> nothing is fixed in stone.
>> 
>> My code uses an atomic inc instruction to increment a 32 bit quantity
>> and checks to see whether the value is what is expected.  If the value
>> is greater than one, the code knows there is contention and backs off
>> for a short delay before trying again.  I've dubbed this thing a
>> semaphore, although it is nothing like a POSIX semaphore.  On top of
>> this primitive, I have written 'read' and 'write' lock methods.  Write
>> locks are completely exclusive while read locks exclude only writers,
>> however the read-lock methods are biased to defer to waiting writers.
>> 
>> This seems to satisfy my general requirements, and it should be fast
>> because I can control how many times a waiting process will spin on the
>> semaphore primitive, and the duration that the thread might
>> nanosleep() if the lock is tied up for a long time by another
>> process.  Note I've said "process" instead of thread since these locks
>> ought to work to synchronize both inter-thread and inter-process data
>> if instantiated in a shared memory segment.  Of course, I don't get
>> any help from the scheduler this way, and at some point I guess I'll
>> have data on just how much this matters to an application.
>> 
>> I am interested in comments on this scheme and invite any criticisms
>> regarding portability or performance that might arise by my avoidance
>> of operating system-provided locking primitives.
>> 
>> Another issue floating around in the back of my mind concerns hardware
>> cache-line synchronization in multi-core systems.  My understanding is
>> that (at least on x86), the 'lock' prefix causes the processor to
>> share the relevant cache line with all processors in the system in
>> some way.  I'm not clear on how this works, but I assume there is some
>> magic that causes memory access delay only in circumstances where two
>> cores are holding the same cache line because a lock is contended
>> between threads.
>> 
>> Further reading suggests this is even more critical on NUMA
>> architectures.  So, if I have a bunch of locks spread throughout an
>> application, should they be scattered through memory, or might it be
>> better to manage them as an array of cache-line sized objects?
>> 
>> My experience with x86 assembler is very limited, and the other
>> systems I've used prior were all much smaller.  Worse, I'm writing my
>> threaded code 'on spec' from available documentation and anticipate
>> difficulty proving the correctness of my design.  Any tips on how to
>> best go about verifying that everything works as intended?  Debugging
>> threaded applications looks as though it could be very difficult.
>> 
>> 
>> [0] http://people.redhat.com/drepper/futex.pdf
>> 
>
>No comments?  The implementation has interesting properties that I was
>looking forward to discussing, as well as any remarks concerning
>scalability or interactions with the scheduler.

Since no-one else has replied then I'll chip in.  I'm not an academic
so am not really interested in examining obscure locking mechanisms.
However I would avoid such features and would stick to POSIX thread
features since my code has to be portable.

Sorry I can't offer any real help ;-)
-- 
(\__/)  M.
(='.'=) Due to the amount of spam posted via googlegroups and
(")_(") their inaction to the problem. I am blocking some articles
posted from there.  If you wish your postings to be seen by
everyone you will need use a different method of posting.

[toc] | [prev] | [next] | [standalone]

#673

On Mon, Nov 07, 2011 at 11:42:22AM +0000, Mark wrote:
> On Sun, 06 Nov 2011 06:54:37 -0500, Steve Thompson
> <thomps2048@yahoo.ca> wrote:
> 
> >On Sun, Oct 30, 2011 at 04:26:05PM -0400, Steve Thompson wrote:
> >> I've been writing some multi-threaded code and have some question
> >> about userspace locking primitives and best practices.
[snip]

> Since no-one else has replied then I'll chip in.  I'm not an academic
> so am not really interested in examining obscure locking mechanisms.
> However I would avoid such features and would stick to POSIX thread
> features since my code has to be portable.

I wouldn't say it is obscure, perhaps novel but no matter.  I haven't
examined the Linux kernel arch-specific code they use mostly because
(a) it looks like macro-spaghetti, and (b) I've wanted to maintain a
'clean' development environment unpolluted by licence-restricted code.
So far I can say that I've not reverse-engineered anything noteworthy,
which ought to make my life easier down the road.  Any IP collisions
will be accidental or will arise subsequent to my design.

As to portability, I have separated architecture-specific code from the
program text to make porting trivial.  I expect more problems as a
consequence of using c99 features or GNUisms, or elsewhere due to
differences in system call semantics.  For your portability
requirements you are relying on the system library writers to do the
architecture-specific code for you, which is admittedly less work.  My
approach allows me to design the algorithm to my requirements rather
than to the system library requirements.

To be more concrete, at program startup, my code chooses a variant
dependent upon the number of VCPUs present, meaning that there is no
hard spinning in uniprocessor environments.  You'll have to verify
that your system libraries do the right thing for your target
platform, if that is a concern in your development environment.

> Sorry I can't offer any real help ;-)

S'ok.





Steve Thompson

[toc] | [prev] | [next] | [standalone]

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web