[PATCH v15] kern: simple futex for gnumach

[Marin Ramesa]

So, I decided to keep working on this.

Thanks Diego for finding bugs in my usage of rbtree nodes, this
was the reason why shared futex was not always waking the threads,
I wrongly concluded that the (VM object, offset) pair is not constant
enough. Anyway I'm now using queue macros which simplifies the code
and bugs are gone. 

As for Justus comments, trailing whitespace was removed and max column size 
is now 80. Function futex_wait() now returns kern_return_t which allows me 
to remove wrongly used assertions. Space is used after casts and a missed lock 
was added for nr_refs.

Futex IPC space was removed, which means that private futexes are not
completely private now, as a task can unlock a futex locked in another
task, but they are private because they don't use (VM object, offset)
pair and a different lock is declared for them.

The code for thread block was written based on thread_sleep()
implementation and in the comments it says that timeouts are
set between assert_wait() and thread_block(), so I'm doing just
that. I hope it's correct. It works.

I switched back to using (address, value) pair for futex_wait(),
this is how it's prototyped in Linux, so I think it will be
good enough. With this comes the call to __sync_bool_compare_and_swap(),
which does an atomic fetch, compare and swap, so I think it's useful.
Timeout parameter of futex_wait() is now of mach_msg_timeout_t type.

I tested a simple userspace mutex based on this and multiple futexes, 
all tests passed.

---
 Makefrag.am               |    2 +
 include/mach/gnumach.defs |   37 +++++++++++
 kern/futex.c              |  159 +++++++++++++++++++++++++++++++++++++++++++++
 kern/futex.h              |   64 ++++++++++++++++++
 kern/startup.c            |    3 +
 5 files changed, 265 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/include/mach/gnumach.defs b/include/mach/gnumach.defs
index 12c4e99..136f323 100644
--- a/include/mach/gnumach.defs
+++ b/include/mach/gnumach.defs
@@ -63,3 +63,40 @@ simpleroutine thread_terminate_release(
                reply_port      : mach_port_name_t;
                address         : vm_address_t;
                size            : vm_size_t);
