Yonghong Song writes:
> On 4/19/24 2:47 AM, Cupertino Miranda wrote:
>> Eduard Zingerman writes:
>>
>>> On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
>>>
>>> [...]
>>>
>>>> static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>>>> + struct bpf_reg_state dst_reg,
>>>> struct bpf_reg_state src_reg)
>>> Nit: there is no need to pass {dst,src}_reg by value,
>>> struct bpf_reg_state is 120 bytes in size
>>> (but maybe compiler handles this).
>>>
>>>> {
>>>> - bool src_known;
>>>> + bool src_known, dst_known;
>>>> u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
>>>> bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
>>>> u8 opcode = BPF_OP(insn->code);
>>>>
>>>> - bool valid_known = true;
>>>> - src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known);
>>>> + bool valid_known_src = true;
>>>> + bool valid_known_dst = true;
>>>> + src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known_src);
>>>> + dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known_dst);
>>>>
>>>> /* Taint dst register if offset had invalid bounds
>>>> * derived from e.g. dead branches.
>>>> */
>>>> - if (valid_known == false)
>>>> + if (valid_known_src == false)
>>>> return UNCOMPUTABLE_RANGE;
>>>>
>>>> switch (opcode) {
>>>> @@ -13457,10 +13460,12 @@ static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>>>> case BPF_OR:
>>>> return COMPUTABLE_RANGE;
>>>>
>>>> - /* Compute range for the following only if the src_reg is known.
>>>> + /* Compute range for MUL if at least one of its registers is known.
>>>> */
>>>> case BPF_MUL:
>>>> - return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
>>>> + if (src_known || (dst_known && valid_known_dst))
>>>> + return COMPUTABLE_RANGE;
>>>> + break;
>>> Is it even necessary to restrict src or dst to be known?
>>> adjust_scalar_min_max_vals() logic for multiplication looks as follows:
>>>
>>> case BPF_MUL:
>>> dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off);
>>> scalar32_min_max_mul(dst_reg, &src_reg);
>>> scalar_min_max_mul(dst_reg, &src_reg);
>>> break;
>>>
>>> Where tnum_mul() refers to a paper, and that paper does not restrict
>>> abstract multiplication algorithm to constant values on either side.
>>> The scalar_min_max_mul() and scalar32_min_max_mul() are similar:
>>> - if both src and dst are positive
>>> - if overflow is not possible
>>> - adjust dst->min *= src->min
>>> - adjust dst->max *= src->max
>>>
>>> I think this should work just fine if neither of src or dst is a known constant.
>>> What do you think?
>>>
>> With the refactor this looked like an armless change. Indeed if we agree
>> that the algorithm covers all scenarios, then why not.
>> I did not study the paper or the scalar_min_max_mul function nearly
>> enough to know for sure.
>
> I double checked and I think Eduard is correct. src_known checking
> is not necessary for multiplication. It would be great if you can
> add this change as well in the patch set.
Sure! Thanks for confirming this.
>
>>> [...]
