Skip to contentSkip to conversation

Sleepable local storage

PATCH Superseded KP Singh 3 participants 28 messages Aug 26, 2021 – Dec 5, 2021

Subsystems (5)

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

KP Singh

author
#0 lore raw

cover Sleepable local storage

Local storage is currently unusable in sleepable helpers. One of the important use cases of local_storage is to attach security (or performance) contextual information to kernel objects in LSM / tracing programs to be used later in the life-cyle of the object.

Sometimes this context can only be gathered from sleepable programs (because it needs accesing __user pointers or helpers like bpf_ima_inode_hash). Allowing local storage to be used from sleepable programs allows such context to be managed with the benefits of local_storage.

KP Singh (2):
bpf: Allow bpf_local_storage to be used by sleepable programs bpf/selftests: Update local storage selftest for sleepable programs

 include/linux/bpf_local_storage.h             |  5 +++
 kernel/bpf/bpf_inode_storage.c                |  9 +++-
 kernel/bpf/bpf_local_storage.c                | 43 +++++++++++++++----
 kernel/bpf/bpf_task_storage.c                 |  6 ++-
 kernel/bpf/verifier.c                         |  3 ++
 net/core/bpf_sk_storage.c                     |  8 +++-
 .../bpf/prog_tests/test_local_storage.c       | 20 +++------
 .../selftests/bpf/progs/local_storage.c       | 24 +++--------
 8 files changed, 72 insertions(+), 46 deletions(-)
Signature · 1 line
2.33.0.259.gc128427fd7-goog
author
#1 lore raw

PATCH 1/2 bpf: Allow bpf_local_storage to be used by sleepable programs

Other maps like hashmaps are already available to sleepable programs. Sleepable BPF programs run under trace RCU. Allow task, local and inode storage to be used from sleepable programs.

The local storage code mostly runs under the programs RCU read section (in __bpf_prog_enter{_sleepable} and __bpf_prog_exit{_sleepable}) (rcu_read_lock or rcu_read_lock_trace) with the exception the logic where the map is freed.

After some discussions and help from Jann Horn, the following changes were made:

bpf_local_storage{_elem} are freed with a kfree_rcu
wrapped with a call_rcu_tasks_trace callback instead of a direct kfree_rcu which does not respect the trace RCU grace periods. The callback frees the storage/selem with kfree_rcu which handles the normal RCU grace period similar to BPF trampolines.

Update the synchronise_rcu to synchronize_rcu_mult in the map freeing code to wait for trace RCU and normal RCU grace periods. While this is an expensive operation, bpf_local_storage_map_free is not called from within a BPF program, rather only called when the owning object is being freed.

Update the dereferencing of the pointers to use rcu_derference_protected (with either the trace or normal RCU locks held) and add warnings in the beginning of the get and delete helpers.

---
 include/linux/bpf_local_storage.h |  5 ++++
 kernel/bpf/bpf_inode_storage.c    |  9 +++++--
 kernel/bpf/bpf_local_storage.c    | 43 ++++++++++++++++++++++++-------
 kernel/bpf/bpf_task_storage.c     |  6 ++++-
 kernel/bpf/verifier.c             |  3 +++
 net/core/bpf_sk_storage.c         |  8 +++++-
 6 files changed, 61 insertions(+), 13 deletions(-)
include/linux/bpf_local_storage.h +5 -0
index 24496bc28e7b..8453488b334d 100644
@@ -16,6 +16,9 @@
 
 #define BPF_LOCAL_STORAGE_CACHE_SIZE	16
 
