7 ms·

Restartable Sequences in Glibc 2.35

43 points by jrepinc 5y ago

amelius 5y ago
Can GDB handle these? How about Valgrind?
- jsnell 5y ago
  Valgring is discussed in the comments of the post, with a link to https://bugs.kde.org/show_bug.cgi?id=405377 https://bugs.kde.org/show_bug.cgi?id=405377
- CUViper 5y ago
  In the LWN comments, mjw said that Valgrind just forces an ENOSYS error.
- simark1 5y ago
  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.
addaon 5y ago
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 5y ago
  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 5y ago
    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
PaulDavisThe1st 5y ago
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 5y ago
  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 5y ago
    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.
    - uluyol 5y ago
      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.
wyldfire 5y ago
This sounds like an interesting feature - any OSs other than Linux implement anything similar?
- uluyol 5y ago
  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.

43 points by jrepinc 5y ago

amelius 5y ago

Can GDB handle these? How about Valgrind?

jsnell 5y ago
Valgring is discussed in the comments of the post, with a link to https://bugs.kde.org/show_bug.cgi?id=405377 https://bugs.kde.org/show_bug.cgi?id=405377
CUViper 5y ago
In the LWN comments, mjw said that Valgrind just forces an ENOSYS error.
simark1 5y ago
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.

addaon 5y ago

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 5y ago
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 5y ago
  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

PaulDavisThe1st 5y ago

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 5y ago
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 5y ago
  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.
  - uluyol 5y ago
    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.

wyldfire 5y ago

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

uluyol 5y ago
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.