[bpf-next,v5,4/8] bpf: Introduce cgroup iter

Commit Message

Yosry Ahmed July 22, 2022, 5:48 p.m. UTC

From: Hao Luo <[e-mail]>

Cgroup_iter is a type of bpf_iter. It walks over cgroups in three modes:

 - walking a cgroup's descendants in pre-order.
 - walking a cgroup's descendants in post-order.
 - walking a cgroup's ancestors.

When attaching cgroup_iter, one can set a cgroup to the iter_link
created from attaching. This cgroup is passed as a file descriptor and
serves as the starting point of the walk. If no cgroup is specified,
the starting point will be the root cgroup.

For walking descendants, one can specify the order: either pre-order or
post-order. For walking ancestors, the walk starts at the specified
cgroup and ends at the root.

One can also terminate the walk early by returning 1 from the iter
program.

Note that because walking cgroup hierarchy holds cgroup_mutex, the iter
program is called with cgroup_mutex held.

Currently only one session is supported, which means, depending on the
volume of data bpf program intends to send to user space, the number
of cgroups that can be walked is limited. For example, given the current
buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
cgroup, the total number of cgroups that can be walked is 512. This is
a limitation of cgroup_iter. If the output data is larger than the
buffer size, the second read() will signal EOPNOTSUPP. In order to work
around, the user may have to update their program to reduce the volume
of data sent to output. For example, skip some uninteresting cgroups.
In future, we may extend bpf_iter flags to allow customizing buffer
size.

Signed-off-by: Hao Luo <[e-mail]>
Signed-off-by: Yosry Ahmed <[e-mail]>
Acked-by: Yonghong Song <[e-mail]>
---
 include/linux/bpf.h                           |   8 +
 include/uapi/linux/bpf.h                      |  30 +++
 kernel/bpf/Makefile                           |   3 +
 kernel/bpf/cgroup_iter.c                      | 252 ++++++++++++++++++
 tools/include/uapi/linux/bpf.h                |  30 +++
 .../selftests/bpf/prog_tests/btf_dump.c       |   4 +-
 6 files changed, 325 insertions(+), 2 deletions(-)
 create mode 100644 kernel/bpf/cgroup_iter.c

Comments

Kumar Kartikeya Dwivedi July 22, 2022, 6:35 p.m. UTC | #1

On Fri, 22 Jul 2022 at 19:52, Yosry Ahmed <[e-mail]> wrote:
>
> From: Hao Luo <[e-mail]>
>
> Cgroup_iter is a type of bpf_iter. It walks over cgroups in three modes:
>
>  - walking a cgroup's descendants in pre-order.
>  - walking a cgroup's descendants in post-order.
>  - walking a cgroup's ancestors.
>
> When attaching cgroup_iter, one can set a cgroup to the iter_link
> created from attaching. This cgroup is passed as a file descriptor and
> serves as the starting point of the walk. If no cgroup is specified,
> the starting point will be the root cgroup.
>
> For walking descendants, one can specify the order: either pre-order or
> post-order. For walking ancestors, the walk starts at the specified
> cgroup and ends at the root.
>
> One can also terminate the walk early by returning 1 from the iter
> program.
>
> Note that because walking cgroup hierarchy holds cgroup_mutex, the iter
> program is called with cgroup_mutex held.
>
> Currently only one session is supported, which means, depending on the
> volume of data bpf program intends to send to user space, the number
> of cgroups that can be walked is limited. For example, given the current
> buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
> cgroup, the total number of cgroups that can be walked is 512. This is
> a limitation of cgroup_iter. If the output data is larger than the
> buffer size, the second read() will signal EOPNOTSUPP. In order to work
> around, the user may have to update their program to reduce the volume
> of data sent to output. For example, skip some uninteresting cgroups.
> In future, we may extend bpf_iter flags to allow customizing buffer
> size.
>
> Signed-off-by: Hao Luo <[e-mail]>
> Signed-off-by: Yosry Ahmed <[e-mail]>
> Acked-by: Yonghong Song <[e-mail]>
> ---
>  include/linux/bpf.h                           |   8 +
>  include/uapi/linux/bpf.h                      |  30 +++
>  kernel/bpf/Makefile                           |   3 +
>  kernel/bpf/cgroup_iter.c                      | 252 ++++++++++++++++++
>  tools/include/uapi/linux/bpf.h                |  30 +++
>  .../selftests/bpf/prog_tests/btf_dump.c       |   4 +-
>  6 files changed, 325 insertions(+), 2 deletions(-)
>  create mode 100644 kernel/bpf/cgroup_iter.c
>
> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> index a97751d845c9..9061618fe929 100644
> --- a/include/linux/bpf.h
> +++ b/include/linux/bpf.h
> @@ -47,6 +47,7 @@ struct kobject;
>  struct mem_cgroup;
>  struct module;
>  struct bpf_func_state;
> +struct cgroup;
>
>  extern struct idr btf_idr;
>  extern spinlock_t btf_idr_lock;
> @@ -1717,7 +1718,14 @@ int bpf_obj_get_user(const char __user *pathname, int flags);
>         int __init bpf_iter_ ## target(args) { return 0; }
>
>  struct bpf_iter_aux_info {
> +       /* for map_elem iter */
>         struct bpf_map *map;
> +
> +       /* for cgroup iter */
> +       struct {
> +               struct cgroup *start; /* starting cgroup */
> +               int order;
> +       } cgroup;
>  };
>
>  typedef int (*bpf_iter_attach_target_t)(struct bpf_prog *prog,
> diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
> index ffcbf79a556b..fe50c2489350 100644
> --- a/include/uapi/linux/bpf.h
> +++ b/include/uapi/linux/bpf.h
> @@ -87,10 +87,30 @@ struct bpf_cgroup_storage_key {
>         __u32   attach_type;            /* program attach type (enum bpf_attach_type) */
>  };
>
> +enum bpf_iter_cgroup_traversal_order {
> +       BPF_ITER_CGROUP_PRE = 0,        /* pre-order traversal */
> +       BPF_ITER_CGROUP_POST,           /* post-order traversal */
> +       BPF_ITER_CGROUP_PARENT_UP,      /* traversal of ancestors up to the root */
> +};
> +
>  union bpf_iter_link_info {
>         struct {
>                 __u32   map_fd;
>         } map;
> +
> +       /* cgroup_iter walks either the live descendants of a cgroup subtree, or the
> +        * ancestors of a given cgroup.
> +        */
> +       struct {
> +               /* Cgroup file descriptor. This is root of the subtree if walking
> +                * descendants; it's the starting cgroup if walking the ancestors.
> +                * If it is left 0, the traversal starts from the default cgroup v2
> +                * root. For walking v1 hierarchy, one should always explicitly
> +                * specify the cgroup_fd.
> +                */
> +               __u32   cgroup_fd;
> +               __u32   traversal_order;
> +       } cgroup;
>  };
>
>  /* BPF syscall commands, see bpf(2) man-page for more details. */
> @@ -6136,6 +6156,16 @@ struct bpf_link_info {
>                                         __u32 map_id;
>                                 } map;
>                         };
> +                       union {
> +                               struct {
> +                                       __u64 cgroup_id;
> +                                       __u32 traversal_order;
> +                               } cgroup;
> +                       };
> +                       /* For new iters, if the first field is larger than __u32,
> +                        * the struct should be added in the second union. Otherwise,
> +                        * it will create holes before map_id, breaking uapi.
> +                        */
>                 } iter;
>                 struct  {
>                         __u32 netns_ino;
> diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
> index 057ba8e01e70..00e05b69a4df 100644
> --- a/kernel/bpf/Makefile
> +++ b/kernel/bpf/Makefile
> @@ -24,6 +24,9 @@ endif
>  ifeq ($(CONFIG_PERF_EVENTS),y)
>  obj-$(CONFIG_BPF_SYSCALL) += stackmap.o
>  endif
> +ifeq ($(CONFIG_CGROUPS),y)
> +obj-$(CONFIG_BPF_SYSCALL) += cgroup_iter.o
> +endif
>  obj-$(CONFIG_CGROUP_BPF) += cgroup.o
>  ifeq ($(CONFIG_INET),y)
>  obj-$(CONFIG_BPF_SYSCALL) += reuseport_array.o
> diff --git a/kernel/bpf/cgroup_iter.c b/kernel/bpf/cgroup_iter.c
> new file mode 100644
> index 000000000000..1027faed0b8b
> --- /dev/null
> +++ b/kernel/bpf/cgroup_iter.c
> @@ -0,0 +1,252 @@
> +// SPDX-License-Identifier: GPL-2.0-only
> +/* Copyright (c) 2022 Google */
> +#include <linux/bpf.h>
> +#include <linux/btf_ids.h>
> +#include <linux/cgroup.h>
> +#include <linux/kernel.h>
> +#include <linux/seq_file.h>
> +
> +#include "../cgroup/cgroup-internal.h"  /* cgroup_mutex and cgroup_is_dead */
> +
> +/* cgroup_iter provides three 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.
> + *  2. Walk the ancestors of a 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
> + * the root.
> + *
> + * The iter program can terminate the walk early by returning 1. Walk
> + * continues if prog returns 0.
> + *
> + * The prog can check (seq->num == 0) to determine whether this is
> + * the first element. The prog may also be passed a NULL cgroup,
> + * which means the walk has completed and the prog has a chance to
> + * do post-processing, such as outputing an epilogue.
> + *
> + * Note: the iter_prog is called with cgroup_mutex held.
> + *
> + * Currently only one session is supported, which means, depending on the
> + * volume of data bpf program intends to send to user space, the number
> + * of cgroups that can be walked is limited. For example, given the current
> + * buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
> + * cgroup, the total number of cgroups that can be walked is 512. This is
> + * a limitation of cgroup_iter. If the output data is larger than the
> + * buffer size, the second read() will signal EOPNOTSUPP. In order to work
> + * around, the user may have to update their program to reduce the volume
> + * of data sent to output. For example, skip some uninteresting cgroups.
> + */
> +
> +struct bpf_iter__cgroup {
> +       __bpf_md_ptr(struct bpf_iter_meta *, meta);
> +       __bpf_md_ptr(struct cgroup *, cgroup);
> +};
> +
> +struct cgroup_iter_priv {
> +       struct cgroup_subsys_state *start_css;
> +       bool terminate;
> +       int order;
> +};
> +
> +static void *cgroup_iter_seq_start(struct seq_file *seq, loff_t *pos)
> +{
> +       struct cgroup_iter_priv *p = seq->private;
> +
> +       mutex_lock(&cgroup_mutex);
> +
> +       /* cgroup_iter doesn't support read across multiple sessions. */
> +       if (*pos > 0)
> +               return ERR_PTR(-EOPNOTSUPP);
> +
> +       ++*pos;
> +       p->terminate = false;
> +       if (p->order == BPF_ITER_CGROUP_PRE)
> +               return css_next_descendant_pre(NULL, p->start_css);
> +       else if (p->order == BPF_ITER_CGROUP_POST)
> +               return css_next_descendant_post(NULL, p->start_css);
> +       else /* BPF_ITER_CGROUP_PARENT_UP */
> +               return p->start_css;
> +}
> +
> +static int __cgroup_iter_seq_show(struct seq_file *seq,
> +                                 struct cgroup_subsys_state *css, int in_stop);
> +
> +static void cgroup_iter_seq_stop(struct seq_file *seq, void *v)
> +{
> +       /* pass NULL to the prog for post-processing */
> +       if (!v)
> +               __cgroup_iter_seq_show(seq, NULL, true);
> +       mutex_unlock(&cgroup_mutex);

I'm just curious, but would it be a good optimization (maybe in a
follow up) to move this mutex_unlock before the check on v? That
allows you to store/buffer some info you want to print as a compressed
struct in a map, then write the full text to the seq_file outside the
cgroup_mutex lock in the post-processing invocation.

It probably also allows you to walk the whole hierarchy, if one
doesn't want to run into seq_file buffer limit (or it can decide what
to print within the limit in the post processing invocation), or it
can use some out of band way (ringbuf, hashmap, etc.) to send the data
to userspace. But all of this can happen without holding cgroup_mutex
lock.

Hao Luo July 22, 2022, 8:33 p.m. UTC | #2

