bpf: query effective progs without cgroup_mutex
cover bpf: query effective progs without cgroup_mutex
We're observing some stalls on the heavily loaded machines in the cgroup_bpf_prog_query path. This is likely due to being blocked on cgroup_mutex.
IIUC, the cgroup_mutex is there mostly to protect the non-effective fields (cgrp->bpf.progs) which might be changed by the update path. For the BPF_F_QUERY_EFFECTIVE case, all we need is to rcu_dereference a bunch of pointers (and keep them around for consistency), so let's do it.
Since RFC, I've added handling for non-effective case as well. It's a bit more complicated, but converting prog hlist to rcu seems to be all we need (unless I'm missing something). Plus, couple of READ_ONCE/WRITE_ONCE for the flags to read them in a lockless (racy) manner.
Stanislav Fomichev (4):
bpf: export bpf_prog_array_copy_core
rculist: add hlist_for_each_rcu
bpf: refactor __cgroup_bpf_query
bpf: query effective progs without cgroup_mutex
include/linux/bpf-cgroup-defs.h | 2 +- include/linux/bpf-cgroup.h | 1 + include/linux/bpf.h | 2 + include/linux/rculist.h | 6 ++ kernel/bpf/cgroup.c | 168 +++++++++++++++++++------------- kernel/bpf/core.c | 14 ++- 6 files changed, 114 insertions(+), 79 deletions(-)
Signature · 1 line
2.40.1.521.gf1e218fcd8-goog
PATCH 1/4 bpf: export bpf_prog_array_copy_core
No functional changes.
It will be used later on to copy prog array into a temporary kernel buffer. I'm also changing its return type to errno to be consistent with the rest of the similar helpers.
--- include/linux/bpf.h | 2 ++ kernel/bpf/core.c | 14 ++++++-------- 2 files changed, 8 insertions(+), 8 deletions(-)
include/linux/bpf.h +2 -0
@@ -1779,6 +1779,8 @@ void bpf_prog_array_free(struct bpf_prog_array *progs);void bpf_prog_array_free_sleepable (struct bpf_prog_array *progs);int bpf_prog_array_length (struct bpf_prog_array *progs);bool bpf_prog_array_is_empty (struct bpf_prog_array *array); +int bpf_prog_array_copy_core (struct bpf_prog_array *array, +u32 *prog_ids,u32 request_cnt);int bpf_prog_array_copy_to_user (struct bpf_prog_array *progs,__u32 __user *prog_ids,u32 cnt);
kernel/bpf/core.c +6 -8
@@ -2306,9 +2306,8 @@ bool bpf_prog_array_is_empty(struct bpf_prog_array *array)return true; } -static bool bpf_prog_array_copy_core (struct bpf_prog_array *array, -u32 *prog_ids, -u32 request_cnt) +int bpf_prog_array_copy_core (struct bpf_prog_array *array, +u32 *prog_ids,u32 request_cnt) {struct bpf_prog_array_item *item;int i =0 ;
@@ -2323,14 +2322,14 @@ static bool bpf_prog_array_copy_core(struct bpf_prog_array *array, } } -return !!(item->prog); +return !!(item->prog) ? -ENOSPC :0 ; }int bpf_prog_array_copy_to_user (struct bpf_prog_array *array,__u32 __user *prog_ids,u32 cnt) {unsigned long err =0 ; -bool nospc; +int nospc;u32 *ids;/* users of this function are doing:
@@ -2348,7 +2347,7 @@ int bpf_prog_array_copy_to_user(struct bpf_prog_array *array,if (err)return -EFAULT ;if (nospc) -return -ENOSPC ; +return nospc;return 0 ; }
@@ -2506,8 +2505,7 @@ int bpf_prog_array_copy_info(struct bpf_prog_array *array,return 0 ;/* this function is called under trace/bpf_trace.c: bpf_event_mutex */ -return bpf_prog_array_copy_core (array, prog_ids, request_cnt) ? -ENOSPC - :0 ; +return bpf_prog_array_copy_core (array, prog_ids, request_cnt); } void __bpf_free_used_maps(struct bpf_prog_aux *aux,
Signature · 1 line
2.40.1.521.gf1e218fcd8-goog
PATCH 2/4 rculist: add hlist_for_each_rcu
In reply to Stanislav FomichevSame as __hlist_for_each_rcu but uses rcu_dereference_raw to suppress the warning from the update path (which is enforced by extra cond expression).
--- include/linux/rculist.h | 6 ++++++ 1 file changed, 6 insertions(+)
include/linux/rculist.h +6 -0
@@ -690,6 +690,12 @@ static inline void hlist_add_behind_rcu(struct hlist_node *n,pos ; \ pos = rcu_dereference(hlist_next_rcu(pos))) +#define hlist_for_each_rcu(pos, head, cond...) \ + for (__list_check_rcu(dummy, ## cond, 0), \ + pos = rcu_dereference_raw(hlist_first_rcu(head)); \ + pos; \ + pos = rcu_dereference_raw(hlist_next_rcu(pos))) +/** * hlist_for_each_entry_rcu - iterate over rcu list of given type * @pos: the type * to use as a loop cursor.
Signature · 1 line
2.40.1.521.gf1e218fcd8-goog
PATCH 3/4 bpf: refactor __cgroup_bpf_query
In reply to Stanislav FomichevNo functional changes.
This patch is here to make it easier to review the next one. We'll be copying buffer to the userspace from the temporary kernel one, so rename prog_ids to user_prog_ids and add new extra variable (p) to traverse it.
Also, instead of decrementing total_cnt, introduce new 'remaning' variable to keep track of where we are. We'll need original total_cnt in the next patch to know how many bytes to copy back.
--- kernel/bpf/cgroup.c | 24 ++++++++++++++---------- 1 file changed, 14 insertions(+), 10 deletions(-)
kernel/bpf/cgroup.c +14 -10
@@ -1021,21 +1021,23 @@ static int __cgroup_bpf_query(struct cgroup *cgrp, const union bpf_attr *attr, {__u32 __user *prog_attach_flags =u64_to_user_ptr (attr->query.prog_attach_flags);bool effective_query = attr->query.query_flags &BPF_F_QUERY_EFFECTIVE ; -__u32 __user *prog_ids =u64_to_user_ptr (attr->query.prog_ids); +__u32 __user *user_prog_ids =u64_to_user_ptr (attr->query.prog_ids);enum bpf_attach_type type = attr->query.attach_type;enum cgroup_bpf_attach_type from_atype, to_atype;enum cgroup_bpf_attach_type atype;struct bpf_prog_array *effective;int cnt, ret =0 , i;int total_cnt =0 ; +int remaining;u32 flags; +u32 *p;if (effective_query && prog_attach_flags)return -EINVAL ;if (type ==BPF_LSM_CGROUP ) {if (!effective_query && attr->query.prog_cnt && - prog_ids && !prog_attach_flags) + user_prog_ids && !prog_attach_flags)return -EINVAL ; from_atype =CGROUP_LSM_START ;
@@ -1065,7 +1067,7 @@ static int __cgroup_bpf_query(struct cgroup *cgrp, const union bpf_attr *attr,return -EFAULT ;if (copy_to_user (&uattr->query.prog_cnt, &total_cnt,sizeof (total_cnt)))return -EFAULT ; -if (attr->query.prog_cnt ==0 || !prog_ids || !total_cnt) +if (attr->query.prog_cnt ==0 || !user_prog_ids || !total_cnt)/* return early if user requested only program count + flags */ return 0 ;
@@ -1074,12 +1076,14 @@ static int __cgroup_bpf_query(struct cgroup *cgrp, const union bpf_attr *attr, ret = -ENOSPC ; } -for (atype = from_atype; atype <= to_atype && total_cnt; atype++) { + p = user_prog_ids; + remaining = total_cnt; +for (atype = from_atype; atype <= to_atype && remaining; atype++) {if (effective_query) { effective =rcu_dereference_protected (cgrp->bpf.effective[atype],lockdep_is_held (&cgroup_mutex)); - cnt =min_t (int,bpf_prog_array_length (effective), total_cnt); - ret =bpf_prog_array_copy_to_user (effective, prog_ids, cnt); + cnt =min_t (int,bpf_prog_array_length (effective), remaining); + ret =bpf_prog_array_copy_to_user (effective, p, cnt); }else {struct hlist_head *progs;struct bpf_prog_list *pl;
@@ -1087,12 +1091,12 @@ static int __cgroup_bpf_query(struct cgroup *cgrp, const union bpf_attr *attr,u32 id; progs = &cgrp->bpf.progs[atype]; - cnt =min_t (int,prog_list_length (progs), total_cnt); + cnt =min_t (int,prog_list_length (progs), remaining); i =0 ;hlist_for_each_entry (pl, progs, node) { prog =prog_list_prog (pl); id = prog->aux->id; -if (copy_to_user (prog_ids + i, &id,sizeof (id))) +if (copy_to_user (p + i, &id,sizeof (id)))return -EFAULT ;if (++i == cnt)break ;
@@ -1109,8 +1113,8 @@ static int __cgroup_bpf_query(struct cgroup *cgrp, const union bpf_attr *attr, } } - prog_ids += cnt; - total_cnt -= cnt; + p += cnt; + remaining -= cnt; }return ret; }
Signature · 1 line
2.40.1.521.gf1e218fcd8-goog
PATCH 4/4 bpf: query effective progs without cgroup_mutex
In reply to Stanislav FomichevWhen querying bpf prog list, we don't really need to hold cgroup_mutex. There is only one caller of cgroup_bpf_query (cgroup_bpf_prog_query) and it does cgroup_get/put, so we're safe WRT cgroup going way. However, we if we stop grabbing cgroup_mutex, we risk racing with the prog attach/detach path to the same cgroup, so here is how to work it around.
We have two case:
1. querying effective array
2. querying non-effective list
(1) is easy because it's already a RCU-managed array, so all we need is to make a copy of that array (under rcu read lock) into a temporary buffer and copy that temporary buffer back to userspace.
(2) is more involved because we keep the list of progs and it's not managed by RCU. However, it seems relatively simple to convert that hlist to the RCU-managed one: convert the readers to use hlist_xxx_rcu and replace kfree with kfree_rcu. One other notable place is cgroup_bpf_release where we replace hlist_for_each_entry_safe with hlist_for_each_entry_rcu. This should be safe because hlist_del_rcu does not remove/poison forward pointer of the list entry, so it's safe to remove the elements while iterating (without specially flavored for_each_safe wrapper).
For (2), we also need to take care of flags. I added a bunch of READ_ONCE/WRITE_ONCE to annotate lockless access. And I also moved flag update path to happen before adding prog to the list to make sure readers observe correct flags.
--- include/linux/bpf-cgroup-defs.h | 2 +- include/linux/bpf-cgroup.h | 1 + kernel/bpf/cgroup.c | 152 ++++++++++++++++++-------------- 3 files changed, 90 insertions(+), 65 deletions(-)
include/linux/bpf-cgroup-defs.h +1 -1
@@ -56,7 +56,7 @@ struct cgroup_bpf {* have either zero or one element * when BPF_F_ALLOW_MULTI the list can have up to BPF_CGROUP_MAX_PROGS */ -struct hlist_head progs[MAX_CGROUP_BPF_ATTACH_TYPE ]; +struct hlist_head __rcu progs[MAX_CGROUP_BPF_ATTACH_TYPE ];u8 flags[MAX_CGROUP_BPF_ATTACH_TYPE ];/* list of cgroup shared storages */
include/linux/bpf-cgroup.h +1 -0
@@ -106,6 +106,7 @@ struct bpf_prog_list {struct bpf_prog *prog;struct bpf_cgroup_link *link;struct bpf_cgroup_storage *storage[MAX_BPF_CGROUP_STORAGE_TYPE ]; +struct rcu_head rcu; };int cgroup_bpf_inherit (struct cgroup *cgrp);
kernel/bpf/cgroup.c +88 -64
365 lines not on this page · raw message
Signature · 1 line
2.40.1.521.gf1e218fcd8-goog
Quoted 33 lines · Stanislav Fomichev
When querying bpf prog list, we don't really need to hold
cgroup_mutex. There is only one caller ofcgroup_bpf_query(cgroup_bpf_prog_query) and it does cgroup_get/put, so we're safe WRT cgroup going way. However, we if we stop grabbingcgroup_mutex, we risk racing with the prog attach/detach path to the same cgroup, so here is how to work it around.We have two case:
1. querying effective array
2. querying non-effective list(1) is easy because it's already a RCU-managed array, so all we need is to make a copy of that array (under rcu read lock) into a temporary buffer and copy that temporary buffer back to userspace.
(2) is more involved because we keep the list of progs and it's not managed by RCU. However, it seems relatively simple to convert that hlist to the RCU-managed one: convert the readers to use
hlist_xxx_rcuand replace kfree withkfree_rcu. One other notable place iscgroup_bpf_releasewhere we replacehlist_for_each_entry_safewithhlist_for_each_entry_rcu. This should be safe becausehlist_del_rcudoes not remove/poison forward pointer of the list entry, so it's safe to remove the elements while iterating (without specially flavoredfor_each_safewrapper).For (2), we also need to take care of flags. I added a bunch of READ_ONCE/WRITE_ONCE to annotate lockless access. And I also moved flag update path to happen before adding prog to the list to make sure readers observe correct flags.
Quoted 7 lines
Signed-off-by Stanislav Fomichev <[email protected]>--- include/linux/bpf-cgroup-defs.h | 2 +- include/linux/bpf-cgroup.h | 1 + kernel/bpf/cgroup.c | 152 ++++++++++++++++++-------------- 3 files changed, 90 insertions(+), 65 deletions(-)
Few reservations from my side:
1. You are adding 16 bytes to bpf_prog_list, of which there could be *tons* copies of. It might be ok, but slightly speeding up something that's not even considered to be a performance-critical operation (prog query) at the expense of more memory usage feels a bit odd.
2. This code is already pretty tricky, and that's under the simplifying conditions of cgroup_mutex being held. We are now making it even more complicated without locks being held.
3. This code is probably going to be changed again once Daniel's multi-prog API lands, so we are going to do this exercise again afterwards?
So taking a bit of a step back. In cover letter you mentioned:
Quoted 3 lines
We're observing some stalls on the heavily loaded machines in the
cgroup_bpf_prog_querypath. This is likely due to being blocked oncgroup_mutex.
Is that likely an unconfirmed suspicion or you did see that cgroup_mutex lock is causing stalls?
Also, I wonder if you tried using BPF program or cgroup iterators to get all this information from BPF side? I wonder if that's feasible?
[...]
Quoted 50 lines · Andrii Nakryiko
Quoted 33 lines · Stanislav Fomichev
When querying bpf prog list, we don't really need to hold
cgroup_mutex. There is only one caller ofcgroup_bpf_query(cgroup_bpf_prog_query) and it does cgroup_get/put, so we're safe WRT cgroup going way. However, we if we stop grabbingcgroup_mutex, we risk racing with the prog attach/detach path to the same cgroup, so here is how to work it around.We have two case:
1. querying effective array
2. querying non-effective list(1) is easy because it's already a RCU-managed array, so all we need is to make a copy of that array (under rcu read lock) into a temporary buffer and copy that temporary buffer back to userspace.
(2) is more involved because we keep the list of progs and it's not managed by RCU. However, it seems relatively simple to convert that hlist to the RCU-managed one: convert the readers to use
hlist_xxx_rcuand replace kfree withkfree_rcu. One other notable place iscgroup_bpf_releasewhere we replacehlist_for_each_entry_safewithhlist_for_each_entry_rcu. This should be safe becausehlist_del_rcudoes not remove/poison forward pointer of the list entry, so it's safe to remove the elements while iterating (without specially flavoredfor_each_safewrapper).For (2), we also need to take care of flags. I added a bunch of READ_ONCE/WRITE_ONCE to annotate lockless access. And I also moved flag update path to happen before adding prog to the list to make sure readers observe correct flags.
Quoted 7 lines
Signed-off-by Stanislav Fomichev <[email protected]>--- include/linux/bpf-cgroup-defs.h | 2 +- include/linux/bpf-cgroup.h | 1 + kernel/bpf/cgroup.c | 152 ++++++++++++++++++-------------- 3 files changed, 90 insertions(+), 65 deletions(-)Few reservations from my side:
1. You are adding 16 bytes to
bpf_prog_list, of which there could be *tons* copies of. It might be ok, but slightly speeding up something that's not even considered to be a performance-critical operation (prog query) at the expense of more memory usage feels a bit odd.
Quoted 7 lines
2. This code is already pretty tricky, and that's under the simplifying conditions of
cgroup_mutexbeing held. We are now making it even more complicated without locks being held.3. This code is probably going to be changed again once Daniel's multi-prog API lands, so we are going to do this exercise again afterwards?
I'm happy to wait for (3). From my pow (2) is the most concerning. The code is a bit complicated (and my patches are not helping), maybe that's a sign that we need to clean it up :-)
Some parts are rcu-safe, some aren't. cgroup_mutex usage looks like something that was done long ago for simplicity and might not apply anymore. We now have machines which have multiple progs attached per cgroup; grabbing global lock just to query the list seems excessive.
Quoted 8 lines
So taking a bit of a step back. In cover letter you mentioned:
Quoted 3 lines
We're observing some stalls on the heavily loaded machines in the
cgroup_bpf_prog_querypath. This is likely due to being blocked oncgroup_mutex.Is that likely an unconfirmed suspicion or you did see that
cgroup_mutexlock is causing stalls?
My intuition: we know that we have multiple-second stalls due cgroup_mutex elsewhere and I don't see any other locks in the prog_query path.
Quoted 2 lines
Also, I wonder if you tried using BPF program or cgroup iterators to get all this information from BPF side? I wonder if that's feasible?
Cgroup iterator has the following in the comment:
Note: the iter_prog is called with cgroup_mutex held.
I can probably use a link iterator; I would have to upcast bpf_link to bpf_cgroup_link (via bpf_probe_read?) to get to the cgroup id, but it seems like a workaround?
Quoted 7 lines · Stanislav Fomichev
Quoted 7 lines
So taking a bit of a step back. In cover letter you mentioned:
Quoted 3 lines
We're observing some stalls on the heavily loaded machines in the
cgroup_bpf_prog_querypath. This is likely due to being blocked oncgroup_mutex.
Quoted 6 lines
Quoted 2 lines
Is that likely an unconfirmed suspicion or you did see that
cgroup_mutexlock is causing stalls?My intuition: we know that we have multiple-second stalls due
cgroup_mutexelsewhere and I don't see any other locks in theprog_querypath.
I think more debugging is necessary here to root cause this multi-second stalls. Sounds like they're real. We have to understand them and fix
the root issue.
"Let's make cgroup_bpf_query lockless, because we can, and hope that it will help" is not a data driven development.
I can imagine that copy_to_user-s done from __cgroup_bpf_query with cgroup_lock taken are causing delay, but multi-second ?! There must be something else.
If copy_to_user is indeed the issue, we can move just that part to be done after cgroup_unlock.
Note cgroup_bpf_attach/detach don't do user access, so shouldn't be influenced by faults in user space.
Quoted 22 lines · Alexei Starovoitov
Quoted 7 lines · Stanislav Fomichev
Quoted 7 lines
So taking a bit of a step back. In cover letter you mentioned:
Quoted 3 lines
We're observing some stalls on the heavily loaded machines in the
cgroup_bpf_prog_querypath. This is likely due to being blocked oncgroup_mutex.Quoted 6 lines
Quoted 2 lines
Is that likely an unconfirmed suspicion or you did see that
cgroup_mutexlock is causing stalls?My intuition: we know that we have multiple-second stalls due
cgroup_mutexelsewhere and I don't see any other locks in theprog_querypath.I think more debugging is necessary here to root cause this multi-second stalls. Sounds like they're real. We have to understand them and fix
the root issue.
"Let's makecgroup_bpf_querylockless, because we can, and hope that it will help" is not a data driven development.
Quoted 7 lines
I can imagine that copy_to_user-s done from
__cgroup_bpf_querywithcgroup_locktaken are causing delay, but multi-second ?! There must be something else.
Ifcopy_to_useris indeed the issue, we can move just that part to be done aftercgroup_unlock.
Note cgroup_bpf_attach/detach don't do user access, so shouldn't be influenced by faults in user space.
It's definitely not our path that is slow. Some other path that grabs cgroup_mutex can hold it for arbitrary time which makes our bpf_query path wait on it.
That's why I was hoping that we can just avoid locking cgroup_mutex where possible (at least query/read paths).
Hao, can you share more about what particular path is causing the issue? I don't see anything mentioned on the internal bug, but maybe you have something to share?