[PATCH RFC bpf-next 0/5] Do not include the original insn in zext patchlet

[PATCH RFC bpf-next 0/5] Do not include the original insn in zext patchlet

[Ilya Leoshkevich]

Hi!

This patch series attempts to fix test_progs failure on s390, which
Yauheni reported here:

https://lore.kernel.org/bpf/20200903140542.156624-1-yauheni.kaliuta@redhat.com/

The problem is that zext code includes the instruction, whose result
needs to be zero-extended, into the zero-extension patchlet. If this
instruction happens to be a call, its delta is not adjusted, and as a
result verifier rejects the program later.

The code seems to have been written this way, because there is no helper
function to insert bpf instructions: currently one can either replace or
remove. So insertion seems to have been emulated with replacement.

Patches 1-4 teach bpf_patch_insn_data() how to insert (by accepting
variable number of old insns, which is normally 1, but can now be 0
too). Patch 5 uses this new capability to resolve the issue.

Ilya Leoshkevich (5):
  bpf: Make bpf_patch_insn_single() accept variable number of old insns
  bpf: Make adjust_insn_aux_data() accept variable number of old insns
  bpf: Make adjust_subprog_starts() accept variable number of old insns
  bpf: Make bpf_patch_insn_data() accept variable number of old insns
  bpf: Do not include the original insn in zext patchlet

 include/linux/filter.h |   4 +-
 kernel/bpf/core.c      |  18 ++++----
 kernel/bpf/verifier.c  | 100 ++++++++++++++++++++++++-----------------
 3 files changed, 70 insertions(+), 52 deletions(-)

-- 
2.25.4

[PATCH RFC bpf-next 1/5] bpf: Make bpf_patch_insn_single() accept variable number of old insns

[Ilya Leoshkevich]

Since this changes the function's meaning, rename it to
bpf_patch_insns(). It is still expected to only grow the function or
to preserve its size, not to shrink it.

Signed-off-by: Ilya Leoshkevich <iii@linux.ibm.com>
---
 include/linux/filter.h |  4 ++--
 kernel/bpf/core.c      | 18 +++++++++---------
 kernel/bpf/verifier.c  |  2 +-
 3 files changed, 12 insertions(+), 12 deletions(-)

diff --git a/include/linux/filter.h b/include/linux/filter.h
index 995625950cc1..d926ab1cfada 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -892,8 +892,8 @@ static inline bool bpf_dump_raw_ok(const struct cred *cred)
 	return kallsyms_show_value(cred);
 }
 
-struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
-				       const struct bpf_insn *patch, u32 len);
+struct bpf_prog *bpf_patch_insns(struct bpf_prog *prog, u32 off, u32 len_old,
+				 const struct bpf_insn *patch, u32 len);
 int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt);
 
 void bpf_clear_redirect_map(struct bpf_map *map);
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index ed0b3578867c..dde5f61f5a99 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -429,10 +429,10 @@ static void bpf_adj_linfo(struct bpf_prog *prog, u32 off, u32 delta)
 		linfo[i].insn_off += delta;
 }
 
-struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
-				       const struct bpf_insn *patch, u32 len)
+struct bpf_prog *bpf_patch_insns(struct bpf_prog *prog, u32 off, u32 len_old,
+				 const struct bpf_insn *patch, u32 len)
 {
-	u32 insn_adj_cnt, insn_rest, insn_delta = len - 1;
+	u32 insn_adj_cnt, insn_rest, insn_delta = len - len_old;
 	const u32 cnt_max = S16_MAX;
 	struct bpf_prog *prog_adj;
 	int err;
@@ -451,7 +451,7 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
 	 * we afterwards may not fail anymore.
 	 */
 	if (insn_adj_cnt > cnt_max &&
-	    (err = bpf_adj_branches(prog, off, off + 1, off + len, true)))
+	    (err = bpf_adj_branches(prog, off, off + len_old, off + len, true)))
 		return ERR_PTR(err);
 
 	/* Several new instructions need to be inserted. Make room
@@ -468,14 +468,13 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
 	/* Patching happens in 3 steps:
 	 *
 	 * 1) Move over tail of insnsi from next instruction onwards,
-	 *    so we can patch the single target insn with one or more
-	 *    new ones (patching is always from 1 to n insns, n > 0).
+	 *    so we can patch the target insns.
 	 * 2) Inject new instructions at the target location.
 	 * 3) Adjust branch offsets if necessary.
 	 */
 	insn_rest = insn_adj_cnt - off - len;
 