On Fri, Jul 22, 2022 at 11:36 AM Kumar Kartikeya Dwivedi
<[e-mail]> wrote:
>
> On Fri, 22 Jul 2022 at 19:52, Yosry Ahmed <[e-mail]> wrote:
> >
> > From: Hao Luo <[e-mail]>
> >
> > Cgroup_iter is a type of bpf_iter. It walks over cgroups in three modes:
> >
> >  - walking a cgroup's descendants in pre-order.
> >  - walking a cgroup's descendants in post-order.
> >  - walking a cgroup's ancestors.
> >
> > When attaching cgroup_iter, one can set a cgroup to the iter_link
> > created from attaching. This cgroup is passed as a file descriptor and
> > serves as the starting point of the walk. If no cgroup is specified,
> > the starting point will be the root cgroup.
> >
> > For walking descendants, one can specify the order: either pre-order or
> > post-order. For walking ancestors, the walk starts at the specified
> > cgroup and ends at the root.
> >
> > One can also terminate the walk early by returning 1 from the iter
> > program.
> >
> > Note that because walking cgroup hierarchy holds cgroup_mutex, the iter
> > program is called with cgroup_mutex held.
> >
> > Currently only one session is supported, which means, depending on the
> > volume of data bpf program intends to send to user space, the number
> > of cgroups that can be walked is limited. For example, given the current
> > buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
> > cgroup, the total number of cgroups that can be walked is 512. This is
> > a limitation of cgroup_iter. If the output data is larger than the
> > buffer size, the second read() will signal EOPNOTSUPP. In order to work
> > around, the user may have to update their program to reduce the volume
> > of data sent to output. For example, skip some uninteresting cgroups.
> > In future, we may extend bpf_iter flags to allow customizing buffer
> > size.
> >
> > Signed-off-by: Hao Luo <[e-mail]>
> > Signed-off-by: Yosry Ahmed <[e-mail]>
> > Acked-by: Yonghong Song <[e-mail]>
> > ---
> >  include/linux/bpf.h                           |   8 +
> >  include/uapi/linux/bpf.h                      |  30 +++
> >  kernel/bpf/Makefile                           |   3 +
> >  kernel/bpf/cgroup_iter.c                      | 252 ++++++++++++++++++
> >  tools/include/uapi/linux/bpf.h                |  30 +++
> >  .../selftests/bpf/prog_tests/btf_dump.c       |   4 +-
> >  6 files changed, 325 insertions(+), 2 deletions(-)
> >  create mode 100644 kernel/bpf/cgroup_iter.c
> >
> > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > index a97751d845c9..9061618fe929 100644
> > --- a/include/linux/bpf.h
> > +++ b/include/linux/bpf.h
> > @@ -47,6 +47,7 @@ struct kobject;
> >  struct mem_cgroup;
> >  struct module;
> >  struct bpf_func_state;
> > +struct cgroup;
> >
> >  extern struct idr btf_idr;
> >  extern spinlock_t btf_idr_lock;
> > @@ -1717,7 +1718,14 @@ int bpf_obj_get_user(const char __user *pathname, int flags);
> >         int __init bpf_iter_ ## target(args) { return 0; }
> >
> >  struct bpf_iter_aux_info {
> > +       /* for map_elem iter */
> >         struct bpf_map *map;
> > +
> > +       /* for cgroup iter */
> > +       struct {
> > +               struct cgroup *start; /* starting cgroup */
> > +               int order;
> > +       } cgroup;
> >  };
> >
> >  typedef int (*bpf_iter_attach_target_t)(struct bpf_prog *prog,
> > diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
> > index ffcbf79a556b..fe50c2489350 100644
> > --- a/include/uapi/linux/bpf.h
> > +++ b/include/uapi/linux/bpf.h
> > @@ -87,10 +87,30 @@ struct bpf_cgroup_storage_key {
> >         __u32   attach_type;            /* program attach type (enum bpf_attach_type) */
> >  };
> >
> > +enum bpf_iter_cgroup_traversal_order {
> > +       BPF_ITER_CGROUP_PRE = 0,        /* pre-order traversal */
> > +       BPF_ITER_CGROUP_POST,           /* post-order traversal */
> > +       BPF_ITER_CGROUP_PARENT_UP,      /* traversal of ancestors up to the root */
> > +};
> > +
> >  union bpf_iter_link_info {
> >         struct {
> >                 __u32   map_fd;
> >         } map;
> > +
> > +       /* cgroup_iter walks either the live descendants of a cgroup subtree, or the
> > +        * ancestors of a given cgroup.
> > +        */
> > +       struct {
> > +               /* Cgroup file descriptor. This is root of the subtree if walking
> > +                * descendants; it's the starting cgroup if walking the ancestors.
> > +                * If it is left 0, the traversal starts from the default cgroup v2
> > +                * root. For walking v1 hierarchy, one should always explicitly
> > +                * specify the cgroup_fd.
> > +                */
> > +               __u32   cgroup_fd;
> > +               __u32   traversal_order;
> > +       } cgroup;
> >  };
> >
> >  /* BPF syscall commands, see bpf(2) man-page for more details. */
> > @@ -6136,6 +6156,16 @@ struct bpf_link_info {
> >                                         __u32 map_id;
> >                                 } map;
> >                         };
> > +                       union {
> > +                               struct {
> > +                                       __u64 cgroup_id;
> > +                                       __u32 traversal_order;
> > +                               } cgroup;
> > +                       };
> > +                       /* For new iters, if the first field is larger than __u32,
> > +                        * the struct should be added in the second union. Otherwise,
> > +                        * it will create holes before map_id, breaking uapi.
> > +                        */
> >                 } iter;
> >                 struct  {
> >                         __u32 netns_ino;
> > diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
> > index 057ba8e01e70..00e05b69a4df 100644
> > --- a/kernel/bpf/Makefile
> > +++ b/kernel/bpf/Makefile
> > @@ -24,6 +24,9 @@ endif
> >  ifeq ($(CONFIG_PERF_EVENTS),y)
> >  obj-$(CONFIG_BPF_SYSCALL) += stackmap.o
> >  endif
> > +ifeq ($(CONFIG_CGROUPS),y)
> > +obj-$(CONFIG_BPF_SYSCALL) += cgroup_iter.o
> > +endif
> >  obj-$(CONFIG_CGROUP_BPF) += cgroup.o
> >  ifeq ($(CONFIG_INET),y)
> >  obj-$(CONFIG_BPF_SYSCALL) += reuseport_array.o
> > diff --git a/kernel/bpf/cgroup_iter.c b/kernel/bpf/cgroup_iter.c
> > new file mode 100644
> > index 000000000000..1027faed0b8b
> > --- /dev/null
> > +++ b/kernel/bpf/cgroup_iter.c
> > @@ -0,0 +1,252 @@
> > +// SPDX-License-Identifier: GPL-2.0-only
> > +/* Copyright (c) 2022 Google */
> > +#include <linux/bpf.h>
> > +#include <linux/btf_ids.h>
> > +#include <linux/cgroup.h>
> > +#include <linux/kernel.h>
> > +#include <linux/seq_file.h>
> > +
> > +#include "../cgroup/cgroup-internal.h"  /* cgroup_mutex and cgroup_is_dead */
> > +
> > +/* cgroup_iter provides three 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.
> > + *  2. Walk the ancestors of a 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
> > + * the root.
> > + *
> > + * The iter program can terminate the walk early by returning 1. Walk
> > + * continues if prog returns 0.
> > + *
> > + * The prog can check (seq->num == 0) to determine whether this is
> > + * the first element. The prog may also be passed a NULL cgroup,
> > + * which means the walk has completed and the prog has a chance to
> > + * do post-processing, such as outputing an epilogue.
> > + *
> > + * Note: the iter_prog is called with cgroup_mutex held.
> > + *
> > + * Currently only one session is supported, which means, depending on the
> > + * volume of data bpf program intends to send to user space, the number
> > + * of cgroups that can be walked is limited. For example, given the current
> > + * buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
> > + * cgroup, the total number of cgroups that can be walked is 512. This is
> > + * a limitation of cgroup_iter. If the output data is larger than the
> > + * buffer size, the second read() will signal EOPNOTSUPP. In order to work
> > + * around, the user may have to update their program to reduce the volume
> > + * of data sent to output. For example, skip some uninteresting cgroups.
> > + */
> > +
> > +struct bpf_iter__cgroup {
> > +       __bpf_md_ptr(struct bpf_iter_meta *, meta);
> > +       __bpf_md_ptr(struct cgroup *, cgroup);
> > +};
> > +
> > +struct cgroup_iter_priv {
> > +       struct cgroup_subsys_state *start_css;
> > +       bool terminate;
> > +       int order;
> > +};
> > +
> > +static void *cgroup_iter_seq_start(struct seq_file *seq, loff_t *pos)
> > +{
> > +       struct cgroup_iter_priv *p = seq->private;
> > +
> > +       mutex_lock(&cgroup_mutex);
> > +
> > +       /* cgroup_iter doesn't support read across multiple sessions. */
> > +       if (*pos > 0)
> > +               return ERR_PTR(-EOPNOTSUPP);
> > +
> > +       ++*pos;
> > +       p->terminate = false;
> > +       if (p->order == BPF_ITER_CGROUP_PRE)
> > +               return css_next_descendant_pre(NULL, p->start_css);
> > +       else if (p->order == BPF_ITER_CGROUP_POST)
> > +               return css_next_descendant_post(NULL, p->start_css);
> > +       else /* BPF_ITER_CGROUP_PARENT_UP */
> > +               return p->start_css;
> > +}
> > +
> > +static int __cgroup_iter_seq_show(struct seq_file *seq,
> > +                                 struct cgroup_subsys_state *css, int in_stop);
> > +
> > +static void cgroup_iter_seq_stop(struct seq_file *seq, void *v)
> > +{
> > +       /* pass NULL to the prog for post-processing */
> > +       if (!v)
> > +               __cgroup_iter_seq_show(seq, NULL, true);
> > +       mutex_unlock(&cgroup_mutex);
>
> I'm just curious, but would it be a good optimization (maybe in a
> follow up) to move this mutex_unlock before the check on v? That
> allows you to store/buffer some info you want to print as a compressed
> struct in a map, then write the full text to the seq_file outside the
> cgroup_mutex lock in the post-processing invocation.
>
> It probably also allows you to walk the whole hierarchy, if one
> doesn't want to run into seq_file buffer limit (or it can decide what
> to print within the limit in the post processing invocation), or it
> can use some out of band way (ringbuf, hashmap, etc.) to send the data
> to userspace. But all of this can happen without holding cgroup_mutex
> lock.

Thanks Kumar.

It sounds like an idea, but the key thing is not about moving
cgroup_mutex unlock before the check IMHO. The user can achieve
compression using the current infra. Compression could actually be
done in the bpf program. user can define and output binary content and
implement a userspace library to parse/decompress when reading out the
data.

Yonghong Song July 28, 2022, 5:49 a.m. UTC | #3

On 7/22/22 10:48 AM, Yosry Ahmed wrote:
> From: Hao Luo <[e-mail]>
> 
> Cgroup_iter is a type of bpf_iter. It walks over cgroups in three modes:
> 
>   - walking a cgroup's descendants in pre-order.
>   - walking a cgroup's descendants in post-order.
>   - walking a cgroup's ancestors.
> 
> When attaching cgroup_iter, one can set a cgroup to the iter_link
> created from attaching. This cgroup is passed as a file descriptor and
> serves as the starting point of the walk. If no cgroup is specified,
> the starting point will be the root cgroup.
> 
> For walking descendants, one can specify the order: either pre-order or
> post-order. For walking ancestors, the walk starts at the specified
> cgroup and ends at the root.
> 
> One can also terminate the walk early by returning 1 from the iter
> program.
> 
> Note that because walking cgroup hierarchy holds cgroup_mutex, the iter
> program is called with cgroup_mutex held.
> 
> Currently only one session is supported, which means, depending on the
> volume of data bpf program intends to send to user space, the number
> of cgroups that can be walked is limited. For example, given the current
> buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
> cgroup, the total number of cgroups that can be walked is 512. This is

PAGE_SIZE needs to be 4KB in order to conclude that the total number of
walked cgroups is 512.

> a limitation of cgroup_iter. If the output data is larger than the
> buffer size, the second read() will signal EOPNOTSUPP. In order to work
> around, the user may have to update their program to reduce the volume
> of data sent to output. For example, skip some uninteresting cgroups.
> In future, we may extend bpf_iter flags to allow customizing buffer
> size.
> 
> Signed-off-by: Hao Luo <[e-mail]>
> Signed-off-by: Yosry Ahmed <[e-mail]>
> Acked-by: Yonghong Song <[e-mail]>
> ---
>   include/linux/bpf.h                           |   8 +
>   include/uapi/linux/bpf.h                      |  30 +++
>   kernel/bpf/Makefile                           |   3 +
>   kernel/bpf/cgroup_iter.c                      | 252 ++++++++++++++++++
>   tools/include/uapi/linux/bpf.h                |  30 +++
>   .../selftests/bpf/prog_tests/btf_dump.c       |   4 +-
>   6 files changed, 325 insertions(+), 2 deletions(-)
>   create mode 100644 kernel/bpf/cgroup_iter.c

This patch cannot apply to bpf-next cleanly, so please rebase
and post again.

> 
> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> index a97751d845c9..9061618fe929 100644
> --- a/include/linux/bpf.h
> +++ b/include/linux/bpf.h
> @@ -47,6 +47,7 @@ struct kobject;
>   struct mem_cgroup;
>   struct module;
>   struct bpf_func_state;
> +struct cgroup;
>   
>   extern struct idr btf_idr;
>   extern spinlock_t btf_idr_lock;
> @@ -1717,7 +1718,14 @@ int bpf_obj_get_user(const char __user *pathname, int flags);
>   	int __init bpf_iter_ ## target(args) { return 0; }
>   
>   struct bpf_iter_aux_info {
> +	/* for map_elem iter */
>   	struct bpf_map *map;
> +
> +	/* for cgroup iter */
> +	struct {
> +		struct cgroup *start; /* starting cgroup */
> +		int order;
> +	} cgroup;
>   };
>   
>   typedef int (*bpf_iter_attach_target_t)(struct bpf_prog *prog,
> diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
> index ffcbf79a556b..fe50c2489350 100644
> --- a/include/uapi/linux/bpf.h
> +++ b/include/uapi/linux/bpf.h
> @@ -87,10 +87,30 @@ struct bpf_cgroup_storage_key {
>   	__u32	attach_type;		/* program attach type (enum bpf_attach_type) */
>   };
>   
> +enum bpf_iter_cgroup_traversal_order {
> +	BPF_ITER_CGROUP_PRE = 0,	/* pre-order traversal */
> +	BPF_ITER_CGROUP_POST,		/* post-order traversal */
> +	BPF_ITER_CGROUP_PARENT_UP,	/* traversal of ancestors up to the root */
> +};
> +
>   union bpf_iter_link_info {
>   	struct {
>   		__u32	map_fd;
>   	} map;
> +
> +	/* cgroup_iter walks either the live descendants of a cgroup subtree, or the
> +	 * ancestors of a given cgroup.
> +	 */
> +	struct {
> +		/* Cgroup file descriptor. This is root of the subtree if walking
> +		 * descendants; it's the starting cgroup if walking the ancestors.
> +		 * If it is left 0, the traversal starts from the default cgroup v2
> +		 * root. For walking v1 hierarchy, one should always explicitly
> +		 * specify the cgroup_fd.
> +		 */

I did see how the above cgroup v1/v2 scenarios are enforced.

> +		__u32	cgroup_fd;
> +		__u32	traversal_order;
> +	} cgroup;
>   };
>   
>   /* BPF syscall commands, see bpf(2) man-page for more details. */
> @@ -6136,6 +6156,16 @@ struct bpf_link_info {
>   					__u32 map_id;
>   				} map;
>   			};
> +			union {
> +				struct {
> +					__u64 cgroup_id;
> +					__u32 traversal_order;
> +				} cgroup;
> +			};
> +			/* For new iters, if the first field is larger than __u32,
> +			 * the struct should be added in the second union. Otherwise,
> +			 * it will create holes before map_id, breaking uapi.
> +			 */

Please put the comment above the union. Let us just say, if
the iter specific field is __u32, it can be put in the first or
second union. Otherwise, it is put in second union.

