Re: Mutexes

[Marcus Brinkmann]

Hi,

this looks pretty good to me, but I think that our level of
understanding the signal code is roughly at the same level, so I have
to make the same reservations as you.

At Thu, 17 Feb 2005 23:12:15 +0000,
Neal H. Walfield wrote:
> Here is my proposal for implementing mutexes without a manager thread.

I think the unwind stuff is pretty much necessary irregardless of how
you do the communication.  It's good to do it without a manager,
though.

Maybe it is useful to relate this mutex design with how RPCs and
signals interact, as there are certain similarities and differences.
If a thread doing an RPC is receiving a signal, the RPC will be
canceled by sending a message to the server, which then cancels the
worker thread, leading to a quick reply (which can either be success
or EINTR).  Only when this reply is fully received the signal is
actually delivered and the signal handler invoked.  This is necessary
as opposed to the local mutex implementation, we can not bail out of
the ipc early - we could miss the server reply that way.

I think there are also unwind handlers to clean up RPC related
resources in case of a longjmp etc.  The userlink code in glibc
suggests that.  I don't fully understand that yet, but the
similarities are striking as the differences are important.

I hope we can get the number of different types of states an
interrupted thread can be in down to a small number.  Currently, this
would be: executing normal code, executing code in a critical section
(glibc internal), being in an RPC operation, or blocking on a mutex.
That's the cases I can think of.  If the user wants to use low level
primitives like ipc() in his code, he better blocks signals and
cancellation or deals with them appropriately!

Just one comment about the code:

>                  tag = l4_call (mutex_waiter->tid);

This should be a sent operation only (there is no reply, and we really
only want to wake up the waiter, not run it right now if we still have
cpu time - imagine we are a high priority thread).

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

Yes.  This is something that I don't know much about - it depends on
your policy.  BTW, I suggest Drepper's paper on futexes (and/or nptl?)
for a list of options and their advantages/disadvantages.

But that's fine tuning, I think.  Also depends on your needs, I suppose.

Another issue that's for later is how all this interacts with
scheduler priorities.

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

Note that unwind stuff etc is already something that's needed in other
places in glibc and our implementation, so we will have low level
support for such handlers.  This should make it simpler.

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

Of course, it could also just keep the mutex and later on continue
normally.  That is not different from first getting the mutex, and
then the signal.  Doing it like you said can be better, because other
threads get a chance to make progress first while this thread runs the
signal handler.  But on the other hand, it also has a marginal risk of
starvation (if many signals arrive).  A very clever implementation may
give up the mutex N times and then just keep it.  But my gut feeling
is that just keeping it always will be just fine.  Both seem to be
better than always giving up the mutex (again, because the potential
risk of starvation).

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

Yes.  I think both parts are pretty solid.  Of course the
implementation details will be according to glibc's internal
interfaces, and may be fine-tuned for more fair behaviour etc.

I really wonder how you start to write such code though.  It seems not
to be easy to implement this incrementally.  I guess a good way to
start would be to check that the setjmp/longjmp code and the unwind
handlers work, and then adding an exception/signal handler thread.
The signal thread in hurd on mach uses spin locks, so a good deal of
it should be implementable even without mutexes.

I always thought that implementing a low level locks would be a good
place to start (then starting to get threads to work, and then signal
management).  But now I start to think that first getting the basics
of signals/interruption/unwinding etc to work may actually be the more
sensical approach.

Thanks,
Marcus