On Fri, Dec 02, 2016 at 11:42:15AM -0800, John Fastabend wrote: > >> As far as pattern search for DNS packets... > >> it was requested by Cloudflare guys back in March: > >> https://github.com/iovisor/bcc/issues/471 > >> and it is useful for several tracing use cases as well. > >> Unfortunately no one had time to implement it yet. > > > > The string operations you proposed on the other hand, which would count > > as one eBPF instructions, would give a lot more flexibility and allow > > more cycles to burn, but don't help parsing binary protocols like IPv6 > > extension headers.
these are two separate things. we need pattern search regardless of bounded loops. bpf program shouldn't be doing any complicated algorithms. The main reasons to have loops are: - speed up execution (smaller I-cache footprint) - avoid forcing compiler to unroll loops (easier for users) - support loops where unroll is not possible (like example below) > My rough thinking on this was the verifier had to start looking for loop > invariants and to guarantee termination. Sounds scary in general but > LLVM could put these in some normal form for us and the verifier could > only accept decreasing loops, the invariants could be required to be > integers, etc. By simplifying the loop enough the problem becomes > tractable. yep. I think what Hannes was proposing earlier is straighforward to implement for a compiler guy. The following: for (int i = 0; i < (var & 0xff); i++) sum += map->value[i]; /* map value_size >= 0xff */ is obviously bounded and dataflow analysis can easily prove that all memory operations are valid. Static analysis tools do way way more than this. > I think this would be better than new instructions and/or multiple > verifiers. agree that it's better than new instructions that would have required JIT changes. Though there are pros to new insns too :)
