This is a preliminary patch, a try at implementation of fast
userspace locking in gnumach. This futex implementation defines
only two operations: FUTEX_WAIT and FUTEX_WAKE. FUTEX_WAIT uses
gnumach's simple locks to atomically check for a change of
value at a given address, and if the value after the lock is
still the same it uses thread_suspend() to put the current thread
to sleep. FUTEX_WAIT doesn't support sleeping time intervals for
threads, so a thread must be awakened by FUTEX_WAKE. FUTEX_WAKE
checks the futex at a given address and uses gnumach's
thread_resume() to awake a number of sleeping threads
There are a number of possible problems with this patch. It only
allows for 128 addresses to be tracked, each having a maximum number
of 128 sleeping threads. This is for testing purposes only - I
will try to make this number unlimited in principle. Next, it
does not support time sleeping intervals, so threads must be
awakened by FUTEX_WAKE. Furthermore, it does not undefine already
defined futexes at the given address when all threads have been
awakened, so futexes stay open for suspension of new threads.
Please, comment on this patch. I did not yet test this. I'm having
some problems running a patched gnumach.
---
Makefrag.am | 2 +
kern/futex.c | 166 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
kern/futex.h | 58 +++++++++++++++++++++
3 files changed, 226 insertions(+)
create mode 100644 kern/futex.c
create mode 100644 kern/futex.h
diff --git a/Makefrag.am b/Makefrag.am
index bb08972..4bc0fdd 100644
--- a/Makefrag.am
+++ b/Makefrag.am
@@ -139,6 +139,8 @@ libkernel_a_SOURCES += \
kern/eventcount.c \
kern/eventcount.h \
kern/exception.c \
+ 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..aba7fb1
--- /dev/null
+++ b/kern/futex.c
@@ -0,0 +1,166 @@
+/*
+ * 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/lock.h>
+#include <kern/printf.h>
+#include <kern/futex.h>
+
+/* Number of futexes. */
+static unsigned int num_futexes = 0;
+
+/* Array of futexes. */
+static ftx_t futexes[FUTEX_MAX];
+
+/*
+ * When operation equals FUTEX_WAIT, this is a method for a thread to wait for
a
+ * change of value at a given address. FUTEX_WAIT ignores the argument
thread_num.
+ * Returns 0 if thread has been resumed by FUTEX_WAKE, and -1 if the value at
the
+ * address has been changed.
+ *
+ * When operation equals FUTEX_WAKE, this is a method for waking up a number
+ * (specified by the argument thread_num) of threads waiting for a change of
value
+ * at a given address (threads that are in FUTEX_WAIT).
+ *
+ * Return values:
+ * 0 - thread has been resumed by FUTEX_WAKE
+ * -1 - value at the address has been changed while inside FUTEX_WAIT and
no
+ * thread has been suspended
+ * 1 - thread_num threads have been resumed by FUTEX_WAKE
+ * -2 - FUTEX_WAKE did not found a suspended thread at the passed address
+ * -3 - maximum number of suspended threads reached at a given address
inside FUTEX_WAIT
+ * -4 - maximum number of futexes reached while inside FUTEX_WAIT
+ * -5 - unknown operation
+ *
+ */
+int futex(int *address, int thread_num, int operation)
+{
+ switch (operation) {
+ case FUTEX_WAIT:
+ return futex_wait(address);
+ break;
+ case FUTEX_WAKE:
+ return futex_wake(address, thread_num);
+ break;
+ default:
+ return -5;
+ }
+}
+
+void futex_init(int *address, ftx_t futex)
+{
+ futex->address = address;
+ futex->num_futexed_threads = 0;
+ futexes[num_futexes] = futex;
+ num_futexes++;
+}
+
+int futex_wait(int *address)
+{
+ lock_t futex_wait_lock;
+
+ /* Save the value at the address. */
+ int temp = *address;
+
+ simple_lock(&futex_wait_lock);
+
+ /* If the value after the lock is still the same. */
+ if (temp == *address) {
+
+ simple_unlock(&futex_wait_lock);
+
+ int i;
+ boolean_t found = FALSE;
+ /* Check if there is an existing futex at the address given. */
+ for (i = 0; i < num_futexes; i++) {
+ if (futexes[i]->address == address) {
+ found = TRUE;
+
+ if (futexes[i]->num_futexed_threads >=
FUTEX_MAX_THREADS) {
+ printf("(futex) maximum number of
suspended threads reached");
+ return -3;
+ }
+ /* Add the thread to the futex. */
+ futexes[i]->futexed_threads
+ [futexes[i]->num_futexed_threads] =
current_thread();
+ futexes[i]->num_futexed_threads++;
+ goto suspend;
+ }
+ }
+ /* If there is no futex, init a new one. */
+ if (!found) {
+
+ if (num_futexes - 1 >= FUTEX_MAX) {
+ printf("(futex) maximum number of futexes
reached");
+ return -4;
+ }
+
+ ftx_t new_futex;
+ futex_init(address, new_futex);
+ num_futexes++;
+ /* Add the thread to the new futex. */
+ futexes[num_futexes - 1]->futexed_threads
+ [futexes[num_futexes - 1]->num_futexed_threads]
=
+ current_thread();
+ futexes[num_futexes - 1]->num_futexed_threads++;
+ }
+
+ suspend:
+ thread_suspend(current_thread());
+ return 0;
+ }
+ simple_unlock(&futex_wait_lock);
+ return -1;
+}
+
+int futex_wake(int *address, int thread_num)
+{
+ int i;
+ boolean_t found = FALSE;
+ for (i = 0; i < num_futexes; i++)
+ if (futexes[i]->address == address) {
+ found = TRUE;
+ break;
+ }
+
+ /* If thread_num is greater than num_futexed_threads, resume all. */
+ if (found && thread_num > futexes[i]->num_futexed_threads)
+ thread_num = futexes[i]->num_futexed_threads - 1;
+
+ if (found) {
+ int j;
+ for (j = 0; j < thread_num; j++) {
+ thread_resume(futexes[i]->futexed_threads[j]);
+ futexes[i]->num_futexed_threads--;
+ }
+ return 1;
+ }
+ else return -2;
+}
+
diff --git a/kern/futex.h b/kern/futex.h
new file mode 100644
index 0000000..10ba091
--- /dev/null
+++ b/kern/futex.h
@@ -0,0 +1,58 @@
+/*
+ * 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>
+
+/* Definitions for futex operations. */
+#define FUTEX_WAIT 0
+#define FUTEX_WAKE 1
+
+/* Maximum number of futexed threads waiting at the same address. */
+#define FUTEX_MAX_THREADS 128
+
+/* Maximum number of futexes. */
+#define FUTEX_MAX 128
+
+struct ftx {
+ int *address;
+
+ /* 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[FUTEX_MAX_THREADS];
+};
+
+typedef struct ftx *ftx_t;
+
+extern int futex(int *address, int thread_num, int operation);
+void futex_init(int *address, ftx_t futex);
+int futex_wait(int *address);
+int futex_wake(int *address, int thread_num);
+
+#endif /* _KERN_FUTEX_H */
--
1.8.1.4
