Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1356958 > unrolled thread

Re: [RFC][PATCH v3 1/5] mm/zsmalloc: introduce class auto-compaction

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [RFC][PATCH v3 1/5] mm/zsmalloc: introduce class auto-compaction Minchan Kim <minchan@kernel.org> - 2016-03-14 07:20 +0100
    Re: [RFC][PATCH v3 1/5] mm/zsmalloc: introduce class auto-compaction Sergey Senozhatsky <sergey.senozhatsky.work@gmail.com> - 2016-03-14 08:50 +0100
      Re: [RFC][PATCH v3 1/5] mm/zsmalloc: introduce class auto-compaction Sergey Senozhatsky <sergey.senozhatsky.work@gmail.com> - 2016-03-14 09:20 +0100
      Re: [RFC][PATCH v3 1/5] mm/zsmalloc: introduce class auto-compaction Minchan Kim <minchan@kernel.org> - 2016-03-15 01:50 +0100
        Re: [RFC][PATCH v3 1/5] mm/zsmalloc: introduce class auto-compaction Sergey Senozhatsky <sergey.senozhatsky.work@gmail.com> - 2016-03-15 02:40 +0100
          Re: [RFC][PATCH v3 1/5] mm/zsmalloc: introduce class auto-compaction Minchan Kim <minchan@kernel.org> - 2016-03-15 07:20 +0100
            Re: [RFC][PATCH v3 1/5] mm/zsmalloc: introduce class auto-compaction Sergey Senozhatsky <sergey.senozhatsky.work@gmail.com> - 2016-03-17 02:30 +0100

#1356958 — Re: [RFC][PATCH v3 1/5] mm/zsmalloc: introduce class auto-compaction

Hey Sergey,

Sorry for late review.

