Skip to contentSkip to conversation

Local kptrs, BPF linked lists

PATCH Superseded Kumar Kartikeya Dwivedi 5 participants 59 messages Nov 3, 2022 – Nov 6, 2022

Subsystems (8)

v4 of 5 Superseded 8 of 24 applied Latest is v5 →

lore
Share & tools
lore

Kumar Kartikeya Dwivedi

author maintainer
#0 lore raw

v4 cover Local kptrs, BPF linked lists

This series introduces user defined BPF objects, by introducing the idea of local kptrs. These are kptrs (strongly typed pointers) that refer to objects of a user defined type, hence called "local" kptrs. This allows BPF programs to allocate their own objects, build their own object hierarchies, and use the basic building blocks provided by BPF runtime to build their own data structures flexibly.

Then, we introduce the support for single ownership BPF linked lists, which can be put inside BPF maps, or local kptrs, and hold such allocated local kptrs as elements. It works as an instrusive collection, which is done to allow making local kptrs part of multiple data structures at the same time in the future.

The eventual goal of this and future patches is to allow one to do some limited form of kernel style programming in BPF C, and allow programmers to build their own complex data structures flexibly out of basic building blocks.

The key difference will be that such programs are verified to be safe, preserve runtime integrity of the system, and are proven to be bug free as far as the invariants of BPF specific APIs are concerned.

One immediate use case that will be using the entire infrastructure this series is introducing will be managing percpu NMI safe linked lists inside BPF programs.

The other use case this will serve in the near future will be linking kernel structures like XDP frame and sk_buff directly into user data structures (rbtree, pifomap, etc.) for packet queueing. This will follow single ownership concept included in this series.

The user has complete control of the internal locking, and hence also the batching of operations for each critical section.

The features are:
- Local kptrs - User defined kernel objects.
- bpf_obj_new, bpf_obj_drop to allocate and free them.
- Single ownership BPF linked lists.
- Support for them in BPF maps.
- Support for them in local kptrs.
- Global spin locks.
- Spin locks inside local kptrs.

Some other notable things:
- Completely static verification of locking.
- Kfunc argument handling has been completely reworked.
- Argument rewriting support for kfuncs.
- Search pruning now understands non-size precise registers.
- A new bpf_experimental.h header as a dumping ground for these APIs.

Any functionality exposed in this series is NOT part of UAPI. It is only available through use of kfuncs, and structs that can be added to map value may also change their size or name in the future. Hence, every feature in this series must be considered experimental.

Follow-ups:
-----------
* Support for kptrs (local and kernel) in local storage and percpu maps + kptr tests
* Fixes for helper access checks rebasing on top of this series

Next steps:
-----------
* NMI safe percpu single ownership linked lists (using local_t protection).
* Lockless linked lists.
* Allow RCU protected local kptrs. This then allows RCU protected list lookups, since spinlock protection for readers does not scale.
* Introduce explicit RCU read sections (using kfuncs).
* Introduce bpf_refcount for local kptrs, shared ownership.
* Introduce shared ownership linked lists.
* Documentation.

Changelog:
----------
v3 -> v4
v3: https://lore.kernel.org/bpf/[email protected]

* Fix compiler error for !CONFIG_BPF_SYSCALL (Kernel Test Robot)
* Fix error due to BUILD_BUG_ON on 32-bit platforms (Kernel Test Robot)

v2 -> v3
v2: https://lore.kernel.org/bpf/[email protected]

* Add ack from Dave for patch 5
* Rename btf_type_fields -> btf_record, btf_type_fields_off -> btf_field_offs, rename functions similarly (Alexei)
* Remove 'kind' component from contains declaration tag (Alexei)
* Move bpf_list_head, bpf_list_node definitions to UAPI bpf.h (Alexei)
* Add note in commit log about modifying btf_struct_access API (Dave)
* Downgrade WARN_ON_ONCE to verbose(env, "...") and return -EFAULT (Dave)
* Add type_is_local_kptr wrapper to avoid noisy checks (Dave)
* Remove unused flags parameter from bpf_kptr_new (Alexei)
* Rename bpf_kptr_new -> bpf_obj_new, bpf_kptr_drop -> bpf_obj_drop (Alexei)
* Reword comment in ref_obj_id_set_release_on_unlock (Dave)
* Fix return type of ref_obj_id_set_release_on_unlock (Dave)
* Introduce is_bpf_list_api_kfunc to dedup checks (Dave)
* Disallow BPF_WRITE to untrusted local kptrs
* Add details about soundness of check_reg_allocation_locked logic
* List untrusted local kptrs for PROBE_MEM handling

v1 -> v2
v1: https://lore.kernel.org/bpf/[email protected]

* Rebase on bpf-next to resolve merge conflict in DENYLIST.s390x
* Fix a couple of mental lapses in bpf_list_head_free

RFC v1 -> v1
RFC v1: https://lore.kernel.org/bpf/[email protected]

* Mostly a complete rewrite of BTF parsing, refactor existing code (Kartikeya)
* Rebase kfunc rewrite for bpf-next, add support for more changes
* Cache type metadata in BTF to avoid recomputation inside verifier (Kartikeya)
* Remove __kernel tag, make things similar to map values, reserve bpf_ prefix
* bpf_kptr_new, bpf_kptr_drop
* Rename precision state enum values (Alexei)
* Drop explicit constructor/destructor support (Alexei)
* Rewrite code for constructing/destructing objects and offload to runtime
* Minimize duplication in bpf_map_value_off_desc handling (Alexei)
* Expose global memory allocator (Alexei)
* Address other nits from Alexei
* Split out local kptrs in maps, more kptrs in maps support into a follow up

Links:
------
* Dave's BPF RB-Tree RFC series
v1 (Discussion thread)

     https://lore.kernel.org/bpf/[email protected]
   v2 (With support for static locks)
     https://lore.kernel.org/bpf/[email protected]

* BPF Linked Lists Discussion
https://lore.kernel.org/bpf/CAP01T74U30+yeBHEgmgzTJ-XYxZ0zj71kqCDJtTH9YQNfTK+Xw@mail.gmail.com
* BPF Memory Allocator from Alexei
https://lore.kernel.org/bpf/[email protected]
* BPF Memory Allocator UAPI Discussion
https://lore.kernel.org/bpf/[email protected]

Kumar Kartikeya Dwivedi (24):
bpf: Document UAPI details for special BPF types
bpf: Allow specifying volatile type modifier for kptrs
bpf: Clobber stack slot when writing over spilled PTR_TO_BTF_ID
bpf: Fix slot type check in check_stack_write_var_off
bpf: Drop reg_type_may_be_refcounted_or_null
bpf: Refactor kptr_off_tab into btf_record
bpf: Consolidate spin_lock, timer management into btf_record
bpf: Refactor map->off_arr handling
bpf: Support bpf_list_head in map values
bpf: Introduce local kptrs
bpf: Recognize bpf_{spin_lock,list_head,list_node} in local kptrs
bpf: Verify ownership relationships for user BTF types
bpf: Support locking bpf_spin_lock in local kptr
bpf: Allow locking bpf_spin_lock global variables
bpf: Rewrite kfunc argument handling
bpf: Drop kfunc bits from btf_check_func_arg_match
bpf: Support constant scalar arguments for kfuncs
bpf: Teach verifier about non-size constant arguments
bpf: Introduce bpf_obj_new
bpf: Introduce bpf_obj_drop
bpf: Permit NULL checking pointer with non-zero fixed offset
bpf: Introduce single ownership BPF linked list API selftests/bpf: Add __contains macro to bpf_experimental.h selftests/bpf: Add BPF linked list API tests

 Documentation/bpf/bpf_design_QA.rst           |   44 +
 Documentation/bpf/kfuncs.rst                  |   30 +
 include/linux/bpf.h                           |  256 ++-
 include/linux/bpf_verifier.h                  |   22 +-
 include/linux/btf.h                           |   77 +-
 include/linux/filter.h                        |    8 +-
 include/uapi/linux/bpf.h                      |   10 +
 kernel/bpf/arraymap.c                         |   30 +-
 kernel/bpf/bpf_local_storage.c                |    2 +-
 kernel/bpf/btf.c                              | 1205 +++++++------
 kernel/bpf/core.c                             |   16 +
 kernel/bpf/hashtab.c                          |   38 +-
 kernel/bpf/helpers.c                          |  141 +-
 kernel/bpf/local_storage.c                    |    2 +-
 kernel/bpf/map_in_map.c                       |   19 +-
 kernel/bpf/syscall.c                          |  401 +++--
 kernel/bpf/verifier.c                         | 1504 ++++++++++++++---
 net/bpf/bpf_dummy_struct_ops.c                |   14 +-
 net/core/bpf_sk_storage.c                     |    4 +-
 net/core/filter.c                             |   34 +-
 net/ipv4/bpf_tcp_ca.c                         |   13 +-
 net/netfilter/nf_conntrack_bpf.c              |   17 +-
 tools/include/uapi/linux/bpf.h                |   10 +
 tools/testing/selftests/bpf/DENYLIST.s390x    |    1 +
 .../testing/selftests/bpf/bpf_experimental.h  |   63 +
 .../bpf/prog_tests/kfunc_dynptr_param.c       |    2 +-
 .../selftests/bpf/prog_tests/linked_list.c    |   79 +
 .../testing/selftests/bpf/progs/linked_list.c |  330 ++++
 tools/testing/selftests/bpf/verifier/calls.c  |    4 +-
 .../selftests/bpf/verifier/ref_tracking.c     |    4 +-
 30 files changed, 3190 insertions(+), 1190 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/bpf_experimental.h
 create mode 100644 tools/testing/selftests/bpf/prog_tests/linked_list.c
 create mode 100644 tools/testing/selftests/bpf/progs/linked_list.c

base-commit: d9095f92950bd16745b9ec24ebebc12d14b3a3e8

Signature · 1 line
2.38.1
author maintainer
#1 lore raw

PATCH v4 1/24 bpf: Document UAPI details for special BPF types

The kernel recognizes some special BPF types in map values or local kptrs. Document that only bpf_spin_lock and bpf_timer will preserve backwards compatibility, and kptr will preserve backwards compatibility for the operations on the pointer, not the types supported for such kptrs.

For local kptrs, document that there are no stability guarantees at all.

Finally, document that 'bpf_' namespace is reserved for adding future special fields, hence BPF programs must not declare types with such names in their programs and still expect backwards compatibility.

---
 Documentation/bpf/bpf_design_QA.rst | 44 +++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)
Documentation/bpf/bpf_design_QA.rst +44 -0
index a210b8a4df00..b5273148497c 100644
@@ -298,3 +298,47 @@ A: NO.
 
 The BTF_ID macro does not cause a function to become part of the ABI
 any more than does the EXPORT_SYMBOL_GPL macro.
+
+Q: What is the compatibility story for special BPF types in map values?
+-----------------------------------------------------------------------
+Q: Users are allowed to embed bpf_spin_lock, bpf_timer fields in their BPF map
+values (when using BTF support for BPF maps). This allows to use helpers for
+such objects on these fields inside map values. Users are also allowed to embed
+pointers to some kernel types (with __kptr and __kptr_ref BTF tags). Will the
+kernel preserve backwards compatibility for these features?
+
+A: It depends. For bpf_spin_lock, bpf_timer: YES, for kptr and everything else:
+NO, but see below.
+
+For struct types that have been added already, like bpf_spin_lock and bpf_timer,
+the kernel will preserve backwards compatibility, as they are part of UAPI.
+
+For kptrs, they are also part of UAPI, but only with respect to the kptr
+mechanism. The types that you can use with a __kptr and __kptr_ref tagged
+pointer in your struct is NOT part of the UAPI contract. The supported types can
+and will change across kernel releases. However, operations like accessing kptr
+fields and bpf_kptr_xchg() helper will continue to be supported across kernel
+releases for the supported types.
+
+For any other supported struct type, unless explicitly stated in this document
+and added to bpf.h UAPI header, such types can and will arbitrarily change their
+size, type, and alignment, or any other user visible API or ABI detail across
+kernel releases. The users must adapt their BPF programs to the new changes and
+update them to make sure their programs continue to work correctly.
+
+NOTE: BPF subsystem specially reserves the 'bpf_' prefix for type names, in
+order to introduce more special fields in the future. Hence, user programs must
+avoid defining types with 'bpf_' prefix to not be broken in future releases. In
+other words, no backwards compatibility is guaranteed if one using a type in BTF
+with 'bpf_' prefix.
+
+Q: What is the compatibility story for special BPF types in local kptrs?
+------------------------------------------------------------------------
+Q: Same as above, but for local kptrs (i.e. pointers to objects allocated using
+bpf_obj_new for user defined structures). Will the kernel preserve backwards
+compatibility for these features?
+
+A: NO.
+
+Unlike map value types, there are no stability guarantees for this case. The
+whole local kptr API itself is unstable (since it is exposed through kfuncs).
Signature · 1 line
2.38.1
Acked-by on v4 1/24
#2 lore raw

Re: [PATCH bpf-next v4 01/24] bpf: Document UAPI details for special BPF types

Quoted 33 lines · Kumar Kartikeya Dwivedi

The kernel recognizes some special BPF types in map values or local kptrs. Document that only bpf_spin_lock and bpf_timer will preserve backwards compatibility, and kptr will preserve backwards compatibility for the operations on the pointer, not the types supported for such kptrs.

For local kptrs, document that there are no stability guarantees at all.

Finally, document that 'bpf_' namespace is reserved for adding future special fields, hence BPF programs must not declare types with such names in their programs and still expect backwards compatibility.

---
 Documentation/bpf/bpf_design_QA.rst | 44 +++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)
Documentation/bpf/bpf_design_QA.rst +8 -0
index a210b8a4df00..b5273148497c 100644
@@ -298,3 +298,47 @@ A: NO.
 
 The BTF_ID macro does not cause a function to become part of the ABI
 any more than does the EXPORT_SYMBOL_GPL macro.
+
+Q: What is the compatibility story for special BPF types in map values?
+-----------------------------------------------------------------------
+Q: Users are allowed to embed bpf_spin_lock, bpf_timer fields in their BPF map
+values (when using BTF support for BPF maps). This allows to use helpers for
+such objects on these fields inside map values. Users are also allowed to embed
+pointers to some kernel types (with __kptr and __kptr_ref BTF tags). Will the
+kernel preserve backwards compatibility for these features?

Documentation/bpf/bpf_design_QA.rst A: NO. · line 318

Quoted 10 lines
Documentation/bpf/bpf_design_QA.rst +10 -0
+
+A: It depends. For bpf_spin_lock, bpf_timer: YES, for kptr and everything else:
+NO, but see below.
+
+For struct types that have been added already, like bpf_spin_lock and bpf_timer,
+the kernel will preserve backwards compatibility, as they are part of UAPI.
+
+For kptrs, they are also part of UAPI, but only with respect to the kptr
+mechanism. The types that you can use with a __kptr and __kptr_ref tagged
+pointer in your struct is NOT part of the UAPI contract. The supported types can

s/is NOT/are NOT

Quoted 29 lines
Documentation/bpf/bpf_design_QA.rst +26 -0
+and will change across kernel releases. However, operations like accessing kptr
+fields and bpf_kptr_xchg() helper will continue to be supported across kernel
+releases for the supported types.
+
+For any other supported struct type, unless explicitly stated in this document
+and added to bpf.h UAPI header, such types can and will arbitrarily change their
+size, type, and alignment, or any other user visible API or ABI detail across
+kernel releases. The users must adapt their BPF programs to the new changes and
+update them to make sure their programs continue to work correctly.
+
+NOTE: BPF subsystem specially reserves the 'bpf_' prefix for type names, in
+order to introduce more special fields in the future. Hence, user programs must
+avoid defining types with 'bpf_' prefix to not be broken in future releases. In
+other words, no backwards compatibility is guaranteed if one using a type in BTF
+with 'bpf_' prefix.
+
+Q: What is the compatibility story for special BPF types in local kptrs?
+------------------------------------------------------------------------
+Q: Same as above, but for local kptrs (i.e. pointers to objects allocated using
+bpf_obj_new for user defined structures). Will the kernel preserve backwards
+compatibility for these features?
+
+A: NO.
+
+Unlike map value types, there are no stability guarantees for this case. The
+whole local kptr API itself is unstable (since it is exposed through kfuncs).
Signature · 1 line
2.38.1

Looks good otherwise.

author maintainer
#3 lore raw

PATCH v4 2/24 bpf: Allow specifying volatile type modifier for kptrs

In reply to Kumar Kartikeya Dwivedi

This is useful in particular to mark the pointer as volatile, so that compiler treats each load and store to the field as a volatile access. The alternative is having to define and use READ_ONCE and WRITE_ONCE in the BPF program.

---
 include/linux/btf.h | 5 +++++
 kernel/bpf/btf.c    | 3 +++
 2 files changed, 8 insertions(+)
include/linux/btf.h +5 -0
index f9aababc5d78..86aad9b2ce02 100644
@@ -288,6 +288,11 @@ static inline bool btf_type_is_typedef(const struct btf_type *t)
 	return BTF_INFO_KIND(t->info) == BTF_KIND_TYPEDEF;
 }
 
