Hi everyone, I'm Jake Hillian. I was hoping to present this with Johannesburg, but he hasn't
quite made it yet due to Deutsche Bahn delays mainly, but he should be here hopefully by
the end to say hello. We're here to talk today about a side project we're working on
involving concurrency testing using custom Linux schedulers. I work at Meta and I work on
schedulers, mainly custom Linux schedulers, so this is pretty related to what I do. Johannes
is an open JDK developer who recently had to spend a lot of time debugging a race condition.
So we hope we could put those two things together and we've got a bit of a proof of concept today
that we can show you and explain how it works to attempt to make these a little bit more likely
to occur, which should make them easier to debug. So Hizenbooks, I imagine lots of us are familiar,
you've got the same input, you hope for the same output, but instead you're going to crash.
This is not great and it's especially not great when it happens 1 in 10,000 or 1 in 100,000,
the 1 in the million invocations. As an application owner, debugging that from reports is very tricky.
We'll go for a simple example now, very simple because these things get complex in reality,
but imagine we've got some data being produced from a producer for it and we're consuming it in a
consumer thread. In our case, and in our example later on, there's an explicit expiry date on
that data, which isn't what really happens in production, more likely you've got some reference
to a pointer that you might clear in some other thread, all of these expiry reasons that that data
might no longer be valid at some point in the future. It doesn't crash, the vast majority of the time.
The reason for this is that schedulers are pretty good, but when that interaction happens,
when your machine gets a bit busy, when some processes get in the way that you weren't expecting,
when the network gets slow, all of these things can just add extra delay. So a large reason for
these conditions is scheduling. We see this, for example, RR, the debugger has a chaos mode that
supports to make these a lot more likely, too, but that has its own issues. What is scheduling
then? What do we actually do? In this case, we're talking about CPU scheduling. It's one of the
more common types. The problem we have, we've got many processes, likely in the order of thousands,
and some number of CPUs, likely in the order of tens nowadays, and we need to somehow make sure
all those processes work successfully on that CPU to share the system. The simplest way we might
do this is just a schedule process A, and whenever it stops, we'll schedule process B.
Unfortunately, that really does not work. There are classes of non-preemptive schedulers,
sometimes it makes sense, but the vast majority of the time we're going to need to schedule
B a bit sooner, or the issues we were talking about before, they'll happen more often,
network timeouts, all that sort of thing. So instead, we go over time, and we'll stop scheduling
A for a bit. B might not be ready the next time, we might schedule A again. We'll schedule B,
we'll schedule A, we'll flip back and forth, and we're doing this on the scale of many
thousands of processes, likely we've several ready at any point in time. On an actual system,
it might look something like this. We're not going to be able to look at any of the detail on
this chart, but on the left, in the y-axis, we have which CPU we're looking at, as we go across,
we're looking at what's happening on that CPU, whether a process is scheduled, the different colors,
the different processes, nor gets quite complex, but these are the charts super interesting. This
is a 612 Linux system, just running EVDF, that default scheduler, we can see processes are
darting around all over the place, they're coming in, they're running for a short time,
some of them are long running, they move about a bit, there's all sorts of complexity,
and this is even on a pretty quiet system. When you start looking at big systems, hundreds of CPUs,
all the interactions just get way more complicated. So when we look at our race conditions,
you're replicating this on your lovely deaf machine, you've got a 32-core processor,
it's nice and quiet, you don't want anything getting in the way of your testing,
the bug never happens, ever, it's a nightmare, you know it's happening, people are reporting it,
you're running the standard scheduler, and the bug never happens, you can try running stresses
in the background, and that might make it a little bit more likely, but the bug still never happens,
working on custom scheduler's at matter, I got to work with some scheduler's that are not too good,
which is great, it turns out when you write a schedule of yourself and you have loads of
configuration options, there are many ways to configure that scheduler badly, and I found one
another while ago, I was working on a service, I was writing a scheduler, I got the configuration
terribly wrong and the service failed, it really didn't work, but there were free parts to the service,
two of them hit massive timeout errors, but they came back to life, one of them crashed,
so 250 hosts died all at once because of my scheduler, it turns out this was a race condition,
someone was storing the value of a shared pointer instead of copying the shared pointer and see
plus plus for efficiency reasons and they got it wrong, so if there was a long enough delay in
scheduling the service with crash, this does happen in the real application, but it's so rare that
nobody would ever look at it, or even if you did, you would really struggle to replicate it,
so what if we wrote a scheduler that was deliberately bad, what if it was deliberately erratic and
got us into these states more often where these errors are likely to happen, that's what we
got a demo of today, but how would you write an erratic scheduler? Well, there's some options here,
you could write it in the Linux kernel, you might have a hard time doing that in general,
the scheduler is very sensitive, if you get it slightly wrong, your system will hit the soft lock
up the texture and immediately reboot, which is a bit of a pain, it's hard to do, if you get it wrong
in memory on safe ways, your system will crash even more quickly, and if you get it right,
you're still waiting, well, maybe in the tens of seconds for a K exec every time you want to change
your kernel, this is a bit awkward. Nowadays, we can do it in user space, you're
kind of supposed to talk about Java, he's got a project that I'm not going to give enough credit
in this presentation because I don't know enough about it, where you can write these schedulers
in Java, I'm more familiar with the Rust ones, you can also do it in C, if that's what you're
like to, and it's all because of BPS, which is the B, scared x, which is the, I think we're supposed
to call it a sex deposit, which is an interesting choice of logo we got there, and then this is
the additional logo on the right. This is a photo of running Greg, supposedly shouting at hard
drives, but there's a quote about putting JavaScript into the Linux kernel here, many similarities
between the EBPS, the way it runs in the kernel, and a virtual machine for JavaScript you might
have in your browser. Here's a photo of him looking slightly more normal, I think he'd prefer that one.
EBPS, we're not going to go into it, it's not super important how it works, but that there are
a few details that we need to cover just for the understanding. When you develop an EBPS program,
you're going to write your source code in some language, there's a few options we have,
it sees the standard one, rust works reasonably well, there's some sort of academic languages
you can choose as well, and then there's the Java Transfiler that your analysis got, which is quite
exciting. You can pull that into BPS byte code, it's like assembly, but it's its own language
that works on all the Linux systems effectively. We make a CIS call to BPS to ask it to load our
program into the kernel, you need a lot of privilege for this, it's a root only operation again,
now I think, it kind of got user for a while, but now it's all root. It goes through the Verifier,
the Verifier is a magic black box that's the post to make sure your program is safe in certain ways,
so you can't remember it in a bad way that will cause your system to crash,
you can't have unbounded loops that don't terminate because we're running this in the schedule
a hop-off, if you have non-terminating code there, you're in trouble, stuff like that,
it's a bit of a beast to work with, but once you're verified, you get jick compiled, loaded
into the kernel, you can look at sockets, network interfaces scheduling now, you're loaded as an x86
program, there's no arm, whichever system you're on, there's no further runtime basically attached,
and then you communicate with that, mostly using Cisco's at the minute, we're getting some new
stuff called Arena's which are more like map memory, and you can communicate back to user space,
so we can write an application across user space and kernel space, which is pretty cool,
so the general way we write our production schedulers is we write some rust that talks to the BPS,
and then the BPS runs in the kernel and makes quick scheduling decisions.
So that's BPS, how do we use that for scheduling? And recently,
you mentioned that it's kernel 612, we're now 613, so it's a pretty recent SCADAXT, SCADAXT,
it's the extension framework for jumping in as a scheduler from BPS space.
This is a tasian, the creator, there are a few key features, I mentioned some of the troubles
we're working in the kernel before, and the idea is that SCADAXt makes them better,
there's a magnum perfect, but it certainly makes them better, so ease of experimentation,
we have a repo with, in the order of 10 schedulers now, maybe a few more, the Linux kernel has
two-ish schedulers, even the old one has to be ripped out to make way for the new one, so we don't,
we don't have a lot of optionality in the kernel, but you can run many different SCADAXt schedulers on
your machine switching between them just by running a program and pressing Ctrl C, it's super easy.
Customisation 2, we can talk to user space, you can do basically anything you want in these schedulers,
sure, some of it has to avoid the hot path, and you've got to communicate with user space a little
bit, turns out that's not as bad as we might think, but you can make loads of choices, you can use
information from Nvidia RESTMI that the Linux kernel is never going to do, and stuff like that,
and finally rapid scheduler deployments, deploying a new kernel at scale is tricky, and we have to
get it to millions of machines, and it takes in the order of weeks to get that kernel out, deploying
a new scheduler can take a day, it's really easy, and running it and stopping it is also easy,
you don't have to reboot, so if we find out weeks later that our scheduler is kind of bad,
we can just stop it, and we go back to the default, and everyone's safe, we don't have to
err, we don't have to worry about how much we've broken all the systems.
In the SCADAXt scheduler, again, maybe don't worry too much about the details, but we have a few
bits that we have to worry about, on each CPU, we have a local phypho queue, it's just first in
a first out, and that's effectively read from by the kernel. If you've put stuff in that queue,
the kernel side of SCX will make sure it gets run, on that CPU in that order, quite convenient.
In SCX, we generally have global queue as well, when we write our own schedulers,
in this picture we got one, you can have a dozen, you can have as many as you like, and within
those queue, you can meet different things, so on some schedulers, we might have a different
queue per LLC, some schedulers, we have a different queue per how much we want to prioritise
the workflow, and various different things like this. The scheduler's job that we write in SCX
is to move things from global queues into local queues, and accept new processes, make decisions
based on them, and let them run in the order we like. To view a super simple scheduler,
in the Java side of this framework, first step, well, first step is the license everything
is GPL, that's an absolute requirement with BPS, which is pretty cool. License it's that,
we're going to share this constant of a shared DSQ ID, nice and easy. We'll create a shared DSQ,
which we need to be able to handle tasks in a more uniform way, handling it per CPU would end up
with separate scheduling issues, so we'll create that DSQ, and now we've got our queue, and that's it.
Next one, NQ. This happens when you receive a task that is now runnable, and you've got
a task ideally, you want to put it on a CPU, but if you can't put it on a CPU, we're going to
end Q it. In this case, we're using another K-Funk SCX BPS dispatch, we're taking our task,
we're putting it in our shared DSQ, we're saying next time it runs, it can have up to five
milliseconds, and then we're just passing through these flags. It's pretty simple too, so far.
And the final one is dispatch. This is what's called runnable CPU goes idle,
you have your CPU, it's finished doing whatever it was doing. It doesn't know what to run next,
because it's little queue is empty, so we just run SCX BPS consume from the shared queue,
which takes the task from the shared queue, and just runs it on that, that's CPU for us.
That's it, that's a whole scheduler. It's not a very good scheduler. We're using
five-fold queues everywhere, there's no priority for any processes, everything is completely equivalent,
which it turns out doesn't work very well, and there's also only one global queue, so if you're
in any sort of complicated CPU, that will really struggle. If you've got two sockets on certain
Intel machines, this will kill the machine, because their cross-socket communication is so slow,
that if you try and run the scheduler, you hit the soft lock up detector, before the skedets
think and get kicked out. It's normally very safe, normally skedets, if you don't schedule stuff,
it just gets kicked out, and you go back to normal, but the Intel machines are so slow,
you can't actually get kicked out, because that bit of kernel code can't run in time.
So that's quite interesting, but in the general case, you're pretty safe, this will run,
and then you can extend it as you like. Producing erratic scheduling orders. That's what
this was all about. How can we make our race condition fun more likely? We have a, let's see,
let's go first of all, this is the example. We have an example here written, I believe in Java
again. It's a super simple thing to crash, we just consume things from a queue that are only
valid for a certain amount of time. It's missing a little bit of the code to it, and I won't find
it, because it gets, you always need a bit of plumbing to make these things work, but effectively
we get a task come from this producer thread. We've set a time on it, that's just the limit,
and if we try and read it beyond that, we're going to crash, and then we just keep reading it.
On a quiet system, this is fine. This will run for days at a time, and it will never crash.
Even on a busy system, we haven't yet seen a crash, but it can theoretically happen.
We had to get quite simple with these examples to make them fit, basically.
I've got a video to show you from your harness that I'm going to have to talk over, I believe.
There we go. Okay, so we started with our schedule, we've got schedule over SH, which just
launches our schedule, with the correct arguments, samplesruncue.sh. Here's our sample script,
the Java Rage Show G. And we're also, we're getting some extra of the velocity out of it.
Every time we make a scheduling decision, we're printing it here. And the way we've set this up
is it's going to sleep things for just way longer than it needs to. We'll take runnable tasks
that would get a CPU immediately on a normal scheduler and not schedule them. For whatever amount
of time this is saying. So this is going between half a second and a second and a half of not
scheduling our tasks that could be scheduled. Then when it runs it, we run it for 80 milliseconds,
something like that, and it normally finishes. And we saw it crashed, which is pretty good.
This program, again, hours at a time, we've left it running on these machines, it doesn't crash.
It just never hits these edge cases, but those edge cases are there, and they can be hit,
and if you scaled this efficiently, if that Fred with the random delay was actually a network
request, and then your systems would slow that was curing on those, this would crash. So we've got,
we've got a lot of times where this could happen. If someone reported it, you wouldn't be able to debug
it comfortably on your machine. And that's it, we've got a crash. I think we've got a few minutes
where I can briefly scroll through the code. There isn't too much of it, surprisingly, again.
Let's go. So we go back to...
I'll take it back. Before I do that, have we gone any questions?
So the question was, are we running that in the CIO just locally at the minute? At this point,
this is very local. It's quite constrained, this scheduler, it only works on small machines
at the minute, we use a lot of those phytocus. It's very new, it's very early. What we were excited
about seeing was whether we could make it crash, and we can. So the next steps with this would be to
production, I said a bit more, get it able to run on a big service. That example, I mentioned earlier,
if I tried to route that machine, it's one of the new AMD chips, so it's got loads of LLCs,
it's all a bit complicated. If we try and run this schedule on there, it just doesn't work.
It gets kicked out. The machine survives, but it doesn't work. So we need a more complex hierarchy
in the scheduler, and then to interject the randomness. We also need some seeding and bits like that
to try and get it more consistent, and probably a bit of searching to find the right conditions
to make it crash. So this is still very early. We'll be happy about contributions too.
Have we tried it on an arm machine? No, but it does work. So schedule it in general, we have
tried an arm machine. It works fine. There's nothing super worrying about it, which is great,
because we've got a lot of arm to cover at the minute.
You do from the schedule. In general, for example, to the process memory, to see what help,
it has what testing purpose, it has these kind of bits, now I know that I have to
schedule it to get a CPUs like another process. So the question was about looking at the
memory of the process, there's a more information we can use from them to make a scheduling decision.
That's super interesting. We haven't looked at that yet. We can do the filtering at the minute,
it's based on parent pids effectively. So we were a little bit, the way we're running the
schedule is we schedule the whole machine, but we only care about messing up this specific process,
because otherwise we'll stop finding race conditions in the shell, and then we'll be in trouble.
So the reason we do it like that is just easier. We use p-pid at the minute, you can filter on
in other schedules, we filter on things like calm, process name, thread groups, or these things.
So that, but I've never seen the option of actually looking at process memory, that's super
interesting. We are doing some stuff where the application can tell the scheduler what it wants
in a more fine-grained way. Currently we just use niceness, which is a bit weak, it's not very
rich. So we're doing more communication from the process to the scheduler in our production
schedule, and I think that would be possible here too. We're running a BPF, it's four
privileges, you can kind of do what you want, which is cool.
It's an excellent question. Their question was about reproducing the crashes, and how we can
make that happen. The answer at the minute is, no, we don't have that. It's a lot of the goal of this
project, but when we were running through it, we started looking at how we could build this scheduler
to get rid of a huge amount of the non-determinance in the process. The way we saw we're scheduling
it, we were going to slow it down too much if we tried to get rid of too much of the non-determinance,
because we want to be in the position long term where we can run this on production applications
with out slowing them down to the point where they stop serving traffic. And that meant we
made some compromises. The main one is we schedule things on course pretty quickly now, when the
original plan was to go one-fred process, but it just isn't scalable at that point. So there's
definitely some work to be done to getting the seeded and making it more reproducible.
I was wondering about this scheduling point where you can decide to make this end. Sounds like
only when the process was the kernel, is the point that you can really do this schedule,
but if you have some divide, let's say, you increment a variable, you should be economy,
but you have the increment do with a fashion head, but just so how do you do to make things
or leaving everything? Yes. So the question was about effectively summarized when we can preempt things.
Anytime, it's good. We have full control over it basically. So we can cut the slices down,
which helps, but we also have a K-fun called a CXBFF kick CPU that kicks a CPU quickly,
which is pretty cool. How we'd integrate that as a different question. We haven't done it yet.
We're purely working with slices in a minute. So that does, sorry.
That does get the primitive scheduler to kick in and stop the process, and we will get these
into leaving eventually, but you're having a more, if you could look at the memory and see a bit
that's flipped, and then kick it, we have that option, which would be very exciting in the future.
I'm hoping that we've opened sked eggs for the world of testing, and that everyone will have
great ideas now, because I'm a scheduler developer. Your harnesses of open JDK developer that
likes schedulers, so it would be really cool for other people to see that schedulers are
available to them, and not completely impossible to write now, and use that in testing more widely.
Can you prevent this soft lock from killing Linux? You can let's say you want to explore all
possible schedules, which can occur in systems. There's two parts to that. We have two of these
kind of lock-up detectors. I glossed over it earlier, but sked eggs itself, if you have, we're given
a task that's runable, and you wait more than 30 seconds and don't run it, the SCX scheduler will
get kicked, and all those tasks will move back to the fair scheduler in the kernel. There's also the
soft lock-up detector, which happens a bit later, that if the machine isn't, I'm not too,
super sure on the details, I just know we hit it. If the machine isn't making reasonable progress,
and it's not much later, I think it's maybe 40 seconds, 45, and then it just repeats the machine,
and that one, I would say turning that off probably isn't super productive, because if you were to hit
that with any normal schedule without your scheduler, the machine would do the same thing.
The SCX one, we haven't needed to turn it off, because 30 seconds is such a long time. Technically,
if we were making kind of network requests, they could take longer to come back than that,
but for the vast majority of bugs, 30 seconds should be plenty. If you do want to change it,
there's a number in the kernel, and you can always recompile it, and that will get longer,
and that you've got to be, there's many systems that come into make that stop.
Yeah, that's a good question. The question was about more erratic behavior, instead of just scheduling
timing. The show answer is no, basically. There's stuff where we're interested in a memory
latency change on systems as they get more loaded. We haven't done any work to train calls like
yet, and it's not easy to do that with the SCX scheduler. There are ways to do it. You can kind of
force things to mess up their cashiers more often with scheduling decisions, and introduce extra
processes that do that too, but I think those races are a lot finer-grained, and we haven't
decided looking about yet. That's great. Thank you very much.