-	memmove(prog_adj->insnsi + off + len, prog_adj->insnsi + off + 1,
+	memmove(prog_adj->insnsi + off + len, prog_adj->insnsi + off + len_old,
 		sizeof(*patch) * insn_rest);
 	memcpy(prog_adj->insnsi + off, patch, sizeof(*patch) * len);
 
@@ -483,7 +482,8 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
 	 * the ship has sailed to reverse to the original state. An
 	 * overflow cannot happen at this point.
 	 */
-	BUG_ON(bpf_adj_branches(prog_adj, off, off + 1, off + len, false));
+	BUG_ON(bpf_adj_branches(prog_adj, off, off + len_old, off + len,
+				false));
 
 	bpf_adj_linfo(prog_adj, off, insn_delta);
 
@@ -1155,7 +1155,7 @@ struct bpf_prog *bpf_jit_blind_constants(struct bpf_prog *prog)
 		if (!rewritten)
 			continue;
 
-		tmp = bpf_patch_insn_single(clone, i, insn_buff, rewritten);
+		tmp = bpf_patch_insns(clone, i, 1, insn_buff, rewritten);
 		if (IS_ERR(tmp)) {
 			/* Patching may have repointed aux->prog during
 			 * realloc from the original one, so we need to
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 814bc6c1ad16..dd0b138ee382 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9628,7 +9628,7 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
 {
 	struct bpf_prog *new_prog;
 
-	new_prog = bpf_patch_insn_single(env->prog, off, patch, len);
+	new_prog = bpf_patch_insns(env->prog, off, 1, patch, len);
 	if (IS_ERR(new_prog)) {
 		if (PTR_ERR(new_prog) == -ERANGE)
 			verbose(env,
-- 
2.25.4

[PATCH RFC bpf-next 2/5] bpf: Make adjust_insn_aux_data() accept variable number of old insns

[Ilya Leoshkevich]

Since this changes the function's meaning, rename it to
adjust_insns_aux_data(). The way this function used to be implemented
for a single insn is somewhat tricky, and the new version preserves
this behavior:

1. For both fast and slow paths, populate zext_dst at [off, off +
   cnt_old) positions from insns at [off + cnt - cnt_old, off + cnt)
   positions. On the fast path, this produces identical insn_aux_data
   and insnsi offsets. On the slow path the offsets are different, but
   they will be fixed up later.
2. If the prog size did not change, return (fast path).
3. Preserve all the aux data for the leading insns.
4. Preserve all the aux data for the trailing insns, including what has
   been produced during step 1. This is done by memcpying it to a
   different offset, which corrects the difference between insn_aux_data
   and insnsi offsets.
5. Populate seen and zext_dst for the remaining insns.

Signed-off-by: Ilya Leoshkevich <iii@linux.ibm.com>
---
 kernel/bpf/verifier.c | 33 +++++++++++++++++++--------------
 1 file changed, 19 insertions(+), 14 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index dd0b138ee382..077919ac3826 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9572,25 +9572,29 @@ static void convert_pseudo_ld_imm64(struct bpf_verifier_env *env)
 			insn->src_reg = 0;
 }
 
-/* single env->prog->insni[off] instruction was replaced with the range
- * insni[off, off + cnt).  Adjust corresponding insn_aux_data by copying
- * [0, off) and [off, end) to new locations, so the patched range stays zero
+/* Instructions from the range env->prog->insni[off, off + cnt_old) were
+ * replaced with the range insni[off, off + cnt). Adjust corresponding
+ * insn_aux_data by copying [0, off) and [off, end) to new locations, so the
+ * patched range stays zero.
  */
-static int adjust_insn_aux_data(struct bpf_verifier_env *env,
-				struct bpf_prog *new_prog, u32 off, u32 cnt)
+static int adjust_insns_aux_data(struct bpf_verifier_env *env,
+				 struct bpf_prog *new_prog, u32 off,
+				 u32 cnt_old, u32 cnt)
 {
 	struct bpf_insn_aux_data *new_data, *old_data = env->insn_aux_data;
 	struct bpf_insn *insn = new_prog->insnsi;
 	u32 prog_len;
 	int i;
 
-	/* aux info at OFF always needs adjustment, no matter fast path
-	 * (cnt == 1) is taken or not. There is no guarantee INSN at OFF is the
-	 * original insn at old prog.
+	/* aux infos at [off, off + cnt_old) need adjustment even on the fast
+	 * path (cnt == cnt_old). There is no guarantee the insns at [off,
+	 * off + cnt_old) are the original ones at old prog.
 	 */
-	old_data[off].zext_dst = insn_has_def32(env, insn + off + cnt - 1);
+	for (i = off; i < off + cnt_old; i++)
+		old_data[i].zext_dst =
+			insn_has_def32(env, insn + i + cnt - cnt_old);
 
-	if (cnt == 1)
+	if (cnt == cnt_old)
 		return 0;
 	prog_len = new_prog->len;
 	new_data = vzalloc(array_size(prog_len,
@@ -9598,9 +9602,10 @@ static int adjust_insn_aux_data(struct bpf_verifier_env *env,
 	if (!new_data)
 		return -ENOMEM;
 	memcpy(new_data, old_data, sizeof(struct bpf_insn_aux_data) * off);
-	memcpy(new_data + off + cnt - 1, old_data + off,
-	       sizeof(struct bpf_insn_aux_data) * (prog_len - off - cnt + 1));
-	for (i = off; i < off + cnt - 1; i++) {
+	memcpy(new_data + off + cnt - cnt_old, old_data + off,
+	       sizeof(struct bpf_insn_aux_data) *
+		       (prog_len - off - cnt + cnt_old));
+	for (i = off; i < off + cnt - cnt_old; i++) {
 		new_data[i].seen = env->pass_cnt;
 		new_data[i].zext_dst = insn_has_def32(env, insn + i);
 	}
@@ -9636,7 +9641,7 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
 				env->insn_aux_data[off].orig_idx);
 		return NULL;
 	}
-	if (adjust_insn_aux_data(env, new_prog, off, len))
+	if (adjust_insns_aux_data(env, new_prog, off, 1, len))
 		return NULL;
 	adjust_subprog_starts(env, off, len);
 	return new_prog;
-- 
2.25.4

[PATCH RFC bpf-next 3/5] bpf: Make adjust_subprog_starts() accept variable number of old insns

[Ilya Leoshkevich]

Simply adjust the fast path condition and the delta. No renaming needed
in this case.

Signed-off-by: Ilya Leoshkevich <iii@linux.ibm.com>
---
 kernel/bpf/verifier.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 077919ac3826..6791a6e1bf76 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9614,17 +9614,18 @@ static int adjust_insns_aux_data(struct bpf_verifier_env *env,
 	return 0;
 }
 
-static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off, u32 len)
+static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off,
+				  u32 len_old, u32 len)
 {
 	int i;
 
-	if (len == 1)
+	if (len == len_old)
 		return;
 	/* NOTE: fake 'exit' subprog should be updated as well. */
 	for (i = 0; i <= env->subprog_cnt; i++) {
 		if (env->subprog_info[i].start <= off)
 			continue;
-		env->subprog_info[i].start += len - 1;
+		env->subprog_info[i].start += len - len_old;
 	}
 }
 
@@ -9643,7 +9644,7 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
 	}
 	if (adjust_insns_aux_data(env, new_prog, off, 1, len))
 		return NULL;
-	adjust_subprog_starts(env, off, len);
+	adjust_subprog_starts(env, off, 1, len);
 	return new_prog;
 }
 
-- 
2.25.4

[PATCH RFC bpf-next 4/5] bpf: Make bpf_patch_insn_data() accept variable number of old insns

[Ilya Leoshkevich]

Since this changes the function's meaning, rename it to
bpf_patch_insns_data(). There are quite a few uses - adjust them all
instead of creating a wrapper, which is not worth it in this case.

Signed-off-by: Ilya Leoshkevich <iii@linux.ibm.com>
---
 kernel/bpf/verifier.c | 44 ++++++++++++++++++++++++++-----------------
 1 file changed, 27 insertions(+), 17 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6791a6e1bf76..17c2e926e436 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9629,12 +9629,14 @@ static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off,
 	}
 }
 
-static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,
-					    const struct bpf_insn *patch, u32 len)
+static struct bpf_prog *bpf_patch_insns_data(struct bpf_verifier_env *env,
+					     u32 off, u32 len_old,
+					     const struct bpf_insn *patch,
+					     u32 len)
 {
 	struct bpf_prog *new_prog;
 
-	new_prog = bpf_patch_insns(env->prog, off, 1, patch, len);
+	new_prog = bpf_patch_insns(env->prog, off, len_old, patch, len);
 	if (IS_ERR(new_prog)) {
 		if (PTR_ERR(new_prog) == -ERANGE)
 			verbose(env,
@@ -9642,9 +9644,9 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
 				env->insn_aux_data[off].orig_idx);
 		return NULL;
 	}
-	if (adjust_insns_aux_data(env, new_prog, off, 1, len))
+	if (adjust_insns_aux_data(env, new_prog, off, len_old, len))
 		return NULL;
-	adjust_subprog_starts(env, off, 1, len);
+	adjust_subprog_starts(env, off, len_old, len);
 	return new_prog;
 }
 
@@ -9972,7 +9974,8 @@ static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 		patch = zext_patch;
 		patch_len = 2;
 apply_patch_buffer:
-		new_prog = bpf_patch_insn_data(env, adj_idx, patch, patch_len);
+		new_prog = bpf_patch_insns_data(env, adj_idx, 1, patch,
+						patch_len);
 		if (!new_prog)
 			return -ENOMEM;
 		env->prog = new_prog;
