3 ms·

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

by 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).
teddyh 7y ago
No computer is actually Turing-complete, since no computer has infinite memory. Math is different from reality.

by dTal 7y ago

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).

teddyh 7y ago

No computer is actually Turing-complete, since no computer has infinite memory. Math is different from reality.