[RFC] kern: simple futex for gnumach (version 6)

[Marin Ramesa]

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