| Age | Commit message (Collapse) | Author |
|---|
|
Global subprogram arguments tagged __arg_untrusted deliberately
accept any caller value. The callee is verified separately with a
read-only untrusted pointer, whose accesses use protected probe-read
instructions.
Keep the untrusted type in the canonical bpf_subprog_info used to
prepare the callee state. Represent it as ARG_IGNORE only in the
temporary bpf_func_proto used for call-site checking, then extend the
guarded check_func_arg() path to cover it.
Signed-off-by: Amery Hung <ameryhung@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260928185334.1004200-6-ameryhung@gmail.com
|
|
BPF subprogram scalar arguments are checked separately even though the
common argument checker enforces the same SCALAR_VALUE requirement.
Start the migration by routing the scalar branch through check_func_arg()
and update the verifier-log expectation.
Use the BTF parameter index for metadata and the ABI slot index for
register lookup. Route extra slots of by-value aggregates through
check_arg_extra_slot() so every occupied slot follows the common path.
Following patches can extend this guarded common-check branch as each
remaining BPF-subprogram-specific implementation is removed.
Signed-off-by: Amery Hung <ameryhung@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260928185334.1004200-5-ameryhung@gmail.com
|
|
The common argument checker consumes a parameter-indexed bpf_func_proto,
while BPF subprogram argument metadata is cached by ABI slot in compact
bpf_subprog_info entries. Embedding a full prototype in every fixed
subprogram entry would waste memory.
Embed a scratch prototype in the verifier environment. Fill it by
walking BTF parameters and the cached slots with separate cursors,
mirroring the kfunc representation for parameters that occupy multiple
slots. Keep the compact cache as the source of truth. The verifier
environment is already heap allocated, so this avoids a separate
allocation, failure path, and cleanup.
Keep the existing validation loop, but make it consume the generated
prototype in preparation for moving BPF subprogram calls to the common
argument checker. No functional change.
Signed-off-by: Amery Hung <ameryhung@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260928185334.1004200-4-ameryhung@gmail.com
|
|
Prepare subprog calls to use the common check_func_args() path. That
checker distinguishes call kinds through bpf_call_arg_meta, but
btf_check_func_arg_match() leaves both BTF and the function ID zero even
though it validates a program-BTF signature.
Represent a subprog call with a non-NULL BTF and a zero function ID.
Define helpers as NULL BTF plus nonzero ID, and kfuncs as non-NULL BTF
plus nonzero ID. Requiring a nonzero kfunc ID also prevents unavailable
special-kfunc IDs from matching subprog metadata. The corresponding
subprog predicate is introduced later alongside its first use.
Setting BTF would expose checks that treat every BTF-backed call as a
kfunc. Restrict kfunc-only BTF parameter lookup, register admission,
release diagnostics, no-cast alias, and projection handling to actual
kfuncs.
The BTF is not modified here, but bpf_call_arg_meta::btf and several
downstream consumers use non-const pointers. Match those existing types
instead of broadening this series with a const-correctness cleanup.
No functional change is intended.
Signed-off-by: Amery Hung <ameryhung@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260928185334.1004200-3-ameryhung@gmail.com
|
|
Several kfunc argument checks index BTF parameters using the ABI slot
number. Parameter and slot indexes diverge after a by-value argument
wider than one eightbyte, so a later argument can select the wrong BTF
parameter or index past the end of the function prototype.
This affects the BTF lookups in check_func_arg_nullability() and
check_func_arg_release(), and the parameter passed to
btf_check_iter_arg() by process_iter_arg().
check_func_arg() already tracks the BTF parameter and ABI slot
separately. Pass the parameter index to all three consumers while
retaining argno for register and stack-slot diagnostics.
Signed-off-by: Amery Hung <ameryhung@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260928185334.1004200-2-ameryhung@gmail.com
|
|
bpf_tramp_image_put() makes sure a trampoline image is not freed while
a task may still be running in it, but nothing similar is done for the
progs called by that image. Detach drops the last prog reference right
away and the prog is freed after grace periods, on the basis that a
task still in the traced function skips the fexit progs once the nop at
ip_after_call is patched to a jump.
That leaves out a task sleeping in a sleepable prog that runs before
the detached one, which no grace period waits for:
CPU 0 CPU 1
in image I, sleeping in prog S
detach P from I's trampoline
-> new image, bpf_tramp_image_put(I)
bpf_prog_put(P), last ref
grace periods, P freed
back from S
__bpf_prog_enter(P)
call P->bpf_func
If S and P are fexit progs the task is already past the patched jump,
and fentry only images don't have one. On x86 this is an int3 in
poisoned bpf_prog_pack memory:
Oops: int3: 0000 [#1] SMP NOPTI
CPU: 18 UID: 0 PID: 94573 Comm: x169 Not tainted 6.18.44 #1 PREEMPT(lazy)
RIP: 0010:0xffffffffc0601d8d
Call Trace:
<TASK>
? bpf_trampoline_6442515411+0x1a4/0x21b
bpf_lsm_bprm_committed_creds+0x5/0x10
security_bprm_committed_creds+0x5f/0x70
begin_new_exec+0x2d6/0x410
...
We hit this in production when progs attached through trampolines got
detached while their hooks were busy, and it was independently found
with a fuzzer and KASAN.
Have the JITs emit a patchable nop in front of each prog call sequence
and record it in the image. When a prog is detached, patch its nop to a
jump over the call sequence. Progs that stay attached keep running for
the tasks that are in the image, and ip_after_call isn't needed anymore.
The task can be in any image that isn't freed yet, not only in the
current one. It sleeps in image I1 that calls S, P and Q, then P is
detached and the trampoline moves to image I2, then Q is detached and
its call is still in I1. So the trampoline keeps a list of its images
until they are freed, and detaching a prog patches its nop in all of
them. Images hold a reference on the trampoline for that long.
On riscv and loongarch a jump of any range takes several instructions,
and a task preempted in the middle of them could resume into half of the
new sequence. The nop is a single instruction there, patched to a near
branch through arch_bpf_trampoline_skip().
With the extra nops, BPF_MAX_TRAMP_LINKS progs no longer fit in a page
on x86 and arm64 (and already didn't on powerpc), so lower the limit
there like s390 does.
Fixes: e21aa341785c ("bpf: Fix fexit trampoline.")
Reported-by: Sechang Lim <rhkrqnwk98@gmail.com>
Suggested-by: Alexei Starovoitov <ast@kernel.org>
Signed-off-by: Florent Revest (Anthropic) <florent.revest@linux.dev>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260926135605.1217928-3-florent.revest@linux.dev
Closes: https://lore.kernel.org/bpf/20260815071927.147049-1-zirajs7@gmail.com/
|
|
When a prog is detached from a trampoline, it is freed after an RCU
grace period, or an RCU tasks trace one if it is sleepable. This covers
the tasks that are running the prog, since the prog's enter helper takes
the matching read lock before the prog is called. On a preemptible
kernel, it doesn't cover a task that was preempted in the trampoline
just before the enter helper. That task holds no lock yet, and it calls
the prog after it was freed:
BUG: KASAN: vmalloc-out-of-bounds in __bpf_prog_enter_recur+0x3a5/0x3f0
Read of size 8 at addr ffffc90000055040 by task candidate/110
CPU: 1 UID: 0 PID: 110 Comm: candidate Not tainted 7.3.0-rc2-00014-g15071f2a1263-dirty #2 PREEMPT(full)
Call Trace:
<TASK>
__bpf_prog_enter_recur+0x3a5/0x3f0
bpf_trampoline_6442509193+0x37/0xf1
__x64_sys_futex+0x9/0x410
do_syscall_64+0xb0/0x530
...
Wait for an RCU tasks grace period before the existing one when freeing
a prog that was linked to a trampoline. An RCU tasks grace period only
ends once the tasks that were preempted have run again, and
bpf_tramp_image_put() already relies on it to free the image. It doesn't
wait for tasks that sleep in the trampoline, the next commit takes care
of those.
Only progs that were linked to a trampoline can be called this way, so
bpf_trampoline_add_prog() marks them and other progs are still freed as
before.
Fixes: e21aa341785c ("bpf: Fix fexit trampoline.")
Reported-by: Junseo Lim <zirajs7@gmail.com>
Signed-off-by: Florent Revest (Anthropic) <florent.revest@linux.dev>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260926135605.1217928-2-florent.revest@linux.dev
Closes: https://lore.kernel.org/bpf/aqdrwVpanH3WGurX@omen-arch/
|
|
The existing BPF_PROG_STREAM_READ_BY_FD command only supports polling a
program stream through repeated bpf() calls. It cannot block for new data
or integrate with poll-based event loops.
Add BPF_PROG_STREAM_OPEN to return a read-only, close-on-exec file
descriptor for a selected program stream. Reads block by default and
BPF_F_STREAM_NONBLOCK, the only accepted flag, provides non-blocking
behavior. poll reports readable data and reports hangup once the program
has been freed. Like pipes and sockets, the descriptor is not seekable and
lseek fails with ESPIPE.
A stream descriptor deliberately does not retain the program. Move each
stream into a separately refcounted allocation so program teardown can mark
it dead and wake descriptor users while outstanding descriptors drain
buffered data safely. Readers sample the dead flag before looking for data,
so EOF is reported only when the stream was already dead before it was
found empty; data published right before teardown is never skipped.
Only programs loaded through BPF_PROG_LOAD get streams. Classic BPF
filters, JIT subprograms and shim programs never write to one, and
kernel-side writers already resolve a subprogram to its main program, so
those programs no longer carry stream state.
Readiness needs its own counter. Stream capacity is charged before
allocation and before an element is published to the stream log, so using
that reservation as the read and poll condition can report readable data
while no element exists: a blocking reader retries instead of sleeping and
a lone non-blocking reader can see POLLIN followed by EAGAIN. Publish bytes
with release ordering after adding elements to the lockless log, use
acquire loads before consuming them or reporting readiness, limit each read
to its readable snapshot and subtract only bytes actually copied. This
keeps the aggregate count correct even when concurrent publishers update it
out of publication order. With several readers on one stream, readiness
remains advisory, as it is for pipes. The capacity counter is kept solely
for enforcing the stream size limit.
Wakeups are always deferred through irq_work. Stream writers run in
whatever context the program runs in: NMI context for perf_event programs,
sections with interrupts disabled inside bpf_spin_lock or rqspinlock
critical sections since bpf_stream_vprintk() is KF_SPINLOCK_SAFE, and
tracing programs attached anywhere in the kernel, including inside the wait
queue and epoll code itself. Waking waiters directly from there can
deadlock, and no cheap context check covers every case: on PREEMPT_RT,
spinlock_t sections do not disable interrupts, so in_nmi() or
irqs_disabled() cannot tell such a program apart from a benign one. Queue
an irq_work item instead, as bpf_ringbuf does.
Queue it only when a publication turns an empty stream readable. Readers
block and pollers wait only after finding the stream empty, and the
readable count never drops below zero because each read is bounded by its
snapshot, so the first publication after such an observation is the one
that makes the count positive, and it is the one that queues the wakeup.
Publications into a stream that already holds data raise no interrupt, so
a program that prints while nobody drains its stream pays for a single
irq_work until the stream is emptied again. This matches bpf_ringbuf, which
notifies only once the consumer has caught up. Blocking readers and
level-triggered pollers re-check the readable count before waiting, so they
cannot miss data, and edge-triggered epoll consumers drain until EAGAIN
before waiting again, as epoll(7) requires.
Synchronize pending work before releasing the final stream reference so
the callback cannot outlive the stream, but only when the work was ever
queued: irq_work_sync() waits for an RCU grace period on PREEMPT_RT and on
architectures without an irq_work interrupt.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260925045536.1480933-3-memxor@gmail.com
|
|
A stream write whose formatted output is empty still allocates a stream
element and links it into the stream log. Capacity accounting only counts
payload bytes, so such elements never count against the stream limit, and a
program that keeps producing empty output allocates elements without bound
until a reader drains them.
Return success without allocating anything when there is nothing to write,
for both bpf_stream_vprintk() and staged writes. Every element in a stream
log then carries at least one byte, which later changes rely on when they
derive read readiness from published byte counts.
Fixes: 5ab154f1463a ("bpf: Introduce BPF standard streams")
Suggested-by: Emil Tsalapatis <emil@etsalapatis.com>
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260925045536.1480933-2-memxor@gmail.com
|
|
A few patches do not expand in place, they prepend: bpf_convert_ctx_accesses()
puts the ctx save for gen_epilogue and the instructions of gen_prologue in
front of insn 0, and bpf_do_misc_fixups() prepends the may_goto counter init
at the start of every subprog that uses may_goto.
They copy the original instruction of 'tgt_idx' into the last slot of the
patch buffer, so it now lives at tgt_idx + delta, and call adjust_jmp_off()
to move direct branches from tgt_idx to tgt_idx + delta.
Nothing does the same for indirect branches, so a BPF_MAP_TYPE_INSN_ARRAY
slot that named tgt_idx keeps naming tgt_idx, which is now the first prepended
instruction, and insn_aux_data[tgt_idx].indirect_target makes the JIT emit
the landing pad there. Add a __bpf_patch_insn_data() variant and pass
BPF_PATCH_MOVE_TARGET at the affected call-sites to fix up the delta. The
poke descriptors of direct tail calls are shifted the same way, and the
original instruction is not searched for by content in that mode, as it
is the last slot by construction.
Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Fixes: 07ae6c130b46 ("bpf: Add helper to detect indirect jump targets")
Reported-by: Nicholas Carlini <npc@anthropic.com>
Suggested-by: Nicholas Carlini <npc@anthropic.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://patch.msgid.link/20260925175244.1136329-11-daniel@iogearbox.net
|
|
A program that fails after the JIT ran, for example in bpf_check_tail_call(),
has already stored its jitted offsets and target pointers into the insn array
maps it uses through bpf_prog_update_insn_ptrs() when release_insn_arrays()
hands them back by clearing the used flag with a plain atomic_set(). Nothing
orders those stores before the flag, so on a weakly ordered architecture they
can still be in flight when the next program takes the map: it is acquired
with atomic_xchg() in bpf_insn_array_init() and reset there, and the late
stores then land on top of whatever the new owner has written since, be it
that reset or the pointers its own JIT stored, leaving entries that point
into an image which is about to be freed.
Clear the flag with atomic_set_release() instead, so that everything the
releasing program stored is visible before the map can be acquired again.
This pairs with the fully ordered atomic_xchg() on the acquire side.
Fixes: b4ce5923e780 ("bpf, x86: add new map type: instructions array")
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260925175244.1136329-10-daniel@iogearbox.net
|
|
An insn array records, per entry, the xlated offset, the jitted offset and
a jitted target pointer in ips[]. bpf_insn_array_init() runs when the map
is bound to a program and resets only xlated_off; the jitted offset and the
ips[] pointer are left as the previous owner set them. A program can be
verified and JITed and only then fail to load (e.g. bpf_check_tail_call()).
By that point bpf_prog_update_insn_ptrs() has already filled ips[] with
pointers into that program's JIT image. Thus, the map is handed back for
reuse with the stale pointers intact. If the next program reuses the map,
the stale pointer survives in the now active program's jump table,
pointing into the previous, freed image. Fix by resetting the jitted offset
and the ips[] pointer alongside the xlated offset.
Fixes: b4ce5923e780 ("bpf, x86: add new map type: instructions array")
Reported-by: Sandipan Roy <saroy@redhat.com>
Reported-by: James Burton <jamesburton@meta.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://patch.msgid.link/20260925175244.1136329-9-daniel@iogearbox.net
|
|
bpf_opt_remove_nops() drops every ja +0 and may_goto +0 unconditionally.
A gotox target may itself be such a transparent nop: it is a verified
entry of an insn array jump table that is reachable at run time through
the indirect jump. bpf_insn_array_adjust_after_remove() marks it as
INSN_DELETED instead, and bpf_insn_array_ready() skips INSN_DELETED
entries, so the program loads with a hole in its jump table. The x86
JIT, for example, lowers gotox to a raw indirect jump, so executing
that index jumps to the zeroed ips[] slot, that is, to address 0.
Fix by keeping an indirect jump target in place.
Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Reported-by: Sandipan Roy <saroy@redhat.com>
Reported-by: James Burton <jamesburton@meta.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://patch.msgid.link/20260925175244.1136329-8-daniel@iogearbox.net
|
|
The jump table of a subprog is collected in compute_subprog_jts() from the
insn_array maps of the program, and a map is attributed to the subprog that
contains its first entry. check_indirect_jump() instead resolves the targets
from the map the gotox register actually points to, bounded only by the
index range of that register, and never relates them back to the subprog
of the gotox.
The two disagree, so bpf_insn_successors() reports a subset of the edges the
BPF program can take and a gotox can enter a subprog the CFG never walked.
Close both ends: reject a map that reaches past the subprog holding its
first entry right when it is collected in compute_subprog_jts(), so that
every map of a program with a gotox is confined to one subprog, and
confine the resolved targets of a gotox to its subprog in
check_indirect_jump(). A target inside the subprog is then always in the
jump table the CFG walked, which is the invariant that actually has to
hold. The out-of-range check in visit_gotox_insn() cannot fire any more
once every table is confined and becomes a verifier_bug_if().
Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Reported-by: James Burton <jamesburton@meta.com>
Reported-by: Nuoqi Gui <gnq25@mails.tsinghua.edu.cn>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://patch.msgid.link/20260925175244.1136329-7-daniel@iogearbox.net
|
|
create_jt() builds the jump table of the subprogram containing a gotox by
copying out and sorting every insn_array map of the program, and it does
so once per gotox instruction. The cost is therefore the number of gotox
instructions times the number of entries in all of the maps. A program of
4003 instructions with 2000 gotox and one 500k entry map holding two
distinct targets has 4000 indirect jump edges, 0.4% of the limit, and
takes 343s to be rejected. The map costs next to nothing to prepare, as
an unset entry is already a valid target. At the insn limit, with a single
1M entry map, the same shape extrapolates to 41 hours.
All gotox instructions of a subprogram share the same jump table, so
build the table of every subprogram in a single pass over the maps and
let every gotox use it in place: bpf_insn_successors() resolves a gotox
through its containing subprogram, and the tables are kept until the
verifier environment is torn down, so nothing is copied into the
instruction aux data. The edge accounting in visit_gotox_insn() moves
to the first visit of the gotox, marked by the BRANCH bit of its CFG
state, and a revisit returns right away since the first one already
pushed every target that still needed exploring.
The only user left of insn_aux_data[].jt is then the table which
visit_abnormal_return_insn() allocates for tail_call and
ld_{abs,ind} insns, so that bpf_insn_successors() reports the hidden
exit from their subprogram. Both are recognisable by their opcode, so
derive that edge in bpf_insn_successors() from the exit_idx of the
containing subprogram instead, again leaving it out when the subprogram
has no exit, and drop the field along with bpf_clear_insn_aux_data().
The instruction aux data then owns no allocation, thus nothing needs to
be freed when insns are removed or the verifier environment is torn
down.
Subprograms removed as dead code free their table in
adjust_subprog_starts_after_remove(), which also clears the slots that
the compaction of subprog_info vacates, as they still hold copies of the
moved entries and with them their table pointers.
check_cfg() is then linear in the number of map entries plus the number
of indirect jump edges, so what still scales now with the program is what
BPF_MAX_GOTOX_EDGES bounds:
gotox map entries edges before after
----------------------------------------------
500 250000 1000 35.34s 0.07s
1000 250000 2000 82.00s 0.07s
2000 250000 4000 148.62s 0.07s
2000 125000 4000 74.54s 0.05s
2000 500000 4000 342.71s 0.19s
Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260925175244.1136329-6-daniel@iogearbox.net
|
|
visit_abnormal_return_insn() gives tail_call and ld_{abs,ind} insns a
second successor, the exit_idx of their subprogram, so that the hidden
exit from the subprogram is part of the CFG. check_subprogs() only
assigns exit_idx when it walks over a BPF_EXIT, and a subprogram whose
last insn jumps back into itself never has one, so exit_idx stays zero
and the edge points at insn 0 of the program:
0: r0 = 0
1: r0 = *(u8 *)skb[0]
2: goto -2
For a subprogram other than main, update_insn() then reads the liveness
masks at a negative relative index. Such a subprogram can still load
when it leaves through a bpf_throw(), so mark exit_idx as unset in that
case and leave the hidden edge out, as there is no exit for it to reach.
Fixes: e40f5a6bf88a ("bpf: correct stack liveness for tail calls")
Fixes: ee861486e377 ("bpf: Fix ld_{abs,ind} failure path analysis in subprogs")
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260925175244.1136329-5-daniel@iogearbox.net
|
|
adjust_subprog_starts_after_remove() compacts subprog_info[] and the
func_info when whole subprograms are removed as dead code, but leaves
env->exception_callback_subprog alone, so an exception callback declared
through the exception_callback decl tag which sits behind a removed
subprogram keeps its old index. jit_subprogs() then takes the exception
callback from func[] at that index, which is past the end when the
callback was the last subprogram, or another subprogram otherwise.
Rebase the index along with the entries it refers to.
Fixes: b9ae0c9dd0ac ("bpf: Add support for custom exception callbacks")
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260925175244.1136329-4-daniel@iogearbox.net
|
|
Every gotox instruction gets its own copy of the jump table of the subprog
containing it, and each distinct target in that table is a CFG successor
of the instruction. The number of such edges is therefore the number of
gotox instructions times the number of distinct targets, and neither
factor is bounded by anything except the instruction limit.
What is expensive is a BPF prog whose gotox instructions are themselves
the targets, which makes the edge count quadratic. 1024 such gotox are
already ~1e6 edges and about 4s of CPU to load.
Bound the total across the program at BPF_COMPLEXITY_LIMIT_INSNS, aka
the limit on the number of instructions the verifier processes. Progs
with real switch statements are orders of magnitude below this.
This bounds the edges only. Building the jump table of a gotox costs the
number of entries of all insn array maps regardless of how many distinct
targets they hold, which a later patch addresses separately.
Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Reported-by: STAR Labs SG <info@starlabs.sg>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
Link: https://patch.msgid.link/20260925175244.1136329-3-daniel@iogearbox.net
|
|
The iterative Tarjan DFS in bpf_compute_scc() emulates recursion with an
explicit 'dfs' stack: when a successor has not been visited yet, the
successor is pushed and the walk restarts at the top of the loop. On the
way back to a vertex the successor scan starts over at index zero, so a
vertex with k successors rescans up to k successors on each of its up to k
descents, i.e. O(k^2) work.
For ordinary instructions k <= 2 and this is irrelevant. For a gotox the
successors are the jump table of the containing subprogram, whose size is
bounded only by the max_entries of the insn_array map, so k can reach the
1M instruction complexity limit. Loading such a program keeps a CPU busy
in the loop for a very long time before verification even begins.
Record in 'dfs_pos' the successor index each frame stopped at and resume
the scan there. Each edge is therefore examined a bounded number of times
and the walk becomes linear in the number of edges.
Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Reported-by: STAR Labs SG <info@starlabs.sg>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://patch.msgid.link/20260925175244.1136329-2-daniel@iogearbox.net
|
|
check_func_callx() requires a JIT with callx support before it looks at
the register operand. On an architecture whose JIT doesn't support callx,
or when the JIT is disabled, every callx is thus rejected with "JIT
doesn't support callx" or "JIT is required to use callx", including one
whose operand is invalid. The "invalid call insn1" test_verifier test
expects "R0 !read_ok" for callx of an uninitialized register and fails
on s390x:
#79/u invalid call insn1 FAIL
Unexpected error message!
EXP: R0 !read_ok
RES: JIT doesn't support callx
Validate the operand first and require the JIT only for a callx that is
otherwise valid. An invalid callx is then rejected with the same message
on every architecture. This fixes various errors when running selftests
on JITs where callx is unsupported for now.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260925060945.1993547-1-memxor@gmail.com
|
|
bpf_ma_set_dtor() duplicates map->record so that the bpf_mem_alloc
destructor can release the special fields of hash and rhash map elements
once the allocator frees them for good. btf_record_dup() only acquires
references on kernel and module BTF. Fields whose types live in the map
BTF keep pointing into it: a kptr to a local type refers to map->btf,
and a list_head or rb_root field carries a value_rec owned by the struct
meta table of map->btf.
That borrowed state can outlive the map. When RCU callbacks are still in
flight, bpf_mem_alloc_destroy() copies the allocator and defers the final
drain, together with the destructor context, to a workqueue.
bpf_map_free() then frees map->record and drops the map's BTF reference
as soon as map_free() returns. Once the program that loaded the BTF is
gone as well, the BTF is freed while the worker still uses the
duplicate. The worker dereferences it through btf_is_kernel() and
btf_find_struct_meta() in bpf_obj_free_fields() when destroying elements
that were freed under RCU, and through btf_is_kernel() in
btf_record_free() when releasing the context itself:
BUG: KASAN: slab-use-after-free in btf_is_kernel+0x19/0x30
Read of size 1 at addr ffff88811505dce8 by task kworker/u16:2/50
Workqueue: events_unbound free_mem_alloc_deferred
Call Trace:
btf_is_kernel+0x19/0x30
btf_record_free+0xc7/0xf0
htab_dtor_ctx_free+0x1a/0x30
free_mem_alloc_no_barrier+0x39/0x230
free_mem_alloc_deferred+0x2a/0x40
process_scheduled_works+0x5ce/0x9d0
worker_thread+0x42a/0x5e0
kthread+0x1f5/0x230
ret_from_fork+0x1dd/0x390
ret_from_fork_asm+0x1a/0x30
Allocated by task 358:
__kmalloc_cache_noprof+0x287/0x510
btf_new_fd+0xf7/0x3d0
__sys_bpf+0x487/0x840
Freed by task 0:
kfree+0x186/0x560
rcu_core+0x6f6/0xd40
Freeing a map that still holds more elements than the allocator's high
watermark is enough to get there, because the bulk free during teardown
queues the RCU callback that makes bpf_mem_alloc_destroy() defer.
Non-preallocated hash maps and resizable hash maps both register the
destructor and are affected alike.
Keep one reference on the map BTF in the destructor context. Every
non-kernel pointer in the duplicated record is either map->btf or memory
owned by it, so a single reference covers kptrs, list heads, and rb
roots, and mirrors what bpf_map_meta_alloc() does for the duplicated
record of an inner map. Release it only after the duplicated record has
been freed: the worker is preemptible and not in an RCU read-side
critical section, so dropping the last reference first would let the
BTF be freed while btf_record_free() still reads its fields.
Fixes: 1df97a7453ee ("bpf: Register dtor for freeing special fields")
Reported-by: Yuan Chen <chenyuan@kylinos.cn>
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://lore.kernel.org/bpf/20260901062845.1379760-3-chenyuan_fl@163.com
Link: https://patch.msgid.link/20260925064652.2261885-1-memxor@gmail.com
|
|
check_stack_range_initialized() takes the spilled register path when
bpf_is_spilled_reg(ss) holds, which, however, only looks at the last
byte of the slot. Hence, a partially spilled scalar (on the lower part)
bypasses the check and the following loads:
0: (b7) r1 = 1 ; R1=1
1: (63) *(u32 *)(r10 -8) = r1 ; R1=1 R10=fp0 fp-8=????1
2: (18) r1 = 0x0 ; R1=map_ptr(map=rb,ks=0,vs=0)
4: (bf) r2 = r10 ; R2=fp0 R10=fp0
5: (07) r2 += -8 ; R2=fp-8
6: (b7) r3 = 8 ; R3=8
7: (b7) r4 = 0 ; R4=0
8: (85) call bpf_ringbuf_output#130
...
When executed, it dumps the uninit four bytes:
RINGBUF: 01 00 00 00 ff ff ff ff
This is the same root cause as the non-fetch atomic case fixed in
commit 5a84b4424db8 ("bpf: Fix uninit read for non-fetch atomics on
partially spilled slots").
Fix by only taking the spilled register path for the bytes marked
STACK_SPILL, so the rest of the slot goes through the usual checks.
Fixes: 354e8f1970f8 ("bpf: Support <8-byte scalar spill and refill")
Suggested-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Hao Sun <sunhao.th@gmail.com>
Link: https://lore.kernel.org/bpf/20260925082814.1554771-1-sunhao.th@gmail.com
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
|
|
bpf_jit_blind_insn() rewrites 'if rX op imm goto off' into:
AX = imm ^ rnd
AX ^= rnd
if rX op AX goto off
and subtracts 2 from off when the jump is backward. off is s16, so
-32767 and -32768 wrap and the jump goes 32767 insns forward, past the
end of the prog. The jump is inside the patch, hence bpf_adj_branches()
doesn't check it. The kernel crashes when such prog runs with
bpf_jit_harden=2.
Return -ERANGE in such case. bpf_jit_blind_constants() fails the same
way when blinding of other insns moves a jump out of range.
Fixes: 4f3446bb809f ("bpf: add generic constant blinding for use in jits")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://lore.kernel.org/bpf/20260924182353.277516-1-alexei.starovoitov@gmail.com
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
|
|
check_stack_read_fixed_off() skips partial spill checks for non-fetch
atomics; the following prog can be loaded:
0: (b7) r1 = 1 ; R1=1
1: (63) *(u32 *)(r10 -8) = r1 ; R1=1 R10=fp0 fp-8=????1
2: (db) lock *(u64 *)(r10 -8) += r1 ; R1=1 R10=fp0 fp-8=mmmmmmmm
3: (79) r0 = *(u64 *)(r10 -8) ; R0=scalar() R10=fp0 fp-8=mmmmmmmm
4: (77) r0 >>= 32 ; R0=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
5: (95) exit
When test run:
retval=4294967295
Note fp-8 is ????1 at #1, yet it becomes fp-8=mmmmmmmm after the
non-fetching atomic add at #2; hence the high 32 bits are leaked.
Fix by applying the partial load check; after the patch, the
prog is rejected:
Verification failed: Memory Safety: Uninitialized stack read
Reason:
This rejected read uses 8 bytes at stack offset -8, but byte 4 in that range is uninitialized on
this path. Programs loaded with CAP_PERFMON can be allowed to read uninitialized stack bytes, but
this program is being rejected without that allowance.
At:
...
0 | (b7) r1 = 1
1 | (63) *(u32 *)(r10 -8) = r1
>>> 2 | (db) lock *(u64 *)(r10 -8) += r1
3 | (79) r0 = *(u64 *)(r10 -8)
4 | (77) r0 >>= 32
This affects CAP_BPF only.
Fixes: 354e8f1970f8 ("bpf: Support <8-byte scalar spill and refill")
Signed-off-by: Hao Sun <sunhao.th@gmail.com>
Link: https://lore.kernel.org/bpf/20260924131342.934290-1-sunhao.th@gmail.com
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
|
|
When the verifier reaches bpf_iter_*_next() in a state that is equal to
a state that is still being explored it concludes that the loop
converged, since an active iterator will be drained eventually.
states_equal() matches ids through idmap, so the same is concluded for
an iterator that was destroyed and created again since the old state:
bpf_iter_num_new(&it, 0, 10);
loop:
if (bpf_ktime_get_ns())
goto remake;
next:
if (!bpf_iter_num_next(&it))
goto out;
goto loop;
remake:
bpf_iter_num_destroy(&it);
bpf_iter_num_new(&it, 0, 10);
goto next;
Such prog is accepted when the call of bpf_iter_num_next() is the first
prune point after bpf_iter_num_new() and it never returns. Otherwise
it's rejected with "infinite loop detected".
Require the iterator to have the same id in both states.
Fixes: 06accc8779c1 ("bpf: add support for open-coded iterator loops")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924233130.1213812-8-alexei.starovoitov@gmail.com
|
|
may_goto is expanded into 'if AX == 0 goto off + 5' when it's timed,
off + 2 when it's not and off - 1 when it jumps backward. The sum is
stored into 16-bit off without a range check, so may_goto +32763
turns into:
if r12 == 0x0 goto pc-32768
and the prog jumps backward when may_goto expires.
Emit 'if AX != 0 goto +1; gotol' when the offset doesn't fit and
compute the offset from the number of insns in the expansion.
JITs that don't support gotol will reject such prog.
Fixes: 011832b97b31 ("bpf: Introduce may_goto instruction")
Fixes: e723608bf428 ("bpf: Add verifier support for timed may_goto")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924233130.1213812-6-alexei.starovoitov@gmail.com
|
|
bpf_do_misc_fixups() inits may_goto count by patching the first insn
of a subprog with [ST, ST, first insn]. bpf_convert_ctx_accesses()
patches insn that needs a barrier with [nospec, insn].
bpf_adj_branches() doesn't adjust insns inside the patch, so when
the copy is a call, ld_imm64 of a func or a jump that points backward
its target is off by the number of insns in front of it:
static int A(void) { return 1; }
static int A2(void) { return 2; }
static int B(void)
{
int i, ret = A();
for (i = 0; i < 10 && can_loop; i++)
...
return ret;
}
When A is placed in front of B and may_goto is timed 'call A' becomes
call of A + 2. B returns 2 when A + 2 is the start of A2. Otherwise
the prog is rejected with "verifier bug: No program to jit at insn".
Add bpf_adj_moved_insn() and use it for both copies.
Fixes: 011832b97b31 ("bpf: Introduce may_goto instruction")
Fixes: d6f1c85f2253 ("bpf: Fall back to nospec for Spectre v1")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924233130.1213812-4-alexei.starovoitov@gmail.com
|
|
push_async_cb() sets in_async_callback_fn and async_entry_cnt on the
callback's own frame, which is frame 0 of the fresh state it starts, and
setup_func_entry() copies neither, so a subprog called by the callback
carries neither. Two places read them from the innermost frame instead.
is_state_visited() skips the infinite loop check when two states differ
in async_entry_cnt, because seeing the same state on a second entry into
an async callback is not a loop. A callback which re-arms itself and
calls a subprog therefore compares the two entries at a loop inside that
subprog, where the innermost frame is the subprog's and has no flag set,
and the state is rejected:
infinite loop detected at insn 60
push_callback_call() numbers a new entry as the caller's count plus one.
When the callback re-arms itself from a subprog, the caller is that
subprog's frame with a count of 0, so every entry is numbered 1, the
check above never sees a difference, and a loop anywhere in such a
callback is rejected the same way.
Read the flag and the count from frame 0 in both places. A loop within a
single entry still has a matching count and is still caught, and frame 0
of a non-async state does not have the flag set, so nothing else changes.
The two other readers are already correct: check_return_code() reads
frame[0], and the one in do_check() is reached only after an early return
for curframe != 0.
Fixes: bfc6bb74e4f1 ("bpf: Implement verifier support for validation of async callbacks.")
Signed-off-by: Puranjay Mohan <puranjay@kernel.org>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924162609.1746610-2-puranjay@kernel.org
|
|
Extend direct cgroup program queries to merge
(pl->flags & BPF_F_PREORDER) with the cgroup-wide flags when copying
prog_attach_flags to user space. Only BPF_F_PREORDER is extracted from
pl->flags to ensure transient positioning flags (such as BPF_F_BEFORE,
BPF_F_AFTER, BPF_F_ID, or BPF_F_REPLACE) are not leaked to user space.
This can introduce new prog_attach_flags[] values with BPF_F_PREORDER
set, for example 0x40 (BPF_F_PREORDER), 0x41
(BPF_F_ALLOW_OVERRIDE | BPF_F_PREORDER), or 0x42
(BPF_F_ALLOW_MULTI | BPF_F_PREORDER), depending on the cgroup-wide
attachment mode.
Older bpftool versions treat such combinations as unknown flags;
bpftool support is updated later in this series.
Signed-off-by: Hui Su <sh_def@163.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260922025442.3176057-2-sh_def@163.com
|
|
A sleepable kfunc call can fail either because the program is not
sleepable or because an otherwise sleepable program has entered a
non-sleepable critical section. check_kfunc_call() checks these
conditions separately. The first check is only gated by in_sleepable(),
so the shared diagnostic can blame an active RCU, preemption-disabled,
IRQ-disabled, or locked region even though leaving that region would not
make the program sleepable. Adding a second diagnostic entry point only
to force the program context would duplicate the API.
Reject the call once based on in_sleepable_context(). Teach the shared
bpf_diag_ctx_forbidden() reporter and non_sleepable_context_description()
to consider active RCU, preempt, IRQ, and lock regions only when the
program is sleepable, and to fall back to the non-sleepable program
otherwise. A non-sleepable program can still hold that context state, so
relying on the existing no-context fallback alone would keep blaming the
critical section.
Select the suggestion at the kfunc, helper, and global-function sites
according to that cause, and choose between the two existing kfunc
verifier messages the same way, so a sleepable program is told to leave
the critical section and a non-sleepable program is told to become
sleepable.
This avoids a diagnostic-only wrapper while retaining context history for
sleepable programs that enter a forbidden region.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://lore.kernel.org/bpf/2e42a1a2bf45f4d2aba7495bdc9f147558055740e2f3c8b9dae255f6c57fc13c@mail.kernel.org/
Link: https://patch.msgid.link/20260924170646.2366016-5-memxor@gmail.com
|
|
diag_record_mod() suppresses lineage-preserving register writes when the
diagnostic snapshot is unchanged. This is reachable for ALU operations that
do not change the represented type or bounds, avoiding a redundant history
event while retaining the register's earlier lineage.
The condition appears to extend this suppression to spill events, but
diag_mod_keeps_lineage() only accepts register writes. The spill producer also
supplies a stack target and an explicit origin, so a spill can never satisfy
the conjunction.
Restrict the condition to writes to reflect the filter's actual contract and
avoid suggesting that it applies to spills.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://lore.kernel.org/bpf/48e6f021b89562f68850fe21ef8c78719819b04cf9c4e4f50bc791937d37ace8@mail.kernel.org/
Link: https://patch.msgid.link/20260924170646.2366016-4-memxor@gmail.com
|
|
Verifier memory diagnostics currently label every fixed-offset stack
read rejected by check_stack_read_fixed_off() as uninitialized. Dynptr,
iterator, and IRQ-flag slots instead contain initialized
verifier-managed state, so the report incorrectly suggests
initialization or CAP_PERFMON.
The variable-offset read without a destination register is currently
reached by atomic read-modify-write instructions, but that follows from
the call sites rather than the check_stack_read() interface. Its
diagnostic also attributes the access to a helper.
Classify rejected stack reads by slot type. Retain the existing
uninitialized report for STACK_INVALID, and describe verifier-managed
slots as opaque state. Use instruction-neutral wording for the
variable-offset read while leaving the existing verifier messages
unchanged.
Reported-by: Sashiko <sashiko-bot@kernel.org>
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://lore.kernel.org/bpf/20260815065956.49D2B1F000E9@smtp.kernel.org/
Link: https://patch.msgid.link/20260924170646.2366016-2-memxor@gmail.com
|
|
Commit 9f3d900a69be ("bpf: Grow the verifier id scratch on demand") turned
the id map comparing the ids of two states, which also serves as the id
stack of release_reference() and as the id set of
bpf_clear_singular_ids(), into arrays grown on demand, so that the env
would not embed a map sized for 2 KiB frames. That gave the map a way to
fail, and with it release_reference() and the iterator destroy path an
-ENOMEM to hand up, states_equal() a case where states compare unequal
for lack of memory, and bpf_clear_singular_ids() a flag to keep every id
when the set could not record them all.
The env is allocated once per program load, so the map can afford to be
sized for the largest state again: MAX_BPF_STACK_SLOTS in each of
MAX_CALL_FRAMES frames, which a state on a private stack can reach since
every frame there may use the whole budget. That makes the map 34 KiB
instead of 10 KiB, a small price per load for having no growth that can
fail. Make the map and the set a fixed union in the env again and drop
the growth and its failure handling.
Suggested-by: Alexei Starovoitov <ast@kernel.org>
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://lore.kernel.org/bpf/DLNQW1IRYK94.1DP0M5VKZSY32@gmail.com
Link: https://patch.msgid.link/20260924193403.3032037-1-memxor@gmail.com
|
|
BPF crypto was implemented using the lskcipher API, which doesn't seem
to be going anywhere. lskcipher supports only ARC4 and block ciphers in
CBC and ECB mode, and only with unoptimized implementations.
Library APIs also have been found to be a much better approach, for a
variety of reasons, including reduced overhead, greater flexibility, and
having to be explicit about the crypto algorithms that are supported.
We can safely ignore the theoretical ARC4 and non-AES block cipher
support in BPF crypto as unused, which leaves AES-CBC and AES-ECB.
AES-CBC was stated to be needed for decrypting packets using a homebrew
UDP-based protocol
(https://lore.kernel.org/r/d1cdfc23-b336-49a9-8833-29f05b5b9fec@linux.dev/).
AES-ECB is used by the BPF self-tests, and it was stated to maybe be
used in the future for QUIC-LB
(https://lore.kernel.org/r/5f9c3aab-5339-463c-a86d-edac297e1e95@linux.dev/).
Those reasons don't make much sense either, especially AES-ECB which
isn't appropriate in new systems and should be dropped. Regardless,
let's assume that both AES-CBC and AES-ECB need to be kept for now.
There are library APIs for both of these now, which are much easier to
use and more efficient. Reimplement BPF crypto on top of them, greatly
simplifying the code. As part of this, the bpf_crypto_type abstraction
layer is removed, as it's not useful.
This removes the only user of the lskcipher API, so follow-up patches
will be able to remove that code as well.
Signed-off-by: Eric Biggers <ebiggers@kernel.org>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924184254.142720-1-ebiggers@kernel.org
|
|
The verifier checks every stack access and the combined depth of a call
chain against MAX_BPF_STACK, which is also the frame size of the
interpreter and the frame that JITs without subprogram tail call
support set up for tail-call targets. A JIT that lays out frames of any
size and lets a tail-called program set up its own frame does not need
that limit; it only needs the verifier to bound how much stack a
program uses in total.
Add bpf_jit_supports_large_stack() for a JIT to claim that, and give
each program its budget through bpf_prog_stack_limit(): MAX_BPF_STACK_JIT
when the JIT is requested, the program is not offloaded and the JIT
supports large stacks as well as tail calls from subprograms,
MAX_BPF_STACK otherwise. The latter is what lets a tail-called program
set up its own frame: without it, do_misc_fixups() gives every program
with tail calls a MAX_BPF_STACK frame, which a deeper frame verified
against the larger budget would overrun. The verifier keeps the budget
in env->stack_limit and uses it for the bounds of fixed and variable
offset stack accesses, for unprivileged stack pointer arithmetic and its
speculation limit, and for the combined and private stack depth checks.
A frame may use any part of its program's budget. The interpreter paths
keep MAX_BPF_STACK: a program whose main frame is deeper falls back to
the JIT-required path of bpf_prog_select_runtime() and one with deeper
subprogram frames is rejected when patching calls for the interpreter.
The extra stack that may_goto and the timed may_goto instrumentation
add below a frame is, as before, not counted against the budget of a
JITed program and rejected past MAX_BPF_STACK for an interpreted one.
Stack liveness treats a read through a pointer of unknown offset, or a
call passing a frame pointer to a subprogram, as reaching the whole
frame, and widens the masks of that frame to the deepest half-slot such
a read can cover. Bound that by the program's budget too: no access
past it is accepted, so a program kept at MAX_BPF_STACK carries masks
of two words for such frames, as before, instead of the eight that
MAX_BPF_STACK_JIT needs. The three selftests matching a whole-frame
read in the liveness log accept either depth.
bpf_clone_redirect() transmits from inside the program, and a tc egress
or lwt_xmit program that redirects to its own device runs again on top
of its own frame until the datapath's recursion limit drops the packet,
ten frames deep. Ten MAX_BPF_STACK frames fit the kernel stack as they
always did; ten MAX_BPF_STACK_JIT frames would not, so a program that
calls bpf_clone_redirect() keeps MAX_BPF_STACK. The redirect helpers
that transmit after the program has returned leave no frame behind and
do not affect the budget. Nesting through other attach points is not
accounted, as before.
The spill tracker of the liveness analysis follows no slot past the
budget either.
The capability is a boolean and the budget a single constant, in the
style of the other bpf_jit_supports_*() queries, rather than a per JIT
size: the budget is meant to be the same everywhere it is raised, so
that programs verify identically across those architectures.
No JIT declares support yet, so every program keeps its 512-byte budget.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-14-memxor@gmail.com
|
|
The verifier keeps a few structures whose size follows the deepest
frame a program may have: the backtracking and scratched-slot bitmaps,
the jump history slot index and the clamp of the liveness masks. They
are all expressed through MAX_BPF_STACK_SLOTS, which derives from
MAX_BPF_STACK, the frame size of the interpreter.
Introduce MAX_BPF_STACK_JIT, the stack budget a program may get on a
JIT that can lay out frames of any size, and derive those structures
from it so that a frame may be as deep as that budget. Nothing grants
the budget yet, so no program verifies differently; the only visible
change is that the liveness log prints a whole-frame read up to the new
depth, so the three selftests matching such reads are updated.
The spill tracker of the liveness analysis keeps a table entry per
instruction and tracked slot, so it follows more than the 64 slots of a
MAX_BPF_STACK frame only while that table stays within what 64 slots
need for the largest program; a subprog of a million instructions keeps
64, one of a quarter million may track all 256. This bounds the table
at its old worst case of 640 MiB instead of letting a single deep store
push it past what kvmalloc() serves.
The backtracking and scratched-slot bitmaps grow from one to four
words per frame, a fixed few hundred bytes per verifier environment.
tmp_str_buf, which formats a frame's slot list for the log, grows from
320 to 1408 bytes so that all 256 slots still fit, and the log's line
buffer from 1 to 2 KiB so that a line built from it is not cut; the
environment stays within its 64 KiB allocation. The liveness masks are
only as wide as the stack a frame uses, so most frames cost the same as
before; a frame that is read as a whole, through a pointer of unknown
offset or by bpf_loop() with two callbacks, now carries masks of eight
words, 192 bytes per instruction per frame instead of 48. Measured over
the 5075 selftest programs, that is 0.2% of the total peak verifier
memory: strobemeta_bpf_loop and pyperf600_bpf_loop grow by 11% (1.2 MiB
and 0.6 MiB), a few dozen small programs by 40 to 100 KiB each,
everything else is unchanged. The next patch bounds such reads by the
program's budget, so this cost is only paid once a JIT grants it.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-13-memxor@gmail.com
|
|
The id map used to compare the ids of two states, which also serves as
the id stack of release_reference() and as the id set of
bpf_clear_singular_ids(), is a fixed array embedded in struct
bpf_verifier_env and sized for the most registers and stack slots a
state can possibly hold: 1312 entries, 10 KiB, for 512-byte frames, and
four times that once frames may reach 2 KiB, which pushes the env
allocation from 64 KiB to 128 KiB for every program verified. States
compare a few dozen ids in practice.
Turn the map and the set into arrays grown on demand, starting at 64
entries and doubling, and free them with the env. A map that cannot
grow treats the states as different, an id set that cannot grow keeps
every id of the state, since its counts are then incomplete, and the id
stack reports -ENOMEM, which release_reference()
hands to its callers. The iterator destroy path used to warn on any
failure of release_reference(), which could only come from a bug while
the id stack could not run out of room; it now returns -ENOMEM and
keeps warning about anything else. An allocation failure thus fails
the load and is never unsafe. This removes the last structure whose
size scaled with the stack bound and shrinks the env by 10 KiB.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-9-memxor@gmail.com
|
|
Stack liveness tracks three masks of 4-byte stack slots - may_read,
must_write and live_before - for every instruction of every frame of
every function instance. Each mask used to be a fixed 128-bit spis_t,
wide enough for the deepest frame MAX_BPF_STACK allows, so an
instruction paid 48 bytes per frame no matter how little stack the frame
actually touched. These per instruction arrays are the largest liveness
allocation: a 40k instruction program spends ~2 MiB on each frame array.
Sizing them for a larger stack budget would multiply that cost for every
program, while most frames use a fraction of the budget.
Replace the fixed masks with a variable width bitmap array per
(instance, frame). struct frame_masks holds the width shared by all of
its masks in @words plus a flat unsigned long array, where mask @kind of
the instruction at relative index @i lives at
&bits[(i * FM_MASK_CNT + kind) * words]. An array starts at the width
the first recorded half-slot needs (minimum one word, that is 256 bytes
of stack with 64-bit words) and is reallocated into a wider stride once
a deeper half-slot shows up. Only the marking functions widen an array,
and they all run during the static analysis before do_check(), so no
verification time path can move one.
The marking API now takes an inclusive half-slot range, which is what
record_stack_access_off() computed anyway, and clamps the upper end to
the deepest half-slot a frame can have. An access below the stack bound
is rejected by the main verifier pass later; liveness only has to stay
inside the masks. A range that covers no whole half-slot, as a byte
store at fp-1 produces, marks nothing.
A "read everything" mark, used for calls that are neither helpers nor
kfuncs and for pointers whose offset or frame identity was lost, widens
the array to the maximum width and sets every bit: recorded at a
narrower width it would lose the half-slots a later widening adds, and
no write can cancel it as no write covers the whole frame. A half-slot
past the width of the masks was never read by the frame and is never
live.
merge_instances() may see a different width on each side, so it widens
dst to cover src and counts a word only dst has as zero on the src
side, which unions into may_read as a no-op and intersects must_write
to empty, never claiming a write that did not happen.
The rest is mechanical: update_insn() propagates live_before word by
word over the array's width (all instructions of one array share it,
hence so do an instruction's successors), is_live_before() answers
false past the width, and the use:/def: log printing iterates up to the
width.
Liveness results are unchanged. A half-slot only ever gets a bit from a
recorded access and recording one widens the array to cover it, so every
bit the fixed masks could hold still fits. Frames whose deepest recorded
half-slot fits in a single word now cost 24 bytes per instruction per
frame instead of 48.
The spill tracker that feeds the analysis had the same limit built in: it
followed 64 slots, fp-8 to fp-512, per subprog, and a fill from a deeper
slot returned an imprecise pointer, so every later access through it
counted as a read of the whole stack of every frame. Let it follow the
deepest 8-byte access a subprog makes directly through R10 when that
reaches past those 64 slots, which is how spills and fills are compiled,
and keep the count with the per-callsite snapshot a callee uses to fill
from its caller's frame. Programs within 512 bytes are tracked exactly as
before; a program spilling deeper stays precise.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-8-memxor@gmail.com
|
|
When the size of a helper or kfunc memory argument is not a constant on
the path, the stack liveness analysis is told the call reads
MAX_BPF_STACK bytes starting at the pointer's offset. Clipped at the
top of the frame this covers everything from the offset upwards, which
is the intent, but only as long as no frame is deeper than
MAX_BPF_STACK bytes.
Return the "unknown" marker instead, which the liveness analysis already
turns into a read of every slot between the offset and the frame top,
independent of how deep the frame is.
No functional change.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-7-memxor@gmail.com
|
|
Precision backtracking keeps the stack slots that still need a precise
mark in one u64 per frame, which ties it to frames of at most 64 slots.
Turn the per-frame masks into bitmaps sized by MAX_BPF_STACK_SLOTS and
use the bitmap helpers for setting, clearing, testing and iterating
them. The formatting helper takes a bitmap and the leftover-slot bug
reports print the formatted slot list instead of a hex mask.
mark_reg_stack_read() collected zero spills in a u64 of its own before
handing it to the backtracker; it now counts them and revisits the
range to mark each slot, which drops the only remaining mask-typed
entry point.
No functional change.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-5-memxor@gmail.com
|
|
Linked scalar registers are recorded in the jump history packed into a
u64 as five 11-bit entries, each naming a frame and a register or stack
slot. The 6-bit slot field covers exactly the 64 slots of a 512-byte
frame, so a spilled scalar in a deeper slot could not be linked and
larger frames were ruled out by construction.
Store the linked registers as an array of five u16 entries plus a count
instead, each entry holding the frame number, a register-or-slot bit
and an 11-bit register or slot index, which covers frames of up to
16 KiB. Callers that record no linked registers pass NULL.
The history entry grows from 16 to 20 bytes, and the history is the
one verifier structure whose size follows the number of instructions a
loop iterates over rather than the state count. Measured over the 5075
selftest programs, peak verifier memory is unchanged for all but the
loop-heavy ones, which grow by 8 to 16%: loop1/nested_loops from 17.6 to
19.2 MiB, verifier_loops1/jumps_out_rather_than_in from 4.4 to 5.1 MiB,
strobemeta by 0.3% and pyperf600_nounroll by 0.8%. Verdicts, processed
instructions and state counts stay the same everywhere.
No functional change.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-4-memxor@gmail.com
|
|
The verifier indexes a frame's stack state directly through
state->stack[spi] and computes the number of tracked slots as
allocated_stack / BPF_REG_SIZE in every file that touches stack slots,
and so does the nfp offload driver. Route all of these through two
helpers, bpf_stack_slot() and bpf_stack_nr_slots(), so the layout of the
per-frame stack state is visible in one place. The one lookup that goes
the other way, reg_to_target() in the diagnostics code, maps a register
pointer back to its slot by address and now says that it relies on the
slots forming one contiguous array. Both helpers take a const frame: the
slot accessor returns the slot through the frame's stack pointer, so
read-only code such as the state printer can use it without giving up
its qualifiers. Functions that look up the same slot repeatedly now
fetch it once.
No functional change.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-2-memxor@gmail.com
|
|
When the verifier inlines a bpf_fastcall helper or kfunc, it removes the
spill/fill pairs that clang emitted around the call and lowers the
subprogram's stack depth so that their slots are no longer part of the
frame. This is only safe if nothing else accesses those slots or any slot
below them. check_fastcall_stack_contract() enforces this: an access to
that region from outside a fastcall pattern disables the rewrite for the
subprogram. It is called from the four stack load and store paths, and
two kinds of access escape it.
Stack buffers passed to helpers and kfuncs are validated by
check_stack_range_initialized(), which does not call it. If such a buffer
is the only other access to the region, the rewrite is still applied, the
JIT reserves a frame that does not contain the buffer, and the helper
reads or writes live kernel stack below the program's frame. For example,
without CAP_PERFMON:
*(u64 *)(r10 - 8) = r1;
call bpf_get_smp_processor_id;
r1 = *(u64 *)(r10 - 8);
r2 = 0;
r3 = r10;
r3 += -64;
r4 = 8;
call bpf_skb_load_bytes;
is accepted with a stack depth of 0 instead of 64.
Some buffers got the check indirectly. For constant-sized outputs in raw
mode, mark_raw_stack() marks the buffer initialized through ordinary
byte stores, which call the check. Commit 5da4a9f26fca ("bpf: Preserve
stack initialization for generic output buffers") limited raw mode to
programs that may read uninitialized stack, so outputs of programs
without CAP_PERFMON lost the check, as in the example above. Buffers
that never used raw mode have lacked the check since fastcall support
was added: helper inputs such as a map key whose only store is a fastcall
spill, variable-sized outputs, and buffers at a variable stack offset.
check_stack_read_fixed_off() applies the check to the current frame,
even when the pointer targets a caller's stack. A callee can therefore
read a caller's fastcall spill slot without disabling the caller's
rewrite:
caller:
r1 = 1;
*(u64 *)(r10 - 8) = r1;
call bpf_get_smp_processor_id;
r1 = *(u64 *)(r10 - 8);
r1 = r10;
r1 += -8;
call callee;
callee:
r0 = *(u64 *)(r1 + 0);
The caller's spill and fill are removed and its stack depth drops to 0,
but the verifier still tracks the slot as holding the spilled constant.
The callee's load then reads kernel stack outside the caller's frame,
while the verifier assumes r0 is 1.
Every stack access first goes through check_stack_access_within_bounds():
loads and stores from check_mem_access(), helper and kfunc buffers from
check_stack_range_initialized(), and the dynptr, iterator and irq flag
slots that kfuncs initialize, whose handlers use check_mem_access(). It
resolves the frame that owns the slots and the lowest offset the access
can touch, and it is the only place where a frame's stack depth grows.
Check the contract there, once for every access, and drop the calls from
the stack read and write paths. Zero-sized buffers touch no stack and
leave the rewrite enabled.
Fixes: 5b5f51bff1b6 ("bpf: no_caller_saved_registers attribute for helper calls")
Fixes: 5da4a9f26fca ("bpf: Preserve stack initialization for generic output buffers")
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://lore.kernel.org/bpf/85f9995a43edb70c76615280e103dc5325742e88330f36c97962ee35f17e3e32@mail.kernel.org
Link: https://patch.msgid.link/20260924075352.2343553-2-memxor@gmail.com
|
|
Cross-merge BPF and other fixes after downstream PR.
Conflicts:
kernel/bpf/helpers.c
tools/testing/selftests/bpf/prog_tests/cb_refs.c
tools/testing/selftests/bpf/prog_tests/verifier.c
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
|
|
Add BTF_KIND_LOC_PARAM, BTF_KIND_LOC_PROTO and BTF_KIND_LOCSEC
to help represent location information for functions.
BTF_KIND_LOC_PARAM is used to represent how we retrieve data at a
location; either via register(s), or register+offset, a dereference
of a register+offset or a constant value.
BTF_KIND_LOC_PROTO represents location information about a location
with multiple BTF_KIND_LOC_PARAMs.
And finally BTF_KIND_LOCSEC is a set of location sites, each
of which has
- a BTF_KIND_FUNC function associated with the inline site
- a location prototype specifying where to find the function
parameters
- an address offset relative to the kernel base address
This can be used to support representing
- a fully-inlined function at potentially multiple inline sites
with potentially different parameter availability
- a partially-inlined function where some _LOC_PROTOs represent
inlined sites as above and others have normal _FUNC representations
Also BTF_KIND_LOCSEC struct btf_loc will have two type id
references; one for the associated func, the other for the loc_proto.
Accordingly increase the number of m_offs references in btf_field_desc
to 2.
Signed-off-by: Alan Maguire <alan.maguire@oracle.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://patch.msgid.link/20260924111428.75957-2-alan.maguire@oracle.com
|
|
pcpu_init_value() initializes the per-cpu area of a newly created
[lru_]percpu_hash element. The area is recycled, so when the value
comes from a BPF program (onallcpus == false) it writes the running
CPU's slot and zeroes the rest.
bpf_percpu_hash_update() passes onallcpus == true, which delegates to
pcpu_copy_value(). pcpu_copy_value() writes only the CPU named in
map_flags when BPF_F_CPU is set, so on the create path the other slots
keep the recycled element's values:
update(k1, 0xdeadc0de, BPF_F_ALL_CPUS) every CPU holds 0xdeadc0de
delete(k1) element back on the freelist
update(k2, 0xc0ffee, BPF_F_CPU | 0) creates, writes CPU 0 only
lookup(k2) CPU 0 0xc0ffee, rest 0xdeadc0de
Zero-fill the other CPUs on that arm too.
Fixes: c6936161fd55 ("bpf: Add BPF_F_CPU and BPF_F_ALL_CPUS flags support for percpu_hash and lru_percpu_hash maps")
Signed-off-by: Donggeun Yoo <donggeunyoo.kernel@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924102321.2120434-2-donggeunyoo.kernel@gmail.com
|
|
The is_extended / prog_array_member_cnt protocol introduced by commit
d6083f040d5d ("bpf: Prevent tailcall infinite loop caused by freplace")
keeps a prog extended by a freplace program out of prog_array maps, and
vice versa: once a tail call re-enters an extended subprogram, its
tail_call_cnt resets on every execution and the loop never terminates.
But is_extended is a plain boolean, while one target prog can carry
several freplace links at the same time, one on its entry and one on a
global subprogram. __bpf_trampoline_unlink_prog() cleared is_extended
whenever *any* freplace link detached, so detaching one of two links
re-armed the unbounded loop through the remaining one.
Replace the is_extended boolean with a count of the freplace links
attached to each target prog, so the target stays extended until its
last link detaches. Also rename bpf_freplace_check_tgt_prog() to
bpf_freplace_link_tgt_prog(), as the helper has never been a pure
check: it reserves the target prog on success.
Fixes: d6083f040d5d ("bpf: Prevent tailcall infinite loop caused by freplace")
Signed-off-by: Yuan Chen <chenyuan@kylinos.cn>
Acked-by: Jiri Olsa <jolsa@kernel.org>
Link: https://lore.kernel.org/bpf/20260924023737.1140521-2-chenyuan_fl@163.com
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
|
|
Compilers put pointers to functions into read-only data: tables of
functions, struct ops, vtables, where they're mixed with sizes,
alignments and other data. Rust vtables are like that.
Let callx call through them:
r6 = vtable ll
r1 = *(u64 *)(r6 + 0) // data
r2 = *(u64 *)(r6 + 8) // pointer to a function
callx r2
libbpf keeps such data in a frozen read-only array map like .rodata and
stores the byte offset of static function within the program into
the pointer. The kernel guesses: aligned 64-bit value that is equal to
the offset of a static subprog is a pointer to it. If the guess is wrong
the program either fails to load, since it uses a pointer as a number,
or sees an address instead of the number. Safe either way.
Add resolve_func_ptrs() that scans such maps of a program with callx
after the maps are resolved and before check_cfg(), so all callees of
callx, including the ones referenced by data only, are known before
the main pass. The prog must be the only user of the map and it must
be allowed to leak pointers (CAP_PERFMON), since it reads function
addresses as data.
- check_cfg() treats ld_imm64 of such map like ld_imm64 BPF_PSEUDO_FUNC
for every function in the map: they're reachable, first insns are
prune and jump points, effects are merged into the subprog that
refers to the map.
- 64-bit load of the pointer is PTR_TO_FUNC. If the offset is variable
(tbl[i]) all possible offsets, given bounds and var_off, must be
pointers. The verifier forks a state for each. If none of them
overlaps with a pointer (tbl[i].data) it's a regular load.
- The value of the pointer is not known until JIT, so reject everything
that would const-fold its bytes: narrow or misaligned loads, const
strings. bpf_compute_const_regs() skips them too.
- The map has offsets until JIT, so the load of the pointer sets
jit_required like callx does. Otherwise the prog that reads the pointer
and passes it to a helper as a callback could run in the interpreter.
After JIT jit_subprogs() replaces the offsets in the map with addresses
of functions. Other progs that use the map were verified with its old
content const-folded, so there must be none. Add 'user' to bpf_map:
__add_used_map() records the first prog that uses the map and marks
the map as shared when another prog comes. Only the sole user can store
addresses into the map. After that no other prog can use it. The prog
that failed to load is not a user. libbpf loads it again to get the log.
The offsets are adjusted when insns are patched or removed, same as
subprog starts. Dead function is removed and the pointer becomes NULL.
The prog may still read it, e.g. when the load is hoisted above a branch,
but callx of it is dead code too.
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924031042.1690890-11-alexei.starovoitov@gmail.com
|
|
add_subprogs() finds subprogs by scanning insns for calls and ld_imm64
BPF_PSEUDO_FUNC. A function that is called via callx through a pointer
in data only, e.g. a vtable, is not referenced by any insn, but it must
be known before check_cfg() and the main pass.
func_info describes all functions of the program and libbpf provides it
for every function it puts into the prog. bpf_prepare_btf_info() reads
it before add_subprogs(). Register every function from func_info as
a subprog.
func_info had to match the subprogs found in insns exactly, so existing
programs are not affected. A function that is listed in func_info and
not referenced by anything is still rejected by check_cfg() as
unreachable.
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924031042.1690890-10-alexei.starovoitov@gmail.com
|
|
The callee of callx is known to the main verifier pass only, but
sort_subprogs_topo() (recursion check) and check_max_stack_depth()
(stack size, number of frames, tail_call_reachable, private stack) need
the call graph. Both treat ld_imm64 BPF_PSEUDO_FUNC as a call from
the subprog that takes the address, which is not where callx calls it:
main: r1 = foo ll; call bar
bar: callx r1
The call chain is main -> bar -> foo, but only main -> bar and
main -> foo are seen.
Record caller -> callee edge in a bitmap when the main pass processes
callx. It explores all feasible paths, so all feasible edges are there.
Then:
- rerun sort_subprogs_topo() after the main pass with callx edges.
Unbounded recursion is already rejected by the frame limit. This one
catches bounded recursion via callx, same as direct recursion.
The call graph is not context sensitive: foo() that calls bar() via
callx and bar() that calls foo() is a recursion even if it never
happens in the same call chain.
- check_max_stack_depth_subprog() walks all recorded callees at each
callx.
The same goes for sync callbacks. The address of a callback may be
taken in one subprog and passed to a helper in another one:
main: r1 = cb ll; call bar
bar: r2 = r1; call bpf_loop
Only main -> cb was accounted. Record caller -> callback edge in
push_callback_call() and walk the edges at helper and kfunc calls
that call callbacks too.
JITs pass tail call counter to the callee in a register. callx doesn't.
Reject tail_call_reachable callees of callx.
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924031042.1690890-7-alexei.starovoitov@gmail.com
|
