Re: [RFC] kern: simple futex for gnumach (version 8)

[Richard Braun]

On Sun, Dec 29, 2013 at 09:44:51PM +0100, Marin Ramesa wrote:
> Futex waiters are now in a list and some bugs were fixed.
> 
> I think this is now ready for test. I have tested this with
> malloc() and free() instead of kalloc() and kfree(), but
> without vm_map_lookup() and assert_wait() since these functions
> segfault on my machine with GDB.

Until you can actually call it from a Hurd userspace program, don't
consider it ready for test.

> Functions thread_sleep() and clear_wait() need to be tested if
> they actually work paired this way. If somebody is willing to
> do this please let me know, here's a short test program:

The thread_sleep function pairs with thread_wakeup. You actually don't
need to implement a list (and I believe you don't even need futex_waiter
structures neither, or maybe in the hash table only), since event-based
sleeps used already existing wait queue code. In other words,
thread_sleep already puts the calling thread on a wait queue, and
thread_wakeup/thread_wakeup_one already walk that queue. Use the address
of the futex as the event.

> extern int futex_wait();
> extern int futex_wake();
> extern int thread_create();
> extern void thread_start();

If you need to do this, there is a serious problem with the exported
interface...... The public header should export *everything* you need
to use the module. As for thread functions, include kern/thread.h.

> +#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))

We need to move that into macro_help.h.

> + * Function: futex_init()

This is completely redundant, anyone can read the function name right
below...

> + * Initialization of a new futex.
> + * 
> + * Takes new futex, address and hash value arguments. Returns:
> + *   FUTEX_RESOURCE_SHORTAGE - allocation of the hash table or the array of
> + *                             futex pointers has failed
> + *   0 - success
> + *
> + */
> +static int futex_init(struct futex *futex, int *address, unsigned int 
> hash_val);

Again, this is redundant. Avoid prototyping static functions. Since
they're private, we don't need to declare them, just define them.
Prototyping static functions should only be done when there are circular
references.

Also, don't waste time commenting something that is obvious. At the same
time, you give absolutely no useful description for the hash_val
argument...

> +static void futex_wake_one_thread(struct futex *futex, int thread_num);

> +static void futex_cross_address_space_wake(struct futex *futex, vm_offset_t 
> offset);

> +static void futex_wake_threads(struct futex *futex, boolean_t wake_all);

Just do that in futex_wake, there really is no need to have so many
functions just to wrap a call to either thread_wakeup or
thread_wakeup_one.

