Skip to contentSkip to conversation

bpf: Account for BPF_FETCH in insn_has_def32()

PATCH Superseded Ilya Leoshkevich 3 participants 4 messages Feb 26, 2021 – Mar 1, 2021

Subsystems (2)

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

PATCH v2 1/1 bpf: Account for BPF_FETCH in insn_has_def32()

insn_has_def32() returns false for 32-bit BPF_FETCH insns. This makes adjust_insn_aux_data() incorrectly set zext_dst, as can be seen in [1]. This happens because insn_no_def() does not know about the BPF_FETCH variants of BPF_STX.

Fix in two steps.

First, replace insn_no_def() with insn_def_regno(), which returns the register an insn defines. Normally insn_no_def() calls are followed by insn->dst_reg uses; replace those with the insn_def_regno() return value.

Second, adjust the BPF_STX special case in is_reg64() to deal with queries made from opt_subreg_zext_lo32_rnd_hi32(), where the state information is no longer available. Add a comment, since the purpose of this special case is not clear at first glance.

[1] https://lore.kernel.org/bpf/[email protected]/

Fixes 5ffa25502b5a ("bpf: Add instructions for atomic_[cmp]xchg")

---

v1: https://lore.kernel.org/bpf/[email protected]/
v1 -> v2: Per Martin's comments: rebase against the bpf branch, fix the
Fixes: tag, fix the comment style, replace ?: with the more readable if-else, handle the internal verifier error using WARN_ON_ONCE(), verbose() and -EFAULT.

 kernel/bpf/verifier.c | 70 ++++++++++++++++++++++++-------------------
 1 file changed, 39 insertions(+), 31 deletions(-)
kernel/bpf/verifier.c +39 -31
index 3d34ba492d46..4730d5628b02 100644
@@ -1703,7 +1703,11 @@ static bool is_reg64(struct bpf_verifier_env *env, struct bpf_insn *insn,
 	}
 
 	if (class == BPF_STX) {
-		if (reg->type != SCALAR_VALUE)
+		/* BPF_STX (including atomic variants) has multiple source
+		 * operands, one of which is a ptr. Check whether the caller is
+		 * asking about it.
+		 */
+		if (t == SRC_OP && reg->type != SCALAR_VALUE)
 			return true;
 		return BPF_SIZE(code) == BPF_DW;
 	}
@@ -1735,22 +1739,38 @@ static bool is_reg64(struct bpf_verifier_env *env, struct bpf_insn *insn,
 	return true;
 }
 
