recursive locks

[Thomas Bushnell, BSG]

You want something like:

struct recursive_lock
{
  spin_lock_t guard;
  int count;
  thread_t owner;
  mutex_t lock;
};

"guard" protects "count" and "owner", and it looks like this:

lock:
  spin_lock (guard)

  if (not owned)
    assert (count == 0)
    owner = me
    mutex_lock (lock)

  if (owner == me)
    increment count
    spin_unlock (guard)
  else
    spin_unlock (guard)
    mutex_lock (lock)
    spin_lock (guard)
    assert (not owned && count == 0)
    owner = me
    increment count


unlock
  spin_lock (guard)
  assert (owner = me && count > 0)
  decrement count
  if (count == 0)
    owner = not owned
    mutex_unlock (lock)
  spin_unlock (guard)


Now if you look closely at this, you'll see that we don't really need
the mutex LOCK at all.  It is only being used to provide a way for the
waiters to block (that is, when we call it, we always know for sure
whether we will succeed or not).  We should use a condition variable
instead.  In fact, we should.  Condition variables have to be
protected by a mutex though, so we would convert LOCK into a condition
at the cost of converting GUARD into a mutex.  Now we have:

struct recursive_lock
{
  struct mutex guard;
  int count;
  thread_t owner;
  condition_t wakeup;
};

lock:
  mutex_lock (guard)
  do
    if (not owned)
      assert (count = 0)
      owner = me
    if (owner == me)
      increment count
      GOT IT
    else
      condition_wait (wakeup, guard)
  while (not GOT IT)

unlock:
  mutex_lock (guard)
  assert (owner == me && count > 0)
  decrement count
  if (count == 0)
    owner = not owned
    condition_signal (wakeup)
  mutex_unlock (guard)


If this is too expensive, then you should implement your own queue,
and do something like:

struct recursive_lock
{
  spin_lock_t held;
  spin_lock_t guard;
  int count;
  thread_t owner
  struct cthread_queue queue;
};

See __mutex_lock_solid and __mutex_unlock_solid in libthread/cprocs.c
for the guts of how to manipulate QUEUE.

Thomas