Efficient Scheduler Live Update for Linux Kernel with Modularization

Different workloads want different CPU schedulers, but the Linux scheduler is welded into the kernel, so changing it means rebooting — minutes of downtime on a server running tens of thousands of threads; Plugsched (Alibaba) uses the compiler's own call graph to cut a boundary through the kernel at function granularity, turning the built-in scheduler into a loadable module that can be swapped in a couple of milliseconds, with the scheduling state carried across by emptying every run queue through the old scheduler and refilling it through the new one.

Why this problem is worth solving

The component people most want to change is the one hardest to detach.

Replacing running code safely is a well-understood discipline with a hard limit.

What people did before, and where it broke

• Patch individual functions in the running kernel. Tools such as kpatch, livepatch and Ksplice are general, open source, and deployed on ordinary commercial servers. Where it broke. They target security fixes of under a hundred lines and have no mechanism for migrating data state, so they cannot express a scheduler change that rewrites hundreds of functions and reshapes run queue structures.
• Move the scheduling policy into user space. A prior system encapsulates policy in user-space processes with mechanisms for state, communication and action, making a policy swap easy. Where it broke. The scope is limited to a single scheduling class, every scheduling decision costs at least two additional context switches — roughly doubling latency by the original report — and installing it requires modifying and rebooting the kernel in the first place.
• Hook the scheduler with the kernel’s safe bytecode facility. A proposed patch set adds hooks so small functions can be attached to scheduling decisions safely. Where it broke. It is function-level, and the safety guarantee is bought by restricting development to specific interfaces and data structure types, which limits what a policy can express.
• Replace whole components, as microkernel and object-oriented systems can. Several research systems support component-level or process-level live update cleanly. Where it broke. They depend on properties Linux does not have — a microkernel structure, an object-oriented kernel, or a component that is already a separate module. One system updates the virtualisation layer live precisely because it is already an independent module.
• Update the guest kernel from underneath, or migrate the machine. A hypervisor can replace a guest kernel, and checkpoint-and-restore can move a workload to a host running the desired scheduler. Where it broke. Both need virtualisation, so neither applies to a bare-metal container host, and restore time grows with thread count — at the more than ten thousand threads common on a modern server, the measured downtime is at the minute level.
• Cut the boundary at file granularity, since the scheduler has its own directory. The obvious approach, and the first one tried here. Where it broke. Those files also contain close to a hundred functions and variables that have nothing to do with scheduling, and moving them out would mean editing kernel source — which defeats the goal of deploying to servers already running an old kernel.
• The gap. Everything general enough for a production Linux server was too small to express a new scheduler; everything expressive enough required a kernel, a hypervisor, or an operating system structure that production Linux servers do not have.

How a built-in subsystem becomes a loadable module

The idea

The boundary was never drawn, so drawing it is the entire contribution. Linux keeps the scheduler in its own directory, which makes a file-level boundary look free, and it is not: those files hold close to a hundred functions and variables unrelated to scheduling, and evicting them would mean editing kernel source that production servers are already running. The move here is to give up on directories and let the compiler answer instead. A plugin records the whole kernel call graph during the build, developers declare which functions the rest of the kernel may call, and a fixed-point traversal repeatedly expels from the candidate set any function reachable from outside except through a declared entry point. What remains is a closure — the kernel can only reach it through the declared interface — and on one kernel version it comes to 786 internal functions behind 96 entry points, with 94 functions ejected. Deciding after the fact where a subsystem ends, instead of accepting where its original authors happened to put the walls, is the same manoeuvre the flexible isolation work covered elsewhere on this site makes when it turns the choice between monolithic, micro and unikernel structure into a build-time knob rather than a commitment made years earlier.

