The Evolution of File Descriptor Monitoring in Linux
Hajnoczi, Stefan
File descriptor monitoring is at the core of event-driven applications from graphical applications to web servers. Over the history of Linux, a number of system calls APIs have been introduced to improve upon the performance, features, and interface design. Developers may ask themselves which API they should use and how they differ. This talk covers select(2), poll(2), epoll(7), as well as the more recent Linux AIO and io_uring APIs. We will look at the classic scalability challenges with these APIs as well as the latest shared kernel memory ring and polling approaches. An understanding of the evolution of file descriptor monitoring in Linux exposes API design topics that have relevance even if you don't need to implement an event loop in your application.
 Hi, my name is Stefan Heinetzi and today we're going to talk about the evolution of file descriptor monitoring in Linux. So what is file descriptor monitoring? File descriptor monitoring APIs allow applications to find out which file descriptors are ready to perform I.O. So that could be something like a server that is handling a bunch of different connections and also has a listen socket. Well, it might want to know when a new client connects to its listen socket. It might also need to know when new data arrives on one of the existing established connections. In other cases, you might have, for example, a pipe which has a finite sized write buffer. And if the application fills up that write buffer, it can't write any more data to it until the other side of the pipe, the reader, has read some of that data. And so file descriptor monitoring can let the application know when there's more write buffer space available. In Linux, there are a number of APIs for file descriptor monitoring. These system calls have been added over the years and they have different characteristics. They have different API designs and they have different performance and scalability. So today, what we're going to do is we're going to have a look at these APIs in turn and then we're going to compare them. So applications still use all of these APIs and this is not some functionality that has been obsolete completely in the kernel. So it's still normal to see different applications using different APIs, but that makes it especially interesting to go and look at them and understand their differences so that we can choose which ones to use ourselves. Before we start looking at the actual system call API design and the performance, let's have a look at how file descriptor monitoring works inside the kernel. Inside the kernel, various file descriptor types are implemented. For example, device drivers might have some file types that they have. Of course, file systems also implement file types. And these file types have a pull function. This pull function returns the set of events that are currently available on that file descriptor. So it could be, for example, that the file descriptor is ready for reading. But this pull function also allows the caller to register themselves and receive a wake up when that file finally becomes ready for the events that it is looking for. The exception to this single API that exists inside the kernel is CIGIO. It has its own API. But for the most part, these very different system calls are actually implemented using this one API in the kernel. Now what are the set of events that the kernel knows about and the set of events that it will raise? Here is the table with the most important ones. The read and the write are the very commonly used ones that are used for finding out when a socket has more data to read or, for example, when a pipe can be written to. There are also events for closing file descriptors, in particular for finding out when the other side of a socket or a pipe has been closed. So there is a hang up, an E-PollHOP event, which notifies the application that the socket has been closed. That doesn't mean that the file descriptor is completely finished and no longer useful because there might still be data in the receive buffers that user space can still read before it itself decides to let go of that socket. There are also some file specific events. So this depends on the specific file type. And a driver, for example, might raise this event when something relevant to its file type happens. That's the E-PollPri flag. It's not used very often. There's also an error flag, of course, in case something goes wrong and the application needs to respond in order to handle this file descriptor that's no longer usable. There's some out of band events, which I haven't even shown here because they're quite rare. They're used for TCP connections, which have the concept of sending data outside of the normal stream. And another thing that's interesting to note is that when these file descriptor events occur, they occur at a point in time. By the time that user space gets around to actually, for example, reading from that file descriptor that had something available, it could be that the file descriptor no longer has data available, either because another thread or another process read from it, or maybe something else happened. So it's important for applications to be aware that in some cases maybe they'll receive an event, and when they actually try to respond to that event, things have already changed and moved on. The kernel has the O non-block open flag for files, and it's important to set this this way. If the application finds out the file is ready for reading, and it does the read, but there's actually no data there, then the kernel will return with E again and let the application know there was nothing. By default, file descriptors are not in non-blocking mode, instead the process would actually be put to sleep, so this would hang the application. So it's worth knowing this. Now before we look at the various APIs in detail, I want to still take a step back, and let's remind ourselves why is file descriptor monitoring used at all? Why do applications do this? Let's take an example, say we're implementing a text-based matrix chat client. We have two sources of activity here. The human who is interacting and entering chat messages that they want to send to the chat room on the keyboard, and the second source of activity is the matrix server, which is sending us the messages that remote users have posted to the chat room, and we need to display them. So we have two different things we need to do at the same time, two different IO activities, and one way of implementing this would be to spawn one thread for the terminal, for the TTY, and one thread for the matrix server socket, and those threads could then process any data that becomes available on those file descriptors. The thing with threads though is that you need some coordination for the life cycle of the thread to safely start it and stop it at the appropriate time, and in addition to that, if there are any shared resources in use, for example, the user interface, which has both updates from the keyboard when the user enters a message and updates from the server when new messages appear, we will need to protect that and implement some synchronization or something to make sure that the terminal, the TTY thread, and the matrix server socket thread don't interfere with each other. So this adds complexity. It would be nice if there was a way to avoid having to have this complexity that that multi-threading brings. The final thing to keep in mind with threads is that they're not free. They are resources and they have some amount of overhead. They have a cost associated with them. And this is particularly apparent when you have a server that has many, many thousands or tens of thousands of file descriptors, because each of those threads is going to have a call stack and it's also going to have some kernel resources associated with it. So is there another way, a more lightweight way, a way that doesn't require complex coordination? Yes, there is. One approach is using an event loop. So this is called an event-driven architecture. Instead of making every IOTask a separate thread, we can instead have an event loop and each activity, so for example the terminal, the TTY file descriptor, whenever it becomes ready, that's an event. We wait for the next event, we handle the current event, and then we go back into the loop and we just repeat doing this until the application stops. And in this event loop approach, file descriptor monitoring is what powers this next event function or this next event primitive. We need to have the ability to monitor a set of file descriptors and see which one of them is ready and then we'll let our application handle it. To become a bit more concrete as well, where is this used in the real world? Which applications use file descriptor monitoring? Well, pretty much all GUI applications, all graphical applications tend to do this because GTK, QT, and also other user interface frameworks, even on other platforms, tend to be based on event loops and they tend to monitor file descriptors. That tends to be what powers the core of user interfaces. But it's not just graphical applications. Servers like NGINX, the web server, is a well-known example for an application that uses an event-driven architecture and event loops. You might also hear about thread per core architectures, which are becoming popular for storage and network processing. And the idea there is that you start a thread for each CPU, but then on that CPU, you run an event loop in order to process work. And finally, you might also come across file descriptor monitoring when it's simply used in order to get around limitations of blocking APIs. And what I mean by that is that sometimes you want to read from a file or write from a file or perform some other blocking operation, an operation that can take a long time. And if those system calls do not have timeouts or cancellations, sometimes an approach that people take is they use a file descriptor monitoring API in order to get that functionality so that they can cancel our timeout. Okay. So we've covered the background for what is file descriptor monitoring, why do applications use it, and what are some of the real world examples. Now let's take a look at the select system call. The select system call is the first of the ones we're going to look at because it is the earliest one that's still widely used. It was introduced in 4.2 BSD, so before Linux. And the variant that I'm showing here on this slide is Pselect. This is a newer version of it. It's a POSIX system call, so it's available not just on Linux. And what this system call added on top of the original select is it has a nanosecond timeout and it also has a signal mask. The reason I'm mentioning these things is I'm always going to show you the most powerful and most recent variant of these system call families because they're useful, for example, if you need high resolution timers, you want to make sure to use something that has, say, more than just millisecond or even microsecond resolution. Or if you're using POSIX signals in your application, then being able to control the signal mask while you're in a blocking system call is important because you need to decide when to block and unblock certain signals. Okay, but let's get to the file descriptor monitoring part. So how does select work? The select system call takes up to three bitmaps, these FD sets. And user space will set a bit to one if it wants to monitor that file descriptor number. So for example, say we want to monitor file descriptor number four, then we would have to set the fifth bit in the bitmap to one to tell the kernel we want to monitor file descriptor number four because the bits, right, they're numbered zero, one, two, three, four, and then that's the one that we want to set to one. If we set it to zero, the kernel will not monitor it. And that's how you build these FD set bitmaps. When you call the system call, the kernel will then look at that bitmap, will monitor the file descriptor numbers that you requested. And when a file descriptor becomes ready or when there's a timeout, it will write out a new bitmap. It will overwrite your bitmap. And instead, you'll have a one if the file descriptor was actually ready, or you'll have a zero if the file descriptor is not ready. And the return value to the system call is just the total number of bits set. And so this is how we can monitor multiple file descriptors with one system call. That's the select system call. Now select has some well-known design quirks, some limitations that make programming with it a little limited in some cases. First of all, this bitmap representation of the file descriptor number space is not very efficient because if we have a single file descriptor we want to monitor, but it happens to have a high number, then we need to provide a long bitmap with zeros all the way up to the file descriptor that we want to monitor. And then when the kernel processes the system call, it's going to have to scan that bitmap to find R1. It's going to have to start from the beginning of the bitmap. And so this is just going to waste CPU. It's maybe not a very good representation to use when you have just a few file descriptors, especially if the numbers are high. Another quirk is that POSIX select has a constant called fdsetsize. And that is the maximum file descriptor count that you can have in the bitmap. So what this means is that on Linux with Glib C, 1,024 is the limit for select. If your application has a file descriptor number that's higher than that, for example, you opened the file and you got file descriptor number 2,000, you would just simply not be able to use the Glib C select function in order to monitor that because it won't fit in the bitmap. So that's a pretty severe limitation if you want to be able to process many file descriptors. So for something that needs to scale and have a lot of file descriptors, select is basically out of the question. Okay, another API design aspect that we're going to be looking at as we go through these different system call APIs is how does the application associate an object with that file descriptor? A file descriptor number by itself is not necessarily useful to a program. If your program is doing many things at the same time and then you find out, okay, file descriptor 13 is now ready for reading, you might not know what that means. Which object is associated with that file descriptor? Was it an HTTPS session that we had going? Was it a pipe we were using to communicate with another process? We need some way of being able to connect the file descriptor with an application object so we can then easily handle the event for that object. Select tends to not do so well here. Usually select is used in a hard coded way where you see actual code that literally says if a particular file descriptor, for example, in our matrix client, if the TTY file descriptor is set, then go and process the TTY. And that is fine when you have a fixed number of file descriptors that you know at compile time. It doesn't work so well if you have, say, a server that's going to have many sessions and the number of file descriptors is dynamic. Now we need to figure out some way. So an obvious way is to just create a hash table but that is going to be a little bit inconvenient. We'll have to set up an extra data structure and it's going to be a hash table to go from a file descriptor number to our application object. So it doesn't have a built in way of doing this. We're going to see later on how other APIs make this easier. Okay, so let's move on from select. Poll is a POSIX API so it's widely available and it makes some of these shortcomings of select go away because it chooses a different representation for the file descriptors. Instead of using this bitmap that we had with select, it uses an array of struct poll FDs and so now we're no longer having to use a bit for every possible file descriptor number. Instead we just use a poll FD for each file descriptor that we actually want to monitor. We don't have zeros anymore. We just have the poll FDs that we are interested in. So that's an interesting approach. It has an input event mask. That's the poll FD events field where the application sets the events it cares about. For example, poll in or poll hop and then it has an R events field where the kernel writes the actual result event mask, the actual events that are ready. So that could be zero if there's no activity on this file descriptor or it could be a non-zero value if one of the bits that we were looking for is ready. It returns the event count, the total number of file descriptors that are actually available. So this is the poll API. Let's look at how it compares to select. So first of all, we're no longer limited to 1024 file descriptors which is a very important property if we want to be able to handle many, many connections at the same time. And the reason for not having this limitation is we're no longer using this bitmap and we no longer have that fixed FD set size. Okay. And in addition to that, we're now using a dense file descriptor list. We don't have all those zeros. So that's another improvement. Why is an improvement? It's an improvement because it means that the kernel, when processing the system call, no longer needs to scan all those zeros and skip through all of them. Instead, it just gets a useful list of the actual FDs that we want to monitor. Okay. So some CPU cycles are saved. Another interesting design decision is that there's that R events field. The kernel does not update our input event mask when we make the system call. Why does that matter? Why is that important? Well, it means you can set up the poll FD array once and then your application can loop and just keep calling poll as long as your set of file descriptors doesn't change. It can just keep calling poll and doesn't need to rebuild that poll FDs array every time it calls poll, which is a nice property. In select, we didn't have that because the kernel overwrote the FD sets that we passed in those bitmaps. We have to recreate the bitmaps every time from scratch. So this is an improvement that poll makes. That's nice. It saves CPU cycles. Finally, application object lookup is now simpler. We can just have a parallel array next to the poll FDs. We just have another array and each entry corresponds to the same index in the FDs array and we just store the object, the pointer to the object. And that way we can efficiently and easily look up the application object associated with this FD. So that's an improvement. The final thing I wanted to show in this slide is a common optimization that programs make. Since the system call told us how many FDs were ready, we can short circuit this for loop. We don't have to scan every poll FDs struct. Then we were monitoring a thousand poll FDs and only one of them was ready. As soon as we find that one, we will leave this for loop and we'll stop scanning. So that's a nice quality to have. We can save some CPU cycles by doing that. Great. So we've looked at select and we've looked at poll. Those are the most portable, they're POSIX, they're widely used, but they're relatively old and they do have some known scalability issues. So now let's move into the 21st century. So E-Poll was added to Linux in the 2000s and it changed the API. It made quite a big, it was quite a big departure from poll and select, which we're about to see. So E-Poll has an E-Poll control system call that we can invoke every time we want to add another or remove a file descriptor from the set of file descriptors that we're monitoring. And in fact, E-Poll itself is represented as a file. So you have an E-Poll file descriptor that you create with the E-Poll create one system call. And this allows you to actually have multiple sets of E-Poll in your application at the same time. If maybe you want to either have nested event loops or you just have different event loops and you want to keep them separate, you can do that. It's not global, it's not per process. Instead it's actually, you can have many instances and each one of them is one E-Poll file descriptor, which is an interesting aspect and we'll see more of that later. So how does it work? Well, we tell E-Poll control which file descriptor we want to monitor and we pass it an event mask similar to how we did it with the poll system call. We also have a data field where we can store an application specific value. We're going to get that value back when this file descriptor becomes ready. And so you can already imagine what that's going to do. It's going to make the application object look up even easier because the kernel will tell us which application object we wanted if we decide to store, for example, the pointer to the object in this data field. So that's something that's coming. All right, so we have been able to add file descriptors for monitoring, but how do we actually get events back? There is a system call called E-Poll P-weight. Here I've shown you the new Linux 5.11 version of the system call. This variant is called E-Poll P-weight 2 and the reason I wanted to show it to you is because it now finally has nanosecond timer resolution, which is excellent for applications that need high resolution timers. That was one of the few big limitations of E-Poll for a long time and now it's been solved. So that's awesome in the next 5.11. Okay, so when we call the system call, we give it an array of E-Poll events and we tell it how many events there are and the kernel will then go and collect the readiness information from the file descriptors and write them into this array and return the number of ready FDs, the number of events that it filled out. What's interesting here and what's different from poll is that we could be monitoring a thousand file descriptors and yet we can call this system call with just say 10 event array elements that the kernel will fill in. And the kernel is prepared to handle that. That's perfectly fine. And it makes a lot of sense because a lot of time your application will only ever have one or two or a few files that are ready at a given time in the event loop. And so it would have been wasteful to have to allocate, if we're monitoring a thousand file descriptors, it would be wasteful to allocate a thousand E-Poll events just in case all of them happen to be ready at the same time. So this is a bit of a gives you some flexibility, allows you to minimize resources if you want. And the kernel also has a built-in algorithm to make sure that if you do have a thousand file descriptors and you only read out the first 10 events, when you call it again, it remembers which ones you've already processed. And even if those files do become ready again, say even more data has arrived with the socket, it won't return them yet. It will make sure that you receive all the other pending events first. So this prevents starvation because imagine you had a loop and there was a lot of activity on the file descriptors and you were only ever harvesting a subset of them, then some of the high numbered file descriptors at the end of the array would just never be processed. So this is a useful feature to have. But that's not all. E-Poll has quite a few interesting things. So E-Poll has an edge triggered mode. If your application decides not to actually do something that will change that readiness state, so if your socket was readable, but then you decide you don't actually want to read it yet and you still want to call it E-Poll wait again, then you have a problem because that file is still readable. So you'll get an event back again saying, hey, the file is readable and you may want to defer that. So one efficient way of doing that is to use the edge triggered mode. What this does is it means that E-Poll will return events when they transition state, so going from not ready to ready instead of returning the level of the event, whether it's ready or not. That way you won't be bothered with lots of returns repeatedly for events that you haven't handled yet. There's also a one shot mode that you can enable. What this does is say you want to respond to an event on a file descriptor, but then you're going to wait for a while after you've handled that before you start monitoring again. With E-Poll system call design, you would actually have to use E-Poll control one more time in order to disable that file descriptor temporarily. Now with the one shot mode, you can get that for free because you're telling the kernel, hey, when this fires, when it triggers, please just disable it. And I'll bring it back later on when I'm ready. So it saves some of the system calls. It's a bit more efficient. The final mode that I really wanted to talk to you about is the E-Poll exclusive mode, which optimizes the way that multiple waiters who are all waiting for a file descriptor to become ready are handled. Let's look at that in detail. This is called the Thundering Heard problem. It's a well-known problem in computer science and in operating systems. The problem is if you have multiple processes or threads that are all waiting for work and the work becomes available, what do you do? If you wake all of them up and say, hey, there's work available, please go and grab it, then what will happen is that only one of them will be able to get the new work and the other ones, when they try to grab it, will find that there's no work available because there was only one item. And so that's very inefficient. On the other hand, you need to do this approach for load balancing because otherwise, if you decide who to give it to, if that worker is busy and isn't ready yet for the next piece of work, then your system will slow down and you'll have to wait for it. So this is called the Thundering Heard problem. Whenever we wake up, all of the workers wake up. They try to grab work. Only one of them makes it. Everyone else is just wasting CPU trying to grab work. So what the exclusive flag does is it tells the kernel that it's okay to wake up just a single worker. And that way, you avoid all that extra overhead. Let's look at that. So I ran a benchmark with E-Poll, exclusive on and off. And what we're seeing here is we're seeing the number of messages that were received and sent. And this is divided by the amount of CPU time that was spent. And so we really see the CPU efficiency here. We see how many messages were we able to process per unit of CPU time. As the number of threads goes up on the x-axis, you can see that without the E-Poll exclusive flag, the scalability is poor, the performance drops as we add more threads because they're all going to wake up, try to fetch some work, and it turns out there's nothing to do. And they go back to sleep again and we've wasted CPU. That's why the efficiency is so poor. And we can see how well the E-Poll exclusive flag works when we have a lot of threads. Great. So that was the Thundering Heard. Another big change, a big departure that E-Poll made in its API design is it is a stateful API. It is not a stateless API. Select and pull are stateless. Each time we call them, the kernel starts from scratch. It doesn't know anything about the file descriptors that we're going to be monitoring. And when we're done, it doesn't care anymore. It forgets about it. And we start from scratch every time. So each time the kernel is going to have to set up the monitoring on the whole set of file descriptors only to collect an event for maybe one or two that are actually ready now and return that back. So that's wasteful. And what E-Poll does is because we've created this E-Poll file descriptor using E-Poll create1, it can actually store which file descriptors are being monitored. And when you make the E-Poll P-weight call, what it's doing is it's not setting up the monitoring. That's already been set up. At that point, it's just collecting the events that have occurred. So that's much, much more efficient. So now the kernel doesn't need to loop over all your FDs, set up the monitoring, and so on. Now it just needs to look at which events have already occurred. So this is an improvement that E-Poll makes just in terms of the fundamental design. And the trick here is that it's a stateful API. Now taking this a bit further, how does the efficiency of this look? This big O notation here I'm using is just to show you, does user space or does the kernel have to loop over the data that we're processing many times? And in the case of select, the kernel actually has to loop over those bitmaps all the way up to the maximum file descriptor number. So that's very inefficient. The pathological case there is say we have file descriptor 1000 and it's the only FD we're monitoring. We still need to create a big bitmap with lots and lots of zeros all the way up to the thousands one. And so that way CPU cycles. Now poll does better. The poll system call does better. It only loops over the actual total number of FDs that we're monitoring. So it doesn't care if the file descriptor number is 1000 or if it's one, the efficiency just hasn't changed there, but it still needs to loop over all of them. So if we want to monitor 1000 FDs, then each poll call is going to have to process all of them. Finally, let's get back to E-Poll. E-Poll is an improvement here. E-Poll only needs to process those that are actually ready. And so you can see that this is a fundamental improvement in terms of efficiency. We only need to see the FDs that are ready. And in user space, the E-Poll events that are returned from poll weight are really just the FDs that we're about to process. So this is great. But that was the 2000s. That was E-Poll. Things have moved on since then. So in the past few years, Linux has gotten the IOU ring system calls and a lot of system calls have now been added to IOU ring so that it can do a lot of functionality asynchronously, which means that there is a submission queue where user space can add requests. And there is a completion queue where user space gets the finished request that the kernel has finished processing. And it allows user space to queue up one or more requests to the kernel. The kernel will then handle them, and the results will be written back to the completion queue when they're done. The system call here is IOU ring enter. And we basically just tell the kernel how many new requests are in the submission queue that we want to process. And we tell it how many requests we want to wait for. Do we want to wait for one request? That could be the next request, whatever that is. Or do you want to wait for 10 requests? Or maybe for no request if we don't actually want to wait at all. So that's how the system call works. There's no timeout here, which you might have noticed compared to all of our other system calls, but we're going to see how that works in a second. OK, so now I mentioned that the submission queue takes these requests. Well, there's lots of request types. Here are the operations that are relevant to file descriptor monitoring. And there are many more that you can find in the documentation that aren't going to be relevant for file descriptor monitoring. Poll add allows us to do a one-shot file descriptor monitoring operation. We can add an FD. We can tell it which events we care about. And this request will complete when the file descriptor has some activity. If we change our mind, if we decide, OK, we don't want to monitor that file descriptor anymore, then we can use the poll remove request type to cancel it. An interesting one, an interesting request type, is the ePollControlRequestType. What this allows us to do is it allows us to invoke the ePollControlSystemCall functionality using IOU ring. So why would we want to do that? We can do it in a way that avoids system calls. So the bottleneck with the ePollControlDesign is that that system call only operates on a single file descriptor. It adds a single file descriptor. It removes a file descriptor or it modifies an existing one. But you can't use it to, say, monitor 1,000 file descriptors in a single system call. And if you have a lot of file descriptors that you're changing frequently, then, of course, that system call overhead is going to be relevant. When using IOU ring, you can actually queue up all of these requests and then do a single IOU ring enter system call to process them. See the trick with IOU ring is that the submission queue and the completion queue are M mapped into user space memory. So the user space processes memory space has the submission completion queues. And that's why we can access them and add things and process completions without doing system calls. So that's an interesting use here. And if you remember back when I said ePoll can nest because that file descriptor itself supports polling, we could use that ePoll file descriptor within IOU ring. For example, we could use poll add on the ePoll file descriptor. The final thing I wanted to mention is timeouts since the IOU ring enter system call doesn't have a timeout argument, the way to do it is to add a timeout request to the submission queue. And that way, we'll be able to stop waiting if there is no activity when our timeout expires. OK, so that was a lot. It's a very different model. And here is an example using the libUring user space library. What's happening here is that we are preparing one file descriptor for read monitoring. We're using poll in flag. So we use IOU ring getSQE to get the next available submission queue entry. We then set the file descriptor number on it and the poll in flag. And then we do the IOU ring SQE set data call. And what that does is it associates, it stores our object pointer, our application object, or any 64-bit value that we want. It stores that with the SQE so that when this completes, we'll get that value back and we can look up our application object. OK, great. So we've added the request, but now we're going to tell the kernel about it and we're going to wait for the completion. And we can do that using the single IOU ring submit and wait library call. And when it returns, we know something has happened. And then we can just loop over the completion queue with the IOU ring for each CQE loop. And then our application can handle the completion result. And that user data field that you see there is going to be that object value that we stashed in the submission queue. And then finally, we need to call IOU ring CQE advanced just to tell the kernel that we have now processed those completion queue entries and they can be reused. So that's programming with IOU ring. What are the characteristics of IOU ring compared to EpoL? So first of all, we talked about how EpoL control only handles one FD at a time. Whereas with IOU ring, we can handle many FDs at a time. We can add many FDs, we can remove many FDs in a single system call. So that's an advantage right there. The system call also combines both submission and completion into a single system call. So it further minimizes it. Whereas with EpoL, we had to do EpoL control and EpoL wait. With IOU ring, we only need to do IOU ring enter. That's the only system call. So again, this is a little performance boost if this is in the inner loop of your application or trying to minimize CPU cycles and minimize latency. Another thing that's interesting about IOU ring is that it supports busy waiting, both in the kernel and in user space. And what that means is that since that completion queue is M-mapped into user space, our user space process can actually just peek at the completion queue memory and can see when requests become ready. It doesn't need to make a system call in order to ask the kernel if requests have completed. If your application is either CPU intensive or if it already has a busy wait loop, you can integrate into that. And you can easily and cheaply check any IOU ring events, which means you can do file descriptor monitoring from within a busy wait loop in your application. On the kernel side, it's also possible to do busy waiting because IOU ring supports kernel polling threads, but we're not going to get too into that. There are also other features that IOU ring has. I think we've only really scratched the surface here. It's very powerful. It has a concept of linked requests. It has some optimizations for pre-registering file descriptors and buffers so that the kernel doesn't need to keep looking them up. So that saves some CPU cycles. And there's a lot more. So it's a really interesting API. Now I just mentioned busy waiting. And so I want to go back and mention that if you're using select poll and ePoll, they also have some busy waiting support. It's limited, but in Linux, you can use the net core busy poll at sysctl in order to set the number of microseconds that these system calls should busy wait instead of idling the CPU. Now, this is used in applications where you have dedicated CPU resources and you want to minimize latency, idling the CPU, putting it into a low power state, and then when a packet comes in having to wake it up again and having to schedule and get back to what we were doing adds latency. And so some applications can use this with select poll and ePoll. So I just wanted to mention that since we were talking about busy waiting for IOU ring. By the way, this is only available for network sockets in Linux. So it's a network subsystem thing. And if you're using other types of file descriptors, then it won't work with them. Okay, so we've looked at the APIs, but we're not really done yet because we talked about threads and some of the pros and cons of threads. Then we looked at file descriptor monitoring. There's actually another approach that we can take aside from threads or file descriptor monitoring. With IOU ring, we could actually just do the IOU operations asynchronously. So we could just tell the kernel using IOU ring to do a read. And it would complete the request when that read is finished. And if the socket is not ready or the pipe is not ready, then that request would just be waiting. But in the meantime, our user space thread could make progress. So we can solve the same problem that we had with our matrix chat client of monitoring and doing stuff in multiple FDs. We can actually solve that using asynchronous IOU instead. Why might that be an interesting idea? Well, because this way, we don't need to attempt to read, find out the socket has no data available, then add it to the set of FDs to monitor, go into the kernel, wait to be woken up when something happens, and then try reading again. We can eliminate all of that kind of housekeeping work, all of that back and forth, and just do a single asynchronous read. So it's potentially an interesting approach. One of the issues with it, though, is that it's something more for new applications. It's hard to retrofit this into existing applications, especially if you remember that I mentioned that GTK and QT and so on are based on file descriptor monitoring. Using something like this universally would mean basically breaking the APIs and changing the way that applications use file descriptors. They would have to start using asynchronous operations instead of monitoring file descriptors. And so this is kind of hard to do with existing code. I've written a blog post about it that goes into more details about the performance advantages that we could get by doing this. And if you're writing new code, you might consider trying this out and seeing how it works. Okay. We should just briefly mention the other APIs that we don't have time to cover in detail. First of all, there is CIGIO, which is an old mechanism, and it's a signal-based mechanism where you can mark a file descriptor as, please send me CIGIO signals when the file descriptor is ready. But it's rarely used, probably because programming with signals is tricky. It's also not a very expressive interface. It's hard to use, and therefore I've never seen it used. There's Linux AIO, which is similar to IOU ring, but is a precursor to it. It has a subset of the functionality, and so that's why I didn't go into that one, but that's available too. Okay. And then finally, let's move on to some performance data and some benchmarks. I have posted a code for a benchmark. What it does is it receives data on a random file descriptor and then just sends the data back. So, it doesn't change the benchmark. It doesn't change the set of file descriptors that are monitored during the benchmark. It only sets it up once. So this may not be representative of your application, but it does show the raw performance of just the file descriptor monitoring itself, just the waiting. Okay. So let's look at the scalability of all the APIs we've talked about. We see they fall into three classes, right? These curves fall into three groups. The bottom group is select and pull, which isn't a big surprise because we talked a lot about their limitations and how they're inefficient and how they don't scale. So we see here that they really don't do well compared to the others. Although note that the Y axis on this graph doesn't start at zero. So it's not as bad as it looks on the graph, but I wanted to zoom in so we can see these details here. In the middle, we have threads. I wanted to make sure we compare this with an application that just has one thread per IOTask. So we don't lose sight of what programming with threads is like. And you can see here that the performance is just always lower than the E-Poll and IOUring performance at the top when we use threads. That's the blue line in the middle. What's interesting is that IOUring using AIO, so not doing file descriptor monitoring, but doing asynchronous reads and writes, is similar to threads in this benchmark. Now I have to add a caveat. I think that there's a lot more that can be done, whether that's tweaking the benchmark itself to make use of IOUring more efficiently. It's not using busy waiting or any stuff like that. Or extending the IOUring implementation in the kernel to make it more favorable for this type of usage. So I think it could go a lot higher, but that's where it is. And it kind of makes sense because IOUring internally does have a thread pool in the kernel. So eventually it does end up in a thread. And so it kind of makes sense that it's similar to using threads. Okay. And finally at the top, the fastest ones, very similar performance was IOUring doing file descriptor monitoring and E-Poll. So they're both excellent. And you can see actually that they scale very well with the number of file descriptors. They didn't, there wasn't a steep curve. They were very flat. So that's nice to see. And IOUring is the one that is a little bit more flexible, as I mentioned. It has all these other features that you might find useful in your application, whereas E-Poll is just dedicated to file descriptor monitoring. That's the difference between those approaches. I just want to also show the CPU efficiency of this. So again, here we're dividing by the unit of CPU time consumed in order to see a slightly different picture here. We're seeing that threads actually consumes a lot of CPU per request compared to the event-driven approaches, which makes some sense because when we're switching threads, we have higher overhead. So the scheduler, maybe the cache and so on, and the call stack all need to be changed and cleaned out, especially with security mitigations and so on. So yeah. Finally, summary. On this slide, I just wanted to show you which of these APIs are the portable ones. I think we saw with performance that really if you are able to use an event loop library that supports a Linux specific API or you have the time to implement it yourself, that's worth it for performance. Thundering Heard is solved by E-Poll and IOU ring. So if you have those concerns, it's best to use those APIs. And then finally, E-Poll is one that's popular today in high performance applications. I think that IOU ring might be more popular in the future as people use some of the other functionality together with file descriptor monitoring. Okay. Thank you very much. We can move on to questions.
 Hi, my name is Stefan Heinetzi and today we're going to talk about the evolution of file  descriptor monitoring in Linux.  So what is file descriptor monitoring?  File descriptor monitoring APIs allow applications to find out which file descriptors are ready  to perform I.O.  So that could be something like a server that is handling a bunch of different connections  and also has a listen socket.  Well, it might want to know when a new client connects to its listen socket.  It might also need to know when new data arrives on one of the existing established connections.  In other cases, you might have, for example, a pipe which has a finite sized write buffer.  And if the application fills up that write buffer, it can't write any more data to it  until the other side of the pipe, the reader, has read some of that data.  And so file descriptor monitoring can let the application know when there's more write  buffer space available.  In Linux, there are a number of APIs for file descriptor monitoring.  These system calls have been added over the years and they have different characteristics.  They have different API designs and they have different performance and scalability.  So today, what we're going to do is we're going to have a look at these APIs in turn  and then we're going to compare them.  So applications still use all of these APIs and this is not some functionality that has  been obsolete completely in the kernel.  So it's still normal to see different applications using different APIs, but that makes it especially  interesting to go and look at them and understand their differences so that we can choose which  ones to use ourselves.  Before we start looking at the actual system call API design and the performance, let's  have a look at how file descriptor monitoring works inside the kernel.  Inside the kernel, various file descriptor types are implemented.  For example, device drivers might have some file types that they have.  Of course, file systems also implement file types.  And these file types have a pull function.  This pull function returns the set of events that are currently available on that file  descriptor.  So it could be, for example, that the file descriptor is ready for reading.  But this pull function also allows the caller to register themselves and receive a wake  up when that file finally becomes ready for the events that it is looking for.  The exception to this single API that exists inside the kernel is CIGIO.  It has its own API.  But for the most part, these very different system calls are actually implemented using  this one API in the kernel.  Now what are the set of events that the kernel knows about and the set of events that it  will raise?  Here is the table with the most important ones.  The read and the write are the very commonly used ones that are used for finding out when  a socket has more data to read or, for example, when a pipe can be written to.  There are also events for closing file descriptors, in particular for finding out when the other  side of a socket or a pipe has been closed.  So there is a hang up, an E-PollHOP event, which notifies the application that the socket  has been closed.  That doesn't mean that the file descriptor is completely finished and no longer useful  because there might still be data in the receive buffers that user space can still read before  it itself decides to let go of that socket.  There are also some file specific events.  So this depends on the specific file type.  And a driver, for example, might raise this event when something relevant to its file  type happens.  That's the E-PollPri flag.  It's not used very often.  There's also an error flag, of course, in case something goes wrong and the application  needs to respond in order to handle this file descriptor that's no longer usable.  There's some out of band events, which I haven't even shown here because they're quite rare.  They're used for TCP connections, which have the concept of sending data outside of the  normal stream.  And another thing that's interesting to note is that when these file descriptor events  occur, they occur at a point in time.  By the time that user space gets around to actually, for example, reading from that file  descriptor that had something available, it could be that the file descriptor no longer  has data available, either because another thread or another process read from it, or  maybe something else happened.  So it's important for applications to be aware that in some cases maybe they'll receive  an event, and when they actually try to respond to that event, things have already changed  and moved on.  The kernel has the O non-block open flag for files, and it's important to set this this  way.  If the application finds out the file is ready for reading, and it does the read, but there's  actually no data there, then the kernel will return with E again and let the application  know there was nothing.  By default, file descriptors are not in non-blocking mode, instead the process would actually be  put to sleep, so this would hang the application.  So it's worth knowing this.  Now before we look at the various APIs in detail, I want to still take a step back, and let's  remind ourselves why is file descriptor monitoring used at all?  Why do applications do this?  Let's take an example, say we're implementing a text-based matrix chat client.  We have two sources of activity here.  The human who is interacting and entering chat messages that they want to send to the  chat room on the keyboard, and the second source of activity is the matrix server, which is  sending us the messages that remote users have posted to the chat room, and we need  to display them.  So we have two different things we need to do at the same time, two different IO activities,  and one way of implementing this would be to spawn one thread for the terminal, for the  TTY, and one thread for the matrix server socket, and those threads could then process  any data that becomes available on those file descriptors.  The thing with threads though is that you need some coordination for the life cycle  of the thread to safely start it and stop it at the appropriate time, and in addition  to that, if there are any shared resources in use, for example, the user interface, which  has both updates from the keyboard when the user enters a message and updates from the  server when new messages appear, we will need to protect that and implement some synchronization  or something to make sure that the terminal, the TTY thread, and the matrix server socket  thread don't interfere with each other.  So this adds complexity.  It would be nice if there was a way to avoid having to have this complexity that that  multi-threading brings.  The final thing to keep in mind with threads is that they're not free.  They are resources and they have some amount of overhead.  They have a cost associated with them.  And this is particularly apparent when you have a server that has many, many thousands  or tens of thousands of file descriptors, because each of those threads is going to  have a call stack and it's also going to have some kernel resources associated with  it.  So is there another way, a more lightweight way, a way that doesn't require complex coordination?  Yes, there is.  One approach is using an event loop.  So this is called an event-driven architecture.  Instead of making every IOTask a separate thread, we can instead have an event loop and each  activity, so for example the terminal, the TTY file descriptor, whenever it becomes ready,  that's an event.  We wait for the next event, we handle the current event, and then we go back into the  loop and we just repeat doing this until the application stops.  And in this event loop approach, file descriptor monitoring is what powers this next event function  or this next event primitive.  We need to have the ability to monitor a set of file descriptors and see which one of them  is ready and then we'll let our application handle it.  To become a bit more concrete as well, where is this used in the real world?  Which applications use file descriptor monitoring?  Well, pretty much all GUI applications, all graphical applications tend to do this because  GTK, QT, and also other user interface frameworks, even on other platforms, tend to be based  on event loops and they tend to monitor file descriptors.  That tends to be what powers the core of user interfaces.  But it's not just graphical applications.  Servers like NGINX, the web server, is a well-known example for an application that uses an event-driven  architecture and event loops.  You might also hear about thread per core architectures, which are becoming popular  for storage and network processing.  And the idea there is that you start a thread for each CPU, but then on that CPU, you run  an event loop in order to process work.  And finally, you might also come across file descriptor monitoring when it's simply used  in order to get around limitations of blocking APIs.  And what I mean by that is that sometimes you want to read from a file or write from  a file or perform some other blocking operation, an operation that can take a long time.  And if those system calls do not have timeouts or cancellations, sometimes an approach that  people take is they use a file descriptor monitoring API in order to get that functionality  so that they can cancel our timeout.  Okay.  So we've covered the background for what is file descriptor monitoring, why do applications  use it, and what are some of the real world examples.  Now let's take a look at the select system call.  The select system call is the first of the ones we're going to look at because it is  the earliest one that's still widely used.  It was introduced in 4.2 BSD, so before Linux.  And the variant that I'm showing here on this slide is Pselect.  This is a newer version of it.  It's a POSIX system call, so it's available not just on Linux.  And what this system call added on top of the original select is it has a nanosecond  timeout and it also has a signal mask.  The reason I'm mentioning these things is I'm always going to show you the most powerful  and most recent variant of these system call families because they're useful, for example,  if you need high resolution timers, you want to make sure to use something that has, say,  more than just millisecond or even microsecond resolution.  Or if you're using POSIX signals in your application, then being able to control the  signal mask while you're in a blocking system call is important because you need to decide  when to block and unblock certain signals.  Okay, but let's get to the file descriptor monitoring part.  So how does select work?  The select system call takes up to three bitmaps, these FD sets.  And user space will set a bit to one if it wants to monitor that file descriptor number.  So for example, say we want to monitor file descriptor number four, then we would have  to set the fifth bit in the bitmap to one to tell the kernel we want to monitor file  descriptor number four because the bits, right, they're numbered zero, one, two, three, four,  and then that's the one that we want to set to one.  If we set it to zero, the kernel will not monitor it.  And that's how you build these FD set bitmaps.  When you call the system call, the kernel will then look at that bitmap, will monitor  the file descriptor numbers that you requested.  And when a file descriptor becomes ready or when there's a timeout, it will write out  a new bitmap.  It will overwrite your bitmap.  And instead, you'll have a one if the file descriptor was actually ready, or you'll have  a zero if the file descriptor is not ready.  And the return value to the system call is just the total number of bits set.  And so this is how we can monitor multiple file descriptors with one system call.  That's the select system call.  Now select has some well-known design quirks, some limitations that make programming with  it a little limited in some cases.  First of all, this bitmap representation of the file descriptor number space is not very  efficient because if we have a single file descriptor we want to monitor, but it happens  to have a high number, then we need to provide a long bitmap with zeros all the way up to  the file descriptor that we want to monitor.  And then when the kernel processes the system call, it's going to have to scan that bitmap  to find R1.  It's going to have to start from the beginning of the bitmap.  And so this is just going to waste CPU.  It's maybe not a very good representation to use when you have just a few file descriptors,  especially if the numbers are high.  Another quirk is that POSIX select has a constant called fdsetsize.  And that is the maximum file descriptor count that you can have in the bitmap.  So what this means is that on Linux with Glib C, 1,024 is the limit for select.  If your application has a file descriptor number that's higher than that, for example,  you opened the file and you got file descriptor number 2,000, you would just simply not be  able to use the Glib C select function in order to monitor that because it won't fit  in the bitmap.  So that's a pretty severe limitation if you want to be able to process many file descriptors.  So for something that needs to scale and have a lot of file descriptors, select is basically  out of the question.  Okay, another API design aspect that we're going to be looking at as we go through these  different system call APIs is how does the application associate an object with that  file descriptor?  A file descriptor number by itself is not necessarily useful to a program.  If your program is doing many things at the same time and then you find out, okay, file  descriptor 13 is now ready for reading, you might not know what that means.  Which object is associated with that file descriptor?  Was it an HTTPS session that we had going?  Was it a pipe we were using to communicate with another process?  We need some way of being able to connect the file descriptor with an application object  so we can then easily handle the event for that object.  Select tends to not do so well here.  Usually select is used in a hard coded way where you see actual code that literally says  if a particular file descriptor, for example, in our matrix client, if the TTY file descriptor  is set, then go and process the TTY.  And that is fine when you have a fixed number of file descriptors that you know at compile  time.  It doesn't work so well if you have, say, a server that's going to have many sessions  and the number of file descriptors is dynamic.  Now we need to figure out some way.  So an obvious way is to just create a hash table but that is going to be a little bit  inconvenient.  We'll have to set up an extra data structure and it's going to be a hash table to go from  a file descriptor number to our application object.  So it doesn't have a built in way of doing this.  We're going to see later on how other APIs make this easier.  Okay, so let's move on from select.  Poll is a POSIX API so it's widely available and it makes some of these shortcomings of  select go away because it chooses a different representation for the file descriptors.  Instead of using this bitmap that we had with select, it uses an array of struct poll  FDs and so now we're no longer having to use a bit for every possible file descriptor number.  Instead we just use a poll FD for each file descriptor that we actually want to monitor.  We don't have zeros anymore.  We just have the poll FDs that we are interested in.  So that's an interesting approach.  It has an input event mask.  That's the poll FD events field where the application sets the events it cares about.  For example, poll in or poll hop and then it has an R events field where the kernel  writes the actual result event mask, the actual events that are ready.  So that could be zero if there's no activity on this file descriptor or it could be a non-zero  value if one of the bits that we were looking for is ready.  It returns the event count, the total number of file descriptors that are actually available.  So this is the poll API.  Let's look at how it compares to select.  So first of all, we're no longer limited to 1024 file descriptors which is a very important  property if we want to be able to handle many, many connections at the same time.  And the reason for not having this limitation is we're no longer using this bitmap and we  no longer have that fixed FD set size.  Okay.  And in addition to that, we're now using a dense file descriptor list.  We don't have all those zeros.  So that's another improvement.  Why is an improvement?  It's an improvement because it means that the kernel, when processing the system call,  no longer needs to scan all those zeros and skip through all of them.  Instead, it just gets a useful list of the actual FDs that we want to monitor.  Okay.  So some CPU cycles are saved.  Another interesting design decision is that there's that R events field.  The kernel does not update our input event mask when we make the system call.  Why does that matter?  Why is that important?  Well, it means you can set up the poll FD array once and then your application can loop and  just keep calling poll as long as your set of file descriptors doesn't change.  It can just keep calling poll and doesn't need to rebuild that poll FDs array every time  it calls poll, which is a nice property.  In select, we didn't have that because the kernel overwrote the FD sets that we passed  in those bitmaps.  We have to recreate the bitmaps every time from scratch.  So this is an improvement that poll makes.  That's nice.  It saves CPU cycles.  Finally, application object lookup is now simpler.  We can just have a parallel array next to the poll FDs.  We just have another array and each entry corresponds to the same index in the FDs array  and we just store the object, the pointer to the object.  And that way we can efficiently and easily look up the application object associated  with this FD.  So that's an improvement.  The final thing I wanted to show in this slide is a common optimization that programs  make.  Since the system call told us how many FDs were ready, we can short circuit this for  loop.  We don't have to scan every poll FDs struct.  Then we were monitoring a thousand poll FDs and only one of them was ready.  As soon as we find that one, we will leave this for loop and we'll stop scanning.  So that's a nice quality to have.  We can save some CPU cycles by doing that.  Great.  So we've looked at select and we've looked at poll.  Those are the most portable, they're POSIX, they're widely used, but they're relatively  old and they do have some known scalability issues.  So now let's move into the 21st century.  So E-Poll was added to Linux in the 2000s and it changed the API.  It made quite a big, it was quite a big departure from poll and select, which we're about to  see.  So E-Poll has an E-Poll control system call that we can invoke every time we want to add  another or remove a file descriptor from the set of file descriptors that we're monitoring.  And in fact, E-Poll itself is represented as a file.  So you have an E-Poll file descriptor that you create with the E-Poll create one system  call.  And this allows you to actually have multiple sets of E-Poll in your application at the  same time.  If maybe you want to either have nested event loops or you just have different event loops  and you want to keep them separate, you can do that.  It's not global, it's not per process.  Instead it's actually, you can have many instances and each one of them is one E-Poll file descriptor,  which is an interesting aspect and we'll see more of that later.  So how does it work?  Well, we tell E-Poll control which file descriptor we want to monitor and we pass it an event  mask similar to how we did it with the poll system call.  We also have a data field where we can store an application specific value.  We're going to get that value back when this file descriptor becomes ready.  And so you can already imagine what that's going to do.  It's going to make the application object look up even easier because the kernel will  tell us which application object we wanted if we decide to store, for example, the pointer  to the object in this data field.  So that's something that's coming.  All right, so we have been able to add file descriptors for monitoring, but how do we actually  get events back?  There is a system call called E-Poll P-weight.  Here I've shown you the new Linux 5.11 version of the system call.  This variant is called E-Poll P-weight 2 and the reason I wanted to show it to you is because  it now finally has nanosecond timer resolution, which is excellent for applications that need  high resolution timers.  That was one of the few big limitations of E-Poll for a long time and now it's been solved.  So that's awesome in the next 5.11.  Okay, so when we call the system call, we give it an array of E-Poll events and we tell it  how many events there are and the kernel will then go and collect the readiness information  from the file descriptors and write them into this array and return the number of ready  FDs, the number of events that it filled out.  What's interesting here and what's different from poll is that we could be monitoring a  thousand file descriptors and yet we can call this system call with just say 10 event array  elements that the kernel will fill in.  And the kernel is prepared to handle that.  That's perfectly fine.  And it makes a lot of sense because a lot of time your application will only ever have  one or two or a few files that are ready at a given time in the event loop.  And so it would have been wasteful to have to allocate, if we're monitoring a thousand  file descriptors, it would be wasteful to allocate a thousand E-Poll events just in  case all of them happen to be ready at the same time.  So this is a bit of a gives you some flexibility, allows you to minimize resources if you want.  And the kernel also has a built-in algorithm to make sure that if you do have a thousand  file descriptors and you only read out the first 10 events, when you call it again, it  remembers which ones you've already processed.  And even if those files do become ready again, say even more data has arrived with the socket,  it won't return them yet.  It will make sure that you receive all the other pending events first.  So this prevents starvation because imagine you had a loop and there was a lot of activity  on the file descriptors and you were only ever harvesting a subset of them, then some of  the high numbered file descriptors at the end of the array would just never be processed.  So this is a useful feature to have.  But that's not all.  E-Poll has quite a few interesting things.  So E-Poll has an edge triggered mode.  If your application decides not to actually do something that will change that readiness  state, so if your socket was readable, but then you decide you don't actually want to  read it yet and you still want to call it E-Poll wait again, then you have a problem  because that file is still readable.  So you'll get an event back again saying, hey, the file is readable and you may want  to defer that.  So one efficient way of doing that is to use the edge triggered mode.  What this does is it means that E-Poll will return events when they transition state,  so going from not ready to ready instead of returning the level of the event, whether  it's ready or not.  That way you won't be bothered with lots of returns repeatedly for events that you haven't  handled yet.  There's also a one shot mode that you can enable.  What this does is say you want to respond to an event on a file descriptor, but then  you're going to wait for a while after you've handled that before you start monitoring again.  With E-Poll system call design, you would actually have to use E-Poll control one more  time in order to disable that file descriptor temporarily.  Now with the one shot mode, you can get that for free because you're telling the kernel,  hey, when this fires, when it triggers, please just disable it.  And I'll bring it back later on when I'm ready.  So it saves some of the system calls.  It's a bit more efficient.  The final mode that I really wanted to talk to you about is the E-Poll exclusive mode,  which optimizes the way that multiple waiters who are all waiting for a file descriptor to  become ready are handled.  Let's look at that in detail.  This is called the Thundering Heard problem.  It's a well-known problem in computer science and in operating systems.  The problem is if you have multiple processes or threads that are all waiting for work and  the work becomes available, what do you do?  If you wake all of them up and say, hey, there's work available, please go and grab it, then  what will happen is that only one of them will be able to get the new work and the other  ones, when they try to grab it, will find that there's no work available because there  was only one item.  And so that's very inefficient.  On the other hand, you need to do this approach for load balancing because otherwise, if you  decide who to give it to, if that worker is busy and isn't ready yet for the next piece  of work, then your system will slow down and you'll have to wait for it.  So this is called the Thundering Heard problem.  Whenever we wake up, all of the workers wake up.  They try to grab work.  Only one of them makes it.  Everyone else is just wasting CPU trying to grab work.  So what the exclusive flag does is it tells the kernel that it's okay to wake up just  a single worker.  And that way, you avoid all that extra overhead.  Let's look at that.  So I ran a benchmark with E-Poll, exclusive on and off.  And what we're seeing here is we're seeing the number of messages that were received  and sent.  And this is divided by the amount of CPU time that was spent.  And so we really see the CPU efficiency here.  We see how many messages were we able to process per unit of CPU time.  As the number of threads goes up on the x-axis, you can see that without the E-Poll exclusive  flag, the scalability is poor, the performance drops as we add more threads because they're  all going to wake up, try to fetch some work, and it turns out there's nothing to do.  And they go back to sleep again and we've wasted CPU.  That's why the efficiency is so poor.  And we can see how well the E-Poll exclusive flag works when we have a lot of threads.  Great.  So that was the Thundering Heard.  Another big change, a big departure that E-Poll made in its API design is it is a stateful  API.  It is not a stateless API.  Select and pull are stateless.  Each time we call them, the kernel starts from scratch.  It doesn't know anything about the file descriptors that we're going to be monitoring.  And when we're done, it doesn't care anymore.  It forgets about it.  And we start from scratch every time.  So each time the kernel is going to have to set up the monitoring on the whole set of  file descriptors only to collect an event for maybe one or two that are actually ready  now and return that back.  So that's wasteful.  And what E-Poll does is because we've created this E-Poll file descriptor using E-Poll create1,  it can actually store which file descriptors are being monitored.  And when you make the E-Poll P-weight call, what it's doing is it's not setting up the  monitoring.  That's already been set up.  At that point, it's just collecting the events that have occurred.  So that's much, much more efficient.  So now the kernel doesn't need to loop over all your FDs, set up the monitoring, and so  on.  Now it just needs to look at which events have already occurred.  So this is an improvement that E-Poll makes just in terms of the fundamental design.  And the trick here is that it's a stateful API.  Now taking this a bit further, how does the efficiency of this look?  This big O notation here I'm using is just to show you, does user space or does the kernel  have to loop over the data that we're processing many times?  And in the case of select, the kernel actually has to loop over those bitmaps all the way  up to the maximum file descriptor number.  So that's very inefficient.  The pathological case there is say we have file descriptor 1000 and it's the only FD  we're monitoring.  We still need to create a big bitmap with lots and lots of zeros all the way up to the  thousands one.  And so that way CPU cycles.  Now poll does better.  The poll system call does better.  It only loops over the actual total number of FDs that we're monitoring.  So it doesn't care if the file descriptor number is 1000 or if it's one, the efficiency  just hasn't changed there, but it still needs to loop over all of them.  So if we want to monitor 1000 FDs, then each poll call is going to have to process all  of them.  Finally, let's get back to E-Poll.  E-Poll is an improvement here.  E-Poll only needs to process those that are actually ready.  And so you can see that this is a fundamental improvement in terms of efficiency.  We only need to see the FDs that are ready.  And in user space, the E-Poll events that are returned from poll weight are really just  the FDs that we're about to process.  So this is great.  But that was the 2000s.  That was E-Poll.  Things have moved on since then.  So in the past few years, Linux has gotten the IOU ring system calls and a lot of system  calls have now been added to IOU ring so that it can do a lot of functionality asynchronously,  which means that there is a submission queue where user space can add requests.  And there is a completion queue where user space gets the finished request that the kernel  has finished processing.  And it allows user space to queue up one or more requests to the kernel.  The kernel will then handle them, and the results will be written back to the completion  queue when they're done.  The system call here is IOU ring enter.  And we basically just tell the kernel how many new requests are in the submission queue  that we want to process.  And we tell it how many requests we want to wait for.  Do we want to wait for one request?  That could be the next request, whatever that is.  Or do you want to wait for 10 requests?  Or maybe for no request if we don't actually want to wait at all.  So that's how the system call works.  There's no timeout here, which you might have noticed compared to all of our other system  calls, but we're going to see how that works in a second.  OK, so now I mentioned that the submission queue takes these requests.  Well, there's lots of request types.  Here are the operations that are relevant to file descriptor monitoring.  And there are many more that you can find in the documentation that aren't going to  be relevant for file descriptor monitoring.  Poll add allows us to do a one-shot file descriptor monitoring operation.  We can add an FD.  We can tell it which events we care about.  And this request will complete when the file descriptor has some activity.  If we change our mind, if we decide, OK, we don't want to monitor that file descriptor  anymore, then we can use the poll remove request type to cancel it.  An interesting one, an interesting request type, is the ePollControlRequestType.  What this allows us to do is it allows us to invoke the ePollControlSystemCall functionality  using IOU ring.  So why would we want to do that?  We can do it in a way that avoids system calls.  So the bottleneck with the ePollControlDesign is that that system call only operates on  a single file descriptor.  It adds a single file descriptor.  It removes a file descriptor or it modifies an existing one.  But you can't use it to, say, monitor 1,000 file descriptors in a single system call.  And if you have a lot of file descriptors that you're changing frequently, then, of course,  that system call overhead is going to be relevant.  When using IOU ring, you can actually queue up all of these requests and then do a single  IOU ring enter system call to process them.  See the trick with IOU ring is that the submission queue and the completion queue are M mapped  into user space memory.  So the user space processes memory space has the submission completion queues.  And that's why we can access them and add things and process completions without doing  system calls.  So that's an interesting use here.  And if you remember back when I said ePoll can nest because that file descriptor itself  supports polling, we could use that ePoll file descriptor within IOU ring.  For example, we could use poll add on the ePoll file descriptor.  The final thing I wanted to mention is timeouts since the IOU ring enter system call doesn't  have a timeout argument, the way to do it is to add a timeout request to the submission  queue.  And that way, we'll be able to stop waiting if there is no activity when our timeout expires.  OK, so that was a lot.  It's a very different model.  And here is an example using the libUring user space library.  What's happening here is that we are preparing one file descriptor for read monitoring.  We're using poll in flag.  So we use IOU ring getSQE to get the next available submission queue entry.  We then set the file descriptor number on it and the poll in flag.  And then we do the IOU ring SQE set data call.  And what that does is it associates, it stores our object pointer, our application object,  or any 64-bit value that we want.  It stores that with the SQE so that when this completes, we'll get that value back and we  can look up our application object.  OK, great.  So we've added the request, but now we're going to tell the kernel about it and we're  going to wait for the completion.  And we can do that using the single IOU ring submit and wait library call.  And when it returns, we know something has happened.  And then we can just loop over the completion queue with the IOU ring for each CQE loop.  And then our application can handle the completion result.  And that user data field that you see there is going to be that object value that we stashed  in the submission queue.  And then finally, we need to call IOU ring CQE advanced just to tell the kernel that we  have now processed those completion queue entries and they can be reused.  So that's programming with IOU ring.  What are the characteristics of IOU ring compared to EpoL?  So first of all, we talked about how EpoL control only handles one FD at a time.  Whereas with IOU ring, we can handle many FDs at a time.  We can add many FDs, we can remove many FDs in a single system call.  So that's an advantage right there.  The system call also combines both submission and completion into a single system call.  So it further minimizes it.  Whereas with EpoL, we had to do EpoL control and EpoL wait.  With IOU ring, we only need to do IOU ring enter.  That's the only system call.  So again, this is a little performance boost if this is in the inner loop of your application  or trying to minimize CPU cycles and minimize latency.  Another thing that's interesting about IOU ring is that it supports busy waiting, both  in the kernel and in user space.  And what that means is that since that completion queue is M-mapped into user space, our user  space process can actually just peek at the completion queue memory and can see when requests  become ready.  It doesn't need to make a system call in order to ask the kernel if requests have completed.  If your application is either CPU intensive or if it already has a busy wait loop, you  can integrate into that.  And you can easily and cheaply check any IOU ring events, which means you can do file  descriptor monitoring from within a busy wait loop in your application.  On the kernel side, it's also possible to do busy waiting because IOU ring supports  kernel polling threads, but we're not going to get too into that.  There are also other features that IOU ring has.  I think we've only really scratched the surface here.  It's very powerful.  It has a concept of linked requests.  It has some optimizations for pre-registering file descriptors and buffers so that the kernel  doesn't need to keep looking them up.  So that saves some CPU cycles.  And there's a lot more.  So it's a really interesting API.  Now I just mentioned busy waiting.  And so I want to go back and mention that if you're using select poll and ePoll, they  also have some busy waiting support.  It's limited, but in Linux, you can use the net core busy poll at sysctl in order to set  the number of microseconds that these system calls should busy wait instead of idling the  CPU.  Now, this is used in applications where you have dedicated CPU resources and you want  to minimize latency, idling the CPU, putting it into a low power state, and then when a  packet comes in having to wake it up again and having to schedule and get back to what  we were doing adds latency.  And so some applications can use this with select poll and ePoll.  So I just wanted to mention that since we were talking about busy waiting for IOU ring.  By the way, this is only available for network sockets in Linux.  So it's a network subsystem thing.  And if you're using other types of file descriptors, then it won't work with them.  Okay, so we've looked at the APIs, but we're not really done yet because we talked about  threads and some of the pros and cons of threads.  Then we looked at file descriptor monitoring.  There's actually another approach that we can take aside from threads or file descriptor  monitoring.  With IOU ring, we could actually just do the IOU operations asynchronously.  So we could just tell the kernel using IOU ring to do a read.  And it would complete the request when that read is finished.  And if the socket is not ready or the pipe is not ready, then that request would just  be waiting.  But in the meantime, our user space thread could make progress.  So we can solve the same problem that we had with our matrix chat client of monitoring and  doing stuff in multiple FDs.  We can actually solve that using asynchronous IOU instead.  Why might that be an interesting idea?  Well, because this way, we don't need to attempt to read, find out the socket has no data available,  then add it to the set of FDs to monitor, go into the kernel, wait to be woken up when  something happens, and then try reading again.  We can eliminate all of that kind of housekeeping work, all of that back and forth, and just  do a single asynchronous read.  So it's potentially an interesting approach.  One of the issues with it, though, is that it's something more for new applications.  It's hard to retrofit this into existing applications, especially if you remember that I mentioned  that GTK and QT and so on are based on file descriptor monitoring.  Using something like this universally would mean basically breaking the APIs and changing  the way that applications use file descriptors.  They would have to start using asynchronous operations instead of monitoring file descriptors.  And so this is kind of hard to do with existing code.  I've written a blog post about it that goes into more details about the performance advantages  that we could get by doing this.  And if you're writing new code, you might consider trying this out and seeing how it  works.  Okay.  We should just briefly mention the other APIs that we don't have time to cover in detail.  First of all, there is CIGIO, which is an old mechanism, and it's a signal-based mechanism  where you can mark a file descriptor as, please send me CIGIO signals when the file descriptor  is ready.  But it's rarely used, probably because programming with signals is tricky.  It's also not a very expressive interface.  It's hard to use, and therefore I've never seen it used.  There's Linux AIO, which is similar to IOU ring, but is a precursor to it.  It has a subset of the functionality, and so that's why I didn't go into that one, but  that's available too.  Okay.  And then finally, let's move on to some performance data and some benchmarks.  I have posted a code for a benchmark.  What it does is it receives data on a random file descriptor and then just sends the data  back.  So, it doesn't change the benchmark.  It doesn't change the set of file descriptors that are monitored during the benchmark.  It only sets it up once.  So this may not be representative of your application, but it does show the raw performance  of just the file descriptor monitoring itself, just the waiting.  Okay.  So let's look at the scalability of all the APIs we've talked about.  We see they fall into three classes, right?  These curves fall into three groups.  The bottom group is select and pull, which isn't a big surprise because we talked a lot  about their limitations and how they're inefficient and how they don't scale.  So we see here that they really don't do well compared to the others.  Although note that the Y axis on this graph doesn't start at zero.  So it's not as bad as it looks on the graph, but I wanted to zoom in so we can see these  details here.  In the middle, we have threads.  I wanted to make sure we compare this with an application that just has one thread per  IOTask.  So we don't lose sight of what programming with threads is like.  And you can see here that the performance is just always lower than the E-Poll and IOUring  performance at the top when we use threads.  That's the blue line in the middle.  What's interesting is that IOUring using AIO, so not doing file descriptor monitoring, but  doing asynchronous reads and writes, is similar to threads in this benchmark.  Now I have to add a caveat.  I think that there's a lot more that can be done, whether that's tweaking the benchmark  itself to make use of IOUring more efficiently.  It's not using busy waiting or any stuff like that.  Or extending the IOUring implementation in the kernel to make it more favorable for this  type of usage.  So I think it could go a lot higher, but that's where it is.  And it kind of makes sense because IOUring internally does have a thread pool in the  kernel.  So eventually it does end up in a thread.  And so it kind of makes sense that it's similar to using threads.  Okay.  And finally at the top, the fastest ones, very similar performance was IOUring doing file  descriptor monitoring and E-Poll.  So they're both excellent.  And you can see actually that they scale very well with the number of file descriptors.  They didn't, there wasn't a steep curve.  They were very flat.  So that's nice to see.  And IOUring is the one that is a little bit more flexible, as I mentioned.  It has all these other features that you might find useful in your application, whereas E-Poll  is just dedicated to file descriptor monitoring.  That's the difference between those approaches.  I just want to also show the CPU efficiency of this.  So again, here we're dividing by the unit of CPU time consumed in order to see a slightly  different picture here.  We're seeing that threads actually consumes a lot of CPU per request compared to the event-driven  approaches, which makes some sense because when we're switching threads, we have higher  overhead.  So the scheduler, maybe the cache and so on, and the call stack all need to be changed  and cleaned out, especially with security mitigations and so on.  So yeah.  Finally, summary.  On this slide, I just wanted to show you which of these APIs are the portable ones.  I think we saw with performance that really if you are able to use an event loop library  that supports a Linux specific API or you have the time to implement it yourself, that's  worth it for performance.  Thundering Heard is solved by E-Poll and IOU ring.  So if you have those concerns, it's best to use those APIs.  And then finally, E-Poll is one that's popular today in high performance applications.  I think that IOU ring might be more popular in the future as people use some of the other  functionality together with file descriptor monitoring.  Okay.  Thank you very much.  We can move on to questions.
