bug-hurd
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[RFC] kern: simple futex for gnumach (version 12)


From: Marin Ramesa
Subject: [RFC] kern: simple futex for gnumach (version 12)
Date: Sat, 11 Jan 2014 14:10:07 +0100

Private futexes are now per task. Tree compare functions have been
rewriten. Waits are now interruptible and bounded sleep has been
merged into the unbounded case. Function futex_wait() now takes
the address as the argument instead of the value.

---
 Makefrag.am               |    2 +
 include/mach/gnumach.defs |   14 +++
 kern/futex.c              |  271 +++++++++++++++++++++++++++++++++++++++++++++
 kern/futex.h              |   55 +++++++++
 kern/startup.c            |    3 +
 5 files changed, 345 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..035d7de
--- /dev/null
+++ b/kern/futex.c
@@ -0,0 +1,271 @@
+/*
+ * 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/rbtree.h>
+#include <kern/futex.h>
+#include <kern/sched_prim.h>
+#include <vm/vm_map.h>
+#include <machine/locore.h>
+#include <kern/thread.h>
+#include <kern/lock.h>
+#include <kern/kalloc.h>
+#include <ipc/ipc_space.h>
+#include <ipc/ipc_entry.h>
+
+struct futex {
+
+       struct rbtree_node *node;
+
+       ipc_entry_t entry;
+
+       decl_simple_lock_data( , lock);
+
+       vm_offset_t address;
+
+       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)
+{
+       struct futex *futex;
+
+       futex = (struct futex *)kalloc(sizeof(*futex));
+       if (futex == NULL)
+               return NULL;
+
+       futex->node = NULL;
+       futex->address = address;
+       futex->nr_refs = 0;
+       futex->object = NULL;
+       futex->offset = 0;
+       futex->entry = NULL;
+
+       simple_lock_init(&futex->lock);
+       is_write_lock(current_thread()->task->itk_space);
+       ipc_entry_grow_table(current_thread()->task->itk_space);
+       ipc_entry_alloc(current_thread()->task->itk_space, &address, 
&futex->entry);
+       is_write_unlock(current_thread()->task->itk_space);
+
+       return futex->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;
+               
+       vm_map_lookup(&current_map(), address, VM_PROT_READ, &version, 
&futex.object, &futex.offset, &prot, &wired);
+       
+       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;
+
+       vm_map_lookup(&current_map(), address, VM_PROT_READ, 
+                       &version, &(*futex)->object, &(*futex)->offset, &prot, 
&wired);
+
+       (*futex)->node = &node;
+       (*futex)->address = address;
+       (*futex)->nr_refs = 0;
+       (*futex)->entry = NULL;
+
+       simple_lock(&futex_shared_lock);
+
+       rbtree_insert(&futex_shared_tree, &node, futex_shared_cmp_insert);
+
+       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));
+                       if (futex_ipc_space == NULL)
+                               return;
+                       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);
+                       if (entry == NULL)
+                               return;
+               }
+
+               if (*(int *)futex_address == *(int *)compare_address) {
+
+                       struct futex *pfutex;
+
+                       pfutex = structof(entry, struct futex, entry);
+
+                       simple_lock(&pfutex->lock);
+                                       
+                       pfutex->nr_refs++;
+
+                       assert_wait(pfutex, TRUE);
+
+                       if (msec != 0)
+                               thread_will_wait_with_timeout(current_thread(), 
(unsigned int)msec);
+
+                       simple_unlock(&pfutex->lock);
+                       
+                       thread_block(NULL);
+
+                       pfutex->nr_refs--;
+                       
+               }
+
+       } else {
+
+               struct rbtree_node *node;
+               struct futex *futex;
+
+               node = futex_lookup_address(futex_address);
+
+               if (node == NULL) 
+                       if (futex_shared_init(futex_address, &futex) != 0)      
                
+                               return;
+
+               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) {
+
+                       struct futex *futex = structof(entry, struct futex, 
entry);
+
+                       simple_lock(&futex->lock);
+
+                       if (wake_all)                           
+                               thread_wakeup(futex);
+                       else 
+                               thread_wakeup_one(futex);
+
+                       simple_unlock(&futex->lock);
+
+               }
+
+       } 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..4c30afa
--- /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 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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]