bpf, docs: document open-coded BPF iterators
Subsystems (2)
Andrii Nakryiko
maintainerPATCH 1/1 bpf, docs: document open-coded BPF iterators
Extract BPF open-coded iterators documentation spread out across a few original commit messages ([0], [1]) into a dedicated doc section under Documentation/bpf/bpf_iterators.rst. Also make explicit expectation that BPF iterator program type should be accompanied by a corresponding open-coded BPF iterator implementation, going forward.
[0] https://lore.kernel.org/all/[email protected]/
[1] https://lore.kernel.org/all/[email protected]/
--- Documentation/bpf/bpf_iterators.rst | 115 +++++++++++++++++++++++++++- 1 file changed, 112 insertions(+), 3 deletions(-)
Documentation/bpf/bpf_iterators.rst +112 -3
@@ -2,10 +2,119 @@ 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 +functionalirt and available across multiple BPF program types. Open-coded +iterators provide similar functionality to BPF iterator programs, but gives +more flexiblity 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 is 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. ----------- -Motivation ----------- +------------------------ +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. struct +bpf_iter_<type> state is supposed to live on BPF program stack, so there will +be no way to change its size later on without breaking backwards +compatibility, so choose wisely! But given this struct is specific to a given +<type> of iterator, this allows a lot of flexibility: simple iterators could +be fine with just one stack slot (8 bytes), like numbers iterator is, while +some other more complicated iterators might need way more to keep their +iterator state. Either way, such design allows to avoid runtime memory +allocations, which otherwise would be necessary if we fixed on-the-stack size +and it turned out to be too small for a given iterator implementation. + +All kfuncs (constructor, next, destructor) have to be named consistenly 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
Signature · 1 line
2.47.1
Quoted 7 lines · Andrii Nakryiko
Extract BPF open-coded iterators documentation spread out across a few original commit messages ([0], [1]) into a dedicated doc section under
Documentation/bpf/bpf_iterators.rst. Also make explicit expectation that BPF iterator program type should be accompanied by a corresponding open-coded BPF iterator implementation, going forward.
Quoted 5 lines
[0] https://lore.kernel.org/all/[email protected]/
[1] https://lore.kernel.org/all/[email protected]/Signed-off-by Andrii Nakryiko <[email protected]>---
Some typos below, but:
Quoted 11 lines
Documentation/bpf/bpf_iterators.rst | 115 +++++++++++++++++++++++++++- 1 file changed, 112 insertions(+), 3 deletions(-)Documentation/bpf/bpf_iterators.rst +0
-0@@ -2,10 +2,119 @@ BPF Iterators =============
Documentation/bpf/bpf_iterators.rst line 14
Quoted 10 lines
Documentation/bpf/bpf_iterators.rst +10
-0+-------- +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 +functionalirt and available across multiple BPF program types. Open-coded
typo: functionality
Documentation/bpf/bpf_iterators.rst line 16
Quoted 2 lines
Documentation/bpf/bpf_iterators.rst +2
-0+iterators provide similar functionality to BPF iterator programs, but gives +more flexiblity and control to all other BPF program types. BPF iterator
typo: flexibility
Documentation/bpf/bpf_iterators.rst line 18
Quoted 2 lines
Documentation/bpf/bpf_iterators.rst +2
-0+programs, on the other hand, can be used to implement anonymous or BPF +FS-mounted special files, whose contents is generated by attached BPF iterator
typo: contents are generated?
Quoted 24 lines
Documentation/bpf/bpf_iterators.rst +20
-3+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. ----------- -Motivation ----------- +------------------------ +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. struct +bpf_iter_<type> state is supposed to live on BPF program stack, so there will
Documentation/bpf/bpf_iterators.rst line 49
Quoted 10 lines
Documentation/bpf/bpf_iterators.rst +10
-0+be no way to change its size later on without breaking backwards +compatibility, so choose wisely! But given this struct is specific to a given +<type> of iterator, this allows a lot of flexibility: simple iterators could +be fine with just one stack slot (8 bytes), like numbers iterator is, while +some other more complicated iterators might need way more to keep their +iterator state. Either way, such design allows to avoid runtime memory +allocations, which otherwise would be necessary if we fixed on-the-stack size +and it turned out to be too small for a given iterator implementation. + +All kfuncs (constructor, next, destructor) have to be named consistenly as
typo: consistently
Quoted 2 lines
Documentation/bpf/bpf_iterators.rst +1
-0+bpf_iter_<type>_{new,next,destroy}(), respectively. <type> represents iterator
Documentation/bpf/bpf_iterators.rst line 47
Quoted 6 lines · Andrii Nakryiko
Documentation/bpf/bpf_iterators.rst +5
-0+be fine with just one stack slot (8 bytes), like numbers iterator is, while +some other more complicated iterators might need way more to keep their +iterator state. Either way, such design allows to avoid runtime memory +allocations, which otherwise would be necessary if we fixed on-the-stack size +and it turned out to be too small for a given iterator implementation.
This part is a bit unclear.
I think in "if we fixed on-the-stack size" you meant that "if all iterator types had fixed on stack size ..." ?
I think it's too much information. The doc can just say that sizeof(struct bpf_iter_<type>) should be small enough to fit in the bpf prog stack.
It probably can also recommend that _new() should avoid memory allocation when possible and use the stack, but it can allocate if there is no other option and the state is big.
Quoted 12 lines · Alexei Starovoitov
Documentation/bpf/bpf_iterators.rst line 47
Quoted 6 lines · Andrii Nakryiko
Documentation/bpf/bpf_iterators.rst +5
-0+be fine with just one stack slot (8 bytes), like numbers iterator is, while +some other more complicated iterators might need way more to keep their +iterator state. Either way, such design allows to avoid runtime memory +allocations, which otherwise would be necessary if we fixed on-the-stack size +and it turned out to be too small for a given iterator implementation.This part is a bit unclear.
I think in "if we fixed on-the-stack size" you meant that "if all iterator types had fixed on stack size ..." ?
yep
Quoted 7 lines
I think it's too much information. The doc can just say that
sizeof(struct bpf_iter_<type>)should be small enough to fit in the bpf prog stack.
It probably can also recommend that_new()should avoid memory allocation when possible and use the stack, but it can allocate if there is no other option and the state is big.
yep, makes sense, will adjust