[PATCH net-next 0/3] Implement delete for BPF LPM trie

[PATCH net-next 0/3] Implement delete for BPF LPM trie

[Craig Gallek]

From: Craig Gallek <kraig@google.com>

This was previously left as a TODO.  Add the implementation and
extend the test to cover it.

Craig Gallek (3):
  bpf: Implement map_delete_elem for BPF_MAP_TYPE_LPM_TRIE
  bpf: Add uniqueness invariant to trivial lpm test implementation
  bpf: Test deletion in BPF_MAP_TYPE_LPM_TRIE

 kernel/bpf/lpm_trie.c                      |  80 +++++++++++-
 tools/testing/selftests/bpf/test_lpm_map.c | 201 ++++++++++++++++++++++++++++-
 2 files changed, 273 insertions(+), 8 deletions(-)

-- 
2.14.1.690.gbb1197296e-goog

[PATCH net-next 1/3] bpf: Implement map_delete_elem for BPF_MAP_TYPE_LPM_TRIE

[Craig Gallek]

From: Craig Gallek <kraig@google.com>

This is a simple non-recursive delete operation.  It prunes paths
of empty nodes in the tree, but it does not try to further compress
the tree as nodes are removed.

Signed-off-by: Craig Gallek <kraig@google.com>
---
 kernel/bpf/lpm_trie.c | 80 +++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 77 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
index 1b767844a76f..9d58a576b2ae 100644
--- a/kernel/bpf/lpm_trie.c
+++ b/kernel/bpf/lpm_trie.c
@@ -389,10 +389,84 @@ static int trie_update_elem(struct bpf_map *map,
 	return ret;
 }
 
-static int trie_delete_elem(struct bpf_map *map, void *key)
+/* Called from syscall or from eBPF program */
+static int trie_delete_elem(struct bpf_map *map, void *_key)
 {
-	/* TODO */
-	return -ENOSYS;
+	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
+	struct bpf_lpm_trie_key *key = _key;
+	struct lpm_trie_node __rcu **trim;
+	struct lpm_trie_node *node;
+	unsigned long irq_flags;
+	unsigned int next_bit;
+	size_t matchlen = 0;
+	int ret = 0;
+
+	if (key->prefixlen > trie->max_prefixlen)
+		return -EINVAL;
+
+	raw_spin_lock_irqsave(&trie->lock, irq_flags);
+
+	/* Walk the tree looking for an exact key/length match and keeping
+	 * track of where we could begin trimming the tree.  The trim-point
+	 * is the sub-tree along the walk consisting of only single-child
+	 * intermediate nodes and ending at a leaf node that we want to
+	 * remove.
+	 */
+	trim = &trie->root;
+	node = rcu_dereference_protected(
+		trie->root, lockdep_is_held(&trie->lock));
+	while (node) {
+		matchlen = longest_prefix_match(trie, node, key);
+
+		if (node->prefixlen != matchlen ||
+		    node->prefixlen == key->prefixlen)
+			break;
+
+		next_bit = extract_bit(key->data, node->prefixlen);
+		/* If we hit a node that has more than one child or is a valid
+		 * prefix itself, do not remove it. Reset the root of the trim
+		 * path to its descendant on our path.
+		 */
+		if (!(node->flags & LPM_TREE_NODE_FLAG_IM) ||
+		    (node->child[0] && node->child[1]))
+			trim = &node->child[next_bit];
+		node = rcu_dereference_protected(
+			node->child[next_bit], lockdep_is_held(&trie->lock));
+	}
+
+	if (!node || node->prefixlen != key->prefixlen ||
+	    (node->flags & LPM_TREE_NODE_FLAG_IM)) {
+		ret = -ENOENT;
+		goto out;
+	}
+
+	trie->n_entries--;
+
+	/* If the node we are removing is not a leaf node, simply mark it
+	 * as intermediate and we are done.
+	 */
+	if (rcu_access_pointer(node->child[0]) ||
+	    rcu_access_pointer(node->child[1])) {
+		node->flags |= LPM_TREE_NODE_FLAG_IM;
+		goto out;
+	}
+
+	/* trim should now point to the slot holding the start of a path from
+	 * zero or more intermediate nodes to our leaf node for deletion.
+	 */
+	while ((node = rcu_dereference_protected(
+			*trim, lockdep_is_held(&trie->lock)))) {
+		RCU_INIT_POINTER(*trim, NULL);
+		trim = rcu_access_pointer(node->child[0]) ?
+			&node->child[0] :
+			&node->child[1];
+		kfree_rcu(node, rcu);
+	}
+
+out:
+	raw_spin_unlock_irqrestore(&trie->lock, irq_flags);
+
+	return ret;
 }
 
 #define LPM_DATA_SIZE_MAX	256
-- 
2.14.1.690.gbb1197296e-goog

[PATCH net-next 2/3] bpf: Add uniqueness invariant to trivial lpm test implementation

[Craig Gallek]

From: Craig Gallek <kraig@google.com>

The 'trivial' lpm implementation in this test allows equivalent nodes
to be added (that is, nodes consisting of the same prefix and prefix
length).  For lookup operations, this is fine because insertion happens
at the head of the (singly linked) list and the first, best match is
returned.  In order to support deletion, the tlpm data structue must
first enforce uniqueness.  This change modifies the insertion algorithm
to search for equivalent nodes and remove them.  Note: the
BPF_MAP_TYPE_LPM_TRIE already has a uniqueness invariant that is
implemented as node replacement.

