Comment by adrianmonk | Hacker News Reader

Comment by adrianmonk | Hacker News Reader

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

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

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

[1] http://www.erights.org/elib/distrib/captp/index.html

[2] http://www.erights.org/index.html

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.

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.

Java was still pretty brand spanking new in ‘96. And RMI wasn’t inflicted on us until ‘97. But half the stuff we use was invented in the 70’s and explored in the 80’s anyway.

The classes in college that I have used the most by far are the series that covered logic and set theory, and the one on distributed computing. The latter does take some of the fun out of people rediscovering things though.

IIRC, Berkeley had an OS with swarm computing and process migration around ‘87. It wasn’t until 20 years later that the speed of disk vs networking had a similar imbalance again. And of course the mainframe guys must constantly think the rest of us are idiots.

Oh I know, I started programming in '92 or so.

The idea of creating a program and sending it across an abstraction boundary for execution to avoid the cost of continually navigating the abstraction boundary for each step in the program is reasonably trivial. It was an approach I used in my first job for optimizing access to data in serialized object heaps - rather than deserialize the whole session object heap for each web request (costly), I'd navigate the object graph in the binary blob, but this required following offsets, arrays etc. The idea of a 'data path' program for fetching data occurred almost immediately.

In the end a different approach using very short-lived objects which were little more than wrappers around offsets into the heap combined with type info turned out to be more usable, and with generational GC, was plenty fast too; the abstraction stack was thin, the main cost avoided was materializing a whole heap.

Everyone is doomed to gradually rediscover QNX while never reinventing it.

The extent to which computer programmers literally don't read anything about computing history or alternative systems is quite funny. I can't wait until, sometime in the next few years, someone announces they're "modernizing the cloud operating system" and "unlocking the synergies between microservices" or whatever by... reinventing MsgSend, which we all knew about 30 years ago at this point.

To save you some time and test my prediction powers: they'll get $50 million in funding and almost flop until they find a way to stick Linux inside of a virtual machine (so it can act like a glorified driver for you, for device compatibility, because it turns out burning cash on trying to replicate 10 million lines of drivers isn't smart). It will grow Docker compatibility at some point. 90% of the development will come from one group of ~6 people. Then they'll get bought out and the project will die overnight. The end.

I wish some day that I could be that nonsense person and Dunning Kreuger my way to mad money by using my powers of selling the past as the future.

Batching and pipelining calls is a quite common design in RPC, especially databases. Mongodb for example has a very easy to use aggregate([op1, op2, ...]) function which you use to build a pipeline of generic operations that all data flows through on the server side, eg input to op2 is the output of op1, and so on.

It doesn't allow any client logic between op1 and op2 if that's what you meant though?

> It doesn't allow any client logic between op1 and op2 if that's what you meant though?

Yeah that seems to be the trick doesn’t it? Is the next step beyond pipelining A) provide a way to run limited code on the server end or B), reformulate the API so that these situations don’t occur as readily.

Take a classic I/O pattern. Give me 5k of data from X, write all 5k out to Y. Except that’s not what actually happens. It tells you what it wrote and you have to do a conditional branch and arithmetic. I still recall feeling shocked and a little scandalized when I learned that these APIs worked like this. First, why didn’t you just do what I asked, and second, why am I the one held responsible for all of the bookkeeping when you are the one selectively following instructions?

I think one of the features of completion ports was a slightly better, “go do this and don’t bother coming back until you have”.

In a client server application I designed as part of a previous job we did exactly this.

An RPC call was a list of functions and arguments, and there was a special tag that could refer back to a previous return value in the same set of calls.

All calls in the same request was executed in the same transaction. Them main goal was to avoid usingddistributed transactions, but also helped reducing latency over slow connections.

I think my comment got lost because I can’t find it, but I said something like: maybe we need a formal macroassembler for IPC/RPC calls instead of running “code” directly in the kernel.

It looks like inventing GraphQL for kernel:

On the web: instead of combining results of several RESTful API calls on the client, send a GraphQL request and combine the REST call on the server.

