fib_trie: Add functions should_inflate and should_halve
authorAlexander Duyck <alexander.h.duyck@redhat.com>
Wed, 31 Dec 2014 18:56:37 +0000 (10:56 -0800)
committerDavid S. Miller <davem@davemloft.net>
Wed, 31 Dec 2014 23:25:54 +0000 (18:25 -0500)
commitf05a48198bf742efd9d36553c51e98a648dbe807
treeb507ffa2ec5a895c13733063725d6b6153976138
parentcf3637bb8f07fb3b6791708f1d5118afb5446061
fib_trie: Add functions should_inflate and should_halve

This change pulls the logic for if we should inflate/halve the nodes out
into separate functions.  It also addresses what I believe is a bug where 1
full node is all that is needed to keep a node from ever being halved.

Simple script to reproduce the issue:
modprobe dummy; ifconfig dummy0 up
for i in `seq 0 255`; do ifconfig dummy0:$i 10.0.${i}.1/24 up; done
ifconfig dummy0:256 10.0.255.33/16 up
for i in `seq 0 254`; do ifconfig dummy0:$i down; done

Results from /proc/net/fib_triestat
Before:
Local:
Aver depth:     3.00
Max depth:      4
Leaves:         17
Prefixes:       18
Internal nodes: 11
  1: 8  2: 2  10: 1
Pointers: 1048
Null ptrs: 1021
Total size: 11  kB
After:
Local:
Aver depth:     3.41
Max depth:      5
Leaves:         17
Prefixes:       18
Internal nodes: 12
  1: 8  2: 3  3: 1
Pointers: 36
Null ptrs: 8
Total size: 3  kB

Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
net/ipv4/fib_trie.c