Skip to contentSkip to conversation

bpf, docs: document open-coded BPF iterators

PATCH Superseded Andrii Nakryiko 4 participants 4 messages May 6, 2025 – May 7, 2025

Subsystems (2)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Andrii Nakryiko

author maintainer
#0 lore raw

PATCH 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
index 385cd05aabf5..f3e9c8894c30 100644
@@ -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
maintainer Acked-by on v1 1/1
#1 lore raw
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]/

---

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
index 385cd05aabf5..f3e9c8894c30 100644
@@ -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
[...]
#2 lore raw
In reply to Andrii Nakryiko

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.

#3 lore raw
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