fib_trie: Fix trie balancing issue if new node pushes down existing node
authorAlexander Duyck <alexander.h.duyck@redhat.com>
Thu, 11 Dec 2014 05:49:22 +0000 (21:49 -0800)
committerDavid S. Miller <davem@davemloft.net>
Fri, 12 Dec 2014 15:58:53 +0000 (10:58 -0500)
commite962f30297491fddc55a432d5d37df33c83e06f2
tree713878612914b7d98a233925ccd45fdf4f34ee99
parent53f6b708f89668cfb5eb9e49384b64b237bae0b2
fib_trie: Fix trie balancing issue if new node pushes down existing node

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.

  ip link add type dummy
  ipval=184549374
  bit=2
  for i in `seq 1 23`
  do
    ifconfig dummy0:$bit $ipval/8
    ipval=`expr $ipval - $bit`
    bit=`expr $bit \* 2`
  done
  cat /proc/net/fib_triestat

Running the script before the patch:

Local:
Aver depth:     10.82
Max depth:      23
Leaves:         29
Prefixes:       30
Internal nodes: 27
  1: 26  2: 1
Pointers: 56
Null ptrs: 1
Total size: 5  kB

After applying the patch and repeating:

Local:
Aver depth:     4.72
Max depth:      9
Leaves:         29
Prefixes:       30
Internal nodes: 12
  1: 3  2: 2  3: 7
Pointers: 70
Null ptrs: 30
Total size: 4  kB

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>
Signed-off-by: David S. Miller <davem@davemloft.net>
net/ipv4/fib_trie.c