LinuxLists.cc - [PATCH v3 00/17] generic hashtable implementation

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On 08/24/2012 10:33 PM, Tejun Heo wrote:
> Hello, Sasha.
>
> On Fri, Aug 24, 2012 at 10:11:55PM +0200, Sasha Levin wrote:
>>> If this implementation is about the common trivial case, why not just
>>> have the usual DECLARE/DEFINE_HASHTABLE() combination?
>>
>> When we add the dynamic non-resizable support, how would DEFINE_HASHTABLE() look?
>
> Hmmm? DECLARE/DEFINE are usually for static ones.

Yup, but we could be using the same API for dynamic non-resizable and static if
we go with the DECLARE/hash_init. We could switch between them (and other
implementations) without having to change the code.

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

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

Consider the following list:

- DECLARE
- hash_init
- hash_add
- hash_del
- hash_hashed
- hash_for_each_[rcu, safe]
- hash_for_each_possible[rcu, safe]

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

>> I think that right now the only real trivial wrapper is hash_hashed(), and I
>> think it's a price worth paying to have a single hashtable API instead of
>> fragmenting it when more implementations come along.
>
> I'm not objecting strongly against full encapsulation but having this
> many thin wrappers makes me scratch my head.
>
> Thanks.
>

2012-08-22 18:05:06

[permalink] [raw]

Subject: Re: [PATCH v3 04/17] workqueue: use new hashtable implementation

On Wed, Aug 22, 2012 at 04:26:59AM +0200, Sasha Levin wrote:
> Switch workqueues to use the new hashtable implementation. This reduces the amount of
> generic unrelated code in the workqueues.
>
> Signed-off-by: Sasha Levin <[email protected]>

Acked-by: Tejun Heo <[email protected]>

Thanks.

--
tejun

2012-08-22 02:27:46

[permalink] [raw]

Subject: [PATCH v3 09/17] SUNRPC/cache: use new hashtable implementation

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

Signed-off-by: Sasha Levin <[email protected]>
---
net/sunrpc/cache.c | 20 +++++++++-----------
1 files changed, 9 insertions(+), 11 deletions(-)

diff --git a/net/sunrpc/cache.c b/net/sunrpc/cache.c
index 2afd2a8..8a8ef6d 100644
--- a/net/sunrpc/cache.c
+++ b/net/sunrpc/cache.c
@@ -28,6 +28,7 @@
#include <linux/workqueue.h>
#include <linux/mutex.h>
#include <linux/pagemap.h>
+#include <linux/hashtable.h>
#include <asm/ioctls.h>
#include <linux/sunrpc/types.h>
#include <linux/sunrpc/cache.h>
@@ -524,19 +525,18 @@ EXPORT_SYMBOL_GPL(cache_purge);
* it to be revisited when cache info is available
*/

-#define DFR_HASHSIZE (PAGE_SIZE/sizeof(struct list_head))
-#define DFR_HASH(item) ((((long)item)>>4 ^ (((long)item)>>13)) % DFR_HASHSIZE)
+#define DFR_HASH_BITS 9

#define DFR_MAX 300 /* ??? */

static DEFINE_SPINLOCK(cache_defer_lock);
static LIST_HEAD(cache_defer_list);
-static struct hlist_head cache_defer_hash[DFR_HASHSIZE];
+static DEFINE_HASHTABLE(cache_defer_hash, DFR_HASH_BITS)
static int cache_defer_cnt;

