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:	Thu, 11 Dec 2014 21:32:16 -0500 (EST)
From:	David Miller <davem@...emloft.net>
To:	alexander.h.duyck@...hat.com
Cc:	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.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.
--
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