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

[Marin Ramesa]

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(&current_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