+static inline bool btf_type_is_volatile(const struct btf_type *t)
+{
+	return BTF_INFO_KIND(t->info) == BTF_KIND_VOLATILE;
+}
+
 static inline bool btf_type_is_func(const struct btf_type *t)
 {
 	return BTF_INFO_KIND(t->info) == BTF_KIND_FUNC;
kernel/bpf/btf.c +3 -0
index 35c07afac924..f4d21eef6ebd 100644
@@ -3225,6 +3225,9 @@ static int btf_find_kptr(const struct btf *btf, const struct btf_type *t,
 	enum bpf_kptr_type type;
 	u32 res_id;
 
+	/* Permit modifiers on the pointer itself */
+	if (btf_type_is_volatile(t))
+		t = btf_type_by_id(btf, t->type);
 	/* For PTR, sz is always == 8 */
 	if (!btf_type_is_ptr(t))
 		return BTF_FIELD_IGNORE;
Signature · 1 line
2.38.1
Acked-by on v4 2/24
#4 lore raw

Re: [PATCH bpf-next v4 02/24] bpf: Allow specifying volatile type modifier for kptrs

Quoted 6 lines · Kumar Kartikeya Dwivedi

This is useful in particular to mark the pointer as volatile, so that compiler treats each load and store to the field as a volatile access. The alternative is having to define and use READ_ONCE and WRITE_ONCE in the BPF program.

author maintainer
#5 lore raw

PATCH v4 3/24 bpf: Clobber stack slot when writing over spilled PTR_TO_BTF_ID

In reply to Kumar Kartikeya Dwivedi

When support was added for spilled PTR_TO_BTF_ID to be accessed by helper memory access, the stack slot was not overwritten to STACK_MISC (and that too is only safe when env->allow_ptr_leaks is true).

This means that helpers who take ARG_PTR_TO_MEM and write to it may essentially overwrite the value while the verifier continues to track the slot for spilled register.

This can cause issues when PTR_TO_BTF_ID is spilled to stack, and then overwritten by helper write access, which can then be passed to BPF helpers or kfuncs.

Handle this by falling back to the case introduced in a later commit, which will also handle PTR_TO_BTF_ID along with other pointer types, i.e. cd17d38f8b28 ("bpf: Permits pointers on stack for helper calls").

Finally, include a comment on why REG_LIVE_WRITTEN is not being set when clobber is set to true. In short, the reason is that while when clobber is unset, we know that we won't be writing, when it is true, we *may* write to any of the stack slots in that range. It may be a partial or complete write, to just one or many stack slots.

We cannot be sure, hence to be conservative, we leave things as is and never set REG_LIVE_WRITTEN for any stack slot. However, clobber still needs to reset them to STACK_MISC assuming writes happened. However read marks still need to be propagated upwards from liveness point of view, as parent stack slot's contents may still continue to matter to child states.

Cc Yonghong Song <[email protected]>
Fixes 1d68f22b3d53 ("bpf: Handle spilled PTR_TO_BTF_ID properly when checking stack_boundary")
---
 kernel/bpf/verifier.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)
kernel/bpf/verifier.c +5 -4
index 82c07fe0bfb1..7bf12c492201 100644
@@ -5154,10 +5154,6 @@ static int check_stack_range_initialized(
 			goto mark;
 		}
 
-		if (is_spilled_reg(&state->stack[spi]) &&
-		    base_type(state->stack[spi].spilled_ptr.type) == PTR_TO_BTF_ID)
-			goto mark;
-
 		if (is_spilled_reg(&state->stack[spi]) &&
 		    (state->stack[spi].spilled_ptr.type == SCALAR_VALUE ||
 		     env->allow_ptr_leaks)) {
@@ -5188,6 +5184,11 @@ static int check_stack_range_initialized(
 		mark_reg_read(env, &state->stack[spi].spilled_ptr,
 			      state->stack[spi].spilled_ptr.parent,
 			      REG_LIVE_READ64);
+		/* We do not set REG_LIVE_WRITTEN for stack slot, as we can not
+		 * be sure that whether stack slot is written to or not. Hence,
+		 * we must still conservatively propagate reads upwards even if
+		 * helper may write to the entire memory range.
+		 */
 	}
 	return update_stack_depth(env, state, min_off);
 }
Signature · 1 line
2.38.1
author maintainer
#6 lore raw

PATCH v4 4/24 bpf: Fix slot type check in check_stack_write_var_off

In reply to Kumar Kartikeya Dwivedi

For the case where allow_ptr_leaks is false, code is checking whether slot type is STACK_INVALID and STACK_SPILL and rejecting other cases. This is a consequence of incorrectly checking for register type instead of the slot type (NOT_INIT and SCALAR_VALUE respectively). Fix the check.

Fixes 01f810ace9ed ("bpf: Allow variable-offset stack access")
---
 kernel/bpf/verifier.c | 19 +++++++++++--------
 1 file changed, 11 insertions(+), 8 deletions(-)
kernel/bpf/verifier.c +11 -8
index 7bf12c492201..eb111a8034e7 100644
@@ -3181,14 +3181,17 @@ static int check_stack_write_var_off(struct bpf_verifier_env *env,
 		stype = &state->stack[spi].slot_type[slot % BPF_REG_SIZE];
 		mark_stack_slot_scratched(env, spi);
 
-		if (!env->allow_ptr_leaks
-				&& *stype != NOT_INIT
-				&& *stype != SCALAR_VALUE) {
-			/* Reject the write if there's are spilled pointers in
-			 * range. If we didn't reject here, the ptr status
-			 * would be erased below (even though not all slots are
-			 * actually overwritten), possibly opening the door to
-			 * leaks.
+		if (!env->allow_ptr_leaks && *stype != STACK_MISC && *stype != STACK_ZERO) {
+			/* Reject the write if range we may write to has not
+			 * been initialized beforehand. If we didn't reject
+			 * here, the ptr status would be erased below (even
+			 * though not all slots are actually overwritten),
+			 * possibly opening the door to leaks.
+			 *
+			 * We do however catch STACK_INVALID case below, and
+			 * only allow reading possibly uninitialized memory
+			 * later for CAP_PERFMON, as the write may not happen to
+			 * that slot.
 			 */
 			verbose(env, "spilled ptr in range of var-offset stack write; insn %d, ptr off: %d",
 				insn_idx, i);
Signature · 1 line
2.38.1
author maintainer
#7 lore raw

PATCH v4 5/24 bpf: Drop reg_type_may_be_refcounted_or_null

In reply to Kumar Kartikeya Dwivedi

It is not scalable to maintain a list of types that can have non-zero ref_obj_id. It is never set for scalars anyway, so just remove the conditional on register types and print it whenever it is non-zero.

---
 kernel/bpf/verifier.c | 9 +--------
 1 file changed, 1 insertion(+), 8 deletions(-)
kernel/bpf/verifier.c +1 -8
index eb111a8034e7..14d350a25d5d 100644
@@ -457,13 +457,6 @@ static bool reg_may_point_to_spin_lock(const struct bpf_reg_state *reg)
 		map_value_has_spin_lock(reg->map_ptr);
 }
 
-static bool reg_type_may_be_refcounted_or_null(enum bpf_reg_type type)
-{
-	type = base_type(type);
-	return type == PTR_TO_SOCKET || type == PTR_TO_TCP_SOCK ||
-		type == PTR_TO_MEM || type == PTR_TO_BTF_ID;
-}
-
 static bool type_is_rdonly_mem(u32 type)
 {
 	return type & MEM_RDONLY;
@@ -875,7 +868,7 @@ static void print_verifier_state(struct bpf_verifier_env *env,
 
 			if (reg->id)
 				verbose_a("id=%d", reg->id);
-			if (reg_type_may_be_refcounted_or_null(t) && reg->ref_obj_id)
+			if (reg->ref_obj_id)
 				verbose_a("ref_obj_id=%d", reg->ref_obj_id);
 			if (t != SCALAR_VALUE)
 				verbose_a("off=%d", reg->off);
Signature · 1 line
2.38.1
Acked-by on v4 5/24
#8 lore raw

Re: [PATCH bpf-next v4 05/24] bpf: Drop reg_type_may_be_refcounted_or_null

Quoted 7 lines · Kumar Kartikeya Dwivedi

It is not scalable to maintain a list of types that can have non-zero ref_obj_id. It is never set for scalars anyway, so just remove the conditional on register types and print it whenever it is non-zero.

---

author maintainer
#9 lore raw

PATCH v4 6/24 bpf: Refactor kptr_off_tab into btf_record

In reply to Kumar Kartikeya Dwivedi

To prepare the BPF verifier to handle special fields in both map values and program allocated types coming from program BTF, we need to refactor the kptr_off_tab handling code into something more generic and reusable across both cases to avoid code duplication.

Later patches also require passing this data to helpers at runtime, so that they can work on user defined types, initialize them, destruct them, etc.

The main observation is that both map values and such allocated types point to a type in program BTF, hence they can be handled similarly. We can prepare a field metadata table for both cases and store them in struct bpf_map or struct btf depending on the use case.

Hence, refactor the code into generic btf_record and btf_field member structs. The btf_record represents the fields of a specific btf_type in user BTF. The cnt indicates the number of special fields we successfully recognized, and field_mask is a bitmask of fields that were found, to enable quick determination of availability of a certain field.

Subsequently, refactor the rest of the code to work with these generic types, remove assumptions about kptr and kptr_off_tab, rename variables to more meaningful names, etc.

---
 include/linux/bpf.h     | 125 ++++++++++++-------
 include/linux/btf.h     |   3 +-
 kernel/bpf/arraymap.c   |  13 +-
 kernel/bpf/btf.c        |  67 +++++-----
 kernel/bpf/hashtab.c    |  14 +--
 kernel/bpf/map_in_map.c |  14 ++-
 kernel/bpf/syscall.c    | 263 +++++++++++++++++++++++-----------------
 kernel/bpf/verifier.c   |  96 +++++++--------
 8 files changed, 332 insertions(+), 263 deletions(-)
include/linux/bpf.h +81 -44
index 8d948bfcb984..1440e7c3c510 100644
@@ -165,35 +165,41 @@ struct bpf_map_ops {
 };
 
 enum {
-	/* Support at most 8 pointers in a BPF map value */
-	BPF_MAP_VALUE_OFF_MAX = 8,
-	BPF_MAP_OFF_ARR_MAX   = BPF_MAP_VALUE_OFF_MAX +
+	/* Support at most 8 pointers in a BTF type */
+	BTF_FIELDS_MAX	      = 8,
+	BPF_MAP_OFF_ARR_MAX   = BTF_FIELDS_MAX +
 				1 + /* for bpf_spin_lock */
 				1,  /* for bpf_timer */
 };
 
-enum bpf_kptr_type {
-	BPF_KPTR_UNREF,
-	BPF_KPTR_REF,
+enum btf_field_type {
+	BPF_KPTR_UNREF = (1 << 2),
+	BPF_KPTR_REF   = (1 << 3),
+	BPF_KPTR       = BPF_KPTR_UNREF | BPF_KPTR_REF,
 };
 
-struct bpf_map_value_off_desc {
+struct btf_field_kptr {
+	struct btf *btf;
+	struct module *module;
+	btf_dtor_kfunc_t dtor;
+	u32 btf_id;
+};
+
+struct btf_field {
 	u32 offset;
-	enum bpf_kptr_type type;
-	struct {
-		struct btf *btf;
-		struct module *module;
-		btf_dtor_kfunc_t dtor;
-		u32 btf_id;
-	} kptr;
+	enum btf_field_type type;
+	union {
+		struct btf_field_kptr kptr;
+	};
 };
 
-struct bpf_map_value_off {
-	u32 nr_off;
-	struct bpf_map_value_off_desc off[];
+struct btf_record {
+	u32 cnt;
+	u32 field_mask;
+	struct btf_field fields[];
 };
 
-struct bpf_map_off_arr {
+struct btf_field_offs {
 	u32 cnt;
 	u32 field_off[BPF_MAP_OFF_ARR_MAX];
 	u8 field_sz[BPF_MAP_OFF_ARR_MAX];
@@ -215,7 +221,7 @@ struct bpf_map {
 	u64 map_extra; /* any per-map-type extra fields */
 	u32 map_flags;
 	int spin_lock_off; /* >=0 valid offset, <0 error */
-	struct bpf_map_value_off *kptr_off_tab;
+	struct btf_record *record;
 	int timer_off; /* >=0 valid offset, <0 error */
 	u32 id;
 	int numa_node;
@@ -227,7 +233,7 @@ struct bpf_map {
 	struct obj_cgroup *objcg;
 #endif
 	char name[BPF_OBJ_NAME_LEN];
-	struct bpf_map_off_arr *off_arr;
+	struct btf_field_offs *field_offs;
 	/* The 3rd and 4th cacheline with misc members to avoid false sharing
 	 * particularly with refcounting.
 	 */
@@ -251,6 +257,37 @@ struct bpf_map {
 	bool frozen; /* write-once; write-protected by freeze_mutex */
 };
 
+static inline u32 btf_field_type_size(enum btf_field_type type)
+{
+	switch (type) {
+	case BPF_KPTR_UNREF:
+	case BPF_KPTR_REF:
+		return sizeof(u64);
+	default:
+		WARN_ON_ONCE(1);
+		return 0;
+	}
+}
+
+static inline u32 btf_field_type_align(enum btf_field_type type)
+{
+	switch (type) {
+	case BPF_KPTR_UNREF:
+	case BPF_KPTR_REF:
+		return __alignof__(u64);
+	default:
+		WARN_ON_ONCE(1);
+		return 0;
+	}
+}
+
+static inline bool btf_record_has_field(const struct btf_record *rec, enum btf_field_type type)
+{
+	if (IS_ERR_OR_NULL(rec))
+		return false;
+	return rec->field_mask & type;
+}
+
 static inline bool map_value_has_spin_lock(const struct bpf_map *map)
 {
 	return map->spin_lock_off >= 0;
@@ -261,23 +298,19 @@ static inline bool map_value_has_timer(const struct bpf_map *map)
 	return map->timer_off >= 0;
 }
 
-static inline bool map_value_has_kptrs(const struct bpf_map *map)
-{
-	return !IS_ERR_OR_NULL(map->kptr_off_tab);
-}
-
 static inline void check_and_init_map_value(struct bpf_map *map, void *dst)
 {
 	if (unlikely(map_value_has_spin_lock(map)))
 		memset(dst + map->spin_lock_off, 0, sizeof(struct bpf_spin_lock));
 	if (unlikely(map_value_has_timer(map)))
 		memset(dst + map->timer_off, 0, sizeof(struct bpf_timer));
-	if (unlikely(map_value_has_kptrs(map))) {
-		struct bpf_map_value_off *tab = map->kptr_off_tab;
+	if (!IS_ERR_OR_NULL(map->record)) {
+		struct btf_field *fields = map->record->fields;
+		u32 cnt = map->record->cnt;
 		int i;
 
-		for (i = 0; i < tab->nr_off; i++)
-			*(u64 *)(dst + tab->off[i].offset) = 0;
+		for (i = 0; i < cnt; i++)
+			memset(dst + fields[i].offset, 0, btf_field_type_size(fields[i].type));
 	}
 }
 
@@ -303,7 +336,7 @@ static inline void __copy_map_value(struct bpf_map *map, void *dst, void *src, b
 	u32 curr_off = 0;
 	int i;
 
-	if (likely(!map->off_arr)) {
+	if (likely(!map->field_offs)) {
 		if (long_memcpy)
 			bpf_long_memcpy(dst, src, round_up(map->value_size, 8));
 		else
@@ -311,11 +344,12 @@ static inline void __copy_map_value(struct bpf_map *map, void *dst, void *src, b
 		return;
 	}
 
-	for (i = 0; i < map->off_arr->cnt; i++) {
-		u32 next_off = map->off_arr->field_off[i];
+	for (i = 0; i < map->field_offs->cnt; i++) {
+		u32 next_off = map->field_offs->field_off[i];
+		u32 sz = next_off - curr_off;
 
-		memcpy(dst + curr_off, src + curr_off, next_off - curr_off);
-		curr_off += map->off_arr->field_sz[i];
+		memcpy(dst + curr_off, src + curr_off, sz);
+		curr_off += map->field_offs->field_sz[i] + sz;
 	}
 	memcpy(dst + curr_off, src + curr_off, map->value_size - curr_off);
 }
@@ -335,16 +369,17 @@ static inline void zero_map_value(struct bpf_map *map, void *dst)
 	u32 curr_off = 0;
 	int i;
 
-	if (likely(!map->off_arr)) {
+	if (likely(!map->field_offs)) {
 		memset(dst, 0, map->value_size);
 		return;
 	}
 
-	for (i = 0; i < map->off_arr->cnt; i++) {
-		u32 next_off = map->off_arr->field_off[i];
+	for (i = 0; i < map->field_offs->cnt; i++) {
+		u32 next_off = map->field_offs->field_off[i];
+		u32 sz = next_off - curr_off;
 
-		memset(dst + curr_off, 0, next_off - curr_off);
-		curr_off += map->off_arr->field_sz[i];
+		memset(dst + curr_off, 0, sz);
+		curr_off += map->field_offs->field_sz[i] + sz;
 	}
 	memset(dst + curr_off, 0, map->value_size - curr_off);
 }
@@ -1699,11 +1734,13 @@ void bpf_prog_put(struct bpf_prog *prog);
 void bpf_prog_free_id(struct bpf_prog *prog, bool do_idr_lock);
 void bpf_map_free_id(struct bpf_map *map, bool do_idr_lock);
 
-struct bpf_map_value_off_desc *bpf_map_kptr_off_contains(struct bpf_map *map, u32 offset);
-void bpf_map_free_kptr_off_tab(struct bpf_map *map);
-struct bpf_map_value_off *bpf_map_copy_kptr_off_tab(const struct bpf_map *map);
-bool bpf_map_equal_kptr_off_tab(const struct bpf_map *map_a, const struct bpf_map *map_b);
-void bpf_map_free_kptrs(struct bpf_map *map, void *map_value);
+struct btf_field *btf_record_find(const struct btf_record *rec,
+				  u32 offset, enum btf_field_type type);
+void btf_record_free(struct btf_record *rec);
+void bpf_map_free_record(struct bpf_map *map);
+struct btf_record *btf_record_dup(const struct btf_record *rec);
+bool btf_record_equal(const struct btf_record *rec_a, const struct btf_record *rec_b);
+void bpf_obj_free_fields(const struct btf_record *rec, void *obj);
 
 struct bpf_map *bpf_map_get(u32 ufd);
 struct bpf_map *bpf_map_get_with_uref(u32 ufd);
include/linux/btf.h +1 -2
index 86aad9b2ce02..9e62717cdc7a 100644
@@ -163,8 +163,7 @@ bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s,
 			   u32 expected_offset, u32 expected_size);
 int btf_find_spin_lock(const struct btf *btf, const struct btf_type *t);
 int btf_find_timer(const struct btf *btf, const struct btf_type *t);
-struct bpf_map_value_off *btf_parse_kptrs(const struct btf *btf,
-					  const struct btf_type *t);
+struct btf_record *btf_parse_fields(const struct btf *btf, const struct btf_type *t);
 bool btf_type_is_void(const struct btf_type *t);
 s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind);
 const struct btf_type *btf_type_skip_modifiers(const struct btf *btf,
kernel/bpf/arraymap.c +6 -7
index 832b2659e96e..417f84342e98 100644
@@ -310,8 +310,7 @@ static void check_and_free_fields(struct bpf_array *arr, void *val)
 {
 	if (map_value_has_timer(&arr->map))
 		bpf_timer_cancel_and_free(val + arr->map.timer_off);
-	if (map_value_has_kptrs(&arr->map))
-		bpf_map_free_kptrs(&arr->map, val);
+	bpf_obj_free_fields(arr->map.record, val);
 }
 
 /* Called from syscall or from eBPF program */
@@ -409,7 +408,7 @@ static void array_map_free_timers(struct bpf_map *map)
 	struct bpf_array *array = container_of(map, struct bpf_array, map);
 	int i;
 
-	/* We don't reset or free kptr on uref dropping to zero. */
+	/* We don't reset or free fields other than timer on uref dropping to zero. */
 	if (!map_value_has_timer(map))
 		return;
 
@@ -423,22 +422,22 @@ static void array_map_free(struct bpf_map *map)
 	struct bpf_array *array = container_of(map, struct bpf_array, map);
 	int i;
 
-	if (map_value_has_kptrs(map)) {
+	if (!IS_ERR_OR_NULL(map->record)) {
 		if (array->map.map_type == BPF_MAP_TYPE_PERCPU_ARRAY) {
 			for (i = 0; i < array->map.max_entries; i++) {
 				void __percpu *pptr = array->pptrs[i & array->index_mask];
 				int cpu;
 
 				for_each_possible_cpu(cpu) {
-					bpf_map_free_kptrs(map, per_cpu_ptr(pptr, cpu));
+					bpf_obj_free_fields(map->record, per_cpu_ptr(pptr, cpu));
 					cond_resched();
 				}
 			}
 		} else {
 			for (i = 0; i < array->map.max_entries; i++)
-				bpf_map_free_kptrs(map, array_map_elem_ptr(array, i));
+				bpf_obj_free_fields(map->record, array_map_elem_ptr(array, i));
 		}
-		bpf_map_free_kptr_off_tab(map);
+		bpf_map_free_record(map);
 	}
 
 	if (array->map.map_type == BPF_MAP_TYPE_PERCPU_ARRAY)
kernel/bpf/btf.c +31 -36

152 lines not on this page · raw message

kernel/bpf/hashtab.c +6 -8
index f39ee3e05589..c5ea8f9bb7a9 100644
@@ -238,21 +238,20 @@ static void htab_free_prealloced_timers(struct bpf_htab *htab)
 	}
 }
 
-static void htab_free_prealloced_kptrs(struct bpf_htab *htab)
+static void htab_free_prealloced_fields(struct bpf_htab *htab)
 {
 	u32 num_entries = htab->map.max_entries;
 	int i;
 
-	if (!map_value_has_kptrs(&htab->map))
+	if (IS_ERR_OR_NULL(htab->map.record))
 		return;
 	if (htab_has_extra_elems(htab))
 		num_entries += num_possible_cpus();
-
 	for (i = 0; i < num_entries; i++) {
 		struct htab_elem *elem;
 
 		elem = get_htab_elem(htab, i);
-		bpf_map_free_kptrs(&htab->map, elem->key + round_up(htab->map.key_size, 8));
+		bpf_obj_free_fields(htab->map.record, elem->key + round_up(htab->map.key_size, 8));
 		cond_resched();
 	}
 }
@@ -766,8 +765,7 @@ static void check_and_free_fields(struct bpf_htab *htab,
 
 	if (map_value_has_timer(&htab->map))
 		bpf_timer_cancel_and_free(map_value + htab->map.timer_off);
-	if (map_value_has_kptrs(&htab->map))
-		bpf_map_free_kptrs(&htab->map, map_value);
+	bpf_obj_free_fields(htab->map.record, map_value);
 }
 
 /* It is called from the bpf_lru_list when the LRU needs to delete
@@ -1517,11 +1515,11 @@ static void htab_map_free(struct bpf_map *map)
 	if (!htab_is_prealloc(htab)) {
 		delete_all_elements(htab);
 	} else {
-		htab_free_prealloced_kptrs(htab);
+		htab_free_prealloced_fields(htab);
 		prealloc_destroy(htab);
 	}
 
-	bpf_map_free_kptr_off_tab(map);
+	bpf_map_free_record(map);
 	free_percpu(htab->extra_elems);
 	bpf_map_area_free(htab->buckets);
 	bpf_mem_alloc_destroy(&htab->pcpu_ma);
kernel/bpf/map_in_map.c +11 -3
index 135205d0d560..d6c662183f88 100644
@@ -52,7 +52,15 @@ struct bpf_map *bpf_map_meta_alloc(int inner_map_ufd)
 	inner_map_meta->max_entries = inner_map->max_entries;
 	inner_map_meta->spin_lock_off = inner_map->spin_lock_off;
 	inner_map_meta->timer_off = inner_map->timer_off;
-	inner_map_meta->kptr_off_tab = bpf_map_copy_kptr_off_tab(inner_map);
+	inner_map_meta->record = btf_record_dup(inner_map->record);
+	if (IS_ERR(inner_map_meta->record)) {
+		/* btf_record_dup returns NULL or valid pointer in case of
+		 * invalid/empty/valid, but ERR_PTR in case of errors. During
+		 * equality NULL or IS_ERR is equivalent.
+		 */
+		fdput(f);
+		return ERR_CAST(inner_map_meta->record);
+	}
 	if (inner_map->btf) {
 		btf_get(inner_map->btf);
 		inner_map_meta->btf = inner_map->btf;
@@ -72,7 +80,7 @@ struct bpf_map *bpf_map_meta_alloc(int inner_map_ufd)
 
 void bpf_map_meta_free(struct bpf_map *map_meta)
 {
-	bpf_map_free_kptr_off_tab(map_meta);
+	bpf_map_free_record(map_meta);
 	btf_put(map_meta->btf);
 	kfree(map_meta);
 }
@@ -86,7 +94,7 @@ bool bpf_map_meta_equal(const struct bpf_map *meta0,
 		meta0->value_size == meta1->value_size &&
 		meta0->timer_off == meta1->timer_off &&
 		meta0->map_flags == meta1->map_flags &&
-		bpf_map_equal_kptr_off_tab(meta0, meta1);
+		btf_record_equal(meta0->record, meta1->record);
 }
 
 void *bpf_map_fd_get_ptr(struct bpf_map *map,
kernel/bpf/syscall.c +149 -114

394 lines not on this page · raw message

kernel/bpf/verifier.c +47 -49

229 lines not on this page · raw message

Signature · 1 line
2.38.1
#10 lore raw

Re: [PATCH bpf-next v4 06/24] bpf: Refactor kptr_off_tab into btf_record

kernel/bpf/syscall.c static int bpf_map_alloc_off_arr(struct bpf_map *map) · line 959

Quoted 7 lines · Kumar Kartikeya Dwivedi
kernel/bpf/syscall.c +1 -2
@@ -936,51 +956,51 @@ static int bpf_map_alloc_off_arr(struct bpf_map *map)
 {
 	bool has_spin_lock = map_value_has_spin_lock(map);
 	bool has_timer = map_value_has_timer(map);
-	bool has_kptrs = map_value_has_kptrs(map);
-	struct bpf_map_off_arr *off_arr;
+	bool has_fields = !IS_ERR_OR_NULL(map);

should have been map->record.

kernel/bpf/verifier.c static int process_kptr_func(struct bpf_verifier_env *env, int regno, · line 5554

Quoted 13 lines
kernel/bpf/verifier.c +2 -9
-	if (!map_value_has_kptrs(map_ptr)) {
-		ret = PTR_ERR_OR_ZERO(map_ptr->kptr_off_tab);
-		if (ret == -E2BIG)
-			verbose(env, "map '%s' has more than %d kptr\n", map_ptr->name,
-				BPF_MAP_VALUE_OFF_MAX);
-		else if (ret == -EEXIST)
-			verbose(env, "map '%s' has repeating kptr BTF tags\n", map_ptr->name);
-		else
-			verbose(env, "map '%s' has no valid kptr\n", map_ptr->name);
+	if (!btf_record_has_field(map_ptr->record, BPF_KPTR)) {
+		verbose(env, "map '%s' has no valid kptr\n", map_ptr->name);
 		return -EINVAL;
 	}

The loss of verbosity is annoying, but I see why you're doing it.

#11 lore raw

Re: [PATCH bpf-next v4 06/24] bpf: Refactor kptr_off_tab into btf_record

In reply to Kumar Kartikeya Dwivedi
Quoted 5 lines · Kumar Kartikeya Dwivedi
include/linux/bpf.h +0 -0
 		else
@@ -311,11 +344,12 @@ static inline void __copy_map_value(struct bpf_map *map, void *dst, void *src, b
 		return;
 	}
 

include/linux/bpf.h static inline void __copy_map_value(struct bpf_map *map, void *dst, void *src, b · line 352

Quoted 10 lines
include/linux/bpf.h +5 -4
-	for (i = 0; i < map->off_arr->cnt; i++) {
-		u32 next_off = map->off_arr->field_off[i];
+	for (i = 0; i < map->field_offs->cnt; i++) {
+		u32 next_off = map->field_offs->field_off[i];
+		u32 sz = next_off - curr_off;
 
-		memcpy(dst + curr_off, src + curr_off, next_off - curr_off);
-		curr_off += map->off_arr->field_sz[i];
+		memcpy(dst + curr_off, src + curr_off, sz);
+		curr_off += map->field_offs->field_sz[i] + sz;

This is a clear bug. The kernel is crashing with this change. How did you test this?

Quoted 13 lines
include/linux/bpf.h +1 -1
 	}
 	memcpy(dst + curr_off, src + curr_off, map->value_size - curr_off);
 }
@@ -335,16 +369,17 @@ static inline void zero_map_value(struct bpf_map *map, void *dst)
 	u32 curr_off = 0;
 	int i;
 
-	if (likely(!map->off_arr)) {
+	if (likely(!map->field_offs)) {
 		memset(dst, 0, map->value_size);
 		return;
 	}
 

include/linux/bpf.h static inline void zero_map_value(struct bpf_map *map, void *dst) · line 382

Quoted 10 lines
include/linux/bpf.h +5 -4
-	for (i = 0; i < map->off_arr->cnt; i++) {
-		u32 next_off = map->off_arr->field_off[i];
+	for (i = 0; i < map->field_offs->cnt; i++) {
+		u32 next_off = map->field_offs->field_off[i];
+		u32 sz = next_off - curr_off;
 
-		memset(dst + curr_off, 0, next_off - curr_off);
-		curr_off += map->off_arr->field_sz[i];
+		memset(dst + curr_off, 0, sz);
+		curr_off += map->field_offs->field_sz[i] + sz;

same thing

author maintainer
#12 lore raw

Re: [PATCH bpf-next v4 06/24] bpf: Refactor kptr_off_tab into btf_record

Quoted 12 lines · Alexei Starovoitov
Quoted 11 lines · Kumar Kartikeya Dwivedi
include/linux/bpf.h +3 -2
 		else
@@ -311,11 +344,12 @@ static inline void __copy_map_value(struct bpf_map *map, void *dst, void *src, b
 		return;
 	}
 
-	for (i = 0; i < map->off_arr->cnt; i++) {
-		u32 next_off = map->off_arr->field_off[i];
+	for (i = 0; i < map->field_offs->cnt; i++) {
+		u32 next_off = map->field_offs->field_off[i];
+		u32 sz = next_off - curr_off;
 
Quoted 8 lines

include/linux/bpf.h static inline void __copy_map_value(struct bpf_map *map, void *dst, void *src, b · line 352

Quoted 4 lines
include/linux/bpf.h +2 -2
-		memcpy(dst + curr_off, src + curr_off, next_off - curr_off);
-		curr_off += map->off_arr->field_sz[i];
+		memcpy(dst + curr_off, src + curr_off, sz);
+		curr_off += map->field_offs->field_sz[i] + sz;

This is a clear bug. The kernel is crashing with this change. How did you test this?

For me it is crashing at bpf-next now without this.

When for map value with size 48, having fields at:

off: 0, 16, 32
sz:  4, 16, 16

The above produces:

memcpy(dst + 0, src + 0, 0) memcpy(dst + 4, src + 4, 12) memcpy(dst + 32, src + 32, 0) memcpy(dst + 48, src + 48, 0)

Without it, it becomes:

memcpy(dst + 0, src + 0, 0) memcpy(dst + 4, src + 4, 12) memcpy(dst + 20, src + 20, 12) memcpy(dst + 36, src + 36, 12)

I will send a follow up fix.

Quoted 25 lines
Quoted 13 lines
include/linux/bpf.h +1 -1
 	}
 	memcpy(dst + curr_off, src + curr_off, map->value_size - curr_off);
 }
@@ -335,16 +369,17 @@ static inline void zero_map_value(struct bpf_map *map, void *dst)
 	u32 curr_off = 0;
 	int i;
 
-	if (likely(!map->off_arr)) {
+	if (likely(!map->field_offs)) {
 		memset(dst, 0, map->value_size);
 		return;
 	}
 

include/linux/bpf.h static inline void zero_map_value(struct bpf_map *map, void *dst) · line 382

Quoted 10 lines
include/linux/bpf.h +5 -4
-	for (i = 0; i < map->off_arr->cnt; i++) {
-		u32 next_off = map->off_arr->field_off[i];
+	for (i = 0; i < map->field_offs->cnt; i++) {
+		u32 next_off = map->field_offs->field_off[i];
+		u32 sz = next_off - curr_off;
 
-		memset(dst + curr_off, 0, next_off - curr_off);
-		curr_off += map->off_arr->field_sz[i];
+		memset(dst + curr_off, 0, sz);
+		curr_off += map->field_offs->field_sz[i] + sz;

same thing

author maintainer
#13 lore raw

Re: [PATCH bpf-next v4 06/24] bpf: Refactor kptr_off_tab into btf_record

Quoted 35 lines · Kumar Kartikeya Dwivedi
Quoted 12 lines · Alexei Starovoitov
Quoted 11 lines · Kumar Kartikeya Dwivedi
include/linux/bpf.h +3 -2
 		else
@@ -311,11 +344,12 @@ static inline void __copy_map_value(struct bpf_map *map, void *dst, void *src, b
 		return;
 	}
 
-	for (i = 0; i < map->off_arr->cnt; i++) {
-		u32 next_off = map->off_arr->field_off[i];
+	for (i = 0; i < map->field_offs->cnt; i++) {
+		u32 next_off = map->field_offs->field_off[i];
+		u32 sz = next_off - curr_off;
 
Quoted 8 lines

include/linux/bpf.h static inline void __copy_map_value(struct bpf_map *map, void *dst, void *src, b · line 352

Quoted 4 lines
include/linux/bpf.h +2 -2
-		memcpy(dst + curr_off, src + curr_off, next_off - curr_off);
-		curr_off += map->off_arr->field_sz[i];
+		memcpy(dst + curr_off, src + curr_off, sz);
+		curr_off += map->field_offs->field_sz[i] + sz;

This is a clear bug. The kernel is crashing with this change. How did you test this?

For me it is crashing at bpf-next now without this.

When for map value with size 48, having fields at:

off: 0, 16, 32
sz:  4, 16, 16

The above produces:

memcpy(dst + 0, src + 0, 0) memcpy(dst + 4, src + 4, 12) memcpy(dst + 32, src + 32, 0) memcpy(dst + 48, src + 48, 0)

Quoted 9 lines

Without it, it becomes:

memcpy(dst + 0, src + 0, 0) memcpy(dst + 4, src + 4, 12) memcpy(dst + 20, src + 20, 12) memcpy(dst + 36, src + 36, 12)

I will send a follow up fix.

I think this is broken in the original code, I didn't realise this at first but it's effectively the same in that commit. So it should have Fixes: tag for that.

#14 lore raw

Re: [PATCH bpf-next v4 06/24] bpf: Refactor kptr_off_tab into btf_record

In reply to Kumar Kartikeya Dwivedi
Quoted 21 lines · Kumar Kartikeya Dwivedi
kernel/bpf/btf.c +4 -8
-
-	for (i = 0; i < nr_off; i++) {
+	rec->cnt = 0;
+	for (i = 0; i < cnt; i++) {
 		const struct btf_type *t;
 		s32 id;
@@ -3500,28 +3499,24 @@ struct bpf_map_value_off *btf_parse_kptrs(const struct btf *btf,
 				ret = -EINVAL;
 				goto end_mod;
 			}
-			tab->off[i].kptr.dtor = (void *)addr;
+			rec->fields[i].kptr.dtor = (void *)addr;
 		}
 
-		tab->off[i].offset = info_arr[i].off;
-		tab->off[i].type = info_arr[i].type;
-		tab->off[i].kptr.btf_id = id;
-		tab->off[i].kptr.btf = kernel_btf;
-		tab->off[i].kptr.module = mod;
+		rec->fields[i].offset = info_arr[i].off;

kernel/bpf/btf.c struct bpf_map_value_off *btf_parse_kptrs(const struct btf *btf, · line 3513

Quoted 10 lines
kernel/bpf/btf.c +7 -2
+		rec->fields[i].type = info_arr[i].type;
+		rec->fields[i].kptr.btf_id = id;
+		rec->fields[i].kptr.btf = kernel_btf;
+		rec->fields[i].kptr.module = mod;
+		rec->cnt++;
 	}
-	tab->nr_off = nr_off;
-	return tab;
+	rec->cnt = cnt;
+	return rec;

This is weird. You also undo this assignment in the next patch. What is the point of rec->cnt = 0;
followed by rec->cnt++
just to be overwritten with rec->cnt = cnt;
??

#15 lore raw

Re: [PATCH bpf-next v4 06/24] bpf: Refactor kptr_off_tab into btf_record

In reply to Kumar Kartikeya Dwivedi
Quoted 9 lines · Kumar Kartikeya Dwivedi
include/linux/bpf.h +4 -3
-enum bpf_kptr_type {
-	BPF_KPTR_UNREF,
-	BPF_KPTR_REF,
+enum btf_field_type {
+	BPF_KPTR_UNREF = (1 << 2),
+	BPF_KPTR_REF   = (1 << 3),
+	BPF_KPTR       = BPF_KPTR_UNREF | BPF_KPTR_REF,
 };

...

Quoted 9 lines
kernel/bpf/syscall.c +9 -0
+		for (i = 0; i < sizeof(map->record->field_mask) * 8; i++) {
+			switch (map->record->field_mask & (1 << i)) {
+			case 0:
+				continue;
+			case BPF_KPTR_UNREF:
+			case BPF_KPTR_REF:
+				if (map->map_type != BPF_MAP_TYPE_HASH &&
+				    map->map_type != BPF_MAP_TYPE_LRU_HASH &&
+				    map->map_type != BPF_MAP_TYPE_ARRAY &&

kernel/bpf/syscall.c static int map_check_btf(struct bpf_map *map, const struct btf *btf, · line 1091

Quoted 10 lines
kernel/bpf/syscall.c +10 -0
+				    map->map_type != BPF_MAP_TYPE_PERCPU_ARRAY) {
+					ret = -EOPNOTSUPP;
+					goto free_map_tab;
+				}
+				break;
+			default:
+				/* Fail if map_type checks are missing for a field type */
+				ret = -EOPNOTSUPP;
+				goto free_map_tab;
+			}

With this patch alone this is also wrong.
And it breaks bisect.
Please make sure to do a full vmtest.sh for every patch in the series.

#16 lore raw

Re: [PATCH bpf-next v4 06/24] bpf: Refactor kptr_off_tab into btf_record

Quoted 34 lines · Alexei Starovoitov
Quoted 9 lines · Kumar Kartikeya Dwivedi
include/linux/bpf.h +4 -3
-enum bpf_kptr_type {
-     BPF_KPTR_UNREF,
-     BPF_KPTR_REF,
+enum btf_field_type {
+     BPF_KPTR_UNREF = (1 << 2),
+     BPF_KPTR_REF   = (1 << 3),
+     BPF_KPTR       = BPF_KPTR_UNREF | BPF_KPTR_REF,
 };

...

Quoted 9 lines
kernel/bpf/syscall.c +9 -0
+             for (i = 0; i < sizeof(map->record->field_mask) * 8; i++) {
+                     switch (map->record->field_mask & (1 << i)) {
+                     case 0:
+                             continue;
+                     case BPF_KPTR_UNREF:
+                     case BPF_KPTR_REF:
+                             if (map->map_type != BPF_MAP_TYPE_HASH &&
+                                 map->map_type != BPF_MAP_TYPE_LRU_HASH &&
+                                 map->map_type != BPF_MAP_TYPE_ARRAY &&

kernel/bpf/syscall.c static int map_check_btf(struct bpf_map *map, const struct btf *btf, · line 1091

Quoted 10 lines
kernel/bpf/syscall.c +10 -0
+                                 map->map_type != BPF_MAP_TYPE_PERCPU_ARRAY) {
+                                     ret = -EOPNOTSUPP;
+                                     goto free_map_tab;
+                             }
+                             break;
+                     default:
+                             /* Fail if map_type checks are missing for a field type */
+                             ret = -EOPNOTSUPP;
+                             goto free_map_tab;
+                     }
Quoted 1 line

With this patch alone this is also wrong.

Actually this bit is probably fine. The bug is elsewhere.

The point below stands:

Quoted 2 lines

And it breaks bisect.
Please make sure to do a full vmtest.sh for every patch in the series.

author maintainer
#17 lore raw

Re: [PATCH bpf-next v4 06/24] bpf: Refactor kptr_off_tab into btf_record

Quoted 36 lines · Alexei Starovoitov
Quoted 34 lines · Alexei Starovoitov
Quoted 9 lines · Kumar Kartikeya Dwivedi
include/linux/bpf.h +4 -3
-enum bpf_kptr_type {
-     BPF_KPTR_UNREF,
-     BPF_KPTR_REF,
+enum btf_field_type {
+     BPF_KPTR_UNREF = (1 << 2),
+     BPF_KPTR_REF   = (1 << 3),
+     BPF_KPTR       = BPF_KPTR_UNREF | BPF_KPTR_REF,
 };

...

Quoted 19 lines
kernel/bpf/syscall.c +19 -0
+             for (i = 0; i < sizeof(map->record->field_mask) * 8; i++) {
+                     switch (map->record->field_mask & (1 << i)) {
+                     case 0:
+                             continue;
+                     case BPF_KPTR_UNREF:
+                     case BPF_KPTR_REF:
+                             if (map->map_type != BPF_MAP_TYPE_HASH &&
+                                 map->map_type != BPF_MAP_TYPE_LRU_HASH &&
+                                 map->map_type != BPF_MAP_TYPE_ARRAY &&
+                                 map->map_type != BPF_MAP_TYPE_PERCPU_ARRAY) {
+                                     ret = -EOPNOTSUPP;
+                                     goto free_map_tab;
+                             }
+                             break;
+                     default:
+                             /* Fail if map_type checks are missing for a field type */
+                             ret = -EOPNOTSUPP;
+                             goto free_map_tab;
+                     }
Quoted 9 lines
Quoted 1 line

With this patch alone this is also wrong.

Actually this bit is probably fine. The bug is elsewhere.

The point below stands:

Quoted 2 lines

And it breaks bisect.
Please make sure to do a full vmtest.sh for every patch in the series.

I'm sorry. I made multiple small changes to these two and never retested them again in isolation, and then it was 'fixed' by later changes. I'll make sure it doesn't happen again.

author maintainer
#18 lore raw

PATCH v4 7/24 bpf: Consolidate spin_lock, timer management into btf_record

In reply to Kumar Kartikeya Dwivedi

Now that kptr_off_tab has been refactored into btf_record, and can hold more than one specific field type, accomodate bpf_spin_lock and bpf_timer as well.

While they don't require any more metadata than offset, having all special fields in one place allows us to share the same code for allocated user defined types and handle both map values and these allocated objects in a similar fashion.

As an optimization, we still keep spin_lock_off and timer_off offsets in the btf_record structure, just to avoid having to find the btf_field struct each time their offset is needed. This is mostly needed to manipulate such objects in a map value at runtime. It's ok to hardcode just one offset as more than one field is disallowed.

---
 include/linux/bpf.h            |  53 +++---
 include/linux/btf.h            |   3 +-
 kernel/bpf/arraymap.c          |  19 +-
 kernel/bpf/bpf_local_storage.c |   2 +-
 kernel/bpf/btf.c               | 325 ++++++++++++++++++---------------
 kernel/bpf/hashtab.c           |  24 +--
 kernel/bpf/helpers.c           |   6 +-
 kernel/bpf/local_storage.c     |   2 +-
 kernel/bpf/map_in_map.c        |   5 +-
 kernel/bpf/syscall.c           | 133 ++++++--------
 kernel/bpf/verifier.c          |  82 +++------
 net/core/bpf_sk_storage.c      |   4 +-
 12 files changed, 314 insertions(+), 344 deletions(-)
include/linux/bpf.h +32 -21
index 1440e7c3c510..d5c81b09577a 100644
@@ -166,13 +166,13 @@ struct bpf_map_ops {
 
 enum {
 	/* Support at most 8 pointers in a BTF type */
-	BTF_FIELDS_MAX	      = 8,
-	BPF_MAP_OFF_ARR_MAX   = BTF_FIELDS_MAX +
-				1 + /* for bpf_spin_lock */
-				1,  /* for bpf_timer */
+	BTF_FIELDS_MAX	      = 10,
+	BPF_MAP_OFF_ARR_MAX   = BTF_FIELDS_MAX,
 };
 
 enum btf_field_type {
+	BPF_SPIN_LOCK  = (1 << 0),
+	BPF_TIMER      = (1 << 1),
 	BPF_KPTR_UNREF = (1 << 2),
 	BPF_KPTR_REF   = (1 << 3),
 	BPF_KPTR       = BPF_KPTR_UNREF | BPF_KPTR_REF,
@@ -196,6 +196,8 @@ struct btf_field {
 struct btf_record {
 	u32 cnt;
 	u32 field_mask;
+	int spin_lock_off;
+	int timer_off;
 	struct btf_field fields[];
 };
 
@@ -220,10 +222,8 @@ struct bpf_map {
 	u32 max_entries;
 	u64 map_extra; /* any per-map-type extra fields */
 	u32 map_flags;
-	int spin_lock_off; /* >=0 valid offset, <0 error */
-	struct btf_record *record;
-	int timer_off; /* >=0 valid offset, <0 error */
 	u32 id;
+	struct btf_record *record;
 	int numa_node;
 	u32 btf_key_type_id;
 	u32 btf_value_type_id;
@@ -257,9 +257,29 @@ struct bpf_map {
 	bool frozen; /* write-once; write-protected by freeze_mutex */
 };
 
+static inline const char *btf_field_type_name(enum btf_field_type type)
+{
+	switch (type) {
+	case BPF_SPIN_LOCK:
+		return "bpf_spin_lock";
+	case BPF_TIMER:
+		return "bpf_timer";
+	case BPF_KPTR_UNREF:
+	case BPF_KPTR_REF:
+		return "kptr";
+	default:
+		WARN_ON_ONCE(1);
+		return "unknown";
+	}
+}
+
 static inline u32 btf_field_type_size(enum btf_field_type type)
 {
 	switch (type) {
+	case BPF_SPIN_LOCK:
+		return sizeof(struct bpf_spin_lock);
+	case BPF_TIMER:
+		return sizeof(struct bpf_timer);
 	case BPF_KPTR_UNREF:
 	case BPF_KPTR_REF:
 		return sizeof(u64);
@@ -272,6 +292,10 @@ static inline u32 btf_field_type_size(enum btf_field_type type)
 static inline u32 btf_field_type_align(enum btf_field_type type)
 {
 	switch (type) {
+	case BPF_SPIN_LOCK:
+		return __alignof__(struct bpf_spin_lock);
+	case BPF_TIMER:
+		return __alignof__(struct bpf_timer);
 	case BPF_KPTR_UNREF:
 	case BPF_KPTR_REF:
 		return __alignof__(u64);
@@ -288,22 +312,8 @@ static inline bool btf_record_has_field(const struct btf_record *rec, enum btf_f
 	return rec->field_mask & type;
 }
 
-static inline bool map_value_has_spin_lock(const struct bpf_map *map)
-{
-	return map->spin_lock_off >= 0;
-}
-
-static inline bool map_value_has_timer(const struct bpf_map *map)
-{
-	return map->timer_off >= 0;
-}
-
 static inline void check_and_init_map_value(struct bpf_map *map, void *dst)
 {
-	if (unlikely(map_value_has_spin_lock(map)))
-		memset(dst + map->spin_lock_off, 0, sizeof(struct bpf_spin_lock));
-	if (unlikely(map_value_has_timer(map)))
-		memset(dst + map->timer_off, 0, sizeof(struct bpf_timer));
 	if (!IS_ERR_OR_NULL(map->record)) {
 		struct btf_field *fields = map->record->fields;
 		u32 cnt = map->record->cnt;
@@ -1740,6 +1750,7 @@ void btf_record_free(struct btf_record *rec);
 void bpf_map_free_record(struct bpf_map *map);
 struct btf_record *btf_record_dup(const struct btf_record *rec);
 bool btf_record_equal(const struct btf_record *rec_a, const struct btf_record *rec_b);
+void bpf_obj_free_timer(const struct btf_record *rec, void *obj);
 void bpf_obj_free_fields(const struct btf_record *rec, void *obj);
 
 struct bpf_map *bpf_map_get(u32 ufd);
include/linux/btf.h +2 -1
index 9e62717cdc7a..282006abd062 100644
@@ -163,7 +163,8 @@ bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s,
 			   u32 expected_offset, u32 expected_size);
 int btf_find_spin_lock(const struct btf *btf, const struct btf_type *t);
 int btf_find_timer(const struct btf *btf, const struct btf_type *t);
-struct btf_record *btf_parse_fields(const struct btf *btf, const struct btf_type *t);
+struct btf_record *btf_parse_fields(const struct btf *btf, const struct btf_type *t,
+				    u32 field_mask, u32 value_size);
 bool btf_type_is_void(const struct btf_type *t);
 s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind);
 const struct btf_type *btf_type_skip_modifiers(const struct btf *btf,
kernel/bpf/arraymap.c +6 -13
index 417f84342e98..672eb17ac421 100644
@@ -306,13 +306,6 @@ static int array_map_get_next_key(struct bpf_map *map, void *key, void *next_key
 	return 0;
 }
 
-static void check_and_free_fields(struct bpf_array *arr, void *val)
-{
-	if (map_value_has_timer(&arr->map))
-		bpf_timer_cancel_and_free(val + arr->map.timer_off);
-	bpf_obj_free_fields(arr->map.record, val);
-}
-
 /* Called from syscall or from eBPF program */
 static int array_map_update_elem(struct bpf_map *map, void *key, void *value,
 				 u64 map_flags)
@@ -334,13 +327,13 @@ static int array_map_update_elem(struct bpf_map *map, void *key, void *value,
 		return -EEXIST;
 
 	if (unlikely((map_flags & BPF_F_LOCK) &&
-		     !map_value_has_spin_lock(map)))
+		     !btf_record_has_field(map->record, BPF_SPIN_LOCK)))
 		return -EINVAL;
 
 	if (array->map.map_type == BPF_MAP_TYPE_PERCPU_ARRAY) {
 		val = this_cpu_ptr(array->pptrs[index & array->index_mask]);
 		copy_map_value(map, val, value);
-		check_and_free_fields(array, val);
+		bpf_obj_free_fields(array->map.record, val);
 	} else {
 		val = array->value +
 			(u64)array->elem_size * (index & array->index_mask);
@@ -348,7 +341,7 @@ static int array_map_update_elem(struct bpf_map *map, void *key, void *value,
 			copy_map_value_locked(map, val, value, false);
 		else
 			copy_map_value(map, val, value);
-		check_and_free_fields(array, val);
+		bpf_obj_free_fields(array->map.record, val);
 	}
 	return 0;
 }
@@ -385,7 +378,7 @@ int bpf_percpu_array_update(struct bpf_map *map, void *key, void *value,
 	pptr = array->pptrs[index & array->index_mask];
 	for_each_possible_cpu(cpu) {
 		copy_map_value_long(map, per_cpu_ptr(pptr, cpu), value + off);
-		check_and_free_fields(array, per_cpu_ptr(pptr, cpu));
+		bpf_obj_free_fields(array->map.record, per_cpu_ptr(pptr, cpu));
 		off += size;
 	}
 	rcu_read_unlock();
@@ -409,11 +402,11 @@ static void array_map_free_timers(struct bpf_map *map)
 	int i;
 
 	/* We don't reset or free fields other than timer on uref dropping to zero. */
-	if (!map_value_has_timer(map))
+	if (!btf_record_has_field(map->record, BPF_TIMER))
 		return;
 
 	for (i = 0; i < array->map.max_entries; i++)
-		bpf_timer_cancel_and_free(array_map_elem_ptr(array, i) + map->timer_off);
+		bpf_obj_free_timer(map->record, array_map_elem_ptr(array, i));
 }
 
 /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
kernel/bpf/bpf_local_storage.c +1 -1
index 93d9b1b17bc8..37020078d1c1 100644
@@ -382,7 +382,7 @@ bpf_local_storage_update(void *owner, struct bpf_local_storage_map *smap,
 	if (unlikely((map_flags & ~BPF_F_LOCK) > BPF_EXIST) ||
 	    /* BPF_F_LOCK can only be used in a value with spin_lock */
 	    unlikely((map_flags & BPF_F_LOCK) &&
-		     !map_value_has_spin_lock(&smap->map)))
+		     !btf_record_has_field(smap->map.record, BPF_SPIN_LOCK)))
 		return ERR_PTR(-EINVAL);
 
 	if (gfp_flags == GFP_KERNEL && (map_flags & ~BPF_F_LOCK) != BPF_NOEXIST)
kernel/bpf/btf.c +178 -147

434 lines not on this page · raw message

kernel/bpf/hashtab.c +8 -16
index c5ea8f9bb7a9..50d254cd0709 100644
@@ -222,7 +222,7 @@ static void htab_free_prealloced_timers(struct bpf_htab *htab)
 	u32 num_entries = htab->map.max_entries;
 	int i;
 
-	if (!map_value_has_timer(&htab->map))
+	if (!btf_record_has_field(htab->map.record, BPF_TIMER))
 		return;
 	if (htab_has_extra_elems(htab))
 		num_entries += num_possible_cpus();
@@ -231,9 +231,7 @@ static void htab_free_prealloced_timers(struct bpf_htab *htab)
 		struct htab_elem *elem;
 
 		elem = get_htab_elem(htab, i);
-		bpf_timer_cancel_and_free(elem->key +
-					  round_up(htab->map.key_size, 8) +
-					  htab->map.timer_off);
+		bpf_obj_free_timer(htab->map.record, elem->key + round_up(htab->map.key_size, 8));
 		cond_resched();
 	}
 }
@@ -763,8 +761,6 @@ static void check_and_free_fields(struct bpf_htab *htab,
 {
 	void *map_value = elem->key + round_up(htab->map.key_size, 8);
 
-	if (map_value_has_timer(&htab->map))
-		bpf_timer_cancel_and_free(map_value + htab->map.timer_off);
 	bpf_obj_free_fields(htab->map.record, map_value);
 }
 
@@ -1089,7 +1085,7 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value,
 	head = &b->head;
 
 	if (unlikely(map_flags & BPF_F_LOCK)) {
-		if (unlikely(!map_value_has_spin_lock(map)))
+		if (unlikely(!btf_record_has_field(map->record, BPF_SPIN_LOCK)))
 			return -EINVAL;
 		/* find an element without taking the bucket lock */
 		l_old = lookup_nulls_elem_raw(head, hash, key, key_size,
@@ -1472,12 +1468,8 @@ static void htab_free_malloced_timers(struct bpf_htab *htab)
 		struct htab_elem *l;
 
 		hlist_nulls_for_each_entry(l, n, head, hash_node) {
-			/* We don't reset or free kptr on uref dropping to zero,
-			 * hence just free timer.
-			 */
-			bpf_timer_cancel_and_free(l->key +
-						  round_up(htab->map.key_size, 8) +
-						  htab->map.timer_off);
+			/* We only free timer on uref dropping to zero */
+			bpf_obj_free_timer(htab->map.record, l->key + round_up(htab->map.key_size, 8));
 		}
 		cond_resched_rcu();
 	}
@@ -1488,8 +1480,8 @@ static void htab_map_free_timers(struct bpf_map *map)
 {
 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
 
-	/* We don't reset or free kptr on uref dropping to zero. */
-	if (!map_value_has_timer(&htab->map))
+	/* We only free timer on uref dropping to zero */
+	if (!btf_record_has_field(htab->map.record, BPF_TIMER))
 		return;
 	if (!htab_is_prealloc(htab))
 		htab_free_malloced_timers(htab);
@@ -1673,7 +1665,7 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
 
 	elem_map_flags = attr->batch.elem_flags;
 	if ((elem_map_flags & ~BPF_F_LOCK) ||
-	    ((elem_map_flags & BPF_F_LOCK) && !map_value_has_spin_lock(map)))
+	    ((elem_map_flags & BPF_F_LOCK) && !btf_record_has_field(map->record, BPF_SPIN_LOCK)))
 		return -EINVAL;
 
 	map_flags = attr->batch.flags;
kernel/bpf/helpers.c +3 -3
index 124fd199ce5c..283f55bbeb70 100644
@@ -366,9 +366,9 @@ void copy_map_value_locked(struct bpf_map *map, void *dst, void *src,
 	struct bpf_spin_lock *lock;
 
 	if (lock_src)
-		lock = src + map->spin_lock_off;
+		lock = src + map->record->spin_lock_off;
 	else
-		lock = dst + map->spin_lock_off;
+		lock = dst + map->record->spin_lock_off;
 	preempt_disable();
 	__bpf_spin_lock_irqsave(lock);
 	copy_map_value(map, dst, src);
@@ -1169,7 +1169,7 @@ BPF_CALL_3(bpf_timer_init, struct bpf_timer_kern *, timer, struct bpf_map *, map
 		ret = -ENOMEM;
 		goto out;
 	}
-	t->value = (void *)timer - map->timer_off;
+	t->value = (void *)timer - map->record->timer_off;
 	t->map = map;
 	t->prog = NULL;
 	rcu_assign_pointer(t->callback_fn, NULL);
kernel/bpf/local_storage.c +1 -1
index 098cf336fae6..e90d9f63edc5 100644
@@ -151,7 +151,7 @@ static int cgroup_storage_update_elem(struct bpf_map *map, void *key,
 		return -EINVAL;
 
 	if (unlikely((flags & BPF_F_LOCK) &&
-		     !map_value_has_spin_lock(map)))
+		     !btf_record_has_field(map->record, BPF_SPIN_LOCK)))
 		return -EINVAL;
 
 	storage = cgroup_storage_lookup((struct bpf_cgroup_storage_map *)map,
kernel/bpf/map_in_map.c +1 -4
index d6c662183f88..8ca0cca39d49 100644
@@ -29,7 +29,7 @@ struct bpf_map *bpf_map_meta_alloc(int inner_map_ufd)
 		return ERR_PTR(-ENOTSUPP);
 	}
 
-	if (map_value_has_spin_lock(inner_map)) {
+	if (btf_record_has_field(inner_map->record, BPF_SPIN_LOCK)) {
 		fdput(f);
 		return ERR_PTR(-ENOTSUPP);
 	}
@@ -50,8 +50,6 @@ struct bpf_map *bpf_map_meta_alloc(int inner_map_ufd)
 	inner_map_meta->value_size = inner_map->value_size;
 	inner_map_meta->map_flags = inner_map->map_flags;
 	inner_map_meta->max_entries = inner_map->max_entries;
-	inner_map_meta->spin_lock_off = inner_map->spin_lock_off;
-	inner_map_meta->timer_off = inner_map->timer_off;
 	inner_map_meta->record = btf_record_dup(inner_map->record);
 	if (IS_ERR(inner_map_meta->record)) {
 		/* btf_record_dup returns NULL or valid pointer in case of
@@ -92,7 +90,6 @@ bool bpf_map_meta_equal(const struct bpf_map *meta0,
 	return meta0->map_type == meta1->map_type &&
 		meta0->key_size == meta1->key_size &&
 		meta0->value_size == meta1->value_size &&
-		meta0->timer_off == meta1->timer_off &&
 		meta0->map_flags == meta1->map_flags &&
 		btf_record_equal(meta0->record, meta1->record);
 }
kernel/bpf/syscall.c +59 -74

239 lines not on this page · raw message

kernel/bpf/verifier.c +21 -61

153 lines not on this page · raw message

net/core/bpf_sk_storage.c +2 -2
index 49884e7de080..9d2288c0736e 100644
@@ -147,7 +147,7 @@ bpf_sk_storage_clone_elem(struct sock *newsk,
 	if (!copy_selem)
 		return NULL;
 
-	if (map_value_has_spin_lock(&smap->map))
+	if (btf_record_has_field(smap->map.record, BPF_SPIN_LOCK))
 		copy_map_value_locked(&smap->map, SDATA(copy_selem)->data,
 				      SDATA(selem)->data, true);
 	else
@@ -566,7 +566,7 @@ static int diag_get(struct bpf_local_storage_data *sdata, struct sk_buff *skb)
 	if (!nla_value)
 		goto errout;
 
-	if (map_value_has_spin_lock(&smap->map))
+	if (btf_record_has_field(smap->map.record, BPF_SPIN_LOCK))
 		copy_map_value_locked(&smap->map, nla_data(nla_value),
 				      sdata->data, true);
 	else
Signature · 1 line
2.38.1
#19 lore raw

Re: [PATCH bpf-next v4 07/24] bpf: Consolidate spin_lock, timer management into btf_record

Quoted 3 lines · Kumar Kartikeya Dwivedi
+               rec->field_mask |= info_arr[i].type;
                rec->fields[i].offset = info_arr[i].off;
                rec->fields[i].type = info_arr[i].type;

I spent an hour to figure out that this hunk should have been in the previous commit. Sigh.

Anyway, I fixed all the bugs I found in the patch 6 and pushed the first 6 patches, since we really need to make progress here quickly.
Too many people are waiting on this set.

#20 lore raw

Re: [PATCH bpf-next v4 07/24] bpf: Consolidate spin_lock, timer management into btf_record

In reply to Kumar Kartikeya Dwivedi
Quoted 38 lines · Kumar Kartikeya Dwivedi

static int bpf_map_alloc_off_arr(struct bpf_map *map) {

kernel/bpf/syscall.c +4 -22
-       bool has_spin_lock = map_value_has_spin_lock(map);
-       bool has_timer = map_value_has_timer(map);
        bool has_fields = !IS_ERR_OR_NULL(map);
        struct btf_field_offs *fo;
-       u32 i;
+       struct btf_record *rec;
+       u32 i, *off;
+       u8 *sz;
 
-       if (!has_spin_lock && !has_timer && !has_fields) {
+       if (!has_fields) {
                map->field_offs = NULL;
                return 0;
        }
@@ -970,32 +987,14 @@ static int bpf_map_alloc_off_arr(struct bpf_map *map)
                return -ENOMEM;
        map->field_offs = fo;
 
-       fo->cnt = 0;
-       if (has_spin_lock) {
-               i = fo->cnt;
-
-               fo->field_off[i] = map->spin_lock_off;
-               fo->field_sz[i] = sizeof(struct bpf_spin_lock);
-               fo->cnt++;
-       }
-       if (has_timer) {
-               i = fo->cnt;
-
-               fo->field_off[i] = map->timer_off;
-               fo->field_sz[i] = sizeof(struct bpf_timer);
-               fo->cnt++;
-       }
-       if (has_fields) {
-               struct btf_record *rec = map->record;
-               u32 *off = &fo->field_off[fo->cnt];

kernel/bpf/syscall.c static int bpf_map_alloc_off_arr(struct bpf_map *map) · line 992

Quoted 10 lines
kernel/bpf/syscall.c +3 -7
-               u8 *sz = &fo->field_sz[fo->cnt];
-
-               for (i = 0; i < rec->cnt; i++) {
-                       *off++ = rec->fields[i].offset;
-                       *sz++ = btf_field_type_size(rec->fields[i].type);
-               }
-               fo->cnt += rec->cnt;
+       rec = map->record;
+       off = &fo->field_off[fo->cnt];
+       sz = &fo->field_sz[fo->cnt];

Another bug that would have been obvious if you run any tests. (fo->cnt contains garbage)

I'm surprised by the amount of issues in the series.

kernel/bpf/syscall.c static int bpf_map_alloc_off_arr(struct bpf_map *map) · line 996

Quoted 4 lines
kernel/bpf/syscall.c +3 -0
+       for (i = 0; i < rec->cnt; i++) {
+               *off++ = rec->fields[i].offset;
+               *sz++ = btf_field_type_size(rec->fields[i].type);
        }

Anyway, pushed this patch as well after fixing this bug.

author maintainer
#21 lore raw

Re: [PATCH bpf-next v4 07/24] bpf: Consolidate spin_lock, timer management into btf_record

Quoted 54 lines · Alexei Starovoitov
Quoted 38 lines · Kumar Kartikeya Dwivedi

static int bpf_map_alloc_off_arr(struct bpf_map *map) {

kernel/bpf/syscall.c +4 -22
-       bool has_spin_lock = map_value_has_spin_lock(map);
-       bool has_timer = map_value_has_timer(map);
        bool has_fields = !IS_ERR_OR_NULL(map);
        struct btf_field_offs *fo;
-       u32 i;
+       struct btf_record *rec;
+       u32 i, *off;
+       u8 *sz;
 
-       if (!has_spin_lock && !has_timer && !has_fields) {
+       if (!has_fields) {
                map->field_offs = NULL;
                return 0;
        }
@@ -970,32 +987,14 @@ static int bpf_map_alloc_off_arr(struct bpf_map *map)
                return -ENOMEM;
        map->field_offs = fo;
 
-       fo->cnt = 0;
-       if (has_spin_lock) {
-               i = fo->cnt;
-
-               fo->field_off[i] = map->spin_lock_off;
-               fo->field_sz[i] = sizeof(struct bpf_spin_lock);
-               fo->cnt++;
-       }
-       if (has_timer) {
-               i = fo->cnt;
-
-               fo->field_off[i] = map->timer_off;
-               fo->field_sz[i] = sizeof(struct bpf_timer);
-               fo->cnt++;
-       }
-       if (has_fields) {
-               struct btf_record *rec = map->record;
-               u32 *off = &fo->field_off[fo->cnt];

kernel/bpf/syscall.c static int bpf_map_alloc_off_arr(struct bpf_map *map) · line 992

Quoted 10 lines
kernel/bpf/syscall.c +3 -7
-               u8 *sz = &fo->field_sz[fo->cnt];
-
-               for (i = 0; i < rec->cnt; i++) {
-                       *off++ = rec->fields[i].offset;
-                       *sz++ = btf_field_type_size(rec->fields[i].type);
-               }
-               fo->cnt += rec->cnt;
+       rec = map->record;
+       off = &fo->field_off[fo->cnt];
+       sz = &fo->field_sz[fo->cnt];

Another bug that would have been obvious if you run any tests. (fo->cnt contains garbage)

Quoted 2 lines

I'm surprised by the amount of issues in the series.

It's my bad, I deleted what was fo->cnt very recently and didn't give this a run again, without realizing it's only the next patch that does kmalloc -> kzalloc.

author maintainer
#22 lore raw

Re: [PATCH bpf-next v4 07/24] bpf: Consolidate spin_lock, timer management into btf_record

Quoted 55 lines · Kumar Kartikeya Dwivedi
Quoted 54 lines · Alexei Starovoitov
Quoted 38 lines · Kumar Kartikeya Dwivedi

static int bpf_map_alloc_off_arr(struct bpf_map *map) {

kernel/bpf/syscall.c +4 -22
-       bool has_spin_lock = map_value_has_spin_lock(map);
-       bool has_timer = map_value_has_timer(map);
        bool has_fields = !IS_ERR_OR_NULL(map);
        struct btf_field_offs *fo;
-       u32 i;
+       struct btf_record *rec;
+       u32 i, *off;
+       u8 *sz;
 
-       if (!has_spin_lock && !has_timer && !has_fields) {
+       if (!has_fields) {
                map->field_offs = NULL;
                return 0;
        }
@@ -970,32 +987,14 @@ static int bpf_map_alloc_off_arr(struct bpf_map *map)
                return -ENOMEM;
        map->field_offs = fo;
 
-       fo->cnt = 0;
-       if (has_spin_lock) {
-               i = fo->cnt;
-
-               fo->field_off[i] = map->spin_lock_off;
-               fo->field_sz[i] = sizeof(struct bpf_spin_lock);
-               fo->cnt++;
-       }
-       if (has_timer) {
-               i = fo->cnt;
-
-               fo->field_off[i] = map->timer_off;
-               fo->field_sz[i] = sizeof(struct bpf_timer);
-               fo->cnt++;
-       }
-       if (has_fields) {
-               struct btf_record *rec = map->record;
-               u32 *off = &fo->field_off[fo->cnt];

kernel/bpf/syscall.c static int bpf_map_alloc_off_arr(struct bpf_map *map) · line 992

Quoted 10 lines
kernel/bpf/syscall.c +3 -7
-               u8 *sz = &fo->field_sz[fo->cnt];
-
-               for (i = 0; i < rec->cnt; i++) {
-                       *off++ = rec->fields[i].offset;
-                       *sz++ = btf_field_type_size(rec->fields[i].type);
-               }
-               fo->cnt += rec->cnt;
+       rec = map->record;
+       off = &fo->field_off[fo->cnt];
+       sz = &fo->field_sz[fo->cnt];

Another bug that would have been obvious if you run any tests. (fo->cnt contains garbage)

Quoted 4 lines
Quoted 2 lines

I'm surprised by the amount of issues in the series.

It's my bad, I deleted what was fo->cnt very recently and didn't give this a run

deleted

Quoted 1 line
Quoted 1 line
Quoted 1 line
kernel/bpf/syscall.c +0 -1
-       fo->cnt = 0;
author maintainer
#23 lore raw

PATCH v4 8/24 bpf: Refactor map->off_arr handling

In reply to Kumar Kartikeya Dwivedi

Refactor map->off_arr handling into generic functions that can work on their own without hardcoding map specific code. The btf_fields_offs structure is now returned from btf_parse_field_offs, which can be reused later for types in program BTF.

All functions like copy_map_value, zero_map_value call generic underlying functions so that they can also be reused later for copying to values allocated in programs which encode specific fields.

Later, some helper functions will also require access to this btf_field_offs structure to be able to skip over special fields at runtime.

---
 include/linux/bpf.h  | 41 ++++++++++++++-----------
 include/linux/btf.h  |  1 +
 kernel/bpf/btf.c     | 55 +++++++++++++++++++++++++++++++++
 kernel/bpf/syscall.c | 73 ++++++--------------------------------------
 4 files changed, 89 insertions(+), 81 deletions(-)
include/linux/bpf.h +24 -17
index d5c81b09577a..bb96bf947e53 100644
@@ -341,57 +341,64 @@ static inline void bpf_long_memcpy(void *dst, const void *src, u32 size)
 }
 
 /* copy everything but bpf_spin_lock, bpf_timer, and kptrs. There could be one of each. */
-static inline void __copy_map_value(struct bpf_map *map, void *dst, void *src, bool long_memcpy)
+static inline void bpf_obj_memcpy(struct btf_field_offs *foffs,
+				  void *dst, void *src, u32 size,
+				  bool long_memcpy)
 {
 	u32 curr_off = 0;
 	int i;
 
-	if (likely(!map->field_offs)) {
+	if (likely(!foffs)) {
 		if (long_memcpy)
-			bpf_long_memcpy(dst, src, round_up(map->value_size, 8));
+			bpf_long_memcpy(dst, src, round_up(size, 8));
 		else
-			memcpy(dst, src, map->value_size);
+			memcpy(dst, src, size);
 		return;
 	}
 
-	for (i = 0; i < map->field_offs->cnt; i++) {
-		u32 next_off = map->field_offs->field_off[i];
+	for (i = 0; i < foffs->cnt; i++) {
+		u32 next_off = foffs->field_off[i];
 		u32 sz = next_off - curr_off;
 
 		memcpy(dst + curr_off, src + curr_off, sz);
-		curr_off += map->field_offs->field_sz[i] + sz;
+		curr_off += foffs->field_sz[i] + sz;
 	}
-	memcpy(dst + curr_off, src + curr_off, map->value_size - curr_off);
+	memcpy(dst + curr_off, src + curr_off, size - curr_off);
 }
 
 static inline void copy_map_value(struct bpf_map *map, void *dst, void *src)
 {
-	__copy_map_value(map, dst, src, false);
+	bpf_obj_memcpy(map->field_offs, dst, src, map->value_size, false);
 }
 
 static inline void copy_map_value_long(struct bpf_map *map, void *dst, void *src)
 {
-	__copy_map_value(map, dst, src, true);
+	bpf_obj_memcpy(map->field_offs, dst, src, map->value_size, true);
 }
 
-static inline void zero_map_value(struct bpf_map *map, void *dst)
+static inline void bpf_obj_memzero(struct btf_field_offs *foffs, void *dst, u32 size)
 {
 	u32 curr_off = 0;
 	int i;
 
-	if (likely(!map->field_offs)) {
-		memset(dst, 0, map->value_size);
+	if (likely(!foffs)) {
+		memset(dst, 0, size);
 		return;
 	}
 
-	for (i = 0; i < map->field_offs->cnt; i++) {
-		u32 next_off = map->field_offs->field_off[i];
+	for (i = 0; i < foffs->cnt; i++) {
+		u32 next_off = foffs->field_off[i];
 		u32 sz = next_off - curr_off;
 
 		memset(dst + curr_off, 0, sz);
-		curr_off += map->field_offs->field_sz[i] + sz;
+		curr_off += foffs->field_sz[i] + sz;
 	}
-	memset(dst + curr_off, 0, map->value_size - curr_off);
+	memset(dst + curr_off, 0, size - curr_off);
+}
+
+static inline void zero_map_value(struct bpf_map *map, void *dst)
+{
+	bpf_obj_memzero(map->field_offs, dst, map->value_size);
 }
 
 void copy_map_value_locked(struct bpf_map *map, void *dst, void *src,
include/linux/btf.h +1 -0
index 282006abd062..d80345fa566b 100644
@@ -165,6 +165,7 @@ int btf_find_spin_lock(const struct btf *btf, const struct btf_type *t);
 int btf_find_timer(const struct btf *btf, const struct btf_type *t);
 struct btf_record *btf_parse_fields(const struct btf *btf, const struct btf_type *t,
 				    u32 field_mask, u32 value_size);
+struct btf_field_offs *btf_parse_field_offs(struct btf_record *rec);
 bool btf_type_is_void(const struct btf_type *t);
 s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind);
 const struct btf_type *btf_type_skip_modifiers(const struct btf *btf,
kernel/bpf/btf.c +55 -0

61 lines not on this page · raw message

kernel/bpf/syscall.c +9 -64

101 lines not on this page · raw message

Signature · 1 line
2.38.1
author maintainer
#24 lore raw

PATCH v4 9/24 bpf: Support bpf_list_head in map values

In reply to Kumar Kartikeya Dwivedi

Add the basic support on the map side to parse, recognize, verify, and build metadata table for a new special field of the type struct bpf_list_head. To parameterize the bpf_list_head for a certain value type and the list_node member it will accept in that value type, we use BTF declaration tags.

The definition of bpf_list_head in a map value will be done as follows:

struct foo {
	struct bpf_list_node node;
	int data;
};
struct map_value {
	struct bpf_list_head head __contains(foo, node);
};

Then, the bpf_list_head only allows adding to the list 'head' using the bpf_list_node 'node' for the type struct foo.

The 'contains' annotation is a BTF declaration tag composed of four parts, "contains:name:node" where the name is then used to look up the type in the map BTF, with its kind hardcoded to BTF_KIND_STRUCT during the lookup. The node defines name of the member in this type that has the type struct bpf_list_node, which is actually used for linking into the linked list. For now, 'kind' part is hardcoded as struct.

This allows building intrusive linked lists in BPF, using container_of to obtain pointer to entry, while being completely type safe from the perspective of the verifier. The verifier knows exactly the type of the nodes, and knows that list helpers return that type at some fixed offset where the bpf_list_node member used for this list exists. The verifier also uses this information to disallow adding types that are not accepted by a certain list.

For now, no elements can be added to such lists. Support for that is coming in future patches, hence draining and freeing items is done with a TODO that will be resolved in a future patch.

---
 include/linux/bpf.h            |  17 ++++
 include/uapi/linux/bpf.h       |  10 +++
 kernel/bpf/btf.c               | 144 ++++++++++++++++++++++++++++++++-
 kernel/bpf/helpers.c           |  32 ++++++++
 kernel/bpf/syscall.c           |  22 ++++-
 kernel/bpf/verifier.c          |   7 ++
 tools/include/uapi/linux/bpf.h |  10 +++
 7 files changed, 238 insertions(+), 4 deletions(-)
include/linux/bpf.h +17 -0
index bb96bf947e53..2d9ebe9efcad 100644
@@ -176,6 +176,7 @@ enum btf_field_type {
 	BPF_KPTR_UNREF = (1 << 2),
 	BPF_KPTR_REF   = (1 << 3),
 	BPF_KPTR       = BPF_KPTR_UNREF | BPF_KPTR_REF,
+	BPF_LIST_HEAD  = (1 << 4),
 };
 
 struct btf_field_kptr {
@@ -185,11 +186,18 @@ struct btf_field_kptr {
 	u32 btf_id;
 };
 
+struct btf_field_list_head {
+	struct btf *btf;
+	u32 value_btf_id;
+	u32 node_offset;
+};
+
 struct btf_field {
 	u32 offset;
 	enum btf_field_type type;
 	union {
 		struct btf_field_kptr kptr;
+		struct btf_field_list_head list_head;
 	};
 };
 
@@ -267,6 +275,8 @@ static inline const char *btf_field_type_name(enum btf_field_type type)
 	case BPF_KPTR_UNREF:
 	case BPF_KPTR_REF:
 		return "kptr";
+	case BPF_LIST_HEAD:
+		return "bpf_list_head";
 	default:
 		WARN_ON_ONCE(1);
 		return "unknown";
@@ -283,6 +293,8 @@ static inline u32 btf_field_type_size(enum btf_field_type type)
 	case BPF_KPTR_UNREF:
 	case BPF_KPTR_REF:
 		return sizeof(u64);
+	case BPF_LIST_HEAD:
+		return sizeof(struct bpf_list_head);
 	default:
 		WARN_ON_ONCE(1);
 		return 0;
@@ -299,6 +311,8 @@ static inline u32 btf_field_type_align(enum btf_field_type type)
 	case BPF_KPTR_UNREF:
 	case BPF_KPTR_REF:
 		return __alignof__(u64);
+	case BPF_LIST_HEAD:
+		return __alignof__(struct bpf_list_head);
 	default:
 		WARN_ON_ONCE(1);
 		return 0;
@@ -404,6 +418,9 @@ static inline void zero_map_value(struct bpf_map *map, void *dst)
 void copy_map_value_locked(struct bpf_map *map, void *dst, void *src,
 			   bool lock_src);
 void bpf_timer_cancel_and_free(void *timer);
+void bpf_list_head_free(const struct btf_field *field, void *list_head,
+			struct bpf_spin_lock *spin_lock);
+
 int bpf_obj_name_cpy(char *dst, const char *src, unsigned int size);
 
 struct bpf_offload_dev;
include/uapi/linux/bpf.h +10 -0
index 94659f6b3395..dd381086bad9 100644
@@ -6887,6 +6887,16 @@ struct bpf_dynptr {
 	__u64 :64;
 } __attribute__((aligned(8)));
 
+struct bpf_list_head {
+	__u64 :64;
+	__u64 :64;
+} __attribute__((aligned(8)));
+
+struct bpf_list_node {
+	__u64 :64;
+	__u64 :64;
+} __attribute__((aligned(8)));
+
 struct bpf_sysctl {
 	__u32	write;		/* Sysctl is being read (= 0) or written (= 1).
 				 * Allows 1,2,4-byte read, but no write.
kernel/bpf/btf.c +141 -3

204 lines not on this page · raw message

kernel/bpf/helpers.c +32 -0
index 283f55bbeb70..339cce94b408 100644
@@ -1706,6 +1706,38 @@ bpf_base_func_proto(enum bpf_func_id func_id)
 	}
 }
 
+void bpf_list_head_free(const struct btf_field *field, void *list_head,
+			struct bpf_spin_lock *spin_lock)
+{
+	struct list_head *head = list_head, *orig_head = head;
+	unsigned long flags;
+
+	BUILD_BUG_ON(sizeof(struct list_head) > sizeof(struct bpf_list_head));
+	BUILD_BUG_ON(__alignof__(struct list_head) > __alignof__(struct bpf_list_head));
+
+	/* __bpf_spin_lock_irqsave cannot be used here, as we may take a spin
+	 * lock again when we call bpf_obj_free_fields in the loop, and it will
+	 * overwrite the per-CPU local_irq_save state.
+	 */
+	local_irq_save(flags);
+	__bpf_spin_lock(spin_lock);
+	if (!head->next || list_empty(head))
+		goto unlock;
+	head = head->next;
+	while (head != orig_head) {
+		void *obj = head;
+
+		obj -= field->list_head.node_offset;
+		head = head->next;
+		/* TODO: Rework later */
+		kfree(obj);
+	}
+unlock:
+	INIT_LIST_HEAD(head);
+	__bpf_spin_unlock(spin_lock);
+	local_irq_restore(flags);
+}
+
 BTF_SET8_START(tracing_btf_ids)
 #ifdef CONFIG_KEXEC_CORE
 BTF_ID_FLAGS(func, crash_kexec, KF_DESTRUCTIVE)
kernel/bpf/syscall.c +21 -1
index 85532d301124..fdbae52f463f 100644
@@ -536,6 +536,9 @@ void btf_record_free(struct btf_record *rec)
 				module_put(rec->fields[i].kptr.module);
 			btf_put(rec->fields[i].kptr.btf);
 			break;
+		case BPF_LIST_HEAD:
+			/* Nothing to release for bpf_list_head */
+			break;
 		default:
 			WARN_ON_ONCE(1);
 			continue;
@@ -578,6 +581,9 @@ struct btf_record *btf_record_dup(const struct btf_record *rec)
 				goto free;
 			}
 			break;
+		case BPF_LIST_HEAD:
+			/* Nothing to acquire for bpf_list_head */
+			break;
 		default:
 			ret = -EFAULT;
 			WARN_ON_ONCE(1);
@@ -637,6 +643,11 @@ void bpf_obj_free_fields(const struct btf_record *rec, void *obj)
 		case BPF_KPTR_REF:
 			field->kptr.dtor((void *)xchg((unsigned long *)field_ptr, 0));
 			break;
+		case BPF_LIST_HEAD:
+			if (WARN_ON_ONCE(rec->spin_lock_off < 0))
+				continue;
+			bpf_list_head_free(field, field_ptr, obj + rec->spin_lock_off);
+			break;
 		default:
 			WARN_ON_ONCE(1);
 			continue;
@@ -965,7 +976,8 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf,
 	if (!value_type || value_size != map->value_size)
 		return -EINVAL;
 
-	map->record = btf_parse_fields(btf, value_type, BPF_SPIN_LOCK | BPF_TIMER | BPF_KPTR,
+	map->record = btf_parse_fields(btf, value_type,
+				       BPF_SPIN_LOCK | BPF_TIMER | BPF_KPTR | BPF_LIST_HEAD,
 				       map->value_size);
 	if (!IS_ERR_OR_NULL(map->record)) {
 		int i;
@@ -1012,6 +1024,14 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf,
 					goto free_map_tab;
 				}
 				break;
+			case BPF_LIST_HEAD:
+				if (map->map_type != BPF_MAP_TYPE_HASH &&
+				    map->map_type != BPF_MAP_TYPE_LRU_HASH &&
+				    map->map_type != BPF_MAP_TYPE_ARRAY) {
+					ret = -EOPNOTSUPP;
+					goto free_map_tab;
+				}
+				break;
 			default:
 				/* Fail if map_type checks are missing for a field type */
 				ret = -EOPNOTSUPP;
kernel/bpf/verifier.c +7 -0
index 73a3516f1a48..168cd8bb9fd6 100644
@@ -12643,6 +12643,13 @@ static int check_map_prog_compatibility(struct bpf_verifier_env *env,
 		}
 	}
 
+	if (btf_record_has_field(map->record, BPF_LIST_HEAD)) {
+		if (is_tracing_prog_type(prog_type)) {
+			verbose(env, "tracing progs cannot use bpf_list_head yet\n");
+			return -EINVAL;
+		}
+	}
+
 	if ((bpf_prog_is_dev_bound(prog->aux) || bpf_map_is_dev_bound(map)) &&
 	    !bpf_offload_prog_map_match(prog, map)) {
 		verbose(env, "offload device mismatch between prog and map\n");
tools/include/uapi/linux/bpf.h +10 -0
index 94659f6b3395..dd381086bad9 100644
@@ -6887,6 +6887,16 @@ struct bpf_dynptr {
 	__u64 :64;
 } __attribute__((aligned(8)));
 
+struct bpf_list_head {
+	__u64 :64;
+	__u64 :64;
+} __attribute__((aligned(8)));
+
+struct bpf_list_node {
+	__u64 :64;
+	__u64 :64;
+} __attribute__((aligned(8)));
+
 struct bpf_sysctl {
 	__u32	write;		/* Sysctl is being read (= 0) or written (= 1).
 				 * Allows 1,2,4-byte read, but no write.
Signature · 1 line
2.38.1
author maintainer
#25 lore raw

PATCH v4 10/24 bpf: Introduce local kptrs

In reply to Kumar Kartikeya Dwivedi

Introduce local kptrs, i.e. PTR_TO_BTF_ID that point to a type in program BTF. This is indicated by the presence of MEM_TYPE_LOCAL type tag in reg->type to avoid having to check btf_is_kernel when trying to match argument types in helpers.

Refactor btf_struct_access callback to just take bpf_reg_state instead of btf and btf_type paramters. Note that the call site in check_map_access now simulates access to a PTR_TO_BTF_ID by creating a dummy reg on stack. Since only the type, btf, and btf_id of the register matter for the checks, it can be done so without complicating the usual cases elsewhere in the verifier where reg->btf and reg->btf_id is used verbatim.

For now, these local kptrs will always be referenced in verifier context, hence ref_obj_id == 0 for them is a bug. It is allowed to write to such objects, as long fields that are special are not touched (support for which will be added in subsequent patches). Note that once such a local kptr is marked PTR_UNTRUSTED, it is no longer allowed to write to it.

No PROBE_MEM handling is hence done unless PTR_UNTRUSTED is part of the register type, since they can never be in an undefined state otherwise, and their lifetime will always be valid.

---
 include/linux/bpf.h              | 28 ++++++++++++++++--------
 include/linux/filter.h           |  8 +++----
 kernel/bpf/btf.c                 | 16 ++++++++++----
 kernel/bpf/verifier.c            | 37 ++++++++++++++++++++++++++------
 net/bpf/bpf_dummy_struct_ops.c   | 14 ++++++------
 net/core/filter.c                | 34 ++++++++++++-----------------
 net/ipv4/bpf_tcp_ca.c            | 13 ++++++-----
 net/netfilter/nf_conntrack_bpf.c | 17 ++++++---------
 8 files changed, 99 insertions(+), 68 deletions(-)
include/linux/bpf.h +19 -9
index 2d9ebe9efcad..bdd3adfcbe5f 100644
@@ -527,6 +527,11 @@ enum bpf_type_flag {
 	/* Size is known at compile time. */
 	MEM_FIXED_SIZE		= BIT(10 + BPF_BASE_TYPE_BITS),
 
+	/* MEM is of a type from program BTF, not kernel BTF. This is used to
+	 * tag PTR_TO_BTF_ID allocated using bpf_kptr_alloc.
+	 */
+	MEM_TYPE_LOCAL		= BIT(11 + BPF_BASE_TYPE_BITS),
+
 	__BPF_TYPE_FLAG_MAX,
 	__BPF_TYPE_LAST_FLAG	= __BPF_TYPE_FLAG_MAX - 1,
 };
@@ -775,6 +780,7 @@ struct bpf_prog_ops {
 			union bpf_attr __user *uattr);
 };
 
+struct bpf_reg_state;
 struct bpf_verifier_ops {
 	/* return eBPF function prototype for verification */
 	const struct bpf_func_proto *
@@ -796,9 +802,8 @@ struct bpf_verifier_ops {
 				  struct bpf_insn *dst,
 				  struct bpf_prog *prog, u32 *target_size);
 	int (*btf_struct_access)(struct bpf_verifier_log *log,
-				 const struct btf *btf,
-				 const struct btf_type *t, int off, int size,
-				 enum bpf_access_type atype,
+				 const struct bpf_reg_state *reg,
+				 int off, int size, enum bpf_access_type atype,
 				 u32 *next_btf_id, enum bpf_type_flag *flag);
 };
 
@@ -2084,9 +2089,9 @@ static inline bool bpf_tracing_btf_ctx_access(int off, int size,
 	return btf_ctx_access(off, size, type, prog, info);
 }
 
-int btf_struct_access(struct bpf_verifier_log *log, const struct btf *btf,
-		      const struct btf_type *t, int off, int size,
-		      enum bpf_access_type atype,
+int btf_struct_access(struct bpf_verifier_log *log,
+		      const struct bpf_reg_state *reg,
+		      int off, int size, enum bpf_access_type atype,
 		      u32 *next_btf_id, enum bpf_type_flag *flag);
 bool btf_struct_ids_match(struct bpf_verifier_log *log,
 			  const struct btf *btf, u32 id, int off,
@@ -2337,9 +2342,8 @@ static inline struct bpf_prog *bpf_prog_by_id(u32 id)
 }
 
 static inline int btf_struct_access(struct bpf_verifier_log *log,
-				    const struct btf *btf,
-				    const struct btf_type *t, int off, int size,
-				    enum bpf_access_type atype,
+				    const struct bpf_reg_state *reg,
+				    int off, int size, enum bpf_access_type atype,
 				    u32 *next_btf_id, enum bpf_type_flag *flag)
 {
 	return -EACCES;
@@ -2796,4 +2800,10 @@ struct bpf_key {
 	bool has_ref;
 };
 #endif /* CONFIG_KEYS */
+
+static inline bool type_is_local_kptr(u32 type)
+{
+	return type & MEM_TYPE_LOCAL;
+}
+
 #endif /* _LINUX_BPF_H */
include/linux/filter.h +4 -4
index efc42a6e3aed..787d35dbf5b0 100644
@@ -568,10 +568,10 @@ struct sk_filter {
 DECLARE_STATIC_KEY_FALSE(bpf_stats_enabled_key);
 
 extern struct mutex nf_conn_btf_access_lock;
-extern int (*nfct_btf_struct_access)(struct bpf_verifier_log *log, const struct btf *btf,
-				     const struct btf_type *t, int off, int size,
-				     enum bpf_access_type atype, u32 *next_btf_id,
-				     enum bpf_type_flag *flag);
+extern int (*nfct_btf_struct_access)(struct bpf_verifier_log *log,
+				     const struct bpf_reg_state *reg,
+				     int off, int size, enum bpf_access_type atype,
+				     u32 *next_btf_id, enum bpf_type_flag *flag);
 
 typedef unsigned int (*bpf_dispatcher_fn)(const void *ctx,
 					  const struct bpf_insn *insnsi,
kernel/bpf/btf.c +12 -4
index e56025505467..2e0ec7307f73 100644
@@ -6016,20 +6016,28 @@ static int btf_struct_walk(struct bpf_verifier_log *log, const struct btf *btf,
 	return -EINVAL;
 }
 
-int btf_struct_access(struct bpf_verifier_log *log, const struct btf *btf,
-		      const struct btf_type *t, int off, int size,
-		      enum bpf_access_type atype __maybe_unused,
+int btf_struct_access(struct bpf_verifier_log *log,
+		      const struct bpf_reg_state *reg,
+		      int off, int size, enum bpf_access_type atype __maybe_unused,
 		      u32 *next_btf_id, enum bpf_type_flag *flag)
 {
+	const struct btf *btf = reg->btf;
 	enum bpf_type_flag tmp_flag = 0;
+	const struct btf_type *t;
+	u32 id = reg->btf_id;
 	int err;
-	u32 id;
 
+	t = btf_type_by_id(btf, id);
 	do {
 		err = btf_struct_walk(log, btf, t, off, size, &id, &tmp_flag);
 
 		switch (err) {
 		case WALK_PTR:
+			/* For local types, the destination register cannot
+			 * become a pointer again.
+			 */
+			if (type_is_local_kptr(reg->type))
+				return SCALAR_VALUE;
 			/* If we found the pointer or scalar on t+off,
 			 * we're done.
 			 */
kernel/bpf/verifier.c +30 -7
index 168cd8bb9fd6..4de72a4a39bb 100644
@@ -4521,17 +4521,28 @@ static int check_ptr_to_btf_access(struct bpf_verifier_env *env,
 		return -EACCES;
 	}
 
-	if (env->ops->btf_struct_access) {
-		ret = env->ops->btf_struct_access(&env->log, reg->btf, t,
-						  off, size, atype, &btf_id, &flag);
+	if (env->ops->btf_struct_access && !type_is_local_kptr(reg->type)) {
+		if (!btf_is_kernel(reg->btf)) {
+			verbose(env, "verifier internal error: reg->btf must be kernel btf\n");
+			return -EFAULT;
+		}
+		ret = env->ops->btf_struct_access(&env->log, reg, off, size, atype, &btf_id, &flag);
 	} else {
-		if (atype != BPF_READ) {
+		/* Writes are permitted with default btf_struct_access for local
+		 * kptrs (which always have ref_obj_id > 0), but not for
+		 * _untrusted_ local kptrs.
+		 */
+		if (atype != BPF_READ && reg->type != (PTR_TO_BTF_ID | MEM_TYPE_LOCAL)) {
 			verbose(env, "only read is supported\n");
 			return -EACCES;
 		}
 
-		ret = btf_struct_access(&env->log, reg->btf, t, off, size,
-					atype, &btf_id, &flag);
+		if (type_is_local_kptr(reg->type) && !reg->ref_obj_id) {
+			verbose(env, "verifier internal error: ref_obj_id for local kptr must be non-zero\n");
+			return -EFAULT;
+		}
+
+		ret = btf_struct_access(&env->log, reg, off, size, atype, &btf_id, &flag);
 	}
 
 	if (ret < 0)
@@ -4557,6 +4568,7 @@ static int check_ptr_to_map_access(struct bpf_verifier_env *env,
 {
 	struct bpf_reg_state *reg = regs + regno;
 	struct bpf_map *map = reg->map_ptr;
+	struct bpf_reg_state map_reg;
 	enum bpf_type_flag flag = 0;
 	const struct btf_type *t;
 	const char *tname;
@@ -4595,7 +4607,10 @@ static int check_ptr_to_map_access(struct bpf_verifier_env *env,
 		return -EACCES;
 	}
 
-	ret = btf_struct_access(&env->log, btf_vmlinux, t, off, size, atype, &btf_id, &flag);
+	/* Simulate access to a PTR_TO_BTF_ID */
+	memset(&map_reg, 0, sizeof(map_reg));
+	mark_btf_ld_reg(env, &map_reg, 0, PTR_TO_BTF_ID, btf_vmlinux, *map->ops->map_btf_id, 0);
+	ret = btf_struct_access(&env->log, &map_reg, off, size, atype, &btf_id, &flag);
 	if (ret < 0)
 		return ret;
 
@@ -5805,6 +5820,7 @@ int check_func_arg_reg_off(struct bpf_verifier_env *env,
 	 * fixed offset.
 	 */
 	case PTR_TO_BTF_ID:
+	case PTR_TO_BTF_ID | MEM_TYPE_LOCAL:
 		/* When referenced PTR_TO_BTF_ID is passed to release function,
 		 * it's fixed offset must be 0.	In the other cases, fixed offset
 		 * can be non-zero.
@@ -13462,6 +13478,13 @@ static int convert_ctx_accesses(struct bpf_verifier_env *env)
 			break;
 		case PTR_TO_BTF_ID:
 		case PTR_TO_BTF_ID | PTR_UNTRUSTED:
+		/* PTR_TO_BTF_ID | MEM_TYPE_LOCAL always has a valid lifetime,
+		 * unlike PTR_TO_BTF_ID, and an active ref_obj_id, but the same
+		 * cannot be said once it is marked PTR_UNTRUSTED, hence we must
+		 * handle any faults for loads into such types. BPF_WRITE is
+		 * disallowed for this case.
+		 */
+		case PTR_TO_BTF_ID | MEM_TYPE_LOCAL | PTR_UNTRUSTED:
 			if (type == BPF_READ) {
 				insn->code = BPF_LDX | BPF_PROBE_MEM |
 					BPF_SIZE((insn)->code);
net/bpf/bpf_dummy_struct_ops.c +7 -7
index e78dadfc5829..2d434c1f4617 100644
@@ -156,29 +156,29 @@ static bool bpf_dummy_ops_is_valid_access(int off, int size,
 }
 
 static int bpf_dummy_ops_btf_struct_access(struct bpf_verifier_log *log,
-					   const struct btf *btf,
-					   const struct btf_type *t, int off,
-					   int size, enum bpf_access_type atype,
+					   const struct bpf_reg_state *reg,
+					   int off, int size, enum bpf_access_type atype,
 					   u32 *next_btf_id,
 					   enum bpf_type_flag *flag)
 {
 	const struct btf_type *state;
+	const struct btf_type *t;
 	s32 type_id;
 	int err;
 
-	type_id = btf_find_by_name_kind(btf, "bpf_dummy_ops_state",
+	type_id = btf_find_by_name_kind(reg->btf, "bpf_dummy_ops_state",
 					BTF_KIND_STRUCT);
 	if (type_id < 0)
 		return -EINVAL;
 
-	state = btf_type_by_id(btf, type_id);
+	t = btf_type_by_id(reg->btf, reg->btf_id);
+	state = btf_type_by_id(reg->btf, type_id);
 	if (t != state) {
 		bpf_log(log, "only access to bpf_dummy_ops_state is supported\n");
 		return -EACCES;
 	}
 
-	err = btf_struct_access(log, btf, t, off, size, atype, next_btf_id,
-				flag);
+	err = btf_struct_access(log, reg, off, size, atype, next_btf_id, flag);
 	if (err < 0)
 		return err;
 
net/core/filter.c +14 -20
index bb0136e7a8e4..1380828d67a3 100644
@@ -8647,28 +8647,25 @@ static bool tc_cls_act_is_valid_access(int off, int size,
 DEFINE_MUTEX(nf_conn_btf_access_lock);
 EXPORT_SYMBOL_GPL(nf_conn_btf_access_lock);
 
-int (*nfct_btf_struct_access)(struct bpf_verifier_log *log, const struct btf *btf,
-			      const struct btf_type *t, int off, int size,
-			      enum bpf_access_type atype, u32 *next_btf_id,
-			      enum bpf_type_flag *flag);
+int (*nfct_btf_struct_access)(struct bpf_verifier_log *log,
+			      const struct bpf_reg_state *reg,
+			      int off, int size, enum bpf_access_type atype,
+			      u32 *next_btf_id, enum bpf_type_flag *flag);
 EXPORT_SYMBOL_GPL(nfct_btf_struct_access);
 
 static int tc_cls_act_btf_struct_access(struct bpf_verifier_log *log,
-					const struct btf *btf,
-					const struct btf_type *t, int off,
-					int size, enum bpf_access_type atype,
-					u32 *next_btf_id,
-					enum bpf_type_flag *flag)
+					const struct bpf_reg_state *reg,
+					int off, int size, enum bpf_access_type atype,
+					u32 *next_btf_id, enum bpf_type_flag *flag)
 {
 	int ret = -EACCES;
 
 	if (atype == BPF_READ)
-		return btf_struct_access(log, btf, t, off, size, atype, next_btf_id,
-					 flag);
+		return btf_struct_access(log, reg, off, size, atype, next_btf_id, flag);
 
 	mutex_lock(&nf_conn_btf_access_lock);
 	if (nfct_btf_struct_access)
-		ret = nfct_btf_struct_access(log, btf, t, off, size, atype, next_btf_id, flag);
+		ret = nfct_btf_struct_access(log, reg, off, size, atype, next_btf_id, flag);
 	mutex_unlock(&nf_conn_btf_access_lock);
 
 	return ret;
@@ -8734,21 +8731,18 @@ void bpf_warn_invalid_xdp_action(struct net_device *dev, struct bpf_prog *prog,
 EXPORT_SYMBOL_GPL(bpf_warn_invalid_xdp_action);
 
 static int xdp_btf_struct_access(struct bpf_verifier_log *log,
-				 const struct btf *btf,
-				 const struct btf_type *t, int off,
-				 int size, enum bpf_access_type atype,
-				 u32 *next_btf_id,
-				 enum bpf_type_flag *flag)
+				 const struct bpf_reg_state *reg,
+				 int off, int size, enum bpf_access_type atype,
+				 u32 *next_btf_id, enum bpf_type_flag *flag)
 {
 	int ret = -EACCES;
 
 	if (atype == BPF_READ)
-		return btf_struct_access(log, btf, t, off, size, atype, next_btf_id,
-					 flag);
+		return btf_struct_access(log, reg, off, size, atype, next_btf_id, flag);
 
 	mutex_lock(&nf_conn_btf_access_lock);
 	if (nfct_btf_struct_access)
-		ret = nfct_btf_struct_access(log, btf, t, off, size, atype, next_btf_id, flag);
+		ret = nfct_btf_struct_access(log, reg, off, size, atype, next_btf_id, flag);
 	mutex_unlock(&nf_conn_btf_access_lock);
 
 	return ret;
net/ipv4/bpf_tcp_ca.c +6 -7
index 6da16ae6a962..d15c91de995f 100644
@@ -69,18 +69,17 @@ static bool bpf_tcp_ca_is_valid_access(int off, int size,
 }
 
 static int bpf_tcp_ca_btf_struct_access(struct bpf_verifier_log *log,
-					const struct btf *btf,
-					const struct btf_type *t, int off,
-					int size, enum bpf_access_type atype,
-					u32 *next_btf_id,
-					enum bpf_type_flag *flag)
+					const struct bpf_reg_state *reg,
+					int off, int size, enum bpf_access_type atype,
+					u32 *next_btf_id, enum bpf_type_flag *flag)
 {
+	const struct btf_type *t;
 	size_t end;
 
 	if (atype == BPF_READ)
-		return btf_struct_access(log, btf, t, off, size, atype, next_btf_id,
-					 flag);
+		return btf_struct_access(log, reg, off, size, atype, next_btf_id, flag);
 
+	t = btf_type_by_id(reg->btf, reg->btf_id);
 	if (t != tcp_sock_type) {
 		bpf_log(log, "only read is supported\n");
 		return -EACCES;
net/netfilter/nf_conntrack_bpf.c +7 -10
index 8639e7efd0e2..24002bc61e07 100644
@@ -191,19 +191,16 @@ BTF_ID(struct, nf_conn___init)
 
 /* Check writes into `struct nf_conn` */
 static int _nf_conntrack_btf_struct_access(struct bpf_verifier_log *log,
-					   const struct btf *btf,
-					   const struct btf_type *t, int off,
-					   int size, enum bpf_access_type atype,
-					   u32 *next_btf_id,
-					   enum bpf_type_flag *flag)
+					   const struct bpf_reg_state *reg,
+					   int off, int size, enum bpf_access_type atype,
+					   u32 *next_btf_id, enum bpf_type_flag *flag)
 {
-	const struct btf_type *ncit;
-	const struct btf_type *nct;
+	const struct btf_type *ncit, *nct, *t;
 	size_t end;
 
-	ncit = btf_type_by_id(btf, btf_nf_conn_ids[1]);
-	nct = btf_type_by_id(btf, btf_nf_conn_ids[0]);
-
+	ncit = btf_type_by_id(reg->btf, btf_nf_conn_ids[1]);
+	nct = btf_type_by_id(reg->btf, btf_nf_conn_ids[0]);
+	t = btf_type_by_id(reg->btf, reg->btf_id);
 	if (t != nct && t != ncit) {
 		bpf_log(log, "only read is supported\n");
 		return -EACCES;
Signature · 1 line
2.38.1
#26 lore raw

Re: [PATCH bpf-next v4 10/24] bpf: Introduce local kptrs

Quoted 5 lines · Kumar Kartikeya Dwivedi

Introduce local kptrs, i.e. PTR_TO_BTF_ID that point to a type in program BTF. This is indicated by the presence of MEM_TYPE_LOCAL type tag in reg->type to avoid having to check btf_is_kernel when trying to match argument types in helpers.

...

include/linux/bpf.h enum bpf_type_flag { · line 534

Quoted 6 lines
include/linux/bpf.h +5 -0
+       /* MEM is of a type from program BTF, not kernel BTF. This is used to
+        * tag PTR_TO_BTF_ID allocated using bpf_kptr_alloc.
+        */
+       MEM_TYPE_LOCAL          = BIT(11 + BPF_BASE_TYPE_BITS),
+

I know we have bpf_core_type_id_local.
It sort-of makes sense in the context of the program. type_id_local -> inside the program type_id_kernel -> kernel

but in the context of the verifier "local kptr" doesn't read right. Especially in MEM_TYPE_LOCAL.

Also, since it applies to PTR_TO_BTF_ID, should it prefix with PTR_? Probably MEM_ is actually cleaner.
And we're not consistent already with MEM_PERCPU.
We can live with this inconsistency for now.

So how about we rename MEM_ALLOC to MEM_RINGBUF,
since it's special bpf_ringbuf_reserve() memory
and use MEM_ALLOC to indicate the memory that came from bpf_obj_new ?

... which made me realize that the comment above should s/bpf_kptr_alloc/bpf_obj_new/

author maintainer
#27 lore raw

Re: [PATCH bpf-next v4 10/24] bpf: Introduce local kptrs

Quoted 15 lines · Alexei Starovoitov
Quoted 5 lines · Kumar Kartikeya Dwivedi

Introduce local kptrs, i.e. PTR_TO_BTF_ID that point to a type in program BTF. This is indicated by the presence of MEM_TYPE_LOCAL type tag in reg->type to avoid having to check btf_is_kernel when trying to match argument types in helpers.

...

include/linux/bpf.h enum bpf_type_flag { · line 534

Quoted 6 lines
include/linux/bpf.h +5 -0
+       /* MEM is of a type from program BTF, not kernel BTF. This is used to
+        * tag PTR_TO_BTF_ID allocated using bpf_kptr_alloc.
+        */
+       MEM_TYPE_LOCAL          = BIT(11 + BPF_BASE_TYPE_BITS),
+
Quoted 7 lines

I know we have bpf_core_type_id_local.
It sort-of makes sense in the context of the program. type_id_local -> inside the program type_id_kernel -> kernel

but in the context of the verifier "local kptr" doesn't read right. Especially in MEM_TYPE_LOCAL.

Yes, "local kptr" is not the best name. "kptr to local type" is too verbose though, do you have any suggestions on what to call this?

Quoted 10 lines

Also, since it applies to PTR_TO_BTF_ID, should it prefix with PTR_? Probably MEM_ is actually cleaner.
And we're not consistent already with MEM_PERCPU.
We can live with this inconsistency for now.

So how about we rename MEM_ALLOC to MEM_RINGBUF,
since it's special bpf_ringbuf_reserve() memory
and use MEM_ALLOC to indicate the memory that came from bpf_obj_new ?

Yes, it makes sense. I think Andrii has expressed the same wish to rename it to something similar to MEM_RINGBUF before in [0].

[0]: https://lore.kernel.org/bpf/CAEf4BzYK939fgyc3LwNvoz3vPk2avyskP_3wRZO344irubXPtg@mail.gmail.com

Quoted 2 lines

... which made me realize that the comment above should s/bpf_kptr_alloc/bpf_obj_new/

I'll fix the comment.

#28 lore raw

Re: [PATCH bpf-next v4 10/24] bpf: Introduce local kptrs

Quoted 39 lines · Kumar Kartikeya Dwivedi
Quoted 15 lines · Alexei Starovoitov
Quoted 5 lines · Kumar Kartikeya Dwivedi

Introduce local kptrs, i.e. PTR_TO_BTF_ID that point to a type in program BTF. This is indicated by the presence of MEM_TYPE_LOCAL type tag in reg->type to avoid having to check btf_is_kernel when trying to match argument types in helpers.

...

include/linux/bpf.h enum bpf_type_flag { · line 534

Quoted 6 lines
include/linux/bpf.h +5 -0
+       /* MEM is of a type from program BTF, not kernel BTF. This is used to
+        * tag PTR_TO_BTF_ID allocated using bpf_kptr_alloc.
+        */
+       MEM_TYPE_LOCAL          = BIT(11 + BPF_BASE_TYPE_BITS),
+
Quoted 7 lines

I know we have bpf_core_type_id_local.
It sort-of makes sense in the context of the program. type_id_local -> inside the program type_id_kernel -> kernel

but in the context of the verifier "local kptr" doesn't read right. Especially in MEM_TYPE_LOCAL.

Yes, "local kptr" is not the best name. "kptr to local type" is too verbose though, do you have any suggestions on what to call this?

Quoted 10 lines

Also, since it applies to PTR_TO_BTF_ID, should it prefix with PTR_? Probably MEM_ is actually cleaner.
And we're not consistent already with MEM_PERCPU.
We can live with this inconsistency for now.

So how about we rename MEM_ALLOC to MEM_RINGBUF,
since it's special bpf_ringbuf_reserve() memory
and use MEM_ALLOC to indicate the memory that came from bpf_obj_new ?

Quoted 4 lines

Yes, it makes sense. I think Andrii has expressed the same wish to rename it to something similar to MEM_RINGBUF before in [0].

[0]: https://lore.kernel.org/bpf/CAEf4BzYK939fgyc3LwNvoz3vPk2avyskP_3wRZO344irubXPtg@mail.gmail.com

Great. Please rename then.
Also let's all of us agree and stop using this [0] notation for links.
It's an email and not an academic paper.
Just insert the link.

#29 lore raw

Re: [PATCH bpf-next v4 10/24] bpf: Introduce local kptrs

In reply to Kumar Kartikeya Dwivedi
Quoted 33 lines · Kumar Kartikeya Dwivedi
Quoted 15 lines · Alexei Starovoitov
Quoted 5 lines · Kumar Kartikeya Dwivedi

Introduce local kptrs, i.e. PTR_TO_BTF_ID that point to a type in program BTF. This is indicated by the presence of MEM_TYPE_LOCAL type tag in reg->type to avoid having to check btf_is_kernel when trying to match argument types in helpers.

...

include/linux/bpf.h enum bpf_type_flag { · line 534

Quoted 6 lines
include/linux/bpf.h +5 -0
+       /* MEM is of a type from program BTF, not kernel BTF. This is used to
+        * tag PTR_TO_BTF_ID allocated using bpf_kptr_alloc.
+        */
+       MEM_TYPE_LOCAL          = BIT(11 + BPF_BASE_TYPE_BITS),
+
Quoted 7 lines

I know we have bpf_core_type_id_local.
It sort-of makes sense in the context of the program. type_id_local -> inside the program type_id_kernel -> kernel

but in the context of the verifier "local kptr" doesn't read right. Especially in MEM_TYPE_LOCAL.

Yes, "local kptr" is not the best name. "kptr to local type" is too verbose though, do you have any suggestions on what to call this?

Quoted 6 lines

Also, since it applies to PTR_TO_BTF_ID, should it prefix with PTR_? Probably MEM_ is actually cleaner.
And we're not consistent already with MEM_PERCPU.
We can live with this inconsistency for now.

Quoted 7 lines
Quoted 4 lines

So how about we rename MEM_ALLOC to MEM_RINGBUF,
since it's special bpf_ringbuf_reserve() memory
and use MEM_ALLOC to indicate the memory that came from bpf_obj_new ?

Yes, it makes sense. I think Andrii has expressed the same wish to rename it to something similar to MEM_RINGBUF before in [0].

I like this idea as well. I've been poking on a small refactoring patchset in the background which will get rid of (current) MEM_ALLOC anyways.

Quoted 7 lines

[0]: https://lore.kernel.org/bpf/CAEf4BzYK939fgyc3LwNvoz3vPk2avyskP_3wRZO344irubXPtg@mail.gmail.com

Quoted 2 lines

... which made me realize that the comment above should s/bpf_kptr_alloc/bpf_obj_new/

I'll fix the comment.

author maintainer
#30 lore raw

PATCH v4 11/24 bpf: Recognize bpf_{spin_lock,list_head,list_node} in local kptrs

In reply to Kumar Kartikeya Dwivedi

Allow specifying bpf_spin_lock, bpf_list_head, bpf_list_node fields in a local kptr.

A bpf_list_head allows implementing map-in-map style use cases, where local kptr with bpf_list_head is linked into a list in a map value. This would require embedding a bpf_list_node, support for which is also included.

Lastly, while we strictly don't require to hold a bpf_spin_lock while manipulating the bpf_list_head of a local kptr, as when have access to it, we have complete ownership of the object, the locking constraint is still kept and may be conditionally lifted in the future.

Note that the specification of such types can be done just like map values, e.g.:

struct bar {
	struct bpf_list_node node;
};
struct foo {
	struct bpf_spin_lock lock;
	struct bpf_list_head head __contains(bar, node);
	struct bpf_list_node node;
};
struct map_value {
	struct bpf_spin_lock lock;
	struct bpf_list_head head __contains(foo, node);
};

To recognize such types in user BTF, we build a btf_struct_metas array of metadata items corresponding to each BTF ID. This is done once during the btf_parse stage to avoid having to do it each time during the verification process's requirement to inspect the metadata.

Moreover, the computed metadata needs to be passed to some helpers in future patches which requires allocating them and storing them in the BTF that is pinned by the program itself, so that valid access can be assumed to such data during program runtime.

---
 include/linux/bpf.h  |   7 ++
 include/linux/btf.h  |  35 ++++++++
 kernel/bpf/btf.c     | 196 +++++++++++++++++++++++++++++++++++++++----
 kernel/bpf/syscall.c |   4 +
 4 files changed, 224 insertions(+), 18 deletions(-)
include/linux/bpf.h +7 -0
index bdd3adfcbe5f..0797c467e894 100644
@@ -177,6 +177,7 @@ enum btf_field_type {
 	BPF_KPTR_REF   = (1 << 3),
 	BPF_KPTR       = BPF_KPTR_UNREF | BPF_KPTR_REF,
 	BPF_LIST_HEAD  = (1 << 4),
+	BPF_LIST_NODE  = (1 << 5),
 };
 
 struct btf_field_kptr {
@@ -277,6 +278,8 @@ static inline const char *btf_field_type_name(enum btf_field_type type)
 		return "kptr";
 	case BPF_LIST_HEAD:
 		return "bpf_list_head";
+	case BPF_LIST_NODE:
+		return "bpf_list_node";
 	default:
 		WARN_ON_ONCE(1);
 		return "unknown";
@@ -295,6 +298,8 @@ static inline u32 btf_field_type_size(enum btf_field_type type)
 		return sizeof(u64);
 	case BPF_LIST_HEAD:
 		return sizeof(struct bpf_list_head);
+	case BPF_LIST_NODE:
+		return sizeof(struct bpf_list_node);
 	default:
 		WARN_ON_ONCE(1);
 		return 0;
@@ -313,6 +318,8 @@ static inline u32 btf_field_type_align(enum btf_field_type type)
 		return __alignof__(u64);
 	case BPF_LIST_HEAD:
 		return __alignof__(struct bpf_list_head);
+	case BPF_LIST_NODE:
+		return __alignof__(struct bpf_list_node);
 	default:
 		WARN_ON_ONCE(1);
 		return 0;
include/linux/btf.h +35 -0
index d80345fa566b..a01a8da20021 100644
@@ -6,6 +6,8 @@
 
 #include <linux/types.h>
 #include <linux/bpfptr.h>
+#include <linux/bsearch.h>
+#include <linux/btf_ids.h>
 #include <uapi/linux/btf.h>
 #include <uapi/linux/bpf.h>
 
@@ -78,6 +80,17 @@ struct btf_id_dtor_kfunc {
 	u32 kfunc_btf_id;
 };
 
+struct btf_struct_meta {
+	u32 btf_id;
+	struct btf_record *record;
+	struct btf_field_offs *field_offs;
+};
+
+struct btf_struct_metas {
+	u32 cnt;
+	struct btf_struct_meta types[];
+};
+
 typedef void (*btf_dtor_kfunc_t)(void *);
 
 extern const struct file_operations btf_fops;
@@ -408,6 +421,23 @@ static inline struct btf_param *btf_params(const struct btf_type *t)
 	return (struct btf_param *)(t + 1);
 }
 
+static inline int btf_id_cmp_func(const void *a, const void *b)
+{
+	const int *pa = a, *pb = b;
+
+	return *pa - *pb;
+}
+
+static inline bool btf_id_set_contains(const struct btf_id_set *set, u32 id)
+{
+	return bsearch(&id, set->ids, set->cnt, sizeof(u32), btf_id_cmp_func) != NULL;
+}
+
+static inline void *btf_id_set8_contains(const struct btf_id_set8 *set, u32 id)
+{
+	return bsearch(&id, set->pairs, set->cnt, sizeof(set->pairs[0]), btf_id_cmp_func);
+}
+
 #ifdef CONFIG_BPF_SYSCALL
 struct bpf_prog;
 
@@ -423,6 +453,7 @@ int register_btf_kfunc_id_set(enum bpf_prog_type prog_type,
 s32 btf_find_dtor_kfunc(struct btf *btf, u32 btf_id);
 int register_btf_id_dtor_kfuncs(const struct btf_id_dtor_kfunc *dtors, u32 add_cnt,
 				struct module *owner);
+struct btf_struct_meta *btf_find_struct_meta(const struct btf *btf, u32 btf_id);
 #else
 static inline const struct btf_type *btf_type_by_id(const struct btf *btf,
 						    u32 type_id)
@@ -454,6 +485,10 @@ static inline int register_btf_id_dtor_kfuncs(const struct btf_id_dtor_kfunc *dt
 {
 	return 0;
 }
+static inline struct btf_struct_meta *btf_find_struct_meta(const struct btf *btf, u32 btf_id)
+{
+	return NULL;
+}
 #endif
 
 static inline bool btf_type_is_struct_ptr(struct btf *btf, const struct btf_type *t)
kernel/bpf/btf.c +178 -18

272 lines not on this page · raw message

kernel/bpf/syscall.c +4 -0
index fdbae52f463f..c96039a4e57f 100644
@@ -537,6 +537,7 @@ void btf_record_free(struct btf_record *rec)
 			btf_put(rec->fields[i].kptr.btf);
 			break;
 		case BPF_LIST_HEAD:
+		case BPF_LIST_NODE:
 			/* Nothing to release for bpf_list_head */
 			break;
 		default:
@@ -582,6 +583,7 @@ struct btf_record *btf_record_dup(const struct btf_record *rec)
 			}
 			break;
 		case BPF_LIST_HEAD:
+		case BPF_LIST_NODE:
 			/* Nothing to acquire for bpf_list_head */
 			break;
 		default:
@@ -648,6 +650,8 @@ void bpf_obj_free_fields(const struct btf_record *rec, void *obj)
 				continue;
 			bpf_list_head_free(field, field_ptr, obj + rec->spin_lock_off);
 			break;
+		case BPF_LIST_NODE:
+			break;
 		default:
 			WARN_ON_ONCE(1);
 			continue;
Signature · 1 line
2.38.1
author maintainer
#31 lore raw

PATCH v4 12/24 bpf: Verify ownership relationships for user BTF types

In reply to Kumar Kartikeya Dwivedi

Ensure that there can be no ownership cycles among different types by way of having owning objects that can hold some other type as their element. For instance, a map value can only hold local kptrs, but these are allowed to have another bpf_list_head. To prevent unbounded recursion while freeing resources, elements of bpf_list_head in local kptrs can never have a bpf_list_head which are part of list in a map value.

Also, to make runtime destruction easier, once btf_struct_metas is fully populated, we can stash the metadata of the value type directly in the metadata of the list_head fields, as that allows easier access to the value type's layout to destruct it at runtime from the btf_field entry of the list head itself.

---
 include/linux/bpf.h  |  1 +
 include/linux/btf.h  |  1 +
 kernel/bpf/btf.c     | 71 ++++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/syscall.c |  4 +++
 4 files changed, 77 insertions(+)
include/linux/bpf.h +1 -0
index 0797c467e894..fb2659c1c10c 100644
@@ -191,6 +191,7 @@ struct btf_field_list_head {
 	struct btf *btf;
 	u32 value_btf_id;
 	u32 node_offset;
+	struct btf_record *value_rec;
 };
 
 struct btf_field {
include/linux/btf.h +1 -0
index a01a8da20021..42d8f3730a8d 100644
@@ -178,6 +178,7 @@ int btf_find_spin_lock(const struct btf *btf, const struct btf_type *t);
 int btf_find_timer(const struct btf *btf, const struct btf_type *t);
 struct btf_record *btf_parse_fields(const struct btf *btf, const struct btf_type *t,
 				    u32 field_mask, u32 value_size);
+int btf_check_and_fixup_fields(const struct btf *btf, struct btf_record *rec);
 struct btf_field_offs *btf_parse_field_offs(struct btf_record *rec);
 bool btf_type_is_void(const struct btf_type *t);
 s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind);
kernel/bpf/btf.c +71 -0

83 lines not on this page · raw message

kernel/bpf/syscall.c +4 -0
index c96039a4e57f..4669020bb47d 100644
@@ -1044,6 +1044,10 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf,
 		}
 	}
 
+	ret = btf_check_and_fixup_fields(btf, map->record);
+	if (ret < 0)
+		goto free_map_tab;
+
 	if (map->ops->map_check_btf) {
 		ret = map->ops->map_check_btf(map, btf, key_type, value_type);
 		if (ret < 0)
Signature · 1 line
2.38.1
author maintainer
#32 lore raw

PATCH v4 13/24 bpf: Support locking bpf_spin_lock in local kptr

In reply to Kumar Kartikeya Dwivedi

Allow locking a bpf_spin_lock embedded in local kptr, in addition to already support map value pointers. The handling is similar to that of map values, by just preserving the reg->id of local kptrs as well, and adjusting process_spin_lock to work with non-PTR_TO_MAP_VALUE and remember the id in verifier state.

---
 kernel/bpf/helpers.c  |  2 ++
 kernel/bpf/verifier.c | 70 ++++++++++++++++++++++++++++++++-----------
 2 files changed, 55 insertions(+), 17 deletions(-)
kernel/bpf/helpers.c +2 -0
index 339cce94b408..207f622ec70d 100644
@@ -336,6 +336,7 @@ const struct bpf_func_proto bpf_spin_lock_proto = {
 	.gpl_only	= false,
 	.ret_type	= RET_VOID,
 	.arg1_type	= ARG_PTR_TO_SPIN_LOCK,
+	.arg1_btf_id    = BPF_PTR_POISON,
 };
 
 static inline void __bpf_spin_unlock_irqrestore(struct bpf_spin_lock *lock)
@@ -358,6 +359,7 @@ const struct bpf_func_proto bpf_spin_unlock_proto = {
 	.gpl_only	= false,
 	.ret_type	= RET_VOID,
 	.arg1_type	= ARG_PTR_TO_SPIN_LOCK,
+	.arg1_btf_id    = BPF_PTR_POISON,
 };
 
 void copy_map_value_locked(struct bpf_map *map, void *dst, void *src,
kernel/bpf/verifier.c +53 -17

123 lines not on this page · raw message

Signature · 1 line
2.38.1
author maintainer
#33 lore raw

PATCH v4 14/24 bpf: Allow locking bpf_spin_lock global variables

In reply to Kumar Kartikeya Dwivedi

Global variables reside in maps accessible using direct_value_addr callbacks, so giving each load instruction's rewrite a unique reg->id disallows us from holding locks which are global.

This is not great, so refactor the active_spin_lock into two separate fields, active_spin_lock_ptr and active_spin_lock_id, which is generic enough to allow it for global variables, map lookups, and local kptr registers at the same time.

Held vs non-held is indicated by active_spin_lock_ptr, which stores the reg->map_ptr or reg->btf pointer of the register used for locking spin lock. But the active_spin_lock_id also needs to be compared to ensure whether bpf_spin_unlock is for the same register.

Next, pseudo load instructions are not given a unique reg->id, as they are doing lookup for the same map value (max_entries is never greater than 1).

Essentially, we consider that the tuple of (active_spin_lock_ptr, active_spin_lock_id) will always be unique for any kind of argument to bpf_spin_{lock,unlock}.

Note that this can be extended in the future to also remember offset used for locking, so that we can introduce multiple bpf_spin_lock fields in the same allocation.

---
 include/linux/bpf_verifier.h |  3 ++-
 kernel/bpf/verifier.c        | 39 +++++++++++++++++++++++++-----------
 2 files changed, 29 insertions(+), 13 deletions(-)
include/linux/bpf_verifier.h +2 -1
index 1a32baa78ce2..bb71c59f21f6 100644
@@ -323,7 +323,8 @@ struct bpf_verifier_state {
 	u32 branches;
 	u32 insn_idx;
 	u32 curframe;
-	u32 active_spin_lock;
+	void *active_spin_lock_ptr;
+	u32 active_spin_lock_id;
 	bool speculative;
 
 	/* first and last insn idx of this verifier state */
kernel/bpf/verifier.c +27 -12
index c31f20aed30c..4a43cde0ff4c 100644
@@ -1201,7 +1201,8 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state,
 	}
 	dst_state->speculative = src->speculative;
 	dst_state->curframe = src->curframe;
-	dst_state->active_spin_lock = src->active_spin_lock;
+	dst_state->active_spin_lock_ptr = src->active_spin_lock_ptr;
+	dst_state->active_spin_lock_id = src->active_spin_lock_id;
 	dst_state->branches = src->branches;
 	dst_state->parent = src->parent;
 	dst_state->first_insn_idx = src->first_insn_idx;
@@ -5470,22 +5471,35 @@ static int process_spin_lock(struct bpf_verifier_env *env, int regno,
 		return -EINVAL;
 	}
 	if (is_lock) {
-		if (cur->active_spin_lock) {
+		if (cur->active_spin_lock_ptr) {
 			verbose(env,
 				"Locking two bpf_spin_locks are not allowed\n");
 			return -EINVAL;
 		}
-		cur->active_spin_lock = reg->id;
+		if (map)
+			cur->active_spin_lock_ptr = map;
+		else
+			cur->active_spin_lock_ptr = btf;
+		cur->active_spin_lock_id = reg->id;
 	} else {
-		if (!cur->active_spin_lock) {
+		void *ptr;
+
+		if (map)
+			ptr = map;
+		else
+			ptr = btf;
+
+		if (!cur->active_spin_lock_ptr) {
 			verbose(env, "bpf_spin_unlock without taking a lock\n");
 			return -EINVAL;
 		}
-		if (cur->active_spin_lock != reg->id) {
+		if (cur->active_spin_lock_ptr != ptr ||
+		    cur->active_spin_lock_id != reg->id) {
 			verbose(env, "bpf_spin_unlock of different lock\n");
 			return -EINVAL;
 		}
-		cur->active_spin_lock = 0;
+		cur->active_spin_lock_ptr = NULL;
+		cur->active_spin_lock_id = 0;
 	}
 	return 0;
 }
@@ -10393,8 +10407,8 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
 	    insn->src_reg == BPF_PSEUDO_MAP_IDX_VALUE) {
 		dst_reg->type = PTR_TO_MAP_VALUE;
 		dst_reg->off = aux->map_off;
-		if (btf_record_has_field(map->record, BPF_SPIN_LOCK))
-			dst_reg->id = ++env->id_gen;
+		WARN_ON_ONCE(map->max_entries != 1);
+		/* We want reg->id to be same (0) as map_value is not distinct */
 	} else if (insn->src_reg == BPF_PSEUDO_MAP_FD ||
 		   insn->src_reg == BPF_PSEUDO_MAP_IDX) {
 		dst_reg->type = CONST_PTR_TO_MAP;
@@ -10472,7 +10486,7 @@ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn)
 		return err;
 	}
 
-	if (env->cur_state->active_spin_lock) {
+	if (env->cur_state->active_spin_lock_ptr) {
 		verbose(env, "BPF_LD_[ABS|IND] cannot be used inside bpf_spin_lock-ed region\n");
 		return -EINVAL;
 	}
@@ -11738,7 +11752,8 @@ static bool states_equal(struct bpf_verifier_env *env,
 	if (old->speculative && !cur->speculative)
 		return false;
 
-	if (old->active_spin_lock != cur->active_spin_lock)
+	if (old->active_spin_lock_ptr != cur->active_spin_lock_ptr ||
+	    old->active_spin_lock_id != cur->active_spin_lock_id)
 		return false;
 
 	/* for states to be equal callsites have to be the same
@@ -12377,7 +12392,7 @@ static int do_check(struct bpf_verifier_env *env)
 					return -EINVAL;
 				}
 
-				if (env->cur_state->active_spin_lock &&
+				if (env->cur_state->active_spin_lock_ptr &&
 				    (insn->src_reg == BPF_PSEUDO_CALL ||
 				     insn->imm != BPF_FUNC_spin_unlock)) {
 					verbose(env, "function calls are not allowed while holding a lock\n");
@@ -12414,7 +12429,7 @@ static int do_check(struct bpf_verifier_env *env)
 					return -EINVAL;
 				}
 
-				if (env->cur_state->active_spin_lock) {
+				if (env->cur_state->active_spin_lock_ptr) {
 					verbose(env, "bpf_spin_unlock is missing\n");
 					return -EINVAL;
 				}
Signature · 1 line
2.38.1
#34 lore raw

Re: [PATCH bpf-next v4 14/24] bpf: Allow locking bpf_spin_lock global variables

Quoted 37 lines · Kumar Kartikeya Dwivedi

Global variables reside in maps accessible using direct_value_addr callbacks, so giving each load instruction's rewrite a unique reg->id disallows us from holding locks which are global.

This is not great, so refactor the active_spin_lock into two separate fields, active_spin_lock_ptr and active_spin_lock_id, which is generic enough to allow it for global variables, map lookups, and local kptr registers at the same time.

Held vs non-held is indicated by active_spin_lock_ptr, which stores the reg->map_ptr or reg->btf pointer of the register used for locking spin lock. But the active_spin_lock_id also needs to be compared to ensure whether bpf_spin_unlock is for the same register.

Next, pseudo load instructions are not given a unique reg->id, as they are doing lookup for the same map value (max_entries is never greater than 1).

Essentially, we consider that the tuple of (active_spin_lock_ptr, active_spin_lock_id) will always be unique for any kind of argument to bpf_spin_{lock,unlock}.

Note that this can be extended in the future to also remember offset used for locking, so that we can introduce multiple bpf_spin_lock fields in the same allocation.

---
 include/linux/bpf_verifier.h |  3 ++-
 kernel/bpf/verifier.c        | 39 +++++++++++++++++++++++++-----------
 2 files changed, 29 insertions(+), 13 deletions(-)
include/linux/bpf_verifier.h +0 -0
index 1a32baa78ce2..bb71c59f21f6 100644

include/linux/bpf_verifier.h struct bpf_verifier_state { · line 328

Quoted 7 lines
include/linux/bpf_verifier.h +2 -1
@@ -323,7 +323,8 @@ struct bpf_verifier_state {
 	u32 branches;
 	u32 insn_idx;
 	u32 curframe;
-	u32 active_spin_lock;
+	void *active_spin_lock_ptr;
+	u32 active_spin_lock_id;
 	bool speculative;

Back in first RFC of this series we talked about turning this "spin lock identity" concept into a proper struct [0]. But to save you the click:

Dave:
"""
It would be good to make this "(lock_ptr, lock_id) is identifier for lock" concept more concrete by grouping these fields in a struct w/ type enum + union, or something similar. Will make it more obvious that they should be used / set together.

But if you'd prefer to keep it as two fields, active_spin_lock_ptr is a confusing name. In the future with no context as to what that field is, I'd assume that it holds a pointer to a spin_lock instead of a "spin lock identity pointer".
"""

Kumar:
"""
That's a good point.

I'm thinking
struct active_lock {
void *id_ptr;
u32 offset;
u32 reg_id;
};
How does that look?
"""

I didn't get back to you, but I think that looks reasonable, and "this can be extended in the future to also remember offset used for locking" in this patch summary supports the desire to group up those fields. (I agree that offset isn't necessary for now, though).

[0]: https://lore.kernel.org/bpf/[email protected]/

author maintainer
#35 lore raw

Re: [PATCH bpf-next v4 14/24] bpf: Allow locking bpf_spin_lock global variables

Quoted 74 lines · Dave Marchevsky
Quoted 37 lines · Kumar Kartikeya Dwivedi

Global variables reside in maps accessible using direct_value_addr callbacks, so giving each load instruction's rewrite a unique reg->id disallows us from holding locks which are global.

This is not great, so refactor the active_spin_lock into two separate fields, active_spin_lock_ptr and active_spin_lock_id, which is generic enough to allow it for global variables, map lookups, and local kptr registers at the same time.

Held vs non-held is indicated by active_spin_lock_ptr, which stores the reg->map_ptr or reg->btf pointer of the register used for locking spin lock. But the active_spin_lock_id also needs to be compared to ensure whether bpf_spin_unlock is for the same register.

Next, pseudo load instructions are not given a unique reg->id, as they are doing lookup for the same map value (max_entries is never greater than 1).

Essentially, we consider that the tuple of (active_spin_lock_ptr, active_spin_lock_id) will always be unique for any kind of argument to bpf_spin_{lock,unlock}.

Note that this can be extended in the future to also remember offset used for locking, so that we can introduce multiple bpf_spin_lock fields in the same allocation.

---
 include/linux/bpf_verifier.h |  3 ++-
 kernel/bpf/verifier.c        | 39 +++++++++++++++++++++++++-----------
 2 files changed, 29 insertions(+), 13 deletions(-)
include/linux/bpf_verifier.h +0 -0
index 1a32baa78ce2..bb71c59f21f6 100644

include/linux/bpf_verifier.h struct bpf_verifier_state { · line 328

Quoted 7 lines
include/linux/bpf_verifier.h +2 -1
@@ -323,7 +323,8 @@ struct bpf_verifier_state {
 	u32 branches;
 	u32 insn_idx;
 	u32 curframe;
-	u32 active_spin_lock;
+	void *active_spin_lock_ptr;
+	u32 active_spin_lock_id;
 	bool speculative;

Back in first RFC of this series we talked about turning this "spin lock identity" concept into a proper struct [0]. But to save you the click:

Dave:
"""
It would be good to make this "(lock_ptr, lock_id) is identifier for lock" concept more concrete by grouping these fields in a struct w/ type enum + union, or something similar. Will make it more obvious that they should be used / set together.

But if you'd prefer to keep it as two fields, active_spin_lock_ptr is a confusing name. In the future with no context as to what that field is, I'd assume that it holds a pointer to a spin_lock instead of a "spin lock identity pointer".
"""

Kumar:
"""
That's a good point.

I'm thinking
struct active_lock {
void *id_ptr;
u32 offset;
u32 reg_id;
};
How does that look?
"""

Quoted 5 lines

I didn't get back to you, but I think that looks reasonable, and "this can be extended in the future to also remember offset used for locking" in this patch summary supports the desire to group up those fields. (I agree that offset isn't necessary for now, though).

I will make this change in v5.

However, do you have any suggestions on what we can call the id_ptr thing? In patch 22 in the big comment above check_reg_allocation_locked I call it lock class, but I'm not sure whether it helps or is more confusing for people.

In active_spin_lock_ptr, 'ptr' alone is confusing as you've pointed out before.

author maintainer
#36 lore raw

PATCH v4 15/24 bpf: Rewrite kfunc argument handling

In reply to Kumar Kartikeya Dwivedi

As we continue to add more features, argument types, kfunc flags, and different extensions to kfuncs, the code to verify the correctness of the kfunc prototype wrt the passed in registers has become ad-hoc and ugly to read.

To make life easier, and make a very clear split between different stages of argument processing, move all the code into verifier.c and refactor into easier to read helpers and functions.

This also makes sharing code within the verifier easier with kfunc argument processing. This will be more and more useful in later patches as we are now moving to implement very core BPF helpers as kfuncs, to keep them experimental before baking into UAPI.

---
 include/linux/btf.h                           |  31 +-
 kernel/bpf/btf.c                              |  16 +-
 kernel/bpf/verifier.c                         | 545 +++++++++++++++++-
 .../bpf/prog_tests/kfunc_dynptr_param.c       |   2 +-
 tools/testing/selftests/bpf/verifier/calls.c  |   4 +-
 .../selftests/bpf/verifier/ref_tracking.c     |   4 +-
 6 files changed, 568 insertions(+), 34 deletions(-)
include/linux/btf.h +30 -1
index 42d8f3730a8d..d5b26380a60f 100644
@@ -338,6 +338,16 @@ static inline bool btf_type_is_struct(const struct btf_type *t)
 	return kind == BTF_KIND_STRUCT || kind == BTF_KIND_UNION;
 }
 
+static inline bool __btf_type_is_struct(const struct btf_type *t)
+{
+	return BTF_INFO_KIND(t->info) == BTF_KIND_STRUCT;
+}
+
+static inline bool btf_type_is_array(const struct btf_type *t)
+{
+	return BTF_INFO_KIND(t->info) == BTF_KIND_ARRAY;
+}
+
 static inline u16 btf_type_vlen(const struct btf_type *t)
 {
 	return BTF_INFO_VLEN(t->info);
@@ -439,9 +449,10 @@ static inline void *btf_id_set8_contains(const struct btf_id_set8 *set, u32 id)
 	return bsearch(&id, set->pairs, set->cnt, sizeof(set->pairs[0]), btf_id_cmp_func);
 }
 
-#ifdef CONFIG_BPF_SYSCALL
 struct bpf_prog;
+struct bpf_verifier_log;
 
+#ifdef CONFIG_BPF_SYSCALL
 const struct btf_type *btf_type_by_id(const struct btf *btf, u32 type_id);
 const char *btf_name_by_offset(const struct btf *btf, u32 offset);
 struct btf *btf_parse_vmlinux(void);
@@ -455,6 +466,12 @@ s32 btf_find_dtor_kfunc(struct btf *btf, u32 btf_id);
 int register_btf_id_dtor_kfuncs(const struct btf_id_dtor_kfunc *dtors, u32 add_cnt,
 				struct module *owner);
 struct btf_struct_meta *btf_find_struct_meta(const struct btf *btf, u32 btf_id);
+const struct btf_member *
+btf_get_prog_ctx_type(struct bpf_verifier_log *log, const struct btf *btf,
+		      const struct btf_type *t, enum bpf_prog_type prog_type,
+		      int arg);
+bool btf_types_are_same(const struct btf *btf1, u32 id1,
+			const struct btf *btf2, u32 id2);
 #else
 static inline const struct btf_type *btf_type_by_id(const struct btf *btf,
 						    u32 type_id)
@@ -490,6 +507,18 @@ static inline struct btf_struct_meta *btf_find_struct_meta(const struct btf *btf
 {
 	return NULL;
 }
+static inline const struct btf_member *
+btf_get_prog_ctx_type(struct bpf_verifier_log *log, const struct btf *btf,
+		      const struct btf_type *t, enum bpf_prog_type prog_type,
+		      int arg)
+{
+	return NULL;
+}
+static inline bool btf_types_are_same(const struct btf *btf1, u32 id1,
+				      const struct btf *btf2, u32 id2)
+{
+	return false;
+}
 #endif
 
 static inline bool btf_type_is_struct_ptr(struct btf *btf, const struct btf_type *t)
kernel/bpf/btf.c +3 -13
index 514219a790f4..7a66aaa02e6a 100644
@@ -478,16 +478,6 @@ static bool btf_type_nosize_or_null(const struct btf_type *t)
 	return !t || btf_type_nosize(t);
 }
 
-static bool __btf_type_is_struct(const struct btf_type *t)
-{
-	return BTF_INFO_KIND(t->info) == BTF_KIND_STRUCT;
-}
-
-static bool btf_type_is_array(const struct btf_type *t)
-{
-	return BTF_INFO_KIND(t->info) == BTF_KIND_ARRAY;
-}
-
 static bool btf_type_is_datasec(const struct btf_type *t)
 {
 	return BTF_INFO_KIND(t->info) == BTF_KIND_DATASEC;
@@ -5534,7 +5524,7 @@ static u8 bpf_ctx_convert_map[] = {
 #undef BPF_MAP_TYPE
 #undef BPF_LINK_TYPE
 
-static const struct btf_member *
+const struct btf_member *
 btf_get_prog_ctx_type(struct bpf_verifier_log *log, const struct btf *btf,
 		      const struct btf_type *t, enum bpf_prog_type prog_type,
 		      int arg)
@@ -6320,8 +6310,8 @@ int btf_struct_access(struct bpf_verifier_log *log,
  * end up with two different module BTFs, but IDs point to the common type in
  * vmlinux BTF.
  */
-static bool btf_types_are_same(const struct btf *btf1, u32 id1,
-			       const struct btf *btf2, u32 id2)
+bool btf_types_are_same(const struct btf *btf1, u32 id1,
+			const struct btf *btf2, u32 id2)
 {
 	if (id1 != id2)
 		return false;
kernel/bpf/verifier.c +530 -15

600 lines not on this page · raw message

tools/testing/selftests/bpf/prog_tests/kfunc_dynptr_param.c +1 -1
index c210657d4d0a..55d641c1f126 100644
@@ -22,7 +22,7 @@ static struct {
 	 "arg#0 pointer type STRUCT bpf_dynptr_kern points to unsupported dynamic pointer type", 0},
 	{"not_valid_dynptr",
 	 "arg#0 pointer type STRUCT bpf_dynptr_kern must be valid and initialized", 0},
-	{"not_ptr_to_stack", "arg#0 pointer type STRUCT bpf_dynptr_kern not to stack", 0},
+	{"not_ptr_to_stack", "arg#0 expected pointer to stack", 0},
 	{"dynptr_data_null", NULL, -EBADMSG},
 };
 
tools/testing/selftests/bpf/verifier/calls.c +2 -2
index e1a937277b54..e349d85f7717 100644
@@ -109,7 +109,7 @@
 	},
 	.prog_type = BPF_PROG_TYPE_SCHED_CLS,
 	.result = REJECT,
-	.errstr = "arg#0 pointer type STRUCT prog_test_ref_kfunc must point",
+	.errstr = "arg#0 expected pointer to btf or socket",
 	.fixup_kfunc_btf_id = {
 		{ "bpf_kfunc_call_test_acquire", 3 },
 		{ "bpf_kfunc_call_test_release", 5 },
@@ -181,7 +181,7 @@
 	},
 	.result_unpriv = REJECT,
 	.result = REJECT,
-	.errstr = "negative offset ptr_ ptr R1 off=-4 disallowed",
+	.errstr = "R1 must have zero offset when passed to release func",
 },
 {
 	"calls: invalid kfunc call: PTR_TO_BTF_ID with variable offset",
tools/testing/selftests/bpf/verifier/ref_tracking.c +2 -2
index f18ce867271f..4784471b0b7f 100644
@@ -142,7 +142,7 @@
 	.kfunc = "bpf",
 	.expected_attach_type = BPF_LSM_MAC,
 	.flags = BPF_F_SLEEPABLE,
-	.errstr = "arg#0 pointer type STRUCT bpf_key must point to scalar, or struct with scalar",
+	.errstr = "arg#0 expected pointer to btf or socket",
 	.fixup_kfunc_btf_id = {
 		{ "bpf_lookup_user_key", 2 },
 		{ "bpf_key_put", 4 },
@@ -163,7 +163,7 @@
 	.kfunc = "bpf",
 	.expected_attach_type = BPF_LSM_MAC,
 	.flags = BPF_F_SLEEPABLE,
-	.errstr = "arg#0 pointer type STRUCT bpf_key must point to scalar, or struct with scalar",
+	.errstr = "arg#0 expected pointer to btf or socket",
 	.fixup_kfunc_btf_id = {
 		{ "bpf_lookup_system_key", 1 },
 		{ "bpf_key_put", 3 },
Signature · 1 line
2.38.1
author maintainer
#37 lore raw

PATCH v4 16/24 bpf: Drop kfunc bits from btf_check_func_arg_match

In reply to Kumar Kartikeya Dwivedi

Remove all kfunc related bits now from btf_check_func_arg_match, as users have been converted away to refactored kfunc argument handling.

This is split into a separate commit to aid review, in order to compare what has been preserved from the removed bits easily instead of mixing removed hunks with previous patch.

---
 include/linux/bpf.h          |  11 --
 include/linux/bpf_verifier.h |   2 -
 kernel/bpf/btf.c             | 364 +----------------------------------
 kernel/bpf/verifier.c        |   4 +-
 4 files changed, 10 insertions(+), 371 deletions(-)
include/linux/bpf.h +0 -11
index fb2659c1c10c..5d9a786e0cef 100644
@@ -2112,22 +2112,11 @@ int btf_distill_func_proto(struct bpf_verifier_log *log,
 			   const char *func_name,
 			   struct btf_func_model *m);
 
-struct bpf_kfunc_arg_meta {
-	u64 r0_size;
-	bool r0_rdonly;
-	int ref_obj_id;
-	u32 flags;
-};
-
 struct bpf_reg_state;
 int btf_check_subprog_arg_match(struct bpf_verifier_env *env, int subprog,
 				struct bpf_reg_state *regs);
 int btf_check_subprog_call(struct bpf_verifier_env *env, int subprog,
 			   struct bpf_reg_state *regs);
-int btf_check_kfunc_arg_match(struct bpf_verifier_env *env,
-			      const struct btf *btf, u32 func_id,
-			      struct bpf_reg_state *regs,
-			      struct bpf_kfunc_arg_meta *meta);
 int btf_prepare_func_args(struct bpf_verifier_env *env, int subprog,
 			  struct bpf_reg_state *reg);
 int btf_check_type_match(struct bpf_verifier_log *log, const struct bpf_prog *prog,
include/linux/bpf_verifier.h +0 -2
index bb71c59f21f6..8dad74432677 100644
@@ -590,8 +590,6 @@ int check_ptr_off_reg(struct bpf_verifier_env *env,
 int check_func_arg_reg_off(struct bpf_verifier_env *env,
 			   const struct bpf_reg_state *reg, int regno,
 			   enum bpf_arg_type arg_type);
-int check_kfunc_mem_size_reg(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
-			     u32 regno);
 int check_mem_reg(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
 		   u32 regno, u32 mem_size);
 bool is_dynptr_reg_valid_init(struct bpf_verifier_env *env,
kernel/bpf/btf.c +8 -356

447 lines not on this page · raw message

kernel/bpf/verifier.c +2 -2
index 5c2f5e61dde9..effc417cc086 100644
@@ -5378,8 +5378,8 @@ int check_mem_reg(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
 	return err;
 }
 
-int check_kfunc_mem_size_reg(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
-			     u32 regno)
+static int check_kfunc_mem_size_reg(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
+				    u32 regno)
 {
 	struct bpf_reg_state *mem_reg = &cur_regs(env)[regno - 1];
 	bool may_be_null = type_may_be_null(mem_reg->type);
Signature · 1 line
2.38.1
author maintainer
#38 lore raw

PATCH v4 17/24 bpf: Support constant scalar arguments for kfuncs

In reply to Kumar Kartikeya Dwivedi

Allow passing known constant scalars as arguments to kfuncs that do not represent a size parameter. This makes the search pruning optimization of verifier more conservative for such kfunc calls, and each non-distinct argument is considered unequivalent.

We will use this support to then expose a global bpf_kptr_alloc function where it takes the local type ID in program BTF, and returns a PTR_TO_BTF_ID to the local type. These will be called local kptrs, and allows programs to allocate their own objects.

However, this is still not completely safe, as mark_chain_precision logic is buggy without more work when the constant argument is not a size, but still needs precise marker propagation for pruning checks. Next patch will fix this problem.

---
 Documentation/bpf/kfuncs.rst | 30 ++++++++++++++++++
 kernel/bpf/verifier.c        | 59 +++++++++++++++++++++++++++---------
 2 files changed, 75 insertions(+), 14 deletions(-)
Documentation/bpf/kfuncs.rst +30 -0
index 0f858156371d..08f9a968d06d 100644
@@ -72,6 +72,36 @@ argument as its size. By default, without __sz annotation, the size of the type
 of the pointer is used. Without __sz annotation, a kfunc cannot accept a void
 pointer.
 
+2.2.1 __k Annotation
+--------------------
+
+This annotation is only understood for scalar arguments, where it indicates that
+the verifier must check the scalar argument to be a known constant, which does
+not indicate a size parameter. This distinction is important, as when the scalar
+argument does not represent a size parameter, verifier is more conservative in
+state search pruning and does not consider two arguments equivalent for safety
+purposes if the already verified value was within range of the new one.
+
+This assumption holds well for sizes (as memory accessed within smaller bounds
+in old verified state will also work for bigger bounds in current to be explored
+state), but not for other constant arguments where each carries a distinct
+semantic effect.
+
+An example is given below::
+
+        void *bpf_mem_alloc(u32 local_type_id__k)
+        {
+        ...
+        }
+
+Here, bpf_mem_alloc uses local_type_id argument to find out the size of that
+type ID in program's BTF and return a sized pointer to it. Each type ID will
+have a distinct size, hence it is crucial to treat each such call as distinct
+when values don't match.
+
+Hence, whenever a constant scalar argument is accepted by a kfunc which is not a
+size parameter, __k suffix must be used.
+
 .. _BPF_kfunc_nodef:
 
 2.3 Using an existing kernel function
kernel/bpf/verifier.c +45 -14

88 lines not on this page · raw message

Signature · 1 line
2.38.1
author maintainer
#39 lore raw

PATCH v4 18/24 bpf: Teach verifier about non-size constant arguments

In reply to Kumar Kartikeya Dwivedi

Currently, the verifier has support for various arguments that either describe the size of the memory being passed in to a helper, or describe the size of the memory being returned. When a constant is passed in like this, it is assumed for the purposes of precision tracking that if the value in the already explored safe state is within the value in current state, it would fine to prune the search.

While this holds well for size arguments, arguments where each value may denote a distinct meaning and needs to be verified separately needs more work. Search can only be pruned if both are constant values and both are equal. In all other cases, it would be incorrect to treat those two precise registers as equivalent if the new value satisfies the old one (i.e. old <= cur).

Hence, make the register precision marker tri-state. There are now three values that reg->precise takes: NOT_PRECISE, PRECISE, EXACT.

Both PRECISE and EXACT are 'true' values. EXACT affects how regsafe decides whether both registers are equivalent for the purposes of verifier state equivalence. When it sees that one register has reg->precise == EXACT, unless both are absolute, it will return false. When both are, it returns true only when both are const and both have the same value. Otherwise, for PRECISE case it falls back to the default check that is present now (i.e. thinking that we're talking about sizes).

This is required as a future patch introduces a BPF memory allocator interface, where we take the program BTF's type ID as an argument. Each distinct type ID may result in the returned pointer obtaining a different size, hence precision tracking is needed, and pruning cannot just happen when the old value is within the current value. It must only happen when the type ID is equal. The type ID will always correspond to prog->aux->btf hence actual type match is not required.

Finally, change mark_chain_precision precision argument to EXACT for kfuncs constant non-size scalar arguments (tagged with __k suffix).

---
 include/linux/bpf_verifier.h |  10 ++--
 kernel/bpf/verifier.c        | 101 ++++++++++++++++++++++-------------
 2 files changed, 70 insertions(+), 41 deletions(-)
include/linux/bpf_verifier.h +7 -3
index 8dad74432677..2614892ca063 100644
@@ -43,6 +43,12 @@ enum bpf_reg_liveness {
 	REG_LIVE_DONE = 0x8, /* liveness won't be updating this register anymore */
 };
 
+enum bpf_reg_precise {
+	NOT_PRECISE,
+	PRECISE,
+	EXACT,
+};
+
 struct bpf_reg_state {
 	/* Ordering of fields matters.  See states_equal() */
 	enum bpf_reg_type type;
@@ -180,7 +186,7 @@ struct bpf_reg_state {
 	s32 subreg_def;
 	enum bpf_reg_liveness live;
 	/* if (!precise && SCALAR_VALUE) min/max/tnum don't affect safety */
-	bool precise;
+	enum bpf_reg_precise precise;
 };
 
 enum bpf_stack_slot_type {
@@ -624,8 +630,6 @@ int bpf_check_attach_target(struct bpf_verifier_log *log,
 			    struct bpf_attach_target_info *tgt_info);
 void bpf_free_kfunc_btf_tab(struct bpf_kfunc_btf_tab *tab);
 
-int mark_chain_precision(struct bpf_verifier_env *env, int regno);
-
 #define BPF_BASE_TYPE_MASK	GENMASK(BPF_BASE_TYPE_BITS - 1, 0)
 
 /* extract base type from bpf_{arg, return, reg}_type. */
kernel/bpf/verifier.c +63 -38

287 lines not on this page · raw message

Signature · 1 line
2.38.1
author maintainer
#40 lore raw

PATCH v4 19/24 bpf: Introduce bpf_obj_new

In reply to Kumar Kartikeya Dwivedi

Introduce type safe memory allocator bpf_obj_new for BPF programs. The kernel side kfunc is named bpf_obj_new_impl, as passing hidden arguments to kfuncs still requires having them in prototype, unlike BPF helpers which always take 5 arguments and have them checked using bpf_func_proto in verifier, ignoring unset argument types.

Introduce __ign suffix to ignore a specific kfunc argument during type checks, then use this to introduce support for passing type metadata to the bpf_obj_new_impl kfunc.

The user passes BTF ID of the type it wants to allocates in program BTF, the verifier then rewrites the first argument as the size of this type, after performing some sanity checks (to ensure it exists and it is a struct type).

The second argument is also fixed up and passed by the verifier. This is the btf_struct_meta for the type being allocated. It would be needed mostly for the offset array which is required for zero initializing special fields while leaving the rest of storage in unitialized state.

It would also be needed in the next patch to perform proper destruction of the object's special fields.

A convenience macro is included in the bpf_experimental.h header to hide over the ugly details of the implementation, leading to user code looking similar to a language level extension which allocates and constructs fields of a user type.

struct bar {
	struct bpf_list_node node;
};
struct foo {
	struct bpf_spin_lock lock;
	struct bpf_list_head head __contains(bar, node);
};
void prog(void) {
	struct foo *f;

	f = bpf_obj_new(typeof(*f));
	if (!f)
		return;
	...
}

A key piece of this story is still missing, i.e. the free function, which will come in the next patch.

---
 include/linux/bpf.h                           |  21 ++--
 include/linux/bpf_verifier.h                  |   2 +
 kernel/bpf/core.c                             |  16 +++
 kernel/bpf/helpers.c                          |  41 +++++--
 kernel/bpf/verifier.c                         | 107 ++++++++++++++++--
 .../testing/selftests/bpf/bpf_experimental.h  |  20 ++++
 6 files changed, 184 insertions(+), 23 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/bpf_experimental.h
include/linux/bpf.h +13 -8
index 5d9a786e0cef..efce66b2e220 100644
@@ -54,6 +54,8 @@ struct cgroup;
 extern struct idr btf_idr;
 extern spinlock_t btf_idr_lock;
 extern struct kobject *btf_kobj;
+extern struct bpf_mem_alloc bpf_global_ma;
+extern bool bpf_global_ma_set;
 
 typedef u64 (*bpf_callback_t)(u64, u64, u64, u64, u64);
 typedef int (*bpf_iter_init_seq_priv_t)(void *private_data,
@@ -334,16 +336,19 @@ static inline bool btf_record_has_field(const struct btf_record *rec, enum btf_f
 	return rec->field_mask & type;
 }
 
-static inline void check_and_init_map_value(struct bpf_map *map, void *dst)
+static inline void bpf_obj_init(const struct btf_field_offs *foffs, void *obj)
 {
-	if (!IS_ERR_OR_NULL(map->record)) {
-		struct btf_field *fields = map->record->fields;
-		u32 cnt = map->record->cnt;
-		int i;
+	int i;
 
-		for (i = 0; i < cnt; i++)
-			memset(dst + fields[i].offset, 0, btf_field_type_size(fields[i].type));
-	}
+	if (!foffs)
+		return;
+	for (i = 0; i < foffs->cnt; i++)
+		memset(obj + foffs->field_off[i], 0, foffs->field_sz[i]);
+}
+
+static inline void check_and_init_map_value(struct bpf_map *map, void *dst)
+{
+	bpf_obj_init(map->field_offs, dst);
 }
 
 /* memcpy that is used with 8-byte aligned pointers, power-of-8 size and
include/linux/bpf_verifier.h +2 -0
index 2614892ca063..1e9c782e0974 100644
@@ -426,6 +426,8 @@ struct bpf_insn_aux_data {
 		 */
 		struct bpf_loop_inline_state loop_inline_state;
 	};
+	u64 obj_new_size; /* remember the size of type passed to bpf_obj_new to rewrite R1 */
+	struct btf_struct_meta *kptr_struct_meta;
 	u64 map_key_state; /* constant (32 bit) key tracking for maps */
 	int ctx_field_size; /* the ctx field size for load insn, maybe 0 */
 	u32 seen; /* this insn was processed by the verifier at env->pass_cnt */
kernel/bpf/core.c +16 -0
index 9c16338bcbe8..2e57fc839a5c 100644
@@ -34,6 +34,7 @@
 #include <linux/log2.h>
 #include <linux/bpf_verifier.h>
 #include <linux/nodemask.h>
+#include <linux/bpf_mem_alloc.h>
 
 #include <asm/barrier.h>
 #include <asm/unaligned.h>
@@ -60,6 +61,9 @@
 #define CTX	regs[BPF_REG_CTX]
 #define IMM	insn->imm
 
+struct bpf_mem_alloc bpf_global_ma;
+bool bpf_global_ma_set;
+
 /* No hurry in this branch
  *
  * Exported for the bpf jit load helper.
@@ -2746,6 +2750,18 @@ int __weak bpf_arch_text_invalidate(void *dst, size_t len)
 	return -ENOTSUPP;
 }
 
+#ifdef CONFIG_BPF_SYSCALL
+static int __init bpf_global_ma_init(void)
+{
+	int ret;
+
+	ret = bpf_mem_alloc_init(&bpf_global_ma, 0, false);
+	bpf_global_ma_set = !ret;
+	return ret;
+}
+late_initcall(bpf_global_ma_init);
+#endif
+
 DEFINE_STATIC_KEY_FALSE(bpf_stats_enabled_key);
 EXPORT_SYMBOL(bpf_stats_enabled_key);
 
kernel/bpf/helpers.c +34 -7

68 lines not on this page · raw message

kernel/bpf/verifier.c +99 -8

165 lines not on this page · raw message

tools/testing/selftests/bpf/bpf_experimental.h new file +20 -0
new file mode 100644
index 000000000000..1d3451084a68
@@ -0,0 +1,20 @@
+#include <vmlinux.h>
+#include <bpf/bpf_tracing.h>
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_core_read.h>
+
+/* Description
+ *	Allocates a local kptr of type represented by 'local_type_id' in program
+ *	BTF. User may use the bpf_core_type_id_local macro to pass the type ID
+ *	of a struct in program BTF.
+ *
+ *	The 'local_type_id' parameter must be a known constant.
+ *	The 'meta' parameter is a hidden argument that is ignored.
+ * Returns
+ *	A local kptr corresponding to passed in 'local_type_id', or NULL on
+ *	failure.
+ */
+extern void *bpf_obj_new_impl(__u64 local_type_id, void *meta) __ksym;
+
+/* Convenience macro to wrap over bpf_obj_new_impl */
+#define bpf_obj_new(type) bpf_obj_new_impl(bpf_core_type_id_local(type), NULL)
Signature · 1 line
2.38.1
#41 lore raw

Re: [PATCH bpf-next v4 19/24] bpf: Introduce bpf_obj_new

Quoted 51 lines · Kumar Kartikeya Dwivedi

Introduce type safe memory allocator bpf_obj_new for BPF programs. The kernel side kfunc is named bpf_obj_new_impl, as passing hidden arguments to kfuncs still requires having them in prototype, unlike BPF helpers which always take 5 arguments and have them checked using bpf_func_proto in verifier, ignoring unset argument types.

Introduce __ign suffix to ignore a specific kfunc argument during type checks, then use this to introduce support for passing type metadata to the bpf_obj_new_impl kfunc.

The user passes BTF ID of the type it wants to allocates in program BTF, the verifier then rewrites the first argument as the size of this type, after performing some sanity checks (to ensure it exists and it is a struct type).

The second argument is also fixed up and passed by the verifier. This is the btf_struct_meta for the type being allocated. It would be needed mostly for the offset array which is required for zero initializing special fields while leaving the rest of storage in unitialized state.

It would also be needed in the next patch to perform proper destruction of the object's special fields.

A convenience macro is included in the bpf_experimental.h header to hide over the ugly details of the implementation, leading to user code looking similar to a language level extension which allocates and constructs fields of a user type.

struct bar {
	struct bpf_list_node node;
};
struct foo {
	struct bpf_spin_lock lock;
	struct bpf_list_head head __contains(bar, node);
};
void prog(void) {
	struct foo *f;

	f = bpf_obj_new(typeof(*f));
	if (!f)
		return;
	...
}

A key piece of this story is still missing, i.e. the free function, which will come in the next patch.

---

[...]

tools/testing/selftests/bpf/bpf_experimental.h

Quoted 5 lines
tools/testing/selftests/bpf/bpf_experimental.h new file +0 -0
new file mode 100644
index 000000000000..1d3451084a68

Maybe bpf_experimental.h should go in libbpf as part of this series? If including vmlinux.h is an issue - nothing in libbpf currently includes it - you could rely on the BPF program including it, with a comment similar to "Note that bpf programs need to include..." in lib/bpf/bpf_helpers.h .

Quoted 21 lines
tools/testing/selftests/bpf/bpf_experimental.h new file +20 -0
@@ -0,0 +1,20 @@
+#include <vmlinux.h>
+#include <bpf/bpf_tracing.h>
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_core_read.h>
+
+/* Description
+ *	Allocates a local kptr of type represented by 'local_type_id' in program
+ *	BTF. User may use the bpf_core_type_id_local macro to pass the type ID
+ *	of a struct in program BTF.
+ *
+ *	The 'local_type_id' parameter must be a known constant.
+ *	The 'meta' parameter is a hidden argument that is ignored.
+ * Returns
+ *	A local kptr corresponding to passed in 'local_type_id', or NULL on
+ *	failure.
+ */
+extern void *bpf_obj_new_impl(__u64 local_type_id, void *meta) __ksym;
+
+/* Convenience macro to wrap over bpf_obj_new_impl */
+#define bpf_obj_new(type) bpf_obj_new_impl(bpf_core_type_id_local(type), NULL)
author maintainer
#42 lore raw

Re: [PATCH bpf-next v4 19/24] bpf: Introduce bpf_obj_new

Quoted 55 lines · Dave Marchevsky
Quoted 51 lines · Kumar Kartikeya Dwivedi

Introduce type safe memory allocator bpf_obj_new for BPF programs. The kernel side kfunc is named bpf_obj_new_impl, as passing hidden arguments to kfuncs still requires having them in prototype, unlike BPF helpers which always take 5 arguments and have them checked using bpf_func_proto in verifier, ignoring unset argument types.

Introduce __ign suffix to ignore a specific kfunc argument during type checks, then use this to introduce support for passing type metadata to the bpf_obj_new_impl kfunc.

The user passes BTF ID of the type it wants to allocates in program BTF, the verifier then rewrites the first argument as the size of this type, after performing some sanity checks (to ensure it exists and it is a struct type).

The second argument is also fixed up and passed by the verifier. This is the btf_struct_meta for the type being allocated. It would be needed mostly for the offset array which is required for zero initializing special fields while leaving the rest of storage in unitialized state.

It would also be needed in the next patch to perform proper destruction of the object's special fields.

A convenience macro is included in the bpf_experimental.h header to hide over the ugly details of the implementation, leading to user code looking similar to a language level extension which allocates and constructs fields of a user type.

struct bar {
	struct bpf_list_node node;
};
struct foo {
	struct bpf_spin_lock lock;
	struct bpf_list_head head __contains(bar, node);
};
void prog(void) {
	struct foo *f;

	f = bpf_obj_new(typeof(*f));
	if (!f)
		return;
	...
}

A key piece of this story is still missing, i.e. the free function, which will come in the next patch.

---

[...]

Quoted 11 lines

tools/testing/selftests/bpf/bpf_experimental.h

Quoted 5 lines
tools/testing/selftests/bpf/bpf_experimental.h new file +0 -0
new file mode 100644
index 000000000000..1d3451084a68

Maybe bpf_experimental.h should go in libbpf as part of this series? If including vmlinux.h is an issue - nothing in libbpf currently includes it - you could rely on the BPF program including it, with a comment similar to "Note that bpf programs need to include..." in lib/bpf/bpf_helpers.h .

I don't have a problem with that, but I would like to also know Andrii's opinion on this, since it won't work properly if people don't keep libbpf and kernel version in sync.

#43 lore raw

Re: [PATCH bpf-next v4 19/24] bpf: Introduce bpf_obj_new

Quoted 69 lines · Kumar Kartikeya Dwivedi
Quoted 55 lines · Dave Marchevsky
Quoted 51 lines · Kumar Kartikeya Dwivedi

Introduce type safe memory allocator bpf_obj_new for BPF programs. The kernel side kfunc is named bpf_obj_new_impl, as passing hidden arguments to kfuncs still requires having them in prototype, unlike BPF helpers which always take 5 arguments and have them checked using bpf_func_proto in verifier, ignoring unset argument types.

Introduce __ign suffix to ignore a specific kfunc argument during type checks, then use this to introduce support for passing type metadata to the bpf_obj_new_impl kfunc.

The user passes BTF ID of the type it wants to allocates in program BTF, the verifier then rewrites the first argument as the size of this type, after performing some sanity checks (to ensure it exists and it is a struct type).

The second argument is also fixed up and passed by the verifier. This is the btf_struct_meta for the type being allocated. It would be needed mostly for the offset array which is required for zero initializing special fields while leaving the rest of storage in unitialized state.

It would also be needed in the next patch to perform proper destruction of the object's special fields.

A convenience macro is included in the bpf_experimental.h header to hide over the ugly details of the implementation, leading to user code looking similar to a language level extension which allocates and constructs fields of a user type.

struct bar {
    struct bpf_list_node node;
};
struct foo {
    struct bpf_spin_lock lock;
    struct bpf_list_head head __contains(bar, node);
};
void prog(void) {
    struct foo *f;

    f = bpf_obj_new(typeof(*f));
    if (!f)
            return;
    ...
}

A key piece of this story is still missing, i.e. the free function, which will come in the next patch.

---

[...]

Quoted 11 lines

tools/testing/selftests/bpf/bpf_experimental.h

Quoted 5 lines
tools/testing/selftests/bpf/bpf_experimental.h new file +0 -0
new file mode 100644
index 000000000000..1d3451084a68

Maybe bpf_experimental.h should go in libbpf as part of this series? If including vmlinux.h is an issue - nothing in libbpf currently includes it - you could rely on the BPF program including it, with a comment similar to "Note that bpf programs need to include..." in lib/bpf/bpf_helpers.h .

Quoted 3 lines

I don't have a problem with that, but I would like to also know Andrii's opinion on this, since it won't work properly if people don't keep libbpf and kernel version in sync.

let's do the directory bikeshedding later. bpf_experimental.h can be moved to libbpf dir in the follow up.

author maintainer
#44 lore raw

PATCH v4 20/24 bpf: Introduce bpf_obj_drop

In reply to Kumar Kartikeya Dwivedi

Introduce bpf_obj_drop, which is the kfunc used to free local kptrs allocated using bpf_obj_new. Similar to bpf_obj_new, it implicitly destructs the fields part of the local kptr automatically without user intervention.

Just like the previous patch, btf_struct_meta that is needed to free up the special fields is passed as a hidden argument to the kfunc.

For the user, a convenience macro hides over the kernel side kfunc which is named bpf_obj_drop_impl.

Continuing the previous example:

void prog(void) {
	struct foo *f;

	f = bpf_obj_new(typeof(*f));
	if (!f)
		return;
	bpf_obj_drop(f);
}
---
 kernel/bpf/helpers.c                          | 11 ++++
 kernel/bpf/verifier.c                         | 66 +++++++++++++++----
 .../testing/selftests/bpf/bpf_experimental.h  | 13 ++++
 3 files changed, 79 insertions(+), 11 deletions(-)
kernel/bpf/helpers.c +11 -0
index e10245e054e4..a30f6573e805 100644
@@ -1764,6 +1764,16 @@ void *bpf_obj_new_impl(u64 local_type_id__k, void *meta__ign)
 	return p;
 }
 
+void bpf_obj_drop_impl(void *p__lkptr, void *meta__ign)
+{
+	struct btf_struct_meta *meta = meta__ign;
+	void *p = p__lkptr;
+
+	if (meta)
+		bpf_obj_free_fields(meta->record, p);
+	bpf_mem_free(&bpf_global_ma, p);
+}
+
 __diag_pop();
 
 BTF_SET8_START(generic_btf_ids)
@@ -1771,6 +1781,7 @@ BTF_SET8_START(generic_btf_ids)
 BTF_ID_FLAGS(func, crash_kexec, KF_DESTRUCTIVE)
 #endif
 BTF_ID_FLAGS(func, bpf_obj_new_impl, KF_ACQUIRE | KF_RET_NULL)
+BTF_ID_FLAGS(func, bpf_kptr_drop_impl, KF_RELEASE)
 BTF_SET8_END(generic_btf_ids)
 
 static const struct btf_kfunc_id_set generic_kfunc_set = {
kernel/bpf/verifier.c +55 -11

126 lines not on this page · raw message

tools/testing/selftests/bpf/bpf_experimental.h +13 -0
index 1d3451084a68..29a5520a4250 100644
@@ -18,3 +18,16 @@ extern void *bpf_obj_new_impl(__u64 local_type_id, void *meta) __ksym;
 
 /* Convenience macro to wrap over bpf_obj_new_impl */
 #define bpf_obj_new(type) bpf_obj_new_impl(bpf_core_type_id_local(type), NULL)
+
+/* Description
+ *	Free a local kptr. All fields of local kptr that require destruction
+ *	will be destructed before the storage is freed.
+ *
+ *	The 'meta' parameter is a hidden argument that is ignored.
+ * Returns
+ *	Void.
+ */
+extern void bpf_obj_drop_impl(void *kptr, void *meta) __ksym;
+
+/* Convenience macro to wrap over bpf_obj_drop_impl */
+#define bpf_obj_drop(kptr) bpf_obj_drop_impl(kptr, NULL)
Signature · 1 line
2.38.1
author maintainer
#45 lore raw

PATCH v4 21/24 bpf: Permit NULL checking pointer with non-zero fixed offset

In reply to Kumar Kartikeya Dwivedi

Pointer increment on seeing PTR_MAYBE_NULL is already protected against, hence make an exception for local kptrs while still keeping the warning for other unintended cases that might creep in.

bpf_list_del{,tail} helpers return a local kptr with incremented offset pointing to bpf_list_node field. The user is supposed to then obtain the pointer to the entry using container_of after NULL checking it. The current restrictions trigger a warning when doing the NULL checking. Revisiting the reason, it is meant as an assertion which seems to actually work and catch the bad case.

Hence, under no other circumstances can reg->off be non-zero for a register that has the PTR_MAYBE_NULL type flag set.

---
 kernel/bpf/verifier.c | 13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)
kernel/bpf/verifier.c +9 -4
index 1e72e559ea6b..58e58678382a 100644
@@ -10622,15 +10622,20 @@ static void mark_ptr_or_null_reg(struct bpf_func_state *state,
 {
 	if (type_may_be_null(reg->type) && reg->id == id &&
 	    !WARN_ON_ONCE(!reg->id)) {
-		if (WARN_ON_ONCE(reg->smin_value || reg->smax_value ||
-				 !tnum_equals_const(reg->var_off, 0) ||
-				 reg->off)) {
+		if (reg->smin_value || reg->smax_value || !tnum_equals_const(reg->var_off, 0) || reg->off) {
 			/* Old offset (both fixed and variable parts) should
 			 * have been known-zero, because we don't allow pointer
 			 * arithmetic on pointers that might be NULL. If we
 			 * see this happening, don't convert the register.
+			 *
+			 * But in some cases, some helpers that return local
+			 * kptrs advance offset for the returned pointer.
+			 * In those cases, it is fine to expect to see reg->off.
 			 */
-			return;
+			if (WARN_ON_ONCE(reg->type != (PTR_TO_BTF_ID | MEM_TYPE_LOCAL | PTR_MAYBE_NULL)))
+				return;
+			if (WARN_ON_ONCE(reg->smin_value || reg->smax_value || !tnum_equals_const(reg->var_off, 0)))
+				return;
 		}
 		if (is_null) {
 			reg->type = SCALAR_VALUE;
Signature · 1 line
2.38.1
author maintainer
#46 lore raw

PATCH v4 22/24 bpf: Introduce single ownership BPF linked list API

In reply to Kumar Kartikeya Dwivedi

Add a linked list API for use in BPF programs, where it expects protection from the bpf_spin_lock in the same allocation as the bpf_list_head. Future patches will extend the same infrastructure to have different flavors with varying protection domains and visibility (e.g. percpu variant with local_t protection, usable in NMI progs).

The following functions are added to kick things off:

bpf_list_push_front
bpf_list_push_back
bpf_list_pop_front
bpf_list_pop_back

The lock protecting the bpf_list_head needs to be taken for all operations.

Once a node has been added to the list, it's pointer changes to PTR_UNTRUSTED. However, it is only released once the lock protecting the list is unlocked. For such local kptrs with PTR_UNTRUSTED set but an active ref_obj_id, it is still permitted to read and write to them as long as the lock is held.

bpf_list_pop_front and bpf_list_pop_back delete the first or last item of the list respectively, and return pointer to the element at the list_node offset. The user can then use container_of style macro to get the actual entry type. The verifier however statically knows the actual type, so the safety properties are still preserved.

With these additions, programs can now manage their own linked lists and store their objects in them.

---
 include/linux/bpf_verifier.h                  |   5 +
 kernel/bpf/helpers.c                          |  50 ++-
 kernel/bpf/verifier.c                         | 377 ++++++++++++++++--
 .../testing/selftests/bpf/bpf_experimental.h  |  28 ++
 4 files changed, 425 insertions(+), 35 deletions(-)
include/linux/bpf_verifier.h +5 -0
index 1e9c782e0974..bde8f9e11132 100644
@@ -229,6 +229,11 @@ struct bpf_reference_state {
 	 * exiting a callback function.
 	 */
 	int callback_ref;
+	/* Mark the reference state to release the registers sharing the same id
+	 * on bpf_spin_unlock (for nodes that we will lose ownership to but are
+	 * safe to access inside the critical section).
+	 */
+	bool release_on_unlock;
 };
 
 /* state of the program:
kernel/bpf/helpers.c +49 -1

62 lines not on this page · raw message

kernel/bpf/verifier.c +343 -34

491 lines not on this page · raw message

tools/testing/selftests/bpf/bpf_experimental.h +28 -0
index 29a5520a4250..4a76c64e50ad 100644
@@ -31,3 +31,31 @@ extern void bpf_obj_drop_impl(void *kptr, void *meta) __ksym;
 
 /* Convenience macro to wrap over bpf_obj_drop_impl */
 #define bpf_obj_drop(kptr) bpf_obj_drop_impl(kptr, NULL)
+
+/* Description
+ *	Add a new entry to the beginning of the BPF linked list.
+ * Returns
+ *	Void.
+ */
+extern void bpf_list_push_front(struct bpf_list_head *head, struct bpf_list_node *node) __ksym;
+
+/* Description
+ *	Add a new entry to the end of the BPF linked list.
+ * Returns
+ *	Void.
+ */
+extern void bpf_list_push_back(struct bpf_list_head *head, struct bpf_list_node *node) __ksym;
+
+/* Description
+ *	Remove the entry at the beginning of the BPF linked list.
+ * Returns
+ *	Pointer to bpf_list_node of deleted entry, or NULL if list is empty.
+ */
+extern struct bpf_list_node *bpf_list_pop_front(struct bpf_list_head *head) __ksym;
+
+/* Description
+ *	Remove the entry at the end of the BPF linked list.
+ * Returns
+ *	Pointer to bpf_list_node of deleted entry, or NULL if list is empty.
+ */
+extern struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) __ksym;
Signature · 1 line
2.38.1
#47 lore raw

Re: [PATCH bpf-next v4 22/24] bpf: Introduce single ownership BPF linked list API

Quoted 13 lines · Kumar Kartikeya Dwivedi

Add a linked list API for use in BPF programs, where it expects protection from the bpf_spin_lock in the same allocation as the bpf_list_head. Future patches will extend the same infrastructure to have different flavors with varying protection domains and visibility (e.g. percpu variant with local_t protection, usable in NMI progs).

The following functions are added to kick things off:

bpf_list_push_front
bpf_list_push_back
bpf_list_pop_front
bpf_list_pop_back

Quoted 8 lines

The lock protecting the bpf_list_head needs to be taken for all operations.

Once a node has been added to the list, it's pointer changes to PTR_UNTRUSTED. However, it is only released once the lock protecting the list is unlocked. For such local kptrs with PTR_UNTRUSTED set but an active ref_obj_id, it is still permitted to read and write to them as long as the lock is held.

I think "still permitted to ... write to them" is not accurate for this version of the series. In v2 you mentioned [0]:

"""
I have switched things a bit to disallow stores, which is a bug right now in this set, because one can do this:

push_front(head, &p->node);
p2 = container_of(pop_front(head));
// p2 == p
bpf_obj_drop(p2);
p->data = ...;

One can always fully initialize the object _before_ inserting it into the list, in some cases that will be the requirement (like adding to RCU protected lists) for correctness.
"""

I confirmed this is currently the case by moving data write after list_push in the selftest and running it:

@@ -87,8 +87,8 @@ static __always_inline int list_push_pop(struct bpf_spin_lock *lock,

        }

        bpf_spin_lock(lock);
-       f->data = 13;
        bpf_list_push_front(head, &f->node);
+       f->data = 13;
        bpf_spin_unlock(lock);

Got "only read is supported" from verifier.
I think it's fine to punt on supporting writes for now and do it in followups.

[0]: https://lore.kernel.org/bpf/20221025190033.bqjr7466o7pdd3wo@apollo/

Quoted 7 lines

bpf_list_pop_front and bpf_list_pop_back delete the first or last item of the list respectively, and return pointer to the element at the list_node offset. The user can then use container_of style macro to get the actual entry type. The verifier however statically knows the actual type, so the safety properties are still preserved.

Quoted 5 lines

With these additions, programs can now manage their own linked lists and store their objects in them.

---

[...]

will comment on rest of patch in separate msg

author maintainer
#48 lore raw

Re: [PATCH bpf-next v4 22/24] bpf: Introduce single ownership BPF linked list API

Quoted 53 lines · Dave Marchevsky
Quoted 13 lines · Kumar Kartikeya Dwivedi

Add a linked list API for use in BPF programs, where it expects protection from the bpf_spin_lock in the same allocation as the bpf_list_head. Future patches will extend the same infrastructure to have different flavors with varying protection domains and visibility (e.g. percpu variant with local_t protection, usable in NMI progs).

The following functions are added to kick things off:

bpf_list_push_front
bpf_list_push_back
bpf_list_pop_front
bpf_list_pop_back

Quoted 8 lines

The lock protecting the bpf_list_head needs to be taken for all operations.

Once a node has been added to the list, it's pointer changes to PTR_UNTRUSTED. However, it is only released once the lock protecting the list is unlocked. For such local kptrs with PTR_UNTRUSTED set but an active ref_obj_id, it is still permitted to read and write to them as long as the lock is held.

I think "still permitted to ... write to them" is not accurate for this version of the series. In v2 you mentioned [0]:

"""
I have switched things a bit to disallow stores, which is a bug right now in this set, because one can do this:

push_front(head, &p->node);
p2 = container_of(pop_front(head));
// p2 == p
bpf_obj_drop(p2);
p->data = ...;

One can always fully initialize the object _before_ inserting it into the list, in some cases that will be the requirement (like adding to RCU protected lists) for correctness.
"""

I confirmed this is currently the case by moving data write after list_push in the selftest and running it:

(quoted diff) +1 -1
@@ -87,8 +87,8 @@ static __always_inline int list_push_pop(struct bpf_spin_lock *lock,
        }
 
        bpf_spin_lock(lock);
-       f->data = 13;
        bpf_list_push_front(head, &f->node);
+       f->data = 13;
        bpf_spin_unlock(lock);
 
Quoted 3 lines

Got "only read is supported" from verifier.
I think it's fine to punt on supporting writes for now and do it in followups.

Thanks for catching it, I'll fix up the commit message.

Also, just to manage the expectations I think enabling writes after pushing the object won't be possible to make safe, unless the definition of "safe" is twisted.

As shown in that example, we can reach a point where it has been freed but we hold an untrusted pointer to it. Once it has been freed the object can be reallocated and be in use again concurrently, possibly as a different type.

I was contemplating whether to simply drop this whole set_release_on_unlock logic entirely. Not sure it's worth the added complexity, atleast for now. Once you push you simply lose ownership of the object and any registers are immediately killed.

#49 lore raw

Re: [PATCH bpf-next v4 22/24] bpf: Introduce single ownership BPF linked list API

Quoted 60 lines · Kumar Kartikeya Dwivedi
Quoted 53 lines · Dave Marchevsky
Quoted 13 lines · Kumar Kartikeya Dwivedi

Add a linked list API for use in BPF programs, where it expects protection from the bpf_spin_lock in the same allocation as the bpf_list_head. Future patches will extend the same infrastructure to have different flavors with varying protection domains and visibility (e.g. percpu variant with local_t protection, usable in NMI progs).

The following functions are added to kick things off:

bpf_list_push_front
bpf_list_push_back
bpf_list_pop_front
bpf_list_pop_back

Quoted 8 lines

The lock protecting the bpf_list_head needs to be taken for all operations.

Once a node has been added to the list, it's pointer changes to PTR_UNTRUSTED. However, it is only released once the lock protecting the list is unlocked. For such local kptrs with PTR_UNTRUSTED set but an active ref_obj_id, it is still permitted to read and write to them as long as the lock is held.

I think "still permitted to ... write to them" is not accurate for this version of the series. In v2 you mentioned [0]:

"""
I have switched things a bit to disallow stores, which is a bug right now in this set, because one can do this:

push_front(head, &p->node);
p2 = container_of(pop_front(head));
// p2 == p
bpf_obj_drop(p2);
p->data = ...;

One can always fully initialize the object _before_ inserting it into the list, in some cases that will be the requirement (like adding to RCU protected lists) for correctness.
"""

I confirmed this is currently the case by moving data write after list_push in the selftest and running it:

(quoted diff) +1 -1
@@ -87,8 +87,8 @@ static __always_inline int list_push_pop(struct bpf_spin_lock *lock,
        }
 
        bpf_spin_lock(lock);
-       f->data = 13;
        bpf_list_push_front(head, &f->node);
+       f->data = 13;
        bpf_spin_unlock(lock);
 
Quoted 3 lines

Got "only read is supported" from verifier.
I think it's fine to punt on supporting writes for now and do it in followups.

Thanks for catching it, I'll fix up the commit message.

Quoted 7 lines

Also, just to manage the expectations I think enabling writes after pushing the object won't be possible to make safe, unless the definition of "safe" is twisted.

As shown in that example, we can reach a point where it has been freed but we hold an untrusted pointer to it. Once it has been freed the object can be reallocated and be in use again concurrently, possibly as a different type.

I think this patchset prevents that example from passing verifier, provided that bpf_spin_{lock,unlock} are added in the right places:

  p = bpf_obj_new(typeof(*p));
  if (!p)
    return;

  bpf_spin_lock(lock);
  push_front(head, &p->node);
  p2 = container_of(pop_front(head));
  // p2 == p
  if (!p2)
    return;
  bpf_spin_unlock(lock);

  bpf_obj_drop(p2);
  p->data = ...;

After bpf_obj_new R0 is of type ptr_or_null_BTF_TYPE with nonzero ref_obj_id, let's say 1.
After null check any regs holding p have _or_null removed.

After push_front any regs w/ ref_obj_id==1 become untrusted and have release_on_unlock set. After pop_front R0 is ptr_or_null_BTF_TYPE with nonzero ref_obj_id different than bpf_obj_new result, let's say 2.
Null check works same way as before.

After bpf_spin_unlock all release_on_unlock references are clobbered, so p->data will result in "invalid mem access 'scalar'" verifier error.

Verifier requires list manipulation functions to be in a critical section and doesn't allow bpf_obj_new or bpf_obj_drop in the critical section. p2 == p but having different ref_obj_ids is OK because only p2 will escape bpf_spin_unlock unclobbered to be released by bpf_obj_drop, and no free()s are allowed until we're out of the critical section. So by the time we can call bpf_obj_drop we only have one valid reference remaining ("trusted" one).

My OBJ_NON_OWNING_REF stuff in rbtree patchsets had same logic, IIRC only difference is that my "add to datastructure" function was considered a RELEASE func that also did an ACQUIRE of a release_on_unlock retval. But this was before static lock checking discussions, so the RELEASE/ACQUIRE could fail. I think directly modifying arg reg like you're doing in set_release_on_unlock is cleaner.

Quoted 4 lines

I was contemplating whether to simply drop this whole set_release_on_unlock logic entirely. Not sure it's worth the added complexity, atleast for now. Once you push you simply lose ownership of the object and any registers are immediately killed.

I think that being able to read / modify the datastructure node after it's been added is pretty critical, at least from a UX perspective.

Totally fine with it being dropped from the series and experimented with later, though.

#50 lore raw

Re: [PATCH bpf-next v4 22/24] bpf: Introduce single ownership BPF linked list API

Quoted 11 lines · Dave Marchevsky
Quoted 5 lines

I was contemplating whether to simply drop this whole set_release_on_unlock logic entirely. Not sure it's worth the added complexity, atleast for now. Once you push you simply lose ownership of the object and any registers are immediately killed.

I think that being able to read / modify the datastructure node after it's been added is pretty critical, at least from a UX perspective.

Totally fine with it being dropped from the series and experimented with later, though.

Kumar,
please split release_on_unlock logic into separate patch. afaics it doesn't have to be introduced together with these kfuncs.

author maintainer
#51 lore raw

Re: [PATCH bpf-next v4 22/24] bpf: Introduce single ownership BPF linked list API

Quoted 11 lines · Alexei Starovoitov
Quoted 9 lines · Dave Marchevsky
Quoted 5 lines

I was contemplating whether to simply drop this whole set_release_on_unlock logic entirely. Not sure it's worth the added complexity, atleast for now. Once you push you simply lose ownership of the object and any registers are immediately killed.

I think that being able to read / modify the datastructure node after it's been added is pretty critical, at least from a UX perspective.

Quoted 6 lines
Quoted 2 lines

Totally fine with it being dropped from the series and experimented with later, though.

Kumar,
please split release_on_unlock logic into separate patch. afaics it doesn't have to be introduced together with these kfuncs.

Ack.

author maintainer
#52 lore raw

PATCH v4 23/24 selftests/bpf: Add __contains macro to bpf_experimental.h

In reply to Kumar Kartikeya Dwivedi

Add user facing __contains macro which provides a convenient wrapper over the verbose kernel specific BTF declaration tag required to annotate BPF list head structs in user types.

---
 tools/testing/selftests/bpf/bpf_experimental.h | 2 ++
 1 file changed, 2 insertions(+)
tools/testing/selftests/bpf/bpf_experimental.h +2 -0
index 4a76c64e50ad..3db1578db2d9 100644
@@ -3,6 +3,8 @@
 #include <bpf/bpf_helpers.h>
 #include <bpf/bpf_core_read.h>
 
+#define __contains(name, node) __attribute__((btf_decl_tag("contains:" #name ":" #node)))
+
 /* Description
  *	Allocates a local kptr of type represented by 'local_type_id' in program
  *	BTF. User may use the bpf_core_type_id_local macro to pass the type ID
Signature · 1 line
2.38.1
author maintainer
#53 lore raw

PATCH v4 24/24 selftests/bpf: Add BPF linked list API tests

In reply to Kumar Kartikeya Dwivedi

Include various tests covering the success and failure cases. Also, run the success cases at runtime to verify correctness of linked list manipulation routines, in addition to ensuring successful verification.

---
 kernel/bpf/helpers.c                          |   5 +-
 tools/testing/selftests/bpf/DENYLIST.s390x    |   1 +
 .../selftests/bpf/prog_tests/linked_list.c    |  79 +++++
 .../testing/selftests/bpf/progs/linked_list.c | 330 ++++++++++++++++++
 4 files changed, 414 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/linked_list.c
 create mode 100644 tools/testing/selftests/bpf/progs/linked_list.c
kernel/bpf/helpers.c +4 -1
index 0acd87ed22fc..db4398a5bb35 100644
@@ -1839,7 +1839,10 @@ static const struct btf_kfunc_id_set generic_kfunc_set = {
 
 static int __init kfunc_init(void)
 {
-	return register_btf_kfunc_id_set(BPF_PROG_TYPE_TRACING, &generic_kfunc_set);
+	int ret;
+
+	ret = register_btf_kfunc_id_set(BPF_PROG_TYPE_TRACING, &generic_kfunc_set);
+	return ret ?: register_btf_kfunc_id_set(BPF_PROG_TYPE_SCHED_CLS, &generic_kfunc_set);
 }
 
 late_initcall(kfunc_init);
tools/testing/selftests/bpf/DENYLIST.s390x +1 -0
index be4e3d47ea3e..072243af93b0 100644
@@ -33,6 +33,7 @@ ksyms_module                             # test_ksyms_module__open_and_load unex
 ksyms_module_libbpf                      # JIT does not support calling kernel function                                (kfunc)
 ksyms_module_lskel                       # test_ksyms_module_lskel__open_and_load unexpected error: -9                 (?)
 libbpf_get_fd_by_id_opts                 # failed to attach: ERROR: strerror_r(-524)=22                                (trampoline)
+linked_list				 # JIT does not support calling kernel function                                (kfunc)
 lookup_key                               # JIT does not support calling kernel function                                (kfunc)
 lru_bug                                  # prog 'printk': failed to auto-attach: -524
 map_kptr                                 # failed to open_and_load program: -524 (trampoline)
tools/testing/selftests/bpf/prog_tests/linked_list.c new file +79 -0

79 lines not on this page · raw message

tools/testing/selftests/bpf/progs/linked_list.c new file +330 -0

330 lines not on this page · raw message

Signature · 1 line
2.38.1
#54 lore raw

Re: [PATCH bpf-next v4 24/24] selftests/bpf: Add BPF linked list API tests

Quoted 6 lines · Kumar Kartikeya Dwivedi

Include various tests covering the success and failure cases. Also, run the success cases at runtime to verify correctness of linked list manipulation routines, in addition to ensuring successful verification.

---

[...]

Quoted 33 lines
tools/testing/selftests/bpf/progs/linked_list.c new file +27 -0
new file mode 100644
index 000000000000..eed0b2c1eb4a
@@ -0,0 +1,330 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <vmlinux.h>
+#include <bpf/bpf_tracing.h>
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_core_read.h>
+#include "bpf_experimental.h"
+
+#ifndef ARRAY_SIZE
+#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
+#endif
+
+struct bar {
+	struct bpf_list_node node;
+	int data;
+};
+
+struct foo {
+	struct bpf_list_node node;
+	struct bpf_list_head head __contains(bar, node);
+	struct bpf_spin_lock lock;
+	int data;
+};
+
+struct map_value {
+	struct bpf_list_head head __contains(foo, node);
+	struct bpf_spin_lock lock;
+	int data;

tools/testing/selftests/bpf/progs/linked_list.c line 37

Quoted 10 lines
tools/testing/selftests/bpf/progs/linked_list.c new file +10 -0
+};
+
+struct array_map {
+	__uint(type, BPF_MAP_TYPE_ARRAY);
+	__type(key, int);
+	__type(value, struct map_value);
+	__uint(max_entries, 1);
+} array_map SEC(".maps");
+
+#define private(name) SEC(".data." #name) __hidden __attribute__((aligned(8)))

This __attribute__((aligned(8))) causes my clang to fail to build this selftest. It fails with:

fatal error: error in backend: unable to write nop sequence of 4 bytes

Tracked it down to llvm/lib/Target/BPF/MCTargetDesc/BPFAsmBackend.cpp:

bool BPFAsmBackend::writeNopData(raw_ostream &OS, uint64_t Count,

                                   const MCSubtargetInfo *STI) const {
    if ((Count % 8) != 0)
      return false;

Presumably since ".data.A" section is PROGBITS the compiler tries to write 4 bytes of nop before / between the variables, but fails.

I'm using a clang built off of a very recent LLVM commit [0]. David Vernet was able to successfully build the selftests with a clang built from late August's tree, so maybe it's my clang version or some other toolchain issue. Which clang did you use to build this?

[0]: github.com/llvm/llvm-project/commit/2a827e4a988b614bc6f70abe00308ceeb50dcd0a

author maintainer
#55 lore raw

Re: [PATCH bpf-next v4 24/24] selftests/bpf: Add BPF linked list API tests

Quoted 66 lines · Dave Marchevsky
Quoted 6 lines · Kumar Kartikeya Dwivedi

Include various tests covering the success and failure cases. Also, run the success cases at runtime to verify correctness of linked list manipulation routines, in addition to ensuring successful verification.

---

[...]

Quoted 33 lines
tools/testing/selftests/bpf/progs/linked_list.c new file +27 -0
new file mode 100644
index 000000000000..eed0b2c1eb4a
@@ -0,0 +1,330 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <vmlinux.h>
+#include <bpf/bpf_tracing.h>
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_core_read.h>
+#include "bpf_experimental.h"
+
+#ifndef ARRAY_SIZE
+#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
+#endif
+
+struct bar {
+	struct bpf_list_node node;
+	int data;
+};
+
+struct foo {
+	struct bpf_list_node node;
+	struct bpf_list_head head __contains(bar, node);
+	struct bpf_spin_lock lock;
+	int data;
+};
+
+struct map_value {
+	struct bpf_list_head head __contains(foo, node);
+	struct bpf_spin_lock lock;
+	int data;

tools/testing/selftests/bpf/progs/linked_list.c line 37

Quoted 10 lines
tools/testing/selftests/bpf/progs/linked_list.c new file +10 -0
+};
+
+struct array_map {
+	__uint(type, BPF_MAP_TYPE_ARRAY);
+	__type(key, int);
+	__type(value, struct map_value);
+	__uint(max_entries, 1);
+} array_map SEC(".maps");
+
+#define private(name) SEC(".data." #name) __hidden __attribute__((aligned(8)))

This __attribute__((aligned(8))) causes my clang to fail to build this selftest. It fails with:

fatal error: error in backend: unable to write nop sequence of 4 bytes

Tracked it down to llvm/lib/Target/BPF/MCTargetDesc/BPFAsmBackend.cpp:

bool BPFAsmBackend::writeNopData(raw_ostream &OS, uint64_t Count,

                                   const MCSubtargetInfo *STI) const {
    if ((Count % 8) != 0)
      return false;
Quoted 8 lines

Presumably since ".data.A" section is PROGBITS the compiler tries to write 4 bytes of nop before / between the variables, but fails.

I'm using a clang built off of a very recent LLVM commit [0]. David Vernet was able to successfully build the selftests with a clang built from late August's tree, so maybe it's my clang version or some other toolchain issue. Which clang did you use to build this?

Yes, I get the same ICE on clang nightly as well, specifically for linked_list test. Then I rebuilt this with clang 14.0.6.

Also, that __attribute__ is necessary because the alignment info in UAPI bpf.h is lost when it gets dumped to BTF and emitted to vmlinux.h. Since the struct only has padding bits, the default alignment is 1. Adding named fields is probably the better solution, which gives it __alignof__(u64).

Quoted 1 line

[0]: github.com/llvm/llvm-project/commit/2a827e4a988b614bc6f70abe00308ceeb50dcd0a

#56 lore raw
In reply to Kumar Kartikeya Dwivedi
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Quoted 8 lines · On Fri, 4 Nov 2022 00:39:49 +0530 you wrote:

This series introduces user defined BPF objects, by introducing the idea of local kptrs. These are kptrs (strongly typed pointers) that refer to objects of a user defined type, hence called "local" kptrs. This allows BPF programs to allocate their own objects, build their own object hierarchies, and use the basic building blocks provided by BPF runtime to build their own data structures flexibly.

[...]

Here is the summary with links:
- [bpf-next,v4,01/24] bpf: Document UAPI details for special BPF types

    https://git.kernel.org/bpf/bpf-next/c/9805af8d8a5b
  - [bpf-next,v4,02/24] bpf: Allow specifying volatile type modifier for kptrs
    https://git.kernel.org/bpf/bpf-next/c/23da464dd6b8
  - [bpf-next,v4,03/24] bpf: Clobber stack slot when writing over spilled PTR_TO_BTF_ID
    https://git.kernel.org/bpf/bpf-next/c/261f4664caff
  - [bpf-next,v4,04/24] bpf: Fix slot type check in check_stack_write_var_off
    https://git.kernel.org/bpf/bpf-next/c/f5e477a861e4
  - [bpf-next,v4,05/24] bpf: Drop reg_type_may_be_refcounted_or_null
    https://git.kernel.org/bpf/bpf-next/c/a28ace782e68
  - [bpf-next,v4,06/24] bpf: Refactor kptr_off_tab into btf_record
    https://git.kernel.org/bpf/bpf-next/c/aa3496accc41

- [bpf-next,v4,07/24] bpf: Consolidate spin_lock, timer management into btf_record (no matching commit)
- [bpf-next,v4,08/24] bpf: Refactor map->off_arr handling
(no matching commit)
- [bpf-next,v4,09/24] bpf: Support bpf_list_head in map values
(no matching commit)
- [bpf-next,v4,10/24] bpf: Introduce local kptrs
(no matching commit)
- [bpf-next,v4,11/24] bpf: Recognize bpf_{spin_lock,list_head,list_node} in local kptrs (no matching commit)
- [bpf-next,v4,12/24] bpf: Verify ownership relationships for user BTF types (no matching commit)
- [bpf-next,v4,13/24] bpf: Support locking bpf_spin_lock in local kptr (no matching commit)
- [bpf-next,v4,14/24] bpf: Allow locking bpf_spin_lock global variables (no matching commit)
- [bpf-next,v4,15/24] bpf: Rewrite kfunc argument handling
(no matching commit)
- [bpf-next,v4,16/24] bpf: Drop kfunc bits from btf_check_func_arg_match (no matching commit)
- [bpf-next,v4,17/24] bpf: Support constant scalar arguments for kfuncs (no matching commit)
- [bpf-next,v4,18/24] bpf: Teach verifier about non-size constant arguments (no matching commit)
- [bpf-next,v4,19/24] bpf: Introduce bpf_obj_new
(no matching commit)
- [bpf-next,v4,20/24] bpf: Introduce bpf_obj_drop
(no matching commit)
- [bpf-next,v4,21/24] bpf: Permit NULL checking pointer with non-zero fixed offset (no matching commit)
- [bpf-next,v4,22/24] bpf: Introduce single ownership BPF linked list API (no matching commit)
- [bpf-next,v4,23/24] selftests/bpf: Add __contains macro to bpf_experimental.h (no matching commit)
- [bpf-next,v4,24/24] selftests/bpf: Add BPF linked list API tests
(no matching commit)

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
#57 lore raw
In reply to Kumar Kartikeya Dwivedi
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Quoted 8 lines · On Fri, 4 Nov 2022 00:39:49 +0530 you wrote:

This series introduces user defined BPF objects, by introducing the idea of local kptrs. These are kptrs (strongly typed pointers) that refer to objects of a user defined type, hence called "local" kptrs. This allows BPF programs to allocate their own objects, build their own object hierarchies, and use the basic building blocks provided by BPF runtime to build their own data structures flexibly.

[...]

Here is the summary with links:
- [bpf-next,v4,01/24] bpf: Document UAPI details for special BPF types (no matching commit)
- [bpf-next,v4,02/24] bpf: Allow specifying volatile type modifier for kptrs (no matching commit)
- [bpf-next,v4,03/24] bpf: Clobber stack slot when writing over spilled PTR_TO_BTF_ID (no matching commit)
- [bpf-next,v4,04/24] bpf: Fix slot type check in check_stack_write_var_off (no matching commit)
- [bpf-next,v4,05/24] bpf: Drop reg_type_may_be_refcounted_or_null
(no matching commit)
- [bpf-next,v4,06/24] bpf: Refactor kptr_off_tab into btf_record
(no matching commit)
- [bpf-next,v4,07/24] bpf: Consolidate spin_lock, timer management into btf_record

    https://git.kernel.org/bpf/bpf-next/c/db559117828d

- [bpf-next,v4,08/24] bpf: Refactor map->off_arr handling
(no matching commit)
- [bpf-next,v4,09/24] bpf: Support bpf_list_head in map values
(no matching commit)
- [bpf-next,v4,10/24] bpf: Introduce local kptrs
(no matching commit)
- [bpf-next,v4,11/24] bpf: Recognize bpf_{spin_lock,list_head,list_node} in local kptrs (no matching commit)
- [bpf-next,v4,12/24] bpf: Verify ownership relationships for user BTF types (no matching commit)
- [bpf-next,v4,13/24] bpf: Support locking bpf_spin_lock in local kptr (no matching commit)
- [bpf-next,v4,14/24] bpf: Allow locking bpf_spin_lock global variables (no matching commit)
- [bpf-next,v4,15/24] bpf: Rewrite kfunc argument handling
(no matching commit)
- [bpf-next,v4,16/24] bpf: Drop kfunc bits from btf_check_func_arg_match (no matching commit)
- [bpf-next,v4,17/24] bpf: Support constant scalar arguments for kfuncs (no matching commit)
- [bpf-next,v4,18/24] bpf: Teach verifier about non-size constant arguments (no matching commit)
- [bpf-next,v4,19/24] bpf: Introduce bpf_obj_new
(no matching commit)
- [bpf-next,v4,20/24] bpf: Introduce bpf_obj_drop
(no matching commit)
- [bpf-next,v4,21/24] bpf: Permit NULL checking pointer with non-zero fixed offset (no matching commit)
- [bpf-next,v4,22/24] bpf: Introduce single ownership BPF linked list API (no matching commit)
- [bpf-next,v4,23/24] selftests/bpf: Add __contains macro to bpf_experimental.h (no matching commit)
- [bpf-next,v4,24/24] selftests/bpf: Add BPF linked list API tests
(no matching commit)

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
#58 lore raw
In reply to Kumar Kartikeya Dwivedi
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Quoted 8 lines · On Fri, 4 Nov 2022 00:39:49 +0530 you wrote:

This series introduces user defined BPF objects, by introducing the idea of local kptrs. These are kptrs (strongly typed pointers) that refer to objects of a user defined type, hence called "local" kptrs. This allows BPF programs to allocate their own objects, build their own object hierarchies, and use the basic building blocks provided by BPF runtime to build their own data structures flexibly.

[...]

Here is the summary with links:
- [bpf-next,v4,01/24] bpf: Document UAPI details for special BPF types (no matching commit)
- [bpf-next,v4,02/24] bpf: Allow specifying volatile type modifier for kptrs (no matching commit)
- [bpf-next,v4,03/24] bpf: Clobber stack slot when writing over spilled PTR_TO_BTF_ID (no matching commit)
- [bpf-next,v4,04/24] bpf: Fix slot type check in check_stack_write_var_off (no matching commit)
- [bpf-next,v4,05/24] bpf: Drop reg_type_may_be_refcounted_or_null
(no matching commit)
- [bpf-next,v4,06/24] bpf: Refactor kptr_off_tab into btf_record
(no matching commit)
- [bpf-next,v4,07/24] bpf: Consolidate spin_lock, timer management into btf_record (no matching commit)
- [bpf-next,v4,08/24] bpf: Refactor map->off_arr handling

    https://git.kernel.org/bpf/bpf-next/c/f71b2f64177a

- [bpf-next,v4,09/24] bpf: Support bpf_list_head in map values
(no matching commit)
- [bpf-next,v4,10/24] bpf: Introduce local kptrs
(no matching commit)
- [bpf-next,v4,11/24] bpf: Recognize bpf_{spin_lock,list_head,list_node} in local kptrs (no matching commit)
- [bpf-next,v4,12/24] bpf: Verify ownership relationships for user BTF types (no matching commit)
- [bpf-next,v4,13/24] bpf: Support locking bpf_spin_lock in local kptr (no matching commit)
- [bpf-next,v4,14/24] bpf: Allow locking bpf_spin_lock global variables (no matching commit)
- [bpf-next,v4,15/24] bpf: Rewrite kfunc argument handling
(no matching commit)
- [bpf-next,v4,16/24] bpf: Drop kfunc bits from btf_check_func_arg_match (no matching commit)
- [bpf-next,v4,17/24] bpf: Support constant scalar arguments for kfuncs (no matching commit)
- [bpf-next,v4,18/24] bpf: Teach verifier about non-size constant arguments (no matching commit)
- [bpf-next,v4,19/24] bpf: Introduce bpf_obj_new
(no matching commit)
- [bpf-next,v4,20/24] bpf: Introduce bpf_obj_drop
(no matching commit)
- [bpf-next,v4,21/24] bpf: Permit NULL checking pointer with non-zero fixed offset (no matching commit)
- [bpf-next,v4,22/24] bpf: Introduce single ownership BPF linked list API (no matching commit)
- [bpf-next,v4,23/24] selftests/bpf: Add __contains macro to bpf_experimental.h (no matching commit)
- [bpf-next,v4,24/24] selftests/bpf: Add BPF linked list API tests
(no matching commit)

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html