2008-01-22 Neal H. Walfield <neal@gnu.org>

	* mutex.h [RM_INTERN]: Raise an error.
	[! __hurd_mutex_have_type]: Only define ss_mutex_t in this case.
	Define __hurd_mutex_have_type.  Change ss_mutex_t to an int.
	[__need_ss_mutex_t]: Undefine __need_ss_mutex_t.  Don't make the
	rest of the file available.
	[! __need_ss_mutex_t]: Include <hurd/futex.h>.
	(_MUTEX_UNLOCKED): New define.
	(_MUTEX_LOCKED): Likewise.
	(_MUTEX_WAITERS): Likewise.
	(ss_mutex_lock): Implement in terms of futexes.
	(ss_mutex_unlock): Likewise.
	(ss_mutex_trylock): Likewise.

	* lock.h (SS_RMUTEX_LOCK): Define.
	(SS_RMUTEX_LOCK_INC): Likewise.
	(SS_RMUTEX_LOCK_WAIT): Likewise.
	(SS_RMUTEX_UNLOCK): Likewise.
	(SS_RMUTEX_UNLOCK_DEC): Likewise.
	(SS_RMUTEX_TRYLOCK): Likewise.
	(SS_RMUTEX_TRYLOCK_INC): Likewise.
	(SS_RMUTEX_TRYLOCK_BLOCKED): Likewise.
	(ss_lock_trace_dump): Handle the above new cases.
	* rmutex.h: New file.
	* Makefile.am (includehurd_HEADERS): Add rmutex.h.
	* headers.m4: Link $(BUILDIR)/include/hurd/rmutex.h to rmutex.h.

6 files changed, 337 insertions, 48 deletions

diff --git a/hurd/ChangeLog b/hurd/ChangeLog
index ed1e1ba..40a0a9f 100644
--- a/hurd/ChangeLog
+++ b/hurd/ChangeLog
@@ -1,3 +1,31 @@
+2008-01-22  Neal H. Walfield  <neal@gnu.org>
+
+	* mutex.h [RM_INTERN]: Raise an error.
+	[! __hurd_mutex_have_type]: Only define ss_mutex_t in this case.
+	Define __hurd_mutex_have_type.  Change ss_mutex_t to an int.
+	[__need_ss_mutex_t]: Undefine __need_ss_mutex_t.  Don't make the
+	rest of the file available.
+	[! __need_ss_mutex_t]: Include <hurd/futex.h>.
+	(_MUTEX_UNLOCKED): New define.
+	(_MUTEX_LOCKED): Likewise.
+	(_MUTEX_WAITERS): Likewise.
+	(ss_mutex_lock): Implement in terms of futexes.
+	(ss_mutex_unlock): Likewise.
+	(ss_mutex_trylock): Likewise.
+
+	* lock.h (SS_RMUTEX_LOCK): Define.
+	(SS_RMUTEX_LOCK_INC): Likewise.
+	(SS_RMUTEX_LOCK_WAIT): Likewise.
+	(SS_RMUTEX_UNLOCK): Likewise.
+	(SS_RMUTEX_UNLOCK_DEC): Likewise.
+	(SS_RMUTEX_TRYLOCK): Likewise.
+	(SS_RMUTEX_TRYLOCK_INC): Likewise.
+	(SS_RMUTEX_TRYLOCK_BLOCKED): Likewise.
+	(ss_lock_trace_dump): Handle the above new cases.
+	* rmutex.h: New file.
+	* Makefile.am (includehurd_HEADERS): Add rmutex.h.
+	* headers.m4: Link $(BUILDIR)/include/hurd/rmutex.h to rmutex.h.
+
 2008-01-17  Neal H. Walfield  <neal@gnu.org>
 
 	* rpc.h (rpc_error_reply_marshal): New function.
diff --git a/hurd/Makefile.am b/hurd/Makefile.am
index c060c6d..10ceb1c 100644
--- a/hurd/Makefile.am
+++ b/hurd/Makefile.am
@@ -23,7 +23,7 @@ COMMON_CPPFLAGS = -I$(srcdir) -I$(top_builddir)/include \
 includehurddir = $(includedir)/hurd
 includehurd_HEADERS = rpc.h startup.h stddef.h types.h addr.h \
 	addr-trans.h cap.h folio.h exceptions.h thread.h activity.h \
