Two new ways to read a file quickly
lwn.net
lwn.net
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 look forward to your PhD thesis disproving Rice's theorem
One need not waste their time proving an impossible generality along the path to proving a specific possibility.
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"
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.
Math is different from reality.
(isn't this basically just a kernel module?)
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.
The problem isn’t Turing completeness. It’s that there’s are too many micro-architectural side channels and unknowns.
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.
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.
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.
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.
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.
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).
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
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.
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.
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.
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”.
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.
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.
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.
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.
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.
Those shortcuts are generally about the ability to batch independent concurrent operations though e.g. instead of
call(foo)
call(bar)
call(baz)
multicall(foo, bar, baz)
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).
It might work like this: user space allocates a buffer, fills it with syscall numbers and arguments, then passes it to the kernel. The kernel executes each syscall in series, placing the return values in the array originally containing arguments. This syscall would not return to user space until all syscalls in the buffer are processed.
Does this idea have any potential?
> Syslets are small, simple, lightweight programs (consisting of system-calls, 'atoms') that the kernel can execute autonomously (and, not the least, asynchronously), without having to exit back into user-space. ....
> Syslets consist of 'syslet atoms', where each atom represents a single system-call. These atoms can be chained to each other: serially, in branches or in loops.
To be fair, io_uring seems to be a pretty sane design. But, for example, for many years anything with a shared ring buffer between userspace and the kernel was suspect. Now there are several such interfaces. Overall tolerance has grown, especially on the part of Linus. The kernel is much larger, and Linus seems to have become much more deferential to subsystem maintainers as his ability to understand and opine on code has slipped beyond his grasp.
User space memory mapping (naturally left to the user) seems to be the error prone bit here.
search for "sys_umem" here: https://people.redhat.com/mingo/syslet-patches/patches/async...
I understand that this is low level stuff for experienced developers, but this approach basically asks the programmer to play linker. Entirely doable but I wonder what it looks like at scale (LOC).
Similarly if all the syscalls done between fork and exec could be squeezed into a single uring chain without any intervening userspace code then the kernel could skip some costly virtual memory operations, bringing us closer to posix_spawn behavior.
And ideally also the cost of mmap_sem (the lock for an address space's memory map), which can be one of the most contended locks in a workload.
> Similarly if all the syscalls done between fork and exec could be squeezed into a single uring chain without any intervening userspace code then the kernel could skip some costly virtual memory operations, bringing us closer to posix_spawn behavior.
I'd love to see a way of doing this with io_uring.
This idea reminds me of pipelined Redis commands. It does work to boost total throughout, but it’s significantly more complicated to use in practice.
whoops. I probably should have thought of that.
1. Enqueue A = openat(...)
2. Enqueue B = read(A, buf, sz)
3. Enqueue close(A)
4. Commit, return B to userspace
In the case of uring I suppose it is possible to link the calls to fail at the first failure.
That's what the min_fd patch is for, and potentially other systems for reserving blocks of fds. Much like memory, you'll ask the kernel for a block of it and then do your own allocations out of that.
Think about how pipelined commands work in a command shell if you want to understand how to construct a program that can define a sequence of operations on objects before they're defined.
I first heard about io_uring here on HN and a rust DB lib called Sled was used as an example.
But when do we get fast MySQL etc?
I recall a paper from 2012 or so that implemented a PoC syscall buffer so a bunch of syscalls could be scheduled and executed sequentially with just one syscall. They claimed 40%+ performance improvements in various programs, including MySQL. This was of course before meltdown and other cache mitigations were a thing.
So programs, including MySQL and Postgres (hey, I know something about various DB storage engines), would benefit massively from scheduled sequential syscalls (easy to adopt, big win) and true async io (io_uring, harder to adopt, even bigger win).
Ideally readfile would take and return a filefd (default -1); if present, skip the open and just read (closing on EOF). This also fixes the EINTR/SA_RESTART issue loeg[0] raised. From a C perspective, it does have a problem of needing to return multiple values (both a fd and a bytecount), though.
Sure, I see why the kernel people wouldn't mind having people specify their own fd numbers, but doing the accounting necessary for that (to avoid conflicts) in userspace doesn't seem nice. Especially when there will be libraries that also may make use of the functionality.
Is there even any way to see what file descriptors that are open without doing a syscall?
At least I think I’m reading this correctly.
A little surprised they didn't also roll in an optional lseek() offset in case you wanted a specific area of the file. Then it would roll 4 syscalls into 1. The somewhat similar sendfile() accepts an offset.
It would not be intended as a convenience API for slurping an entire file but as a performance API for very short reads (straight open(); read(); close() where the syscall overhead is enormous).
The implementation(s) by Greg Kroah-Hartman don't even bother looping until read returns empty or the buffer is full.
The `readfile()` system call will reduce that by some factor, though probably not as high as a factor of one third (it replaces three system calls with two, assuming it turns out to be useful). But getting all the data in one call will be even faster.
Incidentally, a typical read-all-of-this-file function in user-land allocates a buffer of the right size after doing an `open()` and then `fstat()` to find the file's size. Whereas a system call to read a file in one go really can't do that unless it establishes a memory mapping (which is... expensive). So I rather question the utility of this thing. Also, since one might not know what size buffer to give it, it might as well have an option to return an open FD. Or the app should have to `stat()` then `readfile()`, thus replacing three syscalls (`open()`, `fstat()`, `close()` with two -- bummer. Or the caller can `readfile()` repeatedly if the buffer given was not large enough (oof).
No, I'm pretty sure this `readfile()` can't possibly make reading lots of tiny files fast enough to not want a better solution for getting mounted filesystem metadata out of the kernel.
I would welcome being proved wrong.
It violates the unix philosophy of "one call for one specific thing", of course, but massively speeds up performance in practical applications.
In fact, you could get a LOT of speedup at Linux/Microsoft/... (the OS level) by figuring out highly common combinations of syscalls typically all called in a row with mostly the same arguments, and combining them into one single syscall.
Perhaps one day we can get back to that model, or maybe now that Linux has gone corporate those days are gone. Even when you can make something faster with a simple, straight-forward solution, there's always that one corporate sponsor who doesn't benefit. Before Linux would just tell them sod-off.
> Yes, you could do it differently. In fact, other OS's _do_ do it differently. But take a look at our process timings (ignoring wild claims by disgruntled SCO employees that can probably be filed under "L" for "Lies, Outright"). Think about WHY our system call latency beats everybody else on the planet. Think about WHY Linux is fast. It's because it's designed right.
Source: https://lkml.org/lkml/2000/8/25/80
The same architectural approach was taken with fork: Linux optimized the heck out of fork to the point where fork on Linux was faster than thread creation on Windows. On multiple occasions Linus has argued (and proven), that optimizing the simple but "heavy-weight" approach can reap dividends at least as great as more complex, more flexible architectures.
Of course, that was then and this is now. And many things have changed, including the success of Linux. I'm just suggesting, or perhaps implying, that there's more eagerness to entertain the replacement of traditional syscall semantics and other subsystems with more complex frameworks than there once used to be. In the context of Spectre, arguably it would have been easier for a younger Linus (and younger Linux) to refuse to rearchitect syscalls (with the concomitant additional kernel and semantic complexity), to tell everyone to sit tight and wait for AMD and Intel to come up with mitigating hardware fixes, and in the intervening years just take the performance hit.
To be fair, this has been an issue since the first unix kernels, and even though /proc and sysctl are an improvement over grepping kernel memory from user space (the incredibly hackish way old ps worked), in my opinion it's still a big mess in various ways.
Just in case you aren't aware, linux ps/top/etc. has to open possibly hundreds of fake files, parsing from text a bunch of stuff which may or may not be there or valid or the same data type depending on your kernel configuration or version. Just because you could write 'ps' with awk, doesn't make it good. I wouldn't object at all to the /proc interface, as a way of enabling simple tools, if there was also a decent function call interface.
Modern BSDs generally use sysctl, which although being better in theory, that you don't have the overhead of useless translating numbers back and forth from text and looking for space characters, it still has the problem that it's very dependent on subtle changes in the C data structures which can easily happen between version and architectures. But it also has the terrible drawback of not knowing how big the buffer should be and therefore having to be in an allocation fail loop, probably exactly when you don't want it to happen, when you system is overloaded with way too many processes. I really don't see why one couldn't pass a memory allocator function, which could be called in the same manner as a signal handler.
I don't know how windows stuff works inside, but to get process information you ask for a snapshot of the system from which you can return a set of handles to processes, which you can get information from. In other words, it allocates the appropriate things for you and has well defined set of information which you can query, all with a relatively simple function call interface from C. I wrote a 'ps' that works on linux/bsd/macos/windows, and even though I'm not at all fan of windows, the windows kernel does it better than all the unix kernels.
It's actually not that hard to make an acceptable C interface to to say process information, if you ignore the problems of data structure variance. But ignoring it is really the root of the issues, so it seems fairly pointless. sysctl sort of tries to have a metadata system, but it doesn't really address the data type problem well, and can end up using C structs from the kernel with same variance problems. For example task_struct in linux or struct proc on macos is kind of a big mess, but very important. You wouldn't want to restrict it from changing in any way, but you do want to get some of that data to users.
Making a good C metadata interface is complex, and although it's been done many times, it's quite tricky to do well, and you would really want a kernel interface to be done very well. I like to imagine that there could be something less bloated than gtk gobject, but more featurefull than sysctl. Unfortunately when I look at code involved I start feeling like C isn't really a good language for writing an operating system. But I still think that a well designed structured meta data system would be overall less overhead than /proc and could even achieve better speed and reliability.