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]

Message-ID: <20150715055411.GA31926@gondor.apana.org.au>
Date:	Wed, 15 Jul 2015 13:54:12 +0800
From:	Herbert Xu <herbert@...dor.apana.org.au>
To:	Tom Herbert <tom@...bertland.com>
Cc:	davem@...emloft.net, netdev@...r.kernel.org, tgraf@...g.ch,
	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 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?

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