Re: [PATCH bpf-next v2 1/6] bpf: Create links for BPF struct_ops maps.

Martin KaFai Lau
2023-02-24T06:58:53Z

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;
> +}