From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-dy2-f12.google.com (mail-dy2-f12.google.com [74.125.229.12]) (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 27D494A43E8 for ; Thu, 1 Oct 2026 09:35:40 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.229.12 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790847343; cv=none; b=VpWLf2XaOGQ5igO89X545O9ujUfGXCNkc990+jusTQV4SWzUDdSqilcuTaMXb5nzNSvCvJcilpRy9xufLcT0LplJnzAXJp9JVeRp2R8vWBnCJmJ9CNZgPR1qVhMbMTrQ5zIw4xxnJz2G9+MkEeSRmr+6TBZvXwK5+UsCn6Q/JPs= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790847343; c=relaxed/simple; bh=TAy7SXvodxwIVUeYRCkkRqmpU/1T4vMLfRFjM5CPyIQ=; h=From:Subject:Date:Message-Id:MIME-Version:Content-Type:To:Cc; b=cj7PdN/Nb73dqaZWWXkzSiyqunfkPXFv3r0rCjufZFC7+nrGixn3WsTaXJaPg4DX+2bA7eQLGfxuB8kiJfWcTHMxojNOzqPZRCNKqbA1glC/J7MlbMEdxowLQ4cddP7JxDRGSZ9bGAZ1VXE01lVX6vmqzyhA3Hsj2JpZJ4KUmLs= 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=kqm180Pb; arc=none smtp.client-ip=74.125.229.12 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="kqm180Pb" Received: by mail-dy2-f12.google.com with SMTP id 5a478bee46e88-328664c2da6so5393172eec.1 for ; Thu, 01 Oct 2026 02:35:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1790847340; x=1791452140; darn=vger.kernel.org; h=cc:to:content-transfer-encoding:content-type:mime-version :message-id:date:subject:from:from:to:cc:subject:date:message-id :reply-to:content-type; bh=LGX/SBLSJlBXSD7ryPBEbi/Uhkcr21PESamwaTOcG4E=; b=kqm180PbmrGS4GnfTdq6usSOjR//PeE7YQJz6u2KzbV2pOZ4X9DeuvPrjj5Q5RvOWy PXbVEgyc67GpgWX2pe0HpwtJL5NLEk5Y/oDM5gd/RlEv2tokNMwDtkj9OAumN+AE1DZW Jvs8tAmJTK+yCKq9fBS2J9DN5n1Nlxxpa61yTBFTXvWx3qjCeYVVdqh4fv2K/aZGQjXt +2TL33XrUX9LcQ9H09aISEyrIhYc4q4ZjCSu4ISGxziQmCbn5OcR//WCjDTknghrHbOB FoiEZDYTK9fj231f1cIyA6v9+no7V7R3J1517FuYm6TlNUzAWiRBoq2FJyy5cXtkJgDC agQw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1790847340; x=1791452140; h=cc:to:content-transfer-encoding:content-type:mime-version :message-id:date:subject:from:x-gm-gg:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to:content-type; bh=LGX/SBLSJlBXSD7ryPBEbi/Uhkcr21PESamwaTOcG4E=; b=qqixL2tTXG1dAvKp0uSbbQl0qbG1QPPJrrb5XlRktJX3BCVySN42Epa7g86h7mcD9M oNL+M1vXHbhyroOq7hC1L6wqYgboG72BEqfWw65PulISSWYomJ+DDSssqHpxfNbPd+33 FOFA3dMWkuLaXpyJ85L2VEsUhqJ7VPGXQYzzN2eawZNOwRyb0k+OX7yV9U3ui+/l2vdh wsRIroc9Hs5iy7cckPzoOvHFy4sXki+OTj6OmsORY9q8pPcDFvSkRJXraf+zaijtpEmc cP2+lT+YObO3zDA9jiBt64/PaztOqA19EiA0rJaDnKCAygqtTwRI698LFJrgjO9QZle7 jgBA== X-Forwarded-Encrypted: i=1; AKwUvBwwEjorQxK2LAAHL9XNd025xhGcCDlPDYN1aq5Mfa93KO9ULg96yYC/E9Lxi2zIX1YHp2276i+SDhD4JdI=@vger.kernel.org X-Gm-Message-State: AFuF++lVP0nfTmzvq7vmR2vJUenUUP65w7pzT849xKe8APk/f7l9MFeS 5tECyFFCZMDubMSNRtRz4+eRVKm+K5Gb9zQhvhHz+Vz/TgbCJhULpLdG X-Gm-Gg: AYBFou0oCiqU4vu2pYNRWQ6+I0ZPhRdwT4OHrn56Ib5hea3kg8F5nKq5MCc6WwAxP+P L0S2ZsVl4eGKfHOQonFhj4Va3uNbh08K2mkOW0gYtSgI5GmNac6bb39CQg2xgSuKXjqKhmpjgaY RhP+noHw9s//lK4rL76IJqnK2iI+EGEYKhuUVbK0wOfsH0ek13qWSukWhYQg0NT2WiPH91N8Jve OB8f/Yrfn3e+zbu4lSmkvc1LfK36va2hgCyuHdX6Lez+VQzeRH/uFyUaDbEE98vBTVwtg90sTfa uEqnxh8LrMO60j4od9CfrEKusLPkpxNVTQfZYLHLphJ/lUKjFCZh9inOSi/VX9+iZmBYaG75tgG jWmoCtdSrrbgebojwDXbFi0dsYmNMZlXivQDnfZW4CFZWkbRmzBg17KiowJHOJHcYlpTH84xhFg /Dcc09ImbtMuz9694+j5kI3SJk8ljVZHPk+Bj0Iy1BgqW1RcKYidXfL9G831xwDn4jRw== X-Received: by 2002:a05:7301:1928:b0:33b:9540:89c6 with SMTP id 5a478bee46e88-34cdb5f9107mr4257043eec.6.1790847339814; Thu, 01 Oct 2026 02:35:39 -0700 (PDT) Received: from [127.0.1.1] ([23.254.208.9]) by smtp.gmail.com with ESMTPSA id 5a478bee46e88-34db37507a7sm6003982eec.13.2026.10.01.02.35.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 01 Oct 2026 02:35:39 -0700 (PDT) From: Qiliang Yuan Subject: [PATCH bpf-next 0/4] bpf: Apply the rewrites of bpf_do_misc_fixups() at once Date: Thu, 01 Oct 2026 17:35:31 +0800 Message-Id: <20261001-bpf-verifier-patch-batch-v1-0-a12df8a09160@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit X-B4-Tracking: v=1; b=H4sIAGMpvmoC/x3MQQqAIBCF4avErBsYTSq6SrSwGms2JhoRRHfP3 Dz4F997IHEUTjBUD0S+JMnhc6i6gmW3fmOUNTdo0q0iUjgHh1c2TjhisOey41xWG6OpJ+6bboX MQ2Qnd7ke4Vee7xOm9/0AhMWZrXQAAAA= To: Alexei Starovoitov , Daniel Borkmann , John Fastabend , Andrii Nakryiko , Eduard Zingerman , Kumar Kartikeya Dwivedi , Martin KaFai Lau , Song Liu , Yonghong Song , Jiri Olsa , Emil Tsalapatis , Ihor Solodrai , Shuah Khan Cc: bpf@vger.kernel.org, linux-kernel@vger.kernel.org, linux-kselftest@vger.kernel.org, Qiliang Yuan X-Mailer: b4 0.13.0 Eduard pointed out that bpf_patch_insn_data() takes a large share of the time to load pyperf180 [1]. Every patch moves the tail of the instruction and aux data arrays and walks the whole program to fix up branches, so a pass that patches M instructions of an N instruction program does O(N * M) work. Kumar's commit 261b61d3735b ("bpf: Make post-verification instruction rewrites killable") made that work preemptible, but its cost is still quadratic. On current bpf-next nearly all of it comes from one place in pyperf: bpf_do_misc_fixups() inlines each bpf_map_lookup_elem() on a hash map into 3 instructions, 930 times in a ~24k instruction program for pyperf180 and 1530 times in ~42k instructions for pyperf600. Patch 1 adds a list of patches that a pass queues and then applies in one O(N + inserted instructions) step. It keeps the semantics of bpf_patch_insn_data(): a patched instruction is named by the first instruction of its patch, and jumps from a patch out of it are relative to the patch in place. Branches, aux data, subprog starts, line info, instruction arrays, function pointers and poke descriptors are remapped together. Patch 2 moves the main loop of bpf_do_misc_fixups() to it, patch 3 drops the delta that is now always 0, and patch 4 adds xlated tests for jumps around patches. The other passes still use bpf_patch_insn_data() and can move over to the list one at a time in follow-up series. perf stat -B --all-kernel -r30 -- veristat -q , mean of two rounds, x86_64 VM with 32 vCPUs: base patched pyperf180 0.575 s 0.458 s -20.4% pyperf600 1.491 s 1.041 s -30.2% strobemeta 0.531 s 0.532 s test_verif_scale2 0.561 s 0.562 s For the 1042 objects of the selftests, the 2863 programs that load have the same xlated code on both kernels, with the immediates that hold kernel addresses or BTF ids masked. test_verifier passes on both. Of test_progs, only missed/tp_recursion failed once on the patched kernel in a parallel run, it passes when run alone. On a side note, the largest part of the time to load pyperf180 is the arg tracking analysis: analyze_subprog() takes about half of it on base, __arg_track_join() alone about 30%. [1] https://lore.kernel.org/bpf/a714ee96d0ad96bbc9d51037616e5c4e2790a8ec.camel@gmail.com/ Signed-off-by: Qiliang Yuan --- Qiliang Yuan (4): bpf: Add a list of deferred instruction patches bpf: Queue the rewrites of bpf_do_misc_fixups() and apply them at once bpf: Drop the constant delta from bpf_do_misc_fixups() selftests/bpf: Test jumps around patches of bpf_do_misc_fixups() include/linux/bpf.h | 1 + include/linux/bpf_verifier.h | 26 + kernel/bpf/bpf_insn_array.c | 18 + kernel/bpf/fixups.c | 545 ++++++++++++++------- kernel/bpf/verifier.c | 1 + tools/testing/selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_patch_list.c | 120 +++++ 7 files changed, 546 insertions(+), 167 deletions(-) --- base-commit: 6a75c73eebd4d497ded7d08b47894f9ddbebb5a9 change-id: 20261001-bpf-verifier-patch-batch-2442080e837d Best regards, -- Qiliang Yuan