9 ms·

Use of eBPF in CPU Scheduler

147 points by marcodiego 5y ago

jeffbee 5y ago
Would be neat if there were materials. Code for this has just started to trickle out earlier this year at https://github.com/google/ghost-userspace https://github.com/google/ghost-userspace and https://github.com/google/ghost-kernel https://github.com/google/ghost-kernel, but Google has been talking in public about userspace scheduling since 2013.
- neelnatu 5y ago
  https://netdevconf.info/0x15/session.html?ghOSt:-Fast-&-Flexible-User-Space-Delegation-of-Linux-Scheduling https://netdevconf.info/0x15/session.html?ghOSt:-Fast-&-Flex...
marcodiego 5y ago
IIRC, there were some efforts years ago to bring memory management and scheduling to user space. I think those efforts failed mostly because they were very intrusive and imposed performance regressions when not in use. If scheduling is finally allowed from user space without negative effects it will bring a new age of experimentation and finely tuned custom adaptations for the kernel. Other recent related developments and news: https://github.com/rgushchin/atc https://www.phoronix.com/scan.php?page=news_item&px=Linux-BPF-Scheduler https://lore.kernel.org/bpf/CA+khW7i460ey-UFzpMSJ8AP9QeD8ufa4FzLA4PQckNP00ShQSw@mail.gmail.com/T/#u
- nexuist 5y ago
  Wouldn't putting the scheduler in userspace double the amount of context switching? You'd have to interrupt a userspace thread and jump to the kernel, then jump from the kernel to the scheduler program (switch 1), then jump from the scheduler back to the kernel, and then jump from the kernel to the next scheduled thread (switch 2). Having the kernel accessible from userspace as it already is saves two steps, but you still have to use the kernel as a middleman unless there's some way for the scheduler program to directly jump into another process (which I don't think there is because wouldn't this break memory protection?)
  - jeffbee 5y ago
    You kind of have to view this work in light of the fact that Google internally uses their private SwitchTo API that allows userspace to invoke a thread directly and much more efficiently than the kernel does. They tried to upstream it but kernel maintainers lack the industry experience that would allow them to perceive the benefits. https://lkml.org/lkml/2020/7/22/1202 https://lkml.org/lkml/2020/7/22/1202 Apparently now known as UMCG. https://lwn.net/Articles/863386/ https://lwn.net/Articles/863386/
    - marcodiego 5y ago
      A think a more acceptable approach would a system call with two arguments. Both arguments are lists of task_id, task descriptors, pids, whatever uniquely identify a task. The first argument would be a list of tasks to be run before the syscall returns. The second argument would be a list of tasks to be run in that order (with the possibility of unlisted tasks being run between them) before the syscall returns. This could not only replace switchTo, it also would enable scheduling from user space with a very small number of context switches. I'd call this syscall "schedule".
      - scottlamb 5y ago
        That's certainly a more complex interface, but I don't think it enables anything more. I think switchto (which became futex_swap which became umcg_swap) from thread X is roughly "suspend the current thread (X) and unsuspend Y", where suspend is "wait on a futex". When all of the tasks you propose specifying are done, one of them can just unsuspend X (possibly suspending itself at the same time). (Caveat: I don't really know what changed between futex_swap and umcg_swap.) btw, I don't think it's fair to say the kernel maintainers lacked the industry experience to perceive the benefits. I've glanced at some of the UMCG threads and it seems like reviewers have legitimate feedback aimed at improving the patchset rather than rejecting it. Assuming posk has enough time to keep making new drafts, I expect it to be merged eventually.
        marcodiego 5y ago
- indolering 5y ago
  You are correct that all attempts at bringing scheduling out of kernel space have failed, even the L4 folks found the performance impact intolerable. However, this uses eBPF to perform logical operations within kernel space that are loaded from user space at runtime. See https://ebpf.io/ https://ebpf.io/ for more info.
javert 5y ago
Is there a paper? I'm mostly interested in ghOSt itself. I already found the github projects [1] [2]. [1] https://giters.com/google/ghost-userspace https://giters.com/google/ghost-userspace [2] https://github.com/google/ghost-kernel https://github.com/google/ghost-kernel
kzrdude 5y ago
So, is this finally an opening to plugging in some scheduling customizations, even to the degree of the -ck (Con Kolivas) kernels? Since he's recently retired his maintenance of those, it seems topical.
PaulDavisThe1st 5y ago
Possibly more interesting (and a base for this work): https://netdevconf.info/0x15/slides/25/ghOSt%20Talk%20(Netdev).pdf https://netdevconf.info/0x15/slides/25/ghOSt%20Talk%20(Netde... "Fast & Flexible User-Space Delegation of Linux Scheduling" from Google, July 2021
- jeffbee 5y ago
  50% lower tail latency for web search is a hell of a result to be buried so deep in an obscure paper.
  - neelnatu 5y ago
    An updated version of the paper will be presented at SOSP'21: https://sosp2021.mpi-sws.org/accepted.html https://sosp2021.mpi-sws.org/accepted.html
Matthias247 5y ago
I’m curious how the ghOSt work presented here relates to the user managed concurrency groups (umcg) work that also allows userspace to take scheduling decisions. Seems like both originate at google.
nsm 5y ago
Whenever I read news about the kernel surfacing more traditionally OS level features to user space, I'm reminded of Stephen Kell's "Unix, Plan 9 and the Lurking Smalltalk"[1]. There are a lot of parallels between the Smalltalk VMs (where nearly everything about the system is editable and accessible to the user) and where Linux is heading in certain respects, except going there by a very round-about way and relying on very limited binary formats and C instead of high level languages and live objects. [1]: https://www.humprog.org/~stephen//research/papers/kell19unix-personal.pdf https://www.humprog.org/~stephen//research/papers/kell19unix...

147 points by marcodiego 5y ago

Would be neat if there were materials. Code for this has just started to trickle out earlier this year at https://github.com/google/ghost-userspace https://github.com/google/ghost-userspace and https://github.com/google/ghost-kernel https://github.com/google/ghost-kernel, but Google has been talking in public about userspace scheduling since 2013.

neelnatu 5y ago
https://netdevconf.info/0x15/session.html?ghOSt:-Fast-&-Flexible-User-Space-Delegation-of-Linux-Scheduling https://netdevconf.info/0x15/session.html?ghOSt:-Fast-&-Flex...

marcodiego 5y ago

IIRC, there were some efforts years ago to bring memory management and scheduling to user space. I think those efforts failed mostly because they were very intrusive and imposed performance regressions when not in use. If scheduling is finally allowed from user space without negative effects it will bring a new age of experimentation and finely tuned custom adaptations for the kernel. Other recent related developments and news: https://github.com/rgushchin/atc https://www.phoronix.com/scan.php?page=news_item&px=Linux-BPF-Scheduler https://lore.kernel.org/bpf/CA+khW7i460ey-UFzpMSJ8AP9QeD8ufa4FzLA4PQckNP00ShQSw@mail.gmail.com/T/#u

nexuist 5y ago
Wouldn't putting the scheduler in userspace double the amount of context switching? You'd have to interrupt a userspace thread and jump to the kernel, then jump from the kernel to the scheduler program (switch 1), then jump from the scheduler back to the kernel, and then jump from the kernel to the next scheduled thread (switch 2). Having the kernel accessible from userspace as it already is saves two steps, but you still have to use the kernel as a middleman unless there's some way for the scheduler program to directly jump into another process (which I don't think there is because wouldn't this break memory protection?)
- jeffbee 5y ago
  You kind of have to view this work in light of the fact that Google internally uses their private SwitchTo API that allows userspace to invoke a thread directly and much more efficiently than the kernel does. They tried to upstream it but kernel maintainers lack the industry experience that would allow them to perceive the benefits. https://lkml.org/lkml/2020/7/22/1202 https://lkml.org/lkml/2020/7/22/1202 Apparently now known as UMCG. https://lwn.net/Articles/863386/ https://lwn.net/Articles/863386/
  - marcodiego 5y ago
    A think a more acceptable approach would a system call with two arguments. Both arguments are lists of task_id, task descriptors, pids, whatever uniquely identify a task. The first argument would be a list of tasks to be run before the syscall returns. The second argument would be a list of tasks to be run in that order (with the possibility of unlisted tasks being run between them) before the syscall returns. This could not only replace switchTo, it also would enable scheduling from user space with a very small number of context switches. I'd call this syscall "schedule".
    - scottlamb 5y ago
      That's certainly a more complex interface, but I don't think it enables anything more. I think switchto (which became futex_swap which became umcg_swap) from thread X is roughly "suspend the current thread (X) and unsuspend Y", where suspend is "wait on a futex". When all of the tasks you propose specifying are done, one of them can just unsuspend X (possibly suspending itself at the same time). (Caveat: I don't really know what changed between futex_swap and umcg_swap.) btw, I don't think it's fair to say the kernel maintainers lacked the industry experience to perceive the benefits. I've glanced at some of the UMCG threads and it seems like reviewers have legitimate feedback aimed at improving the patchset rather than rejecting it. Assuming posk has enough time to keep making new drafts, I expect it to be merged eventually.
      - marcodiego 5y ago
indolering 5y ago
You are correct that all attempts at bringing scheduling out of kernel space have failed, even the L4 folks found the performance impact intolerable. However, this uses eBPF to perform logical operations within kernel space that are loaded from user space at runtime. See https://ebpf.io/ https://ebpf.io/ for more info.

javert 5y ago

Is there a paper? I'm mostly interested in ghOSt itself. I already found the github projects [1] [2]. [1] https://giters.com/google/ghost-userspace https://giters.com/google/ghost-userspace [2] https://github.com/google/ghost-kernel https://github.com/google/ghost-kernel

kzrdude 5y ago

So, is this finally an opening to plugging in some scheduling customizations, even to the degree of the -ck (Con Kolivas) kernels? Since he's recently retired his maintenance of those, it seems topical.

PaulDavisThe1st 5y ago

Possibly more interesting (and a base for this work): https://netdevconf.info/0x15/slides/25/ghOSt%20Talk%20(Netdev).pdf https://netdevconf.info/0x15/slides/25/ghOSt%20Talk%20(Netde... "Fast & Flexible User-Space Delegation of Linux Scheduling" from Google, July 2021

jeffbee 5y ago
50% lower tail latency for web search is a hell of a result to be buried so deep in an obscure paper.
- neelnatu 5y ago
  An updated version of the paper will be presented at SOSP'21: https://sosp2021.mpi-sws.org/accepted.html https://sosp2021.mpi-sws.org/accepted.html

Matthias247 5y ago

I’m curious how the ghOSt work presented here relates to the user managed concurrency groups (umcg) work that also allows userspace to take scheduling decisions. Seems like both originate at google.

nsm 5y ago

Whenever I read news about the kernel surfacing more traditionally OS level features to user space, I'm reminded of Stephen Kell's "Unix, Plan 9 and the Lurking Smalltalk"[1]. There are a lot of parallels between the Smalltalk VMs (where nearly everything about the system is editable and accessible to the user) and where Linux is heading in certain respects, except going there by a very round-about way and relying on very limited binary formats and C instead of high level languages and live objects. [1]: https://www.humprog.org/~stephen//research/papers/kell19unix-personal.pdf https://www.humprog.org/~stephen//research/papers/kell19unix...