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