FAQ Search Today's Posts Mark Forums Read
» Video Reviews

» Linux Archive

Linux-archive is a website aiming to archive linux email lists and to make them easily accessible for linux users/developers.


» Sponsor

» Partners

» Sponsor

Go Back   Linux Archive > Redhat > Device-mapper Development

 
 
LinkBack Thread Tools
 
Old 08-22-2012, 06:01 PM
Tejun Heo
 
Default hashtable: introduce a small and naive hashtable

Hello, Sasha.

On Wed, Aug 22, 2012 at 04:26:56AM +0200, Sasha Levin wrote:
> +#define DEFINE_HASHTABLE(name, bits)
> + struct hlist_head name[HASH_SIZE(bits)];

Shouldn't this be something like the following?

#define DEFINE_HASHTABLE(name, bits)
struct hlist_head name[HASH_SIZE(bits)] =
{ [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT };

Also, given that the declaration isn't non-trivial, you'll probably
want a matching DECLARE_HASHTABLE() macro too.

> +/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */
> +#define hash_min(val, bits) ((sizeof(val)==4) ? hash_32((val), (bits)) : hash_long((val), (bits)))

Why is the branching condition sizeof(val) == 4 instead of <= 4?
Also, no biggie but why isn't this macro in caps?

> +/**
> + * hash_add_size - add an object to a hashtable
> + * @hashtable: hashtable to add to
> + * @bits: bit count used for hashing
> + * @node: the &struct hlist_node of the object to be added
> + * @key: the key of the object to be added
> + */
> +#define hash_add_size(hashtable, bits, node, key)
> + hlist_add_head(node, &hashtable[hash_min(key, bits)]);
> +
> +/**
> + * hash_add - add an object to a hashtable
> + * @hashtable: hashtable to add to
> + * @node: the &struct hlist_node of the object to be added
> + * @key: the key of the object to be added
> + */
> +#define hash_add(hashtable, node, key)
> + hash_add_size(hashtable, HASH_BITS(hashtable), node, key)

It would be nice if the comments actually say something which can
differentiate the two. Ditto for rcu variants.

> +/**
> + * hash_add_rcu_size - add an object to a rcu enabled hashtable
> + * @hashtable: hashtable to add to
> + * @bits: bit count used for hashing
> + * @node: the &struct hlist_node of the object to be added
> + * @key: the key of the object to be added
> + */
> +#define hash_add_rcu_size(hashtable, bits, node, key)
> + hlist_add_head_rcu(node, &hashtable[hash_min(key, bits)]);
> +
> +/**
> + * hash_add_rcu - add an object to a rcu enabled hashtable
> + * @hashtable: hashtable to add to
> + * @node: the &struct hlist_node of the object to be added
> + * @key: the key of the object to be added
> + */
> +#define hash_add_rcu(hashtable, node, key)
> + hash_add_rcu_size(hashtable, HASH_BITS(hashtable), node, key)

Or maybe we're better off with hash_head_size() and hash_head()? I'll
expand on it later. Please bear with me.

> +/**
> + * hash_hashed - check whether an object is in any hashtable
> + * @node: the &struct hlist_node of the object to be checked
> + */
> +#define hash_hashed(node) (!hlist_unhashed(node))

As the 'h' in hlist* stand for hash anyway and I think this type of
thin wrappers tend to obfuscate more than anything else.

> +/**
> + * hash_del - remove an object from a hashtable
> + * @node: &struct hlist_node of the object to remove
> + */
> +static inline void hash_del(struct hlist_node *node)
> +{
> + hlist_del_init(node);
> +}
> +
> +/**
> + * hash_del_rcu - remove an object from a rcu enabled hashtable
> + * @node: &struct hlist_node of the object to remove
> + */
> +static inline void hash_del_rcu(struct hlist_node *node)
> +{
> + hlist_del_init_rcu(node);
> +}

If we do that, we can remove all these thin wrappers.

> +#define hash_for_each_size(name, bits, bkt, node, obj, member)
> + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)
> + hlist_for_each_entry(obj, node, &name[bkt], member)
..
> +#define hash_for_each(name, bkt, node, obj, member)
> + hash_for_each_size(name, HASH_BITS(name), bkt, node, obj, member)
...
> +#define hash_for_each_rcu_size(name, bits, bkt, node, obj, member)
> + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)
> + hlist_for_each_entry_rcu(obj, node, &name[bkt], member)
...
> +#define hash_for_each_rcu(name, bkt, node, obj, member)
> + hash_for_each_rcu_size(name, HASH_BITS(name), bkt, node, obj, member)
...
> +#define hash_for_each_safe_size(name, bits, bkt, node, tmp, obj, member)
> + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)
> + hlist_for_each_entry_safe(obj, node, tmp, &name[bkt], member)
...
> +#define hash_for_each_safe(name, bkt, node, tmp, obj, member)
> + hash_for_each_safe_size(name, HASH_BITS(name), bkt, node,
> + tmp, obj, member)
...
> +#define hash_for_each_possible_size(name, obj, bits, node, member, key)
> + hlist_for_each_entry(obj, node, &name[hash_min(key, bits)], member)
...
> +#define hash_for_each_possible(name, obj, node, member, key)
> + hash_for_each_possible_size(name, obj, HASH_BITS(name), node, member, key)
...
> +#define hash_for_each_possible_rcu_size(name, obj, bits, node, member, key)
> + hlist_for_each_entry_rcu(obj, node, &name[hash_min(key, bits)], member)
...
> +#define hash_for_each_possible_rcu(name, obj, node, member, key)
> + hash_for_each_possible_rcu_size(name, obj, HASH_BITS(name),
...
> +#define hash_for_each_possible_safe_size(name, obj, bits, node, tmp, member, key)
> + hlist_for_each_entry_safe(obj, node, tmp,
> + &name[hash_min(key, bits)], member)
...
> +#define hash_for_each_possible_safe(name, obj, node, tmp, member, key)
> + hash_for_each_possible_safe_size(name, obj, HASH_BITS(name),

And also all these. We'd only need hash_for_each_head() and
hash_head(). hash_for_each_possible*() could be nice for convenience,
I suppose.

I think the almost trivial nature of hlist hashtables makes this a bit
tricky and I'm not very sure but having this combinatory explosion is
a bit dazzling when the same functionality can be achieved by simply
combining operations which are already defined and named considering
hashtable. I'm not feeling too strong about this tho. What do others
think?

Also, can you please audit the comments on top of each macro? They
have wrong names and don't differentiate the different variants very
well.

Thanks.

--
tejun

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 08-23-2012, 08:04 PM
Tejun Heo
 
Default hashtable: introduce a small and naive hashtable

Hello, Sasha.

On Thu, Aug 23, 2012 at 02:24:32AM +0200, Sasha Levin wrote:
> > I think the almost trivial nature of hlist hashtables makes this a bit
> > tricky and I'm not very sure but having this combinatory explosion is
> > a bit dazzling when the same functionality can be achieved by simply
> > combining operations which are already defined and named considering
> > hashtable. I'm not feeling too strong about this tho. What do others
> > think?
>
> I'm thinking that this hashtable API will have 2 purposes: First, it would
> prevent the excessive duplication of hashtable implementations all around the code.
>
> Second, it will allow more easily interchangeable hashtable implementations to
> find their way into the kernel. There are several maintainers who would be happy
> to see dynamically sized RCU hashtable, and I'm guessing that several more
> variants could be added based on needs in specific modules.
>
> The second reason is why several things you've mentioned look the way they are:
>
> - No DEFINE_HASHTABLE(): I wanted to force the use of hash_init() since
> initialization for other hashtables may be more complicated than the static
> initialization for this implementation, which means that any place that used
> DEFINE_HASHTABLE() and didn't do hash_init() will be buggy.

I think this is problematic. It looks exactly like other existing
DEFINE macros yet what its semantics is different. I don't think
that's a good idea.

> I'm actually tempted in hiding hlist completely from hashtable users, probably
> by simply defining a hash_head/hash_node on top of the hlist_ counterparts.

I think that it would be best to keep this one simple & obvious, which
already has enough in-kernel users to justify its existence. There
are significant benefits in being trivially understandable and
expectable. If we want more advanced ones - say resizing, hybrid or
what not, let's make that a separate one. No need to complicate the
common straight-forward case for that.

So, I think it would be best to keep this one as straight-forward and
trivial as possible. Helper macros to help its users are fine but
let's please not go for full encapsulation.

Thanks.

--
tejun

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 08-24-2012, 07:59 PM
Tejun Heo
 
Default hashtable: introduce a small and naive hashtable

Hello, Sasha.

On Fri, Aug 24, 2012 at 09:47:19PM +0200, Sasha Levin wrote:
> > I think this is problematic. It looks exactly like other existing
> > DEFINE macros yet what its semantics is different. I don't think
> > that's a good idea.
>
> I can switch that to be DECLARE_HASHTABLE() if the issue is semantics.

If this implementation is about the common trivial case, why not just
have the usual DECLARE/DEFINE_HASHTABLE() combination?

> > So, I think it would be best to keep this one as straight-forward and
> > trivial as possible. Helper macros to help its users are fine but
> > let's please not go for full encapsulation.
>
> What if we cut off the dynamic allocated (but not resizable) hashtable out for
> the moment, and focus on the most common statically allocated hashtable case?
>
> The benefits would be:
>
> - Getting rid of all the _size() macros, which will make the amount of helpers
> here reasonable.
> - Dynamically allocated hashtable can be easily added as a separate
> implementation using the same API. We already have some of those in the kernel...

It seems we have enough of this static usage and solving the static
case first shouldn't hinder the dynamic (!resize) case later, so,
yeah, sounds good to me.

> - When that's ready, I feel it's a shame to lose full encapsulation just due to
> hash_hashed().

I don't know. If we stick to the static (or even !resize dymaic)
straight-forward hash - and we need something like that - I don't see
what the full encapsulation buys us other than a lot of trivial
wrappers.

Thanks.

--
tejun

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 08-24-2012, 08:33 PM
Tejun Heo
 
Default hashtable: introduce a small and naive hashtable

Hello, Sasha.

On Fri, Aug 24, 2012 at 10:11:55PM +0200, Sasha Levin wrote:
> > If this implementation is about the common trivial case, why not just
> > have the usual DECLARE/DEFINE_HASHTABLE() combination?
>
> When we add the dynamic non-resizable support, how would DEFINE_HASHTABLE() look?

Hmmm? DECLARE/DEFINE are usually for static ones.

> > I don't know. If we stick to the static (or even !resize dymaic)
> > straight-forward hash - and we need something like that - I don't see
> > what the full encapsulation buys us other than a lot of trivial
> > wrappers.
>
> Which macros do you consider as trivial within the current API?
>
> Basically this entire thing could be reduced to DEFINE/DECLARE_HASHTABLE and
> get_bucket(), but it would make the life of anyone who wants a slightly
> different hashtable a hell.

Wouldn't the following be enough to get most of the benefits?

* DECLARE/DEFINE
* hash_head()
* hash_for_each_head()
* hash_add*()
* hash_for_each_possible*()

> I think that right now the only real trivial wrapper is hash_hashed(), and I
> think it's a price worth paying to have a single hashtable API instead of
> fragmenting it when more implementations come along.

I'm not objecting strongly against full encapsulation but having this
many thin wrappers makes me scratch my head.

Thanks.

--
tejun

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 08-24-2012, 09:23 PM
Tejun Heo
 
Default hashtable: introduce a small and naive hashtable

Hello,

On Fri, Aug 24, 2012 at 10:53:45PM +0200, Sasha Levin wrote:
> Yup, but we could be using the same API for dynamic non-resizable and static if
> we go with the DECLARE/hash_init. We could switch between them (and other
> implementations) without having to change the code.

I think it's better to stick with the usual conventions.

> > * DECLARE/DEFINE
> > * hash_head()
> > * hash_for_each_head()
> > * hash_add*()
> > * hash_for_each_possible*()
> * hash_for_each*() ?
>
> Why do we need hash_head/hash_for_each_head()? I haven't stumbled on a place yet
> that needed direct access to the bucket itself.

Because whole hash table walking is much less common and we can avoid
another full set of iterators.

> This basically means 11 macros/functions that would let us have full
> encapsulation and will make it very easy for future implementations to work with
> this API instead of making up a new one. It's also not significantly (+~2-3)
> more than the ones you listed.

I'm not sure whether full encapsulation is a good idea for trivial
hashtable. For higher level stuff, sure but at this level I think
benefits coming from known obvious implementation can be larger.
e.g. suppose the caller knows certain entries to be way colder than
others and wants to put them at the end of the chain.

So, I think implmenting the minimal set of helpers which reflect the
underlying trivial implementation explicitly could actually be better
even when discounting the reduced number of wrappers.

Thanks.

--
tejun

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 08-24-2012, 11:07 PM
Tejun Heo
 
Default hashtable: introduce a small and naive hashtable

Hello,

On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> Thats the thing, the amount of things of things you can do with a given bucket
> is very limited. You can't add entries to any point besides the head (without
> walking the entire list).

Kinda my point. We already have all the hlist*() interface to deal
with such cases. Having something which is evidently the trivial
hlist hashtable and advertises as such in the interface can be
helpful. I think we need that more than we need anything fancy.

Heh, this is a debate about which one is less insignificant. I can
see your point. I'd really like to hear what others think on this.

Guys, do we want something which is evidently trivial hlist hashtable
which can use hlist_*() API directly or do we want something better
encapsulated?

Thanks.

--
tejun

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 09-04-2012, 03:35 PM
Steven Rostedt
 
Default hashtable: introduce a small and naive hashtable

On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:

> Looking again at:
>
> +#define hash_for_each_size(name, bits, bkt, node, obj, member)
> + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)
> + hlist_for_each_entry(obj, node, &name[bkt], member)
>
> you will notice that a "break" or "continue" in the inner loop will not
> affect the outer loop, which is certainly not what the programmer would
> expect!
>
> I advise strongly against creating such error-prone construct.
>

