From: Alexander Duyck <alexander.h.duyck@redhat.com>
To: Dave Taht <dave.taht@gmail.com>
Cc: "netdev@vger.kernel.org" <netdev@vger.kernel.org>
Subject: Re: [RFC PATCH 00/17] fib_trie: Reduce time spent in fib_table_lookup by 35 to 75%
Date: Mon, 22 Dec 2014 10:38:12 -0800 [thread overview]
Message-ID: <54986514.1010502@redhat.com> (raw)
In-Reply-To: <CAA93jw7Zz8_wToKOou42mXhgunZypQ6f=oGEHZk2K6CbrsrNqg@mail.gmail.com>
On 12/22/2014 10:08 AM, Dave Taht wrote:
> impressive. I think. But I don't quite understand what you mean by a depth of 7?
>
> What did your routing table actually look like?
>
> For example, my ipv4 routing table looks like this at the moment.
>
> What is depth? searching from /32, /31, /30, /29?
What I was referring to is the local trie since all routing ends up
having to do a failed lookup there before we can look in the main trie.
What I did is populate a list of addresses such that I had 15 bits set
in the lower 16 of the address. By doing that it allowed me to stress
the trie pretty hard since it can only inflate out to a tnode with 8
children.
My routing test was from my ixgbe which was on a 10.0.0.X address to a
dummy address at 192.168.255.253 which resulted in it being routed to
the dummy interface. The ixgbe to local receive was to address
192.168.255.254.
Below is all the info for my trie.
- Alex
[root@ahduyck-vm-fedora20 net]# cat /proc/net/fib_triestat
Basic info: size of leaf: 40 bytes, size of tnode: 40 bytes.
Main:
Aver depth: 2.80
Max depth: 4
Leaves: 15
Prefixes: 15
Internal nodes: 6
2: 2 3: 4
Pointers: 40
Null ptrs: 20
Total size: 2 kB
Local:
Aver depth: 3.87
Max depth: 7
Leaves: 49
Prefixes: 50
Internal nodes: 24
1: 10 2: 6 3: 7 4: 1
Pointers: 116
Null ptrs: 44
Total size: 7 kB
[root@ahduyck-vm-fedora20 ~]# cat /proc/net/fib_trie
Main:
+-- 0.0.0.0/0 3 0 5
+-- 0.0.0.0/4 2 0 2
|-- 0.0.0.0
/0 universe UNICAST
+-- 10.0.0.0/22 3 0 4
|-- 10.0.0.0
/24 link UNICAST
|-- 10.0.1.0
/24 link UNICAST
|-- 10.0.2.0
/24 link UNICAST
|-- 10.0.3.0
/24 link UNICAST
|-- 169.254.0.0
/16 link UNICAST
+-- 192.168.0.0/16 3 1 4
|-- 192.168.122.0
/24 link UNICAST
|-- 192.168.128.0
/24 link UNICAST
|-- 192.168.192.0
/24 link UNICAST
+-- 192.168.224.0/19 3 1 4
|-- 192.168.224.0
/24 link UNICAST
|-- 192.168.240.0
/24 link UNICAST
|-- 192.168.248.0
/24 link UNICAST
+-- 192.168.252.0/22 2 0 1
|-- 192.168.252.0
/24 link UNICAST
|-- 192.168.254.0
/24 link UNICAST
|-- 192.168.255.0
/24 link UNICAST
Local:
+-- 0.0.0.0/0 3 0 5
+-- 10.0.0.0/22 4 0 4
|-- 10.0.0.0
/32 link BROADCAST
|-- 10.0.0.128
/32 host LOCAL
|-- 10.0.0.255
/32 link BROADCAST
|-- 10.0.1.0
/32 link BROADCAST
|-- 10.0.1.128
/32 host LOCAL
|-- 10.0.1.255
/32 link BROADCAST
|-- 10.0.2.0
/32 link BROADCAST
|-- 10.0.2.128
/32 host LOCAL
|-- 10.0.2.255
/32 link BROADCAST
|-- 10.0.3.0
/32 link BROADCAST
|-- 10.0.3.128
/32 host LOCAL
|-- 10.0.3.255
/32 link BROADCAST
+-- 127.0.0.0/8 2 0 2
+-- 127.0.0.0/31 1 0 0
|-- 127.0.0.0
/32 link BROADCAST
/8 host LOCAL
|-- 127.0.0.1
/32 host LOCAL
|-- 127.255.255.255
/32 link BROADCAST
+-- 192.168.0.0/16 3 1 4
+-- 192.168.122.0/24 2 0 1
|-- 192.168.122.0
/32 link BROADCAST
|-- 192.168.122.173
/32 host LOCAL
|-- 192.168.122.255
/32 link BROADCAST
+-- 192.168.128.0/24 2 0 2
+-- 192.168.128.0/31 1 0 0
|-- 192.168.128.0
/32 link BROADCAST
|-- 192.168.128.1
/32 host LOCAL
|-- 192.168.128.255
/32 link BROADCAST
+-- 192.168.192.0/24 2 0 2
+-- 192.168.192.0/31 1 0 0
|-- 192.168.192.0
/32 link BROADCAST
|-- 192.168.192.1
/32 host LOCAL
|-- 192.168.192.255
/32 link BROADCAST
+-- 192.168.224.0/19 3 2 4
+-- 192.168.224.0/24 2 0 2
|-- 192.168.224.0
/32 link BROADCAST
|-- 192.168.224.1
/32 host LOCAL
|-- 192.168.224.255
/32 link BROADCAST
+-- 192.168.240.0/24 2 0 2
+-- 192.168.240.0/31 1 0 0
|-- 192.168.240.0
/32 link BROADCAST
|-- 192.168.240.1
/32 host LOCAL
|-- 192.168.240.255
/32 link BROADCAST
+-- 192.168.248.0/22 3 0 6
+-- 192.168.248.0/31 1 0 0
|-- 192.168.248.0
/32 link BROADCAST
|-- 192.168.248.1
/32 host LOCAL
|-- 192.168.248.255
/32 link BROADCAST
+-- 192.168.252.0/22 3 1 2
+-- 192.168.252.0/31 1 0 0
|-- 192.168.252.0
/32 link BROADCAST
|-- 192.168.252.1
/32 host LOCAL
|-- 192.168.252.255
/32 link BROADCAST
+-- 192.168.254.0/31 1 0 0
|-- 192.168.254.0
/32 link BROADCAST
|-- 192.168.254.1
/32 host LOCAL
|-- 192.168.254.255
/32 link BROADCAST
+-- 192.168.255.0/31 1 0 0
|-- 192.168.255.0
/32 link BROADCAST
|-- 192.168.255.1
/32 host LOCAL
+-- 192.168.255.128/25 3 1 4
|-- 192.168.255.128
/32 host LOCAL
|-- 192.168.255.192
/32 host LOCAL
|-- 192.168.255.224
/32 host LOCAL
+-- 192.168.255.240/28 3 1 4
|-- 192.168.255.240
/32 host LOCAL
|-- 192.168.255.248
/32 host LOCAL
|-- 192.168.255.252
/32 host LOCAL
+-- 192.168.255.254/31 1 0 0
|-- 192.168.255.254
/32 host LOCAL
|-- 192.168.255.255
/32 link BROADCAST
next prev parent reply other threads:[~2014-12-22 18:38 UTC|newest]
Thread overview: 30+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-12-22 17:40 [RFC PATCH 00/17] fib_trie: Reduce time spent in fib_table_lookup by 35 to 75% Alexander Duyck
2014-12-22 17:40 ` [RFC PATCH 01/17] fib_trie: Update usage stats to be percpu instead of global variables Alexander Duyck
2014-12-22 19:21 ` Cong Wang
2014-12-22 17:41 ` [RFC PATCH 02/17] fib_trie: Make leaf and tnode more uniform Alexander Duyck
2014-12-22 18:33 ` David Miller
2014-12-22 18:55 ` Alexander Duyck
2014-12-22 21:50 ` David Miller
2014-12-22 23:38 ` Alexander Duyck
2014-12-22 17:41 ` [RFC PATCH 03/17] fib_trie: Merge tnode_free and leaf_free into node_free Alexander Duyck
2014-12-22 17:41 ` [RFC PATCH 04/17] fib_trie: Merge leaf into tnode Alexander Duyck
2014-12-22 17:41 ` [RFC PATCH 05/17] fib_trie: Optimize fib_table_lookup to avoid wasting time on loops/variables Alexander Duyck
2014-12-22 18:30 ` David Miller
2014-12-22 17:41 ` [RFC PATCH 06/17] fib_trie: Optimize fib_find_node Alexander Duyck
2014-12-22 17:41 ` [RFC PATCH 07/17] fib_trie: Optimize fib_table_insert Alexander Duyck
2014-12-22 17:41 ` [RFC PATCH 08/17] fib_trie: Update meaning of pos to represent unchecked bits Alexander Duyck
2014-12-22 17:41 ` [RFC PATCH 09/17] fib_trie: Use unsigned long for anything dealing with a shift by bits Alexander Duyck
2014-12-22 17:41 ` [RFC PATCH 10/17] fib_trie: Push rcu_read_lock/unlock to callers Alexander Duyck
2014-12-22 17:42 ` [RFC PATCH 11/17] fib_trie: Move resize to after inflate/halve Alexander Duyck
2014-12-22 17:42 ` [RFC PATCH 12/17] fib_trie: Add functions should_inflate and should_halve Alexander Duyck
2014-12-22 17:42 ` [RFC PATCH 13/17] fib_trie: Push assignment of child to parent down into inflate/halve Alexander Duyck
2014-12-22 17:42 ` [RFC PATCH 14/17] fib_trie: Push tnode flushing down to inflate/halve Alexander Duyck
2014-12-22 17:42 ` [RFC PATCH 15/17] fib_trie: inflate/halve nodes in a more RCU friendly way Alexander Duyck
2014-12-22 17:42 ` [RFC PATCH 16/17] fib_trie: Remove checks for index >= tnode_child_length from tnode_get_child Alexander Duyck
2014-12-22 17:42 ` [RFC PATCH 17/17] fib_trie: Add tracking value for suffix length Alexander Duyck
2014-12-22 18:32 ` David Miller
2014-12-22 18:08 ` [RFC PATCH 00/17] fib_trie: Reduce time spent in fib_table_lookup by 35 to 75% Dave Taht
2014-12-22 18:38 ` Alexander Duyck [this message]
2014-12-22 18:59 ` Dave Taht
2014-12-22 18:53 ` David Miller
2014-12-22 18:35 ` David Miller
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=54986514.1010502@redhat.com \
--to=alexander.h.duyck@redhat.com \
--cc=dave.taht@gmail.com \
--cc=netdev@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).