From: Alexei Starovoitov Removal of dead code. Scalars have no ids any more, so every check of a scalar id in regsafe() passes. No prog is verified differently. 4: r6 = r7 5: if r6 > 10 goto .. 6: use r7 While a jump refined all scalars with the id of the tested register, a state in which r6 and r7 have the same id was stronger than a state with the same ranges and two ids: in the first one insn 5 bounds r7. So regsafe() did not stop at the ranges. check_scalar_ids() mapped the ids of the old state to those of the current one, an id that the current state did not have got a temporary one, BPF_ADD_CONST and delta had to be equal. Now no state says that two scalars hold the same value. What insn 5 refines are its linked registers. Scalar evolution computes them before the main pass, and a link holds on every path to insn 5, whatever state gets there. The stack slot of a caller that a jump refines is found through a pointer in the state, and regsafe() compares pointers as before. For two scalars range_within() and tnum_in() are enough. Remove check_scalar_ids() and the table of cases in regsafe(). Signed-off-by: Alexei Starovoitov --- kernel/bpf/states.c | 108 ++------------------------------------------ 1 file changed, 3 insertions(+), 105 deletions(-) diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c index b60676349655..48359e789faa 100644 --- a/kernel/bpf/states.c +++ b/kernel/bpf/states.c @@ -58,7 +58,7 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) return true; /* a name of what the caller has, see BPF_INHERITED_ID */ - if (((old_id | cur_id) & ~BPF_ADD_CONST) >= BPF_INHERITED_ID) + if ((old_id | cur_id) >= BPF_INHERITED_ID) return old_id == cur_id; for (i = 0; i < idmap->cnt; i++) { @@ -85,49 +85,6 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) return false; } -/* - * Compare scalar register IDs for state equivalence. - * - * When old_id == 0, the old register is independent - not linked to any - * other register. Any linking in the current state only adds constraints, - * making it more restrictive. Since the old state didn't rely on any ID - * relationships for this register, it's always safe to accept cur regardless - * of its ID. Hence, return true immediately. - * - * When old_id != 0 but cur_id == 0, we need to ensure that different - * independent registers in cur don't incorrectly satisfy the ID matching - * requirements of linked registers in old. - * - * Example: if old has r6.id=X and r7.id=X (linked), but cur has r6.id=0 - * and r7.id=0 (both independent), without temp IDs both would map old_id=X - * to cur_id=0 and pass. With temp IDs: r6 maps X->temp1, r7 tries to map - * X->temp2, but X is already mapped to temp1, so the check fails correctly. - * - * When old_id has BPF_ADD_CONST set, the compound id (base | flag) and the - * base id (flag stripped) must both map consistently. Example: old has - * r2.id=A, r3.id=A|flag (r3 = r2 + delta), cur has r2.id=B, r3.id=C|flag - * (r3 derived from unrelated r4). Without the base check, idmap gets two - * independent entries A->B and A|flag->C|flag, missing that A->C conflicts - * with A->B. The base ID cross-check catches this. - */ -static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) -{ - if (!old_id) - return true; - - cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen; - - if (!check_ids(old_id, cur_id, idmap)) - return false; - if (old_id & BPF_ADD_CONST) { - old_id &= ~BPF_ADD_CONST; - cur_id &= ~BPF_ADD_CONST; - if (!check_ids(old_id, cur_id, idmap)) - return false; - } - return true; -} - static void __clean_func_state(struct bpf_verifier_env *env, struct bpf_func_state *st, u16 live_regs, int frame) @@ -272,65 +229,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, /* explore_alu_limits disables tnum_in() and range_within() * logic and requires everything to be strict */ - return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 && - check_scalar_ids(rold->id, rcur->id, idmap); + return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0; } - /* - * Linked register tracking uses rold->id to detect relationships. - * When rold->id == 0, the register is independent and any linking - * in rcur only adds constraints. When rold->id != 0, we must verify - * id mapping and (for BPF_ADD_CONST) offset consistency. - * - * +------------------+-----------+------------------+---------------+ - * | | rold->id | rold + ADD_CONST | rold->id == 0 | - * |------------------+-----------+------------------+---------------| - * | rcur->id | range,ids | false | range | - * | rcur + ADD_CONST | false | range,ids,off | range | - * | rcur->id == 0 | range,ids | false | range | - * +------------------+-----------+------------------+---------------+ - * - * Why check_ids() for scalar registers? - * - * Consider the following BPF code: - * 1: r6 = ... unbound scalar, ID=a ... - * 2: r7 = ... unbound scalar, ID=b ... - * 3: if (r6 > r7) goto +1 - * 4: r6 = r7 - * 5: if (r6 > X) goto ... - * 6: ... memory operation using r7 ... - * - * First verification path is [1-6]: - * - at (4) same bpf_reg_state::id (b) would be assigned to r6 and r7; - * - at (5) r6 would be marked <= X, sync_linked_regs() would also mark - * r7 <= X, because r6 and r7 share same id. - * Next verification path is [1-4, 6]. - * - * Instruction (6) would be reached in two states: - * I. r6{.id=b}, r7{.id=b} via path 1-6; - * II. r6{.id=a}, r7{.id=b} via path 1-4, 6. - * - * Use check_ids() to distinguish these states. - * --- - * Also verify that new value satisfies old value range knowledge. - */ - - /* - * ADD_CONST flags must match exactly: BPF_ADD_CONST32 and - * BPF_ADD_CONST64 have different linking semantics in - * sync_linked_regs() (alu32 zero-extends, alu64 does not), - * so one doesn't stand for the other. - */ - if (rold->id && - (rold->id & BPF_ADD_CONST) != (rcur->id & BPF_ADD_CONST)) - return false; - - /* Both have offset linkage: offsets must match */ - if ((rold->id & BPF_ADD_CONST) && rold->delta != rcur->delta) - return false; - - if (!check_scalar_ids(rold->id, rcur->id, idmap)) - return false; - return range_within(rold, rcur) && tnum_in(rold->var_off, rcur->var_off); case PTR_TO_MAP_KEY: case PTR_TO_MAP_VALUE: @@ -468,8 +368,7 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old, /* * 64 and 32-bit scalar spills vs MISC/INVALID slots and vice versa. * Load from MISC/INVALID slots produces unbound scalar. - * Construct a fake register for such stack and call - * regsafe() to ensure scalar ids are compared. + * Construct a fake register for such stack and call regsafe(). */ if (im == 0 || im == 4) { old_reg = scalar_reg_for_stack(env, old_slot, im); @@ -736,7 +635,6 @@ static void reset_idmap_scratch(struct bpf_verifier_env *env) { struct bpf_idmap *idmap = &env->idmap_scratch; - idmap->tmp_id_gen = env->id_gen; idmap->cnt = 0; } -- 2.55.0