+#define bpf_local_storage_rcu_lock_held()			\
+	(rcu_read_lock_held() || rcu_read_lock_trace_held() ||	\
+		rcu_read_lock_bh_held())
 struct bpf_local_storage_map_bucket {
 	struct hlist_head list;
 	raw_spinlock_t lock;
@@ -161,4 +164,6 @@ struct bpf_local_storage_data *
 bpf_local_storage_update(void *owner, struct bpf_local_storage_map *smap,
 			 void *value, u64 map_flags);
 
+void bpf_local_storage_free_rcu(struct rcu_head *rcu);
+
 #endif /* _BPF_LOCAL_STORAGE_H */
kernel/bpf/bpf_inode_storage.c +7 -2
index 96ceed0e0fb5..409ef5d3efee 100644
@@ -17,6 +17,7 @@
 #include <linux/bpf_lsm.h>
 #include <linux/btf_ids.h>
 #include <linux/fdtable.h>
+#include <linux/rcupdate_trace.h>
 
 DEFINE_BPF_STORAGE_CACHE(inode_cache);
 
@@ -44,7 +45,8 @@ static struct bpf_local_storage_data *inode_storage_lookup(struct inode *inode,
 	if (!bsb)
 		return NULL;
 
-	inode_storage = rcu_dereference(bsb->storage);
+	inode_storage = rcu_dereference_protected(bsb->storage,
+						  bpf_local_storage_rcu_lock_held());
 	if (!inode_storage)
 		return NULL;
 
@@ -97,7 +99,8 @@ void bpf_inode_storage_free(struct inode *inode)
 	 * local_storage->list was non-empty.
 	 */
 	if (free_inode_storage)
-		kfree_rcu(local_storage, rcu);
+		call_rcu_tasks_trace(&local_storage->rcu,
+				     bpf_local_storage_free_rcu);
 }
 
 static void *bpf_fd_inode_storage_lookup_elem(struct bpf_map *map, void *key)
@@ -172,6 +175,7 @@ BPF_CALL_4(bpf_inode_storage_get, struct bpf_map *, map, struct inode *, inode,
 {
 	struct bpf_local_storage_data *sdata;
 
+	WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
 	if (flags & ~(BPF_LOCAL_STORAGE_GET_F_CREATE))
 		return (unsigned long)NULL;
 
@@ -204,6 +208,7 @@ BPF_CALL_4(bpf_inode_storage_get, struct bpf_map *, map, struct inode *, inode,
 BPF_CALL_2(bpf_inode_storage_delete,
 	   struct bpf_map *, map, struct inode *, inode)
 {
+	WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
 	if (!inode)
 		return -EINVAL;
 
kernel/bpf/bpf_local_storage.c +34 -9

101 lines not on this page · raw message

kernel/bpf/bpf_task_storage.c +5 -1
index 3ce75758d394..87f0daeff314 100644
@@ -17,6 +17,7 @@
 #include <uapi/linux/btf.h>
 #include <linux/btf_ids.h>
 #include <linux/fdtable.h>
+#include <linux/rcupdate_trace.h>
 
 DEFINE_BPF_STORAGE_CACHE(task_cache);
 
@@ -59,7 +60,8 @@ task_storage_lookup(struct task_struct *task, struct bpf_map *map,
 	struct bpf_local_storage *task_storage;
 	struct bpf_local_storage_map *smap;
 
-	task_storage = rcu_dereference(task->bpf_storage);
+	task_storage = rcu_dereference_protected(task->bpf_storage,
+						 bpf_local_storage_rcu_lock_held());
 	if (!task_storage)
 		return NULL;
 
@@ -229,6 +231,7 @@ BPF_CALL_4(bpf_task_storage_get, struct bpf_map *, map, struct task_struct *,
 {
 	struct bpf_local_storage_data *sdata;
 
+	WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
 	if (flags & ~(BPF_LOCAL_STORAGE_GET_F_CREATE))
 		return (unsigned long)NULL;
 
@@ -260,6 +263,7 @@ BPF_CALL_2(bpf_task_storage_delete, struct bpf_map *, map, struct task_struct *,
 {
 	int ret;
 
+	WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
 	if (!task)
 		return -EINVAL;
 
kernel/bpf/verifier.c +3 -0
index 206c221453cf..4e0b807a0104 100644
@@ -11457,6 +11457,9 @@ static int check_map_prog_compatibility(struct bpf_verifier_env *env,
 			}
 			break;
 		case BPF_MAP_TYPE_RINGBUF:
+		case BPF_MAP_TYPE_INODE_STORAGE:
+		case BPF_MAP_TYPE_SK_STORAGE:
+		case BPF_MAP_TYPE_TASK_STORAGE:
 			break;
 		default:
 			verbose(env,
net/core/bpf_sk_storage.c +7 -1
index 68d2cbf8331a..b56578579a0d 100644
@@ -13,6 +13,7 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
 
 DEFINE_BPF_STORAGE_CACHE(sk_cache);
 
@@ -22,7 +23,8 @@ bpf_sk_storage_lookup(struct sock *sk, struct bpf_map *map, bool cacheit_lockit)
 	struct bpf_local_storage *sk_storage;
 	struct bpf_local_storage_map *smap;
 
-	sk_storage = rcu_dereference(sk->sk_bpf_storage);
+	sk_storage = rcu_dereference_protected(sk->sk_bpf_storage,
+					       bpf_local_storage_rcu_lock_held());
 	if (!sk_storage)
 		return NULL;
 
@@ -258,6 +260,7 @@ BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk,
 {
 	struct bpf_local_storage_data *sdata;
 
+	WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
 	if (!sk || !sk_fullsock(sk) || flags > BPF_SK_STORAGE_GET_F_CREATE)
 		return (unsigned long)NULL;
 
@@ -288,6 +291,7 @@ BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk,
 
 BPF_CALL_2(bpf_sk_storage_delete, struct bpf_map *, map, struct sock *, sk)
 {
+	WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
 	if (!sk || !sk_fullsock(sk))
 		return -EINVAL;
 
@@ -416,6 +420,7 @@ static bool bpf_sk_storage_tracing_allowed(const struct bpf_prog *prog)
 BPF_CALL_4(bpf_sk_storage_get_tracing, struct bpf_map *, map, struct sock *, sk,
 	   void *, value, u64, flags)
 {
+	WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
 	if (in_hardirq() || in_nmi())
 		return (unsigned long)NULL;
 
@@ -425,6 +430,7 @@ BPF_CALL_4(bpf_sk_storage_get_tracing, struct bpf_map *, map, struct sock *, sk,
 BPF_CALL_2(bpf_sk_storage_delete_tracing, struct bpf_map *, map,
 	   struct sock *, sk)
 {
+	WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
 	if (in_hardirq() || in_nmi())
 		return -EPERM;
 
Signature · 1 line
2.33.0.259.gc128427fd7-goog
#2 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 43 lines · KP Singh

Other maps like hashmaps are already available to sleepable programs. Sleepable BPF programs run under trace RCU. Allow task, local and inode storage to be used from sleepable programs.

The local storage code mostly runs under the programs RCU read section (in __bpf_prog_enter{_sleepable} and __bpf_prog_exit{_sleepable}) (rcu_read_lock or rcu_read_lock_trace) with the exception the logic where the map is freed.

After some discussions and help from Jann Horn, the following changes were made:

bpf_local_storage{_elem} are freed with a kfree_rcu
wrapped with a call_rcu_tasks_trace callback instead of a direct kfree_rcu which does not respect the trace RCU grace periods. The callback frees the storage/selem with kfree_rcu which handles the normal RCU grace period similar to BPF trampolines.

Update the synchronise_rcu to synchronize_rcu_mult in the map freeing code to wait for trace RCU and normal RCU grace periods. While this is an expensive operation, bpf_local_storage_map_free is not called from within a BPF program, rather only called when the owning object is being freed.

Update the dereferencing of the pointers to use rcu_derference_protected (with either the trace or normal RCU locks held) and add warnings in the beginning of the get and delete helpers.

---
 include/linux/bpf_local_storage.h |  5 ++++
 kernel/bpf/bpf_inode_storage.c    |  9 +++++--
 kernel/bpf/bpf_local_storage.c    | 43 ++++++++++++++++++++++++-------
 kernel/bpf/bpf_task_storage.c     |  6 ++++-
 kernel/bpf/verifier.c             |  3 +++
 net/core/bpf_sk_storage.c         |  8 +++++-
 6 files changed, 61 insertions(+), 13 deletions(-)
include/linux/bpf_local_storage.h +0 -0
index 24496bc28e7b..8453488b334d 100644

include/linux/bpf_local_storage.h line 21

Quoted 6 lines
include/linux/bpf_local_storage.h +3 -0
@@ -16,6 +16,9 @@
 
 #define BPF_LOCAL_STORAGE_CACHE_SIZE	16
 
+#define bpf_local_storage_rcu_lock_held()			\
+	(rcu_read_lock_held() || rcu_read_lock_trace_held() ||	\
+		rcu_read_lock_bh_held())

There is a similar test in hashtab. May be renaming it to a more generic name such that it can be reused there?

[ ... ]

Quoted 53 lines
kernel/bpf/bpf_local_storage.c +21 -3
index b305270b7a4b..7760bc4e9565 100644
@@ -11,6 +11,8 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
+#include <linux/rcupdate_wait.h>
 
 #define BPF_LOCAL_STORAGE_CREATE_FLAG_MASK (BPF_F_NO_PREALLOC | BPF_F_CLONE)
 
@@ -81,6 +83,22 @@ bpf_selem_alloc(struct bpf_local_storage_map *smap, void *owner,
 	return NULL;
 }
 
+void bpf_local_storage_free_rcu(struct rcu_head *rcu)
+{
+	struct bpf_local_storage *local_storage;
+
+	local_storage = container_of(rcu, struct bpf_local_storage, rcu);
+	kfree_rcu(local_storage, rcu);
+}
+
+static void bpf_selem_free_rcu(struct rcu_head *rcu)
+{
+	struct bpf_local_storage_elem *selem;
+
+	selem = container_of(rcu, struct bpf_local_storage_elem, rcu);
+	kfree_rcu(selem, rcu);
+}
+
 /* local_storage->lock must be held and selem->local_storage == local_storage.
  * The caller must ensure selem->smap is still valid to be
  * dereferenced for its smap->elem_size and smap->cache_idx.
@@ -118,12 +136,12 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
 		 *
 		 * Although the unlock will be done under
 		 * rcu_read_lock(),  it is more intutivie to
-		 * read if kfree_rcu(local_storage, rcu) is done
+		 * read if the freeing of the storage is done
 		 * after the raw_spin_unlock_bh(&local_storage->lock).
 		 *
 		 * Hence, a "bool free_local_storage" is returned
-		 * to the caller which then calls the kfree_rcu()
-		 * after unlock.
+		 * to the caller which then calls then frees the storage after
+		 * all the RCU grace periods have expired.
 		 */
 	}
 	hlist_del_init_rcu(&selem->snode);

kernel/bpf/bpf_local_storage.c bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage, · line 152

Quoted 5 lines
kernel/bpf/bpf_local_storage.c +1 -1
@@ -131,7 +149,7 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
 	    SDATA(selem))
 		RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);
 
-	kfree_rcu(selem, rcu);
+	call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);

Although the common use case is usually storage_get() much more often than storage_delete(), do you aware any performance impact for the bpf prog that does a lot of storage_delete()?

Quoted 14 lines
kernel/bpf/bpf_local_storage.c +2 -1
 	return free_local_storage;
 }
@@ -154,7 +172,8 @@ static void __bpf_selem_unlink_storage(struct bpf_local_storage_elem *selem)
 	raw_spin_unlock_irqrestore(&local_storage->lock, flags);
 
 	if (free_local_storage)
-		kfree_rcu(local_storage, rcu);
+		call_rcu_tasks_trace(&local_storage->rcu,
+				     bpf_local_storage_free_rcu);
 }
 
 void bpf_selem_link_storage_nolock(struct bpf_local_storage *local_storage,

kernel/bpf/bpf_local_storage.c bpf_local_storage_lookup(struct bpf_local_storage *local_storage, · line 236

Quoted 6 lines
kernel/bpf/bpf_local_storage.c +2 -1
@@ -213,7 +232,8 @@ bpf_local_storage_lookup(struct bpf_local_storage *local_storage,
 	struct bpf_local_storage_elem *selem;
 
 	/* Fast path (cache hit) */
-	sdata = rcu_dereference(local_storage->cache[smap->cache_idx]);
+	sdata = rcu_dereference_protected(local_storage->cache[smap->cache_idx],
+					  bpf_local_storage_rcu_lock_held());

There are other places using rcu_dereference() also. e.g. in bpf_local_storage_update().
Should they be changed also?

[ ... ]

Quoted 21 lines
net/core/bpf_sk_storage.c +3 -1
@@ -13,6 +13,7 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
 
 DEFINE_BPF_STORAGE_CACHE(sk_cache);
 
@@ -22,7 +23,8 @@ bpf_sk_storage_lookup(struct sock *sk, struct bpf_map *map, bool cacheit_lockit)
 	struct bpf_local_storage *sk_storage;
 	struct bpf_local_storage_map *smap;
 
-	sk_storage = rcu_dereference(sk->sk_bpf_storage);
+	sk_storage = rcu_dereference_protected(sk->sk_bpf_storage,
+					       bpf_local_storage_rcu_lock_held());
 	if (!sk_storage)
 		return NULL;
 

net/core/bpf_sk_storage.c BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk, · line 264

Quoted 5 lines
net/core/bpf_sk_storage.c +1 -0
@@ -258,6 +260,7 @@ BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk,
 {
 	struct bpf_local_storage_data *sdata;
 
+	WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
 	if (!sk || !sk_fullsock(sk) || flags > BPF_SK_STORAGE_GET_F_CREATE)

sk is protected by rcu_read_lock here.
Is it always safe to access it with the rcu_read_lock_trace alone ?

Quoted 2 lines
net/core/bpf_sk_storage.c +0 -0
 		return (unsigned long)NULL;
 
author
#3 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 32 lines · Martin KaFai Lau
Quoted 30 lines · KP Singh

Other maps like hashmaps are already available to sleepable programs. Sleepable BPF programs run under trace RCU. Allow task, local and inode storage to be used from sleepable programs.

The local storage code mostly runs under the programs RCU read section (in __bpf_prog_enter{_sleepable} and __bpf_prog_exit{_sleepable}) (rcu_read_lock or rcu_read_lock_trace) with the exception the logic where the map is freed.

After some discussions and help from Jann Horn, the following changes were made:

bpf_local_storage{_elem} are freed with a kfree_rcu
wrapped with a call_rcu_tasks_trace callback instead of a direct kfree_rcu which does not respect the trace RCU grace periods. The callback frees the storage/selem with kfree_rcu which handles the normal RCU grace period similar to BPF trampolines.

Update the synchronise_rcu to synchronize_rcu_mult in the map freeing code to wait for trace RCU and normal RCU grace periods. While this is an expensive operation, bpf_local_storage_map_free is not called from within a BPF program, rather only called when the owning object is being freed.

Update the dereferencing of the pointers to use rcu_derference_protected (with either the trace or normal RCU locks held) and add warnings in the beginning of the get and delete helpers.

---

[...]

Quoted 9 lines

include/linux/bpf_local_storage.h line 21

Quoted 7 lines
include/linux/bpf_local_storage.h +3 -0
@@ -16,6 +16,9 @@
 
 #define BPF_LOCAL_STORAGE_CACHE_SIZE 16
 
+#define bpf_local_storage_rcu_lock_held()                    \
+     (rcu_read_lock_held() || rcu_read_lock_trace_held() ||  \
+             rcu_read_lock_bh_held())

There is a similar test in hashtab. May be renaming it to a more generic name such that it can be reused there?

Sure.

Quoted 59 lines

[ ... ]

Quoted 56 lines
kernel/bpf/bpf_local_storage.c +21 -3
index b305270b7a4b..7760bc4e9565 100644
@@ -11,6 +11,8 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
+#include <linux/rcupdate_wait.h>
 
 #define BPF_LOCAL_STORAGE_CREATE_FLAG_MASK (BPF_F_NO_PREALLOC | BPF_F_CLONE)
 
@@ -81,6 +83,22 @@ bpf_selem_alloc(struct bpf_local_storage_map *smap, void *owner,
      return NULL;
 }
 
+void bpf_local_storage_free_rcu(struct rcu_head *rcu)
+{
+     struct bpf_local_storage *local_storage;
+
+     local_storage = container_of(rcu, struct bpf_local_storage, rcu);
+     kfree_rcu(local_storage, rcu);
+}
+
+static void bpf_selem_free_rcu(struct rcu_head *rcu)
+{
+     struct bpf_local_storage_elem *selem;
+
+     selem = container_of(rcu, struct bpf_local_storage_elem, rcu);
+     kfree_rcu(selem, rcu);
+}
+
 /* local_storage->lock must be held and selem->local_storage == local_storage.
  * The caller must ensure selem->smap is still valid to be
  * dereferenced for its smap->elem_size and smap->cache_idx.
@@ -118,12 +136,12 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
               *
               * Although the unlock will be done under
               * rcu_read_lock(),  it is more intutivie to
-              * read if kfree_rcu(local_storage, rcu) is done
+              * read if the freeing of the storage is done
               * after the raw_spin_unlock_bh(&local_storage->lock).
               *
               * Hence, a "bool free_local_storage" is returned
-              * to the caller which then calls the kfree_rcu()
-              * after unlock.
+              * to the caller which then calls then frees the storage after
+              * all the RCU grace periods have expired.
               */
      }
      hlist_del_init_rcu(&selem->snode);
@@ -131,7 +149,7 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
          SDATA(selem))
              RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);
 
Quoted 5 lines

kernel/bpf/bpf_local_storage.c bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage, · line 152

Quoted 2 lines
kernel/bpf/bpf_local_storage.c +1 -1
-     kfree_rcu(selem, rcu);
+     call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);

Although the common use case is usually storage_get() much more often than storage_delete(), do you aware any performance impact for the bpf prog that does a lot of storage_delete()?

I have not really measured the impact on deletes, My understanding is that it should
not impact the BPF program, but yes, if there are some critical sections that are prolonged
due to a sleepable program "sleeping" too long, then it would pile up the callbacks.

But this is not something new, as we have a similar thing in BPF trampolines. If this really
becomes an issue, we could add a flag BPF_F_SLEEPABLE_STORAGE and only maps with this flag would be allowed in sleepable progs.

We could then wait for both critical sections only when this flag is set on the map.

Quoted 17 lines
Quoted 17 lines
kernel/bpf/bpf_local_storage.c +2 -1
      return free_local_storage;
 }
@@ -154,7 +172,8 @@ static void __bpf_selem_unlink_storage(struct bpf_local_storage_elem *selem)
      raw_spin_unlock_irqrestore(&local_storage->lock, flags);
 
      if (free_local_storage)
-             kfree_rcu(local_storage, rcu);
+             call_rcu_tasks_trace(&local_storage->rcu,
+                                  bpf_local_storage_free_rcu);
 }
 
 void bpf_selem_link_storage_nolock(struct bpf_local_storage *local_storage,
@@ -213,7 +232,8 @@ bpf_local_storage_lookup(struct bpf_local_storage *local_storage,
      struct bpf_local_storage_elem *selem;
 
Quoted 7 lines

kernel/bpf/bpf_local_storage.c bpf_local_storage_lookup(struct bpf_local_storage *local_storage, · line 236

Quoted 4 lines
kernel/bpf/bpf_local_storage.c +2 -1
      /* Fast path (cache hit) */
-     sdata = rcu_dereference(local_storage->cache[smap->cache_idx]);
+     sdata = rcu_dereference_protected(local_storage->cache[smap->cache_idx],
+                                       bpf_local_storage_rcu_lock_held());

There are other places using rcu_dereference() also. e.g. in bpf_local_storage_update().
Should they be changed also?

From what I saw, the other usage of rcu_derference is in a nested (w.r.t to the RCU section that in bpf_prog_enter/exit) RCU
read side critical section/rcu_read_{lock, unlock} so it should not be required.

If there are some that are not, then they need to be updated. Did I miss any?

Quoted 23 lines

[ ... ]

Quoted 20 lines
net/core/bpf_sk_storage.c +3 -1
@@ -13,6 +13,7 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
 
 DEFINE_BPF_STORAGE_CACHE(sk_cache);
 
@@ -22,7 +23,8 @@ bpf_sk_storage_lookup(struct sock *sk, struct bpf_map *map, bool cacheit_lockit)
      struct bpf_local_storage *sk_storage;
      struct bpf_local_storage_map *smap;
 
-     sk_storage = rcu_dereference(sk->sk_bpf_storage);
+     sk_storage = rcu_dereference_protected(sk->sk_bpf_storage,
+                                            bpf_local_storage_rcu_lock_held());
      if (!sk_storage)
              return NULL;
 
Quoted 8 lines

net/core/bpf_sk_storage.c BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk, · line 264

Quoted 6 lines
net/core/bpf_sk_storage.c +1 -0
@@ -258,6 +260,7 @@ BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk,
 {
      struct bpf_local_storage_data *sdata;
 
+     WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
      if (!sk || !sk_fullsock(sk) || flags > BPF_SK_STORAGE_GET_F_CREATE)

sk is protected by rcu_read_lock here.
Is it always safe to access it with the rcu_read_lock_trace alone ?

We don't dereference sk with an rcu_dereference though, is it still the case for tracing and LSM programs? Or is it somehow implicity protected even though we don't
use rcu_dereference since that's just a READ_ONCE + some checks?

Would grabbing a refcount earlier in the code be helpful?

Quoted 3 lines
Quoted 3 lines
net/core/bpf_sk_storage.c +0 -0
              return (unsigned long)NULL;
 
#4 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

On Sun, Aug 29, 2021 at 11:52:03PM +0200, KP Singh wrote:
[ ... ]

Quoted 69 lines
Quoted 56 lines
Quoted 56 lines
kernel/bpf/bpf_local_storage.c +21 -3
index b305270b7a4b..7760bc4e9565 100644
@@ -11,6 +11,8 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
+#include <linux/rcupdate_wait.h>
 
 #define BPF_LOCAL_STORAGE_CREATE_FLAG_MASK (BPF_F_NO_PREALLOC | BPF_F_CLONE)
 
@@ -81,6 +83,22 @@ bpf_selem_alloc(struct bpf_local_storage_map *smap, void *owner,
      return NULL;
 }
 
+void bpf_local_storage_free_rcu(struct rcu_head *rcu)
+{
+     struct bpf_local_storage *local_storage;
+
+     local_storage = container_of(rcu, struct bpf_local_storage, rcu);
+     kfree_rcu(local_storage, rcu);
+}
+
+static void bpf_selem_free_rcu(struct rcu_head *rcu)
+{
+     struct bpf_local_storage_elem *selem;
+
+     selem = container_of(rcu, struct bpf_local_storage_elem, rcu);
+     kfree_rcu(selem, rcu);
+}
+
 /* local_storage->lock must be held and selem->local_storage == local_storage.
  * The caller must ensure selem->smap is still valid to be
  * dereferenced for its smap->elem_size and smap->cache_idx.
@@ -118,12 +136,12 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
               *
               * Although the unlock will be done under
               * rcu_read_lock(),  it is more intutivie to
-              * read if kfree_rcu(local_storage, rcu) is done
+              * read if the freeing of the storage is done
               * after the raw_spin_unlock_bh(&local_storage->lock).
               *
               * Hence, a "bool free_local_storage" is returned
-              * to the caller which then calls the kfree_rcu()
-              * after unlock.
+              * to the caller which then calls then frees the storage after
+              * all the RCU grace periods have expired.
               */
      }
      hlist_del_init_rcu(&selem->snode);
@@ -131,7 +149,7 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
          SDATA(selem))
              RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);
 
Quoted 5 lines

kernel/bpf/bpf_local_storage.c bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage, · line 152

Quoted 2 lines
kernel/bpf/bpf_local_storage.c +1 -1
-     kfree_rcu(selem, rcu);
+     call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);

Although the common use case is usually storage_get() much more often than storage_delete(), do you aware any performance impact for the bpf prog that does a lot of storage_delete()?

I have not really measured the impact on deletes, My understanding is that it should
not impact the BPF program, but yes, if there are some critical sections that are prolonged
due to a sleepable program "sleeping" too long, then it would pile up the callbacks.

Quoted 4 lines

But this is not something new, as we have a similar thing in BPF trampolines. If this really
becomes an issue, we could add a flag BPF_F_SLEEPABLE_STORAGE and only maps with this flag would be allowed in sleepable progs.

Agree that is similar to trampoline updates but not sure it is comparable in terms of the frequency of elems being deleted here. e.g. many short lived tcp connections created by external traffic.

Adding a BPF_F_SLEEPABLE_STORAGE later won't work. It will break existing sleepable bpf prog.

I don't know enough on call_rcu_tasks_trace() here, so the earlier question on perf/callback-pile-up implications in order to decide if extra logic or knob is needed here or not.

Quoted 29 lines

We could then wait for both critical sections only when this flag is set on the map.

Quoted 17 lines
Quoted 17 lines
kernel/bpf/bpf_local_storage.c +2 -1
      return free_local_storage;
 }
@@ -154,7 +172,8 @@ static void __bpf_selem_unlink_storage(struct bpf_local_storage_elem *selem)
      raw_spin_unlock_irqrestore(&local_storage->lock, flags);
 
      if (free_local_storage)
-             kfree_rcu(local_storage, rcu);
+             call_rcu_tasks_trace(&local_storage->rcu,
+                                  bpf_local_storage_free_rcu);
 }
 
 void bpf_selem_link_storage_nolock(struct bpf_local_storage *local_storage,
@@ -213,7 +232,8 @@ bpf_local_storage_lookup(struct bpf_local_storage *local_storage,
      struct bpf_local_storage_elem *selem;
 
Quoted 7 lines

kernel/bpf/bpf_local_storage.c bpf_local_storage_lookup(struct bpf_local_storage *local_storage, · line 236

Quoted 4 lines
kernel/bpf/bpf_local_storage.c +2 -1
      /* Fast path (cache hit) */
-     sdata = rcu_dereference(local_storage->cache[smap->cache_idx]);
+     sdata = rcu_dereference_protected(local_storage->cache[smap->cache_idx],
+                                       bpf_local_storage_rcu_lock_held());

There are other places using rcu_dereference() also. e.g. in bpf_local_storage_update().
Should they be changed also?

Quoted 3 lines

From what I saw, the other usage of rcu_derference is in a nested (w.r.t to the RCU section that in bpf_prog_enter/exit) RCU
read side critical section/rcu_read_{lock, unlock} so it should not be required.

hmm... not sure what nested or not has to do here. It is likely we are talking different things.

Did you turn on the lockdep rcu debugging in kconfig?

afaik, lockdep uses the second "check" argument to WARN on incorrect usage. Even the right check is passed here, the later rcu_dereference() will still complain because it only checks for rcu_read_lock_held().

Also, after another look, why rcu_dereference_protected() is used here instead of rcu_dereference_check()? The spinlock is not acquired here. The same comment goes for similar rcu_dereference_protected() usages.

Quoted 30 lines

If there are some that are not, then they need to be updated. Did I miss any?

Quoted 27 lines

[ ... ]

Quoted 24 lines
net/core/bpf_sk_storage.c +3 -1
@@ -13,6 +13,7 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
 
 DEFINE_BPF_STORAGE_CACHE(sk_cache);
 
@@ -22,7 +23,8 @@ bpf_sk_storage_lookup(struct sock *sk, struct bpf_map *map, bool cacheit_lockit)
      struct bpf_local_storage *sk_storage;
      struct bpf_local_storage_map *smap;
 
-     sk_storage = rcu_dereference(sk->sk_bpf_storage);
+     sk_storage = rcu_dereference_protected(sk->sk_bpf_storage,
+                                            bpf_local_storage_rcu_lock_held());
      if (!sk_storage)
              return NULL;
 
@@ -258,6 +260,7 @@ BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk,
 {
      struct bpf_local_storage_data *sdata;
 
Quoted 8 lines
Quoted 4 lines

net/core/bpf_sk_storage.c BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk, · line 264

Quoted 2 lines
net/core/bpf_sk_storage.c +1 -0
+     WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
      if (!sk || !sk_fullsock(sk) || flags > BPF_SK_STORAGE_GET_F_CREATE)

sk is protected by rcu_read_lock here.
Is it always safe to access it with the rcu_read_lock_trace alone ?

We don't dereference sk with an rcu_dereference though, is it still the case for tracing and LSM programs? Or is it somehow implicity protected even though we don't use rcu_dereference since that's just a READ_ONCE + some checks?

e.g. the bpf_prog (currently run under rcu_read_lock()) may read the sk from req_sk->sk which I don't think the verifier will optimize it out, so as good as READ_ONCE(), iiuc.

The sk here is obtained from the bpf_lsm_socket_* hooks? Those sk should have a refcnt, right? If that is the case, it should be good enough for now.

Quoted 2 lines

Would grabbing a refcount earlier in the code be helpful?

Grab the refcount earlier in the bpf prog itself?
right, it may be what eventually needs to be done
if somehow there is a usecase that the sleepable bpf prog can get a hold on a rcu protected sk.

author
#5 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 81 lines · Martin KaFai Lau

On Sun, Aug 29, 2021 at 11:52:03PM +0200, KP Singh wrote:
[ ... ]

Quoted 69 lines
Quoted 56 lines
Quoted 56 lines
kernel/bpf/bpf_local_storage.c +21 -3
index b305270b7a4b..7760bc4e9565 100644
@@ -11,6 +11,8 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
+#include <linux/rcupdate_wait.h>
 
 #define BPF_LOCAL_STORAGE_CREATE_FLAG_MASK (BPF_F_NO_PREALLOC | BPF_F_CLONE)
 
@@ -81,6 +83,22 @@ bpf_selem_alloc(struct bpf_local_storage_map *smap, void *owner,
      return NULL;
 }
 
+void bpf_local_storage_free_rcu(struct rcu_head *rcu)
+{
+     struct bpf_local_storage *local_storage;
+
+     local_storage = container_of(rcu, struct bpf_local_storage, rcu);
+     kfree_rcu(local_storage, rcu);
+}
+
+static void bpf_selem_free_rcu(struct rcu_head *rcu)
+{
+     struct bpf_local_storage_elem *selem;
+
+     selem = container_of(rcu, struct bpf_local_storage_elem, rcu);
+     kfree_rcu(selem, rcu);
+}
+
 /* local_storage->lock must be held and selem->local_storage == local_storage.
  * The caller must ensure selem->smap is still valid to be
  * dereferenced for its smap->elem_size and smap->cache_idx.
@@ -118,12 +136,12 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
               *
               * Although the unlock will be done under
               * rcu_read_lock(),  it is more intutivie to
-              * read if kfree_rcu(local_storage, rcu) is done
+              * read if the freeing of the storage is done
               * after the raw_spin_unlock_bh(&local_storage->lock).
               *
               * Hence, a "bool free_local_storage" is returned
-              * to the caller which then calls the kfree_rcu()
-              * after unlock.
+              * to the caller which then calls then frees the storage after
+              * all the RCU grace periods have expired.
               */
      }
      hlist_del_init_rcu(&selem->snode);
@@ -131,7 +149,7 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
          SDATA(selem))
              RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);
 
Quoted 5 lines

kernel/bpf/bpf_local_storage.c bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage, · line 152

Quoted 2 lines
kernel/bpf/bpf_local_storage.c +1 -1
-     kfree_rcu(selem, rcu);
+     call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);

Although the common use case is usually storage_get() much more often than storage_delete(), do you aware any performance impact for the bpf prog that does a lot of storage_delete()?

I have not really measured the impact on deletes, My understanding is that it should
not impact the BPF program, but yes, if there are some critical sections that are prolonged
due to a sleepable program "sleeping" too long, then it would pile up the callbacks.

Quoted 4 lines

But this is not something new, as we have a similar thing in BPF trampolines. If this really
becomes an issue, we could add a flag BPF_F_SLEEPABLE_STORAGE and only maps with this flag would be allowed in sleepable progs.

Agree that is similar to trampoline updates but not sure it is comparable in terms of the frequency of elems being deleted here. e.g. many short lived tcp connections created by external traffic.

Quoted 6 lines

Adding a BPF_F_SLEEPABLE_STORAGE later won't work. It will break existing sleepable bpf prog.

I don't know enough on call_rcu_tasks_trace() here, so the earlier question on perf/callback-pile-up implications in order to decide if extra logic or knob is needed here or not.

I will defer to the others, maybe Alexei and Paul, we could also just add the flag to not affect existing performance characteristics?

Quoted 30 lines
Quoted 30 lines

We could then wait for both critical sections only when this flag is set on the map.

Quoted 24 lines
Quoted 15 lines
kernel/bpf/bpf_local_storage.c +2 -1
      return free_local_storage;
 }
@@ -154,7 +172,8 @@ static void __bpf_selem_unlink_storage(struct bpf_local_storage_elem *selem)
      raw_spin_unlock_irqrestore(&local_storage->lock, flags);
 
      if (free_local_storage)
-             kfree_rcu(local_storage, rcu);
+             call_rcu_tasks_trace(&local_storage->rcu,
+                                  bpf_local_storage_free_rcu);
 }
 
 void bpf_selem_link_storage_nolock(struct bpf_local_storage *local_storage,

kernel/bpf/bpf_local_storage.c bpf_local_storage_lookup(struct bpf_local_storage *local_storage, · line 236

Quoted 6 lines
kernel/bpf/bpf_local_storage.c +2 -1
@@ -213,7 +232,8 @@ bpf_local_storage_lookup(struct bpf_local_storage *local_storage,
      struct bpf_local_storage_elem *selem;
 
      /* Fast path (cache hit) */
-     sdata = rcu_dereference(local_storage->cache[smap->cache_idx]);
+     sdata = rcu_dereference_protected(local_storage->cache[smap->cache_idx],
+                                       bpf_local_storage_rcu_lock_held());

There are other places using rcu_dereference() also. e.g. in bpf_local_storage_update().
Should they be changed also?

Quoted 6 lines
Quoted 3 lines

From what I saw, the other usage of rcu_derference is in a nested (w.r.t to the RCU section that in bpf_prog_enter/exit) RCU
read side critical section/rcu_read_{lock, unlock} so it should not be required.

hmm... not sure what nested or not has to do here. It is likely we are talking different things.

Yeah, we were looking at different things.

e.g. bpf_selem_unlink does not need to be changed as it is in a rcu_read_lock.

But you are right there is another in bpf_local_storage_update which I will fix.

Quoted 1 line

Did you turn on the lockdep rcu debugging in kconfig?

Yes I have PROVE_RCU and LOCKDEP

Quoted 10 lines

afaik, lockdep uses the second "check" argument to WARN on incorrect usage. Even the right check is passed here, the later rcu_dereference() will still complain because it only checks for rcu_read_lock_held().

Also, after another look, why rcu_dereference_protected() is used here instead of rcu_dereference_check()? The spinlock is not acquired here. The same comment goes for similar rcu_dereference_protected() usages.

Good catch, it should be rcu_dereference_check.

Quoted 39 lines
Quoted 31 lines

If there are some that are not, then they need to be updated. Did I miss any?

Quoted 27 lines

[ ... ]

Quoted 24 lines
net/core/bpf_sk_storage.c +3 -1
@@ -13,6 +13,7 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
 
 DEFINE_BPF_STORAGE_CACHE(sk_cache);
 
@@ -22,7 +23,8 @@ bpf_sk_storage_lookup(struct sock *sk, struct bpf_map *map, bool cacheit_lockit)
      struct bpf_local_storage *sk_storage;
      struct bpf_local_storage_map *smap;
 
-     sk_storage = rcu_dereference(sk->sk_bpf_storage);
+     sk_storage = rcu_dereference_protected(sk->sk_bpf_storage,
+                                            bpf_local_storage_rcu_lock_held());
      if (!sk_storage)
              return NULL;
 
@@ -258,6 +260,7 @@ BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk,
 {
      struct bpf_local_storage_data *sdata;
 
Quoted 8 lines
Quoted 4 lines

net/core/bpf_sk_storage.c BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk, · line 264

Quoted 2 lines
net/core/bpf_sk_storage.c +1 -0
+     WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
      if (!sk || !sk_fullsock(sk) || flags > BPF_SK_STORAGE_GET_F_CREATE)

sk is protected by rcu_read_lock here.
Is it always safe to access it with the rcu_read_lock_trace alone ?

We don't dereference sk with an rcu_dereference though, is it still the case for tracing and LSM programs? Or is it somehow implicity protected even though we don't use rcu_dereference since that's just a READ_ONCE + some checks?

Quoted 6 lines

e.g. the bpf_prog (currently run under rcu_read_lock()) may read the sk from req_sk->sk which I don't think the verifier will optimize it out, so as good as READ_ONCE(), iiuc.

The sk here is obtained from the bpf_lsm_socket_* hooks? Those sk should have a refcnt, right? If that is the case, it should be good enough for now.

The one passed in the arguments yes, but if you notice the discussion in

https://lore.kernel.org/bpf/[email protected]/T/#me254212a125516a6c5d2fbf349b97c199e66dce0

one may also get an sk in LSM and tracing progs by pointer walking.

Quoted 7 lines
Quoted 3 lines

Would grabbing a refcount earlier in the code be helpful?

Grab the refcount earlier in the bpf prog itself?
right, it may be what eventually needs to be done
if somehow there is a usecase that the sleepable bpf prog can get a hold on a rcu protected sk.

#6 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 85 lines · KP Singh
Quoted 84 lines · Martin KaFai Lau

On Sun, Aug 29, 2021 at 11:52:03PM +0200, KP Singh wrote:
[ ... ]

Quoted 69 lines
Quoted 56 lines
Quoted 56 lines
kernel/bpf/bpf_local_storage.c +21 -3
index b305270b7a4b..7760bc4e9565 100644
@@ -11,6 +11,8 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
+#include <linux/rcupdate_wait.h>
 
 #define BPF_LOCAL_STORAGE_CREATE_FLAG_MASK (BPF_F_NO_PREALLOC | BPF_F_CLONE)
 
@@ -81,6 +83,22 @@ bpf_selem_alloc(struct bpf_local_storage_map *smap, void *owner,
      return NULL;
 }
 
+void bpf_local_storage_free_rcu(struct rcu_head *rcu)
+{
+     struct bpf_local_storage *local_storage;
+
+     local_storage = container_of(rcu, struct bpf_local_storage, rcu);
+     kfree_rcu(local_storage, rcu);
+}
+
+static void bpf_selem_free_rcu(struct rcu_head *rcu)
+{
+     struct bpf_local_storage_elem *selem;
+
+     selem = container_of(rcu, struct bpf_local_storage_elem, rcu);
+     kfree_rcu(selem, rcu);
+}
+
 /* local_storage->lock must be held and selem->local_storage == local_storage.
  * The caller must ensure selem->smap is still valid to be
  * dereferenced for its smap->elem_size and smap->cache_idx.
@@ -118,12 +136,12 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
               *
               * Although the unlock will be done under
               * rcu_read_lock(),  it is more intutivie to
-              * read if kfree_rcu(local_storage, rcu) is done
+              * read if the freeing of the storage is done
               * after the raw_spin_unlock_bh(&local_storage->lock).
               *
               * Hence, a "bool free_local_storage" is returned
-              * to the caller which then calls the kfree_rcu()
-              * after unlock.
+              * to the caller which then calls then frees the storage after
+              * all the RCU grace periods have expired.
               */
      }
      hlist_del_init_rcu(&selem->snode);
@@ -131,7 +149,7 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
          SDATA(selem))
              RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);
 
Quoted 5 lines

kernel/bpf/bpf_local_storage.c bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage, · line 152

Quoted 2 lines
kernel/bpf/bpf_local_storage.c +1 -1
-     kfree_rcu(selem, rcu);
+     call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);

Although the common use case is usually storage_get() much more often than storage_delete(), do you aware any performance impact for the bpf prog that does a lot of storage_delete()?

I have not really measured the impact on deletes, My understanding is that it should
not impact the BPF program, but yes, if there are some critical sections that are prolonged
due to a sleepable program "sleeping" too long, then it would pile up the callbacks.

Quoted 4 lines

But this is not something new, as we have a similar thing in BPF trampolines. If this really
becomes an issue, we could add a flag BPF_F_SLEEPABLE_STORAGE and only maps with this flag would be allowed in sleepable progs.

Agree that is similar to trampoline updates but not sure it is comparable in terms of the frequency of elems being deleted here. e.g. many short lived tcp connections created by external traffic.

Adding a BPF_F_SLEEPABLE_STORAGE later won't work. It will break existing sleepable bpf prog.

Quoted 8 lines
Quoted 3 lines

I don't know enough on call_rcu_tasks_trace() here, so the earlier question on perf/callback-pile-up implications in order to decide if extra logic or knob is needed here or not.

I will defer to the others, maybe Alexei and Paul,

we could also just
add the flag to not affect existing performance characteristics?

I would see if it is really necessary first. Other sleepable supported maps do not need a flag. Adding one here for local storage will be confusing especially if it turns out to be unnecessary.

Could you run some tests first which can guide the decision?

Quoted 34 lines
Quoted 34 lines
Quoted 34 lines

We could then wait for both critical sections only when this flag is set on the map.

Quoted 17 lines
Quoted 17 lines
kernel/bpf/bpf_local_storage.c +2 -1
      return free_local_storage;
 }
@@ -154,7 +172,8 @@ static void __bpf_selem_unlink_storage(struct bpf_local_storage_elem *selem)
      raw_spin_unlock_irqrestore(&local_storage->lock, flags);
 
      if (free_local_storage)
-             kfree_rcu(local_storage, rcu);
+             call_rcu_tasks_trace(&local_storage->rcu,
+                                  bpf_local_storage_free_rcu);
 }
 
 void bpf_selem_link_storage_nolock(struct bpf_local_storage *local_storage,
@@ -213,7 +232,8 @@ bpf_local_storage_lookup(struct bpf_local_storage *local_storage,
      struct bpf_local_storage_elem *selem;
 
Quoted 7 lines

kernel/bpf/bpf_local_storage.c bpf_local_storage_lookup(struct bpf_local_storage *local_storage, · line 236

Quoted 4 lines
kernel/bpf/bpf_local_storage.c +2 -1
      /* Fast path (cache hit) */
-     sdata = rcu_dereference(local_storage->cache[smap->cache_idx]);
+     sdata = rcu_dereference_protected(local_storage->cache[smap->cache_idx],
+                                       bpf_local_storage_rcu_lock_held());

There are other places using rcu_dereference() also. e.g. in bpf_local_storage_update().
Should they be changed also?

From what I saw, the other usage of rcu_derference is in a nested (w.r.t to the RCU section that in bpf_prog_enter/exit) RCU
read side critical section/rcu_read_{lock, unlock} so it should not be required.

Quoted 7 lines
Quoted 3 lines

hmm... not sure what nested or not has to do here. It is likely we are talking different things.

Yeah, we were looking at different things.

e.g. bpf_selem_unlink does not need to be changed as it is in a rcu_read_lock.

No. It is not always under rcu_read_lock(). From the patch 2 test, it should have a splat either from bpf_inode_storage_delete() or bpf_sk_storage_delete(), depending on which one runs first.

Quoted 63 lines

But you are right there is another in bpf_local_storage_update which I will fix.

Quoted 1 line

Did you turn on the lockdep rcu debugging in kconfig?

Yes I have PROVE_RCU and LOCKDEP

Quoted 10 lines

afaik, lockdep uses the second "check" argument to WARN on incorrect usage. Even the right check is passed here, the later rcu_dereference() will still complain because it only checks for rcu_read_lock_held().

Also, after another look, why rcu_dereference_protected() is used here instead of rcu_dereference_check()? The spinlock is not acquired here. The same comment goes for similar rcu_dereference_protected() usages.

Good catch, it should be rcu_dereference_check.

Quoted 43 lines
Quoted 31 lines

If there are some that are not, then they need to be updated. Did I miss any?

Quoted 27 lines

[ ... ]

Quoted 24 lines
net/core/bpf_sk_storage.c +3 -1
@@ -13,6 +13,7 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
 
 DEFINE_BPF_STORAGE_CACHE(sk_cache);
 
@@ -22,7 +23,8 @@ bpf_sk_storage_lookup(struct sock *sk, struct bpf_map *map, bool cacheit_lockit)
      struct bpf_local_storage *sk_storage;
      struct bpf_local_storage_map *smap;
 
-     sk_storage = rcu_dereference(sk->sk_bpf_storage);
+     sk_storage = rcu_dereference_protected(sk->sk_bpf_storage,
+                                            bpf_local_storage_rcu_lock_held());
      if (!sk_storage)
              return NULL;
 
@@ -258,6 +260,7 @@ BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk,
 {
      struct bpf_local_storage_data *sdata;
 
Quoted 8 lines
Quoted 4 lines

net/core/bpf_sk_storage.c BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk, · line 264

Quoted 2 lines
net/core/bpf_sk_storage.c +1 -0
+     WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
      if (!sk || !sk_fullsock(sk) || flags > BPF_SK_STORAGE_GET_F_CREATE)

sk is protected by rcu_read_lock here.
Is it always safe to access it with the rcu_read_lock_trace alone ?

We don't dereference sk with an rcu_dereference though, is it still the case for tracing and LSM programs? Or is it somehow implicity protected even though we don't use rcu_dereference since that's just a READ_ONCE + some checks?

e.g. the bpf_prog (currently run under rcu_read_lock()) may read the sk from req_sk->sk which I don't think the verifier will optimize it out, so as good as READ_ONCE(), iiuc.

Quoted 8 lines
Quoted 2 lines

The sk here is obtained from the bpf_lsm_socket_* hooks? Those sk should have a refcnt, right? If that is the case, it should be good enough for now.

The one passed in the arguments yes, but if you notice the discussion in

https://lore.kernel.org/bpf/[email protected]/T/#me254212a125516a6c5d2fbf349b97c199e66dce0

one may also get an sk in LSM and tracing progs by pointer walking.

Right. There is pointer walking case.
e.g. "struct request_sock __rcu *fastopen_rsk" in tcp_sock. I don't think it is possible for lsm to get a hold on tcp_sock but agree that other similar cases could happen.

May be for now, in sleepable program, only allow safe sk ptr
to be used in helpers that take sk PTR_TO_BTF_ID argument.
e.g. sock->sk is safe in the test in patch 2. The same should go for other storages like inode. This needs verifier change.

In the very near future, it can move to Yonghong's (cc) btf tagging solution to tag a particular member of a struct to make this verifier checking more generic.

author
#7 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 93 lines · Martin KaFai Lau
Quoted 90 lines · KP Singh
Quoted 81 lines · Martin KaFai Lau

On Sun, Aug 29, 2021 at 11:52:03PM +0200, KP Singh wrote:
[ ... ]

Quoted 69 lines
Quoted 56 lines
Quoted 56 lines
kernel/bpf/bpf_local_storage.c +21 -3
index b305270b7a4b..7760bc4e9565 100644
@@ -11,6 +11,8 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
+#include <linux/rcupdate_wait.h>
 
 #define BPF_LOCAL_STORAGE_CREATE_FLAG_MASK (BPF_F_NO_PREALLOC | BPF_F_CLONE)
 
@@ -81,6 +83,22 @@ bpf_selem_alloc(struct bpf_local_storage_map *smap, void *owner,
      return NULL;
 }
 
+void bpf_local_storage_free_rcu(struct rcu_head *rcu)
+{
+     struct bpf_local_storage *local_storage;
+
+     local_storage = container_of(rcu, struct bpf_local_storage, rcu);
+     kfree_rcu(local_storage, rcu);
+}
+
+static void bpf_selem_free_rcu(struct rcu_head *rcu)
+{
+     struct bpf_local_storage_elem *selem;
+
+     selem = container_of(rcu, struct bpf_local_storage_elem, rcu);
+     kfree_rcu(selem, rcu);
+}
+
 /* local_storage->lock must be held and selem->local_storage == local_storage.
  * The caller must ensure selem->smap is still valid to be
  * dereferenced for its smap->elem_size and smap->cache_idx.
@@ -118,12 +136,12 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
               *
               * Although the unlock will be done under
               * rcu_read_lock(),  it is more intutivie to
-              * read if kfree_rcu(local_storage, rcu) is done
+              * read if the freeing of the storage is done
               * after the raw_spin_unlock_bh(&local_storage->lock).
               *
               * Hence, a "bool free_local_storage" is returned
-              * to the caller which then calls the kfree_rcu()
-              * after unlock.
+              * to the caller which then calls then frees the storage after
+              * all the RCU grace periods have expired.
               */
      }
      hlist_del_init_rcu(&selem->snode);
@@ -131,7 +149,7 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
          SDATA(selem))
              RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);
 
Quoted 5 lines

kernel/bpf/bpf_local_storage.c bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage, · line 152

Quoted 2 lines
kernel/bpf/bpf_local_storage.c +1 -1
-     kfree_rcu(selem, rcu);
+     call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);

Although the common use case is usually storage_get() much more often than storage_delete(), do you aware any performance impact for the bpf prog that does a lot of storage_delete()?

I have not really measured the impact on deletes, My understanding is that it should
not impact the BPF program, but yes, if there are some critical sections that are prolonged
due to a sleepable program "sleeping" too long, then it would pile up the callbacks.

Quoted 4 lines

But this is not something new, as we have a similar thing in BPF trampolines. If this really
becomes an issue, we could add a flag BPF_F_SLEEPABLE_STORAGE and only maps with this flag would be allowed in sleepable progs.

Agree that is similar to trampoline updates but not sure it is comparable in terms of the frequency of elems being deleted here. e.g. many short lived tcp connections created by external traffic.

Quoted 6 lines

Adding a BPF_F_SLEEPABLE_STORAGE later won't work. It will break existing sleepable bpf prog.

I don't know enough on call_rcu_tasks_trace() here, so the earlier question on perf/callback-pile-up implications in order to decide if extra logic or knob is needed here or not.

I will defer to the others, maybe Alexei and Paul,

Quoted 8 lines
Quoted 2 lines

we could also just
add the flag to not affect existing performance characteristics?

I would see if it is really necessary first. Other sleepable supported maps do not need a flag. Adding one here for local storage will be confusing especially if it turns out to be unnecessary.

Could you run some tests first which can guide the decision?

I think the performance impact would happen only in the worst case which needs some work to simulate. What do you think about:

A bprm_committed_creds program that processes a large argv and also gets a storage on the inode.

A file_open program that tries to delete the local storage on the inode.

Trigger this code in parallel. i.e. lots of programs that execute with a very large argv and then in parallel the executable being opened to trigger the delete.

Do you have any other ideas? Is there something we could re-use from the selftests?

Quoted 38 lines
Quoted 38 lines
Quoted 38 lines
Quoted 32 lines

We could then wait for both critical sections only when this flag is set on the map.

Quoted 17 lines
Quoted 17 lines
kernel/bpf/bpf_local_storage.c +2 -1
      return free_local_storage;
 }
@@ -154,7 +172,8 @@ static void __bpf_selem_unlink_storage(struct bpf_local_storage_elem *selem)
      raw_spin_unlock_irqrestore(&local_storage->lock, flags);
 
      if (free_local_storage)
-             kfree_rcu(local_storage, rcu);
+             call_rcu_tasks_trace(&local_storage->rcu,
+                                  bpf_local_storage_free_rcu);
 }
 
 void bpf_selem_link_storage_nolock(struct bpf_local_storage *local_storage,
@@ -213,7 +232,8 @@ bpf_local_storage_lookup(struct bpf_local_storage *local_storage,
      struct bpf_local_storage_elem *selem;
 
Quoted 7 lines

kernel/bpf/bpf_local_storage.c bpf_local_storage_lookup(struct bpf_local_storage *local_storage, · line 236

Quoted 4 lines
kernel/bpf/bpf_local_storage.c +2 -1
      /* Fast path (cache hit) */
-     sdata = rcu_dereference(local_storage->cache[smap->cache_idx]);
+     sdata = rcu_dereference_protected(local_storage->cache[smap->cache_idx],
+                                       bpf_local_storage_rcu_lock_held());

There are other places using rcu_dereference() also. e.g. in bpf_local_storage_update().
Should they be changed also?

Quoted 3 lines

From what I saw, the other usage of rcu_derference is in a nested (w.r.t to the RCU section that in bpf_prog_enter/exit) RCU
read side critical section/rcu_read_{lock, unlock} so it should not be required.

hmm... not sure what nested or not has to do here. It is likely we are talking different things.

Quoted 7 lines
Quoted 4 lines

Yeah, we were looking at different things.

e.g. bpf_selem_unlink does not need to be changed as it is in a rcu_read_lock.

No. It is not always under rcu_read_lock(). From the patch 2 test, it should have a splat either from bpf_inode_storage_delete() or bpf_sk_storage_delete(), depending on which one runs first.

I missed this one, but I wonder why it did not trigger a warning. The test does exercise the delete and rcu_dereference should have warned me that I am not holding an rcu_read_lock();

Quoted 77 lines
Quoted 64 lines

But you are right there is another in bpf_local_storage_update which I will fix.

Quoted 1 line

Did you turn on the lockdep rcu debugging in kconfig?

Yes I have PROVE_RCU and LOCKDEP

Quoted 10 lines

afaik, lockdep uses the second "check" argument to WARN on incorrect usage. Even the right check is passed here, the later rcu_dereference() will still complain because it only checks for rcu_read_lock_held().

Also, after another look, why rcu_dereference_protected() is used here instead of rcu_dereference_check()? The spinlock is not acquired here. The same comment goes for similar rcu_dereference_protected() usages.

Good catch, it should be rcu_dereference_check.

Quoted 43 lines
Quoted 31 lines

If there are some that are not, then they need to be updated. Did I miss any?

Quoted 27 lines

[ ... ]

Quoted 24 lines
net/core/bpf_sk_storage.c +3 -1
@@ -13,6 +13,7 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
 
 DEFINE_BPF_STORAGE_CACHE(sk_cache);
 
@@ -22,7 +23,8 @@ bpf_sk_storage_lookup(struct sock *sk, struct bpf_map *map, bool cacheit_lockit)
      struct bpf_local_storage *sk_storage;
      struct bpf_local_storage_map *smap;
 
-     sk_storage = rcu_dereference(sk->sk_bpf_storage);
+     sk_storage = rcu_dereference_protected(sk->sk_bpf_storage,
+                                            bpf_local_storage_rcu_lock_held());
      if (!sk_storage)
              return NULL;
 
@@ -258,6 +260,7 @@ BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk,
 {
      struct bpf_local_storage_data *sdata;
 
Quoted 8 lines
Quoted 4 lines

net/core/bpf_sk_storage.c BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk, · line 264

Quoted 2 lines
net/core/bpf_sk_storage.c +1 -0
+     WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
      if (!sk || !sk_fullsock(sk) || flags > BPF_SK_STORAGE_GET_F_CREATE)

sk is protected by rcu_read_lock here.
Is it always safe to access it with the rcu_read_lock_trace alone ?

We don't dereference sk with an rcu_dereference though, is it still the case for tracing and LSM programs? Or is it somehow implicity protected even though we don't use rcu_dereference since that's just a READ_ONCE + some checks?

e.g. the bpf_prog (currently run under rcu_read_lock()) may read the sk from req_sk->sk which I don't think the verifier will optimize it out, so as good as READ_ONCE(), iiuc.

Quoted 8 lines
Quoted 2 lines

The sk here is obtained from the bpf_lsm_socket_* hooks? Those sk should have a refcnt, right? If that is the case, it should be good enough for now.

The one passed in the arguments yes, but if you notice the discussion in

https://lore.kernel.org/bpf/[email protected]/T/#me254212a125516a6c5d2fbf349b97c199e66dce0

one may also get an sk in LSM and tracing progs by pointer walking.

Right. There is pointer walking case.
e.g. "struct request_sock __rcu *fastopen_rsk" in tcp_sock. I don't think it is possible for lsm to get a hold on tcp_sock but agree that other similar cases could happen.

Quoted 5 lines

May be for now, in sleepable program, only allow safe sk ptr
to be used in helpers that take sk PTR_TO_BTF_ID argument.
e.g. sock->sk is safe in the test in patch 2. The same should go for other storages like inode. This needs verifier change.

Sorry, I may be missing some context. Do you mean wait for Yonghong's work?

Or is there another way to update the verifier to recognize safe sk and inode pointers?

Quoted 3 lines

In the very near future, it can move to Yonghong's (cc) btf tagging solution to tag a particular member of a struct to make this verifier checking more generic.

#8 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

On Tue, Aug 31, 2021 at 09:38:01PM +0200, KP Singh wrote:
[ ... ]

Quoted 49 lines
Quoted 34 lines
Quoted 33 lines
Quoted 25 lines
Quoted 17 lines
Quoted 9 lines

Review bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage, · line 152

Quoted 6 lines
(quoted diff) +1 -1
@@ -131,7 +149,7 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
          SDATA(selem))
              RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);
 
-     kfree_rcu(selem, rcu);
+     call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);

Although the common use case is usually storage_get() much more often than storage_delete(), do you aware any performance impact for the bpf prog that does a lot of storage_delete()?

I have not really measured the impact on deletes, My understanding is that it should
not impact the BPF program, but yes, if there are some critical sections that are prolonged
due to a sleepable program "sleeping" too long, then it would pile up the callbacks.

Quoted 4 lines

But this is not something new, as we have a similar thing in BPF trampolines. If this really
becomes an issue, we could add a flag BPF_F_SLEEPABLE_STORAGE and only maps with this flag would be allowed in sleepable progs.

Agree that is similar to trampoline updates but not sure it is comparable in terms of the frequency of elems being deleted here. e.g. many short lived tcp connections created by external traffic.

Quoted 6 lines

Adding a BPF_F_SLEEPABLE_STORAGE later won't work. It will break existing sleepable bpf prog.

I don't know enough on call_rcu_tasks_trace() here, so the earlier question on perf/callback-pile-up implications in order to decide if extra logic or knob is needed here or not.

I will defer to the others, maybe Alexei and Paul,

Quoted 8 lines
Quoted 2 lines

we could also just
add the flag to not affect existing performance characteristics?

I would see if it is really necessary first. Other sleepable supported maps do not need a flag. Adding one here for local storage will be confusing especially if it turns out to be unnecessary.

Could you run some tests first which can guide the decision?

I think the performance impact would happen only in the worst case which needs some work to simulate. What do you think about:

A bprm_committed_creds program that processes a large argv and also gets a storage on the inode.

Quoted 8 lines

A file_open program that tries to delete the local storage on the inode.

Trigger this code in parallel. i.e. lots of programs that execute with a very large argv and then in parallel the executable being opened to trigger the delete.

Do you have any other ideas? Is there something we could re-use from the selftests?

There is a bench framework in tools/testing/selftests/bpf/benchs/ that has a parallel thread setup which could be useful.

Don't know how to simulate the "sleeping" too long which then pile-up callbacks. This is not bpf specific. Paul, I wonder if you have similar test to trigger this to compare between call_rcu_tasks_trace() and call_rcu()?

[ ... ]

Quoted 21 lines
Quoted 21 lines
Quoted 21 lines
Quoted 11 lines
Quoted 11 lines
Quoted 10 lines

Review bpf_local_storage_lookup(struct bpf_local_storage *local_storage, · line 236

Quoted 7 lines
(quoted diff) +2 -1
@@ -213,7 +232,8 @@ bpf_local_storage_lookup(struct bpf_local_storage *local_storage,
      struct bpf_local_storage_elem *selem;
 
      /* Fast path (cache hit) */
-     sdata = rcu_dereference(local_storage->cache[smap->cache_idx]);
+     sdata = rcu_dereference_protected(local_storage->cache[smap->cache_idx],
+                                       bpf_local_storage_rcu_lock_held());

There are other places using rcu_dereference() also. e.g. in bpf_local_storage_update().
Should they be changed also?

Quoted 6 lines
Quoted 3 lines

From what I saw, the other usage of rcu_derference is in a nested (w.r.t to the RCU section that in bpf_prog_enter/exit) RCU
read side critical section/rcu_read_{lock, unlock} so it should not be required.

hmm... not sure what nested or not has to do here. It is likely we are talking different things.

Yeah, we were looking at different things.

e.g. bpf_selem_unlink does not need to be changed as it is in a rcu_read_lock.

Quoted 7 lines
Quoted 3 lines

No. It is not always under rcu_read_lock(). From the patch 2 test, it should have a splat either from bpf_inode_storage_delete() or bpf_sk_storage_delete(), depending on which one runs first.

I missed this one, but I wonder why it did not trigger a warning. The test does exercise the delete and rcu_dereference should have warned me that I am not holding an rcu_read_lock();

hmm... not sure either. may be some kconfigs that disabled rcu_read_lock_held()? I would also take a look at RCU_LOCKDEP_WARN().

I just quickly tried the patches to check:

[  143.376587] =============================
[  143.377068] WARNING: suspicious RCU usage
[  143.377541] 5.14.0-rc5-01271-g68e5bda2b18e #4966 Tainted: G           O
[  143.378378] -----------------------------
[  143.378857] kernel/bpf/bpf_local_storage.c:114 suspicious rcu_dereference_check() usage!
[  143.379914]
[  143.379914] other info that might help us debug this:
[  143.379914]
[  143.380838]
[  143.380838] rcu_scheduler_active = 2, debug_locks = 1
[  143.381602] 4 locks held by mv/1781:
[  143.382025]  #0: ffff888121e7c438 (sb_writers#6){.+.+}-{0:0}, at: do_renameat2+0x2f5/0xa80
[  143.383009]  #1: ffff88812ce68760 (&type->i_mutex_dir_key#5/1){+.+.}-{3:3}, at: lock_rename+0x1f4/0x250
[  143.384144]  #2: ffffffff843fbc60 (rcu_read_lock_trace){....}-{0:0}, at: __bpf_prog_enter_sleepable+0x45/0x160
[  143.385326]  #3: ffff88811d8348b8 (&storage->lock){..-.}-{2:2}, at: __bpf_selem_unlink_storage+0x7d/0x170
[  143.386459]
[  143.386459] stack backtrace:
[  143.386983] CPU: 2 PID: 1781 Comm: mv Tainted: G           O      5.14.0-rc5-01271-g68e5bda2b18e #4966
[  143.388071] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.9.3-1.el7.centos 04/01/2014
[  143.389146] Call Trace:
[  143.389446]  dump_stack_lvl+0x5b/0x82
[  143.389901]  dump_stack+0x10/0x12
[  143.390302]  lockdep_rcu_suspicious+0x15c/0x167
[  143.390854]  bpf_selem_unlink_storage_nolock+0x2e1/0x6d0
[  143.391501]  __bpf_selem_unlink_storage+0xb7/0x170
[  143.392085]  bpf_selem_unlink+0x1b/0x30
[  143.392554]  bpf_inode_storage_delete+0x57/0xa0
[  143.393112]  bpf_prog_31e277fe2c132665_inode_rename+0x9c/0x268
[  143.393814]  bpf_trampoline_6442476301_0+0x4e/0x1000
[  143.394413]  bpf_lsm_inode_rename+0x5/0x10
Quoted 49 lines
Quoted 49 lines
Quoted 36 lines
Quoted 36 lines
Quoted 24 lines
Quoted 24 lines
Quoted 24 lines
net/core/bpf_sk_storage.c +3 -1
@@ -13,6 +13,7 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
 
 DEFINE_BPF_STORAGE_CACHE(sk_cache);
 
@@ -22,7 +23,8 @@ bpf_sk_storage_lookup(struct sock *sk, struct bpf_map *map, bool cacheit_lockit)
      struct bpf_local_storage *sk_storage;
      struct bpf_local_storage_map *smap;
 
-     sk_storage = rcu_dereference(sk->sk_bpf_storage);
+     sk_storage = rcu_dereference_protected(sk->sk_bpf_storage,
+                                            bpf_local_storage_rcu_lock_held());
      if (!sk_storage)
              return NULL;
 
@@ -258,6 +260,7 @@ BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk,
 {
      struct bpf_local_storage_data *sdata;
 
Quoted 8 lines
Quoted 4 lines

net/core/bpf_sk_storage.c BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk, · line 264

Quoted 2 lines
net/core/bpf_sk_storage.c +1 -0
+     WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
      if (!sk || !sk_fullsock(sk) || flags > BPF_SK_STORAGE_GET_F_CREATE)

sk is protected by rcu_read_lock here.
Is it always safe to access it with the rcu_read_lock_trace alone ?

We don't dereference sk with an rcu_dereference though, is it still the case for tracing and LSM programs? Or is it somehow implicity protected even though we don't use rcu_dereference since that's just a READ_ONCE + some checks?

e.g. the bpf_prog (currently run under rcu_read_lock()) may read the sk from req_sk->sk which I don't think the verifier will optimize it out, so as good as READ_ONCE(), iiuc.

Quoted 8 lines
Quoted 2 lines

The sk here is obtained from the bpf_lsm_socket_* hooks? Those sk should have a refcnt, right? If that is the case, it should be good enough for now.

The one passed in the arguments yes, but if you notice the discussion in

https://lore.kernel.org/bpf/[email protected]/T/#me254212a125516a6c5d2fbf349b97c199e66dce0

one may also get an sk in LSM and tracing progs by pointer walking.

Right. There is pointer walking case.
e.g. "struct request_sock __rcu *fastopen_rsk" in tcp_sock. I don't think it is possible for lsm to get a hold on tcp_sock but agree that other similar cases could happen.

Quoted 7 lines
Quoted 5 lines

May be for now, in sleepable program, only allow safe sk ptr
to be used in helpers that take sk PTR_TO_BTF_ID argument.
e.g. sock->sk is safe in the test in patch 2. The same should go for other storages like inode. This needs verifier change.

Sorry, I may be missing some context. Do you mean wait for Yonghong's work?

I don't think we have to wait. Just saying Yonghong's work could fit well in this use case in the future.

Quoted 2 lines

Or is there another way to update the verifier to recognize safe sk and inode pointers?

I was thinking specifically for this pointer walking case. Take a look at btf_struct_access(). It walks the struct
in the verifier and figures out reading sock->sk will get
a "struct sock *". It marks the reg to PTR_TO_BTF_ID.
This will allow the bpf prog to directly read from sk (e.g. sk->sk_num) or pass the sk to helper that takes a "struct sock *" pointer. Reading from any sk pointer is fine since it is protected by BPF_PROBE_MEM read. However, we only allow the sk from sock->sk to be passed to the helper here because we only know this one is refcnt-ed.

Take a look at check_ptr_to_btf_access(). An individual verifier_ops can also have its own btf_struct_access. One possibility is to introduce a (new) PTR_TO_RDONLY_BTF_ID to mean it can only do BPR_PROBE_MEM read but cannot be used in helper.

#9 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 61 lines · Martin KaFai Lau

On Tue, Aug 31, 2021 at 09:38:01PM +0200, KP Singh wrote:
[ ... ]

Quoted 49 lines
Quoted 34 lines
Quoted 33 lines
Quoted 25 lines
Quoted 17 lines
Quoted 9 lines

Review bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage, · line 152

Quoted 6 lines
(quoted diff) +1 -1
@@ -131,7 +149,7 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
          SDATA(selem))
              RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);
 
-     kfree_rcu(selem, rcu);
+     call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);

Although the common use case is usually storage_get() much more often than storage_delete(), do you aware any performance impact for the bpf prog that does a lot of storage_delete()?

I have not really measured the impact on deletes, My understanding is that it should
not impact the BPF program, but yes, if there are some critical sections that are prolonged
due to a sleepable program "sleeping" too long, then it would pile up the callbacks.

Quoted 4 lines

But this is not something new, as we have a similar thing in BPF trampolines. If this really
becomes an issue, we could add a flag BPF_F_SLEEPABLE_STORAGE and only maps with this flag would be allowed in sleepable progs.

Agree that is similar to trampoline updates but not sure it is comparable in terms of the frequency of elems being deleted here. e.g. many short lived tcp connections created by external traffic.

Quoted 6 lines

Adding a BPF_F_SLEEPABLE_STORAGE later won't work. It will break existing sleepable bpf prog.

I don't know enough on call_rcu_tasks_trace() here, so the earlier question on perf/callback-pile-up implications in order to decide if extra logic or knob is needed here or not.

I will defer to the others, maybe Alexei and Paul,

Quoted 8 lines
Quoted 2 lines

we could also just
add the flag to not affect existing performance characteristics?

I would see if it is really necessary first. Other sleepable supported maps do not need a flag. Adding one here for local storage will be confusing especially if it turns out to be unnecessary.

Could you run some tests first which can guide the decision?

I think the performance impact would happen only in the worst case which needs some work to simulate. What do you think about:

A bprm_committed_creds program that processes a large argv and also gets a storage on the inode.

Quoted 8 lines

A file_open program that tries to delete the local storage on the inode.

Trigger this code in parallel. i.e. lots of programs that execute with a very large argv and then in parallel the executable being opened to trigger the delete.

Do you have any other ideas? Is there something we could re-use from the selftests?

Quoted 7 lines

There is a bench framework in tools/testing/selftests/bpf/benchs/ that has a parallel thread setup which could be useful.

Don't know how to simulate the "sleeping" too long which then pile-up callbacks. This is not bpf specific. Paul, I wonder if you have similar test to trigger this to compare between call_rcu_tasks_trace() and call_rcu()?

It is definitely the case that call_rcu() is way more scalable than is call_rcu_tasks_trace(). Something about call_rcu_tasks_trace() acquiring a global lock. ;-)

