]> git.baikalelectronics.ru Git - kernel.git/commit
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)
commitbea8e562f31bbcac38ab0a9f142fe8d993564451
tree9f8910499824fbed47f94db9ea7f16489e9339e3
parent886f238934541cfbdd54136252248dfbfb15bfc4
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