mm: add ztree - new allocator for use via zpool API
Subsystems (2)
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
@@ -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
@@ -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
@@ -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
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()andfree()times than zsmalloc, does not deteriorate over time and has slightly worse but comparable compression ratio. For zswap, ztree has better worst casemalloc()andfree()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?
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()andfree()times than zsmalloc, does not deteriorate over time and has slightly worse but comparable compression ratio. For zswap, ztree has better worst casemalloc()andfree()times than z3fold, better compression ratio than z3fold and supports reclaim unlike zsmalloc.
Quoted 6 lines
Quoted 1 line
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
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