+
+/*
+ * The calling thread blocks if value at the futex address 
+ * is same as value. The value at the futex address should 
+ * be an integer.
+ *
+ * If msec is non-zero, thread blocks for msec amount of time. 
+ * If it's zero, no timeout is used. 
+ *
+ * If private_futex is true, futex is not shared between tasks.
+ *
+ */
+routine futex_wait(
+               task            : task_t;
+               futex_address   : vm_offset_t;
+               value           : int;
+               msec            : natural_t;
+               private_futex   : boolean_t);
+
+/*
+ * The calling thread wakes one or all threads blocked in 
+ * futex_wait().
+ * 
+ * If wake_all is true, all threads are awakened. If it's 
+ * false, only one thread is awakened.
+ *
+ * If private_futex is false the thread wakes one or all 
+ * threads with futex addresses at the same offset in the 
+ * same VM object.
+ *
+ */
+routine futex_wake(
+               task            : task_t;
+               address         : vm_offset_t;
+               wake_all        : boolean_t;
+               private_futex   : boolean_t);
+
diff --git a/kern/futex.c b/kern/futex.c
new file mode 100644
index 0000000..1484896
--- /dev/null
+++ b/kern/futex.c
@@ -0,0 +1,159 @@
+/*
+ * Copyright (C) 2013, 2014 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/queue.h>
+#include <kern/sched_prim.h>
+#include <kern/thread.h>
+#include <kern/lock.h>
+#include <kern/kalloc.h>
+#include <vm/vm_map.h>
+
+struct futex {
+       queue_chain_t chain;  /* Futex chain field in the queue. */
+       vm_object_t object;   /* Futex VM object from vm_map_lookup(). */
+       vm_offset_t offset;   /* Offset for the futex address. */
+       unsigned int nr_refs; /* Number of futex waiters. */
+};
+
+static queue_head_t futex_shared_queue;
+decl_simple_lock_data(static, futex_shared_lock);
+decl_simple_lock_data(static, futex_private_lock);
+
+void futex_setup(void)
+{
+       queue_init(&futex_shared_queue);
+       simple_lock_init(&futex_shared_lock);
+       simple_lock_init(&futex_private_lock);
+}
+
+static struct futex *futex_lookup_address(vm_offset_t address)
+{
+       struct futex *futex = NULL;
+       vm_object_t object;
+       vm_offset_t offset;
+       vm_map_version_t version;
+       vm_prot_t prot;
+       boolean_t wired;
+
+       vm_map_lookup(&current_map(), address, VM_PROT_READ, &version,
+                     &object, &offset, &prot, &wired);
+       queue_iterate(&futex_shared_queue, futex, struct futex *, chain)
+               if (object == futex->object && offset == futex->offset)
+                       return futex;
+       return futex;
+}
+
+static struct futex *futex_shared_init(vm_offset_t address)
+{
+       struct futex *futex;
+       vm_map_version_t version;
+       vm_prot_t prot;
+       boolean_t wired;
+
+       futex = (struct futex *) kalloc(sizeof(*futex));
+       if (futex == NULL)
+               return NULL;
+       vm_map_lookup(&current_map(), address, VM_PROT_READ, &version,
+                     &futex->object, &futex->offset, &prot, &wired);
+       futex->nr_refs = 0;
+       simple_lock(&futex_shared_lock);
+       queue_enter(&futex_shared_queue, futex, struct futex *, chain);
+       simple_unlock(&futex_shared_lock);
+       return futex;
+}
+
+kern_return_t
+futex_wait(task_t task, vm_offset_t futex_address, int value,
+           mach_msg_timeout_t msec, boolean_t private_futex)
+{
+       if (private_futex) {
+               if (__sync_bool_compare_and_swap(
+                       (int *) futex_address, value, value)) {
+                       simple_lock(&futex_private_lock);
+                       assert_wait((event_t) futex_address, TRUE);
+                       if (msec != 0)
+                               thread_will_wait_with_timeout(
+                                       current_thread(), msec);
+                       simple_unlock(&futex_private_lock);
+                       thread_block(NULL);
+                       return KERN_SUCCESS;
+               }
+               return KERN_SUCCESS;
+       } else {
+               struct futex *futex;
+
+               futex = futex_lookup_address(futex_address);
+               if (futex == NULL) {
+                       futex = futex_shared_init(futex_address);
+                       if (futex == NULL)
+                               return KERN_RESOURCE_SHORTAGE;
+               }
+               if (__sync_bool_compare_and_swap(
+                       (int *) futex_address, value, value)) {
+                       simple_lock(&futex_shared_lock);
+                       futex->nr_refs++;
+                       assert_wait(futex, TRUE);
+                       if (msec != 0)
+                               thread_will_wait_with_timeout(
+                                       current_thread(), msec);
+                       simple_unlock(&futex_shared_lock);
+                       thread_block(NULL);
+                       simple_lock(&futex_shared_lock)
+                       if (--futex->nr_refs == 0) {
+                               queue_remove(&futex_shared_queue, futex,
+                                            struct futex *, chain)
+                               kfree((vm_offset_t) futex, sizeof(*futex));
+                       }
+                       simple_unlock(&futex_shared_lock);
+                       return KERN_SUCCESS;
+               }
+               return KERN_SUCCESS;
+       }
+}
+
+void
+futex_wake(task_t task, vm_offset_t address,
+          boolean_t wake_all, boolean_t private_futex)
+{
+       if (private_futex) {
+               simple_lock(&futex_private_lock);
+               if (wake_all)
+                       thread_wakeup((event_t)address);
+               else
+                       thread_wakeup_one((event_t)address);
+               simple_unlock(&futex_private_lock);
+       } else {
+               struct futex *futex = futex_lookup_address(address);
+
+               if (futex != NULL) {
+                       simple_lock(&futex_shared_lock);
+                       if (wake_all)
+                               thread_wakeup(futex);
+                       else
+                               thread_wakeup_one(futex);
+                       simple_unlock(&futex_shared_lock);
+               }
+       }
+}
diff --git a/kern/futex.h b/kern/futex.h
new file mode 100644
index 0000000..c3ead8f
--- /dev/null
+++ b/kern/futex.h
@@ -0,0 +1,64 @@
+/*
+ * Copyright (C) 2013, 2014 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 <mach/message.h>
+#include <kern/task.h>
+
+struct futex;
+
+void futex_setup(void);
+
+/*
+ * The calling thread blocks if value at the futex address
+ * is same as value. The value at the futex address should
+ * be an integer.
+ *
+ * If msec is non-zero, thread blocks for msec amount of time.
+ * If it's zero, no timeout is used.
+ *
+ * If private_futex is true, futex is not shared between tasks,
+ * but a task may unlock a futex locked in another task.
+ *
+ */
+kern_return_t
+futex_wait(task_t task, vm_offset_t futex_address, int value,
+          mach_msg_timeout_t msec, boolean_t private_futex);
+
+/*
+ * The calling thread wakes one or all threads blocked in
+ * futex_wait().
+ *
+ * If wake_all is true, all threads are awakened. If it's
+ * false, only one thread is awakened.
+ *
+ * If private_futex is false the thread wakes one or all
+ * threads with futex addresses at the same offset in the
+ * same VM object.
+ *
+ */
+void
+futex_wake(task_t task, vm_offset_t address,
+          boolean_t wake_all, boolean_t private_futex);
+
+#endif /* _KERN_FUTEX_H_ */
diff --git a/kern/startup.c b/kern/startup.c
index 12f5123..447c528 100644
--- a/kern/startup.c
+++ b/kern/startup.c
@@ -50,6 +50,7 @@
 #include <kern/bootstrap.h>
 #include <kern/time_stamp.h>
 #include <kern/startup.h>
+#include <kern/futex.h>
 #include <vm/vm_kern.h>
 #include <vm/vm_map.h>
 #include <vm/vm_object.h>
@@ -158,6 +159,8 @@ void setup_main(void)
        recompute_priorities(NULL);
        compute_mach_factor();
 
+       futex_setup();
+
        /*
         *      Create a kernel thread to start the other kernel
         *      threads.  Thread_resume (from kernel_thread) calls
-- 
1.7.10.4