summaryrefslogtreecommitdiff
path: root/kern
diff options
context:
space:
mode:
Diffstat (limited to 'kern')
-rw-r--r--kern/rtmutex.c108
-rw-r--r--kern/rtmutex.h111
-rw-r--r--kern/rtmutex_i.h79
-rw-r--r--kern/rtmutex_types.h30
4 files changed, 328 insertions, 0 deletions
diff --git a/kern/rtmutex.c b/kern/rtmutex.c
new file mode 100644
index 00000000..f79f8a88
--- /dev/null
+++ b/kern/rtmutex.c
@@ -0,0 +1,108 @@
+/*
+ * 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/>.
+ */
+
+#include <stddef.h>
+#include <stdint.h>
+
+#include <kern/assert.h>
+#include <kern/rtmutex.h>
+#include <kern/rtmutex_i.h>
+#include <kern/rtmutex_types.h>
+#include <kern/thread.h>
+#include <kern/turnstile.h>
+#include <machine/atomic.h>
+
+static void
+rtmutex_set_contended(struct rtmutex *rtmutex)
+{
+ uintptr_t owner, prev_owner;
+
+ do {
+ owner = rtmutex->owner;
+ prev_owner = atomic_cas_uintptr(&rtmutex->owner, owner,
+ owner | RTMUTEX_CONTENDED);
+ } while (prev_owner != owner);
+}
+
+void
+rtmutex_lock_slow(struct rtmutex *rtmutex)
+{
+ struct turnstile *turnstile;
+ uintptr_t owner, prev_owner;
+ struct thread *thread;
+ uintptr_t bits;
+
+ owner = (uintptr_t)thread_self();
+
+ turnstile = turnstile_lend(rtmutex);
+
+ rtmutex_set_contended(rtmutex);
+
+ bits = RTMUTEX_CONTENDED;
+
+ for (;;) {
+ prev_owner = atomic_cas_uintptr(&rtmutex->owner, bits, owner | bits);
+ assert((prev_owner & bits) == bits);
+
+ if (prev_owner == bits) {
+ break;
+ }
+
+ thread = (struct thread *)(prev_owner & RTMUTEX_OWNER_MASK);
+ turnstile_wait(turnstile, "rtmutex", thread);
+ bits |= RTMUTEX_FORCE_WAIT;
+ }
+
+ turnstile_own(turnstile);
+
+ if (turnstile_empty(turnstile)) {
+ prev_owner = atomic_swap_uintptr(&rtmutex->owner, owner);
+ assert(prev_owner == (owner | bits));
+ }
+
+ turnstile_return(turnstile);
+
+ /*
+ * A lock owner should never perform priority propagation on itself,
+ * because this process is done using its own priority, potentially
+ * introducing unbounded priority inversion.
+ * Instead, let new waiters do it, using their own priority.
+ */
+}
+
+void
+rtmutex_unlock_slow(struct rtmutex *rtmutex)
+{
+ struct turnstile *turnstile;
+ uintptr_t owner, prev_owner;
+
+ owner = (uintptr_t)thread_self();
+
+ turnstile = turnstile_acquire(rtmutex);
+ assert(turnstile != NULL);
+
+ prev_owner = atomic_swap_uintptr(&rtmutex->owner,
+ RTMUTEX_FORCE_WAIT | RTMUTEX_CONTENDED);
+ assert((prev_owner & RTMUTEX_OWNER_MASK) == owner);
+
+ turnstile_disown(turnstile);
+ turnstile_signal(turnstile);
+
+ turnstile_release(turnstile);
+
+ thread_propagate_priority();
+}
diff --git a/kern/rtmutex.h b/kern/rtmutex.h
new file mode 100644
index 00000000..f7cee716
--- /dev/null
+++ b/kern/rtmutex.h
@@ -0,0 +1,111 @@
+/*
+ * 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/>.
+ *
+ *
+ * Real-time mutual exclusion locks.
+ *
+ * A real-time mutex is similar to a regular mutex, except priority
+ * inheritance is unconditionnally enabled.
+ */
+
+#ifndef _KERN_RTMUTEX_H
+#define _KERN_RTMUTEX_H
+
+#include <stdint.h>
+
+#include <kern/assert.h>
+#include <kern/error.h>
+#include <kern/rtmutex_i.h>
+#include <kern/rtmutex_types.h>
+
+struct rtmutex;
+
+#define rtmutex_assert_locked(rtmutex) assert((rtmutex)->owner != 0)
+
+/*
+ * Initialize a real-time mutex.
+ */
+static inline void
+rtmutex_init(struct rtmutex *rtmutex)
+{
+ rtmutex->owner = 0;
+}
+
+/*
+ * Attempt to lock the given real-time mutex.
+ *
+ * This function may not sleep.
+ *
+ * Return 0 on success, ERROR_BUSY if the mutex is already locked.
+ */
+static inline int
+rtmutex_trylock(struct rtmutex *rtmutex)
+{
+ uintptr_t prev_owner;
+
+ prev_owner = rtmutex_tryacquire(rtmutex);
+
+ if (prev_owner == 0) {
+ return 0;
+ }
+
+ return ERROR_BUSY;
+}
+
+/*
+ * Lock a real-time mutex.
+ *
+ * If the mutex is already locked, the calling thread sleeps until the
+ * mutex is unlocked, and its priority is propagated as needed to prevent
+ * unbounded priority inversion.
+ *
+ * A mutex can only be locked once.
+ */
+static inline void
+rtmutex_lock(struct rtmutex *rtmutex)
+{
+ uintptr_t prev_owner;
+
+ prev_owner = rtmutex_tryacquire(rtmutex);
+
+ if (prev_owner == 0) {
+ return;
+ }
+
+ rtmutex_lock_slow(rtmutex);
+}
+
+/*
+ * Unlock a real-time mutex.
+ *
+ * The mutex must be locked, and must have been locked by the calling
+ * thread.
+ */
+static inline void
+rtmutex_unlock(struct rtmutex *rtmutex)
+{
+ uintptr_t prev_owner;
+
+ prev_owner = rtmutex_tryrelease(rtmutex);
+
+ if (!(prev_owner & RTMUTEX_CONTENDED)) {
+ return;
+ }
+
+ rtmutex_unlock_slow(rtmutex);
+}
+
+#endif /* _KERN_RTMUTEX_H */
diff --git a/kern/rtmutex_i.h b/kern/rtmutex_i.h
new file mode 100644
index 00000000..b99b5bd0
--- /dev/null
+++ b/kern/rtmutex_i.h
@@ -0,0 +1,79 @@
+/*
+ * 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_RTMUTEX_I_H
+#define _KERN_RTMUTEX_I_H
+
+#include <stdbool.h>
+#include <stdint.h>
+
+#include <kern/assert.h>
+#include <kern/rtmutex_types.h>
+#include <kern/thread.h>
+#include <machine/atomic.h>
+
+/*
+ * Real-time mutex flags.
+ *
+ * The "contended" flag indicates that threads are waiting for the mutex
+ * to be unlocked. It forces threads trying to lock the mutex as well as
+ * the owner to take the slow path.
+ *
+ * The "force-wait" flag prevents "stealing" a mutex. When a contended
+ * mutex is unlocked, a thread may concurrently try to lock it. Without
+ * this flag, it may succeed, and in doing so, it would prevent a
+ * potentially higher priority thread from locking the mutex. The flag
+ * forces all threads to not only take the slow path, but to also call
+ * the turnstile wait function so that only the highest priority thread
+ * may lock the mutex.
+ */
+#define RTMUTEX_CONTENDED 0x1
+#define RTMUTEX_FORCE_WAIT 0x2
+
+#define RTMUTEX_OWNER_MASK (~((uintptr_t)(RTMUTEX_FORCE_WAIT \
+ | RTMUTEX_CONTENDED)))
+
+#define rtmutex_assert_owner_aligned(owner) \
+ assert(((owner) & ~RTMUTEX_OWNER_MASK) == 0)
+
+static inline uintptr_t
+rtmutex_tryacquire(struct rtmutex *rtmutex)
+{
+ uintptr_t owner;
+
+ owner = (uintptr_t)thread_self();
+ rtmutex_assert_owner_aligned(owner);
+ return atomic_cas_uintptr(&rtmutex->owner, 0, owner);
+}
+
+static inline uintptr_t
+rtmutex_tryrelease(struct rtmutex *rtmutex)
+{
+ uintptr_t owner, prev_owner;
+
+ owner = (uintptr_t)thread_self();
+ rtmutex_assert_owner_aligned(owner);
+ prev_owner = atomic_cas_uintptr(&rtmutex->owner, owner, 0);
+ assert((prev_owner & RTMUTEX_OWNER_MASK) == owner);
+ return prev_owner;
+}
+
+void rtmutex_lock_slow(struct rtmutex *rtmutex);
+
+void rtmutex_unlock_slow(struct rtmutex *rtmutex);
+
+#endif /* _KERN_RTMUTEX_I_H */
diff --git a/kern/rtmutex_types.h b/kern/rtmutex_types.h
new file mode 100644
index 00000000..c03e0484
--- /dev/null
+++ b/kern/rtmutex_types.h
@@ -0,0 +1,30 @@
+/*
+ * 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_RTMUTEX_TYPES_H
+#define _KERN_RTMUTEX_TYPES_H
+
+#include <stdint.h>
+
+struct rtmutex {
+ uintptr_t owner;
+};
+
+#endif /* _KERN_RTMUTEX_TYPES_H */
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-31 14:39:05 +0000