From patchwork Wed Jan 22 12:04:36 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13947211 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f175.google.com (mail-pl1-f175.google.com [209.85.214.175]) (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 9F5A3211A2D for ; Wed, 22 Jan 2025 12:05:02 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.175 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737547504; cv=none; b=HSWnzLWbeVi0Eh6HK795VtURvFigypa5Ze3guXjBH6EdLIkVBUFyHjWS7MVfJwcBGa+wF76TbkTmqjoAlIHgUq2cujU3QclxraaTBeBAM1L6yJ3NthLkxzQIrzG+XfJzy6wBKiUc54wK7S1Gm4zk3acQt2qJiYRHVJaQUs+9X+Q= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737547504; c=relaxed/simple; bh=jMTSymEefxUmchMhlprnFt1mX/c+7lNsFNWcUW8Y12c=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=ENanmK8JnJpwhAN2wfECAeKr2NCoxtn1MKFpp48dIAPH/a1Ei5I88MPj/X1ICHwDW3joxt7RJQr3ZjceF0oG9XGFITcxxoHS6D85+px2Iq3v/249goO2co5icrgZkfrIFO0zH9SORzqYjWbvNWHEaGVa7Y9ntumit0tJ7TMObAQ= 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=T5G1WLIq; arc=none smtp.client-ip=209.85.214.175 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="T5G1WLIq" Received: by mail-pl1-f175.google.com with SMTP id d9443c01a7336-216426b0865so116489805ad.0 for ; Wed, 22 Jan 2025 04:05:02 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1737547501; x=1738152301; 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=W9m15PhxS3SDAVDAGndcYvrgTV4MB+kIx+3mFednYfY=; b=T5G1WLIqclimidfxe/YlJUCvGAHtmVUpGI2HzlqycHofko3otmUHUl74ni50/5VnBU bXjWQ8tL0ePAfHsWqXvDyIhyX9u9i3Mit1IKcxrWozY7gaxYrxjty4ilWWiF+GTcZI3x rNMCcN6XPpBsezpY2PpVUmCae7lqfwf20mUjNEEvJsS78TbHHoruq9aohF7/NMFDjzC7 BKGTHYLF+bCNDkOqNz5EJkc64POwvBp3k1l2nlCznc0Z+eAZWfn4ykD/iO1Wri1WuLAX S0ZFRJB8bGjnwOXtJo1hXvXl2aHvQZTuuNDL3DhVzZx2CDxNwGiaBJDSoszJLCWqIPRi x8bQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1737547501; x=1738152301; 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=W9m15PhxS3SDAVDAGndcYvrgTV4MB+kIx+3mFednYfY=; b=OKJoX5J++NWN5ycAnM6aEjwso4M/GoWw+m3Mt3IhOcFzxcK2XEASygcHIW+UDfLxr7 kPRuQKGvZ0uLLPYglByKDWcI0Xf/s2oyk6LNsJYzasjRKogRRvJrW8Vd9fBRXhVt2FtO MO6qIiVhY6RjQ0JqU7UpOb0k2gHYqAkeosRP5LwdCKcB8s6PTJMAn5O5XqLroMOpb/4Z VDFYo8b//qlvL+1jyUf2Pk7q2P9KI69efsKtf5j0OmDyACiyoUk/MxmNlaU6zUd0QvpT dDwQuQ4flcsIZpa9iBZDiLJngg7IbomuHjCiPPxev0ptpoU/J3w1/7S+PsBDDLcufxs6 3w3A== X-Gm-Message-State: AOJu0YypP3E6RBGGjvpF61loAG64WackvchSFcpS2gv9+ZhzTLugua9d iAc+5axZxZGFJfpauT0QWFMD064PL/u+V6SNRq4dYEa/WNQqprCt/eoNbA== X-Gm-Gg: ASbGnctiSa+urQ5Rx6bvsSbL+FK1TRuOpW9vkxPs3BjLW46v89oaEvMVEfpRqRx1pw0 LBFEWhlqBUKhxGuRhMvI90Vq/IsOiFx0Lo7Rg/e8/SVyrmtt3FeL8ToM5zJWYfDJrEnjmtevHES OP2bhcYQPsyBNJPL4dwo6afo1PZUzdicODgbQJYyldTCOhIAIaPvRF44AjgR/KG8OR/m+tKyVtw UnBPvHwhJaDnIcMLBrpmzGoT4psIyW0ds6ax+bVAPsPVU1s0Wf/3fxUOHzS754Npw== X-Google-Smtp-Source: AGHT+IEuVv6JUZcG36U4wsUrBi3hKCII5MN2lF36yS9K5xDrERtnoimzZePGhe/9V0h3zDxvqvQe5Q== X-Received: by 2002:a05:6a20:841c:b0:1e1:ae9a:6316 with SMTP id adf61e73a8af0-1eb215ec18amr38956730637.35.1737547501435; Wed, 22 Jan 2025 04:05:01 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-72dab816412sm11055732b3a.66.2025.01.22.04.05.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Jan 2025 04:05:00 -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, Eduard Zingerman Subject: [RFC bpf-next v1 1/7] bpf: copy_verifier_state() should copy 'loop_entry' field Date: Wed, 22 Jan 2025 04:04:36 -0800 Message-ID: <20250122120442.3536298-2-eddyz87@gmail.com> X-Mailer: git-send-email 2.47.1 In-Reply-To: <20250122120442.3536298-1-eddyz87@gmail.com> References: <20250122120442.3536298-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 X-Patchwork-State: RFC 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: Program Insns (DIFF) States (DIFF) ---------------------------- -------------- ------------- arena_htab_llvm -291 (-40.59%) -20 (-35.09%) arena_htab_asm -152 (-25.46%) -10 (-21.28%) arena_list_del -30 (-9.71%) -9 (-39.13%) checkpoint_states_deletion -5 (-0.03%) -1 (-0.12%) iter_nested_deeply_iters -26 (-4.38%) -4 (-5.97%) iter_subprog_check_stacksafe -14 (-9.03%) -1 (-6.67%) iter_subprog_iters -91 (-8.32%) -5 (-5.68%) loop_state_deps2 +246 (+51.36%) +17 (+36.96%) open_coded_iter -4 (-6.35%) -1 (-14.29%) on_event -320 (-2.59%) -80 (-18.14%) big_alloc2 +7 (+0.24%) +1 (+0.65%) max_words -8 (-8.70%) -1 (-12.50%) cond_break2 -6 (-5.31%) +0 (+0.00%) And significant negative impact for sched_ext: Program Insns (DIFF) States (DIFF) ---------------------- -------------------- ------------------ lavd_cpu_offline +4 (+0.09%) -1 (-0.32%) lavd_cpu_online +4 (+0.09%) -1 (-0.32%) lavd_enqueue -4 (-0.08%) +0 (+0.00%) lavd_init +7684 (+109.40%) +649 (+133.26%) layered_dispatch -937 (-8.16%) -86 (-10.14%) layered_dump +992580 (+13375.29%) +30497 (+4478.27%) layered_enqueue -2733 (-20.91%) -260 (-22.07%) layered_runnable -435 (-13.52%) -38 (-12.88%) refresh_layer_cpumasks +658273 (+3992.68%) +63600 (+3593.22%) rustland_init -22 (-4.42%) -4 (-9.76%) rustland_init -22 (-4.42%) -4 (-9.76%) rusty_init +1917 (+12.72%) +175 (+22.76%) rusty_init_task +135 (+0.32%) +10 (+0.45%) rusty_select_cpu +75128 (+3580.93%) +5807 (+3208.29%) rusty_set_cpumask -15799 (-78.00%) -1349 (-81.02%) central_dispatch +2051 (+322.48%) +164 (+260.32%) nest_init +179 (+28.14%) +13 (+21.67%) qmap_dispatch +1187 (+49.60%) +57 (+29.08%) qmap_dump +85 (+36.48%) +8 (+36.36%) qmap_init +1069 (+6.53%) +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 74525392714e..c7ceb59d3a19 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) { @@ -19230,6 +19231,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 Wed Jan 22 12:04:37 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13947212 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f180.google.com (mail-pl1-f180.google.com [209.85.214.180]) (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 97B45212B07 for ; Wed, 22 Jan 2025 12:05:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737547505; cv=none; b=NfoqKZw6TMmhRQ1QCFjwAa+Sc65f/ufdfTE6PiuQjCRpRdmsf/LT+LL9VQ3lzYVXdTZPYsjK+pwpSZIMhbnWlH7dhiCq9CXAzbzI5xRx16SnMfdl4wPyEFGVQU043bIKeEx/pLT8ho8Vz1eJCVM0/izD/g05rDuNtt4rarJ0QGc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737547505; c=relaxed/simple; bh=FQ/lQu77KXi9PFSk4G0j0T9pJCUkHBi+terX+pGUIgY=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=Fbo3MRX/VI51uWomQpm53obhtYxqabA1X0NIby9XuOE3oxAb/+v2TrzdwvCKqcAR/Ly08Mho6p4JWox8DhgRc0/LoSYF5HlT0v/cW8ZUMrfQ3Vuak4GVN5lzZ6j4hMT8KuaZ4avhG2Vm1hUiSwKYZOiI/RNS8tcYU9zG1D7ia6I= 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=cYcKsw1A; arc=none smtp.client-ip=209.85.214.180 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="cYcKsw1A" Received: by mail-pl1-f180.google.com with SMTP id d9443c01a7336-2162c0f6a39so14258975ad.0 for ; Wed, 22 Jan 2025 04:05:03 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1737547502; x=1738152302; 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=LEfktsTz8lBKgBrczz+acAgFgdtAgvpRqhJLsD4UUVo=; b=cYcKsw1ARfHGkEj/Bk3WRo5NkYdCBL/GRfYa+Y16f0xHVyDyAgfRx1vDgtDdHoygc0 gls4OmRDWrbWpkCWrTSbuU+LCeQWzfbhUqe7k+a66qlj1bWJBQvFlJqUw0CUe6c/poDh DBPAWyAVY3CxKcg1ORj36PU+Oq2CRi8pPaBCHjQiZezGMpUw35dn7c+Vyygzsf5n9qGU nEaw7e7owXJmN4wBfy31+0A9jzciyp/XVZv6J1ULgKr/LsNFjOunEsEJGsPOIqRuD/J9 4/Q0CNLbHriywwKSBPGb0gdfhFNdL2dXdyDza8/v1ds+0GJ311bRPBO0XhpBSYfksb9f 0D5w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1737547502; x=1738152302; 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=LEfktsTz8lBKgBrczz+acAgFgdtAgvpRqhJLsD4UUVo=; b=cC+oCjEqTS6Xr2stPHiMMhDa5ENerB97vLSsk+pAh6h7KbgQyB7gf7R62w+pOjLpIr CNeUr6YUHWSLQLR5np7XDVwqgQ/3cOWK8T6gHWe44bAXpXmxnzllB2uhu47skEQCZYUd /omhSerif/7YIzoM3LJwutzpf1GIIIqCjh63aqKEvhdeTmCzeVCvSX6mYzBoFzTQNise ymHBCmZ4IdykVQPwZsvQHCnsUgl7tkALgt7s0wpcCJZeOA/127cnwBf+fDOWjkiD6jUP 1yLxsvqymDKW9vag8rzb6aqHLT2NfSrm8gnNR91L1etOJZ/DdUxV4xYzP/8zH1k5EWP4 fBAg== X-Gm-Message-State: AOJu0Yxu4a+nzucHDg+5vYQldawahjUgh+cbsSmRhZgIRZDGOeffiDMj b++t4fxjXFxWwK2wUqCeMFXPJlD1d53lShQVJ1ycn2b1Hmljgy/KezG61g== X-Gm-Gg: ASbGncsO+gqnSUEbnx1RBSrucQ7yGBDFBGYC2UIfrFcVG8NJySAQQmv/6rXr1Jer2xf /n3i35mVUJvKe9Dj2y7AnHVmAOH0PsdVKMlYKmmJ6wyj8BSWY51NC2Xg1YRIG7HHNPGwlqswN0f POrgOAAzed+R1SMxyvBfuOmUB0PtTKAzurAaPTU33S4ohBSd45WZb0jxSmMGq7MN6e1RiqtC+7w H+Jc30IQzWMg/cT7JjV7qrgxxKakHn8ZXNQB2dty7QU/zVK/GgG+jgi604EEDiK1w== X-Google-Smtp-Source: AGHT+IGjlfBfl3sMDHube0HR6woo6cHj6KuMEXa6BWfzbmQVgpmC6JLj/j+Bs21ZMOBy140/O9Eaog== X-Received: by 2002:a05:6a20:2453:b0:1e0:d3e9:1f8 with SMTP id adf61e73a8af0-1eb216294admr29387428637.10.1737547502512; Wed, 22 Jan 2025 04:05:02 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-72dab816412sm11055732b3a.66.2025.01.22.04.05.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Jan 2025 04:05:01 -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, Eduard Zingerman Subject: [RFC bpf-next v1 2/7] selftests/bpf: test correct loop_entry update in copy_verifier_state Date: Wed, 22 Jan 2025 04:04:37 -0800 Message-ID: <20250122120442.3536298-3-eddyz87@gmail.com> X-Mailer: git-send-email 2.47.1 In-Reply-To: <20250122120442.3536298-1-eddyz87@gmail.com> References: <20250122120442.3536298-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 X-Patchwork-State: RFC 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 Wed Jan 22 12:04:38 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13947213 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pj1-f41.google.com (mail-pj1-f41.google.com [209.85.216.41]) (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 A6075212B14 for ; Wed, 22 Jan 2025 12:05:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.41 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737547506; cv=none; b=NdxA/VcR9rypS/jZok8odwjio769cjPrXzCdCxik6TrdrJX5UlHxeQLb9KYKQDqaQtYu3TFm/ZPEdwziN0kKG61L/FQ2mw15saWs2v3kP5CM4vL1SOCMCR1i4JMGRAfWvDSlPJRF0Sm1oerkZHQD3hwD3ypnDU8l6ut/ikhnF0I= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737547506; c=relaxed/simple; bh=cYYfh13zoiuouqQ3GjfIjGgTjjIH5PgBdU03m4vsMHA=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=JRHMnoaPahAAcNjRlCHxGRBKWY1CrVBFjevgTrbvDHFtjWRzjYrEdW4VbWWQ0oqCKILcr2AIuFQAElzMr/xU/+cPcDCBomp3kwfabVAOmChWpJTUZTyEYgF51PBvTOycEqkdJoM/daKVZoIpYzxqipvmt53WMtE73bu0eittbxk= 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=WY6y5Azy; arc=none smtp.client-ip=209.85.216.41 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="WY6y5Azy" Received: by mail-pj1-f41.google.com with SMTP id 98e67ed59e1d1-2ef87d24c2dso8932407a91.1 for ; Wed, 22 Jan 2025 04:05:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1737547503; x=1738152303; 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=jr6Xk5Yu/6fmW4G5zgRffPcow/7eTHW8sKlPQZSp8VU=; b=WY6y5Azy5oDfv4eFlCyHK9cvbpHLfh2Bgp3LiUYtwhKOQnRJWBVYMHFnGSJ4k5Z/9L ASCYOC6XbwjWd4RslXp7uFU2h88SHXuEruRWfQt0+oj5dicLWp//yWp8CeHsoRDpDfSY gVesKEJk98B++Xyrczdqni92sbFo0975mcJpuTDCcw+F9Komo23DXkdr6N3UtRbYyXhA TLnNbDud8zYi73c8owgViBPAwCKBD4D5o2f/YOoRSVQN02+Cq2sByyvr5W9cUvlZsgWF YsXiNNSfOG/8+UmX2dn5RQX9qq8wsjJup+3rv/gd1UkwGG88O6ZB2upu9/ER46ILdjEz Iq0g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1737547503; x=1738152303; 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=jr6Xk5Yu/6fmW4G5zgRffPcow/7eTHW8sKlPQZSp8VU=; b=NpW0X9tE4MWcYHngIgCMlUfLDeZbqhSnI8JaWtydQZYC+WoaxoaE++uZ4hKtrdJ1OC CQ2amOqYmyYRc3ONCtbfEIi4QewkJaat4o4JTmIdHBlmb5KQEP5tn/DEtLKVHdV20GcL A0OSsikqIMoZzdZ8uWB39E11zmoOHK5RuoMuJlRczbqxjsgme7iK79qgL08WdlNqvjyv DTHbBYAFApegWwuu8V+zBNxH7wEakegDME04E7Uu8t1EERYdrQ/t96JaB3sDB51QGDqs 5jEdSi5vUI3jSprIq8oiVcK0q3mT1uOP6HkfNFHpVRYTm04DyZNLGKFBimewsW1zWqFX 4R/w== X-Gm-Message-State: AOJu0YyIDw84nFeyhyyPMUFYFFw9H2Wn3Z9XKha5RDrXCiGIKlbInbch CjbfXm8OpcN5JlGovM31uVEQ+T9FDq+/x2usAfRtfQbPcOuPzi9b6z4Ogw== X-Gm-Gg: ASbGnctmjVqAXGnEmSPbZzh8fu8GRm0wNX0waoWBvHwf0PnTFcovfelqKrHsY+gYPs2 ljLtm78o+81qS04IT9pSQPXBdqAos/aMqr9URoDQzueDy2FjXCRYShBJY2iQQhFQmM6k36phe8H FoffwIfD8pNymPb1thdws+fTkY/8wHqEniRZTqSVDdBhYuyR6M8m0KecZn74T5OFA8gtaLCPVYW fAqwopeDV/MtHFxT31T+D6wTr3B2Wp6TBz6dWj0kLcfh3AhK7frFhOjWImEpCXaIA== X-Google-Smtp-Source: AGHT+IHWZ6/8YpDT8Blilce0frjQyVCM+SdsIYzih/z2p2hb7g5y4XaTaj8r1mr5HziXdKgociZk5g== X-Received: by 2002:a05:6a00:428d:b0:725:ae5f:7f06 with SMTP id d2e1a72fcca58-72dafadbc37mr29955546b3a.23.1737547503450; Wed, 22 Jan 2025 04:05:03 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-72dab816412sm11055732b3a.66.2025.01.22.04.05.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Jan 2025 04:05:03 -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, Eduard Zingerman Subject: [RFC bpf-next v1 3/7] bpf: don't do clean_live_states when state->loop_entry->branches > 0 Date: Wed, 22 Jan 2025 04:04:38 -0800 Message-ID: <20250122120442.3536298-4-eddyz87@gmail.com> X-Mailer: git-send-email 2.47.1 In-Reply-To: <20250122120442.3536298-1-eddyz87@gmail.com> References: <20250122120442.3536298-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 X-Patchwork-State: RFC 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 (DIFF) States (DIFF) -------------------- ---------------------------- ----------------- ---------------- arena_htab.bpf.o arena_htab_llvm -294 (-41.00%) -20 (-35.09%) arena_htab_asm.bpf.o arena_htab_asm -152 (-25.46%) -10 (-21.28%) arena_list.bpf.o arena_list_add +329 (+22.04%) +7 (+23.33%) arena_list.bpf.o arena_list_del -51 (-16.50%) -8 (-34.78%) iters.bpf.o checkpoint_states_deletion -8297 (-45.78%) -451 (-55.13%) iters.bpf.o clean_live_states -998653 (-99.87%) -90126 (-99.85%) iters.bpf.o iter_nested_deeply_iters -226 (-38.11%) -24 (-35.82%) iters.bpf.o iter_subprog_check_stacksafe -20 (-12.90%) -1 (-6.67%) iters.bpf.o iter_subprog_iters -286 (-26.14%) -20 (-22.73%) iters.bpf.o loop_state_deps2 -123 (-25.68%) -11 (-23.91%) iters.bpf.o triple_continue -4 (-11.43%) +0 (+0.00%) mptcp_subflow.bpf.o _getsockopt_subflow -55 (-10.98%) -2 (-8.00%) pyperf600_iter.bpf.o on_event -6025 (-48.83%) -160 (-36.28%) (arena_list_add requires further investigation) sched_ext: Program Insns (DIFF) States (DIFF) ---------------------- ----------------- ---------------- layered_dispatch -3570 (-31.08%) -227 (-26.77%) layered_dump -2746 (-37.00%) -411 (-60.35%) layered_enqueue -3781 (-28.93%) -341 (-28.95%) layered_init -994488 (-99.45%) -84153 (-99.39%) layered_runnable -1467 (-45.59%) -160 (-54.24%) refresh_layer_cpumasks -15202 (-92.21%) -1650 (-93.22%) rusty_select_cpu -647 (-30.84%) -53 (-29.28%) rusty_set_cpumask -15934 (-78.67%) -1359 (-81.62%) central_init -330 (-36.18%) -10 (-20.83%) pair_dispatch -998092 (-99.81%) -58249 (-99.76%) '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 c7ceb59d3a19..1c2199a3f38f 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -17801,12 +17801,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 Wed Jan 22 12:04:39 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13947214 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 84A61212B21 for ; Wed, 22 Jan 2025 12:05:05 +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=1737547507; cv=none; b=HptauAB6evIkYo/ezuPQLwKAbyeu0lGvzWmkl1y1FlNc237FkiBRipVSCq/T6/qHT9QTeNA9rnhnluyw0KJz3Bt+1keWjLxLEGSr4AGeJaDoiKG5IxRozecdrHwF20JS1dYHiocoLGGE/+qOePuiUWhk1Mn2cpyWzHvBO8Jd/9E= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737547507; c=relaxed/simple; bh=U9VjoVwEI1GZDWJL4gENnlWoZSf/vyvnLCIilsG1aYs=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=NlCgCy/UuM3/lYlW2ySgcSYoggHJ4xV+UbH0Z4KB0sjGMAEQ9AAqHYmqzzY4n6COsielao2LTz1rnRFvX/iinHm431lLpZD2q7RsHwVCD72f1xxmYWAgKgJVBIsZVMH7QcJSJziUPAvMRz23lKOqv6PjEOXCa9oCtBt6S/VdQa4= 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=gLwwr70O; 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="gLwwr70O" Received: by mail-pl1-f174.google.com with SMTP id d9443c01a7336-2164b662090so124689905ad.1 for ; Wed, 22 Jan 2025 04:05:05 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1737547504; x=1738152304; 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=IQpN9Raq9KxubRV4TgvIOLOIn0GGWFbmG8pxMikfG8I=; b=gLwwr70O56QXKR/V1n/1e4uGvY475fAg5ecG/wTPv5ecpvtLcHIC8Qein8i2lprr3z GxdEFbs3tLp4dOEMQETVHIulQJs06paCdQuAAuqVU/ZCV6daaOGy9s3nh8BVOKmFCPEO boMFGT95Bn57PW5HT5nO6EMarYvTFJGpN/Zojy7GxKJxebX7+yPzpFy27ekXx0xTo5Yf ePWrMp9t9RP2oSVURcXZJH6lBGHfN1iP+Gov3LV3p0O/BcoXsjQeuWlNDN9CH4gIBsbi wtlfwB9sNuG0Hq/1Z1Jk8RtWKE0vg6Zq1is00KFEtBqZMAh6bV4nGtwfO3Qqy53I6qej MzcQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1737547504; x=1738152304; 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=IQpN9Raq9KxubRV4TgvIOLOIn0GGWFbmG8pxMikfG8I=; b=BC+2TzTlhk0FC6KuC4/Jkt7KDeRnLX1hY33rP1uAAy39cAA+JVCmOGtJ5ZeYEU3a5H fxdc2MHP8fn6VqSjdmWce1REGM/BYItXWymJukttwHYEXjGC87CCe0fwqoaPb3mkKkv2 FqWmeKYxloebiqjgPntjXeUEIk/CIk/a4q0SU2w1qN3w580KVZVR9FBVCfkWGK655Lv2 YYXgDnTaWDNmgZMo64kOfd8Bmyb+fx45e1+NniacnFAQ+6yVa3+sC3V5Kk18p3FK52Ij Jb5lCy5Tscd42CplvNXu3OJjv+aK9RSiR3CIuRe0uQ4yDVnxoa8FYPyic+VrGKfdrmay jCdQ== X-Gm-Message-State: AOJu0YxRz1IYmiBE+vAnfRbeeVgD8iXWV7QG/o/StPFMYtnd+bDVKBnz lG8HpNSC/tIzCMj1O5JoAWPUOw1GFPMLaWCnD8F841olDHhAf2tr2te/ZQ== X-Gm-Gg: ASbGnctg5b158bwbmvK2uerve2DeMqeI1sbyyM3lPRFgE3+qdLXSG0rZ8D5fF0miYA8 pCxXfGdFsbAYywTwhOoWKwXcYuWitKDf1B/lchQnTtQS2LxRKtRTX1t+D2/ZygPtcpyCSg47eLS Svmz4tHaXa2sHlbgcX4fW6wY20UigVHSTqBNGUKH5QK53IfPik9dnPQV4XiXEUxcGQGoy5wfKf1 dEW9Dziy5Fmo3VieC5ODNqskXEuy0sxsrqJiX3gx/iRBnqoBwue5K0BcYSjbKDT2Ehu/HVe16aN X-Google-Smtp-Source: AGHT+IHVilZvItZYziHNTbi51M19KlmBFq2SG8tK75MkQvEdvulBfNrdaNwhXM44SMhZLLhH6Jr/9g== X-Received: by 2002:a05:6a20:cf8e:b0:1e1:f40d:9783 with SMTP id adf61e73a8af0-1eb215ca197mr40439596637.40.1737547504468; Wed, 22 Jan 2025 04:05:04 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-72dab816412sm11055732b3a.66.2025.01.22.04.05.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Jan 2025 04:05:03 -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, Eduard Zingerman Subject: [RFC bpf-next v1 4/7] selftests/bpf: check states pruning for deeply nested iterator Date: Wed, 22 Jan 2025 04:04:39 -0800 Message-ID: <20250122120442.3536298-5-eddyz87@gmail.com> X-Mailer: git-send-email 2.47.1 In-Reply-To: <20250122120442.3536298-1-eddyz87@gmail.com> References: <20250122120442.3536298-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 X-Patchwork-State: RFC 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 Wed Jan 22 12:04:40 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13947216 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pj1-f43.google.com (mail-pj1-f43.google.com [209.85.216.43]) (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 91724212D60 for ; Wed, 22 Jan 2025 12:05:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.43 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737547509; cv=none; b=l6G3QXsmUePYx96Se+NXsLSFyub6ReMJRm/p8jDmgwadc7L1zlIqxeyQoiuA71SDHBX+Rsy2p6LbzqTJ0BOdAtmky2wYAu1k3bfwfXniVVlhPlQaWoYMLvtvHq9Vbo3e/tl6boDNA1phvD2hGARrIHd1R5GRcMg8zC0zw3fcjuE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737547509; c=relaxed/simple; bh=eXvBNDxWQXxp4P3J/r71Hi2RVZk6Y8EC+RH2KpizEL4=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=lhGnY+Uk1iWPaNIuWCI153yLteS5RL//MaFZdxr13CWinayfm6pVQ8NA5cz6rHsyM/Uh9uUJjrSvkKCo9VCgYgpbrYw16aFgZXrgG9jTuL4xl8P4XKCrJ7upNtJx6mOIIqI2jFcLtE5EMSfgpEpfd3Quli1RUOBBavIl3t9zhE0= 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=RDeuwyv9; arc=none smtp.client-ip=209.85.216.43 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="RDeuwyv9" Received: by mail-pj1-f43.google.com with SMTP id 98e67ed59e1d1-2ee709715d9so9475935a91.3 for ; Wed, 22 Jan 2025 04:05:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1737547506; x=1738152306; 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=QZf3ecuWIOghN+lgZSZBs7yqr/8ijf2Yq0vtSSWuFt4=; b=RDeuwyv9bIAs0EAFdBtskZAWGEwBcAjTMksVRddNYrbUpP2Vfp/yYWKDMK7xMarjeK N1yCBahnLP8rN9PMqLXLvCJpk2ibS0qBnFyfX7GUZacy13846TVoU9uDEsbUCgdqSpzK JJr87tZyens7m0/dYfY1HuPFguG6DbrUFiatkUM/+HDCdScTV0yR+TkP+i8bkjiJoJXM VULxgriXzhboHGF9LCGg/SbGFVPuymEchVAsZPE5JdfMZIt0Qs3SPu9Udc6kvtieT5Sh KaszZR35JZO/tLgK0h72OpMi+bYaflvvct5tYxdGPqfewytbkGKD5dP52644jf9t/UpP +Vvg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1737547506; x=1738152306; 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=QZf3ecuWIOghN+lgZSZBs7yqr/8ijf2Yq0vtSSWuFt4=; b=wvkCuiUFOQNkAxkT4KVmGbG9JaY3Mc50HzFibYKfr88Mx3UwgxcE7Qca7TJFRQDkGS oYpOZUhmHg0KOz/x2V0AXlSkihryHDUZZ7mfnfdM/WlmXlzx+NH71asJWOAq9D/yMpl4 HGxUV58l6vTxn8s7HFDU9fZWihezqmPm5Wr2H8z/GpeTXQxSz7LKDF48DIE0An4iqmFW K9bOhKdfnH36A2suZ9lP3cqVVVMsdPETQb4zOLOD0ju/zp4K470dgDsj8m7CbL/DXzyR rNwmU+ID9tvaKHLQXwEoqNz2PPn3vhJyNj3IMscKVgBP1X+cURT+P+HweUCoulkGdOBG C6XQ== X-Gm-Message-State: AOJu0YxYbpgVF5hO+yC1PKqRorECRwJhF5pXrkFu7JTV2jh1xwjL90uM xD/odIkmeI/SXkBe0Xdx+B/4YeDRnNk2KGfE52Q3iKa9cZqgTw98FD9HKg== X-Gm-Gg: ASbGncuwjb5MawJQ9HfpZQIQXtt7LThEI3GxdcP3VoCibosmbj/va1BdS4SCS/iNsYu pMPt6+xbAbeAPNNp6g7zX2WmUYTcLP339BlgV8A7L7Q8otX+5mWmREHHpsw8XUzPb+yhWB4USdW /W6zQcMtarvW9+g7QvtfeMRMiFadvowtv7lhArjyZEgscZ1SxglS6vac6oTQUFcHPgE9MEDcGDC UvJgmWU3sf6KtBxoyxpzNIGNeL+hndzb4sQwtH0hz3vOPE3CPSCjYt3gY7zIeqXdQ== X-Google-Smtp-Source: AGHT+IGzxHtLLWIObAIsDZNVHlJJ/ToGn0ikoivI/fIiKs+Iw9vE5tmHamdCIKyf4BKWPiTxj6TcyA== X-Received: by 2002:a05:6a00:c92:b0:725:e499:5b8a with SMTP id d2e1a72fcca58-72dafa9ac70mr27484807b3a.15.1737547505402; Wed, 22 Jan 2025 04:05:05 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-72dab816412sm11055732b3a.66.2025.01.22.04.05.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Jan 2025 04:05:04 -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, Eduard Zingerman Subject: [RFC bpf-next v1 5/7] bpf: DFA-based liveness analysis for program registers Date: Wed, 22 Jan 2025 04:04:40 -0800 Message-ID: <20250122120442.3536298-6-eddyz87@gmail.com> X-Mailer: git-send-email 2.47.1 In-Reply-To: <20250122120442.3536298-1-eddyz87@gmail.com> References: <20250122120442.3536298-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 X-Patchwork-State: RFC Compute may-live registers before each instruction in the program. The register is live before the instruction I if it is read by I or some instruction S following I during program execution and is not overwritten between I and S. This information would be used in the next patch as a hint in func_states_equal(). Use a simple algorithm described in [1] to compute this information: - define the following: - I.use : a set of all registers read by instruction I; - I.def : a set of all registers written by instruction I; - I.in : a set of all registers that may be alive before I execution; - I.out : a set of all registers that may be alive after I execution; - I.successors : a set of instructions S that might immediately follow I for some program execution; - associate separate empty sets 'I.in' and 'I.out' with each instruction; - visit each instruction in a postorder and update corresponding 'I.in' and 'I.out' sets as follows: I.out = U [S.in for S in I.successors] I.in = (I.out / I.def) U I.use (where U stands for set union, / stands for set difference) - repeat the computation while I.{in,out} changes for any instruction. On implementation side keep things as simple, as possible: - check_cfg() already marks instructions EXPLORED in post-order, modify it to save the index of each EXPLORED instruction in a vector; - represent I.{in,out,use,def} as bitmasks; - don't split the program into basic blocks and don't maintain the work queue, instead: - do fixed-point computation by visiting each instruction; - maintain a simple 'changed' flag if I.{in,out} for any instruction change; Measurements show that even such simplistic implementation does not add measurable verification time overhead (for selftests, at-least). Note on check_cfg() ex_insn_beg/ex_done change: To avoid out of bounds access to env->cfg.insn_postorder array, it should be guaranteed that instruction transitions to EXPLORED state only once. Previously this was not the fact for incorrect programs with direct calls to exception callbacks. The 'align' selftest needs adjustment to skip computed insn/live registers printout. Otherwise it matches lines from the live registers printout. [1] https://en.wikipedia.org/wiki/Live-variable_analysis Signed-off-by: Eduard Zingerman --- include/linux/bpf_verifier.h | 6 + kernel/bpf/verifier.c | 351 ++++++++++++++++-- .../testing/selftests/bpf/prog_tests/align.c | 11 +- 3 files changed, 344 insertions(+), 24 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 32c23f2a3086..2b243a32d846 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -589,6 +589,8 @@ struct bpf_insn_aux_data { * accepts callback function as a parameter. */ bool calls_callback; + /* registers alive before this instruction. */ + u16 live_regs_before; }; #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */ @@ -742,7 +744,11 @@ struct bpf_verifier_env { struct { int *insn_state; int *insn_stack; + /* vector of instruction indexes sorted in post-order */ + int *insn_postorder; int cur_stack; + /* current position in the insn_postorder vector */ + int cur_postorder; } cfg; struct backtrack_state bt; struct bpf_insn_hist_entry *insn_hist; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 1c2199a3f38f..d36c5a3309e9 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -3268,6 +3268,15 @@ static int add_subprog_and_kfunc(struct bpf_verifier_env *env) return 0; } +static int jmp_offset(struct bpf_insn *insn) +{ + u8 code = insn->code; + + if (code == (BPF_JMP32 | BPF_JA)) + return insn->imm; + return insn->off; +} + static int check_subprogs(struct bpf_verifier_env *env) { int i, subprog_start, subprog_end, off, cur_subprog = 0; @@ -3294,10 +3303,7 @@ static int check_subprogs(struct bpf_verifier_env *env) goto next; if (BPF_OP(code) == BPF_EXIT || BPF_OP(code) == BPF_CALL) goto next; - if (code == (BPF_JMP32 | BPF_JA)) - off = i + insn[i].imm + 1; - else - off = i + insn[i].off + 1; + off = i + jmp_offset(&insn[i]) + 1; if (off < subprog_start || off >= subprog_end) { verbose(env, "jump out of range from insn %d to %d\n", i, off); return -EINVAL; @@ -3827,6 +3833,17 @@ static const char *disasm_kfunc_name(void *data, const struct bpf_insn *insn) return btf_name_by_offset(desc_btf, func->name_off); } +static void verbose_insn(struct bpf_verifier_env *env, struct bpf_insn *insn) +{ + const struct bpf_insn_cbs cbs = { + .cb_call = disasm_kfunc_name, + .cb_print = verbose, + .private_data = env, + }; + + print_bpf_insn(&cbs, insn, env->allow_ptr_leaks); +} + static inline void bt_init(struct backtrack_state *bt, u32 frame) { bt->frame = frame; @@ -4027,11 +4044,6 @@ static bool calls_callback(struct bpf_verifier_env *env, int insn_idx); static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx, struct bpf_insn_hist_entry *hist, struct backtrack_state *bt) { - const struct bpf_insn_cbs cbs = { - .cb_call = disasm_kfunc_name, - .cb_print = verbose, - .private_data = env, - }; struct bpf_insn *insn = env->prog->insnsi + idx; u8 class = BPF_CLASS(insn->code); u8 opcode = BPF_OP(insn->code); @@ -4049,7 +4061,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx, fmt_stack_mask(env->tmp_str_buf, TMP_STR_BUF_LEN, bt_stack_mask(bt)); verbose(env, "stack=%s before ", env->tmp_str_buf); verbose(env, "%d: ", idx); - print_bpf_insn(&cbs, insn, env->allow_ptr_leaks); + verbose_insn(env, insn); } /* If there is a history record that some registers gained range at this insn, @@ -10909,6 +10921,9 @@ static int get_helper_proto(struct bpf_verifier_env *env, int func_id, return *ptr ? 0 : -EINVAL; } +/* Bitmask with 1s for all caller saved registers */ +#define ALL_CALLER_SAVED_REGS ((1u << CALLER_SAVED_REGS) - 1) + static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn, int *insn_idx_p) { @@ -17111,9 +17126,8 @@ static int visit_insn(int t, struct bpf_verifier_env *env) static int check_cfg(struct bpf_verifier_env *env) { int insn_cnt = env->prog->len; - int *insn_stack, *insn_state; + int *insn_stack, *insn_state, *insn_postorder; int ex_insn_beg, i, ret = 0; - bool ex_done = false; insn_state = env->cfg.insn_state = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL); if (!insn_state) @@ -17125,6 +17139,17 @@ static int check_cfg(struct bpf_verifier_env *env) return -ENOMEM; } + insn_postorder = env->cfg.insn_postorder = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL); + if (!insn_postorder) { + kvfree(insn_state); + kvfree(insn_stack); + return -ENOMEM; + } + + ex_insn_beg = env->exception_callback_subprog + ? env->subprog_info[env->exception_callback_subprog].start + : 0; + insn_state[0] = DISCOVERED; /* mark 1st insn as discovered */ insn_stack[0] = 0; /* 0 is the first instruction */ env->cfg.cur_stack = 1; @@ -17138,6 +17163,7 @@ static int check_cfg(struct bpf_verifier_env *env) case DONE_EXPLORING: insn_state[t] = EXPLORED; env->cfg.cur_stack--; + insn_postorder[env->cfg.cur_postorder++] = t; break; case KEEP_EXPLORING: break; @@ -17156,13 +17182,10 @@ static int check_cfg(struct bpf_verifier_env *env) goto err_free; } - if (env->exception_callback_subprog && !ex_done) { - ex_insn_beg = env->subprog_info[env->exception_callback_subprog].start; - + if (ex_insn_beg && insn_state[ex_insn_beg] != EXPLORED) { insn_state[ex_insn_beg] = DISCOVERED; insn_stack[0] = ex_insn_beg; env->cfg.cur_stack = 1; - ex_done = true; goto walk_cfg; } @@ -19001,19 +19024,13 @@ static int do_check(struct bpf_verifier_env *env) } if (env->log.level & BPF_LOG_LEVEL) { - const struct bpf_insn_cbs cbs = { - .cb_call = disasm_kfunc_name, - .cb_print = verbose, - .private_data = env, - }; - if (verifier_state_scratched(env)) print_insn_state(env, state, state->curframe); verbose_linfo(env, env->insn_idx, "; "); env->prev_log_pos = env->log.end_pos; verbose(env, "%d: ", env->insn_idx); - print_bpf_insn(&cbs, insn, env->allow_ptr_leaks); + verbose_insn(env, insn); env->prev_insn_print_pos = env->log.end_pos - env->prev_log_pos; env->prev_log_pos = env->log.end_pos; } @@ -23024,6 +23041,289 @@ static int process_fd_array(struct bpf_verifier_env *env, union bpf_attr *attr, return 0; } +static bool can_fallthrough(struct bpf_insn *insn) +{ + u8 class = BPF_CLASS(insn->code); + u8 opcode = BPF_OP(insn->code); + + if (class != BPF_JMP && class != BPF_JMP32) + return true; + + if (opcode == BPF_EXIT || opcode == BPF_JA) + return false; + + return true; +} + +static bool can_jump(struct bpf_insn *insn) +{ + u8 class = BPF_CLASS(insn->code); + u8 opcode = BPF_OP(insn->code); + + if (class != BPF_JMP && class != BPF_JMP32) + return false; + + switch (opcode) { + case BPF_JA: + case BPF_JEQ: + case BPF_JNE: + case BPF_JLT: + case BPF_JLE: + case BPF_JGT: + case BPF_JGE: + case BPF_JSGT: + case BPF_JSGE: + case BPF_JSLT: + case BPF_JSLE: + case BPF_JCOND: + return true; + } + + return false; +} + +static int insn_successors(struct bpf_prog *prog, u32 idx, u32 succ[2]) +{ + struct bpf_insn *insn = &prog->insnsi[idx]; + int i = 0, insn_sz; + u32 dst; + + succ[0] = prog->len; + succ[1] = prog->len; + + insn_sz = bpf_is_ldimm64(insn) ? 2 : 1; + if (can_fallthrough(insn) && idx + 1 < prog->len) + succ[i++] = idx + insn_sz; + + if (can_jump(insn)) { + dst = idx + jmp_offset(insn) + 1; + if (i == 0 || succ[0] != dst) + succ[i++] = dst; + } + + return i; +} + +/* Each field is a register bitmask */ +struct insn_live_regs { + u16 use; /* registers read by instruction */ + u16 def; /* registers written by instruction */ + u16 in; /* registers that may be alive before instruction */ + u16 out; /* registers that may be alive after instruction */ +}; + +/* Compute *use and *def values for the call instruction */ +static void compute_call_live_regs(struct bpf_verifier_env *env, + struct bpf_insn *insn, + u16 *use, u16 *def) +{ + *def = ALL_CALLER_SAVED_REGS; + *use = *def & ~BIT(BPF_REG_0); +} + +/* Compute info->{use,def} fields for the instruction */ +static void compute_insn_live_regs(struct bpf_verifier_env *env, + struct bpf_insn *insn, + struct insn_live_regs *info) +{ + u8 class = BPF_CLASS(insn->code); + u8 code = BPF_OP(insn->code); + u8 mode = BPF_MODE(insn->code); + u16 src = BIT(insn->src_reg); + u16 dst = BIT(insn->dst_reg); + u16 r0 = BIT(0); + u16 def = 0; + u16 use = 0xffff; + + switch (class) { + case BPF_LD: + switch (mode) { + case BPF_IMM: + if (BPF_SIZE(insn->code) == BPF_DW) { + def = dst; + use = 0; + } + break; + case BPF_LD | BPF_ABS: + case BPF_LD | BPF_IND: + /* stick with defaults */ + break; + } + break; + case BPF_LDX: + switch (mode) { + case BPF_MEM: + case BPF_MEMSX: + def = dst; + use = src; + break; + } + break; + case BPF_ST: + switch (mode) { + case BPF_MEM: + def = 0; + use = dst; + break; + } + break; + case BPF_STX: + switch (mode) { + case BPF_MEM: + def = 0; + use = dst | src; + break; + case BPF_ATOMIC: + use = dst | src; + if (insn->imm & BPF_FETCH) { + if (insn->imm == BPF_CMPXCHG) + def = r0; + else + def = src; + } else { + def = 0; + } + break; + } + break; + case BPF_ALU: + case BPF_ALU64: + switch (code) { + case BPF_END: + use = dst; + def = dst; + break; + case BPF_MOV: + def = dst; + if (BPF_SRC(insn->code) == BPF_K) + use = 0; + else + use = src; + break; + default: + def = dst; + if (BPF_SRC(insn->code) == BPF_K) + use = dst; + else + use = dst | src; + } + break; + case BPF_JMP: + case BPF_JMP32: + switch (code) { + case BPF_JA: + def = 0; + use = 0; + break; + case BPF_EXIT: + def = 0; + use = r0; + break; + case BPF_CALL: + compute_call_live_regs(env, insn, &use, &def); + break; + default: + def = 0; + if (BPF_SRC(insn->code) == BPF_K) + use = dst; + else + use = dst | src; + } + break; + } + + info->def = def; + info->use = use; +} + +/* Compute may-live registers after each instruction in the program. + * The register is live after the instruction I if it is read by some + * instruction S following I during program execution and is not + * overwritten between I and S. + * + * Store result in env->insn_aux_data[i].live_regs. + */ +static int compute_live_registers(struct bpf_verifier_env *env) +{ + struct bpf_insn_aux_data *insn_aux = env->insn_aux_data; + struct bpf_insn *insns = env->prog->insnsi; + struct insn_live_regs *state; + int insn_cnt = env->prog->len; + int err = 0, i, j; + bool changed; + + /* Use simple algorithm desribed in: + * https://en.wikipedia.org/wiki/Live-variable_analysis + * + * - visit each instruction in a postorder and update + * state[i].in, state[i].out as follows: + * + * state[i].out = U [state[s].in for S in insn_successors(i)] + * state[i].in = (state[i].out / state[i].def) U state[i].use + * + * (where U stands for set union, / stands for set difference) + * - repeat the computation while {in,out} fields changes for + * any instruction. + */ + state = kvcalloc(insn_cnt, sizeof(*state), GFP_KERNEL); + if (!state) { + err = -ENOMEM; + goto out; + } + + for (i = 0; i < insn_cnt; ++i) + compute_insn_live_regs(env, &insns[i], &state[i]); + + changed = true; + while (changed) { + changed = false; + for (i = 0; i < env->cfg.cur_postorder; ++i) { + int insn_idx = env->cfg.insn_postorder[i]; + struct insn_live_regs *live = &state[insn_idx]; + int succ_num; + u32 succ[2]; + u16 new_out = 0; + u16 new_in = 0; + + succ_num = insn_successors(env->prog, insn_idx, succ); + for (int s = 0; s < succ_num; ++s) + new_out |= state[succ[s]].in; + new_in = (new_out & ~live->def) | live->use; + if (new_out != live->out || new_in != live->in) { + live->in = new_in; + live->out = new_out; + changed = true; + } + } + } + + for (i = 0; i < insn_cnt; ++i) + insn_aux[i].live_regs_before = state[i].in; + + if (env->log.level & BPF_LOG_LEVEL2) { + verbose(env, "Live regs before insn:\n"); + for (i = 0; i < insn_cnt; ++i) { + verbose(env, "%3d: ", i); + for (j = BPF_REG_0; j < BPF_REG_10; ++j) + if (insn_aux[i].live_regs_before & BIT(j)) + verbose(env, "%d", j); + else + verbose(env, "."); + verbose(env, " "); + verbose_insn(env, &insns[i]); + if (bpf_is_ldimm64(&insns[i])) + i++; + } + } + +out: + kvfree(state); + kvfree(env->cfg.insn_postorder); + env->cfg.insn_postorder = NULL; + env->cfg.cur_postorder = 0; + return err; +} + int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u32 uattr_size) { u64 start_time = ktime_get_ns(); @@ -23141,6 +23441,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3 if (ret) goto skip_full_check; + ret = compute_live_registers(env); + if (ret < 0) + goto skip_full_check; + ret = mark_fastcall_patterns(env); if (ret < 0) goto skip_full_check; @@ -23279,6 +23583,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3 vfree(env->insn_aux_data); kvfree(env->insn_hist); err_free_env: + kvfree(env->cfg.insn_postorder); kvfree(env); return ret; } diff --git a/tools/testing/selftests/bpf/prog_tests/align.c b/tools/testing/selftests/bpf/prog_tests/align.c index 4ebd0da898f5..1d53a8561ee2 100644 --- a/tools/testing/selftests/bpf/prog_tests/align.c +++ b/tools/testing/selftests/bpf/prog_tests/align.c @@ -610,9 +610,11 @@ static int do_test_single(struct bpf_align_test *test) .log_size = sizeof(bpf_vlog), .log_level = 2, ); + const char *main_pass_start = "0: R1=ctx() R10=fp0"; const char *line_ptr; int cur_line = -1; int prog_len, i; + char *start; int fd_prog; int ret; @@ -632,7 +634,13 @@ static int do_test_single(struct bpf_align_test *test) ret = 0; /* We make a local copy so that we can strtok() it */ strncpy(bpf_vlog_copy, bpf_vlog, sizeof(bpf_vlog_copy)); - line_ptr = strtok(bpf_vlog_copy, "\n"); + start = strstr(bpf_vlog_copy, main_pass_start); + if (!start) { + ret = 1; + printf("Can't find initial line '%s'\n", main_pass_start); + goto out; + } + line_ptr = strtok(start, "\n"); for (i = 0; i < MAX_MATCHES; i++) { struct bpf_reg_match m = test->matches[i]; const char *p; @@ -682,6 +690,7 @@ static int do_test_single(struct bpf_align_test *test) break; } } +out: if (fd_prog >= 0) close(fd_prog); } From patchwork Wed Jan 22 12:04:41 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13947215 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f175.google.com (mail-pl1-f175.google.com [209.85.214.175]) (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 7A03C212B39 for ; Wed, 22 Jan 2025 12:05:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.175 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737547509; cv=none; b=QWWQCTOfqTQO4vUejpgqHyYXcjxOalXo9s78JXoOgeFVHmmcZl1cCViKCIl/b/hZAD83Q7cHFcJDONFsDfHDOdAsRWPoldZH8v+TUtn8rjhzDzxUiQKCZV3mrwQGYUuKADczDBzDkGAoOPRffDxeYQ/nitS62OXN6VoiRuwNoEM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737547509; c=relaxed/simple; bh=ZFBW98UPTvZU4Vhis/qY77Tw000t8sOskTvhA3T9pY0=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=bMKFXtdDRRfd+MWSB3XRTCrhBQrlrgav1mfKooGqKFbcsCNb5pTtfgdNlWdgBuL7bkKmHki6p0oqBhV52ozfxwVsBM3kBLoxYRZL38zF+TwHBAGSnfUlACJu8N1itPJHR8Jv4dDY2bqSP5MtLB0//WiqKI9n0NtkmPdfmDFnStA= 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=hssHHfYi; arc=none smtp.client-ip=209.85.214.175 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="hssHHfYi" Received: by mail-pl1-f175.google.com with SMTP id d9443c01a7336-21628b3fe7dso118808105ad.3 for ; Wed, 22 Jan 2025 04:05:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1737547506; x=1738152306; 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=G9YnhYhlAwSR/bgJ6my/TfsoOeWkMATKaBOpbfFyQJM=; b=hssHHfYiVhQSTMm+SnfX8fBgSk+KJEbqWM616s1FoIqy3MU4OzJmArOQ1QrhNDNsXe +LhOz68Rz8wUNTQsz8eJQiemXojfhbUXLGRBEEUZKoHYu+zXAEOAvfaktjKUJK0iQpgI 1MPnd/Ojtd5DVWScLcTTd3mTmwI+pP0caKOGndnSK0kGArSX0ZExqsVQjy5sYqlwi2Bg WG0h8an3ACmpqKpn52DmlFGhKyZwrr1we1K6bUKAPjFtXjtk/IuOLQ/P9xSRXZbE87ar tsQaFemycxihjkcFL46SN38rBrxcWp9+q+mSR7ChJsa/OTd+qud+YbQVat/aevfb1uSY XCrA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1737547506; x=1738152306; 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=G9YnhYhlAwSR/bgJ6my/TfsoOeWkMATKaBOpbfFyQJM=; b=CXrlEWSnDRcRWc83S12S63FsPNtlxDESe1ysSdkKio3cqR+eEzrs+aHrHMqwCK3zTG mipk9REl+s87YbuhEXH1RJBQ7e134KKe2sKSsl8FjFHPAfrmE7wA2CpS0IAL1usAkl54 /cpSdFdPPtkFM48hW6t0cKCdkI8YWV/49kN1lY5zAnJTeRL/JdpGIMv2yhy6vpImNLVZ rcjnwkj49pWp2sGuhbDSJWeg9DT04FyKgLLtZQoe0qATTWVQ89okz1Kj/e1xVeCyRE/J AlNASgAM6PPu6Ef8ZwbT+Xk2bHNxWxRFXJlyofi/us3EAMxr6sWX2YHJ7t8Xq7LdEHiJ hQ/A== X-Gm-Message-State: AOJu0YzcZklx//zqUe0+nmIcuk7isXDRG2YcsNbGNY4LMwqn1tXQ8Vs/ 7X9P0Cjp2Xh+IiQ3ArhTf1Uqq0tT3bAPrDQm3CfmDVm+t8iKOO0jK+f0aA== X-Gm-Gg: ASbGncuu2sZX+oxXmN1sNYX6eL/5qh6aR+b9p/dh2b2I/SpnRkGyZ4zX98+d2n+jRoc qv1bSUjZfFJar/rrfe7yVqCljYkFje2U9Dm/OSrziQTwu9cFhn0JfGCC1JOs3qPmyZDUoKTTLZB QlwZLO5Iy8M172+aTHb66lsdFU9AyJBH9/AA7K7gXqEcz9OVx3F/1nKy9LKhiCziI33hVqTP5bY xVKzeYNRcC4sfbODhRCt28zIZ24OftXtUb2vfNBgymG1jxDHq4nVA2/KicMSojVY1Q0T59j34/i X-Google-Smtp-Source: AGHT+IHBeW92ho/JRKYDVU24bfGR8WLwQPUIG70nwsqxdecJ8E/fU02hQKoHD5e2UaSPhhLlaMjo0g== X-Received: by 2002:a05:6a00:4fcb:b0:727:99a8:cd31 with SMTP id d2e1a72fcca58-72daf97b5d3mr32020615b3a.14.1737547506322; Wed, 22 Jan 2025 04:05:06 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-72dab816412sm11055732b3a.66.2025.01.22.04.05.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Jan 2025 04:05:05 -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, Eduard Zingerman Subject: [RFC bpf-next v1 6/7] bpf: use register liveness information for func_states_equal Date: Wed, 22 Jan 2025 04:04:41 -0800 Message-ID: <20250122120442.3536298-7-eddyz87@gmail.com> X-Mailer: git-send-email 2.47.1 In-Reply-To: <20250122120442.3536298-1-eddyz87@gmail.com> References: <20250122120442.3536298-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 X-Patchwork-State: RFC Liveness analysis DFA computes a set of registers live before each instruction. Leverage this information to skip comparison of dead registers in func_states_equal(). This helps with convergance of iterator processing loops, as bpf_reg_state->live marks can't be used when loops are processed. This has certain performance impact for selftests, here is a veristat listing for bigger ones (this patch compared to previous patch): File Program Insns (DIFF) States (DIFF) -------------------- -------------------------- --------------- -------------- iters.bpf.o checkpoint_states_deletion -8617 (-87.68%) -327 (-89.10%) iters.bpf.o iter_nested_iters -140 (-18.13%) -10 (-13.89%) pyperf600_iter.bpf.o on_event -2608 (-41.31%) -29 (-10.32%) Impact on sched_ext: Program Insns (DIFF) States (DIFF) ---------------------- ---------------- --------------- lavd_dispatch -34018 (-22.00%) -1885 (-21.06%) layered_dispatch -1808 (-22.83%) -86 (-13.85%) layered_dump -943 (-20.17%) -44 (-16.30%) layered_init -995 (-18.05%) -80 (-15.41%) refresh_layer_cpumasks -395 (-30.74%) -34 (-28.33%) rustland_init -63 (-13.24%) -3 (-8.11%) rustland_init -63 (-13.24%) -3 (-8.11%) tp_cgroup_attach_task -53 (-26.24%) -4 (-22.22%) central_init -146 (-25.09%) -2 (-5.26%) pair_dispatch -331 (-17.34%) -15 (-10.56%) qmap_dispatch -375 (-17.15%) -26 (-14.94%) userland_dispatch -34 (-21.79%) -4 (-23.53%) Signed-off-by: Eduard Zingerman --- kernel/bpf/verifier.c | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index d36c5a3309e9..babc2e179c08 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -18223,15 +18223,17 @@ static bool refsafe(struct bpf_verifier_state *old, struct bpf_verifier_state *c * the current state will reach 'bpf_exit' instruction safely */ static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_state *old, - struct bpf_func_state *cur, enum exact_level exact) + struct bpf_func_state *cur, u32 insn_idx, enum exact_level exact) { - int i; + u16 live_regs = env->insn_aux_data[insn_idx].live_regs_before; + u16 i; if (old->callback_depth > cur->callback_depth) return false; for (i = 0; i < MAX_BPF_REG; i++) - if (!regsafe(env, &old->regs[i], &cur->regs[i], + if (((1 << i) & live_regs) && + !regsafe(env, &old->regs[i], &cur->regs[i], &env->idmap_scratch, exact)) return false; @@ -18252,6 +18254,7 @@ static bool states_equal(struct bpf_verifier_env *env, struct bpf_verifier_state *cur, enum exact_level exact) { + u32 insn_idx; int i; if (old->curframe != cur->curframe) @@ -18275,9 +18278,12 @@ static bool states_equal(struct bpf_verifier_env *env, * and all frame states need to be equivalent */ for (i = 0; i <= old->curframe; i++) { + insn_idx = i == old->curframe + ? env->insn_idx + : old->frame[i + 1]->callsite; if (old->frame[i]->callsite != cur->frame[i]->callsite) return false; - if (!func_states_equal(env, old->frame[i], cur->frame[i], exact)) + if (!func_states_equal(env, old->frame[i], cur->frame[i], insn_idx, exact)) return false; } return true; From patchwork Wed Jan 22 12:04:42 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 13947217 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f176.google.com (mail-pl1-f176.google.com [209.85.214.176]) (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 C75AD212B02 for ; Wed, 22 Jan 2025 12:05:08 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.176 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737547510; cv=none; b=oTaMi6jFkSAnrlX9wCaVL+C5mM1dIWQCf5TykkTq0/R34825b4tTHkdYb0dFpTeBMNJ7E0BqgJpkWM+DdzMrlOfxEz51pERbHfYUEi0C+tBPMhONScTcCKZS0+drWJxR1zryTA4/fWgEjacdbFsZIxeT03q/x8Dn774bdGJPz+k= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1737547510; c=relaxed/simple; bh=6N8caChTTQwsoKDFGtSSZ23N5E8qDbrZqDDSBdDAALs=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=uMGUxdvrBPE8oaYEozpNgWBsqzs68u9ssEiTYhHcd4dAhsFDW0brrCZ/KAGzQVJTjKT5OJoL3QnCkGVnzZZxCpF+ZvtYXwwOBtbltEkj5vbutghn5RdMwyPtCEH2t0UXMekYgMh1rNFZbaMXfqD35LSX8k/ZkteJD1Hfh2tETCk= 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=DZ0qbUyc; arc=none smtp.client-ip=209.85.214.176 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="DZ0qbUyc" Received: by mail-pl1-f176.google.com with SMTP id d9443c01a7336-2162c0f6a39so14260515ad.0 for ; Wed, 22 Jan 2025 04:05:08 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1737547508; x=1738152308; 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=j5o4Cb3BLqtPRwc3WDOy5KP44bfkuIkve46JbYHmSuw=; b=DZ0qbUycOiDewgoHj+9FPt9us6bcjkMY0s5tDKE/4Q8T30CPq4zQQEhHmzmS2n2Gy0 8Wyk4f2bWWajUicn8PyKiKveW1VLDndJ/bd4grYuWG78P4QkCWaCF6yRigzKoVXKqc9l uhlLjBPdml0NSKoGcS+dmY/2woWMq2fGIJ2fB3VpTn4rZFobuvu2TC1W5+UVeb//d3c2 /ki8DN9EgMuw2L1lIpQEzv7ae3DNb5N0SNbOb5zybrvdKmiL562isgGHhsT7cc9654lI 4FYJvv6F8DCAFNDtTffx8x+ZSFX/ALgFCvFLa7Htc2/ZPwzvZUSFmJchRwhgjr+79g20 IWhg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1737547508; x=1738152308; 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=j5o4Cb3BLqtPRwc3WDOy5KP44bfkuIkve46JbYHmSuw=; b=DeGswjT6kKP+r3aKCVxJMNsK1duol/H9ijZLSUW/p35F60Fp04dC+hoAGB+KQ4Mstd wWXRye0uTgHjNoXimcjT7gXg3dzTn7jVkafoeczfpaKt5aReQl4msuhn4XKsie94P/sN WqVhWtGDlLpouXgXzWhbZEe9/6MFFRDP4Zb3BybZ7NW79sDOjejnwB+C8mpCGFLdkIBQ ZX8yr5nttRmWDfk0Le0ILkEJ2tBydeXNCjOGGOhfeddJvGDlJTc6M7Wx+3bPKQ7msY+D 4SFC/vUAHcignWW+DnEC2n64FDqcpWlqjci/tHWIweW1F3L1d/lI2nSBuXSjdOqJ52lf yg1g== X-Gm-Message-State: AOJu0YzKrKkRHwDixqDbYSTl4cKNce4BAlaYFUUHUxuDh9uH3aj04LFY MbAq7j72OFxKa7xMRaoCV3cpB+CXZoChuG/iPzLFV4JVVcydJcG16zqkrw== X-Gm-Gg: ASbGncvnfkuqQIOBwuoNIYFJTE0Q1YQ27ZO7PDg1O+bqsjLUwJ207Vojvg5ZwoOXhQD h+9rJzzbMK2ujHJ+NNT3zBQ9en+UZjLz1h80EHb/Dr4Fj+d4EVYJE5/QxhGAgbt6jpBckCIlqhA Aexm/nvNEkmhqjdQoirUaf4FaSGI+Se+MrpWsocxH6ykQeS8JO4+Fz3sqnkaSHOUsIjwRCN03MX lCEtSaRsHPbz35dXniLdEOTYb2X5fm3i2jHTP6S369xntVhPOiUSNLlNEW7pjqT/A== X-Google-Smtp-Source: AGHT+IFPYeStzu+P7q+OWRFbVeMYAKHOHH3ZQr9OmdFxrU0TLsPyd60p/Wy462tTbw5fzQ70rGx6Ig== X-Received: by 2002:a05:6a21:9215:b0:1e1:b0e8:11dc with SMTP id adf61e73a8af0-1eb2176de74mr31026126637.21.1737547507520; Wed, 22 Jan 2025 04:05:07 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-72dab816412sm11055732b3a.66.2025.01.22.04.05.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Jan 2025 04:05:06 -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, Eduard Zingerman Subject: [RFC bpf-next v1 7/7] selftests/bpf: test cases for compute_live_registers() Date: Wed, 22 Jan 2025 04:04:42 -0800 Message-ID: <20250122120442.3536298-8-eddyz87@gmail.com> X-Mailer: git-send-email 2.47.1 In-Reply-To: <20250122120442.3536298-1-eddyz87@gmail.com> References: <20250122120442.3536298-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 X-Patchwork-State: RFC Cover instructions from each kind: - assignment - arithmetic - store/load - endian conversion - atomics - branches, conditional branches, may_goto, calls - LD_ABS/LD_IND - address_space_cast Signed-off-by: Eduard Zingerman --- .../bpf/prog_tests/compute_live_registers.c | 9 + tools/testing/selftests/bpf/progs/bpf_misc.h | 12 + .../bpf/progs/compute_live_registers.c | 363 ++++++++++++++++++ .../selftests/bpf/progs/verifier_gotol.c | 6 +- .../bpf/progs/verifier_iterating_callbacks.c | 6 +- 5 files changed, 386 insertions(+), 10 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/compute_live_registers.c create mode 100644 tools/testing/selftests/bpf/progs/compute_live_registers.c diff --git a/tools/testing/selftests/bpf/prog_tests/compute_live_registers.c b/tools/testing/selftests/bpf/prog_tests/compute_live_registers.c new file mode 100644 index 000000000000..285f20241fe1 --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/compute_live_registers.c @@ -0,0 +1,9 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include "compute_live_registers.skel.h" +#include "test_progs.h" + +void test_compute_live_registers(void) +{ + RUN_TESTS(compute_live_registers); +} diff --git a/tools/testing/selftests/bpf/progs/bpf_misc.h b/tools/testing/selftests/bpf/progs/bpf_misc.h index f45f4352feeb..2b34911439d4 100644 --- a/tools/testing/selftests/bpf/progs/bpf_misc.h +++ b/tools/testing/selftests/bpf/progs/bpf_misc.h @@ -208,4 +208,16 @@ #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) #endif +#if (defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) || \ + (defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64) || \ + defined(__TARGET_ARCH_arm) || defined(__TARGET_ARCH_s390) || \ + defined(__TARGET_ARCH_loongarch)) && \ + __clang_major__ >= 18 +#define CAN_USE_GOTOL +#endif + +#if _clang_major__ >= 18 +#define CAN_USE_BPF_ST +#endif + #endif diff --git a/tools/testing/selftests/bpf/progs/compute_live_registers.c b/tools/testing/selftests/bpf/progs/compute_live_registers.c new file mode 100644 index 000000000000..988fdd442f55 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/compute_live_registers.c @@ -0,0 +1,363 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include +#include +#include "../../../include/linux/filter.h" +#include "bpf_arena_common.h" +#include "bpf_misc.h" + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY); + __uint(max_entries, 1); + __type(key, __u32); + __type(value, __u64); +} test_map SEC(".maps"); + +struct { + __uint(type, BPF_MAP_TYPE_ARENA); + __uint(map_flags, BPF_F_MMAPABLE); + __uint(max_entries, 1); +} arena SEC(".maps"); + +SEC("socket") +__log_level(2) +__msg(" 0: .......... (b7) r0 = 42") +__msg(" 1: 0......... (bf) r1 = r0") +__msg(" 2: .1........ (bf) r2 = r1") +__msg(" 3: ..2....... (bf) r3 = r2") +__msg(" 4: ...3...... (bf) r4 = r3") +__msg(" 5: ....4..... (bf) r5 = r4") +__msg(" 6: .....5.... (bf) r6 = r5") +__msg(" 7: ......6... (bf) r7 = r6") +__msg(" 8: .......7.. (bf) r8 = r7") +__msg(" 9: ........8. (bf) r9 = r8") +__msg("10: .........9 (bf) r0 = r9") +__msg("11: 0......... (95) exit") +__naked void assign_chain(void) +{ + asm volatile ( + "r0 = 42;" + "r1 = r0;" + "r2 = r1;" + "r3 = r2;" + "r4 = r3;" + "r5 = r4;" + "r6 = r5;" + "r7 = r6;" + "r8 = r7;" + "r9 = r8;" + "r0 = r9;" + "exit;" + ::: __clobber_all); +} + +SEC("socket") +__log_level(2) +__msg("0: .......... (b7) r1 = 7") +__msg("1: .1........ (07) r1 += 7") +__msg("2: .......... (b7) r2 = 7") +__msg("3: ..2....... (b7) r3 = 42") +__msg("4: ..23...... (0f) r2 += r3") +__msg("5: .......... (b7) r0 = 0") +__msg("6: 0......... (95) exit") +__naked void arithmetics(void) +{ + asm volatile ( + "r1 = 7;" + "r1 += 7;" + "r2 = 7;" + "r3 = 42;" + "r2 += r3;" + "r0 = 0;" + "exit;" + ::: __clobber_all); +} + +#ifdef CAN_USE_BPF_ST +SEC("socket") +__log_level(2) +__msg(" 1: .1........ (07) r1 += -8") +__msg(" 2: .1........ (7a) *(u64 *)(r1 +0) = 7") +__msg(" 3: .1........ (b7) r2 = 42") +__msg(" 4: .12....... (7b) *(u64 *)(r1 +0) = r2") +__msg(" 5: .12....... (7b) *(u64 *)(r1 +0) = r2") +__msg(" 6: .......... (b7) r0 = 0") +__naked void store(void) +{ + asm volatile ( + "r1 = r10;" + "r1 += -8;" + "*(u64 *)(r1 +0) = 7;" + "r2 = 42;" + "*(u64 *)(r1 +0) = r2;" + "*(u64 *)(r1 +0) = r2;" + "r0 = 0;" + "exit;" + ::: __clobber_all); +} +#endif + +SEC("socket") +__log_level(2) +__msg("1: ....4..... (07) r4 += -8") +__msg("2: ....4..... (79) r5 = *(u64 *)(r4 +0)") +__msg("3: ....45.... (07) r4 += -8") +__naked void load(void) +{ + asm volatile ( + "r4 = r10;" + "r4 += -8;" + "r5 = *(u64 *)(r4 +0);" + "r4 += -8;" + "r0 = r5;" + "exit;" + ::: __clobber_all); +} + +SEC("socket") +__log_level(2) +__msg("0: .1........ (61) r2 = *(u32 *)(r1 +0)") +__msg("1: ..2....... (d4) r2 = le64 r2") +__msg("2: ..2....... (bf) r0 = r2") +__naked void endian(void) +{ + asm volatile ( + "r2 = *(u32 *)(r1 +0);" + "r2 = le64 r2;" + "r0 = r2;" + "exit;" + ::: __clobber_all); +} + +SEC("socket") +__log_level(2) +__msg(" 8: 0......... (b7) r1 = 1") +__msg(" 9: 01........ (db) r1 = atomic64_fetch_add((u64 *)(r0 +0), r1)") +__msg("10: 01........ (c3) lock *(u32 *)(r0 +0) += r1") +__msg("11: 01........ (db) r1 = atomic64_xchg((u64 *)(r0 +0), r1)") +__msg("12: 01........ (bf) r2 = r0") +__msg("13: .12....... (bf) r0 = r1") +__msg("14: .12....... (db) r0 = atomic64_cmpxchg((u64 *)(r2 +0), r0, r1)") +__naked void atomic(void) +{ + asm volatile ( + "r2 = r10;" + "r2 += -8;" + "r1 = 0;" + "*(u64 *)(r2 +0) = r1;" + "r1 = %[test_map] ll;" + "call %[bpf_map_lookup_elem];" + "if r0 == 0 goto 1f;" + "r1 = 1;" + "r1 = atomic_fetch_add((u64 *)(r0 +0), r1);" + ".8byte %[add_nofetch];" /* same as "lock *(u32 *)(r0 +0) += r1;" */ + "r1 = xchg_64(r0 + 0, r1);" + "r2 = r0;" + "r0 = r1;" + "r0 = cmpxchg_64(r2 + 0, r0, r1);" + "1: exit;" + : + : __imm(bpf_map_lookup_elem), + __imm_addr(test_map), + __imm_insn(add_nofetch, BPF_ATOMIC_OP(BPF_W, BPF_ADD, BPF_REG_0, BPF_REG_1, 0)) + : __clobber_all); +} + +SEC("socket") +__log_level(2) +__msg("4: .12345.7.. (85) call bpf_trace_printk#6") +__msg("5: 0......7.. (0f) r0 += r7") +__naked void regular_call(void) +{ + asm volatile ( + "r7 = 1;" + "r1 = r10;" + "r1 += -8;" + "r2 = 1;" + "call %[bpf_trace_printk];" + "r0 += r7;" + "exit;" + : + : __imm(bpf_trace_printk) + : __clobber_all); +} + +SEC("socket") +__log_level(2) +__msg("2: 012....... (25) if r1 > 0x7 goto pc+1") +__msg("3: ..2....... (bf) r0 = r2") +__naked void if1(void) +{ + asm volatile ( + "r0 = 1;" + "r2 = 2;" + "if r1 > 0x7 goto +1;" + "r0 = r2;" + "exit;" + ::: __clobber_all); +} + +SEC("socket") +__log_level(2) +__msg("3: 0123...... (2d) if r1 > r3 goto pc+1") +__msg("4: ..2....... (bf) r0 = r2") +__naked void if2(void) +{ + asm volatile ( + "r0 = 1;" + "r2 = 2;" + "r3 = 7;" + "if r1 > r3 goto +1;" + "r0 = r2;" + "exit;" + ::: __clobber_all); +} + +SEC("socket") +__log_level(2) +__msg("0: .......... (b7) r1 = 0") +__msg("1: .1........ (b7) r2 = 7") +__msg("2: .12....... (25) if r1 > 0x7 goto pc+4") +__msg("3: .12....... (07) r1 += 1") +__msg("4: .12....... (27) r2 *= 2") +__msg("5: .12....... (05) goto pc+0") +__msg("6: .12....... (05) goto pc-5") +__msg("7: .......... (b7) r0 = 0") +__msg("8: 0......... (95) exit") +__naked void loop(void) +{ + asm volatile ( + "r1 = 0;" + "r2 = 7;" + "if r1 > 0x7 goto +4;" + "r1 += 1;" + "r2 *= 2;" + "goto +0;" + "goto -5;" + "r0 = 0;" + "exit;" + : + : __imm(bpf_trace_printk) + : __clobber_all); +} + +#ifdef CAN_USE_GOTOL +SEC("socket") +__log_level(2) +__msg("2: .123...... (25) if r1 > 0x7 goto pc+2") +__msg("3: ..2....... (bf) r0 = r2") +__msg("4: 0......... (06) gotol pc+1") +__msg("5: ...3...... (bf) r0 = r3") +__msg("6: 0......... (95) exit") +__naked void gotol(void) +{ + asm volatile ( + "r2 = 42;" + "r3 = 24;" + "if r1 > 0x7 goto +2;" + "r0 = r2;" + "gotol +1;" + "r0 = r3;" + "exit;" + : + : __imm(bpf_trace_printk) + : __clobber_all); +} +#endif + +SEC("socket") +__log_level(2) +__msg("0: 0......... (b7) r1 = 1") +__msg("1: 01........ (e5) may_goto pc+1") +__msg("2: 0......... (05) goto pc-3") +__msg("3: .1........ (bf) r0 = r1") +__msg("4: 0......... (95) exit") +__naked void may_goto(void) +{ + asm volatile ( + "1: r1 = 1;" + ".8byte %[may_goto];" + "goto 1b;" + "r0 = r1;" + "exit;" + : + : __imm(bpf_get_smp_processor_id), + __imm_insn(may_goto, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, +1 /* offset */, 0)) + : __clobber_all); +} + +SEC("socket") +__log_level(2) +__msg("1: 0......... (18) r2 = 0x7") +__msg("3: 0.2....... (0f) r0 += r2") +__naked void ldimm64(void) +{ + asm volatile ( + "r0 = 0;" + "r2 = 0x7 ll;" + "r0 += r2;" + "exit;" + : + :: __clobber_all); +} + +/* No rules specific for LD_ABS/LD_IND, default behaviour kicks in */ +SEC("socket") +__log_level(2) +__msg("2: 0123456789 (30) r0 = *(u8 *)skb[42]") +__msg("3: 012.456789 (0f) r7 += r0") +__msg("4: 012.456789 (b7) r3 = 42") +__msg("5: 0123456789 (50) r0 = *(u8 *)skb[r3 + 0]") +__msg("6: 0......7.. (0f) r7 += r0") +__naked void ldabs(void) +{ + asm volatile ( + "r6 = r1;" + "r7 = 0;" + "r0 = *(u8 *)skb[42];" + "r7 += r0;" + "r3 = 42;" + ".8byte %[ld_ind];" /* same as "r0 = *(u8 *)skb[r3];" */ + "r7 += r0;" + "r0 = r7;" + "exit;" + : + : __imm_insn(ld_ind, BPF_LD_IND(BPF_B, BPF_REG_3, 0)) + : __clobber_all); +} + + +#ifdef __BPF_FEATURE_ADDR_SPACE_CAST +SEC("?fentry.s/" SYS_PREFIX "sys_getpgid") +__log_level(2) +__msg(" 6: .12345.... (85) call bpf_arena_alloc_pages") +__msg(" 7: 0......... (bf) r1 = addr_space_cast(r0, 0, 1)") +__msg(" 8: .1........ (b7) r2 = 42") +__naked void addr_space_cast(void) +{ + asm volatile ( + "r1 = %[arena] ll;" + "r2 = 0;" + "r3 = 1;" + "r4 = 0;" + "r5 = 0;" + "call %[bpf_arena_alloc_pages];" + "r1 = addr_space_cast(r0, 0, 1);" + "r2 = 42;" + "*(u64 *)(r1 +0) = r2;" + "r0 = 0;" + "exit;" + : + : __imm(bpf_arena_alloc_pages), + __imm_addr(arena) + : __clobber_all); +} +#endif + +/* to retain debug info for BTF generation */ +void kfunc_root(void) +{ + bpf_arena_alloc_pages(0, 0, 0, 0, 0); +} + +char _license[] SEC("license") = "GPL"; diff --git a/tools/testing/selftests/bpf/progs/verifier_gotol.c b/tools/testing/selftests/bpf/progs/verifier_gotol.c index 05a329ee45ee..d5d8f24df394 100644 --- a/tools/testing/selftests/bpf/progs/verifier_gotol.c +++ b/tools/testing/selftests/bpf/progs/verifier_gotol.c @@ -4,11 +4,7 @@ #include #include "bpf_misc.h" -#if (defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) || \ - (defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64) || \ - defined(__TARGET_ARCH_arm) || defined(__TARGET_ARCH_s390) || \ - defined(__TARGET_ARCH_loongarch)) && \ - __clang_major__ >= 18 +#ifdef CAN_USE_GOTOL SEC("socket") __description("gotol, small_imm") diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c index e54bb5385bc1..75dd922e4e9f 100644 --- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c @@ -407,11 +407,7 @@ l0_%=: call %[bpf_jiffies64]; \ : __clobber_all); } -#if (defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) || \ - (defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64) || \ - defined(__TARGET_ARCH_arm) || defined(__TARGET_ARCH_s390) || \ - defined(__TARGET_ARCH_loongarch)) && \ - __clang_major__ >= 18 +#ifdef CAN_USE_GOTOL SEC("socket") __success __retval(0) __naked void gotol_and_may_goto(void)