From: Eduard Zingerman <eddyz87@gmail.com>
To: Amery Hung <ameryhung@gmail.com>, bpf@vger.kernel.org
Cc: netdev@vger.kernel.org, alexei.starovoitov@gmail.com,
andrii@kernel.org, daniel@iogearbox.net, memxor@gmail.com,
martin.lau@kernel.org, mykyta.yatsenko5@gmail.com,
kernel-team@meta.com
Subject: Re: [PATCH bpf-next v4 04/12] bpf: Preserve reg->id of pointer objects after null-check
Date: Mon, 11 May 2026 14:48:47 -0700 [thread overview]
Message-ID: <7cffd25282e426002edc4a371b17816bcb862d41.camel@gmail.com> (raw)
In-Reply-To: <20260506142709.2298255-5-ameryhung@gmail.com>
On Wed, 2026-05-06 at 07:27 -0700, Amery Hung wrote:
> 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
>
> Program Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF)
> ------------------------ --------- --------- -------------- ---------- ---------- -------------
> rbtree_search 6820 7326 +506 (+7.42%) 379 398 +19 (+5.01%)
>
> Meta BPF objects with insns_diff > 0
>
> 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 523 526 +3 (+0.57%) 39 40 +1 (+2.56%)
> 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 34656 35717 +1061 (+3.06%) 936 970 +34 (+3.63%)
> tw_twfw_egress 222327 222338 +11 (+0.00%) 10563 10564 +1 (+0.01%)
> tw_twfw_ingress 78295 78299 +4 (+0.01%) 3825 3826 +1 (+0.03%)
> tw_twfw_tc_eg 222839 222859 +20 (+0.01%) 10584 10585 +1 (+0.01%)
> tw_twfw_tc_in 78295 78299 +4 (+0.01%) 3825 3826 +1 (+0.03%)
> tw_twfw_egress 8080 8085 +5 (+0.06%) 456 456 +0 (+0.00%)
> tw_twfw_ingress 8053 8056 +3 (+0.04%) 454 454 +0 (+0.00%)
> tw_twfw_tc_eg 8154 8174 +20 (+0.25%) 456 457 +1 (+0.22%)
> tw_twfw_tc_in 8060 8063 +3 (+0.04%) 455 455 +0 (+0.00%)
> tw_twfw_egress 222327 222338 +11 (+0.00%) 10563 10564 +1 (+0.01%)
> tw_twfw_ingress 78295 78299 +4 (+0.01%) 3825 3826 +1 (+0.03%)
> tw_twfw_tc_eg 222839 222859 +20 (+0.01%) 10584 10585 +1 (+0.01%)
> tw_twfw_tc_in 78295 78299 +4 (+0.01%) 3825 3826 +1 (+0.03%)
> tw_twfw_egress 8080 8085 +5 (+0.06%) 456 456 +0 (+0.00%)
> tw_twfw_ingress 8053 8056 +3 (+0.04%) 454 454 +0 (+0.00%)
> tw_twfw_tc_eg 8154 8174 +20 (+0.25%) 456 457 +1 (+0.22%)
> tw_twfw_tc_in 8060 8063 +3 (+0.04%) 455 455 +0 (+0.00%)
>
> 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 safe
>
> Acked-by: Andrii Nakryiko <andrii@kernel.org>
> Signed-off-by: Amery Hung <ameryhung@gmail.com>
> ---
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
[...]
next prev parent reply other threads:[~2026-05-11 21:49 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-05-06 14:26 [PATCH bpf-next v4 00/12] Refactor verifier object relationship tracking Amery Hung
2026-05-06 14:26 ` [PATCH bpf-next v4 01/12] bpf: Simplify mark_stack_slot_obj_read() and callers Amery Hung
2026-05-11 17:17 ` Eduard Zingerman
2026-05-06 14:26 ` [PATCH bpf-next v4 02/12] bpf: Unify dynptr handling in the verifier Amery Hung
2026-05-06 15:27 ` bot+bpf-ci
2026-05-07 12:22 ` Amery Hung
2026-05-06 14:26 ` [PATCH bpf-next v4 03/12] bpf: Assign reg->id when getting referenced kptr from ctx Amery Hung
2026-05-06 15:27 ` bot+bpf-ci
2026-05-07 12:38 ` Amery Hung
2026-05-11 21:31 ` Eduard Zingerman
2026-05-06 14:27 ` [PATCH bpf-next v4 04/12] bpf: Preserve reg->id of pointer objects after null-check Amery Hung
2026-05-11 21:48 ` Eduard Zingerman [this message]
2026-05-06 14:27 ` [PATCH bpf-next v4 05/12] bpf: Refactor object relationship tracking and fix dynptr UAF bug Amery Hung
2026-05-06 15:27 ` bot+bpf-ci
2026-05-07 12:20 ` Amery Hung
2026-05-06 14:27 ` [PATCH bpf-next v4 06/12] bpf: Remove redundant dynptr arg check for helper Amery Hung
2026-05-06 14:27 ` [PATCH bpf-next v4 07/12] bpf: Unify referenced object tracking in verifier Amery Hung
2026-05-06 14:27 ` [PATCH bpf-next v4 08/12] bpf: Unify release handling for helpers and kfuncs Amery Hung
2026-05-06 14:27 ` [PATCH bpf-next v4 09/12] selftests/bpf: Test creating dynptr from dynptr data and slice Amery Hung
2026-05-06 14:27 ` [PATCH bpf-next v4 10/12] selftests/bpf: Test using dynptr after freeing the underlying object Amery Hung
2026-05-06 14:27 ` [PATCH bpf-next v4 11/12] selftests/bpf: Test using slice after invalidating dynptr clone Amery Hung
2026-05-06 14:27 ` [PATCH bpf-next v4 12/12] selftests/bpf: Test using file dynptr after the reference on file is dropped Amery Hung
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=7cffd25282e426002edc4a371b17816bcb862d41.camel@gmail.com \
--to=eddyz87@gmail.com \
--cc=alexei.starovoitov@gmail.com \
--cc=ameryhung@gmail.com \
--cc=andrii@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=kernel-team@meta.com \
--cc=martin.lau@kernel.org \
--cc=memxor@gmail.com \
--cc=mykyta.yatsenko5@gmail.com \
--cc=netdev@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox