Add support for bpf2bpf function calls

[dthaler]

Implemented approach discussed in meeting between Dave, Elazar, Arie, and others. Each function is treated as a "macro" and CFG nodes are created as if the compiler had inlined the functions. The new nodes use variables prefixed with the conceptual call stack, so that nesting and multiple calls to the same function are both supported. E.g., "1/5/r6.svalue=0" means the svalue property of r6 in a macro called from label 5 which was in turn called from label 1.

As tested by the bpf_conformance suite, it turns out that an Exit instruction is responsible for restoring registers R6-R9 (as opposed to being restored by other instructions generated by the compiler). Hence the CallLocal instruction makes copies of R6-R9 state, and the Exit instruction restores R6-R9 from the copies, and cleans up the copied state.

This PR also:

• fixes a use-after-free bug in wto.cpp where args2 state was being read after a pop() that could free that memory.
• adds a "simplify" option for YAML tests that want to test behavior without no_simplify. Previously all YAML tests used no_simplify, but we needed to test CallLocal both with and without the simplify step in order to fully test the CFG changes.
• updates the template matching code in test_marshal.cpp to correctly deal with fields with wildcards, to resolve an issue hit when testing this PR.

Fixes #451

[coveralls]

coverage: 90.417% (-0.01%) from 90.431% when pulling e2cf59a76d8c66cd2ff6cf3ed11a8d78cff46765 on dthaler:bpf2bpf into cd399bb487e8cdbd718a0acc9409953b1fec1711 on vbpf:main.

[elazarg]

I don't think handling function calls as macros at the CFG level is the right approach, and I do not believe Arie and @caballa supported this approach. Inlining (as opposed to computing a summary) can be implemented by letting the abstract interpreter treat the code in same way a concrete interpreter would: jump to the start of the function with a copy of the abstract state, execute normally, then jump back with the resulting state.

In order to have the same behavior as in the macro approach you'd need to index the tracked states (instead of the instructions) with the same conceptual call stack, but I think this approach is more flexible in case we'd want to implement alternative approaches to inlining. For example, we can join on entry from all caller sites and thus converge faster, probably with a simpler debug output (also maybe slightly more useful proof-carrying-code in the future).

[dthaler]

I don't think handling function calls as macros at the CFG level is the right approach, and I do not believe Arie and @caballa supported this approach.

This is the approach I understood on the call. Would like Arie and @caballa to weigh in.

Inlining (as opposed to computing a summary) can be implemented by letting the abstract interpreter treat the code in same way a concrete interpreter would: jump to the start of the function with a copy of the abstract state, execute normally, then jump back with the resulting state.

I don't follow what that means. What I do know is that this PR does work. Do we need to have another Zoom call?

In order to have the same behavior as in the macro approach you'd need to index the tracked states (instead of the instructions) with the same conceptual call stack, but I think this approach is more flexible in case we'd want to implement alternative approaches to inlining. For example, we can join on entry from all caller sites and thus converge faster, probably with a simpler debug output (also maybe slightly more useful proof-carrying-code in the future).

[caballa]

I read the slides given by @dthaler and asked Arie about the meeting you had and what I understand @dthaler has implemented is consistent with what I remember.

@elazarg suggests a "dynamic" inlining approach. By "dynamic", I mean that the abstract interpreter actually does the inlining as it goes. There are several advantages of doing that. Elazar mentioned some. Another important advantage is that a function call wouldn't be inlined if it's unreachable.

What @dthaler has implemented is more like a "static" inlining approach by doing some program transformation (I haven't looked at the PR but this is my guess).

Both approaches are compatible. We can start with Dave's approach since it's already implemented and tested and we can always implement what Elazar suggests if needed.

[dthaler]

Code coverage failure seems to be a transient failure due to coveralls backend, not specific to this PR.

[shankarseal]

@dthaler @elazarg the eBPF for Windows project would like to onboard bpf2bpf function call support to investigate if this can replace tail calls (among others) to improve performance of bpf programs in network datapath. Can you please continue this PR (which seems stalled) and resolve the remaining issues?

[elazarg]

@shankarseal done.