netdev.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [RFC PATCH 00/29] Phase 2 of fib_trie updates
@ 2015-02-24 20:47 Alexander Duyck
  2015-02-24 20:48 ` [RFC PATCH 01/29] fib_trie: Convert fib_alias to hlist from list Alexander Duyck
                   ` (29 more replies)
  0 siblings, 30 replies; 39+ messages in thread
From: Alexander Duyck @ 2015-02-24 20:47 UTC (permalink / raw)
  To: netdev

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

--

^ permalink raw reply	[flat|nested] 39+ messages in thread

end of thread, other threads:[~2015-02-27 21:01 UTC | newest]

Thread overview: 39+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2015-02-24 20:47 [RFC PATCH 00/29] Phase 2 of fib_trie updates Alexander Duyck
2015-02-24 20:48 ` [RFC PATCH 01/29] fib_trie: Convert fib_alias to hlist from list Alexander Duyck
2015-02-24 21:51   ` Or Gerlitz
2015-02-24 21:52     ` Or Gerlitz
2015-02-24 22:08     ` David Miller
2015-02-24 22:14       ` Alexander Duyck
2015-02-24 22:47   ` Julian Anastasov
2015-02-24 23:09   ` Julian Anastasov
2015-02-24 20:48 ` [RFC PATCH 02/29] fib_trie: Replace plen with slen in leaf_info Alexander Duyck
2015-02-24 20:48 ` [RFC PATCH 03/29] fib_trie: Add slen to fib alias Alexander Duyck
2015-02-24 20:48 ` [RFC PATCH 04/29] fib_trie: Remove leaf_info Alexander Duyck
2015-02-24 20:48 ` [RFC PATCH 05/29] fib_trie: Only resize N/2 times instead N * log(N) times in fib_table_flush Alexander Duyck
2015-02-24 20:48 ` [RFC PATCH 06/29] fib_trie: Fib walk rcu should take a tnode and key instead of a trie and a leaf Alexander Duyck
2015-02-24 20:48 ` [RFC PATCH 07/29] fib_trie: Fib find node should return parent Alexander Duyck
2015-02-24 20:48 ` [RFC PATCH 08/29] fib_trie: Update insert and delete to make use of tp from find_node Alexander Duyck
2015-02-24 20:48 ` [RFC PATCH 09/29] fib_trie: Make fib_table rcu safe Alexander Duyck
2015-02-24 20:49 ` [RFC PATCH 10/29] fib_trie: Return pointer to tnode pointer in resize/inflate/halve Alexander Duyck
2015-02-24 20:49 ` [RFC PATCH 11/29] fib_trie: Rename tnode to key_vector Alexander Duyck
2015-02-24 20:49 ` [RFC PATCH 12/29] fib_trie: move leaf and tnode to occupy the same spot in the key vector Alexander Duyck
2015-02-24 20:49 ` [RFC PATCH 13/29] fib_trie: replace tnode_get_child functions with get_child macros Alexander Duyck
2015-02-24 20:49 ` [RFC PATCH 14/29] fib_trie: Rename tnode_child_length to child_length Alexander Duyck
2015-02-24 20:49 ` [RFC PATCH 15/29] fib_trie: Add tnode struct as a container for fields not needed in key_vector Alexander Duyck
2015-02-24 20:49 ` [RFC PATCH 16/29] fib_trie: Move rcu from key_vector to tnode, add accessors Alexander Duyck
2015-02-24 20:49 ` [RFC PATCH 17/29] fib_trie: Pull empty_children and full_children into tnode Alexander Duyck
2015-02-24 20:49 ` [RFC PATCH 18/29] fib_trie: Move parent from key_vector to tnode Alexander Duyck
2015-02-24 20:50 ` [RFC PATCH 19/29] fib_trie: Add key vector to root, return parent key_vector in resize Alexander Duyck
2015-02-24 20:50 ` [RFC PATCH 20/29] fib_trie: Push net pointer down into fib_trie insert/delete/flush calls Alexander Duyck
2015-02-24 20:50 ` [RFC PATCH 21/29] fib_trie: Rewrite handling of RCU to include parent in replacement Alexander Duyck
2015-02-24 20:50 ` [RFC PATCH 22/29] fib_trie: Allocate tnode as array of key_vectors instead of key_vector as array of tnode pointers Alexander Duyck
2015-02-24 20:50 ` [RFC PATCH 23/29] fib_trie: Add leaf_init Alexander Duyck
2015-02-24 20:50 ` [RFC PATCH 24/29] fib_trie: Update tnode_new to drop use of put_child_root Alexander Duyck
2015-02-24 20:50 ` [RFC PATCH 25/29] fib_trie: Add function for dropping children from trie Alexander Duyck
2015-02-24 20:50 ` [RFC PATCH 26/29] fib_trie: Use put_child to only copy key_vectors instead of pointers Alexander Duyck
2015-02-24 20:50 ` [RFC PATCH 27/29] fib_trie: Move key and pos into key_vector from tnode Alexander Duyck
2015-02-24 20:51 ` [RFC PATCH 28/29] fib_trie: Move slen from tnode to key vector Alexander Duyck
2015-02-24 20:51 ` [RFC PATCH 29/29] fib_trie: Push bits up one level, and move leaves up into parent key_vector array Alexander Duyck
2015-02-25  3:53 ` [RFC PATCH 00/29] Phase 2 of fib_trie updates David Miller
2015-02-25  5:12   ` Alexander Duyck
2015-02-27 21:01     ` David Miller

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).