Test one to test one to see this seems reasonable, right? So you can use this microphone and we should be good It was many a many a year ago in this kingdom by the sea that a maiden there lived whom you may know By the name of Annabelle Lee And we loved with a love that was more than a love I and my Annabelle Lee Once upon a midnight dreary while I pondered week and weary over many acquaint curious volume of forgotten lore as I pondered Nearly napping suddenly there came a tapping as of someone gently wrapping 1115 can everybody hear me now? Excellent, so I'll start it off by saying the one thing I must not forget to say which is hi dad okay, so Thank you to the organizers for accepting this presentation Which is about deferred work in the Linux kernel? And thank you everyone for attending this morning when there are so many other talks you could have heard Before I get into the material, I'll start out by saying that all the demo code and the Linux kernel and such Artifacts are at this github URL In fact, you can download the demo code and run it yourself on your machine if you have properly prepared it The latest version of this slides will always be at this URL. It really is HTTP rather than HTTPS So to dive right in let's talk about what deferred work is is it too loud? Is it too cold to a little bit louder? Okay? Okay. All right. How's that? Okay, I'm not a good singer So like this Okay, I'll get this before we're done Okay, so to get into the technical material now Let's talk about what deferred work is and thank you audience for your participation so Deferred work comes basically in two categories. There is work that Was running or could run But doesn't because of resource unavailability and the resource that is lacking could be a lock a buffer a message And so that work is waiting Then there's work that is newly needed in response to an event and this work is typically run by a function called a callback and so Just to make more concrete what I'm talking about Here is a seasonally appropriate example Your accountant might say upload your tax documents But rather than do that now if you're in an uninterruptible fund state You might in queue the work function on a list to be performed later So this is an example of deferred work and of course deferred work is not unique or invented by the Linux kernel It's a old pattern in software engineering and used by all kinds of programs Well, let's turn to the kinds of deferred work that are important for the Linux kernel So for the purpose of this talk, there are two major Performers of deferred work. There are soft IR cues So called because they follow on are the bottom halves in the parlance of hard IR cues, which are actual Interrupts and then there are key workers, which are executor of work, which has been placed on work cues And so the first half of the talk will describe soft IR cues Which are a legacy mechanism added in 1992 to the kernel the file soft IR cue.c actually has Linus's own copyright at the top and then Key workers, which also are a very old feature of the kernel, but are more flexible and newer and And so why would you care about deferred work at all? Why would you ever think about it? Well, the answer is sometimes it Causes problems on the system and so if you're a kernel caretaker or a kernel developer, you may have to look into it One example of something that can go wrong is that a task gets deferred too long While the work that is performed by soft IR cues and work cues Can be put off and shouldn't be performed for example in interrupt context. It can't be put off forever So RCU stands for read copy update. It's essentially the kernels garbage collector that frees no longer used memory You can guess that while you could delay freeing unused memory. You can't delay it forever or actually you run out of memory strangely another sign that Work is being delayed too long is when heavy network traffic makes the System kind of fall over or freeze up That may be because Network soft IR cues for example are delaying other soft IR cues and much more about that in a moment so the kind of opposite problem of too long deferral of Work is that the executors of deferred work like k workers or k soft IR QD Could run and run and run and run and meanwhile the user space applications Who's a serving serving the user space applications is the purpose of the system? And it doesn't get to run because these callbacks are running and so you have to look into that oddly another sign that Divert work is running too long is that the watchdog timer associated with k workers can fire and that happens when a K worker is sitting on a core and not yielding and so if You work on systems that are very busy you have to look into this kind of problem and the real pain point About soft IR cues and work cues is that they gather up a lot of different kinds of tasks together and It's often been hard to figure out exactly what they're doing and it has been hard to figure out what to Do about them when you have problems So the purpose of this talk is really to open this window and give you some tools to investigate these Work deferral mechanisms and to some extent do something about them the first half of the talk is about soft IR cues which Remain difficult to control and difficult to understand and the second half of the talk is about work cues and That is full of good news so that I'll give away the fact that the talk has a happy ending But with that let's dive right into soft IR cues So what are the soft IR cues really? Well, there are 10 to lift 10 delicious flavors These are the order in which K soft IR QD will execute them There are high-end tasklet soft IR cues Which are first in order then there are the network soft IR cues which are kind of obvious There are some associated with a block layer for those who don't know the block layer is what connects memory and file systems There are some run by the scheduler There are the rather obscure IR cue pole ones which are used as far as I know only by network attached storage devices There are two kinds of timer soft IR cues and whoops There are some associated with the read copy update Garbage collector and so without knowing anything further about soft IR cues You might say ha the network receipt Soft IR cues are above the timers in this list and feel some foreboding And so the fundamental design that we have a hard IR cue and then we have a soft IR cue that does the work That it is indicating needs to be done sounds like a good design But there are problems. In fact Soft IR cues just between us are not the most beloved feature of the kernel. Here are three money quotes from well-known software developers of Frederick vice-vector has said that soft IR cues are a pain to deal with Thomas glasner who's the dean of real-time Linux has called K soft IR QD the big soft IR Q lock and He has commented that Soft IR cues have heuristics, which he finds disgusting So I will brace yourself. I will now show you these disgusting soft soft IR cue heuristics There are two limits, which according to the Documentation have been established by experimentation. They are shown right here one is the time slice Maximum that case after our QD can use and is one is the maximum number of times that case after our QD will Run through that list of 10 soft IR cues These numbers are hard compiled into the kernel and since you all know undoubtedly that the kernel runs everything from smart watches to sprinklers to Supercomputers to Android phones. You might be wondering Huh, why are these numbers perfect for all those use cases and the answer is they're not and no one knows But no one has the nerve to change them. They've fitted the kernel for a long time This situation is particularly painful because we continually have improvements to scheduling in the kernel There's going to be a talk later on this afternoon About some new improvements in scheduling in this very room That I'm looking forward to but the scheduler is can't varies these numbers because they are they are compiled in So this is not a great situation But furthermore, let's that's not the really bad problem with soft RQs Let's talk about what the really bad problem is so the only one soft RQ runs at any given time on a given core and What that really means is When a hard IRQ occurs and as we say in the kernel Raises the associated soft RQ the runtime will check if the another soft RQ Is already running so in other words if this hard IRQ has preempted a running soft IRQ then The soft RQ will have called the function local bottom half Disable which is the the villain in this part of the talk so if no Soft RQ is already running then the happy path called the piggyback occurs and the function do soft IRQ Will invoke the soft IRQ that the hard IRQ indicates is needed However, if a soft RQ was already running Then it has taken this lock. It is called local bottom half disable you recall that soft RQs are also called Bottom halves and the soft RQ will have to wait for the case of the RQD thread To execute it so in other words the soft RQ may occur actually in interrupt context Without a context which right after the hard IRQ or it may occur some time and the reason I say some time is The next time case soft RQD runs it could run out that time slice and never get to this soft RQ So the waiting may be for a while So that is the big soft RQ lock that Glacier is referring to I want to talk a little bit about Kind of briefly about how you can tell what case soft RQD is doing So to do that I have two pieces of demo hardware here one is this very laptop which I'm running a kernel that no sane person would run on a computer used for a presentation and one is In arm 64 8 core IMX 8 board running kernel 6.1 and So the laptop is running kernel 6.7 and What I'm going to show you we have to put down this mic for a second. Hopefully it won't make a loud crashing noise is They function called Stack count that is part of the Libby PF BCC tools suite It's a package you can install on your system And what stack count does is it prints out stack traces from the running kernel? That end in a particular function and so I showed you in the previous slide how do soft RQ function is actually the executor of soft RQs, and so that's the function we're going to trace and the The demo is going to be run by stack count via a shell script I'm running all these demos via shell script just to minimize the amount that you actually have to watch me type with the demo is live and What is going to happen is that as With all BPF programs Live LLVM is going to jit compile some C code. It's going to submit it To a validator in the kernel Which if the program is found to be valid will load it into a virtual machine inside the kernel and Then it will spit out these stack traces that end in the function do soft RQ and show you What the paths of execution are leading to calls of soft RQ do soft RQ? So if this is all sounds confusing here's some warning messages It's always nice in the morning and now I'll run it on the 6.1 kernel on the arm board And so the live LLVM is actually jit compiling this code and inserting it in the kernel And you can see the laptop is faster than the arm board And so here are our stack traces. There were 6,200 occurrences of this stack trace during that time period and this stack trace refers to CPU idle, so I believe that it is a Scheduler soft IRQ if I can do this one-handed here's one that says send message. So this is clearly a network Stack trace or 914 of these and here's the here's the result from arm There here's another CPU idle. So this is another scheduler soft IRQ All these functions with EL One EL zero these are all arm assembly Would be great if I had a handless like But hands-free like but whatever So here's more TCP stuff. Here's a PCIE Function that is calling do soft IRQ you can see here's local bottom half Enable that is freeing the lock right right before do soft IRQ runs and so forth So this is the best way I know to see what? Ksoft IRQD is actually doing on a running system so Enough about that. This is the demo you've just seen Let's talk a little bit more about the big soft IRQ lock and why it is a problem for real-time Linux So this shows why local bottom half disable the big soft IRQ lock is a problem Another title for this slide could be F trace output is hard to understand But let's work with it. This slide actually comes from Sebastian Severe who's one of the main Developers of RT Linux from a talk. He gave it Linux plumbers in the fall Fundamentally what we see here is that a network soft IRQ net Rx is running a Sita interrupt which is higher priority comes in and Would like to run the block soft IRQ, but it can't run even though it's a Rt system and the highest priority thread should run Because the network soft IRQ has called local bottom half disable So what actually happens is that the scheduler increases the priority of the network? Receipt soft IRQ it finally finishes it may take a while and then finally the block soft IRQ gets to run and so this problem with local bottom half disable and non concurrency of soft IRQsology that we we in this room in theory at least can improve so So I wanted to show you a timeline of the Great laborers over the years of attempts to improve soft IRQs starting with Colonel 3.8. You could run RCU the Garbage collector Callbacks in their own K thread and not inside K software QD. That means you could pin these threads to cores You could increase their priority Obviously changing the priority of K software QD doesn't do you a lot of good because you're changing the priority of all those soft IRQs together Starting in Colonel 512 you could run the network callbacks in their own thread And move them out of K software QD Ah, there have been Two attempts To move timers out of K software QD if there's any callback you would like to be timely presumably it would be a timer callback And there have been two more recent ones One was a proposal by Frederick Weiss mecher and colonel 6.5 to mark individual timers as Able to be run at the same time as other soft IRQs that ran into lock depth problems and didn't get very far Another one called Local lock nested that was presented in the CVR talk from plumbers that I just showed a snippet of this is very clever It actually uses scoped locks the Colonel has scoped locks now So we could in theory remove all the go-tos from the Colonel, which would just be amazing This was an attempt to move Get basically get rid of local bottom half disable and replace with actual locks close to the data That local bottom half disable is protecting so in good software engineering practice We want to have locks right next to the critical data sections that Can't be touched by multiple threads at one time But problem is is that local bottom half disable is scattered throughout the colonel and then finally Just merged in six point nine this week there is some work by Tijin howl the maintainer of Work queues and C groups in the colonel to change tasklets into Users of the work queue API so the the tasklets are going to stay Run by case after a Qt, but their API is completely changing Tasklets had a a global use after free problem Which if you don't know what that is it's a big headache for security and so There's work underway to basically change all the tasklets over from Using the existing API to work queues and this change was Linus's own idea So it's not amazing that it has merged and I should say that Tijin howl the author of work queues maintainer of work queues and C groups will be speaking in this very room later on this afternoon and So I I'm looking forward to hearing that So with that We are Good God, that was not what I wanted to happen. I think I clicked on a hyperlink all the text on the other text all these slides That isn't blue as a hyperlink There we go. So to summarize the part of here about Softire queues There are about 250 call sites for local bottom half disabled in the colonel so getting rid of it is no small task as People have commented nobody really knows what this lock is is protecting That was the same feature with the big colonel lock of old which took years to to remove It is possible to run RCU Network and in the real-time colonel timer Softire queues and a separate thread Which makes it more manageable and easier to observe But if you do that, then you're incurring a context switch penalty Every time that thread runs and that may actually make your system performance worse So for all these tunables that I'll be mentioning As with any colonel configuration you really have to run Performance tests relevant to your workload to see if the changes will help and as I said, it's Not so user-visible, but a big improvement is coming to tasklets in Colonel six point nine whose merge window is still open Because they will be changing to the work queue API and work use are just an all-around better design that we're done with soft our cues and if anybody has any Questions about soft our cues before we move on I'll be I'll be happy to answer them There's no room to put the mic stand next to all the do-dads. I have on top of the podium For your demo, what were you actually running in the script? You were tracing syscalls, but like what were you actually running in order? Were you tracing? Let's go back and we can just look at that real quickly again. As I said all these All these are at github Slide Here's just a slide that's a substituting for the Little app demo. So it's actually running this upstream tool stack count It prints out these stack counts along with the number of occurrences of that exact stack count And so you can put any function you want here that's not running You know, that's I don't know There are very few functions you can't put here And so you can trace any function you want using this upstream tool Just to confirm the bottom half lock is on a per core That is correct. So two of Instances of soft our cues to block soft our cues could be running on two different cores But on a given core there is per core data that can't be corrupted by two threads And so the the crazy part is is it really not possible to run block device soft our cues and You know scheduler soft our cues at the same time what what per CPU data could they have in common? And the answer is I said with 250 call sites of that function is no one actually knows Do you gain anything by trying to lock your soft IR curious to a particular core? So soft our cues are per Core threads and so at boot the kernel creates a case after a QD thread for each core And that's fundamental to the kernels design. So there's Yeah, and so a hard RQ on a given core will raise the soft RQ on that core So if you have a real-time Linux, you can pin the interrupts to different cores But if I start talking about that, I'll never talk about work is Any other burning questions before we talk about work is Let's get to let's get to the good news part of the talk So the hardest part about this presentation Has been okay, so the heart of that part about this presentation is that Work cues have changed so much in the last 18 months that I've had trouble keeping up with it and preparing us talk Let's talk about what work cues are. So here's a diagram to explain the fundamental idea of work cues Unsurprisingly we have lists of work functions, which are pointers to the work that needs to be performed Each one of these work cues will belong to a different kernel entity so it might be that You know some file system for example owns this work queue and that file system driver is free to In queue all different work functions on the work queue and but a different You know a crypto driver would have its own work queue with its own work functions Nonetheless these two work cues may be associated with the same worker pool Which includes the K worker threads that actually perform the work on on behalf of the drivers and once again the bound work cues that I'm talking about here are Kernel per CPU threads So at boot on each core the kernel starts a high priority worker pool and a default priority worker pool and The K workers have names like K worker core number and then just an instance and When you create a work queue the work queue is associated with a worker pool a worker pool Based on the flags that you set on it And so if you set a high priority on your work queue then it will be assigned to the high priority worker pools nothing surprising about that Let's talk about the names of K workers you see in the process table I Sort of described already the bound K workers. There's a fixed number of pools to per core The kernel will spin up and spin down new K workers as they're needed and these K workers are bound So they can't migrate in contrast. We also have the mechanism of unbound K workers Unbound K workers can run on on any core by default but that is configurable as I will note in a second There is a pool ID, which is just a number as is the K worker ID So every time you reboot these these numbers may be different the unbound pools are for long-running persistent work That some are created that boot for system services and some are dynamic related to device drivers these Work items can can wander from core to core There not only is not a fixed number of workers per pool, but there's not a fixed number of pools And so once again, why might you care about all this stuff who cares about this work use and K workers and the answer is if you are Responsible for maintaining the kernel you may be presented with a Jira ticket, which has a splat like this in it where the Work queue core informs us that some K worker has been running and not yielding for 207 seconds, which is a lot of computer time and that Anti-social K workers associated with pool 112 and the splat will show you This is a real data from 515 kernel There were three work queues associated with that pool at the time the crime was committed One was the IXDBE Network driver one was some file system cleanup tasks and one was a device driver whose Name has been redacted You can see that this isn't in fact an unbound work queue because it could run on any of 56 cores and the reason that these three work queues are in the same pool is because the flags of each of them ends in the bite a which is Some flags that describe the configuration of the work queue now if you have experience in maintaining The kernel and dealing with threads that are conflicting threads that are hugging cores You might say, huh, I'll either change the priority of the thing that's causing the problem Or I'll pin it to a core away from the work that I really care about and so you might use CHRT to change the scheduler policy You could use renice to change the priority or you could use task set to set the core Affinity of the problematic thread and all three of these methods won't work I So I'm going to show you this once again by coming over here to the hardware So the thing you'd like to do is use task set to set the The CPU affinity of a thread written as program called classify process affinity You have to type the names of the programs. That's the only thing and We'll ask classify process affinity to read affinity of K workers and So on this arm a core board of Work or board here are these kernel per CPU Bound K workers at the top with the names K worker slash core number down here at the bottom We have the unbound K workers. They're in a Default priority and a high priority pool You can see Right away that K workers come and go Because the numbering of these K workers in pool 8 is not consecutive. They're Presumably used to be a u8 to and the wasn't being used so the kernel got rid of it But the real point of this demo was we can see that all these K workers are Unpinnable and that seems really odd Because I just told you that the unbound K workers Can migrate so if they can migrate Why shouldn't they be able to be pinned that seems to not make any sense and the answer is Going to be shown in a second here. I just want to Just want to compare and contrast the situation with K workers on the newer kernel 6.7 You can see now there are K workers called slash are Which are rescue K workers? That reclaim memory when the system is getting low so they prevent the system from ooming and Let's go over to back to the slides So the way the class is classified process affinity works is it reads struck test flags from Prokofs What do I mean by test set and chrt and re nice Managed the wrong thing what I specifically mean is that what you really care about is your work Not K workers. You don't care about kernel threads that perform the work you need What you really won't want is for this work to get done and so the work queue API Quires a change of mindset you actually configure properties onto the work queue onto the work and then Work queue core provides K workers that match the attributes that you want so test set and chrt make make System calls into this kernel scheduler and the kernel scheduler really doesn't manage work use because it manages threads You need to use the work queue API that manages work And so I'm running out of time apparently, but I'm going to show you On x86 6.7 here a demo which should make this clear Iconify the so this demo Shows you how to Illustrates the use of the Okay All right Perfect. Okay. Now. We're going to jet through this demo. So this demo is to show you how to manage Work queues via the work queue API not via the scheduler and how you bind properties to the work queue Not to the key workers about which you don't care. So this demo won't work before kernel 6.6, which is why we are looking at it on Actually, let's start this over again. Oh, yeah, okay, which is why we're looking at it on Intel Here we're looking at a listing of sys devices virtual work queue. There are Five work queues in there one associated with block control groups three associated with MVME and one associated with flushing of dirty pages back to the backing storage and You can kind of guess from seeing these all these storage devices one Work queues exported to SysFS that unlike software queues Where it is the network stack that tends to cause problems for other work. It is the block layer in Work queues and here are the tunables that are Setable via SysFS. There are two associated with Affinity of the work queue notice is affinity of the work and not the K worker again One associated with concurrency. There's niceness that you know what it is I don't have time to talk about it, but the Treatment of affinity and the kernel with work queues Has really improved in recent kernels the default affinity affinity is per cache line Now it used to be per pneumonode. So this is a big improvement once again in performance by default We can see that the default niceness is zero I guess that might be off the bottom of the screen. Oh, well tough to take my word for it now we're using the dragon debugger from meta to run a Script called work you dumped up pie And we're asking it about the MVME delete work queue. We can see that the MVME delete work queue is Running in work pool 16 on all cores because it is unbound This demo is a little bit slow because it really is running in real time. And so now We're asking dragon to query the kernel What else is running in work pool 16 besides the MVME delete work queue and the answer is a whole bunch of stuff Which is unrelated related to thunderbolt related to graphics and so forth and so on And we're echoing for into SysFS to change the niceness and we can see that The MVME delete work queue has changed to a different worker pool. And so as I said, this is a I'm just gonna skip the rest of this And go back to the side so I can finish And this is what I've just shown you is that you can configure work queues via SysFS and not via the functions that you're used to and work queues have Just had one improvement after another in 6.5 6.6 There's also a new BPF BCC tool called work queue lat which is not even part of the kernel source repository, which has just appeared and so with that I have told you that software queues run in Interrupt context they can be fast under the best Circumstances, but often they are slow and the opportunities for configuring them are are low And people Have been working on it very hard and progress is the lack of progress is frustrating work queues run in process context You manage the work queues not the key workers about which you don't care Their observability configurability and performance has improved greatly in recent kernels I think Sarah Newman for her suggestions about this talk and there is a huge amount of Further advice and resource information in these slides which are available at the scale website So with that I thank you for attention, and I think I have time for probably about one One question, but I'll be around after the presentation if somebody wants to ask I have which I've got 20 minutes. Oh man. Who wants to see about half dozen more demos? Or actually who has a question first well, I'll just show you So the when I changed the niceness of this work queue it changed the pool 18 So we were able to change the pool of the work queue by setting the niceness and you might say who cares Well, if we ask Dragon now to query the kernel We can see that in fact the pool 18 has niceness minus four So the reason this NVMe delete work queue is in pool 18 now is once again its attributes match that pool and what else runs in the new pool 18 pool 16 had like 15 work queues associated with it the answer is nothing so NVMe delete work queue has its own Its own worker pool So that's great right that's that's wonderful, but actually it might not be great and I'll answer your question in just a second. The reason it might not be great is switching between work queues When when a key worker is running Doesn't require a context switch. Context switches are very expensive in In modern kernels and so it could be by putting your your work queue in its own pool all by itself That it got more latent so there's always a trade-off in Performance CPU utilization and latency and there's no perfect solution and it depends on your work queue And you have to you have to measure to find out if you're making something better So let's we run the microphone over to the thought that has a question and Tom I think you left your sunglasses up here Could you elaborate on what niceness means? How exactly niceness changes? Where the work is being moved? Right, so I mean if we would have changed the question is How niceness affects where the work is being moved? so There was no work or pool with niceness minus four or eleven or something like that, right? so the Colonel will just create new work pools If there is no work pool that matches a Work queue 18 may already have been been there and just been idle for all I know I'm not I'm not actually sure The niceness then does just what you think it does it Increases or decreases the priority of the key workers And so it's a communication between the work queue API and the scheduler, but it's Very odd because you're setting this niceness on a data structure essentially right and Niceness is the priority of the thread so The work queue API is really weird The more you think about it the more it actually gives you the tools to do what you want Because no one really cares about k threads at the end of the day. I'm not sure if I answered your question Okay, so a threaded IRQ can be set affinity to a particular CPU You can set that this seems like now you've set a Particular work queue to be able to also have affinity to a particular core. Is that correct? It's one of the eyes one of those parameters, right? So the question is you can set the affinity of a work queue to a particular core That is correct if you set the the niceness to zero which is the default or the niceness to 20 minus 20 Which is the high priority one and you set it to particular core. It's gonna run on one of the bound work is But it won't stay on the same core all the time it will oh it will If it you can set the affinity Let's go back and look at that. Yeah, it's too small. I can't see it. That's right. I will make it larger. Thank you So if we say this devices virtual Work queues look at right back Yeah, she'll get it bigger. So here we have two parameters affinity scope and affinity strict Affinity scope can be per CPU per cash line per Numa node System-wide or there's one called SMT which has to do with hyper threads on a on a given core and Cash is now the default which is great. So Unbound work will migrate only within the scope of a given cash line by default Then there's this affinity strict Which is a parameter where you can express If my work can't run because it's current affinity scope is so busy Do I want to allow it to migrate to a different affinity scope and? So You also can set the CPU mask Something I haven't said is when we looked at the list of Unbound work queues associated with pool 16. There's like 15 of them But there's only a few work queues in SysFS and that's because we're only the work queues that are created with the flag WQ SysFS I think appear in SysFS So if a particular Work queue is giving you heartburn one of the things you could do to make a tiny kernel patch and just turn on that flag and then it'll be there in SysFS and you can You can change it so with the By default Any work queues that are created by drivers will just be run by the the bound work queues And there's another flag WQ unbound that assigns them to the To the unbound one question. So a lot of this is stuff. I haven't played with is there a particular Book or blog series or video series you recommend to get more familiar with work queues and Yes, the question is what are the best resources for for work queues I As I said, I put some stuff that I found useful in here. There's some Also some all these are hyperlinks here if you want to read about these features I have to say that the documentation for work queues is excellent people like work queues the Manual for software queues is still missing unfortunately because people hate software queues They want to change them. They want to get rid of them and no one wants to write about them On this slide are three different tools for observing work queues Work queue monitor, which is kind of top-like. There's work you dump which dumps out a huge amount of information I've been piping it through grep and it's because it produces pages of output And I'm only grepping out the one line that it's it's slow and then there's this BPF CC tools new tool called work you lat which prints out the amount of time elapsed between a work you wanting to run and actually run in the spirit of the whole family of BPF CC tools that report about latency, so You could learn a lot just by reading the kernels entry documentation and using these tools And then you get get most of it as I said all these Dem I have a bunch more demos That I don't have time to show and you could just you could download all of them and run on my All right, thank you, and thanks for a great talk Hi, I hope this isn't too off-topic, but in terms of other ways of dealing with real-time Do you have any notion of what the disadvantages might be of like on an arm? System using attached cortex M course to do your real-time stuff. Is there are there disadvantages to that? Okay, so for those the question is are there advantages to using cortex M course which may be part of arm SOC's arm SOC's systems on chip tend to have high performance cores and lower performance cores sometimes in pairs And so you can assign some work to the cortex and lower capability cores certainly using the cortex M cores to offload the kernel Say from handling network packets, you're just a kind of any kind of Workload that tends to thrash the kernel by having a lot of interrupts you could possibly assign to the To the cortex M. Well, the reason is to try and Make it more hard real-time. You know like if you're trying to Run a PID loop running it on a time-sharing CPU can give you less than ideal results because PID loops tend to assume that you're always measuring the system at a constant rate and Even with the the real-time Linux stuff that's not really hard real-time. It's more soft real-time. Yeah, so Bill is talking about PID. He means Proportional integral derivative Servo loops or tank circuit as we used to call them. Yeah And could you run a control loop on a cortex M and sure that something like that that just is a very well-bounded? Task would be perfect for a dumb device sure Yeah, and basically my question is is there any downsides to doing something like that if it has to do a lot of communication with the Other course then you incur a Yeah, okay These two are software cues and work cues interchangeable in a system such that you can disable one and your system will be fine or is the kernel in such a Place where you have to keep them both enabled So the question is can you do without? Software cues or work cues they're very both very integral to the operation of the kernel they appear if you look at the kernels main function in the in the directory in it There's actually a main function a main dot C with a main function in it and it actually starts the work Cues and software cues there because Colonel really can't Even ignoring user space and the actual work you want done it can't be without them. So they start really Quite early after the system powers on You can you can fiddle around with them a little bit, but you're kind of stuck with them. So You just have to deal with them Yeah In your top in the description of your talk you mentioned that you also have been using BPF trace I was just wondering what sort of information that you've been trying to view through that. Yes. What are your experiences with it? Right, so I've written Thanks for the question. I've also been playing a little bit with BPF trace to peer into the heart of Work cues and soft arc cues Soft arc cues what you can observe with them is really limited and the reason is because they can run following the hard arc you in atomic context and interrupt context and so if you know what interrupt context is you can't be printing from interrupt handlers or You can't have trace points inside interrupt handlers. That's why the soft arc cues are so inscrutable but because the work you run in In process context you can have all these nice things So let's run. There's one here called so Actually, well, yeah, let's run this one So here's Well, let's cat it. So here's oh, I put some comments at the top, but here's here's the entire BPF trace Program So it's gonna print out this little header and then it's gonna print a table It's easier just to this but this is the whole this is the whole darn thing So BPF trace is simple all these functions tend to Watch themselves So if I don't rep out L-disc, it's just gonna tell you that it's printing to this To this console, which isn't very interesting. So once again See function is being jit compiled by Lubell DM. It's being inserted into the virtual machine in the live kernel and Here is some output. So here is the CPU mask of some different work use which are running Here's a memory management per CPU work you here's a least recently Used add drain per CPU. So it's cleaning out the page cache. Here's a so This memory management work you is them By gripping out eight we're looking at only at the bound ones. So it's running some memory statistics and then if we look at the unbound ones We see lots of events work use running here's some associated with the Intel graphics There's Ordered and unordered work use with just yet another Wrinkle and here you can see the work they're performing Flushing fleshing the bump the front buffer. So that's blit for people who follow graphics and so forth Console callback on the event. So once again, it's sort of observing itself here, but Anyhow, it's easy to cook up these these BPF tray scripts, but dragon and Debugger and these Great Python tools in tree and the kernel came along while I was writing this and they're Better and they're maintained by Togen howl who maintains work is so Kind of no need to all your own anymore. I would say it's easy to do Just sorry just to follow up. So would it be easy to for instance to See what wasn't actually getting scheduled in the same worker pool that you were interested in and then See like if there was something overriding what you were Function you that you were interested in scheduling if you if you play around with these different tools So you work you monitor Which is in the tunnel. This is the top-lake tool. So what once again? This is running dragon and it's just running kitchen house Python here if by some combination of these tools You really can you can really fair out everything And you can always make Little BPF tray scripts to watch the work you that you're really interested in But this this is now so easy compared to what it was when I started working on this talk. It's amazing And also there's this automatic CPU intensive detection Long story short the splat that I showed you in the beginning. I think it might not happen now because internal automatic detection of Long-running work use has improved and these observability tools Didn't exist in kernel 515 when I had to investigate this bud And so this problem is just so much easier than it was 18 months ago. It's it's amazing So this part of the talk is all good news so are you aware of any tools that or any cases in The field actually where people actually migrate to new work pools and groups if you will based on observe latency sort of a Scheduler that runs in user space that manages this stuff automatically or is that something that's just not yet being done? Because it would kind of be counterproductive Yeah, I think I think that's a lot of this stuff is so new That people haven't really rocked it yet in some sense even though Keeping up with Teejun house and his co-workers most recent developments was problematic for the preparation of this talk It's also a sign that Great opportunity because there probably haven't been that many presentations that talked about all these features so far but But yeah, I like a lot of projects my project isn't Up to point nine yet, but when we get there I think there are real opportunities to use all these observability and figure ability features to make things Better or of course worse. I mean if you just say oh, I want all my all my k-workers in separate pools And I'm gonna Move everything out of case off the RQD. You'll end up making a mess. What you really need is tasks to characterize your workload and It's performance and there's no substitute for doing a lot of work no matter how many Gives you more rope to hang yourself with at the end of the day Test test test. Okay. Cool. That's is working. All right. Hello everyone Thanks for coming to this talk. I've titled the talk a sequel approach to exploring off objects It's like the start of an idea. I've been pulling on I'm gonna present some of what I've been working on There's a lot more to it, but so this is just like the Genesis. I Think I've shown it to a couple people and they either think it's crazier Stupid or awesome. So, you know, you'll have some opinion on it But you know, please suspend your expectations for a bit. It's a pretty small group So just ask me questions in the moment if you want just raise your hand I'll take a question. You don't have to wait till the end or anything like that And if you'd like to reach me after the talk, that's I have a couple different emails. That's one I'm also on like X Twitter and all that other stuff, but yeah Okay, just really quickly who am I that's a photo of me. I Don't I have three young boys. I find that important to share. I live in California. I'm a student at UCSC Studying computer science. I also work at Google. I'm doing nothing related to this talk at all at Google and I'm also at scale for Nixcon, which was here the last two days. So if you were part of Nixcon, whoo I'll try to have a quite a long time, but okay, so I thought I wanted to start the presentation of like the journey that I'm on and Why I want to look at this problem and it's Like I wanted to share a couple insights that are driving my thinking so these are insights that are basically well known to us all as practitioners of software, but I think some of us maybe have forgotten the scope and Then grasp the scope So these insights are the fundamental fundamental motivation For my research specifically for my PhD research and I want to bring you along for the journey So basically starts with Eric Raymond who published the paper in 1999 where he described two philosophies for producing software The bizarre model or the cathedral model So in the bizarre model developments done kind of in the wild And the cathedral model is done closed source like monolithically I want to make the case that the bizarre model has clearly won out against the cathedral model And we've seen an explosion of packages and open source libraries by authors So on the left is a graphic of the number of available installations Prolinx distribution as of October 2022 So it's a bit old, but it's kind of this driving the same point and it's from the site Rappology comm that tracks multiple different distributions on the right There's a different metric specifically for Debian, but shows the explosion on a temporal dimension Starting from 2004 and you can see the rise of submissions of packages Basically, I just want to drive the point that there's a lot of software out there so on the left Nick's packages has Over eight, you know, I think right now it's over 80,000 packages installable and There's about 200,000 submissions for Debian These are also packages where the authors have gone out and painstakingly modeled their software put it for installation So, you know, just there's probably another order of magnitude more of just available soft like software out there Conversely another data point published by github has that which has become like the de facto open source Place to place your code is as of 2023. There's 300 million repositories out there 50 million which are public So there's like a proliferation of software this is a garbled mess and If you can't make sense of it, that's like fine, and that's the point So it's the the build and runtime dependencies for the Ruby interpreter, so I generated this graph with Nick's which models exactly all the build dependencies you need I Just want to convey to you that like softwares become immensely complex beyond our understanding and it's like hidden. I Picked Ruby because it's actually a very innocuous Program, it's available on every distribution. It's written in C It's has very minimal actually dependencies and yet that small dependency graph is in fact this So this insight is complexity so in the last two slides I showed that there's a huge the sheer quantity of software has exploded and Maybe not surprisingly as a result. We're building software that even when perceived to be simple is incredibly complex and requires many dependencies The final insight is that all those software has gotten more complex and numerous our ability to specify it The specificity of it has remained low as a proxy. Here's a graph of all packages in Debian The distribution and how they specify their dependencies So this is just something I wrote a script to grab and just parsed out like the version semantics and the the package metadata So pathic. Yeah Sorry, can you read the quite? Yeah, I don't think that's a million is it 100,000. Yeah This includes maybe Library, okay. Yeah, so on this graph I have about a hundred thousand on a previous previous graph It showed about much less than that for installable packages for Debian I don't have a great answer for that right now. This must include Libraries and stuff like that just doesn't count as for the other package installable. Yeah So basically the the point driving cross in this is three quarters of all packages installed by Debian are unversioned So the problem has become increasing complex and having more dependencies and they're in fact under specified You might ask yourself. Well, then how does this all work in practice? These packages work because and really only because the maintainers of Debian Diligently and manually ensure that the full graph of packages in the distribution build link and work together. It's an incredibly impressive feat and It requires an immense amount of knowledge about the needs of all these packages and It's basically encoded within this Single graph that you can install when you use Debian Interestingly, this cost is actually paid by every distribution out there You as a user though are ultimately locked into a single monolithic package set so that it all makes this possible So there's three big insights diversity complexity and specificity You can see from the previous slides that diversity and complexity are inherent to our modern softwares ecosystem and in tension with specificity As practitioners we have to tame the diversity and complexity to do our jobs But as the Debian package versions versioning story shows it's often too hard to pull off if we had better tooling to track software metadata Specificity could help us tame that chaos So that's kind of like the broad guiding theme of my research. So let's see what I kind of did with that Okay, where does this complexity come from I kind of sat and thought about that and And at what point is versioning really necessary? So maybe unsurprisingly I looked at shared libraries, which to me are the most fundamental data management unit in Linux So shared libraries effectively allow Linux programs to share code They do this by assigning by assigning names to chunks of compiled code like functions and global variables These names are known as symbols They were invented in the 1960s when disk and bandwidth were at a premium back then when it was a benefit to having to upgrade a single file and Whether for it was network bandwidth costs or you know quick security upgrades Unfortunately sharing code always creates problems and opportunities for weird disagreements Included here a nice quote for a co-author of mine from a previous paper Which basically says the the cause and solution to all of life's life's problems. I Mentioned all the nice attributes. I'll be it outdated for shared objects, but what are these problems his quotes referring to I? believe we've hidden an inflection point and there's now an opportunity to rethink and revisit many primitives and President today's stack. You don't have to read this quote. It's from Linus. I just wanted to include it You can't I don't know if it's totally eligible But it's just like you know, he's known for taking a spicy take on things This is just one spicy of his many takes on things where he is himself calling out that shared libraries are Basically a problem. They're unneeded. They're causing way more problems than they solve Specifically in this thread it was all about performance So yeah, it's like not a novel idea that I have and in fact, you know the Originator Linux also shares the same idea as a practical example. Let me ask you as this question Have you ever had a problem installing a Python package? Specifically, have you ever seen this error? That undefined message means that one such symptom of the problems of shared libraries can introduce Python is taking on the challenge of participating in a large diverse and complicated software ecosystem Most of which which isn't written in Python That's what makes Python useful and extremely frustrating I'm not here to solve that issue and if you're interested in that topic. I hope you attended nixcon yesterday And because that could be a one hopeful solution These kind of problems make me think of this comic which although originally intended to poke fun at house Some seemingly unknown open source library is keeping the software world afloat. I think fits nicely into this framing as well And it's a great photo. It fits into like a ton of different framings But hopefully by this point my take is you all agree that while software is getting more complex and expansive It's also suffering from low fidelity and that's because it's hard to specify what we want and understand What's present and work with the system? The majority of the tools that we've come to use and establish to run and link software and introspect them were devised in the 90s or even earlier These tool chains associate objects with code at once So we should really kind of look to that space to figure out how to tame this chaos. I Think there's a lot of opportunities. It's like rife for improvements because they're untouched. We're all focused way higher up in the stack Okay, so if we're gonna solve problems with symbol resolution again the process of finding chunks to satisfy the dependencies at runtime Then we'll need to take control over the sources of information about symbols and the code they refer to That information struck stored in a structure known as elf or the executable and lickable format Shared libraries relocatable objects binaries. It's all elf right now You know, we're at the southern California Linux expo It won't surprise any of us to hear that I'll be talking about the rest of this presentation. We focused on elf If you happen to be on other distributions like non-linux, I Found that if you squint hard enough, they're actually all the same and they follow the same Format so it's the same so Mac. Oh P. E. They're eerily similar if you squint at them elf has dominated the Linux space since 1999 when it was chosen as the standard and In fact as of 2022 Linux kernel 5.18 dropped support for the predecessor 8.0 out The elf object format had like solved a lot of real problems So we can specify varying isa's a bi byte encodings It was adapted to be very Configurable and adaptable and to support enhancements without breaking compatibility. It's highly configurable and over time though Has become more dependent on convention But basically if you could see the photo It's a series of like containers and there's two types of containers sections or segments and the reference to by Name or a pointer in a header table, so it's a very generic format and then each segment or section has more meaning Yeah, but it's not by can on the standard The format's comprised of like I said either sections Which is if you use relocatable objects, you'll have that or segments, which is the X rule code such as in a binary complicating matters further is elf files could have both and There's an overlapping between the two The granularity categorization of data and to name sections by convention such as is totally by convention So there's dot text dot data. That's just like different tool chains have specified that and they've become Their convention, but it become law And also like bss has uninitialized data for instance Conversely the execution view represented through segments is crafted with a lens though for a performance so it's It's tightly packed Executable code that can be mapped into process space and then run The L file was designed with trade-offs favoring performance and size It's evidence from the terseness of the file format, you know like hex editing the format is very difficult rife with problems and surprisingly we do it often the Format also contains a lot of data structures for performance So it has a hash map multiple types of hash maps It has a bloom filter and some of the other segments have like different optimizing coatings What is the state of present? The what is the state of the art like today if you wanted to look at your elf objects as Software system grows in complexity You'd imagine the tools we rely on to debug and optimize to keep pace oddly enough the landscape of tooling to introspect and work With elf has seen a consistent reliance on a traditional Unix tools such as read-off defect depicted here Which basically just dumps the raw ASCII representation of the file These tools have stood the test of time and one can argue they here to the Linux slash Unix philosophy do one thing well But it leads to cumbersome commands to extract meaningful answers to questions one may have about data The status quo for investigating binaries data has basically gone unchallenged In an era where data is growing at an unprecedented scale. We've seen software burgeon in size and complexity There is an impending need to reevaluate our tool set Performing more advanced analysis on elf at the moment requires software authors to familiarize themselves with the elf format Because they need to link in like lib elf and read it directly Each tool which seeks to ask questions like nuanced ones about their elf format have to do so on their own Leveraging at most a library which helps parse the file format Anecdotally, I found most software that needs data from elf to choose basically just to shell out instead to read-off So you'll have like some software and it just Spons a sub-process and does read-off and greps out the information it needs There also remains no comprehensive library that supports modification of elf files There are targeted tools such as patch elf That can change the interpreter and a few other things But so they have pretty restricted editing capabilities and the tool has seen its fair share of bugs from keeping edits in the file consistent a Common meme like amongst Unix programmers is that shell scripting specifically awk can solve anything There's a lot of truth to this in fact Brian Kennegan's book the awk programming language had an implementation of relational database an assembler an interpreter for a toy computer a graph Drawing language and a recursive descent parser Okay, so I had to do a lot of work with some elf files, and that was me. I'm like god. I'm really sick of like read-off or obj dump and While those tools stood the test of time and I can get the information I needed I was kind of seeing it felt like a mismatched pairing about techniques that like our best practice in the software industry And what we're currently doing today So the the questioning led me to explore the union of traditional data management principles and binary formats sequels the declarative language lingua franca for databases and its value propositions pretty well understood like It decouples understanding how the data is laid out and you can just to declaratively ask what you want There's an engine it processes that information and gives you the information you seek And it leaves the database to apply any optimization techniques when appropriate this is oh, yeah I Everyone's mentioning how they have to include AI in their talks So this was me asking some LLM to generate a logo depicting the Linux penguin and sequel light and I had to ask it many different times and this was Pretty good actually so yeah Go AI I guess okay, so to kind of like test my hypothesis. I said can I model the schema of elf in a relational model? This is the most basic schema that I could do at like to start to port the L file to the relational model I Mentioned earlier that elf was effectively a series of continuous code or data blocks and that's what I have It's nothing like too crazy. It's also not very helpful, but you got your header You got a content blob and a content blob and you have many of them That's what elf is and that's kind of what it gives you and then those contents have more meaning depending on the name And there's a lot of specialization there But like as a starting point, they're I some they're isomorphic I'll explain what this is. You don't have to read it. It's okay. It's not super legible, but I wanted to show I it's like oddly an unexplored space This is a Google search where I just wrote the term sequel and elf I have some generated content up there some blog posts and a repo that I'll get into in a section In a second those are the only like top hits There's a couple more that I that are there, but they're actually about sequel server by Microsoft Getting supported on Linux so they talked about sequel server ported to the elf file. So it came up with sequel and elf But other than that nothing So when nothing comes up for an idea you're pursuing I don't know you're either on to something very wrong or very right and it just had me thinking about it Okay, just to cover my bases. I also asked chat GPT 4.0. Okay, so it's the paid model Have you heard a good about a good tool to do this to combine sequel and elf? It came up with nothing and at best just kept recommending read elf and obj dump So AI doesn't know more about this than the rest of us. So for now our jobs are safe Okay, so this is the repo. Oh god I'll talk about it a little bit more, but I started to explore this in a utility It's called sequel elf It's on github. It's an MIT license. So it's a open source It has a much more complete relational schema for elf which will be on the next slide I could talk about that a little bit and you can query elf objects through sequel It's pip installable at the moment It's written in Python Which is a good thing and a bad thing because it's a little bit slow for very very large binaries But those are more at the like tail end of some quantiles that I don't rarely see And it only supports reading at the moment. I have a plan to try to think through updates The it's a code base. Yeah, and shout out to my buddy mark right there who helped Contribute on the project. So the tool offers a schema. It's pretty expensive. It won't fit in one slide I tried to show just a part of it. It's backed by sequel light The schema here is a partial representation like I said and some of the nodal parts missing are I support for real locations and Dwarf itself is like a whole other huge mapping of tables that's in When you build with debug symbols on Right now I did a pretty one-to-one mapping for many of the sections into tables With some minor abstractions to make it a bit easier when you're writing sequel Which I actually find to be a benefit of sequel so if a particular section is difficult to introspect sequel lets you just create a logical view Make the the better abstraction you want to work with and you jump off from there. I was able if I found an abstraction Common enough. I kept needing so one of them was the string table. I wanted to know the list of strings in my L file Well, I would I just made a new view with a new table that how all the list of strings present So yeah, it's been a pretty fruitful schema and I don't think it's gonna, you know It's it's evolving and I'm kind of pulling in more as I discover constant Queries I want to do often Well wish I knew was on that slide, okay How legible is that I can walk I'm gonna walk through the code so you don't have to super read it They're just examples and I'm gonna talk about some interesting ones The rest of this talk now is like five or six Anecdotes of like ways I've been using the tool when I'd make you appeal to your senses why you might want to use the tool so at the top is Getting the Above is the relatively simple query to assess whether there are any symbols in the whole dependency closure of the application Which may have been shadowed or interposed in the which is the word used in the compiler world So a shadowed symbol is one where the there's a symbol exported by two libraries Most often this is a bug unless you're doing LD preload where you're very very explicit about it If you've loaded two symbols, sorry two libraries and they export the same symbol like you're gonna pick one and the one you Pick isn't probably the one you intended Distributions check for this because again They have a single package set and they need to make sure no symbols interfere You could be library a and library b and you don't know about each other's code And if you just happen to pick the same symbol and later on someone decides to link you both they're gonna have a bad time so maintainers just like manually audit this and Maybe surprisingly unsurprisingly they write off ox scripts to just like comb through this and and test it out. I Was able to write a sequel query at the moment It's checking it on a list of binaries, but I'll talk later. You can run this against the whole distribution so you can encode the question you want as a declarative language question and Check the result on The bottom left is a sequel query from work Where I work I did replacing sequel elf In the audit wheel package so audit wheel what the Python's packaging story is kind of crazy audit wheels part of Python solution to the problem of how do we distribute compiled code? From one machine to another effectively. There's an RFC The community audit a base set of libraries and symbols present on a commonly used Linux system and deem those dependencies to be present always Any other disturb any other dependency must be included in the Python distribution format itself, which they call a wheel By not distributing every dependency and relying on some symbols to be present on the machine itself they then like Deem your package to work on most Linux's and in Python they call that many Linux so you get like this fancy tag in Any case parts of the code I want it we wanted to understand that I was looking at if the shared object was a CPython extension And whether it was for Python 2 or 3? So they had like a pretty expensive code block that used Whatever Python's equivalent to reading elf and they would go through the symbol table and check for this some symbol and see Does it match a or b just to get the answer is this extension of? Python to see Python 2 extension CPython 3 I thought it was nice. I could rewrite that whole thing in a pretty terse SQL statement I could run it on my command line. I could also there's a Python API and I changed in an auto wheel and I Found it more legible on the bottom right is the use case that was offered to me from one of my colleagues at Google They had some tooling that effectively broke when they assumed an invariant invariant that no two symbols could occupy the same address space With an elf file They had to write custom code to check this like they've hit it once and then it they had to write a custom binary That would check all their code, you know like with a declarative language a new issue comes up It's a bit more meta. You just write the query you want and then you add it and you can check your binaries And and that's an equivalent there One final example is a quick way to find the instructions associated with the given symbol So I have an instruction table. I added for fun You could even like because it's all lazy sequel the columns you want I could disassemble I don't know if I show that I do show the disassembly as well so you could just add the disassembler similar to how kind of obj dump and read-off can do and They'll you only pay for that cost when you see that column and Yeah, so on the left I use the symbol table itself and on the right as a demonstration of the tool beginning to use some the Dwarfs tables on the right is like me looking at functions in dwarf and calculating their size and Yeah, okay, so this is me showing I mostly sequel off works. Oh, sorry. Yeah, go ahead. I didn't see him That's That's one mode. I'll talk in a second. There's a way like that that's pretty potentially expensive and you might want to Memoize the result. So it has a mode where it effectively, you know dumps it out and then it's much faster and I have a Shitty benchmark that I'll show that shows it's pretty fast But yeah, it uses sequelize virtual table to start off Functionality which is a virtual schema so you could lay Metadata schema schema on top of elf files and access it that way Cool, so sequel doesn't have to work on one file Sequel elf, you know read elf works on one and that's a pretty like limitation the relational model is all about tuples So that so now we could think about data in terms of that format The schema easily can handle multiple binaries because I've had this extra column of the path of where the binaries from This next now lets you think about doing aggregate analysis Like read off is only like let me read this one particular file and I could think about doing analysis across your whole system Because that's what the relational model gives us So maybe I wanted to know what is the most used symbol amongst a set of read-off files like you know I want to do some I want to think about Some sort of like dead code elimination. Oh wow like in my distribution. No one's ever calling this library Maybe I should think about removing it. No one's using these symbols like so you can kind of do this after the fact ad hoc What's the most used shared object and so forth? also like I had this insight AR the Linux format for it just packages a bunch of like Object files when you compile it's kind of similar like there's a lot of overlap now where You can have a schema where you're packing in all these different elf Objects and the AR format's doing that. So yeah, I'll touch on that a little more. Yeah, go ahead Yeah, so the question is in an embedded world. Would this help me and analyze my symbols? being used and figure out which ones to Shut out or strip out if I'd like like to I'd say yes because an elf file has to say which symbols are exported and The another off shared object file or binary has to say which ones they're importing So you could get an exhaustive SQL query and say is anyone out of all these binaries did anyone import this symbol if not Then you know at least it doesn't need to export it. You'd have to know if it's being used within itself and then yeah But you could remove them remove it from the export set Which really cuts down on the surface at least of what people can link against which is like the first step Yeah, go ahead. Do you see this as purely like an introspection tool? Or do you see like as it like sequels a way of exposing like an alternative like binary format that like an interpreter could actually Yeah, okay, so the question. I guess that should be that question. I'll repeat anyways. Do I see this? Maybe being purely an introspection tool or replacing elf itself. I have dreams of the ladder this isn't I haven't implemented that yet, but Like it begs the question do we need elf? You know and I'll talk a little bit like there's a need for the performance at angle of it And if we can figure out that trade-off, then maybe we don't need it as well as much And then that's kind of where I was getting it here Ar like there's parts of the tool chain that can collapse as soon as you're working in the relational model It's like do you need ar ar is also just a sequel light table effectively with many binaries in it instead of one Okay, I think two more examples This is on the top Wait, what's on the bottom? Just dwarf examples. I covered it enough.  So I try not to put too much. I just kind of wanted to show some more interesting ones That one is like I have the relocations table is on the top and on the bottom is a an interesting like static analysis I wanted to see line count so dwarf has function symbols and it maps it to source code lines So you can kind of do what's the largest program? What's the largest functions amongst a series of binaries or in your binary so you can get like static analysis in sequel that's kind of neat like after the fact like as long as you compile the debug symbols on Okay, so how does this approach like in practice for performance? Well, since the space of possible queries is effectively limitless and sequel off can allow arbitrary complex queries It was pretty tough to do a performance benchmark against. I don't know read-off, but I chose Basically a straightforward example is a proxy and compared it. We're just doing a single scan. So I have I Chose just list all the symbols like so just one scan query That was kind of similar to read-off on the left is a graph where a sequel off is much slower So it's the green line the red line is read-off But interestingly you can Memo eyes so I can take that virtual schema and say well now dump like dump it persist it to disk and Then I could access I could use a C client now the sequel I'd see quite client I don't even have to use my sequel elf tool. I could use the ecosystem of sequel light which I'll talk to in a second to access this data and Maybe I'm surprising that wicked fast Like databases are fast. There's like the 1 billion row challenge and People are writing like crazy optimized code and they're still hitting the same as an engine. It's like the fighter jet So and it was pretty easy to persist the data You can use a C task which is a crate table select to effectively effectively memoize the data and It helps me avoid the pitfalls of having it written in Python now how problematic are elf files with symbols on The order of a hundred thousand it looks because that's when the graph really kind of spikes up for my sequel I did another audit of a distribution and found I think there was you know I normalized it a very small amount have over a hundred thousand files So like on in practice Linux distributions, it's gonna work surprisingly well where it kind of shit the bed was I tried applying it to some binaries produced at Google And those were on the work. They were like gigs huge size files and it didn't work very well there, but You know for most of us it's gonna be fine for now and you know if I need to we could rewrite it and Some more performant language Okay, I built another tool part of it just like layering the thing where you give it a docker image and it produces For that distribution the full final sequel elf metadata that you can explore So you run our individual images I ran it on Debbie and stable and then Debbie and Buster takes it's pretty quick So that's now a single sequel light file that has every binary as part of that docker image You can then I don't show that command But when you file a sequel light you can attach multiple files and they become Like effectively different namespaces and that secondary query you can kind of see The two different from statements the Debian stable or Debian Buster So I'm asking the question here, you know, part of the problems you have to come up with interesting questions So that sometimes I'm you know, that's like step two, but this interesting question was Which g-lib C's aren't present in both which g-lib C version Isn't present in both distributions So that meant if you built your software using some of these symbols with this version You can't work it won't work across both Debian distributions. I thought that was a pretty interesting quick Example to audit. I'm a library author out like What distributions do I know I'm gonna work on and this is like one way of discovering? Well, those distributions have no symbols like that's their intersection. This is another tool It's written by Simon Wilson. It's called data set you give it sequel light files And it gives you a really nice visualization to explore the metadata This was me uploading one of those Debian ones to his tool. It has a lot. You should really check out the project It's very it's really interesting. It's kind of meant for journalists to explore data and build websites But I have the showcase here is like sequel lights a huge ecosystem itself So we get to tap into that instead of having an art, you know I was gonna use the word archaic but I'd say neat more and it's not niche because it's all of Linux is elf but it's definitely a segmented ecosystem and Coupling with that sequel light gives you access to a ton of a ton more tools And this was an interesting one too. It's like well. I could just throw a website up. I Deployed it with some cloud provider and you can give it different sequel light files and instantly start visualizing and Navigating with a UI if writing sequels not your thing Visualizing the data set Yeah, I think someone asked a pretty poignant question. It's like where was I really going with this? I think the kernel Seed idea is I'm finding I'm jumping through hoops to replicate and Do what elf does and sequel light kind of does it well and things need to access what all that elf metadata The loader compilers linkers And they're all doing that on their own Individually in different ways and and and trying to counteract Performance by adding date like optimization did data structures like they're building their own engines Individually to do something like what a database would do so is there you know So this is like this sequel up to me is like a little seed and I think there's this like bigger broader idea out there also to pursue All right, thank you for the talk. I'm happy to take a few more questions Green shirt. Oh, it's query or one of the other Yeah, I'm kind of investigating right now So the questions looks like it has some good applications for malware analysis. Have you looked into integrating with OS query? Definitely, there's a lot of synergy between OS query and this OS query is trying to also Put a sequel abstraction onto the rest of your system And I think what could it gives you a nice temporal analysis like sequel elf right now is giving you in the moment view of a static file What's there and I you know, I'm looking to do it with OS query to see Well, you could kind of get this analysis over time And I think that would be that the dimension OS query gives you so yeah, and I think it The more you augment the schema, I think more malware detection analysis could be possible specifically with the instructions so right now it's Just a pretty simple dump of the each row is just one instruction. Yeah You said I got the mic I got the conch You said that the different binary formats are kind of similar if you squint yeah Are they similar enough where you could abstract them in the sequel? Schema and then present like a similar interface for you know other operating systems and make it a general purpose tool For everybody. Is that interesting cool? Yeah, I think so. I mean they all need symbols. I mean I've looked at we've written a little bit about the other Formats specifically Mako and PE and they all need to encode they all have code blocks They all have to define what symbols they need and where to find and what other shared libraries That's pretty much it And Someone's already forked this code and added support he added a few extra tables and he added Mako support It's not unified So it's like there's the elf tables and then there's the Mako tables, but the setup had lend itself It was a very small fork to add But definitely I think there's like a unifications right definitely some of the tables Part of this is to let you explore elf Specifics so you kind of want the specific schema for some of the elf Specific sections, but yeah Actually, I'm on the same lines. I was wondering have you looked at rather than using SQLite using Postgres as the underlying data store and query engine Yeah, I I kind of knew I wanted to head in the direction of maybe replacing elf The I think the interesting analogy more would be there's DB OS which is trying to replace all of the database with kind of Sorry, the operating system of the database access layer. So there's more synergy there, but to start I had this breadcrumb idea Let me lay on SQL on top of elf and SQLite It's just a little more simpler to work with and then it has a file So the analogy is like you had a file before you still have a file if I can execute it And I've just given you SQL introspection, you know, yeah But yeah, thank you for the comment. This question is a bit out of my depth, but SQL I think has roots in data log Which has like more expressive Query like syntax especially like recursive queries on datasets. Did you do any investigation about? implementing like a query Elf feature like using data log instead of SQL itself like Performance is a concern. What's sorry, what's it a log? I'm not familiar with it. Oh It's in SQLite. Is that we said no data log is like It's a query language that predates SQL and like sort of was its progenitor and then see It's like, yeah, it hasn't that prolog and data log Yeah, I just want to know if like SQL was a constraint for some reason because it's just ubiquitous or if it was It's more of the ubiquitousness of it and the lingua franca So yeah, I want to make the tool available to like many practitioners and there's again It's that ecosystem like I also chose SQLite. It's got The ability to share a file is really important and then tap into all the tools to access it and I didn't cover it in this slide But SQLite They publish is the most widely used software on the world. It's on every phone multiple times and And It's on your computer many times so they have it as like it's on the order of trillion or something about installable Which is pretty insane Yeah, I would assume that there's a lot of opportunity for like the on-disk format to be like efficient for like memory mapping and stuff to that regard I was wondering if you've been following the TVX Next re-implementation which has like a would store all binaries and a fuse backed storage and then I was thinking like that could provide a Like native view SQLite view even if the underlying storage was perhaps more optimal than the standard SQLite database Yeah, I've been following TVX, which is the next Re-implementation not that closely following it just more like when is it done and Yours what was the first question? Oh? It was more a common just like thinking like It could be go beyond SQLite like the native storage format which might not be optimized, you know totally into Perhaps having a better on-disk representation, but then providing different views into binaries whether it's being used as a executable or being loaded as a Yeah, I'm looking to just prove I'm suspending the requirement for performance right now, which I know could be a limiting factor for many but as Kind of like a research student I'm allowed to do that So I'm saying what if we didn't take that trade off of always picking Performance which always comes with the constraint of like terse and all that stuff what do we get out of it and then if there's a benefit there try to like add back performance or say There's probably cases where it's still You know you could relax the requirement for performance and I thought through a few ways to add performance You could always like have an index where you still have the memory like regions contiguous and map them in And still have that those sections to explore Did you have a question I'll take maybe it's the last one so To return to the original problem statement people shell out to read elf because parsing elf is painful But you're now shelling out to SQL elf Even though you do not love shared object libraries have you thought of You know publishing an API so that people could reuse this approach Without rating get another shell script to that calls a SQL elf totally So it's a Python library So it's an application as well as a Python library. So if your code's written in Python today, you can use it in your code base fairly trivially and if you can't if you're not written in Python you can at the moment do this step Memorizing it into a SQLite database and I think every language at the moment has a SQLite client that you could use and access the data that way So there's definitely very Good integrations possible without having to shell out. But what I liked is then you can always take that code block and Kind of be like what it's not working I don't know if you guys all been there and like you don't want to mental map it to something else and it's great You know, you're not in the same language, but it is nice to be able to copy that block on your terminal Kind of continue your investigation and then go back. So it's definitely a little bit of trade-off But yeah integrations with languages very possible right now. All right. Thank you everyone Right. Whoa, that's cool. Ah Hi everyone. Thank you for coming to my talk today. I'm sweet tea. I work at meta Primarily on the butterfess file system for the past two years before that I was at red hat. I Really enjoy working on the Linux kernel and today I want to tell you all about encrypted butterfess sub volumes, which is a project that I have spent a bit of my time at meta on It's one of the most exciting new features in butterfess in my humble opinion in several years And I'm really excited that all of you felt like coming into hearing about it So to as an overview first, I'll be talking a little bit about butterfess and where Encrypted butterfess sub volumes actually are then I'll be talking a bunch about the technical aspects of the work talking about the differences between different file systems and built-in disk encryption future goals for the work and then Practical usage of the encryption encrypted sub volumes. Oh, so yeah With that I'm curious how many of y'all use butterfess So about two-thirds very cool very cool and how many of y'all have contributed to the Linux kernel Cool, so about one-third very cool very cool awesome So a general sort of overview of butterfess Butterfess is in my humble opinion an advanced file system It's not necessarily a judgment on quality just a judgment on the number of features that it has So butterfess So a normal file system, you know, you've got a disk and you use it in your file system and it provides files and directories glorious worked well ten years ago still works pretty well for most use cases, but Advanced file systems have a couple of new features that can lead to data efficiency Or isolatability which older file systems don't have one of these features is called ref linking or reference linking It's where you take a chunk of data and you Tell the file system that it's actually part of two different files So it allows you to sort of de-duplicate your data Sub volumes are another great feature instead of having just one Disk that you mount and provides you with your whole file system with sub volumes You can choose which directory tree to mount at any given point. So for instance, you could have Every user on your machine can have a different user sub volume containing their personal user data and only that personal user data so that even without the Without file permissions that user can't read any other users data because that other users data isn't mounted at all just completely unavailable Along with sub volumes snapshots are a very cool feature snapshots allow you to take a sub volume and Grab a snapshot of how the files in that sub volume appear at any given moment in time So this is really great for backups. It allows you to take a Snapshot of exactly a point in time and save it elsewhere so you can easily roll back Package install or a change in your code that you turn out not to have went it after all So snapshots are pretty exciting But our fast also features check summing of your data, you know Discs are glorious and discs are very reliable, but at metascale sometimes discs go bad so We have check summing built into butter FS so that we notice when data on disk has gone bad And it's also useful for your own personal computers So that you know when to dig out the backups So overall I would call butter FS XFS and be cash FS the advanced file systems in the Linux kernel It's possible that I just don't know how wonderful and advanced other file systems are XFS doesn't have sub volumes and snapshots, but it's got ref linking which is pretty cool But our fs has all of these and my understanding is that be cash of us has all of these things too However for a long time butter FS has not had a good encryption story now We've got disk based encryption using device mapper using DM crypt Which is the underlying technology behind Lux And Lux is pretty standard on most distributions these days. However, there are When you're using butter FS on top of a Lux device it works great But it encrypts everything and because butter FS copies data every time you write There can be a little bit of extra IO which can slow you down a little bit um the way that Encryption for file systems is usually done in the Linux kernel Would have meant that we would need to give up ref linking and check summing in the past however as of a couple of years ago, we Started working on per sub volume encryption where each sub volume has its own encryption key Which also works particularly well for? Per user sub volumes That way every user can have their own key. It's pretty great Now at this point is the part where I awkwardly admit that when I submitted this talk It seemed like this work was about to go into the Linux kernel And it would be widely available and easy to use everywhere by the time I gave this talk six months later however How many of those of you who've worked with the Linux kernel before know that sometimes it can be a little difficult to Successfully come to a joint understanding and get your code reviewed and into the kernel So this is the part where I awkwardly say this stuff isn't actually in the kernel yet it's just a patch set on a mailing list of branch on github and It's not actually easy to use yet, but one more kernel release is what I've been saying for the past six months, so In any case There have there were some technical challenges to add encryption to butterfs that I think are particularly interesting and illustrate Some of the complexities of butterfs compared to other file systems, which maybe aren't Don't have those advanced file systems features that I was talking about So in in the Linux kernel, there's a sort of library Called fscript that provides encryption facilities to file systems It provides So there's an encryption area of the Linux kernel and then fscript is the glue that Connects your file system with all the different options available for encryption in the kernel It makes it easy to use It's commonly used on Android as I understand it so Probably at least half of you are currently using fscript in your pockets X4 f2fs f and ubifs are currently integrated currently have Integrated fscript so they all support encryption with this interface but fscript has been around for a while and so it's oriented at File systems that don't have those advanced features I was talking about So they have one key per directory tree and you can't have multiple keys in a directory tree This is a little awkward for butterfs given that you might want to have sub volumes inside of sub volumes inside of sub volumes Stack them all up Nest them all over But fscript doesn't currently support that Fscript also allows you to delete files without actually having the key This is a really important feature because otherwise you couldn't get your space back unless you reformatted your system Which I don't know about you, but I don't like reformatting my systems anybody anybody actually like reformatting of Course, there's some Kent anchors people in the world Keep calm and reinstall So the big advantage of using fscript instead of a lux disk encryption is that FScript allows you to only encrypt your personal data. So there are different threat models that you could treat That you could think about for your data, right? There's the threat model where everything about your data is important Even just the size of your file could give away some information about it and you know That's a perfectly valid way of thinking about it That's a perfectly valid that model to use and in that universe It is a good idea to use full disk encryption So you absolutely don't leak any information about your files at all however For me and for some other folks in the world perhaps even a lot of other folks in the world We really only care about our data being read. We don't really care about other people knowing how big our files are There can be a lot of files with the given size As long as you can't read the data or the file name. What's the harm? So fscript allows you FScript file systems just encrypt file names and data which allows for added Which reduces the amount of stuff that needs encryption, which means you spend less CPU on your encryption So I don't know how many of y'all have worked in the Linux kernel enough to know about inodes How many of you've heard of inodes? Okay, so about about three quarters very cool So the idea for fscript is that the in kernel inode structure embeds an fscript information Structure that gets stored on disk basically that information structure allows the fscript library to encrypt data in files based on where that data is in the file and Which file it's in now You can probably already see where this is going and why this Would have Prevented this would have forced us to give up for ref linking because if you've got data in two different files and It's encrypted With this scheme then on one side you're trying to decrypt it with this file info and on this file You're trying to encrypt it with this file info, which is different so Without making changes to fscript we couldn't Reflink encrypted data together, which would be a bit awkward Also as I mentioned butter fs likes to use nested sub volumes which makes It sort of important to have different keys at different points in the directory tree and Finally, it's difficult to do check something if the file system Never actually can access the encrypted data, which is the direction that fscript is moving in so this is a bit awkward and requires a bit of changes to fscript and Figuring out exactly what those changes to fscript should be has been a bit of a project The overall vision for butter fs encryption is that instead of Encrypting data based on what file it's in you encrypt based on what extent it's in now if you've worked with files Systems you might know that File systems usually store the information for a file in some actual Extent on the disk which serves as a sort of indirection layer To allow moving the data around or more efficiently packing the data So the idea that we came up with is to store the The fscript information alongside those extents instead of those inodes that way if you've got two files pointing at the same Extent by reflinking They both can successfully decrypt the data given that the key is the Additional information combined with the key in order to decrypt it is stored right there This does mean that it takes more metadata space than for older file systems But it means that we can reflink so by and large for butter fs. It's a win to do it this way We Sint up the first version of these packages with one design back all the way in October of 21 We we were using a Minimal set of data stored with each extent and it was pretty decent It had some security risks and so as it should have been it was odd I worked on this a lot and eventually we came to an understanding that the security holes are too bad And it was a bad idea in November 22. We sent out a second design. That was almost entirely That was largely my work Using trying to pull down the inode information directly on to the disk this was Elegant in some respects and in elegant in other respects and so the maintainer Decided that this approach wasn't working either and so in September of 23 Which was about when the call for proposals for this conference was due We came up with a third design my team lead Joseph Bacic and the maintainer worked together to come up with a design that everybody agreed on and And so my packages were amended greatly and new versions of the packs that were sent upstream Unfortunately, it means that we can't have nested sub volumes right now, but we can one day in the future The effort was to try to get it into the kernel sooner and then add this additional feature later and Unfortunately, even though it seemed like it was one release away for the past six months. It still hasn't gone upstream I'm still really excited about it and I'm still of confident that it will happen in the near future But it Hasn't happened yet. So the idea here is that we're storing sort of a Where we're storing both information along with the inode and also information down with the extent So The inode is storing what key we're using So if two inodes want to reflink together, they have to use the same key This does Provide some advantages when it comes to security So that two users who happen to have the same data don't end up using The two sub volumes that have the same key don't end up Leaking information if only one of them is mounted So It's got some merits. It does somewhat restrict Quite encryption options you can use And we're up to version 5 coming out soon on the mailing list and it still hasn't gotten in but hopefully when we're released I Evenkilly But this addresses all of the difficulties that I talked about it doesn't allow changing the keys yet And you might conceive of wanting to change the keys Let's say you have a subvolume That serves as the base for all of your user home directories you might want to take a snapshot of that and then give each user their own key and Either re-encrypt or use the old key to access the common data across all of the user directories Unfortunately, we don't have support for that yet, but it's possible to add it fairly easily We also came up with a way to Check some the encrypted data which is very important for better FS So that you can tell if your data's got encrypted on disk And by using all three elements to encrypt instead of just two elements it allows reflinking and will Eventually allow reflinking between Any number of i-nodes so it's got a lot of potential and I'm really Excited for it to go upstream soon and There's still some work to be done here Be cash FS is the wave of the future According to some people how many of y'all have played with be cash FS So about a quarter very cool Be cash FS Has some great features and I've really enjoyed playing with it. I really enjoy the there being more file systems with subvolume features in the kernel so that we can build common interfaces and Spread the love of subvolume swider But be cash FS doesn't actually use FS script right now it also only has one encryption key profile system and Everything is encrypted. You can't delete stuff if you lose the key, which is a little awkward However, there are some features that it has that FS script doesn't yet have FS script does not currently allow you to have authenticated encryption. So authenticated encryption is sort of like a more advanced form of check summing You take your data you take a key and you get out your encrypted data plus some authentication tag that You can only derive if you have the correct key So it leaks absolutely no information. I'll check some even if the could either be spoofed if it's a check some of encrypted data or You could Find out what that data is if it's a check sum of unencrypted data. So authenticated encryption Nicely solves these problems by only allowing you to verify the data's correctness if you already have the encryption key So this is a very cool feature. I think be cash FS is doing wonderful work in using it but it does mean there are fewer options for encryption algorithm and Different companies different countries have different requirements for encryption algorithm So there are some there's some trade-offs between be cash FS and better FS Another Option that you've probably heard of that I talked a little bit about was Lux. So Lux does allow Authenticated encryption also if you use the DM integrity target also It still only allows one encryption key per file system or block device. Obviously everything's encrypted Which again means you can't delete stuff if you don't have the key But it does allow you to do authenticated encryption As I mentioned and it allows you to change the encryption key, which is a really cool feature It means that if you lose your key you Can say this key is no longer valid and not lose all of your data You can also be encrypt with some newer and fence your encryption algorithm if you're existing encryption algorithm Turns out to be insecure now. I believe Lux is yes. I What um I Believe the technology is technology So technology is pretty cool Very exciting So how many of y'all have had an exciting experience with displays on your computers Cool and how many of you have deleted something that you didn't want to delete and How many of you have reformatted a disk that you did it mean to reformat? Good times good times Have any of y'all actually used the Lux option to re-encrypt your data Very cool very cool. It's a lot more than I expected very cool very cool and How often have you changed your keys? Yeah, it is a bit of a pain right you either need to keep both keys around or you need to Spend the CPU times and the IO time to read all your data and re-encrypt it. So it is a bit of a pain technology Different technology, so it goes Yes So the question is does this have anything along the lines of access control lists? So my understanding is that ACLs are more or less distinct. So this revolves around Having an entire file system directory that is only visible to a User if they successfully load their key So when they load their key, however, the entire set of file system features is available So if you've got your ACLs stored as you normally would with the file system Those would be available now that you've decrypted it. Yes So that's so the scenario being described is basically every combination of two of Some number of three users wanting to access different files being able to access different files So there are some files that only a and b should be able to see some files only b and c should be able to see some only a and c I see Definitely definitely so the idea is that pharmaceutical companies sometimes collaborate and sometimes don't want to collaborate And we don't want to leak information between Companies that don't want to collaborate Indeed indeed. So Unfortunately, I can't come I have not thought about this very much You would need eight partitions with Luxe with a butterfuss based approach. You could still have eight sub volumes for every combination here That is a good point so While I don't have a good solution other than a sub volume for every pair that went to every set that went to collaborate With a Luxe based partitioning scheme You have to decide how much space you're going to use for each of those partitions at formatting time with a butterfuss Sub-volume everything is being stored in the same set of backing discs So it's a lot more flexible and if you delete some space from one shared sub volume Now all the rest of the sub volumes can use that newly freed up space. Oh I can my understanding is that there's some Technology to take one single encryption key and split it up into many encryption keys I'm not a cryptographer. So don't ask me how but Such a technology could easily be layered on top of using butterfuss sub volumes To provide exactly the sort of shared access controls that you're talking about. I believe When one key unlocks all the sub volumes that you're supposed to have access to each with their own different key and that I believe allows the sort of Some subsets of Users can access each different sub volume Yep, it is the case that right now you can use normal file system partitions and that's a Reasonable solution in the current world, but definitely Encrypted sub volumes could be used in this fashion also So it looks like my technology is properly technology now so I will Charge forward with the rest of my slides Yeah, so we were talking about Lux it's great it encrypts everything Sometimes you don't need everything encrypted sometimes you care about performance more than you care about encrypting everything So that's why FS script might be a different choice for different Applications than Lux So we talked about those two options and how Key changes is a very cool feature and I definitely hope to use it Hope to integrate that into a butterfuss encryption one day soon So there's a fedora proposal to maybe use butterfuss encryption one day. The idea is that Some laptop OEMs have requested a way to load a encrypted image onto a disc that they're For a laptop that they're sending to a company common encrypted disk that way everything is encrypted then the company can set a new key for their own personal packages that they want to install on the computer and Then sets up their home directory templates and then the user can set their own new key for the home directory Possibly with some sort of escrow so that both the company and the user can read the user's data because users Sometimes lose their keys and really didn't mean to It's probably a bad idea if your user loses their key and loses their past three months of work stored on their computer So this directly requires key changing you start with an encrypted image You probably want to change the key on that encrypted image on a per company basis Then the company wants to change that so the OEM can't access it Then the user wants to change their key so that anybody else from the same company Can't access their data without having the full company key, etc The only bit of meta information in this talk is that we once had a vision where we would do something similar And we may want to do this one day in the future where we install an unencrypted package into a sub volume We usually run surfaces inside of a container inside of a sub volume for isolation purposes So if we install an unencrypted set of binaries Then we could change the key on the sub volume so that everything written by that surface To disk is encrypted. No chance of somebody forgetting to call the encryption service before writing to disk However, we've decided to go with a different solution for now, but there but our fast encryption is a Feature that has wide applicability and we may find an application for it in the future or change technologies And finally there are some companies that just believe in changing your password every so often And this would allow you to change the password our key on your sub volume. Well still Which can't currently be done with the about our fast encryption proposal as it is now So that's like the technical overview of how this is all put together and why we care about it Now we come to the part where I really wanted to have a demo, but I I'm a Running Mac OS and my virtual machines broke with an update this morning. So that's a bit awkward But I Mean it's what I get for using a sex for kernel development, right? Also true So This is if you download the patch set off of mailing list build the kernel and Interact with the keys Directly with the FS crypts tool you can set up encrypted sub volumes right now Obviously, it's still the early days. So if you're an early adopter, we appreciate your efforts and hope that you don't lose any data There there is definitely a Stabilization period while we don't know of any bugs You know, everybody knows how software without bugs Doesn't exist. So Yeah But it whoops it shouldn't Once it lands upstream in the kernel It should just be a matter of installing the new kernel Installing the FS crypts tool that interacts with file systems And then a very small amount of changes to your system D services in order to ask In order to make it ask for a butter FS key instead of just a locks key and that will load it into the kernel key ring and Then butter FS will unlock the master the like root sub volume Assuming it's encrypted with that key and then it should be easy to integrate Potentially with system D home there or some other Login surface in order to unlock your home directory as part of logging in So once this actually lands in the kernel, there's very little user space changes needed to use it And I definitely have a hope that one day all of the Fedora users in the room will be able to pick between Lux or butter a fast encryption when you install or perhaps be cash a fast encryption. They all have their merits So, yeah, how many of y'all actually use Fedora? Okay, a lot of Debian nubuntu users a fair number a fair number Sousa now, I'm really curious about what the rest of you use Of course Of course next OS is also an excellent choice. Um, so yeah It's true and I I really like next so I don't know why I didn't think of it Cool, so unfortunately that wraps up my talk about upcoming real soon now features in better FS Thank you And we have a bit of time for questions, so I see a question back there So my understanding is that there's a big limitation with like FS script type things where the metadata is remains unencrypted Has it been had to read any thoughts to Adding in something like compose a fast or Euro fast to maintain the metadata So you can have both encrypted metadata as well as per file encryption. Oh, so You're asking about the possibility of encrypting metadata Sort of like be cash of us does So that's quite possible For butterfuss specifically it's very difficult Because we store all of the file systems metadata in a single metadata tree So it's not obvious what key you would use to encrypt each Files each block of data in that tree if you tried to encrypt each individual File metadata item Those items are so small that there's too much there could be too much of a risk of brute force Attacks on your key, I believe I could imagine a world where you Used an overlay FS type thing and stored metadata stored all the changes To your sub volume in a different encrypted File on butterfuss, and I suppose that could work. Yep. So that's a good idea. It should be easy to Integrate above the butterfuss sub volumes encryption support once it lands Yes, yeah, you you mentioned there was a restriction on having nested sub volumes with different keys Does that that doesn't prevent me from having two sub volumes and just mounting them in In apparent directory relationship in a regular file system hierarchy What like so what what were the implications of not having this restriction like what does that prevent us from being able to do? Right, so for nested sub volumes the idea is that you have a directory tree and then at some point in the directory tree You have another sub volume that looks like a directory So For FS script right now you can perfectly well have two different directory trees That don't overlap at all that each have their own encryption key. However if you Had your one directory tree and then you tried to access The new sub volume that looked like a normal directory the keys would mismatch and you would get to error You'd have to mount them separately in different parts of your file system hierarchy. So hopefully we can Loosen that restriction at some point. It shouldn't be very technically difficult to do that I just we haven't done it yet Question behind you my concern is ransomware. I missed a little bit of the talk at the beginning So we were hit for ransomware and my company I work paid for it. Okay So where everybody went crazy and it's been a crazy year securing everything so the question is Can this be done so I understand that this is done at the volume level Or a sub volumes level and I'm not an expert on bt-rfs. I run everything on zfs, but all my servers run bt-rfs So the question is whether the application itself is the only Entity that can decrypt the decrypt the data not the user. I see so it so the only Entity capable of decrypting or increase if we if we get hacked this Entity should not be able to encrypt my disk basically or But I guess if he has access he can do anything he wants, but I don't know in the ransomware scenario How can this help? I unfortunately don't think I follow your question in enough details to figure out a solution for it Right now. Let's connect offline. Sorry The exactly. Yeah, I see you know your point. Your point is right. It's very well taken. There is no way Can group owned volumes be opened and unlocked by multiple users? Yes, if you use some sort of key distribution scheme or a key derivation scheme so that multiple users all Have the same key they can all unlock a shared sub volume using that key. I Think my answer there is a derivation of your questions. So, thank you very much Are there more questions? So I think all of y'all for coming to my talk. I I'm sorry. I don't have actual packages and fedora repositories to tell you to install right now to get encryption But I'm excited for that day to happen real soon now, and I hope all of you try out better I've had encryption one day and Thank you for learning about it today. We're 20 minutes early. So yeah Can folks hear me? All right. We'll start in like another minute or so Just not obstacle. All right. I think I'm gonna get started Welcome folks to my talk appreciate you all being here You know pretty pretty nice audience for a cold and windowless room to present in and so Thanks for being here. I'm Dan Schatzberg. I work at meta work on the containers team but I also do a lot of work associated with resource isolation resource efficiency and Topic today is gonna be skedexed, which is the extensible scheduler class. It's a way to write schedulers for Linux I'm gonna get into background motivation, but before I get started like How many people have Written BPF how many people have Written their own scheduler or edited the Linux kernel scheduler Smaller set of people I'm going to cover both topics And and how they combine together to make it much easier to change the Linux scheduler It's something we care a lot about Very quickly, I'll cover kind of what is the CPU scheduler? What does it do? Very classically you have a single core. You may have multiple tasks in Linux terms I may use the term thread pretty interchangeably with tasks, but Means the same thing right some entity that I want to schedule And the scheduler's job is just sharing the core. You have one physical core You have multiple things that want to execute as if they are running on their own hardware And so the scheduler is deciding Which tasks to run next where they run all that sort of stuff Obviously this simple model has changed a lot in the last, you know, 20 plus years We have multiple cores, but that's not really that much more trouble. You have Okay, multiple tasks. You may have to move them from core to core depending on whatever's idle This is again the kind of core functionality of the scheduler Obviously, there's some complexity with moving stuff if you have caches You don't always want to move a task around from core to core because some of its data may be hot in the cache So you want to keep it on the same core. So there's all sorts of penalties for migrating things And this is just the like Very very, you know scratching the surface of all the various challenges that are involved in scheduling Quite a lot of different problems you care about the schedule. One is fairness. How do I make sure that each task gets the amount it should? various properties of optimization I want to make sure to Use the system resources pretty well Make sure the scheduler itself isn't taking too much CPU time and taking away from other stuff And I wanted to work on various different architectures across different workloads for for all of these different purposes And this is just a small subset right like power management may be a concern of your scheduler And you would want it to behave differently thermal management is another area That I haven't listed here schedulers kind of in some way or another involved in all of these sorts of things There are a lot of different constraints depending on the environment you run on CFS the slides may be a little outdated in a sense But the CFS has been the kind of default kernel schedulers the completely fair scheduler for many years now In the last year it got replaced by EEVDF which works similarly There are some differences, but I will largely talk about CFS is that's kind of Been around for a lot longer in Linux And this is the the kind of default scheduling class in Linux and It's called the off a fair-weighted virtual time scheduler, which is a wordy way to describe Something that tries to preserve fairness basically and like largely what it does it figures out for each task on a core How much CPU it It's gotten and scales that proportionally by the amount of weight So if you set niceness on a thread that is changing its weight in some way And it's able to scale like okay if you're supposed to have a high weight then you get more time on the core and CFS basically just keeps track of how much time it's given everything and Make sure that each one gets his proportional share So showing three different examples here all with equal weights if you have one task It gets 100% of the CPU two tasks 50% and this is kind of just the abstraction right obviously at any one time a course running a single task CFS is sitting there making sure to you know give everyone switch switch threads frequently enough to give everyone their fair share It's been around since 2007 so we're very close to the 17 year anniversary of CFS being in the Linux kernel As I said over the last year there's been quite a substantial change here to move to EEVDF, but Both schedules are fairly have a lot of conceptual similarities right there's effectively a scheduler per core some load balancing on top And and using weighted virtual time as a mechanism I Think the the like history here is pretty important I think because it like dictates a lot about the structure of CFS and Linux scheduling in general So this is I think like a 2007 era top-of-the-line server CPU you might see and all of its two cores and Well, you notice about okay. There's just two cores one L3 cache and The topology is pretty homogenous. You just have the two cores, right? There's no new more properties here necessarily The migration latency is the cost of communicating between two cores like fairly high at this time so a lot of what scheduling was developed around was keeping everything local right like stuff stuff should run on a single core and stay on that core and You know periodically you can do load balancing to make sure your system is well utilized, but Not a lot of thought beyond that Nowadays you have much more complex hardware Topologies, I'll use this is I think AMD terminologies core complexes and core complex dies But it's kind of chiplet architecture has become common across a number of different hard hardware companies Which is to say that you have you know a far more complicated topology than just number of cores sharing a cache You have potentially multiple caches on a chip and potentially multiple chips and enuma system Which creates some some a lot more complexity here, so Kind of now the way I typically view it is you have you know heterogeneity across the system different cores having different latency to other cores and Depending on which cores and where those are some things may be faster slower than in the past so you have on a die you may have certain Memory access uniformity the cache through core complexes It may be faster or slower depending on exact number here So these are two fairly recent AMD micro architectures. I know the picture is Probably too small to see any details, but Zen 2 and Zen 3 if you want to dig into details here So Highlight all of that to say like scheduling is you know The hardware has changed that puts a lot of pressure on our schedulers to like perform Well and in this kind of shifting landscape and one place that we struggle a lot with CFS is that it's really difficult to experiment Right like I run a lot of production workloads at Meta and I want to see what what if I change this property of the scheduler What's going to happen? It's hard right after like recompile my kernel after reboot Once the machines reboot may take a while before the services back up and running to its kind of ideal performance and Just a high iteration cycle for any of that Makes experimentation really difficult to change CFS and the kernel It's also just generalizable right like the same scheduler needs to work for my Android phone my laptop and my data center and that you know Sacrifices performance, you know in the name of generalizability And of course just the upstream process of working on on the scheduler is challenging You can't regress it across all these different environments is an understandably high bar for contributions and What it results in is you know a lot of different Scheduler scheduler patches end up being maintained out of tree. I know at Meta We we try to minimize the amount of out-of-tree patches we have for the scheduler, but nonetheless if you know we can save 1% Performance on a workload we're gonna find a way to do that so that ends up having to Be a maintenance cost and something that's difficult for us to often share with others I'm gonna very quickly touch on BPF. This is like not a Not really a BPF talk, but I will If you have questions feel free to stop me at any point and just let me let me know So BPF like at its core is like a kernel feature that allows you to run custom code That you've developed in in the kernel and injected at runtime The very early days it was like a generalizable way BPF stands for Berkeley packet filter. It was a way to do packet filtering and Custom logic that said okay, if there's this field in the packet then do this or something like that over the last Several years it has evolved into a much much larger subsystem You can use it for tracing and all sorts of things by sort of attaching to different functions in the kernel and running Arbitrary logic and figuring out There's some demos earlier today showing a bunch of BPF, but at its core you like write C code You compile that into BPF byte code User space loads that into the kernel and then the kernel is gonna verify that your code has a lot of properties that necessarily The the C compiler didn't catch right that you aren't accessing invalid memory that you eventually terminate Bunch of different properties so that you know with this code running in the kernel It's not gonna crash the whole system but at a high level it's like a jit in the compiler you're able to you know run arbitrary code inside the kernel and I'm getting to what skedex actually is I realize it's a little long in the talk to to get to the kind of punchline here But um skedex is really like allowing you to implement Scheduling policies right so what is the actual logic of your scheduler and implementing those as BPF programs that you can load at Runtime you can change them reload them. You don't need to reboot your kernel There's a whole lot of safety built into the system here. So if you load a bad scheduler policy and suddenly we see that say You know a thread is not getting scheduler scheduled or hasn't been able to run for a while The core core system behind it will kind of kick out your scheduler and go back to CFS or whatever the the default scheduler is in the system so The the iteration cycle is like much as you would run any system service or kind of user space Damon in the system you would now write your own scheduler and BPF load that with the Damon that that Injects the BPF code into the kernel to use a new new feature called struct ops And BPF and Now you have a new scheduler running and you can take over all all of what what Linux kernel scheduler is doing The really big piece for us is that allows us rapid experimentation So as I mentioned you don't need to do any reboot you just recompile your program and go This is a huge win for us trying to run across a bunch of machines if I need to reboot them all I don't even have to stop the running workload, right? I can just unload the scheduler. It'll fall back to CFS I get a new one. I will deploy it. The workload keeps running just as before DPI is quite nice. I know that's fairly subjective, but It's a lot simpler than the kind of the core Linux APIs around scheduling There's a lot of heavy lifting done for you already in the API's And as I mentioned you have a lot of safety here, right? So like BPF on the one hand make sure that you can't write a scheduler that like corrupts memory, which is nice And there's some watchdog that will disable your scheduler if you're not running some some tasks for Configurable amount of time and also there's just you know a key you can hit if you you need to kick your scheduler out If something isn't running well Another big win is that it moves a lot of the complexity into user space So load balancing is something like classically pretty complicated in the kernel and trying to figure out how much load is on each core How much load should I take away you have to play around with the fact that like using floating point is not something you Oftentimes have the ability to do in the kernel if you move all that logic into user space You can interact between user space and BPF to do load balancing a lot more flexibly Using standard debugging tools. I actually think this is a space the kernels gotten a lot better more recently There's this cool stuff like like BPF like drag in the ways to debug the kernel code That you couldn't in the past but it's really nice just to use like gdb right on a binary and debug how it works So it becomes a lot more easy to kind of figure out Okay, I need to add some more data to my scheduler have it X I want to know when it's doing this kind of event or something like that Have it bump a counter from user space. I can see that read it printed out those sorts of things come a lot easier And then a big thing is just like the ability to share scheduling logic, right? So as I said like if we have our own custom patch for for our scheduler And I want to share it, you know, okay. It only works with this version version of our kernel Can be a little tricky and and things change here There's the kind of core functionality we get out of skeptics is you have an API, right? It tells you what you need to implement to be a scheduler and you can share that Pretty easily people can load to experiment on their own machines pretty pretty easily All right next section I'm gonna get into like how to actually build schedulers of skedex I debated a little bit about like whether or not I should put code on slides And decided some of the code is short enough that it is worth putting on the slides to show exactly how short it is I made that decision before I saw how large the screen was so My apologies for people particularly in the back that you you may not be able to see things But you will get a sense of how large the code is I hope So very concretely like what do you do you you create a BPF program It fills out a struct with function pointers those function pointers are callbacks, right? So the kernel is going to call those functions at certain points during during the process of scheduling and You tell the kernel what to do, right? So those callbacks are things like task wake-up right like a task was blocked reading on a socket Let's say suddenly that socket has data. It is now Awoken what what do you want to do with it? What core should handle this wake-up and Q and DQ so when when a Task is runnable What do you want to do with it? And then all sorts of state changes of tasks you get notified of usually these are helpful for just You know accounting that you might want to do in the kernel know when something is runnable know when something's actuall