BPF verifier complexity limit: always_inline vs __noinline (same logic, opposite outcomes)

README.md

BPF verifier: always_inline vs __noinline — same logic, opposite outcomes

A minimal, runnable demo of the BPF verifier complexity limit (1,000,000 processed instructions). One source file, compiled two ways:

Build	Static instructions	Processed insns	Result
always_inline	38	1,000,001	REJECTED (E2BIG)
__noinline	43	6,742	LOADED

Same program, ~150× difference in verifier work — and only 38 static instructions, proving it is the complexity limit, not program size.

The program is an outer loop that, each iteration, calls a helper walk() containing an inner bounded loop. The only thing that changes between builds is whether walk() is always_inline or a real __noinline BPF-to-BPF subprogram (-DINLINE_MODE=1 vs 0).

• always_inline: the inner loop is stamped into the outer loop's body. The outer index i is still live, so the verifier's state at the inner loop differs on every outer iteration → no pruning → the inner loop is re-walked OUTER times. Cost ≈ OUTER × INNER × k (k ≈ 13 instruction-visits per inner iteration on 5.10).
• __noinline: walk() is entered via BPF_CALL with a fresh frame whose only input is the (constant) map-value pointer. i is not part of the entry state, so the inner loop is verified once. Cost ≈ (inner loop once) + OUTER × const.

Requirements

• Linux with BTF (/sys/kernel/btf/vmlinux); kernel >= 5.3 for BPF-to-BPF calls (tested on 5.10).
• clang, llvm (llvm-objdump), bpftool, libbpf headers (libbpf-devel).
• root (loading a program needs CAP_BPF / CAP_SYS_ADMIN).

Run it

sudo ./run_explosion.sh

The script generates vmlinux.h from kernel BTF, builds both variants, loads each with bpftool prog load ... -d, and prints the verifier's processed N insns line for each.

Or by hand

# 1. headers from your running kernel's BTF
bpftool btf dump file /sys/kernel/btf/vmlinux format c > vmlinux.h

# 2. build both variants (set ARCH to x86 / arm64 to match your machine)
clang -g -O2 -Wall -target bpf -D__TARGET_ARCH_x86 -DINLINE_MODE=1 \
    -I. -c explosion_demo.bpf.c -o explosion.inline.o
clang -g -O2 -Wall -target bpf -D__TARGET_ARCH_x86 -DINLINE_MODE=0 \
    -I. -c explosion_demo.bpf.c -o explosion.noinline.o

# 3. load each and read the verifier log (-d = verbose verifier output)
sudo bpftool prog load explosion.inline.o   /sys/fs/bpf/expl_in  type xdp -d 2>&1 | grep -E "processed|too large"
sudo bpftool prog load explosion.noinline.o /sys/fs/bpf/expl_no  type xdp -d 2>&1 | grep -E "processed|too large"
sudo rm -f /sys/fs/bpf/expl_in /sys/fs/bpf/expl_no

# count static instructions in each object
llvm-objdump -d explosion.inline.o   | grep -cE '^\s+[0-9a-f]+:'
llvm-objdump -d explosion.noinline.o | grep -cE '^\s+[0-9a-f]+:'

The inline build fails with:

BPF program is too large. Processed 1000001 insn

The __noinline build loads (processed 6742 insns).

Tuning

OUTER (default 280) and INNER (default 300) are #defined at the top of the source and can be overridden at compile time (-DOUTER=... -DINNER=...):

• If both builds load, raise OUTER/INNER.
• If both fail, lower them (the inline build may be hitting the static BPF_MAXINSNS size limit instead of the complexity limit).

Measured crossover at INNER=300: OUTER=255 loads at 997,068 processed; OUTER=256 caps at 1,000,001.

explosion_demo.bpf.c

// explosion_demo.bpf.c
//
// Shows an ACTUAL verifier "processed instructions" explosion: the
// always_inline build blows the 1,000,000 processed-insn complexity limit and
// is REJECTED (E2BIG); the __noinline build verifies and LOADS.
//
// Mechanism (kernel 5.10 verifier) -- see the long note at the bottom.
//
// Build/run via run_explosion.sh.

#include "vmlinux.h"
#include <bpf/bpf_helpers.h>

#ifndef OUTER
#define OUTER 280    // outer (non-unrolled) iterations; one call site to walk()
#endif
#ifndef INNER
#define INNER 300    // inner bounded loop length inside walk()
#endif
#define SLOTS 64
#define SLOT_MASK (SLOTS - 1)

struct arr_value {
    __u64 slot[SLOTS];
};

struct {
    __uint(type, BPF_MAP_TYPE_ARRAY);
    __uint(max_entries, 1);
    __type(key, __u32);
    __type(value, struct arr_value);
} m SEC(".maps");

#ifndef INLINE_MODE
#define INLINE_MODE 1
#endif

#if INLINE_MODE
#define ATTR __attribute__((always_inline))
#else
#define ATTR __attribute__((noinline))
#endif

// Branchless bounded inner loop. The ONLY branch is the loop back-edge, so we
// never trip the jump-sequence limit. walk() receives ONLY a loop-independent
// map-value pointer -- it never sees the outer index i.
static ATTR __u64 walk(struct arr_value *arr) {
    // Accumulate into a local. walk() receives only the constant `arr` pointer
    // and nothing per-iteration, so the callee's verifier ENTRY STATE is
    // identical on every call -- the property the __noinline subprogram needs
    // to be analyzed once and reused. (The verifier does not track the scalar
    // contents of map-value memory, so what the loop reads is irrelevant here;
    // what matters is that the call's argument/entry state stays constant.)
    __u64 acc = 0;
#pragma clang loop unroll(disable)
    for (__u32 j = 0; j < INNER; j++)
        acc += arr->slot[j & SLOT_MASK];
    return acc;
}

