[PATCH v3] z3fold: add shrinker

[Vitaly Wool]

This patch implements shrinker for z3fold. This shrinker
implementation does not free up any pages directly but it allows
for a denser placement of compressed objects which results in
less actual pages consumed and higher compression ratio therefore.

This patch has been checked with the latest Linus's tree.

Signed-off-by: Vitaly Wool 
---
 mm/z3fold.c | 157 ++--
 1 file changed, 132 insertions(+), 25 deletions(-)

diff --git a/mm/z3fold.c b/mm/z3fold.c
index 8f9e89c..8d35b4a 100644
--- a/mm/z3fold.c
+++ b/mm/z3fold.c
@@ -30,6 +30,7 @@
 #include 
 #include 
 #include 
+#include 
 
 /*
  * Structures
@@ -69,8 +70,10 @@ struct z3fold_ops {
  * @lru:   list tracking the z3fold pages in LRU order by most recently
  * added buddy.
  * @pages_nr:  number of z3fold pages in the pool.
+ * @unbuddied_nr:  number of unbuddied z3fold pages in the pool.
  * @ops:   pointer to a structure of user defined operations specified at
  * pool creation time.
+ * @shrinker:  shrinker structure to optimize page layout in background
  *
  * This structure is allocated at pool creation time and maintains metadata
  * pertaining to a particular z3fold pool.
@@ -81,9 +84,11 @@ struct z3fold_pool {
struct list_head buddied;
struct list_head lru;
u64 pages_nr;
+   u64 unbuddied_nr;
const struct z3fold_ops *ops;
struct zpool *zpool;
const struct zpool_ops *zpool_ops;
+   struct shrinker shrinker;
 };
 
 enum buddy {
@@ -134,6 +139,9 @@ static int size_to_chunks(size_t size)
 #define for_each_unbuddied_list(_iter, _begin) \
for ((_iter) = (_begin); (_iter) < NCHUNKS; (_iter)++)
 
+#define for_each_unbuddied_list_down(_iter, _end) \
+   for ((_iter) = (_end); (_iter) > 0; (_iter)--)
+
 /* Initializes the z3fold header of a newly allocated z3fold page */
 static struct z3fold_header *init_z3fold_page(struct page *page)
 {
@@ -209,6 +217,100 @@ static int num_free_chunks(struct z3fold_header *zhdr)
return nfree;
 }
 
