Dynamic Tracing by Rewriting Instructions: ftrace and kprobes

Tracing a function call usually means rebuilding with instrumentation, which changes timing, changes inlining decisions, and produces a binary that is not the one under investigation. The alternative is to modify the running text: overwrite the first bytes of a function with a jump to a trampoline, and restore the original bytes when tracing stops. The trick is simple in principle and delicate in every detail, because other CPUs are executing that text while it is being rewritten.

The patch site

On x86-64 a direct jump to a target within two gigabytes is five bytes: an opcode byte followed by a signed 32-bit displacement relative to the next instruction. Kernel text is within that range of itself, and the trampolines that ftrace allocates for its dynamic sites are placed by the module allocator precisely so that they land in the same window.

Five bytes is also the smallest patch that can be made safely, and that constrains where it can be made. The compiler emits, at the start of every function that the build instruments, a five-byte call to an external symbol, placed at a point where the function’s prologue has not yet modified registers or the stack. On x86-64 the kernel arranges that by using the fentry instrumentation form, where the call is the first instruction of the function; the older pg form emits the call after the prologue, which is why its use has narrowed to toolchains that do not support fentry. That build-time call is the patch site. It is a real call at build time, so a kernel with tracing compiled in but not enabled pays a call and a return per function entry; the alternative is to compile the call out and have no site to patch, which is why the mechanism requires the build option rather than being purely runtime.

The call targets a stub that does nothing. Enabling tracing rewrites the displacement so that the call goes to the tracer instead. That is the whole of the fast path: a call instruction whose destination is changed from a no-op to a recorder. There is no branch, no conditional, no test of a flag. The cost when disabled is the call and return themselves, a handful of cycles.

Recording every function entry is rarely what is wanted, so the patched destination is a dispatcher that consults a bitmap of enabled call sites. Each instrumented function has an index into that bitmap, and the call site is patched only when its bit is set. Turning tracing on for one function patches one site; turning on tracing for a subsystem patches a few dozen. The bitmap lookup is a load and a test, cheap enough that leaving the call in place for a function whose bit is clear still costs far less than the tracing itself would.

Rewriting text that other CPUs are running

Writing five bytes into an instruction that another processor may be executing at that moment is not atomic. A processor fetches instructions in cache-line-sized chunks; if the patch crosses a cache line boundary, or if the write is not atomic with respect to instruction fetch, another CPU can observe a partially written instruction. The result is not a wrong answer but an invalid opcode, or worse, a valid-looking instruction with a garbage displacement.

The kernel’s answer has three parts. First, patching is done with a single atomic store where the architecture permits it: on x86-64 a call site is rewritten by writing the new displacement as one naturally aligned 32-bit store, so a CPU cannot observe a half-written displacement for that field, and the opcode byte at the site is the same in the patched and unpatched forms, so the processor’s view of the instruction stream never becomes a different instruction with a stale operand. Second, the patching code synchronises every other CPU before and after the write, so that each core serialises its pipeline and discards prefetched bytes before execution resumes; where an opcode itself must change, the primitive deliberately plants a breakpoint byte first, lets any CPU that reaches it trap, and only then writes the rest, so that no core is ever executing an instruction that is being rewritten underneath it. Third, the whole sequence runs under a mutex that serialises patchers, so two subsystems cannot rewrite the same site at once.

The ordering is what matters. Writing the new bytes first and flushing afterwards would leave a window in which one CPU executes the new instruction while another executes the old. The kernel instead arranges that the write happens when every other CPU has been diverted into a known state, and that the flush completes before any of them returns. This is expensive (an inter-processor interrupt to every core, on the order of microseconds per patch), and it is why enabling tracing for a large set of functions is a batched operation rather than a per-function one.

The mechanism is also the one that replaces alternatives at boot. Instructions that the kernel wants to optimise out at runtime, such as a conditional that is always false on this CPU, are compiled as a five-byte sequence that can be rewritten into a jump over the check. The same primitive does the work, and the same care about concurrency applies.

