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 146F7C2D0CD for ; Thu, 15 May 2025 13:12:43 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 48B1B6B000A; Thu, 15 May 2025 09:12:42 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 410556B0082; Thu, 15 May 2025 09:12:42 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2B2A26B0083; Thu, 15 May 2025 09:12:42 -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 06B206B000A for ; Thu, 15 May 2025 09:12:42 -0400 (EDT) Received: from smtpin18.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id D02C7BD21C for ; Thu, 15 May 2025 13:12:42 +0000 (UTC) X-FDA: 83445181764.18.D8B8C54 Received: from mail-wr1-f65.google.com (mail-wr1-f65.google.com [209.85.221.65]) by imf27.hostedemail.com (Postfix) with ESMTP id DFCD44000A for ; Thu, 15 May 2025 13:12:40 +0000 (UTC) Authentication-Results: imf27.hostedemail.com; dkim=pass header.d=suse.com header.s=google header.b=B0dT0gmY; spf=pass (imf27.hostedemail.com: domain of shung-hsi.yu@suse.com designates 209.85.221.65 as permitted sender) smtp.mailfrom=shung-hsi.yu@suse.com; dmarc=pass (policy=quarantine) header.from=suse.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1747314761; 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:in-reply-to: references:dkim-signature; bh=9Sc7s4zPug7QCBZMgJvj3UJe25bWXU+WVGJNmLlNHLU=; b=BosugNF4UrchRUVWh+92Bj52NGio0gP5J0MlpGmejk3UZMHS7EOkF3i6I6adtTtkIZIEdC VRfc0ZSxGEUxyN//eUF3lDK+jE8dJ6aLAu92+oypLDhXyrbJ5XQ0X/Dlp4sUznLh5q9uFc jWpkRmuK2cZ+ik4+UdjzgIZZHdqeA3A= ARC-Authentication-Results: i=1; imf27.hostedemail.com; dkim=pass header.d=suse.com header.s=google header.b=B0dT0gmY; spf=pass (imf27.hostedemail.com: domain of shung-hsi.yu@suse.com designates 209.85.221.65 as permitted sender) smtp.mailfrom=shung-hsi.yu@suse.com; dmarc=pass (policy=quarantine) header.from=suse.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1747314761; a=rsa-sha256; cv=none; b=pYCyId7ry48NH6Bt8hzxYhmzVfDZx6vIF9nRM44chHGJZMsg/HN+iqJJEk1YdlTiIiuQHl qxh1l/1ciaykoR/3Jj45SB9VDowD9y6ZK2lzq+1+G/Tv/Rvm7tW3Wpwj4pY+Fq4W2LRlue OllVGCc6AaUUuDur3JFOU3Ds+/Fy/h0= Received: by mail-wr1-f65.google.com with SMTP id ffacd0b85a97d-3a0b9625662so804898f8f.3 for ; Thu, 15 May 2025 06:12:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.com; s=google; t=1747314759; x=1747919559; darn=kvack.org; h=content-disposition:mime-version:message-id:subject:cc:to:from:date :from:to:cc:subject:date:message-id:reply-to; bh=9Sc7s4zPug7QCBZMgJvj3UJe25bWXU+WVGJNmLlNHLU=; b=B0dT0gmY9VT6tNI+yhFwzY1ja37693G7izEr18tQwRRyt9rzU0oFzcdLp7OAC0EglR DQBUCaV/+UccKWjXfJNyG1C/egwn0nMHjkDW3PFDj+HyelzoMehOrgZ3G0opoGvU49PU eiiZaB1BRE059sRYZuCHCJkYXRNELhAe7POeqolR70G+FzhVYECo5+CKQAsPMShJ3FUu k1br/EmOYrGDqSAjG/c9rl46lXy201mqH0/Zyc9T0afYAduC9lKpB+af44/hONrPt5P+ UnZB3Fe2aAP7KBxBMVtOTOsPafEFmKEd25xV7cDQdZHZB/YFf0BWyIqgiFC1lH1H6j9e ltvQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1747314759; x=1747919559; h=content-disposition:mime-version:message-id:subject:cc:to:from:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=9Sc7s4zPug7QCBZMgJvj3UJe25bWXU+WVGJNmLlNHLU=; b=Q6dF6pPw3vP+Ox79K8MikyBtBqH3ImxwXncU6Qn0hW9XDsPwIfTYBDlbH1ZQJzb0L7 8fjC22W2JADG/Bg/aQiaYG8gDkmMlz0zkJPIHMfQri1l1AmWTeLmeFIMbmdwQSD3Yf1u JGbEYaS62dIKZSDlR/hIguKMKKOPc262t4IptsrWuSOjKIxDWttqwJd/9mn4Kyn2nBSD nhg4v3LvnK12bSQtBNTKAtf3KJa7TcULXSpK94KZPwNKOew/PY8WbItUajf3K1yRMHNk jPldZxrL02cYJbFguoswmHe0932v04KZ1JW4bMhv15gJxL8ruwt2ME2+kuxtHKxi+Ttj KD6A== X-Forwarded-Encrypted: i=1; AJvYcCWxEw03QCs3SiHH99Zwy3OiUcAlnVQcyqIrQZGccalLHU/u+FKVw3YRb2ZTTsNMpXcWOx+iT481RQ==@kvack.org X-Gm-Message-State: AOJu0Yzap7A7Nkxcs6kLKqS55pCBkj9IF5fmL+tzEJYJ6qC94yaS9J6i 0uRwEmDUtJ8zPgcR5XJHeEon0f8ixfdhluMq9j1bRt1P/9k1+GWJZ9y75f1D0CU= X-Gm-Gg: ASbGncuIODxdjKcuumvxvTvyne9/2IaD4If32FMz1o0PqSm5F2hTv+vAD9rEg4eL4gn tkHI6sEbyqc0BoVrRtdIssM2Ao7U9CH8HscPlQEDUOv7ig/+B4N8SF66AE63GzI5uUKG+vVVYkg lDbLmP/tQ41kDt4z6yF3S/1WPWIpGRHlvjLrvpzGwupjYc8ozyUQPcz60QZKGXRYBUHrFYTCVyE vFiDGR5BmssbO3wzeckY3FjnkBIBLojQcbg8J8aqnEXJVv7e18WlWUioVX9A3wHiIdLyOzkRdVh VBbjrLkP69H/31Vvv+iE+Aon7cbhq9Gc/6ijEWOmorNousnq7z2d7Cv4Bm3sxlE0+hFWsF2AcZs = X-Google-Smtp-Source: AGHT+IGU57xOouQYJOoHXSv7L1CzbOeG1YaSFTyHO9EqbI2SUzbIwPqP+E+vwOTbyIhTtUlFo0TsXw== X-Received: by 2002:a05:6000:2506:b0:3a0:8c45:d41b with SMTP id ffacd0b85a97d-3a3496a71b3mr6559388f8f.20.1747314759305; Thu, 15 May 2025 06:12:39 -0700 (PDT) Received: from u94a (1-174-3-124.dynamic-ip.hinet.net. [1.174.3.124]) by smtp.gmail.com with ESMTPSA id ada2fe7eead31-4df8299e6dbsm2404387137.14.2025.05.15.06.12.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 May 2025 06:12:38 -0700 (PDT) Date: Thu, 15 May 2025 21:12:25 +0800 From: Shung-Hsi Yu To: bpf@vger.kernel.org, linux-mm@kvack.org, Kees Cook , 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: [REGRESSION] bpf verifier slowdown due to vrealloc() change since 6.15-rc6 Message-ID: <20250515-bpf-verifier-slowdown-vwo2meju4cgp2su5ckj@6gi6ssxbnfqg> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Rspam-User: X-Rspamd-Queue-Id: DFCD44000A X-Rspamd-Server: rspam09 X-Stat-Signature: g68xuoanmbs6hga3e5p8w5wu39ikyopo X-HE-Tag: 1747314760-153216 X-HE-Meta: U2FsdGVkX18+5kusgReNcP+KALe1XihrInCBhECXTVn4O/qGgr5K2nw7ROPFH2pZUR7awI5hBAxN9Xl8rSMbKlojHDCOJVRtWY7L0g0sRW7IoOFnSEmXh6C6MINOHHzWcfSuMCBSyxEh/5MxdGrql+QEXHHP1VVNgUwZHCl9dsrRDWuH9NMiT80MSndfuKYU/CI9ogKE3kQZU/AD0v3XGmtcs7TcLPg4PMafpJmwqsXG33ijLad1KUBRccH5oCwFzZDRcjfymGwSWxQrxTovFDSXCkn3hRGS0hFiuiFVzfP4Pxbx1kGILiAWIVDgfy3ZPwzPRJHBH7TnBku70uKqdx1xcM0YdMBCuyg5Z0gViM9C4LOjkX92H+YVa3UK8G7KjSkRPR0H6/izkBfMq7PZA7O4fT5xoJUSHpAgXGWXqTqeSGejI6AAelIPBnS+JDqH7pk/3tNuvbK3fvlkUeAiggvDdU5S+qrmiMgvIJIV+MToj1+j3fyupjQVQ4xGGdpY85GmbsxAaoP9a8x2wbfTyZ6FX/m60Y2/5UNKj2pLdYoxI+jL4IyvYOfAePJMPHs/rQZeljtv4h3z/hTsqvGcKuxt2+WtL4OmB9FogTv7WWfJ81XSJf/WD6ZSqGmnvamUSjwFza1w0uBPHKJ6FtIQ7O3lWgU1vpzapDqgWUvgzGlUEpkSDJbXP3b9odmoMVl+xoYv9BYoo1lvbWdQhHcxhYcHwle7u4aLPz5+WWOeg+1sQ4eGVB93Povzhkj/aAe1zunKGRzWSUUUEzgZdagHa2jZNQYBLPnQczWktAvyCzXWywEMyT6M0bi2lesfIL8TXlpHAo2OgJFTv1Axe35mSYJJPQO3bK+b1APsk12mW0qqLDKTo5W67EGOnBlzamhrZrhZpCQloUBVl632beaW0xjoWHyWLOSmHQjIg4q4cdzL1BH2y7KLaeA7u2k5vLNox1v/sZQCHTeIIlInkMN sme8lPxh NNitFP5k2yuiXRzjl9TBz2ZxWLQ4wOUdezQLwdjCSJfOeVZzY0U7Aajjzlpz4gt+QvRynv/3ZYc1PFLxO+gbClsAx3iMoc12pgpZ7kDCmLT4ho2wRu0ABJWqeRW3LSNCvqo23S+fpECEwSnfS8rkPi8DJwFHjgXHtftfUmUlcwk6BPYWYpOoLoOAQotamG29+BdtAA9plqFyd9jiIYA+XFwzNPBM8rz8+O+EpGVezlkx6yx+3Zv3VFB1aCULx9pfK7VNRP02CKWTqvknmnd6bCTE5tVIvU8vdDJCrKE/7VRTp3f1376vUYEglogsrjqPj428bnsungieWTebLCibkK2m/gr0HPTZoPxm/ 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: Hi, There is an observable slowdown when running BPF selftests on 6.15-rc6 kernel[1] built with tools/testing/selftests/bpf/{config,config.x86_64}. 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. Bisect was done by Pawan and got to commit a0309faf1cb0 "mm: vmalloc: support more granular vrealloc() sizing"[2]. 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]. While the bisect and the revert is done on 6.14.7-rc2, I think it should stll be pretty representitive. In short, the follow were tested: - 6.15-rc6 (has a0309faf1cb0) -> slowdown - 6.14.7-rc2 (has a0309faf1cb0) -> slowdown - 6.14.7-rc2 (has a0309faf1cb0, call to kvrealloc in kernel/bpf/verifier.c replaced with krealloc) -> _no_ slowdown And the vrealloc() change is causing slowdown in kvrealloc() call within push_insn_history(). /* for any branch, call, exit record the history of jmps in the given state */ static int push_insn_history(struct bpf_verifier_env *env, struct bpf_verifier_state *cur, int insn_flags, u64 linked_regs) { struct bpf_insn_hist_entry *p; size_t alloc_size; ... if (cur->insn_hist_end + 1 > env->insn_hist_cap) { alloc_size = size_mul(cur->insn_hist_end + 1, sizeof(*p)); p = kvrealloc(env->insn_hist, alloc_size, GFP_USER); if (!p) return -ENOMEM; env->insn_hist = p; env->insn_hist_cap = alloc_size / sizeof(*p); } p = &env->insn_hist[cur->insn_hist_end]; p->idx = env->insn_idx; p->prev_idx = env->prev_insn_idx; p->flags = insn_flags; p->linked_regs = linked_regs; cur->insn_hist_end++; env->cur_hist_ent = p; return 0; } BPF CI probably hasn't hit this yet because bpf-next have only got to 6.15-rc4. Shung-Hsi #regzbot introduced: a0309faf1cb0622cac7c820150b7abf2024acff5 1: https://github.com/shunghsiyu/libbpf/actions/runs/15038992168/job/42266125686 2: https://lore.kernel.org/stable/20250515041659.smhllyarxdwp7cav@desk/ 3: https://github.com/shunghsiyu/libbpf/actions/runs/15043433548/job/42280277024