zsmalloc: merge size_class to reduce fragmentation
diff mbox series

Message ID 1411461011-17959-1-git-send-email-iamjoonsoo.kim@lge.com
State New, archived
Headers show
Series
  • zsmalloc: merge size_class to reduce fragmentation
Related show

Commit Message

Joonsoo Kim Sept. 23, 2014, 8:30 a.m. UTC
zsmalloc has many size_classes to reduce fragmentation and they are
in 16 bytes unit, for example, 16, 32, 48, etc., if PAGE_SIZE is 4096.
And, zsmalloc has constraint that each zspage has 4 pages at maximum.

In this situation, we can see interesting aspect.
Let's think about size_class for 1488, 1472, ..., 1376.
To prevent external fragmentation, they uses 4 pages per zspage and
so all they can contain 11 objects at maximum.

16384 (4096 * 4) = 1488 * 11 + remains
16384 (4096 * 4) = 1472 * 11 + remains
16384 (4096 * 4) = ...
16384 (4096 * 4) = 1376 * 11 + remains

It means that they have same chracteristics and classification between
them isn't needed. If we use one size_class for them, we can reduce
fragementation and save some memory. Below is result of my simple test.

TEST ENV: EXT4 on zram, mount with discard option
WORKLOAD: untar kernel source code, remove directory in descending order
in size. (drivers arch fs sound include net Documentation firmware
kernel tools)

Each line represents orig_data_size, compr_data_size, mem_used_total,
fragmentation overhead (mem_used - compr_data_size) and overhead ratio
(overhead to compr_data_size), respectively, after untar and remove
operation is executed.

* untar-nomerge.out

orig_size compr_size used_size overhead overhead_ratio
525.88MB 199.16MB 210.23MB  11.08MB 5.56%
288.32MB  97.43MB 105.63MB   8.20MB 8.41%
177.32MB  61.12MB  69.40MB   8.28MB 13.55%
146.47MB  47.32MB  56.10MB   8.78MB 18.55%
124.16MB  38.85MB  48.41MB   9.55MB 24.58%
103.93MB  31.68MB  40.93MB   9.25MB 29.21%
 84.34MB  22.86MB  32.72MB   9.86MB 43.13%
 66.87MB  14.83MB  23.83MB   9.00MB 60.70%
 60.67MB  11.11MB  18.60MB   7.49MB 67.48%
 55.86MB   8.83MB  16.61MB   7.77MB 88.03%
 53.32MB   8.01MB  15.32MB   7.31MB 91.24%

* untar-merge.out

orig_size compr_size used_size overhead overhead_ratio
526.23MB 199.18MB 209.81MB  10.64MB 5.34%
288.68MB  97.45MB 104.08MB   6.63MB 6.80%
177.68MB  61.14MB  66.93MB   5.79MB 9.47%
146.83MB  47.34MB  52.79MB   5.45MB 11.51%
124.52MB  38.87MB  44.30MB   5.43MB 13.96%
104.29MB  31.70MB  36.83MB   5.13MB 16.19%
 84.70MB  22.88MB  27.92MB   5.04MB 22.04%
 67.11MB  14.83MB  19.26MB   4.43MB 29.86%
 60.82MB  11.10MB  14.90MB   3.79MB 34.17%
 55.90MB   8.82MB  12.61MB   3.79MB 42.97%
 53.32MB   8.01MB  11.73MB   3.73MB 46.53%

As you can see above result, merged one has better utilization (overhead
ratio, 5th column) and uses less memory (mem_used_total, 3rd column).

Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
---
 mm/zsmalloc.c |   41 +++++++++++++++++++++++++++++------------
 1 file changed, 29 insertions(+), 12 deletions(-)

Comments

Andrew Morton Sept. 23, 2014, 10:25 p.m. UTC | #1
On Tue, 23 Sep 2014 17:30:11 +0900 Joonsoo Kim <iamjoonsoo.kim@lge.com> wrote:

> zsmalloc has many size_classes to reduce fragmentation and they are
> in 16 bytes unit, for example, 16, 32, 48, etc., if PAGE_SIZE is 4096.
> And, zsmalloc has constraint that each zspage has 4 pages at maximum.
> 
> In this situation, we can see interesting aspect.
> Let's think about size_class for 1488, 1472, ..., 1376.
> To prevent external fragmentation, they uses 4 pages per zspage and
> so all they can contain 11 objects at maximum.
> 
> 16384 (4096 * 4) = 1488 * 11 + remains
> 16384 (4096 * 4) = 1472 * 11 + remains
> 16384 (4096 * 4) = ...
> 16384 (4096 * 4) = 1376 * 11 + remains
> 
> It means that they have same chracteristics and classification between
> them isn't needed. If we use one size_class for them, we can reduce
> fragementation and save some memory. Below is result of my simple test.
> 
> TEST ENV: EXT4 on zram, mount with discard option
> WORKLOAD: untar kernel source code, remove directory in descending order
> in size. (drivers arch fs sound include net Documentation firmware
> kernel tools)
> 
> Each line represents orig_data_size, compr_data_size, mem_used_total,
> fragmentation overhead (mem_used - compr_data_size) and overhead ratio
> (overhead to compr_data_size), respectively, after untar and remove
> operation is executed.
> 
> * untar-nomerge.out
> 
> orig_size compr_size used_size overhead overhead_ratio
> 525.88MB 199.16MB 210.23MB  11.08MB 5.56%
> 288.32MB  97.43MB 105.63MB   8.20MB 8.41%
> 177.32MB  61.12MB  69.40MB   8.28MB 13.55%
> 146.47MB  47.32MB  56.10MB   8.78MB 18.55%
> 124.16MB  38.85MB  48.41MB   9.55MB 24.58%
> 103.93MB  31.68MB  40.93MB   9.25MB 29.21%
>  84.34MB  22.86MB  32.72MB   9.86MB 43.13%
>  66.87MB  14.83MB  23.83MB   9.00MB 60.70%
>  60.67MB  11.11MB  18.60MB   7.49MB 67.48%
>  55.86MB   8.83MB  16.61MB   7.77MB 88.03%
>  53.32MB   8.01MB  15.32MB   7.31MB 91.24%
> 
> * untar-merge.out
> 
> orig_size compr_size used_size overhead overhead_ratio
> 526.23MB 199.18MB 209.81MB  10.64MB 5.34%
> 288.68MB  97.45MB 104.08MB   6.63MB 6.80%
> 177.68MB  61.14MB  66.93MB   5.79MB 9.47%
> 146.83MB  47.34MB  52.79MB   5.45MB 11.51%
> 124.52MB  38.87MB  44.30MB   5.43MB 13.96%
> 104.29MB  31.70MB  36.83MB   5.13MB 16.19%
>  84.70MB  22.88MB  27.92MB   5.04MB 22.04%
>  67.11MB  14.83MB  19.26MB   4.43MB 29.86%
>  60.82MB  11.10MB  14.90MB   3.79MB 34.17%
>  55.90MB   8.82MB  12.61MB   3.79MB 42.97%
>  53.32MB   8.01MB  11.73MB   3.73MB 46.53%
> 
> As you can see above result, merged one has better utilization (overhead
> ratio, 5th column) and uses less memory (mem_used_total, 3rd column).
> 

The above is great, but it provided no description of the implementation,
and there are no code comments describing what's going on either.

