linux-kernel - [PATCHv2 0/6] zsmalloc: fine-grained fullness and new compaction algorithm

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-Id: <20230223030451.543162-1-senozhatsky@chromium.org>
Date:   Thu, 23 Feb 2023 12:04:45 +0900
From:   Sergey Senozhatsky <senozhatsky@...omium.org>
To:     Minchan Kim <minchan@...nel.org>,
        Andrew Morton <akpm@...ux-foundation.org>
Cc:     Yosry Ahmed <yosryahmed@...gle.com>, linux-kernel@...r.kernel.org,
        linux-mm@...ck.org, Sergey Senozhatsky <senozhatsky@...omium.org>
Subject: [PATCHv2 0/6] zsmalloc: fine-grained fullness and new compaction algorithm

	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 CPU-cycles (as it potentially does fewer memcpy-s
in zs_object_copy()).

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)

Sergey Senozhatsky (6):
  zsmalloc: remove insert_zspage() ->inuse optimization
  zsmalloc: remove stat and fullness enums
  zsmalloc: fine-grained inuse ratio based fullness grouping
  zsmalloc: rework compaction algorithm
  zsmalloc: extend compaction statistics
  zram: show zsmalloc objs_moved stat in mm_stat

 Documentation/admin-guide/blockdev/zram.rst |   1 +
 drivers/block/zram/zram_drv.c               |   5 +-
 include/linux/zsmalloc.h                    |   2 +
 mm/zsmalloc.c                               | 365 ++++++++++----------
 4 files changed, 188 insertions(+), 185 deletions(-)

-- 
2.39.2.637.g21b0678d19-goog