Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 10:23 PM, Linus Torvalds wrote: > On Tue, Oct 30, 2012 at 6:36 PM, Sasha Levin wrote: >> >> I can either rebase that on top of mainline, or we can ask maintainers >> to take it to their own trees if you take only 01/16 into mainline. >> What would you prefer? > > I don't really care deeply. The only reason to merge it now would be > to avoid any pain with it during the next merge window. Just taking > 01/16 might be the sanest way to do that, then the rest can trickle in > independently at their own leisure. Okay, I'll keep working on converting everything else as soon as 01/16 makes it in your tree. Thanks, Sasha -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 10:23 PM, Linus Torvalds torva...@linux-foundation.org wrote: On Tue, Oct 30, 2012 at 6:36 PM, Sasha Levin levinsasha...@gmail.com wrote: I can either rebase that on top of mainline, or we can ask maintainers to take it to their own trees if you take only 01/16 into mainline. What would you prefer? I don't really care deeply. The only reason to merge it now would be to avoid any pain with it during the next merge window. Just taking 01/16 might be the sanest way to do that, then the rest can trickle in independently at their own leisure. Okay, I'll keep working on converting everything else as soon as 01/16 makes it in your tree. Thanks, Sasha -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
RE: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
> > > On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote:
> > >> +/* 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);
> > >> \
> > >> +})
> > >
> > > Doesn't the above fit in 80 column. Why is it broken into multiple
> > > lines? Also, you probably want () around at least @val. In general,
> > > it's a good idea to add () around any macro argument to avoid nasty
> > > surprises.
> >
> > It was broken to multiple lines because it looks nicer that way (IMO).
> >
> > If we wrap it with () it's going to go over 80, so it's going to stay
> > broken down either way :)
>
> ({ \
> sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits); \
> })
>
> Is the better way to go. We are C programmers, we like to see the ?: on
> a single line if possible. The way you have it, looks like three
> statements run consecutively.
To add some more colour (not color):
In any case, this is a normal C #define, it doesn't need the {}.
So it can just be:
# define hash_min(val, bits) \
(sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))
I don't think that s/val/(val)/g and s/bits/(bits)/g are needed
because the tokens are already ',' separated.
I do actually wonder how many of these hash lists should be replaced
with some kind of tree structure in order to get O(log(n)) searches.
After all hashing is still O(n).
(apologies if I mean o(n) not O(n) - it's a long time since I did
my maths degree!)
David
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
RE: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote:
+/* 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);
\
+})
Doesn't the above fit in 80 column. Why is it broken into multiple
lines? Also, you probably want () around at least @val. In general,
it's a good idea to add () around any macro argument to avoid nasty
surprises.
It was broken to multiple lines because it looks nicer that way (IMO).
If we wrap it with () it's going to go over 80, so it's going to stay
broken down either way :)
({ \
sizeof(val) = 4 ? hash_32(val, bits) : hash_long(val, bits); \
})
Is the better way to go. We are C programmers, we like to see the ?: on
a single line if possible. The way you have it, looks like three
statements run consecutively.
To add some more colour (not color):
In any case, this is a normal C #define, it doesn't need the {}.
So it can just be:
# define hash_min(val, bits) \
(sizeof(val) = 4 ? hash_32(val, bits) : hash_long(val, bits))
I don't think that s/val/(val)/g and s/bits/(bits)/g are needed
because the tokens are already ',' separated.
I do actually wonder how many of these hash lists should be replaced
with some kind of tree structure in order to get O(log(n)) searches.
After all hashing is still O(n).
(apologies if I mean o(n) not O(n) - it's a long time since I did
my maths degree!)
David
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 8:24 PM, Al Viro wrote: > > Oh, well... there go my blackmail plans ;-) Seriously, though, I'm at loss > regarding several embedded architectures - arch/score, in particular, > seems to be completely orphaned. Don't worry about it. Do a best-effort, and if nobody ever reacts about some odd-ball architecture, whatever. We won't start deleting architectures over something like this, but it might be another sign down the road that some arch code can be removed entirely. So it's not arch/score I'd worry about. It's all the *other* architectures.. Linus -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 07:48:19PM -0700, Linus Torvalds wrote: > On Tue, Oct 30, 2012 at 7:24 PM, Al Viro wrote: > > > > BTW, how serious have you been back at KS when you were talking about > > pull requests killing a thousand of lines of code being acceptable > > at any point in the cycle? > > Well... I'm absolutely a lot more open to pull requests that kill code > than not, but I have to admit to being a bit more worried about stuff > like your execve/fork patches that touch very low-level code. > > So I think I'll punt that for 3.8 anyway. Oh, well... there go my blackmail plans ;-) Seriously, though, I'm at loss regarding several embedded architectures - arch/score, in particular, seems to be completely orphaned. As far as I can see, it's * abandoned by hw vendor (seems like they were planning to push it game consoles, but that was just before the recession, and...) * abandoned by primary maintainer, who isn't employed by said hw vendor anymore, so his old address had been bouncy for several years. He had bothered to update it in gcc tree, but hadn't been active there either for almost as long. And new address in gcc tree is of form +g...@gmail.com, so using it for kernel-related mail would seem to be a lousy idea. * the second maintainer seems to be nearly MIA as well - all I can find is Acked-by on one commit. Cc'ed on the kernel_execve() thread, but... no signs of life whatsoever. * a lot of asm glue is in "apparently never worked" state, starting with ptrace hookup (it's clearly started its life as a mips clone, but uses different registers for passing return value, etc. TIF_SYSCALL_TRACE side of that thing still assumes MIPS ABI *and* is suffering obvious bitrot) Sigh... -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 7:24 PM, Al Viro wrote: > > BTW, how serious have you been back at KS when you were talking about > pull requests killing a thousand of lines of code being acceptable > at any point in the cycle? Well... I'm absolutely a lot more open to pull requests that kill code than not, but I have to admit to being a bit more worried about stuff like your execve/fork patches that touch very low-level code. So I think I'll punt that for 3.8 anyway. Linus -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 06:25:46PM -0700, Linus Torvalds wrote: > But whatever. This series has gotten way too much bike-shedding > anyway. I think it should just be applied, since it does remove lines > of code overall. I'd even possibly apply it to mainline, but it seems > to be against linux-next. BTW, how serious have you been back at KS when you were talking about pull requests killing a thousand of lines of code being acceptable at any point in the cycle? Because right now I'm sitting on a pile that removes 2-3 times as much (~-2KLoC for stuff that got considerable testing for most of the architectures, -3KLoC if I include fork/clone/vfork unification series) and seeing how maintainers of a bunch of embedded architectures seem to be MIA... The idea of saying "screw them" and sending a pull request becomes more and more tempting every day ;-) -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 6:36 PM, Sasha Levin wrote: > > I can either rebase that on top of mainline, or we can ask maintainers > to take it to their own trees if you take only 01/16 into mainline. > What would you prefer? I don't really care deeply. The only reason to merge it now would be to avoid any pain with it during the next merge window. Just taking 01/16 might be the sanest way to do that, then the rest can trickle in independently at their own leisure. Linus -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
Hi Linus, > But whatever. This series has gotten way too much bike-shedding > anyway. I think it should just be applied, since it does remove lines > of code overall. I'd even possibly apply it to mainline, but it seems > to be against linux-next. Yup, I switched to using -next because I've been running my trinity/KVM tools tests with it. I can either rebase that on top of mainline, or we can ask maintainers to take it to their own trees if you take only 01/16 into mainline. What would you prefer? Thanks, Sasha -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, 2012-10-30 at 18:25 -0700, Linus Torvalds wrote:
> On Tue, Oct 30, 2012 at 6:16 PM, Steven Rostedt wrote:
> >
> > ({\
> > sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits); \
> > })
> >
> > Is the better way to go. We are C programmers, we like to see the ?: on
> > a single line if possible. The way you have it, looks like three
> > statements run consecutively.
>
> If we're C programmers, why use the non-standard statement-expression
> at all? And split it onto three lines when it's just a single one?
I like the blue color over the pink. Anyway, I was just expressing an
opinion and really didn't care if it was changed or not.
>
> But whatever. This series has gotten way too much bike-shedding
> anyway. I think it should just be applied, since it does remove lines
> of code overall. I'd even possibly apply it to mainline, but it seems
> to be against linux-next.
I would think this change is a bit too big for an -rc4 release, but
you're the boss. I've already given my ack for my code that this set
touches. Let it go to Stephen's repo then.
-- Steve
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 6:16 PM, Steven Rostedt wrote:
>
> ({\
> sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits); \
> })
>
> Is the better way to go. We are C programmers, we like to see the ?: on
> a single line if possible. The way you have it, looks like three
> statements run consecutively.
If we're C programmers, why use the non-standard statement-expression
at all? And split it onto three lines when it's just a single one?
But whatever. This series has gotten way too much bike-shedding
anyway. I think it should just be applied, since it does remove lines
of code overall. I'd even possibly apply it to mainline, but it seems
to be against linux-next.
Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, 2012-10-30 at 20:33 -0400, Sasha Levin wrote:
> On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo wrote:
> > Hello,
> >
> > Just some nitpicks.
> >
> > On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote:
> >> +/* 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);
> >>\
> >> +})
> >
> > Doesn't the above fit in 80 column. Why is it broken into multiple
> > lines? Also, you probably want () around at least @val. In general,
> > it's a good idea to add () around any macro argument to avoid nasty
> > surprises.
>
> It was broken to multiple lines because it looks nicer that way (IMO).
>
> If we wrap it with () it's going to go over 80, so it's going to stay
> broken down either way :)
({\
sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits); \
})
Is the better way to go. We are C programmers, we like to see the ?: on
a single line if possible. The way you have it, looks like three
statements run consecutively.
-- Steve
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 8:51 PM, Jim Rees wrote:
> Sasha Levin wrote:
>
> On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo wrote:
> > Hello,
> >
> > Just some nitpicks.
> >
> > On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote:
> >> +/* 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);
> \
> >> +})
> >
> > Doesn't the above fit in 80 column. Why is it broken into multiple
> > lines? Also, you probably want () around at least @val. In general,
> > it's a good idea to add () around any macro argument to avoid nasty
> > surprises.
>
> It was broken to multiple lines because it looks nicer that way (IMO).
>
> If we wrap it with () it's going to go over 80, so it's going to stay
> broken down either way :)
>
> I would prefer the body be all on one line too. But shouldn't this be a
> static inline function?
We want sizeof(val), which wouldn't work in a static inline. We can
either wrap a static inline __hash_min() with a macro and pass that
size to it, but that's quite an overkill here, or we can add a size
parameter to hash_min(), but it would look awkward considering how
hash_32()/hash_64()/hash_long() look like.
Thanks,
Sasha
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
Sasha Levin wrote:
On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo wrote:
> Hello,
>
> Just some nitpicks.
>
> On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote:
>> +/* 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);
\
>> +})
>
> Doesn't the above fit in 80 column. Why is it broken into multiple
> lines? Also, you probably want () around at least @val. In general,
> it's a good idea to add () around any macro argument to avoid nasty
> surprises.
It was broken to multiple lines because it looks nicer that way (IMO).
If we wrap it with () it's going to go over 80, so it's going to stay
broken down either way :)
I would prefer the body be all on one line too. But shouldn't this be a
static inline function?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo wrote:
> Hello,
>
> Just some nitpicks.
>
> On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote:
>> +/* 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);
>> \
>> +})
>
> Doesn't the above fit in 80 column. Why is it broken into multiple
> lines? Also, you probably want () around at least @val. In general,
> it's a good idea to add () around any macro argument to avoid nasty
> surprises.
It was broken to multiple lines because it looks nicer that way (IMO).
If we wrap it with () it's going to go over 80, so it's going to stay
broken down either way :)
Thanks,
Sasha
> Looks good to me otherwise.
>
> Reviewed-by: Tejun Heo
>
> Thanks.
>
> --
> tejun
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
Hello,
Just some nitpicks.
On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote:
> +/* 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);
> \
> +})
Doesn't the above fit in 80 column. Why is it broken into multiple
lines? Also, you probably want () around at least @val. In general,
it's a good idea to add () around any macro argument to avoid nasty
surprises.
Looks good to me otherwise.
Reviewed-by: Tejun Heo
Thanks.
--
tejun
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
* Sasha Levin (levinsasha...@gmail.com) wrote:
> 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
Reviewed-by: Mathieu Desnoyers
> ---
>
> Changes from v8:
>
> - Addressed comments from Tejun Heo and Mathieu Desnoyers.
>
>
> include/linux/hashtable.h | 196
> ++
> 1 file changed, 196 insertions(+)
> create mode 100644 include/linux/hashtable.h
>
> diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
> new file mode 100644
> index 000..3c1a9cb
> --- /dev/null
> +++ b/include/linux/hashtable.h
> @@ -0,0 +1,196 @@
> +/*
> + * Statically sized hash table implementation
> + * (C) 2012 Sasha Levin
> + */
> +
> +#ifndef _LINUX_HASHTABLE_H
> +#define _LINUX_HASHTABLE_H
> +
> +#include
> +#include
> +#include
> +#include
> +#include
> +
> +#define DEFINE_HASHTABLE(name, bits)
> \
> + struct hlist_head name[1 << (bits)] =
> \
> + { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
> +
> +#define DECLARE_HASHTABLE(name, bits)
> \
> + struct hlist_head name[1 << (bits)]
> +
> +#define HASH_SIZE(name) (ARRAY_SIZE(name))
> +#define HASH_BITS(name) ilog2(HASH_SIZE(name))
> +
> +/* 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);
> \
> +})
> +
> +static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
> +{
> + unsigned int i;
> +
> + for (i = 0; i < sz; i++)
> + INIT_HLIST_HEAD([i]);
> +}
> +
> +/**
> + * hash_init - initialize a hash table
> + * @hashtable: hashtable to be initialized
> + *
> + * Calculates the size of the hashtable from the given parameter, otherwise
> + * same as hash_init_size.
> + *
> + * This has to be a macro since HASH_BITS() will not work on pointers since
> + * it calculates the size during preprocessing.
> + */
> +#define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))
> +
> +/**
> + * hash_add - add an object to a hashtable
> + * @hashtable: hashtable to add to
> + * @node: the hlist_node of the object to be added
> + * @key: the key of the object to be added
> + */
> +#define hash_add(hashtable, node, key)
> \
> + hlist_add_head(node, [hash_min(key, HASH_BITS(hashtable))])
> +
> +/**
> + * hash_add_rcu - add an object to a rcu enabled hashtable
> + * @hashtable: hashtable to add to
> + * @node: the hlist_node of the object to be added
> + * @key: the key of the object to be added
> + */
> +#define hash_add_rcu(hashtable, node, key)
> \
> + hlist_add_head_rcu(node, [hash_min(key,
> HASH_BITS(hashtable))])
> +
> +/**
> + * hash_hashed - check whether an object is in any hashtable
> + * @node: the hlist_node of the object to be checked
> + */
> +static inline bool hash_hashed(struct hlist_node *node)
> +{
> + return !hlist_unhashed(node);
> +}
> +
> +static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz)
> +{
> + unsigned int i;
> +
> + for (i = 0; i < sz; i++)
> + if (!hlist_empty([i]))
> + return false;
> +
> + return true;
> +}
> +
> +/**
> + * hash_empty - check whether a hashtable is empty
> + * @hashtable: hashtable to check
> + *
> + * This has to be a macro since HASH_BITS() will not work on pointers since
> + * it calculates the size during preprocessing.
> + */
> +#define hash_empty(hashtable) __hash_empty(hashtable, HASH_SIZE(hashtable))
> +
> +/**
> + * hash_del - remove an object from a hashtable
> + * @node: 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: hlist_node of the object to remove
> + */
> +static inline void hash_del_rcu(struct hlist_node *node)
> +{
> + hlist_del_init_rcu(node);
> +}
> +
> +/**
> + * hash_for_each - iterate over a hashtable
> + * @name: hashtable to iterate
> + * @bkt: integer to use as bucket loop cursor
> + * @node: the list_head to use as a loop cursor for each entry
> + * @obj: the type * to use as a loop cursor for each entry
> + * @member: the name of the hlist_node within the struct
> + */
> +#define hash_for_each(name, bkt, node, obj, member)
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
* Sasha Levin (levinsasha...@gmail.com) wrote:
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 levinsasha...@gmail.com
Reviewed-by: Mathieu Desnoyers mathieu.desnoy...@efficios.com
---
Changes from v8:
- Addressed comments from Tejun Heo and Mathieu Desnoyers.
include/linux/hashtable.h | 196
++
1 file changed, 196 insertions(+)
create mode 100644 include/linux/hashtable.h
diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
new file mode 100644
index 000..3c1a9cb
--- /dev/null
+++ b/include/linux/hashtable.h
@@ -0,0 +1,196 @@
+/*
+ * Statically sized hash table implementation
+ * (C) 2012 Sasha Levin levinsasha...@gmail.com
+ */
+
+#ifndef _LINUX_HASHTABLE_H
+#define _LINUX_HASHTABLE_H
+
+#include linux/list.h
+#include linux/types.h
+#include linux/kernel.h
+#include linux/hash.h
+#include linux/rculist.h
+
+#define DEFINE_HASHTABLE(name, bits)
\
+ struct hlist_head name[1 (bits)] =
\
+ { [0 ... ((1 (bits)) - 1)] = HLIST_HEAD_INIT }
+
+#define DECLARE_HASHTABLE(name, bits)
\
+ struct hlist_head name[1 (bits)]
+
+#define HASH_SIZE(name) (ARRAY_SIZE(name))
+#define HASH_BITS(name) ilog2(HASH_SIZE(name))
+
+/* 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);
\
+})
+
+static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
+{
+ unsigned int i;
+
+ for (i = 0; i sz; i++)
+ INIT_HLIST_HEAD(ht[i]);
+}
+
+/**
+ * hash_init - initialize a hash table
+ * @hashtable: hashtable to be initialized
+ *
+ * Calculates the size of the hashtable from the given parameter, otherwise
+ * same as hash_init_size.
+ *
+ * This has to be a macro since HASH_BITS() will not work on pointers since
+ * it calculates the size during preprocessing.
+ */
+#define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))
+
+/**
+ * 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)
\
+ hlist_add_head(node, hashtable[hash_min(key, HASH_BITS(hashtable))])
+
+/**
+ * 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)
\
+ hlist_add_head_rcu(node, hashtable[hash_min(key,
HASH_BITS(hashtable))])
+
+/**
+ * hash_hashed - check whether an object is in any hashtable
+ * @node: the struct hlist_node of the object to be checked
+ */
+static inline bool hash_hashed(struct hlist_node *node)
+{
+ return !hlist_unhashed(node);
+}
+
+static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz)
+{
+ unsigned int i;
+
+ for (i = 0; i sz; i++)
+ if (!hlist_empty(ht[i]))
+ return false;
+
+ return true;
+}
+
+/**
+ * hash_empty - check whether a hashtable is empty
+ * @hashtable: hashtable to check
+ *
+ * This has to be a macro since HASH_BITS() will not work on pointers since
+ * it calculates the size during preprocessing.
+ */
+#define hash_empty(hashtable) __hash_empty(hashtable, HASH_SIZE(hashtable))
+
+/**
+ * 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);
+}
+
+/**
+ * hash_for_each - iterate over a hashtable
+ * @name: hashtable to iterate
+ * @bkt: integer to use as bucket loop cursor
+ * @node: the struct list_head to use as a loop cursor for each entry
+ * @obj: the type * to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ */
+#define hash_for_each(name, bkt, node,
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
Hello,
Just some nitpicks.
On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote:
+/* 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);
\
+})
Doesn't the above fit in 80 column. Why is it broken into multiple
lines? Also, you probably want () around at least @val. In general,
it's a good idea to add () around any macro argument to avoid nasty
surprises.
Looks good to me otherwise.
Reviewed-by: Tejun Heo t...@kernel.org
Thanks.
--
tejun
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo t...@kernel.org wrote:
Hello,
Just some nitpicks.
On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote:
+/* 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);
\
+})
Doesn't the above fit in 80 column. Why is it broken into multiple
lines? Also, you probably want () around at least @val. In general,
it's a good idea to add () around any macro argument to avoid nasty
surprises.
It was broken to multiple lines because it looks nicer that way (IMO).
If we wrap it with () it's going to go over 80, so it's going to stay
broken down either way :)
Thanks,
Sasha
Looks good to me otherwise.
Reviewed-by: Tejun Heo t...@kernel.org
Thanks.
--
tejun
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
Sasha Levin wrote:
On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo t...@kernel.org wrote:
Hello,
Just some nitpicks.
On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote:
+/* 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);
\
+})
Doesn't the above fit in 80 column. Why is it broken into multiple
lines? Also, you probably want () around at least @val. In general,
it's a good idea to add () around any macro argument to avoid nasty
surprises.
It was broken to multiple lines because it looks nicer that way (IMO).
If we wrap it with () it's going to go over 80, so it's going to stay
broken down either way :)
I would prefer the body be all on one line too. But shouldn't this be a
static inline function?
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 8:51 PM, Jim Rees r...@umich.edu wrote:
Sasha Levin wrote:
On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo t...@kernel.org wrote:
Hello,
Just some nitpicks.
On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote:
+/* 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);
\
+})
Doesn't the above fit in 80 column. Why is it broken into multiple
lines? Also, you probably want () around at least @val. In general,
it's a good idea to add () around any macro argument to avoid nasty
surprises.
It was broken to multiple lines because it looks nicer that way (IMO).
If we wrap it with () it's going to go over 80, so it's going to stay
broken down either way :)
I would prefer the body be all on one line too. But shouldn't this be a
static inline function?
We want sizeof(val), which wouldn't work in a static inline. We can
either wrap a static inline __hash_min() with a macro and pass that
size to it, but that's quite an overkill here, or we can add a size
parameter to hash_min(), but it would look awkward considering how
hash_32()/hash_64()/hash_long() look like.
Thanks,
Sasha
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, 2012-10-30 at 20:33 -0400, Sasha Levin wrote:
On Tue, Oct 30, 2012 at 5:42 PM, Tejun Heo t...@kernel.org wrote:
Hello,
Just some nitpicks.
On Tue, Oct 30, 2012 at 02:45:57PM -0400, Sasha Levin wrote:
+/* 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);
\
+})
Doesn't the above fit in 80 column. Why is it broken into multiple
lines? Also, you probably want () around at least @val. In general,
it's a good idea to add () around any macro argument to avoid nasty
surprises.
It was broken to multiple lines because it looks nicer that way (IMO).
If we wrap it with () it's going to go over 80, so it's going to stay
broken down either way :)
({\
sizeof(val) = 4 ? hash_32(val, bits) : hash_long(val, bits); \
})
Is the better way to go. We are C programmers, we like to see the ?: on
a single line if possible. The way you have it, looks like three
statements run consecutively.
-- Steve
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 6:16 PM, Steven Rostedt rost...@goodmis.org wrote:
({\
sizeof(val) = 4 ? hash_32(val, bits) : hash_long(val, bits); \
})
Is the better way to go. We are C programmers, we like to see the ?: on
a single line if possible. The way you have it, looks like three
statements run consecutively.
If we're C programmers, why use the non-standard statement-expression
at all? And split it onto three lines when it's just a single one?
But whatever. This series has gotten way too much bike-shedding
anyway. I think it should just be applied, since it does remove lines
of code overall. I'd even possibly apply it to mainline, but it seems
to be against linux-next.
Linus
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, 2012-10-30 at 18:25 -0700, Linus Torvalds wrote:
On Tue, Oct 30, 2012 at 6:16 PM, Steven Rostedt rost...@goodmis.org wrote:
({\
sizeof(val) = 4 ? hash_32(val, bits) : hash_long(val, bits); \
})
Is the better way to go. We are C programmers, we like to see the ?: on
a single line if possible. The way you have it, looks like three
statements run consecutively.
If we're C programmers, why use the non-standard statement-expression
at all? And split it onto three lines when it's just a single one?
I like the blue color over the pink. Anyway, I was just expressing an
opinion and really didn't care if it was changed or not.
But whatever. This series has gotten way too much bike-shedding
anyway. I think it should just be applied, since it does remove lines
of code overall. I'd even possibly apply it to mainline, but it seems
to be against linux-next.
I would think this change is a bit too big for an -rc4 release, but
you're the boss. I've already given my ack for my code that this set
touches. Let it go to Stephen's repo then.
-- Steve
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
Hi Linus, But whatever. This series has gotten way too much bike-shedding anyway. I think it should just be applied, since it does remove lines of code overall. I'd even possibly apply it to mainline, but it seems to be against linux-next. Yup, I switched to using -next because I've been running my trinity/KVM tools tests with it. I can either rebase that on top of mainline, or we can ask maintainers to take it to their own trees if you take only 01/16 into mainline. What would you prefer? Thanks, Sasha -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 6:36 PM, Sasha Levin levinsasha...@gmail.com wrote: I can either rebase that on top of mainline, or we can ask maintainers to take it to their own trees if you take only 01/16 into mainline. What would you prefer? I don't really care deeply. The only reason to merge it now would be to avoid any pain with it during the next merge window. Just taking 01/16 might be the sanest way to do that, then the rest can trickle in independently at their own leisure. Linus -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 06:25:46PM -0700, Linus Torvalds wrote: But whatever. This series has gotten way too much bike-shedding anyway. I think it should just be applied, since it does remove lines of code overall. I'd even possibly apply it to mainline, but it seems to be against linux-next. BTW, how serious have you been back at KS when you were talking about pull requests killing a thousand of lines of code being acceptable at any point in the cycle? Because right now I'm sitting on a pile that removes 2-3 times as much (~-2KLoC for stuff that got considerable testing for most of the architectures, -3KLoC if I include fork/clone/vfork unification series) and seeing how maintainers of a bunch of embedded architectures seem to be MIA... The idea of saying screw them and sending a pull request becomes more and more tempting every day ;-) -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 7:24 PM, Al Viro v...@zeniv.linux.org.uk wrote: BTW, how serious have you been back at KS when you were talking about pull requests killing a thousand of lines of code being acceptable at any point in the cycle? Well... I'm absolutely a lot more open to pull requests that kill code than not, but I have to admit to being a bit more worried about stuff like your execve/fork patches that touch very low-level code. So I think I'll punt that for 3.8 anyway. Linus -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 07:48:19PM -0700, Linus Torvalds wrote: On Tue, Oct 30, 2012 at 7:24 PM, Al Viro v...@zeniv.linux.org.uk wrote: BTW, how serious have you been back at KS when you were talking about pull requests killing a thousand of lines of code being acceptable at any point in the cycle? Well... I'm absolutely a lot more open to pull requests that kill code than not, but I have to admit to being a bit more worried about stuff like your execve/fork patches that touch very low-level code. So I think I'll punt that for 3.8 anyway. Oh, well... there go my blackmail plans ;-) Seriously, though, I'm at loss regarding several embedded architectures - arch/score, in particular, seems to be completely orphaned. As far as I can see, it's * abandoned by hw vendor (seems like they were planning to push it game consoles, but that was just before the recession, and...) * abandoned by primary maintainer, who isn't employed by said hw vendor anymore, so his old address had been bouncy for several years. He had bothered to update it in gcc tree, but hadn't been active there either for almost as long. And new address in gcc tree is of form name+g...@gmail.com, so using it for kernel-related mail would seem to be a lousy idea. * the second maintainer seems to be nearly MIA as well - all I can find is Acked-by on one commit. Cc'ed on the kernel_execve() thread, but... no signs of life whatsoever. * a lot of asm glue is in apparently never worked state, starting with ptrace hookup (it's clearly started its life as a mips clone, but uses different registers for passing return value, etc. TIF_SYSCALL_TRACE side of that thing still assumes MIPS ABI *and* is suffering obvious bitrot) Sigh... -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v8 01/16] hashtable: introduce a small and naive hashtable
On Tue, Oct 30, 2012 at 8:24 PM, Al Viro v...@zeniv.linux.org.uk wrote: Oh, well... there go my blackmail plans ;-) Seriously, though, I'm at loss regarding several embedded architectures - arch/score, in particular, seems to be completely orphaned. Don't worry about it. Do a best-effort, and if nobody ever reacts about some odd-ball architecture, whatever. We won't start deleting architectures over something like this, but it might be another sign down the road that some arch code can be removed entirely. So it's not arch/score I'd worry about. It's all the *other* architectures.. Linus -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
