1. 27 Dec, 2017 4 commits
    • Alexei Starovoitov's avatar
      bpf: fix max call depth check · aada9ce6
      Alexei Starovoitov authored
      fix off by one error in max call depth check
      and add a test
      
      Fixes: f4d7e40a ("bpf: introduce function calls (verification)")
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      aada9ce6
    • Alexei Starovoitov's avatar
      selftests/bpf: additional stack depth tests · 6b86c421
      Alexei Starovoitov authored
      to test inner logic of stack depth tracking
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      6b86c421
    • Alexei Starovoitov's avatar
      bpf: fix maximum stack depth tracking logic · 70a87ffe
      Alexei Starovoitov authored
      Instead of computing max stack depth for current call chain
      during the main verifier pass track stack depth of each
      function independently and after do_check() is done do
      another pass over all instructions analyzing depth
      of all possible call stacks.
      
      Fixes: f4d7e40a ("bpf: introduce function calls (verification)")
      Reported-by: default avatarJann Horn <jannh@google.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      70a87ffe
    • Jann Horn's avatar
      bpf: selftest for late caller stack size increase · 6b80ad29
      Jann Horn authored
      This checks that it is not possible to bypass the total stack size check in
      update_stack_depth() by calling a function that uses a large amount of
      stack memory *before* using a large amount of stack memory in the caller.
      
      Currently, the first added testcase causes a rejection as expected, but
      the second testcase is (AFAICS incorrectly) accepted:
      
      [...]
      #483/p calls: stack overflow using two frames (post-call access) FAIL
      Unexpected success to load!
      0: (85) call pc+2
      caller:
       R10=fp0,call_-1
      callee:
       frame1: R1=ctx(id=0,off=0,imm=0) R10=fp0,call_0
      3: (72) *(u8 *)(r10 -300) = 0
      4: (b7) r0 = 0
      5: (95) exit
      returning from callee:
       frame1: R0_w=inv0 R1=ctx(id=0,off=0,imm=0) R10=fp0,call_0
      to caller at 1:
       R0_w=inv0 R10=fp0,call_-1
      
      from 5 to 1: R0=inv0 R10=fp0,call_-1
      1: (72) *(u8 *)(r10 -300) = 0
      2: (95) exit
      processed 6 insns, stack depth 300+300
      [...]
      Summary: 704 PASSED, 1 FAILED
      
      AFAICS the JIT-generated code for the second testcase shows that this
      really causes the stack pointer to be decremented by 300+300:
      
      first function:
      00000000  55                push rbp
      00000001  4889E5            mov rbp,rsp
      00000004  4881EC58010000    sub rsp,0x158
      0000000B  4883ED28          sub rbp,byte +0x28
      [...]
      00000025  E89AB3AFE5        call 0xffffffffe5afb3c4
      0000002A  C685D4FEFFFF00    mov byte [rbp-0x12c],0x0
      [...]
      00000041  4883C528          add rbp,byte +0x28
      00000045  C9                leave
      00000046  C3                ret
      
      second function:
      00000000  55                push rbp
      00000001  4889E5            mov rbp,rsp
      00000004  4881EC58010000    sub rsp,0x158
      0000000B  4883ED28          sub rbp,byte +0x28
      [...]
      00000025  C685D4FEFFFF00    mov byte [rbp-0x12c],0x0
      [...]
      0000003E  4883C528          add rbp,byte +0x28
      00000042  C9                leave
      00000043  C3                ret
      Signed-off-by: default avatarJann Horn <jannh@google.com>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      6b80ad29
  2. 23 Dec, 2017 2 commits
    • Gianluca Borello's avatar
      bpf: fix stacksafe exploration when comparing states · fd05e57b
      Gianluca Borello authored
      Commit cc2b14d5 ("bpf: teach verifier to recognize zero initialized
      stack") introduced a very relaxed check when comparing stacks of different
      states, effectively returning a positive result in many cases where it
      shouldn't.
      
      This can create problems in cases such as this following C pseudocode:
      
      long var;
      long *x = bpf_map_lookup(...);
      if (!x)
              return;
      
      if (*x != 0xbeef)
              var = 0;
      else
              var = 1;
      
      /* This is the key part, calling a helper causes an explored state
       * to be saved with the information that "var" is on the stack as
       * STACK_ZERO, since the helper is first met by the verifier after
       * the "var = 0" assignment. This state will however be wrongly used
       * also for the "var = 1" case, so the verifier assumes "var" is always
       * 0 and will replace the NULL assignment with nops, because the
       * search pruning prevents it from exploring the faulty branch.
       */
      bpf_ktime_get_ns();
      
      if (var)
              *(long *)0 = 0xbeef;
      
      Fix the issue by making sure that the stack is fully explored before
      returning a positive comparison result.
      
      Also attach a couple tests that highlight the bad behavior. In the first
      test, without this fix instructions 16 and 17 are replaced with nops
      instead of being rejected by the verifier.
      
      The second test, instead, allows a program to make a potentially illegal
      read from the stack.
      
      Fixes: cc2b14d5 ("bpf: teach verifier to recognize zero initialized stack")
      Signed-off-by: default avatarGianluca Borello <g.borello@gmail.com>
      Acked-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      fd05e57b
    • David Miller's avatar
      bpf: sparc64: Add JIT support for multi-function programs. · 5f5a6411
      David Miller authored
      Modelled strongly upon the arm64 implementation.
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      5f5a6411
  3. 21 Dec, 2017 4 commits
    • Yonghong Song's avatar
      tools/bpf: adjust rlimit RLIMIT_MEMLOCK for test_dev_cgroup · c475ffad
      Yonghong Song authored
      The default rlimit RLIMIT_MEMLOCK is 64KB. In certain cases,
      e.g. in a test machine mimicking our production system, this test may
      fail due to unable to charge the required memory for prog load:
      
        $ ./test_dev_cgroup
        libbpf: load bpf program failed: Operation not permitted
        libbpf: failed to load program 'cgroup/dev'
        libbpf: failed to load object './dev_cgroup.o'
        Failed to load DEV_CGROUP program
        ...
      
      Changing the default rlimit RLIMIT_MEMLOCK to unlimited
      makes the test pass.
      
      This patch also fixed a problem where when bpf_prog_load fails,
      cleanup_cgroup_environment() should not be called since
      setup_cgroup_environment() has not been invoked. Otherwise,
      the following confusing message will appear:
        ...
        (/home/yhs/local/linux/tools/testing/selftests/bpf/cgroup_helpers.c:95:
         errno: No such file or directory) Opening Cgroup Procs: /mnt/cgroup.procs
        ...
      Signed-off-by: default avatarYonghong Song <yhs@fb.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      c475ffad
    • Alexei Starovoitov's avatar
      Merge branch 'bpftool-improvements-kallsymfix' · 74661776
      Alexei Starovoitov authored
      Daniel Borkmann says:
      
      ====================
      This work adds correlation of maps and calls into the bpftool
      xlated dump in order to help debugging and introspection of
      loaded BPF progs. First patch makes kallsyms work on subprogs
      with bpf calls, and second implements the actual correlation.
      Details and example output can be found in the 2nd patch.
      ====================
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      74661776
    • Daniel Borkmann's avatar
      bpf: allow for correlation of maps and helpers in dump · 7105e828
      Daniel Borkmann authored
      Currently a dump of an xlated prog (post verifier stage) doesn't
      correlate used helpers as well as maps. The prog info lists
      involved map ids, however there's no correlation of where in the
      program they are used as of today. Likewise, bpftool does not
      correlate helper calls with the target functions.
      
      The latter can be done w/o any kernel changes through kallsyms,
      and also has the advantage that this works with inlined helpers
      and BPF calls.
      
      Example, via interpreter:
      
        # tc filter show dev foo ingress
        filter protocol all pref 49152 bpf chain 0
        filter protocol all pref 49152 bpf chain 0 handle 0x1 foo.o:[ingress] \
                            direct-action not_in_hw id 1 tag c74773051b364165   <-- prog id:1
      
        * Output before patch (calls/maps remain unclear):
      
        # bpftool prog dump xlated id 1             <-- dump prog id:1
         0: (b7) r1 = 2
         1: (63) *(u32 *)(r10 -4) = r1
         2: (bf) r2 = r10
         3: (07) r2 += -4
         4: (18) r1 = 0xffff95c47a8d4800
         6: (85) call unknown#73040
         7: (15) if r0 == 0x0 goto pc+18
         8: (bf) r2 = r10
         9: (07) r2 += -4
        10: (bf) r1 = r0
        11: (85) call unknown#73040
        12: (15) if r0 == 0x0 goto pc+23
        [...]
      
        * Output after patch:
      
        # bpftool prog dump xlated id 1
         0: (b7) r1 = 2
         1: (63) *(u32 *)(r10 -4) = r1
         2: (bf) r2 = r10
         3: (07) r2 += -4
         4: (18) r1 = map[id:2]                     <-- map id:2
         6: (85) call bpf_map_lookup_elem#73424     <-- helper call
         7: (15) if r0 == 0x0 goto pc+18
         8: (bf) r2 = r10
         9: (07) r2 += -4
        10: (bf) r1 = r0
        11: (85) call bpf_map_lookup_elem#73424
        12: (15) if r0 == 0x0 goto pc+23
        [...]
      
        # bpftool map show id 2                     <-- show/dump/etc map id:2
        2: hash_of_maps  flags 0x0
              key 4B  value 4B  max_entries 3  memlock 4096B
      
      Example, JITed, same prog:
      
        # tc filter show dev foo ingress
        filter protocol all pref 49152 bpf chain 0
        filter protocol all pref 49152 bpf chain 0 handle 0x1 foo.o:[ingress] \
                        direct-action not_in_hw id 3 tag c74773051b364165 jited
      
        # bpftool prog show id 3
        3: sched_cls  tag c74773051b364165
              loaded_at Dec 19/13:48  uid 0
              xlated 384B  jited 257B  memlock 4096B  map_ids 2
      
        # bpftool prog dump xlated id 3
         0: (b7) r1 = 2
         1: (63) *(u32 *)(r10 -4) = r1
         2: (bf) r2 = r10
         3: (07) r2 += -4
         4: (18) r1 = map[id:2]                      <-- map id:2
         6: (85) call __htab_map_lookup_elem#77408   <-+ inlined rewrite
         7: (15) if r0 == 0x0 goto pc+2                |
         8: (07) r0 += 56                              |
         9: (79) r0 = *(u64 *)(r0 +0)                <-+
        10: (15) if r0 == 0x0 goto pc+24
        11: (bf) r2 = r10
        12: (07) r2 += -4
        [...]
      
      Example, same prog, but kallsyms disabled (in that case we are
      also not allowed to pass any relative offsets, etc, so prog
      becomes pointer sanitized on dump):
      
        # sysctl kernel.kptr_restrict=2
        kernel.kptr_restrict = 2
      
        # bpftool prog dump xlated id 3
         0: (b7) r1 = 2
         1: (63) *(u32 *)(r10 -4) = r1
         2: (bf) r2 = r10
         3: (07) r2 += -4
         4: (18) r1 = map[id:2]
         6: (85) call bpf_unspec#0
         7: (15) if r0 == 0x0 goto pc+2
        [...]
      
      Example, BPF calls via interpreter:
      
        # bpftool prog dump xlated id 1
         0: (85) call pc+2#__bpf_prog_run_args32
         1: (b7) r0 = 1
         2: (95) exit
         3: (b7) r0 = 2
         4: (95) exit
      
      Example, BPF calls via JIT:
      
        # sysctl net.core.bpf_jit_enable=1
        net.core.bpf_jit_enable = 1
        # sysctl net.core.bpf_jit_kallsyms=1
        net.core.bpf_jit_kallsyms = 1
      
        # bpftool prog dump xlated id 1
         0: (85) call pc+2#bpf_prog_3b185187f1855c4c_F
         1: (b7) r0 = 1
         2: (95) exit
         3: (b7) r0 = 2
         4: (95) exit
      
      And finally, an example for tail calls that is now working
      as well wrt correlation:
      
        # bpftool prog dump xlated id 2
        [...]
        10: (b7) r2 = 8
        11: (85) call bpf_trace_printk#-41312
        12: (bf) r1 = r6
        13: (18) r2 = map[id:1]
        15: (b7) r3 = 0
        16: (85) call bpf_tail_call#12
        17: (b7) r1 = 42
        18: (6b) *(u16 *)(r6 +46) = r1
        19: (b7) r0 = 0
        20: (95) exit
      
        # bpftool map show id 1
        1: prog_array  flags 0x0
              key 4B  value 4B  max_entries 1  memlock 4096B
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      Acked-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      7105e828
    • Daniel Borkmann's avatar
      bpf: fix kallsyms handling for subprogs · 4f74d809
      Daniel Borkmann authored
      Right now kallsyms handling is not working with JITed subprogs.
      The reason is that when in 1c2a088a ("bpf: x64: add JIT support
      for multi-function programs") in jit_subprogs() they are passed
      to bpf_prog_kallsyms_add(), then their prog type is 0, which BPF
      core will think it's a cBPF program as only cBPF programs have a
      0 type. Thus, they need to inherit the type from the main prog.
      
      Once that is fixed, they are indeed added to the BPF kallsyms
      infra, but their tag is 0. Therefore, since intention is to add
      them as bpf_prog_F_<tag>, we need to pass them to bpf_prog_calc_tag()
      first. And once this is resolved, there is a use-after-free on
      prog cleanup: we remove the kallsyms entry from the main prog,
      later walk all subprogs and call bpf_jit_free() on them. However,
      the kallsyms linkage was never released on them. Thus, do that
      for all subprogs right in __bpf_prog_put() when refcount hits 0.
      
      Fixes: 1c2a088a ("bpf: x64: add JIT support for multi-function programs")
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      Acked-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      4f74d809
  4. 20 Dec, 2017 1 commit
  5. 19 Dec, 2017 6 commits
  6. 18 Dec, 2017 23 commits