19 ms·

Linux: Introduce restartable sequences system call

197 points by tgragnato 8y ago

wahern 8y ago
That took nearly 3 years to get merged: https://lwn.net/Articles/650333/ https://lwn.net/Articles/650333/
- schmichael 8y ago
  5 years since first presented: https://www.youtube.com/watch?v=KXuZi9aeGTw https://www.youtube.com/watch?v=KXuZi9aeGTw
  - wahern 8y ago
    Are the userland scheduling patches (switchto) in the pipeline?
    - schmichael 8y ago
      If they are I can't find where...
  - ailideex 8y ago
    I'm not entirely sure this is same thing - but if anybody know where the patches for this is please share - I have tried to contact the presenter to get them but had no success thus far.
  - cryptonector 8y ago
    That doesn't talk about this, but about a larger set of enhancements (new system calls) for avoiding a bunch of threading/scheduler pathologies.
- taftster 8y ago
  Could you clarify if you think this is good, bad, or just interesting? Your comment might be received as though a change like this taking three years is somehow not efficient or tsk-worthy.
  - schmichael 8y ago
    I'm not the OP, but I posted the video I remember watching 5 years ago with great interest. I have no basis on which to inform an opinion on whether 5 years is a good or bad period of time to go from an idea to a syscall in the Linux kernel. I just find it interesting as someone who has switched jobs multiple times in 5 years -- much less worked on a single idea that long!
    - ebikelaw 8y ago
      Well, to be fair to the authors, their idea became a system in the linux kernel within Google years ago. It's only the general public that has been deprived of its benefit.
      - compudj 8y ago
        (disclaimer: I am the patch author, Mathieu Desnoyers) Just as a clarification, the idea originates from Google (I give full credits to Paul Turner and Andrew Hunter for it). However, the extra 3 years of work required to get it upstream has been done by myself at EfficiOS.
        pas 8y ago
        Thank you for persevering! Could you elaborate a bit on what had to be done to get it upstream?
        compudj 8y ago
        Sure, before getting it upstream, I had to: - Gather a list of desiderata, ensuring we take into account a complete list of use-cases targeted by everyone active in the rseq discussions. This is crucially important to ensure discussions don't spin in circles going back and forth between different requirements, - Redesign the uapi/linux/rseq.h ABI, making sure a single TLS store is needed to enter a rseq critical section, without requiring any extra registers as ABI. I have introduced the "rseq_cs" structure as critical section descriptor to do this, - Optimize arm32 and x86 rseq critical sections for speed, by creating my own benchmark programs, - Rewrite the kernel rseq implementation a few times so it follows the kernel coding style and ensure it pleases everyone caring about it, - Present 2 talks about rseq at Linux Plumbers Conference, - Go through various rounds of in person, email, and IRC discussions with Paul Turner, Peter Zijlstra, Andy Lutomirski, Boqun Feng, Paul E. McKenney, Thomas Gleixner, Ben Maurer, Linus Torvalds, and many others. Those were very constructive discussions bringing up everyone's concerns with respect to this new system call, - Extend the rseq selftests, adding new testing strategies such as delay loops between "steps" of the critical section, thus increasing the likelihood of generating preemption races, - Figure out nasty races only happening on NUMA systems after about a full day of stress-testing, - Provide solutions for debugger single-stepping "lack of progress" problem if rseq is used when retrying on abort. It's basically the cpu_opv system call I plan to propose for 4.19. Meanwhile, without cpu_opv, rseq can still be used in ways to guarantee forward progress, but the abort code needs to use a partitioning strategy rather than a simple retry (e.g. going to a different memory pool in case of abort for a memory allocator), - Harden the rseq mechanism for security, by adding a "signature" word before the abort label, - Implement prototypes of lttng-ust and liburcu which use rseq, gathering benchmarks to validate the approach, - Write rseq and cpu_opv man pages. And this is just the items that were "forward progress" in the rseq adventure. I'm leaving out everything that were attempts at making things more generic that had to be thrown away.
mereel 8y ago
What is an example of the "per-cpu data" they're talking about here[0]? [0] https://github.com/torvalds/linux/blob/d82991a8688ad128b46db1b42d5d84396487a508/kernel/rseq.c#L31-L32 https://github.com/torvalds/linux/blob/d82991a8688ad128b46db...
- yarosv 8y ago
  AFAIK it means that it guarantees the block of code will not be interrupted by scheduler and executed on another CPU/Core
  - jcriddle4 8y ago
    Sort of. It looks like if some critical code is interrupted, by a CPU move, then the process would get some code restarted. The idea being since, in some cases, CPU moves can be rare you aren't paying for the expense of locks to guard against this and just let the OS tell the process, hey I moved you will you were doing something critical, let me restart that for you. This isn't a full solution for all process locks but for a number of locking scenarios restarting the code is all that is needed.
    - Dykam 8y ago
      Kind of like optimistic concurrency? "Lets try, we'll retry on failure".
      - zaarn 8y ago
        It doesn't look like it's a full retry, atleast not for critical sections. From what I can tell you do three things; A) you can define a critical section which must run atomically in respect to the CPU core moves B) if the critical section is interrupted you can define a callback or restart the section (meaning the section can be safely repeated) C) you can define a single operation to commit (ie, updating a pointer) You can certainly build a "retry on failure" method using this, CPU moves are rare so it's unlikely to fail the second time.
- 8y ago
stefan_ 8y ago
So that's what the warning I get on 4.18 with arm64 is about.. CALL scripts/checksyscalls.sh <stdin>:1335:2: warning: #warning syscall rseq not implemented [-Wcpp] I guess it's not really in, then.
- pm215 8y ago
  The nature of the thing is that there's a chunk of per-architecture work required (maybe 20-30 lines of actual kernel code and another 700 lines of userspace/testcase support, judging by the diffstat). What's gone in to start with includes support for x86-64, i386, powerpc and 32-bit arm as well as the common code. Maintainers of other architectures can then add support on top of this at some point. Support for new syscalls not being perfectly in sync across all kernel archs is not uncommon, I think. The other not-yet-there part is how userspace libcs are going to expose this usefully to applications; there's some interesting discussion on the kernel mailing list about that. (It needs some libc support because the kernel only supports a single registered restartable-sequence area, so if multiple libraries try to do it they'll tread on each others' feet; and libc will want to use this feature itself.)
  - webaholic 8y ago
    Are you aware of any effort to add ARM64 support?
    - compudj 8y ago
      Yes, Will Deacon (Linux ARM64 maintainer) is working on it right now.
dooglius 8y ago
>The address of jump target abort_ip must be outside the critical region Seems like an odd requirement, isn't the whole point that we want to restart the critical section, or at least part of it, over in the case that it's interrupted?
- foota 8y ago
  Yes, but you can't restart from inside the critical section, you have to like reinitialize it.
- jgalar 8y ago
  Not necessarily. Applications may choose to retry a certain number of times and fallback to another mechanism if the critical section can't complete. A problematic case that was brought up on LKML was the interaction with debuggers and unexpected page faults, see this comment: https://lwn.net/Articles/738119/ https://lwn.net/Articles/738119/
- codedokode 8y ago
  Usually you need to do some cleanup first. Abort_ip being outside critical section prevents kernel from restarting this cleanup code.
Grollicus 8y ago
The Speedup numbers named in the commit [0] are impressive on arm but don't look very well on x86. On the other hand they add a thread-local write to every context switch and add a bunch of code. Add to that only 1.2 speedup on the LTTng benchmark. To me as a non-kernel guy this doesn't sound very impressive.. [0] https://github.com/torvalds/linux/commit/d7822b1e24f2df5df98c76f0e94a5416349ff759 https://github.com/torvalds/linux/commit/d7822b1e24f2df5df98...
- hshehehjdjdjd 8y ago
  A 1.2x speedup affecting a primitive operation is huge.
