On Fri, Apr 26, 2019 at 03:50:33PM +0100, Edward Cree wrote: > On 26/04/2019 14:06, Jiong Wang wrote: > > Alexei Starovoitov writes: > >> Note that bpf_patch_insn_single() is calling bpf_adj_branches() twice too. > >> And dead_code + convert_ctx + fixup_bpf_calls are calling > >> bpf_patch_insn_single() a lot. > >> How about before dead_code pass we convert the program into basic-block > >> format, patch it all, and then convert from bb back to offsets. > >> Patching will become very cheap, since no loop over program will be > >> necessary. A jump from bb-N to bb-M will stay as-is regardless > >> of amount of patching was done inside each bb. > >> The loops inside these patching passes will be converted from: > >> for (i = 0; i < insn_cnt; i++, insn++) > >> into: > >> for each bb > >> for each insn in bb > > Interesting. If I am understanding correctly, BB then needs to support > > dynamic insn buffer resize. And after all insn patching finished, all BBs > > are finalized, we then linearized BBs (in a best order) to generate the > > final bpf image. > Does any verifier metadata ever take the index of an insn that was added by > patching? If not, then we could have, instead of an array of insns, an > array of list_heads, each of which is a list of insns (plus aux data etc.). > At entry the original program is converted into an array of 1-element lists. > On patching we edit the list, which doesn't change the index of any insn. > Then after all insn patching finishes, we linearise as above. Interesting idea. It can be optimized further: instead of converting all insns into lists of 1 before all patching it can be done on demand: convert from insn to list only when patching is needed. Patched insn becomes a pointer to a block of new insns. We have reserved opcodes to recognize such situation. The question is how to linearise it once at the end?
