Happy new year 🎉!
\nIn this post, I will be expressing strong opinions about a topic I have relatively little practical experience with, so feel free to roast and educate me in comments (link at the end of the post) :-)
\nSpecifically, I’ll talk about:
\n#[no_std] ,I maintain once_cell crate, which is a synchronization primitive.\nIt uses std blocking facilities under the hood (specifically, std::thread::park), and as such is not compatible with #[no_std].\nA popular request is to add a spin-lock based implementation for use in #[no_std] environments: #61.
More generally, this seems to be a common pattern in Rust ecosystem:
\nMutex or other synchronization mechanism fromstd#[no_std] supportMutex is swapped for some variation of spinlock.For example, the lazy_static crate does this:
github.com/rust-lang-nursery/lazy-static.rs/blob/master/src/core_lazy.rs
\nI think this is an anti-pattern, and I am writing this blog post to call it out.
\nA Spinlock is the simplest possible implementation of a mutex, its general form looks like this:
compare_and_swap until it succeeds. The CPU “spins” in this very short loop.Why we need Ordering::Acquire and Ordering::Release is very interesting, but beyond the scope of this article.
The key take-away here is that a spinlock is implemented entirely in user space: from OS point of view, a “spinning” thread looks exactly like a thread that does a heavy computation.
\nAn OS-based mutex, like std::sync::Mutex or parking_lot::Mutex, uses a system call to tell the operating system that a thread needs to be blocked. In pseudo code, an implementation might look like this:
The main difference is park_this_thread — a blocking system call.\nIt instructs the OS to take current thread off the CPU until it is woken up by an unpark_some_thread call.\nThe kernel maintains a queue of threads waiting for a mutex.\nThe park call enqueues current thread onto this queue, while unpark dequeues some thread. The park system call returns when the thread is dequeued.\nIn the meantime, the thread waits off the CPU.
If there are several different mutexes, the kernel needs to maintain several queues.\nAn address of a lock can be used as a token to identify a specific queue (this is a futex API).
\nSystem calls are expensive, so production implementations of Mutex usually spin for several iterations before calling into OS, optimistically hoping that the Mutex will be released soon.\nHowever, the waiting always bottoms out in a syscall.
Because spin locks are so simple and fast, it seems to be a good idea to use them for short-lived critical sections. For example, if you only need to increment a couple of integers, should you really bother with complicated syscalls? In the worst case, the other thread will spin just for a couple of iterations…
\nUnfortunately, this logic is flawed! A thread can be preempted at any time, including during a short critical section. If it is preempted, that means that all other threads will need to spin until the original thread gets its share of CPU again. And, because a spinning thread looks like a good, busy thread to the OS, the other threads will spin until they exhaust their quants, preventing the unlucky thread from getting back on the processor!
\nIf this sounds like a series of unfortunate events, don’t worry, it gets even worse. Enter Priority Inversion. Suppose our threads have priorities, and OS tries to schedule high-priority threads over low-priority ones.
\nNow, what happens if the thread that enters a critical section is a low-priority one, but competing threads have high priority? It will likely get preempted: there are higher priority threads after all. And, if the number of cores is smaller than the number of high priority threads that try to lock a mutex, it likely won’t be able to complete a critical section at all: OS will be repeatedly scheduling all the other threads!
\nBut wait! — you would say — we only use spin locks in #[no_std] crates, so there’s no OS to preempt our threads.
First, it’s not really true: it’s perfectly fine, and often even desirable, to use #[no_std] crates for usual user-space applications.\nFor example, if you write a Rust replacement for a low-level C library, like zlib or openssl, you will probably make the crate #[no_std], so that non-Rust applications can link to it without pulling the whole of the Rust runtime.
Second, if there’s really no OS to speak about, and you are on the bare metal (or in the kernel), it gets even worse than priority inversion.
\nOn bare metal, we generally don’t worry about thread preemption, but we need to worry about processor interrupts. That is, while processor is executing some code, it might receive an interrupt from some periphery device, and temporary switch to the interrupt handler’s code.
\nAnd here comes the disaster: if the main code is in the middle of the critical section when the interrupt arrives, and if the interrupt handler tries to enter the critical section as well, we get a guaranteed deadlock!\nThere’s no OS to switch threads after a quant expires.\nHere are Linux kernel docs discussing this issue.
\nLet’s trigger priority inversion!\nOur victim is the getrandom crate.\nI don’t pick on getrandom specifically here: the pattern is pervasive across the ecosystem.
The crate uses spinning in the LazyUsize utility type:
There’s a static instance of LazyUsize which caches file descriptor for /dev/random:
https://github.com/rust-random/getrandom/blob/v0.1.13/src/use_file.rs#L26
\nThis descriptor is used when calling getrandom — the only function that is exported by the crate.
To trigger priority inversion, we will create 1 + N threads, each of which will call getrandom::getrandom.\nWe arrange it so that the first thread has a low priority, and the rest are high priority.\nWe stagger threads a little bit so that the first one does the initialization.\nWe also make creating the file descriptor slow, so that the first thread gets preempted while in the critical section.
Here is the implementation of this plan: https://github.com/matklad/spin-of-death.
\nIt uses a couple of systems programming hacks to make this disaster scenario easy to reproduce.\nTo simulate slow /dev/random, we want to intercept the poll syscall getrandom is using to ensure that there’s enough entropy.\nWe can use strace to log system calls issued by a program.\nI don’t know if strace can be used to make a syscall run slow (now, once I’ve looked at the website, I see that it can in fact be used to tamper with syscalls, sigh), but we actually don’t need to!\ngetrandom does not use the syscall directly, it uses the poll function from libc.\nWe can substitute this function by using LD_PRELOAD, but there’s an even simpler way!\nWe can trick the static linker into using a function which we define ourselves:
The name of the function accidentally ( :) ) clashes with a well-known POSIX function.
\nHowever, this alone is not enough.\ngetrandom tries to use getrandom syscall first, and that code path does not use a spin lock.\nWe need to fool getrandom into believing that the syscall is not available.\nOur extern "C" trick wouldn’t have worked if getrandom literally used the syscall instruction.\nHowever, as inline assembly (which you need to issue a syscall manually) is not available on stable Rust, getrandom goes via syscall function from libc.\nThat we can override with the same trick.
However, there’s a wrinkle!\nTraditionally, libc API used errno for error reporting.\nThat is, on a failure the function would return an single specific invalid value, and set the errno thread local variable to the specific error code. syscall follows this pattern.
The errno interface is cumbersome to use.\nThe worst part of errno is that the specification requires it to be a macro, and so you can only really use it from C source code.\nInternally, on Linux the macro calls __get_errno_location function to get the thread local, but this is an implementation detail (which we will gladly take advantage of, in this land of reckless systems hacking!). The irony is that the ABI of Linux syscall just returns error codes, so libc has to do some legwork to adapt to the awkward errno interface.
So, here’s a strong contender for the most cursed function I’ve written so far:
\nIt makes getrandom believe that there’s no getrandom syscall, which causes it to fallback to /dev/random implementation.
To set thread priorities, we use thread_priority crate, which is a thin wrapper around pthread APIs.\nWe will be using real time priorities, which require sudo.
And here are the results:
\nNote that I had to kill the program after two minutes. Also note the impressive system time, as well as load average
\nIf we patch getrandom to use std::sync::Once instead we get a much better result:
Note how real is half a second, butuser andsys are small.
That’s because we are waiting for 500 milliseconds in ourpoll
This is because Once uses OS facilities for blocking, and so OS notices that high priority threads are actually blocked and gives the low priority thread a chance to finish its work.
First, if you only use a spin lock because “it’s faster for small critical sections”, just replace it with a mutex from std or parking_lot.\nThey already do a small amount of spinning iterations before calling into the kernel, so they are as fast as a spinlock in the best case, and infinitely faster in the worst case.
Second, it seems like most problematic uses of spinlocks come from one time initialization (which is exactly what my once_cell crate helps with). I think it usually is possible to get away without using spinlocks. For example, instead of storing the state itself, the library may just delegate state storing to the user. For getrandom, it can expose two functions:
It then becomes the user’s problem to cache RandomState appropriately.\nFor example, std may continue using a thread local (src) while rand, with std feature enabled, could use a global variable, protected by Once.
Another option, if the state fits into usize and the initializing function is idempotent and relatively quick, is to do a racy initialization:
Take a second to appreciate the absence of unsafe blocks and cross-core communication in the above example!\nAt worst, (EDIT: this is wrong, thanks to /u/pcpthm for init will be called number of cores timespointing this out!).
There’s also a nuclear option: parametrize the library by blocking behavior, and allow the user to supply their own synchronization primitive.
\nThird, sometimes you just know that there’s only a single thread in the program, and you might want to use a spinlock just to silence those annoying compiler errors about static mut.\nThe primary use case here I think is WASM. A solution for this case is to assume that blocking just doesn’t happen, and panic otherwise. This is what std does for Mutex on WASM, and what is implemented for once_cell in this PR: #82.
Discussion on /r/rust.
\nEDIT: If you enjoyed this post, you might also like this one:
\nLooks like we have some contention here!
\nEDIT: there’s now a follow up post, where we actually benchmark spinlocks:
\nhttps://matklad.github.io/2020/01/04/mutexes-are-faster-than-spinlocks.html
","headings":[{"level":1,"text":"Spinlocks Considered Harmful","id":"spinlocks-considered-harmful"},{"level":2,"text":"Context","id":"context"},{"level":2,"text":"What Is a Spinlock, Anyway?","id":"what-is-a-spinlock-anyway"},{"level":2,"text":"Spinning Just For a Little Bit, What Can Go Wrong?","id":"spinning-just-for-a-little-bit-what-can-go-wrong"},{"level":2,"text":"No OS, no problem?","id":"no-os-no-problem"},{"level":2,"text":"Practical Applications","id":"practical-applications"},{"level":2,"text":"If Not a Spinlock, Then What?","id":"if-not-a-spinlock-then-what"}]}}