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