mm: add zblock - new allocator for use via zpool API
Subsystems (4)
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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
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
@@ -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
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_zblockinstead?
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 worstReview
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@@ -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.
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_zblockinstead?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 worstReview
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@@ -1,31 +1,31 @@.. SPDX-License-Identifier: GPL-2.0
-.._block:
+.._zblock:
======
zblock
======
-Zblock stores integer number of compressed objects per block. TheseDocumentation/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 worstexecution times, thus allowing for better response time and real-time characteristics of the whole system.
-Like z3fold and zsmalloczblock_alloc()does not return a dereferenceableDocumentation/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