From: Alexander Duyck <alexander.duyck@gmail•com>
To: David Miller <davem@davemloft•net>, alexander.h.duyck@redhat•com
Cc: netdev@vger•kernel.org
Subject: Re: [net PATCH] fib_trie: Fix trie balancing issue if new node pushes down existing node
Date: Fri, 12 Dec 2014 08:09:15 -0800 [thread overview]
Message-ID: <548B132B.5000606@gmail.com> (raw)
In-Reply-To: <20141212.105425.2023800747122061277.davem@davemloft.net>
On 12/12/2014 07:54 AM, David Miller wrote:
> From: David Miller <davem@davemloft•net>
> Date: Thu, 11 Dec 2014 21:32:16 -0500 (EST)
>
>> From: Alexander Duyck <alexander.h.duyck@redhat•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@redhat•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. :)
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.
- Alex
next prev parent reply other threads:[~2014-12-12 16:09 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-12-11 5:49 [net PATCH] fib_trie: Fix trie balancing issue if new node pushes down existing node Alexander Duyck
2014-12-12 2:32 ` David Miller
2014-12-12 15:54 ` David Miller
2014-12-12 16:09 ` Alexander Duyck [this message]
2014-12-12 17:05 ` David Laight
2014-12-12 15:55 ` Alexander Duyck
2014-12-12 16:00 ` David Miller
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=548B132B.5000606@gmail.com \
--to=alexander.duyck@gmail$(echo .)com \
--cc=alexander.h.duyck@redhat$(echo .)com \
--cc=davem@davemloft$(echo .)net \
--cc=netdev@vger$(echo .)kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox