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 7)


From: Marin Ramesa
Subject: [RFC] kern: simple futex for gnumach (version 7)
Date: Sat, 28 Dec 2013 21:05:02 +0100

Typedefs were removed. Static variables have been prefixed with futex.
Code now uses the list module, but I have not been able to use 
list_for_each_entry(), GCC seems to optimize the loop away when there
is one futex in the list. Hash table init is now a public function and
renamed to *setup. Statements with side effects have been removed from
conditional expressions. Sizeof is now used on variables. Futexed threads
have been renamed to futex waiters and the structure has been modified to
exclude unnecessary data. Unnecessary gotos have been removed. New futex
waiter is now allocated on the stack. Function thread_sleep() is now used
paired with clear_wait(). New macro ARRAY_SIZE() has been defined to replace
the usage of number of threads variable. Generating a hash value is now done
differently. The call to vm_map_lookup() has been modifed to exclude
unnecessary data. Futex structure is now in the public header. Function
futex_cross_address_space_wake() has been rewriten and called now from
futex_wake_threads(). There is no difference now beetwen an ordinary and
cross address space wake. The file futex_i.h has been removed and static
declarations of non-public functions are now in the .c file.

---
 Makefrag.am  |    2 +
 kern/futex.c |  385 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 kern/futex.h |  107 ++++++++++++++++
 3 files changed, 494 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..45f2cff
--- /dev/null
+++ b/kern/futex.c
@@ -0,0 +1,385 @@
+/*
+ * 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]))
+
+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 and thread number 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 or array of
+ *                               futex pointers 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));
+       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))*sizeof(&waiter));
+                       if (futex->futex_waiters == NULL)
+                               return FUTEX_RESOURCE_SHORTAGE;
+
+                       /* Add the waiter to the futex. */
+                       
futex->futex_waiters[ARRAY_SIZE(futex->futex_waiters)-1] = waiter;
+
+                       thread_sleep(futex, 
(simple_lock_t)&futex->futex_wait_lock, FALSE);
+
+                       /* Wait has been cleared in futex_wake_one_thread(). */
+                       
kfree((vm_offset_t)&futex->futex_waiters[ARRAY_SIZE(futex->futex_waiters)-1], 
sizeof(&waiter));                 
+                       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)
+{
+       for (futex = &futex_table->futex_elements[0]; 
+            futex != NULL;
+            futex = (struct futex *)futex->futex_list.next,
+            futex != &futex_table->futex_elements[0]) {
+
+               simple_lock(&futex->futex_wait_lock);
+
+               int i;
+
+               for (i = 0; i < ARRAY_SIZE(futex->futex_waiters); i++) {
+
+                       if (*futex->futex_waiters[i].offset == offset) {
+                       
+                               futex_wake_one_thread(futex, i);
+                               
+                               if (ARRAY_SIZE(futex->futex_waiters) == 0) {
+                                       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) {
+               int i;
+               for (i = 0; i < ARRAY_SIZE(futex->futex_waiters); i++)
+                       futex_cross_address_space_wake(futex, 
*futex->futex_waiters[i].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));
+       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 = 0;
+
+       hash_val = (unsigned int)address + (hash_val << 5) - hash_val;
+
+       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);
+
+       for (futex = &futex_table->futex_elements[0]; 
+            futex != NULL;
+            futex = (struct futex *)futex->futex_list.next,
+            futex != &futex_table->futex_elements[0]) {
+
+               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));
+       
+       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));
+               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..7a768be
--- /dev/null
+++ b/kern/futex.h
@@ -0,0 +1,107 @@
+/*
+ * 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 {
+
+       thread_t thread;
+       
+       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. If there is a futex
+ * waiter with the same offset, it's also 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]