In-Kernel Aggregation: Counting Stacks in a Hash Map Instead of Shipping Them

The previous articles assumed that the expensive part of profiling happens off the sampled thread: the handler copies addresses into a ring, a collector drains the ring, folds stacks, symbolizes, and ships the result. That design keeps the sampled thread’s cost to a bounded copy, but it does not keep the data on the machine, and the volume arithmetic in The Overhead Budget of a Sampling Profiler shows why that matters at fleet scale.

Kernel-side aggregation inverts the arrangement. The folding happens inside the kernel, in a map that holds counts keyed by stack, and userspace reads only the aggregated table. The sampled thread’s cost becomes a hash and an increment. The ring buffer, the collector thread, and the transfer of raw stacks disappear from the per-sample path entirely.

A map keyed by stack

The mechanism rests on a kernel hash map whose key can be a stack trace. When a program running in the kernel is triggered, it can ask the kernel for the stack of the current task, obtaining an array of instruction pointers, and then use that array as a key in a map of counters. The lookup either finds an existing entry and increments it, or inserts a new entry with a count of one.

The kernel’s stack representation is a fixed-size array of addresses, typically a few dozen entries. The size is a compile-time constant set when the map is created, and it is the same for every key in the map. A key that would exceed the limit is truncated, not rejected, so the deepest frames are silently dropped, which is the truncation bias described in Folded Stacks, Call Trees, and What Aggregation Destroys appearing at a different layer.

Hashing a stack key costs more than hashing an integer. The key is a few hundred bytes, so the hash touches several cache lines, and the comparison on lookup walks the same bytes. Compared with a user-space integer counter, which is a single atomic add to a per-CPU slot, this is expensive in relative terms; compared with copying a stack to a ring buffer and hashing it in userspace, it is cheaper, because it happens once instead of twice and does not touch a shared data structure across the boundary.

Per-CPU maps are the usual mitigation for the contention that would otherwise dominate. A single shared hash map serializes all CPUs on the same cache line when they increment the same key, which for a hot stack means every core contending on one counter. A per-CPU map gives each CPU its own copy of the table, so increments never contend, at the cost of multiplying memory by the CPU count and requiring userspace to sum across CPUs at read time.

The verifier constrains the hot path

Code that runs in the kernel must pass a static verifier before it runs, and the verifier’s rules shape what an aggregation program can do. Loops must be provably bounded, memory accesses must be checked against known bounds, and the total instruction count is capped. The practical consequence is that the aggregation program is small and branch-light: take a sample, request the stack, look up the counter, increment, return.

The bounded-loop rule interacts with variable stack depth in a way that catches people writing stack walkers by hand. A kernel-side unwinder that loops until it reaches a sentinel must either prove the iteration count is bounded or use the kernel’s own helper that performs the walk with an explicit depth limit. The depth limit is what the map key size must accommodate, so the two constants are coupled: increasing the captured depth requires a larger key, which increases the hash and comparison cost per sample for every sample, not just the deep ones.

Requesting a stack trace is itself a cost that the verifier cannot help with. The kernel must walk the current task’s stack, and for kernel stacks that walk is over the kernel stack format; for user stacks it is a separate and more expensive operation, because the kernel must read another address space, and doing so safely from a context that may be holding locks is delicate. The kernel exposes helpers that perform the walk and copy the result, and their cost is proportional to depth with a factor considerably larger than a frame-pointer chase in userspace, since each read may fault and the code must tolerate that.

Frequency, not bytes, becomes the budget

With aggregation in the kernel, the per-sample cost is a fixed amount of work bounded by the key size. The tuning parameter is frequency, and the budget arithmetic becomes simple: frequency times per-sample cost, with the per-sample cost dominated by the stack walk rather than the hash.

The advantage over the ring-buffer design is not that this cost is smaller; it is that this cost is the only one. The ring design pays the same walk plus a copy into the ring, plus the collector’s copy out, plus a hash and tree insertion in userspace, plus serialization and transmission. For a per-host profiler the difference is a constant factor. For a fleet profiler it is the difference between shipping megabytes per second per host and shipping a table of a few thousand entries per collection interval.

What is lost is per-sample detail. The map holds counts, not individual samples, so questions that need the identity of a specific sample cannot be answered from it. Attribution of a sample to a trace identifier, correlation with a particular request, and reconstruction of the order in which stacks occurred are all gone. Systems that need those keep a ring buffer alongside the aggregated map, sampling at low rate into the ring for detail and aggregating at high rate for shape.

Sampling triggers inside the kernel

The trigger for a sample can be a timer, a hardware event, or a kernel function entry. The timer and hardware-event triggers work as described earlier, with the program attached to an event that overflows. The function-entry trigger is different in kind: it fires on a specific kernel or userspace function being entered or returned from, which makes it an instrumenting profiler rather than a sampling one, with exact counts and a per-call cost proportional to the number of calls.

The distinction matters for overhead. A sampling trigger’s cost is bounded by the rate regardless of how hot the code is. A function-entry trigger’s cost is bounded by the call count, so attaching it to a function called millions of times per second produces millions of probes per second, each with the cost of the trampoline plus the program. That is why function-entry instrumentation is appropriate for counting rare events, such as a specific error path or a lock acquisition on a contended mutex, and inappropriate for profiling hot code.

A middle path exists for cheap counts: a program attached to a function can count entries in a per-CPU array without requesting a stack, which costs a few dozen instructions and is affordable at high frequencies. Stack capture is the expensive part, so the useful design is to count everything and capture stacks on a sampled subset, which is what produces the differential flame graphs that show a function’s cost by caller without paying for a stack walk on every call.

Reading the map and the aggregation gap

Userspace reads the map periodically, copying each entry and its count, then clears or snapshots it. The read is a batch operation over the table and costs time proportional to the number of entries, not to the number of samples, which is the whole point.

The gap between reads is a window in which the data exists only in the kernel. If the profiler process is slow, the window grows and the map grows with it, bounded by its maximum entry count. With per-CPU maps the maximum is per CPU, so the bound is the product of the entry limit and the CPU count, and the memory is charged to the kernel, which makes an oversized map a system-wide risk rather than a process-local one.

Entries that hit the limit are not counted; the map refuses the insert and the increment is lost. The kernel’s map API can report a flag indicating that an insertion failed, but a program that ignores it produces a profile that silently under-counts the rarest stacks, which are exactly the long-tail paths that a fleet profile is supposed to reveal. Reading that flag and exporting it as a first-class metric is the difference between a profiler that lies quietly and one that reports its own saturation.

What stays true regardless of where folding happens

Moving aggregation into the kernel changes the cost profile and the failure modes but not the statistical character of the result. The counts are still sample counts over a random process, the confidence intervals are still binomial, and the bias from non-uniform instruction cost is unchanged. A kernel-side profiler at 100 Hz is exactly as informative as a userspace profiler at 100 Hz with the same stacks, and it is less informative than a userspace profiler at 1000 Hz that can afford the transfer.

What the kernel placement buys is the ability to run at high frequency with bounded overhead and bounded data volume, which is the configuration continuous collection needs. It also constrains the clock: kernel-side timers can sample regardless of whether the thread is runnable, so a wall-clock or scheduler-based trigger can capture waiting time that a CPU-time trigger never sees. That capability is the door to the next subject, treated in Off-CPU Time and Scheduler Delay as a Profile.