-/* Return TRUE if INSN doesn't have explicit value define. */
-static bool insn_no_def(struct bpf_insn *insn)
+/* Return the regno defined by the insn, or -1. */
+static int insn_def_regno(const struct bpf_insn *insn)
 {
-	u8 class = BPF_CLASS(insn->code);
-
-	return (class == BPF_JMP || class == BPF_JMP32 ||
-		class == BPF_STX || class == BPF_ST);
+	switch (BPF_CLASS(insn->code)) {
+	case BPF_JMP:
+	case BPF_JMP32:
+	case BPF_ST:
+		return -1;
+	case BPF_STX:
+		if (BPF_MODE(insn->code) == BPF_ATOMIC &&
+		    (insn->imm & BPF_FETCH)) {
+			if (insn->imm == BPF_CMPXCHG)
+				return BPF_REG_0;
+			else
+				return insn->src_reg;
+		} else {
+			return -1;
+		}
+	default:
+		return insn->dst_reg;
+	}
 }
 
 /* Return TRUE if INSN has defined any 32-bit value explicitly. */
 static bool insn_has_def32(struct bpf_verifier_env *env, struct bpf_insn *insn)
 {
-	if (insn_no_def(insn))
+	int dst_reg = insn_def_regno(insn);
+
+	if (dst_reg == -1)
 		return false;
 
-	return !is_reg64(env, insn, insn->dst_reg, NULL, DST_OP);
+	return !is_reg64(env, insn, dst_reg, NULL, DST_OP);
 }
 
 static void mark_insn_zext(struct bpf_verifier_env *env,
@@ -11006,9 +11026,10 @@ static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 	for (i = 0; i < len; i++) {
 		int adj_idx = i + delta;
 		struct bpf_insn insn;
-		u8 load_reg;
+		int load_reg;
 
 		insn = insns[adj_idx];
+		load_reg = insn_def_regno(&insn);
 		if (!aux[adj_idx].zext_dst) {
 			u8 code, class;
 			u32 imm_rnd;
@@ -11018,14 +11039,14 @@ static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 
 			code = insn.code;
 			class = BPF_CLASS(code);
-			if (insn_no_def(&insn))
+			if (load_reg == -1)
 				continue;
 
 			/* NOTE: arg "reg" (the fourth one) is only used for
-			 *       BPF_STX which has been ruled out in above
-			 *       check, it is safe to pass NULL here.
+			 *       BPF_STX + SRC_OP, so it is safe to pass NULL
+			 *       here.
 			 */
-			if (is_reg64(env, &insn, insn.dst_reg, NULL, DST_OP)) {
+			if (is_reg64(env, &insn, load_reg, NULL, DST_OP)) {
 				if (class == BPF_LD &&
 				    BPF_MODE(code) == BPF_IMM)
 					i++;
@@ -11040,7 +11061,7 @@ static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 			imm_rnd = get_random_int();
 			rnd_hi32_patch[0] = insn;
 			rnd_hi32_patch[1].imm = imm_rnd;
-			rnd_hi32_patch[3].dst_reg = insn.dst_reg;
+			rnd_hi32_patch[3].dst_reg = load_reg;
 			patch = rnd_hi32_patch;
 			patch_len = 4;
 			goto apply_patch_buffer;
@@ -11049,22 +11070,9 @@ static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 		if (!bpf_jit_needs_zext())
 			continue;
 
-		/* zext_dst means that we want to zero-extend whatever register
-		 * the insn defines, which is dst_reg most of the time, with
-		 * the notable exception of BPF_STX + BPF_ATOMIC + BPF_FETCH.
-		 */
-		if (BPF_CLASS(insn.code) == BPF_STX &&
-		    BPF_MODE(insn.code) == BPF_ATOMIC) {
-			/* BPF_STX + BPF_ATOMIC insns without BPF_FETCH do not
-			 * define any registers, therefore zext_dst cannot be
-			 * set.
-			 */
-			if (WARN_ON(!(insn.imm & BPF_FETCH)))
-				return -EINVAL;
-			load_reg = insn.imm == BPF_CMPXCHG ? BPF_REG_0
-							   : insn.src_reg;
-		} else {
-			load_reg = insn.dst_reg;
+		if (WARN_ON_ONCE(load_reg == -1)) {
+			verbose(env, "zext_dst is set, but no reg is defined\n");
+			return -EFAULT;
 		}
 
 		zext_patch[0] = insn;
Signature · 1 line
2.29.2
Acked-by on v2 1/1
#1 lore raw
Quoted 21 lines · Ilya Leoshkevich

insn_has_def32() returns false for 32-bit BPF_FETCH insns. This makes adjust_insn_aux_data() incorrectly set zext_dst, as can be seen in [1]. This happens because insn_no_def() does not know about the BPF_FETCH variants of BPF_STX.

Fix in two steps.

First, replace insn_no_def() with insn_def_regno(), which returns the register an insn defines. Normally insn_no_def() calls are followed by insn->dst_reg uses; replace those with the insn_def_regno() return value.

Second, adjust the BPF_STX special case in is_reg64() to deal with queries made from opt_subreg_zext_lo32_rnd_hi32(), where the state information is no longer available. Add a comment, since the purpose of this special case is not clear at first glance.

[1] https://lore.kernel.org/bpf/[email protected]/

Fixes 5ffa25502b5a ("bpf: Add instructions for atomic_[cmp]xchg")
Quoted 7 lines

---

v1: https://lore.kernel.org/bpf/[email protected]/
v1 -> v2: Per Martin's comments: rebase against the bpf branch, fix the
Fixes: tag, fix the comment style, replace ?: with the more readable if-else, handle the internal verifier error using WARN_ON_ONCE(), verbose() and -EFAULT.

#2 lore raw
In reply to Ilya Leoshkevich

Hi, sorry it's been almost a week since I responded - I think I need to adjust my sense of urgency for this stuff.

Quoted 98 lines · Ilya Leoshkevich

insn_has_def32() returns false for 32-bit BPF_FETCH insns. This makes adjust_insn_aux_data() incorrectly set zext_dst, as can be seen in [1]. This happens because insn_no_def() does not know about the BPF_FETCH variants of BPF_STX.

Fix in two steps.

First, replace insn_no_def() with insn_def_regno(), which returns the register an insn defines. Normally insn_no_def() calls are followed by insn->dst_reg uses; replace those with the insn_def_regno() return value.

Second, adjust the BPF_STX special case in is_reg64() to deal with queries made from opt_subreg_zext_lo32_rnd_hi32(), where the state information is no longer available. Add a comment, since the purpose of this special case is not clear at first glance.

[1] https://lore.kernel.org/bpf/[email protected]/

Fixes 5ffa25502b5a ("bpf: Add instructions for atomic_[cmp]xchg")

---

v1: https://lore.kernel.org/bpf/[email protected]/
v1 -> v2: Per Martin's comments: rebase against the bpf branch, fix the
Fixes: tag, fix the comment style, replace ?: with the more readable if-else, handle the internal verifier error using WARN_ON_ONCE(), verbose() and -EFAULT.

 kernel/bpf/verifier.c | 70 ++++++++++++++++++++++++-------------------
 1 file changed, 39 insertions(+), 31 deletions(-)
kernel/bpf/verifier.c +29 -9
index 3d34ba492d46..4730d5628b02 100644
@@ -1703,7 +1703,11 @@ static bool is_reg64(struct bpf_verifier_env *env, struct bpf_insn *insn,
        }
 
        if (class == BPF_STX) {
-               if (reg->type != SCALAR_VALUE)
+               /* BPF_STX (including atomic variants) has multiple source
+                * operands, one of which is a ptr. Check whether the caller is
+                * asking about it.
+                */
+               if (t == SRC_OP && reg->type != SCALAR_VALUE)
                        return true;
                return BPF_SIZE(code) == BPF_DW;
        }
@@ -1735,22 +1739,38 @@ static bool is_reg64(struct bpf_verifier_env *env, struct bpf_insn *insn,
        return true;
 }
 
-/* Return TRUE if INSN doesn't have explicit value define. */
-static bool insn_no_def(struct bpf_insn *insn)
+/* Return the regno defined by the insn, or -1. */
+static int insn_def_regno(const struct bpf_insn *insn)
 {
-       u8 class = BPF_CLASS(insn->code);
-
-       return (class == BPF_JMP || class == BPF_JMP32 ||
-               class == BPF_STX || class == BPF_ST);
+       switch (BPF_CLASS(insn->code)) {
+       case BPF_JMP:
+       case BPF_JMP32:
+       case BPF_ST:
+               return -1;
+       case BPF_STX:
+               if (BPF_MODE(insn->code) == BPF_ATOMIC &&
+                   (insn->imm & BPF_FETCH)) {
+                       if (insn->imm == BPF_CMPXCHG)
+                               return BPF_REG_0;
+                       else
+                               return insn->src_reg;
+               } else {
+                       return -1;
+               }
+       default:
+               return insn->dst_reg;
+       }
 }
 
 /* Return TRUE if INSN has defined any 32-bit value explicitly. */
 static bool insn_has_def32(struct bpf_verifier_env *env, struct bpf_insn *insn)
 {
-       if (insn_no_def(insn))
+       int dst_reg = insn_def_regno(insn);
+
+       if (dst_reg == -1)
                return false;
 
-       return !is_reg64(env, insn, insn->dst_reg, NULL, DST_OP);
+       return !is_reg64(env, insn, dst_reg, NULL, DST_OP);
 }
 
 static void mark_insn_zext(struct bpf_verifier_env *env,

kernel/bpf/verifier.c static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env, · line 11032

Quoted 8 lines
kernel/bpf/verifier.c +2 -1
@@ -11006,9 +11026,10 @@ static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
        for (i = 0; i < len; i++) {
                int adj_idx = i + delta;
                struct bpf_insn insn;
-               u8 load_reg;
+               int load_reg;
 
                insn = insns[adj_idx];
+               load_reg = insn_def_regno(&insn);

Nit: Might as well save a line by squashing this into the declaration.

Quoted 43 lines
kernel/bpf/verifier.c +5 -13
                if (!aux[adj_idx].zext_dst) {
                        u8 code, class;
                        u32 imm_rnd;
@@ -11018,14 +11039,14 @@ static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 
                        code = insn.code;
                        class = BPF_CLASS(code);
-                       if (insn_no_def(&insn))
+                       if (load_reg == -1)
                                continue;
 
                        /* NOTE: arg "reg" (the fourth one) is only used for
-                        *       BPF_STX which has been ruled out in above
-                        *       check, it is safe to pass NULL here.
+                        *       BPF_STX + SRC_OP, so it is safe to pass NULL
+                        *       here.
                         */
-                       if (is_reg64(env, &insn, insn.dst_reg, NULL, DST_OP)) {
+                       if (is_reg64(env, &insn, load_reg, NULL, DST_OP)) {
                                if (class == BPF_LD &&
                                    BPF_MODE(code) == BPF_IMM)
                                        i++;
@@ -11040,7 +11061,7 @@ static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
                        imm_rnd = get_random_int();
                        rnd_hi32_patch[0] = insn;
                        rnd_hi32_patch[1].imm = imm_rnd;
-                       rnd_hi32_patch[3].dst_reg = insn.dst_reg;
+                       rnd_hi32_patch[3].dst_reg = load_reg;
                        patch = rnd_hi32_patch;
                        patch_len = 4;
                        goto apply_patch_buffer;
@@ -11049,22 +11070,9 @@ static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
                if (!bpf_jit_needs_zext())
                        continue;
 
-               /* zext_dst means that we want to zero-extend whatever register
-                * the insn defines, which is dst_reg most of the time, with
-                * the notable exception of BPF_STX + BPF_ATOMIC + BPF_FETCH.
-                */
-               if (BPF_CLASS(insn.code) == BPF_STX &&
-                   BPF_MODE(insn.code) == BPF_ATOMIC) {
-                       /* BPF_STX + BPF_ATOMIC insns without BPF_FETCH do not
-                        * define any registers, therefore zext_dst cannot be

kernel/bpf/verifier.c static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env, · line 11074

Quoted 10 lines
kernel/bpf/verifier.c +2 -8
-                        * set.
-                        */
-                       if (WARN_ON(!(insn.imm & BPF_FETCH)))
-                               return -EINVAL;
-                       load_reg = insn.imm == BPF_CMPXCHG ? BPF_REG_0
-                                                          : insn.src_reg;
-               } else {
-                       load_reg = insn.dst_reg;
+               if (WARN_ON_ONCE(load_reg == -1)) {
+                       verbose(env, "zext_dst is set, but no reg is defined\n");

Let's add the string "verifier bug." to the beginning of this message (this is done elsewhere too). Hopefully the only person that ever sees this message would be someone who's hacking on the verifier, but even for them it could be a significant time-saver.

Quoted 6 lines
kernel/bpf/verifier.c +1 -1
+                       return -EFAULT;
                }
 
                zext_patch[0] = insn;
--

2.29.2

Overall LGTM, thanks. It seems like without this patch, the cmpxchg test I added in [1] should fail on the s390 JIT, and this patch should fix it. Is that correct? If so could you add the test to this patch? (I guess you ought to paste in my Signed-off-by)

[1] https://lore.kernel.org/bpf/[email protected]/T/#mf6546406db03c6ca473a29cdf3bde7ddeeedf1a1

#3 lore raw
Quoted 2 lines · Brendan Jackman

On Fri, 26 Feb 2021 at 22:31, Ilya Leoshkevich <[email protected]> wrote:

[...]

Quoted 8 lines
Quoted 8 lines
kernel/bpf/verifier.c +1 -1
@@ -11006,9 +11026,10 @@ static int
 opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
         for (i = 0; i < len; i++) {
                 int adj_idx = i + delta;
                 struct bpf_insn insn;
-               u8 load_reg;
+               int load_reg;
 
Quoted 5 lines

kernel/bpf/verifier.c static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env, · line 11032

Quoted 2 lines
kernel/bpf/verifier.c +1 -0
                 insn = insns[adj_idx];
+               load_reg = insn_def_regno(&insn);

Nit: Might as well save a line by squashing this into the declaration.

Will do.

[...]

Quoted 29 lines
Quoted 29 lines
kernel/bpf/verifier.c +0 -1
@@ -11049,22 +11070,9 @@ static int
 opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
                 if (!bpf_jit_needs_zext())
                         continue;
 
-               /* zext_dst means that we want to zero-extend

whatever register
-                * the insn defines, which is dst_reg most of the time, with
-                * the notable exception of BPF_STX + BPF_ATOMIC + BPF_FETCH.
-                */
-               if (BPF_CLASS(insn.code) == BPF_STX &&
-                   BPF_MODE(insn.code) == BPF_ATOMIC) { -                       /* BPF_STX + BPF_ATOMIC insns without BPF_FETCH do not
-                        * define any registers, therefore zext_dst cannot be
-                        * set.
-                        */
-                       if (WARN_ON(!(insn.imm & BPF_FETCH))) -                               return -EINVAL;
-                       load_reg = insn.imm == BPF_CMPXCHG ? BPF_REG_0
-                                                          :
insn.src_reg;
-               } else {
-                       load_reg = insn.dst_reg;
+               if (WARN_ON_ONCE(load_reg == -1)) {

Quoted 8 lines
Quoted 2 lines

+                       verbose(env, "zext_dst is set, but no reg is defined\n");

Let's add the string "verifier bug." to the beginning of this message (this is done elsewhere too). Hopefully the only person that ever sees
this message would be someone who's hacking on the verifier, but even for them it could be a significant time-saver.

OK.

[...]

Quoted 8 lines

Overall LGTM, thanks. It seems like without this patch, the cmpxchg test I added in [1] should fail on the s390 JIT, and this patch should
fix it. Is that correct? If so could you add the test to this patch? (I guess you ought to paste in my Signed-off-by)

[1]
https://lore.kernel.org/bpf/[email protected]/T/#mf6546406db03c6ca473a29cdf3bde7ddeeedf1a1

For this to work, my implementation of atomics needs to be merged (and I haven't posted it yet). I propose to keep your tests in your patch, merge this commit first, then your zext patch with tests, then my atomics patch.