On Tue, Jun 03, 2025 at 08:49:59PM -0400, Sasha Levin wrote:
From: Martin KaFai Lau martin.lau@kernel.org
[ Upstream commit 9e3e66c553f705de51707c7ddc7f35ce159a8ef1 ]
In a bpf fq implementation that is much closer to the kernel fq, it will need to traverse the rbtree: https://lore.kernel.org/bpf/20250418224652.105998-13-martin.lau@linux.dev/
...
Acked-by: Kumar Kartikeya Dwivedi memxor@gmail.com Signed-off-by: Martin KaFai Lau martin.lau@kernel.org Link: https://lore.kernel.org/r/20250506015857.817950-4-martin.lau@linux.dev Signed-off-by: Alexei Starovoitov ast@kernel.org Signed-off-by: Sasha Levin sashal@kernel.org
NO This commit should not be backported to stable kernel trees. Here's my extensive analysis: ## Primary Reason: New Feature Addition This commit adds three new kfunc functions (`bpf_rbtree_root`, `bpf_rbtree_left`, `bpf_rbtree_right`) to the BPF rbtree API. These are entirely new capabilities that enable rbtree traversal functionality that did not exist before. ## Specific Code Analysis ### 1. New Function Implementations ```c __bpf_kfunc struct bpf_rb_node *bpf_rbtree_root(struct bpf_rb_root *root) { struct rb_root_cached *r = (struct rb_root_cached *)root; return (struct bpf_rb_node *)r->rb_root.rb_node; } __bpf_kfunc struct bpf_rb_node *bpf_rbtree_left(struct bpf_rb_root *root, struct bpf_rb_node *node) { struct bpf_rb_node_kern *node_internal = (struct bpf_rb_node_kern *)node; if (READ_ONCE(node_internal->owner) != root) return NULL; return (struct bpf_rb_node *)node_internal->rb_node.rb_left; } __bpf_kfunc struct bpf_rb_node *bpf_rbtree_right(struct bpf_rb_root *root, struct bpf_rb_node *node) { struct bpf_rb_node_kern *node_internal = (struct bpf_rb_node_kern *)node; if (READ_ONCE(node_internal->owner) != root) return NULL; return (struct bpf_rb_node *)node_internal->rb_node.rb_right; } ``` These are completely new functions that extend the BPF API surface, which is characteristic of feature additions rather than bug fixes. ### 2. Verifier Infrastructure Expansion The commit adds these new functions to multiple verifier tables: ```c enum special_kfunc_type { // ... existing entries ... KF_bpf_rbtree_root, KF_bpf_rbtree_left, KF_bpf_rbtree_right, // ... } BTF_SET_START(special_kfunc_set) // ... existing entries ... BTF_ID(func, bpf_rbtree_root) BTF_ID(func, bpf_rbtree_left) BTF_ID(func, bpf_rbtree_right) BTF_SET_END(special_kfunc_set) ``` This systematic addition to verifier infrastructure demonstrates this is an API expansion, not a fix. ### 3. Enhanced Function Classification Logic ```c static bool is_bpf_rbtree_api_kfunc(u32 btf_id) { return btf_id == special_kfunc_list[KF_bpf_rbtree_add_impl] || btf_id == special_kfunc_list[KF_bpf_rbtree_remove] || btf_id == special_kfunc_list[KF_bpf_rbtree_first] || + btf_id == special_kfunc_list[KF_bpf_rbtree_root] || + btf_id == special_kfunc_list[KF_bpf_rbtree_left] || + btf_id == special_kfunc_list[KF_bpf_rbtree_right]; } ``` The functions are being added to existing classification systems, expanding the API scope. ### 4. New Argument Validation Logic ```c static bool check_kfunc_is_graph_node_api(struct bpf_verifier_env *env, enum btf_field_type node_field_type, u32 kfunc_btf_id) { // ... existing logic ... case BPF_RB_NODE: ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_remove] || kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_add_impl] || + kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_left] || + kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_right]); break; } ``` This adds new argument validation paths for the new functions. ## Comparison with Similar Commits Looking at the historical examples: - **Similar Commit #1 (YES)**: Added basic rbtree kfuncs - this was part of the foundational rbtree infrastructure - **Similar Commit #2 (YES)**: Added argument support for rbtree types - essential for the basic functionality - **Similar Commit #3 (NO)**: Added function declarations to test headers - clearly test infrastructure - **Similar Commit #4 (NO)**: Added special verifier handling - complex new feature logic - **Similar Commit #5 (YES)**: Added basic BTF support for rbtree types - foundational infrastructure ## Use Case Analysis The commit message describes a complex use case for implementing a Fair Queuing (FQ) algorithm that requires traversal capabilities. This is clearly an advanced feature for specialized networking applications, not a bug fix for existing functionality. ## Risk Assessment Adding new kfuncs carries several risks: 1. **API Stability**: New functions become part of the stable ABI 2. **Complexity**: Introduces new code paths in verifier logic 3. **Testing**: New functionality may not have complete test coverage in stable kernels 4. **Dependencies**: May rely on other recent changes not present in stable trees ## Conclusion This commit represents a clear feature addition that extends the BPF rbtree API with new traversal capabilities. ...
Hi Sasha,
Any reason this patch is included despite your tooling suggest _not_ taking the patch into stable?
It does not fix any existing bugs or address critical issues. The functionality is designed for advanced use cases and represents an expansion of the BPF programming model rather than maintenance of existing capabilities. Following stable tree guidelines, this should remain in mainline development kernels and not be backported to stable releases.
I don't see a Stable-dep-of tag, so it seem more likely that this patch was accidentally selected.
Also could you have the tooling's decision log better formatted? In it's current form it cannot be easily read.
Thanks, Shung-Hsi Yu
kernel/bpf/helpers.c | 30 ++++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 22 ++++++++++++++++++---- 2 files changed, 48 insertions(+), 4 deletions(-)
diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c index a71aa4cb85fae..6a55198c2d9ad 100644 --- a/kernel/bpf/helpers.c +++ b/kernel/bpf/helpers.c @@ -2367,6 +2367,33 @@ __bpf_kfunc struct bpf_rb_node *bpf_rbtree_first(struct bpf_rb_root *root) return (struct bpf_rb_node *)rb_first_cached(r); } +__bpf_kfunc struct bpf_rb_node *bpf_rbtree_root(struct bpf_rb_root *root) +{
- struct rb_root_cached *r = (struct rb_root_cached *)root;
- return (struct bpf_rb_node *)r->rb_root.rb_node;
+}
...