[RFC PATCH 00/29] Phase 2 of fib_trie updates

Alexander Duyck
2015-02-24T20:47:57Z

This patch series implements the second phase of the fib_trie changes. I
presented on these and the previous changes at Netdev01 and netconf. The
slides for the Netdev01 presentation can be found at
https://www.netdev01.org/docs/duyck-fib-trie.pdf.

I'm currently debating if I should just submit the entire patch-set as-is
or if I should hold off on submitting the last 10 patches as they currently
have a potential performance impact in the case of a large number of
entries placed in the local table. Specifically I have seen that removing
an interface in the case of 8K local subnets being configured on it
resulted in the time for a dummy interface being removed increasing from
about .6 seconds to 2.4 seconds. I am not sure how common of a use-case
something like this would be. I have not seen the same issue if I assign
8K routes to the interface as I believe the fib_table_flush aggregates them
all in to one resize action.

The entire series reduces the total look-up time by another 20-35% versus
what is currently in the 4.0-rc1 kernel. So for example a set of routing
look-ups which took 140ns in the 4.0-rc1 kernel will now only take about
105ns after these patches.

---

Alexander Duyck (29):
fib_trie: Convert fib_alias to hlist from list
fib_trie: Replace plen with slen in leaf_info
fib_trie: Add slen to fib alias
fib_trie: Remove leaf_info
fib_trie: Only resize N/2 times instead N * log(N) times in fib_table_flush
fib_trie: Fib walk rcu should take a tnode and key instead of a trie and a leaf
fib_trie: Fib find node should return parent
fib_trie: Update insert and delete to make use of tp from find_node
fib_trie: Make fib_table rcu safe
fib_trie: Return pointer to tnode pointer in resize/inflate/halve
fib_trie: Rename tnode to key_vector
fib_trie: move leaf and tnode to occupy the same spot in the key vector
fib_trie: replace tnode_get_child functions with get_child macros
fib_trie: Rename tnode_child_length to child_length
fib_trie: Add tnode struct as a container for fields not needed in key_vector
fib_trie: Move rcu from key_vector to tnode, add accessors.
fib_trie: Pull empty_children and full_children into tnode
fib_trie: Move parent from key_vector to tnode
fib_trie: Add key vector to root, return parent key_vector in resize
fib_trie: Push net pointer down into fib_trie insert/delete/flush calls
fib_trie: Rewrite handling of RCU to include parent in replacement
fib_trie: Allocate tnode as array of key_vectors instead of key_vector as array of tnode pointers
fib_trie: Add leaf_init
fib_trie: Update tnode_new to drop use of put_child_root
fib_trie: Add function for dropping children from trie
fib_trie: Use put_child to only copy key_vectors instead of pointers
fib_trie: Move key and pos into key_vector from tnode
fib_trie: Move slen from tnode to key vector
fib_trie: Push bits up one level, and move leaves up into parent key_vector array

include/net/ip_fib.h | 80 +-
include/net/netns/ipv4.h | 7
net/ipv4/fib_frontend.c | 89 ++
net/ipv4/fib_lookup.h | 3
net/ipv4/fib_semantics.c | 4
net/ipv4/fib_trie.c | 1974 ++++++++++++++++++++++++----------------------
6 files changed, 1152 insertions(+), 1005 deletions(-)

--