Futex waiters are now in a list and some bugs were fixed. I think this is now ready for test. I have tested this with malloc() and free() instead of kalloc() and kfree(), but without vm_map_lookup() and assert_wait() since these functions segfault on my machine with GDB.
Functions thread_sleep() and clear_wait() need to be tested if they actually work paired this way. If somebody is willing to do this please let me know, here's a short test program: extern int futex_wait(); extern int futex_wake(); extern int thread_create(); extern void thread_start(); struct thread; typedef struct thread *thread_t; int e = 0; void thread_function(void) { futex_wait(&e, e); } int main(void) { thread_t new_thread; thread_create(current_thread()->task, &new_thread); thread_start(new_thread, thread_function); return futex_wake(&e, 0); } All I need are the return values from main. Thanks. --- Makefrag.am | 2 + kern/futex.c | 398 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ kern/futex.h | 115 +++++++++++++++++ 3 files changed, 515 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..23fb4d4 --- /dev/null +++ b/kern/futex.c @@ -0,0 +1,398 @@ +/* + * Copyright (C) 2013 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/kalloc.h> +#include <vm/vm_map.h> + +#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) + +#define futex_list_for_each(array, entry, list) \ +for (entry = &array[0]; entry != NULL; \ + entry = (typeof(entry))entry->list.next, \ + entry != &array[0]) + +struct futex_hash_table { + + /* Futex hash table lock. */ + decl_simple_lock_data( , futex_hash_table_lock); + + /* Size of the hash table. */ + size_t size; + + /* Array of futexes. */ + struct futex *futex_elements; +}; + +static struct futex_hash_table *futex_table = NULL; +static unsigned int futex_max_hash_val = 0; + +/* + * Function: futex_init() + * + * Initialization of a new futex. + * + * Takes new futex, address and hash value arguments. Returns: + * FUTEX_RESOURCE_SHORTAGE - allocation of the hash table or the array of + * futex pointers has failed + * 0 - success + * + */ +static int futex_init(struct futex *futex, int *address, unsigned int hash_val); + +/* + * Function: futex_wake_one_thread() + * + * Wake one futex thread. + * + * Takes the futex as an argument. + * + */ +static void futex_wake_one_thread(struct futex *futex, int thread_num); + +/* + * Function: futex_cross_address_space_wake() + * + * Cross address space wake. Wakes all threads with the same offset. + * + * Takes the futex and offset arguments. + * + */ +static void futex_cross_address_space_wake(struct futex *futex, vm_offset_t offset); + +/* + * Function: futex_wake_threads() + * + * Wake one or all threads in the futex. + * + * Takes the futex and wake_all arguments. Meaning of wake_all is the same as in + * futex_wake(). + * + */ +static void futex_wake_threads(struct futex *futex, boolean_t wake_all); + +/* + * Function: futex_hash() + * + * Generate a hash value. + * + * Takes the address argument. Returns hash value or 0 if hash table is NULL. + * + */ +static unsigned int futex_hash(int *address); + +/* + * Function: futex_hash_table_lookup_address() + * + * Finds the futex with the specified address. + * + * Takes the address argument. Returns the futex with the address or NULL if it's not + * found. + * + */ +static struct futex *futex_hash_table_lookup_address(int *address); + +/* + * Function: futex_hash_table_add_address() + * + * Add a new address in the hash table. + * + * Takes the address argument. Returns: + * FUTEX_RESOURCE_SHORTAGE - allocation of the hash table, array of + * futex pointers or the new futex has failed + * 0 - success + * + */ +static int futex_hash_table_add_address(int *address); + +/* + * Function: futex_hash_table_delete_futex() + * + * Delete a futex from the hash table. + * + * Takes the futex to be deleted as an argument. + * + */ +static void futex_hash_table_delete_futex(struct futex *futex); + +static int futex_init(struct futex *futex, int *address, unsigned int hash_val) +{ + if (futex_table == NULL) { + if (futex_hash_table_setup() == FUTEX_RESOURCE_SHORTAGE) { + return FUTEX_RESOURCE_SHORTAGE; + } + } + + futex = (struct futex *)kalloc(sizeof(*futex)); + futex_table->futex_elements = (struct futex *)kalloc((futex_max_hash_val + 1) * sizeof(futex)); + //futex = (struct futex *)__builtin_malloc(sizeof(*futex)); + //futex_table->futex_elements = (struct futex *)__builtin_malloc((futex_max_hash_val + 1) * sizeof(futex)); + if (futex_table->futex_elements == NULL || futex == NULL) + return FUTEX_RESOURCE_SHORTAGE; + + simple_lock_init(&futex->futex_wait_lock); + + futex->address = address; + + futex->hash_val = hash_val; + + futex_table->futex_elements[hash_val] = *futex; + futex_table->size++; + + list_init(&futex->futex_list); + list_concat(&futex_table->futex_elements[0].futex_list, &futex->futex_list); + + return 0; +} + +int futex_wait(int *address, int value) +{ + struct futex *futex; + struct futex_waiter waiter; + + lookup: + + futex = futex_hash_table_lookup_address(address); + + if (futex != NULL) { + + simple_lock(&futex->futex_wait_lock); + + /* If the value is still the same. */ + if (*address == value) { + + waiter.thread = current_thread(); + + kern_return_t kr; + kr = vm_map_lookup(¤t_map(), (vm_offset_t)futex->address, VM_PROT_READ, NULL, NULL, + &waiter.offset, NULL, NULL); + if (kr != KERN_SUCCESS) + return FUTEX_MEMORY_ERROR; + + futex->futex_waiters = (struct futex_waiter *)kalloc((ARRAY_SIZE(futex->futex_waiters) + 1) * sizeof(&waiter)); + /*futex->futex_waiters = (struct futex_waiter *) + __builtin_malloc((ARRAY_SIZE(futex->futex_waiters) + 1) * sizeof(&waiter));*/ + if (futex->futex_waiters == NULL) + return FUTEX_RESOURCE_SHORTAGE; + + waiter.index = ARRAY_SIZE(futex->futex_waiters) - 1; + + /* Add the waiter to the futex. */ + futex->futex_waiters[ARRAY_SIZE(futex->futex_waiters) - 1] = waiter; + + list_init(&futex->futex_waiters[ARRAY_SIZE(futex->futex_waiters) - 1].futex_waiters_list); + list_concat(&futex->futex_waiters[0].futex_waiters_list, + &futex->futex_waiters[ARRAY_SIZE(futex->futex_waiters) - 1].futex_waiters_list); + + thread_sleep(futex, (simple_lock_t)&futex->futex_wait_lock, FALSE); + + /* Wait has been cleared in futex_wake_one_thread(). */ + list_remove(&futex->futex_waiters[waiter.index].futex_waiters_list); + kfree((vm_offset_t)&futex->futex_waiters[waiter.index], sizeof(&waiter)); + //__builtin_free(&futex->futex_waiters[waiter.index]); + return FUTEX_RESUMED_BY_WAKE; + + } else { + simple_unlock(&futex->futex_wait_lock); + return FUTEX_NO_THREAD_SUSPENDED; + } + + } else { + + int i = futex_hash_table_add_address(address); + + if (i != 0) return i; + + goto lookup; + } +} + +int futex_wake(int *address, boolean_t wake_all) +{ + struct futex *futex; + + futex = futex_hash_table_lookup_address(address); + + if (futex != NULL) { + + simple_lock(&futex->futex_wait_lock); + + futex_wake_threads(futex, wake_all); + + simple_unlock(&futex->futex_wait_lock); + + return FUTEX_SOME_NUMBER_RESUMED; + + } else + return FUTEX_NO_THREAD; +} + +static void futex_wake_one_thread(struct futex *futex, int thread_num) +{ + clear_wait(futex->futex_waiters[thread_num].thread, THREAD_AWAKENED, FALSE); +} + +static void futex_cross_address_space_wake(struct futex *futex, vm_offset_t offset) +{ + futex_list_for_each(futex_table->futex_elements, futex, futex_list) { + + simple_lock(&futex->futex_wait_lock); + + struct futex_waiter *waiter; + + futex_list_for_each(futex->futex_waiters, waiter, futex_waiters_list) { + + if (waiter->offset == offset) { + + futex_wake_one_thread(futex, waiter->index); + + if (list_empty(&futex->futex_waiters[0].futex_waiters_list)) { + simple_unlock(&futex->futex_wait_lock); + futex_hash_table_delete_futex(futex); + return; + } + } + } + + simple_unlock(&futex->futex_wait_lock); + } +} + +static void futex_wake_threads(struct futex *futex, boolean_t wake_all) +{ + if (wake_all) { + + struct futex_waiter *waiter; + + futex_list_for_each(futex->futex_waiters, waiter, futex_waiters_list) + futex_cross_address_space_wake(futex, waiter->offset); + + } else + futex_cross_address_space_wake(futex, futex->futex_waiters[ARRAY_SIZE(futex->futex_waiters) - 1].offset); +} + +int futex_hash_table_setup(void) +{ + futex_table = (struct futex_hash_table *)kalloc(sizeof(*futex_table)); + //futex_table = (struct futex_hash_table *)__builtin_malloc(sizeof(*futex_table)); + if (futex_table == NULL) + return FUTEX_RESOURCE_SHORTAGE; + + simple_lock_init(&futex_table->futex_hash_table_lock); + + futex_table->size = 0; + + return 0; +} + +static unsigned int futex_hash(int *address) +{ + unsigned int hash_val = (unsigned int)address; + + if (futex_table != NULL) { + unsigned int power_of_two_size = 1, i; + for (i = 1; i < futex_table->size; i++) + power_of_two_size *= 2; + unsigned int ret = hash_val & power_of_two_size; + if (ret > futex_max_hash_val) + futex_max_hash_val = ret; + return ret; + } else + return 0; +} + +static struct futex *futex_hash_table_lookup_address(int *address) +{ + struct futex *futex; + + if (futex_table == NULL) { + return NULL; + } + + simple_lock(&futex_table->futex_hash_table_lock); + + futex_list_for_each(futex_table->futex_elements, futex, futex_list) { + + if (address == futex->address) { + simple_unlock(&futex_table->futex_hash_table_lock); + return futex; + + } + } + + simple_unlock(&futex_table->futex_hash_table_lock); + + return NULL; +} + +static int futex_hash_table_add_address(int *address) +{ + struct futex *new_futex = NULL; + + unsigned int hash_val = futex_hash(address); + + if (futex_table != NULL) + simple_lock(&futex_table->futex_hash_table_lock); + + int ret; + + ret = futex_init(new_futex, address, hash_val); + if (ret != 0) { + if (futex_table != NULL) + simple_unlock(&futex_table->futex_hash_table_lock); + return ret; + } + + /* futex_table is non-NULL because of the call to futex_init(). */ + if (simple_lock_try(&futex_table->futex_hash_table_lock)) + simple_unlock(&futex_table->futex_hash_table_lock); + + return 0; +} + +static void futex_hash_table_delete_futex(struct futex *futex) +{ + simple_lock(&futex_table->futex_hash_table_lock); + + list_remove(&futex->futex_list); + + kfree((vm_offset_t)futex, sizeof(*futex)); + kfree((vm_offset_t)&futex_table->futex_elements[futex->hash_val], sizeof(futex)); + //__builtin_free(futex); + //__builtin_free(&futex_table->futex_elements[futex->hash_val]); + + futex_table->size--; + + if (futex_table->size == 0) { + simple_unlock(&futex_table->futex_hash_table_lock); + kfree((vm_offset_t)futex_table, sizeof(*futex_table)); + //__builtin_free(futex_table); + futex_table = NULL; + return; + } + + simple_unlock(&futex_table->futex_hash_table_lock); +} diff --git a/kern/futex.h b/kern/futex.h new file mode 100644 index 0000000..faa8fda --- /dev/null +++ b/kern/futex.h @@ -0,0 +1,115 @@ +/* + * Copyright (C) 2013 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/lock.h> +#include <kern/list.h> +#include <kern/thread.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 + +struct futex_waiter { + + /* Futex waiters list. */ + struct list futex_waiters_list; + + /* Index in the futex. */ + unsigned int index; + + /* Associated thread. */ + thread_t thread; + + /* Offset from the (task map, futex address) value pair. */ + vm_offset_t offset; +}; + +struct futex { + /* List of futexes. */ + struct list futex_list; + + /* Futex lock. */ + decl_simple_lock_data( , futex_wait_lock); + + /* Futex address. */ + int *address; + + /* Array of futex waiters at the same address. */ + struct futex_waiter *futex_waiters; + + /* Hash value in the hash table. */ + unsigned int hash_val; +}; + +/* + * Function: futex_wait() + * + * This is a method for a thread to wait for a change of value at a given address. + * + * Takes address and value arguments. Returns: + * FUTEX_RESUMED_BY_WAKE - thread has been resumed by futex_wake() + * FUTEX_NO_THREAD_SUSPENDED - value at the address has been changed while inside + * futex_wait() and no thread has been suspended + * FUTEX_RESOURCE_SHORTAGE - allocation of the new futex, hash table, array of futex + * pointers or array of futex waiters pointers has failed + * FUTEX_MEMORY_ERROR - vm_map_lookup() has failed + * + */ +extern int futex_wait(int *address, int value); + + +/* + * Function: futex_wake() + * + * This is a method for waking up one or all threads waiting for a change of + * value at a given address. + * + * Takes address and wake_all arguments. If wake_all is TRUE, all threads are + * awakened. If it is FALSE, only one thread is awakened. + * + * Returns: + * FUTEX_SOME_NUMBER_RESUMED - threads have been resumed by futex_wake() + * FUTEX_NO_THREAD - futex_wake() did not found a suspended thread at the + * passed address + * + */ +extern int futex_wake(int *address, boolean_t wake_all); + +/* + * Function: futex_hash_table_setup() + * + * Setup of the global hash table. + * + * Returns: + * FUTEX_RESOURCE_SHORTAGE - allocation of the hash table has failed + * 0 - success + * + */ +int futex_hash_table_setup(void); + +#endif /* _KERN_FUTEX_H_ */ -- 1.7.10.4