linux-riscv.lists.infradead.org archive mirror
 help / color / mirror / Atom feed
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


  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 \
    --subject='Re: [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching' \
    /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

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).