netdev - Re: [net-next PATCH 00/17] fib_trie: Reduce time spent in fib_table

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:	Fri, 02 Jan 2015 15:34:04 -0500 (EST)
From:	David Miller <davem@...emloft.net>
To:	alexander.duyck@...il.com
Cc:	alexander.h.duyck@...hat.com, netdev@...r.kernel.org
Subject: Re: [net-next PATCH 00/17] fib_trie: Reduce time spent in
 fib_table_lookup by 35 to 75%

From: Alexander Duyck <alexander.duyck@...il.com>
Date: Fri, 02 Jan 2015 08:28:00 -0800

> I'm hoping that growing smaller nodes will help offset the fact that we
> have to restrict the larger nodes.  For backtracing these large nodes
> come at a significant price as each bit value beyond what can be fit in
> a cache-line means one additional cache line being read when
> backtracking.  So for example two 3 bit nodes on 64b require 4
> cache-lines when backtracking an all 1s value, but one 6 bit node will
> require reading 5 cache-lines.

If you load a full BGP table into fib_trie you will notice that
basically what it does is degenerate into what is essentially a trie
of huge hash tables.  Largest will be the root node.

So a good test would be loading a sample full BGP table into fib_trie,
then iterate randomly choosing 15 or so routes to remove then re-add
over and over again.  This would simulate route flaps, and you can
check to see how much deeper the trie is with your changes added.

> Also I hope to reduce the memory accesses/dependencies to half of what
> they currently are so hopefully the two will offset each other in the
> case where there were performance gains from having nodes larger than
> 256B that cannot reach the necessary value to inflate after the change. 
> If nothing else I figure I can tune the utilization values based on the
> truesize so that we get the best memory utilization/performance ratio. 
> If necessary I might relax the value from the 50% it is now as we pretty
> much have to be all full nodes in order to inflate based on the truesize
> beyond 256B.

See above.

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html