netdev - [net-next PATCH v2 0/4] fib_trie: Remove leaf

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-next>] [day] [month] [year] [list]

Message-ID: <20150225232731.1242.38553.stgit@ahduyck-vm-fedora20>
Date:	Wed, 25 Feb 2015 15:31:24 -0800
From:	Alexander Duyck <alexander.h.duyck@...hat.com>
To:	netdev@...r.kernel.org
Cc:	ja@....bg, davem@...emloft.net
Subject: [net-next PATCH v2 0/4] fib_trie: Remove leaf_info structure

This patch set removes the leaf_info structure from the IPv4 fib_trie.  The
general idea is that the leaf_info structure itself only held about 6
actual bits of data, beyond that it was mostly just waste.  As such we can
drop the structure, move the 1 byte representing the prefix/suffix length
into the fib_alias and just link it all into one list.

My testing shows that this saves somewhere between 4 to 10ns depending on
the type of test performed.  I'm suspecting that this represents 1 to 2 L1
cache misses saved per look-up.

One side effect of this change is that semantic_match_miss will now only
increment once per leaf instead of once per leaf_info miss.  However the
stat is already skewed now that we perform a preliminary check on the leaf
as a part of the look-up.

I also have gone through and addressed a number of ordering issues in the
first patch since I had misread the behavior of list_add_tail.

I have since run some additional testing and verified the resulting lists
are in the same order when combining multiple prefix length and tos values
in a single leaf.

v2: Update patches 2 and 3 to use (key ^ n->key) >= (1ul << slen) instead of
    shifting the result of the xor which could be undefined.

---

Alexander Duyck (4):
      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

 include/net/ip_fib.h     |    2 
 net/ipv4/fib_lookup.h    |    3 
 net/ipv4/fib_semantics.c |    4 
 net/ipv4/fib_trie.c      |  489 ++++++++++++++++------------------------------
 4 files changed, 176 insertions(+), 322 deletions(-)

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