Fixed a bug in private wakeups by calling ipc_entry_alloc_name(). This is the last version as everything works now.
To do a quick userspace mutex test with timed waits: #include "gnumach.h" #include <mach_init.h> #include <pthread.h> #include <stdio.h> int e = 0; void *thread_f(void *arg) { printf("Thread 2 about to block.\n"); futex_wait(mach_task_self(), (vm_offset_t)&e, (vm_offset_t)&e, 0, 1); printf("Thread 2 waking up.\n"); return NULL; } int main() { pthread_t new_thread; pthread_attr_t attr; pthread_attr_init(&attr); pthread_create(&new_thread, &attr, thread_f, NULL); printf("Thread 1 about to sleep for 1000 msec (first time).\n"); futex_wait(mach_task_self(), (vm_offset_t)&e, (vm_offset_t)&e, 1000, 1); printf("Thread 1 about to wake thread 2.\n"); futex_wake(mach_task_self(), (vm_offset_t)&e, 1, 1); printf("Thread 1 about to sleep for 1000 msec (second time).\n"); futex_wait(mach_task_self(), (vm_offset_t)&e, (vm_offset_t)&e, 1000, 1); return 0; } --- Makefrag.am | 2 + include/mach/gnumach.defs | 14 +++ kern/futex.c | 247 +++++++++++++++++++++++++++++++++++++++++++++ kern/futex.h | 55 ++++++++++ kern/startup.c | 3 + 5 files changed, 321 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..2868545 --- /dev/null +++ b/kern/futex.c @@ -0,0 +1,247 @@ +/* + * 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/rbtree.h> +#include <kern/sched_prim.h> +#include <kern/thread.h> +#include <kern/lock.h> +#include <kern/kalloc.h> +#include <kern/assert.h> +#include <vm/vm_map.h> +#include <ipc/ipc_space.h> +#include <ipc/ipc_entry.h> + +struct futex { + + struct rbtree_node *node; + + 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) +{ + ipc_entry_t entry; + mach_port_t name; + + ipc_entry_alloc(current_thread()->task->itk_space, &name, &entry); + is_write_unlock(current_thread()->task->itk_space); + ipc_entry_alloc_name(current_thread()->task->itk_space, address, &entry); + entry->ie_bits |= MACH_PORT_TYPE_DEAD_NAME; + is_write_unlock(current_thread()->task->itk_space); + + return 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; + + kern_return_t kr; + kr = vm_map_lookup(¤t_map(), address, VM_PROT_READ, &version, &futex.object, &futex.offset, &prot, &wired); + assert(kr == KERN_SUCCESS); + + 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; + + kern_return_t kr; + kr = vm_map_lookup(¤t_map(), address, VM_PROT_READ, + &version, &(*futex)->object, &(*futex)->offset, &prot, &wired); + assert(kr == KERN_SUCCESS); + + (*futex)->nr_refs = 0; + + simple_lock(&futex_shared_lock); + + rbtree_insert(&futex_shared_tree, &node, futex_shared_cmp_insert); + + (*futex)->node = &node; + + 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)); + assert(futex_ipc_space != NULL); + ipc_space_create(0, &futex_ipc_space); + 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); + assert(entry != NULL); + } + + if (*(int *)futex_address == *(int *)compare_address) { + + is_write_lock(current_thread()->task->itk_space); + + assert_wait((event_t)futex_address, TRUE); + + if (msec != 0) + thread_will_wait_with_timeout(current_thread(), (unsigned int)msec); + + is_write_unlock(current_thread()->task->itk_space); + + thread_block(NULL); + + } + + } else { + + struct rbtree_node *node; + struct futex *futex; + + node = futex_lookup_address(futex_address); + + if (node == NULL) + assert(futex_shared_init(futex_address, &futex) == 0); + + 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) { + + is_write_lock(current_thread()->task->itk_space); + + if (wake_all) + thread_wakeup((event_t)address); + else + thread_wakeup_one((event_t)address); + + is_write_unlock(current_thread()->task->itk_space); + + } + + } 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..172c43c --- /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 one or 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