diff options
Diffstat (limited to 'Documentation/bpf/bpf_iterators.rst')
| -rw-r--r-- | Documentation/bpf/bpf_iterators.rst | 589 |
1 files changed, 589 insertions, 0 deletions
diff --git a/Documentation/bpf/bpf_iterators.rst b/Documentation/bpf/bpf_iterators.rst new file mode 100644 index 000000000000..189e3ec1c6c8 --- /dev/null +++ b/Documentation/bpf/bpf_iterators.rst @@ -0,0 +1,589 @@ +============= +BPF Iterators +============= + +-------- +Overview +-------- + +BPF supports two separate entities collectively known as "BPF iterators": BPF +iterator *program type* and *open-coded* BPF iterators. The former is +a stand-alone BPF program type which, when attached and activated by user, +will be called once for each entity (task_struct, cgroup, etc) that is being +iterated. The latter is a set of BPF-side APIs implementing iterator +functionality and available across multiple BPF program types. Open-coded +iterators provide similar functionality to BPF iterator programs, but gives +more flexibility and control to all other BPF program types. BPF iterator +programs, on the other hand, can be used to implement anonymous or BPF +FS-mounted special files, whose contents are generated by attached BPF iterator +program, backed by seq_file functionality. Both are useful depending on +specific needs. + +When adding a new BPF iterator program, it is expected that similar +functionality will be added as open-coded iterator for maximum flexibility. +It's also expected that iteration logic and code will be maximally shared and +reused between two iterator API surfaces. + +------------------------ +Open-coded BPF Iterators +------------------------ + +Open-coded BPF iterators are implemented as tightly-coupled trios of kfuncs +(constructor, next element fetch, destructor) and iterator-specific type +describing on-the-stack iterator state, which is guaranteed by the BPF +verifier to not be tampered with outside of the corresponding +constructor/destructor/next APIs. + +Each kind of open-coded BPF iterator has its own associated +struct bpf_iter_<type>, where <type> denotes a specific type of iterator. +bpf_iter_<type> state needs to live on BPF program stack, so make sure it's +small enough to fit on BPF stack. For performance reasons its best to avoid +dynamic memory allocation for iterator state and size the state struct big +enough to fit everything necessary. But if necessary, dynamic memory +allocation is a way to bypass BPF stack limitations. Note, state struct size +is part of iterator's user-visible API, so changing it will break backwards +compatibility, so be deliberate about designing it. + +All kfuncs (constructor, next, destructor) have to be named consistently as +bpf_iter_<type>_{new,next,destroy}(), respectively. <type> represents iterator +type, and iterator state should be represented as a matching +`struct bpf_iter_<type>` state type. Also, all iter kfuncs should have +a pointer to this `struct bpf_iter_<type>` as the very first argument. + +Additionally: + - Constructor, i.e., `bpf_iter_<type>_new()`, can have arbitrary extra + number of arguments. Return type is not enforced either. + - Next method, i.e., `bpf_iter_<type>_next()`, has to return a pointer + type and should have exactly one argument: `struct bpf_iter_<type> *` + (const/volatile/restrict and typedefs are ignored). + - Destructor, i.e., `bpf_iter_<type>_destroy()`, should return void and + should have exactly one argument, similar to the next method. + - `struct bpf_iter_<type>` size is enforced to be positive and + a multiple of 8 bytes (to fit stack slots correctly). + +Such strictness and consistency allows to build generic helpers abstracting +important, but boilerplate, details to be able to use open-coded iterators +effectively and ergonomically (see libbpf's bpf_for_each() macro). This is +enforced at kfunc registration point by the kernel. + +Constructor/next/destructor implementation contract is as follows: + - constructor, `bpf_iter_<type>_new()`, always initializes iterator state on + the stack. If any of the input arguments are invalid, constructor should + make sure to still initialize it such that subsequent next() calls will + return NULL. I.e., on error, *return error and construct empty iterator*. + Constructor kfunc is marked with KF_ITER_NEW flag. + + - next method, `bpf_iter_<type>_next()`, accepts pointer to iterator state + and produces an element. Next method should always return a pointer. The + contract between BPF verifier is that next method *guarantees* that it + will eventually return NULL when elements are exhausted. Once NULL is + returned, subsequent next calls *should keep returning NULL*. Next method + is marked with KF_ITER_NEXT (and should also have KF_RET_NULL as + NULL-returning kfunc, of course). + + - destructor, `bpf_iter_<type>_destroy()`, is always called once. Even if + constructor failed or next returned nothing. Destructor frees up any + resources and marks stack space used by `struct bpf_iter_<type>` as usable + for something else. Destructor is marked with KF_ITER_DESTROY flag. + +Any open-coded BPF iterator implementation has to implement at least these +three methods. It is enforced that for any given type of iterator only +applicable constructor/destructor/next are callable. I.e., verifier ensures +you can't pass number iterator state into, say, cgroup iterator's next method. + +From a 10,000-feet BPF verification point of view, next methods are the points +of forking a verification state, which are conceptually similar to what +verifier is doing when validating conditional jumps. Verifier is branching out +`call bpf_iter_<type>_next` instruction and simulates two outcomes: NULL +(iteration is done) and non-NULL (new element is returned). NULL is simulated +first and is supposed to reach exit without looping. After that non-NULL case +is validated and it either reaches exit (for trivial examples with no real +loop), or reaches another `call bpf_iter_<type>_next` instruction with the +state equivalent to already (partially) validated one. State equivalency at +that point means we technically are going to be looping forever without +"breaking out" out of established "state envelope" (i.e., subsequent +iterations don't add any new knowledge or constraints to the verifier state, +so running 1, 2, 10, or a million of them doesn't matter). But taking into +account the contract stating that iterator next method *has to* return NULL +eventually, we can conclude that loop body is safe and will eventually +terminate. Given we validated logic outside of the loop (NULL case), and +concluded that loop body is safe (though potentially looping many times), +verifier can claim safety of the overall program logic. + +------------------------ +BPF Iterators Motivation +------------------------ + +There are a few existing ways to dump kernel data into user space. The most +popular one is the ``/proc`` system. For example, ``cat /proc/net/tcp6`` dumps +all tcp6 sockets in the system, and ``cat /proc/net/netlink`` dumps all netlink +sockets in the system. However, their output format tends to be fixed, and if +users want more information about these sockets, they have to patch the kernel, +which often takes time to publish upstream and release. The same is true for popular +tools like `ss <https://man7.org/linux/man-pages/man8/ss.8.html>`_ where any +additional information needs a kernel patch. + +To solve this problem, the `drgn +<https://www.kernel.org/doc/html/latest/bpf/drgn.html>`_ tool is often used to +dig out the kernel data with no kernel change. However, the main drawback for +drgn is performance, as it cannot do pointer tracing inside the kernel. In +addition, drgn cannot validate a pointer value and may read invalid data if the +pointer becomes invalid inside the kernel. + +The BPF iterator solves the above problem by providing flexibility on what data +(e.g., tasks, bpf_maps, etc.) to collect by calling BPF programs for each kernel +data object. + +---------------------- +How BPF Iterators Work +---------------------- + +A BPF iterator is a type of BPF program that allows users to iterate over +specific types of kernel objects. Unlike traditional BPF tracing programs that +allow users to define callbacks that are invoked at particular points of +execution in the kernel, BPF iterators allow users to define callbacks that +should be executed for every entry in a variety of kernel data structures. + +For example, users can define a BPF iterator that iterates over every task on +the system and dumps the total amount of CPU runtime currently used by each of +them. Another BPF task iterator may instead dump the cgroup information for each +task. Such flexibility is the core value of BPF iterators. + +A BPF program is always loaded into the kernel at the behest of a user space +process. A user space process loads a BPF program by opening and initializing +the program skeleton as required and then invoking a syscall to have the BPF +program verified and loaded by the kernel. + +In traditional tracing programs, a program is activated by having user space +obtain a ``bpf_link`` to the program with ``bpf_program__attach()``. Once +activated, the program callback will be invoked whenever the tracepoint is +triggered in the main kernel. For BPF iterator programs, a ``bpf_link`` to the +program is obtained using ``bpf_link_create()``, and the program callback is +invoked by issuing system calls from user space. + +Next, let us see how you can use the iterators to iterate on kernel objects and +read data. + +------------------------ +How to Use BPF iterators +------------------------ + +BPF selftests are a great resource to illustrate how to use the iterators. In +this section, we’ll walk through a BPF selftest which shows how to load and use +a BPF iterator program. To begin, we’ll look at `bpf_iter.c +<https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/testing/selftests/bpf/prog_tests/bpf_iter.c>`_, +which illustrates how to load and trigger BPF iterators on the user space side. +Later, we’ll look at a BPF program that runs in kernel space. + +Loading a BPF iterator in the kernel from user space typically involves the +following steps: + +* The BPF program is loaded into the kernel through ``libbpf``. Once the kernel + has verified and loaded the program, it returns a file descriptor (fd) to user + space. +* Obtain a ``link_fd`` to the BPF program by calling the ``bpf_link_create()`` + specified with the BPF program file descriptor received from the kernel. +* Next, obtain a BPF iterator file descriptor (``bpf_iter_fd``) by calling the + ``bpf_iter_create()`` specified with the ``bpf_link`` received from Step 2. +* Trigger the iteration by calling ``read(bpf_iter_fd)`` until no data is + available. +* Close the iterator fd using ``close(bpf_iter_fd)``. +* If needed to reread the data, get a new ``bpf_iter_fd`` and do the read again. + +The following are a few examples of selftest BPF iterator programs: + +* `bpf_iter_tcp4.c <https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/testing/selftests/bpf/progs/bpf_iter_tcp4.c>`_ +* `bpf_iter_task_vmas.c <https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/testing/selftests/bpf/progs/bpf_iter_task_vmas.c>`_ +* `bpf_iter_task_file.c <https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/testing/selftests/bpf/progs/bpf_iter_task_file.c>`_ + +Let us look at ``bpf_iter_task_file.c``, which runs in kernel space: + +Here is the definition of ``bpf_iter__task_file`` in `vmlinux.h +<https://facebookmicrosites.github.io/bpf/blog/2020/02/19/bpf-portability-and-co-re.html#btf>`_. +Any struct name in ``vmlinux.h`` in the format ``bpf_iter__<iter_name>`` +represents a BPF iterator. The suffix ``<iter_name>`` represents the type of +iterator. + +:: + + struct bpf_iter__task_file { + union { + struct bpf_iter_meta *meta; + }; + union { + struct task_struct *task; + }; + u32 fd; + union { + struct file *file; + }; + }; + +In the above code, the field 'meta' contains the metadata, which is the same for +all BPF iterator programs. The rest of the fields are specific to different +iterators. For example, for task_file iterators, the kernel layer provides the +'task', 'fd' and 'file' field values. The 'task' and 'file' are `reference +counted +<https://facebookmicrosites.github.io/bpf/blog/2018/08/31/object-lifetime.html#file-descriptors-and-reference-counters>`_, +so they won't go away when the BPF program runs. + +Here is a snippet from the ``bpf_iter_task_file.c`` file: + +:: + + SEC("iter/task_file") + int dump_task_file(struct bpf_iter__task_file *ctx) + { + struct seq_file *seq = ctx->meta->seq; + struct task_struct *task = ctx->task; + struct file *file = ctx->file; + __u32 fd = ctx->fd; + + if (task == NULL || file == NULL) + return 0; + + if (ctx->meta->seq_num == 0) { + count = 0; + BPF_SEQ_PRINTF(seq, " tgid gid fd file\n"); + } + + if (tgid == task->tgid && task->tgid != task->pid) + count++; + + if (last_tgid != task->tgid) { + last_tgid = task->tgid; + unique_tgid_count++; + } + + BPF_SEQ_PRINTF(seq, "%8d %8d %8d %lx\n", task->tgid, task->pid, fd, + (long)file->f_op); + return 0; + } + +In the above example, the section name ``SEC(iter/task_file)``, indicates that +the program is a BPF iterator program to iterate all files from all tasks. The +context of the program is ``bpf_iter__task_file`` struct. + +The user space program invokes the BPF iterator program running in the kernel +by issuing a ``read()`` syscall. Once invoked, the BPF +program can export data to user space using a variety of BPF helper functions. +You can use either ``bpf_seq_printf()`` (and BPF_SEQ_PRINTF helper macro) or +``bpf_seq_write()`` function based on whether you need formatted output or just +binary data, respectively. For binary-encoded data, the user space applications +can process the data from ``bpf_seq_write()`` as needed. For the formatted data, +you can use ``cat <path>`` to print the results similar to ``cat +/proc/net/netlink`` after pinning the BPF iterator to the bpffs mount. Later, +use ``rm -f <path>`` to remove the pinned iterator. + +For example, you can use the following command to create a BPF iterator from the +``bpf_iter_ipv6_route.o`` object file and pin it to the ``/sys/fs/bpf/my_route`` +path: + +:: + + $ bpftool iter pin ./bpf_iter_ipv6_route.o /sys/fs/bpf/my_route + +And then print out the results using the following command: + +:: + + $ cat /sys/fs/bpf/my_route + + +------------------------------------------------------- +Implement Kernel Support for BPF Iterator Program Types +------------------------------------------------------- + +To implement a BPF iterator in the kernel, the developer must make a one-time +change to the following key data structure defined in the `bpf.h +<https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/include/linux/bpf.h>`_ +file. + +:: + + struct bpf_iter_reg { + const char *target; + bpf_iter_attach_target_t attach_target; + bpf_iter_detach_target_t detach_target; + bpf_iter_show_fdinfo_t show_fdinfo; + bpf_iter_fill_link_info_t fill_link_info; + bpf_iter_get_func_proto_t get_func_proto; + u32 ctx_arg_info_size; + u32 feature; + struct bpf_ctx_arg_aux ctx_arg_info[BPF_ITER_CTX_ARG_MAX]; + const struct bpf_iter_seq_info *seq_info; + }; + +After filling the data structure fields, call ``bpf_iter_reg_target()`` to +register the iterator to the main BPF iterator subsystem. + +The following is the breakdown for each field in struct ``bpf_iter_reg``. + +.. list-table:: + :widths: 25 50 + :header-rows: 1 + + * - Fields + - Description + * - target + - Specifies the name of the BPF iterator. For example: ``bpf_map``, + ``bpf_map_elem``. The name should be different from other ``bpf_iter`` target names in the kernel. + * - attach_target and detach_target + - Allows for target specific ``link_create`` action since some targets + may need special processing. Called during the user space link_create stage. + * - show_fdinfo and fill_link_info + - Called to fill target specific information when user tries to get link + info associated with the iterator. + * - get_func_proto + - Permits a BPF iterator to access BPF helpers specific to the iterator. + * - ctx_arg_info_size and ctx_arg_info + - Specifies the verifier states for BPF program arguments associated with + the bpf iterator. + * - feature + - Specifies certain action requests in the kernel BPF iterator + infrastructure. Currently, only BPF_ITER_RESCHED is supported. This means + that the kernel function cond_resched() is called to avoid other kernel + subsystem (e.g., rcu) misbehaving. + * - seq_info + - Specifies the set of seq operations for the BPF iterator and helpers to + initialize/free the private data for the corresponding ``seq_file``. + +`Click here +<https://lore.kernel.org/bpf/20210212183107.50963-2-songliubraving@fb.com/>`_ +to see an implementation of the ``task_vma`` BPF iterator in the kernel. + +--------------------------------- +Parameterizing BPF Task Iterators +--------------------------------- + +By default, BPF iterators walk through all the objects of the specified types +(processes, cgroups, maps, etc.) across the entire system to read relevant +kernel data. But often, there are cases where we only care about a much smaller +subset of iterable kernel objects, such as only iterating tasks within a +specific process. Therefore, BPF iterator programs support filtering out objects +from iteration by allowing user space to configure the iterator program when it +is attached. + +-------------------------- +BPF Task Iterator Program +-------------------------- + +The following code is a BPF iterator program to print files and task information +through the ``seq_file`` of the iterator. It is a standard BPF iterator program +that visits every file of an iterator. We will use this BPF program in our +example later. + +:: + + #include <vmlinux.h> + #include <bpf/bpf_helpers.h> + + char _license[] SEC("license") = "GPL"; + + SEC("iter/task_file") + int dump_task_file(struct bpf_iter__task_file *ctx) + { + struct seq_file *seq = ctx->meta->seq; + struct task_struct *task = ctx->task; + struct file *file = ctx->file; + __u32 fd = ctx->fd; + if (task == NULL || file == NULL) + return 0; + if (ctx->meta->seq_num == 0) { + BPF_SEQ_PRINTF(seq, " tgid pid fd file\n"); + } + BPF_SEQ_PRINTF(seq, "%8d %8d %8d %lx\n", task->tgid, task->pid, fd, + (long)file->f_op); + return 0; + } + +---------------------------------------- +Creating a File Iterator with Parameters +---------------------------------------- + +Now, let us look at how to create an iterator that includes only files of a +process. + +First, fill the ``bpf_iter_attach_opts`` struct as shown below: + +:: + + LIBBPF_OPTS(bpf_iter_attach_opts, opts); + union bpf_iter_link_info linfo; + memset(&linfo, 0, sizeof(linfo)); + linfo.task.pid = getpid(); + opts.link_info = &linfo; + opts.link_info_len = sizeof(linfo); + +``linfo.task.pid``, if it is non-zero, directs the kernel to create an iterator +that only includes opened files for the process with the specified ``pid``. In +this example, we will only be iterating files for our process. If +``linfo.task.pid`` is zero, the iterator will visit every opened file of every +process. Similarly, ``linfo.task.tid`` directs the kernel to create an iterator +that visits opened files of a specific thread, not a process. In this example, +``linfo.task.tid`` is different from ``linfo.task.pid`` only if the thread has a +separate file descriptor table. In most circumstances, all process threads share +a single file descriptor table. + +Now, in the userspace program, pass the pointer of struct to the +``bpf_program__attach_iter()``. + +:: + + link = bpf_program__attach_iter(prog, &opts); + iter_fd = bpf_iter_create(bpf_link__fd(link)); + +If both *tid* and *pid* are zero, an iterator created from this struct +``bpf_iter_attach_opts`` will include every opened file of every task in the +system (in the namespace, actually.) It is the same as passing a NULL as the +second argument to ``bpf_program__attach_iter()``. + +The whole program looks like the following code: + +:: + + #include <stdio.h> + #include <unistd.h> + #include <bpf/bpf.h> + #include <bpf/libbpf.h> + #include "bpf_iter_task_ex.skel.h" + + static int do_read_opts(struct bpf_program *prog, struct bpf_iter_attach_opts *opts) + { + struct bpf_link *link; + char buf[16] = {}; + int iter_fd = -1, len; + int ret = 0; + + link = bpf_program__attach_iter(prog, opts); + if (!link) { + fprintf(stderr, "bpf_program__attach_iter() fails\n"); + return -1; + } + iter_fd = bpf_iter_create(bpf_link__fd(link)); + if (iter_fd < 0) { + fprintf(stderr, "bpf_iter_create() fails\n"); + ret = -1; + goto free_link; + } + /* not check contents, but ensure read() ends without error */ + while ((len = read(iter_fd, buf, sizeof(buf) - 1)) > 0) { + buf[len] = 0; + printf("%s", buf); + } + printf("\n"); + free_link: + if (iter_fd >= 0) + close(iter_fd); + bpf_link__destroy(link); + return 0; + } + + static void test_task_file(void) + { + LIBBPF_OPTS(bpf_iter_attach_opts, opts); + struct bpf_iter_task_ex *skel; + union bpf_iter_link_info linfo; + skel = bpf_iter_task_ex__open_and_load(); + if (skel == NULL) + return; + memset(&linfo, 0, sizeof(linfo)); + linfo.task.pid = getpid(); + opts.link_info = &linfo; + opts.link_info_len = sizeof(linfo); + printf("PID %d\n", getpid()); + do_read_opts(skel->progs.dump_task_file, &opts); + bpf_iter_task_ex__destroy(skel); + } + + int main(int argc, const char * const * argv) + { + test_task_file(); + return 0; + } + +The following lines are the output of the program. +:: + + PID 1859 + + tgid pid fd file + 1859 1859 0 ffffffff82270aa0 + 1859 1859 1 ffffffff82270aa0 + 1859 1859 2 ffffffff82270aa0 + 1859 1859 3 ffffffff82272980 + 1859 1859 4 ffffffff8225e120 + 1859 1859 5 ffffffff82255120 + 1859 1859 6 ffffffff82254f00 + 1859 1859 7 ffffffff82254d80 + 1859 1859 8 ffffffff8225abe0 + +------------------ +Without Parameters +------------------ + +Let us look at how a BPF iterator without parameters skips files of other +processes in the system. In this case, the BPF program has to check the pid or +the tid of tasks, or it will receive every opened file in the system (in the +current *pid* namespace, actually). So, we usually add a global variable in the +BPF program to pass a *pid* to the BPF program. + +The BPF program would look like the following block. + + :: + + ...... + int target_pid = 0; + + SEC("iter/task_file") + int dump_task_file(struct bpf_iter__task_file *ctx) + { + ...... + if (task->tgid != target_pid) /* Check task->pid instead to check thread IDs */ + return 0; + BPF_SEQ_PRINTF(seq, "%8d %8d %8d %lx\n", task->tgid, task->pid, fd, + (long)file->f_op); + return 0; + } + +The user space program would look like the following block: + + :: + + ...... + static void test_task_file(void) + { + ...... + skel = bpf_iter_task_ex__open_and_load(); + if (skel == NULL) + return; + skel->bss->target_pid = getpid(); /* process ID. For thread id, use gettid() */ + memset(&linfo, 0, sizeof(linfo)); + linfo.task.pid = getpid(); + opts.link_info = &linfo; + opts.link_info_len = sizeof(linfo); + ...... + } + +``target_pid`` is a global variable in the BPF program. The user space program +should initialize the variable with a process ID to skip opened files of other +processes in the BPF program. When you parametrize a BPF iterator, the iterator +calls the BPF program fewer times which can save significant resources. + +--------------------------- +Parametrizing VMA Iterators +--------------------------- + +By default, a BPF VMA iterator includes every VMA in every process. However, +you can still specify a process or a thread to include only its VMAs. Unlike +files, a thread can not have a separate address space (since Linux 2.6.0-test6). +Here, using *tid* makes no difference from using *pid*. + +---------------------------- +Parametrizing Task Iterators +---------------------------- + +A BPF task iterator with *pid* includes all tasks (threads) of a process. The +BPF program receives these tasks one after another. You can specify a BPF task +iterator with *tid* parameter to include only the tasks that match the given +*tid*. |