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 v2 bpf-next 05/10] bpf: maintain bitmasks across all active frames in __mark_chain_precision
Date: Thu, 4 May 2023 17:09:03 -0700 [thread overview]
Message-ID: <20230505000908.1265044-6-andrii@kernel.org> (raw)
In-Reply-To: <20230505000908.1265044-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 4ede7c9bf477..d373f472406b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3752,7 +3752,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;
@@ -3861,56 +3861,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 0:09 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-05-05 0:08 [PATCH v2 bpf-next 00/10] Add precision propagation for subprogs and callbacks Andrii Nakryiko
2023-05-05 0:08 ` [PATCH v2 bpf-next 01/10] veristat: add -t flag for adding BPF_F_TEST_STATE_FREQ program flag Andrii Nakryiko
2023-05-05 0:09 ` [PATCH v2 bpf-next 02/10] bpf: mark relevant stack slots scratched for register read instructions Andrii Nakryiko
2023-05-05 0:09 ` [PATCH v2 bpf-next 03/10] bpf: encapsulate precision backtracking bookkeeping Andrii Nakryiko
2023-05-05 1:54 ` Alexei Starovoitov
2023-05-05 4:08 ` Andrii Nakryiko
2023-05-05 0:09 ` [PATCH v2 bpf-next 04/10] bpf: improve precision backtrack logging Andrii Nakryiko
2023-05-05 0:09 ` Andrii Nakryiko [this message]
2023-05-05 0:09 ` [PATCH v2 bpf-next 06/10] bpf: fix propagate_precision() logic for inner frames Andrii Nakryiko
2023-05-05 0:09 ` [PATCH v2 bpf-next 07/10] bpf: fix mark_all_scalars_precise use in mark_chain_precision Andrii Nakryiko
2023-05-05 0:09 ` [PATCH v2 bpf-next 08/10] bpf: support precision propagation in the presence of subprogs Andrii Nakryiko
2023-05-05 0:09 ` [PATCH v2 bpf-next 09/10] selftests/bpf: add precision propagation tests " Andrii Nakryiko
2023-05-05 0:09 ` [PATCH v2 bpf-next 10/10] selftests/bpf: revert iter test subprog precision workaround Andrii Nakryiko
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=20230505000908.1265044-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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.