[RFC 0/4] generic hashtable implementation

[RFC 0/4] generic hashtable implementation

[Sasha Levin]

There are quite a few places in the kernel which implement a hashtable
in a very similar way. Instead of having implementations of a hashtable
all over the kernel, we can re-use the code.

This patch series introduces a very simple hashtable implementation, and
modifies three (random) modules to use it. I've limited it to 3 only
so that it would be easy to review and modify, and to show that even
at this number we already eliminate a big amount of duplicated code.

If this basic hashtable looks ok, future code will include:

 - RCU support
 - Self locking (list_bl?)
 - Converting more code to use the hashtable


Sasha Levin (4):
  hashtable: introduce a small and naive hashtable
  user_ns: use new hashtable implementation
  mm,ksm: use new hashtable implementation
  workqueue: use new hashtable implementation

 include/linux/hashtable.h      |   46 ++++++++++++++++++++
 include/linux/user_namespace.h |   11 +++--
 kernel/user.c                  |   54 ++++-------------------
 kernel/user_namespace.c        |    4 +-
 kernel/workqueue.c             |   91 ++++++---------------------------------
 mm/ksm.c                       |   29 ++++---------
 6 files changed, 87 insertions(+), 148 deletions(-)
 create mode 100644 include/linux/hashtable.h

-- 
1.7.8.6

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[RFC 1/4] hashtable: introduce a small and naive hashtable

[Sasha Levin]

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 |   46 +++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 46 insertions(+), 0 deletions(-)
 create mode 100644 include/linux/hashtable.h

diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
new file mode 100644
index 0000000..9b29fd1
--- /dev/null
+++ b/include/linux/hashtable.h
@@ -0,0 +1,46 @@
+#ifndef _LINUX_HASHTABLE_H
+#define _LINUX_HASHTABLE_H
+
+#include <linux/list.h>
+#include <linux/types.h>
+#include <linux/kernel.h>
+#include <linux/hash.h>
+
+#define DEFINE_HASHTABLE(name, bits)					\
+	struct hlist_head name[1 << bits];
+
+#define HASH_BITS(name) (order_base_2(ARRAY_SIZE(name)))
+#define HASH_SIZE(name) (1 << (HASH_BITS(name)))
+
+#define HASH_INIT(name)							\
+({									\
+	int __i;							\
+	for (__i = 0 ; __i < HASH_SIZE(name) ; __i++)			\
+		INIT_HLIST_HEAD(&name[__i]);				\
+})
+
+#define HASH_ADD(name, obj, key)					\
+	hlist_add_head(obj, &name[					\
+		hash_long((unsigned long)key, HASH_BITS(name))]);
+
+#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[			\
+			hash_long((unsigned long) __key,		\
+			HASH_BITS(name))], member)			\
+		if (cmp_fn(__obj, __key))				\
+			break;						\
+	__obj;								\
+})
+
+#define HASH_DEL(obj, member)						\
+	hlist_del(&obj->member)
+
+#define HASH_FOR_EACH(bkt, node, name, obj, member)			\
+	for (bkt = 0; bkt < HASH_SIZE(name); bkt++)			\
+		hlist_for_each_entry(obj, node, &name[i], member)
+
+#endif
-- 
1.7.8.6

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Tejun Heo]

Hello, Sasha.

On Tue, Jul 31, 2012 at 08:05:17PM +0200, Sasha Levin wrote:
> +#define HASH_INIT(name)							\
> +({									\
> +	int __i;							\
> +	for (__i = 0 ; __i < HASH_SIZE(name) ; __i++)			\
> +		INIT_HLIST_HEAD(&name[__i]);				\
> +})

Why use macro?

> +#define HASH_ADD(name, obj, key)					\
> +	hlist_add_head(obj, &name[					\
> +		hash_long((unsigned long)key, HASH_BITS(name))]);

Ditto.

> +#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[			\
> +			hash_long((unsigned long) __key,		\
> +			HASH_BITS(name))], member)			\
> +		if (cmp_fn(__obj, __key))				\
> +			break;						\
> +	__obj;								\
> +})

Wouldn't it be simpler to have something like the following

	hash_for_each_possible_match(pos, hash, key)

and let the caller handle the actual comparison?  Callbacks often are
painful to use and I don't think the above dancing buys much.

> +#define HASH_DEL(obj, member)						\
> +	hlist_del(&obj->member)

@obj is struct hlist_node in HASH_ADD and the containing type here?
Most in-kernel generic data containers implement just the container
itself and let the caller handle the conversions between container
node and the containing object.  I think it would better not to
deviate from that.

> +#define HASH_FOR_EACH(bkt, node, name, obj, member)			\
> +	for (bkt = 0; bkt < HASH_SIZE(name); bkt++)			\
> +		hlist_for_each_entry(obj, node, &name[i], member)

Why in caps?  Most for_each macros are in lower case.

Thanks.

-- 
tejun

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 07/31/2012 08:23 PM, Tejun Heo wrote:
> Hello, Sasha.
> 
> On Tue, Jul 31, 2012 at 08:05:17PM +0200, Sasha Levin wrote:
>> +#define HASH_INIT(name)							\
>> +({									\
>> +	int __i;							\
>> +	for (__i = 0 ; __i < HASH_SIZE(name) ; __i++)			\
>> +		INIT_HLIST_HEAD(&name[__i]);				\
>> +})
> 
> Why use macro?
> 
>> +#define HASH_ADD(name, obj, key)					\
>> +	hlist_add_head(obj, &name[					\
>> +		hash_long((unsigned long)key, HASH_BITS(name))]);
> 
> Ditto.

No special reason, I'll modify both to be functions.

>> +#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[			\
>> +			hash_long((unsigned long) __key,		\
>> +			HASH_BITS(name))], member)			\
>> +		if (cmp_fn(__obj, __key))				\
>> +			break;						\
>> +	__obj;								\
>> +})
> 
> Wouldn't it be simpler to have something like the following
> 
> 	hash_for_each_possible_match(pos, hash, key)
> 
> and let the caller handle the actual comparison?  Callbacks often are
> painful to use and I don't think the above dancing buys much.

I thought about that, but if you look at the 3 modules I've converted to use this hashtable, I think that the option to provide a callback worked pretty well for all of them, and in my opinion in those cases it looks better than iterating over entries in the code.

Would it make sense to have both methods?

>> +#define HASH_DEL(obj, member)						\
>> +	hlist_del(&obj->member)
> 
> @obj is struct hlist_node in HASH_ADD and the containing type here?
> Most in-kernel generic data containers implement just the container
> itself and let the caller handle the conversions between container
> node and the containing object.  I think it would better not to
> deviate from that.

Agreed, will fix.

>> +#define HASH_FOR_EACH(bkt, node, name, obj, member)			\
>> +	for (bkt = 0; bkt < HASH_SIZE(name); bkt++)			\
>> +		hlist_for_each_entry(obj, node, &name[i], member)
> 
> Why in caps?  Most for_each macros are in lower case.

No special reason, will fix that as well.

Thanks for the review Tejun!

> Thanks.
> 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 07/31/2012 08:23 PM, Tejun Heo wrote:
> Hello, Sasha.
> 
> On Tue, Jul 31, 2012 at 08:05:17PM +0200, Sasha Levin wrote:
>> +#define HASH_INIT(name)							\
>> +({									\
>> +	int __i;							\
>> +	for (__i = 0 ; __i < HASH_SIZE(name) ; __i++)			\
>> +		INIT_HLIST_HEAD(&name[__i]);				\
>> +})
> 
> Why use macro?
> 
>> +#define HASH_ADD(name, obj, key)					\
>> +	hlist_add_head(obj, &name[					\
>> +		hash_long((unsigned long)key, HASH_BITS(name))]);
> 
> Ditto.

Oh, yes, I've started working on this and remembered why it's macro in the first place.

Notice that we don't store hashtable size anywhere, this is because we can get it directly from the size of the hashtable array itself.

If we switch to using functions, we could no longer hide it anywhere (we'd need to either turn the buckets into a struct, or have the user pass it around to all functions).

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Tejun Heo]

On Wed, Aug 01, 2012 at 08:19:52PM +0200, Sasha Levin wrote:
> If we switch to using functions, we could no longer hide it anywhere
> (we'd need to either turn the buckets into a struct, or have the
> user pass it around to all functions).

Create an outer struct hash_table which remembers the size?

-- 
tejun

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 08/01/2012 08:21 PM, Tejun Heo wrote:
> On Wed, Aug 01, 2012 at 08:19:52PM +0200, Sasha Levin wrote:
>> If we switch to using functions, we could no longer hide it anywhere
>> (we'd need to either turn the buckets into a struct, or have the
>> user pass it around to all functions).
> 
> Create an outer struct hash_table which remembers the size?

Possible. I just wanted to avoid creating new structs where they're not really required.

Do you think it's worth it for eliminating those two macros?

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Tejun Heo]

On Wed, Aug 01, 2012 at 08:24:32PM +0200, Sasha Levin wrote:
> On 08/01/2012 08:21 PM, Tejun Heo wrote:
> > On Wed, Aug 01, 2012 at 08:19:52PM +0200, Sasha Levin wrote:
> >> If we switch to using functions, we could no longer hide it anywhere
> >> (we'd need to either turn the buckets into a struct, or have the
> >> user pass it around to all functions).
> > 
> > Create an outer struct hash_table which remembers the size?
> 
> Possible. I just wanted to avoid creating new structs where they're not really required.
> 
> Do you think it's worth it for eliminating those two macros?

What if someone wants to allocate hashtable dynamically which isn't
too unlikely?  I think it's best to stay away from macro tricks as
much as possible although I gotta admit I fall into the macro trap
more often than I would like.

Thanks.

