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

[Torvald Riegel <triegel at redhat dot com>]

On Fri, 2014-04-04 at 11:04 -0400, Rich Felker wrote:
> 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.

Not according to the specification at least (well, Linux man pages).  If
you've seen other specifications of the errors that allow it, please
point us to them.

> 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.

Please do.

> Of course the point is just that code already has
> to be prepared to deal with spurious wakes.

That's not true.  It's a difference whether current implementations do
this or whether they're specified to do this.  I agree that if current
implementations do this anyway, then this is encouragement that we could
update the specifications without too much risk.  But we would be
updating the specifications.

> > === 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).

I think it does because once you know that there's a pending FUTEX_WAKE,
you can wait for the notification that this one is done.

I'm not sure what you mean by "legally munmap a mutex": Which specific
case(s) do you have in mind, and why is it (/ are they) allowed by
POSIX?

> > === 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

Sorry, but I can't get more from this than that you dislike it.  And
that alone doesn't tell me much, and doesn't influence much.  If you
have technical arguments against it, please communicate those.

To give a counter-example: An MCS lock is certainly not "hideous", or do
you think it is?

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

That's true, but I would have no problem splitting the implementation of
the two if this enables us to do better things for either case.