- opmac 8y ago
  Ah yes, the ubiquitous middlebrow dismissal (https://news.ycombinator.com/item?id=4693920 https://news.ycombinator.com/item?id=4693920 http://www.byrnehobart.com/blog/why-are-middlebrow-dismissals-so-tempting/ http://www.byrnehobart.com/blog/why-are-middlebrow-dismissal...). "As a non-kernal guy" gives it away immediately.
  - cryptonector 8y ago
    The other responses were useful. Yours is just a put-down. Why bother? To discourage "middlebrow" comments? But the one you're responding to elicited useful information, so it's hardly a problem.
    - striking 8y ago
      I found the articles on the "middlebrow dismissal" insightful. And I don't think ends usually justify means; I think the parent-most comment was not as nice as it should have been. The parent comment is not so much a put-down as much as it calls out a particularly unsophisticated dismissal. The parent-most comment would have elicited the same useful information if it were phrased as a question, but would have been less uncouth. I think that's a perfectly fine thing to write a comment about.
- 8y ago
deleted 8y ago
[deleted]
rwmj 8y ago
Will this finally allow us to implement the mkdir system call in terms of mknod and link :-?
- int0x80 8y ago
  Why do you want that?
- nikital 8y ago
  No, you can't call syscalls from restartable sequences
voltagex_ 8y ago
This is too far above my level to understand directly - has anyone got an example of an application that will be affected by this? I see some comments about tracing below.
- compudj 8y ago
  Some use-cases likely to be enhanced by rseq: statistics counters, memory allocators (jemalloc, glibc malloc, and others), user-space tracing (LTTng), user-space Read-Copy Update (liburcu), reading performance monitoring unit counters from user-space on ARM64, and possibly user-space task scheduling. Also, just reading the current CPU number can now be done faster by reading the __rseq_abi->cpu_id field rather than calling the sched_getcpu vDSO.
  - FrankBooth 8y ago
    Thanks for seeing this work through, Mathieu. > possibly user-space task scheduling I'm very interested in this aspect. Do you have a sense of whether there's enough in the kernel now to build this, or are there still pieces missing?
    - compudj 8y ago
      Yes, there are indeed pieces missing for this use-case. I intend to push another system call for the next merge window (4.19): "cpu_opv" [1]. It stands for "CPU operation vector", which is needed to take care of moving user-level tasks around between per-cpu work-queues touched by rseq fast-paths in a way that is safe against CPU hotplug. It's also needed to migrate free memory between per-cpu memory pools modified by rseq fast-paths safely against CPU hotplug. Some of it can be approximated by setting cpu affinity, but it's racy against CPU hotplug. cpu_opv can be used as a slow-path fallback in pretty much all scenarios where the rseq fast-path aborts. rseq user-level APIs are pretty much limited to only work on the current CPU, whereas cpu_opv allows creating operations on per-cpu data structures [2] which take the CPU number as argument. If it happens to be on the current CPU, rseq can be used and it is fast, but if the CPU number is not the current CPU, or is an offline CPU, then cpu_opv takes care of performing the operation safely with respect to rseq critical sections, and other cpu_opv operations. [1] https://git.kernel.org/pub/scm/linux/kernel/git/rseq/linux-rseq.git/commit/?h=v4.18-rc1-rseq-20180619.2&id=293b0fb03e6dc9c70d2c5e6ce4065456aa8c4d5e https://git.kernel.org/pub/scm/linux/kernel/git/rseq/linux-r... [2] https://git.kernel.org/pub/scm/linux/kernel/git/rseq/linux-rseq.git/commit/?h=v4.18-rc1-rseq-20180619.2&id=d380b8e2f5f08c09ad893dc46cf530b45910914d https://git.kernel.org/pub/scm/linux/kernel/git/rseq/linux-r...
glandium 8y ago
Does something similar exist on other OSes?
- davidtgoldblatt 8y ago
  It's implementable with a kernel driver on Solaris because of its scheduling hooks. (This was done in the "Mostly Lock-Free Malloc" paper).
signa11 8y ago
genuine question: why not boot the machine with 'isolcpu' and place your tasks on said cpu's ? such tasks would be not subjected to vagaries of scheduler etc...
- compudj 8y ago
  It all depends on how much control you have on the system you target. The strategy you refer to may well work for a dedicated deployment, but if you are developing a general-purpose memory allocator targeting a wide range of applications, you might not want to impose those constraints on your users.
  - signa11 8y ago
    ah, thanks for the information ! having used 'isolcpu' on dedicated-systems, i completely overlooked this aspect.
- bonzini 8y ago
  You could still have N threads but only want M (M<N) CPUs. For example there are situations where the single threads are mostly I/O bound, but reducing the little CPU work they do allows you to pack more threads (and e.g. serve more clients) on the same number of CPUs. Without restartable sequences, replacing per-thread data with per-CPU data had a trade-off: per-thread data can be accessed with less overhead, per-CPU data consumes less memory. Restartable sequences give you the best of both worlds.
muxator 8y ago
Is it only me? A github link instead of a kernel.org one? Maybe it's just an effort to reduce the HN death hug, and every git repo is an identical clone after all, yet I can't help but think that a link to the kernel tree should point to [0]. Github is (and never was) the only source of truth. It (sort of) became because of us. Replace this with Operaring System, Social Network, default Win 95 browser, any commonly accepted belief. [0] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/diff/kernel/rseq.c?id=d82991a8688ad128b46db1b42d5d84396487a508 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
- nemanjaboric 8y ago
  I guess this would be in line with the Linus' description of GitHub: > I think github does a stellar job at the actual hosting part. I really do. There is no question in my mind that github is one of the absolute best places to host a project. It's fast, it's efficient, it works, and it's available to anybody. https://github.com/torvalds/linux/pull/17#issuecomment-5654674 https://github.com/torvalds/linux/pull/17#issuecomment-56546...
  - Fnoord 8y ago
    Correct source of comment is elsewhere in that thread [1] [1] https://github.com/torvalds/linux/pull/17#issuecomment-5661304 https://github.com/torvalds/linux/pull/17#issuecomment-56613...
hawski 8y ago
Here are the man page for it: Search for "Man page associated": https://patchwork.kernel.org/patch/10444833/ https://patchwork.kernel.org/patch/10444833/ Also man page source: https://patchwork.kernel.org/patch/10468085/ https://patchwork.kernel.org/patch/10468085/
nikital 8y ago
A restartable sequence is defined by a start and an end offset. If I write a restarable sequence in C I can't be absolutely sure that it's contiguous and I can't know where the commit instruction is... Does it mean that I have to write it in assembly to make sure that I know where the sequence starts and where it ends?
- viraptor 8y ago
  I think C lost it at: abort must be possible to call from any place in the critical block. Since you can't be sure the registers didn't spill on the stack, I don't think anything more than ASM would work.
- compudj 8y ago
  Indeed the restartable sequence critical section needs to be written in assembly. The idea is to keep this complexity within public headers implementing the common operations as inline assembly for all supported architectures. You can see such operations already implemented for x86 as part of the rseq selftests here: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/tools/testing/selftests/rseq/rseq-x86.h?h=v4.18-rc1 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...

197 points by tgragnato 8y ago

wahern 8y ago

That took nearly 3 years to get merged: https://lwn.net/Articles/650333/ https://lwn.net/Articles/650333/

schmichael 8y ago
5 years since first presented: https://www.youtube.com/watch?v=KXuZi9aeGTw https://www.youtube.com/watch?v=KXuZi9aeGTw
- wahern 8y ago
  Are the userland scheduling patches (switchto) in the pipeline?
  - schmichael 8y ago
    If they are I can't find where...
- ailideex 8y ago
  I'm not entirely sure this is same thing - but if anybody know where the patches for this is please share - I have tried to contact the presenter to get them but had no success thus far.
- cryptonector 8y ago
  That doesn't talk about this, but about a larger set of enhancements (new system calls) for avoiding a bunch of threading/scheduler pathologies.
taftster 8y ago
Could you clarify if you think this is good, bad, or just interesting? Your comment might be received as though a change like this taking three years is somehow not efficient or tsk-worthy.
- schmichael 8y ago
  I'm not the OP, but I posted the video I remember watching 5 years ago with great interest. I have no basis on which to inform an opinion on whether 5 years is a good or bad period of time to go from an idea to a syscall in the Linux kernel. I just find it interesting as someone who has switched jobs multiple times in 5 years -- much less worked on a single idea that long!
  - ebikelaw 8y ago
    Well, to be fair to the authors, their idea became a system in the linux kernel within Google years ago. It's only the general public that has been deprived of its benefit.
    - compudj 8y ago
      (disclaimer: I am the patch author, Mathieu Desnoyers) Just as a clarification, the idea originates from Google (I give full credits to Paul Turner and Andrew Hunter for it). However, the extra 3 years of work required to get it upstream has been done by myself at EfficiOS.
      - pas 8y ago
        Thank you for persevering! Could you elaborate a bit on what had to be done to get it upstream?
        compudj 8y ago
        Sure, before getting it upstream, I had to: - Gather a list of desiderata, ensuring we take into account a complete list of use-cases targeted by everyone active in the rseq discussions. This is crucially important to ensure discussions don't spin in circles going back and forth between different requirements, - Redesign the uapi/linux/rseq.h ABI, making sure a single TLS store is needed to enter a rseq critical section, without requiring any extra registers as ABI. I have introduced the "rseq_cs" structure as critical section descriptor to do this, - Optimize arm32 and x86 rseq critical sections for speed, by creating my own benchmark programs, - Rewrite the kernel rseq implementation a few times so it follows the kernel coding style and ensure it pleases everyone caring about it, - Present 2 talks about rseq at Linux Plumbers Conference, - Go through various rounds of in person, email, and IRC discussions with Paul Turner, Peter Zijlstra, Andy Lutomirski, Boqun Feng, Paul E. McKenney, Thomas Gleixner, Ben Maurer, Linus Torvalds, and many others. Those were very constructive discussions bringing up everyone's concerns with respect to this new system call, - Extend the rseq selftests, adding new testing strategies such as delay loops between "steps" of the critical section, thus increasing the likelihood of generating preemption races, - Figure out nasty races only happening on NUMA systems after about a full day of stress-testing, - Provide solutions for debugger single-stepping "lack of progress" problem if rseq is used when retrying on abort. It's basically the cpu_opv system call I plan to propose for 4.19. Meanwhile, without cpu_opv, rseq can still be used in ways to guarantee forward progress, but the abort code needs to use a partitioning strategy rather than a simple retry (e.g. going to a different memory pool in case of abort for a memory allocator), - Harden the rseq mechanism for security, by adding a "signature" word before the abort label, - Implement prototypes of lttng-ust and liburcu which use rseq, gathering benchmarks to validate the approach, - Write rseq and cpu_opv man pages. And this is just the items that were "forward progress" in the rseq adventure. I'm leaving out everything that were attempts at making things more generic that had to be thrown away.

mereel 8y ago

What is an example of the "per-cpu data" they're talking about here[0]? [0] https://github.com/torvalds/linux/blob/d82991a8688ad128b46db1b42d5d84396487a508/kernel/rseq.c#L31-L32 https://github.com/torvalds/linux/blob/d82991a8688ad128b46db...

yarosv 8y ago
AFAIK it means that it guarantees the block of code will not be interrupted by scheduler and executed on another CPU/Core
- jcriddle4 8y ago
  Sort of. It looks like if some critical code is interrupted, by a CPU move, then the process would get some code restarted. The idea being since, in some cases, CPU moves can be rare you aren't paying for the expense of locks to guard against this and just let the OS tell the process, hey I moved you will you were doing something critical, let me restart that for you. This isn't a full solution for all process locks but for a number of locking scenarios restarting the code is all that is needed.
  - Dykam 8y ago
    Kind of like optimistic concurrency? "Lets try, we'll retry on failure".
    - zaarn 8y ago
      It doesn't look like it's a full retry, atleast not for critical sections. From what I can tell you do three things; A) you can define a critical section which must run atomically in respect to the CPU core moves B) if the critical section is interrupted you can define a callback or restart the section (meaning the section can be safely repeated) C) you can define a single operation to commit (ie, updating a pointer) You can certainly build a "retry on failure" method using this, CPU moves are rare so it's unlikely to fail the second time.
