From: Martin KaFai Lau <martin.lau@linux.dev>
To: Kui-Feng Lee <kuifeng@meta.com>
Cc: bpf@vger.kernel.org, ast@kernel.org, song@kernel.org,
kernel-team@meta.com, andrii@kernel.org, sdf@google.com
Subject: Re: [PATCH bpf-next v2 1/6] bpf: Create links for BPF struct_ops maps.
Date: Thu, 23 Feb 2023 22:58:33 -0800 [thread overview]
Message-ID: <60634c64-5e16-c3d8-3561-6b88c5b5b1fd@linux.dev> (raw)
In-Reply-To: <20230223011238.12313-2-kuifeng@meta.com>
On 2/22/23 5:12 PM, Kui-Feng Lee wrote:
> +/*
> + * Maintain the state of kvalue.
> + *
> + * For a struct_ops that has no link, its state diagram is
> + *
> + * INIT ----> INUSE --> TOBEFREE
> + * ^ |
> + * | (refcnt == 0) |
> + * +---------------------+
For non BPF_F_LINK case, no need to transit back to INIT from TOBEFREE to
support "re"-update or "re"-register. The userspace can create a new struct_ops
if it needs a different set of bpf prog. The new BPF_F_LINK can be used for
"re"-register. Keep the existing non BPF_F_LINK case as simple as is.
> + *
> + * For a struct_ops that has a link (BPF_F_LINK), its state diagram is
> + *
> + * (refcnt == 0)
> + * +-----------------------+
> + * | |
> + * V |
> + * INIT ---> UNREG -+--> INUSE --> TOBEUNREG
> + * ^ |
> + * | V
> + * +---------- TOBEFREE
> + * (refcnt == 0)
> + *
> + * After transiting to the INUSE state of a struct_ops, the refcnt of
> + * its kvalue is set to 1.
> + *
> + * After transiting from the INUSE state of a struct_ops, the caller
> + * should decrease the refcnt of its kvalue by 1 by calling
> + * bpf_struct_ops_put().
> + *
> + * TOBEFREE and TOBEUNREG are in a grace period, waiting for other
> + * tasks holding references of the struct_ops. When the refcnt drops
> + * from 1 to 0, TOBEFREE and TOBEUNREG are transited to INIT and UNREG
> + * respectively.
> + *
> + * It is safe to assume that there will be no registration race
> + * conditions after a task transits the same struct_ops to INUSE,
> + * TOBEFREE and TOBEUNREG states. The task is able to register or
> + * unregister the struct_ops without the need for any additional
> + * synchronization.
> + */
> +static int bpf_struct_ops_transit_state(struct bpf_struct_ops_map *st_map,
> + enum bpf_struct_ops_state src,
> + enum bpf_struct_ops_state dst)
> +{
I think the state transition that requires a rather long switch case is a good
signal that it needs some simplification. Lets explore how to simplify it.
Hopefully, it could be simple enough that it does not need a dedicated function
to transit state. In particular, for BPF_F_LINK, I think it can stay with three
states:
INIT --> UNREG --> INUSE
^ |
+---------+
TOBEUNREG is a bit confusing. Whenever '->unreg' is called, the unregistration
is done, so it should be UNREG instead of TOBEUNREG. eg. when
tcp_unregister_congestion_control() is called, the unreg is done. The existing
connections may still use it but for the struct_ops concern it is unregistered.
The user space can inspect how many connections are still using it by checking
the kvalue->refcnt.
As long as the struct_ops is in UNREG and the userspace has a hold to the map
fd, the userspace should be able to create a link to register the struct_ops
(may be the very first time or may be again).
The existing TOBEFREE only makes sense to the existing non BPF_F_LINK use case.
Whenever the struct_ops is unregistered (by delete_elem), there is no way to
register again because the registation and update must be done together. The
struct_ops can only wait to be freed after the very last connections finished
using it.
Thus, there is no need to have TOBEFREE for the BPF_F_LINK case. Update and
registration are done separately now.
To simplify it further, I would suggest not to consider the use case that a
struct_ops can be updated (i.e. update_elem) for the second time. Thus, no need
to transit back to INIT. The user can always create a new struct_ops with
another set of bpf progs and do BPF_LINK_UPDATE.
WDYT?
Also, I would suggest not to mix the reg/unreg between the existing non
BPF_F_LINK map and the new BPF_F_LINK map. The new BPF_F_LINK map should only
reg/unreg through BPF_LINK_CREATE, BPF_LINK_DETACH, BPF_LINK_UPDATE and
bpf_link_release(). The new BPF_F_LINK map should not be allowed to unreg
through the old delete_elem() API.
Regarding the locks, the existing code uses the map lock (st_map->lock) to
protect the update_elem(). smp_load_acquire/smp_store_release() and cmpxchg() to
make the lookup_elem and delete_elem lockless. Stan also mentioned similar
points in another thread. It seems some of the new critical sections in this
patch now is under yet another global lock (update_mutex), so some of those
lockless trick may not worth it anymore. However, it is a bit hard to comb
through now. It will be easier to see through how to clean up the lock usage
after simpifying other things first.
> + int old_state;
> +
> + switch (src) {
> + case BPF_STRUCT_OPS_STATE_INIT:
> + if (dst != BPF_STRUCT_OPS_STATE_INUSE &&
> + dst != BPF_STRUCT_OPS_STATE_UNREG)
> + return -EINVAL;
> +
> + old_state = cmpxchg(&st_map->kvalue.state, src, dst);
> + if (old_state != src)
> + break;
> +
> + if (dst == BPF_STRUCT_OPS_STATE_INUSE)
> + refcount_set(&st_map->kvalue.refcnt, 1);
> + break;
> +
> + case BPF_STRUCT_OPS_STATE_UNREG:
> + if (dst != BPF_STRUCT_OPS_STATE_INUSE &&
> + dst != BPF_STRUCT_OPS_STATE_TOBEFREE)
> + return -EINVAL;
> +
> + old_state = cmpxchg(&st_map->kvalue.state, src, dst);
> + if (old_state != src)
> + break;
> +
> + if (dst == BPF_STRUCT_OPS_STATE_INUSE)
> + refcount_set(&st_map->kvalue.refcnt, 1);
> + else if (dst == BPF_STRUCT_OPS_STATE_TOBEFREE)
> + cmpxchg(&st_map->kvalue.state, dst, BPF_STRUCT_OPS_STATE_INIT);
> + break;
> +
> + case BPF_STRUCT_OPS_STATE_INUSE:
> + if (dst != BPF_STRUCT_OPS_STATE_TOBEFREE &&
> + dst != BPF_STRUCT_OPS_STATE_TOBEUNREG)
> + return -EINVAL;
> +
> + old_state = cmpxchg(&st_map->kvalue.state, src, dst);
> + break;
> +
> + case BPF_STRUCT_OPS_STATE_TOBEFREE:
> + /*
> + * This transition should only be performed when the
> + * refcnt drops to 0 from 1.
> + */
> + if (dst != BPF_STRUCT_OPS_STATE_INIT)
> + return -EINVAL;
> + old_state = cmpxchg(&st_map->kvalue.state, src, dst);
> + if (old_state != src)
> + break;
> + break;
> +
> + case BPF_STRUCT_OPS_STATE_TOBEUNREG:
> + /*
> + * This transition should only be performed when the
> + * refcnt drops to 0 from 1.
> + */
> + if (dst != BPF_STRUCT_OPS_STATE_UNREG)
> + return -EINVAL;
> + old_state = cmpxchg(&st_map->kvalue.state, src, dst);
> + if (old_state != src)
> + return old_state;
> + break;
> +
> + default:
> + return -EOPNOTSUPP;
> + }
> +
> + return old_state;
> +}
> +
> +static int bpf_struct_ops_transit_state_check(struct bpf_struct_ops_map *st_map,
> + enum bpf_struct_ops_state src,
> + enum bpf_struct_ops_state dst)
> +{
> + int err;
> +
> + err = bpf_struct_ops_transit_state(st_map, src, dst);
> + if (err < 0)
> + return err;
> + if (err != src)
> + return -EINVAL;
> + return 0;
> +}
> +
> +/*
> + * Restore the state of a struct_ops to UNREG from INUSE.
> + *
> + * It handles the case which a struct_ops transited to INUSE from
> + * UNREG successfully; somehow, need to rollback the struct_ops state.
> + */
> +static void bpf_struct_ops_restore_unreg(struct bpf_struct_ops_map *st_map)
> +{
> + struct bpf_struct_ops_value *kvalue;
> +
> + kvalue = &st_map->kvalue;
> + refcount_set(&kvalue->refcnt, 0);
> + /* Make sure the above change is seen before the state change. */
> + smp_store_release(&kvalue->state, BPF_STRUCT_OPS_STATE_UNREG);
> +}
> +
> static int bpf_struct_ops_map_update_elem(struct bpf_map *map, void *key,
> void *value, u64 flags)
> {
> @@ -390,7 +539,11 @@ static int bpf_struct_ops_map_update_elem(struct bpf_map *map, void *key,
>
> mutex_lock(&st_map->lock);
>
> - if (kvalue->state != BPF_STRUCT_OPS_STATE_INIT) {
> + /* Make sure that all following changes are seen after the
> + * state value here.
> + */
> + if (smp_load_acquire(&kvalue->state) >= BPF_STRUCT_OPS_STATE_INUSE ||
> + refcount_read(&kvalue->refcnt)) {
Only allow a struct_ops map to be updated once. ie. only allow update_elem for
struct_ops in BPF_STRUCT_OPS_STATE_INIT. The user space can create another new
struct_ops and then use BPF_LINK_UPDATE.
> err = -EBUSY;
> goto unlock;
> }
> @@ -491,17 +644,21 @@ static int bpf_struct_ops_map_update_elem(struct bpf_map *map, void *key,
> *(unsigned long *)(udata + moff) = prog->aux->id;
> }
>
> - refcount_set(&kvalue->refcnt, 1);
> + if (st_map->map.map_flags & BPF_F_LINK) {
> + /* Let bpf_link handle registration & unregistration. */
> + err = bpf_struct_ops_transit_state_check(st_map, BPF_STRUCT_OPS_STATE_INIT,
> + BPF_STRUCT_OPS_STATE_UNREG);
> + goto unlock;
> + }
> +
> bpf_map_inc(map);
>
> set_memory_rox((long)st_map->image, 1);
> err = st_ops->reg(kdata);
> if (likely(!err)) {
> - /* Pair with smp_load_acquire() during lookup_elem().
> - * It ensures the above udata updates (e.g. prog->aux->id)
> - * can be seen once BPF_STRUCT_OPS_STATE_INUSE is set.
> - */
> - smp_store_release(&kvalue->state, BPF_STRUCT_OPS_STATE_INUSE);
> + /* Infallible */
> + bpf_struct_ops_transit_state(st_map, BPF_STRUCT_OPS_STATE_INIT,
> + BPF_STRUCT_OPS_STATE_INUSE);
> goto unlock;
> }
>
> @@ -526,28 +683,49 @@ static int bpf_struct_ops_map_update_elem(struct bpf_map *map, void *key,
>
> static int bpf_struct_ops_map_delete_elem(struct bpf_map *map, void *key)
> {
> - enum bpf_struct_ops_state prev_state;
> struct bpf_struct_ops_map *st_map;
> + int old_state;
> + int err = 0;
>
> st_map = (struct bpf_struct_ops_map *)map;
> - prev_state = cmpxchg(&st_map->kvalue.state,
> - BPF_STRUCT_OPS_STATE_INUSE,
> - BPF_STRUCT_OPS_STATE_TOBEFREE);
> - switch (prev_state) {
> +
> + old_state = bpf_struct_ops_transit_state(st_map,
> + (st_map->map.map_flags & BPF_F_LINK ?
I may not have been clear in v1 comment by "return -ENOTSUPP". For BPF_F_LINK
map, it should only be unreg by user space holding the link. It should not be
unreg through delete_elem().
> + BPF_STRUCT_OPS_STATE_UNREG :
> + BPF_STRUCT_OPS_STATE_INUSE),
> + BPF_STRUCT_OPS_STATE_TOBEFREE);
> +
> + if (old_state < 0)
> + return old_state;
> +
> + switch (old_state) {
> + case BPF_STRUCT_OPS_STATE_UNREG:
> + break;
> case BPF_STRUCT_OPS_STATE_INUSE:
> - st_map->st_ops->unreg(&st_map->kvalue.data);
> - if (refcount_dec_and_test(&st_map->kvalue.refcnt))
> - bpf_map_put(map);
> - return 0;
> + if (st_map->map.map_flags & BPF_F_LINK)
> + err = -EBUSY;
> + else {
> + st_map->st_ops->unreg(&st_map->kvalue.data);
> + bpf_struct_ops_put(&st_map->kvalue.data);
> + }
> + break;
> case BPF_STRUCT_OPS_STATE_TOBEFREE:
> - return -EINPROGRESS;
> + err = -EINPROGRESS;
> + break;
> + case BPF_STRUCT_OPS_STATE_TOBEUNREG:
> + err = -EBUSY;
> + break;
> case BPF_STRUCT_OPS_STATE_INIT:
> - return -ENOENT;
> + err = -ENOENT;
> + break;
> default:
> WARN_ON_ONCE(1);
> /* Should never happen. Treat it as not found. */
> - return -ENOENT;
> + err = -ENOENT;
> + break;
> }
> +
> + return err;
> }
>
> static void bpf_struct_ops_map_seq_show_elem(struct bpf_map *map, void *key,
> @@ -585,7 +763,7 @@ static void bpf_struct_ops_map_free(struct bpf_map *map)
> static int bpf_struct_ops_map_alloc_check(union bpf_attr *attr)
> {
> if (attr->key_size != sizeof(unsigned int) || attr->max_entries != 1 ||
> - attr->map_flags || !attr->btf_vmlinux_value_type_id)
> + (attr->map_flags & ~BPF_F_LINK) || !attr->btf_vmlinux_value_type_id)
> return -EINVAL;
> return 0;
> }
> @@ -671,6 +849,15 @@ static void bpf_struct_ops_put_rcu(struct rcu_head *head)
> struct bpf_struct_ops_map *st_map;
>
> st_map = container_of(head, struct bpf_struct_ops_map, rcu);
> +
> + /* The struct_ops can be reused after a rcu grace period. */
> + if (st_map->kvalue.state == BPF_STRUCT_OPS_STATE_TOBEFREE)
> + bpf_struct_ops_transit_state(st_map, BPF_STRUCT_OPS_STATE_TOBEFREE,
> + BPF_STRUCT_OPS_STATE_INIT);
> + else if (st_map->kvalue.state == BPF_STRUCT_OPS_STATE_TOBEUNREG)
> + bpf_struct_ops_transit_state(st_map, BPF_STRUCT_OPS_STATE_TOBEUNREG,
> + BPF_STRUCT_OPS_STATE_UNREG);
> +
> bpf_map_put(&st_map->map);
> }
>
> @@ -684,6 +871,7 @@ void bpf_struct_ops_put(const void *kdata)
>
> st_map = container_of(kvalue, struct bpf_struct_ops_map,
> kvalue);
> +
> /* The struct_ops's function may switch to another struct_ops.
> *
> * For example, bpf_tcp_cc_x->init() may switch to
> @@ -698,3 +886,143 @@ void bpf_struct_ops_put(const void *kdata)
> call_rcu(&st_map->rcu, bpf_struct_ops_put_rcu);
> }
> }
> +
> +static void bpf_struct_ops_map_link_dealloc(struct bpf_link *link)
> +{
> + struct bpf_struct_ops_link *st_link;
> + struct bpf_struct_ops_map *st_map;
> +
> + st_link = container_of(link, struct bpf_struct_ops_link, link);
> + if (st_link->map) {
> + st_map = (struct bpf_struct_ops_map *)st_link->map;
> + bpf_struct_ops_transit_state(st_map, BPF_STRUCT_OPS_STATE_INUSE,
> + (st_map->map.map_flags & BPF_F_LINK ?
> + BPF_STRUCT_OPS_STATE_TOBEUNREG :
> + BPF_STRUCT_OPS_STATE_TOBEFREE));
> + st_map->st_ops->unreg(&st_map->kvalue.data);
> + bpf_struct_ops_put(&st_map->kvalue.data);
> + }
> + kfree(st_link);
> +}
> +
> +static int bpf_struct_ops_map_link_detach(struct bpf_link *link)
> +{
> + struct bpf_struct_ops_link *st_link;
> + struct bpf_struct_ops_map *st_map;
> +
> + mutex_lock(&update_mutex);
> + st_link = container_of(link, struct bpf_struct_ops_link, link);
> + st_map = container_of(st_link->map, struct bpf_struct_ops_map, map);
> + if (st_map) {
> + /*
> + * All chaning on st_link->map are protected by
> + * update_mutex. This ensures that the struct_ops is
> + * INUSE, and the state transition always success.
> + */
> + rcu_assign_pointer(st_link->map, NULL);
I think the map is leaked. I also think it does not need assign NULL also.
Otherwise, the show_fdinfo and fill_link_info will become confusing.
> + bpf_struct_ops_transit_state(st_map, BPF_STRUCT_OPS_STATE_INUSE,
> + (st_map->map.map_flags & BPF_F_LINK ?
> + BPF_STRUCT_OPS_STATE_TOBEUNREG :
> + BPF_STRUCT_OPS_STATE_TOBEFREE));
> + st_map->st_ops->unreg(&st_map->kvalue.data);
> + bpf_struct_ops_put(&st_map->kvalue.data);
> + }
> + mutex_unlock(&update_mutex);
> +
> + return 0;
> +}
next prev parent reply other threads:[~2023-02-24 6:58 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-02-23 1:12 [PATCH bpf-next v2 0/6] Transit between BPF TCP congestion controls Kui-Feng Lee
2023-02-23 1:12 ` [PATCH bpf-next v2 1/6] bpf: Create links for BPF struct_ops maps Kui-Feng Lee
2023-02-23 2:15 ` Kui-Feng Lee
2023-02-23 21:19 ` Stanislav Fomichev
2023-02-24 6:58 ` Martin KaFai Lau [this message]
2023-02-28 7:25 ` Kui-Feng Lee
2023-02-23 1:12 ` [PATCH bpf-next v2 2/6] net: Update an existing TCP congestion control algorithm Kui-Feng Lee
2023-02-23 1:12 ` [PATCH bpf-next v2 3/6] libbpf: Create a bpf_link in bpf_map__attach_struct_ops() Kui-Feng Lee
2023-02-23 1:12 ` [PATCH bpf-next v2 4/6] bpf: Update the struct_ops of a bpf_link Kui-Feng Lee
2023-02-23 1:12 ` [PATCH bpf-next v2 5/6] libbpf: Update a bpf_link with another struct_ops Kui-Feng Lee
2023-02-23 1:12 ` [PATCH bpf-next v2 6/6] selftests/bpf: Test switching TCP Congestion Control algorithms Kui-Feng Lee
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=60634c64-5e16-c3d8-3561-6b88c5b5b1fd@linux.dev \
--to=martin.lau@linux.dev \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=kernel-team@meta.com \
--cc=kuifeng@meta.com \
--cc=sdf@google.com \
--cc=song@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox