[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[RFC] kern: simple futex for gnumach (version 10)
|
From: |
Marin Ramesa |
|
Subject: |
[RFC] kern: simple futex for gnumach (version 10) |
|
Date: |
Sun, 5 Jan 2014 23:12:29 +0100 |
This time with a sync circle and a simple mutex (based on
Event and Mutex Take 3 chapters from "Futexes Are Tricky").
---
Makefrag.am | 2 +
kern/futex.c | 320 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
kern/futex.h | 104 ++++++++++++++++++
kern/startup.c | 3 +
4 files changed, 429 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/kern/futex.c b/kern/futex.c
new file mode 100644
index 0000000..44ba939
--- /dev/null
+++ b/kern/futex.c
@@ -0,0 +1,320 @@
+/*
+ * 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>
+
+/* Atomic compare using GCC builtin. */
+#define atomic_compare(value1, value2) __sync_bool_compare_and_swap(&value1,
value2, value1)
+
+#define is_black(x) ((x & RBTREE_COLOR_MASK) == RBTREE_COLOR_BLACK)
+#define set_black(x) (x & RBTREE_PARENT_MASK) | RBTREE_COLOR_BLACK;
+
+#define thread_addr(node) (node)->children[RBTREE_LEFT]
+
+/*
+ * When color of the node is red, parent of the node is the futex address,
left child or
+ * the right child is the futex waiter offset and right child is the another
futex address.
+ * When color of the node is black, parent of the node is the futex waiter's
offset, left
+ * child is the thread address and right child is another offset.
+ */
+static struct rbtree futex_tree;
+
+decl_simple_lock_data(static, futex_lock);
+
+void futex_setup(void)
+{
+ rbtree_init(&futex_tree);
+ simple_lock_init(&futex_lock);
+}
+
+/* Inserts are always with absolute difference so we insert in the right
direction in the tree. */
+#define abs(x) ((x) >= 0 ? (x) : -(x))
+
+/* Returns the difference in futex addresses; assertion in rbtree_insert()
fails if it returns 0. */
+static inline int compare_nodes_insert_futex(struct rbtree_node *node1, struct
rbtree_node *node2)
+{
+ return abs(node1->parent - node2->parent);
+}
+
+/* Add the differences between the node addresses, offsets and thread
addresses. */
+static inline int compare_nodes_insert_waiter(struct rbtree_node *node1,
struct rbtree_node *node2)
+{
+ return abs(node1 - node2 + node1->parent - node2->parent +
thread_addr(node1) - thread_addr(node2));
+}
+
+#undef abs
+
+/* For the lookup to succeed the return value must be zero. Which means the
key node's parent must not be the offset. */
+static inline int compare_nodes_lookup(struct rbtree_node *node1, struct
rbtree_node *node2)
+{
+ if (node1 == futex_tree.root)
+ return node1->parent - node2->parent;
+ else
+ return node1->parent - node2->parent + is_black(node1->parent);
+}
+
+/* Insert a new address as the node in the futex tree. */
+static int futex_init(int *address)
+{
+ struct rbtree_node *futex;
+
+ simple_lock(&futex_lock);
+
+ futex = (struct rbtree_node *)kalloc(sizeof(*futex));
+ if (futex == NULL)
+ return FUTEX_RESOURCE_SHORTAGE;
+
+ futex->parent = (unsigned long)address;
+ rbtree_insert(&futex_tree, futex, compare_nodes_insert_futex);
+
+ simple_unlock(&futex_lock);
+
+ return 0;
+}
+
+/* Find the node slot of the futex address in the tree. */
+static unsigned long futex_lookup_address(int *address)
+{
+ unsigned long node_slot = 0;
+ struct rbtree_node node;
+
+ simple_lock(&futex_lock);
+
+ node.parent = (unsigned long)address;
+ rbtree_lookup_slot(&futex_tree, &node, compare_nodes_lookup, node_slot);
+
+ simple_unlock(&futex_lock);
+
+ return node_slot;
+}
+
+int futex_wait(int *address, int value)
+{
+ unsigned long node_slot = 0;
+
+ lookup:
+
+ node_slot = futex_lookup_address(address);
+
+ if (node_slot != 0) {
+
+ simple_lock(&futex_lock);
+
+ int addr_value;
+ copyin(address, &addr_value, sizeof(int));
+
+ if (atomic_compare(addr_value, value)) {
+
+ vm_offset_t offset;
+ struct rbtree_node node;
+
+ /* Fetch the offset from the (task map, futex address)
value pair. */
+ kern_return_t kr;
+ kr = vm_map_lookup(¤t_map(),
(vm_offset_t)address, VM_PROT_READ, NULL, NULL, &offset, NULL, NULL);
+ if (kr != KERN_SUCCESS)
+ return FUTEX_MEMORY_ERROR;
+
+ /* Mark the node black and write the offset. */
+ node.parent = set_black(offset);
+
+ /* Save the current thread address. */
+ thread_addr(&node) = (struct rbtree_node
*)current_thread();
+
+ rbtree_insert(&futex_tree, &node,
compare_nodes_insert_waiter);
+
+ /* Block with the offset as the event. */
+ thread_sleep((event_t)node.parent,
(simple_lock_t)&futex_lock, FALSE);
+
+ /* Thread was awakened in thread_wakeup_prim(). Remove
the offset. */
+ rbtree_remove(&futex_tree, &node);
+
+ return FUTEX_RESUMED_BY_WAKE;
+
+ } else {
+ simple_unlock(&futex_lock);
+ return FUTEX_NO_THREAD_SUSPENDED;
+ }
+
+ } else {
+
+ if (futex_init(address) != 0)
+ return FUTEX_RESOURCE_SHORTAGE;
+
+ goto lookup;
+ }
+}
+
+int futex_wake(int *address, _Bool wake_all)
+{
+ #define offset(x) x->children[RBTREE_RIGHT]->parent
+ #define next_node(x) x->children[RBTREE_RIGHT]
+
+ unsigned node_slot = 0;
+ node_slot = futex_lookup_address(address);
+
+ if (node_slot != 0) {
+
+ simple_lock(&futex_lock);
+
+ struct rbtree_node *node;
+
+ for (node = rbtree_first(&futex_tree); node != NULL; node =
next_node(node)) {
+
+ /* Clean up the futex with zero waiters. */
+ if (next_node(node) == NULL && node != futex_tree.root
&& !is_black(node->parent)) {
+ kfree((vm_offset_t)node, sizeof(*node));
+ rbtree_remove(&futex_tree, node);
+ continue;
+ }
+
+ /* If addresses match and the child node is black wake
the thread/s. */
+ if (!is_black(node->parent) && is_black(offset(node))
&& ((int *)node->parent == address)) {
+ if (wake_all)
+ thread_wakeup((event_t)offset(node));
+ else
+
thread_wakeup_one((event_t)offset(node));
+ break;
+ }
+
+ /* Break if this was the last node. */
+ if (node == rbtree_last(&futex_tree)) {
+ break;
+ }
+
+ }
+
+ simple_unlock(&futex_lock);
+ return FUTEX_SOME_NUMBER_RESUMED;
+
+ } else {
+ return FUTEX_NO_THREAD;
+ }
+#undef offset
+#undef next_node
+}
+
+int futex_wait_timeout(int *address, int value, unsigned int msec)
+{
+ unsigned long node_slot = 0;
+
+ lookup:
+
+ node_slot = futex_lookup_address(address);
+
+ if (node_slot != 0) {
+
+ simple_lock(&futex_lock);
+
+ int addr_value;
+ copyin(address, &addr_value, sizeof(int));
+
+ if (atomic_compare(addr_value, value)) {
+
+ thread_timeout_setup(current_thread());
+
+ assert_wait(NULL, TRUE);
+ thread_will_wait_with_timeout(current_thread(), msec);
+ simple_unlock(&futex_lock);
+
+ thread_block(NULL);
+
+ return FUTEX_TIMED_OUT;
+
+ } else {
+ simple_unlock(&futex_lock);
+ return FUTEX_NO_THREAD_SUSPENDED;
+ }
+
+ } else {
+
+ futex_init(address);
+
+ goto lookup;
+ }
+}
+
+int r_futex_wait(task_t task, pointer_t address, int value)
+{
+ return futex_wait((int *)address, value);
+}
+
+int r_futex_wake(task_t task, pointer_t address, boolean_t wake_all)
+{
+ return futex_wake((int *)address, (_Bool)wake_all);
+}
+
+void sync_circle_init(struct sync_circle *scircle)
+{
+ scircle->value = 0;
+}
+
+int sync_circle_wait(struct sync_circle *scircle)
+{
+ return futex_wait(&scircle->value, scircle->value);
+}
+
+int sync_circle_signal(struct sync_circle *scircle)
+{
+ scircle->value++;
+ return futex_wake(&scircle->value, 1);
+}
+
+#define cmpxchg(x, y, z) __sync_val_compare_and_swap(&x, y, z)
+#define xchg(x, y) __sync_lock_test_and_set(&x, y)
+#define atomic_dec(x) __sync_lock_test_and_set(&x, x - 1)
+
+void simple_mutex_init(struct simple_mutex *smutex)
+{
+ smutex->value = SMUTEX_UNLOCKED;
+}
+
+void simple_mutex_lock(struct simple_mutex *smutex)
+{
+ int c;
+
+ if ((c = cmpxchg(smutex->value, SMUTEX_UNLOCKED, SMUTEX_NO_WAITERS)) !=
SMUTEX_UNLOCKED) {
+ if (c != SMUTEX_WAITERS)
+ c = xchg(smutex->value, SMUTEX_WAITERS);
+ while (c != 0) {
+ futex_wait(&smutex->value, SMUTEX_WAITERS);
+ c = xchg(smutex->value, SMUTEX_WAITERS);
+ }
+ }
+}
+
+void simple_mutex_unlock(struct simple_mutex *smutex)
+{
+ if (atomic_dec(smutex->value) != SMUTEX_NO_WAITERS) {
+ smutex->value = SMUTEX_UNLOCKED;
+ futex_wake(&smutex->value, 0);
+ }
+}
diff --git a/kern/futex.h b/kern/futex.h
new file mode 100644
index 0000000..8b98274
--- /dev/null
+++ b/kern/futex.h
@@ -0,0 +1,104 @@
+/*
+ * 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 <mach/std_types.h>
+#include <kern/task.h>
+
+/* Definitions for return values. */
+#define FUTEX_RESUMED_BY_WAKE 0
+#define FUTEX_NO_THREAD_SUSPENDED 1
+#define FUTEX_SOME_NUMBER_RESUMED 2
+#define FUTEX_NO_THREAD 3
+#define FUTEX_MEMORY_ERROR 4
+#define FUTEX_RESOURCE_SHORTAGE 6
+#define FUTEX_TIMED_OUT 7
+
+/* Initialization of the futex tree and the locks. */
+void futex_setup(void);
+
+/*
+ * This is a method for a thread to wait for a change of value at a given
address.
+ *
+ * Function performs a lookup of the address in the futex tree. If address is
+ * found, value at the address is atomically compared with the argument value.
+ * If the values are same, offset from the task's map and futex address is
+ * calculated and thread blocks.
+ */
+int futex_wait(int *address, int value);
+
+/*
+ * This is a method for waking up one or all threads waiting for a change of
+ * value at a given address.
+ *
+ * Function performs a lookup of the address in the futex tree. If address is
+ * found and wake_all argument is TRUE, all threads with the same offsets are
+ * awakened. If wake_all is FALSE, only one thread from the futex is awakened.
+ */
+int futex_wake(int *address, _Bool wake_all);
+
+/* Timed wait for msec time. */
+int futex_wait_timeout(int *address, int value, unsigned int msec);
+
+/* RPCs to call from userspace. */
+int r_futex_wait(task_t task, pointer_t address, int value);
+int r_futex_wake(task_t task, pointer_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. Function sync_circle_signal() first modifies the
sync_circle's
+ * value, which closes the sync circle and then calls futex_wake().
+ */
+struct sync_circle {
+
+ int value;
+
+};
+
+#define decl_sync_circle(class, name) \
+class struct sync_circle name;
+
+void sync_circle_init(struct sync_circle *scircle);
+int sync_circle_wait(struct sync_circle *scircle);
+int sync_circle_signal(struct sync_circle *scircle);
+
+/* Simple mutex implementation based on futex calls and GCC builtins. */
+struct simple_mutex {
+
+ #define SMUTEX_UNLOCKED 0
+ #define SMUTEX_NO_WAITERS 1
+ #define SMUTEX_WAITERS 2
+
+ int value;
+
+};
+
+#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
- [RFC] kern: simple futex for gnumach (version 10),
Marin Ramesa <=