8y ago

stefan_ 8y ago

So that's what the warning I get on 4.18 with arm64 is about.. CALL scripts/checksyscalls.sh <stdin>:1335:2: warning: #warning syscall rseq not implemented [-Wcpp] I guess it's not really in, then.

pm215 8y ago
The nature of the thing is that there's a chunk of per-architecture work required (maybe 20-30 lines of actual kernel code and another 700 lines of userspace/testcase support, judging by the diffstat). What's gone in to start with includes support for x86-64, i386, powerpc and 32-bit arm as well as the common code. Maintainers of other architectures can then add support on top of this at some point. Support for new syscalls not being perfectly in sync across all kernel archs is not uncommon, I think. The other not-yet-there part is how userspace libcs are going to expose this usefully to applications; there's some interesting discussion on the kernel mailing list about that. (It needs some libc support because the kernel only supports a single registered restartable-sequence area, so if multiple libraries try to do it they'll tread on each others' feet; and libc will want to use this feature itself.)
- webaholic 8y ago
  Are you aware of any effort to add ARM64 support?
  - compudj 8y ago
    Yes, Will Deacon (Linux ARM64 maintainer) is working on it right now.

dooglius 8y ago

>The address of jump target abort_ip must be outside the critical region Seems like an odd requirement, isn't the whole point that we want to restart the critical section, or at least part of it, over in the case that it's interrupted?

