Timer Wheels and the Cost of Finding the Next Expiry

A kernel can have tens of thousands of timers outstanding at once. Most are short-lived: a TCP retransmission, a device command timeout, a scheduler slice. A few are long: a keepalive, a lease renewal. The operation that happens constantly is not “expire a timer” but “find the earliest deadline”, because the clock event device must be programmed to fire at that moment. Everything else is secondary, and the choice of data structure follows from that asymmetry.

The naive structures fail on different axes. A sorted list gives the earliest deadline in constant time but insertion is linear. A binary heap gives logarithmic insertion and logarithmic lookup, but every cancellation and every re-arm costs the same, and a kernel cancels timers far more often than it adds them: every completed I/O cancels a timeout, every received packet cancels a retransmission. A red-black tree, which is what the high-resolution timer subsystem actually uses, gives logarithmic everything and stable behaviour, at the cost of pointer chasing and a rebalance on each operation.

What the wheel buys

A hashed timing wheel gives up the guarantee that the earliest deadline is exactly at hand. Instead it partitions time into buckets of fixed width and puts each timer in the bucket corresponding to its expiry. The current bucket advances as time passes, and expiring a bucket means walking a list rather than finding a minimum. Each bucket’s list is unsorted, which is enough because every timer in it is due at the same moment. Insertion is constant time once the bucket index has been computed. Cancellation is constant time if the timer’s node is on a doubly linked list, since the removal needs no search. And the earliest deadline is found by scanning forward from the current bucket to the first non-empty one, which is cheap if a bitmap tracks which buckets are occupied.

The price is resolution. A timer placed in a bucket that covers a span of time may expire anywhere within that span, so the error is bounded by the bucket width. Because the kernel’s bucket width is measured in tick periods, the resolution itself depends on the configured tick rate: the first level of the wheel is one tick wide, so a 100 Hz kernel resolves it to 10 ms and a 1000 Hz kernel to 1 ms. A flat wheel with 64 buckets therefore spans only 64 ticks, which is the reason the production structure is hierarchical rather than flat.

The classic paper describes both the flat and the hierarchical form, and the hierarchical form is what makes the structure usable for arbitrary timeouts. With several levels, a timer far in the future goes into a coarse level. When the coarse level’s bucket becomes current, its timers are redistributed into the finer level beneath it. The total work is bounded by the number of timers, amortised across the cascading steps, and the resolution at the finest level is preserved for timers that are actually near.

/* A two-level wheel sketch: coarse buckets cascade into fine ones.
 * FINE_BITS must be less than the width of unsigned long, because the
 * fine bitmap holds one bit per fine bucket.
 */
#define FINE_BITS    8
#define FINE_SLOTS   (1u << FINE_BITS)
#define COARSE_SLOTS 64

struct timer_wheel {
    struct list_head *fine;      /* FINE_SLOTS buckets, each FINE_MS wide   */
    struct list_head *coarse;    /* COARSE_SLOTS buckets, each FINE_MS * FINE_SLOTS */
    unsigned long    fine_pos;
    unsigned long    coarse_pos;
    unsigned long    bitmap_fine;    /* which fine buckets are occupied */
    unsigned long    bitmap_coarse;
};

static void wheel_advance(struct timer_wheel *w)
{
    if (++w->fine_pos == FINE_SLOTS) {
        w->fine_pos = 0;
        /* One coarse bucket's worth of time has passed: cascade it. */
        cascade(w, &w->coarse[w->coarse_pos]);
        if (++w->coarse_pos == COARSE_SLOTS)
            w->coarse_pos = 0;
    }
}

The cascade is where the amortisation comes from. A timer inserted an hour ahead costs one list insertion in a coarse bucket, not a search through the fine level. It is moved down only when its coarse bucket becomes current, and by then it is close enough that the fine level can hold it. The work of the move is charged to the moment the bucket expires, and each timer is moved a bounded number of times: at most once per level.

The kernel’s own timer wheel takes this further than the sketch. Each level is clocked eight times slower than the level below it, and a level holds 64 buckets, so the coverage grows by a factor of 512 per level while the finest level keeps tick resolution. Nothing is ever moved down at all: a timer is placed in the level whose granularity matches its distance, and when that level’s bucket expires, everything in it is expired. The rounding that placement implies is the slack the structure accepts in exchange for never walking a timer twice. Expiry therefore costs one pass over one bucket, never a rescan, and the total work is proportional to the number of timers expiring rather than to the number armed.

Where the wheel is still used

The kernel’s original timer implementation was a wheel, and the structure survives in the timeout facilities built on top of the high-resolution timers. A socket timeout does not need microsecond accuracy; it needs to be cheap to set and cheap to cancel, because it is set and cancelled on every packet. A wheel gives exactly that, and the resolution loss is irrelevant when the underlying event is a retransmission measured in hundreds of milliseconds.

The high-resolution timer subsystem took the other path. It keeps timers in a red-black tree ordered by expiry, per CPU and per clock base, because the feature it was built for is accurate wakeup: a media player’s frame pacing, a real-time thread’s period, a device driver’s precise delay. For those, a bucket error measured in ticks is a defect, and enqueueing in time order is also what makes an absolute timer survive a change to the wall clock without being dequeued and re-armed. The tree is not the whole structure, though. A separate list per base holds the currently queued timers so that the expiry code can walk them without traversing the tree, and an idle base needs no timer removal from the tree at all, because the kernel records the next expiry as a time value rather than as a pointer to a node.

