[DTrace-devel] stressing the BPF verifier

[Kris Van Hees]

On Tue, Dec 01, 2020 at 07:42:12PM -0800, Eugene Loh wrote:
> I'm looking at the quantize() aggregation function, which takes any 
> 64-bit value and assigns it to one of 127 different bins.  The rule is 
> something like 1<<1 gets assigned to some bin, 1<<2 to the next, 1<<3 to 
> the next, and so on.  So that explains 63 of the bins.  If the value is 
> negative, you get another 63 bins.  And if the value is 0, there's a 
> special bin.
> 
> The code to reduce the value to a bin index basically searches for a 
> leftmost bit (modulo that "value is negative" wrinkle).  The algorithm 
> is something like
> 
> - offset = 0
> - if the leftmost 32 bits are nonzero, offset+=32, value>>=32
> - now, the leftmost 32 bits are zero
> - if the next 16 bits are nonzero, offset+=16, value>>16
> - now, the leftmost 48 bits are zero
> - if the next 8 bits are nonzero, offset+=8, value>>8
> - etc.
> 
> The thing is there are these conditionals, and so the BPF verifier walks 
> all those different branches... on order of 127 different paths.
> 
> If I run a D script like:
> 
>      x = 0;
>      @ = quantize(x);
>      @ = quantize(x);
>      @ = quantize(x);
>      ... repeat ...
> 
> I can only have about 14 aggregations before the BPF verifier has a 
> mental breakdown.

Can you elaborate a bit on the 'mental breakdown'?  What are the symptoms?
Is there an error report, error code, anything?

> Comments?  Tough luck?  That's a limitation?  Need to solve this?
> 
> (I thought I used to be able to go to more aggregations before hitting 
> this limit, but maybe I'm remembering incorrectly. Anyhow, the problem 
> is there, even if it isn't always exactly at 14 aggregations.)