foota 8y ago
Yes, but you can't restart from inside the critical section, you have to like reinitialize it.
jgalar 8y ago
Not necessarily. Applications may choose to retry a certain number of times and fallback to another mechanism if the critical section can't complete. A problematic case that was brought up on LKML was the interaction with debuggers and unexpected page faults, see this comment: https://lwn.net/Articles/738119/ https://lwn.net/Articles/738119/
codedokode 8y ago
Usually you need to do some cleanup first. Abort_ip being outside critical section prevents kernel from restarting this cleanup code.

Grollicus 8y ago

The Speedup numbers named in the commit [0] are impressive on arm but don't look very well on x86. On the other hand they add a thread-local write to every context switch and add a bunch of code. Add to that only 1.2 speedup on the LTTng benchmark. To me as a non-kernel guy this doesn't sound very impressive.. [0] https://github.com/torvalds/linux/commit/d7822b1e24f2df5df98c76f0e94a5416349ff759 https://github.com/torvalds/linux/commit/d7822b1e24f2df5df98...

hshehehjdjdjd 8y ago
A 1.2x speedup affecting a primitive operation is huge.
opmac 8y ago
Ah yes, the ubiquitous middlebrow dismissal (https://news.ycombinator.com/item?id=4693920 https://news.ycombinator.com/item?id=4693920 http://www.byrnehobart.com/blog/why-are-middlebrow-dismissals-so-tempting/ http://www.byrnehobart.com/blog/why-are-middlebrow-dismissal...). "As a non-kernal guy" gives it away immediately.
- cryptonector 8y ago
  The other responses were useful. Yours is just a put-down. Why bother? To discourage "middlebrow" comments? But the one you're responding to elicited useful information, so it's hardly a problem.
  - striking 8y ago
    I found the articles on the "middlebrow dismissal" insightful. And I don't think ends usually justify means; I think the parent-most comment was not as nice as it should have been. The parent comment is not so much a put-down as much as it calls out a particularly unsophisticated dismissal. The parent-most comment would have elicited the same useful information if it were phrased as a question, but would have been less uncouth. I think that's a perfectly fine thing to write a comment about.
8y ago

deleted 8y ago

[deleted]

rwmj 8y ago

Will this finally allow us to implement the mkdir system call in terms of mknod and link :-?

int0x80 8y ago
Why do you want that?
nikital 8y ago
No, you can't call syscalls from restartable sequences

voltagex_ 8y ago

This is too far above my level to understand directly - has anyone got an example of an application that will be affected by this? I see some comments about tracing below.

compudj 8y ago
Some use-cases likely to be enhanced by rseq: statistics counters, memory allocators (jemalloc, glibc malloc, and others), user-space tracing (LTTng), user-space Read-Copy Update (liburcu), reading performance monitoring unit counters from user-space on ARM64, and possibly user-space task scheduling. Also, just reading the current CPU number can now be done faster by reading the __rseq_abi->cpu_id field rather than calling the sched_getcpu vDSO.
- FrankBooth 8y ago
  Thanks for seeing this work through, Mathieu. > possibly user-space task scheduling I'm very interested in this aspect. Do you have a sense of whether there's enough in the kernel now to build this, or are there still pieces missing?
  - compudj 8y ago
    Yes, there are indeed pieces missing for this use-case. I intend to push another system call for the next merge window (4.19): "cpu_opv" [1]. It stands for "CPU operation vector", which is needed to take care of moving user-level tasks around between per-cpu work-queues touched by rseq fast-paths in a way that is safe against CPU hotplug. It's also needed to migrate free memory between per-cpu memory pools modified by rseq fast-paths safely against CPU hotplug. Some of it can be approximated by setting cpu affinity, but it's racy against CPU hotplug. cpu_opv can be used as a slow-path fallback in pretty much all scenarios where the rseq fast-path aborts. rseq user-level APIs are pretty much limited to only work on the current CPU, whereas cpu_opv allows creating operations on per-cpu data structures [2] which take the CPU number as argument. If it happens to be on the current CPU, rseq can be used and it is fast, but if the CPU number is not the current CPU, or is an offline CPU, then cpu_opv takes care of performing the operation safely with respect to rseq critical sections, and other cpu_opv operations. [1] https://git.kernel.org/pub/scm/linux/kernel/git/rseq/linux-rseq.git/commit/?h=v4.18-rc1-rseq-20180619.2&id=293b0fb03e6dc9c70d2c5e6ce4065456aa8c4d5e https://git.kernel.org/pub/scm/linux/kernel/git/rseq/linux-r... [2] https://git.kernel.org/pub/scm/linux/kernel/git/rseq/linux-rseq.git/commit/?h=v4.18-rc1-rseq-20180619.2&id=d380b8e2f5f08c09ad893dc46cf530b45910914d https://git.kernel.org/pub/scm/linux/kernel/git/rseq/linux-r...

glandium 8y ago

Does something similar exist on other OSes?

davidtgoldblatt 8y ago
It's implementable with a kernel driver on Solaris because of its scheduling hooks. (This was done in the "Mostly Lock-Free Malloc" paper).

signa11 8y ago

genuine question: why not boot the machine with 'isolcpu' and place your tasks on said cpu's ? such tasks would be not subjected to vagaries of scheduler etc...

compudj 8y ago
It all depends on how much control you have on the system you target. The strategy you refer to may well work for a dedicated deployment, but if you are developing a general-purpose memory allocator targeting a wide range of applications, you might not want to impose those constraints on your users.
- signa11 8y ago
  ah, thanks for the information ! having used 'isolcpu' on dedicated-systems, i completely overlooked this aspect.
bonzini 8y ago
You could still have N threads but only want M (M<N) CPUs. For example there are situations where the single threads are mostly I/O bound, but reducing the little CPU work they do allows you to pack more threads (and e.g. serve more clients) on the same number of CPUs. Without restartable sequences, replacing per-thread data with per-CPU data had a trade-off: per-thread data can be accessed with less overhead, per-CPU data consumes less memory. Restartable sequences give you the best of both worlds.

muxator 8y ago

Is it only me? A github link instead of a kernel.org one? Maybe it's just an effort to reduce the HN death hug, and every git repo is an identical clone after all, yet I can't help but think that a link to the kernel tree should point to [0]. Github is (and never was) the only source of truth. It (sort of) became because of us. Replace this with Operaring System, Social Network, default Win 95 browser, any commonly accepted belief. [0] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/diff/kernel/rseq.c?id=d82991a8688ad128b46db1b42d5d84396487a508 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...

nemanjaboric 8y ago
I guess this would be in line with the Linus' description of GitHub: > I think github does a stellar job at the actual hosting part. I really do. There is no question in my mind that github is one of the absolute best places to host a project. It's fast, it's efficient, it works, and it's available to anybody. https://github.com/torvalds/linux/pull/17#issuecomment-5654674 https://github.com/torvalds/linux/pull/17#issuecomment-56546...
- Fnoord 8y ago
  Correct source of comment is elsewhere in that thread [1] [1] https://github.com/torvalds/linux/pull/17#issuecomment-5661304 https://github.com/torvalds/linux/pull/17#issuecomment-56613...

hawski 8y ago

Here are the man page for it: Search for "Man page associated": https://patchwork.kernel.org/patch/10444833/ https://patchwork.kernel.org/patch/10444833/ Also man page source: https://patchwork.kernel.org/patch/10468085/ https://patchwork.kernel.org/patch/10468085/

nikital 8y ago

A restartable sequence is defined by a start and an end offset. If I write a restarable sequence in C I can't be absolutely sure that it's contiguous and I can't know where the commit instruction is... Does it mean that I have to write it in assembly to make sure that I know where the sequence starts and where it ends?

viraptor 8y ago
I think C lost it at: abort must be possible to call from any place in the critical block. Since you can't be sure the registers didn't spill on the stack, I don't think anything more than ASM would work.
compudj 8y ago
Indeed the restartable sequence critical section needs to be written in assembly. The idea is to keep this complexity within public headers implementing the common operations as inline assembly for all supported architectures. You can see such operations already implemented for x86 as part of the rseq selftests here: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/tools/testing/selftests/rseq/rseq-x86.h?h=v4.18-rc1 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...