State survives the swap because it is reconstructed, not carried. This is the part that defeats function-level patching: the scheduler holds hundreds of stateful structures, and a genuinely new policy may organise them differently — one design tested here splits a single red-black tree of runnable tasks into separate high and low priority trees. Prior systems either forbid data changes or attach shadow fields that the hardware must chase forever and the developer must maintain by hand. The observation that dissolves the problem is that every scheduling class in Linux must implement two callbacks, one to put a task into a run queue and one to take it out, and that the state of a run queue is by construction whatever results from enqueueing its tasks. So the swap dequeues every runnable task through the old scheduler and enqueues it through the new one, and correct state simply appears — with the split trees populated by priority as a consequence of the new enqueue rather than a translation written by hand. Threads that are asleep need no handling at all, since they will be enqueued by the new scheduler whenever they wake. Where the machine-learning checkpointing work covered elsewhere on this site spends its ingenuity on saving state faster, this one arranges not to need the saved state at all.

One function could not be redirected, and the fix borrows an exploitation technique. The routine at the heart of scheduling does two things: it picks the next task, and it performs the context switch. Redirecting it wholesale fails for a subtle reason — a task that goes to sleep inside the old version will resume inside the old version when woken, no matter what the jump at the entry point says. So it is cut in half at the switch point. The upper half, where policy lives, is replaced; the lower half, where execution resumes, stays where it was, shared by both versions. Reaching it requires adjusting the stack frame so the new upper half and the old lower half agree about its size, then overwriting the return address of the context switch call so control lands in the old code. Those are a stack pivot and a return-oriented jump — the primitives of memory-corruption exploitation, used here deliberately and in the same kernel that the continuous re-randomisation work covered elsewhere on this site is trying to keep them out of.

Following one scheduler swap from compile to run queue

Configurations are provided for two kernel versions and adapted by hand for others. This preprocessing runs offline and takes several minutes.

Why it works

• A call graph answers a question source layout cannot. Directories record where authors chose to put files, not what depends on what → but the compiler already computes, for the entire kernel, which function calls which → so a fixed-point traversal over that graph can find a genuine closure, letting the subsystem be cut out with no edit to kernel source and therefore deployment onto machines already running an old kernel.
• Run queue state is defined by the operation that builds it. Translating hundreds of structures between two layouts is exactly the work nobody can do generically → but every scheduling class must implement enqueue and dequeue, and a run queue simply is the result of enqueueing its tasks → so draining and refilling reconstructs correct state even when the new policy organises it completely differently, with no per-structure conversion code.
• Almost nothing that takes time has to happen during the halt. Downtime is the only cost applications actually see → so memory is pre-allocated, the analysis is done offline, and only stack inspection, entry point rewriting and the drain-and-refill remain inside the halt → which is why the halt is about 2.3 milliseconds out of 141 for the whole upgrade.
• Every processor is idle during the halt anyway, which is a waste worth reclaiming. The conventional approach parks every core but one and inspects all stacks serially → dividing threads into per-core groups puts the parked cores to work, and sorting the entry points turns each frame check from a scan into a binary search → together giving stack inspection an order of magnitude improvement over the tool compared against.
• A clear boundary tells you exactly what to redirect. A patch tool must diff object code to discover which functions changed, and check all of them → but once the interface set is fixed, only those functions can possibly be entered from outside → so only they need redirecting, and the safety check has a small, known, sorted target set rather than an inferred one.

What it costs (trade-offs and scope)

