• Alexander Duyck's avatar
    fib_trie: Add functions should_inflate and should_halve · f05a4819
    Alexander Duyck authored
    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: default avatarAlexander Duyck <alexander.h.duyck@redhat.com>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    f05a4819
fib_trie.c 56.2 KB