Number of threads to wake is now a boolean, which means it's one or all. Call to assert_wait() has been added before thread_suspend(). The scan for vm_objects has been removed and recursion in futex_wake() has been removed and code rewriten.
There are problems however, futex_wait() test on the Hurd fails with illegal instruction error. When I comment out the entire futex_wait() I still get the same error, so I don't know how to fix this, since I can't trace the error to any instruction in the program. The code to reproduce this is: extern int futex_wait(); int e = 0; int main(void) { return futex_wait(&e, e); } On Linux everything works fine, except segfaults in vm_map_lookup() and assert_wait() and of course thread_suspend() doesn't actually work. But when commented out everything else works fine. There is also a failed assertion in malloc.c:3096 when allocating memory for the threads. If anybody has any info on this errors, I'll be thankful. They may just be beginner's mistakes. --- Makefrag.am | 2 + kern/futex.c | 370 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ kern/futex.h | 100 ++++++++++++++++ 3 files changed, 472 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..878be81 --- /dev/null +++ b/kern/futex.c @@ -0,0 +1,370 @@ +/* + * 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> + +static futex_hash_table_t table = NULL; +static unsigned int prev_hash_val = 0; +static unsigned int max_hash_val = 0; + +/* + * When operation equals futex_wait(), this is a method for a thread to wait for a + * change of value at a given address. + * + * When operation equals futex_wake(), this is a method for waking up all or one + * thread waiting for a change of value at a given address. + * + * Return values: + * 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_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 + * FUTEX_MEMORY_ERROR - memory error + * FUTEX_RESOURCE_SHORTAGE - no virtual memory + * FUTEX_THREAD_NO_SUSPEND - thread suspend failed + * + */ + +int futex_init(futex_t futex, int *address) +{ + if (table == NULL) { + if (futex_hash_table_init() == FUTEX_RESOURCE_SHORTAGE) + return FUTEX_RESOURCE_SHORTAGE; + } + + if ((table->futex_elements = (futex_t)__builtin_malloc((max_hash_val+1)*sizeof(struct futex))) == NULL) + return FUTEX_RESOURCE_SHORTAGE; + + simple_lock_init(&futex->futex_wait_lock); + + futex->address = address; + futex->num_futexed_threads = 0; + futex->next_futex = NULL; + futex->prev_futex = &(table->futex_elements[prev_hash_val]); + futex->prev_futex->next_futex = futex; + *futex->map = current_thread()->task->map; + + if ((vm_map_lookup(futex->map, (vm_offset_t)address, VM_PROT_READ, futex->version, futex->object, + futex->offset, futex->out_prot, futex->wired) != KERN_SUCCESS)) { + unsigned int temp_hash_val = futex_hash(address); + __builtin_free(&(table->futex_elements[temp_hash_val])); + return FUTEX_MEMORY_ERROR; + } + + return 0; +} + +int futex_wait(int *address, int value) +{ + futex_t futex; + + 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) { + + if (futex->num_futexed_threads == 128) + return FUTEX_RESOURCE_SHORTAGE; + + /* Add the thread to the futex. */ + + /* Commented out. Failed assertion in malloc.c:3096. Number of threads + * is limited to 128. + */ + /* + if ((futex->futexed_threads = + (thread_t)__builtin_malloc((futex->num_futexed_threads+1)*sizeof(struct thread))) == NULL) { + simple_unlock(&futex->futex_wait_lock); + return FUTEX_RESOURCE_SHORTAGE; + } + + futex->futexed_threads[futex->num_futexed_threads++] = *(current_thread()); + */ + + futex->futexed_threads[futex->num_futexed_threads++] = current_thread(); + + goto suspend; + } else + goto no_suspend; + + } else { + + int i = futex_hash_table_add_address(address); + + if (i == 1) return FUTEX_RESOURCE_SHORTAGE; + if (i != 0) return i; + + goto lookup; + } + + suspend: + assert_wait(¤t_thread()->state , FALSE); + simple_unlock(&futex->futex_wait_lock); + kern_return_t ret = thread_suspend(current_thread()); + if (ret != KERN_SUCCESS) { + //__builtin_free(&(futex->futexed_threads[--futex->num_futexed_threads])); + return FUTEX_THREAD_NO_SUSPEND; + } + return FUTEX_RESUMED_BY_WAKE; + + no_suspend: + simple_unlock(&futex->futex_wait_lock); + return FUTEX_NO_THREAD_SUSPENDED; +} + +int futex_wake(int *address, boolean_t wake_all) +{ + futex_t futex, temp_futex; + + temp_futex = futex_hash_table_lookup_address(address); + + if (temp_futex != NULL) + futex_cross_address_space_wake(temp_futex, wake_all); + else + goto no_thread; + + futex = futex_hash_table_lookup_address(address); + + if (futex != NULL) { + + simple_lock(&futex->futex_wait_lock); + + futex_wake_threads(futex, wake_all); + + if (futex->num_futexed_threads == 0) + futex_hash_table_delete_futex(futex); + + simple_unlock(&futex->futex_wait_lock); + + return FUTEX_SOME_NUMBER_RESUMED; + + } else { + no_thread: + return FUTEX_NO_THREAD; + } +} + +void futex_cross_address_space_wake(futex_t futex, boolean_t wake_all) +{ + futex_t temp_futex = futex; + + for ( ; futex != NULL; futex = futex->next_futex) { + + simple_lock(&futex->futex_wait_lock); + + if (*(futex->offset) == *(futex->next_futex->offset)) { + + simple_lock(&futex->next_futex->futex_wait_lock); + + futex_wake_threads(futex->next_futex, wake_all); + + if (futex->next_futex->num_futexed_threads == 0) { + simple_unlock(&futex->futex_wait_lock); + simple_unlock(&futex->next_futex->futex_wait_lock); + futex_hash_table_delete_futex(futex->next_futex); + return; + } + + simple_unlock(&futex->next_futex->futex_wait_lock); + + } + + simple_unlock(&futex->futex_wait_lock); + } + + for (futex = temp_futex; futex != NULL; futex = futex->prev_futex) { + + simple_lock(&futex->futex_wait_lock); + + if (*(futex->offset) == *(futex->prev_futex->offset)) { + + simple_lock(&futex->prev_futex->futex_wait_lock); + + futex_wake_threads(futex->prev_futex, wake_all); + + if (futex->prev_futex->num_futexed_threads == 0) { + simple_unlock(&futex->futex_wait_lock); + simple_unlock(&futex->prev_futex->futex_wait_lock); + futex_hash_table_delete_futex(futex->prev_futex); + return; + } + + simple_unlock(&futex->prev_futex->futex_wait_lock); + + } + + simple_unlock(&futex->futex_wait_lock); + } +} + +void futex_wake_threads(futex_t futex, boolean_t wake_all) +{ + if (wake_all) { + int i; + int thread_num = futex->num_futexed_threads; + for (i = 0; i < thread_num; i++) { + thread_resume(futex->futexed_threads[i]); + futex->num_futexed_threads--; + //__builtin_free(futex->futexed_threads[i]); + } + } else { + thread_resume(futex->futexed_threads[futex->num_futexed_threads-1]); + futex->num_futexed_threads--; + //__builtin_free(futex->futexed_threads[futex->num_futexed_threads]); + } +} + +int futex_hash_table_init(void) +{ + if ((table = (futex_hash_table_t)__builtin_malloc(sizeof(struct futex_hash_table))) == NULL) + return FUTEX_RESOURCE_SHORTAGE; + + simple_lock_init(&table->futex_hash_table_lock); + + table->size = 0; + + return 0; +} + +unsigned int futex_hash(int *address) +{ + unsigned int hash_val = 0; + + hash_val = (unsigned int)address + (hash_val << 5) - hash_val; + + if (table != NULL) { + unsigned int ret = hash_val % table->size; + if (ret > max_hash_val) + max_hash_val = ret; + return ret; + } else + return 0; +} + +futex_t futex_hash_table_lookup_address(int *address) +{ + futex_t futex; + + if (table == NULL) + return NULL; + + unsigned int hash_val = futex_hash(address); + + simple_lock(&table->futex_hash_table_lock); + + for (futex = &(table->futex_elements[hash_val]); futex != NULL; futex = futex->next_futex) { + + if (address == futex->address) { + simple_unlock(&table->futex_hash_table_lock); + return futex; + + } + } + + for (futex = &(table->futex_elements[hash_val]); futex != NULL; futex = futex->prev_futex) { + + if (address == futex->address) { + simple_unlock(&table->futex_hash_table_lock); + return futex; + + } + } + + simple_unlock(&table->futex_hash_table_lock); + + return NULL; +} + +int futex_hash_table_add_address(int *address) +{ + futex_t new_futex; + + unsigned int hash_val = futex_hash(address); + + if (table != NULL) { + simple_lock(&table->futex_hash_table_lock); + } + + if ((new_futex = (futex_t)__builtin_malloc(sizeof(struct futex))) == NULL) { + if (table != NULL) + simple_unlock(&table->futex_hash_table_lock); + return 1; + } + + int ret; + + if ((ret = futex_init(new_futex, address)) != 0) { + if (table != NULL) + simple_unlock(&table->futex_hash_table_lock); + return ret; + } + + new_futex->hash_val = hash_val; + table->futex_elements[hash_val] = *new_futex; + table->size++; + + prev_hash_val = hash_val; + + if (table != NULL) + simple_unlock(&table->futex_hash_table_lock); + + return 0; +} + +void futex_hash_table_delete_futex(futex_t futex) +{ + /* New next futex in queue. */ + futex_t new_next_futex = futex->next_futex; + + simple_lock(&table->futex_hash_table_lock); + + table->futex_elements[futex->hash_val].prev_futex->next_futex = new_next_futex; + + /* New previous futex of the new next futex in queue. */ + if (new_next_futex != NULL) + table->futex_elements[futex->hash_val].prev_futex->next_futex->prev_futex = + table->futex_elements[futex->hash_val].prev_futex; + + __builtin_free(&(table->futex_elements[futex->hash_val])); + + table->size--; + + if (table->size == 0) { + simple_unlock(&table->futex_hash_table_lock); + __builtin_free(table); + table = NULL; + } + + if (table != NULL) + simple_unlock(&table->futex_hash_table_lock); +} diff --git a/kern/futex.h b/kern/futex.h new file mode 100644 index 0000000..3af500a --- /dev/null +++ b/kern/futex.h @@ -0,0 +1,100 @@ +/* + * 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 <kern/thread.h> +#include <vm/vm_map.h> +#include <kern/lock.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_THREAD_NO_SUSPEND 7 + +typedef struct futex *futex_t; + +struct futex { + + /* Futex lock. */ + decl_simple_lock_data( , futex_wait_lock); + + /* Futex address. */ + int *address; + + /* Map futex is in. */ + vm_map_t *map; + + vm_map_version_t *version; + vm_object_t *object; + vm_offset_t *offset; + vm_prot_t *out_prot; + boolean_t *wired; + + /* Next futex in queue. */ + futex_t next_futex; + + /* Previous futex in queue. */ + futex_t prev_futex; + + /* Number of futexed threads at the same address. */ + unsigned int num_futexed_threads; + + /* Array of futexed threads at the same address. */ + //thread_t futexed_threads; + + thread_t futexed_threads[128]; + + /* Hash value in the hash table. */ + unsigned int hash_val; +}; + +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. */ + futex_t futex_elements; +}; + +typedef struct futex_hash_table *futex_hash_table_t; + +int futex_init(futex_t futex, int *address); +extern int futex_wait(int *address, int value); +extern int futex_wake(int *address, boolean_t wake_all); +void futex_cross_address_space_wake(futex_t futex, boolean_t wake_all); +void futex_wake_threads(futex_t futex, boolean_t wake_all); +int futex_hash_table_init(void); +unsigned int futex_hash(int *address); +futex_t futex_hash_table_lookup_address(int *address); +int futex_hash_table_add_address(int *address); +void futex_hash_table_delete_futex(futex_t futex); + +#endif /* _KERN_FUTEX_H_ */ -- 1.7.10.4