| Message ID | 1344003788-1417-2-git-send-email-levinsasha928@gmail.com |
|---|---|
| State | Not Applicable, archived |
| Delegated to: | David Miller |
| Headers | show |
Hello, Sasha. On Fri, Aug 03, 2012 at 04:23:02PM +0200, Sasha Levin wrote: > +#define DEFINE_STATIC_HASHTABLE(n, b) \ > + static struct hash_table n = { .bits = (b), \ > + .buckets = { [0 ... ((1 << (b)) - 1)] = HLIST_HEAD_INIT } } What does this "static" mean? > +#define DEFINE_HASHTABLE(n, b) \ > + union { \ > + struct hash_table n; \ > + struct { \ > + size_t bits; \ > + struct hlist_head buckets[1 << (b)]; \ > + } __##n ; \ > + }; Is this supposed to be embedded in struct definition? If so, the name is rather misleading as DEFINE_* is supposed to define and initialize stand-alone constructs. Also, for struct members, simply putting hash entries after struct hash_table should work. Wouldn't using DEFINE_HASHTABLE() for the first macro and DEFINE_HASHTABLE_MEMBER() for the latter be better? > +#define HASH_BITS(name) ((name)->bits) > +#define HASH_SIZE(name) (1 << (HASH_BITS(name))) > + > +__attribute__ ((unused)) Are we using __attribute__((unused)) for functions defined in headers instead of static inline now? If so, why? > +static void hash_init(struct hash_table *ht, size_t bits) > +{ > + size_t i; I would prefer int here but no biggie. > + ht->bits = bits; > + for (i = 0; i < (1 << bits); i++) > + INIT_HLIST_HEAD(&ht->buckets[i]); > +} > + > +static void hash_add(struct hash_table *ht, struct hlist_node *node, long key) > +{ > + hlist_add_head(node, > + &ht->buckets[hash_long((unsigned long)key, HASH_BITS(ht))]); > +} > + > + > +#define hash_get(name, key, type, member, cmp_fn) \ > +({ \ > + struct hlist_node *__node; \ > + typeof(key) __key = key; \ > + type *__obj = NULL; \ > + hlist_for_each_entry(__obj, __node, &(name)->buckets[ \ > + hash_long((unsigned long) __key, \ > + HASH_BITS(name))], member) \ > + if (cmp_fn(__obj, __key)) \ > + break; \ > + __obj; \ > +}) As opposed to using hash_for_each_possible(), how much difference does this make? Is it really worthwhile? Thanks.
Ooh, one more thing. Comments please.
On Fri, 2012-08-03 at 16:23 +0200, Sasha Levin wrote: > This hashtable implementation is using hlist buckets to provide a simple > hashtable to prevent it from getting reimplemented all over the kernel. > > +static void hash_add(struct hash_table *ht, struct hlist_node *node, long key) > +{ > + hlist_add_head(node, > + &ht->buckets[hash_long((unsigned long)key, HASH_BITS(ht))]); > +} > + Why key is a long, casted later to "unsigned long" ? hash_long() is expensive on 64bit arches, and not really needed if key is an u32 from the beginning ( I am referring to your patches 6 & 7 using jhash() ) Maybe you could use a macro, so that we can automatically select hash_32() if key is an u32, and hash_long() for other types. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 08/03/2012 07:15 PM, Tejun Heo wrote: > Hello, Sasha. > > On Fri, Aug 03, 2012 at 04:23:02PM +0200, Sasha Levin wrote: >> +#define DEFINE_STATIC_HASHTABLE(n, b) \ >> + static struct hash_table n = { .bits = (b), \ >> + .buckets = { [0 ... ((1 << (b)) - 1)] = HLIST_HEAD_INIT } } > > What does this "static" mean? > >> +#define DEFINE_HASHTABLE(n, b) \ >> + union { \ >> + struct hash_table n; \ >> + struct { \ >> + size_t bits; \ >> + struct hlist_head buckets[1 << (b)]; \ >> + } __##n ; \ >> + }; > > Is this supposed to be embedded in struct definition? If so, the name > is rather misleading as DEFINE_* is supposed to define and initialize > stand-alone constructs. Also, for struct members, simply putting hash > entries after struct hash_table should work. It would work, but I didn't want to just put them in the union since I feel it's safer to keep them in a separate struct so they won't be used by mistake, > Wouldn't using DEFINE_HASHTABLE() for the first macro and > DEFINE_HASHTABLE_MEMBER() for the latter be better? Indeed that sounds better, will fix. >> +#define HASH_BITS(name) ((name)->bits) >> +#define HASH_SIZE(name) (1 << (HASH_BITS(name))) >> + >> +__attribute__ ((unused)) > > Are we using __attribute__((unused)) for functions defined in headers > instead of static inline now? If so, why? > >> +static void hash_init(struct hash_table *ht, size_t bits) >> +{ >> + size_t i; > > I would prefer int here but no biggie. Just wondering, is there a particular reason behind it? >> + ht->bits = bits; >> + for (i = 0; i < (1 << bits); i++) >> + INIT_HLIST_HEAD(&ht->buckets[i]); >> +} >> + >> +static void hash_add(struct hash_table *ht, struct hlist_node *node, long key) >> +{ >> + hlist_add_head(node, >> + &ht->buckets[hash_long((unsigned long)key, HASH_BITS(ht))]); >> +} >> + >> + >> +#define hash_get(name, key, type, member, cmp_fn) \ >> +({ \ >> + struct hlist_node *__node; \ >> + typeof(key) __key = key; \ >> + type *__obj = NULL; \ >> + hlist_for_each_entry(__obj, __node, &(name)->buckets[ \ >> + hash_long((unsigned long) __key, \ >> + HASH_BITS(name))], member) \ >> + if (cmp_fn(__obj, __key)) \ >> + break; \ >> + __obj; \ >> +}) > > As opposed to using hash_for_each_possible(), how much difference does > this make? Is it really worthwhile? Most of the places I've switched to using this hashtable so far (4 out of 6) are using hash_get(). I think that the code looks cleaner when you an just provide a comparison function instead of implementing the iteration itself. I think hash_for_for_each_possible() is useful if the comparison condition is more complex than a simple comparison of one of the object members with the key - there's no need to force it on all the users. > > Thanks. > -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hello, On Fri, Aug 03, 2012 at 11:19:57PM +0200, Sasha Levin wrote: > > Is this supposed to be embedded in struct definition? If so, the name > > is rather misleading as DEFINE_* is supposed to define and initialize > > stand-alone constructs. Also, for struct members, simply putting hash > > entries after struct hash_table should work. > > It would work, but I didn't want to just put them in the union since > I feel it's safer to keep them in a separate struct so they won't be > used by mistake, Just use ugly enough pre/postfixes. If the user still accesses that, it's the user's fault. > >> +static void hash_init(struct hash_table *ht, size_t bits) > >> +{ > >> + size_t i; > > > > I would prefer int here but no biggie. > > Just wondering, is there a particular reason behind it? It isn't a size and using unsigned when signed suffices seems to cause more headache than helps anything usually due to lack of values to use for exceptional conditions (usually -errno or -1). > > As opposed to using hash_for_each_possible(), how much difference does > > this make? Is it really worthwhile? > > Most of the places I've switched to using this hashtable so far (4 > out of 6) are using hash_get(). I think that the code looks cleaner > when you an just provide a comparison function instead of > implementing the iteration itself. > > I think hash_for_for_each_possible() is useful if the comparison > condition is more complex than a simple comparison of one of the > object members with the key - there's no need to force it on all the > users. I don't know. What's the difference? In terms of LOC, it might even not save any thanks to the extra function definition, right? I don't think it's saving enough complexity to justify a separate rather unusual interface. Thanks.
On 08/03/2012 11:30 PM, Tejun Heo wrote: >> I think hash_for_for_each_possible() is useful if the comparison >> > condition is more complex than a simple comparison of one of the >> > object members with the key - there's no need to force it on all the >> > users. > I don't know. What's the difference? In terms of LOC, it might even > not save any thanks to the extra function definition, right? I don't > think it's saving enough complexity to justify a separate rather > unusual interface. The function definition itself is just a macro, for example: #define MM_SLOTS_HASH_CMP(mm_slot, obj) ((mm_slot)->mm == (obj)) As an alternative, what do you think about simplifying that to be just a 'cond' instead of a function? Something like: hash_get(&mm_slots_hash, mm, struct mm_slot, hash, mm); In that case, the last param ("mm") will get unrolled to a condition like this: if ((obj)->mm == key) Which will be simple and easy for the user. The only reason I want to keep this interface is that most cases I've stumbled so far were easy short comparisons of a struct member with the key, and I don't want to make them more complex than they need to be. I probably will switch hash_get() to use hash_for_each_possible() as well, which will cut down on how hash_get() is a separate case. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 08/03/2012 11:30 PM, Tejun Heo wrote: > Hello, > > On Fri, Aug 03, 2012 at 11:19:57PM +0200, Sasha Levin wrote: >>> Is this supposed to be embedded in struct definition? If so, the name >>> is rather misleading as DEFINE_* is supposed to define and initialize >>> stand-alone constructs. Also, for struct members, simply putting hash >>> entries after struct hash_table should work. >> >> It would work, but I didn't want to just put them in the union since >> I feel it's safer to keep them in a separate struct so they won't be >> used by mistake, > > Just use ugly enough pre/postfixes. If the user still accesses that, > it's the user's fault. I forgot to comment on that one, sorry. If we put hash entries after struct hash_table we don't take the bits field size into account, or did I miss something? -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hello, Sasha. On Fri, Aug 03, 2012 at 11:36:49PM +0200, Sasha Levin wrote: > On 08/03/2012 11:30 PM, Tejun Heo wrote: > The function definition itself is just a macro, for example: > > #define MM_SLOTS_HASH_CMP(mm_slot, obj) ((mm_slot)->mm == (obj)) It seems like it would make things more difficult to follow and error-prone. I'd definitely prefer just using functions. > As an alternative, what do you think about simplifying that to be > just a 'cond' instead of a function? Something like: > > hash_get(&mm_slots_hash, mm, struct mm_slot, hash, mm); > > In that case, the last param ("mm") will get unrolled to a condition like this: > > if ((obj)->mm == key) > > Which will be simple and easy for the user. It seems a bit too magical(tm) to me. ;) > The only reason I want to keep this interface is that most cases > I've stumbled so far were easy short comparisons of a struct member > with the key, and I don't want to make them more complex than they > need to be. I probably will switch hash_get() to use > hash_for_each_possible() as well, which will cut down on how > hash_get() is a separate case. I can understand that but I think the benefit we're talking about is a bit too miniscule to matter and to have two different interfaces. What do others think? Thanks.
Hello, On Fri, Aug 03, 2012 at 11:41:34PM +0200, Sasha Levin wrote: > I forgot to comment on that one, sorry. > > If we put hash entries after struct hash_table we don't take the > bits field size into account, or did I miss something? So, if you do the following, struct { struct { int i; long ar[]; } B; long __ar_storage[32]; } A; It should always be safe to dereference A.B.ar[31]. I'm not sure whether this is something guaranteed by C tho. Maybe compilers are allowed to put members in reverse order but I think we already depend on the above. Thanks.
On 08/03/2012 11:48 PM, Tejun Heo wrote: > Hello, > > On Fri, Aug 03, 2012 at 11:41:34PM +0200, Sasha Levin wrote: >> I forgot to comment on that one, sorry. >> >> If we put hash entries after struct hash_table we don't take the >> bits field size into account, or did I miss something? > > So, if you do the following, > > struct { > struct { > int i; > long ar[]; > } B; > long __ar_storage[32]; > } A; struct A should have been an union, right? > It should always be safe to dereference A.B.ar[31]. I'm not sure > whether this is something guaranteed by C tho. Maybe compilers are > allowed to put members in reverse order but I think we already depend > on the above. why is accessing A.B.ar[31] safe? __ar_storage is only 32*sizeof(long) bytes long, while struct B would need to be 32*sizeof(long) + sizeof(int) bytes long so that A.B.ar[31] access would be safe. > Thanks. > -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hello, On Sat, Aug 04, 2012 at 12:20:02AM +0200, Sasha Levin wrote: > On 08/03/2012 11:48 PM, Tejun Heo wrote: > > On Fri, Aug 03, 2012 at 11:41:34PM +0200, Sasha Levin wrote: > >> I forgot to comment on that one, sorry. > >> > >> If we put hash entries after struct hash_table we don't take the > >> bits field size into account, or did I miss something? > > > > So, if you do the following, > > > > struct { > > struct { > > int i; > > long ar[]; > > } B; > > long __ar_storage[32]; > > } A; > > struct A should have been an union, right? I actually meant an enclosing struct. When you're defining a struct member, simply putting the storage after a struct with var array should be good enough. If that doesn't work, quite a few things in the kernel will break. Thanks.
On 08/04/2012 12:23 AM, Tejun Heo wrote: > Hello, > > On Sat, Aug 04, 2012 at 12:20:02AM +0200, Sasha Levin wrote: >> On 08/03/2012 11:48 PM, Tejun Heo wrote: >>> On Fri, Aug 03, 2012 at 11:41:34PM +0200, Sasha Levin wrote: >>>> I forgot to comment on that one, sorry. >>>> >>>> If we put hash entries after struct hash_table we don't take the >>>> bits field size into account, or did I miss something? >>> >>> So, if you do the following, >>> >>> struct { >>> struct { >>> int i; >>> long ar[]; >>> } B; >>> long __ar_storage[32]; >>> } A; >> >> struct A should have been an union, right? > > I actually meant an enclosing struct. When you're defining a struct > member, simply putting the storage after a struct with var array > should be good enough. If that doesn't work, quite a few things in > the kernel will break. Ah, I see, I've missed that part. Thanks! > Thanks. > -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Aug 3, 2012 at 3:23 PM, Tejun Heo <tj@kernel.org> wrote: > > I actually meant an enclosing struct. When you're defining a struct > member, simply putting the storage after a struct with var array > should be good enough. If that doesn't work, quite a few things in > the kernel will break. The unsigned member of a struct has to be the last one, so your struct won't work. Linus -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Aug 03, 2012 at 03:29:10PM -0700, Linus Torvalds wrote: > On Fri, Aug 3, 2012 at 3:23 PM, Tejun Heo <tj@kernel.org> wrote: > > > > I actually meant an enclosing struct. When you're defining a struct > > member, simply putting the storage after a struct with var array > > should be good enough. If that doesn't work, quite a few things in > > the kernel will break. > > The unsigned member of a struct has to be the last one, so your struct > won't work. I suppose you mean unsized. I remember this working. Maybe I'm confusing it with zero-sized array. Hmm... gcc doesn't complain about the following. --std=c99 seems happy too. #include <stdio.h> struct A { int i; long ar[]; }; struct B { struct A a; long ar_storage[32]; }; int main(void) { printf("sizeof(A)=%zd sizeof(B)=%zd\n", sizeof(struct A), sizeof(struct B)); return 0; } $ ./a.out sizeof(A)=8 sizeof(B)=264
On Fri, Aug 3, 2012 at 3:36 PM, Tejun Heo <tj@kernel.org> wrote: > > I suppose you mean unsized. I remember this working. Maybe I'm > confusing it with zero-sized array. Hmm... gcc doesn't complain about > the following. --std=c99 seems happy too. Ok, I'm surprised, but maybe it's supposed to work if you do it inside another struct like that, exactly so that you can preallocate things.. Or maybe it's just a gcc bug. I do think this all is way hackier than Sasha's original simple code that didn't need these kinds of games, and didn't need a size member at all. I really think all the extra complexity and overhead is just *bad*. The first simple version was much nicer and likely generated better code too. Linus -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hi Linus, On 08/04/2012 01:47 AM, Linus Torvalds wrote: > Or maybe it's just a gcc bug. I do think this all is way hackier than > Sasha's original simple code that didn't need these kinds of games, > and didn't need a size member at all. > > I really think all the extra complexity and overhead is just *bad*. > The first simple version was much nicer and likely generated better > code too. The problem with that code was that it doesn't work with dynamically allocated hashtables, or hashtables that grow/shrink. The alternative to going down this path, is going back to the old code and saying that it only works for the simple case, and if you're interested in something more complex it should have it's own different implementation. Does it make sense? We'll keep the simple & common case simple, and let anyone who needs something more complex than this write it as an extension? -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hello, On Fri, Aug 03, 2012 at 04:47:47PM -0700, Linus Torvalds wrote: > On Fri, Aug 3, 2012 at 3:36 PM, Tejun Heo <tj@kernel.org> wrote: > > > > I suppose you mean unsized. I remember this working. Maybe I'm > > confusing it with zero-sized array. Hmm... gcc doesn't complain about > > the following. --std=c99 seems happy too. > > Ok, I'm surprised, but maybe it's supposed to work if you do it inside > another struct like that, exactly so that you can preallocate things.. Yeah, I think the rule is var array should be the last member of any given struct definition. Once a struct is defined, its alignment and size are fixed and it behaves like any other struct. > Or maybe it's just a gcc bug. I do think this all is way hackier than > Sasha's original simple code that didn't need these kinds of games, > and didn't need a size member at all. > > I really think all the extra complexity and overhead is just *bad*. > The first simple version was much nicer and likely generated better > code too. The size member could have performance impact in extreme cases. If we're looking for something simple & fast, maybe just pass in @size as argument and be done with it? Thanks.
On Fri, Aug 3, 2012 at 5:03 PM, Sasha Levin <levinsasha928@gmail.com> wrote: > > The problem with that code was that it doesn't work with dynamically allocated hashtables, or hashtables that grow/shrink. Sure. But once you have that kind of complexity, why would you care about the trivial cases? Linus -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 08/04/2012 02:05 AM, Linus Torvalds wrote: > On Fri, Aug 3, 2012 at 5:03 PM, Sasha Levin <levinsasha928@gmail.com> wrote: >> >> The problem with that code was that it doesn't work with dynamically allocated hashtables, or hashtables that grow/shrink. > > Sure. But once you have that kind of complexity, why would you care > about the trivial cases? Because there are far more trivial cases than complex ones - I've counted 50+ of these "trivial" cases. None of them need the complexity we're trying to deal with at the moment. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h new file mode 100644 index 0000000..b004cf7 --- /dev/null +++ b/include/linux/hashtable.h @@ -0,0 +1,75 @@ +#ifndef _LINUX_HASHTABLE_H +#define _LINUX_HASHTABLE_H + +#include <linux/list.h> +#include <linux/types.h> +#include <linux/kernel.h> +#include <linux/hash.h> + +struct hash_table { + size_t bits; + struct hlist_head buckets[]; +}; + +#define DEFINE_STATIC_HASHTABLE(n, b) \ + static struct hash_table n = { .bits = (b), \ + .buckets = { [0 ... ((1 << (b)) - 1)] = HLIST_HEAD_INIT } } + +#define DEFINE_HASHTABLE(n, b) \ + union { \ + struct hash_table n; \ + struct { \ + size_t bits; \ + struct hlist_head buckets[1 << (b)]; \ + } __##n ; \ + }; + +#define HASH_BITS(name) ((name)->bits) +#define HASH_SIZE(name) (1 << (HASH_BITS(name))) + +__attribute__ ((unused)) +static void hash_init(struct hash_table *ht, size_t bits) +{ + size_t i; + + ht->bits = bits; + for (i = 0; i < (1 << bits); i++) + INIT_HLIST_HEAD(&ht->buckets[i]); +} + +static void hash_add(struct hash_table *ht, struct hlist_node *node, long key) +{ + hlist_add_head(node, + &ht->buckets[hash_long((unsigned long)key, HASH_BITS(ht))]); +} + + +#define hash_get(name, key, type, member, cmp_fn) \ +({ \ + struct hlist_node *__node; \ + typeof(key) __key = key; \ + type *__obj = NULL; \ + hlist_for_each_entry(__obj, __node, &(name)->buckets[ \ + hash_long((unsigned long) __key, \ + HASH_BITS(name))], member) \ + if (cmp_fn(__obj, __key)) \ + break; \ + __obj; \ +}) + +__attribute__ ((unused)) +static void hash_del(struct hlist_node *node) +{ + hlist_del_init(node); +} + +#define hash_for_each(bkt, node, name, obj, member) \ + for (bkt = 0; bkt < HASH_SIZE(name); bkt++) \ + hlist_for_each_entry(obj, node, &(name)->buckets[i], member) + +#define hash_for_each_possible(name, node, obj, member, key) \ + hlist_for_each_entry(obj, node, \ + &(name)->buckets[hash_long((unsigned long) key, \ + HASH_BITS(name))], member) + +#endif
This hashtable implementation is using hlist buckets to provide a simple hashtable to prevent it from getting reimplemented all over the kernel. Signed-off-by: Sasha Levin <levinsasha928@gmail.com> --- include/linux/hashtable.h | 75 +++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 75 insertions(+), 0 deletions(-) create mode 100644 include/linux/hashtable.h