Private futexes are now per task. Tree compare functions have been rewriten. Waits are now interruptible and bounded sleep has been merged into the unbounded case. Function futex_wait() now takes the address as the argument instead of the value.
--- Makefrag.am | 2 + include/mach/gnumach.defs | 14 +++ kern/futex.c | 271 +++++++++++++++++++++++++++++++++++++++++++++ kern/futex.h | 55 +++++++++ kern/startup.c | 3 + 5 files changed, 345 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..5fef7ea 100644 --- a/include/mach/gnumach.defs +++ b/include/mach/gnumach.defs @@ -63,3 +63,17 @@ simpleroutine thread_terminate_release( reply_port : mach_port_name_t; address : vm_address_t; size : vm_size_t); + +routine futex_wait( + task : task_t; + futex_address : vm_offset_t; + compare_address : vm_offset_t; + msec : int; + private_futex : boolean_t); + +routine futex_wake( + task : task_t; + address : vm_offset_t; + wake_all : boolean_t; + private_futex : boolean_t); + diff --git a/kern/futex.c b/kern/futex.c new file mode 100644 index 0000000..035d7de --- /dev/null +++ b/kern/futex.c @@ -0,0 +1,271 @@ +/* + * 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/rbtree.h> +#include <kern/futex.h> +#include <kern/sched_prim.h> +#include <vm/vm_map.h> +#include <machine/locore.h> +#include <kern/thread.h> +#include <kern/lock.h> +#include <kern/kalloc.h> +#include <ipc/ipc_space.h> +#include <ipc/ipc_entry.h> + +struct futex { + + struct rbtree_node *node; + + ipc_entry_t entry; + + decl_simple_lock_data( , lock); + + vm_offset_t address; + + vm_object_t object; + + vm_offset_t offset; + + unsigned int nr_refs; + +}; + +static struct rbtree futex_shared_tree; +decl_simple_lock_data(static, futex_shared_lock); + +void futex_setup(void) +{ + rbtree_init(&futex_shared_tree); + simple_lock_init(&futex_shared_lock); +} + +static inline int futex_shared_cmp_lookup(struct futex *futex, struct rbtree_node *node2) +{ + int temp = futex->offset - rbtree_entry(node2, struct futex, node)->offset + + futex->object - rbtree_entry(node2, struct futex, node)->object; + + if (temp < 0) return -1; + else if (temp > 0) return 1; + else return 0; +} + +static inline int futex_shared_cmp_insert(struct rbtree_node *node1, struct rbtree_node *node2) +{ + return futex_shared_cmp_lookup(rbtree_entry(node1, struct futex, node), node2); +} + +static ipc_entry_t futex_private_init(vm_offset_t address) +{ + struct futex *futex; + + futex = (struct futex *)kalloc(sizeof(*futex)); + if (futex == NULL) + return NULL; + + futex->node = NULL; + futex->address = address; + futex->nr_refs = 0; + futex->object = NULL; + futex->offset = 0; + futex->entry = NULL; + + simple_lock_init(&futex->lock); + is_write_lock(current_thread()->task->itk_space); + ipc_entry_grow_table(current_thread()->task->itk_space); + ipc_entry_alloc(current_thread()->task->itk_space, &address, &futex->entry); + is_write_unlock(current_thread()->task->itk_space); + + return futex->entry; +} + +static struct rbtree_node *futex_lookup_address(vm_offset_t address) +{ + struct futex futex; + + vm_map_version_t version; + vm_prot_t prot; + boolean_t wired; + + vm_map_lookup(¤t_map(), address, VM_PROT_READ, &version, &futex.object, &futex.offset, &prot, &wired); + + return rbtree_lookup(&futex_shared_tree, &futex, futex_shared_cmp_lookup); +} + +static int futex_shared_init(vm_offset_t address, struct futex **futex) +{ + vm_map_version_t version; + vm_prot_t prot; + boolean_t wired; + + *futex = (struct futex *)kalloc(sizeof(**futex)); + if (*futex == NULL) + return -1; + + struct rbtree_node node; + + vm_map_lookup(¤t_map(), address, VM_PROT_READ, + &version, &(*futex)->object, &(*futex)->offset, &prot, &wired); + + (*futex)->node = &node; + (*futex)->address = address; + (*futex)->nr_refs = 0; + (*futex)->entry = NULL; + + simple_lock(&futex_shared_lock); + + rbtree_insert(&futex_shared_tree, &node, futex_shared_cmp_insert); + + simple_unlock(&futex_shared_lock); + + return 0; +} + +void futex_wait(task_t task, vm_offset_t futex_address, vm_offset_t compare_address, int msec, boolean_t private_futex) +{ + if (private_futex) { + + ipc_entry_t entry; + + if (current_thread()->task->itk_space == NULL) { + + struct ipc_space *futex_ipc_space; + + futex_ipc_space = (struct ipc_space *)kalloc(sizeof(*futex_ipc_space)); + if (futex_ipc_space == NULL) + return; + is_lock_init(futex_ipc_space); + futex_ipc_space->is_active = TRUE; + current_thread()->task->itk_space = futex_ipc_space; + + } + + entry = ipc_entry_lookup(current_thread()->task->itk_space, futex_address); + + if (entry == NULL) { + entry = futex_private_init(futex_address); + if (entry == NULL) + return; + } + + if (*(int *)futex_address == *(int *)compare_address) { + + struct futex *pfutex; + + pfutex = structof(entry, struct futex, entry); + + simple_lock(&pfutex->lock); + + pfutex->nr_refs++; + + assert_wait(pfutex, TRUE); + + if (msec != 0) + thread_will_wait_with_timeout(current_thread(), (unsigned int)msec); + + simple_unlock(&pfutex->lock); + + thread_block(NULL); + + pfutex->nr_refs--; + + } + + } else { + + struct rbtree_node *node; + struct futex *futex; + + node = futex_lookup_address(futex_address); + + if (node == NULL) + if (futex_shared_init(futex_address, &futex) != 0) + return; + + if (*(int *)futex_address == *(int *)compare_address) { + + simple_lock(&futex_shared_lock); + + if (node != NULL) + futex = rbtree_entry(node, struct futex, node); + + futex->nr_refs++; + + assert_wait(futex, TRUE); + + if (msec != 0) + thread_will_wait_with_timeout(current_thread(), (unsigned int)msec); + + simple_unlock(&futex_shared_lock); + + thread_block(NULL); + + if (--futex->nr_refs == 0) { + rbtree_remove(&futex_shared_tree, futex->node); + kfree((vm_offset_t)futex, sizeof(*futex)); + } + } + } +} + +void futex_wake(task_t task, vm_offset_t address, boolean_t wake_all, boolean_t private_futex) +{ + if (private_futex) { + + ipc_entry_t entry = ipc_entry_lookup(current_thread()->task->itk_space, address); + + if (entry != NULL) { + + struct futex *futex = structof(entry, struct futex, entry); + + simple_lock(&futex->lock); + + if (wake_all) + thread_wakeup(futex); + else + thread_wakeup_one(futex); + + simple_unlock(&futex->lock); + + } + + } else { + + struct rbtree_node *node = futex_lookup_address(address); + + if (node != NULL) { + + struct futex *futex = rbtree_entry(node, struct futex, node); + + simple_lock(&futex_shared_lock); + + if (wake_all) + thread_wakeup(futex); + else + thread_wakeup_one(futex); + + simple_unlock(&futex_shared_lock); + + } + } +} diff --git a/kern/futex.h b/kern/futex.h new file mode 100644 index 0000000..4c30afa --- /dev/null +++ b/kern/futex.h @@ -0,0 +1,55 @@ +/* + * 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); + +/* + * The calling thread blocks if values at the addresses are the same. Values + * should be integers. + * + * If msec is non-zero, thread blocks for msec amount of time. If it's zero, no + * timeout is used. + * + * If private_futex is true, futex is not shared between tasks. + * + */ +void futex_wait(task_t task, vm_offset_t futex_address, vm_offset_t compare_address, int msec, boolean_t private_futex); + +/* + * The calling thread wakes one or all threads blocked in futex_wait(). + * + * If wake_all is true, all threads are awakened. If it's false, only one thread is + * awakened. + * + * If private_futex is false the thread wakes all threads with futex addresses at the + * same offset in the same VM object. + * + */ +void futex_wake(task_t task, vm_offset_t address, boolean_t wake_all, boolean_t private_futex); + +#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