So actually testing it makes a lot of sense.

I do have an rcuscale module, but it is set up more for synchronous grace periods such as synchronize_rcu() and synchronize_rcu_tasks_trace(). It has the beginnings of support for call_rcu() and call_rcu_tasks_trace(), but I would not yet trust them.

But I also have a test for global locking:

$ tools/testing/selftests/rcutorture/bin/kvm.sh --torture refscale --allcpus --duration 5 --configs "NOPREEMPT" --kconfig "CONFIG_NR_CPUS=16" --bootargs "refscale.scale_type=lock refscale.loops=10000 refscale.holdoff=20 torture.disable_onoff_at_boot" --trust-make

This gives a median lock overhead of 960ns. Running a single CPU rather than 16 of them:

$ tools/testing/selftests/rcutorture/bin/kvm.sh --torture refscale --allcpus --duration 5 --configs "NOPREEMPT" --kconfig "CONFIG_NR_CPUS=16" --bootargs "refscale.scale_type=lock refscale.loops=10000 refscale.holdoff=20 torture.disable_onoff_at_boot" --trust-make

This gives a median lock overhead of 4.1ns, which is way faster. And the greater the number of CPUs, the greater the lock overhead.

On the other hand, if each call to call_rcu_tasks_trace() involves a fork()/exec() pair, I would be rather surprised if that global lock was your bottleneck.

