• Eduard Zingerman's avatar
    bpf: keep track of max number of bpf_loop callback iterations · bb124da6
    Eduard Zingerman authored
    In some cases verifier can't infer convergence of the bpf_loop()
    iteration. E.g. for the following program:
    
        static int cb(__u32 idx, struct num_context* ctx)
        {
            ctx->i++;
            return 0;
        }
    
        SEC("?raw_tp")
        int prog(void *_)
        {
            struct num_context ctx = { .i = 0 };
            __u8 choice_arr[2] = { 0, 1 };
    
            bpf_loop(2, cb, &ctx, 0);
            return choice_arr[ctx.i];
        }
    
    Each 'cb' simulation would eventually return to 'prog' and reach
    'return choice_arr[ctx.i]' statement. At which point ctx.i would be
    marked precise, thus forcing verifier to track multitude of separate
    states with {.i=0}, {.i=1}, ... at bpf_loop() callback entry.
    
    This commit allows "brute force" handling for such cases by limiting
    number of callback body simulations using 'umax' value of the first
    bpf_loop() parameter.
    
    For this, extend bpf_func_state with 'callback_depth' field.
    Increment this field when callback visiting state is pushed to states
    traversal stack. For frame #N it's 'callback_depth' field counts how
    many times callback with frame depth N+1 had been executed.
    Use bpf_func_state specifically to allow independent tracking of
    callback depths when multiple nested bpf_loop() calls are present.
    Signed-off-by: default avatarEduard Zingerman <eddyz87@gmail.com>
    Link: https://lore.kernel.org/r/20231121020701.26440-11-eddyz87@gmail.comSigned-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
    bb124da6
verifier_subprog_precision.c 18.3 KB