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 <>
To:     Jiong Wang <>,
        Alexei Starovoitov <>
CC:     Alexei Starovoitov <>, <>,
        <>, <>,
        Jakub Kicinski <>,
        "" <>
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,

Powered by blists - more mailing lists