From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id E91C3C2D0CD for ; Thu, 15 May 2025 14:51:34 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 6290C6B00A3; Thu, 15 May 2025 10:51:33 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 5D8046B00A4; Thu, 15 May 2025 10:51:33 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 49F956B00A5; Thu, 15 May 2025 10:51:33 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 27C176B00A3 for ; Thu, 15 May 2025 10:51:33 -0400 (EDT) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id F21908017C for ; Thu, 15 May 2025 14:51:33 +0000 (UTC) X-FDA: 83445430866.07.8FD6BC5 Received: from sea.source.kernel.org (sea.source.kernel.org [172.234.252.31]) by imf25.hostedemail.com (Postfix) with ESMTP id 31DD3A0002 for ; Thu, 15 May 2025 14:51:31 +0000 (UTC) Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=mXebSOmW; spf=pass (imf25.hostedemail.com: domain of kees@kernel.org designates 172.234.252.31 as permitted sender) smtp.mailfrom=kees@kernel.org; dmarc=pass (policy=quarantine) header.from=kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1747320692; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=92+YxkMA5jXDQ8jPC3A9bfW8/7HDbX/WNPtCkwyYeAU=; b=etVFSAHtilgaBmlwMhWY553vjhki/vBoPVtWlepWIg3tBhxS+m5JW6hr35dGSRY5eT6A2V 8GpjsadaZ4+0PPR7W3ZzmAXT7FUQnm/4HZoCmDF2LDIoqDT74Y8eIW9+XEUXv4kfYsnGmM iV9Ymh80+xd0n6gz7I1ntrmmu/udCr8= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1747320692; a=rsa-sha256; cv=none; b=NxPZHQhd6+UK2Uv0U3gieM8aTVc2l/wMa+uArUJJQ8VauMwObxYC4wq5cDAcEjY+1kCIlp FN/Hf3tSX8dKK3BYdn891gC0HLp35iK259ZbNbSbyQnimWAwrna+6t4dOjEKYe88XDV0CY jPBrfTBxHr7uVWJecloiwPV38GR7RRo= ARC-Authentication-Results: i=1; imf25.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=mXebSOmW; spf=pass (imf25.hostedemail.com: domain of kees@kernel.org designates 172.234.252.31 as permitted sender) smtp.mailfrom=kees@kernel.org; dmarc=pass (policy=quarantine) header.from=kernel.org Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by sea.source.kernel.org (Postfix) with ESMTP id DAC71435B6; Thu, 15 May 2025 14:51:30 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id A3A81C4CEE7; Thu, 15 May 2025 14:51:30 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1747320690; bh=gPLoJgRnkayVWLQlz1ZTjudKv0fME3HsKweEpIKKq+E=; h=Date:From:To:CC:Subject:In-Reply-To:References:From; b=mXebSOmWp+w4si2qesd00c6VxgzaTwS28nVOHCxpHOew/rDrZDXTVj4zjCXPg2a5h yyU2lhydPthHrsQrVhj7ABbLHsEKOI06C56xmACTztVlZ+Reu/wF/ybUIm+1c20TRp P1RAOIM/LI/udJwOZOhu325yh4a3wby3cua0rRfglWiu5yjtfdwXS5X5jqxAVn+iHU D5/6ksrat5XfdtSt9sgf4V0ChWEhs40iXxF/pICpcnqFUmPupQQccRoFKAY0tFlqkx JBOSd9lhxNQEMgBubTFaXYhIbp4RkiZKNV2j+1EyX3y/cuIf3vu2U835HQ8leEQ4XI 4S5OHz0rtQtFA== Date: Thu, 15 May 2025 07:51:26 -0700 From: Kees Cook To: Shung-Hsi Yu , bpf@vger.kernel.org, linux-mm@kvack.org, Andrii Nakryiko , Ihor Solodrai CC: Andrew Morton , Michal Hocko , Vlastimil Babka , Uladzislau Rezki , linux-kernel@vger.kernel.org, linux-hardening@vger.kernel.org, regressions@lists.linux.dev, Greg Kroah-Hartman , Alexei Starovoitov , Daniel Borkmann , Pawan Gupta , Eduard Zingerman Subject: =?US-ASCII?Q?Re=3A_=5BREGRESSION=5D_bpf_verifier_slowdown_?= =?US-ASCII?Q?due_to_vrealloc=28=29_change_since_6=2E15-rc6?= User-Agent: K-9 Mail for Android In-Reply-To: <20250515-bpf-verifier-slowdown-vwo2meju4cgp2su5ckj@6gi6ssxbnfqg> References: <20250515-bpf-verifier-slowdown-vwo2meju4cgp2su5ckj@6gi6ssxbnfqg> Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Stat-Signature: 4hn7tazy7dkwjiajgdcjjudyk4w33ike X-Rspamd-Queue-Id: 31DD3A0002 X-Rspam-User: X-Rspamd-Server: rspam02 X-HE-Tag: 1747320691-926141 X-HE-Meta: U2FsdGVkX18dLlpYldOk5TRLGmA2yqLBvAKERISjbn0l42oAZbbRuxOve2VNabeh6lK7WhrNjYOJaDHn/dVh6gdxdEh6wo3CSxMni31orxwUsv/ePr8co1sv8u2qW5fjl434c2S4Hq5NYNY/5QBm4/MT01yM89Q7jvir0aDMnfQHPfsW7yVm64HO5afmercw/ZQYPK3TBJrLg92CbZWTDW6mYdavrnhbom+D9hSPprmGjUd0pGw7hqXNX1AnpRjoggV0C+o78bofiUsFg2qftQRlhpObNmb4aKLKz+ub6CyJAM0kp6O1gwgMn4JyOsuSYWBYcM+mki7np2D0aX2sbluhQ/ES7uRkPHGcn0Pa95T/45k4XNUjc4OvPwcqu/p1FMfaqsm/AUyNZW5FxjqgkHX8rNCCh7hJMYuwjPyfsq7+6tRR0Lrb3w7y0nd4xiogFTG3vhGRN8Fgcy0HhD6yG4gmFfnQkCyFaRNyek3PFsKzriR9n62IHtUxVaUtoG4JKjYymBiwnqHc0uGq8XHf4qsWCPFa4KQgnbv4Dgf3cP+L4wijDVEqffov8Ys3nPJvyNu9tCPxH6Ht9hwJ+7ZMAzmHvfNRgeURkp6Rjl8z0C/asDi8w6nZGpSyDXbF+j+Y4KLbM5+p0q/ouuBkBOvqBIi2kFoUlmfrFDuIEiLuFQ1jmQ28pwSKNnLlRpjU45GGmVqyBL36O67HGZo7XIknyJZsVnx93E6IXv8UCyXrz3W822jaGn5eCwpBzeygYuQ7OgdmanVTEjjawtNfT1ljr3/PX3Xfu1jbln/JC5w2XXXdgHtsqDUD+fn7/Sz/5Op1Qb40XPVH800sQ/3rMVP3CCNWZJZ7FkgxVEwI3/ZkgQjgOvRVaigpu2O0MjlC416D3vd6Mtn8/Nld2XxFQRqFd2UzQebDWkjhtjc5q5Uq88+IoMT6g4F4/Y4xyaUULUTi3geqI9DZus4Sf8FonHs 9FcMvPpI /DMbzO9i8vZaDwgA7UbdXEe+BOqa3yR+quqZ1lcLpr7H1UyacPTWeBM6RmgeLxUi6fCV9ZgpA2B0M+u+Fcc7wi2ncF8El3/zqBRssAZdfssQE+Vl/qNA7jG+GypbXyEKroCGpMfeh+CgkMcL9Gyhf2EbAv5W0YJTkLHIOQc2Th8qsDr3NzfDwUkJCi0p8IyFluRb8jyYLmg3hfijrYqpnqmBjeMy+dMnjjNN6bSEW8DD5a8qkGl7FtuCIAImGUusKcTsMv4Als5x3a33hOIZIRL3yLNtBVqBScGjd4Jwd5cvBOD6px8dN/IeuP1Hpz6rfq/wS7r6Y54Fs2LtoCqRKOmWDjwx1LVYmC2x1eWbmw8IzE/hboCf0Fc829e/55tC0BJZn X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: On May 15, 2025 6:12:25 AM PDT, Shung-Hsi Yu w= rote: >Hi, > >There is an observable slowdown when running BPF selftests on 6=2E15-rc6 >kernel[1] built with tools/testing/selftests/bpf/{config,config=2Ex86_64}= =2E >Overall the BPF selftests now takes 2x time to run (from ~25m to ~50m), >and for the verif_scale_loop3_fail it went from single digit seconds to >6 minutes=2E > >Bisect was done by Pawan and got to commit a0309faf1cb0 "mm: vmalloc: >support more granular vrealloc() sizing"[2]=2E To further zoom in the >issue, I tried removing the only kvrealloc() call in kernel/bpf/ by >reverting commit 96a30e469ca1 "bpf: use common instruction history >across all states", so _krealloc()_ was used instead of kvrealloc(), and >observe that there is _no_ slowdown[3]=2E While the bisect and the revert >is done on 6=2E14=2E7-rc2, I think it should stll be pretty representitiv= e=2E > >In short, the follow were tested: >- 6=2E15-rc6 (has a0309faf1cb0) -> slowdown >- 6=2E14=2E7-rc2 (has a0309faf1cb0) -> slowdown >- 6=2E14=2E7-rc2 (has a0309faf1cb0, call to kvrealloc in > kernel/bpf/verifier=2Ec replaced with krealloc) -> _no_ slowdown > >And the vrealloc() change is causing slowdown in kvrealloc() call within >push_insn_history()=2E This is very strange! The vrealloc change should make things faster -- it = removes potentially unneeded vmalloc and full object copies when it isn't n= eeded=2E Where can I find the =2Econfig for the slow runs? And how do I run the test myself directly? -Kees > > /* for any branch, call, exit record the history of jmps in the given s= tate */ > static int push_insn_history(struct bpf_verifier_env *env, struct bpf_v= erifier_state *cur, > int insn_flags, u64 linked_regs) > { > struct bpf_insn_hist_entry *p; > size_t alloc_size; > =2E=2E=2E > if (cur->insn_hist_end + 1 > env->insn_hist_cap) { > alloc_size =3D size_mul(cur->insn_hist_end + 1, sizeof(*p)); > p =3D kvrealloc(env->insn_hist, alloc_size, GFP_USER); > if (!p) > return -ENOMEM; > env->insn_hist =3D p; > env->insn_hist_cap =3D alloc_size / sizeof(*p); > } > =20 > p =3D &env->insn_hist[cur->insn_hist_end]; > p->idx =3D env->insn_idx; > p->prev_idx =3D env->prev_insn_idx; > p->flags =3D insn_flags; > p->linked_regs =3D linked_regs; > =20 > cur->insn_hist_end++; > env->cur_hist_ent =3D p; > =20 > return 0; > } > >BPF CI probably hasn't hit this yet because bpf-next have only got to >6=2E15-rc4=2E > >Shung-Hsi > >#regzbot introduced: a0309faf1cb0622cac7c820150b7abf2024acff5 > >1: https://github=2Ecom/shunghsiyu/libbpf/actions/runs/15038992168/job/42= 266125686 >2: https://lore=2Ekernel=2Eorg/stable/20250515041659=2Esmhllyarxdwp7cav@d= esk/ >3: https://github=2Ecom/shunghsiyu/libbpf/actions/runs/15043433548/job/42= 280277024 --=20 Kees Cook