Skip to contentSkip to conversation

zsmalloc support compaction

RFC In review Minchan Kim 4 participants 15 messages Dec 2, 2014 – Dec 23, 2014

Subsystems (4)
Memory management Block layer zram Zsmalloc compressed slab memory allocator
lore
Share & tools
lore

Minchan Kim

author maintainer
#0 lore raw

cover zsmalloc support compaction

Recently, there was issue about zsmalloc fragmentation and I got a report from Juno that new fork failed although there are plenty of free pages in the system.
His investigation revealed zram is one of the culprit to make heavy fragmentation so there was no more contiguous 16K page for pgd to fork in the ARM.

This patchset implement *basic* zsmalloc compaction support and zram utilizes it so admin can do

	"echo 1 > /sys/block/zram0/compact"

Actually, ideal is that mm migrate code is aware of zram pages and migrate them out automatically without admin's manual opeartion when system is out of contiguous page. Howver, we need more thinking before adding more hooks to migrate.c. Even though we implement it, we need manual trigger mode, too so I hope we could enhance zram migration stuff based on this primitive functions in future.

I just tested it on only x86 so need more testing on other arches. Additionally, I should have a number for zsmalloc regression caused by indirect layering. Unfortunately, I don't have any ARM test machine on my desk. I will get it soon and test it. Anyway, before further work, I'd like to hear opinion.

Pathset is based on v3.18-rc6-mmotm-2014-11-26-15-45.

Thanks.

Minchan Kim (6):
zsmalloc: expand size class to support sizeof(unsigned long)
zsmalloc: add indrection layer to decouple handle from object
zsmalloc: implement reverse mapping
zsmalloc: encode alloced mark in handle object
zsmalloc: support compaction
zram: support compaction

 drivers/block/zram/zram_drv.c |  24 ++
 drivers/block/zram/zram_drv.h |   1 +
 include/linux/zsmalloc.h      |   1 +
 mm/zsmalloc.c                 | 596 +++++++++++++++++++++++++++++++++++++-----
 4 files changed, 552 insertions(+), 70 deletions(-)
Signature · 7 lines
2.0.0

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
author maintainer
#1 lore raw

RFC 1/6 zsmalloc: expand size class to support sizeof(unsigned long)

For compaction of zsmalloc, we need to decouple handle and obj position binding. For that, we need another memory to keep handle and I want to reuse existing functions of zsmalloc to implement indirect layer.

For that, we need to support new size class(ie, sizeof(unsigned long)) so this patch does it.

Signed-off-by Minchan Kim <[email protected]>
---
 mm/zsmalloc.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)
mm/zsmalloc.c +5 -4
index 2021df5eb891..a806d714924c 100644
@@ -100,7 +100,8 @@
  * span more than 1 page which avoids complex case of mapping 2 pages simply
  * to restore link_free pointer values.
  */
-#define ZS_ALIGN		8
+#define ZS_ALIGN		(sizeof(struct link_free))
+#define ZS_HANDLE_SIZE		(sizeof(unsigned long))
 
 /*
  * A single 'zspage' is composed of up to 2^N discontiguous 0-order (single)

@@ -138,11 +139,11 @@
 #define MAX(a, b) ((a) >= (b) ? (a) : (b))
 /* ZS_MIN_ALLOC_SIZE must be multiple of ZS_ALIGN */
 #define ZS_MIN_ALLOC_SIZE \
-	MAX(32, (ZS_MAX_PAGES_PER_ZSPAGE << PAGE_SHIFT >> OBJ_INDEX_BITS))
-#define ZS_MAX_ALLOC_SIZE	PAGE_SIZE
+	MAX(ZS_ALIGN, (ZS_MAX_PAGES_PER_ZSPAGE << PAGE_SHIFT >> OBJ_INDEX_BITS))
+#define ZS_MAX_ALLOC_SIZE	(PAGE_SIZE + ZS_HANDLE_SIZE)
 
 /*
- * On systems with 4K page size, this gives 255 size classes! There is a
+ * On systems with 4K page size, this gives 257 size classes! There is a
  * trader-off here:
  *  - Large number of size classes is potentially wasteful as free page are
  *    spread across these classes
Signature · 1 line
2.0.0
author maintainer
#2 lore raw

RFC 2/6 zsmalloc: add indrection layer to decouple handle from object

In reply to Minchan Kim

Currently, zram's handle encodes object's location directly so it makes hard to support migration/compaction.

This patch adds indirection layer for decoupling handle and object location. With it, we could prepare to support migration/ compaction to prevent fragment problem of zsmalloc. As well, it could make zram use movable pages in future.

First of all, we need indirection layer to assoicate handle with object so that this patch introduces logics to support the decoupling.

Old procedure of zsmalloc is as follows

* zs_malloc -> allocate object -> return object as handle because object itself is handle.
* zs_map_object -> get object's position from handle -> map pages
* zs_unmap_object -> get object's position from handle -> unmap pages
* zs_free -> free object because handle itself encodes object's location.

New behavior is as follows

* zsmalloc -> allocate handle -> allocate object -> assoicate handle with object -> return handle, not object.
* zs_map_object-> get object from handle via indiretion layer -> get object's position from object -> map pages
* zs_unmap_object-> get object from handle via indirection layer -> get object's position from object -> unmap pages
* zs_free -> get object from handle via indirection layer -> free handle -> free object

As drawback, it would increase overhead of allocator. Yet, it's not measured and might separate it with another config if it's heavy.

Signed-off-by Minchan Kim <[email protected]>
---
 mm/zsmalloc.c | 199 +++++++++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 157 insertions(+), 42 deletions(-)
mm/zsmalloc.c +157 -42
index a806d714924c..5f3f9119705e 100644
@@ -219,6 +219,7 @@ struct link_free {
 
 struct zs_pool {
 	struct size_class **size_class;
+	struct size_class *handle_class;
 
 	gfp_t flags;	/* allocation flags used when growing pool */
 	atomic_long_t pages_allocated;

@@ -243,6 +244,11 @@ struct mapping_area {
 	enum zs_mapmode vm_mm; /* mapping mode */
 };
 
+static unsigned long __zs_malloc(struct zs_pool *pool,
+			struct size_class *class, gfp_t flags);
+static void __zs_free(struct zs_pool *pool, struct size_class *class,
+			unsigned long handle);
+
 /* zpool driver */
 
 #ifdef CONFIG_ZPOOL

