Re: [PATCH v2] zsmalloc: merge size_class to reduce fragmentation

[Minchan Kim <minchan@kernel.org>]

Hi Joonsoo,

On Wed, Sep 24, 2014 at 03:03:46PM +0900, Joonsoo Kim 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 characteristics and classification between
> them isn't needed. If we use one size_class for them, we can reduce
> fragementation and save some memory. For this purpose, this patch
> implement size_class merging. If there is size_class that have
> same pages_per_zspage and same number of objects per zspage with previous
> size_class, we don't create and use new size_class. Instead, we use
> previous, same characteristic size_class. With this way, above example
> sizes (1488, 1472, ..., 1376) use just one size_class so we can get much
> more memory utilization.
> 
> 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).

What a nice patch!

Below is minor but want to fix.

> 
> Changed from v1:
> - More commit description about what to do in this patch.
> - Remove nr_obj in size_class, because it isn't need after initialization.
> - Rename __size_class to size_class, size_class to merged_size_class.
> - Add code comment for merged_size_class of struct zs_pool.
> - Add code comment how merging works in zs_create_pool().
> 
> Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
> ---
>  mm/zsmalloc.c |   57 ++++++++++++++++++++++++++++++++++++++++++++++++---------
>  1 file changed, 48 insertions(+), 9 deletions(-)
> 
> diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c
> index c4a9157..586c19d 100644
> --- a/mm/zsmalloc.c
> +++ b/mm/zsmalloc.c
> @@ -214,6 +214,11 @@ struct link_free {
>  };
>  
>  struct zs_pool {
> +	/*
> +	 * Each merge_size_class is pointing to one of size_class that have
> +	 * same characteristics. See zs_create_pool() for more information.
> +	 */
> +	struct size_class *merged_size_class[ZS_SIZE_CLASSES];
>  	struct size_class size_class[ZS_SIZE_CLASSES];

I don't like the naming.
My preference is to keep size_class as it is. Instead, please use
__size_class or raw_size_class for internal size class.

>  
>  	gfp_t flags;	/* allocation flags used when growing pool */
> @@ -468,7 +473,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->merged_size_class[class_idx];
>  	remove_zspage(page, class, currfg);
>  	insert_zspage(page, class, newfg);
>  	set_zspage_mapping(page, class_idx, newfg);
> @@ -929,6 +934,22 @@ fail:
>  	return notifier_to_errno(ret);
>  }
>  
> +static unsigned int objs_per_zspage(struct size_class *class)

It seems to be the number of objects in the class but it doesn't.
Please use get_maxobj_per_zspage for consistent with get_pages_per_zspage.

> +{
> +	return class->pages_per_zspage * PAGE_SIZE / class->size;
> +}
> +
> +static bool can_merge(struct size_class *prev, struct size_class *curr)
> +{
> +	if (prev->pages_per_zspage != curr->pages_per_zspage)
> +		return false;
> +
> +	if (objs_per_zspage(prev) != objs_per_zspage(curr))
> +		return false;
> +
> +	return true;
> +}
> +
>  /**
>   * zs_create_pool - Creates an allocation pool to work from.
>   * @flags: allocation flags used to allocate pool metadata
> @@ -949,9 +970,14 @@ struct zs_pool *zs_create_pool(gfp_t flags)
>  	if (!pool)
>  		return NULL;
>  
> -	for (i = 0; i < ZS_SIZE_CLASSES; i++) {
> +	/*
> +	 * Loop reversly, because, size of size_class that we want to use for
> +	 * merging should be larger or equal to current size.
> +	 */
> +	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)
> @@ -963,6 +989,22 @@ struct zs_pool *zs_create_pool(gfp_t flags)
>  		spin_lock_init(&class->lock);
>  		class->pages_per_zspage = get_pages_per_zspage(size);
>  
> +		pool->merged_size_class[i] = class;
> +		if (i == ZS_SIZE_CLASSES - 1)
> +			continue;
> +
> +		/*
> +		 * merged_size_class is used for normal zsmalloc operation such
> +		 * as alloc/free for that size. Although it is natural that we
> +		 * have one size_class for each size, there is a chance that we
> +		 * can get more memory utilization if we use one size_class for
> +		 * many different sizes whose size_class have same
> +		 * characteristics. So, we makes merged_size_class point to
> +		 * previous size_class if possible.
> +		 */
> +		prev_class = pool->merged_size_class[i + 1];
> +		if (can_merge(prev_class, class))
> +			pool->merged_size_class[i] = prev_class;
>  	}
>  
>  	pool->flags = flags;
> @@ -1003,7 +1045,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 +1053,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->merged_size_class[get_size_class_index(size)];
>  
>  	spin_lock(&class->lock);
>  	first_page = find_get_zspage(class);
> @@ -1067,7 +1106,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->merged_size_class[class_idx];
>  	f_offset = obj_idx_to_offset(f_page, f_objidx, class->size);
>  
>  	spin_lock(&class->lock);
> @@ -1128,7 +1167,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->merged_size_class[class_idx];
>  	off = obj_idx_to_offset(page, obj_idx, class->size);
>  
>  	area = &get_cpu_var(zs_map_area);
> @@ -1162,7 +1201,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->merged_size_class[class_idx];
>  	off = obj_idx_to_offset(page, obj_idx, class->size);
>  
>  	area = this_cpu_ptr(&zs_map_area);
> -- 
> 1.7.9.5
> 
> --
> To unsubscribe, send a message with 'unsubscribe linux-mm' in
> the body to majordomo@kvack.org.  For more info on Linux MM,
> see: http://www.linux-mm.org/ .
> Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

-- 
Kind regards,
Minchan Kim

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