file_descriptor_monitoring_0_179.png file_descriptor_monitoring_180_359.png file_descriptor_monitoring_360_1631.png file_descriptor_monitoring_1632_2759.png file_descriptor_monitoring_2760_2855.png file_descriptor_monitoring_2856_4499.png file_descriptor_monitoring_4500_8627.png file_descriptor_monitoring_8628_9887.png file_descriptor_monitoring_9888_13487.png file_descriptor_monitoring_13488_15815.png file_descriptor_monitoring_15816_19943.png file_descriptor_monitoring_19944_22571.png file_descriptor_monitoring_22572_22619.png file_descriptor_monitoring_22620_22667.png file_descriptor_monitoring_22668_22715.png file_descriptor_monitoring_22716_22787.png file_descriptor_monitoring_22788_25223.png file_descriptor_monitoring_25224_27275.png file_descriptor_monitoring_27276_31343.png file_descriptor_monitoring_31344_34343.png file_descriptor_monitoring_34344_38135.png file_descriptor_monitoring_38136_39131.png file_descriptor_monitoring_39132_39215.png file_descriptor_monitoring_39216_39287.png file_descriptor_monitoring_39288_39335.png file_descriptor_monitoring_39336_39407.png file_descriptor_monitoring_39408_39515.png file_descriptor_monitoring_39516_39563.png file_descriptor_monitoring_39564_39611.png file_descriptor_monitoring_39612_39683.png file_descriptor_monitoring_39684_40055.png file_descriptor_monitoring_40056_40343.png file_descriptor_monitoring_40344_40631.png file_descriptor_monitoring_40632_41099.png file_descriptor_monitoring_41100_43151.png file_descriptor_monitoring_43152_44567.png file_descriptor_monitoring_44568_46763.png file_descriptor_monitoring_46764_49175.png file_descriptor_monitoring_49176_51335.png file_descriptor_monitoring_51336_55535.png file_descriptor_monitoring_55536_57959.png file_descriptor_monitoring_57960_61271.png file_descriptor_monitoring_61272_62915.png file_descriptor_monitoring_62916_65051.png file_descriptor_monitoring_65052_66371.png file_descriptor_monitoring_66372_67679.png file_descriptor_monitoring_67680_68615.png file_descriptor_monitoring_68616_72251.png file_descriptor_monitoring_72252_73163.png file_descriptor_monitoring_73164_74291.png file_descriptor_monitoring_74292_74435.png file_descriptor_monitoring_74436_74483.png file_descriptor_monitoring_74484_74543.png file_descriptor_monitoring_74544_74831.png file_descriptor_monitoring_74832_74956.png
Hi, my name is Stefan Heinetzi and today we're going to talk about the evolution of file descriptor monitoring in Linux. So what is file descriptor monitoring? File descriptor monitoring APIs allow applications to find out which file descriptors are ready to perform I.O. So that could be something like a server that is handling a bunch of different connections and also has a listen socket. Well, it might want to know when a new client connects to its listen socket. It might also need to know when new data arrives on one of the existing established connections. In other cases, you might have, for example, a pipe which has a finite sized write buffer. And if the application fills up that write buffer, it can't write any more data to it until the other side of the pipe, the reader, has read some of that data. And so file descriptor monitoring can let the application know when there's more write buffer space available. In Linux, there are a number of APIs for file descriptor monitoring. These system calls have been added over the years and they have different characteristics. They have different API designs and they have different performance and scalability. So today, what we're going to do is we're going to have a look at these APIs in turn and then we're going to compare them. So applications still use all of these APIs and this is not some functionality that has been obsolete completely in the kernel. So it's still normal to see different applications using different APIs, but that makes it especially interesting to go and look at them and understand their differences so that we can choose which ones to use ourselves. Before we start looking at the actual system call API design and the performance, let's have a look at how file descriptor monitoring works inside the kernel. Inside the kernel, various file descriptor types are implemented. For example, device drivers might have some file types that they have. Of course, file systems also implement file types. And these file types have a pull function. This pull function returns the set of events that are currently available on that file descriptor. So it could be, for example, that the file descriptor is ready for reading. But this pull function also allows the caller to register themselves and receive a wake up when that file finally becomes ready for the events that it is looking for. The exception to this single API that exists inside the kernel is CIGIO. It has its own API. But for the most part, these very different system calls are actually implemented using this one API in the kernel. Now what are the set of events that the kernel knows about and the set of events that it will raise? Here is the table with the most important ones. The read and the write are the very commonly used ones that are used for finding out when a socket has more data to read or, for example, when a pipe can be written to. There are also events for closing file descriptors, in particular for finding out when the other side of a socket or a pipe has been closed. So there is a hang up, an E-PollHOP event, which notifies the application that the socket has been closed. That doesn't mean that the file descriptor is completely finished and no longer useful because there might still be data in the receive buffers that user space can still read before it itself decides to let go of that socket. There are also some file specific events. So this depends on the specific file type. And a driver, for example, might raise this event when something relevant to its file type happens. That's the E-PollPri flag. It's not used very often. There's also an error flag, of course, in case something goes wrong and the application needs to respond in order to handle this file descriptor that's no longer usable. There's some out of band events, which I haven't even shown here because they're quite rare. They're used for TCP connections, which have the concept of sending data outside of the normal stream. And another thing that's interesting to note is that when these file descriptor events occur, they occur at a point in time. By the time that user space gets around to actually, for example, reading from that file descriptor that had something available, it could be that the file descriptor no longer has data available, either because another thread or another process read from it, or maybe something else happened. So it's important for applications to be aware that in some cases maybe they'll receive an event, and when they actually try to respond to that event, things have already changed and moved on. The kernel has the O non-block open flag for files, and it's important to set this this way. If the application finds out the file is ready for reading, and it does the read, but there's actually no data there, then the kernel will return with E again and let the application know there was nothing. By default, file descriptors are not in non-blocking mode, instead the process would actually be put to sleep, so this would hang the application. So it's worth knowing this. Now before we look at the various APIs in detail, I want to still take a step back, and let's remind ourselves why is file descriptor monitoring used at all? Why do applications do this? Let's take an example, say we're implementing a text-based matrix chat client. We have two sources of activity here. The human who is interacting and entering chat messages that they want to send to the chat room on the keyboard, and the second source of activity is the matrix server, which is sending us the messages that remote users have posted to the chat room, and we need to display them. So we have two different things we need to do at the same time, two different IO activities, and one way of implementing this would be to spawn one thread for the terminal, for the TTY, and one thread for the matrix server socket, and those threads could then process any data that becomes available on those file descriptors. The thing with threads though is that you need some coordination for the life cycle of the thread to safely start it and stop it at the appropriate time, and in addition to that, if there are any shared resources in use, for example, the user interface, which has both updates from the keyboard when the user enters a message and updates from the server when new messages appear, we will need to protect that and implement some synchronization or something to make sure that the terminal, the TTY thread, and the matrix server socket thread don't interfere with each other. So this adds complexity. It would be nice if there was a way to avoid having to have this complexity that that multi-threading brings. The final thing to keep in mind with threads is that they're not free. They are resources and they have some amount of overhead. They have a cost associated with them. And this is particularly apparent when you have a server that has many, many thousands or tens of thousands of file descriptors, because each of those threads is going to have a call stack and it's also going to have some kernel resources associated with it. So is there another way, a more lightweight way, a way that doesn't require complex coordination? Yes, there is. One approach is using an event loop. So this is called an event-driven architecture. Instead of making every IOTask a separate thread, we can instead have an event loop and each activity, so for example the terminal, the TTY file descriptor, whenever it becomes ready, that's an event. We wait for the next event, we handle the current event, and then we go back into the loop and we just repeat doing this until the application stops. And in this event loop approach, file descriptor monitoring is what powers this next event function or this next event primitive. We need to have the ability to monitor a set of file descriptors and see which one of them is ready and then we'll let our application handle it. To become a bit more concrete as well, where is this used in the real world? Which applications use file descriptor monitoring? Well, pretty much all GUI applications, all graphical applications tend to do this because GTK, QT, and also other user interface frameworks, even on other platforms, tend to be based on event loops and they tend to monitor file descriptors. That tends to be what powers the core of user interfaces. But it's not just graphical applications. Servers like NGINX, the web server, is a well-known example for an application that uses an event-driven architecture and event loops. You might also hear about thread per core architectures, which are becoming popular for storage and network processing. And the idea there is that you start a thread for each CPU, but then on that CPU, you run an event loop in order to process work. And finally, you might also come across file descriptor monitoring when it's simply used in order to get around limitations of blocking APIs. And what I mean by that is that sometimes you want to read from a file or write from a file or perform some other blocking operation, an operation that can take a long time. And if those system calls do not have timeouts or cancellations, sometimes an approach that people take is they use a file descriptor monitoring API in order to get that functionality so that they can cancel our timeout. Okay. So we've covered the background for what is file descriptor monitoring, why do applications use it, and what are some of the real world examples. Now let's take a look at the select system call. The select system call is the first of the ones we're going to look at because it is the earliest one that's still widely used. It was introduced in 4.2 BSD, so before Linux. And the variant that I'm showing here on this slide is Pselect. This is a newer version of it. It's a POSIX system call, so it's available not just on Linux. And what this system call added on top of the original select is it has a nanosecond timeout and it also has a signal mask. The reason I'm mentioning these things is I'm always going to show you the most powerful and most recent variant of these system call families because they're useful, for example, if you need high resolution timers, you want to make sure to use something that has, say, more than just millisecond or even microsecond resolution. Or if you're using POSIX signals in your application, then being able to control the signal mask while you're in a blocking system call is important because you need to decide when to block and unblock certain signals. Okay, but let's get to the file descriptor monitoring part. So how does select work? The select system call takes up to three bitmaps, these FD sets. And user space will set a bit to one if it wants to monitor that file descriptor number. So for example, say we want to monitor file descriptor number four, then we would have to set the fifth bit in the bitmap to one to tell the kernel we want to monitor file descriptor number four because the bits, right, they're numbered zero, one, two, three, four, and then that's the one that we want to set to one. If we set it to zero, the kernel will not monitor it. And that's how you build these FD set bitmaps. When you call the system call, the kernel will then look at that bitmap, will monitor the file descriptor numbers that you requested. And when a file descriptor becomes ready or when there's a timeout, it will write out a new bitmap. It will overwrite your bitmap. And instead, you'll have a one if the file descriptor was actually ready, or you'll have a zero if the file descriptor is not ready. And the return value to the system call is just the total number of bits set. And so this is how we can monitor multiple file descriptors with one system call. That's the select system call. Now select has some well-known design quirks, some limitations that make programming with it a little limited in some cases. First of all, this bitmap representation of the file descriptor number space is not very efficient because if we have a single file descriptor we want to monitor, but it happens to have a high number, then we need to provide a long bitmap with zeros all the way up to the file descriptor that we want to monitor. And then when the kernel processes the system call, it's going to have to scan that bitmap to find R1. It's going to have to start from the beginning of the bitmap. And so this is just going to waste CPU. It's maybe not a very good representation to use when you have just a few file descriptors, especially if the numbers are high. Another quirk is that POSIX select has a constant called fdsetsize. And that is the maximum file descriptor count that you can have in the bitmap. So what this means is that on Linux with Glib C, 1,024 is the limit for select. If your application has a file descriptor number that's higher than that, for example, you opened the file and you got file descriptor number 2,000, you would just simply not be able to use the Glib C select function in order to monitor that because it won't fit in the bitmap. So that's a pretty severe limitation if you want to be able to process many file descriptors. So for something that needs to scale and have a lot of file descriptors, select is basically out of the question. Okay, another API design aspect that we're going to be looking at as we go through these different system call APIs is how does the application associate an object with that file descriptor? A file descriptor number by itself is not necessarily useful to a program. If your program is doing many things at the same time and then you find out, okay, file descriptor 13 is now ready for reading, you might not know what that means. Which object is associated with that file descriptor? Was it an HTTPS session that we had going? Was it a pipe we were using to communicate with another process? We need some way of being able to connect the file descriptor with an application object so we can then easily handle the event for that object. Select tends to not do so well here. Usually select is used in a hard coded way where you see actual code that literally says if a particular file descriptor, for example, in our matrix client, if the TTY file descriptor is set, then go and process the TTY. And that is fine when you have a fixed number of file descriptors that you know at compile time. It doesn't work so well if you have, say, a server that's going to have many sessions and the number of file descriptors is dynamic. Now we need to figure out some way. So an obvious way is to just create a hash table but that is going to be a little bit inconvenient. We'll have to set up an extra data structure and it's going to be a hash table to go from a file descriptor number to our application object. So it doesn't have a built in way of doing this. We're going to see later on how other APIs make this easier. Okay, so let's move on from select. Poll is a POSIX API so it's widely available and it makes some of these shortcomings of select go away because it chooses a different representation for the file descriptors. Instead of using this bitmap that we had with select, it uses an array of struct poll FDs and so now we're no longer having to use a bit for every possible file descriptor number. Instead we just use a poll FD for each file descriptor that we actually want to monitor. We don't have zeros anymore. We just have the poll FDs that we are interested in. So that's an interesting approach. It has an input event mask. That's the poll FD events field where the application sets the events it cares about. For example, poll in or poll hop and then it has an R events field where the kernel writes the actual result event mask, the actual events that are ready. So that could be zero if there's no activity on this file descriptor or it could be a non-zero value if one of the bits that we were looking for is ready. It returns the event count, the total number of file descriptors that are actually available. So this is the poll API. Let's look at how it compares to select. So first of all, we're no longer limited to 1024 file descriptors which is a very important property if we want to be able to handle many, many connections at the same time. And the reason for not having this limitation is we're no longer using this bitmap and we no longer have that fixed FD set size. Okay. And in addition to that, we're now using a dense file descriptor list. We don't have all those zeros. So that's another improvement. Why is an improvement? It's an improvement because it means that the kernel, when processing the system call, no longer needs to scan all those zeros and skip through all of them. Instead, it just gets a useful list of the actual FDs that we want to monitor. Okay. So some CPU cycles are saved. Another interesting design decision is that there's that R events field. The kernel does not update our input event mask when we make the system call. Why does that matter? Why is that important? Well, it means you can set up the poll FD array once and then your application can loop and just keep calling poll as long as your set of file descriptors doesn't change. It can just keep calling poll and doesn't need to rebuild that poll FDs array every time it calls poll, which is a nice property. In select, we didn't have that because the kernel overwrote the FD sets that we passed in those bitmaps. We have to recreate the bitmaps every time from scratch. So this is an improvement that poll makes. That's nice. It saves CPU cycles. Finally, application object lookup is now simpler. We can just have a parallel array next to the poll FDs. We just have another array and each entry corresponds to the same index in the FDs array and we just store the object, the pointer to the object. And that way we can efficiently and easily look up the application object associated with this FD. So that's an improvement. The final thing I wanted to show in this slide is a common optimization that programs make. Since the system call told us how many FDs were ready, we can short circuit this for loop. We don't have to scan every poll FDs struct. Then we were monitoring a thousand poll FDs and only one of them was ready. As soon as we find that one, we will leave this for loop and we'll stop scanning. So that's a nice quality to have. We can save some CPU cycles by doing that. Great. So we've looked at select and we've looked at poll. Those are the most portable, they're POSIX, they're widely used, but they're relatively old and they do have some known scalability issues. So now let's move into the 21st century. So E-Poll was added to Linux in the 2000s and it changed the API. It made quite a big, it was quite a big departure from poll and select, which we're about to see. So E-Poll has an E-Poll control system call that we can invoke every time we want to add another or remove a file descriptor from the set of file descriptors that we're monitoring. And in fact, E-Poll itself is represented as a file. So you have an E-Poll file descriptor that you create with the E-Poll create one system call. And this allows you to actually have multiple sets of E-Poll in your application at the same time. If maybe you want to either have nested event loops or you just have different event loops and you want to keep them separate, you can do that. It's not global, it's not per process. Instead it's actually, you can have many instances and each one of them is one E-Poll file descriptor, which is an interesting aspect and we'll see more of that later. So how does it work? Well, we tell E-Poll control which file descriptor we want to monitor and we pass it an event mask similar to how we did it with the poll system call. We also have a data field where we can store an application specific value. We're going to get that value back when this file descriptor becomes ready. And so you can already imagine what that's going to do. It's going to make the application object look up even easier because the kernel will tell us which application object we wanted if we decide to store, for example, the pointer to the object in this data field. So that's something that's coming. All right, so we have been able to add file descriptors for monitoring, but how do we actually get events back? There is a system call called E-Poll P-weight. Here I've shown you the new Linux 5.11 version of the system call. This variant is called E-Poll P-weight 2 and the reason I wanted to show it to you is because it now finally has nanosecond timer resolution, which is excellent for applications that need high resolution timers. That was one of the few big limitations of E-Poll for a long time and now it's been solved. So that's awesome in the next 5.11. Okay, so when we call the system call, we give it an array of E-Poll events and we tell it how many events there are and the kernel will then go and collect the readiness information from the file descriptors and write them into this array and return the number of ready FDs, the number of events that it filled out. What's interesting here and what's different from poll is that we could be monitoring a thousand file descriptors and yet we can call this system call with just say 10 event array elements that the kernel will fill in. And the kernel is prepared to handle that. That's perfectly fine. And it makes a lot of sense because a lot of time your application will only ever have one or two or a few files that are ready at a given time in the event loop. And so it would have been wasteful to have to allocate, if we're monitoring a thousand file descriptors, it would be wasteful to allocate a thousand E-Poll events just in case all of them happen to be ready at the same time. So this is a bit of a gives you some flexibility, allows you to minimize resources if you want. And the kernel also has a built-in algorithm to make sure that if you do have a thousand file descriptors and you only read out the first 10 events, when you call it again, it remembers which ones you've already processed. And even if those files do become ready again, say even more data has arrived with the socket, it won't return them yet. It will make sure that you receive all the other pending events first. So this prevents starvation because imagine you had a loop and there was a lot of activity on the file descriptors and you were only ever harvesting a subset of them, then some of the high numbered file descriptors at the end of the array would just never be processed. So this is a useful feature to have. But that's not all. E-Poll has quite a few interesting things. So E-Poll has an edge triggered mode. If your application decides not to actually do something that will change that readiness state, so if your socket was readable, but then you decide you don't actually want to read it yet and you still want to call it E-Poll wait again, then you have a problem because that file is still readable. So you'll get an event back again saying, hey, the file is readable and you may want to defer that. So one efficient way of doing that is to use the edge triggered mode. What this does is it means that E-Poll will return events when they transition state, so going from not ready to ready instead of returning the level of the event, whether it's ready or not. That way you won't be bothered with lots of returns repeatedly for events that you haven't handled yet. There's also a one shot mode that you can enable. What this does is say you want to respond to an event on a file descriptor, but then you're going to wait for a while after you've handled that before you start monitoring again. With E-Poll system call design, you would actually have to use E-Poll control one more time in order to disable that file descriptor temporarily. Now with the one shot mode, you can get that for free because you're telling the kernel, hey, when this fires, when it triggers, please just disable it. And I'll bring it back later on when I'm ready. So it saves some of the system calls. It's a bit more efficient. The final mode that I really wanted to talk to you about is the E-Poll exclusive mode, which optimizes the way that multiple waiters who are all waiting for a file descriptor to become ready are handled. Let's look at that in detail. This is called the Thundering Heard problem. It's a well-known problem in computer science and in operating systems. The problem is if you have multiple processes or threads that are all waiting for work and the work becomes available, what do you do? If you wake all of them up and say, hey, there's work available, please go and grab it, then what will happen is that only one of them will be able to get the new work and the other ones, when they try to grab it, will find that there's no work available because there was only one item. And so that's very inefficient. On the other hand, you need to do this approach for load balancing because otherwise, if you decide who to give it to, if that worker is busy and isn't ready yet for the next piece of work, then your system will slow down and you'll have to wait for it. So this is called the Thundering Heard problem. Whenever we wake up, all of the workers wake up. They try to grab work. Only one of them makes it. Everyone else is just wasting CPU trying to grab work. So what the exclusive flag does is it tells the kernel that it's okay to wake up just a single worker. And that way, you avoid all that extra overhead. Let's look at that. So I ran a benchmark with E-Poll, exclusive on and off. And what we're seeing here is we're seeing the number of messages that were received and sent. And this is divided by the amount of CPU time that was spent. And so we really see the CPU efficiency here. We see how many messages were we able to process per unit of CPU time. As the number of threads goes up on the x-axis, you can see that without the E-Poll exclusive flag, the scalability is poor, the performance drops as we add more threads because they're all going to wake up, try to fetch some work, and it turns out there's nothing to do. And they go back to sleep again and we've wasted CPU. That's why the efficiency is so poor. And we can see how well the E-Poll exclusive flag works when we have a lot of threads. Great. So that was the Thundering Heard. Another big change, a big departure that E-Poll made in its API design is it is a stateful API. It is not a stateless API. Select and pull are stateless. Each time we call them, the kernel starts from scratch. It doesn't know anything about the file descriptors that we're going to be monitoring. And when we're done, it doesn't care anymore. It forgets about it. And we start from scratch every time. So each time the kernel is going to have to set up the monitoring on the whole set of file descriptors only to collect an event for maybe one or two that are actually ready now and return that back. So that's wasteful. And what E-Poll does is because we've created this E-Poll file descriptor using E-Poll create1, it can actually store which file descriptors are being monitored. And when you make the E-Poll P-weight call, what it's doing is it's not setting up the monitoring. That's already been set up. At that point, it's just collecting the events that have occurred. So that's much, much more efficient. So now the kernel doesn't need to loop over all your FDs, set up the monitoring, and so on. Now it just needs to look at which events have already occurred. So this is an improvement that E-Poll makes just in terms of the fundamental design. And the trick here is that it's a stateful API. Now taking this a bit further, how does the efficiency of this look? This big O notation here I'm using is just to show you, does user space or does the kernel have to loop over the data that we're processing many times? And in the case of select, the kernel actually has to loop over those bitmaps all the way up to the maximum file descriptor number. So that's very inefficient. The pathological case there is say we have file descriptor 1000 and it's the only FD we're monitoring. We still need to create a big bitmap with lots and lots of zeros all the way up to the thousands one. And so that way CPU cycles. Now poll does better. The poll system call does better. It only loops over the actual total number of FDs that we're monitoring. So it doesn't care if the file descriptor number is 1000 or if it's one, the efficiency just hasn't changed there, but it still needs to loop over all of them. So if we want to monitor 1000 FDs, then each poll call is going to have to process all of them. Finally, let's get back to E-Poll. E-Poll is an improvement here. E-Poll only needs to process those that are actually ready. And so you can see that this is a fundamental improvement in terms of efficiency. We only need to see the FDs that are ready. And in user space, the E-Poll events that are returned from poll weight are really just the FDs that we're about to process. So this is great. But that was the 2000s. That was E-Poll. Things have moved on since then. So in the past few years, Linux has gotten the IOU ring system calls and a lot of system calls have now been added to IOU ring so that it can do a lot of functionality asynchronously, which means that there is a submission queue where user space can add requests. And there is a completion queue where user space gets the finished request that the kernel has finished processing. And it allows user space to queue up one or more requests to the kernel. The kernel will then handle them, and the results will be written back to the completion queue when they're done. The system call here is IOU ring enter. And we basically just tell the kernel how many new requests are in the submission queue that we want to process. And we tell it how many requests we want to wait for. Do we want to wait for one request? That could be the next request, whatever that is. Or do you want to wait for 10 requests? Or maybe for no request if we don't actually want to wait at all. So that's how the system call works. There's no timeout here, which you might have noticed compared to all of our other system calls, but we're going to see how that works in a second. OK, so now I mentioned that the submission queue takes these requests. Well, there's lots of request types. Here are the operations that are relevant to file descriptor monitoring. And there are many more that you can find in the documentation that aren't going to be relevant for file descriptor monitoring. Poll add allows us to do a one-shot file descriptor monitoring operation. We can add an FD. We can tell it which events we care about. And this request will complete when the file descriptor has some activity. If we change our mind, if we decide, OK, we don't want to monitor that file descriptor anymore, then we can use the poll remove request type to cancel it. An interesting one, an interesting request type, is the ePollControlRequestType. What this allows us to do is it allows us to invoke the ePollControlSystemCall functionality using IOU ring. So why would we want to do that? We can do it in a way that avoids system calls. So the bottleneck with the ePollControlDesign is that that system call only operates on a single file descriptor. It adds a single file descriptor. It removes a file descriptor or it modifies an existing one. But you can't use it to, say, monitor 1,000 file descriptors in a single system call. And if you have a lot of file descriptors that you're changing frequently, then, of course, that system call overhead is going to be relevant. When using IOU ring, you can actually queue up all of these requests and then do a single IOU ring enter system call to process them. See the trick with IOU ring is that the submission queue and the completion queue are M mapped into user space memory. So the user space processes memory space has the submission completion queues. And that's why we can access them and add things and process completions without doing system calls. So that's an interesting use here. And if you remember back when I said ePoll can nest because that file descriptor itself supports polling, we could use that ePoll file descriptor within IOU ring. For example, we could use poll add on the ePoll file descriptor. The final thing I wanted to mention is timeouts since the IOU ring enter system call doesn't have a timeout argument, the way to do it is to add a timeout request to the submission queue. And that way, we'll be able to stop waiting if there is no activity when our timeout expires. OK, so that was a lot. It's a very different model. And here is an example using the libUring user space library. What's happening here is that we are preparing one file descriptor for read monitoring. We're using poll in flag. So we use IOU ring getSQE to get the next available submission queue entry. We then set the file descriptor number on it and the poll in flag. And then we do the IOU ring SQE set data call. And what that does is it associates, it stores our object pointer, our application object, or any 64-bit value that we want. It stores that with the SQE so that when this completes, we'll get that value back and we can look up our application object. OK, great. So we've added the request, but now we're going to tell the kernel about it and we're going to wait for the completion. And we can do that using the single IOU ring submit and wait library call. And when it returns, we know something has happened. And then we can just loop over the completion queue with the IOU ring for each CQE loop. And then our application can handle the completion result. And that user data field that you see there is going to be that object value that we stashed in the submission queue. And then finally, we need to call IOU ring CQE advanced just to tell the kernel that we have now processed those completion queue entries and they can be reused. So that's programming with IOU ring. What are the characteristics of IOU ring compared to EpoL? So first of all, we talked about how EpoL control only handles one FD at a time. Whereas with IOU ring, we can handle many FDs at a time. We can add many FDs, we can remove many FDs in a single system call. So that's an advantage right there. The system call also combines both submission and completion into a single system call. So it further minimizes it. Whereas with EpoL, we had to do EpoL control and EpoL wait. With IOU ring, we only need to do IOU ring enter. That's the only system call. So again, this is a little performance boost if this is in the inner loop of your application or trying to minimize CPU cycles and minimize latency. Another thing that's interesting about IOU ring is that it supports busy waiting, both in the kernel and in user space. And what that means is that since that completion queue is M-mapped into user space, our user space process can actually just peek at the completion queue memory and can see when requests become ready. It doesn't need to make a system call in order to ask the kernel if requests have completed. If your application is either CPU intensive or if it already has a busy wait loop, you can integrate into that. And you can easily and cheaply check any IOU ring events, which means you can do file descriptor monitoring from within a busy wait loop in your application. On the kernel side, it's also possible to do busy waiting because IOU ring supports kernel polling threads, but we're not going to get too into that. There are also other features that IOU ring has. I think we've only really scratched the surface here. It's very powerful. It has a concept of linked requests. It has some optimizations for pre-registering file descriptors and buffers so that the kernel doesn't need to keep looking them up. So that saves some CPU cycles. And there's a lot more. So it's a really interesting API. Now I just mentioned busy waiting. And so I want to go back and mention that if you're using select poll and ePoll, they also have some busy waiting support. It's limited, but in Linux, you can use the net core busy poll at sysctl in order to set the number of microseconds that these system calls should busy wait instead of idling the CPU. Now, this is used in applications where you have dedicated CPU resources and you want to minimize latency, idling the CPU, putting it into a low power state, and then when a packet comes in having to wake it up again and having to schedule and get back to what we were doing adds latency. And so some applications can use this with select poll and ePoll. So I just wanted to mention that since we were talking about busy waiting for IOU ring. By the way, this is only available for network sockets in Linux. So it's a network subsystem thing. And if you're using other types of file descriptors, then it won't work with them. Okay, so we've looked at the APIs, but we're not really done yet because we talked about threads and some of the pros and cons of threads. Then we looked at file descriptor monitoring. There's actually another approach that we can take aside from threads or file descriptor monitoring. With IOU ring, we could actually just do the IOU operations asynchronously. So we could just tell the kernel using IOU ring to do a read. And it would complete the request when that read is finished. And if the socket is not ready or the pipe is not ready, then that request would just be waiting. But in the meantime, our user space thread could make progress. So we can solve the same problem that we had with our matrix chat client of monitoring and doing stuff in multiple FDs. We can actually solve that using asynchronous IOU instead. Why might that be an interesting idea? Well, because this way, we don't need to attempt to read, find out the socket has no data available, then add it to the set of FDs to monitor, go into the kernel, wait to be woken up when something happens, and then try reading again. We can eliminate all of that kind of housekeeping work, all of that back and forth, and just do a single asynchronous read. So it's potentially an interesting approach. One of the issues with it, though, is that it's something more for new applications. It's hard to retrofit this into existing applications, especially if you remember that I mentioned that GTK and QT and so on are based on file descriptor monitoring. Using something like this universally would mean basically breaking the APIs and changing the way that applications use file descriptors. They would have to start using asynchronous operations instead of monitoring file descriptors. And so this is kind of hard to do with existing code. I've written a blog post about it that goes into more details about the performance advantages that we could get by doing this. And if you're writing new code, you might consider trying this out and seeing how it works. Okay. We should just briefly mention the other APIs that we don't have time to cover in detail. First of all, there is CIGIO, which is an old mechanism, and it's a signal-based mechanism where you can mark a file descriptor as, please send me CIGIO signals when the file descriptor is ready. But it's rarely used, probably because programming with signals is tricky. It's also not a very expressive interface. It's hard to use, and therefore I've never seen it used. There's Linux AIO, which is similar to IOU ring, but is a precursor to it. It has a subset of the functionality, and so that's why I didn't go into that one, but that's available too. Okay. And then finally, let's move on to some performance data and some benchmarks. I have posted a code for a benchmark. What it does is it receives data on a random file descriptor and then just sends the data back. So, it doesn't change the benchmark. It doesn't change the set of file descriptors that are monitored during the benchmark. It only sets it up once. So this may not be representative of your application, but it does show the raw performance of just the file descriptor monitoring itself, just the waiting. Okay. So let's look at the scalability of all the APIs we've talked about. We see they fall into three classes, right? These curves fall into three groups. The bottom group is select and pull, which isn't a big surprise because we talked a lot about their limitations and how they're inefficient and how they don't scale. So we see here that they really don't do well compared to the others. Although note that the Y axis on this graph doesn't start at zero. So it's not as bad as it looks on the graph, but I wanted to zoom in so we can see these details here. In the middle, we have threads. I wanted to make sure we compare this with an application that just has one thread per IOTask. So we don't lose sight of what programming with threads is like. And you can see here that the performance is just always lower than the E-Poll and IOUring performance at the top when we use threads. That's the blue line in the middle. What's interesting is that IOUring using AIO, so not doing file descriptor monitoring, but doing asynchronous reads and writes, is similar to threads in this benchmark. Now I have to add a caveat. I think that there's a lot more that can be done, whether that's tweaking the benchmark itself to make use of IOUring more efficiently. It's not using busy waiting or any stuff like that. Or extending the IOUring implementation in the kernel to make it more favorable for this type of usage. So I think it could go a lot higher, but that's where it is. And it kind of makes sense because IOUring internally does have a thread pool in the kernel. So eventually it does end up in a thread. And so it kind of makes sense that it's similar to using threads. Okay. And finally at the top, the fastest ones, very similar performance was IOUring doing file descriptor monitoring and E-Poll. So they're both excellent. And you can see actually that they scale very well with the number of file descriptors. They didn't, there wasn't a steep curve. They were very flat. So that's nice to see. And IOUring is the one that is a little bit more flexible, as I mentioned. It has all these other features that you might find useful in your application, whereas E-Poll is just dedicated to file descriptor monitoring. That's the difference between those approaches. I just want to also show the CPU efficiency of this. So again, here we're dividing by the unit of CPU time consumed in order to see a slightly different picture here. We're seeing that threads actually consumes a lot of CPU per request compared to the event-driven approaches, which makes some sense because when we're switching threads, we have higher overhead. So the scheduler, maybe the cache and so on, and the call stack all need to be changed and cleaned out, especially with security mitigations and so on. So yeah. Finally, summary. On this slide, I just wanted to show you which of these APIs are the portable ones. I think we saw with performance that really if you are able to use an event loop library that supports a Linux specific API or you have the time to implement it yourself, that's worth it for performance. Thundering Heard is solved by E-Poll and IOU ring. So if you have those concerns, it's best to use those APIs. And then finally, E-Poll is one that's popular today in high performance applications. I think that IOU ring might be more popular in the future as people use some of the other functionality together with file descriptor monitoring. Okay. Thank you very much. We can move on to questions.
going to talk about the evolution of file descriptor monitoring in Linux. So what is file descriptor monitoring? File descriptor monitoring that has been obsolete completely in the kernel. design and the performance, let's have a look at interface, which has both updates from the we will need to protect that and implement some applications, all graphical applications tend to take is they use a file descriptor monitoring API sets of E-Poll in your application at the same the scalability is poor, the performance drops as number of microseconds that these system calls they're inefficient and how they don't scale. So scale very well with the number of file event-driven approaches, which makes some sense are able to use an event loop library that E-Poll and IOU ring. So if you have those