From patchwork Tue Jan 21 04:35:10 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Daniel Xu X-Patchwork-Id: 13945642 X-Patchwork-Delegate: bpf@iogearbox.net Received: from fhigh-a3-smtp.messagingengine.com (fhigh-a3-smtp.messagingengine.com [103.168.172.154]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 76D7A183CBB; Tue, 21 Jan 2025 04:35:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=103.168.172.154 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737434132; cv=none; b=sY/4v81Sn+R80ifbQ6/2Fr6a+U6WfGAj2QmogNWr/LmVoZUF507n9SkEznckNw0wsSEa0aI0bPjlS20f3WVB0QphxKSBx1obp7Rlqeaqlokb48x2OAkTII0oCZ+eO/43UuSEnhX+fd7etJeE+xybs3fyrnLnBK04R3nhRCc0OoM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737434132; c=relaxed/simple; bh=QkLoGrfKx1lD/I4UPNL0Gan5ka9GlqN3cHU5jJH96T4=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=otjnaKZoLsbS0/zyk6H6AuMRM6E6fBFkuu10L0qumjXRylJg4oQ5i7sWxOvW+ZNeghWp44sGq4wvqI+nUfXTHFUi06NeeJ34jJIyvmYlhZjP2bPRiw75dZPyGxHJiBTrb+H3oDOlIf9beMqaFJyaMTRZm+4r22h1j+lhKcSc62I= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=dxuuu.xyz; spf=pass smtp.mailfrom=dxuuu.xyz; dkim=pass (2048-bit key) header.d=dxuuu.xyz header.i=@dxuuu.xyz header.b=Vwq7Usiz; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=sb+iRa5s; arc=none smtp.client-ip=103.168.172.154 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=dxuuu.xyz Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=dxuuu.xyz Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=dxuuu.xyz header.i=@dxuuu.xyz header.b="Vwq7Usiz"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="sb+iRa5s" Received: from phl-compute-09.internal (phl-compute-09.phl.internal [10.202.2.49]) by mailfhigh.phl.internal (Postfix) with ESMTP id 87D021140214; Mon, 20 Jan 2025 23:35:29 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-09.internal (MEProxy); Mon, 20 Jan 2025 23:35:29 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=dxuuu.xyz; h=cc :cc:content-transfer-encoding:content-type:date:date:from:from :in-reply-to:in-reply-to:message-id:mime-version:references :reply-to:subject:subject:to:to; s=fm1; t=1737434129; x= 1737520529; bh=SZAXs5yTdoBGR6ZQCG+nPO0VZEYRp0DNDrMb+3A1LUA=; b=V wq7UsizgmRSAtAhP6fsx+fRn9f4QQtEpJUJrl0kjhRuonIfXn76GUx2AAW6ICs7X T3pNHjebJM1c7z6Qkb4cFQ45OsQ3SevP4l91jPaXLdrgYSvkUwDMzSUkPkSajv+0 /kMDXolyXK/dwF3noYOtvkT9DNAgK2ToChQqAOFspg/i91J1N+cW9kBamIMHGUkF iNlEEjLPJ11TH8h3fM2IKFVoPHYlkGQmK8vdjm4Hao/CRRJ4FKFeGtI552gPVi5V KPd/Svu6S04dfPgwHO9mUkqTxZk4yGLpEKBoVzTv6sbM98SJZ5j0qnjMgV0L3CfV w6+GVc8FwddXfK6MI5UJQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :content-type:date:date:feedback-id:feedback-id:from:from :in-reply-to:in-reply-to:message-id:mime-version:references :reply-to:subject:subject:to:to:x-me-proxy:x-me-sender :x-me-sender:x-sasl-enc; s=fm2; t=1737434129; x=1737520529; bh=S ZAXs5yTdoBGR6ZQCG+nPO0VZEYRp0DNDrMb+3A1LUA=; b=sb+iRa5s4Qvuz6BoR 5aQkypxCsK2zSg/9tipHtE6yLMraYZPaeSuBn2c0u9Wecn9i1EPiEYXnRuNztUeZ 4cIvxdbnPpjUQwZwsjIXm7Jenid8CGLmCkjCuaEnzoqSB0OyKlCiUQQpRxXLqEhF p/NTa1fKxpnSa0UwyHQ00DKtnGJfk1gD2ZJ3+DTA7H9TLM3Rzv+PWWOPjo9/d+mt kNKLUQcb+BB9zC5ikKY3iQ/fzxK513fR/ZVD6jeY/nWkAUqvE0ln9Njxnm4w2iyj CYis8o9B9B0BWxTydpoRLW0D5sbfJTWNWCrbDp9hUoF1Fyo3E61rRI8pHFSvKgaK g6Czw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefuddrudejtddgjedvucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucgfrhhlucfvnfffucdlje dtmdenucfjughrpefhvfevufffkffojghfggfgsedtkeertdertddtnecuhfhrohhmpeff rghnihgvlhcuighuuceougiguhesugiguhhuuhdrgiihiieqnecuggftrfgrthhtvghrnh epgfefgfegjefhudeikedvueetffelieefuedvhfehjeeljeejkefgffeghfdttdetnecu vehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepugiguhesug iguhhuuhdrgiihiidpnhgspghrtghpthhtohepudegpdhmohguvgepshhmthhpohhuthdp rhgtphhtthhopegurghnihgvlhesihhoghgvrghrsghogidrnhgvthdprhgtphhtthhope grshhtsehkvghrnhgvlhdrohhrghdprhgtphhtthhopegrnhgurhhiiheskhgvrhhnvghl rdhorhhgpdhrtghpthhtohepjhhohhhnrdhfrghsthgrsggvnhgusehgmhgrihhlrdgtoh hmpdhrtghpthhtohepmhgrrhhtihhnrdhlrghusehlihhnuhigrdguvghvpdhrtghpthht ohepvgguugihiiekjeesghhmrghilhdrtghomhdprhgtphhtthhopehsohhngheskhgvrh hnvghlrdhorhhgpdhrtghpthhtohephihonhhghhhonhhgrdhsohhngheslhhinhhugidr uggvvhdprhgtphhtthhopehkphhsihhnghhhsehkvghrnhgvlhdrohhrgh X-ME-Proxy: Feedback-ID: i6a694271:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 20 Jan 2025 23:35:27 -0500 (EST) From: Daniel Xu To: daniel@iogearbox.net, ast@kernel.org, andrii@kernel.org Cc: john.fastabend@gmail.com, martin.lau@linux.dev, eddyz87@gmail.com, song@kernel.org, yonghong.song@linux.dev, kpsingh@kernel.org, sdf@fomichev.me, haoluo@google.com, jolsa@kernel.org, bpf@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [PATCH bpf-next 1/3] bpf: verifier: Store null elision decision in insn_aux_data Date: Mon, 20 Jan 2025 21:35:10 -0700 Message-ID: <222efbc63de2519fd345e558cf27649220ccffa2.1737433945.git.dxu@dxuuu.xyz> X-Mailer: git-send-email 2.47.1 In-Reply-To: References: Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net Save the null elision decision from verification so that it can be reused later during bpf_map_lookup_elem inlining. There's a generated jump that can be omitted if the null was elided. Signed-off-by: Daniel Xu --- include/linux/bpf_verifier.h | 4 ++++ kernel/bpf/verifier.c | 4 +++- 2 files changed, 7 insertions(+), 1 deletion(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 32c23f2a3086..1bcd6d66e546 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -515,6 +515,10 @@ struct bpf_map_ptr_state { struct bpf_map *map_ptr; bool poison; bool unpriv; + /* true if instruction is a bpf_map_lookup_elem() with statically + * known in-bounds key. + */ + bool inbounds; }; /* Possible states for alu_state member. */ diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 74525392714e..e83145c2260d 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -11265,8 +11265,10 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn if (func_id == BPF_FUNC_map_lookup_elem && can_elide_value_nullness(meta.map_ptr->map_type) && meta.const_map_key >= 0 && - meta.const_map_key < meta.map_ptr->max_entries) + meta.const_map_key < meta.map_ptr->max_entries) { ret_flag &= ~PTR_MAYBE_NULL; + env->insn_aux_data[insn_idx].map_ptr_state.inbounds = true; + } regs[BPF_REG_0].map_ptr = meta.map_ptr; regs[BPF_REG_0].map_uid = meta.map_uid; From patchwork Tue Jan 21 04:35:11 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Daniel Xu X-Patchwork-Id: 13945643 X-Patchwork-Delegate: bpf@iogearbox.net Received: from flow-a8-smtp.messagingengine.com (flow-a8-smtp.messagingengine.com [103.168.172.143]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C20491A4F0A; Tue, 21 Jan 2025 04:35:33 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=103.168.172.143 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737434135; cv=none; b=d9Q9Elp+u5WIt8e93Ij7LT2+c/EO1kcCxz8amAG6QQ6mrae8D4ctWHTT1ABegGZJpgG1GLW45BvQdH/US40DlyUOVu6WnOyuhMxF9xgrg4awXvvPoWSUvADlRA10C7d+Wkj/7f+96HgPLG/EZCijIZXrtxq71fMXx4D9gIp4iB0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737434135; c=relaxed/simple; bh=AWT6UplJsuwd3Z1amd6LIjTyP84SpScj+bGO3VyIbJE=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=NvxhxZijFylQR8z44evSJjwSWzA7t6MseWdvBjt32AbPBCLQKCcQZB2FoB4dMhhlOAbI73rXna3UMt/qEPkgWUMdkziLH1XOGO4MBiSJGJCVihvwIms7l18Mv0EsjKoVN6fXcJpcdYWy/8d2k9Ur5ZotnE6Ev8wafqszPHsPT8Y= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=dxuuu.xyz; spf=pass smtp.mailfrom=dxuuu.xyz; dkim=pass (2048-bit key) header.d=dxuuu.xyz header.i=@dxuuu.xyz header.b=VNzQwPI4; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=d7UykF9W; arc=none smtp.client-ip=103.168.172.143 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=dxuuu.xyz Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=dxuuu.xyz Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=dxuuu.xyz header.i=@dxuuu.xyz header.b="VNzQwPI4"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="d7UykF9W" Received: from phl-compute-11.internal (phl-compute-11.phl.internal [10.202.2.51]) by mailflow.phl.internal (Postfix) with ESMTP id A0055201296; Mon, 20 Jan 2025 23:35:32 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-11.internal (MEProxy); Mon, 20 Jan 2025 23:35:32 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=dxuuu.xyz; h=cc :cc:content-transfer-encoding:content-type:date:date:from:from :in-reply-to:in-reply-to:message-id:mime-version:references :reply-to:subject:subject:to:to; s=fm1; t=1737434132; x= 1737441332; bh=EuqqOj/JE/BXRgo4FV0CYOWoLTXMMcc6C+q/QgacqSc=; b=V NzQwPI45itkIfm7FMr02QLiNF/FIxeRPwv5cYz9vW/qL+QM/TV8kU59EWUv8HR0T J0wNWyN4WfHvgwNtgo+tlWkkbMdZrcxk8M18sP+YHWtJNtaFrSBnoSRvosP4VW9L wVGHOhupBlHleo9RJDcinFj9HzP5/yijn/tpGzX/uts15zDiT2PZOVsNZWM5hrAm 8SCDVpldyE/865f4IrJR/QuvOJ9qGkSEBO8nPo6/Qytz/+IsD0sn55GiIM+rOB03 7llPQ03q6J/Iv2KovM6nGBXTl7WJL4y4CDW0jZgIYs9cpxHOdQI4ac5i3dlAhyiS rGdCDPu5PapGGSbpuISKQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :content-type:date:date:feedback-id:feedback-id:from:from :in-reply-to:in-reply-to:message-id:mime-version:references :reply-to:subject:subject:to:to:x-me-proxy:x-me-sender :x-me-sender:x-sasl-enc; s=fm2; t=1737434132; x=1737441332; bh=E uqqOj/JE/BXRgo4FV0CYOWoLTXMMcc6C+q/QgacqSc=; b=d7UykF9WoPjVYzhEs nzNHGB0EtNBA1jNgsdmLIKcNu/famaq+oR6eIdh098hlLTCsYHI/QYQB51J3aV8e s0MNUrduJchkPJBEMDY7TB+hESi/+fZrDXN+N09livksHCbQ73cGsBBxyzFMuH+w liEqCEsAUQkstRQjWcIwNj1tScqjMTE8rUB5bCndkXlIH2AdRdoBLYsXzXUhDWFF 9uchp1ZkjtgJl2RCnB6ACbf0HXRFLN6IQHSSM8+VJ89PXXK4MzzAtNW2P/DI4mij 2M+hiU9tlTfuqO53RbPRMzyFCyi3bEHF5TwMSqx6mVb5ihiq+HY2e7UPraH7kIXc o7rLw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefuddrudejtddgjedvucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucgfrhhlucfvnfffucdlje dtmdenucfjughrpefhvfevufffkffojghfggfgsedtkeertdertddtnecuhfhrohhmpeff rghnihgvlhcuighuuceougiguhesugiguhhuuhdrgiihiieqnecuggftrfgrthhtvghrnh epgfefgfegjefhudeikedvueetffelieefuedvhfehjeeljeejkefgffeghfdttdetnecu vehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepugiguhesug iguhhuuhdrgiihiidpnhgspghrtghpthhtohepvdehpdhmohguvgepshhmthhpohhuthdp rhgtphhtthhopehprggsvghnihesrhgvughhrghtrdgtohhmpdhrtghpthhtohepkhhusg grsehkvghrnhgvlhdrohhrghdprhgtphhtthhopehhrgifkheskhgvrhhnvghlrdhorhhg pdhrtghpthhtohepmhgrtghivghjrdhfihhjrghlkhhofihskhhisehinhhtvghlrdgtoh hmpdhrtghpthhtoheprghstheskhgvrhhnvghlrdhorhhgpdhrtghpthhtohepvgguuhhm rgiivghtsehgohhoghhlvgdrtghomhdprhgtphhtthhopegurghnihgvlhesihhoghgvrg hrsghogidrnhgvthdprhgtphhtthhopegurghvvghmsegurghvvghmlhhofhhtrdhnvght pdhrtghpthhtohepsghjohhrnheskhgvrhhnvghlrdhorhhg X-ME-Proxy: Feedback-ID: i6a694271:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 20 Jan 2025 23:35:29 -0500 (EST) From: Daniel Xu To: pabeni@redhat.com, kuba@kernel.org, hawk@kernel.org, maciej.fijalkowski@intel.com, ast@kernel.org, edumazet@google.com, daniel@iogearbox.net, davem@davemloft.net, bjorn@kernel.org, john.fastabend@gmail.com, magnus.karlsson@intel.com, andrii@kernel.org Cc: martin.lau@linux.dev, eddyz87@gmail.com, song@kernel.org, yonghong.song@linux.dev, kpsingh@kernel.org, sdf@fomichev.me, haoluo@google.com, jolsa@kernel.org, jonathan.lemon@gmail.com, horms@kernel.org, bpf@vger.kernel.org, linux-kernel@vger.kernel.org, netdev@vger.kernel.org Subject: [PATCH bpf-next 2/3] bpf: map: Thread null elision metadata to map_gen_lookup Date: Mon, 20 Jan 2025 21:35:11 -0700 Message-ID: <2050196010b1bf1efa357cfddebd15a152582bb4.1737433945.git.dxu@dxuuu.xyz> X-Mailer: git-send-email 2.47.1 In-Reply-To: References: Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net Add an extra parameter to map_gen_lookup callback so that if the lookup is known to be inbounds, the bounds check can be omitted. The next commit will take advantage of this new information. Signed-off-by: Daniel Xu --- include/linux/bpf.h | 2 +- kernel/bpf/arraymap.c | 11 ++++++++--- kernel/bpf/hashtab.c | 14 ++++++++++---- kernel/bpf/verifier.c | 2 +- net/xdp/xskmap.c | 4 +++- 5 files changed, 23 insertions(+), 10 deletions(-) diff --git a/include/linux/bpf.h b/include/linux/bpf.h index feda0ce90f5a..da8b420095c9 100644 --- a/include/linux/bpf.h +++ b/include/linux/bpf.h @@ -117,7 +117,7 @@ struct bpf_map_ops { * may manipulate it, exists. */ void (*map_fd_put_ptr)(struct bpf_map *map, void *ptr, bool need_defer); - int (*map_gen_lookup)(struct bpf_map *map, struct bpf_insn *insn_buf); + int (*map_gen_lookup)(struct bpf_map *map, struct bpf_insn *insn_buf, bool inbounds); u32 (*map_fd_sys_lookup_elem)(void *ptr); void (*map_seq_show_elem)(struct bpf_map *map, void *key, struct seq_file *m); diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c index eb28c0f219ee..8dbdceeead95 100644 --- a/kernel/bpf/arraymap.c +++ b/kernel/bpf/arraymap.c @@ -205,7 +205,9 @@ static int array_map_direct_value_meta(const struct bpf_map *map, u64 imm, } /* emit BPF instructions equivalent to C code of array_map_lookup_elem() */ -static int array_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf) +static int array_map_gen_lookup(struct bpf_map *map, + struct bpf_insn *insn_buf, + bool inbounds) { struct bpf_array *array = container_of(map, struct bpf_array, map); struct bpf_insn *insn = insn_buf; @@ -250,7 +252,9 @@ static void *percpu_array_map_lookup_elem(struct bpf_map *map, void *key) } /* emit BPF instructions equivalent to C code of percpu_array_map_lookup_elem() */ -static int percpu_array_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf) +static int percpu_array_map_gen_lookup(struct bpf_map *map, + struct bpf_insn *insn_buf, + bool inbounds) { struct bpf_array *array = container_of(map, struct bpf_array, map); struct bpf_insn *insn = insn_buf; @@ -1392,7 +1396,8 @@ static void *array_of_map_lookup_elem(struct bpf_map *map, void *key) } static int array_of_map_gen_lookup(struct bpf_map *map, - struct bpf_insn *insn_buf) + struct bpf_insn *insn_buf, + bool inbounds) { struct bpf_array *array = container_of(map, struct bpf_array, map); u32 elem_size = array->elem_size; diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c index 4a9eeb7aef85..103cdab85977 100644 --- a/kernel/bpf/hashtab.c +++ b/kernel/bpf/hashtab.c @@ -720,7 +720,9 @@ static void *htab_map_lookup_elem(struct bpf_map *map, void *key) * bpf_prog * __htab_map_lookup_elem */ -static int htab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf) +static int htab_map_gen_lookup(struct bpf_map *map, + struct bpf_insn *insn_buf, + bool inbounds) { struct bpf_insn *insn = insn_buf; const int ret = BPF_REG_0; @@ -760,7 +762,8 @@ static void *htab_lru_map_lookup_elem_sys(struct bpf_map *map, void *key) } static int htab_lru_map_gen_lookup(struct bpf_map *map, - struct bpf_insn *insn_buf) + struct bpf_insn *insn_buf, + bool inbounds) { struct bpf_insn *insn = insn_buf; const int ret = BPF_REG_0; @@ -2342,7 +2345,9 @@ static void *htab_percpu_map_lookup_elem(struct bpf_map *map, void *key) } /* inline bpf_map_lookup_elem() call for per-CPU hashmap */ -static int htab_percpu_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf) +static int htab_percpu_map_gen_lookup(struct bpf_map *map, + struct bpf_insn *insn_buf, + bool inbounds) { struct bpf_insn *insn = insn_buf; @@ -2626,7 +2631,8 @@ static void *htab_of_map_lookup_elem(struct bpf_map *map, void *key) } static int htab_of_map_gen_lookup(struct bpf_map *map, - struct bpf_insn *insn_buf) + struct bpf_insn *insn_buf, + bool inbounds) { struct bpf_insn *insn = insn_buf; const int ret = BPF_REG_0; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index e83145c2260d..2ed2fd3c42f2 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -21582,7 +21582,7 @@ static int do_misc_fixups(struct bpf_verifier_env *env) ops = map_ptr->ops; if (insn->imm == BPF_FUNC_map_lookup_elem && ops->map_gen_lookup) { - cnt = ops->map_gen_lookup(map_ptr, insn_buf); + cnt = ops->map_gen_lookup(map_ptr, insn_buf, aux->map_ptr_state.inbounds); if (cnt == -EOPNOTSUPP) goto patch_map_ops_generic; if (cnt <= 0 || cnt >= INSN_BUF_SIZE) { diff --git a/net/xdp/xskmap.c b/net/xdp/xskmap.c index afa457506274..78579583b0a1 100644 --- a/net/xdp/xskmap.c +++ b/net/xdp/xskmap.c @@ -118,7 +118,9 @@ static int xsk_map_get_next_key(struct bpf_map *map, void *key, void *next_key) return 0; } -static int xsk_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf) +static int xsk_map_gen_lookup(struct bpf_map *map, + struct bpf_insn *insn_buf, + bool inbounds) { const int ret = BPF_REG_0, mp = BPF_REG_1, index = BPF_REG_2; struct bpf_insn *insn = insn_buf; From patchwork Tue Jan 21 04:35:12 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Daniel Xu X-Patchwork-Id: 13945644 X-Patchwork-Delegate: bpf@iogearbox.net Received: from fhigh-a3-smtp.messagingengine.com (fhigh-a3-smtp.messagingengine.com [103.168.172.154]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 60B5B1A8F7A; Tue, 21 Jan 2025 04:35:35 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=103.168.172.154 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737434137; cv=none; b=GmClSL3FaDLIhLNlwt9hL1kINettp2iJ1nBQypv9m4eYL716RJDa/3osyaA5LyrhA+8c4MuzhtSw2PP7eU9rXBXd/8dpqBVdkdPCkMoDutI7QKGznVGVSGD6vlEahhmkg1ILOjKrnWI9jWFRtPs2HJHZvAQbqmkSGRQ2pah7KfM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737434137; c=relaxed/simple; bh=eVM7SdtXCFlUVH4oy/Vkcn3phtLYk4plrqvtCWZRjUY=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=X6DNZmNiCyEdGU3spfW8dmQSq56JR/TRTo9O6vGOmO/w0aNKEZQZn6wS3upoK64Ewy7KGMdYbDKKedC45NyQ9Jz4CnXxgH4PWYtjtW9N6+tsR0H+2OpRC/WiHipd3h+AychiE/y2bC3rmvliTTZTV9QeUxAiD+vVrN+PDx/EDco= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=dxuuu.xyz; spf=pass smtp.mailfrom=dxuuu.xyz; dkim=pass (2048-bit key) header.d=dxuuu.xyz header.i=@dxuuu.xyz header.b=ZLc7tUfQ; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=SSAL5ixW; arc=none smtp.client-ip=103.168.172.154 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=dxuuu.xyz Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=dxuuu.xyz Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=dxuuu.xyz header.i=@dxuuu.xyz header.b="ZLc7tUfQ"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="SSAL5ixW" Received: from phl-compute-01.internal (phl-compute-01.phl.internal [10.202.2.41]) by mailfhigh.phl.internal (Postfix) with ESMTP id A922111401CA; Mon, 20 Jan 2025 23:35:34 -0500 (EST) Received: from phl-mailfrontend-01 ([10.202.2.162]) by phl-compute-01.internal (MEProxy); Mon, 20 Jan 2025 23:35:34 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=dxuuu.xyz; h=cc :cc:content-transfer-encoding:content-type:date:date:from:from :in-reply-to:in-reply-to:message-id:mime-version:references :reply-to:subject:subject:to:to; s=fm1; t=1737434134; x= 1737520534; bh=rLsYj07eT2ZgMjURoHuQghZV4EHGquLJkQ6YJEcpFpQ=; b=Z Lc7tUfQPfpSIDE8rmrR+JI286lmvZbFvC7/2tLp5A4KswkXteX53qnyliP27Khqi BvoJs1MIsDeBWDOFl1LlbxV5a800IwK4AJ+tqaxyarxP79BoojTgwPk1jdQAnUlE dohhjMzi6ObQDST56uaDrQRB/YMc0ITThtttt/ZulCBXuNf9LhUuz80TGEo2nrJP /LbhzNDF5RGeg20zRGJnfrxs0nyAx4kHksn8uA+BCLj49NQ+gbAL6D3MlxR73QTK tMXsQSFF8qx3swCgQfr/63FM9z203NxCAol9NeY5RTuOjf+qikj7LrrtUGdM31p/ /Dv2Pg6oJe9afcXryDM3Q== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :content-type:date:date:feedback-id:feedback-id:from:from :in-reply-to:in-reply-to:message-id:mime-version:references :reply-to:subject:subject:to:to:x-me-proxy:x-me-sender :x-me-sender:x-sasl-enc; s=fm2; t=1737434134; x=1737520534; bh=r LsYj07eT2ZgMjURoHuQghZV4EHGquLJkQ6YJEcpFpQ=; b=SSAL5ixWDnss6aW2j 9DjM2r9L33oINZKhHGk2cxZpvCzOC//HeN0DiWxB47CnZeiGa1NTPxsG+MHt3DmI ELa64sZU9c4g6iqhdKoyuDFfm9O2i/wCjt3Spb4YBibnv1XXyDkdwU9SkdeN8lwu 8N/Z8V1WpJ5SSBhCFKuHZO5PfRr7iWVdIdeBySeuGGP7yc5MaxKCwdxZ+O4oep35 x+723wcbr5Xjll6LkoNAu3NecFL6oe++ivCzbK+0IXsxvY4XgBdaD26D8Mjc1jJm QG8cgusjbGIvehFczGXwX/7bePtomfErTiU58FPPHzrfJz5dcuj1h/V8lT1UjR+C Q/goQ== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefuddrudejtddgjeefucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucgfrhhlucfvnfffucdlje dtmdenucfjughrpefhvfevufffkffojghfggfgsedtkeertdertddtnecuhfhrohhmpeff rghnihgvlhcuighuuceougiguhesugiguhhuuhdrgiihiieqnecuggftrfgrthhtvghrnh epgfefgfegjefhudeikedvueetffelieefuedvhfehjeeljeejkefgffeghfdttdetnecu vehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepugiguhesug iguhhuuhdrgiihiidpnhgspghrtghpthhtohepudegpdhmohguvgepshhmthhpohhuthdp rhgtphhtthhopegurghnihgvlhesihhoghgvrghrsghogidrnhgvthdprhgtphhtthhope grshhtsehkvghrnhgvlhdrohhrghdprhgtphhtthhopegrnhgurhhiiheskhgvrhhnvghl rdhorhhgpdhrtghpthhtohepmhgrrhhtihhnrdhlrghusehlihhnuhigrdguvghvpdhrtg hpthhtohepvgguugihiiekjeesghhmrghilhdrtghomhdprhgtphhtthhopehsohhnghes khgvrhhnvghlrdhorhhgpdhrtghpthhtohephihonhhghhhonhhgrdhsohhngheslhhinh hugidruggvvhdprhgtphhtthhopehjohhhnhdrfhgrshhtrggsvghnugesghhmrghilhdr tghomhdprhgtphhtthhopehkphhsihhnghhhsehkvghrnhgvlhdrohhrgh X-ME-Proxy: Feedback-ID: i6a694271:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 20 Jan 2025 23:35:32 -0500 (EST) From: Daniel Xu To: daniel@iogearbox.net, ast@kernel.org, andrii@kernel.org Cc: martin.lau@linux.dev, eddyz87@gmail.com, song@kernel.org, yonghong.song@linux.dev, john.fastabend@gmail.com, kpsingh@kernel.org, sdf@fomichev.me, haoluo@google.com, jolsa@kernel.org, bpf@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [PATCH bpf-next 3/3] bpf: arraymap: Skip boundscheck during inlining when possible Date: Mon, 20 Jan 2025 21:35:12 -0700 Message-ID: <7bfb3b6b1d3400d03fd9b7a7e15586c826449c71.1737433945.git.dxu@dxuuu.xyz> X-Mailer: git-send-email 2.47.1 In-Reply-To: References: Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net For regular arraymaps and percpu arraymaps, if the lookup is known to be inbounds, the inlined bounds check can be omitted. One fewer jump puts less pressure on the branch predictor. While it probably won't affect real workloads much, we can basically get this for free. So might as well - free wins are nice. JIT diff for regular arraymap (x86-64): ; val = bpf_map_lookup_elem(&map_array, &key); - 22: movabsq $-131387164803072, %rdi + 22: movabsq $-131387246749696, %rdi 2c: addq $472, %rdi 33: movl (%rsi), %eax - 36: cmpq $2, %rax - 3a: jae 0x45 - 3c: imulq $48, %rax, %rax - 40: addq %rdi, %rax - 43: jmp 0x47 - 45: xorl %eax, %eax - 47: movl $4, %edi + 36: imulq $48, %rax, %rax + 3a: addq %rdi, %rax + 3d: jmp 0x41 + 3f: xorl %eax, %eax + 41: movl $4, %edi JIT diff for percpu arraymap (x86-64): ; val = bpf_map_lookup_elem(&map_array_pcpu, &key); - 22: movabsq $-131387183532032, %rdi + 22: movabsq $-131387273779200, %rdi 2c: addq $472, %rdi 33: movl (%rsi), %eax - 36: cmpq $2, %rax - 3a: jae 0x52 - 3c: shlq $3, %rax - 40: addq %rdi, %rax - 43: movq (%rax), %rax - 47: addq %gs:170664, %rax - 50: jmp 0x54 - 52: xorl %eax, %eax - 54: movl $4, %edi + 36: shlq $3, %rax + 3a: addq %rdi, %rax + 3d: movq (%rax), %rax + 41: addq %gs:170664, %rax + 4a: jmp 0x4e + 4c: xorl %eax, %eax + 4e: movl $4, %edi Signed-off-by: Daniel Xu --- kernel/bpf/arraymap.c | 24 ++++++++++++++---------- 1 file changed, 14 insertions(+), 10 deletions(-) diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c index 8dbdceeead95..7385104dc0d0 100644 --- a/kernel/bpf/arraymap.c +++ b/kernel/bpf/arraymap.c @@ -221,11 +221,13 @@ static int array_map_gen_lookup(struct bpf_map *map, *insn++ = BPF_ALU64_IMM(BPF_ADD, map_ptr, offsetof(struct bpf_array, value)); *insn++ = BPF_LDX_MEM(BPF_W, ret, index, 0); - if (!map->bypass_spec_v1) { - *insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 4); - *insn++ = BPF_ALU32_IMM(BPF_AND, ret, array->index_mask); - } else { - *insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 3); + if (!inbounds) { + if (!map->bypass_spec_v1) { + *insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 4); + *insn++ = BPF_ALU32_IMM(BPF_AND, ret, array->index_mask); + } else { + *insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 3); + } } if (is_power_of_2(elem_size)) { @@ -269,11 +271,13 @@ static int percpu_array_map_gen_lookup(struct bpf_map *map, *insn++ = BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, offsetof(struct bpf_array, pptrs)); *insn++ = BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_2, 0); - if (!map->bypass_spec_v1) { - *insn++ = BPF_JMP_IMM(BPF_JGE, BPF_REG_0, map->max_entries, 6); - *insn++ = BPF_ALU32_IMM(BPF_AND, BPF_REG_0, array->index_mask); - } else { - *insn++ = BPF_JMP_IMM(BPF_JGE, BPF_REG_0, map->max_entries, 5); + if (!inbounds) { + if (!map->bypass_spec_v1) { + *insn++ = BPF_JMP_IMM(BPF_JGE, BPF_REG_0, map->max_entries, 6); + *insn++ = BPF_ALU32_IMM(BPF_AND, BPF_REG_0, array->index_mask); + } else { + *insn++ = BPF_JMP_IMM(BPF_JGE, BPF_REG_0, map->max_entries, 5); + } } *insn++ = BPF_ALU64_IMM(BPF_LSH, BPF_REG_0, 3);