fib_trie: Add tracking value for suffix length
authorAlexander Duyck <alexander.h.duyck@redhat.com>
Wed, 31 Dec 2014 18:57:08 +0000 (10:57 -0800)
committerDavid S. Miller <davem@davemloft.net>
Wed, 31 Dec 2014 23:25:55 +0000 (18:25 -0500)
commit5405afd1a30620de8601436bae739c67c0bc7324
tree9f8910499824fbed47f94db9ea7f16489e9339e3
parent21d1f11db0e2f20a549ad8322879507850544670
fib_trie: Add tracking value for suffix length

This change adds a tracking value for the maximum suffix length of all
prefixes stored in any given tnode.  With this value we can determine if we
need to backtrace or not based on if the suffix is greater than the pos
value.

By doing this we can reduce the CPU overhead for lookups in the local table
as many of the prefixes there are 32b long and have a suffix length of 0
meaning we can immediately backtrace to the root node without needing to
test any of the nodes between it and where we ended up.

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