Skip to content

RFC Local kptrs, BPF linked lists

Kumar Kartikeya Dwivedi bpf 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 RFC Latest32 patches 49 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/32bpf: Add copy_map_value_long to copy to remote percpu memoryinclude/linux/bpf.h+33 -190 replies
2/32bpf: Support kptrs in percpu arraymapkernel/bpf/arraymap.c kernel/bpf/syscall.c+26 -100 replies
3/32bpf: Add zero_map_value to zero map value with special fieldsinclude/linux/bpf.h+19 -00 replies
4/32bpf: Support kptrs in percpu hashmap and percpu LRU hashmapkernel/bpf/hashtab.c kernel/bpf/syscall.c+46 -260 replies
5/32bpf: Support kptrs in local storage mapsinclude/linux/bpf_local_storage.h kernel/bpf/bpf_local_storage.c kernel/bpf/syscall.c +1 more+40 -94 replies
6/32bpf: Annotate data races in bpf_local_storagekernel/bpf/bpf_local_storage.c+13 -30 replies
7/32bpf: Allow specifying volatile type modifier for kptrsinclude/linux/btf.h kernel/bpf/btf.c+8 -00 replies
8/32bpf: Add comment about kptr's PTR_TO_MAP_VALUE handlingkernel/bpf/verifier.c+5 -00 replies
9/32bpf: Rewrite kfunc argument handlinginclude/linux/btf.h kernel/bpf/btf.c kernel/bpf/verifier.c +1 more+438 -240 replies
10/32bpf: Drop kfunc support from btf_check_func_arg_matchinclude/linux/bpf.h include/linux/bpf_verifier.h kernel/bpf/btf.c +1 more+10 -2620 replies
11/32bpf: Support constant scalar arguments for kfuncsDocumentation/bpf/kfuncs.rst kernel/bpf/verifier.c+80 -170 replies
12/32bpf: Teach verifier about non-size constant argumentsinclude/linux/bpf_verifier.h kernel/bpf/verifier.c+76 -252 replies
13/32bpf: Introduce bpf_list_head support for BPF mapsinclude/linux/bpf.h include/linux/btf.h kernel/bpf/arraymap.c +7 more+378 -432 replies
14/32bpf: Introduce bpf_kptr_alloc helperinclude/linux/bpf.h include/linux/bpf_verifier.h include/linux/btf.h +6 more+191 -302 replies
15/32bpf: Add helper macro bpf_expr_for_each_reg_in_vstateinclude/linux/bpf_verifier.h kernel/bpf/verifier.c+49 -1071 reply
16/32bpf: Introduce BPF memory object modelinclude/linux/bpf.h include/linux/bpf_verifier.h kernel/bpf/verifier.c+336 -29 replies
17/32bpf: Support bpf_list_node in local kptrsinclude/linux/btf.h kernel/bpf/btf.c kernel/bpf/helpers.c +2 more+146 -180 replies
18/32bpf: Support bpf_spin_lock in local kptrsinclude/linux/btf.h include/linux/poison.h kernel/bpf/btf.c +3 more+121 -274 replies
19/32bpf: Support bpf_list_head in local kptrsinclude/linux/btf.h kernel/bpf/btf.c kernel/bpf/helpers.c +2 more+106 -120 replies
20/32bpf: Introduce bpf_kptr_free helperkernel/bpf/helpers.c kernel/bpf/verifier.c tools/testing/selftests/bpf/bpf_experimental.h+43 -00 replies
21/32bpf: Allow locking bpf_spin_lock global variablesinclude/linux/bpf_verifier.h kernel/bpf/verifier.c+29 -1325 replies
22/32bpf: Bump BTF_KFUNC_SET_MAX_CNTkernel/bpf/btf.c+1 -10 replies
23/32bpf: Add single ownership BPF linked list APIinclude/linux/bpf_verifier.h include/linux/btf.h kernel/bpf/btf.c +3 more+599 -430 replies
24/32bpf: Permit NULL checking pointer with non-zero fixed offsetkernel/bpf/verifier.c+9 -40 replies
25/32bpf: Allow storing local kptrs in BPF mapsinclude/linux/bpf.h include/linux/btf.h kernel/bpf/btf.c +3 more+142 -490 replies
26/32bpf: Wire up freeing of bpf_list_heads in mapsinclude/linux/bpf.h kernel/bpf/arraymap.c kernel/bpf/bpf_local_storage.c +3 more+93 -40 replies
27/32bpf: Add destructor for bpf_list_head in local kptrinclude/linux/bpf.h kernel/bpf/helpers.c kernel/bpf/syscall.c +2 more+69 -140 replies
28/32bpf: Remove duplicate PTR_TO_BTF_ID RO checkkernel/bpf/verifier.c+0 -30 replies
29/32libbpf: Add support for private BSS map sectiontools/lib/bpf/libbpf.c+44 -210 replies
30/32selftests/bpf: Add BTF tag macros for local kptrs, BPF linked liststools/testing/selftests/bpf/bpf_experimental.h+4 -00 replies
31/32selftests/bpf: Add BPF linked list API testskernel/bpf/helpers.c tools/testing/selftests/bpf/prog_tests/linked_list.c tools/testing/selftests/bpf/progs/linked_list.c+439 -10 replies
32/32selftests/bpf: Add referenced local kptr teststools/testing/selftests/bpf/prog_tests/map_kptr.c tools/testing/selftests/bpf/progs/map_kptr.c+39 -10 replies

Reviews trailers per patch

1 of 32 patches has a Reviewed-by or Acked-by.

