1. 26 Apr, 2022 14 commits
    • Kumar Kartikeya Dwivedi's avatar
      selftests/bpf: Add test for strict BTF type check · 792c0a34
      Kumar Kartikeya Dwivedi authored
      Ensure that the edge case where first member type was matched
      successfully even if it didn't match BTF type of register is caught and
      rejected by the verifier.
      Signed-off-by: default avatarKumar Kartikeya Dwivedi <memxor@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20220424214901.2743946-14-memxor@gmail.com
      792c0a34
    • Kumar Kartikeya Dwivedi's avatar
      selftests/bpf: Add verifier tests for kptr · 05a945de
      Kumar Kartikeya Dwivedi authored
      Reuse bpf_prog_test functions to test the support for PTR_TO_BTF_ID in
      BPF map case, including some tests that verify implementation sanity and
      corner cases.
      Signed-off-by: default avatarKumar Kartikeya Dwivedi <memxor@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20220424214901.2743946-13-memxor@gmail.com
      05a945de
    • Kumar Kartikeya Dwivedi's avatar
      selftests/bpf: Add C tests for kptr · 2cbc469a
      Kumar Kartikeya Dwivedi authored
      This uses the __kptr and __kptr_ref macros as well, and tries to test
      the stuff that is supposed to work, since we have negative tests in
      test_verifier suite. Also include some code to test map-in-map support,
      such that the inner_map_meta matches the kptr_off_tab of map added as
      element.
      Signed-off-by: default avatarKumar Kartikeya Dwivedi <memxor@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20220424214901.2743946-12-memxor@gmail.com
      2cbc469a
    • Kumar Kartikeya Dwivedi's avatar
      libbpf: Add kptr type tag macros to bpf_helpers.h · ef89654f
      Kumar Kartikeya Dwivedi authored
      Include convenience definitions:
      __kptr:	Unreferenced kptr
      __kptr_ref: Referenced kptr
      
      Users can use them to tag the pointer type meant to be used with the new
      support directly in the map value definition.
      Signed-off-by: default avatarKumar Kartikeya Dwivedi <memxor@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20220424214901.2743946-11-memxor@gmail.com
      ef89654f
    • Kumar Kartikeya Dwivedi's avatar
      bpf: Make BTF type match stricter for release arguments · 2ab3b380
      Kumar Kartikeya Dwivedi authored
      The current of behavior of btf_struct_ids_match for release arguments is
      that when type match fails, it retries with first member type again
      (recursively). Since the offset is already 0, this is akin to just
      casting the pointer in normal C, since if type matches it was just
      embedded inside parent sturct as an object. However, we want to reject
      cases for release function type matching, be it kfunc or BPF helpers.
      
      An example is the following:
      
      struct foo {
      	struct bar b;
      };
      
      struct foo *v = acq_foo();
      rel_bar(&v->b); // btf_struct_ids_match fails btf_types_are_same, then
      		// retries with first member type and succeeds, while
      		// it should fail.
      
      Hence, don't walk the struct and only rely on btf_types_are_same for
      strict mode. All users of strict mode must be dealing with zero offset
      anyway, since otherwise they would want the struct to be walked.
      Signed-off-by: default avatarKumar Kartikeya Dwivedi <memxor@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20220424214901.2743946-10-memxor@gmail.com
      2ab3b380
    • Kumar Kartikeya Dwivedi's avatar
      bpf: Teach verifier about kptr_get kfunc helpers · a1ef1959
      Kumar Kartikeya Dwivedi authored
      We introduce a new style of kfunc helpers, namely *_kptr_get, where they
      take pointer to the map value which points to a referenced kernel
      pointer contained in the map. Since this is referenced, only
      bpf_kptr_xchg from BPF side and xchg from kernel side is allowed to
      change the current value, and each pointer that resides in that location
      would be referenced, and RCU protected (this must be kept in mind while
      adding kernel types embeddable as reference kptr in BPF maps).
      
      This means that if do the load of the pointer value in an RCU read
      section, and find a live pointer, then as long as we hold RCU read lock,
      it won't be freed by a parallel xchg + release operation. This allows us
      to implement a safe refcount increment scheme. Hence, enforce that first
      argument of all such kfunc is a proper PTR_TO_MAP_VALUE pointing at the
      right offset to referenced pointer.
      
      For the rest of the arguments, they are subjected to typical kfunc
      argument checks, hence allowing some flexibility in passing more intent
      into how the reference should be taken.
      
      For instance, in case of struct nf_conn, it is not freed until RCU grace
      period ends, but can still be reused for another tuple once refcount has
      dropped to zero. Hence, a bpf_ct_kptr_get helper not only needs to call
      refcount_inc_not_zero, but also do a tuple match after incrementing the
      reference, and when it fails to match it, put the reference again and
      return NULL.
      
      This can be implemented easily if we allow passing additional parameters
      to the bpf_ct_kptr_get kfunc, like a struct bpf_sock_tuple * and a
      tuple__sz pair.
      Signed-off-by: default avatarKumar Kartikeya Dwivedi <memxor@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20220424214901.2743946-9-memxor@gmail.com
      a1ef1959
    • Kumar Kartikeya Dwivedi's avatar
      bpf: Wire up freeing of referenced kptr · 14a324f6
      Kumar Kartikeya Dwivedi authored
      A destructor kfunc can be defined as void func(type *), where type may
      be void or any other pointer type as per convenience.
      
      In this patch, we ensure that the type is sane and capture the function
      pointer into off_desc of ptr_off_tab for the specific pointer offset,
      with the invariant that the dtor pointer is always set when 'kptr_ref'
      tag is applied to the pointer's pointee type, which is indicated by the
      flag BPF_MAP_VALUE_OFF_F_REF.
      
      Note that only BTF IDs whose destructor kfunc is registered, thus become
      the allowed BTF IDs for embedding as referenced kptr. Hence it serves
      the purpose of finding dtor kfunc BTF ID, as well acting as a check
      against the whitelist of allowed BTF IDs for this purpose.
      
      Finally, wire up the actual freeing of the referenced pointer if any at
      all available offsets, so that no references are leaked after the BPF
      map goes away and the BPF program previously moved the ownership a
      referenced pointer into it.
      
      The behavior is similar to BPF timers, where bpf_map_{update,delete}_elem
      will free any existing referenced kptr. The same case is with LRU map's
      bpf_lru_push_free/htab_lru_push_free functions, which are extended to
      reset unreferenced and free referenced kptr.
      
      Note that unlike BPF timers, kptr is not reset or freed when map uref
      drops to zero.
      Signed-off-by: default avatarKumar Kartikeya Dwivedi <memxor@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20220424214901.2743946-8-memxor@gmail.com
      14a324f6
    • Kumar Kartikeya Dwivedi's avatar
      bpf: Populate pairs of btf_id and destructor kfunc in btf · 5ce937d6
      Kumar Kartikeya Dwivedi authored
      To support storing referenced PTR_TO_BTF_ID in maps, we require
      associating a specific BTF ID with a 'destructor' kfunc. This is because
      we need to release a live referenced pointer at a certain offset in map
      value from the map destruction path, otherwise we end up leaking
      resources.
      
      Hence, introduce support for passing an array of btf_id, kfunc_btf_id
      pairs that denote a BTF ID and its associated release function. Then,
      add an accessor 'btf_find_dtor_kfunc' which can be used to look up the
      destructor kfunc of a certain BTF ID. If found, we can use it to free
      the object from the map free path.
      
      The registration of these pairs also serve as a whitelist of structures
      which are allowed as referenced PTR_TO_BTF_ID in a BPF map, because
      without finding the destructor kfunc, we will bail and return an error.
      Signed-off-by: default avatarKumar Kartikeya Dwivedi <memxor@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20220424214901.2743946-7-memxor@gmail.com
      5ce937d6
    • Kumar Kartikeya Dwivedi's avatar
      bpf: Adapt copy_map_value for multiple offset case · 4d7d7f69
      Kumar Kartikeya Dwivedi authored
      Since now there might be at most 10 offsets that need handling in
      copy_map_value, the manual shuffling and special case is no longer going
      to work. Hence, let's generalise the copy_map_value function by using
      a sorted array of offsets to skip regions that must be avoided while
      copying into and out of a map value.
      
      When the map is created, we populate the offset array in struct map,
      Then, copy_map_value uses this sorted offset array is used to memcpy
      while skipping timer, spin lock, and kptr. The array is allocated as
      in most cases none of these special fields would be present in map
      value, hence we can save on space for the common case by not embedding
      the entire object inside bpf_map struct.
      Signed-off-by: default avatarKumar Kartikeya Dwivedi <memxor@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20220424214901.2743946-6-memxor@gmail.com
      4d7d7f69
    • Kumar Kartikeya Dwivedi's avatar
      bpf: Prevent escaping of kptr loaded from maps · 6efe152d
      Kumar Kartikeya Dwivedi authored
      While we can guarantee that even for unreferenced kptr, the object
      pointer points to being freed etc. can be handled by the verifier's
      exception handling (normal load patching to PROBE_MEM loads), we still
      cannot allow the user to pass these pointers to BPF helpers and kfunc,
      because the same exception handling won't be done for accesses inside
      the kernel. The same is true if a referenced pointer is loaded using
      normal load instruction. Since the reference is not guaranteed to be
      held while the pointer is used, it must be marked as untrusted.
      
      Hence introduce a new type flag, PTR_UNTRUSTED, which is used to mark
      all registers loading unreferenced and referenced kptr from BPF maps,
      and ensure they can never escape the BPF program and into the kernel by
      way of calling stable/unstable helpers.
      
      In check_ptr_to_btf_access, the !type_may_be_null check to reject type
      flags is still correct, as apart from PTR_MAYBE_NULL, only MEM_USER,
      MEM_PERCPU, and PTR_UNTRUSTED may be set for PTR_TO_BTF_ID. The first
      two are checked inside the function and rejected using a proper error
      message, but we still want to allow dereference of untrusted case.
      
      Also, we make sure to inherit PTR_UNTRUSTED when chain of pointers are
      walked, so that this flag is never dropped once it has been set on a
      PTR_TO_BTF_ID (i.e. trusted to untrusted transition can only be in one
      direction).
      
      In convert_ctx_accesses, extend the switch case to consider untrusted
      PTR_TO_BTF_ID in addition to normal PTR_TO_BTF_ID for PROBE_MEM
      conversion for BPF_LDX.
      Signed-off-by: default avatarKumar Kartikeya Dwivedi <memxor@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20220424214901.2743946-5-memxor@gmail.com
      6efe152d
    • Kumar Kartikeya Dwivedi's avatar
      bpf: Allow storing referenced kptr in map · c0a5a21c
      Kumar Kartikeya Dwivedi authored
      Extending the code in previous commits, introduce referenced kptr
      support, which needs to be tagged using 'kptr_ref' tag instead. Unlike
      unreferenced kptr, referenced kptr have a lot more restrictions. In
      addition to the type matching, only a newly introduced bpf_kptr_xchg
      helper is allowed to modify the map value at that offset. This transfers
      the referenced pointer being stored into the map, releasing the
      references state for the program, and returning the old value and
      creating new reference state for the returned pointer.
      
      Similar to unreferenced pointer case, return value for this case will
      also be PTR_TO_BTF_ID_OR_NULL. The reference for the returned pointer
      must either be eventually released by calling the corresponding release
      function, otherwise it must be transferred into another map.
      
      It is also allowed to call bpf_kptr_xchg with a NULL pointer, to clear
      the value, and obtain the old value if any.
      
      BPF_LDX, BPF_STX, and BPF_ST cannot access referenced kptr. A future
      commit will permit using BPF_LDX for such pointers, but attempt at
      making it safe, since the lifetime of object won't be guaranteed.
      
      There are valid reasons to enforce the restriction of permitting only
      bpf_kptr_xchg to operate on referenced kptr. The pointer value must be
      consistent in face of concurrent modification, and any prior values
      contained in the map must also be released before a new one is moved
      into the map. To ensure proper transfer of this ownership, bpf_kptr_xchg
      returns the old value, which the verifier would require the user to
      either free or move into another map, and releases the reference held
      for the pointer being moved in.
      
      In the future, direct BPF_XCHG instruction may also be permitted to work
      like bpf_kptr_xchg helper.
      
      Note that process_kptr_func doesn't have to call
      check_helper_mem_access, since we already disallow rdonly/wronly flags
      for map, which is what check_map_access_type checks, and we already
      ensure the PTR_TO_MAP_VALUE refers to kptr by obtaining its off_desc,
      so check_map_access is also not required.
      Signed-off-by: default avatarKumar Kartikeya Dwivedi <memxor@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20220424214901.2743946-4-memxor@gmail.com
      c0a5a21c
    • Kumar Kartikeya Dwivedi's avatar
      bpf: Tag argument to be released in bpf_func_proto · 8f14852e
      Kumar Kartikeya Dwivedi authored
      Add a new type flag for bpf_arg_type that when set tells verifier that
      for a release function, that argument's register will be the one for
      which meta.ref_obj_id will be set, and which will then be released
      using release_reference. To capture the regno, introduce a new field
      release_regno in bpf_call_arg_meta.
      
      This would be required in the next patch, where we may either pass NULL
      or a refcounted pointer as an argument to the release function
      bpf_kptr_xchg. Just releasing only when meta.ref_obj_id is set is not
      enough, as there is a case where the type of argument needed matches,
      but the ref_obj_id is set to 0. Hence, we must enforce that whenever
      meta.ref_obj_id is zero, the register that is to be released can only
      be NULL for a release function.
      
      Since we now indicate whether an argument is to be released in
      bpf_func_proto itself, is_release_function helper has lost its utitlity,
      hence refactor code to work without it, and just rely on
      meta.release_regno to know when to release state for a ref_obj_id.
      Still, the restriction of one release argument and only one ref_obj_id
      passed to BPF helper or kfunc remains. This may be lifted in the future.
      Signed-off-by: default avatarKumar Kartikeya Dwivedi <memxor@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20220424214901.2743946-3-memxor@gmail.com
      8f14852e
    • Kumar Kartikeya Dwivedi's avatar
      bpf: Allow storing unreferenced kptr in map · 61df10c7
      Kumar Kartikeya Dwivedi authored
      This commit introduces a new pointer type 'kptr' which can be embedded
      in a map value to hold a PTR_TO_BTF_ID stored by a BPF program during
      its invocation. When storing such a kptr, BPF program's PTR_TO_BTF_ID
      register must have the same type as in the map value's BTF, and loading
      a kptr marks the destination register as PTR_TO_BTF_ID with the correct
      kernel BTF and BTF ID.
      
      Such kptr are unreferenced, i.e. by the time another invocation of the
      BPF program loads this pointer, the object which the pointer points to
      may not longer exist. Since PTR_TO_BTF_ID loads (using BPF_LDX) are
      patched to PROBE_MEM loads by the verifier, it would safe to allow user
      to still access such invalid pointer, but passing such pointers into
      BPF helpers and kfuncs should not be permitted. A future patch in this
      series will close this gap.
      
      The flexibility offered by allowing programs to dereference such invalid
      pointers while being safe at runtime frees the verifier from doing
      complex lifetime tracking. As long as the user may ensure that the
      object remains valid, it can ensure data read by it from the kernel
      object is valid.
      
      The user indicates that a certain pointer must be treated as kptr
      capable of accepting stores of PTR_TO_BTF_ID of a certain type, by using
      a BTF type tag 'kptr' on the pointed to type of the pointer. Then, this
      information is recorded in the object BTF which will be passed into the
      kernel by way of map's BTF information. The name and kind from the map
      value BTF is used to look up the in-kernel type, and the actual BTF and
      BTF ID is recorded in the map struct in a new kptr_off_tab member. For
      now, only storing pointers to structs is permitted.
      
      An example of this specification is shown below:
      
      	#define __kptr __attribute__((btf_type_tag("kptr")))
      
      	struct map_value {
      		...
      		struct task_struct __kptr *task;
      		...
      	};
      
      Then, in a BPF program, user may store PTR_TO_BTF_ID with the type
      task_struct into the map, and then load it later.
      
      Note that the destination register is marked PTR_TO_BTF_ID_OR_NULL, as
      the verifier cannot know whether the value is NULL or not statically, it
      must treat all potential loads at that map value offset as loading a
      possibly NULL pointer.
      
      Only BPF_LDX, BPF_STX, and BPF_ST (with insn->imm = 0 to denote NULL)
      are allowed instructions that can access such a pointer. On BPF_LDX, the
      destination register is updated to be a PTR_TO_BTF_ID, and on BPF_STX,
      it is checked whether the source register type is a PTR_TO_BTF_ID with
      same BTF type as specified in the map BTF. The access size must always
      be BPF_DW.
      
      For the map in map support, the kptr_off_tab for outer map is copied
      from the inner map's kptr_off_tab. It was chosen to do a deep copy
      instead of introducing a refcount to kptr_off_tab, because the copy only
      needs to be done when paramterizing using inner_map_fd in the map in map
      case, hence would be unnecessary for all other users.
      
      It is not permitted to use MAP_FREEZE command and mmap for BPF map
      having kptrs, similar to the bpf_timer case. A kptr also requires that
      BPF program has both read and write access to the map (hence both
      BPF_F_RDONLY_PROG and BPF_F_WRONLY_PROG are disallowed).
      
      Note that check_map_access must be called from both
      check_helper_mem_access and for the BPF instructions, hence the kptr
      check must distinguish between ACCESS_DIRECT and ACCESS_HELPER, and
      reject ACCESS_HELPER cases. We rename stack_access_src to bpf_access_src
      and reuse it for this purpose.
      Signed-off-by: default avatarKumar Kartikeya Dwivedi <memxor@gmail.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20220424214901.2743946-2-memxor@gmail.com
      61df10c7
    • Stanislav Fomichev's avatar
      bpf: Use bpf_prog_run_array_cg_flags everywhere · d9d31cf8
      Stanislav Fomichev authored
      Rename bpf_prog_run_array_cg_flags to bpf_prog_run_array_cg and
      use it everywhere. check_return_code already enforces sane
      return ranges for all cgroup types. (only egress and bind hooks have
      uncanonical return ranges, the rest is using [0, 1])
      
      No functional changes.
      
      v2:
      - 'func_ret & 1' under explicit test (Andrii & Martin)
      Suggested-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Signed-off-by: default avatarStanislav Fomichev <sdf@google.com>
      Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
      Link: https://lore.kernel.org/bpf/20220425220448.3669032-1-sdf@google.com
      d9d31cf8
  2. 25 Apr, 2022 3 commits
  3. 22 Apr, 2022 4 commits
  4. 21 Apr, 2022 11 commits
  5. 20 Apr, 2022 8 commits