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]

Date:   Fri, 26 Apr 2019 15:50:33 +0100
From:   Edward Cree <ecree@...arflare.com>
To:     Jiong Wang <jiong.wang@...ronome.com>,
        Alexei Starovoitov <alexei.starovoitov@...il.com>
CC:     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 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.

Just a thought,
-Ed