SEC("xdp")
int xdp_explode(struct xdp_md *ctx) {
    __u32 key = 0;
    struct arr_value *arr = bpf_map_lookup_elem(&m, &key);
    if (!arr)
        return XDP_ABORTED;

    // ONE static call site, reached OUTER times with the outer induction
    // variable `i` live in the register file. `sink` keeps walk()'s result live
    // but is NEVER fed back into walk(), so the call argument stays constant.
    __u64 sink = 0;
#pragma clang loop unroll(disable)
    for (__u32 i = 0; i < OUTER; i++)
        sink ^= walk(arr);

    return sink & 1 ? XDP_PASS : XDP_DROP;
}

char _license[] SEC("license") = "GPL";

// ---------------------------------------------------------------------------
// WHY inline explodes and noinline passes (kernel 5.10 verifier):
//
//   The verifier prunes a loop re-walk only when it reaches an instruction in a
//   state it has already seen (is_state_visited / states_equal). State includes
//   ALL live registers -- in particular the OUTER induction variable `i`.
//
//   always_inline: walk()'s INNER loop is stamped into the caller. At the inner
//     loop's back-edge the live outer index `i` is part of the compared state.
//     Because `i` takes OUTER distinct values, no inner-loop state matches a
//     prior one, so the verifier re-walks all INNER iterations for every outer
//     value. The cost is processed ~= OUTER * INNER * k, where k is the number
//     of verifier instruction-VISITS per inner source-iteration (index mask +
//     bounds check + load + accumulate + back-edge + state bookkeeping).
//     Measured here: k ~= 13 for INNER >= 100. Note OUTER*INNER alone is only
//     84,000 at the default 280*300 -- ~12x UNDER the limit; it is the k factor
//     that pushes processed over 1,000,000. (Empirically the cap is first hit
//     at OUTER=256 / INNER=300: OUTER=255 loads at 997,068, 256 caps at
//     1,000,001.) -> REJECTED.
//
//   __noinline: walk() is a real BPF-to-BPF subprogram entered via BPF_CALL.
//     check_func_call gives it a FRESH frame whose only input is the constant
//     `arr` pointer argument -- the caller's live `i` is not part of the
//     callee's entry state. The INNER loop is therefore verified ONCE; OUTER
//     only adds a flat per-call cost. Total is ~(inner-loop-once) + OUTER*const,
//     NOT a product -- e.g. 6,742 at 280*300 -> LOADED.
// ---------------------------------------------------------------------------

run_explosion.sh

#!/bin/bash
#
# Build explosion_demo.bpf.c two ways and load each. The always_inline build is
# expected to be REJECTED by the verifier with E2BIG (processed insns > 1M); the
# __noinline build is expected to load.
#
# Usage:  sudo ./run_explosion.sh
set -uo pipefail

cd "$(dirname "$0")"
ARCH=$(uname -m | sed 's/x86_64/x86/;s/aarch64/arm64/')

if [ ! -f vmlinux.h ]; then
    echo "[*] Generating vmlinux.h from kernel BTF..."
    bpftool btf dump file /sys/kernel/btf/vmlinux format c > vmlinux.h
fi

build() {
    local mode=$1 out=$2
    clang -g -O2 -Wall -target bpf -D__TARGET_ARCH_${ARCH} \
        -DINLINE_MODE=${mode} -I. -c explosion_demo.bpf.c -o "${out}"
}

load_and_report() {
    local obj=$1 label=$2
    local pin=/sys/fs/bpf/explosion_${label}
    rm -f "${pin}" 2>/dev/null || true
    local log rc
    log=$(bpftool prog load "${obj}" "${pin}" type xdp -d 2>&1)
    rc=$?
    rm -f "${pin}" 2>/dev/null || true

    echo "===== ${label} ====="
    local insns
    insns=$(llvm-objdump -d "${obj}" 2>/dev/null | grep -cE "^\s+[0-9a-f]+:" || true)
    echo "static instructions in object (prog + .text): ${insns}"
    # processed-insns summary if the verifier printed one
    echo "${log}" | grep -E "processed [0-9]+ insns" | tail -1 || true
    # too-large / rejection line, if any
    echo "${log}" | grep -iE "too large|Processed [0-9]+ insn|argument list too long" | tail -1 || true
    if [ ${rc} -eq 0 ]; then
        echo "RESULT: LOADED (verifier accepted)"
    else
        echo "RESULT: REJECTED (load failed, rc=${rc})"
    fi
    echo
}

echo "[*] Building always_inline variant..."
build 1 explosion.inline.o
echo "[*] Building __noinline variant..."
build 0 explosion.noinline.o

echo
echo "############ VERIFIER COMPLEXITY EXPLOSION ############"
load_and_report explosion.inline.o   inline
load_and_report explosion.noinline.o noinline

echo "Expected: inline REJECTED (processed > 1,000,000 insns => E2BIG),"
echo "          noinline LOADED. If both load, raise N in explosion_demo.bpf.c;"
echo "          if both fail, lower N (the inline build may exceed the 1M static"
echo "          BPF_MAXINSNS limit instead of the complexity limit)."