Re: futex for Mach?

1) futex certainly is a sensible facility, and I have no objection to
   providing it.  Roland is right that we don't break L4 migration by
   building pthreads on it; the requirement is pthreads, not any
   particular pthreads implementation.  However, futex will become a
   standard thing that people can depend on, and we should expect that
   just like spin locks, the fact that it isn't in pthreads doesn't
   mean we don't have to worry about migration.  So L4 pthreads need
   not use futex, but if we add futex here, we will have to make sure
   we can do it in L4 too.  Still, I don't think this is any serious
   obstacle.

2) Implementing it as a syscall is bad.  One way to see why is to
   think about network transparency, but basically, the point is that
   everyone sharing the page should be sharing the futex, and it is
   the memory manager and not the kernel that knows who all the
   sharers are.

So I think the following is a superior implementation than the syscall
approach; it comprises four parts.  Be sure to read through to the
fourth part, because that will be crucial.

Part I
------

User interface for futex should be through a vm_* message sent to the
task, just like all other memory-related manipulations.

Part II
-------

The kernel, just like for all memory-related manipulations, is a
conduit; in principle the real work is done by the pager.  So we would
have memory_object_lock_futex (or whatever), and this would need to be
added to the XP protocol, together with suitable reply messages.

At this point we could stop.  The implementation would be slow, but
reliable.  The following to steps implement an important optimization.

Part III
--------

A page is always either owned by the kernel or the memory manager.
vm_lock_futex (or whatever) will always page in the page first, so the
kernel is always trying to lock a futex in a page that the kernel
owns.

So the first time someone locks a futex, the kernel needs to do a
memory_object_lock_futex, and interface with the pager.  But after
that, the kernel can just *retain* the lock, as far as the pager is
concerned.  The user unlocks, but the kernel still holds the lock in
the XP context.  The next user wants to lock, and no exchange with the
pager is necessary.  

That provides the crucial performance so that this is all no worse
than a syscall.  It would truly suck if we had to do RPC on every
lock.  (And doing this without a kernel facility, as Roland notes,
would be major hair and very expensive in time-cost.)

This is all really very similar to the way that page protections work
already. 

Part IV
-------

If the kernel has the lock locked, and some other user out there wants
to acquire the lock (that is, some *other* kernel [or kernel-like
entity] communicating with the same pager) then the pager needs a way
to force the kernel to relinquish.

So the XP interface needs a pager->kernel call like
memory_object_relinquish_futex; the kernel will either relinquish the
lock immediately (if no real user is holding it), or will relinquish
it as soon as the real user does, rather than handing it off to
another local user.

Parts III and IV make the kernel not just a conduit for lock
manipulations, but a *cache*, just like for other pager things.

Thomas