1 files changed, 165 insertions, 0 deletions
diff --git a/src/mutex.h b/src/mutex.h
new file mode 100644
index 0000000..c158d5e
--- /dev/null
+++ b/src/mutex.h
@@ -0,0 +1,165 @@
+/*
+ * Copyright (c) 2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ *
+ * Mutex module.
+ *
+ * A mutex is a thread synchronization tool that provides mutual exclusion.
+ * The code between locking and unlocking a mutex forms a critical section
+ * that only one thread may be running at a time. This is true for all
+ * critical sections created with the same mutex, i.e. only one thread may
+ * be running code in all the critical sections created with the same mutex.
+ *
+ * A mutex is initially not owned. When a thread locks a mutex, it becomes
+ * owned until unlocked, and any other thread trying to lock the mutex
+ * waits for the owner to unlock it. This is called contention. Waiting
+ * can be active, e.g. by spinning on the mutex, constantly checking if
+ * it's still locked, or passive, by sleeping until the owner unlocks
+ * and wakes up one of the waiters. Mutexes are generally passive, and
+ * this is also the case for this module.
+ *
+ * Since mutexes work by blocking execution of some threads, they are a
+ * type of lock. Despite their apparent simplicity, they are associated
+ * with a number of problems, most considered difficult when compared to
+ * other well know problems of computer science.
+ *
+ * In particular, mutexes are vulnerable to deadlocks, i.e. a situation
+ * where all threads involved are waiting for events that cannot occur.
+ * Imagine two threads, T1 and T2, and 2 mutexes, M1 and M2. Here is
+ * a representation of the execution history of those threads leading to
+ * a deadlock :
+ *
+ * T1 : lock(M1) -> lock(M2) (M2 is locked by T2)
+ * T2 : lock(M2) -> lock(M1) (M1 is locked by T1)
+ *
+ * Here, both threads are waiting for the other to unlock one of the
+ * mutexes before unlocking the other mutex, and none can make progress.
+ *
+ * The most simple solution to avoid deadlocks is to not use locks in
+ * the first place, and use other synchronization tools such as disabling
+ * preemption, or resorting to lock-free algorithms, but this is often
+ * not possible (preemption cannot normally be disabled outside kernel
+ * code, and lock-free algorithms are difficult to implement and may
+ * lack other dependencies like atomic instructions on small processors).
+ *
+ * Another simple solution is to avoid holding two mutexes at the same
+ * time. It can often be achieved, but not always. Sometimes, holding
+ * multiple mutexes at the same time is a requirement. In such cases,
+ * the most common solution is to establish a locking order, since a
+ * deadlock may only occur if mutexes are acquired in different orders.
+ * In the example above, the locking order could be represented as
+ * "M1 -> M2", stating that, when hodling both mutexes, M1 must always
+ * be locked before M2.
+ *
+ * Another common problem with mutexes is unbounded priority inversion.
+ * Imagine 2 threads, T1 and T2 with priorities 1 and 2 respectively
+ * (higher value means higher priority). On a real-time system with
+ * a simple fixed priority scheduler, T2 would preempt T1 whenever it
+ * is active. But if it then tries to lock a mutex owned by T1, it will
+ * have to wait for T1 to unlock the mutex. This is priority inversion,
+ * because T1 is running instead of T2 despite having a lower priority.
+ * Priority inversion itself is common and often unavoidable in many
+ * cases, and if kept reliably short, it normally doesn't disturb
+ * real-time behaviour. But if there is no guarantee that the critical
+ * section is time-bounded, real-time behaviour may not be achieved.
+ * The classic example is three threads, T1, T2, and T3, with priorities
+ * 1, 2, and 3 respectively, and T3 locking a mutex already owned by T1 :
+ *
+ *  time ->
+ * T3                   lock(M) +             run ...
+ * T2               run +       run +         |
+ * T1 lock(M) - run +               unlock(M) +
+ * +: preemption                ^^^
+ *                              duration not known/bounded
+ *
+ * Here, T3 has to wait for T1 to unlock the mutex before making progress,
+ * but T2 may preempt T1 because of its higher priority. The time T2 runs,
+ * keeping T1 from making progress, is likely not known and unbounded, and
+ * it indirectly delays T3, despite T3 having a higher priority. This is
+ * unbounded priority inversion. It can be avoided at somewhat high cost
+ * with priority ceiling/inheritance, or by avoiding the use of mutexes,
+ * relying instead on e.g. message queues using preemption for
+ * synchronization.
+ *
+ * The implementation of this module is very simple and doesn't prevent
+ * unbounded priority inversions.
+ *
+ * When deciding whether to use a mutex or to disable preemption for
+ * mutual exclusion, keep in mind that all real-world mutex implementations
+ * disable preemption internally. As a result, it is best to use mutexes
+ * when critical sections are noticeably more expensive than the overhead
+ * of locking. Another parameter is whether or not the critical section
+ * must remain preemptible.
+ *
+ * This mutex interface matches the "fast" kind of POSIX mutexes. In
+ * particular, a mutex cannot be locked recursively.
+ */
+
+#ifndef _MUTEX_H
+#define _MUTEX_H
+
+#include <stdbool.h>
+
+#include <lib/list.h>
+
+#include "thread.h"
+
+/*
+ * Mutex type.
+ *
+ * All members are private.
+ */
+struct mutex {
+    struct list waiters;
+    struct thread *owner;
+    bool locked;
+};
+
+/*
+ * Initialize a mutex.
+ */
+void mutex_init(struct mutex *mutex);
+
+/*
+ * Lock a mutex.
+ *
+ * If the given mutex is already locked, the calling thread blocks (by
+ * sleeping) and resumes once it holds the mutex.
+ */
+void mutex_lock(struct mutex *mutex);
+
+/*
+ * Try to lock a mutex.
+ *
+ * This is the non-blocking variant of mutex_lock().
+ *
+ * Return 0 on success, ERROR_BUSY if locking the mutex failed.
+ */
+int mutex_trylock(struct mutex *mutex);
+
+/*
+ * Unlock a mutex.
+ *
+ * The calling thread must be the mutex owner.
+ */
+void mutex_unlock(struct mutex *mutex);
+
+#endif /* _MUTEX_H */