>   		} iter;
>   		struct  {
>   			__u32 netns_ino;
> diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
> index 057ba8e01e70..00e05b69a4df 100644
> --- a/kernel/bpf/Makefile
> +++ b/kernel/bpf/Makefile
> @@ -24,6 +24,9 @@ endif
>   ifeq ($(CONFIG_PERF_EVENTS),y)
>   obj-$(CONFIG_BPF_SYSCALL) += stackmap.o
>   endif
> +ifeq ($(CONFIG_CGROUPS),y)
> +obj-$(CONFIG_BPF_SYSCALL) += cgroup_iter.o
> +endif
>   obj-$(CONFIG_CGROUP_BPF) += cgroup.o
>   ifeq ($(CONFIG_INET),y)
>   obj-$(CONFIG_BPF_SYSCALL) += reuseport_array.o
> diff --git a/kernel/bpf/cgroup_iter.c b/kernel/bpf/cgroup_iter.c
> new file mode 100644
> index 000000000000..1027faed0b8b
> --- /dev/null
> +++ b/kernel/bpf/cgroup_iter.c
> @@ -0,0 +1,252 @@
> +// SPDX-License-Identifier: GPL-2.0-only
> +/* Copyright (c) 2022 Google */
> +#include <linux/bpf.h>
> +#include <linux/btf_ids.h>
> +#include <linux/cgroup.h>
> +#include <linux/kernel.h>
> +#include <linux/seq_file.h>
> +
> +#include "../cgroup/cgroup-internal.h"  /* cgroup_mutex and cgroup_is_dead */
> +
> +/* cgroup_iter provides three 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.
> + *  2. Walk the ancestors of a 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
> + * the root.
> + *
> + * The iter program can terminate the walk early by returning 1. Walk
> + * continues if prog returns 0.
> + *
> + * The prog can check (seq->num == 0) to determine whether this is
> + * the first element. The prog may also be passed a NULL cgroup,
> + * which means the walk has completed and the prog has a chance to
> + * do post-processing, such as outputing an epilogue.
> + *
> + * Note: the iter_prog is called with cgroup_mutex held.
> + *
> + * Currently only one session is supported, which means, depending on the
> + * volume of data bpf program intends to send to user space, the number
> + * of cgroups that can be walked is limited. For example, given the current
> + * buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
> + * cgroup, the total number of cgroups that can be walked is 512. This is

Again, let us specify PAGE_SIZE = 4KB here.

> + * a limitation of cgroup_iter. If the output data is larger than the
> + * buffer size, the second read() will signal EOPNOTSUPP. In order to work
> + * around, the user may have to update their program to reduce the volume
> + * of data sent to output. For example, skip some uninteresting cgroups.
> + */
> +
> +struct bpf_iter__cgroup {
> +	__bpf_md_ptr(struct bpf_iter_meta *, meta);
> +	__bpf_md_ptr(struct cgroup *, cgroup);
> +};
> +
> +struct cgroup_iter_priv {
> +	struct cgroup_subsys_state *start_css;
> +	bool terminate;
> +	int order;
> +};
> +
> +static void *cgroup_iter_seq_start(struct seq_file *seq, loff_t *pos)
> +{
> +	struct cgroup_iter_priv *p = seq->private;
> +
> +	mutex_lock(&cgroup_mutex);
> +
> +	/* cgroup_iter doesn't support read across multiple sessions. */
> +	if (*pos > 0)
> +		return ERR_PTR(-EOPNOTSUPP);

This is not quite right. Let us say, the number of cgroups is 1,
after bpf program run, pos = 1, and the control return to user
space. Now the second read() will return -EOPNOTSUPP which is not
right. -EOPNOTSUPP should be returned ONLY if the previous cgroup
iterations do not traverse all cgroups.
So you might need to record additional information in cgroup_iter_priv
to record such information.

> +
> +	++*pos;
> +	p->terminate = false;
> +	if (p->order == BPF_ITER_CGROUP_PRE)
> +		return css_next_descendant_pre(NULL, p->start_css);
> +	else if (p->order == BPF_ITER_CGROUP_POST)
> +		return css_next_descendant_post(NULL, p->start_css);
> +	else /* BPF_ITER_CGROUP_PARENT_UP */
> +		return p->start_css;
> +}
> +
> +static int __cgroup_iter_seq_show(struct seq_file *seq,
> +				  struct cgroup_subsys_state *css, int in_stop);
> +
> +static void cgroup_iter_seq_stop(struct seq_file *seq, void *v)
> +{
> +	/* pass NULL to the prog for post-processing */
> +	if (!v)
> +		__cgroup_iter_seq_show(seq, NULL, true);
> +	mutex_unlock(&cgroup_mutex);
> +}
> +
> +static void *cgroup_iter_seq_next(struct seq_file *seq, void *v, loff_t *pos)
> +{
> +	struct cgroup_subsys_state *curr = (struct cgroup_subsys_state *)v;
> +	struct cgroup_iter_priv *p = seq->private;
> +
> +	++*pos;
> +	if (p->terminate)
> +		return NULL;
> +
> +	if (p->order == BPF_ITER_CGROUP_PRE)
> +		return css_next_descendant_pre(curr, p->start_css);
> +	else if (p->order == BPF_ITER_CGROUP_POST)
> +		return css_next_descendant_post(curr, p->start_css);
> +	else
> +		return curr->parent;
> +}
> +
[...]

Yonghong Song July 28, 2022, 6:55 a.m. UTC | #4

On 7/22/22 1:33 PM, Hao Luo wrote:
> On Fri, Jul 22, 2022 at 11:36 AM Kumar Kartikeya Dwivedi
> <[e-mail]> wrote:
>>
>> On Fri, 22 Jul 2022 at 19:52, Yosry Ahmed <[e-mail]> wrote:
>>>
>>> From: Hao Luo <[e-mail]>
>>>
>>> Cgroup_iter is a type of bpf_iter. It walks over cgroups in three modes:
>>>
>>>   - walking a cgroup's descendants in pre-order.
>>>   - walking a cgroup's descendants in post-order.
>>>   - walking a cgroup's ancestors.
>>>
>>> When attaching cgroup_iter, one can set a cgroup to the iter_link
>>> created from attaching. This cgroup is passed as a file descriptor and
>>> serves as the starting point of the walk. If no cgroup is specified,
>>> the starting point will be the root cgroup.
>>>
>>> For walking descendants, one can specify the order: either pre-order or
>>> post-order. For walking ancestors, the walk starts at the specified
>>> cgroup and ends at the root.
>>>
>>> One can also terminate the walk early by returning 1 from the iter
>>> program.
>>>
>>> Note that because walking cgroup hierarchy holds cgroup_mutex, the iter
>>> program is called with cgroup_mutex held.
>>>
>>> Currently only one session is supported, which means, depending on the
>>> volume of data bpf program intends to send to user space, the number
>>> of cgroups that can be walked is limited. For example, given the current
>>> buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
>>> cgroup, the total number of cgroups that can be walked is 512. This is
>>> a limitation of cgroup_iter. If the output data is larger than the
>>> buffer size, the second read() will signal EOPNOTSUPP. In order to work
>>> around, the user may have to update their program to reduce the volume
>>> of data sent to output. For example, skip some uninteresting cgroups.
>>> In future, we may extend bpf_iter flags to allow customizing buffer
>>> size.
>>>
>>> Signed-off-by: Hao Luo <[e-mail]>
>>> Signed-off-by: Yosry Ahmed <[e-mail]>
>>> Acked-by: Yonghong Song <[e-mail]>
>>> ---
>>>   include/linux/bpf.h                           |   8 +
>>>   include/uapi/linux/bpf.h                      |  30 +++
>>>   kernel/bpf/Makefile                           |   3 +
>>>   kernel/bpf/cgroup_iter.c                      | 252 ++++++++++++++++++
>>>   tools/include/uapi/linux/bpf.h                |  30 +++
>>>   .../selftests/bpf/prog_tests/btf_dump.c       |   4 +-
>>>   6 files changed, 325 insertions(+), 2 deletions(-)
>>>   create mode 100644 kernel/bpf/cgroup_iter.c
>>>
>>> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
>>> index a97751d845c9..9061618fe929 100644
>>> --- a/include/linux/bpf.h
>>> +++ b/include/linux/bpf.h
>>> @@ -47,6 +47,7 @@ struct kobject;
>>>   struct mem_cgroup;
>>>   struct module;
>>>   struct bpf_func_state;
>>> +struct cgroup;
>>>
>>>   extern struct idr btf_idr;
>>>   extern spinlock_t btf_idr_lock;
>>> @@ -1717,7 +1718,14 @@ int bpf_obj_get_user(const char __user *pathname, int flags);
>>>          int __init bpf_iter_ ## target(args) { return 0; }
>>>
>>>   struct bpf_iter_aux_info {
>>> +       /* for map_elem iter */
>>>          struct bpf_map *map;
>>> +
>>> +       /* for cgroup iter */
>>> +       struct {
>>> +               struct cgroup *start; /* starting cgroup */
>>> +               int order;
>>> +       } cgroup;
>>>   };
>>>
>>>   typedef int (*bpf_iter_attach_target_t)(struct bpf_prog *prog,
>>> diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
>>> index ffcbf79a556b..fe50c2489350 100644
>>> --- a/include/uapi/linux/bpf.h
>>> +++ b/include/uapi/linux/bpf.h
>>> @@ -87,10 +87,30 @@ struct bpf_cgroup_storage_key {
>>>          __u32   attach_type;            /* program attach type (enum bpf_attach_type) */
>>>   };
>>>
>>> +enum bpf_iter_cgroup_traversal_order {
>>> +       BPF_ITER_CGROUP_PRE = 0,        /* pre-order traversal */
>>> +       BPF_ITER_CGROUP_POST,           /* post-order traversal */
>>> +       BPF_ITER_CGROUP_PARENT_UP,      /* traversal of ancestors up to the root */
>>> +};
>>> +
>>>   union bpf_iter_link_info {
>>>          struct {
>>>                  __u32   map_fd;
>>>          } map;
>>> +
>>> +       /* cgroup_iter walks either the live descendants of a cgroup subtree, or the
>>> +        * ancestors of a given cgroup.
>>> +        */
>>> +       struct {
>>> +               /* Cgroup file descriptor. This is root of the subtree if walking
>>> +                * descendants; it's the starting cgroup if walking the ancestors.
>>> +                * If it is left 0, the traversal starts from the default cgroup v2
>>> +                * root. For walking v1 hierarchy, one should always explicitly
>>> +                * specify the cgroup_fd.
>>> +                */
>>> +               __u32   cgroup_fd;
>>> +               __u32   traversal_order;
>>> +       } cgroup;
>>>   };
>>>
>>>   /* BPF syscall commands, see bpf(2) man-page for more details. */
>>> @@ -6136,6 +6156,16 @@ struct bpf_link_info {
>>>                                          __u32 map_id;
>>>                                  } map;
>>>                          };
>>> +                       union {
>>> +                               struct {
>>> +                                       __u64 cgroup_id;
>>> +                                       __u32 traversal_order;
>>> +                               } cgroup;
>>> +                       };
>>> +                       /* For new iters, if the first field is larger than __u32,
>>> +                        * the struct should be added in the second union. Otherwise,
>>> +                        * it will create holes before map_id, breaking uapi.
>>> +                        */
>>>                  } iter;
>>>                  struct  {
>>>                          __u32 netns_ino;
>>> diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
>>> index 057ba8e01e70..00e05b69a4df 100644
>>> --- a/kernel/bpf/Makefile
>>> +++ b/kernel/bpf/Makefile
>>> @@ -24,6 +24,9 @@ endif
>>>   ifeq ($(CONFIG_PERF_EVENTS),y)
>>>   obj-$(CONFIG_BPF_SYSCALL) += stackmap.o
>>>   endif
>>> +ifeq ($(CONFIG_CGROUPS),y)
>>> +obj-$(CONFIG_BPF_SYSCALL) += cgroup_iter.o
>>> +endif
>>>   obj-$(CONFIG_CGROUP_BPF) += cgroup.o
>>>   ifeq ($(CONFIG_INET),y)
>>>   obj-$(CONFIG_BPF_SYSCALL) += reuseport_array.o
>>> diff --git a/kernel/bpf/cgroup_iter.c b/kernel/bpf/cgroup_iter.c
>>> new file mode 100644
>>> index 000000000000..1027faed0b8b
>>> --- /dev/null
>>> +++ b/kernel/bpf/cgroup_iter.c
>>> @@ -0,0 +1,252 @@
>>> +// SPDX-License-Identifier: GPL-2.0-only
>>> +/* Copyright (c) 2022 Google */
>>> +#include <linux/bpf.h>
>>> +#include <linux/btf_ids.h>
>>> +#include <linux/cgroup.h>
>>> +#include <linux/kernel.h>
>>> +#include <linux/seq_file.h>
>>> +
>>> +#include "../cgroup/cgroup-internal.h"  /* cgroup_mutex and cgroup_is_dead */
>>> +
>>> +/* cgroup_iter provides three 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.
>>> + *  2. Walk the ancestors of a 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
>>> + * the root.
>>> + *
>>> + * The iter program can terminate the walk early by returning 1. Walk
>>> + * continues if prog returns 0.
>>> + *
>>> + * The prog can check (seq->num == 0) to determine whether this is
>>> + * the first element. The prog may also be passed a NULL cgroup,
>>> + * which means the walk has completed and the prog has a chance to
>>> + * do post-processing, such as outputing an epilogue.
>>> + *
>>> + * Note: the iter_prog is called with cgroup_mutex held.
>>> + *
>>> + * Currently only one session is supported, which means, depending on the
>>> + * volume of data bpf program intends to send to user space, the number
>>> + * of cgroups that can be walked is limited. For example, given the current
>>> + * buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
>>> + * cgroup, the total number of cgroups that can be walked is 512. This is
>>> + * a limitation of cgroup_iter. If the output data is larger than the
>>> + * buffer size, the second read() will signal EOPNOTSUPP. In order to work
>>> + * around, the user may have to update their program to reduce the volume
>>> + * of data sent to output. For example, skip some uninteresting cgroups.
>>> + */
>>> +
>>> +struct bpf_iter__cgroup {
>>> +       __bpf_md_ptr(struct bpf_iter_meta *, meta);
>>> +       __bpf_md_ptr(struct cgroup *, cgroup);
>>> +};
>>> +
>>> +struct cgroup_iter_priv {
>>> +       struct cgroup_subsys_state *start_css;
>>> +       bool terminate;
>>> +       int order;
>>> +};
>>> +
>>> +static void *cgroup_iter_seq_start(struct seq_file *seq, loff_t *pos)
>>> +{
>>> +       struct cgroup_iter_priv *p = seq->private;
>>> +
>>> +       mutex_lock(&cgroup_mutex);
>>> +
>>> +       /* cgroup_iter doesn't support read across multiple sessions. */
>>> +       if (*pos > 0)
>>> +               return ERR_PTR(-EOPNOTSUPP);
>>> +
>>> +       ++*pos;
>>> +       p->terminate = false;
>>> +       if (p->order == BPF_ITER_CGROUP_PRE)
>>> +               return css_next_descendant_pre(NULL, p->start_css);
>>> +       else if (p->order == BPF_ITER_CGROUP_POST)
>>> +               return css_next_descendant_post(NULL, p->start_css);
>>> +       else /* BPF_ITER_CGROUP_PARENT_UP */
>>> +               return p->start_css;
>>> +}
>>> +
>>> +static int __cgroup_iter_seq_show(struct seq_file *seq,
>>> +                                 struct cgroup_subsys_state *css, int in_stop);
>>> +
>>> +static void cgroup_iter_seq_stop(struct seq_file *seq, void *v)
>>> +{
>>> +       /* pass NULL to the prog for post-processing */
>>> +       if (!v)
>>> +               __cgroup_iter_seq_show(seq, NULL, true);
>>> +       mutex_unlock(&cgroup_mutex);
>>
>> I'm just curious, but would it be a good optimization (maybe in a
>> follow up) to move this mutex_unlock before the check on v? That
>> allows you to store/buffer some info you want to print as a compressed
>> struct in a map, then write the full text to the seq_file outside the
>> cgroup_mutex lock in the post-processing invocation.
>>
>> It probably also allows you to walk the whole hierarchy, if one
>> doesn't want to run into seq_file buffer limit (or it can decide what
>> to print within the limit in the post processing invocation), or it
>> can use some out of band way (ringbuf, hashmap, etc.) to send the data
>> to userspace. But all of this can happen without holding cgroup_mutex
>> lock.
> 
> Thanks Kumar.
> 
> It sounds like an idea, but the key thing is not about moving
> cgroup_mutex unlock before the check IMHO. The user can achieve
> compression using the current infra. Compression could actually be
> done in the bpf program. user can define and output binary content and
> implement a userspace library to parse/decompress when reading out the
> data.

Right mutex_unlock() can be moved to the beginning of the
function since the cgroup is not used in
   __cgroup_iter_seq_show(seq, NULL, true)

Tejun Heo July 28, 2022, 4:51 p.m. UTC | #5

Hello,