On Thu, Mar 03, 2016 at 11:45:59PM +0900, Sergey Senozhatsky wrote:
> zsmalloc classes are known to be affected by internal fragmentation.
> 
> For example, /sys/kernel/debug/zsmalloc/zramX/classes
>  class  size almost_full almost_empty obj_allocated   obj_used pages_used pages_per_zspage freeable
>     54   896           1           12           117         57         26                2       12
> ...
>    107  1744           1           23           196         76         84                3       51
>    111  1808           0            0            63         63         28                4        0
>    126  2048           0          160           568        408        284                1       80
>    144  2336          52          620          8631       5747       4932                4     1648
>    151  2448         123          406         10090       8736       6054                3      810
>    168  2720           0          512         15738      14926      10492                2      540
>    190  3072           0            2           136        130        102                3        3
> ...
> 
> demonstrates that class-896 has 12/26=46% of unused pages, class-2336 has
> 1648/4932=33% of unused pages, etc. And the more classes we will have as
> 'normal' classes (more than one object per-zspage) the bigger this problem
> will grow. The existing compaction relies on a user space (user can trigger
> compaction via `compact' zram's sysfs attr) or a shrinker; it does not
> happen automatically.
> 
> This patch introduces a 'watermark' value of unused pages and schedules a
> compaction work on a per-class basis once class's fragmentation becomes
> too big. So compaction is not performed in current I/O operation context,
> but in workqueue workers later.
> 
> The current watermark is set to 40% -- if class has 40+% of `freeable'
> pages then compaction work will be scheduled.

Could you explain why you select per-class watermark?
Because my plan was we kick background work based on total fragmented memory
(i.e., considering used_pages/allocated_pages < some threshold).

IOW, if used_pages/allocated_pages is less than some ratio,
we kick background job with marking index of size class just freed
and then the job scans size_class from the index circulary.
As well, we should put a upper bound to scan zspages to make it
deterministic.

What do you think about it?

> 
> TEST
> ====
> 
>   2G zram, ext4, lz0
> 
>   iozone -t 1 -R -r 64K -s 1200M -I +Z
> 
>                         BASE       PATCHED
> "  Initial write "   959670.94    966724.62
> "        Rewrite "  1276167.62   1237632.88
> "           Read "  3334708.25   3345357.50
> "        Re-read "  3405310.75   3337137.25
> "   Reverse Read "  3284499.75   3241283.50
> "    Stride read "  3293417.75   3268364.00
> "    Random read "  3255253.50   3241685.00
> " Mixed workload "  3274398.00   3231498.00
> "   Random write "  1253207.50   1216247.00
> "         Pwrite "   873682.25    877045.81
> "          Pread "  3173266.00   3318471.75
> "         Fwrite "   881278.38    897622.81
> "          Fread "  4397147.00   4501131.50
> 
>   iozone -t 3 -R -r 64K -s 60M -I +Z
> 
>                         BASE       PATCHED
> "  Initial write "  1855931.62   1869576.31
> "        Rewrite "  2223531.06   2221543.62
> "           Read "  7958435.75   8023044.75
> "        Re-read "  7912776.75   8068961.00
> "   Reverse Read "  7832227.50   7788237.50
> "    Stride read "  7952113.50   7919778.00
> "    Random read "  7908816.00   7881792.50
> " Mixed workload "  6364520.38   6332493.94
> "   Random write "  2230115.69   2176777.19
> "         Pwrite "  1915939.31   1929464.75
> "          Pread "  3857052.91   3840517.91
> "         Fwrite "  2271730.44   2272800.31
> "          Fread "  9053867.00   8880966.25
> 
> Signed-off-by: Sergey Senozhatsky <sergey.senozhatsky@gmail.com>

> ---
>  mm/zsmalloc.c | 37 +++++++++++++++++++++++++++++++++++++
>  1 file changed, 37 insertions(+)
> 
> diff --git a/mm/zsmalloc.c b/mm/zsmalloc.c
> index e72efb1..a4ef7e7 100644
> --- a/mm/zsmalloc.c
> +++ b/mm/zsmalloc.c
> @@ -219,6 +219,10 @@ struct size_class {
>  	int pages_per_zspage;
>  	/* huge object: pages_per_zspage == 1 && maxobj_per_zspage == 1 */
>  	bool huge;
> +
> +	bool compact_scheduled;
> +	struct zs_pool *pool;
> +	struct work_struct compact_work;
>  };
>  
>  /*
> @@ -1467,6 +1471,8 @@ static void obj_free(struct zs_pool *pool, struct size_class *class,
>  	zs_stat_dec(class, OBJ_USED, 1);
>  }
>  
> +static bool class_watermark_ok(struct size_class *class);
> +
>  void zs_free(struct zs_pool *pool, unsigned long handle)
>  {
>  	struct page *first_page, *f_page;
> @@ -1495,6 +1501,11 @@ void zs_free(struct zs_pool *pool, unsigned long handle)
>  		atomic_long_sub(class->pages_per_zspage,
>  				&pool->pages_allocated);
>  		free_zspage(first_page);
> +	} else {
> +		if (!class_watermark_ok(class) && !class->compact_scheduled) {
> +			queue_work(system_long_wq, &class->compact_work);
> +			class->compact_scheduled = true;
> +		}
>  	}
>  	spin_unlock(&class->lock);
>  	unpin_tag(handle);
> @@ -1745,6 +1756,19 @@ static unsigned long zs_can_compact(struct size_class *class)
>  	return obj_wasted * class->pages_per_zspage;
>  }
>  
> +static bool class_watermark_ok(struct size_class *class)
> +{
> +	unsigned long pages_used = zs_stat_get(class, OBJ_ALLOCATED);
> +
> +	pages_used /= get_maxobj_per_zspage(class->size,
> +			class->pages_per_zspage) * class->pages_per_zspage;
> +
> +	if (!pages_used)
> +		return true;
> +
> +	return (100 * zs_can_compact(class) / pages_used) < 40;
> +}
> +
>  static void __zs_compact(struct zs_pool *pool, struct size_class *class)
>  {
>  	struct zs_compact_control cc;
> @@ -1789,9 +1813,17 @@ static void __zs_compact(struct zs_pool *pool, struct size_class *class)
>  	if (src_page)
>  		putback_zspage(pool, class, src_page);
>  
> +	class->compact_scheduled = false;
>  	spin_unlock(&class->lock);
>  }
>  
> +static void class_compaction_work(struct work_struct *work)
> +{
> +	struct size_class *class = container_of(work, struct size_class, compact_work);
> +
> +	__zs_compact(class->pool, class);
> +}
> +
>  unsigned long zs_compact(struct zs_pool *pool)
>  {
>  	int i;
> @@ -1948,6 +1980,9 @@ struct zs_pool *zs_create_pool(const char *name, gfp_t flags)
>  		if (pages_per_zspage == 1 &&
>  			get_maxobj_per_zspage(size, pages_per_zspage) == 1)
>  			class->huge = true;
> +
> +		INIT_WORK(&class->compact_work, class_compaction_work);
> +		class->pool = pool;
>  		spin_lock_init(&class->lock);
>  		pool->size_class[i] = class;
>  
> @@ -1990,6 +2025,8 @@ void zs_destroy_pool(struct zs_pool *pool)
>  		if (class->index != i)
>  			continue;
>  
> +		cancel_work_sync(&class->compact_work);
> +
>  		for (fg = 0; fg < _ZS_NR_FULLNESS_GROUPS; fg++) {
>  			if (class->fullness_list[fg]) {
>  				pr_info("Freeing non-empty class with size %db, fullness group %d\n",
> -- 
> 2.8.0.rc0
> 

[toc] | [next] | [standalone]

#1357016

Hello Minchan,

On (03/14/16 15:17), Minchan Kim wrote:
[..]
> > demonstrates that class-896 has 12/26=46% of unused pages, class-2336 has
> > 1648/4932=33% of unused pages, etc. And the more classes we will have as
> > 'normal' classes (more than one object per-zspage) the bigger this problem
> > will grow. The existing compaction relies on a user space (user can trigger
> > compaction via `compact' zram's sysfs attr) or a shrinker; it does not
> > happen automatically.
> > 
> > This patch introduces a 'watermark' value of unused pages and schedules a
> > compaction work on a per-class basis once class's fragmentation becomes
> > too big. So compaction is not performed in current I/O operation context,
> > but in workqueue workers later.
> > 
> > The current watermark is set to 40% -- if class has 40+% of `freeable'
> > pages then compaction work will be scheduled.
> 
> Could you explain why you select per-class watermark?

yes,

we do less work this way - scan and compact only one class, instead
of locking and compacting all of them; which sounds reasonable.


> Because my plan was we kick background work based on total fragmented memory
> (i.e., considering used_pages/allocated_pages < some threshold).

if we know that a particular class B is fragmented and the rest of them
are just fine, then we can compact only that class B, skipping extra job.

> IOW, if used_pages/allocated_pages is less than some ratio,
> we kick background job with marking index of size class just freed
> and then the job scans size_class from the index circulary.
>
> As well, we should put a upper bound to scan zspages to make it
> deterministic.

you mean that __zs_compact() instead of just checking per-class
zs_can_compact() should check global pool ratio and bail out if
compaction of class Z has dropped the overall fragmentation ratio
below some watermark?

my logic was that
 -- suppose we have class A with fragmentation ratio 49% and class B
 with 8% of wasted pages, so the overall pool fragmentation is
 (50 + 10)/ 2 < 30%, while we still have almost 50% fragmented class.
 if the aim is to reduce the memory wastage then per-class watermarks
 seem to be more flexible.

> What do you think about it?

	-ss

[toc] | [prev] | [next] | [standalone]

#1357045

On (03/14/16 16:41), Sergey Senozhatsky wrote:
[..]
> you mean that __zs_compact() instead of just checking per-class
> zs_can_compact() should check global pool ratio and bail out if
> compaction of class Z has dropped the overall fragmentation ratio
> below some watermark?
> 
> my logic was that
>  -- suppose we have class A with fragmentation ratio 49% and class B
>  with 8% of wasted pages, so the overall pool fragmentation is
>  (50 + 10)/ 2 < 30%, while we still have almost 50% fragmented class.

  "(49 + 8) / 2 < 30%"

	-ss

[toc] | [prev] | [next] | [standalone]

#1357724

On Mon, Mar 14, 2016 at 04:41:59PM +0900, Sergey Senozhatsky wrote:
> Hello Minchan,
> 
> On (03/14/16 15:17), Minchan Kim wrote:
> [..]
> > > demonstrates that class-896 has 12/26=46% of unused pages, class-2336 has
> > > 1648/4932=33% of unused pages, etc. And the more classes we will have as
> > > 'normal' classes (more than one object per-zspage) the bigger this problem
> > > will grow. The existing compaction relies on a user space (user can trigger
> > > compaction via `compact' zram's sysfs attr) or a shrinker; it does not
> > > happen automatically.
> > > 
> > > This patch introduces a 'watermark' value of unused pages and schedules a
> > > compaction work on a per-class basis once class's fragmentation becomes
> > > too big. So compaction is not performed in current I/O operation context,
> > > but in workqueue workers later.
> > > 
> > > The current watermark is set to 40% -- if class has 40+% of `freeable'
> > > pages then compaction work will be scheduled.
> > 
> > Could you explain why you select per-class watermark?
> 
> yes,
> 
> we do less work this way - scan and compact only one class, instead
> of locking and compacting all of them; which sounds reasonable.

Hmm,, It consumes more memory(i.e., sizeof(work_struct) + sizeof(void *)
+ sizeof(bool) * NR_CLASS) as well as kicking many work up to NR_CLASS.
I didn't test your patch but I guess I can make worst case scenario.

* make every class fragmented under 40%
* On the 40% boundary, repeated alloc/free of every class so every free
  can schedule work if it was not scheduled.
* Although class fragment is too high, it's not a problem if the class
  consumes small amount of memory.

I guess it can make degradation if I try to test on zsmalloc
microbenchmark.

As well, although I don't know workqueue internal well, thesedays,
I saw a few of mails related to workqueue(maybe, vmstat) and it had
some trouble if system memory pressure is heavy IIRC.

My approach is as follows, for exmaple.

Let's make a global ratio. Let's say it's 4M.
If zs_free(or something) realizes current fragment is over 4M,
kick compacion backgroud job.
The job scans from highest to lower class and compact zspages
in each size_class until it meets high watermark(e.g, 4M + 4M /2 =
6M fragment ratio).
And in the middle of background compaction, if we find it's too
many scan(e.g., 256 zspages or somethings), just bail out the
job for the latency and reschedule it for next time. At the next
time, we can continue from the last size class.

I know your concern is unncessary scan but I'm not sure it can
affect performance although we try to evaluate performance with
microbenchmark. It just loops and check with zs_can_compact
for 255 size class.

If you still don't like this approach, we can implement each
solution and test/compare. ;-)

> 
> 
> > Because my plan was we kick background work based on total fragmented memory
> > (i.e., considering used_pages/allocated_pages < some threshold).
> 
> if we know that a particular class B is fragmented and the rest of them
> are just fine, then we can compact only that class B, skipping extra job.
> 
> > IOW, if used_pages/allocated_pages is less than some ratio,
> > we kick background job with marking index of size class just freed
> > and then the job scans size_class from the index circulary.
> >
> > As well, we should put a upper bound to scan zspages to make it
> > deterministic.
> 
> you mean that __zs_compact() instead of just checking per-class
> zs_can_compact() should check global pool ratio and bail out if
> compaction of class Z has dropped the overall fragmentation ratio
> below some watermark?

Above my comment can explan the question.

> 
> my logic was that
>  -- suppose we have class A with fragmentation ratio 49% and class B
>  with 8% of wasted pages, so the overall pool fragmentation is
>  (50 + 10)/ 2 < 30%, while we still have almost 50% fragmented class.
>  if the aim is to reduce the memory wastage then per-class watermarks
>  seem to be more flexible.
> 
> > What do you think about it?
> 
> 	-ss

[toc] | [prev] | [next] | [standalone]

#1357737

On (03/15/16 09:46), Minchan Kim wrote:
[..]
> > yes,
> > 
> > we do less work this way - scan and compact only one class, instead
> > of locking and compacting all of them; which sounds reasonable.
> 
> Hmm,, It consumes more memory(i.e., sizeof(work_struct) + sizeof(void *)
> + sizeof(bool) * NR_CLASS) as well as kicking many work up to NR_CLASS.

yes, it does. not really happy with it either.

> I didn't test your patch but I guess I can make worst case scenario.
> 
> * make every class fragmented under 40%
> * On the 40% boundary, repeated alloc/free of every class so every free
>   can schedule work if it was not scheduled.
> * Although class fragment is too high, it's not a problem if the class
>   consumes small amount of memory.

hm, in this scenario both solutions are less than perfect. we jump
X times over 40% margin, we have X*NR_CLASS compaction scans in the
end. the difference is that we queue less works, yes, but we don't
have to use workqueue in the first place; compaction can be done
asynchronously by a pool's dedicated kthread. so we will just
wake_up() the process.

> I guess it can make degradation if I try to test on zsmalloc
> microbenchmark.
> 
> As well, although I don't know workqueue internal well, thesedays,
> I saw a few of mails related to workqueue(maybe, vmstat) and it had
> some trouble if system memory pressure is heavy IIRC.

yes, you are right. wq provides WQ_MEM_RECLAIM bit for this
case -- a special kthread that it will wake up to process works.

> My approach is as follows, for exmaple.
>
> Let's make a global ratio. Let's say it's 4M.

ok. should it depend on pool size?  min(20% of pool_size, XXMB)?

> If zs_free(or something) realizes current fragment is over 4M,
> kick compacion backgroud job.

yes, zs_free() is the only place that introduces fragmentation.

> The job scans from highest to lower class and compact zspages
> in each size_class until it meets high watermark(e.g, 4M + 4M /2 =
> 6M fragment ratio).

ok.

> And in the middle of background compaction, if we find it's too
> many scan(e.g., 256 zspages or somethings), just bail out the
> job for the latency and reschedule it for next time. At the next
> time, we can continue from the last size class.

ok. I'd probably prefer more simple rules here:
-- bail out because it has compacted XXMB
   so the fragmentation ratio is *expected* to be below the watermark
-- nothing to scan anymore
   compaction is executed concurrently with zs_free()/zs_malloc()
   calls, it's harder to control/guarantee some global state.

overall, no real objections. this approach can work, I think. need
to test it.

> I know your concern is unncessary scan but I'm not sure it can
> affect performance although we try to evaluate performance with
> microbenchmark. It just loops and check with zs_can_compact
> for 255 size class.

	-ss

[toc] | [prev] | [next] | [standalone]

#1357819

On Tue, Mar 15, 2016 at 10:33:03AM +0900, Sergey Senozhatsky wrote:
> On (03/15/16 09:46), Minchan Kim wrote:
> [..]
> > > yes,
> > > 
> > > we do less work this way - scan and compact only one class, instead
> > > of locking and compacting all of them; which sounds reasonable.
> > 
> > Hmm,, It consumes more memory(i.e., sizeof(work_struct) + sizeof(void *)
> > + sizeof(bool) * NR_CLASS) as well as kicking many work up to NR_CLASS.
> 
> yes, it does. not really happy with it either.
> 
> > I didn't test your patch but I guess I can make worst case scenario.
> > 
> > * make every class fragmented under 40%
> > * On the 40% boundary, repeated alloc/free of every class so every free
> >   can schedule work if it was not scheduled.
> > * Although class fragment is too high, it's not a problem if the class
> >   consumes small amount of memory.
> 
> hm, in this scenario both solutions are less than perfect. we jump
> X times over 40% margin, we have X*NR_CLASS compaction scans in the
> end. the difference is that we queue less works, yes, but we don't
> have to use workqueue in the first place; compaction can be done
> asynchronously by a pool's dedicated kthread. so we will just
> wake_up() the process.

Hmm, kthread is over-engineered to me. If we want to create new kthread
in the system, I guess we should persuade many people to merge in.
Surely, we should have why it couldn't be done by others(e.g., workqueue).

I think your workqueue approach is good to me.
Only problem I can see with it is we cannot start compaction when
we want instantly so my conclusion is we need both direct and
background compaction.

For shrinker and user-space trigger knob, we could compact in that context
while we could queue background job to compact in zs_free.

> 
> > I guess it can make degradation if I try to test on zsmalloc
> > microbenchmark.
> > 
> > As well, although I don't know workqueue internal well, thesedays,
> > I saw a few of mails related to workqueue(maybe, vmstat) and it had
> > some trouble if system memory pressure is heavy IIRC.
> 
> yes, you are right. wq provides WQ_MEM_RECLAIM bit for this
> case -- a special kthread that it will wake up to process works.
> 
> > My approach is as follows, for exmaple.
> >
> > Let's make a global ratio. Let's say it's 4M.
> 
> ok. should it depend on pool size?  min(20% of pool_size, XXMB)?

Maybe, that could be a knob but need to think more what should be
default. In this moment, clear thing is that we should prevent
frequent ping-pong background compaction as repeated alloc/free
with dancing on threshold boundary.

> 
> > If zs_free(or something) realizes current fragment is over 4M,
> > kick compacion backgroud job.
> 
> yes, zs_free() is the only place that introduces fragmentation.
> 
> > The job scans from highest to lower class and compact zspages
> > in each size_class until it meets high watermark(e.g, 4M + 4M /2 =
> > 6M fragment ratio).
> 
> ok.
> 
> > And in the middle of background compaction, if we find it's too
> > many scan(e.g., 256 zspages or somethings), just bail out the
> > job for the latency and reschedule it for next time. At the next
> > time, we can continue from the last size class.
> 
> ok. I'd probably prefer more simple rules here:
> -- bail out because it has compacted XXMB
>    so the fragmentation ratio is *expected* to be below the watermark

Need high watermark to stop compaction.
It will prevent frequent background compaction triggering.


> -- nothing to scan anymore
>    compaction is executed concurrently with zs_free()/zs_malloc()
>    calls, it's harder to control/guarantee some global state.
> 
> overall, no real objections. this approach can work, I think. need
> to test it.

Thanks, Sergey!

[toc] | [prev] | [next] | [standalone]

#1359513

Hello Minchan,

On (03/15/16 15:17), Minchan Kim wrote:
[..]
> > hm, in this scenario both solutions are less than perfect. we jump
> > X times over 40% margin, we have X*NR_CLASS compaction scans in the
> > end. the difference is that we queue less works, yes, but we don't
> > have to use workqueue in the first place; compaction can be done
> > asynchronously by a pool's dedicated kthread. so we will just
> > wake_up() the process.
> 
> Hmm, kthread is over-engineered to me. If we want to create new kthread
> in the system, I guess we should persuade many people to merge in.
> Surely, we should have why it couldn't be done by others(e.g., workqueue).
> 
> I think your workqueue approach is good to me.
> Only problem I can see with it is we cannot start compaction when
> we want instantly so my conclusion is we need both direct and
> background compaction.

well, if we will keep the shrinker callbacks then it's not such a huge
issue, IMHO. for that type of forward progress guarantees we can have
our own, dedicated, workqueue with a rescuer thread (WQ_MEM_RECLAIM).

> > > If zs_free(or something) realizes current fragment is over 4M,
> > > kick compacion backgroud job.
> > 
> > yes, zs_free() is the only place that introduces fragmentation.
> > 
> > > The job scans from highest to lower class and compact zspages
> > > in each size_class until it meets high watermark(e.g, 4M + 4M /2 =
> > > 6M fragment ratio).

just thought... I think it'll be tricky to implement this. We scan classes
from HIGH class_size to SMALL class_size, counting fragmentation value and
re-calculating the global fragmentation all the time; once the global
fragmentation passes the watermark, we start compacting from HIGH to
SMALL. the problem here is that as soon as we calculated the class B
fragmentation index and moved to class A we can't trust B anymore. classes
are not locked and absolutely free to change. so the global fragmentation
index likely will be inaccurate.

so I'm thinking about triggering a global compaction from zs_free() (to
queue less works), but instead of calculating global watermark and compacting
afterwards, just compact every class that has fragmentation over XY% (for
example 30%). "iterate from HI to LO and compact everything that is too
fragmented".

we still need some sort of a pool->compact_ts timestamp to prevent too
frequent compaction jobs.

	-ss

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web