Re: Mutexes on L4Ka::Pistachio?

Hi Farid,

On 07/19/2010 11:32 AM, Farid Hajji wrote:
>> You're right, pistachio doesn't offer a kernel-supported
>> mutex/locking scheme at the moment.
> 
> I guess it's not strictly needed. However, a little help from the
> kernel could be useful to improve efficiency (s. below).

For running our Genode OS Framework on Pistachio, we had to solve the
thread-synchronization issue, too. Maybe, our experience can be of help
for you. Our lock implementation looks as follows:

Interface:

http://genode.svn.sourceforge.net/viewvc/genode/trunk/base/include/base/cancelable_lock.h?revision=112&view=markup

Implementation (platform-independent and Pistachio-specific):

http://genode.svn.sourceforge.net/viewvc/genode/trunk/base/src/base/lock/lock.cc?revision=112&view=markup
http://genode.svn.sourceforge.net/viewvc/genode/trunk/base-pistachio/src/base/lock/lock_helper.h?revision=97&view=markup

In short, each lock has a list of threads applying for the lock (we call
such a thread Applicant). When a thread applies for the lock, it checks
if the lock is currently owned by another thread. If not, it sets itself
as new lock owner. If the lock currently owned by another thread, the
applying threads adds itself to the lock's list of applicants and puts
itself to halt (using Pistachio's L4_Stop variant of the exregs
syscall). Once the current lock owner frees the lock, it wakes up the
next thread found in the lock's applicants list.

There are three advantages of this solution. There is no need for a
central server because threads wake up each other in a peer-to-peer
fashion (using a central server would immediately raise
resource-accounting problems about lock metadata). Second, entering an
uncontended lock does not involve any syscall, which is good for
performance. Third, in contrast to a spinlock, threads block on a
contended lock, freeing the CPU time for executing other threads.

If you decide to take this idea as blueprint for your implementation,
two technical details are worth noting:

* The list of lock applicants must by synchronized, which somehow
  leads to a chicken-egg problem. Contention in this code path is
  extremely rare but it must be considered. We use a yielding spinlock
  for this purpose. If you intend to synchronize threads with different
  priorities, this spinlock could turn out as a problem.

* The check of a new lock applicant about the lock ownership and the
  subsequent call of 'L4_Stop' are not atomic. Hence, a thread can put
  itself to sleep after the lock owner releases the lock w/o waking
  up the new applicant. For this reason, the wakeup mechanism makes
  use of Pistachio's subtle exregs feature, which returns the previous
  thread state. Only if the previous thread state during a wakeup
  was blocked, the wakeup is detected as effective. If this is not
  the case, the owner helps the to-be-blocked-and-then-waken-up
  thread to enter L4_Stop by calling 'L4_ThreadSwitch' and performs
  the wakeup again.

>> Sounds sensible. But I'm also sure OKL4 has a reason to offer a
>> kernel primitive. My guess is that it is because kernel notifications
>> are convenient and can be better integrated into the scheduler and/or
>> other kernel subsystems. But I personally have never looked into the
>> details, so it might make sense to ask the OKL4 developers directly.
> 
> Perhaps OKL4 provides a kernel primitive for efficiency reasons,
> but it's not strictly needed?

We have looked closely at OKL4's kernel mutexes (OKL4 version 2.1) but
found them of little use, for the following reasons: They can only be
used by roottask. They consume kernel resources. They work only for
protecting critical sections - the caller of unlock must be the same as
the caller of lock. Consequently on OKL4, we use the same lock as
described above but with a different 'lock_helper.h'.

Best regards
Norman

-- 
Dr.-Ing. Norman Feske
Genode Labs

http://www.genode-labs.com · http://genode.org

Genode Labs GmbH · Amtsgericht Dresden · HRB 28424 · Sitz Dresden
Geschäftsführer: Dr.-Ing. Norman Feske, Christian Helmuth