linux-kernel - Re: [PATCH v3] bpf/verifier: optimize precision backtracking by skipping precise bits

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <CAADnVQ+F94-KVQTzZZSGY-rjidY_kU+zQDR68jcz8Mq1+4YmkA@mail.gmail.com>
Date: Sat, 17 Jan 2026 09:12:29 -0800
From: Alexei Starovoitov <alexei.starovoitov@...il.com>
To: Qiliang Yuan <realwujing@...il.com>
Cc: Eduard <eddyz87@...il.com>, Andrii Nakryiko <andrii@...nel.org>, 
	Alexei Starovoitov <ast@...nel.org>, bpf <bpf@...r.kernel.org>, 
	Daniel Borkmann <daniel@...earbox.net>, Hao Luo <haoluo@...gle.com>, Jiri Olsa <jolsa@...nel.org>, 
	KP Singh <kpsingh@...nel.org>, LKML <linux-kernel@...r.kernel.org>, 
	Martin KaFai Lau <martin.lau@...ux.dev>, Stanislav Fomichev <sdf@...ichev.me>, Song Liu <song@...nel.org>, 
	Yonghong Song <yonghong.song@...ux.dev>, yuanql9@...natelecom.cn
Subject: Re: [PATCH v3] bpf/verifier: optimize precision backtracking by
 skipping precise bits

On Sat, Jan 17, 2026 at 2:09 AM Qiliang Yuan <realwujing@...il.com> wrote:
>
>
> Test case (backtrack_stress.c):
> #include "vmlinux.h"
> #include <bpf/bpf_helpers.h>
>
> struct {
>     __uint(type, BPF_MAP_TYPE_ARRAY);
>     __uint(max_entries, 1);
>     __type(key, __u32);
>     __type(value, __u64);
> } dummy_map SEC(".maps");
>
> SEC("tc")
> int backtrack_stress(struct __sk_buff *skb)
> {
>     __u32 key = 0;
>     __u64 *val = bpf_map_lookup_elem(&dummy_map, &key);
>     if (!val) return 0;
>     __u64 x = *val;
>
>     /* 1. Create a deep dependency chain to fill history for 'x' */
>     x += 1; x *= 2; x -= 1; x ^= 0x55;
>     x += 1; x *= 2; x -= 1; x ^= 0xAA;
>     x += 1; x *= 2; x -= 1; x ^= 0x55;
>     x += 1; x *= 2; x -= 1; x ^= 0xAA;
>
>     /* 2. Create many states via conditional branches */
> #define CHECK_X(n) if (x == n) { x += 1; } if (x == n + 1) { x -= 1; }
> #define CHECK_X10(n)  CHECK_X(n) CHECK_X(n+2) CHECK_X(n+4) CHECK_X(n+6) CHECK_X(n+8) \
>                       CHECK_X(n+10) CHECK_X(n+12) CHECK_X(n+14) CHECK_X(n+16) CHECK_X(n+18)
> #define CHECK_X100(n) CHECK_X10(n) CHECK_X10(n+20) CHECK_X10(n+40) CHECK_X10(n+60) CHECK_X10(n+80) \
>                       CHECK_X10(n+100) CHECK_X10(n+120) CHECK_X10(n+140) CHECK_X10(n+160) CHECK_X10(n+180)
>
>     CHECK_X100(0)
>     CHECK_X100(200)
>     CHECK_X100(400)
>     CHECK_X100(600)
>     CHECK_X100(800)
>     CHECK_X100(1000)
>
>     /* 3. Trigger mark_chain_precision() multiple times on 'x' */
>     #pragma clang loop unroll(full)
>     for (int i = 0; i < 500; i++) {
>         if (x == (2000 + i)) {
>             x += 1;
>         }
>     }
>
>     return x;
> }

Thanks for the test. It's a good one.

> Baseline (6.19.0-rc5-baseline, git commit 944aacb68baf):
> File                    Program           Verdict  Duration (us)   Insns  States  Program size  Jited size
> ----------------------  ----------------  -------  -------------  ------  ------  ------------  ----------
> backtrack_stress.bpf.o  backtrack_stress  success         197924  289939   34331          5437       28809
> ----------------------  ----------------  -------  -------------  ------  ------  ------------  ----------
...
> Patched (6.19.0-rc5-optimized):
> File                    Program           Verdict  Duration (us)   Insns  States  Program size  Jited size
> ----------------------  ----------------  -------  -------------  ------  ------  ------------  ----------
> backtrack_stress.bpf.o  backtrack_stress  success         214600  289939   34331          5437       28809
> ----------------------  ----------------  -------  -------------  ------  ------  ------------  ----------

but the performance results show that your patch makes
absolutely no difference. Total time is the same and
the verifier is doing exactly the same steps.
Try veristat -v -l2 backtrack_stress.bpf.o | grep mark_precise

and you'll see that the output before and after is the same.

The parallel invocations of veristat only add noise.
4m vs 8m page-faults is a noise. It's not a result of the patch.

pw-bot: cr