linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
To: linux-kernel@vger.kernel.org
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
	stable@vger.kernel.org, Lorenz Bauer <lmb@cloudflare.com>,
	Alexei Starovoitov <ast@kernel.org>,
	Edward Cree <ecree.xilinx@gmail.com>
Subject: [PATCH 5.10 61/67] bpf: verifier: Allocate idmap scratch in verifier env
Date: Mon,  2 Aug 2021 15:45:24 +0200	[thread overview]
Message-ID: <20210802134341.134023420@linuxfoundation.org> (raw)
In-Reply-To: <20210802134339.023067817@linuxfoundation.org>

From: Lorenz Bauer <lmb@cloudflare.com>

commit c9e73e3d2b1eb1ea7ff068e05007eec3bd8ef1c9 upstream.

func_states_equal makes a very short lived allocation for idmap,
probably because it's too large to fit on the stack. However the
function is called quite often, leading to a lot of alloc / free
churn. Replace the temporary allocation with dedicated scratch
space in struct bpf_verifier_env.

Signed-off-by: Lorenz Bauer <lmb@cloudflare.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Edward Cree <ecree.xilinx@gmail.com>
Link: https://lore.kernel.org/bpf/20210429134656.122225-4-lmb@cloudflare.com
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
---
 include/linux/bpf_verifier.h |    8 +++++++
 kernel/bpf/verifier.c        |   46 ++++++++++++++-----------------------------
 2 files changed, 23 insertions(+), 31 deletions(-)

--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -204,6 +204,13 @@ struct bpf_idx_pair {
 	u32 idx;
 };
 
