[bpf-next,04/10] bpf: Handle in-place update for full LPM trie correctly

Commit Message

Hou Tao Nov. 18, 2024, 1:08 a.m. UTC

From: Hou Tao <[e-mail]>

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.

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

Comments

Sebastian Andrzej Siewior Nov. 18, 2024, 1:13 p.m. UTC | #1

On 2024-11-18 09:08:02 [+0800], Hou Tao wrote:
> From: Hou Tao <[e-mail]>
> 
> 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.

This and the previous patch look like a fix to an existing problem.
Shouldn't both have a fixes tag?

> Signed-off-by: Hou Tao <[e-mail]>

Sebastian

Hou Tao Nov. 19, 2024, 1:05 a.m. UTC | #2

On 11/18/2024 9:13 PM, Sebastian Andrzej Siewior wrote:
> On 2024-11-18 09:08:02 [+0800], Hou Tao wrote:
>> From: Hou Tao <[e-mail]>
>>
>> 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.
> This and the previous patch look like a fix to an existing problem.
> Shouldn't both have a fixes tag?

Will add in v2. Thanks for the suggestion.
>
>> Signed-off-by: Hou Tao <[e-mail]>
> Sebastian

Toke Høiland-Jørgensen Nov. 21, 2024, 10:53 a.m. UTC | #3

Hou Tao <[e-mail]> writes:

> From: Hou Tao <[e-mail]>
>
> 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.
>
> Signed-off-by: Hou Tao <[e-mail]>
> ---
>  kernel/bpf/lpm_trie.c | 46 +++++++++++++++++++++----------------------
>  1 file changed, 23 insertions(+), 23 deletions(-)
>
> diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
> index 4300bd51ec6e..ff57e35357ae 100644
> --- a/kernel/bpf/lpm_trie.c
> +++ b/kernel/bpf/lpm_trie.c
> @@ -310,6 +310,15 @@ static struct lpm_trie_node *lpm_trie_node_alloc(const struct lpm_trie *trie,
>  	return node;
>  }
>  
> +static int trie_check_noreplace_update(const struct lpm_trie *trie, u64 flags)

I think this function name is hard to parse (took me a few tries). How
about trie_check_add_entry() instead?

> +{
> +	if (flags == BPF_EXIST)
> +		return -ENOENT;
> +	if (trie->n_entries == trie->map.max_entries)
> +		return -ENOSPC;

The calls to this function are always paired with a trie->n_entries++; -
so how about moving that into the function after the checks? You'll have
to then add a decrement if the im_node allocation fails, but I think
that is still clearer than having the n_entries++ statements scattered
around the function.

-Toke

Hou Tao Nov. 22, 2024, 2:06 a.m. UTC | #4

Hi,

On 11/21/2024 6:53 PM, Toke Høiland-Jørgensen wrote:
> Hou Tao <[e-mail]> writes:
>
>> From: Hou Tao <[e-mail]>
>>
>> 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.
>>
>> Signed-off-by: Hou Tao <[e-mail]>
>> ---
>>  kernel/bpf/lpm_trie.c | 46 +++++++++++++++++++++----------------------
>>  1 file changed, 23 insertions(+), 23 deletions(-)
>>
>> diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
>> index 4300bd51ec6e..ff57e35357ae 100644
>> --- a/kernel/bpf/lpm_trie.c
>> +++ b/kernel/bpf/lpm_trie.c
>> @@ -310,6 +310,15 @@ static struct lpm_trie_node *lpm_trie_node_alloc(const struct lpm_trie *trie,
>>  	return node;
>>  }
>>  
>> +static int trie_check_noreplace_update(const struct lpm_trie *trie, u64 flags)
> I think this function name is hard to parse (took me a few tries). How
> about trie_check_add_entry() instead?

Better. However, "entry" is not commonly used. The commonly used noun is
either "node" or "element". Will use trie_check_add_elem().
>
>> +{
>> +	if (flags == BPF_EXIST)
>> +		return -ENOENT;
>> +	if (trie->n_entries == trie->map.max_entries)
>> +		return -ENOSPC;
> The calls to this function are always paired with a trie->n_entries++; -
> so how about moving that into the function after the checks? You'll have
> to then add a decrement if the im_node allocation fails, but I think
> that is still clearer than having the n_entries++ statements scattered
> around the function.

Got it. Will update it in v2.  One motivation for adding n_entries only
necessary is to prevent trie_mem_usage from reading an inaccurate
n_entries, but consider it again I don't think it matters much.
>
> -Toke

Patch

diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
index 4300bd51ec6e..ff57e35357ae 100644
--- a/kernel/bpf/lpm_trie.c
+++ b/kernel/bpf/lpm_trie.c
@@ -310,6 +310,15 @@  static struct lpm_trie_node *lpm_trie_node_alloc(const struct lpm_trie *trie,
 	return node;
 }
 
+static int trie_check_noreplace_update(const struct lpm_trie *trie, u64 flags)
+{
+	if (flags == BPF_EXIST)
+		return -ENOENT;
+	if (trie->n_entries == trie->map.max_entries)
+		return -ENOSPC;
+	return 0;
+}
+
 /* Called from syscall or from eBPF program */
 static long trie_update_elem(struct bpf_map *map,
 			     void *_key, void *value, u64 flags)
@@ -333,20 +342,12 @@  static long 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);
@@ -375,10 +376,11 @@  static long 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_noreplace_update(trie, flags);
+		if (ret)
 			goto out;
-		}
+
+		trie->n_entries++;
 		rcu_assign_pointer(*slot, new_node);
 		goto out;
 	}
@@ -392,10 +394,11 @@  static long 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_noreplace_update(trie, flags);
+			if (ret)
+				goto out;
+			trie->n_entries++;
 		}
 
 		new_node->child[0] = node->child[0];
@@ -407,15 +410,15 @@  static long trie_update_elem(struct bpf_map *map,
 		goto out;
 	}
 
-	if (flags == BPF_EXIST) {
-		ret = -ENOENT;
+	ret = trie_check_noreplace_update(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.
 	 */
 	if (matchlen == key->prefixlen) {
+		trie->n_entries++;
 		next_bit = extract_bit(node->data, matchlen);
 		rcu_assign_pointer(new_node->child[next_bit], node);
 		rcu_assign_pointer(*slot, new_node);
@@ -428,6 +431,7 @@  static long trie_update_elem(struct bpf_map *map,
 		goto out;
 	}
 
+	trie->n_entries++;
 	im_node->prefixlen = matchlen;
 	im_node->flags |= LPM_TREE_NODE_FLAG_IM;
 	memcpy(im_node->data, node->data, trie->data_size);
@@ -445,12 +449,8 @@  static long 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);