Skip to content

bpf: implement bpf iterator for kernel data

Yonghong Song bpf netdev 4 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v4 Latest21 patches 20 repliesIn review
  2. v321 patches 23 repliesSuperseded
  3. v220 patches 41 repliesSuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v119 patches58 repliesSuperseded

Changes in v4 from the cover letter

- in bpf_seq_read(), if start() failed with an error, return that error to user space (Andrii)
- in bpf_seq_printf(), if reading kernel memory failed for %s and %p{i,I}{4,6}, set buffer to empty string or address 0. Documented this behavior in uapi header (Andrii)
- fix a few error handling issues for bpftool (Andrii)
- A few other minor fixes and cosmetic changes.

Patches in v4 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/21bpf: implement an interface to register bpf_iter targetsinclude/linux/bpf.h kernel/bpf/Makefile kernel/bpf/bpf_iter.c+75 -10 replies
2/21bpf: allow loading of a bpf_iter programinclude/linux/bpf.h include/uapi/linux/bpf.h kernel/bpf/bpf_iter.c +2 more+62 -05 replies
3/21bpf: support bpf tracing/iter programs for BPF_LINK_CREATEinclude/linux/bpf.h include/linux/bpf_types.h include/uapi/linux/bpf.h +3 more+80 -00 replies
4/21bpf: support bpf tracing/iter programs for BPF_LINK_UPDATEkernel/bpf/bpf_iter.c+31 -00 replies
5/21bpf: implement bpf_seq_read() for bpf iteratorkernel/bpf/bpf_iter.c+123 -02 replies
6/21bpf: create anonymous bpf iteratorinclude/linux/bpf.h include/uapi/linux/bpf.h kernel/bpf/bpf_iter.c +2 more+168 -00 replies
7/21bpf: create file bpf iteratorinclude/linux/bpf.h kernel/bpf/bpf_iter.c kernel/bpf/inode.c+22 -20 replies
8/21bpf: implement common macros/helpers for target iteratorsinclude/linux/bpf.h kernel/bpf/bpf_iter.c+91 -50 replies
9/21bpf: add bpf_map iteratorinclude/linux/bpf.h kernel/bpf/Makefile kernel/bpf/map_iter.c +1 more+118 -10 replies
10/21net: bpf: add netlink and ipv6_route bpf_iter targetsfs/proc/proc_net.c include/linux/proc_fs.h net/ipv6/ip6_fib.c +2 more+207 -40 replies
11/21bpf: add task and task/file iterator targetskernel/bpf/Makefile kernel/bpf/task_iter.c+334 -10 replies
12/21bpf: add PTR_TO_BTF_ID_OR_NULL supportinclude/linux/bpf.h kernel/bpf/btf.c kernel/bpf/verifier.c+18 -54 replies
13/21bpf: add bpf_seq_printf and bpf_seq_write helpersinclude/uapi/linux/bpf.h kernel/trace/bpf_trace.c scripts/bpf_helpers_doc.py +1 more+292 -20 replies
14/21bpf: handle spilled PTR_TO_BTF_ID properly when checking stack_boundarykernel/bpf/verifier.c+5 -00 replies
15/21bpf: support variable length array in tracing programskernel/bpf/btf.c+37 -00 replies
16/21tools/libbpf: add bpf_iter supporttools/lib/bpf/bpf.c tools/lib/bpf/bpf.h tools/lib/bpf/bpf_tracing.h +3 more+91 -04 replies
17/21tools/libpf: add offsetof/container_of macro in bpf_helpers.htools/lib/bpf/bpf_helpers.h+14 -00 replies
18/21tools/bpftool: add bpf_iter support for bptooltools/bpf/bpftool/Documentation/bpftool-iter.rst tools/bpf/bpftool/bash-completion/bpftool tools/bpf/bpftool/iter.c +3 more+188 -10 replies
19/21tools/bpf: selftests: add iterator programs for ipv6_route and netlinktools/testing/selftests/bpf/progs/bpf_iter_ipv6_route.c tools/testing/selftests/bpf/progs/bpf_iter_netlink.c+128 -00 replies
20/21tools/bpf: selftests: add iter progs for bpf_map/task/task_filetools/testing/selftests/bpf/progs/bpf_iter_bpf_map.c tools/testing/selftests/bpf/progs/bpf_iter_task.c tools/testing/selftests/bpf/progs/bpf_iter_task_file.c+79 -00 replies
21/21tools/bpf: selftests: add bpf_iter selfteststools/testing/selftests/bpf/prog_tests/bpf_iter.c tools/testing/selftests/bpf/progs/bpf_iter_test_kern1.c tools/testing/selftests/bpf/progs/bpf_iter_test_kern2.c +3 more+509 -03 replies

Reviews trailers per patch

20 of 21 patches have a Reviewed-by or Acked-by.