@@ -10011,7 +10014,8 @@ static int convert_ctx_accesses(struct bpf_verifier_env *env)
 			verbose(env, "bpf verifier is misconfigured\n");
 			return -EINVAL;
 		} else if (cnt) {
-			new_prog = bpf_patch_insn_data(env, 0, insn_buf, cnt);
+			new_prog =
+				bpf_patch_insns_data(env, 0, 1, insn_buf, cnt);
 			if (!new_prog)
 				return -ENOMEM;
 
@@ -10059,7 +10063,8 @@ static int convert_ctx_accesses(struct bpf_verifier_env *env)
 			};
 
 			cnt = ARRAY_SIZE(patch);
-			new_prog = bpf_patch_insn_data(env, i + delta, patch, cnt);
+			new_prog = bpf_patch_insns_data(env, i + delta, 1,
+							patch, cnt);
 			if (!new_prog)
 				return -ENOMEM;
 
@@ -10157,7 +10162,8 @@ static int convert_ctx_accesses(struct bpf_verifier_env *env)
 			}
 		}
 
-		new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
+		new_prog =
+			bpf_patch_insns_data(env, i + delta, 1, insn_buf, cnt);
 		if (!new_prog)
 			return -ENOMEM;
 
@@ -10435,7 +10441,8 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env)
 				cnt = ARRAY_SIZE(mask_and_mod) - (is64 ? 1 : 0);
 			}
 
-			new_prog = bpf_patch_insn_data(env, i + delta, patchlet, cnt);
+			new_prog = bpf_patch_insns_data(env, i + delta, 1,
+							patchlet, cnt);
 			if (!new_prog)
 				return -ENOMEM;
 
@@ -10454,7 +10461,8 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env)
 				return -EINVAL;
 			}
 
-			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
+			new_prog = bpf_patch_insns_data(env, i + delta, 1,
+							insn_buf, cnt);
 			if (!new_prog)
 				return -ENOMEM;
 
@@ -10506,7 +10514,8 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env)
 				*patch++ = BPF_ALU64_IMM(BPF_MUL, off_reg, -1);
 			cnt = patch - insn_buf;
 
-			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
+			new_prog = bpf_patch_insns_data(env, i + delta, 1,
+							insn_buf, cnt);
 			if (!new_prog)
 				return -ENOMEM;
 
@@ -10590,7 +10599,8 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env)
 								 map)->index_mask);
 			insn_buf[2] = *insn;
 			cnt = 3;
-			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
+			new_prog = bpf_patch_insns_data(env, i + delta, 1,
+							insn_buf, cnt);
 			if (!new_prog)
 				return -ENOMEM;
 
@@ -10625,8 +10635,8 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env)
 					return -EINVAL;
 				}
 
-				new_prog = bpf_patch_insn_data(env, i + delta,
-							       insn_buf, cnt);
+				new_prog = bpf_patch_insns_data(
+					env, i + delta, 1, insn_buf, cnt);
 				if (!new_prog)
 					return -ENOMEM;
 
@@ -10694,8 +10704,8 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env)
 						  BPF_REG_0, 0);
 			cnt = 3;
 
-			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf,
-						       cnt);
+			new_prog = bpf_patch_insns_data(env, i + delta, 1,
+							insn_buf, cnt);
 			if (!new_prog)
 				return -ENOMEM;
 
-- 
2.25.4

[PATCH RFC bpf-next 5/5] bpf: Do not include the original insn in zext patchlet

[Ilya Leoshkevich]

If the original insn is a jump, then it is not subjected to branch
adjustment, which is incorrect. As discovered by Yauheni in

https://lore.kernel.org/bpf/20200903140542.156624-1-yauheni.kaliuta@redhat.com/

this causes `test_progs -t global_funcs` failures on s390.

Most likely, the current code includes the original insn in the
patchlet, because there was no infrastructure to insert new insns, only
to replace the existing ones. Now that bpf_patch_insns_data() can do
insertions, stop including the original insns in zext patchlets.

