diff mbox series

[PATCH/RESEND] mm: add ztree - new allocator for use via zpool API

Message ID 20220228110546.151513-1-a.badmaev@clicknet.pro (mailing list archive)
State New
Headers show
Series [PATCH/RESEND] mm: add ztree - new allocator for use via zpool API | expand

Commit Message

Ananda Badmaev Feb. 28, 2022, 11:05 a.m. UTC
From: Ananda Badmaev <a.badmaev@clicknet.pro>

    Ztree stores integer number of compressed objects per ztree block. These
blocks consist of several physical pages (from 1 to 8) and are arranged in trees.
    The range from 0 to PAGE_SIZE is divided into the number of intervals
corresponding to the number of trees and each tree only operates objects of size
from its interval. Thus the block trees are isolated from each other, which makes it
possible to simultaneously perform actions with several objects from different trees.
    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.
    Apart from greater flexibility, ztree is significantly superior to other zpool
backends with regard to the worst execution times, thus allowing for better response
time and real-time characteristics of the whole system.

Signed-off-by: Ananda Badmaev <a.badmaev@clicknet.pro>
---
 MAINTAINERS |   7 +
 mm/Kconfig  |  18 ++
 mm/Makefile |   1 +
 mm/ztree.c  | 754 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 780 insertions(+)
 create mode 100644 mm/ztree.c

Comments

kernel test robot Feb. 28, 2022, 5:35 p.m. UTC | #1
Hi Ananda,

I love your patch! Perhaps something to improve:

[auto build test WARNING on hnaz-mm/master]

