Restartable Sequences in Glibc 2.35 | Hacker News Reader

Restartable Sequences in Glibc 2.35

lwn.net

43 pointsjrepinc17 comments

So for a single critical section per thread, there's a small fixed overhead for every scheduling event in the system (the changes to the scheduler to check for whether the IP is in the critical section), and there's a restart cost if rescheduling actually happens during the critical section, but there's no additional code size or instructions on the critical path itself. But once managing multiple critical sections per thread this is no longer true...

Seems like interesting tradeoffs with an approach where the kernel manages a scheduling generation number in shared memory with each thread that gets incremented each scheduling, and having the user code responsible for checking at the end of the critical section whether it matches the value at the beginning. Probably an instruction or three less (and less pointer chasing) per scheduling event, but it eats a register during the critical section and grows the critical section by a few instructions, which also (for very tight critical sections) increases the chances they need a restart...

The LWN article mentions that compare-and-exchange is considered "slow", and the design you're mentioning here, you'd need that.

This is an alternative to cmpxchg-style solutions, which you can implement entirely in user space with no kernel collarboration. As I mentioned in another thread, the restartable sequence approach seems very limited in applicability, since it only offers you something in cases where it is specifically preemption, not multithreaded access to the data, that you need to protect against.

Edit: Oops, leaving this for posterity, but there's an error below. At the point marked OOPS cmpxchg or another atomic op is the (only?) way to avoid a race condition when there's a potential interrupt between the write-back instruction of the atomic operation and the comparison to the generation. My bad.

For this use case, I don't think the approach I mentioned requires an atomic cmpxchg.

Fast path (no pre-emption):

    - Read generation number shared memory location (GNSML) to register
    - Perform atomic operation
    - Compare (non-atomic) *GNSML to register [OOPS]
    - Equal, so continue

Slow path (pre-emption):

    - Read generation number shared memory location (GNSML) to register
    - Perform (part of) atomic operation
    -- Pre-emption occurs -- kernel updates GNSML, already has plenty of memory barriers with mode transitions
    - Perform (rest of) atomic operation
    - Compare (non-atomic) *GNSML to register -- because we're reading on the far side of the barrier, see new value
    - Different, so jump to restart

This seems really clever, but then I started thinking about the actual use cases. It does not offer protection against multiple threads modifying the same data. It is only useful where the "I was preempted in the middle" allows some deterministic recovery pathway to be taken. These are not unheard of, but they are rare compared to the cases where two (or more) threads may write the same non-atomic data (the ones where you'd really like cost-free RCU).

From the LWN article:

> The first rule is that the critical section cannot make any changes to the protected data structure that are visible to other threads until the final instruction in that section.

This makes me fairly certain that you cannot use this approach to deal with multi-core systems with data shared between threads, since the data could be modified without any preemption taking place.

As the article says at the beginning, this is intended for per-CPU data structures, not shared ones. For example, buffer pools where you don't care exactly which pool a given thread takes its buffers from, but you do care about maximizing performance and minimizing contention.

That also requires pinning the thread to the cpu, or it can find itself "on the wrong core" when it wants to release the buffer.

This narrows the use case even further. To be clear I write software that could nominally benefit from stuff like this, but the tradeoffs (requiring pinning, in particular, which may not be available on all platforms) mean that it seems better to use approaches (e.g. RCU) that will work without restartable sequences.

I think most allocators don't care which core you call free on. It's already the case that you can malloc from any core and free on another.

Special purpose allocators maybe. Agree that this mechanism overall is rather niche, but that niche (malloc) is a rather important one.

In the GP comment from @teraflop:

> As the article says at the beginning, this is intended for per-CPU data structures, not shared ones.

Indeed. And even though glibc has only recently introduced support for rseq, the rseq system call has been around for a while. Search around, I found tcmalloc (https://google.github.io/tcmalloc/) is an example of software that is using rseq today, without glibc's support. And as far as I can tell, tcmalloc is using rseq both with a 'per-CPU' structure (actually portions of a larger block of memory), and without a requirement to pin processes or threads to a particular CPU.

Their design document (https://google.github.io/tcmalloc/rseq.html) might be of interest to you.

The original use case (I believe) was tcmalloc. Tcmalloc maintained per-thread caches of free memory, but that's wasteful since it increases fragmentation but has no parallelism advantage compared to per-CPU buffers. OTOH, you can't just use per-CPU data since you can get preempted, hence rseq. malloc from the per-CPU cache without locking, and free to any other cache without locking.

You do not require pinning, rather that is the opposite of the use case.

An actual use case where restartable windows are useful is when writing a data entry to a per-core buffer where the entire acquire-write-release sequence can be fit into the restartable window. This guarantees that the entirety of the write will occur on a single core even if it is preempted or moved as the sequence will restart on the new core if you get moved. The advantages of this approach are that you are guaranteed the buffer will be in the cache of the core being executed on guaranteeing excellent cache locality. The disadvantages are that you may have to redo the writes if you get preempted, but that should be very unlikely if your write is not too long.

In terms of the general case, restartable windows can be thought of as having a disable_preemption() or disable_core_migration() similar to how you might have a way of disabling interrupts except with some more constraints on what you can do while things are disabled.

This sounds like an interesting feature - any OSs other than Linux implement anything similar?

This feature is pretty niche and really only helps on high thread count workloads (relative to the number of cores). Otherwise you can use per-thread data and it'll be the same, since the number of threads is approximately (or less than) the number of cores.

What workloads are high thread count? Mainly servers, I think (at least I don't know if any others offhand). So OSes aimed for embedded use or desktop use don't gain much from this sort of thing. Linux dominates the server market.

Can GDB handle these? How about Valgrind?

Valgring is discussed in the comments of the post, with a link to https://bugs.kde.org/show_bug.cgi?id=405377

In the LWN comments, mjw said that Valgrind just forces an ENOSYS error.

If GDB doesn't need to do single step the region, it should make no difference. Trying to single step the region would restart it indefinitely.

librseq generates a section describing the possible critical sections, so it would be possible to make GDB read it and skip critical sections when single stepping.

Reply on news.ycombinator.com