[PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[Sergey Senozhatsky]

	Hi,

Existing zsmalloc page fullness grouping leads to suboptimal page
selection for both zs_malloc() and zs_compact(). This patchset
reworks zsmalloc fullness grouping/classification.

Additinally it also implements new compaction algorithm that is
expected to use less CPU-cycles (as it potentially does fewer
memcpy-s in zs_object_copy()).

Test (synthetic) results can be seen in patch 0003.

v4:
-- fixed classes stats loop bug (Yosry)
-- fixed spelling errors (Andrew)
-- dropped some unnecessary hunks from the patches

v3:
-- reworked compaction algorithm implementation (Minchan)
-- keep existing stats and fullness enums (Minchan, Yosry)
-- dropped the patch with new zsmalloc compaction stats (Minchan)
-- report per inuse ratio group classes stats

Sergey Senozhatsky (4):
  zsmalloc: remove insert_zspage() ->inuse optimization
  zsmalloc: fine-grained inuse ratio based fullness grouping
  zsmalloc: rework compaction algorithm
  zsmalloc: show per fullness group class stats

 mm/zsmalloc.c | 358 ++++++++++++++++++++++++--------------------------
 1 file changed, 173 insertions(+), 185 deletions(-)

-- 
2.40.0.rc0.216.gc4246ad0f0-goog

[PATCHv4 1/4] zsmalloc: remove insert_zspage() ->inuse optimization

[Sergey Senozhatsky]

This optimization has no effect. It only ensures that
when a zspage was added to its corresponding fullness
list, its "inuse" counter was higher or lower than the
"inuse" counter of the zspage at the head of the list.
The intention was to keep busy zspages at the head, so
they could be filled up and moved to the ZS_FULL
fullness group more quickly. However, this doesn't work
as the "inuse" counter of a zspage can be modified by
obj_free() but the zspage may still belong to the same
fullness list. So, fix_fullness_group() won't change
the zspage's position in relation to the head's "inuse"
counter, leading to a largely random order of zspages
within the fullness list.

For instance, consider a printout of the "inuse"
counters of the first 10 zspages in a class that holds
93 objects per zspage:

 ZS_ALMOST_EMPTY:  36  67  68  64  35  54  63  52

As we can see the zspage with the lowest "inuse" counter
is actually the head of the fullness list.

Remove this pointless "optimisation".

Signed-off-by: Sergey Senozhatsky <senozhatsky@chromium.org>
---
 mm/zsmalloc.c | 13 +------------
 1 file changed, 1 insertion(+), 12 deletions(-)

diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c
index 3aed46ab7e6c..abe0c4d7942d 100644
--- a/mm/zsmalloc.c
+++ b/mm/zsmalloc.c
@@ -762,19 +762,8 @@ static void insert_zspage(struct size_class *class,
 				struct zspage *zspage,
 				enum fullness_group fullness)
 {
-	struct zspage *head;
-
 	class_stat_inc(class, fullness, 1);
-	head = list_first_entry_or_null(&class->fullness_list[fullness],
-					struct zspage, list);
-	/*
-	 * We want to see more ZS_FULL pages and less almost empty/full.
-	 * Put pages with higher ->inuse first.
-	 */
-	if (head && get_zspage_inuse(zspage) < get_zspage_inuse(head))
-		list_add(&zspage->list, &head->list);
-	else
-		list_add(&zspage->list, &class->fullness_list[fullness]);
+	list_add(&zspage->list, &class->fullness_list[fullness]);
 }
 
 /*
-- 
2.40.0.rc0.216.gc4246ad0f0-goog

[PATCHv4 2/4] zsmalloc: fine-grained inuse ratio based fullness grouping

[Sergey Senozhatsky]

Each zspage maintains ->inuse counter which keeps track of the
number of objects stored in the zspage. The ->inuse counter also
determines the zspage's "fullness group" which is calculated as
the ratio of the "inuse" objects to the total number of objects
the zspage can hold (objs_per_zspage). The closer the ->inuse
counter is to objs_per_zspage, the better.

Each size class maintains several fullness lists, that keep
track of zspages of particular "fullness". Pages within each
fullness list are stored in random order with regard to the
->inuse counter. This is because sorting the zspages by ->inuse
counter each time obj_malloc() or obj_free() is called would
be too expensive. However, the ->inuse counter is still a
crucial factor in many situations.

For the two major zsmalloc operations, zs_malloc() and zs_compact(),
we typically select the head zspage from the corresponding fullness
list as the best candidate zspage. However, this assumption is not
always accurate.

For the zs_malloc() operation, the optimal candidate zspage should
have the highest ->inuse counter. This is because the goal is to
maximize the number of ZS_FULL zspages and make full use of all
allocated memory.

For the zs_compact() operation, the optimal source zspage should
have the lowest ->inuse counter. This is because compaction needs
to move objects in use to another page before it can release the
zspage and return its physical pages to the buddy allocator. The
fewer objects in use, the quicker compaction can release the zspage.
Additionally, compaction is measured by the number of pages it
releases.

This patch reworks the fullness grouping mechanism. Instead of
having two groups - ZS_ALMOST_EMPTY (usage ratio below 3/4) and
ZS_ALMOST_FULL (usage ration above 3/4) - that result in too many
zspages being included in the ALMOST_EMPTY group for specific
classes, size classes maintain a larger number of fullness lists
that give strict guarantees on the minimum and maximum ->inuse
values within each group. Each group represents a 10% change in the
->inuse ratio compared to neighboring groups. In essence, there
are groups for zspages with 0%, 10%, 20% usage ratios, and so on,
up to 100%.

This enhances the selection of candidate zspages for both zs_malloc()
and zs_compact(). A printout of the ->inuse counters of the first 7
zspages per (random) class fullness group:

 class-768 objs_per_zspage 16:
   fullness 100%:  empty
   fullness  99%:  empty
   fullness  90%:  empty
   fullness  80%:  empty
   fullness  70%:  empty
   fullness  60%:  8  8  9  9  8  8  8
   fullness  50%:  empty
   fullness  40%:  5  5  6  5  5  5  5
   fullness  30%:  4  4  4  4  4  4  4
   fullness  20%:  2  3  2  3  3  2  2
   fullness  10%:  1  1  1  1  1  1  1
   fullness   0%:  empty

The zs_malloc() function searches through the groups of pages
starting with the one having the highest usage ratio. This means
that it always selects a zspage from the group with the least
internal fragmentation (highest usage ratio) and makes it even
less fragmented by increasing its usage ratio.

The zs_compact() function, on the other hand, begins by scanning
the group with the highest fragmentation (lowest usage ratio) to
locate the source page. The first available zspage is selected, and
then the function moves downward to find a destination zspage in
the group with the lowest internal fragmentation (highest usage
ratio).

Signed-off-by: Sergey Senozhatsky <senozhatsky@chromium.org>
---
 mm/zsmalloc.c | 248 ++++++++++++++++++++++++++------------------------
 1 file changed, 130 insertions(+), 118 deletions(-)

diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c
index abe0c4d7942d..cc59336a966a 100644
--- a/mm/zsmalloc.c
+++ b/mm/zsmalloc.c
@@ -127,7 +127,7 @@
 #define OBJ_INDEX_MASK	((_AC(1, UL) << OBJ_INDEX_BITS) - 1)
 
 #define HUGE_BITS	1
-#define FULLNESS_BITS	2
+#define FULLNESS_BITS	4
 #define CLASS_BITS	8
 #define ISOLATED_BITS	5
 #define MAGIC_VAL_BITS	8
@@ -159,51 +159,46 @@
 #define ZS_SIZE_CLASSES	(DIV_ROUND_UP(ZS_MAX_ALLOC_SIZE - ZS_MIN_ALLOC_SIZE, \
 				      ZS_SIZE_CLASS_DELTA) + 1)
 
+/*
+ * Pages are distinguished by the ratio of used memory (that is the ratio
+ * of ->inuse objects to all objects that page can store). For example,
+ * INUSE_RATIO_10 means that the ratio of used objects is > 0% and <= 10%.
+ *
+ * The number of fullness groups is not random. It allows us to keep
+ * difference between the least busy page in the group (minimum permitted
+ * number of ->inuse objects) and the most busy page (maximum permitted
+ * number of ->inuse objects) at a reasonable value.
+ */
 enum fullness_group {
-	ZS_EMPTY,
-	ZS_ALMOST_EMPTY,
-	ZS_ALMOST_FULL,
-	ZS_FULL,
-	NR_ZS_FULLNESS,
+	ZS_INUSE_RATIO_0,
+	ZS_INUSE_RATIO_10,
+	/* NOTE: 5 more fullness groups here */
+	ZS_INUSE_RATIO_70	= 7,
+	/* NOTE: 2 more fullness groups here */
+	ZS_INUSE_RATIO_99       = 10,
+	ZS_INUSE_RATIO_100,
+	NR_FULLNESS_GROUPS,
 };
 
 enum class_stat_type {
-	CLASS_EMPTY,
-	CLASS_ALMOST_EMPTY,
-	CLASS_ALMOST_FULL,
-	CLASS_FULL,
-	OBJ_ALLOCATED,
-	OBJ_USED,
-	NR_ZS_STAT_TYPE,
+	/* NOTE: stats for 12 fullness groups here: from inuse 0 to 100 */
+	ZS_OBJS_ALLOCATED       = NR_FULLNESS_GROUPS,
+	ZS_OBJS_INUSE,
+	NR_CLASS_STAT_TYPES,
 };
 
 struct zs_size_stat {
-	unsigned long objs[NR_ZS_STAT_TYPE];
+	unsigned long objs[NR_CLASS_STAT_TYPES];
 };
 
 #ifdef CONFIG_ZSMALLOC_STAT
 static struct dentry *zs_stat_root;
 #endif
 
-/*
- * We assign a page to ZS_ALMOST_EMPTY fullness group when:
- *	n <= N / f, where
- * n = number of allocated objects
- * N = total number of objects zspage can store
- * f = fullness_threshold_frac
- *
- * Similarly, we assign zspage to:
- *	ZS_ALMOST_FULL	when n > N / f
- *	ZS_EMPTY	when n == 0
- *	ZS_FULL		when n == N
- *
- * (see: fix_fullness_group())
- */
-static const int fullness_threshold_frac = 4;
 static size_t huge_class_size;
 
 struct size_class {
-	struct list_head fullness_list[NR_ZS_FULLNESS];
+	struct list_head fullness_list[NR_FULLNESS_GROUPS];
 	/*
 	 * Size of objects stored in this class. Must be multiple
 	 * of ZS_ALIGN.
@@ -547,8 +542,8 @@ static inline void set_freeobj(struct zspage *zspage, unsigned int obj)
 }
 
 static void get_zspage_mapping(struct zspage *zspage,
-				unsigned int *class_idx,
-				enum fullness_group *fullness)
+			       unsigned int *class_idx,
+			       int *fullness)
 {
 	BUG_ON(zspage->magic != ZSPAGE_MAGIC);
 
@@ -557,14 +552,14 @@ static void get_zspage_mapping(struct zspage *zspage,
 }
 
 static struct size_class *zspage_class(struct zs_pool *pool,
-					     struct zspage *zspage)
+				       struct zspage *zspage)
 {
 	return pool->size_class[zspage->class];
 }
 
 static void set_zspage_mapping(struct zspage *zspage,
-				unsigned int class_idx,
-				enum fullness_group fullness)
+			       unsigned int class_idx,
+			       int fullness)
 {
 	zspage->class = class_idx;
 	zspage->fullness = fullness;
@@ -588,23 +583,19 @@ static int get_size_class_index(int size)
 	return min_t(int, ZS_SIZE_CLASSES - 1, idx);
 }
 
-/* type can be of enum type class_stat_type or fullness_group */
 static inline void class_stat_inc(struct size_class *class,
 				int type, unsigned long cnt)
 {
 	class->stats.objs[type] += cnt;
 }
 
-/* type can be of enum type class_stat_type or fullness_group */
 static inline void class_stat_dec(struct size_class *class,
 				int type, unsigned long cnt)
 {
 	class->stats.objs[type] -= cnt;
 }
 
-/* type can be of enum type class_stat_type or fullness_group */
-static inline unsigned long zs_stat_get(struct size_class *class,
-				int type)
+static inline unsigned long zs_stat_get(struct size_class *class, int type)
 {
 	return class->stats.objs[type];
 }
@@ -646,16 +637,27 @@ static int zs_stats_size_show(struct seq_file *s, void *v)
 			"pages_per_zspage", "freeable");
 
 	for (i = 0; i < ZS_SIZE_CLASSES; i++) {
+		int fg;
+
 		class = pool->size_class[i];
 
 		if (class->index != i)
 			continue;
 
 		spin_lock(&pool->lock);
-		class_almost_full = zs_stat_get(class, CLASS_ALMOST_FULL);
-		class_almost_empty = zs_stat_get(class, CLASS_ALMOST_EMPTY);
-		obj_allocated = zs_stat_get(class, OBJ_ALLOCATED);
-		obj_used = zs_stat_get(class, OBJ_USED);
+		class_almost_full = 0;
+		class_almost_empty = 0;
+		/*
+		 * Replicate old behaviour for almost_full and almost_empty
+		 * stats.
+		 */
+		for (fg = ZS_INUSE_RATIO_70; fg <= ZS_INUSE_RATIO_99; fg++)
+			class_almost_full += zs_stat_get(class, fg);
+		for (fg = ZS_INUSE_RATIO_10; fg < ZS_INUSE_RATIO_70; fg++)
+			class_almost_empty += zs_stat_get(class, fg);
+
+		obj_allocated = zs_stat_get(class, ZS_OBJS_ALLOCATED);
+		obj_used = zs_stat_get(class, ZS_OBJS_INUSE);
 		freeable = zs_can_compact(class);
 		spin_unlock(&pool->lock);
 
@@ -726,30 +728,28 @@ static inline void zs_pool_stat_destroy(struct zs_pool *pool)
 
 /*
  * For each size class, zspages are divided into different groups
- * depending on how "full" they are. This was done so that we could
- * easily find empty or nearly empty zspages when we try to shrink
- * the pool (not yet implemented). This function returns fullness
+ * depending on their usage ratio. This function returns fullness
  * status of the given page.
  */
-static enum fullness_group get_fullness_group(struct size_class *class,
-						struct zspage *zspage)
+static int get_fullness_group(struct size_class *class, struct zspage *zspage)
 {
-	int inuse, objs_per_zspage;
-	enum fullness_group fg;
+	int inuse, objs_per_zspage, ratio;
 
 	inuse = get_zspage_inuse(zspage);
 	objs_per_zspage = class->objs_per_zspage;
 
 	if (inuse == 0)
-		fg = ZS_EMPTY;
-	else if (inuse == objs_per_zspage)
-		fg = ZS_FULL;
-	else if (inuse <= 3 * objs_per_zspage / fullness_threshold_frac)
-		fg = ZS_ALMOST_EMPTY;
-	else
-		fg = ZS_ALMOST_FULL;
+		return ZS_INUSE_RATIO_0;
+	if (inuse == objs_per_zspage)
+		return ZS_INUSE_RATIO_100;
 
-	return fg;
+	ratio = 100 * inuse / objs_per_zspage;
+	/*
+	 * Take integer division into consideration: a page with one inuse
+	 * object out of 127 possible, will end up having 0 usage ratio,
+	 * which is wrong as it belongs in ZS_INUSE_RATIO_10 fullness group.
+	 */
+	return ratio / 10 + 1;
 }
 
 /*
@@ -760,7 +760,7 @@ static enum fullness_group get_fullness_group(struct size_class *class,
  */
 static void insert_zspage(struct size_class *class,
 				struct zspage *zspage,
-				enum fullness_group fullness)
+				int fullness)
 {
 	class_stat_inc(class, fullness, 1);
 	list_add(&zspage->list, &class->fullness_list[fullness]);
@@ -772,7 +772,7 @@ static void insert_zspage(struct size_class *class,
  */
 static void remove_zspage(struct size_class *class,
 				struct zspage *zspage,
-				enum fullness_group fullness)
+				int fullness)
 {
 	VM_BUG_ON(list_empty(&class->fullness_list[fullness]));
 
@@ -783,17 +783,16 @@ static void remove_zspage(struct size_class *class,
 /*
  * Each size class maintains zspages in different fullness groups depending
  * on the number of live objects they contain. When allocating or freeing
- * objects, the fullness status of the page can change, say, from ALMOST_FULL
- * to ALMOST_EMPTY when freeing an object. This function checks if such
- * a status change has occurred for the given page and accordingly moves the
- * page from the freelist of the old fullness group to that of the new
- * fullness group.
+ * objects, the fullness status of the page can change, for instance, from
+ * INUSE_RATIO_80 to INUSE_RATIO_70 when freeing an object. This function
+ * checks if such a status change has occurred for the given page and
+ * accordingly moves the page from the list of the old fullness group to that
+ * of the new fullness group.
  */
-static enum fullness_group fix_fullness_group(struct size_class *class,
-						struct zspage *zspage)
+static int fix_fullness_group(struct size_class *class, struct zspage *zspage)
 {
 	int class_idx;
-	enum fullness_group currfg, newfg;
+	int currfg, newfg;
 
 	get_zspage_mapping(zspage, &class_idx, &currfg);
 	newfg = get_fullness_group(class, zspage);
@@ -966,7 +965,7 @@ static void __free_zspage(struct zs_pool *pool, struct size_class *class,
 				struct zspage *zspage)
 {
 	struct page *page, *next;
-	enum fullness_group fg;
+	int fg;
 	unsigned int class_idx;
 
 	get_zspage_mapping(zspage, &class_idx, &fg);
@@ -974,7 +973,7 @@ static void __free_zspage(struct zs_pool *pool, struct size_class *class,
 	assert_spin_locked(&pool->lock);
 
 	VM_BUG_ON(get_zspage_inuse(zspage));
-	VM_BUG_ON(fg != ZS_EMPTY);
+	VM_BUG_ON(fg != ZS_INUSE_RATIO_0);
 
 	/* Free all deferred handles from zs_free */
 	free_handles(pool, class, zspage);
@@ -992,9 +991,8 @@ static void __free_zspage(struct zs_pool *pool, struct size_class *class,
 
 	cache_free_zspage(pool, zspage);
 
-	class_stat_dec(class, OBJ_ALLOCATED, class->objs_per_zspage);
-	atomic_long_sub(class->pages_per_zspage,
-					&pool->pages_allocated);
+	class_stat_dec(class, ZS_OBJS_ALLOCATED, class->objs_per_zspage);
+	atomic_long_sub(class->pages_per_zspage, &pool->pages_allocated);
 }
 
 static void free_zspage(struct zs_pool *pool, struct size_class *class,
@@ -1013,7 +1011,7 @@ static void free_zspage(struct zs_pool *pool, struct size_class *class,
 		return;
 	}
 
-	remove_zspage(class, zspage, ZS_EMPTY);
+	remove_zspage(class, zspage, ZS_INUSE_RATIO_0);
 #ifdef CONFIG_ZPOOL
 	list_del(&zspage->lru);
 #endif
@@ -1149,9 +1147,9 @@ static struct zspage *find_get_zspage(struct size_class *class)
 	int i;
 	struct zspage *zspage;
 
-	for (i = ZS_ALMOST_FULL; i >= ZS_EMPTY; i--) {
+	for (i = ZS_INUSE_RATIO_99; i >= ZS_INUSE_RATIO_0; i--) {
 		zspage = list_first_entry_or_null(&class->fullness_list[i],
-				struct zspage, list);
+						  struct zspage, list);
 		if (zspage)
 			break;
 	}
@@ -1510,7 +1508,7 @@ unsigned long zs_malloc(struct zs_pool *pool, size_t size, gfp_t gfp)
 {
 	unsigned long handle, obj;
 	struct size_class *class;
-	enum fullness_group newfg;
+	int newfg;
 	struct zspage *zspage;
 
 	if (unlikely(!size || size > ZS_MAX_ALLOC_SIZE))
@@ -1532,7 +1530,7 @@ unsigned long zs_malloc(struct zs_pool *pool, size_t size, gfp_t gfp)
 		/* Now move the zspage to another fullness group, if required */
 		fix_fullness_group(class, zspage);
 		record_obj(handle, obj);
-		class_stat_inc(class, OBJ_USED, 1);
+		class_stat_inc(class, ZS_OBJS_INUSE, 1);
 		spin_unlock(&pool->lock);
 
 		return handle;
@@ -1552,10 +1550,9 @@ unsigned long zs_malloc(struct zs_pool *pool, size_t size, gfp_t gfp)
 	insert_zspage(class, zspage, newfg);
 	set_zspage_mapping(zspage, class->index, newfg);
 	record_obj(handle, obj);
-	atomic_long_add(class->pages_per_zspage,
-				&pool->pages_allocated);
-	class_stat_inc(class, OBJ_ALLOCATED, class->objs_per_zspage);
-	class_stat_inc(class, OBJ_USED, 1);
+	atomic_long_add(class->pages_per_zspage, &pool->pages_allocated);
+	class_stat_inc(class, ZS_OBJS_ALLOCATED, class->objs_per_zspage);
+	class_stat_inc(class, ZS_OBJS_INUSE, 1);
 
 	/* We completely set up zspage so mark them as movable */
 	SetZsPageMovable(pool, zspage);
@@ -1611,7 +1608,7 @@ void zs_free(struct zs_pool *pool, unsigned long handle)
 	struct page *f_page;
 	unsigned long obj;
 	struct size_class *class;
-	enum fullness_group fullness;
+	int fullness;
 
 	if (IS_ERR_OR_NULL((void *)handle))
 		return;
@@ -1626,7 +1623,7 @@ void zs_free(struct zs_pool *pool, unsigned long handle)
 	zspage = get_zspage(f_page);
 	class = zspage_class(pool, zspage);
 
-	class_stat_dec(class, OBJ_USED, 1);
+	class_stat_dec(class, ZS_OBJS_INUSE, 1);
 
 #ifdef CONFIG_ZPOOL
 	if (zspage->under_reclaim) {
@@ -1644,7 +1641,7 @@ void zs_free(struct zs_pool *pool, unsigned long handle)
 	obj_free(class->size, obj, NULL);
 
 	fullness = fix_fullness_group(class, zspage);
-	if (fullness == ZS_EMPTY)
+	if (fullness == ZS_INUSE_RATIO_0)
 		free_zspage(pool, class, zspage);
 
 	spin_unlock(&pool->lock);
@@ -1826,22 +1823,33 @@ static int migrate_zspage(struct zs_pool *pool, struct size_class *class,
 	return ret;
 }
 
-static struct zspage *isolate_zspage(struct size_class *class, bool source)
+static struct zspage *isolate_src_zspage(struct size_class *class)
 {
-	int i;
 	struct zspage *zspage;
-	enum fullness_group fg[2] = {ZS_ALMOST_EMPTY, ZS_ALMOST_FULL};
+	int fg;
 
-	if (!source) {
-		fg[0] = ZS_ALMOST_FULL;
-		fg[1] = ZS_ALMOST_EMPTY;
+	for (fg = ZS_INUSE_RATIO_10; fg <= ZS_INUSE_RATIO_99; fg++) {
+		zspage = list_first_entry_or_null(&class->fullness_list[fg],
+						  struct zspage, list);
+		if (zspage) {
+			remove_zspage(class, zspage, fg);
+			return zspage;
+		}
 	}
 
-	for (i = 0; i < 2; i++) {
-		zspage = list_first_entry_or_null(&class->fullness_list[fg[i]],
-							struct zspage, list);
+	return zspage;
+}
+
+static struct zspage *isolate_dst_zspage(struct size_class *class)
+{
+	struct zspage *zspage;
+	int fg;
+
+	for (fg = ZS_INUSE_RATIO_99; fg >= ZS_INUSE_RATIO_10; fg--) {
+		zspage = list_first_entry_or_null(&class->fullness_list[fg],
+						  struct zspage, list);
 		if (zspage) {
-			remove_zspage(class, zspage, fg[i]);
+			remove_zspage(class, zspage, fg);
 			return zspage;
 		}
 	}
@@ -1854,12 +1862,11 @@ static struct zspage *isolate_zspage(struct size_class *class, bool source)
  * @class: destination class
  * @zspage: target page
  *
- * Return @zspage's fullness_group
+ * Return @zspage's fullness status
  */
-static enum fullness_group putback_zspage(struct size_class *class,
-			struct zspage *zspage)
+static int putback_zspage(struct size_class *class, struct zspage *zspage)
 {
-	enum fullness_group fullness;
+	int fullness;
 
 	fullness = get_fullness_group(class, zspage);
 	insert_zspage(class, zspage, fullness);
@@ -2123,7 +2130,7 @@ static void async_free_zspage(struct work_struct *work)
 	int i;
 	struct size_class *class;
 	unsigned int class_idx;
-	enum fullness_group fullness;
+	int fullness;
 	struct zspage *zspage, *tmp;
 	LIST_HEAD(free_pages);
 	struct zs_pool *pool = container_of(work, struct zs_pool,
@@ -2135,7 +2142,8 @@ static void async_free_zspage(struct work_struct *work)
 			continue;
 
 		spin_lock(&pool->lock);
-		list_splice_init(&class->fullness_list[ZS_EMPTY], &free_pages);
+		list_splice_init(&class->fullness_list[ZS_INUSE_RATIO_0],
+				 &free_pages);
 		spin_unlock(&pool->lock);
 	}
 
@@ -2144,7 +2152,7 @@ static void async_free_zspage(struct work_struct *work)
 		lock_zspage(zspage);
 
 		get_zspage_mapping(zspage, &class_idx, &fullness);
-		VM_BUG_ON(fullness != ZS_EMPTY);
+		VM_BUG_ON(fullness != ZS_INUSE_RATIO_0);
 		class = pool->size_class[class_idx];
 		spin_lock(&pool->lock);
 #ifdef CONFIG_ZPOOL
@@ -2192,8 +2200,8 @@ static inline void zs_flush_migration(struct zs_pool *pool) { }
 static unsigned long zs_can_compact(struct size_class *class)
 {
 	unsigned long obj_wasted;
-	unsigned long obj_allocated = zs_stat_get(class, OBJ_ALLOCATED);
-	unsigned long obj_used = zs_stat_get(class, OBJ_USED);
+	unsigned long obj_allocated = zs_stat_get(class, ZS_OBJS_ALLOCATED);
+	unsigned long obj_used = zs_stat_get(class, ZS_OBJS_INUSE);
 
 	if (obj_allocated <= obj_used)
 		return 0;
@@ -2217,7 +2225,7 @@ static unsigned long __zs_compact(struct zs_pool *pool,
 	 * as well as zpage allocation/free
 	 */
 	spin_lock(&pool->lock);
-	while ((src_zspage = isolate_zspage(class, true))) {
+	while ((src_zspage = isolate_src_zspage(class))) {
 		/* protect someone accessing the zspage(i.e., zs_map_object) */
 		migrate_write_lock(src_zspage);
 
@@ -2227,7 +2235,7 @@ static unsigned long __zs_compact(struct zs_pool *pool,
 		cc.obj_idx = 0;
 		cc.s_page = get_first_page(src_zspage);
 
-		while ((dst_zspage = isolate_zspage(class, false))) {
+		while ((dst_zspage = isolate_dst_zspage(class))) {
 			migrate_write_lock_nested(dst_zspage);
 
 			cc.d_page = get_first_page(dst_zspage);
@@ -2252,7 +2260,7 @@ static unsigned long __zs_compact(struct zs_pool *pool,
 		putback_zspage(class, dst_zspage);
 		migrate_write_unlock(dst_zspage);
 
-		if (putback_zspage(class, src_zspage) == ZS_EMPTY) {
+		if (putback_zspage(class, src_zspage) == ZS_INUSE_RATIO_0) {
 			migrate_write_unlock(src_zspage);
 			free_zspage(pool, class, src_zspage);
 			pages_freed += class->pages_per_zspage;
@@ -2410,7 +2418,7 @@ struct zs_pool *zs_create_pool(const char *name)
 		int pages_per_zspage;
 		int objs_per_zspage;
 		struct size_class *class;
-		int fullness = 0;
+		int fullness;
 
 		size = ZS_MIN_ALLOC_SIZE + i * ZS_SIZE_CLASS_DELTA;
 		if (size > ZS_MAX_ALLOC_SIZE)
@@ -2464,9 +2472,12 @@ struct zs_pool *zs_create_pool(const char *name)
 		class->pages_per_zspage = pages_per_zspage;
 		class->objs_per_zspage = objs_per_zspage;
 		pool->size_class[i] = class;
-		for (fullness = ZS_EMPTY; fullness < NR_ZS_FULLNESS;
-							fullness++)
+
+		fullness = ZS_INUSE_RATIO_0;
+		while (fullness < NR_FULLNESS_GROUPS) {
 			INIT_LIST_HEAD(&class->fullness_list[fullness]);
+			fullness++;
+		}
 
 		prev_class = class;
 	}
@@ -2512,11 +2523,12 @@ void zs_destroy_pool(struct zs_pool *pool)
 		if (class->index != i)
 			continue;
 
-		for (fg = ZS_EMPTY; fg < NR_ZS_FULLNESS; fg++) {
-			if (!list_empty(&class->fullness_list[fg])) {
-				pr_info("Freeing non-empty class with size %db, fullness group %d\n",
-					class->size, fg);
-			}
+		for (fg = ZS_INUSE_RATIO_0; fg < NR_FULLNESS_GROUPS; fg++) {
+			if (list_empty(&class->fullness_list[fg]))
+				continue;
+
+			pr_err("Class-%d fullness group %d is not empty\n",
+			       class->size, fg);
 		}
 		kfree(class);
 	}
@@ -2618,7 +2630,7 @@ static int zs_reclaim_page(struct zs_pool *pool, unsigned int retries)
 	unsigned long handle;
 	struct zspage *zspage;
 	struct page *page;
-	enum fullness_group fullness;
+	int fullness;
 
 	/* Lock LRU and fullness list */
 	spin_lock(&pool->lock);
@@ -2688,7 +2700,7 @@ static int zs_reclaim_page(struct zs_pool *pool, unsigned int retries)
 			 * while the page is removed from the pool. Fix it
 			 * up for the check in __free_zspage().
 			 */
-			zspage->fullness = ZS_EMPTY;
+			zspage->fullness = ZS_INUSE_RATIO_0;
 
 			__free_zspage(pool, class, zspage);
 			spin_unlock(&pool->lock);
-- 
2.40.0.rc0.216.gc4246ad0f0-goog

[PATCHv4 3/4] zsmalloc: rework compaction algorithm

[Sergey Senozhatsky]

The zsmalloc compaction algorithm has the potential to
waste some CPU cycles, particularly when compacting pages
within the same fullness group. This is due to the way it
selects the head page of the fullness list for source and
destination pages, and how it reinserts those pages during
each iteration. The algorithm may first use a page as a
migration destination and then as a migration source,
leading to an unnecessary back-and-forth movement of
objects.

Consider the following fullness list:

PageA PageB PageC PageD PageE

During the first iteration, the compaction algorithm will
select PageA as the source and PageB as the destination.
All of PageA's objects will be moved to PageB, and then
PageA will be released while PageB is reinserted into the
fullness list.

PageB PageC PageD PageE

During the next iteration, the compaction algorithm will
again select the head of the list as the source and destination,
meaning that PageB will now serve as the source and PageC as
the destination. This will result in the objects being moved
away from PageB, the same objects that were just moved to PageB
in the previous iteration.

To prevent this avalanche effect, the compaction algorithm
should not reinsert the destination page between iterations.
By doing so, the most optimal page will continue to be used
and its usage ratio will increase, reducing internal
fragmentation. The destination page should only be reinserted
into the fullness list if:
- It becomes full
- No source page is available.

TEST
====

It's very challenging to reliably test this series. I ended up
developing my own synthetic test that has 100% reproducibility.
The test generates significan fragmentation (for each size class)
and then performs compaction for each class individually and tracks
the number of memcpy() in zs_object_copy(), so that we can compare
the amount work compaction does on per-class basis.

Total amount of work (zram mm_stat objs_moved)
----------------------------------------------

Old fullness grouping, old compaction algorithm:
323977 memcpy() in zs_object_copy().

Old fullness grouping, new compaction algorithm:
262944 memcpy() in zs_object_copy().

New fullness grouping, new compaction algorithm:
213978 memcpy() in zs_object_copy().

Per-class compaction memcpy() comparison (T-test)
-------------------------------------------------

x Old fullness grouping, old compaction algorithm
+ Old fullness grouping, new compaction algorithm

    N           Min           Max        Median           Avg        Stddev
x 140           349          3513          2461     2314.1214     806.03271
+ 140           289          2778          2006     1878.1714     641.02073
Difference at 95.0% confidence
        -435.95 +/- 170.595
        -18.8387% +/- 7.37193%
        (Student's t, pooled s = 728.216)

x Old fullness grouping, old compaction algorithm
+ New fullness grouping, new compaction algorithm

    N           Min           Max        Median           Avg        Stddev
x 140           349          3513          2461     2314.1214     806.03271
+ 140           226          2279          1644     1528.4143     524.85268
Difference at 95.0% confidence
        -785.707 +/- 159.331
        -33.9527% +/- 6.88516%
        (Student's t, pooled s = 680.132)

Signed-off-by: Sergey Senozhatsky <senozhatsky@chromium.org>
---
 mm/zsmalloc.c | 78 ++++++++++++++++++++++++---------------------------
 1 file changed, 36 insertions(+), 42 deletions(-)

diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c
index cc59336a966a..a61540afbb28 100644
--- a/mm/zsmalloc.c
+++ b/mm/zsmalloc.c
@@ -1782,15 +1782,14 @@ struct zs_compact_control {
 	int obj_idx;
 };
 
-static int migrate_zspage(struct zs_pool *pool, struct size_class *class,
-				struct zs_compact_control *cc)
+static void migrate_zspage(struct zs_pool *pool, struct size_class *class,
+			   struct zs_compact_control *cc)
 {
 	unsigned long used_obj, free_obj;
 	unsigned long handle;
 	struct page *s_page = cc->s_page;
 	struct page *d_page = cc->d_page;
 	int obj_idx = cc->obj_idx;
-	int ret = 0;
 
 	while (1) {
 		handle = find_alloced_obj(class, s_page, &obj_idx);
@@ -1803,10 +1802,8 @@ static int migrate_zspage(struct zs_pool *pool, struct size_class *class,
 		}
 
 		/* Stop if there is no more space */
-		if (zspage_full(class, get_zspage(d_page))) {
-			ret = -ENOMEM;
+		if (zspage_full(class, get_zspage(d_page)))
 			break;
-		}
 
 		used_obj = handle_to_obj(handle);
 		free_obj = obj_malloc(pool, get_zspage(d_page), handle);
@@ -1819,8 +1816,6 @@ static int migrate_zspage(struct zs_pool *pool, struct size_class *class,
 	/* Remember last position in this iteration */
 	cc->s_page = s_page;
 	cc->obj_idx = obj_idx;
-
-	return ret;
 }
 
 static struct zspage *isolate_src_zspage(struct size_class *class)
@@ -2216,7 +2211,7 @@ static unsigned long __zs_compact(struct zs_pool *pool,
 				  struct size_class *class)
 {
 	struct zs_compact_control cc;
-	struct zspage *src_zspage;
+	struct zspage *src_zspage = NULL;
 	struct zspage *dst_zspage = NULL;
 	unsigned long pages_freed = 0;
 
@@ -2225,50 +2220,45 @@ static unsigned long __zs_compact(struct zs_pool *pool,
 	 * as well as zpage allocation/free
 	 */
 	spin_lock(&pool->lock);
-	while ((src_zspage = isolate_src_zspage(class))) {
-		/* protect someone accessing the zspage(i.e., zs_map_object) */
-		migrate_write_lock(src_zspage);
+	while (zs_can_compact(class)) {
+		int fg;
 
-		if (!zs_can_compact(class))
+		if (!dst_zspage) {
+			dst_zspage = isolate_dst_zspage(class);
+			if (!dst_zspage)
+				break;
+			migrate_write_lock(dst_zspage);
+			cc.d_page = get_first_page(dst_zspage);
+		}
+
+		src_zspage = isolate_src_zspage(class);
+		if (!src_zspage)
 			break;
 
+		migrate_write_lock_nested(src_zspage);
+
 		cc.obj_idx = 0;
 		cc.s_page = get_first_page(src_zspage);
+		migrate_zspage(pool, class, &cc);
+		fg = putback_zspage(class, src_zspage);
+		migrate_write_unlock(src_zspage);
 
-		while ((dst_zspage = isolate_dst_zspage(class))) {
-			migrate_write_lock_nested(dst_zspage);
-
-			cc.d_page = get_first_page(dst_zspage);
-			/*
-			 * If there is no more space in dst_page, resched
-			 * and see if anyone had allocated another zspage.
-			 */
-			if (!migrate_zspage(pool, class, &cc))
-				break;
+		if (fg == ZS_INUSE_RATIO_0) {
+			free_zspage(pool, class, src_zspage);
+			pages_freed += class->pages_per_zspage;
+			src_zspage = NULL;
+		}
 
+		if (get_fullness_group(class, dst_zspage) == ZS_INUSE_RATIO_100
+		    || spin_is_contended(&pool->lock)) {
 			putback_zspage(class, dst_zspage);
 			migrate_write_unlock(dst_zspage);
 			dst_zspage = NULL;
-			if (spin_is_contended(&pool->lock))
-				break;
-		}
 
-		/* Stop if we couldn't find slot */
-		if (dst_zspage == NULL)
-			break;
-
-		putback_zspage(class, dst_zspage);
-		migrate_write_unlock(dst_zspage);
-
-		if (putback_zspage(class, src_zspage) == ZS_INUSE_RATIO_0) {
-			migrate_write_unlock(src_zspage);
-			free_zspage(pool, class, src_zspage);
-			pages_freed += class->pages_per_zspage;
-		} else
-			migrate_write_unlock(src_zspage);
-		spin_unlock(&pool->lock);
-		cond_resched();
-		spin_lock(&pool->lock);
+			spin_unlock(&pool->lock);
+			cond_resched();
+			spin_lock(&pool->lock);
+		}
 	}
 
 	if (src_zspage) {
@@ -2276,6 +2266,10 @@ static unsigned long __zs_compact(struct zs_pool *pool,
 		migrate_write_unlock(src_zspage);
 	}
 
+	if (dst_zspage) {
+		putback_zspage(class, dst_zspage);
+		migrate_write_unlock(dst_zspage);
+	}
 	spin_unlock(&pool->lock);
 
 	return pages_freed;
-- 
2.40.0.rc0.216.gc4246ad0f0-goog

[PATCH] zsmalloc: reset compaction source zspage pointer after putback_zspage()

[Sergey Senozhatsky]

Fixup.

Reported-by: Yu Zhao <yuzhao@google.com>
Signed-off-by: Sergey Senozhatsky <senozhatsky@chromium.org>
---
 mm/zsmalloc.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c
index aea50e2aa350..cc81dfba05a0 100644
--- a/mm/zsmalloc.c
+++ b/mm/zsmalloc.c
@@ -2239,8 +2239,8 @@ static unsigned long __zs_compact(struct zs_pool *pool,
 		if (fg == ZS_INUSE_RATIO_0) {
 			free_zspage(pool, class, src_zspage);
 			pages_freed += class->pages_per_zspage;
-			src_zspage = NULL;
 		}
+		src_zspage = NULL;
 
 		if (get_fullness_group(class, dst_zspage) == ZS_INUSE_RATIO_100
 		    || spin_is_contended(&pool->lock)) {
-- 
2.40.0.634.g4ca3ef3211-goog

Re: [PATCH] zsmalloc: reset compaction source zspage pointer after putback_zspage()

[Yu Zhao]

On Sun, Apr 16, 2023 at 11:01 PM Sergey Senozhatsky
<senozhatsky@chromium.org> wrote:
>
> Fixup.
>
> Reported-by: Yu Zhao <yuzhao@google.com>
> Signed-off-by: Sergey Senozhatsky <senozhatsky@chromium.org>

Tested-by: Yu Zhao <yuzhao@google.com>

Re: [PATCH] zsmalloc: reset compaction source zspage pointer after putback_zspage()

[Yosry Ahmed]

Hi Sergey,

On Sun, Apr 16, 2023 at 10:01 PM Sergey Senozhatsky
<senozhatsky@chromium.org> wrote:
>
> Fixup.

I think the original patch landed in mm-stable already, so we might
want a proper commit log and fixes tag.

I suspect we want:
Fixes: 5a845e9f2d66 ("zsmalloc: rework compaction algorithm")

>
> Reported-by: Yu Zhao <yuzhao@google.com>
> Signed-off-by: Sergey Senozhatsky <senozhatsky@chromium.org>

Otherwise, LGTM.

Reviewed-by: Yosry Ahmed <yosryahmed@google.com>

> ---
>  mm/zsmalloc.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c
> index aea50e2aa350..cc81dfba05a0 100644
> --- a/mm/zsmalloc.c
> +++ b/mm/zsmalloc.c
> @@ -2239,8 +2239,8 @@ static unsigned long __zs_compact(struct zs_pool *pool,
>                 if (fg == ZS_INUSE_RATIO_0) {
>                         free_zspage(pool, class, src_zspage);
>                         pages_freed += class->pages_per_zspage;
> -                       src_zspage = NULL;
>                 }
> +               src_zspage = NULL;
>
>                 if (get_fullness_group(class, dst_zspage) == ZS_INUSE_RATIO_100
>                     || spin_is_contended(&pool->lock)) {
> --
> 2.40.0.634.g4ca3ef3211-goog
>

Re: [PATCH] zsmalloc: reset compaction source zspage pointer after putback_zspage()

[Sergey Senozhatsky]

Hi,

On (23/04/17 04:43), Yosry Ahmed wrote:
> <senozhatsky@chromium.org> wrote:
> >
> > Fixup.
> 
> I think the original patch landed in mm-stable already, so we might
> want a proper commit log and fixes tag.
> 
> I suspect we want:
> Fixes: 5a845e9f2d66 ("zsmalloc: rework compaction algorithm")

Oh, OK, let me send out a proper patch, just in case.

> >
> > Reported-by: Yu Zhao <yuzhao@google.com>
> > Signed-off-by: Sergey Senozhatsky <senozhatsky@chromium.org>
> 
> Otherwise, LGTM.
> 
> Reviewed-by: Yosry Ahmed <yosryahmed@google.com>

Thanks.

[PATCH] zsmalloc: reset compaction source zspage pointer after putback_zspage()

[Sergey Senozhatsky]

The current implementation of the compaction loop fails to set
the source zspage pointer to NULL in all cases, leading to a
potential issue where __zs_compact() could use a stale zspage
pointer. This pointer could even point to a previously freed
zspage, causing unexpected behavior in the putback_zspage()
and migrate_write_unlock() functions after returning from the
compaction loop.

Address the issue by ensuring that the source zspage pointer is
always set to NULL when it should be.

Fixes: 5a845e9f2d66 ("zsmalloc: rework compaction algorithm")
Signed-off-by: Sergey Senozhatsky <senozhatsky@chromium.org>
Reported-by: Yu Zhao <yuzhao@google.com>
Tested-by: Yu Zhao <yuzhao@google.com>
Reviewed-by: Yosry Ahmed <yosryahmed@google.com>
---
 mm/zsmalloc.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c
index aea50e2aa350..cc81dfba05a0 100644
--- a/mm/zsmalloc.c
+++ b/mm/zsmalloc.c
@@ -2239,8 +2239,8 @@ static unsigned long __zs_compact(struct zs_pool *pool,
 		if (fg == ZS_INUSE_RATIO_0) {
 			free_zspage(pool, class, src_zspage);
 			pages_freed += class->pages_per_zspage;
-			src_zspage = NULL;
 		}
+		src_zspage = NULL;
 
 		if (get_fullness_group(class, dst_zspage) == ZS_INUSE_RATIO_100
 		    || spin_is_contended(&pool->lock)) {
-- 
2.40.0.634.g4ca3ef3211-goog

[PATCHv4 4/4] zsmalloc: show per fullness group class stats

[Sergey Senozhatsky]

We keep the old fullness (3/4 threshold) reporting in
zs_stats_size_show(). Switch from allmost full/empty
stats to fine-grained per inuse ratio (fullness group)
reporting, which gives signicantly more data on classes
fragmentation.

Signed-off-by: Sergey Senozhatsky <senozhatsky@chromium.org>
---
 mm/zsmalloc.c | 53 ++++++++++++++++++++++-----------------------------
 1 file changed, 23 insertions(+), 30 deletions(-)

diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c
index a61540afbb28..aea50e2aa350 100644
--- a/mm/zsmalloc.c
+++ b/mm/zsmalloc.c
@@ -172,9 +172,7 @@
 enum fullness_group {
 	ZS_INUSE_RATIO_0,
 	ZS_INUSE_RATIO_10,
-	/* NOTE: 5 more fullness groups here */
-	ZS_INUSE_RATIO_70	= 7,
-	/* NOTE: 2 more fullness groups here */
+	/* NOTE: 8 more fullness groups here */
 	ZS_INUSE_RATIO_99       = 10,
 	ZS_INUSE_RATIO_100,
 	NR_FULLNESS_GROUPS,
@@ -621,23 +619,22 @@ static unsigned long zs_can_compact(struct size_class *class);
 
 static int zs_stats_size_show(struct seq_file *s, void *v)
 {
-	int i;
+	int i, fg;
 	struct zs_pool *pool = s->private;
 	struct size_class *class;
 	int objs_per_zspage;
-	unsigned long class_almost_full, class_almost_empty;
 	unsigned long obj_allocated, obj_used, pages_used, freeable;
-	unsigned long total_class_almost_full = 0, total_class_almost_empty = 0;
 	unsigned long total_objs = 0, total_used_objs = 0, total_pages = 0;
 	unsigned long total_freeable = 0;
+	unsigned long inuse_totals[NR_FULLNESS_GROUPS] = {0, };
 
-	seq_printf(s, " %5s %5s %11s %12s %13s %10s %10s %16s %8s\n",
-			"class", "size", "almost_full", "almost_empty",
+	seq_printf(s, " %5s %5s %9s %9s %9s %9s %9s %9s %9s %9s %9s %9s %9s %13s %10s %10s %16s %8s\n",
+			"class", "size", "10%", "20%", "30%", "40%",
+			"50%", "60%", "70%", "80%", "90%", "99%", "100%",
 			"obj_allocated", "obj_used", "pages_used",
 			"pages_per_zspage", "freeable");
 
 	for (i = 0; i < ZS_SIZE_CLASSES; i++) {
-		int fg;
 
 		class = pool->size_class[i];
 
@@ -645,16 +642,12 @@ static int zs_stats_size_show(struct seq_file *s, void *v)
 			continue;
 
 		spin_lock(&pool->lock);
-		class_almost_full = 0;
-		class_almost_empty = 0;
-		/*
-		 * Replicate old behaviour for almost_full and almost_empty
-		 * stats.
-		 */
-		for (fg = ZS_INUSE_RATIO_70; fg <= ZS_INUSE_RATIO_99; fg++)
-			class_almost_full += zs_stat_get(class, fg);
-		for (fg = ZS_INUSE_RATIO_10; fg < ZS_INUSE_RATIO_70; fg++)
-			class_almost_empty += zs_stat_get(class, fg);
+
+		seq_printf(s, " %5u %5u ", i, class->size);
+		for (fg = ZS_INUSE_RATIO_10; fg < NR_FULLNESS_GROUPS; fg++) {
+			inuse_totals[fg] += zs_stat_get(class, fg);
+			seq_printf(s, "%9lu ", zs_stat_get(class, fg));
+		}
 
 		obj_allocated = zs_stat_get(class, ZS_OBJS_ALLOCATED);
 		obj_used = zs_stat_get(class, ZS_OBJS_INUSE);
@@ -665,14 +658,10 @@ static int zs_stats_size_show(struct seq_file *s, void *v)
 		pages_used = obj_allocated / objs_per_zspage *
 				class->pages_per_zspage;
 
-		seq_printf(s, " %5u %5u %11lu %12lu %13lu"
-				" %10lu %10lu %16d %8lu\n",
-			i, class->size, class_almost_full, class_almost_empty,
-			obj_allocated, obj_used, pages_used,
-			class->pages_per_zspage, freeable);
+		seq_printf(s, "%13lu %10lu %10lu %16d %8lu\n",
+			   obj_allocated, obj_used, pages_used,
+			   class->pages_per_zspage, freeable);
 
-		total_class_almost_full += class_almost_full;
-		total_class_almost_empty += class_almost_empty;
 		total_objs += obj_allocated;
 		total_used_objs += obj_used;
 		total_pages += pages_used;
@@ -680,10 +669,14 @@ static int zs_stats_size_show(struct seq_file *s, void *v)
 	}
 
 	seq_puts(s, "\n");
-	seq_printf(s, " %5s %5s %11lu %12lu %13lu %10lu %10lu %16s %8lu\n",
-			"Total", "", total_class_almost_full,
-			total_class_almost_empty, total_objs,
-			total_used_objs, total_pages, "", total_freeable);
+	seq_printf(s, " %5s %5s ", "Total", "");
+
+	for (fg = ZS_INUSE_RATIO_10; fg < NR_FULLNESS_GROUPS; fg++)
+		seq_printf(s, "%9lu ", inuse_totals[fg]);
+
+	seq_printf(s, "%13lu %10lu %10lu %16s %8lu\n",
+		   total_objs, total_used_objs, total_pages, "",
+		   total_freeable);
 
 	return 0;
 }
-- 
2.40.0.rc0.216.gc4246ad0f0-goog

Re: [PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[Minchan Kim]

On Sat, Mar 04, 2023 at 12:48:31PM +0900, Sergey Senozhatsky wrote:
> 	Hi,
> 
> Existing zsmalloc page fullness grouping leads to suboptimal page
> selection for both zs_malloc() and zs_compact(). This patchset
> reworks zsmalloc fullness grouping/classification.
> 
> Additinally it also implements new compaction algorithm that is
> expected to use less CPU-cycles (as it potentially does fewer
> memcpy-s in zs_object_copy()).
> 
> Test (synthetic) results can be seen in patch 0003.
> 
> v4:
> -- fixed classes stats loop bug (Yosry)
> -- fixed spelling errors (Andrew)
> -- dropped some unnecessary hunks from the patches
> 
> v3:
> -- reworked compaction algorithm implementation (Minchan)
> -- keep existing stats and fullness enums (Minchan, Yosry)
> -- dropped the patch with new zsmalloc compaction stats (Minchan)
> -- report per inuse ratio group classes stats
> 
> Sergey Senozhatsky (4):
>   zsmalloc: remove insert_zspage() ->inuse optimization
>   zsmalloc: fine-grained inuse ratio based fullness grouping
>   zsmalloc: rework compaction algorithm
>   zsmalloc: show per fullness group class stats
> 
>  mm/zsmalloc.c | 358 ++++++++++++++++++++++++--------------------------
>  1 file changed, 173 insertions(+), 185 deletions(-)
> 
> -- 

Acked-by: Minchan Kim <minchan@kernel.org>

Thanks, Sergey!

Re: [PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[Sergey Senozhatsky]

On (23/03/10 13:10), Minchan Kim wrote:
> > v4:
> > -- fixed classes stats loop bug (Yosry)
> > -- fixed spelling errors (Andrew)
> > -- dropped some unnecessary hunks from the patches
> > 
> > v3:
> > -- reworked compaction algorithm implementation (Minchan)
> > -- keep existing stats and fullness enums (Minchan, Yosry)
> > -- dropped the patch with new zsmalloc compaction stats (Minchan)
> > -- report per inuse ratio group classes stats
> > 
> > Sergey Senozhatsky (4):
> >   zsmalloc: remove insert_zspage() ->inuse optimization
> >   zsmalloc: fine-grained inuse ratio based fullness grouping
> >   zsmalloc: rework compaction algorithm
> >   zsmalloc: show per fullness group class stats
> > 
> >  mm/zsmalloc.c | 358 ++++++++++++++++++++++++--------------------------
> >  1 file changed, 173 insertions(+), 185 deletions(-)
> > 
> > -- 
> 
> Acked-by: Minchan Kim <minchan@kernel.org>
> 
> Thanks, Sergey!

Thank you!

Re: [PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[Yu Zhao]

On Fri, Mar 3, 2023 at 8:48 PM Sergey Senozhatsky
<senozhatsky@chromium.org> wrote:
>
>         Hi,
>
> Existing zsmalloc page fullness grouping leads to suboptimal page
> selection for both zs_malloc() and zs_compact(). This patchset
> reworks zsmalloc fullness grouping/classification.
>
> Additinally it also implements new compaction algorithm that is
> expected to use less CPU-cycles (as it potentially does fewer
> memcpy-s in zs_object_copy()).
>
> Test (synthetic) results can be seen in patch 0003.

Seeing the following crashes from mm-unstable. Please take a look. Thanks.

  list_add corruption. next is NULL.
  kernel BUG at lib/list_debug.c:26!
  Call Trace:
   <TASK>
   zs_compact+0xbf6/0xda0
   zs_shrinker_scan+0x19/0x30
   do_shrink_slab+0x1ac/0x450
   shrink_slab+0xdc/0x3d0
   shrink_one+0xe2/0x1d0
   shrink_node+0xc7f/0xea0
   do_try_to_free_pages+0x1b5/0x500
   try_to_free_pages+0x396/0x5d0
   __alloc_pages_slowpath+0x5d0/0x1030
   __alloc_pages+0x1de/0x280
   __folio_alloc+0x1e/0x40
   vma_alloc_folio+0x4c0/0x530
   shmem_alloc_and_acct_folio+0x1a6/0x3b0
   shmem_get_folio_gfp+0x689/0xf00
   shmem_fault+0x81/0x240

Re: [PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[Sergey Senozhatsky]

On (23/04/16 01:20), Yu Zhao wrote:
> 
> Seeing the following crashes from mm-unstable. Please take a look. Thanks.
> 

Hi,

Did you bisect it down to this series?

Re: [PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[Yu Zhao]

On Sun, Apr 16, 2023 at 9:19 AM Sergey Senozhatsky
<senozhatsky@chromium.org> wrote:
>
> On (23/04/16 01:20), Yu Zhao wrote:
> >
> > Seeing the following crashes from mm-unstable. Please take a look. Thanks.
> >
>
> Hi,
>
> Did you bisect it down to this series?

Not exactly -- since this series was the only suspect I had, I cherry
picked it to v6.3-rc6 and verified it is the culprit.

Re: [PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[Sergey Senozhatsky]

On (23/04/16 13:27), Yu Zhao wrote:
> > Hi,
> >
> > Did you bisect it down to this series?
> 
> Not exactly -- since this series was the only suspect I had, I cherry
> picked it to v6.3-rc6 and verified it is the culprit.

Can't reproduce it yet. One of the theories is that get_fullness_group()
maybe returns an invalid index, but I don't immediately see how would it
do so.

Is the problem reproducible? Do you run some specific test?

Re: [PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[Yu Zhao]

On Sun, Apr 16, 2023 at 8:44 PM Sergey Senozhatsky
<senozhatsky@chromium.org> wrote:
>
> On (23/04/16 13:27), Yu Zhao wrote:
> > > Hi,
> > >
> > > Did you bisect it down to this series?
> >
> > Not exactly -- since this series was the only suspect I had, I cherry
> > picked it to v6.3-rc6 and verified it is the culprit.
>
> Can't reproduce it yet. One of the theories is that get_fullness_group()
> maybe returns an invalid index, but I don't immediately see how would it
> do so.
>
> Is the problem reproducible?

Whenever swapping *multithreaded* heavily.

> Do you run some specific test?

E.g.,
  tools/testing/selftests/kvm/max_guest_memory_test -c 112 -m 800 -s 800
with 112 CPUs and ~770GB DRAM + 32GB zram.

Re: [PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[Sergey Senozhatsky]

On (23/04/16 20:55), Yu Zhao wrote:
> > Do you run some specific test?
> 
> E.g.,
>   tools/testing/selftests/kvm/max_guest_memory_test -c 112 -m 800 -s 800
> with 112 CPUs and ~770GB DRAM + 32GB zram.

Hmm ...

Something like this maybe?

The src zspage pointer is not NULL-ed after non-empty zspage is
put back to corresponding fullness list.

---

@@ -2239,8 +2241,8 @@ static unsigned long __zs_compact(struct zs_pool *pool,
                if (fg == ZS_INUSE_RATIO_0) {
                        free_zspage(pool, class, src_zspage);
                        pages_freed += class->pages_per_zspage;
-                       src_zspage = NULL;
                }
+               src_zspage = NULL;

                if (get_fullness_group(class, dst_zspage) == ZS_INUSE_RATIO_100
                    || spin_is_contended(&pool->lock)) {

Re: [PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[Yosry Ahmed]

Hi Sergey,

On Sun, Apr 16, 2023 at 8:52 PM Sergey Senozhatsky
<senozhatsky@chromium.org> wrote:
>
> On (23/04/16 20:55), Yu Zhao wrote:
> > > Do you run some specific test?
> >
> > E.g.,
> >   tools/testing/selftests/kvm/max_guest_memory_test -c 112 -m 800 -s 800
> > with 112 CPUs and ~770GB DRAM + 32GB zram.
>
> Hmm ...
>
> Something like this maybe?
>
> The src zspage pointer is not NULL-ed after non-empty zspage is
> put back to corresponding fullness list.
>
> ---
>
> @@ -2239,8 +2241,8 @@ static unsigned long __zs_compact(struct zs_pool *pool,
>                 if (fg == ZS_INUSE_RATIO_0) {
>                         free_zspage(pool, class, src_zspage);
>                         pages_freed += class->pages_per_zspage;
> -                       src_zspage = NULL;
>                 }
> +               src_zspage = NULL;
>
>                 if (get_fullness_group(class, dst_zspage) == ZS_INUSE_RATIO_100
>                     || spin_is_contended(&pool->lock)) {

For my own education, how can this result in the "next is NULL" debug
error Yu Zhao is seeing?

IIUC if we do not set src_zspage to NULL properly after putback, then
we will attempt to putback again after the main loop in some cases.
This can result in a zspage being present more than once in the
per-class fullness list, right?

I am not sure how this can lead to "next is NULL", which sounds like a
corrupted list_head, because the next ptr should never be NULL as far
as I can tell. I feel like I am missing something.

Re: [PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[Sergey Senozhatsky]

On (23/04/17 01:29), Yosry Ahmed wrote:
> > @@ -2239,8 +2241,8 @@ static unsigned long __zs_compact(struct zs_pool *pool,
> >                 if (fg == ZS_INUSE_RATIO_0) {
> >                         free_zspage(pool, class, src_zspage);
> >                         pages_freed += class->pages_per_zspage;
> > -                       src_zspage = NULL;
> >                 }
> > +               src_zspage = NULL;
> >
> >                 if (get_fullness_group(class, dst_zspage) == ZS_INUSE_RATIO_100
> >                     || spin_is_contended(&pool->lock)) {
> 
> For my own education, how can this result in the "next is NULL" debug
> error Yu Zhao is seeing?
> 
> IIUC if we do not set src_zspage to NULL properly after putback, then
> we will attempt to putback again after the main loop in some cases.
> This can result in a zspage being present more than once in the
> per-class fullness list, right?
> 
> I am not sure how this can lead to "next is NULL", which sounds like a
> corrupted list_head, because the next ptr should never be NULL as far
> as I can tell. I feel like I am missing something.

That's a good question to which I don't have an answer. We can list_add()
the same zspage twice, unlocking the pool after first list_add() so that
another process (including another zs_compact()) can do something to that
zspage. The answer is somewhere between these lines, I guess.

I can see how, for example, another DEBUG_LIST check can be triggered:
"list_add double add", because we basically can do

	list_add(page, list)
	list_add(page, list)

I can also see how lockdep can be unhappy with us doing

	write_unlock(&zspage->lock);
	write_unlock(&zspage->lock);

But I don't think I see how "next is NULL" happens (I haven't observed
it).

Re: [PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[Yosry Ahmed]

On Mon, Apr 17, 2023 at 4:12 AM Sergey Senozhatsky
<senozhatsky@chromium.org> wrote:
>
> On (23/04/17 01:29), Yosry Ahmed wrote:
> > > @@ -2239,8 +2241,8 @@ static unsigned long __zs_compact(struct zs_pool *pool,
> > >                 if (fg == ZS_INUSE_RATIO_0) {
> > >                         free_zspage(pool, class, src_zspage);
> > >                         pages_freed += class->pages_per_zspage;
> > > -                       src_zspage = NULL;
> > >                 }
> > > +               src_zspage = NULL;
> > >
> > >                 if (get_fullness_group(class, dst_zspage) == ZS_INUSE_RATIO_100
> > >                     || spin_is_contended(&pool->lock)) {
> >
> > For my own education, how can this result in the "next is NULL" debug
> > error Yu Zhao is seeing?
> >
> > IIUC if we do not set src_zspage to NULL properly after putback, then
> > we will attempt to putback again after the main loop in some cases.
> > This can result in a zspage being present more than once in the
> > per-class fullness list, right?
> >
> > I am not sure how this can lead to "next is NULL", which sounds like a
> > corrupted list_head, because the next ptr should never be NULL as far
> > as I can tell. I feel like I am missing something.
>
> That's a good question to which I don't have an answer. We can list_add()
> the same zspage twice, unlocking the pool after first list_add() so that
> another process (including another zs_compact()) can do something to that
> zspage. The answer is somewhere between these lines, I guess.

But the first list_add() is (in this case) the correct add, so we
expect other processes to be able to access the zspage after the first
list_add() anyway, right?

>
> I can see how, for example, another DEBUG_LIST check can be triggered:
> "list_add double add", because we basically can do
>
>         list_add(page, list)
>         list_add(page, list)
>
> I can also see how lockdep can be unhappy with us doing
>
>         write_unlock(&zspage->lock);
>         write_unlock(&zspage->lock);
>
> But I don't think I see how "next is NULL" happens (I haven't observed
> it).

Yeah I reached the same conclusion. Couldn't figure out how we can
reach the NULL scenario.

Re: [PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[Sergey Senozhatsky]

On (23/04/17 04:16), Yosry Ahmed wrote:
> > That's a good question to which I don't have an answer. We can list_add()
> > the same zspage twice, unlocking the pool after first list_add() so that
> > another process (including another zs_compact()) can do something to that
> > zspage. The answer is somewhere between these lines, I guess.
> 
> But the first list_add() is (in this case) the correct add, so we
> expect other processes to be able to access the zspage after the first
> list_add() anyway, right?

Correct. Compaction also can unlock pool->lock and schedule() so that
another process can access the source zspage, when compaction gets
scheduled it can attempt putback/unlock the same zspage one more time
(the zspage may not even exist at this point, I assume).

Re: [PATCHv4 0/4] zsmalloc: fine-grained fullness and new compaction algorithm

[Yosry Ahmed]

On Mon, Apr 17, 2023 at 4:24 AM Sergey Senozhatsky
<senozhatsky@chromium.org> wrote:
>
> On (23/04/17 04:16), Yosry Ahmed wrote:
> > > That's a good question to which I don't have an answer. We can list_add()
> > > the same zspage twice, unlocking the pool after first list_add() so that
> > > another process (including another zs_compact()) can do something to that
> > > zspage. The answer is somewhere between these lines, I guess.
> >
> > But the first list_add() is (in this case) the correct add, so we
> > expect other processes to be able to access the zspage after the first
> > list_add() anyway, right?
>
> Correct. Compaction also can unlock pool->lock and schedule() so that
> another process can access the source zspage, when compaction gets
> scheduled it can attempt putback/unlock the same zspage one more time
> (the zspage may not even exist at this point, I assume).

Good point, that could very well be where the corruption is coming
from. Thanks for pointing this out.