Skip to contentSkip to conversation

mm: add ztree - new allocator for use via zpool API

PATCH Superseded Ananda Badmaev 3 participants 4 messages Sep 16, 2021 – Sep 17, 2021

Subsystems (2)

v1 of 9 Superseded Latest is v9 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 mm: add ztree - new allocator for use via zpool API

ztree is a versatile backend for zswap and potentially zram. It got its name due to the usage of red-black trees to store blocks of compressed objects. These blocks consist of several consecutive pages and ztree keeps an integer number of objects per block.

For zram, ztree has better worst case malloc() and free() times than zsmalloc, does not deteriorate over time and has slightly worse but comparable compression ratio. For zswap, ztree has better worst case malloc() and free() times than z3fold, better compression ratio than z3fold and supports reclaim unlike zsmalloc.

---
 MAINTAINERS |   7 +
 mm/Kconfig  |  18 ++
 mm/Makefile |   1 +
 mm/ztree.c  | 761 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 787 insertions(+)
 create mode 100644 mm/ztree.c
MAINTAINERS +7 -0
index d7b4f32875a9..d22ab5641e98 100644
@@ -20482,6 +20482,13 @@ L:	[email protected]
 S:	Maintained
 F:	mm/zbud.c
 
+ZTREE COMPRESSED PAGE ALLOCATOR
+M:	Ananda Badmaev <[email protected]>
+M:	Vitaly Wool <[email protected]>
+L:	[email protected]
+S:	Maintained
+F:	mm/ztree.c
+
 ZD1211RW WIRELESS DRIVER
 M:	Daniel Drake <[email protected]>
 M:	Ulrich Kunitz <[email protected]>
mm/Kconfig +18 -0
index 40a9bfcd5062..96b89ce95a3d 100644
@@ -641,6 +641,12 @@ config ZSWAP_ZPOOL_DEFAULT_Z3FOLD
 	help
 	  Use the z3fold allocator as the default allocator.
 
+config ZSWAP_ZPOOL_DEFAULT_ZTREE
+	bool "ztree"
+	select ZTREE
+	help
+	  Use the ztree allocator as the default allocator.
+
 config ZSWAP_ZPOOL_DEFAULT_ZSMALLOC
 	bool "zsmalloc"
 	select ZSMALLOC
@@ -653,6 +659,7 @@ config ZSWAP_ZPOOL_DEFAULT
        depends on ZSWAP
        default "zbud" if ZSWAP_ZPOOL_DEFAULT_ZBUD
        default "z3fold" if ZSWAP_ZPOOL_DEFAULT_Z3FOLD
+	   default "ztree" if ZSWAP_ZPOOL_DEFAULT_ZTREE
        default "zsmalloc" if ZSWAP_ZPOOL_DEFAULT_ZSMALLOC
        default ""
 
@@ -691,6 +698,17 @@ config Z3FOLD
 	  page. It is a ZBUD derivative so the simplicity and determinism are
 	  still there.
 
+config ZTREE
+	tristate "Simple allocator for compressed pages"
+	depends on ZPOOL
+	help
+	  A special purpose allocator for storing compressed pages.
+	  It stores integer number of compressed pages per block and
+	  each block consists of integer number of physical pages.
+	  Red-black trees are used for efficient block organization.
+	  ztree provides fast random read/write operations and
+	  good compression ratio in most scenarios.
+
 config ZSMALLOC
 	tristate "Memory allocator for compressed pages"
 	depends on MMU
mm/Makefile +1 -0
index e3436741d539..a38dd41e4dbc 100644
@@ -108,6 +108,7 @@ obj-$(CONFIG_ZPOOL)	+= zpool.o
 obj-$(CONFIG_ZBUD)	+= zbud.o
 obj-$(CONFIG_ZSMALLOC)	+= zsmalloc.o
 obj-$(CONFIG_Z3FOLD)	+= z3fold.o
+obj-$(CONFIG_ZTREE)		+= ztree.o
 obj-$(CONFIG_GENERIC_EARLY_IOREMAP) += early_ioremap.o
 obj-$(CONFIG_CMA)	+= cma.o
 obj-$(CONFIG_MEMORY_BALLOON) += balloon_compaction.o
mm/ztree.c new file +761 -0

761 lines not on this page · raw message

Signature · 1 line
2.20.1
#1 lore raw
Quoted 11 lines · Ananda Badmaev

ztree is a versatile backend for zswap and potentially zram. It got its name due to the usage of red-black trees to store blocks of compressed objects. These blocks consist of several consecutive pages and ztree keeps an integer number of objects per block.

For zram, ztree has better worst case malloc() and free() times than zsmalloc, does not deteriorate over time and has slightly worse but comparable compression ratio. For zswap, ztree has better worst case malloc() and free() times than z3fold, better compression ratio than z3fold and supports reclaim unlike zsmalloc.