On Fri, Jul 22, 2022 at 05:48:25PM +0000, Yosry Ahmed wrote:
> +
> +	/* cgroup_iter walks either the live descendants of a cgroup subtree, or the
> +	 * ancestors of a given cgroup.
> +	 */
> +	struct {
> +		/* Cgroup file descriptor. This is root of the subtree if walking
> +		 * descendants; it's the starting cgroup if walking the ancestors.
> +		 * If it is left 0, the traversal starts from the default cgroup v2
> +		 * root. For walking v1 hierarchy, one should always explicitly
> +		 * specify the cgroup_fd.
> +		 */
> +		__u32	cgroup_fd;

So, we're identifying the starting point with an fd.

> +		__u32	traversal_order;
> +	} cgroup;
>  };
>  
>  /* BPF syscall commands, see bpf(2) man-page for more details. */
> @@ -6136,6 +6156,16 @@ struct bpf_link_info {
>  					__u32 map_id;
>  				} map;
>  			};
> +			union {
> +				struct {
> +					__u64 cgroup_id;
> +					__u32 traversal_order;
> +				} cgroup;

but iterating the IDs. IDs are the better choice for cgroup2 as there's
nothing specific to the calling program or the fds it has, but I guess this
is because you want to use it for cgroup1, right? Oh well, that's okay I
guess.

Acked-by: Tejun Heo <[e-mail]>

Thanks.

Hao Luo July 28, 2022, 5:20 p.m. UTC | #6

Hi Tejun,

On Thu, Jul 28, 2022 at 9:51 AM Tejun Heo <[e-mail]> wrote:
>
> Hello,
>
> On Fri, Jul 22, 2022 at 05:48:25PM +0000, Yosry Ahmed wrote:
> > +
> > +     /* cgroup_iter walks either the live descendants of a cgroup subtree, or the
> > +      * ancestors of a given cgroup.
> > +      */
> > +     struct {
> > +             /* Cgroup file descriptor. This is root of the subtree if walking
> > +              * descendants; it's the starting cgroup if walking the ancestors.
> > +              * If it is left 0, the traversal starts from the default cgroup v2
> > +              * root. For walking v1 hierarchy, one should always explicitly
> > +              * specify the cgroup_fd.
> > +              */
> > +             __u32   cgroup_fd;
>
> So, we're identifying the starting point with an fd.
>
> > +             __u32   traversal_order;
> > +     } cgroup;
> >  };
> >
> >  /* BPF syscall commands, see bpf(2) man-page for more details. */
> > @@ -6136,6 +6156,16 @@ struct bpf_link_info {
> >                                       __u32 map_id;
> >                               } map;
> >                       };
> > +                     union {
> > +                             struct {
> > +                                     __u64 cgroup_id;
> > +                                     __u32 traversal_order;
> > +                             } cgroup;
>
> but iterating the IDs. IDs are the better choice for cgroup2 as there's
> nothing specific to the calling program or the fds it has, but I guess this
> is because you want to use it for cgroup1, right? Oh well, that's okay I
> guess.
>

Yes, we are identifying the starting point with FD. The cgroup_id here
is the information reported from kernel to userspace for identifying
the cgroup.

We use FD because it is a convention in BPF. Compatibility of cgroup1
is a good feature of this convention. My thoughts: It seems that ID
may be better, for two reasons. First, because ID is stateless, the
userspace doesn't have to remember closing the FD. Second, using
different identifications in two directions (userspace specifies
cgroup using FD, while kernel reports cgroup using ID) introduces a
little complexity when connecting them together.

Hao

> Acked-by: Tejun Heo <[e-mail]>
>
> Thanks.
>
> --
> tejun

Hao Luo July 28, 2022, 5:25 p.m. UTC | #7

On Wed, Jul 27, 2022 at 10:49 PM Yonghong Song <[e-mail]> wrote:
>
>
>
> On 7/22/22 10:48 AM, Yosry Ahmed wrote:
> > From: Hao Luo <[e-mail]>
> >
> > Cgroup_iter is a type of bpf_iter. It walks over cgroups in three modes:
> >
> >   - walking a cgroup's descendants in pre-order.
> >   - walking a cgroup's descendants in post-order.
> >   - walking a cgroup's ancestors.
> >
> > When attaching cgroup_iter, one can set a cgroup to the iter_link
> > created from attaching. This cgroup is passed as a file descriptor and
> > serves as the starting point of the walk. If no cgroup is specified,
> > the starting point will be the root cgroup.
> >
> > For walking descendants, one can specify the order: either pre-order or
> > post-order. For walking ancestors, the walk starts at the specified
> > cgroup and ends at the root.
> >
> > One can also terminate the walk early by returning 1 from the iter
> > program.
> >
> > Note that because walking cgroup hierarchy holds cgroup_mutex, the iter
> > program is called with cgroup_mutex held.
> >
> > Currently only one session is supported, which means, depending on the
> > volume of data bpf program intends to send to user space, the number
> > of cgroups that can be walked is limited. For example, given the current
> > buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
> > cgroup, the total number of cgroups that can be walked is 512. This is
>
> PAGE_SIZE needs to be 4KB in order to conclude that the total number of
> walked cgroups is 512.
>

Sure. Will change that.

> > a limitation of cgroup_iter. If the output data is larger than the
> > buffer size, the second read() will signal EOPNOTSUPP. In order to work
> > around, the user may have to update their program to reduce the volume
> > of data sent to output. For example, skip some uninteresting cgroups.
> > In future, we may extend bpf_iter flags to allow customizing buffer
> > size.
> >
> > Signed-off-by: Hao Luo <[e-mail]>
> > Signed-off-by: Yosry Ahmed <[e-mail]>
> > Acked-by: Yonghong Song <[e-mail]>
> > ---
> >   include/linux/bpf.h                           |   8 +
> >   include/uapi/linux/bpf.h                      |  30 +++
> >   kernel/bpf/Makefile                           |   3 +
> >   kernel/bpf/cgroup_iter.c                      | 252 ++++++++++++++++++
> >   tools/include/uapi/linux/bpf.h                |  30 +++
> >   .../selftests/bpf/prog_tests/btf_dump.c       |   4 +-
> >   6 files changed, 325 insertions(+), 2 deletions(-)
> >   create mode 100644 kernel/bpf/cgroup_iter.c
>
> This patch cannot apply to bpf-next cleanly, so please rebase
> and post again.
>

Sorry about that. Will do.

> >
> > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > index a97751d845c9..9061618fe929 100644
> > --- a/include/linux/bpf.h
> > +++ b/include/linux/bpf.h
> > @@ -47,6 +47,7 @@ struct kobject;
> >   struct mem_cgroup;
> >   struct module;
> >   struct bpf_func_state;
> > +struct cgroup;
> >
> >   extern struct idr btf_idr;
> >   extern spinlock_t btf_idr_lock;
> > @@ -1717,7 +1718,14 @@ int bpf_obj_get_user(const char __user *pathname, int flags);
> >       int __init bpf_iter_ ## target(args) { return 0; }
> >
> >   struct bpf_iter_aux_info {
> > +     /* for map_elem iter */
> >       struct bpf_map *map;
> > +
> > +     /* for cgroup iter */
> > +     struct {
> > +             struct cgroup *start; /* starting cgroup */
> > +             int order;
> > +     } cgroup;
> >   };
> >
> >   typedef int (*bpf_iter_attach_target_t)(struct bpf_prog *prog,
> > diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
> > index ffcbf79a556b..fe50c2489350 100644
> > --- a/include/uapi/linux/bpf.h
> > +++ b/include/uapi/linux/bpf.h
> > @@ -87,10 +87,30 @@ struct bpf_cgroup_storage_key {
> >       __u32   attach_type;            /* program attach type (enum bpf_attach_type) */
> >   };
> >
> > +enum bpf_iter_cgroup_traversal_order {
> > +     BPF_ITER_CGROUP_PRE = 0,        /* pre-order traversal */
> > +     BPF_ITER_CGROUP_POST,           /* post-order traversal */
> > +     BPF_ITER_CGROUP_PARENT_UP,      /* traversal of ancestors up to the root */
> > +};
> > +
> >   union bpf_iter_link_info {
> >       struct {
> >               __u32   map_fd;
> >       } map;
> > +
> > +     /* cgroup_iter walks either the live descendants of a cgroup subtree, or the
> > +      * ancestors of a given cgroup.
> > +      */
> > +     struct {
> > +             /* Cgroup file descriptor. This is root of the subtree if walking
> > +              * descendants; it's the starting cgroup if walking the ancestors.
> > +              * If it is left 0, the traversal starts from the default cgroup v2
> > +              * root. For walking v1 hierarchy, one should always explicitly
> > +              * specify the cgroup_fd.
> > +              */
>
> I did see how the above cgroup v1/v2 scenarios are enforced.
>

Do you mean _not_ see? Yosry and I experimented a bit. We found even
on systems where v2 is not enabled, cgroup v2 root always exists and
can be attached to, and can be iterated on (only trivially). We didn't
find a way to tell v1 and v2 apart and deemed a comment to instruct v1
users is fine?

> > +             __u32   cgroup_fd;
> > +             __u32   traversal_order;
> > +     } cgroup;
> >   };
> >
> >   /* BPF syscall commands, see bpf(2) man-page for more details. */
> > @@ -6136,6 +6156,16 @@ struct bpf_link_info {
> >                                       __u32 map_id;
> >                               } map;
> >                       };
> > +                     union {
> > +                             struct {
> > +                                     __u64 cgroup_id;
> > +                                     __u32 traversal_order;
> > +                             } cgroup;
> > +                     };
> > +                     /* For new iters, if the first field is larger than __u32,
> > +                      * the struct should be added in the second union. Otherwise,
> > +                      * it will create holes before map_id, breaking uapi.
> > +                      */
>
> Please put the comment above the union. Let us just say, if
> the iter specific field is __u32, it can be put in the first or
> second union. Otherwise, it is put in second union.
>

Ok.

> >               } iter;
> >               struct  {
> >                       __u32 netns_ino;
> > diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
> > index 057ba8e01e70..00e05b69a4df 100644
> > --- a/kernel/bpf/Makefile
> > +++ b/kernel/bpf/Makefile
> > @@ -24,6 +24,9 @@ endif
> >   ifeq ($(CONFIG_PERF_EVENTS),y)
> >   obj-$(CONFIG_BPF_SYSCALL) += stackmap.o
> >   endif
> > +ifeq ($(CONFIG_CGROUPS),y)
> > +obj-$(CONFIG_BPF_SYSCALL) += cgroup_iter.o
> > +endif
> >   obj-$(CONFIG_CGROUP_BPF) += cgroup.o
> >   ifeq ($(CONFIG_INET),y)
> >   obj-$(CONFIG_BPF_SYSCALL) += reuseport_array.o
> > diff --git a/kernel/bpf/cgroup_iter.c b/kernel/bpf/cgroup_iter.c
> > new file mode 100644
> > index 000000000000..1027faed0b8b
> > --- /dev/null
> > +++ b/kernel/bpf/cgroup_iter.c
> > @@ -0,0 +1,252 @@
> > +// SPDX-License-Identifier: GPL-2.0-only
> > +/* Copyright (c) 2022 Google */
> > +#include <linux/bpf.h>
> > +#include <linux/btf_ids.h>
> > +#include <linux/cgroup.h>
> > +#include <linux/kernel.h>
> > +#include <linux/seq_file.h>
> > +
> > +#include "../cgroup/cgroup-internal.h"  /* cgroup_mutex and cgroup_is_dead */
> > +
> > +/* cgroup_iter provides three 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.
> > + *  2. Walk the ancestors of a 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
> > + * the root.
> > + *
> > + * The iter program can terminate the walk early by returning 1. Walk
> > + * continues if prog returns 0.
> > + *
> > + * The prog can check (seq->num == 0) to determine whether this is
> > + * the first element. The prog may also be passed a NULL cgroup,
> > + * which means the walk has completed and the prog has a chance to
> > + * do post-processing, such as outputing an epilogue.
> > + *
> > + * Note: the iter_prog is called with cgroup_mutex held.
> > + *
> > + * Currently only one session is supported, which means, depending on the
> > + * volume of data bpf program intends to send to user space, the number
> > + * of cgroups that can be walked is limited. For example, given the current
> > + * buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
> > + * cgroup, the total number of cgroups that can be walked is 512. This is
>
> Again, let us specify PAGE_SIZE = 4KB here.
>

Ok.

> > + * a limitation of cgroup_iter. If the output data is larger than the
> > + * buffer size, the second read() will signal EOPNOTSUPP. In order to work
> > + * around, the user may have to update their program to reduce the volume
> > + * of data sent to output. For example, skip some uninteresting cgroups.
> > + */
> > +
> > +struct bpf_iter__cgroup {
> > +     __bpf_md_ptr(struct bpf_iter_meta *, meta);
> > +     __bpf_md_ptr(struct cgroup *, cgroup);
> > +};
> > +
> > +struct cgroup_iter_priv {
> > +     struct cgroup_subsys_state *start_css;
> > +     bool terminate;
> > +     int order;
> > +};
> > +
> > +static void *cgroup_iter_seq_start(struct seq_file *seq, loff_t *pos)
> > +{
> > +     struct cgroup_iter_priv *p = seq->private;
> > +
> > +     mutex_lock(&cgroup_mutex);
> > +
> > +     /* cgroup_iter doesn't support read across multiple sessions. */
> > +     if (*pos > 0)
> > +             return ERR_PTR(-EOPNOTSUPP);
>
> This is not quite right. Let us say, the number of cgroups is 1,
> after bpf program run, pos = 1, and the control return to user
> space. Now the second read() will return -EOPNOTSUPP which is not
> right. -EOPNOTSUPP should be returned ONLY if the previous cgroup
> iterations do not traverse all cgroups.
> So you might need to record additional information in cgroup_iter_priv
> to record such information.
>

Oh, I missed seeing this scenario. Then we need a flag in
cgroup_iter_priv indicating whether iter is happening. Only when
during iter hasn't ended, we return -EOPNOTSUPP.

> > +
> > +     ++*pos;
> > +     p->terminate = false;
> > +     if (p->order == BPF_ITER_CGROUP_PRE)
> > +             return css_next_descendant_pre(NULL, p->start_css);
> > +     else if (p->order == BPF_ITER_CGROUP_POST)
> > +             return css_next_descendant_post(NULL, p->start_css);
> > +     else /* BPF_ITER_CGROUP_PARENT_UP */
> > +             return p->start_css;
> > +}
> > +
> > +static int __cgroup_iter_seq_show(struct seq_file *seq,
> > +                               struct cgroup_subsys_state *css, int in_stop);
> > +
> > +static void cgroup_iter_seq_stop(struct seq_file *seq, void *v)
> > +{
> > +     /* pass NULL to the prog for post-processing */
> > +     if (!v)
> > +             __cgroup_iter_seq_show(seq, NULL, true);
> > +     mutex_unlock(&cgroup_mutex);
> > +}
> > +
> > +static void *cgroup_iter_seq_next(struct seq_file *seq, void *v, loff_t *pos)
> > +{
> > +     struct cgroup_subsys_state *curr = (struct cgroup_subsys_state *)v;
> > +     struct cgroup_iter_priv *p = seq->private;
> > +
> > +     ++*pos;
> > +     if (p->terminate)
> > +             return NULL;
> > +
> > +     if (p->order == BPF_ITER_CGROUP_PRE)
> > +             return css_next_descendant_pre(curr, p->start_css);
> > +     else if (p->order == BPF_ITER_CGROUP_POST)
> > +             return css_next_descendant_post(curr, p->start_css);
> > +     else
> > +             return curr->parent;
> > +}
> > +
> [...]

Hao Luo July 28, 2022, 5:26 p.m. UTC | #8

On Wed, Jul 27, 2022 at 11:56 PM Yonghong Song <[e-mail]> wrote:
>
>
>
> On 7/22/22 1:33 PM, Hao Luo wrote:
> > On Fri, Jul 22, 2022 at 11:36 AM Kumar Kartikeya Dwivedi
> > <[e-mail]> wrote:
> >>
> >> On Fri, 22 Jul 2022 at 19:52, Yosry Ahmed <[e-mail]> wrote:
<...>
> >>> +
> >>> +static int __cgroup_iter_seq_show(struct seq_file *seq,
> >>> +                                 struct cgroup_subsys_state *css, int in_stop);
> >>> +
> >>> +static void cgroup_iter_seq_stop(struct seq_file *seq, void *v)
> >>> +{
> >>> +       /* pass NULL to the prog for post-processing */
> >>> +       if (!v)
> >>> +               __cgroup_iter_seq_show(seq, NULL, true);
> >>> +       mutex_unlock(&cgroup_mutex);
> >>
> >> I'm just curious, but would it be a good optimization (maybe in a
> >> follow up) to move this mutex_unlock before the check on v? That
> >> allows you to store/buffer some info you want to print as a compressed
> >> struct in a map, then write the full text to the seq_file outside the
> >> cgroup_mutex lock in the post-processing invocation.
> >>
> >> It probably also allows you to walk the whole hierarchy, if one
> >> doesn't want to run into seq_file buffer limit (or it can decide what
> >> to print within the limit in the post processing invocation), or it
> >> can use some out of band way (ringbuf, hashmap, etc.) to send the data
> >> to userspace. But all of this can happen without holding cgroup_mutex
> >> lock.
> >
> > Thanks Kumar.
> >
> > It sounds like an idea, but the key thing is not about moving
> > cgroup_mutex unlock before the check IMHO. The user can achieve
> > compression using the current infra. Compression could actually be
> > done in the bpf program. user can define and output binary content and
> > implement a userspace library to parse/decompress when reading out the
> > data.
>
> Right mutex_unlock() can be moved to the beginning of the
> function since the cgroup is not used in
>    __cgroup_iter_seq_show(seq, NULL, true)

Ok. Will do.

Tejun Heo July 28, 2022, 5:35 p.m. UTC | #9

On Thu, Jul 28, 2022 at 10:20:46AM -0700, Hao Luo wrote:
...
> is a good feature of this convention. My thoughts: It seems that ID
> may be better, for two reasons. First, because ID is stateless, the
> userspace doesn't have to remember closing the FD. Second, using
> different identifications in two directions (userspace specifies
> cgroup using FD, while kernel reports cgroup using ID) introduces a
> little complexity when connecting them together.

Yeah, you can pass the IDs around different processes, print and log them in
meaningful ways and so on because they're actual IDs, so my preference is
towards using them for anything new.

Thanks.

Yonghong Song July 28, 2022, 6:08 p.m. UTC | #10

