When Recursion Becomes a Loop
Every programmer meets recursion early, often through the Fibonacci sequence: Fn = Fn-1 + Fn-2. The naive recursive implementation is easy to write, but it has a problem—each call pushes a new frame onto a finite stack. A tail-recursive version avoids that because the recursive call is the very last operation in the function.
The difference shows up in the generated assembly. For x86-64 and arm64, a tail-recursive Fibonacci compiles to a tight loop: the final call is replaced by a simple jump. The non-tail version, by contrast, turns into a sprawling graph of basic blocks stuffed with call instructions—so many that it can barely fit on a listing page:
Watching the stack pointer during the naive version confirms the damage: the stack grows with every recursive call. The tail version never touches it. This is the essence of tail call elimination, a compiler optimization that reuses the caller's stack frame for the callee since the caller's frame is about to be destroyed anyway.
Decompiling a tail-optimized object file with Ghidra makes the transformation obvious: instead of a call at the end of the function, there is simply a jump back to the beginning. The resulting machine code is dramatically shorter and much faster.
BPF's Own Tail Call Semantics
Tail call elimination exists in the BPF world too. LLVM's BPF backend will eliminate trailing calls at the intermediate representation level, which spares you BPF-to-BPF call -N instructions. But when BPF developers talk about tail calls, they usually mean something else entirely: a JIT mechanism for chaining entire BPF programs together.
Cloudflare adopted this for its XDP-based DDoS mitigation pipeline, splitting packet processing into multiple XDP programs, each with one responsibility, linked via BPF tail calls:
The helper is bpf_tail_call(). You don't name the target program directly—instead you hand it a BPF_MAP_TYPE_PROG_ARRAY map and an index into that map:
long bpf_tail_call(void *ctx, struct bpf_map *prog_array_map, u32 index)
Description
This special helper is used to trigger a "tail call", or
in other words, to jump into another eBPF program. The
same stack frame is used (but values on stack and in reg‐
isters for the caller are not accessible to the callee).
This mechanism allows for program chaining, either for
raising the maximum number of available eBPF instructions,
or to execute given programs in conditional blocks. For
security reasons, there is an upper limit to the number of
successive tail calls that can be performed.This looks similar to execve(2)—swap the current program for another—but it's not. The Cilium documentation nails it: tail calls are "a mechanism that allows one BPF program to call another, without returning to the old program," implemented as a long jump reusing the same stack frame. Yet when you mix in BPF function calls, the picture becomes subtler: a tail call unwinds only the stack frame of the function that made it. If that function was called by another BPF program, the caller's frame remains alive. When the tail-called program finally returns, control flows all the way back to the top-level caller of the function that initiated the tail call.
Compiler Surprises in the Details
Those semantics lead to genuinely surprising behavior. Consider two BPF programs, server1() and server2(), each of which calls the same BPF function bring_order(). That function tail-calls into serve_drink() via the map. Logically, both programs should return the same thing—one gets ☕, the other gets ?.
struct {
__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
__uint(max_entries, 1);
__uint(key_size, sizeof(__u32));
__uint(value_size, sizeof(__u32));
} bar SEC(".maps");
SEC("tc")
int serve_drink(struct __sk_buff *skb __unused)
{
return 0xcafe;
}
static __noinline
int bring_order(struct __sk_buff *skb)
{
bpf_tail_call(skb, &bar, 0);
return 0xf00d;
}
SEC("tc")
int server1(struct __sk_buff *skb)
{
return bring_order(skb);
}
SEC("tc")
int server2(struct __sk_buff *skb)
{
__attribute__((musttail)) return bring_order(skb);
}Why the difference? Because the compiler has no idea that bpf_tail_call() changes control flow. It optimizes as if execution would continue past the helper call. In server1(), the compiler constant-propagates the return value of bring_order(), baking it into the caller's code path. The call graph is identical, but the generated BPF assembly isn't:
The fix is to tell the compiler the truth: use the musttail attribute on calls to functions that end with a BPF tail call. That forces the call to be a proper tail call, guaranteeing that the function's return value is used as-is by the caller. Skipping that attribute risks optimization-driven inconsistencies.
Architecture-Specific Constraints
Beyond semantics, there was a hard implementation constraint on arm64: you couldn't mix BPF function calls and BPF tail calls in the same XDP program. The reasons live in the BPF JIT compiler's mechanics, which we're about to dig into—and which explain why Cloudflare had to pay close attention to this on arm64, one of its supported architectures. On x86-64 this was never an issue.
Following the tail call through the JIT
The BPF JIT compiler for x86-64 in arch/x86/net/bpf_jit_comp.c handles BPF_JMP | BPF_TAIL_CALL instructions through emit_bpf_tail_call_direct(), but inspecting generated code requires a populated program array first. This is because the JIT can use instruction patching when the target index is known at load time.
Reading the instruction stream from bpftool prog dump jited output is misleading: the displayed jump addresses for tail calls are not the real targets. The actual addresses live in kernel memory, discoverable via gdb using the JIT’ed program addresses from /proc/kallsyms.# bpftool prog loadall ./tail_call_ex1.o /sys/fs/bpf pinmaps /sys/fs/bpf
# bpftool map update pinned /sys/fs/bpf/jmp_table key 0 0 0 0 value pinned /sys/fs/bpf/target_prog
# bpftool prog dump xlated pinned /sys/fs/bpf/entry_prog
int entry_prog(struct __sk_buff * skb):
; bpf_tail_call(skb, &jmp_table, 0);
0: (18) r2 = map[id:24]
2: (b7) r3 = 0
3: (85) call bpf_tail_call#12
; return 0xf00d;
4: (b7) r0 = 61453
5: (95) exit
# bpftool prog dump jited pinned /sys/fs/bpf/entry_prog
int entry_prog(struct __sk_buff * skb):
bpf_prog_4f697d723aa87765_entry_prog:
; bpf_tail_call(skb, &jmp_table, 0);
0: nopl 0x0(%rax,%rax,1)
5: xor %eax,%eax
7: push %rbp
8: mov %rsp,%rbp
b: push %rax
c: movabs $0xffff888102764800,%rsi
16: xor %edx,%edx
18: mov -0x4(%rbp),%eax
1e: cmp $0x21,%eax
21: jae 0x0000000000000037
23: add $0x1,%eax
26: mov %eax,-0x4(%rbp)
2c: nopl 0x0(%rax,%rax,1)
31: pop %rax
32: jmp 0xffffffffffffffe3 // bug? ?
; return 0xf00d;
37: mov $0xf00d,%eax
3c: leave
3d: ret
# tail -2 /proc/kallsyms
ffffffffa0000720 t bpf_prog_f85b2547b00cbbe9_target_prog [bpf]
ffffffffa0000748 t bpf_prog_4f697d723aa87765_entry_prog [bpf]
# gdb -q -c /proc/kcore -ex 'x/18i 0xffffffffa0000748' -ex 'quit'
[New process 1]
Core was generated by `earlyprintk=serial,ttyS0,115200 console=ttyS0 psmouse.proto=exps "virtme_stty_c'.
#0 0x0000000000000000 in ?? ()
0xffffffffa0000748: nopl 0x0(%rax,%rax,1)
0xffffffffa000074d: xor %eax,%eax
0xffffffffa000074f: push %rbp
0xffffffffa0000750: mov %rsp,%rbp
0xffffffffa0000753: push %rax
0xffffffffa0000754: movabs $0xffff888102764800,%rsi
0xffffffffa000075e: xor %edx,%edx
0xffffffffa0000760: mov -0x4(%rbp),%eax
0xffffffffa0000766: cmp $0x21,%eax
0xffffffffa0000769: jae 0xffffffffa000077f
0xffffffffa000076b: add $0x1,%eax
0xffffffffa000076e: mov %eax,-0x4(%rbp)
0xffffffffa0000774: nopl 0x0(%rax,%rax,1)
0xffffffffa0000779: pop %rax
0xffffffffa000077a: jmp 0xffffffffa000072b
0xffffffffa000077f: mov $0xf00d,%eax
0xffffffffa0000784: leave
0xffffffffa0000785: ret
# gdb -q -c /proc/kcore -ex 'x/7i 0xffffffffa0000720' -ex 'quit'
[New process 1]
Core was generated by `earlyprintk=serial,ttyS0,115200 console=ttyS0 psmouse.proto=exps "virtme_stty_c'.
#0 0x0000000000000000 in ?? ()
0xffffffffa0000720: nopl 0x0(%rax,%rax,1)
0xffffffffa0000725: xchg %ax,%ax
0xffffffffa0000727: push %rbp
0xffffffffa0000728: mov %rsp,%rbp
0xffffffffa000072b: mov $0xcafe,%eax
0xffffffffa0000730: leave
0xffffffffa0000731: ret
#The security constraint that shapes the code
BPF's bpf_tail_call() jumps into another function's code while reusing the current stack frame. The critical feature is the run-time limit on the depth of jump chains, capped at MAX_TAIL_CALL_CNT = 33. The verifier cannot account for dynamic updates to the program array, so the JITed code maintains a counter, tail_call_cnt, at run time.
The counter travels between programs through the x86-64 rax register, which the JIT reuses for this purpose since it doesn't hold arguments under the standard calling convention. When the next program starts executing, its prologue saves this value onto the stack. Later invocations of bpf_tail_call() retrieve it from that known stack offset and increment it before the next jump.
A BPF program may also be split into a main program and several subprograms, each with its own stack frame — the BPF component model — and subprogram handling introduces a complication. Since function calls overwrite rax, the tail call counter must be saved and restored around each BPF function call, and the subprogram's prologue must not reset the register as the main program's prologue does. Whenever a bpf_tail_call() executes inside such a nest, it has to preserve its own stack frame while unwinding the frames above it, and then save the accumulated count to the target program's stack.
| BPF | x86-64 |
|---|---|
| r0 | rax |
| r1 | rdi |
| r2 | rsi |
| r3 | rdx |
| r4 | rcx |
| r5 | r8 |
| r6 | rbx |
| r7 | r13 |
| r8 | r14 |
| r9 | r15 |
| r10 | rbp |
| internal | r9-r12 |
static int check_max_stack_depth(struct bpf_verifier_env *env)
{
…
/* protect against potential stack overflow that might happen when
* bpf2bpf calls get combined with tailcalls. Limit the caller's stack
* depth for such case down to 256 so that the worst case scenario
* would result in 8k stack size (32 which is tailcall limit * 256 =
* 8k).
*
* To get the idea what might happen, see an example:
* func1 -> sub rsp, 128
* subfunc1 -> sub rsp, 256
* tailcall1 -> add rsp, 256
* func2 -> sub rsp, 192 (total stack size = 128 + 192 = 320)
* subfunc2 -> sub rsp, 64
* subfunc22 -> sub rsp, 128
* tailcall2 -> add rsp, 128
* func3 -> sub rsp, 32 (total stack size 128 + 192 + 64 + 32 = 416)
*
* tailcall will unwind the current stack frame but it will not get rid
* of caller's stack as shown on the example above.
*/
if (idx && subprog[idx].has_tail_call && depth >= 256) {
verbose(env,
"tail_calls are not allowed when call stack of previous frames is %d bytes. Too large\n",
depth);
return -EACCES;
}
…
}
What changes on arm64
The arm64 JIT has different constraints and layout decisions, starting with which free register doubles as the hidden counter. Like the x86-64 version, its tail call routine picks the next program from the map, checks the slot limit, unwinds the stack, and jumppoints into the target — only the exact register usage, immediate field sizes and alignment rules differ.
The one difference that stands out is how arm64 encodes the per-program stack depth vs. how it unwinds multiple frames before the jump. This demands both a stricter maximum nesting depth and careful ordering of prologue saves, but it leaves the overall BPF contract unchanged: a tail call is still a stack-reusing, non-recursive jump, still bounded by the same MAX_TAIL_CALL_CNT verdict.
Mixing BPF calls and tail calls on arm64
If you attempt to load a BPF program that combines BPF-to-BPF function calls with tail calls on an arm64 machine running the 5.15 LTS kernel (or even 5.19 stable), the verifier refuses:
# uname -rm
5.19.12 aarch64
# bpftool prog loadall tail_call_ex2.o /sys/fs/bpf
libbpf: prog 'entry_prog': BPF program load failed: Invalid argument
libbpf: prog 'entry_prog': -- BEGIN PROG LOAD LOG --
0: R1=ctx(off=0,imm=0) R10=fp0
; __attribute__((musttail)) return sub_func(skb);
0: (85) call pc+1
caller:
R10=fp0
callee:
frame1: R1=ctx(off=0,imm=0) R10=fp0
; bpf_tail_call(skb, &jmp_table, 0);
2: (18) r2 = 0xffffff80c38c7200 ; frame1: R2_w=map_ptr(off=0,ks=4,vs=4,imm=0)
4: (b7) r3 = 0 ; frame1: R3_w=P0
5: (85) call bpf_tail_call#12
tail_calls are not allowed in non-JITed programs with bpf-to-bpf calls
processed 4 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
-- END PROG LOAD LOG --
…
#That limitation is unfortunate. With lengthy, machine-generated BPF programs, code sharing via BPF-to-BPF calls is a major win. So we dug into arch/arm64/net/bpf_jit_comp.c to see what it would take to lift the restriction.
The arm64 JIT already handles tail calls and BPF function calls independently. The only real problem is understanding how registers and stack state flow through the two code paths, and figuring out where they clash. We don't need to read the entire JIT source—just a few key functions:
bpf_int_jit_compile()build_prologue()build_body()and its per-instructionbuild_insn(), which dispatches on the BPF opcode forBPF_JMP | BPF_CALLandBPF_JMP | BPF_TAIL_CALLbuild_epilogue()
Unlike x86-64, arm64 (like most RISC architectures) has plenty of general-purpose registers—x0 through x30. That's an advantage: the JIT can dedicate a register to internal state such as the tail call counter instead of spilling it to memory.
| BPF | arm64 |
|---|---|
| r0 | x7 |
| r1 | x0 |
| r2 | x1 |
| r3 | x2 |
| r4 | x3 |
| r5 | x4 |
| r6 | x19 |
| r7 | x20 |
| r8 | x21 |
| r9 | x22 |
| r10 | x25 |
| internal | x9-x12, x26 (tail_call_cnt), x27 |
To see where the conflict lies, we traced the JIT's input and output for two simple scenarios. This means reading through the generated ARM64 assembly instruction by instruction. If you're new to ARM64 assembly, it's worth skimming a basic guide (like the Guide to ARM64 / AArch64 Assembly on Linux) first.
Scenario 1: A plain BPF tail call
Input BPF assembly (bpftool prog dump xlated):
0: (18) r2 = map[id:4] // jmp_table map
2: (b7) r3 = 0
3: (85) call bpf_tail_call#12
4: (b7) r0 = 61453 // 0xf00d
5: (95) exitOutput ARM64 assembly (bpftool prog dump jited):
0: paciasp // Sign LR (ROP protection) ①
4: stp x29, x30, [sp, #-16]! // Save FP and LR registers ②
8: mov x29, sp // Set up Frame Pointer
c: stp x19, x20, [sp, #-16]! // Save callee-saved registers ③
10: stp x21, x22, [sp, #-16]! // ⋮
14: stp x25, x26, [sp, #-16]! // ⋮
18: stp x27, x28, [sp, #-16]! // ⋮
1c: mov x25, sp // Set up BPF stack base register (r10)
20: mov x26, #0x0 // Initialize tail_call_cnt ④
24: sub x27, x25, #0x0 // Calculate FP bottom ⑤
28: sub sp, sp, #0x200 // Set up BPF program stack ⑥
2c: mov x1, #0xffffff80ffffffff // r2 = map[id:4] ⑦
30: movk x1, #0xc38c, lsl #16 // ⋮
34: movk x1, #0x7200 // ⋮
38: mov x2, #0x0 // r3 = 0
3c: mov w10, #0x24 // = offsetof(struct bpf_array, map.max_entries) ⑧
40: ldr w10, [x1, x10] // Load array->map.max_entries
44: add w2, w2, #0x0 // = index (0)
48: cmp w2, w10 // if (index >= array->map.max_entries)
4c: b.cs 0x0000000000000088 // goto out;
50: mov w10, #0x21 // = MAX_TAIL_CALL_CNT (33)
54: cmp x26, x10 // if (tail_call_cnt >= MAX_TAIL_CALL_CNT)
58: b.cs 0x0000000000000088 // goto out;
5c: add x26, x26, #0x1 // tail_call_cnt++;
60: mov w10, #0x110 // = offsetof(struct bpf_array, ptrs)
64: add x10, x1, x10 // = &array->ptrs
68: lsl x11, x2, #3 // = index * sizeof(array->ptrs[0])
6c: ldr x11, [x10, x11] // prog = array->ptrs[index];
70: cbz x11, 0x0000000000000088 // if (prog == NULL) goto out;
74: mov w10, #0x30 // = offsetof(struct bpf_prog, bpf_func)
78: ldr x10, [x11, x10] // Load prog->bpf_func
7c: add x10, x10, #0x24 // += PROLOGUE_OFFSET * AARCH64_INSN_SIZE (4)
80: add sp, sp, #0x200 // Unwind BPF stack
84: br x10 // goto *(prog->bpf_func + prologue_offset)
88: mov x7, #0xf00d // r0 = 0xf00d
8c: add sp, sp, #0x200 // Unwind BPF stack ⑨
90: ldp x27, x28, [sp], #16 // Restore used callee-saved registers
94: ldp x25, x26, [sp], #16 // ⋮
98: ldp x21, x22, [sp], #16 // ⋮
9c: ldp x19, x20, [sp], #16 // ⋮
a0: ldp x29, x30, [sp], #16 // ⋮
a4: add x0, x7, #0x0 // Set return value
a8: autiasp // Authenticate LR
ac: ret // Return to callerThe prologue is doing several things:
- Emitting Pointer Authentication Code (PAC) for protection against return-oriented programming, if
CONFIG_ARM64_PTR_AUTH_KERNELis enabled. - Saving the frame pointer (
X29) and link register (X30), as required by the Arm 64 Procedure Call Standard. - Preserving callee-saved registers
X19–X28,X29, andX30.X23andX24are skipped because the JIT doesn't use them currently. - Initializing
X26as the tail call depth counter. No stack save is needed because the register is dedicated. - Setting up an FP bottom pointer to permit single-instruction load/store with an immediate offset for BPF stack access.
- Reserving stack space for the BPF program's stack frame.
The body runs until it hits the bpf_tail_call() sequence, after which the epilogue takes over. A key detail: arm64's tail call path isn't optimized like x86-64's. There's no code patching for a direct jump when the target program index is known at JIT time—instead, the target address must be loaded from the BPF program array every time.
Scenario 2: A BPF-to-BPF call
Input BPF assembly (bpftool prog dump xlated):
int entry_prog(struct __sk_buff * skb):
0: (85) call pc+1#bpf_prog_a84919ecd878b8f3_sub_func
1: (95) exit
int sub_func(struct __sk_buff * skb):
2: (b7) r0 = 61453 // 0xf00d
3: (95) exitOutput ARM64 assembly:
int entry_prog(struct __sk_buff * skb):
bpf_prog_163e74e7188910f2_entry_prog:
0: paciasp // Begin prologue
4: stp x29, x30, [sp, #-16]! // ⋮
8: mov x29, sp // ⋮
c: stp x19, x20, [sp, #-16]! // ⋮
10: stp x21, x22, [sp, #-16]! // ⋮
14: stp x25, x26, [sp, #-16]! // ⋮
18: stp x27, x28, [sp, #-16]! // ⋮
1c: mov x25, sp // ⋮
20: mov x26, #0x0 // ⋮
24: sub x27, x25, #0x0 // ⋮
28: sub sp, sp, #0x0 // End prologue
2c: mov x10, #0xffffffffffff5420 // Build sub_func()+0x0 address
30: movk x10, #0x8ff, lsl #16 // ⋮
34: movk x10, #0xffc0, lsl #32 // ⋮
38: blr x10 ------------------. // Call sub_func()+0x0
3c: add x7, x0, #0x0 <----------. // r0 = sub_func()
40: mov sp, sp | | // Begin epilogue
44: ldp x27, x28, [sp], #16 | | // ⋮
48: ldp x25, x26, [sp], #16 | | // ⋮
4c: ldp x21, x22, [sp], #16 | | // ⋮
50: ldp x19, x20, [sp], #16 | | // ⋮
54: ldp x29, x30, [sp], #16 | | // ⋮
58: add x0, x7, #0x0 | | // ⋮
5c: autiasp | | // ⋮
60: ret | | // End epilogue
| |
int sub_func(struct __sk_buff * skb): | |
bpf_prog_a84919ecd878b8f3_sub_func: | |
0: paciasp <---------------------' | // Begin prologue
4: stp x29, x30, [sp, #-16]! | // ⋮
8: mov x29, sp | // ⋮
c: stp x19, x20, [sp, #-16]! | // ⋮
10: stp x21, x22, [sp, #-16]! | // ⋮
14: stp x25, x26, [sp, #-16]! | // ⋮
18: stp x27, x28, [sp, #-16]! | // ⋮
1c: mov x25, sp | // ⋮
20: mov x26, #0x0 | // ⋮
24: sub x27, x25, #0x0 | // ⋮
28: sub sp, sp, #0x0 | // End prologue
2c: mov x7, #0xf00d | // r0 = 0xf00d
30: mov sp, sp | // Begin epilogue
34: ldp x27, x28, [sp], #16 | // ⋮
38: ldp x25, x26, [sp], #16 | // ⋮
3c: ldp x21, x22, [sp], #16 | // ⋮
40: ldp x19, x20, [sp], #16 | // ⋮
44: ldp x29, x30, [sp], #16 | // ⋮
48: add x0, x7, #0x0 | // ⋮
4c: autiasp | // ⋮
50: ret ----------------------------' // End epilogueOnce you see both variants side by side, the bug is obvious: entering a BPF subprogram resets X26 (the tail call counter) to zero via mov x26, #0x0 in the subprogram's prologue. If tail calls and BPF function calls were mixed, that reset would allow a user to chain programs well past the MAX_TAIL_CALL_CNT limit—the counter would start from scratch on every subroutine entry.
The fix and the result
Can we simply omit that zeroing instruction when JIT-compiling a BPF subprogram prologue?
@@ -246,6 +246,7 @@ static bool is_lsi_offset(int offset, int scale)
static int build_prologue(struct jit_ctx *ctx, bool ebpf_from_cbpf)
{
const struct bpf_prog *prog = ctx->prog;
+ const bool is_main_prog = prog->aux->func_idx == 0;
const u8 r6 = bpf2a64[BPF_REG_6];
const u8 r7 = bpf2a64[BPF_REG_7];
const u8 r8 = bpf2a64[BPF_REG_8];
@@ -299,7 +300,7 @@ static int build_prologue(struct jit_ctx *ctx, bool ebpf_from_cbpf)
/* Set up BPF prog stack base register */
emit(A64_MOV(1, fp, A64_SP), ctx);
- if (!ebpf_from_cbpf) {
+ if (!ebpf_from_cbpf && is_main_prog) {
/* Initialize tail_call_cnt */
emit(A64_MOVZ(1, tcc, 0, 0), ctx);That single change—skipping the tail call count reset for subprogram prologues—turned out to be the entire missing piece. It was merged for Linux 6.0, enabling both features simultaneously on arm64.
You can see the result in action in this GDB walkthrough, which steps through BPF code that calls into a BPF function and then tail calls onward to another BPF program.