The two structures coexist because they answer different questions. The wheel answers “when should this roughly happen” with constant-time operations and an error bounded by a known granularity. The tree answers “when exactly is the next deadline” with logarithmic operations and exact ordering. Neither is a replacement for the other, and a kernel that used only one would be worse for one of the two workloads. The commit that introduced high-resolution timers states the reason plainly: the wheel was tuned for timeouts that are usually cancelled before they fire, and the attempt to extend it in place produced compromises on both sides.

The next-expiry problem

Finding the next deadline is what drives the clock event programming. The kernel must know the earliest expiry across all timers on a CPU so it can program the device to fire then, and it must do so every time a timer is added or removed, because the new earliest may be sooner or the old earliest may be gone.

With a tree, the answer is the leftmost node, which is a pointer walk of the tree’s height. With a wheel, the answer is a bitmap scan, which is a few instructions. With a sorted list it is the head, but maintaining the head costs linear insertion.

The interesting case is cancellation. If the cancelled timer was the earliest, the next deadline changes and the device must be reprogrammed. If it was not, nothing changes. The tree gives this for free by re-reading the leftmost node; a wheel gives it by re-reading the bitmap. A structure that required a full scan on every cancellation would be unusable, and this is the reason the timer API distinguishes cancellation from expiry and keeps the two on different paths.

Reprogramming the device is not free. Programming the next event is a write to a memory-mapped or MSR-backed register, so it is a store that may leave the core, and some hardware requires a read back before the value can be trusted. A kernel that reprogrammed on every timer insertion would spend a large fraction of its time in those writes. The optimisation is to defer: mark the device as needing reprogramming and do it once, at the end of the batch, rather than once per operation. The high-resolution timer code does exactly this with a per-CPU flag that the next event handler checks.

Expiry, and what runs it

A timer expiry is not a callback in interrupt context. Each timer base is split into a hard base and a soft base: a timer whose expiry must be honoured in hard interrupt context is run from the clock event interrupt itself, and everything else is queued to the timer softirq and run from there, which means it may not sleep and it runs with interrupts enabled. A driver that wants to do sleeping work on expiry must forward to a workqueue, which adds a context switch to the expiry path.

The softirq processes all timers whose deadline has passed, which raises a fairness question. If a hundred timers all expire in the same tick, they all run in the same softirq invocation, and the softirq budget may be exhausted before they finish. The remainder is deferred to ksoftirqd, as described in Softirqs and the Per-CPU Deferred Queue, so the expiries happen but later than the deadline.

The re-arm path has a matching hazard. A periodic timer that re-arms itself from its own callback can starve other timers if the re-arm is scheduled in the past. The kernel handles a past expiry by placing the timer in the current bucket, which means it runs again on the next pass through the wheel, and the restart limit of the softirq loop is what stops a callback that re-arms to an already-passed deadline from spinning forever. The same treatment applies to a callback that arms a new timer for the past: it is not rejected, but it is not given priority over timers that are already due.

Accuracy, jitter, and the floor

The achievable accuracy of a timer is bounded by the clock event device, not by the data structure. A device that can program an arbitrary absolute deadline in the future gives accuracy limited by interrupt latency, which is the time from the device firing to the handler running. That latency is set by whether interrupts are disabled, whether a higher-priority handler is running, and whether the CPU is in a state from which it must be woken.

A device that can only program a relative interval gives accuracy limited by the programming path: the interval is measured from when the write lands, not from when the decision was made. The kernel compensates by reading the current counter and computing the interval, but the read and the write are not atomic with respect to the counter, so the error is on the order of the time between them.

The floor for both is the cost of the interrupt itself, on the order of a few microseconds on a machine that is not in a deep idle state, and much worse when the CPU must be woken from one. This is why real-time workloads disable deep idle states: the wakeup latency from a package C-state can exceed the timer period, which turns a periodic task into an aperiodic one.

Three ways a timer goes wrong

A timer whose callback frees the timer structure is the classic use-after-free. The kernel’s timer API has a variant that guarantees the callback is not running when the cancellation returns, and another that does not; using the non-waiting variant and then freeing is a bug that appears only under load.

A timer armed from interrupt context on a CPU that then goes offline is the second. The timer wheel is per CPU, and a CPU going offline cannot simply abandon its timers. The kernel’s hotplug path iterates every level and bucket of the departing CPU’s wheel and moves each armed timer to a base that is still online, taking care not to race with a callback that is running at that moment; the destination is chosen among the CPUs the timer’s flags permit. The migration is why timer setup and teardown interact with CPU hotplug at all, and why a timer callback that is still executing when a CPU comes online again cannot assume it ran on the CPU it was armed on.

A timer that is repeatedly re-armed to a deadline in the past is the third. A past expiry is placed in the current bucket, so the callback runs again on the next pass, and without the softirq loop’s restart limit the cycle of run, re-arm, and run-again would continue within one invocation until the time budget ran out. The restart limit is what converts an infinite loop into a bounded delay, and the re-arm itself is the bug, not the expiry.

The relationship between this structure and the clock device is direct: the earliest deadline in the wheel or tree is what gets programmed into the device described in Clock Sources, Clock Events, and the Tick. The relationship to interrupt latency is the subject of Measuring and Bounding Interrupt Latency, where the tail of the distribution matters more than the mean.