From patchwork Tue Mar 4 07:42:35 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eduard Zingerman X-Patchwork-Id: 14000111 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pj1-f48.google.com (mail-pj1-f48.google.com [209.85.216.48]) (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 AEB7C1F9A83 for ; Tue, 4 Mar 2025 07:43:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.48 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741074221; cv=none; b=VQoue4nhha03GuJKJtFqRp+e3erqZVlaXDexB2FaxShtH7ZuHb2UXBfwyvXbKO3BvnV6I1CrrZMBfoVdCflLmL30caE6S5vdrSEWff5RzhRgcJo5yfcgiU/Bsx465dxKj1qyg8PWJ6Rhm4XaGGwVle6ZnGSYTIXsQALbE7X/DAQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741074221; c=relaxed/simple; bh=G9kwgp1XYHzwS4zv9hmeFHnK+OlbyYCUY0IKzyg1f9o=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=a0mjV+20L0q8seDh/xOex5rNQGoEc/PSd0a6Lk3ISW13xzb/uf02+2OKN7JDmVAh2EUimUeINM3E21V3DkVhftVId54D5bgxdvVj6OjgHzQzDKElaxiv1KWgy6GZz3A1ZTOCHSlT1CM+KopQagJDQ/zSPQlzc/LloOtDyJlHZCg= 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=R3sd9ITz; arc=none smtp.client-ip=209.85.216.48 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="R3sd9ITz" Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-2fef5c978ccso3275974a91.1 for ; Mon, 03 Mar 2025 23:43:39 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741074219; x=1741679019; 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=lUKUKmhVLNzAt9Oxo2/kipJeEcV/Mmy5AU+trlWFn+c=; b=R3sd9ITz1mzQZ4GZAS8aGIPE7TMr/2mY2DAj2Zn8OCzyBemNQl5ij1LnjpDDsuIDbp TMnF+N9b3Kr2ZIESa8MTWnxwuDlbRmXQ9KnFqE9+EPa320qu75BDttahJM4RK30FgE6F 1YlBn2GBpLwdfzUGrPT2fgg/WeYYfa2Gij56BLBA0mM5HN+aRHwFw0BjDDqjpk19sHEX MscK7rGM6X4UingvqDbipUsjUvysaRv2GzZJA7CvQxZQJ17jsfD/IPbjsDTcLM/b1zQH +qNXD+apF1NG6XbZLiz545MPaUvxiCcXUsZbHyFzQ+wBXEVOieIx5/kvkrsY4Lp3kOHF t/uA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741074219; x=1741679019; 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=lUKUKmhVLNzAt9Oxo2/kipJeEcV/Mmy5AU+trlWFn+c=; b=Ot98+VXYP6Bsq3INcTZ9JvC0G3DNEhAprj2/pRme0f6mnUtrtJDepf1QstkqasFFcV fkhBePRzx4MgKIz0P1mJcvQwPxqDDuGjJR358iEP6hbLsBqtqCckNVIPRmskxQ7LkIBE TmozQc5hvSxI7f5oY4ioAwVGzJ0AeMZZtxeC03j2qa9ifNABWgk509+iXu+zwQc3NwBk 81sPJebLv4nZqrZiYcpcXkD3Mruz8AXfeiudqjvYKE3f+12XbvuD+mmxwOlrMQXNcy33 6B003pqQwtER5YBBnLk4zlF2CVqMg0phDN0WOElwwyYKya7XJnYdweO88MYxK3Bcx3E+ MUhA== X-Gm-Message-State: AOJu0YzVSpkzHpGG28+UaiZ2atAGTg9V/yA/aY03tghUgkyH2IzkRlNa 5FHAJkqTxKGSG5PPOSJFs7racGtVHsYFkaqC+I8mAYC5FnSwu2hfibeVxQ== X-Gm-Gg: ASbGncvJjEUG4diUMGDHMGonR33knICyTg6aJtQ2zaV4bAIdbiXC3U9wQwgSDT3dwM3 t+Hp/eE2HSEvVFARtVkOwJ+BPkpCjMQB4i2Eyl9c/MsGEBEerp8jgxuD0DWN3s9cM5ITVkXonZU VBPqFpapjSH+tfv0huM+r4sVrCS58+TCUn06lkvRhb7ohor1n/7ZuMv/eFpsJMqnn4JZsWvuqjZ pKA8kD/Cs8uyUFiE1mDuwqm6/1ig+bYWzB49XJBFCYEo61wneoaoUQcLrjbWB6lSC4KpNRc3b4R njJLY868k/RTdZHJqUgfV733NTYpaOJPmU432K5u X-Google-Smtp-Source: AGHT+IE+L2ZQ7KB+sInMsg2+47Q3R8k0qD6ZbExFkN1u2/MxJvhvAXELx4iUgF3JU3fkSgZNP4thOQ== X-Received: by 2002:a17:90b:3f50:b0:2ee:af31:a7bd with SMTP id 98e67ed59e1d1-2febab2bdcbmr23299422a91.5.1741074218831; Mon, 03 Mar 2025 23:43:38 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2235050d7c1sm89545125ad.198.2025.03.03.23.43.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 03 Mar 2025 23:43: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, Eduard Zingerman Subject: [PATCH bpf-next v2 1/5] bpf: jmp_offset() and verbose_insn() utility functions Date: Mon, 3 Mar 2025 23:42:35 -0800 Message-ID: <20250304074239.2328752-2-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250304074239.2328752-1-eddyz87@gmail.com> References: <20250304074239.2328752-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 Extract two utility functions: - One BPF jump instruction uses .imm field to encode jump offset, while the rest use .off. Encapsulate this detail as jmp_offset() function. - Avoid duplicating instruction printing callback definitions by defining a verbose_insn() function, which disassembles an instruction into the verifier log while hiding this detail. These functions will be used in the next patch. Signed-off-by: Eduard Zingerman --- kernel/bpf/verifier.c | 40 +++++++++++++++++++++++----------------- 1 file changed, 23 insertions(+), 17 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index b6664d0f6914..25910b740bbc 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -3360,6 +3360,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; @@ -3386,10 +3395,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; @@ -3919,6 +3925,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; @@ -4119,11 +4136,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); @@ -4141,7 +4153,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, @@ -19273,19 +19285,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; } From patchwork Tue Mar 4 07:42: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: 14000112 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 D68F31F9A86 for ; Tue, 4 Mar 2025 07:43:40 +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=1741074222; cv=none; b=PWPJVy/Pn0jZ2Nex7skDDDqCHhHmPqfvTrAp6/YrjTmvSEtAT+RZGuIgIZ5jCKqoLoF6Dwpa3rSDwCZzlUeRlkwhvGffggMrRnPNTgwFL0VClI0aDPU1hyPLAYxMdo8rTtCm0PKk6RLv0y7v4HuTXS05jndy1m52nrTYz4B0wlU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741074222; c=relaxed/simple; bh=D8ZEKVn64Sd5axtddKMZqk8ljAOwuL71ctoGRhSaCQc=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=rkw0s9/b3SZInPYCOyI51qeXvtMZepx/fzBKPvRpAOEqjiKT9YwRChYsTjCKeTn6UwhPCkv2sWujWG8WuNJoAVwKs2FWYuodnmTQdgEj+6NsXREoZwJ+i6rCtU9fmUpnLcuoKUrhnRuzB4qsRQ7NFNW2nSpxbUWufWfGTunFPos= 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=gSv9g/pL; 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="gSv9g/pL" Received: by mail-pl1-f181.google.com with SMTP id d9443c01a7336-223a7065ff8so51731485ad.0 for ; Mon, 03 Mar 2025 23:43:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741074220; x=1741679020; 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=coac0IMqhgbNlsTguy9T8pdlS35mZJeiVU0PCL9zvew=; b=gSv9g/pLBOpTq7KnQ9qgWExvtBZpg1BSJYta1LCrnLyfrZWrOlwHpkl26j00XWV9Ve NILjg3Ro4m00t8PEUkxL9plm4WPOkL9jg++WM8+co7TGKSIAfd1ntGeaTsbCpR9n4gu9 z4aCrW2kwW9D+dktt5VDvDsaZH301KtRxQ0cAbYfMbTPH6y26+Ag4LKmcmMKHGdb8UeF ETH+CqwJ1yNEQmGh7WKw7shHowrwD+3qx0Qm6qKP6Lt1NP6xfqBK5zhZpKWa1UGY7YnR k3vFAWV8GXaOdFbpECr1HdYAEe0cuJ7X3beueNhZTm4s3kax4rLgbZknSLY6Z81N3/WO PswA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741074220; x=1741679020; 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=coac0IMqhgbNlsTguy9T8pdlS35mZJeiVU0PCL9zvew=; b=cLOaPeyY4esnby3F1qi4D57JdRx5yVwKPPOb3xSOqe+DDy/ttFWZ6UBhMs6r9nmd2/ Zmze27HkMyvxu2gcBw3t3QFc8K/Ykj0u7luDG/Un9dPFgv452U4lRWQxxrUUL9Z85LvK YIhTS+s+Z/9u12v3N4gRlgIIiCrZP5nu/9hKYheKSbMREKwNzPRIIQZthikn7liWHXhu DMhtXeMOz/JjCE4W1u2zUNaBQ++WvazHkllz7UeeMYMhKpIqFXGtKKEnElhHEsQaJV2r HSABOg076OMU3McaKgatspEvAWKHR6JlQgIaZzGprktVJTRAPaYAagwDc1G1hH5f7CQ0 I0ow== X-Gm-Message-State: AOJu0YzEE0sPLmuSw2/VwRYAECg9eudSRaq657P9HZ+kzrEmuUDbfJUL CtjB1U3inM3DI6zaH4mj+x6mXUYMtusKdd4JGJD/RaLb3Ojx8uflnbUlbg== X-Gm-Gg: ASbGncsmD3WFYuB33KT5uMReHyDeipjGrulOgPWulW31+flQbTHcBtjx73ivcg5qxzi D5lKTgyqQu3GjbxqNDihm/Mh+QRJ4vAkkxM5njH/4u6ZiYcCG9hbeV+L6K6lY4jS7v3fWVWhLkh +pHxLdMBYsBivR9+h5bphIulF1AHmBGq4J9lxDp6Kxt20eJou71Lfy2tdgG+Ldi4pB+3EmBif3B is0gEomXxjwYjjMMKTz1yukJqEDiiQwovJGoIRbGOb/dCjGXJs/1oP/B9gVajCKId/xhYdXA7vc p0698CSav8KJt7mAur93vGGu6gURXYZTYAEWPYL7 X-Google-Smtp-Source: AGHT+IH7Qxam26rkGXcXexRRCCTf2J5BdcbMcXKGvSA+TOpZb0VbYO4lkt6tWtY50FKrJtCzVOxjoA== X-Received: by 2002:a17:902:fc84:b0:220:d28a:c5c7 with SMTP id d9443c01a7336-22368fc267emr274906045ad.21.1741074219875; Mon, 03 Mar 2025 23:43:39 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2235050d7c1sm89545125ad.198.2025.03.03.23.43.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 03 Mar 2025 23:43: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, Eduard Zingerman Subject: [PATCH bpf-next v2 2/5] bpf: get_call_summary() utility function Date: Mon, 3 Mar 2025 23:42:36 -0800 Message-ID: <20250304074239.2328752-3-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250304074239.2328752-1-eddyz87@gmail.com> References: <20250304074239.2328752-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 Refactor mark_fastcall_pattern_for_call() to extract a utility function get_call_summary(). For a helper or kfunc call this function fills the following information: {num_params, is_void, fastcall}. This function would be used in the next patch in order to get number of parameters of a helper or kfunc call. Signed-off-by: Eduard Zingerman --- kernel/bpf/verifier.c | 121 ++++++++++++++++++++---------------------- 1 file changed, 57 insertions(+), 64 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 25910b740bbc..5cc1b6ed0e92 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -17019,27 +17019,6 @@ static int visit_func_call_insn(int t, struct bpf_insn *insns, /* Bitmask with 1s for all caller saved registers */ #define ALL_CALLER_SAVED_REGS ((1u << CALLER_SAVED_REGS) - 1) -/* Return a bitmask specifying which caller saved registers are - * clobbered by a call to a helper *as if* this helper follows - * bpf_fastcall contract: - * - includes R0 if function is non-void; - * - includes R1-R5 if corresponding parameter has is described - * in the function prototype. - */ -static u32 helper_fastcall_clobber_mask(const struct bpf_func_proto *fn) -{ - u32 mask; - int i; - - mask = 0; - if (fn->ret_type != RET_VOID) - mask |= BIT(BPF_REG_0); - for (i = 0; i < ARRAY_SIZE(fn->arg_type); ++i) - if (fn->arg_type[i] != ARG_DONTCARE) - mask |= BIT(BPF_REG_1 + i); - return mask; -} - /* True if do_misc_fixups() replaces calls to helper number 'imm', * replacement patch is presumed to follow bpf_fastcall contract * (see mark_fastcall_pattern_for_call() below). @@ -17056,24 +17035,54 @@ static bool verifier_inlines_helper_call(struct bpf_verifier_env *env, s32 imm) } } -/* Same as helper_fastcall_clobber_mask() but for kfuncs, see comment above */ -static u32 kfunc_fastcall_clobber_mask(struct bpf_kfunc_call_arg_meta *meta) +struct call_summary { + u8 num_params; + bool is_void; + bool fastcall; +}; + +/* If @call is a kfunc or helper call, fills @cs and returns true, + * otherwise returns false. + */ +static bool get_call_summary(struct bpf_verifier_env *env, struct bpf_insn *call, + struct call_summary *cs) { - u32 vlen, i, mask; + struct bpf_kfunc_call_arg_meta meta; + const struct bpf_func_proto *fn; + int i; - vlen = btf_type_vlen(meta->func_proto); - mask = 0; - if (!btf_type_is_void(btf_type_by_id(meta->btf, meta->func_proto->type))) - mask |= BIT(BPF_REG_0); - for (i = 0; i < vlen; ++i) - mask |= BIT(BPF_REG_1 + i); - return mask; -} + if (bpf_helper_call(call)) { -/* Same as verifier_inlines_helper_call() but for kfuncs, see comment above */ -static bool is_fastcall_kfunc_call(struct bpf_kfunc_call_arg_meta *meta) -{ - return meta->kfunc_flags & KF_FASTCALL; + if (get_helper_proto(env, call->imm, &fn) < 0) + /* error would be reported later */ + return false; + cs->fastcall = fn->allow_fastcall && + (verifier_inlines_helper_call(env, call->imm) || + bpf_jit_inlines_helper_call(call->imm)); + cs->is_void = fn->ret_type == RET_VOID; + cs->num_params = 0; + for (i = 0; i < ARRAY_SIZE(fn->arg_type); ++i) { + if (fn->arg_type[i] == ARG_DONTCARE) + break; + cs->num_params++; + } + return true; + } + + if (bpf_pseudo_kfunc_call(call)) { + int err; + + err = fetch_kfunc_meta(env, call, &meta, NULL); + if (err < 0) + /* error would be reported later */ + return false; + cs->num_params = btf_type_vlen(meta.func_proto); + cs->fastcall = meta.kfunc_flags & KF_FASTCALL; + cs->is_void = btf_type_is_void(btf_type_by_id(meta.btf, meta.func_proto->type)); + return true; + } + + return false; } /* LLVM define a bpf_fastcall function attribute. @@ -17156,39 +17165,23 @@ static void mark_fastcall_pattern_for_call(struct bpf_verifier_env *env, { struct bpf_insn *insns = env->prog->insnsi, *stx, *ldx; struct bpf_insn *call = &env->prog->insnsi[insn_idx]; - const struct bpf_func_proto *fn; - u32 clobbered_regs_mask = ALL_CALLER_SAVED_REGS; + u32 clobbered_regs_mask; + struct call_summary cs; u32 expected_regs_mask; - bool can_be_inlined = false; s16 off; int i; - if (bpf_helper_call(call)) { - if (get_helper_proto(env, call->imm, &fn) < 0) - /* error would be reported later */ - return; - clobbered_regs_mask = helper_fastcall_clobber_mask(fn); - can_be_inlined = fn->allow_fastcall && - (verifier_inlines_helper_call(env, call->imm) || - bpf_jit_inlines_helper_call(call->imm)); - } - - if (bpf_pseudo_kfunc_call(call)) { - struct bpf_kfunc_call_arg_meta meta; - int err; - - err = fetch_kfunc_meta(env, call, &meta, NULL); - if (err < 0) - /* error would be reported later */ - return; - - clobbered_regs_mask = kfunc_fastcall_clobber_mask(&meta); - can_be_inlined = is_fastcall_kfunc_call(&meta); - } - - if (clobbered_regs_mask == ALL_CALLER_SAVED_REGS) + if (!get_call_summary(env, call, &cs)) return; + /* A bitmask specifying which caller saved registers are clobbered + * by a call to a helper/kfunc *as if* this helper/kfunc follows + * bpf_fastcall contract: + * - includes R0 if function is non-void; + * - includes R1-R5 if corresponding parameter has is described + * in the function prototype. + */ + clobbered_regs_mask = GENMASK(cs.num_params, cs.is_void ? 1 : 0); /* e.g. if helper call clobbers r{0,1}, expect r{2,3,4,5} in the pattern */ expected_regs_mask = ~clobbered_regs_mask & ALL_CALLER_SAVED_REGS; @@ -17246,7 +17239,7 @@ static void mark_fastcall_pattern_for_call(struct bpf_verifier_env *env, * don't set 'fastcall_spills_num' for call B so that remove_fastcall_spills_fills() * does not remove spill/fill pair {4,6}. */ - if (can_be_inlined) + if (cs.fastcall) env->insn_aux_data[insn_idx].fastcall_spills_num = i - 1; else subprog->keep_fastcall_stack = 1; From patchwork Tue Mar 4 07:42: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: 14000113 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 C1A3C1F9428 for ; Tue, 4 Mar 2025 07:43:41 +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=1741074223; cv=none; b=VO3I2Akua+TOVOuy+Sox14YCr+sQCrKcoF3nFIdHhSbKVm1zB3wznvSvHkkwqwBZNVm4PKKZQsWqom+ONLqSleZIxK/EIAJu1jKeaJiTHllhi1IIS90pa2fC1lDDV4TLvI7us6Dd+IBAz0tq0hXQxAiJQLCKUt/h/FdIROXRNaM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741074223; c=relaxed/simple; bh=AsDrgacNyl246KXUPfaAuZM3GyNzowAPE0B758TrbEU=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=fNFbb1Md9jNM4jKmOdrtkC+YCPzNxWoE1tAD12CXmEbd7UZdS3PktAqEwQcjKcSpXr3fnSdV1DufGMhzY8Z3ppdcxS8Q5l/ltQwwMGRDYFDvGSALLwfdgNBxS5AhTaRKcBZHk+BvuAAZ/Yf2gKdhcgiJfhes7MjHksaceHpk19s= 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=Lx3Be5Sx; 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="Lx3Be5Sx" Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-2235189adaeso85859115ad.0 for ; Mon, 03 Mar 2025 23:43:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741074221; x=1741679021; 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=0m5K1oeMi/o9jphWMETSsjoz5kzUJo6FbqB8i5HmWes=; b=Lx3Be5Sx1R4gE027B0DVWxr4kS1eIuA6q2/Q6p07W9BfgG+dGlrDGMO1IYfWdD6toL pWp0GJgD6LsLjBFbqbttiMeGtsacds+3C41TSs05yhFmxx4/zhPaSICfhRgEIZjv06Kj MIeCR81fjUBhMdoIVmRkjGX9cBO1kOhgQjqaoj4MXWkrRFm1eAq4oqldF2v4RXeFy9Ag +wm/zHaCXSmAKn5B5wCEnjZf9M9YXEl/Fm6QWXcHQVJuWW9r74nVQsGK36WwimfJqD35 +9KHR/HVoT+U3jB6Te9SZBaSWv++fuhavlxXJkMLRFyE5P8ORtZwmQ7NEu8d9eDIa1mS ZhgQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741074221; x=1741679021; 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=0m5K1oeMi/o9jphWMETSsjoz5kzUJo6FbqB8i5HmWes=; b=oupbz6vo0ST2VyXzBO4rwwxnYqKjCa3YSXEh3Qlp+eMMyty2PuCF04QPH6Epwr3uhr 1dUvhm/7jq+A3WFyHdgX1fag0PILhJ+cYP85puDb2wQU3Jdi5UZ6WnMiJ9tjyvSXKGdY Dl51OCcto7zLHlRcKPqldYXJuX23vDJ9elktlTuLM0LayWf0iPkqFNzpZ7Ftc9iaektl adzaMXPPVXA5PYCWHVD5pDbgs0bfUe0y55Bye446OZHa0oBZUZTojO166VBUbak9JAl9 2GMUmpYlScVIp/eYHYBSBb3+EzvJE2YYjueMYcmZ2mJiVbZW9GS1GTCP7SM3gUPaVf/C L80w== X-Gm-Message-State: AOJu0Yx65ea6EDErUj81pITzrohm/NE0Txx3FdDiGt+GwYXOqDyrVTEU oaa90dztAmfZqlbcDt4AFDLOlHz6/GiH4cW7gaCnllqaL9+GRLNwxVoSnA== X-Gm-Gg: ASbGncv7htWrMhsruuI9m0inWYtTo6IEfnCUsCE++c+9JcVp/QefLMkCVyVf6N1n5pY FZRcV4TR2u9OwXsAYB6CbJeU33pTZbkpogFZKhF/UzE9Bjp9ZP4K4L2PFTPBFt87QfRUmP2A8pK LrbEILC+OWK1rRlLjayVcr0mUdN8n1ALEX1xvV36WqD8DmSKsqCuYyf7uh7QTc17/QSVLOkt/Wu TKsQi6CpzXvbxruxeoxtKM52Pgt8sJz+bJWjNKzrj8ZoZVK/k1do4QhgLjZZoYhN0al8OMA3boG c2rJnT81VftA6QttfOmO9QRXflPVhOIxFouyMMS5 X-Google-Smtp-Source: AGHT+IENjinNTLcdFpUbpzGgVeFvnxp5GhjVSg2XXcMhNqwNfYhmVSGsYCK8qCci6wEq1zJN4gOAsA== X-Received: by 2002:a17:903:1c1:b0:221:751f:cfbe with SMTP id d9443c01a7336-223d9173960mr37860495ad.19.1741074220689; Mon, 03 Mar 2025 23:43:40 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2235050d7c1sm89545125ad.198.2025.03.03.23.43.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 03 Mar 2025 23:43:40 -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, Eduard Zingerman Subject: [PATCH bpf-next v2 3/5] bpf: simple DFA-based live registers analysis Date: Mon, 3 Mar 2025 23:42:37 -0800 Message-ID: <20250304074239.2328752-4-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250304074239.2328752-1-eddyz87@gmail.com> References: <20250304074239.2328752-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 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 | 309 +++++++++++++++++- .../testing/selftests/bpf/prog_tests/align.c | 11 +- 3 files changed, 319 insertions(+), 7 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index d338f2a96bba..d6cfc4ee6820 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -591,6 +591,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 */ @@ -748,7 +750,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 5cc1b6ed0e92..09298e0e4b73 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -17402,9 +17402,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) @@ -17416,6 +17415,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; @@ -17429,6 +17439,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; @@ -17447,13 +17458,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; } @@ -23379,6 +23387,290 @@ 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; + + 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 */ +}; + +/* Bitmask with 1s for all caller saved registers */ +#define ALL_CALLER_SAVED_REGS ((1u << CALLER_SAVED_REGS) - 1) + +/* 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) +{ + struct call_summary cs; + 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: + def = ALL_CALLER_SAVED_REGS; + use = def & ~BIT(BPF_REG_0); + if (get_call_summary(env, insn, &cs)) + use = GENMASK(cs.num_params, 1); + 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 the following algorithm: + * - 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; + * - insn_successors(I): 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 + * 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(); @@ -23500,6 +23792,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; @@ -23638,6 +23934,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 Tue Mar 4 07:42: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: 14000114 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 707C11F9A83 for ; Tue, 4 Mar 2025 07:43:42 +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=1741074224; cv=none; b=LWHwMifVQurF7lBuqYbiz9rZWx/Zgky5aNKf/H6u8xtMgfp2vqExfJYoeWyb8VKWBCT5ZK3q3i/d/qLJINYsLgxcDTavQhFKxTvzIeX03/ebSXiDJO8pt+gjOcmqFPjbb/6nnRUkWhb0Lrrmjyg/PBwv4YXjRs4erlWjJk837Bk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741074224; c=relaxed/simple; bh=hSp9ao7hvzRr2iO5Mp3H3YgWUajloZ/Lw/CDax4ils0=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=iY50bRgnnl9zhhqALk6Hlgbl/WOyX08ocdESeu58itwg7wXj8w6cywTzjd+x3+9pFSsLAqeu3YoBcbSOzoSgpCD+wM2oqzogCkWEmu6R9Za5jc5lsUFlbdbOmLBd3dCsqU/AcPzbVl+Dym2vzTDMA0W7MLQ+EZqajWz9jWZTuiE= 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=aV8ugoXt; 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="aV8ugoXt" Received: by mail-pj1-f41.google.com with SMTP id 98e67ed59e1d1-2f44353649aso8440566a91.0 for ; Mon, 03 Mar 2025 23:43:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741074221; x=1741679021; 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=ZTuh+Ebz89LvmqO9DItlVl/GvCvtRJOYt4hWet4SWic=; b=aV8ugoXtn7s1QmcpE3ssjVFGE6ScSD85ZDVNRu10foaHIXomdvxBBYnG48VlAVSjpQ eo4Pg6xaVKFBGbk54txLiflafdPH2NKa+Zd9L7fDCXY9yNws4NoK0NWx1wwuqP77IDhk fssMB50BWPiN4nY7KLD4lLUeP3NGuNwJD+lOLPeoBvePaCUYQkM2RixfYnrJ1BQKVAVc I5S8a53uzROJDnbJfQFtXXRTc2Y8JjZe8F1aiP9wXdB1NPBBF7KbBZ89BeNONye7Fc0R soCVv3s3cdRxE0v3mwc+nLuZbX0sOG5KGf5Zjc8BFInqE9K0RWuTy5WNfO00VJ3dwvvj 4V4Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741074221; x=1741679021; 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=ZTuh+Ebz89LvmqO9DItlVl/GvCvtRJOYt4hWet4SWic=; b=AtVot28JS9aH6S6oHs2mK37NqqsuTiG4zZT7r5uNPRrb7w+FJOuS/eI+p62EP+gzU5 z2aS7O1ZGmHSeIoKmIfiaSSbphXnd7Hr4BSvQyOMVZs7eiWJ43PSOFln6+TxxDDBA/5v bH5nBNDqVxpikW4vZn3CwHpUTQC8B53jOlCe85Hh1m+/nl+g+Pjo1oHpyiGKHtZiWrhJ GWKssXSEI0K/MCRNBjJI0xiJP1p/MIAWASroKcwf0bR+7NT7ktE3foxOdZmQFAbj/7h9 1AEYheNsEINfiZaYLs6iIg9DlQcL9gTc1hW3oh5NK84vDAcGdk5s+eLuK8aXg7tb0HJz cjsw== X-Gm-Message-State: AOJu0YwW2okFx2TwN4jajAZ+7/M1IHa7mUhBuAzsZ4t1L2TPfWKZQJtj q6w00G+BkALz8xjHPM8SIdmzjMBGgvj20mkcX82CImP5dLcZmSUG1LxnSA== X-Gm-Gg: ASbGncvR7izW8Lb5uFf68h8bwMg0ZUaOQJaHKD/FV5UoqWzDwdbKj7IT6lbsCGA2V8h HnQvVKzlx008gA07ImazHSiUGHy7C4LcDE8WIpdz0bdFZeVJ0RFmzPDYbbYgWuemaHOxyDa2sNf yeW2dB7cVenLrxyCxdxsZUsCTy8TXJNCy6abLpFpc3V1FIcKw4vqEZMTBPqBRmH3dap2skHifRN 9rvvaGaMEF/w6TYUjiaXezpxQ90zmkVXMF95amBfsMHR3E8GYOPH0NlUikHZOSTAB8tMYk7OIGk vOfYeW51YZLyIKkymXJ298NsB/JJqdvbw+rPT3C1 X-Google-Smtp-Source: AGHT+IFDoTRdifM52GWZc6JYPAlaG/AEl/DyaE5kzgCvgaM2Q0NGNakmAyLQnp6CAlotDIMOdys9+Q== X-Received: by 2002:a17:90b:17cf:b0:2fe:9e6c:add9 with SMTP id 98e67ed59e1d1-2febab70151mr27550889a91.18.1741074221574; Mon, 03 Mar 2025 23:43:41 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2235050d7c1sm89545125ad.198.2025.03.03.23.43.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 03 Mar 2025 23:43:41 -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, Eduard Zingerman Subject: [PATCH bpf-next v2 4/5] bpf: use register liveness information for func_states_equal Date: Mon, 3 Mar 2025 23:42:38 -0800 Message-ID: <20250304074239.2328752-5-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250304074239.2328752-1-eddyz87@gmail.com> References: <20250304074239.2328752-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 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 using `-f "insns_pct>5" -f "!insns<200"` selftests: File Program States (A) States (B) States (DIFF) -------------------- ----------------------------- ---------- ---------- -------------- arena_htab.bpf.o arena_htab_llvm 37 35 -2 (-5.41%) arena_htab_asm.bpf.o arena_htab_asm 37 33 -4 (-10.81%) arena_list.bpf.o arena_list_add 37 22 -15 (-40.54%) dynptr_success.bpf.o test_dynptr_copy 22 16 -6 (-27.27%) dynptr_success.bpf.o test_dynptr_copy_xdp 68 58 -10 (-14.71%) iters.bpf.o checkpoint_states_deletion 918 40 -878 (-95.64%) iters.bpf.o clean_live_states 136 66 -70 (-51.47%) iters.bpf.o iter_nested_deeply_iters 43 37 -6 (-13.95%) iters.bpf.o iter_nested_iters 72 62 -10 (-13.89%) iters.bpf.o iter_pass_iter_ptr_to_subprog 30 26 -4 (-13.33%) iters.bpf.o iter_subprog_iters 68 59 -9 (-13.24%) iters.bpf.o loop_state_deps2 35 32 -3 (-8.57%) iters_css.bpf.o iter_css_for_each 32 29 -3 (-9.38%) pyperf600_iter.bpf.o on_event 286 192 -94 (-32.87%) Total progs: 3577 Old success: 2060 New success: 2060 States diff min: -95.64% States diff max: 0.00% -100 .. -90 %: 1 -55 .. -45 %: 3 -45 .. -35 %: 2 -35 .. -25 %: 5 -20 .. -10 %: 12 -10 .. 0 %: 6 sched_ext: File Program States (A) States (B) States (DIFF) ----------------- ---------------------- ---------- ---------- --------------- bpf.bpf.o lavd_dispatch 8950 7065 -1885 (-21.06%) bpf.bpf.o lavd_init 516 480 -36 (-6.98%) bpf.bpf.o layered_dispatch 662 501 -161 (-24.32%) bpf.bpf.o layered_dump 298 237 -61 (-20.47%) bpf.bpf.o layered_init 523 423 -100 (-19.12%) bpf.bpf.o layered_init_task 24 22 -2 (-8.33%) bpf.bpf.o layered_runnable 151 125 -26 (-17.22%) bpf.bpf.o p2dq_dispatch 66 53 -13 (-19.70%) bpf.bpf.o p2dq_init 170 142 -28 (-16.47%) bpf.bpf.o refresh_layer_cpumasks 120 78 -42 (-35.00%) bpf.bpf.o rustland_init 37 34 -3 (-8.11%) bpf.bpf.o rustland_init 37 34 -3 (-8.11%) bpf.bpf.o rusty_select_cpu 125 108 -17 (-13.60%) scx_central.bpf.o central_dispatch 59 43 -16 (-27.12%) scx_central.bpf.o central_init 39 28 -11 (-28.21%) scx_nest.bpf.o nest_init 58 51 -7 (-12.07%) scx_pair.bpf.o pair_dispatch 142 111 -31 (-21.83%) scx_qmap.bpf.o qmap_dispatch 174 141 -33 (-18.97%) scx_qmap.bpf.o qmap_init 768 654 -114 (-14.84%) Total progs: 216 Old success: 186 New success: 186 States diff min: -35.00% States diff max: 0.00% -35 .. -25 %: 3 -25 .. -20 %: 6 -20 .. -15 %: 6 -15 .. -5 %: 7 -5 .. 0 %: 6 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 09298e0e4b73..9685b283224a 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -18500,15 +18500,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; @@ -18529,6 +18531,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) @@ -18552,9 +18555,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 Tue Mar 4 07:42: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: 14000115 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 B872E1F9A86 for ; Tue, 4 Mar 2025 07:43:43 +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=1741074225; cv=none; b=ZW3at/x0s6ZJZhcpgma071lPpvMSqNOJa2vwTSEZQj7kQSwdDgSMil2WDpCs4aH25M2VITQVeloCYH4C6eu5okyzsRzfqUcteSg/WOF/XUUEmFQ0MmTaPBTdAzECBaEu1dpOTKEQoC9l+O0bjfyzAPjS/xU7AAq0kHB8YJC+oZw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741074225; c=relaxed/simple; bh=YN3G3YZazzHGMMVO428oq8bgL5//nHvjHURH55dkKRM=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=jZCgmKUAwiVldzeVcQKxHRY1CoLPhfSEa53KAlPQHsHcccNyjS+g1SS84nR8XVacxE0yBvMZcuBWEj6aQCMTTc3bSGxw6NA+GJMERSjV/E3XFwO5ldabU6/rDc/vFj54rsXnvkTKChAVKwPcujU4+0gbLdBJ4AnquOabuWvJctQ= 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=IbqmQEgy; 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="IbqmQEgy" Received: by mail-pj1-f41.google.com with SMTP id 98e67ed59e1d1-2fee4d9c2efso3872429a91.3 for ; Mon, 03 Mar 2025 23:43:43 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1741074223; x=1741679023; 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=kSp8gvfROLFsaGBDv3InVZ7BjIcQeD3oOI0lSKjHuT8=; b=IbqmQEgyJ3Yz76HGw4s8fW6RBnYq9NYWwY7ZHiQ+HjVeNzcIRyjAvE8I4EDtFiDl45 90if8Okb19ydtPxezxOsGFjvMv/1TUmKpsT7SAeDx3yeYVM6nhEA/pquz2GHS4ttjvmc NIxvCWH+4fuuFSAYT+oz48ASJB2Xa3YheXchwv1HouZ3ge0RO5/TbE+bQTk7bEfn82j4 +rg0oFH759WXMGR+JjvucO8CSMsK0mxopzBxpLxn0h1lAvUx4PygDyboRGA8VaW92vbL V6EEcIz2V0c9ok7DU3ABMXylGnwDbC52mHzaEqDSiO03RPt02qO0bZVB0iCeiel4TAoF XDbw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741074223; x=1741679023; 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=kSp8gvfROLFsaGBDv3InVZ7BjIcQeD3oOI0lSKjHuT8=; b=KvCyEWAbBxmRiqhhf8MEV7qnu8w/9ukj7sfrJTwOPJnRppf0AXBfd8yRUprm/f/aO6 Vl4WGC20hFBchUhK0U3p6+cqWLGTi/Eu6NKqsUjLcE6gWw5lWlTLB2VGn1rPSmsDkzWK qdodbDpz2uEkisZ+g4OIUHh9QSEsGR6XGlD6Dg4gu4rNzG0+clh8nCLLtiT3ouOy+FW2 ggASv4ghJdd1IUotxgMK5JL0Q5OCk8wq2/5SYcbJli19lB+srbUhrmQhnskFHwJz77KK TAuUuDLWJ+3a4BI1FnQT41P/wD6Up0TZipO+pxAqCWxvEjBeUfmHVHuJ18pYKtlifTqr aRsQ== X-Gm-Message-State: AOJu0YzdunihWkQvBtLte/zNqA2sZCXF9MqrMON+9VmW2fUGsgxIF3FI vc3BuLRkWem1EMng4jtC0kR1OVNOQggg13G5OwzUypEFjdZ1S2p42a7R7Q== X-Gm-Gg: ASbGncvaGIELgpZ2pdqWfiAOvGS75Jfd6YEnRz8cFOVPTvQOLx8mfXLFeAiBn1oIEdc FZQLmnBovNTzb9lCAoeQHSmCsu01kXK6zNeH8/Dw2Tgc57pOf81tcl31Wb6lYQKRWNEcoE2eNHv ra31VkiCXx3k9DG/wd+QUZ8jXXjKNPhhMgCW/elznZs0la96aLtPQETBi11ckP+0ugsN6iQIx0o biuIs8Tm1jiVOYzibiGFZFRD2KhNWE0IOC71o2ZnSQoohbZt0UKHZsYvMIm6FWlmFJUB6Vdct6M B0GEJIx0ClL10BohZyJY0vqLQmfVgJja2vuItGTS X-Google-Smtp-Source: AGHT+IHPQ12hif0nkCU/4IU3GcGQQjIVzg4lkSYkjpbTD4KEnrGd9jdTzG7xBI/R1eLUYt8TQCGzvQ== X-Received: by 2002:a17:90b:394e:b0:2ea:37b4:5373 with SMTP id 98e67ed59e1d1-2febab5ba76mr27348026a91.10.1741074222727; Mon, 03 Mar 2025 23:43:42 -0800 (PST) Received: from honey-badger.. ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2235050d7c1sm89545125ad.198.2025.03.03.23.43.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 03 Mar 2025 23:43:42 -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, Eduard Zingerman Subject: [PATCH bpf-next v2 5/5] selftests/bpf: test cases for compute_live_registers() Date: Mon, 3 Mar 2025 23:42:39 -0800 Message-ID: <20250304074239.2328752-6-eddyz87@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250304074239.2328752-1-eddyz87@gmail.com> References: <20250304074239.2328752-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 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 | 397 ++++++++++++++++++ .../selftests/bpf/progs/verifier_gotol.c | 6 +- .../bpf/progs/verifier_iterating_callbacks.c | 6 +- 5 files changed, 420 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 34f555da546f..e12e74e7e66e 100644 --- a/tools/testing/selftests/bpf/progs/bpf_misc.h +++ b/tools/testing/selftests/bpf/progs/bpf_misc.h @@ -213,4 +213,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..f976dec2bb88 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/compute_live_registers.c @@ -0,0 +1,397 @@ +// 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: .12....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 + +static __used __naked int aux1(void) +{ + asm volatile ( + "r0 = r1;" + "r0 += r2;" + "exit;" + ::: __clobber_all); +} + +SEC("socket") +__log_level(2) +__msg("0: ....45.... (b7) r1 = 1") +__msg("1: .1..45.... (b7) r2 = 2") +__msg("2: .12.45.... (b7) r3 = 3") +/* Conservative liveness for subprog parameters. */ +__msg("3: .12345.... (85) call pc+2") +__msg("4: .......... (b7) r0 = 0") +__msg("5: 0......... (95) exit") +__msg("6: .12....... (bf) r0 = r1") +__msg("7: 0.2....... (0f) r0 += r2") +/* Conservative liveness for subprog return value. */ +__msg("8: 0......... (95) exit") +__naked void subprog1(void) +{ + asm volatile ( + "r1 = 1;" + "r2 = 2;" + "r3 = 3;" + "call aux1;" + "r0 = 0;" + "exit;" + ::: __clobber_all); +} + +/* 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)