• The evaluation caps threads at about a thousand while the motivation cites more than ten thousand. Downtime is measured with the total thread count limited to roughly 1000, and stack inspection is separately shown to grow linearly with active threads well past that. The case made for the work rests on servers where checkpoint-based approaches take minutes because threads are so numerous; the headline downtime is not measured under that condition.
• Data shared with the kernel cannot change shape. Structures visible outside the module, and shared ones inside it, may not change size or alter the meaning of existing fields. New fields must fit in 64 bytes of padding pre-reserved inside scheduler structures, with a pointer into a pre-allocated pool for anything larger. That padding has to already exist in the running kernel, which is a real qualification on the claim of needing no kernel changes.
• Updates cannot be stacked. Installing a second module on top of a first is unsupported, so multiple changes must be merged into one. The production case study shows the consequence: an earlier feature had to be rolled back and reinstalled combined with the new one.
• Correctness of the new scheduler is the developer’s problem. The system guarantees the update operation, not the policy. The evidence offered is a standard kernel test suite plus two internal checks — replacing old function prologues with an illegal instruction so a missed call graph edge panics, and verifying shared symbols resolve to a single definition. The illegal-instruction test only catches edges that a run actually exercises.
• Some changes escape the boundary by design. A companion mechanism lets developers hand-add modified functions from outside the scheduler, and the paper states plainly that this violates the principles of modularisation and should be used only for minor changes.
• The conflict rule is printed backwards. The text states the deployment terminates when the set of functions patched by another tool and the set patched here have an empty intersection, which is the opposite of what avoiding a conflict requires. Read as intended it is a sound safeguard, but as written it is an error.
• The comparison against a patch tool can only use tiny patches. The 24 and 26 percent downtime reductions are measured on changes of a few lines, because that is all the compared tool can express. There is no baseline at all for the cases the system exists to handle.
• Parallelism stops helping after about six cores, because core loads are unbalanced and cores cannot all begin inspecting at the same instant. The paper reports this openly.
• Applications feel more than the downtime figure. A web server pinned to one core drops to 3 percent of normal throughput and takes 8 milliseconds to recover, with full recovery inside 60 milliseconds; across 96 cores the worst per-core drop is 36 percent lasting 4 milliseconds. All of these exceed the 2.3 millisecond halt.
• The second architecture is unevaluated and undescribed. An implementation exists for both major server architectures, but a footnote states that several techniques differ on the other one and are omitted, and every measurement reported is from the one platform.
• Deployment is broad but selective. More than 4000 production servers run it, described as a canary deployment, with the authors noting that servers running stable workloads without a need for new features are deliberately excluded.
• Configuration is manual per kernel version, supplied for two versions and adapted by hand for the rest.

The evaluation

Check yourself

Sources

The paper is “Efficient Scheduler Live Update for Linux Kernel with Modularization” by Teng Ma, Shanpei Chen, Yihao Wu, Erwei Deng, Zhuo Song, Quan Chen and Minyi Guo, published at ASPLOS 2023, pages 194-207, DOI 10.1145/3582016.3582054. The authors are at Alibaba Group and Shanghai Jiao Tong University, and the system is open source under the name Plugsched.

This explainer is written from the full 14-page text. Everything above comes from the paper’s own sections: the background on the Linux scheduler and its size and coupling, and the survey of live update approaches with the two-axis comparison of expressiveness against generality; the stated design goals of expressiveness, generality, short downtime with safety, and ease of use; the modularisation methodology dividing functions into interface, internal and external sets and data into internal and external, with its three principles and the fixed-point boundary analysis algorithm, the information gathering by compiler plugin, and the code extraction rules; the optimised stack inspection with its parallelisation across threads and binary search across sorted interface addresses, and the complexity comparison against the tool it is measured against; the function redirection mechanism including disabling write protection and the special handling of the central scheduling routine by splitting it with a stack pivot and a redirected return address; the data update design covering the classification of critical and non-critical, private and shared data, the rebuild procedure based on the two stable callbacks, the reserved padding and memory pool for new fields, and the stated constraints on changing shared data and on stacking updates; the correctness verification by illegal-instruction function test and symbol-resolution data test; the implementation notes on line counts, the memory pool, the companion mechanism for changes outside the boundary, and the conflict check against other patch tools; and the evaluation covering the seven change cases, the downtime breakdowns with and without parallelisation, the comparison against an existing patch tool, the scalability with cores and with thread count, the impact on two latency-sensitive services, the production fleet statistics, the two in-production case studies, and the discussion of applying the same method to other kernel subsystems.