This is a note to let you know that I've just added the patch titled
bpf: Handle in-place update for full LPM trie correctly
to the 6.1-stable tree which can be found at:
http://www.kernel.org/git/?p=linux/kernel/git/stable/stable-queue.git;a=summary
The filename of the patch is:
bpf-handle-in-place-update-for-full-lpm-trie-correct.patch
and it can be found in the queue-6.1 subdirectory.
If you, or anyone else, feels it should not be added to the stable tree,
please let <stable@xxxxxxxxxxxxxxx> know about it.
commit 32d6dc38fee33d57d3965fefeecacf8bd0d2a91c
Author: Hou Tao <houtao1@xxxxxxxxxx>
Date: Fri Dec 6 19:06:17 2024 +0800
bpf: Handle in-place update for full LPM trie correctly
[ Upstream commit 532d6b36b2bfac5514426a97a4df8d103d700d43 ]
When a LPM trie is full, in-place updates of existing elements
incorrectly return -ENOSPC.
Fix this by deferring the check of trie->n_entries. For new insertions,
n_entries must not exceed max_entries. However, in-place updates are
allowed even when the trie is full.
Fixes: b95a5c4db09b ("bpf: add a longest prefix match trie map implementation")
Reviewed-by: Toke Høiland-Jørgensen <toke@xxxxxxxxxx>
Signed-off-by: Hou Tao <houtao1@xxxxxxxxxx>
Link: https://lore.kernel.org/r/20241206110622.1161752-5-houtao@xxxxxxxxxxxxxxx
Signed-off-by: Alexei Starovoitov <ast@xxxxxxxxxx>
Signed-off-by: Sasha Levin <sashal@xxxxxxxxxx>
diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
index 694fbf9891f4f..c5fa2a74de771 100644
--- a/kernel/bpf/lpm_trie.c
+++ b/kernel/bpf/lpm_trie.c
@@ -302,6 +302,16 @@ static struct lpm_trie_node *lpm_trie_node_alloc(const struct lpm_trie *trie,
return node;
}
+static int trie_check_add_elem(struct lpm_trie *trie, u64 flags)
+{
+ if (flags == BPF_EXIST)
+ return -ENOENT;
+ if (trie->n_entries == trie->map.max_entries)
+ return -ENOSPC;
+ trie->n_entries++;
+ return 0;
+}
+
/* Called from syscall or from eBPF program */
static int trie_update_elem(struct bpf_map *map,
void *_key, void *value, u64 flags)
@@ -325,20 +335,12 @@ static int trie_update_elem(struct bpf_map *map,
spin_lock_irqsave(&trie->lock, irq_flags);
/* Allocate and fill a new node */
-
- if (trie->n_entries == trie->map.max_entries) {
- ret = -ENOSPC;
- goto out;
- }
-
new_node = lpm_trie_node_alloc(trie, value);
if (!new_node) {
ret = -ENOMEM;
goto out;
}
- trie->n_entries++;
-
new_node->prefixlen = key->prefixlen;
RCU_INIT_POINTER(new_node->child[0], NULL);
RCU_INIT_POINTER(new_node->child[1], NULL);
@@ -368,10 +370,10 @@ static int trie_update_elem(struct bpf_map *map,
* simply assign the @new_node to that slot and be done.
*/
if (!node) {
- if (flags == BPF_EXIST) {
- ret = -ENOENT;
+ ret = trie_check_add_elem(trie, flags);
+ if (ret)
goto out;
- }
+
rcu_assign_pointer(*slot, new_node);
goto out;
}
@@ -385,10 +387,10 @@ static int trie_update_elem(struct bpf_map *map,
ret = -EEXIST;
goto out;
}
- trie->n_entries--;
- } else if (flags == BPF_EXIST) {
- ret = -ENOENT;
- goto out;
+ } else {
+ ret = trie_check_add_elem(trie, flags);
+ if (ret)
+ goto out;
}
new_node->child[0] = node->child[0];
@@ -400,10 +402,9 @@ static int trie_update_elem(struct bpf_map *map,
goto out;
}
- if (flags == BPF_EXIST) {
- ret = -ENOENT;
+ ret = trie_check_add_elem(trie, flags);
+ if (ret)
goto out;
- }
/* If the new node matches the prefix completely, it must be inserted
* as an ancestor. Simply insert it between @node and *@slot.
@@ -417,6 +418,7 @@ static int trie_update_elem(struct bpf_map *map,
im_node = lpm_trie_node_alloc(trie, NULL);
if (!im_node) {
+ trie->n_entries--;
ret = -ENOMEM;
goto out;
}
@@ -438,12 +440,8 @@ static int trie_update_elem(struct bpf_map *map,
rcu_assign_pointer(*slot, im_node);
out:
- if (ret) {
- if (new_node)
- trie->n_entries--;
+ if (ret)
kfree(new_node);
- }
-
spin_unlock_irqrestore(&trie->lock, irq_flags);
kfree_rcu(free_node, rcu);