-- 
tejun

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 08/01/2012 08:27 PM, Tejun Heo wrote:
> On Wed, Aug 01, 2012 at 08:24:32PM +0200, Sasha Levin wrote:
>> On 08/01/2012 08:21 PM, Tejun Heo wrote:
>>> On Wed, Aug 01, 2012 at 08:19:52PM +0200, Sasha Levin wrote:
>>>> If we switch to using functions, we could no longer hide it anywhere
>>>> (we'd need to either turn the buckets into a struct, or have the
>>>> user pass it around to all functions).
>>>
>>> Create an outer struct hash_table which remembers the size?
>>
>> Possible. I just wanted to avoid creating new structs where they're not really required.
>>
>> Do you think it's worth it for eliminating those two macros?
> 
> What if someone wants to allocate hashtable dynamically which isn't
> too unlikely?  I think it's best to stay away from macro tricks as
> much as possible although I gotta admit I fall into the macro trap
> more often than I would like.

Using a struct makes the dynamic case much easier, but it complicates the static case.

Previously we could create the buckets statically.

Consider this struct:

struct hash_table {
	u32 bits;
	struct hlist_head buckets[];
};

We can't make any code that wraps this to make it work properly statically allocated nice enough to be acceptable.


What if when creating the buckets, we actually allocate bits+1 buckets, and use the last bucket not as a bucket but as the bitcount? It looks like a hack but I think it's much nicer than the previous.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Tejun Heo]

On Wed, Aug 01, 2012 at 09:06:50PM +0200, Sasha Levin wrote:
> Using a struct makes the dynamic case much easier, but it complicates the static case.
> 
> Previously we could create the buckets statically.
> 
> Consider this struct:
> 
> struct hash_table {
> 	u32 bits;
> 	struct hlist_head buckets[];
> };
> 
> We can't make any code that wraps this to make it work properly
> statically allocated nice enough to be acceptable.

I don't know.  Maybe you can create an anonymous outer struct / union
and play symbol trick to alias hash_table to its member.  If it is
gimped either way, I'm not sure whether it's really worthwhile to
create the abstraction.  It's not like we're saving a lot of
complexity.

Thanks.

-- 
tejun

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 08/01/2012 10:24 PM, Tejun Heo wrote:
> On Wed, Aug 01, 2012 at 09:06:50PM +0200, Sasha Levin wrote:
>> Using a struct makes the dynamic case much easier, but it complicates the static case.
>>
>> Previously we could create the buckets statically.
>>
>> Consider this struct:
>>
>> struct hash_table {
>> 	u32 bits;
>> 	struct hlist_head buckets[];
>> };
>>
>> We can't make any code that wraps this to make it work properly
>> statically allocated nice enough to be acceptable.
> 
> I don't know.  Maybe you can create an anonymous outer struct / union
> and play symbol trick to alias hash_table to its member.  If it is
> gimped either way, I'm not sure whether it's really worthwhile to
> create the abstraction.  It's not like we're saving a lot of
> complexity.

I must be missing something here, but how would you avoid it?

How would your DEFINE_HASHTABLE look like if we got for the simple 'struct hash_table' approach?

> Thanks.
> 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Tejun Heo]

On Thu, Aug 02, 2012 at 12:41:56AM +0200, Sasha Levin wrote:
> How would your DEFINE_HASHTABLE look like if we got for the simple
> 'struct hash_table' approach?

I think defining a different enclosing anonymous struct which the
requested number of array entries and then aliasing the actual
hash_table to that symbol should work.  It's rather horrible and I'm
not sure it's worth the trouble.

Thanks.

-- 
tejun

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 08/02/2012 12:45 AM, Tejun Heo wrote:
> On Thu, Aug 02, 2012 at 12:41:56AM +0200, Sasha Levin wrote:
>> How would your DEFINE_HASHTABLE look like if we got for the simple
>> 'struct hash_table' approach?
> 
> I think defining a different enclosing anonymous struct which the
> requested number of array entries and then aliasing the actual
> hash_table to that symbol should work.  It's rather horrible and I'm
> not sure it's worth the trouble.

I agree that this is probably not worth the trouble.

At the moment I see two alternatives:

1. Dynamically allocate the hash buckets.

2. Use the first bucket to store size. Something like the follows:

	#define HASH_TABLE(name, bits)	\
        	struct hlist_head name[1 << bits + 1];

	#define HASH_TABLE_INIT (bits) ({name[0].next = bits});

And then have hash_{add,get} just skip the first bucket.


While it's not a pretty hack, I don't see a nice way to avoid having to dynamically allocate buckets for all cases.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Josh Triplett]

On Thu, Aug 02, 2012 at 12:00:33PM +0200, Sasha Levin wrote:
> On 08/02/2012 12:45 AM, Tejun Heo wrote:
> > On Thu, Aug 02, 2012 at 12:41:56AM +0200, Sasha Levin wrote:
> >> How would your DEFINE_HASHTABLE look like if we got for the simple
> >> 'struct hash_table' approach?
> > 
> > I think defining a different enclosing anonymous struct which the
> > requested number of array entries and then aliasing the actual
> > hash_table to that symbol should work.  It's rather horrible and I'm
> > not sure it's worth the trouble.
> 
> I agree that this is probably not worth the trouble.
> 
> At the moment I see two alternatives:
> 
> 1. Dynamically allocate the hash buckets.
> 
> 2. Use the first bucket to store size. Something like the follows:
> 
> 	#define HASH_TABLE(name, bits)	\
>         	struct hlist_head name[1 << bits + 1];
> 
> 	#define HASH_TABLE_INIT (bits) ({name[0].next = bits});
> 
> And then have hash_{add,get} just skip the first bucket.
> 
> 
> While it's not a pretty hack, I don't see a nice way to avoid having to dynamically allocate buckets for all cases.

What about using a C99 flexible array member?  Kernel style prohibits
variable-length arrays, but I don't think the same rationale applies to
flexible array members.

struct hash_table {
    size_t count;
    struct hlist_head buckets[];
};

#define DEFINE_HASH_TABLE(name, length) struct hash_table name = { .count = length, .buckets = { [0 ... (length - 1)] = HLIST_HEAD_INIT } }

- Josh Triplett

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 08/02/2012 12:32 PM, Josh Triplett wrote:
> On Thu, Aug 02, 2012 at 12:00:33PM +0200, Sasha Levin wrote:
>> On 08/02/2012 12:45 AM, Tejun Heo wrote:
>>> On Thu, Aug 02, 2012 at 12:41:56AM +0200, Sasha Levin wrote:
>>>> How would your DEFINE_HASHTABLE look like if we got for the simple
>>>> 'struct hash_table' approach?
>>>
>>> I think defining a different enclosing anonymous struct which the
>>> requested number of array entries and then aliasing the actual
>>> hash_table to that symbol should work.  It's rather horrible and I'm
>>> not sure it's worth the trouble.
>>
>> I agree that this is probably not worth the trouble.
>>
>> At the moment I see two alternatives:
>>
>> 1. Dynamically allocate the hash buckets.
>>
>> 2. Use the first bucket to store size. Something like the follows:
>>
>> 	#define HASH_TABLE(name, bits)	\
>>         	struct hlist_head name[1 << bits + 1];
>>
>> 	#define HASH_TABLE_INIT (bits) ({name[0].next = bits});
>>
>> And then have hash_{add,get} just skip the first bucket.
>>
>>
>> While it's not a pretty hack, I don't see a nice way to avoid having to dynamically allocate buckets for all cases.
> 
> What about using a C99 flexible array member?  Kernel style prohibits
> variable-length arrays, but I don't think the same rationale applies to
> flexible array members.
> 
> struct hash_table {
>     size_t count;
>     struct hlist_head buckets[];
> };
> 
> #define DEFINE_HASH_TABLE(name, length) struct hash_table name = { .count = length, .buckets = { [0 ... (length - 1)] = HLIST_HEAD_INIT } }

The limitation of this approach is that the struct hash_table variable must be 'static', which is a bit limiting - see for example the use of hashtable in 'struct user_namespace'.

> 
> - Josh Triplett
> 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 08/02/2012 01:23 PM, Sasha Levin wrote:
>> #define DEFINE_HASH_TABLE(name, length) struct hash_table name = { .count = length, .buckets = { [0 ... (length - 1)] = HLIST_HEAD_INIT } }
> The limitation of this approach is that the struct hash_table variable must be 'static', which is a bit limiting - see for example the use of hashtable in 'struct user_namespace'.
> 

What if we just use two possible decelerations? One of static structs and one for regular ones.

struct hash_table {
        size_t bits;
        struct hlist_head buckets[];
};

#define DEFINE_HASHTABLE(name, bits)                                    \
        union {                                                         \
                struct hash_table name;                                 \
                struct {                                                \
                        size_t bits;                                    \
                        struct hlist_head buckets[1 << bits];           \
                } __name;                                               \
        }

#define DEFINE_STATIC_HASHTABLE(name, bit)                              \
        static struct hash_table name = { .bits = bit,                  \
                .buckets = { [0 ... (bit - 1)] = HLIST_HEAD_INIT } }

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Josh Triplett]

On Thu, Aug 02, 2012 at 03:04:19PM +0200, Sasha Levin wrote:
> On 08/02/2012 01:23 PM, Sasha Levin wrote:
> >> #define DEFINE_HASH_TABLE(name, length) struct hash_table name = { .count = length, .buckets = { [0 ... (length - 1)] = HLIST_HEAD_INIT } }
> > The limitation of this approach is that the struct hash_table variable must be 'static', which is a bit limiting - see for example the use of hashtable in 'struct user_namespace'.
> > 
> 
> What if we just use two possible decelerations? One of static structs and one for regular ones.
> 
> struct hash_table {
>         size_t bits;
>         struct hlist_head buckets[];
> };
> 
> #define DEFINE_HASHTABLE(name, bits)                                    \
>         union {                                                         \
>                 struct hash_table name;                                 \
>                 struct {                                                \
>                         size_t bits;                                    \

This shouldn't use "bits", since it'll get expanded to the macro
argument.

>                         struct hlist_head buckets[1 << bits];           \
>                 } __name;                                               \

__##name

>         }
> 
> #define DEFINE_STATIC_HASHTABLE(name, bit)                              \
>         static struct hash_table name = { .bits = bit,                  \
>                 .buckets = { [0 ... (bit - 1)] = HLIST_HEAD_INIT } }

