[RFC] kern: simple futex for gnumach

[Marin Ramesa]

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