From: Daniel Borkmann <daniel@iogearbox•net>
To: Craig Gallek <kraigatgoog@gmail•com>, Alexei Starovoitov <ast@fb•com>
Cc: Daniel Mack <daniel@zonque•org>,
"David S . Miller" <davem@davemloft•net>,
netdev <netdev@vger•kernel.org>
Subject: Re: [PATCH net-next 1/3] bpf: Implement map_delete_elem for BPF_MAP_TYPE_LPM_TRIE
Date: Tue, 19 Sep 2017 18:12:12 +0200 [thread overview]
Message-ID: <59C141DC.9060200@iogearbox.net> (raw)
In-Reply-To: <CAEfhGixLCqEmR=bwBqC6bT=-j22X5+rSScPb=1qWX3F-mi6H3g@mail.gmail.com>
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>
next prev parent reply other threads:[~2017-09-19 16:12 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-09-18 19:30 [PATCH net-next 0/3] Implement delete for BPF LPM trie Craig Gallek
2017-09-18 19:30 ` [PATCH net-next 1/3] bpf: Implement map_delete_elem for BPF_MAP_TYPE_LPM_TRIE Craig Gallek
2017-09-18 22:53 ` Alexei Starovoitov
2017-09-19 15:08 ` Craig Gallek
2017-09-19 16:12 ` Daniel Borkmann [this message]
2017-09-19 19:48 ` Daniel Mack
2017-09-18 19:30 ` [PATCH net-next 2/3] bpf: Add uniqueness invariant to trivial lpm test implementation Craig Gallek
2017-09-18 22:54 ` Alexei Starovoitov
2017-09-19 16:12 ` Daniel Borkmann
2017-09-18 19:30 ` [PATCH net-next 3/3] bpf: Test deletion in BPF_MAP_TYPE_LPM_TRIE Craig Gallek
2017-09-18 22:54 ` Alexei Starovoitov
2017-09-19 16:12 ` Daniel Borkmann
2017-09-19 20:55 ` [PATCH net-next 0/3] Implement delete for BPF LPM trie David Miller
2017-09-19 21:13 ` Daniel Mack
2017-09-19 21:16 ` Craig Gallek
2017-09-19 21:29 ` David Miller
2017-09-19 21:31 ` Daniel Mack
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=59C141DC.9060200@iogearbox.net \
--to=daniel@iogearbox$(echo .)net \
--cc=ast@fb$(echo .)com \
--cc=daniel@zonque$(echo .)org \
--cc=davem@davemloft$(echo .)net \
--cc=kraigatgoog@gmail$(echo .)com \
--cc=netdev@vger$(echo .)kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox