7 ms·

I'm not a kernel hacker, but the Linux kernel now has an in-kernel VM (BPF), doesn't it? As I understand, it started with letting you load programs into the ker

I'm not a kernel hacker, but the Linux kernel now has an in-kernel VM (BPF), doesn't it? As I understand, it started with letting you load programs into the kernel to filter network packets, but now it allows several other things. So, readfile() combines 3 syscalls into 1 by manually implementing a new system call. Would another approach be to make these same calls (openat(), read(), and close()) and some others available to BPF programs? The idea is to provide a more general mechanism, rather than solving this one case. Obviously, the kernel change would need to be feasible, and the result would need to be safe and fast. Then a user mode program could effectively just write its own readfile(), or some other variation in case that exact sequence of calls isn't what it needs. (An even more out-there idea is to have the kernel auto-detect situations like this, examine the native code, then after verifying that it's simple and harmless, just move a whole chunk of code or tight loop into the kernel. In effect, it would dynamically generate a new syscall.)

dmitrygr 7y ago
> verifying that it's simple and harmless I look forward to your PhD thesis disproving Rice's theorem
- klyrs 7y ago
  Funny thing about Rice's theorem. It says that semantic properties (such as halting) are undecidable in general. That says nothing about specific programs. It's easy to prove that certain programs halt; it's easy to prove that others never halt. In fact, there are whole classes of programs for which it is trivial to prove halting (e.g. bf programs that do not contain [ or ]), or non-halting (e.g. bf programs that contain a single + and the remaining instructions are [ or ]). One need not waste their time proving an impossible generality along the path to proving a specific possibility.
  - deleted 7y ago
    [deleted]
  - dTal 7y ago
    Yes, but if you enforce that the program be decidable, as part of a dynamic kernel API, then you are no longer offering a Turing-complete language. Are there so many use cases that would benefit from this nonetheless, that it wouldn't be better to just hard-code them?
    - klyrs 7y ago
      That's not how I (generously) read GP's suggestion. It could be worthwhile to implement heuristics that can be used to prove certain classes safe; and those could be lifted to a "new syscall". If the heuristics give a non-result, gracefully fall back to not pulling userspace crap into the kernel. Not saying I'd be interested in doing this work, but there's a vast middle ground between "the halting problem is undecideable" and "we can never know if while(1); will halt"
      - adrianmonk 7y ago
        Exactly. That's what I meant. I tried to hint at that by saying you'd verify that it's simple and harmless, meaning you solve the simple cases and leave the others as-is. But then I also described it as a more general mechanism, and I guess people ran with that and kinda understandably interpreted it to mean a fully general mechanism. About the halting problem, I'm not necessarily convinced that prevents this from being done. At least not in theory. (This is getting impractical, but it's interesting to think about.) Let's say I have an infinite loop in user space. I then move the infinite loop to kernel space. What specific harm have I caused? I already had an infinite loop; now I still have one. Though there might be some consequences other than burning CPU cycles. I think "kill -9" may not take effect until system calls return. Also, there's such a thing as scheduler priorities and CPU quotas, and those might be impacted. Of course it would always be possible to just exclude anything with a loop from what you try to move into the kernel. Or it might also be possible to handle infinite loops with some kind of complicated thing involving a timeout and restarting system calls.
    - monocasa 7y ago
      BPF isn't turning complete in very interesting ways that allows it to still be fairly general (but obviously not completely general).
- dTal 7y ago
  The snark was perhaps a touch excessive, but this is indeed an excellent reason why the radical suggestion proffered shall remain radical. (isn't this basically just a kernel module?)
  - im3w1l 7y ago
    It's very easy to misinterpret what a theorem means. And doing this can derail a conversation for decades. I remember two such cases. The theorem that two hidden layer neural networks can approximate any function - Common interpretation: two layers are enough. And a proof of well I don't recall the details... being interpreted as imaging being limited by wavelength. Then came super resolution which worked around it by not using some of the implicit assumptions of the common interpretation. So I think it's justified to take issue.
rjeli 7y ago
One possibility is integrating io_uring with bpf: https://lwn.net/Articles/810414/ https://lwn.net/Articles/810414/
Elv13 7y ago
eBPF isn't safe to load without root privilege. This means no containers and no users process. From what I saw so far, there is fear that letting Turing complete programs in the kernel would make some future CPU/hardware vulnerabilities more dangerous. While the compiler makes sure the program return, it cannot make sure it isn't nefarious. ref: https://lwn.net/Articles/808048/ https://lwn.net/Articles/808048/
- loeg 7y ago
  One can easily imagine a restricted subset of eBPF that is not turing complete and could be safe for unprivileged users to use.
  - amscanne 7y ago
    That’s what BPF is already. It’s not Turing complete. Unbounded loops and backward branching is not allowed. The problem isn’t Turing completeness. It’s that there’s are too many micro-architectural side channels and unknowns.
    - monocasa 7y ago
      They currently go out of their way to remove microarchitectural side channels. Yes, there's almost certainly others, but it's pretty clear that the end goal is to allow non root creation of bpf programs.
      - nickodell 7y ago
        Is it really possible to remove the side channels? Even if you formally prove that it does not access memory outside of authorized regions, that doesn't prevent it from speculatively accessing unauthorized memory. We've seen Spectre exploits through sandboxed Javascript. Unless you separated the eBPF VM address space from the kernel address space, I suspect you would have the exact same problems that browsers have had. But if you did put them in separate address spaces, then why bother with eBPF? You could run a normal userspace program.
hinkley 7y ago
I remember a paper decades ago now about a way to reduce RPC call round-tripping by sending something akin to promises back and forth, so you could pass the result of one remote call to another one without transferring it across the network. Kinda think something similar might be useful here. What typically ends up happening in “services” (or any distributed system) is that you start creating convenience APIs to speed things up that are mostly just combinations of other calls, and you stay with the ones that seem like they might be the most useful, so you don’t slam into combinatorics face first. Given the amount of talk I’ve heard about system call overhead lately, it sounds like the magnitude of the delays is creeping up again (especially post-Meltdown).
- exrook 7y ago
  I don't know if this is what you were thinking of, but capnproto[0] does exactly that with a promise like interface. Actually this may be the paper you were referencing, from the bottom of the capnproto page: > Cap’n Proto’s RPC protocol is based heavily on CapTP[1], the distributed capability protocol used by the E programming language[2]. Lots of useful material for understanding capabilities can be found at those links. [0] https://capnproto.org/rpc.html https://capnproto.org/rpc.html [1] http://www.erights.org/elib/distrib/captp/index.html http://www.erights.org/elib/distrib/captp/index.html [2] http://www.erights.org/index.html http://www.erights.org/index.html
  - hinkley 7y ago
    Very interesting, but if memory serves, Microsoft had this idea maybe in ‘96. Though patent expiry-wise, the timing of cap’n proto might make a bit of sense.
    - barrkel 7y ago
      E is from '97 and built on top of ideas implemented before that with extensions to Java; not sure of the date, but could easily predate '96.
      - 7y ago
fragmede 7y ago
BPF is not run inside of a virtual machine (the same way that Java is). It is not safe to load untrusted code into it.

dmitrygr 7y ago

> verifying that it's simple and harmless I look forward to your PhD thesis disproving Rice's theorem

klyrs 7y ago
Funny thing about Rice's theorem. It says that semantic properties (such as halting) are undecidable in general. That says nothing about specific programs. It's easy to prove that certain programs halt; it's easy to prove that others never halt. In fact, there are whole classes of programs for which it is trivial to prove halting (e.g. bf programs that do not contain [ or ]), or non-halting (e.g. bf programs that contain a single + and the remaining instructions are [ or ]). One need not waste their time proving an impossible generality along the path to proving a specific possibility.
- deleted 7y ago
  [deleted]
- dTal 7y ago
  Yes, but if you enforce that the program be decidable, as part of a dynamic kernel API, then you are no longer offering a Turing-complete language. Are there so many use cases that would benefit from this nonetheless, that it wouldn't be better to just hard-code them?
  - klyrs 7y ago
    That's not how I (generously) read GP's suggestion. It could be worthwhile to implement heuristics that can be used to prove certain classes safe; and those could be lifted to a "new syscall". If the heuristics give a non-result, gracefully fall back to not pulling userspace crap into the kernel. Not saying I'd be interested in doing this work, but there's a vast middle ground between "the halting problem is undecideable" and "we can never know if while(1); will halt"
    - adrianmonk 7y ago
      Exactly. That's what I meant. I tried to hint at that by saying you'd verify that it's simple and harmless, meaning you solve the simple cases and leave the others as-is. But then I also described it as a more general mechanism, and I guess people ran with that and kinda understandably interpreted it to mean a fully general mechanism. About the halting problem, I'm not necessarily convinced that prevents this from being done. At least not in theory. (This is getting impractical, but it's interesting to think about.) Let's say I have an infinite loop in user space. I then move the infinite loop to kernel space. What specific harm have I caused? I already had an infinite loop; now I still have one. Though there might be some consequences other than burning CPU cycles. I think "kill -9" may not take effect until system calls return. Also, there's such a thing as scheduler priorities and CPU quotas, and those might be impacted. Of course it would always be possible to just exclude anything with a loop from what you try to move into the kernel. Or it might also be possible to handle infinite loops with some kind of complicated thing involving a timeout and restarting system calls.
  - monocasa 7y ago
    BPF isn't turning complete in very interesting ways that allows it to still be fairly general (but obviously not completely general).
dTal 7y ago
The snark was perhaps a touch excessive, but this is indeed an excellent reason why the radical suggestion proffered shall remain radical. (isn't this basically just a kernel module?)
- im3w1l 7y ago
  It's very easy to misinterpret what a theorem means. And doing this can derail a conversation for decades. I remember two such cases. The theorem that two hidden layer neural networks can approximate any function - Common interpretation: two layers are enough. And a proof of well I don't recall the details... being interpreted as imaging being limited by wavelength. Then came super resolution which worked around it by not using some of the implicit assumptions of the common interpretation. So I think it's justified to take issue.

rjeli 7y ago

One possibility is integrating io_uring with bpf: https://lwn.net/Articles/810414/ https://lwn.net/Articles/810414/

Elv13 7y ago

eBPF isn't safe to load without root privilege. This means no containers and no users process. From what I saw so far, there is fear that letting Turing complete programs in the kernel would make some future CPU/hardware vulnerabilities more dangerous. While the compiler makes sure the program return, it cannot make sure it isn't nefarious. ref: https://lwn.net/Articles/808048/ https://lwn.net/Articles/808048/

loeg 7y ago
One can easily imagine a restricted subset of eBPF that is not turing complete and could be safe for unprivileged users to use.
- amscanne 7y ago
  That’s what BPF is already. It’s not Turing complete. Unbounded loops and backward branching is not allowed. The problem isn’t Turing completeness. It’s that there’s are too many micro-architectural side channels and unknowns.
  - monocasa 7y ago
    They currently go out of their way to remove microarchitectural side channels. Yes, there's almost certainly others, but it's pretty clear that the end goal is to allow non root creation of bpf programs.
    - nickodell 7y ago
      Is it really possible to remove the side channels? Even if you formally prove that it does not access memory outside of authorized regions, that doesn't prevent it from speculatively accessing unauthorized memory. We've seen Spectre exploits through sandboxed Javascript. Unless you separated the eBPF VM address space from the kernel address space, I suspect you would have the exact same problems that browsers have had. But if you did put them in separate address spaces, then why bother with eBPF? You could run a normal userspace program.

hinkley 7y ago

I remember a paper decades ago now about a way to reduce RPC call round-tripping by sending something akin to promises back and forth, so you could pass the result of one remote call to another one without transferring it across the network. Kinda think something similar might be useful here. What typically ends up happening in “services” (or any distributed system) is that you start creating convenience APIs to speed things up that are mostly just combinations of other calls, and you stay with the ones that seem like they might be the most useful, so you don’t slam into combinatorics face first. Given the amount of talk I’ve heard about system call overhead lately, it sounds like the magnitude of the delays is creeping up again (especially post-Meltdown).

exrook 7y ago
I don't know if this is what you were thinking of, but capnproto[0] does exactly that with a promise like interface. Actually this may be the paper you were referencing, from the bottom of the capnproto page: > Cap’n Proto’s RPC protocol is based heavily on CapTP[1], the distributed capability protocol used by the E programming language[2]. Lots of useful material for understanding capabilities can be found at those links. [0] https://capnproto.org/rpc.html https://capnproto.org/rpc.html [1] http://www.erights.org/elib/distrib/captp/index.html http://www.erights.org/elib/distrib/captp/index.html [2] http://www.erights.org/index.html http://www.erights.org/index.html
- hinkley 7y ago
  Very interesting, but if memory serves, Microsoft had this idea maybe in ‘96. Though patent expiry-wise, the timing of cap’n proto might make a bit of sense.
  - barrkel 7y ago
    E is from '97 and built on top of ideas implemented before that with extensions to Java; not sure of the date, but could easily predate '96.
    - 7y ago

fragmede 7y ago

BPF is not run inside of a virtual machine (the same way that Java is). It is not safe to load untrusted code into it.