bug-hurd
[Top][All Lists]
Advanced

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

[PATCH v16] kern: simple futex for gnumach


From: Marin Ramesa
Subject: [PATCH v16] kern: simple futex for gnumach
Date: Fri, 17 Jan 2014 15:32:05 +0100

Function __atomic_load_n() is now used. Private futex structure and queue
was defined to avoid conflicts in block and wakeup events. Now, private
futex is really private and may only be used by threads of the task where
it was locked.

All of libpthread tests are successful with pthread mutex based on these
calls. 

I've looked at other futex userspace applications (condvars, semaphores, 
rwlocks and barriers) and I think they can be implemented with these 
calls coupled with libpthread. 

---
 Makefrag.am               |    2 +
 include/mach/gnumach.defs |   37 ++++++++
 kern/futex.c              |  231 +++++++++++++++++++++++++++++++++++++++++++++
 kern/futex.h              |   64 +++++++++++++
 kern/startup.c            |    3 +
 5 files changed, 337 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..36f6c68 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,
+ * and may only be used by threads in a task where it was locked. 
+ * Private futex is tied to the current map.
+ */
+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..6a6206c
--- /dev/null
+++ b/kern/futex.c
@@ -0,0 +1,231 @@
+/*
+ * 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. */
+};
+
+struct private_futex {
+       queue_chain_t chain;  /* Futex chain field in the queue. */
+       vm_offset_t address;  /* Futex address. */
+       task_t task;          /* Futex task. */
+       unsigned int nr_refs; /* Number of futex waiters. */
+};
+
+static queue_head_t futex_shared_queue;
+static queue_head_t futex_private_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);
+       queue_init(&futex_private_queue);
+       simple_lock_init(&futex_shared_lock);
+       simple_lock_init(&futex_private_lock);
+}
+
+static struct futex *
+futex_shared_lookup_address(vm_offset_t address)
+{
+       struct futex *futex;
+       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 NULL;
+}
+
+static struct private_futex *
+futex_private_lookup_address(vm_offset_t address)
+{
+       struct private_futex *futex;
+
+       queue_iterate(&futex_private_queue, futex, struct private_futex *, 
chain)
+               if (address == futex->address && current_map() == 
futex->task->map)
+                       return futex;
+
+       return NULL;
+}
+
+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;
+}
+
+static struct private_futex *
+futex_private_init(vm_offset_t address)
+{
+       struct private_futex *futex;
+
+       futex = (struct private_futex *) kalloc(sizeof(*futex));
+       if (futex == NULL)
+               return NULL;
+
+       futex->address = address;
+       futex->task = current_thread()->task;
+       futex->nr_refs = 0;
+
+       simple_lock(&futex_private_lock);
+       queue_enter(&futex_private_queue, futex, struct private_futex *, chain);
+       simple_unlock(&futex_private_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) {
+               struct private_futex *futex;
+
+               futex = futex_private_lookup_address(futex_address);
+               if (futex == NULL) {
+                       futex = futex_private_init(futex_address);
+                       if (futex == NULL)
+                               return KERN_RESOURCE_SHORTAGE;
+               }
+
+               if (__atomic_load_n(
+                       (int *) futex_address, __ATOMIC_RELAXED) == value) {
+                       simple_lock(&futex_private_lock);
+                       futex->nr_refs++;
+                       assert_wait(futex, TRUE);
+                       if (msec != 0)
+                               thread_will_wait_with_timeout(
+                                       current_thread(), msec);
+                       simple_unlock(&futex_private_lock);
+                       thread_block(NULL);
+
+                       simple_lock(&futex_private_lock)
+                       if (--futex->nr_refs == 0) {
+                               queue_remove(&futex_private_queue, futex,
+                                            struct private_futex *, chain)
+                               kfree((vm_offset_t) futex, sizeof(*futex));
+                       }
+                       simple_unlock(&futex_private_lock);
+               }
+       } else {
+               struct futex *futex;
+
+               futex = futex_shared_lookup_address(futex_address);
+               if (futex == NULL) {
+                       futex = futex_shared_init(futex_address);
+                       if (futex == NULL)
+                               return KERN_RESOURCE_SHORTAGE;
+               }
+
+               if (__atomic_load_n(
+                       (int *) futex_address, __ATOMIC_RELAXED) == 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;
+}
+
+void
+futex_wake(task_t task, vm_offset_t address,
+          boolean_t wake_all, boolean_t private_futex)
+{
+       if (private_futex) {
+               struct private_futex *futex = 
futex_private_lookup_address(address);
+
+               if (futex != NULL)
+                       if (futex->task == current_thread()->task) {
+                               simple_lock(&futex_private_lock);
+                               if (wake_all)
+                                       thread_wakeup(futex);
+                               else
+                                       thread_wakeup_one(futex);
+                               simple_unlock(&futex_private_lock);
+                       }
+       } else {
+               struct futex *futex = futex_shared_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..e34cd42
--- /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;
+struct private_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,
+ * and may only be used by threads in a task where it was locked.
+ * Private futex is tied to the current map.
+ */
+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




reply via email to

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