Source code for kSTEP: Characterization and Deterministic Testing of Linux CPU Scheduler Bugs. (OSDI '26).

Tingjia Cao, Shawn Wanxiang Zhong, Caeden Whitaker, Ke Han, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau

📄 Paper  ·  💻 Code (osdi26)  ·  🌐 Website  ·  📚 Study  ·  📊 Results

# 📦 Clone the repository (add `--branch osdi26` to reproduce the paper exactly)
git clone --recurse-submodules https://github.com/kstep-dev/kstep && cd kstep

# 💾 Install dependencies
./install_deps.sh

# 🐞 Reproduce bugs
# ./reproduce.py <name|all> [--run <buggy|fixed|plot>]
#   1. Checks out the buggy and/or fixed kernels
#   2. Builds and runs the specified driver (or all drivers)
#   3. Plots the results
./reproduce.py sync_wakeup

kSTEP Driver, Fix, and Output	Figure
sync_wakeup.c Official Fix: linux@aa3ee4f Our Fix: sync_wakeup.patch buggy.jsonl, fixed.jsonl
vruntime_overflow.c Fix: linux@bbce3de buggy.jsonl, fixed.jsonl
freeze.c Fix: linux@cd9626e buggy.jsonl, fixed.jsonl
extra_balance.c Fix: linux@6d7e478 buggy.jsonl, fixed.jsonl
driver_util_avg.c Fix: linux@17e3e88 buggy.jsonl, fixed.jsonl
long_balance.c Fix: linux@2feab24 buggy.jsonl, fixed.jsonl
lag_vruntime.c Fix: linux@5068d84 buggy.jsonl, fixed.jsonl
even_idle_cpu.c Fix: even_idle_cpu.patch buggy.jsonl, fixed.jsonl
local_group_imbalance.c Fix: fix_local_group_imbalanced.patch buggy.jsonl, fixed.jsonl
util_avg_jump.c Fix: fix_util_avg_jump.patch buggy.jsonl, fixed.jsonl
rt_runtime_toggle.c Fix: linux@9b58e97 buggy.jsonl, fixed.jsonl
uclamp_inversion.c Fix: linux@0213b70 buggy.jsonl, fixed.jsonl
h_nr_runnable.c Fix: linux@3429dd5 buggy.jsonl, fixed.jsonl

For driver development, please refer to AGENTS.md for recommended workflow and tips.

./checkout.py <version> [<name>] [--tar | --git]

• <version>: Linux tag (e.g., v6.14) or commit hash (e.g., 6d7e478, 5068d84~1).

• --tar (default): download tarball from kernel.org / GitHub (fast, one-shot).

• --git: add a worktree from build/master (multi-version dev, supports git log/git diff).

• Example: ./checkout.py v6.14 foo_buggy checks out Linux v6.14 under build/foo_buggy/linux/ and points build/current at build/foo_buggy/.

make [KERNEL=<name>]  # Build kSTEP rootfs (kmod + user). Trigger `make linux` on first build.
make linux [KERNEL=<name>]  # Full kernel build. Run this after Linux file changes.

• [KERNEL=<name>]: build directory name under build/; defaults to whatever build/current points to.

./run.py <name> [--num_cpus <n>] [--mem_mb <mb>] [--kernel <name>] [--label <dir>]

• <name>: Driver to run (see *.c files in kmod/drivers/ and kmod/drivers_new_bugs/).

• [--kernel <name>]: kernel build to run against (defaults to build/current).

• [--label <dir>]: subdir under results/ for output; defaults to a timestamped tmp_* dir. results/latest symlinks to it.

• See ./run.py --help for --topology, --frequency, --capacity, --debug, etc.

• Example: ./run.py sync_wakeup runs the sync_wakeup driver with default parameters.

• kmod/: Kernel module (kmod.ko) loaded at boot

  • drivers/, drivers_new_bugs/: bug-specific drivers (one .c per bug)
  • fuzz/: fuzz executor, op handlers, coverage, sanity checks
  • cpu.c: topology, capacity, frequency setup
  • driver.h: public API for drivers (task creation, ticking, cgroups, etc.)
  • internal.h and other top-level *.c: framework primitives

• user/: Minimal userspace (user.c) that mounts filesystems and loads kmod.ko

• linux/: Project-static kernel files (committed to git)

  • config.kstep*: Kconfig fragments merged into the build
  • cov.c, Kconfig.kstep, Makefile.kstep: scheduler-coverage instrumentation
  • *.patch: Fixes for specific bugs

• build/: Per-kernel build artifacts. See build/README.md for the full layout. Top-level: current (symlink), user (kernel-agnostic userspace binary), <KERNEL>/ per-checkout dirs containing the boot kernel, rootfs.cpio, and linux/ source tree.

• results/: Run outputs. See results/README.md. repro_<bug>/ and fuzz_<bug>/ are tracked; tmp_* are gitignored.

• scripts/: Python utilities for fuzz orchestration, coverage parsing, and plotting.