Signed-off-by: Craig Gallek <kraig@google.com>
---
 tools/testing/selftests/bpf/test_lpm_map.c | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

diff --git a/tools/testing/selftests/bpf/test_lpm_map.c b/tools/testing/selftests/bpf/test_lpm_map.c
index e97565243d59..a5ed7c4f1819 100644
--- a/tools/testing/selftests/bpf/test_lpm_map.c
+++ b/tools/testing/selftests/bpf/test_lpm_map.c
@@ -31,6 +31,10 @@ struct tlpm_node {
 	uint8_t key[];
 };
 
+static struct tlpm_node *tlpm_match(struct tlpm_node *list,
+				    const uint8_t *key,
+				    size_t n_bits);
+
 static struct tlpm_node *tlpm_add(struct tlpm_node *list,
 				  const uint8_t *key,
 				  size_t n_bits)
@@ -38,9 +42,17 @@ static struct tlpm_node *tlpm_add(struct tlpm_node *list,
 	struct tlpm_node *node;
 	size_t n;
 
+	n = (n_bits + 7) / 8;
+
+	/* 'overwrite' an equivalent entry if one already exists */
+	node = tlpm_match(list, key, n_bits);
+	if (node && node->n_bits == n_bits) {
+		memcpy(node->key, key, n);
+		return list;
+	}
+
 	/* add new entry with @key/@n_bits to @list and return new head */
 
-	n = (n_bits + 7) / 8;
 	node = malloc(sizeof(*node) + n);
 	assert(node);
 
-- 
2.14.1.690.gbb1197296e-goog

[PATCH net-next 3/3] bpf: Test deletion in BPF_MAP_TYPE_LPM_TRIE

[Craig Gallek]

From: Craig Gallek <kraig@google.com>

Extend the 'random' operation tests to include a delete operation
(delete half of the nodes from both lpm implementions and ensure
that lookups are still equivalent).

Also, add a simple IPv4 test which verifies lookup behavior as nodes
are deleted from the tree.

Signed-off-by: Craig Gallek <kraig@google.com>
---
 tools/testing/selftests/bpf/test_lpm_map.c | 187 ++++++++++++++++++++++++++++-
 1 file changed, 183 insertions(+), 4 deletions(-)

diff --git a/tools/testing/selftests/bpf/test_lpm_map.c b/tools/testing/selftests/bpf/test_lpm_map.c
index a5ed7c4f1819..6fedb9fec36b 100644
--- a/tools/testing/selftests/bpf/test_lpm_map.c
+++ b/tools/testing/selftests/bpf/test_lpm_map.c
@@ -104,6 +104,34 @@ static struct tlpm_node *tlpm_match(struct tlpm_node *list,
 	return best;
 }
 
+static struct tlpm_node *tlpm_delete(struct tlpm_node *list,
+				     const uint8_t *key,
+				     size_t n_bits)
+{
+	struct tlpm_node *best = tlpm_match(list, key, n_bits);
+	struct tlpm_node *node;
+
+	if (!best || best->n_bits != n_bits)
+		return list;
+
+	if (best == list) {
+		node = best->next;
+		free(best);
+		return node;
+	}
+
+	for (node = list; node; node = node->next) {
+		if (node->next == best) {
+			node->next = best->next;
+			free(best);
+			return list;
+		}
+	}
+	/* should never get here */
+	assert(0);
+	return list;
+}
+
 static void test_lpm_basic(void)
 {
 	struct tlpm_node *list = NULL, *t1, *t2;
@@ -126,6 +154,13 @@ static void test_lpm_basic(void)
 	assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 15));
 	assert(!tlpm_match(list, (uint8_t[]){ 0x7f, 0xff }, 16));
 
+	list = tlpm_delete(list, (uint8_t[]){ 0xff, 0xff }, 16);
+	assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));
+	assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));
+
+	list = tlpm_delete(list, (uint8_t[]){ 0xff }, 8);
+	assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8));
+
 	tlpm_clear(list);
 }
 
@@ -170,7 +205,7 @@ static void test_lpm_order(void)
 
 static void test_lpm_map(int keysize)
 {
-	size_t i, j, n_matches, n_nodes, n_lookups;
+	size_t i, j, n_matches, n_matches_after_delete, n_nodes, n_lookups;
 	struct tlpm_node *t, *list = NULL;
 	struct bpf_lpm_trie_key *key;
 	uint8_t *data, *value;
@@ -182,6 +217,7 @@ static void test_lpm_map(int keysize)
 	 */
 
 	n_matches = 0;
+	n_matches_after_delete = 0;
 	n_nodes = 1 << 8;
 	n_lookups = 1 << 16;
 
@@ -235,15 +271,54 @@ static void test_lpm_map(int keysize)
 		}
 	}
 
