linux-kernel - [RFC 4/6] zsmalloc: encode alloced mark in handle object

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Tue,  2 Dec 2014 11:49:45 +0900
From:	Minchan Kim <minchan@...nel.org>
To:	Andrew Morton <akpm@...ux-foundation.org>
Cc:	linux-kernel@...r.kernel.org, linux-mm@...ck.org,
	Nitin Gupta <ngupta@...are.org>,
	Dan Streetman <ddstreet@...e.org>,
	Seth Jennings <sjennings@...iantweb.net>,
	Sergey Senozhatsky <sergey.senozhatsky@...il.com>,
	Luigi Semenzato <semenzato@...gle.com>,
	Jerome Marchand <jmarchan@...hat.com>, juno.choi@....com,
	seungho1.park@....com, Minchan Kim <minchan@...nel.org>
Subject: [RFC 4/6] zsmalloc: encode alloced mark in handle object

For compaction, we need to look up using object in zspage
to migrate but there is no way to distinguish it from
free objects without walking all of free objects via
first_page->freelist, which would be haavy.

This patch encodes alloced mark in handle's least bit
so compaction can find it with small cost.

Signed-off-by: Minchan Kim <minchan@...nel.org>
---
 mm/zsmalloc.c | 35 +++++++++++++++++++++++------------
 1 file changed, 23 insertions(+), 12 deletions(-)

diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c
index 1eec2a539f77..16c40081c22e 100644
--- a/mm/zsmalloc.c
+++ b/mm/zsmalloc.c
@@ -133,7 +133,9 @@
 #endif
 #endif
 #define _PFN_BITS		(MAX_PHYSMEM_BITS - PAGE_SHIFT)
-#define OBJ_INDEX_BITS	(BITS_PER_LONG - _PFN_BITS)
+#define OBJ_ALLOCATED	1
+#define OBJ_ALLOC_BITS	1
+#define OBJ_INDEX_BITS	(BITS_PER_LONG - _PFN_BITS - OBJ_ALLOC_BITS)
 #define OBJ_INDEX_MASK	((_AC(1, UL) << OBJ_INDEX_BITS) - 1)
 
 #define MAX(a, b) ((a) >= (b) ? (a) : (b))
@@ -555,9 +557,6 @@ static struct page *get_next_page(struct page *page)
 
 /*
  * Encode <page, obj_idx> as a single handle value.
- * On hardware platforms with physical memory starting at 0x0 the pfn
- * could be 0 so we ensure that the handle will never be 0 by adjusting the
- * encoded obj_idx value before encoding.
  */
 static void *obj_location_to_handle(struct page *page, unsigned long obj_idx)
 {
@@ -568,22 +567,20 @@ static void *obj_location_to_handle(struct page *page, unsigned long obj_idx)
 		return NULL;
 	}
 
-	handle = page_to_pfn(page) << OBJ_INDEX_BITS;
-	handle |= ((obj_idx + 1) & OBJ_INDEX_MASK);
+	handle = page_to_pfn(page) << (OBJ_INDEX_BITS + OBJ_ALLOC_BITS);
+	handle |= (obj_idx & OBJ_INDEX_MASK) << OBJ_ALLOC_BITS;
 
 	return (void *)handle;
 }
 
 /*
- * Decode <page, obj_idx> pair from the given object handle. We adjust the
- * decoded obj_idx back to its original value since it was adjusted in
- * obj_location_to_handle().
+ * Decode <page, obj_idx> pair from the given object handle.
  */
 static void obj_to_location(unsigned long handle, struct page **page,
 				unsigned long *obj_idx)
 {
-	*page = pfn_to_page(handle >> OBJ_INDEX_BITS);
-	*obj_idx = (handle & OBJ_INDEX_MASK) - 1;
+	*page = pfn_to_page(handle >> (OBJ_INDEX_BITS + OBJ_ALLOC_BITS));
+	*obj_idx = ((handle >> OBJ_ALLOC_BITS) & OBJ_INDEX_MASK);
 }
 
 static unsigned long obj_idx_to_offset(struct page *page,
@@ -623,8 +620,21 @@ static unsigned long handle_to_obj(struct zs_pool *pool, unsigned long handle)
 
 static unsigned long alloc_handle(struct zs_pool *pool)
 {
-	return __zs_malloc(pool, pool->handle_class,
+	unsigned long handle;
+
+	handle = __zs_malloc(pool, pool->handle_class,
 			pool->flags & ~__GFP_HIGHMEM, 0);
+	/*
+	 * OBJ_ALLOCATED marks the object allocated tag so compaction
+	 * can identify it among free objects in zspage.
+	 * In addtion, on hardware platforms with physical memory
+	 * starting at 0x0 the pfn could be 0 so it ensure that the
+	 * handle will never be 0 which means fail of allocation now.
+	 */
+	if (likely(handle))
+		handle |= OBJ_ALLOCATED;
+
+	return handle;
 }
 
 static void free_handle(struct zs_pool *pool, unsigned long handle)
@@ -1259,6 +1269,7 @@ static void __zs_free(struct zs_pool *pool, struct size_class *class,
 	spin_lock(&class->lock);
 	/* Insert this object in containing zspage's freelist */
 	link = (struct link_free *)(vaddr + f_offset);
+	link->handle &= ~OBJ_ALLOCATED;
 	link->next = first_page->freelist;
 	first_page->freelist = (void *)handle;
 
-- 
2.0.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/