Rework mutex implementation selection

10 files changed, 280 insertions, 178 deletions

diff --git a/kern/atomic.h b/kern/atomic.h
index 75b07012..63f0ac73 100644
--- a/kern/atomic.h
+++ b/kern/atomic.h
@@ -116,6 +116,9 @@ MACRO_END
  * Common shortcuts.
  */
 
+#define atomic_load_acquire(ptr) atomic_load(ptr, ATOMIC_ACQUIRE)
+#define atomic_store_release(ptr, val) atomic_store(ptr, val, ATOMIC_RELEASE)
+
 #define atomic_cas_acquire(ptr, oval, nval) \
     atomic_cas(ptr, oval, nval, ATOMIC_ACQUIRE)
 
@@ -129,9 +132,6 @@ MACRO_END
 #define atomic_swap_release(ptr, val)   atomic_swap(ptr, val, ATOMIC_RELEASE)
 #define atomic_swap_acq_rel(ptr, val)   atomic_swap(ptr, val, ATOMIC_ACQ_REL)
 
-#define atomic_fetch_add_acq_rel(ptr, val) \
-    atomic_fetch_add(ptr, val, ATOMIC_ACQ_REL)
-
 #define atomic_fetch_sub_acq_rel(ptr, val) \
     atomic_fetch_sub(ptr, val, ATOMIC_ACQ_REL)
 
diff --git a/kern/mutex.h b/kern/mutex.h
index 1100b77d..e599e8a2 100644
--- a/kern/mutex.h
+++ b/kern/mutex.h
@@ -18,75 +18,31 @@
  * Mutual exclusion sleep locks.
  *
  * Unlike spin locks, acquiring a mutex may make the calling thread sleep.
- *
- * TODO Adaptive spinning.
  */
 
 #ifndef _KERN_MUTEX_H
 #define _KERN_MUTEX_H
 
-#include <kern/mutex_types.h>
-
-#ifdef X15_MUTEX_PI
-
-#include <kern/rtmutex.h>
-
-struct mutex;
-
-#define mutex_assert_locked(mutex) rtmutex_assert_locked(&(mutex)->rtmutex)
-
-static inline void
-mutex_init(struct mutex *mutex)
-{
-    rtmutex_init(&mutex->rtmutex);
-}
-
-static inline int
-mutex_trylock(struct mutex *mutex)
-{
-    return rtmutex_trylock(&mutex->rtmutex);
-}
-
-static inline void
-mutex_lock(struct mutex *mutex)
-{
-    rtmutex_lock(&mutex->rtmutex);
-}
-
-static inline void
-mutex_unlock(struct mutex *mutex)
-{
-    rtmutex_unlock(&mutex->rtmutex);
+#if defined(X15_MUTEX_PI)
+#include <kern/mutex/mutex_pi_i.h>
+#else
+#include <kern/mutex/mutex_plain_i.h>
+#endif
 
-    /*
-     * If this mutex was used along with a condition variable, wake up
-     * a potential pending waiter. This must be done after the mutex is
-     * unlocked so that a higher priority thread can directly acquire it.
-     */
-    thread_wakeup_last_cond();
-}
-
-#else /* X15_MUTEX_PI */
-
-#include <kern/assert.h>
-#include <kern/error.h>
-#include <kern/macros.h>
-#include <kern/mutex_i.h>
+#include <kern/mutex_types.h>
 #include <kern/thread.h>
 
-struct mutex;
-
-#define mutex_assert_locked(mutex) assert((mutex)->state != MUTEX_UNLOCKED)
-
 /*
  * Initialize a mutex.
  */
 static inline void
 mutex_init(struct mutex *mutex)
 {
-    mutex->state = MUTEX_UNLOCKED;
+    mutex_impl_init(mutex);
 }
 