Of course, if call_rcu_tasks_trace() does prove to be a bottleneck, there are of course things that can be done.

Quoted 57 lines

[ ... ]

Quoted 21 lines
Quoted 21 lines
Quoted 21 lines
Quoted 11 lines
Quoted 11 lines
Quoted 10 lines

Review bpf_local_storage_lookup(struct bpf_local_storage *local_storage, · line 236

Quoted 7 lines
(quoted diff) +2 -1
@@ -213,7 +232,8 @@ bpf_local_storage_lookup(struct bpf_local_storage *local_storage,
      struct bpf_local_storage_elem *selem;
 
      /* Fast path (cache hit) */
-     sdata = rcu_dereference(local_storage->cache[smap->cache_idx]);
+     sdata = rcu_dereference_protected(local_storage->cache[smap->cache_idx],
+                                       bpf_local_storage_rcu_lock_held());

There are other places using rcu_dereference() also. e.g. in bpf_local_storage_update().
Should they be changed also?

Quoted 6 lines
Quoted 3 lines

From what I saw, the other usage of rcu_derference is in a nested (w.r.t to the RCU section that in bpf_prog_enter/exit) RCU
read side critical section/rcu_read_{lock, unlock} so it should not be required.

hmm... not sure what nested or not has to do here. It is likely we are talking different things.

Yeah, we were looking at different things.

e.g. bpf_selem_unlink does not need to be changed as it is in a rcu_read_lock.

Quoted 7 lines
Quoted 3 lines

No. It is not always under rcu_read_lock(). From the patch 2 test, it should have a splat either from bpf_inode_storage_delete() or bpf_sk_storage_delete(), depending on which one runs first.

I missed this one, but I wonder why it did not trigger a warning. The test does exercise the delete and rcu_dereference should have warned me that I am not holding an rcu_read_lock();

hmm... not sure either. may be some kconfigs that disabled rcu_read_lock_held()? I would also take a look at RCU_LOCKDEP_WARN().

I just quickly tried the patches to check:

[  143.376587] =============================
[  143.377068] WARNING: suspicious RCU usage
[  143.377541] 5.14.0-rc5-01271-g68e5bda2b18e #4966 Tainted: G           O
[  143.378378] -----------------------------
[  143.378857] kernel/bpf/bpf_local_storage.c:114 suspicious rcu_dereference_check() usage!
[  143.379914]
[  143.379914] other info that might help us debug this:
[  143.379914]
[  143.380838]
[  143.380838] rcu_scheduler_active = 2, debug_locks = 1
[  143.381602] 4 locks held by mv/1781:
[  143.382025]  #0: ffff888121e7c438 (sb_writers#6){.+.+}-{0:0}, at: do_renameat2+0x2f5/0xa80
[  143.383009]  #1: ffff88812ce68760 (&type->i_mutex_dir_key#5/1){+.+.}-{3:3}, at: lock_rename+0x1f4/0x250
[  143.384144]  #2: ffffffff843fbc60 (rcu_read_lock_trace){....}-{0:0}, at: __bpf_prog_enter_sleepable+0x45/0x160
[  143.385326]  #3: ffff88811d8348b8 (&storage->lock){..-.}-{2:2}, at: __bpf_selem_unlink_storage+0x7d/0x170
[  143.386459]
[  143.386459] stack backtrace:
[  143.386983] CPU: 2 PID: 1781 Comm: mv Tainted: G           O      5.14.0-rc5-01271-g68e5bda2b18e #4966
[  143.388071] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.9.3-1.el7.centos 04/01/2014
[  143.389146] Call Trace:
[  143.389446]  dump_stack_lvl+0x5b/0x82
[  143.389901]  dump_stack+0x10/0x12
Quoted 8 lines
[  143.390302]  lockdep_rcu_suspicious+0x15c/0x167
[  143.390854]  bpf_selem_unlink_storage_nolock+0x2e1/0x6d0
[  143.391501]  __bpf_selem_unlink_storage+0xb7/0x170
[  143.392085]  bpf_selem_unlink+0x1b/0x30
[  143.392554]  bpf_inode_storage_delete+0x57/0xa0
[  143.393112]  bpf_prog_31e277fe2c132665_inode_rename+0x9c/0x268
[  143.393814]  bpf_trampoline_6442476301_0+0x4e/0x1000
[  143.394413]  bpf_lsm_inode_rename+0x5/0x10

I am not sure what line 114 is (it is a blank line in bpf-next), but you might be missing a rcu_read_lock_trace_held() in the second argument of rcu_dereference_check().

Thanx, Paul

Quoted 75 lines
Quoted 49 lines
Quoted 49 lines
Quoted 36 lines
Quoted 36 lines
Quoted 24 lines
Quoted 24 lines
Quoted 24 lines
net/core/bpf_sk_storage.c +3 -1
@@ -13,6 +13,7 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
 
 DEFINE_BPF_STORAGE_CACHE(sk_cache);
 
@@ -22,7 +23,8 @@ bpf_sk_storage_lookup(struct sock *sk, struct bpf_map *map, bool cacheit_lockit)
      struct bpf_local_storage *sk_storage;
      struct bpf_local_storage_map *smap;
 
-     sk_storage = rcu_dereference(sk->sk_bpf_storage);
+     sk_storage = rcu_dereference_protected(sk->sk_bpf_storage,
+                                            bpf_local_storage_rcu_lock_held());
      if (!sk_storage)
              return NULL;
 
@@ -258,6 +260,7 @@ BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk,
 {
      struct bpf_local_storage_data *sdata;
 
Quoted 8 lines
Quoted 4 lines

net/core/bpf_sk_storage.c BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk, · line 264

Quoted 2 lines
net/core/bpf_sk_storage.c +1 -0
+     WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
      if (!sk || !sk_fullsock(sk) || flags > BPF_SK_STORAGE_GET_F_CREATE)

sk is protected by rcu_read_lock here.
Is it always safe to access it with the rcu_read_lock_trace alone ?

We don't dereference sk with an rcu_dereference though, is it still the case for tracing and LSM programs? Or is it somehow implicity protected even though we don't use rcu_dereference since that's just a READ_ONCE + some checks?

e.g. the bpf_prog (currently run under rcu_read_lock()) may read the sk from req_sk->sk which I don't think the verifier will optimize it out, so as good as READ_ONCE(), iiuc.

Quoted 8 lines
Quoted 2 lines

The sk here is obtained from the bpf_lsm_socket_* hooks? Those sk should have a refcnt, right? If that is the case, it should be good enough for now.

The one passed in the arguments yes, but if you notice the discussion in

https://lore.kernel.org/bpf/[email protected]/T/#me254212a125516a6c5d2fbf349b97c199e66dce0

one may also get an sk in LSM and tracing progs by pointer walking.

Right. There is pointer walking case.
e.g. "struct request_sock __rcu *fastopen_rsk" in tcp_sock. I don't think it is possible for lsm to get a hold on tcp_sock but agree that other similar cases could happen.

Quoted 7 lines
Quoted 5 lines

May be for now, in sleepable program, only allow safe sk ptr
to be used in helpers that take sk PTR_TO_BTF_ID argument.
e.g. sock->sk is safe in the test in patch 2. The same should go for other storages like inode. This needs verifier change.

Sorry, I may be missing some context. Do you mean wait for Yonghong's work?

I don't think we have to wait. Just saying Yonghong's work could fit well in this use case in the future.

Quoted 2 lines

Or is there another way to update the verifier to recognize safe sk and inode pointers?

I was thinking specifically for this pointer walking case. Take a look at btf_struct_access(). It walks the struct
in the verifier and figures out reading sock->sk will get
a "struct sock *". It marks the reg to PTR_TO_BTF_ID.
This will allow the bpf prog to directly read from sk (e.g. sk->sk_num) or pass the sk to helper that takes a "struct sock *" pointer. Reading from any sk pointer is fine since it is protected by BPF_PROBE_MEM read. However, we only allow the sk from sock->sk to be passed to the helper here because we only know this one is refcnt-ed.

Take a look at check_ptr_to_btf_access(). An individual verifier_ops can also have its own btf_struct_access. One possibility is to introduce a (new) PTR_TO_RDONLY_BTF_ID to mean it can only do BPR_PROBE_MEM read but cannot be used in helper.

#10 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 85 lines · Paul E. McKenney
Quoted 61 lines · Martin KaFai Lau

On Tue, Aug 31, 2021 at 09:38:01PM +0200, KP Singh wrote:
[ ... ]

Quoted 49 lines
Quoted 34 lines
Quoted 33 lines
Quoted 25 lines
Quoted 17 lines
Quoted 9 lines

Review bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage, · line 152

Quoted 6 lines
(quoted diff) +1 -1
@@ -131,7 +149,7 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
          SDATA(selem))
              RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);
 
-     kfree_rcu(selem, rcu);
+     call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);

Although the common use case is usually storage_get() much more often than storage_delete(), do you aware any performance impact for the bpf prog that does a lot of storage_delete()?

I have not really measured the impact on deletes, My understanding is that it should
not impact the BPF program, but yes, if there are some critical sections that are prolonged
due to a sleepable program "sleeping" too long, then it would pile up the callbacks.

Quoted 4 lines

But this is not something new, as we have a similar thing in BPF trampolines. If this really
becomes an issue, we could add a flag BPF_F_SLEEPABLE_STORAGE and only maps with this flag would be allowed in sleepable progs.

Agree that is similar to trampoline updates but not sure it is comparable in terms of the frequency of elems being deleted here. e.g. many short lived tcp connections created by external traffic.

Quoted 6 lines

Adding a BPF_F_SLEEPABLE_STORAGE later won't work. It will break existing sleepable bpf prog.

I don't know enough on call_rcu_tasks_trace() here, so the earlier question on perf/callback-pile-up implications in order to decide if extra logic or knob is needed here or not.

I will defer to the others, maybe Alexei and Paul,

Quoted 8 lines
Quoted 2 lines

we could also just
add the flag to not affect existing performance characteristics?

I would see if it is really necessary first. Other sleepable supported maps do not need a flag. Adding one here for local storage will be confusing especially if it turns out to be unnecessary.

Could you run some tests first which can guide the decision?

I think the performance impact would happen only in the worst case which needs some work to simulate. What do you think about:

A bprm_committed_creds program that processes a large argv and also gets a storage on the inode.

Quoted 8 lines

A file_open program that tries to delete the local storage on the inode.

Trigger this code in parallel. i.e. lots of programs that execute with a very large argv and then in parallel the executable being opened to trigger the delete.

Do you have any other ideas? Is there something we could re-use from the selftests?

Quoted 7 lines

There is a bench framework in tools/testing/selftests/bpf/benchs/ that has a parallel thread setup which could be useful.

Don't know how to simulate the "sleeping" too long which then pile-up callbacks. This is not bpf specific. Paul, I wonder if you have similar test to trigger this to compare between call_rcu_tasks_trace() and call_rcu()?

It is definitely the case that call_rcu() is way more scalable than is call_rcu_tasks_trace(). Something about call_rcu_tasks_trace() acquiring a global lock. ;-)

So actually testing it makes a lot of sense.

I do have an rcuscale module, but it is set up more for synchronous grace periods such as synchronize_rcu() and synchronize_rcu_tasks_trace(). It has the beginnings of support for call_rcu() and call_rcu_tasks_trace(), but I would not yet trust them.

But I also have a test for global locking:

$ tools/testing/selftests/rcutorture/bin/kvm.sh --torture refscale --allcpus --duration 5 --configs "NOPREEMPT" --kconfig "CONFIG_NR_CPUS=16" --bootargs "refscale.scale_type=lock refscale.loops=10000 refscale.holdoff=20 torture.disable_onoff_at_boot" --trust-make
Quoted 7 lines

This gives a median lock overhead of 960ns. Running a single CPU rather than 16 of them:

$ tools/testing/selftests/rcutorture/bin/kvm.sh --torture refscale --allcpus --duration 5 --configs "NOPREEMPT" --kconfig "CONFIG_NR_CPUS=16" --bootargs "refscale.scale_type=lock refscale.loops=10000 refscale.holdoff=20 torture.disable_onoff_at_boot" --trust-make

This gives a median lock overhead of 4.1ns, which is way faster. And the greater the number of CPUs, the greater the lock overhead.

Thanks for the explanation and numbers!

I think the global lock will be an issue for the current non-sleepable netdev bpf-prog which could be triggered by external traffic, so a flag is needed here to provide a fast path. I suspect other non-prealloc map may need it in the future, so probably s/BPF_F_SLEEPABLE_STORAGE/BPF_F_SLEEPABLE/ instead.

[ ... ]

Quoted 31 lines
Quoted 22 lines
[  143.376587] =============================
[  143.377068] WARNING: suspicious RCU usage
[  143.377541] 5.14.0-rc5-01271-g68e5bda2b18e #4966 Tainted: G           O
[  143.378378] -----------------------------
[  143.378857] kernel/bpf/bpf_local_storage.c:114 suspicious rcu_dereference_check() usage!
[  143.379914]
[  143.379914] other info that might help us debug this:
[  143.379914]
[  143.380838]
[  143.380838] rcu_scheduler_active = 2, debug_locks = 1
[  143.381602] 4 locks held by mv/1781:
[  143.382025]  #0: ffff888121e7c438 (sb_writers#6){.+.+}-{0:0}, at: do_renameat2+0x2f5/0xa80
[  143.383009]  #1: ffff88812ce68760 (&type->i_mutex_dir_key#5/1){+.+.}-{3:3}, at: lock_rename+0x1f4/0x250
[  143.384144]  #2: ffffffff843fbc60 (rcu_read_lock_trace){....}-{0:0}, at: __bpf_prog_enter_sleepable+0x45/0x160
[  143.385326]  #3: ffff88811d8348b8 (&storage->lock){..-.}-{2:2}, at: __bpf_selem_unlink_storage+0x7d/0x170
[  143.386459]
[  143.386459] stack backtrace:
[  143.386983] CPU: 2 PID: 1781 Comm: mv Tainted: G           O      5.14.0-rc5-01271-g68e5bda2b18e #4966
[  143.388071] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.9.3-1.el7.centos 04/01/2014
[  143.389146] Call Trace:
[  143.389446]  dump_stack_lvl+0x5b/0x82
[  143.389901]  dump_stack+0x10/0x12
Quoted 8 lines
[  143.390302]  lockdep_rcu_suspicious+0x15c/0x167
[  143.390854]  bpf_selem_unlink_storage_nolock+0x2e1/0x6d0
[  143.391501]  __bpf_selem_unlink_storage+0xb7/0x170
[  143.392085]  bpf_selem_unlink+0x1b/0x30
[  143.392554]  bpf_inode_storage_delete+0x57/0xa0
[  143.393112]  bpf_prog_31e277fe2c132665_inode_rename+0x9c/0x268
[  143.393814]  bpf_trampoline_6442476301_0+0x4e/0x1000
[  143.394413]  bpf_lsm_inode_rename+0x5/0x10
Quoted 3 lines

