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

[Richard Braun]

On Thu, Jan 09, 2014 at 05:06:09PM +0100, Marin Ramesa wrote:
> On 01/09/2014 03:45:35 PM, Richard Braun wrote:
> >> +/* TODO Should be per-task. */
> >> +static struct futex *pfutexes;
> >
> >Most locks are private, so yes, do work on that too.
> 
> I actually did not implement this because I don't know how.
> How to make a variable visible only and private to a task?
> I tried to find code examples of this but I don't know what
> should I look for.

Just as tasks have IPC spaces (struct ipc_space *itk_space in struct
task), you could create a "futex space" and add it to the task
structure. It's as simple as that. I said "per task", not "only visible
to one task".

> >> +static vm_offset_t futex_gen_unique_event_num(vm_offset_t sum,
> >vm_offset_t add1, vm_offset_t add2)
> >> +{
> >> +  if (sum == 0) return 0;
> >> +  
> >> +  struct rbtree_node *node;
> >> +
> >> +  for(node = futex_tree.root; node != NULL; node =
> >node->children[RBTREE_RIGHT]) {
> >> +
> >> +          struct futex *futex;
> >> +          futex = rbtree_entry(node, struct futex, node);
> >> +
> >> +          vm_offset_t futex_event_num = (vm_offset_t)futex->event;
> >> +          
> >> +          if (futex_event_num == sum) {
> >> +                  
> >> +                  if (futex_event_num - add2 == add1)
> >> +                          continue;
> >> +                  else
> >> +                          return futex_gen_unique_event_num(sum - 1, 
> >> add1, add2);
> >> +
> >> +          }               
> >> +  }
> >> +
> >> +  return sum;
> >> +}
> >
> >??
> 
> Consider a case where you have an address/map or an object
> address/offset pair
> of (x, y) and another one (z, w) where x != z and y != w, but x + y
> = z + w. So,
> in order for the events to work correctly I need to make the sum
> unique. But if
> I implement the trees differently this function might become reduntant.

That's the idea, use one global tree for shared futexes, per task trees
for private ones.

> >> +          if (private_futex) {
> >> +                  pfutexes = (struct futex *)kalloc(sizeof(pfutexes));
> >> +                  if (pfutexes == NULL)
> >> +                          return;
> >> +                  node_slot = futex_init(task, address, TRUE,
> >&pfutexes[ARRAY_SIZE(pfutexes) - 1]);
> >> +          } else {
> >> +                  shared_futexes = (struct futex
> >*)kalloc(sizeof(shared_futexes));
> >> +                  if (shared_futexes == NULL)
> >> +                          return;
> >> +                  node_slot = futex_init(task, address, FALSE,
> >&shared_futexes[ARRAY_SIZE(shared_futexes) - 1]);
> >> +          }
> >> +          if (node_slot == 0) return;
> >> +  }
> >> +          
> >> +  if (__sync_bool_compare_and_swap((int *)address, value,
> >value)) {
> >
> >What are you trying to do here ?? This call has no particular effect,
> >except being a memory barrier ...
> 
> Shouldn't the compare be atomic. Maybe I don't understand what
> atomic really
> means but the GCC manual says this function is. Or is it enough to
> hold the lock.

>From the GCC manual :
"These built-in functions perform an atomic compare and swap. That is,
if the current value of *ptr is oldval, then write newval into *ptr".
So tell us what the point of replacing oldval with itself is.

In addition, use __sync_val_compare_and_swap please.

> >> +          if (msec != 0) {
> >> +
> >> +                  simple_lock(&futex_shared_lock);
> >> +                          
> >> +                  thread_timeout_setup(current_thread());
> >> +
> >> +                  assert_wait(NULL, TRUE);
> >> +                  thread_will_wait_with_timeout(current_thread(), 
> >> (unsigned
> >int)msec);
> >> +
> >> +                  simple_unlock(&futex_shared_lock);
> >> +                  
> >> +                  thread_block(NULL);
> >> +                  
> >> +                  return;
> >> +
> >> +          }
> >
> >This can't work... You're completely isolating the bounded wait case
> >from the unbounded one. This is merely a sleep, not waiting for
> >anything.
> 
> But it works. I tested it. How do I rewrite this?

Oh I do believe the sleep works... But think again, this code isn't
waiting on any event at all, so how do you wake up the thread ??
Look at the implementation of thread_sleep to understand how to merge
this into the unbounded case.

> >> +                  simple_lock(&pfutex->futex_private_lock);
> >> +
> >> +                  pfutex->num_waiters++;
> >> +
> >> +                  pfutex->event = (event_t)futex_gen_unique_event_num
> >> +                          ((vm_offset_t)pfutex->map + address,
> >(vm_offset_t)pfutex->map, address);
> >
> >Use the address of the futex object in kernel memory for events, this
> >is the traditional way of using them.
> 
> I can't because currently I can have two futexes with the same event
> value. But
> if I implement the tree differently maybe this will be possible. I
> can get rid of
> futex_gen_unique_event_num().

Yes, do that.

-- 
Richard Braun