Re: [RFC PATCH bpf-next 10/11] bpf: Introduce PTR_ITER and PTR_ITER_END type flags

[Alexei Starovoitov <ast@fb.com>]

On 8/2/22 6:05 AM, Kumar Kartikeya Dwivedi wrote:
> On Tue, 2 Aug 2022 at 00:46, Alexei Starovoitov <ast@fb.com> wrote:
>>
>> On 7/22/22 11:34 AM, Dave Marchevsky wrote:
>>>        if (__is_pointer_value(false, reg)) {
>>> +             if (__is_iter_end(reg) && val == 0) {
>>> +                     __mark_reg_const_zero(reg);
>>> +                     switch (opcode) {
>>> +                     case BPF_JEQ:
>>> +                             return 1;
>>> +                     case BPF_JNE:
>>> +                             return 0;
>>> +                     default:
>>> +                             return -1;
>>> +                     }
>>> +             }
>>
>> as discussed the verifying the loop twice is not safe.
>> This needs more advanced verifier hacking.
>> Maybe let's postpone rbtree iters for now and resolve all the rest?
>> Or do iters with a callback, since that's more or less a clear path fwd?
>>
> 
> Can you elaborate a bit on what you think the challenges/concerns are
> (even just for educational purposes)? I am exploring a similar
> approach for one of my use cases.

struct node *elem = data_structure_iter_first(&some_map);
int i = 0;

while (elem) {
     array[i++] = 0;
     elem = data_structure_iter_next(&some_map, elem);
}

If the verifier checks the loop body only twice the array[] access
will go out of bounds.
We discussed downgrading all scalars to be not-precise (in the verifier 
terms) while verifying the body. Then we can catch such cases.
In other words the verifier need to look at any induction variable
as being unbounded, since the loop count is non deterministic.