+#define mutex_assert_locked(mutex) mutex_impl_assert_locked(mutex)
+
 /*
  * Attempt to lock the given mutex.
  *
@@ -97,37 +53,20 @@ mutex_init(struct mutex *mutex)
 static inline int
 mutex_trylock(struct mutex *mutex)
 {
-    unsigned int state;
-
-    state = mutex_lock_fast(mutex);
-
-    if (unlikely(state != MUTEX_UNLOCKED)) {
-        assert((state == MUTEX_LOCKED) || (state == MUTEX_CONTENDED));
-        return ERROR_BUSY;
-    }
-
-    return 0;
+    return mutex_impl_trylock(mutex);
 }
 
 /*
  * Lock a mutex.
  *
- * If the mutex is already locked, the calling thread sleeps until the
- * mutex is unlocked.
+ * On return, the mutex is locked. A mutex can only be locked once.
  *
- * A mutex can only be locked once.
+ * This function may sleep.
  */
 static inline void
 mutex_lock(struct mutex *mutex)
 {
-    unsigned int state;
-
-    state = mutex_lock_fast(mutex);
-
-    if (unlikely(state != MUTEX_UNLOCKED)) {
-        assert((state == MUTEX_LOCKED) || (state == MUTEX_CONTENDED));
-        mutex_lock_slow(mutex);
-    }
+    mutex_impl_lock(mutex);
 }
 
 /*
@@ -139,14 +78,7 @@ mutex_lock(struct mutex *mutex)
 static inline void
 mutex_unlock(struct mutex *mutex)
 {
-    unsigned int state;
-
-    state = mutex_unlock_fast(mutex);
-
-    if (unlikely(state != MUTEX_LOCKED)) {
-        assert(state == MUTEX_CONTENDED);
-        mutex_unlock_slow(mutex);
-    }
+    mutex_impl_unlock(mutex);
 
     /*
      * If this mutex was used along with a condition variable, wake up
@@ -155,6 +87,4 @@ mutex_unlock(struct mutex *mutex)
     thread_wakeup_last_cond();
 }
 
-#endif /* X15_MUTEX_PI */
-
 #endif /* _KERN_MUTEX_H */
diff --git a/kern/mutex/mutex_pi_i.h b/kern/mutex/mutex_pi_i.h
new file mode 100644
index 00000000..6c39db74
--- /dev/null
+++ b/kern/mutex/mutex_pi_i.h
@@ -0,0 +1,60 @@
+/*
+ * Copyright (c) 2017 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _KERN_MUTEX_PI_I_H
+#define _KERN_MUTEX_PI_I_H
+
+#ifndef _KERN_MUTEX_H
+#error "don't include <kern/mutex/mutex_pi_i.h> directly," \
+       " use <kern/mutex.h> instead"
+#endif
+
+#include <kern/mutex_types.h>
+#include <kern/rtmutex.h>
+
+/*
+ * Interface exported to the public mutex header.
+ */
+
+static inline void
+mutex_impl_init(struct mutex *mutex)
+{
+    rtmutex_init(&mutex->rtmutex);
+}
+
+#define mutex_impl_assert_locked(mutex) \
+    rtmutex_assert_locked(&(mutex)->rtmutex)
+
+static inline int
+mutex_impl_trylock(struct mutex *mutex)
+{
+    return rtmutex_trylock(&mutex->rtmutex);
+}
+
+static inline void
+mutex_impl_lock(struct mutex *mutex)
+{
+    rtmutex_lock(&mutex->rtmutex);
+}
+
+static inline void
+mutex_impl_unlock(struct mutex *mutex)
+{
+    rtmutex_unlock(&mutex->rtmutex);
+}
+
+#endif /* _KERN_MUTEX_PI_I_H */
diff --git a/kern/mutex/mutex_pi_types.h b/kern/mutex/mutex_pi_types.h
new file mode 100644
index 00000000..d9ebb6e2
--- /dev/null
+++ b/kern/mutex/mutex_pi_types.h
@@ -0,0 +1,39 @@
+/*
+ * Copyright (c) 2017 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ * Isolated type definition used to avoid inclusion circular dependencies.
+ */
+
+#ifndef _KERN_MUTEX_PI_TYPES_H
+#define _KERN_MUTEX_PI_TYPES_H
+
+#ifndef _KERN_MUTEX_TYPES_H
+#error "don't include <kern/mutex/mutex_pi_types.h> directly," \
+       " use <kern/mutex_types.h> instead"
+#endif
+
+#include <kern/rtmutex_types.h>
+
+/*
+ * Do not directly alias rtmutex to make sure they cannot be used
+ * with condition variables by mistake.
+ */
+struct mutex {
+    struct rtmutex rtmutex;
+};
+
+#endif /* _KERN_MUTEX_PI_TYPES_H */
diff --git a/kern/mutex.c b/kern/mutex/mutex_plain.c
index 7899bef9..a925a5a2 100644
--- a/kern/mutex.c
+++ b/kern/mutex/mutex_plain.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2013-2017 Richard Braun.
+ * Copyright (c) 2017 Richard Braun.
  *
  * This program is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -15,26 +15,25 @@
  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-#ifndef X15_MUTEX_PI
-
 #include <stdbool.h>
 #include <stddef.h>
 
+#include <kern/atomic.h>
 #include <kern/mutex.h>
-#include <kern/mutex_i.h>
+#include <kern/mutex_types.h>
 #include <kern/sleepq.h>
 
 void
