[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH v16] kern: simple futex for gnumach
From: |
Justus Winter |
Subject: |
Re: [PATCH v16] kern: simple futex for gnumach |
Date: |
Fri, 17 Jan 2014 15:56:39 +0100 |
User-agent: |
alot/0.3.4 |
Quoting Marin Ramesa (2014-01-17 15:32:05)
> 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.
Sounds promising, if they are in a shape to be presented, please
publish these patches somewhere. Also, did you try some more complex
programs?
The sysbench suite has micro benchmarks that iirc mainly test lock
performance:
% sysbench --test=threads --max-time=60 run
> 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.
The (ugly) linux interface presented in the futex paper is much
richer, sure that this is enough ?
>
> ---
> 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(¤t_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(¤t_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) {
If you would combine these two if-statements, the code would more
closely match the next block for the shared futexe. I think this is
both aesthetically more pleasing and makes it easier to spot
differences.
> + 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
Cheers,
Justus