bug-hurd
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


From: Marin Ramesa
Subject: [RFC] kern: simple futex for gnumach (version 8)
Date: Sun, 29 Dec 2013 21:44:51 +0100

Futex waiters are now in a list and some bugs were fixed.

I think this is now ready for test. I have tested this with
malloc() and free() instead of kalloc() and kfree(), but
without vm_map_lookup() and assert_wait() since these functions
segfault on my machine with GDB.

Functions thread_sleep() and clear_wait() need to be tested if
they actually work paired this way. If somebody is willing to
do this please let me know, here's a short test program:

extern int futex_wait();
extern int futex_wake();
extern int thread_create();
extern void thread_start();

struct thread;
typedef struct thread *thread_t;

int e = 0;

void thread_function(void)
{
        futex_wait(&e, e);
}

int main(void)
{
        thread_t new_thread;
        thread_create(current_thread()->task, &new_thread);
        thread_start(new_thread, thread_function);
        return futex_wake(&e, 0);
}

All I need are the return values from main.

Thanks.

---
 Makefrag.am  |    2 +
 kern/futex.c |  398 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 kern/futex.h |  115 +++++++++++++++++
 3 files changed, 515 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..23fb4d4
--- /dev/null
+++ b/kern/futex.c
@@ -0,0 +1,398 @@
+/*
+ * 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>
+#include <kern/kalloc.h>
+#include <vm/vm_map.h>
+
+#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
+
+#define futex_list_for_each(array, entry, list)     \
+for (entry = &array[0]; entry != NULL;              \
+     entry = (typeof(entry))entry->list.next,       \
+     entry != &array[0])
+
+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. */
+       struct futex *futex_elements;
+};
+
+static struct futex_hash_table *futex_table = NULL; 
+static unsigned int futex_max_hash_val = 0;
+
+/*
+ * Function: futex_init()
+ *
+ * Initialization of a new futex.
+ * 
+ * Takes new futex, address and hash value arguments. Returns:
+ *     FUTEX_RESOURCE_SHORTAGE - allocation of the hash table or the array of
+ *                               futex pointers has failed
+ *     0 - success
+ *
+ */
+static int futex_init(struct futex *futex, int *address, unsigned int 
hash_val);
+
+/*
+ * Function: futex_wake_one_thread()
+ *
+ * Wake one futex thread.
+ * 
+ * Takes the futex as an argument. 
+ *
+ */
+static void futex_wake_one_thread(struct futex *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 offset arguments. 
+ *
+ */
+static void futex_cross_address_space_wake(struct futex *futex, vm_offset_t 
offset);
+
+/*
+ * 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(). 
+ *
+ */
+static void futex_wake_threads(struct futex *futex, boolean_t wake_all);
+
+/*
+ * Function: futex_hash()
+ *
+ * Generate a hash value. 
+ * 
+ * Takes the address argument. Returns hash value or 0 if hash table is NULL.
+ *
+ */
+static 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. 
+ *
+ */
+static struct futex *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:
+ *     FUTEX_RESOURCE_SHORTAGE - allocation of the hash table, array of
+ *                               futex pointers or the new futex has failed
+ *     0 - success 
+ *
+ */
+static 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. 
+ *
+ */
+static void futex_hash_table_delete_futex(struct futex *futex);
+
+static int futex_init(struct futex *futex, int *address, unsigned int hash_val)
+{
+       if (futex_table == NULL) {
+               if (futex_hash_table_setup() == FUTEX_RESOURCE_SHORTAGE) {
+                       return FUTEX_RESOURCE_SHORTAGE;
+               }
+       }
+
+       futex = (struct futex *)kalloc(sizeof(*futex));
+       futex_table->futex_elements = (struct futex 
*)kalloc((futex_max_hash_val + 1) * sizeof(futex));
+       //futex = (struct futex *)__builtin_malloc(sizeof(*futex));
+       //futex_table->futex_elements = (struct futex 
*)__builtin_malloc((futex_max_hash_val + 1) * sizeof(futex));     
+       if (futex_table->futex_elements == NULL || futex == NULL) 
+               return FUTEX_RESOURCE_SHORTAGE;
+
+       simple_lock_init(&futex->futex_wait_lock);
+
+       futex->address = address;
+
+       futex->hash_val = hash_val;
+
+       futex_table->futex_elements[hash_val] = *futex;
+       futex_table->size++;
+       
+       list_init(&futex->futex_list);
+       list_concat(&futex_table->futex_elements[0].futex_list, 
&futex->futex_list);
+               
+       return 0;       
+}
+
+int futex_wait(int *address, int value)
+{
+       struct futex *futex;
+       struct futex_waiter waiter; 
+
+       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) {
+                       
+                       waiter.thread = current_thread();
+                       
+                       kern_return_t kr;
+                       kr = vm_map_lookup(&current_map(), 
(vm_offset_t)futex->address, VM_PROT_READ, NULL, NULL, 
+                                               &waiter.offset, NULL, NULL);
+                       if (kr != KERN_SUCCESS) 
+                               return FUTEX_MEMORY_ERROR;
+                                       
+                       futex->futex_waiters = (struct futex_waiter 
*)kalloc((ARRAY_SIZE(futex->futex_waiters) + 1) * sizeof(&waiter));
+                       /*futex->futex_waiters = (struct futex_waiter *)
+                               
__builtin_malloc((ARRAY_SIZE(futex->futex_waiters) + 1) * sizeof(&waiter));*/   
                
+                       if (futex->futex_waiters == NULL)
+                               return FUTEX_RESOURCE_SHORTAGE;
+
+                       waiter.index = ARRAY_SIZE(futex->futex_waiters) - 1;
+
+                       /* Add the waiter to the futex. */
+                       futex->futex_waiters[ARRAY_SIZE(futex->futex_waiters) - 
1] = waiter;
+
+                       
list_init(&futex->futex_waiters[ARRAY_SIZE(futex->futex_waiters) - 
1].futex_waiters_list);
+                       
list_concat(&futex->futex_waiters[0].futex_waiters_list, 
+                               
&futex->futex_waiters[ARRAY_SIZE(futex->futex_waiters) - 1].futex_waiters_list);
+
+                       thread_sleep(futex, 
(simple_lock_t)&futex->futex_wait_lock, FALSE);
+
+                       /* Wait has been cleared in futex_wake_one_thread(). */
+                       
list_remove(&futex->futex_waiters[waiter.index].futex_waiters_list);
+                       kfree((vm_offset_t)&futex->futex_waiters[waiter.index], 
sizeof(&waiter));                       
+                       //__builtin_free(&futex->futex_waiters[waiter.index]);  
                
+                       return FUTEX_RESUMED_BY_WAKE;
+
+               } else {
+                       simple_unlock(&futex->futex_wait_lock);
+                       return FUTEX_NO_THREAD_SUSPENDED;
+               }
+
+       } else {
+               
+               int i = futex_hash_table_add_address(address); 
+
+               if (i != 0) return i;
+               
+               goto lookup;
+       }       
+}              
+
+int futex_wake(int *address, boolean_t wake_all)
+{
+       struct futex *futex;
+       
+       futex = futex_hash_table_lookup_address(address);
+
+       if (futex != NULL) {
+
+               simple_lock(&futex->futex_wait_lock);
+
+               futex_wake_threads(futex, wake_all);
+
+               simple_unlock(&futex->futex_wait_lock);
+
+               return FUTEX_SOME_NUMBER_RESUMED;
+
+       } else
+               return FUTEX_NO_THREAD;
+}      
+
+static void futex_wake_one_thread(struct futex *futex, int thread_num)
+{
+       clear_wait(futex->futex_waiters[thread_num].thread, THREAD_AWAKENED, 
FALSE);
+}                    
+
+static void futex_cross_address_space_wake(struct futex *futex, vm_offset_t 
offset)
+{
+       futex_list_for_each(futex_table->futex_elements, futex, futex_list) {
+
+               simple_lock(&futex->futex_wait_lock);
+
+               struct futex_waiter *waiter;
+
+               futex_list_for_each(futex->futex_waiters, waiter, 
futex_waiters_list) {
+
+                       if (waiter->offset == offset) {
+                       
+                               futex_wake_one_thread(futex, waiter->index);
+                               
+                               if 
(list_empty(&futex->futex_waiters[0].futex_waiters_list)) {
+                                       simple_unlock(&futex->futex_wait_lock);
+                                       futex_hash_table_delete_futex(futex);
+                                       return;                         
+                               }
+                       }
+               }
+       
+               simple_unlock(&futex->futex_wait_lock);         
+       }
+}
+
+static void futex_wake_threads(struct futex *futex, boolean_t wake_all)
+{
+       if (wake_all) {
+               
+               struct futex_waiter *waiter;
+
+               futex_list_for_each(futex->futex_waiters, waiter, 
futex_waiters_list)
+                       futex_cross_address_space_wake(futex, waiter->offset); 
+
+       } else 
+               futex_cross_address_space_wake(futex, 
futex->futex_waiters[ARRAY_SIZE(futex->futex_waiters) - 1].offset);
+}
+
+int futex_hash_table_setup(void)
+{
+       futex_table = (struct futex_hash_table *)kalloc(sizeof(*futex_table));
+       //futex_table = (struct futex_hash_table 
*)__builtin_malloc(sizeof(*futex_table));      
+       if (futex_table == NULL)
+               return FUTEX_RESOURCE_SHORTAGE;
+
+       simple_lock_init(&futex_table->futex_hash_table_lock);
+
+       futex_table->size = 0;
+
+       return 0;
+}
+
+static unsigned int futex_hash(int *address)
+{
+       unsigned int hash_val = (unsigned int)address;
+
+       if (futex_table != NULL) {
+               unsigned int power_of_two_size = 1, i;
+               for (i = 1; i < futex_table->size; i++)
+                       power_of_two_size *= 2;
+               unsigned int ret = hash_val & power_of_two_size; 
+               if (ret > futex_max_hash_val)
+                       futex_max_hash_val = ret;               
+               return ret;
+       } else
+               return 0;
+}
+
+static struct futex *futex_hash_table_lookup_address(int *address)
+{
+       struct futex *futex;
+
+       if (futex_table == NULL) {
+               return NULL;
+       }
+
+       simple_lock(&futex_table->futex_hash_table_lock);
+
+       futex_list_for_each(futex_table->futex_elements, futex, futex_list) {
+
+               if (address == futex->address) {
+                       simple_unlock(&futex_table->futex_hash_table_lock);
+                       return futex;
+
+               }
+       }
+
+       simple_unlock(&futex_table->futex_hash_table_lock);
+
+       return NULL;
+}
+
+static int futex_hash_table_add_address(int *address)
+{
+       struct futex *new_futex = NULL;
+
+       unsigned int hash_val = futex_hash(address);
+
+       if (futex_table != NULL) 
+               simple_lock(&futex_table->futex_hash_table_lock);
+               
+       int ret;
+
+       ret = futex_init(new_futex, address, hash_val);
+       if (ret != 0) {
+               if (futex_table != NULL)
+                       simple_unlock(&futex_table->futex_hash_table_lock);
+               return ret;
+       }
+
+       /* futex_table is non-NULL because of the call to futex_init(). */
+       if (simple_lock_try(&futex_table->futex_hash_table_lock))
+               simple_unlock(&futex_table->futex_hash_table_lock);
+
+       return 0;
+}      
+
+static void futex_hash_table_delete_futex(struct futex *futex)
+{
+       simple_lock(&futex_table->futex_hash_table_lock);
+
+       list_remove(&futex->futex_list);
+
+       kfree((vm_offset_t)futex, sizeof(*futex));
+       kfree((vm_offset_t)&futex_table->futex_elements[futex->hash_val], 
sizeof(futex));
+       //__builtin_free(futex);
+       //__builtin_free(&futex_table->futex_elements[futex->hash_val]);        
+
+       futex_table->size--;
+
+       if (futex_table->size == 0) {
+               simple_unlock(&futex_table->futex_hash_table_lock);
+               kfree((vm_offset_t)futex_table, sizeof(*futex_table));
+               //__builtin_free(futex_table);          
+               futex_table = NULL;
+               return;
+       }
+
+       simple_unlock(&futex_table->futex_hash_table_lock);
+}
diff --git a/kern/futex.h b/kern/futex.h
new file mode 100644
index 0000000..faa8fda
--- /dev/null
+++ b/kern/futex.h
@@ -0,0 +1,115 @@
+/*
+ * 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>
+#include <kern/lock.h>
+#include <kern/list.h>
+#include <kern/thread.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
+
+struct futex_waiter {
+
+       /* Futex waiters list. */
+       struct list futex_waiters_list;
+
+       /* Index in the futex. */
+       unsigned int index;
+
+       /* Associated thread. */
+       thread_t thread;
+       
+       /* Offset from the (task map, futex address) value pair. */
+       vm_offset_t offset;
+};
+
+struct futex {
+       /* List of futexes. */  
+       struct list futex_list;
+
+       /* Futex lock. */
+       decl_simple_lock_data( , futex_wait_lock);
+
+       /* Futex address. */
+       int *address;
+
+       /* Array of futex waiters at the same address. */
+       struct futex_waiter *futex_waiters;
+
+       /* Hash value in the hash table. */
+       unsigned int hash_val;
+};
+
+/*
+ * 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, 
array of futex 
+ *                               pointers or array of futex waiters pointers 
has failed
+ *     FUTEX_MEMORY_ERROR - vm_map_lookup() 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);
+
+/*
+ * Function: futex_hash_table_setup()
+ *
+ * Setup of the global hash table.
+ * 
+ * Returns:
+ *     FUTEX_RESOURCE_SHORTAGE - allocation of the hash table has failed
+ *     0 - success
+ *
+ */
+int futex_hash_table_setup(void);
+
+#endif /* _KERN_FUTEX_H_ */
-- 
1.7.10.4




reply via email to

[Prev in Thread] Current Thread [Next in Thread]