+	/* Remove the first half of the elements in the tlpm and the
+	 * corresponding nodes from the bpf-lpm.  Then run the same
+	 * large number of random lookups in both and make sure they match.
+	 * Note: we need to count the number of nodes actually inserted
+	 * since there may have been duplicates.
+	 */
+	for (i = 0, t = list; t; i++, t = t->next)
+		;
+	for (j = 0; j < i / 2; ++j) {
+		key->prefixlen = list->n_bits;
+		memcpy(key->data, list->key, keysize);
+		r = bpf_map_delete_elem(map, key);
+		assert(!r);
+		list = tlpm_delete(list, list->key, list->n_bits);
+		assert(list);
+	}
+	for (i = 0; i < n_lookups; ++i) {
+		for (j = 0; j < keysize; ++j)
+			data[j] = rand() & 0xff;
+
+		t = tlpm_match(list, data, 8 * keysize);
+
+		key->prefixlen = 8 * keysize;
+		memcpy(key->data, data, keysize);
+		r = bpf_map_lookup_elem(map, key, value);
+		assert(!r || errno == ENOENT);
+		assert(!t == !!r);
+
+		if (t) {
+			++n_matches_after_delete;
+			assert(t->n_bits == value[keysize]);
+			for (j = 0; j < t->n_bits; ++j)
+				assert((t->key[j / 8] & (1 << (7 - j % 8))) ==
+				       (value[j / 8] & (1 << (7 - j % 8))));
+		}
+	}
+
 	close(map);
 	tlpm_clear(list);
 
 	/* With 255 random nodes in the map, we are pretty likely to match
 	 * something on every lookup. For statistics, use this:
 	 *
-	 *     printf("  nodes: %zu\n"
-	 *            "lookups: %zu\n"
-	 *            "matches: %zu\n", n_nodes, n_lookups, n_matches);
+	 *     printf("          nodes: %zu\n"
+	 *            "        lookups: %zu\n"
+	 *            "        matches: %zu\n"
+	 *            "matches(delete): %zu\n",
+	 *            n_nodes, n_lookups, n_matches, n_matches_after_delete);
 	 */
 }
 
@@ -343,6 +418,108 @@ static void test_lpm_ipaddr(void)
 	close(map_fd_ipv6);
 }
 
+static void test_lpm_delete(void)
+{
+	struct bpf_lpm_trie_key *key;
+	size_t key_size;
+	int map_fd;
+	__u64 value;
+
+	key_size = sizeof(*key) + sizeof(__u32);
+	key = alloca(key_size);
+
+	map_fd = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE,
+				key_size, sizeof(value),
+				100, BPF_F_NO_PREALLOC);
+	assert(map_fd >= 0);
+
+	/* Add nodes:
+	 * 192.168.0.0/16   (1)
+	 * 192.168.0.0/24   (2)
+	 * 192.168.128.0/24 (3)
+	 * 192.168.1.0/24   (4)
+	 *
+	 *         (1)
+	 *        /   \
+         *     (IM)    (3)
+	 *    /   \
+         *   (2)  (4)
+	 */
+	value = 1;
+	key->prefixlen = 16;
+	inet_pton(AF_INET, "192.168.0.0", key->data);
+	assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
+
+	value = 2;
+	key->prefixlen = 24;
+	inet_pton(AF_INET, "192.168.0.0", key->data);
+	assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
+
+	value = 3;
+	key->prefixlen = 24;
+	inet_pton(AF_INET, "192.168.128.0", key->data);
+	assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
+
+	value = 4;
+	key->prefixlen = 24;
+	inet_pton(AF_INET, "192.168.1.0", key->data);
+	assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);
+
+	/* remove non-existent node */
+	key->prefixlen = 32;
+	inet_pton(AF_INET, "10.0.0.1", key->data);
+	assert(bpf_map_lookup_elem(map_fd, key, &value) == -1 &&
+		errno == ENOENT);
+
+	/* assert initial lookup */
+	key->prefixlen = 32;
+	inet_pton(AF_INET, "192.168.0.1", key->data);
+	assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
+	assert(value == 2);
+
+	/* remove leaf node */
+	key->prefixlen = 24;
+	inet_pton(AF_INET, "192.168.0.0", key->data);
+	assert(bpf_map_delete_elem(map_fd, key) == 0);
+
+	key->prefixlen = 32;
+	inet_pton(AF_INET, "192.168.0.1", key->data);
+	assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
+	assert(value == 1);
+
+	/* remove leaf (and intermediary) node */
+	key->prefixlen = 24;
+	inet_pton(AF_INET, "192.168.1.0", key->data);
+	assert(bpf_map_delete_elem(map_fd, key) == 0);
+
+	key->prefixlen = 32;
+	inet_pton(AF_INET, "192.168.1.1", key->data);
+	assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
+	assert(value == 1);
+
+	/* remove root node */
+	key->prefixlen = 16;
+	inet_pton(AF_INET, "192.168.0.0", key->data);
+	assert(bpf_map_delete_elem(map_fd, key) == 0);
+
+	key->prefixlen = 32;
+	inet_pton(AF_INET, "192.168.128.1", key->data);
+	assert(bpf_map_lookup_elem(map_fd, key, &value) == 0);
+	assert(value == 3);
+
+	/* remove last node */
+	key->prefixlen = 24;
+	inet_pton(AF_INET, "192.168.128.0", key->data);
+	assert(bpf_map_delete_elem(map_fd, key) == 0);
+
+	key->prefixlen = 32;
+	inet_pton(AF_INET, "192.168.128.1", key->data);
+	assert(bpf_map_lookup_elem(map_fd, key, &value) == -1 &&
+		errno == ENOENT);
+
+	close(map_fd);
+}
+
 int main(void)
 {
 	struct rlimit limit  = { RLIM_INFINITY, RLIM_INFINITY };
@@ -365,6 +542,8 @@ int main(void)
 
 	test_lpm_ipaddr();
 
+	test_lpm_delete();
+
 	printf("test_lpm: OK\n");
 	return 0;
 }
