netdev - Re: [net PATCH] fib_trie: Fix trie balancing issue if new node pushes down existing node

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Fri, 12 Dec 2014 11:00:51 -0500 (EST)
From:	David Miller <davem@...emloft.net>
To:	alexander.duyck@...il.com
Cc:	alexander.h.duyck@...hat.com, netdev@...r.kernel.org
Subject: Re: [net PATCH] fib_trie: Fix trie balancing issue if new node
 pushes down existing node

From: Alexander Duyck <alexander.duyck@...il.com>
Date: Fri, 12 Dec 2014 07:55:02 -0800

> On 12/11/2014 06:32 PM, David Miller wrote:
>> From: Alexander Duyck <alexander.h.duyck@...hat.com>
>> Date: Wed, 10 Dec 2014 21:49:22 -0800
>>
>>> This patch addresses an issue with the level compression of the fib_trie.
>>> Specifically in the case of adding a new leaf that triggers a new node to
>>> be added that takes the place of the old node.  The result is a trie where
>>> the 1 child tnode is on one side and one leaf is on the other which gives
>>> you a very deep trie.  Below is the script I used to generate a trie on
>>> dummy0 with a 10.X.X.X family of addresses.
>>  ...
>>> What this fix does is start the rebalance at the newly created tnode
>>> instead of at the parent tnode.  This way if there is a gap between the
>>> parent and the new node it doesn't prevent the new tnode from being
>>> coalesced with any pre-existing nodes that may have been pushed into one
>>> of the new nodes child branches.
>>>
>>> Signed-off-by: Alexander Duyck <alexander.h.duyck@...hat.com>
>> One has to be mindful with this code that what it's doing now might
>> be intentional.  For example, it might be doing things this way
>> on purpose in order to minimize rebalancing during route flaps.
>>
>> Barring anything like that, I think your change is fine.
> 
> I'm fairly certain that this isn't intentional.  If we replace a NULL
> pointer in an existing tnode then we rebalance starting at that tnode,
> it is only when there is no room in the trie and we have to add a new
> tnode that the issue occurs where we rebalance at the parent and not the
> tnode that the leaf was added to.

Ok, thanks for taking the time to explain this, I'm now convinced :)

Applied, thanks again.
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html