-	lock.h mutex.h futex.h
+	lock.h mutex.h rmutex.h futex.h
 
 TESTS = t-addr t-addr-trans t-rpc
 check_PROGRAMS = $(TESTS)
diff --git a/hurd/headers.m4 b/hurd/headers.m4
index 732a187..836de66 100644
--- a/hurd/headers.m4
+++ b/hurd/headers.m4
@@ -23,5 +23,6 @@ AC_CONFIG_LINKS([include/hurd/stddef.h:hurd/stddef.h
 		 include/hurd/activity.h:hurd/activity.h
 		 include/hurd/lock.h:hurd/lock.h
 		 include/hurd/mutex.h:hurd/mutex.h
+		 include/hurd/rmutex.h:hurd/rmutex.h
 		 include/hurd/futex.h:hurd/futex.h
 		])
diff --git a/hurd/lock.h b/hurd/lock.h
index e167652..644f5c1 100644
--- a/hurd/lock.h
+++ b/hurd/lock.h
@@ -31,21 +31,33 @@
 
 struct ss_lock_trace
 {
-  __const char *caller;
-  int line;
+  const char *caller;
+  unsigned int line : 28;
+  unsigned int func : 4;
   void *lock;
-  int func;
   l4_thread_id_t tid;
 };
 #define SS_LOCK_TRACE_COUNT 1000
 extern struct ss_lock_trace ss_lock_trace[SS_LOCK_TRACE_COUNT];
 extern int ss_lock_trace_count;
 
-#define SS_MUTEX_LOCK 1
-#define SS_MUTEX_LOCK_WAIT 2
-#define SS_MUTEX_UNLOCK 3
-#define SS_MUTEX_TRYLOCK 4
-#define SS_MUTEX_TRYLOCK_BLOCKED 5
+enum
+  {
+    SS_MUTEX_LOCK,
+    SS_MUTEX_LOCK_WAIT,
+    SS_MUTEX_UNLOCK,
+    SS_MUTEX_TRYLOCK,
+    SS_MUTEX_TRYLOCK_BLOCKED,
+
+    SS_RMUTEX_LOCK,
+    SS_RMUTEX_LOCK_INC,
+    SS_RMUTEX_LOCK_WAIT,
+    SS_RMUTEX_UNLOCK,
+    SS_RMUTEX_UNLOCK_DEC,
+    SS_RMUTEX_TRYLOCK,
+    SS_RMUTEX_TRYLOCK_INC,
+    SS_RMUTEX_TRYLOCK_BLOCKED,
+  };
 
 #endif /* NDEBUG */
 
@@ -84,6 +96,31 @@ ss_lock_trace_dump (void *lock)
 	case SS_MUTEX_TRYLOCK_BLOCKED:
 	  func = "trylock(blocked)";
 	  break;
+
+	case SS_RMUTEX_LOCK:
+	  func = "ss_rmutex_lock";
+	  break;
+	case SS_RMUTEX_LOCK_INC:
+	  func = "ss_rmutex_lock_inc";
+	  break;
+	case SS_RMUTEX_LOCK_WAIT:
+	  func = "ss_rmutex_lock_wait";
+	  break;
+	case SS_RMUTEX_UNLOCK:
+	  func = "ss_rmutex_unlock";
+	  break;
+	case SS_RMUTEX_UNLOCK_DEC:
+	  func = "ss_rmutex_unlock_dec";
+	  break;
+	case SS_RMUTEX_TRYLOCK:
+	  func = "ss_rmutex_trylock";
+	  break;
+	case SS_RMUTEX_TRYLOCK_INC:
+	  func = "ss_rmutex_trylock_inc";
+	  break;
+	case SS_RMUTEX_TRYLOCK_BLOCKED:
+	  func = "ss_rmutex_trylock_blocked";
+	  break;
 	}
       assert (func);
 
diff --git a/hurd/mutex.h b/hurd/mutex.h
index ce41e01..3e21eee 100644
--- a/hurd/mutex.h
+++ b/hurd/mutex.h
@@ -18,6 +18,21 @@
    License along with GNU Hurd.  If not, see
    <http://www.gnu.org/licenses/>.  */
 
+#ifdef RM_INTERN
+# error "This implementation is not appropriate for the kernel."
+#endif
+
+#ifndef __hurd_mutex_have_type
+#define __hurd_mutex_have_type
+typedef int ss_mutex_t;
+#endif
+
+/* If __need_ss_mutex_t is defined, then we only export the type
+   definition.  */
+#ifdef __need_ss_mutex_t
+# undef __need_ss_mutex_t
+#else
+
 #ifndef _HURD_MUTEX_H
 #define _HURD_MUTEX_H
 
@@ -25,31 +40,40 @@
 #include <atomic.h>
 #include <assert.h>
 #include <hurd/lock.h>
+#include <hurd/futex.h>
+
+/* Unlocked.  */
+#define _MUTEX_UNLOCKED 0
+/* There the lock is locked.  */
+#define _MUTEX_LOCKED 1
+/* There there are waiters.  */
+#define _MUTEX_WAITERS 2
 
-typedef l4_thread_id_t ss_mutex_t;
 
 static inline void
-ss_mutex_lock (__const char *caller, int line, ss_mutex_t *lock)
+ss_mutex_lock (__const char *caller, int line, ss_mutex_t *lockp)
 {
-  l4_thread_id_t owner;
-
-  for (;;)
+  int c;
+  c = atomic_compare_and_exchange_val_acq (lockp, _MUTEX_LOCKED,
+					   _MUTEX_UNLOCKED);
+  if (c != _MUTEX_UNLOCKED)
+    /* Someone else owns the lock.  */
     {
-      owner = atomic_exchange_acq (lock, l4_myself ());
-      if (owner == l4_nilthread)
-	{
-	  ss_mutex_trace_add (SS_MUTEX_LOCK, caller, line, lock);
-	  return;
-	}
-  
-      ss_mutex_trace_add (SS_MUTEX_LOCK_WAIT, caller, line, lock);
+      ss_mutex_trace_add (SS_MUTEX_LOCK_WAIT, caller, line, lockp);
 
-      if (owner == l4_myself ())
-	ss_lock_trace_dump (lock);
-      assert (owner != l4_myself ());
+      if (c != _MUTEX_WAITERS)
+	/* Note that there are waiters.  */
+	c = atomic_exchange_acq (lockp, _MUTEX_WAITERS);
 
-      __ss_lock_wait (owner);
+      /* Try to sleep but only if LOCKP is _MUTEX_WAITERS.  */
+      while (c != _MUTEX_UNLOCKED)
+	{
+	  futex_wait (lockp, _MUTEX_WAITERS);
+	  c = atomic_exchange_acq (lockp, _MUTEX_WAITERS);
+	}
     }
+
+  ss_mutex_trace_add (SS_MUTEX_LOCK, caller, line, lockp);
 }
 
 #define ss_mutex_lock(__sml_lockp)					\
@@ -61,22 +85,19 @@ ss_mutex_lock (__const char *caller, int line, ss_mutex_t *lock)
   while (0)
 
 static inline void
-ss_mutex_unlock (__const char *caller, int line, ss_mutex_t *lock)
+ss_mutex_unlock (__const char *caller, int line, ss_mutex_t *lockp)
 {
-  l4_thread_id_t waiter;
-
-  waiter = atomic_exchange_acq (lock, l4_nilthread);
-  ss_mutex_trace_add (SS_MUTEX_UNLOCK, caller, line, lock);
-  if (waiter == l4_myself ())
-    /* No waiter.  */
-    return;
-
-  if (waiter == l4_nilthread)
-    ss_lock_trace_dump (lock);
-  assert (waiter != l4_nilthread);
+  /* We rely on the knowledge that unlocked is 0, locked and no
+     waiters is 1 and locked with waiters is 2.  Thus if *lockp is 1,
+     an atomic dec yields 0 and we know that there are no waiters.  */
+  if (! atomic_decrement_and_test (lockp))
+    /* There are waiters.  */
+    {
+      *lockp = 0;
+      futex_wake (lockp, 1);
+    }
 
-  /* Signal the waiter.  */
-  __ss_lock_wakeup (waiter);
+  ss_mutex_trace_add (SS_MUTEX_UNLOCK, caller, line, lockp);
 }
 
 #define ss_mutex_unlock(__smu_lockp)					\
@@ -88,19 +109,19 @@ ss_mutex_unlock (__const char *caller, int line, ss_mutex_t *lock)
   while (0)
 
 static inline bool
-ss_mutex_trylock (__const char *caller, int line, ss_mutex_t *lock)
+ss_mutex_trylock (__const char *caller, int line, ss_mutex_t *lockp)
 {
-  l4_thread_id_t owner;
-
-  owner = atomic_compare_and_exchange_val_acq (lock, l4_myself (),
-					       l4_nilthread);
-  if (owner == l4_nilthread)
+  int c;
+  c = atomic_compare_and_exchange_val_acq (lockp, _MUTEX_LOCKED,
+					   _MUTEX_UNLOCKED);
+  if (c == _MUTEX_UNLOCKED)
+    /* Got the lock.  */
     {
-      ss_mutex_trace_add (SS_MUTEX_TRYLOCK, caller, line, lock);
+      ss_mutex_trace_add (SS_MUTEX_TRYLOCK, caller, line, lockp);
       return true;
     }
 
-  ss_mutex_trace_add (SS_MUTEX_TRYLOCK_BLOCKED, caller, line, lock);
+  // ss_mutex_trace_add (SS_MUTEX_TRYLOCK_BLOCKED, caller, line, lockp);
 
   return false;
 }
@@ -114,3 +135,6 @@ ss_mutex_trylock (__const char *caller, int line, ss_mutex_t *lock)
   })
 
 #endif
