From: Andrii Nakryiko <andrii@kernel.org>
To: <bpf@vger.kernel.org>, <ast@kernel.org>, <daniel@iogearbox.net>,
<martin.lau@kernel.org>
Cc: <andrii@kernel.org>, <kernel-team@meta.com>
Subject: [PATCH v3 bpf-next 05/10] bpf: maintain bitmasks across all active frames in __mark_chain_precision
Date: Thu, 4 May 2023 21:33:12 -0700 [thread overview]
Message-ID: <20230505043317.3629845-6-andrii@kernel.org> (raw)
In-Reply-To: <20230505043317.3629845-1-andrii@kernel.org>
Teach __mark_chain_precision logic to maintain register/stack masks
across all active frames when going from child state to parent state.
Currently this should be mostly no-op, as precision backtracking usually
bails out when encountering subprog entry/exit.
It's not very apparent from the diff due to increased indentation, but
the logic remains the same, except everything is done on specific `fr`
frame index. Calls to bt_clear_reg() and bt_clear_slot() are replaced
with frame-specific bt_clear_frame_reg() and bt_clear_frame_slot(),
where frame index is passed explicitly, instead of using current frame
number.
We also adjust logging to emit affected frame number. And we also add
better logging of human-readable register and stack slot masks, similar
to previous patch.
Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
kernel/bpf/verifier.c | 100 ++++++++++--------
.../testing/selftests/bpf/verifier/precise.c | 18 ++--
2 files changed, 62 insertions(+), 56 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5412c8c8511d..5a7997bc96f5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3736,7 +3736,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int frame, int r
struct bpf_func_state *func;
struct bpf_reg_state *reg;
bool skip_first = true;
- int i, err;
+ int i, fr, err;
if (!env->bpf_capable)
return 0;
@@ -3845,56 +3845,62 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int frame, int r
if (!st)
break;
- func = st->frame[frame];
- bitmap_from_u64(mask, bt_reg_mask(bt));
- for_each_set_bit(i, mask, 32) {
- reg = &func->regs[i];
- if (reg->type != SCALAR_VALUE) {
- bt_clear_reg(bt, i);
- continue;
+ for (fr = bt->frame; fr >= 0; fr--) {
+ func = st->frame[fr];
+ bitmap_from_u64(mask, bt_frame_reg_mask(bt, fr));
+ for_each_set_bit(i, mask, 32) {
+ reg = &func->regs[i];
+ if (reg->type != SCALAR_VALUE) {
+ bt_clear_frame_reg(bt, fr, i);
+ continue;
+ }
+ if (reg->precise)
+ bt_clear_frame_reg(bt, fr, i);
+ else
+ reg->precise = true;
}
- if (reg->precise)
- bt_clear_reg(bt, i);
- else
- reg->precise = true;
- }
- bitmap_from_u64(mask, bt_stack_mask(bt));
- for_each_set_bit(i, mask, 64) {
- if (i >= func->allocated_stack / BPF_REG_SIZE) {
- /* the sequence of instructions:
- * 2: (bf) r3 = r10
- * 3: (7b) *(u64 *)(r3 -8) = r0
- * 4: (79) r4 = *(u64 *)(r10 -8)
- * doesn't contain jmps. It's backtracked
- * as a single block.
- * During backtracking insn 3 is not recognized as
- * stack access, so at the end of backtracking
- * stack slot fp-8 is still marked in stack_mask.
- * However the parent state may not have accessed
- * fp-8 and it's "unallocated" stack space.
- * In such case fallback to conservative.
- */
- mark_all_scalars_precise(env, st);
- bt_reset(bt);
- return 0;
- }
+ bitmap_from_u64(mask, bt_frame_stack_mask(bt, fr));
+ for_each_set_bit(i, mask, 64) {
+ if (i >= func->allocated_stack / BPF_REG_SIZE) {
+ /* the sequence of instructions:
+ * 2: (bf) r3 = r10
+ * 3: (7b) *(u64 *)(r3 -8) = r0
+ * 4: (79) r4 = *(u64 *)(r10 -8)
+ * doesn't contain jmps. It's backtracked
+ * as a single block.
+ * During backtracking insn 3 is not recognized as
+ * stack access, so at the end of backtracking
+ * stack slot fp-8 is still marked in stack_mask.
+ * However the parent state may not have accessed
+ * fp-8 and it's "unallocated" stack space.
+ * In such case fallback to conservative.
+ */
+ mark_all_scalars_precise(env, st);
+ bt_reset(bt);
+ return 0;
+ }
- if (!is_spilled_scalar_reg(&func->stack[i])) {
- bt_clear_slot(bt, i);
- continue;
+ if (!is_spilled_scalar_reg(&func->stack[i])) {
+ bt_clear_frame_slot(bt, fr, i);
+ continue;
+ }
+ reg = &func->stack[i].spilled_ptr;
+ if (reg->precise)
+ bt_clear_frame_slot(bt, fr, i);
+ else
+ reg->precise = true;
+ }
+ if (env->log.level & BPF_LOG_LEVEL2) {
+ fmt_reg_mask(env->tmp_str_buf, TMP_STR_BUF_LEN,
+ bt_frame_reg_mask(bt, fr));
+ verbose(env, "mark_precise: frame%d: parent state regs=%s ",
+ fr, env->tmp_str_buf);
+ fmt_stack_mask(env->tmp_str_buf, TMP_STR_BUF_LEN,
+ bt_frame_stack_mask(bt, fr));
+ verbose(env, "stack=%s: ", env->tmp_str_buf);
+ print_verifier_state(env, func, true);
}
- reg = &func->stack[i].spilled_ptr;
- if (reg->precise)
- bt_clear_slot(bt, i);
- else
- reg->precise = true;
- }
- if (env->log.level & BPF_LOG_LEVEL2) {
- verbose(env, "parent %s regs=%x stack=%llx marks:",
- !bt_empty(bt) ? "didn't have" : "already had",
- bt_reg_mask(bt), bt_stack_mask(bt));
- print_verifier_state(env, func, true);
}
if (bt_empty(bt))
diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c
index a22fabd404ed..77ea018582c5 100644
--- a/tools/testing/selftests/bpf/verifier/precise.c
+++ b/tools/testing/selftests/bpf/verifier/precise.c
@@ -44,7 +44,7 @@
mark_precise: frame0: regs=r2 stack= before 23\
mark_precise: frame0: regs=r2 stack= before 22\
mark_precise: frame0: regs=r2 stack= before 20\
- parent didn't have regs=4 stack=0 marks:\
+ mark_precise: frame0: parent state regs=r2 stack=:\
mark_precise: frame0: last_idx 19 first_idx 10\
mark_precise: frame0: regs=r2 stack= before 19\
mark_precise: frame0: regs=r9 stack= before 18\
@@ -55,7 +55,7 @@
mark_precise: frame0: regs=r9 stack= before 12\
mark_precise: frame0: regs=r9 stack= before 11\
mark_precise: frame0: regs=r9 stack= before 10\
- parent already had regs=0 stack=0 marks:",
+ mark_precise: frame0: parent state regs= stack=:",
},
{
"precise: test 2",
@@ -104,15 +104,15 @@
mark_precise: frame0: regs=r2 stack= before 24\
mark_precise: frame0: regs=r2 stack= before 23\
mark_precise: frame0: regs=r2 stack= before 22\
- parent didn't have regs=4 stack=0 marks:\
+ mark_precise: frame0: parent state regs=r2 stack=:\
mark_precise: frame0: last_idx 20 first_idx 20\
mark_precise: frame0: regs=r2 stack= before 20\
- parent didn't have regs=4 stack=0 marks:\
+ mark_precise: frame0: parent state regs=r2 stack=:\
mark_precise: frame0: last_idx 19 first_idx 17\
mark_precise: frame0: regs=r2 stack= before 19\
mark_precise: frame0: regs=r9 stack= before 18\
mark_precise: frame0: regs=r8,r9 stack= before 17\
- parent already had regs=0 stack=0 marks:",
+ mark_precise: frame0: parent state regs= stack=:",
},
{
"precise: cross frame pruning",
@@ -153,14 +153,14 @@
.prog_type = BPF_PROG_TYPE_XDP,
.flags = BPF_F_TEST_STATE_FREQ,
.errstr = "mark_precise: frame0: last_idx 5 first_idx 5\
- parent didn't have regs=10 stack=0 marks:\
+ mark_precise: frame0: parent state regs=r4 stack=:\
mark_precise: frame0: last_idx 4 first_idx 2\
mark_precise: frame0: regs=r4 stack= before 4\
mark_precise: frame0: regs=r4 stack= before 3\
mark_precise: frame0: regs= stack=-8 before 2\
mark_precise: frame0: falling back to forcing all scalars precise\
mark_precise: frame0: last_idx 5 first_idx 5\
- parent didn't have regs=1 stack=0 marks:",
+ mark_precise: frame0: parent state regs=r0 stack=:",
.result = VERBOSE_ACCEPT,
.retval = -1,
},
@@ -179,7 +179,7 @@
.prog_type = BPF_PROG_TYPE_XDP,
.flags = BPF_F_TEST_STATE_FREQ,
.errstr = "mark_precise: frame0: last_idx 6 first_idx 6\
- parent didn't have regs=10 stack=0 marks:\
+ mark_precise: frame0: parent state regs=r4 stack=:\
mark_precise: frame0: last_idx 5 first_idx 3\
mark_precise: frame0: regs=r4 stack= before 5\
mark_precise: frame0: regs=r4 stack= before 4\
@@ -188,7 +188,7 @@
force_precise: frame0: forcing r0 to be precise\
force_precise: frame0: forcing r0 to be precise\
mark_precise: frame0: last_idx 6 first_idx 6\
- parent didn't have regs=1 stack=0 marks:\
+ mark_precise: frame0: parent state regs=r0 stack=:\
mark_precise: frame0: last_idx 5 first_idx 3\
mark_precise: frame0: regs=r0 stack= before 5",
.result = VERBOSE_ACCEPT,
--
2.34.1
next prev parent reply other threads:[~2023-05-05 4:33 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-05-05 4:33 [PATCH v3 bpf-next 00/10] Add precision propagation for subprogs and callbacks Andrii Nakryiko
2023-05-05 4:33 ` [PATCH v3 bpf-next 01/10] veristat: add -t flag for adding BPF_F_TEST_STATE_FREQ program flag Andrii Nakryiko
2023-05-05 4:33 ` [PATCH v3 bpf-next 02/10] bpf: mark relevant stack slots scratched for register read instructions Andrii Nakryiko
2023-05-05 4:33 ` [PATCH v3 bpf-next 03/10] bpf: encapsulate precision backtracking bookkeeping Andrii Nakryiko
2023-05-05 4:33 ` [PATCH v3 bpf-next 04/10] bpf: improve precision backtrack logging Andrii Nakryiko
2023-05-05 4:33 ` Andrii Nakryiko [this message]
2023-05-05 4:33 ` [PATCH v3 bpf-next 06/10] bpf: fix propagate_precision() logic for inner frames Andrii Nakryiko
2023-05-05 4:33 ` [PATCH v3 bpf-next 07/10] bpf: fix mark_all_scalars_precise use in mark_chain_precision Andrii Nakryiko
2023-05-05 4:33 ` [PATCH v3 bpf-next 08/10] bpf: support precision propagation in the presence of subprogs Andrii Nakryiko
2023-05-05 4:33 ` [PATCH v3 bpf-next 09/10] selftests/bpf: add precision propagation tests " Andrii Nakryiko
2023-05-05 4:33 ` [PATCH v3 bpf-next 10/10] selftests/bpf: revert iter test subprog precision workaround Andrii Nakryiko
2023-05-05 5:50 ` [PATCH v3 bpf-next 00/10] Add precision propagation for subprogs and callbacks patchwork-bot+netdevbpf
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20230505043317.3629845-6-andrii@kernel.org \
--to=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=kernel-team@meta.com \
--cc=martin.lau@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox