Re: [RFC] mutex destruction (#13690): problem description and workarounds

[Rich Felker <dalias at aerifal dot cx>]

On Fri, Apr 04, 2014 at 04:20:30PM +0200, Torvald Riegel wrote:
> === Workaround 1: Specify that spurious FUTEX_WAKE calls are possible
> 
> FUTEX_WAIT is currently specified to return 0 if it got woken by a
> FUTEX_WAKE call, and EINTR when wake-up happened due to a signal or
> other spurious wakeup.  The memory reuse thus possibly allows for
> unrelated FUTEX_WAKE calls being injected into the code running a new
> futex after memory reuse.  If this code relies on the FUTEX_WAIT return
> values to be correct (just regarding 0 vs. EINTR!), the pending
> unrelated FUTEX_WAKE calls can break it.

Spurious futex wakes are already possible anyway. I have not been able
to track down the cause, but they come from the kernel and look
exactly like a FUTEX_WAKE, i.e. the wait operation returns 0 rather
than an error. I have a test case I can dig up and post for this if
you're interested. Of course the point is just that code already has
to be prepared to deal with spurious wakes.

> === Workaround 1a: New FUTEX_WAKE_SPURIOUS operation that avoids the
> specification change

Does not seem useful to me.

> === Workaround 2: New FUTEX_UNLOCK operation that makes resetting the
> futex var and unblocking other threads atomic wrt. other FUTEX_WAIT ops
> 
> This is like UNLOCK_PI, except for not doing PI.  Variations of this new
> futex op could store user-supplied values, or do a compare-and-set (or
> similar) read-modify-write operations.  FUTEX_WAKE_OP could be used as
> well, but we don't need to wake another futex (unnecessary overhead).
> (I haven't checked the kernel's FUTEX_WAKE_OP implementation, and there
> might be reasons why it can't be used as is (e.g., due to how things are
> locked regarding the second futex).

Rather than "unlock" with fixed zeroing semantics, I think it should
just be FUTEX_SET that sets the futex value atomically with waking one
or more waiters. This could be used for lots of purposes, not just
unlocking.

> The biggest performance drawback that I see is a potential increase in
> the latency of unlocking any thread (blocked *or* spinning) when any
> thread is blocked.  This is because we'll have to ask the kernel to
> reset the futex var (instead of, like now, userspace doing it), which
> means that we'll have to enter the kernel first before a spinning thread
> can get the okay to acquire the lock.  This could decrease lock
> scalability for short critical sections in particular because those
> effectively get longer.

Only in the contended case, but yes, I see how that could be an issue.

> === Workaround 3: Tell mutex destruction about pending FUTEX_WAKEs

This doesn't solve the problem at all because it's not just
destruction you race with. You can legally munmap a mutex in shared
memory without destroying it (since another thread or process could be
responsible for destroying it).

> === Workaround 4: Only use futexes in non-reused memory.
> 
> This doesn't avoid the pending FUTEX_WAKEs, but makes them manageable by
> redirecting any blocking on things like mutexes to separate blocking
> constructs.  For example, we could have per-thread futexes for blocking
> (each thread will only block on one thing concurrently) in memory that
> won't be reused for anything but such futexes.  This could require some
> more work at thread destruction, but should be doable I guess.
> 
> The normal synchronization constructs would then install pointers to
> those futexes (or the enclosing data structures) when they actually
> block, and potentially build lists/queues of those.  Thus, this would
> kind of duplicate what the kernel is doing for futexes, but we'd get all
> the flexibility we'd need to build whatever we need (e.g., to solve the
> pending FUTEX_WAKE problem, to have 64b futexes, etc.), and optimize how
> we need it (and using the information that glibc might have, but the
> kernel doesn't have).

This is hideous and does not work with process-shared synchronization
objects anyway, so I don't think it's a solution.

> === Summary / RFC
> 
> IMO, workarounds 1, 1a, or 2 might be the best ones, although 4 might
> also be good.
> 
> Do you see any other options, or have comments on those above?

I'm not aware of any others. FYI I use option 1.

Rich