Re: [PATCH] futex: add FUTEX_SET_WAIT operation

Michel Lespinasse
2009-11-18T04:21:31Z

On Tue, Nov 17, 2009 at 07:24:09AM -0800, Linus Torvalds wrote:
> The FUTEX_SET_WAIT concept seems well-defined, although it sounds more
> like a FUTEX_CMPXCHG_WAIT to me than a "SET" operation. I'm not entirely
> sure that we really want to do the CMPXCHG in the kernel rather than in
> user space, since lock stealing generally isn't a problem, but I don't
> think it's _wrong_ to add this concept.
>
> In fact, CMPXCHG is generally seen to be the "fundamental" base for
> implementing locking, so in that sense it makes perfect sense to have it
> as a FUTEX model.

My first version called the operation that way, but it did *NOT* block if
val2 (now renamed setval) was already set in the futex. Turned out it helps
my use case if I do block in that situation, so I changed the operation
accordingly and renamed it into FUTEX_SET_WAIT (with a CAS model in mind,
though it's still also similar to cmpxchg in that it just returns if
the uval is not 'val' or 'setval').

> That said, I personally think the adaptive wait model is (a) more likely
> to fix many performance issues and (b) a bit more high-level concept, so I
> like Peter's patch too, but I don't see that the patches would really be
> mutually exclusive.
>
> Of course, it's possible that Michel's performance problem is fixed by the
> adaptive approach too, in which case the FUTEX_SET_WAIT (or _CMPXCHG_WAIT)
> patch is just fundamentally less interesting. But some people do need
> fairness - even when it's bad for performance - so...
>
> One thing that does strike me is that _if_ we want to do both interfaces,
> then I would assume that we quite likely also want to have an adaptive
> version of the FUTEX_SET|CMPXCHG_WAIT thing. Which perhaps implies that
> the "ADAPTIVE" part should be a bitflag in the command value?

I like the adaptive approach as well, though I'm not sure yet if it'd work
for us. I can try it but it'll take a bit of time.

One difficulty with adaptive spinning is that we want to avoid deadlocks.
If two threads end up spinning in-kernel waiting for each other, we better
have preemption enabled... or detect and deal with the situation somehow.

Also one aspect I dislike is that this would impose a given format on the
futex for storing the TID. I would prefer if there were several bits available
in the futex for userspace to do whatever they want. 8 bits would likely
be enough, which leaves 24 for the TID - enough for us, but I have no idea
if that's good enough for upstream inclusion. It that's not possible,
one possible compromise could be:

- userspace passes a TID (which it extracted from the futex value; but kernel
does not necessarily know how)
- kernel spins until that TID goes to sleep, or the futex value is not equal
to val or setval anymore
- if val != setval and the futex value is val, set it to setval
- if the futex valus is setval, block, otherwise -EWOULDBLOCK.

If the lock got stolen from a different thread, userspace can decide to
retry with or without adaptive spinning.

That would be the most generic interface I can think of, though it's
starting to be a LOT of parameters - actually, too many to pass through
the _syscall6 interface.

I also like Darren's suggestion to do a FUTEX_SET_WAIT_REQUEUE_PI,
but it's hitting the same 'too many parameters' limitation as well :/

--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.