Sampled Allocation Profiling and the Cost of Interposing on malloc

CPU profiles count where time is spent. Allocation profiles count where memory comes from, and the second question has a complication the first does not: memory that is allocated and freed in a loop is cheap, while memory that is allocated once and retained for the life of the process costs the same to allocate and vastly more to hold. A profile that counts allocation events measures churn, not footprint, and the two rank functions differently.

Getting from events to footprint requires tracking lifetime, which means interposing on the allocator rather than sampling the instruction pointer. The instrumentation is therefore in the hot path of every allocation, and the design problem is how to keep that cost bounded when malloc is called millions of times per second.

Two allocations, one profile

The distinction to make explicit at the start: an allocation count per call site answers “where does churn come from”, and a live-bytes count per call site answers “where does size come from”. Both are useful, and they require different bookkeeping.

Churn is cheap to measure. Every allocation is an event, so a counter per call site suffices, and the counter is incremented in the interposer. The result is exact if every allocation is counted, and it directly identifies the functions responsible for allocator traffic, which is what a latency problem caused by allocator contention or by mmap churn needs.

Live bytes require matching allocations to frees, so each allocation must carry enough identity to be attributed to a site when it is released. That identity is either the stack that allocated it or a recorded call-site identifier, stored in a header adjacent to the allocation. The freed bytes are then subtracted from the site’s total, and the running difference is the live figure. This is exact if every free is seen and correctly attributed, and it is what leak-detection and heap-profiling tools report at their most exact setting.

Continuous allocation profiling for a production fleet usually wants footprint, which is the harder of the two, and the tools that do it either interpose on the allocator or read the allocator’s own metadata.

Where interposition happens and what it costs

Three interposition points are available, and they differ in what the profiler can see and in how much of the call path it can attribute.

The first is the libc symbol. malloc, free, calloc, and realloc are ordinary dynamic symbols, so a library loaded ahead of libc can define them and forward to the real implementations. This is the least invasive option and the least complete, because it sees only calls that go through the dynamic symbol. Static linking, inlined allocation helpers in a custom allocator, and calls that resolve internally inside libc bypass it entirely.

The second is the allocator’s own hook interface. Several general-purpose allocators expose callbacks invoked on allocation and deallocation, including the originating stack captured by the allocator itself. Hook interfaces see every allocation the allocator serves, including internal ones, and they exist precisely so that this kind of accounting does not require interposing on symbols. The cost is that the hooks are per-allocator, so the profiler must be built for the allocator in use.

The third is the kernel. Allocating new pages shows up as mmap or brk requests, and those events are traceable from outside the process. This sees memory at page granularity, which is far coarser than an application allocation, so it attributes footprint to the code that caused the heap to grow rather than to the code that requested the bytes. It is nonetheless useful for finding the component responsible for a multi-megabyte growth, and it requires no interposition in the process at all.

The cost of the first two is paid per allocation, in the caller’s thread, and it is much larger in relative terms than a CPU sample’s cost. A malloc call to a thread-local cache in a fast allocator is on the order of tens of nanoseconds. Adding a stack capture, which is at minimum a few hundred nanoseconds and can be several microseconds with debug information or a table lookup, multiplies the cost of the operation by one or two orders of magnitude. Interposing naively converts a program that allocates quickly into a program that allocates slowly, and the profiler’s own overhead dominates whatever it measures.

Sampling allocations is not the same as sampling CPU

The standard escape from that cost is sampling: record a fraction of allocations and scale the counts. The scaling is where allocation sampling diverges from instruction sampling.

An instruction sample can be treated as a uniform draw over time, because the sampler fires at regular intervals regardless of what the program is doing. An allocation sample is chosen at allocation time, and the natural way to choose it is by size: sample a large allocation with probability one, a small one with probability proportional to its size. That yields unbiased estimates of bytes allocated per site, since a site’s expected sample weight equals its byte volume.

The correction is needed because of how the sampling interval interacts with allocator behaviour. If the sampler picks every allocation with a fixed probability $p$, then a site that allocates $N$ times with mean size $s$ contributes $N s$ bytes and yields about $pN$ samples, so multiplying the sampled bytes by $1/p$ gives an unbiased total. Fine, but the variance is now the variance of a negative binomial, and for a site whose total size is small relative to the average allocation size, the estimate is dominated by whether it happened to be sampled at all. A site that allocates two large buffers contributes either zero or a large number, and there is no middle ground.

Size-proportional sampling does not fix the variance; it changes its shape. The estimator for total bytes is unbiased, but the per-site estimate has a distribution with a long right tail and a point mass at zero, and summing many such sites gives a fleet-wide total that is much better estimated than any individual site. This is why sampled allocation profiles are informative at the aggregate level and unreliable at the level of a single small caller.

The second divergence is that allocation events are not independent of the code being measured. A program that allocates in a loop allocates faster when it is running faster, so a sampler that fires every $k$-th allocation produces a sample rate proportional to allocation rate, not to time. The profile is then a profile of allocation events rather than of time, which is the right frame for memory questions and the wrong one for CPU questions; the two profiles are not interchangeable and cannot be merged.

Attribution through the header

For footprint tracking, each allocation needs to carry its origin until it is freed. The conventional layout puts a fixed-size header immediately before the returned pointer, holding the call-site identifier, the requested size, and the sampling weight.

The header changes the alignment of returned pointers and the layout of the heap, which has consequences beyond the profiler. Alignment requirements in the ABI mean the allocator rounds sizes up; adding sixteen bytes of header to every allocation shifts every size class boundary and can change which size class an allocation lands in, which changes the allocator’s own fragmentation behaviour. A profiler that changes the size class distribution has changed the workload it is measuring, and the resulting memory figures are not the unprofiled program’s figures.

Recovering the header on free requires the pointer to still be the one that was returned. Programs that free an interior pointer, or that pass a pointer through a reallocating API that returns a different address, break the mapping unless the interposer handles those cases explicitly. realloc is the classic case: it may return a new pointer while freeing the old, and the header must be copied with the identity preserved so that the total live bytes do not double count.

There is also the case of allocations made before the profiler initializes. Library constructors that allocate during load run before any hook installed by the application, so those allocations have no header and no site. Reading the header for them would read memory that belongs to something else. A robust interposer checks a signature or a validity field before trusting the header, and falls back to attributing the free to an unknown site, which keeps the accounting consistent at the price of a small unattributed remainder.

Answering the footprint question in production

The practical form of continuous allocation profiling for a fleet is a sampled count of live bytes per call site, collected at a low rate and exported as a periodic snapshot. Because the quantity is a state rather than a rate, the snapshot is meaningful without a time window: the live bytes at a moment are the number of interest, and comparing snapshots over time shows growth.

That state semantics is both the strength and the trap. A snapshot taken at process start shows a large footprint in the initialization path, which never changes and therefore never matters. A snapshot taken after a traffic spike shows the spike’s allocations still live, which may be pooled buffers that will be reused rather than a leak. Distinguishing growth from pooling requires comparing several snapshots and looking at the sites whose contribution increases monotonically, which is a query over time rather than a single profile.

The overhead budget for the whole exercise is small if the sampling rate is: a sampled allocator configured to capture one stack per few thousand allocations, with the capture performed by the allocator’s own fast path, costs well under a percent of runtime on allocation-heavy workloads. The design constraints are the ones this cluster keeps returning to: capture cheaply on the hot path, aggregate close to the source, and make the loss visible rather than silent.