> +static int futex_init(struct futex *futex, int *address, unsigned int 
> hash_val)
> +{
> +     if (futex_table == NULL) {
> +             if (futex_hash_table_setup() == FUTEX_RESOURCE_SHORTAGE) {
> +                     return FUTEX_RESOURCE_SHORTAGE;
> +             }
> +     }

No. Please read and understand (and ask when you don't). We do not want
to initialize such data on the fly. Create a public futex_setup function
that creates the hash table, call it from kernel startup code, and
remove this check. The code must be able to rely on the hash table being
properly initialized without checking anything.

> +     futex = (struct futex *)kalloc(sizeof(*futex));
> +     futex_table->futex_elements = (struct futex 
> *)kalloc((futex_max_hash_val + 1) * sizeof(futex));

Are you initializing the hash table slots *every* time a futex is
initialized ?? By the way, call those "buckets" or "slots", and no need
to prefix with futex_. Also, where is futex_max_hash_val initialized
(I mean, to a value different from 0) ?

Fix that, this is trivial hash table init code and you manage to fail
it...

> +int futex_wait(int *address, int value)
> +{
> +     struct futex *futex;
> +     struct futex_waiter waiter; 
> +
> +     lookup:
> +
> +     futex = futex_hash_table_lookup_address(address);
> +
> +     if (futex != NULL) {
> +
> +             simple_lock(&futex->futex_wait_lock);
> +
> +             /* If the value is still the same. */
> +             if (*address == value) {
> +                     
> +                     waiter.thread = current_thread();
> +                     
> +                     kern_return_t kr;
> +                     kr = vm_map_lookup(&current_map(), 
> (vm_offset_t)futex->address, VM_PROT_READ, NULL, NULL, 
> +                                             &waiter.offset, NULL, NULL);

What's the point of this lookup ?

> +int futex_wake(int *address, boolean_t wake_all)
> +{
> +     struct futex *futex;
> +     
> +     futex = futex_hash_table_lookup_address(address);
> +
> +     if (futex != NULL) {
> +
> +             simple_lock(&futex->futex_wait_lock);
> +
> +             futex_wake_threads(futex, wake_all);
> +
> +             simple_unlock(&futex->futex_wait_lock);
> +
> +             return FUTEX_SOME_NUMBER_RESUMED;
> +
> +     } else
> +             return FUTEX_NO_THREAD;

Please do :

if (...) {
    ...
} else {
    ...
}

So readers can easily find where the entire expression ends.

> +static unsigned int futex_hash(int *address)
> +{
> +     unsigned int hash_val = (unsigned int)address;
> +
> +     if (futex_table != NULL) {

Why would the hash function depend on the hash table ?? Just make it
"random" enough, and most importantly fast. Actually, I doubt a hash
table even is the best data structure for this. Personally, I'd use
a per-task red-black tree.

> +static int futex_hash_table_add_address(int *address)

> +static void futex_hash_table_delete_futex(struct futex *futex)

Adding addresses but removing futexes ? This lack of symmetry is very
confusing. Again, I suggest using per-task containers (backed by a
red-black tree for some scalability). What you add to this container
are the (map, address) pairs. Since they're per-task, and each task
has its own map, you actually only add the address. And that's also
what you should remove...

> diff --git a/kern/futex.h b/kern/futex.h
> new file mode 100644
> index 0000000..faa8fda
> --- /dev/null
> +++ b/kern/futex.h
> @@ -0,0 +1,115 @@
> +/*
> + * Copyright (C) 2013 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/lock.h>
> +#include <kern/list.h>
> +#include <kern/thread.h>
> +
> +/* Definitions for return values. */
> +#define FUTEX_RESUMED_BY_WAKE 0
> +#define FUTEX_NO_THREAD_SUSPENDED 1
> +#define FUTEX_SOME_NUMBER_RESUMED 2
> +#define FUTEX_NO_THREAD 3
> +#define FUTEX_MEMORY_ERROR 4
> +#define FUTEX_RESOURCE_SHORTAGE 6
> +
> +struct futex_waiter {
> +
> +     /* Futex waiters list. */
> +     struct list futex_waiters_list;
> +
> +     /* Index in the futex. */
> +     unsigned int index;
> +
> +     /* Associated thread. */
> +     thread_t thread;
> +     
> +     /* Offset from the (task map, futex address) value pair. */
> +     vm_offset_t offset;
> +};

I don't see any public use of this type. Why is it exported ?

> +struct futex {
> +     /* List of futexes. */  
> +     struct list futex_list;
> +
> +     /* Futex lock. */
> +     decl_simple_lock_data( , futex_wait_lock);
> +
> +     /* Futex address. */
> +     int *address;
> +
> +     /* Array of futex waiters at the same address. */
> +     struct futex_waiter *futex_waiters;
> +
> +     /* Hash value in the hash table. */
> +     unsigned int hash_val;
> +};

Ditto.

> +/*
> + * Function: futex_wait()
> + *
> + * This is a method for a thread to wait for a change of value at a given 
> address.
> + * 
> + * Takes address and value arguments. Returns:
> + *   FUTEX_RESUMED_BY_WAKE - thread has been resumed by futex_wake()
> + *   FUTEX_NO_THREAD_SUSPENDED - value at the address has been changed while 
> inside 
> + *                               futex_wait() and no thread has been 
> suspended
> + *   FUTEX_RESOURCE_SHORTAGE - allocation of the new futex, hash table, 
> array of futex 
> + *                             pointers or array of futex waiters pointers 
> has failed
> + *   FUTEX_MEMORY_ERROR - vm_map_lookup() has failed
> + *
> + */
> +extern int futex_wait(int *address, int value);

Remove extern.

> + * Function: futex_wake()
> + *
> + * This is a method for waking up one or all threads waiting for a change of 
> + * value at a given address.
> + * 
> + * Takes address and wake_all arguments. If wake_all is TRUE, all threads are
> + * awakened. If it is FALSE, only one thread is awakened. 
> + *
> + * Returns:
> + *   FUTEX_SOME_NUMBER_RESUMED - threads have been resumed by futex_wake()
> + *   FUTEX_NO_THREAD - futex_wake() did not found a suspended thread at the 
> + *                     passed address
> + *
> + */
> +extern int futex_wake(int *address, boolean_t wake_all);
> +
> +/*
> + * Function: futex_hash_table_setup()
> + *
> + * Setup of the global hash table.
> + * 
> + * Returns:
> + *   FUTEX_RESOURCE_SHORTAGE - allocation of the hash table has failed
> + *   0 - success
> + *
> + */
> +int futex_hash_table_setup(void);

Rename that to futex_setup. The caller should not know what happens
internally.

As a general rule, rewrite the description of the API to extensively
describe the behaviour. I personally don't recommend listing the return
codes, as it can easily change without being maintained. List a return
code only when it's special and important enough that it needs to be
mentioned. The description of the behaviour is far more important.

Also, how do you intend to handle timed waits ?

Last, but not least, when are futex objects released ?

-- 
Richard Braun