[HN Gopher] Restartable Sequences in Glibc 2.35
___________________________________________________________________
Restartable Sequences in Glibc 2.35
Author : jrepinc
Score : 37 points
Date : 2022-02-10 12:06 UTC (2 days ago)
(HTM) web link (lwn.net)
(TXT) w3m dump (lwn.net)
| amelius wrote:
| Can GDB handle these? How about Valgrind?
| jsnell wrote:
| Valgring is discussed in the comments of the post, with a link
| to https://bugs.kde.org/show_bug.cgi?id=405377
| CUViper wrote:
| In the LWN comments, mjw said that Valgrind just forces an
| ENOSYS error.
| PaulDavisThe1st wrote:
| 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.
| teraflop wrote:
| 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.
| PaulDavisThe1st wrote:
| 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.
| Veserv wrote:
| 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.
| uluyol wrote:
| 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.
| PaulDavisThe1st wrote:
| In the GP comment from @teraflop:
|
| > As the article says at the beginning, this is intended
| for per-CPU data structures, not shared ones.
| CaliforniaKarl wrote:
| 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.
| uluyol wrote:
| 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.
| wyldfire wrote:
| This sounds like an interesting feature - any OSs other than
| Linux implement anything similar?
| uluyol wrote:
| 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.
| addaon wrote:
| 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...
| PaulDavisThe1st wrote:
| 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.
| addaon wrote:
| 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
___________________________________________________________________
(page generated 2022-02-12 23:01 UTC)