+/* Has to be called with lock held */
+static int z3fold_compact_page(struct z3fold_header *zhdr, bool sync)
+{
+   struct page *page = virt_to_page(zhdr);
+   void *beg = zhdr;
+
+
+   if (!test_bit(MIDDLE_CHUNK_MAPPED, >private)) {
+   if (zhdr->middle_chunks != 0 &&
+   zhdr->first_chunks == 0 &&
+   zhdr->last_chunks == 0) {
+   memmove(beg + ZHDR_SIZE_ALIGNED,
+   beg + (zhdr->start_middle << CHUNK_SHIFT),
+   zhdr->middle_chunks << CHUNK_SHIFT);
+   zhdr->first_chunks = zhdr->middle_chunks;
+   zhdr->middle_chunks = 0;
+   zhdr->start_middle = 0;
+   zhdr->first_num++;
+   return 1;
+   }
+   if (sync)
+   goto out;
+
+   /* moving data is expensive, so let's only do that if
+* there's substantial gain (2+ chunks)
+*/
+   if (zhdr->middle_chunks != 0 && zhdr->first_chunks != 0 &&
+   zhdr->last_chunks == 0 &&
+   zhdr->start_middle > zhdr->first_chunks + 2) {
+   unsigned short new_start = zhdr->first_chunks + 1;
+   memmove(beg + (new_start << CHUNK_SHIFT),
+   beg + (zhdr->start_middle << CHUNK_SHIFT),
+   zhdr->middle_chunks << CHUNK_SHIFT);
+   zhdr->start_middle = new_start;
+   return 1;
+   }
+   if (zhdr->middle_chunks != 0 && zhdr->last_chunks != 0 &&
+   zhdr->first_chunks == 0 &&
+   zhdr->middle_chunks + zhdr->last_chunks <=
+   NCHUNKS - zhdr->start_middle - 2) {
+   unsigned short new_start = NCHUNKS - zhdr->last_chunks -
+   zhdr->middle_chunks;
+   memmove(beg + (new_start << CHUNK_SHIFT),
+   beg + (zhdr->start_middle << CHUNK_SHIFT),
+   zhdr->middle_chunks << CHUNK_SHIFT);
+   zhdr->start_middle = new_start;
+   return 1;
+   }
+   }
+out:
+   return 0;
+}
+
+static unsigned long z3fold_shrink_count(struct shrinker *shrink,
+   struct shrink_control *sc)
+{
+   struct z3fold_pool *pool = container_of(shrink, struct z3fold_pool,
+   shrinker);
+
+   return pool->unbuddied_nr;
+}
+
+static unsigned long z3fold_shrink_scan(struct shrinker *shrink,
+   struct shrink_control *sc)
+{
+   struct z3fold_pool *pool = container_of(shrink, struct 

[PATCH v3] z3fold: add shrinker

[Vitaly Wool]

This patch implements shrinker for z3fold. This shrinker
implementation does not free up any pages directly but it allows
for a denser placement of compressed objects which results in
less actual pages consumed and higher compression ratio therefore.

This patch has been checked with the latest Linus's tree.

Signed-off-by: Vitaly Wool 
---
 mm/z3fold.c | 157 ++--
 1 file changed, 132 insertions(+), 25 deletions(-)

diff --git a/mm/z3fold.c b/mm/z3fold.c
index 8f9e89c..8d35b4a 100644
--- a/mm/z3fold.c
+++ b/mm/z3fold.c
@@ -30,6 +30,7 @@
 #include 
 #include 
 #include 
+#include 
 
 /*
  * Structures
@@ -69,8 +70,10 @@ struct z3fold_ops {
  * @lru:   list tracking the z3fold pages in LRU order by most recently
  * added buddy.
  * @pages_nr:  number of z3fold pages in the pool.
+ * @unbuddied_nr:  number of unbuddied z3fold pages in the pool.
  * @ops:   pointer to a structure of user defined operations specified at
  * pool creation time.
+ * @shrinker:  shrinker structure to optimize page layout in background
  *
  * This structure is allocated at pool creation time and maintains metadata
  * pertaining to a particular z3fold pool.
@@ -81,9 +84,11 @@ struct z3fold_pool {
struct list_head buddied;
struct list_head lru;
u64 pages_nr;
+   u64 unbuddied_nr;
const struct z3fold_ops *ops;
struct zpool *zpool;
const struct zpool_ops *zpool_ops;
+   struct shrinker shrinker;
 };
 
 enum buddy {
@@ -134,6 +139,9 @@ static int size_to_chunks(size_t size)
 #define for_each_unbuddied_list(_iter, _begin) \
for ((_iter) = (_begin); (_iter) < NCHUNKS; (_iter)++)
 
+#define for_each_unbuddied_list_down(_iter, _end) \
+   for ((_iter) = (_end); (_iter) > 0; (_iter)--)
+
 /* Initializes the z3fold header of a newly allocated z3fold page */
 static struct z3fold_header *init_z3fold_page(struct page *page)
 {
@@ -209,6 +217,100 @@ static int num_free_chunks(struct z3fold_header *zhdr)
return nfree;
 }
 
+/* Has to be called with lock held */
+static int z3fold_compact_page(struct z3fold_header *zhdr, bool sync)
+{
+   struct page *page = virt_to_page(zhdr);
+   void *beg = zhdr;
+
+
+   if (!test_bit(MIDDLE_CHUNK_MAPPED, >private)) {
+   if (zhdr->middle_chunks != 0 &&
+   zhdr->first_chunks == 0 &&
+   zhdr->last_chunks == 0) {
+   memmove(beg + ZHDR_SIZE_ALIGNED,
+   beg + (zhdr->start_middle << CHUNK_SHIFT),
+   zhdr->middle_chunks << CHUNK_SHIFT);
+   zhdr->first_chunks = zhdr->middle_chunks;
+   zhdr->middle_chunks = 0;
+   zhdr->start_middle = 0;
+   zhdr->first_num++;
+   return 1;
+   }
+   if (sync)
+   goto out;
+
+   /* moving data is expensive, so let's only do that if
+* there's substantial gain (2+ chunks)
+*/
+   if (zhdr->middle_chunks != 0 && zhdr->first_chunks != 0 &&
+   zhdr->last_chunks == 0 &&
+   zhdr->start_middle > zhdr->first_chunks + 2) {
+   unsigned short new_start = zhdr->first_chunks + 1;
+   memmove(beg + (new_start << CHUNK_SHIFT),
+   beg + (zhdr->start_middle << CHUNK_SHIFT),
+   zhdr->middle_chunks << CHUNK_SHIFT);
+   zhdr->start_middle = new_start;
+   return 1;
+   }
+   if (zhdr->middle_chunks != 0 && zhdr->last_chunks != 0 &&
+   zhdr->first_chunks == 0 &&
+   zhdr->middle_chunks + zhdr->last_chunks <=
+   NCHUNKS - zhdr->start_middle - 2) {
+   unsigned short new_start = NCHUNKS - zhdr->last_chunks -
+   zhdr->middle_chunks;
+   memmove(beg + (new_start << CHUNK_SHIFT),
+   beg + (zhdr->start_middle << CHUNK_SHIFT),
+   zhdr->middle_chunks << CHUNK_SHIFT);
+   zhdr->start_middle = new_start;
+   return 1;
+   }
+   }
+out:
+   return 0;
+}
+
+static unsigned long z3fold_shrink_count(struct shrinker *shrink,
+   struct shrink_control *sc)
+{
+   struct z3fold_pool *pool = container_of(shrink, struct z3fold_pool,
+   shrinker);
+
+   return pool->unbuddied_nr;
+}
+
+static unsigned long z3fold_shrink_scan(struct shrinker *shrink,
+   struct shrink_control *sc)
+{
+   struct z3fold_pool *pool = container_of(shrink, struct z3fold_pool,
+