So how many of these allocators do we need? Minimally IMHO some data should be provided for the performance comparison claims above.
Sounds like if this is based on z3fold (I haven't actually compared the code) and better in every aspect, why not just "upgrade" z3fold to ztree then?

#2 lore raw
Quoted 12 lines · Vlastimil Babka
Quoted 10 lines · Ananda Badmaev

ztree is a versatile backend for zswap and potentially zram. It got its name due to the usage of red-black trees to store blocks of compressed objects. These blocks consist of several consecutive pages and ztree keeps an integer number of objects per block.

For zram, ztree has better worst case malloc() and free() times than zsmalloc, does not deteriorate over time and has slightly worse but comparable compression ratio. For zswap, ztree has better worst case malloc() and free() times than z3fold, better compression ratio than z3fold and supports reclaim unlike zsmalloc.

Quoted 6 lines
Quoted 1 line

So how many of these allocators do we need? Minimally IMHO some data should be provided for the performance comparison claims above.
Sounds like if this is based on z3fold (I haven't actually compared the code) and better in every aspect, why not just "upgrade" z3fold to ztree then?

We have collected a lot of data and it wouldn't fit in the cover message. I believe Ananda will follow up with comparison details on various architectures.

I wouldn't say that ztree is completely based on z3fold, the latter might have served as an inspiration and ztree shares the idea that keeping an integral amount of objects per page is a good thing. With that said, ztree operates on blocks, not on pages which allows for more flexibility.

~Vitaly

#3 lore raw

fio command used in all tests over zram disk with lz4 compressor: fio --bs=4k --randrepeat=1 --randseed=100 --refill_buffers \    --buffer_compress_percentage=VALUE --scramble_buffers=1 \    --direct=1 --loops=15 --numjobs=4 --filename=/dev/zram0 \    --name=seq-write --rw=write --stonewall --name=seq-read \    --rw=read --stonewall --name=seq-readwrite --rw=rw --stonewall \    --name=rand-readwrite --rw=randrw --stonewall where VALUE=30/50/70 depending on particular test  1. Average results: qemu simulation of cortex-a53 on x86 pc;   buffer_compress_page 30/50; disk size 128/192/256 Mb z3fold    WRITE: 42 MB/s    READ: 189 MB/s    READ/WRITE: 31 MB/s    READ/WRITE: 29 MB/s    Compression ratio: 1.5 zsmalloc    WRITE: 88 MB/s    READ: 187 MB/s    READ/WRITE: 54 MB/s    READ/WRITE: 50 MB/s    Compression ratio: 2.4 ztree    WRITE: 94.5 MB/s    READ: 206 MB/s    READ/WRITE: 59.5 MB/s    READ/WRITE: 56 MB/s    Compression ratio: 2.0  2. Average results: armhf Raspberry Pi 3 model B;   buffer_compress_page 50; disk size 256/512 Mb z3fold    WRITE: 120 MB/s    READ: 240 MB/s    READ/WRITE: 85 MB/s    READ/WRITE: 80 MB/s    Compression ratio: 2.0 zsmalloc    WRITE: 127 MB/s    READ: 296 MB/s    READ/WRITE: 91 MB/s    READ/WRITE: 84 MB/s    Compression ratio: 2.5 ztree    WRITE: 132 MB/s    READ: 275 MB/s    READ/WRITE: 94 MB/s    READ/WRITE: 90 MB/s    Compression ratio: 2.05  3. Average results: arm64 Raspberry Pi 4 model B;   buffer_compress_page 50/70; disk size 256/512/1024 Mb z3fold    WRITE: 367 MB/s    READ: 1378 MB/s    READ/WRITE: 265 MB/s    READ/WRITE: 254 MB/s    Compression ratio: 1.4 zsmalloc    WRITE: 595 MB/s    READ: 1397 MB/s    READ/WRITE: 407 MB/s    READ/WRITE: 372 MB/s    Compression ratio: 2.2 ztree    WRITE: 650 MB/s    READ: 1282 MB/s    READ/WRITE: 400 MB/s    READ/WRITE: 381 MB/s    Compression ratio: 1.8 In real cases perfomance could be higher since fio gives extremely uneven load on trees:mainly one tree is loaded from 16.16.09.2021, 13:38, "Vitaly Wool" <[email protected]>:On Thu, Sep 16, 2021 at 12:12 PM Vlastimil Babka <[email protected]> wrote:

 On 9/16/21 10:51, Ananda Badmaev wrote:
 > ztree is a versatile backend for zswap and potentially zram. It got its name > due to the usage of red-black trees to store blocks of compressed objects. > These blocks consist of several consecutive pages and ztree keeps an integer > number of objects per block.
 >
 > For zram, ztree has better worst case malloc() and free() times than zsmalloc, > does not deteriorate over time and has slightly worse but comparable compression > ratio. For zswap, ztree has better worst case malloc() and free() times than > z3fold, better compression ratio than z3fold and supports reclaim unlike zsmalloc. >
 > Signed-off-by: Ananda Badmaev <[email protected]>

 So how many of these allocators do we need? Minimally IMHO some data should be provided for the performance comparison claims above.
 Sounds like if this is based on z3fold (I haven't actually compared the code) and better in every aspect, why not just "upgrade" z3fold to ztree then? We have collected a lot of data and it wouldn't fit in the cover message. I believe Ananda will follow up with comparison details on various architectures.

I wouldn't say that ztree is completely based on z3fold, the latter might have served as an inspiration and ztree shares the idea that keeping an integral amount of objects per page is a good thing. With that said, ztree operates on blocks, not on pages which allows for more flexibility.

~Vitaly