I am not sure what line 114 is (it is a blank line in bpf-next), but you might be missing a rcu_read_lock_trace_held() in the second argument of rcu_dereference_check().

Right, this path is only under rcu_read_lock_trace().

author
#11 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 94 lines · Martin KaFai Lau
Quoted 85 lines · Paul E. McKenney
Quoted 61 lines · Martin KaFai Lau

On Tue, Aug 31, 2021 at 09:38:01PM +0200, KP Singh wrote:
[ ... ]

Quoted 49 lines
Quoted 34 lines
Quoted 33 lines
Quoted 25 lines
Quoted 17 lines
Quoted 9 lines

Review bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage, · line 152

Quoted 6 lines
(quoted diff) +1 -1
@@ -131,7 +149,7 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
          SDATA(selem))
              RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);
 
-     kfree_rcu(selem, rcu);
+     call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);

Although the common use case is usually storage_get() much more often than storage_delete(), do you aware any performance impact for the bpf prog that does a lot of storage_delete()?

I have not really measured the impact on deletes, My understanding is that it should
not impact the BPF program, but yes, if there are some critical sections that are prolonged
due to a sleepable program "sleeping" too long, then it would pile up the callbacks.

Quoted 4 lines

But this is not something new, as we have a similar thing in BPF trampolines. If this really
becomes an issue, we could add a flag BPF_F_SLEEPABLE_STORAGE and only maps with this flag would be allowed in sleepable progs.

Agree that is similar to trampoline updates but not sure it is comparable in terms of the frequency of elems being deleted here. e.g. many short lived tcp connections created by external traffic.

Quoted 6 lines

Adding a BPF_F_SLEEPABLE_STORAGE later won't work. It will break existing sleepable bpf prog.

I don't know enough on call_rcu_tasks_trace() here, so the earlier question on perf/callback-pile-up implications in order to decide if extra logic or knob is needed here or not.

I will defer to the others, maybe Alexei and Paul,

Quoted 8 lines
Quoted 2 lines

we could also just
add the flag to not affect existing performance characteristics?

I would see if it is really necessary first. Other sleepable supported maps do not need a flag. Adding one here for local storage will be confusing especially if it turns out to be unnecessary.

Could you run some tests first which can guide the decision?

I think the performance impact would happen only in the worst case which needs some work to simulate. What do you think about:

A bprm_committed_creds program that processes a large argv and also gets a storage on the inode.

Quoted 8 lines

A file_open program that tries to delete the local storage on the inode.

Trigger this code in parallel. i.e. lots of programs that execute with a very large argv and then in parallel the executable being opened to trigger the delete.

Do you have any other ideas? Is there something we could re-use from the selftests?

Quoted 7 lines

There is a bench framework in tools/testing/selftests/bpf/benchs/ that has a parallel thread setup which could be useful.

Don't know how to simulate the "sleeping" too long which then pile-up callbacks. This is not bpf specific. Paul, I wonder if you have similar test to trigger this to compare between call_rcu_tasks_trace() and call_rcu()?

It is definitely the case that call_rcu() is way more scalable than is call_rcu_tasks_trace(). Something about call_rcu_tasks_trace() acquiring a global lock. ;-)

So actually testing it makes a lot of sense.

I do have an rcuscale module, but it is set up more for synchronous grace periods such as synchronize_rcu() and synchronize_rcu_tasks_trace(). It has the beginnings of support for call_rcu() and call_rcu_tasks_trace(), but I would not yet trust them.

But I also have a test for global locking:

$ tools/testing/selftests/rcutorture/bin/kvm.sh --torture refscale --allcpus --duration 5 --configs "NOPREEMPT" --kconfig "CONFIG_NR_CPUS=16" --bootargs "refscale.scale_type=lock refscale.loops=10000 refscale.holdoff=20 torture.disable_onoff_at_boot" --trust-make
Quoted 7 lines

This gives a median lock overhead of 960ns. Running a single CPU rather than 16 of them:

$ tools/testing/selftests/rcutorture/bin/kvm.sh --torture refscale --allcpus --duration 5 --configs "NOPREEMPT" --kconfig "CONFIG_NR_CPUS=16" --bootargs "refscale.scale_type=lock refscale.loops=10000 refscale.holdoff=20 torture.disable_onoff_at_boot" --trust-make

This gives a median lock overhead of 4.1ns, which is way faster. And the greater the number of CPUs, the greater the lock overhead.

Quoted 7 lines

Thanks for the explanation and numbers!

I think the global lock will be an issue for the current non-sleepable netdev bpf-prog which could be triggered by external traffic, so a flag is needed here to provide a fast path. I suspect other non-prealloc map may need it in the future, so probably s/BPF_F_SLEEPABLE_STORAGE/BPF_F_SLEEPABLE/ instead.

I was re-working the patches and had a couple of questions.

There are two data structures that get freed under RCU here:

struct bpf_local_storage
struct bpf_local_storage_selem

We can choose to free the bpf_local_storage_selem under call_rcu_tasks_trace based on
whether the map it belongs to is sleepable with something like:

if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)

    call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
else
    kfree_rcu(selem, rcu);

Questions:

* Can we free bpf_local_storage under kfree_rcu by ensuring it's always accessed in a
classical RCU critical section? Or maybe I am missing something and
this also needs to be freed
under trace RCU if any of the selems are from a sleepable map.

* There is an issue with nested raw spinlocks, e.g. in bpf_inode_storage.c:bpf_inode_storage_free

  hlist_for_each_entry_safe(selem, n, &local_storage->list, snode) {
  /* Always unlink from map before unlinking from
  * local_storage.
  */
  bpf_selem_unlink_map(selem);
  free_inode_storage = bpf_selem_unlink_storage_nolock(
                 local_storage, selem, false);
  }
  raw_spin_unlock_bh(&local_storage->lock);

in bpf_selem_unlink_storage_nolock (if we add the above logic with the flag in place of kfree_rcu)
call_rcu_tasks_trace grabs a spinlock and these cannot be nested in a raw spin lock.

I am moving the freeing code out of the spinlock, saving the selems on a local list and then
doing the free RCU (trace or normal) callbacks at the end. WDYT?

- KP

Quoted 38 lines

[ ... ]

Quoted 31 lines
Quoted 22 lines
[  143.376587] =============================
[  143.377068] WARNING: suspicious RCU usage
[  143.377541] 5.14.0-rc5-01271-g68e5bda2b18e #4966 Tainted: G           O
[  143.378378] -----------------------------
[  143.378857] kernel/bpf/bpf_local_storage.c:114 suspicious rcu_dereference_check() usage!
[  143.379914]
[  143.379914] other info that might help us debug this:
[  143.379914]
[  143.380838]
[  143.380838] rcu_scheduler_active = 2, debug_locks = 1
[  143.381602] 4 locks held by mv/1781:
[  143.382025]  #0: ffff888121e7c438 (sb_writers#6){.+.+}-{0:0}, at: do_renameat2+0x2f5/0xa80
[  143.383009]  #1: ffff88812ce68760 (&type->i_mutex_dir_key#5/1){+.+.}-{3:3}, at: lock_rename+0x1f4/0x250
[  143.384144]  #2: ffffffff843fbc60 (rcu_read_lock_trace){....}-{0:0}, at: __bpf_prog_enter_sleepable+0x45/0x160
[  143.385326]  #3: ffff88811d8348b8 (&storage->lock){..-.}-{2:2}, at: __bpf_selem_unlink_storage+0x7d/0x170
[  143.386459]
[  143.386459] stack backtrace:
[  143.386983] CPU: 2 PID: 1781 Comm: mv Tainted: G           O      5.14.0-rc5-01271-g68e5bda2b18e #4966
[  143.388071] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.9.3-1.el7.centos 04/01/2014
[  143.389146] Call Trace:
[  143.389446]  dump_stack_lvl+0x5b/0x82
[  143.389901]  dump_stack+0x10/0x12
Quoted 8 lines
[  143.390302]  lockdep_rcu_suspicious+0x15c/0x167
[  143.390854]  bpf_selem_unlink_storage_nolock+0x2e1/0x6d0
[  143.391501]  __bpf_selem_unlink_storage+0xb7/0x170
[  143.392085]  bpf_selem_unlink+0x1b/0x30
[  143.392554]  bpf_inode_storage_delete+0x57/0xa0
[  143.393112]  bpf_prog_31e277fe2c132665_inode_rename+0x9c/0x268
[  143.393814]  bpf_trampoline_6442476301_0+0x4e/0x1000
[  143.394413]  bpf_lsm_inode_rename+0x5/0x10
Quoted 3 lines

I am not sure what line 114 is (it is a blank line in bpf-next), but you might be missing a rcu_read_lock_trace_held() in the second argument of rcu_dereference_check().

Right, this path is only under rcu_read_lock_trace().

#12 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 140 lines · KP Singh
Quoted 94 lines · Martin KaFai Lau
Quoted 85 lines · Paul E. McKenney
Quoted 61 lines · Martin KaFai Lau

On Tue, Aug 31, 2021 at 09:38:01PM +0200, KP Singh wrote:
[ ... ]

Quoted 49 lines
Quoted 34 lines
Quoted 33 lines
Quoted 25 lines
Quoted 17 lines
Quoted 9 lines

Review bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage, · line 152

Quoted 6 lines
(quoted diff) +1 -1
@@ -131,7 +149,7 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
          SDATA(selem))
              RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);
 
-     kfree_rcu(selem, rcu);
+     call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);

Although the common use case is usually storage_get() much more often than storage_delete(), do you aware any performance impact for the bpf prog that does a lot of storage_delete()?

I have not really measured the impact on deletes, My understanding is that it should
not impact the BPF program, but yes, if there are some critical sections that are prolonged
due to a sleepable program "sleeping" too long, then it would pile up the callbacks.

Quoted 4 lines

But this is not something new, as we have a similar thing in BPF trampolines. If this really
becomes an issue, we could add a flag BPF_F_SLEEPABLE_STORAGE and only maps with this flag would be allowed in sleepable progs.

Agree that is similar to trampoline updates but not sure it is comparable in terms of the frequency of elems being deleted here. e.g. many short lived tcp connections created by external traffic.

Quoted 6 lines

Adding a BPF_F_SLEEPABLE_STORAGE later won't work. It will break existing sleepable bpf prog.

I don't know enough on call_rcu_tasks_trace() here, so the earlier question on perf/callback-pile-up implications in order to decide if extra logic or knob is needed here or not.

I will defer to the others, maybe Alexei and Paul,

Quoted 8 lines
Quoted 2 lines

we could also just
add the flag to not affect existing performance characteristics?

I would see if it is really necessary first. Other sleepable supported maps do not need a flag. Adding one here for local storage will be confusing especially if it turns out to be unnecessary.

Could you run some tests first which can guide the decision?

I think the performance impact would happen only in the worst case which needs some work to simulate. What do you think about:

A bprm_committed_creds program that processes a large argv and also gets a storage on the inode.

Quoted 8 lines

A file_open program that tries to delete the local storage on the inode.

Trigger this code in parallel. i.e. lots of programs that execute with a very large argv and then in parallel the executable being opened to trigger the delete.

Do you have any other ideas? Is there something we could re-use from the selftests?

Quoted 7 lines

There is a bench framework in tools/testing/selftests/bpf/benchs/ that has a parallel thread setup which could be useful.

Don't know how to simulate the "sleeping" too long which then pile-up callbacks. This is not bpf specific. Paul, I wonder if you have similar test to trigger this to compare between call_rcu_tasks_trace() and call_rcu()?

It is definitely the case that call_rcu() is way more scalable than is call_rcu_tasks_trace(). Something about call_rcu_tasks_trace() acquiring a global lock. ;-)

So actually testing it makes a lot of sense.

I do have an rcuscale module, but it is set up more for synchronous grace periods such as synchronize_rcu() and synchronize_rcu_tasks_trace(). It has the beginnings of support for call_rcu() and call_rcu_tasks_trace(), but I would not yet trust them.

But I also have a test for global locking:

$ tools/testing/selftests/rcutorture/bin/kvm.sh --torture refscale --allcpus --duration 5 --configs "NOPREEMPT" --kconfig "CONFIG_NR_CPUS=16" --bootargs "refscale.scale_type=lock refscale.loops=10000 refscale.holdoff=20 torture.disable_onoff_at_boot" --trust-make
Quoted 7 lines

This gives a median lock overhead of 960ns. Running a single CPU rather than 16 of them:

$ tools/testing/selftests/rcutorture/bin/kvm.sh --torture refscale --allcpus --duration 5 --configs "NOPREEMPT" --kconfig "CONFIG_NR_CPUS=16" --bootargs "refscale.scale_type=lock refscale.loops=10000 refscale.holdoff=20 torture.disable_onoff_at_boot" --trust-make

This gives a median lock overhead of 4.1ns, which is way faster. And the greater the number of CPUs, the greater the lock overhead.

Quoted 7 lines

Thanks for the explanation and numbers!

I think the global lock will be an issue for the current non-sleepable netdev bpf-prog which could be triggered by external traffic, so a flag is needed here to provide a fast path. I suspect other non-prealloc map may need it in the future, so probably s/BPF_F_SLEEPABLE_STORAGE/BPF_F_SLEEPABLE/ instead.

I was re-working the patches and had a couple of questions.

There are two data structures that get freed under RCU here:

struct bpf_local_storage
struct bpf_local_storage_selem

We can choose to free the bpf_local_storage_selem under call_rcu_tasks_trace based on
whether the map it belongs to is sleepable with something like:

if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)

    call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
else
    kfree_rcu(selem, rcu);

Questions:

* Can we free bpf_local_storage under kfree_rcu by ensuring it's always accessed in a
classical RCU critical section? Or maybe I am missing something and
this also needs to be freed
under trace RCU if any of the selems are from a sleepable map.

* There is an issue with nested raw spinlocks, e.g. in bpf_inode_storage.c:bpf_inode_storage_free

  hlist_for_each_entry_safe(selem, n, &local_storage->list, snode) {
  /* Always unlink from map before unlinking from
  * local_storage.
  */
  bpf_selem_unlink_map(selem);
  free_inode_storage = bpf_selem_unlink_storage_nolock(
                 local_storage, selem, false);
  }
  raw_spin_unlock_bh(&local_storage->lock);
Quoted 8 lines

in bpf_selem_unlink_storage_nolock (if we add the above logic with the flag in place of kfree_rcu)
call_rcu_tasks_trace grabs a spinlock and these cannot be nested in a raw spin lock.

I am moving the freeing code out of the spinlock, saving the selems on a local list and then
doing the free RCU (trace or normal) callbacks at the end. WDYT?

Depending on the urgency, another approach is to rely on my ongoing work removing the call_rcu_tasks_trace() bottleneck. This commit on branch "dev" in the -rcu tree allows boot-time setting of per-CPU callback queues for call_rcu_tasks_trace(), along with the other RCU-tasks flavors:

0b886cc4b10f ("rcu-tasks: Add rcupdate.rcu_task_enqueue_lim to set initial queueing")

Preceding commits actually set up the queues. With these commits, you could boot with rcupdate.rcu_task_enqueue_lim=N, where N greater than or equal to the number of CPUs on your system, to get per-CPU queuing. These commits probably still have a bug or three, but on the other hand, they have survived a couple of weeks worth of rcutorture runs.

This week's work will allow automatic transition between single-queue and per-CPU-queue operation based on lock contention and the number of callbacks queued.

My current plan is to get this into the next merge window (v5.17).

Thoughts?

Thanx, Paul

Quoted 40 lines

- KP

Quoted 38 lines

[ ... ]

Quoted 31 lines
Quoted 22 lines
[  143.376587] =============================
[  143.377068] WARNING: suspicious RCU usage
[  143.377541] 5.14.0-rc5-01271-g68e5bda2b18e #4966 Tainted: G           O
[  143.378378] -----------------------------
[  143.378857] kernel/bpf/bpf_local_storage.c:114 suspicious rcu_dereference_check() usage!
[  143.379914]
[  143.379914] other info that might help us debug this:
[  143.379914]
[  143.380838]
[  143.380838] rcu_scheduler_active = 2, debug_locks = 1
[  143.381602] 4 locks held by mv/1781:
[  143.382025]  #0: ffff888121e7c438 (sb_writers#6){.+.+}-{0:0}, at: do_renameat2+0x2f5/0xa80
[  143.383009]  #1: ffff88812ce68760 (&type->i_mutex_dir_key#5/1){+.+.}-{3:3}, at: lock_rename+0x1f4/0x250
[  143.384144]  #2: ffffffff843fbc60 (rcu_read_lock_trace){....}-{0:0}, at: __bpf_prog_enter_sleepable+0x45/0x160
[  143.385326]  #3: ffff88811d8348b8 (&storage->lock){..-.}-{2:2}, at: __bpf_selem_unlink_storage+0x7d/0x170
[  143.386459]
[  143.386459] stack backtrace:
[  143.386983] CPU: 2 PID: 1781 Comm: mv Tainted: G           O      5.14.0-rc5-01271-g68e5bda2b18e #4966
[  143.388071] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.9.3-1.el7.centos 04/01/2014
[  143.389146] Call Trace:
[  143.389446]  dump_stack_lvl+0x5b/0x82
[  143.389901]  dump_stack+0x10/0x12
Quoted 8 lines
[  143.390302]  lockdep_rcu_suspicious+0x15c/0x167
[  143.390854]  bpf_selem_unlink_storage_nolock+0x2e1/0x6d0
[  143.391501]  __bpf_selem_unlink_storage+0xb7/0x170
[  143.392085]  bpf_selem_unlink+0x1b/0x30
[  143.392554]  bpf_inode_storage_delete+0x57/0xa0
[  143.393112]  bpf_prog_31e277fe2c132665_inode_rename+0x9c/0x268
[  143.393814]  bpf_trampoline_6442476301_0+0x4e/0x1000
[  143.394413]  bpf_lsm_inode_rename+0x5/0x10
Quoted 3 lines

I am not sure what line 114 is (it is a blank line in bpf-next), but you might be missing a rcu_read_lock_trace_held() in the second argument of rcu_dereference_check().

Right, this path is only under rcu_read_lock_trace().

#13 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 12 lines · Paul E. McKenney
Quoted 11 lines · KP Singh
Quoted 5 lines · Martin KaFai Lau

I think the global lock will be an issue for the current non-sleepable netdev bpf-prog which could be triggered by external traffic, so a flag is needed here to provide a fast path. I suspect other non-prealloc map may need it in the future, so probably s/BPF_F_SLEEPABLE_STORAGE/BPF_F_SLEEPABLE/ instead.

I was re-working the patches and had a couple of questions.

There are two data structures that get freed under RCU here:

Quoted 8 lines
Quoted 8 lines

struct bpf_local_storage
struct bpf_local_storage_selem

We can choose to free the bpf_local_storage_selem under call_rcu_tasks_trace based on
whether the map it belongs to is sleepable with something like:

if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)

Paul's current work (mentioned by his previous email) will improve the performance of call_rcu_tasks_trace, so it probably can avoid the new BPF_F_SLEEPABLE flag and make it easier to use.

Quoted 10 lines
Quoted 10 lines
    call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
else
    kfree_rcu(selem, rcu);

Questions:

* Can we free bpf_local_storage under kfree_rcu by ensuring it's always accessed in a classical RCU critical section? Or maybe I am missing something and this also needs to be freed under trace RCU if any of the selems are from a sleepable map.

In the inode_storage_lookup() of this patch:

+#define bpf_local_storage_rcu_lock_held() \
+ (rcu_read_lock_held() || rcu_read_lock_trace_held() || \
+ rcu_read_lock_bh_held())

@@ -44,7 +45,8 @@ static struct bpf_local_storage_data *inode_storage_lookup(struct inode *inode,

	if (!bsb)
		return NULL;

- inode_storage = rcu_dereference(bsb->storage);
+ inode_storage = rcu_dereference_protected(bsb->storage,
+ bpf_local_storage_rcu_lock_held());

Thus, it is not always in classical RCU critical.

Quoted 14 lines
Quoted 14 lines

* There is an issue with nested raw spinlocks, e.g. in bpf_inode_storage.c:bpf_inode_storage_free

  hlist_for_each_entry_safe(selem, n, &local_storage->list, snode) {
  /* Always unlink from map before unlinking from
  * local_storage.
  */
  bpf_selem_unlink_map(selem);
  free_inode_storage = bpf_selem_unlink_storage_nolock(
                 local_storage, selem, false);
  }
  raw_spin_unlock_bh(&local_storage->lock);
Quoted 8 lines
Quoted 8 lines

in bpf_selem_unlink_storage_nolock (if we add the above logic with the flag in place of kfree_rcu)
call_rcu_tasks_trace grabs a spinlock and these cannot be nested in a raw spin lock.

I am moving the freeing code out of the spinlock, saving the selems on a local list and then doing the free RCU (trace or normal) callbacks at the end. WDYT?

There could be more than one selem to save.

I think the splat is from CONFIG_PROVE_RAW_LOCK_NESTING=y.

Just happened to bump into Paul briefly offline, his work probably can also avoid the spin_lock in call_rcu_tasks_trace().

I would ignore this splat for now which should go away when it is merged with Paul's work in the 5.17 merge cycle.

Quoted 13 lines

Depending on the urgency, another approach is to rely on my ongoing work removing the call_rcu_tasks_trace() bottleneck. This commit on branch "dev" in the -rcu tree allows boot-time setting of per-CPU callback queues for call_rcu_tasks_trace(), along with the other RCU-tasks flavors:

0b886cc4b10f ("rcu-tasks: Add rcupdate.rcu_task_enqueue_lim to set initial queueing")

Preceding commits actually set up the queues. With these commits, you could boot with rcupdate.rcu_task_enqueue_lim=N, where N greater than or equal to the number of CPUs on your system, to get per-CPU queuing. These commits probably still have a bug or three, but on the other hand, they have survived a couple of weeks worth of rcutorture runs.

Quoted 5 lines

This week's work will allow automatic transition between single-queue and per-CPU-queue operation based on lock contention and the number of callbacks queued.

My current plan is to get this into the next merge window (v5.17).

That would be great.

author
#14 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 50 lines · Martin KaFai Lau
Quoted 12 lines · Paul E. McKenney
Quoted 11 lines · KP Singh
Quoted 5 lines · Martin KaFai Lau

I think the global lock will be an issue for the current non-sleepable netdev bpf-prog which could be triggered by external traffic, so a flag is needed here to provide a fast path. I suspect other non-prealloc map may need it in the future, so probably s/BPF_F_SLEEPABLE_STORAGE/BPF_F_SLEEPABLE/ instead.

I was re-working the patches and had a couple of questions.

There are two data structures that get freed under RCU here:

Quoted 8 lines
Quoted 8 lines

struct bpf_local_storage
struct bpf_local_storage_selem

We can choose to free the bpf_local_storage_selem under call_rcu_tasks_trace based on
whether the map it belongs to is sleepable with something like:

if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)

