Skip to contentSkip to conversation

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

PATCH Superseded Ananda 2 participants 2 messages Mar 1, 2022 – Mar 2, 2022

Subsystems (2)

v2 of 9 Superseded Latest is v9 →

lore
Share & tools
lore

Ananda

author
#0 lore raw

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
index dd36acc87ce6..bde8ee006953 100644
@@ -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
index 356f4f2c779e..a31f6e46e0af 100644
@@ -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
index d6c0042e3aa0..6bb4582632b1 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 +754 -0

754 lines not on this page · raw message

Signature · 1 line
2.30.2
#1 lore raw
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 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.

Quoted 1 line