PatchAndrii Nakryiko
1/21A-b
2/21A-b
3/21A-b
4/21A-b
5/21A-b
6/21A-b
7/21A-b
8/21A-b
9/21A-b
10/21A-b
11/21A-b
12/21A-b
13/21A-b
14/21A-b
15/21A-b
16/21A-b
17/21A-b
18/21
19/21A-b
20/21A-b
21/21A-b

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

Read the v4 thread

Cover letter [PATCH bpf-next v4 00/21] bpf: implement bpf iterator for kernel data

Motivation:
The current way to dump kernel data structures mostly:
1. /proc system
2. various specific tools like "ss" which requires kernel support.
3. drgn
The dropback for the first two is that whenever you want to dump more, you need change the kernel. For example, Martin wants to dump socket local storage with "ss". Kernel change is needed for it to work ([1]). This is also the direct motivation for this work.

drgn ([2]) solves this proble nicely and no kernel change is not needed. But since drgn is not able to verify the validity of a particular pointer value, it might present the wrong results in rare cases.

In this patch set, we introduce bpf iterator. Initial kernel changes are still needed for interested kernel data, but a later data structure change will not require kernel changes any more. bpf program itself can adapt to new data structure changes. This will give certain flexibility with guaranteed correctness.

In this patch set, kernel seq_ops is used to facilitate iterating through kernel data, similar to current /proc and many other lossless kernel dumping facilities. In the future, different iterators can be implemented to trade off losslessness for other criteria e.g. no repeated object visits, etc.

User Interface:
1. Similar to prog/map/link, the iterator can be pinned into a path within a bpffs mount point.
2. The bpftool command can pin an iterator to a file bpftool iter pin <bpf_prog.o> <path>
3. Use cat <path> to dump the contents.
Use rm -f <path> to remove the pinned iterator.
4. The anonymous iterator can be created as well.

Please see patch #19 andd #20 for bpf programs and bpf iterator output examples.

Note that certain iterators are namespace aware. For example, task and task_file targets only iterate through current pid namespace. ipv6_route and netlink will iterate through current net namespace.

Please see individual patches for implementation details.

Performance:
The bpf iterator provides in-kernel aggregation abilities
for kernel data. This can greatly improve performance
compared to e.g., iterating all process directories under /proc.
For example, I did an experiment on my VM with an application forking different number of tasks and each forked process opening various number of files. The following is the result with the latency with unit of microseconds:

    # of forked tasks   # of open files    # of bpf_prog calls  # latency (us)
    100                 100                11503                7586
    1000                1000               1013203              709513
    10000               100                1130203              764519

The number of bpf_prog calls may be more than forked tasks multipled by open files since there are other tasks running on the system. The bpf program is a do-nothing program. One millions of bpf calls takes less than one second.

Although the initial motivation is from Martin's sk_local_storage, this patch didn't implement tcp6 sockets and sk_local_storage. The /proc/net/tcp6 involves three types of sockets, timewait, request and tcp6 sockets. Some kind of type casting or other mechanism is needed to handle all these socket types in one bpf program. This will be addressed in future work.

Currently, we do not support kernel data generated under module. This requires some BTF work.

More work for more iterators, e.g., tcp, udp, bpf_map elements, etc.

Changelog:
v3 -> v4:
- in bpf_seq_read(), if start() failed with an error, return that error to user space (Andrii)
- in bpf_seq_printf(), if reading kernel memory failed for %s and %p{i,I}{4,6}, set buffer to empty string or address 0. Documented this behavior in uapi header (Andrii)
- fix a few error handling issues for bpftool (Andrii)
- A few other minor fixes and cosmetic changes.
v2 -> v3:
- add bpf_iter_unreg_target() to unregister a target, used in the error path of the __init functions.
- handle err != 0 before handling overflow (Andrii)
- reference count "task" for task_file target (Andrii)
- remove some redundancy for bpf_map/task/task_file targets
- add bpf_iter_unreg_target() in ip6_route_cleanup()
- Handling "%%" format in bpf_seq_printf() (Andrii)
- implement auto-attach for bpf_iter in libbpf (Andrii)
- add macros offsetof and container_of in bpf_helpers.h (Andrii)
- add tests for auto-attach and program-return-1 cases
- some other minor fixes
v1 -> v2:
- removed target_feature, using callback functions instead
- checking target to ensure program specified btf_id supported (Martin)
- link_create change with new changes from Andrii
- better handling of btf_iter vs. seq_file private data (Martin, Andrii)
- implemented bpf_seq_read() (Andrii, Alexei)
- percpu buffer for bpf_seq_printf() (Andrii)
- better syntax for BPF_SEQ_PRINTF macro (Andrii)
- bpftool fixes (Quentin)
- a lot of other fixes
RFC v2 -> v1:
- rename bpfdump to bpf_iter
- use bpffs instead of a new file system
- use bpf_link to streamline and simplify iterator creation.

References:
[1]: https://lore.kernel.org/bpf/[email protected]
[2]: https://github.com/osandov/drgn