Paul's current work (mentioned by his previous email) will improve the performance of call_rcu_tasks_trace, so it probably can avoid the new BPF_F_SLEEPABLE flag and make it easier to use.

Quoted 10 lines
Quoted 10 lines
    call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
else
    kfree_rcu(selem, rcu);

Questions:

* Can we free bpf_local_storage under kfree_rcu by ensuring it's always accessed in a classical RCU critical section? Or maybe I am missing something and this also needs to be freed under trace RCU if any of the selems are from a sleepable map.

In the inode_storage_lookup() of this patch:

(quoted diff) +5 -1
+#define bpf_local_storage_rcu_lock_held()                      \
+       (rcu_read_lock_held() || rcu_read_lock_trace_held() ||  \
+        rcu_read_lock_bh_held())
@@ -44,7 +45,8 @@ static struct bpf_local_storage_data *inode_storage_lookup(struct inode *inode,
        if (!bsb)
                return NULL;
 
-       inode_storage = rcu_dereference(bsb->storage);
+       inode_storage = rcu_dereference_protected(bsb->storage,
+                                                 bpf_local_storage_rcu_lock_held());
 
Quoted 1 line

Thus, it is not always in classical RCU critical.

I was planning on adding a classical RCU read side critical section whenever we called the lookup functions.

Would that have worked? (for the sake of learning).

Quoted 25 lines
Quoted 15 lines
Quoted 15 lines

* There is an issue with nested raw spinlocks, e.g. in bpf_inode_storage.c:bpf_inode_storage_free

  hlist_for_each_entry_safe(selem, n, &local_storage->list, snode) {
  /* Always unlink from map before unlinking from
  * local_storage.
  */
  bpf_selem_unlink_map(selem);
  free_inode_storage = bpf_selem_unlink_storage_nolock(
                 local_storage, selem, false);
  }
  raw_spin_unlock_bh(&local_storage->lock);
Quoted 8 lines
Quoted 8 lines

in bpf_selem_unlink_storage_nolock (if we add the above logic with the flag in place of kfree_rcu)
call_rcu_tasks_trace grabs a spinlock and these cannot be nested in a raw spin lock.

I am moving the freeing code out of the spinlock, saving the selems on a local list and then doing the free RCU (trace or normal) callbacks at the end. WDYT?

There could be more than one selem to save.

Quoted 7 lines

I think the splat is from CONFIG_PROVE_RAW_LOCK_NESTING=y.

Just happened to bump into Paul briefly offline, his work probably can also avoid the spin_lock in call_rcu_tasks_trace().

I would ignore this splat for now which should go away when it is merged with Paul's work in the 5.17 merge cycle.

Agreed.

Quoted 14 lines
Quoted 14 lines

Depending on the urgency, another approach is to rely on my ongoing work removing the call_rcu_tasks_trace() bottleneck. This commit on branch "dev" in the -rcu tree allows boot-time setting of per-CPU callback queues for call_rcu_tasks_trace(), along with the other RCU-tasks flavors:

0b886cc4b10f ("rcu-tasks: Add rcupdate.rcu_task_enqueue_lim to set initial queueing")

Preceding commits actually set up the queues. With these commits, you could boot with rcupdate.rcu_task_enqueue_lim=N, where N greater than or equal to the number of CPUs on your system, to get per-CPU queuing. These commits probably still have a bug or three, but on the other hand, they have survived a couple of weeks worth of rcutorture runs.

Quoted 6 lines
Quoted 5 lines

This week's work will allow automatic transition between single-queue and per-CPU-queue operation based on lock contention and the number of callbacks queued.

My current plan is to get this into the next merge window (v5.17).

That would be great.

+1 :)

#15 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 51 lines · KP Singh
Quoted 50 lines · Martin KaFai Lau
Quoted 12 lines · Paul E. McKenney
Quoted 11 lines · KP Singh
Quoted 5 lines · Martin KaFai Lau

I think the global lock will be an issue for the current non-sleepable netdev bpf-prog which could be triggered by external traffic, so a flag is needed here to provide a fast path. I suspect other non-prealloc map may need it in the future, so probably s/BPF_F_SLEEPABLE_STORAGE/BPF_F_SLEEPABLE/ instead.

I was re-working the patches and had a couple of questions.

There are two data structures that get freed under RCU here:

Quoted 8 lines
Quoted 8 lines

struct bpf_local_storage
struct bpf_local_storage_selem

We can choose to free the bpf_local_storage_selem under call_rcu_tasks_trace based on
whether the map it belongs to is sleepable with something like:

if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)

Paul's current work (mentioned by his previous email) will improve the performance of call_rcu_tasks_trace, so it probably can avoid the new BPF_F_SLEEPABLE flag and make it easier to use.

Quoted 10 lines
Quoted 10 lines
    call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
else
    kfree_rcu(selem, rcu);

Questions:

* Can we free bpf_local_storage under kfree_rcu by ensuring it's always accessed in a classical RCU critical section? Or maybe I am missing something and this also needs to be freed under trace RCU if any of the selems are from a sleepable map.

In the inode_storage_lookup() of this patch:

(quoted diff) +5 -1
+#define bpf_local_storage_rcu_lock_held()                      \
+       (rcu_read_lock_held() || rcu_read_lock_trace_held() ||  \
+        rcu_read_lock_bh_held())
@@ -44,7 +45,8 @@ static struct bpf_local_storage_data *inode_storage_lookup(struct inode *inode,
        if (!bsb)
                return NULL;
 
-       inode_storage = rcu_dereference(bsb->storage);
+       inode_storage = rcu_dereference_protected(bsb->storage,
+                                                 bpf_local_storage_rcu_lock_held());
 
Quoted 6 lines
Quoted 1 line

Thus, it is not always in classical RCU critical.

I was planning on adding a classical RCU read side critical section whenever we called the lookup functions.

Would that have worked? (for the sake of learning).

ah. ic. You meant local_storage could be under rcu_read_lock() if we wanted to since it is not exposed to the sleepable bpf_prog which is under rcu_read_lock_trace()?

It should work after a quick thought but then we
need to figure out the needed places to add
an extra rcu_read_lock(). What is the
reason for doing this?

author
#16 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

In reply to Martin KaFai Lau
Quoted 71 lines · Martin KaFai Lau
Quoted 12 lines · Paul E. McKenney
Quoted 11 lines · KP Singh
Quoted 5 lines · Martin KaFai Lau

I think the global lock will be an issue for the current non-sleepable netdev bpf-prog which could be triggered by external traffic, so a flag is needed here to provide a fast path. I suspect other non-prealloc map may need it in the future, so probably s/BPF_F_SLEEPABLE_STORAGE/BPF_F_SLEEPABLE/ instead.

I was re-working the patches and had a couple of questions.

There are two data structures that get freed under RCU here:

Quoted 8 lines
Quoted 8 lines

struct bpf_local_storage
struct bpf_local_storage_selem

We can choose to free the bpf_local_storage_selem under call_rcu_tasks_trace based on
whether the map it belongs to is sleepable with something like:

if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)

Paul's current work (mentioned by his previous email) will improve the performance of call_rcu_tasks_trace, so it probably can avoid the new BPF_F_SLEEPABLE flag and make it easier to use.

Quoted 10 lines
Quoted 10 lines
    call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
else
    kfree_rcu(selem, rcu);

Questions:

* Can we free bpf_local_storage under kfree_rcu by ensuring it's always accessed in a classical RCU critical section? Or maybe I am missing something and this also needs to be freed under trace RCU if any of the selems are from a sleepable map.

In the inode_storage_lookup() of this patch:

(quoted diff) +5 -1
+#define bpf_local_storage_rcu_lock_held()                      \
+       (rcu_read_lock_held() || rcu_read_lock_trace_held() ||  \
+        rcu_read_lock_bh_held())
@@ -44,7 +45,8 @@ static struct bpf_local_storage_data *inode_storage_lookup(struct inode *inode,
        if (!bsb)
                return NULL;
 
-       inode_storage = rcu_dereference(bsb->storage);
+       inode_storage = rcu_dereference_protected(bsb->storage,
+                                                 bpf_local_storage_rcu_lock_held());
 

Thus, it is not always in classical RCU critical.

Quoted 19 lines
Quoted 19 lines

* There is an issue with nested raw spinlocks, e.g. in bpf_inode_storage.c:bpf_inode_storage_free

  hlist_for_each_entry_safe(selem, n, &local_storage->list, snode) {
  /* Always unlink from map before unlinking from
  * local_storage.
  */
  bpf_selem_unlink_map(selem);
  free_inode_storage = bpf_selem_unlink_storage_nolock(
                 local_storage, selem, false);
  }
  raw_spin_unlock_bh(&local_storage->lock);

in bpf_selem_unlink_storage_nolock (if we add the above logic with the flag in place of kfree_rcu)
call_rcu_tasks_trace grabs a spinlock and these cannot be nested in a raw spin lock.

Quoted 4 lines
Quoted 3 lines
Quoted 3 lines

I am moving the freeing code out of the spinlock, saving the selems on a local list and then doing the free RCU (trace or normal) callbacks at the end. WDYT?

There could be more than one selem to save.

Yes, that's why I was saving them on a local list and then calling kfree_rcu or call_rcu_tasks_trace after unlocking the raw_spin_lock

INIT_HLIST_HEAD(&free_list); 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_local_storage = bpf_selem_unlink_storage_nolock(
    local_storage, selem, false);
    hlist_add_head(&selem->snode, &free_list);
}

raw_spin_unlock_irqrestore(&local_storage->lock, flags);

/* The element needs to be freed outside the raw spinlock because spin
* locks cannot nest inside a raw spin locks and call_rcu_tasks_trace
* grabs a spinklock when the RCU code calls into the scheduler. *
* free_local_storage should always be true as long as
* local_storage->list was non-empty.
*/

hlist_for_each_entry_safe(selem, n, &free_list, snode) {
    if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)
        call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
    else
        kfree_rcu(selem, rcu);
}

But... we won't need this anymore.

Quoted 28 lines

I think the splat is from CONFIG_PROVE_RAW_LOCK_NESTING=y.

Just happened to bump into Paul briefly offline, his work probably can also avoid the spin_lock in call_rcu_tasks_trace().

I would ignore this splat for now which should go away when it is merged with Paul's work in the 5.17 merge cycle.

Quoted 13 lines

Depending on the urgency, another approach is to rely on my ongoing work removing the call_rcu_tasks_trace() bottleneck. This commit on branch "dev" in the -rcu tree allows boot-time setting of per-CPU callback queues for call_rcu_tasks_trace(), along with the other RCU-tasks flavors:

0b886cc4b10f ("rcu-tasks: Add rcupdate.rcu_task_enqueue_lim to set initial queueing")

Preceding commits actually set up the queues. With these commits, you could boot with rcupdate.rcu_task_enqueue_lim=N, where N greater than or equal to the number of CPUs on your system, to get per-CPU queuing. These commits probably still have a bug or three, but on the other hand, they have survived a couple of weeks worth of rcutorture runs.

Quoted 5 lines

This week's work will allow automatic transition between single-queue and per-CPU-queue operation based on lock contention and the number of callbacks queued.

My current plan is to get this into the next merge window (v5.17).

That would be great.

#17 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 97 lines · KP Singh
Quoted 71 lines · Martin KaFai Lau
Quoted 12 lines · Paul E. McKenney
Quoted 11 lines · KP Singh
Quoted 5 lines · Martin KaFai Lau

I think the global lock will be an issue for the current non-sleepable netdev bpf-prog which could be triggered by external traffic, so a flag is needed here to provide a fast path. I suspect other non-prealloc map may need it in the future, so probably s/BPF_F_SLEEPABLE_STORAGE/BPF_F_SLEEPABLE/ instead.

I was re-working the patches and had a couple of questions.

There are two data structures that get freed under RCU here:

Quoted 8 lines
Quoted 8 lines

struct bpf_local_storage
struct bpf_local_storage_selem

We can choose to free the bpf_local_storage_selem under call_rcu_tasks_trace based on
whether the map it belongs to is sleepable with something like:

if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)

Paul's current work (mentioned by his previous email) will improve the performance of call_rcu_tasks_trace, so it probably can avoid the new BPF_F_SLEEPABLE flag and make it easier to use.

Quoted 10 lines
Quoted 10 lines
    call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
else
    kfree_rcu(selem, rcu);

Questions:

* Can we free bpf_local_storage under kfree_rcu by ensuring it's always accessed in a classical RCU critical section? Or maybe I am missing something and this also needs to be freed under trace RCU if any of the selems are from a sleepable map.

In the inode_storage_lookup() of this patch:

(quoted diff) +5 -1
+#define bpf_local_storage_rcu_lock_held()                      \
+       (rcu_read_lock_held() || rcu_read_lock_trace_held() ||  \
+        rcu_read_lock_bh_held())
@@ -44,7 +45,8 @@ static struct bpf_local_storage_data *inode_storage_lookup(struct inode *inode,
        if (!bsb)
                return NULL;
 
-       inode_storage = rcu_dereference(bsb->storage);
+       inode_storage = rcu_dereference_protected(bsb->storage,
+                                                 bpf_local_storage_rcu_lock_held());
 

Thus, it is not always in classical RCU critical.

Quoted 19 lines
Quoted 19 lines

* There is an issue with nested raw spinlocks, e.g. in bpf_inode_storage.c:bpf_inode_storage_free

  hlist_for_each_entry_safe(selem, n, &local_storage->list, snode) {
  /* Always unlink from map before unlinking from
  * local_storage.
  */
  bpf_selem_unlink_map(selem);
  free_inode_storage = bpf_selem_unlink_storage_nolock(
                 local_storage, selem, false);
  }
  raw_spin_unlock_bh(&local_storage->lock);

in bpf_selem_unlink_storage_nolock (if we add the above logic with the flag in place of kfree_rcu)
call_rcu_tasks_trace grabs a spinlock and these cannot be nested in a raw spin lock.

Quoted 4 lines
Quoted 3 lines
Quoted 3 lines

I am moving the freeing code out of the spinlock, saving the selems on a local list and then doing the free RCU (trace or normal) callbacks at the end. WDYT?

There could be more than one selem to save.

Yes, that's why I was saving them on a local list and then calling kfree_rcu or call_rcu_tasks_trace after unlocking the raw_spin_lock

INIT_HLIST_HEAD(&free_list); 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_local_storage = bpf_selem_unlink_storage_nolock(
    local_storage, selem, false);
    hlist_add_head(&selem->snode, &free_list);
}

raw_spin_unlock_irqrestore(&local_storage->lock, flags);

/* The element needs to be freed outside the raw spinlock because spin
* locks cannot nest inside a raw spin locks and call_rcu_tasks_trace
* grabs a spinklock when the RCU code calls into the scheduler. *
* free_local_storage should always be true as long as
* local_storage->list was non-empty.
*/

Quoted 8 lines
hlist_for_each_entry_safe(selem, n, &free_list, snode) {
    if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)
        call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
    else
        kfree_rcu(selem, rcu);
}

But... we won't need this anymore.

Yep, Paul's work (thanks!) will make this piece simpler.

KP, this set functionally does not depend on Paul's changes. Do you want to spin a new version so that it can be reviewed in parallel? When the rcu-task changes land in -next, it can probably
be merged into bpf-next first before landing the sleepable bpf storage work.

author
#18 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 106 lines · Martin KaFai Lau
Quoted 104 lines · KP Singh
Quoted 71 lines · Martin KaFai Lau
Quoted 12 lines · Paul E. McKenney
Quoted 11 lines · KP Singh
Quoted 5 lines · Martin KaFai Lau

I think the global lock will be an issue for the current non-sleepable netdev bpf-prog which could be triggered by external traffic, so a flag is needed here to provide a fast path. I suspect other non-prealloc map may need it in the future, so probably s/BPF_F_SLEEPABLE_STORAGE/BPF_F_SLEEPABLE/ instead.

I was re-working the patches and had a couple of questions.

There are two data structures that get freed under RCU here:

Quoted 8 lines
Quoted 8 lines

struct bpf_local_storage
struct bpf_local_storage_selem

We can choose to free the bpf_local_storage_selem under call_rcu_tasks_trace based on
whether the map it belongs to is sleepable with something like:

if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)

Paul's current work (mentioned by his previous email) will improve the performance of call_rcu_tasks_trace, so it probably can avoid the new BPF_F_SLEEPABLE flag and make it easier to use.

Quoted 10 lines
Quoted 10 lines
    call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
else
    kfree_rcu(selem, rcu);

Questions:

* Can we free bpf_local_storage under kfree_rcu by ensuring it's always accessed in a classical RCU critical section? Or maybe I am missing something and this also needs to be freed under trace RCU if any of the selems are from a sleepable map.

In the inode_storage_lookup() of this patch:

(quoted diff) +5 -1
+#define bpf_local_storage_rcu_lock_held()                      \
+       (rcu_read_lock_held() || rcu_read_lock_trace_held() ||  \
+        rcu_read_lock_bh_held())
@@ -44,7 +45,8 @@ static struct bpf_local_storage_data *inode_storage_lookup(struct inode *inode,
        if (!bsb)
                return NULL;
 
-       inode_storage = rcu_dereference(bsb->storage);
+       inode_storage = rcu_dereference_protected(bsb->storage,
+                                                 bpf_local_storage_rcu_lock_held());
 

Thus, it is not always in classical RCU critical.

Quoted 19 lines
Quoted 19 lines

* There is an issue with nested raw spinlocks, e.g. in bpf_inode_storage.c:bpf_inode_storage_free

  hlist_for_each_entry_safe(selem, n, &local_storage->list, snode) {
  /* Always unlink from map before unlinking from
  * local_storage.
  */
  bpf_selem_unlink_map(selem);
  free_inode_storage = bpf_selem_unlink_storage_nolock(
                 local_storage, selem, false);
  }
  raw_spin_unlock_bh(&local_storage->lock);

in bpf_selem_unlink_storage_nolock (if we add the above logic with the flag in place of kfree_rcu)
call_rcu_tasks_trace grabs a spinlock and these cannot be nested in a raw spin lock.

Quoted 4 lines
Quoted 3 lines
Quoted 3 lines

I am moving the freeing code out of the spinlock, saving the selems on a local list and then doing the free RCU (trace or normal) callbacks at the end. WDYT?

There could be more than one selem to save.

Yes, that's why I was saving them on a local list and then calling kfree_rcu or call_rcu_tasks_trace after unlocking the raw_spin_lock

INIT_HLIST_HEAD(&free_list); 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_local_storage = bpf_selem_unlink_storage_nolock(
    local_storage, selem, false);
    hlist_add_head(&selem->snode, &free_list);
}

raw_spin_unlock_irqrestore(&local_storage->lock, flags);

/* The element needs to be freed outside the raw spinlock because spin
* locks cannot nest inside a raw spin locks and call_rcu_tasks_trace
* grabs a spinklock when the RCU code calls into the scheduler. *
* free_local_storage should always be true as long as
* local_storage->list was non-empty.
*/

hlist_for_each_entry_safe(selem, n, &free_list, snode) {
    if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)
        call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
    else
        kfree_rcu(selem, rcu);
}
Quoted 2 lines
Quoted 1 line

But... we won't need this anymore.

Yep, Paul's work (thanks!) will make this piece simpler.

+100

Quoted 3 lines

KP, this set functionally does not depend on Paul's changes. Do you want to spin a new version so that it can be reviewed in parallel?

Sure, I will fix the remaining issues (i.e. with RCU locks and renames) and spin a new version.

Quoted 3 lines

When the rcu-task changes land in -next, it can probably be merged into bpf-next first before landing the sleepable bpf storage work.

#19 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 110 lines · KP Singh
Quoted 106 lines · Martin KaFai Lau
Quoted 104 lines · KP Singh
Quoted 71 lines · Martin KaFai Lau
Quoted 12 lines · Paul E. McKenney
Quoted 11 lines · KP Singh
Quoted 5 lines · Martin KaFai Lau

I think the global lock will be an issue for the current non-sleepable netdev bpf-prog which could be triggered by external traffic, so a flag is needed here to provide a fast path. I suspect other non-prealloc map may need it in the future, so probably s/BPF_F_SLEEPABLE_STORAGE/BPF_F_SLEEPABLE/ instead.

I was re-working the patches and had a couple of questions.

There are two data structures that get freed under RCU here:

Quoted 8 lines
Quoted 8 lines

struct bpf_local_storage
struct bpf_local_storage_selem

We can choose to free the bpf_local_storage_selem under call_rcu_tasks_trace based on
whether the map it belongs to is sleepable with something like:

if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)

Paul's current work (mentioned by his previous email) will improve the performance of call_rcu_tasks_trace, so it probably can avoid the new BPF_F_SLEEPABLE flag and make it easier to use.

Quoted 10 lines
Quoted 10 lines
    call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
else
    kfree_rcu(selem, rcu);

Questions:

* Can we free bpf_local_storage under kfree_rcu by ensuring it's always accessed in a classical RCU critical section? Or maybe I am missing something and this also needs to be freed under trace RCU if any of the selems are from a sleepable map.

In the inode_storage_lookup() of this patch:

(quoted diff) +5 -1
+#define bpf_local_storage_rcu_lock_held()                      \
+       (rcu_read_lock_held() || rcu_read_lock_trace_held() ||  \
+        rcu_read_lock_bh_held())
@@ -44,7 +45,8 @@ static struct bpf_local_storage_data *inode_storage_lookup(struct inode *inode,
        if (!bsb)
                return NULL;
 
-       inode_storage = rcu_dereference(bsb->storage);
+       inode_storage = rcu_dereference_protected(bsb->storage,
+                                                 bpf_local_storage_rcu_lock_held());
 

Thus, it is not always in classical RCU critical.

Quoted 19 lines
Quoted 19 lines

* There is an issue with nested raw spinlocks, e.g. in bpf_inode_storage.c:bpf_inode_storage_free

  hlist_for_each_entry_safe(selem, n, &local_storage->list, snode) {
  /* Always unlink from map before unlinking from
  * local_storage.
  */
  bpf_selem_unlink_map(selem);
  free_inode_storage = bpf_selem_unlink_storage_nolock(
                 local_storage, selem, false);
  }
  raw_spin_unlock_bh(&local_storage->lock);

in bpf_selem_unlink_storage_nolock (if we add the above logic with the flag in place of kfree_rcu)
call_rcu_tasks_trace grabs a spinlock and these cannot be nested in a raw spin lock.

Quoted 4 lines
Quoted 3 lines
Quoted 3 lines

I am moving the freeing code out of the spinlock, saving the selems on a local list and then doing the free RCU (trace or normal) callbacks at the end. WDYT?

There could be more than one selem to save.

Yes, that's why I was saving them on a local list and then calling kfree_rcu or call_rcu_tasks_trace after unlocking the raw_spin_lock

INIT_HLIST_HEAD(&free_list); 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_local_storage = bpf_selem_unlink_storage_nolock(
    local_storage, selem, false);
    hlist_add_head(&selem->snode, &free_list);
}

raw_spin_unlock_irqrestore(&local_storage->lock, flags);

/* The element needs to be freed outside the raw spinlock because spin
* locks cannot nest inside a raw spin locks and call_rcu_tasks_trace
* grabs a spinklock when the RCU code calls into the scheduler. *
* free_local_storage should always be true as long as
* local_storage->list was non-empty.
*/

hlist_for_each_entry_safe(selem, n, &free_list, snode) {
    if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)
        call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
    else
        kfree_rcu(selem, rcu);
}
Quoted 2 lines
Quoted 1 line

But... we won't need this anymore.

Yep, Paul's work (thanks!) will make this piece simpler.

Quoted 12 lines

+100

Quoted 3 lines

KP, this set functionally does not depend on Paul's changes. Do you want to spin a new version so that it can be reviewed in parallel?

Sure, I will fix the remaining issues (i.e. with RCU locks and renames) and spin a new version.

Quoted 3 lines

When the rcu-task changes land in -next, it can probably be merged into bpf-next first before landing the sleepable bpf storage work.

And I just now got both the expand-queues and shrink-queues code at least pretending to work, and it will be picked up in the next -next. I was probably too late for today's edition, but there is always tomorrow.

There are probably still bugs, but it is passing much nastier tests than a couple of weeks ago, so here is hoping...

Thanx, Paul

#20 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 124 lines · Paul E. McKenney
Quoted 110 lines · KP Singh
Quoted 106 lines · Martin KaFai Lau
Quoted 104 lines · KP Singh
Quoted 71 lines · Martin KaFai Lau
Quoted 12 lines · Paul E. McKenney
Quoted 11 lines · KP Singh
Quoted 5 lines · Martin KaFai Lau

I think the global lock will be an issue for the current non-sleepable netdev bpf-prog which could be triggered by external traffic, so a flag is needed here to provide a fast path. I suspect other non-prealloc map may need it in the future, so probably s/BPF_F_SLEEPABLE_STORAGE/BPF_F_SLEEPABLE/ instead.

I was re-working the patches and had a couple of questions.

There are two data structures that get freed under RCU here:

Quoted 8 lines
Quoted 8 lines

struct bpf_local_storage
struct bpf_local_storage_selem

We can choose to free the bpf_local_storage_selem under call_rcu_tasks_trace based on
whether the map it belongs to is sleepable with something like:

if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)

Paul's current work (mentioned by his previous email) will improve the performance of call_rcu_tasks_trace, so it probably can avoid the new BPF_F_SLEEPABLE flag and make it easier to use.

Quoted 10 lines
Quoted 10 lines
    call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
else
    kfree_rcu(selem, rcu);

Questions:

* Can we free bpf_local_storage under kfree_rcu by ensuring it's always accessed in a classical RCU critical section? Or maybe I am missing something and this also needs to be freed under trace RCU if any of the selems are from a sleepable map.

In the inode_storage_lookup() of this patch:

(quoted diff) +5 -1
+#define bpf_local_storage_rcu_lock_held()                      \
+       (rcu_read_lock_held() || rcu_read_lock_trace_held() ||  \
+        rcu_read_lock_bh_held())
@@ -44,7 +45,8 @@ static struct bpf_local_storage_data *inode_storage_lookup(struct inode *inode,
        if (!bsb)
                return NULL;
 
-       inode_storage = rcu_dereference(bsb->storage);
+       inode_storage = rcu_dereference_protected(bsb->storage,
+                                                 bpf_local_storage_rcu_lock_held());
 

Thus, it is not always in classical RCU critical.

Quoted 19 lines
Quoted 19 lines

* There is an issue with nested raw spinlocks, e.g. in bpf_inode_storage.c:bpf_inode_storage_free

  hlist_for_each_entry_safe(selem, n, &local_storage->list, snode) {
  /* Always unlink from map before unlinking from
  * local_storage.
  */
  bpf_selem_unlink_map(selem);
  free_inode_storage = bpf_selem_unlink_storage_nolock(
                 local_storage, selem, false);
  }
  raw_spin_unlock_bh(&local_storage->lock);

in bpf_selem_unlink_storage_nolock (if we add the above logic with the flag in place of kfree_rcu)
call_rcu_tasks_trace grabs a spinlock and these cannot be nested in a raw spin lock.

Quoted 4 lines
Quoted 3 lines
Quoted 3 lines

I am moving the freeing code out of the spinlock, saving the selems on a local list and then doing the free RCU (trace or normal) callbacks at the end. WDYT?

There could be more than one selem to save.

Yes, that's why I was saving them on a local list and then calling kfree_rcu or call_rcu_tasks_trace after unlocking the raw_spin_lock

INIT_HLIST_HEAD(&free_list); 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_local_storage = bpf_selem_unlink_storage_nolock(
    local_storage, selem, false);
    hlist_add_head(&selem->snode, &free_list);
}

raw_spin_unlock_irqrestore(&local_storage->lock, flags);

/* The element needs to be freed outside the raw spinlock because spin
* locks cannot nest inside a raw spin locks and call_rcu_tasks_trace
* grabs a spinklock when the RCU code calls into the scheduler. *
* free_local_storage should always be true as long as
* local_storage->list was non-empty.
*/

hlist_for_each_entry_safe(selem, n, &free_list, snode) {
    if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)
        call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
    else
        kfree_rcu(selem, rcu);
}
Quoted 2 lines
Quoted 1 line

But... we won't need this anymore.

Yep, Paul's work (thanks!) will make this piece simpler.

Quoted 12 lines

+100

Quoted 3 lines

KP, this set functionally does not depend on Paul's changes. Do you want to spin a new version so that it can be reviewed in parallel?

Sure, I will fix the remaining issues (i.e. with RCU locks and renames) and spin a new version.

Quoted 3 lines

When the rcu-task changes land in -next, it can probably be merged into bpf-next first before landing the sleepable bpf storage work.

Quoted 6 lines

And I just now got both the expand-queues and shrink-queues code at least pretending to work, and it will be picked up in the next -next. I was probably too late for today's edition, but there is always tomorrow.

There are probably still bugs, but it is passing much nastier tests than a couple of weeks ago, so here is hoping...

And this is now in -next. Please let me know how it goes!

Thanx, Paul

author
#21 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 2 lines · Paul E. McKenney

On Tue, Nov 30, 2021 at 02:51:29PM -0800, Paul E. McKenney wrote:

[...]

Quoted 4 lines
Quoted 2 lines

There are probably still bugs, but it is passing much nastier tests than a couple of weeks ago, so here is hoping...

And this is now in -next. Please let me know how it goes!

I was able to rebase this on linux-next which has Paul's changes and ran it with:

root@kpsingh:~# cat /proc/cmdline
console=ttyS0,115200 root=/dev/sda rw nokaslr rcupdate.rcu_task_enqueue_lim=4

The warning about the nested spinlock in the raw spin locked section is also gone and I don't
see any other warnings. Will send the rebased series after doing a few more checks.

- KP

Quoted 2 lines

Thanx, Paul

#22 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 14 lines · KP Singh
Quoted 2 lines · Paul E. McKenney

On Tue, Nov 30, 2021 at 02:51:29PM -0800, Paul E. McKenney wrote:

[...]

Quoted 4 lines
Quoted 2 lines

There are probably still bugs, but it is passing much nastier tests than a couple of weeks ago, so here is hoping...

And this is now in -next. Please let me know how it goes!

I was able to rebase this on linux-next which has Paul's changes and ran it with:

Quoted 7 lines
root@kpsingh:~# cat /proc/cmdline
console=ttyS0,115200 root=/dev/sda rw nokaslr rcupdate.rcu_task_enqueue_lim=4

The warning about the nested spinlock in the raw spin locked section is also gone and I don't
see any other warnings. Will send the rebased series after doing a few more checks.

Thank you, and here is hoping for continued testing success! ;-)

Thanx, Paul

author
#23 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

In reply to Paul E. McKenney
Quoted 147 lines · Paul E. McKenney
Quoted 145 lines · KP Singh
Quoted 94 lines · Martin KaFai Lau
Quoted 85 lines · Paul E. McKenney
Quoted 61 lines · Martin KaFai Lau

On Tue, Aug 31, 2021 at 09:38:01PM +0200, KP Singh wrote:
[ ... ]

Quoted 49 lines
Quoted 34 lines
Quoted 33 lines
Quoted 25 lines
Quoted 17 lines
Quoted 9 lines

Review bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage, · line 152

Quoted 6 lines
(quoted diff) +1 -1
@@ -131,7 +149,7 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
          SDATA(selem))
              RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);
 
-     kfree_rcu(selem, rcu);
+     call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);

Although the common use case is usually storage_get() much more often than storage_delete(), do you aware any performance impact for the bpf prog that does a lot of storage_delete()?

I have not really measured the impact on deletes, My understanding is that it should
not impact the BPF program, but yes, if there are some critical sections that are prolonged
due to a sleepable program "sleeping" too long, then it would pile up the callbacks.

Quoted 4 lines

But this is not something new, as we have a similar thing in BPF trampolines. If this really
becomes an issue, we could add a flag BPF_F_SLEEPABLE_STORAGE and only maps with this flag would be allowed in sleepable progs.

Agree that is similar to trampoline updates but not sure it is comparable in terms of the frequency of elems being deleted here. e.g. many short lived tcp connections created by external traffic.

Quoted 6 lines

Adding a BPF_F_SLEEPABLE_STORAGE later won't work. It will break existing sleepable bpf prog.

I don't know enough on call_rcu_tasks_trace() here, so the earlier question on perf/callback-pile-up implications in order to decide if extra logic or knob is needed here or not.

I will defer to the others, maybe Alexei and Paul,

Quoted 8 lines
Quoted 2 lines

we could also just
add the flag to not affect existing performance characteristics?

I would see if it is really necessary first. Other sleepable supported maps do not need a flag. Adding one here for local storage will be confusing especially if it turns out to be unnecessary.

Could you run some tests first which can guide the decision?

I think the performance impact would happen only in the worst case which needs some work to simulate. What do you think about:

A bprm_committed_creds program that processes a large argv and also gets a storage on the inode.

Quoted 8 lines

A file_open program that tries to delete the local storage on the inode.

Trigger this code in parallel. i.e. lots of programs that execute with a very large argv and then in parallel the executable being opened to trigger the delete.

Do you have any other ideas? Is there something we could re-use from the selftests?

Quoted 7 lines

There is a bench framework in tools/testing/selftests/bpf/benchs/ that has a parallel thread setup which could be useful.

Don't know how to simulate the "sleeping" too long which then pile-up callbacks. This is not bpf specific. Paul, I wonder if you have similar test to trigger this to compare between call_rcu_tasks_trace() and call_rcu()?

It is definitely the case that call_rcu() is way more scalable than is call_rcu_tasks_trace(). Something about call_rcu_tasks_trace() acquiring a global lock. ;-)

So actually testing it makes a lot of sense.

I do have an rcuscale module, but it is set up more for synchronous grace periods such as synchronize_rcu() and synchronize_rcu_tasks_trace(). It has the beginnings of support for call_rcu() and call_rcu_tasks_trace(), but I would not yet trust them.

But I also have a test for global locking:

$ tools/testing/selftests/rcutorture/bin/kvm.sh --torture refscale --allcpus --duration 5 --configs "NOPREEMPT" --kconfig "CONFIG_NR_CPUS=16" --bootargs "refscale.scale_type=lock refscale.loops=10000 refscale.holdoff=20 torture.disable_onoff_at_boot" --trust-make
Quoted 7 lines

This gives a median lock overhead of 960ns. Running a single CPU rather than 16 of them:

$ tools/testing/selftests/rcutorture/bin/kvm.sh --torture refscale --allcpus --duration 5 --configs "NOPREEMPT" --kconfig "CONFIG_NR_CPUS=16" --bootargs "refscale.scale_type=lock refscale.loops=10000 refscale.holdoff=20 torture.disable_onoff_at_boot" --trust-make

This gives a median lock overhead of 4.1ns, which is way faster. And the greater the number of CPUs, the greater the lock overhead.

Quoted 7 lines

Thanks for the explanation and numbers!

I think the global lock will be an issue for the current non-sleepable netdev bpf-prog which could be triggered by external traffic, so a flag is needed here to provide a fast path. I suspect other non-prealloc map may need it in the future, so probably s/BPF_F_SLEEPABLE_STORAGE/BPF_F_SLEEPABLE/ instead.

I was re-working the patches and had a couple of questions.

There are two data structures that get freed under RCU here:

struct bpf_local_storage
struct bpf_local_storage_selem

We can choose to free the bpf_local_storage_selem under call_rcu_tasks_trace based on
whether the map it belongs to is sleepable with something like:

if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)

    call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
else
    kfree_rcu(selem, rcu);

Questions:

* Can we free bpf_local_storage under kfree_rcu by ensuring it's always accessed in a
classical RCU critical section? Or maybe I am missing something and
this also needs to be freed
under trace RCU if any of the selems are from a sleepable map.

* There is an issue with nested raw spinlocks, e.g. in bpf_inode_storage.c:bpf_inode_storage_free

  hlist_for_each_entry_safe(selem, n, &local_storage->list, snode) {
  /* Always unlink from map before unlinking from
  * local_storage.
  */
  bpf_selem_unlink_map(selem);
  free_inode_storage = bpf_selem_unlink_storage_nolock(
                 local_storage, selem, false);
  }
  raw_spin_unlock_bh(&local_storage->lock);

in bpf_selem_unlink_storage_nolock (if we add the above logic with the flag in place of kfree_rcu)
call_rcu_tasks_trace grabs a spinlock and these cannot be nested in a raw spin lock.

Quoted 5 lines
Quoted 3 lines

I am moving the freeing code out of the spinlock, saving the selems on a local list and then
doing the free RCU (trace or normal) callbacks at the end. WDYT?

Depending on the urgency, another approach is to rely on my ongoing work

It's best to wait for your patches to land and keep this code simple.

Quoted 11 lines

removing the call_rcu_tasks_trace() bottleneck. This commit on branch "dev" in the -rcu tree allows boot-time setting of per-CPU callback queues for call_rcu_tasks_trace(), along with the other RCU-tasks flavors:

0b886cc4b10f ("rcu-tasks: Add rcupdate.rcu_task_enqueue_lim to set initial queueing")

Preceding commits actually set up the queues. With these commits, you could boot with rcupdate.rcu_task_enqueue_lim=N, where N greater than or equal to the number of CPUs on your system, to get per-CPU queuing. These commits probably still have a bug or three, but on the other hand, they have survived a couple of weeks worth of rcutorture runs.

Thank you so much, this would make my life a lot easier :)

- KP

Quoted 51 lines

This week's work will allow automatic transition between single-queue and per-CPU-queue operation based on lock contention and the number of callbacks queued.

My current plan is to get this into the next merge window (v5.17).

Thoughts?

Thanx, Paul

Quoted 40 lines

- KP

Quoted 38 lines

[ ... ]

Quoted 31 lines
Quoted 22 lines
[  143.376587] =============================
[  143.377068] WARNING: suspicious RCU usage
[  143.377541] 5.14.0-rc5-01271-g68e5bda2b18e #4966 Tainted: G           O
[  143.378378] -----------------------------
[  143.378857] kernel/bpf/bpf_local_storage.c:114 suspicious rcu_dereference_check() usage!
[  143.379914]
[  143.379914] other info that might help us debug this:
[  143.379914]
[  143.380838]
[  143.380838] rcu_scheduler_active = 2, debug_locks = 1
[  143.381602] 4 locks held by mv/1781:
[  143.382025]  #0: ffff888121e7c438 (sb_writers#6){.+.+}-{0:0}, at: do_renameat2+0x2f5/0xa80
[  143.383009]  #1: ffff88812ce68760 (&type->i_mutex_dir_key#5/1){+.+.}-{3:3}, at: lock_rename+0x1f4/0x250
[  143.384144]  #2: ffffffff843fbc60 (rcu_read_lock_trace){....}-{0:0}, at: __bpf_prog_enter_sleepable+0x45/0x160
[  143.385326]  #3: ffff88811d8348b8 (&storage->lock){..-.}-{2:2}, at: __bpf_selem_unlink_storage+0x7d/0x170
[  143.386459]
[  143.386459] stack backtrace:
[  143.386983] CPU: 2 PID: 1781 Comm: mv Tainted: G           O      5.14.0-rc5-01271-g68e5bda2b18e #4966
[  143.388071] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.9.3-1.el7.centos 04/01/2014
[  143.389146] Call Trace:
[  143.389446]  dump_stack_lvl+0x5b/0x82
[  143.389901]  dump_stack+0x10/0x12
Quoted 8 lines
[  143.390302]  lockdep_rcu_suspicious+0x15c/0x167
[  143.390854]  bpf_selem_unlink_storage_nolock+0x2e1/0x6d0
[  143.391501]  __bpf_selem_unlink_storage+0xb7/0x170
[  143.392085]  bpf_selem_unlink+0x1b/0x30
[  143.392554]  bpf_inode_storage_delete+0x57/0xa0
[  143.393112]  bpf_prog_31e277fe2c132665_inode_rename+0x9c/0x268
[  143.393814]  bpf_trampoline_6442476301_0+0x4e/0x1000
[  143.394413]  bpf_lsm_inode_rename+0x5/0x10
Quoted 3 lines

I am not sure what line 114 is (it is a blank line in bpf-next), but you might be missing a rcu_read_lock_trace_held() in the second argument of rcu_dereference_check().

Right, this path is only under rcu_read_lock_trace().

#24 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 162 lines · KP Singh
Quoted 147 lines · Paul E. McKenney
Quoted 145 lines · KP Singh
Quoted 94 lines · Martin KaFai Lau
Quoted 85 lines · Paul E. McKenney
Quoted 61 lines · Martin KaFai Lau

On Tue, Aug 31, 2021 at 09:38:01PM +0200, KP Singh wrote:
[ ... ]

Quoted 49 lines
Quoted 34 lines
Quoted 33 lines
Quoted 25 lines
Quoted 17 lines
Quoted 9 lines
Quoted 6 lines

@@ -131,7 +149,7 @@ bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage,
SDATA(selem))
RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL);

- kfree_rcu(selem, rcu);
+ call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);

Although the common use case is usually storage_get() much more often than storage_delete(), do you aware any performance impact for the bpf prog that does a lot of storage_delete()?

I have not really measured the impact on deletes, My understanding is that it should
not impact the BPF program, but yes, if there are some critical sections that are prolonged
due to a sleepable program "sleeping" too long, then it would pile up the callbacks.

Quoted 4 lines

But this is not something new, as we have a similar thing in BPF trampolines. If this really
becomes an issue, we could add a flag BPF_F_SLEEPABLE_STORAGE and only maps with this flag would be allowed in sleepable progs.

Agree that is similar to trampoline updates but not sure it is comparable in terms of the frequency of elems being deleted here. e.g. many short lived tcp connections created by external traffic.

Quoted 6 lines

Adding a BPF_F_SLEEPABLE_STORAGE later won't work. It will break existing sleepable bpf prog.

I don't know enough on call_rcu_tasks_trace() here, so the earlier question on perf/callback-pile-up implications in order to decide if extra logic or knob is needed here or not.

I will defer to the others, maybe Alexei and Paul,

Quoted 8 lines
Quoted 2 lines

we could also just
add the flag to not affect existing performance characteristics?

I would see if it is really necessary first. Other sleepable supported maps do not need a flag. Adding one here for local storage will be confusing especially if it turns out to be unnecessary.

Could you run some tests first which can guide the decision?

I think the performance impact would happen only in the worst case which needs some work to simulate. What do you think about:

A bprm_committed_creds program that processes a large argv and also gets a storage on the inode.

Quoted 8 lines

A file_open program that tries to delete the local storage on the inode.

Trigger this code in parallel. i.e. lots of programs that execute with a very large argv and then in parallel the executable being opened to trigger the delete.

Do you have any other ideas? Is there something we could re-use from the selftests?

Quoted 7 lines

There is a bench framework in tools/testing/selftests/bpf/benchs/ that has a parallel thread setup which could be useful.

Don't know how to simulate the "sleeping" too long which then pile-up callbacks. This is not bpf specific. Paul, I wonder if you have similar test to trigger this to compare between call_rcu_tasks_trace() and call_rcu()?

