mm: add ztree - new allocator for use via zpool API
Subsystems (2)
PATCH v2 1/1 mm: add ztree - new allocator for use via zpool API
From: Ananda Badmaev <[email protected]>
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.
--- MAINTAINERS | 7 + mm/Kconfig | 18 ++ mm/Makefile | 1 + mm/ztree.c | 754 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 780 insertions(+) create mode 100644 mm/ztree.c
MAINTAINERS +7 -0
@@ -21027,6 +21027,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: Ulrich Kunitz <[email protected]> L: [email protected]
mm/Kconfig +18 -0
@@ -646,6 +646,12 @@ config ZSWAP_ZPOOL_DEFAULT_ZSMALLOC select ZSMALLOC help Use the zsmalloc allocator as the default allocator. + +config ZSWAP_ZPOOL_DEFAULT_ZTREE + bool "ztree" + select ZTREE + help + Use the ztree allocator as the default allocator. endchoice config ZSWAP_ZPOOL_DEFAULT
@@ -654,6 +660,7 @@ config ZSWAP_ZPOOL_DEFAULT default "zbud" if ZSWAP_ZPOOL_DEFAULT_ZBUD default "z3fold" if ZSWAP_ZPOOL_DEFAULT_Z3FOLD default "zsmalloc" if ZSWAP_ZPOOL_DEFAULT_ZSMALLOC + default "ztree" if ZSWAP_ZPOOL_DEFAULT_ZTREE default "" config ZSWAP_DEFAULT_ON
@@ -712,6 +719,17 @@ config ZSMALLOC_STAT information to userspace via debugfs. If unsure, say N. +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 write, limited worst case time for + operations and good compression ratio in most scenarios. + config GENERIC_EARLY_IOREMAP bool
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 +754 -0
754 lines not on this page · raw message
Signature · 1 line
2.30.2
Quoted 14 lines
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 toPAGE_SIZEis 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.
Quoted 1 line
Signed-off-by Ananda Badmaev <[email protected]>