Skip to contentSkip to conversation

bpf: query effective progs without cgroup_mutex

PATCH In review Stanislav Fomichev 3 participants 9 messages May 11, 2023 – May 17, 2023

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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
index 456f33b9d205..b5a3d95d2657 100644
@@ -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
index 7421487422d4..5793d6df30c6 100644
@@ -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
#2 lore raw

PATCH 2/4 rculist: add hlist_for_each_rcu

In reply to Stanislav Fomichev

Same 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
index d29740be4833..7b0a73139b21 100644
@@ -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
#3 lore raw

PATCH 3/4 bpf: refactor __cgroup_bpf_query

In reply to Stanislav Fomichev

No 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
index a06e118a9be5..32092c78602f 100644
@@ -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
#4 lore raw

PATCH 4/4 bpf: query effective progs without cgroup_mutex

In reply to Stanislav Fomichev

When 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
index 7b121bd780eb..df0b8faa1a17 100644
@@ -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
index 57e9e109257e..555e9cbb3a05 100644
@@ -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
#5 lore raw
Quoted 33 lines · Stanislav Fomichev

When 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.

Quoted 7 lines
---
 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_query path. This is likely due to being blocked on cgroup_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?

[...]

#6 lore raw
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 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.

Quoted 7 lines
---
 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_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?

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_query path. This is likely due to being blocked on cgroup_mutex.

Is that likely an unconfirmed suspicion or you did see that cgroup_mutex lock 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?

#7 lore raw
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_query path. This is likely due to being blocked on cgroup_mutex.

Quoted 6 lines
Quoted 2 lines

Is that likely an unconfirmed suspicion or you did see that cgroup_mutex lock 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.

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.

#8 lore raw
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_query path. This is likely due to being blocked on cgroup_mutex.

Quoted 6 lines
Quoted 2 lines

Is that likely an unconfirmed suspicion or you did see that cgroup_mutex lock 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.

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.

Quoted 7 lines

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.

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?