> --- a/mm/zsmalloc.c
> +++ b/mm/zsmalloc.c
> @@ -193,6 +193,7 @@ struct size_class {
>  	 */
>  	int size;
>  	unsigned int index;
> +	unsigned int nr_obj;

Documenting the data structures is critical.  If the roles and
relationships and interactions between the data structures are
skilfully described, the implementation tends to become relatively
obvious.

>  	/* Number of PAGE_SIZE sized pages to combine to form a 'zspage' */
>  	int pages_per_zspage;
> @@ -214,7 +215,8 @@ struct link_free {
>  };
>  
>  struct zs_pool {
> -	struct size_class size_class[ZS_SIZE_CLASSES];
> +	struct size_class *size_class[ZS_SIZE_CLASSES];
> +	struct size_class __size_class[ZS_SIZE_CLASSES];

Are these the best possible names?

I assume the entries in size_class[] point into entries in
__size_class[].  Some description of how (and why!) this is arranged
would go a long way.

> @@ -949,20 +961,28 @@ struct zs_pool *zs_create_pool(gfp_t flags)
>  	if (!pool)
>  		return NULL;
>  
> -	for (i = 0; i < ZS_SIZE_CLASSES; i++) {
> +	for (i = ZS_SIZE_CLASSES - 1; i >= 0; i--) {
>  		int size;
>  		struct size_class *class;
> +		struct size_class *prev_class;
>  
>  		size = ZS_MIN_ALLOC_SIZE + i * ZS_SIZE_CLASS_DELTA;
>  		if (size > ZS_MAX_ALLOC_SIZE)
>  			size = ZS_MAX_ALLOC_SIZE;
>  
> -		class = &pool->size_class[i];
> +		class = &pool->__size_class[i];
>  		class->size = size;
>  		class->index = i;
>  		spin_lock_init(&class->lock);
>  		class->pages_per_zspage = get_pages_per_zspage(size);
> +		class->nr_obj = class->pages_per_zspage * PAGE_SIZE / size;
>  
> +		pool->size_class[i] = class;
> +		if (i < ZS_SIZE_CLASSES - 1) {
> +			prev_class = pool->size_class[i + 1];
> +			if (is_same_density(prev_class, class))
> +				pool->size_class[i] = prev_class;
> +		}
>  	}

This is the key part and is a great place to explain your design to your
readers.


Please, let's do better than this?


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
Joonsoo Kim Sept. 24, 2014, 12:48 a.m. UTC | #2
On Tue, Sep 23, 2014 at 03:25:55PM -0700, Andrew Morton wrote:
> On Tue, 23 Sep 2014 17:30:11 +0900 Joonsoo Kim <iamjoonsoo.kim@lge.com> wrote:
> 
> > zsmalloc has many size_classes to reduce fragmentation and they are
> > in 16 bytes unit, for example, 16, 32, 48, etc., if PAGE_SIZE is 4096.
> > And, zsmalloc has constraint that each zspage has 4 pages at maximum.
> > 
> > In this situation, we can see interesting aspect.
> > Let's think about size_class for 1488, 1472, ..., 1376.
> > To prevent external fragmentation, they uses 4 pages per zspage and
> > so all they can contain 11 objects at maximum.
> > 
> > 16384 (4096 * 4) = 1488 * 11 + remains
> > 16384 (4096 * 4) = 1472 * 11 + remains
> > 16384 (4096 * 4) = ...
> > 16384 (4096 * 4) = 1376 * 11 + remains
> > 
> > It means that they have same chracteristics and classification between
> > them isn't needed. If we use one size_class for them, we can reduce
> > fragementation and save some memory. Below is result of my simple test.
> > 
> > TEST ENV: EXT4 on zram, mount with discard option
> > WORKLOAD: untar kernel source code, remove directory in descending order
> > in size. (drivers arch fs sound include net Documentation firmware
> > kernel tools)
> > 
> > Each line represents orig_data_size, compr_data_size, mem_used_total,
> > fragmentation overhead (mem_used - compr_data_size) and overhead ratio
> > (overhead to compr_data_size), respectively, after untar and remove
> > operation is executed.
> > 
> > * untar-nomerge.out
> > 
> > orig_size compr_size used_size overhead overhead_ratio
> > 525.88MB 199.16MB 210.23MB  11.08MB 5.56%
> > 288.32MB  97.43MB 105.63MB   8.20MB 8.41%
> > 177.32MB  61.12MB  69.40MB   8.28MB 13.55%
> > 146.47MB  47.32MB  56.10MB   8.78MB 18.55%
> > 124.16MB  38.85MB  48.41MB   9.55MB 24.58%
> > 103.93MB  31.68MB  40.93MB   9.25MB 29.21%
> >  84.34MB  22.86MB  32.72MB   9.86MB 43.13%
> >  66.87MB  14.83MB  23.83MB   9.00MB 60.70%
> >  60.67MB  11.11MB  18.60MB   7.49MB 67.48%
> >  55.86MB   8.83MB  16.61MB   7.77MB 88.03%
> >  53.32MB   8.01MB  15.32MB   7.31MB 91.24%
> > 
> > * untar-merge.out
> > 
> > orig_size compr_size used_size overhead overhead_ratio
> > 526.23MB 199.18MB 209.81MB  10.64MB 5.34%
> > 288.68MB  97.45MB 104.08MB   6.63MB 6.80%
> > 177.68MB  61.14MB  66.93MB   5.79MB 9.47%
> > 146.83MB  47.34MB  52.79MB   5.45MB 11.51%
> > 124.52MB  38.87MB  44.30MB   5.43MB 13.96%
> > 104.29MB  31.70MB  36.83MB   5.13MB 16.19%
> >  84.70MB  22.88MB  27.92MB   5.04MB 22.04%
> >  67.11MB  14.83MB  19.26MB   4.43MB 29.86%
> >  60.82MB  11.10MB  14.90MB   3.79MB 34.17%
> >  55.90MB   8.82MB  12.61MB   3.79MB 42.97%
> >  53.32MB   8.01MB  11.73MB   3.73MB 46.53%
> > 
> > As you can see above result, merged one has better utilization (overhead
> > ratio, 5th column) and uses less memory (mem_used_total, 3rd column).
> > 
> 
> The above is great, but it provided no description of the implementation,
> and there are no code comments describing what's going on either.

Okay. I will add it.

> 
> > --- a/mm/zsmalloc.c
> > +++ b/mm/zsmalloc.c
> > @@ -193,6 +193,7 @@ struct size_class {
> >  	 */
> >  	int size;
> >  	unsigned int index;
> > +	unsigned int nr_obj;
> 
> Documenting the data structures is critical.  If the roles and
> relationships and interactions between the data structures are
> skilfully described, the implementation tends to become relatively
> obvious.

Okay.

> 
> >  	/* Number of PAGE_SIZE sized pages to combine to form a 'zspage' */
> >  	int pages_per_zspage;
> > @@ -214,7 +215,8 @@ struct link_free {
> >  };
> >  
> >  struct zs_pool {
> > -	struct size_class size_class[ZS_SIZE_CLASSES];
> > +	struct size_class *size_class[ZS_SIZE_CLASSES];
> > +	struct size_class __size_class[ZS_SIZE_CLASSES];
> 
> Are these the best possible names?
> 
> I assume the entries in size_class[] point into entries in
> __size_class[].  Some description of how (and why!) this is arranged
> would go a long way.

Okay.

> 
> > @@ -949,20 +961,28 @@ struct zs_pool *zs_create_pool(gfp_t flags)
> >  	if (!pool)
> >  		return NULL;
> >  
> > -	for (i = 0; i < ZS_SIZE_CLASSES; i++) {
> > +	for (i = ZS_SIZE_CLASSES - 1; i >= 0; i--) {
> >  		int size;
> >  		struct size_class *class;
> > +		struct size_class *prev_class;
> >  
> >  		size = ZS_MIN_ALLOC_SIZE + i * ZS_SIZE_CLASS_DELTA;
> >  		if (size > ZS_MAX_ALLOC_SIZE)
> >  			size = ZS_MAX_ALLOC_SIZE;
> >  
> > -		class = &pool->size_class[i];
> > +		class = &pool->__size_class[i];
> >  		class->size = size;
> >  		class->index = i;
> >  		spin_lock_init(&class->lock);
> >  		class->pages_per_zspage = get_pages_per_zspage(size);
> > +		class->nr_obj = class->pages_per_zspage * PAGE_SIZE / size;
> >  
> > +		pool->size_class[i] = class;
> > +		if (i < ZS_SIZE_CLASSES - 1) {
> > +			prev_class = pool->size_class[i + 1];
> > +			if (is_same_density(prev_class, class))
> > +				pool->size_class[i] = prev_class;
> > +		}
> >  	}
> 
> This is the key part and is a great place to explain your design to your
> readers.

Yes.

> 
> Please, let's do better than this?
> 

Okay. :)
I will consider all your comments and send v2 soon.

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

Patch
diff mbox series

diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c
index c4a9157..36484f4 100644
--- a/mm/zsmalloc.c
+++ b/mm/zsmalloc.c
@@ -193,6 +193,7 @@  struct size_class {
 	 */
 	int size;
 	unsigned int index;
+	unsigned int nr_obj;
 
 	/* Number of PAGE_SIZE sized pages to combine to form a 'zspage' */
 	int pages_per_zspage;
@@ -214,7 +215,8 @@  struct link_free {
 };
 
 struct zs_pool {
-	struct size_class size_class[ZS_SIZE_CLASSES];
+	struct size_class *size_class[ZS_SIZE_CLASSES];
+	struct size_class __size_class[ZS_SIZE_CLASSES];
 
 	gfp_t flags;	/* allocation flags used when growing pool */
 	atomic_long_t pages_allocated;
@@ -468,7 +470,7 @@  static enum fullness_group fix_fullness_group(struct zs_pool *pool,
 	if (newfg == currfg)
 		goto out;
 
-	class = &pool->size_class[class_idx];
+	class = pool->size_class[class_idx];
 	remove_zspage(page, class, currfg);
 	insert_zspage(page, class, newfg);
 	set_zspage_mapping(page, class_idx, newfg);
@@ -929,6 +931,16 @@  fail:
 	return notifier_to_errno(ret);
 }
 
+static bool is_same_density(struct size_class *prev, struct size_class *curr)
+{
+	if (prev->pages_per_zspage != curr->pages_per_zspage)
+		return false;
+	if (prev->nr_obj != curr->nr_obj)
+		return false;
+
+	return true;
+}
+
 /**
  * zs_create_pool - Creates an allocation pool to work from.
  * @flags: allocation flags used to allocate pool metadata
@@ -949,20 +961,28 @@  struct zs_pool *zs_create_pool(gfp_t flags)
 	if (!pool)
 		return NULL;
 
-	for (i = 0; i < ZS_SIZE_CLASSES; i++) {
+	for (i = ZS_SIZE_CLASSES - 1; i >= 0; i--) {
 		int size;
 		struct size_class *class;
+		struct size_class *prev_class;
 
 		size = ZS_MIN_ALLOC_SIZE + i * ZS_SIZE_CLASS_DELTA;
 		if (size > ZS_MAX_ALLOC_SIZE)
 			size = ZS_MAX_ALLOC_SIZE;
 
-		class = &pool->size_class[i];
+		class = &pool->__size_class[i];
 		class->size = size;
 		class->index = i;
 		spin_lock_init(&class->lock);
 		class->pages_per_zspage = get_pages_per_zspage(size);
+		class->nr_obj = class->pages_per_zspage * PAGE_SIZE / size;
 
+		pool->size_class[i] = class;
+		if (i < ZS_SIZE_CLASSES - 1) {
+			prev_class = pool->size_class[i + 1];
+			if (is_same_density(prev_class, class))
+				pool->size_class[i] = prev_class;
+		}
 	}
 
 	pool->flags = flags;
@@ -977,7 +997,7 @@  void zs_destroy_pool(struct zs_pool *pool)
 
 	for (i = 0; i < ZS_SIZE_CLASSES; i++) {
 		int fg;
-		struct size_class *class = &pool->size_class[i];
+		struct size_class *class = &pool->__size_class[i];
 
 		for (fg = 0; fg < _ZS_NR_FULLNESS_GROUPS; fg++) {
 			if (class->fullness_list[fg]) {
@@ -1003,7 +1023,6 @@  unsigned long zs_malloc(struct zs_pool *pool, size_t size)
 {
 	unsigned long obj;
 	struct link_free *link;
-	int class_idx;
 	struct size_class *class;
 
 	struct page *first_page, *m_page;
@@ -1012,9 +1031,7 @@  unsigned long zs_malloc(struct zs_pool *pool, size_t size)
 	if (unlikely(!size || size > ZS_MAX_ALLOC_SIZE))
 		return 0;
 
-	class_idx = get_size_class_index(size);
-	class = &pool->size_class[class_idx];
-	BUG_ON(class_idx != class->index);
+	class = pool->size_class[get_size_class_index(size)];
 
 	spin_lock(&class->lock);
 	first_page = find_get_zspage(class);
@@ -1067,7 +1084,7 @@  void zs_free(struct zs_pool *pool, unsigned long obj)
 	first_page = get_first_page(f_page);
 
 	get_zspage_mapping(first_page, &class_idx, &fullness);
-	class = &pool->size_class[class_idx];
+	class = pool->size_class[class_idx];
 	f_offset = obj_idx_to_offset(f_page, f_objidx, class->size);
 
 	spin_lock(&class->lock);
@@ -1128,7 +1145,7 @@  void *zs_map_object(struct zs_pool *pool, unsigned long handle,
 
 	obj_handle_to_location(handle, &page, &obj_idx);
 	get_zspage_mapping(get_first_page(page), &class_idx, &fg);
-	class = &pool->size_class[class_idx];
+	class = pool->size_class[class_idx];
 	off = obj_idx_to_offset(page, obj_idx, class->size);
 
 	area = &get_cpu_var(zs_map_area);
@@ -1162,7 +1179,7 @@  void zs_unmap_object(struct zs_pool *pool, unsigned long handle)
 
 	obj_handle_to_location(handle, &page, &obj_idx);
 	get_zspage_mapping(get_first_page(page), &class_idx, &fg);
-	class = &pool->size_class[class_idx];
+	class = pool->size_class[class_idx];
 	off = obj_idx_to_offset(page, obj_idx, class->size);
 
 	area = this_cpu_ptr(&zs_map_area);