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

On 09/19/2017 05:08 PM, Craig Gallek wrote:

On Mon, Sep 18, 2017 at 6:53 PM, Alexei Starovoitov [off-list ref] wrote:

quoted

On 9/18/17 12:30 PM, Craig Gallek wrote:

[...]

quoted

quoted

+
+               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>