netdev - Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin

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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <20190125160204.GD4240@linux.ibm.com>
Date:   Fri, 25 Jan 2019 08:02:04 -0800
From:   "Paul E. McKenney" <paulmck@...ux.ibm.com>
To:     Alexei Starovoitov <ast@...com>
Cc:     Alexei Starovoitov <alexei.starovoitov@...il.com>,
        Jann Horn <jannh@...gle.com>,
        Peter Zijlstra <peterz@...radead.org>,
        Alexei Starovoitov <ast@...nel.org>,
        "David S. Miller" <davem@...emloft.net>,
        Daniel Borkmann <daniel@...earbox.net>,
        "jakub.kicinski@...ronome.com" <jakub.kicinski@...ronome.com>,
        Network Development <netdev@...r.kernel.org>,
        Kernel Team <Kernel-team@...com>,
        Ingo Molnar <mingo@...hat.com>,
        Will Deacon <will.deacon@....com>
Subject: Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

On Fri, Jan 25, 2019 at 04:47:20AM +0000, Alexei Starovoitov wrote:
> On 1/24/19 8:31 PM, Paul E. McKenney wrote:
> > On Fri, Jan 25, 2019 at 04:27:02AM +0000, Alexei Starovoitov wrote:
> >> On 1/24/19 6:38 PM, Alexei Starovoitov wrote:
> >>>> For programs created with CAP_SYS_ADMIN,
> >>>> things get more tricky because you can create your own functions and
> >>>> call them repeatedly; I'm not sure whether the pessimal runtime there
> >>>> becomes exponential, or whether there is some check that catches this.
> >>> I think you're referring to bpf-to-bpf calls.
> >>> The limit it still the same. 4k per program including all calls.
> >>> tail calls are not allowed when bpf-to-bpf is used. So no 32 multiplier.
> >>
> >> Jann,
> >>
> >> I think you meant
> >> main:
> >> call A
> >> call A
> >> call A
> >> exit
> >> A:
> >> call B
> >> call B
> >> call B
> >> exit
> >> B:
> >> call C
> >> ...
> >>
> >> scenario when everything fits into 4k?
> >> Would be great if you can construct such test while we're fixing
> >> the rest of the issues brought up in this thread.
> >> It will definitely be no more than BPF_COMPLEXITY_LIMIT_INSNS
> >> which is 128k, but I wonder what will be the actual number of
> >> executed insns.
> >> I think such clever constructed sequence can actually
> >> hit 128k executed too.
> >> It would be awesome test to add to test_verifier.c
> >> We have some of such pushing-the-boundary tests in lib/test_bpf.c
> >> that are generated in assembler.
> >> The longest takes 23853 nanoseconds, but clever bpf2bpf call hack
> >> like above with map_update call in the leaf function should
> >> certainly take much longer.
> >> I accept Paul's challenge to try to get such fancy bpf prog
> >> to take 100 millseconds :)
> > 
> > Fair enough!  But once you meet my challenge, the RCU CPU stall warning
> > code will challenge you to hit 21 seconds (or only three seconds given
> > an appropriately configured kernel).  ;-)
> 
>          if (till_stall_check < 3) {
>                  WRITE_ONCE(rcu_cpu_stall_timeout, 3);
>                  till_stall_check = 3;
> 
> let's change that limit to 1 !

Heh!  It was 1.5 seconds back in DYNIX/ptx.  However, taking it below
3 seconds would require some other adjustments.  Something about there
being a lot more moving parts in the Linux kernel.

> Seriously though folks have proposed to teach bpf verifier
> to sprinkle cond_resched() automatically into bpf program
> when critical path through the program reaches certain insn limit.
> The verifier can easily be taught to compute the longest path.

Good point, for PREEMPT=n, cond_resched() will help.

> Other folks proposed to get rid of 4k limit when prog
> is preemptable and executing in user context.
> That's when srcu will come into play.

OK, please let me know when you get to this point so that I can get
the lightweight variant of SRCU moving forward.

							Thanx, Paul