From nobody Sat Feb 7 17:55:50 2026 Received: from mail-dl1-f54.google.com (mail-dl1-f54.google.com [74.125.82.54]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 0D5F53AA19F for ; Thu, 15 Jan 2026 15:04:22 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.82.54 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768489470; cv=none; b=VSELIKTmWvzA2q3+tl9xXqmKB8uI1XK6E18iEGwwfz8MWC63Oh+qwToeU5fISuBrwEWUe3yBTdlKQkPEVcSkrfcehddWVP48VQ6argswyEzyIzZuSRmoeZoC5C6tsMMLyoI2EE/TTeYxUEuGBAtMXFRvGbl0uHYTEw5k8tiqVdg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1768489470; c=relaxed/simple; bh=gohZgJ3UzhdeCz3r8nYsKbGc+x6zYf73Hq3q96clfMI=; h=From:To:Cc:Subject:Date:Message-Id:MIME-Version; b=PACBM4rQ+gcEZhauxyc+ckk6LR6K3K27nrfH5EZUYsi9b2BnqspNCTnCxQaS0W5dVjkaDRfSMpWJ88ylkUf7K7wMGG3rgDQ+oeZWoM1qzqzH3Wydc+oycaBMeBUykXnepu7G3BsyidS1sb9ehasbO9Gucqu1ugVkcCBda+XRAxo= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=dUzrk1ab; arc=none smtp.client-ip=74.125.82.54 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="dUzrk1ab" Received: by mail-dl1-f54.google.com with SMTP id a92af1059eb24-1220154725fso712347c88.0 for ; Thu, 15 Jan 2026 07:04:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1768489459; x=1769094259; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=eehhj16F++hI4m+1Pleke9yunTvqMtKyr82Xytjlo0s=; b=dUzrk1abWu56ydbn8WEtumCRSA7WHmp4biYjA0RkW/PC9CJEsza3P+BkYTaeWVUKff zRYQm9vizxR1dxbDRNW2a7kyvTcswnEI9Hd4rsbxLRNLEsKopgoRipNqRSAHi5QBs3aV Hb51igT9f8KoK8g13Orc2JRyaFqdTRPkSi+GO5vv6Ax9/nsA2HacDt8VUj1pnhTTpmmi zSsv9RewKNEt63ngrFcRWL5pUmObVo+fDMDbWVoDErKfpewJ/0zjCvVjWclhDNmAOeJt 3ceW9FFn8E1d3uCszv9zIWUldnWuutUKUooFVOBd5w5boAmJ3/GP+gICq9YbMPdatBnU f1Hg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1768489459; x=1769094259; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-gg:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=eehhj16F++hI4m+1Pleke9yunTvqMtKyr82Xytjlo0s=; b=pDZejjKkgeSTaICyl6J7I2wXgbGy/6GVGa6UmK1DooPzSnNWvEG1d6A5TGI/4Kyv5c VGBgZZsGTzJFqxMkNeIqc9Pl2NgZ58B+jHD3qvqI7Q9r2U1YZFr3ht0h/lgNFoO5qOxY rrdd3sRVvZOXVyxLj9CxVO1FwzZYKple/V/1qeGayC1WGLg4OyhXh+37nAGQHWWHw8vR rOJLyuxGVegfFM5IwL9xVOI7gCgoUYUVaY1tPgaGGC8VP4Zn+uXsHWwD7jBSoh6tcCPy 1u4Hp5tpuBSxIOsrqT2nKMv8KdyuO0FRafIGiHCkqhyQubMUReCMTjR0563r8XhKrQKY uAWw== X-Forwarded-Encrypted: i=1; AJvYcCXOVw51UK2ksDjh8tYbXPGAQpC3I39wic9l7VO3CqWAH9o7XZ4lu2Bp23I/LIDxlIxNI1n+m4cmylo54uI=@vger.kernel.org X-Gm-Message-State: AOJu0YxGfeUNNVWbHDlVhyRE0r1ReoNoHdkcH0HknQolHFNy60hWAcIn +oiHl7xHa56KW3E942fwdrDxfH8JkI88ZpDdxYcnmmg7dmh3w/V0SeLK X-Gm-Gg: AY/fxX5dGcWo9I8TptsVaxlwBn8tYV6+/3FNib2UFLUjx3j3gKG1ibHrRhpE3FxTCBZ IzJZjo7XT5GuR16h5pWhXzzQBdiNHPMgnct8Zohx0t88WhdBj6rjiIkEbxDainhH/QWkKnN0ypE zNciekhJ/UV1XxOJ8CtHJdrkmqJkxykaOQmxvA0zEcYQL20wde8Wgh7svfKj6HrKSIu8Z6jYJl0 YkWYkck0xfAkj+aVVF+WTfpKifw5xrS3ZvO1lmAsfAg9LB1f97g5eRIz6vigt9KqrIXOX3y8eJj 1E0SgyK414Hn1GUUpDfJtAUuXkq6NLZ5Rcu7WEW0THGjxijqc3IDWRAMJz8vTPo/ThuY9gWMI8f riF5fciNLUgrtB0zA++Ayp/pmAzL+ZW0oHduLzp9B1jRAtRJCWce9fQb2G1edOyEx5B10RGh3Jo tXdbvwVZgEds/MoYzyOuzC+Zg= X-Received: by 2002:a05:7022:f512:b0:11d:fbf1:1e27 with SMTP id a92af1059eb24-1233d060fa8mr2315202c88.19.1768489457287; Thu, 15 Jan 2026 07:04:17 -0800 (PST) Received: from localhost.localdomain ([74.48.213.230]) by smtp.gmail.com with ESMTPSA id a92af1059eb24-121f243421esm34342659c88.2.2026.01.15.07.04.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Jan 2026 07:04:16 -0800 (PST) From: wujing To: Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko Cc: Martin KaFai Lau , Eduard Zingerman , Song Liu , Yonghong Song , KP Singh , Stanislav Fomichev , Hao Luo , Jiri Olsa , bpf@vger.kernel.org, linux-kernel@vger.kernel.org, wujing , Qiliang Yuan Subject: [PATCH] bpf/verifier: optimize precision backtracking by skipping precise bits Date: Thu, 15 Jan 2026 23:04:05 +0800 Message-Id: <20260115150405.443581-1-realwujing@gmail.com> X-Mailer: git-send-email 2.39.5 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Backtracking is one of the most expensive parts of the verifier. When marking precision, currently the verifier always triggers the full __mark_chain_precision even if the target register or stack slot is already marked as precise. Since a precise mark in a state implies that all necessary ancestors have already been backtracked and marked accordingly, we can safely skip the backtracking process if the bit is already set. This patch implements early exit logic in: 1. mark_chain_precision: Check if the register is already precise. 2. propagate_precision: Skip registers and stack slots that are already precise in the current state when propagating from an old state. This significantly reduces redundant backtracking in complex BPF programs with frequent state pruning and merges. Signed-off-by: wujing Signed-off-by: Qiliang Yuan --- kernel/bpf/verifier.c | 19 +++++++++++++++++-- 1 file changed, 17 insertions(+), 2 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 6220dde41107..378341e1177f 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -4927,6 +4927,14 @@ static int __mark_chain_precision(struct bpf_verifie= r_env *env, =20 int mark_chain_precision(struct bpf_verifier_env *env, int regno) { + struct bpf_reg_state *reg; + + if (regno >=3D 0) { + reg =3D &env->cur_state->frame[env->cur_state->curframe]->regs[regno]; + if (reg->precise) + return 0; + } + return __mark_chain_precision(env, env->cur_state, regno, NULL); } =20 @@ -19527,19 +19535,23 @@ static int propagate_precision(struct bpf_verifie= r_env *env, struct bpf_verifier_state *cur, bool *changed) { - struct bpf_reg_state *state_reg; - struct bpf_func_state *state; + struct bpf_reg_state *state_reg, *cur_reg; + struct bpf_func_state *state, *cur_state; int i, err =3D 0, fr; bool first; =20 for (fr =3D old->curframe; fr >=3D 0; fr--) { state =3D old->frame[fr]; + cur_state =3D cur->frame[fr]; state_reg =3D state->regs; first =3D true; for (i =3D 0; i < BPF_REG_FP; i++, state_reg++) { if (state_reg->type !=3D SCALAR_VALUE || !state_reg->precise) continue; + cur_reg =3D &cur_state->regs[i]; + if (cur_reg->precise) + continue; if (env->log.level & BPF_LOG_LEVEL2) { if (first) verbose(env, "frame %d: propagating r%d", fr, i); @@ -19557,6 +19569,9 @@ static int propagate_precision(struct bpf_verifier_= env *env, if (state_reg->type !=3D SCALAR_VALUE || !state_reg->precise) continue; + cur_reg =3D &cur_state->stack[i].spilled_ptr; + if (cur_reg->precise) + continue; if (env->log.level & BPF_LOG_LEVEL2) { if (first) verbose(env, "frame %d: propagating fp%d", --=20 2.39.5