netdev - Re: [PATCH v2 net-next 2/3] rhashtable: Add a function for in order insertion and lookup in buckets

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, 15 Jul 2015 12:46:45 -0700
From:	Tom Herbert <tom@...bertland.com>
To:	Herbert Xu <herbert@...dor.apana.org.au>
Cc:	"David S. Miller" <davem@...emloft.net>,
	Linux Kernel Network Developers <netdev@...r.kernel.org>,
	Thomas Graf <tgraf@...g.ch>, Kernel Team <kernel-team@...com>
Subject: Re: [PATCH v2 net-next 2/3] rhashtable: Add a function for in order
 insertion and lookup in buckets

On Tue, Jul 14, 2015 at 10:54 PM, Herbert Xu
<herbert@...dor.apana.org.au> wrote:
> On Tue, Jul 14, 2015 at 04:45:48PM -0700, Tom Herbert wrote:
>> The obj_orderfn function may be specified in the parameters for a
>> rhashtable. When inserting an element this function is used to order
>> objects in a bucket list (greatest to least ordering value).This
>> allows entries to have wild card fields, where entries with
>> more specific information match are placed first in the bucket.
>> When a lookup is done, the first match found will contain
>> the most specific match.
>>
>> In order to maintain ordering guarantees during rehash, the
>> rhashtable_lookup_ordered_cmpfn was added. This function will check
>> future tables for matches that would have a greater insertion order
>> than a match found in an older table.
>>
>> Signed-off-by: Tom Herbert <tom@...bertland.com>
>
> There is another problem with exposing rhashtable directly to these
> duplicate entries.  It breaks the logic on when to resize.  In the
> worst case on a server with a single port you can end up with a
> large hash table where everything is stored in a single chain.
>
> Granted you can work around this by teaching rhashtable to count
> identical entries as a single entry.  But I really think it's much
> easier to just have this logic sit on top of rhashtable instead of
> inside it.
>
> The memory cost is merely 8 bytes per local port, is it really too
> much?
>
Okay, it looks like there is already an additional hlist_node in
skc_common that can be used for a secondary hash. It's conceivable
this can be generalized and used in the TCP listeners also in
combination with rhashtable.

Tom

> Cheers,
> --
> Email: Herbert Xu <herbert@...dor.apana.org.au>
> Home Page: http://gondor.apana.org.au/~herbert/
> PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
--
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