Skip to content

Allocated objects, BPF linked lists

Kumar Kartikeya Dwivedi bpf llvm 5 versions – Applied

Status from this message: This series was applied to bpf/bpf-next.git (master)

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v10 Latest24 patches 13 repliesApplied 24/24
  2. v923 patches 6 repliesSuperseded
  3. v822 patches 0 repliesSuperseded
Earlier versions · 2
VersionPostedPatchesRepliesStatus
v726 patches20 repliesSuperseded 7 of 26 applied
v626 patches2 repliesSuperseded

Changes in v10 from the cover letter

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

* Deduplicate code to find btf_record of reg (Alexei)
* Add linked_list test to DENYLIST.aarch64 (Alexei)
* Disable some linked list tests for now so that they compile with clang nightly (Alexei)

Patches in v10 All 24 applied

#Subject and filesSizeRepliesApplied
1/24bpf: Fix early return in map_check_btfkernel/bpf/syscall.c+1 -10 repliesApplied
2/24bpf: Do btf_record_free outside map_free callbackkernel/bpf/arraymap.c kernel/bpf/hashtab.c kernel/bpf/syscall.c+14 -60 repliesApplied
3/24bpf: Free inner_map_meta when btf_record_dup failskernel/bpf/map_in_map.c+3 -10 repliesApplied
4/24bpf: Populate field_offs for inner_map_metakernel/bpf/map_in_map.c+32 -120 repliesApplied
5/24bpf: Introduce allocated objects supportinclude/linux/bpf.h kernel/bpf/btf.c kernel/bpf/verifier.c+39 -20 repliesApplied
6/24bpf: Recognize lock and list fields in allocated objectsinclude/linux/bpf.h include/linux/btf.h kernel/bpf/btf.c +1 more+225 -180 repliesApplied
7/24bpf: Verify ownership relationships for user BTF typesinclude/linux/bpf.h include/linux/btf.h kernel/bpf/btf.c +1 more+77 -00 repliesApplied
8/24bpf: Allow locking bpf_spin_lock in allocated objectskernel/bpf/helpers.c kernel/bpf/verifier.c+67 -250 repliesApplied
9/24bpf: Allow locking bpf_spin_lock global variablesinclude/linux/bpf_verifier.h kernel/bpf/verifier.c+43 -140 repliesApplied
10/24bpf: Allow locking bpf_spin_lock in inner map valueskernel/bpf/map_in_map.c+0 -50 repliesApplied
11/24bpf: Rewrite kfunc argument handlinginclude/linux/bpf.h include/linux/bpf_verifier.h include/linux/btf.h +5 more+573 -4047 repliesApplied
12/24bpf: Support constant scalar arguments for kfuncsDocumentation/bpf/kfuncs.rst kernel/bpf/verifier.c+67 -140 repliesApplied
13/24bpf: Introduce bpf_obj_newinclude/linux/bpf.h include/linux/bpf_verifier.h kernel/bpf/core.c +3 more+190 -230 repliesApplied
14/24bpf: Introduce bpf_obj_dropkernel/bpf/helpers.c kernel/bpf/verifier.c tools/testing/selftests/bpf/bpf_experimental.h+79 -110 repliesApplied
15/24bpf: Permit NULL checking pointer with non-zero fixed offsetkernel/bpf/verifier.c+12 -90 repliesApplied
16/24bpf: Introduce single ownership BPF linked list APIkernel/bpf/helpers.c kernel/bpf/verifier.c tools/testing/selftests/bpf/bpf_experimental.h+349 -91 replyApplied
17/24bpf: Add 'release on unlock' logic for bpf_list_push_{front,back}include/linux/bpf_verifier.h kernel/bpf/verifier.c+62 -10 repliesApplied
18/24bpf: Add comments for map BTF matching requirement for bpf_list_headkernel/bpf/btf.c kernel/bpf/map_in_map.c kernel/bpf/syscall.c+22 -00 repliesApplied
19/24selftests/bpf: Add __contains macro to bpf_experimental.htools/testing/selftests/bpf/bpf_experimental.h+2 -00 repliesApplied
20/24selftests/bpf: Update spinlock selftesttools/testing/selftests/bpf/prog_tests/spin_lock.c tools/testing/selftests/bpf/prog_tests/spinlock.c tools/testing/selftests/bpf/progs/test_spin_lock.c+51 -470 repliesApplied
21/24selftests/bpf: Add failure test cases for spin lock pairingtools/testing/selftests/bpf/prog_tests/spin_lock.c tools/testing/selftests/bpf/progs/test_spin_lock_fail.c+292 -10 repliesApplied
22/24selftests/bpf: Add BPF linked list API teststools/testing/selftests/bpf/DENYLIST.aarch64 tools/testing/selftests/bpf/DENYLIST.s390x tools/testing/selftests/bpf/prog_tests/linked_list.c +3 more+1264 -04 repliesApplied
23/24selftests/bpf: Add BTF sanity teststools/testing/selftests/bpf/prog_tests/linked_list.c+485 -00 repliesApplied
24/24selftests/bpf: Temporarily disable linked list teststools/testing/selftests/bpf/prog_tests/linked_list.c tools/testing/selftests/bpf/progs/linked_list.c tools/testing/selftests/bpf/progs/linked_list.h +1 more+34 -161 replyApplied

