All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH bpf-next v4 00/13] Introduce typed pointer support in BPF maps
@ 2022-04-09  9:32 Kumar Kartikeya Dwivedi
  2022-04-09  9:32 ` [PATCH bpf-next v4 01/13] bpf: Make btf_find_field more generic Kumar Kartikeya Dwivedi
                   ` (12 more replies)
  0 siblings, 13 replies; 30+ messages in thread
From: Kumar Kartikeya Dwivedi @ 2022-04-09  9:32 UTC (permalink / raw)
  To: bpf
  Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
	Toke Høiland-Jørgensen, Jesper Dangaard Brouer

This set enables storing pointers of a certain type in BPF map, and extends the
verifier to enforce type safety and lifetime correctness properties.

The infrastructure being added is generic enough for allowing storing any kind
of pointers whose type is available using BTF (user or kernel) in the future
(e.g. strongly typed memory allocation in BPF program), which are internally
tracked in the verifier as PTR_TO_BTF_ID, but for now the series limits them to
two kinds of pointers obtained from the kernel.

Obviously, use of this feature depends on map BTF.

1. Unreferenced kernel pointer

In this case, there are very few restrictions. The pointer type being stored
must match the type declared in the map value. However, such a pointer when
loaded from the map can only be dereferenced, but not passed to any in-kernel
helpers or kernel functions available to the program. This is because while the
verifier's exception handling mechanism coverts BPF_LDX to PROBE_MEM loads,
which are then handled specially by the JIT implementation, the same liberty is
not available to accesses inside the kernel. The pointer by the time it is
passed into a helper has no lifetime related guarantees about the object it is
pointing to, and may well be referencing invalid memory.

2. Referenced kernel pointer

This case imposes a lot of restrictions on the programmer, to ensure safety. To
transfer the ownership of a reference in the BPF program to the map, the user
must use the bpf_kptr_xchg helper, which returns the old pointer contained in
the map, as an acquired reference, and releases verifier state for the
referenced pointer being exchanged, as it moves into the map.

This a normal PTR_TO_BTF_ID that can be used with in-kernel helpers and kernel
functions callable by the program.

However, if BPF_LDX is used to load a referenced pointer from the map, it is
still not permitted to pass it to in-kernel helpers or kernel functions. To
obtain a reference usable with helpers, the user must invoke a kfunc helper
which returns a usable reference (which also must be eventually released before
BPF_EXIT, or moved into a map).

Since the load of the pointer (preserving data dependency ordering) must happen
inside the RCU read section, the kfunc helper will take a pointer to the map
value, which must point to the actual pointer of the object whose reference is
to be raised. The type will be verified from the BTF information of the kfunc,
as the prototype must be:

	T *func(T **, ... /* other arguments */);

Then, the verifier checks whether pointer at offset of the map value points to
the type T, and permits the call.

This convention is followed so that such helpers may also be called from
sleepable BPF programs, where RCU read lock is not necessarily held in the BPF
program context, hence necessiating the need to pass in a pointer to the actual
pointer to perform the load inside the RCU read section.

Notes
-----

 * C selftests require https://reviews.llvm.org/D119799 to pass.
 * Unlike BPF timers, kptr is not reset or freed on map_release_uref.
 * Referenced kptr storage is always treated as unsigned long * on kernel side,
   as BPF side cannot mutate it. The storage (8 bytes) is sufficient for both
   32-bit and 64-bit platforms.
 * Use of WRITE_ONCE to reset unreferenced kptr on 32-bit systems is fine, as
   the actual pointer is always word sized, so the store tearing into two 32-bit
   stores won't be a problem as the other half is always zeroed out.

Changelog:
----------
v3 -> v4
v3: https://lore.kernel.org/bpf/20220320155510.671497-1-memxor@gmail.com

 * Use btf_parse_kptrs, plural kptrs naming (Joanne, Andrii)
 * Remove unused parameters in check_map_kptr_access (Joanne)
 * Handle idx < info_cnt kludge using tmp variable (Andrii)
 * Validate tags always precede modifiers in BTF (Andrii)
   * Split out into https://lore.kernel.org/bpf/20220406004121.282699-1-memxor@gmail.com
 * Store u32 type_id in btf_field_info (Andrii)
 * Use base_type in map_kptr_match_type (Andrii)
 * Free	kptr_off_tab when not bpf_capable (Martin)
 * Use PTR_RELEASE flag instead of bools in bpf_func_proto (Joanne)
 * Drop extra reg->off and reg->ref_obj_id checks in map_kptr_match_type (Martin)
 * Use separate u32 and u8 arrays for offs and sizes in off_arr (Andrii)
 * Simplify and remove map->value_size sentinel in copy_map_value (Andrii)
 * Use sort_r to keep both arrays in sync while sorting (Andrii)
 * Rename check_and_free_timers_and_kptr to check_and_free_fields (Andrii)
 * Move dtor prototype checks to registration phase (Alexei)
 * Use ret variable for checking ASSERT_XXX, use shorter strings (Andrii)
 * Fix missing checks for other maps (Jiri)
 * Fix various other nits, and bugs noticed during self review

