[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(¤t_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
- [RFC] kern: simple futex for gnumach (version 8),
Marin Ramesa <=