Reviews trailers per patch

2 of 24 patches have a Reviewed-by or Acked-by.

PatchDave Marchevsky
1/24
2/24
3/24
4/24
5/24
6/24
7/24
8/24
9/24
10/24
11/24
12/24
13/24
14/24
15/24
16/24
17/24A-b
18/24
19/24A-b
20/24
21/24
22/24
23/24
24/24

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v10 thread

Cover letter [PATCH bpf-next v10 00/24] Allocated objects, BPF linked lists

This series introduces user defined BPF objects of a type in program BTF. 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 allocated objects, and hold such allocated objects as elements. It works as an instrusive collection, which is done to allow making allocated objects 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:
- Allocated 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 allocated objects.
- Global spin locks.
- Spin locks inside allocated objects.

Some other notable things:
- Completely static verification of locking.
- Kfunc argument handling has been completely reworked.
- Argument rewriting support for kfuncs.
- 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 BPF allocated objects. This then allows RCU protected list lookups, since spinlock protection for readers does not scale.
* Introduce bpf_refcount for local kptrs, shared ownership.
* Introduce shared ownership linked lists.
* Documentation.

Changelog:
----------
v9 -> v10
v9: https://lore.kernel.org/bpf/[email protected]

* Deduplicate code to find btf_record of reg (Alexei)
* Add linked_list test to DENYLIST.aarch64 (Alexei)
* Disable some linked list tests for now so that they compile with clang nightly (Alexei)

v8 -> v9
v8: https://lore.kernel.org/bpf/[email protected]

* Fix up commit log of patch 2, Simplify patch 3
* Explain the implicit requirement of bpf_list_head requiring map BTF to match in btf_record_equal in a separate patch.

v7 -> v8
v7: https://lore.kernel.org/bpf/[email protected]

* Fix early return in map_check_btf (Dan Carpenter)
* Fix two memory leak bugs in local storage maps, outer maps
* Address comments from Alexei and Dave
* More local kptr -> allocated object renaming
* Use krealloc with NULL instead kmalloc + krealloc
* Drop WARN_ON_ONCE for field_offs parsing
* Combine kfunc add + remove patches into one
* Drop STRONG suffix from KF_ARG_PTR_TO_KPTR
* Rename is_kfunc_arg_ret_buf_size to is_kfunc_arg_scalar_with_name
* Remove redundant check for reg->type and arg type in it
* Drop void * ret type check
* Remove code duplication in checks for NULL pointer with offset != 0
* Fix two bpf_list_node typos
* Improve log message for bpf_list_head operations
* Improve comments for active_lock struct
* Improve comments for Implementation details of process_spin_lock
* Add Dave's acks

v6 -> v7
v6: https://lore.kernel.org/bpf/[email protected]

* Fix uninitialized variable warning (Dan Carpenter, Kernel Test Robot)
* One more local_kptr renaming

v5 -> v6
v5: https://lore.kernel.org/bpf/[email protected]

