From patchwork Sat Feb 15 11:03:52 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13976030 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f182.google.com (mail-pl1-f182.google.com [209.85.214.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 755FB567D for ; Sat, 15 Feb 2025 11:04:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617471; cv=none; b=fW9iRZaIOk8YVTgOp8Z7/Hfu+pNmXWiW3B6XAjeOunZgk1gmshDZk/YPFfPEZL3O7X1Dsl1D+LvCoCF+2/e5fn1VGEfXDoOULcBrsxxL/+slBlszyA/qn3Vjz8TVcpy6/sQQjen9iykMG5JhYYKZdOiMpQiUdlCsrCHrizwUibc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617471; c=relaxed/simple; bh=WkCPlxXztbh4fxcmSu4WiZv7V4WDMRd9RR5F8AEMpBo=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=TZH1oUpyRsb9MdppwgvjROIL/vD7+9fvoED5PXL7I+gk7qI7hi5PlZD7SM9QAKzUdEVKpJCqrtQY2o9enNiF9RsHRtmDSkOyq5nAtO+kBqLluy72O5dMrFTITkjdnC2slM7v816kfyKZuvhubEER/DMKf2pjFW1g+mzem7KlPf4= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=csuBRfTs; arc=none smtp.client-ip=209.85.214.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="csuBRfTs" Received: by mail-pl1-f182.google.com with SMTP id d9443c01a7336-220d601886fso37846315ad.1 for ; Sat, 15 Feb 2025 03:04:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1739617469; x=1740222269; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Al1gouzPQIoojWQkgz4Tm7UeYY8vUvaXcnuySNT5o1A=; b=csuBRfTspUuLLgBROT76Ysf//pWAZFIxR7LObJNDMgwFUopmYP5pPPa8H33gRIeNIL GvmC2SQlq+Z+B9Hsf/MXXP9uw/Yx5QZ2OGgJF0y4liC08i7w1IM6nEMcl7r+txaswTvs H7mDiAT0BUXPnk3UzkrWKzT1CtWBz5DnWWm6+bhHfJQqPvMeWD7wGc+FbZH1O3w0MpNI W9S8halvx1VH7nJeBGIiiILe8BdorH6k6HjKOa3LkmMEvsw6D+A/3b0KfFc259Tl0c3x tUU8EqOREbZTBUu99JQeV215f+CwLNLqrzXpZ0i9ba2YLD1Wols73J89Zl0dved0q6Sn HDBg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1739617469; x=1740222269; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Al1gouzPQIoojWQkgz4Tm7UeYY8vUvaXcnuySNT5o1A=; b=nCWm4JCmszu7MkU7yd2p6qino32X3qAisbp3qiv4nIT+ikqAEyCE9ixeywdVg8emkW 0w+kYjqUeVh6NkXikTDsbcvmFL99WoNPF+VEECQE5b8TyiWPVfxOIQWhk08/gmnt4K6/ vfhJ0KKmJ0g0p3KrKMDoTkT+nru+HrH91WcAoIHq9PbVy3fP+aA5vWEykNqGXI4fjb1A o6O5L4pHx5tJAJ9Ez5VrrQjPTuzDPID3y3vkVb95wxxwmAjp0HYOVM74u6GamoJgarPG D3+eSry32AmBbC+VHLGAzaidBPA8s+i6eelZ0lBYCaxCcCSQKOZaiy3Bm7YKLMS4r6qH 0xhw== X-Gm-Message-State: AOJu0Yx7mnWovTOAKq2TM/oL8A7IhAuFk/qEWWSWnWRJp1N/r5ktriTh 1r7H2L8J3RrmyB++A3gk6XyVUiVnFPXkyGTtmyaKnSz8wij8gx6S3RFniA== X-Gm-Gg: ASbGncsXCeAYWtMy83XjCyBEqcYqRc9rbrI+jp3a5m4s7KiKE9M2vFIoMKFci/BohdU 7pfRFxoe/40onuRg8Dqb6bXNWpcza/wVSKSkzPm1a/iz5NzPKs54J9GRWhn6kS7XkNsZPyC0R3M DdRBsXWRsvxIOaBzqazrdXg7q1cWdFD4/28D6IyETHlvj1ijtNfC/ayBxF/WvoM+pxtZXu5bIGO 0s7DnD15QEBFcEncvo72ioWqRnpeHLYWvk4IScGooVdQsy3NRW0DVMH1ga2aOIUiDIEXQ3MgRPu oJRIa38KQ6U= X-Google-Smtp-Source: AGHT+IG04Sd8tTP3fhqex/mq6o+SojIPDFiV4j4U3Ba2t9hOZs3ZZ99Rfsp55rv3NhRru4cESFs1Ug== X-Received: by 2002:a05:6a20:430b:b0:1e0:d87a:f67 with SMTP id adf61e73a8af0-1ee8cb5d455mr4903916637.13.1739617469407; Sat, 15 Feb 2025 03:04:29 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7326d58d4d0sm72435b3a.94.2025.02.15.03.04.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 15 Feb 2025 03:04:28 -0800 (PST) From: Eduard Zingerman To: bpf@vger.kernel.org, ast@kernel.org Cc: andrii@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev, kernel-team@fb.com, yonghong.song@linux.dev, tj@kernel.org, patsomaru@meta.com, Eduard Zingerman Subject: [PATCH bpf-next v1 01/10] bpf: copy_verifier_state() should copy 'loop_entry' field Date: Sat, 15 Feb 2025 03:03:52 -0800 Message-ID: <20250215110411.3236773-2-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250215110411.3236773-1-eddyz87@gmail.com> References: <20250215110411.3236773-1-eddyz87@gmail.com> 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 The bpf_verifier_state.loop_entry state should be copied by copy_verifier_state(). Otherwise, .loop_entry values from unrelated states would poison env->cur_state. Additionally, env->stack should not contain any states with .loop_entry != NULL. The states in env->stack are yet to be verified, while .loop_entry is set for states that reached an equivalent state. This means that env->cur_state->loop_entry should always be NULL after pop_stack(). See the selftest in the next commit for an example of the program that is not safe yet is accepted by verifier w/o this fix. This change has some verification performance impact for selftests: File Program Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF) ---------------------------------- ---------------------------- --------- --------- -------------- ---------- ---------- ------------- arena_htab.bpf.o arena_htab_llvm 717 426 -291 (-40.59%) 57 37 -20 (-35.09%) arena_htab_asm.bpf.o arena_htab_asm 597 445 -152 (-25.46%) 47 37 -10 (-21.28%) arena_list.bpf.o arena_list_del 309 279 -30 (-9.71%) 23 14 -9 (-39.13%) iters.bpf.o iter_subprog_check_stacksafe 155 141 -14 (-9.03%) 15 14 -1 (-6.67%) iters.bpf.o iter_subprog_iters 1094 1003 -91 (-8.32%) 88 83 -5 (-5.68%) iters.bpf.o loop_state_deps2 479 725 +246 (+51.36%) 46 63 +17 (+36.96%) kmem_cache_iter.bpf.o open_coded_iter 63 59 -4 (-6.35%) 7 6 -1 (-14.29%) verifier_bits_iter.bpf.o max_words 92 84 -8 (-8.70%) 8 7 -1 (-12.50%) verifier_iterating_callbacks.bpf.o cond_break2 113 107 -6 (-5.31%) 12 12 +0 (+0.00%) And significant negative impact for sched_ext: File Program Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF) ----------------- ---------------------- --------- --------- -------------------- ---------- ---------- ------------------ bpf.bpf.o lavd_init 7039 14723 +7684 (+109.16%) 490 1139 +649 (+132.45%) bpf.bpf.o layered_dispatch 11485 10548 -937 (-8.16%) 848 762 -86 (-10.14%) bpf.bpf.o layered_dump 7422 1000001 +992579 (+13373.47%) 681 31178 +30497 (+4478.27%) bpf.bpf.o layered_enqueue 16854 71127 +54273 (+322.02%) 1611 6450 +4839 (+300.37%) bpf.bpf.o p2dq_dispatch 665 791 +126 (+18.95%) 68 78 +10 (+14.71%) bpf.bpf.o p2dq_init 2343 2980 +637 (+27.19%) 201 237 +36 (+17.91%) bpf.bpf.o refresh_layer_cpumasks 16487 674760 +658273 (+3992.68%) 1770 65370 +63600 (+3593.22%) bpf.bpf.o rusty_select_cpu 1937 40872 +38935 (+2010.07%) 177 3210 +3033 (+1713.56%) scx_central.bpf.o central_dispatch 636 2687 +2051 (+322.48%) 63 227 +164 (+260.32%) scx_nest.bpf.o nest_init 636 815 +179 (+28.14%) 60 73 +13 (+21.67%) scx_qmap.bpf.o qmap_dispatch 2393 3580 +1187 (+49.60%) 196 253 +57 (+29.08%) scx_qmap.bpf.o qmap_dump 233 318 +85 (+36.48%) 22 30 +8 (+36.36%) scx_qmap.bpf.o qmap_init 16367 17436 +1069 (+6.53%) 603 669 +66 (+10.95%) Note 'layered_dump' program, which now hits 1M instructions limit. This impact would be mitigated in the next patch. Signed-off-by: Eduard Zingerman --- kernel/bpf/verifier.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 04d1d75d9ff9..01b31b718f4f 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1659,6 +1659,7 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state, dst_state->callback_unroll_depth = src->callback_unroll_depth; dst_state->used_as_loop_entry = src->used_as_loop_entry; dst_state->may_goto_depth = src->may_goto_depth; + dst_state->loop_entry = src->loop_entry; for (i = 0; i <= src->curframe; i++) { dst = dst_state->frame[i]; if (!dst) { @@ -19243,6 +19244,8 @@ static int do_check(struct bpf_verifier_env *env) return err; break; } else { + if (WARN_ON_ONCE(env->cur_state->loop_entry)) + env->cur_state->loop_entry = NULL; do_print_state = true; continue; } From patchwork Sat Feb 15 11:03:53 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13976031 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f174.google.com (mail-pl1-f174.google.com [209.85.214.174]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9BE2E1A2388 for ; Sat, 15 Feb 2025 11:04:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.174 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617473; cv=none; b=h5P85IxLnAAI9kyyxjLbW94uJN3j6PM1mhlDFMLkQ/6Nug62cXNV61eFQILF06AwAwOgk11l3eX3t4LNFdlSCD0rE7tYBQ8hnxpgJZhfOCDqGq1jFxxf7oYITcFkPUq9z3GZFAnaPHkTUt063z32tS1sqMzD21Ctr3+CtXiZ4qI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617473; c=relaxed/simple; bh=wGgISqWd8P9mdDG2yI3hvKfXyLCQ3oDwMXj4bjXEjIQ=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=OTbw1ikEecJhf1TAobXztWWCqVOeB3D9fICT2A2HC7yLCXlmDs7E3Wx9RWI6HwMkCyyjkymAMEEAApm1T1rUzY2LaKSZNg+UhkZw8m3JvlJGCW5Dwy4/eV27QMb++/zdUZOUJw2PUpeh/Txuh8TNh03BdmiA0xzticjScgOyqhs= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=Pk90MTKB; arc=none smtp.client-ip=209.85.214.174 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Pk90MTKB" Received: by mail-pl1-f174.google.com with SMTP id d9443c01a7336-220ecbdb4c2so45342425ad.3 for ; Sat, 15 Feb 2025 03:04:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1739617470; x=1740222270; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=+GOCH4mEvoqZ0DCMEaS+DNrb1EkjOaHoe0Dctn/XG64=; b=Pk90MTKBkWNZcSNHOY1EpM6CUkTi9nUpi4+rM7FxHMlehCL9xswAOPiXa3NhijQW81 06xn5kSXd7DAkV1GMVkSKvADfvO+AejusC/XXGzu/9VkarcHarP5MSQ0Z87/zMHO17+s YeVzWfkRdLjJT75Ve5ItBEeiB2oG4Zawq2b5G60w8UE5Uz+F8qI7YPbqRtZ6mV2+qANg Vw1A180d06fDdEb0Tjh79MRP29vp5bXBpR9U4RIDS5+/wdvXddcFb5/BCbRoSsGPrVpd DcKwH2OZmDrtlYdQj2ynt7qbZqrj/+SHyKAo7ElIILTsglGe32LQr6sih0YJGsqBkStW 76tQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1739617470; x=1740222270; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=+GOCH4mEvoqZ0DCMEaS+DNrb1EkjOaHoe0Dctn/XG64=; b=TeBTL3dhWPafwp8t1rQ1LidglVkmT6nldPs5V4M3pKLKhAldKN0j7WGrJy7kIppkjl 7JquyzPLSQ4V1LqlEuxH4cwcDXQQLtEXrbGYNpFQl7b3sj5r1jYYA6ajk6f79BhO8gwA hDmGStCVcPwnaVgvHKtrLZRsxpDHXTkpIeMBK+63N2bEp5OCnlkTeQx+MZ6jKvIEWprO X+r662DN858T7E2nPia1+LeKwsM2QIRvFyw9VFkpkNFn+SQpOWpSQsORSfWnoZxbYht/ LT+nf/vyAEVs0rBCr5N1tawwqDHXLmynhNP9zRy+EYEvNqAzq3JlMwUf5jopBPlPyuNP inYw== X-Gm-Message-State: AOJu0YxWowWUDAnf0ktK0lxZjAZcIxA9kY8OHwgRZZsbfkU+ofHV8iL8 TWu6A/ElRolMF38EegBt2pW6o5CZqRQMZySU2VUHsKXNuSpdFY3D9/cnVw== X-Gm-Gg: ASbGncvhWiHlDSNzkDsYEPOjHA1L+Joo2C72EGPFTH8M7M8/QnFo3hX3ckSgN3C5viN QbVliuwdlqLVtdBGdxO1KxAuMFcImiexh6cjo8rYB9hryX6Zm0Px3R0Rz3jbBm1B1m1gJMV6b+p 2d+QN3cuS1dsYc6JOAnhP4Jiq632o//CUMGgnXlOWEO11osPZR17tbpKH5XTgbr+QFXH9Oxv1yt a9NVQ6rX5LB9nvPAXTOvugFxTgdcqpkGQIoPCZbExsIJ7mOJai38jGdtwdO87VnRaAAS8rIRGkB Hq6+wbAqkgw= X-Google-Smtp-Source: AGHT+IGKADK8Dy6y0EMN7F0y6nPNzFx33FOvHf1madq5xIKdxOgXpLB5fMvn8I57zpGzIhvI+3qI6w== X-Received: by 2002:a05:6a20:a125:b0:1db:dfc0:d342 with SMTP id adf61e73a8af0-1ee8cb0e82cmr5938379637.7.1739617470482; Sat, 15 Feb 2025 03:04:30 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7326d58d4d0sm72435b3a.94.2025.02.15.03.04.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 15 Feb 2025 03:04:29 -0800 (PST) From: Eduard Zingerman To: bpf@vger.kernel.org, ast@kernel.org Cc: andrii@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev, kernel-team@fb.com, yonghong.song@linux.dev, tj@kernel.org, patsomaru@meta.com, Eduard Zingerman Subject: [PATCH bpf-next v1 02/10] selftests/bpf: test correct loop_entry update in copy_verifier_state Date: Sat, 15 Feb 2025 03:03:53 -0800 Message-ID: <20250215110411.3236773-3-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250215110411.3236773-1-eddyz87@gmail.com> References: <20250215110411.3236773-1-eddyz87@gmail.com> 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 A somewhat cumbersome test case sensitive to correct copying of bpf_verifier_state->loop_entry fields in verifier.c:copy_verifier_state(). W/o the fix from a previous commit the program is accepted as safe. 1: /* poison block */ 2: if (random() != 24) { // assume false branch is placed first 3: i = iter_new(); 4: while (iter_next(i)); 5: iter_destroy(i); 6: return; 7: } 8: 9: /* dfs_depth block */ 10: for (i = 10; i > 0; i--); 11: 12: /* main block */ 13: i = iter_new(); // fp[-16] 14: b = -24; // r8 15: for (;;) { 16: if (iter_next(i)) 17: break; 18: if (random() == 77) { // assume false branch is placed first 19: *(u64 *)(r10 + b) = 7; // this is not safe when b == -25 20: iter_destroy(i); 21: return; 22: } 23: if (random() == 42) { // assume false branch is placed first 24: b = -25; 25: } 26: } 27: iter_destroy(i); The goal of this example is to: (a) poison env->cur_state->loop_entry with a state S, such that S->branches == 0; (b) set state S as a loop_entry for all checkpoints in /* main block */, thus forcing NOT_EXACT states comparisons; (c) exploit incorrect loop_entry set for checkpoint at line 18 by first creating a checkpoint with b == -24 and then pruning the state with b == -25 using that checkpoint. The /* poison block */ is responsible for goal (a). It forces verifier to first validate some unrelated iterator based loop, which leads to an update_loop_entry() call in is_state_visited(), which places checkpoint created at line 4 as env->cur_state->loop_entry. Starting from line 8, the branch count for that checkpoint is 0. The /* dfs_depth block */ is responsible for goal (b). It abuses the fact that update_loop_entry(cur, hdr) only updates cur->loop_entry when hdr->dfs_depth <= cur->dfs_depth. After line 12 every state has dfs_depth bigger then dfs_depth of poisoned env->cur_state->loop_entry. Thus the above condition is never true for lines 12-27. The /* main block */ is responsible for goal (c). Verification proceeds as follows: - checkpoint {b=-24,i=active} created at line 16; - jump 18->23 is verified first, jump to 19 pushed to stack; - jump 23->26 is verified first, jump to 24 pushed to stack; - checkpoint {b=-24,i=active} created at line 15; - current state is pruned by checkpoint created at line 16, this sets branches count for checkpoint at line 15 to 0; - jump to 24 is popped from stack; - line 16 is reached in state {b=-25,i=active}; - this is pruned by a previous checkpoint {b=-24,i=active}: - checkpoint's loop_entry is poisoned and has branch count of 0, hence states are compared using NOT_EXACT rules; - b is not marked precise yet. Signed-off-by: Eduard Zingerman --- tools/testing/selftests/bpf/progs/iters.c | 116 ++++++++++++++++++++++ 1 file changed, 116 insertions(+) diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c index 190822b2f08b..007831dc8c46 100644 --- a/tools/testing/selftests/bpf/progs/iters.c +++ b/tools/testing/selftests/bpf/progs/iters.c @@ -1174,6 +1174,122 @@ __naked int loop_state_deps2(void) ); } +SEC("?raw_tp") +__failure +__msg("math between fp pointer and register with unbounded") +__flag(BPF_F_TEST_STATE_FREQ) +__naked int loop_state_deps3(void) +{ + /* This is equivalent to a C program below. + * + * if (random() != 24) { // assume false branch is placed first + * i = iter_new(); // fp[-8] + * while (iter_next(i)); + * iter_destroy(i); + * return; + * } + * + * for (i = 10; i > 0; i--); // increase dfs_depth for child states + * + * i = iter_new(); // fp[-8] + * b = -24; // r8 + * for (;;) { // checkpoint (L) + * if (iter_next(i)) // checkpoint (N) + * break; + * if (random() == 77) { // assume false branch is placed first + * *(u64 *)(r10 + b) = 7; // this is not safe when b == -25 + * iter_destroy(i); + * return; + * } + * if (random() == 42) { // assume false branch is placed first + * b = -25; + * } + * } + * iter_destroy(i); + * + * In case of a buggy verifier first loop might poison + * env->cur_state->loop_entry with a state having 0 branches + * and small dfs_depth. This would trigger NOT_EXACT states + * comparison for some states within second loop. + * Specifically, checkpoint (L) might be problematic if: + * - branch with '*(u64 *)(r10 + b) = 7' is not explored yet; + * - checkpoint (L) is first reached in state {b=-24}; + * - traversal is pruned at checkpoint (N) setting checkpoint's (L) + * branch count to 0, thus making it eligible for use in pruning; + * - checkpoint (L) is next reached in state {b=-25}, + * this would cause NOT_EXACT comparison with a state {b=-24} + * while 'b' is not marked precise yet. + */ + asm volatile ( + "call %[bpf_get_prandom_u32];" + "if r0 == 24 goto 2f;" + "r1 = r10;" + "r1 += -8;" + "r2 = 0;" + "r3 = 5;" + "call %[bpf_iter_num_new];" + "1:" + "r1 = r10;" + "r1 += -8;" + "call %[bpf_iter_num_next];" + "if r0 != 0 goto 1b;" + "r1 = r10;" + "r1 += -8;" + "call %[bpf_iter_num_destroy];" + "r0 = 0;" + "exit;" + "2:" + /* loop to increase dfs_depth */ + "r0 = 10;" + "3:" + "r0 -= 1;" + "if r0 != 0 goto 3b;" + /* end of loop */ + "r1 = r10;" + "r1 += -8;" + "r2 = 0;" + "r3 = 10;" + "call %[bpf_iter_num_new];" + "r8 = -24;" + "main_loop_%=:" + "r1 = r10;" + "r1 += -8;" + "call %[bpf_iter_num_next];" + "if r0 == 0 goto main_loop_end_%=;" + /* first if */ + "call %[bpf_get_prandom_u32];" + "if r0 == 77 goto unsafe_write_%=;" + /* second if */ + "call %[bpf_get_prandom_u32];" + "if r0 == 42 goto poison_r8_%=;" + /* iterate */ + "goto main_loop_%=;" + "main_loop_end_%=:" + "r1 = r10;" + "r1 += -8;" + "call %[bpf_iter_num_destroy];" + "r0 = 0;" + "exit;" + + "unsafe_write_%=:" + "r0 = r10;" + "r0 += r8;" + "r1 = 7;" + "*(u64 *)(r0 + 0) = r1;" + "goto main_loop_end_%=;" + + "poison_r8_%=:" + "r8 = -25;" + "goto main_loop_%=;" + : + : __imm(bpf_get_prandom_u32), + __imm(bpf_iter_num_new), + __imm(bpf_iter_num_next), + __imm(bpf_iter_num_destroy) + : __clobber_all + ); +} + SEC("?raw_tp") __success __naked int triple_continue(void) From patchwork Sat Feb 15 11:03:54 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13976032 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f181.google.com (mail-pl1-f181.google.com [209.85.214.181]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id BE80A567D for ; Sat, 15 Feb 2025 11:04:32 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617474; cv=none; b=VCcVPRjABOJHgyKTNXFCV+5/Jp1Z9638JfqEhswtej38crzRrJE06Cudu/b90qqIcsz3cxD6ZpaFZVDdFIUei/FmVjnmjeBHCRkS5NJvgIvPX4wBHWYDE+f9QDAMSm87XGW+riJ1r004KzBSR0ExrXuBYnh/nau/CUtzZ9GLnXw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617474; c=relaxed/simple; bh=3tF1Xq37jo54OXD9rvanfjQVKZSCBCxDR1nXCrusP28=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=WPTCP0zI0uq4lQfvgwUP1zXLYIzOowxMuXRtfUemiXq6n3lE+Tq8KdS6NJEk6TBja2pLezSRQADZeNyLAQGy5tuzWPUGPpzh7wwKCBJ3BwuP5fij5SL6dtL98ymy7kZYsI9oyXePNxnth4q13MFQlVcla6TakG8CDUD4rDKBeQc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=SRseqG09; arc=none smtp.client-ip=209.85.214.181 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="SRseqG09" Received: by mail-pl1-f181.google.com with SMTP id d9443c01a7336-220c8cf98bbso57950955ad.1 for ; Sat, 15 Feb 2025 03:04:32 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1739617472; x=1740222272; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=uDb/gdeQU/PSQ/UUil4dmXW1Hd6+EUYI3l5WuidH/TU=; b=SRseqG09ekVMaJIn4//REmZXdeQSTHKqpNmqU7bfHG2AZ+zN6Fg1o67klKXG91f0wR 2NAWmJbZFB9L6Ey5+txnD5mgI5lyoSofYQQsoFAkbyaSwq8spCFY7zdjgWLyMDCHykX4 kavoUugoPI375LLRy6YOcQU5CnYjVe1CAbiU3IxZpN4FTJnPpvKAlbKBYmL9o/4smzTk hEDCD3UCV8F7cKuF8SRK2Q4GB92GP2iL3CLvfJs/2AxqoRp2hi5ReEUZfPKZgMp9BfyF aQ4aeplrCYBHhNsF9FjIE+QRMcuXuYiS/EdKdtcworaOV7gupDHR5HaWXkUYCCeGDyVT mnVA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1739617472; x=1740222272; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=uDb/gdeQU/PSQ/UUil4dmXW1Hd6+EUYI3l5WuidH/TU=; b=ltnh2jiek7coPJB5CjrsWwGO+lBwJuwDhsQLwpNew0MzmtotK2saoQWhRhtzv2zIMt tx+o2wul9/kYvR5v0l5MwMiibBorR2IX3gWSDXFg/3lZLopLYg07VaL5470XcfSflcqj CAzRdp6nwJ6FGxL8kYHcDpxHw8fgWWIVgBZpR/SPHRd/2z4AAyfXp0ZIDJnsYs/KEuir 5pgb4PKnX50WL7UMiVjLe9Ped/mfgm+ysMZacWci5uslfxzobKSTM8No5kvKnHdhRHVr bbkKmd0pz8ri+rDZd5xRXiJPcVdxL0wPpemTHLoh719CK3umxajPRvc+LFU9X0zH6WLr KhBQ== X-Gm-Message-State: AOJu0YyI3TWF7uFtxu1fDZFve+zUUHCwVs9OKuca3cuhnoTmCQ5H8Z1R y61mtLoGusGKukSqrMkAZ+ZHLjv7kPf6vt2YfE+fkmIyhgc+ay/a6IVgiQ== X-Gm-Gg: ASbGncsy/K9QsfH3KEtdv6HzQCA/auNZEf+wPZgPAC2CVUZBoVsNMCcfBfVp2mmMyZl mLrLwob+wJTQ63x/u2Id6Pyx9aqOEdN16RHhytTxqjINCtXwbGOYPzojkSNwMlUj0LzhqS/W6pO qEDqULEbJL8YpjncMD2xAqsJdZ1IZ+ql9avih/hCYxyQGE66kKkOEt0xCWB0YDdQGPGvYos03kX Ul4IpE/Sv2MWYaBRF8VXIJRHZ73YqCxZ5AkE//09oSIHFwgnqrP/RyEHGnWZ3VNBlzHO2xL/1cw f8SPBc7OIok= X-Google-Smtp-Source: AGHT+IFSlaD0AncONg+3xUUfqvzoMkINFPuEdpgyn0zfVa2FRV5BktRnHMmRq20kQ7yBhe6mdTimcA== X-Received: by 2002:a05:6a20:3948:b0:1ee:64c4:89b9 with SMTP id adf61e73a8af0-1ee8cbe8197mr4010369637.33.1739617471655; Sat, 15 Feb 2025 03:04:31 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7326d58d4d0sm72435b3a.94.2025.02.15.03.04.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 15 Feb 2025 03:04:30 -0800 (PST) From: Eduard Zingerman To: bpf@vger.kernel.org, ast@kernel.org Cc: andrii@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev, kernel-team@fb.com, yonghong.song@linux.dev, tj@kernel.org, patsomaru@meta.com, Eduard Zingerman Subject: [PATCH bpf-next v1 03/10] bpf: don't do clean_live_states when state->loop_entry->branches > 0 Date: Sat, 15 Feb 2025 03:03:54 -0800 Message-ID: <20250215110411.3236773-4-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250215110411.3236773-1-eddyz87@gmail.com> References: <20250215110411.3236773-1-eddyz87@gmail.com> 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 verifier.c:is_state_visited() uses RANGE_WITHIN states comparison rules for cached states that have loop_entry with non-zero branches count (meaning that loop_entry's verification is not yet done). The RANGE_WITHIN rules in regsafe()/stacksafe() require register and stack objects types to be identical in current and old states. verifier.c:clean_live_states() replaces registers and stack spills with NOT_INIT/STACK_INVALID marks, if these registers/stack spills are not read in any child state. This means that clean_live_states() works against loop convergence logic under some conditions. See selftest in the next patch for a specific example. Mitigate this by prohibiting clean_verifier_state() when state->loop_entry->branches > 0. This undoes negative verification performance impact of the copy_verifier_state() fix from the previous patch. Below is comparison between master and current patch. selftests: File Program Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF) ---------------------------------- ---------------------------- --------- --------- --------------- ---------- ---------- -------------- arena_htab.bpf.o arena_htab_llvm 717 423 -294 (-41.00%) 57 37 -20 (-35.09%) arena_htab_asm.bpf.o arena_htab_asm 597 445 -152 (-25.46%) 47 37 -10 (-21.28%) arena_list.bpf.o arena_list_add 1493 1822 +329 (+22.04%) 30 37 +7 (+23.33%) arena_list.bpf.o arena_list_del 309 261 -48 (-15.53%) 23 15 -8 (-34.78%) iters.bpf.o checkpoint_states_deletion 18125 22154 +4029 (+22.23%) 818 918 +100 (+12.22%) iters.bpf.o iter_nested_deeply_iters 593 367 -226 (-38.11%) 67 43 -24 (-35.82%) iters.bpf.o iter_nested_iters 813 772 -41 (-5.04%) 79 72 -7 (-8.86%) iters.bpf.o iter_subprog_check_stacksafe 155 135 -20 (-12.90%) 15 14 -1 (-6.67%) iters.bpf.o iter_subprog_iters 1094 808 -286 (-26.14%) 88 68 -20 (-22.73%) iters.bpf.o loop_state_deps2 479 356 -123 (-25.68%) 46 35 -11 (-23.91%) iters.bpf.o triple_continue 35 31 -4 (-11.43%) 3 3 +0 (+0.00%) kmem_cache_iter.bpf.o open_coded_iter 63 59 -4 (-6.35%) 7 6 -1 (-14.29%) mptcp_subflow.bpf.o _getsockopt_subflow 501 446 -55 (-10.98%) 25 23 -2 (-8.00%) pyperf600_iter.bpf.o on_event 12339 6379 -5960 (-48.30%) 441 286 -155 (-35.15%) verifier_bits_iter.bpf.o max_words 92 84 -8 (-8.70%) 8 7 -1 (-12.50%) verifier_iterating_callbacks.bpf.o cond_break2 113 192 +79 (+69.91%) 12 21 +9 (+75.00%) sched_ext: File Program Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF) ----------------- ---------------------- --------- --------- ----------------- ---------- ---------- ---------------- bpf.bpf.o layered_dispatch 11485 9039 -2446 (-21.30%) 848 662 -186 (-21.93%) bpf.bpf.o layered_dump 7422 5022 -2400 (-32.34%) 681 298 -383 (-56.24%) bpf.bpf.o layered_enqueue 16854 13753 -3101 (-18.40%) 1611 1308 -303 (-18.81%) bpf.bpf.o layered_init 1000001 5549 -994452 (-99.45%) 84672 523 -84149 (-99.38%) bpf.bpf.o layered_runnable 3149 1899 -1250 (-39.70%) 288 151 -137 (-47.57%) bpf.bpf.o p2dq_init 2343 1936 -407 (-17.37%) 201 170 -31 (-15.42%) bpf.bpf.o refresh_layer_cpumasks 16487 1285 -15202 (-92.21%) 1770 120 -1650 (-93.22%) bpf.bpf.o rusty_select_cpu 1937 1386 -551 (-28.45%) 177 125 -52 (-29.38%) scx_central.bpf.o central_dispatch 636 600 -36 (-5.66%) 63 59 -4 (-6.35%) scx_central.bpf.o central_init 913 632 -281 (-30.78%) 48 39 -9 (-18.75%) scx_nest.bpf.o nest_init 636 601 -35 (-5.50%) 60 58 -2 (-3.33%) scx_pair.bpf.o pair_dispatch 1000001 1914 -998087 (-99.81%) 58169 142 -58027 (-99.76%) scx_qmap.bpf.o qmap_dispatch 2393 2187 -206 (-8.61%) 196 174 -22 (-11.22%) scx_qmap.bpf.o qmap_init 16367 22777 +6410 (+39.16%) 603 768 +165 (+27.36%) 'layered_init' and 'pair_dispatch' hit 1M on master, but are verified ok with this patch. Signed-off-by: Eduard Zingerman --- kernel/bpf/verifier.c | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 01b31b718f4f..945a13b2cfeb 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -17814,12 +17814,16 @@ static void clean_verifier_state(struct bpf_verifier_env *env, static void clean_live_states(struct bpf_verifier_env *env, int insn, struct bpf_verifier_state *cur) { + struct bpf_verifier_state *loop_entry; struct bpf_verifier_state_list *sl; sl = *explored_state(env, insn); while (sl) { if (sl->state.branches) goto next; + loop_entry = get_loop_entry(&sl->state); + if (loop_entry && loop_entry->branches) + goto next; if (sl->state.insn_idx != insn || !same_callsites(&sl->state, cur)) goto next; From patchwork Sat Feb 15 11:03:55 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13976033 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f182.google.com (mail-pl1-f182.google.com [209.85.214.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C5ADC1A7044 for ; Sat, 15 Feb 2025 11:04:33 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617475; cv=none; b=IvqzJm7xGwLAT1mA1arUQPonkpF0/yDvysrgvgzKu/NSXxfCScmN12WtkabVEXqt2aacp0BHtU0oSooxRKO2lnqv+RJ81For0b0VBSrn68i3GEUojSvQrpeusyeCQ7myX+UTpoZMmz+pOHzatv64BIfiUggfvEL443hC6hP+AHU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617475; c=relaxed/simple; bh=E7j3SOAv9uvgPzCiplw3O27KVBB/BmeGa6ttCeKsplA=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=UESCpfjl2LnmDd4YFc6LPGVZyP/BCODEvY9M811tN1mUK7GI7WL5g1bSd0kVBWJCtxQCR8EKOqKTJZGoxdVPY3Ek3NRbPnJ5WX2NCbl8HYFYdMB19tWm3AeZfeTnQZwkvQZJO4DzaTXPpdCcco8o7C1hYzGD+0eknqj3x+b9bb4= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=hQMhKPsl; arc=none smtp.client-ip=209.85.214.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="hQMhKPsl" Received: by mail-pl1-f182.google.com with SMTP id d9443c01a7336-221050f3f00so8519105ad.2 for ; Sat, 15 Feb 2025 03:04:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1739617473; x=1740222273; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=F77Gcm2L7f+gFRYtZxeBSlP72OFg0lY7wRA0PQsfy1w=; b=hQMhKPsl6Wr+zK3oeggAXc+hJ0tgeeEWb1507Ywxh6ydGPxaTXyKGR9Z+Tn2m07n8w XES7j86dGH9w6h+YJYFblp7H1UCKj/oeqIlZt/IODrwVluEcJCZ5BRrySm2iYP5Q3GOc 3iX3RGW3pJBq0krP3W4xOvFeOrt6ybXORUqickudEeS1HZqm9nRslV1ptEf71/XtFnGp LNJpDHCMOsZw5OP5jHuBwjz8ySk85DYk5n33czLJZbnZAyTTB4m6QaOywgrJL9aR+aYe DuS3ANKhHjU3IXiRXiwCTlf+Izux1Z8URtUrNxwYOtT2x7TqGTWKsubhjBj/XinFQFEP yQYA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1739617473; x=1740222273; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=F77Gcm2L7f+gFRYtZxeBSlP72OFg0lY7wRA0PQsfy1w=; b=WAVkEXo8vfkYn8xFUbN19tlVzcI+FKcdL1Slhtw1secltnChtbDYe2rnU1y4HC8aXH pyF12VPgldY8hdWjqEXQwjpCTbMUSZNISICd1rU9bDeP8BtH9kHP5B6Ti9JgukBGsF/O BHWNn0CtJFmF0LU0/jG3zWQ2HjamLhogXWvAmUK2dLDiBHkpOMCHRj2/F7rgoyfnJBfe dS88H2MJY6Fr8afjNt81+OdA7m+6G9l5ibma4jlTFqNFNC3QIvT5ESgcxZDf5affqYfM DINU8cuzgYQ8b77FVYEULzCtRAlyPenCac3H9LiTqXFwbIUQc6O/oR6T4G6sv/8uD6kf mWJg== X-Gm-Message-State: AOJu0YxHwOgaaMkqydQ6J3kCu5lti7/Z5vLGyKcH9UQrKCCpsRZVTYZU O7kvDGQy9rSHhJX3dLbKAKaQdlHCNXmxvXgLAeL+S5fGhpYqHKv15BX47w== X-Gm-Gg: ASbGncsG0iSikPi3L2PCSs1JvpN/ydhlwDioYncyuptA7/mPKCRlcpQPXUcMLfhJofM xeTFsclSW/ga4Pt9pb828TOf47fLxrirr/wDQzfmvTmQG3J22h7xXPMO4ZSrC31qE9CRgidGyKp sJXABHnkYiHmR8+5PQERSjj8/DaKkE2rj3rDS+y9VtOdgKWxwpxgGOGbqKKCuGc8udfulZQYalj jlgHYVJyDIcAAKCqVbxR4R4sj1fYBGW/r1Lz9ilB9Qt+P2X3IP/H+P/y3cFf1ttbCxRO/kQ1P4k iwbvPgc2j4s= X-Google-Smtp-Source: AGHT+IF80Nyjt7jz8cLtIibs2kYG22h214fi8iXqZEYSBJg1DTvldSwhaBmfzq9vge5jtIkvqNVASw== X-Received: by 2002:a05:6a00:198c:b0:732:2484:e0ce with SMTP id d2e1a72fcca58-732618c1cf1mr4111530b3a.17.1739617472768; Sat, 15 Feb 2025 03:04:32 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7326d58d4d0sm72435b3a.94.2025.02.15.03.04.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 15 Feb 2025 03:04:32 -0800 (PST) From: Eduard Zingerman To: bpf@vger.kernel.org, ast@kernel.org Cc: andrii@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev, kernel-team@fb.com, yonghong.song@linux.dev, tj@kernel.org, patsomaru@meta.com, Eduard Zingerman Subject: [PATCH bpf-next v1 04/10] selftests/bpf: check states pruning for deeply nested iterator Date: Sat, 15 Feb 2025 03:03:55 -0800 Message-ID: <20250215110411.3236773-5-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250215110411.3236773-1-eddyz87@gmail.com> References: <20250215110411.3236773-1-eddyz87@gmail.com> 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 A test case with ridiculously deep bpf_for() nesting and a conditional update of a stack location. Consider the innermost loop structure: 1: bpf_for(o, 0, 10) 2: if (unlikely(bpf_get_prandom_u32())) 3: buf[0] = 42; 4: Assuming that verifier.c:clean_live_states() operates w/o change from the previous patch (e.g. as on current master) verification would proceed as follows: - at (1) state {buf[0]=?,o=drained}: - checkpoint - push visit to (2) for later - at (4) {buf[0]=?,o=drained} - pop (2) {buf[0]=?,o=active}, push visit to (3) for later - at (1) {buf[0]=?,o=active} - checkpoint - push visit to (2) for later - at (4) {buf[0]=?,o=drained} - pop (2) {buf[0]=?,o=active}, push visit to (3) for later - at (1) {buf[0]=?,o=active}: - checkpoint reached, checkpoint's branch count becomes 0 - checkpoint is processed by clean_live_states() and becomes {o=active} - pop (3) {buf[0]=42,o=active} - at (1), {buf[0]=42,o=active} - checkpoint - push visit to (2) for later - at (4) {buf[0]=42,o=drained} - pop (2) {buf[0]=42,o=active}, push visit to (3) for later - at (1) {buf[0]=42,o=active}, checkpoint reached - pop (3) {buf[0]=42,o=active} - at (1) {buf[0]=42,o=active}: - checkpoint reached, checkpoint's branch count becomes 0 - checkpoint is processed by clean_live_states() and becomes {o=active} - ... Note how clean_live_states() converted the checkpoint {buf[0]=42,o=active} to {o=active} and it can no longer be matched against {buf[0]=,o=active}, because iterator based states are compared using stacksafe(... RANGE_WITHIN), that requires stack slots to have same types. At the same time there are still states {buf[0]=42,o=active} pushed to DFS stack. This behaviour becomes exacerbated with multiple nesting levels, here are veristat results: - nesting level 1: 69 insns - nesting level 2: 258 insns - nesting level 3: 900 insns - nesting level 4: 4754 insns - nesting level 5: 35944 insns - nesting level 6: 312558 insns - nesting level 7: 1M limit Signed-off-by: Eduard Zingerman --- tools/testing/selftests/bpf/progs/iters.c | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c index 007831dc8c46..427b72954b87 100644 --- a/tools/testing/selftests/bpf/progs/iters.c +++ b/tools/testing/selftests/bpf/progs/iters.c @@ -7,6 +7,8 @@ #include "bpf_misc.h" #include "bpf_compiler.h" +#define unlikely(x) __builtin_expect(!!(x), 0) + static volatile int zero = 0; int my_pid; @@ -1628,4 +1630,25 @@ int iter_destroy_bad_arg(const void *ctx) return 0; } +SEC("raw_tp") +__success +int clean_live_states(const void *ctx) +{ + char buf[1]; + int i, j, k, l, m, n, o; + + bpf_for(i, 0, 10) + bpf_for(j, 0, 10) + bpf_for(k, 0, 10) + bpf_for(l, 0, 10) + bpf_for(m, 0, 10) + bpf_for(n, 0, 10) + bpf_for(o, 0, 10) { + if (unlikely(bpf_get_prandom_u32())) + buf[0] = 42; + bpf_printk("%s", buf); + } + return 0; +} + char _license[] SEC("license") = "GPL"; From patchwork Sat Feb 15 11:03:56 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13976034 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f170.google.com (mail-pl1-f170.google.com [209.85.214.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D8DDF1A841A for ; Sat, 15 Feb 2025 11:04:34 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617476; cv=none; b=GJ6VvaMlg5x7z3bOzlrnCTbeNFrQ64685O1iloeBpUY5XlDzc3RoElNdj+HcpVh5DkPEUj/RWbJruMJXp78udYiBZPxQavCI4BGqXThZSaT/bEonkBWo50sYzcI80U/XYLvPPaQFk9doFDkJUDZ+hbhEfkZ+zFt+L5qtHFdGqU8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617476; c=relaxed/simple; bh=i+7JT73zOvHWrIOe7tS5snCvt4cQ5nFjNPFm4hDEZfk=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=dLRRNDFa27RuXwwhkyB2bMIc3ZlmOIt3RiQdzNNdXoa5HrDqJ6eg0Oyg8KI3E7/XJn/qK8bINgI2r2wJh9u8DaPyHW4lrO77TJPowiZFweRCicUS5fNNViv4nKwAixtbf9O/Ju6vIArbaWUmUBW5RhgOO4+T5WY4iylpLzmhaOw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=SMClMz6u; arc=none smtp.client-ip=209.85.214.170 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="SMClMz6u" Received: by mail-pl1-f170.google.com with SMTP id d9443c01a7336-220c8f38febso53510565ad.2 for ; Sat, 15 Feb 2025 03:04:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1739617474; x=1740222274; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=mjlDCIWwGo32gH8E4EO6vOfzFuAH4iigeCMDvhoWpo0=; b=SMClMz6ucR5Omywge9Mh5Nh8UqOATPYVXnMpcs/A2UjVTE1u9hHLB3q2dfQKX0bs/9 mQdBXWcBOTPBQjIlwHhPWQ7KFUENqgbSx/LLIkSC3yy93O6Zj63IMlPfU/myQGhWomY5 4GqFO0smXDKyFfcul9L8XGwicdSeTlsD/1BdcVlcQPvUtNBOmDAeYZfwULCozlkPAqpp Vgnz2SDpGWxZJ+A7iuqL0Apzue5FFU3j8smvrKZcXNwUFivvfeA/fSxbomGGxMAVFpOw 4EEeDLllKhtaItIn5INBUc+Tx919oZH1K7XbOd0PSKS38t9Pj32Ya1ut/92iJp5KsBpo fCcQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1739617474; x=1740222274; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=mjlDCIWwGo32gH8E4EO6vOfzFuAH4iigeCMDvhoWpo0=; b=X0fxyQaETa57npwtOKl2iRFMJw3342vDl1V1dc/RzkYxzIxmLCuYR3iUSB2eYmMCTr Ov3Ya7+2/WEFztgmpwN2FVg8t+WXD4xjWisZYY1gymgqhkdPXACsXvWKgNhzHuxbdK+T n2NIzDJRh/OsFZwbv9QJ/bFOPGbglJm0xRiEbdHPamgBWa4XXXVm9z+2stgn7cqHfrRz d5wo9vhWbV9zU3L9jPK8sMhbyz8CRPiQWCBDuygV9AUCotjOYpoa4NwtYHxRueHFVAnz tDkBvTJ5RA2964x4/ODUg+lQnPI69rwbrfx3hxOVyyb3136i0VpIjdWZ4BCVfF5IGatE 4DLg== X-Gm-Message-State: AOJu0YzxoyGCfj+A3BgodX7OUqwfbuiRiKIkLYvVyChqfoMBYRZJhxiD ENQbr5siO3KOVuoBmNdN3g7p4+0ZjTkFEKR7MN0FBfPUqi2mWHwY7bHdEg== X-Gm-Gg: ASbGncurhEoar5ByTpOxwF0SK+KhclX00m28pGLyC9lhvO8+nhiaRCChqu5XT1xDVq3 aj0nSeU/cSmiNdAWzoF377Vya/9aNCcMH6XWxRuIFYIUu95bgYPD4s/r+sCe4J/mHDclc9dGU9k JBpwDwl2lQVsS0Pr8gicvi6bGodmY5Erj7jocs+/BL/fD2byFxeLR2W0p8kxmQA5S1eIQYiTCE/ 3E7hRLmpIKs8b4SiTzOlYfYUCs5UDo84yihMxHQhUwSJgbvxIgyMqLJ9VPfVuJAk+ufIjt3PhLR NmsqhnXeGSM= X-Google-Smtp-Source: AGHT+IHT9oB1SgXYNBRy7hYEqPtbU8hieBvqAPfkxvPBRC7SeX+MWqWTqS/auVERHXO+6W5ozAL3Hw== X-Received: by 2002:a05:6a21:4ccc:b0:1e1:aa10:5491 with SMTP id adf61e73a8af0-1ee8cb814bbmr5942181637.24.1739617473760; Sat, 15 Feb 2025 03:04:33 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7326d58d4d0sm72435b3a.94.2025.02.15.03.04.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 15 Feb 2025 03:04:33 -0800 (PST) From: Eduard Zingerman To: bpf@vger.kernel.org, ast@kernel.org Cc: andrii@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev, kernel-team@fb.com, yonghong.song@linux.dev, tj@kernel.org, patsomaru@meta.com, Eduard Zingerman Subject: [PATCH bpf-next v1 05/10] bpf: detect infinite loop in get_loop_entry() Date: Sat, 15 Feb 2025 03:03:56 -0800 Message-ID: <20250215110411.3236773-6-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250215110411.3236773-1-eddyz87@gmail.com> References: <20250215110411.3236773-1-eddyz87@gmail.com> 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 Tejun Heo reported an infinite loop in get_loop_entry(), when verifying a sched_ext program layered_dispatch in [1]. After some investigation I'm sure that root cause is fixed by patches 1,3 in this patch-set. To err on the safe side, this commit modifies get_loop_entry() to detect infinite loops and abort verification in such cases. The number of steps get_loop_entry(S) can make while moving along the bpf_verifier_state->loop_entry chain is bounded by the DFS depth of state S. This fact is exploited to implement the check. To avoid dealing with the potential error code returned from get_loop_entry() in update_loop_entry(), remove the get_loop_entry() calls there: - This change does not affect correctness. Loop entries would still be updated during the backward DFS move in update_branch_counts(). - This change does not affect performance. Measurements show that get_loop_entry() performs at most 1 step on selftests and at most 2 steps on sched_ext programs (1 step in 17 cases, 2 steps in 3 cases, measured using "do-not-submit" patches from [2]). [1] https://github.com/sched-ext/scx/ commit f0b27038ea10 ("XXX - kernel stall") [2] https://github.com/eddyz87/bpf/tree/get-loop-entry-hungup Reported-by: Tejun Heo Signed-off-by: Eduard Zingerman --- kernel/bpf/verifier.c | 39 +++++++++++++++++++++------------------ 1 file changed, 21 insertions(+), 18 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 945a13b2cfeb..f750c8607470 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1792,12 +1792,9 @@ static bool same_callsites(struct bpf_verifier_state *a, struct bpf_verifier_sta * h = entries[h] * return h * - * # Update n's loop entry if h's outermost entry comes - * # before n's outermost entry in current DFS path. + * # Update n's loop entry if h comes before n in current DFS path. * def update_loop_entry(n, h): - * n1 = get_loop_entry(n) or n - * h1 = get_loop_entry(h) or h - * if h1 in path and depths[h1] <= depths[n1]: + * if h in path and depths[entries.get(n, n)] < depths[n]: * entries[n] = h1 * * def dfs(n, depth): @@ -1809,7 +1806,7 @@ static bool same_callsites(struct bpf_verifier_state *a, struct bpf_verifier_sta * # Case A: explore succ and update cur's loop entry * # only if succ's entry is in current DFS path. * dfs(succ, depth + 1) - * h = get_loop_entry(succ) + * h = entries.get(succ, None) * update_loop_entry(n, h) * else: * # Case B or C depending on `h1 in path` check in update_loop_entry(). @@ -1824,12 +1821,20 @@ static bool same_callsites(struct bpf_verifier_state *a, struct bpf_verifier_sta * - handle cases B and C in is_state_visited(); * - update topmost loop entry for intermediate states in get_loop_entry(). */ -static struct bpf_verifier_state *get_loop_entry(struct bpf_verifier_state *st) +static struct bpf_verifier_state *get_loop_entry(struct bpf_verifier_env *env, + struct bpf_verifier_state *st) { struct bpf_verifier_state *topmost = st->loop_entry, *old; + u32 steps = 0; - while (topmost && topmost->loop_entry && topmost != topmost->loop_entry) + while (topmost && topmost->loop_entry && topmost != topmost->loop_entry) { + if (steps++ > st->dfs_depth) { + WARN_ONCE(true, "verifier bug: infinite loop in get_loop_entry\n"); + verbose(env, "verifier bug: infinite loop in get_loop_entry()\n"); + return ERR_PTR(-EFAULT); + } topmost = topmost->loop_entry; + } /* Update loop entries for intermediate states to avoid this * traversal in future get_loop_entry() calls. */ @@ -1843,17 +1848,13 @@ static struct bpf_verifier_state *get_loop_entry(struct bpf_verifier_state *st) static void update_loop_entry(struct bpf_verifier_state *cur, struct bpf_verifier_state *hdr) { - struct bpf_verifier_state *cur1, *hdr1; - - cur1 = get_loop_entry(cur) ?: cur; - hdr1 = get_loop_entry(hdr) ?: hdr; - /* The head1->branches check decides between cases B and C in - * comment for get_loop_entry(). If hdr1->branches == 0 then + /* The hdr->branches check decides between cases B and C in + * comment for get_loop_entry(). If hdr->branches == 0 then * head's topmost loop entry is not in current DFS path, * hence 'cur' and 'hdr' are not in the same loop and there is * no need to update cur->loop_entry. */ - if (hdr1->branches && hdr1->dfs_depth <= cur1->dfs_depth) { + if (hdr->branches && hdr->dfs_depth <= (cur->loop_entry ?: cur)->dfs_depth) { cur->loop_entry = hdr; hdr->used_as_loop_entry = true; } @@ -17821,8 +17822,8 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn, while (sl) { if (sl->state.branches) goto next; - loop_entry = get_loop_entry(&sl->state); - if (loop_entry && loop_entry->branches) + loop_entry = get_loop_entry(env, &sl->state); + if (!IS_ERR_OR_NULL(loop_entry) && loop_entry->branches) goto next; if (sl->state.insn_idx != insn || !same_callsites(&sl->state, cur)) @@ -18700,7 +18701,9 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) * * Additional details are in the comment before get_loop_entry(). */ - loop_entry = get_loop_entry(&sl->state); + loop_entry = get_loop_entry(env, &sl->state); + if (IS_ERR(loop_entry)) + return PTR_ERR(loop_entry); force_exact = loop_entry && loop_entry->branches > 0; if (states_equal(env, &sl->state, cur, force_exact ? RANGE_WITHIN : NOT_EXACT)) { if (force_exact) From patchwork Sat Feb 15 11:03:57 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13976035 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pj1-f50.google.com (mail-pj1-f50.google.com [209.85.216.50]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D23861A9B39 for ; Sat, 15 Feb 2025 11:04:35 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.50 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617477; cv=none; b=CkJKiPrCDhAsQQW6iYFwwuuWbjbSJDk3Uj25OPTS1dUvPvotjNHiCOjsjQgiCQiGrBFl8/zCck+LIYS41QaRZBsUIKw1VKWs9ey1yMdgqTFAW6TRi5wC60Tqs6FXyls16BelI+LnErAGcENaPF7/AUY9RF4IwrzppZJEiWr2tTc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617477; c=relaxed/simple; bh=d/gA7YbLF8CuPatwKNVF8jZFZ3F4DtpmMEBhJe2mdQQ=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=NgfbSBicUqLQzuETtJmr7ZqadimknHX2t2TsE0X0EHR0jq6NqBB4pAvWHTeKOKLm85/qVn3mEw9eaw4ONowIFLM69y5gzpY1OEU53M8gPVFGOrq/jU4xor/Yf0nB3CtosNN4yw5LrC5VF9AfZWp3wbu8Po0+qmcXjTip+LyO6Kg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=kNYgj7Tv; arc=none smtp.client-ip=209.85.216.50 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="kNYgj7Tv" Received: by mail-pj1-f50.google.com with SMTP id 98e67ed59e1d1-2fbffe0254fso5333856a91.3 for ; Sat, 15 Feb 2025 03:04:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1739617475; x=1740222275; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=qD4Fri+vIX2r3fzgTK26CxYSkIN9OYppa9kRT0keu4A=; b=kNYgj7TvRO0V4xbwbTP2RK0c3cQ7q3uX3jsPN5C/mi+N9FqLQ0b14VoKc+JSM033cE 6z4z6zIgk5C+ymXGnCSR7h8IkG62mH78UnMMHCsRVLgTKWAaLpVxHIBpexZvujEVk7YH 7mGr1oaTqH9eftnflpSgNkYkW9sAkhn7hTfkOIYp0mF/5ALAVP0CGj/uNFnEqIB6LrLd bCt9fDBucUiNrxFBs6E0O3seaYWdAR5xdsGvqPKfXqFddVvfeAt9Q8US6Az7brSq2Cs9 SPUPkjlZbOSRNfIvjfF0sKlPSd0XkxqdxUAHdouPm5ynHSwq/XO/o1bO5ltr3Dd/afHN fxVw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1739617475; x=1740222275; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=qD4Fri+vIX2r3fzgTK26CxYSkIN9OYppa9kRT0keu4A=; b=TsouI0OjMXmp/IFhfi0aoFHAloos/K+pVM8kIgp8+E/+99teef6cTnCIMkzUz/8Zll MjzrB/BtWxqNomQFBTQ5MuOLBLwN3avVjhx7ruYo0G0ShwjO11MduAbf95oi4X4GM7CX wIfUZ7Ggd7oDjGVltnUsuJV4J7wVGPk5fppm76ZNlNfj9AM7RSU2mwfci7DYYRaAme0L sC9l2KVw9FhnT01x0fsxdquFLNwRVbHQOckLfSAsu4hb3xajaw/05UYVCQPLnhBjTdzA 6imgiC1pmGoRsFNbju6EBLhFOJ7QDaBYS982wyKbIaI4cgGXR93HUh1cRFP+v6RZCWJD 0Jqw== X-Gm-Message-State: AOJu0YzLMuAMceUqKFd7+Av6A0XZc6z3LqNPdBlL7TgWk3Qut3BSefeC QHaUlCDi0azqyFTUuundOxwZ0PalD1P6EGG3qhv1KoaFWnA0pFqEXGd/PQ== X-Gm-Gg: ASbGnctXkZcTPo7WHOBA10LcDbTf5KwAvBGNJ9nlO37jjMauZDfRyAyLfJdpBmYRex2 4oI7yy/YDGbw1U9cM/KliVB/BJ5HlzKAxFkTRJ70QHqDJGPBWbz4SUzGudJhtDZLht7CdnPSQ3+ I8kv/lkjq4LZT93dK6FY7uX2hHJ/9ObW4AtTdlApoRJYzgEb13c5PuXu6yxhH1XSvX7wfkCaXHD wPh4uic8NtnAFYu3quDgDe/48A0vuKxKACxU4pHYYUV7oQ0YrvcuW2nR4FyqHhsg4PF3zyX/BYL +72l0R8pkTg= X-Google-Smtp-Source: AGHT+IG1trQgNo7jW2laOLKHbSGl2l8ALFyGvU1PHIRf1bZOsOE3BpIUouAXjwnZ7csn8iNIIezr9w== X-Received: by 2002:a05:6a00:198c:b0:732:1840:8382 with SMTP id d2e1a72fcca58-7326144b0b3mr4815210b3a.0.1739617474965; Sat, 15 Feb 2025 03:04:34 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7326d58d4d0sm72435b3a.94.2025.02.15.03.04.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 15 Feb 2025 03:04:34 -0800 (PST) From: Eduard Zingerman To: bpf@vger.kernel.org, ast@kernel.org Cc: andrii@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev, kernel-team@fb.com, yonghong.song@linux.dev, tj@kernel.org, patsomaru@meta.com, Eduard Zingerman Subject: [PATCH bpf-next v1 06/10] bpf: make state->dfs_depth < state->loop_entry->dfs_depth an invariant Date: Sat, 15 Feb 2025 03:03:57 -0800 Message-ID: <20250215110411.3236773-7-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250215110411.3236773-1-eddyz87@gmail.com> References: <20250215110411.3236773-1-eddyz87@gmail.com> 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 a generic loop detection algorithm a graph node can be a loop header for itself. However, state loop entries are computed for use in is_state_visited(), where get_loop_entry(state)->branches is checked. is_state_visited() also checks state->branches, thus the case when state == state->loop_entry is not interesting for is_state_visited(). This change does not affect correctness, but simplifies get_loop_entry() a bit and also simplifies change to update_loop_entry() in patch 9. Signed-off-by: Eduard Zingerman --- kernel/bpf/verifier.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index f750c8607470..02f60b8683b5 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1788,7 +1788,7 @@ static bool same_callsites(struct bpf_verifier_state *a, struct bpf_verifier_sta * # Find outermost loop entry known for n * def get_loop_entry(n): * h = entries.get(n, None) - * while h in entries and entries[h] != h: + * while h in entries: * h = entries[h] * return h * @@ -1827,7 +1827,7 @@ static struct bpf_verifier_state *get_loop_entry(struct bpf_verifier_env *env, struct bpf_verifier_state *topmost = st->loop_entry, *old; u32 steps = 0; - while (topmost && topmost->loop_entry && topmost != topmost->loop_entry) { + while (topmost && topmost->loop_entry) { if (steps++ > st->dfs_depth) { WARN_ONCE(true, "verifier bug: infinite loop in get_loop_entry\n"); verbose(env, "verifier bug: infinite loop in get_loop_entry()\n"); @@ -1854,7 +1854,7 @@ static void update_loop_entry(struct bpf_verifier_state *cur, struct bpf_verifie * hence 'cur' and 'hdr' are not in the same loop and there is * no need to update cur->loop_entry. */ - if (hdr->branches && hdr->dfs_depth <= (cur->loop_entry ?: cur)->dfs_depth) { + if (hdr->branches && hdr->dfs_depth < (cur->loop_entry ?: cur)->dfs_depth) { cur->loop_entry = hdr; hdr->used_as_loop_entry = true; } From patchwork Sat Feb 15 11:03:58 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13976036 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f178.google.com (mail-pl1-f178.google.com [209.85.214.178]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 289D71AAA05 for ; Sat, 15 Feb 2025 11:04:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617478; cv=none; b=kGM7lVq7vw+0Pus5P7ngUpDEZbiQuU7YiCYgB7faO4JIhm4S6AsTA1BdXDUlBohV2R0I2MFQz/uyH0cA7rMwlBmkXsMq74rBqA6EErIeZmFK9oMF4Y8TZzFHwgW911uE3qOiPMSXdP3r+19vf8BgrVaeJCBcpNg4TrqxRwZnIzM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617478; c=relaxed/simple; bh=zW8+5TENzAvCSmTbURt8vxWlBzCtY0nYAdZoNcBCKw4=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=T0Dg4YRTamBNscPCl1GPN0sJUy46p6TT2ff1AV0xTxe3iEImlBdwSAiqPCk4koAg1pgSfXeET/zLI3bW8mAK/kx8z3Tu8AAuFo6u4K+1l11pBFDwarv7zBQmA1TLSr6NRQOjmTCJeBjEP+1xmlcPFpBQ/eyLikEaD1qIUV4rLpk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=PdtwdkCx; arc=none smtp.client-ip=209.85.214.178 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="PdtwdkCx" Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-220e6028214so43940425ad.0 for ; Sat, 15 Feb 2025 03:04:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1739617476; x=1740222276; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=k+bl+eqTT71k7Cy8xTV2OMB4wPPQcmIs2LMmUf+rGFc=; b=PdtwdkCx2f3jUjRS/yjV2TniVpCV9DXTfW/cQVlKz3mmaTxJAzY/TsGxPKotYVozTX Udhh9ce33RLKtLeoXO7k8UyKjFUlNIAuLQuE0etyz0ex2/nVH0uXZ3hWcjFTrEN38iD7 T8RczHYIkIP69KX+tK4362RbCaMM2URpESCbTd9/6HOZ7SoUkxXHDQH87w1/3J1vgA+Q BF4YdOKnwvlonDqqt3Yaw082EOu2SJ5DdAqO/XHdARSW5tWBjYXoWbML1kcAhfD9JM5m 92q9OFbVKitL3aEFLNyQ/KkBTfgqmIe4hnflrqSFPRtx0Woszum7iBqZsEvvKzN+/fvZ WVSQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1739617476; x=1740222276; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=k+bl+eqTT71k7Cy8xTV2OMB4wPPQcmIs2LMmUf+rGFc=; b=QFDSI8VMCGWskI+Z5NrvRPs/JAtiOx01/hDfJ9I05JbzcWGOZ6cCI0JQmFIVHPicUS yOmCIhuTf3xu1RzGZE0HCmQ+GtKO5Zi1A7TQnNLdcGTj6zVB2VkkP9fY3XFgX7Xp7DT5 l6DhP1sU+SgLtfHdlkSaaSMzRRxRlgTvk67CGrnen/Jql3yqRo3/Y2N6M8WALv+TutpU Neup7hCPRuGIuGUGohTVoeBFgxhxzUEGmcpM58cSyH/Lcm6s244H/PhdqiYDbR72lMJ+ tNLsDd2BRJlpoffUKrp+lXWR9eElYtq5J8CBjNWII+BgsYJYhiDScfQQnx8nIIjNUfa9 KNlQ== X-Gm-Message-State: AOJu0YwTTGpmLOHa3Kn1gWgjl6ZzwiryTzoS20DEB/6yM0pkru/fqhiO CY+v3k4J25eKqvWCrHI2lNBsHTxBhZVHlsYEXE5tAU4h7gcLMLfV5Y59Cw== X-Gm-Gg: ASbGncvKFu7dSgxX9lA8dp8OEG+BTAJjgI1q0OFEV/mq5R8Wwkr6TjC+COBto5WffHg hjryK5aIlMP93tWnNqaY2jML1bnsV5Vk5/H1wTpsfjVG5curU1u01E0TE/sdnWy1UdJBX5phWCd aL1U4heABoAxOqx2iZGhAUa6en9wFKakJwc1LdpLu5sVl7w2Lt/ZG9LlirWSm4GSUn00ScQeNqY gMu+VkUu6n+6PPBHOPwTXmK8yhCPpKaMDq/4/m686BMXGzph3wjxf3T8jzH/1Usmvrh3Xj92cYN QAew36CF6oo= X-Google-Smtp-Source: AGHT+IF5xSaFP4uk9kfHqmRO+6ik1V2ezCbpf/X+GjHmbQ5SFQVysU0bq5CMeOjBdx5Ls0J8sUVLag== X-Received: by 2002:a05:6a00:2351:b0:732:564e:1ec6 with SMTP id d2e1a72fcca58-7326193a7e0mr3825641b3a.22.1739617476075; Sat, 15 Feb 2025 03:04:36 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7326d58d4d0sm72435b3a.94.2025.02.15.03.04.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 15 Feb 2025 03:04:35 -0800 (PST) From: Eduard Zingerman To: bpf@vger.kernel.org, ast@kernel.org Cc: andrii@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev, kernel-team@fb.com, yonghong.song@linux.dev, tj@kernel.org, patsomaru@meta.com, Eduard Zingerman Subject: [PATCH bpf-next v1 07/10] bpf: do not update state->loop_entry in get_loop_entry() Date: Sat, 15 Feb 2025 03:03:58 -0800 Message-ID: <20250215110411.3236773-8-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250215110411.3236773-1-eddyz87@gmail.com> References: <20250215110411.3236773-1-eddyz87@gmail.com> 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 The patch 9 is simpler if less places modify loop_entry field. The loop deleted by this patch does not affect correctness, but is a performance optimization. However, measurements on selftests and sched_ext programs show that this optimization is unnecessary: - at most 2 steps are done in get_loop_entry(); - most of the time 0 or 1 steps are done in get_loop_entry(). Measured using "do-not-submit" patches from here: https://github.com/eddyz87/bpf/tree/get-loop-entry-hungup Signed-off-by: Eduard Zingerman --- kernel/bpf/verifier.c | 13 ++----------- 1 file changed, 2 insertions(+), 11 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 02f60b8683b5..3c3f33d90fc0 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1818,13 +1818,12 @@ static bool same_callsites(struct bpf_verifier_state *a, struct bpf_verifier_sta * and cur's loop entry has to be updated (case A), handle this in * update_branch_counts(); * - use st->branch > 0 as a signal that st is in the current DFS path; - * - handle cases B and C in is_state_visited(); - * - update topmost loop entry for intermediate states in get_loop_entry(). + * - handle cases B and C in is_state_visited(). */ static struct bpf_verifier_state *get_loop_entry(struct bpf_verifier_env *env, struct bpf_verifier_state *st) { - struct bpf_verifier_state *topmost = st->loop_entry, *old; + struct bpf_verifier_state *topmost = st->loop_entry; u32 steps = 0; while (topmost && topmost->loop_entry) { @@ -1835,14 +1834,6 @@ static struct bpf_verifier_state *get_loop_entry(struct bpf_verifier_env *env, } topmost = topmost->loop_entry; } - /* Update loop entries for intermediate states to avoid this - * traversal in future get_loop_entry() calls. - */ - while (st && st->loop_entry != topmost) { - old = st->loop_entry; - st->loop_entry = topmost; - st = old; - } return topmost; } From patchwork Sat Feb 15 11:03:59 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13976037 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f169.google.com (mail-pl1-f169.google.com [209.85.214.169]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 6188C1A9B39 for ; Sat, 15 Feb 2025 11:04:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617480; cv=none; b=Md7i+Q+wjISTN7MtVyHPIUfD2le+6VkKnXOhupOGFD87uZ17jlroNPFhvVfgmdQgQzdX7swxLDMSgK8p510li0A3PLUBo+uJLXqpbB6PHUzvdFCAPhXH8ayeboM835rEiWG7rG6LvrNh/NJKJ2JGPNzK6OQJ1XEOhd1WaloYC60= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617480; c=relaxed/simple; bh=znfSnaYoA7dCF7AWy0G4YR2r/ImBgWEfa88RBqrB39g=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=T1y292Cm6P1Tq3vvZPJEX1G4HnC27bm1ViE9v+Uha53KfH4i8e3KjPkpUYrph5idlZN7YEPmKRO5GfvEK0/s6ZHkt0f5t3jEf7X0W2DuRDqlIuCFdDF4qV359ljgM/o4MjpJOlf4qbU4zVgUUwKwgG4jkHM0H8Mh7uvIepi7pYk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=AzVvSZPx; arc=none smtp.client-ip=209.85.214.169 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="AzVvSZPx" Received: by mail-pl1-f169.google.com with SMTP id d9443c01a7336-22100006bc8so15929625ad.0 for ; Sat, 15 Feb 2025 03:04:38 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1739617477; x=1740222277; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=ffDif9cLlzs8ZbWp40VK6UKD3HwOOkOekNENzc4XXA4=; b=AzVvSZPx8BprxUx+fwYRsAxtF/NM3o8as9sEXFpFxlRMGqLjQGr+1Or+YoDVY9XHer xvz6KXPk/FxGkv3b67Ro/Bn8Rn5i/1xfsDOlDr8daqc5lbgQ/4xE05ivUDOQaJ/B/us7 wNFCPvVBDGrc08uLtSobRA7R977PGyOdprUSRxVxDOEgr7QEvoO/nZSFQ+EAH7eSzYTg Yq2/C8Y9cmMJp3UtFLwt/aveDpyruf5wUcHXfm/h/PeNazrECId4WhcXsBsb3HQNCszJ wYh+ReqJ0PnqNOhckrBUPDh6X0zJfSiQH2kQPJHTbNT/U23ZHwPuXx4YWp0Ynexyu4vM 2tQw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1739617477; x=1740222277; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=ffDif9cLlzs8ZbWp40VK6UKD3HwOOkOekNENzc4XXA4=; b=SOgqAnKlQdAoCbnAvfDLtOS/sifmmlfaEpIL0Bh27VmrZ3KntxsHAVMjeTV2Sqi0ya O+ZQGl+i/B/GqXtz2u+TFmZ3pkqn7+XfToeUp1KDnhF4ZUoBSuoHJsXYxBrhRhYL7OZ5 DGmglDtPvs8eMr3Elu1Gi1hi+sQNqRvskW2YNfKDtXm/W70A44sMr1wtITEkjUYMjVou yYtYrboWmNiB25pTp2FGdAAELzTHvIvMz+F3yxeJ7zppqNfWlBVuaBROVnuitww7bErg TEgnSsF18U0kmVSQIoPVmw4Ak3w5l7QB6hdqcr8KqbyraUGtxxyjOibZg8qcbvtiA/rf e5lQ== X-Gm-Message-State: AOJu0Yze+Ubgkbundzdm7bkAU8kDPiHBXX4A543d4ADddZzSp3FryMF5 vj6yYvOokRUADVvbm+5nXWMn/+/7bEN1wuH/UEm0nG+gVW0sSQA4yHdUBg== X-Gm-Gg: ASbGnctK90RN2W2yv4fpc0D4p8SfhW5T8O/+CmG9XLVStiHzYfbuuWcouMkIFNGMbOa 9DzAg6CVIRTP7AagO7UBTc01SFEWF5W3ToVpYjSweNcES6dQmRntrQgQpA+UJg7TkcOFj6DJrfy NvptK4Eoc5Ao4QuMs0fiRVszOK9ga4Z4rDbqHPQLuG5XvgG46cikf89ws2IDls7FYMbXdSalSLM POpIdASsF9dZXh9IHFUoXZo2Cjrqj24uKXCAZRJ6agj6IsSoXIKfx2AH00+HS694dfIqUwwdQTT 8GYIZhKAwwQ= X-Google-Smtp-Source: AGHT+IGSgvBvZQd8CCejELJFSxcTouIhTLCjN6i+gokvYx+LYvSej1O7cOKbH3DC1KuS4PCD7YLjOQ== X-Received: by 2002:a05:6a00:3d55:b0:730:7d3f:8c7d with SMTP id d2e1a72fcca58-732618c23d0mr3830636b3a.15.1739617477423; Sat, 15 Feb 2025 03:04:37 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7326d58d4d0sm72435b3a.94.2025.02.15.03.04.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 15 Feb 2025 03:04:36 -0800 (PST) From: Eduard Zingerman To: bpf@vger.kernel.org, ast@kernel.org Cc: andrii@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev, kernel-team@fb.com, yonghong.song@linux.dev, tj@kernel.org, patsomaru@meta.com, Eduard Zingerman Subject: [PATCH bpf-next v1 08/10] bpf: use list_head to track explored states and free list Date: Sat, 15 Feb 2025 03:03:59 -0800 Message-ID: <20250215110411.3236773-9-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250215110411.3236773-1-eddyz87@gmail.com> References: <20250215110411.3236773-1-eddyz87@gmail.com> 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 The next patch in the set needs the ability to remove individual states from env->free_list while only holding a pointer to the state. Which requires env->free_list to be a doubly linked list. This patch converts env->free_list and struct bpf_verifier_state_list to use struct list_head for this purpose. The change to env->explored_states is collateral. Signed-off-by: Eduard Zingerman --- include/linux/bpf_verifier.h | 9 +++-- kernel/bpf/verifier.c | 74 ++++++++++++++++++------------------ 2 files changed, 42 insertions(+), 41 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 32c23f2a3086..222f6af278ec 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -498,7 +498,7 @@ struct bpf_verifier_state { /* linked list of verifier states used to prune search */ struct bpf_verifier_state_list { struct bpf_verifier_state state; - struct bpf_verifier_state_list *next; + struct list_head node; int miss_cnt, hit_cnt; }; @@ -710,8 +710,11 @@ struct bpf_verifier_env { bool test_state_freq; /* test verifier with different pruning frequency */ bool test_reg_invariants; /* fail verification on register invariants violations */ struct bpf_verifier_state *cur_state; /* current verifier state */ - struct bpf_verifier_state_list **explored_states; /* search pruning optimization */ - struct bpf_verifier_state_list *free_list; + /* Search pruning optimization, array of list_heads for + * lists of struct bpf_verifier_state_list. + */ + struct list_head *explored_states; + struct list_head free_list; /* list of struct bpf_verifier_state_list */ struct bpf_map *used_maps[MAX_USED_MAPS]; /* array of map's used by eBPF program */ struct btf_mod_pair used_btfs[MAX_USED_BTFS]; /* array of BTF's used by BPF program */ u32 used_map_cnt; /* number of used maps */ diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 3c3f33d90fc0..1016481ea754 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1680,7 +1680,7 @@ static u32 state_htab_size(struct bpf_verifier_env *env) return env->prog->len; } -static struct bpf_verifier_state_list **explored_state(struct bpf_verifier_env *env, int idx) +static struct list_head *explored_state(struct bpf_verifier_env *env, int idx) { struct bpf_verifier_state *cur = env->cur_state; struct bpf_func_state *state = cur->frame[cur->curframe]; @@ -8422,10 +8422,12 @@ static struct bpf_verifier_state *find_prev_entry(struct bpf_verifier_env *env, { struct bpf_verifier_state_list *sl; struct bpf_verifier_state *st; + struct list_head *pos, *head; /* Explored states are pushed in stack order, most recent states come first */ - sl = *explored_state(env, insn_idx); - for (; sl; sl = sl->next) { + head = explored_state(env, insn_idx); + list_for_each(pos, head) { + sl = container_of(pos, struct bpf_verifier_state_list, node); /* If st->branches != 0 state is a part of current DFS verification path, * hence cur & st for a loop. */ @@ -17808,20 +17810,20 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn, { struct bpf_verifier_state *loop_entry; struct bpf_verifier_state_list *sl; + struct list_head *pos, *head; - sl = *explored_state(env, insn); - while (sl) { + head = explored_state(env, insn); + list_for_each(pos, head) { + sl = container_of(pos, struct bpf_verifier_state_list, node); if (sl->state.branches) - goto next; + continue; loop_entry = get_loop_entry(env, &sl->state); if (!IS_ERR_OR_NULL(loop_entry) && loop_entry->branches) - goto next; + continue; if (sl->state.insn_idx != insn || !same_callsites(&sl->state, cur)) - goto next; + continue; clean_verifier_state(env, &sl->state); -next: - sl = sl->next; } } @@ -18512,10 +18514,11 @@ static bool iter_active_depths_differ(struct bpf_verifier_state *old, struct bpf static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) { struct bpf_verifier_state_list *new_sl; - struct bpf_verifier_state_list *sl, **pprev; + struct bpf_verifier_state_list *sl; struct bpf_verifier_state *cur = env->cur_state, *new, *loop_entry; int i, j, n, err, states_cnt = 0; bool force_new_state, add_new_state, force_exact; + struct list_head *pos, *tmp, *head; force_new_state = env->test_state_freq || is_force_checkpoint(env, insn_idx) || /* Avoid accumulating infinitely long jmp history */ @@ -18534,15 +18537,14 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) env->insn_processed - env->prev_insn_processed >= 8) add_new_state = true; - pprev = explored_state(env, insn_idx); - sl = *pprev; - clean_live_states(env, insn_idx, cur); - while (sl) { + head = explored_state(env, insn_idx); + list_for_each_safe(pos, tmp, head) { + sl = container_of(pos, struct bpf_verifier_state_list, node); states_cnt++; if (sl->state.insn_idx != insn_idx) - goto next; + continue; if (sl->state.branches) { struct bpf_func_state *frame = sl->state.frame[sl->state.curframe]; @@ -18747,7 +18749,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) /* the state is unlikely to be useful. Remove it to * speed up verification */ - *pprev = sl->next; + list_del(&sl->node); if (sl->state.frame[0]->regs[0].live & REG_LIVE_DONE && !sl->state.used_as_loop_entry) { u32 br = sl->state.branches; @@ -18763,15 +18765,9 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) * walk it later. Add it for free_list instead to * be freed at the end of verification */ - sl->next = env->free_list; - env->free_list = sl; + list_add(&sl->node, &env->free_list); } - sl = *pprev; - continue; } -next: - pprev = &sl->next; - sl = *pprev; } if (env->max_states_per_insn < states_cnt) @@ -18820,8 +18816,8 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) cur->first_insn_idx = insn_idx; cur->insn_hist_start = cur->insn_hist_end; cur->dfs_depth = new->dfs_depth + 1; - new_sl->next = *explored_state(env, insn_idx); - *explored_state(env, insn_idx) = new_sl; + list_add(&new_sl->node, head); + /* connect new state to parentage chain. Current frame needs all * registers connected. Only r6 - r9 of the callers are alive (pushed * to the stack implicitly by JITs) so in callers' frames connect just @@ -22138,31 +22134,29 @@ static int remove_fastcall_spills_fills(struct bpf_verifier_env *env) static void free_states(struct bpf_verifier_env *env) { - struct bpf_verifier_state_list *sl, *sln; + struct bpf_verifier_state_list *sl; + struct list_head *head, *pos, *tmp; int i; - sl = env->free_list; - while (sl) { - sln = sl->next; + list_for_each_safe(pos, tmp, &env->free_list) { + sl = container_of(pos, struct bpf_verifier_state_list, node); free_verifier_state(&sl->state, false); kfree(sl); - sl = sln; } - env->free_list = NULL; + INIT_LIST_HEAD(&env->free_list); if (!env->explored_states) return; for (i = 0; i < state_htab_size(env); i++) { - sl = env->explored_states[i]; + head = &env->explored_states[i]; - while (sl) { - sln = sl->next; + list_for_each_safe(pos, tmp, head) { + sl = container_of(pos, struct bpf_verifier_state_list, node); free_verifier_state(&sl->state, false); kfree(sl); - sl = sln; } - env->explored_states[i] = NULL; + INIT_LIST_HEAD(&env->explored_states[i]); } } @@ -23120,12 +23114,16 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3 env->test_reg_invariants = attr->prog_flags & BPF_F_TEST_REG_INVARIANTS; env->explored_states = kvcalloc(state_htab_size(env), - sizeof(struct bpf_verifier_state_list *), + sizeof(struct list_head), GFP_USER); ret = -ENOMEM; if (!env->explored_states) goto skip_full_check; + for (i = 0; i < state_htab_size(env); i++) + INIT_LIST_HEAD(&env->explored_states[i]); + INIT_LIST_HEAD(&env->free_list); + ret = check_btf_info_early(env, attr, uattr); if (ret < 0) goto skip_full_check; From patchwork Sat Feb 15 11:04:00 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13976038 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f178.google.com (mail-pl1-f178.google.com [209.85.214.178]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id A36C01A2385 for ; Sat, 15 Feb 2025 11:04:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617481; cv=none; b=Ulq1TVYsQ2Ac7WNfkfl/R3GH3AdiRvMdeZGGP6xd6hBodSmNU0Ak2i3YLgZ46bneAHCBdF9EVRqgJIQoeY8NI5jAmWhWi37V1mqn82iwjP00939Pwh6xCunaTD68q1K0KYrJKiw69RsRJWZUwB6WjRdMMOcNjseNd3p6OZfFlsA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617481; c=relaxed/simple; bh=+DfS+GyLbUJHdW/X64WkBKFCZRZg+hk/cJW8fdRccLs=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=NtVdawx+roqZmPT9DL5sC5Z6TsXtTI8uK3k3LVWGjCfORR7tvaz7Kn8FPPBSrCjm9fkm7CVC1nnMxfCFu4/bTSCwRbyAULEvnymFL8SR9rLTnE55p2uh/OeO8enWKK2/YSxWoS/6V1KxSzV8YRNSCxS/+GqyUeGazx42IDsPusA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=nfGLH+MA; arc=none smtp.client-ip=209.85.214.178 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="nfGLH+MA" Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-220e83d65e5so39980485ad.1 for ; Sat, 15 Feb 2025 03:04:39 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1739617479; x=1740222279; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=6gR0Ow73SgpQ9Ni07Z6IDcyMmHQIfl1OEhqIwDsg3G8=; b=nfGLH+MAdO+3qUsj3uPYtH0tOZnP+DiCMbkVZ8QA/pHNZ6dGAC+DQdSDgp+8kHbWS+ 7vgdmnaMSG9lIhhcYjzOhf41WEstU6dTB28Fz1boyGcewhVUTD5IeCJAOFjZgiP0sX3e 23+1wqd501uIAG1MSi5twOpFRfnJvdhkPOOp3HkvXhttSPmC4Ctl+yVW6v46AS4WTbl5 3h7uqx6fyYcah/M1t+8nQuwoTGWkbj0YYLYMFOUl+0tROaoAPKCHwJbwTogbZdj6pGdH GMrKEE37nTCe4aP1OAa2xCx2Tkl+b4L1G7+cVOxGMbCUPh0RD6XJ9gA553U/vyndhumz TVDQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1739617479; x=1740222279; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=6gR0Ow73SgpQ9Ni07Z6IDcyMmHQIfl1OEhqIwDsg3G8=; b=kmUWszndkjyX2QRRcrsalZRehRcJO0OwjqoC8hre4aPKYYKAn/9l1U3gUfzq1wBoZ4 qUZMmJLYx88l5x4qPGVv/rjViM/UwROoy8vjacV4YBDO0U/ff7JavC9mUudjHseqyZNc /xbieOa8e0AtBKOljQe3p3ftXWKTVlWSoM0Cjhik7GJ/CRKqJiI7gJPCNLR/EIc44WHc ca7hARCKJQOyY09ILBXt2okPgaLfP7fQggIrbfYRhXpKv2qPjaASVTo8UkgJ29eyjMed v7I92WR734FTps+UBmgb/hi9UMK84038z/B3IXeujn3HI84Sztns+W6VyYojPDPSt8/B vdkA== X-Gm-Message-State: AOJu0YxAno1dWN9rvPo9P/83Kap7dCxUh8n0klwIDpGwTwqmciWUEgXk 3o/ZhWowg6xsvfAI4FQqSlN5UrYyxmhnIKPB1yqvcILV5KXZT9f23W89sA== X-Gm-Gg: ASbGncsmBfEuhfXTeiWtnCIhcwzvT8z3adquoWlFly3THbpGk9UqsOPLEmgaT/bFak3 tQmSAG9yXSpylpn6hPSOheaLpTfuGsNPmggxjGgLlZ6tyV4YZ5lCAO1LDfYfUWBYwp79RBJjuSd PFNHfW5UgH/5kdXqX3ui5tJt1fvH82jJG97/Wq7OA4eOLnBzMetn+rgeNd1KLfLlWeUZVCdGcA5 57VXTwJbZFY9WKj3xiWAFedPV3ydGHSJ2opOGneqPxUGBwPskomJVihfeYyPwkMG3nhkzGYTsX5 8IknNaZBrRI= X-Google-Smtp-Source: AGHT+IFrjOBiaNW5fjL02+gyQaqCNKSpOeREIgajsD8+ZZvx+e7FUn8hZfPABlWN3rrSPCmIx4B+KA== X-Received: by 2002:a05:6a20:9145:b0:1ee:6ec3:e824 with SMTP id adf61e73a8af0-1ee8cba0ff3mr5006380637.30.1739617478710; Sat, 15 Feb 2025 03:04:38 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7326d58d4d0sm72435b3a.94.2025.02.15.03.04.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 15 Feb 2025 03:04:38 -0800 (PST) From: Eduard Zingerman To: bpf@vger.kernel.org, ast@kernel.org Cc: andrii@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev, kernel-team@fb.com, yonghong.song@linux.dev, tj@kernel.org, patsomaru@meta.com, Eduard Zingerman Subject: [PATCH bpf-next v1 09/10] bpf: free verifier states when they are no longer referenced Date: Sat, 15 Feb 2025 03:04:00 -0800 Message-ID: <20250215110411.3236773-10-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250215110411.3236773-1-eddyz87@gmail.com> References: <20250215110411.3236773-1-eddyz87@gmail.com> 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 When fixes from patches 1 and 3 are applied, Patrick Somaru reported an increase in memory consumption for sched_ext iterator-based programs hitting 1M instructions limit. For example, 2Gb VMs ran out of memory while verifying a program. Similar behaviour could be reproduced on current bpf-next master. Here is an example of such program: /* verification completes if given 16G or RAM, * final env->free_list size is 369,960 entries. */ SEC("raw_tp") __flag(BPF_F_TEST_STATE_FREQ) __success int free_list_bomb(const void *ctx) { volatile char buf[48] = {}; unsigned i, j; j = 0; bpf_for(i, 0, 10) { /* this forks verifier state: * - verification of current path continues and * creates a checkpoint after 'if'; * - verification of forked path hits the * checkpoint and marks it as loop_entry. */ if (bpf_get_prandom_u32()) asm volatile (""); /* this marks 'j' as precise, thus any checkpoint * created on current iteration would not be matched * on the next iteration. */ buf[j++] = 42; j %= ARRAY_SIZE(buf); } asm volatile (""::"r"(buf)); return 0; } Memory consumption increased due to more states being marked as loop entries and eventually added to env->free_list. This commit introduces logic to free states from env->free_list during verification. A state in env->free_list can be freed if: - it has no child states; - it is not used as a loop_entry. This commit: - updates bpf_verifier_state->used_as_loop_entry to be a counter that tracks how many states use this one as a loop entry; - adds a function maybe_free_verifier_state(), which: - frees a state if its ->branches and ->used_as_loop_entry counters are both zero; - if the state is freed, state->loop_entry->used_as_loop_entry is decremented, and an attempt is made to free state->loop_entry. In the example above, this approach reduces the maximum number of states in the free list from 369,960 to 16,223. However, this approach has its limitations. If the buf size in the example above is modified to 64, state caching overflows: the state for j=0 is evicted from the cache before it can be used to stop traversal. As a result, states in the free list accumulate because their branch counters do not reach zero. The effect of this patch on the selftests looks as follows: File Program Max free list (A) Max free list (B) Max free list (DIFF) -------------------------------- ------------------------------------ ----------------- ----------------- -------------------- arena_list.bpf.o arena_list_add 17 3 -14 (-82.35%) bpf_iter_task_stack.bpf.o dump_task_stack 39 9 -30 (-76.92%) iters.bpf.o checkpoint_states_deletion 265 89 -176 (-66.42%) iters.bpf.o clean_live_states 19 0 -19 (-100.00%) profiler2.bpf.o tracepoint__syscalls__sys_enter_kill 102 1 -101 (-99.02%) profiler3.bpf.o tracepoint__syscalls__sys_enter_kill 144 0 -144 (-100.00%) pyperf600_iter.bpf.o on_event 15 0 -15 (-100.00%) pyperf600_nounroll.bpf.o on_event 1170 1158 -12 (-1.03%) setget_sockopt.bpf.o skops_sockopt 18 0 -18 (-100.00%) strobemeta_nounroll1.bpf.o on_event 147 83 -64 (-43.54%) strobemeta_nounroll2.bpf.o on_event 312 209 -103 (-33.01%) strobemeta_subprogs.bpf.o on_event 124 86 -38 (-30.65%) test_cls_redirect_subprogs.bpf.o cls_redirect 15 0 -15 (-100.00%) timer.bpf.o test1 30 15 -15 (-50.00%) Measured using "do-not-submit" patches from here: https://github.com/eddyz87/bpf/tree/get-loop-entry-hungup Reported-by: Patrick Somaru Signed-off-by: Eduard Zingerman --- include/linux/bpf_verifier.h | 14 +++--- kernel/bpf/verifier.c | 91 ++++++++++++++++++++++++++---------- 2 files changed, 75 insertions(+), 30 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 222f6af278ec..f920af30eb06 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -427,11 +427,6 @@ struct bpf_verifier_state { bool active_rcu_lock; bool speculative; - /* If this state was ever pointed-to by other state's loop_entry field - * this flag would be set to true. Used to avoid freeing such states - * while they are still in use. - */ - bool used_as_loop_entry; bool in_sleepable; /* first and last insn idx of this verifier state */ @@ -458,6 +453,11 @@ struct bpf_verifier_state { u32 dfs_depth; u32 callback_unroll_depth; u32 may_goto_depth; + /* If this state was ever pointed-to by other state's loop_entry field + * this flag would be set to true. Used to avoid freeing such states + * while they are still in use. + */ + u32 used_as_loop_entry; }; #define bpf_get_spilled_reg(slot, frame, mask) \ @@ -499,7 +499,9 @@ struct bpf_verifier_state { struct bpf_verifier_state_list { struct bpf_verifier_state state; struct list_head node; - int miss_cnt, hit_cnt; + u32 miss_cnt; + u32 hit_cnt:31; + u32 in_free_list:1; }; struct bpf_loop_inline_state { diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 1016481ea754..eadd404ab9ab 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1620,6 +1620,50 @@ static void free_verifier_state(struct bpf_verifier_state *state, kfree(state); } +/* struct bpf_verifier_state->{parent,loop_entry} refer to states + * that are in either of env->{expored_states,free_list}. + * In both cases the state is contained in struct bpf_verifier_state_list. + */ +static struct bpf_verifier_state_list *state_parent_as_list(struct bpf_verifier_state *st) +{ + if (st->parent) + return container_of(st->parent, struct bpf_verifier_state_list, state); + return NULL; +} + +static struct bpf_verifier_state_list *state_loop_entry_as_list(struct bpf_verifier_state *st) +{ + if (st->loop_entry) + return container_of(st->loop_entry, struct bpf_verifier_state_list, state); + return NULL; +} + +/* A state can be freed if it is no longer referenced: + * - is in the env->free_list; + * - has no children states; + * - is not used as loop_entry. + * + * Freeing a state can make it's loop_entry free-able. + */ +static void maybe_free_verifier_state(struct bpf_verifier_env *env, + struct bpf_verifier_state_list *sl) +{ + struct bpf_verifier_state_list *loop_entry_sl; + + while (sl && sl->in_free_list && + sl->state.branches == 0 && + sl->state.used_as_loop_entry == 0) { + loop_entry_sl = state_loop_entry_as_list(&sl->state); + if (loop_entry_sl) + loop_entry_sl->state.used_as_loop_entry--; + list_del(&sl->node); + free_verifier_state(&sl->state, false); + kfree(sl); + env->peak_states--; + sl = loop_entry_sl; + } +} + /* copy verifier state from src to dst growing dst stack space * when necessary to accommodate larger src stack */ @@ -1837,7 +1881,8 @@ static struct bpf_verifier_state *get_loop_entry(struct bpf_verifier_env *env, return topmost; } -static void update_loop_entry(struct bpf_verifier_state *cur, struct bpf_verifier_state *hdr) +static void update_loop_entry(struct bpf_verifier_env *env, + struct bpf_verifier_state *cur, struct bpf_verifier_state *hdr) { /* The hdr->branches check decides between cases B and C in * comment for get_loop_entry(). If hdr->branches == 0 then @@ -1846,13 +1891,20 @@ static void update_loop_entry(struct bpf_verifier_state *cur, struct bpf_verifie * no need to update cur->loop_entry. */ if (hdr->branches && hdr->dfs_depth < (cur->loop_entry ?: cur)->dfs_depth) { + if (cur->loop_entry) { + cur->loop_entry->used_as_loop_entry--; + maybe_free_verifier_state(env, state_loop_entry_as_list(cur)); + } cur->loop_entry = hdr; - hdr->used_as_loop_entry = true; + hdr->used_as_loop_entry++; } } static void update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifier_state *st) { + struct bpf_verifier_state_list *sl = NULL, *parent_sl; + struct bpf_verifier_state *parent; + while (st) { u32 br = --st->branches; @@ -1862,7 +1914,7 @@ static void update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifi * This is a part of 'case A' in get_loop_entry() comment. */ if (br == 0 && st->parent && st->loop_entry) - update_loop_entry(st->parent, st->loop_entry); + update_loop_entry(env, st->parent, st->loop_entry); /* WARN_ON(br > 1) technically makes sense here, * but see comment in push_stack(), hence: @@ -1872,7 +1924,12 @@ static void update_branch_counts(struct bpf_verifier_env *env, struct bpf_verifi br); if (br) break; - st = st->parent; + parent = st->parent; + parent_sl = state_parent_as_list(st); + if (sl) + maybe_free_verifier_state(env, sl); + st = parent; + sl = parent_sl; } } @@ -18618,7 +18675,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) spi = __get_spi(iter_reg->off + iter_reg->var_off.value); iter_state = &func(env, iter_reg)->stack[spi].spilled_ptr; if (iter_state->iter.state == BPF_ITER_STATE_ACTIVE) { - update_loop_entry(cur, &sl->state); + update_loop_entry(env, cur, &sl->state); goto hit; } } @@ -18627,7 +18684,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) if (is_may_goto_insn_at(env, insn_idx)) { if (sl->state.may_goto_depth != cur->may_goto_depth && states_equal(env, &sl->state, cur, RANGE_WITHIN)) { - update_loop_entry(cur, &sl->state); + update_loop_entry(env, cur, &sl->state); goto hit; } } @@ -18700,7 +18757,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) force_exact = loop_entry && loop_entry->branches > 0; if (states_equal(env, &sl->state, cur, force_exact ? RANGE_WITHIN : NOT_EXACT)) { if (force_exact) - update_loop_entry(cur, loop_entry); + update_loop_entry(env, cur, loop_entry); hit: sl->hit_cnt++; /* reached equivalent register/stack state, @@ -18749,24 +18806,10 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) /* the state is unlikely to be useful. Remove it to * speed up verification */ + sl->in_free_list = true; list_del(&sl->node); - if (sl->state.frame[0]->regs[0].live & REG_LIVE_DONE && - !sl->state.used_as_loop_entry) { - u32 br = sl->state.branches; - - WARN_ONCE(br, - "BUG live_done but branches_to_explore %d\n", - br); - free_verifier_state(&sl->state, false); - kfree(sl); - env->peak_states--; - } else { - /* cannot free this state, since parentage chain may - * walk it later. Add it for free_list instead to - * be freed at the end of verification - */ - list_add(&sl->node, &env->free_list); - } + list_add(&sl->node, &env->free_list); + maybe_free_verifier_state(env, sl); } } From patchwork Sat Feb 15 11:04:01 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13976039 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f171.google.com (mail-pl1-f171.google.com [209.85.214.171]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 7954F1A2385 for ; Sat, 15 Feb 2025 11:04:41 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.171 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617483; cv=none; b=rXpQrAxvMrHV2LcP0RDkjKTJCTokQWnMZzJY4AjQd73u7z6JKRhBc++KChgyCb3kUJI3kwHsrXb/RcysbD32MMAERPxD3DK5By3Md+5lCJ7E9fv7FRr54j8Virom83rg1dc95UyYGaBqck2ncqz6Va245Cdrpmaz07qikxtC1ho= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1739617483; c=relaxed/simple; bh=KjcnHc5O6yZ6ppWi6UYnAuBXdE/nWJsH0bTv1HOHTik=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=MAkZmrIWnYRyExqEedJotA7oIrDqU+zKEFAulRlvGe277RtLmFx/BW8NJSkJbrQg80pXfSIYm5RPFB3BM/AG9Jfjm9fEIwqt0DR3tGw1T2jBp+xC9/bhv58JRPR7RD3Ay2dCzoN39eaaaE4m5YMlqgOpiS1y5DoSGMHnw0MDeP0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=ZanGhunS; arc=none smtp.client-ip=209.85.214.171 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ZanGhunS" Received: by mail-pl1-f171.google.com with SMTP id d9443c01a7336-221050f3f00so8520025ad.2 for ; Sat, 15 Feb 2025 03:04:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1739617480; x=1740222280; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=vaPZFkGYvP5xO3AbmsaBLhATdZxWoTWdvu2m54yy0IE=; b=ZanGhunSFN3S6MYe7zEA7pbJKeebAZWOa+btW2tWouhZkArUICpbV2ziNJ+3IWtvZA QbvJJbF26CeQuSMDiuPWFo01YEkAX1Y2qAzXB7WA5Z7ZuJ6kXCC/Df2aS9dbNL+3RZ3h N36rcoDOWp2V71VwfHDLSEWIXaCqaTrV4q0KYNYvMZT3TPimmmw1vy5RNULr2A2d2Rw4 fz6XcWVDRGDIQoK2mPTlm1DEcqsGaYmV0KCJvjR+e+b+jc2XtvBOAbSrcrkqJKv70mgX VxV1q+t8zX+y79pAl0rAsDOEOPPsgt9g5wNmLBndWY9ZkpDjoB8UisqoWgGZ21Y+A2BD wfQQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1739617480; x=1740222280; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=vaPZFkGYvP5xO3AbmsaBLhATdZxWoTWdvu2m54yy0IE=; b=qevB/cdKlAkd+AeAukFIKVrP+E4p99gxIvRvuyxDA45YBw3PKBUka1QWobVyDiZg6E TwlJaSoQdJcbcdMZ/Lke8XSqE2f68pgRhollRiZfji2OwoNw3kDUmhVvvnuTsnqpUELG C2dRg6k8/nBcQe3+Bp4g4pcJtt57hetEBrMParO7NGDNjZxK82hqUPLOkjBFPTSfXEF6 D63aFAUMtPXSrl7AA8oYsUkjnXyF5DW5ynm88H5M8TBD8fB1AgUanlTFvc/YtINVN8eg PC9jrOmO92feSWd/6YAUW16g9uIiR+hjuoXl0rKtm8Um91lqrX2PIftTC/+/8WklQyR1 +reg== X-Gm-Message-State: AOJu0YwAZAqHPsLjCcTwZwAPc6EcXmJqC15TlNbJFzKzPBoI5ggJk99c Xqd6zxgenJ+sPXty/J/FOfVAQa4UFHyHnD0tkSoJq9p5X0ugKuiEqVISUA== X-Gm-Gg: ASbGncvJa8G7o980z1nCBZghCJ4Udp6XB+No32i6oMODZJU+GQtXeC3BQSIMBu9TO60 GFO8hu+MyHeVbQ0XxxlIYcksSGib8waMBm/iO+dSIXKAO4Q5eW84HmUnrVRECx1CogfeUkiOrnM L+lh7wzrZnhcVgNP9IY9TC9vajpnSJeA5qt3tnQCjyh/toBQO9Y43qeOC3wcTGQi2ePKmD/UpJT qmc5oZFNFHNq9aai11cib2DsThI1y3ZgGJWMFhtrPfeC058OgXRNilicf1xN6xqYxq+0X0d9QSw D7jPGbAFjO4= X-Google-Smtp-Source: AGHT+IHS1L2hwnJZ0t4yRPC354bW8OH3WLRedIoGORTfHaV8io19mY2P+H+yvQkVNVe7qBTB2MU6BA== X-Received: by 2002:a05:6a20:729f:b0:1e1:a716:316a with SMTP id adf61e73a8af0-1ee8cb5d182mr4819128637.10.1739617480457; Sat, 15 Feb 2025 03:04:40 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7326d58d4d0sm72435b3a.94.2025.02.15.03.04.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 15 Feb 2025 03:04:39 -0800 (PST) From: Eduard Zingerman To: bpf@vger.kernel.org, ast@kernel.org Cc: andrii@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev, kernel-team@fb.com, yonghong.song@linux.dev, tj@kernel.org, patsomaru@meta.com, Eduard Zingerman Subject: [PATCH bpf-next v1 10/10] bpf: fix env->peak_states computation Date: Sat, 15 Feb 2025 03:04:01 -0800 Message-ID: <20250215110411.3236773-11-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250215110411.3236773-1-eddyz87@gmail.com> References: <20250215110411.3236773-1-eddyz87@gmail.com> 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 Compute env->peak_states as a maximum value of sum of env->explored_states and env->free_list size. Signed-off-by: Eduard Zingerman --- include/linux/bpf_verifier.h | 2 ++ kernel/bpf/verifier.c | 15 +++++++++++++-- 2 files changed, 15 insertions(+), 2 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index f920af30eb06..bbd013c38ff9 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -772,6 +772,8 @@ struct bpf_verifier_env { u32 peak_states; /* longest register parentage chain walked for liveness marking */ u32 longest_mark_read_walk; + u32 free_list_size; + u32 explored_states_size; bpfptr_t fd_array; /* bit mask to keep track of whether a register has been accessed diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index eadd404ab9ab..b92d5eb47083 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1598,6 +1598,14 @@ static struct bpf_reference_state *find_lock_state(struct bpf_verifier_state *st return NULL; } +static void update_peak_states(struct bpf_verifier_env *env) +{ + u32 cur_states; + + cur_states = env->explored_states_size + env->free_list_size; + env->peak_states = max(env->peak_states, cur_states); +} + static void free_func_state(struct bpf_func_state *state) { if (!state) @@ -1659,7 +1667,7 @@ static void maybe_free_verifier_state(struct bpf_verifier_env *env, list_del(&sl->node); free_verifier_state(&sl->state, false); kfree(sl); - env->peak_states--; + env->free_list_size--; sl = loop_entry_sl; } } @@ -18809,6 +18817,8 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) sl->in_free_list = true; list_del(&sl->node); list_add(&sl->node, &env->free_list); + env->free_list_size++; + env->explored_states_size--; maybe_free_verifier_state(env, sl); } } @@ -18835,7 +18845,8 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) if (!new_sl) return -ENOMEM; env->total_states++; - env->peak_states++; + env->explored_states_size++; + update_peak_states(env); env->prev_jmps_processed = env->jmps_processed; env->prev_insn_processed = env->insn_processed;