Probing an arbitrary instruction

A kprobe is a harder problem. The target is not a call site the compiler placed; it is any instruction the user names, at any offset in any function, including inside the middle of a basic block. The mechanism replaces that instruction with a breakpoint instruction (a single byte on x86, 0xCC) whose execution traps. The trap handler looks up the address, finds the probe, runs the pre-handler, single-steps the original instruction, runs the post-handler, and resumes.

The single-step is why a copy is needed. The original instruction must be executed somewhere, and it cannot be executed at its own address because that address now holds a breakpoint. The kernel keeps a pool of instruction slots in executable memory, copies the instruction into one of them, and redirects execution there with the trap flag set so that the processor stops after exactly one instruction; several probes share a slot page rather than each taking one. On x86, instructions are variable-length and some are position-dependent (a relative jump computes its target from its own address), so the copied instruction is not generally equivalent to the original. The kernel decodes the instruction, determines its length, and fixes up relative branches and instruction-pointer-relative operands so the copy behaves as the original would have at its original address.

Instructions that cannot be relocated are not probeable, and the kernel reports that when the probe is registered rather than at the moment it fires. The check is done by attempting the decode at registration time, which also produces the length used for the trap.

#include <linux/kprobes.h>

static int handler_pre(struct kprobe *p, struct pt_regs *regs)
{
	/* regs->ip points at the copied instruction's original address. */
	return 0;   /* non-zero suppresses execution of the probed instruction */
}

static struct kprobe kp = {
	.symbol_name = "vfs_open",
	.pre_handler = handler_pre,
};

static int __init probe_init(void)
{
	return register_kprobe(&kp);
}

Cost, and what the two mechanisms are for

A kprobe costs a trap, and a trap is a full privilege transition: saving the register state, switching stacks, running the handler, restoring, and returning. That is on the order of a microsecond per hit, two to three orders of magnitude more than an ftrace call. Kprobes are therefore suited to a small number of hits on a cold path, not to a function called per packet. For return values there is a cheaper shape: a kretprobe still installs its trap at function entry, but its pre-handler swaps the return address on the stack for a trampoline address, so the exit is observed when the function returns through the stub rather than through a second trap. Entry costs what a kprobe costs; exit becomes a jump.

An ftrace call site costs a call and a return, and the dispatcher’s bitmap test. A trace of ten thousand function entries per second is unremarkable; a kprobe at the same rate would consume a noticeable fraction of a CPU. The distinction decides which to use: ftrace for breadth and frequency, kprobes for precision at a specific instruction or for functions that were not compiled with instrumentation.

Both mechanisms share a hazard. A probe handler runs in the context of the probed code, which may be holding locks, may be in an interrupt, and may be inside a region where the kernel considers preemption impossible. A handler that allocates, sleeps, or takes a lock held by the probed path deadlocks or corrupts. The kernel does not prevent this; it documents it, and a probe that misbehaves produces a hang whose stack points into the tracing code rather than into the probed function. The same constraint governs lock ordering validation: a tool that observes the kernel from inside it must never change the timing relationships it is trying to reason about.

Interaction with the rest of the debugging surface

Both mechanisms depend on the symbol table, so a probe on a function that was inlined has no site to patch and registration fails with a clear message. Both are disabled or restricted when the kernel is locked down, because rewriting kernel text is precisely the capability an attacker wants. Both are recorded in the kernel’s own state so that a crash while tracing can be attributed: a stack trace that passes through a tracer is recognisable, and the alternative explanation (that the traced function itself failed) is eliminated.

The patching primitive is also what livepatch uses to redirect a function to a replacement while it runs, and the atomicity problem there is worse, because the function may be executing on another CPU when the redirection happens. The five-byte jump is the same; the guarantee about when it is safe to make it is not.