• Alexander Duyck's avatar
    fib_trie: Optimize fib_table_lookup to avoid wasting time on loops/variables · 9f9e636d
    Alexander Duyck authored
    This patch is meant to reduce the complexity of fib_table_lookup by reducing
    the number of variables to the bare minimum while still keeping the same if
    not improved functionality versus the original.
    
    Most of this change was started off by the desire to rid the function of
    chopped_off and current_prefix_length as they actually added very little to
    the function since they only applied when computing the cindex.  I was able
    to replace them mostly with just a check for the prefix match.  As long as
    the prefix between the key and the node being tested was the same we know
    we can search the tnode fully versus just testing cindex 0.
    
    The second portion of the change ended up being a massive reordering.
    Originally the calls to check_leaf were up near the start of the loop, and
    the backtracing and descending into lower levels of tnodes was later.  This
    didn't make much sense as the structure of the tree means the leaves are
    always the last thing to be tested.  As such I reordered things so that we
    instead have a loop that will delve into the tree and only exit when we
    have either found a leaf or we have exhausted the tree.  The advantage of
    rearranging things like this is that we can fully inline check_leaf since
    there is now only one reference to it in the function.
    Signed-off-by: default avatarAlexander Duyck <alexander.h.duyck@redhat.com>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    9f9e636d
fib_trie.c 57.6 KB