PatchKumar Kartikeya Dwivedi
1/32
2/32
3/32
4/32
5/32
6/32
7/32
8/32
9/32
10/32
11/32
12/32
13/32
14/32
15/32
16/32
17/32
18/32
19/32
20/32
21/32
22/32
23/32
24/32
25/32
26/32
27/32
28/32A-b
29/32
30/32
31/32
32/32

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

Read the v1 thread

Cover letter [PATCH RFC bpf-next v1 00/32] Local kptrs, BPF linked lists

WARNING: This is an RFC. WARN_ON_ONCE is sprinkled around the code liberally (useful while working on this stuff). I'll be doing a thorough pass and clean all that up before sending out non-RFC v1.
TODO before non-RFC v1.
- A lot more corner case tests, failure tests, more tests for the new local kptr support. I did test the basic stuff (which the verifier complained about when writing linked_list.c).
- More tests for kptr support in new map types.
- More self review.

--

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.

Eventually, with some more support in future patches, users will be able to write fully concurrent RCU protected hash table using BPF_MAP_TYPE_ARRAY for buckets and embed BPF linked lists in these buckets. All of this will be possible in safe BPF C, which will be proven for runtime safety by the BPF verifier.

The features, core infrastructure, and other improvements in this set are:
- Allow storing kptrs in local storage and percpu maps.
- Local kptrs - User defined kernel objects.
- bpf_kptr_alloc, bpf_kptr_free to allocate and free them.
- BPF memory object model, similar to what C and C++ abstract machines have, now verifier reasons about an object's lifetime, i.e. the concept of object lifetime, visibility, construction, destruction is reified.
The separation of storage and object lifetime is understood by the verifier.
- 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.
- Allow storing local kptrs in all BPF maps with support for kernel kptrs.

Some other notable things:
- Completely static verification of locking.
- Kfunc argument handling has been completely reworked.
- Argument rewriting support for kfuncs.
Now we can also support inlining block of BPF insns for certain kfuncs.
- Iteration over all registers in verifier state has a new lambda based iterator (and can be nifty or crazy - depending on your love for GNU C).
- 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**.

Next steps:
-----------
* NMI safe percpu single ownership linked lists (using local_t protection).
- This enables open coded freelist use case
* 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.

Notes:
------
* Delyan's work to expose Alexei's BPF memory allocator as global allocator is still needed before this can be merged. For now, direct kmalloc and kfree is used.

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]

Daniel Xu (1):
bpf: Remove duplicate PTR_TO_BTF_ID RO check

Dave Marchevsky (1):
libbpf: Add support for private BSS map section

Kumar Kartikeya Dwivedi (30):
bpf: Add copy_map_value_long to copy to remote percpu memory
bpf: Support kptrs in percpu arraymap
bpf: Add zero_map_value to zero map value with special fields
bpf: Support kptrs in percpu hashmap and percpu LRU hashmap
bpf: Support kptrs in local storage maps
bpf: Annotate data races in bpf_local_storage
bpf: Allow specifying volatile type modifier for kptrs
bpf: Add comment about kptr's PTR_TO_MAP_VALUE handling
bpf: Rewrite kfunc argument handling
bpf: Drop kfunc support from btf_check_func_arg_match
bpf: Support constant scalar arguments for kfuncs
bpf: Teach verifier about non-size constant arguments
bpf: Introduce bpf_list_head support for BPF maps
bpf: Introduce bpf_kptr_alloc helper
bpf: Add helper macro bpf_expr_for_each_reg_in_vstate
bpf: Introduce BPF memory object model
bpf: Support bpf_list_node in local kptrs
bpf: Support bpf_spin_lock in local kptrs
bpf: Support bpf_list_head in local kptrs
bpf: Introduce bpf_kptr_free helper
bpf: Allow locking bpf_spin_lock global variables
bpf: Bump BTF_KFUNC_SET_MAX_CNT
bpf: Add single ownership BPF linked list API
bpf: Permit NULL checking pointer with non-zero fixed offset
bpf: Allow storing local kptrs in BPF maps
bpf: Wire up freeing of bpf_list_heads in maps
bpf: Add destructor for bpf_list_head in local kptr selftests/bpf: Add BTF tag macros for local kptrs, BPF linked lists selftests/bpf: Add BPF linked list API tests selftests/bpf: Add referenced local kptr tests

 Documentation/bpf/kfuncs.rst                  |   30 +
 include/linux/bpf.h                           |  177 +-
 include/linux/bpf_local_storage.h             |    2 +-
 include/linux/bpf_verifier.h                  |   77 +-
 include/linux/btf.h                           |   76 +-
 include/linux/poison.h                        |    3 +
 kernel/bpf/arraymap.c                         |   43 +-
 kernel/bpf/bpf_local_storage.c                |   53 +-
 kernel/bpf/btf.c                              |  727 +++---
 kernel/bpf/hashtab.c                          |   91 +-
 kernel/bpf/helpers.c                          |  137 +-
 kernel/bpf/map_in_map.c                       |    5 +-
 kernel/bpf/syscall.c                          |  231 +-
 kernel/bpf/verifier.c                         | 2084 ++++++++++++++---
 net/bpf/bpf_dummy_struct_ops.c                |    5 +-
 net/ipv4/bpf_tcp_ca.c                         |    5 +-
 tools/lib/bpf/libbpf.c                        |   65 +-
 .../testing/selftests/bpf/bpf_experimental.h  |  120 +
 .../selftests/bpf/prog_tests/linked_list.c    |   88 +
 .../selftests/bpf/prog_tests/map_kptr.c       |    2 +-
 .../testing/selftests/bpf/progs/linked_list.c |  347 +++
 tools/testing/selftests/bpf/progs/map_kptr.c  |   38 +
 tools/testing/selftests/bpf/verifier/calls.c  |    2 +-
 23 files changed, 3626 insertions(+), 782 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
Signature · 1 line
2.34.1