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 10:54:25 -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: David Miller <davem@...emloft.net>
Date: Thu, 11 Dec 2014 21:32:16 -0500 (EST)

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

Alex, in case it isn't clear, I'm hoping that you might have some
thoughts on this aspect of your changes. :)
--
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

Powered by blists - more mailing lists