bug-hurd
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


From: Richard Braun
Subject: Re: [RFC] kern: simple futex for gnumach (version 6)
Date: Fri, 27 Dec 2013 19:14:40 +0100
User-agent: Mutt/1.5.21 (2010-09-15)

On Fri, Dec 27, 2013 at 04:28:33PM +0100, Marin Ramesa wrote:
> On Hurd tests fail with a segmentation fault in kalloc() (GDB says kalloc()
> segfaults in vm_map_find_entry()). On Linux everything works except segfaults
> in vm_map_lookup(), assert_wait(), thread_block() and kalloc() that are to be 
> expected since gnumach is not running.

What do you mean when you say you test on the Hurd and Linux ? How do
you use GDB with Mach to determine it's actually kalloc thta segfaults ?

> +typedef struct futex_hash_table *futex_hash_table_t;

I should have talked about this earlier, but since this is an incremental
review process, let's say it's OK to mention it now.

It's traditional in Mach to use custom types to structure pointers, but
this is actually bad practice. Simply use the struct keyword, and avoid
defining types. This makes the code clearer as a reader directly knows
the type.

> +static futex_hash_table_t table = NULL; 
> +static unsigned int max_hash_val = 0;

I strongly recommend using the module namespace for everything global,
including static variables and functions. Otherwise ...

