netdev - [RFC] fib_trie: memory waste solutions

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]

Date:	Fri, 4 Apr 2008 09:02:57 -0700
From:	Stephen Hemminger <shemminger@...tta.com>
To:	David Miller <davem@...emloft.net>
Cc:	Eric Dumazet <dada1@...mosbay.com>,
	Robert Olsson <Robert.Olsson@...a.slu.se>,
	netdev@...r.kernel.org
Subject: [RFC] fib_trie: memory waste solutions

Eric wisely pointed out that for larger sizes of nodes, the
current allocation in fib_trie wastes lots of memory.  For a sample
of routes extracted from the bugzilla bug the largest node grows
to 2M bytes on 64 bit system. This leads to 2044K of wasted memory.

There are two possible solutions (see attached). One uses vmalloc()
rather than alloc_pages, but has to add complexity on freeing.
The other adds a layer of indirection to the tnode lookup.

Both have been tested on net-2.6.26 with the huge route table.
I slightly prefer the vmalloc version, but both work fine.

View attachment "fib-trie-vmalloc.patch" of type "text/x-patch" (1992 bytes)

View attachment "fib-trie-split-child.patch" of type "text/x-patch" (2795 bytes)