It is definitely the case that call_rcu() is way more scalable than is call_rcu_tasks_trace(). Something about call_rcu_tasks_trace() acquiring a global lock. ;-)

So actually testing it makes a lot of sense.

I do have an rcuscale module, but it is set up more for synchronous grace periods such as synchronize_rcu() and synchronize_rcu_tasks_trace(). It has the beginnings of support for call_rcu() and call_rcu_tasks_trace(), but I would not yet trust them.

But I also have a test for global locking:

$ tools/testing/selftests/rcutorture/bin/kvm.sh --torture refscale --allcpus --duration 5 --configs "NOPREEMPT" --kconfig "CONFIG_NR_CPUS=16" --bootargs "refscale.scale_type=lock refscale.loops=10000 refscale.holdoff=20 torture.disable_onoff_at_boot" --trust-make
Quoted 7 lines

This gives a median lock overhead of 960ns. Running a single CPU rather than 16 of them:

$ tools/testing/selftests/rcutorture/bin/kvm.sh --torture refscale --allcpus --duration 5 --configs "NOPREEMPT" --kconfig "CONFIG_NR_CPUS=16" --bootargs "refscale.scale_type=lock refscale.loops=10000 refscale.holdoff=20 torture.disable_onoff_at_boot" --trust-make

This gives a median lock overhead of 4.1ns, which is way faster. And the greater the number of CPUs, the greater the lock overhead.

Quoted 7 lines

Thanks for the explanation and numbers!

I think the global lock will be an issue for the current non-sleepable netdev bpf-prog which could be triggered by external traffic, so a flag is needed here to provide a fast path. I suspect other non-prealloc map may need it in the future, so probably s/BPF_F_SLEEPABLE_STORAGE/BPF_F_SLEEPABLE/ instead.

I was re-working the patches and had a couple of questions.

There are two data structures that get freed under RCU here:

struct bpf_local_storage
struct bpf_local_storage_selem

We can choose to free the bpf_local_storage_selem under call_rcu_tasks_trace based on
whether the map it belongs to is sleepable with something like:

if (selem->sdata.smap->map.map_flags & BPF_F_SLEEPABLE_STORAGE)

    call_rcu_tasks_trace(&selem->rcu, bpf_selem_free_rcu);
else
    kfree_rcu(selem, rcu);

Questions:

* Can we free bpf_local_storage under kfree_rcu by ensuring it's always accessed in a
classical RCU critical section? Or maybe I am missing something and
this also needs to be freed
under trace RCU if any of the selems are from a sleepable map.

* There is an issue with nested raw spinlocks, e.g. in bpf_inode_storage.c:bpf_inode_storage_free

  hlist_for_each_entry_safe(selem, n, &local_storage->list, snode) {
  /* Always unlink from map before unlinking from
  * local_storage.
  */
  bpf_selem_unlink_map(selem);
  free_inode_storage = bpf_selem_unlink_storage_nolock(
                 local_storage, selem, false);
  }
  raw_spin_unlock_bh(&local_storage->lock);

in bpf_selem_unlink_storage_nolock (if we add the above logic with the flag in place of kfree_rcu)
call_rcu_tasks_trace grabs a spinlock and these cannot be nested in a raw spin lock.

Quoted 5 lines
Quoted 3 lines

I am moving the freeing code out of the spinlock, saving the selems on a local list and then
doing the free RCU (trace or normal) callbacks at the end. WDYT?

Depending on the urgency, another approach is to rely on my ongoing work

It's best to wait for your patches to land and keep this code simple.

Quoted 6 lines

removing the call_rcu_tasks_trace() bottleneck. This commit on branch "dev" in the -rcu tree allows boot-time setting of per-CPU callback queues for call_rcu_tasks_trace(), along with the other RCU-tasks flavors:

0b886cc4b10f ("rcu-tasks: Add rcupdate.rcu_task_enqueue_lim to set initial queueing")

Quoted 7 lines
Quoted 5 lines

Preceding commits actually set up the queues. With these commits, you could boot with rcupdate.rcu_task_enqueue_lim=N, where N greater than or equal to the number of CPUs on your system, to get per-CPU queuing. These commits probably still have a bug or three, but on the other hand, they have survived a couple of weeks worth of rcutorture runs.

Thank you so much, this would make my life a lot easier :)

And the code that automatically increases the number of callback queues when it senses sufficient lock contention is now passing modest rcutorture testing. I have set things up so that, failing additional problems, Stephen Rothwell should be taking it into the next -next releases.

Automatically decreasing based on few callbacks is a task for next week. ;-)

Thanx, Paul

Quoted 53 lines

- KP

Quoted 51 lines

This week's work will allow automatic transition between single-queue and per-CPU-queue operation based on lock contention and the number of callbacks queued.

My current plan is to get this into the next merge window (v5.17).

Thoughts?

Thanx, Paul

Quoted 40 lines

- KP

Quoted 38 lines

[ ... ]

Quoted 31 lines
Quoted 22 lines
[  143.376587] =============================
[  143.377068] WARNING: suspicious RCU usage
[  143.377541] 5.14.0-rc5-01271-g68e5bda2b18e #4966 Tainted: G           O
[  143.378378] -----------------------------
[  143.378857] kernel/bpf/bpf_local_storage.c:114 suspicious rcu_dereference_check() usage!
[  143.379914]
[  143.379914] other info that might help us debug this:
[  143.379914]
[  143.380838]
[  143.380838] rcu_scheduler_active = 2, debug_locks = 1
[  143.381602] 4 locks held by mv/1781:
[  143.382025]  #0: ffff888121e7c438 (sb_writers#6){.+.+}-{0:0}, at: do_renameat2+0x2f5/0xa80
[  143.383009]  #1: ffff88812ce68760 (&type->i_mutex_dir_key#5/1){+.+.}-{3:3}, at: lock_rename+0x1f4/0x250
[  143.384144]  #2: ffffffff843fbc60 (rcu_read_lock_trace){....}-{0:0}, at: __bpf_prog_enter_sleepable+0x45/0x160
[  143.385326]  #3: ffff88811d8348b8 (&storage->lock){..-.}-{2:2}, at: __bpf_selem_unlink_storage+0x7d/0x170
[  143.386459]
[  143.386459] stack backtrace:
[  143.386983] CPU: 2 PID: 1781 Comm: mv Tainted: G           O      5.14.0-rc5-01271-g68e5bda2b18e #4966
[  143.388071] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.9.3-1.el7.centos 04/01/2014
[  143.389146] Call Trace:
[  143.389446]  dump_stack_lvl+0x5b/0x82
[  143.389901]  dump_stack+0x10/0x12
Quoted 8 lines
[  143.390302]  lockdep_rcu_suspicious+0x15c/0x167
[  143.390854]  bpf_selem_unlink_storage_nolock+0x2e1/0x6d0
[  143.391501]  __bpf_selem_unlink_storage+0xb7/0x170
[  143.392085]  bpf_selem_unlink+0x1b/0x30
[  143.392554]  bpf_inode_storage_delete+0x57/0xa0
[  143.393112]  bpf_prog_31e277fe2c132665_inode_rename+0x9c/0x268
[  143.393814]  bpf_trampoline_6442476301_0+0x4e/0x1000
[  143.394413]  bpf_lsm_inode_rename+0x5/0x10
Quoted 3 lines

I am not sure what line 114 is (it is a blank line in bpf-next), but you might be missing a rcu_read_lock_trace_held() in the second argument of rcu_dereference_check().

Right, this path is only under rcu_read_lock_trace().

#25 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

In reply to Martin KaFai Lau
Quoted 71 lines · Martin KaFai Lau
Quoted 49 lines
Quoted 49 lines
Quoted 36 lines
Quoted 36 lines
Quoted 24 lines
Quoted 24 lines
Quoted 24 lines
net/core/bpf_sk_storage.c +3 -1
@@ -13,6 +13,7 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
 
 DEFINE_BPF_STORAGE_CACHE(sk_cache);
 
@@ -22,7 +23,8 @@ bpf_sk_storage_lookup(struct sock *sk, struct bpf_map *map, bool cacheit_lockit)
      struct bpf_local_storage *sk_storage;
      struct bpf_local_storage_map *smap;
 
-     sk_storage = rcu_dereference(sk->sk_bpf_storage);
+     sk_storage = rcu_dereference_protected(sk->sk_bpf_storage,
+                                            bpf_local_storage_rcu_lock_held());
      if (!sk_storage)
              return NULL;
 
@@ -258,6 +260,7 @@ BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk,
 {
      struct bpf_local_storage_data *sdata;
 
Quoted 8 lines
Quoted 4 lines

net/core/bpf_sk_storage.c BPF_CALL_4(bpf_sk_storage_get, struct bpf_map *, map, struct sock *, sk, · line 264

Quoted 2 lines
net/core/bpf_sk_storage.c +1 -0
+     WARN_ON_ONCE(!bpf_local_storage_rcu_lock_held());
      if (!sk || !sk_fullsock(sk) || flags > BPF_SK_STORAGE_GET_F_CREATE)

sk is protected by rcu_read_lock here.
Is it always safe to access it with the rcu_read_lock_trace alone ?

We don't dereference sk with an rcu_dereference though, is it still the case for tracing and LSM programs? Or is it somehow implicity protected even though we don't use rcu_dereference since that's just a READ_ONCE + some checks?

e.g. the bpf_prog (currently run under rcu_read_lock()) may read the sk from req_sk->sk which I don't think the verifier will optimize it out, so as good as READ_ONCE(), iiuc.

Quoted 8 lines
Quoted 2 lines

The sk here is obtained from the bpf_lsm_socket_* hooks? Those sk should have a refcnt, right? If that is the case, it should be good enough for now.

The one passed in the arguments yes, but if you notice the discussion in

https://lore.kernel.org/bpf/[email protected]/T/#me254212a125516a6c5d2fbf349b97c199e66dce0

one may also get an sk in LSM and tracing progs by pointer walking.

Right. There is pointer walking case.
e.g. "struct request_sock __rcu *fastopen_rsk" in tcp_sock. I don't think it is possible for lsm to get a hold on tcp_sock but agree that other similar cases could happen.

Quoted 7 lines
Quoted 5 lines

May be for now, in sleepable program, only allow safe sk ptr
to be used in helpers that take sk PTR_TO_BTF_ID argument.
e.g. sock->sk is safe in the test in patch 2. The same should go for other storages like inode. This needs verifier change.

Sorry, I may be missing some context. Do you mean wait for Yonghong's work?

I don't think we have to wait. Just saying Yonghong's work could fit well in this use case in the future.

Quoted 2 lines

Or is there another way to update the verifier to recognize safe sk and inode pointers?

I was thinking specifically for this pointer walking case. Take a look at btf_struct_access(). It walks the struct
in the verifier and figures out reading sock->sk will get
a "struct sock *". It marks the reg to PTR_TO_BTF_ID.
This will allow the bpf prog to directly read from sk (e.g. sk->sk_num) or pass the sk to helper that takes a "struct sock *" pointer. Reading from any sk pointer is fine since it is protected by BPF_PROBE_MEM read. However, we only allow the sk from sock->sk to be passed to the helper here because we only know this one is refcnt-ed.

Quoted 4 lines

Take a look at check_ptr_to_btf_access(). An individual verifier_ops can also have its own btf_struct_access. One possibility is to introduce a (new) PTR_TO_RDONLY_BTF_ID to mean it can only do BPR_PROBE_MEM read but cannot be used in helper.

KP, not sure how far you are with the verifier change, if it is moving well, please ignore. Otherwise,
I looked at the sock a bit and I currently don't see
potential concern on the following pointer case without the rcu_read_lock for those sock-related sleepable lsm hooks in bpf_lsm.c. If cases did come up later (e.g. other lsm hooks are added or something got overlooked), we could bring in a bigger hammer to make the above verifier change. I think it should be fine to stop some exotic usage later that is proven to be not safe. For the lsm sleepable hook case, another option is to lock the sock first before calling the bpf prog.

If you agree a similar situation is also true for inode and task, do you want to respin the patches addressing other points discussed in this thread.

author
#26 lore raw

Re: [PATCH bpf-next 1/2] bpf: Allow bpf_local_storage to be used by sleepable programs

Quoted 10 lines · Martin KaFai Lau
Quoted 8 lines · Martin KaFai Lau
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
net/core/bpf_sk_storage.c +1 -0
@@ -13,6 +13,7 @@
 #include <net/sock.h>
 #include <uapi/linux/sock_diag.h>
 #include <uapi/linux/btf.h>
+#include <linux/rcupdate_trace.h>
 

[...]

Quoted 16 lines
Quoted 12 lines
Quoted 2 lines

Or is there another way to update the verifier to recognize safe sk and inode pointers?

I was thinking specifically for this pointer walking case. Take a look at btf_struct_access(). It walks the struct
in the verifier and figures out reading sock->sk will get
a "struct sock *". It marks the reg to PTR_TO_BTF_ID.
This will allow the bpf prog to directly read from sk (e.g. sk->sk_num) or pass the sk to helper that takes a "struct sock *" pointer. Reading from any sk pointer is fine since it is protected by BPF_PROBE_MEM read. However, we only allow the sk from sock->sk to be passed to the helper here because we only know this one is refcnt-ed.

Quoted 4 lines

Take a look at check_ptr_to_btf_access(). An individual verifier_ops can also have its own btf_struct_access. One possibility is to introduce a (new) PTR_TO_RDONLY_BTF_ID to mean it can only do BPR_PROBE_MEM read but cannot be used in helper.

Quoted 8 lines

KP, not sure how far you are with the verifier change, if it is moving well, please ignore. Otherwise,
I looked at the sock a bit and I currently don't see
potential concern on the following pointer case without the rcu_read_lock for those sock-related sleepable lsm hooks in bpf_lsm.c. If cases did come up later (e.g. other lsm hooks are added or something got overlooked), we could bring in a bigger hammer to make the above verifier change. I think it should be fine to stop some exotic usage

+1 Makes sense.

Quoted 6 lines

later that is proven to be not safe. For the lsm sleepable hook case, another option is to lock the sock first before calling the bpf prog.

If you agree a similar situation is also true for inode and task, do you want to respin the patches addressing other points discussed in this thread.

I will respin the series with the other changes discussed.

author
#27 lore raw

PATCH 2/2 bpf/selftests: Update local storage selftest for sleepable programs

In reply to KP Singh

Remove the spin lock logic and update the selftests to use sleepable programs to use a mix of sleepable and non-sleepable programs. It's more useful to test the sleepable programs since the tests don't really need spinlocks.

---
 .../bpf/prog_tests/test_local_storage.c       | 20 +++++-----------
 .../selftests/bpf/progs/local_storage.c       | 24 ++++---------------
 2 files changed, 11 insertions(+), 33 deletions(-)
tools/testing/selftests/bpf/prog_tests/test_local_storage.c +6 -14
index d2c16eaae367..26ac26a88026 100644
@@ -28,10 +28,6 @@ static unsigned int duration;
 struct storage {
 	void *inode;
 	unsigned int value;
-	/* Lock ensures that spin locked versions of local stoage operations
-	 * also work, most operations in this tests are still single threaded
-	 */
-	struct bpf_spin_lock lock;
 };
 
 /* Fork and exec the provided rm binary and return the exit code of the
@@ -66,27 +62,24 @@ static int run_self_unlink(int *monitored_pid, const char *rm_path)
 
 static bool check_syscall_operations(int map_fd, int obj_fd)
 {
-	struct storage val = { .value = TEST_STORAGE_VALUE, .lock = { 0 } },
-		       lookup_val = { .value = 0, .lock = { 0 } };
+	struct storage val = { .value = TEST_STORAGE_VALUE },
+		       lookup_val = { .value = 0 };
 	int err;
 
 	/* Looking up an existing element should fail initially */
-	err = bpf_map_lookup_elem_flags(map_fd, &obj_fd, &lookup_val,
-					BPF_F_LOCK);
+	err = bpf_map_lookup_elem_flags(map_fd, &obj_fd, &lookup_val, 0);
 	if (CHECK(!err || errno != ENOENT, "bpf_map_lookup_elem",
 		  "err:%d errno:%d\n", err, errno))
 		return false;
 
 	/* Create a new element */
-	err = bpf_map_update_elem(map_fd, &obj_fd, &val,
-				  BPF_NOEXIST | BPF_F_LOCK);
+	err = bpf_map_update_elem(map_fd, &obj_fd, &val, BPF_NOEXIST);
 	if (CHECK(err < 0, "bpf_map_update_elem", "err:%d errno:%d\n", err,
 		  errno))
 		return false;
 
 	/* Lookup the newly created element */
-	err = bpf_map_lookup_elem_flags(map_fd, &obj_fd, &lookup_val,
-					BPF_F_LOCK);
+	err = bpf_map_lookup_elem_flags(map_fd, &obj_fd, &lookup_val, 0);
 	if (CHECK(err < 0, "bpf_map_lookup_elem", "err:%d errno:%d", err,
 		  errno))
 		return false;
@@ -102,8 +95,7 @@ static bool check_syscall_operations(int map_fd, int obj_fd)
 		return false;
 
 	/* The lookup should fail, now that the element has been deleted */
-	err = bpf_map_lookup_elem_flags(map_fd, &obj_fd, &lookup_val,
-					BPF_F_LOCK);
+	err = bpf_map_lookup_elem_flags(map_fd, &obj_fd, &lookup_val, 0);
 	if (CHECK(!err || errno != ENOENT, "bpf_map_lookup_elem",
 		  "err:%d errno:%d\n", err, errno))
 		return false;
tools/testing/selftests/bpf/progs/local_storage.c +5 -19
index 95868bc7ada9..9b1f9b75d5c2 100644
@@ -20,7 +20,6 @@ int sk_storage_result = -1;
 struct local_storage {
 	struct inode *exec_inode;
 	__u32 value;
-	struct bpf_spin_lock lock;
 };
 
 struct {
@@ -58,9 +57,7 @@ int BPF_PROG(unlink_hook, struct inode *dir, struct dentry *victim)
 				       bpf_get_current_task_btf(), 0, 0);
 	if (storage) {
 		/* Don't let an executable delete itself */
-		bpf_spin_lock(&storage->lock);
 		is_self_unlink = storage->exec_inode == victim->d_inode;
-		bpf_spin_unlock(&storage->lock);
 		if (is_self_unlink)
 			return -EPERM;
 	}
@@ -68,7 +65,7 @@ int BPF_PROG(unlink_hook, struct inode *dir, struct dentry *victim)
 	return 0;
 }
 
-SEC("lsm/inode_rename")
+SEC("lsm.s/inode_rename")
 int BPF_PROG(inode_rename, struct inode *old_dir, struct dentry *old_dentry,
 	     struct inode *new_dir, struct dentry *new_dentry,
 	     unsigned int flags)
@@ -89,10 +86,8 @@ int BPF_PROG(inode_rename, struct inode *old_dir, struct dentry *old_dentry,
 	if (!storage)
 		return 0;
 
-	bpf_spin_lock(&storage->lock);
 	if (storage->value != DUMMY_STORAGE_VALUE)
 		inode_storage_result = -1;
-	bpf_spin_unlock(&storage->lock);
 
 	err = bpf_inode_storage_delete(&inode_storage_map, old_dentry->d_inode);
 	if (!err)
@@ -101,7 +96,7 @@ int BPF_PROG(inode_rename, struct inode *old_dir, struct dentry *old_dentry,
 	return 0;
 }
 
-SEC("lsm/socket_bind")
+SEC("lsm.s/socket_bind")
 int BPF_PROG(socket_bind, struct socket *sock, struct sockaddr *address,
 	     int addrlen)
 {
@@ -117,10 +112,8 @@ int BPF_PROG(socket_bind, struct socket *sock, struct sockaddr *address,
 	if (!storage)
 		return 0;
 
-	bpf_spin_lock(&storage->lock);
 	if (storage->value != DUMMY_STORAGE_VALUE)
 		sk_storage_result = -1;
-	bpf_spin_unlock(&storage->lock);
 
 	err = bpf_sk_storage_delete(&sk_storage_map, sock->sk);
 	if (!err)
@@ -129,7 +122,7 @@ int BPF_PROG(socket_bind, struct socket *sock, struct sockaddr *address,
 	return 0;
 }
 
-SEC("lsm/socket_post_create")
+SEC("lsm.s/socket_post_create")
 int BPF_PROG(socket_post_create, struct socket *sock, int family, int type,
 	     int protocol, int kern)
 {
@@ -144,9 +137,7 @@ int BPF_PROG(socket_post_create, struct socket *sock, int family, int type,
 	if (!storage)
 		return 0;
 
-	bpf_spin_lock(&storage->lock);
 	storage->value = DUMMY_STORAGE_VALUE;
-	bpf_spin_unlock(&storage->lock);
 
 	return 0;
 }
@@ -154,7 +145,7 @@ int BPF_PROG(socket_post_create, struct socket *sock, int family, int type,
 /* This uses the local storage to remember the inode of the binary that a
  * process was originally executing.
  */
-SEC("lsm/bprm_committed_creds")
+SEC("lsm.s/bprm_committed_creds")
 void BPF_PROG(exec, struct linux_binprm *bprm)
 {
 	__u32 pid = bpf_get_current_pid_tgid() >> 32;
@@ -166,18 +157,13 @@ void BPF_PROG(exec, struct linux_binprm *bprm)
 	storage = bpf_task_storage_get(&task_storage_map,
 				       bpf_get_current_task_btf(), 0,
 				       BPF_LOCAL_STORAGE_GET_F_CREATE);
-	if (storage) {
-		bpf_spin_lock(&storage->lock);
+	if (storage)
 		storage->exec_inode = bprm->file->f_inode;
-		bpf_spin_unlock(&storage->lock);
-	}
 
 	storage = bpf_inode_storage_get(&inode_storage_map, bprm->file->f_inode,
 					0, BPF_LOCAL_STORAGE_GET_F_CREATE);
 	if (!storage)
 		return;
 
-	bpf_spin_lock(&storage->lock);
 	storage->value = DUMMY_STORAGE_VALUE;
-	bpf_spin_unlock(&storage->lock);
 }
Signature · 1 line
2.33.0.259.gc128427fd7-goog