v2 -> v3
v2: https://lore.kernel.org/bpf/20220317115957.3193097-1-memxor@gmail.com

 * Address comments from Alexei
   * Set name, sz, align in btf_find_field
   * Do idx >= info_cnt check in caller of btf_find_field_*
     * Use extra element in the info_arr to make this safe
   * Remove while loop, reject extra tags
   * Remove cases of defensive programming
   * Move bpf_capable() check to map_check_btf
   * Put check_ptr_off_reg reordering hunk into separate patch
   * Warn for ref_ptr once
   * Make the meta.ref_obj_id == 0 case simpler to read
   * Remove kptr_percpu and kptr_user support, remove their tests
   * Store size of field at offset in off_arr
 * Fix BPF_F_NO_PREALLOC set wrongly for hash map in C selftest
 * Add missing check_mem_reg call for kptr_get kfunc arg#0 check

v1 -> v2
v1: https://lore.kernel.org/bpf/20220220134813.3411982-1-memxor@gmail.com

 * Address comments from Alexei
   * Rename bpf_btf_find_by_name_kind_all to bpf_find_btf_id
   * Reduce indentation level in that function
   * Always take reference regardless of module or vmlinux BTF
   * Also made it the same for btf_get_module_btf
   * Use kptr, kptr_ref, kptr_percpu, kptr_user type tags
   * Don't reserve tag namespace
   * Refactor btf_find_field to be side effect free, allocate and populate
     kptr_off_tab in caller
   * Move module reference to dtor patch
   * Remove support for BPF_XCHG, BPF_CMPXCHG insn
   * Introduce bpf_kptr_xchg helper
   * Embed offset array in struct bpf_map, populate and sort it once
   * Adjust copy_map_value to memcpy directly using this offset array
   * Removed size member from offset array to save space
 * Fix some problems pointed out by kernel test robot
 * Tidy selftests
 * Lots of other minor fixes

Kumar Kartikeya Dwivedi (13):
  bpf: Make btf_find_field more generic
  bpf: Move check_ptr_off_reg before check_map_access
  bpf: Allow storing unreferenced kptr in map
  bpf: Tag argument to be released in bpf_func_proto
  bpf: Allow storing referenced kptr in map
  bpf: Prevent escaping of kptr loaded from maps
  bpf: Adapt copy_map_value for multiple offset case
  bpf: Populate pairs of btf_id and destructor kfunc in btf
  bpf: Wire up freeing of referenced kptr
  bpf: Teach verifier about kptr_get kfunc helpers
  libbpf: Add kptr type tag macros to bpf_helpers.h
  selftests/bpf: Add C tests for kptr
  selftests/bpf: Add verifier tests for kptr

 include/linux/bpf.h                           | 107 +++-
 include/linux/btf.h                           |  23 +
 include/uapi/linux/bpf.h                      |  12 +
 kernel/bpf/arraymap.c                         |  14 +-
 kernel/bpf/btf.c                              | 520 ++++++++++++++++--
 kernel/bpf/hashtab.c                          |  58 +-
 kernel/bpf/helpers.c                          |  21 +
 kernel/bpf/map_in_map.c                       |   5 +-
 kernel/bpf/ringbuf.c                          |   4 +-
 kernel/bpf/syscall.c                          | 249 ++++++++-
 kernel/bpf/verifier.c                         | 368 +++++++++++--
 net/bpf/test_run.c                            |  45 +-
 net/core/filter.c                             |   2 +-
 tools/include/uapi/linux/bpf.h                |  12 +
 tools/lib/bpf/bpf_helpers.h                   |   2 +
 .../selftests/bpf/prog_tests/map_kptr.c       |  37 ++
 tools/testing/selftests/bpf/progs/map_kptr.c  | 190 +++++++
 tools/testing/selftests/bpf/test_verifier.c   |  55 +-
 .../testing/selftests/bpf/verifier/map_kptr.c | 446 +++++++++++++++
 19 files changed, 2014 insertions(+), 156 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/map_kptr.c
 create mode 100644 tools/testing/selftests/bpf/progs/map_kptr.c
 create mode 100644 tools/testing/selftests/bpf/verifier/map_kptr.c

