[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[RFC] kern: simple futex for gnumach (version 5)
From: |
Marin Ramesa |
Subject: |
[RFC] kern: simple futex for gnumach (version 5) |
Date: |
Thu, 26 Dec 2013 14:30:10 +0100 |
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(¤t_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
- [RFC] kern: simple futex for gnumach (version 5),
Marin Ramesa <=