z3fold: the 3-fold allocator for compressed pages

This patch introduces z3fold, a special purpose allocator for storing
compressed pages.  It is designed to store up to three compressed pages
per physical page.  It is a ZBUD derivative which allows for higher
compression ratio keeping the simplicity and determinism of its
predecessor.

This patch comes as a follow-up to the discussions at the Embedded Linux
Conference in San-Diego related to the talk [1].  The outcome of these
discussions was that it would be good to have a compressed page
allocator as stable and deterministic as zbud with with higher
compression ratio.

To keep the determinism and simplicity, z3fold, just like zbud, always
stores an integral number of compressed pages per page, but it can store
up to 3 pages unlike zbud which can store at most 2.  Therefore the
compression ratio goes to around 2.6x while zbud's one is around 1.7x.

The patch is based on the latest linux.git tree.

This version has been updated after testing on various simulators (e.g.
ARM Versatile Express, MIPS Malta, x86_64/Haswell) and basing on
comments from Dan Streetman [3].

[1] https://openiotelc2016.sched.org/event/6DAC/swapping-and-embedded-compression-relieves-the-pressure-vitaly-wool-softprise-consulting-ou
[2] https://lkml.org/lkml/2016/4/21/799
[3] https://lkml.org/lkml/2016/5/4/852

Link: http://lkml.kernel.org/r/20160509151753.ec3f9fda3c9898d31ff52a32@gmail.com
Signed-off-by: Vitaly Wool <vitalywool@gmail.com>
Cc: Seth Jennings <sjenning@redhat.com>
Cc: Dan Streetman <ddstreet@ieee.org>
Cc: Vlastimil Babka <vbabka@suse.cz>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

1 files changed, 11 insertions, 1 deletions

diff --git a/mm/Kconfig b/mm/Kconfig
index b0432b71137d..1a6a28ebcb8b 100644
--- a/mm/Kconfig
+++ b/mm/Kconfig
@@ -567,7 +567,7 @@ config ZPOOL
           zsmalloc.
 
 config ZBUD
-        tristate "Low density storage for compressed pages"
+        tristate "Low (Up to 2x) density storage for compressed pages"
         default n
         help
           A special purpose allocator for storing compressed pages.
@@ -576,6 +576,16 @@ config ZBUD
           deterministic reclaim properties that make it preferable to a higher
           density approach when reclaim will be used.
 
+config Z3FOLD
+        tristate "Up to 3x density storage for compressed pages"
+        depends on ZPOOL
+        default n
+        help
+          A special purpose allocator for storing compressed pages.
+          It is designed to store up to three compressed pages per physical
+          page. It is a ZBUD derivative so the simplicity and determinism are
+          still there.
+
 config ZSMALLOC
         tristate "Memory allocator for compressed pages"
         depends on MMU