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

[Justus Winter]

Quoting Marin Ramesa (2014-01-15 01:48:01)
> So, I decided to keep working on this.

Awesome :)

> [..]
> I tested a simple userspace mutex based on this and multiple futexes, 
> all tests passed.

Could you put that somewhere? I still have so little "context", I'd
like to see how futexe are used in a mutex implementation.

> 
> ---
>  Makefrag.am               |    2 +
>  include/mach/gnumach.defs |   37 +++++++++++
>  kern/futex.c              |  159 
> +++++++++++++++++++++++++++++++++++++++++++++
>  kern/futex.h              |   64 ++++++++++++++++++
>  kern/startup.c            |    3 +
>  5 files changed, 265 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..136f323 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 

Trailing whitespace.

I use emacs, and with the following setting, trailing whitespace is
shown as red blocks at the end of the line.  It makes your eyes bleed,
so naturally one wants to avoid it in the first place ;)

 '(show-trailing-whitespace t)

> + * is same as value. The value at the futex address should 

Likewise.

> + * 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.
> + *
> + */
> +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..1484896
> --- /dev/null
> +++ b/kern/futex.c
> @@ -0,0 +1,159 @@
> +/*
> + * 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. */
> +};
> +
> +static queue_head_t futex_shared_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);
> +       simple_lock_init(&futex_shared_lock);
> +       simple_lock_init(&futex_private_lock);
> +}
> +
> +static struct futex *futex_lookup_address(vm_offset_t address)
> +{
> +       struct futex *futex = NULL;

Why initialize it to NULL ?

> +       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;

So here the queue stuff replaced the r/b tree?  If so, note that your
lookup cost just went from O(log n) to O(n).  This might very well be
okay, I just wanted to point that out.

> +       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;
> +}

When I said that you used to put superfluous newlines into the code, I
didn't mean to imply that you should remove all newlines. I mostly
think that newlines after/before parenthesis are useless/noise b/c the
parenthesis already provide "visual" structure.

Now your code looks very dense.

> +
> +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) {
> +               if (__sync_bool_compare_and_swap(
> +                       (int *) futex_address, value, value)) {

Richard already mentioned that, this looks very wrong.  For reference,
this is the atomic equivalent of:

if (*futex_address == value) {
  *futex_address = value;
  return 1;
}
return 0;

You surely wouldn't want to see any such code in a kernel you use.
Also, the __sync* functions are deprecated.  Use the __atomic*
functions instead.

If you merely want to do an atomic load at this address, use
__atomic_load_n.

> +                       simple_lock(&futex_private_lock);
> +                       assert_wait((event_t) futex_address, TRUE);
> +                       if (msec != 0)
> +                               thread_will_wait_with_timeout(
> +                                       current_thread(), msec);
> +                       simple_unlock(&futex_private_lock);
> +                       thread_block(NULL);
> +                       return KERN_SUCCESS;
> +               }
> +               return KERN_SUCCESS;
> +       } else {
> +               struct futex *futex;
> +
> +               futex = futex_lookup_address(futex_address);
> +               if (futex == NULL) {
> +                       futex = futex_shared_init(futex_address);
> +                       if (futex == NULL)
> +                               return KERN_RESOURCE_SHORTAGE;
> +               }
> +               if (__sync_bool_compare_and_swap(
> +                       (int *) futex_address, value, 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;
> +               }
> +               return KERN_SUCCESS;
> +       }

There are four times return KERN_SUCCESS in this functions. You could
remove them all and put a single return KERN_SUCCESS at the end of the
function.

> +}
> +
> +void
> +futex_wake(task_t task, vm_offset_t address,
> +          boolean_t wake_all, boolean_t private_futex)
> +{
> +       if (private_futex) {
> +               simple_lock(&futex_private_lock);
> +               if (wake_all)
> +                       thread_wakeup((event_t)address);
> +               else
> +                       thread_wakeup_one((event_t)address);
> +               simple_unlock(&futex_private_lock);
> +       } else {
> +               struct futex *futex = futex_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..c3ead8f
> --- /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;
> +
> +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,
> + * but a task may unlock a futex locked in another task.
> + *
> + */
> +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();
>  

See the trailing whitespace here? You have the golden opportunity to
fix this. Please do ;)

> +       futex_setup();
> +
>         /*
>          *      Create a kernel thread to start the other kernel
>          *      threads.  Thread_resume (from kernel_thread) calls
> -- 
> 1.7.10.4

Cheers,
Justus