+struct bpf_id_pair {
+	u32 old;
+	u32 cur;
+};
+
+/* Maximum number of register states that can exist at once */
+#define BPF_ID_MAP_SIZE (MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE)
 #define MAX_CALL_FRAMES 8
 struct bpf_verifier_state {
 	/* call stack tracking */
@@ -401,6 +408,7 @@ struct bpf_verifier_env {
 	const struct bpf_line_info *prev_linfo;
 	struct bpf_verifier_log log;
 	struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1];
+	struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE];
 	struct {
 		int *insn_state;
 		int *insn_stack;
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -8962,13 +8962,6 @@ static bool range_within(struct bpf_reg_
 	       old->s32_max_value >= cur->s32_max_value;
 }
 
-/* Maximum number of register states that can exist at once */
-#define ID_MAP_SIZE	(MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE)
-struct idpair {
-	u32 old;
-	u32 cur;
-};
-
 /* If in the old state two registers had the same id, then they need to have
  * the same id in the new state as well.  But that id could be different from
  * the old state, so we need to track the mapping from old to new ids.
@@ -8979,11 +8972,11 @@ struct idpair {
  * So we look through our idmap to see if this old id has been seen before.  If
  * so, we require the new id to match; otherwise, we add the id pair to the map.
  */
-static bool check_ids(u32 old_id, u32 cur_id, struct idpair *idmap)
+static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)
 {
 	unsigned int i;
 
-	for (i = 0; i < ID_MAP_SIZE; i++) {
+	for (i = 0; i < BPF_ID_MAP_SIZE; i++) {
 		if (!idmap[i].old) {
 			/* Reached an empty slot; haven't seen this id before */
 			idmap[i].old = old_id;
@@ -9096,7 +9089,7 @@ next:
 
 /* Returns true if (rold safe implies rcur safe) */
 static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur,
-		    struct idpair *idmap)
+		    struct bpf_id_pair *idmap)
 {
 	bool equal;
 
@@ -9213,7 +9206,7 @@ static bool regsafe(struct bpf_reg_state
 
 static bool stacksafe(struct bpf_func_state *old,
 		      struct bpf_func_state *cur,
-		      struct idpair *idmap)
+		      struct bpf_id_pair *idmap)
 {
 	int i, spi;
 
@@ -9310,32 +9303,23 @@ static bool refsafe(struct bpf_func_stat
  * whereas register type in current state is meaningful, it means that
  * the current state will reach 'bpf_exit' instruction safely
  */
-static bool func_states_equal(struct bpf_func_state *old,
+static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_state *old,
 			      struct bpf_func_state *cur)
 {
-	struct idpair *idmap;
-	bool ret = false;
 	int i;
 
-	idmap = kcalloc(ID_MAP_SIZE, sizeof(struct idpair), GFP_KERNEL);
-	/* If we failed to allocate the idmap, just say it's not safe */
-	if (!idmap)
-		return false;
-
-	for (i = 0; i < MAX_BPF_REG; i++) {
-		if (!regsafe(&old->regs[i], &cur->regs[i], idmap))
-			goto out_free;
-	}
+	memset(env->idmap_scratch, 0, sizeof(env->idmap_scratch));
+	for (i = 0; i < MAX_BPF_REG; i++)
+		if (!regsafe(&old->regs[i], &cur->regs[i], env->idmap_scratch))
+			return false;
 
-	if (!stacksafe(old, cur, idmap))
-		goto out_free;
+	if (!stacksafe(old, cur, env->idmap_scratch))
+		return false;
 
 	if (!refsafe(old, cur))
-		goto out_free;
-	ret = true;
-out_free:
-	kfree(idmap);
-	return ret;
+		return false;
+
+	return true;
 }
 
 static bool states_equal(struct bpf_verifier_env *env,
@@ -9362,7 +9346,7 @@ static bool states_equal(struct bpf_veri
 	for (i = 0; i <= old->curframe; i++) {
 		if (old->frame[i]->callsite != cur->frame[i]->callsite)
 			return false;
-		if (!func_states_equal(old->frame[i], cur->frame[i]))
+		if (!func_states_equal(env, old->frame[i], cur->frame[i]))
 			return false;
 	}
 	return true;



  parent reply	other threads:[~2021-08-02 14:03 UTC|newest]

Thread overview: 83+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-08-02 13:44 [PATCH 5.10 00/67] 5.10.56-rc1 review Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 01/67] io_uring: fix null-ptr-deref in io_sq_offload_start() Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 02/67] x86/asm: Ensure asm/proto.h can be included stand-alone Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 03/67] pipe: make pipe writes always wake up readers Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 04/67] btrfs: fix rw device counting in __btrfs_free_extra_devids Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 05/67] btrfs: mark compressed range uptodate only if all bio succeed Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 06/67] Revert "ACPI: resources: Add checks for ACPI IRQ override" Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 07/67] ACPI: DPTF: Fix reading of attributes Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 08/67] x86/kvm: fix vcpu-id indexed array sizes Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 09/67] KVM: add missing compat KVM_CLEAR_DIRTY_LOG Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 10/67] ocfs2: fix zero out valid data Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 11/67] ocfs2: issue zeroout to EOF blocks Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 12/67] can: j1939: j1939_xtp_rx_dat_one(): fix rxtimer value between consecutive TP.DT to 750ms Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 13/67] can: raw: raw_setsockopt(): fix raw_rcv panic for sock UAF Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 14/67] can: peak_usb: pcan_usb_handle_bus_evt(): fix reading rxerr/txerr values Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 15/67] can: mcba_usb_start(): add missing urb->transfer_dma initialization Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 16/67] can: usb_8dev: fix memory leak Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 17/67] can: ems_usb: " Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 18/67] can: esd_usb2: " Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 19/67] alpha: register early reserved memory in memblock Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 20/67] HID: wacom: Re-enable touch by default for Cintiq 24HDT / 27QHDT Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 21/67] NIU: fix incorrect error return, missed in previous revert Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 22/67] drm/amd/display: ensure dentist display clock update finished in DCN20 Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 23/67] drm/amdgpu: Avoid printing of stack contents on firmware load error Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 24/67] drm/amdgpu: Fix resource leak on probe error path Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 25/67] blk-iocost: fix operation ordering in iocg_wake_fn() Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 26/67] nfc: nfcsim: fix use after free during module unload Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 27/67] cfg80211: Fix possible memory leak in function cfg80211_bss_update Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 28/67] RDMA/bnxt_re: Fix stats counters Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 29/67] bpf: Fix OOB read when printing XDP link fdinfo Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 30/67] mac80211: fix enabling 4-address mode on a sta vif after assoc Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 31/67] netfilter: conntrack: adjust stop timestamp to real expiry value Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 32/67] netfilter: nft_nat: allow to specify layer 4 protocol NAT only Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 33/67] i40e: Fix logic of disabling queues Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 34/67] i40e: Fix firmware LLDP agent related warning Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 35/67] i40e: Fix queue-to-TC mapping on Tx Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.10 36/67] i40e: Fix log TC creation failure when max num of queues is exceeded Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 37/67] tipc: fix implicit-connect for SYN+ Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 38/67] tipc: fix sleeping in tipc accept routine Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 39/67] net: Set true network header for ECN decapsulation Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 40/67] net: qrtr: fix memory leaks Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 41/67] ionic: remove intr coalesce update from napi Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 42/67] ionic: fix up dim accounting for tx and rx Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 43/67] ionic: count csum_none when offload enabled Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 44/67] tipc: do not write skb_shinfo frags when doing decrytion Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 45/67] octeontx2-pf: Fix interface down flag on error Greg Kroah-Hartman
2021-08-02 17:40   ` Pavel Machek
2021-08-02 13:45 ` [PATCH 5.10 46/67] mlx4: Fix missing error code in mlx4_load_one() Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 47/67] KVM: x86: Check the right feature bit for MSR_KVM_ASYNC_PF_ACK access Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 48/67] net: llc: fix skb_over_panic Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 49/67] drm/msm/dpu: Fix sm8250_mdp register length Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 50/67] drm/msm/dp: Initialize the INTF_CONFIG register Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 51/67] skmsg: Make sk_psock_destroy() static Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 52/67] net/mlx5: Fix flow table chaining Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 53/67] net/mlx5e: Fix nullptr in mlx5e_hairpin_get_mdev() Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 54/67] sctp: fix return value check in __sctp_rcv_asconf_lookup Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 55/67] tulip: windbond-840: Fix missing pci_disable_device() in probe and remove Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 56/67] sis900: " Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 57/67] can: hi311x: fix a signedness bug in hi3110_cmd() Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 58/67] bpf: Introduce BPF nospec instruction for mitigating Spectre v4 Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 59/67] bpf: Fix leakage due to insufficient speculative store bypass mitigation Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 60/67] bpf: Remove superfluous aux sanitation on subprog rejection Greg Kroah-Hartman
2021-08-02 13:45 ` Greg Kroah-Hartman [this message]
2021-08-02 13:45 ` [PATCH 5.10 62/67] bpf: Fix pointer arithmetic mask tightening under state pruning Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 63/67] SMB3: fix readpage for large swap cache Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 64/67] powerpc/pseries: Fix regression while building external modules Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 65/67] Revert "perf map: Fix dso->nsinfo refcounting" Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 66/67] i40e: Add additional info to PHY type error Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.10 67/67] can: j1939: j1939_session_deactivate(): clarify lifetime of session object Greg Kroah-Hartman
2021-08-02 16:23 ` [PATCH 5.10 00/67] 5.10.56-rc1 review Fox Chen
2021-08-02 17:49 ` Pavel Machek
2021-08-03  7:23 ` Naresh Kamboju
2021-08-03 10:38 ` Sudip Mukherjee
2021-08-03 11:13 ` Rudi Heitbaum
2021-08-03 19:16 ` Guenter Roeck
2021-08-03 19:26 ` Pavel Machek
2021-08-03 19:37   ` Guenter Roeck
2021-08-03 19:50     ` Pavel Machek
2021-08-03 20:52       ` Guenter Roeck
2021-08-04  6:21   ` Greg Kroah-Hartman
2021-08-04  6:25   ` Thomas Backlund
2021-08-04  6:35     ` Greg Kroah-Hartman
2021-08-04  3:05 ` Samuel Zou

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20210802134341.134023420@linuxfoundation.org \
    --to=gregkh@linuxfoundation.org \
    --cc=ast@kernel.org \
    --cc=ecree.xilinx@gmail.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=lmb@cloudflare.com \
    --cc=stable@vger.kernel.org \
    --subject='Re: [PATCH 5.10 61/67] bpf: verifier: Allocate idmap scratch in verifier env' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).