+
+#endif /* __need_ss_mutex_t */
+
diff --git a/hurd/rmutex.h b/hurd/rmutex.h
new file mode 100644
index 0000000..d0e50e3
--- /dev/null
+++ b/hurd/rmutex.h
@@ -0,0 +1,199 @@
+/* rmutex.c - Small, simple LIFO recursive mutex implementation.
+   Copyright (C) 2008 Free Software Foundation, Inc.
+   Written by Neal H. Walfield <neal@gnu.org>.
+
+   This file is part of the GNU Hurd.
+
+   GNU Hurd is free software: you can redistribute it and/or modify it
+   under the terms of the GNU Lesser General Public License as
+   published by the Free Software Foundation, either version 3 of the
+   License, or (at your option) any later version.
+
+   GNU Hurd is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with GNU Hurd.  If not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#ifndef __hurd_rmutex_have_type
+#define __hurd_rmutex_have_type
+
+/* For ss_mutex_t.  */
+#define __need_ss_mutex_t
+#include <hurd/mutex.h>
+/* For l4_thread_id_t.  */
+#include <l4/thread.h>
+
+struct ss_rmutex
+{
+  ss_mutex_t lock;
+  int count;
+  l4_thread_id_t owner;
+};
+typedef struct ss_rmutex ss_rmutex_t;
+
+#endif /* !__hurd_rmutex_have_type */
+
+/* If __need_ss_rmutex_t is defined, then we only export the type
+   definition.  */
+#ifdef __need_ss_rmutex_t
+# undef __need_ss_rmutex_t
+#else
+
+#ifndef _HURD_RMUTEX_H
+#define _HURD_RMUTEX_H
+
+#define SS_RMUTEX_INIT { 0, 0, l4_nilthread }
+
+static inline void
+ss_rmutex_lock (const char *caller, int line, ss_rmutex_t *lock)
+{
+  while (1)
+    {
+      __lock_acquire (&lockp->lock);
+
+      if (lockp->owner == l4_myself ())
+	{
+	  assert (lockp->count != 0);
+
+	  ss_mutex_trace_add (SS_RMUTEX_LOCK_INC, caller, line, lock);
+
+	  if (lockp->count > 0)
+	    lockp->count ++;
+	  else
+	    /* Negative means there may be waiters.  */
+	    lockp->count --;
+
+	  __lock_release (&lockp->lock);
+	  return;
+	}
+
+      if (lockp->owner == l4_nilthread)
+	{
+	  assert (lockp->count == 0);
+
+	  ss_mutex_trace_add (SS_RMUTEX_LOCK, caller, line, lock);
+
+	  lockp->count = 1;
+	  lockp->owner = l4_myself ();
+	  __lock_release (&lockp->lock);
+	  return;
+	}
+
+      assert (lockp->count != 0);
+
+      if (lockp->count > 0)
+	/* Note that there are waiters.  */
+	lockp->count = -lockp->count;
+
+      __lock_release (&lockp->lock);
+
+      ss_mutex_trace_add (SS_RMUTEX_LOCK, caller, line, lock);
+      futex_wait (&lockp->count, lockp->count);
+    }
+}
+
+#define ss_rmutex_lock(__srl_lockp)					\
+  do									\
+    {									\
+      debug (5, "ss_rmutex_lock (%p)", __srl_lockp);			\
+      ss_rmutex_lock (__func__, __LINE__, __srl_lockp);			\
+    }									\
+  while (0)
+
+static inline void
+ss_rmutex_unlock (const char *caller, int line, ss_rmutex_t *lock)
+{
+  __lock_acquire (&lockp->lock);
+
+  assert (lockp->owner == l4_myself ());
+  assert (lockp->count != 0);
+
+  int waiters = lockp->count < 0;
+  if (lockp->count > 0)
+    lockp->count --;
+  else
+    lockp->count ++;
+
+  if (lockp->count == 0)
+    ss_mutex_trace_add (SS_RMUTEX_UNLOCK, caller, line, lock);
+  else
+    ss_mutex_trace_add (SS_RMUTEX_UNLOCK_DEC, caller, line, lock);
+
+  lockp->owner = l4_nilthread;
+
+  __lock_release (&lockp->lock);
+
+  if (waiters)
+    futex_wake (&lockp->count, 1);
+}
+
+#define ss_rmutex_unlock(__sru_lockp)					\
+  do									\
+    {									\
+      debug (5, "ss_rmutex_unlock (%p)", __sru_lockp);			\
+      ss_rmutex_unlock (__func__, __LINE__, __sru_lockp);		\
+    }									\
+  while (0)
+
+static inline bool
+ss_rmutex_trylock (const char *caller, int line, ss_rmutex_t *lock)
+{
+  /* If someone holds the meta-lock then the lock is either held or
+     about to be held.  */
+  if (__lock_try_acquire (&lockp->lock) == 1)
+    /* Busy.  */
+    {
+      ss_mutex_trace_add (SS_RMUTEX_TRYLOCK_BLOCKED, caller, line, lock);
+
+      return false;
+    }
+
+  if (lockp->owner == l4_myself ())
+    {
+      assert (lockp->count != 0);
+
+      ss_mutex_trace_add (SS_RMUTEX_TRYLOCK_INC, caller, line, lock);
+
+      if (lockp->count > 0)
+	lockp->count ++;
+      else
+	/* Negative means there may be waiters.  */
+	lockp->count --;
+
+      __lock_release (&lockp->lock);
+      return true;
+    }
+
+  if (lockp->owner == l4_nilthread)
+    {
+      ss_mutex_trace_add (SS_RMUTEX_TRYLOCK, caller, line, lock);
+
+      assert (lockp->count == 0);
+      lockp->count = 1;
+      lockp->owner = l4_myself ();
+      __lock_release (&lockp->lock);
+      return true;
+    }
+
+  assert (lockp->count != 0);
+
+  ss_mutex_trace_add (SS_RMUTEX_TRYLOCK_BLOCKED, caller, line, lock);
+
+  return false;
+}
+
+#define ss_rmutex_trylock(__srl_lockp)					\
+  ({									\
+    bool __srl_r = ss_rmutex_trylock (__func__, __LINE__, __srl_lockp);	\
+    debug (5, "ss_rmutex_trylock (%p) -> %s",				\
+	   __srl_lockp, __srl_r ? "t" : "f");				\
+    __srl_r;								\
+  })
+
+#endif
+
+#endif /* __need_ss_rmutex_t */