-- 
2.35.1


^ permalink raw reply	[flat|nested] 30+ messages in thread
* Re: [PATCH bpf-next v4 05/13] bpf: Allow storing referenced kptr in map
@ 2022-04-09 14:00 kernel test robot
  0 siblings, 0 replies; 30+ messages in thread
From: kernel test robot @ 2022-04-09 14:00 UTC (permalink / raw)
  To: kbuild

[-- Attachment #1: Type: text/plain, Size: 6091 bytes --]

CC: kbuild-all(a)lists.01.org
BCC: lkp(a)intel.com
In-Reply-To: <20220409093303.499196-6-memxor@gmail.com>
References: <20220409093303.499196-6-memxor@gmail.com>
TO: Kumar Kartikeya Dwivedi <memxor@gmail.com>
TO: bpf(a)vger.kernel.org
CC: Alexei Starovoitov <ast@kernel.org>
CC: Andrii Nakryiko <andrii@kernel.org>
CC: Daniel Borkmann <daniel@iogearbox.net>
CC: "Toke Høiland-Jørgensen" <toke@redhat.com>
CC: Jesper Dangaard Brouer <brouer@redhat.com>

Hi Kumar,

Thank you for the patch! Perhaps something to improve:

[auto build test WARNING on bpf-next/master]

url:    https://github.com/intel-lab-lkp/linux/commits/Kumar-Kartikeya-Dwivedi/Introduce-typed-pointer-support-in-BPF-maps/20220409-173513
base:   https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
:::::: branch date: 4 hours ago
:::::: commit date: 4 hours ago
config: i386-randconfig-m021 (https://download.01.org/0day-ci/archive/20220409/202204092155.HhbdLcz8-lkp(a)intel.com/config)
compiler: gcc-11 (Debian 11.2.0-19) 11.2.0

If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <lkp@intel.com>
Reported-by: Dan Carpenter <dan.carpenter@oracle.com>

smatch warnings:
kernel/bpf/verifier.c:5317 process_kptr_func() warn: passing zero to 'PTR_ERR'

vim +/PTR_ERR +5317 kernel/bpf/verifier.c

b00628b1c7d595 Alexei Starovoitov      2021-07-14  5295  
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5296  static int process_kptr_func(struct bpf_verifier_env *env, int regno,
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5297  			     struct bpf_call_arg_meta *meta)
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5298  {
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5299  	struct bpf_reg_state *regs = cur_regs(env), *reg = &regs[regno];
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5300  	struct bpf_map_value_off_desc *off_desc;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5301  	struct bpf_map *map_ptr = reg->map_ptr;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5302  	u32 kptr_off;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5303  	int ret;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5304  
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5305  	if (!tnum_is_const(reg->var_off)) {
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5306  		verbose(env,
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5307  			"R%d doesn't have constant offset. kptr has to be at the constant offset\n",
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5308  			regno);
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5309  		return -EINVAL;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5310  	}
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5311  	if (!map_ptr->btf) {
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5312  		verbose(env, "map '%s' has to have BTF in order to use bpf_kptr_xchg\n",
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5313  			map_ptr->name);
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5314  		return -EINVAL;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5315  	}
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5316  	if (!map_value_has_kptrs(map_ptr)) {
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09 @5317  		ret = PTR_ERR(map_ptr->kptr_off_tab);
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5318  		if (ret == -E2BIG)
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5319  			verbose(env, "map '%s' has more than %d kptr\n", map_ptr->name,
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5320  				BPF_MAP_VALUE_OFF_MAX);
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5321  		else if (ret == -EEXIST)
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5322  			verbose(env, "map '%s' has repeating kptr BTF tags\n", map_ptr->name);
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5323  		else
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5324  			verbose(env, "map '%s' has no valid kptr\n", map_ptr->name);
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5325  		return -EINVAL;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5326  	}
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5327  
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5328  	meta->map_ptr = map_ptr;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5329  	/* Check access for BPF_WRITE */
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5330  	meta->raw_mode = true;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5331  	ret = check_helper_mem_access(env, regno, sizeof(u64), false, meta);
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5332  	if (ret < 0)
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5333  		return ret;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5334  
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5335  	kptr_off = reg->off + reg->var_off.value;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5336  	off_desc = bpf_map_kptr_off_contains(map_ptr, kptr_off);
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5337  	if (!off_desc) {
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5338  		verbose(env, "off=%d doesn't point to kptr\n", kptr_off);
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5339  		return -EACCES;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5340  	}
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5341  	if (!(off_desc->flags & BPF_MAP_VALUE_OFF_F_REF)) {
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5342  		verbose(env, "off=%d kptr isn't referenced kptr\n", kptr_off);
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5343  		return -EACCES;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5344  	}
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5345  	meta->kptr_off_desc = off_desc;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5346  	return 0;
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5347  }
dd8be1418d45aa Kumar Kartikeya Dwivedi 2022-04-09  5348  

-- 
0-DAY CI Kernel Test Service
https://01.org/lkp

^ permalink raw reply	[flat|nested] 30+ messages in thread

end of thread, other threads:[~2022-04-13 18:39 UTC | newest]

Thread overview: 30+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-04-09  9:32 [PATCH bpf-next v4 00/13] Introduce typed pointer support in BPF maps Kumar Kartikeya Dwivedi
2022-04-09  9:32 ` [PATCH bpf-next v4 01/13] bpf: Make btf_find_field more generic Kumar Kartikeya Dwivedi
2022-04-11 20:20   ` Joanne Koong
2022-04-12 19:48     ` Kumar Kartikeya Dwivedi
2022-04-09  9:32 ` [PATCH bpf-next v4 02/13] bpf: Move check_ptr_off_reg before check_map_access Kumar Kartikeya Dwivedi
2022-04-11 20:28   ` Joanne Koong
2022-04-09  9:32 ` [PATCH bpf-next v4 03/13] bpf: Allow storing unreferenced kptr in map Kumar Kartikeya Dwivedi
2022-04-12  0:32   ` Joanne Koong
2022-04-12 19:16     ` Kumar Kartikeya Dwivedi
2022-04-12 23:56       ` Joanne Koong
2022-04-13  5:50         ` Kumar Kartikeya Dwivedi
2022-04-13  5:41   ` kernel test robot
2022-04-09  9:32 ` [PATCH bpf-next v4 04/13] bpf: Tag argument to be released in bpf_func_proto Kumar Kartikeya Dwivedi
2022-04-12 18:16   ` Joanne Koong
2022-04-12 20:11     ` Kumar Kartikeya Dwivedi
2022-04-13 18:33       ` Joanne Koong
2022-04-13 18:39         ` Joanne Koong
2022-04-09  9:32 ` [PATCH bpf-next v4 05/13] bpf: Allow storing referenced kptr in map Kumar Kartikeya Dwivedi
2022-04-12 23:05   ` Joanne Koong
2022-04-13  5:36     ` Kumar Kartikeya Dwivedi
2022-04-13  5:54       ` Kumar Kartikeya Dwivedi
2022-04-09  9:32 ` [PATCH bpf-next v4 06/13] bpf: Prevent escaping of kptr loaded from maps Kumar Kartikeya Dwivedi
2022-04-09  9:32 ` [PATCH bpf-next v4 07/13] bpf: Adapt copy_map_value for multiple offset case Kumar Kartikeya Dwivedi
2022-04-09  9:32 ` [PATCH bpf-next v4 08/13] bpf: Populate pairs of btf_id and destructor kfunc in btf Kumar Kartikeya Dwivedi
2022-04-09  9:32 ` [PATCH bpf-next v4 09/13] bpf: Wire up freeing of referenced kptr Kumar Kartikeya Dwivedi
2022-04-09  9:33 ` [PATCH bpf-next v4 10/13] bpf: Teach verifier about kptr_get kfunc helpers Kumar Kartikeya Dwivedi
2022-04-09  9:33 ` [PATCH bpf-next v4 11/13] libbpf: Add kptr type tag macros to bpf_helpers.h Kumar Kartikeya Dwivedi
2022-04-09  9:33 ` [PATCH bpf-next v4 12/13] selftests/bpf: Add C tests for kptr Kumar Kartikeya Dwivedi
2022-04-09  9:33 ` [PATCH bpf-next v4 13/13] selftests/bpf: Add verifier " Kumar Kartikeya Dwivedi
2022-04-09 14:00 [PATCH bpf-next v4 05/13] bpf: Allow storing referenced kptr in map kernel test robot

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.