static void __unhash_deferred_req(struct cache_deferred_req *dreq)
{
- hlist_del_init(&dreq->hash);
+ hash_del(&dreq->hash);
if (!list_empty(&dreq->recent)) {
list_del_init(&dreq->recent);
cache_defer_cnt--;
@@ -545,10 +545,7 @@ static void __unhash_deferred_req(struct cache_deferred_req *dreq)

static void __hash_deferred_req(struct cache_deferred_req *dreq, struct cache_head *item)
{
- int hash = DFR_HASH(item);
-
- INIT_LIST_HEAD(&dreq->recent);
- hlist_add_head(&dreq->hash, &cache_defer_hash[hash]);
+ hash_add(cache_defer_hash, &dreq->hash, (unsigned long)item);
}

static void setup_deferral(struct cache_deferred_req *dreq,
@@ -600,7 +597,7 @@ static void cache_wait_req(struct cache_req *req, struct cache_head *item)
* to clean up
*/
spin_lock(&cache_defer_lock);
- if (!hlist_unhashed(&sleeper.handle.hash)) {
+ if (hash_hashed(&sleeper.handle.hash)) {
__unhash_deferred_req(&sleeper.handle);
spin_unlock(&cache_defer_lock);
} else {
@@ -671,12 +668,11 @@ static void cache_revisit_request(struct cache_head *item)
struct cache_deferred_req *dreq;
struct list_head pending;
struct hlist_node *lp, *tmp;
- int hash = DFR_HASH(item);

INIT_LIST_HEAD(&pending);
spin_lock(&cache_defer_lock);

- hlist_for_each_entry_safe(dreq, lp, tmp, &cache_defer_hash[hash], hash)
+ hash_for_each_possible_safe(cache_defer_hash, dreq, lp, tmp, hash, (unsigned long)item)
if (dreq->item == item) {
__unhash_deferred_req(dreq);
list_add(&dreq->recent, &pending);
@@ -1636,6 +1632,8 @@ static int create_cache_proc_entries(struct cache_detail *cd, struct net *net)
void __init cache_initialize(void)
{
INIT_DELAYED_WORK_DEFERRABLE(&cache_cleaner, do_cache_clean);
+
+ hash_init(cache_defer_hash);
}

int cache_register_net(struct cache_detail *cd, struct net *net)
--
1.7.8.6

2012-08-24 23:07:46

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

Hello,

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

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

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

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

Thanks.

--
tejun

2012-08-24 19:59:46

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

Hello, Sasha.

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

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

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

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

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

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

Thanks.

--
tejun

2012-08-24 20:11:30

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On 08/24/2012 09:59 PM, Tejun Heo wrote:
> Hello, Sasha.
>
> On Fri, Aug 24, 2012 at 09:47:19PM +0200, Sasha Levin wrote:
>>> I think this is problematic. It looks exactly like other existing
>>> DEFINE macros yet what its semantics is different. I don't think
>>> that's a good idea.
>>
>> I can switch that to be DECLARE_HASHTABLE() if the issue is semantics.
>
> If this implementation is about the common trivial case, why not just
> have the usual DECLARE/DEFINE_HASHTABLE() combination?

When we add the dynamic non-resizable support, how would DEFINE_HASHTABLE() look?

>>> So, I think it would be best to keep this one as straight-forward and
>>> trivial as possible. Helper macros to help its users are fine but
>>> let's please not go for full encapsulation.
>>
>> What if we cut off the dynamic allocated (but not resizable) hashtable out for
>> the moment, and focus on the most common statically allocated hashtable case?
>>
>> The benefits would be:
>>
>> - Getting rid of all the _size() macros, which will make the amount of helpers
>> here reasonable.
>> - Dynamically allocated hashtable can be easily added as a separate
>> implementation using the same API. We already have some of those in the kernel...
>
> It seems we have enough of this static usage and solving the static
> case first shouldn't hinder the dynamic (!resize) case later, so,
> yeah, sounds good to me.
>
>> - When that's ready, I feel it's a shame to lose full encapsulation just due to
>> hash_hashed().
>
> I don't know. If we stick to the static (or even !resize dymaic)
> straight-forward hash - and we need something like that - I don't see
> what the full encapsulation buys us other than a lot of trivial
> wrappers.

Which macros do you consider as trivial within the current API?

Basically this entire thing could be reduced to DEFINE/DECLARE_HASHTABLE and
get_bucket(), but it would make the life of anyone who wants a slightly
different hashtable a hell.

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

Thanks,
Sasha

>
> Thanks.
>

2012-08-22 11:48:22

by J. Bruce Fields

[permalink] [raw]

Subject: Re: [PATCH v3 13/17] lockd: use new hashtable implementation

On Wed, Aug 22, 2012 at 04:27:08AM +0200, Sasha Levin wrote:
> +static int __init nlm_init(void)
> +{
> + hash_init(nlm_files);
> + return 0;
> +}
> +
> +module_init(nlm_init);

That's giving me:

fs/lockd/svcsubs.o: In function `nlm_init':
/home/bfields/linux-2.6/fs/lockd/svcsubs.c:454: multiple definition of `init_module'
fs/lockd/svc.o:/home/bfields/linux-2.6/fs/lockd/svc.c:606: first defined here
make[2]: *** [fs/lockd/lockd.o] Error 1
make[1]: *** [fs/lockd] Error 2
make[1]: *** Waiting for unfinished jobs....

--b.

2012-08-22 02:27:40

[permalink] [raw]

Subject: [PATCH v3 08/17] block,elevator: use new hashtable implementation

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

This also removes the dymanic allocation of the hash table. The size of the table is
constant so there's no point in paying the price of an extra dereference when accessing
it.

Signed-off-by: Sasha Levin <[email protected]>
---
block/blk.h | 2 +-
block/elevator.c | 23 ++++-------------------
include/linux/elevator.h | 5 ++++-
3 files changed, 9 insertions(+), 21 deletions(-)

diff --git a/block/blk.h b/block/blk.h
index 2a0ea32..5650d48 100644
--- a/block/blk.h
+++ b/block/blk.h
@@ -61,7 +61,7 @@ static inline void blk_clear_rq_complete(struct request *rq)
/*
* Internal elevator interface
*/
-#define ELV_ON_HASH(rq) (!hlist_unhashed(&(rq)->hash))
+#define ELV_ON_HASH(rq) hash_hashed(&(rq)->hash)

void blk_insert_flush(struct request *rq);
void blk_abort_flushes(struct request_queue *q);
diff --git a/block/elevator.c b/block/elevator.c
index 6a55d41..f462a83 100644
--- a/block/elevator.c
+++ b/block/elevator.c
@@ -46,11 +46,6 @@ static LIST_HEAD(elv_list);
/*
* Merge hash stuff.
*/
-static const int elv_hash_shift = 6;
-#define ELV_HASH_BLOCK(sec) ((sec) >> 3)
-#define ELV_HASH_FN(sec) \
- (hash_long(ELV_HASH_BLOCK((sec)), elv_hash_shift))
-#define ELV_HASH_ENTRIES (1 << elv_hash_shift)
#define rq_hash_key(rq) (blk_rq_pos(rq) + blk_rq_sectors(rq))

/*
@@ -142,7 +137,6 @@ static struct elevator_queue *elevator_alloc(struct request_queue *q,
struct elevator_type *e)
{
struct elevator_queue *eq;
- int i;

eq = kmalloc_node(sizeof(*eq), GFP_KERNEL | __GFP_ZERO, q->node);
if (unlikely(!eq))
@@ -151,14 +145,7 @@ static struct elevator_queue *elevator_alloc(struct request_queue *q,
eq->type = e;
kobject_init(&eq->kobj, &elv_ktype);
mutex_init(&eq->sysfs_lock);
-
- eq->hash = kmalloc_node(sizeof(struct hlist_head) * ELV_HASH_ENTRIES,
- GFP_KERNEL, q->node);
- if (!eq->hash)
- goto err;
-
- for (i = 0; i < ELV_HASH_ENTRIES; i++)
- INIT_HLIST_HEAD(&eq->hash[i]);
+ hash_init(eq->hash);

return eq;
err:
@@ -173,7 +160,6 @@ static void elevator_release(struct kobject *kobj)

e = container_of(kobj, struct elevator_queue, kobj);
elevator_put(e->type);
- kfree(e->hash);
kfree(e);
}

@@ -240,7 +226,7 @@ EXPORT_SYMBOL(elevator_exit);

static inline void __elv_rqhash_del(struct request *rq)
{
- hlist_del_init(&rq->hash);
+ hash_del(&rq->hash);
}

static void elv_rqhash_del(struct request_queue *q, struct request *rq)
@@ -254,7 +240,7 @@ static void elv_rqhash_add(struct request_queue *q, struct request *rq)
struct elevator_queue *e = q->elevator;

BUG_ON(ELV_ON_HASH(rq));
- hlist_add_head(&rq->hash, &e->hash[ELV_HASH_FN(rq_hash_key(rq))]);
+ hash_add(e->hash, &rq->hash, rq_hash_key(rq));
}

static void elv_rqhash_reposition(struct request_queue *q, struct request *rq)
@@ -266,11 +252,10 @@ static void elv_rqhash_reposition(struct request_queue *q, struct request *rq)
static struct request *elv_rqhash_find(struct request_queue *q, sector_t offset)
{
struct elevator_queue *e = q->elevator;
- struct hlist_head *hash_list = &e->hash[ELV_HASH_FN(offset)];
struct hlist_node *entry, *next;
struct request *rq;

- hlist_for_each_entry_safe(rq, entry, next, hash_list, hash) {
+ hash_for_each_possible_safe(e->hash, rq, entry, next, hash, offset) {
BUG_ON(!ELV_ON_HASH(rq));

if (unlikely(!rq_mergeable(rq))) {
diff --git a/include/linux/elevator.h b/include/linux/elevator.h
index c03af76..20b539c 100644
--- a/include/linux/elevator.h
+++ b/include/linux/elevator.h
@@ -2,6 +2,7 @@
#define _LINUX_ELEVATOR_H

#include <linux/percpu.h>
+#include <linux/hashtable.h>

#ifdef CONFIG_BLOCK

@@ -96,6 +97,8 @@ struct elevator_type
struct list_head list;
};

+#define ELV_HASH_BITS 6
+
/*
* each queue has an elevator_queue associated with it
*/
@@ -105,7 +108,7 @@ struct elevator_queue
void *elevator_data;
struct kobject kobj;
struct mutex sysfs_lock;
- struct hlist_head *hash;
+ DEFINE_HASHTABLE(hash, ELV_HASH_BITS);
unsigned int registered:1;
};

--
1.7.8.6

2012-08-28 11:56:42

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

* Sasha Levin ([email protected]) wrote:
> On 08/28/2012 12:11 PM, Mathieu Desnoyers wrote:
> > * Sasha Levin ([email protected]) wrote:
> >> On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
> >>> * Tejun Heo ([email protected]) wrote:
> >>>> Hello,
> >>>>
> >>>> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> >>>>> Thats the thing, the amount of things of things you can do with a given bucket
> >>>>> is very limited. You can't add entries to any point besides the head (without
> >>>>> walking the entire list).
> >>>>
> >>>> Kinda my point. We already have all the hlist*() interface to deal
> >>>> with such cases. Having something which is evidently the trivial
> >>>> hlist hashtable and advertises as such in the interface can be
> >>>> helpful. I think we need that more than we need anything fancy.
> >>>>
> >>>> Heh, this is a debate about which one is less insignificant. I can
> >>>> see your point. I'd really like to hear what others think on this.
> >>>>
> >>>> Guys, do we want something which is evidently trivial hlist hashtable
> >>>> which can use hlist_*() API directly or do we want something better
> >>>> encapsulated?
> >>>
> >>> My 2 cents, FWIW: I think this specific effort should target a trivially
> >>> understandable API and implementation, for use-cases where one would be
> >>> tempted to reimplement his own trivial hash table anyway. So here
> >>> exposing hlist internals, with which kernel developers are already
> >>> familiar, seems like a good approach in my opinion, because hiding stuff
> >>> behind new abstraction might make the target users go away.
> >>>
> >>> Then, as we see the need, we can eventually merge a more elaborate hash
> >>> table with poneys and whatnot, but I would expect that the trivial hash
> >>> table implementation would still be useful. There are of course very
> >>> compelling reasons to use a more featureful hash table: automatic
> >>> resize, RT-aware updates, scalable updates, etc... but I see a purpose
> >>> for a trivial implementation. Its primary strong points being:
> >>>
> >>> - it's trivially understandable, so anyone how want to be really sure
> >>> they won't end up debugging the hash table instead of their
> >>> work-in-progress code can have a full understanding of it,
> >>> - it has few dependencies, which makes it easier to understand and
> >>> easier to use in some contexts (e.g. early boot).
> >>>
> >>> So I'm in favor of not overdoing the abstraction for this trivial hash
> >>> table, and honestly I would rather prefer that this trivial hash table
> >>> stays trivial. A more elaborate hash table should probably come as a
> >>> separate API.
> >>>
> >>> Thanks,
> >>>
> >>> Mathieu
> >>>
> >>
> >> Alright, let's keep it simple then.
> >>
> >> I do want to keep the hash_for_each[rcu,safe] family though.
> >
> > Just a thought: if the API offered by the simple hash table focus on
> > providing a mechanism to find the hash bucket to which belongs the hash
> > chain containing the key looked up, and then expects the user to use the
> > hlist API to iterate on the chain (with or without the hlist _rcu
> > variant), then it might seem consistent that a helper providing
> > iteration over the entire table would actually just provide iteration on
> > all buckets, and let the user call the hlist for each iterator for each
> > node within the bucket, e.g.:
> >
> > struct hlist_head *head;
> > struct hlist_node *pos;
> >
> > hash_for_each_bucket(ht, head) {
> > hlist_for_each(pos, head) {
> > ...
> > }
> > }
> >
> > That way you only have to provide one single macro
> > (hash_for_each_bucket), and rely on the already existing:
> >
> > - hlist_for_each_entry
> > - hlist_for_each_safe
> > - hlist_for_each_entry_rcu
> > - hlist_for_each_safe_rcu
> > .....
> >
> > and various flavors that can appear in the future without duplicating
> > this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
> > versions of the hash_for_each_bucket macro.
> >
> > Thoughts ?
>
> In my opinion, the downside here is that it'll require 2 function calls and 2
> levels of nesting for a simple hash iteration.

Those are macros, not functions. No function call is required. But I see
your point about nesting.

>
> hash_for_each_bucket() will always be followed by an iteration of that
> bucket, so splitting a hash_for_each() which does both into 2
> different functions which will almost always must be called in that
> given order sounds unintuitive to me.
>
> It's also just 3 different possible iterators:
>
> - hlist_for_each_entry
> - hlist_for_each_entry_safe
> - hlist_for_each_entry_rcu
>
> So I think that it's a good price to pay - 2 extra macro definitions
> in the header to save a macro call + nesting level in each place that
> uses a hashtable.

I must admin I don't care that much one way or another.

Thanks,

Mathieu

>
>
> Thanks,
> Sasha
>
> > Thanks,
> >
> > Mathieu
> >
>

--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

2012-08-22 02:28:11

[permalink] [raw]

Subject: [PATCH v3 12/17] dm: use new hashtable implementation

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

Signed-off-by: Sasha Levin <[email protected]>
---
drivers/md/dm-snap.c | 24 ++++-----------
drivers/md/persistent-data/dm-block-manager.c | 1 -
.../persistent-data/dm-persistent-data-internal.h | 19 ------------
.../md/persistent-data/dm-transaction-manager.c | 30 ++++++--------------
4 files changed, 16 insertions(+), 58 deletions(-)
delete mode 100644 drivers/md/persistent-data/dm-persistent-data-internal.h

diff --git a/drivers/md/dm-snap.c b/drivers/md/dm-snap.c
index a143921..7ac121f 100644
--- a/drivers/md/dm-snap.c
+++ b/drivers/md/dm-snap.c
@@ -34,9 +34,7 @@ static const char dm_snapshot_merge_target_name[] = "snapshot-merge";
*/
#define MIN_IOS 256

-#define DM_TRACKED_CHUNK_HASH_SIZE 16
-#define DM_TRACKED_CHUNK_HASH(x) ((unsigned long)(x) & \
- (DM_TRACKED_CHUNK_HASH_SIZE - 1))
+#define DM_TRACKED_CHUNK_HASH_BITS 4

struct dm_exception_table {
uint32_t hash_mask;
@@ -80,7 +78,7 @@ struct dm_snapshot {
/* Chunks with outstanding reads */
spinlock_t tracked_chunk_lock;
mempool_t *tracked_chunk_pool;
- struct hlist_head tracked_chunk_hash[DM_TRACKED_CHUNK_HASH_SIZE];
+ DEFINE_HASHTABLE(tracked_chunk_hash, DM_TRACKED_CHUNK_HASH_BITS);

/* The on disk metadata handler */
struct dm_exception_store *store;
@@ -203,8 +201,7 @@ static struct dm_snap_tracked_chunk *track_chunk(struct dm_snapshot *s,
c->chunk = chunk;

spin_lock_irqsave(&s->tracked_chunk_lock, flags);
- hlist_add_head(&c->node,
- &s->tracked_chunk_hash[DM_TRACKED_CHUNK_HASH(chunk)]);
+ hash_add(s->tracked_chunk_hash, &c->node, chunk);
spin_unlock_irqrestore(&s->tracked_chunk_lock, flags);

return c;
@@ -216,7 +213,7 @@ static void stop_tracking_chunk(struct dm_snapshot *s,
unsigned long flags;

spin_lock_irqsave(&s->tracked_chunk_lock, flags);
- hlist_del(&c->node);
+ hash_del(&c->node);
spin_unlock_irqrestore(&s->tracked_chunk_lock, flags);

mempool_free(c, s->tracked_chunk_pool);
@@ -230,8 +227,7 @@ static int __chunk_is_tracked(struct dm_snapshot *s, chunk_t chunk)

spin_lock_irq(&s->tracked_chunk_lock);

- hlist_for_each_entry(c, hn,
- &s->tracked_chunk_hash[DM_TRACKED_CHUNK_HASH(chunk)], node) {
+ hash_for_each_possible(s->tracked_chunk_hash, c, hn, node, chunk) {
if (c->chunk == chunk) {
found = 1;
break;
@@ -1033,7 +1029,6 @@ static void stop_merge(struct dm_snapshot *s)
static int snapshot_ctr(struct dm_target *ti, unsigned int argc, char **argv)
{
struct dm_snapshot *s;
- int i;
int r = -EINVAL;
char *origin_path, *cow_path;
unsigned args_used, num_flush_requests = 1;
@@ -1128,8 +1123,7 @@ static int snapshot_ctr(struct dm_target *ti, unsigned int argc, char **argv)
goto bad_tracked_chunk_pool;
}

- for (i = 0; i < DM_TRACKED_CHUNK_HASH_SIZE; i++)
- INIT_HLIST_HEAD(&s->tracked_chunk_hash[i]);
+ hash_init(s->tracked_chunk_hash);

spin_lock_init(&s->tracked_chunk_lock);

@@ -1253,9 +1247,6 @@ static void __handover_exceptions(struct dm_snapshot *snap_src,

static void snapshot_dtr(struct dm_target *ti)
{
-#ifdef CONFIG_DM_DEBUG
- int i;
-#endif
struct dm_snapshot *s = ti->private;
struct dm_snapshot *snap_src = NULL, *snap_dest = NULL;

@@ -1286,8 +1277,7 @@ static void snapshot_dtr(struct dm_target *ti)
smp_mb();

#ifdef CONFIG_DM_DEBUG
- for (i = 0; i < DM_TRACKED_CHUNK_HASH_SIZE; i++)
- BUG_ON(!hlist_empty(&s->tracked_chunk_hash[i]));
+ BUG_ON(!hash_empty(s->tracked_chunk_hash));
#endif

mempool_destroy(s->tracked_chunk_pool);
diff --git a/drivers/md/persistent-data/dm-block-manager.c b/drivers/md/persistent-data/dm-block-manager.c
index 5ba2777..31edaf13 100644
--- a/drivers/md/persistent-data/dm-block-manager.c
+++ b/drivers/md/persistent-data/dm-block-manager.c
@@ -4,7 +4,6 @@
* This file is released under the GPL.
*/
#include "dm-block-manager.h"
-#include "dm-persistent-data-internal.h"
#include "../dm-bufio.h"

#include <linux/crc32c.h>
diff --git a/drivers/md/persistent-data/dm-persistent-data-internal.h b/drivers/md/persistent-data/dm-persistent-data-internal.h
deleted file mode 100644
index c49e26f..0000000
--- a/drivers/md/persistent-data/dm-persistent-data-internal.h
+++ /dev/null
@@ -1,19 +0,0 @@
-/*
- * Copyright (C) 2011 Red Hat, Inc.
- *
- * This file is released under the GPL.
- */
-
-#ifndef _DM_PERSISTENT_DATA_INTERNAL_H
-#define _DM_PERSISTENT_DATA_INTERNAL_H
-
-#include "dm-block-manager.h"
-
-static inline unsigned dm_hash_block(dm_block_t b, unsigned hash_mask)
-{
- const unsigned BIG_PRIME = 4294967291UL;
-
- return (((unsigned) b) * BIG_PRIME) & hash_mask;
-}
-
-#endif /* _PERSISTENT_DATA_INTERNAL_H */
diff --git a/drivers/md/persistent-data/dm-transaction-manager.c b/drivers/md/persistent-data/dm-transaction-manager.c
index d247a35..a57c4ed 100644
--- a/drivers/md/persistent-data/dm-transaction-manager.c
+++ b/drivers/md/persistent-data/dm-transaction-manager.c
@@ -7,11 +7,11 @@
#include "dm-space-map.h"
#include "dm-space-map-disk.h"
#include "dm-space-map-metadata.h"
-#include "dm-persistent-data-internal.h"

#include <linux/export.h>
#include <linux/slab.h>
#include <linux/device-mapper.h>
+#include <linux/hashtable.h>

#define DM_MSG_PREFIX "transaction manager"

@@ -25,8 +25,7 @@ struct shadow_info {
/*
* It would be nice if we scaled with the size of transaction.
*/
-#define HASH_SIZE 256
-#define HASH_MASK (HASH_SIZE - 1)
+#define DM_HASH_BITS 8

struct dm_transaction_manager {
int is_clone;
@@ -36,7 +35,7 @@ struct dm_transaction_manager {
struct dm_space_map *sm;

spinlock_t lock;
- struct hlist_head buckets[HASH_SIZE];
+ DEFINE_HASHTABLE(hash, DM_HASH_BITS);
};

/*----------------------------------------------------------------*/
@@ -44,12 +43,11 @@ struct dm_transaction_manager {
static int is_shadow(struct dm_transaction_manager *tm, dm_block_t b)
{
int r = 0;
- unsigned bucket = dm_hash_block(b, HASH_MASK);
struct shadow_info *si;
struct hlist_node *n;

spin_lock(&tm->lock);
- hlist_for_each_entry(si, n, tm->buckets + bucket, hlist)
+ hash_for_each_possible(tm->hash, si, n, hlist, b)
if (si->where == b) {
r = 1;
break;
@@ -65,15 +63,13 @@ static int is_shadow(struct dm_transaction_manager *tm, dm_block_t b)
*/
static void insert_shadow(struct dm_transaction_manager *tm, dm_block_t b)
{
- unsigned bucket;
struct shadow_info *si;

si = kmalloc(sizeof(*si), GFP_NOIO);
if (si) {
si->where = b;
- bucket = dm_hash_block(b, HASH_MASK);
spin_lock(&tm->lock);
- hlist_add_head(&si->hlist, tm->buckets + bucket);
+ hash_add(tm->hash, &si->hlist, b);
spin_unlock(&tm->lock);
}
}
@@ -82,18 +78,12 @@ static void wipe_shadow_table(struct dm_transaction_manager *tm)
{
struct shadow_info *si;
struct hlist_node *n, *tmp;
- struct hlist_head *bucket;
int i;

spin_lock(&tm->lock);
- for (i = 0; i < HASH_SIZE; i++) {
- bucket = tm->buckets + i;
- hlist_for_each_entry_safe(si, n, tmp, bucket, hlist)
- kfree(si);
-
- INIT_HLIST_HEAD(bucket);
- }
-
+ hash_for_each_safe(tm->hash, i, n, tmp, si, hlist)
+ kfree(si);
+ hash_init(tm->hash);
spin_unlock(&tm->lock);
}

@@ -102,7 +92,6 @@ static void wipe_shadow_table(struct dm_transaction_manager *tm)
static struct dm_transaction_manager *dm_tm_create(struct dm_block_manager *bm,
struct dm_space_map *sm)
{
- int i;
struct dm_transaction_manager *tm;

tm = kmalloc(sizeof(*tm), GFP_KERNEL);
@@ -115,8 +104,7 @@ static struct dm_transaction_manager *dm_tm_create(struct dm_block_manager *bm,
tm->sm = sm;

spin_lock_init(&tm->lock);
- for (i = 0; i < HASH_SIZE; i++)
- INIT_HLIST_HEAD(tm->buckets + i);
+ hash_init(tm->hash);

return tm;
}
--
1.7.8.6

2012-08-22 02:27:21

[permalink] [raw]

Subject: [PATCH v3 05/17] mm/huge_memory: use new hashtable implementation

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

This also removes the dymanic allocation of the hash table. The size of the table is
constant so there's no point in paying the price of an extra dereference when accessing
it.

Signed-off-by: Sasha Levin <[email protected]>
---
mm/huge_memory.c | 57 ++++++++++++++---------------------------------------
1 files changed, 15 insertions(+), 42 deletions(-)

diff --git a/mm/huge_memory.c b/mm/huge_memory.c
index 8b3c55a..cebe345 100644
--- a/mm/huge_memory.c
+++ b/mm/huge_memory.c
@@ -17,6 +17,7 @@
#include <linux/khugepaged.h>
#include <linux/freezer.h>
#include <linux/mman.h>
+#include <linux/hashtable.h>
#include <asm/tlb.h>
#include <asm/pgalloc.h>
#include "internal.h"
@@ -57,12 +58,12 @@ static DECLARE_WAIT_QUEUE_HEAD(khugepaged_wait);
static unsigned int khugepaged_max_ptes_none __read_mostly = HPAGE_PMD_NR-1;

static int khugepaged(void *none);
-static int mm_slots_hash_init(void);
static int khugepaged_slab_init(void);
static void khugepaged_slab_free(void);

-#define MM_SLOTS_HASH_HEADS 1024
-static struct hlist_head *mm_slots_hash __read_mostly;
+#define MM_SLOTS_HASH_BITS 10
+static DEFINE_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_BITS);
+
static struct kmem_cache *mm_slot_cache __read_mostly;

/**
@@ -140,7 +141,7 @@ static int start_khugepaged(void)
int err = 0;
if (khugepaged_enabled()) {
int wakeup;
- if (unlikely(!mm_slot_cache || !mm_slots_hash)) {
+ if (unlikely(!mm_slot_cache)) {
err = -ENOMEM;
goto out;
}
@@ -554,12 +555,6 @@ static int __init hugepage_init(void)
if (err)
goto out;

- err = mm_slots_hash_init();
- if (err) {
- khugepaged_slab_free();
- goto out;
- }
-
/*
* By default disable transparent hugepages on smaller systems,
* where the extra memory used could hurt more than TLB overhead
@@ -1540,6 +1535,8 @@ static int __init khugepaged_slab_init(void)
if (!mm_slot_cache)
return -ENOMEM;

+ hash_init(mm_slots_hash);
+
return 0;
}

@@ -1561,47 +1558,23 @@ static inline void free_mm_slot(struct mm_slot *mm_slot)
kmem_cache_free(mm_slot_cache, mm_slot);
}

-static int __init mm_slots_hash_init(void)
-{
- mm_slots_hash = kzalloc(MM_SLOTS_HASH_HEADS * sizeof(struct hlist_head),
- GFP_KERNEL);
- if (!mm_slots_hash)
- return -ENOMEM;
- return 0;
-}
-
-#if 0
-static void __init mm_slots_hash_free(void)
-{
- kfree(mm_slots_hash);
- mm_slots_hash = NULL;
-}
-#endif
-
static struct mm_slot *get_mm_slot(struct mm_struct *mm)
{
- struct mm_slot *mm_slot;
- struct hlist_head *bucket;
+ struct mm_slot *slot;
struct hlist_node *node;

- bucket = &mm_slots_hash[((unsigned long)mm / sizeof(struct mm_struct))
- % MM_SLOTS_HASH_HEADS];
- hlist_for_each_entry(mm_slot, node, bucket, hash) {
- if (mm == mm_slot->mm)
- return mm_slot;
- }
+ hash_for_each_possible(mm_slots_hash, slot, node, hash, (unsigned long) mm)
+ if (slot->mm == mm)
+ return slot;
+
return NULL;
}

static void insert_to_mm_slots_hash(struct mm_struct *mm,
struct mm_slot *mm_slot)
{
- struct hlist_head *bucket;
-
- bucket = &mm_slots_hash[((unsigned long)mm / sizeof(struct mm_struct))
- % MM_SLOTS_HASH_HEADS];
mm_slot->mm = mm;
- hlist_add_head(&mm_slot->hash, bucket);
+ hash_add(mm_slots_hash, &mm_slot->hash, (long)mm);
}

static inline int khugepaged_test_exit(struct mm_struct *mm)
@@ -1670,7 +1643,7 @@ void __khugepaged_exit(struct mm_struct *mm)
spin_lock(&khugepaged_mm_lock);
mm_slot = get_mm_slot(mm);
if (mm_slot && khugepaged_scan.mm_slot != mm_slot) {
- hlist_del(&mm_slot->hash);
+ hash_del(&mm_slot->hash);
list_del(&mm_slot->mm_node);
free = 1;
}
@@ -2080,7 +2053,7 @@ static void collect_mm_slot(struct mm_slot *mm_slot)

if (khugepaged_test_exit(mm)) {
/* free mm_slot */
- hlist_del(&mm_slot->hash);
+ hash_del(&mm_slot->hash);
list_del(&mm_slot->mm_node);

/*
--
1.7.8.6

2012-08-22 02:27:15

[permalink] [raw]

Subject: [PATCH v3 04/17] workqueue: use new hashtable implementation

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

Signed-off-by: Sasha Levin <[email protected]>
---
kernel/workqueue.c | 86 +++++++++-------------------------------------------
1 files changed, 15 insertions(+), 71 deletions(-)

diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index 11723c5..fca751e 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"

@@ -82,8 +83,6 @@ enum {
NR_WORKER_POOLS = 2, /* # worker pools per gcwq */

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 */
@@ -180,7 +179,7 @@ struct global_cwq {
unsigned int flags; /* L: GCWQ_* flags */

/* workers are chained either in busy_hash or pool idle_list */
- struct hlist_head busy_hash[BUSY_WORKER_HASH_SIZE];
+ DEFINE_HASHTABLE(busy_hash, BUSY_WORKER_HASH_ORDER);
/* L: hash of busy workers */

struct worker_pool pools[2]; /* normal and highpri pools */
@@ -288,8 +287,7 @@ EXPORT_SYMBOL_GPL(system_nrt_freezable_wq);
(pool) < &(gcwq)->pools[NR_WORKER_POOLS]; (pool)++)

#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)
+ hash_for_each(gcwq->busy_hash, i, pos, worker, hentry)

static inline int __next_gcwq_cpu(int cpu, const struct cpumask *mask,
unsigned int sw)
@@ -845,63 +843,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
@@ -920,8 +861,14 @@ 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);
+ struct worker *worker;
+ struct hlist_node *tmp;
+
+ hash_for_each_possible(gcwq->busy_hash, worker, tmp, hentry, (unsigned long)work)
+ if (worker->current_work == work)
+ return worker;
+
+ return NULL;
}

/**
@@ -2120,7 +2067,6 @@ __acquires(&gcwq->lock)
struct cpu_workqueue_struct *cwq = get_work_cwq(work);
struct worker_pool *pool = worker->pool;
struct global_cwq *gcwq = pool->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;
@@ -2152,7 +2098,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;
@@ -2160,7 +2106,7 @@ __acquires(&gcwq->lock)

/* claim and dequeue */
debug_work_deactivate(work);
- hlist_add_head(&worker->hentry, bwh);
+ hash_add(gcwq->busy_hash, &worker->hentry, (unsigned long)worker);
worker->current_work = work;
worker->current_cwq = cwq;
work_color = get_work_color(work);
@@ -2223,7 +2169,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);
@@ -3855,7 +3801,6 @@ out_unlock:
static int __init init_workqueues(void)
{
unsigned int cpu;
- int i;

/* make sure we have enough bits for OFFQ CPU number */
BUILD_BUG_ON((1LU << (BITS_PER_LONG - WORK_OFFQ_CPU_SHIFT)) <
@@ -3873,8 +3818,7 @@ static int __init init_workqueues(void)
gcwq->cpu = cpu;
gcwq->flags |= GCWQ_DISASSOCIATED;

- for (i = 0; i < BUSY_WORKER_HASH_SIZE; i++)
- INIT_HLIST_HEAD(&gcwq->busy_hash[i]);
+ hash_init(gcwq->busy_hash);

for_each_worker_pool(pool, gcwq) {
pool->gcwq = gcwq;
--
1.7.8.6

2012-08-24 19:46:52

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

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

I can switch that to be DECLARE_HASHTABLE() if the issue is semantics.

>> I'm actually tempted in hiding hlist completely from hashtable users, probably
>> by simply defining a hash_head/hash_node on top of the hlist_ counterparts.
>
> I think that it would be best to keep this one simple & obvious, which
> already has enough in-kernel users to justify its existence. There
> are significant benefits in being trivially understandable and
> expectable. If we want more advanced ones - say resizing, hybrid or
> what not, let's make that a separate one. No need to complicate the
> common straight-forward case for that.
>
> So, I think it would be best to keep this one as straight-forward and
> trivial as possible. Helper macros to help its users are fine but
> let's please not go for full encapsulation.

What if we cut off the dynamic allocated (but not resizable) hashtable out for
the moment, and focus on the most common statically allocated hashtable case?

The benefits would be:

- Getting rid of all the _size() macros, which will make the amount of helpers
here reasonable.
- Dynamically allocated hashtable can be easily added as a separate
implementation using the same API. We already have some of those in the kernel...
- When that's ready, I feel it's a shame to lose full encapsulation just due to
hash_hashed().

Thanks,
Sasha

>
> Thanks.
>

2012-08-24 21:23:53

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

Hello,

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

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

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

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

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

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

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

Thanks.

--
tejun

2012-08-22 02:27:03

[permalink] [raw]

Subject: [PATCH v3 02/17] userns: use new hashtable implementation

Switch to using the new hashtable implementation to store user structs.
This reduces the amount of generic unrelated code in kernel/user.c.

Signed-off-by: Sasha Levin <[email protected]>
---
kernel/user.c | 33 +++++++++++++--------------------
1 files changed, 13 insertions(+), 20 deletions(-)

diff --git a/kernel/user.c b/kernel/user.c
index b815fef..d10c484 100644
--- a/kernel/user.c
+++ b/kernel/user.c
@@ -16,6 +16,7 @@
#include <linux/interrupt.h>
#include <linux/export.h>
#include <linux/user_namespace.h>
+#include <linux/hashtable.h>

/*
* userns count is 1 for root user, 1 for init_uts_ns,
@@ -52,13 +53,9 @@ EXPORT_SYMBOL_GPL(init_user_ns);
*/

#define UIDHASH_BITS (CONFIG_BASE_SMALL ? 3 : 7)
-#define UIDHASH_SZ (1 << UIDHASH_BITS)
-#define UIDHASH_MASK (UIDHASH_SZ - 1)
-#define __uidhashfn(uid) (((uid >> UIDHASH_BITS) + uid) & UIDHASH_MASK)
-#define uidhashentry(uid) (uidhash_table + __uidhashfn((__kuid_val(uid))))

static struct kmem_cache *uid_cachep;
-struct hlist_head uidhash_table[UIDHASH_SZ];
+static DEFINE_HASHTABLE(uidhash_table, UIDHASH_BITS)

/*
* The uidhash_lock is mostly taken from process context, but it is
@@ -84,22 +81,22 @@ struct user_struct root_user = {
/*
* These routines must be called with the uidhash spinlock held!
*/
-static void uid_hash_insert(struct user_struct *up, struct hlist_head *hashent)
+static void uid_hash_insert(struct user_struct *up)
{
- hlist_add_head(&up->uidhash_node, hashent);
+ hash_add(uidhash_table, &up->uidhash_node, __kuid_val(up->uid));
}

static void uid_hash_remove(struct user_struct *up)
{
- hlist_del_init(&up->uidhash_node);
+ hash_del(&up->uidhash_node);
}

-static struct user_struct *uid_hash_find(kuid_t uid, struct hlist_head *hashent)
+static struct user_struct *uid_hash_find(kuid_t uid)
{
struct user_struct *user;
struct hlist_node *h;

- hlist_for_each_entry(user, h, hashent, uidhash_node) {
+ hash_for_each_possible(uidhash_table, user, h, uidhash_node, __kuid_val(uid)) {
if (uid_eq(user->uid, uid)) {
atomic_inc(&user->__count);
return user;
@@ -135,7 +132,7 @@ struct user_struct *find_user(kuid_t uid)
unsigned long flags;

spin_lock_irqsave(&uidhash_lock, flags);
- ret = uid_hash_find(uid, uidhashentry(uid));
+ ret = uid_hash_find(uid);
spin_unlock_irqrestore(&uidhash_lock, flags);
return ret;
}
@@ -156,11 +153,10 @@ void free_uid(struct user_struct *up)

struct user_struct *alloc_uid(kuid_t uid)
{
- struct hlist_head *hashent = uidhashentry(uid);
struct user_struct *up, *new;

spin_lock_irq(&uidhash_lock);
- up = uid_hash_find(uid, hashent);
+ up = uid_hash_find(uid);
spin_unlock_irq(&uidhash_lock);

if (!up) {
@@ -176,13 +172,13 @@ struct user_struct *alloc_uid(kuid_t uid)
* on adding the same user already..
*/
spin_lock_irq(&uidhash_lock);
- up = uid_hash_find(uid, hashent);
+ up = uid_hash_find(uid);
if (up) {
key_put(new->uid_keyring);
key_put(new->session_keyring);
kmem_cache_free(uid_cachep, new);
} else {
- uid_hash_insert(new, hashent);
+ uid_hash_insert(new);
up = new;
}
spin_unlock_irq(&uidhash_lock);
@@ -196,17 +192,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(uidhash_table + n);
+ hash_init(uidhash_table);

/* Insert the root user immediately (init already runs as root) */
spin_lock_irq(&uidhash_lock);
- uid_hash_insert(&root_user, uidhashentry(GLOBAL_ROOT_UID));
+ uid_hash_insert(&root_user);
spin_unlock_irq(&uidhash_lock);

return 0;
--
1.7.8.6

2012-08-22 02:28:23

[permalink] [raw]

Subject: [PATCH v3 14/17] net,rds: use new hashtable implementation

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

Signed-off-by: Sasha Levin <[email protected]>
---
net/rds/bind.c | 28 +++++++++-----
net/rds/connection.c | 102 ++++++++++++++++++++++----------------------------
2 files changed, 63 insertions(+), 67 deletions(-)

diff --git a/net/rds/bind.c b/net/rds/bind.c
index 637bde5..79d65ce 100644
--- a/net/rds/bind.c
+++ b/net/rds/bind.c
@@ -36,16 +36,16 @@
#include <linux/if_arp.h>
#include <linux/jhash.h>
#include <linux/ratelimit.h>
+#include <linux/hashtable.h>
#include "rds.h"

-#define BIND_HASH_SIZE 1024
-static struct hlist_head bind_hash_table[BIND_HASH_SIZE];
+#define BIND_HASH_BITS 10
+static DEFINE_HASHTABLE(bind_hash_table, BIND_HASH_BITS);
static DEFINE_SPINLOCK(rds_bind_lock);

-static struct hlist_head *hash_to_bucket(__be32 addr, __be16 port)
+static u32 rds_hash(__be32 addr, __be16 port)
{
- return bind_hash_table + (jhash_2words((u32)addr, (u32)port, 0) &
- (BIND_HASH_SIZE - 1));
+ return jhash_2words((u32)addr, (u32)port, 0);
}

static struct rds_sock *rds_bind_lookup(__be32 addr, __be16 port,
@@ -53,12 +53,12 @@ static struct rds_sock *rds_bind_lookup(__be32 addr, __be16 port,
{
struct rds_sock *rs;
struct hlist_node *node;
- struct hlist_head *head = hash_to_bucket(addr, port);
+ u32 key = rds_hash(addr, port);
u64 cmp;
u64 needle = ((u64)be32_to_cpu(addr) << 32) | be16_to_cpu(port);

rcu_read_lock();
- hlist_for_each_entry_rcu(rs, node, head, rs_bound_node) {
+ hash_for_each_possible_rcu(bind_hash_table, rs, node, rs_bound_node, key) {
cmp = ((u64)be32_to_cpu(rs->rs_bound_addr) << 32) |
be16_to_cpu(rs->rs_bound_port);

@@ -74,13 +74,13 @@ static struct rds_sock *rds_bind_lookup(__be32 addr, __be16 port,
* make sure our addr and port are set before
* we are added to the list, other people
* in rcu will find us as soon as the
- * hlist_add_head_rcu is done
+ * hash_add_rcu is done
*/
insert->rs_bound_addr = addr;
insert->rs_bound_port = port;
rds_sock_addref(insert);

- hlist_add_head_rcu(&insert->rs_bound_node, head);
+ hash_add_rcu(bind_hash_table, &insert->rs_bound_node, key);
}
return NULL;
}
@@ -152,7 +152,7 @@ void rds_remove_bound(struct rds_sock *rs)
rs, &rs->rs_bound_addr,
ntohs(rs->rs_bound_port));

- hlist_del_init_rcu(&rs->rs_bound_node);
+ hash_del_rcu(&rs->rs_bound_node);
rds_sock_put(rs);
rs->rs_bound_addr = 0;
}
@@ -202,3 +202,11 @@ out:
synchronize_rcu();
return ret;
}
+
+static int __init rds_init(void)
+{
+ hash_init(bind_hash_table);
+ return 0;
+}
+
+module_init(rds_init);
diff --git a/net/rds/connection.c b/net/rds/connection.c
index 9e07c75..5b09ee1 100644
--- a/net/rds/connection.c
+++ b/net/rds/connection.c
@@ -34,28 +34,24 @@
#include <linux/list.h>
#include <linux/slab.h>
#include <linux/export.h>
+#include <linux/hashtable.h>
#include <net/inet_hashtables.h>

#include "rds.h"
#include "loop.h"

#define RDS_CONNECTION_HASH_BITS 12
-#define RDS_CONNECTION_HASH_ENTRIES (1 << RDS_CONNECTION_HASH_BITS)
-#define RDS_CONNECTION_HASH_MASK (RDS_CONNECTION_HASH_ENTRIES - 1)

/* converting this to RCU is a chore for another day.. */
static DEFINE_SPINLOCK(rds_conn_lock);
static unsigned long rds_conn_count;
-static struct hlist_head rds_conn_hash[RDS_CONNECTION_HASH_ENTRIES];
+static DEFINE_HASHTABLE(rds_conn_hash, RDS_CONNECTION_HASH_BITS);
static struct kmem_cache *rds_conn_slab;

-static struct hlist_head *rds_conn_bucket(__be32 laddr, __be32 faddr)
+static unsigned long rds_conn_hashfn(__be32 laddr, __be32 faddr)
{
/* Pass NULL, don't need struct net for hash */
- unsigned long hash = inet_ehashfn(NULL,
- be32_to_cpu(laddr), 0,
- be32_to_cpu(faddr), 0);
- return &rds_conn_hash[hash & RDS_CONNECTION_HASH_MASK];
+ return inet_ehashfn(NULL, be32_to_cpu(laddr), 0, be32_to_cpu(faddr), 0);
}

#define rds_conn_info_set(var, test, suffix) do { \
@@ -64,14 +60,14 @@ static struct hlist_head *rds_conn_bucket(__be32 laddr, __be32 faddr)
} while (0)

/* rcu read lock must be held or the connection spinlock */
-static struct rds_connection *rds_conn_lookup(struct hlist_head *head,
- __be32 laddr, __be32 faddr,
+static struct rds_connection *rds_conn_lookup(__be32 laddr, __be32 faddr,
struct rds_transport *trans)
{
struct rds_connection *conn, *ret = NULL;
struct hlist_node *pos;
+ unsigned long key = rds_conn_hashfn(laddr, faddr);

- hlist_for_each_entry_rcu(conn, pos, head, c_hash_node) {
+ hash_for_each_possible_rcu(rds_conn_hash, conn, pos, c_hash_node, key) {
if (conn->c_faddr == faddr && conn->c_laddr == laddr &&
conn->c_trans == trans) {
ret = conn;
@@ -117,13 +113,12 @@ static struct rds_connection *__rds_conn_create(__be32 laddr, __be32 faddr,
int is_outgoing)
{
struct rds_connection *conn, *parent = NULL;
- struct hlist_head *head = rds_conn_bucket(laddr, faddr);
struct rds_transport *loop_trans;
unsigned long flags;
int ret;

rcu_read_lock();
- conn = rds_conn_lookup(head, laddr, faddr, trans);
+ conn = rds_conn_lookup(laddr, faddr, trans);
if (conn && conn->c_loopback && conn->c_trans != &rds_loop_transport &&
!is_outgoing) {
/* This is a looped back IB connection, and we're
@@ -224,13 +219,15 @@ static struct rds_connection *__rds_conn_create(__be32 laddr, __be32 faddr,
/* Creating normal conn */
struct rds_connection *found;

- found = rds_conn_lookup(head, laddr, faddr, trans);
+ found = rds_conn_lookup(laddr, faddr, trans);
if (found) {
trans->conn_free(conn->c_transport_data);
kmem_cache_free(rds_conn_slab, conn);
conn = found;
} else {
- hlist_add_head_rcu(&conn->c_hash_node, head);
+ unsigned long key = rds_conn_hashfn(laddr, faddr);
+
+ hash_add_rcu(rds_conn_hash, &conn->c_hash_node, key);
rds_cong_add_conn(conn);
rds_conn_count++;
}
@@ -303,7 +300,7 @@ void rds_conn_shutdown(struct rds_connection *conn)
* conn - the reconnect is always triggered by the active peer. */
cancel_delayed_work_sync(&conn->c_conn_w);
rcu_read_lock();
- if (!hlist_unhashed(&conn->c_hash_node)) {
+ if (hash_hashed(&conn->c_hash_node)) {
rcu_read_unlock();
rds_queue_reconnect(conn);
} else {
@@ -329,7 +326,7 @@ void rds_conn_destroy(struct rds_connection *conn)

/* Ensure conn will not be scheduled for reconnect */
spin_lock_irq(&rds_conn_lock);
- hlist_del_init_rcu(&conn->c_hash_node);
+ hash_del(&conn->c_hash_node);
spin_unlock_irq(&rds_conn_lock);
synchronize_rcu();

@@ -375,7 +372,6 @@ static void rds_conn_message_info(struct socket *sock, unsigned int len,
struct rds_info_lengths *lens,
int want_send)
{
- struct hlist_head *head;
struct hlist_node *pos;
struct list_head *list;
struct rds_connection *conn;
@@ -388,27 +384,24 @@ static void rds_conn_message_info(struct socket *sock, unsigned int len,

rcu_read_lock();

- for (i = 0, head = rds_conn_hash; i < ARRAY_SIZE(rds_conn_hash);
- i++, head++) {
- hlist_for_each_entry_rcu(conn, pos, head, c_hash_node) {
- if (want_send)
- list = &conn->c_send_queue;
- else
- list = &conn->c_retrans;
-
- spin_lock_irqsave(&conn->c_lock, flags);
-
- /* XXX too lazy to maintain counts.. */
- list_for_each_entry(rm, list, m_conn_item) {
- total++;
- if (total <= len)
- rds_inc_info_copy(&rm->m_inc, iter,
- conn->c_laddr,
- conn->c_faddr, 0);
- }
-
- spin_unlock_irqrestore(&conn->c_lock, flags);
+ hash_for_each_rcu(rds_conn_hash, i, pos, conn, c_hash_node) {
+ if (want_send)
+ list = &conn->c_send_queue;
+ else
+ list = &conn->c_retrans;
+
+ spin_lock_irqsave(&conn->c_lock, flags);
+
+ /* XXX too lazy to maintain counts.. */
+ list_for_each_entry(rm, list, m_conn_item) {
+ total++;
+ if (total <= len)
+ rds_inc_info_copy(&rm->m_inc, iter,
+ conn->c_laddr,
+ conn->c_faddr, 0);
}
+
+ spin_unlock_irqrestore(&conn->c_lock, flags);
}
rcu_read_unlock();

@@ -438,7 +431,6 @@ void rds_for_each_conn_info(struct socket *sock, unsigned int len,
size_t item_len)
{
uint64_t buffer[(item_len + 7) / 8];
- struct hlist_head *head;
struct hlist_node *pos;
struct rds_connection *conn;
size_t i;
@@ -448,23 +440,19 @@ void rds_for_each_conn_info(struct socket *sock, unsigned int len,
lens->nr = 0;
lens->each = item_len;

- for (i = 0, head = rds_conn_hash; i < ARRAY_SIZE(rds_conn_hash);
- i++, head++) {
- hlist_for_each_entry_rcu(conn, pos, head, c_hash_node) {
-
- /* XXX no c_lock usage.. */
- if (!visitor(conn, buffer))
- continue;
-
- /* We copy as much as we can fit in the buffer,
- * but we count all items so that the caller
- * can resize the buffer. */
- if (len >= item_len) {
- rds_info_copy(iter, buffer, item_len);
- len -= item_len;
- }
- lens->nr++;
+ hash_for_each_rcu(rds_conn_hash, i, pos, conn, c_hash_node) {
+ /* XXX no c_lock usage.. */
+ if (!visitor(conn, buffer))
+ continue;
+
+ /* We copy as much as we can fit in the buffer,
+ * but we count all items so that the caller
+ * can resize the buffer. */
+ if (len >= item_len) {
+ rds_info_copy(iter, buffer, item_len);
+ len -= item_len;
}
+ lens->nr++;
}
rcu_read_unlock();
}
@@ -518,6 +506,8 @@ int rds_conn_init(void)
rds_info_register_func(RDS_INFO_RETRANS_MESSAGES,
rds_conn_message_info_retrans);

+ hash_init(rds_conn_hash);
+
return 0;
}

@@ -525,8 +515,6 @@ void rds_conn_exit(void)
{
rds_loop_exit();

- WARN_ON(!hlist_empty(rds_conn_hash));
-
kmem_cache_destroy(rds_conn_slab);

rds_info_deregister_func(RDS_INFO_CONNECTIONS, rds_conn_info);
--
1.7.8.6

2012-08-22 02:28:29

[permalink] [raw]

Subject: [PATCH v3 15/17] openvswitch: use new hashtable implementation

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

Signed-off-by: Sasha Levin <[email protected]>
---
net/openvswitch/vport.c | 30 +++++++++++++-----------------
1 files changed, 13 insertions(+), 17 deletions(-)

diff --git a/net/openvswitch/vport.c b/net/openvswitch/vport.c
index 6140336..3484120 100644
--- a/net/openvswitch/vport.c
+++ b/net/openvswitch/vport.c
@@ -27,6 +27,7 @@
#include <linux/rcupdate.h>
#include <linux/rtnetlink.h>
#include <linux/compat.h>
+#include <linux/hashtable.h>

#include "vport.h"
#include "vport-internal_dev.h"
@@ -39,8 +40,8 @@ static const struct vport_ops *vport_ops_list[] = {
};

/* Protected by RCU read lock for reading, RTNL lock for writing. */
-static struct hlist_head *dev_table;
-#define VPORT_HASH_BUCKETS 1024
+#define VPORT_HASH_BITS 10
+static DEFINE_HASHTABLE(dev_table, VPORT_HASH_BITS);

/**
* ovs_vport_init - initialize vport subsystem
@@ -49,10 +50,7 @@ static struct hlist_head *dev_table;
*/
int ovs_vport_init(void)
{
- dev_table = kzalloc(VPORT_HASH_BUCKETS * sizeof(struct hlist_head),
- GFP_KERNEL);
- if (!dev_table)
- return -ENOMEM;
+ hash_init(dev_table);

return 0;
}
@@ -67,12 +65,6 @@ void ovs_vport_exit(void)
kfree(dev_table);
}

-static struct hlist_head *hash_bucket(const char *name)
-{
- unsigned int hash = full_name_hash(name, strlen(name));
- return &dev_table[hash & (VPORT_HASH_BUCKETS - 1)];
-}
-
/**
* ovs_vport_locate - find a port that has already been created
*
@@ -82,11 +74,11 @@ static struct hlist_head *hash_bucket(const char *name)
*/
struct vport *ovs_vport_locate(const char *name)
{
- struct hlist_head *bucket = hash_bucket(name);
struct vport *vport;
struct hlist_node *node;
+ int key = full_name_hash(name, strlen(name));

- hlist_for_each_entry_rcu(vport, node, bucket, hash_node)
+ hash_for_each_possible_rcu(dev_table, vport, node, hash_node, key)
if (!strcmp(name, vport->ops->get_name(vport)))
return vport;

@@ -170,14 +162,18 @@ struct vport *ovs_vport_add(const struct vport_parms *parms)

for (i = 0; i < ARRAY_SIZE(vport_ops_list); i++) {
if (vport_ops_list[i]->type == parms->type) {
+ int key;
+ const char *name;
+
vport = vport_ops_list[i]->create(parms);
if (IS_ERR(vport)) {
err = PTR_ERR(vport);
goto out;
}

- hlist_add_head_rcu(&vport->hash_node,
- hash_bucket(vport->ops->get_name(vport)));
+ name = vport->ops->get_name(vport);
+ key = full_name_hash(name, strlen(name));
+ hash_add_rcu(dev_table, &vport->hash_node, key);
return vport;
}
}
@@ -218,7 +214,7 @@ void ovs_vport_del(struct vport *vport)
{
ASSERT_RTNL();

- hlist_del_rcu(&vport->hash_node);
+ hash_del_rcu(&vport->hash_node);

vport->ops->destroy(vport);
}
--
1.7.8.6

2012-08-22 02:27:52

[permalink] [raw]

Subject: [PATCH v3 10/17] dlm: use new hashtable implementation

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

Signed-off-by: Sasha Levin <[email protected]>
---
fs/dlm/lowcomms.c | 47 +++++++++++++----------------------------------
1 files changed, 13 insertions(+), 34 deletions(-)

diff --git a/fs/dlm/lowcomms.c b/fs/dlm/lowcomms.c
index 331ea4f..9f21774 100644
--- a/fs/dlm/lowcomms.c
+++ b/fs/dlm/lowcomms.c
@@ -55,6 +55,7 @@
#include <net/sctp/sctp.h>
#include <net/sctp/user.h>
#include <net/ipv6.h>
+#include <linux/hashtable.h>

#include "dlm_internal.h"
#include "lowcomms.h"
@@ -62,7 +63,7 @@
#include "config.h"

#define NEEDED_RMEM (4*1024*1024)
-#define CONN_HASH_SIZE 32
+#define CONN_HASH_BITS 5

/* Number of messages to send before rescheduling */
#define MAX_SEND_MSG_COUNT 25
@@ -158,34 +159,21 @@ static int dlm_allow_conn;
static struct workqueue_struct *recv_workqueue;
static struct workqueue_struct *send_workqueue;

-static struct hlist_head connection_hash[CONN_HASH_SIZE];
+static struct hlist_head connection_hash[CONN_HASH_BITS];
static DEFINE_MUTEX(connections_lock);
static struct kmem_cache *con_cache;

static void process_recv_sockets(struct work_struct *work);
static void process_send_sockets(struct work_struct *work);

-
-/* This is deliberately very simple because most clusters have simple
- sequential nodeids, so we should be able to go straight to a connection
- struct in the array */
-static inline int nodeid_hash(int nodeid)
-{
- return nodeid & (CONN_HASH_SIZE-1);
-}
-
static struct connection *__find_con(int nodeid)
{
- int r;
struct hlist_node *h;
struct connection *con;

- r = nodeid_hash(nodeid);
-
- hlist_for_each_entry(con, h, &connection_hash[r], list) {
+ hash_for_each_possible(connection_hash, con, h, list, nodeid)
if (con->nodeid == nodeid)
return con;
- }
return NULL;
}

@@ -196,7 +184,6 @@ static struct connection *__find_con(int nodeid)
static struct connection *__nodeid2con(int nodeid, gfp_t alloc)
{
struct connection *con = NULL;
- int r;

con = __find_con(nodeid);
if (con || !alloc)
@@ -206,8 +193,7 @@ static struct connection *__nodeid2con(int nodeid, gfp_t alloc)
if (!con)
return NULL;

- r = nodeid_hash(nodeid);
- hlist_add_head(&con->list, &connection_hash[r]);
+ hash_add(connection_hash, &con->list, nodeid);

con->nodeid = nodeid;
mutex_init(&con->sock_mutex);
@@ -235,11 +221,8 @@ static void foreach_conn(void (*conn_func)(struct connection *c))
struct hlist_node *h, *n;
struct connection *con;

- for (i = 0; i < CONN_HASH_SIZE; i++) {
- hlist_for_each_entry_safe(con, h, n, &connection_hash[i], list){
- conn_func(con);
- }
- }
+ hash_for_each_safe(connection_hash, i, h, n, con, list)
+ conn_func(con);
}

static struct connection *nodeid2con(int nodeid, gfp_t allocation)
@@ -262,12 +245,10 @@ static struct connection *assoc2con(int assoc_id)

mutex_lock(&connections_lock);

- for (i = 0 ; i < CONN_HASH_SIZE; i++) {
- hlist_for_each_entry(con, h, &connection_hash[i], list) {
- if (con->sctp_assoc == assoc_id) {
- mutex_unlock(&connections_lock);
- return con;
- }
+ hash_for_each(connection_hash, i, h, con, list) {
+ if (con->sctp_assoc == assoc_id) {
+ mutex_unlock(&connections_lock);
+ return con;
}
}
mutex_unlock(&connections_lock);
@@ -1638,7 +1619,7 @@ static void free_conn(struct connection *con)
close_connection(con, true);
if (con->othercon)
kmem_cache_free(con_cache, con->othercon);
- hlist_del(&con->list);
+ hash_del(&con->list);
kmem_cache_free(con_cache, con);
}

@@ -1667,10 +1648,8 @@ int dlm_lowcomms_start(void)
{
int error = -EINVAL;
struct connection *con;
- int i;

- for (i = 0; i < CONN_HASH_SIZE; i++)
- INIT_HLIST_HEAD(&connection_hash[i]);
+ hash_init(connection_hash);

init_local();
if (!dlm_local_count) {
--
1.7.8.6

2012-08-28 23:00:54

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

* Mathieu Desnoyers ([email protected]) wrote:
> * Sasha Levin ([email protected]) wrote:
> > On 08/28/2012 12:11 PM, Mathieu Desnoyers wrote:
> > > * Sasha Levin ([email protected]) wrote:
> > >> On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
> > >>> * Tejun Heo ([email protected]) wrote:
> > >>>> Hello,
> > >>>>
> > >>>> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> > >>>>> Thats the thing, the amount of things of things you can do with a given bucket
> > >>>>> is very limited. You can't add entries to any point besides the head (without
> > >>>>> walking the entire list).
> > >>>>
> > >>>> Kinda my point. We already have all the hlist*() interface to deal
> > >>>> with such cases. Having something which is evidently the trivial
> > >>>> hlist hashtable and advertises as such in the interface can be
> > >>>> helpful. I think we need that more than we need anything fancy.
> > >>>>
> > >>>> Heh, this is a debate about which one is less insignificant. I can
> > >>>> see your point. I'd really like to hear what others think on this.
> > >>>>
> > >>>> Guys, do we want something which is evidently trivial hlist hashtable
> > >>>> which can use hlist_*() API directly or do we want something better
> > >>>> encapsulated?
> > >>>
> > >>> My 2 cents, FWIW: I think this specific effort should target a trivially
> > >>> understandable API and implementation, for use-cases where one would be
> > >>> tempted to reimplement his own trivial hash table anyway. So here
> > >>> exposing hlist internals, with which kernel developers are already
> > >>> familiar, seems like a good approach in my opinion, because hiding stuff
> > >>> behind new abstraction might make the target users go away.
> > >>>
> > >>> Then, as we see the need, we can eventually merge a more elaborate hash
> > >>> table with poneys and whatnot, but I would expect that the trivial hash
> > >>> table implementation would still be useful. There are of course very
> > >>> compelling reasons to use a more featureful hash table: automatic
> > >>> resize, RT-aware updates, scalable updates, etc... but I see a purpose
> > >>> for a trivial implementation. Its primary strong points being:
> > >>>
> > >>> - it's trivially understandable, so anyone how want to be really sure
> > >>> they won't end up debugging the hash table instead of their
> > >>> work-in-progress code can have a full understanding of it,
> > >>> - it has few dependencies, which makes it easier to understand and
> > >>> easier to use in some contexts (e.g. early boot).
> > >>>
> > >>> So I'm in favor of not overdoing the abstraction for this trivial hash
> > >>> table, and honestly I would rather prefer that this trivial hash table
> > >>> stays trivial. A more elaborate hash table should probably come as a
> > >>> separate API.
> > >>>
> > >>> Thanks,
> > >>>
> > >>> Mathieu
> > >>>
> > >>
> > >> Alright, let's keep it simple then.
> > >>
> > >> I do want to keep the hash_for_each[rcu,safe] family though.
> > >
> > > Just a thought: if the API offered by the simple hash table focus on
> > > providing a mechanism to find the hash bucket to which belongs the hash
> > > chain containing the key looked up, and then expects the user to use the
> > > hlist API to iterate on the chain (with or without the hlist _rcu
> > > variant), then it might seem consistent that a helper providing
> > > iteration over the entire table would actually just provide iteration on
> > > all buckets, and let the user call the hlist for each iterator for each
> > > node within the bucket, e.g.:
> > >
> > > struct hlist_head *head;
> > > struct hlist_node *pos;
> > >
> > > hash_for_each_bucket(ht, head) {
> > > hlist_for_each(pos, head) {
> > > ...
> > > }
> > > }
> > >
> > > That way you only have to provide one single macro
> > > (hash_for_each_bucket), and rely on the already existing:
> > >
> > > - hlist_for_each_entry
> > > - hlist_for_each_safe
> > > - hlist_for_each_entry_rcu
> > > - hlist_for_each_safe_rcu
> > > .....
> > >
> > > and various flavors that can appear in the future without duplicating
> > > this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
> > > versions of the hash_for_each_bucket macro.
> > >
> > > Thoughts ?
> >
> > In my opinion, the downside here is that it'll require 2 function calls and 2
> > levels of nesting for a simple hash iteration.
>
> Those are macros, not functions. No function call is required. But I see
> your point about nesting.
>
> >
> > hash_for_each_bucket() will always be followed by an iteration of that
> > bucket, so splitting a hash_for_each() which does both into 2
> > different functions which will almost always must be called in that
> > given order sounds unintuitive to me.
> >
> > It's also just 3 different possible iterators:
> >
> > - hlist_for_each_entry
> > - hlist_for_each_entry_safe
> > - hlist_for_each_entry_rcu
> >
> > So I think that it's a good price to pay - 2 extra macro definitions
> > in the header to save a macro call + nesting level in each place that
> > uses a hashtable.
>
> I must admin I don't care that much one way or another.

Looking again at:

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

you will notice that a "break" or "continue" in the inner loop will not
affect the outer loop, which is certainly not what the programmer would
expect!

I advise strongly against creating such error-prone construct.

Thanks,

Mathieu

>
> Thanks,
>
> Mathieu
>
> >
> >
> > Thanks,
> > Sasha
> >
> > > Thanks,
> > >
> > > Mathieu
> > >
> >
>
> --
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com

--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

2012-08-23 00:24:06

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

Hi Tejun,

On 08/22/2012 08:01 PM, Tejun Heo wrote:
> Hello, Sasha.
>
> On Wed, Aug 22, 2012 at 04:26:56AM +0200, Sasha Levin wrote:
>> +#define DEFINE_HASHTABLE(name, bits) \
>> + struct hlist_head name[HASH_SIZE(bits)];
>
> Shouldn't this be something like the following?
>
> #define DEFINE_HASHTABLE(name, bits) \
> struct hlist_head name[HASH_SIZE(bits)] = \
> { [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT };
>
> Also, given that the declaration isn't non-trivial, you'll probably
> want a matching DECLARE_HASHTABLE() macro too.

I figured we might do a DEFINE_HASHTABLE() to prevent the need from using
hash_init() on hashtables defined this way, but I preferred not to since we may
end up wanting a more complex initialization (I'll explain why extensively below).

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

No reason, will fix.

> Also, no biggie but why isn't this macro in caps?

I had this plan in my mind to move it into linux/hash.h at some stage later, and
the API there uses low caps even for macros (hash_long()).

>> +/**
>> + * hash_add_rcu_size - add an object to a rcu enabled hashtable
>> + * @hashtable: hashtable to add to
>> + * @bits: bit count used for hashing
>> + * @node: the &struct hlist_node of the object to be added
>> + * @key: the key of the object to be added
>> + */
>> +#define hash_add_rcu_size(hashtable, bits, node, key) \
>> + hlist_add_head_rcu(node, &hashtable[hash_min(key, bits)]);
>> +
>> +/**
>> + * hash_add_rcu - add an object to a rcu enabled hashtable
>> + * @hashtable: hashtable to add to
>> + * @node: the &struct hlist_node of the object to be added
>> + * @key: the key of the object to be added
>> + */
>> +#define hash_add_rcu(hashtable, node, key) \
>> + hash_add_rcu_size(hashtable, HASH_BITS(hashtable), node, key)
>
> Or maybe we're better off with hash_head_size() and hash_head()? I'll
> expand on it later. Please bear with me.
>
>> +/**
>> + * hash_hashed - check whether an object is in any hashtable
>> + * @node: the &struct hlist_node of the object to be checked
>> + */
>> +#define hash_hashed(node) (!hlist_unhashed(node))
>
> As the 'h' in hlist* stand for hash anyway and I think this type of
> thin wrappers tend to obfuscate more than anything else.
>
>> +/**
>> + * hash_del - remove an object from a hashtable
>> + * @node: &struct hlist_node of the object to remove
>> + */
>> +static inline void hash_del(struct hlist_node *node)
>> +{
>> + hlist_del_init(node);
>> +}
>> +
>> +/**
>> + * hash_del_rcu - remove an object from a rcu enabled hashtable
>> + * @node: &struct hlist_node of the object to remove
>> + */
>> +static inline void hash_del_rcu(struct hlist_node *node)
>> +{
>> + hlist_del_init_rcu(node);
>> +}
>
> If we do that, we can remove all these thin wrappers.
>
>> +#define hash_for_each_size(name, bits, bkt, node, obj, member) \
>> + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++) \
>> + hlist_for_each_entry(obj, node, &name[bkt], member)
> ..
>> +#define hash_for_each(name, bkt, node, obj, member) \
>> + hash_for_each_size(name, HASH_BITS(name), bkt, node, obj, member)
> ...
>> +#define hash_for_each_rcu_size(name, bits, bkt, node, obj, member) \
>> + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++) \
>> + hlist_for_each_entry_rcu(obj, node, &name[bkt], member)
> ...
>> +#define hash_for_each_rcu(name, bkt, node, obj, member) \
>> + hash_for_each_rcu_size(name, HASH_BITS(name), bkt, node, obj, member)
> ...
>> +#define hash_for_each_safe_size(name, bits, bkt, node, tmp, obj, member) \
>> + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++) \
>> + hlist_for_each_entry_safe(obj, node, tmp, &name[bkt], member)
> ...
>> +#define hash_for_each_safe(name, bkt, node, tmp, obj, member) \
>> + hash_for_each_safe_size(name, HASH_BITS(name), bkt, node, \
>> + tmp, obj, member)
> ...
>> +#define hash_for_each_possible_size(name, obj, bits, node, member, key) \
>> + hlist_for_each_entry(obj, node, &name[hash_min(key, bits)], member)
> ...
>> +#define hash_for_each_possible(name, obj, node, member, key) \
>> + hash_for_each_possible_size(name, obj, HASH_BITS(name), node, member, key)
> ...
>> +#define hash_for_each_possible_rcu_size(name, obj, bits, node, member, key) \
>> + hlist_for_each_entry_rcu(obj, node, &name[hash_min(key, bits)], member)
> ...
>> +#define hash_for_each_possible_rcu(name, obj, node, member, key) \
>> + hash_for_each_possible_rcu_size(name, obj, HASH_BITS(name), \
> ...
>> +#define hash_for_each_possible_safe_size(name, obj, bits, node, tmp, member, key)\
>> + hlist_for_each_entry_safe(obj, node, tmp, \
>> + &name[hash_min(key, bits)], member)
> ...
>> +#define hash_for_each_possible_safe(name, obj, node, tmp, member, key) \
>> + hash_for_each_possible_safe_size(name, obj, HASH_BITS(name), \
>
> And also all these. We'd only need hash_for_each_head() and
> hash_head(). hash_for_each_possible*() could be nice for convenience,
> I suppose.
>
> I think the almost trivial nature of hlist hashtables makes this a bit
> tricky and I'm not very sure but having this combinatory explosion is
> a bit dazzling when the same functionality can be achieved by simply
> combining operations which are already defined and named considering
> hashtable. I'm not feeling too strong about this tho. What do others
> think?

I'm thinking that this hashtable API will have 2 purposes: First, it would
prevent the excessive duplication of hashtable implementations all around the code.

Second, it will allow more easily interchangeable hashtable implementations to
find their way into the kernel. There are several maintainers who would be happy
to see dynamically sized RCU hashtable, and I'm guessing that several more
variants could be added based on needs in specific modules.

The second reason is why several things you've mentioned look the way they are:

- No DEFINE_HASHTABLE(): I wanted to force the use of hash_init() since
initialization for other hashtables may be more complicated than the static
initialization for this implementation, which means that any place that used
DEFINE_HASHTABLE() and didn't do hash_init() will be buggy.

- hash_hashed(): Different hashtable implementations may not use hlist, so
letting them assume that doing hlist operations on hashtable objects is wrong.

- Lack of hash_head(): I didn't want to expose the internal structure of the
hashtable to the user. This might make it hard to implement hashtables that
resize themselves if we let the user hold a bucket in his hands.

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

Now, I know that I mention a lot of these hashtables that might or might not be
added later on in the kernel, this is mostly due to the interest in dynamic
resizable hashtables which was shown during the RFC, and the fact that there is
a solid implementation of a dynamic RCU hashtable in urcu which might be a great
benefit in the kernel as well (I'm also looking at it while working on this
hashtable to verify that both could share an API in the future).

Regarding the amount of new macros, we can address this by splitting off any
dynamic elements into a new hashtable type. This will let us reduce quite a lot
of macros (removing all the _size() ones at least).

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

Sure, sorry about that.

Thanks,
Sasha

> Thanks.
>

2012-08-22 13:13:01

by J. Bruce Fields

[permalink] [raw]

Subject: Re: [PATCH v3 13/17] lockd: use new hashtable implementation

On Wed, Aug 22, 2012 at 02:13:54PM +0200, Sasha Levin wrote:
> On 08/22/2012 01:47 PM, J. Bruce Fields wrote:
> > On Wed, Aug 22, 2012 at 04:27:08AM +0200, Sasha Levin wrote:
> >> +static int __init nlm_init(void)
> >> +{
> >> + hash_init(nlm_files);
> >> + return 0;
> >> +}
> >> +
> >> +module_init(nlm_init);
> >
> > That's giving me:
> >
> > fs/lockd/svcsubs.o: In function `nlm_init':
> > /home/bfields/linux-2.6/fs/lockd/svcsubs.c:454: multiple definition of `init_module'
> > fs/lockd/svc.o:/home/bfields/linux-2.6/fs/lockd/svc.c:606: first defined here
> > make[2]: *** [fs/lockd/lockd.o] Error 1
> > make[1]: *** [fs/lockd] Error 2
> > make[1]: *** Waiting for unfinished jobs....
>
> I tested this entire patch set both with linux-next and Linus' latest master,
> and it worked fine in both places.
>
> Is it possible that lockd has a -next tree which isn't pulled into linux-next?
> (there's nothing listed in MAINTAINERS that I could see).

No, there's the same problem with Linus's latest.

I'm applying just patches 1 and 13--but doesn't look like your earlier
patches touch lockd.

Are you actually building lockd? (CONFIG_LOCKD).

--b.

2012-08-25 04:24:22

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

* Tejun Heo ([email protected]) wrote:
> Hello,
>
> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> > Thats the thing, the amount of things of things you can do with a given bucket
> > is very limited. You can't add entries to any point besides the head (without
> > walking the entire list).
>
> Kinda my point. We already have all the hlist*() interface to deal
> with such cases. Having something which is evidently the trivial
> hlist hashtable and advertises as such in the interface can be
> helpful. I think we need that more than we need anything fancy.
>
> Heh, this is a debate about which one is less insignificant. I can
> see your point. I'd really like to hear what others think on this.
>
> Guys, do we want something which is evidently trivial hlist hashtable
> which can use hlist_*() API directly or do we want something better
> encapsulated?

My 2 cents, FWIW: I think this specific effort should target a trivially
understandable API and implementation, for use-cases where one would be
tempted to reimplement his own trivial hash table anyway. So here
exposing hlist internals, with which kernel developers are already
familiar, seems like a good approach in my opinion, because hiding stuff
behind new abstraction might make the target users go away.

Then, as we see the need, we can eventually merge a more elaborate hash
table with poneys and whatnot, but I would expect that the trivial hash
table implementation would still be useful. There are of course very
compelling reasons to use a more featureful hash table: automatic
resize, RT-aware updates, scalable updates, etc... but I see a purpose
for a trivial implementation. Its primary strong points being:

- it's trivially understandable, so anyone how want to be really sure
they won't end up debugging the hash table instead of their
work-in-progress code can have a full understanding of it,
- it has few dependencies, which makes it easier to understand and
easier to use in some contexts (e.g. early boot).

So I'm in favor of not overdoing the abstraction for this trivial hash
table, and honestly I would rather prefer that this trivial hash table
stays trivial. A more elaborate hash table should probably come as a
separate API.

Thanks,

Mathieu

--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

2012-08-22 02:27:27

[permalink] [raw]

Subject: [PATCH v3 06/17] tracepoint: use new hashtable implementation

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

Signed-off-by: Sasha Levin <[email protected]>
---
kernel/tracepoint.c | 27 +++++++++++----------------
1 files changed, 11 insertions(+), 16 deletions(-)

diff --git a/kernel/tracepoint.c b/kernel/tracepoint.c
index d96ba22..854df92 100644
--- a/kernel/tracepoint.c
+++ b/kernel/tracepoint.c
@@ -26,6 +26,7 @@
#include <linux/slab.h>
#include <linux/sched.h>
#include <linux/static_key.h>
+#include <linux/hashtable.h>

extern struct tracepoint * const __start___tracepoints_ptrs[];
extern struct tracepoint * const __stop___tracepoints_ptrs[];
@@ -49,8 +50,7 @@ static LIST_HEAD(tracepoint_module_list);
* Protected by tracepoints_mutex.
*/
#define TRACEPOINT_HASH_BITS 6
-#define TRACEPOINT_TABLE_SIZE (1 << TRACEPOINT_HASH_BITS)
-static struct hlist_head tracepoint_table[TRACEPOINT_TABLE_SIZE];
+static DEFINE_HASHTABLE(tracepoint_table, TRACEPOINT_HASH_BITS);

/*
* Note about RCU :
@@ -191,16 +191,15 @@ tracepoint_entry_remove_probe(struct tracepoint_entry *entry,
*/
static struct tracepoint_entry *get_tracepoint(const char *name)
{
- struct hlist_head *head;
struct hlist_node *node;
struct tracepoint_entry *e;
u32 hash = jhash(name, strlen(name), 0);

- head = &tracepoint_table[hash & (TRACEPOINT_TABLE_SIZE - 1)];
- hlist_for_each_entry(e, node, head, hlist) {
+ hash_for_each_possible(tracepoint_table, e, node, hlist, hash) {
if (!strcmp(name, e->name))
return e;
}
+
return NULL;
}

@@ -210,19 +209,13 @@ static struct tracepoint_entry *get_tracepoint(const char *name)
*/
static struct tracepoint_entry *add_tracepoint(const char *name)
{
- struct hlist_head *head;
- struct hlist_node *node;
struct tracepoint_entry *e;
size_t name_len = strlen(name) + 1;
u32 hash = jhash(name, name_len-1, 0);

- head = &tracepoint_table[hash & (TRACEPOINT_TABLE_SIZE - 1)];
- hlist_for_each_entry(e, node, head, hlist) {
- if (!strcmp(name, e->name)) {
- printk(KERN_NOTICE
- "tracepoint %s busy\n", name);
- return ERR_PTR(-EEXIST); /* Already there */
- }
+ if (get_tracepoint(name)) {
+ printk(KERN_NOTICE "tracepoint %s busy\n", name);
+ return ERR_PTR(-EEXIST); /* Already there */
}
/*
* Using kmalloc here to allocate a variable length element. Could
@@ -234,7 +227,7 @@ static struct tracepoint_entry *add_tracepoint(const char *name)
memcpy(&e->name[0], name, name_len);
e->funcs = NULL;
e->refcount = 0;
- hlist_add_head(&e->hlist, head);
+ hash_add(tracepoint_table, &e->hlist, hash);
return e;
}

@@ -244,7 +237,7 @@ static struct tracepoint_entry *add_tracepoint(const char *name)
*/
static inline void remove_tracepoint(struct tracepoint_entry *e)
{
- hlist_del(&e->hlist);
+ hash_del(&e->hlist);
kfree(e);
}

@@ -722,6 +715,8 @@ struct notifier_block tracepoint_module_nb = {

static int init_tracepoints(void)
{
+ hash_init(tracepoint_table);
+
return register_module_notifier(&tracepoint_module_nb);
}
__initcall(init_tracepoints);
--
1.7.8.6

2012-08-22 18:01:44

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

Hello, Sasha.

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

Shouldn't this be something like the following?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Thanks.

--
tejun

2012-08-28 09:56:35

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
> * Tejun Heo ([email protected]) wrote:
>> Hello,
>>
>> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
>>> Thats the thing, the amount of things of things you can do with a given bucket
>>> is very limited. You can't add entries to any point besides the head (without
>>> walking the entire list).
>>
>> Kinda my point. We already have all the hlist*() interface to deal
>> with such cases. Having something which is evidently the trivial
>> hlist hashtable and advertises as such in the interface can be
>> helpful. I think we need that more than we need anything fancy.
>>
>> Heh, this is a debate about which one is less insignificant. I can
>> see your point. I'd really like to hear what others think on this.
>>
>> Guys, do we want something which is evidently trivial hlist hashtable
>> which can use hlist_*() API directly or do we want something better
>> encapsulated?
>
> My 2 cents, FWIW: I think this specific effort should target a trivially
> understandable API and implementation, for use-cases where one would be
> tempted to reimplement his own trivial hash table anyway. So here
> exposing hlist internals, with which kernel developers are already
> familiar, seems like a good approach in my opinion, because hiding stuff
> behind new abstraction might make the target users go away.
>
> Then, as we see the need, we can eventually merge a more elaborate hash
> table with poneys and whatnot, but I would expect that the trivial hash
> table implementation would still be useful. There are of course very
> compelling reasons to use a more featureful hash table: automatic
> resize, RT-aware updates, scalable updates, etc... but I see a purpose
> for a trivial implementation. Its primary strong points being:
>
> - it's trivially understandable, so anyone how want to be really sure
> they won't end up debugging the hash table instead of their
> work-in-progress code can have a full understanding of it,
> - it has few dependencies, which makes it easier to understand and
> easier to use in some contexts (e.g. early boot).
>
> So I'm in favor of not overdoing the abstraction for this trivial hash
> table, and honestly I would rather prefer that this trivial hash table
> stays trivial. A more elaborate hash table should probably come as a
> separate API.
>
> Thanks,
>
> Mathieu
>

Alright, let's keep it simple then.

I do want to keep the hash_for_each[rcu,safe] family though.

2012-08-22 02:27:33

[permalink] [raw]

Subject: [PATCH v3 07/17] net,9p: use new hashtable implementation

Switch 9p error table to use the new hashtable implementation. This reduces the amount of
generic unrelated code in 9p.

Signed-off-by: Sasha Levin <[email protected]>
---
net/9p/error.c | 21 ++++++++++-----------
1 files changed, 10 insertions(+), 11 deletions(-)

diff --git a/net/9p/error.c b/net/9p/error.c
index 2ab2de7..a5cc7dd 100644
--- a/net/9p/error.c
+++ b/net/9p/error.c
@@ -34,7 +34,7 @@
#include <linux/jhash.h>
#include <linux/errno.h>
#include <net/9p/9p.h>
-
+#include <linux/hashtable.h>
/**
* struct errormap - map string errors from Plan 9 to Linux numeric ids
* @name: string sent over 9P
@@ -50,8 +50,8 @@ struct errormap {
struct hlist_node list;
};

-#define ERRHASHSZ 32
-static struct hlist_head hash_errmap[ERRHASHSZ];
+#define ERR_HASH_BITS 5
+static DEFINE_HASHTABLE(hash_errmap, ERR_HASH_BITS);

/* FixMe - reduce to a reasonable size */
static struct errormap errmap[] = {
@@ -193,18 +193,17 @@ static struct errormap errmap[] = {
int p9_error_init(void)
{
struct errormap *c;
- int bucket;
+ u32 hash;

/* initialize hash table */
- for (bucket = 0; bucket < ERRHASHSZ; bucket++)
- INIT_HLIST_HEAD(&hash_errmap[bucket]);
+ hash_init(hash_errmap);

/* load initial error map into hash table */
for (c = errmap; c->name != NULL; c++) {
c->namelen = strlen(c->name);
- bucket = jhash(c->name, c->namelen, 0) % ERRHASHSZ;
+ hash = jhash(c->name, c->namelen, 0);
INIT_HLIST_NODE(&c->list);
- hlist_add_head(&c->list, &hash_errmap[bucket]);
+ hash_add(hash_errmap, &c->list, hash);
}

return 1;
@@ -223,13 +222,13 @@ int p9_errstr2errno(char *errstr, int len)
int errno;
struct hlist_node *p;
struct errormap *c;
- int bucket;
+ u32 hash;

errno = 0;
p = NULL;
c = NULL;
- bucket = jhash(errstr, len, 0) % ERRHASHSZ;
- hlist_for_each_entry(c, p, &hash_errmap[bucket], list) {
+ hash = jhash(errstr, len, 0);
+ hash_for_each_possible(hash_errmap, c, p, list, hash) {
if (c->namelen == len && !memcmp(c->name, errstr, len)) {
errno = c->val;
break;
--
1.7.8.6

2012-08-22 02:27:09

[permalink] [raw]

Subject: [PATCH v3 03/17] mm,ksm: use new hashtable implementation

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 <[email protected]>
---
mm/ksm.c | 33 +++++++++++++++------------------
1 files changed, 15 insertions(+), 18 deletions(-)

diff --git a/mm/ksm.c b/mm/ksm.c
index 9638620..dd4d6af 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>

@@ -156,9 +156,8 @@ struct rmap_item {
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_SLOTS_HASH_BITS 10
+static DEFINE_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_BITS);

static struct mm_slot ksm_mm_head = {
.mm_list = LIST_HEAD_INIT(ksm_mm_head.mm_list),
@@ -275,26 +274,21 @@ 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;
+ struct mm_slot *slot;
+
+ hash_for_each_possible(mm_slots_hash, slot, node, link, (unsigned long)mm)
+ if (slot->mm == mm)
+ return slot;

- 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;
}

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, (unsigned long)mm);
}

static inline int in_stable_tree(struct rmap_item *rmap_item)
@@ -647,7 +641,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 +1379,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);

@@ -1552,7 +1546,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 {
@@ -2028,6 +2022,9 @@ static int __init ksm_init(void)
*/
hotplug_memory_notifier(ksm_memory_callback, 100);
#endif
+
+ hash_init(mm_slots_hash);
+
return 0;

out_free:
--
1.7.8.6

2012-08-22 02:28:35

[permalink] [raw]

Subject: [PATCH v3 16/17] tracing output: use new hashtable implementation

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

Signed-off-by: Sasha Levin <[email protected]>
---
kernel/trace/trace_output.c | 20 ++++++++------------
1 files changed, 8 insertions(+), 12 deletions(-)

diff --git a/kernel/trace/trace_output.c b/kernel/trace/trace_output.c
index 123b189..1324c1a 100644
--- a/kernel/trace/trace_output.c
+++ b/kernel/trace/trace_output.c
@@ -8,15 +8,15 @@
#include <linux/module.h>
#include <linux/mutex.h>
#include <linux/ftrace.h>
+#include <linux/hashtable.h>

#include "trace_output.h"

-/* must be a power of 2 */
-#define EVENT_HASHSIZE 128
+#define EVENT_HASH_BITS 7

DECLARE_RWSEM(trace_event_mutex);

-static struct hlist_head event_hash[EVENT_HASHSIZE] __read_mostly;
+static DEFINE_HASHTABLE(event_hash, EVENT_HASH_BITS);

static int next_event_type = __TRACE_LAST_TYPE + 1;

@@ -712,11 +712,8 @@ struct trace_event *ftrace_find_event(int type)
{
struct trace_event *event;
struct hlist_node *n;
- unsigned key;

- key = type & (EVENT_HASHSIZE - 1);
-
- hlist_for_each_entry(event, n, &event_hash[key], node) {
+ hash_for_each_possible(event_hash, event, n, node, type) {
if (event->type == type)
return event;
}
@@ -781,7 +778,6 @@ void trace_event_read_unlock(void)
*/
int register_ftrace_event(struct trace_event *event)
{
- unsigned key;
int ret = 0;

down_write(&trace_event_mutex);
@@ -833,9 +829,7 @@ int register_ftrace_event(struct trace_event *event)
if (event->funcs->binary == NULL)
event->funcs->binary = trace_nop_print;

- key = event->type & (EVENT_HASHSIZE - 1);
-
- hlist_add_head(&event->node, &event_hash[key]);
+ hash_add(event_hash, &event->node, event->type);

ret = event->type;
out:
@@ -850,7 +844,7 @@ EXPORT_SYMBOL_GPL(register_ftrace_event);
*/
int __unregister_ftrace_event(struct trace_event *event)
{
- hlist_del(&event->node);
+ hash_del(&event->node);
list_del(&event->list);
return 0;
}
@@ -1323,6 +1317,8 @@ __init static int init_events(void)
}
}

+ hash_init(event_hash);
+
return 0;
}
early_initcall(init_events);
--
1.7.8.6

2012-08-24 20:33:40

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

Hello, Sasha.

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

Hmmm? DECLARE/DEFINE are usually for static ones.

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

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

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

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

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

Thanks.

--
tejun

2012-08-22 17:32:26

[permalink] [raw]

Subject: Re: [PATCH v3 13/17] lockd: use new hashtable implementation

On 08/22/2012 03:22 PM, Mathieu Desnoyers wrote:
> * Sasha Levin ([email protected]) wrote:
>> On 08/22/2012 01:47 PM, J. Bruce Fields wrote:
>>> On Wed, Aug 22, 2012 at 04:27:08AM +0200, Sasha Levin wrote:
>>>> +static int __init nlm_init(void)
>>>> +{
>>>> + hash_init(nlm_files);
>>>> + return 0;
>>>> +}
>>>> +
>>>> +module_init(nlm_init);
>>>
>>> That's giving me:
>>>
>>> fs/lockd/svcsubs.o: In function `nlm_init':
>>> /home/bfields/linux-2.6/fs/lockd/svcsubs.c:454: multiple definition of `init_module'
>>> fs/lockd/svc.o:/home/bfields/linux-2.6/fs/lockd/svc.c:606: first defined here
>>> make[2]: *** [fs/lockd/lockd.o] Error 1
>>> make[1]: *** [fs/lockd] Error 2
>>> make[1]: *** Waiting for unfinished jobs....
>>
>> I tested this entire patch set both with linux-next and Linus' latest master,
>> and it worked fine in both places.
>>
>> Is it possible that lockd has a -next tree which isn't pulled into linux-next?
>> (there's nothing listed in MAINTAINERS that I could see).
>
> fs/lockd/Makefile:
>
> obj-$(CONFIG_LOCKD) += lockd.o
>
> lockd-objs-y := clntlock.o clntproc.o clntxdr.o host.o svc.o svclock.o \
> svcshare.o svcproc.o svcsubs.o mon.o xdr.o grace.o
>
> your patch adds a module_init to svcsubs.c.
> However, there is already one in svc.c, pulled into the same module.
>
> in your test build, is CONFIG_LOCKD defined as "m" or "y" ? You should
> always test both.
>
> One solution here is to create a "local" init function in svcsubs.c and
> expose it to svc.c, so the latter can call it from its module init
> function.

Ah yes, it was on =y and I didn't notice :/

I'll fix that.

> Thanks,
>
> Mathieu
>

2012-08-28 11:27:07

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On 08/28/2012 12:11 PM, Mathieu Desnoyers wrote:
> * Sasha Levin ([email protected]) wrote:
>> On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
>>> * Tejun Heo ([email protected]) wrote:
>>>> Hello,
>>>>
>>>> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
>>>>> Thats the thing, the amount of things of things you can do with a given bucket
>>>>> is very limited. You can't add entries to any point besides the head (without
>>>>> walking the entire list).
>>>>
>>>> Kinda my point. We already have all the hlist*() interface to deal
>>>> with such cases. Having something which is evidently the trivial
>>>> hlist hashtable and advertises as such in the interface can be
>>>> helpful. I think we need that more than we need anything fancy.
>>>>
>>>> Heh, this is a debate about which one is less insignificant. I can
>>>> see your point. I'd really like to hear what others think on this.
>>>>
>>>> Guys, do we want something which is evidently trivial hlist hashtable
>>>> which can use hlist_*() API directly or do we want something better
>>>> encapsulated?
>>>
>>> My 2 cents, FWIW: I think this specific effort should target a trivially
>>> understandable API and implementation, for use-cases where one would be
>>> tempted to reimplement his own trivial hash table anyway. So here
>>> exposing hlist internals, with which kernel developers are already
>>> familiar, seems like a good approach in my opinion, because hiding stuff
>>> behind new abstraction might make the target users go away.
>>>
>>> Then, as we see the need, we can eventually merge a more elaborate hash
>>> table with poneys and whatnot, but I would expect that the trivial hash
>>> table implementation would still be useful. There are of course very
>>> compelling reasons to use a more featureful hash table: automatic
>>> resize, RT-aware updates, scalable updates, etc... but I see a purpose
>>> for a trivial implementation. Its primary strong points being:
>>>
>>> - it's trivially understandable, so anyone how want to be really sure
>>> they won't end up debugging the hash table instead of their
>>> work-in-progress code can have a full understanding of it,
>>> - it has few dependencies, which makes it easier to understand and
>>> easier to use in some contexts (e.g. early boot).
>>>
>>> So I'm in favor of not overdoing the abstraction for this trivial hash
>>> table, and honestly I would rather prefer that this trivial hash table
>>> stays trivial. A more elaborate hash table should probably come as a
>>> separate API.
>>>
>>> Thanks,
>>>
>>> Mathieu
>>>
>>
>> Alright, let's keep it simple then.
>>
>> I do want to keep the hash_for_each[rcu,safe] family though.
>
> Just a thought: if the API offered by the simple hash table focus on
> providing a mechanism to find the hash bucket to which belongs the hash
> chain containing the key looked up, and then expects the user to use the
> hlist API to iterate on the chain (with or without the hlist _rcu
> variant), then it might seem consistent that a helper providing
> iteration over the entire table would actually just provide iteration on
> all buckets, and let the user call the hlist for each iterator for each
> node within the bucket, e.g.:
>
> struct hlist_head *head;
> struct hlist_node *pos;
>
> hash_for_each_bucket(ht, head) {
> hlist_for_each(pos, head) {
> ...
> }
> }
>
> That way you only have to provide one single macro
> (hash_for_each_bucket), and rely on the already existing:
>
> - hlist_for_each_entry
> - hlist_for_each_safe
> - hlist_for_each_entry_rcu
> - hlist_for_each_safe_rcu
> .....
>
> and various flavors that can appear in the future without duplicating
> this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
> versions of the hash_for_each_bucket macro.
>
> Thoughts ?

In my opinion, the downside here is that it'll require 2 function calls and 2
levels of nesting for a simple hash iteration.

hash_for_each_bucket() will always be followed by an iteration of that bucket,
so splitting a hash_for_each() which does both into 2 different functions which
will almost always must be called in that given order sounds unintuitive to me.

It's also just 3 different possible iterators:

- hlist_for_each_entry
- hlist_for_each_entry_safe
- hlist_for_each_entry_rcu

So I think that it's a good price to pay - 2 extra macro definitions in the
header to save a macro call + nesting level in each place that uses a hashtable.

Thanks,
Sasha

> Thanks,
>
> Mathieu
>

2012-08-22 13:22:50

[permalink] [raw]

Subject: Re: [PATCH v3 13/17] lockd: use new hashtable implementation

* Sasha Levin ([email protected]) wrote:
> On 08/22/2012 01:47 PM, J. Bruce Fields wrote:
> > On Wed, Aug 22, 2012 at 04:27:08AM +0200, Sasha Levin wrote:
> >> +static int __init nlm_init(void)
> >> +{
> >> + hash_init(nlm_files);
> >> + return 0;
> >> +}
> >> +
> >> +module_init(nlm_init);
> >
> > That's giving me:
> >
> > fs/lockd/svcsubs.o: In function `nlm_init':
> > /home/bfields/linux-2.6/fs/lockd/svcsubs.c:454: multiple definition of `init_module'
> > fs/lockd/svc.o:/home/bfields/linux-2.6/fs/lockd/svc.c:606: first defined here
> > make[2]: *** [fs/lockd/lockd.o] Error 1
> > make[1]: *** [fs/lockd] Error 2
> > make[1]: *** Waiting for unfinished jobs....
>
> I tested this entire patch set both with linux-next and Linus' latest master,
> and it worked fine in both places.
>
> Is it possible that lockd has a -next tree which isn't pulled into linux-next?
> (there's nothing listed in MAINTAINERS that I could see).

fs/lockd/Makefile:

obj-$(CONFIG_LOCKD) += lockd.o

lockd-objs-y := clntlock.o clntproc.o clntxdr.o host.o svc.o svclock.o \
svcshare.o svcproc.o svcsubs.o mon.o xdr.o grace.o

your patch adds a module_init to svcsubs.c.
However, there is already one in svc.c, pulled into the same module.

in your test build, is CONFIG_LOCKD defined as "m" or "y" ? You should
always test both.

One solution here is to create a "local" init function in svcsubs.c and
expose it to svc.c, so the latter can call it from its module init
function.

Thanks,

Mathieu

--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

2012-08-22 12:13:30

[permalink] [raw]

Subject: Re: [PATCH v3 13/17] lockd: use new hashtable implementation

On 08/22/2012 01:47 PM, J. Bruce Fields wrote:
> On Wed, Aug 22, 2012 at 04:27:08AM +0200, Sasha Levin wrote:
>> +static int __init nlm_init(void)
>> +{
>> + hash_init(nlm_files);
>> + return 0;
>> +}
>> +
>> +module_init(nlm_init);
>
> That's giving me:
>
> fs/lockd/svcsubs.o: In function `nlm_init':
> /home/bfields/linux-2.6/fs/lockd/svcsubs.c:454: multiple definition of `init_module'
> fs/lockd/svc.o:/home/bfields/linux-2.6/fs/lockd/svc.c:606: first defined here
> make[2]: *** [fs/lockd/lockd.o] Error 1
> make[1]: *** [fs/lockd] Error 2
> make[1]: *** Waiting for unfinished jobs....

I tested this entire patch set both with linux-next and Linus' latest master,
and it worked fine in both places.

Is it possible that lockd has a -next tree which isn't pulled into linux-next?
(there's nothing listed in MAINTAINERS that I could see).

2012-08-22 02:28:17

[permalink] [raw]

Subject: [PATCH v3 13/17] lockd: use new hashtable implementation

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

Signed-off-by: Sasha Levin <[email protected]>
---
fs/lockd/svcsubs.c | 66 ++++++++++++++++++++++++++++-----------------------
1 files changed, 36 insertions(+), 30 deletions(-)

diff --git a/fs/lockd/svcsubs.c b/fs/lockd/svcsubs.c
index 0deb5f6..d223a1f 100644
--- a/fs/lockd/svcsubs.c
+++ b/fs/lockd/svcsubs.c
@@ -20,6 +20,7 @@
#include <linux/lockd/share.h>
#include <linux/module.h>
#include <linux/mount.h>
+#include <linux/hashtable.h>

#define NLMDBG_FACILITY NLMDBG_SVCSUBS

@@ -28,8 +29,7 @@
* Global file hash table
*/
#define FILE_HASH_BITS 7
-#define FILE_NRHASH (1<<FILE_HASH_BITS)
-static struct hlist_head nlm_files[FILE_NRHASH];
+static DEFINE_HASHTABLE(nlm_files, FILE_HASH_BITS);
static DEFINE_MUTEX(nlm_file_mutex);

#ifdef NFSD_DEBUG
@@ -68,7 +68,7 @@ static inline unsigned int file_hash(struct nfs_fh *f)
int i;
for (i=0; i<NFS2_FHSIZE;i++)
tmp += f->data[i];
- return tmp & (FILE_NRHASH - 1);
+ return tmp;
}

/*
@@ -86,17 +86,17 @@ nlm_lookup_file(struct svc_rqst *rqstp, struct nlm_file **result,
{
struct hlist_node *pos;
struct nlm_file *file;
- unsigned int hash;
+ unsigned int key;
__be32 nfserr;

nlm_debug_print_fh("nlm_lookup_file", f);

- hash = file_hash(f);
+ key = file_hash(f);

/* Lock file table */
mutex_lock(&nlm_file_mutex);

- hlist_for_each_entry(file, pos, &nlm_files[hash], f_list)
+ hash_for_each_possible(nlm_files, file, pos, f_list, file_hash(f))
if (!nfs_compare_fh(&file->f_handle, f))
goto found;

@@ -123,7 +123,7 @@ nlm_lookup_file(struct svc_rqst *rqstp, struct nlm_file **result,
goto out_free;
}

- hlist_add_head(&file->f_list, &nlm_files[hash]);
+ hash_add(nlm_files, &file->f_list, key);

found:
dprintk("lockd: found file %p (count %d)\n", file, file->f_count);
@@ -147,8 +147,8 @@ static inline void
nlm_delete_file(struct nlm_file *file)
{
nlm_debug_print_file("closing file", file);
- if (!hlist_unhashed(&file->f_list)) {
- hlist_del(&file->f_list);
+ if (hash_hashed(&file->f_list)) {
+ hash_del(&file->f_list);
nlmsvc_ops->fclose(file->f_file);
kfree(file);
} else {
@@ -253,27 +253,25 @@ nlm_traverse_files(void *data, nlm_host_match_fn_t match,
int i, ret = 0;

mutex_lock(&nlm_file_mutex);
- for (i = 0; i < FILE_NRHASH; i++) {
- hlist_for_each_entry_safe(file, pos, next, &nlm_files[i], f_list) {
- if (is_failover_file && !is_failover_file(data, file))
- continue;
- file->f_count++;
- mutex_unlock(&nlm_file_mutex);
-
- /* Traverse locks, blocks and shares of this file
- * and update file->f_locks count */
- if (nlm_inspect_file(data, file, match))
- ret = 1;
-
- mutex_lock(&nlm_file_mutex);
- file->f_count--;
- /* No more references to this file. Let go of it. */
- if (list_empty(&file->f_blocks) && !file->f_locks
- && !file->f_shares && !file->f_count) {
- hlist_del(&file->f_list);
- nlmsvc_ops->fclose(file->f_file);
- kfree(file);
- }
+ hash_for_each_safe(nlm_files, i, pos, next, file, f_list) {
+ if (is_failover_file && !is_failover_file(data, file))
+ continue;
+ file->f_count++;
+ mutex_unlock(&nlm_file_mutex);
+
+ /* Traverse locks, blocks and shares of this file
+ * and update file->f_locks count */
+ if (nlm_inspect_file(data, file, match))
+ ret = 1;
+
+ mutex_lock(&nlm_file_mutex);
+ file->f_count--;
+ /* No more references to this file. Let go of it. */
+ if (list_empty(&file->f_blocks) && !file->f_locks
+ && !file->f_shares && !file->f_count) {
+ hash_del(&file->f_list);
+ nlmsvc_ops->fclose(file->f_file);
+ kfree(file);
}
}
mutex_unlock(&nlm_file_mutex);
@@ -451,3 +449,11 @@ nlmsvc_unlock_all_by_ip(struct sockaddr *server_addr)
return ret ? -EIO : 0;
}
EXPORT_SYMBOL_GPL(nlmsvc_unlock_all_by_ip);
+
+static int __init nlm_init(void)
+{
+ hash_init(nlm_files);
+ return 0;
+}
+
+module_init(nlm_init);
--
1.7.8.6

2012-08-22 02:28:41

[permalink] [raw]

Subject: [PATCH v3 17/17] SUNRPC: use new hashtable implementation in auth

Switch sunrpc/auth.c to use the new hashtable implementation. This reduces the amount of
generic unrelated code in auth.c.

Signed-off-by: Sasha Levin <[email protected]>
---
net/sunrpc/auth.c | 45 +++++++++++++++++++--------------------------
1 files changed, 19 insertions(+), 26 deletions(-)

diff --git a/net/sunrpc/auth.c b/net/sunrpc/auth.c
index b5c067b..5d50e2d 100644
--- a/net/sunrpc/auth.c
+++ b/net/sunrpc/auth.c
@@ -15,6 +15,7 @@
#include <linux/sunrpc/clnt.h>
#include <linux/sunrpc/gss_api.h>
#include <linux/spinlock.h>
+#include <linux/hashtable.h>

#ifdef RPC_DEBUG
# define RPCDBG_FACILITY RPCDBG_AUTH
@@ -222,7 +223,7 @@ static DEFINE_SPINLOCK(rpc_credcache_lock);
static void
rpcauth_unhash_cred_locked(struct rpc_cred *cred)
{
- hlist_del_rcu(&cred->cr_hash);
+ hash_del_rcu(&cred->cr_hash);
smp_mb__before_clear_bit();
clear_bit(RPCAUTH_CRED_HASHED, &cred->cr_flags);
}
@@ -249,16 +250,15 @@ int
rpcauth_init_credcache(struct rpc_auth *auth)
{
struct rpc_cred_cache *new;
- unsigned int hashsize;

new = kmalloc(sizeof(*new), GFP_KERNEL);
if (!new)
goto out_nocache;
new->hashbits = auth_hashbits;
- hashsize = 1U << new->hashbits;
- new->hashtable = kcalloc(hashsize, sizeof(new->hashtable[0]), GFP_KERNEL);
+ new->hashtable = kmalloc(HASH_REQUIRED_SIZE(new->hashbits), GFP_KERNEL);
if (!new->hashtable)
goto out_nohashtbl;
+ hash_init_size(new->hashtable, new->hashbits);
spin_lock_init(&new->lock);
auth->au_credcache = new;
return 0;
@@ -292,25 +292,20 @@ void
rpcauth_clear_credcache(struct rpc_cred_cache *cache)
{
LIST_HEAD(free);
- struct hlist_head *head;
+ struct hlist_node *n, *t;
struct rpc_cred *cred;
- unsigned int hashsize = 1U << cache->hashbits;
- int i;
+ int i;

spin_lock(&rpc_credcache_lock);
spin_lock(&cache->lock);
- for (i = 0; i < hashsize; i++) {
- head = &cache->hashtable[i];
- while (!hlist_empty(head)) {
- cred = hlist_entry(head->first, struct rpc_cred, cr_hash);
- get_rpccred(cred);
- if (!list_empty(&cred->cr_lru)) {
- list_del(&cred->cr_lru);
- number_cred_unused--;
- }
- list_add_tail(&cred->cr_lru, &free);
- rpcauth_unhash_cred_locked(cred);
+ hash_for_each_safe_size(cache->hashtable, cache->hashbits, i, n, t, cred, cr_hash) {
+ get_rpccred(cred);
+ if (!list_empty(&cred->cr_lru)) {
+ list_del(&cred->cr_lru);
+ number_cred_unused--;
}
+ list_add_tail(&cred->cr_lru, &free);
+ rpcauth_unhash_cred_locked(cred);
}
spin_unlock(&cache->lock);
spin_unlock(&rpc_credcache_lock);
@@ -408,14 +403,11 @@ rpcauth_lookup_credcache(struct rpc_auth *auth, struct auth_cred * acred,
LIST_HEAD(free);
struct rpc_cred_cache *cache = auth->au_credcache;
struct hlist_node *pos;
- struct rpc_cred *cred = NULL,
- *entry, *new;
- unsigned int nr;
-
- nr = hash_long(acred->uid, cache->hashbits);
+ struct rpc_cred *cred = NULL, *entry = NULL, *new;

rcu_read_lock();
- hlist_for_each_entry_rcu(entry, pos, &cache->hashtable[nr], cr_hash) {
+ hash_for_each_possible_rcu_size(cache->hashtable, cred, cache->hashbits,
+ pos, cr_hash, acred->uid) {
if (!entry->cr_ops->crmatch(acred, entry, flags))
continue;
spin_lock(&cache->lock);
@@ -439,7 +431,8 @@ rpcauth_lookup_credcache(struct rpc_auth *auth, struct auth_cred * acred,
}

spin_lock(&cache->lock);
- hlist_for_each_entry(entry, pos, &cache->hashtable[nr], cr_hash) {
+ hash_for_each_possible_size(cache->hashtable, entry, cache->hashbits, pos,
+ cr_hash, acred->uid) {
if (!entry->cr_ops->crmatch(acred, entry, flags))
continue;
cred = get_rpccred(entry);
@@ -448,7 +441,7 @@ rpcauth_lookup_credcache(struct rpc_auth *auth, struct auth_cred * acred,
if (cred == NULL) {
cred = new;
set_bit(RPCAUTH_CRED_HASHED, &cred->cr_flags);
- hlist_add_head_rcu(&cred->cr_hash, &cache->hashtable[nr]);
+ hash_add_size(cache->hashtable, cache->hashbits, &cred->cr_hash, acred->uid);
} else
list_add_tail(&new->cr_lru, &free);
spin_unlock(&cache->lock);
--
1.7.8.6

2012-08-24 22:59:03

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

>> Why do we need hash_head/hash_for_each_head()? I haven't stumbled on a place yet
>> that needed direct access to the bucket itself.
>
> Because whole hash table walking is much less common and we can avoid
> another full set of iterators.

I don't agree. Out of 32 places which now use a hashtable iterator of some kind,
12 of them (38%) walk the entire table.

The thing is that usually data structures are indexable by more than one key, so
usually hashtables are fully walked in cold paths to look for different keys.

Take kernel/workqueue.c for example: There are 4 places which do a key lookup
(find_worker_executing_work()) and 3 places which fully walk the entire table
(for_each_busy_worker()).

>> This basically means 11 macros/functions that would let us have full
>> encapsulation and will make it very easy for future implementations to work with
>> this API instead of making up a new one. It's also not significantly (+~2-3)
>> more than the ones you listed.
>
> I'm not sure whether full encapsulation is a good idea for trivial
> hashtable. For higher level stuff, sure but at this level I think
> benefits coming from known obvious implementation can be larger.
> e.g. suppose the caller knows certain entries to be way colder than
> others and wants to put them at the end of the chain.

Thats the thing, the amount of things of things you can do with a given bucket
is very limited. You can't add entries to any point besides the head (without
walking the entire list).

Basically you can do only two things with a bucket:

- Add something to it at a very specific place.
- Walk it

So I don't understand whats the point in exposing the internal structure of the
hashtable if there's nothing significant that can be gained from it by the user.

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

2012-08-22 02:26:57

[permalink] [raw]

Subject: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

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 <[email protected]>
---
include/linux/hashtable.h | 291 +++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 291 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..d2d6ed0
--- /dev/null
+++ b/include/linux/hashtable.h
@@ -0,0 +1,291 @@
+/*
+ * Hash table implementation
+ * (C) 2012 Sasha Levin <[email protected]>
+ */
+
+#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[HASH_SIZE(bits)];
+
+#define HASH_SIZE(bits) (1 << (bits))
+#define HASH_BITS(name) (ilog2(ARRAY_SIZE(name)))
+#define HASH_REQUIRED_SIZE(bits) (sizeof(struct hlist_head) * HASH_SIZE(bits))
+
+/* 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)))
+
+/**
+ * hash_init_size - initialize a hash table
+ * @hashtable: hashtable to be initialized
+ * @bits: bit count of hashing function
+ *
+ * Initializes a hash table with 2**bits buckets.
+ */
+static inline void hash_init_size(struct hlist_head *hashtable, int bits)
+{
+ int i;
+
+ for (i = 0; i < HASH_SIZE(bits); i++)
+ INIT_HLIST_HEAD(hashtable + 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.
+ */
+#define hash_init(name) hash_init_size(name, HASH_BITS(name))
+
+/**
+ * hash_add_size - add an object to a hashtable
+ * @hashtable: hashtable to add to
+ * @bits: bit count used for hashing
+ * @node: the &struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_size(hashtable, bits, node, key) \
+ hlist_add_head(node, &hashtable[hash_min(key, bits)]);
+
+/**
+ * hash_add - add an object to a hashtable
+ * @hashtable: hashtable to add to
+ * @node: the &struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add(hashtable, node, key) \
+ hash_add_size(hashtable, HASH_BITS(hashtable), node, key)
+
+/**
+ * hash_add_rcu_size - add an object to a rcu enabled hashtable
+ * @hashtable: hashtable to add to
+ * @bits: bit count used for hashing
+ * @node: the &struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_rcu_size(hashtable, bits, node, key) \
+ hlist_add_head_rcu(node, &hashtable[hash_min(key, bits)]);
+
+/**
+ * hash_add_rcu - add an object to a rcu enabled hashtable
+ * @hashtable: hashtable to add to
+ * @node: the &struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_rcu(hashtable, node, key) \
+ hash_add_rcu_size(hashtable, HASH_BITS(hashtable), node, key)
+
+/**
+ * hash_hashed - check whether an object is in any hashtable
+ * @node: the &struct hlist_node of the object to be checked
+ */
+#define hash_hashed(node) (!hlist_unhashed(node))
+
+/**
+ * hash_empty_size - check whether a hashtable is empty
+ * @hashtable: hashtable to check
+ * @bits: bit count used for hashing
+ */
+static inline bool hash_empty_size(struct hlist_head *hashtable, int bits)
+{
+ int i;
+
+ for (i = 0; i < HASH_SIZE(bits); i++)
+ if (!hlist_empty(&hashtable[i]))
+ return false;
+
+ return true;
+}
+
+/**
+ * hash_empty - check whether a hashtable is empty
+ * @hashtable: hashtable to check
+ */
+#define hash_empty(name) hash_empty_size(name, HASH_BITS(name))
+
+/**
+ * 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_size - iterate over a hashtable
+ * @name: hashtable to iterate
+ * @bits: bit count of hashing function of the hashtable
+ * @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_size(name, bits, bkt, node, obj, member) \
+ for (bkt = 0; bkt < HASH_SIZE(bits); bkt++) \
+ hlist_for_each_entry(obj, node, &name[bkt], member)
+
+/**
+ * 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, obj, member) \
+ hash_for_each_size(name, HASH_BITS(name), bkt, node, obj, member)
+
+/**
+ * hash_for_each_rcu_size - iterate over a rcu enabled hashtable
+ * @name: hashtable to iterate
+ * @bits: bit count of hashing function of the hashtable
+ * @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_rcu_size(name, bits, bkt, node, obj, member) \
+ for (bkt = 0; bkt < HASH_SIZE(bits); bkt++) \
+ hlist_for_each_entry_rcu(obj, node, &name[bkt], member)
+
+/**
+ * hash_for_each_rcu - iterate over a rcu enabled 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_rcu(name, bkt, node, obj, member) \
+ hash_for_each_rcu_size(name, HASH_BITS(name), bkt, node, obj, member)
+
+/**
+ * hash_for_each_safe_size - iterate over a hashtable safe against removal of
+ * hash entry
+ * @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
+ * @tmp: another &struct hlist_node to use as temporary storage
+ * @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_safe_size(name, bits, bkt, node, tmp, obj, member) \
+ for (bkt = 0; bkt < HASH_SIZE(bits); bkt++) \
+ hlist_for_each_entry_safe(obj, node, tmp, &name[bkt], member)
+
+/**
+ * hash_for_each_safe_size - iterate over a hashtable safe against removal of
+ * hash entry
+ * @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_safe(name, bkt, node, tmp, obj, member) \
+ hash_for_each_safe_size(name, HASH_BITS(name), bkt, node, \
+ tmp, obj, member)
+
+/**
+ * hash_for_each_possible - iterate over all possible objects hasing to the
+ * same bucket
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each entry
+ * @bits: bit count of hashing function of the hashtable
+ * @node: the &struct list_head to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ * @key: the key of the objects to iterate over
+ */
+#define hash_for_each_possible_size(name, obj, bits, node, member, key) \
+ hlist_for_each_entry(obj, node, &name[hash_min(key, bits)], member)
+
+/**
+ * hash_for_each_possible - iterate over all possible objects hashing to the
+ * same bucket
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each entry
+ * @bits: bit count of hashing function of the hashtable
+ * @node: the &struct list_head to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ * @key: the key of the objects to iterate over
+ */
+#define hash_for_each_possible(name, obj, node, member, key) \
+ hash_for_each_possible_size(name, obj, HASH_BITS(name), node, member, key)
+
+/**
+ * hash_for_each_possible - iterate over all possible objects hashing to the
+ * same bucket
+ * in a rcu enabled hashtable
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each entry
+ * @bits: bit count of hashing function of the hashtable
+ * @node: the &struct list_head to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ * @key: the key of the objects to iterate over
+ */
+#define hash_for_each_possible_rcu_size(name, obj, bits, node, member, key) \
+ hlist_for_each_entry_rcu(obj, node, &name[hash_min(key, bits)], member)
+
+/**
+ * hash_for_each_possible - iterate over all possible objects hashing to the
+ * same bucket
+ * in a rcu enabled hashtable
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each entry
+ * @node: the &struct list_head to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ * @key: the key of the objects to iterate over
+ */
+#define hash_for_each_possible_rcu(name, obj, node, member, key) \
+ hash_for_each_possible_rcu_size(name, obj, HASH_BITS(name), \
+ node, member, key)
+
+/**
+ * hash_for_each_possible - iterate over all possible objects hashing to the
+ * same bucket
+ * safe against removal of hash entry
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each entry
+ * @bits: bit count of hashing function of the hashtable
+ * @node: the &struct list_head to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ * @key: the key of the objects to iterate over
+ */
+#define hash_for_each_possible_safe_size(name, obj, bits, node, tmp, member, key)\
+ hlist_for_each_entry_safe(obj, node, tmp, \
+ &name[hash_min(key, bits)], member)
+
+/**
+ * hash_for_each_possible - iterate over all possible objects hashing to the
+ * same bucket
+ * safe against removal of hash entry
+ * @name: hashtable to iterate
+ * @obj: the type * to use as a loop cursor for each entry
+ * @node: the &struct list_head to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ * @key: the key of the objects to iterate over
+ */
+#define hash_for_each_possible_safe(name, obj, node, tmp, member, key) \
+ hash_for_each_possible_safe_size(name, obj, HASH_BITS(name), \
+ node, tmp, member, key)
+
+#endif
--
1.7.8.6

2012-08-22 02:27:58

[permalink] [raw]

Subject: [PATCH v3 11/17] net,l2tp: use new hashtable implementation

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

Signed-off-by: Sasha Levin <[email protected]>
---
net/l2tp/l2tp_core.c | 134 +++++++++++++++++-----------------------------
net/l2tp/l2tp_core.h | 8 ++--
net/l2tp/l2tp_debugfs.c | 19 +++----
3 files changed, 61 insertions(+), 100 deletions(-)

diff --git a/net/l2tp/l2tp_core.c b/net/l2tp/l2tp_core.c
index 393355d..1d395ce 100644
--- a/net/l2tp/l2tp_core.c
+++ b/net/l2tp/l2tp_core.c
@@ -44,6 +44,7 @@
#include <linux/udp.h>
#include <linux/l2tp.h>
#include <linux/hash.h>
+#include <linux/hashtable.h>
#include <linux/sort.h>
#include <linux/file.h>
#include <linux/nsproxy.h>
@@ -107,8 +108,8 @@ static unsigned int l2tp_net_id;
struct l2tp_net {
struct list_head l2tp_tunnel_list;
spinlock_t l2tp_tunnel_list_lock;
- struct hlist_head l2tp_session_hlist[L2TP_HASH_SIZE_2];
- spinlock_t l2tp_session_hlist_lock;
+ DEFINE_HASHTABLE(l2tp_session_hash, L2TP_HASH_BITS_2)
+ spinlock_t l2tp_session_hash_lock;
};

static void l2tp_session_set_header_len(struct l2tp_session *session, int version);
@@ -156,30 +157,17 @@ do { \
#define l2tp_tunnel_dec_refcount(t) l2tp_tunnel_dec_refcount_1(t)
#endif

-/* Session hash global list for L2TPv3.
- * The session_id SHOULD be random according to RFC3931, but several
- * L2TP implementations use incrementing session_ids. So we do a real
- * hash on the session_id, rather than a simple bitmask.
- */
-static inline struct hlist_head *
-l2tp_session_id_hash_2(struct l2tp_net *pn, u32 session_id)
-{
- return &pn->l2tp_session_hlist[hash_32(session_id, L2TP_HASH_BITS_2)];
-
-}
-
/* Lookup a session by id in the global session list
*/
static struct l2tp_session *l2tp_session_find_2(struct net *net, u32 session_id)
{
struct l2tp_net *pn = l2tp_pernet(net);
- struct hlist_head *session_list =
- l2tp_session_id_hash_2(pn, session_id);
struct l2tp_session *session;
struct hlist_node *walk;

rcu_read_lock_bh();
- hlist_for_each_entry_rcu(session, walk, session_list, global_hlist) {
+ hash_for_each_possible_rcu(pn->l2tp_session_hash, session, walk,
+ global_hlist, session_id) {
if (session->session_id == session_id) {
rcu_read_unlock_bh();
return session;
@@ -190,23 +178,10 @@ static struct l2tp_session *l2tp_session_find_2(struct net *net, u32 session_id)
return NULL;
}

-/* Session hash list.
- * The session_id SHOULD be random according to RFC2661, but several
- * L2TP implementations (Cisco and Microsoft) use incrementing
- * session_ids. So we do a real hash on the session_id, rather than a
- * simple bitmask.
- */
-static inline struct hlist_head *
-l2tp_session_id_hash(struct l2tp_tunnel *tunnel, u32 session_id)
-{
- return &tunnel->session_hlist[hash_32(session_id, L2TP_HASH_BITS)];
-}
-
/* Lookup a session by id
*/
struct l2tp_session *l2tp_session_find(struct net *net, struct l2tp_tunnel *tunnel, u32 session_id)
{
- struct hlist_head *session_list;
struct l2tp_session *session;
struct hlist_node *walk;

@@ -217,15 +192,14 @@ struct l2tp_session *l2tp_session_find(struct net *net, struct l2tp_tunnel *tunn
if (tunnel == NULL)
return l2tp_session_find_2(net, session_id);

- session_list = l2tp_session_id_hash(tunnel, session_id);
- read_lock_bh(&tunnel->hlist_lock);
- hlist_for_each_entry(session, walk, session_list, hlist) {
+ read_lock_bh(&tunnel->hash_lock);
+ hash_for_each_possible(tunnel->session_hash, session, walk, hlist, session_id) {
if (session->session_id == session_id) {
- read_unlock_bh(&tunnel->hlist_lock);
+ read_unlock_bh(&tunnel->hash_lock);
return session;
}
}
- read_unlock_bh(&tunnel->hlist_lock);
+ read_unlock_bh(&tunnel->hash_lock);

return NULL;
}
@@ -238,17 +212,15 @@ struct l2tp_session *l2tp_session_find_nth(struct l2tp_tunnel *tunnel, int nth)
struct l2tp_session *session;
int count = 0;

- read_lock_bh(&tunnel->hlist_lock);
- for (hash = 0; hash < L2TP_HASH_SIZE; hash++) {
- hlist_for_each_entry(session, walk, &tunnel->session_hlist[hash], hlist) {
- if (++count > nth) {
- read_unlock_bh(&tunnel->hlist_lock);
- return session;
- }
+ read_lock_bh(&tunnel->hash_lock);
+ hash_for_each(tunnel->session_hash, hash, walk, session, hlist) {
+ if (++count > nth) {
+ read_unlock_bh(&tunnel->hash_lock);
+ return session;
}
}

- read_unlock_bh(&tunnel->hlist_lock);
+ read_unlock_bh(&tunnel->hash_lock);

return NULL;
}
@@ -265,12 +237,10 @@ struct l2tp_session *l2tp_session_find_by_ifname(struct net *net, char *ifname)
struct l2tp_session *session;

rcu_read_lock_bh();
- for (hash = 0; hash < L2TP_HASH_SIZE_2; hash++) {
- hlist_for_each_entry_rcu(session, walk, &pn->l2tp_session_hlist[hash], global_hlist) {
- if (!strcmp(session->ifname, ifname)) {
- rcu_read_unlock_bh();
- return session;
- }
+ hash_for_each_rcu(pn->l2tp_session_hash, hash, walk, session, global_hlist) {
+ if (!strcmp(session->ifname, ifname)) {
+ rcu_read_unlock_bh();
+ return session;
}
}

@@ -1272,7 +1242,7 @@ end:
*/
static void l2tp_tunnel_closeall(struct l2tp_tunnel *tunnel)
{
- int hash;
+ int hash, found = 0;
struct hlist_node *walk;
struct hlist_node *tmp;
struct l2tp_session *session;
@@ -1282,16 +1252,14 @@ static void l2tp_tunnel_closeall(struct l2tp_tunnel *tunnel)
l2tp_info(tunnel, L2TP_MSG_CONTROL, "%s: closing all sessions...\n",
tunnel->name);

- write_lock_bh(&tunnel->hlist_lock);
- for (hash = 0; hash < L2TP_HASH_SIZE; hash++) {
-again:
- hlist_for_each_safe(walk, tmp, &tunnel->session_hlist[hash]) {
- session = hlist_entry(walk, struct l2tp_session, hlist);
-
+ write_lock_bh(&tunnel->hash_lock);
+ do {
+ found = 0;
+ hash_for_each_safe(tunnel->session_hash, hash, walk, tmp, session, hlist) {
l2tp_info(session, L2TP_MSG_CONTROL,
"%s: closing session\n", session->name);

- hlist_del_init(&session->hlist);
+ hash_del(&session->hlist);

/* Since we should hold the sock lock while
* doing any unbinding, we need to release the
@@ -1302,14 +1270,14 @@ again:
if (session->ref != NULL)
(*session->ref)(session);

- write_unlock_bh(&tunnel->hlist_lock);
+ write_unlock_bh(&tunnel->hash_lock);

if (tunnel->version != L2TP_HDR_VER_2) {
struct l2tp_net *pn = l2tp_pernet(tunnel->l2tp_net);

- spin_lock_bh(&pn->l2tp_session_hlist_lock);
- hlist_del_init_rcu(&session->global_hlist);
- spin_unlock_bh(&pn->l2tp_session_hlist_lock);
+ spin_lock_bh(&pn->l2tp_session_hash_lock);
+ hash_del_rcu(&session->global_hlist);
+ spin_unlock_bh(&pn->l2tp_session_hash_lock);
synchronize_rcu();
}

@@ -1319,17 +1287,17 @@ again:
if (session->deref != NULL)
(*session->deref)(session);

- write_lock_bh(&tunnel->hlist_lock);
+ write_lock_bh(&tunnel->hash_lock);

/* Now restart from the beginning of this hash
* chain. We always remove a session from the
* list so we are guaranteed to make forward
* progress.
*/
- goto again;
+ found = 1;
}
- }
- write_unlock_bh(&tunnel->hlist_lock);
+ } while (found);
+ write_unlock_bh(&tunnel->hash_lock);
}

/* Really kill the tunnel.
@@ -1575,7 +1543,7 @@ int l2tp_tunnel_create(struct net *net, int fd, int version, u32 tunnel_id, u32

tunnel->magic = L2TP_TUNNEL_MAGIC;
sprintf(&tunnel->name[0], "tunl %u", tunnel_id);
- rwlock_init(&tunnel->hlist_lock);
+ rwlock_init(&tunnel->hash_lock);

/* The net we belong to */
tunnel->l2tp_net = net;
@@ -1610,6 +1578,8 @@ int l2tp_tunnel_create(struct net *net, int fd, int version, u32 tunnel_id, u32

/* Add tunnel to our list */
INIT_LIST_HEAD(&tunnel->list);
+
+ hash_init(tunnel->session_hash);
atomic_inc(&l2tp_tunnel_count);

/* Bump the reference count. The tunnel context is deleted
@@ -1674,17 +1644,17 @@ void l2tp_session_free(struct l2tp_session *session)
BUG_ON(tunnel->magic != L2TP_TUNNEL_MAGIC);

/* Delete the session from the hash */
- write_lock_bh(&tunnel->hlist_lock);
- hlist_del_init(&session->hlist);
- write_unlock_bh(&tunnel->hlist_lock);
+ write_lock_bh(&tunnel->hash_lock);
+ hash_del(&session->hlist);
+ write_unlock_bh(&tunnel->hash_lock);

/* Unlink from the global hash if not L2TPv2 */
if (tunnel->version != L2TP_HDR_VER_2) {
struct l2tp_net *pn = l2tp_pernet(tunnel->l2tp_net);

- spin_lock_bh(&pn->l2tp_session_hlist_lock);
- hlist_del_init_rcu(&session->global_hlist);
- spin_unlock_bh(&pn->l2tp_session_hlist_lock);
+ spin_lock_bh(&pn->l2tp_session_hash_lock);
+ hash_del_rcu(&session->global_hlist);
+ spin_unlock_bh(&pn->l2tp_session_hash_lock);
synchronize_rcu();
}

@@ -1797,19 +1767,17 @@ struct l2tp_session *l2tp_session_create(int priv_size, struct l2tp_tunnel *tunn
sock_hold(tunnel->sock);

/* Add session to the tunnel's hash list */
- write_lock_bh(&tunnel->hlist_lock);
- hlist_add_head(&session->hlist,
- l2tp_session_id_hash(tunnel, session_id));
- write_unlock_bh(&tunnel->hlist_lock);
+ write_lock_bh(&tunnel->hash_lock);
+ hash_add(tunnel->session_hash, &session->hlist, session_id);
+ write_unlock_bh(&tunnel->hash_lock);

/* And to the global session list if L2TPv3 */
if (tunnel->version != L2TP_HDR_VER_2) {
struct l2tp_net *pn = l2tp_pernet(tunnel->l2tp_net);

- spin_lock_bh(&pn->l2tp_session_hlist_lock);
- hlist_add_head_rcu(&session->global_hlist,
- l2tp_session_id_hash_2(pn, session_id));
- spin_unlock_bh(&pn->l2tp_session_hlist_lock);
+ spin_lock_bh(&pn->l2tp_session_hash_lock);
+ hash_add(pn->l2tp_session_hash, &session->global_hlist, session_id);
+ spin_unlock_bh(&pn->l2tp_session_hash_lock);
}

/* Ignore management session in session count value */
@@ -1828,15 +1796,13 @@ EXPORT_SYMBOL_GPL(l2tp_session_create);
static __net_init int l2tp_init_net(struct net *net)
{
struct l2tp_net *pn = net_generic(net, l2tp_net_id);
- int hash;

INIT_LIST_HEAD(&pn->l2tp_tunnel_list);
spin_lock_init(&pn->l2tp_tunnel_list_lock);

- for (hash = 0; hash < L2TP_HASH_SIZE_2; hash++)
- INIT_HLIST_HEAD(&pn->l2tp_session_hlist[hash]);
+ hash_init(pn->l2tp_session_hash);

- spin_lock_init(&pn->l2tp_session_hlist_lock);
+ spin_lock_init(&pn->l2tp_session_hash_lock);

return 0;
}
diff --git a/net/l2tp/l2tp_core.h b/net/l2tp/l2tp_core.h
index a38ec6c..23bf320 100644
--- a/net/l2tp/l2tp_core.h
+++ b/net/l2tp/l2tp_core.h
@@ -11,17 +11,17 @@
#ifndef _L2TP_CORE_H_
#define _L2TP_CORE_H_

+#include <linux/hashtable.h>
+
/* Just some random numbers */
#define L2TP_TUNNEL_MAGIC 0x42114DDA
#define L2TP_SESSION_MAGIC 0x0C04EB7D

/* Per tunnel, session hash table size */
#define L2TP_HASH_BITS 4
-#define L2TP_HASH_SIZE (1 << L2TP_HASH_BITS)

/* System-wide, session hash table size */
#define L2TP_HASH_BITS_2 8
-#define L2TP_HASH_SIZE_2 (1 << L2TP_HASH_BITS_2)

/* Debug message categories for the DEBUG socket option */
enum {
@@ -163,8 +163,8 @@ struct l2tp_tunnel_cfg {

struct l2tp_tunnel {
int magic; /* Should be L2TP_TUNNEL_MAGIC */
- rwlock_t hlist_lock; /* protect session_hlist */
- struct hlist_head session_hlist[L2TP_HASH_SIZE];
+ rwlock_t hash_lock; /* protect session_hash */
+ DEFINE_HASHTABLE(session_hash, L2TP_HASH_BITS);
/* hashed list of sessions,
* hashed by id */
u32 tunnel_id;
diff --git a/net/l2tp/l2tp_debugfs.c b/net/l2tp/l2tp_debugfs.c
index c3813bc..655f1fa 100644
--- a/net/l2tp/l2tp_debugfs.c
+++ b/net/l2tp/l2tp_debugfs.c
@@ -105,21 +105,16 @@ static void l2tp_dfs_seq_tunnel_show(struct seq_file *m, void *v)
int session_count = 0;
int hash;
struct hlist_node *walk;
- struct hlist_node *tmp;
+ struct l2tp_session *session;

- read_lock_bh(&tunnel->hlist_lock);
- for (hash = 0; hash < L2TP_HASH_SIZE; hash++) {
- hlist_for_each_safe(walk, tmp, &tunnel->session_hlist[hash]) {
- struct l2tp_session *session;
+ read_lock_bh(&tunnel->hash_lock);
+ hash_for_each(tunnel->session_hash, hash, walk, session, hlist) {
+ if (session->session_id == 0)
+ continue;

- session = hlist_entry(walk, struct l2tp_session, hlist);
- if (session->session_id == 0)
- continue;
-
- session_count++;
- }
+ session_count++;
}
- read_unlock_bh(&tunnel->hlist_lock);
+ read_unlock_bh(&tunnel->hash_lock);

seq_printf(m, "\nTUNNEL %u peer %u", tunnel->tunnel_id, tunnel->peer_tunnel_id);
if (tunnel->sock) {
--
1.7.8.6

2012-08-23 20:05:01

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

Hello, Sasha.

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

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

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

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

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

Thanks.

--
tejun

2012-08-28 10:11:51

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

* Sasha Levin ([email protected]) wrote:
> On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
> > * Tejun Heo ([email protected]) wrote:
> >> Hello,
> >>
> >> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> >>> Thats the thing, the amount of things of things you can do with a given bucket
> >>> is very limited. You can't add entries to any point besides the head (without
> >>> walking the entire list).
> >>
> >> Kinda my point. We already have all the hlist*() interface to deal
> >> with such cases. Having something which is evidently the trivial
> >> hlist hashtable and advertises as such in the interface can be
> >> helpful. I think we need that more than we need anything fancy.
> >>
> >> Heh, this is a debate about which one is less insignificant. I can
> >> see your point. I'd really like to hear what others think on this.
> >>
> >> Guys, do we want something which is evidently trivial hlist hashtable
> >> which can use hlist_*() API directly or do we want something better
> >> encapsulated?
> >
> > My 2 cents, FWIW: I think this specific effort should target a trivially
> > understandable API and implementation, for use-cases where one would be
> > tempted to reimplement his own trivial hash table anyway. So here
> > exposing hlist internals, with which kernel developers are already
> > familiar, seems like a good approach in my opinion, because hiding stuff
> > behind new abstraction might make the target users go away.
> >
> > Then, as we see the need, we can eventually merge a more elaborate hash
> > table with poneys and whatnot, but I would expect that the trivial hash
> > table implementation would still be useful. There are of course very
> > compelling reasons to use a more featureful hash table: automatic
> > resize, RT-aware updates, scalable updates, etc... but I see a purpose
> > for a trivial implementation. Its primary strong points being:
> >
> > - it's trivially understandable, so anyone how want to be really sure
> > they won't end up debugging the hash table instead of their
> > work-in-progress code can have a full understanding of it,
> > - it has few dependencies, which makes it easier to understand and
> > easier to use in some contexts (e.g. early boot).
> >
> > So I'm in favor of not overdoing the abstraction for this trivial hash
> > table, and honestly I would rather prefer that this trivial hash table
> > stays trivial. A more elaborate hash table should probably come as a
> > separate API.
> >
> > Thanks,
> >
> > Mathieu
> >
>
> Alright, let's keep it simple then.
>
> I do want to keep the hash_for_each[rcu,safe] family though.

Just a thought: if the API offered by the simple hash table focus on
providing a mechanism to find the hash bucket to which belongs the hash
chain containing the key looked up, and then expects the user to use the
hlist API to iterate on the chain (with or without the hlist _rcu
variant), then it might seem consistent that a helper providing
iteration over the entire table would actually just provide iteration on
all buckets, and let the user call the hlist for each iterator for each
node within the bucket, e.g.:

struct hlist_head *head;
struct hlist_node *pos;

hash_for_each_bucket(ht, head) {
hlist_for_each(pos, head) {
...
}
}

That way you only have to provide one single macro
(hash_for_each_bucket), and rely on the already existing:

- hlist_for_each_entry
- hlist_for_each_safe
- hlist_for_each_entry_rcu
- hlist_for_each_safe_rcu
.....

and various flavors that can appear in the future without duplicating
this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
versions of the hash_for_each_bucket macro.

Thoughts ?

Thanks,

Mathieu

--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

2012-09-04 20:59:10

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

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

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

-- Steve

2012-09-06 17:15:46

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On Thu, 2012-09-06 at 18:21 +0200, Sasha Levin wrote:
> On 09/06/2012 06:00 PM, Steven Rostedt wrote:
> >> > I think that that code doesn't make sense. The users of hlist_for_each_* aren't
> >> > supposed to be changing the loop cursor.
> > I totally agree. Modifying the 'node' pointer is just asking for issues.
> > Yes that is error prone, but not due to the double loop. It's due to the
> > modifying of the node pointer that is used internally by the loop
> > counter. Don't do that :-)
>
> While we're on this subject, I haven't actually seen hlist_for_each_entry() code
> that even *touches* 'pos'.
>
> Will people yell at me loudly if I change the prototype of those macros to be:
>
> hlist_for_each_entry(tpos, head, member)
>
> (Dropping the 'pos' parameter), and updating anything that calls those macros to
> drop it as well?

If 'pos' is no longer used in the macro, I don't see any reason for
keeping it around.

-- Steve

2012-09-06 16:21:31

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On 09/06/2012 06:00 PM, Steven Rostedt wrote:
>> > I think that that code doesn't make sense. The users of hlist_for_each_* aren't
>> > supposed to be changing the loop cursor.
> I totally agree. Modifying the 'node' pointer is just asking for issues.
> Yes that is error prone, but not due to the double loop. It's due to the
> modifying of the node pointer that is used internally by the loop
> counter. Don't do that :-)

While we're on this subject, I haven't actually seen hlist_for_each_entry() code
that even *touches* 'pos'.

Will people yell at me loudly if I change the prototype of those macros to be:

hlist_for_each_entry(tpos, head, member)

(Dropping the 'pos' parameter), and updating anything that calls those macros to
drop it as well?

Thanks,
Sasha

2012-09-06 15:49:19

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On 09/06/2012 04:55 PM, Josh Triplett wrote:
> On Thu, Sep 06, 2012 at 03:53:58PM +0200, Sasha Levin wrote:
>> On 09/04/2012 07:01 PM, Mathieu Desnoyers wrote:
>>>> #define do_for_each_ftrace_rec(pg, rec) \
>>>>> for (pg = ftrace_pages_start, rec = &pg->records[pg->index]; \
>>>>> pg && rec == &pg->records[pg->index]; \
>>>>> pg = pg->next) \
>>>>> for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
>>> Maybe in some cases there might be ways to combine the two loops into
>>> one ? I'm not seeing exactly how to do it for this one, but it should
>>> not be impossible. If the inner loop condition can be moved to the outer
>>> loop, and if we use (blah ? loop1_conf : loop2_cond) to test for
>>> different conditions depending on the context, and do the same for the
>>> 3rd argument of the for() loop. The details elude me for now though, so
>>> maybe it's complete non-sense ;)
>>>
>>> It might not be that useful for do_for_each_ftrace_rec, but if we can do
>>> it for the hash table iterator, it might be worth it.
>>
>> So I think that for the hash iterator it might actually be simpler.
>>
>> My solution to making 'break' work in the iterator is:A code like that doesn
>>
>> for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
>> hlist_for_each_entry(obj, node, &name[bkt], member)
>>
>> We initialize our node loop cursor with NULL in the external loop, and the
>> external loop will have a new condition to loop while that cursor is NULL.
>>
>> My logic is that we can only 'break' when we are iterating over an object in the
>> internal loop. If we're iterating over an object in that loop then 'node != NULL'.
>>
>> This way, if we broke from within the internal loop, the external loop will see
>> node as not NULL, and so it will stop looping itself. On the other hand, if the
>> internal loop has actually ended, then node will be NULL, and the outer loop
>> will keep running.
>>
>> Is there anything I've missed?
>
> Looks reasonable. However, it would break (or rather, not break) on
> code like this:
>
> hash_for_each_entry(...) {
> if (...) {
> foo(node);
> node = NULL;
> break;
> }
> }
>
> Hiding the double loop still seems error-prone.

I think that that code doesn't make sense. The users of hlist_for_each_* aren't
supposed to be changing the loop cursor.

We have three options here:

1. Stuff everything into a single for(). While not too difficult, it will make
the readability of the code difficult as it will force us to abandon using
hlist_for_each_* macros.

2. Over-complicate everything, and check for 'node == NULL && obj &&
obj->member.next == NULL' instead. That one will fail only if the user has
specifically set the object as the last object in the list and the node as NULL.

3. Use 2 loops which might not work properly if the user does something odd,
with a big fat warning above them.

To sum it up, I'd rather go with 3 and let anyone who does things he shouldn't
be doing break.

Thanks,
Sasha

2012-09-06 16:50:58

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

* Sasha Levin ([email protected]) wrote:
> On 09/06/2012 06:00 PM, Steven Rostedt wrote:
> >> > I think that that code doesn't make sense. The users of hlist_for_each_* aren't
> >> > supposed to be changing the loop cursor.
> > I totally agree. Modifying the 'node' pointer is just asking for issues.
> > Yes that is error prone, but not due to the double loop. It's due to the
> > modifying of the node pointer that is used internally by the loop
> > counter. Don't do that :-)
>
> While we're on this subject, I haven't actually seen hlist_for_each_entry() code
> that even *touches* 'pos'.
>
> Will people yell at me loudly if I change the prototype of those macros to be:
>
> hlist_for_each_entry(tpos, head, member)
>
> (Dropping the 'pos' parameter), and updating anything that calls those macros to
> drop it as well?

I think the intent there is to keep hlist macros and list macros
slightly in sync. Given those are vastly used, I'm not sure you want to
touch them. But hey, that's just my 2 cents.

Thanks,

Mathieu

>
>
> Thanks,
> Sasha

--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

2012-09-04 21:51:48

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

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

Please explain why it would fail on a 'break'.

--
Pedro Alves

2012-09-04 23:27:11

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On Tue, 2012-09-04 at 23:58 +0100, Pedro Alves wrote:

> Not true. The comma operator introduces a sequence point. It's the comma
> that separates function parameters that doesn't guarantee ordering.

Bah! C language is almost as confusing as English.

-- Steve

2012-09-04 16:40:53

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On 09/04/2012 05:30 PM, Pedro Alves wrote:
> On 09/04/2012 04:35 PM, Steven Rostedt wrote:
>> On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:
>>
>>> Looking again at:
>>>
>>> +#define hash_for_each_size(name, bits, bkt, node, obj, member) \
>>> + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++) \
>>> + hlist_for_each_entry(obj, node, &name[bkt], member)
>>>
>>> you will notice that a "break" or "continue" in the inner loop will not
>>> affect the outer loop, which is certainly not what the programmer would
>>> expect!
>>>
>>> I advise strongly against creating such error-prone construct.
>>>
>>
>> A few existing loop macros do this. But they require a do { } while ()
>> approach, and all have a comment.
>>
>> It's used by do_each_thread() in sched.h and ftrace does this as well.
>> Look at kernel/trace/ftrace.c at do_for_each_ftrace_rec().
>>
>> Yes it breaks 'break' but it does not break 'continue' as it would just
>> go to the next item that would have been found (like a normal for
>> would).
>
> /*
> * This is a double for. Do not use 'break' to break out of the loop,
> * you must use a goto.
> */
> #define do_for_each_ftrace_rec(pg, rec) \
> for (pg = ftrace_pages_start; pg; pg = pg->next) { \
> int _____i; \
> for (_____i = 0; _____i < pg->index; _____i++) { \
> rec = &pg->records[_____i];
>
>
>
> You can make 'break' also work as expected if you can embed a little knowledge
> of the inner loop's condition in the outer loop's condition. Sometimes it's
> trivial, most often when the inner loop's iterator is a pointer that goes
> NULL at the end, but other times not so much. Something like (completely untested):
>
> #define do_for_each_ftrace_rec(pg, rec) \
> for (pg = ftrace_pages_start, rec = &pg->records[pg->index]; \
> pg && rec == &pg->records[pg->index]; \
> pg = pg->next) { \
> int _____i; \
> for (_____i = 0; _____i < pg->index; _____i++) { \
> rec = &pg->records[_____i];
>
>
> (other variants possible)
>
> IOW, the outer loop only iterates if the inner loop completes. If there's
> a break in the inner loop, then the outer loop breaks too. Of course, it
> all depends on whether the generated code looks sane or hideous, if
> the uses of the macro care for it over bug avoidance.
>

BTW, you can also go a step further and remove the need to close with double }},
with something like:

#define do_for_each_ftrace_rec(pg, rec) \
for (pg = ftrace_pages_start, rec = &pg->records[pg->index]; \
pg && rec == &pg->records[pg->index]; \
pg = pg->next) \
for (rec = pg->records; rec < &pg->records[pg->index]; rec++)

--
Pedro Alves

2012-09-04 17:01:40

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

* Pedro Alves ([email protected]) wrote:
> On 09/04/2012 05:30 PM, Pedro Alves wrote:
> > On 09/04/2012 04:35 PM, Steven Rostedt wrote:
> >> On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:
> >>
> >>> Looking again at:
> >>>
> >>> +#define hash_for_each_size(name, bits, bkt, node, obj, member) \
> >>> + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++) \
> >>> + hlist_for_each_entry(obj, node, &name[bkt], member)
> >>>
> >>> you will notice that a "break" or "continue" in the inner loop will not
> >>> affect the outer loop, which is certainly not what the programmer would
> >>> expect!
> >>>
> >>> I advise strongly against creating such error-prone construct.
> >>>
> >>
> >> A few existing loop macros do this. But they require a do { } while ()
> >> approach, and all have a comment.
> >>
> >> It's used by do_each_thread() in sched.h and ftrace does this as well.
> >> Look at kernel/trace/ftrace.c at do_for_each_ftrace_rec().
> >>
> >> Yes it breaks 'break' but it does not break 'continue' as it would just
> >> go to the next item that would have been found (like a normal for
> >> would).
> >
> > /*
> > * This is a double for. Do not use 'break' to break out of the loop,
> > * you must use a goto.
> > */
> > #define do_for_each_ftrace_rec(pg, rec) \
> > for (pg = ftrace_pages_start; pg; pg = pg->next) { \
> > int _____i; \
> > for (_____i = 0; _____i < pg->index; _____i++) { \
> > rec = &pg->records[_____i];
> >
> >
> >
> > You can make 'break' also work as expected if you can embed a little knowledge
> > of the inner loop's condition in the outer loop's condition. Sometimes it's
> > trivial, most often when the inner loop's iterator is a pointer that goes
> > NULL at the end, but other times not so much. Something like (completely untested):
> >
> > #define do_for_each_ftrace_rec(pg, rec) \
> > for (pg = ftrace_pages_start, rec = &pg->records[pg->index]; \
> > pg && rec == &pg->records[pg->index]; \
> > pg = pg->next) { \
> > int _____i; \
> > for (_____i = 0; _____i < pg->index; _____i++) { \
> > rec = &pg->records[_____i];
> >
> >
> > (other variants possible)
> >
> > IOW, the outer loop only iterates if the inner loop completes. If there's
> > a break in the inner loop, then the outer loop breaks too. Of course, it
> > all depends on whether the generated code looks sane or hideous, if
> > the uses of the macro care for it over bug avoidance.
> >
>
> BTW, you can also go a step further and remove the need to close with double }},
> with something like:
>
> #define do_for_each_ftrace_rec(pg, rec) \
> for (pg = ftrace_pages_start, rec = &pg->records[pg->index]; \
> pg && rec == &pg->records[pg->index]; \
> pg = pg->next) \
> for (rec = pg->records; rec < &pg->records[pg->index]; rec++)

Maybe in some cases there might be ways to combine the two loops into
one ? I'm not seeing exactly how to do it for this one, but it should
not be impossible. If the inner loop condition can be moved to the outer
loop, and if we use (blah ? loop1_conf : loop2_cond) to test for
different conditions depending on the context, and do the same for the
3rd argument of the for() loop. The details elude me for now though, so
maybe it's complete non-sense ;)

It might not be that useful for do_for_each_ftrace_rec, but if we can do
it for the hash table iterator, it might be worth it.

Thanks,

Mathieu

--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

2012-09-06 14:33:23

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

* Sasha Levin ([email protected]) wrote:
> On 09/04/2012 07:01 PM, Mathieu Desnoyers wrote:
> >> #define do_for_each_ftrace_rec(pg, rec) \
> >> > for (pg = ftrace_pages_start, rec = &pg->records[pg->index]; \
> >> > pg && rec == &pg->records[pg->index]; \
> >> > pg = pg->next) \
> >> > for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
> > Maybe in some cases there might be ways to combine the two loops into
> > one ? I'm not seeing exactly how to do it for this one, but it should
> > not be impossible. If the inner loop condition can be moved to the outer
> > loop, and if we use (blah ? loop1_conf : loop2_cond) to test for
> > different conditions depending on the context, and do the same for the
> > 3rd argument of the for() loop. The details elude me for now though, so
> > maybe it's complete non-sense ;)
> >
> > It might not be that useful for do_for_each_ftrace_rec, but if we can do
> > it for the hash table iterator, it might be worth it.
>
> So I think that for the hash iterator it might actually be simpler.
>
> My solution to making 'break' work in the iterator is:
>
> for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
> hlist_for_each_entry(obj, node, &name[bkt], member)
>
> We initialize our node loop cursor with NULL in the external loop, and the
> external loop will have a new condition to loop while that cursor is NULL.
>
> My logic is that we can only 'break' when we are iterating over an object in the
> internal loop. If we're iterating over an object in that loop then 'node != NULL'.
>
> This way, if we broke from within the internal loop, the external loop will see
> node as not NULL, and so it will stop looping itself. On the other hand, if the
> internal loop has actually ended, then node will be NULL, and the outer loop
> will keep running.
>
> Is there anything I've missed?

This sounds good. Unless I'm missing something too.

Thanks!

Mathieu

>
>
> Thanks,
> Sasha

--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

2012-09-06 16:00:10

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On Thu, 2012-09-06 at 17:49 +0200, Sasha Levin wrote:
>
> > Looks reasonable. However, it would break (or rather, not break) on
> > code like this:
> >
> > hash_for_each_entry(...) {
> > if (...) {
> > foo(node);
> > node = NULL;

ug, I didn't even notice this. Ignore my last email :-p

/me needs to wake-up a bit more.

> > break;
> > }
> > }
> >
> > Hiding the double loop still seems error-prone.
>
> I think that that code doesn't make sense. The users of hlist_for_each_* aren't
> supposed to be changing the loop cursor.

I totally agree. Modifying the 'node' pointer is just asking for issues.
Yes that is error prone, but not due to the double loop. It's due to the
modifying of the node pointer that is used internally by the loop
counter. Don't do that :-)

>
> We have three options here:
>
> 1. Stuff everything into a single for(). While not too difficult, it will make
> the readability of the code difficult as it will force us to abandon using
> hlist_for_each_* macros.
>
> 2. Over-complicate everything, and check for 'node == NULL && obj &&
> obj->member.next == NULL' instead. That one will fail only if the user has
> specifically set the object as the last object in the list and the node as NULL.
>
> 3. Use 2 loops which might not work properly if the user does something odd,
> with a big fat warning above them.
>
>
> To sum it up, I'd rather go with 3 and let anyone who does things he shouldn't
> be doing break.

I agree, the double loop itself is not error prone. If you are modifying
'node' you had better know what the hell you are doing.

Actually, it may be something that is legitimate. That is, if you want
to skip to the next bucket, just set node to NULL and do the break (as
Josh had done). This would break if the macro loop changed later on, but
hey, like I said, it's error prone ;-) If you really want to do that,
then hand coding the double loop would be a better bet. IOW, don't use
the macro loop.

-- Steve

2012-09-04 22:58:54

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On 09/04/2012 11:41 PM, Steven Rostedt wrote:
> Ah, I missed the condition with the rec == &pg->records[pg->index]. But
> if ftrace_pages_start is NULL, the rec = &pg->records[pg->index] will
> fault.

Right.

>
> You could do something like rec = pg ? &pg->records[pg->index] : NULL,

Right.

> but IIRC, the comma operator does not guarantee order evaluation. That
> is, the compiler is allowed to process "a , b" as "b; a;" and not "a;
> b;".

Not true. The comma operator introduces a sequence point. It's the comma
that separates function parameters that doesn't guarantee ordering.

--
Pedro Alves

2012-09-04 15:35:51

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

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

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

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

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

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

-- Steve

2012-09-06 15:11:37

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On Thu, 2012-09-06 at 07:55 -0700, Josh Triplett wrote:

> > My solution to making 'break' work in the iterator is:
> >
> > for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
> > hlist_for_each_entry(obj, node, &name[bkt], member)
> >
>
> Looks reasonable. However, it would break (or rather, not break) on
> code like this:
>
> hash_for_each_entry(...) {
> if (...) {
> foo(node);
> node = NULL;
> break;
> }
> }
>
> Hiding the double loop still seems error-prone.

We've already had this conversation ;-) A guess a big comment is in
order:

/*
* NOTE! Although this is a double loop, 'break' still works because of
* the 'node == NULL' condition in the outer loop. On break of
* the inner loop, node will be !NULL, and the outer loop will
* exit as well.
*/

-- Steve

2012-09-06 14:20:38

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On 09/06/2012 02:53 PM, Sasha Levin wrote:

> So I think that for the hash iterator it might actually be simpler.
>
> My solution to making 'break' work in the iterator is:
>
> for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
> hlist_for_each_entry(obj, node, &name[bkt], member)
>
> We initialize our node loop cursor with NULL in the external loop, and the
> external loop will have a new condition to loop while that cursor is NULL.
>
> My logic is that we can only 'break' when we are iterating over an object in the
> internal loop. If we're iterating over an object in that loop then 'node != NULL'.
>
> This way, if we broke from within the internal loop, the external loop will see
> node as not NULL, and so it will stop looping itself. On the other hand, if the
> internal loop has actually ended, then node will be NULL, and the outer loop
> will keep running.
>
> Is there anything I've missed?

Looks right to me, from a cursory look at hlist_for_each_entry. That's exactly
what I meant with this most often being trivial when the inner loop's iterator
is a pointer that goes NULL at the end.

--
Pedro Alves

2012-09-06 17:02:39

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

* Sasha Levin ([email protected]) wrote:
> On 09/06/2012 06:50 PM, Mathieu Desnoyers wrote:
> > * Sasha Levin ([email protected]) wrote:
> >> On 09/06/2012 06:00 PM, Steven Rostedt wrote:
> >>>>> I think that that code doesn't make sense. The users of hlist_for_each_* aren't
> >>>>> supposed to be changing the loop cursor.
> >>> I totally agree. Modifying the 'node' pointer is just asking for issues.
> >>> Yes that is error prone, but not due to the double loop. It's due to the
> >>> modifying of the node pointer that is used internally by the loop
> >>> counter. Don't do that :-)
> >>
> >> While we're on this subject, I haven't actually seen hlist_for_each_entry() code
> >> that even *touches* 'pos'.
> >>
> >> Will people yell at me loudly if I change the prototype of those macros to be:
> >>
> >> hlist_for_each_entry(tpos, head, member)
> >>
> >> (Dropping the 'pos' parameter), and updating anything that calls those macros to
> >> drop it as well?
> >
> > I think the intent there is to keep hlist macros and list macros
> > slightly in sync. Given those are vastly used, I'm not sure you want to
> > touch them. But hey, that's just my 2 cents.
>
> Actually, the corresponding list macro looks like this:
>
> list_for_each_entry(pos, head, member)
>
> With 'pos' being the equivalent of 'tpos' in the hlist macros (the type *).
> Changing hlist macro will make them both look as follows:
>
> hlist_for_each_entry(pos, head, member)
> list_for_each_entry(pos, head, member)
>
> So following this suggesting will actually bring them back to sync...
>
> The only issue I can see is that as you've said, they're used almost everywhere,
> so doing something to change that will require some coordination.

if this brings hlist and list in sync, then it looks like an
improvement. It might be good to propose this change as a separate
patchset.

Thanks,

Mathieu

>
>
> Thanks,
> Sasha

--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

2012-09-04 22:41:53

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

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

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

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

-- Steve

2012-09-04 16:31:12

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On 09/04/2012 04:35 PM, Steven Rostedt wrote:
> On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:
>
>> Looking again at:
>>
>> +#define hash_for_each_size(name, bits, bkt, node, obj, member) \
>> + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++) \
>> + hlist_for_each_entry(obj, node, &name[bkt], member)
>>
>> you will notice that a "break" or "continue" in the inner loop will not
>> affect the outer loop, which is certainly not what the programmer would
>> expect!
>>
>> I advise strongly against creating such error-prone construct.
>>
>
> A few existing loop macros do this. But they require a do { } while ()
> approach, and all have a comment.
>
> It's used by do_each_thread() in sched.h and ftrace does this as well.
> Look at kernel/trace/ftrace.c at do_for_each_ftrace_rec().
>
> Yes it breaks 'break' but it does not break 'continue' as it would just
> go to the next item that would have been found (like a normal for
> would).

/*
* This is a double for. Do not use 'break' to break out of the loop,
* you must use a goto.
*/
#define do_for_each_ftrace_rec(pg, rec) \
for (pg = ftrace_pages_start; pg; pg = pg->next) { \
int _____i; \
for (_____i = 0; _____i < pg->index; _____i++) { \
rec = &pg->records[_____i];

You can make 'break' also work as expected if you can embed a little knowledge
of the inner loop's condition in the outer loop's condition. Sometimes it's
trivial, most often when the inner loop's iterator is a pointer that goes
NULL at the end, but other times not so much. Something like (completely untested):

#define do_for_each_ftrace_rec(pg, rec) \
for (pg = ftrace_pages_start, rec = &pg->records[pg->index]; \
pg && rec == &pg->records[pg->index]; \
pg = pg->next) { \
int _____i; \
for (_____i = 0; _____i < pg->index; _____i++) { \
rec = &pg->records[_____i];

(other variants possible)

IOW, the outer loop only iterates if the inner loop completes. If there's
a break in the inner loop, then the outer loop breaks too. Of course, it
all depends on whether the generated code looks sane or hideous, if
the uses of the macro care for it over bug avoidance.

--
Pedro Alves

2012-09-06 17:00:56

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On 09/06/2012 06:50 PM, Mathieu Desnoyers wrote:
> * Sasha Levin ([email protected]) wrote:
>> On 09/06/2012 06:00 PM, Steven Rostedt wrote:
>>>>> I think that that code doesn't make sense. The users of hlist_for_each_* aren't
>>>>> supposed to be changing the loop cursor.
>>> I totally agree. Modifying the 'node' pointer is just asking for issues.
>>> Yes that is error prone, but not due to the double loop. It's due to the
>>> modifying of the node pointer that is used internally by the loop
>>> counter. Don't do that :-)
>>
>> While we're on this subject, I haven't actually seen hlist_for_each_entry() code
>> that even *touches* 'pos'.
>>
>> Will people yell at me loudly if I change the prototype of those macros to be:
>>
>> hlist_for_each_entry(tpos, head, member)
>>
>> (Dropping the 'pos' parameter), and updating anything that calls those macros to
>> drop it as well?
>
> I think the intent there is to keep hlist macros and list macros
> slightly in sync. Given those are vastly used, I'm not sure you want to
> touch them. But hey, that's just my 2 cents.

Actually, the corresponding list macro looks like this:

list_for_each_entry(pos, head, member)

With 'pos' being the equivalent of 'tpos' in the hlist macros (the type *).
Changing hlist macro will make them both look as follows:

hlist_for_each_entry(pos, head, member)
list_for_each_entry(pos, head, member)

So following this suggesting will actually bring them back to sync...

The only issue I can see is that as you've said, they're used almost everywhere,
so doing something to change that will require some coordination.

Thanks,
Sasha

2012-09-04 16:32:23

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

* Steven Rostedt ([email protected]) wrote:
> On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:
>
> > Looking again at:
> >
> > +#define hash_for_each_size(name, bits, bkt, node, obj, member) \
> > + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++) \
> > + hlist_for_each_entry(obj, node, &name[bkt], member)
> >
> > you will notice that a "break" or "continue" in the inner loop will not
> > affect the outer loop, which is certainly not what the programmer would
> > expect!
> >
> > I advise strongly against creating such error-prone construct.
> >
>
> A few existing loop macros do this. But they require a do { } while ()
> approach, and all have a comment.
>
> It's used by do_each_thread() in sched.h

Yes. It's worth noting that it is a do_each_thread() /
while_each_thread() pair.

> and ftrace does this as well.
> Look at kernel/trace/ftrace.c at do_for_each_ftrace_rec().

Same here.

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

Good point.

So would changing hash_for_each_size() to a

do_each_hash_size()/while_each_hash_size() make it clearer that this
contains a double-loop ? (along with an appropriate comment about
break).

Thanks,

Mathieu

>
> -- Steve
>
>

--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

2012-09-06 13:53:35

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

On 09/04/2012 07:01 PM, Mathieu Desnoyers wrote:
>> #define do_for_each_ftrace_rec(pg, rec) \
>> > for (pg = ftrace_pages_start, rec = &pg->records[pg->index]; \
>> > pg && rec == &pg->records[pg->index]; \
>> > pg = pg->next) \
>> > for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
> Maybe in some cases there might be ways to combine the two loops into
> one ? I'm not seeing exactly how to do it for this one, but it should
> not be impossible. If the inner loop condition can be moved to the outer
> loop, and if we use (blah ? loop1_conf : loop2_cond) to test for
> different conditions depending on the context, and do the same for the
> 3rd argument of the for() loop. The details elude me for now though, so
> maybe it's complete non-sense ;)
>
> It might not be that useful for do_for_each_ftrace_rec, but if we can do
> it for the hash table iterator, it might be worth it.

So I think that for the hash iterator it might actually be simpler.

My solution to making 'break' work in the iterator is:

for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
hlist_for_each_entry(obj, node, &name[bkt], member)

We initialize our node loop cursor with NULL in the external loop, and the
external loop will have a new condition to loop while that cursor is NULL.

My logic is that we can only 'break' when we are iterating over an object in the
internal loop. If we're iterating over an object in that loop then 'node != NULL'.

This way, if we broke from within the internal loop, the external loop will see
node as not NULL, and so it will stop looping itself. On the other hand, if the
internal loop has actually ended, then node will be NULL, and the outer loop
will keep running.

Is there anything I've missed?

Thanks,
Sasha

2012-09-06 14:38:31

by David Laight

[permalink] [raw]

Subject: RE: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

> My solution to making 'break' work in the iterator is:
>
> for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node ==
NULL; bkt++)
> hlist_for_each_entry(obj, node, &name[bkt], member)

I'd take a look at the generated code.
Might come out a bit better if the condition is changed to:
node == NULL && bkt < HASH_SIZE(name)
you might find the compiler always optimises out the
node == NULL comparison.
(It might anyway, but switching the order gives it a better
chance.)

David

2012-09-04 17:17:11

[permalink] [raw]

Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

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

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

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

-- Steve

2012-09-04 17:21:50