url:    https://github.com/0day-ci/linux/commits/Ananda/mm-add-ztree-new-allocator-for-use-via-zpool-API/20220228-190619
base:   https://github.com/hnaz/linux-mm master
config: sh-allmodconfig (https://download.01.org/0day-ci/archive/20220228/202202282010.qo0U7ATX-lkp@intel.com/config)
compiler: sh4-linux-gcc (GCC) 11.2.0
reproduce (this is a W=1 build):
        wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # https://github.com/0day-ci/linux/commit/a30d4197bd92974faeafba46d6e74d3d8943c88c
        git remote add linux-review https://github.com/0day-ci/linux
        git fetch --no-tags linux-review Ananda/mm-add-ztree-new-allocator-for-use-via-zpool-API/20220228-190619
        git checkout a30d4197bd92974faeafba46d6e74d3d8943c88c
        # save the config file to linux build tree
        mkdir build_dir
        COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-11.2.0 make.cross O=build_dir ARCH=sh SHELL=/bin/bash M=mm/

If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <lkp@intel.com>

All warnings (new ones prefixed by >>):

>> mm/ztree.c:236:6: warning: no previous prototype for 'free_block_tree' [-Wmissing-prototypes]
     236 | void free_block_tree(struct ztree_pool *pool, int block_type)
         |      ^~~~~~~~~~~~~~~
>> mm/ztree.c:282:20: warning: no previous prototype for 'ztree_create_pool' [-Wmissing-prototypes]
     282 | struct ztree_pool *ztree_create_pool(gfp_t gfp, const struct ztree_ops *ops)
         |                    ^~~~~~~~~~~~~~~~~
>> mm/ztree.c:327:6: warning: no previous prototype for 'ztree_destroy_pool' [-Wmissing-prototypes]
     327 | void ztree_destroy_pool(struct ztree_pool *pool)
         |      ^~~~~~~~~~~~~~~~~~
>> mm/ztree.c:350:5: warning: no previous prototype for 'ztree_alloc' [-Wmissing-prototypes]
     350 | int ztree_alloc(struct ztree_pool *pool, size_t size, gfp_t gfp,
         |     ^~~~~~~~~~~
>> mm/ztree.c:414:6: warning: no previous prototype for 'ztree_free' [-Wmissing-prototypes]
     414 | void ztree_free(struct ztree_pool *pool, unsigned long handle)
         |      ^~~~~~~~~~
>> mm/ztree.c:474:5: warning: no previous prototype for 'ztree_reclaim_block' [-Wmissing-prototypes]
     474 | int ztree_reclaim_block(struct ztree_pool *pool)
         |     ^~~~~~~~~~~~~~~~~~~
>> mm/ztree.c:554:7: warning: no previous prototype for 'ztree_map' [-Wmissing-prototypes]
     554 | void *ztree_map(struct ztree_pool *pool, unsigned long handle)
         |       ^~~~~~~~~
>> mm/ztree.c:591:6: warning: no previous prototype for 'ztree_unmap' [-Wmissing-prototypes]
     591 | void ztree_unmap(struct ztree_pool *pool, unsigned long handle)
         |      ^~~~~~~~~~~
>> mm/ztree.c:628:5: warning: no previous prototype for 'ztree_get_pool_size' [-Wmissing-prototypes]
     628 | u64 ztree_get_pool_size(struct ztree_pool *pool)
         |     ^~~~~~~~~~~~~~~~~~~

Kconfig warnings: (for reference only)
   WARNING: unmet direct dependencies detected for SND_SOC_LPASS_RX_MACRO
   Depends on SOUND && !UML && SND && SND_SOC && COMMON_CLK
   Selected by
   - SND_SOC_SC7280 && SOUND && !UML && SND && SND_SOC && SND_SOC_QCOM && I2C && SOUNDWIRE
   WARNING: unmet direct dependencies detected for SND_SOC_LPASS_TX_MACRO
   Depends on SOUND && !UML && SND && SND_SOC && COMMON_CLK
   Selected by
   - SND_SOC_SC7280 && SOUND && !UML && SND && SND_SOC && SND_SOC_QCOM && I2C && SOUNDWIRE


vim +/free_block_tree +236 mm/ztree.c

   231	
   232	
   233	/*
   234	 * free block tree with blocks of particular type
   235	 */
 > 236	void free_block_tree(struct ztree_pool *pool, int block_type)
   237	{
   238		struct ztree_block *block, *tmp;
   239		struct block_tree *tree;
   240	
   241		tree = &(pool->block_trees)[block_type];
   242		spin_lock(&tree->lock);
   243		rbtree_postorder_for_each_entry_safe(block, tmp, &tree->root, block_node) {
   244			free_pages((unsigned long)block->compressed_data,
   245						tree_desc[block_type].order);
   246			kmem_cache_free(pool->block_cache, block);
   247		}
   248		spin_unlock(&tree->lock);
   249	}
   250	
   251	/*
   252	 * Encodes the handle of a particular slot in the pool using metadata
   253	 */
   254	static inline unsigned long metadata_to_handle(unsigned long block_type,
   255						unsigned long block_index, unsigned long slot)
   256	{
   257		return (block_type << BLOCK_TYPE_SHIFT) + (block_index << SLOT_BITS) + slot;
   258	}
   259	
   260	
   261	/* Returns block type, block index and slot in the pool corresponding to handle */
   262	static inline void handle_to_metadata(unsigned long handle, unsigned long *block_type,
   263							unsigned long *block_index, unsigned long *slot)
   264	{
   265		*block_type = handle >> BLOCK_TYPE_SHIFT;
   266		*block_index = (handle & BLOCK_INDEX_MASK) >> SLOT_BITS;
   267		*slot = handle & SLOT_MASK;
   268	}
   269	
   270	
   271	/*****************
   272	 * API Functions
   273	 *****************/
   274	/**
   275	 * ztree_create_pool() - create a new ztree pool array
   276	 * @gfp:	gfp flags when allocating the ztree pool structure
   277	 * @ops:	user-defined operations for the ztree pool
   278	 *
   279	 * Return: pointer to the new ztree pool or NULL if the metadata allocation
   280	 * failed.
   281	 */
 > 282	struct ztree_pool *ztree_create_pool(gfp_t gfp, const struct ztree_ops *ops)
   283	{
   284		struct ztree_pool *pool;
   285		struct block_tree *tree;
   286		int i, block_types_nr;
   287	
   288		pool = kmalloc(sizeof(struct ztree_pool), gfp);
   289		if (!pool)
   290			return NULL;
   291	
   292		block_types_nr = ARRAY_SIZE(tree_desc);
   293	
   294		pool->block_cache = kmem_cache_create("ztree_blocks",
   295						sizeof(struct ztree_block), 0, 0, NULL);
   296		if (!pool->block_cache) {
   297			kfree(pool);
   298			return NULL;
   299		}
   300	
   301		pool->block_trees = kmalloc(block_types_nr * sizeof(struct block_tree), gfp);
   302		if (!pool->block_trees) {
   303			kmem_cache_destroy(pool->block_cache);
   304			kfree(pool);
   305			return NULL;
   306		}
   307	
   308		/* init each basic block tree */
   309		for (i = 0; i < block_types_nr; i++) {
   310			tree = &(pool->block_trees)[i];
   311			spin_lock_init(&tree->lock);
   312			tree->root = RB_ROOT;
   313			tree->last_block = NULL;
   314			tree->current_block = NULL;
   315			tree->counter = 0;
   316			tree->block_count = 0;
   317		}
   318		pool->ops = ops;
   319		return pool;
   320	}
   321	
   322	/**
   323	 * ztree_destroy_pool() - destroys an existing ztree pool
   324	 * @pool:	the ztree pool to be destroyed
   325	 *
   326	 */
 > 327	void ztree_destroy_pool(struct ztree_pool *pool)
   328	{
   329		int i;
   330	
   331		for (i = 0; i < ARRAY_SIZE(tree_desc); i++)
   332			free_block_tree(pool, i);
   333		kmem_cache_destroy(pool->block_cache);
   334		kfree(pool->block_trees);
   335		kfree(pool);
   336	}
   337	
   338	
   339	/**
   340	 * ztree_alloc() - allocates a slot of appropriate size
   341	 * @pool:	ztree pool from which to allocate
   342	 * @size:	size in bytes of the desired allocation
   343	 * @gfp:	gfp flags used if the pool needs to grow
   344	 * @handle:	handle of the new allocation
   345	 *
   346	 * Return: 0 if success and handle is set, otherwise -EINVAL if the size or
   347	 * gfp arguments are invalid or -ENOMEM if the pool was unable to allocate
   348	 * a new slot.
   349	 */
 > 350	int ztree_alloc(struct ztree_pool *pool, size_t size, gfp_t gfp,
   351				unsigned long *handle)
   352	{
   353		unsigned long block_type, slot;
   354		struct ztree_block *block;
   355		struct block_tree *tree;
   356	
   357		if (!size)
   358			return -EINVAL;
   359	
   360		if (size > PAGE_SIZE)
   361			return -ENOSPC;
   362	
   363		/* find basic block type with suitable slot size */
   364		for (block_type = 0; block_type < ARRAY_SIZE(tree_desc); block_type++) {
   365			if (size <= tree_desc[block_type].slot_size)
   366				break;
   367		}
   368		tree = &(pool->block_trees[block_type]);
   369		spin_lock(&tree->lock);
   370		/* check if there are free slots in the current and the last added blocks */
   371		if (tree->current_block && tree->current_block->free_slots > 0) {
   372			block = tree->current_block;
   373			goto found;
   374		}
   375		if (tree->last_block && tree->last_block->free_slots > 0) {
   376			block = tree->last_block;
   377			goto found;
   378		}
   379		spin_unlock(&tree->lock);
   380	
   381		/* not found block with free slots try to allocate new empty block */
   382		block = alloc_block(pool, block_type, gfp);
   383		spin_lock(&tree->lock);
   384		if (block) {
   385			tree->current_block = block;
   386			goto found;
   387		}
   388		spin_unlock(&tree->lock);
   389		return -ENOMEM;
   390	
   391	found:
   392		spin_lock(&block->lock);
   393		block->free_slots--;
   394		spin_unlock(&tree->lock);
   395		/* find the first free slot in block */
   396		for (slot = 0; slot < tree_desc[block_type].slots_per_block; slot++) {
   397			if (block->slot_info[slot] == SLOT_FREE)
   398				break;
   399		}
   400		block->slot_info[slot] = SLOT_OCCUPIED;
   401		block->coeff = block->free_slots *
   402				(tree_desc[block_type].slots_per_block - block->free_slots);
   403		spin_unlock(&block->lock);
   404		*handle = metadata_to_handle(block_type, block->block_index, slot);
   405		return 0;
   406	}
   407	
   408	/**
   409	 * ztree_free() - frees the allocation associated with the given handle
   410	 * @pool:	pool in which the allocation resided
   411	 * @handle:	handle associated with the allocation returned by ztree_alloc()
   412	 *
   413	 */
 > 414	void ztree_free(struct ztree_pool *pool, unsigned long handle)
   415	{
   416		unsigned long slot, block_type, block_index;
   417		struct rb_node *tmp;
   418		struct ztree_block *block;
   419		struct block_tree *tree;
   420	
   421		handle_to_metadata(handle, &block_type, &block_index, &slot);
   422		tree = &(pool->block_trees[block_type]);
   423	
   424		/* find block corresponding to handle */
   425		spin_lock(&tree->lock);
   426		tmp = rb_find(&block_index, &tree->root, index_comp);
   427		if (!tmp) {
   428			spin_unlock(&tree->lock);
   429			pr_err("ztree block not found\n");
   430			return;
   431		}
   432		block = rb_entry(tmp, struct ztree_block, block_node);
   433		if (block->under_reclaim) {
   434			spin_unlock(&tree->lock);
   435			return;
   436		}
   437		block->free_slots++;
   438		/* if all slots in block are empty delete whole block */
   439		if (block->free_slots == tree_desc[block_type].slots_per_block) {
   440			rb_erase(&block->block_node, &tree->root);
   441			tree->block_count--;
   442	
   443			/* if the last block to be deleted */
   444			if (block == tree->last_block) {
   445				tree->current_block = NULL;
   446				tree->last_block = NULL;
   447			/* otherwise set current block to last block */
   448			} else {
   449				tree->current_block = tree->last_block;
   450			}
   451			spin_unlock(&tree->lock);
   452			free_pages((unsigned long)block->compressed_data, tree_desc[block_type].order);
   453			kmem_cache_free(pool->block_cache, block);
   454			return;
   455		}
   456		/* switch current block */
   457		if (!tree->current_block || block->coeff >= tree->current_block->coeff)
   458			tree->current_block = block;
   459		spin_lock(&block->lock);
   460		spin_unlock(&tree->lock);
   461		block->slot_info[slot] = SLOT_FREE;
   462		block->coeff = block->free_slots *
   463					(tree_desc[block_type].slots_per_block - block->free_slots);
   464		spin_unlock(&block->lock);
   465	}
   466	

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all@lists.01.org
diff mbox series

Patch

diff --git a/MAINTAINERS b/MAINTAINERS
index dd36acc87ce6..bde8ee006953 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -21027,6 +21027,13 @@  L:	linux-mm@kvack.org
 S:	Maintained
 F:	mm/zbud.c
 
+ZTREE COMPRESSED PAGE ALLOCATOR
+M:	Ananda Badmaev <a.badmaev@clicknet.pro>
+M:	Vitaly Wool <vitaly.wool@konsulko.com>
+L:	linux-mm@kvack.org
+S:	Maintained
+F:	mm/ztree.c
+
 ZD1211RW WIRELESS DRIVER
 M:	Ulrich Kunitz <kune@deine-taler.de>
 L:	linux-wireless@vger.kernel.org
diff --git a/mm/Kconfig b/mm/Kconfig
index 356f4f2c779e..a31f6e46e0af 100644
--- a/mm/Kconfig
+++ b/mm/Kconfig
@@ -646,6 +646,12 @@  config ZSWAP_ZPOOL_DEFAULT_ZSMALLOC
 	select ZSMALLOC
 	help
 	  Use the zsmalloc allocator as the default allocator.
+
+config ZSWAP_ZPOOL_DEFAULT_ZTREE
+	bool "ztree"
+	select ZTREE
+	help
+	  Use the ztree allocator as the default allocator.
 endchoice
 
 config ZSWAP_ZPOOL_DEFAULT
@@ -654,6 +660,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 "ztree" if ZSWAP_ZPOOL_DEFAULT_ZTREE
        default ""
 
 config ZSWAP_DEFAULT_ON
@@ -712,6 +719,17 @@  config ZSMALLOC_STAT
 	  information to userspace via debugfs.
 	  If unsure, say N.
 
+config ZTREE
+	tristate "Simple allocator for compressed pages"
+	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 integer number of physical pages.
+	  Red-black trees are used for efficient block organization.
+	  ztree provides fast write, limited worst case time for
+	  operations and good compression ratio in most scenarios.
+
 config GENERIC_EARLY_IOREMAP
 	bool
 
diff --git a/mm/Makefile b/mm/Makefile
index d6c0042e3aa0..6bb4582632b1 100644
--- a/mm/Makefile
+++ b/mm/Makefile
@@ -108,6 +108,7 @@  obj-$(CONFIG_ZPOOL)	+= zpool.o
 obj-$(CONFIG_ZBUD)	+= zbud.o
 obj-$(CONFIG_ZSMALLOC)	+= zsmalloc.o
 obj-$(CONFIG_Z3FOLD)	+= z3fold.o
+obj-$(CONFIG_ZTREE)		+= ztree.o
 obj-$(CONFIG_GENERIC_EARLY_IOREMAP) += early_ioremap.o
 obj-$(CONFIG_CMA)	+= cma.o
 obj-$(CONFIG_MEMORY_BALLOON) += balloon_compaction.o
diff --git a/mm/ztree.c b/mm/ztree.c
new file mode 100644
index 000000000000..08d1d7edc1ed
--- /dev/null
+++ b/mm/ztree.c
@@ -0,0 +1,754 @@ 
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * ztree.c
+ *
+ * Author: Ananda Badmaev <a.badmaev@clicknet.pro>
+ * Copyright (C) 2021, Konsulko AB.
+ *
+ * This implementation is based on z3fold written by Vitaly Wool.
+ * Ztree is a small object allocator with the intention to serve as a
+ * zpool backend. It operates on page blocks and stores integer number
+ * of compressed pages per block which results in determinism and
+ * simplicity. Red-black trees are used for efficient block organization.
+ *
+ * ztree doesn't export any API and is meant to be used via zpool API.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <linux/mm.h>
+#include <linux/module.h>
+#include <linux/preempt.h>
+#include <linux/slab.h>
+#include <linux/spinlock.h>
+#include <linux/zpool.h>
+#include <linux/rbtree.h>
+
+
+#define SLOT_FREE 0
+#define SLOT_OCCUPIED 1
+#define SLOT_MAPPED 2
+#define SLOT_UNMAPPED 3
+
+#define SLOT_BITS 4
+#define BLOCK_TYPE_BITS 4
+
+#define BLOCK_TYPE_SHIFT (sizeof(long) * 8 - BLOCK_TYPE_BITS)
+#define MAX_BLOCK_INDEX (ULONG_MAX >> (SLOT_BITS + BLOCK_TYPE_BITS))
+#define BLOCK_INDEX_MASK (MAX_BLOCK_INDEX << SLOT_BITS)
+#define MAX_SLOTS (1 << SLOT_BITS)
+#define SLOT_MASK ((0x1UL << SLOT_BITS) - 1)
+
+/*****************
+ * Structures
+ *****************/
+
+struct ztree_pool;
+
+struct ztree_ops {
+	int (*evict)(struct ztree_pool *pool, unsigned long handle);
+};
+
+/**
+ * struct ztree_block - block metadata
+ * Block consists of several (1/2/4/8) pages and contains fixed
+ * integer number of slots for allocating compressed pages.
+ * @block_node:	     links block into the relevant tree in the pool
+ * @slot_info:	     contains data about free/occupied slots
+ * @compressed_data: pointer to the memory block
+ * @block_index:	 unique for each ztree_block in the tree
+ * @free_slots:		 number of free slots in the block
+ * @coeff:           to switch between blocks
+ * @under_reclaim:   if true shows that block is being evicted
+ */
+struct ztree_block {
+	spinlock_t lock;
+	struct rb_node block_node;
+	u8 slot_info[MAX_SLOTS];
+	void *compressed_data;
+	unsigned long block_index;
+	unsigned short free_slots;
+	unsigned short coeff;
+	bool under_reclaim;
+};
+
+
+/**
+ * struct tree_desc - general metadata for block trees
+ * Each block tree stores only blocks of corresponding type which means
+ * that all blocks in it have the same number and size of slots.
+ * All slots are aligned to size of long.
+ * @slot_size:	     size of slot for this tree
+ * @slots_per_block: number of slots per block for this tree
+ * @order:           order for __get_free_pages
+ */
+static struct tree_desc {
+	const unsigned int slot_size;
+	const unsigned short slots_per_block;
+	const unsigned short order;
+} tree_desc[] = {
+	/* 1 page blocks with 16 slots */
+	[0] = { PAGE_SIZE / 16, 0x10, 0 },
+	/* 1 page blocks with 11 slots */
+	[1] = { PAGE_SIZE / (11 * sizeof(long)) * sizeof(long), 0xB, 0 },
+	/* 1 page blocks with  8 slots */
+	[2] = { PAGE_SIZE / 8, 0x8, 0 },
+	/* 2 page blocks with 11 slots */
+	[3] = { 2 * PAGE_SIZE / (11 * sizeof(long)) * sizeof(long), 0xB, 1 },
+	/* 2 page blocks with 8 slots */
+	[4] = { PAGE_SIZE / 4, 0x8, 1 },
+	/* 4 page blocks with 14 slots */
+	[5] = { 4 * PAGE_SIZE / (14 * sizeof(long)) * sizeof(long), 0xE, 2 },
+	/* 4 page blocks with 12 slots */
+	[6] = { 4 * PAGE_SIZE / (12 * sizeof(long)) * sizeof(long), 0xC, 2 },
+	/* 4 page blocks with 10 slots */
+	[7] = { 4 * PAGE_SIZE / (10 * sizeof(long)) * sizeof(long), 0xA, 2 },
+	/* 4 page blocks with 9 slots */
+	[8] = { 4 * PAGE_SIZE / (9 * sizeof(long)) * sizeof(long), 0x9, 2 },
+	/* 4 page blocks with 8 slots */
+	[9] = { PAGE_SIZE / 2, 0x8, 2 },
+	/* 8 page blocks with 14 slots */
+	[10] = { 8 * PAGE_SIZE / (14 * sizeof(long)) * sizeof(long), 0xE, 3 },
+	/* 8 page blocks with 13 slots */
+	[11] = { 8 * PAGE_SIZE / (13 * sizeof(long)) * sizeof(long), 0xD, 3 },
+	/* 8 page blocks with 12 slots */
+	[12] = { 8 * PAGE_SIZE / (12 * sizeof(long)) * sizeof(long), 0xC, 3 },
+	/* 8 page blocks with 11 slots */
+	[13] = { 8 * PAGE_SIZE / (11 * sizeof(long)) * sizeof(long), 0xB, 3 },
+	/* 8 page blocks with 10 slots */
+	[14] = { 8 * PAGE_SIZE / (10 * sizeof(long)) * sizeof(long), 0xA, 3 },
+	/* 8 page blocks with 8 slots */
+	[15] = { PAGE_SIZE, 0x8, 3}
+};
+
+
+/**
+ * struct block_tree - stores metadata of particular tree
+ * @lock:	       protects tree
+ * @root:	       root of this tree
+ * @last_block:    pointer to the last added block in the tree
+ * @current_block: pointer to current block for allocation
+ * @counter:	   counter for block_index in ztree_block
+ * @block_count:   total number of blocks in the tree
+ */
+struct block_tree {
+	spinlock_t lock;
+	struct rb_root root;
+	struct ztree_block *last_block;
+	struct ztree_block *current_block;
+	unsigned long counter;
+	unsigned int block_count;
+};
+
+/**
+ * struct ztree_pool - stores metadata for each ztree pool
+ * @block_trees:  array of block trees
+ * @block_cache:  array of block cache for block metadata allocation
+ * @ops:	      pointer to a structure of user defined operations specified at
+ *				pool creation time.
+ *
+ * This structure is allocated at pool creation time and maintains metadata
+ * for a particular ztree pool.
+ */
+struct ztree_pool {
+	struct block_tree *block_trees;
+	struct kmem_cache *block_cache;
+	const struct ztree_ops *ops;
+	struct zpool *zpool;
+	const struct zpool_ops *zpool_ops;
+};
+
+
+/*****************
+ * Helpers
+ *****************/
+
+/* compare 2 nodes by block index, used by rb_add() */
+static bool node_comp(struct rb_node *node1, const struct rb_node *node2)
+{
+	struct ztree_block *block1, *block2;
+
+	block1 = rb_entry(node1, struct ztree_block, block_node);
+	block2 = rb_entry(node2, struct ztree_block, block_node);
+	return block1->block_index < block2->block_index;
+}
+
+/* compare key with block index of node, used by rb_find() */
+static int index_comp(const void *key, const struct rb_node *node)
+{
+	struct ztree_block *block;
+	unsigned long block_index;
+
+	block = rb_entry(node, struct ztree_block, block_node);
+	block_index = *(unsigned long *)key;
+	if (block_index < block->block_index)
+		return -1;
+	else if (block_index > block->block_index)
+		return 1;
+	else
+		return 0;
+}
+
+
+/*
+ * allocate new block and add it to corresponding block tree
+ */
+static struct ztree_block *alloc_block(struct ztree_pool *pool,
+									int block_type, gfp_t gfp)
+{
+	struct ztree_block *block;
+	struct block_tree *tree;
+
+	block = kmem_cache_alloc(pool->block_cache,
+					(gfp & ~(__GFP_HIGHMEM | __GFP_MOVABLE)));
+	if (!block)
+		return NULL;
+
+	block->compressed_data = (void *)__get_free_pages(gfp, tree_desc[block_type].order);
+	if (!block->compressed_data) {
+		kmem_cache_free(pool->block_cache, block);
+		return NULL;
+	}
+	tree = &(pool->block_trees)[block_type];
+
+	/* init block data  */
+	spin_lock_init(&block->lock);
+	memset(block->slot_info, SLOT_FREE, tree_desc[block_type].slots_per_block);
+	block->free_slots = tree_desc[block_type].slots_per_block;
+	block->coeff = 0;
+	block->under_reclaim = false;
+
+	spin_lock(&tree->lock);
+	/* block indexation and inserting block into tree */
+	block->block_index = tree->counter++;
+	tree->counter &= MAX_BLOCK_INDEX;
+	rb_add(&block->block_node, &tree->root, node_comp);
+	tree->last_block = block;
+	tree->block_count++;
+	spin_unlock(&tree->lock);
+	return block;
+}
+
+
+/*
+ * free block tree with blocks of particular type
+ */
+void free_block_tree(struct ztree_pool *pool, int block_type)
+{
+	struct ztree_block *block, *tmp;
+	struct block_tree *tree;
+
+	tree = &(pool->block_trees)[block_type];
+	spin_lock(&tree->lock);
+	rbtree_postorder_for_each_entry_safe(block, tmp, &tree->root, block_node) {
+		free_pages((unsigned long)block->compressed_data,
+					tree_desc[block_type].order);
+		kmem_cache_free(pool->block_cache, block);
+	}
+	spin_unlock(&tree->lock);
+}
+
+/*
+ * Encodes the handle of a particular slot in the pool using metadata
+ */
+static inline unsigned long metadata_to_handle(unsigned long block_type,
+					unsigned long block_index, unsigned long slot)
+{
+	return (block_type << BLOCK_TYPE_SHIFT) + (block_index << SLOT_BITS) + slot;
+}
+
+
+/* Returns block type, block index and slot in the pool corresponding to handle */
+static inline void handle_to_metadata(unsigned long handle, unsigned long *block_type,
+						unsigned long *block_index, unsigned long *slot)
+{
+	*block_type = handle >> BLOCK_TYPE_SHIFT;
+	*block_index = (handle & BLOCK_INDEX_MASK) >> SLOT_BITS;
+	*slot = handle & SLOT_MASK;
+}
+
+
+/*****************
+ * API Functions
+ *****************/
+/**
+ * ztree_create_pool() - create a new ztree pool array
+ * @gfp:	gfp flags when allocating the ztree pool structure
+ * @ops:	user-defined operations for the ztree pool
+ *
+ * Return: pointer to the new ztree pool or NULL if the metadata allocation
+ * failed.
+ */
+struct ztree_pool *ztree_create_pool(gfp_t gfp, const struct ztree_ops *ops)
+{
+	struct ztree_pool *pool;
+	struct block_tree *tree;
+	int i, block_types_nr;
+
+	pool = kmalloc(sizeof(struct ztree_pool), gfp);
+	if (!pool)
+		return NULL;
+
+	block_types_nr = ARRAY_SIZE(tree_desc);
+
+	pool->block_cache = kmem_cache_create("ztree_blocks",
+					sizeof(struct ztree_block), 0, 0, NULL);
+	if (!pool->block_cache) {
+		kfree(pool);
+		return NULL;
+	}
+
+	pool->block_trees = kmalloc(block_types_nr * sizeof(struct block_tree), gfp);
+	if (!pool->block_trees) {
+		kmem_cache_destroy(pool->block_cache);
+		kfree(pool);
+		return NULL;
+	}
+
+	/* init each basic block tree */
+	for (i = 0; i < block_types_nr; i++) {
+		tree = &(pool->block_trees)[i];
+		spin_lock_init(&tree->lock);
+		tree->root = RB_ROOT;
+		tree->last_block = NULL;
+		tree->current_block = NULL;
+		tree->counter = 0;
+		tree->block_count = 0;
+	}
+	pool->ops = ops;
+	return pool;
+}
+
+/**
+ * ztree_destroy_pool() - destroys an existing ztree pool
+ * @pool:	the ztree pool to be destroyed
+ *
+ */
+void ztree_destroy_pool(struct ztree_pool *pool)
+{
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(tree_desc); i++)
+		free_block_tree(pool, i);
+	kmem_cache_destroy(pool->block_cache);
+	kfree(pool->block_trees);
+	kfree(pool);
+}
+
+
+/**
+ * ztree_alloc() - allocates a slot of appropriate size
+ * @pool:	ztree pool from which to allocate
+ * @size:	size in bytes of the desired allocation
+ * @gfp:	gfp flags used if the pool needs to grow
+ * @handle:	handle of the new allocation
+ *
+ * Return: 0 if success and handle is set, otherwise -EINVAL if the size or
+ * gfp arguments are invalid or -ENOMEM if the pool was unable to allocate
+ * a new slot.
+ */
+int ztree_alloc(struct ztree_pool *pool, size_t size, gfp_t gfp,
+			unsigned long *handle)
+{
+	unsigned long block_type, slot;
+	struct ztree_block *block;
+	struct block_tree *tree;
+
+	if (!size)
+		return -EINVAL;
+
+	if (size > PAGE_SIZE)
+		return -ENOSPC;
+
+	/* find basic block type with suitable slot size */
+	for (block_type = 0; block_type < ARRAY_SIZE(tree_desc); block_type++) {
+		if (size <= tree_desc[block_type].slot_size)
+			break;
+	}
+	tree = &(pool->block_trees[block_type]);
+	spin_lock(&tree->lock);
+	/* check if there are free slots in the current and the last added blocks */
+	if (tree->current_block && tree->current_block->free_slots > 0) {
+		block = tree->current_block;
+		goto found;
+	}
+	if (tree->last_block && tree->last_block->free_slots > 0) {
+		block = tree->last_block;
+		goto found;
+	}
+	spin_unlock(&tree->lock);
+
+	/* not found block with free slots try to allocate new empty block */
+	block = alloc_block(pool, block_type, gfp);
+	spin_lock(&tree->lock);
+	if (block) {
+		tree->current_block = block;
+		goto found;
+	}
+	spin_unlock(&tree->lock);
+	return -ENOMEM;
+
+found:
+	spin_lock(&block->lock);
+	block->free_slots--;
+	spin_unlock(&tree->lock);
+	/* find the first free slot in block */
+	for (slot = 0; slot < tree_desc[block_type].slots_per_block; slot++) {
+		if (block->slot_info[slot] == SLOT_FREE)
+			break;
+	}
+	block->slot_info[slot] = SLOT_OCCUPIED;
+	block->coeff = block->free_slots *
+			(tree_desc[block_type].slots_per_block - block->free_slots);
+	spin_unlock(&block->lock);
+	*handle = metadata_to_handle(block_type, block->block_index, slot);
+	return 0;
+}
+
+/**
+ * ztree_free() - frees the allocation associated with the given handle
+ * @pool:	pool in which the allocation resided
+ * @handle:	handle associated with the allocation returned by ztree_alloc()
+ *
+ */
+void ztree_free(struct ztree_pool *pool, unsigned long handle)
+{
+	unsigned long slot, block_type, block_index;
+	struct rb_node *tmp;
+	struct ztree_block *block;
+	struct block_tree *tree;
+
+	handle_to_metadata(handle, &block_type, &block_index, &slot);
+	tree = &(pool->block_trees[block_type]);
+
+	/* find block corresponding to handle */
+	spin_lock(&tree->lock);
+	tmp = rb_find(&block_index, &tree->root, index_comp);
+	if (!tmp) {
+		spin_unlock(&tree->lock);
+		pr_err("ztree block not found\n");
+		return;
+	}
+	block = rb_entry(tmp, struct ztree_block, block_node);
+	if (block->under_reclaim) {
+		spin_unlock(&tree->lock);
+		return;
+	}
+	block->free_slots++;
+	/* if all slots in block are empty delete whole block */
+	if (block->free_slots == tree_desc[block_type].slots_per_block) {
+		rb_erase(&block->block_node, &tree->root);
+		tree->block_count--;
+
+		/* if the last block to be deleted */
+		if (block == tree->last_block) {
+			tree->current_block = NULL;
+			tree->last_block = NULL;
+		/* otherwise set current block to last block */
+		} else {
+			tree->current_block = tree->last_block;
+		}
+		spin_unlock(&tree->lock);
+		free_pages((unsigned long)block->compressed_data, tree_desc[block_type].order);
+		kmem_cache_free(pool->block_cache, block);
+		return;
+	}
+	/* switch current block */
+	if (!tree->current_block || block->coeff >= tree->current_block->coeff)
+		tree->current_block = block;
+	spin_lock(&block->lock);
+	spin_unlock(&tree->lock);
+	block->slot_info[slot] = SLOT_FREE;
+	block->coeff = block->free_slots *
+				(tree_desc[block_type].slots_per_block - block->free_slots);
+	spin_unlock(&block->lock);
+}
+
+/**
+ * ztree_reclaim_block() - evicts allocations from block and frees it
+ * @pool:	pool from which a block will attempt to be evicted
+ *
+ * Returns: pages reclaimed count if block is successfully freed
+ *          otherwise -EINVAL if there are no blocks to evict
+ */
+int ztree_reclaim_block(struct ztree_pool *pool)
+{
+	struct ztree_block *block;
+	struct rb_node *tmp;
+	struct block_tree *tree;
+	unsigned long handle, block_type, slot;
+	int ret, reclaimed;
+
+	/* start with tree storing blocks with the worst compression and try
+	 * to evict block with the lowest index (the first element in tree)
+	 */
+	for (block_type = ARRAY_SIZE(tree_desc) - 1; block_type >= 0; --block_type) {
+		tree = &(pool->block_trees[block_type]);
+		spin_lock(&tree->lock);
+
+		/* find the first block in tree */
+		tmp = rb_first(&tree->root);
+
+		if (tmp == NULL) {
+			spin_unlock(&tree->lock);
+			continue;
+		}
+		block = rb_entry(tmp, struct ztree_block, block_node);
+
+		/* skip iteration if this block is current or last */
+		if (block == tree->current_block || block == tree->last_block) {
+			spin_unlock(&tree->lock);
+			continue;
+		}
+		block->under_reclaim = true;
+		spin_unlock(&tree->lock);
+		reclaimed = 0;
+
+		/* try to evict all UNMAPPED slots in block */
+		for (slot = 0; slot < tree_desc[block_type].slots_per_block; ++slot) {
+			if (block->slot_info[slot] == SLOT_UNMAPPED) {
+				handle = metadata_to_handle(block_type, block->block_index, slot);
+				ret = pool->ops->evict(pool, handle);
+				if (ret)
+					break;
+
+				++reclaimed;
+				spin_lock(&block->lock);
+				block->slot_info[slot] = SLOT_FREE;
+				spin_unlock(&block->lock);
+				block->free_slots++;
+			}
+		}
+		spin_lock(&tree->lock);
+		/* some occupied slots remained - modify coeff and leave the block */
+		if (block->free_slots != tree_desc[block_type].slots_per_block) {
+			block->under_reclaim = false;
+			block->coeff = block->free_slots *
+				(tree_desc[block_type].slots_per_block - block->free_slots);
+			spin_unlock(&tree->lock);
+		} else {
+		/* all slots are free - delete this block */
+			rb_erase(&block->block_node, &tree->root);
+			tree->block_count--;
+			spin_unlock(&tree->lock);
+			free_pages((unsigned long)block->compressed_data,
+						tree_desc[block_type].order);
+			kmem_cache_free(pool->block_cache, block);
+		}
+		if (reclaimed != 0)
+			return reclaimed;
+		return -EAGAIN;
+	}
+	return -EINVAL;
+}
+
+
+/**
+ * ztree_map() - maps the allocation associated with the given handle
+ * @pool:	pool in which the allocation resides
+ * @handle:	handle associated with the allocation to be mapped
+ *
+ *
+ * Returns: a pointer to the mapped allocation
+ */
+void *ztree_map(struct ztree_pool *pool, unsigned long handle)
+{
+	unsigned long block_type, block_index, slot;
+	struct rb_node *tmp;
+	struct ztree_block *block;
+	struct block_tree *tree;
+
+	handle_to_metadata(handle, &block_type, &block_index, &slot);
+	tree = &(pool->block_trees[block_type]);
+	spin_lock(&tree->lock);
+
+	/* often requested block turns out to be current_block */
+	if (tree->current_block && tree->current_block->block_index == block_index) {
+		block = tree->current_block;
+		spin_unlock(&tree->lock);
+		goto found;
+	}
+	/* find block with index corresponding to handle */
+	tmp = rb_find(&block_index, &tree->root, index_comp);
+	spin_unlock(&tree->lock);
+	if (!tmp) {
+		pr_err("ztree block not found\n");
+		return NULL;
+	}
+	block = rb_entry(tmp, struct ztree_block, block_node);
+found:
+	spin_lock(&block->lock);
+	block->slot_info[slot] = SLOT_MAPPED;
+	spin_unlock(&block->lock);
+	return block->compressed_data + slot * tree_desc[block_type].slot_size;
+}
+
+/**
+ * ztree_unmap() - unmaps the allocation associated with the given handle
+ * @pool:	pool in which the allocation resides
+ * @handle:	handle associated with the allocation to be unmapped
+ */
+void ztree_unmap(struct ztree_pool *pool, unsigned long handle)
+{
+	unsigned long block_type, block_index, slot;
+	struct rb_node *tmp;
+	struct ztree_block *block;
+	struct block_tree *tree;
+
+	handle_to_metadata(handle, &block_type, &block_index, &slot);
+	tree = &(pool->block_trees[block_type]);
+	spin_lock(&tree->lock);
+
+	/* often requested block turns out to be current_block */
+	if (tree->current_block && tree->current_block->block_index == block_index) {
+		block = tree->current_block;
+		spin_unlock(&tree->lock);
+		goto found;
+	}
+	/* find block with index corresponding to handle */
+	tmp = rb_find(&block_index, &tree->root, index_comp);
+	spin_unlock(&tree->lock);
+	if (!tmp) {
+		pr_err("ztree block not found\n");
+		return;
+	}
+	block = rb_entry(tmp, struct ztree_block, block_node);
+found:
+	spin_lock(&block->lock);
+	block->slot_info[slot] = SLOT_UNMAPPED;
+	spin_unlock(&block->lock);
+}
+
+/**
+ * ztree_get_pool_size() - gets the ztree pool size in bytes
+ * @pool:	pool whose size is being queried
+ *
+ * Returns: size in bytes of the given pool.
+ */
+u64 ztree_get_pool_size(struct ztree_pool *pool)
+{
+	u64 total_size;
+	int i;
+
+	total_size = 0;
+	for (i = 0; i < ARRAY_SIZE(tree_desc); i++) {
+		total_size += (pool->block_trees)[i].block_count
+				* tree_desc[i].slot_size * tree_desc[i].slots_per_block;
+	}
+	return total_size;
+}
+
+/*****************
+ * zpool
+ ****************/
+
+static int ztree_zpool_evict(struct ztree_pool *pool, unsigned long handle)
+{
+	if (pool->zpool && pool->zpool_ops && pool->zpool_ops->evict)
+		return pool->zpool_ops->evict(pool->zpool, handle);
+	else
+		return -ENOENT;
+}
+
+static const struct ztree_ops ztree_zpool_ops = {
+	.evict =	ztree_zpool_evict
+};
+
+static void *ztree_zpool_create(const char *name, gfp_t gfp,
+				   const struct zpool_ops *zpool_ops,
+				   struct zpool *zpool)
+{
+	struct ztree_pool *pool;
+
+	pool = ztree_create_pool(gfp, &ztree_zpool_ops);
+	if (pool) {
+		pool->zpool = zpool;
+		pool->zpool_ops = zpool_ops;
+	}
+	return pool;
+}
+
+static void ztree_zpool_destroy(void *pool)
+{
+	ztree_destroy_pool(pool);
+}
+
+static int ztree_zpool_malloc(void *pool, size_t size, gfp_t gfp,
+			unsigned long *handle)
+{
+	return ztree_alloc(pool, size, gfp, handle);
+}
+
+static void ztree_zpool_free(void *pool, unsigned long handle)
+{
+	ztree_free(pool, handle);
+}
+
+static int ztree_zpool_shrink(void *pool, unsigned int pages,
+			unsigned int *reclaimed)
+{
+	unsigned int total = 0;
+	int ret = -EINVAL;
+
+	while (total < pages) {
+		ret = ztree_reclaim_block(pool);
+		if (ret < 0)
+			break;
+		total += ret;
+	}
+	if (reclaimed)
+		*reclaimed = total;
+
+	return ret;
+}
+
+static void *ztree_zpool_map(void *pool, unsigned long handle,
+			enum zpool_mapmode mm)
+{
+	return ztree_map(pool, handle);
+}
+
+static void ztree_zpool_unmap(void *pool, unsigned long handle)
+{
+	ztree_unmap(pool, handle);
+}
+
+static u64 ztree_zpool_total_size(void *pool)
+{
+	return ztree_get_pool_size(pool);
+}
+
+static struct zpool_driver ztree_zpool_driver = {
+	.type =		"ztree",
+	.owner =	THIS_MODULE,
+	.create =	ztree_zpool_create,
+	.destroy =	ztree_zpool_destroy,
+	.malloc =	ztree_zpool_malloc,
+	.free =		ztree_zpool_free,
+	.shrink =	ztree_zpool_shrink,
+	.map =		ztree_zpool_map,
+	.unmap =	ztree_zpool_unmap,
+	.total_size =	ztree_zpool_total_size,
+};
+
+MODULE_ALIAS("zpool-ztree");
+
+static int __init init_ztree(void)
+{
+	pr_info("loaded\n");
+	zpool_register_driver(&ztree_zpool_driver);
+	return 0;
+}
+
+static void __exit exit_ztree(void)
+{
+	zpool_unregister_driver(&ztree_zpool_driver);
+	pr_info("unloaded\n");
+}
+
+module_init(init_ztree);
+module_exit(exit_ztree);
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Ananda Badmaeb <a.badmaev@clicknet.pro>");
+MODULE_DESCRIPTION("simple block allocator");