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

From: Alexander Duyck <[email-masked]>
Date: Fri, 12 Dec 2014 07:55:02 -0800

On 12/11/2014 06:32 PM, David Miller wrote:
> From: Alexander Duyck <[email-masked]>
> 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 <[email-masked]>
> 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.

- Alex