[PATCH v13] kern: simple futex for gnumach

[Marin Ramesa]

Assertions were added instead of silently returning from functions
on errors and private futexes were simplified.

This is one of the last versions. I won't be changing the base code, 
except for fixing bugs if they are found, as this actually works as 
expected. I'm little bit unsure about the correctness of tests I did 
for private wakeups, but since everything works in timed waits I don't 
think there will be a problem here. I'm also a little bit concerned 
about the (VM object, offset) pair being not constant enough to 
consistently wake the threads blocked in shared futexes, but we will 
see this in actual practice.

The next step, I think, is to write a userspace mutex implementation 
based on these calls and see how it behaves.

---
 Makefrag.am               |    2 +
 include/mach/gnumach.defs |   14 +++
 kern/futex.c              |  243 +++++++++++++++++++++++++++++++++++++++++++++
 kern/futex.h              |   55 ++++++++++
 kern/startup.c            |    3 +
 5 files changed, 317 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..5fef7ea 100644
--- a/include/mach/gnumach.defs
+++ b/include/mach/gnumach.defs
@@ -63,3 +63,17 @@ simpleroutine thread_terminate_release(
                reply_port      : mach_port_name_t;
                address         : vm_address_t;
                size            : vm_size_t);
+
+routine futex_wait(
+               task            : task_t;
+               futex_address   : vm_offset_t;
+               compare_address : vm_offset_t;
+               msec            : int;
+               private_futex   : boolean_t);
+
+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..760cc6b
--- /dev/null
+++ b/kern/futex.c
@@ -0,0 +1,243 @@
+/*
+ * 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/rbtree.h>
+#include <kern/sched_prim.h>
+#include <kern/thread.h>
+#include <kern/lock.h>
+#include <kern/kalloc.h>
+#include <kern/assert.h>
+#include <vm/vm_map.h>
+#include <ipc/ipc_space.h>
+#include <ipc/ipc_entry.h>
+
+struct futex {
+
+       struct rbtree_node *node;
+
+       vm_object_t object;
+       
+       vm_offset_t offset;
+
+       unsigned int nr_refs;
+
+};
+
+static struct rbtree futex_shared_tree;
+decl_simple_lock_data(static, futex_shared_lock); 
+
+void futex_setup(void)
+{
+       rbtree_init(&futex_shared_tree);
+       simple_lock_init(&futex_shared_lock); 
+}
+
+static inline int futex_shared_cmp_lookup(struct futex *futex, struct 
rbtree_node *node2)
+{
+       int temp = futex->offset - rbtree_entry(node2, struct futex, 
node)->offset +
+                  futex->object - rbtree_entry(node2, struct futex, 
node)->object; 
+
+       if (temp < 0) return -1;
+       else if (temp > 0) return 1;    
+       else return 0;
+}
+
+static inline int futex_shared_cmp_insert(struct rbtree_node *node1, struct 
rbtree_node *node2)
+{
+       return futex_shared_cmp_lookup(rbtree_entry(node1, struct futex, node), 
node2);
+}
+
+static ipc_entry_t futex_private_init(vm_offset_t address)
+{
+       ipc_entry_t entry;
+
+       ipc_entry_alloc(current_thread()->task->itk_space, &address, &entry);
+       is_write_unlock(current_thread()->task->itk_space);
+
+       return entry;
+}
+
+static struct rbtree_node *futex_lookup_address(vm_offset_t address)
+{
+       struct futex futex;
+
+       vm_map_version_t version;
+       vm_prot_t prot;
+       boolean_t wired;
+       
+       kern_return_t kr;       
+       kr = vm_map_lookup(&current_map(), address, VM_PROT_READ, &version, 
&futex.object, &futex.offset, &prot, &wired);
+       assert(kr == KERN_SUCCESS);     
+
+       return rbtree_lookup(&futex_shared_tree, &futex, 
futex_shared_cmp_lookup);
+}      
+
+static int 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 -1;
+
+       struct rbtree_node node;
+
+       kern_return_t kr;
+       kr = vm_map_lookup(&current_map(), address, VM_PROT_READ, 
+                       &version, &(*futex)->object, &(*futex)->offset, &prot, 
&wired);
+       assert(kr == KERN_SUCCESS);
+
+       (*futex)->nr_refs = 0;
+
+       simple_lock(&futex_shared_lock);
+
+       rbtree_insert(&futex_shared_tree, &node, futex_shared_cmp_insert);
+
+       (*futex)->node = &node;
+
+       simple_unlock(&futex_shared_lock);
+
+       return 0;               
+}
+
+void futex_wait(task_t task, vm_offset_t futex_address, vm_offset_t 
compare_address, int msec, boolean_t private_futex)
+{
+       if (private_futex) {
+
+               ipc_entry_t entry;
+
+               if (current_thread()->task->itk_space == NULL) {
+               
+                       struct ipc_space *futex_ipc_space;
+
+                       futex_ipc_space = (struct ipc_space 
*)kalloc(sizeof(*futex_ipc_space));
+                       assert(futex_ipc_space != NULL);
+                       ipc_space_create(0, &futex_ipc_space);
+                       is_lock_init(futex_ipc_space);
+                       futex_ipc_space->is_active = TRUE;              
+                       current_thread()->task->itk_space = futex_ipc_space;
+               
+               }
+
+               entry = ipc_entry_lookup(current_thread()->task->itk_space, 
futex_address);
+
+               if (entry == NULL) {
+                       entry = futex_private_init(futex_address);
+                       assert(entry != NULL);
+               }
+
+               if (*(int *)futex_address == *(int *)compare_address) {
+
+                       is_write_lock(current_thread()->task->itk_space);
+
+                       assert_wait((event_t)futex_address, TRUE);
+
+                       if (msec != 0)
+                               thread_will_wait_with_timeout(current_thread(), 
(unsigned int)msec);
+
+                       is_write_unlock(current_thread()->task->itk_space);
+                       
+                       thread_block(NULL);
+
+               }
+
+       } else {
+
+               struct rbtree_node *node;
+               struct futex *futex;
+
+               node = futex_lookup_address(futex_address);
+
+               if (node == NULL) 
+                       assert(futex_shared_init(futex_address, &futex) == 0);  
                
+
+               if (*(int *)futex_address == *(int *)compare_address) {
+                       
+                       simple_lock(&futex_shared_lock);
+
+                       if (node != NULL)
+                               futex = rbtree_entry(node, struct futex, node);
+
+                       futex->nr_refs++;
+
+                       assert_wait(futex, TRUE);
+
+                       if (msec != 0)
+                               thread_will_wait_with_timeout(current_thread(), 
(unsigned int)msec);
+
+                       simple_unlock(&futex_shared_lock);
+                       
+                       thread_block(NULL);
+                       
+                       if (--futex->nr_refs == 0) {
+                               rbtree_remove(&futex_shared_tree, futex->node);
+                               kfree((vm_offset_t)futex, sizeof(*futex));
+                       }
+               }
+       }
+}
+
+void futex_wake(task_t task, vm_offset_t address, boolean_t wake_all, 
boolean_t private_futex)
+{ 
+       if (private_futex) {
+               
+               ipc_entry_t entry = 
ipc_entry_lookup(current_thread()->task->itk_space, address);
+       
+               if (entry != NULL) {
+
+                       is_write_lock(current_thread()->task->itk_space);
+
+                       if (wake_all)                           
+                               thread_wakeup((event_t)address);
+                       else 
+                               thread_wakeup_one((event_t)address);
+
+                       is_write_unlock(current_thread()->task->itk_space);
+
+               }
+
+       } else {
+
+               struct rbtree_node *node = futex_lookup_address(address);
+
+               if (node != NULL) {
+
+                       struct futex *futex = rbtree_entry(node, struct futex, 
node);
+
+                       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..172c43c
--- /dev/null
+++ b/kern/futex.h
@@ -0,0 +1,55 @@
+/*
+ * 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 <kern/task.h>
+
+struct futex;
+
+void futex_setup(void);
+
+/*
+ * The calling thread blocks if values at the addresses are the same. Values
+ * should be integers.
+ *
+ * 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.
+ *
+ */
+void futex_wait(task_t task, vm_offset_t futex_address, vm_offset_t 
compare_address, int 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