Skip to contentSkip to conversation

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

PATCH Superseded ananda 1 participant 1 message Oct 5, 2022

Subsystems (4)

v6 of 9 Superseded Latest is v9 →

lore
Share & tools
lore

ananda

author
#0 lore raw

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

From: Ananda <[email protected]>

Zblock stores integer number of compressed objects per zblock block.
These blocks consist of several physical pages (1/2/4/8) and are arranged in linked lists.
The range from 0 to PAGE_SIZE is divided into the number of intervals
corresponding to the number of lists and each list only operates objects of size from its interval. Thus the block lists are isolated from each other, which makes it possible to simultaneously perform actions with several objects from different lists.
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.
Zblock does not require MMU and also is superior to zsmalloc with
regard to the worst execution times, thus allowing for better response time and real-time characteristics of the whole system.

---

v2: fixed compiler warnings

v3: added documentation and const modifier to struct tree_descr

v4: - fixed gfp flags for block allocation
- fixed potential memory leak when allocating blocks
- resolved some issues with code style and warnings from checkpatch (except warning about single line config symbol description)
- moved test results from documentation to changelog

v5: - "direct" handle mapping and use of linked lists instead of red-black
trees resulting in faster operations and a bit simpler code
- renamed ztree -> zblock
- edited various comments and descriptions

v6: - fixed tabs (tab size 8 instead of 4)
- evict also pages that have not been mapped

 Documentation/mm/zblock.rst |  31 ++
 MAINTAINERS                 |   7 +
 mm/Kconfig                  |  17 +
 mm/Makefile                 |   1 +
 mm/zblock.c                 | 638 ++++++++++++++++++++++++++++++++++++
 5 files changed, 694 insertions(+)
 create mode 100644 Documentation/mm/zblock.rst
 create mode 100644 mm/zblock.c
Documentation/mm/zblock.rst new file +31 -0
new file mode 100644
index 000000000000..5008ce90b54b
@@ -0,0 +1,31 @@
+.. SPDX-License-Identifier: GPL-2.0
+
+.. _block:
+
+======
+zblock
+======
+
+Zblock stores integer number of compressed objects per block. These
+blocks consist of several consecutive physical pages (from 1 to 8) and
+are arranged in lists. The range from 0 to PAGE_SIZE is divided into the
+number of intervals corresponding to the number of lists and each list
+only operates objects of size from its interval. Thus the block lists are
+isolated from each other, which makes it possible to simultaneously
+perform actions with several objects from different lists.
+
+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. Zblock does
+not require MMU and also is superior to zsmalloc 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 zblock_alloc() does not return a dereferenceable
+pointer. Instead, it returns an unsigned long handle which encodes actual
+location of the allocated object.
+
+Unlike zbud and z3fold zblock works well with objects of various sizes - both
+highly compressed and poorly compressed including cases where both types
+are present.
MAINTAINERS +7 -0
index f1390b8270b2..014fb19eb2cc 100644
@@ -22457,6 +22457,13 @@ L:	[email protected]
 S:	Maintained
 F:	mm/z3fold.c
 
+ZBLOCK COMPRESSED PAGE ALLOCATOR
+M:	Ananda Badmaev <[email protected]>
+M:	Vitaly Wool <[email protected]>
+L:	[email protected]
+S:	Maintained
+F:	mm/zblock.c
+
 ZD1211RW WIRELESS DRIVER
 M:	Ulrich Kunitz <[email protected]>
 L:	[email protected]
mm/Kconfig +17 -0
index 0331f1461f81..470c80f5726d 100644
@@ -149,6 +149,12 @@ config ZSWAP_ZPOOL_DEFAULT_ZSMALLOC
 	select ZSMALLOC
 	help
 	  Use the zsmalloc allocator as the default allocator.
+
+config ZSWAP_ZPOOL_DEFAULT_ZBLOCK
+	bool "zblock"
+	select ZBLOCK
+	help
+	  Use the zblock allocator as the default allocator.
 endchoice
 
 config ZSWAP_ZPOOL_DEFAULT
@@ -157,6 +163,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 "zblock" if ZSWAP_ZPOOL_DEFAULT_ZBLOCK
        default ""
 
 config ZBUD
@@ -187,6 +194,16 @@ config ZSMALLOC
 	  pages of various compression levels efficiently. It achieves
 	  the highest storage density with the least amount of fragmentation.
 
+config ZBLOCK
+	tristate "Simple block allocator (zblock)"
+	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 number of physical pages being a power of 2.
+	  zblock provides fast read/write, limited worst case time for
+	  operations and good compression ratio in most scenarios.
+
 config ZSMALLOC_STAT
 	bool "Export zsmalloc statistics"
 	depends on ZSMALLOC
mm/Makefile +1 -0
index 9a564f836403..eb7235da6e61 100644
@@ -110,6 +110,7 @@ obj-$(CONFIG_ZPOOL)	+= zpool.o
 obj-$(CONFIG_ZBUD)	+= zbud.o
 obj-$(CONFIG_ZSMALLOC)	+= zsmalloc.o
 obj-$(CONFIG_Z3FOLD)	+= z3fold.o
+obj-$(CONFIG_ZBLOCK)	+= zblock.o
 obj-$(CONFIG_GENERIC_EARLY_IOREMAP) += early_ioremap.o
 obj-$(CONFIG_CMA)	+= cma.o
 obj-$(CONFIG_MEMORY_BALLOON) += balloon_compaction.o
mm/zblock.c new file +638 -0

638 lines not on this page · raw message

Signature · 1 line
2.34.1