On 7/28/22 10:25 AM, Hao Luo wrote:
> On Wed, Jul 27, 2022 at 10:49 PM Yonghong Song <[e-mail]> wrote:
>>
>>
>>
>> On 7/22/22 10:48 AM, Yosry Ahmed wrote:
>>> From: Hao Luo <[e-mail]>
>>>
>>> Cgroup_iter is a type of bpf_iter. It walks over cgroups in three modes:
>>>
>>>    - walking a cgroup's descendants in pre-order.
>>>    - walking a cgroup's descendants in post-order.
>>>    - walking a cgroup's ancestors.
>>>
>>> When attaching cgroup_iter, one can set a cgroup to the iter_link
>>> created from attaching. This cgroup is passed as a file descriptor and
>>> serves as the starting point of the walk. If no cgroup is specified,
>>> the starting point will be the root cgroup.
>>>
>>> For walking descendants, one can specify the order: either pre-order or
>>> post-order. For walking ancestors, the walk starts at the specified
>>> cgroup and ends at the root.
>>>
>>> One can also terminate the walk early by returning 1 from the iter
>>> program.
>>>
>>> Note that because walking cgroup hierarchy holds cgroup_mutex, the iter
>>> program is called with cgroup_mutex held.
>>>
>>> Currently only one session is supported, which means, depending on the
>>> volume of data bpf program intends to send to user space, the number
>>> of cgroups that can be walked is limited. For example, given the current
>>> buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
>>> cgroup, the total number of cgroups that can be walked is 512. This is
>>
>> PAGE_SIZE needs to be 4KB in order to conclude that the total number of
>> walked cgroups is 512.
>>
> 
> Sure. Will change that.
> 
>>> a limitation of cgroup_iter. If the output data is larger than the
>>> buffer size, the second read() will signal EOPNOTSUPP. In order to work
>>> around, the user may have to update their program to reduce the volume
>>> of data sent to output. For example, skip some uninteresting cgroups.
>>> In future, we may extend bpf_iter flags to allow customizing buffer
>>> size.
>>>
>>> Signed-off-by: Hao Luo <[e-mail]>
>>> Signed-off-by: Yosry Ahmed <[e-mail]>
>>> Acked-by: Yonghong Song <[e-mail]>
>>> ---
>>>    include/linux/bpf.h                           |   8 +
>>>    include/uapi/linux/bpf.h                      |  30 +++
>>>    kernel/bpf/Makefile                           |   3 +
>>>    kernel/bpf/cgroup_iter.c                      | 252 ++++++++++++++++++
>>>    tools/include/uapi/linux/bpf.h                |  30 +++
>>>    .../selftests/bpf/prog_tests/btf_dump.c       |   4 +-
>>>    6 files changed, 325 insertions(+), 2 deletions(-)
>>>    create mode 100644 kernel/bpf/cgroup_iter.c
>>
>> This patch cannot apply to bpf-next cleanly, so please rebase
>> and post again.
>>
> 
> Sorry about that. Will do.
> 
>>>
>>> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
>>> index a97751d845c9..9061618fe929 100644
>>> --- a/include/linux/bpf.h
>>> +++ b/include/linux/bpf.h
>>> @@ -47,6 +47,7 @@ struct kobject;
>>>    struct mem_cgroup;
>>>    struct module;
>>>    struct bpf_func_state;
>>> +struct cgroup;
>>>
>>>    extern struct idr btf_idr;
>>>    extern spinlock_t btf_idr_lock;
>>> @@ -1717,7 +1718,14 @@ int bpf_obj_get_user(const char __user *pathname, int flags);
>>>        int __init bpf_iter_ ## target(args) { return 0; }
>>>
>>>    struct bpf_iter_aux_info {
>>> +     /* for map_elem iter */
>>>        struct bpf_map *map;
>>> +
>>> +     /* for cgroup iter */
>>> +     struct {
>>> +             struct cgroup *start; /* starting cgroup */
>>> +             int order;
>>> +     } cgroup;
>>>    };
>>>
>>>    typedef int (*bpf_iter_attach_target_t)(struct bpf_prog *prog,
>>> diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
>>> index ffcbf79a556b..fe50c2489350 100644
>>> --- a/include/uapi/linux/bpf.h
>>> +++ b/include/uapi/linux/bpf.h
>>> @@ -87,10 +87,30 @@ struct bpf_cgroup_storage_key {
>>>        __u32   attach_type;            /* program attach type (enum bpf_attach_type) */
>>>    };
>>>
>>> +enum bpf_iter_cgroup_traversal_order {
>>> +     BPF_ITER_CGROUP_PRE = 0,        /* pre-order traversal */
>>> +     BPF_ITER_CGROUP_POST,           /* post-order traversal */
>>> +     BPF_ITER_CGROUP_PARENT_UP,      /* traversal of ancestors up to the root */
>>> +};
>>> +
>>>    union bpf_iter_link_info {
>>>        struct {
>>>                __u32   map_fd;
>>>        } map;
>>> +
>>> +     /* cgroup_iter walks either the live descendants of a cgroup subtree, or the
>>> +      * ancestors of a given cgroup.
>>> +      */
>>> +     struct {
>>> +             /* Cgroup file descriptor. This is root of the subtree if walking
>>> +              * descendants; it's the starting cgroup if walking the ancestors.
>>> +              * If it is left 0, the traversal starts from the default cgroup v2
>>> +              * root. For walking v1 hierarchy, one should always explicitly
>>> +              * specify the cgroup_fd.
>>> +              */
>>
>> I did see how the above cgroup v1/v2 scenarios are enforced.
>>
> 
> Do you mean _not_ see? Yosry and I experimented a bit. We found even

Ya, I mean 'not see'...

> on systems where v2 is not enabled, cgroup v2 root always exists and
> can be attached to, and can be iterated on (only trivially). We didn't
> find a way to tell v1 and v2 apart and deemed a comment to instruct v1
> users is fine?

So, cgroup_fd = 0, start from cgroup v2 root.
     cgroup_fd != 0, start from that particular cgroup (cgroup_v1 or v2)
Okay, since cgroup v2 root is always available and can be iterated,
I think comments should be okay.

> 
>>> +             __u32   cgroup_fd;
>>> +             __u32   traversal_order;
>>> +     } cgroup;
>>>    };
>>>
>>>    /* BPF syscall commands, see bpf(2) man-page for more details. */
[...]

Andrii Nakryiko Aug. 2, 2022, 3:42 a.m. UTC | #11

On Fri, Jul 22, 2022 at 10:48 AM Yosry Ahmed <[e-mail]> wrote:
>
> From: Hao Luo <[e-mail]>
>
> Cgroup_iter is a type of bpf_iter. It walks over cgroups in three modes:
>
>  - walking a cgroup's descendants in pre-order.
>  - walking a cgroup's descendants in post-order.
>  - walking a cgroup's ancestors.
>
> When attaching cgroup_iter, one can set a cgroup to the iter_link
> created from attaching. This cgroup is passed as a file descriptor and
> serves as the starting point of the walk. If no cgroup is specified,
> the starting point will be the root cgroup.
>
> For walking descendants, one can specify the order: either pre-order or
> post-order. For walking ancestors, the walk starts at the specified
> cgroup and ends at the root.
>
> One can also terminate the walk early by returning 1 from the iter
> program.
>
> Note that because walking cgroup hierarchy holds cgroup_mutex, the iter
> program is called with cgroup_mutex held.
>
> Currently only one session is supported, which means, depending on the
> volume of data bpf program intends to send to user space, the number
> of cgroups that can be walked is limited. For example, given the current
> buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
> cgroup, the total number of cgroups that can be walked is 512. This is
> a limitation of cgroup_iter. If the output data is larger than the
> buffer size, the second read() will signal EOPNOTSUPP. In order to work
> around, the user may have to update their program to reduce the volume
> of data sent to output. For example, skip some uninteresting cgroups.
> In future, we may extend bpf_iter flags to allow customizing buffer
> size.
>
> Signed-off-by: Hao Luo <[e-mail]>
> Signed-off-by: Yosry Ahmed <[e-mail]>
> Acked-by: Yonghong Song <[e-mail]>
> ---
>  include/linux/bpf.h                           |   8 +
>  include/uapi/linux/bpf.h                      |  30 +++
>  kernel/bpf/Makefile                           |   3 +
>  kernel/bpf/cgroup_iter.c                      | 252 ++++++++++++++++++
>  tools/include/uapi/linux/bpf.h                |  30 +++
>  .../selftests/bpf/prog_tests/btf_dump.c       |   4 +-
>  6 files changed, 325 insertions(+), 2 deletions(-)
>  create mode 100644 kernel/bpf/cgroup_iter.c
>
> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> index a97751d845c9..9061618fe929 100644
> --- a/include/linux/bpf.h
> +++ b/include/linux/bpf.h
> @@ -47,6 +47,7 @@ struct kobject;
>  struct mem_cgroup;
>  struct module;
>  struct bpf_func_state;
> +struct cgroup;
>
>  extern struct idr btf_idr;
>  extern spinlock_t btf_idr_lock;
> @@ -1717,7 +1718,14 @@ int bpf_obj_get_user(const char __user *pathname, int flags);
>         int __init bpf_iter_ ## target(args) { return 0; }
>
>  struct bpf_iter_aux_info {
> +       /* for map_elem iter */
>         struct bpf_map *map;
> +
> +       /* for cgroup iter */
> +       struct {
> +               struct cgroup *start; /* starting cgroup */
> +               int order;
> +       } cgroup;
>  };
>
>  typedef int (*bpf_iter_attach_target_t)(struct bpf_prog *prog,
> diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
> index ffcbf79a556b..fe50c2489350 100644
> --- a/include/uapi/linux/bpf.h
> +++ b/include/uapi/linux/bpf.h
> @@ -87,10 +87,30 @@ struct bpf_cgroup_storage_key {
>         __u32   attach_type;            /* program attach type (enum bpf_attach_type) */
>  };
>
> +enum bpf_iter_cgroup_traversal_order {
> +       BPF_ITER_CGROUP_PRE = 0,        /* pre-order traversal */
> +       BPF_ITER_CGROUP_POST,           /* post-order traversal */
> +       BPF_ITER_CGROUP_PARENT_UP,      /* traversal of ancestors up to the root */

I've just put up my arguments why it's a good idea to also support a
"trivial" mode of only traversing specified cgroup and no descendants
or parents. Please see [0]. I think the same applies here, especially
considering that it seems like a good idea to support
task/task_vma/task_files iteration within a cgroup. So depending on
how successful I am in arguing for supporting task iterator with
target cgroup, I think we should reuse *exactly* this
bpf_iter_cgroup_traversal_order and how we specify cgroup (FD or ID,
see some more below) *as is* in task iterators as well. In the latter
case, having an ability to say "iterate task for only given cgroup" is
very useful, and for such mode all the PRE/POST/PARENT_UP is just an
unnecessary nuisance.

So please consider also adding and supporting BPF_ITER_CGROUP_SELF (or
whatever naming makes most sense).


Some more naming nits. I find BPF_ITER_CGROUP_PRE and
BPF_ITER_CGROUP_POST a bit confusing. Even internally in kernel we
have css_next_descendant_pre/css_next_descendant_post, so why not
reflect the fact that we are going to iterate descendants:
BPF_ITER_CGROUP_DESCENDANTS_{PRE,POST}. And now that we use
"descendants" terminology, PARENT_UP should be ANCESTORS. ANCESTORS_UP
probably is fine, but seems a bit redundant (unless we consider a
somewhat weird ANCESTORS_DOWN, where we find the furthest parent and
then descend through preceding parents until we reach specified
cgroup; seems a bit exotic).

  [0] https://lore.kernel.org/bpf/[e-mail]/T/#m5ce50632aa550dd87a99241efb168cbcde1ee98f

> +};
> +
>  union bpf_iter_link_info {
>         struct {
>                 __u32   map_fd;
>         } map;
> +
> +       /* cgroup_iter walks either the live descendants of a cgroup subtree, or the
> +        * ancestors of a given cgroup.
> +        */
> +       struct {
> +               /* Cgroup file descriptor. This is root of the subtree if walking
> +                * descendants; it's the starting cgroup if walking the ancestors.
> +                * If it is left 0, the traversal starts from the default cgroup v2
> +                * root. For walking v1 hierarchy, one should always explicitly
> +                * specify the cgroup_fd.
> +                */
> +               __u32   cgroup_fd;

Now, similar to what I argued in regard of pidfd vs pid, I think the
same applied to cgroup_fd vs cgroup_id. Why can't we support both?
cgroup_fd has some benefits, but cgroup_id is nice due to simplicity
and not having to open/close/keep extra FDs (which can add up if we
want to periodically query something about a large set of cgroups).
Please see my arguments from [0] above.

Thoughts?

> +               __u32   traversal_order;
> +       } cgroup;
>  };
>
>  /* BPF syscall commands, see bpf(2) man-page for more details. */

[...]

Hao Luo Aug. 2, 2022, 10:27 p.m. UTC | #12

Hi Andrii,

On Mon, Aug 1, 2022 at 8:43 PM Andrii Nakryiko
<[e-mail]> wrote:
>
> On Fri, Jul 22, 2022 at 10:48 AM Yosry Ahmed <[e-mail]> wrote:
> >
> > From: Hao Luo <[e-mail]>
> >
> > Cgroup_iter is a type of bpf_iter. It walks over cgroups in three modes:
> >
> >  - walking a cgroup's descendants in pre-order.
> >  - walking a cgroup's descendants in post-order.
> >  - walking a cgroup's ancestors.
> >
> > When attaching cgroup_iter, one can set a cgroup to the iter_link
> > created from attaching. This cgroup is passed as a file descriptor and
> > serves as the starting point of the walk. If no cgroup is specified,
> > the starting point will be the root cgroup.
> >
> > For walking descendants, one can specify the order: either pre-order or
> > post-order. For walking ancestors, the walk starts at the specified
> > cgroup and ends at the root.
> >
> > One can also terminate the walk early by returning 1 from the iter
> > program.
> >
> > Note that because walking cgroup hierarchy holds cgroup_mutex, the iter
> > program is called with cgroup_mutex held.
> >
> > Currently only one session is supported, which means, depending on the
> > volume of data bpf program intends to send to user space, the number
> > of cgroups that can be walked is limited. For example, given the current
> > buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
> > cgroup, the total number of cgroups that can be walked is 512. This is
> > a limitation of cgroup_iter. If the output data is larger than the
> > buffer size, the second read() will signal EOPNOTSUPP. In order to work
> > around, the user may have to update their program to reduce the volume
> > of data sent to output. For example, skip some uninteresting cgroups.
> > In future, we may extend bpf_iter flags to allow customizing buffer
> > size.
> >
> > Signed-off-by: Hao Luo <[e-mail]>
> > Signed-off-by: Yosry Ahmed <[e-mail]>
> > Acked-by: Yonghong Song <[e-mail]>
> > ---
> >  include/linux/bpf.h                           |   8 +
> >  include/uapi/linux/bpf.h                      |  30 +++
> >  kernel/bpf/Makefile                           |   3 +
> >  kernel/bpf/cgroup_iter.c                      | 252 ++++++++++++++++++
> >  tools/include/uapi/linux/bpf.h                |  30 +++
> >  .../selftests/bpf/prog_tests/btf_dump.c       |   4 +-
> >  6 files changed, 325 insertions(+), 2 deletions(-)
> >  create mode 100644 kernel/bpf/cgroup_iter.c
> >
> > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > index a97751d845c9..9061618fe929 100644
> > --- a/include/linux/bpf.h
> > +++ b/include/linux/bpf.h
> > @@ -47,6 +47,7 @@ struct kobject;
> >  struct mem_cgroup;
> >  struct module;
> >  struct bpf_func_state;
> > +struct cgroup;
> >
> >  extern struct idr btf_idr;
> >  extern spinlock_t btf_idr_lock;
> > @@ -1717,7 +1718,14 @@ int bpf_obj_get_user(const char __user *pathname, int flags);
> >         int __init bpf_iter_ ## target(args) { return 0; }
> >
> >  struct bpf_iter_aux_info {
> > +       /* for map_elem iter */
> >         struct bpf_map *map;
> > +
> > +       /* for cgroup iter */
> > +       struct {
> > +               struct cgroup *start; /* starting cgroup */
> > +               int order;
> > +       } cgroup;
> >  };
> >
> >  typedef int (*bpf_iter_attach_target_t)(struct bpf_prog *prog,
> > diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
> > index ffcbf79a556b..fe50c2489350 100644
> > --- a/include/uapi/linux/bpf.h
> > +++ b/include/uapi/linux/bpf.h
> > @@ -87,10 +87,30 @@ struct bpf_cgroup_storage_key {
> >         __u32   attach_type;            /* program attach type (enum bpf_attach_type) */
> >  };
> >
> > +enum bpf_iter_cgroup_traversal_order {
> > +       BPF_ITER_CGROUP_PRE = 0,        /* pre-order traversal */
> > +       BPF_ITER_CGROUP_POST,           /* post-order traversal */
> > +       BPF_ITER_CGROUP_PARENT_UP,      /* traversal of ancestors up to the root */
>
> I've just put up my arguments why it's a good idea to also support a
> "trivial" mode of only traversing specified cgroup and no descendants
> or parents. Please see [0].

cc Kui-Feng in this thread.

Yeah, I think it's a good idea. It's useful when we only want to show
a single object, which can be common. Going further, I think we may
want to restructure bpf_iter to optimize for this case.

> I think the same applies here, especially
> considering that it seems like a good idea to support
> task/task_vma/task_files iteration within a cgroup.

I have reservations on these use cases. I don't see immediate use of
iterating vma or files within a cgroup. Tasks within a cgroup? Maybe.
:)

> So depending on
> how successful I am in arguing for supporting task iterator with
> target cgroup, I think we should reuse *exactly* this
> bpf_iter_cgroup_traversal_order and how we specify cgroup (FD or ID,
> see some more below) *as is* in task iterators as well. In the latter
> case, having an ability to say "iterate task for only given cgroup" is
> very useful, and for such mode all the PRE/POST/PARENT_UP is just an
> unnecessary nuisance.
>
> So please consider also adding and supporting BPF_ITER_CGROUP_SELF (or
> whatever naming makes most sense).
>

PRE/POST/UP can be reused for iter of tree-structured containers, like
rbtree [1]. SELF can be reused for any iters like iter/task,
iter/cgroup, etc. Promoting all of them out of cgroup-specific struct
seems valuable.

[1] https://lwn.net/Articles/902405/

>
> Some more naming nits. I find BPF_ITER_CGROUP_PRE and
> BPF_ITER_CGROUP_POST a bit confusing. Even internally in kernel we
> have css_next_descendant_pre/css_next_descendant_post, so why not
> reflect the fact that we are going to iterate descendants:
> BPF_ITER_CGROUP_DESCENDANTS_{PRE,POST}. And now that we use
> "descendants" terminology, PARENT_UP should be ANCESTORS. ANCESTORS_UP
> probably is fine, but seems a bit redundant (unless we consider a
> somewhat weird ANCESTORS_DOWN, where we find the furthest parent and
> then descend through preceding parents until we reach specified
> cgroup; seems a bit exotic).
>

BPF_ITER_CGROUP_DESCENDANTS_PRE is too verbose. If there is a
possibility of merging rbtree and supporting walk order of rbtree
iter, maybe the name here could be general, like
BPF_ITER_DESCENDANTS_PRE, which seems better.

>   [0] https://lore.kernel.org/bpf/[e-mail]/T/#m5ce50632aa550dd87a99241efb168cbcde1ee98f
>
> > +};
> > +
> >  union bpf_iter_link_info {
> >         struct {
> >                 __u32   map_fd;
> >         } map;
> > +
> > +       /* cgroup_iter walks either the live descendants of a cgroup subtree, or the
> > +        * ancestors of a given cgroup.
> > +        */
> > +       struct {
> > +               /* Cgroup file descriptor. This is root of the subtree if walking
> > +                * descendants; it's the starting cgroup if walking the ancestors.
> > +                * If it is left 0, the traversal starts from the default cgroup v2
> > +                * root. For walking v1 hierarchy, one should always explicitly
> > +                * specify the cgroup_fd.
> > +                */
> > +               __u32   cgroup_fd;
>
> Now, similar to what I argued in regard of pidfd vs pid, I think the
> same applied to cgroup_fd vs cgroup_id. Why can't we support both?
> cgroup_fd has some benefits, but cgroup_id is nice due to simplicity
> and not having to open/close/keep extra FDs (which can add up if we
> want to periodically query something about a large set of cgroups).
> Please see my arguments from [0] above.
>
> Thoughts?
>

We can support both, it's a good idea IMO. But what exactly is the
interface going to look like? Can you be more specific about that?
Below is something I tried based on your description.

@@ -91,6 +91,18 @@ union bpf_iter_link_info {
        struct {
                __u32   map_fd;
        } map;
+       struct {
+               /* PRE/POST/UP/SELF */
+               __u32 order;
+               struct {
+                       __u32 cgroup_fd;
+                       __u64 cgroup_id;
+               } cgroup;
+               struct {
+                       __u32 pid_fd;
+                       __u64 pid;
+               } task;
+       };
 };

> > +               __u32   traversal_order;
> > +       } cgroup;
> >  };
> >
> >  /* BPF syscall commands, see bpf(2) man-page for more details. */
>
> [...]

Andrii Nakryiko Aug. 2, 2022, 10:49 p.m. UTC | #13

On Tue, Aug 2, 2022 at 3:27 PM Hao Luo <[e-mail]> wrote:
>
> Hi Andrii,
>
> On Mon, Aug 1, 2022 at 8:43 PM Andrii Nakryiko
> <[e-mail]> wrote:
> >
> > On Fri, Jul 22, 2022 at 10:48 AM Yosry Ahmed <[e-mail]> wrote:
> > >
> > > From: Hao Luo <[e-mail]>
> > >
> > > Cgroup_iter is a type of bpf_iter. It walks over cgroups in three modes:
> > >
> > >  - walking a cgroup's descendants in pre-order.
> > >  - walking a cgroup's descendants in post-order.
> > >  - walking a cgroup's ancestors.
> > >
> > > When attaching cgroup_iter, one can set a cgroup to the iter_link
> > > created from attaching. This cgroup is passed as a file descriptor and
> > > serves as the starting point of the walk. If no cgroup is specified,
> > > the starting point will be the root cgroup.
> > >
> > > For walking descendants, one can specify the order: either pre-order or
> > > post-order. For walking ancestors, the walk starts at the specified
> > > cgroup and ends at the root.
> > >
> > > One can also terminate the walk early by returning 1 from the iter
> > > program.
> > >
> > > Note that because walking cgroup hierarchy holds cgroup_mutex, the iter
> > > program is called with cgroup_mutex held.
> > >
> > > Currently only one session is supported, which means, depending on the
> > > volume of data bpf program intends to send to user space, the number
> > > of cgroups that can be walked is limited. For example, given the current
> > > buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
> > > cgroup, the total number of cgroups that can be walked is 512. This is
> > > a limitation of cgroup_iter. If the output data is larger than the
> > > buffer size, the second read() will signal EOPNOTSUPP. In order to work
> > > around, the user may have to update their program to reduce the volume
> > > of data sent to output. For example, skip some uninteresting cgroups.
> > > In future, we may extend bpf_iter flags to allow customizing buffer
> > > size.
> > >
> > > Signed-off-by: Hao Luo <[e-mail]>
> > > Signed-off-by: Yosry Ahmed <[e-mail]>
> > > Acked-by: Yonghong Song <[e-mail]>
> > > ---
> > >  include/linux/bpf.h                           |   8 +
> > >  include/uapi/linux/bpf.h                      |  30 +++
> > >  kernel/bpf/Makefile                           |   3 +
> > >  kernel/bpf/cgroup_iter.c                      | 252 ++++++++++++++++++
> > >  tools/include/uapi/linux/bpf.h                |  30 +++
> > >  .../selftests/bpf/prog_tests/btf_dump.c       |   4 +-
> > >  6 files changed, 325 insertions(+), 2 deletions(-)
> > >  create mode 100644 kernel/bpf/cgroup_iter.c
> > >
> > > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > > index a97751d845c9..9061618fe929 100644
> > > --- a/include/linux/bpf.h
> > > +++ b/include/linux/bpf.h
> > > @@ -47,6 +47,7 @@ struct kobject;
> > >  struct mem_cgroup;
> > >  struct module;
> > >  struct bpf_func_state;
> > > +struct cgroup;
> > >
> > >  extern struct idr btf_idr;
> > >  extern spinlock_t btf_idr_lock;
> > > @@ -1717,7 +1718,14 @@ int bpf_obj_get_user(const char __user *pathname, int flags);
> > >         int __init bpf_iter_ ## target(args) { return 0; }
> > >
> > >  struct bpf_iter_aux_info {
> > > +       /* for map_elem iter */
> > >         struct bpf_map *map;
> > > +
> > > +       /* for cgroup iter */
> > > +       struct {
> > > +               struct cgroup *start; /* starting cgroup */
> > > +               int order;
> > > +       } cgroup;
> > >  };
> > >
> > >  typedef int (*bpf_iter_attach_target_t)(struct bpf_prog *prog,
> > > diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
> > > index ffcbf79a556b..fe50c2489350 100644
> > > --- a/include/uapi/linux/bpf.h
> > > +++ b/include/uapi/linux/bpf.h
> > > @@ -87,10 +87,30 @@ struct bpf_cgroup_storage_key {
> > >         __u32   attach_type;            /* program attach type (enum bpf_attach_type) */
> > >  };
> > >
> > > +enum bpf_iter_cgroup_traversal_order {
> > > +       BPF_ITER_CGROUP_PRE = 0,        /* pre-order traversal */
> > > +       BPF_ITER_CGROUP_POST,           /* post-order traversal */
> > > +       BPF_ITER_CGROUP_PARENT_UP,      /* traversal of ancestors up to the root */
> >
> > I've just put up my arguments why it's a good idea to also support a
> > "trivial" mode of only traversing specified cgroup and no descendants
> > or parents. Please see [0].
>
> cc Kui-Feng in this thread.
>
> Yeah, I think it's a good idea. It's useful when we only want to show
> a single object, which can be common. Going further, I think we may
> want to restructure bpf_iter to optimize for this case.
>
> > I think the same applies here, especially
> > considering that it seems like a good idea to support
> > task/task_vma/task_files iteration within a cgroup.
>
> I have reservations on these use cases. I don't see immediate use of
> iterating vma or files within a cgroup. Tasks within a cgroup? Maybe.
> :)
>

iter/task was what I had in mind in the first place. But I can also
imagine tools utilizing iter/task_files for each process within a
cgroup, so given iter/{task, task_file, task_vma} share the same UAPI
and internals, I don't see why we'd restrict this to only iter/task.

> > So depending on
> > how successful I am in arguing for supporting task iterator with
> > target cgroup, I think we should reuse *exactly* this
> > bpf_iter_cgroup_traversal_order and how we specify cgroup (FD or ID,
> > see some more below) *as is* in task iterators as well. In the latter
> > case, having an ability to say "iterate task for only given cgroup" is
> > very useful, and for such mode all the PRE/POST/PARENT_UP is just an
> > unnecessary nuisance.
> >
> > So please consider also adding and supporting BPF_ITER_CGROUP_SELF (or
> > whatever naming makes most sense).
> >
>
> PRE/POST/UP can be reused for iter of tree-structured containers, like
> rbtree [1]. SELF can be reused for any iters like iter/task,
> iter/cgroup, etc. Promoting all of them out of cgroup-specific struct
> seems valuable.

you mean just define them as generic tree traversal orders? Sure, I
guess makes sense. No strong feelings.

>
> [1] https://lwn.net/Articles/902405/
>
> >
> > Some more naming nits. I find BPF_ITER_CGROUP_PRE and
> > BPF_ITER_CGROUP_POST a bit confusing. Even internally in kernel we
> > have css_next_descendant_pre/css_next_descendant_post, so why not
> > reflect the fact that we are going to iterate descendants:
> > BPF_ITER_CGROUP_DESCENDANTS_{PRE,POST}. And now that we use
> > "descendants" terminology, PARENT_UP should be ANCESTORS. ANCESTORS_UP
> > probably is fine, but seems a bit redundant (unless we consider a
> > somewhat weird ANCESTORS_DOWN, where we find the furthest parent and
> > then descend through preceding parents until we reach specified
> > cgroup; seems a bit exotic).
> >
>
> BPF_ITER_CGROUP_DESCENDANTS_PRE is too verbose. If there is a
> possibility of merging rbtree and supporting walk order of rbtree
> iter, maybe the name here could be general, like
> BPF_ITER_DESCENDANTS_PRE, which seems better.

it's not like you'll be typing this hundreds of type, so verboseness
doesn't seem to be too problematic, but sure, BPF_ITER_DESCENDANTS_PRE
is fine with me

>
> >   [0] https://lore.kernel.org/bpf/[e-mail]/T/#m5ce50632aa550dd87a99241efb168cbcde1ee98f
> >
> > > +};
> > > +
> > >  union bpf_iter_link_info {
> > >         struct {
> > >                 __u32   map_fd;
> > >         } map;
> > > +
> > > +       /* cgroup_iter walks either the live descendants of a cgroup subtree, or the
> > > +        * ancestors of a given cgroup.
> > > +        */
> > > +       struct {
> > > +               /* Cgroup file descriptor. This is root of the subtree if walking
> > > +                * descendants; it's the starting cgroup if walking the ancestors.
> > > +                * If it is left 0, the traversal starts from the default cgroup v2
> > > +                * root. For walking v1 hierarchy, one should always explicitly
> > > +                * specify the cgroup_fd.
> > > +                */
> > > +               __u32   cgroup_fd;
> >
> > Now, similar to what I argued in regard of pidfd vs pid, I think the
> > same applied to cgroup_fd vs cgroup_id. Why can't we support both?
> > cgroup_fd has some benefits, but cgroup_id is nice due to simplicity
> > and not having to open/close/keep extra FDs (which can add up if we
> > want to periodically query something about a large set of cgroups).
> > Please see my arguments from [0] above.
> >
> > Thoughts?
> >
>
> We can support both, it's a good idea IMO. But what exactly is the
> interface going to look like? Can you be more specific about that?
> Below is something I tried based on your description.
>
> @@ -91,6 +91,18 @@ union bpf_iter_link_info {
>         struct {
>                 __u32   map_fd;
>         } map;
> +       struct {
> +               /* PRE/POST/UP/SELF */
> +               __u32 order;
> +               struct {
> +                       __u32 cgroup_fd;
> +                       __u64 cgroup_id;
> +               } cgroup;
> +               struct {
> +                       __u32 pid_fd;
> +                       __u64 pid;
> +               } task;
> +       };
>  };
>

So I wouldn't combine task and cgroup definition together, let's keep
them independent.

then for cgroup we can do something like:

struct {
    __u32 order;
    __u32 cgroup_fd; /* cgroup_fd ^ cgroup_id, exactly one can be non-zero */
    __u32 cgroup_id;
} cgroup

Similar idea with task, but it's a bit more complicated because there
we have target that can be pid, pidfd, or cgroup (cgroup_fd and
cgroup_id). I haven't put much thought into the best representation,
though.

> > > +               __u32   traversal_order;
> > > +       } cgroup;
> > >  };
> > >
> > >  /* BPF syscall commands, see bpf(2) man-page for more details. */
> >
> > [...]

Hao Luo Aug. 3, 2022, 8:29 p.m. UTC | #14

On Tue, Aug 2, 2022 at 3:50 PM Andrii Nakryiko
<[e-mail]> wrote:
>
> On Tue, Aug 2, 2022 at 3:27 PM Hao Luo <[e-mail]> wrote:
> >
> > Hi Andrii,
> >
> > On Mon, Aug 1, 2022 at 8:43 PM Andrii Nakryiko
> > <[e-mail]> wrote:
> > >
> > > On Fri, Jul 22, 2022 at 10:48 AM Yosry Ahmed <[e-mail]> wrote:
[...]
> > > >
> > > > +enum bpf_iter_cgroup_traversal_order {
> > > > +       BPF_ITER_CGROUP_PRE = 0,        /* pre-order traversal */
> > > > +       BPF_ITER_CGROUP_POST,           /* post-order traversal */
> > > > +       BPF_ITER_CGROUP_PARENT_UP,      /* traversal of ancestors up to the root */
> > >
> > > I've just put up my arguments why it's a good idea to also support a
> > > "trivial" mode of only traversing specified cgroup and no descendants
> > > or parents. Please see [0].
> >
> > cc Kui-Feng in this thread.
> >
> > Yeah, I think it's a good idea. It's useful when we only want to show
> > a single object, which can be common. Going further, I think we may
> > want to restructure bpf_iter to optimize for this case.
> >
> > > I think the same applies here, especially
> > > considering that it seems like a good idea to support
> > > task/task_vma/task_files iteration within a cgroup.
> >
> > I have reservations on these use cases. I don't see immediate use of
> > iterating vma or files within a cgroup. Tasks within a cgroup? Maybe.
> > :)
> >
>
> iter/task was what I had in mind in the first place. But I can also
> imagine tools utilizing iter/task_files for each process within a
> cgroup, so given iter/{task, task_file, task_vma} share the same UAPI
> and internals, I don't see why we'd restrict this to only iter/task.

No problem. I was hoping we don't over-design the interface. IMHO keep
it simple stupid. :)

>
[...]
> >
> > [1] https://lwn.net/Articles/902405/
> >
> > >
> > > Some more naming nits. I find BPF_ITER_CGROUP_PRE and
> > > BPF_ITER_CGROUP_POST a bit confusing. Even internally in kernel we
> > > have css_next_descendant_pre/css_next_descendant_post, so why not
> > > reflect the fact that we are going to iterate descendants:
> > > BPF_ITER_CGROUP_DESCENDANTS_{PRE,POST}. And now that we use
> > > "descendants" terminology, PARENT_UP should be ANCESTORS. ANCESTORS_UP
> > > probably is fine, but seems a bit redundant (unless we consider a
> > > somewhat weird ANCESTORS_DOWN, where we find the furthest parent and
> > > then descend through preceding parents until we reach specified
> > > cgroup; seems a bit exotic).
> > >
> >
> > BPF_ITER_CGROUP_DESCENDANTS_PRE is too verbose. If there is a
> > possibility of merging rbtree and supporting walk order of rbtree
> > iter, maybe the name here could be general, like
> > BPF_ITER_DESCENDANTS_PRE, which seems better.
>
> it's not like you'll be typing this hundreds of type, so verboseness
> doesn't seem to be too problematic, but sure, BPF_ITER_DESCENDANTS_PRE
> is fine with me
>
> >
> > >   [0] https://lore.kernel.org/bpf/[e-mail]/T/#m5ce50632aa550dd87a99241efb168cbcde1ee98f
> > >
> > > > +};
> > > > +
> > > >  union bpf_iter_link_info {
> > > >         struct {
> > > >                 __u32   map_fd;
> > > >         } map;
> > > > +
> > > > +       /* cgroup_iter walks either the live descendants of a cgroup subtree, or the
> > > > +        * ancestors of a given cgroup.
> > > > +        */
> > > > +       struct {
> > > > +               /* Cgroup file descriptor. This is root of the subtree if walking
> > > > +                * descendants; it's the starting cgroup if walking the ancestors.
> > > > +                * If it is left 0, the traversal starts from the default cgroup v2
> > > > +                * root. For walking v1 hierarchy, one should always explicitly
> > > > +                * specify the cgroup_fd.
> > > > +                */
> > > > +               __u32   cgroup_fd;
> > >
> > > Now, similar to what I argued in regard of pidfd vs pid, I think the
> > > same applied to cgroup_fd vs cgroup_id. Why can't we support both?
> > > cgroup_fd has some benefits, but cgroup_id is nice due to simplicity
> > > and not having to open/close/keep extra FDs (which can add up if we
> > > want to periodically query something about a large set of cgroups).
> > > Please see my arguments from [0] above.
> > >
> > > Thoughts?
> > >
> >
> > We can support both, it's a good idea IMO. But what exactly is the
> > interface going to look like? Can you be more specific about that?
> > Below is something I tried based on your description.
> >
> > @@ -91,6 +91,18 @@ union bpf_iter_link_info {
> >         struct {
> >                 __u32   map_fd;
> >         } map;
> > +       struct {
> > +               /* PRE/POST/UP/SELF */
> > +               __u32 order;
> > +               struct {
> > +                       __u32 cgroup_fd;
> > +                       __u64 cgroup_id;
> > +               } cgroup;
> > +               struct {
> > +                       __u32 pid_fd;
> > +                       __u64 pid;
> > +               } task;
> > +       };
> >  };
> >
>
> So I wouldn't combine task and cgroup definition together, let's keep
> them independent.
>
> then for cgroup we can do something like:
>
> struct {
>     __u32 order;
>     __u32 cgroup_fd; /* cgroup_fd ^ cgroup_id, exactly one can be non-zero */
>     __u32 cgroup_id;
> } cgroup
>
> Similar idea with task, but it's a bit more complicated because there
> we have target that can be pid, pidfd, or cgroup (cgroup_fd and
> cgroup_id). I haven't put much thought into the best representation,
> though.
>

The cgroup part sounds good to me. For the full picture, how about
this? I'm just trying  a prototype, hoping that it can help people to
get a clear picture.

union bpf_iter_link_info {
          struct {
                  __u32   map_fd;
          } map;
          struct {
                  __u32   order; /* PRE/POST/UP/SELF */
                  __u32   cgroup_fd;
                  __u64   cgroup_id;
          } cgroup;
          struct {
                  __u32   pid;
                  __u32   pid_fd;
                  __u64   cgroup_id;
                  __u32   cgroup_fd;
                  __u32   mode; /* SELF or others */
          } task;
};

> > > > +               __u32   traversal_order;
> > > > +       } cgroup;
> > > >  };
> > > >
> > > >  /* BPF syscall commands, see bpf(2) man-page for more details. */
> > >
> > > [...]

