Skip to contentSkip to conversation

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

PATCH Superseded ananda 2 participants 4 messages Nov 19, 2022 – Nov 20, 2022

Subsystems (4)

v7 of 9 Superseded Latest is v9 →

lore
Share & tools
lore

ananda

author
#0 lore raw

PATCH v7 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

v7:
- fixed potential unsigned overflow of block_type in zblock_reclaim_block
- added check on the ability to store objects of size PAGE_SIZE at pool creation time
- added zblock into Documentation/mm/index.rst

 Documentation/mm/index.rst  |   1 +
 Documentation/mm/zblock.rst |  31 ++
 MAINTAINERS                 |   7 +
 mm/Kconfig                  |  17 +
 mm/Makefile                 |   1 +
 mm/zblock.c                 | 642 ++++++++++++++++++++++++++++++++++++
 6 files changed, 699 insertions(+)
 create mode 100644 Documentation/mm/zblock.rst
 create mode 100644 mm/zblock.c
Documentation/mm/index.rst +1 -0
index 4aa12b8be278..3e538e098eb6 100644
@@ -66,4 +66,5 @@ above structured documentation, or deleted if it has served its purpose.
    vmalloced-kernel-stacks
    vmemmap_dedup
    z3fold
+   zblock
    zsmalloc
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 379945f82a64..506edaffbf36 100644
@@ -22690,6 +22690,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 57e1d8c5b505..8836ffae2905 100644
@@ -143,6 +143,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
@@ -151,6 +157,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
@@ -181,6 +188,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 8e105e5b3e29..f2c89390542c 100644
@@ -114,6 +114,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 +642 -0

642 lines not on this page · raw message

Signature · 1 line
2.34.1
#1 lore raw
Quoted 3 lines · ananda

+.. SPDX-License-Identifier: GPL-2.0
+
+.. _block:

Why is the anchor label for doc title _block? Why not _zblock instead?

Quoted 18 lines
(quoted diff) +18 -0
+
+======
+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

Review

Quoted 10 lines
(quoted diff) +10 -0
+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.

The wording can be better (including doc title label suggestion):

---- >8 ----

Documentation/mm/zblock.rst +18 -18
index 5008ce90b54bef..1eb91a8d175dbb 100644
@@ -1,31 +1,31 @@
 .. SPDX-License-Identifier: GPL-2.0
 
-.. _block:
+.. _zblock:
 
 ======
 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.
+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 each list and these only operates on objects of size from the
+corresponding 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
+With zblock, it is 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
+incomplete blocks instead of adding new ones. As a result, in many cases it
+provides 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.
+Like similar allocation method from 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.
+Unlike zbud and z3fold, zblock works well with objects of various sizes -
+including but not limited to highly compressed and poorly compressed, as well
+as cases where both object types exist.

Thanks.

Signature · 1 line
An old man doll... just what I always wanted! - Clara
#2 lore raw

19.11.2022 15:46, Bagas Sanjaya пишет:

Quoted 7 lines · ananda
Quoted 3 lines

+.. SPDX-License-Identifier: GPL-2.0
+
+.. _block:

Why is the anchor label for doc title _block? Why not _zblock instead?

This is a typo. It will be fixed in the next version if necessary.

Quoted 84 lines
Quoted 14 lines
(quoted diff) +14 -0
+
+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

Review

Quoted 10 lines
(quoted diff) +10 -0
+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.

The wording can be better (including doc title label suggestion):

---- >8 ----

Documentation/mm/zblock.rst +18 -18
index 5008ce90b54bef..1eb91a8d175dbb 100644
@@ -1,31 +1,31 @@
  .. SPDX-License-Identifier: GPL-2.0
 
-.. _block:
+.. _zblock:
 
  ======
  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.
+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 each list and these only operates on objects of size from the
+corresponding 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
+With zblock, it is 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
+incomplete blocks instead of adding new ones. As a result, in many cases it
+provides 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.
+Like similar allocation method from 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.
+Unlike zbud and z3fold, zblock works well with objects of various sizes -
+including but not limited to highly compressed and poorly compressed, as well
+as cases where both object types exist.
Quoted 2 lines

Thanks.

I'm not sure there's much point in simply reformulating the text, but in the next version it may be worth a bit changing this text along with other changes.

#3 lore raw
Quoted 90 lines · Ananda Badmaev

19.11.2022 15:46, Bagas Sanjaya пишет:

Quoted 7 lines · ananda
Quoted 3 lines

+.. SPDX-License-Identifier: GPL-2.0
+
+.. _block:

Why is the anchor label for doc title _block? Why not _zblock instead?

This is a typo. It will be fixed in the next version if necessary.

Quoted 78 lines
Quoted 14 lines
(quoted diff) +14 -0
+
+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

Review

Quoted 10 lines
(quoted diff) +10 -0
+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.

The wording can be better (including doc title label suggestion):

---- >8 ----

Documentation/mm/zblock.rst +0 -0
index 5008ce90b54bef..1eb91a8d175dbb 100644
@@ -1,31 +1,31 @@

  .. SPDX-License-Identifier: GPL-2.0
  -.. _block:
+.. _zblock:
    ======
  zblock
  ======
  -Zblock stores integer number of compressed objects per block. These

Documentation/mm/zblock.rst +7 -6
-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.
+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 each list and these only operates on objects of size from the
+corresponding 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 +With zblock, it is possible to densely arrange objects of various sizes, resulting in low internal fragmentation. Also this allocator tries to fill

Documentation/mm/zblock.rst +3 -3
-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
+incomplete blocks instead of adding new ones. As a result, in many cases it
+provides 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

Documentation/mm/zblock.rst +3 -2
-pointer. Instead, it returns an unsigned long handle which encodes actual
-location of the allocated object.
+Like similar allocation method from 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

Documentation/mm/zblock.rst +3 -2
-highly compressed and poorly compressed including cases where both types
-are present.
+Unlike zbud and z3fold, zblock works well with objects of various sizes -
+including but not limited to highly compressed and poorly compressed, as well
+as cases where both object types exist.
Quoted 5 lines
Quoted 2 lines

Thanks.

I'm not sure there's much point in simply reformulating the text, but in the next version it may be worth a bit changing this text along with other changes.

OK, thanks.

Next time, don't forget to Cc linux-doc list for patches touching Documentation/. Adding one since you don't.

Signature · 1 line
An old man doll... just what I always wanted! - Clara