@@ -458,11 +464,10 @@ static void remove_zspage(struct page *page, struct size_class *class,
  * page from the freelist of the old fullness group to that of the new
  * fullness group.
  */
-static enum fullness_group fix_fullness_group(struct zs_pool *pool,
-						struct page *page)
+static enum fullness_group fix_fullness_group(struct size_class *class,
+					struct page *page)
 {
 	int class_idx;
-	struct size_class *class;
 	enum fullness_group currfg, newfg;
 
 	BUG_ON(!is_first_page(page));

@@ -472,7 +477,6 @@ static enum fullness_group fix_fullness_group(struct zs_pool *pool,
 	if (newfg == currfg)
 		goto out;
 
-	class = pool->size_class[class_idx];
 	remove_zspage(page, class, currfg);
 	insert_zspage(page, class, newfg);
 	set_zspage_mapping(page, class_idx, newfg);

@@ -569,7 +573,7 @@ static void *obj_location_to_handle(struct page *page, unsigned long obj_idx)
  * decoded obj_idx back to its original value since it was adjusted in
  * obj_location_to_handle().
  */
-static void obj_handle_to_location(unsigned long handle, struct page **page,
+static void obj_to_location(unsigned long handle, struct page **page,
 				unsigned long *obj_idx)
 {
 	*page = pfn_to_page(handle >> OBJ_INDEX_BITS);

@@ -587,6 +591,41 @@ static unsigned long obj_idx_to_offset(struct page *page,
 	return off + obj_idx * class_size;
 }
 
+static void *handle_to_addr(struct zs_pool *pool, unsigned long handle)
+{
+	struct page *page;
+	unsigned long obj_idx, off;
+	struct size_class *class;
+
+	obj_to_location(handle, &page, &obj_idx);
+	class = pool->handle_class;
+	off = obj_idx_to_offset(page, obj_idx, class->size);
+
+	return lowmem_page_address(page) + off;
+}
+
+static unsigned long handle_to_obj(struct zs_pool *pool, unsigned long handle)
+{
+	unsigned long obj;
+	unsigned long *h_addr;
+
+	h_addr = handle_to_addr(pool, handle);
+	obj = *h_addr;
+
+	return obj;
+}
+
+static unsigned long alloc_handle(struct zs_pool *pool)
+{
+	return __zs_malloc(pool, pool->handle_class,
+			pool->flags & ~__GFP_HIGHMEM);
+}
+
+static void free_handle(struct zs_pool *pool, unsigned long handle)
+{
+	__zs_free(pool, pool->handle_class, handle);
+}
+
 static void reset_page(struct page *page)
 {
 	clear_bit(PG_private, &page->flags);

@@ -968,6 +1007,24 @@ static bool can_merge(struct size_class *prev, int size, int pages_per_zspage)
 	return true;
 }
 
+static int create_handle_class(struct zs_pool *pool, int handle_size)
+{
+	struct size_class *class;
+
+	class = kzalloc(sizeof(struct size_class), GFP_KERNEL);
+	if (!class)
+		return -ENOMEM;
+
+	class->index = 0;
+	class->size = handle_size;
+	class->pages_per_zspage = 1;
+	BUG_ON(class->pages_per_zspage != get_pages_per_zspage(handle_size));
+	spin_lock_init(&class->lock);
+	pool->handle_class = class;
+
+	return 0;
+}
+
 /**
  * zs_create_pool - Creates an allocation pool to work from.
  * @flags: allocation flags used to allocate pool metadata

@@ -989,12 +1046,13 @@ struct zs_pool *zs_create_pool(gfp_t flags)
 	if (!pool)
 		return NULL;
 
+	if (create_handle_class(pool, ZS_HANDLE_SIZE))
+		goto err;
+
 	pool->size_class = kcalloc(zs_size_classes, sizeof(struct size_class *),
 			GFP_KERNEL);
-	if (!pool->size_class) {
-		kfree(pool);
-		return NULL;
-	}
+	if (!pool->size_class)
+		goto err;
 
 	/*
 	 * Iterate reversly, because, size of size_class that we want to use

@@ -1053,6 +1111,8 @@ void zs_destroy_pool(struct zs_pool *pool)
 {
 	int i;
 
+	kfree(pool->handle_class);
+
 	for (i = 0; i < zs_size_classes; i++) {
 		int fg;
 		struct size_class *class = pool->size_class[i];

@@ -1077,36 +1137,21 @@ void zs_destroy_pool(struct zs_pool *pool)
 }
 EXPORT_SYMBOL_GPL(zs_destroy_pool);
 
-/**
- * zs_malloc - Allocate block of given size from pool.
- * @pool: pool to allocate from
- * @size: size of block to allocate
- *
- * On success, handle to the allocated object is returned,
- * otherwise 0.
- * Allocation requests with size > ZS_MAX_ALLOC_SIZE will fail.
- */
-unsigned long zs_malloc(struct zs_pool *pool, size_t size)
+static unsigned long __zs_malloc(struct zs_pool *pool,
+			struct size_class *class, gfp_t flags)
 {
 	unsigned long obj;
 	struct link_free *link;
-	struct size_class *class;
-	void *vaddr;
-
 	struct page *first_page, *m_page;
 	unsigned long m_objidx, m_offset;
-
-	if (unlikely(!size || size > ZS_MAX_ALLOC_SIZE))
-		return 0;
-
-	class = pool->size_class[get_size_class_index(size)];
+	void *vaddr;
 
 	spin_lock(&class->lock);
 	first_page = find_get_zspage(class);
 
 	if (!first_page) {
 		spin_unlock(&class->lock);
-		first_page = alloc_zspage(class, pool->flags);
+		first_page = alloc_zspage(class, flags);
 		if (unlikely(!first_page))
 			return 0;
 

@@ -1117,7 +1162,7 @@ unsigned long zs_malloc(struct zs_pool *pool, size_t size)
 	}
 
 	obj = (unsigned long)first_page->freelist;
-	obj_handle_to_location(obj, &m_page, &m_objidx);
+	obj_to_location(obj, &m_page, &m_objidx);
 	m_offset = obj_idx_to_offset(m_page, m_objidx, class->size);
 
 	vaddr = kmap_atomic(m_page);

@@ -1128,14 +1173,54 @@ unsigned long zs_malloc(struct zs_pool *pool, size_t size)
 
 	first_page->inuse++;
 	/* Now move the zspage to another fullness group, if required */
-	fix_fullness_group(pool, first_page);
+	fix_fullness_group(class, first_page);
 	spin_unlock(&class->lock);
 
 	return obj;
 }
+
+/**
+ * zs_malloc - Allocate block of given size from pool.
+ * @pool: pool to allocate from
+ * @size: size of block to allocate
+ *
+ * On success, handle to the allocated object is returned,
+ * otherwise 0.
+ * Allocation requests with size > ZS_MAX_ALLOC_SIZE will fail.
+ */
+unsigned long zs_malloc(struct zs_pool *pool, size_t size)
+{
+	unsigned long obj, handle;
+	struct size_class *class;
+	unsigned long *h_addr;
+
+	if (unlikely(!size || size > ZS_MAX_ALLOC_SIZE))
+		return 0;
+
+	/* allocate handle */
+	handle = alloc_handle(pool);
+	if (!handle)
+		goto out;
+
+	/* allocate obj */
+	class = pool->size_class[get_size_class_index(size)];
+	obj = __zs_malloc(pool, class, pool->flags);
+	if (!obj) {
+		__zs_free(pool, pool->handle_class, handle);
+		handle = 0;
+		goto out;
+	}
+
+	/* associate handle with obj */
+	h_addr = handle_to_addr(pool, handle);
+	*h_addr = obj;
+out:
+	return handle;
+}
 EXPORT_SYMBOL_GPL(zs_malloc);
 
-void zs_free(struct zs_pool *pool, unsigned long obj)
+static void __zs_free(struct zs_pool *pool, struct size_class *class,
+			unsigned long handle)
 {
 	struct link_free *link;
 	struct page *first_page, *f_page;

@@ -1143,38 +1228,64 @@ void zs_free(struct zs_pool *pool, unsigned long obj)
 	void *vaddr;
 
 	int class_idx;
-	struct size_class *class;
 	enum fullness_group fullness;
 
-	if (unlikely(!obj))
+	if (unlikely(!handle))
 		return;
 
-	obj_handle_to_location(obj, &f_page, &f_objidx);
+	obj_to_location(handle, &f_page, &f_objidx);
 	first_page = get_first_page(f_page);
 
 	get_zspage_mapping(first_page, &class_idx, &fullness);
-	class = pool->size_class[class_idx];
 	f_offset = obj_idx_to_offset(f_page, f_objidx, class->size);
 
-	spin_lock(&class->lock);
+	vaddr = kmap_atomic(f_page);
 
+	spin_lock(&class->lock);
 	/* Insert this object in containing zspage's freelist */
-	vaddr = kmap_atomic(f_page);
 	link = (struct link_free *)(vaddr + f_offset);
 	link->next = first_page->freelist;
-	kunmap_atomic(vaddr);
-	first_page->freelist = (void *)obj;
+	first_page->freelist = (void *)handle;
 
 	first_page->inuse--;
-	fullness = fix_fullness_group(pool, first_page);
+	fullness = fix_fullness_group(class, first_page);
 	spin_unlock(&class->lock);
 
+	kunmap_atomic(vaddr);
+
 	if (fullness == ZS_EMPTY) {
 		atomic_long_sub(class->pages_per_zspage,
 				&pool->pages_allocated);
 		free_zspage(first_page);
 	}
 }
+
+void zs_free(struct zs_pool *pool, unsigned long handle)
+{
+	unsigned long obj;
+	struct page *first_page, *f_page;
+	unsigned long f_objidx;
+
+	int class_idx;
+	struct size_class *class;
+	enum fullness_group fullness;
+
+	if (unlikely(!handle))
+		return;
+
+	obj = handle_to_obj(pool, handle);
+	/* free handle */
+	free_handle(pool, handle);
+
+	/* free obj */
+	obj_to_location(obj, &f_page, &f_objidx);
+	first_page = get_first_page(f_page);
+
+	get_zspage_mapping(first_page, &class_idx, &fullness);
+	class = pool->size_class[class_idx];
+
+	__zs_free(pool, class, obj);
+}
 EXPORT_SYMBOL_GPL(zs_free);
 
 /**

@@ -1195,6 +1306,7 @@ void *zs_map_object(struct zs_pool *pool, unsigned long handle,
 			enum zs_mapmode mm)
 {
 	struct page *page;
+	unsigned long obj;
 	unsigned long obj_idx, off;
 
 	unsigned int class_idx;

@@ -1212,7 +1324,8 @@ void *zs_map_object(struct zs_pool *pool, unsigned long handle,
 	 */
 	BUG_ON(in_interrupt());
 
-	obj_handle_to_location(handle, &page, &obj_idx);
+	obj = handle_to_obj(pool, handle);
+	obj_to_location(obj, &page, &obj_idx);
 	get_zspage_mapping(get_first_page(page), &class_idx, &fg);
 	class = pool->size_class[class_idx];
 	off = obj_idx_to_offset(page, obj_idx, class->size);

@@ -1237,6 +1350,7 @@ EXPORT_SYMBOL_GPL(zs_map_object);
 void zs_unmap_object(struct zs_pool *pool, unsigned long handle)
 {
 	struct page *page;
+	unsigned long obj;
 	unsigned long obj_idx, off;
 
 	unsigned int class_idx;

@@ -1246,7 +1360,8 @@ void zs_unmap_object(struct zs_pool *pool, unsigned long handle)
 
 	BUG_ON(!handle);
 
-	obj_handle_to_location(handle, &page, &obj_idx);
+	obj = handle_to_obj(pool, handle);
+	obj_to_location(obj, &page, &obj_idx);
 	get_zspage_mapping(get_first_page(page), &class_idx, &fg);
 	class = pool->size_class[class_idx];
 	off = obj_idx_to_offset(page, obj_idx, class->size);
Signature · 7 lines
2.0.0

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
author maintainer
#3 lore raw

RFC 3/6 zsmalloc: implement reverse mapping

In reply to Minchan Kim

This patch supports reverse mapping which gets handle from object. For keeping handle per object, it allocates ZS_HANDLE_SIZE greater than size user requested and stores handle in there. IOW, *(mapped address by zs_map_object - ZS_HANDLE_SIZE) == handle.

Signed-off-by Minchan Kim <[email protected]>
---
 mm/zsmalloc.c | 55 +++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 35 insertions(+), 20 deletions(-)
mm/zsmalloc.c +35 -20
index 5f3f9119705e..1eec2a539f77 100644
@@ -213,8 +213,12 @@ struct size_class {
  * This must be power of 2 and less than or equal to ZS_ALIGN
  */
 struct link_free {
-	/* Handle of next free chunk (encodes <PFN, obj_idx>) */
-	void *next;
+	union {
+		/* Handle of next free chunk (encodes <PFN, obj_idx>) */
+		void *next;
+		/* Handle of object allocated to user */
+		unsigned long handle;
+	};
 };
 
 struct zs_pool {

@@ -245,7 +249,9 @@ struct mapping_area {
 };
 
 static unsigned long __zs_malloc(struct zs_pool *pool,
-			struct size_class *class, gfp_t flags);
+			struct size_class *class, gfp_t flags,
+			unsigned long handle);
+
 static void __zs_free(struct zs_pool *pool, struct size_class *class,
 			unsigned long handle);
 

@@ -618,7 +624,7 @@ 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,
-			pool->flags & ~__GFP_HIGHMEM);
+			pool->flags & ~__GFP_HIGHMEM, 0);
 }
 
 static void free_handle(struct zs_pool *pool, unsigned long handle)

@@ -873,18 +879,22 @@ static void __zs_unmap_object(struct mapping_area *area,
 {
 	int sizes[2];
 	void *addr;
-	char *buf = area->vm_buf;
+	char *buf;
 
 	/* no write fastpath */
 	if (area->vm_mm == ZS_MM_RO)
 		goto out;
 
-	sizes[0] = PAGE_SIZE - off;
+	/* We shouldn't overwrite handle */
+	buf = area->vm_buf + ZS_HANDLE_SIZE;
+	size -= ZS_HANDLE_SIZE;
+
+	sizes[0] = PAGE_SIZE - off - ZS_HANDLE_SIZE;
 	sizes[1] = size - sizes[0];
 
 	/* copy per-cpu buffer to object */
 	addr = kmap_atomic(pages[0]);
-	memcpy(addr + off, buf, sizes[0]);
+	memcpy(addr + off + ZS_HANDLE_SIZE, buf, sizes[0]);
 	kunmap_atomic(addr);
 	addr = kmap_atomic(pages[1]);
 	memcpy(addr, buf + sizes[0], sizes[1]);

@@ -1138,7 +1148,7 @@ void zs_destroy_pool(struct zs_pool *pool)
 EXPORT_SYMBOL_GPL(zs_destroy_pool);
 
 static unsigned long __zs_malloc(struct zs_pool *pool,
-			struct size_class *class, gfp_t flags)
+		struct size_class *class, gfp_t flags, unsigned long handle)
 {
 	unsigned long obj;
 	struct link_free *link;

@@ -1168,10 +1178,19 @@ static unsigned long __zs_malloc(struct zs_pool *pool,
 	vaddr = kmap_atomic(m_page);
 	link = (struct link_free *)vaddr + m_offset / sizeof(*link);
 	first_page->freelist = link->next;
-	memset(link, POISON_INUSE, sizeof(*link));
+	link->handle = handle;
 	kunmap_atomic(vaddr);
 
 	first_page->inuse++;
+
+	if (handle) {
+		unsigned long *h_addr;
+
+		/* associate handle with obj */
+		h_addr = handle_to_addr(pool, handle);
+		*h_addr = obj;
+	}
+
 	/* Now move the zspage to another fullness group, if required */
 	fix_fullness_group(class, first_page);
 	spin_unlock(&class->lock);

@@ -1192,9 +1211,8 @@ unsigned long zs_malloc(struct zs_pool *pool, size_t size)
 {
 	unsigned long obj, handle;
 	struct size_class *class;
-	unsigned long *h_addr;
 
-	if (unlikely(!size || size > ZS_MAX_ALLOC_SIZE))
+	if (unlikely(!size || (size + ZS_HANDLE_SIZE) > ZS_MAX_ALLOC_SIZE))
 		return 0;
 
 	/* allocate handle */

@@ -1202,18 +1220,15 @@ unsigned long zs_malloc(struct zs_pool *pool, size_t size)
 	if (!handle)
 		goto out;
 
-	/* allocate obj */
+	/* allocate obj and associate it with handle */
+	size += ZS_HANDLE_SIZE;
 	class = pool->size_class[get_size_class_index(size)];
-	obj = __zs_malloc(pool, class, pool->flags);
+	obj = __zs_malloc(pool, class, pool->flags, handle);
 	if (!obj) {
-		__zs_free(pool, pool->handle_class, handle);
+		free_handle(pool, handle);
 		handle = 0;
 		goto out;
 	}
-
-	/* associate handle with obj */
-	h_addr = handle_to_addr(pool, handle);
-	*h_addr = obj;
 out:
 	return handle;
 }

@@ -1335,7 +1350,7 @@ void *zs_map_object(struct zs_pool *pool, unsigned long handle,
 	if (off + class->size <= PAGE_SIZE) {
 		/* this object is contained entirely within a page */
 		area->vm_addr = kmap_atomic(page);
-		return area->vm_addr + off;
+		return area->vm_addr + off + ZS_HANDLE_SIZE;
 	}
 
 	/* this object spans two pages */

@@ -1343,7 +1358,7 @@ void *zs_map_object(struct zs_pool *pool, unsigned long handle,
 	pages[1] = get_next_page(page);
 	BUG_ON(!pages[1]);
 
-	return __zs_map_object(area, pages, off, class->size);
+	return __zs_map_object(area, pages, off, class->size) + ZS_HANDLE_SIZE;
 }
 EXPORT_SYMBOL_GPL(zs_map_object);
Signature · 7 lines
2.0.0

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
author maintainer
#4 lore raw

RFC 4/6 zsmalloc: encode alloced mark in handle object

In reply to Minchan Kim

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 <[email protected]>
---
 mm/zsmalloc.c | 35 +++++++++++++++++++++++------------
 1 file changed, 23 insertions(+), 12 deletions(-)
mm/zsmalloc.c +23 -12
index 1eec2a539f77..16c40081c22e 100644
@@ -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;
Signature · 7 lines
2.0.0

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
author maintainer
#5 lore raw

RFC 5/6 zsmalloc: support compaction

In reply to Minchan Kim

This patch enables zsmalloc compaction so that user can use it via calling zs_compact(pool).

The migration policy is as follows,

1. find migration target objects in ZS_ALMOST_EMPTY
2. find free space in ZS_ALMOST_FULL. With no found, find it in ZS_ALMOST_EMPTY.
3. migrate objects get by 1 to free spaces get by 2
4. repeat [1-3] on each size class

Signed-off-by Minchan Kim <[email protected]>
---
 include/linux/zsmalloc.h |   1 +
 mm/zsmalloc.c            | 344 ++++++++++++++++++++++++++++++++++++++++++++---
 2 files changed, 330 insertions(+), 15 deletions(-)
include/linux/zsmalloc.h +1 -0
index 05c214760977..04ecd3fc4283 100644
@@ -47,5 +47,6 @@ void *zs_map_object(struct zs_pool *pool, unsigned long handle,
 void zs_unmap_object(struct zs_pool *pool, unsigned long handle);
 
 unsigned long zs_get_total_pages(struct zs_pool *pool);
+unsigned long zs_compact(struct zs_pool *pool);
 
 #endif
mm/zsmalloc.c +329 -15

430 lines not on this page · raw message

Signature · 7 lines
2.0.0

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
author maintainer
#6 lore raw

RFC 6/6 zram: support compaction

In reply to Minchan Kim

Now that zsmalloc supports compaction, zram can use it. For the first step, this patch exports compact knob via sysfs so user can do compaction via "echo 1 > /sys/block/zram0/compact".

Maybe, we need another knob to trigger compaction automatically once the amount of fragment is higher than the ratio.

echo "fragment_ratio" > /sys/block/zram0/compact_based_on_the_ratio

Signed-off-by Minchan Kim <[email protected]>
---
 drivers/block/zram/zram_drv.c | 24 ++++++++++++++++++++++++
 drivers/block/zram/zram_drv.h |  1 +
 2 files changed, 25 insertions(+)
drivers/block/zram/zram_drv.c +24 -0
index 976eab6f35b9..53c110b289fc 100644
@@ -247,6 +247,26 @@ static ssize_t comp_algorithm_store(struct device *dev,
 	return len;
 }
 
+static ssize_t compact_store(struct device *dev,
+		struct device_attribute *attr, const char *buf, size_t len)
+{
+	unsigned long nr_migrated;
+	struct zram *zram = dev_to_zram(dev);
+	struct zram_meta *meta;
+
+	down_read(&zram->init_lock);
+	if (!init_done(zram)) {
+		up_read(&zram->init_lock);
+		return -EINVAL;
+	}
+
+	meta = zram->meta;
+	nr_migrated = zs_compact(meta->mem_pool);
+	up_read(&zram->init_lock);
+	atomic64_add(nr_migrated, &zram->stats.num_migrated);
+	return len;
+}
+
 /* flag operations needs meta->tb_lock */
 static int zram_test_flag(struct zram_meta *meta, u32 index,
 			enum zram_pageflags flag)

@@ -1008,6 +1028,7 @@ static DEVICE_ATTR(max_comp_streams, S_IRUGO | S_IWUSR,
 		max_comp_streams_show, max_comp_streams_store);
 static DEVICE_ATTR(comp_algorithm, S_IRUGO | S_IWUSR,
 		comp_algorithm_show, comp_algorithm_store);
+static DEVICE_ATTR(compact, S_IWUSR, NULL, compact_store);
 
 ZRAM_ATTR_RO(num_reads);
 ZRAM_ATTR_RO(num_writes);

@@ -1017,6 +1038,7 @@ ZRAM_ATTR_RO(invalid_io);
 ZRAM_ATTR_RO(notify_free);
 ZRAM_ATTR_RO(zero_pages);
 ZRAM_ATTR_RO(compr_data_size);
+ZRAM_ATTR_RO(num_migrated);
 
 static struct attribute *zram_disk_attrs[] = {
 	&dev_attr_disksize.attr,

@@ -1024,6 +1046,7 @@ static struct attribute *zram_disk_attrs[] = {
 	&dev_attr_reset.attr,
 	&dev_attr_num_reads.attr,
 	&dev_attr_num_writes.attr,
+	&dev_attr_num_migrated.attr,
 	&dev_attr_failed_reads.attr,
 	&dev_attr_failed_writes.attr,
 	&dev_attr_invalid_io.attr,

@@ -1036,6 +1059,7 @@ static struct attribute *zram_disk_attrs[] = {
 	&dev_attr_mem_used_max.attr,
 	&dev_attr_max_comp_streams.attr,
 	&dev_attr_comp_algorithm.attr,
+	&dev_attr_compact.attr,
 	NULL,
 };
drivers/block/zram/zram_drv.h +1 -0
index b05a816b09ac..5e7a565808b9 100644
@@ -84,6 +84,7 @@ struct zram_stats {
 	atomic64_t compr_data_size;	/* compressed size of pages stored */
 	atomic64_t num_reads;	/* failed + successful */
 	atomic64_t num_writes;	/* --do-- */
+	atomic64_t num_migrated;	/* no. of migrated object */
 	atomic64_t failed_reads;	/* can happen when memory is too low */
 	atomic64_t failed_writes;	/* can happen when memory is too low */
 	atomic64_t invalid_io;	/* non-page-aligned I/O requests */
Signature · 1 line
2.0.0
#7 lore raw
In reply to Minchan Kim

Hi, Minchan.

I have a question.
The problem mentioned can't be resolved with compaction? Is there any reason that zsmalloc pages can't be moved by compaction operation in direct reclaim?

2014-12-02 오전 11:49에 Minchan Kim 이(가) 쓴 글:

Quoted 42 lines

Recently, there was issue about zsmalloc fragmentation and I got a report from Juno that new fork failed although there are plenty of free pages in the system.
His investigation revealed zram is one of the culprit to make heavy fragmentation so there was no more contiguous 16K page for pgd to fork in the ARM.

This patchset implement *basic* zsmalloc compaction support and zram utilizes it so admin can do

	"echo 1 > /sys/block/zram0/compact"

Actually, ideal is that mm migrate code is aware of zram pages and migrate them out automatically without admin's manual opeartion when system is out of contiguous page. Howver, we need more thinking before adding more hooks to migrate.c. Even though we implement it, we need manual trigger mode, too so I hope we could enhance zram migration stuff based on this primitive functions in future.

I just tested it on only x86 so need more testing on other arches. Additionally, I should have a number for zsmalloc regression caused by indirect layering. Unfortunately, I don't have any ARM test machine on my desk. I will get it soon and test it. Anyway, before further work, I'd like to hear opinion.

Pathset is based on v3.18-rc6-mmotm-2014-11-26-15-45.

Thanks.

Minchan Kim (6):
zsmalloc: expand size class to support sizeof(unsigned long)
zsmalloc: add indrection layer to decouple handle from object
zsmalloc: implement reverse mapping
zsmalloc: encode alloced mark in handle object
zsmalloc: support compaction
zram: support compaction

  drivers/block/zram/zram_drv.c |  24 ++
  drivers/block/zram/zram_drv.h |   1 +
  include/linux/zsmalloc.h      |   1 +
  mm/zsmalloc.c                 | 596 +++++++++++++++++++++++++++++++++++++-----
  4 files changed, 552 insertions(+), 70 deletions(-)
author maintainer
#8 lore raw

Hey Seungho,

Quoted 6 lines · On Thu, Dec 04, 2014 at 03:49:21PM +0900, "박승호/책임연구원/SW…

Hi, Minchan.

I have a question.
The problem mentioned can't be resolved with compaction? Is there any reason that zsmalloc pages can't be moved by compaction operation in direct reclaim?

Currently, zsmalloc doesn't request movable page to page allocator since compaction is not aware of zram pages(ie, PageZram(page)). IOW, compaction cannot migrate zram pages at the moment. As I described, it's final destination we should go but I think we need more thinking to generalize such special pages handling (ex, balloon, zswap, zram and so on for future) in compaction logic.

Now, I want to merge basic primitive functions in zsmalloc to support zspage migration, which will be used as basic utility functions for supporting compaction-aware zspage migration.

In addition, even we need manual opeartion logic to trigger compaction for zsmalloc like /proc/sys/vm/compact_memory.

Quoted 50 lines

2014-12-02 오전 11:49에 Minchan Kim 이(가) 쓴 글:

Quoted 36 lines

Recently, there was issue about zsmalloc fragmentation and I got a report from Juno that new fork failed although there are plenty of free pages in the system.
His investigation revealed zram is one of the culprit to make heavy fragmentation so there was no more contiguous 16K page for pgd to fork in the ARM.

This patchset implement *basic* zsmalloc compaction support and zram utilizes it so admin can do

	"echo 1 > /sys/block/zram0/compact"

Actually, ideal is that mm migrate code is aware of zram pages and migrate them out automatically without admin's manual opeartion when system is out of contiguous page. Howver, we need more thinking before adding more hooks to migrate.c. Even though we implement it, we need manual trigger mode, too so I hope we could enhance zram migration stuff based on this primitive functions in future.

I just tested it on only x86 so need more testing on other arches. Additionally, I should have a number for zsmalloc regression caused by indirect layering. Unfortunately, I don't have any ARM test machine on my desk. I will get it soon and test it. Anyway, before further work, I'd like to hear opinion.

Pathset is based on v3.18-rc6-mmotm-2014-11-26-15-45.

Thanks.

Minchan Kim (6):
zsmalloc: expand size class to support sizeof(unsigned long)
zsmalloc: add indrection layer to decouple handle from object
zsmalloc: implement reverse mapping
zsmalloc: encode alloced mark in handle object
zsmalloc: support compaction
zram: support compaction

Quoted 6 lines
 drivers/block/zram/zram_drv.c |  24 ++
 drivers/block/zram/zram_drv.h |   1 +
 include/linux/zsmalloc.h      |   1 +
 mm/zsmalloc.c                 | 596 +++++++++++++++++++++++++++++++++++++-----
 4 files changed, 552 insertions(+), 70 deletions(-)

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

Signature · 2 lines
Kind regards,
Minchan Kim
#9 lore raw

Hi, Minchan.

I got it. Thank u :).

Seungho.

2014-12-04 오후 4:20에 Minchan Kim 이(가) 쓴 글:

Quoted 71 lines

Hey Seungho,

Quoted 6 lines · On Thu, Dec 04, 2014 at 03:49:21PM +0900, "박승호/책임연구원/SW…

Hi, Minchan.

I have a question.
The problem mentioned can't be resolved with compaction? Is there any reason that zsmalloc pages can't be moved by compaction operation in direct reclaim?

Currently, zsmalloc doesn't request movable page to page allocator since compaction is not aware of zram pages(ie, PageZram(page)). IOW, compaction cannot migrate zram pages at the moment. As I described, it's final destination we should go but I think we need more thinking to generalize such special pages handling (ex, balloon, zswap, zram and so on for future) in compaction logic.

Now, I want to merge basic primitive functions in zsmalloc to support zspage migration, which will be used as basic utility functions for supporting compaction-aware zspage migration.

In addition, even we need manual opeartion logic to trigger compaction for zsmalloc like /proc/sys/vm/compact_memory.

Quoted 48 lines

2014-12-02 오전 11:49에 Minchan Kim 이(가) 쓴 글:

Quoted 36 lines

Recently, there was issue about zsmalloc fragmentation and I got a report from Juno that new fork failed although there are plenty of free pages in the system.
His investigation revealed zram is one of the culprit to make heavy fragmentation so there was no more contiguous 16K page for pgd to fork in the ARM.

This patchset implement *basic* zsmalloc compaction support and zram utilizes it so admin can do

	"echo 1 > /sys/block/zram0/compact"

Actually, ideal is that mm migrate code is aware of zram pages and migrate them out automatically without admin's manual opeartion when system is out of contiguous page. Howver, we need more thinking before adding more hooks to migrate.c. Even though we implement it, we need manual trigger mode, too so I hope we could enhance zram migration stuff based on this primitive functions in future.

I just tested it on only x86 so need more testing on other arches. Additionally, I should have a number for zsmalloc regression caused by indirect layering. Unfortunately, I don't have any ARM test machine on my desk. I will get it soon and test it. Anyway, before further work, I'd like to hear opinion.

Pathset is based on v3.18-rc6-mmotm-2014-11-26-15-45.

Thanks.

Minchan Kim (6):
zsmalloc: expand size class to support sizeof(unsigned long)
zsmalloc: add indrection layer to decouple handle from object
zsmalloc: implement reverse mapping
zsmalloc: encode alloced mark in handle object
zsmalloc: support compaction
zram: support compaction

Quoted 6 lines
  drivers/block/zram/zram_drv.c |  24 ++
  drivers/block/zram/zram_drv.h |   1 +
  include/linux/zsmalloc.h      |   1 +
  mm/zsmalloc.c                 | 596 +++++++++++++++++++++++++++++++++++++-----
  4 files changed, 552 insertions(+), 70 deletions(-)

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

#10 lore raw
In reply to 박승호/책임연구원/SW Platform(연)AOT팀([email protected])

Hi, Minchan.

Sorry, I got it. You made zsmalloc pages movable.
forget it.

Seungho.

2014-12-04 i??i?? 3:49i?? "e??i?1i?,/i+-?i??i??eu!i??/SW Platform(i??)AOTi?? ([email protected])" i?'(e??) i?' e,?:

Quoted 52 lines

Hi, Minchan.

I have a question.
The problem mentioned can't be resolved with compaction? Is there any reason that zsmalloc pages can't be moved by compaction operation in direct reclaim?

2014-12-02 i??i ? 11:49i?? Minchan Kim i?'(e??) i?' e,?:

Quoted 43 lines

Recently, there was issue about zsmalloc fragmentation and I got a report from Juno that new fork failed although there are plenty of free pages in the system.
His investigation revealed zram is one of the culprit to make heavy fragmentation so there was no more contiguous 16K page for pgd to fork in the ARM.

This patchset implement *basic* zsmalloc compaction support and zram utilizes it so admin can do

    "echo 1 > /sys/block/zram0/compact"

Actually, ideal is that mm migrate code is aware of zram pages and migrate them out automatically without admin's manual opeartion when system is out of contiguous page. Howver, we need more thinking before adding more hooks to migrate.c. Even though we implement it, we need manual trigger mode, too so I hope we could enhance zram migration stuff based on this primitive functions in future.

I just tested it on only x86 so need more testing on other arches. Additionally, I should have a number for zsmalloc regression caused by indirect layering. Unfortunately, I don't have any ARM test machine on my desk. I will get it soon and test it. Anyway, before further work, I'd like to hear opinion.

Pathset is based on v3.18-rc6-mmotm-2014-11-26-15-45.

Thanks.

Minchan Kim (6):
zsmalloc: expand size class to support sizeof(unsigned long)
zsmalloc: add indrection layer to decouple handle from object
zsmalloc: implement reverse mapping
zsmalloc: encode alloced mark in handle object
zsmalloc: support compaction
zram: support compaction

  drivers/block/zram/zram_drv.c |  24 ++
  drivers/block/zram/zram_drv.h |   1 +
  include/linux/zsmalloc.h      |   1 +
  mm/zsmalloc.c                 | 596 
+++++++++++++++++++++++++++++++++++++-----
  4 files changed, 552 insertions(+), 70 deletions(-)

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

#11 lore raw
In reply to Minchan Kim
Quoted 18 lines · Minchan Kim

Recently, there was issue about zsmalloc fragmentation and I got a report from Juno that new fork failed although there are plenty of free pages in the system.
His investigation revealed zram is one of the culprit to make heavy fragmentation so there was no more contiguous 16K page for pgd to fork in the ARM.

This patchset implement *basic* zsmalloc compaction support and zram utilizes it so admin can do

	"echo 1 > /sys/block/zram0/compact"

Actually, ideal is that mm migrate code is aware of zram pages and migrate them out automatically without admin's manual opeartion when system is out of contiguous page. Howver, we need more thinking before adding more hooks to migrate.c. Even though we implement it, we need manual trigger mode, too so I hope we could enhance zram migration stuff based on this primitive functions in future.

Quoted 7 lines

I just tested it on only x86 so need more testing on other arches. Additionally, I should have a number for zsmalloc regression caused by indirect layering. Unfortunately, I don't have any ARM test machine on my desk. I will get it soon and test it. Anyway, before further work, I'd like to hear opinion.

Pathset is based on v3.18-rc6-mmotm-2014-11-26-15-45.

Hey Minchan, sorry it has taken a while for me to look at this.

I have prototyped this for zbud to and I see you face some of the same issues, some of them much worse for zsmalloc like large number of objects to move to reclaim a page (with zbud, the max is 1).

I see you are using zsmalloc itself for allocating the handles. Why not kmalloc()? Then you wouldn't need to track the handle_class stuff and adjust the class sizes (just in the interest of changing only what is need to achieve the functionality).

I used kmalloc() but that is not without issue as the handles can be allocated from many slabs and any slab that contains a handle can't be freed, basically resulting in the handles themselves needing to be compacted, which they can't be because the user handle is a pointer to them.

One way to fix this, but it would be some amount of work, is to have the user (zswap/zbud) provide the space for the handle to zbud/zsmalloc. The zswap/zbud layer knows the size of the device (i.e. handle space) and could allocate a statically sized vmalloc area for holding handles so they don't get spread all over memory. I haven't fully explored this idea yet.

It is pretty limiting having the user trigger the compaction. Can we have a work item that periodically does some amount of compaction? Maybe also have something analogous to direct reclaim that, when zs_malloc fails to secure a new page, it will try to compact to get one? I understand this is a first step. Maybe too much.

Also worth pointing out that the fullness groups are very coarse. Combining the objects from a ZS_ALMOST_EMPTY zspage and ZS_ALMOST_FULL zspage, might not result in very tight packing. In the worst case, the destination zspage would be slightly over 1/4 full (see fullness_threshold_frac)

It also seems that you start with the smallest size classes first. Seems like if we start with the biggest first, we move fewer objects and reclaim more pages.

It does add a lot of code :-/ Not sure if there is any way around that though if we want this functionality for zsmalloc.

Seth

Quoted 11 lines

Thanks.

Minchan Kim (6):
zsmalloc: expand size class to support sizeof(unsigned long)
zsmalloc: add indrection layer to decouple handle from object
zsmalloc: implement reverse mapping
zsmalloc: encode alloced mark in handle object
zsmalloc: support compaction
zram: support compaction

Quoted 14 lines
 drivers/block/zram/zram_drv.c |  24 ++
 drivers/block/zram/zram_drv.h |   1 +
 include/linux/zsmalloc.h      |   1 +
 mm/zsmalloc.c                 | 596 +++++++++++++++++++++++++++++++++++++-----
 4 files changed, 552 insertions(+), 70 deletions(-)
Signature · 7 lines
2.0.0

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

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

#12 lore raw

2014-12-18 7:19 GMT+08:00 Seth Jennings <[email protected]>:

Quoted 51 lines · Minchan Kim
Quoted 18 lines

Recently, there was issue about zsmalloc fragmentation and I got a report from Juno that new fork failed although there are plenty of free pages in the system.
His investigation revealed zram is one of the culprit to make heavy fragmentation so there was no more contiguous 16K page for pgd to fork in the ARM.

This patchset implement *basic* zsmalloc compaction support and zram utilizes it so admin can do

      "echo 1 > /sys/block/zram0/compact"

Actually, ideal is that mm migrate code is aware of zram pages and migrate them out automatically without admin's manual opeartion when system is out of contiguous page. Howver, we need more thinking before adding more hooks to migrate.c. Even though we implement it, we need manual trigger mode, too so I hope we could enhance zram migration stuff based on this primitive functions in future.

Quoted 7 lines

I just tested it on only x86 so need more testing on other arches. Additionally, I should have a number for zsmalloc regression caused by indirect layering. Unfortunately, I don't have any ARM test machine on my desk. I will get it soon and test it. Anyway, before further work, I'd like to hear opinion.

Pathset is based on v3.18-rc6-mmotm-2014-11-26-15-45.

Hey Minchan, sorry it has taken a while for me to look at this.

I have prototyped this for zbud to and I see you face some of the same issues, some of them much worse for zsmalloc like large number of objects to move to reclaim a page (with zbud, the max is 1).

I see you are using zsmalloc itself for allocating the handles. Why not kmalloc()? Then you wouldn't need to track the handle_class stuff and adjust the class sizes (just in the interest of changing only what is need to achieve the functionality).

I used kmalloc() but that is not without issue as the handles can be allocated from many slabs and any slab that contains a handle can't be freed, basically resulting in the handles themselves needing to be compacted, which they can't be because the user handle is a pointer to them.

One way to fix this, but it would be some amount of work, is to have the user (zswap/zbud) provide the space for the handle to zbud/zsmalloc. The zswap/zbud layer knows the size of the device (i.e. handle space) and could allocate a statically sized vmalloc area for holding handles so they don't get spread all over memory. I haven't fully explored this idea yet.

Quoted 5 lines

It is pretty limiting having the user trigger the compaction. Can we have a work item that periodically does some amount of compaction? Maybe also have something analogous to direct reclaim that, when zs_malloc fails to secure a new page, it will try to compact to get one? I understand this is a first step. Maybe too much.

Yes, User do not know when to do the compaction.
Actually, zsmalloc's responsibility is to keep the fragmentation in a low level. How about dynamically monitoring the fragmentation and do the compaction when there are too much fragmentation.

I am working on another patch to collect statistics of zsmalloc objects. Maybe that will
be helpful for this.

Thanks.

Quoted 46 lines

Also worth pointing out that the fullness groups are very coarse. Combining the objects from a ZS_ALMOST_EMPTY zspage and ZS_ALMOST_FULL zspage, might not result in very tight packing. In the worst case, the destination zspage would be slightly over 1/4 full (see fullness_threshold_frac)

It also seems that you start with the smallest size classes first. Seems like if we start with the biggest first, we move fewer objects and reclaim more pages.

It does add a lot of code :-/ Not sure if there is any way around that though if we want this functionality for zsmalloc.

Seth

Quoted 17 lines

Thanks.

Minchan Kim (6):
zsmalloc: expand size class to support sizeof(unsigned long)
zsmalloc: add indrection layer to decouple handle from object
zsmalloc: implement reverse mapping
zsmalloc: encode alloced mark in handle object
zsmalloc: support compaction
zram: support compaction

 drivers/block/zram/zram_drv.c |  24 ++
 drivers/block/zram/zram_drv.h |   1 +
 include/linux/zsmalloc.h      |   1 +
 mm/zsmalloc.c                 | 596 +++++++++++++++++++++++++++++++++++++-----
 4 files changed, 552 insertions(+), 70 deletions(-)
Quoted 8 lines

--
2.0.0

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

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

author maintainer
#13 lore raw
In reply to Seth Jennings

Hey Seth,

Quoted 25 lines · Seth Jennings
Quoted 24 lines · Minchan Kim

Recently, there was issue about zsmalloc fragmentation and I got a report from Juno that new fork failed although there are plenty of free pages in the system.
His investigation revealed zram is one of the culprit to make heavy fragmentation so there was no more contiguous 16K page for pgd to fork in the ARM.

This patchset implement *basic* zsmalloc compaction support and zram utilizes it so admin can do

	"echo 1 > /sys/block/zram0/compact"

Actually, ideal is that mm migrate code is aware of zram pages and migrate them out automatically without admin's manual opeartion when system is out of contiguous page. Howver, we need more thinking before adding more hooks to migrate.c. Even though we implement it, we need manual trigger mode, too so I hope we could enhance zram migration stuff based on this primitive functions in future.

I just tested it on only x86 so need more testing on other arches. Additionally, I should have a number for zsmalloc regression caused by indirect layering. Unfortunately, I don't have any ARM test machine on my desk. I will get it soon and test it. Anyway, before further work, I'd like to hear opinion.

Quoted 3 lines
Quoted 1 line

Pathset is based on v3.18-rc6-mmotm-2014-11-26-15-45.

Hey Minchan, sorry it has taken a while for me to look at this.

It's better than forever silence. Thanks, Seth.

Quoted 9 lines

I have prototyped this for zbud to and I see you face some of the same issues, some of them much worse for zsmalloc like large number of objects to move to reclaim a page (with zbud, the max is 1).

I see you are using zsmalloc itself for allocating the handles. Why not kmalloc()? Then you wouldn't need to track the handle_class stuff and adjust the class sizes (just in the interest of changing only what is need to achieve the functionality).

1. kmalloc minimum size : 8 byte but 4byte is enough to keep the handle
2. handle can pin lots of slab pages in memory
3. it's inaccurate for accouting memory usage of zsmalloc
4. Creating handle class in zsmalloc is simple.

Quoted 6 lines

I used kmalloc() but that is not without issue as the handles can be allocated from many slabs and any slab that contains a handle can't be freed, basically resulting in the handles themselves needing to be compacted, which they can't be because the user handle is a pointer to them.

Sure.

Quoted 3 lines

One way to fix this, but it would be some amount of work, is to have the user (zswap/zbud) provide the space for the handle to zbud/zsmalloc.

zram?

Quoted 1 line

The zswap/zbud layer knows the size of the device (i.e. handle space)

zram?

Quoted 3 lines

and could allocate a statically sized vmalloc area for holding handles so they don't get spread all over memory. I haven't fully explored this idea yet.

Hmm, I don't think it's a good idea.

Don't make an assumption that user of allocator know the size in advance. In addition, you want to populate all of pages to keep handle in vmalloc area statiscally? It wouldn't be huge but it depends on the user's setup of disksize. More question: How do you search empty slot for new handle? At last, we need caching logic and small allocator for that. IMHO, it has cons than pros compared current my approach.

Quoted 2 lines

It is pretty limiting having the user trigger the compaction. Can we

Yeb, As I said, we need more policy but in this step, I want to introduce primitive functions to enhance our policy as next step.

Quoted 1 line

have a work item that periodically does some amount of compaction?

I'm not sure periodic cleanup is good idea. I'd like to pass the decision to the user, rather than allocator itself. It's enough for allocator to expose current status to the user.

Quoted 3 lines

Maybe also have something analogous to direct reclaim that, when zs_malloc fails to secure a new page, it will try to compact to get one? I understand this is a first step. Maybe too much.

Yeb, I want to separate enhance as another patchset.

Quoted 6 lines

Also worth pointing out that the fullness groups are very coarse. Combining the objects from a ZS_ALMOST_EMPTY zspage and ZS_ALMOST_FULL zspage, might not result in very tight packing. In the worst case, the destination zspage would be slightly over 1/4 full (see fullness_threshold_frac)

Good point. Actually, I had noticed that.
after all of ALMOST_EMPTY zspages are done to migrate, we might peek out ZS_ALMOST_FULL zspages to consider.

Quoted 4 lines

It also seems that you start with the smallest size classes first. Seems like if we start with the biggest first, we move fewer objects and reclaim more pages.

Good idea. I will respin.
Thanks for the comment!

Quoted 37 lines

It does add a lot of code :-/ Not sure if there is any way around that though if we want this functionality for zsmalloc.

Seth

Quoted 11 lines

Thanks.

Minchan Kim (6):
zsmalloc: expand size class to support sizeof(unsigned long)
zsmalloc: add indrection layer to decouple handle from object
zsmalloc: implement reverse mapping
zsmalloc: encode alloced mark in handle object
zsmalloc: support compaction
zram: support compaction

Quoted 14 lines
 drivers/block/zram/zram_drv.c |  24 ++
 drivers/block/zram/zram_drv.h |   1 +
 include/linux/zsmalloc.h      |   1 +
 mm/zsmalloc.c                 | 596 +++++++++++++++++++++++++++++++++++++-----
 4 files changed, 552 insertions(+), 70 deletions(-)
Signature · 7 lines
2.0.0

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

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

Signature · 2 lines
Kind regards,
Minchan Kim
author maintainer
#14 lore raw
Quoted 50 lines · Minchan Kim

Hey Seth,

Quoted 25 lines · Seth Jennings
Quoted 24 lines · Minchan Kim

Recently, there was issue about zsmalloc fragmentation and I got a report from Juno that new fork failed although there are plenty of free pages in the system.
His investigation revealed zram is one of the culprit to make heavy fragmentation so there was no more contiguous 16K page for pgd to fork in the ARM.

This patchset implement *basic* zsmalloc compaction support and zram utilizes it so admin can do

	"echo 1 > /sys/block/zram0/compact"

Actually, ideal is that mm migrate code is aware of zram pages and migrate them out automatically without admin's manual opeartion when system is out of contiguous page. Howver, we need more thinking before adding more hooks to migrate.c. Even though we implement it, we need manual trigger mode, too so I hope we could enhance zram migration stuff based on this primitive functions in future.

I just tested it on only x86 so need more testing on other arches. Additionally, I should have a number for zsmalloc regression caused by indirect layering. Unfortunately, I don't have any ARM test machine on my desk. I will get it soon and test it. Anyway, before further work, I'd like to hear opinion.

Quoted 3 lines
Quoted 1 line

Pathset is based on v3.18-rc6-mmotm-2014-11-26-15-45.

Hey Minchan, sorry it has taken a while for me to look at this.

It's better than forever silence. Thanks, Seth.

Quoted 9 lines

I have prototyped this for zbud to and I see you face some of the same issues, some of them much worse for zsmalloc like large number of objects to move to reclaim a page (with zbud, the max is 1).

I see you are using zsmalloc itself for allocating the handles. Why not kmalloc()? Then you wouldn't need to track the handle_class stuff and adjust the class sizes (just in the interest of changing only what is need to achieve the functionality).

1. kmalloc minimum size : 8 byte but 4byte is enough to keep the handle
2. handle can pin lots of slab pages in memory
3. it's inaccurate for accouting memory usage of zsmalloc
4. Creating handle class in zsmalloc is simple.

Quoted 1 line
Quoted 7 lines
Quoted 5 lines

I used kmalloc() but that is not without issue as the handles can be allocated from many slabs and any slab that contains a handle can't be freed, basically resulting in the handles themselves needing to be compacted, which they can't be because the user handle is a pointer to them.

Sure.

One thing for good with slab is that it could remove unnecessary operations to translate handle to handle's position(page, idx) so that it would be faster although we waste 50% on 32 bit machine. Okay, I will check it.

Thanks, Seth.

Quoted 105 lines
Quoted 4 lines

One way to fix this, but it would be some amount of work, is to have the user (zswap/zbud) provide the space for the handle to zbud/zsmalloc.

zram?

Quoted 1 line

The zswap/zbud layer knows the size of the device (i.e. handle space)

zram?

Quoted 3 lines

and could allocate a statically sized vmalloc area for holding handles so they don't get spread all over memory. I haven't fully explored this idea yet.

Hmm, I don't think it's a good idea.

Don't make an assumption that user of allocator know the size in advance. In addition, you want to populate all of pages to keep handle in vmalloc area statiscally? It wouldn't be huge but it depends on the user's setup of disksize. More question: How do you search empty slot for new handle? At last, we need caching logic and small allocator for that. IMHO, it has cons than pros compared current my approach.

Quoted 2 lines

It is pretty limiting having the user trigger the compaction. Can we

Yeb, As I said, we need more policy but in this step, I want to introduce primitive functions to enhance our policy as next step.

Quoted 1 line

have a work item that periodically does some amount of compaction?

I'm not sure periodic cleanup is good idea. I'd like to pass the decision to the user, rather than allocator itself. It's enough for allocator to expose current status to the user.

Quoted 3 lines

Maybe also have something analogous to direct reclaim that, when zs_malloc fails to secure a new page, it will try to compact to get one? I understand this is a first step. Maybe too much.

Yeb, I want to separate enhance as another patchset.

Quoted 6 lines

Also worth pointing out that the fullness groups are very coarse. Combining the objects from a ZS_ALMOST_EMPTY zspage and ZS_ALMOST_FULL zspage, might not result in very tight packing. In the worst case, the destination zspage would be slightly over 1/4 full (see fullness_threshold_frac)

Good point. Actually, I had noticed that.
after all of ALMOST_EMPTY zspages are done to migrate, we might peek out ZS_ALMOST_FULL zspages to consider.

Quoted 4 lines

It also seems that you start with the smallest size classes first. Seems like if we start with the biggest first, we move fewer objects and reclaim more pages.

Good idea. I will respin.
Thanks for the comment!

Quoted 37 lines

It does add a lot of code :-/ Not sure if there is any way around that though if we want this functionality for zsmalloc.

Seth

Quoted 11 lines

Thanks.

Minchan Kim (6):
zsmalloc: expand size class to support sizeof(unsigned long)
zsmalloc: add indrection layer to decouple handle from object
zsmalloc: implement reverse mapping
zsmalloc: encode alloced mark in handle object
zsmalloc: support compaction
zram: support compaction

Quoted 14 lines
 drivers/block/zram/zram_drv.c |  24 ++
 drivers/block/zram/zram_drv.h |   1 +
 include/linux/zsmalloc.h      |   1 +
 mm/zsmalloc.c                 | 596 +++++++++++++++++++++++++++++++++++++-----
 4 files changed, 552 insertions(+), 70 deletions(-)
Signature · 7 lines
2.0.0

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

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

Signature · 8 lines
Kind regards,
Minchan Kim

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Signature · 2 lines
Kind regards,
Minchan Kim