Re: [RFC PATCH bpf-next v2 05/11] bpf: Preserve reg->id of pointer objects after null-check
From: Amery Hung <hidden>
Date: 2026-03-11 23:46:41
Also in:
bpf
On Wed, Mar 11, 2026 at 3:30 PM Alexei Starovoitov [off-list ref] wrote:
On Wed, Mar 11, 2026 at 3:26 PM Alexei Starovoitov [off-list ref] wrote:quoted
On Fri, Mar 6, 2026 at 10:44 PM Amery Hung [off-list ref] wrote:quoted
Preserve reg->id of pointer objects after null-checking the register so that children objects derived from it can still refer to it in the new object relationship tracking mechanism introduced in a later patch. This change incurs a slight increase in the number of states in one selftest bpf object, rbtree_search.bpf.o. For Meta bpf objects, the increase of states is also negligible. Selftest BPF objects with insns_diff > 0 Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF) --------- --------- ------------- ---------- ---------- ------------- 7309 7814 +505 (+6.91%) 394 413 +19 (+4.82%) Meta BPF objects with insns_diff > 0 Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF) --------- --------- -------------- ---------- ---------- ------------- 52 57 +5 (+9.62%) 5 6 +1 (+20.00%) 52 57 +5 (+9.62%) 5 6 +1 (+20.00%) 676 679 +3 (+0.44%) 54 54 +0 (+0.00%) 289 292 +3 (+1.04%) 20 20 +0 (+0.00%) 78 82 +4 (+5.13%) 8 8 +0 (+0.00%) 252 320 +68 (+26.98%) 21 27 +6 (+28.57%) 252 320 +68 (+26.98%) 21 27 +6 (+28.57%) 119 126 +7 (+5.88%) 6 7 +1 (+16.67%) 1119 1128 +9 (+0.80%) 95 96 +1 (+1.05%) 1128 1137 +9 (+0.80%) 95 96 +1 (+1.05%) 4380 4465 +85 (+1.94%) 114 118 +4 (+3.51%) 3093 3170 +77 (+2.49%) 83 88 +5 (+6.02%) 30181 31224 +1043 (+3.46%) 832 863 +31 (+3.73%) 237608 237619 +11 (+0.00%) 11670 11671 +1 (+0.01%) 94832 94836 +4 (+0.00%) 4787 4788 +1 (+0.02%) 237387 237407 +20 (+0.01%) 11651 11652 +1 (+0.01%) 94832 94836 +4 (+0.00%) 4787 4788 +1 (+0.02%) 8103 8108 +5 (+0.06%) 459 459 +0 (+0.00%) 8076 8079 +3 (+0.04%) 457 457 +0 (+0.00%) 8177 8197 +20 (+0.24%) 459 460 +1 (+0.22%) 8083 8086 +3 (+0.04%) 458 458 +0 (+0.00%) 237608 237619 +11 (+0.00%) 11670 11671 +1 (+0.01%) 94832 94836 +4 (+0.00%) 4787 4788 +1 (+0.02%) 237387 237407 +20 (+0.01%) 11651 11652 +1 (+0.01%) 94832 94836 +4 (+0.00%) 4787 4788 +1 (+0.02%) 8103 8108 +5 (+0.06%) 459 459 +0 (+0.00%) 8076 8079 +3 (+0.04%) 457 457 +0 (+0.00%) 8177 8197 +20 (+0.24%) 459 460 +1 (+0.22%) 8083 8086 +3 (+0.04%) 458 458 +0 (+0.00%)The table is missing names. State columns can be dropped instead.
Program Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF) ------------------------ --------- --------- -------------- ---------- ---------- ------------- ned_imex_be_tclass 52 57 +5 (+9.62%) 5 6 +1 (+20.00%) ned_imex_be_tclass 52 57 +5 (+9.62%) 5 6 +1 (+20.00%) ned_skop_auto_flowlabel 676 679 +3 (+0.44%) 54 54 +0 (+0.00%) ned_skop_mss 289 292 +3 (+1.04%) 20 20 +0 (+0.00%) ned_skopt_bet_classifier 78 82 +4 (+5.13%) 8 8 +0 (+0.00%) dctcp_update_alpha 252 320 +68 (+26.98%) 21 27 +6 (+28.57%) dctcp_update_alpha 252 320 +68 (+26.98%) 21 27 +6 (+28.57%) ned_ts_func 119 126 +7 (+5.88%) 6 7 +1 (+16.67%) tw_egress 1119 1128 +9 (+0.80%) 95 96 +1 (+1.05%) tw_ingress 1128 1137 +9 (+0.80%) 95 96 +1 (+1.05%) tw_tproxy_router 4380 4465 +85 (+1.94%) 114 118 +4 (+3.51%) tw_tproxy_router4 3093 3170 +77 (+2.49%) 83 88 +5 (+6.02%) ttls_tc_ingress 30181 31224 +1043 (+3.46%) 832 863 +31 (+3.73%) tw_twfw_egress 237608 237619 +11 (+0.00%) 11670 11671 +1 (+0.01%) tw_twfw_ingress 94832 94836 +4 (+0.00%) 4787 4788 +1 (+0.02%) tw_twfw_tc_eg 237387 237407 +20 (+0.01%) 11651 11652 +1 (+0.01%) tw_twfw_tc_in 94832 94836 +4 (+0.00%) 4787 4788 +1 (+0.02%) tw_twfw_egress 8103 8108 +5 (+0.06%) 459 459 +0 (+0.00%) tw_twfw_ingress 8076 8079 +3 (+0.04%) 457 457 +0 (+0.00%) tw_twfw_tc_eg 8177 8197 +20 (+0.24%) 459 460 +1 (+0.22%) tw_twfw_tc_in 8083 8086 +3 (+0.04%) 458 458 +0 (+0.00%) tw_twfw_egress 237608 237619 +11 (+0.00%) 11670 11671 +1 (+0.01%) tw_twfw_ingress 94832 94836 +4 (+0.00%) 4787 4788 +1 (+0.02%) tw_twfw_tc_eg 237387 237407 +20 (+0.01%) 11651 11652 +1 (+0.01%) tw_twfw_tc_in 94832 94836 +4 (+0.00%) 4787 4788 +1 (+0.02%) tw_twfw_egress 8103 8108 +5 (+0.06%) 459 459 +0 (+0.00%) tw_twfw_ingress 8076 8079 +3 (+0.04%) 457 457 +0 (+0.00%) tw_twfw_tc_eg 8177 8197 +20 (+0.24%) 459 460 +1 (+0.22%) tw_twfw_tc_in 8083 8086 +3 (+0.04%) 458 458 +0 (+0.00%)
quoted
quoted
Looking into rbtree_search, the reason for such increase is that the verifier has to explore the main loop shown below for one more iteration until state pruning decides the current state is safe. long rbtree_search(void *ctx) { ... bpf_spin_lock(&glock0); rb_n = bpf_rbtree_root(&groot0); while (can_loop) { if (!rb_n) { bpf_spin_unlock(&glock0); return __LINE__; } n = rb_entry(rb_n, struct node_data, r0); if (lookup_key == n->key0) break; if (nr_gc < NR_NODES) gc_ns[nr_gc++] = rb_n; if (lookup_key < n->key0) rb_n = bpf_rbtree_left(&groot0, rb_n); else rb_n = bpf_rbtree_right(&groot0, rb_n); } ... } Below is what the verifier sees at the start of each iteration (65: may_goto) after preserving id of rb_n. Without id of rb_n, the verifier stops exploring the loop at iter 16. rb_n gc_ns[15] iter 15 257 257 iter 16 290 257 rb_n: idmap add 257->290 gc_ns[15]: check 257 != 290 --> state not equal iter 17 325 257 rb_n: idmap add 290->325 gc_ns[15]: idmap add 257->257 --> state safeI'm not following. The verifier processes above as a bounded loop. All 16 (NR_NODES) iterations.
This is not a bounded loop IIUC. Note that there is no else branch for "if (nr_gc < NR_NODES)" to break the loop. Therefore the verifier processes 17 loops after preserving id.
quoted
Why presence of id on 'rb_n' makes a difference? It will still process 16 loops. Which insn is safe vs not in the above ? One after gc_ns[nr_gc++] = rb_n ?
It is while (can_loop)
One more thing... How does it interact with reg_is_init_pkt_pointer() ? That pointer has to have id == 0.
I haven't looked deep into the case. Currently, skb is non-referenced for non-qdisc programs, so skb dynptr won't need to track it. If there is ever a need to track it, we can assign a reserved non-zero id to the unmodified pkt pointer. For reg_is_init_pkt_pointer(), it is already checking tnum_equals_const(reg->var_off, 0), so maybe it is fine to drop the id check (not sure).