I noticed some bugs. I'm sending a fixed patch. The prevoius version is here:
http://lists.gnu.org/archive/html/bug-hurd/2013-12/msg00493.html
---
Makefrag.am | 2 +
kern/futex.c | 364 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
kern/futex.h | 110 ++++++++++++++++++
3 files changed, 476 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..3e244f0
--- /dev/null
+++ b/kern/futex.c
@@ -0,0 +1,364 @@
+/*
+ * Copyright (c) 2013 Marin Ramesa
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/*
+ * Fast userspace locking
+ *
+ */
+
+#include <kern/futex.h>
+#include <kern/kalloc.h>
+
+static futex_hash_table_t table = NULL;
+static unsigned int prev_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 a number
+ * (specified by the argument value) of threads waiting for a change of value
+ * at a given address (threads that are in FUTEX_WAIT).
+ *
+ * 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 - value threads have been resumed by
FUTEX_WAKE
+ * FUTEX_NO_THREAD - FUTEX_WAKE did not found a suspended thread at the
passed address
+ * FUTEX_EXISTS - futex already exists at the new address
+ * FUTEX_MEMORY_ERROR - memory error
+ * FUTEX_UNKNOWN_OPERATION - unknown operation
+ * FUTEX_RESOURCE_SHORTAGE - no virtual memory or the mutex is not
per-process
+ *
+ */
+int futex(int *address, int value, int operation)
+{
+ switch (operation) {
+ case FUTEX_WAIT:
+ return futex_wait(address, value);
+ case FUTEX_WAKE:
+ return futex_wake(address, value);
+ default:
+ return FUTEX_UNKNOWN_OPERATION;
+ }
+}
+
+int futex_init(int *address, futex_t futex, futex_hash_table_t hash_table,
unsigned int hash_val)
+{
+ simple_lock_init(&futex->futex_wait_lock);
+
+ if (hash_table == NULL) {
+ hash_table = futex_hash_table_init(INITIAL_HASH_TABLE_SIZE,
current_thread()->task);
+ if (hash_table == NULL)
+ return FUTEX_RESOURCE_SHORTAGE;
+ }
+
+ if ((hash_table->futex_elements =
+ (futex_t)kalloc((hash_table->size + 1) * sizeof(futex_t))) ==
NULL) {
+
+ return FUTEX_RESOURCE_SHORTAGE;
+
+ }
+
+ futex->address = address;
+ futex->num_futexed_threads = 0;
+ futex->next_futex = &(hash_table->futex_elements[hash_val]);
+ futex->prev_futex = &(hash_table->futex_elements[prev_hash_val]);
+
+ 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)) {
+ hash_table->size++;
+ unsigned int temp_hash_val = futex_hash(hash_table, address);
+
kfree((vm_offset_t)&(hash_table->futex_elements[temp_hash_val]),
sizeof(futex_t));
+ hash_table->size--;
+ return FUTEX_MEMORY_ERROR;
+ }
+
+ hash_table->size++;
+
+ return 0;
+}
+
+int futex_wait(int *address, int value)
+{
+ futex_t futex;
+ boolean_t per_process_mutex;
+
+ lookup:
+
+ per_process_mutex = TRUE;
+
+ futex = futex_hash_table_lookup_address(table, address,
&per_process_mutex);
+
+ if (per_process_mutex == FALSE)
+ return FUTEX_RESOURCE_SHORTAGE;
+
+ 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. */
+ if ((futex->futexed_threads =
+
(thread_t)kalloc((futex->num_futexed_threads+1)*sizeof(thread_t))) == NULL) {
+ simple_unlock(&futex->futex_wait_lock);
+ return FUTEX_RESOURCE_SHORTAGE;
+ }
+
+ futex->futexed_threads[++futex->num_futexed_threads] =
*(current_thread());
+
+ goto suspend;
+ } else
+ goto no_suspend;
+
+ } else {
+
+ int i = futex_hash_table_add_address(table, address);
+
+ if (i == 1) return FUTEX_RESOURCE_SHORTAGE;
+ if (i == 2) return FUTEX_EXISTS;
+ if (i != 0) return i;
+
+ goto lookup;
+
+ }
+
+ suspend:
+ simple_unlock(&futex->futex_wait_lock);
+ thread_suspend(current_thread());
+ return FUTEX_RESUMED_BY_WAKE;
+
+ no_suspend:
+ simple_unlock(&futex->futex_wait_lock);
+ return FUTEX_NO_THREAD_SUSPENDED;
+}
+
+int futex_wake(int *address, int thread_num)
+{
+ futex_t futex;
+
+ unsigned int hash_val = futex_hash(table, address);
+
+ for (futex = &(table->futex_elements[hash_val]); futex != NULL;
+ futex = futex->next_futex) {
+
+ if ((*(futex->offset) == *(futex->next_futex->offset)) &&
+ (futex->object == futex->next_futex->object)) {
+
+ futex_wake(futex->next_futex->address, thread_num);
+
+ }
+ }
+
+ for (futex = &(table->futex_elements[hash_val]); futex != NULL;
+ futex = futex->prev_futex) {
+
+ if ((*(futex->offset) == *(futex->prev_futex->offset)) &&
+ (futex->object == futex->prev_futex->object)) {
+
+ futex_wake(futex->prev_futex->address, thread_num);
+
+ }
+ }
+
+ boolean_t per_process_mutex = TRUE;
+
+ futex = futex_hash_table_lookup_address(table, address,
&per_process_mutex);
+
+ if (per_process_mutex == FALSE)
+ return FUTEX_RESOURCE_SHORTAGE;
+
+ if (futex != NULL) {
+
+ /* If the number of threads to be awakened is greater then the
number
+ * of threads in the futex, wake all.
+ */
+ if (thread_num > futex->num_futexed_threads)
+ thread_num = futex->num_futexed_threads - 1;
+ int i;
+ vm_size_t size_free = 0;
+ for (i = 0; i < thread_num; i++) {
+ thread_resume(&(futex->futexed_threads[i]));
+ futex->num_futexed_threads--;
+ size_free++;
+ }
+ kfree((vm_offset_t)&(futex->futexed_threads[i]), size_free *
sizeof(thread_t));
+
+ if (futex->num_futexed_threads == 0)
+ if (futex_hash_table_delete_futex(futex, table,
address) == -1)
+ return FUTEX_RESOURCE_SHORTAGE;
+
+ return FUTEX_SOME_NUMBER_RESUMED;
+ } else
+ return FUTEX_NO_THREAD;
+}
+
+futex_hash_table_t futex_hash_table_init(size_t size, task_t task)
+{
+ /* If we're still in the same task. */
+ if (current_thread()->task == task) {
+
+ futex_hash_table_t new_table;
+
+ simple_lock_init(&new_table->futex_hash_table_lock);
+
+ if ((new_table =
+ (futex_hash_table_t)kalloc(sizeof(struct
futex_hash_table))) == NULL)
+ return NULL;
+
+ if ((new_table->futex_elements =
+ (futex_t)kalloc(size * sizeof(futex_t))) == NULL)
+ return NULL;
+
+ new_table->size = size;
+
+ new_table->task = task;
+
+ return new_table;
+ } else
+ return NULL;
+}
+
+unsigned int futex_hash(futex_hash_table_t hash_table, int *address)
+{
+ unsigned int hash_val = 0;
+
+ hash_val = (unsigned int)address + (hash_val << 5) - hash_val;
+
+ return hash_val % hash_table->size;
+}
+
+futex_t futex_hash_table_lookup_address(futex_hash_table_t hash_table, int
*address,
+ boolean_t *per_process_mutex)
+{
+ futex_t futex;
+
+ if (current_thread()->task == hash_table->task) {
+
+ simple_lock(&hash_table->futex_hash_table_lock);
+
+ unsigned int hash_val = futex_hash(hash_table, address);
+
+ for (futex = &(hash_table->futex_elements[hash_val]); futex !=
NULL;
+ futex = futex->next_futex) {
+
+ if (address == futex->address) {
+
simple_unlock(&hash_table->futex_hash_table_lock);
+ return futex;
+
+ }
+ }
+
+ for (futex = &(hash_table->futex_elements[hash_val]); futex !=
NULL;
+ futex = futex->prev_futex) {
+
+ if (address == futex->address) {
+
simple_unlock(&hash_table->futex_hash_table_lock);
+ return futex;
+
+ }
+ }
+
+ simple_unlock(&hash_table->futex_hash_table_lock);
+
+ } else
+ *per_process_mutex = FALSE;
+
+ return NULL;
+}
+
+int futex_hash_table_add_address(futex_hash_table_t hash_table, int *address)
+{
+ futex_t new_futex;
+ futex_t current_futex;
+
+ simple_lock(&hash_table->futex_hash_table_lock);
+
+ unsigned int hash_val = futex_hash(hash_table, address);
+
+ if ((new_futex = (futex_t)kalloc(sizeof(futex_t))) == NULL) {
+ simple_unlock(&hash_table->futex_hash_table_lock);
+ return 1;
+ }
+
+ boolean_t per_process_mutex = TRUE;
+
+ current_futex = futex_hash_table_lookup_address(hash_table, address,
&per_process_mutex);
+ if (current_futex != NULL) {
+ simple_unlock(&hash_table->futex_hash_table_lock);
+ return 2;
+ }
+ if (per_process_mutex == FALSE) return 1;
+
+ int ret;
+
+ if ((ret = futex_init(address, new_futex, hash_table, hash_val)) != 0) {
+ simple_unlock(&hash_table->futex_hash_table_lock);
+ return ret;
+ }
+
+ hash_table->futex_elements[hash_val] = *new_futex;
+
+ prev_hash_val = hash_val;
+
+ simple_unlock(&hash_table->futex_hash_table_lock);
+
+ return 0;
+}
+
+int futex_hash_table_delete_futex(futex_t futex, futex_hash_table_t
hash_table, int *address)
+{
+ if (current_thread()->task == hash_table->task) {
+
+ /* New next futex in queue. */
+ futex_t new_next_futex = futex->next_futex;
+
+ simple_lock(&hash_table->futex_hash_table_lock);
+
+ unsigned int hash_val = futex_hash(hash_table, address);
+
+ hash_table->futex_elements[hash_val].prev_futex->next_futex =
new_next_futex;
+
+ /* New previous futex of the new next futex in queue. */
+
hash_table->futex_elements[hash_val].prev_futex->next_futex->prev_futex =
+ hash_table->futex_elements[hash_val].prev_futex;
+
+ kfree((vm_offset_t)&(hash_table->futex_elements[hash_val]),
sizeof(futex_t));
+
+ hash_table->size--;
+
+ if (hash_table->size == 0) {
+ kfree((vm_offset_t)hash_table, sizeof(struct
futex_hash_table));
+ hash_table = NULL;
+ }
+
+ simple_unlock(&hash_table->futex_hash_table_lock);
+
+ return 0;
+
+ } else
+ return -1;
+}
diff --git a/kern/futex.h b/kern/futex.h
new file mode 100644
index 0000000..29b9993
--- /dev/null
+++ b/kern/futex.h
@@ -0,0 +1,110 @@
+/*
+ * Copyright (c) 2013 Marin Ramesa
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#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 futex operations. */
+#define FUTEX_WAIT 0
+#define FUTEX_WAKE 1
+
+/* Definitions for return values. */
+#define FUTEX_RESUMED_BY_WAKE 0
+#define FUTEX_NO_THREAD_SUSPENDED -1
+#define FUTEX_SOME_NUMBER_RESUMED 1
+#define FUTEX_NO_THREAD -2
+#define FUTEX_EXISTS -3
+#define FUTEX_MEMORY_ERROR -4
+#define FUTEX_UNKNOWN_OPERATION -5
+#define FUTEX_RESOURCE_SHORTAGE -6
+
+/* Initial size of the hash table. */
+#define INITIAL_HASH_TABLE_SIZE 8
+
+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;
+};
+
+struct futex_hash_table {
+
+ /* Futex hash table lock. */
+ decl_simple_lock_data( , futex_hash_table_lock);
+
+ /* Size of the hash table. */
+ size_t size;
+
+ /* Task to which the hash table belongs. */
+ task_t task;
+
+ /* Array of futexes. */
+ futex_t futex_elements;
+};
+
+typedef struct futex_hash_table *futex_hash_table_t;
+
+extern int futex(int *address, int value, int operation);
+int futex_init(int *address, futex_t futex, futex_hash_table_t hash_table,
unsigned int hash_val);
+int futex_wait(int *address, int value);
+int futex_wake(int *address, int thread_num);
+futex_hash_table_t futex_hash_table_init(size_t size, task_t task);
+unsigned int futex_hash(futex_hash_table_t hash_table, int *address);
+futex_t futex_hash_table_lookup_address(futex_hash_table_t hash_table, int
*address, boolean_t *per_process_mutex);
+int futex_hash_table_add_address(futex_hash_table_t hash_table, int *address);
+int futex_hash_table_delete_futex(futex_t futex, futex_hash_table_t
hash_table, int *address);
+
+#endif /* _KERN_FUTEX_H */
--
1.8.1.4
