Mutexes

[Neal H. Walfield]

Here is my proposal for implementing mutexes without a manager thread.

When a thread blocks on a mutex, it adds itself to a list of threads
waiting for the mutex and enters a closed wait on itself:

        struct mutex_waiter
        {
          struct mutex_waiter *next;
          l4_thread_id_t tid;
        };
        
        void    
        mutex_lock (mutex)
        {
          spin_lock (&mutex->self_lock);
          if (mutex->locked)
            /* Add ourself to the mutex's wait queue.  */
            {
              struct mutex_waiter mutex_waiter
                = { mutex->waiters, l4_my_local_id () };
              mutex->waiters = &mutex_waiter;
              spin_unlock (&mutex->self_lock);

              l4_receive (l4_my_local_id ());
            }
          else
            /* Got it!  */
            {
              mutex->locked = l4_my_local_id ();
              spin_unlock (&mutex->self_lock);
            }
        }

When the thread holding the mutex releases it, it needs to wake up the
a waiter.  It chooses a waiter, then using propagation, sends it a
message appearing to be from itself.

        void
        mutex_unlock (mutex)
        {
          spin_lock (&mutex->self_lock);
        
          if (mutex->waiters)
            /* Someone is waiting for the mutex.  */
            {
               struct mutex_waiter mutex_waiter = mutex->waiters;
               l4_msg_tag_t tag;
        
               mutex->waiters = mutex->waiters->next;
               mutex->locked = mutex_waiter->tid;
        
               spin_unlock (&mutex->self_lock);

               do
                 {
                   l4_set_propagation (&tag);
                   l4_load_mr (0, tag);
                   l4_set_virtual_sender (mutex_waiter->tid);
                   tag = l4_call (mutex_waiter->tid);
                 }
               while (l4_ipc_failed (tag) && l4_error_code () == 3);

               assert (l4_ipc_succeeded (tag);
             }
           else
             /* No one is waiting for the mutex.  */
             {
               mutex->lock = l4_nil_thread;
               spin_unlock (&mutex->self_lock);
             }
        }

The above algorithm is a bit unfair as waiters are woken in a LIFO
order but should be illustrative.  Also, the code may be able to be
rewritten to use atomic operations.


This code is problematic if a thread is interrupted.  For instance, if
a POSIX signal is delivered, the tread shouldn't block all waiters on
the mutex while the handler is running.  But more importantly, if the
thread does a longjmp out of the signal thread or if the thread is
cancelled, the thread must remove itself from the wait queue.

One way to do this would use a pair of callbacks with a bit of TLS
magic:

        struct wind
        {
          (strut wind *) (*callback) (void *cookie);
          void *cookie;
        };

        thread struct wind unwind;
        thread struct wind rewind;

Unwind is used to exit wait queues, etc.  Rewind to reenter them.
When the signal thread wishes to deliver a signal, it does an exregs
on the thread in question aborting any ipcs and saving the current
context.  Before running the handler, however, the thread does:

        struct wind *wind = unwind;

        while (unwind)
          unwind = unwind->callback (unwind->cookie);
        
In the case of unwinding a mutex, this will remove the thread from the
mutex's list of waiters.  There is a race here, however: if the thread
is not on the list another thread is trying to signal it that it now
owns the mutex.  It must acknowledge this and then release the mutex.
Finally, it needs to add itself to the rewind chain and run the next
unwind function.  Here is an rough implementation:

        struct mutex_wind_cookie
        {
          struct mutex *mutex;
          struct mutex_waiter *me_waiting;
          struct wind wind;
        };

        void
        mutex_unwind (void *cookie)
        {
          struct mutex_wind_cookie *wind_cookie = cookie;
          struct mutex *mutex = wind_cookie->mutex;
          struct wind *winder;

          struct mutex_waiter **prevp, *waiter;

          spin_lock (&mutex->self_lock);
          if (mutex->lock == l4_my_local_id ())
            /* We own the lock.  That means that someone is trying to
               wake us up.  We need to acknowledge the message and
               then pass the lock on.  */
            {
              spin_unlock (&mutex->self_lock);
              l4_receive (l4_my_local_id ());
              mutex_unlock (mutex);
            }
          else
            {
              for (prevp = &mutex->waiters, waiter = mutex->waiters; waiter;
                   prevp = &waiter->next, waiter = waiter->next)
                if (waiter->tid == l4_my_local_id ())
                  {
                    assert (waiter == cookie->me_waiting);
                    *prevp = waiter->next
                    break;
                  }

               spin_unlock (&mutex->self_lock);

               assert (waiter);
            }

          /* Cache the next callback on the unwind chain.  */
          winder = wind_cookie->wind;

          /* Save the head of the rewind chain.  */
          wind_cookie->wind = rewind;
          /* Add ourselves to the rewind chain.  */
          rewind.callback = mutex_rewind;
          rewind.cookie = wind_cookie;

          /* Return the next unwind function.  */
          return winder;
        }

        void
        mutex_rewind (void *cookie)
        {
          struct mutex_wind_cookie *wind_cookie = cookie;
          struct mutex *mutex = wind_cookie->mutex;
          struct wind *winder;

          spin_lock (&mutex->self_lock);
          assert (cookie->me_waiting->tid == l4_my_local_tid ());
          cookie->me_waiting->next = mutex->waiters;
          mutex->waiters = cookie->me_waiting;

          /* Cache the next callback on the rewind chain.  */
          winder = wind_cookie->wind;

          /* mutex_lock better be blocked waiting for a thread to
             reply.  Thus, there can be no one after us.  */

          assert (! wind_cookie->wind.handler);

          /* Add ourselves to the unwind chain.  */
          unwind.callback = mutex_unwind;
          unwind.cookie = wind_cookie;

          spin_unlock (&mutex->self_lock);

          /* Once we return, the caller of the rewind chain will do an
             exregs and restore the state before the signal.  We'll be
             back in the context of mutex_lock, the ipc will return
             and the error tcb will indicate that the ipc was
             interrupted.  The code will loop and resume waiting for a
             wake up message.  */

          return winder;
        }

As can be seen from above call backs are added to the head of the
lists so that they are called in a LIFO order.  Since rewind callbacks
are added in the unwind callbacks, the rewind callbacks are called in
the reverse order with respect to the unwind callbacks but in the same
order that the resources were acquired.



This is just a rough outline of what I have in mind.  I think the
first part is pretty solid (that is, eliding the manager thread and
using propagation to signal sleeping threads).  I haven't thought
about all of the issues as they relate to signal handling and looking
at the code in glibc for the Mach port, I am sure I am missing a few
details.  Hence, I include the wind code less as a "here is what we
should do" and more as a request for comments and a starting point of
discussion.

Thanks,
Neal