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

[Justus Winter]

Hi Marin :)

Quoting Marin Ramesa (2014-01-13 15:38:19)
> Fixed a bug in private wakeups by calling ipc_entry_alloc_name().
> 
> This is the last version as everything works now.

Heh, how many times did I think just that >,<

> To do a quick userspace mutex test with timed waits:

Good to see you made it into the Hurd world :)

[...]

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

These two require documentation.

> diff --git a/kern/futex.c b/kern/futex.c
> new file mode 100644
> index 0000000..2868545
> --- /dev/null
> +++ b/kern/futex.c
> @@ -0,0 +1,247 @@
> +/*
> + * 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
> + *

Extra line in comment.

> + */
> +
> +#include <kern/futex.h>
> +#include <kern/rbtree.h>
> +#include <kern/sched_prim.h>
> +#include <kern/thread.h>
> +#include <kern/lock.h>
> +#include <kern/kalloc.h>
> +#include <kern/assert.h>
> +#include <vm/vm_map.h>
> +#include <ipc/ipc_space.h>
> +#include <ipc/ipc_entry.h>
> +
> +struct futex {
> +
> +       struct rbtree_node *node;
> +
> +       vm_object_t object;
> +       

Trailing whitespace.  I configured my editor to highlight trailing
whitespace so it's easy to spot.  You can fix your files with
something like sed -i -e 's/\s*$//' your_file.

> +       vm_offset_t offset;
> +
> +       unsigned int nr_refs;
> +
> +};

This is formatted in a weird way, and there is no documentation
whatsoever.

> +
> +static struct rbtree futex_shared_tree;
> +decl_simple_lock_data(static, futex_shared_lock); 

trailing whitespace again

> +
> +void futex_setup(void)
> +{
> +       rbtree_init(&futex_shared_tree);
> +       simple_lock_init(&futex_shared_lock); 

again

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

again

> +
> +       if (temp < 0) return -1;
> +       else if (temp > 0) return 1;    

again....

> +       else return 0;

Also, this is formatted strangely.  It's a matter of taste, I guess,
but I'd prefer it like this:

if (..)
    ...
else
    ...

> +}
> +
> +static inline int futex_shared_cmp_insert(struct rbtree_node *node1, struct 
> rbtree_node *node2)

You do use very long lines.  While I personally don't mind, there are
others that do.  As a rule of thumb, look what the other source code
looks like and stick to that convention.

> +{
> +       return futex_shared_cmp_lookup(rbtree_entry(node1, struct futex, 
> node), node2);
> +}
> +
> +static ipc_entry_t futex_private_init(vm_offset_t address)
> +{
> +       ipc_entry_t entry;
> +       mach_port_t name;
> +
> +       ipc_entry_alloc(current_thread()->task->itk_space, &name, &entry);
> +       is_write_unlock(current_thread()->task->itk_space);
> +       ipc_entry_alloc_name(current_thread()->task->itk_space, address, 
> &entry);
> +       entry->ie_bits |= MACH_PORT_TYPE_DEAD_NAME;
> +       is_write_unlock(current_thread()->task->itk_space);
> +
> +       return 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;
> +       
> +       kern_return_t kr;       
> +       kr = vm_map_lookup(&current_map(), address, VM_PROT_READ, &version, 
> &futex.object, &futex.offset, &prot, &wired);
> +       assert(kr == KERN_SUCCESS);     

assert may only be used to express invariants.  Here, you are using
assert for error handling.  This is a no-go.

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

I'd prefer a space after a cast, not sure how the other gnumach code
looks like though.

> +       if (*futex == NULL)
> +               return -1;
> +
> +       struct rbtree_node node;
> +
> +       kern_return_t kr;
> +       kr = vm_map_lookup(&current_map(), address, VM_PROT_READ, 
> +                       &version, &(*futex)->object, &(*futex)->offset, 
> &prot, &wired);
> +       assert(kr == KERN_SUCCESS);

Likewise.

> +
> +       (*futex)->nr_refs = 0;
> +
> +       simple_lock(&futex_shared_lock);
> +
> +       rbtree_insert(&futex_shared_tree, &node, futex_shared_cmp_insert);
> +
> +       (*futex)->node = &node;
> +
> +       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) {
> +

Spurious newline.

> +               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));
> +                       assert(futex_ipc_space != NULL);

Likewise.

> +                       ipc_space_create(0, &futex_ipc_space);
> +                       is_lock_init(futex_ipc_space);
> +                       futex_ipc_space->is_active = TRUE;              
> +                       current_thread()->task->itk_space = futex_ipc_space;
> +               

Spurious newline.

> +               }
> +
> +               entry = ipc_entry_lookup(current_thread()->task->itk_space, 
> futex_address);
> +
> +               if (entry == NULL) {
> +                       entry = futex_private_init(futex_address);
> +                       assert(entry != NULL);

Likewise.

> +               }
> +
> +               if (*(int *)futex_address == *(int *)compare_address) {
> +
> +                       is_write_lock(current_thread()->task->itk_space);
> +
> +                       assert_wait((event_t)futex_address, TRUE);
> +
> +                       if (msec != 0)
> +                               
> thread_will_wait_with_timeout(current_thread(), (unsigned int)msec);
> +
> +                       is_write_unlock(current_thread()->task->itk_space);
> +                       
> +                       thread_block(NULL);
> +
> +               }
> +
> +       } else {
> +
> +               struct rbtree_node *node;
> +               struct futex *futex;
> +
> +               node = futex_lookup_address(futex_address);
> +
> +               if (node == NULL) 
> +                       assert(futex_shared_init(futex_address, &futex) == 
> 0);                  

This is wrong.  Not only are you using assert for error checking, but
your expression also very likely has side-effects.  If gnumach is
compiled so that assert becomes a no-op, the futex will not be
initialized.

> +
> +               if (*(int *)futex_address == *(int *)compare_address) {

I don't know what the code is supposed to be doing, but if
futex_address is in fact an address, this looks wrong.  You must not
assume that an integer can hold an 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) {

Are you sure it's safe to decrement nr_refs like this?  As far as I
can see you are neither holding any locks nor using functions for
atomic memory access.

> +                               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) {
> +
> +                       is_write_lock(current_thread()->task->itk_space);
> +
> +                       if (wake_all)                           
> +                               thread_wakeup((event_t)address);
> +                       else 
> +                               thread_wakeup_one((event_t)address);
> +
> +                       is_write_unlock(current_thread()->task->itk_space);
> +
> +               }
> +
> +       } 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..172c43c
> --- /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 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