You probably wanted to change that to [0 ... ((1 << bit) - 1)] , to
match DEFINE_HASHTABLE.

Since your definition of DEFINE_HASHTABLE would also work fine when used
statically, why not just always use that?

#define DEFINE_STATIC_HASHTABLE(name, bits) static DEFINE_HASHTABLE(name, bits) = { .name.bits = bits }

One downside: you can't use this to define a global non-static hash
table, because you can't have a global non-static anonymous union.
Using the non-union form would actually allow a global non-static hash
table:

#define DEFINE_HASHTABLE_INIT(name, bits) struct hash_table name = { .bits = bits, .buckets = { [0 ... ((1 << bits) - 1)] = HLIST_HEAD_INIT } }

/* elsewhere */
extern struct hash_table name;

I don't know if that seems like a good idea or not.

- Josh Triplett

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 08/02/2012 06:15 PM, Josh Triplett wrote:
> On Thu, Aug 02, 2012 at 03:04:19PM +0200, Sasha Levin wrote:
>> On 08/02/2012 01:23 PM, Sasha Levin wrote:
>>>> #define DEFINE_HASH_TABLE(name, length) struct hash_table name = { .count = length, .buckets = { [0 ... (length - 1)] = HLIST_HEAD_INIT } }
>>> The limitation of this approach is that the struct hash_table variable must be 'static', which is a bit limiting - see for example the use of hashtable in 'struct user_namespace'.
>>>
>>
>> What if we just use two possible decelerations? One of static structs and one for regular ones.
>>
>> struct hash_table {
>>         size_t bits;
>>         struct hlist_head buckets[];
>> };
>>
>> #define DEFINE_HASHTABLE(name, bits)                                    \
>>         union {                                                         \
>>                 struct hash_table name;                                 \
>>                 struct {                                                \
>>                         size_t bits;                                    \
> 
> This shouldn't use "bits", since it'll get expanded to the macro
> argument.
> 
>>                         struct hlist_head buckets[1 << bits];           \
>>                 } __name;                                               \
> 
> __##name
> 
>>         }
>>
>> #define DEFINE_STATIC_HASHTABLE(name, bit)                              \
>>         static struct hash_table name = { .bits = bit,                  \
>>                 .buckets = { [0 ... (bit - 1)] = HLIST_HEAD_INIT } }
> 
> You probably wanted to change that to [0 ... ((1 << bit) - 1)] , to
> match DEFINE_HASHTABLE.

I wrote it by hand and didn't compile test, will fix all of those.

> Since your definition of DEFINE_HASHTABLE would also work fine when used
> statically, why not just always use that?
> 
> #define DEFINE_STATIC_HASHTABLE(name, bits) static DEFINE_HASHTABLE(name, bits) = { .name.bits = bits }

It will get defined fine, but it will be awkward to use. We'd need to pass anonymous union to all the functions that handle this hashtable, which isn't pretty.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Josh Triplett]

On Thu, Aug 02, 2012 at 06:48:07PM +0200, Sasha Levin wrote:
> On 08/02/2012 06:15 PM, Josh Triplett wrote:
> > On Thu, Aug 02, 2012 at 03:04:19PM +0200, Sasha Levin wrote:
> >> On 08/02/2012 01:23 PM, Sasha Levin wrote:
> >>>> #define DEFINE_HASH_TABLE(name, length) struct hash_table name = { .count = length, .buckets = { [0 ... (length - 1)] = HLIST_HEAD_INIT } }
> >>> The limitation of this approach is that the struct hash_table variable must be 'static', which is a bit limiting - see for example the use of hashtable in 'struct user_namespace'.
> >>>
> >>
> >> What if we just use two possible decelerations? One of static structs and one for regular ones.
> >>
> >> struct hash_table {
> >>         size_t bits;
> >>         struct hlist_head buckets[];
> >> };
> >>
> >> #define DEFINE_HASHTABLE(name, bits)                                    \
> >>         union {                                                         \
> >>                 struct hash_table name;                                 \
> >>                 struct {                                                \
> >>                         size_t bits;                                    \
> > 
> > This shouldn't use "bits", since it'll get expanded to the macro
> > argument.
> > 
> >>                         struct hlist_head buckets[1 << bits];           \
> >>                 } __name;                                               \
> > 
> > __##name
> > 
> >>         }
> >>
> >> #define DEFINE_STATIC_HASHTABLE(name, bit)                              \
> >>         static struct hash_table name = { .bits = bit,                  \
> >>                 .buckets = { [0 ... (bit - 1)] = HLIST_HEAD_INIT } }
> > 
> > You probably wanted to change that to [0 ... ((1 << bit) - 1)] , to
> > match DEFINE_HASHTABLE.
> 
> I wrote it by hand and didn't compile test, will fix all of those.
> 
> > Since your definition of DEFINE_HASHTABLE would also work fine when used
> > statically, why not just always use that?
> > 
> > #define DEFINE_STATIC_HASHTABLE(name, bits) static DEFINE_HASHTABLE(name, bits) = { .name.bits = bits }
> 
> It will get defined fine, but it will be awkward to use. We'd need to pass anonymous union to all the functions that handle this hashtable, which isn't pretty.

No, it'll still use the anonymous union, so you'll still have a thing of
type "struct hash_table" with the given name, and you can use that name
with the hash-table functions.

- Josh Triplett

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 08/02/2012 07:44 PM, Josh Triplett wrote:
> On Thu, Aug 02, 2012 at 06:48:07PM +0200, Sasha Levin wrote:
>> On 08/02/2012 06:15 PM, Josh Triplett wrote:
>>> On Thu, Aug 02, 2012 at 03:04:19PM +0200, Sasha Levin wrote:
>>>> On 08/02/2012 01:23 PM, Sasha Levin wrote:
>>>>>> #define DEFINE_HASH_TABLE(name, length) struct hash_table name = { .count = length, .buckets = { [0 ... (length - 1)] = HLIST_HEAD_INIT } }
>>>>> The limitation of this approach is that the struct hash_table variable must be 'static', which is a bit limiting - see for example the use of hashtable in 'struct user_namespace'.
>>>>>
>>>>
>>>> What if we just use two possible decelerations? One of static structs and one for regular ones.
>>>>
>>>> struct hash_table {
>>>>         size_t bits;
>>>>         struct hlist_head buckets[];
>>>> };
>>>>
>>>> #define DEFINE_HASHTABLE(name, bits)                                    \
>>>>         union {                                                         \
>>>>                 struct hash_table name;                                 \
>>>>                 struct {                                                \
>>>>                         size_t bits;                                    \
>>>
>>> This shouldn't use "bits", since it'll get expanded to the macro
>>> argument.
>>>
>>>>                         struct hlist_head buckets[1 << bits];           \
>>>>                 } __name;                                               \
>>>
>>> __##name
>>>
>>>>         }
>>>>
>>>> #define DEFINE_STATIC_HASHTABLE(name, bit)                              \
>>>>         static struct hash_table name = { .bits = bit,                  \
>>>>                 .buckets = { [0 ... (bit - 1)] = HLIST_HEAD_INIT } }
>>>
>>> You probably wanted to change that to [0 ... ((1 << bit) - 1)] , to
>>> match DEFINE_HASHTABLE.
>>
>> I wrote it by hand and didn't compile test, will fix all of those.
>>
>>> Since your definition of DEFINE_HASHTABLE would also work fine when used
>>> statically, why not just always use that?
>>>
>>> #define DEFINE_STATIC_HASHTABLE(name, bits) static DEFINE_HASHTABLE(name, bits) = { .name.bits = bits }
>>
>> It will get defined fine, but it will be awkward to use. We'd need to pass anonymous union to all the functions that handle this hashtable, which isn't pretty.
> 
> No, it'll still use the anonymous union, so you'll still have a thing of
> type "struct hash_table" with the given name, and you can use that name
> with the hash-table functions.

We can use 'struct hash_table' directly, but then the call will look awkward :)

Consider this case (I've placed arbitrary values into size and name:

/* I've "preprocessed" the DEFINE macro below */
union {
	struct hash_table table;
	struct {
		size_t bits;
		struct hlist_head buckets[32];
	}
} my_hashtable;

void foo(struct hash_table *table)
{
/* Do something */
}

int main(void)
{
	foo(my_hashtable); /* This is what the user expects to work, and won't work in this case */

	foo(&my_hashtable.table); /* This is what he has to do, which means the user has to know about the internal structure of the union */
}

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Josh Triplett]

