Correctly implementing a spinlock in C++
86 comments · 86% upvoted · source · other discussions
comments
[deleted]
AmunRa
If you’re interested in user space techniques for “better” locks (for specific use-cases) then Facebook’s Folly library has some interesting ideas - for example SharedMutex and DistributedMutex
max0x7ba
On Linux one can use an adaptive mutex that does limited spinning in userspace before blocking in the kernel.
[deleted]
Is this still correct though?
For TTAS, shouldn't the code be:
bool try_lock() noexcept {
if (lock.load(std::memory_order_relaxed) == true) {
return false;
}
return !lock_.exchange(true, std::memory_order_acquire);
}
rigtorp [OP]
I've seen a lot of poor spinlock implementations using `std::atomic_flag`, likely copied from the example code here https://en.cppreference.com/w/cpp/atomic/atomic_flag. So I wrote this short note on how to correctly implement a spinlock in C++.
peppedx
permalink
permalink
permalink
permalink
permalink
permalink
permalink
rigtorp [OP]
Timur's spinlocks exhibits the spin on RMW operation flaw.
tvaneerd
atomic_flag.test_and_set() might do test-and-test-and-set internally, meaning the flaw isn't there. IIUC.
rigtorp [OP]
GCC and clang implements it as a single XCHG instruction: https://godbolt.org/z/ZN2b_n
tvaneerd
good to know.
Why didn't I just use godbolt?
This needs to be a slogan "Why didn't I use godbolt" or "Next time I'll use godbolt", "I should have godbolted", etc.
The weird part is that technically doesn't tell you how it is implemented, it tells you what is left after the compiler is done with it - a compiler could take test-and-test-and-set and remove the first test! (Although I hope it doesn't and doubt any do.)
But no sane compiler would optimize atomics. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4455.html
rigtorp [OP]
It will work with the new C++20 std::atomic_flag::test(): https://godbolt.org/z/AAGEE3
TheThiefMaster
No, release is only necessary if you want to make other unsynchronized writes visible to the next thread to acquire from that write - that's necessary when un locking but when taking a lock you only want to synchronize against anything the previous lock holder did before it unlocked - i.e. you need an acquire exchange on acquiring the lock, and a release exchange on releasing it.
SavingsLocal
Really cool article. I don't know that I'll ever use it or what it could be useful for, but the way you identified a problem through superior mindfulness and created a solution is awesome.
I don't even know if the article is right, because there's too many gaps in my knowledge. Such as with the benchmark, if one thread is grabbing it 100m times, then the next thread 100m times, sequentially. Or with the cache coherency logic, if the atomic exchange only requests write access if the operation succeeds. But whether it's correct or not, it's still awesome.
rigtorp [OP]
The exact details of the cache coherency protocols for Intel CPUs are proprietary as far as I know. You can create programs that pokes at memory using atomic operations in different ways and observe the CPU performance counters to try and see how it's implemented under the hood.
mmomtchev
bionic-unix
But method exchange is also a writing action. Should the order be acq_rel rather than acquire?
rigtorp [OP]
matthieum
I don't think you need Release semantics when acquiring the lock.
Release semantics are to prevent writes from migrating after the Release, which is only necessary on unlock.
tvaneerd
Depends if you want to prevent two lock regions from overlapping.
x = 10;
lock();
y = 11;
unlock();
z = 12;
The write to y can't move outside the lock, but x and z can move into the lock region (so the order might end up being z, y, x). This is fine - if it wasn't, you would have put x and z inside locks somehow.
But what about this:
lock1();
y = 11;
unlock1();
lock2();
z = 12;
unlock2();
If you are not careful about your memory orders for unlock and lock, this can become:
lock1();
y = 11;
lock2();
unlock1();
z = 12;
unlock2();
ie your locks have overlapped. This might be OK, but it might also cause deadlocks in cases you were not expecting.
rigtorp [OP]
You are right. Release semantics on unlock doesn't prevent later stores from being reordered before the release. Lock acquisiton needs to be std::m_o_acq_rel to prevent loads and stores from being re-ordered either way. (http://eel.is/c++draft/intro.multithread#intro.races-3)
rigtorp [OP]
Actually reading http://eel.is/c++draft/intro.multithread#intro.races-9.3.1 acquire is enough to prevent the lock2()-unlock1() re-ordering:
unlock1() (A) inter-thread happens before lock2() (B) because: store-release of unlock1() (A) synchronizes with acquire-load of lock1() (X) which is sequenced before lock2 (B).
tvaneerd
Hmmm, not so sure about that. In particular:
store-release of unlock1() (A) synchronizes with acquire-load of lock1() (X)
A release syncs with an acquire if the acquire sees that value left by the release. http://eel.is/c++draft/atomics.order#2.sentence-1
That doesn't happen here.
rigtorp [OP]
You keep on thinking about consume semantics, I'm using acquire-release semantics. acquire-release semantics affect the ordering of all loads and stores, not only those on the consume dependency chain.
The standard explicitly states that mutex lock() is acquire and unlock() is release, so that acquire-release should be sufficient.
Look at rule 9.3.1 again http://eel.is/c++draft/intro.multithread#intro.races-9.3.1. It states that unlock1() must inter-thread happen before anything that is sequenced after unlock1().
Look at rule 9.3.2. It states that any evaluation before unlock1() must inter-thread happen before anything sequenced after unlock1(). It also states that since lock1() inter-thread happens before unlock1(), anything sequenced before lock1() must inter-thread happen before lock1().
This means unlock1() must be a load-store barrier and indeed checking ARM output on godbolt we see that GCC and clang generates a load-store barrier: https://godbolt.org/z/QMf6Ls
DMB ISH is a load-store barrier: http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.kui0100a/armasm_cihjfgfe.htm
tvaneerd
Why would I ever think about consume semantics? Why would anyone? :-)
rigtorp [OP]
Because I think what you are stating is correct under consume semantics but not acquire. Yeah does any compiler even implement consume other than as a alias for acquire?
tvaneerd
The committee isn't even sure about what consume means, so no.
More info on what I was trying to say: https://preshing.com/20170612/can-reordering-of-release-acquire-operations-introduce-deadlock/
And from Olivier, who is chair of the currency subgroup (SG1) in the committee. (I'm only a semi-regular of SG1). https://twitter.com/__simt__/status/1258504009804943360 "I now (recently) believe the standard permits this overlap, but implementers should not do this."
bionic-unix
I got it. The value written by exchange does not make a big deal.
matthieum
What are your thoughts on spinning a few times in the while loop before pausing?
Disclaimer: I've only ever used spinlocks on pinned threads w/o HT.
1BADragon
Nickreal03
So basically you are staying stay away from "std::atomic_flag".
Because there is is no way to relax load check its value.
Have you tested it?
rigtorp [OP]
Yes no relaxed load on GCC or clang: https://godbolt.org/z/ZN2b_n
NilacTheGrim
Unless you can prove the number of iterations is strictly bounded to some smallish finite value when the lock is contended -- a spinlock in userspace code is generally a bad idea.
If you find yourself spinning for 10,000 iterations or for an unbounded number of iterations worst-case -- use a mutex that sleeps the thread. It almost always is what you want.
Last time someone tried to post their implementation of a spin-lock along with benchmarks to show how much faster it was, it turned out to be a complete dud. That post was quite a bit more sophisticated than this one so I will remain skeptical that this is an improvement over it. As it turns out implementing a spin lock in user space on almost all common platforms is basically a waste of time.
Here is the original article implementing a spin lock
https://probablydance.com/2019/12/30/measuring-mutexes-spinlocks-and-how-bad-the-linux-scheduler-really-is/
Here is Linus Torvalds explaining why that article is basically worthless:
https://www.realworldtech.com/forum/?threadid=189711&curpostid=189723
The TL;DR is that many user space spin lock implementations will appear to give very fast results in naïve microbenchmarks like the one in this article, but are actually spectacularly poor in real world scenarios because the underlying OS scheduler itself is designed to handle scenarios that are very dissimilar to the scenarios that are used to benchmark spinlocks.
Ultimately the advice given by Linus, which I have come to agree with after experimenting with spin locks on my own project and falling for the same trap Linus points out is to simply not use spin locks in user space. They are simply not worth it and all platforms nowadays implement mutexes that do some form of spinning anyways before yielding to the scheduler, which will ultimately do a far better job than I or almost anyone will be able to do.
cdglove 52 points · Apr 2020
It fundantally comes down to this: you need to tell the scheduler what you want for it to effectively schedule. You do that through OS synchronisation primitives.
quicknir 33 points · Apr 2020
Your post seems to assume that the scheduler is actually involved. There's lots of use cases, on servers and not applications, where you simply fully lock one thread/process per core, keep all the background junk on some off core. At that point, once you have the core fully pinned to a thread anyway, you may as well use a spin lock (unless you care about power).
This is basically standard stuff in certain kind of low latency work, such as HFT.
gayasri 8 points · Apr 2020
This is pretty much our use case for spin locks. In low-latency paths, threads are pinned to isolated cores (with interrupts etc. bound to some other cores); so they almost never preempt.
I think if your all the threads that would wait on a lock owns their own individual cores, it's would be okay to use spin locks as long as you're okay with thermals/power since those cores have nothing else to do away. _mm_pause would also help esp. if HT is enabled.
[deleted] 0 points · Apr 2020
[deleted]
quicknir 3 points · Apr 2020
My phrasing isn't precise either, but pedantically, this is wrong as well. Pinning a thread to a core doesn't exclude the possibility that another thread is also running on that core, so it's not sufficient for our case. We need the threads and cores to be exactly 1 to 1.
[deleted] 0 points · Apr 2020
[deleted]
quicknir 3 points · Apr 2020
I mean, it's necessary but not sufficient, as you yourself just acknowledged.
[deleted] 0 points · Apr 2020
[deleted]
quicknir 3 points · Apr 2020
Lol. I very clearly explained the whole thing originally; dozens of people seem to have understood it without issue and agreed with it. You raised a pedantic point, which was pointless regardless, but also not fully pedantically correct, and now you're also throwing insults?
I'll leave this here for you to review: https://en.wikipedia.org/wiki/Necessity_and_sufficiency
rigtorp [OP] 25 points · Apr 2020
I don't discuss when to use a spinlock in the post. If you are writing a kernel in C++ and need a non-scalable spinlock, this is how you would do it. Spinlocks are for non-preemptible contexts, not generic application code. I might follow up later with scalable spinlock variants.
[deleted] 14 points · Apr 2020
Curious to know how you benchmarked your spinlock then since the impression I got is that you're using a laptop running some kind of POSIX-like OS to get the results. The point I'm making, and mostly just deferring to Linus' argument, is that such a benchmark is basically meaningless.
rigtorp [OP] 18 points · Apr 2020
Isolate the cores: https://rigtorp.se/low-latency-guide/
In the benchmark section I show that the number of cache misses and locked loads are lower for the correctly implemented spinlock (less coherency traffic).
[deleted] 3 points · Apr 2020
Yes, I think we're in agreement that your benchmark shows that your spinlock implementation is faster than the naïve implementation, but nothing on your low-latency-guide suggests that your spin-lock will outperform say
pthread_mutex_t. Without seeing the actual benchmark to determine if it avoids the mistakes that are commonly made when benchmarking these things it's basically impossible to tell.That said given your brief description of the benchmark, namely that it is a simple benchmark that only measures the amount of time used up by a lock()-unlock() pair, then it looks like the same mistakes are being made and you should absolutely read Linus' response to see why such a benchmark is not measuring what you think it is.
rigtorp [OP] 2 points · Apr 2020
The article just shows why you want to minimize cache coherency traffic. I ran the benchmark on linux because it's convenient. No where do I state that this is somehow better than using a mutex. In the real-time system where this is used a kernel scheduler is not available, so how can I use
pthread_mutex_t?[deleted] 8 points · Apr 2020
You make the correct argument that there are situations where no scheduler exists or even no kernel and so a spin lock is necessary. I agree with that but then your benchmark should be executed in such an environment. It makes no sense to benchmark a spin-lock in an environment so drastically different from the environment that it will actually be used in.
Your rationale about convenience is not particularly strong. You should not conduct a benchmark out of convenience if it comes at the cost of correctness.
rigtorp [OP] 0 points · Apr 2020
I still show that with a better design the amount of cache misses can be reduced (this implies less coherency traffic) and this data is tracked per process so independent on if a scheduler is running or not. I also show that the lock acquisition times are lowered and this will likely translate to other situations where you have one thread per core. Convenience is important otherwise it's too much work to write this up on a Saturday. It's not meant to be some irrefutable scientific proof.
[deleted] 9 points · Apr 2020
That's what I'm trying to point out though, there are serious flaws in this post worth refuting that are not apparent to someone who doesn't know any better.
It's not clear from the article that this spin lock should only be used in situations where no scheduler or kernel is available given that you're running it and using it in an environment with both.
It's also not clear that the benchmark you wrote was chosen for convenience rather than correctness and it's worth pointing out that writing a correct benchmark for a spin-lock in the presence of a scheduler is very difficult.
That context is important and worth pointing out given both the technical nature of the article as well as the fact that since the article criticizes other attempts at a spin-lock one should be careful not to leave themselves wide open to some fundamental criticisms as well.
It really is worth running this benchmark in an environment where a spin-lock is viable as opposed to user-space because otherwise these numbers really aren't that meaningful not to mention I highly suspect the way you measure the timings exhibits the same flaws that Linus points.
SlightlyLessHairyApe 5 points · Apr 2020
Even if you are writing a kernel, the scheduler absolutely needs to know when not to suspend a thread. That’s been true in Linux since 2.6 and BSD since 4.X
So maybe there is a non-preemtible context where this is useful, but it’s not kernel or user or driver ¯\_(ツ)_/¯
[deleted] -1 points · Apr 2020
[deleted]
SlightlyLessHairyApe 3 points · Apr 2020
Because I want the CPUs on my machine to run the highest priority work, consistent with other goals (see Linus' excellent explanation). A given thread (not sure why you say it's "my" thread, they are all my threads) may be high or lower priority than other live threads at any given time, even within the kernel.
It's instructive to look at the history of BSD before 4.X and Linux before 2.4 -- they initially started with kernel threads as non-preemptible, and then switched in order to resolve serious latency problems.
Link
Link
rigtorp [OP] 1 points · Apr 2020
Linux kernel is not fully pre-emptible. qspinlock is used in many places.
ArashPartow 3 points · Apr 2020
All you need to do is at the start of the article mention:
Solution presented below is for the scenario of a single thread pinned to a single isolated core
In core pairs every even core is disabled so there's no cache sharing at least at the l1/l2 levels - aka isolated core.
Core power management is disabled
Solution is not useful in general purpose, context switching, wakeable threading scenarios.
NilacTheGrim 1 points · Apr 2020
YES! Thank you! THIS!
_Js_Kc_ 3 points · Apr 2020
I mean, if anything, what the Probably Dance article shows is that std::mutex performance is robust.
You can beat it with a finely tuned spinlock on a particular system, but that will spin out of control at the drop of a hat.
[deleted] 8 points · Apr 2020
[deleted]
Tringi 6 points · Apr 2020 · github.com/tringi
The interesting thing is that CRITCIAL_SECTION was rewritten in almost every major release of Windows. In a current iteration of Windows 10, it was rewritten again to use WakeOnAddress and might be actually faster than SRWLocks. I remember seeing a recent blog post on this with interesting numbers. Will update this comment if I find it.
[deleted] 2 points · Apr 2020
[deleted]
Tringi 3 points · Apr 2020 · github.com/tringi
Yep, that hasn't changed. But it's not that huge, 24 or 40 bytes (with one similarly sized extra allocation when in debug), although of course pointer-sized primitives are much nicer.
NilacTheGrim 3 points · Apr 2020
Heh.
rigtorp [OP] 1 points · Apr 2020
That article is using spinlocks incorrectly. They are needed in non-preemtible contexts such as interrupt handlers. I've used it also between FGPA and CPU on the same PCIe bus.
kalmoc 2 points · Apr 2020
A (spin-)lock in an interrupt handler? Does that really make sense?
robstoon 1 points · May 2020
Necessary in some cases where the interrupt handler shares data with other code that might be running on another CPU. However that requires the other code that acquires the lock to disable interrupts first, so that it doesn't get interrupted by the interrupt handler which tries to acquire the same lock, causing a deadlock.
kalmoc 1 points · May 2020
My general concern is to put any potential blocking code into an interrupt handler.
robstoon 1 points · May 2020
It's a valid concern, but in some cases it's necessary, and doesn't generally cause a huge issue given that anything running inside a spinlock should have a short, bounded execution time in any case. In the hardest real time systems, one approach is to defer almost all interrupt processing to process context where it can be priority managed like any other process.
NilacTheGrim 3 points · Apr 2020
This is my experience as well. I never met a spin-lock in userspace that was justified.
marcodev 2 points · Apr 2020
So end of the story: don't use/implement a spin lock in user space unless you are enough crazy. What about the pthread_spn_lock then?
Tringi 1 points · Apr 2020 · github.com/tringi
I found myself writing a R/W spinlock a few months back and have been questioning that decision ever since.
The reason was that I needed locking around a short mov/xchg sequences, strongly preferring readers, per array item, in a memory shared between multiple processes, on Windows. Any such primitive simply doesn't exists, and using kernel objects seems too heavyweight as creating one per array item would result in millions of them.
At least if I could get someone with in-depth experience to tell me it's not terrible.
EDIT: https://github.com/tringi/rwspinlock
[deleted] 1 points · Apr 2020
I'm not sure if standard synchronisation primitives work with shared memory. Boost.Interprocess has its own mutexes, for example
Tringi 1 points · Apr 2020 · github.com/tringi
Yes. Even the fast ones, spinning ones, eventually back off to use OS mutex, which is private for the process. I could use named mutexes or explicitly share their handles (inherit or DuplicateHandle) but the costs of that are terrible if you have million objects. Thus custom spinlock (edited the above post to include link).
[deleted] 1 points · Apr 2020
Ok, but what I failed to get across is that I believe normal mutexes only work across memory shared by threads in the same process, not across memory shared by processes. If this is true, then I'd wager that your spinlock on shared memory may not actually be completely safe.
This doc suggests there is indeed a difference. https://pubs.opengroup.org/onlinepubs/007908775/xsh/pthread_mutexattr_setpshared.html
[deleted] 1 points · Apr 2020
[deleted]
[deleted] 1 points · Apr 2020
yes, shared between processes, not threads. There's a discussion further down.
UnDosTresPescao -1 points · Apr 2020
I was going to make a long reply trashing the article. Thanks for this, Linus covered it quite well.
[deleted] 4 points · Apr 2020
Why trash the article?
Just because it's not the best way to go about doing something such as spinlocks doesn't mean it's not productive and not contributional to thought.
[deleted] -3 points · Apr 2020
[deleted]
AdventurousMention0 3 points · Apr 2020
I’ve been a quant and have never needed a mutex, spinlock, critical section, etc. the only potential place would be startup.
If your using anything that can slow you down than your not doing it right. A spinlock May eat your entire trade time budget.
rigtorp [OP] 1 points · Apr 2020
Many such firms use onload which internally uses spinlocks or mutex depending on configuration, so it's not so black and white. In general avoid locks as you say.
rigtorp [OP] -1 points · Apr 2020
There are legitimate use case for spinlocks. For example linux kernel uses the qspinlock. I've used spinlocks in real-time systems where there is a single non-preemptible thread per core.
UnDosTresPescao 2 points · Apr 2020
Yes, baremetal real-time systems are one place where I have used them but very few of those support modern C++.
dkormalev -5 points · Apr 2020
I tend to disagree. I have a small library of my own with custom Future and task scheduler implementation and it (of course!) has its own spin lock implementation (actually with pausing similar to OP article, but on atomic_flag and with some cooldowns - https://github.com/dkormalev/asynqro/blob/develop/include/asynqro/impl/spinlock.h ). I have benchmarks that try to replicate stressful real life use of task scheduling (like create tasks from multiple threads, do something cpu-intensive in tasks, rinse, repeat). Having mutex instead of spinlock gives me about 40% overhead in particular cases (mostly in high concurrency tests) and is at least the same in others.
rigtorp [OP] 13 points · Apr 2020
That's not really a spinlock, you are sleeping for 500us on failed lock acquisition.
[deleted] 17 points · Apr 2020
But your implementation isn't a spin-lock. In the very source code you link to, on line 52 you yield to the OS scheduler. That is literally the very thing a spin lock is not supposed to do.
There is no dispute that one can implement a lock that can give a performance benefit over
std::mutexfor a given platform and for a given workload, the only argument that's being made is that you're not going to implement such a lock in user-space without getting the scheduler involved. The implementation you link to does involve the scheduler and hence it's not a spin lock and so it's not subject to the point I'm making despite the name you gave your implementation.dkormalev 3 points · Apr 2020
Ok, your edit is mostly about what I wrote (and meant). Yes, I fully agree with that words
kalmoc 1 points · Apr 2020
Actually Linus also explains rather vehemently, why locks using sched_yield are bad too.
load 1 more replies →