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] [day] [month] [year] [list]

Date:	Fri, 12 Dec 2014 17:05:29 +0000
From:	David Laight <David.Laight@...LAB.COM>
To:	'Alexander Duyck' <alexander.duyck@...il.com>,
	David Miller <davem@...emloft.net>,
	"alexander.h.duyck@...hat.com" <alexander.h.duyck@...hat.com>
CC:	"netdev@...r.kernel.org" <netdev@...r.kernel.org>
Subject: RE: [net PATCH] fib_trie: Fix trie balancing issue if new node
 pushes down existing node

From: Alexander Duyck
...
> >> 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. :)
> 
> Route flaps should at most trigger an inflate without a deflate due to
> the way the resize logic works.  If this occurs often it would be useful
> since then there would already be space in the tree for the next time
> around.

One way to deal with 'flapping' is to leave deleted items in the tree
(marked so they won't be used).
Deleted entries do need to be garbage collected at some point.
Doing so during insert is more than adequate, and possibly only for
nodes that are traversed while processing the insert itself
(and maybe only is the ratio of valid to invalid entries is low).

This might also mean that you don't need to actively run any timeouts.
Timed out entries just stay put - marked invalid by their timestamp.

	David



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