Re: [PATCH v16] kern: simple futex for gnumach

[Justus Winter]

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(&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) {

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