-mutex_lock_slow(struct mutex *mutex)
+mutex_plain_lock_slow(struct mutex *mutex)
 {
+    unsigned int state;
     struct sleepq *sleepq;
     unsigned long flags;
-    unsigned int state;
 
     sleepq = sleepq_lend(mutex, false, &flags);
 
     for (;;) {
-        state = atomic_swap_acquire(&mutex->state, MUTEX_CONTENDED);
+        state = atomic_swap_release(&mutex->state, MUTEX_CONTENDED);
 
         if (state == MUTEX_UNLOCKED) {
             break;
@@ -44,28 +43,23 @@ mutex_lock_slow(struct mutex *mutex)
     }
 
     if (sleepq_empty(sleepq)) {
-        state = atomic_swap_acquire(&mutex->state, MUTEX_LOCKED);
-        assert(state == MUTEX_CONTENDED);
+        /* TODO Review memory order */
+        atomic_store(&mutex->state, MUTEX_LOCKED, ATOMIC_RELEASE);
     }
 
     sleepq_return(sleepq, flags);
 }
 
 void
-mutex_unlock_slow(struct mutex *mutex)
+mutex_plain_unlock_slow(struct mutex *mutex)
 {
     struct sleepq *sleepq;
     unsigned long flags;
 
     sleepq = sleepq_acquire(mutex, false, &flags);
 
-    if (sleepq == NULL) {
-        return;
+    if (sleepq != NULL) {
+        sleepq_signal(sleepq);
+        sleepq_release(sleepq, flags);
     }
-
-    sleepq_signal(sleepq);
-
-    sleepq_release(sleepq, flags);
 }
-
-#endif /* X15_MUTEX_PI */
diff --git a/kern/mutex/mutex_plain_i.h b/kern/mutex/mutex_plain_i.h
new file mode 100644
index 00000000..9e41ff27
--- /dev/null
+++ b/kern/mutex/mutex_plain_i.h
@@ -0,0 +1,112 @@
+/*
+ * Copyright (c) 2017 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _KERN_MUTEX_PLAIN_I_H
+#define _KERN_MUTEX_PLAIN_I_H
+
+#ifndef _KERN_MUTEX_H
+#error "don't include <kern/mutex/mutex_plain_i.h> directly," \
+       " use <kern/mutex.h> instead"
+#endif
+
+#include <kern/assert.h>
+#include <kern/atomic.h>
+#include <kern/error.h>
+#include <kern/mutex_types.h>
+
+#define MUTEX_UNLOCKED  0
+#define MUTEX_LOCKED    1
+#define MUTEX_CONTENDED 2
+
+static inline void
+mutex_plain_init(struct mutex *mutex)
+{
+    mutex->state = MUTEX_UNLOCKED;
+}
+
+#define mutex_plain_assert_locked(mutex) \
+    assert((mutex)->state != MUTEX_UNLOCKED)
+
+static inline int
+mutex_plain_lock_fast(struct mutex *mutex)
+{
+    unsigned int state;
+
+    state = atomic_cas_acquire(&mutex->state, MUTEX_UNLOCKED, MUTEX_LOCKED);
+
+    if (unlikely(state != MUTEX_UNLOCKED)) {
+        return ERROR_BUSY;
+    }
+
+    return 0;
+}
+
+static inline int
+mutex_plain_unlock_fast(struct mutex *mutex)
+{
+    unsigned int state;
+
+    state = atomic_swap_release(&mutex->state, MUTEX_UNLOCKED);
+
+    if (unlikely(state == MUTEX_CONTENDED)) {
+        return ERROR_BUSY;
+    }
+
+    return 0;
+}
+
+void mutex_plain_lock_slow(struct mutex *mutex);
+void mutex_plain_unlock_slow(struct mutex *mutex);
+
+/*
+ * Interface exported to the public mutex header.
+ */
+
+#define mutex_impl_init             mutex_plain_init
+#define mutex_impl_assert_locked    mutex_plain_assert_locked
+
+static inline int
+mutex_impl_trylock(struct mutex *mutex)
+{
+    return mutex_plain_lock_fast(mutex);
+}
+
+static inline void
+mutex_impl_lock(struct mutex *mutex)
+{
+    int error;
+
+    error = mutex_plain_lock_fast(mutex);
+
+    if (unlikely(error)) {
+        mutex_plain_lock_slow(mutex);
+    }
+}
+
+static inline void
+mutex_impl_unlock(struct mutex *mutex)
+{
+    int error;
+
+    error = mutex_plain_unlock_fast(mutex);
+
+    if (unlikely(error)) {
+        mutex_plain_unlock_slow(mutex);
+    }
+}
+
+#endif /* _KERN_MUTEX_PLAIN_I_H */
diff --git a/kern/mutex/mutex_plain_types.h b/kern/mutex/mutex_plain_types.h
new file mode 100644
index 00000000..02731e94
--- /dev/null
+++ b/kern/mutex/mutex_plain_types.h
@@ -0,0 +1,33 @@
+/*
+ * Copyright (c) 2017 Richard Braun.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ * Isolated type definition used to avoid inclusion circular dependencies.
+ */
+
+#ifndef _KERN_MUTEX_PLAIN_TYPES_H
+#define _KERN_MUTEX_PLAIN_TYPES_H
+
+#ifndef _KERN_MUTEX_TYPES_H
+#error "don't include <kern/mutex/mutex_plain_types.h> directly," \
+       " use <kern/mutex_types.h> instead"
+#endif
+
+struct mutex {
+    unsigned int state;
+};
+
+#endif /* _KERN_MUTEX_PLAIN_TYPES_H */
diff --git a/kern/mutex_i.h b/kern/mutex_i.h
deleted file mode 100644
index a4a40eb5..00000000
--- a/kern/mutex_i.h
+++ /dev/null
@@ -1,53 +0,0 @@
-/*
- * Copyright (c) 2013-2017 Richard Braun.
- *
- * This program is free software: you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation, either version 3 of the License, or
- * (at your option) any later version.
- *
- * This program 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 General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program.  If not, see <http://www.gnu.org/licenses/>.
- */
-
-#ifndef _KERN_MUTEX_I_H
-#define _KERN_MUTEX_I_H
-
-#ifndef X15_MUTEX_PI
-
-#include <kern/assert.h>
-#include <kern/atomic.h>
-#include <kern/mutex_types.h>
-
-#define MUTEX_UNLOCKED  0
-#define MUTEX_LOCKED    1
-#define MUTEX_CONTENDED 2
-
-static inline unsigned int
-mutex_lock_fast(struct mutex *mutex)
-{
-    return atomic_cas_acquire(&mutex->state, MUTEX_UNLOCKED, MUTEX_LOCKED);
-}
-
-static inline unsigned int
-mutex_unlock_fast(struct mutex *mutex)
-{
-    unsigned int state;
-
-    state = atomic_swap_release(&mutex->state, MUTEX_UNLOCKED);
-    assert((state == MUTEX_LOCKED) || (state == MUTEX_CONTENDED));
-    return state;
-}
-
-void mutex_lock_slow(struct mutex *mutex);
-
-void mutex_unlock_slow(struct mutex *mutex);
-
-#endif /* X15_MUTEX_PI */
-
-#endif /* _KERN_MUTEX_I_H */
diff --git a/kern/mutex_types.h b/kern/mutex_types.h
index 4b7947fc..432eab30 100644
--- a/kern/mutex_types.h
+++ b/kern/mutex_types.h
@@ -21,24 +21,10 @@
 #ifndef _KERN_MUTEX_TYPES_H
 #define _KERN_MUTEX_TYPES_H
 
-#ifdef X15_MUTEX_PI
-
-#include <kern/rtmutex_types.h>
-
-/*
- * Do not directly alias rtmutex to make sure they cannot be used
- * with condition variables by mistake.
- */
-struct mutex {
-    struct rtmutex rtmutex;
-};
-
-#else /* X15_MUTEX_PI */
-
-struct mutex {
-    unsigned int state;
-};
-
-#endif /* X15_MUTEX_PI */
+#if defined(X15_MUTEX_PI)
+#include <kern/mutex/mutex_pi_types.h>
+#else
+#include <kern/mutex/mutex_plain_types.h>
+#endif
 
 #endif /* _KERN_MUTEX_TYPES_H */
diff --git a/kern/rtmutex.c b/kern/rtmutex.c
index 6f639ddf..6909ce18 100644
--- a/kern/rtmutex.c
+++ b/kern/rtmutex.c
@@ -36,7 +36,7 @@ void
 rtmutex_lock_slow(struct rtmutex *rtmutex)
 {
     struct turnstile *turnstile;
-    uintptr_t owner, prev_owner;
+    uintptr_t owner, prev_owner; /* TODO Review names */
     struct thread *thread;
     uintptr_t bits;
 
@@ -64,6 +64,7 @@ rtmutex_lock_slow(struct rtmutex *rtmutex)
     turnstile_own(turnstile);
 
     if (turnstile_empty(turnstile)) {
+        /* TODO Review memory order */
         prev_owner = atomic_swap_acquire(&rtmutex->owner, owner);
         assert(prev_owner == (owner | bits));
     }