On Thu, Aug 02, 2012 at 07:54:42PM +0200, Sasha Levin wrote:
> On 08/02/2012 07:44 PM, Josh Triplett wrote:
> > On Thu, Aug 02, 2012 at 06:48:07PM +0200, Sasha Levin wrote:
> >> On 08/02/2012 06:15 PM, Josh Triplett wrote:
> >>> On Thu, Aug 02, 2012 at 03:04:19PM +0200, Sasha Levin wrote:
> >>>> On 08/02/2012 01:23 PM, Sasha Levin wrote:
> >>>>>> #define DEFINE_HASH_TABLE(name, length) struct hash_table name = { .count = length, .buckets = { [0 ... (length - 1)] = HLIST_HEAD_INIT } }
> >>>>> The limitation of this approach is that the struct hash_table variable must be 'static', which is a bit limiting - see for example the use of hashtable in 'struct user_namespace'.
> >>>>>
> >>>>
> >>>> What if we just use two possible decelerations? One of static structs and one for regular ones.
> >>>>
> >>>> struct hash_table {
> >>>>         size_t bits;
> >>>>         struct hlist_head buckets[];
> >>>> };
> >>>>
> >>>> #define DEFINE_HASHTABLE(name, bits)                                    \
> >>>>         union {                                                         \
> >>>>                 struct hash_table name;                                 \
> >>>>                 struct {                                                \
> >>>>                         size_t bits;                                    \
> >>>
> >>> This shouldn't use "bits", since it'll get expanded to the macro
> >>> argument.
> >>>
> >>>>                         struct hlist_head buckets[1 << bits];           \
> >>>>                 } __name;                                               \
> >>>
> >>> __##name
> >>>
> >>>>         }
> >>>>
> >>>> #define DEFINE_STATIC_HASHTABLE(name, bit)                              \
> >>>>         static struct hash_table name = { .bits = bit,                  \
> >>>>                 .buckets = { [0 ... (bit - 1)] = HLIST_HEAD_INIT } }
> >>>
> >>> You probably wanted to change that to [0 ... ((1 << bit) - 1)] , to
> >>> match DEFINE_HASHTABLE.
> >>
> >> I wrote it by hand and didn't compile test, will fix all of those.
> >>
> >>> Since your definition of DEFINE_HASHTABLE would also work fine when used
> >>> statically, why not just always use that?
> >>>
> >>> #define DEFINE_STATIC_HASHTABLE(name, bits) static DEFINE_HASHTABLE(name, bits) = { .name.bits = bits }
> >>
> >> It will get defined fine, but it will be awkward to use. We'd need to pass anonymous union to all the functions that handle this hashtable, which isn't pretty.
> > 
> > No, it'll still use the anonymous union, so you'll still have a thing of
> > type "struct hash_table" with the given name, and you can use that name
> > with the hash-table functions.
> 
> We can use 'struct hash_table' directly, but then the call will look awkward :)
> 
> Consider this case (I've placed arbitrary values into size and name:
> 
> /* I've "preprocessed" the DEFINE macro below */
> union {
> 	struct hash_table table;
> 	struct {
> 		size_t bits;
> 		struct hlist_head buckets[32];
> 	}
> } my_hashtable;

That expansion doesn't match the macros.  Using the most recent
definitions of DEFINE_HASHTABLE and DEFINE_STATIC_HASHTABLE from above,
the definition would look something like this:

static union {
	struct hash_table my_hashtable;
	struct {
		size_t bits;
		struct hlist_head buckets[1 << 5];
	} __my_hashtable;
} = { .my_hashtable.bits = 5 };

> void foo(struct hash_table *table)
> {
> /* Do something */
> }
> 
> int main(void)
> {
> 	foo(my_hashtable); /* This is what the user expects to work, and won't work in this case */
> 
> 	foo(&my_hashtable.table); /* This is what he has to do, which means the user has to know about the internal structure of the union */
> }

Given the expansion above, you can just write this as
foo(&my_hashtable), which seems sensible to me.

- Josh Triplett

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 08/02/2012 10:41 PM, Josh Triplett wrote:
> On Thu, Aug 02, 2012 at 07:54:42PM +0200, Sasha Levin wrote:
>> /* I've "preprocessed" the DEFINE macro below */
>> union {
>> 	struct hash_table table;
>> 	struct {
>> 		size_t bits;
>> 		struct hlist_head buckets[32];
>> 	}
>> } my_hashtable;
> 
> That expansion doesn't match the macros.  Using the most recent
> definitions of DEFINE_HASHTABLE and DEFINE_STATIC_HASHTABLE from above,
> the definition would look something like this:
> 
> static union {
> 	struct hash_table my_hashtable;
> 	struct {
> 		size_t bits;
> 		struct hlist_head buckets[1 << 5];
> 	} __my_hashtable;
> } = { .my_hashtable.bits = 5 };

It's different because I don't think you can do what you did above with global variables.

You won't be defining any instances of that anonymous struct, so my_hashtable won't exist anywhere.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Josh Triplett]

On Thu, Aug 02, 2012 at 11:47:01PM +0200, Sasha Levin wrote:
> On 08/02/2012 10:41 PM, Josh Triplett wrote:
> > On Thu, Aug 02, 2012 at 07:54:42PM +0200, Sasha Levin wrote:
> >> /* I've "preprocessed" the DEFINE macro below */
> >> union {
> >> 	struct hash_table table;
> >> 	struct {
> >> 		size_t bits;
> >> 		struct hlist_head buckets[32];
> >> 	}
> >> } my_hashtable;
> > 
> > That expansion doesn't match the macros.  Using the most recent
> > definitions of DEFINE_HASHTABLE and DEFINE_STATIC_HASHTABLE from above,
> > the definition would look something like this:
> > 
> > static union {
> > 	struct hash_table my_hashtable;
> > 	struct {
> > 		size_t bits;
> > 		struct hlist_head buckets[1 << 5];
> > 	} __my_hashtable;
> > } = { .my_hashtable.bits = 5 };
> 
> It's different because I don't think you can do what you did above with global variables.
> 
> You won't be defining any instances of that anonymous struct, so my_hashtable won't exist anywhere.

...how strange.  The above syntax ought to work, and many other
compilers document it as legal syntax (and I thought that C1x's
anonymous structs and unions allowed it), but indeed GCC doesn't accept
it.

Fair enough; looks like consolidating the macro implementations won't
actually work.

- Josh Triplett

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Eric W. Biederman]

Sasha Levin <levinsasha928@gmail.com> writes:
> On 08/02/2012 12:32 PM, Josh Triplett wrote:
>> What about using a C99 flexible array member?  Kernel style prohibits
>> variable-length arrays, but I don't think the same rationale applies to
>> flexible array members.
>> 
>> struct hash_table {
>>     size_t count;
>>     struct hlist_head buckets[];
>> };
>> 
>> #define DEFINE_HASH_TABLE(name, length) struct hash_table name = { .count = length, .buckets = { [0 ... (length - 1)] = HLIST_HEAD_INIT } }
>
> The limitation of this approach is that the struct hash_table variable
> must be 'static', which is a bit limiting - see for example the use of
> hashtable in 'struct user_namespace'.

You mean the hash table that was made static in 3.5?

You might want to try basing your patches on something a little more current.

Eric

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Sasha Levin]

On 08/02/2012 06:03 PM, Eric W. Biederman wrote:
> Sasha Levin <levinsasha928@gmail.com> writes:
>> On 08/02/2012 12:32 PM, Josh Triplett wrote:
>>> What about using a C99 flexible array member?  Kernel style prohibits
>>> variable-length arrays, but I don't think the same rationale applies to
>>> flexible array members.
>>>
>>> struct hash_table {
>>>     size_t count;
>>>     struct hlist_head buckets[];
>>> };
>>>
>>> #define DEFINE_HASH_TABLE(name, length) struct hash_table name = { .count = length, .buckets = { [0 ... (length - 1)] = HLIST_HEAD_INIT } }
>>
>> The limitation of this approach is that the struct hash_table variable
>> must be 'static', which is a bit limiting - see for example the use of
>> hashtable in 'struct user_namespace'.
> 
> You mean the hash table that was made static in 3.5?
> 
> You might want to try basing your patches on something a little more current.
> 
> Eric
> 

Heh, I've started working on it in April, and just returned to this. Didn't think about rebasing to something new.

will fix - Thanks!

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Eric W. Biederman]

Sasha Levin <levinsasha928@gmail.com> writes:

> Heh, I've started working on it in April, and just returned to this. Didn't think about rebasing to something new.
>
> will fix - Thanks!

You might want to look at some of the work that Eric Dumazet has done in
the networking stack with rcu hashtables that can be resized.

For a trivial hash table I don't know if the abstraction is worth it.
For a hash table that starts off small and grows as big as you need it
the incent to use a hash table abstraction seems a lot stronger.

Eric

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Linus Torvalds]

On Thu, Aug 2, 2012 at 9:40 AM, Eric W. Biederman <ebiederm@xmission.com> wrote:
>
> For a trivial hash table I don't know if the abstraction is worth it.
> For a hash table that starts off small and grows as big as you need it
> the incent to use a hash table abstraction seems a lot stronger.

I'm not sure growing hash tables are worth it.

In the dcache layer, we have an allocated-at-boot-time sizing thing,
and I have been playing around with a patch that makes the hash table
statically sized (and pretty small). And it actually speeds things up!

A statically allocated hash-table with a fixed size is quite
noticeably faster, because you don't have those extra indirect reads
of the base/size that are in the critical path to the actual lookup.
So for the dentry code I tried a small(ish) direct-mapped fixed-size
"L1 hash" table that then falls back to the old dynamically sized one
when it misses ("main memory"), and it really does seem to work really
well.

The reason it's not committed in my tree is that the filling of the
small L1 hash is racy for me right now (I don't want to take any locks
for filling the small one, and I haven't figured out how to fill it
racelessly without having to add the sequence number to the hash table
itself, which would make it annoyingly bigger).

Anyway, what I really wanted to bring up was the fact that static hash
tables of a fixed size are really quite noticeably faster. So I would
say that Sasha's patch to make *that* case easy actually sounds nice,
rather than making some more complicated case that is fundamentally
slower and more complicated.

                      Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Eric Dumazet]

On Thu, 2012-08-02 at 10:32 -0700, Linus Torvalds wrote:
> On Thu, Aug 2, 2012 at 9:40 AM, Eric W. Biederman <ebiederm@xmission.com> wrote:
> >
> > For a trivial hash table I don't know if the abstraction is worth it.
> > For a hash table that starts off small and grows as big as you need it
> > the incent to use a hash table abstraction seems a lot stronger.
> 
> I'm not sure growing hash tables are worth it.
> 
> In the dcache layer, we have an allocated-at-boot-time sizing thing,
> and I have been playing around with a patch that makes the hash table
> statically sized (and pretty small). And it actually speeds things up!