Fixes: a4b1d3c1ddf6 ("bpf: verifier: insert zero extension according to analysis result")
Reported-by: Yauheni Kaliuta <yauheni.kaliuta@redhat.com>
Signed-off-by: Ilya Leoshkevich <iii@linux.ibm.com>
---
 kernel/bpf/verifier.c | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 17c2e926e436..64a04953c631 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9911,7 +9911,7 @@ static int opt_remove_nops(struct bpf_verifier_env *env)
 static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 					 const union bpf_attr *attr)
 {
-	struct bpf_insn *patch, zext_patch[2], rnd_hi32_patch[4];
+	struct bpf_insn *patch, zext_patch, rnd_hi32_patch[4];
 	struct bpf_insn_aux_data *aux = env->insn_aux_data;
 	int i, patch_len, delta = 0, len = env->prog->len;
 	struct bpf_insn *insns = env->prog->insnsi;
@@ -9919,13 +9919,14 @@ static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 	bool rnd_hi32;
 
 	rnd_hi32 = attr->prog_flags & BPF_F_TEST_RND_HI32;
-	zext_patch[1] = BPF_ZEXT_REG(0);
+	zext_patch = BPF_ZEXT_REG(0);
 	rnd_hi32_patch[1] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_AX, 0);
 	rnd_hi32_patch[2] = BPF_ALU64_IMM(BPF_LSH, BPF_REG_AX, 32);
 	rnd_hi32_patch[3] = BPF_ALU64_REG(BPF_OR, 0, BPF_REG_AX);
 	for (i = 0; i < len; i++) {
 		int adj_idx = i + delta;
 		struct bpf_insn insn;
+		int len_old = 1;
 
 		insn = insns[adj_idx];
 		if (!aux[adj_idx].zext_dst) {
@@ -9968,20 +9969,21 @@ static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 		if (!bpf_jit_needs_zext())
 			continue;
 
-		zext_patch[0] = insn;
-		zext_patch[1].dst_reg = insn.dst_reg;
-		zext_patch[1].src_reg = insn.dst_reg;
-		patch = zext_patch;
-		patch_len = 2;
+		zext_patch.dst_reg = insn.dst_reg;
+		zext_patch.src_reg = insn.dst_reg;
+		patch = &zext_patch;
+		patch_len = 1;
+		adj_idx++;
+		len_old = 0;
 apply_patch_buffer:
-		new_prog = bpf_patch_insns_data(env, adj_idx, 1, patch,
+		new_prog = bpf_patch_insns_data(env, adj_idx, len_old, patch,
 						patch_len);
 		if (!new_prog)
 			return -ENOMEM;
 		env->prog = new_prog;
 		insns = new_prog->insnsi;
 		aux = env->insn_aux_data;
-		delta += patch_len - 1;
+		delta += patch_len - len_old;
 	}
 
 	return 0;
-- 
2.25.4

Re: [PATCH RFC bpf-next 5/5] bpf: Do not include the original insn in zext patchlet

[Yauheni Kaliuta]

Hi, Ilya!

Cool, thanks!

Shouldn't the rnd patch be done the same way for completeness?
Even if it is unlikely there to hit the problem.

>>>>> On Thu, 10 Sep 2020 01:34:39 +0200, Ilya Leoshkevich  wrote:

 > If the original insn is a jump, then it is not subjected to branch
 > adjustment, which is incorrect. As discovered by Yauheni in

 > https://lore.kernel.org/bpf/20200903140542.156624-1-yauheni.kaliuta@redhat.com/

 > this causes `test_progs -t global_funcs` failures on s390.

 > Most likely, the current code includes the original insn in the
 > patchlet, because there was no infrastructure to insert new insns, only
 > to replace the existing ones. Now that bpf_patch_insns_data() can do
 > insertions, stop including the original insns in zext patchlets.

 > Fixes: a4b1d3c1ddf6 ("bpf: verifier: insert zero extension according
 > to analysis result")
 > Reported-by: Yauheni Kaliuta <yauheni.kaliuta@redhat.com>
 > Signed-off-by: Ilya Leoshkevich <iii@linux.ibm.com>
 > ---
 >  kernel/bpf/verifier.c | 20 +++++++++++---------
 >  1 file changed, 11 insertions(+), 9 deletions(-)

 > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
 > index 17c2e926e436..64a04953c631 100644
 > --- a/kernel/bpf/verifier.c
 > +++ b/kernel/bpf/verifier.c
 > @@ -9911,7 +9911,7 @@ static int opt_remove_nops(struct bpf_verifier_env *env)
 >  static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 >  					 const union bpf_attr *attr)
 >  {
 > -	struct bpf_insn *patch, zext_patch[2], rnd_hi32_patch[4];
 > +	struct bpf_insn *patch, zext_patch, rnd_hi32_patch[4];
 >  	struct bpf_insn_aux_data *aux = env->insn_aux_data;
 >  	int i, patch_len, delta = 0, len = env->prog->len;
 >  	struct bpf_insn *insns = env->prog->insnsi;
 > @@ -9919,13 +9919,14 @@ static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 >  	bool rnd_hi32;
 
 >  	rnd_hi32 = attr->prog_flags & BPF_F_TEST_RND_HI32;
 > -	zext_patch[1] = BPF_ZEXT_REG(0);
 > +	zext_patch = BPF_ZEXT_REG(0);
 >  	rnd_hi32_patch[1] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_AX, 0);
 >  	rnd_hi32_patch[2] = BPF_ALU64_IMM(BPF_LSH, BPF_REG_AX, 32);
 >  	rnd_hi32_patch[3] = BPF_ALU64_REG(BPF_OR, 0, BPF_REG_AX);
 >  	for (i = 0; i < len; i++) {
 >  		int adj_idx = i + delta;
 >  		struct bpf_insn insn;
 > +		int len_old = 1;
 
 >  		insn = insns[adj_idx];
 >  		if (!aux[adj_idx].zext_dst) {
 > @@ -9968,20 +9969,21 @@ static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 >  		if (!bpf_jit_needs_zext())
 >  			continue;
 
 > -		zext_patch[0] = insn;
 > -		zext_patch[1].dst_reg = insn.dst_reg;
 > -		zext_patch[1].src_reg = insn.dst_reg;
 > -		patch = zext_patch;
 > -		patch_len = 2;
 > +		zext_patch.dst_reg = insn.dst_reg;
 > +		zext_patch.src_reg = insn.dst_reg;
 > +		patch = &zext_patch;
 > +		patch_len = 1;
 > +		adj_idx++;
 > +		len_old = 0;
 >  apply_patch_buffer:
 > -		new_prog = bpf_patch_insns_data(env, adj_idx, 1, patch,
 > +		new_prog = bpf_patch_insns_data(env, adj_idx, len_old, patch,
 >  						patch_len);
 >  		if (!new_prog)
 >  			return -ENOMEM;
 env-> prog = new_prog;
 >  		insns = new_prog->insnsi;
 >  		aux = env->insn_aux_data;
 > -		delta += patch_len - 1;
 > +		delta += patch_len - len_old;
 >  	}
 
 >  	return 0;
 > -- 

 > 2.25.4


-- 
WBR,
Yauheni Kaliuta

Re: [PATCH RFC bpf-next 5/5] bpf: Do not include the original insn in zext patchlet

[Ilya Leoshkevich]

On Thu, 2020-09-10 at 09:59 +0300, Yauheni Kaliuta wrote:
> Hi, Ilya!
> 
> Cool, thanks!
> 
> Shouldn't the rnd patch be done the same way for completeness?
> Even if it is unlikely there to hit the problem.

Ah, I haven't noticed that this pattern used elsewhere as well -
I just checked and found 4 places. Let's wait and see whether the whole
approach is acceptable, if yes, then I'll make patches that clean up
these occurrences.

> 
> > > > > > On Thu, 10 Sep 2020 01:34:39 +0200, Ilya
> > > > > > Leoshkevich  wrote:
> 
>  > If the original insn is a jump, then it is not subjected to branch
>  > adjustment, which is incorrect. As discovered by Yauheni in
> 
>  > 
> https://lore.kernel.org/bpf/20200903140542.156624-1-yauheni.kaliuta@redhat.com/
> 
>  > this causes `test_progs -t global_funcs` failures on s390.
> 
>  > Most likely, the current code includes the original insn in the
>  > patchlet, because there was no infrastructure to insert new insns,
> only
>  > to replace the existing ones. Now that bpf_patch_insns_data() can
> do
>  > insertions, stop including the original insns in zext patchlets.
> 
>  > Fixes: a4b1d3c1ddf6 ("bpf: verifier: insert zero extension
> according
>  > to analysis result")
>  > Reported-by: Yauheni Kaliuta <yauheni.kaliuta@redhat.com>
>  > Signed-off-by: Ilya Leoshkevich <iii@linux.ibm.com>
>  > ---
>  >  kernel/bpf/verifier.c | 20 +++++++++++---------
>  >  1 file changed, 11 insertions(+), 9 deletions(-)
> 
>  > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>  > index 17c2e926e436..64a04953c631 100644
>  > --- a/kernel/bpf/verifier.c
>  > +++ b/kernel/bpf/verifier.c
>  > @@ -9911,7 +9911,7 @@ static int opt_remove_nops(struct
> bpf_verifier_env *env)
>  >  static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env
> *env,
>  >  					 const union bpf_attr *attr)
>  >  {
>  > -	struct bpf_insn *patch, zext_patch[2], rnd_hi32_patch[4];
>  > +	struct bpf_insn *patch, zext_patch, rnd_hi32_patch[4];
>  >  	struct bpf_insn_aux_data *aux = env->insn_aux_data;
>  >  	int i, patch_len, delta = 0, len = env->prog->len;
>  >  	struct bpf_insn *insns = env->prog->insnsi;
>  > @@ -9919,13 +9919,14 @@ static int
> opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
>  >  	bool rnd_hi32;
>  
>  >  	rnd_hi32 = attr->prog_flags & BPF_F_TEST_RND_HI32;
>  > -	zext_patch[1] = BPF_ZEXT_REG(0);
>  > +	zext_patch = BPF_ZEXT_REG(0);
>  >  	rnd_hi32_patch[1] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_AX, 0);
>  >  	rnd_hi32_patch[2] = BPF_ALU64_IMM(BPF_LSH, BPF_REG_AX, 32);
>  >  	rnd_hi32_patch[3] = BPF_ALU64_REG(BPF_OR, 0, BPF_REG_AX);
>  >  	for (i = 0; i < len; i++) {
>  >  		int adj_idx = i + delta;
>  >  		struct bpf_insn insn;
>  > +		int len_old = 1;
>  
>  >  		insn = insns[adj_idx];
>  >  		if (!aux[adj_idx].zext_dst) {
>  > @@ -9968,20 +9969,21 @@ static int
> opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
>  >  		if (!bpf_jit_needs_zext())
>  >  			continue;
>  
>  > -		zext_patch[0] = insn;
>  > -		zext_patch[1].dst_reg = insn.dst_reg;
>  > -		zext_patch[1].src_reg = insn.dst_reg;
>  > -		patch = zext_patch;
>  > -		patch_len = 2;
>  > +		zext_patch.dst_reg = insn.dst_reg;
>  > +		zext_patch.src_reg = insn.dst_reg;
>  > +		patch = &zext_patch;
>  > +		patch_len = 1;
>  > +		adj_idx++;
>  > +		len_old = 0;
>  >  apply_patch_buffer:
>  > -		new_prog = bpf_patch_insns_data(env, adj_idx, 1, patch,
>  > +		new_prog = bpf_patch_insns_data(env, adj_idx, len_old,
> patch,
>  >  						patch_len);
>  >  		if (!new_prog)
>  >  			return -ENOMEM;
>  env-> prog = new_prog;
>  >  		insns = new_prog->insnsi;
>  >  		aux = env->insn_aux_data;
>  > -		delta += patch_len - 1;
>  > +		delta += patch_len - len_old;
>  >  	}
>  
>  >  	return 0;
>  > -- 
> 
>  > 2.25.4
> 
> 

Re: [PATCH RFC bpf-next 5/5] bpf: Do not include the original insn in zext patchlet

[Alexei Starovoitov]

On Wed, Sep 9, 2020 at 4:37 PM Ilya Leoshkevich <iii@linux.ibm.com> wrote:
>
> If the original insn is a jump, then it is not subjected to branch
> adjustment, which is incorrect. As discovered by Yauheni in

I think the problem is elsewhere.
Something is wrong with zext logic.
the branch insn should not have been marked as zext_dst.
and in the line:
zext_patch[0] = insn;
this 'insn' should never be a branch.
See insn_no_def().

Re: [PATCH RFC bpf-next 5/5] bpf: Do not include the original insn in zext patchlet

[Yauheni Kaliuta]

Hi, Alexei!

>>>>> On Thu, 10 Sep 2020 17:25:43 -0700, Alexei Starovoitov  wrote:

 > On Wed, Sep 9, 2020 at 4:37 PM Ilya Leoshkevich <iii@linux.ibm.com> wrote:
 >> 
 >> If the original insn is a jump, then it is not subjected to branch
 >> adjustment, which is incorrect. As discovered by Yauheni in

 > I think the problem is elsewhere.
 > Something is wrong with zext logic.
 > the branch insn should not have been marked as zext_dst.
 > and in the line:
 > zext_patch[0] = insn;
 > this 'insn' should never be a branch.
 > See insn_no_def().

Yes, it may be the case, as I mentioned in my analysis, but the
patching itself looks much more clear with Ilya's changes.

-- 
WBR,
Yauheni Kaliuta

Re: [PATCH RFC bpf-next 5/5] bpf: Do not include the original insn in zext patchlet

[Ilya Leoshkevich]

On Thu, 2020-09-10 at 17:25 -0700, Alexei Starovoitov wrote:
> On Wed, Sep 9, 2020 at 4:37 PM Ilya Leoshkevich <iii@linux.ibm.com>
> wrote:
> > If the original insn is a jump, then it is not subjected to branch
> > adjustment, which is incorrect. As discovered by Yauheni in
> 
> I think the problem is elsewhere.
> Something is wrong with zext logic.
> the branch insn should not have been marked as zext_dst.
> and in the line:
> zext_patch[0] = insn;
> this 'insn' should never be a branch.
> See insn_no_def().

Would it make sense to add a WARN_ON(insn_no_def(&insn)) there?


I believe the root cause is triggered by clear_caller_saved_regs().

This is our prog:

[     0]: BPF_JMP | BPF_CALL | BPF_K, BPF_REG_0, BPF_REG_1, 0x0, 0x1
[     1]: BPF_JMP | BPF_EXIT | BPF_K, BPF_REG_0, BPF_REG_0, 0x0, 0x0
[     2]: BPF_JMP | BPF_CALL | BPF_K, BPF_REG_0, BPF_REG_1, 0x0, 0x1
[     3]: BPF_JMP | BPF_EXIT | BPF_K, BPF_REG_0, BPF_REG_0, 0x0, 0x0
...

and env->insn_idx is 2. clear_caller_saved_regs() calls

	check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);

for register 0, and then inside check_reg_arg() we come to

	reg->subreg_def = rw64 ? DEF_NOT_SUBREG : env->insn_idx + 1;

where rw64 is false, because insn 2 is a BPF_PSEUDO_CALL. Having
non-zero subreg_def causes mark_insn_zext() to set zext_dst later on.

Maybe mark_reg_unknown() can do something to prevent this? My knee-jerk
reaction would be to set subreg_def to 0 there, but I'm not sure
whether this would be correct.

Re: [PATCH RFC bpf-next 5/5] bpf: Do not include the original insn in zext patchlet

[Ilya Leoshkevich]

On Fri, 2020-09-11 at 14:58 +0200, Ilya Leoshkevich wrote:
> On Thu, 2020-09-10 at 17:25 -0700, Alexei Starovoitov wrote:
> > On Wed, Sep 9, 2020 at 4:37 PM Ilya Leoshkevich <iii@linux.ibm.com>
> > wrote:
> > > If the original insn is a jump, then it is not subjected to
> > > branch
> > > adjustment, which is incorrect. As discovered by Yauheni in
> > 
> > I think the problem is elsewhere.
> > Something is wrong with zext logic.
> > the branch insn should not have been marked as zext_dst.
> > and in the line:
> > zext_patch[0] = insn;
> > this 'insn' should never be a branch.
> > See insn_no_def().
> 
> Would it make sense to add a WARN_ON(insn_no_def(&insn)) there?
> 
> 
> I believe the root cause is triggered by clear_caller_saved_regs().
> 
> This is our prog:
> 
> [     0]: BPF_JMP | BPF_CALL | BPF_K, BPF_REG_0, BPF_REG_1, 0x0, 0x1
> [     1]: BPF_JMP | BPF_EXIT | BPF_K, BPF_REG_0, BPF_REG_0, 0x0, 0x0
> [     2]: BPF_JMP | BPF_CALL | BPF_K, BPF_REG_0, BPF_REG_1, 0x0, 0x1
> [     3]: BPF_JMP | BPF_EXIT | BPF_K, BPF_REG_0, BPF_REG_0, 0x0, 0x0
> ...
> 
> and env->insn_idx is 2. clear_caller_saved_regs() calls
> 
> 	check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
> 
> for register 0, and then inside check_reg_arg() we come to
> 
> 	reg->subreg_def = rw64 ? DEF_NOT_SUBREG : env->insn_idx + 1;
> 
> where rw64 is false, because insn 2 is a BPF_PSEUDO_CALL. Having
> non-zero subreg_def causes mark_insn_zext() to set zext_dst later on.
> 
> Maybe mark_reg_unknown() can do something to prevent this? My knee-
> jerk
> reaction would be to set subreg_def to 0 there, but I'm not sure
> whether this would be correct.

Another possible fix (inspired by helper function call handling) is:

--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4751,6 +4751,7 @@ static int check_func_call(struct
bpf_verifier_env *env, struct bpf_insn *insn,
 
                        /* All global functions return SCALAR_VALUE */
                        mark_reg_unknown(env, caller->regs, BPF_REG_0);
+                       caller->regs[BPF_REG_0].subreg_def =
DEF_NOT_SUBREG;
 
                        /* continue with next insn after call */
                        return 0;

This relies on global functions always returning 64-bit values, which
I believe should always be the case.

If this sounds reasonable, I can send a proper patch.