netdev - Re: [RFC PATCH v3 bpf-next 0/5] bpf/verifier: subprog/func

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: <d1918863-4312-d40d-c22b-d8ce05f65df8@netronome.com>
Date:   Tue, 10 Apr 2018 13:54:18 +0100
From:   Jiong Wang <jiong.wang@...ronome.com>
To:     Edward Cree <ecree@...arflare.com>,
        Alexei Starovoitov <alexei.starovoitov@...il.com>,
        Daniel Borkmann <daniel@...earbox.net>
Cc:     netdev@...r.kernel.org
Subject: Re: [RFC PATCH v3 bpf-next 0/5] bpf/verifier: subprog/func_call
 simplifications

On 06/04/2018 18:11, Edward Cree wrote:
> By storing subprog boundaries as a subprogno mark on each insn, rather than
>  a start (and implicit end) for each subprog, the code handling subprogs can
>  in various places be made simpler, more explicit, and more efficient (i.e.
>  better asymptotic complexity).

IMHO, the subprog number might be much smaller than insn number, so just
keeping sorted subprog information in env->subprog_info and do bsearch
looks reasonable to me.

While the new added "subprogno" field is only used round find_subprog, so
I feel it is a little bit heavy to allocate a delicated field that wouldn't
be used broadly for each instruction.

> This also lays the ground for possible
>  future work in which an extension of the check_subprogs() code to cover
>  basic blocks could replace check_cfg(), which currently largely duplicates
>  the insn-walking part.

I was thinking to remove the insn-walk duplication in the other way by
center them in the DFS insn-walk in check_cfg, as we can't remove that one
before we migrate to other loop detection method. This approach is
questionable though.

> Some other changes were also included to support this:
> * Per-subprog info is stored in env->subprog_info, an array of structs,
>   rather than several arrays with a common index.
> * Subprog numbers and corresponding subprog_info index are now 0-based;
>   subprog 0 is the main()-function of the program, starting at insn 0.
> * Call graph is now stored in the new bpf_subprog_info struct; used here
>   for check_max_stack_depth() but may have other uses too.

Ack above changes which center all subprog related info into
env->subprog_info and the new addition of callee field.