[PATCH v2] mm,ksm: use new hashtable implementation

[PATCH v2] mm,ksm: use new hashtable implementation

[Sasha Levin]

From: Sasha Levin <levinsasha928@gmail.com>

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

This patch depends on d9b482c ("hashtable: introduce a small and naive
hashtable") which was merged in v3.6.

Acked-by: Hugh Dickins <hughd@google.com>
Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---

Change in v2:
 - Removed irrelevant newline.

 mm/ksm.c | 30 ++++++++++++------------------
 1 file changed, 12 insertions(+), 18 deletions(-)

diff --git a/mm/ksm.c b/mm/ksm.c
index e1f1f27..abbf7f1 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -33,7 +33,7 @@
 #include <linux/mmu_notifier.h>
 #include <linux/swap.h>
 #include <linux/ksm.h>
-#include <linux/hash.h>
+#include <linux/hashtable.h>
 #include <linux/freezer.h>
 #include <linux/oom.h>
 
@@ -156,9 +156,8 @@ struct rmap_item {
 static struct rb_root root_stable_tree = RB_ROOT;
 static struct rb_root root_unstable_tree = RB_ROOT;
 
-#define MM_SLOTS_HASH_SHIFT 10
-#define MM_SLOTS_HASH_HEADS (1 << MM_SLOTS_HASH_SHIFT)
-static struct hlist_head mm_slots_hash[MM_SLOTS_HASH_HEADS];
+#define MM_SLOTS_HASH_BITS 10
+static DEFINE_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_BITS);
 
 static struct mm_slot ksm_mm_head = {
 	.mm_list = LIST_HEAD_INIT(ksm_mm_head.mm_list),
@@ -275,26 +274,21 @@ static inline void free_mm_slot(struct mm_slot *mm_slot)
 
 static struct mm_slot *get_mm_slot(struct mm_struct *mm)
 {
-	struct mm_slot *mm_slot;
-	struct hlist_head *bucket;
 	struct hlist_node *node;
+	struct mm_slot *slot;
+
+	hash_for_each_possible(mm_slots_hash, slot, node, link, (unsigned long)mm) 
+		if (slot->mm == mm)
+			return slot;
 
-	bucket = &mm_slots_hash[hash_ptr(mm, MM_SLOTS_HASH_SHIFT)];
-	hlist_for_each_entry(mm_slot, node, bucket, link) {
-		if (mm == mm_slot->mm)
-			return mm_slot;
-	}
 	return NULL;
 }
 
 static void insert_to_mm_slots_hash(struct mm_struct *mm,
 				    struct mm_slot *mm_slot)
 {
-	struct hlist_head *bucket;
-
-	bucket = &mm_slots_hash[hash_ptr(mm, MM_SLOTS_HASH_SHIFT)];
 	mm_slot->mm = mm;
-	hlist_add_head(&mm_slot->link, bucket);
+	hash_add(mm_slots_hash, &mm_slot->link, (unsigned long)mm);
 }
 
 static inline int in_stable_tree(struct rmap_item *rmap_item)
@@ -647,7 +641,7 @@ static int unmerge_and_remove_all_rmap_items(void)
 		ksm_scan.mm_slot = list_entry(mm_slot->mm_list.next,
 						struct mm_slot, mm_list);
 		if (ksm_test_exit(mm)) {
-			hlist_del(&mm_slot->link);
+			hash_del(&mm_slot->link);
 			list_del(&mm_slot->mm_list);
 			spin_unlock(&ksm_mmlist_lock);
 
@@ -1392,7 +1386,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);
 
@@ -1559,7 +1553,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.8.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: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH v2] mm,ksm: use new hashtable implementation

[Andrew Morton]

On Fri, 21 Dec 2012 12:46:50 -0500
Sasha Levin <sasha.levin@oracle.com> wrote:

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

hm, include/linux/hashtable.h:hash_min() is rather dangerous - it
returns different values depending on the size of the first argument. 
So if the calling code mixes up its ints and longs (and boy we do that
a lot), the result will work on 32-bit and fail on 64-bit.

Also, is there ever likely to be a situation where the first arg to
hash_min() is *not* a pointer?  Perhaps it would be better to concede
to reality: rename `key' to `ptr' and remove all those typcasts you
just added.

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

Re: [PATCH v2] mm,ksm: use new hashtable implementation

[Sasha Levin]

On 12/21/2012 04:36 PM, Andrew Morton wrote:
> On Fri, 21 Dec 2012 12:46:50 -0500
> Sasha Levin <sasha.levin@oracle.com> wrote:
> 
>> Switch ksm to use the new hashtable implementation. This reduces the amount of
>> generic unrelated code in the ksm module.
> 
> hm, include/linux/hashtable.h:hash_min() is rather dangerous - it
> returns different values depending on the size of the first argument. 
> So if the calling code mixes up its ints and longs (and boy we do that
> a lot), the result will work on 32-bit and fail on 64-bit.

The reason for doing so is because hashing 32 bits is much faster than
hashing 64 bits.

I'd really prefer to fix the code the mixes up ints and longs instead
of removing optimizations. Not only because of the optimizations themselves
but because these mixups will be rather obvious with the hashtable as
opposed to all the other places that just misbehave silently.

> Also, is there ever likely to be a situation where the first arg to
> hash_min() is *not* a pointer?  Perhaps it would be better to concede
> to reality: rename `key' to `ptr' and remove all those typcasts you
> just added.

There actually are several. This is the reason for hash_min really - several
places that used 32bit keys would have been slowed down by switch to
hash_long(), which is why hash_min() was introduced.

The first places that come to mind are userns, 9p and tracepoints, I guess
there are a few more which I don't remember.


Thanks,
Sasha

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