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.13 094/104] bpf: verifier: Allocate idmap scratch in verifier env
Date: Mon,  2 Aug 2021 15:45:31 +0200	[thread overview]
Message-ID: <20210802134347.102414407@linuxfoundation.org> (raw)
In-Reply-To: <20210802134344.028226640@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
@@ -215,6 +215,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 */
@@ -418,6 +425,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
@@ -9779,13 +9779,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.
@@ -9796,11 +9789,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;
@@ -9913,7 +9906,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;
 
@@ -10031,7 +10024,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;
 
@@ -10128,32 +10121,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,
@@ -10180,7 +10164,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:16 UTC|newest]

Thread overview: 109+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-08-02 13:43 [PATCH 5.13 000/104] 5.13.8-rc1 review Greg Kroah-Hartman
2021-08-02 13:43 ` [PATCH 5.13 001/104] pipe: make pipe writes always wake up readers Greg Kroah-Hartman
2021-08-02 13:43 ` [PATCH 5.13 002/104] fs/ext2: Avoid page_address on pages returned by ext2_get_page Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 003/104] btrfs: fix lost inode on log replay after mix of fsync, rename and inode eviction Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 004/104] btrfs: fix rw device counting in __btrfs_free_extra_devids Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 005/104] btrfs: mark compressed range uptodate only if all bio succeed Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 006/104] Revert "ACPI: resources: Add checks for ACPI IRQ override" Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 007/104] ACPI: DPTF: Fix reading of attributes Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 008/104] x86/kvm: fix vcpu-id indexed array sizes Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 009/104] KVM: add missing compat KVM_CLEAR_DIRTY_LOG Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 010/104] ocfs2: fix zero out valid data Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 011/104] ocfs2: issue zeroout to EOF blocks Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 012/104] mm: memcontrol: fix blocking rstat function called from atomic cgroup1 thresholding code Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 013/104] mm/memcg: fix NULL pointer dereference in memcg_slab_free_hook() Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 014/104] 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.13 015/104] can: raw: raw_setsockopt(): fix raw_rcv panic for sock UAF Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 016/104] can: peak_usb: pcan_usb_handle_bus_evt(): fix reading rxerr/txerr values Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 017/104] can: mcba_usb_start(): add missing urb->transfer_dma initialization Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 018/104] can: usb_8dev: fix memory leak Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 019/104] can: ems_usb: " Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 020/104] can: esd_usb2: " Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 021/104] alpha: register early reserved memory in memblock Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 022/104] HID: wacom: Re-enable touch by default for Cintiq 24HDT / 27QHDT Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 023/104] net: stmmac: add est_irq_status callback function for GMAC 4.10 and 5.10 Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 024/104] NIU: fix incorrect error return, missed in previous revert Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 025/104] drm/amd/display: ensure dentist display clock update finished in DCN20 Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 026/104] drm/amdgpu: Check pmops for desired suspend state Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 027/104] drm/amdgpu: Avoid printing of stack contents on firmware load error Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 028/104] drm/amdgpu: Fix resource leak on probe error path Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 029/104] blk-iocost: fix operation ordering in iocg_wake_fn() Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 030/104] nfc: nfcsim: fix use after free during module unload Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 031/104] io_uring: fix io_prep_async_link locking Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 032/104] io_uring: dont block level reissue off completion path Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 033/104] io_uring: fix poll requests leaking second poll entries Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 034/104] cfg80211: Fix possible memory leak in function cfg80211_bss_update Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 035/104] RDMA/bnxt_re: Fix stats counters Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 036/104] platform/x86: amd-pmc: Fix command completion code Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 037/104] platform/x86: amd-pmc: Fix SMU firmware reporting mechanism Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 038/104] platform/x86: amd-pmc: Fix missing unlock on error in amd_pmc_send_cmd() Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 039/104] RDMA/rxe: Fix memory leak in error path code Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 040/104] netfilter: nf_tables: fix audit memory leak in nf_tables_commit Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 041/104] bpf: Fix OOB read when printing XDP link fdinfo Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 042/104] mac80211: fix enabling 4-address mode on a sta vif after assoc Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 043/104] netfilter: conntrack: adjust stop timestamp to real expiry value Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 044/104] netfilter: nft_nat: allow to specify layer 4 protocol NAT only Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 045/104] i40e: Fix logic of disabling queues Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 046/104] i40e: Fix firmware LLDP agent related warning Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 047/104] i40e: Fix queue-to-TC mapping on Tx Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 048/104] i40e: Fix log TC creation failure when max num of queues is exceeded Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 049/104] tipc: fix implicit-connect for SYN+ Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 050/104] tipc: fix sleeping in tipc accept routine Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 051/104] net: Set true network header for ECN decapsulation Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 052/104] net: dsa: mv88e6xxx: silently accept the deletion of VID 0 too Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 053/104] loop: reintroduce global lock for safe loop_validate_file() traversal Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 054/104] net: qrtr: fix memory leaks Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 055/104] ionic: make all rx_mode work threadsafe Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 056/104] ionic: catch no ptp support earlier Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 057/104] ionic: remove intr coalesce update from napi Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 058/104] ionic: fix up dim accounting for tx and rx Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 059/104] ionic: count csum_none when offload enabled Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 060/104] can: mcp251xfd: mcp251xfd_irq(): stop timestamping worker in case error in IRQ Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 061/104] tipc: do not write skb_shinfo frags when doing decrytion Greg Kroah-Hartman
2021-08-02 13:44 ` [PATCH 5.13 062/104] octeontx2-pf: Fix interface down flag on error Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 063/104] octeontx2-pf: Dont enable backpressure on LBK links Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 064/104] net: phy: broadcom: re-add check for PHY_BRCM_DIS_TXCRXC_NOENRGY on the BCM54811 PHY Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 065/104] mlx4: Fix missing error code in mlx4_load_one() Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 066/104] drm/panel: panel-simple: Fix proper bpc for ytc700tlag_05_201c Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 067/104] drm/i915/bios: Fix ports mask Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 068/104] KVM: x86: Check the right feature bit for MSR_KVM_ASYNC_PF_ACK access Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 069/104] net: llc: fix skb_over_panic Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 070/104] drm/msm/dpu: Fix sm8250_mdp register length Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 071/104] drm/msm/dp: use dp_ctrl_off_link_stream during PHY compliance test run Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 072/104] drm/msm/dp: Initialize the INTF_CONFIG register Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 073/104] KVM: selftests: Fix missing break in dirty_log_perf_test arg parsing Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 074/104] bpf, sockmap: Zap ingress queues after stopping strparser Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 075/104] net/mlx5: Fix flow table chaining Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 076/104] net/mlx5e: Disable Rx ntuple offload for uplink representor Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 077/104] net/mlx5: E-Switch, Set destination vport vhca id only when merged eswitch is supported Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 078/104] net/mlx5: E-Switch, handle devcom events only for ports on the same device Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 079/104] net/mlx5e: RX, Avoid possible data corruption when relaxed ordering and LRO combined Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 080/104] net/mlx5e: Add NETIF_F_HW_TC to hw_features when HTB offload is available Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 081/104] net/mlx5e: Fix page allocation failure for trap-RQ over SF Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 082/104] net/mlx5e: Fix page allocation failure for ptp-RQ " Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 083/104] net/mlx5: Unload device upon firmware fatal error Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 084/104] net/mlx5e: Fix nullptr in mlx5e_hairpin_get_mdev() Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 085/104] net/mlx5: Fix mlx5_vport_tbl_attr chain from u16 to u32 Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 086/104] block: delay freeing the gendisk Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 087/104] sctp: fix return value check in __sctp_rcv_asconf_lookup Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 088/104] tulip: windbond-840: Fix missing pci_disable_device() in probe and remove Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 089/104] sis900: " Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 090/104] can: hi311x: fix a signedness bug in hi3110_cmd() Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 091/104] bpf: Introduce BPF nospec instruction for mitigating Spectre v4 Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 092/104] bpf: Fix leakage due to insufficient speculative store bypass mitigation Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 093/104] 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.13 095/104] bpf: Fix pointer arithmetic mask tightening under state pruning Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 096/104] SMB3: fix readpage for large swap cache Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 097/104] powerpc/vdso: Dont use r30 to avoid breaking Go lang Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 098/104] powerpc/pseries: Fix regression while building external modules Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 099/104] Revert "perf map: Fix dso->nsinfo refcounting" Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 100/104] io_uring: fix race in unified task_work running Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 101/104] i40e: Add additional info to PHY type error Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 102/104] can: j1939: j1939_session_deactivate(): clarify lifetime of session object Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 103/104] perf pmu: Fix alias matching Greg Kroah-Hartman
2021-08-02 13:45 ` [PATCH 5.13 104/104] octeontx2-af: Remove unnecessary devm_kfree Greg Kroah-Hartman
2021-08-02 18:33 ` [PATCH 5.13 000/104] 5.13.8-rc1 review Fox Chen
2021-08-03  6:56 ` Naresh Kamboju
2021-08-03 19:16 ` Guenter Roeck
2021-08-03 19:37 ` Justin Forbes

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=20210802134347.102414407@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.13 094/104] 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).