kleendr12
Re:eBPF Summit Day 1 Recap
on Friday October 30, 2020 @05:03AM (#24940413)
I'm not quite sure I follow your comment. If the program never terminates then it will loop forever and potentially freeze the machine depending from where it is invoked in the kernel. Example of loops that can be detected to terminate:
int nested_loops(volatile struct pt_regs* ctx)
{
int i, j, sum = 0, m;
for (j = 0; j < 300; j++)
for (i = 0; i < j; i++) {
if (j & 1)
m = ctx->rax;
else
m = j;
sum += i * m;
}
return sum;
}
Or for example another one that is also part of selftests with induction variable i: int while_true(volatile struct pt_regs* ctx)
{
int i = 0;
while (true) {
if (ctx->rax & 1)
i += 3;
else
i += 7;
if (i > 40)
break;
}
return i;
}
Overall this is very useful to avoid unrolling loops & keeping the code dense and icache friendly, and to parse (e.g.) IPv6 extension headers and such.
Re:eBPF Summit Day 1 Recap
on Friday October 30, 2020 @04:34AM (#24940273)
When there's no loop bound it cannot prove termination, see halting problem. Goal is to avoid getting an infinite loop and then freezing the kernel of course.
Re:eBPF Summit Day 1 Recap
on Friday October 30, 2020 @04:13AM (#24940163)
Loops must be bounded, that means, the verifier must be able to see that the loop will eventually terminate based on the condition. The verifier will simulate all iterations of the loop and as such it is limited by the verifier complexity, that is, it'll do analysis of up to 1 million walked insns for the entire program until the verifier rejects it.