netdev - Re: inetpeer with create==0

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:	Wed, 02 Mar 2011 21:36:34 -0800 (PST)
From:	David Miller <davem@...emloft.net>
To:	xiaosuo@...il.com
Cc:	eric.dumazet@...il.com, netdev@...r.kernel.org
Subject: Re: inetpeer with create==0

From: Changli Gao <xiaosuo@...il.com>
Date: Thu, 3 Mar 2011 13:30:03 +0800

> I am just wondering why we need a trie(radix tree) here, we don't have
> to do LPM since the lengths of the keys are always fixed(ether 4 or
> 16). Maybe a hash table is enough and simpler, and it is RCU
> compatible.

Because trie eliminates all of the issues of having to size a hash
table, dynamically resize it, etc.

Trie gives well bounded performance dependent solely upon size of
the table, rather than access patterns, distribution of keys, and
how perfect hash function is.

We used to use a hash table for the page cache too, but now we use
a trie structure there as well, and that uses full long word sized
keys and the generic raidx-tree code.

Using hash tables is really foolish for potentially large data sets.
--
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