-- 
2.14.1.690.gbb1197296e-goog

Re: [PATCH net-next 1/3] bpf: Implement map_delete_elem for BPF_MAP_TYPE_LPM_TRIE

[Alexei Starovoitov]

On 9/18/17 12:30 PM, Craig Gallek wrote:
> From: Craig Gallek <kraig@google.com>
>
> This is a simple non-recursive delete operation.  It prunes paths
> of empty nodes in the tree, but it does not try to further compress
> the tree as nodes are removed.
>
> Signed-off-by: Craig Gallek <kraig@google.com>
> ---
>  kernel/bpf/lpm_trie.c | 80 +++++++++++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 77 insertions(+), 3 deletions(-)
>
> diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
> index 1b767844a76f..9d58a576b2ae 100644
> --- a/kernel/bpf/lpm_trie.c
> +++ b/kernel/bpf/lpm_trie.c
> @@ -389,10 +389,84 @@ static int trie_update_elem(struct bpf_map *map,
>  	return ret;
>  }
>
> -static int trie_delete_elem(struct bpf_map *map, void *key)
> +/* Called from syscall or from eBPF program */
> +static int trie_delete_elem(struct bpf_map *map, void *_key)
>  {
> -	/* TODO */
> -	return -ENOSYS;
> +	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
> +	struct bpf_lpm_trie_key *key = _key;
> +	struct lpm_trie_node __rcu **trim;
> +	struct lpm_trie_node *node;
> +	unsigned long irq_flags;
> +	unsigned int next_bit;
> +	size_t matchlen = 0;
> +	int ret = 0;
> +
> +	if (key->prefixlen > trie->max_prefixlen)
> +		return -EINVAL;
> +
> +	raw_spin_lock_irqsave(&trie->lock, irq_flags);
> +
> +	/* Walk the tree looking for an exact key/length match and keeping
> +	 * track of where we could begin trimming the tree.  The trim-point
> +	 * is the sub-tree along the walk consisting of only single-child
> +	 * intermediate nodes and ending at a leaf node that we want to
> +	 * remove.
> +	 */
> +	trim = &trie->root;
> +	node = rcu_dereference_protected(
> +		trie->root, lockdep_is_held(&trie->lock));
> +	while (node) {
> +		matchlen = longest_prefix_match(trie, node, key);
> +
> +		if (node->prefixlen != matchlen ||
> +		    node->prefixlen == key->prefixlen)
> +			break;

curious why there is no need to do
'node->prefixlen == trie->max_prefixlen' in the above
like update/lookup do?

> +
> +		next_bit = extract_bit(key->data, node->prefixlen);
> +		/* If we hit a node that has more than one child or is a valid
> +		 * prefix itself, do not remove it. Reset the root of the trim
> +		 * path to its descendant on our path.
> +		 */
> +		if (!(node->flags & LPM_TREE_NODE_FLAG_IM) ||
> +		    (node->child[0] && node->child[1]))
> +			trim = &node->child[next_bit];
> +		node = rcu_dereference_protected(
> +			node->child[next_bit], lockdep_is_held(&trie->lock));
> +	}
> +
> +	if (!node || node->prefixlen != key->prefixlen ||
> +	    (node->flags & LPM_TREE_NODE_FLAG_IM)) {
> +		ret = -ENOENT;
> +		goto out;
> +	}
> +
> +	trie->n_entries--;
> +
> +	/* If the node we are removing is not a leaf node, simply mark it
> +	 * as intermediate and we are done.
> +	 */
> +	if (rcu_access_pointer(node->child[0]) ||
> +	    rcu_access_pointer(node->child[1])) {
> +		node->flags |= LPM_TREE_NODE_FLAG_IM;
> +		goto out;
> +	}
> +
> +	/* trim should now point to the slot holding the start of a path from
> +	 * zero or more intermediate nodes to our leaf node for deletion.
> +	 */
> +	while ((node = rcu_dereference_protected(
> +			*trim, lockdep_is_held(&trie->lock)))) {
> +		RCU_INIT_POINTER(*trim, NULL);
> +		trim = rcu_access_pointer(node->child[0]) ?
> +			&node->child[0] :
> +			&node->child[1];
> +		kfree_rcu(node, rcu);

can it be that some of the nodes this loop walks have
both child[0] and [1] ?

Re: [PATCH net-next 2/3] bpf: Add uniqueness invariant to trivial lpm test implementation

[Alexei Starovoitov]

On 9/18/17 12:30 PM, Craig Gallek wrote:
> From: Craig Gallek <kraig@google.com>
>
> The 'trivial' lpm implementation in this test allows equivalent nodes
> to be added (that is, nodes consisting of the same prefix and prefix
> length).  For lookup operations, this is fine because insertion happens
> at the head of the (singly linked) list and the first, best match is
> returned.  In order to support deletion, the tlpm data structue must
> first enforce uniqueness.  This change modifies the insertion algorithm
> to search for equivalent nodes and remove them.  Note: the
> BPF_MAP_TYPE_LPM_TRIE already has a uniqueness invariant that is
> implemented as node replacement.
>
> Signed-off-by: Craig Gallek <kraig@google.com>

Acked-by: Alexei Starovoitov <ast@kernel.org>

Re: [PATCH net-next 3/3] bpf: Test deletion in BPF_MAP_TYPE_LPM_TRIE

[Alexei Starovoitov]

On 9/18/17 12:30 PM, Craig Gallek wrote:
> From: Craig Gallek <kraig@google.com>
>
> Extend the 'random' operation tests to include a delete operation
> (delete half of the nodes from both lpm implementions and ensure
> that lookups are still equivalent).
>
> Also, add a simple IPv4 test which verifies lookup behavior as nodes
> are deleted from the tree.
>
> Signed-off-by: Craig Gallek <kraig@google.com>

Thanks for the tests!
Acked-by: Alexei Starovoitov <ast@kernel.org>

Re: [PATCH net-next 1/3] bpf: Implement map_delete_elem for BPF_MAP_TYPE_LPM_TRIE

[Craig Gallek]

On Mon, Sep 18, 2017 at 6:53 PM, Alexei Starovoitov <ast@fb.com> wrote:
Thanks for the review!  Please correct me if I'm wrong...

> On 9/18/17 12:30 PM, Craig Gallek wrote:
>>
>> From: Craig Gallek <kraig@google.com>
>>
>> This is a simple non-recursive delete operation.  It prunes paths
>> of empty nodes in the tree, but it does not try to further compress
>> the tree as nodes are removed.
>>
>> Signed-off-by: Craig Gallek <kraig@google.com>
>> ---
>>  kernel/bpf/lpm_trie.c | 80
>> +++++++++++++++++++++++++++++++++++++++++++++++++--
>>  1 file changed, 77 insertions(+), 3 deletions(-)
>>
>> diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
>> index 1b767844a76f..9d58a576b2ae 100644
>> --- a/kernel/bpf/lpm_trie.c
>> +++ b/kernel/bpf/lpm_trie.c
>> @@ -389,10 +389,84 @@ static int trie_update_elem(struct bpf_map *map,
>>         return ret;
>>  }
>>
>> -static int trie_delete_elem(struct bpf_map *map, void *key)
>> +/* Called from syscall or from eBPF program */
>> +static int trie_delete_elem(struct bpf_map *map, void *_key)
>>  {
>> -       /* TODO */
>> -       return -ENOSYS;
>> +       struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
>> +       struct bpf_lpm_trie_key *key = _key;
>> +       struct lpm_trie_node __rcu **trim;
>> +       struct lpm_trie_node *node;
>> +       unsigned long irq_flags;
>> +       unsigned int next_bit;
>> +       size_t matchlen = 0;
>> +       int ret = 0;
>> +
>> +       if (key->prefixlen > trie->max_prefixlen)
>> +               return -EINVAL;
>> +
>> +       raw_spin_lock_irqsave(&trie->lock, irq_flags);
>> +
>> +       /* Walk the tree looking for an exact key/length match and keeping
>> +        * track of where we could begin trimming the tree.  The
>> trim-point
>> +        * is the sub-tree along the walk consisting of only single-child
>> +        * intermediate nodes and ending at a leaf node that we want to
>> +        * remove.
>> +        */
>> +       trim = &trie->root;
>> +       node = rcu_dereference_protected(
>> +               trie->root, lockdep_is_held(&trie->lock));
>> +       while (node) {
>> +               matchlen = longest_prefix_match(trie, node, key);
>> +
>> +               if (node->prefixlen != matchlen ||
>> +                   node->prefixlen == key->prefixlen)
>> +                       break;
>
>
> curious why there is no need to do
> 'node->prefixlen == trie->max_prefixlen' in the above
> like update/lookup do?
I don't believe the node->prefixlen == trie->max_prefixlen check in
trie_update_elem is necessary. In order to get to this third clause,
it implies that the first two clauses evaluated false.  Which happens
when we find an exact prefix match for the current node, but the
to-be-inserted key prefix is different.  If the node we are comparing
against had a prefix of max_prefixlen, it would not be possible to
have both a full prefix match but different prefix lengths.  This
assumes that there are no nodes in the tree with > max_prefixlen
prefixes, but that is handled earlier in the update function.

There's a similar (I believe) unnecessary max_prefixlen check in
trie_lookup_elem.  The function should behave the same way without
that check, but at least in this case it's used as an early-out and
saves a few lines of execution.

>
>> +
>> +               next_bit = extract_bit(key->data, node->prefixlen);
>> +               /* If we hit a node that has more than one child or is a
>> valid
>> +                * prefix itself, do not remove it. Reset the root of the
>> trim
>> +                * path to its descendant on our path.
>> +                */
>> +               if (!(node->flags & LPM_TREE_NODE_FLAG_IM) ||
>> +                   (node->child[0] && node->child[1]))
>> +                       trim = &node->child[next_bit];
>> +               node = rcu_dereference_protected(
>> +                       node->child[next_bit],
>> lockdep_is_held(&trie->lock));
>> +       }
>> +
>> +       if (!node || node->prefixlen != key->prefixlen ||
>> +           (node->flags & LPM_TREE_NODE_FLAG_IM)) {
>> +               ret = -ENOENT;
>> +               goto out;
>> +       }
>> +
>> +       trie->n_entries--;
>> +
>> +       /* If the node we are removing is not a leaf node, simply mark it
>> +        * as intermediate and we are done.
>> +        */
>> +       if (rcu_access_pointer(node->child[0]) ||
>> +           rcu_access_pointer(node->child[1])) {
>> +               node->flags |= LPM_TREE_NODE_FLAG_IM;
>> +               goto out;
>> +       }
>> +
>> +       /* trim should now point to the slot holding the start of a path
>> from
>> +        * zero or more intermediate nodes to our leaf node for deletion.
>> +        */
>> +       while ((node = rcu_dereference_protected(
>> +                       *trim, lockdep_is_held(&trie->lock)))) {
>> +               RCU_INIT_POINTER(*trim, NULL);
>> +               trim = rcu_access_pointer(node->child[0]) ?
>> +                       &node->child[0] :
>> +                       &node->child[1];
>> +               kfree_rcu(node, rcu);
>
>
> can it be that some of the nodes this loop walks have
> both child[0] and [1] ?
No, the loop above will push trim down the walk every time it
encounters a node with two children.  The only other trim assignment
is the initial trim = &trie->root.  But the only time we would skip
the assignment in the loop is if the node being removed is the root.
If the root had multiple children and is being removed, it would be
handled by the case that turns the node into an intermediate node
rather than walking the trim path freeing things.

Re: [PATCH net-next 1/3] bpf: Implement map_delete_elem for BPF_MAP_TYPE_LPM_TRIE

[Daniel Borkmann]

On 09/19/2017 05:08 PM, Craig Gallek wrote:
> On Mon, Sep 18, 2017 at 6:53 PM, Alexei Starovoitov <ast@fb.com> wrote:
>> On 9/18/17 12:30 PM, Craig Gallek wrote:
[...]
>>> +
>>> +               next_bit = extract_bit(key->data, node->prefixlen);
>>> +               /* If we hit a node that has more than one child or is a
>>> valid
>>> +                * prefix itself, do not remove it. Reset the root of the
>>> trim
>>> +                * path to its descendant on our path.
>>> +                */
>>> +               if (!(node->flags & LPM_TREE_NODE_FLAG_IM) ||
>>> +                   (node->child[0] && node->child[1]))
>>> +                       trim = &node->child[next_bit];
>>> +               node = rcu_dereference_protected(
>>> +                       node->child[next_bit],
>>> lockdep_is_held(&trie->lock));
>>> +       }
>>> +
>>> +       if (!node || node->prefixlen != key->prefixlen ||
>>> +           (node->flags & LPM_TREE_NODE_FLAG_IM)) {
>>> +               ret = -ENOENT;
>>> +               goto out;
>>> +       }
>>> +
>>> +       trie->n_entries--;
>>> +
>>> +       /* If the node we are removing is not a leaf node, simply mark it
>>> +        * as intermediate and we are done.
>>> +        */
>>> +       if (rcu_access_pointer(node->child[0]) ||
>>> +           rcu_access_pointer(node->child[1])) {
>>> +               node->flags |= LPM_TREE_NODE_FLAG_IM;
>>> +               goto out;
>>> +       }
>>> +
>>> +       /* trim should now point to the slot holding the start of a path
>>> from
>>> +        * zero or more intermediate nodes to our leaf node for deletion.
>>> +        */
>>> +       while ((node = rcu_dereference_protected(
>>> +                       *trim, lockdep_is_held(&trie->lock)))) {
>>> +               RCU_INIT_POINTER(*trim, NULL);
>>> +               trim = rcu_access_pointer(node->child[0]) ?
>>> +                       &node->child[0] :
>>> +                       &node->child[1];
>>> +               kfree_rcu(node, rcu);
>>
>> can it be that some of the nodes this loop walks have
>> both child[0] and [1] ?
> No, the loop above will push trim down the walk every time it
> encounters a node with two children.  The only other trim assignment
> is the initial trim = &trie->root.  But the only time we would skip
> the assignment in the loop is if the node being removed is the root.
> If the root had multiple children and is being removed, it would be
> handled by the case that turns the node into an intermediate node
> rather than walking the trim path freeing things.

Looks good to me. We should probably still merge nodes once we turn
a real node into an im which just has a single child attached to it;
parent can be im or real node. Thus, we don't need to traverse this
extra one on lookup.

Acked-by: Daniel Borkmann <daniel@iogearbox.net>

Re: [PATCH net-next 2/3] bpf: Add uniqueness invariant to trivial lpm test implementation

[Daniel Borkmann]

On 09/18/2017 09:30 PM, Craig Gallek wrote:
> From: Craig Gallek <kraig@google.com>
>
> The 'trivial' lpm implementation in this test allows equivalent nodes
> to be added (that is, nodes consisting of the same prefix and prefix
> length).  For lookup operations, this is fine because insertion happens
> at the head of the (singly linked) list and the first, best match is
> returned.  In order to support deletion, the tlpm data structue must
> first enforce uniqueness.  This change modifies the insertion algorithm
> to search for equivalent nodes and remove them.  Note: the
> BPF_MAP_TYPE_LPM_TRIE already has a uniqueness invariant that is
> implemented as node replacement.
>
> Signed-off-by: Craig Gallek <kraig@google.com>

Acked-by: Daniel Borkmann <daniel@iogearbox.net>

Re: [PATCH net-next 3/3] bpf: Test deletion in BPF_MAP_TYPE_LPM_TRIE

[Daniel Borkmann]

On 09/18/2017 09:30 PM, Craig Gallek wrote:
> From: Craig Gallek <kraig@google.com>
>
> Extend the 'random' operation tests to include a delete operation
> (delete half of the nodes from both lpm implementions and ensure
> that lookups are still equivalent).
>
> Also, add a simple IPv4 test which verifies lookup behavior as nodes
> are deleted from the tree.
>
> Signed-off-by: Craig Gallek <kraig@google.com>

Acked-by: Daniel Borkmann <daniel@iogearbox.net>

Re: [PATCH net-next 1/3] bpf: Implement map_delete_elem for BPF_MAP_TYPE_LPM_TRIE

[Daniel Mack]

Hi,

Thanks for working on this, Craig!

On 09/19/2017 06:12 PM, Daniel Borkmann wrote:
> On 09/19/2017 05:08 PM, Craig Gallek wrote:
>> On Mon, Sep 18, 2017 at 6:53 PM, Alexei Starovoitov <ast@fb.com> wrote:
>>> On 9/18/17 12:30 PM, Craig Gallek wrote:
> [...]
>>>> +
>>>> +               next_bit = extract_bit(key->data, node->prefixlen);
>>>> +               /* If we hit a node that has more than one child or is a
>>>> valid
>>>> +                * prefix itself, do not remove it. Reset the root of the
>>>> trim
>>>> +                * path to its descendant on our path.
>>>> +                */
>>>> +               if (!(node->flags & LPM_TREE_NODE_FLAG_IM) ||
>>>> +                   (node->child[0] && node->child[1]))
>>>> +                       trim = &node->child[next_bit];
>>>> +               node = rcu_dereference_protected(
>>>> +                       node->child[next_bit],
>>>> lockdep_is_held(&trie->lock));
>>>> +       }
>>>> +
>>>> +       if (!node || node->prefixlen != key->prefixlen ||
>>>> +           (node->flags & LPM_TREE_NODE_FLAG_IM)) {
>>>> +               ret = -ENOENT;
>>>> +               goto out;
>>>> +       }
>>>> +
>>>> +       trie->n_entries--;
>>>> +
>>>> +       /* If the node we are removing is not a leaf node, simply mark it
>>>> +        * as intermediate and we are done.
>>>> +        */
>>>> +       if (rcu_access_pointer(node->child[0]) ||
>>>> +           rcu_access_pointer(node->child[1])) {
>>>> +               node->flags |= LPM_TREE_NODE_FLAG_IM;
>>>> +               goto out;
>>>> +       }
>>>> +
>>>> +       /* trim should now point to the slot holding the start of a path
>>>> from
>>>> +        * zero or more intermediate nodes to our leaf node for deletion.
>>>> +        */
>>>> +       while ((node = rcu_dereference_protected(
>>>> +                       *trim, lockdep_is_held(&trie->lock)))) {
>>>> +               RCU_INIT_POINTER(*trim, NULL);
>>>> +               trim = rcu_access_pointer(node->child[0]) ?
>>>> +                       &node->child[0] :
>>>> +                       &node->child[1];
>>>> +               kfree_rcu(node, rcu);
>>>
>>> can it be that some of the nodes this loop walks have
>>> both child[0] and [1] ?
>> No, the loop above will push trim down the walk every time it
>> encounters a node with two children.  The only other trim assignment
>> is the initial trim = &trie->root.  But the only time we would skip
>> the assignment in the loop is if the node being removed is the root.
>> If the root had multiple children and is being removed, it would be
>> handled by the case that turns the node into an intermediate node
>> rather than walking the trim path freeing things.
> 
> Looks good to me. We should probably still merge nodes once we turn
> a real node into an im which just has a single child attached to it;
> parent can be im or real node. Thus, we don't need to traverse this
> extra one on lookup.

Right, but only if the the parent of the node allows us to do that,
because the 'next bit' in the lookup key has to match the slot index.

To illustrate, consider the following trie with no IM nodes:

                      +----------------+
                      |       (1)  (R) |
                      | 192.168.0.0/16 |
                      |    value: 1    |
                      |   [0]    [1]   |
                      +----------------+
                           |      |
            +----------------+  +------------------+
            |       (2)      |  |        (3)       |
            | 192.168.0.0/23 |  | 192.168.128.0/24 |
            |    value: 2    |  |     value: 3     |
            |   [0]    [1]   |  |    [0]    [1]    |
            +----------------+  +------------------+
                        |
                      +----------------+
                      |       (4)      |
                      | 192.168.1.0/24 |
                      |     value: 4   |
                      |   [0]    [1]   |
                      +----------------+

If you now try to delete (2), the node has to stay around because (3)
and (4) share the same value in bit 17 (1). If, however, (4) had a
prefix of 192.168.0.0/24, then (2) should be removed completely, and (4)
should be directly attached to (1) as child[0].

With this implementation, a situation in which multiple IM nodes appear
in a chain cannot emerge. And that again should make your trimming
algorithm simpler, because you only need to find an exact match, and
then handle three distinct cases:

a) the node as 0 children: simply remove it and nullify the pointer in
the parent

b) the node has 1 child: apply logic I described above

c) the node has 2 children: turn the node into an IM


Makes sense?


Thanks,
Daniel

Re: [PATCH net-next 0/3] Implement delete for BPF LPM trie

[David Miller]

From: Craig Gallek <kraigatgoog@gmail.com>
Date: Mon, 18 Sep 2017 15:30:54 -0400

> This was previously left as a TODO.  Add the implementation and
> extend the test to cover it.

Series applied, thanks.

Re: [PATCH net-next 0/3] Implement delete for BPF LPM trie

[Daniel Mack]

On 09/19/2017 10:55 PM, David Miller wrote:
> From: Craig Gallek <kraigatgoog@gmail.com>
> Date: Mon, 18 Sep 2017 15:30:54 -0400
> 
>> This was previously left as a TODO.  Add the implementation and
>> extend the test to cover it.
> 
> Series applied, thanks.
> 

Hmm, I think these patches need some more discussion regarding the IM
nodes handling, see the reply I sent an hour ago. Could you wait for
that before pushing your tree?


Thanks,
Daniel

Re: [PATCH net-next 0/3] Implement delete for BPF LPM trie

[Craig Gallek]

On Tue, Sep 19, 2017 at 5:13 PM, Daniel Mack <daniel@zonque.org> wrote:
> On 09/19/2017 10:55 PM, David Miller wrote:
>> From: Craig Gallek <kraigatgoog@gmail.com>
>> Date: Mon, 18 Sep 2017 15:30:54 -0400
>>
>>> This was previously left as a TODO.  Add the implementation and
>>> extend the test to cover it.
>>
>> Series applied, thanks.
>>
>
> Hmm, I think these patches need some more discussion regarding the IM
> nodes handling, see the reply I sent an hour ago. Could you wait for
> that before pushing your tree?

I can follow up with a patch to implement your suggestion.  It's
really just an efficiency improvement, though, so I think it's ok to
handle independently. (Sorry, I haven't had a chance to play with the
implementation details yet).

Craig

Re: [PATCH net-next 0/3] Implement delete for BPF LPM trie

[David Miller]

From: Craig Gallek <kraigatgoog@gmail.com>
Date: Tue, 19 Sep 2017 17:16:13 -0400

> On Tue, Sep 19, 2017 at 5:13 PM, Daniel Mack <daniel@zonque.org> wrote:
>> On 09/19/2017 10:55 PM, David Miller wrote:
>>> From: Craig Gallek <kraigatgoog@gmail.com>
>>> Date: Mon, 18 Sep 2017 15:30:54 -0400
>>>
>>>> This was previously left as a TODO.  Add the implementation and
>>>> extend the test to cover it.
>>>
>>> Series applied, thanks.
>>>
>>
>> Hmm, I think these patches need some more discussion regarding the IM
>> nodes handling, see the reply I sent an hour ago. Could you wait for
>> that before pushing your tree?
> 
> I can follow up with a patch to implement your suggestion.  It's
> really just an efficiency improvement, though, so I think it's ok to
> handle independently. (Sorry, I haven't had a chance to play with the
> implementation details yet).

Sorry, I thought the core implementation had been agreed upon and the
series was OK.  All that was asked for were simplifications and/or
optimization which could be done via follow-up patches.

It's already pushed out to my tree, so I would need to do a real
revert.

I hope that won't be necessary.

Re: [PATCH net-next 0/3] Implement delete for BPF LPM trie

[Daniel Mack]

On 09/19/2017 11:29 PM, David Miller wrote:
> From: Craig Gallek <kraigatgoog@gmail.com>
> Date: Tue, 19 Sep 2017 17:16:13 -0400
> 
>> On Tue, Sep 19, 2017 at 5:13 PM, Daniel Mack <daniel@zonque.org> wrote:
>>> On 09/19/2017 10:55 PM, David Miller wrote:
>>>> From: Craig Gallek <kraigatgoog@gmail.com>
>>>> Date: Mon, 18 Sep 2017 15:30:54 -0400
>>>>
>>>>> This was previously left as a TODO.  Add the implementation and
>>>>> extend the test to cover it.
>>>>
>>>> Series applied, thanks.
>>>>
>>>
>>> Hmm, I think these patches need some more discussion regarding the IM
>>> nodes handling, see the reply I sent an hour ago. Could you wait for
>>> that before pushing your tree?
>>
>> I can follow up with a patch to implement your suggestion.  It's
>> really just an efficiency improvement, though, so I think it's ok to
>> handle independently. (Sorry, I haven't had a chance to play with the
>> implementation details yet).
> 
> Sorry, I thought the core implementation had been agreed upon and the
> series was OK.  All that was asked for were simplifications and/or
> optimization which could be done via follow-up patches.
> 
> It's already pushed out to my tree, so I would need to do a real
> revert.
> 
> I hope that won't be necessary.
> 

Nah, it's okay I guess. I trust Craig to send follow-up patches. After
all, efficiency is what this whole exercise is all about, so I think it
should be done correctly :)



Thanks,
Daniel