From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx182.postini.com [74.125.245.182]) by kanga.kvack.org (Postfix) with SMTP id 555A56B0044 for ; Fri, 3 Aug 2012 10:23:12 -0400 (EDT) Received: by bkcjc3 with SMTP id jc3so397032bkc.14 for ; Fri, 03 Aug 2012 07:23:10 -0700 (PDT) From: Sasha Levin Subject: [RFC v2 0/7] generic hashtable implementation Date: Fri, 3 Aug 2012 16:23:01 +0200 Message-Id: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin There are quite a few places in the kernel which implement a hashtable in a very similar way. Instead of having implementations of a hashtable all over the kernel, we can re-use the code. This patch series introduces a very simple hashtable implementation, and modifies three (random) modules to use it. I've limited it to 3 only so that it would be easy to review and modify, and to show that even at this number we already eliminate a big amount of duplicated code. If this basic hashtable looks ok, future code will include: - RCU support - Self locking (list_bl?) - Converting more code to use the hashtable Changes in V2: - Address review comments by Tejun Heo, Josh Triplett and Eric Beiderman (Thanks all!). - Rebase on top of latest master. - Convert more places to use the hashtable. Hopefully it will trigger more reviews by touching more subsystems. Sasha Levin (7): hashtable: introduce a small and naive hashtable user_ns: use new hashtable implementation mm,ksm: use new hashtable implementation workqueue: use new hashtable implementation mm/huge_memory: use new hashtable implementation tracepoint: use new hashtable implementation net,9p: use new hashtable implementation include/linux/hashtable.h | 75 ++++++++++++++++++++++++++++++++++++ kernel/tracepoint.c | 26 ++++-------- kernel/user.c | 53 +++++++++----------------- kernel/workqueue.c | 93 +++++++-------------------------------------- mm/huge_memory.c | 56 +++++---------------------- mm/ksm.c | 29 ++++---------- net/9p/error.c | 17 ++++---- 7 files changed, 144 insertions(+), 205 deletions(-) create mode 100644 include/linux/hashtable.h -- 1.7.8.6 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx184.postini.com [74.125.245.184]) by kanga.kvack.org (Postfix) with SMTP id 9AEE36B005A for ; Fri, 3 Aug 2012 10:23:14 -0400 (EDT) Received: by bkcjc3 with SMTP id jc3so397078bkc.14 for ; Fri, 03 Aug 2012 07:23:12 -0700 (PDT) From: Sasha Levin Subject: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Date: Fri, 3 Aug 2012 16:23:02 +0200 Message-Id: <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> In-Reply-To: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin This hashtable implementation is using hlist buckets to provide a simple hashtable to prevent it from getting reimplemented all over the kernel. Signed-off-by: Sasha Levin --- include/linux/hashtable.h | 75 +++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 75 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..b004cf7 --- /dev/null +++ b/include/linux/hashtable.h @@ -0,0 +1,75 @@ +#ifndef _LINUX_HASHTABLE_H +#define _LINUX_HASHTABLE_H + +#include +#include +#include +#include + +struct hash_table { + size_t bits; + struct hlist_head buckets[]; +}; + +#define DEFINE_STATIC_HASHTABLE(n, b) \ + static struct hash_table n = { .bits = (b), \ + .buckets = { [0 ... ((1 << (b)) - 1)] = HLIST_HEAD_INIT } } + +#define DEFINE_HASHTABLE(n, b) \ + union { \ + struct hash_table n; \ + struct { \ + size_t bits; \ + struct hlist_head buckets[1 << (b)]; \ + } __##n ; \ + }; + +#define HASH_BITS(name) ((name)->bits) +#define HASH_SIZE(name) (1 << (HASH_BITS(name))) + +__attribute__ ((unused)) +static void hash_init(struct hash_table *ht, size_t bits) +{ + size_t i; + + ht->bits = bits; + for (i = 0; i < (1 << bits); i++) + INIT_HLIST_HEAD(&ht->buckets[i]); +} + +static void hash_add(struct hash_table *ht, struct hlist_node *node, long key) +{ + hlist_add_head(node, + &ht->buckets[hash_long((unsigned long)key, HASH_BITS(ht))]); +} + + +#define hash_get(name, key, type, member, cmp_fn) \ +({ \ + struct hlist_node *__node; \ + typeof(key) __key = key; \ + type *__obj = NULL; \ + hlist_for_each_entry(__obj, __node, &(name)->buckets[ \ + hash_long((unsigned long) __key, \ + HASH_BITS(name))], member) \ + if (cmp_fn(__obj, __key)) \ + break; \ + __obj; \ +}) + +__attribute__ ((unused)) +static void hash_del(struct hlist_node *node) +{ + hlist_del_init(node); +} + +#define hash_for_each(bkt, node, name, obj, member) \ + for (bkt = 0; bkt < HASH_SIZE(name); bkt++) \ + hlist_for_each_entry(obj, node, &(name)->buckets[i], member) + +#define hash_for_each_possible(name, node, obj, member, key) \ + hlist_for_each_entry(obj, node, \ + &(name)->buckets[hash_long((unsigned long) key, \ + HASH_BITS(name))], member) + +#endif -- 1.7.8.6 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx182.postini.com [74.125.245.182]) by kanga.kvack.org (Postfix) with SMTP id B0F6D6B005A for ; Fri, 3 Aug 2012 10:23:15 -0400 (EDT) Received: by mail-bk0-f41.google.com with SMTP id jc3so397032bkc.14 for ; Fri, 03 Aug 2012 07:23:15 -0700 (PDT) From: Sasha Levin Subject: [RFC v2 2/7] user_ns: use new hashtable implementation Date: Fri, 3 Aug 2012 16:23:03 +0200 Message-Id: <1344003788-1417-3-git-send-email-levinsasha928@gmail.com> In-Reply-To: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin Switch user_ns to use the new hashtable implementation. This reduces the amount of generic unrelated code in user_ns. Signed-off-by: Sasha Levin --- kernel/user.c | 53 ++++++++++++++++++----------------------------------- 1 files changed, 18 insertions(+), 35 deletions(-) diff --git a/kernel/user.c b/kernel/user.c index b815fef..555c71a 100644 --- a/kernel/user.c +++ b/kernel/user.c @@ -16,6 +16,7 @@ #include #include #include +#include /* * userns count is 1 for root user, 1 for init_uts_ns, @@ -50,15 +51,14 @@ EXPORT_SYMBOL_GPL(init_user_ns); * UID task count cache, to get fast user lookup in "alloc_uid" * when changing user ID's (ie setuid() and friends). */ - -#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)))) +#define UIDHASH_BITS (CONFIG_BASE_SMALL ? 3 : 7) +#define UIDHASH_CMP(obj, key) ((obj)->uid == (key)) +#define uidhash_entry(key) (hash_get(&uidhash_table, key, \ + struct user_struct, uidhash_node, \ + UIDHASH_CMP)) static struct kmem_cache *uid_cachep; -struct hlist_head uidhash_table[UIDHASH_SZ]; +DEFINE_STATIC_HASHTABLE(uidhash_table, UIDHASH_BITS); /* * The uidhash_lock is mostly taken from process context, but it is @@ -84,29 +84,14 @@ 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, up->uid); } static void uid_hash_remove(struct user_struct *up) { - hlist_del_init(&up->uidhash_node); -} - -static struct user_struct *uid_hash_find(kuid_t uid, struct hlist_head *hashent) -{ - struct user_struct *user; - struct hlist_node *h; - - hlist_for_each_entry(user, h, hashent, uidhash_node) { - if (uid_eq(user->uid, uid)) { - atomic_inc(&user->__count); - return user; - } - } - - return NULL; + hash_del(&up->uidhash_node); } /* IRQs are disabled and uidhash_lock is held upon function entry. @@ -135,7 +120,9 @@ 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 = uidhash_entry(uid); + if (ret) + atomic_inc(&ret->__count); spin_unlock_irqrestore(&uidhash_lock, flags); return ret; } @@ -156,11 +143,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 = uidhash_entry(uid); spin_unlock_irq(&uidhash_lock); if (!up) { @@ -176,13 +162,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 = uidhash_entry(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 +182,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, UIDHASH_BITS); /* 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 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx184.postini.com [74.125.245.184]) by kanga.kvack.org (Postfix) with SMTP id B14066B0068 for ; Fri, 3 Aug 2012 10:23:17 -0400 (EDT) Received: by mail-bk0-f41.google.com with SMTP id jc3so397078bkc.14 for ; Fri, 03 Aug 2012 07:23:17 -0700 (PDT) From: Sasha Levin Subject: [RFC v2 3/7] mm,ksm: use new hashtable implementation Date: Fri, 3 Aug 2012 16:23:04 +0200 Message-Id: <1344003788-1417-4-git-send-email-levinsasha928@gmail.com> In-Reply-To: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin Switch ksm to use the new hashtable implementation. This reduces the amount of generic unrelated code in the ksm module. Signed-off-by: Sasha Levin --- mm/ksm.c | 29 +++++++++-------------------- 1 files changed, 9 insertions(+), 20 deletions(-) diff --git a/mm/ksm.c b/mm/ksm.c index 47c8853..72d062a 100644 --- a/mm/ksm.c +++ b/mm/ksm.c @@ -33,7 +33,7 @@ #include #include #include -#include +#include #include #include @@ -157,8 +157,8 @@ static struct rb_root root_stable_tree = RB_ROOT; static struct rb_root root_unstable_tree = RB_ROOT; #define MM_SLOTS_HASH_SHIFT 10 -#define MM_SLOTS_HASH_HEADS (1 << MM_SLOTS_HASH_SHIFT) -static struct hlist_head mm_slots_hash[MM_SLOTS_HASH_HEADS]; +#define mm_hash_cmp(slot, key) ((slot)->mm == (key)) +DEFINE_STATIC_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_SHIFT); static struct mm_slot ksm_mm_head = { .mm_list = LIST_HEAD_INIT(ksm_mm_head.mm_list), @@ -275,26 +275,15 @@ static inline void free_mm_slot(struct mm_slot *mm_slot) static struct mm_slot *get_mm_slot(struct mm_struct *mm) { - struct mm_slot *mm_slot; - struct hlist_head *bucket; - struct hlist_node *node; - - bucket = &mm_slots_hash[hash_ptr(mm, MM_SLOTS_HASH_SHIFT)]; - hlist_for_each_entry(mm_slot, node, bucket, link) { - if (mm == mm_slot->mm) - return mm_slot; - } - return NULL; + return hash_get(&mm_slots_hash, mm, struct mm_slot, + link, mm_hash_cmp); } static void insert_to_mm_slots_hash(struct mm_struct *mm, struct mm_slot *mm_slot) { - struct hlist_head *bucket; - - bucket = &mm_slots_hash[hash_ptr(mm, MM_SLOTS_HASH_SHIFT)]; mm_slot->mm = mm; - hlist_add_head(&mm_slot->link, bucket); + hash_add(&mm_slots_hash, &mm_slot->link, (long)mm); } static inline int in_stable_tree(struct rmap_item *rmap_item) @@ -647,7 +636,7 @@ static int unmerge_and_remove_all_rmap_items(void) ksm_scan.mm_slot = list_entry(mm_slot->mm_list.next, struct mm_slot, mm_list); if (ksm_test_exit(mm)) { - hlist_del(&mm_slot->link); + hash_del(&mm_slot->link); list_del(&mm_slot->mm_list); spin_unlock(&ksm_mmlist_lock); @@ -1385,7 +1374,7 @@ next_mm: * or when all VM_MERGEABLE areas have been unmapped (and * mmap_sem then protects against race with MADV_MERGEABLE). */ - hlist_del(&slot->link); + hash_del(&slot->link); list_del(&slot->mm_list); spin_unlock(&ksm_mmlist_lock); @@ -1548,7 +1537,7 @@ void __ksm_exit(struct mm_struct *mm) mm_slot = get_mm_slot(mm); if (mm_slot && ksm_scan.mm_slot != mm_slot) { if (!mm_slot->rmap_list) { - hlist_del(&mm_slot->link); + hash_del(&mm_slot->link); list_del(&mm_slot->mm_list); easy_to_free = 1; } else { -- 1.7.8.6 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx182.postini.com [74.125.245.182]) by kanga.kvack.org (Postfix) with SMTP id 21BB96B0069 for ; Fri, 3 Aug 2012 10:23:19 -0400 (EDT) Received: by mail-bk0-f41.google.com with SMTP id jc3so397032bkc.14 for ; Fri, 03 Aug 2012 07:23:19 -0700 (PDT) From: Sasha Levin Subject: [RFC v2 4/7] workqueue: use new hashtable implementation Date: Fri, 3 Aug 2012 16:23:05 +0200 Message-Id: <1344003788-1417-5-git-send-email-levinsasha928@gmail.com> In-Reply-To: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin Switch workqueues to use the new hashtable implementation. This reduces the amount of generic unrelated code in the workqueues. Signed-off-by: Sasha Levin --- kernel/workqueue.c | 93 ++++++++-------------------------------------------- 1 files changed, 14 insertions(+), 79 deletions(-) diff --git a/kernel/workqueue.c b/kernel/workqueue.c index 692d976..480975d 100644 --- a/kernel/workqueue.c +++ b/kernel/workqueue.c @@ -41,6 +41,7 @@ #include #include #include +#include #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 */ @@ -102,6 +101,8 @@ enum { HIGHPRI_NICE_LEVEL = -20, }; +#define worker_hash_cmp(obj, key) ((obj)->current_work == (key)) + /* * Structure fields follow one of the following exclusion rules. * @@ -180,7 +181,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 */ @@ -287,10 +288,6 @@ EXPORT_SYMBOL_GPL(system_nrt_freezable_wq); for ((pool) = &(gcwq)->pools[0]; \ (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) - static inline int __next_gcwq_cpu(int cpu, const struct cpumask *mask, unsigned int sw) { @@ -822,70 +819,11 @@ 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 * - * Find a worker which is executing @work on @gcwq. This function is - * identical to __find_worker_executing_work() except that this - * function calculates @bwh itself. + * Find a worker which is executing @work on @gcwq. * * CONTEXT: * spin_lock_irq(gcwq->lock). @@ -897,8 +835,8 @@ static struct worker *__find_worker_executing_work(struct global_cwq *gcwq, static struct worker *find_worker_executing_work(struct global_cwq *gcwq, struct work_struct *work) { - return __find_worker_executing_work(gcwq, busy_worker_head(gcwq, work), - work); + return hash_get(&gcwq->busy_hash, work, struct worker, + hentry, worker_hash_cmp); } /** @@ -959,7 +897,7 @@ static bool is_chained_work(struct workqueue_struct *wq) int i; spin_lock_irqsave(&gcwq->lock, flags); - for_each_busy_worker(worker, i, pos, gcwq) { + hash_for_each(i, pos, &gcwq->busy_hash, worker, hentry) { if (worker->task != current) continue; spin_unlock_irqrestore(&gcwq->lock, flags); @@ -1432,7 +1370,7 @@ retry: wake_up_all(&gcwq->rebind_hold); /* rebind busy workers */ - for_each_busy_worker(worker, i, pos, gcwq) { + hash_for_each(i, pos, &gcwq->busy_hash, worker, hentry) { struct work_struct *rebind_work = &worker->rebind_work; /* morph UNBOUND to REBIND */ @@ -1932,7 +1870,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; @@ -1964,7 +1901,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; @@ -1972,7 +1909,7 @@ __acquires(&gcwq->lock) /* claim and process */ debug_work_deactivate(work); - hlist_add_head(&worker->hentry, bwh); + hash_add(&gcwq->busy_hash, &worker->hentry, (long)work); worker->current_work = work; worker->current_cwq = cwq; work_color = get_work_color(work); @@ -2027,7 +1964,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); @@ -3405,7 +3342,7 @@ static void gcwq_unbind_fn(struct work_struct *work) list_for_each_entry(worker, &pool->idle_list, entry) worker->flags |= WORKER_UNBOUND; - for_each_busy_worker(worker, i, pos, gcwq) + hash_for_each(i, pos, &gcwq->busy_hash, worker, hentry) worker->flags |= WORKER_UNBOUND; gcwq->flags |= GCWQ_DISASSOCIATED; @@ -3690,7 +3627,6 @@ out_unlock: static int __init init_workqueues(void) { unsigned int cpu; - int i; cpu_notifier(workqueue_cpu_up_callback, CPU_PRI_WORKQUEUE_UP); cpu_notifier(workqueue_cpu_down_callback, CPU_PRI_WORKQUEUE_DOWN); @@ -3704,8 +3640,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, BUSY_WORKER_HASH_ORDER); for_each_worker_pool(pool, gcwq) { pool->gcwq = gcwq; -- 1.7.8.6 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx184.postini.com [74.125.245.184]) by kanga.kvack.org (Postfix) with SMTP id 7824B6B006E for ; Fri, 3 Aug 2012 10:23:22 -0400 (EDT) Received: by mail-bk0-f41.google.com with SMTP id jc3so397078bkc.14 for ; Fri, 03 Aug 2012 07:23:21 -0700 (PDT) From: Sasha Levin Subject: [RFC v2 5/7] mm/huge_memory: use new hashtable implementation Date: Fri, 3 Aug 2012 16:23:06 +0200 Message-Id: <1344003788-1417-6-git-send-email-levinsasha928@gmail.com> In-Reply-To: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin 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 --- mm/huge_memory.c | 56 ++++++++++------------------------------------------- 1 files changed, 11 insertions(+), 45 deletions(-) diff --git a/mm/huge_memory.c b/mm/huge_memory.c index 57c4b93..7b2cad5 100644 --- a/mm/huge_memory.c +++ b/mm/huge_memory.c @@ -17,6 +17,7 @@ #include #include #include +#include #include #include #include "internal.h" @@ -57,12 +58,13 @@ 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 +#define MM_SLOTS_HASH_CMP(mm_slot, obj) ((mm_slot)->mm == (obj)) +DEFINE_STATIC_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_BITS); + static struct kmem_cache *mm_slot_cache __read_mostly; /** @@ -140,7 +142,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 +556,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 @@ -1562,47 +1558,17 @@ 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 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; - } - return NULL; + return hash_get(&mm_slots_hash, mm, struct mm_slot, + hash, MM_SLOTS_HASH_CMP); } static void insert_to_mm_slots_hash(struct mm_struct *mm, struct mm_slot *mm_slot) { - struct hlist_head *bucket; - - bucket = &mm_slots_hash[((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) @@ -1675,7 +1641,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; } @@ -2089,7 +2055,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 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx182.postini.com [74.125.245.182]) by kanga.kvack.org (Postfix) with SMTP id 47E9E6B0069 for ; Fri, 3 Aug 2012 10:23:24 -0400 (EDT) Received: by mail-bk0-f41.google.com with SMTP id jc3so397032bkc.14 for ; Fri, 03 Aug 2012 07:23:23 -0700 (PDT) From: Sasha Levin Subject: [RFC v2 6/7] tracepoint: use new hashtable implementation Date: Fri, 3 Aug 2012 16:23:07 +0200 Message-Id: <1344003788-1417-7-git-send-email-levinsasha928@gmail.com> In-Reply-To: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin Switch tracepoints to use the new hashtable implementation. This reduces the amount of generic unrelated code in the tracepoints. Signed-off-by: Sasha Levin --- kernel/tracepoint.c | 26 +++++++++----------------- 1 files changed, 9 insertions(+), 17 deletions(-) diff --git a/kernel/tracepoint.c b/kernel/tracepoint.c index d96ba22..b5a2650 100644 --- a/kernel/tracepoint.c +++ b/kernel/tracepoint.c @@ -26,6 +26,7 @@ #include #include #include +#include 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]; +DEFINE_STATIC_HASHTABLE(tracepoint_table, TRACEPOINT_HASH_BITS); /* * Note about RCU : @@ -191,16 +191,14 @@ 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, node, e, hlist, hash) if (!strcmp(name, e->name)) return e; - } + return NULL; } @@ -210,19 +208,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 +226,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 +236,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); } -- 1.7.8.6 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx184.postini.com [74.125.245.184]) by kanga.kvack.org (Postfix) with SMTP id 783BC6B0071 for ; Fri, 3 Aug 2012 10:23:27 -0400 (EDT) Received: by mail-bk0-f41.google.com with SMTP id jc3so397078bkc.14 for ; Fri, 03 Aug 2012 07:23:26 -0700 (PDT) From: Sasha Levin Subject: [RFC v2 7/7] net,9p: use new hashtable implementation Date: Fri, 3 Aug 2012 16:23:08 +0200 Message-Id: <1344003788-1417-8-git-send-email-levinsasha928@gmail.com> In-Reply-To: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin 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 --- net/9p/error.c | 17 ++++++++--------- 1 files changed, 8 insertions(+), 9 deletions(-) diff --git a/net/9p/error.c b/net/9p/error.c index 2ab2de7..f1037db 100644 --- a/net/9p/error.c +++ b/net/9p/error.c @@ -34,7 +34,7 @@ #include #include #include - +#include /** * 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 ERRHASHSZ 5 +DEFINE_STATIC_HASHTABLE(hash_errmap, ERRHASHSZ); /* FixMe - reduce to a reasonable size */ static struct errormap errmap[] = { @@ -196,15 +196,14 @@ int p9_error_init(void) int bucket; /* initialize hash table */ - for (bucket = 0; bucket < ERRHASHSZ; bucket++) - INIT_HLIST_HEAD(&hash_errmap[bucket]); + hash_init(&hash_errmap, ERRHASHSZ); /* 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; + bucket = 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, bucket); } return 1; @@ -228,8 +227,8 @@ int p9_errstr2errno(char *errstr, int len) errno = 0; p = NULL; c = NULL; - bucket = jhash(errstr, len, 0) % ERRHASHSZ; - hlist_for_each_entry(c, p, &hash_errmap[bucket], list) { + bucket = jhash(errstr, len, 0); + hash_for_each_possible(&hash_errmap, p, c, list, bucket) { if (c->namelen == len && !memcmp(c->name, errstr, len)) { errno = c->val; break; -- 1.7.8.6 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx129.postini.com [74.125.245.129]) by kanga.kvack.org (Postfix) with SMTP id 2805D6B0044 for ; Fri, 3 Aug 2012 13:15:21 -0400 (EDT) Received: by yhr47 with SMTP id 47so1324796yhr.14 for ; Fri, 03 Aug 2012 10:15:20 -0700 (PDT) Date: Fri, 3 Aug 2012 10:15:15 -0700 From: Tejun Heo Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120803171515.GH15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: Sasha Levin Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Hello, Sasha. On Fri, Aug 03, 2012 at 04:23:02PM +0200, Sasha Levin wrote: > +#define DEFINE_STATIC_HASHTABLE(n, b) \ > + static struct hash_table n = { .bits = (b), \ > + .buckets = { [0 ... ((1 << (b)) - 1)] = HLIST_HEAD_INIT } } What does this "static" mean? > +#define DEFINE_HASHTABLE(n, b) \ > + union { \ > + struct hash_table n; \ > + struct { \ > + size_t bits; \ > + struct hlist_head buckets[1 << (b)]; \ > + } __##n ; \ > + }; Is this supposed to be embedded in struct definition? If so, the name is rather misleading as DEFINE_* is supposed to define and initialize stand-alone constructs. Also, for struct members, simply putting hash entries after struct hash_table should work. Wouldn't using DEFINE_HASHTABLE() for the first macro and DEFINE_HASHTABLE_MEMBER() for the latter be better? > +#define HASH_BITS(name) ((name)->bits) > +#define HASH_SIZE(name) (1 << (HASH_BITS(name))) > + > +__attribute__ ((unused)) Are we using __attribute__((unused)) for functions defined in headers instead of static inline now? If so, why? > +static void hash_init(struct hash_table *ht, size_t bits) > +{ > + size_t i; I would prefer int here but no biggie. > + ht->bits = bits; > + for (i = 0; i < (1 << bits); i++) > + INIT_HLIST_HEAD(&ht->buckets[i]); > +} > + > +static void hash_add(struct hash_table *ht, struct hlist_node *node, long key) > +{ > + hlist_add_head(node, > + &ht->buckets[hash_long((unsigned long)key, HASH_BITS(ht))]); > +} > + > + > +#define hash_get(name, key, type, member, cmp_fn) \ > +({ \ > + struct hlist_node *__node; \ > + typeof(key) __key = key; \ > + type *__obj = NULL; \ > + hlist_for_each_entry(__obj, __node, &(name)->buckets[ \ > + hash_long((unsigned long) __key, \ > + HASH_BITS(name))], member) \ > + if (cmp_fn(__obj, __key)) \ > + break; \ > + __obj; \ > +}) As opposed to using hash_for_each_possible(), how much difference does this make? Is it really worthwhile? Thanks. -- tejun -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx115.postini.com [74.125.245.115]) by kanga.kvack.org (Postfix) with SMTP id 5DB626B0044 for ; Fri, 3 Aug 2012 13:16:41 -0400 (EDT) Received: by yhr47 with SMTP id 47so1326601yhr.14 for ; Fri, 03 Aug 2012 10:16:40 -0700 (PDT) Date: Fri, 3 Aug 2012 10:16:35 -0700 From: Tejun Heo Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120803171635.GI15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20120803171515.GH15477@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: Sasha Levin Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Ooh, one more thing. Comments please. -- tejun -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx195.postini.com [74.125.245.195]) by kanga.kvack.org (Postfix) with SMTP id EA73D6B0044 for ; Fri, 3 Aug 2012 13:39:16 -0400 (EDT) Received: by bkcjc3 with SMTP id jc3so507273bkc.14 for ; Fri, 03 Aug 2012 10:39:15 -0700 (PDT) Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable From: Eric Dumazet In-Reply-To: <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> Content-Type: text/plain; charset="UTF-8" Date: Fri, 03 Aug 2012 19:39:10 +0200 Message-ID: <1344015550.9299.1387.camel@edumazet-glaptop> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Sasha Levin Cc: torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org On Fri, 2012-08-03 at 16:23 +0200, Sasha Levin wrote: > This hashtable implementation is using hlist buckets to provide a simple > hashtable to prevent it from getting reimplemented all over the kernel. > > +static void hash_add(struct hash_table *ht, struct hlist_node *node, long key) > +{ > + hlist_add_head(node, > + &ht->buckets[hash_long((unsigned long)key, HASH_BITS(ht))]); > +} > + Why key is a long, casted later to "unsigned long" ? hash_long() is expensive on 64bit arches, and not really needed if key is an u32 from the beginning ( I am referring to your patches 6 & 7 using jhash() ) Maybe you could use a macro, so that we can automatically select hash_32() if key is an u32, and hash_long() for other types. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx107.postini.com [74.125.245.107]) by kanga.kvack.org (Postfix) with SMTP id 060056B0044 for ; Fri, 3 Aug 2012 14:00:57 -0400 (EDT) Received: by bkcjc3 with SMTP id jc3so514485bkc.14 for ; Fri, 03 Aug 2012 11:00:56 -0700 (PDT) Subject: Re: [RFC v2 7/7] net,9p: use new hashtable implementation From: Eric Dumazet In-Reply-To: <1344003788-1417-8-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-8-git-send-email-levinsasha928@gmail.com> Content-Type: text/plain; charset="UTF-8" Date: Fri, 03 Aug 2012 20:00:51 +0200 Message-ID: <1344016851.9299.1415.camel@edumazet-glaptop> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Sasha Levin Cc: torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org On Fri, 2012-08-03 at 16:23 +0200, Sasha Levin wrote: > 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 > --- > net/9p/error.c | 17 ++++++++--------- > 1 files changed, 8 insertions(+), 9 deletions(-) > > diff --git a/net/9p/error.c b/net/9p/error.c > index 2ab2de7..f1037db 100644 > --- a/net/9p/error.c > +++ b/net/9p/error.c > @@ -34,7 +34,7 @@ > #include > #include > #include > - > +#include > /** > * 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 ERRHASHSZ 5 This name is confusing, it should mention SHIFT or BITS maybe... > +DEFINE_STATIC_HASHTABLE(hash_errmap, ERRHASHSZ); > > /* FixMe - reduce to a reasonable size */ > static struct errormap errmap[] = { > @@ -196,15 +196,14 @@ int p9_error_init(void) > int bucket; remove "int bucket" and use : u32 hash; > > /* initialize hash table */ > - for (bucket = 0; bucket < ERRHASHSZ; bucket++) > - INIT_HLIST_HEAD(&hash_errmap[bucket]); > + hash_init(&hash_errmap, ERRHASHSZ); Why is hash_init() even needed ? If hash is "DEFINE_STATIC_HASHTABLE(...)", its already ready for use ! > > /* 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; > + bucket = jhash(c->name, c->namelen, 0); bucket is a wrong name here, its more like "key" or "hash" > INIT_HLIST_NODE(&c->list); > - hlist_add_head(&c->list, &hash_errmap[bucket]); > + hash_add(&hash_errmap, &c->list, bucket); > } > > return 1; > @@ -228,8 +227,8 @@ int p9_errstr2errno(char *errstr, int len) > errno = 0; > p = NULL; > c = NULL; > - bucket = jhash(errstr, len, 0) % ERRHASHSZ; > - hlist_for_each_entry(c, p, &hash_errmap[bucket], list) { > + bucket = jhash(errstr, len, 0); hash = jhash(errstr, len, 0); > + hash_for_each_possible(&hash_errmap, p, c, list, bucket) { > if (c->namelen == len && !memcmp(c->name, errstr, len)) { > errno = c->val; > break; -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx134.postini.com [74.125.245.134]) by kanga.kvack.org (Postfix) with SMTP id 2CC0A6B0062 for ; Fri, 3 Aug 2012 17:13:54 -0400 (EDT) Received: by wgbdq12 with SMTP id dq12so941566wgb.26 for ; Fri, 03 Aug 2012 14:13:52 -0700 (PDT) Message-ID: <501C3F2B.7080004@gmail.com> Date: Fri, 03 Aug 2012 23:14:19 +0200 From: Sasha Levin MIME-Version: 1.0 Subject: Re: [RFC v2 7/7] net,9p: use new hashtable implementation References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-8-git-send-email-levinsasha928@gmail.com> <1344016851.9299.1415.camel@edumazet-glaptop> In-Reply-To: <1344016851.9299.1415.camel@edumazet-glaptop> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Eric Dumazet Cc: torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org On 08/03/2012 08:00 PM, Eric Dumazet wrote: > On Fri, 2012-08-03 at 16:23 +0200, Sasha Levin wrote: >> /* initialize hash table */ >> - for (bucket = 0; bucket < ERRHASHSZ; bucket++) >> - INIT_HLIST_HEAD(&hash_errmap[bucket]); >> + hash_init(&hash_errmap, ERRHASHSZ); > > Why is hash_init() even needed ? > > If hash is "DEFINE_STATIC_HASHTABLE(...)", its already ready for use ! Indeed it is. I've removed it, and then decided to put it back since the definition of the hashtable isn't fully cooked yet, and I didn't want to miss this initialization point if it turn out we need to initialize that hashtable afterall. I will remove it once the hashtable definitions are clear. The rest of the review comments will be addressed. Thanks! -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx128.postini.com [74.125.245.128]) by kanga.kvack.org (Postfix) with SMTP id 192F96B0062 for ; Fri, 3 Aug 2012 17:19:32 -0400 (EDT) Received: by wibhq4 with SMTP id hq4so850886wib.8 for ; Fri, 03 Aug 2012 14:19:30 -0700 (PDT) Message-ID: <501C407D.9080900@gmail.com> Date: Fri, 03 Aug 2012 23:19:57 +0200 From: Sasha Levin MIME-Version: 1.0 Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> In-Reply-To: <20120803171515.GH15477@google.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Tejun Heo Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org On 08/03/2012 07:15 PM, Tejun Heo wrote: > Hello, Sasha. > > On Fri, Aug 03, 2012 at 04:23:02PM +0200, Sasha Levin wrote: >> +#define DEFINE_STATIC_HASHTABLE(n, b) \ >> + static struct hash_table n = { .bits = (b), \ >> + .buckets = { [0 ... ((1 << (b)) - 1)] = HLIST_HEAD_INIT } } > > What does this "static" mean? > >> +#define DEFINE_HASHTABLE(n, b) \ >> + union { \ >> + struct hash_table n; \ >> + struct { \ >> + size_t bits; \ >> + struct hlist_head buckets[1 << (b)]; \ >> + } __##n ; \ >> + }; > > Is this supposed to be embedded in struct definition? If so, the name > is rather misleading as DEFINE_* is supposed to define and initialize > stand-alone constructs. Also, for struct members, simply putting hash > entries after struct hash_table should work. It would work, but I didn't want to just put them in the union since I feel it's safer to keep them in a separate struct so they won't be used by mistake, > Wouldn't using DEFINE_HASHTABLE() for the first macro and > DEFINE_HASHTABLE_MEMBER() for the latter be better? Indeed that sounds better, will fix. >> +#define HASH_BITS(name) ((name)->bits) >> +#define HASH_SIZE(name) (1 << (HASH_BITS(name))) >> + >> +__attribute__ ((unused)) > > Are we using __attribute__((unused)) for functions defined in headers > instead of static inline now? If so, why? > >> +static void hash_init(struct hash_table *ht, size_t bits) >> +{ >> + size_t i; > > I would prefer int here but no biggie. Just wondering, is there a particular reason behind it? >> + ht->bits = bits; >> + for (i = 0; i < (1 << bits); i++) >> + INIT_HLIST_HEAD(&ht->buckets[i]); >> +} >> + >> +static void hash_add(struct hash_table *ht, struct hlist_node *node, long key) >> +{ >> + hlist_add_head(node, >> + &ht->buckets[hash_long((unsigned long)key, HASH_BITS(ht))]); >> +} >> + >> + >> +#define hash_get(name, key, type, member, cmp_fn) \ >> +({ \ >> + struct hlist_node *__node; \ >> + typeof(key) __key = key; \ >> + type *__obj = NULL; \ >> + hlist_for_each_entry(__obj, __node, &(name)->buckets[ \ >> + hash_long((unsigned long) __key, \ >> + HASH_BITS(name))], member) \ >> + if (cmp_fn(__obj, __key)) \ >> + break; \ >> + __obj; \ >> +}) > > As opposed to using hash_for_each_possible(), how much difference does > this make? Is it really worthwhile? Most of the places I've switched to using this hashtable so far (4 out of 6) are using hash_get(). I think that the code looks cleaner when you an just provide a comparison function instead of implementing the iteration itself. I think hash_for_for_each_possible() is useful if the comparison condition is more complex than a simple comparison of one of the object members with the key - there's no need to force it on all the users. > > Thanks. > -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx108.postini.com [74.125.245.108]) by kanga.kvack.org (Postfix) with SMTP id A9AA96B0044 for ; Fri, 3 Aug 2012 17:30:22 -0400 (EDT) Received: by pbbrp2 with SMTP id rp2so2212366pbb.14 for ; Fri, 03 Aug 2012 14:30:22 -0700 (PDT) Date: Fri, 3 Aug 2012 14:30:17 -0700 From: Tejun Heo Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120803213017.GK15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <501C407D.9080900@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: Sasha Levin Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Hello, On Fri, Aug 03, 2012 at 11:19:57PM +0200, Sasha Levin wrote: > > Is this supposed to be embedded in struct definition? If so, the name > > is rather misleading as DEFINE_* is supposed to define and initialize > > stand-alone constructs. Also, for struct members, simply putting hash > > entries after struct hash_table should work. > > It would work, but I didn't want to just put them in the union since > I feel it's safer to keep them in a separate struct so they won't be > used by mistake, Just use ugly enough pre/postfixes. If the user still accesses that, it's the user's fault. > >> +static void hash_init(struct hash_table *ht, size_t bits) > >> +{ > >> + size_t i; > > > > I would prefer int here but no biggie. > > Just wondering, is there a particular reason behind it? It isn't a size and using unsigned when signed suffices seems to cause more headache than helps anything usually due to lack of values to use for exceptional conditions (usually -errno or -1). > > As opposed to using hash_for_each_possible(), how much difference does > > this make? Is it really worthwhile? > > Most of the places I've switched to using this hashtable so far (4 > out of 6) are using hash_get(). I think that the code looks cleaner > when you an just provide a comparison function instead of > implementing the iteration itself. > > I think hash_for_for_each_possible() is useful if the comparison > condition is more complex than a simple comparison of one of the > object members with the key - there's no need to force it on all the > users. I don't know. What's the difference? In terms of LOC, it might even not save any thanks to the extra function definition, right? I don't think it's saving enough complexity to justify a separate rather unusual interface. Thanks. -- tejun -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx115.postini.com [74.125.245.115]) by kanga.kvack.org (Postfix) with SMTP id 260786B0044 for ; Fri, 3 Aug 2012 17:36:23 -0400 (EDT) Received: by weys10 with SMTP id s10so921572wey.14 for ; Fri, 03 Aug 2012 14:36:21 -0700 (PDT) Message-ID: <501C4471.4090706@gmail.com> Date: Fri, 03 Aug 2012 23:36:49 +0200 From: Sasha Levin MIME-Version: 1.0 Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> In-Reply-To: <20120803213017.GK15477@google.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Tejun Heo Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org On 08/03/2012 11:30 PM, Tejun Heo wrote: >> I think hash_for_for_each_possible() is useful if the comparison >> > condition is more complex than a simple comparison of one of the >> > object members with the key - there's no need to force it on all the >> > users. > I don't know. What's the difference? In terms of LOC, it might even > not save any thanks to the extra function definition, right? I don't > think it's saving enough complexity to justify a separate rather > unusual interface. The function definition itself is just a macro, for example: #define MM_SLOTS_HASH_CMP(mm_slot, obj) ((mm_slot)->mm == (obj)) As an alternative, what do you think about simplifying that to be just a 'cond' instead of a function? Something like: hash_get(&mm_slots_hash, mm, struct mm_slot, hash, mm); In that case, the last param ("mm") will get unrolled to a condition like this: if ((obj)->mm == key) Which will be simple and easy for the user. The only reason I want to keep this interface is that most cases I've stumbled so far were easy short comparisons of a struct member with the key, and I don't want to make them more complex than they need to be. I probably will switch hash_get() to use hash_for_each_possible() as well, which will cut down on how hash_get() is a separate case. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx203.postini.com [74.125.245.203]) by kanga.kvack.org (Postfix) with SMTP id 32B966B0044 for ; Fri, 3 Aug 2012 17:41:09 -0400 (EDT) Received: by wibhm6 with SMTP id hm6so5540635wib.8 for ; Fri, 03 Aug 2012 14:41:07 -0700 (PDT) Message-ID: <501C458E.7050000@gmail.com> Date: Fri, 03 Aug 2012 23:41:34 +0200 From: Sasha Levin MIME-Version: 1.0 Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> In-Reply-To: <20120803213017.GK15477@google.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Tejun Heo Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org On 08/03/2012 11:30 PM, Tejun Heo wrote: > Hello, > > On Fri, Aug 03, 2012 at 11:19:57PM +0200, Sasha Levin wrote: >>> Is this supposed to be embedded in struct definition? If so, the name >>> is rather misleading as DEFINE_* is supposed to define and initialize >>> stand-alone constructs. Also, for struct members, simply putting hash >>> entries after struct hash_table should work. >> >> It would work, but I didn't want to just put them in the union since >> I feel it's safer to keep them in a separate struct so they won't be >> used by mistake, > > Just use ugly enough pre/postfixes. If the user still accesses that, > it's the user's fault. I forgot to comment on that one, sorry. If we put hash entries after struct hash_table we don't take the bits field size into account, or did I miss something? -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx113.postini.com [74.125.245.113]) by kanga.kvack.org (Postfix) with SMTP id D19076B0044 for ; Fri, 3 Aug 2012 17:44:19 -0400 (EDT) Received: by pbbrp2 with SMTP id rp2so2227442pbb.14 for ; Fri, 03 Aug 2012 14:44:19 -0700 (PDT) Date: Fri, 3 Aug 2012 14:44:14 -0700 From: Tejun Heo Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120803214414.GL15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C4471.4090706@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <501C4471.4090706@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: Sasha Levin Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Hello, Sasha. On Fri, Aug 03, 2012 at 11:36:49PM +0200, Sasha Levin wrote: > On 08/03/2012 11:30 PM, Tejun Heo wrote: > The function definition itself is just a macro, for example: > > #define MM_SLOTS_HASH_CMP(mm_slot, obj) ((mm_slot)->mm == (obj)) It seems like it would make things more difficult to follow and error-prone. I'd definitely prefer just using functions. > As an alternative, what do you think about simplifying that to be > just a 'cond' instead of a function? Something like: > > hash_get(&mm_slots_hash, mm, struct mm_slot, hash, mm); > > In that case, the last param ("mm") will get unrolled to a condition like this: > > if ((obj)->mm == key) > > Which will be simple and easy for the user. It seems a bit too magical(tm) to me. ;) > The only reason I want to keep this interface is that most cases > I've stumbled so far were easy short comparisons of a struct member > with the key, and I don't want to make them more complex than they > need to be. I probably will switch hash_get() to use > hash_for_each_possible() as well, which will cut down on how > hash_get() is a separate case. I can understand that but I think the benefit we're talking about is a bit too miniscule to matter and to have two different interfaces. What do others think? Thanks. -- tejun -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx140.postini.com [74.125.245.140]) by kanga.kvack.org (Postfix) with SMTP id B69DA6B0044 for ; Fri, 3 Aug 2012 17:48:11 -0400 (EDT) Received: by pbbrp2 with SMTP id rp2so2231677pbb.14 for ; Fri, 03 Aug 2012 14:48:11 -0700 (PDT) Date: Fri, 3 Aug 2012 14:48:06 -0700 From: Tejun Heo Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120803214806.GM15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <501C458E.7050000@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: Sasha Levin Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Hello, On Fri, Aug 03, 2012 at 11:41:34PM +0200, Sasha Levin wrote: > I forgot to comment on that one, sorry. > > If we put hash entries after struct hash_table we don't take the > bits field size into account, or did I miss something? So, if you do the following, struct { struct { int i; long ar[]; } B; long __ar_storage[32]; } A; It should always be safe to dereference A.B.ar[31]. I'm not sure whether this is something guaranteed by C tho. Maybe compilers are allowed to put members in reverse order but I think we already depend on the above. Thanks. -- tejun -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx152.postini.com [74.125.245.152]) by kanga.kvack.org (Postfix) with SMTP id 1CBCF6B0044 for ; Fri, 3 Aug 2012 18:19:37 -0400 (EDT) Received: by bkcjc3 with SMTP id jc3so585489bkc.14 for ; Fri, 03 Aug 2012 15:19:35 -0700 (PDT) Message-ID: <501C4E92.1070801@gmail.com> Date: Sat, 04 Aug 2012 00:20:02 +0200 From: Sasha Levin MIME-Version: 1.0 Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> In-Reply-To: <20120803214806.GM15477@google.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Tejun Heo Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org On 08/03/2012 11:48 PM, Tejun Heo wrote: > Hello, > > On Fri, Aug 03, 2012 at 11:41:34PM +0200, Sasha Levin wrote: >> I forgot to comment on that one, sorry. >> >> If we put hash entries after struct hash_table we don't take the >> bits field size into account, or did I miss something? > > So, if you do the following, > > struct { > struct { > int i; > long ar[]; > } B; > long __ar_storage[32]; > } A; struct A should have been an union, right? > It should always be safe to dereference A.B.ar[31]. I'm not sure > whether this is something guaranteed by C tho. Maybe compilers are > allowed to put members in reverse order but I think we already depend > on the above. why is accessing A.B.ar[31] safe? __ar_storage is only 32*sizeof(long) bytes long, while struct B would need to be 32*sizeof(long) + sizeof(int) bytes long so that A.B.ar[31] access would be safe. > Thanks. > -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx134.postini.com [74.125.245.134]) by kanga.kvack.org (Postfix) with SMTP id 7B86E6B0044 for ; Fri, 3 Aug 2012 18:23:44 -0400 (EDT) Received: by pbbrp2 with SMTP id rp2so2270679pbb.14 for ; Fri, 03 Aug 2012 15:23:43 -0700 (PDT) Date: Fri, 3 Aug 2012 15:23:39 -0700 From: Tejun Heo Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120803222339.GN15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <501C4E92.1070801@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: Sasha Levin Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Hello, On Sat, Aug 04, 2012 at 12:20:02AM +0200, Sasha Levin wrote: > On 08/03/2012 11:48 PM, Tejun Heo wrote: > > On Fri, Aug 03, 2012 at 11:41:34PM +0200, Sasha Levin wrote: > >> I forgot to comment on that one, sorry. > >> > >> If we put hash entries after struct hash_table we don't take the > >> bits field size into account, or did I miss something? > > > > So, if you do the following, > > > > struct { > > struct { > > int i; > > long ar[]; > > } B; > > long __ar_storage[32]; > > } A; > > struct A should have been an union, right? I actually meant an enclosing struct. When you're defining a struct member, simply putting the storage after a struct with var array should be good enough. If that doesn't work, quite a few things in the kernel will break. Thanks. -- tejun -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx119.postini.com [74.125.245.119]) by kanga.kvack.org (Postfix) with SMTP id B7E976B0044 for ; Fri, 3 Aug 2012 18:25:48 -0400 (EDT) Received: by bkcjc3 with SMTP id jc3so586800bkc.14 for ; Fri, 03 Aug 2012 15:25:47 -0700 (PDT) Message-ID: <501C5005.2090107@gmail.com> Date: Sat, 04 Aug 2012 00:26:13 +0200 From: Sasha Levin MIME-Version: 1.0 Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> In-Reply-To: <20120803222339.GN15477@google.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Tejun Heo Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org On 08/04/2012 12:23 AM, Tejun Heo wrote: > Hello, > > On Sat, Aug 04, 2012 at 12:20:02AM +0200, Sasha Levin wrote: >> On 08/03/2012 11:48 PM, Tejun Heo wrote: >>> On Fri, Aug 03, 2012 at 11:41:34PM +0200, Sasha Levin wrote: >>>> I forgot to comment on that one, sorry. >>>> >>>> If we put hash entries after struct hash_table we don't take the >>>> bits field size into account, or did I miss something? >>> >>> So, if you do the following, >>> >>> struct { >>> struct { >>> int i; >>> long ar[]; >>> } B; >>> long __ar_storage[32]; >>> } A; >> >> struct A should have been an union, right? > > I actually meant an enclosing struct. When you're defining a struct > member, simply putting the storage after a struct with var array > should be good enough. If that doesn't work, quite a few things in > the kernel will break. Ah, I see, I've missed that part. Thanks! > Thanks. > -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx157.postini.com [74.125.245.157]) by kanga.kvack.org (Postfix) with SMTP id D97EB6B0044 for ; Fri, 3 Aug 2012 18:29:32 -0400 (EDT) Received: by wibhq4 with SMTP id hq4so883140wib.8 for ; Fri, 03 Aug 2012 15:29:31 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <20120803222339.GN15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> From: Linus Torvalds Date: Fri, 3 Aug 2012 15:29:10 -0700 Message-ID: Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Content-Type: text/plain; charset=ISO-8859-1 Sender: owner-linux-mm@kvack.org List-ID: To: Tejun Heo Cc: Sasha Levin , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org On Fri, Aug 3, 2012 at 3:23 PM, Tejun Heo wrote: > > I actually meant an enclosing struct. When you're defining a struct > member, simply putting the storage after a struct with var array > should be good enough. If that doesn't work, quite a few things in > the kernel will break. The unsigned member of a struct has to be the last one, so your struct won't work. Linus -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx135.postini.com [74.125.245.135]) by kanga.kvack.org (Postfix) with SMTP id 9B3AE6B0044 for ; Fri, 3 Aug 2012 18:36:39 -0400 (EDT) Received: by pbbrp2 with SMTP id rp2so2285327pbb.14 for ; Fri, 03 Aug 2012 15:36:38 -0700 (PDT) Date: Fri, 3 Aug 2012 15:36:34 -0700 From: Tejun Heo Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120803223634.GO15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Sender: owner-linux-mm@kvack.org List-ID: To: Linus Torvalds Cc: Sasha Levin , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org On Fri, Aug 03, 2012 at 03:29:10PM -0700, Linus Torvalds wrote: > On Fri, Aug 3, 2012 at 3:23 PM, Tejun Heo wrote: > > > > I actually meant an enclosing struct. When you're defining a struct > > member, simply putting the storage after a struct with var array > > should be good enough. If that doesn't work, quite a few things in > > the kernel will break. > > The unsigned member of a struct has to be the last one, so your struct > won't work. I suppose you mean unsized. I remember this working. Maybe I'm confusing it with zero-sized array. Hmm... gcc doesn't complain about the following. --std=c99 seems happy too. #include struct A { int i; long ar[]; }; struct B { struct A a; long ar_storage[32]; }; int main(void) { printf("sizeof(A)=%zd sizeof(B)=%zd\n", sizeof(struct A), sizeof(struct B)); return 0; } $ ./a.out sizeof(A)=8 sizeof(B)=264 -- tejun -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx148.postini.com [74.125.245.148]) by kanga.kvack.org (Postfix) with SMTP id BA2846B0044 for ; Fri, 3 Aug 2012 19:48:09 -0400 (EDT) Received: by wgbdq12 with SMTP id dq12so1015027wgb.26 for ; Fri, 03 Aug 2012 16:48:08 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <20120803223634.GO15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> <20120803223634.GO15477@google.com> From: Linus Torvalds Date: Fri, 3 Aug 2012 16:47:47 -0700 Message-ID: Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Content-Type: text/plain; charset=ISO-8859-1 Sender: owner-linux-mm@kvack.org List-ID: To: Tejun Heo Cc: Sasha Levin , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org On Fri, Aug 3, 2012 at 3:36 PM, Tejun Heo wrote: > > I suppose you mean unsized. I remember this working. Maybe I'm > confusing it with zero-sized array. Hmm... gcc doesn't complain about > the following. --std=c99 seems happy too. Ok, I'm surprised, but maybe it's supposed to work if you do it inside another struct like that, exactly so that you can preallocate things.. Or maybe it's just a gcc bug. I do think this all is way hackier than Sasha's original simple code that didn't need these kinds of games, and didn't need a size member at all. I really think all the extra complexity and overhead is just *bad*. The first simple version was much nicer and likely generated better code too. Linus -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx114.postini.com [74.125.245.114]) by kanga.kvack.org (Postfix) with SMTP id 053386B005A for ; Fri, 3 Aug 2012 20:02:49 -0400 (EDT) Received: by bkcjc3 with SMTP id jc3so606455bkc.14 for ; Fri, 03 Aug 2012 17:02:48 -0700 (PDT) Message-ID: <501C66C2.2020706@gmail.com> Date: Sat, 04 Aug 2012 02:03:14 +0200 From: Sasha Levin MIME-Version: 1.0 Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> <20120803223634.GO15477@google.com> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Linus Torvalds Cc: Tejun Heo , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Hi Linus, On 08/04/2012 01:47 AM, Linus Torvalds wrote: > Or maybe it's just a gcc bug. I do think this all is way hackier than > Sasha's original simple code that didn't need these kinds of games, > and didn't need a size member at all. > > I really think all the extra complexity and overhead is just *bad*. > The first simple version was much nicer and likely generated better > code too. The problem with that code was that it doesn't work with dynamically allocated hashtables, or hashtables that grow/shrink. The alternative to going down this path, is going back to the old code and saying that it only works for the simple case, and if you're interested in something more complex it should have it's own different implementation. Does it make sense? We'll keep the simple & common case simple, and let anyone who needs something more complex than this write it as an extension? -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx198.postini.com [74.125.245.198]) by kanga.kvack.org (Postfix) with SMTP id 170DB6B0044 for ; Fri, 3 Aug 2012 20:05:37 -0400 (EDT) Received: by pbbrp2 with SMTP id rp2so2390159pbb.14 for ; Fri, 03 Aug 2012 17:05:36 -0700 (PDT) Date: Fri, 3 Aug 2012 17:05:31 -0700 From: Tejun Heo Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120804000531.GP15477@google.com> References: <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> <20120803223634.GO15477@google.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Sender: owner-linux-mm@kvack.org List-ID: To: Linus Torvalds Cc: Sasha Levin , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Hello, On Fri, Aug 03, 2012 at 04:47:47PM -0700, Linus Torvalds wrote: > On Fri, Aug 3, 2012 at 3:36 PM, Tejun Heo wrote: > > > > I suppose you mean unsized. I remember this working. Maybe I'm > > confusing it with zero-sized array. Hmm... gcc doesn't complain about > > the following. --std=c99 seems happy too. > > Ok, I'm surprised, but maybe it's supposed to work if you do it inside > another struct like that, exactly so that you can preallocate things.. Yeah, I think the rule is var array should be the last member of any given struct definition. Once a struct is defined, its alignment and size are fixed and it behaves like any other struct. > Or maybe it's just a gcc bug. I do think this all is way hackier than > Sasha's original simple code that didn't need these kinds of games, > and didn't need a size member at all. > > I really think all the extra complexity and overhead is just *bad*. > The first simple version was much nicer and likely generated better > code too. The size member could have performance impact in extreme cases. If we're looking for something simple & fast, maybe just pass in @size as argument and be done with it? Thanks. -- tejun -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx177.postini.com [74.125.245.177]) by kanga.kvack.org (Postfix) with SMTP id B81696B005D for ; Fri, 3 Aug 2012 20:06:10 -0400 (EDT) Received: by weys10 with SMTP id s10so982415wey.14 for ; Fri, 03 Aug 2012 17:06:09 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <501C66C2.2020706@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> <20120803223634.GO15477@google.com> <501C66C2.2020706@gmail.com> From: Linus Torvalds Date: Fri, 3 Aug 2012 17:05:48 -0700 Message-ID: Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Content-Type: text/plain; charset=ISO-8859-1 Sender: owner-linux-mm@kvack.org List-ID: To: Sasha Levin Cc: Tejun Heo , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org On Fri, Aug 3, 2012 at 5:03 PM, Sasha Levin wrote: > > The problem with that code was that it doesn't work with dynamically allocated hashtables, or hashtables that grow/shrink. Sure. But once you have that kind of complexity, why would you care about the trivial cases? Linus -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx111.postini.com [74.125.245.111]) by kanga.kvack.org (Postfix) with SMTP id 347276B0044 for ; Fri, 3 Aug 2012 20:32:42 -0400 (EDT) Received: by bkcjc3 with SMTP id jc3so612042bkc.14 for ; Fri, 03 Aug 2012 17:32:40 -0700 (PDT) Message-ID: <501C6DC3.90904@gmail.com> Date: Sat, 04 Aug 2012 02:33:07 +0200 From: Sasha Levin MIME-Version: 1.0 Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> <20120803223634.GO15477@google.com> <501C66C2.2020706@gmail.com> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Linus Torvalds Cc: Tejun Heo , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org On 08/04/2012 02:05 AM, Linus Torvalds wrote: > On Fri, Aug 3, 2012 at 5:03 PM, Sasha Levin wrote: >> >> The problem with that code was that it doesn't work with dynamically allocated hashtables, or hashtables that grow/shrink. > > Sure. But once you have that kind of complexity, why would you care > about the trivial cases? Because there are far more trivial cases than complex ones - I've counted 50+ of these "trivial" cases. None of them need the complexity we're trying to deal with at the moment. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx107.postini.com [74.125.245.107]) by kanga.kvack.org (Postfix) with SMTP id 3C2E36B0075 for ; Sat, 4 Aug 2012 20:36:38 -0400 (EDT) Message-ID: <1344126994.27983.116.camel@gandalf.stny.rr.com> Subject: Re: [RFC v2 6/7] tracepoint: use new hashtable implementation From: Steven Rostedt Date: Sat, 04 Aug 2012 20:36:34 -0400 In-Reply-To: <1344003788-1417-7-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-7-git-send-email-levinsasha928@gmail.com> Content-Type: text/plain; charset="ISO-8859-15" Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Sasha Levin Cc: torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Mathieu Desnoyers FYI, Mathieu is the author of this file. -- Steve On Fri, 2012-08-03 at 16:23 +0200, Sasha Levin wrote: > Switch tracepoints to use the new hashtable implementation. This reduces the amount of > generic unrelated code in the tracepoints. > > Signed-off-by: Sasha Levin > --- > kernel/tracepoint.c | 26 +++++++++----------------- > 1 files changed, 9 insertions(+), 17 deletions(-) > > diff --git a/kernel/tracepoint.c b/kernel/tracepoint.c > index d96ba22..b5a2650 100644 > --- a/kernel/tracepoint.c > +++ b/kernel/tracepoint.c > @@ -26,6 +26,7 @@ > #include > #include > #include > +#include > > 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]; > +DEFINE_STATIC_HASHTABLE(tracepoint_table, TRACEPOINT_HASH_BITS); > > /* > * Note about RCU : > @@ -191,16 +191,14 @@ 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, node, e, hlist, hash) > if (!strcmp(name, e->name)) > return e; > - } > + > return NULL; > } > > @@ -210,19 +208,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 +226,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 +236,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); > } > -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx163.postini.com [74.125.245.163]) by kanga.kvack.org (Postfix) with SMTP id CFBF66B005D for ; Sat, 4 Aug 2012 20:58:52 -0400 (EDT) From: ebiederm@xmission.com (Eric W. Biederman) References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-3-git-send-email-levinsasha928@gmail.com> Date: Sat, 04 Aug 2012 17:58:32 -0700 In-Reply-To: <1344003788-1417-3-git-send-email-levinsasha928@gmail.com> (Sasha Levin's message of "Fri, 3 Aug 2012 16:23:03 +0200") Message-ID: <87pq76tarr.fsf@xmission.com> MIME-Version: 1.0 Content-Type: text/plain Subject: Re: [RFC v2 2/7] user_ns: use new hashtable implementation Sender: owner-linux-mm@kvack.org List-ID: To: Sasha Levin Cc: torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Sasha Levin writes: > Switch user_ns to use the new hashtable implementation. This reduces the amount of > generic unrelated code in user_ns. Just looking at this ick. - Your comparison function is broken. - The naming is awkward. hash_get without a reference count being incremented? - The magic is deep. hash_get is named like a function but takes a piece of code to call like only a macro can. - uid_hash_find always bumped the reference count but your uidhash_entry doesn't nor do all of the callers of uidhash_entry bump the reference count. Nacked-by: "Eric W. Biederman" I don't have the time for a new improved better hash table that makes the code buggier. Eric > Signed-off-by: Sasha Levin > --- > kernel/user.c | 53 ++++++++++++++++++----------------------------------- > 1 files changed, 18 insertions(+), 35 deletions(-) > > diff --git a/kernel/user.c b/kernel/user.c > index b815fef..555c71a 100644 > --- a/kernel/user.c > +++ b/kernel/user.c > @@ -16,6 +16,7 @@ > #include > #include > #include > +#include > > /* > * userns count is 1 for root user, 1 for init_uts_ns, > @@ -50,15 +51,14 @@ EXPORT_SYMBOL_GPL(init_user_ns); > * UID task count cache, to get fast user lookup in "alloc_uid" > * when changing user ID's (ie setuid() and friends). > */ > - > -#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)))) > +#define UIDHASH_BITS (CONFIG_BASE_SMALL ? 3 : 7) > +#define UIDHASH_CMP(obj, key) ((obj)->uid == (key)) > +#define uidhash_entry(key) (hash_get(&uidhash_table, key, \ > + struct user_struct, uidhash_node, \ > + UIDHASH_CMP)) > > static struct kmem_cache *uid_cachep; > -struct hlist_head uidhash_table[UIDHASH_SZ]; > +DEFINE_STATIC_HASHTABLE(uidhash_table, UIDHASH_BITS); > > /* > * The uidhash_lock is mostly taken from process context, but it is > @@ -84,29 +84,14 @@ 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, up->uid); > } > > static void uid_hash_remove(struct user_struct *up) > { > - hlist_del_init(&up->uidhash_node); > -} > - > -static struct user_struct *uid_hash_find(kuid_t uid, struct hlist_head *hashent) > -{ > - struct user_struct *user; > - struct hlist_node *h; > - > - hlist_for_each_entry(user, h, hashent, uidhash_node) { > - if (uid_eq(user->uid, uid)) { > - atomic_inc(&user->__count); > - return user; > - } > - } > - > - return NULL; > + hash_del(&up->uidhash_node); > } > > /* IRQs are disabled and uidhash_lock is held upon function entry. > @@ -135,7 +120,9 @@ 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 = uidhash_entry(uid); > + if (ret) > + atomic_inc(&ret->__count); > spin_unlock_irqrestore(&uidhash_lock, flags); > return ret; > } > @@ -156,11 +143,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 = uidhash_entry(uid); > spin_unlock_irq(&uidhash_lock); > > if (!up) { > @@ -176,13 +162,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 = uidhash_entry(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 +182,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, UIDHASH_BITS); > > /* 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; -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx155.postini.com [74.125.245.155]) by kanga.kvack.org (Postfix) with SMTP id 081F26B0044 for ; Sun, 5 Aug 2012 12:31:16 -0400 (EDT) Date: Sun, 5 Aug 2012 12:31:14 -0400 From: Mathieu Desnoyers Subject: Re: [RFC v2 6/7] tracepoint: use new hashtable implementation Message-ID: <20120805163114.GA21768@Krystal> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-7-git-send-email-levinsasha928@gmail.com> <1344126994.27983.116.camel@gandalf.stny.rr.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1344126994.27983.116.camel@gandalf.stny.rr.com> Sender: owner-linux-mm@kvack.org List-ID: To: Steven Rostedt Cc: Sasha Levin , torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org * Steven Rostedt (rostedt@goodmis.org) wrote: > FYI, Mathieu is the author of this file. > > -- Steve > > > On Fri, 2012-08-03 at 16:23 +0200, Sasha Levin wrote: > > Switch tracepoints to use the new hashtable implementation. This reduces the amount of > > generic unrelated code in the tracepoints. > > > > Signed-off-by: Sasha Levin > > --- > > kernel/tracepoint.c | 26 +++++++++----------------- > > 1 files changed, 9 insertions(+), 17 deletions(-) > > > > diff --git a/kernel/tracepoint.c b/kernel/tracepoint.c > > index d96ba22..b5a2650 100644 > > --- a/kernel/tracepoint.c > > +++ b/kernel/tracepoint.c > > @@ -26,6 +26,7 @@ > > #include > > #include > > #include > > +#include > > > > 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]; > > +DEFINE_STATIC_HASHTABLE(tracepoint_table, TRACEPOINT_HASH_BITS); I wonder why the "static" has been embedded within "DEFINE_STATIC_HASHTABLE" ? I'm used to see something similar to: static DEFINE_HASHTABLE(tracepoint_table, TRACEPOINT_HASH_BITS); elsewhere in the kernel (e.g. static DEFINE_PER_CPU(), static DEFINE_MUTEX(), etc). > > > > /* > > * Note about RCU : > > @@ -191,16 +191,14 @@ 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, node, e, hlist, hash) > > if (!strcmp(name, e->name)) > > return e; > > - } > > + Typically, where there are 2 or more nesting levels, I try to keep the outer brackets, even if the 1st level only contain a single statement (this is what I did across tracepoint.c). This is especially useful when nesting multiple if levels, and ensures the "else" clause match the right if. We might want to keep it that way within the file, to ensure style consistency. Other than that, it looks good! Thanks! Mathieu > > return NULL; > > } > > > > @@ -210,19 +208,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 +226,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 +236,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); > > } > > > > -- Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx182.postini.com [74.125.245.182]) by kanga.kvack.org (Postfix) with SMTP id D086B6B0044 for ; Sun, 5 Aug 2012 13:02:31 -0400 (EDT) Received: by obhx4 with SMTP id x4so5503724obh.14 for ; Sun, 05 Aug 2012 10:02:31 -0700 (PDT) Message-ID: <501EA749.9060400@gmail.com> Date: Sun, 05 Aug 2012 19:03:05 +0200 From: Sasha Levin MIME-Version: 1.0 Subject: Re: [RFC v2 6/7] tracepoint: use new hashtable implementation References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-7-git-send-email-levinsasha928@gmail.com> <1344126994.27983.116.camel@gandalf.stny.rr.com> <20120805163114.GA21768@Krystal> In-Reply-To: <20120805163114.GA21768@Krystal> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Mathieu Desnoyers Cc: Steven Rostedt , torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org On 08/05/2012 06:31 PM, Mathieu Desnoyers wrote: > * Steven Rostedt (rostedt@goodmis.org) wrote: >> FYI, Mathieu is the author of this file. >> >> -- Steve >> >> >> On Fri, 2012-08-03 at 16:23 +0200, Sasha Levin wrote: >>> Switch tracepoints to use the new hashtable implementation. This reduces the amount of >>> generic unrelated code in the tracepoints. >>> >>> Signed-off-by: Sasha Levin >>> --- >>> kernel/tracepoint.c | 26 +++++++++----------------- >>> 1 files changed, 9 insertions(+), 17 deletions(-) >>> >>> diff --git a/kernel/tracepoint.c b/kernel/tracepoint.c >>> index d96ba22..b5a2650 100644 >>> --- a/kernel/tracepoint.c >>> +++ b/kernel/tracepoint.c >>> @@ -26,6 +26,7 @@ >>> #include >>> #include >>> #include >>> +#include >>> >>> 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]; >>> +DEFINE_STATIC_HASHTABLE(tracepoint_table, TRACEPOINT_HASH_BITS); > > I wonder why the "static" has been embedded within > "DEFINE_STATIC_HASHTABLE" ? I'm used to see something similar to: > > static DEFINE_HASHTABLE(tracepoint_table, TRACEPOINT_HASH_BITS); > > elsewhere in the kernel (e.g. static DEFINE_PER_CPU(), static > DEFINE_MUTEX(), etc). We had to create two different definitions of hashtable, one to be used as static and one to be used in structs. I chose the uglier way of doing it, and Tejun already pointed it out :) It will be much nicer in the future. >>> >>> /* >>> * Note about RCU : >>> @@ -191,16 +191,14 @@ 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, node, e, hlist, hash) >>> if (!strcmp(name, e->name)) >>> return e; >>> - } >>> + > > Typically, where there are 2 or more nesting levels, I try to keep the > outer brackets, even if the 1st level only contain a single statement > (this is what I did across tracepoint.c). This is especially useful when > nesting multiple if levels, and ensures the "else" clause match the > right if. We might want to keep it that way within the file, to ensure > style consistency. Roger that, will fix. > Other than that, it looks good! > > Thanks! > > Mathieu > Thanks for the review Mathieu! -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx174.postini.com [74.125.245.174]) by kanga.kvack.org (Postfix) with SMTP id 461766B0044 for ; Sun, 5 Aug 2012 13:13:01 -0400 (EDT) Date: Sun, 5 Aug 2012 13:12:57 -0400 From: Mathieu Desnoyers Subject: Re: [RFC v2 6/7] tracepoint: use new hashtable implementation Message-ID: <20120805171257.GB22267@Krystal> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-7-git-send-email-levinsasha928@gmail.com> <1344126994.27983.116.camel@gandalf.stny.rr.com> <20120805163114.GA21768@Krystal> <501EA749.9060400@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable In-Reply-To: <501EA749.9060400@gmail.com> Sender: owner-linux-mm@kvack.org List-ID: To: Sasha Levin Cc: Steven Rostedt , torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Lai Jiangshan , "Paul E. McKenney" * Sasha Levin (levinsasha928@gmail.com) wrote: [...] > > Other than that, it looks good! > >=20 > > Thanks! > >=20 > > Mathieu > >=20 >=20 > Thanks for the review Mathieu! No problem! By the way, if you want to have a look at another hash table API for ideas, here is the RCU lock-free hash table API, within the Userspace RCU tree: =66rom git://git.lttng.org/userspace-rcu.git branch: master API: urcu/rculfhash.h core code: rculfhash.c hash table index memory management: rculfhash-mm-chunk.c, rculfhash-mm-mmap.c, rculfhash-mm-order.c The git tree is down today due to electrical maintenance, so I am appending the hash table API below. #ifndef _URCU_RCULFHASH_H #define _URCU_RCULFHASH_H /* * urcu/rculfhash.h * * Userspace RCU library - Lock-Free RCU Hash Table * * Copyright 2011 - Mathieu Desnoyers * Copyright 2011 - Lai Jiangshan * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301= USA * * Include this file _after_ including your URCU flavor. */ #include #include #include #include #ifdef __cplusplus extern "C" { #endif /* * cds_lfht_node: Contains the next pointers and reverse-hash * value required for lookup and traversal of the hash table. * * struct cds_lfht_node should be aligned on 8-bytes boundaries because * the three lower bits are used as flags. It is worth noting that the * information contained within these three bits could be represented on * two bits by re-using the same bit for REMOVAL_OWNER_FLAG and * BUCKET_FLAG. This can be done if we ensure that no iterator nor * updater check the BUCKET_FLAG after it detects that the REMOVED_FLAG * is set. Given the minimum size of struct cds_lfht_node is 8 bytes on * 32-bit architectures, we choose to go for simplicity and reserve * three bits. * * struct cds_lfht_node can be embedded into a structure (as a field). * caa_container_of() can be used to get the structure from the struct * cds_lfht_node after a lookup. * * The structure which embeds it typically holds the key (or key-value * pair) of the object. The caller code is responsible for calculation * of the hash value for cds_lfht APIs. */ struct cds_lfht_node { struct cds_lfht_node *next; /* ptr | REMOVAL_OWNER_FLAG | BUCKET_FLAG | RE= MOVED_FLAG */ unsigned long reverse_hash; } __attribute__((aligned(8))); /* cds_lfht_iter: Used to track state while traversing a hash chain. */ struct cds_lfht_iter { struct cds_lfht_node *node, *next; }; static inline struct cds_lfht_node *cds_lfht_iter_get_node(struct cds_lfht_iter *iter) { return iter->node; } struct cds_lfht; /* * Caution ! * Ensure reader and writer threads are registered as urcu readers. */ typedef int (*cds_lfht_match_fct)(struct cds_lfht_node *node, const void *k= ey); /* * cds_lfht_node_init - initialize a hash table node * @node: the node to initialize. * * This function is kept to be eventually used for debugging purposes * (detection of memory corruption). */ static inline void cds_lfht_node_init(struct cds_lfht_node *node) { } /* * Hash table creation flags. */ enum { CDS_LFHT_AUTO_RESIZE =3D (1U << 0), CDS_LFHT_ACCOUNTING =3D (1U << 1), }; struct cds_lfht_mm_type { struct cds_lfht *(*alloc_cds_lfht)(unsigned long min_nr_alloc_buckets, unsigned long max_nr_buckets); void (*alloc_bucket_table)(struct cds_lfht *ht, unsigned long order); void (*free_bucket_table)(struct cds_lfht *ht, unsigned long order); struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht, unsigned long index); }; extern const struct cds_lfht_mm_type cds_lfht_mm_order; extern const struct cds_lfht_mm_type cds_lfht_mm_chunk; extern const struct cds_lfht_mm_type cds_lfht_mm_mmap; /* * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly. */ struct cds_lfht *_cds_lfht_new(unsigned long init_size, unsigned long min_nr_alloc_buckets, unsigned long max_nr_buckets, int flags, const struct cds_lfht_mm_type *mm, const struct rcu_flavor_struct *flavor, pthread_attr_t *attr); /* * cds_lfht_new - allocate a hash table. * @init_size: number of buckets to allocate initially. Must be power of tw= o. * @min_nr_alloc_buckets: the minimum number of allocated buckets. * (must be power of two) * @max_nr_buckets: the maximum number of hash table buckets allowed. * (must be power of two) * @flags: hash table creation flags (can be combined with bitwise or: '|'). * 0: no flags. * CDS_LFHT_AUTO_RESIZE: automatically resize hash table. * CDS_LFHT_ACCOUNTING: count the number of node addition * and removal in the table * @attr: optional resize worker thread attributes. NULL for default. * * Return NULL on error. * Note: the RCU flavor must be already included before the hash table head= er. * * The programmer is responsible for ensuring that resize operation has a * priority equal to hash table updater threads. It should be performed by * specifying the appropriate priority in the pthread "attr" argument, and, * for CDS_LFHT_AUTO_RESIZE, by ensuring that call_rcu worker threads also = have * this priority level. Having lower priority for call_rcu and resize threa= ds * does not pose any correctness issue, but the resize operations could be * starved by updates, thus leading to long hash table bucket chains. * Threads calling cds_lfht_new are NOT required to be registered RCU * read-side threads. It can be called very early. (e.g. before RCU is * initialized) */ static inline struct cds_lfht *cds_lfht_new(unsigned long init_size, unsigned long min_nr_alloc_buckets, unsigned long max_nr_buckets, int flags, pthread_attr_t *attr) { return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets, flags, NULL, &rcu_flavor, attr); } /* * cds_lfht_destroy - destroy a hash table. * @ht: the hash table to destroy. * @attr: (output) resize worker thread attributes, as received by cds_lfht= _new. * The caller will typically want to free this pointer if dynamically * allocated. The attr point can be NULL if the caller does not * need to be informed of the value passed to cds_lfht_new(). * * Return 0 on success, negative error value on error. * Threads calling this API need to be registered RCU read-side threads. */ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr); /* * cds_lfht_count_nodes - count the number of nodes in the hash table. * @ht: the hash table. * @split_count_before: sample the node count split-counter before traversa= l. * @count: traverse the hash table, count the number of nodes observed. * @split_count_after: sample the node count split-counter after traversal. * * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. */ void cds_lfht_count_nodes(struct cds_lfht *ht, long *split_count_before, unsigned long *count, long *split_count_after); /* * cds_lfht_lookup - lookup a node by key. * @ht: the hash table. * @hash: the key hash. * @match: the key match function. * @key: the current node key. * @iter: node, if found (output). *iter->node set to NULL if not found. * * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * This function acts as a rcu_dereference() to read the node pointer. */ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash, cds_lfht_match_fct match, const void *key, struct cds_lfht_iter *iter); /* * cds_lfht_next_duplicate - get the next item with same key, after iterato= r. * @ht: the hash table. * @match: the key match function. * @key: the current node key. * @iter: input: current iterator. * output: node, if found. *iter->node set to NULL if not found. * * Uses an iterator initialized by a lookup or traversal. Important: the * iterator _needs_ to be initialized before calling * cds_lfht_next_duplicate. * Sets *iter-node to the following node with same key. * Sets *iter->node to NULL if no following node exists with same key. * RCU read-side lock must be held across cds_lfht_lookup and * cds_lfht_next calls, and also between cds_lfht_next calls using the * node returned by a previous cds_lfht_next. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * This function acts as a rcu_dereference() to read the node pointer. */ void cds_lfht_next_duplicate(struct cds_lfht *ht, cds_lfht_match_fct match, const void *key, struct cds_lfht_iter *iter); /* * cds_lfht_first - get the first node in the table. * @ht: the hash table. * @iter: First node, if exists (output). *iter->node set to NULL if not fo= und. * * Output in "*iter". *iter->node set to NULL if table is empty. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * This function acts as a rcu_dereference() to read the node pointer. */ void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter); /* * cds_lfht_next - get the next node in the table. * @ht: the hash table. * @iter: input: current iterator. * output: next node, if exists. *iter->node set to NULL if not foun= d. * * Input/Output in "*iter". *iter->node set to NULL if *iter was * pointing to the last table node. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * This function acts as a rcu_dereference() to read the node pointer. */ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter); /* * cds_lfht_add - add a node to the hash table. * @ht: the hash table. * @hash: the key hash. * @node: the node to add. * * This function supports adding redundant keys into the table. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * This function issues a full memory barrier before and after its * atomic commit. */ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash, struct cds_lfht_node *node); /* * cds_lfht_add_unique - add a node to hash table, if key is not present. * @ht: the hash table. * @hash: the node's hash. * @match: the key match function. * @key: the node's key. * @node: the node to try adding. * * Return the node added upon success. * Return the unique node already present upon failure. If * cds_lfht_add_unique fails, the node passed as parameter should be * freed by the caller. In this case, the caller does NOT need to wait * for a grace period before freeing the node. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * * The semantic of this function is that if only this function is used * to add keys into the table, no duplicated keys should ever be * observable in the table. The same guarantee apply for combination of * add_unique and add_replace (see below). * * Upon success, this function issues a full memory barrier before and * after its atomic commit. Upon failure, this function acts like a * simple lookup operation: it acts as a rcu_dereference() to read the * node pointer. The failure case does not guarantee any other memory * barrier. */ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht, unsigned long hash, cds_lfht_match_fct match, const void *key, struct cds_lfht_node *node); /* * cds_lfht_add_replace - replace or add a node within hash table. * @ht: the hash table. * @hash: the node's hash. * @match: the key match function. * @key: the node's key. * @node: the node to add. * * Return the node replaced upon success. If no node matching the key * was present, return NULL, which also means the operation succeeded. * This replacement operation should never fail. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * After successful replacement, a grace period must be waited for before * freeing the memory reserved for the returned node. * * The semantic of replacement vs lookups and traversals is the * following: if lookups and traversals are performed between a key * unique insertion and its removal, we guarantee that the lookups and * traversals will always find exactly one instance of the key if it is * replaced concurrently with the lookups. * * Providing this semantic allows us to ensure that replacement-only * schemes will never generate duplicated keys. It also allows us to * guarantee that a combination of add_replace and add_unique updates * will never generate duplicated keys. * * This function issues a full memory barrier before and after its * atomic commit. */ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht, unsigned long hash, cds_lfht_match_fct match, const void *key, struct cds_lfht_node *node); /* * cds_lfht_replace - replace a node pointed to by iter within hash table. * @ht: the hash table. * @old_iter: the iterator position of the node to replace. * @hash: the node's hash. * @match: the key match function. * @key: the node's key. * @new_node: the new node to use as replacement. * * Return 0 if replacement is successful, negative value otherwise. * Replacing a NULL old node or an already removed node will fail with * -ENOENT. * If the hash or value of the node to replace and the new node differ, * this function returns -EINVAL without proceeding to the replacement. * Old node can be looked up with cds_lfht_lookup and cds_lfht_next. * RCU read-side lock must be held between lookup and replacement. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * After successful replacement, a grace period must be waited for before * freeing the memory reserved for the old node (which can be accessed * with cds_lfht_iter_get_node). * * The semantic of replacement vs lookups is the same as * cds_lfht_add_replace(). * * Upon success, this function issues a full memory barrier before and * after its atomic commit. Upon failure, this function does not issue * any memory barrier. */ int cds_lfht_replace(struct cds_lfht *ht, struct cds_lfht_iter *old_iter, unsigned long hash, cds_lfht_match_fct match, const void *key, struct cds_lfht_node *new_node); /* * cds_lfht_del - remove node pointed to by iterator from hash table. * @ht: the hash table. * @node: the node to delete. * * Return 0 if the node is successfully removed, negative value * otherwise. * Deleting a NULL node or an already removed node will fail with a * negative value. * Node can be looked up with cds_lfht_lookup and cds_lfht_next, * followed by use of cds_lfht_iter_get_node. * RCU read-side lock must be held between lookup and removal. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * After successful removal, a grace period must be waited for before * freeing the memory reserved for old node (which can be accessed with * cds_lfht_iter_get_node). * Upon success, this function issues a full memory barrier before and * after its atomic commit. Upon failure, this function does not issue * any memory barrier. */ int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_node *node); /* * cds_lfht_is_node_deleted - query whether a node is removed from hash tab= le. * * Return non-zero if the node is deleted from the hash table, 0 * otherwise. * Node can be looked up with cds_lfht_lookup and cds_lfht_next, * followed by use of cds_lfht_iter_get_node. * RCU read-side lock must be held between lookup and call to this * function. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * This function does not issue any memory barrier. */ int cds_lfht_is_node_deleted(struct cds_lfht_node *node); /* * cds_lfht_resize - Force a hash table resize * @ht: the hash table. * @new_size: update to this hash table size. * * Threads calling this API need to be registered RCU read-side threads. * This function does not (necessarily) issue memory barriers. */ void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size); /* * Note: it is safe to perform element removal (del), replacement, or * any hash table update operation during any of the following hash * table traversals. * These functions act as rcu_dereference() to read the node pointers. */ #define cds_lfht_for_each(ht, iter, node) \ for (cds_lfht_first(ht, iter), \ node =3D cds_lfht_iter_get_node(iter); \ node !=3D NULL; \ cds_lfht_next(ht, iter), \ node =3D cds_lfht_iter_get_node(iter)) #define cds_lfht_for_each_duplicate(ht, hash, match, key, iter, node) \ for (cds_lfht_lookup(ht, hash, match, key, iter), \ node =3D cds_lfht_iter_get_node(iter); \ node !=3D NULL; \ cds_lfht_next_duplicate(ht, match, key, iter), \ node =3D cds_lfht_iter_get_node(iter)) #define cds_lfht_for_each_entry(ht, iter, pos, member) \ for (cds_lfht_first(ht, iter), \ pos =3D caa_container_of(cds_lfht_iter_get_node(iter), \ __typeof__(*(pos)), member); \ &(pos)->member !=3D NULL; \ cds_lfht_next(ht, iter), \ pos =3D caa_container_of(cds_lfht_iter_get_node(iter), \ __typeof__(*(pos)), member)) #define cds_lfht_for_each_entry_duplicate(ht, hash, match, key, \ iter, pos, member) \ for (cds_lfht_lookup(ht, hash, match, key, iter), \ pos =3D caa_container_of(cds_lfht_iter_get_node(iter), \ __typeof__(*(pos)), member); \ &(pos)->member !=3D NULL; \ cds_lfht_next_duplicate(ht, match, key, iter), \ pos =3D caa_container_of(cds_lfht_iter_get_node(iter), \ __typeof__(*(pos)), member)) #ifdef __cplusplus } #endif #endif /* _URCU_RCULFHASH_H */ --=20 Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753133Ab2HCOXQ (ORCPT ); Fri, 3 Aug 2012 10:23:16 -0400 Received: from mail-bk0-f46.google.com ([209.85.214.46]:35880 "EHLO mail-bk0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753189Ab2HCOXM (ORCPT ); Fri, 3 Aug 2012 10:23:12 -0400 From: Sasha Levin To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin Subject: [RFC v2 0/7] generic hashtable implementation Date: Fri, 3 Aug 2012 16:23:01 +0200 Message-Id: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> X-Mailer: git-send-email 1.7.8.6 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org There are quite a few places in the kernel which implement a hashtable in a very similar way. Instead of having implementations of a hashtable all over the kernel, we can re-use the code. This patch series introduces a very simple hashtable implementation, and modifies three (random) modules to use it. I've limited it to 3 only so that it would be easy to review and modify, and to show that even at this number we already eliminate a big amount of duplicated code. If this basic hashtable looks ok, future code will include: - RCU support - Self locking (list_bl?) - Converting more code to use the hashtable Changes in V2: - Address review comments by Tejun Heo, Josh Triplett and Eric Beiderman (Thanks all!). - Rebase on top of latest master. - Convert more places to use the hashtable. Hopefully it will trigger more reviews by touching more subsystems. Sasha Levin (7): hashtable: introduce a small and naive hashtable user_ns: use new hashtable implementation mm,ksm: use new hashtable implementation workqueue: use new hashtable implementation mm/huge_memory: use new hashtable implementation tracepoint: use new hashtable implementation net,9p: use new hashtable implementation include/linux/hashtable.h | 75 ++++++++++++++++++++++++++++++++++++ kernel/tracepoint.c | 26 ++++-------- kernel/user.c | 53 +++++++++----------------- kernel/workqueue.c | 93 +++++++-------------------------------------- mm/huge_memory.c | 56 +++++---------------------- mm/ksm.c | 29 ++++---------- net/9p/error.c | 17 ++++---- 7 files changed, 144 insertions(+), 205 deletions(-) create mode 100644 include/linux/hashtable.h -- 1.7.8.6 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753650Ab2HCOXT (ORCPT ); Fri, 3 Aug 2012 10:23:19 -0400 Received: from mail-bk0-f46.google.com ([209.85.214.46]:35880 "EHLO mail-bk0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753439Ab2HCOXQ (ORCPT ); Fri, 3 Aug 2012 10:23:16 -0400 From: Sasha Levin To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin Subject: [RFC v2 2/7] user_ns: use new hashtable implementation Date: Fri, 3 Aug 2012 16:23:03 +0200 Message-Id: <1344003788-1417-3-git-send-email-levinsasha928@gmail.com> X-Mailer: git-send-email 1.7.8.6 In-Reply-To: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Switch user_ns to use the new hashtable implementation. This reduces the amount of generic unrelated code in user_ns. Signed-off-by: Sasha Levin --- kernel/user.c | 53 ++++++++++++++++++----------------------------------- 1 files changed, 18 insertions(+), 35 deletions(-) diff --git a/kernel/user.c b/kernel/user.c index b815fef..555c71a 100644 --- a/kernel/user.c +++ b/kernel/user.c @@ -16,6 +16,7 @@ #include #include #include +#include /* * userns count is 1 for root user, 1 for init_uts_ns, @@ -50,15 +51,14 @@ EXPORT_SYMBOL_GPL(init_user_ns); * UID task count cache, to get fast user lookup in "alloc_uid" * when changing user ID's (ie setuid() and friends). */ - -#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)))) +#define UIDHASH_BITS (CONFIG_BASE_SMALL ? 3 : 7) +#define UIDHASH_CMP(obj, key) ((obj)->uid == (key)) +#define uidhash_entry(key) (hash_get(&uidhash_table, key, \ + struct user_struct, uidhash_node, \ + UIDHASH_CMP)) static struct kmem_cache *uid_cachep; -struct hlist_head uidhash_table[UIDHASH_SZ]; +DEFINE_STATIC_HASHTABLE(uidhash_table, UIDHASH_BITS); /* * The uidhash_lock is mostly taken from process context, but it is @@ -84,29 +84,14 @@ 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, up->uid); } static void uid_hash_remove(struct user_struct *up) { - hlist_del_init(&up->uidhash_node); -} - -static struct user_struct *uid_hash_find(kuid_t uid, struct hlist_head *hashent) -{ - struct user_struct *user; - struct hlist_node *h; - - hlist_for_each_entry(user, h, hashent, uidhash_node) { - if (uid_eq(user->uid, uid)) { - atomic_inc(&user->__count); - return user; - } - } - - return NULL; + hash_del(&up->uidhash_node); } /* IRQs are disabled and uidhash_lock is held upon function entry. @@ -135,7 +120,9 @@ 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 = uidhash_entry(uid); + if (ret) + atomic_inc(&ret->__count); spin_unlock_irqrestore(&uidhash_lock, flags); return ret; } @@ -156,11 +143,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 = uidhash_entry(uid); spin_unlock_irq(&uidhash_lock); if (!up) { @@ -176,13 +162,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 = uidhash_entry(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 +182,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, UIDHASH_BITS); /* 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 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753967Ab2HCOXg (ORCPT ); Fri, 3 Aug 2012 10:23:36 -0400 Received: from mail-bk0-f46.google.com ([209.85.214.46]:58633 "EHLO mail-bk0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753675Ab2HCOXX (ORCPT ); Fri, 3 Aug 2012 10:23:23 -0400 From: Sasha Levin To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin Subject: [RFC v2 5/7] mm/huge_memory: use new hashtable implementation Date: Fri, 3 Aug 2012 16:23:06 +0200 Message-Id: <1344003788-1417-6-git-send-email-levinsasha928@gmail.com> X-Mailer: git-send-email 1.7.8.6 In-Reply-To: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 --- mm/huge_memory.c | 56 ++++++++++------------------------------------------- 1 files changed, 11 insertions(+), 45 deletions(-) diff --git a/mm/huge_memory.c b/mm/huge_memory.c index 57c4b93..7b2cad5 100644 --- a/mm/huge_memory.c +++ b/mm/huge_memory.c @@ -17,6 +17,7 @@ #include #include #include +#include #include #include #include "internal.h" @@ -57,12 +58,13 @@ 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 +#define MM_SLOTS_HASH_CMP(mm_slot, obj) ((mm_slot)->mm == (obj)) +DEFINE_STATIC_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_BITS); + static struct kmem_cache *mm_slot_cache __read_mostly; /** @@ -140,7 +142,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 +556,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 @@ -1562,47 +1558,17 @@ 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 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; - } - return NULL; + return hash_get(&mm_slots_hash, mm, struct mm_slot, + hash, MM_SLOTS_HASH_CMP); } static void insert_to_mm_slots_hash(struct mm_struct *mm, struct mm_slot *mm_slot) { - struct hlist_head *bucket; - - bucket = &mm_slots_hash[((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) @@ -1675,7 +1641,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; } @@ -2089,7 +2055,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 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753834Ab2HCOXa (ORCPT ); Fri, 3 Aug 2012 10:23:30 -0400 Received: from mail-bk0-f46.google.com ([209.85.214.46]:35880 "EHLO mail-bk0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753620Ab2HCOXU (ORCPT ); Fri, 3 Aug 2012 10:23:20 -0400 From: Sasha Levin To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin Subject: [RFC v2 4/7] workqueue: use new hashtable implementation Date: Fri, 3 Aug 2012 16:23:05 +0200 Message-Id: <1344003788-1417-5-git-send-email-levinsasha928@gmail.com> X-Mailer: git-send-email 1.7.8.6 In-Reply-To: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Switch workqueues to use the new hashtable implementation. This reduces the amount of generic unrelated code in the workqueues. Signed-off-by: Sasha Levin --- kernel/workqueue.c | 93 ++++++++-------------------------------------------- 1 files changed, 14 insertions(+), 79 deletions(-) diff --git a/kernel/workqueue.c b/kernel/workqueue.c index 692d976..480975d 100644 --- a/kernel/workqueue.c +++ b/kernel/workqueue.c @@ -41,6 +41,7 @@ #include #include #include +#include #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 */ @@ -102,6 +101,8 @@ enum { HIGHPRI_NICE_LEVEL = -20, }; +#define worker_hash_cmp(obj, key) ((obj)->current_work == (key)) + /* * Structure fields follow one of the following exclusion rules. * @@ -180,7 +181,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 */ @@ -287,10 +288,6 @@ EXPORT_SYMBOL_GPL(system_nrt_freezable_wq); for ((pool) = &(gcwq)->pools[0]; \ (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) - static inline int __next_gcwq_cpu(int cpu, const struct cpumask *mask, unsigned int sw) { @@ -822,70 +819,11 @@ 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 * - * Find a worker which is executing @work on @gcwq. This function is - * identical to __find_worker_executing_work() except that this - * function calculates @bwh itself. + * Find a worker which is executing @work on @gcwq. * * CONTEXT: * spin_lock_irq(gcwq->lock). @@ -897,8 +835,8 @@ static struct worker *__find_worker_executing_work(struct global_cwq *gcwq, static struct worker *find_worker_executing_work(struct global_cwq *gcwq, struct work_struct *work) { - return __find_worker_executing_work(gcwq, busy_worker_head(gcwq, work), - work); + return hash_get(&gcwq->busy_hash, work, struct worker, + hentry, worker_hash_cmp); } /** @@ -959,7 +897,7 @@ static bool is_chained_work(struct workqueue_struct *wq) int i; spin_lock_irqsave(&gcwq->lock, flags); - for_each_busy_worker(worker, i, pos, gcwq) { + hash_for_each(i, pos, &gcwq->busy_hash, worker, hentry) { if (worker->task != current) continue; spin_unlock_irqrestore(&gcwq->lock, flags); @@ -1432,7 +1370,7 @@ retry: wake_up_all(&gcwq->rebind_hold); /* rebind busy workers */ - for_each_busy_worker(worker, i, pos, gcwq) { + hash_for_each(i, pos, &gcwq->busy_hash, worker, hentry) { struct work_struct *rebind_work = &worker->rebind_work; /* morph UNBOUND to REBIND */ @@ -1932,7 +1870,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; @@ -1964,7 +1901,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; @@ -1972,7 +1909,7 @@ __acquires(&gcwq->lock) /* claim and process */ debug_work_deactivate(work); - hlist_add_head(&worker->hentry, bwh); + hash_add(&gcwq->busy_hash, &worker->hentry, (long)work); worker->current_work = work; worker->current_cwq = cwq; work_color = get_work_color(work); @@ -2027,7 +1964,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); @@ -3405,7 +3342,7 @@ static void gcwq_unbind_fn(struct work_struct *work) list_for_each_entry(worker, &pool->idle_list, entry) worker->flags |= WORKER_UNBOUND; - for_each_busy_worker(worker, i, pos, gcwq) + hash_for_each(i, pos, &gcwq->busy_hash, worker, hentry) worker->flags |= WORKER_UNBOUND; gcwq->flags |= GCWQ_DISASSOCIATED; @@ -3690,7 +3627,6 @@ out_unlock: static int __init init_workqueues(void) { unsigned int cpu; - int i; cpu_notifier(workqueue_cpu_up_callback, CPU_PRI_WORKQUEUE_UP); cpu_notifier(workqueue_cpu_down_callback, CPU_PRI_WORKQUEUE_DOWN); @@ -3704,8 +3640,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, BUSY_WORKER_HASH_ORDER); for_each_worker_pool(pool, gcwq) { pool->gcwq = gcwq; -- 1.7.8.6 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754008Ab2HCOXm (ORCPT ); Fri, 3 Aug 2012 10:23:42 -0400 Received: from mail-bk0-f46.google.com ([209.85.214.46]:35880 "EHLO mail-bk0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753686Ab2HCOXY (ORCPT ); Fri, 3 Aug 2012 10:23:24 -0400 From: Sasha Levin To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin Subject: [RFC v2 6/7] tracepoint: use new hashtable implementation Date: Fri, 3 Aug 2012 16:23:07 +0200 Message-Id: <1344003788-1417-7-git-send-email-levinsasha928@gmail.com> X-Mailer: git-send-email 1.7.8.6 In-Reply-To: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Switch tracepoints to use the new hashtable implementation. This reduces the amount of generic unrelated code in the tracepoints. Signed-off-by: Sasha Levin --- kernel/tracepoint.c | 26 +++++++++----------------- 1 files changed, 9 insertions(+), 17 deletions(-) diff --git a/kernel/tracepoint.c b/kernel/tracepoint.c index d96ba22..b5a2650 100644 --- a/kernel/tracepoint.c +++ b/kernel/tracepoint.c @@ -26,6 +26,7 @@ #include #include #include +#include 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]; +DEFINE_STATIC_HASHTABLE(tracepoint_table, TRACEPOINT_HASH_BITS); /* * Note about RCU : @@ -191,16 +191,14 @@ 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, node, e, hlist, hash) if (!strcmp(name, e->name)) return e; - } + return NULL; } @@ -210,19 +208,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 +226,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 +236,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); } -- 1.7.8.6 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754081Ab2HCOY4 (ORCPT ); Fri, 3 Aug 2012 10:24:56 -0400 Received: from mail-bk0-f46.google.com ([209.85.214.46]:58633 "EHLO mail-bk0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753740Ab2HCOX1 (ORCPT ); Fri, 3 Aug 2012 10:23:27 -0400 From: Sasha Levin To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin Subject: [RFC v2 7/7] net,9p: use new hashtable implementation Date: Fri, 3 Aug 2012 16:23:08 +0200 Message-Id: <1344003788-1417-8-git-send-email-levinsasha928@gmail.com> X-Mailer: git-send-email 1.7.8.6 In-Reply-To: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 --- net/9p/error.c | 17 ++++++++--------- 1 files changed, 8 insertions(+), 9 deletions(-) diff --git a/net/9p/error.c b/net/9p/error.c index 2ab2de7..f1037db 100644 --- a/net/9p/error.c +++ b/net/9p/error.c @@ -34,7 +34,7 @@ #include #include #include - +#include /** * 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 ERRHASHSZ 5 +DEFINE_STATIC_HASHTABLE(hash_errmap, ERRHASHSZ); /* FixMe - reduce to a reasonable size */ static struct errormap errmap[] = { @@ -196,15 +196,14 @@ int p9_error_init(void) int bucket; /* initialize hash table */ - for (bucket = 0; bucket < ERRHASHSZ; bucket++) - INIT_HLIST_HEAD(&hash_errmap[bucket]); + hash_init(&hash_errmap, ERRHASHSZ); /* 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; + bucket = 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, bucket); } return 1; @@ -228,8 +227,8 @@ int p9_errstr2errno(char *errstr, int len) errno = 0; p = NULL; c = NULL; - bucket = jhash(errstr, len, 0) % ERRHASHSZ; - hlist_for_each_entry(c, p, &hash_errmap[bucket], list) { + bucket = jhash(errstr, len, 0); + hash_for_each_possible(&hash_errmap, p, c, list, bucket) { if (c->namelen == len && !memcmp(c->name, errstr, len)) { errno = c->val; break; -- 1.7.8.6 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753985Ab2HCOZV (ORCPT ); Fri, 3 Aug 2012 10:25:21 -0400 Received: from mail-bk0-f46.google.com ([209.85.214.46]:35880 "EHLO mail-bk0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753189Ab2HCOXS (ORCPT ); Fri, 3 Aug 2012 10:23:18 -0400 From: Sasha Levin To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin Subject: [RFC v2 3/7] mm,ksm: use new hashtable implementation Date: Fri, 3 Aug 2012 16:23:04 +0200 Message-Id: <1344003788-1417-4-git-send-email-levinsasha928@gmail.com> X-Mailer: git-send-email 1.7.8.6 In-Reply-To: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 --- mm/ksm.c | 29 +++++++++-------------------- 1 files changed, 9 insertions(+), 20 deletions(-) diff --git a/mm/ksm.c b/mm/ksm.c index 47c8853..72d062a 100644 --- a/mm/ksm.c +++ b/mm/ksm.c @@ -33,7 +33,7 @@ #include #include #include -#include +#include #include #include @@ -157,8 +157,8 @@ static struct rb_root root_stable_tree = RB_ROOT; static struct rb_root root_unstable_tree = RB_ROOT; #define MM_SLOTS_HASH_SHIFT 10 -#define MM_SLOTS_HASH_HEADS (1 << MM_SLOTS_HASH_SHIFT) -static struct hlist_head mm_slots_hash[MM_SLOTS_HASH_HEADS]; +#define mm_hash_cmp(slot, key) ((slot)->mm == (key)) +DEFINE_STATIC_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_SHIFT); static struct mm_slot ksm_mm_head = { .mm_list = LIST_HEAD_INIT(ksm_mm_head.mm_list), @@ -275,26 +275,15 @@ static inline void free_mm_slot(struct mm_slot *mm_slot) static struct mm_slot *get_mm_slot(struct mm_struct *mm) { - struct mm_slot *mm_slot; - struct hlist_head *bucket; - struct hlist_node *node; - - bucket = &mm_slots_hash[hash_ptr(mm, MM_SLOTS_HASH_SHIFT)]; - hlist_for_each_entry(mm_slot, node, bucket, link) { - if (mm == mm_slot->mm) - return mm_slot; - } - return NULL; + return hash_get(&mm_slots_hash, mm, struct mm_slot, + link, mm_hash_cmp); } static void insert_to_mm_slots_hash(struct mm_struct *mm, struct mm_slot *mm_slot) { - struct hlist_head *bucket; - - bucket = &mm_slots_hash[hash_ptr(mm, MM_SLOTS_HASH_SHIFT)]; mm_slot->mm = mm; - hlist_add_head(&mm_slot->link, bucket); + hash_add(&mm_slots_hash, &mm_slot->link, (long)mm); } static inline int in_stable_tree(struct rmap_item *rmap_item) @@ -647,7 +636,7 @@ static int unmerge_and_remove_all_rmap_items(void) ksm_scan.mm_slot = list_entry(mm_slot->mm_list.next, struct mm_slot, mm_list); if (ksm_test_exit(mm)) { - hlist_del(&mm_slot->link); + hash_del(&mm_slot->link); list_del(&mm_slot->mm_list); spin_unlock(&ksm_mmlist_lock); @@ -1385,7 +1374,7 @@ next_mm: * or when all VM_MERGEABLE areas have been unmapped (and * mmap_sem then protects against race with MADV_MERGEABLE). */ - hlist_del(&slot->link); + hash_del(&slot->link); list_del(&slot->mm_list); spin_unlock(&ksm_mmlist_lock); @@ -1548,7 +1537,7 @@ void __ksm_exit(struct mm_struct *mm) mm_slot = get_mm_slot(mm); if (mm_slot && ksm_scan.mm_slot != mm_slot) { if (!mm_slot->rmap_list) { - hlist_del(&mm_slot->link); + hash_del(&mm_slot->link); list_del(&mm_slot->mm_list); easy_to_free = 1; } else { -- 1.7.8.6 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753807Ab2HCOZx (ORCPT ); Fri, 3 Aug 2012 10:25:53 -0400 Received: from mail-bk0-f46.google.com ([209.85.214.46]:35880 "EHLO mail-bk0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753275Ab2HCOXN (ORCPT ); Fri, 3 Aug 2012 10:23:13 -0400 From: Sasha Levin To: torvalds@linux-foundation.org Cc: tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Sasha Levin Subject: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Date: Fri, 3 Aug 2012 16:23:02 +0200 Message-Id: <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> X-Mailer: git-send-email 1.7.8.6 In-Reply-To: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 --- include/linux/hashtable.h | 75 +++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 75 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..b004cf7 --- /dev/null +++ b/include/linux/hashtable.h @@ -0,0 +1,75 @@ +#ifndef _LINUX_HASHTABLE_H +#define _LINUX_HASHTABLE_H + +#include +#include +#include +#include + +struct hash_table { + size_t bits; + struct hlist_head buckets[]; +}; + +#define DEFINE_STATIC_HASHTABLE(n, b) \ + static struct hash_table n = { .bits = (b), \ + .buckets = { [0 ... ((1 << (b)) - 1)] = HLIST_HEAD_INIT } } + +#define DEFINE_HASHTABLE(n, b) \ + union { \ + struct hash_table n; \ + struct { \ + size_t bits; \ + struct hlist_head buckets[1 << (b)]; \ + } __##n ; \ + }; + +#define HASH_BITS(name) ((name)->bits) +#define HASH_SIZE(name) (1 << (HASH_BITS(name))) + +__attribute__ ((unused)) +static void hash_init(struct hash_table *ht, size_t bits) +{ + size_t i; + + ht->bits = bits; + for (i = 0; i < (1 << bits); i++) + INIT_HLIST_HEAD(&ht->buckets[i]); +} + +static void hash_add(struct hash_table *ht, struct hlist_node *node, long key) +{ + hlist_add_head(node, + &ht->buckets[hash_long((unsigned long)key, HASH_BITS(ht))]); +} + + +#define hash_get(name, key, type, member, cmp_fn) \ +({ \ + struct hlist_node *__node; \ + typeof(key) __key = key; \ + type *__obj = NULL; \ + hlist_for_each_entry(__obj, __node, &(name)->buckets[ \ + hash_long((unsigned long) __key, \ + HASH_BITS(name))], member) \ + if (cmp_fn(__obj, __key)) \ + break; \ + __obj; \ +}) + +__attribute__ ((unused)) +static void hash_del(struct hlist_node *node) +{ + hlist_del_init(node); +} + +#define hash_for_each(bkt, node, name, obj, member) \ + for (bkt = 0; bkt < HASH_SIZE(name); bkt++) \ + hlist_for_each_entry(obj, node, &(name)->buckets[i], member) + +#define hash_for_each_possible(name, node, obj, member, key) \ + hlist_for_each_entry(obj, node, \ + &(name)->buckets[hash_long((unsigned long) key, \ + HASH_BITS(name))], member) + +#endif -- 1.7.8.6 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753085Ab2HCRPW (ORCPT ); Fri, 3 Aug 2012 13:15:22 -0400 Received: from mail-yw0-f46.google.com ([209.85.213.46]:54963 "EHLO mail-yw0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751470Ab2HCRPV (ORCPT ); Fri, 3 Aug 2012 13:15:21 -0400 Date: Fri, 3 Aug 2012 10:15:15 -0700 From: Tejun Heo To: Sasha Levin Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120803171515.GH15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> User-Agent: Mutt/1.5.20 (2009-06-14) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hello, Sasha. On Fri, Aug 03, 2012 at 04:23:02PM +0200, Sasha Levin wrote: > +#define DEFINE_STATIC_HASHTABLE(n, b) \ > + static struct hash_table n = { .bits = (b), \ > + .buckets = { [0 ... ((1 << (b)) - 1)] = HLIST_HEAD_INIT } } What does this "static" mean? > +#define DEFINE_HASHTABLE(n, b) \ > + union { \ > + struct hash_table n; \ > + struct { \ > + size_t bits; \ > + struct hlist_head buckets[1 << (b)]; \ > + } __##n ; \ > + }; Is this supposed to be embedded in struct definition? If so, the name is rather misleading as DEFINE_* is supposed to define and initialize stand-alone constructs. Also, for struct members, simply putting hash entries after struct hash_table should work. Wouldn't using DEFINE_HASHTABLE() for the first macro and DEFINE_HASHTABLE_MEMBER() for the latter be better? > +#define HASH_BITS(name) ((name)->bits) > +#define HASH_SIZE(name) (1 << (HASH_BITS(name))) > + > +__attribute__ ((unused)) Are we using __attribute__((unused)) for functions defined in headers instead of static inline now? If so, why? > +static void hash_init(struct hash_table *ht, size_t bits) > +{ > + size_t i; I would prefer int here but no biggie. > + ht->bits = bits; > + for (i = 0; i < (1 << bits); i++) > + INIT_HLIST_HEAD(&ht->buckets[i]); > +} > + > +static void hash_add(struct hash_table *ht, struct hlist_node *node, long key) > +{ > + hlist_add_head(node, > + &ht->buckets[hash_long((unsigned long)key, HASH_BITS(ht))]); > +} > + > + > +#define hash_get(name, key, type, member, cmp_fn) \ > +({ \ > + struct hlist_node *__node; \ > + typeof(key) __key = key; \ > + type *__obj = NULL; \ > + hlist_for_each_entry(__obj, __node, &(name)->buckets[ \ > + hash_long((unsigned long) __key, \ > + HASH_BITS(name))], member) \ > + if (cmp_fn(__obj, __key)) \ > + break; \ > + __obj; \ > +}) As opposed to using hash_for_each_possible(), how much difference does this make? Is it really worthwhile? Thanks. -- tejun From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753311Ab2HCRQm (ORCPT ); Fri, 3 Aug 2012 13:16:42 -0400 Received: from mail-gh0-f174.google.com ([209.85.160.174]:61662 "EHLO mail-gh0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751793Ab2HCRQk (ORCPT ); Fri, 3 Aug 2012 13:16:40 -0400 Date: Fri, 3 Aug 2012 10:16:35 -0700 From: Tejun Heo To: Sasha Levin Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120803171635.GI15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20120803171515.GH15477@google.com> User-Agent: Mutt/1.5.20 (2009-06-14) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Ooh, one more thing. Comments please. -- tejun From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753517Ab2HCRj3 (ORCPT ); Fri, 3 Aug 2012 13:39:29 -0400 Received: from mail-bk0-f46.google.com ([209.85.214.46]:49726 "EHLO mail-bk0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752062Ab2HCRjQ (ORCPT ); Fri, 3 Aug 2012 13:39:16 -0400 Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable From: Eric Dumazet To: Sasha Levin Cc: torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org In-Reply-To: <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> Content-Type: text/plain; charset="UTF-8" Date: Fri, 03 Aug 2012 19:39:10 +0200 Message-ID: <1344015550.9299.1387.camel@edumazet-glaptop> Mime-Version: 1.0 X-Mailer: Evolution 2.28.3 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Fri, 2012-08-03 at 16:23 +0200, Sasha Levin wrote: > This hashtable implementation is using hlist buckets to provide a simple > hashtable to prevent it from getting reimplemented all over the kernel. > > +static void hash_add(struct hash_table *ht, struct hlist_node *node, long key) > +{ > + hlist_add_head(node, > + &ht->buckets[hash_long((unsigned long)key, HASH_BITS(ht))]); > +} > + Why key is a long, casted later to "unsigned long" ? hash_long() is expensive on 64bit arches, and not really needed if key is an u32 from the beginning ( I am referring to your patches 6 & 7 using jhash() ) Maybe you could use a macro, so that we can automatically select hash_32() if key is an u32, and hash_long() for other types. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753863Ab2HCSA7 (ORCPT ); Fri, 3 Aug 2012 14:00:59 -0400 Received: from mail-bk0-f46.google.com ([209.85.214.46]:43401 "EHLO mail-bk0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753289Ab2HCSA5 (ORCPT ); Fri, 3 Aug 2012 14:00:57 -0400 Subject: Re: [RFC v2 7/7] net,9p: use new hashtable implementation From: Eric Dumazet To: Sasha Levin Cc: torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org In-Reply-To: <1344003788-1417-8-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-8-git-send-email-levinsasha928@gmail.com> Content-Type: text/plain; charset="UTF-8" Date: Fri, 03 Aug 2012 20:00:51 +0200 Message-ID: <1344016851.9299.1415.camel@edumazet-glaptop> Mime-Version: 1.0 X-Mailer: Evolution 2.28.3 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Fri, 2012-08-03 at 16:23 +0200, Sasha Levin wrote: > 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 > --- > net/9p/error.c | 17 ++++++++--------- > 1 files changed, 8 insertions(+), 9 deletions(-) > > diff --git a/net/9p/error.c b/net/9p/error.c > index 2ab2de7..f1037db 100644 > --- a/net/9p/error.c > +++ b/net/9p/error.c > @@ -34,7 +34,7 @@ > #include > #include > #include > - > +#include > /** > * 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 ERRHASHSZ 5 This name is confusing, it should mention SHIFT or BITS maybe... > +DEFINE_STATIC_HASHTABLE(hash_errmap, ERRHASHSZ); > > /* FixMe - reduce to a reasonable size */ > static struct errormap errmap[] = { > @@ -196,15 +196,14 @@ int p9_error_init(void) > int bucket; remove "int bucket" and use : u32 hash; > > /* initialize hash table */ > - for (bucket = 0; bucket < ERRHASHSZ; bucket++) > - INIT_HLIST_HEAD(&hash_errmap[bucket]); > + hash_init(&hash_errmap, ERRHASHSZ); Why is hash_init() even needed ? If hash is "DEFINE_STATIC_HASHTABLE(...)", its already ready for use ! > > /* 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; > + bucket = jhash(c->name, c->namelen, 0); bucket is a wrong name here, its more like "key" or "hash" > INIT_HLIST_NODE(&c->list); > - hlist_add_head(&c->list, &hash_errmap[bucket]); > + hash_add(&hash_errmap, &c->list, bucket); > } > > return 1; > @@ -228,8 +227,8 @@ int p9_errstr2errno(char *errstr, int len) > errno = 0; > p = NULL; > c = NULL; > - bucket = jhash(errstr, len, 0) % ERRHASHSZ; > - hlist_for_each_entry(c, p, &hash_errmap[bucket], list) { > + bucket = jhash(errstr, len, 0); hash = jhash(errstr, len, 0); > + hash_for_each_possible(&hash_errmap, p, c, list, bucket) { > if (c->namelen == len && !memcmp(c->name, errstr, len)) { > errno = c->val; > break; From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753710Ab2HCVNz (ORCPT ); Fri, 3 Aug 2012 17:13:55 -0400 Received: from mail-we0-f174.google.com ([74.125.82.174]:52046 "EHLO mail-we0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753284Ab2HCVNy (ORCPT ); Fri, 3 Aug 2012 17:13:54 -0400 Message-ID: <501C3F2B.7080004@gmail.com> Date: Fri, 03 Aug 2012 23:14:19 +0200 From: Sasha Levin User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120730 Thunderbird/14.0 MIME-Version: 1.0 To: Eric Dumazet CC: torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 7/7] net,9p: use new hashtable implementation References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-8-git-send-email-levinsasha928@gmail.com> <1344016851.9299.1415.camel@edumazet-glaptop> In-Reply-To: <1344016851.9299.1415.camel@edumazet-glaptop> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/03/2012 08:00 PM, Eric Dumazet wrote: > On Fri, 2012-08-03 at 16:23 +0200, Sasha Levin wrote: >> /* initialize hash table */ >> - for (bucket = 0; bucket < ERRHASHSZ; bucket++) >> - INIT_HLIST_HEAD(&hash_errmap[bucket]); >> + hash_init(&hash_errmap, ERRHASHSZ); > > Why is hash_init() even needed ? > > If hash is "DEFINE_STATIC_HASHTABLE(...)", its already ready for use ! Indeed it is. I've removed it, and then decided to put it back since the definition of the hashtable isn't fully cooked yet, and I didn't want to miss this initialization point if it turn out we need to initialize that hashtable afterall. I will remove it once the hashtable definitions are clear. The rest of the review comments will be addressed. Thanks! From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753542Ab2HCVTf (ORCPT ); Fri, 3 Aug 2012 17:19:35 -0400 Received: from mail-we0-f174.google.com ([74.125.82.174]:36161 "EHLO mail-we0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752377Ab2HCVTb (ORCPT ); Fri, 3 Aug 2012 17:19:31 -0400 Message-ID: <501C407D.9080900@gmail.com> Date: Fri, 03 Aug 2012 23:19:57 +0200 From: Sasha Levin User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120730 Thunderbird/14.0 MIME-Version: 1.0 To: Tejun Heo CC: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> In-Reply-To: <20120803171515.GH15477@google.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/03/2012 07:15 PM, Tejun Heo wrote: > Hello, Sasha. > > On Fri, Aug 03, 2012 at 04:23:02PM +0200, Sasha Levin wrote: >> +#define DEFINE_STATIC_HASHTABLE(n, b) \ >> + static struct hash_table n = { .bits = (b), \ >> + .buckets = { [0 ... ((1 << (b)) - 1)] = HLIST_HEAD_INIT } } > > What does this "static" mean? > >> +#define DEFINE_HASHTABLE(n, b) \ >> + union { \ >> + struct hash_table n; \ >> + struct { \ >> + size_t bits; \ >> + struct hlist_head buckets[1 << (b)]; \ >> + } __##n ; \ >> + }; > > Is this supposed to be embedded in struct definition? If so, the name > is rather misleading as DEFINE_* is supposed to define and initialize > stand-alone constructs. Also, for struct members, simply putting hash > entries after struct hash_table should work. It would work, but I didn't want to just put them in the union since I feel it's safer to keep them in a separate struct so they won't be used by mistake, > Wouldn't using DEFINE_HASHTABLE() for the first macro and > DEFINE_HASHTABLE_MEMBER() for the latter be better? Indeed that sounds better, will fix. >> +#define HASH_BITS(name) ((name)->bits) >> +#define HASH_SIZE(name) (1 << (HASH_BITS(name))) >> + >> +__attribute__ ((unused)) > > Are we using __attribute__((unused)) for functions defined in headers > instead of static inline now? If so, why? > >> +static void hash_init(struct hash_table *ht, size_t bits) >> +{ >> + size_t i; > > I would prefer int here but no biggie. Just wondering, is there a particular reason behind it? >> + ht->bits = bits; >> + for (i = 0; i < (1 << bits); i++) >> + INIT_HLIST_HEAD(&ht->buckets[i]); >> +} >> + >> +static void hash_add(struct hash_table *ht, struct hlist_node *node, long key) >> +{ >> + hlist_add_head(node, >> + &ht->buckets[hash_long((unsigned long)key, HASH_BITS(ht))]); >> +} >> + >> + >> +#define hash_get(name, key, type, member, cmp_fn) \ >> +({ \ >> + struct hlist_node *__node; \ >> + typeof(key) __key = key; \ >> + type *__obj = NULL; \ >> + hlist_for_each_entry(__obj, __node, &(name)->buckets[ \ >> + hash_long((unsigned long) __key, \ >> + HASH_BITS(name))], member) \ >> + if (cmp_fn(__obj, __key)) \ >> + break; \ >> + __obj; \ >> +}) > > As opposed to using hash_for_each_possible(), how much difference does > this make? Is it really worthwhile? Most of the places I've switched to using this hashtable so far (4 out of 6) are using hash_get(). I think that the code looks cleaner when you an just provide a comparison function instead of implementing the iteration itself. I think hash_for_for_each_possible() is useful if the comparison condition is more complex than a simple comparison of one of the object members with the key - there's no need to force it on all the users. > > Thanks. > From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753599Ab2HCVaZ (ORCPT ); Fri, 3 Aug 2012 17:30:25 -0400 Received: from mail-pb0-f46.google.com ([209.85.160.46]:44759 "EHLO mail-pb0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752377Ab2HCVaW (ORCPT ); Fri, 3 Aug 2012 17:30:22 -0400 Date: Fri, 3 Aug 2012 14:30:17 -0700 From: Tejun Heo To: Sasha Levin Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120803213017.GK15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <501C407D.9080900@gmail.com> User-Agent: Mutt/1.5.20 (2009-06-14) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hello, On Fri, Aug 03, 2012 at 11:19:57PM +0200, Sasha Levin wrote: > > Is this supposed to be embedded in struct definition? If so, the name > > is rather misleading as DEFINE_* is supposed to define and initialize > > stand-alone constructs. Also, for struct members, simply putting hash > > entries after struct hash_table should work. > > It would work, but I didn't want to just put them in the union since > I feel it's safer to keep them in a separate struct so they won't be > used by mistake, Just use ugly enough pre/postfixes. If the user still accesses that, it's the user's fault. > >> +static void hash_init(struct hash_table *ht, size_t bits) > >> +{ > >> + size_t i; > > > > I would prefer int here but no biggie. > > Just wondering, is there a particular reason behind it? It isn't a size and using unsigned when signed suffices seems to cause more headache than helps anything usually due to lack of values to use for exceptional conditions (usually -errno or -1). > > As opposed to using hash_for_each_possible(), how much difference does > > this make? Is it really worthwhile? > > Most of the places I've switched to using this hashtable so far (4 > out of 6) are using hash_get(). I think that the code looks cleaner > when you an just provide a comparison function instead of > implementing the iteration itself. > > I think hash_for_for_each_possible() is useful if the comparison > condition is more complex than a simple comparison of one of the > object members with the key - there's no need to force it on all the > users. I don't know. What's the difference? In terms of LOC, it might even not save any thanks to the extra function definition, right? I don't think it's saving enough complexity to justify a separate rather unusual interface. Thanks. -- tejun From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753657Ab2HCVgY (ORCPT ); Fri, 3 Aug 2012 17:36:24 -0400 Received: from mail-wi0-f178.google.com ([209.85.212.178]:50126 "EHLO mail-wi0-f178.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753110Ab2HCVgW (ORCPT ); Fri, 3 Aug 2012 17:36:22 -0400 Message-ID: <501C4471.4090706@gmail.com> Date: Fri, 03 Aug 2012 23:36:49 +0200 From: Sasha Levin User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120730 Thunderbird/14.0 MIME-Version: 1.0 To: Tejun Heo CC: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> In-Reply-To: <20120803213017.GK15477@google.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/03/2012 11:30 PM, Tejun Heo wrote: >> I think hash_for_for_each_possible() is useful if the comparison >> > condition is more complex than a simple comparison of one of the >> > object members with the key - there's no need to force it on all the >> > users. > I don't know. What's the difference? In terms of LOC, it might even > not save any thanks to the extra function definition, right? I don't > think it's saving enough complexity to justify a separate rather > unusual interface. The function definition itself is just a macro, for example: #define MM_SLOTS_HASH_CMP(mm_slot, obj) ((mm_slot)->mm == (obj)) As an alternative, what do you think about simplifying that to be just a 'cond' instead of a function? Something like: hash_get(&mm_slots_hash, mm, struct mm_slot, hash, mm); In that case, the last param ("mm") will get unrolled to a condition like this: if ((obj)->mm == key) Which will be simple and easy for the user. The only reason I want to keep this interface is that most cases I've stumbled so far were easy short comparisons of a struct member with the key, and I don't want to make them more complex than they need to be. I probably will switch hash_get() to use hash_for_each_possible() as well, which will cut down on how hash_get() is a separate case. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753600Ab2HCVlL (ORCPT ); Fri, 3 Aug 2012 17:41:11 -0400 Received: from mail-wi0-f172.google.com ([209.85.212.172]:35031 "EHLO mail-wi0-f172.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753052Ab2HCVlJ (ORCPT ); Fri, 3 Aug 2012 17:41:09 -0400 Message-ID: <501C458E.7050000@gmail.com> Date: Fri, 03 Aug 2012 23:41:34 +0200 From: Sasha Levin User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120730 Thunderbird/14.0 MIME-Version: 1.0 To: Tejun Heo CC: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> In-Reply-To: <20120803213017.GK15477@google.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/03/2012 11:30 PM, Tejun Heo wrote: > Hello, > > On Fri, Aug 03, 2012 at 11:19:57PM +0200, Sasha Levin wrote: >>> Is this supposed to be embedded in struct definition? If so, the name >>> is rather misleading as DEFINE_* is supposed to define and initialize >>> stand-alone constructs. Also, for struct members, simply putting hash >>> entries after struct hash_table should work. >> >> It would work, but I didn't want to just put them in the union since >> I feel it's safer to keep them in a separate struct so they won't be >> used by mistake, > > Just use ugly enough pre/postfixes. If the user still accesses that, > it's the user's fault. I forgot to comment on that one, sorry. If we put hash entries after struct hash_table we don't take the bits field size into account, or did I miss something? From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753658Ab2HCVoX (ORCPT ); Fri, 3 Aug 2012 17:44:23 -0400 Received: from mail-pb0-f46.google.com ([209.85.160.46]:35588 "EHLO mail-pb0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753110Ab2HCVoT (ORCPT ); Fri, 3 Aug 2012 17:44:19 -0400 Date: Fri, 3 Aug 2012 14:44:14 -0700 From: Tejun Heo To: Sasha Levin Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120803214414.GL15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C4471.4090706@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <501C4471.4090706@gmail.com> User-Agent: Mutt/1.5.20 (2009-06-14) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hello, Sasha. On Fri, Aug 03, 2012 at 11:36:49PM +0200, Sasha Levin wrote: > On 08/03/2012 11:30 PM, Tejun Heo wrote: > The function definition itself is just a macro, for example: > > #define MM_SLOTS_HASH_CMP(mm_slot, obj) ((mm_slot)->mm == (obj)) It seems like it would make things more difficult to follow and error-prone. I'd definitely prefer just using functions. > As an alternative, what do you think about simplifying that to be > just a 'cond' instead of a function? Something like: > > hash_get(&mm_slots_hash, mm, struct mm_slot, hash, mm); > > In that case, the last param ("mm") will get unrolled to a condition like this: > > if ((obj)->mm == key) > > Which will be simple and easy for the user. It seems a bit too magical(tm) to me. ;) > The only reason I want to keep this interface is that most cases > I've stumbled so far were easy short comparisons of a struct member > with the key, and I don't want to make them more complex than they > need to be. I probably will switch hash_get() to use > hash_for_each_possible() as well, which will cut down on how > hash_get() is a separate case. I can understand that but I think the benefit we're talking about is a bit too miniscule to matter and to have two different interfaces. What do others think? Thanks. -- tejun From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753744Ab2HCVsO (ORCPT ); Fri, 3 Aug 2012 17:48:14 -0400 Received: from mail-pb0-f46.google.com ([209.85.160.46]:38494 "EHLO mail-pb0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753107Ab2HCVsL (ORCPT ); Fri, 3 Aug 2012 17:48:11 -0400 Date: Fri, 3 Aug 2012 14:48:06 -0700 From: Tejun Heo To: Sasha Levin Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120803214806.GM15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <501C458E.7050000@gmail.com> User-Agent: Mutt/1.5.20 (2009-06-14) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hello, On Fri, Aug 03, 2012 at 11:41:34PM +0200, Sasha Levin wrote: > I forgot to comment on that one, sorry. > > If we put hash entries after struct hash_table we don't take the > bits field size into account, or did I miss something? So, if you do the following, struct { struct { int i; long ar[]; } B; long __ar_storage[32]; } A; It should always be safe to dereference A.B.ar[31]. I'm not sure whether this is something guaranteed by C tho. Maybe compilers are allowed to put members in reverse order but I think we already depend on the above. Thanks. -- tejun From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753967Ab2HCWTj (ORCPT ); Fri, 3 Aug 2012 18:19:39 -0400 Received: from mail-bk0-f46.google.com ([209.85.214.46]:42230 "EHLO mail-bk0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753319Ab2HCWTg (ORCPT ); Fri, 3 Aug 2012 18:19:36 -0400 Message-ID: <501C4E92.1070801@gmail.com> Date: Sat, 04 Aug 2012 00:20:02 +0200 From: Sasha Levin User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120730 Thunderbird/14.0 MIME-Version: 1.0 To: Tejun Heo CC: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> In-Reply-To: <20120803214806.GM15477@google.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/03/2012 11:48 PM, Tejun Heo wrote: > Hello, > > On Fri, Aug 03, 2012 at 11:41:34PM +0200, Sasha Levin wrote: >> I forgot to comment on that one, sorry. >> >> If we put hash entries after struct hash_table we don't take the >> bits field size into account, or did I miss something? > > So, if you do the following, > > struct { > struct { > int i; > long ar[]; > } B; > long __ar_storage[32]; > } A; struct A should have been an union, right? > It should always be safe to dereference A.B.ar[31]. I'm not sure > whether this is something guaranteed by C tho. Maybe compilers are > allowed to put members in reverse order but I think we already depend > on the above. why is accessing A.B.ar[31] safe? __ar_storage is only 32*sizeof(long) bytes long, while struct B would need to be 32*sizeof(long) + sizeof(int) bytes long so that A.B.ar[31] access would be safe. > Thanks. > From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754002Ab2HCWXq (ORCPT ); Fri, 3 Aug 2012 18:23:46 -0400 Received: from mail-pb0-f46.google.com ([209.85.160.46]:40114 "EHLO mail-pb0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753839Ab2HCWXo (ORCPT ); Fri, 3 Aug 2012 18:23:44 -0400 Date: Fri, 3 Aug 2012 15:23:39 -0700 From: Tejun Heo To: Sasha Levin Cc: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120803222339.GN15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <501C4E92.1070801@gmail.com> User-Agent: Mutt/1.5.20 (2009-06-14) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hello, On Sat, Aug 04, 2012 at 12:20:02AM +0200, Sasha Levin wrote: > On 08/03/2012 11:48 PM, Tejun Heo wrote: > > On Fri, Aug 03, 2012 at 11:41:34PM +0200, Sasha Levin wrote: > >> I forgot to comment on that one, sorry. > >> > >> If we put hash entries after struct hash_table we don't take the > >> bits field size into account, or did I miss something? > > > > So, if you do the following, > > > > struct { > > struct { > > int i; > > long ar[]; > > } B; > > long __ar_storage[32]; > > } A; > > struct A should have been an union, right? I actually meant an enclosing struct. When you're defining a struct member, simply putting the storage after a struct with var array should be good enough. If that doesn't work, quite a few things in the kernel will break. Thanks. -- tejun From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754034Ab2HCWZw (ORCPT ); Fri, 3 Aug 2012 18:25:52 -0400 Received: from mail-bk0-f46.google.com ([209.85.214.46]:44847 "EHLO mail-bk0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753577Ab2HCWZs (ORCPT ); Fri, 3 Aug 2012 18:25:48 -0400 Message-ID: <501C5005.2090107@gmail.com> Date: Sat, 04 Aug 2012 00:26:13 +0200 From: Sasha Levin User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120730 Thunderbird/14.0 MIME-Version: 1.0 To: Tejun Heo CC: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> In-Reply-To: <20120803222339.GN15477@google.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/04/2012 12:23 AM, Tejun Heo wrote: > Hello, > > On Sat, Aug 04, 2012 at 12:20:02AM +0200, Sasha Levin wrote: >> On 08/03/2012 11:48 PM, Tejun Heo wrote: >>> On Fri, Aug 03, 2012 at 11:41:34PM +0200, Sasha Levin wrote: >>>> I forgot to comment on that one, sorry. >>>> >>>> If we put hash entries after struct hash_table we don't take the >>>> bits field size into account, or did I miss something? >>> >>> So, if you do the following, >>> >>> struct { >>> struct { >>> int i; >>> long ar[]; >>> } B; >>> long __ar_storage[32]; >>> } A; >> >> struct A should have been an union, right? > > I actually meant an enclosing struct. When you're defining a struct > member, simply putting the storage after a struct with var array > should be good enough. If that doesn't work, quite a few things in > the kernel will break. Ah, I see, I've missed that part. Thanks! > Thanks. > From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754007Ab2HCW3f (ORCPT ); Fri, 3 Aug 2012 18:29:35 -0400 Received: from mail-we0-f174.google.com ([74.125.82.174]:49873 "EHLO mail-we0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753541Ab2HCW3c (ORCPT ); Fri, 3 Aug 2012 18:29:32 -0400 MIME-Version: 1.0 In-Reply-To: <20120803222339.GN15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> From: Linus Torvalds Date: Fri, 3 Aug 2012 15:29:10 -0700 X-Google-Sender-Auth: S_cIE84LaFYc7wz-oS-Lx7-x3Qc Message-ID: Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable To: Tejun Heo Cc: Sasha Levin , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Content-Type: text/plain; charset=ISO-8859-1 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Fri, Aug 3, 2012 at 3:23 PM, Tejun Heo wrote: > > I actually meant an enclosing struct. When you're defining a struct > member, simply putting the storage after a struct with var array > should be good enough. If that doesn't work, quite a few things in > the kernel will break. The unsigned member of a struct has to be the last one, so your struct won't work. Linus From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754041Ab2HCWgs (ORCPT ); Fri, 3 Aug 2012 18:36:48 -0400 Received: from mail-pb0-f46.google.com ([209.85.160.46]:51957 "EHLO mail-pb0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753907Ab2HCWgj (ORCPT ); Fri, 3 Aug 2012 18:36:39 -0400 Date: Fri, 3 Aug 2012 15:36:34 -0700 From: Tejun Heo To: Linus Torvalds Cc: Sasha Levin , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120803223634.GO15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Fri, Aug 03, 2012 at 03:29:10PM -0700, Linus Torvalds wrote: > On Fri, Aug 3, 2012 at 3:23 PM, Tejun Heo wrote: > > > > I actually meant an enclosing struct. When you're defining a struct > > member, simply putting the storage after a struct with var array > > should be good enough. If that doesn't work, quite a few things in > > the kernel will break. > > The unsigned member of a struct has to be the last one, so your struct > won't work. I suppose you mean unsized. I remember this working. Maybe I'm confusing it with zero-sized array. Hmm... gcc doesn't complain about the following. --std=c99 seems happy too. #include struct A { int i; long ar[]; }; struct B { struct A a; long ar_storage[32]; }; int main(void) { printf("sizeof(A)=%zd sizeof(B)=%zd\n", sizeof(struct A), sizeof(struct B)); return 0; } $ ./a.out sizeof(A)=8 sizeof(B)=264 -- tejun From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754094Ab2HCXsL (ORCPT ); Fri, 3 Aug 2012 19:48:11 -0400 Received: from mail-we0-f174.google.com ([74.125.82.174]:58160 "EHLO mail-we0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754025Ab2HCXsJ (ORCPT ); Fri, 3 Aug 2012 19:48:09 -0400 MIME-Version: 1.0 In-Reply-To: <20120803223634.GO15477@google.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> <20120803223634.GO15477@google.com> From: Linus Torvalds Date: Fri, 3 Aug 2012 16:47:47 -0700 X-Google-Sender-Auth: WjhUl7UeqK1B_FBr2DwCYdtbGRw Message-ID: Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable To: Tejun Heo Cc: Sasha Levin , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Content-Type: text/plain; charset=ISO-8859-1 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Fri, Aug 3, 2012 at 3:36 PM, Tejun Heo wrote: > > I suppose you mean unsized. I remember this working. Maybe I'm > confusing it with zero-sized array. Hmm... gcc doesn't complain about > the following. --std=c99 seems happy too. Ok, I'm surprised, but maybe it's supposed to work if you do it inside another struct like that, exactly so that you can preallocate things.. Or maybe it's just a gcc bug. I do think this all is way hackier than Sasha's original simple code that didn't need these kinds of games, and didn't need a size member at all. I really think all the extra complexity and overhead is just *bad*. The first simple version was much nicer and likely generated better code too. Linus From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754102Ab2HDACv (ORCPT ); Fri, 3 Aug 2012 20:02:51 -0400 Received: from mail-bk0-f46.google.com ([209.85.214.46]:41946 "EHLO mail-bk0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754018Ab2HDACt (ORCPT ); Fri, 3 Aug 2012 20:02:49 -0400 Message-ID: <501C66C2.2020706@gmail.com> Date: Sat, 04 Aug 2012 02:03:14 +0200 From: Sasha Levin User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120730 Thunderbird/14.0 MIME-Version: 1.0 To: Linus Torvalds CC: Tejun Heo , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> <20120803223634.GO15477@google.com> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hi Linus, On 08/04/2012 01:47 AM, Linus Torvalds wrote: > Or maybe it's just a gcc bug. I do think this all is way hackier than > Sasha's original simple code that didn't need these kinds of games, > and didn't need a size member at all. > > I really think all the extra complexity and overhead is just *bad*. > The first simple version was much nicer and likely generated better > code too. The problem with that code was that it doesn't work with dynamically allocated hashtables, or hashtables that grow/shrink. The alternative to going down this path, is going back to the old code and saying that it only works for the simple case, and if you're interested in something more complex it should have it's own different implementation. Does it make sense? We'll keep the simple & common case simple, and let anyone who needs something more complex than this write it as an extension? From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754117Ab2HDAFi (ORCPT ); Fri, 3 Aug 2012 20:05:38 -0400 Received: from mail-pb0-f46.google.com ([209.85.160.46]:51043 "EHLO mail-pb0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753992Ab2HDAFg (ORCPT ); Fri, 3 Aug 2012 20:05:36 -0400 Date: Fri, 3 Aug 2012 17:05:31 -0700 From: Tejun Heo To: Linus Torvalds Cc: Sasha Levin , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable Message-ID: <20120804000531.GP15477@google.com> References: <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> <20120803223634.GO15477@google.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hello, On Fri, Aug 03, 2012 at 04:47:47PM -0700, Linus Torvalds wrote: > On Fri, Aug 3, 2012 at 3:36 PM, Tejun Heo wrote: > > > > I suppose you mean unsized. I remember this working. Maybe I'm > > confusing it with zero-sized array. Hmm... gcc doesn't complain about > > the following. --std=c99 seems happy too. > > Ok, I'm surprised, but maybe it's supposed to work if you do it inside > another struct like that, exactly so that you can preallocate things.. Yeah, I think the rule is var array should be the last member of any given struct definition. Once a struct is defined, its alignment and size are fixed and it behaves like any other struct. > Or maybe it's just a gcc bug. I do think this all is way hackier than > Sasha's original simple code that didn't need these kinds of games, > and didn't need a size member at all. > > I really think all the extra complexity and overhead is just *bad*. > The first simple version was much nicer and likely generated better > code too. The size member could have performance impact in extreme cases. If we're looking for something simple & fast, maybe just pass in @size as argument and be done with it? Thanks. -- tejun From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754149Ab2HDAGN (ORCPT ); Fri, 3 Aug 2012 20:06:13 -0400 Received: from mail-wi0-f172.google.com ([209.85.212.172]:34043 "EHLO mail-wi0-f172.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753992Ab2HDAGK (ORCPT ); Fri, 3 Aug 2012 20:06:10 -0400 MIME-Version: 1.0 In-Reply-To: <501C66C2.2020706@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> <20120803223634.GO15477@google.com> <501C66C2.2020706@gmail.com> From: Linus Torvalds Date: Fri, 3 Aug 2012 17:05:48 -0700 X-Google-Sender-Auth: o2BIsqanA7pfbEMxj1rkqGavU5k Message-ID: Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable To: Sasha Levin Cc: Tejun Heo , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Content-Type: text/plain; charset=ISO-8859-1 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Fri, Aug 3, 2012 at 5:03 PM, Sasha Levin wrote: > > The problem with that code was that it doesn't work with dynamically allocated hashtables, or hashtables that grow/shrink. Sure. But once you have that kind of complexity, why would you care about the trivial cases? Linus From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754132Ab2HDAcv (ORCPT ); Fri, 3 Aug 2012 20:32:51 -0400 Received: from mail-bk0-f46.google.com ([209.85.214.46]:33952 "EHLO mail-bk0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754037Ab2HDAcl (ORCPT ); Fri, 3 Aug 2012 20:32:41 -0400 Message-ID: <501C6DC3.90904@gmail.com> Date: Sat, 04 Aug 2012 02:33:07 +0200 From: Sasha Levin User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120730 Thunderbird/14.0 MIME-Version: 1.0 To: Linus Torvalds CC: Tejun Heo , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> <501C407D.9080900@gmail.com> <20120803213017.GK15477@google.com> <501C458E.7050000@gmail.com> <20120803214806.GM15477@google.com> <501C4E92.1070801@gmail.com> <20120803222339.GN15477@google.com> <20120803223634.GO15477@google.com> <501C66C2.2020706@gmail.com> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/04/2012 02:05 AM, Linus Torvalds wrote: > On Fri, Aug 3, 2012 at 5:03 PM, Sasha Levin wrote: >> >> The problem with that code was that it doesn't work with dynamically allocated hashtables, or hashtables that grow/shrink. > > Sure. But once you have that kind of complexity, why would you care > about the trivial cases? Because there are far more trivial cases than complex ones - I've counted 50+ of these "trivial" cases. None of them need the complexity we're trying to deal with at the moment. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754110Ab2HEAgm (ORCPT ); Sat, 4 Aug 2012 20:36:42 -0400 Received: from hrndva-omtalb.mail.rr.com ([71.74.56.122]:7553 "EHLO hrndva-omtalb.mail.rr.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752263Ab2HEAgi (ORCPT ); Sat, 4 Aug 2012 20:36:38 -0400 X-Authority-Analysis: v=2.0 cv=IOWA+3TG c=1 sm=0 a=s5Htg7xnQOKvHEu9STBOug==:17 a=OpT9cpI26MMA:10 a=PrZ6d8cNei4A:10 a=5SG0PmZfjMsA:10 a=Q9fys5e9bTEA:10 a=meVymXHHAAAA:8 a=ayC55rCoAAAA:8 a=pGLkceISAAAA:8 a=ZbNDx9BeURdUlYJOclgA:9 a=PUjeQqilurYA:10 a=E6k37eg1NvgA:10 a=MSl-tDqOz04A:10 a=s5Htg7xnQOKvHEu9STBOug==:117 X-Cloudmark-Score: 0 X-Originating-IP: 72.230.195.127 Message-ID: <1344126994.27983.116.camel@gandalf.stny.rr.com> Subject: Re: [RFC v2 6/7] tracepoint: use new hashtable implementation From: Steven Rostedt To: Sasha Levin Cc: torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Mathieu Desnoyers Date: Sat, 04 Aug 2012 20:36:34 -0400 In-Reply-To: <1344003788-1417-7-git-send-email-levinsasha928@gmail.com> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-7-git-send-email-levinsasha928@gmail.com> Content-Type: text/plain; charset="ISO-8859-15" X-Mailer: Evolution 3.4.3-1 Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org FYI, Mathieu is the author of this file. -- Steve On Fri, 2012-08-03 at 16:23 +0200, Sasha Levin wrote: > Switch tracepoints to use the new hashtable implementation. This reduces the amount of > generic unrelated code in the tracepoints. > > Signed-off-by: Sasha Levin > --- > kernel/tracepoint.c | 26 +++++++++----------------- > 1 files changed, 9 insertions(+), 17 deletions(-) > > diff --git a/kernel/tracepoint.c b/kernel/tracepoint.c > index d96ba22..b5a2650 100644 > --- a/kernel/tracepoint.c > +++ b/kernel/tracepoint.c > @@ -26,6 +26,7 @@ > #include > #include > #include > +#include > > 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]; > +DEFINE_STATIC_HASHTABLE(tracepoint_table, TRACEPOINT_HASH_BITS); > > /* > * Note about RCU : > @@ -191,16 +191,14 @@ 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, node, e, hlist, hash) > if (!strcmp(name, e->name)) > return e; > - } > + > return NULL; > } > > @@ -210,19 +208,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 +226,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 +236,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); > } > From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754129Ab2HEA65 (ORCPT ); Sat, 4 Aug 2012 20:58:57 -0400 Received: from out03.mta.xmission.com ([166.70.13.233]:56051 "EHLO out03.mta.xmission.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753954Ab2HEA6w (ORCPT ); Sat, 4 Aug 2012 20:58:52 -0400 From: ebiederm@xmission.com (Eric W. Biederman) To: Sasha Levin Cc: torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-3-git-send-email-levinsasha928@gmail.com> Date: Sat, 04 Aug 2012 17:58:32 -0700 In-Reply-To: <1344003788-1417-3-git-send-email-levinsasha928@gmail.com> (Sasha Levin's message of "Fri, 3 Aug 2012 16:23:03 +0200") Message-ID: <87pq76tarr.fsf@xmission.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.1 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-XM-SPF: eid=;;;mid=;;;hst=in02.mta.xmission.com;;;ip=98.207.153.68;;;frm=ebiederm@xmission.com;;;spf=neutral X-XM-AID: U2FsdGVkX1+bdFC9EB8n5pkoAxo8KHQYZ/edI2vwvq4= X-SA-Exim-Connect-IP: 98.207.153.68 X-SA-Exim-Mail-From: ebiederm@xmission.com X-Spam-Report: * -1.0 ALL_TRUSTED Passed through trusted hosts only via SMTP * 0.0 T_TM2_M_HEADER_IN_MSG BODY: T_TM2_M_HEADER_IN_MSG * -3.0 BAYES_00 BODY: Bayes spam probability is 0 to 1% * [score: 0.0063] * -0.0 DCC_CHECK_NEGATIVE Not listed in DCC * [sa07 1397; Body=1 Fuz1=1 Fuz2=1] * 0.0 T_TooManySym_01 4+ unique symbols in subject X-Spam-DCC: XMission; sa07 1397; Body=1 Fuz1=1 Fuz2=1 X-Spam-Combo: ;Sasha Levin X-Spam-Relay-Country: Subject: Re: [RFC v2 2/7] user_ns: use new hashtable implementation X-Spam-Flag: No X-SA-Exim-Version: 4.2.1 (built Fri, 06 Aug 2010 16:31:04 -0600) X-SA-Exim-Scanned: Yes (on in02.mta.xmission.com) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Sasha Levin writes: > Switch user_ns to use the new hashtable implementation. This reduces the amount of > generic unrelated code in user_ns. Just looking at this ick. - Your comparison function is broken. - The naming is awkward. hash_get without a reference count being incremented? - The magic is deep. hash_get is named like a function but takes a piece of code to call like only a macro can. - uid_hash_find always bumped the reference count but your uidhash_entry doesn't nor do all of the callers of uidhash_entry bump the reference count. Nacked-by: "Eric W. Biederman" I don't have the time for a new improved better hash table that makes the code buggier. Eric > Signed-off-by: Sasha Levin > --- > kernel/user.c | 53 ++++++++++++++++++----------------------------------- > 1 files changed, 18 insertions(+), 35 deletions(-) > > diff --git a/kernel/user.c b/kernel/user.c > index b815fef..555c71a 100644 > --- a/kernel/user.c > +++ b/kernel/user.c > @@ -16,6 +16,7 @@ > #include > #include > #include > +#include > > /* > * userns count is 1 for root user, 1 for init_uts_ns, > @@ -50,15 +51,14 @@ EXPORT_SYMBOL_GPL(init_user_ns); > * UID task count cache, to get fast user lookup in "alloc_uid" > * when changing user ID's (ie setuid() and friends). > */ > - > -#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)))) > +#define UIDHASH_BITS (CONFIG_BASE_SMALL ? 3 : 7) > +#define UIDHASH_CMP(obj, key) ((obj)->uid == (key)) > +#define uidhash_entry(key) (hash_get(&uidhash_table, key, \ > + struct user_struct, uidhash_node, \ > + UIDHASH_CMP)) > > static struct kmem_cache *uid_cachep; > -struct hlist_head uidhash_table[UIDHASH_SZ]; > +DEFINE_STATIC_HASHTABLE(uidhash_table, UIDHASH_BITS); > > /* > * The uidhash_lock is mostly taken from process context, but it is > @@ -84,29 +84,14 @@ 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, up->uid); > } > > static void uid_hash_remove(struct user_struct *up) > { > - hlist_del_init(&up->uidhash_node); > -} > - > -static struct user_struct *uid_hash_find(kuid_t uid, struct hlist_head *hashent) > -{ > - struct user_struct *user; > - struct hlist_node *h; > - > - hlist_for_each_entry(user, h, hashent, uidhash_node) { > - if (uid_eq(user->uid, uid)) { > - atomic_inc(&user->__count); > - return user; > - } > - } > - > - return NULL; > + hash_del(&up->uidhash_node); > } > > /* IRQs are disabled and uidhash_lock is held upon function entry. > @@ -135,7 +120,9 @@ 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 = uidhash_entry(uid); > + if (ret) > + atomic_inc(&ret->__count); > spin_unlock_irqrestore(&uidhash_lock, flags); > return ret; > } > @@ -156,11 +143,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 = uidhash_entry(uid); > spin_unlock_irq(&uidhash_lock); > > if (!up) { > @@ -176,13 +162,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 = uidhash_entry(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 +182,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, UIDHASH_BITS); > > /* 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; From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754723Ab2HEQlR (ORCPT ); Sun, 5 Aug 2012 12:41:17 -0400 Received: from mail.openrapids.net ([64.15.138.104]:49362 "EHLO blackscsi.openrapids.net" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1754175Ab2HEQlQ (ORCPT ); Sun, 5 Aug 2012 12:41:16 -0400 X-Greylist: delayed 598 seconds by postgrey-1.27 at vger.kernel.org; Sun, 05 Aug 2012 12:41:15 EDT Date: Sun, 5 Aug 2012 12:31:14 -0400 From: Mathieu Desnoyers To: Steven Rostedt Cc: Sasha Levin , torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 6/7] tracepoint: use new hashtable implementation Message-ID: <20120805163114.GA21768@Krystal> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-7-git-send-email-levinsasha928@gmail.com> <1344126994.27983.116.camel@gandalf.stny.rr.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1344126994.27983.116.camel@gandalf.stny.rr.com> X-Editor: vi X-Info: http://www.efficios.com User-Agent: Mutt/1.5.18 (2008-05-17) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org * Steven Rostedt (rostedt@goodmis.org) wrote: > FYI, Mathieu is the author of this file. > > -- Steve > > > On Fri, 2012-08-03 at 16:23 +0200, Sasha Levin wrote: > > Switch tracepoints to use the new hashtable implementation. This reduces the amount of > > generic unrelated code in the tracepoints. > > > > Signed-off-by: Sasha Levin > > --- > > kernel/tracepoint.c | 26 +++++++++----------------- > > 1 files changed, 9 insertions(+), 17 deletions(-) > > > > diff --git a/kernel/tracepoint.c b/kernel/tracepoint.c > > index d96ba22..b5a2650 100644 > > --- a/kernel/tracepoint.c > > +++ b/kernel/tracepoint.c > > @@ -26,6 +26,7 @@ > > #include > > #include > > #include > > +#include > > > > 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]; > > +DEFINE_STATIC_HASHTABLE(tracepoint_table, TRACEPOINT_HASH_BITS); I wonder why the "static" has been embedded within "DEFINE_STATIC_HASHTABLE" ? I'm used to see something similar to: static DEFINE_HASHTABLE(tracepoint_table, TRACEPOINT_HASH_BITS); elsewhere in the kernel (e.g. static DEFINE_PER_CPU(), static DEFINE_MUTEX(), etc). > > > > /* > > * Note about RCU : > > @@ -191,16 +191,14 @@ 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, node, e, hlist, hash) > > if (!strcmp(name, e->name)) > > return e; > > - } > > + Typically, where there are 2 or more nesting levels, I try to keep the outer brackets, even if the 1st level only contain a single statement (this is what I did across tracepoint.c). This is especially useful when nesting multiple if levels, and ensures the "else" clause match the right if. We might want to keep it that way within the file, to ensure style consistency. Other than that, it looks good! Thanks! Mathieu > > return NULL; > > } > > > > @@ -210,19 +208,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 +226,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 +236,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); > > } > > > > -- Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755104Ab2HERCe (ORCPT ); Sun, 5 Aug 2012 13:02:34 -0400 Received: from mail-ob0-f174.google.com ([209.85.214.174]:45292 "EHLO mail-ob0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755022Ab2HERCb (ORCPT ); Sun, 5 Aug 2012 13:02:31 -0400 Message-ID: <501EA749.9060400@gmail.com> Date: Sun, 05 Aug 2012 19:03:05 +0200 From: Sasha Levin User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120730 Thunderbird/14.0 MIME-Version: 1.0 To: Mathieu Desnoyers CC: Steven Rostedt , torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 6/7] tracepoint: use new hashtable implementation References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-7-git-send-email-levinsasha928@gmail.com> <1344126994.27983.116.camel@gandalf.stny.rr.com> <20120805163114.GA21768@Krystal> In-Reply-To: <20120805163114.GA21768@Krystal> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/05/2012 06:31 PM, Mathieu Desnoyers wrote: > * Steven Rostedt (rostedt@goodmis.org) wrote: >> FYI, Mathieu is the author of this file. >> >> -- Steve >> >> >> On Fri, 2012-08-03 at 16:23 +0200, Sasha Levin wrote: >>> Switch tracepoints to use the new hashtable implementation. This reduces the amount of >>> generic unrelated code in the tracepoints. >>> >>> Signed-off-by: Sasha Levin >>> --- >>> kernel/tracepoint.c | 26 +++++++++----------------- >>> 1 files changed, 9 insertions(+), 17 deletions(-) >>> >>> diff --git a/kernel/tracepoint.c b/kernel/tracepoint.c >>> index d96ba22..b5a2650 100644 >>> --- a/kernel/tracepoint.c >>> +++ b/kernel/tracepoint.c >>> @@ -26,6 +26,7 @@ >>> #include >>> #include >>> #include >>> +#include >>> >>> 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]; >>> +DEFINE_STATIC_HASHTABLE(tracepoint_table, TRACEPOINT_HASH_BITS); > > I wonder why the "static" has been embedded within > "DEFINE_STATIC_HASHTABLE" ? I'm used to see something similar to: > > static DEFINE_HASHTABLE(tracepoint_table, TRACEPOINT_HASH_BITS); > > elsewhere in the kernel (e.g. static DEFINE_PER_CPU(), static > DEFINE_MUTEX(), etc). We had to create two different definitions of hashtable, one to be used as static and one to be used in structs. I chose the uglier way of doing it, and Tejun already pointed it out :) It will be much nicer in the future. >>> >>> /* >>> * Note about RCU : >>> @@ -191,16 +191,14 @@ 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, node, e, hlist, hash) >>> if (!strcmp(name, e->name)) >>> return e; >>> - } >>> + > > Typically, where there are 2 or more nesting levels, I try to keep the > outer brackets, even if the 1st level only contain a single statement > (this is what I did across tracepoint.c). This is especially useful when > nesting multiple if levels, and ensures the "else" clause match the > right if. We might want to keep it that way within the file, to ensure > style consistency. Roger that, will fix. > Other than that, it looks good! > > Thanks! > > Mathieu > Thanks for the review Mathieu! From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754848Ab2HERND (ORCPT ); Sun, 5 Aug 2012 13:13:03 -0400 Received: from mail.openrapids.net ([64.15.138.104]:50530 "EHLO blackscsi.openrapids.net" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1754712Ab2HERNB convert rfc822-to-8bit (ORCPT ); Sun, 5 Aug 2012 13:13:01 -0400 Date: Sun, 5 Aug 2012 13:12:57 -0400 From: Mathieu Desnoyers To: Sasha Levin Cc: Steven Rostedt , torvalds@linux-foundation.org, tj@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org, Lai Jiangshan , "Paul E. McKenney" Subject: Re: [RFC v2 6/7] tracepoint: use new hashtable implementation Message-ID: <20120805171257.GB22267@Krystal> References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-7-git-send-email-levinsasha928@gmail.com> <1344126994.27983.116.camel@gandalf.stny.rr.com> <20120805163114.GA21768@Krystal> <501EA749.9060400@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: 8BIT In-Reply-To: <501EA749.9060400@gmail.com> X-Editor: vi X-Info: http://www.efficios.com User-Agent: Mutt/1.5.18 (2008-05-17) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org * Sasha Levin (levinsasha928@gmail.com) wrote: [...] > > Other than that, it looks good! > > > > Thanks! > > > > Mathieu > > > > Thanks for the review Mathieu! No problem! By the way, if you want to have a look at another hash table API for ideas, here is the RCU lock-free hash table API, within the Userspace RCU tree: from git://git.lttng.org/userspace-rcu.git branch: master API: urcu/rculfhash.h core code: rculfhash.c hash table index memory management: rculfhash-mm-chunk.c, rculfhash-mm-mmap.c, rculfhash-mm-order.c The git tree is down today due to electrical maintenance, so I am appending the hash table API below. #ifndef _URCU_RCULFHASH_H #define _URCU_RCULFHASH_H /* * urcu/rculfhash.h * * Userspace RCU library - Lock-Free RCU Hash Table * * Copyright 2011 - Mathieu Desnoyers * Copyright 2011 - Lai Jiangshan * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * * Include this file _after_ including your URCU flavor. */ #include #include #include #include #ifdef __cplusplus extern "C" { #endif /* * cds_lfht_node: Contains the next pointers and reverse-hash * value required for lookup and traversal of the hash table. * * struct cds_lfht_node should be aligned on 8-bytes boundaries because * the three lower bits are used as flags. It is worth noting that the * information contained within these three bits could be represented on * two bits by re-using the same bit for REMOVAL_OWNER_FLAG and * BUCKET_FLAG. This can be done if we ensure that no iterator nor * updater check the BUCKET_FLAG after it detects that the REMOVED_FLAG * is set. Given the minimum size of struct cds_lfht_node is 8 bytes on * 32-bit architectures, we choose to go for simplicity and reserve * three bits. * * struct cds_lfht_node can be embedded into a structure (as a field). * caa_container_of() can be used to get the structure from the struct * cds_lfht_node after a lookup. * * The structure which embeds it typically holds the key (or key-value * pair) of the object. The caller code is responsible for calculation * of the hash value for cds_lfht APIs. */ struct cds_lfht_node { struct cds_lfht_node *next; /* ptr | REMOVAL_OWNER_FLAG | BUCKET_FLAG | REMOVED_FLAG */ unsigned long reverse_hash; } __attribute__((aligned(8))); /* cds_lfht_iter: Used to track state while traversing a hash chain. */ struct cds_lfht_iter { struct cds_lfht_node *node, *next; }; static inline struct cds_lfht_node *cds_lfht_iter_get_node(struct cds_lfht_iter *iter) { return iter->node; } struct cds_lfht; /* * Caution ! * Ensure reader and writer threads are registered as urcu readers. */ typedef int (*cds_lfht_match_fct)(struct cds_lfht_node *node, const void *key); /* * cds_lfht_node_init - initialize a hash table node * @node: the node to initialize. * * This function is kept to be eventually used for debugging purposes * (detection of memory corruption). */ static inline void cds_lfht_node_init(struct cds_lfht_node *node) { } /* * Hash table creation flags. */ enum { CDS_LFHT_AUTO_RESIZE = (1U << 0), CDS_LFHT_ACCOUNTING = (1U << 1), }; struct cds_lfht_mm_type { struct cds_lfht *(*alloc_cds_lfht)(unsigned long min_nr_alloc_buckets, unsigned long max_nr_buckets); void (*alloc_bucket_table)(struct cds_lfht *ht, unsigned long order); void (*free_bucket_table)(struct cds_lfht *ht, unsigned long order); struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht, unsigned long index); }; extern const struct cds_lfht_mm_type cds_lfht_mm_order; extern const struct cds_lfht_mm_type cds_lfht_mm_chunk; extern const struct cds_lfht_mm_type cds_lfht_mm_mmap; /* * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly. */ struct cds_lfht *_cds_lfht_new(unsigned long init_size, unsigned long min_nr_alloc_buckets, unsigned long max_nr_buckets, int flags, const struct cds_lfht_mm_type *mm, const struct rcu_flavor_struct *flavor, pthread_attr_t *attr); /* * cds_lfht_new - allocate a hash table. * @init_size: number of buckets to allocate initially. Must be power of two. * @min_nr_alloc_buckets: the minimum number of allocated buckets. * (must be power of two) * @max_nr_buckets: the maximum number of hash table buckets allowed. * (must be power of two) * @flags: hash table creation flags (can be combined with bitwise or: '|'). * 0: no flags. * CDS_LFHT_AUTO_RESIZE: automatically resize hash table. * CDS_LFHT_ACCOUNTING: count the number of node addition * and removal in the table * @attr: optional resize worker thread attributes. NULL for default. * * Return NULL on error. * Note: the RCU flavor must be already included before the hash table header. * * The programmer is responsible for ensuring that resize operation has a * priority equal to hash table updater threads. It should be performed by * specifying the appropriate priority in the pthread "attr" argument, and, * for CDS_LFHT_AUTO_RESIZE, by ensuring that call_rcu worker threads also have * this priority level. Having lower priority for call_rcu and resize threads * does not pose any correctness issue, but the resize operations could be * starved by updates, thus leading to long hash table bucket chains. * Threads calling cds_lfht_new are NOT required to be registered RCU * read-side threads. It can be called very early. (e.g. before RCU is * initialized) */ static inline struct cds_lfht *cds_lfht_new(unsigned long init_size, unsigned long min_nr_alloc_buckets, unsigned long max_nr_buckets, int flags, pthread_attr_t *attr) { return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets, flags, NULL, &rcu_flavor, attr); } /* * cds_lfht_destroy - destroy a hash table. * @ht: the hash table to destroy. * @attr: (output) resize worker thread attributes, as received by cds_lfht_new. * The caller will typically want to free this pointer if dynamically * allocated. The attr point can be NULL if the caller does not * need to be informed of the value passed to cds_lfht_new(). * * Return 0 on success, negative error value on error. * Threads calling this API need to be registered RCU read-side threads. */ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr); /* * cds_lfht_count_nodes - count the number of nodes in the hash table. * @ht: the hash table. * @split_count_before: sample the node count split-counter before traversal. * @count: traverse the hash table, count the number of nodes observed. * @split_count_after: sample the node count split-counter after traversal. * * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. */ void cds_lfht_count_nodes(struct cds_lfht *ht, long *split_count_before, unsigned long *count, long *split_count_after); /* * cds_lfht_lookup - lookup a node by key. * @ht: the hash table. * @hash: the key hash. * @match: the key match function. * @key: the current node key. * @iter: node, if found (output). *iter->node set to NULL if not found. * * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * This function acts as a rcu_dereference() to read the node pointer. */ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash, cds_lfht_match_fct match, const void *key, struct cds_lfht_iter *iter); /* * cds_lfht_next_duplicate - get the next item with same key, after iterator. * @ht: the hash table. * @match: the key match function. * @key: the current node key. * @iter: input: current iterator. * output: node, if found. *iter->node set to NULL if not found. * * Uses an iterator initialized by a lookup or traversal. Important: the * iterator _needs_ to be initialized before calling * cds_lfht_next_duplicate. * Sets *iter-node to the following node with same key. * Sets *iter->node to NULL if no following node exists with same key. * RCU read-side lock must be held across cds_lfht_lookup and * cds_lfht_next calls, and also between cds_lfht_next calls using the * node returned by a previous cds_lfht_next. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * This function acts as a rcu_dereference() to read the node pointer. */ void cds_lfht_next_duplicate(struct cds_lfht *ht, cds_lfht_match_fct match, const void *key, struct cds_lfht_iter *iter); /* * cds_lfht_first - get the first node in the table. * @ht: the hash table. * @iter: First node, if exists (output). *iter->node set to NULL if not found. * * Output in "*iter". *iter->node set to NULL if table is empty. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * This function acts as a rcu_dereference() to read the node pointer. */ void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter); /* * cds_lfht_next - get the next node in the table. * @ht: the hash table. * @iter: input: current iterator. * output: next node, if exists. *iter->node set to NULL if not found. * * Input/Output in "*iter". *iter->node set to NULL if *iter was * pointing to the last table node. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * This function acts as a rcu_dereference() to read the node pointer. */ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter); /* * cds_lfht_add - add a node to the hash table. * @ht: the hash table. * @hash: the key hash. * @node: the node to add. * * This function supports adding redundant keys into the table. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * This function issues a full memory barrier before and after its * atomic commit. */ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash, struct cds_lfht_node *node); /* * cds_lfht_add_unique - add a node to hash table, if key is not present. * @ht: the hash table. * @hash: the node's hash. * @match: the key match function. * @key: the node's key. * @node: the node to try adding. * * Return the node added upon success. * Return the unique node already present upon failure. If * cds_lfht_add_unique fails, the node passed as parameter should be * freed by the caller. In this case, the caller does NOT need to wait * for a grace period before freeing the node. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * * The semantic of this function is that if only this function is used * to add keys into the table, no duplicated keys should ever be * observable in the table. The same guarantee apply for combination of * add_unique and add_replace (see below). * * Upon success, this function issues a full memory barrier before and * after its atomic commit. Upon failure, this function acts like a * simple lookup operation: it acts as a rcu_dereference() to read the * node pointer. The failure case does not guarantee any other memory * barrier. */ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht, unsigned long hash, cds_lfht_match_fct match, const void *key, struct cds_lfht_node *node); /* * cds_lfht_add_replace - replace or add a node within hash table. * @ht: the hash table. * @hash: the node's hash. * @match: the key match function. * @key: the node's key. * @node: the node to add. * * Return the node replaced upon success. If no node matching the key * was present, return NULL, which also means the operation succeeded. * This replacement operation should never fail. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * After successful replacement, a grace period must be waited for before * freeing the memory reserved for the returned node. * * The semantic of replacement vs lookups and traversals is the * following: if lookups and traversals are performed between a key * unique insertion and its removal, we guarantee that the lookups and * traversals will always find exactly one instance of the key if it is * replaced concurrently with the lookups. * * Providing this semantic allows us to ensure that replacement-only * schemes will never generate duplicated keys. It also allows us to * guarantee that a combination of add_replace and add_unique updates * will never generate duplicated keys. * * This function issues a full memory barrier before and after its * atomic commit. */ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht, unsigned long hash, cds_lfht_match_fct match, const void *key, struct cds_lfht_node *node); /* * cds_lfht_replace - replace a node pointed to by iter within hash table. * @ht: the hash table. * @old_iter: the iterator position of the node to replace. * @hash: the node's hash. * @match: the key match function. * @key: the node's key. * @new_node: the new node to use as replacement. * * Return 0 if replacement is successful, negative value otherwise. * Replacing a NULL old node or an already removed node will fail with * -ENOENT. * If the hash or value of the node to replace and the new node differ, * this function returns -EINVAL without proceeding to the replacement. * Old node can be looked up with cds_lfht_lookup and cds_lfht_next. * RCU read-side lock must be held between lookup and replacement. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * After successful replacement, a grace period must be waited for before * freeing the memory reserved for the old node (which can be accessed * with cds_lfht_iter_get_node). * * The semantic of replacement vs lookups is the same as * cds_lfht_add_replace(). * * Upon success, this function issues a full memory barrier before and * after its atomic commit. Upon failure, this function does not issue * any memory barrier. */ int cds_lfht_replace(struct cds_lfht *ht, struct cds_lfht_iter *old_iter, unsigned long hash, cds_lfht_match_fct match, const void *key, struct cds_lfht_node *new_node); /* * cds_lfht_del - remove node pointed to by iterator from hash table. * @ht: the hash table. * @node: the node to delete. * * Return 0 if the node is successfully removed, negative value * otherwise. * Deleting a NULL node or an already removed node will fail with a * negative value. * Node can be looked up with cds_lfht_lookup and cds_lfht_next, * followed by use of cds_lfht_iter_get_node. * RCU read-side lock must be held between lookup and removal. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * After successful removal, a grace period must be waited for before * freeing the memory reserved for old node (which can be accessed with * cds_lfht_iter_get_node). * Upon success, this function issues a full memory barrier before and * after its atomic commit. Upon failure, this function does not issue * any memory barrier. */ int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_node *node); /* * cds_lfht_is_node_deleted - query whether a node is removed from hash table. * * Return non-zero if the node is deleted from the hash table, 0 * otherwise. * Node can be looked up with cds_lfht_lookup and cds_lfht_next, * followed by use of cds_lfht_iter_get_node. * RCU read-side lock must be held between lookup and call to this * function. * Call with rcu_read_lock held. * Threads calling this API need to be registered RCU read-side threads. * This function does not issue any memory barrier. */ int cds_lfht_is_node_deleted(struct cds_lfht_node *node); /* * cds_lfht_resize - Force a hash table resize * @ht: the hash table. * @new_size: update to this hash table size. * * Threads calling this API need to be registered RCU read-side threads. * This function does not (necessarily) issue memory barriers. */ void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size); /* * Note: it is safe to perform element removal (del), replacement, or * any hash table update operation during any of the following hash * table traversals. * These functions act as rcu_dereference() to read the node pointers. */ #define cds_lfht_for_each(ht, iter, node) \ for (cds_lfht_first(ht, iter), \ node = cds_lfht_iter_get_node(iter); \ node != NULL; \ cds_lfht_next(ht, iter), \ node = cds_lfht_iter_get_node(iter)) #define cds_lfht_for_each_duplicate(ht, hash, match, key, iter, node) \ for (cds_lfht_lookup(ht, hash, match, key, iter), \ node = cds_lfht_iter_get_node(iter); \ node != NULL; \ cds_lfht_next_duplicate(ht, match, key, iter), \ node = cds_lfht_iter_get_node(iter)) #define cds_lfht_for_each_entry(ht, iter, pos, member) \ for (cds_lfht_first(ht, iter), \ pos = caa_container_of(cds_lfht_iter_get_node(iter), \ __typeof__(*(pos)), member); \ &(pos)->member != NULL; \ cds_lfht_next(ht, iter), \ pos = caa_container_of(cds_lfht_iter_get_node(iter), \ __typeof__(*(pos)), member)) #define cds_lfht_for_each_entry_duplicate(ht, hash, match, key, \ iter, pos, member) \ for (cds_lfht_lookup(ht, hash, match, key, iter), \ pos = caa_container_of(cds_lfht_iter_get_node(iter), \ __typeof__(*(pos)), member); \ &(pos)->member != NULL; \ cds_lfht_next_duplicate(ht, match, key, iter), \ pos = caa_container_of(cds_lfht_iter_get_node(iter), \ __typeof__(*(pos)), member)) #ifdef __cplusplus } #endif #endif /* _URCU_RCULFHASH_H */ -- Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com