linux-riscv.lists.infradead.org archive mirror
 help / color / mirror / Atom feed
From: Palmer Dabbelt <palmerdabbelt@google.com>
To: Bjorn Topel <bjorn.topel@gmail.com>
Cc: daniel@iogearbox.net, netdev@vger.kernel.org, ast@kernel.org,
	lukenels@cs.washington.edu, linux-riscv@lists.infradead.org,
	bpf@vger.kernel.org, xi.wang@gmail.com
Subject: Re: [PATCH bpf-next v2 2/9] riscv, bpf: add support for far branching
Date: Wed, 22 Jan 2020 18:08:57 -0800 (PST)	[thread overview]
Message-ID: <mhng-9d460c8a-52e3-4a65-bd23-6210ad1fbf05@palmerdabbelt-glaptop> (raw)
In-Reply-To: <CAJ+HfNjoO2ihHMh2NHMQfxG8X1zLdzEq6Ywr=b2qD0tNwXreFA@mail.gmail.com>

On Tue, 07 Jan 2020 00:13:56 PST (-0800), Bjorn Topel wrote:
> 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?

That would work, but it breaks my unfinished optimization below.  I was
thinking something more like "every time offset[i] is updated, check that it
gets smaller and otherwise barf".

>> 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?

Ya, I don't either any more.  Hopefully I just got confused between prog and
ctx...

>> > +             }
>> > +             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!

I guess I meant to say "determines if it would be possible to make any
modifications next time".  I was thinking something along the lines of:

* as you run through the program, keep track of the shortest branch distance
* if you didn't remove enough bytes to make that branch cross a relaxation
  boundary, then you know that next time you won't be able to do any useful
  work

You're already computing all the branch lengths, so it's just an extra min().
Since we're assuming a small number of passes (after reversing the relaxation
direction), you'll probably save more work avoiding the extra pass than it'll
take to compute the extra information.  I guess some sort of benchmark would
give a real answer, but it certainly smells like a good idea ;)

>
>
> Thanks for the review/suggestions!
> Björn


  parent reply	other threads:[~2020-01-23  2:09 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
2020-01-23  2:08   ` Palmer Dabbelt [this message]
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=mhng-9d460c8a-52e3-4a65-bd23-6210ad1fbf05@palmerdabbelt-glaptop \
    --to=palmerdabbelt@google.com \
    --cc=ast@kernel.org \
    --cc=bjorn.topel@gmail.com \
    --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=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).