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
| ||
|
Date: Thu, 3 Mar 2011 14:27:40 +0800 From: Changli Gao <xiaosuo@...il.com> To: David Miller <davem@...emloft.net> Cc: eric.dumazet@...il.com, netdev@...r.kernel.org Subject: Re: inetpeer with create==0 On Thu, Mar 3, 2011 at 1:36 PM, David Miller <davem@...emloft.net> wrote: > > 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. Thanks for your explaination. Routing cache has all of these issues. :) > > 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. > However, I don't agree with you at every aspect. Radix tree may cost lots of memory than a rbtree, avl tree or hash table. Here is a case: turning to rbtree from radix tree. http://git.kernel.org/?p=linux/kernel/git/davem/net-next-2.6.git;a=commit;h=8549164143a5431f9d9ea846acaa35a862410d9c Since the keys of inetpeer rely on the access pattern, a attacker may do a OOM DoS attack using sparse keys. We can't simply limit the number of inetpeers to limit the memory cost of this subsystem. We have to count the memory used for the inner branches of a radix tree. Nevertheless, a attacker may also make this OS inefficiency by reduce the max number of inetpeers. Hash table + jhash have been proven a safe and efficient data structure for large data sets(conntrack and ipvs), although the size of the hash table may have to be adjusted by an administrator. -- Regards, Changli Gao(xiaosuo@...il.com) -- 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
Powered by blists - more mailing lists