A few existing loop macros do this. But they require a do { } while ()
approach, and all have a comment.

It's used by do_each_thread() in sched.h and ftrace does this as well.
Look at kernel/trace/ftrace.c at do_for_each_ftrace_rec().

Yes it breaks 'break' but it does not break 'continue' as it would just
go to the next item that would have been found (like a normal for
would).

-- Steve


--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 09-04-2012, 05:17 PM
Steven Rostedt
 
Default hashtable: introduce a small and naive hashtable

On Tue, 2012-09-04 at 17:40 +0100, Pedro Alves wrote:

> BTW, you can also go a step further and remove the need to close with double }},
> with something like:
>
> #define do_for_each_ftrace_rec(pg, rec)
> for (pg = ftrace_pages_start, rec = &pg->records[pg->index];
> pg && rec == &pg->records[pg->index];
> pg = pg->next)
> for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
>

Yeah, but why bother? It's hidden in a macro, and the extra '{ }' shows
that this is something "special".

-- Steve


--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 09-04-2012, 08:59 PM
Steven Rostedt
 
Default hashtable: introduce a small and naive hashtable

On Tue, 2012-09-04 at 18:21 +0100, Pedro Alves wrote:
> On 09/04/2012 06:17 PM, Steven Rostedt wrote:
> > On Tue, 2012-09-04 at 17:40 +0100, Pedro Alves wrote:
> >
> >> BTW, you can also go a step further and remove the need to close with double }},
> >> with something like:
> >>
> >> #define do_for_each_ftrace_rec(pg, rec)
> >> for (pg = ftrace_pages_start, rec = &pg->records[pg->index];
> >> pg && rec == &pg->records[pg->index];
> >> pg = pg->next)
> >> for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
> >>
> >
> > Yeah, but why bother? It's hidden in a macro, and the extra '{ }' shows
> > that this is something "special".
>
> The point of both changes is that there's nothing special in the end
> at all. It all just works...
>

