[DTrace-devel] stressing the BPF verifier

[Eugene Loh]

On 12/01/2020 07:55 PM, Kris Van Hees wrote:

> 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?

Ha, yeah, sorry.  Program runs fine with 14 aggregations, but then I add 
a 15th and the BPF verifier spits out over 100k lines of output... 
walking all sorts of combinations of branches (I guess, I haven't really 
looked too closely, but I think that's what it's doing) and then in the 
"middle" of the walk it stops reporting, saying
dtrace: could not enable tracing: BPF program load for 'dtrace:::BEGIN' 
failed: No space left on device

So, in dt_bpf_prog_load(), I doubled the size of the BPF log passed to 
bpf_load_program_xattr(), and I could go from 14 aggregations to 28.  
So, I guess I have a workaround.  Still, the BPF verifier seems rather 
heavyweight.

>> 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.)