On Tue, Apr 25, 2023 at 04:49:09PM -0700, Andrii Nakryiko wrote: > Add support precision backtracking in the presence of subprogram frames in > jump history. > > This means supporting a few different kinds of subprogram invocation > situations, all requiring a slightly different handling in precision > backtracking handling logic: > - static subprogram calls; > - global subprogram calls; > - callback-calling helpers/kfuncs. > > For each of those we need to handle a few precision propagation cases: > - what to do with precision of subprog returns (r0); > - what to do with precision of input arguments; > - for all of them callee-saved registers in caller function should be > propagated ignoring subprog/callback part of jump history. > > N.B. Async callback-calling helpers (currently only > bpf_timer_set_callback()) are transparent to all this because they set > a separate async callback environment and thus callback's history is not > shared with main program's history. So as far as all the changes in this > commit goes, such helper is just a regular helper. > > Let's look at all these situation in more details. Let's start with > static subprogram being called, using an exxerpt of a simple main > program and its static subprog, indenting subprog's frame slightly to > make everything clear. > > frame 0 frame 1 precision set > ======= ======= ============= > > 9: r6 = 456; > 10: r1 = 123; r6 > 11: call pc+10; r1, r6 > 22: r0 = r1; r1 > 23: exit r0 > 12: r1 = <map_pointer> r0, r6 > 13: r1 += r0; r0, r6 > 14: r1 += r6; r6; > 15: exit > > As can be seen above main function is passing 123 as single argument to > an identity (`return x;`) subprog. Returned value is used to adjust map > pointer offset, which forces r0 to be marked as precise. Then > instruction #14 does the same for callee-saved r6, which will have to be > backtracked all the way to instruction #9. For brevity, precision sets > for instruction #13 and #14 are combined in the diagram above. > > First, for subprog calls, r0 returned from subprog (in frame 0) has to > go into subprog's frame 1, and should be cleared from frame 0. So we go > back into subprog's frame knowing we need to mark r0 precise. We then > see that insn #22 sets r0 from r1, so now we care about marking r1 > precise. When we pop up from subprog's frame back into caller at > insn #11 we keep r1, as it's an argument-passing register, so we eventually > find `10: r1 = 123;` and satify precision propagation chain for insn #13. > > This example demonstrates two sets of rules: > - r0 returned after subprog call has to be moved into subprog's r0 set; > - *static* subprog arguments (r1-r5) are moved back to caller precision set. Haven't read the rest. Only commenting on the above... The description of "precision set" combines multiple frames and skips the lower which makes it hard to reason. I think it should be: 10: r1 = 123; fr0: r6 11: call pc+10; fr0: r1, r6 22: r0 = r1; fr0: r6; fr1: r1 23: exit fr0: r6; fr1: r0 12: r1 = <map_pointer> fr0: r0, r6 13: r1 += r0; fr0: r0, r6 14: r1 += r6; fr0: r6 Right?
