Queue functions and macros are used to implement generic doubly-linked lists.
New structure futex_thread is defined since vm_map_lookup() is now per-thread.
Functions assert_wait(), thread_block(), thread_wakeup() and clear_wait() are
now used instead of thread_suspend() and thread_resume(). New file futex_i.h
is created to contain non-public parts of the futex.h header file. All functions
have been documented.
On Hurd tests fail with a segmentation fault in kalloc() (GDB says kalloc()
segfaults in vm_map_find_entry()). On Linux everything works except segfaults
in vm_map_lookup(), assert_wait(), thread_block() and kalloc() that are to be
expected since gnumach is not running.
---
Makefrag.am | 3 +
kern/futex.c | 350 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
kern/futex.h | 67 +++++++++++
kern/futex_i.h | 188 ++++++++++++++++++++++++++++++
4 files changed, 608 insertions(+)
create mode 100644 kern/futex.c
create mode 100644 kern/futex.h
create mode 100644 kern/futex_i.h
diff --git a/Makefrag.am b/Makefrag.am
index c1387bd..a8f387c 100644
--- a/Makefrag.am
+++ b/Makefrag.am
@@ -145,6 +145,9 @@ libkernel_a_SOURCES += \
kern/eventcount.h \
kern/exception.c \
kern/exception.h \
+ kern/futex.c \
+ kern/futex.h \
+ kern/futex_i.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..6bea384
--- /dev/null
+++ b/kern/futex.c
@@ -0,0 +1,350 @@
+/*
+ * 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/futex_i.h>
+#include <kern/sched_prim.h>
+#include <kern/kalloc.h>
+
+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;
+
+static futex_hash_table_t table = NULL;
+static unsigned int max_hash_val = 0;
+
+int futex_init(futex_t futex, int *address)
+{
+ if (table == NULL) {
+ futex->chain.next = &futex->chain;
+ futex->chain.prev = &futex->chain;
+ if (futex_hash_table_init() == FUTEX_RESOURCE_SHORTAGE) {
+ return FUTEX_RESOURCE_SHORTAGE;
+ }
+ }
+
+ if ((table->futex_elements =
(futex_t)kalloc((max_hash_val+1)*sizeof(futex_t))) == NULL) {
+ return FUTEX_RESOURCE_SHORTAGE;
+ }
+
+ simple_lock_init(&futex->futex_wait_lock);
+
+ futex->address = address;
+ futex->num_futexed_threads = 0;
+
+ queue_enter_first(&futex->chain, futex, futex_t, chain);
+
+ return 0;
+}
+
+int futex_wait(int *address, int value)
+{
+ futex_t futex;
+ futex_thread_t thread = NULL;
+
+ 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) {
+
+ /* Add the thread to the futex. */
+ int ret;
+
+ if ((ret = futex_thread_init(futex, thread)) != 0)
+ return ret;
+
+ 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(&thread->thread->state , FALSE);
+ simple_unlock(&futex->futex_wait_lock);
+ thread_block(NULL);
+ thread_wakeup(&thread->thread->state);
+ 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_wake_one_thread(futex_t futex, int thread_num)
+{
+
clear_wait((&(futex->futexed_threads[futex->num_futexed_threads]))->thread,
THREAD_AWAKENED, FALSE);
+ futex->num_futexed_threads--;
+
kfree((vm_offset_t)&(futex->futexed_threads[futex->num_futexed_threads]),
sizeof(futex_thread_t));
+}
+
+void futex_cross_address_space_wake(futex_t futex, boolean_t wake_all)
+{
+ #define min(x, y) (x <= y ? x : y)
+
+ queue_iterate(&futex->chain, futex, futex_t, chain) {
+
+ simple_lock(&futex->futex_wait_lock);
+
+ int i;
+
+ for (i = 0; i < min(futex->num_futexed_threads,
+ ((futex_t)futex->chain.next)->num_futexed_threads);
i++) {
+
+ if (*(futex->futexed_threads[i].offset) ==
+
*(((futex_t)futex->chain.next)->futexed_threads[i].offset)) {
+
+
simple_lock(&((futex_t)futex->chain.next)->futex_wait_lock);
+
+
futex_wake_one_thread((futex_t)futex->chain.next, i);
+
+ if
(((futex_t)futex->chain.next)->num_futexed_threads == 0) {
+ simple_unlock(&futex->futex_wait_lock);
+
simple_unlock(&((futex_t)futex->chain.next)->futex_wait_lock);
+
futex_hash_table_delete_futex((futex_t)futex->chain.next);
+ #undef min
+ return;
+ }
+ }
+ }
+
+ simple_unlock(&((futex_t)futex->chain.next)->futex_wait_lock);
+ simple_unlock(&futex->futex_wait_lock);
+
+ }
+
+#undef min
+}
+
+void futex_wake_threads(futex_t futex, boolean_t wake_all)
+{
+ if (wake_all) {
+ int i;
+ for (i = 0; i < futex->num_futexed_threads; i++)
+ futex_wake_one_thread(futex, i);
+ } else
+ futex_wake_one_thread(futex, futex->num_futexed_threads-1);
+}
+
+int futex_hash_table_init(void)
+{
+ if ((table = (futex_hash_table_t)kalloc(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);
+
+ if (table->size == 1)
+ hash_val = 0;
+
+ simple_lock(&table->futex_hash_table_lock);
+
+ for (futex = &(table->futex_elements[hash_val]); futex != NULL; futex =
(futex_t)futex->chain.next) {
+
+ if (address == futex->address) {
+ simple_unlock(&table->futex_hash_table_lock);
+ return futex;
+
+ }
+ }
+
+ for (futex = &(table->futex_elements[hash_val]); futex != NULL; futex =
(futex_t)futex->chain.prev) {
+
+ 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)kalloc(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++;
+
+ if (table != NULL)
+ simple_unlock(&table->futex_hash_table_lock);
+
+ return 0;
+}
+
+void futex_hash_table_delete_futex(futex_t futex)
+{
+ simple_lock(&table->futex_hash_table_lock);
+
+ queue_remove(&futex->chain, futex, futex_t, chain);
+
+ kfree((vm_offset_t)futex, sizeof(struct futex));
+ kfree((vm_offset_t)&(table->futex_elements[futex->hash_val]),
sizeof(futex_t));
+
+ table->size--;
+
+ if (table->size == 0) {
+ simple_unlock(&table->futex_hash_table_lock);
+ kfree((vm_offset_t)table, sizeof(struct futex_hash_table));
+ table = NULL;
+ }
+
+ if (table != NULL)
+ simple_unlock(&table->futex_hash_table_lock);
+}
+
+int futex_thread_init(futex_t futex, futex_thread_t thread)
+{
+ if ((thread = (futex_thread_t)kalloc(sizeof(futex_thread_t))) == NULL)
+ return FUTEX_RESOURCE_SHORTAGE;
+
+ thread->thread = current_thread();
+ thread->futex = futex;
+
+ *thread->map = current_map();
+ if ((vm_map_lookup(thread->map, (vm_offset_t)futex->address,
VM_PROT_READ, thread->version, thread->object,
+ thread->offset, thread->out_prot,
thread->wired) != KERN_SUCCESS)) {
+ kfree((vm_offset_t)thread, sizeof(struct futex_thread));
+ return FUTEX_MEMORY_ERROR;
+ }
+
+ if ((futex->futexed_threads =
(futex_thread_t)kalloc((futex->num_futexed_threads++)*sizeof(futex_thread_t)))
== NULL) {
+ return FUTEX_RESOURCE_SHORTAGE;
+ }
+
+ futex->futexed_threads[futex->num_futexed_threads-1] = *thread;
+
+ return 0;
+}
diff --git a/kern/futex.h b/kern/futex.h
new file mode 100644
index 0000000..6dfeff8
--- /dev/null
+++ b/kern/futex.h
@@ -0,0 +1,67 @@
+/*
+ * 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>
+
+/* 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
+
+/*
+ * 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 or
array of futex
+ * pointers 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);
+
+#endif /* _KERN_FUTEX_H_ */
diff --git a/kern/futex_i.h b/kern/futex_i.h
new file mode 100644
index 0000000..3f611f1
--- /dev/null
+++ b/kern/futex_i.h
@@ -0,0 +1,188 @@
+/*
+ * 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_I_H_
+#define _KERN_FUTEX_I_H_
+
+#include <kern/futex.h>
+#include <kern/thread.h>
+#include <vm/vm_map.h>
+#include <kern/lock.h>
+#include <kern/task.h>
+#include <kern/queue.h>
+
+typedef struct futex *futex_t;
+
+struct futex_thread {
+
+ thread_t thread;
+
+ futex_t futex;
+
+ /* Map thread 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;
+};
+
+typedef struct futex_thread *futex_thread_t;
+
+struct futex {
+ /* Queue of futexes. */
+ queue_chain_t chain;
+
+ /* Futex lock. */
+ decl_simple_lock_data( , futex_wait_lock);
+
+ /* Futex address. */
+ int *address;
+
+ /* Number of futexed threads at the same address. */
+ unsigned int num_futexed_threads;
+
+ /* Array of futexed threads at the same address. */
+ futex_thread_t futexed_threads;
+
+ /* Hash value in the hash table. */
+ unsigned int hash_val;
+};
+
+/*
+ * Function: futex_init()
+ *
+ * Initialization of a new futex.
+ *
+ * Takes new futex and address arguments. Returns:
+ * FUTEX_RESOURCE_SHORTAGE - allocation of the hash table or the array of
+ * futex pointers has failed
+ * 0 - success
+ *
+ */
+int futex_init(futex_t futex, int *address);
+
+/*
+ * Function: futex_wake_one_thread()
+ *
+ * Wake one futex thread.
+ *
+ * Takes the futex and thread number in the array of futex threads arguments.
+ *
+ */
+void futex_wake_one_thread(futex_t 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 wake_all arguments. Meaning of wake_all is the same as
in
+ * futex_wake().
+ *
+ */
+void futex_cross_address_space_wake(futex_t futex, boolean_t wake_all);
+
+/*
+ * 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().
+ *
+ */
+void futex_wake_threads(futex_t futex, boolean_t wake_all);
+
+/*
+ * Function: futex_hash_table_init()
+ *
+ * Initialization of the hash table.
+ *
+ * Returns:
+ * FUTEX_RESOURCE_SHORTAGE - allocation of the hash table has failed
+ * 0 - success
+ *
+ */
+int futex_hash_table_init(void);
+
+/*
+ * Function: futex_hash()
+ *
+ * Generate a hash value.
+ *
+ * Takes the address argument. Returns hash value or 0 if hash table is NULL.
+ *
+ */
+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.
+ *
+ */
+futex_t 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:
+ * 1 - allocation of the new futex has failed
+ * FUTEX_RESOURCE_SHORTAGE - allocation of the hash table or the array of
+ * futex pointers has failed
+ * 0 - success
+ *
+ */
+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.
+ *
+ */
+void futex_hash_table_delete_futex(futex_t futex);
+
+/*
+ * Function: futex_thread_init()
+ *
+ * Initialization of the new futex thread.
+ *
+ * Takes the futex and the thread as an argument. Thread is updated in
+ * the function. Returns:
+ * FUTEX_RESOURCE_SHORTAGE - allocation of the thread or the array of
+ * thread pointers has failed
+ * FUTEX_MEMORY_ERROR - vm_map_lookup() has failed
+ * 0 - success
+ *
+ */
+int futex_thread_init(futex_t futex, futex_thread_t thread);
+
+#endif /* _KERN_FUTEX_I_H_ */
--
1.7.10.4