Andrii Nakryiko Aug. 3, 2022, 8:39 p.m. UTC | #15

On Wed, Aug 3, 2022 at 1:30 PM Hao Luo <[e-mail]> wrote:
>
> On Tue, Aug 2, 2022 at 3:50 PM Andrii Nakryiko
> <[e-mail]> wrote:
> >
> > On Tue, Aug 2, 2022 at 3:27 PM Hao Luo <[e-mail]> wrote:
> > >
> > > Hi Andrii,
> > >
> > > On Mon, Aug 1, 2022 at 8:43 PM Andrii Nakryiko
> > > <[e-mail]> wrote:
> > > >
> > > > On Fri, Jul 22, 2022 at 10:48 AM Yosry Ahmed <[e-mail]> wrote:
> [...]
> > > > >
> > > > > +enum bpf_iter_cgroup_traversal_order {
> > > > > +       BPF_ITER_CGROUP_PRE = 0,        /* pre-order traversal */
> > > > > +       BPF_ITER_CGROUP_POST,           /* post-order traversal */
> > > > > +       BPF_ITER_CGROUP_PARENT_UP,      /* traversal of ancestors up to the root */
> > > >
> > > > I've just put up my arguments why it's a good idea to also support a
> > > > "trivial" mode of only traversing specified cgroup and no descendants
> > > > or parents. Please see [0].
> > >
> > > cc Kui-Feng in this thread.
> > >
> > > Yeah, I think it's a good idea. It's useful when we only want to show
> > > a single object, which can be common. Going further, I think we may
> > > want to restructure bpf_iter to optimize for this case.
> > >
> > > > I think the same applies here, especially
> > > > considering that it seems like a good idea to support
> > > > task/task_vma/task_files iteration within a cgroup.
> > >
> > > I have reservations on these use cases. I don't see immediate use of
> > > iterating vma or files within a cgroup. Tasks within a cgroup? Maybe.
> > > :)
> > >
> >
> > iter/task was what I had in mind in the first place. But I can also
> > imagine tools utilizing iter/task_files for each process within a
> > cgroup, so given iter/{task, task_file, task_vma} share the same UAPI
> > and internals, I don't see why we'd restrict this to only iter/task.
>
> No problem. I was hoping we don't over-design the interface. IMHO keep
> it simple stupid. :)
>
> >
> [...]
> > >
> > > [1] https://lwn.net/Articles/902405/
> > >
> > > >
> > > > Some more naming nits. I find BPF_ITER_CGROUP_PRE and
> > > > BPF_ITER_CGROUP_POST a bit confusing. Even internally in kernel we
> > > > have css_next_descendant_pre/css_next_descendant_post, so why not
> > > > reflect the fact that we are going to iterate descendants:
> > > > BPF_ITER_CGROUP_DESCENDANTS_{PRE,POST}. And now that we use
> > > > "descendants" terminology, PARENT_UP should be ANCESTORS. ANCESTORS_UP
> > > > probably is fine, but seems a bit redundant (unless we consider a
> > > > somewhat weird ANCESTORS_DOWN, where we find the furthest parent and
> > > > then descend through preceding parents until we reach specified
> > > > cgroup; seems a bit exotic).
> > > >
> > >
> > > BPF_ITER_CGROUP_DESCENDANTS_PRE is too verbose. If there is a
> > > possibility of merging rbtree and supporting walk order of rbtree
> > > iter, maybe the name here could be general, like
> > > BPF_ITER_DESCENDANTS_PRE, which seems better.
> >
> > it's not like you'll be typing this hundreds of type, so verboseness
> > doesn't seem to be too problematic, but sure, BPF_ITER_DESCENDANTS_PRE
> > is fine with me
> >
> > >
> > > >   [0] https://lore.kernel.org/bpf/[e-mail]/T/#m5ce50632aa550dd87a99241efb168cbcde1ee98f
> > > >
> > > > > +};
> > > > > +
> > > > >  union bpf_iter_link_info {
> > > > >         struct {
> > > > >                 __u32   map_fd;
> > > > >         } map;
> > > > > +
> > > > > +       /* cgroup_iter walks either the live descendants of a cgroup subtree, or the
> > > > > +        * ancestors of a given cgroup.
> > > > > +        */
> > > > > +       struct {
> > > > > +               /* Cgroup file descriptor. This is root of the subtree if walking
> > > > > +                * descendants; it's the starting cgroup if walking the ancestors.
> > > > > +                * If it is left 0, the traversal starts from the default cgroup v2
> > > > > +                * root. For walking v1 hierarchy, one should always explicitly
> > > > > +                * specify the cgroup_fd.
> > > > > +                */
> > > > > +               __u32   cgroup_fd;
> > > >
> > > > Now, similar to what I argued in regard of pidfd vs pid, I think the
> > > > same applied to cgroup_fd vs cgroup_id. Why can't we support both?
> > > > cgroup_fd has some benefits, but cgroup_id is nice due to simplicity
> > > > and not having to open/close/keep extra FDs (which can add up if we
> > > > want to periodically query something about a large set of cgroups).
> > > > Please see my arguments from [0] above.
> > > >
> > > > Thoughts?
> > > >
> > >
> > > We can support both, it's a good idea IMO. But what exactly is the
> > > interface going to look like? Can you be more specific about that?
> > > Below is something I tried based on your description.
> > >
> > > @@ -91,6 +91,18 @@ union bpf_iter_link_info {
> > >         struct {
> > >                 __u32   map_fd;
> > >         } map;
> > > +       struct {
> > > +               /* PRE/POST/UP/SELF */
> > > +               __u32 order;
> > > +               struct {
> > > +                       __u32 cgroup_fd;
> > > +                       __u64 cgroup_id;
> > > +               } cgroup;
> > > +               struct {
> > > +                       __u32 pid_fd;
> > > +                       __u64 pid;
> > > +               } task;
> > > +       };
> > >  };
> > >
> >
> > So I wouldn't combine task and cgroup definition together, let's keep
> > them independent.
> >
> > then for cgroup we can do something like:
> >
> > struct {
> >     __u32 order;
> >     __u32 cgroup_fd; /* cgroup_fd ^ cgroup_id, exactly one can be non-zero */
> >     __u32 cgroup_id;
> > } cgroup
> >
> > Similar idea with task, but it's a bit more complicated because there
> > we have target that can be pid, pidfd, or cgroup (cgroup_fd and
> > cgroup_id). I haven't put much thought into the best representation,
> > though.
> >
>
> The cgroup part sounds good to me. For the full picture, how about
> this? I'm just trying  a prototype, hoping that it can help people to
> get a clear picture.
>
> union bpf_iter_link_info {
>           struct {
>                   __u32   map_fd;
>           } map;
>           struct {
>                   __u32   order; /* PRE/POST/UP/SELF */
>                   __u32   cgroup_fd;
>                   __u64   cgroup_id;
>           } cgroup;

lgtm

>           struct {
>                   __u32   pid;
>                   __u32   pid_fd;
>                   __u64   cgroup_id;
>                   __u32   cgroup_fd;
>                   __u32   mode; /* SELF or others */

I'd move mode to be first. I'm undecided on using 4 separate fields
for pid/pid_fd/cgroup_{id,fd} vs a single union (or just generic "u64
target"  and then mode can define how we should treat target --
whether it's pid, pid_fd, cgroup ID or FD. I'm fine either way, I
think. But for cgroup case not having to duplicate PRE/POST/UP/SELF
for cgroup id and then for cgroup fd seems like a win. So separate
fields might be better. It's also pretty extendable. And I'm
personally not worried about using few more bytes in bpf_attr for
disjoin fields like this.

>           } task;
> };
>
> > > > > +               __u32   traversal_order;
> > > > > +       } cgroup;
> > > > >  };
> > > > >
> > > > >  /* BPF syscall commands, see bpf(2) man-page for more details. */
> > > >
> > > > [...]

Hao Luo Aug. 4, 2022, 12:29 a.m. UTC | #16

On Wed, Aug 3, 2022 at 1:40 PM Andrii Nakryiko
<[e-mail]> wrote:
>
> On Wed, Aug 3, 2022 at 1:30 PM Hao Luo <[e-mail]> wrote:
> >
> > On Tue, Aug 2, 2022 at 3:50 PM Andrii Nakryiko
> > <[e-mail]> wrote:
> > >
> > > On Tue, Aug 2, 2022 at 3:27 PM Hao Luo <[e-mail]> wrote:
> > > >
> > > > On Mon, Aug 1, 2022 at 8:43 PM Andrii Nakryiko
> > > > <[e-mail]> wrote:
> > > > >
> > > > > On Fri, Jul 22, 2022 at 10:48 AM Yosry Ahmed <[e-mail]> wrote:
[...]
> > > > > > +};
> > > > > > +
> > > > > >  union bpf_iter_link_info {
> > > > > >         struct {
> > > > > >                 __u32   map_fd;
> > > > > >         } map;
> > > > > > +
> > > > > > +       /* cgroup_iter walks either the live descendants of a cgroup subtree, or the
> > > > > > +        * ancestors of a given cgroup.
> > > > > > +        */
> > > > > > +       struct {
> > > > > > +               /* Cgroup file descriptor. This is root of the subtree if walking
> > > > > > +                * descendants; it's the starting cgroup if walking the ancestors.
> > > > > > +                * If it is left 0, the traversal starts from the default cgroup v2
> > > > > > +                * root. For walking v1 hierarchy, one should always explicitly
> > > > > > +                * specify the cgroup_fd.
> > > > > > +                */
> > > > > > +               __u32   cgroup_fd;
> > > > >
> > > > > Now, similar to what I argued in regard of pidfd vs pid, I think the
> > > > > same applied to cgroup_fd vs cgroup_id. Why can't we support both?
> > > > > cgroup_fd has some benefits, but cgroup_id is nice due to simplicity
> > > > > and not having to open/close/keep extra FDs (which can add up if we
> > > > > want to periodically query something about a large set of cgroups).
> > > > > Please see my arguments from [0] above.
> > > > >
> > > > > Thoughts?
> > > > >
> > > >
> > > > We can support both, it's a good idea IMO. But what exactly is the
> > > > interface going to look like? Can you be more specific about that?
> > > > Below is something I tried based on your description.
> > > >
> > > > @@ -91,6 +91,18 @@ union bpf_iter_link_info {
> > > >         struct {
> > > >                 __u32   map_fd;
> > > >         } map;
> > > > +       struct {
> > > > +               /* PRE/POST/UP/SELF */
> > > > +               __u32 order;
> > > > +               struct {
> > > > +                       __u32 cgroup_fd;
> > > > +                       __u64 cgroup_id;
> > > > +               } cgroup;
> > > > +               struct {
> > > > +                       __u32 pid_fd;
> > > > +                       __u64 pid;
> > > > +               } task;
> > > > +       };
> > > >  };
> > > >
> > >
> > > So I wouldn't combine task and cgroup definition together, let's keep
> > > them independent.
> > >
> > > then for cgroup we can do something like:
> > >
> > > struct {
> > >     __u32 order;
> > >     __u32 cgroup_fd; /* cgroup_fd ^ cgroup_id, exactly one can be non-zero */
> > >     __u32 cgroup_id;
> > > } cgroup
> > >
> > > Similar idea with task, but it's a bit more complicated because there
> > > we have target that can be pid, pidfd, or cgroup (cgroup_fd and
> > > cgroup_id). I haven't put much thought into the best representation,
> > > though.
> > >
> >
> > The cgroup part sounds good to me. For the full picture, how about
> > this? I'm just trying  a prototype, hoping that it can help people to
> > get a clear picture.
> >
> > union bpf_iter_link_info {
> >           struct {
> >                   __u32   map_fd;
> >           } map;
> >           struct {
> >                   __u32   order; /* PRE/POST/UP/SELF */
> >                   __u32   cgroup_fd;
> >                   __u64   cgroup_id;
> >           } cgroup;
>
> lgtm
>
> >           struct {
> >                   __u32   pid;
> >                   __u32   pid_fd;
> >                   __u64   cgroup_id;
> >                   __u32   cgroup_fd;
> >                   __u32   mode; /* SELF or others */
>
> I'd move mode to be first. I'm undecided on using 4 separate fields
> for pid/pid_fd/cgroup_{id,fd} vs a single union (or just generic "u64
> target"  and then mode can define how we should treat target --
> whether it's pid, pid_fd, cgroup ID or FD. I'm fine either way, I
> think. But for cgroup case not having to duplicate PRE/POST/UP/SELF
> for cgroup id and then for cgroup fd seems like a win. So separate
> fields might be better. It's also pretty extendable. And I'm
> personally not worried about using few more bytes in bpf_attr for
> disjoin fields like this.
>

Sounds good. Thanks for clarification. Using separate fields looks
good to me. Since we settled on the cgroup part, I will apply update
in cgroup_iter v7.


> >           } task;
> > };
> >
> > > > > > +               __u32   traversal_order;
> > > > > > +       } cgroup;
> > > > > >  };
> > > > > >
> > > > > >  /* BPF syscall commands, see bpf(2) man-page for more details. */
> > > > >
> > > > > [...]

Patch

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index a97751d845c9..9061618fe929 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -47,6 +47,7 @@  struct kobject;
 struct mem_cgroup;
 struct module;
 struct bpf_func_state;
+struct cgroup;
 
 extern struct idr btf_idr;
 extern spinlock_t btf_idr_lock;
@@ -1717,7 +1718,14 @@  int bpf_obj_get_user(const char __user *pathname, int flags);
 	int __init bpf_iter_ ## target(args) { return 0; }
 
 struct bpf_iter_aux_info {
+	/* for map_elem iter */
 	struct bpf_map *map;
+
+	/* for cgroup iter */
+	struct {
+		struct cgroup *start; /* starting cgroup */
+		int order;
+	} cgroup;
 };
 
 typedef int (*bpf_iter_attach_target_t)(struct bpf_prog *prog,
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index ffcbf79a556b..fe50c2489350 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -87,10 +87,30 @@  struct bpf_cgroup_storage_key {
 	__u32	attach_type;		/* program attach type (enum bpf_attach_type) */
 };
 
+enum bpf_iter_cgroup_traversal_order {
+	BPF_ITER_CGROUP_PRE = 0,	/* pre-order traversal */
+	BPF_ITER_CGROUP_POST,		/* post-order traversal */
+	BPF_ITER_CGROUP_PARENT_UP,	/* traversal of ancestors up to the root */
+};
+
 union bpf_iter_link_info {
 	struct {
 		__u32	map_fd;
 	} map;
+
+	/* cgroup_iter walks either the live descendants of a cgroup subtree, or the
+	 * ancestors of a given cgroup.
+	 */
+	struct {
+		/* Cgroup file descriptor. This is root of the subtree if walking
+		 * descendants; it's the starting cgroup if walking the ancestors.
+		 * If it is left 0, the traversal starts from the default cgroup v2
+		 * root. For walking v1 hierarchy, one should always explicitly
+		 * specify the cgroup_fd.
+		 */
+		__u32	cgroup_fd;
+		__u32	traversal_order;
+	} cgroup;
 };
 
 /* BPF syscall commands, see bpf(2) man-page for more details. */
@@ -6136,6 +6156,16 @@  struct bpf_link_info {
 					__u32 map_id;
 				} map;
 			};
+			union {
+				struct {
+					__u64 cgroup_id;
+					__u32 traversal_order;
+				} cgroup;
+			};
+			/* For new iters, if the first field is larger than __u32,
+			 * the struct should be added in the second union. Otherwise,
+			 * it will create holes before map_id, breaking uapi.
+			 */
 		} iter;
 		struct  {
 			__u32 netns_ino;
diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
index 057ba8e01e70..00e05b69a4df 100644
--- a/kernel/bpf/Makefile
+++ b/kernel/bpf/Makefile
@@ -24,6 +24,9 @@  endif
 ifeq ($(CONFIG_PERF_EVENTS),y)
 obj-$(CONFIG_BPF_SYSCALL) += stackmap.o
 endif
+ifeq ($(CONFIG_CGROUPS),y)
+obj-$(CONFIG_BPF_SYSCALL) += cgroup_iter.o
+endif
 obj-$(CONFIG_CGROUP_BPF) += cgroup.o
 ifeq ($(CONFIG_INET),y)
 obj-$(CONFIG_BPF_SYSCALL) += reuseport_array.o
diff --git a/kernel/bpf/cgroup_iter.c b/kernel/bpf/cgroup_iter.c
new file mode 100644
index 000000000000..1027faed0b8b
--- /dev/null
+++ b/kernel/bpf/cgroup_iter.c
@@ -0,0 +1,252 @@ 
+// SPDX-License-Identifier: GPL-2.0-only
+/* Copyright (c) 2022 Google */
+#include <linux/bpf.h>
+#include <linux/btf_ids.h>
+#include <linux/cgroup.h>
+#include <linux/kernel.h>
+#include <linux/seq_file.h>
+
+#include "../cgroup/cgroup-internal.h"  /* cgroup_mutex and cgroup_is_dead */
+
+/* cgroup_iter provides three 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.
+ *  2. Walk the ancestors of a 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
+ * the root.
+ *
+ * The iter program can terminate the walk early by returning 1. Walk
+ * continues if prog returns 0.
+ *
+ * The prog can check (seq->num == 0) to determine whether this is
+ * the first element. The prog may also be passed a NULL cgroup,
+ * which means the walk has completed and the prog has a chance to
+ * do post-processing, such as outputing an epilogue.
+ *
+ * Note: the iter_prog is called with cgroup_mutex held.
+ *
+ * Currently only one session is supported, which means, depending on the
+ * volume of data bpf program intends to send to user space, the number
+ * of cgroups that can be walked is limited. For example, given the current
+ * buffer size is 8 * PAGE_SIZE, if the program sends 64B data for each
+ * cgroup, the total number of cgroups that can be walked is 512. This is
+ * a limitation of cgroup_iter. If the output data is larger than the
+ * buffer size, the second read() will signal EOPNOTSUPP. In order to work
+ * around, the user may have to update their program to reduce the volume
+ * of data sent to output. For example, skip some uninteresting cgroups.
+ */
+
+struct bpf_iter__cgroup {
+	__bpf_md_ptr(struct bpf_iter_meta *, meta);
+	__bpf_md_ptr(struct cgroup *, cgroup);
+};
+
+struct cgroup_iter_priv {
+	struct cgroup_subsys_state *start_css;
+	bool terminate;
+	int order;
+};
+
+static void *cgroup_iter_seq_start(struct seq_file *seq, loff_t *pos)
+{
+	struct cgroup_iter_priv *p = seq->private;
+
+	mutex_lock(&cgroup_mutex);
+
+	/* cgroup_iter doesn't support read across multiple sessions. */
+	if (*pos > 0)
+		return ERR_PTR(-EOPNOTSUPP);
+
+	++*pos;
+	p->terminate = false;
+	if (p->order == BPF_ITER_CGROUP_PRE)
+		return css_next_descendant_pre(NULL, p->start_css);
+	else if (p->order == BPF_ITER_CGROUP_POST)
+		return css_next_descendant_post(NULL, p->start_css);
+	else /* BPF_ITER_CGROUP_PARENT_UP */
+		return p->start_css;
+}
+
+static int __cgroup_iter_seq_show(struct seq_file *seq,
+				  struct cgroup_subsys_state *css, int in_stop);
+
+static void cgroup_iter_seq_stop(struct seq_file *seq, void *v)
+{
+	/* pass NULL to the prog for post-processing */
+	if (!v)
+		__cgroup_iter_seq_show(seq, NULL, true);
+	mutex_unlock(&cgroup_mutex);
+}
+
+static void *cgroup_iter_seq_next(struct seq_file *seq, void *v, loff_t *pos)
+{
+	struct cgroup_subsys_state *curr = (struct cgroup_subsys_state *)v;
+	struct cgroup_iter_priv *p = seq->private;
+
+	++*pos;
+	if (p->terminate)
+		return NULL;
+
+	if (p->order == BPF_ITER_CGROUP_PRE)
+		return css_next_descendant_pre(curr, p->start_css);
+	else if (p->order == BPF_ITER_CGROUP_POST)
+		return css_next_descendant_post(curr, p->start_css);
+	else
+		return curr->parent;
+}
+
+static int __cgroup_iter_seq_show(struct seq_file *seq,
+				  struct cgroup_subsys_state *css, int in_stop)
+{
+	struct cgroup_iter_priv *p = seq->private;
+	struct bpf_iter__cgroup ctx;
+	struct bpf_iter_meta meta;
+	struct bpf_prog *prog;
+	int ret = 0;
+
+	/* cgroup is dead, skip this element */
+	if (css && cgroup_is_dead(css->cgroup))
+		return 0;
+
+	ctx.meta = &meta;
+	ctx.cgroup = css ? css->cgroup : NULL;
+	meta.seq = seq;
+	prog = bpf_iter_get_info(&meta, in_stop);
+	if (prog)
+		ret = bpf_iter_run_prog(prog, &ctx);
+
+	/* if prog returns > 0, terminate after this element. */
+	if (ret != 0)
+		p->terminate = true;
+
+	return 0;
+}
+
+static int cgroup_iter_seq_show(struct seq_file *seq, void *v)
+{
+	return __cgroup_iter_seq_show(seq, (struct cgroup_subsys_state *)v,
+				      false);
+}
+
+static const struct seq_operations cgroup_iter_seq_ops = {
+	.start  = cgroup_iter_seq_start,
+	.next   = cgroup_iter_seq_next,
+	.stop   = cgroup_iter_seq_stop,
+	.show   = cgroup_iter_seq_show,
+};
+
+BTF_ID_LIST_SINGLE(bpf_cgroup_btf_id, struct, cgroup)
+
+static int cgroup_iter_seq_init(void *priv, struct bpf_iter_aux_info *aux)
+{
+	struct cgroup_iter_priv *p = (struct cgroup_iter_priv *)priv;
+	struct cgroup *cgrp = aux->cgroup.start;
+
+	p->start_css = &cgrp->self;
+	p->terminate = false;
+	p->order = aux->cgroup.order;
+	return 0;
+}
+
+static const struct bpf_iter_seq_info cgroup_iter_seq_info = {
+	.seq_ops                = &cgroup_iter_seq_ops,
+	.init_seq_private       = cgroup_iter_seq_init,
+	.seq_priv_size          = sizeof(struct cgroup_iter_priv),
+};
+
+static int bpf_iter_attach_cgroup(struct bpf_prog *prog,
+				  union bpf_iter_link_info *linfo,
+				  struct bpf_iter_aux_info *aux)
+{
+	int fd = linfo->cgroup.cgroup_fd;
+	int order = linfo->cgroup.traversal_order;
+	struct cgroup *cgrp;
+
+	if (order != BPF_ITER_CGROUP_PRE &&
+	    order != BPF_ITER_CGROUP_POST &&
+	    order != BPF_ITER_CGROUP_PARENT_UP)
+		return -EINVAL;
+
+	if (fd)
+		cgrp = cgroup_get_from_fd(fd);
+	else /* walk the entire hierarchy by default. */
+		cgrp = cgroup_get_from_path("/");
+
+	if (IS_ERR(cgrp))
+		return PTR_ERR(cgrp);
+
+	aux->cgroup.start = cgrp;
+	aux->cgroup.order = order;
+	return 0;
+}
+
+static void bpf_iter_detach_cgroup(struct bpf_iter_aux_info *aux)
+{
+	cgroup_put(aux->cgroup.start);
+}
+
+static void bpf_iter_cgroup_show_fdinfo(const struct bpf_iter_aux_info *aux,
+					struct seq_file *seq)
+{
+	char *buf;
+
+	buf = kzalloc(PATH_MAX, GFP_KERNEL);
+	if (!buf) {
+		seq_puts(seq, "cgroup_path:\t<unknown>\n");
+		goto show_order;
+	}
+
+	/* If cgroup_path_ns() fails, buf will be an empty string, cgroup_path
+	 * will print nothing.
+	 *
+	 * Path is in the calling process's cgroup namespace.
+	 */
+	cgroup_path_ns(aux->cgroup.start, buf, PATH_MAX,
+		       current->nsproxy->cgroup_ns);
+	seq_printf(seq, "cgroup_path:\t%s\n", buf);
+	kfree(buf);
+
+show_order:
+	if (aux->cgroup.order == BPF_ITER_CGROUP_PRE)
+		seq_puts(seq, "traversal_order: pre\n");
+	else if (aux->cgroup.order == BPF_ITER_CGROUP_POST)
+		seq_puts(seq, "traversal_order: post\n");
+	else /* BPF_ITER_CGROUP_PARENT_UP */
+		seq_puts(seq, "traversal_order: parent_up\n");
+}
+
+static int bpf_iter_cgroup_fill_link_info(const struct bpf_iter_aux_info *aux,
+					  struct bpf_link_info *info)
+{
+	info->iter.cgroup.traversal_order = aux->cgroup.order;
+	info->iter.cgroup.cgroup_id = cgroup_id(aux->cgroup.start);
+	return 0;
+}
+
+DEFINE_BPF_ITER_FUNC(cgroup, struct bpf_iter_meta *meta,
+		     struct cgroup *cgroup)
+
+static struct bpf_iter_reg bpf_cgroup_reg_info = {
+	.target			= "cgroup",
+	.attach_target		= bpf_iter_attach_cgroup,
+	.detach_target		= bpf_iter_detach_cgroup,
+	.show_fdinfo		= bpf_iter_cgroup_show_fdinfo,
+	.fill_link_info		= bpf_iter_cgroup_fill_link_info,
+	.ctx_arg_info_size	= 1,
+	.ctx_arg_info		= {
+		{ offsetof(struct bpf_iter__cgroup, cgroup),
+		  PTR_TO_BTF_ID_OR_NULL },
+	},
+	.seq_info		= &cgroup_iter_seq_info,
+};
+
+static int __init bpf_cgroup_iter_init(void)
+{
+	bpf_cgroup_reg_info.ctx_arg_info[0].btf_id = bpf_cgroup_btf_id[0];
+	return bpf_iter_reg_target(&bpf_cgroup_reg_info);
+}
+
+late_initcall(bpf_cgroup_iter_init);
diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index ffcbf79a556b..fe50c2489350 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h
@@ -87,10 +87,30 @@  struct bpf_cgroup_storage_key {
 	__u32	attach_type;		/* program attach type (enum bpf_attach_type) */
 };
 
+enum bpf_iter_cgroup_traversal_order {
+	BPF_ITER_CGROUP_PRE = 0,	/* pre-order traversal */
+	BPF_ITER_CGROUP_POST,		/* post-order traversal */
+	BPF_ITER_CGROUP_PARENT_UP,	/* traversal of ancestors up to the root */
+};
+
 union bpf_iter_link_info {
 	struct {
 		__u32	map_fd;
 	} map;
+
+	/* cgroup_iter walks either the live descendants of a cgroup subtree, or the
+	 * ancestors of a given cgroup.
+	 */
+	struct {
+		/* Cgroup file descriptor. This is root of the subtree if walking
+		 * descendants; it's the starting cgroup if walking the ancestors.
+		 * If it is left 0, the traversal starts from the default cgroup v2
+		 * root. For walking v1 hierarchy, one should always explicitly
+		 * specify the cgroup_fd.
+		 */
+		__u32	cgroup_fd;
+		__u32	traversal_order;
+	} cgroup;
 };
 
 /* BPF syscall commands, see bpf(2) man-page for more details. */
@@ -6136,6 +6156,16 @@  struct bpf_link_info {
 					__u32 map_id;
 				} map;
 			};
