Locking in WebKit

#1

Post by pizlonator » Fri, May 06, 2016, 3:03 PM UTC

Re: Locking in WebKit

#2

Post by emehrkay » Fri, May 06, 2016, 5:13 PM UTC

Random observation: WTF would be a great base exception in a new, hip programming language.

   WTF.happened
   WTF.context
   ...and so on

Re: Locking in WebKit

#3

Post by exDM69 » Fri, May 06, 2016, 5:28 PM UTC

One byte per mutex sounds a bit suspicious given that atomic operations typically work on a word or cache line granularity. If you have two mutexes in the same cache line, false sharing occurs and the CPU interconnect gets busy. Locking two uncontended mutexes in same cache line on different cores ends up executing serially because the cores need to snoop each other's caches.

Some benchmarks might be useful to see how this affects performance and CPU perf counters.

Re: Locking in WebKit

#4

Post by cokernel_hacker » Fri, May 06, 2016, 5:34 PM UTC

Spinning in locks are always tricky business.

The sharpest thorn, to me, is: what happens when you are running inside the critical section and your thread gets preempted?

Well, now the next thread which tries to acquire the lock is stuck waiting. But waiting for what? Waiting for the original thread to get scheduled.

Now, the OS has no idea that the original thread should get scheduled again and is free to continue scheduling more and more work items.

Fortunately for the lock in this article, and most other locks which spin, it is adaptive and will not spin for too long. But how long is long enough? If the spin is timed for a few loads and stores, then all is probably well as spins will not be attempted for very long.

I wonder how these locks figure out how long they should spin? In the nasty case I previously mentioned, you'd want to spin for a very short while to avoid large amounts of waste. But spins which are too short lead to higher lock/unlock latency if the lock was held for any appreciable amount of time.

This leads me to the following conclusion: spinning inevitable leads to _some_ number of wasted CPU cycles and therefore increased latency.

I'm curious as to how the amount of spinning was chosen.

Re: Locking in WebKit

#5

Post by eridius » Fri, May 06, 2016, 5:43 PM UTC

Two things come to mind when reading this:

1. WTF::Lock is using sequential consistency for all of the slow path operations. Surely this isn't necessary and it could still use acquire/release for most of them (like it does in the fast path).

2. Ditching OS-provided mutexes has one possibly-important drawback on OS X and iOS: lack of priority donation. Recent versions of OS X and iOS have a Quality Of Service implementation in the kernel that classifies threads (and libdispatch queues) according to one of several QOS levels, and then handles normal thread priorities within those levels. For this reason you actually cannot safely implement your own spinlock, as I documented a few months ago (http://engineering.postmates.com/Spinlocks-Considered-Harmfu... it'll appear to work under many normal workloads, but once you start using the spinlock from threads of different QOS levels at the same time, you risk hitting a priority inversion livelock where a lower-QOS thread has the spinlock locked but is never scheduled because higher-QOS threads spinning on the lock are always given priority. The OS does actually have a safe spinlock (which does priority donation), but it's not public API and so can't be used outside of system code. Of course, this doesn't apply to adaptive spinlocks, since they'll just end up in the slow path of parking their thread, but this does still serve to highlight the issue they do have, which is if a high-QOS thread is parked waiting for a lock that's owned by a low-QOS thread, the high-QOS thread is effectively having its priority lowered to the low QOS until the owning thread releases the lock. This is obviously not what you want. The system-provided pthread_mutex_t does priority donation specifically to fix this issue, but WTF::Lock doesn't.

Re: Locking in WebKit

#6

Post by pron » Fri, May 06, 2016, 5:45 PM UTC

The talk Engineering Concurrent Library Components, by Doug Lea, is one of the best overviews of the issues surrounding the design and implementation of low-level concurrency building blocks: https://www.youtube.com/watch?v=sq0MX3fHkro

Re: Locking in WebKit

#7

Post by pron » Fri, May 06, 2016, 5:46 PM UTC

cokernel_hacker wrote: post #4

Spinning in locks are always tricky business. The sharpest thorn, to me, is: what happens when you are running inside the critical section and your thread gets preempted? Well, now the next thread which tries to acquire the lock is stuck waiting. But waiting for what? Waiting for the original thread to get scheduled. Now, the OS has no idea that the original thread should get scheduled again and is free to continue s…

See the Doug Lea talk I linked to in another comment. Turns out that even the process of spinning is itself not so simple on some new processors.

Re: Locking in WebKit

#8

Post by skocznymroczny » Fri, May 06, 2016, 5:50 PM UTC

emehrkay wrote: post #2

Random observation: WTF would be a great base exception in a new, hip programming language. WTF.happened WTF.context ...and so on

there's Log.wtf method in Android for errors that shouldn't have happened

Re: Locking in WebKit

#9

Post by poizan42 » Fri, May 06, 2016, 5:50 PM UTC

emehrkay wrote: post #2

Random observation: WTF would be a great base exception in a new, hip programming language. WTF.happened WTF.context ...and so on

Android has Log.WTF which of course stands for What a Terrible Failure (and totally not that other word, the similarity is a complete coincidence /s )

Re: Locking in WebKit

#10

Post by cpeterso » Fri, May 06, 2016, 5:53 PM UTC

emehrkay wrote: post #2

Random observation: WTF would be a great base exception in a new, hip programming language. WTF.happened WTF.context ...and so on

Android has a Log.wtf() method for logging "What a Terrible Failure" conditions:

http://developer.android.com/reference/android/util/Log.html...