By the way, anybody tried to tweak vmalloc() (or
alloc_large_system_hash()) to use HugePages for those large hash
tables ?



--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Josh Triplett]

On Thu, Aug 02, 2012 at 10:32:13AM -0700, Linus Torvalds wrote:
> On Thu, Aug 2, 2012 at 9:40 AM, Eric W. Biederman <ebiederm@xmission.com> wrote:
> >
> > For a trivial hash table I don't know if the abstraction is worth it.
> > For a hash table that starts off small and grows as big as you need it
> > the incent to use a hash table abstraction seems a lot stronger.
> 
> I'm not sure growing hash tables are worth it.
> 
> In the dcache layer, we have an allocated-at-boot-time sizing thing,
> and I have been playing around with a patch that makes the hash table
> statically sized (and pretty small). And it actually speeds things up!
>
> A statically allocated hash-table with a fixed size is quite
> noticeably faster, because you don't have those extra indirect reads
> of the base/size that are in the critical path to the actual lookup.
> So for the dentry code I tried a small(ish) direct-mapped fixed-size
> "L1 hash" table that then falls back to the old dynamically sized one
> when it misses ("main memory"), and it really does seem to work really
> well.

You shouldn't have any extra indirection for the base, if it lives
immediately after the size.  You should only have a single extra
indirection for the size, and in a workload that uses that hash table
heavily, I'd hope that cache line sticks around.

Also, if you want to use a fixed-size "L1" hash table to reduce
indirections, you might as well use a non-chaining hash table to
eliminate another few indirections.

> The reason it's not committed in my tree is that the filling of the
> small L1 hash is racy for me right now (I don't want to take any locks
> for filling the small one, and I haven't figured out how to fill it
> racelessly without having to add the sequence number to the hash table
> itself, which would make it annoyingly bigger).

I'd be interested to see the performance numbers for an L1 hash that
doesn't cheat by skipping synchronization. :)  If you benchmarked an L1
hash with no synchronization against the existing dcache with its pile
of synchronization, that would make a large difference in performance,
but not necessarily because of a single extra indirection.

> Anyway, what I really wanted to bring up was the fact that static hash
> tables of a fixed size are really quite noticeably faster. So I would
> say that Sasha's patch to make *that* case easy actually sounds nice,
> rather than making some more complicated case that is fundamentally
> slower and more complicated.

The current approach that Sasha and I have iterated on should make the
fixed-size case equally easy and efficient, while also making the
resizable case possible.  Any particular reason not to use that
approach?

- Josh Triplett

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Linus Torvalds]

On Thu, Aug 2, 2012 at 10:59 AM, Josh Triplett <josh@joshtriplett.org> wrote:
>
> You shouldn't have any extra indirection for the base, if it lives
> immediately after the size.

Umm. You *always* have the extra indirection. Because you have that allocation.

So you have to follow the pointer to get the base/size, because they
aren't compile/link-time constants.

The cache misses were noticeable in macro-benchmarks, and in
micro-benchmarks the smaller L1 hash table means that things fit much
better in the L2.

It really improved performance. Seriously. Even things like "find /"
that had a lot of L1 misses ended up faster, because "find" is
apparently pretty moronic and does some things over and over. For
stuff that fit in the L1, it qas quite noticeable.

Of course, one reason for the speedup for the dcache was that I also
made the L1 only contain the simple cases (ie no "d_compare" thing
etc), so it speeded up dcache lookups in other ways too. But according
to the profiles, it really looked like better cache behavior was one
of the bigger things.

Trust me: every problem in computer science may be solved by an
indirection, but those indirections are *expensive*. Pointer chasing
is just about the most expensive thing you can do on modern CPU's.

               Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Josh Triplett]

On Thu, Aug 02, 2012 at 11:08:06AM -0700, Linus Torvalds wrote:
> On Thu, Aug 2, 2012 at 10:59 AM, Josh Triplett <josh@joshtriplett.org> wrote:
> >
> > You shouldn't have any extra indirection for the base, if it lives
> > immediately after the size.
> 
> Umm. You *always* have the extra indirection. Because you have that allocation.
> 
> So you have to follow the pointer to get the base/size, because they
> aren't compile/link-time constants.

Sorry, I should clarify what I meant: you'll have a total of one extra
indirection, not two.  You have to follow the pointer to get to both the
size and the buckets.  However, I would *hope* that you'd keep that line
in cache during any repeated activity using that hash table, which ought
to eliminate the cost of the indirection.  Does that line really get
evicted from cache entirely by the time you touch the dcache again?

> The cache misses were noticeable in macro-benchmarks, and in
> micro-benchmarks the smaller L1 hash table means that things fit much
> better in the L2.
>
> It really improved performance. Seriously. Even things like "find /"
> that had a lot of L1 misses ended up faster, because "find" is
> apparently pretty moronic and does some things over and over. For
> stuff that fit in the L1, it qas quite noticeable.
> 
> Of course, one reason for the speedup for the dcache was that I also
> made the L1 only contain the simple cases (ie no "d_compare" thing
> etc), so it speeded up dcache lookups in other ways too. But according
> to the profiles, it really looked like better cache behavior was one
> of the bigger things.

Seems like avoiding some of the longer paths through the dcache code
would also improve your cache behavior.  But in any case, I can easily
believe that the small L1 cache provides a win.

> Trust me: every problem in computer science may be solved by an
> indirection, but those indirections are *expensive*. Pointer chasing
> is just about the most expensive thing you can do on modern CPU's.

By that argument, it might make sense to make the L1 cache a closed hash
table and drop the chaining, to get rid of one more indirection, or
several.

Does your two-level dcache handle eviction?

Mind posting the WIP patches?

- Josh Triplett

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Linus Torvalds]

