First threads were blocked and awakened when called from userspace. :)
Timed waits work as expected. Private and shared futexes always block threads
when called from futex_wait().
This is now ready for test. What needs to be tested is:
1. If sync circle actually wakes the threads when sent a wakeup signal.
2. If simple mutex actually blocks the threads locking a locked mutex and
if it wakes waiters when mutex becomes unlocked.
3. Cross address space wake test. This needs to create two threads blocked at
different addresses in different mappings but sharing the same vm_object
at the same offset.
As far the code is concerned I bypassed the opacity of red-black tree
structures in two places, as I always get a segfault somewhere in the
rbtree module.
Also, I had to create a recursion to generate unique event numbers, but it's
bounded so I don't think there will be a problem. I expect only one or two
levels of recursion in actual usage, if any.
---
Makefrag.am | 2 +
include/mach/gnumach.defs | 13 ++
kern/futex.c | 389 +++++++++++++++++++++++++++++++++++++++++++++
kern/futex.h | 70 ++++++++
kern/startup.c | 3 +
5 files changed, 477 insertions(+)
create mode 100644 kern/futex.c
create mode 100644 kern/futex.h
diff --git a/Makefrag.am b/Makefrag.am
index c1387bd..e43f882 100644
--- a/Makefrag.am
+++ b/Makefrag.am
@@ -145,6 +145,8 @@ libkernel_a_SOURCES += \
kern/eventcount.h \
kern/exception.c \
kern/exception.h \
+ kern/futex.c \
+ kern/futex.h \
kern/host.c \
kern/host.h \
kern/ipc_host.c \
diff --git a/include/mach/gnumach.defs b/include/mach/gnumach.defs
index 12c4e99..196dbd7 100644
--- a/include/mach/gnumach.defs
+++ b/include/mach/gnumach.defs
@@ -63,3 +63,16 @@ simpleroutine thread_terminate_release(
reply_port : mach_port_name_t;
address : vm_address_t;
size : vm_size_t);
+
+routine futex_wait(
+ task : task_t;
+ address : vm_offset_t;
+ value : int;
+ msec : int;
+ private_futex : boolean_t);
+
+routine futex_wake(
+ task : task_t;
+ address : vm_offset_t;
+ wake_all: boolean_t);
+
diff --git a/kern/futex.c b/kern/futex.c
new file mode 100644
index 0000000..765741d
--- /dev/null
+++ b/kern/futex.c
@@ -0,0 +1,395 @@
+/*
+ * Copyright (C) 2013, 2014 Free Software Foundation, Inc.
+ *
+ * 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 2, 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, write to the Free Software
+ * Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ * Author: Marin Ramesa
+ */
+
+/*
+ * Fast userspace locking
+ *
+ */
+
+#include <kern/futex.h>
+#include <kern/sched_prim.h>
+#include <kern/rbtree.h>
+#include <vm/vm_map.h>
+#include <machine/locore.h>
+#include <kern/thread.h>
+#include <kern/lock.h>
+#include <kern/kalloc.h>
+
+#define ARRAY_SIZE(x) (sizeof(x) / sizeof(x[0]))
+
+struct futex {
+
+ /* Futex node in the futex tree. */
+ struct rbtree_node *node;
+
+ decl_simple_lock_data( , futex_private_lock);
+
+ vm_offset_t address;
+
+ /* If a shared futex this is NULL, otherwise it holds the address of
the task. */
+ task_t task;
+
+ /* Block and wakeup event. */
+ event_t event;
+
+ /* Save the map for futex_check_consistency() routine. */
+ vm_map_t map;
+
+ /* Save the vm_object for futex_check_consistency() routine. */
+ vm_object_t object;
+
+ /* Number of futex waiters. Needed to release the memory after
thread_wakeup_prim(). */
+ unsigned int num_waiters;
+
+};
+
+static struct rbtree futex_tree;
+decl_simple_lock_data(static, futex_shared_lock);
+static struct futex *shared_futexes;
+
+/* TODO Should be per-task. */
+static struct futex *pfutexes;
+
+void futex_setup(void)
+{
+ rbtree_init(&futex_tree);
+ simple_lock_init(&futex_shared_lock);
+}
+
+static inline int compare_nodes_insert(struct rbtree_node *node1, struct
rbtree_node *node2)
+{
+ if (rbtree_entry(node1, struct futex, node)->address -
rbtree_entry(node2, struct futex, node)->address != 0)
+ return 1;
+ else
+ return 0;
+}
+
+static inline int compare_nodes_lookup(vm_offset_t address, struct rbtree_node
*node2)
+{
+ if (address - rbtree_entry(node2, struct futex, node)->address != 0)
+ return 1;
+ else
+ return 0;
+}
+
+static unsigned long futex_init(task_t task, vm_offset_t address, boolean_t
private_futex, struct futex *futex)
+{
+ unsigned long node_slot = 0;
+
+ futex = (struct futex *)kalloc(sizeof(*futex));
+ if (futex == NULL)
+ return 0;
+
+ simple_lock(&futex_shared_lock);
+
+ struct rbtree_node node;
+ rbtree_node_init(&node);
+
+ rbtree_insert(&futex_tree, &node, compare_nodes_insert);
+ futex->node = &node;
+ futex->address = address;
+ futex->event = NULL;
+ futex->map = current_map();
+ futex->num_waiters = 0;
+ futex->object = NULL;
+
+ if (private_futex) {
+ futex->task = task;
+ simple_lock_init(&futex->futex_private_lock);
+ } else
+ futex->task = NULL;
+
+ rbtree_lookup_slot(&futex_tree, address, compare_nodes_lookup,
node_slot);
+
+ simple_unlock(&futex_shared_lock);
+
+ return node_slot;
+}
+
+static unsigned long futex_lookup_address(vm_offset_t address)
+{
+ unsigned long node_slot = 0;
+
+ simple_lock(&futex_shared_lock);
+
+ rbtree_lookup_slot(&futex_tree, address, compare_nodes_lookup,
node_slot);
+
+ simple_unlock(&futex_shared_lock);
+
+ return node_slot;
+}
+
+static void futex_deallocate_array_slot(struct futex *futex, struct
rbtree_node *node)
+{
+ if (futex->task == NULL) {
+ int i;
+ for (i = 0; i < ARRAY_SIZE(shared_futexes); i++)
+ if (shared_futexes[i].node == node) break;
+ kfree((vm_offset_t)&shared_futexes[i],
sizeof(&shared_futexes[i]));
+ } else {
+ int i;
+ for (i = 0; i < ARRAY_SIZE(pfutexes); i++)
+ if (pfutexes[i].node == node) break;
+ kfree((vm_offset_t)&pfutexes[i], sizeof(&pfutexes[i]));
+ }
+}
+
+static vm_offset_t futex_gen_unique_event_num(vm_offset_t sum, vm_offset_t
add1, vm_offset_t add2)
+{
+ if (sum == 0) return 0;
+
+ struct rbtree_node *node;
+
+ for(node = futex_tree.root; node != NULL; node =
node->children[RBTREE_RIGHT]) {
+
+ struct futex *futex;
+ futex = rbtree_entry(node, struct futex, node);
+
+ vm_offset_t futex_event_num = (vm_offset_t)futex->event;
+
+ if (futex_event_num == sum) {
+
+ if (futex_event_num - add2 == add1)
+ continue;
+ else
+ return futex_gen_unique_event_num(sum - 1,
add1, add2);
+
+ }
+ }
+
+ return sum;
+}
+void futex_wait(task_t task, vm_offset_t address, int value, int /* TODO Use
time_value_t */ msec, boolean_t private_futex)
+{
+ unsigned long node_slot = 0;
+
+ node_slot = futex_lookup_address(address);
+ if (node_slot == 0) {
+ if (private_futex) {
+ pfutexes = (struct futex *)kalloc(sizeof(pfutexes));
+ if (pfutexes == NULL)
+ return;
+ node_slot = futex_init(task, address, TRUE,
&pfutexes[ARRAY_SIZE(pfutexes) - 1]);
+ } else {
+ shared_futexes = (struct futex
*)kalloc(sizeof(shared_futexes));
+ if (shared_futexes == NULL)
+ return;
+ node_slot = futex_init(task, address, FALSE,
&shared_futexes[ARRAY_SIZE(shared_futexes) - 1]);
+ }
+ if (node_slot == 0) return;
+ }
+
+ if (__sync_bool_compare_and_swap((int *)address, value, value)) {
+
+ if (msec != 0) {
+
+ simple_lock(&futex_shared_lock);
+
+ thread_timeout_setup(current_thread());
+
+ assert_wait(NULL, TRUE);
+ thread_will_wait_with_timeout(current_thread(),
(unsigned int)msec);
+
+ simple_unlock(&futex_shared_lock);
+
+ thread_block(NULL);
+
+ return;
+
+ }
+
+ if (private_futex) {
+
+ struct futex *pfutex;
+
+ simple_lock(&futex_shared_lock);
+
+ pfutex = rbtree_entry(rbtree_slot_parent(node_slot),
struct futex, node);
+
+ simple_unlock(&futex_shared_lock);
+
+ simple_lock(&pfutex->futex_private_lock);
+
+ pfutex->num_waiters++;
+
+ pfutex->event = (event_t)futex_gen_unique_event_num
+ ((vm_offset_t)pfutex->map + address,
(vm_offset_t)pfutex->map, address);
+
+ thread_sleep(pfutex->event,
(simple_lock_t)&pfutex->futex_private_lock, FALSE);
+
+ pfutex->num_waiters--;
+ if (pfutex->num_waiters == 0) {
+ rbtree_remove(&futex_tree, pfutex->node);
+ futex_deallocate_array_slot(pfutex,
pfutex->node);
+ kfree((vm_offset_t)pfutex, sizeof(*pfutex));
+ }
+
+ } else {
+
+ struct futex *futex;
+ vm_object_t object;
+ vm_offset_t offset;
+ vm_map_version_t version;
+ vm_prot_t prot;
+ boolean_t wired;
+
+ simple_lock(&futex_shared_lock);
+
+ futex = rbtree_entry(rbtree_slot_parent(node_slot),
struct futex, node);
+
+ vm_map_lookup(¤t_map(), address, VM_PROT_READ,
&version, &object, &offset, &prot, &wired);
+
+ futex->object = object;
+
+ futex->event = (event_t)futex_gen_unique_event_num
+ ((vm_offset_t)object + offset,
(vm_offset_t)object, offset);
+
+ thread_sleep(futex->event,
(simple_lock_t)&futex_shared_lock, FALSE);
+
+ futex->num_waiters--;
+ if (futex->num_waiters == 0) {
+ rbtree_remove(&futex_tree, futex->node);
+ futex_deallocate_array_slot(futex, futex->node);
+ kfree((vm_offset_t)futex, sizeof(*futex));
+ }
+ }
+
+ }
+}
+
+static int futex_check_consistency(struct futex *futex)
+{
+ vm_object_t object;
+ vm_offset_t offset;
+ vm_map_version_t version;
+ vm_prot_t prot;
+ boolean_t wired;
+
+ vm_map_lookup(&futex->map, futex->address, VM_PROT_READ, &version,
&object, &offset, &prot, &wired);
+
+ if (futex->event == (event_t)((vm_offset_t)object + offset))
+ return 0;
+ else {
+ if ((futex->object->shadowed) && (futex->object->shadow ==
object))
+ return 0;
+ else
+ return -1;
+ }
+}
+
+void futex_wake(task_t task, vm_offset_t address, boolean_t wake_all)
+{
+ unsigned node_slot = 0;
+ node_slot = futex_lookup_address(address);
+
+ if (node_slot != 0) {
+
+ simple_lock(&futex_shared_lock);
+
+ struct rbtree_node *node;
+
+ for(node = futex_tree.root; node != NULL; node =
node->children[RBTREE_RIGHT]) {
+
+ struct futex *futex;
+ futex = rbtree_entry(node, struct futex, node);
+
+ if (futex->task == NULL)
+ if (futex_check_consistency(futex) != 0)
+ continue;
+
+ if (wake_all) {
+ thread_wakeup(futex->event);
+ continue;
+ }
+ else {
+ thread_wakeup_one(futex->event);
+ break;
+ }
+ }
+
+ simple_unlock(&futex_shared_lock);
+ }
+}
+
+struct sync_circle {
+
+ int value;
+
+};
+
+void sync_circle_init(struct sync_circle *scircle)
+{
+ scircle->value = 0;
+}
+
+void sync_circle_wait(struct sync_circle *scircle)
+{
+ futex_wait(current_thread()->task, (vm_offset_t)&scircle->value,
scircle->value, 0, 1);
+}
+
+void sync_circle_signal(struct sync_circle *scircle)
+{
+ scircle->value++;
+ futex_wake(current_thread()->task, (vm_offset_t)&scircle->value, 1);
+}
+
+struct simple_mutex {
+
+ #define SMUTEX_UNLOCKED 0
+ #define SMUTEX_NO_WAITERS 1
+ #define SMUTEX_WAITERS 2
+
+ int value;
+
+};
+
+void simple_mutex_init(struct simple_mutex *smutex)
+{
+ smutex->value = SMUTEX_UNLOCKED;
+}
+
+void simple_mutex_lock(struct simple_mutex *smutex)
+{
+ int c;
+
+ if ((c = __sync_val_compare_and_swap(&smutex->value, SMUTEX_UNLOCKED,
SMUTEX_NO_WAITERS)) != SMUTEX_UNLOCKED) {
+ if (c != SMUTEX_WAITERS)
+ c = __sync_lock_test_and_set(&smutex->value,
SMUTEX_WAITERS);
+ while (c != SMUTEX_UNLOCKED) {
+ futex_wait(current_thread()->task,
(vm_offset_t)&smutex->value, SMUTEX_WAITERS, 0, 1);
+ c = __sync_lock_test_and_set(&smutex->value,
SMUTEX_WAITERS);
+ }
+ }
+}
+
+void simple_mutex_unlock(struct simple_mutex *smutex)
+{
+ if (__sync_lock_test_and_set(&smutex->value, smutex->value - 1) !=
SMUTEX_NO_WAITERS) {
+ smutex->value = SMUTEX_UNLOCKED;
+ futex_wake(current_thread()->task, (vm_offset_t)&smutex->value,
0);
+ }
+}
diff --git a/kern/futex.h b/kern/futex.h
new file mode 100644
index 0000000..d88c9f6
--- /dev/null
+++ b/kern/futex.h
@@ -0,0 +1,70 @@
+/*
+ * Copyright (C) 2013, 2014 Free Software Foundation, Inc.
+ *
+ * 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 2, 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, write to the Free Software
+ * Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ * Author: Marin Ramesa
+ */
+
+#ifndef _KERN_FUTEX_H_
+#define _KERN_FUTEX_H_
+
+#include <mach/boolean.h>
+#include <kern/task.h>
+
+struct futex;
+
+void futex_setup(void);
+
+/*
+ * This is a method for a thread to wait for a change of value at a given
address.
+ * If msec is non-zero, thread blocks for msec amount of time. If it's zero, no
+ * timeout is used. If private_futex is one, futex is not shared between tasks.
+ */
+void futex_wait(task_t task, vm_offset_t address, int value, int msec,
boolean_t private_futex);
+
+/*
+ * This is a method for waking up one or all threads waiting for a change of
+ * value at a given address.
+ *
+ * If wake_all is one, all threads are awakened. If it's zero, only one thread
is
+ * awakened.
+ */
+void futex_wake(task_t task, vm_offset_t address, boolean_t wake_all);
+
+/*
+ * The idea is that each thread calls sync_circle_wait() with the same object
as
+ * the argument. Then a thread outside of the sync circle calls
sync_circle_signal()
+ * to send a wakeup signal.
+ */
+struct sync_circle;
+
+#define decl_sync_circle(class, name) \
+class struct sync_circle name;
+
+void sync_circle_init(struct sync_circle *scircle);
+void sync_circle_wait(struct sync_circle *scircle);
+void sync_circle_signal(struct sync_circle *scircle);
+
+/* Simple mutex implementation based on futex calls and GCC builtins. */
+struct simple_mutex;
+
+#define decl_simple_mutex(class, name) \
+class struct simple_mutex name;
+
+void simple_mutex_init(struct simple_mutex *smutex);
+void simple_mutex_lock(struct simple_mutex *smutex);
+void simple_mutex_unlock(struct simple_mutex *smutex);
+
+#endif /* _KERN_FUTEX_H_ */
diff --git a/kern/startup.c b/kern/startup.c
index 12f5123..447c528 100644
--- a/kern/startup.c
+++ b/kern/startup.c
@@ -50,6 +50,7 @@
#include <kern/bootstrap.h>
#include <kern/time_stamp.h>
#include <kern/startup.h>
+#include <kern/futex.h>
#include <vm/vm_kern.h>
#include <vm/vm_map.h>
#include <vm/vm_object.h>
@@ -158,6 +159,8 @@ void setup_main(void)
recompute_priorities(NULL);
compute_mach_factor();
+ futex_setup();
+
/*
* Create a kernel thread to start the other kernel
* threads. Thread_resume (from kernel_thread) calls
--
1.7.10.4
