netdev - Re: [PATCH net-next 1/3] rhashtable: Add a function for in order insertion 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:	Tue, 14 Jul 2015 09:42:49 -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 net-next 1/3] rhashtable: Add a function for in order
 insertion in buckets

On Tue, Jul 14, 2015 at 2:57 AM, Herbert Xu <herbert@...dor.apana.org.au> wrote:
> Tom Herbert <tom@...bertland.com> 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.
>>
>> Signed-off-by: Tom Herbert <tom@...bertland.com>
>
Hi Herbert,

> I think this is fundamentally broken with respect to rehashing.
> During a rehash you're going to have some elements in the old table
> and some in the new table.  At which point all your ordering
> guarantees go out of the window.
>
Yes, good observation.

> I actually need something quite similar for IPsec.  What I was
> planning on doing is have the actual objects hang off an ordered
> list object.  The ordered list would then be the thing that you
> insert into rhashtable.  This means that during rehashing they
> get moved atomically.
>
Hmm, I do like the simplicity of a flat linear search.

Scored lookups can provides the same functionality, but requires that
we scan all the elements so I see some overhead compared to doing
ordered insertion. One way to resolve the rehash problem is search any
future table after we find a hit in the first table to see if there
are any entries that would precede the element already found. So in
the common non-rehash case lookup happens as it does now except that
we would always check for future_tbl.

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