[-- Attachment #1: Type: text/plain, Size: 961 bytes --]

On Thu, Aug 2, 2012 at 1:25 PM, Josh Triplett <josh@joshtriplett.org> wrote:
>
> Sorry, I should clarify what I meant: you'll have a total of one extra
> indirection, not two.

Yes. But the hash table address generation is noticeably bigger and
slower due to the non-fixed size too.

In general, you can basically think of a dynamic hash table as always
having one extra entry in the hash chains. Sure, the base address
*may* cache well, but on the other hand, a smaller static hash table
caches better than a big one, so you lose some and you win some.
According to my numbers, you win a lot more than you lose.

> Does your two-level dcache handle eviction?
>
> Mind posting the WIP patches?

Attached. It's against an older kernel, but I suspect it still applies
cleanly. The patch is certainly simple, but note the warning (you can
*run* it, though - the race is almost entirely theoretical, so you can
get numbers without ever seeing it)

           Linus

[-- Attachment #2: patch.diff --]
[-- Type: application/octet-stream, Size: 6855 bytes --]

commit 8c8d4bb18dbaacfe88a4ce758610b386028499ba
Author: Linus Torvalds <torvalds@linux-foundation.org>
Date:   Thu May 31 10:26:52 2012 -0700

    vfs: add simple direct-mapped dcache lookup front-end
    
    I've pushed __d_lookup_rcu() just about as far as I could, and it still
    had some problems.
    
    The problems were mainly due to:
    
     - the complexity of the slow-case handling causes register spills
    
     - the hash chain lookup loop causes not only register pressure, but
       also the extra magic "mask off lock bit from the hash chain head
       pointer" etc logic
    
     - the hash list need to be dynamically sized (we want *big* caches, but
       you can't use the same size for big and small machines), which causes
       the initial hash lookup itself to be more complex.
    
    This looks like a viable solution to all three problems, and it is
    actually surprisingly simple: make a trivial fixed-size direct-mapped L1
    dentry cache.  No chains, no locking, no nothing.
    
    This gives measurable improvement on my microbenchmark, and gets good
    hit-rates on both kernel compiles and even on something like "updatedb",
    which I'd have expected to be one of the worst possible cases.
    Apparently updatedb still ends up looking up the same files (/etc/fstab
    etc) a lot.  So those good hit-rates seem to often be due to really
    stupid programming, but hey, I think we all agree that "stupid
    programming" is likely the common case that we generally do need to also
    optimize for ;)
    
    For my kernel compile benchmark ("make -j" on a fully built tree), the
    profile shows (this is kernel-only profile, so user space overhead
    removed):
    
      8.19%  [k] link_path_walk
      7.74%  [k] __d_lookup_rcu
      5.66%  [k] selinux_inode_permission
      3.73%  [k] do_lookup
      2.86%  [k] path_lookupat
      2.72%  [k] avc_has_perm_noaudit
      2.71%  [k] inode_has_perm.isra.49.constprop.71
      2.68%  [k] avc_lookup
      2.51%  [k] generic_permission
      ...
      0.78%  [k] __d_lookup_rcu_slow
      ...
    
    where "__d_lookup_rcu_slow()" is the exact same old __d_lookup_rcu(), so
    it's not really "slow", but it's quite noticeably slower than the new
    streamlined __d_lookup_rcu().  And as you can tell, that means that we
    must have a 90%+ hitrate in the new L1 dcache lookup, since we only see
    10% as much time in the slow routine as in the L1 front-end.
    
    HOWEVER. The fast L1 lookup right now is subtly buggy: not the lookup
    itself, but the code that adds entries to the L1 is racy with those
    entries being removed. I added a comment on it, and I think it's quite
    solvable (and it's all in the slow-path), but I'll need to think it
    through.
    
    Cc: Al Viro <viro@zeniv.linux.org.uk>
    Cc: Nick Piggin <npiggin@gmail.com>
    Cc: Miklos Szeredi <mszeredi@suse.cz>
    Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 fs/dcache.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 79 insertions(+), 2 deletions(-)

diff --git a/fs/dcache.c b/fs/dcache.c
index 4435d8b32904..f549f6505e53 100644
--- a/fs/dcache.c
+++ b/fs/dcache.c
@@ -402,6 +402,45 @@ static struct dentry *d_kill(struct dentry *dentry, struct dentry *parent)
 }
 
 /*
+ * This has a NULL parent and zero length, and will thus
+ * never match anything. But it means that the dcache_l1
+ * array never contains NULL, so you don't need to check.
+ */
+static struct dentry invalid_dentry;
+
+#define L1_DCACHE_BITS (13)
+#define L1_DCACHE_SIZE (1u << L1_DCACHE_BITS)
+static struct dentry *dcache_l1[L1_DCACHE_SIZE] = {
+	[0 ... L1_DCACHE_SIZE-1] = &invalid_dentry
+};
+
+static unsigned int dentry_l1_index(unsigned int hash, const struct dentry *parent)
+{
+	hash += (unsigned long) parent / L1_CACHE_BYTES;
+	hash = hash + (hash >> L1_DCACHE_BITS);
+	return hash & (L1_DCACHE_SIZE-1);
+}
+
+/* Must be called with d_lock held */
+static void d_remove_from_l1(const struct dentry *dentry)
+{
+	unsigned int n = dentry_l1_index(dentry->d_name.hash, dentry->d_parent);
+	dcache_l1[n] = &invalid_dentry;
+}
+
+static void d_add_to_l1(struct dentry *dentry, unsigned int hash, const struct dentry *parent)
+{
+	unsigned int n = dentry_l1_index(hash, parent);
+	dcache_l1[n] = dentry;
+}
+
+static struct dentry *d_lookup_l1(unsigned int hash, const struct dentry *parent)
+{
+	unsigned int n = dentry_l1_index(hash, parent);
+	return ACCESS_ONCE(dcache_l1[n]);
+}
+
+/*
  * Unhash a dentry without inserting an RCU walk barrier or checking that
  * dentry->d_lock is locked.  The caller must take care of that, if
  * appropriate.
@@ -416,6 +455,7 @@ static void __d_shrink(struct dentry *dentry)
 			b = d_hash(dentry->d_parent, dentry->d_name.hash);
 
 		hlist_bl_lock(b);
+		d_remove_from_l1(dentry);
 		__hlist_bl_del(&dentry->d_hash);
 		dentry->d_hash.pprev = NULL;
 		hlist_bl_unlock(b);
@@ -1825,7 +1865,7 @@ static noinline enum slow_d_compare slow_dentry_cmp(
  * NOTE! The caller *has* to check the resulting dentry against the sequence
  * number we've returned before using any of the resulting dentry state!
  */
-struct dentry *__d_lookup_rcu(const struct dentry *parent,
+static noinline struct dentry *__d_lookup_rcu_slow(const struct dentry *parent,
 				const struct qstr *name,
 				unsigned *seqp, struct inode *inode)
 {
@@ -1896,12 +1936,49 @@ seqretry:
 
 		if (dentry->d_name.hash_len != hashlen)
 			continue;
-		if (!dentry_cmp(dentry, str, hashlen_len(hashlen)))
+		if (!dentry_cmp(dentry, str, hashlen_len(hashlen))) {
+			/* FIXME! RACY! What if it just got unhashed? */
+			d_add_to_l1(dentry, hashlen_hash(hashlen), parent);
 			return dentry;
+		}
 	}
 	return NULL;
 }
 
+/*
+ * Fast non-chained L1 hash lookup.
+ *
+ * NOTE! We don't need to worry about DCACHE_OP_COMPARE, because
+ * dentries with complex parents never get added to the L1 cache.
+ *
+ * We also don't need to worry about d_lookup_l1() returning NULL,
+ * because we fill the cache with otherwise valid dentries that do
+ * not match anything.
+ */
+struct dentry *__d_lookup_rcu(const struct dentry *parent,
+				const struct qstr *name,
+				unsigned *seqp, struct inode *inode)
+{
+	u64 hashlen = name->hash_len;
+	struct dentry *dentry = d_lookup_l1(hashlen_hash(hashlen), parent);
+	unsigned int seq;
+
+	do {
+		seq = raw_seqcount_begin(&dentry->d_seq);
+		if (unlikely(dentry->d_parent != parent))
+			break;
+		*seqp = seq;
+		if (unlikely(dentry->d_name.hash_len != hashlen))
+			break;
+		if (unlikely(dentry_cmp(dentry, name->name, hashlen_len(hashlen))))
+			break;
+		if (unlikely(d_unhashed(dentry)))
+			break;
+		return dentry;
+	} while (0);
+	return __d_lookup_rcu_slow(parent, name, seqp, inode);
+}
+
 /**
  * d_lookup - search for a dentry
  * @parent: parent dentry

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Josh Triplett]

On Thu, Aug 02, 2012 at 01:32:41PM -0700, Linus Torvalds wrote:
> On Thu, Aug 2, 2012 at 1:25 PM, Josh Triplett <josh@joshtriplett.org> wrote:
> >
> > Sorry, I should clarify what I meant: you'll have a total of one extra
> > indirection, not two.
> 
> Yes. But the hash table address generation is noticeably bigger and
> slower due to the non-fixed size too.

If you store the size as a precomputed bitmask, that should simplify the
bucket lookup to just a fetch, mask, and offset.  (You shouldn't ever
need the actual number of buckets or the shift except when resizing, so
the bitmask seems like the optimal thing to store.)  With a fixed table
size, I'd expect to see the same code minus the fetch, with an immediate
in the masking instruction.  Did GCC's generated code have worse
differences than an immediate versus a fetched value?

> In general, you can basically think of a dynamic hash table as always
> having one extra entry in the hash chains. Sure, the base address
> *may* cache well, but on the other hand, a smaller static hash table
> caches better than a big one, so you lose some and you win some.
> According to my numbers, you win a lot more than you lose.

Agreed.

I don't think any of this argues against having a second-level cache,
though, and making that one resizable seems sensible.  So, having a
scalable resizable hash table seems orthogonal to having a small
fixed-size hash table as a first-level cache.  I already agree with you
that the hash table API should not make the latter more complex or
expensive to better suit the former; as far as I can tell, address
generation seems like the only issue there.

> > Does your two-level dcache handle eviction?
> >
> > Mind posting the WIP patches?
> 
> Attached. It's against an older kernel, but I suspect it still applies
> cleanly. The patch is certainly simple, but note the warning (you can
> *run* it, though - the race is almost entirely theoretical, so you can
> get numbers without ever seeing it)
> 
>            Linus


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Linus Torvalds]

On Thu, Aug 2, 2012 at 2:21 PM, Josh Triplett <josh@joshtriplett.org> wrote:
>
>  Did GCC's generated code have worse differences than an immediate
>  versus a fetched value?

Oh, *way* worse.

Nobody just masks the low bits. You have more bits than the low bits,
and unless you have some cryptographic hash (seldom) you want to use
them.

So no, it's not just as mask. For the dcache, it's

        hash = hash + (hash >> D_HASHBITS);
        return dentry_hashtable + (hash & D_HASHMASK);

so it's "shift + mask", and the constants mean less register pressure
and fewer latencies. One of the advantages of the L1 dcache code is
that the code gets *so* much simpler that it doesn't need a stack save
area at all, for example.

But as mentioned, the dcache L1 patch had other simplifications than
just the hash calculations, though. It doesn't do any loop over next
fields at all (it falls back to the slow case if it isn't a direct
hit), and it doesn't care about the d_compare() case (they will never
be added to the L1, since looking those things up is so slow that
there's no point). So there are other issues at play than just
avoiding the indirection to fetch base/mask/bitcount things and the
simplified hash calculation.

Not having a loop makes the register lifetimes simpler and again
causes less register pressure.

               Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

[Josh Triplett]

On Wed, Aug 01, 2012 at 11:27:49AM -0700, Tejun Heo wrote:
> On Wed, Aug 01, 2012 at 08:24:32PM +0200, Sasha Levin wrote:
> > On 08/01/2012 08:21 PM, Tejun Heo wrote:
> > > On Wed, Aug 01, 2012 at 08:19:52PM +0200, Sasha Levin wrote:
> > >> If we switch to using functions, we could no longer hide it anywhere
> > >> (we'd need to either turn the buckets into a struct, or have the
> > >> user pass it around to all functions).
> > > 
> > > Create an outer struct hash_table which remembers the size?
> > 
> > Possible. I just wanted to avoid creating new structs where they're not really required.
> > 
> > Do you think it's worth it for eliminating those two macros?
> 
> What if someone wants to allocate hashtable dynamically which isn't
> too unlikely?

In particular, once this goes in, I'd like to add RCU-based hash
resizing to it, which will require wrapping the hash table in a struct
that also contains the size.  So, please do consider having such a
struct rather than relying on static array sizes.

- Josh Triplett

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[RFC 2/4] user_ns: use new hashtable implementation

[Sasha Levin]

Switch user_ns to use the new hashtable implementation. This reduces the amount of
generic unrelated code in user_ns.

Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
 include/linux/user_namespace.h |   11 +++++---
 kernel/user.c                  |   54 +++++++--------------------------------
 kernel/user_namespace.c        |    4 +--
 3 files changed, 18 insertions(+), 51 deletions(-)

diff --git a/include/linux/user_namespace.h b/include/linux/user_namespace.h
index faf4679..cbbe342 100644
--- a/include/linux/user_namespace.h
+++ b/include/linux/user_namespace.h
@@ -5,13 +5,16 @@
 #include <linux/nsproxy.h>
 #include <linux/sched.h>
 #include <linux/err.h>
+#include <linux/hashtable.h>
 
-#define UIDHASH_BITS	(CONFIG_BASE_SMALL ? 3 : 7)
-#define UIDHASH_SZ	(1 << UIDHASH_BITS)
-
+#define UIDHASH_BITS		(CONFIG_BASE_SMALL ? 3 : 7)
+#define UIDHASH_CMP(obj, key)	((obj)->uid == (key))
+#define UIDHASH_ENTRY(ns, key)	(HASH_GET((ns)->uidhash_table, key,	\
+				struct user_struct, uidhash_node,	\
+				UIDHASH_CMP))
 struct user_namespace {
 	struct kref		kref;
-	struct hlist_head	uidhash_table[UIDHASH_SZ];
+	DEFINE_HASHTABLE(uidhash_table, UIDHASH_BITS);
 	struct user_struct	*creator;
 	struct work_struct	destroyer;
 };
diff --git a/kernel/user.c b/kernel/user.c
index 71dd236..3b8367c 100644
--- a/kernel/user.c
+++ b/kernel/user.c
@@ -34,10 +34,6 @@ EXPORT_SYMBOL_GPL(init_user_ns);
  * when changing user ID's (ie setuid() and friends).
  */
 
-#define UIDHASH_MASK		(UIDHASH_SZ - 1)
-#define __uidhashfn(uid)	(((uid >> UIDHASH_BITS) + uid) & UIDHASH_MASK)
-#define uidhashentry(ns, uid)	((ns)->uidhash_table + __uidhashfn((uid)))
-
 static struct kmem_cache *uid_cachep;
 
 /*
@@ -61,35 +57,6 @@ struct user_struct root_user = {
 	.user_ns	= &init_user_ns,
 };
 
-/*
- * These routines must be called with the uidhash spinlock held!
- */
-static void uid_hash_insert(struct user_struct *up, struct hlist_head *hashent)
-{
-	hlist_add_head(&up->uidhash_node, hashent);
-}
-
-static void uid_hash_remove(struct user_struct *up)
-{
-	hlist_del_init(&up->uidhash_node);
-	put_user_ns(up->user_ns);
-}
-
-static struct user_struct *uid_hash_find(uid_t uid, struct hlist_head *hashent)
-{
-	struct user_struct *user;
-	struct hlist_node *h;
-
-	hlist_for_each_entry(user, h, hashent, uidhash_node) {
-		if (user->uid == uid) {
-			atomic_inc(&user->__count);
-			return user;
-		}
-	}
-
-	return NULL;
-}
-
 /* IRQs are disabled and uidhash_lock is held upon function entry.
  * IRQ state (as stored in flags) is restored and uidhash_lock released
  * upon function exit.
@@ -97,7 +64,8 @@ static struct user_struct *uid_hash_find(uid_t uid, struct hlist_head *hashent)
 static void free_user(struct user_struct *up, unsigned long flags)
 	__releases(&uidhash_lock)
 {
-	uid_hash_remove(up);
+	HASH_DEL(up, uidhash_node);
+	put_user_ns(up->user_ns);
 	spin_unlock_irqrestore(&uidhash_lock, flags);
 	key_put(up->uid_keyring);
 	key_put(up->session_keyring);
@@ -117,7 +85,9 @@ struct user_struct *find_user(uid_t uid)
 	struct user_namespace *ns = current_user_ns();
 
 	spin_lock_irqsave(&uidhash_lock, flags);
-	ret = uid_hash_find(uid, uidhashentry(ns, uid));
+	ret = UIDHASH_ENTRY(ns, uid);
+	if (ret)
+		atomic_inc(&ret->__count);
 	spin_unlock_irqrestore(&uidhash_lock, flags);
 	return ret;
 }
@@ -138,11 +108,10 @@ void free_uid(struct user_struct *up)
 
 struct user_struct *alloc_uid(struct user_namespace *ns, uid_t uid)
 {
-	struct hlist_head *hashent = uidhashentry(ns, uid);
 	struct user_struct *up, *new;
 
 	spin_lock_irq(&uidhash_lock);
-	up = uid_hash_find(uid, hashent);
+	up = UIDHASH_ENTRY(ns, uid);
 	spin_unlock_irq(&uidhash_lock);
 
 	if (!up) {
@@ -160,14 +129,14 @@ struct user_struct *alloc_uid(struct user_namespace *ns, uid_t uid)
 		 * on adding the same user already..
 		 */
 		spin_lock_irq(&uidhash_lock);
-		up = uid_hash_find(uid, hashent);
+		up = UIDHASH_ENTRY(ns, uid);
 		if (up) {
 			put_user_ns(ns);
 			key_put(new->uid_keyring);
 			key_put(new->session_keyring);
 			kmem_cache_free(uid_cachep, new);
 		} else {
-			uid_hash_insert(new, hashent);
+			HASH_ADD(ns->uidhash_table, &new->uidhash_node, uid);
 			up = new;
 		}
 		spin_unlock_irq(&uidhash_lock);
@@ -181,17 +150,14 @@ out_unlock:
 
 static int __init uid_cache_init(void)
 {
-	int n;
-
 	uid_cachep = kmem_cache_create("uid_cache", sizeof(struct user_struct),
 			0, SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);
 
-	for(n = 0; n < UIDHASH_SZ; ++n)
-		INIT_HLIST_HEAD(init_user_ns.uidhash_table + n);
+	HASH_INIT(init_user_ns.uidhash_table);
 
 	/* Insert the root user immediately (init already runs as root) */
 	spin_lock_irq(&uidhash_lock);
-	uid_hash_insert(&root_user, uidhashentry(&init_user_ns, 0));
+	HASH_ADD(init_user_ns.uidhash_table, &root_user.uidhash_node, 0);
 	spin_unlock_irq(&uidhash_lock);
 
 	return 0;
diff --git a/kernel/user_namespace.c b/kernel/user_namespace.c
index 3b906e9..914c8c5 100644
--- a/kernel/user_namespace.c
+++ b/kernel/user_namespace.c
@@ -26,7 +26,6 @@ int create_user_ns(struct cred *new)
 {
 	struct user_namespace *ns;
 	struct user_struct *root_user;
-	int n;
 
 	ns = kmem_cache_alloc(user_ns_cachep, GFP_KERNEL);
 	if (!ns)
@@ -34,8 +33,7 @@ int create_user_ns(struct cred *new)
 
 	kref_init(&ns->kref);
 
-	for (n = 0; n < UIDHASH_SZ; ++n)
-		INIT_HLIST_HEAD(ns->uidhash_table + n);
+	HASH_INIT(ns->uidhash_table);
 
 	/* Alloc new root user.  */
 	root_user = alloc_uid(ns, 0);
-- 
1.7.8.6

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[RFC 3/4] mm,ksm: use new hashtable implementation

[Sasha Levin]

Switch ksm to use the new hashtable implementation. This reduces the amount of
generic unrelated code in the ksm module.

Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
 mm/ksm.c |   29 +++++++++--------------------
 1 files changed, 9 insertions(+), 20 deletions(-)

diff --git a/mm/ksm.c b/mm/ksm.c
index 47c8853..2f57def 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -33,7 +33,7 @@
 #include <linux/mmu_notifier.h>
 #include <linux/swap.h>
 #include <linux/ksm.h>
-#include <linux/hash.h>
+#include <linux/hashtable.h>
 #include <linux/freezer.h>
 #include <linux/oom.h>
 
@@ -157,8 +157,8 @@ static struct rb_root root_stable_tree = RB_ROOT;
 static struct rb_root root_unstable_tree = RB_ROOT;
 
 #define MM_SLOTS_HASH_SHIFT 10
-#define MM_SLOTS_HASH_HEADS (1 << MM_SLOTS_HASH_SHIFT)
-static struct hlist_head mm_slots_hash[MM_SLOTS_HASH_HEADS];
+#define mm_hash_cmp(slot, key) ((slot)->mm == (key))
+static DEFINE_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_SHIFT);
 
 static struct mm_slot ksm_mm_head = {
 	.mm_list = LIST_HEAD_INIT(ksm_mm_head.mm_list),
@@ -275,26 +275,15 @@ static inline void free_mm_slot(struct mm_slot *mm_slot)
 
 static struct mm_slot *get_mm_slot(struct mm_struct *mm)
 {
-	struct mm_slot *mm_slot;
-	struct hlist_head *bucket;
-	struct hlist_node *node;
-
-	bucket = &mm_slots_hash[hash_ptr(mm, MM_SLOTS_HASH_SHIFT)];
-	hlist_for_each_entry(mm_slot, node, bucket, link) {
-		if (mm == mm_slot->mm)
-			return mm_slot;
-	}
-	return NULL;
+	return HASH_GET(mm_slots_hash, mm, struct mm_slot,
+				link, mm_hash_cmp);
 }
 
 static void insert_to_mm_slots_hash(struct mm_struct *mm,
 				    struct mm_slot *mm_slot)
 {
-	struct hlist_head *bucket;
-
-	bucket = &mm_slots_hash[hash_ptr(mm, MM_SLOTS_HASH_SHIFT)];
 	mm_slot->mm = mm;
-	hlist_add_head(&mm_slot->link, bucket);
+	HASH_ADD(mm_slots_hash, &mm_slot->link, mm);
 }
 
 static inline int in_stable_tree(struct rmap_item *rmap_item)
@@ -647,7 +636,7 @@ static int unmerge_and_remove_all_rmap_items(void)
 		ksm_scan.mm_slot = list_entry(mm_slot->mm_list.next,
 						struct mm_slot, mm_list);
 		if (ksm_test_exit(mm)) {
-			hlist_del(&mm_slot->link);
+			HASH_DEL(mm_slot, link);
 			list_del(&mm_slot->mm_list);
 			spin_unlock(&ksm_mmlist_lock);
 
@@ -1385,7 +1374,7 @@ next_mm:
 		 * or when all VM_MERGEABLE areas have been unmapped (and
 		 * mmap_sem then protects against race with MADV_MERGEABLE).
 		 */
-		hlist_del(&slot->link);
+		HASH_DEL(slot, link);
 		list_del(&slot->mm_list);
 		spin_unlock(&ksm_mmlist_lock);
 
@@ -1548,7 +1537,7 @@ void __ksm_exit(struct mm_struct *mm)
 	mm_slot = get_mm_slot(mm);
 	if (mm_slot && ksm_scan.mm_slot != mm_slot) {
 		if (!mm_slot->rmap_list) {
-			hlist_del(&mm_slot->link);
+			HASH_DEL(mm_slot, link);
 			list_del(&mm_slot->mm_list);
 			easy_to_free = 1;
 		} else {
-- 
1.7.8.6

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

[RFC 4/4] workqueue: use new hashtable implementation

[Sasha Levin]

Switch workqueues to use the new hashtable implementation. This reduces the amount of
generic unrelated code in the workqueues.

Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
 kernel/workqueue.c |   91 ++++++++--------------------------------------------
 1 files changed, 14 insertions(+), 77 deletions(-)

diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index 5abf42f..8a9f232 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -41,6 +41,7 @@
 #include <linux/debug_locks.h>
 #include <linux/lockdep.h>
 #include <linux/idr.h>
+#include <linux/hashtable.h>
 
 #include "workqueue_sched.h"
 
@@ -73,8 +74,6 @@ enum {
 	TRUSTEE_DONE		= 4,		/* trustee is done */
 
 	BUSY_WORKER_HASH_ORDER	= 6,		/* 64 pointers */
-	BUSY_WORKER_HASH_SIZE	= 1 << BUSY_WORKER_HASH_ORDER,
-	BUSY_WORKER_HASH_MASK	= BUSY_WORKER_HASH_SIZE - 1,
 
 	MAX_IDLE_WORKERS_RATIO	= 4,		/* 1/4 of busy can be idle */
 	IDLE_WORKER_TIMEOUT	= 300 * HZ,	/* keep idle ones for 5 mins */
@@ -139,6 +138,8 @@ struct worker {
 	struct work_struct	rebind_work;	/* L: rebind worker to cpu */
 };
 
+#define worker_hash_cmp(obj, key) ((obj)->current_work == (key))
+
 /*
  * Global per-cpu workqueue.  There's one and only one for each cpu
  * and all works are queued and processed here regardless of their
@@ -155,7 +156,7 @@ struct global_cwq {
 
 	/* workers are chained either in the idle_list or busy_hash */
 	struct list_head	idle_list;	/* X: list of idle workers */
-	struct hlist_head	busy_hash[BUSY_WORKER_HASH_SIZE];
+	DEFINE_HASHTABLE(busy_hash, BUSY_WORKER_HASH_ORDER);
 						/* L: hash of busy workers */
 
 	struct timer_list	idle_timer;	/* L: worker idle timeout */
@@ -264,10 +265,6 @@ EXPORT_SYMBOL_GPL(system_nrt_freezable_wq);
 #define CREATE_TRACE_POINTS
 #include <trace/events/workqueue.h>
 
-#define for_each_busy_worker(worker, i, pos, gcwq)			\
-	for (i = 0; i < BUSY_WORKER_HASH_SIZE; i++)			\
-		hlist_for_each_entry(worker, pos, &gcwq->busy_hash[i], hentry)
-
 static inline int __next_gcwq_cpu(int cpu, const struct cpumask *mask,
 				  unsigned int sw)
 {
@@ -787,63 +784,6 @@ static inline void worker_clr_flags(struct worker *worker, unsigned int flags)
 }
 
 /**
- * busy_worker_head - return the busy hash head for a work
- * @gcwq: gcwq of interest
- * @work: work to be hashed
- *
- * Return hash head of @gcwq for @work.
- *
- * CONTEXT:
- * spin_lock_irq(gcwq->lock).
- *
- * RETURNS:
- * Pointer to the hash head.
- */
-static struct hlist_head *busy_worker_head(struct global_cwq *gcwq,
-					   struct work_struct *work)
-{
-	const int base_shift = ilog2(sizeof(struct work_struct));
-	unsigned long v = (unsigned long)work;
-
-	/* simple shift and fold hash, do we need something better? */
-	v >>= base_shift;
-	v += v >> BUSY_WORKER_HASH_ORDER;
-	v &= BUSY_WORKER_HASH_MASK;
-
-	return &gcwq->busy_hash[v];
-}
-
-/**
- * __find_worker_executing_work - find worker which is executing a work
- * @gcwq: gcwq of interest
- * @bwh: hash head as returned by busy_worker_head()
- * @work: work to find worker for
- *
- * Find a worker which is executing @work on @gcwq.  @bwh should be
- * the hash head obtained by calling busy_worker_head() with the same
- * work.
- *
- * CONTEXT:
- * spin_lock_irq(gcwq->lock).
- *
- * RETURNS:
- * Pointer to worker which is executing @work if found, NULL
- * otherwise.
- */
-static struct worker *__find_worker_executing_work(struct global_cwq *gcwq,
-						   struct hlist_head *bwh,
-						   struct work_struct *work)
-{
-	struct worker *worker;
-	struct hlist_node *tmp;
-
-	hlist_for_each_entry(worker, tmp, bwh, hentry)
-		if (worker->current_work == work)
-			return worker;
-	return NULL;
-}
-
-/**
  * find_worker_executing_work - find worker which is executing a work
  * @gcwq: gcwq of interest
  * @work: work to find worker for
@@ -862,8 +802,8 @@ static struct worker *__find_worker_executing_work(struct global_cwq *gcwq,
 static struct worker *find_worker_executing_work(struct global_cwq *gcwq,
 						 struct work_struct *work)
 {
-	return __find_worker_executing_work(gcwq, busy_worker_head(gcwq, work),
-					    work);
+	return HASH_GET(gcwq->busy_hash, work, struct worker,
+			hentry, worker_hash_cmp);
 }
 
 /**
@@ -953,7 +893,7 @@ static bool is_chained_work(struct workqueue_struct *wq)
 {
 	unsigned long flags;
 	unsigned int cpu;
-
+	
 	for_each_gcwq_cpu(cpu) {
 		struct global_cwq *gcwq = get_gcwq(cpu);
 		struct worker *worker;
@@ -961,7 +901,7 @@ static bool is_chained_work(struct workqueue_struct *wq)
 		int i;
 
 		spin_lock_irqsave(&gcwq->lock, flags);
-		for_each_busy_worker(worker, i, pos, gcwq) {
+		HASH_FOR_EACH(i, pos, gcwq->busy_hash, worker, hentry) {
 			if (worker->task != current)
 				continue;
 			spin_unlock_irqrestore(&gcwq->lock, flags);
@@ -1797,7 +1737,6 @@ __acquires(&gcwq->lock)
 {
 	struct cpu_workqueue_struct *cwq = get_work_cwq(work);
 	struct global_cwq *gcwq = cwq->gcwq;
-	struct hlist_head *bwh = busy_worker_head(gcwq, work);
 	bool cpu_intensive = cwq->wq->flags & WQ_CPU_INTENSIVE;
 	work_func_t f = work->func;
 	int work_color;
@@ -1818,7 +1757,7 @@ __acquires(&gcwq->lock)
 	 * already processing the work.  If so, defer the work to the
 	 * currently executing one.
 	 */
-	collision = __find_worker_executing_work(gcwq, bwh, work);
+	collision = find_worker_executing_work(gcwq, work);
 	if (unlikely(collision)) {
 		move_linked_works(work, &collision->scheduled, NULL);
 		return;
@@ -1826,7 +1765,7 @@ __acquires(&gcwq->lock)
 
 	/* claim and process */
 	debug_work_deactivate(work);
-	hlist_add_head(&worker->hentry, bwh);
+	HASH_ADD(gcwq->busy_hash, &worker->hentry, work);
 	worker->current_work = work;
 	worker->current_cwq = cwq;
 	work_color = get_work_color(work);
@@ -1889,7 +1828,7 @@ __acquires(&gcwq->lock)
 		worker_clr_flags(worker, WORKER_CPU_INTENSIVE);
 
 	/* we're done with it, release */
-	hlist_del_init(&worker->hentry);
+	HASH_DEL(worker, hentry);
 	worker->current_work = NULL;
 	worker->current_cwq = NULL;
 	cwq_dec_nr_in_flight(cwq, work_color, false);
@@ -3330,7 +3269,7 @@ static int __cpuinit trustee_thread(void *__gcwq)
 	list_for_each_entry(worker, &gcwq->idle_list, entry)
 		worker->flags |= WORKER_ROGUE;
 
-	for_each_busy_worker(worker, i, pos, gcwq)
+	HASH_FOR_EACH(i, pos, gcwq->busy_hash, worker, hentry)
 		worker->flags |= WORKER_ROGUE;
 
 	/*
@@ -3426,7 +3365,7 @@ static int __cpuinit trustee_thread(void *__gcwq)
 	 */
 	WARN_ON(!list_empty(&gcwq->idle_list));
 
-	for_each_busy_worker(worker, i, pos, gcwq) {
+	HASH_FOR_EACH(i, pos, gcwq->busy_hash, worker, hentry) {
 		struct work_struct *rebind_work = &worker->rebind_work;
 
 		/*
@@ -3768,7 +3707,6 @@ out_unlock:
 static int __init init_workqueues(void)
 {
 	unsigned int cpu;
-	int i;
 
 	cpu_notifier(workqueue_cpu_callback, CPU_PRI_WORKQUEUE);
 
@@ -3782,8 +3720,7 @@ static int __init init_workqueues(void)
 		gcwq->flags |= GCWQ_DISASSOCIATED;
 
 		INIT_LIST_HEAD(&gcwq->idle_list);
-		for (i = 0; i < BUSY_WORKER_HASH_SIZE; i++)
-			INIT_HLIST_HEAD(&gcwq->busy_hash[i]);
+		HASH_INIT(gcwq->busy_hash);
 
 		init_timer_deferrable(&gcwq->idle_timer);
 		gcwq->idle_timer.function = idle_worker_timeout;
-- 
1.7.8.6

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>