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

[Alexander Duyck <alexander.h.duyck@redhat.com>]

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(-)

--