• Yonghong Song's avatar
    bpf/verifier: improve register value range tracking with ARSH · 9cbe1f5a
    Yonghong Song authored
    When helpers like bpf_get_stack returns an int value
    and later on used for arithmetic computation, the LSH and ARSH
    operations are often required to get proper sign extension into
    64-bit. For example, without this patch:
        54: R0=inv(id=0,umax_value=800)
        54: (bf) r8 = r0
        55: R0=inv(id=0,umax_value=800) R8_w=inv(id=0,umax_value=800)
        55: (67) r8 <<= 32
        56: R8_w=inv(id=0,umax_value=3435973836800,var_off=(0x0; 0x3ff00000000))
        56: (c7) r8 s>>= 32
        57: R8=inv(id=0)
    With this patch:
        54: R0=inv(id=0,umax_value=800)
        54: (bf) r8 = r0
        55: R0=inv(id=0,umax_value=800) R8_w=inv(id=0,umax_value=800)
        55: (67) r8 <<= 32
        56: R8_w=inv(id=0,umax_value=3435973836800,var_off=(0x0; 0x3ff00000000))
        56: (c7) r8 s>>= 32
        57: R8=inv(id=0, umax_value=800,var_off=(0x0; 0x3ff))
    With better range of "R8", later on when "R8" is added to other register,
    e.g., a map pointer or scalar-value register, the better register
    range can be derived and verifier failure may be avoided.
    
    In our later example,
        ......
        usize = bpf_get_stack(ctx, raw_data, max_len, BPF_F_USER_STACK);
        if (usize < 0)
            return 0;
        ksize = bpf_get_stack(ctx, raw_data + usize, max_len - usize, 0);
        ......
    Without improving ARSH value range tracking, the register representing
    "max_len - usize" will have smin_value equal to S64_MIN and will be
    rejected by verifier.
    Acked-by: default avatarAlexei Starovoitov <ast@kernel.org>
    Signed-off-by: default avatarYonghong Song <yhs@fb.com>
    Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
    9cbe1f5a
verifier.c 169 KB