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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Wed, 02 Mar 2011 22:42:20 -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 14:27:40 +0800

> 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. :)

Thats why I am working hard to remove it :-)

The %99 percentile performance of our routing cache is absolutely
terrible.  The routing cache does nothing except get in the way.

It is the reason why Linux is still completely unsuitable for use as a
router on the core internet.

> 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

I would not be against the use of rbtree or similar if it could be
done with with fully RCU non-locked lookups even in the not-present
case.

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

If anything is proven, it is that hashing based collections of cached
information are nothing but trouble when the contents are controlled in
some way by external entities.

Actually, back to the original topic, I wonder how bad it is to simply
elide the recheck in the create==0 case anyways.  Except for the ipv4
fragmentation wraparound protection values, perfect inetpeer finding
is not necessary for correctness.  And IPv4 fragmentation always calls
inetpeer with create!=0.

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