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:   Wed, 24 Apr 2019 21:33:49 -0700
From:   Alexei Starovoitov <alexei.starovoitov@...il.com>
To:     Jiong Wang <jiong.wang@...ronome.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 Thu, Apr 25, 2019 at 12:07:06AM +0100, Jiong Wang wrote:
> 
> Alexei Starovoitov writes:
> 
> > Add two tests to check that sequence of 1024 jumps is verifiable.
> >
> > Signed-off-by: Alexei Starovoitov <ast@...nel.org>
> > ---
> >  tools/testing/selftests/bpf/test_verifier.c  | 70 ++++++++++++++++++++
> >  tools/testing/selftests/bpf/verifier/scale.c | 18 +++++
> 
> I am rebasing 32-bit opt pass on top of latest bpf-next and found these new
> tests take more than 20 minutes to run and had not finished after that.
> 
> The reason the following insn filling insde bpf_fill_scale1 is generating
> nearly 1M insn whose results are recognized as safe to be poisoned.
> 
>   bpf_fill_scale1:
>     while (i < MAX_TEST_INSNS - 1025)
>       insn[i++] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 42);
> 
> For each hi32 poisoning, there will be one call to "bpf_patch_insn_data"
> which actually is not cheap (adjust jump insns, insn aux info etc). Now,
> 1M call to it has exhausted server resources as described, 20minutes running
> still not finished.
> 
> For real world applications, we don't do hi32 poisoning, and there isn't much
> lo32 zext. Benchmarking those bpf programs inside Cilium shows the final
> zext pass adds about 8% ~ 15% verification time.
> 
> The zext pass based on top of "bpf_patch_insn_data" looks more and more is
> not the best approach to utilize the read32 analysis results.
> 
> Previously, in v1 cover letter, I listed some of my other thoughts on how to
> utilize the liveness analysis results:
> 
>    1 Minor change on back-end JIT hook, also pass aux_insn information to
>      back-ends so they could have per insn information and they could do
>      zero extension for the marked insn themselves using the most
>      efficient native insn.
> 
>    2 Introduce zero extension insn for eBPF. Then verifier could insert
>      the new zext insn instead of lshift + rshift. zext could be JITed
>      more efficiently.
> 
>    3 Otherwise JIT back-ends need to do peephole to catch lshift + rshift
>      and turn them into native zext.

all options sounds like hacks to workaround inefficient bpf_patch_insn_data().
Especially option 2 will work only because single insn is replaced
with another insn ?
Let's fix the algo of bpf_patch_insn_data() instead, so that 1 insn -> 2+ insn
is also fast.
The main point of bumping the internal limits to 1M and these tests
was to expose such algorithmic inefficiencies.