From: Tom Herbert <tom@herbertland.com>
To: Herbert Xu <herbert@gondor.apana.org.au>
Cc: "David S. Miller" <davem@davemloft.net>,
Linux Kernel Network Developers <netdev@vger.kernel.org>,
Thomas Graf <tgraf@suug.ch>, Kernel Team <kernel-team@fb.com>
Subject: Re: [PATCH net-next 1/3] rhashtable: Add a function for in order insertion in buckets
Date: Tue, 14 Jul 2015 09:42:49 -0700 [thread overview]
Message-ID: <CALx6S34mGfzUbmPvsxTZDSJX7tehoh4j3nee3C33a57_FFnerw@mail.gmail.com> (raw)
In-Reply-To: <20150714095721.GA22264@gondor.apana.org.au>
On Tue, Jul 14, 2015 at 2:57 AM, Herbert Xu <herbert@gondor.apana.org.au> wrote:
> Tom Herbert <tom@herbertland.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@herbertland.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@gondor.apana.org.au>
> Home Page: http://gondor.apana.org.au/~herbert/
> PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
next prev parent reply other threads:[~2015-07-14 16:42 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-07-14 0:39 [PATCH net-next 0/3] rhashtable: Wildcard and scored lookups Tom Herbert
2015-07-14 0:39 ` [PATCH net-next 1/3] rhashtable: Add a function for in order insertion in buckets Tom Herbert
2015-07-14 9:57 ` Herbert Xu
2015-07-14 16:42 ` Tom Herbert [this message]
2015-07-14 23:58 ` Herbert Xu
2015-07-15 0:59 ` Tom Herbert
2015-07-15 1:08 ` Herbert Xu
2015-07-14 0:39 ` [PATCH net-next 2/3] rhashtable: allow lookup function to have compare function agument Tom Herbert
2015-07-14 9:44 ` Thomas Graf
2015-07-14 15:43 ` Tom Herbert
2015-07-14 0:39 ` [PATCH net-next 3/3] rhashtable: Add scored lookups Tom Herbert
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CALx6S34mGfzUbmPvsxTZDSJX7tehoh4j3nee3C33a57_FFnerw@mail.gmail.com \
--to=tom@herbertland.com \
--cc=davem@davemloft.net \
--cc=herbert@gondor.apana.org.au \
--cc=kernel-team@fb.com \
--cc=netdev@vger.kernel.org \
--cc=tgraf@suug.ch \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.