From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752535AbaJBFjm (ORCPT ); Thu, 2 Oct 2014 01:39:42 -0400 Received: from LGEMRELSE7Q.lge.com ([156.147.1.151]:42412 "EHLO lgemrelse7q.lge.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752005AbaJBFjk (ORCPT ); Thu, 2 Oct 2014 01:39:40 -0400 X-Original-SENDERIP: 10.177.222.183 X-Original-MAILFROM: iamjoonsoo.kim@lge.com Date: Thu, 2 Oct 2014 14:39:49 +0900 From: Joonsoo Kim To: Minchan Kim Cc: Andrew Morton , Nitin Gupta , linux-mm@kvack.org, linux-kernel@vger.kernel.org, Jerome Marchand , Sergey Senozhatsky , Dan Streetman , Luigi Semenzato , juno.choi@lge.com, "seungho1.park" Subject: Re: [PATCH v4] zsmalloc: merge size_class to reduce fragmentation Message-ID: <20141002053949.GC7433@js1304-P5Q-DELUXE> References: <1411976727-29421-1-git-send-email-iamjoonsoo.kim@lge.com> <20140929231022.GC18318@bbox> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20140929231022.GC18318@bbox> User-Agent: Mutt/1.5.21 (2010-09-15) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, Sep 30, 2014 at 08:10:22AM +0900, Minchan Kim wrote: > Hey Joonsoo, > > On Mon, Sep 29, 2014 at 04:45:27PM +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 since both the 1488 and 1472 sized > > classes can only fit 11 objects into 4 pages, and an object that's > > 1472 bytes can fit into an object that's 1488 bytes, merging these > > classes to always use objects that are 1488 bytes will reduce the total > > number of size classes. And reducing the total number of size classes > > reduces overall fragmentation, because a wider range of compressed pages > > can fit into a single size class, leaving less unused objects in each > > size class. > > > > 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 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). > > > > Changes 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(). > > > > Changes from v2: > > - Add more commit description (Dan) > > - dynamically allocate size_class structure (Dan) > > - rename objs_per_zspage to get_maxobj_per_zspage (Minchan) > > > > Changes from v3: > > - Add error handling logic in zs_create_pool (Dan) > > > > Signed-off-by: Joonsoo Kim > > --- > > mm/zsmalloc.c | 84 +++++++++++++++++++++++++++++++++++++++++++++++---------- > > 1 file changed, 70 insertions(+), 14 deletions(-) > > > > diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c > > index c4a9157..11556ae 100644 > > --- a/mm/zsmalloc.c > > +++ b/mm/zsmalloc.c > > @@ -187,6 +187,7 @@ enum fullness_group { > > static const int fullness_threshold_frac = 4; > > > > struct size_class { > > + int ref; > > Couldn't we remove the ref from size_class by making zs_destroy_pool > aware of merged size class like zs_create_pool? > Hello, I think that using ref would makes intuitive code. Although there is some memory overhead, it is really small. So I prefer to this way. But, if you think that removing ref is better, I will do it. Please let me know your final decision. Thanks. From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pd0-f172.google.com (mail-pd0-f172.google.com [209.85.192.172]) by kanga.kvack.org (Postfix) with ESMTP id B9ACB6B0038 for ; Thu, 2 Oct 2014 01:39:42 -0400 (EDT) Received: by mail-pd0-f172.google.com with SMTP id ft15so1465024pdb.31 for ; Wed, 01 Oct 2014 22:39:42 -0700 (PDT) Received: from lgemrelse7q.lge.com (LGEMRELSE7Q.lge.com. [156.147.1.151]) by mx.google.com with ESMTP id zt1si2998864pac.10.2014.10.01.22.39.39 for ; Wed, 01 Oct 2014 22:39:41 -0700 (PDT) Date: Thu, 2 Oct 2014 14:39:49 +0900 From: Joonsoo Kim Subject: Re: [PATCH v4] zsmalloc: merge size_class to reduce fragmentation Message-ID: <20141002053949.GC7433@js1304-P5Q-DELUXE> References: <1411976727-29421-1-git-send-email-iamjoonsoo.kim@lge.com> <20140929231022.GC18318@bbox> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20140929231022.GC18318@bbox> Sender: owner-linux-mm@kvack.org List-ID: To: Minchan Kim Cc: Andrew Morton , Nitin Gupta , linux-mm@kvack.org, linux-kernel@vger.kernel.org, Jerome Marchand , Sergey Senozhatsky , Dan Streetman , Luigi Semenzato , juno.choi@lge.com, "seungho1.park" On Tue, Sep 30, 2014 at 08:10:22AM +0900, Minchan Kim wrote: > Hey Joonsoo, > > On Mon, Sep 29, 2014 at 04:45:27PM +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 since both the 1488 and 1472 sized > > classes can only fit 11 objects into 4 pages, and an object that's > > 1472 bytes can fit into an object that's 1488 bytes, merging these > > classes to always use objects that are 1488 bytes will reduce the total > > number of size classes. And reducing the total number of size classes > > reduces overall fragmentation, because a wider range of compressed pages > > can fit into a single size class, leaving less unused objects in each > > size class. > > > > 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 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). > > > > Changes 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(). > > > > Changes from v2: > > - Add more commit description (Dan) > > - dynamically allocate size_class structure (Dan) > > - rename objs_per_zspage to get_maxobj_per_zspage (Minchan) > > > > Changes from v3: > > - Add error handling logic in zs_create_pool (Dan) > > > > Signed-off-by: Joonsoo Kim > > --- > > mm/zsmalloc.c | 84 +++++++++++++++++++++++++++++++++++++++++++++++---------- > > 1 file changed, 70 insertions(+), 14 deletions(-) > > > > diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c > > index c4a9157..11556ae 100644 > > --- a/mm/zsmalloc.c > > +++ b/mm/zsmalloc.c > > @@ -187,6 +187,7 @@ enum fullness_group { > > static const int fullness_threshold_frac = 4; > > > > struct size_class { > > + int ref; > > Couldn't we remove the ref from size_class by making zs_destroy_pool > aware of merged size class like zs_create_pool? > Hello, I think that using ref would makes intuitive code. Although there is some memory overhead, it is really small. So I prefer to this way. But, if you think that removing ref is better, I will do it. Please let me know your final decision. Thanks. -- 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: email@kvack.org