1. 31 Mar, 2020 1 commit
    • Andrii Nakryiko's avatar
      bpf: Implement bpf_link-based cgroup BPF program attachment · af6eea57
      Andrii Nakryiko authored
      Implement new sub-command to attach cgroup BPF programs and return FD-based
      bpf_link back on success. bpf_link, once attached to cgroup, cannot be
      replaced, except by owner having its FD. Cgroup bpf_link supports only
      BPF_F_ALLOW_MULTI semantics. Both link-based and prog-based BPF_F_ALLOW_MULTI
      attachments can be freely intermixed.
      
      To prevent bpf_cgroup_link from keeping cgroup alive past the point when no
      BPF program can be executed, implement auto-detachment of link. When
      cgroup_bpf_release() is called, all attached bpf_links are forced to release
      cgroup refcounts, but they leave bpf_link otherwise active and allocated, as
      well as still owning underlying bpf_prog. This is because user-space might
      still have FDs open and active, so bpf_link as a user-referenced object can't
      be freed yet. Once last active FD is closed, bpf_link will be freed and
      underlying bpf_prog refcount will be dropped. But cgroup refcount won't be
      touched, because cgroup is released already.
      
      The inherent race between bpf_cgroup_link release (from closing last FD) and
      cgroup_bpf_release() is resolved by both operations taking cgroup_mutex. So
      the only additional check required is when bpf_cgroup_link attempts to detach
      itself from cgroup. At that time we need to check whether there is still
      cgroup associated with that link. And if not, exit with success, because
      bpf_cgroup_link was already successfully detached.
      Signed-off-by: default avatarAndrii Nakryiko <andriin@fb.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Acked-by: default avatarRoman Gushchin <guro@fb.com>
      Link: https://lore.kernel.org/bpf/20200330030001.2312810-2-andriin@fb.com
      af6eea57
  2. 30 Mar, 2020 20 commits
    • Alexei Starovoitov's avatar
      Merge branch 'subreg-bounds' · e5ffcc91
      Alexei Starovoitov authored
      John Fastabend says:
      
      ====================
      This series adds ALU32 signed and unsigned min/max bounds.
      
      The origins of this work is to fix do_refine_retval_range() which before
      this series clamps the return value bounds to [0, max]. However, this
      is not correct because its possible these functions may return negative
      errors so the correct bound is [*MIN, max]. Where *MIN is the signed
      and unsigned min values U64_MIN and S64_MIN. And 'max' here is the max
      positive value returned by this routine.
      
      Patch 1 changes the do_refine_retval_range() to return the correct bounds
      but this breaks existing programs that were depending on the old incorrect
      bound. To repair these old programs we add ALU32 bounds to properly track
      the return values from these helpers. The ALU32 bounds are needed because
      clang realizes these helepers return 'int' type and will use jmp32 ops
      with the return value.  With current state of things this does little to
      help 64bit bounds and with patch 1 applied will cause many programs to
      fail verifier pass. See patch 5 for trace details on how this happens.
      
      Patch 2 does the ALU32 addition it adds the new bounds and populates them
      through the verifier. Design note, initially a var32 was added but as
      pointed out by Alexei and Edward it is not strictly needed so it was
      removed here. This worked out nicely.
      
      Patch 3 notes that the refine return value can now also bound the 32-bit
      subregister allowing better bouinds tracking in these cases.
      
      Patches 4 adds a C test case to test_progs which will cause the verifier
      to fail if new 32bit and do_refine_retval_range() is incorrect.
      
      Patches 5 and 6 fix test cases that broke after refining the return
      values from helpers. I attempted to be explicit about each failure and
      why we need the change. See patches for details.
      
      Patch 7 adds some bounds check tests to ensure bounds checking when
      mixing alu32, alu64 and jmp32 ops together.
      
      Thanks to Alexei, Edward, and Daniel for initial feedback it helped clean
      this up a lot.
      
      v2:
        - rebased to bpf-next
        - fixed tnum equals optimization for combining 32->64bits
        - updated patch to fix verifier test correctly
        - updated refine_retval_range to set both s32_*_value and s*_value we
          need both to get better bounds tracking
      ====================
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      e5ffcc91
    • John Fastabend's avatar
      bpf: Test_verifier, add alu32 bounds tracking tests · 41f70fe0
      John Fastabend authored
      Its possible to have divergent ALU32 and ALU64 bounds when using JMP32
      instructins and ALU64 arithmatic operations. Sometimes the clang will
      even generate this code. Because the case is a bit tricky lets add
      a specific test for it.
      
      Here is  pseudocode asm version to illustrate the idea,
      
       1 r0 = 0xffffffff00000001;
       2 if w0 > 1 goto %l[fail];
       3 r0 += 1
       5 if w0 > 2 goto %l[fail]
       6 exit
      
      The intent here is the verifier will fail the load if the 32bit bounds
      are not tracked correctly through ALU64 op. Similarly we can check the
      64bit bounds are correctly zero extended after ALU32 ops.
      
       1 r0 = 0xffffffff00000001;
       2 w0 += 1
       2 if r0 > 3 goto %l[fail];
       6 exit
      
      The above will fail if we do not correctly zero extend 64bit bounds
      after 32bit op.
      Signed-off-by: default avatarJohn Fastabend <john.fastabend@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/158560430155.10843.514209255758200922.stgit@john-Precision-5820-Tower
      41f70fe0
    • John Fastabend's avatar
      bpf: Test_verifier, #65 error message updates for trunc of boundary-cross · 32f13a5a
      John Fastabend authored
      After changes to add update_reg_bounds after ALU ops and 32-bit bounds
      tracking truncation of boundary crossing range will fail earlier and with
      a different error message. Now the test error trace is the following
      
      11: (17) r1 -= 2147483584
      12: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
          R1_w=invP(id=0,smin_value=-2147483584,smax_value=63)
          R10=fp0 fp-8_w=mmmmmmmm
      12: (17) r1 -= 2147483584
      13: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
          R1_w=invP(id=0,
                    umin_value=18446744069414584448,umax_value=18446744071562068095,
                    var_off=(0xffffffff00000000; 0xffffffff))
          R10=fp0 fp-8_w=mmmmmmmm
      13: (77) r1 >>= 8
      14: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0)
          R1_w=invP(id=0,
                    umin_value=72057594021150720,umax_value=72057594029539328,
                    var_off=(0xffffffff000000; 0xffffff),
                    s32_min_value=-16777216,s32_max_value=-1,
                    u32_min_value=-16777216)
          R10=fp0 fp-8_w=mmmmmmmm
      14: (0f) r0 += r1
      value 72057594021150720 makes map_value pointer be out of bounds
      
      Because we have 'umin_value == umax_value' instead of previously
      where 'umin_value != umax_value' we can now fail earlier noting
      that pointer addition is out of bounds.
      Signed-off-by: default avatarJohn Fastabend <john.fastabend@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/158560428103.10843.6316594510312781186.stgit@john-Precision-5820-Tower
      32f13a5a
    • John Fastabend's avatar
      bpf: Test_verifier, bpf_get_stack return value add <0 · 9ac26e99
      John Fastabend authored
      With current ALU32 subreg handling and retval refine fix from last
      patches we see an expected failure in test_verifier. With verbose
      verifier state being printed at each step for clarity we have the
      following relavent lines [I omit register states that are not
      necessarily useful to see failure cause],
      
      #101/p bpf_get_stack return R0 within range FAIL
      Failed to load prog 'Success'!
      [..]
      14: (85) call bpf_get_stack#67
       R0_w=map_value(id=0,off=0,ks=8,vs=48,imm=0)
       R3_w=inv48
      15:
       R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
      15: (b7) r1 = 0
      16:
       R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
       R1_w=inv0
      16: (bf) r8 = r0
      17:
       R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
       R1_w=inv0
       R8_w=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
      17: (67) r8 <<= 32
      18:
       R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
       R1_w=inv0
       R8_w=inv(id=0,smax_value=9223372032559808512,
                     umax_value=18446744069414584320,
                     var_off=(0x0; 0xffffffff00000000),
                     s32_min_value=0,
                     s32_max_value=0,
                     u32_max_value=0,
                     var32_off=(0x0; 0x0))
      18: (c7) r8 s>>= 32
      19
       R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
       R1_w=inv0
       R8_w=inv(id=0,smin_value=-2147483648,
                     smax_value=2147483647,
                     var32_off=(0x0; 0xffffffff))
      19: (cd) if r1 s< r8 goto pc+16
       R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
       R1_w=inv0
       R8_w=inv(id=0,smin_value=-2147483648,
                     smax_value=0,
                     var32_off=(0x0; 0xffffffff))
      20:
       R0=inv(id=0,smax_value=48,var32_off=(0x0; 0xffffffff))
       R1_w=inv0
       R8_w=inv(id=0,smin_value=-2147483648,
                     smax_value=0,
       R9=inv48
      20: (1f) r9 -= r8
      21: (bf) r2 = r7
      22:
       R2_w=map_value(id=0,off=0,ks=8,vs=48,imm=0)
      22: (0f) r2 += r8
      value -2147483648 makes map_value pointer be out of bounds
      
      After call bpf_get_stack() on line 14 and some moves we have at line 16
      an r8 bound with max_value 48 but an unknown min value. This is to be
      expected bpf_get_stack call can only return a max of the input size but
      is free to return any negative error in the 32-bit register space. The
      C helper is returning an int so will use lower 32-bits.
      
      Lines 17 and 18 clear the top 32 bits with a left/right shift but use
      ARSH so we still have worst case min bound before line 19 of -2147483648.
      At this point the signed check 'r1 s< r8' meant to protect the addition
      on line 22 where dst reg is a map_value pointer may very well return
      true with a large negative number. Then the final line 22 will detect
      this as an invalid operation and fail the program. What we want to do
      is proceed only if r8 is positive non-error. So change 'r1 s< r8' to
      'r1 s> r8' so that we jump if r8 is negative.
      
      Next we will throw an error because we access past the end of the map
      value. The map value size is 48 and sizeof(struct test_val) is 48 so
      we walk off the end of the map value on the second call to
      get bpf_get_stack(). Fix this by changing sizeof(struct test_val) to
      24 by using 'sizeof(struct test_val) / 2'. After this everything passes
      as expected.
      Signed-off-by: default avatarJohn Fastabend <john.fastabend@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/158560426019.10843.3285429543232025187.stgit@john-Precision-5820-Tower
      9ac26e99
    • John Fastabend's avatar
      bpf: Test_progs, add test to catch retval refine error handling · d2db08c7
      John Fastabend authored
      Before this series the verifier would clamp return bounds of
      bpf_get_stack() to [0, X] and this led the verifier to believe
      that a JMP_JSLT 0 would be false and so would prune that path.
      
      The result is anything hidden behind that JSLT would be unverified.
      Add a test to catch this case by hiding an goto pc-1 behind the
      check which will cause an infinite loop if not rejected.
      Signed-off-by: default avatarJohn Fastabend <john.fastabend@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/158560423908.10843.11783152347709008373.stgit@john-Precision-5820-Tower
      d2db08c7
    • John Fastabend's avatar
      bpf: Verifier, refine 32bit bound in do_refine_retval_range · fa123ac0
      John Fastabend authored
      Further refine return values range in do_refine_retval_range by noting
      these are int return types (We will assume here that int is a 32-bit type).
      
      Two reasons to pull this out of original patch. First it makes the original
      fix impossible to backport. And second I've not seen this as being problematic
      in practice unlike the other case.
      
      Fixes: 849fa506 ("bpf/verifier: refine retval R0 state for bpf_get_stack helper")
      Signed-off-by: default avatarJohn Fastabend <john.fastabend@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/158560421952.10843.12496354931526965046.stgit@john-Precision-5820-Tower
      fa123ac0
    • John Fastabend's avatar
      bpf: Verifier, do explicit ALU32 bounds tracking · 3f50f132
      John Fastabend authored
      It is not possible for the current verifier to track ALU32 and JMP ops
      correctly. This can result in the verifier aborting with errors even though
      the program should be verifiable. BPF codes that hit this can work around
      it by changin int variables to 64-bit types, marking variables volatile,
      etc. But this is all very ugly so it would be better to avoid these tricks.
      
      But, the main reason to address this now is do_refine_retval_range() was
      assuming return values could not be negative. Once we fixed this code that
      was previously working will no longer work. See do_refine_retval_range()
      patch for details. And we don't want to suddenly cause programs that used
      to work to fail.
      
      The simplest example code snippet that illustrates the problem is likely
      this,
      
       53: w8 = w0                    // r8 <- [0, S32_MAX],
                                      // w8 <- [-S32_MIN, X]
       54: w8 <s 0                    // r8 <- [0, U32_MAX]
                                      // w8 <- [0, X]
      
      The expected 64-bit and 32-bit bounds after each line are shown on the
      right. The current issue is without the w* bounds we are forced to use
      the worst case bound of [0, U32_MAX]. To resolve this type of case,
      jmp32 creating divergent 32-bit bounds from 64-bit bounds, we add explicit
      32-bit register bounds s32_{min|max}_value and u32_{min|max}_value. Then
      from branch_taken logic creating new bounds we can track 32-bit bounds
      explicitly.
      
      The next case we observed is ALU ops after the jmp32,
      
       53: w8 = w0                    // r8 <- [0, S32_MAX],
                                      // w8 <- [-S32_MIN, X]
       54: w8 <s 0                    // r8 <- [0, U32_MAX]
                                      // w8 <- [0, X]
       55: w8 += 1                    // r8 <- [0, U32_MAX+1]
                                      // w8 <- [0, X+1]
      
      In order to keep the bounds accurate at this point we also need to track
      ALU32 ops. To do this we add explicit ALU32 logic for each of the ALU
      ops, mov, add, sub, etc.
      
      Finally there is a question of how and when to merge bounds. The cases
      enumerate here,
      
      1. MOV ALU32   - zext 32-bit -> 64-bit
      2. MOV ALU64   - copy 64-bit -> 32-bit
      3. op  ALU32   - zext 32-bit -> 64-bit
      4. op  ALU64   - n/a
      5. jmp ALU32   - 64-bit: var32_off | upper_32_bits(var64_off)
      6. jmp ALU64   - 32-bit: (>> (<< var64_off))
      
      Details for each case,
      
      For "MOV ALU32" BPF arch zero extends so we simply copy the bounds
      from 32-bit into 64-bit ensuring we truncate var_off and 64-bit
      bounds correctly. See zext_32_to_64.
      
      For "MOV ALU64" copy all bounds including 32-bit into new register. If
      the src register had 32-bit bounds the dst register will as well.
      
      For "op ALU32" zero extend 32-bit into 64-bit the same as move,
      see zext_32_to_64.
      
      For "op ALU64" calculate both 32-bit and 64-bit bounds no merging
      is done here. Except we have a special case. When RSH or ARSH is
      done we can't simply ignore shifting bits from 64-bit reg into the
      32-bit subreg. So currently just push bounds from 64-bit into 32-bit.
      This will be correct in the sense that they will represent a valid
      state of the register. However we could lose some accuracy if an
      ARSH is following a jmp32 operation. We can handle this special
      case in a follow up series.
      
      For "jmp ALU32" mark 64-bit reg unknown and recalculate 64-bit bounds
      from tnum by setting var_off to ((<<(>>var_off)) | var32_off). We
      special case if 64-bit bounds has zero'd upper 32bits at which point
      we can simply copy 32-bit bounds into 64-bit register. This catches
      a common compiler trick where upper 32-bits are zeroed and then
      32-bit ops are used followed by a 64-bit compare or 64-bit op on
      a pointer. See __reg_combine_64_into_32().
      
      For "jmp ALU64" cast the bounds of the 64bit to their 32-bit
      counterpart. For example s32_min_value = (s32)reg->smin_value. For
      tnum use only the lower 32bits via, (>>(<<var_off)). See
      __reg_combine_64_into_32().
      Signed-off-by: default avatarJohn Fastabend <john.fastabend@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/158560419880.10843.11448220440809118343.stgit@john-Precision-5820-Tower
      3f50f132
    • John Fastabend's avatar
      bpf: Verifier, do_refine_retval_range may clamp umin to 0 incorrectly · 10060503
      John Fastabend authored
      do_refine_retval_range() is called to refine return values from specified
      helpers, probe_read_str and get_stack at the moment, the reasoning is
      because both have a max value as part of their input arguments and
      because the helper ensure the return value will not be larger than this
      we can set smax values of the return register, r0.
      
      However, the return value is a signed integer so setting umax is incorrect
      It leads to further confusion when the do_refine_retval_range() then calls,
      __reg_deduce_bounds() which will see a umax value as meaning the value is
      unsigned and then assuming it is unsigned set the smin = umin which in this
      case results in 'smin = 0' and an 'smax = X' where X is the input argument
      from the helper call.
      
      Here are the comments from _reg_deduce_bounds() on why this would be safe
      to do.
      
       /* Learn sign from unsigned bounds.  Signed bounds cross the sign
        * boundary, so we must be careful.
        */
       if ((s64)reg->umax_value >= 0) {
      	/* Positive.  We can't learn anything from the smin, but smax
      	 * is positive, hence safe.
      	 */
      	reg->smin_value = reg->umin_value;
      	reg->smax_value = reg->umax_value = min_t(u64, reg->smax_value,
      						  reg->umax_value);
      
      But now we incorrectly have a return value with type int with the
      signed bounds (0,X). Suppose the return value is negative, which is
      possible the we have the verifier and reality out of sync. Among other
      things this may result in any error handling code being falsely detected
      as dead-code and removed. For instance the example below shows using
      bpf_probe_read_str() causes the error path to be identified as dead
      code and removed.
      
      >From the 'llvm-object -S' dump,
      
       r2 = 100
       call 45
       if r0 s< 0 goto +4
       r4 = *(u32 *)(r7 + 0)
      
      But from dump xlate
      
        (b7) r2 = 100
        (85) call bpf_probe_read_compat_str#-96768
        (61) r4 = *(u32 *)(r7 +0)  <-- dropped if goto
      
      Due to verifier state after call being
      
       R0=inv(id=0,umax_value=100,var_off=(0x0; 0x7f))
      
      To fix omit setting the umax value because its not safe. The only
      actual bounds we know is the smax. This results in the correct bounds
      (SMIN, X) where X is the max length from the helper. After this the
      new verifier state looks like the following after call 45.
      
      R0=inv(id=0,smax_value=100)
      
      Then xlated version no longer removed dead code giving the expected
      result,
      
        (b7) r2 = 100
        (85) call bpf_probe_read_compat_str#-96768
        (c5) if r0 s< 0x0 goto pc+4
        (61) r4 = *(u32 *)(r7 +0)
      
      Note, bpf_probe_read_* calls are root only so we wont hit this case
      with non-root bpf users.
      
      v3: comment had some documentation about meta set to null case which
      is not relevant here and confusing to include in the comment.
      
      v2 note: In original version we set msize_smax_value from check_func_arg()
      and propagated this into smax of retval. The logic was smax is the bound
      on the retval we set and because the type in the helper is ARG_CONST_SIZE
      we know that the reg is a positive tnum_const() so umax=smax. Alexei
      pointed out though this is a bit odd to read because the register in
      check_func_arg() has a C type of u32 and the umax bound would be the
      normally relavent bound here. Pulling in extra knowledge about future
      checks makes reading the code a bit tricky. Further having a signed
      meta data that can only ever be positive is also a bit odd. So dropped
      the msize_smax_value metadata and made it a u64 msize_max_value to
      indicate its unsigned. And additionally save bound from umax value in
      check_arg_funcs which is the same as smax due to as noted above tnumx_cont
      and negative check but reads better. By my analysis nothing functionally
      changes in v2 but it does get easier to read so that is win.
      
      Fixes: 849fa506 ("bpf/verifier: refine retval R0 state for bpf_get_stack helper")
      Signed-off-by: default avatarJohn Fastabend <john.fastabend@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/158560417900.10843.14351995140624628941.stgit@john-Precision-5820-Tower
      10060503
    • KP Singh's avatar
      bpf, lsm: Make BPF_LSM depend on BPF_EVENTS · 4edf16b7
      KP Singh authored
      LSM and tracing programs share their helpers with bpf_tracing_func_proto
      which is only defined (in bpf_trace.c) when BPF_EVENTS is enabled.
      
      Instead of adding __weak symbol, make BPF_LSM depend on BPF_EVENTS so
      that both tracing and LSM programs can actually share helpers.
      
      Fixes: fc611f47 ("bpf: Introduce BPF_PROG_TYPE_LSM")
      Reported-by: default avatarRandy Dunlap <rdunlap@infradead.org>
      Signed-off-by: default avatarKP Singh <kpsingh@google.com>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      Link: https://lore.kernel.org/bpf/20200330204059.13024-1-kpsingh@chromium.org
      4edf16b7
    • Alexei Starovoitov's avatar
      Merge branch 'bpf_sk_assign' · c58b1558
      Alexei Starovoitov authored
      Joe Stringer says:
      
      ====================
      Introduce a new helper that allows assigning a previously-found socket
      to the skb as the packet is received towards the stack, to cause the
      stack to guide the packet towards that socket subject to local routing
      configuration. The intention is to support TProxy use cases more
      directly from eBPF programs attached at TC ingress, to simplify and
      streamline Linux stack configuration in scale environments with Cilium.
      
      Normally in ip{,6}_rcv_core(), the skb will be orphaned, dropping any
      existing socket reference associated with the skb. Existing tproxy
      implementations in netfilter get around this restriction by running the
      tproxy logic after ip_rcv_core() in the PREROUTING table. However, this
      is not an option for TC-based logic (including eBPF programs attached at
      TC ingress).
      
      This series introduces the BPF helper bpf_sk_assign() to associate the
      socket with the skb on the ingress path as the packet is passed up the
      stack. The initial patch in the series simply takes a reference on the
      socket to ensure safety, but later patches relax this for listen
      sockets.
      
      To ensure delivery to the relevant socket, we still consult the routing
      table, for full examples of how to configure see the tests in patch #5;
      the simplest form of the route would look like this:
      
        $ ip route add local default dev lo
      
      This series is laid out as follows:
      * Patch 1 extends the eBPF API to add sk_assign() and defines a new
        socket free function to allow the later paths to understand when the
        socket associated with the skb should be kept through receive.
      * Patches 2-3 optimize the receive path to avoid taking a reference on
        listener sockets during receive.
      * Patches 4-5 extends the selftests with examples of the new
        functionality and validation of correct behaviour.
      
      Changes since v4:
      * Fix build with CONFIG_INET disabled
      * Rebase
      
      Changes since v3:
      * Use sock_gen_put() directly instead of sock_edemux() from sock_pfree()
      * Commit message wording fixups
      * Add acks from Martin, Lorenz
      * Rebase
      
      Changes since v2:
      * Add selftests for UDP socket redirection
      * Drop the early demux optimization patch (defer for more testing)
      * Fix check for orphaning after TC act return
      * Tidy up the tests to clean up properly and be less noisy.
      
      Changes since v1:
      * Replace the metadata_dst approach with using the skb->destructor to
        determine whether the socket has been prefetched. This is much
        simpler.
      * Avoid taking a reference on listener sockets during receive
      * Restrict assigning sockets across namespaces
      * Restrict assigning SO_REUSEPORT sockets
      * Fix cookie usage for socket dst check
      * Rebase the tests against test_progs infrastructure
      * Tidy up commit messages
      ====================
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      c58b1558
    • Joe Stringer's avatar
      selftests: bpf: Extend sk_assign tests for UDP · 8a02a170
      Joe Stringer authored
      Add support for testing UDP sk_assign to the existing tests.
      Signed-off-by: default avatarJoe Stringer <joe@wand.net.nz>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Acked-by: default avatarLorenz Bauer <lmb@cloudflare.com>
      Acked-by: default avatarMartin KaFai Lau <kafai@fb.com>
      Link: https://lore.kernel.org/bpf/20200329225342.16317-6-joe@wand.net.nz
      8a02a170
    • Lorenz Bauer's avatar
      selftests: bpf: Add test for sk_assign · 2d7824ff
      Lorenz Bauer authored
      Attach a tc direct-action classifier to lo in a fresh network
      namespace, and rewrite all connection attempts to localhost:4321
      to localhost:1234 (for port tests) and connections to unreachable
      IPv4/IPv6 IPs to the local socket (for address tests). Includes
      implementations for both TCP and UDP.
      
      Keep in mind that both client to server and server to client traffic
      passes the classifier.
      Signed-off-by: default avatarLorenz Bauer <lmb@cloudflare.com>
      Signed-off-by: default avatarJoe Stringer <joe@wand.net.nz>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Acked-by: default avatarMartin KaFai Lau <kafai@fb.com>
      Link: https://lore.kernel.org/bpf/20200329225342.16317-5-joe@wand.net.nzCo-authored-by: default avatarJoe Stringer <joe@wand.net.nz>
      2d7824ff
    • Joe Stringer's avatar
      bpf: Don't refcount LISTEN sockets in sk_assign() · 7ae215d2
      Joe Stringer authored
      Avoid taking a reference on listen sockets by checking the socket type
      in the sk_assign and in the corresponding skb_steal_sock() code in the
      the transport layer, and by ensuring that the prefetch free (sock_pfree)
      function uses the same logic to check whether the socket is refcounted.
      Suggested-by: default avatarMartin KaFai Lau <kafai@fb.com>
      Signed-off-by: default avatarJoe Stringer <joe@wand.net.nz>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Acked-by: default avatarMartin KaFai Lau <kafai@fb.com>
      Link: https://lore.kernel.org/bpf/20200329225342.16317-4-joe@wand.net.nz
      7ae215d2
    • Joe Stringer's avatar
      net: Track socket refcounts in skb_steal_sock() · 71489e21
      Joe Stringer authored
      Refactor the UDP/TCP handlers slightly to allow skb_steal_sock() to make
      the determination of whether the socket is reference counted in the case
      where it is prefetched by earlier logic such as early_demux.
      Signed-off-by: default avatarJoe Stringer <joe@wand.net.nz>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Acked-by: default avatarMartin KaFai Lau <kafai@fb.com>
      Link: https://lore.kernel.org/bpf/20200329225342.16317-3-joe@wand.net.nz
      71489e21
    • Joe Stringer's avatar
      bpf: Add socket assign support · cf7fbe66
      Joe Stringer authored
      Add support for TPROXY via a new bpf helper, bpf_sk_assign().
      
      This helper requires the BPF program to discover the socket via a call
      to bpf_sk*_lookup_*(), then pass this socket to the new helper. The
      helper takes its own reference to the socket in addition to any existing
      reference that may or may not currently be obtained for the duration of
      BPF processing. For the destination socket to receive the traffic, the
      traffic must be routed towards that socket via local route. The
      simplest example route is below, but in practice you may want to route
      traffic more narrowly (eg by CIDR):
      
        $ ip route add local default dev lo
      
      This patch avoids trying to introduce an extra bit into the skb->sk, as
      that would require more invasive changes to all code interacting with
      the socket to ensure that the bit is handled correctly, such as all
      error-handling cases along the path from the helper in BPF through to
      the orphan path in the input. Instead, we opt to use the destructor
      variable to switch on the prefetch of the socket.
      Signed-off-by: default avatarJoe Stringer <joe@wand.net.nz>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Acked-by: default avatarMartin KaFai Lau <kafai@fb.com>
      Link: https://lore.kernel.org/bpf/20200329225342.16317-2-joe@wand.net.nz
      cf7fbe66
    • Daniel Borkmann's avatar
      bpf, doc: Add John as official reviewer to BPF subsystem · b49e42a2
      Daniel Borkmann authored
      We've added John Fastabend to our weekly BPF patch review rotation over
      last months now where he provided excellent and timely feedback on BPF
      patches. Therefore, add him to the BPF core reviewer team to the MAINTAINERS
      file to reflect that.
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      Acked-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Acked-by: default avatarJohn Fastabend <john.fastabend@gmail.com>
      Link: https://lore.kernel.org/bpf/0e9a74933b3f21f4c5b5a3bc7f8e900b39805639.1585556231.git.daniel@iogearbox.net
      b49e42a2
    • KP Singh's avatar
      bpf: btf: Fix arg verification in btf_ctx_access() · f50b49a0
      KP Singh authored
      The bounds checking for the arguments accessed in the BPF program breaks
      when the expected_attach_type is not BPF_TRACE_FEXIT, BPF_LSM_MAC or
      BPF_MODIFY_RETURN resulting in no check being done for the default case
      (the programs which do not receive the return value of the attached
      function in its arguments) when the index of the argument being accessed
      is equal to the number of arguments (nr_args).
      
      This was a result of a misplaced "else if" block  introduced by the
      Commit 6ba43b76 ("bpf: Attachment verification for
      BPF_MODIFY_RETURN")
      
      Fixes: 6ba43b76 ("bpf: Attachment verification for BPF_MODIFY_RETURN")
      Reported-by: default avatarJann Horn <jannh@google.com>
      Signed-off-by: default avatarKP Singh <kpsingh@google.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20200330144246.338-1-kpsingh@chromium.org
      f50b49a0
    • Jann Horn's avatar
      bpf: Simplify reg_set_min_max_inv handling · 0fc31b10
      Jann Horn authored
      reg_set_min_max_inv() contains exactly the same logic as reg_set_min_max(),
      just flipped around. While this makes sense in a cBPF verifier (where ALU
      operations are not symmetric), it does not make sense for eBPF.
      
      Replace reg_set_min_max_inv() with a helper that flips the opcode around,
      then lets reg_set_min_max() do the complicated work.
      Signed-off-by: default avatarJann Horn <jannh@google.com>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20200330160324.15259-4-daniel@iogearbox.net
      0fc31b10
    • Jann Horn's avatar
      bpf: Fix tnum constraints for 32-bit comparisons · 604dca5e
      Jann Horn authored
      The BPF verifier tried to track values based on 32-bit comparisons by
      (ab)using the tnum state via 581738a6 ("bpf: Provide better register
      bounds after jmp32 instructions"). The idea is that after a check like
      this:
      
          if ((u32)r0 > 3)
            exit
      
      We can't meaningfully constrain the arithmetic-range-based tracking, but
      we can update the tnum state to (value=0,mask=0xffff'ffff'0000'0003).
      However, the implementation from 581738a6 didn't compute the tnum
      constraint based on the fixed operand, but instead derives it from the
      arithmetic-range-based tracking. This means that after the following
      sequence of operations:
      
          if (r0 >= 0x1'0000'0001)
            exit
          if ((u32)r0 > 7)
            exit
      
      The verifier assumed that the lower half of r0 is in the range (0, 0)
      and apply the tnum constraint (value=0,mask=0xffff'ffff'0000'0000) thus
      causing the overall tnum to be (value=0,mask=0x1'0000'0000), which was
      incorrect. Provide a fixed implementation.
      
      Fixes: 581738a6 ("bpf: Provide better register bounds after jmp32 instructions")
      Signed-off-by: default avatarJann Horn <jannh@google.com>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20200330160324.15259-3-daniel@iogearbox.net
      604dca5e
    • Daniel Borkmann's avatar
      bpf: Undo incorrect __reg_bound_offset32 handling · f2d67fec
      Daniel Borkmann authored
      Anatoly has been fuzzing with kBdysch harness and reported a hang in
      one of the outcomes:
      
        0: (b7) r0 = 808464432
        1: (7f) r0 >>= r0
        2: (14) w0 -= 808464432
        3: (07) r0 += 808464432
        4: (b7) r1 = 808464432
        5: (de) if w1 s<= w0 goto pc+0
         R0_w=invP(id=0,umin_value=808464432,umax_value=5103431727,var_off=(0x30303020;0x10000001f)) R1_w=invP808464432 R10=fp0
        6: (07) r0 += -2144337872
        7: (14) w0 -= -1607454672
        8: (25) if r0 > 0x30303030 goto pc+0
         R0_w=invP(id=0,umin_value=271581184,umax_value=271581311,var_off=(0x10300000;0x7f)) R1_w=invP808464432 R10=fp0
        9: (76) if w0 s>= 0x303030 goto pc+2
        12: (95) exit
      
        from 8 to 9: safe
      
        from 5 to 6: R0_w=invP(id=0,umin_value=808464432,umax_value=5103431727,var_off=(0x30303020;0x10000001f)) R1_w=invP808464432 R10=fp0
        6: (07) r0 += -2144337872
        7: (14) w0 -= -1607454672
        8: (25) if r0 > 0x30303030 goto pc+0
         R0_w=invP(id=0,umin_value=271581184,umax_value=271581311,var_off=(0x10300000;0x7f)) R1_w=invP808464432 R10=fp0
        9: safe
      
        from 8 to 9: safe
        verification time 589 usec
        stack depth 0
        processed 17 insns (limit 1000000) [...]
      
      The underlying program was xlated as follows:
      
        # bpftool p d x i 9
         0: (b7) r0 = 808464432
         1: (7f) r0 >>= r0
         2: (14) w0 -= 808464432
         3: (07) r0 += 808464432
         4: (b7) r1 = 808464432
         5: (de) if w1 s<= w0 goto pc+0
         6: (07) r0 += -2144337872
         7: (14) w0 -= -1607454672
         8: (25) if r0 > 0x30303030 goto pc+0
         9: (76) if w0 s>= 0x303030 goto pc+2
        10: (05) goto pc-1
        11: (05) goto pc-1
        12: (95) exit
      
      The verifier rewrote original instructions it recognized as dead code with
      'goto pc-1', but reality differs from verifier simulation in that we're
      actually able to trigger a hang due to hitting the 'goto pc-1' instructions.
      
      Taking different examples to make the issue more obvious: in this example
      we're probing bounds on a completely unknown scalar variable in r1:
      
        [...]
        5: R0_w=inv1 R1_w=inv(id=0) R10=fp0
        5: (18) r2 = 0x4000000000
        7: R0_w=inv1 R1_w=inv(id=0) R2_w=inv274877906944 R10=fp0
        7: (18) r3 = 0x2000000000
        9: R0_w=inv1 R1_w=inv(id=0) R2_w=inv274877906944 R3_w=inv137438953472 R10=fp0
        9: (18) r4 = 0x400
        11: R0_w=inv1 R1_w=inv(id=0) R2_w=inv274877906944 R3_w=inv137438953472 R4_w=inv1024 R10=fp0
        11: (18) r5 = 0x200
        13: R0_w=inv1 R1_w=inv(id=0) R2_w=inv274877906944 R3_w=inv137438953472 R4_w=inv1024 R5_w=inv512 R10=fp0
        13: (2d) if r1 > r2 goto pc+4
         R0_w=inv1 R1_w=inv(id=0,umax_value=274877906944,var_off=(0x0; 0x7fffffffff)) R2_w=inv274877906944 R3_w=inv137438953472 R4_w=inv1024 R5_w=inv512 R10=fp0
        14: R0_w=inv1 R1_w=inv(id=0,umax_value=274877906944,var_off=(0x0; 0x7fffffffff)) R2_w=inv274877906944 R3_w=inv137438953472 R4_w=inv1024 R5_w=inv512 R10=fp0
        14: (ad) if r1 < r3 goto pc+3
         R0_w=inv1 R1_w=inv(id=0,umin_value=137438953472,umax_value=274877906944,var_off=(0x0; 0x7fffffffff)) R2_w=inv274877906944 R3_w=inv137438953472 R4_w=inv1024 R5_w=inv512 R10=fp0
        15: R0=inv1 R1=inv(id=0,umin_value=137438953472,umax_value=274877906944,var_off=(0x0; 0x7fffffffff)) R2=inv274877906944 R3=inv137438953472 R4=inv1024 R5=inv512 R10=fp0
        15: (2e) if w1 > w4 goto pc+2
         R0=inv1 R1=inv(id=0,umin_value=137438953472,umax_value=274877906944,var_off=(0x0; 0x7f00000000)) R2=inv274877906944 R3=inv137438953472 R4=inv1024 R5=inv512 R10=fp0
        16: R0=inv1 R1=inv(id=0,umin_value=137438953472,umax_value=274877906944,var_off=(0x0; 0x7f00000000)) R2=inv274877906944 R3=inv137438953472 R4=inv1024 R5=inv512 R10=fp0
        16: (ae) if w1 < w5 goto pc+1
         R0=inv1 R1=inv(id=0,umin_value=137438953472,umax_value=274877906944,var_off=(0x0; 0x7f00000000)) R2=inv274877906944 R3=inv137438953472 R4=inv1024 R5=inv512 R10=fp0
        [...]
      
      We're first probing lower/upper bounds via jmp64, later we do a similar
      check via jmp32 and examine the resulting var_off there. After fall-through
      in insn 14, we get the following bounded r1 with 0x7fffffffff unknown marked
      bits in the variable section.
      
      Thus, after knowing r1 <= 0x4000000000 and r1 >= 0x2000000000:
      
        max: 0b100000000000000000000000000000000000000 / 0x4000000000
        var: 0b111111111111111111111111111111111111111 / 0x7fffffffff
        min: 0b010000000000000000000000000000000000000 / 0x2000000000
      
      Now, in insn 15 and 16, we perform a similar probe with lower/upper bounds
      in jmp32.
      
      Thus, after knowing r1 <= 0x4000000000 and r1 >= 0x2000000000 and
                          w1 <= 0x400        and w1 >= 0x200:
      
        max: 0b100000000000000000000000000000000000000 / 0x4000000000
        var: 0b111111100000000000000000000000000000000 / 0x7f00000000
        min: 0b010000000000000000000000000000000000000 / 0x2000000000
      
      The lower/upper bounds haven't changed since they have high bits set in
      u64 space and the jmp32 tests can only refine bounds in the low bits.
      
      However, for the var part the expectation would have been 0x7f000007ff
      or something less precise up to 0x7fffffffff. A outcome of 0x7f00000000
      is not correct since it would contradict the earlier probed bounds
      where we know that the result should have been in [0x200,0x400] in u32
      space. Therefore, tests with such info will lead to wrong verifier
      assumptions later on like falsely predicting conditional jumps to be
      always taken, etc.
      
      The issue here is that __reg_bound_offset32()'s implementation from
      commit 581738a6 ("bpf: Provide better register bounds after jmp32
      instructions") makes an incorrect range assumption:
      
        static void __reg_bound_offset32(struct bpf_reg_state *reg)
        {
              u64 mask = 0xffffFFFF;
              struct tnum range = tnum_range(reg->umin_value & mask,
                                             reg->umax_value & mask);
              struct tnum lo32 = tnum_cast(reg->var_off, 4);
              struct tnum hi32 = tnum_lshift(tnum_rshift(reg->var_off, 32), 32);
      
              reg->var_off = tnum_or(hi32, tnum_intersect(lo32, range));
        }
      
      In the above walk-through example, __reg_bound_offset32() as-is chose
      a range after masking with 0xffffffff of [0x0,0x0] since umin:0x2000000000
      and umax:0x4000000000 and therefore the lo32 part was clamped to 0x0 as
      well. However, in the umin:0x2000000000 and umax:0x4000000000 range above
      we'd end up with an actual possible interval of [0x0,0xffffffff] for u32
      space instead.
      
      In case of the original reproducer, the situation looked as follows at
      insn 5 for r0:
      
        [...]
        5: R0_w=invP(id=0,umin_value=808464432,umax_value=5103431727,var_off=(0x0; 0x1ffffffff)) R1_w=invP808464432 R10=fp0
                                     0x30303030           0x13030302f
        5: (de) if w1 s<= w0 goto pc+0
         R0_w=invP(id=0,umin_value=808464432,umax_value=5103431727,var_off=(0x30303020; 0x10000001f)) R1_w=invP808464432 R10=fp0
                                   0x30303030           0x13030302f
        [...]
      
      After the fall-through, we similarly forced the var_off result into
      the wrong range [0x30303030,0x3030302f] suggesting later on that fixed
      bits must only be of 0x30303020 with 0x10000001f unknowns whereas such
      assumption can only be made when both bounds in hi32 range match.
      
      Originally, I was thinking to fix this by moving reg into a temp reg and
      use proper coerce_reg_to_size() helper on the temp reg where we can then
      based on that define the range tnum for later intersection:
      
        static void __reg_bound_offset32(struct bpf_reg_state *reg)
        {
              struct bpf_reg_state tmp = *reg;
              struct tnum lo32, hi32, range;
      
              coerce_reg_to_size(&tmp, 4);
              range = tnum_range(tmp.umin_value, tmp.umax_value);
              lo32 = tnum_cast(reg->var_off, 4);
              hi32 = tnum_lshift(tnum_rshift(reg->var_off, 32), 32);
              reg->var_off = tnum_or(hi32, tnum_intersect(lo32, range));
        }
      
      In the case of the concrete example, this gives us a more conservative unknown
      section. Thus, after knowing r1 <= 0x4000000000 and r1 >= 0x2000000000 and
                                   w1 <= 0x400        and w1 >= 0x200:
      
        max: 0b100000000000000000000000000000000000000 / 0x4000000000
        var: 0b111111111111111111111111111111111111111 / 0x7fffffffff
        min: 0b010000000000000000000000000000000000000 / 0x2000000000
      
      However, above new __reg_bound_offset32() has no effect on refining the
      knowledge of the register contents. Meaning, if the bounds in hi32 range
      mismatch we'll get the identity function given the range reg spans
      [0x0,0xffffffff] and we cast var_off into lo32 only to later on binary
      or it again with the hi32.
      
      Likewise, if the bounds in hi32 range match, then we mask both bounds
      with 0xffffffff, use the resulting umin/umax for the range to later
      intersect the lo32 with it. However, _prior_ called __reg_bound_offset()
      did already such intersection on the full reg and we therefore would only
      repeat the same operation on the lo32 part twice.
      
      Given this has no effect and the original commit had false assumptions,
      this patch reverts the code entirely which is also more straight forward
      for stable trees: apparently 581738a6 got auto-selected by Sasha's
      ML system and misclassified as a fix, so it got sucked into v5.4 where
      it should never have landed. A revert is low-risk also from a user PoV
      since it requires a recent kernel and llc to opt-into -mcpu=v3 BPF CPU
      to generate jmp32 instructions. A proper bounds refinement would need a
      significantly more complex approach which is currently being worked, but
      no stable material [0]. Hence revert is best option for stable. After the
      revert, the original reported program gets rejected as follows:
      
        1: (7f) r0 >>= r0
        2: (14) w0 -= 808464432
        3: (07) r0 += 808464432
        4: (b7) r1 = 808464432
        5: (de) if w1 s<= w0 goto pc+0
         R0_w=invP(id=0,umin_value=808464432,umax_value=5103431727,var_off=(0x0; 0x1ffffffff)) R1_w=invP808464432 R10=fp0
        6: (07) r0 += -2144337872
        7: (14) w0 -= -1607454672
        8: (25) if r0 > 0x30303030 goto pc+0
         R0_w=invP(id=0,umax_value=808464432,var_off=(0x0; 0x3fffffff)) R1_w=invP808464432 R10=fp0
        9: (76) if w0 s>= 0x303030 goto pc+2
         R0=invP(id=0,umax_value=3158063,var_off=(0x0; 0x3fffff)) R1=invP808464432 R10=fp0
        10: (30) r0 = *(u8 *)skb[808464432]
        BPF_LD_[ABS|IND] uses reserved fields
        processed 11 insns (limit 1000000) [...]
      
        [0] https://lore.kernel.org/bpf/158507130343.15666.8018068546764556975.stgit@john-Precision-5820-Tower/T/
      
      Fixes: 581738a6 ("bpf: Provide better register bounds after jmp32 instructions")
      Reported-by: default avatarAnatoly Trosinenko <anatoly.trosinenko@gmail.com>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20200330160324.15259-2-daniel@iogearbox.net
      f2d67fec
  3. 29 Mar, 2020 12 commits
  4. 28 Mar, 2020 7 commits