+			union {
+				struct {
+					__u64 cgroup_id;
+					__u32 traversal_order;
+				} cgroup;
+			};
+			/* For new iters, if the first field is larger than __u32,
+			 * the struct should be added in the second union. Otherwise,
+			 * it will create holes before map_id, breaking uapi.
+			 */
 		} iter;
 		struct  {
 			__u32 netns_ino;
diff --git a/tools/testing/selftests/bpf/prog_tests/btf_dump.c b/tools/testing/selftests/bpf/prog_tests/btf_dump.c
index 5fce7008d1ff..604a40777cfa 100644
--- a/tools/testing/selftests/bpf/prog_tests/btf_dump.c
+++ b/tools/testing/selftests/bpf/prog_tests/btf_dump.c
@@ -764,8 +764,8 @@  static void test_btf_dump_struct_data(struct btf *btf, struct btf_dump *d,
 
 	/* union with nested struct */
 	TEST_BTF_DUMP_DATA(btf, d, "union", str, union bpf_iter_link_info, BTF_F_COMPACT,
-			   "(union bpf_iter_link_info){.map = (struct){.map_fd = (__u32)1,},}",
-			   { .map = { .map_fd = 1 }});
+			   "(union bpf_iter_link_info){.map = (struct){.map_fd = (__u32)1,},.cgroup = (struct){.cgroup_fd = (__u32)1,.traversal_order = (__u32)1,},}",
+			   { .cgroup = { .cgroup_fd = 1, .traversal_order = 1, }});
 
 	/* struct skb with nested structs/unions; because type output is so
 	 * complex, we don't do a string comparison, just verify we return