Re: [PATCH v3] mm: add ztree - new allocator for use via zpool API

[Mike Rapoport <rppt@kernel.org>]

On Mon, Mar 07, 2022 at 05:27:24PM +0300, Ananda wrote:
> From: Ananda Badmaev <a.badmaev@clicknet.pro>
> 
>     Ztree stores integer number of compressed objects per ztree block.
> These blocks consist of several physical pages (from 1 to 8) and are
> arranged in trees.
>     The range from 0 to PAGE_SIZE is divided into the number of intervals
> corresponding to the number of trees and each tree only operates objects of
> size from its interval. Thus the block trees are isolated from each other,
> which makes it possible to simultaneously perform actions with several
> objects from different trees.
>     Blocks make it possible to densely arrange objects of various sizes
> resulting in low internal fragmentation. Also this allocator tries to fill
> incomplete blocks instead of adding new ones thus in many cases providing a
> compression ratio substantially higher than z3fold and zbud.
>     Apart from greater flexibility, ztree is significantly superior to other
> zpool backends with regard to the worst execution times, thus allowing for
> better response time and real-time characteristics of the whole system.
> 
> Signed-off-by: Ananda Badmaev <a.badmaev@clicknet.pro>
> ---
> 
> v2: fixed compiler warnings
> 
> v3: added documentation and const modifier to struct tree_descr
> 
>  Documentation/vm/ztree.rst | 104 +++++
>  MAINTAINERS                |   7 +
>  mm/Kconfig                 |  18 +
>  mm/Makefile                |   1 +
>  mm/ztree.c                 | 754 +++++++++++++++++++++++++++++++++++++
>  5 files changed, 884 insertions(+)
>  create mode 100644 Documentation/vm/ztree.rst
>  create mode 100644 mm/ztree.c

There are a lot of style issues, please run scripts/checkpatch.pl.
 
> diff --git a/Documentation/vm/ztree.rst b/Documentation/vm/ztree.rst
> new file mode 100644
> index 000000000000..78cad0a6d616
> --- /dev/null
> +++ b/Documentation/vm/ztree.rst
> @@ -0,0 +1,104 @@
> +.. _ztree:
> +
> +=====
> +ztree
> +=====
> +
> +Ztree stores integer number of compressed objects per ztree block. These
> +blocks consist of several consecutive physical pages (from 1 to 8) and
> +are arranged in trees. The range from 0 to PAGE_SIZE is divided into the
> +number of intervals corresponding to the number of trees and each tree
> +only operates objects of size from its interval. Thus the block trees are
> +isolated from each other, which makes it possible to simultaneously
> +perform actions with several objects from different trees.
> +
> +Blocks make it possible to densely arrange objects of various sizes
> +resulting in low internal fragmentation. Also this allocator tries to fill
> +incomplete blocks instead of adding new ones thus in many cases providing
> +a compression ratio substantially higher than z3fold and zbud. Apart from
> +greater flexibility, ztree is significantly superior to other zpool
> +backends with regard to the worst execution times, thus allowing for better
> +response time and real-time characteristics of the whole system.
> +
> +Like z3fold and zsmalloc ztree_alloc() does not return a dereferenceable
> +pointer. Instead, it returns an unsigned long handle which encodes actual
> +location of the allocated object.
> +
> +Unlike others ztree works well with objects of various sizes - both highly
> +compressed and poorly compressed including cases where both types are present.
> +
> +Tests
> +=====

I don't think the sections below belong to the Documentation. IMO they are
more suitable to the changelog
> +
> +Test platform
> +-------------
> +
> +Qemu arm64 virtual board with debian 11.
> +
> +Kernel
> +------
> +
> +Linux 5.17-rc6 with ztree and zram over zpool patch. Additionally, counters and
> +time measurements using ktime_get_ns() have been added to ZPOOL API.
> +
> +Tools
> +-----
> +
> +ZRAM disks of size 1000M/1500M/2G, fio 3.25.
> +
> +Test description
> +----------------
> +
> +Run 2 fio scripts in parallel - one with VALUE=50, other with VALUE=70.
> +This emulates page content heterogeneity.
> +
> +fio --bs=4k --randrepeat=1 --randseed=100 --refill_buffers \
> +    --scramble_buffers=1 --buffer_compress_percentage=VALUE \
> +    --direct=1 --loops=1 --numjobs=1 --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
> +
> +Results
> +-------
> +
> +ztree
> +~~~~~
> +
> +* average malloc time (us): 3.8
> +* average free time (us): 3.1
> +* average map time (us): 4.5
> +* average unmap time (us): 1.2
> +* worst zpool op time (us): ~2200
> +* total zpool ops exceeding 1000 us: 29
> +
> +
> +zsmalloc
> +~~~~~~~~
> +
> +* average malloc time (us): 10.3
> +* average free time (us): 6.5
> +* average map time (us): 3.2
> +* average unmap time (us): 1.2
> +* worst zpool op time (us): ~6200
> +* total zpool ops exceeding 1000 us: 1031
> +
> +z3fold
> +~~~~~~
> +
> +* average malloc time (us): 20.8
> +* average free time (us): 29.9
> +* average map time (us): 3.4
> +* average unmap time (us): 1.4
> +* worst zpool op time (us): ~4900
> +* total zpool ops exceeding 1000 us: 100
> +
> +zbud
> +~~~~
> +
> +* average malloc time (us): 8.1
> +* average free time (us): 4.0
> +* average map time (us): 0.3
> +* average unmap time (us): 0.3
> +* worst zpool op time (us): ~9400
> +* total zpool ops exceeding 1000 us: 727

-- 
Sincerely yours,
Mike.