[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[RFC] Simple futex for gnumach (version 2)
From: |
Marin Ramesa |
Subject: |
[RFC] Simple futex for gnumach (version 2) |
Date: |
Sat, 21 Dec 2013 14:09:53 +0100 |
This is a simple futex implementation with a hash table, vm_map lookup, futex
wake that wakes futexes at the same offset, dynamic allocation and a per-process
mutex for the hash table.
---
Makefrag.am | 2 +
kern/futex.c | 255 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
kern/futex.h | 114 ++++++++++++++++++++++++++
3 files changed, 371 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..9b743fe
--- /dev/null
+++ b/kern/futex.c
@@ -0,0 +1,255 @@
+/*
+ * Copyright (c) 2013 Marin Ramesa
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/*
+ * Fast userspace locking
+ *
+ */
+
+#include <kern/futex.h>
+#include <kern/kalloc.h>
+
+static futex_hash_table_t table = NULL;
+static unsigned int prev_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 a number
+ * (specified by the argument value) of threads waiting for a change of value
+ * at a given address (threads that are in FUTEX_WAIT).
+ *
+ * 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_NUMBER_RESUMED - value threads have been resumed by FUTEX_WAKE
+ * FUTEX_NO_THREAD - FUTEX_WAKE did not found a suspended thread at the
passed address
+ * FUTEX_EXISTS - futex already exists at the new address
+ * FUTEX_MEMORY_ERROR - memory error
+ * FUTEX_UNKNOWN_OPERATION - unknown operation
+ *
+ */
+int futex(int *address, int value, int operation)
+{
+ switch (operation) {
+ case FUTEX_WAIT:
+ return futex_wait(address, value);
+ break;
+ case FUTEX_WAKE:
+ return futex_wake(address, value);
+ break;
+ default:
+ return FUTEX_UNKNOWN_OPERATION;
+ }
+}
+
+int futex_init(int *address, futex_t futex, futex_hash_table_t hash_table,
unsigned int hash_val)
+{
+ simple_lock_init(&futex->futex_wait_lock);
+ if (hash_table == NULL) {
+ hash_table = futex_hash_table_init(INITIAL_HASH_TABLE_SIZE,
current_thread()->task);
+ if (hash_table == NULL)
+ return FUTEX_NO_MEMORY;
+ }
+ if (hash_table->size == hash_table->num_of_futexes)
+ if ((hash_table->futex_elements =
(futex_t)kalloc((hash_table->size + 1) * sizeof(futex_t))) == NULL)
+ return FUTEX_NO_MEMORY;
+ futex->address = address;
+ futex->num_futexed_threads = 0;
+ futex->next_futex = &(hash_table->futex_elements[hash_val]);
+ futex->prev_futex = &(hash_table->futex_elements[prev_hash_val]);
+ 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))
+ return FUTEX_MEMORY_ERROR;
+ return 0;
+}
+
+int futex_wait(int *address, int value)
+{
+ futex_t futex;
+
+ lookup:
+
+ futex = futex_hash_table_lookup_address(table, address);
+
+ if (futex != NULL) {
+
+ simple_lock(&futex->futex_wait_lock);
+
+ /* If the value after the lock is still the same. */
+ if (*address == value) {
+
+ /* Add the thread to the futex. */
+ if ((futex->futexed_threads =
(thread_t)kalloc((futex->num_futexed_threads + 1) * sizeof(thread_t))) == NULL)
+ return FUTEX_NO_MEMORY;
+
+ futex->futexed_threads[++futex->num_futexed_threads] =
*(current_thread());
+
+ goto suspend;
+ } else goto no_suspend;
+
+
+ } else {
+
+ int i = futex_hash_table_add_address(table, address);
+
+ if (i == 1) return FUTEX_NO_MEMORY;
+ if (i == 2) return FUTEX_EXISTS;
+ if (i != 0) return i;
+
+ goto lookup;
+
+ }
+
+ suspend:
+ simple_unlock(&futex->futex_wait_lock);
+ thread_suspend(current_thread());
+ return FUTEX_RESUMED_BY_WAKE;
+
+ no_suspend:
+ simple_unlock(&futex->futex_wait_lock);
+ return FUTEX_NO_THREAD_SUSPENDED;
+}
+
+int futex_wake(int *address, int thread_num)
+{
+ futex_t futex;
+
+ unsigned int hash_val = futex_hash(table, address);
+
+ for (futex = &(table->futex_elements[hash_val]); futex != NULL; futex =
futex->next_futex)
+ if (futex->offset == futex->next_futex->offset)
+ futex_wake(futex->next_futex->address, thread_num);
+
+ for (futex = &(table->futex_elements[hash_val]); futex != NULL; futex =
futex->prev_futex)
+ if (futex->offset == futex->prev_futex->offset)
+ futex_wake(futex->prev_futex->address, thread_num);
+
+ futex = futex_hash_table_lookup_address(table, address);
+
+ if (futex != NULL) {
+ if (thread_num > futex->num_futexed_threads)
+ thread_num = futex->num_futexed_threads - 1;
+ int i;
+ vm_size_t size_free = 0;
+ for (i = 0; i < thread_num; i++) {
+ thread_resume(&(futex->futexed_threads[i]));
+ futex->num_futexed_threads--;
+ size_free++;
+ }
+ kfree((vm_offset_t)&(futex->futexed_threads[i]), size_free *
sizeof(thread_t));
+
+ if (futex->num_futexed_threads == 0)
+ futex_hash_table_delete_futex(futex, table, address);
+
+ return FUTEX_NUMBER_RESUMED;
+ } else
+ return FUTEX_NO_THREAD;
+}
+
+futex_hash_table_t futex_hash_table_init(size_t size, task_t task)
+{
+ if (current_thread()->task == task) {
+
+ futex_hash_table_t new_table;
+
+ simple_lock_init(&new_table->futex_hash_table_lock);
+
+ if ((new_table = (futex_hash_table_t)kalloc(sizeof(struct
futex_hash_table))) == NULL)
+ return NULL;
+
+ if ((new_table->futex_elements = (futex_t)kalloc(size *
sizeof(futex_t))) == NULL)
+ return NULL;
+
+ new_table->size = size;
+
+ new_table->task = task;
+
+ return new_table;
+ } else
+ return NULL;
+}
+
+unsigned int futex_hash(futex_hash_table_t hash_table, int *address)
+{
+ unsigned int hash_val = 0;
+
+ hash_val = (unsigned int)address + (hash_val << 5) - hash_val;
+
+ return hash_val % hash_table->size;
+}
+
+futex_t futex_hash_table_lookup_address(futex_hash_table_t hash_table, int
*address)
+{
+ futex_t futex;
+
+ simple_lock(&hash_table->futex_hash_table_lock);
+
+ unsigned int hash_val = futex_hash(hash_table, address);
+
+ for (futex = &(hash_table->futex_elements[hash_val]); futex != NULL;
futex = futex->next_futex)
+ if (address == futex->address) {
+ simple_unlock(&hash_table->futex_hash_table_lock);
+ return futex;
+ }
+
+ for (futex = &(hash_table->futex_elements[hash_val]); futex != NULL;
futex = futex->prev_futex)
+ if (address == futex->address) {
+ simple_unlock(&hash_table->futex_hash_table_lock);
+ return futex;
+ }
+
+ simple_unlock(&hash_table->futex_hash_table_lock);
+
+ return NULL;
+}
+
+int futex_hash_table_add_address(futex_hash_table_t hash_table, int *address)
+{
+ futex_t new_futex;
+ futex_t current_futex;
+
+ simple_lock(&hash_table->futex_hash_table_lock);
+
+ unsigned int hash_val = futex_hash(hash_table, address);
+
+ if ((new_futex = (futex_t)kalloc(sizeof(futex_t))) == NULL) {
+ simple_unlock(&hash_table->futex_hash_table_lock);
+ return 1;
+ }
+
+ current_futex = futex_hash_table_lookup_address(hash_table, address);
+ if (current_futex != NULL) {
+ simple_unlock(&hash_table->futex_hash_table_lock);
+ return 2;
+ }
+
+ int ret;
+
+ if ((ret = futex_init(address, new_futex, hash_table, hash_val)) != 0) {
+ simple_unlock(&hash_table->futex_hash_table_lock);
+ return ret;
+ }
+
+ hash_table->futex_elements[hash_val] = *new_futex;
+
+ prev_hash_val = hash_val;
+
+ simple_unlock(&hash_table->futex_hash_table_lock);
+
+ return 0;
+}
+
+void futex_hash_table_delete_futex(futex_t futex, futex_hash_table_t
hash_table, int *address)
+{
+ futex_t new_next_futex = futex->next_futex;
+
+ simple_lock(&hash_table->futex_hash_table_lock);
+
+ unsigned int hash_val = futex_hash(hash_table, address);
+
+ hash_table->futex_elements[hash_val].prev_futex->next_futex =
new_next_futex;
+
+ kfree((vm_offset_t)&(hash_table->futex_elements[hash_val]),
sizeof(futex_t));
+
+ simple_unlock(&hash_table->futex_hash_table_lock);
+}
diff --git a/kern/futex.h b/kern/futex.h
new file mode 100644
index 0000000..4a0640d
--- /dev/null
+++ b/kern/futex.h
@@ -0,0 +1,114 @@
+/*
+ * Copyright (c) 2013 Marin Ramesa
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#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 futex operations. */
+#define FUTEX_WAIT 0
+#define FUTEX_WAKE 1
+
+/* Definitions for return values. */
+#define FUTEX_RESUMED_BY_WAKE 0
+#define FUTEX_NO_THREAD_SUSPENDED -1
+#define FUTEX_NUMBER_RESUMED 1
+#define FUTEX_NO_THREAD -2
+#define FUTEX_EXISTS -3
+#define FUTEX_MEMORY_ERROR -4
+#define FUTEX_UNKNOWN_OPERATION -5
+
+/* Initial size of the hash table. */
+#define INITIAL_HASH_TABLE_SIZE 24
+
+#define FUTEX_NO_MEMORY -6
+
+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;
+};
+
+struct futex_hash_table {
+
+ /* Futex hash table lock. */
+ decl_simple_lock_data( , futex_hash_table_lock);
+
+ /* Size of the hash table. */
+ size_t size;
+
+ /* Task to which the hash table belongs. */
+ task_t task;
+
+ /* Number of futexes in the hash table. */
+ unsigned int num_of_futexes;
+
+ /* Array of futexes. */
+ futex_t futex_elements;
+};
+
+typedef struct futex_hash_table *futex_hash_table_t;
+
+extern int futex(int *address, int value, int operation);
+int futex_init(int *address, futex_t futex, futex_hash_table_t hash_table,
unsigned int hash_val);
+int futex_wait(int *address, int value);
+int futex_wake(int *address, int thread_num);
+futex_hash_table_t futex_hash_table_init(size_t size, task_t task);
+unsigned int futex_hash(futex_hash_table_t hash_table, int *address);
+futex_t futex_hash_table_lookup_address(futex_hash_table_t hash_table, int
*address);
+int futex_hash_table_add_address(futex_hash_table_t hash_table, int *address);
+void futex_hash_table_delete_futex(futex_t futex, futex_hash_table_t
hash_table, int *address);
+
+#endif /* _KERN_FUTEX_H */
--
1.8.1.4
- [RFC] Simple futex for gnumach (version 2),
Marin Ramesa <=