Re: [PATCH bpf-next v2 2/6] bpf: Implement cgroup storage available to non-cgroup-attached bpf progs

Yonghong Song
2022-10-21T17:34:21Z

On 10/20/22 10:22 PM, David Vernet wrote:
> On Thu, Oct 20, 2022 at 03:13:06PM -0700, Yonghong Song wrote:
>> Similar to sk/inode/task storage, implement similar cgroup local storage.
>>
>> There already exists a local storage implementation for cgroup-attached
>> bpf programs. See map type BPF_MAP_TYPE_CGROUP_STORAGE and helper
>> bpf_get_local_storage(). But there are use cases such that non-cgroup
>> attached bpf progs wants to access cgroup local storage data. For example,
>> tc egress prog has access to sk and cgroup. It is possible to use
>> sk local storage to emulate cgroup local storage by storing data in socket.
>> But this is a waste as it could be lots of sockets belonging to a particular
>> cgroup. Alternatively, a separate map can be created with cgroup id as the key.
>> But this will introduce additional overhead to manipulate the new map.
>> A cgroup local storage, similar to existing sk/inode/task storage,
>> should help for this use case.
>>
>> The life-cycle of storage is managed with the life-cycle of the
>> cgroup struct. i.e. the storage is destroyed along with the owning cgroup
>> with a callback to the bpf_cgrp_storage_free when cgroup itself
>> is deleted.
>>
>> The userspace map operations can be done by using a cgroup fd as a key
>> passed to the lookup, update and delete operations.
>>
>> Typically, the following code is used to get the current cgroup:
>> struct task_struct *task = bpf_get_current_task_btf();
>> ... task->cgroups->dfl_cgrp ...
>> and in structure task_struct definition:
>> struct task_struct {
>> ....
>> struct css_set __rcu *cgroups;
>> ....
>> }
>> With sleepable program, accessing task->cgroups is not protected by rcu_read_lock.
>> So the current implementation only supports non-sleepable program and supporting
>> sleepable program will be the next step together with adding rcu_read_lock
>> protection for rcu tagged structures.
>>
>> Since map name BPF_MAP_TYPE_CGROUP_STORAGE has been used for old cgroup local
>> storage support, the new map name BPF_MAP_TYPE_CGRP_STORAGE is used
>> for cgroup storage available to non-cgroup-attached bpf programs. The old
>> cgroup storage supports bpf_get_local_storage() helper to get the cgroup data.
>> The new cgroup storage helper bpf_cgrp_storage_get() can provide similar
>> functionality. While old cgroup storage pre-allocates storage memory, the new
>> mechanism can also pre-allocate with a user space bpf_map_update_elem() call
>> to avoid potential run-time memory allocaiton failure.
>
> s/allocaiton/allocation

ack.

