Hi everyone, I'm Jake Hillian. I was hoping to present this with Johannesburg for a good
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, Heisenbergs, I imagine lots of us are familiar. You've got the same input, you
hope for the same output but instead you get a crash. This is not great and it's especially
not great when it happens 1 in 10,000 or 1 in 100,000 or 1 in a 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 thread and we're consuming it in a consumer thread.
In our case and in our example later on there's a 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, our
rather debugger has a chaos mode that's supposed to make these a lot more likely to, 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, like
the 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 be a bit
sooner, or the issues we were talking about before, they'll happen more often, network
time outs, 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. You 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 have 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 B-thirl
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. It all gets quite complex, but these sort of charts super
interesting. This is a 612 Linux system, just running a VDF 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 condition,
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 is a matter, I got to work with some schedulers that are
not too good, which is great. It turns out when you write a scheduler yourself, and you
had loads of configuration options, there are many ways to configure that scheduler badly.
And I found what I heard a 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 three parts to the service, two of them hit massive time-out 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, and someone was storing the value of a shared
pointer instead of copying the shared pointer and C++ 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,
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 detector 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 exact every time you want to change your kernel.
This is a bit awkward. Nowadays, we can do it in user space. You're hunting so
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 like to.
And it's all because of BPS, which is the B, scared-ext, which is the, I think we're supposed to
call it a sex-depress, 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 Brendan Gregg,
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 bike code.
It's like assembly, but it sits own language that works on all the Linux systems effectively.
We make a CISC 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
supposed 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 jet compiled, loaded into the kernel. You can look at sockets, network interfaces scheduling now,
you're loaded as an X86 program. There's no or arm, whichever system you're on. There's no
further run time basically attached. Then you communicate with that. Most of the using
Cisco's at the minute, we're getting some new stuff called arenas, which are more like mat
memory, and you can communicate back to user space. We can write an application across user space
and kernel space, which is pretty cool. The general way we write our production schedule 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? Recently,
I mentioned that it's kernel 612, we're now 613, so it's pretty recent. Schedule XT,
Schedule XT, it's the extension framework for jumping in as a scheduler from BPS space.
This is a tasian, the creator, a few key features. I mentioned some of the troubles we've
working in the kernel before, and the idea is that Schedule X 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 SCX Schedulers on
your machine switching between them just by running a program and pressing Ctrl C. It's
super easy. Customization, too. 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 schedule of deployments, deploying a new kernel at scale
is tricky. 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 Schedulet 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
Schedulers kind of bad, we can just stop it and we go back to the default and everyone's safe.
We don't have to worry about how much we've broken all the systems.
In the SCX Scheduler, maybe no worries too much about the D-cells, but we have a few bits that we
have to worry about. On each CPU, we have a local FIFO queue, it's just first in 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 queues as well when we write our own Schedulers. In this picture,
we've got one. You can have a dozen, you can have as many as you like, and within those queues,
you can mean different things. On some Schedulers, we might have a different Q per LLC.
Some Schedulers, we have a different Q per how much we want to prioritise the workflow,
and various different things like this. The Schedulers 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 job aside of this
framework, first step, well, first step is to license everything as GPL. That's an absolute
requirement with BPS, which is pretty cool. License it's that we're going to share this 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 Q, and that's it. Next one,
NQ. This happens when you receive a task that is now runnable. 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 NQ 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 flights. It's pretty simple too, so far.
And the final one is dispatch. This is what's called on a 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
Q is empty. So we just run SCX BPS consumed from the shared Q, which takes the task from the shared
Q, and just runs it on that CPU for us. That's it. That's a whole schedule. It's not a very
good schedule. We're using Firefox everywhere. There's no priority for any processes. Everything is
completely equivalent, which it turns out doesn't work very well. There's also only one global
Q, 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 they're cross socket communication
is so slow, that if you try and run the scheduler, you hit the soft lock up detector,
before the schedules thing can get kicked out. It's normally very safe. Normally,
schedules, 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 Q that are only valid for
a certain amount of time. It's missing a little bit of the code here, 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 a 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. Thank you. Okay, so we started our schedule. We've got schedule
over the SH, which just launches our schedule, with the correct arguments. Some pools run Q.SH.
Here's our sample script, the Java Registro G, and we're also getting some extra
of the bossity 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 run-able 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 kind of 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 of the 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 sufficiently, if that Fred with the random delay was actually
a network request, then your system's got slow, that was curing on those. This would crash.
So 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. So we go back to, before I do that, have we got any questions?
So the question was, are we running that in the CI or 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 Python cues. 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, 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, and 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's in general, we have
tried on arm machines. It works fine, there's nothing super worrying about it, which is great,
so yeah, we're a bit concerned, we've got a lot of arm to cover at the minute.
Can you do from the schedule? Can you, for example, go to the process memory to see if I
hope it has, what it has to improve, it has these kind of bits, now I know that I have to
schedule it to get a CPU slash another process. So the question was about looking at the
memory of the processes and what 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, 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 start finding race conditions in the shell and 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, all 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 BFF, it's four root 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
without 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 thread per 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 a schedule.
Sounds like the only one that process was the kernel, is the point that you can do the schedule,
but if you have something bad, let's say you recommend the variable, you should be on the
criminally with a fashion head, so how do you explain the meaning of anything?
Yes. So the question was about effectively summarized when we can preempt things. Any time,
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 SCXBFF Kick CPU that kicks the 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 preemptive 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 SCXBFF's 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, if let's say you want to explore all
possible schedules which can occur in systems than it will crash?
So there's two parts to that. We have two of these lock-up detectors, I got stover it earlier,
but Skedox itself, if you have, we'll give it 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, but you've got to be, there's many
systems that come in to make that stop.
Yeah, it's a good question. The question was about more erratic behavior, instead of just
scheduling timings. 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 that, 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 caches 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 started looking about, yeah. That's great. Thank you very much.