> +int futex_init(futex_t futex, int *address)
> +{
> +     if (table == NULL) {

... you may wonder where things such as table here are from.

> +             futex->chain.next = &futex->chain;
> +             futex->chain.prev = &futex->chain;

Isn't there a queue_init somewhere ? Also, I advise new code to use the
kern/list module which uses mostly inline functions.

> +             if (futex_hash_table_init() == FUTEX_RESOURCE_SHORTAGE) {
> +                     return FUTEX_RESOURCE_SHORTAGE;
> +             }
> +     }

You should write a public function to initialize the global table once
at startup and never have to check later. I personally use xxx_setup to
avoid confusion between initializing a runtime module (setup) and
initializing the content of an already allocated structure (init).

> +     if ((table->futex_elements = 
> (futex_t)kalloc((max_hash_val+1)*sizeof(futex_t))) == NULL) {

Another bad practice warning, don't put statements with side effects
in conditional expressions. Some spaces around arithmetic operators
please. And make it a habit of using sizeof on variables rather than
types, to make it easy to change types without rewriting too much code.

> +int futex_wait(int *address, int value)
> +{
> +     futex_t futex;
> +     futex_thread_t thread = NULL; 

Do NOT call the per-thread futex structure "thread". It's NOT a thread.
This leads to confusion and error-prone code. Use something like
futex_waiter.

> +     lookup:

Have you tried without gotos ? Do they really improve things ? We tend
to use gotos for a centralized exit path, it's really not the rule to
use them that way.

> +     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) {
> +
> +                     /* Add the thread to the futex. */                      
> +                     int ret;
> +
> +                     if ((ret = futex_thread_init(futex, thread)) != 0)

As I mentioned in my previous review, you shouldn't need to allocate the
per-thread structure through the kernel allocator. A thread can only be
doing one wait at a time, so allocate it on the stack.

> +     suspend:
> +             assert_wait(&thread->thread->state , FALSE);
> +             simple_unlock(&futex->futex_wait_lock);
> +             thread_block(NULL);
> +             thread_wakeup(&thread->thread->state);

I'm not sure to understand that wakeup following the blocking... If the
code isn't obvious, comment it. When you add a comment, ask yourself if
you can rewrite the code in a way that makes the comment moot.

Also, look at thread_sleep, which seems to make using assert_wait /
thread_block a little more straightforward, at least guaranteeing the
correct handling of the interlock. I guess it's paired with
thread_wakeup_prim, which also handles an event (and you could use the
futex address for that) and can wake either one or all threads waiting,
probably making your life easier.

> +int futex_wake(int *address, boolean_t wake_all)
> +{
> +     futex_t futex, temp_futex;
> +     
> +     temp_futex = futex_hash_table_lookup_address(address);
> +     
> +     if (temp_futex != NULL) 
> +             futex_cross_address_space_wake(temp_futex, wake_all);
> +     else
> +             goto no_thread;
> +     
> +     futex = futex_hash_table_lookup_address(address);

Two lookups ?? I don't understand what your code is supposed to be doing
at all here...

> +void futex_wake_one_thread(futex_t futex, int thread_num)
> +{
> +     
> clear_wait((&(futex->futexed_threads[futex->num_futexed_threads]))->thread, 
> THREAD_AWAKENED, FALSE);
> +     futex->num_futexed_threads--;
> +     
> kfree((vm_offset_t)&(futex->futexed_threads[futex->num_futexed_threads]), 
> sizeof(futex_thread_t));

This looks ugly. What are you releasing here ? The per-thread structure
allocated in futex_wait ? In that case, the target thread might end up
trying to use memory that has already been freed by the waker. And this
is the kind of mistakes that someone with proper experience with
concurrency would not do.

I may already have said that, but better safe than sorry so: I don't
see the point of maintaining the number of threads.

> +void futex_cross_address_space_wake(futex_t futex, boolean_t wake_all)
> +{
> +     #define min(x, y) (x <= y ? x : y)
> +
> +     queue_iterate(&futex->chain, futex, futex_t, chain) {
> +
> +             simple_lock(&futex->futex_wait_lock);
> +
> +             int i;
> +
> +             for (i = 0; i < min(futex->num_futexed_threads, 
> +                     ((futex_t)futex->chain.next)->num_futexed_threads); 
> i++) {

If you have a list, you just walk it, there is no need to count the
number of items.

> +                             
> futex_wake_one_thread((futex_t)futex->chain.next, i);
> +                             
> +                             if 
> (((futex_t)futex->chain.next)->num_futexed_threads == 0) {
> +                                     simple_unlock(&futex->futex_wait_lock);
> +                                     
> simple_unlock(&((futex_t)futex->chain.next)->futex_wait_lock);
> +                                     
> futex_hash_table_delete_futex((futex_t)futex->chain.next);
> +                                     #undef min
> +                                     return;                         
> +                             }
> +                     }
> +             }
> +     
> +             simple_unlock(&((futex_t)futex->chain.next)->futex_wait_lock);
> +             simple_unlock(&futex->futex_wait_lock);
> +             
> +     }
> +
> +#undef min

This isn't C, it's a preprocessor directive, and you've already
undefined min earlier.

> +void futex_wake_threads(futex_t futex, boolean_t wake_all)
> +{
> +     if (wake_all) {
> +             int i;
> +             for (i = 0; i < futex->num_futexed_threads; i++) 
> +                     futex_wake_one_thread(futex, i);
> +     } else 
> +             futex_wake_one_thread(futex, futex->num_futexed_threads-1);
> +}

What's the difference between this and futex_cross_address_space_wake ??

> +unsigned int futex_hash(int *address)
> +{
> +     unsigned int hash_val = 0;
> +
> +     hash_val = (unsigned int)address + (hash_val << 5) - hash_val;
> +
> +     if (table != NULL) {
> +             unsigned int ret = hash_val % table->size; 

A modulo is expensive. Make the hash table size a power-of-two and use
an AND.

> +int futex_hash_table_add_address(int *address)
> +{
> +     futex_t new_futex;
> +
> +     unsigned int hash_val = futex_hash(address);
> +
> +     if (table != NULL) {
> +             simple_lock(&table->futex_hash_table_lock);
> +     }
> +
> +     if ((new_futex = (futex_t)kalloc(sizeof(struct futex))) == NULL) {
> +             if (table != NULL)
> +                     simple_unlock(&table->futex_hash_table_lock);

Uh ? Do you have a hash table or not ? How can this work if it's not
there ??

> +     table->futex_elements[hash_val] = *new_futex;
> +     table->size++;

Looks like you have one after all...

> +int futex_thread_init(futex_t futex, futex_thread_t thread)
> +{
> +     if ((thread = (futex_thread_t)kalloc(sizeof(futex_thread_t))) == NULL)

Why do you pass thread as an argument ?? This means futex_wait is bound
to crash on its first access to the "thread" variable...

> +             return FUTEX_RESOURCE_SHORTAGE;
> +     
> +     thread->thread = current_thread();
> +     thread->futex = futex;
> +
> +     *thread->map = current_map();

You don't have to store the map since you can find it through the task
of the thread.

> +     if ((vm_map_lookup(thread->map, (vm_offset_t)futex->address, 
> VM_PROT_READ, thread->version, thread->object,
> +                             thread->offset, thread->out_prot, 
> thread->wired) != KERN_SUCCESS)) {
> +             kfree((vm_offset_t)thread, sizeof(struct futex_thread));
> +             return FUTEX_MEMORY_ERROR;
> +     }

Futexes are only concerned with (map, address) pairs, why are
VM objects involved ?

> +++ b/kern/futex.h

The public header should at least define struct futex as an opaque type.

> +++ b/kern/futex_i.h

You didn't use the private header correctly. What you put into it
should instead be declared as static functions inside the .c file.

There are undoubtedly other problems but I don't have the time nor
the motivation to look through them now. If you really insist on this
task, you should really, really, REALLY get better with the basics
first. There are just too many mistakes here to do anything with that
patch.

-- 
Richard Braun



reply via email to

[Prev in Thread] Current Thread [Next in Thread]