>
>> Therefore, the new cgroup storage can provide all functionality w.r.t.
>> the old one. So in uapi bpf.h, the old BPF_MAP_TYPE_CGROUP_STORAGE is alias to
>> BPF_MAP_TYPE_CGROUP_STORAGE_DEPRECATED to indicate the old cgroup storage can
>> be deprecated since the new one can provide the same functionality.
>>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
>> ---
>> include/linux/bpf.h | 3 +
>> include/linux/bpf_types.h | 1 +
>> include/linux/cgroup-defs.h | 4 +
>> include/uapi/linux/bpf.h | 48 +++++-
>> kernel/bpf/Makefile | 2 +-
>> kernel/bpf/bpf_cgrp_storage.c | 276 +++++++++++++++++++++++++++++++++
>> kernel/bpf/helpers.c | 6 +
>> kernel/bpf/syscall.c | 3 +-
>> kernel/bpf/verifier.c | 13 +-
>> kernel/cgroup/cgroup.c | 4 +
>> kernel/trace/bpf_trace.c | 4 +
>> scripts/bpf_doc.py | 2 +
>> tools/include/uapi/linux/bpf.h | 48 +++++-
>> 13 files changed, 409 insertions(+), 5 deletions(-)
>> create mode 100644 kernel/bpf/bpf_cgrp_storage.c
>>
>> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
>> index 9e7d46d16032..674da3129248 100644
>> --- a/include/linux/bpf.h
>> +++ b/include/linux/bpf.h
>> @@ -2045,6 +2045,7 @@ struct bpf_link *bpf_link_by_id(u32 id);
>>
>> const struct bpf_func_proto *bpf_base_func_proto(enum bpf_func_id func_id);
>> void bpf_task_storage_free(struct task_struct *task);
>> +void bpf_cgrp_storage_free(struct cgroup *cgroup);
>> bool bpf_prog_has_kfunc_call(const struct bpf_prog *prog);
>> const struct btf_func_model *
>> bpf_jit_find_kfunc_model(const struct bpf_prog *prog,
>> @@ -2537,6 +2538,8 @@ extern const struct bpf_func_proto bpf_copy_from_user_task_proto;
>> extern const struct bpf_func_proto bpf_set_retval_proto;
>> extern const struct bpf_func_proto bpf_get_retval_proto;
>> extern const struct bpf_func_proto bpf_user_ringbuf_drain_proto;
>> +extern const struct bpf_func_proto bpf_cgrp_storage_get_proto;
>> +extern const struct bpf_func_proto bpf_cgrp_storage_delete_proto;
>>
>> const struct bpf_func_proto *tracing_prog_func_proto(
>> enum bpf_func_id func_id, const struct bpf_prog *prog);
>> diff --git a/include/linux/bpf_types.h b/include/linux/bpf_types.h
>> index 2c6a4f2562a7..f9d5aa62fed0 100644
>> --- a/include/linux/bpf_types.h
>> +++ b/include/linux/bpf_types.h
>> @@ -90,6 +90,7 @@ BPF_MAP_TYPE(BPF_MAP_TYPE_CGROUP_ARRAY, cgroup_array_map_ops)
>> #ifdef CONFIG_CGROUP_BPF
>> BPF_MAP_TYPE(BPF_MAP_TYPE_CGROUP_STORAGE, cgroup_storage_map_ops)
>> BPF_MAP_TYPE(BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE, cgroup_storage_map_ops)
>> +BPF_MAP_TYPE(BPF_MAP_TYPE_CGRP_STORAGE, cgrp_storage_map_ops)
>> #endif
>> BPF_MAP_TYPE(BPF_MAP_TYPE_HASH, htab_map_ops)
>> BPF_MAP_TYPE(BPF_MAP_TYPE_PERCPU_HASH, htab_percpu_map_ops)
>> diff --git a/include/linux/cgroup-defs.h b/include/linux/cgroup-defs.h
>> index 8f481d1b159a..4a72bc3a0a4e 100644
>> --- a/include/linux/cgroup-defs.h
>> +++ b/include/linux/cgroup-defs.h
>> @@ -504,6 +504,10 @@ struct cgroup {
>> /* Used to store internal freezer state */
>> struct cgroup_freezer_state freezer;
>>
>> +#ifdef CONFIG_CGROUP_BPF
>> + struct bpf_local_storage __rcu *bpf_cgrp_storage;
>> +#endif
>> +
>> /* All ancestors including self */
>> struct cgroup *ancestors[];
>> };
>> diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
>> index 17f61338f8f8..2d7f79bf3500 100644
>> --- a/include/uapi/linux/bpf.h
>> +++ b/include/uapi/linux/bpf.h
>> @@ -922,7 +922,14 @@ enum bpf_map_type {
>> BPF_MAP_TYPE_CPUMAP,
>> BPF_MAP_TYPE_XSKMAP,
>> BPF_MAP_TYPE_SOCKHASH,
>> - BPF_MAP_TYPE_CGROUP_STORAGE,
>> + BPF_MAP_TYPE_CGROUP_STORAGE_DEPRECATED,
>> + /* BPF_MAP_TYPE_CGROUP_STORAGE is available to bpf programs attaching
>> + * to a cgroup. The newer BPF_MAP_TYPE_CGRP_STORAGE is available to
>> + * both cgroup-attached and other progs and supports all functionality
>> + * provided by BPF_MAP_TYPE_CGROUP_STORAGE. So mark
>> + * BPF_MAP_TYPE_CGROUP_STORAGE deprecated.
>> + */
>> + BPF_MAP_TYPE_CGROUP_STORAGE = BPF_MAP_TYPE_CGROUP_STORAGE_DEPRECATED,
>> BPF_MAP_TYPE_REUSEPORT_SOCKARRAY,
>> BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE,
>> BPF_MAP_TYPE_QUEUE,
>> @@ -935,6 +942,7 @@ enum bpf_map_type {
>> BPF_MAP_TYPE_TASK_STORAGE,
>> BPF_MAP_TYPE_BLOOM_FILTER,
>> BPF_MAP_TYPE_USER_RINGBUF,
>> + BPF_MAP_TYPE_CGRP_STORAGE,
>> };
>>
>> /* Note that tracing related programs such as
>> @@ -5435,6 +5443,42 @@ union bpf_attr {
>> * **-E2BIG** if user-space has tried to publish a sample which is
>> * larger than the size of the ring buffer, or which cannot fit
>> * within a struct bpf_dynptr.
>> + *
>> + * void *bpf_cgrp_storage_get(struct bpf_map *map, struct cgroup *cgroup, void *value, u64 flags)
>> + * Description
>> + * Get a bpf_local_storage from the *cgroup*.
>> + *
>> + * Logically, it could be thought of as getting the value from
>> + * a *map* with *cgroup* as the **key**. From this
>> + * perspective, the usage is not much different from
>> + * **bpf_map_lookup_elem**\ (*map*, **&**\ *cgroup*) except this
>> + * helper enforces the key must be a cgroup struct and the map must also
>> + * be a **BPF_MAP_TYPE_CGRP_STORAGE**.
>> + *
>> + * Underneath, the value is stored locally at *cgroup* instead of
>> + * the *map*. The *map* is used as the bpf-local-storage
>> + * "type". The bpf-local-storage "type" (i.e. the *map*) is
>> + * searched against all bpf_local_storage residing at *cgroup*.
>
> IMO this paragraph is a bit hard to parse. Please correct me if I'm
> wrong, but I think what it's trying to convey is that when an instance
> of cgroup bpf-local-storage is accessed by a program in e.g.
> bpf_cgrp_storage_get(), all of the cgroup bpf_local_storage entries are
> iterated over in the struct cgroup object until this program's local
> storage instance is found. Is that right? If so, perhaps something like
> this would be more clear:

yes. your above interpretation is correct.

>
> In reality, the local-storage value is embedded directly inside of the
> *cgroup* object itself, rather than being located in the
> **BPF_MAP_TYPE_CGRP_STORAGE** map. When the local-storage value is
> queried for some *map* on a *cgroup* object, the kernel will perform an
> O(n) iteration over all of the live local-storage values for that
> *cgroup* object until the local-storage value for the *map* is found.

Sounds okay. I can change the explanation like the above.

>
> What do you think?
>
>> + * An optional *flags* (**BPF_LOCAL_STORAGE_GET_F_CREATE**) can be
>> + * used such that a new bpf_local_storage will be
>> + * created if one does not exist. *value* can be used
>> + * together with **BPF_LOCAL_STORAGE_GET_F_CREATE** to specify
>> + * the initial value of a bpf_local_storage. If *value* is
>> + * **NULL**, the new bpf_local_storage will be zero initialized.
>> + * Return
>> + * A bpf_local_storage pointer is returned on success.
>> + *
>> + * **NULL** if not found or there was an error in adding
>> + * a new bpf_local_storage.
>> + *
>> + * long bpf_cgrp_storage_delete(struct bpf_map *map, struct cgroup *cgroup)
>> + * Description
>> + * Delete a bpf_local_storage from a *cgroup*.
>> + * Return
>> + * 0 on success.
>> + *
>> + * **-ENOENT** if the bpf_local_storage cannot be found.
>> */
>> #define ___BPF_FUNC_MAPPER(FN, ctx...) \
>> FN(unspec, 0, ##ctx) \
>> @@ -5647,6 +5691,8 @@ union bpf_attr {
>> FN(tcp_raw_check_syncookie_ipv6, 207, ##ctx) \
>> FN(ktime_get_tai_ns, 208, ##ctx) \
>> FN(user_ringbuf_drain, 209, ##ctx) \
>> + FN(cgrp_storage_get, 210, ##ctx) \
>> + FN(cgrp_storage_delete, 211, ##ctx) \
>> /* */
>>
>> /* backwards-compatibility macros for users of __BPF_FUNC_MAPPER that don't
>> diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
>> index 341c94f208f4..3a12e6b400a2 100644
>> --- a/kernel/bpf/Makefile
>> +++ b/kernel/bpf/Makefile
>> @@ -25,7 +25,7 @@ ifeq ($(CONFIG_PERF_EVENTS),y)
>> obj-$(CONFIG_BPF_SYSCALL) += stackmap.o
>> endif
>> ifeq ($(CONFIG_CGROUPS),y)
>
> I assume that you double checked that it's valid to compile the helper
> with CONFIG_CGROUPS && !CONFIG_CGROUP_BPF, but I must admit that even if
> that's the case, I'm not following why we would want the map to be
> compiled with a different kconfig option than the helper that provides
> access to it. If theres's a precedent for doing this then I suppose it's
> fine, but it does seem wrong and/or at least wasteful to compile these
> helpers in if CONFIG_CGROUPS is defined but CONFIG_CGROUP_BPF is not.

The following is my understanding.
CONFIG_CGROUP_BPF guards kernel/bpf/cgroup.c which contains
implementation mostly for cgroup-attached program types, helpers, etc.

A lot of other cgroup-related implementation like cgroup_iter, some
cgroup related helper (not related to cgroup-attached program types),
etc. are guarded with CONFIG_CGROUPS and CONFIG_BPF_SYSCALL.

Note that it is totally possible CONFIG_CGROUP_BPF is 'n' while
CONFIG_CGROUPS and CONFIG_BPF_SYSCALL are 'y'.

So for cgroup local storage implemented in this patch set,
using CONFIG_CGROUPS and CONFIG_BPF_SYSCALL seems okay.

>
>> -obj-$(CONFIG_BPF_SYSCALL) += cgroup_iter.o
>> +obj-$(CONFIG_BPF_SYSCALL) += cgroup_iter.o bpf_cgrp_storage.o
>> endif
>> obj-$(CONFIG_CGROUP_BPF) += cgroup.o
>> ifeq ($(CONFIG_INET),y)
>> diff --git a/kernel/bpf/bpf_cgrp_storage.c b/kernel/bpf/bpf_cgrp_storage.c
>> new file mode 100644
>> index 000000000000..bcc5f0fc20be
>> --- /dev/null
>> +++ b/kernel/bpf/bpf_cgrp_storage.c
>> @@ -0,0 +1,276 @@
>> +// SPDX-License-Identifier: GPL-2.0
>> +/*
>> + * Copyright (c) 2022 Meta Platforms, Inc. and affiliates.
>> + */
>> +
>> +#include <linux/types.h>
>> +#include <linux/bpf.h>
>> +#include <linux/bpf_local_storage.h>
>> +#include <uapi/linux/btf.h>
>> +#include <linux/btf_ids.h>
>> +
>> +DEFINE_BPF_STORAGE_CACHE(cgroup_cache);
>> +
>> +static DEFINE_PER_CPU(int, bpf_cgrp_storage_busy);
>> +
>> +static void bpf_cgrp_storage_lock(void)
>> +{
>> + migrate_disable();
>> + this_cpu_inc(bpf_cgrp_storage_busy);
>> +}
>> +
>> +static void bpf_cgrp_storage_unlock(void)
>> +{
>> + this_cpu_dec(bpf_cgrp_storage_busy);
>> + migrate_enable();
>> +}
>> +
>> +static bool bpf_cgrp_storage_trylock(void)
>> +{
>> + migrate_disable();
>> + if (unlikely(this_cpu_inc_return(bpf_cgrp_storage_busy) != 1)) {
>> + this_cpu_dec(bpf_cgrp_storage_busy);
>> + migrate_enable();
>> + return false;
>> + }
>> + return true;
>> +}
>> +
>> +static struct bpf_local_storage __rcu **cgroup_storage_ptr(void *owner)
>> +{
>> + struct cgroup *cg = owner;
>> +
>> + return &cg->bpf_cgrp_storage;
>> +}
>> +
>> +void bpf_cgrp_storage_free(struct cgroup *cgroup)
>> +{
>> + struct bpf_local_storage *local_storage;
>> + struct bpf_local_storage_elem *selem;
>> + bool free_cgroup_storage = false;
>> + struct hlist_node *n;
>> + unsigned long flags;
>> +
>> + rcu_read_lock();
>> + local_storage = rcu_dereference(cgroup->bpf_cgrp_storage);
>> + if (!local_storage) {
>> + rcu_read_unlock();
>> + return;
>> + }
>> +
>> + /* Neither the bpf_prog nor the bpf-map's syscall
>
> Very minor nit, but I think using a hyphen in bpf-map like this is
> incorrect as it's not a compound adjective. Applies elsewhere as well. I
> don't believe "added-to" or "deleted-from" require hyphens either.

ack.

>
>> + * could be modifying the local_storage->list now.
>> + * Thus, no elem can be added-to or deleted-from the
>> + * local_storage->list by the bpf_prog or by the bpf-map's syscall.
>> + *
>> + * It is racing with bpf_local_storage_map_free() alone
>> + * when unlinking elem from the local_storage->list and
>> + * the map's bucket->list.
>> + */
>> + bpf_cgrp_storage_lock();
>> + raw_spin_lock_irqsave(&local_storage->lock, flags);
>> + hlist_for_each_entry_safe(selem, n, &local_storage->list, snode) {
>> + bpf_selem_unlink_map(selem);
>> + free_cgroup_storage =
>> + bpf_selem_unlink_storage_nolock(local_storage, selem, false, false);
>
> This still requires a comment explaining why it's OK to overwrite
> free_cgroup_storage with a previous value from calling
> bpf_selem_unlink_storage_nolock(). Even if that is safe, this looks like
> a pretty weird programming pattern, and IMO doing this feels more
> intentional and future-proof:
>
> if (bpf_selem_unlink_storage_nolock(local_storage, selem, false, false))
> free_cgroup_storage = true;

We have a comment a few lines below.
/* free_cgroup_storage should always be true as long as
* local_storage->list was non-empty.
*/
if (free_cgroup_storage)
kfree_rcu(local_storage, rcu);

I will add more explanation in the above code like

bpf_selem_unlink_map(selem);
/* If local_storage list only have one element, the
* bpf_selem_unlink_storage_nolock() will return true.
* Otherwise, it will return false. The current loop iteration
* intends to remove all local storage. So the last iteration
* of the loop will set the free_cgroup_storage to true.
*/
free_cgroup_storage =
bpf_selem_unlink_storage_nolock(local_storage, selem, false, false);

>
>> + }
>> + raw_spin_unlock_irqrestore(&local_storage->lock, flags);
>> + bpf_cgrp_storage_unlock();
>> + rcu_read_unlock();
>> +
>> + /* free_cgroup_storage should always be true as long as
>> + * local_storage->list was non-empty.
>> + */
>> + if (free_cgroup_storage)
>> + kfree_rcu(local_storage, rcu);
>> +}
>> +
>> +static struct bpf_local_storage_data *
>> +cgroup_storage_lookup(struct cgroup *cgroup, struct bpf_map *map, bool cacheit_lockit)
>> +{
>> + struct bpf_local_storage *cgroup_storage;
>> + struct bpf_local_storage_map *smap;
>> +
>> + cgroup_storage = rcu_dereference_check(cgroup->bpf_cgrp_storage,
>> + bpf_rcu_lock_held());
>> + if (!cgroup_storage)
>> + return NULL;
>> +
>> + smap = (struct bpf_local_storage_map *)map;
>> + return bpf_local_storage_lookup(cgroup_storage, smap, cacheit_lockit);
>> +}
>> +
>> +static void *bpf_cgrp_storage_lookup_elem(struct bpf_map *map, void *key)
>> +{
>> + struct bpf_local_storage_data *sdata;
>> + struct cgroup *cgroup;
>> + int fd;
>> +
>> + fd = *(int *)key;
>> + cgroup = cgroup_get_from_fd(fd);
>> + if (IS_ERR(cgroup))
>> + return ERR_CAST(cgroup);
>> +
>> + bpf_cgrp_storage_lock();
>> + sdata = cgroup_storage_lookup(cgroup, map, true);
>> + bpf_cgrp_storage_unlock();
>> + cgroup_put(cgroup);
>> + return sdata ? sdata->data : NULL;
>> +}
>
> Stanislav pointed out in the v1 revision that there's a lot of very
> similar logic in task storage, and I think you'd mentioned that you were
> going to think about generalizing some of that. Have you had a chance to
> consider?

It is hard to have a common function for
lookup_elem/update_elem/delete_elem(). They are quite different as each
heavily involves
task/cgroup-specific functions.

but map_alloc and map_free could have common helpers.

>
>> +static int bpf_cgrp_storage_update_elem(struct bpf_map *map, void *key,
>> + void *value, u64 map_flags)
>> +{
>> + struct bpf_local_storage_data *sdata;
>> + struct cgroup *cgroup;
>> + int fd;
>> +
>> + fd = *(int *)key;
>> + cgroup = cgroup_get_from_fd(fd);
>> + if (IS_ERR(cgroup))
>> + return PTR_ERR(cgroup);
>> +
>> + bpf_cgrp_storage_lock();
>> + sdata = bpf_local_storage_update(cgroup, (struct bpf_local_storage_map *)map,
>> + value, map_flags, GFP_ATOMIC);
>> + bpf_cgrp_storage_unlock();
>> + cgroup_put(cgroup);
>> + return PTR_ERR_OR_ZERO(sdata);
>> +}
>> +
>> +static int cgroup_storage_delete(struct cgroup *cgroup, struct bpf_map *map)
>> +{
>> + struct bpf_local_storage_data *sdata;
>> +
>> + sdata = cgroup_storage_lookup(cgroup, map, false);
>> + if (!sdata)
>> + return -ENOENT;
>> +
>> + bpf_selem_unlink(SELEM(sdata), true);
>> + return 0;
>> +}
>> +
>> +static int bpf_cgrp_storage_delete_elem(struct bpf_map *map, void *key)
>> +{
>> + struct cgroup *cgroup;
>> + int err, fd;
>> +
>> + fd = *(int *)key;
>> + cgroup = cgroup_get_from_fd(fd);
>> + if (IS_ERR(cgroup))
>> + return PTR_ERR(cgroup);
>> +
>> + bpf_cgrp_storage_lock();
>> + err = cgroup_storage_delete(cgroup, map);
>> + bpf_cgrp_storage_unlock();
>> + cgroup_put(cgroup);
>> + return err;
>> +}
>> +
>> +static int notsupp_get_next_key(struct bpf_map *map, void *key, void *next_key)
>> +{
>> + return -ENOTSUPP;
>> +}
>> +
>> +static struct bpf_map *cgroup_storage_map_alloc(union bpf_attr *attr)
>> +{
>> + struct bpf_local_storage_map *smap;
>> +
>> + smap = bpf_local_storage_map_alloc(attr);
>> + if (IS_ERR(smap))
>> + return ERR_CAST(smap);
>> +
>> + smap->cache_idx = bpf_local_storage_cache_idx_get(&cgroup_cache);
>> + return &smap->map;
>> +}
>> +
>> +static void cgroup_storage_map_free(struct bpf_map *map)
>> +{
>> + struct bpf_local_storage_map *smap;
>> +
>> + smap = (struct bpf_local_storage_map *)map;
>> + bpf_local_storage_cache_idx_free(&cgroup_cache, smap->cache_idx);
>> + bpf_local_storage_map_free(smap, NULL);
>> +}
>> + …