bpf: add new BPF_CGROUP_ITER_CHILDREN_ONLY control option
Subsystems (4)
PATCH 1/2 bpf: add new BPF_CGROUP_ITER_CHILDREN_ONLY control option
Currently, the BPF cgroup iterator supports walking descendants in either pre-order (BPF_CGROUP_ITER_DESCENDANTS_PRE) or post-order (BPF_CGROUP_ITER_DESCENDANTS_POST). These modes perform an exhaustive depth-first search (DFS) of the hierarchy. In scenarios where a BPF program may need to inspect only the direct children of a given parent cgroup, a full DFS is unnecessarily expensive.
This patch introduces a new BPF cgroup iterator control option, BPF_CGROUP_ITER_CHILDREN_ONLY. This control option restricts the traversal to the immediate children of a specified parent cgroup, allowing for more targeted and efficient iteration, particularly when exhaustive depth-first search (DFS) traversal is not required.
--- include/uapi/linux/bpf.h | 16 ++++++++++++---- kernel/bpf/cgroup_iter.c | 26 +++++++++++++++++++++----- tools/include/uapi/linux/bpf.h | 16 ++++++++++++---- 3 files changed, 45 insertions(+), 13 deletions(-)
include/uapi/linux/bpf.h +12 -4
@@ -115,10 +115,18 @@ struct bpf_cgroup_storage_key {enum bpf_cgroup_iter_order {BPF_CGROUP_ITER_ORDER_UNSPEC =0 , -BPF_CGROUP_ITER_SELF_ONLY ,/* process only a single object. */ -BPF_CGROUP_ITER_DESCENDANTS_PRE ,/* walk descendants in pre-order. */ -BPF_CGROUP_ITER_DESCENDANTS_POST ,/* walk descendants in post-order. */ -BPF_CGROUP_ITER_ANCESTORS_UP ,/* walk ancestors upward. */ +BPF_CGROUP_ITER_SELF_ONLY ,/* process only a single object. */ +BPF_CGROUP_ITER_DESCENDANTS_PRE ,/* walk descendants in pre-order. */ +BPF_CGROUP_ITER_DESCENDANTS_POST ,/* walk descendants in post-order. */ +BPF_CGROUP_ITER_ANCESTORS_UP ,/* walk ancestors upward. */ +/* +* Walks the immediate children of the specified parent +* cgroup_subsys_state. Unlike BPF_CGROUP_ITER_DESCENDANTS_PRE, +* BPF_CGROUP_ITER_DESCENDANTS_POST, and BPF_CGROUP_ITER_ANCESTORS_UP +* the iterator does not include the specified parent as one of the +* returned iterator elements. +*/ +BPF_CGROUP_ITER_CHILDREN_ONLY , };union bpf_iter_link_info {
kernel/bpf/cgroup_iter.c +21 -5
@@ -8,12 +8,13 @@#include "../cgroup/cgroup-internal.h" /* cgroup_mutex and cgroup_is_dead */ -/* cgroup_iter provides four modes of traversal to the cgroup hierarchy. +/* cgroup_iter provides five modes of traversal to the cgroup hierarchy. * * 1. Walk the descendants of a cgroup in pre-order. * 2. Walk the descendants of a cgroup in post-order. * 3. Walk the ancestors of a cgroup. * 4. Show the given cgroup only. +* 5. Walk only the children of a given parent cgroup. * * For walking descendants, cgroup_iter can walk in either pre-order or * post-order. For walking ancestors, the iter walks up from a cgroup to
@@ -78,6 +79,8 @@ static void *cgroup_iter_seq_start(struct seq_file *seq, loff_t *pos)return css_next_descendant_pre (NULL , p->start_css); else if (p->order == BPF_CGROUP_ITER_DESCENDANTS_POST) return css_next_descendant_post(NULL, p->start_css); + else if (p->order == BPF_CGROUP_ITER_CHILDREN_ONLY) + return css_next_child(NULL, p->start_css); else /* BPF_CGROUP_ITER_SELF_ONLY and BPF_CGROUP_ITER_ANCESTORS_UP */ return p->start_css; }
@@ -113,6 +116,8 @@ static void *cgroup_iter_seq_next(struct seq_file *seq, void *v, loff_t *pos)return css_next_descendant_post (curr, p->start_css); else if (p->order == BPF_CGROUP_ITER_ANCESTORS_UP) return curr->parent; + else if (p->order == BPF_CGROUP_ITER_CHILDREN_ONLY) + return css_next_child(curr, p->start_css); else /* BPF_CGROUP_ITER_SELF_ONLY */ return NULL; }
@@ -200,11 +205,16 @@ static int bpf_iter_attach_cgroup(struct bpf_prog *prog,int order = linfo->cgroup.order;struct cgroup *cgrp; -if (order !=BPF_CGROUP_ITER_DESCENDANTS_PRE && - order !=BPF_CGROUP_ITER_DESCENDANTS_POST && - order !=BPF_CGROUP_ITER_ANCESTORS_UP && - order !=BPF_CGROUP_ITER_SELF_ONLY ) +switch (order) { +case BPF_CGROUP_ITER_DESCENDANTS_PRE : +case BPF_CGROUP_ITER_DESCENDANTS_POST : +case BPF_CGROUP_ITER_ANCESTORS_UP : +case BPF_CGROUP_ITER_SELF_ONLY : +case BPF_CGROUP_ITER_CHILDREN_ONLY : +break ; +default :return -EINVAL ; + }if (fd && id)return -EINVAL ;
@@ -257,6 +267,8 @@ static void bpf_iter_cgroup_show_fdinfo(const struct bpf_iter_aux_info *aux,seq_puts (seq,"order: descendants_post\n" ); else if (aux->cgroup.order == BPF_CGROUP_ITER_ANCESTORS_UP) seq_puts(seq, "order: ancestors_up\n"); + else if (aux->cgroup.order == BPF_CGROUP_ITER_CHILDREN_ONLY) + seq_puts(seq, "order: children_only\n"); else /* BPF_CGROUP_ITER_SELF_ONLY */ seq_puts(seq, "order: self_only\n"); }
@@ -320,6 +332,7 @@ __bpf_kfunc int bpf_iter_css_new(struct bpf_iter_css *it,case BPF_CGROUP_ITER_DESCENDANTS_PRE :case BPF_CGROUP_ITER_DESCENDANTS_POST :case BPF_CGROUP_ITER_ANCESTORS_UP : +case BPF_CGROUP_ITER_CHILDREN_ONLY :break ;default :return -EINVAL ;
@@ -345,6 +358,9 @@ __bpf_kfunc struct cgroup_subsys_state *bpf_iter_css_next(struct bpf_iter_css *icase BPF_CGROUP_ITER_DESCENDANTS_POST : kit->pos =css_next_descendant_post (kit->pos, kit->start);break ; +case BPF_CGROUP_ITER_CHILDREN_ONLY : + kit->pos =css_next_child (kit->pos, kit->start); +break ;case BPF_CGROUP_ITER_ANCESTORS_UP : kit->pos = kit->pos ? kit->pos->parent : kit->start; }
tools/include/uapi/linux/bpf.h +12 -4
@@ -115,10 +115,18 @@ struct bpf_cgroup_storage_key {enum bpf_cgroup_iter_order {BPF_CGROUP_ITER_ORDER_UNSPEC =0 , -BPF_CGROUP_ITER_SELF_ONLY ,/* process only a single object. */ -BPF_CGROUP_ITER_DESCENDANTS_PRE ,/* walk descendants in pre-order. */ -BPF_CGROUP_ITER_DESCENDANTS_POST ,/* walk descendants in post-order. */ -BPF_CGROUP_ITER_ANCESTORS_UP ,/* walk ancestors upward. */ +BPF_CGROUP_ITER_SELF_ONLY ,/* process only a single object. */ +BPF_CGROUP_ITER_DESCENDANTS_PRE ,/* walk descendants in pre-order. */ +BPF_CGROUP_ITER_DESCENDANTS_POST ,/* walk descendants in post-order. */ +BPF_CGROUP_ITER_ANCESTORS_UP ,/* walk ancestors upward. */ +/* +* Walks the immediate children of the specified parent +* cgroup_subsys_state. Unlike BPF_CGROUP_ITER_DESCENDANTS_PRE, +* BPF_CGROUP_ITER_DESCENDANTS_POST, and BPF_CGROUP_ITER_ANCESTORS_UP +* the iterator does not include the specified parent as one of the +* returned iterator elements. +*/ +BPF_CGROUP_ITER_CHILDREN_ONLY , };union bpf_iter_link_info {
Signature · 1 line
2.52.0.457.g6b5491de43-goog
PATCH 2/2 bpf/selftests: cover BPF_CGROUP_ITER_CHILDREN_ONLY control option
Extend some of the existing CSS iterator selftests such that they cover the newly introduced BPF_CGROUP_ITER_CHILDREN_ONLY iterator control option.
--- tools/testing/selftests/bpf/prog_tests/cgroup_iter.c | 12 ++++++++++++ tools/testing/selftests/bpf/prog_tests/iters.c | 8 +++++++- tools/testing/selftests/bpf/progs/iters_css.c | 9 ++++++--- 3 files changed, 25 insertions(+), 4 deletions(-)
tools/testing/selftests/bpf/prog_tests/cgroup_iter.c +12 -0
@@ -190,6 +190,16 @@ static void test_walk_self_only(struct cgroup_iter *skel) BPF_CGROUP_ITER_SELF_ONLY, "self_only"); } +static void test_walk_children_only (struct cgroup_iter *skel) +{ +snprintf (expected_output,sizeof (expected_output), +PROLOGUE "%8llu\n%8llu\n" EPILOGUE , cg_id[CHILD1 ], + cg_id[CHILD2 ]); + +read_from_cgroup_iter (skel->progs.cgroup_id_printer, cg_fd[PARENT ], +BPF_CGROUP_ITER_CHILDREN_ONLY ,"children" ); +} +static void test_walk_dead_self_only (struct cgroup_iter *skel) {DECLARE_LIBBPF_OPTS (bpf_iter_attach_opts, opts);
@@ -325,6 +335,8 @@ void test_cgroup_iter(void)test_walk_dead_self_only (skel);if (test__start_subtest ("cgroup_iter__self_only_css_task" ))test_walk_self_only_css_task (); +if (test__start_subtest ("cgroup_iter__children_only" )) +test_walk_children_only (skel); out:cgroup_iter__destroy (skel);
tools/testing/selftests/bpf/prog_tests/iters.c +7 -1
@@ -253,6 +253,11 @@ static void subtest_css_iters(void) { "/cg1/cg2" }, { "/cg1/cg2/cg3" }, { "/cg1/cg2/cg3/cg4" }, + { "/cg1/cg5" }, + { "/cg1/cg5/cg6" }, + { "/cg1/cg7" }, + { "/cg1/cg7/cg8" }, + { "/cg1/cg7/cg8/cg9" }, };int err, cg_nr =ARRAY_SIZE (cgs);int i;
@@ -284,7 +289,8 @@ static void subtest_css_iters(void)ASSERT_EQ (skel->bss->post_order_cnt, cg_nr,"post_order_cnt" );ASSERT_EQ (skel->bss->last_cg_id,get_cgroup_id (cgs[0 ].path),"last_cg_id" ); -ASSERT_EQ (skel->bss->tree_high, cg_nr -1 ,"tree_high" ); +ASSERT_EQ (skel->bss->children_cnt,3 ,"children_cnt" ); +ASSERT_EQ (skel->bss->tree_high,3 ,"tree_high" );iters_css__detach (skel); cleanup:cleanup_cgroup_environment ();
tools/testing/selftests/bpf/progs/iters_css.c +6 -3
@@ -12,8 +12,7 @@ char _license[] SEC("license") = "GPL";pid_t target_pid;u64 root_cg_id, leaf_cg_id;u64 first_cg_id, last_cg_id; - -int pre_order_cnt, post_order_cnt, tree_high; +int pre_order_cnt, post_order_cnt, children_cnt, tree_high;struct cgroup *bpf_cgroup_from_id (u64 cgid) __ksym; void bpf_cgroup_release(struct cgroup *p) __ksym;
@@ -43,7 +42,7 @@ int iter_css_for_each(const void *ctx) } root_css = &root_cgrp->self; leaf_css = &leaf_cgrp->self; - pre_order_cnt = post_order_cnt = tree_high =0 ; + pre_order_cnt = post_order_cnt = children_cnt = tree_high =0 ; first_cg_id = last_cg_id =0 ;bpf_rcu_read_lock ();
@@ -60,6 +59,10 @@ int iter_css_for_each(const void *ctx) first_cg_id = cur_cgrp->kn->id; } +bpf_for_each (css, pos, root_css,BPF_CGROUP_ITER_CHILDREN_ONLY ) { + children_cnt++; + } +bpf_for_each (css, pos, leaf_css,BPF_CGROUP_ITER_ANCESTORS_UP ) tree_high++;
Signature · 1 line
2.52.0.457.g6b5491de43-goog
Song Liu
reviewerQuoted 8 lines · Matt Bobrowski
Currently, the BPF cgroup iterator supports walking descendants in either pre-order (
BPF_CGROUP_ITER_DESCENDANTS_PRE) or post-order (BPF_CGROUP_ITER_DESCENDANTS_POST). These modes perform an exhaustive depth-first search (DFS) of the hierarchy. In scenarios where a BPF program may need to inspect only the direct children of a given parent cgroup, a full DFS is unnecessarily expensive.
Quoted 7 lines
This patch introduces a new BPF cgroup iterator control option,
BPF_CGROUP_ITER_CHILDREN_ONLY. This control option restricts the traversal to the immediate children of a specified parent cgroup, allowing for more targeted and efficient iteration, particularly when exhaustive depth-first search (DFS) traversal is not required.Signed-off-by Matt Bobrowski <[email protected]>
The code looks good to me.
Some nitpick and some high level questions/ideas below
include/uapi/linux/bpf.h struct bpf_cgroup_storage_key { · line 121
Quoted 10 lines
enum
bpf_cgroup_iter_order{
BPF_CGROUP_ITER_ORDER_UNSPEC= 0,include/uapi/linux/bpf.h +4
-4-BPF_CGROUP_ITER_SELF_ONLY ,/* process only a single object. */ -BPF_CGROUP_ITER_DESCENDANTS_PRE ,/* walk descendants in pre-order. */ -BPF_CGROUP_ITER_DESCENDANTS_POST ,/* walk descendants in post-order. */ - BPF_CGROUP_ITER_ANCESTORS_UP, /* walk ancestors upward. */ +BPF_CGROUP_ITER_SELF_ONLY ,/* process only a single object. */ +BPF_CGROUP_ITER_DESCENDANTS_PRE ,/* walk descendants in pre-order. */ +BPF_CGROUP_ITER_DESCENDANTS_POST ,/* walk descendants in post-order. */ + BPF_CGROUP_ITER_ANCESTORS_UP, /* walk ancestors upward. */
Changes above seem unnecessary.
Quoted 9 lines
include/uapi/linux/bpf.h +8
-0+/* +* Walks the immediate children of the specified parent +* cgroup_subsys_state. Unlike BPF_CGROUP_ITER_DESCENDANTS_PRE, +* BPF_CGROUP_ITER_DESCENDANTS_POST, and BPF_CGROUP_ITER_ANCESTORS_UP +* the iterator does not include the specified parent as one of the +* returned iterator elements. +*/ + BPF_CGROUP_ITER_CHILDREN_ONLY, };
[...]
Quoted 9 lines
kernel/bpf/cgroup_iter.c +1
-0@@ -320,6 +332,7 @@ __bpf_kfunc int bpf_iter_css_new(struct bpf_iter_css *it,case BPF_CGROUP_ITER_DESCENDANTS_PRE :case BPF_CGROUP_ITER_DESCENDANTS_POST :case BPF_CGROUP_ITER_ANCESTORS_UP : +case BPF_CGROUP_ITER_CHILDREN_ONLY :break ;default :return -EINVAL ;
kernel/bpf/cgroup_iter.c __bpf_kfunc struct cgroup_subsys_state *bpf_iter_css_next(struct bpf_iter_css *i · line 366
Quoted 9 lines
kernel/bpf/cgroup_iter.c +3
-0@@ -345,6 +358,9 @@ __bpf_kfunc struct cgroup_subsys_state *bpf_iter_css_next(struct bpf_iter_css *icase BPF_CGROUP_ITER_DESCENDANTS_POST : kit->pos =css_next_descendant_post (kit->pos, kit->start);break ; +case BPF_CGROUP_ITER_CHILDREN_ONLY : + kit->pos =css_next_child (kit->pos, kit->start); +break ;case BPF_CGROUP_ITER_ANCESTORS_UP : kit->pos = kit->pos ? kit->pos->parent : kit->start; }
I wonder whether we can use the return values and/or the kfuncs to enable more flexible walks. For example, some return value means "do not walk more children, go back to the parent". This will enable use cases like "walk children and grandchildren nodes from here, but not any deeper". WDYT?
Thanks,
Song
Quoted 15 lines · Song Liu
Quoted 14 lines · Matt Bobrowski
Currently, the BPF cgroup iterator supports walking descendants in either pre-order (
BPF_CGROUP_ITER_DESCENDANTS_PRE) or post-order (BPF_CGROUP_ITER_DESCENDANTS_POST). These modes perform an exhaustive depth-first search (DFS) of the hierarchy. In scenarios where a BPF program may need to inspect only the direct children of a given parent cgroup, a full DFS is unnecessarily expensive.This patch introduces a new BPF cgroup iterator control option,
BPF_CGROUP_ITER_CHILDREN_ONLY. This control option restricts the traversal to the immediate children of a specified parent cgroup, allowing for more targeted and efficient iteration, particularly when exhaustive depth-first search (DFS) traversal is not required.
Quoted 5 lines
Quoted 1 line
Signed-off-by Matt Bobrowski <[email protected]>The code looks good to me.
Some nitpick and some high level questions/ideas below
Sure, thank you for taking a look!
Quoted 11 lines
include/uapi/linux/bpf.h struct bpf_cgroup_storage_key { · line 121
Quoted 10 lines
enum
bpf_cgroup_iter_order{
BPF_CGROUP_ITER_ORDER_UNSPEC= 0,include/uapi/linux/bpf.h +4
-4-BPF_CGROUP_ITER_SELF_ONLY ,/* process only a single object. */ -BPF_CGROUP_ITER_DESCENDANTS_PRE ,/* walk descendants in pre-order. */ -BPF_CGROUP_ITER_DESCENDANTS_POST ,/* walk descendants in post-order. */ - BPF_CGROUP_ITER_ANCESTORS_UP, /* walk ancestors upward. */ +BPF_CGROUP_ITER_SELF_ONLY ,/* process only a single object. */ +BPF_CGROUP_ITER_DESCENDANTS_PRE ,/* walk descendants in pre-order. */ +BPF_CGROUP_ITER_DESCENDANTS_POST ,/* walk descendants in post-order. */ + BPF_CGROUP_ITER_ANCESTORS_UP, /* walk ancestors upward. */
Quoted 1 line
Changes above seem unnecessary.
This is just noise, sorry. Will revert this once I send out v2.
Quoted 28 lines
Quoted 9 lines
include/uapi/linux/bpf.h +8
-0+/* +* Walks the immediate children of the specified parent +* cgroup_subsys_state. Unlike BPF_CGROUP_ITER_DESCENDANTS_PRE, +* BPF_CGROUP_ITER_DESCENDANTS_POST, and BPF_CGROUP_ITER_ANCESTORS_UP +* the iterator does not include the specified parent as one of the +* returned iterator elements. +*/ + BPF_CGROUP_ITER_CHILDREN_ONLY, };[...]
Quoted 16 lines
kernel/bpf/cgroup_iter.c +4
-0@@ -320,6 +332,7 @@ __bpf_kfunc int bpf_iter_css_new(struct bpf_iter_css *it,case BPF_CGROUP_ITER_DESCENDANTS_PRE :case BPF_CGROUP_ITER_DESCENDANTS_POST :case BPF_CGROUP_ITER_ANCESTORS_UP : +case BPF_CGROUP_ITER_CHILDREN_ONLY :break ;default :return -EINVAL ;@@ -345,6 +358,9 @@ __bpf_kfunc struct cgroup_subsys_state *bpf_iter_css_next(struct bpf_iter_css *icase BPF_CGROUP_ITER_DESCENDANTS_POST : kit->pos =css_next_descendant_post (kit->pos, kit->start);break ; +case BPF_CGROUP_ITER_CHILDREN_ONLY : + kit->pos =css_next_child (kit->pos, kit->start); +break ;case BPF_CGROUP_ITER_ANCESTORS_UP :
Quoted 8 lines
kernel/bpf/cgroup_iter.c __bpf_kfunc struct cgroup_subsys_state *bpf_iter_css_next(struct bpf_iter_css *i · line 366
Quoted 2 lines
kernel/bpf/cgroup_iter.c +0
-0kit->pos = kit->pos ? kit->pos->parent : kit->start; }I wonder whether we can use the return values and/or the kfuncs to enable more flexible walks. For example, some return value means "do not walk more children, go back to the parent". This will enable use cases like "walk children and grandchildren nodes from here, but not any deeper". WDYT?
Some general control over whether the DFS traversal should continue in a specific direction could be nice. That way you could reverse out of a specific subtree/branch early without necessarily having to walk all nodes under a given subtree/branch.
With the above said however, it's not really a control/semantic which I'm after at this point. I'm purely interested in exhaustively iterating children of a given parent before selectively deciding which subtree/branch, and therefore parent, I'd like to explore next.
kernel/bpf/cgroup_iter.c __bpf_kfunc struct cgroup_subsys_state *bpf_iter_css_next(struct bpf_iter_css *i · line 363
Quoted 5 lines · Matt Bobrowski
break;kernel/bpf/cgroup_iter.c +3
-0+case BPF_CGROUP_ITER_CHILDREN_ONLY : + kit->pos =css_next_child (kit->pos, kit->start); +break ;
There are no users of css_next_child() outside of cgroup internals. It's a red flag for me. I feel there is something wrong with the use case. It should have been handled by the primitives we have.
pw-bot: cr
Quoted 9 lines · Alexei Starovoitov
kernel/bpf/cgroup_iter.c __bpf_kfunc struct cgroup_subsys_state *bpf_iter_css_next(struct bpf_iter_css *i · line 363
Quoted 5 lines · Matt Bobrowski
break;kernel/bpf/cgroup_iter.c +3
-0+case BPF_CGROUP_ITER_CHILDREN_ONLY : + kit->pos =css_next_child (kit->pos, kit->start); +break ;There are no users of
css_next_child()outside of cgroup internals. It's a red flag for me.
Hm, I can see the slight hesitation here. However, until somewhat recently, the same argument could have been applied to functions like css_next_descendant_post(), right?
css_next_descendant_post() has rather recently started seeing usage in other subsystems (block/, kernel/sched/, kernel/bpf), despite remaining internal-only since its inception over a decade ago. Given that css_next_descendant_post() continues to remain unexported, in all fairness, I don't see css_next_child() being all that different in this context.
Would your stance change if Tejun agreed to mark css_next_child() as exportable, or simply agreed to it being used from BPF cgroup iterators?
Both css_next_child() and css_for_each_child() have remained virtually unchanged - and therefore inherently stable - since their introduction. I should also mention that functions like css_next_child() and css_next_descendant_post() were originally marked as exported, and only later unmarked. This presumably was done as part of a symbol cleanup, not because the functions were unstable primitives.
Quoted 2 lines
I feel there is something wrong with the use case. It should have been handled by the primitives we have.
Right, arguably it could be handled with the current set of primitives, but it isn't nice and certainly not as efficient as I'd like.
Quoted 35 lines · Matt Bobrowski
Quoted 9 lines · Alexei Starovoitov
kernel/bpf/cgroup_iter.c __bpf_kfunc struct cgroup_subsys_state *bpf_iter_css_next(struct bpf_iter_css *i · line 363
Quoted 5 lines · Matt Bobrowski
break;kernel/bpf/cgroup_iter.c +3
-0+case BPF_CGROUP_ITER_CHILDREN_ONLY : + kit->pos =css_next_child (kit->pos, kit->start); +break ;There are no users of
css_next_child()outside of cgroup internals. It's a red flag for me.Hm, I can see the slight hesitation here. However, until somewhat recently, the same argument could have been applied to functions like
css_next_descendant_post(), right?
css_next_descendant_post()has rather recently started seeing usage in other subsystems (block/,kernel/sched/, kernel/bpf), despite remaining internal-only since its inception over a decade ago. Given thatcss_next_descendant_post()continues to remain unexported, in all fairness, I don't seecss_next_child()being all that different in this context.Would your stance change if Tejun agreed to mark
css_next_child()as exportable, or simply agreed to it being used from BPF cgroup iterators?Both
css_next_child()andcss_for_each_child()have remained virtually unchanged - and therefore inherently stable - since their introduction. I should also mention that functions likecss_next_child()andcss_next_descendant_post()were originally marked as exported, and only later unmarked. This presumably was done as part of a symbol cleanup, not because the functions were unstable primitives.
Quoted 6 lines
Quoted 2 lines
I feel there is something wrong with the use case. It should have been handled by the primitives we have.
Right, arguably it could be handled with the current set of primitives, but it isn't nice and certainly not as efficient as I'd like.
Why is it? Just descdant_pre and break out of the loop if not immediate. The thought process should be to use what's available as much as possible. Adding UAPI for specific use cases isn't great.
If it was a new kfunc that's one thing, but here you're touching uapi/bpf.h So acceptance bar is much much higher.
Quoted 36 lines · Alexei Starovoitov
Quoted 35 lines · Matt Bobrowski
Quoted 9 lines · Alexei Starovoitov
kernel/bpf/cgroup_iter.c __bpf_kfunc struct cgroup_subsys_state *bpf_iter_css_next(struct bpf_iter_css *i · line 363
Quoted 5 lines · Matt Bobrowski
break;kernel/bpf/cgroup_iter.c +3
-0+case BPF_CGROUP_ITER_CHILDREN_ONLY : + kit->pos =css_next_child (kit->pos, kit->start); +break ;There are no users of
css_next_child()outside of cgroup internals. It's a red flag for me.Hm, I can see the slight hesitation here. However, until somewhat recently, the same argument could have been applied to functions like
css_next_descendant_post(), right?
css_next_descendant_post()has rather recently started seeing usage in other subsystems (block/,kernel/sched/, kernel/bpf), despite remaining internal-only since its inception over a decade ago. Given thatcss_next_descendant_post()continues to remain unexported, in all fairness, I don't seecss_next_child()being all that different in this context.Would your stance change if Tejun agreed to mark
css_next_child()as exportable, or simply agreed to it being used from BPF cgroup iterators?Both
css_next_child()andcss_for_each_child()have remained virtually unchanged - and therefore inherently stable - since their introduction. I should also mention that functions likecss_next_child()andcss_next_descendant_post()were originally marked as exported, and only later unmarked. This presumably was done as part of a symbol cleanup, not because the functions were unstable primitives.
Quoted 8 lines
Quoted 6 lines
Quoted 2 lines
I feel there is something wrong with the use case. It should have been handled by the primitives we have.
Right, arguably it could be handled with the current set of primitives, but it isn't nice and certainly not as efficient as I'd like.
Why is it? Just
descdant_preand break out of the loop if not immediate.
If I use a break when I hit a grandchild in pre-order traversal, I will still terminate the loop early and miss all the subsequent immediate children?
I do understand that using css_next_descendant_post() (without a break) could allow me to logically filter for children in the loop. However, my concern is purely about algorithmic complexity and scalability.
css_next_descendant_post() performs a full subtree walk (O(Descendants)). If I have a top-level cgroup with only a few children but a massive hierarchy underneath (hundreds/thousands of grandchildren), using the descendant based iterator requires me to literally visit every single node in that subtree.
In contrast, iterating immediate children is just a linked-list walk (O(Children)). For deep hierarchies, the performance difference is not constant - it's orders of magnitude.
For example, if I have 5 children under a given root/parent with each of those 5 children having 500 nested descedants each:
- A pre-order traversal would lead me to visiting 2505 nodes.
- A linear traversal would lead me to visting 5 nodes.
Quoted 1 line
The thought process should be to use what's available as much as possible.
Well, I get that and it was my initial idea. But, I quickly realized that we have a gap in the current iterators capabilities, and this patch is meant to address this gap.
Quoted 3 lines
Adding UAPI for specific use cases isn't great.
If it was a new kfunc that's one thing, but here you're touchinguapi/bpf.hSo acceptance bar is much much higher.
OK, but now that Tejun confirmed [0] that he's fine with exposing css_next_child(), how does this weigh up?
Quoted 77 lines · Matt Bobrowski
Quoted 36 lines · Alexei Starovoitov
Quoted 35 lines · Matt Bobrowski
Quoted 9 lines · Alexei Starovoitov
kernel/bpf/cgroup_iter.c __bpf_kfunc struct cgroup_subsys_state *bpf_iter_css_next(struct bpf_iter_css *i · line 363
Quoted 5 lines · Matt Bobrowski
break;kernel/bpf/cgroup_iter.c +3
-0+case BPF_CGROUP_ITER_CHILDREN_ONLY : + kit->pos =css_next_child (kit->pos, kit->start); +break ;There are no users of
css_next_child()outside of cgroup internals. It's a red flag for me.Hm, I can see the slight hesitation here. However, until somewhat recently, the same argument could have been applied to functions like
css_next_descendant_post(), right?
css_next_descendant_post()has rather recently started seeing usage in other subsystems (block/,kernel/sched/, kernel/bpf), despite remaining internal-only since its inception over a decade ago. Given thatcss_next_descendant_post()continues to remain unexported, in all fairness, I don't seecss_next_child()being all that different in this context.Would your stance change if Tejun agreed to mark
css_next_child()as exportable, or simply agreed to it being used from BPF cgroup iterators?Both
css_next_child()andcss_for_each_child()have remained virtually unchanged - and therefore inherently stable - since their introduction. I should also mention that functions likecss_next_child()andcss_next_descendant_post()were originally marked as exported, and only later unmarked. This presumably was done as part of a symbol cleanup, not because the functions were unstable primitives.Quoted 8 lines
Quoted 6 lines
Quoted 2 lines
I feel there is something wrong with the use case. It should have been handled by the primitives we have.
Right, arguably it could be handled with the current set of primitives, but it isn't nice and certainly not as efficient as I'd like.
Why is it? Just
descdant_preand break out of the loop if not immediate.If I use a break when I hit a grandchild in pre-order traversal, I will still terminate the loop early and miss all the subsequent immediate children?
I do understand that using
css_next_descendant_post()(without a break) could allow me to logically filter for children in the loop. However, my concern is purely about algorithmic complexity and scalability.
css_next_descendant_post()performs a full subtree walk (O(Descendants)). If I have a top-level cgroup with only a few children but a massive hierarchy underneath (hundreds/thousands of grandchildren), using the descendant based iterator requires me to literally visit every single node in that subtree.In contrast, iterating immediate children is just a linked-list walk (O(Children)). For deep hierarchies, the performance difference is not constant - it's orders of magnitude.
For example, if I have 5 children under a given root/parent with each of those 5 children having 500 nested descedants each:
- A pre-order traversal would lead me to visiting 2505 nodes.
- A linear traversal would lead me to visting 5 nodes.Quoted 1 line
The thought process should be to use what's available as much as possible.
Well, I get that and it was my initial idea. But, I quickly realized that we have a gap in the current iterators capabilities, and this patch is meant to address this gap.
Quoted 6 lines
Quoted 3 lines
Adding UAPI for specific use cases isn't great.
If it was a new kfunc that's one thing, but here you're touchinguapi/bpf.hSo acceptance bar is much much higher.OK, but now that Tejun confirmed [0] that he's fine with exposing
css_next_child(), how does this weigh up?
ok. let's add it.
Maybe shorten the name toBPF_CGROUP_ITER_CHILDREN
"_ONLY" looks unnecessary.
Quoted 82 lines · Alexei Starovoitov
Quoted 81 lines · Matt Bobrowski
Quoted 36 lines · Alexei Starovoitov
Quoted 35 lines · Matt Bobrowski
Quoted 9 lines · Alexei Starovoitov
kernel/bpf/cgroup_iter.c __bpf_kfunc struct cgroup_subsys_state *bpf_iter_css_next(struct bpf_iter_css *i · line 363
Quoted 5 lines · Matt Bobrowski
break;kernel/bpf/cgroup_iter.c +3
-0+case BPF_CGROUP_ITER_CHILDREN_ONLY : + kit->pos =css_next_child (kit->pos, kit->start); +break ;There are no users of
css_next_child()outside of cgroup internals. It's a red flag for me.Hm, I can see the slight hesitation here. However, until somewhat recently, the same argument could have been applied to functions like
css_next_descendant_post(), right?
css_next_descendant_post()has rather recently started seeing usage in other subsystems (block/,kernel/sched/, kernel/bpf), despite remaining internal-only since its inception over a decade ago. Given thatcss_next_descendant_post()continues to remain unexported, in all fairness, I don't seecss_next_child()being all that different in this context.Would your stance change if Tejun agreed to mark
css_next_child()as exportable, or simply agreed to it being used from BPF cgroup iterators?Both
css_next_child()andcss_for_each_child()have remained virtually unchanged - and therefore inherently stable - since their introduction. I should also mention that functions likecss_next_child()andcss_next_descendant_post()were originally marked as exported, and only later unmarked. This presumably was done as part of a symbol cleanup, not because the functions were unstable primitives.Quoted 8 lines
Quoted 6 lines
Quoted 2 lines
I feel there is something wrong with the use case. It should have been handled by the primitives we have.
Right, arguably it could be handled with the current set of primitives, but it isn't nice and certainly not as efficient as I'd like.
Why is it? Just
descdant_preand break out of the loop if not immediate.If I use a break when I hit a grandchild in pre-order traversal, I will still terminate the loop early and miss all the subsequent immediate children?
I do understand that using
css_next_descendant_post()(without a break) could allow me to logically filter for children in the loop. However, my concern is purely about algorithmic complexity and scalability.
css_next_descendant_post()performs a full subtree walk (O(Descendants)). If I have a top-level cgroup with only a few children but a massive hierarchy underneath (hundreds/thousands of grandchildren), using the descendant based iterator requires me to literally visit every single node in that subtree.In contrast, iterating immediate children is just a linked-list walk (O(Children)). For deep hierarchies, the performance difference is not constant - it's orders of magnitude.
For example, if I have 5 children under a given root/parent with each of those 5 children having 500 nested descedants each:
- A pre-order traversal would lead me to visiting 2505 nodes.
- A linear traversal would lead me to visting 5 nodes.Quoted 1 line
The thought process should be to use what's available as much as possible.
Well, I get that and it was my initial idea. But, I quickly realized that we have a gap in the current iterators capabilities, and this patch is meant to address this gap.
Quoted 3 lines
Adding UAPI for specific use cases isn't great.
If it was a new kfunc that's one thing, but here you're touchinguapi/bpf.hSo acceptance bar is much much higher.
Quoted 7 lines
Quoted 2 lines
OK, but now that Tejun confirmed [0] that he's fine with exposing
css_next_child(), how does this weigh up?ok. let's add it.
Maybe shorten the name toBPF_CGROUP_ITER_CHILDREN
"_ONLY" looks unnecessary.
Sounds good, thank you. Shortening to BPF_CGROUP_ITER_CHILDREN is OK too. Will send it out as part of v2.
Hello,
Quoted 3 lines · Matt Bobrowski
Would your stance change if Tejun agreed to mark
css_next_child()as exportable, or simply agreed to it being used from BPF cgroup iterators?
FWIW, I don't think there's any issue to exposing css_next_child(). This is a part of the fundamental structure of cgroups and I don't see it changing in any foreseeable future. That said, I wonder whether it'd be more flexible to expose css_rightmost_descendant() which allows skipping the current subtree during pre-order traversals. However, this has higher complexity for traversing just immediate children as it would have to skip each child subtree.
Thanks.
Signature · 1 line
tejun
Quoted 10 lines · Tejun Heo
Hello,
Quoted 3 lines · Matt Bobrowski
Would your stance change if Tejun agreed to mark
css_next_child()as exportable, or simply agreed to it being used from BPF cgroup iterators?FWIW, I don't think there's any issue to exposing
css_next_child(). This is a part of the fundamental structure of cgroups and I don't see it changing in any foreseeable future.
Thanks for weighing in on this Tejun.
Quoted 5 lines
That said, I wonder whether it'd be more flexible to expose
css_rightmost_descendant()which allows skipping the current subtree during pre-order traversals. However, this has higher complexity for traversing just immediate children as it would have to skip each child subtree.
Yeah, css_rightmost_descendant() isn't what I'm immediately after at this point. However, I also wouldn't argue against exposing it as another possible control order available to the BPF cgroup iterators.