[bpf,v2,7/9] bpf: Use raw_spinlock_t for LPM trie

Commit Message

Hou Tao Nov. 27, 2024, 12:46 a.m. UTC

From: Hou Tao <[e-mail]>

After switching from kmalloc() to the bpf memory allocator, there will be
no blocking operation during the update of LPM trie. Therefore, change
trie->lock from spinlock_t to raw_spinlock_t to make LPM trie usable in
atomic context, even on RT kernels.

The max value of prefixlen is 2048. Therefore, update or deletion
operations will find the target after at most 2048 comparisons.
Constructing a test case which updates an element after 2048 comparisons
under a 8 CPU VM, and the average time and the maximal time for such
update operation is about 210us and 900us.

Signed-off-by: Hou Tao <[e-mail]>
---
 kernel/bpf/lpm_trie.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

Comments

Toke Høiland-Jørgensen Nov. 29, 2024, 12:18 p.m. UTC | #1

Hou Tao <[e-mail]> writes:

> From: Hou Tao <[e-mail]>
>
> After switching from kmalloc() to the bpf memory allocator, there will be
> no blocking operation during the update of LPM trie. Therefore, change
> trie->lock from spinlock_t to raw_spinlock_t to make LPM trie usable in
> atomic context, even on RT kernels.
>
> The max value of prefixlen is 2048. Therefore, update or deletion
> operations will find the target after at most 2048 comparisons.
> Constructing a test case which updates an element after 2048 comparisons
> under a 8 CPU VM, and the average time and the maximal time for such
> update operation is about 210us and 900us.

That is... quite a long time? I'm not sure we have any guidance on what
the maximum acceptable time is (perhaps the RT folks can weigh in
here?), but stalling for almost a millisecond seems long.

Especially doing this unconditionally seems a bit risky; this means that
even a networking program using the lpm map in the data path can stall
the system for that long, even if it would have been perfectly happy to
be preempted.

So one option here could be to make it conditional? As in, have a map
flag (on creation) that switches to raw_spinlock usage, and reject using
the map from atomic context if that flag is not set?

-Toke

Patch

diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
index 4a3d837e9c9a..81b3554754ae 100644
--- a/kernel/bpf/lpm_trie.c
+++ b/kernel/bpf/lpm_trie.c
@@ -36,7 +36,7 @@  struct lpm_trie {
 	size_t				n_entries;
 	size_t				max_prefixlen;
 	size_t				data_size;
-	spinlock_t			lock;
+	raw_spinlock_t			lock;
 };
 
 /* This trie implements a longest prefix match algorithm that can be used to
@@ -336,7 +336,7 @@  static long trie_update_elem(struct bpf_map *map,
 	if (key->prefixlen > trie->max_prefixlen)
 		return -EINVAL;
 
-	spin_lock_irqsave(&trie->lock, irq_flags);
+	raw_spin_lock_irqsave(&trie->lock, irq_flags);
 
 	/* Allocate and fill a new node */
 	new_node = lpm_trie_node_alloc(trie, value);
@@ -446,7 +446,7 @@  static long trie_update_elem(struct bpf_map *map,
 	if (ret)
 		bpf_mem_cache_free(&trie->ma, new_node);
 	bpf_mem_cache_free_rcu(&trie->ma, free_node);
-	spin_unlock_irqrestore(&trie->lock, irq_flags);
+	raw_spin_unlock_irqrestore(&trie->lock, irq_flags);
 
 	return ret;
 }
@@ -467,7 +467,7 @@  static long trie_delete_elem(struct bpf_map *map, void *_key)
 	if (key->prefixlen > trie->max_prefixlen)
 		return -EINVAL;
 
-	spin_lock_irqsave(&trie->lock, irq_flags);
+	raw_spin_lock_irqsave(&trie->lock, irq_flags);
 
 	/* Walk the tree looking for an exact key/length match and keeping
 	 * track of the path we traverse.  We will need to know the node
@@ -545,7 +545,7 @@  static long trie_delete_elem(struct bpf_map *map, void *_key)
 out:
 	bpf_mem_cache_free_rcu(&trie->ma, free_parent);
 	bpf_mem_cache_free_rcu(&trie->ma, free_node);
-	spin_unlock_irqrestore(&trie->lock, irq_flags);
+	raw_spin_unlock_irqrestore(&trie->lock, irq_flags);
 
 	return ret;
 }
@@ -591,7 +591,7 @@  static struct bpf_map *trie_alloc(union bpf_attr *attr)
 			  offsetof(struct bpf_lpm_trie_key_u8, data);
 	trie->max_prefixlen = trie->data_size * 8;
 
-	spin_lock_init(&trie->lock);
+	raw_spin_lock_init(&trie->lock);
 
 	/* Allocate intermediate and leaf nodes from the same allocator */
 	leaf_size = sizeof(struct lpm_trie_node) + trie->data_size +