[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]

Re: Poor condvar performance

Hash: SHA1

Jamie Lokier wrote:

> But without a list, how do you know what value of nr_wake to pass to
> FUTEX_REQUEUE2 for broadcast?
> [...]
> If all the waiters are on the same mutex, you want to wake one and
> requeue the rest.  If they are different mutexes, you want to take
> as many as there are separate mutexes.

Look at the current requeue interface.  There are two numbers:

~ the number of threads to wake
~ the number of threads to requeue

cond_broadcast always passes 1 and INT_MAX.  The context for the threads
which are requeued will contain the information with which to locate the
destinate futex.

> Another problem is that FUTEX_REQUEUE2 is harder to implement if there
> are different waiting mutex addresses.


> More hash lists than 2 are
> involved, which could make the kernel implementation quite hairy
> (because of the hashed spinlocks), unless we say that the requeue
> operation is no longer atomic and can be done as dequeue followed by
> requeue.

I wouldn't object if in this case all threads are simply woken since the
POSIX specs require the same mutex to be used.  But in this case it
might be best to fail at the time the FUTEX_WAIT2 call is made.  If
there is already a waiter which registered a different requeue futex,
fail the FUTEX_WAIT2 call.

> On the other hand, getting rid of the list makes it much easier to
> ensure waiters are woken in FIFO order.  To do FIFO with the list
> would require two intertwined lists in userspace, and more
> FUTEX_REQUEUE2 calls in some cases.

Where does FIFO comes in here?  There are no FIFO guarantees.  Ideally
the futex wakeup functionality will at some point get some intelligence
and either do implement FIFO or, better IMO, a policy which prefers
threads with hot caches.  The POSIX specs does not guarantee anything
for regular thread.

When it comes to RT you'll have to look at priorities and this is a
completely different ballgame.

> If we requeue any, we need the mutex state to reflect that it has
> waiters, and if we didn't, to reflect that, otherwise when the holder
> of the mutex eventually releases it it will have to call futex_wake
> unconditionally.

That's a completely separate issue and far less critical.  Think fast
syscalls which we have on x86, amd64, ia64 now.  With the the extra
syscall isn't that bad.  It might be possible to think about this at
some point but it's IMO a micro optimization.  Let's not lose focus.
There are many much more important problems.

> At the moment, futex_requeue returns the number of requeued waiters,

No, it returns the number of threads woken plus the number of threads

> so the caller of futex_requeue can be responsible for setting the
> mutex state so as to indicate waiters or not.

When Ingo and I started I've experimented _a lot_ with more elaborate
mechanisms which do refcounting etc.  They all failed under stress
sooner or later.  I don't say it's not possible, but it'll require large
amounts of support code.  You'll once again have to register handlers to
help in situations like cancellation or signal handling.  Things we had
to do with LinuxThreads and don't have to do now.  All this overhead
would slow down the ordinary operations and my expectations are that the
result is worse than what we have today.

> These two problems suggest that FUTEX_REQUEUE2 should not be passed
> separate nr_wake and nr_requeue values, but instead should modify each
> waiter's mutex word, [...]

I don't agree because just like today, I don't see any more clever
method at userlevel workable.  Just have this one little semantic change
(the futex address is part of WAIT2 instead of REQUEUE2) and the rest of
the implementation can stay the same.  If you want to go for a
completely different implementation try it with the existing futex
functionality first.  Try to make it reliable.  Then you can talk about
these optimizations.

> One thing that would be very easy: currently futex_wait returns 0 if
> woken.  We could change that so a parameter passed to futex_wake or
> futex_requeue is the value to return from futex_wait.  That opens all
> sorts of token-passing possibilities.  Have a think about whether you
> would find that useful.

It might be that this is useful, I haven't stumbled across any situation
where I needed it.  Know that you planted that idea in my head I'll
think about it.

Once again, first priority for me is to get the implementation stable
and well performing.  The simple REQUEUE2 interface can help.  It's a
very specific interface, just like REQUEUE itself.  But the amount of
additional code shouldn't be large to justify adding it.

[PS: I haven't forgotten to send you the collected futex ideas.  I
simply haven't found the time to write it down yet.]

- -- 
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
Version: GnuPG v1.2.3 (GNU/Linux)


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]