Restartable Sequences in Glibc 2.35 • Hacker News Board

Re: Restartable Sequences in Glibc 2.35

#11

Post by uluyol » Sat, Feb 12, 2022, 6:21 PM UTC

PaulDavisThe1st wrote: post #10

teraflop wrote: post #9

Earlier quoted context omitted.

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 wit…

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.

Re: Restartable Sequences in Glibc 2.35

#12

Post by addaon » Sat, Feb 12, 2022, 6:29 PM UTC

PaulDavisThe1st wrote: post #7

addaon wrote: post #5

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 p…

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 s…

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

Re: Restartable Sequences in Glibc 2.35

#13

Post by PaulDavisThe1st » Sat, Feb 12, 2022, 6:40 PM UTC

uluyol wrote: post #11

PaulDavisThe1st wrote: post #10

Earlier quoted context omitted.

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 wit…

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.

Re: Restartable Sequences in Glibc 2.35

#14

Post by Veserv » Sat, Feb 12, 2022, 6:43 PM UTC

PaulDavisThe1st wrote: post #10

teraflop wrote: post #9

Earlier quoted context omitted.

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 wit…

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.

Re: Restartable Sequences in Glibc 2.35

#15

Post by CaliforniaKarl » Sat, Feb 12, 2022, 7:03 PM UTC

PaulDavisThe1st wrote: post #13

uluyol wrote: post #11

Earlier quoted context omitted.

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.

Re: Restartable Sequences in Glibc 2.35

#16

Post by uluyol » Sat, Feb 12, 2022, 7:27 PM UTC

PaulDavisThe1st wrote: post #13

uluyol wrote: post #11

Earlier quoted context omitted.

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.

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.

Re: Restartable Sequences in Glibc 2.35

#17

Post by uluyol » Sat, Feb 12, 2022, 7:33 PM UTC

wyldfire wrote: post #8

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.

Re: Restartable Sequences in Glibc 2.35

#18

Post by simark1 » Sun, Feb 13, 2022, 1:08 AM UTC

amelius wrote: post #2

Can GDB handle these? How about Valgrind?

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.