Yonghong Song (21):
bpf: implement an interface to register bpf_iter targets
bpf: allow loading of a bpf_iter program
bpf: support bpf tracing/iter programs for BPF_LINK_CREATE
bpf: support bpf tracing/iter programs for BPF_LINK_UPDATE
bpf: implement bpf_seq_read() for bpf iterator
bpf: create anonymous bpf iterator
bpf: create file bpf iterator
bpf: implement common macros/helpers for target iterators
bpf: add bpf_map iterator
net: bpf: add netlink and ipv6_route bpf_iter targets
bpf: add task and task/file iterator targets
bpf: add PTR_TO_BTF_ID_OR_NULL support
bpf: add bpf_seq_printf and bpf_seq_write helpers
bpf: handle spilled PTR_TO_BTF_ID properly when checking
stack_boundary
bpf: support variable length array in tracing programs tools/libbpf: add bpf_iter support
tools/libpf: add offsetof/container_of macro in bpf_helpers.h tools/bpftool: add bpf_iter support for bptool
tools/bpf: selftests: add iterator programs for ipv6_route and netlink tools/bpf: selftests: add iter progs for bpf_map/task/task_file tools/bpf: selftests: add bpf_iter selftests

 fs/proc/proc_net.c                            |  19 +
 include/linux/bpf.h                           |  36 ++
 include/linux/bpf_types.h                     |   1 +
 include/linux/proc_fs.h                       |   3 +
 include/uapi/linux/bpf.h                      |  47 +-
 kernel/bpf/Makefile                           |   2 +-
 kernel/bpf/bpf_iter.c                         | 530 ++++++++++++++++++
 kernel/bpf/btf.c                              |  42 +-
 kernel/bpf/inode.c                            |   5 +-
 kernel/bpf/map_iter.c                         |  97 ++++
 kernel/bpf/syscall.c                          |  59 ++
 kernel/bpf/task_iter.c                        | 333 +++++++++++
 kernel/bpf/verifier.c                         |  42 +-
 kernel/trace/bpf_trace.c                      | 214 +++++++
 net/ipv6/ip6_fib.c                            |  65 ++-
 net/ipv6/route.c                              |  37 ++
 net/netlink/af_netlink.c                      |  87 ++-
 scripts/bpf_helpers_doc.py                    |   2 +
 .../bpftool/Documentation/bpftool-iter.rst    |  83 +++
 tools/bpf/bpftool/bash-completion/bpftool     |  13 +
 tools/bpf/bpftool/iter.c                      |  88 +++
 tools/bpf/bpftool/link.c                      |   1 +
 tools/bpf/bpftool/main.c                      |   3 +-
 tools/bpf/bpftool/main.h                      |   1 +
 tools/include/uapi/linux/bpf.h                |  47 +-
 tools/lib/bpf/bpf.c                           |  10 +
 tools/lib/bpf/bpf.h                           |   2 +
 tools/lib/bpf/bpf_helpers.h                   |  14 +
 tools/lib/bpf/bpf_tracing.h                   |  16 +
 tools/lib/bpf/libbpf.c                        |  52 ++
 tools/lib/bpf/libbpf.h                        |   9 +
 tools/lib/bpf/libbpf.map                      |   2 +
 .../selftests/bpf/prog_tests/bpf_iter.c       | 409 ++++++++++++++
 .../selftests/bpf/progs/bpf_iter_bpf_map.c    |  28 +
 .../selftests/bpf/progs/bpf_iter_ipv6_route.c |  62 ++
 .../selftests/bpf/progs/bpf_iter_netlink.c    |  66 +++
 .../selftests/bpf/progs/bpf_iter_task.c       |  25 +
 .../selftests/bpf/progs/bpf_iter_task_file.c  |  26 +
 .../selftests/bpf/progs/bpf_iter_test_kern1.c |   4 +
 .../selftests/bpf/progs/bpf_iter_test_kern2.c |   4 +
 .../selftests/bpf/progs/bpf_iter_test_kern3.c |  18 +
 .../selftests/bpf/progs/bpf_iter_test_kern4.c |  52 ++
 .../bpf/progs/bpf_iter_test_kern_common.h     |  22 +
 43 files changed, 2664 insertions(+), 14 deletions(-)
 create mode 100644 kernel/bpf/bpf_iter.c
 create mode 100644 kernel/bpf/map_iter.c
 create mode 100644 kernel/bpf/task_iter.c
 create mode 100644 tools/bpf/bpftool/Documentation/bpftool-iter.rst
 create mode 100644 tools/bpf/bpftool/iter.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_iter.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_iter_bpf_map.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_iter_ipv6_route.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_iter_netlink.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_iter_task.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_iter_task_file.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_iter_test_kern1.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_iter_test_kern2.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_iter_test_kern3.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_iter_test_kern4.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_iter_test_kern_common.h
Signature · 1 line
2.24.1