netdev - Re: bpf bounded loops. Was: [flamebait] xdp

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: <b7c99fea-dfaa-a7a0-0694-d6abe649708e@stressinduktion.org>
Date:   Mon, 5 Dec 2016 17:50:26 +0100
From:   Hannes Frederic Sowa <hannes@...essinduktion.org>
To:     Edward Cree <ecree@...arflare.com>,
        Alexei Starovoitov <alexei.starovoitov@...il.com>
Cc:     Tom Herbert <tom@...bertland.com>, Thomas Graf <tgraf@...g.ch>,
        Linux Kernel Network Developers <netdev@...r.kernel.org>,
        Daniel Borkmann <daniel@...earbox.net>,
        "David S. Miller" <davem@...emloft.net>
Subject: Re: bpf bounded loops. Was: [flamebait] xdp

On 05.12.2016 17:40, Edward Cree wrote:
> On 02/12/16 19:25, Hannes Frederic Sowa wrote:
>> On 02.12.2016 19:39, Alexei Starovoitov wrote:
>>> Hannes,
>>> Not too long ago you proposed a very interesting idea to add
>>> support for bounded loops without adding any new bpf instructions and
>>> changing llvm (which was way better than my 'rep' like instructions
>>> I was experimenting with). I thought systemtap guys also wanted bounded
>>> loops and you were cooperating on the design, so I gave up on my work and
>>> was expecting an imminent patch from you. I guess it sounds like you know
>>> believe that bounded loops are impossible or I misunderstand your statement ?
>> Your argument was that it would need a new verifier as the current first
>> pass checks that we indeed can lay out the basic blocks as a DAG which
>> the second pass depends on. This would be violated.
> I may be completely mistaken here, but can't the verifier unroll the loop 'for
> verification' without it actually being unrolled in the program?
> I.e., any "proof that the loop terminates" should translate into "rewrite of
> the directed graph to make it a DAG, possibly duplicating a lot of insns", and
> you feed the rewritten graph to the verifier, while using the original loopy
> version as the actual program to store and later execute.
> Then the verifier happily checks things like array indices being valid, without
> having to know about the bounded loops.

That is what is already happening. E.g. __builtin_memset is expanded up
to 128 rounds (which is a lot) but at some point llvm doesn't do enoug
unrolling of that.

The BPF target configures that in
http://llvm.org/docs/doxygen/html/BPFISelLowering_8cpp_source.html on
line 166-169.

Bye,
Hannes