From: "Björn Töpel" <bjorn.topel@gmail.com>
To: Palmer Dabbelt <palmerdabbelt@google.com>
Cc: Daniel Borkmann <daniel@iogearbox.net>,
Netdev <netdev@vger.kernel.org>,
Alexei Starovoitov <ast@kernel.org>,
Luke Nelson <lukenels@cs.washington.edu>,
linux-riscv@lists.infradead.org, bpf <bpf@vger.kernel.org>,
Xi Wang <xi.wang@gmail.com>
Subject: Re: [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching
Date: Tue, 7 Jan 2020 09:13:56 +0100 [thread overview]
Message-ID: <CAJ+HfNjoO2ihHMh2NHMQfxG8X1zLdzEq6Ywr=b2qD0tNwXreFA@mail.gmail.com> (raw)
In-Reply-To: <mhng-6be38b2a-78df-4016-aaea-f35aa0acd7e0@palmerdabbelt-glaptop>
Back from the holidays; Sorry about the delayed reply.
On Mon, 23 Dec 2019 at 19:03, Palmer Dabbelt <palmerdabbelt@google.com> wrote:
>
> On Mon, 16 Dec 2019 01:13:36 PST (-0800), Bjorn Topel wrote:
> > This commit adds branch relaxation to the BPF JIT, and with that
[...]
> > @@ -1557,6 +1569,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
> > {
> > bool tmp_blinded = false, extra_pass = false;
> > struct bpf_prog *tmp, *orig_prog = prog;
> > + int pass = 0, prev_ninsns = 0, i;
> > struct rv_jit_data *jit_data;
> > struct rv_jit_context *ctx;
> > unsigned int image_size;
> > @@ -1596,15 +1609,25 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
> > prog = orig_prog;
> > goto out_offset;
> > }
> > + for (i = 0; i < prog->len; i++) {
> > + prev_ninsns += 32;
> > + ctx->offset[i] = prev_ninsns;
> > + }
>
> It feels like the first-order implementation is the same as binutils here: the
> first round is worst cased, after which things can be more exact. We're only
> doing one pass in binutils because most of the relaxation happens in the
> linker, but this approach seems reasonable to me. I'd be interested in seeing
> some benchmarks, as it may be worth relaxing these in the binutils linker as
> well -- I can certainly come up with contrived test cases that aren't relaxed,
> but I'm not sure how common this is.
>
Ah, interesting! Let me try to pull out some branch relaxation
statistics/benchmarks for the BPF selftests.
> My only worry is that that invariant should be more explicit. Specifically,
> I'm thinking that every time offset is updated there should be some sort of
> assertion that the offset is shrinking. This is enforced structurally in the
> binutils code because we only generate code once and then move it around, but
> since you're generating code every time it'd be easy for a bug to sneak in as
> the JIT gets more complicated.
>
Hmm, yes. Maybe use a checksum for the program in addition to the
length invariant, and converge condition would then be prev_len == len
&& prev_crc == crc?
> Since most of the branches should be forward, you'll probably end up with way
> fewer iterations if you do the optimization passes backwards.
>
Good idea!
> > - /* First pass generates the ctx->offset, but does not emit an image. */
> > - if (build_body(ctx, extra_pass)) {
> > - prog = orig_prog;
> > - goto out_offset;
> > + for (i = 0; i < 16; i++) {
> > + pass++;
> > + ctx->ninsns = 0;
> > + if (build_body(ctx, extra_pass)) {
> > + prog = orig_prog;
> > + goto out_offset;
>
> Isn't this returning a broken program if build_body() errors out the first time
> through?
>
Hmm, care to elaborate? I don't see how?
> > + }
> > + build_prologue(ctx);
> > + ctx->epilogue_offset = ctx->ninsns;
> > + build_epilogue(ctx);
> > + if (ctx->ninsns == prev_ninsns)
> > + break;
> > + prev_ninsns = ctx->ninsns;
>
> IDK how important the performance of the JIT is, but you could probably get
> away with skipping an iteration by keeping track of some simple metric that
> determines if it would be possible to
>
...to? Given that the programs are getting larger, performance of the
JIT is important. So, any means the number of passes can be reduced is
a good thing!
Thanks for the review/suggestions!
Björn
next prev parent reply other threads:[~2020-01-07 8:14 UTC|newest]
Thread overview: 33+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-12-16 9:13 [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Björn Töpel
2019-12-16 9:13 ` [PATCH bpf-next v2 1/9] riscv, bpf: fix broken BPF tail calls Björn Töpel
2019-12-16 9:13 ` [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching Björn Töpel
2019-12-16 9:13 ` [PATCH bpf-next v2 3/9] riscv, bpf: add support for far branching when emitting tail call Björn Töpel
2019-12-16 9:13 ` [PATCH bpf-next v2 4/9] riscv, bpf: add support for far jumps and exits Björn Töpel
2019-12-16 9:13 ` [PATCH bpf-next v2 5/9] riscv, bpf: optimize BPF tail calls Björn Töpel
2019-12-16 9:13 ` [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free Björn Töpel
2019-12-16 15:09 ` Daniel Borkmann
2019-12-18 6:23 ` Björn Töpel
2020-01-04 1:32 ` Paul Walmsley
2020-01-07 10:24 ` Björn Töpel
2020-01-07 10:47 ` Paul Walmsley
2020-02-02 13:37 ` Alex Ghiti
2020-02-03 12:28 ` Björn Töpel
2020-02-03 20:57 ` Alex Ghiti
2019-12-16 9:13 ` [PATCH bpf-next v2 7/9] riscv, bpf: optimize calls Björn Töpel
2019-12-16 9:13 ` [PATCH bpf-next v2 8/9] riscv, bpf: add missing uapi header for BPF_PROG_TYPE_PERF_EVENT programs Björn Töpel
2019-12-16 9:13 ` [PATCH bpf-next v2 9/9] riscv, perf: add arch specific perf_arch_bpf_user_pt_regs Björn Töpel
2019-12-19 15:07 ` [PATCH bpf-next v2 0/9] riscv: BPF JIT fix, optimizations and far jumps support Daniel Borkmann
2019-12-19 22:02 ` [PATCH bpf-next v2 1/9] riscv, bpf: fix broken BPF tail calls Palmer Dabbelt
2019-12-23 18:03 ` [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching Palmer Dabbelt
2020-01-07 8:13 ` Björn Töpel [this message]
2020-01-23 2:08 ` Palmer Dabbelt
2019-12-23 18:18 ` [PATCH bpf-next v2 3/9] riscv, bpf: add support for far branching when emitting tail call Palmer Dabbelt
2019-12-23 18:18 ` [PATCH bpf-next v2 4/9] riscv, bpf: add support for far jumps and exits Palmer Dabbelt
2019-12-23 18:29 ` [PATCH bpf-next v2 5/9] riscv, bpf: optimize BPF tail calls Palmer Dabbelt
2019-12-23 18:30 ` [PATCH bpf-next v2 6/9] riscv, bpf: provide RISC-V specific JIT image alloc/free Palmer Dabbelt
2019-12-23 18:58 ` [PATCH bpf-next v2 7/9] riscv, bpf: optimize calls Palmer Dabbelt
2020-01-07 10:14 ` Björn Töpel
2020-01-28 2:15 ` Palmer Dabbelt
2020-02-03 12:11 ` Björn Töpel
2019-12-23 18:58 ` [PATCH bpf-next v2 8/9] riscv, bpf: add missing uapi header for BPF_PROG_TYPE_PERF_EVENT programs Palmer Dabbelt
2019-12-23 18:58 ` [PATCH bpf-next v2 9/9] riscv, perf: add arch specific perf_arch_bpf_user_pt_regs Palmer Dabbelt
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAJ+HfNjoO2ihHMh2NHMQfxG8X1zLdzEq6Ywr=b2qD0tNwXreFA@mail.gmail.com' \
--to=bjorn.topel@gmail.com \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=linux-riscv@lists.infradead.org \
--cc=lukenels@cs.washington.edu \
--cc=netdev@vger.kernel.org \
--cc=palmerdabbelt@google.com \
--cc=xi.wang@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).