Concurrency Testing using Custom Linux Schedulers by Jake Hillion & Johannes Bechberger

New features of the Linux kernel allow us to develop our own Linux schedulers. This talk shows how anyone can write a basic Linux scheduler and use it, for example, to fuzz for concurrency bugs or optimize for specific workloads.

1. A ScyllaDB Community
Jake Hillion
Software Engineer
Johannes Bechberger
OpenJDK Developer
Concurrency Testing using
Custom Linux Schedulers

2. Heisenbugs

3. Producers and consumers
Producer Consumer
Best-before Best-before

4. Crashes on expiry
Producer Consumer
Best-before Best-before

5. Crashes on expiry - even in the Linux kernel!
Producer Consumer
Best-before Best-before

6. Scheduling

9. Work-Conserving
Responsive
Fair

10. Work-Conserving
Responsive
Fair

This is predictable.

11. ERRATIC TBD We need an erratic scheduler!

12. Work-Conserving
Responsive
Fair

13. Work-Conserving
Responsive
Fair

Not
Not
Maybe

14. Work-Conserving
Responsive
Fair

Not
Not
Maybe
This is not predictable.

15. Building our scheduler

16. eBPF is a crazy
technology, it’s like
putting JavaScript
into the Linux kernel 
Brendan Gregg
“
https://www.facesofopensource.com/brendan-gregg/

17. sched_ext
Ease of experimentation and exploration
Customization
Rapid scheduler deployments

18. Let's create our own
+ +

19. T0
CPU 1
Local
Queue
CPU 2
Local
Queue
Global
Queue
Scheduler
...
...
Scheduler dance
T1

20. @BPF(license = "GPL")
public abstract class SampleScheduler
extends BPFProgram implements Scheduler {

static final long SHARED_DSQ_ID = 0;

@Override
public int init() {
return scx_bpf_create_dsq(SHARED_DSQ_ID, -1);
}
}

21. @BPF(license = "GPL")
public abstract class SampleScheduler {

@Override
public void enqueue(Ptr<task_struct> p,
long enq_flags) {
scx_bpf_dispatch(p, SHARED_DSQ_ID,
5_000_000, enq_flags);
}

}

22. @BPF(license = "GPL")
public abstract class SampleScheduler {

@Override
public void dispatch(int cpu,
Ptr<task_struct> prev) {
scx_bpf_consume(SHARED_DSQ_ID);
}

}

23. Fixing a kernel driver scheduling bug
with scx_chaos

24. int hsmp_send_message(struct hsmp_message *msg) {
take_per_socket_lock();
msg_socket->send_request(msg);
while (!timed_out) {
resp = msg_socket->gather_response();
if (resp.ready)
break;
usleep_range(100, 2000); // sleep for
100-2000 micros
}
release_per_socket_lock();
}

25. int hsmp_send_message(struct hsmp_message *msg) {
take_per_socket_lock();
msg_socket->send_request(msg);
while (!timed_out) {
resp = msg_socket->gather_response();
if (resp.ready)
break;
usleep_range(100, 2000); // sleep for
100-2000 micros
}
release_per_socket_lock();
}
Defensive code gone wrong

26. int hsmp_send_message(struct hsmp_message *msg) {
take_per_socket_lock();
msg_socket->send_request(msg);
while (true) {
resp = msg_socket->gather_response();
if (resp.ready)
break;
if (timed_out)
break;
usleep_range(100, 2000); // sleep for 100-2000 micros
}
release_per_socket_lock();
}

27. Reproduction

28. “Normally we just add sleeps
and hope for the best”
-Anonymous kernel developer

29. Demo

30. scx_chaos helps to find bugs
due to invalid concurrency
assumptions.

31. https://github.com/parttimenerd/
concurrency-fuzz-scheduler
https://github.com/sched-ext/scx/tree/
main/scheds/rust/scx_chaos

32. Thank you! Let’s connect.
Jake Hillion
@jakehillion.me on Bluesky
https://matrix.to/#/@jake:hillion.co.uk
blog.hillion.co.uk
Johannes Bechberger
@mostlynerdless.de on Bluesky
https://mastodon.social/@parttimenerd
mostlynerdless.de