On a host: instead of combining results of several syscalls in user-space, send a program to an in-kernel interpreter that would combine the syscalls kernel-side aka define a syscall such as readfile() on the fly.

Yeah I had that though while writing up my first follow up, but the compositing here is between multiple, small endpoints and GraphQL is subsetting one large endpoint.

Maybe you could model kernel calls as a single large subsystem that allows multiple questions, but GraphQL seems a lot less imperative that syscalls so I’m having trouble picturing how that would translate.

In theory, the JVM could allow users to upload ‘arbitrary’ code, where the configuration of the JVM (custom class loader) enforces various restrictions as to want that ‘arbitrary‘ means.

I have never seen that implemented, though, possibly because of the experience with the increase in attack surface Java applets gave, or because it is hard to restrict memory and CPU usage of uploaded code.

I heard a presentation on Jini when it was young and this something they very much wanted to do, but I believe it got watered down to mostly sending code from the server to the client and not so much the other way around.

This is reminding me of a research hardware project from the same era where they took NUMA design about as far as you could go; they embedded simple (vector?) computing directly onto the RAM chips, so the code goes to the data instead of the other way around. One of their demos was splitting the screen up into cells and calculating pixels in parallel directly on the memory chips.

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

Those shortcuts are generally about the ability to batch independent concurrent operations though e.g. instead of

    call(foo)
    call(bar)
    call(baz)

you can

    multicall(foo, bar, baz)

which goes from 3 sequential round-trips to 1, without increasing "instantaneous" server load as much as performing concurrent calls (promise-style) would.

Here this is more of a pipeline desire and the issue there is it requires some error handling and adaptation between the calls, as the various functions are not always compatible (you often can't feed the output of one as the input of the next).

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/

One can easily imagine a restricted subset of eBPF that is not turing complete and could be safe for unprivileged users to use.

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.

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.

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.

eBPF right now issues fence instructions before computed address loads, in order to manually shutdown speculative instructions. They also do a cute trick to compute the address with a mask so that if a speculative access does happen, the speculatively computed offset is still in the valid range.

That's a very good point, and thank you for correcting me.

eBPF isn't fundamentally unsafe (and, in particular, it's not Turing-complete, precisely because it's guaranteed that all eBPF programs terminate). It's just very ambitious and it exposes too much attack surface for people to feel comfortable making it available to unprivileged users.

However, we do have a similar system exposed to unprivileged users - classic BPF. You could imagine writing classic BPF programs to chain multiple system calls with just one context switch.

> it's not Turing-complete

On their own, but there is more than 1 way to insert BPF programs.

If there is a key learning from ROP style exploits, is that you can assemble surprising constructs out of thin air. Linux 5.6 adds way for eBPF programs to write vtables. That one alone is an exploit waiting to happen. You just have to connect the calls just right and poof, eBPF programs calling each other: Turing completeness achieved.

> On their own, but there is more than 1 way to insert BPF programs.

And the recursion, even tail recursion, in BPF is limited for that very reason.

All eBPF programs have a statically verifiable worst case execution time.

My point is that this limitation can be bypassed if you are smart enough. The Linux kernel is more complex than any single BPF program, it has side effects.

For example, let say that I am an attacker who which to execute a loop to brute force a key using a new side channel from kernel space. eBPF programs are now available to userspace with "insert new shiny here". I add one as a performance tracepoint, then one in the packet filter, then one modifying a vtable somewhere. Now, I manage to make them oscillate and call each other while never leaving kernel space. I now "deadlock" the kernel with my small BPF programs until I manage to extract what I am after, then let the "deadlock" go away.

It take only 1 bug to make this happen. Each BFP program individually return, but only to be called again. If you let users put these in the kernel, this will happen eventually. This kind of tricks has been used over and over with other technologies.

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

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.

> verifying that it's simple and harmless

I look forward to your PhD thesis disproving Rice's theorem

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.

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?

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"

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.

BPF isn't turning complete in very interesting ways that allows it to still be fairly general (but obviously not completely general).

No computer is actually Turing-complete, since no computer has infinite memory.

Math is different from reality.

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

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.

Reply on news.ycombinator.com