netdev - Re: [RFC PATCH 02/17] fib_trie: Make leaf and tnode more uniform

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

Message-Id: <20141222.165015.1694288362513627826.davem@davemloft.net>
Date:	Mon, 22 Dec 2014 16:50:15 -0500 (EST)
From:	David Miller <davem@...emloft.net>
To:	alexander.h.duyck@...hat.com
Cc:	netdev@...r.kernel.org
Subject: Re: [RFC PATCH 02/17] fib_trie: Make leaf and tnode more uniform

From: Alexander Duyck <alexander.h.duyck@...hat.com>
Date: Mon, 22 Dec 2014 10:55:17 -0800

> The thing is I don't think we would actually be saving any space. The
> slub allocator will round us up anyway.  On a 32b system the size is
> 28B if I recall correctly.  Dropping it to 24B would mean only a 2
> child node could be allocated from the 32B slab.  Anything larger than
> that it wouldn't matter.

Indeed, you even mention this in the commit messages of your
series.

> My real concern with all of this is the fact that we have to do 2
> separate memory reads per node, one for the key info and one for the
> child pointer.  I really think we need to get this down to 1 in order
> to get there, but the overhead is the tricky part for that. What I
> would look at doing is splitting the tnode into two parts. One would
> be a key vector (key, pos, bits, seq) paired with a pointer to either
> a tnode_info or leaf_info, the other would be something like a
> tnode_info (rcu, parent pointer, full_children, empty_children, key
> vector array[0]) that provides a means of backtracing and stores the
> nodes.  The problem is it makes insertion/deletion and backtracking
> more complicated and doubles (64b) or quadruples (32b) the memory
> needed as such I am still just throwing the idea around and haven't
> gotten into implementation yet.

I think calling into this code twice for every non-local FIB lookup
has costs as well.

And yes I agree with you that the memory references matter a lot.
--
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