futex: Implement futexes with CVs
authorBarret Rhoden <brho@cs.berkeley.edu>
Mon, 15 Oct 2018 20:24:50 +0000 (16:24 -0400)
committerBarret Rhoden <brho@cs.berkeley.edu>
Mon, 22 Oct 2018 23:35:50 +0000 (19:35 -0400)
commitb82d69219273ca96aa5453e0ddad26cfe5939567
tree8740f2f1fbadc4069fa4972371db33780d2b3600
parent47c2cf2efd4ede802b233c285dd3ba09d338b4f2
futex: Implement futexes with CVs

This version is similar to the old one in that we still have a single
futex_element per futex_wait call, and there is a linked list of these
elements.  Future versions could use a hash table or something.

You could even consider having M:1 waiters to addresses, with those
structs in a hash table.  If you do this, consider keeping the futex
elements forever.

The thing to be careful of is the lifetime of the futex element.  This
is something the old code had a hard time with, and this new code is no
exception.

The old version had hand-rolled the timeout.  Although the new code
avoids the duplicated issues there, the one benefit of the timeout was
that it yanked 'e' off the list, such that if the futex_wait() uthread
was running, then we knew it was off the list.  In the current version,
we must yank it off the list, and then wait for any users (futex_wake())
to be done with it.  Fun with shared memory synchronization!  The
current approach is similar to the old awaiter.data = NULL approach, but
this is more explicit.

Here are a few other things I considered:
- Put the futex element in the uthread/pthread: our thread could exit,
  instead of just unwinding the stack, so this is broken.  It's still a
use-after-free issue.

- Have a custom timeout with the CV, and have the timeout just do
  futex_wake: Not a bad idea.  I wanted to use the CV infrastructure
instead of rolling our own.  We'd also need a bit to signal that the
wakeup was a timeout.  Also, in future versions, I want to use a single
CV for multiple waiters, and this would break that.

- Never have the waker yank the CV element, just kick the CV: We still
  have the lifetime issues.  Even if we know we didn't timeout, we still
could have another waker (consider multiple threads calling
futex_wake()).  The root cause here is that the waker kicks the CVs
outside the futex lock, which was an attempt to cut down on the number
of locks held across 2LS ops.  Though note the CV lock *is* held across
some 2LS ops (has_blocked).

- Have the waker grab the CV lock while holding the futex lock, in an
  attempt to transfer the lock.  The rule is to hold both locks when
adding/removing an element from the list: That would work, but would
require the waiter to do a trylock (lock ordering), and handling the
fallback (unlock CV, then lock for real).  I'd like to avoid gratuitous
global locking.

- Don't have elements at all, use a single CV: we want to wake based on
  uaddr, which would require knowing the waiters that waited on a
specific addr.  A CV per addr works.  (Right now, we have a CV per
waiter).

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
user/pthread/futex.c