This patch addresses the verifier deficiency where it would throw away a good range whenever that range crossed zero. | 1: (54) w0 &= 63 ; R0=scalar(smin32=0,smax32=63,...) | 2: (14) w0 -= 63 ; R0=scalar(smin32=-63,smax32=0,...) | 3: (bc) w0 = (s8)w0 ; R0=scalar(smin32=-128,smax32=127,...) | 4: (c6) if w0 s< 0xffffffc1 goto pc+2 | ... | 7: (34) w0 /= 0 | div by zero [-63, 0] already fits an s8, so insn 3 cannot change any value in it, yet the range comes out widened to [-128, 127]. The guard at insn 4 then cannot be resolved and the div becomes reachable. The issue is the following check in coerce_subreg_to_size_sx() top_smax_value = ((u32)reg_s32_max(reg) >> num_bits) << num_bits; top_smin_value = ((u32)reg_s32_min(reg) >> num_bits) << num_bits; if (top_smax_value != top_smin_value) goto out; which doesn't fire when the range includes zero, since the top bits differ. e.g. for [-63, 0]: smin32 = -63: high bits all ones smax32 = 0: high bits all zero The cheap noop test above it does not catch this either -- it only looks at reg_umax(), which a negative smin makes huge. The 64-bit twin, coerce_reg_to_size_sx(), had the same gap and was given an equivalent early return by commit 0892ef2a7ef3 ("bpf: Representation for intervals with steps"). This patch does the same for the 32-bit path, for the s8 and s16 widths it handles. It doesn't improve anything in selftests or corpora of external objects -- the shape above only shows up in the test the next patch adds -- but seems like the right thing to do anyways. Fixes: 8100928c8814 ("bpf: Support new sign-extension mov insns") Signed-off-by: Vineet Gupta --- v3: was v2 5/13. - moved to the front: it is unrelated to the low-32 tracking (Alexei) - narrowed to the 32-bit path. Commit 0892ef2a7ef3 ("bpf: Representation for intervals with steps") has since given coerce_reg_to_size_sx() an equivalent early return, so Fixes: 1f9a1ea821ff goes with that half. - measured inert: 0 instruction and 0 state changes on both selftest corpora and on 441 external objects. kernel/bpf/verifier.c | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 62f8951126ba..e1b41975a442 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -6182,6 +6182,7 @@ static void set_sext32_default_val(struct bpf_reg_state *reg, int size) static void coerce_subreg_to_size_sx(struct bpf_reg_state *reg, int size) { s32 init_s32_max, init_s32_min, s32_max, s32_min, u32_val; + s32 field_smin, field_smax; u32 top_smax_value, top_smin_value; u32 num_bits = size * 8; @@ -6192,6 +6193,27 @@ static void coerce_subreg_to_size_sx(struct bpf_reg_state *reg, int size) if (reg_umax(reg) < (1ULL << (num_bits - 1))) return; + if (size == 1) { + field_smin = S8_MIN; + field_smax = S8_MAX; + } else { + /* size == 2 */ + field_smin = S16_MIN; + field_smax = S16_MAX; + } + + /* + * The range already fits the field, so (sN)v == v for every value the + * register can hold and the sign extension changes nothing. The test + * above misses this once the range straddles zero: it only looks at + * reg_umax(), which a negative smin makes huge. + * + * This has to precede reg_step_reset() below: the extension is a noop, + * so the base/step line still holds and there is nothing to discard. + */ + if (reg_s32_min(reg) >= field_smin && reg_s32_max(reg) <= field_smax) + return; + /* See comment at reg_step_check_unsigned(). */ reg_step_reset(reg); -- 2.53.0-Meta