* Replace (i && !off) check with next_off, include test (Andrii)
* Drop local kptrs naming (Andrii, Alexei)
* Drop reg->precise == EXACT patch (Andrii)
* Add comment about ptr member of struct active_lock (Andrii)
* Use btf__new_empty + btf__add_xxx APIs (Andrii)
* Address other misc nits from Andrii

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

* Add a lot more selftests (failure, success, runtime, BTF)
* Make sure series is bisect friendly
* Move list draining out of spin lock
* This exposed an issue where bpf_mem_free can now be called in map_free path without migrate_disable, also fixed that.
* Rename MEM_ALLOC -> MEM_RINGBUF, MEM_TYPE_LOCAL -> MEM_ALLOC (Alexei)
* Group lock identity into a struct active_lock { ptr, id } (Dave)
* Split set_release_on_unlock logic into separate patch (Alexei)

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: Fix early return in map_check_btf
bpf: Do btf_record_free outside map_free callback
bpf: Free inner_map_meta when btf_record_dup fails
bpf: Populate field_offs for inner_map_meta
bpf: Introduce allocated objects support
bpf: Recognize lock and list fields in allocated objects
bpf: Verify ownership relationships for user BTF types
bpf: Allow locking bpf_spin_lock in allocated objects
bpf: Allow locking bpf_spin_lock global variables
bpf: Allow locking bpf_spin_lock in inner map values
bpf: Rewrite kfunc argument handling
bpf: Support constant scalar arguments for kfuncs
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
bpf: Add 'release on unlock' logic for bpf_list_push_{front,back}
bpf: Add comments for map BTF matching requirement for bpf_list_head selftests/bpf: Add __contains macro to bpf_experimental.h selftests/bpf: Update spinlock selftest
selftests/bpf: Add failure test cases for spin lock pairing selftests/bpf: Add BPF linked list API tests selftests/bpf: Add BTF sanity tests
selftests/bpf: Temporarily disable linked list tests

 Documentation/bpf/kfuncs.rst                  |   24 +
 include/linux/bpf.h                           |   51 +-
 include/linux/bpf_verifier.h                  |   25 +-
 include/linux/btf.h                           |   67 +-
 kernel/bpf/arraymap.c                         |    1 -
 kernel/bpf/btf.c                              |  656 ++++-----
 kernel/bpf/core.c                             |   16 +
 kernel/bpf/hashtab.c                          |    1 -
 kernel/bpf/helpers.c                          |  115 +-
 kernel/bpf/map_in_map.c                       |   48 +-
 kernel/bpf/syscall.c                          |   42 +-
 kernel/bpf/verifier.c                         | 1220 +++++++++++++++--
 tools/testing/selftests/bpf/DENYLIST.aarch64  |    1 +
 tools/testing/selftests/bpf/DENYLIST.s390x    |    1 +
 .../testing/selftests/bpf/bpf_experimental.h  |   68 +
 .../bpf/prog_tests/kfunc_dynptr_param.c       |    2 +-
 .../selftests/bpf/prog_tests/linked_list.c    |  747 ++++++++++
 .../selftests/bpf/prog_tests/spin_lock.c      |  136 ++
 .../selftests/bpf/prog_tests/spinlock.c       |   45 -
 .../testing/selftests/bpf/progs/linked_list.c |  379 +++++
 .../testing/selftests/bpf/progs/linked_list.h |   58 +
 .../selftests/bpf/progs/linked_list_fail.c    |  581 ++++++++
 .../selftests/bpf/progs/test_spin_lock.c      |    4 +-
 .../selftests/bpf/progs/test_spin_lock_fail.c |  204 +++
 tools/testing/selftests/bpf/verifier/calls.c  |    2 +-
 .../selftests/bpf/verifier/ref_tracking.c     |    4 +-
 26 files changed, 3931 insertions(+), 567 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/prog_tests/spin_lock.c
 delete mode 100644 tools/testing/selftests/bpf/prog_tests/spinlock.c
 create mode 100644 tools/testing/selftests/bpf/progs/linked_list.c
 create mode 100644 tools/testing/selftests/bpf/progs/linked_list.h
 create mode 100644 tools/testing/selftests/bpf/progs/linked_list_fail.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_spin_lock_fail.c

base-commit: 98b2afc8a67f651ed01fc7d5a7e2528e63dd4e08

Signature · 1 line
2.38.1