[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20140808204855.GQ1674@brightrain.aerifal.cx>
Date: Fri, 8 Aug 2014 16:48:55 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Re: Explaining cond var destroy [Re: C threads, v3.0]
On Fri, Aug 08, 2014 at 03:14:06PM -0400, Rich Felker wrote:
> I think I may have a solution you'll like:
>
> We can perform the release of the lock via a compare-and-swap rather
> than a simple swap. In this way, we can know before releasing the lock
> whether it's going to require a wake or not:
>
> - If waiters was zero and the cas from owned/uncontended to zero
> succeeds, no futex wake operation is needed.
>
> - If waiters was nonzero, or if the cas fails (thereby instead
> requiring a cas from owned/contended to zero), we can do the
> following:
>
> Don't use a userspace CAS to release; this would allow the lock to be
> acquired by another thread, released, destroyed, and freed before the
> futex wake is performed. Instead, use FUTEX_WAKE_OP to atomically
> perform the atomic assignment and futex wake.
FUTEX_WAKE_OP is highly under-documented, and i'm worried it might be
unsupported on some archs (since the atomics for it have to be
implemented on a per-arch basis in the kernel) but of course we can
just fallback on archs where it's not supported yet.
Anyway, the behavior seems to be:
- Futex acquisition for uaddr1 and uaddr2 both happen prior to the
atomic operation, and this hold locks that seem to prevent new
waiters on the futex(es). This should preclude any risk of waking a
new waiter that arrives after the atomic operation, as desired.
- Both uaddr1 and uaddr2 are hashed, with no check for equality. This
is a fairly costly wasteful operation, but could be fixed on the
kernel side. At present I suspect they don't care because
FUTEX_WAKE_OP is considered unnecessary, but if I raise it on the
glibc bug tracker thread for issue 13690 as a solution to the
problem, I think there would be a lot more interest in optimizing
this kernel path.
- After the atomic operation is performed, a wake is always performed
on uaddr1 (based on the previous acquisition); this fact is omitted
from all the documentation, but it's obviously intentional since
otherwise the uaddr1 argument would not be used for anything but
wasting time. The wake on uaddr2 is conditional on a comparison.
- No allocation is required anywhere in the operation, so we don't
have to worry about lost actions on OOM. For plain FUTEX_WAKE this
would not have been an issue (if acquirin the futex required memory,
then failure for FUTEX_WAKE to acquire it would mean there was no
FUTEX_WAIT taking place anyway), but for FUTEX_WAKE_OP, failure
would omit the atomic operation, which must take place even if there
are no current FUTEX_WAIT waiters (e.g. if the FUTEX_WAIT was
interrupted by a signal handler).
Based on the above, I think it's safe to move forward with using
FUTEX_WAKE_OP. It seems optimal to me to use uaddr1==uaddr2 and a
comparison that always yields false, so that the wake only goes to
uaddr1. This will allow the kernel to optimize out double-hashing in
the future by checking for uaddr1==uaddr2, and already optimizes out
the double-iteration of the hash bucket for waking purposes.
Any further thoughts on the matter? I think we should finish the
private futex support task before starting on this, so that we don't
do new work that's going to conflict with a pending patch.
Rich
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
