gpderetta (gpderetta.delete@this.gmail.com) on January 15, 2020 3:28 am wrote:
> Travis Downs (travis.downs.delete@this.gmail.com) on January 14, 2020 10:06 am wrote:
> > [1] One could imagine a lock that uses the control word to indicate the usual stuff like "some waiters",
> > and then the unlocker does first a check to see if the lock is in the uncontended state (i.e., just the
> > "locked" bit set, no waiters indicated), and if so does a plain store, but if not falls back to the slower
> > full handling path using CAS. Now there is a race between that check and the store, but maybe you "fix"
> > that by having the waiters periodically wake up and check to see what's going on, or a separate thread
> > that does that (e.g., checks for locks that are unlocked but have waiters), and newly arriving lockers can
> > make that check too. Since this race may often be rare, maybe it doesn't happen often. Frankly this sounds
> > terrible, but if you *really* want to cut out of one of the CAS operations you could try it.
> >
> >
>
> Java has an optimization, known as biased locking, in its lock implementation where it can avoid a CAS
> even in the acquire path for locks that have never been contended. Basically a lock would effectively
> always stay in the acquired state after the first acquisition, so lock and unlocks are almost no-ops.
> To switch the lock back to the normal state waiters need to somehow signal the owner to change state.
> This is an expensive operation and requires, I think, the equivalent of a sys_membarrier.
>
> I think that's a similar schema to what you have in mind and it might be
> important in Java, where pretty much every object has a embedded mutex.

Assuming you are talking about the CAS-avoiding lock in [1], then yeah a bit, and biased locking crossed by mind while writing it! It's still quite similar to a regular lock though: it only eliminates 1 of the two CASes, not both as biased locking does. The potential speedup of eliminating that second CAS is large, compared to the first which 2x at best.

Yeah, I think you could do biased locking in native code too, but yeah you'd need some way to detect that the privileged thread has left the lock after the revocation, i.e., that it guaranteed to see the revocation, before other threads can proceed. I think you could do it with a Dekker-style thing in concert with sys_membarrier, but at the cost of the privileged thread needing to do a (non-atomic) flag write on entry and exit.

Otherwise, you could detect a safe (quiescent?) period some other way, e.g., when the priviledged thread passes through some point it is known not to hold the lock and this would allow even faster biased performance since no flag writes are needed on the fast path.

Of course, all of these approaches rely on a really fast way to get the thread id (or some other suitable identifier for the current thread), so that the "am I the privileged thread". pthread_self is not going to be fast enough, so you'd probably have to try something with an ID stored in TLS, like:

https://godbolt.org/z/LyNVgY

The PIE version (on top) looks fine, but the -fPIC version is pretty terrible although I guess there is some linker magic to clean it up depending on how the object actually gets used.