It would still fail on a 'break'. The 'while' macro tells us that it is
special, because in the end, it wont work.

-- Steve


--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 09-04-2012, 10:41 PM
Steven Rostedt
 
Default hashtable: introduce a small and naive hashtable

On Tue, 2012-09-04 at 22:51 +0100, Pedro Alves wrote:
> On 09/04/2012 09:59 PM, Steven Rostedt wrote:
> > On Tue, 2012-09-04 at 18:21 +0100, Pedro Alves wrote:
> >> On 09/04/2012 06:17 PM, Steven Rostedt wrote:
> >>> On Tue, 2012-09-04 at 17:40 +0100, Pedro Alves wrote:
> >>>
> >>>> BTW, you can also go a step further and remove the need to close with double }},
> >>>> with something like:
> >>>>
> >>>> #define do_for_each_ftrace_rec(pg, rec)
> >>>> for (pg = ftrace_pages_start, rec = &pg->records[pg->index];
> >>>> pg && rec == &pg->records[pg->index];
> >>>> pg = pg->next)
> >>>> for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
> >>>>
> >>>
> >>> Yeah, but why bother? It's hidden in a macro, and the extra '{ }' shows
> >>> that this is something "special".
> >>
> >> The point of both changes is that there's nothing special in the end
> >> at all. It all just works...
> >>
> >
> > It would still fail on a 'break'. The 'while' macro tells us that it is
> > special, because in the end, it wont work.
>
> Please explain why it would fail on a 'break'.
>

Ah, I missed the condition with the rec == &pg->records[pg->index]. But
if ftrace_pages_start is NULL, the rec = &pg->records[pg->index] will
fault.

You could do something like rec = pg ? &pg->records[pg->index] : NULL,
but IIRC, the comma operator does not guarantee order evaluation. That
is, the compiler is allowed to process "a , b" as "b; a;" and not "a;
b;".

-- Steve


--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 

Thread Tools




All times are GMT. The time now is 10:29 AM.

VBulletin, Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO ©2007, Crawlability, Inc.
Copyright 2007 - 2008, www.linux-archive.org