netdev - Re: 32-bit zext time complexity (Was Re: [PATCH bpf-next] selftests/bpf: two scale tests)

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20190427031122.dgnt4y4v6rnbawq2@ast-mbp>
Date:   Fri, 26 Apr 2019 20:11:23 -0700
From:   Alexei Starovoitov <alexei.starovoitov@...il.com>
To:     Edward Cree <ecree@...arflare.com>
Cc:     Jiong Wang <jiong.wang@...ronome.com>,
        Alexei Starovoitov <ast@...nel.org>, daniel@...earbox.net,
        netdev@...r.kernel.org, bpf@...r.kernel.org,
        Jakub Kicinski <jakub.kicinski@...ronome.com>,
        "oss-drivers@...ronome.com" <oss-drivers@...ronome.com>
Subject: Re: 32-bit zext time complexity (Was Re: [PATCH bpf-next]
 selftests/bpf: two scale tests)

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?