From patchwork Tue Apr 1 17:17:54 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vitaly X-Patchwork-Id: 14035207 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id A9F71C36010 for ; Tue, 1 Apr 2025 17:18:11 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0A8B0280002; Tue, 1 Apr 2025 13:18:10 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 0571E280001; Tue, 1 Apr 2025 13:18:09 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E15B9280002; Tue, 1 Apr 2025 13:18:09 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id BB0DF280001 for ; Tue, 1 Apr 2025 13:18:09 -0400 (EDT) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 9D81F1605F9 for ; Tue, 1 Apr 2025 17:18:10 +0000 (UTC) X-FDA: 83286133140.01.271C752 Received: from mailrelay2-3.pub.mailoutpod3-cph3.one.com (mailrelay2-3.pub.mailoutpod3-cph3.one.com [46.30.212.1]) by imf05.hostedemail.com (Postfix) with ESMTP id 2AEEF100005 for ; Tue, 1 Apr 2025 17:18:07 +0000 (UTC) Authentication-Results: imf05.hostedemail.com; dkim=pass header.d=konsulko.se header.s=rsa1 header.b=R54bow5j; dkim=pass header.d=konsulko.se header.s=ed1 header.b=y+8FfbMO; spf=none (imf05.hostedemail.com: domain of vitaly.wool@konsulko.se has no SPF policy when checking 46.30.212.1) smtp.mailfrom=vitaly.wool@konsulko.se; dmarc=none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1743527889; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:references:dkim-signature; bh=NT8Bmd8+m3BCJWvQdNn4oRcizc+lc4FMn4uFxaLYgS8=; b=2QMmgALoEYKs6HOOqIKlZUwzlhhmd0A70SiDQtnMAiWwU7bxlNknCW3OdTRfayQQTdIe2V UtO85mameU7cAROzCgQHznpMW0kt+RZxGa2xWZn7F1BZ4uJvG1pnVtRnhvUHC0o0REeoQm MyVtmEePv3uEuFJwqGZyj0ajfGIZkms= ARC-Authentication-Results: i=1; imf05.hostedemail.com; dkim=pass header.d=konsulko.se header.s=rsa1 header.b=R54bow5j; dkim=pass header.d=konsulko.se header.s=ed1 header.b=y+8FfbMO; spf=none (imf05.hostedemail.com: domain of vitaly.wool@konsulko.se has no SPF policy when checking 46.30.212.1) smtp.mailfrom=vitaly.wool@konsulko.se; dmarc=none ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1743527889; a=rsa-sha256; cv=none; b=rvU6wDs0JPvS7HAAE5TVkwKaAbMcVLd+Ymb00Gjgn9RockYkd/E6JEQVJUmsxlzdvak9HF wLtVTppkDpzGLMnX5PV/7IhmJUjwLa5AWVmLTBdzGmO+tHvOzhNLH/DgE8pkgqc0tIhUkv tbmEXzzhVkZY187uBn1lm3i0NFlnmYA= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; t=1743527885; x=1744132685; d=konsulko.se; s=rsa1; h=content-transfer-encoding:mime-version:message-id:date:subject:cc:to:from: from; bh=NT8Bmd8+m3BCJWvQdNn4oRcizc+lc4FMn4uFxaLYgS8=; b=R54bow5jTLQiPQc/BuibDeXx+xDXtzdUJiqsglk1LGbb1yjCH8nfKjcPyhdZ66SxjFeQHpIRvRugk w2H6kwhl5Hsy16oev+mOEzw2+qM82pMBSNIqLNKT3PcAdD5yV75UynphZvAmSEPp//4PW5E854gafa vsKBK9fjmjM4uTS5dEWiGsxMU3NaXlPS5FVYiA2CWs8jTaLl4WV4Wl7Svwp13iMGcKQFhd93PdmX0p QSVaNvki9+GcUgiazN0CYEoX2WzS7cWLekfRew4azG+ZpltTfvErnZRTZbvfe70bF3B3LYNyMA/uxF G9NoJpT9chvjbv77kWQppBXuneBRB7w== DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; t=1743527885; x=1744132685; d=konsulko.se; s=ed1; h=content-transfer-encoding:mime-version:message-id:date:subject:cc:to:from: from; bh=NT8Bmd8+m3BCJWvQdNn4oRcizc+lc4FMn4uFxaLYgS8=; b=y+8FfbMOor7VKFp1xM1w34l0jXfJBThUqoacCyK4qEL/TM5v8gweIYDPCJBdt40OxuYrAbfaEFfhA NMw0ldNCA== X-HalOne-ID: 45606074-0f1d-11f0-bc71-b37c246f863f Received: from localhost.localdomain (host-90-233-218-222.mobileonline.telia.com [90.233.218.222]) by mailrelay2.pub.mailoutpod3-cph3.one.com (Halon) with ESMTPSA id 45606074-0f1d-11f0-bc71-b37c246f863f; Tue, 01 Apr 2025 17:18:04 +0000 (UTC) From: Vitaly Wool To: linux-mm@kvack.org Cc: akpm@linux-foundation.org, Vitaly Wool , Igor Belousov Subject: [PATCH] mm: add zblock allocator Date: Tue, 1 Apr 2025 19:17:54 +0200 Message-Id: <20250401171754.2686501-1-vitaly.wool@konsulko.se> X-Mailer: git-send-email 2.39.2 MIME-Version: 1.0 X-Rspamd-Queue-Id: 2AEEF100005 X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: 1dubuhkpfacsrgs19womiqmgmxjqpffu X-HE-Tag: 1743527887-76140 X-HE-Meta: U2FsdGVkX1+xxK+4uhX8r1sFai03qv/+pFP3rl9kdlwI+j2k/R8yzkqsrQ3RaWLy8KHuNfpxR9Fsz7riLTgv3fRAg05jX9B0/OmWYsuVa1j41xM2BvsB0pQ4w0Lf81qN1BI17m7m2jQ+KlQ7+8pKPADtCNX1gPuq6gg2X3FHA8bBcqgO+K+3CVhRABN5cL3018/eGzOb9WsXcpdTn5+zLJZLmfE3hDdcdVyOUvDjuPWnvOL+yk8fqddbRYBH7BnpoPEE29BPYN4QzSTzni/pIxcnKNfVNATdVApcWPZLuDkgQZaXtg1joLlJMRLEbMyYiVLt7UF7ZC+7qgT113+zulfmLPflbFmkkFoHNQKWeXFTUX6ucCjT6f0sXcbvGYJoJoiniwPUp4o+EPk2EOmqvJuQpYbXDIS6EIwfifxwAzsYdgXq6ozJ8WDWUrLeOO52HWTqWZsjk1Zlm2vvZUh/HUux4EszoYfaRyZGhYBzPjNUMfstkwY8fmHk2VEJTrYo+421w9V6Xq1Hx9koeajAazs268H6BV9jlok0boHfi33SGJnPoSUZL9r2KaUmSXoKVVRda/z8On8T8Wt52/Rntnt4DUjpJ2q7Y8zL9zZGHIEWEsQnpVJOef3ao3Fr/qMQMAr1zguusp1/K3EcUyRnK2BiPuEcj8uH3EjRh9srldi0s+PKoNqKf/YVW24ojxo1oZzgYuVcmEdzURCwPKM00+BTyJ2Mrd1TwHbFgT6ZmQDqSVTKL5mEsfLXSqJMmTBUR8Z1I2LQkHa85mZeVaF+QcK3KrVAyATJQfKsMTHJuYiEE+G5hMQdTYkTaAhPJVcex33vyDC/YnyuxxQktWIpO68SRP2XGTorGkhpbktsfVNMwf9/4SlwDgM8tPBBOPrGd9mGHN5ev6ze+QDsuZ2C4XG43GLFbMAZPFfa0nsAUXHC3tf/nccgo5OcabGiNs9Ke/x9XLfhAmGBxhjkd2h FF0KtYpz TzJL3zYFpV6OS7YTK7+SD+Hd36NfIgb/8mKRPo2JBQyUk8XgU+1ssc0qxPFdVV6gYczv46Zprz0843GnWfuTkZJPjmqEM0qTtzxg6BxWzxdEHkcUniDMOs9D7UAj7D6oNn1QDNEmvGKpqeQOPKgmCEYacy9mBsqH3MUtyCJfnySsALvHqBTK60Q/jc9ITkRpoeDeqzqf2d42NYZU8bgUbnxJK0GWKwGibPG1K/XU+j+JPQ+i66KRsTZzXZX99MiNattLh+Xee5bAuPKp7+Asq591hHGNnNXk8ru0glr8llO3MglRfnwYyb4TISPBrnH8Zlv31jT+9hJtxV/gqIVrCoLFt3b4ibP42cmJk X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: zblock is a special purpose allocator for storing compressed pages. It stores integer number of compressed objects per its block. These blocks consist of several physical pages (2**n, i. e. 1/2/4/8). 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, in many cases providing a compression ratio substantially higher than z3fold and zbud (though lower than zmalloc's). zblock does not require MMU to operate and also is superior to zsmalloc with regard to average performance and worst execution times, thus allowing for better response time and real-time characteristics of the whole system. E. g. on a series of stress-ng tests run on a Raspberry Pi 5, we get 5-10% higher value for bogo ops/s in zblock/zsmalloc comparison. Signed-off-by: Vitaly Wool Signed-off-by: Igor Belousov --- Documentation/mm/zblock.rst | 22 ++ MAINTAINERS | 7 + mm/Kconfig | 8 + mm/Makefile | 1 + mm/zblock.c | 492 ++++++++++++++++++++++++++++++++++++ 5 files changed, 530 insertions(+) create mode 100644 Documentation/mm/zblock.rst create mode 100644 mm/zblock.c diff --git a/Documentation/mm/zblock.rst b/Documentation/mm/zblock.rst new file mode 100644 index 000000000000..754b3dbb9e94 --- /dev/null +++ b/Documentation/mm/zblock.rst @@ -0,0 +1,22 @@ +====== +zblock +====== + +zblock is a special purpose allocator for storing compressed pages. +It stores integer number of compressed objects per its block. These +blocks consist of several physical pages (2**n, i. e. 1/2/4/8). + +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, in many cases +providing a compression ratio substantially higher than z3fold and zbud +(though lower than zmalloc's). + +zblock does not require MMU to operate and also is superior to zsmalloc +with regard to average performance and worst execution times, thus +allowing for better response time and real-time characteristics of the +whole system. + +E. g. on a series of stress-ng tests run on a Raspberry Pi 5, we get +5-10% higher value for bogo ops/s in zblock/zsmalloc comparison. + diff --git a/MAINTAINERS b/MAINTAINERS index 991a33bad10e..166e9bfa04dc 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -26313,6 +26313,13 @@ F: Documentation/networking/device_drivers/hamradio/z8530drv.rst F: drivers/net/hamradio/*scc.c F: drivers/net/hamradio/z8530.h +ZBLOCK COMPRESSED SLAB MEMORY ALLOCATOR +M: Vitaly Wool +L: linux-mm@kvack.org +S: Maintained +F: Documentation/mm/zblock.rst +F: mm/zblock.c + ZBUD COMPRESSED PAGE ALLOCATOR M: Seth Jennings M: Dan Streetman diff --git a/mm/Kconfig b/mm/Kconfig index 1b501db06417..26b79e3c1300 100644 --- a/mm/Kconfig +++ b/mm/Kconfig @@ -193,6 +193,14 @@ config Z3FOLD_DEPRECATED page. It is a ZBUD derivative so the simplicity and determinism are still there. +config ZBLOCK + tristate "Fast compression allocator with high density" + depends on ZPOOL + help + A special purpose allocator for storing compressed pages. + It is designed to store same size compressed pages in blocks of + physical pages. + config Z3FOLD tristate default y if Z3FOLD_DEPRECATED=y diff --git a/mm/Makefile b/mm/Makefile index 850386a67b3e..2018455b7baa 100644 --- a/mm/Makefile +++ b/mm/Makefile @@ -116,6 +116,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_NUMA) += numa.o diff --git a/mm/zblock.c b/mm/zblock.c new file mode 100644 index 000000000000..a6778653c451 --- /dev/null +++ b/mm/zblock.c @@ -0,0 +1,492 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * zblock.c + * + * Author: Vitaly Wool + * Based on the work from Ananda Badmaev + * Copyright (C) 2022-2024, Konsulko AB. + * + * Zblock is a small object allocator with the intention to serve as a + * zpool backend. It operates on page blocks which consist of number + * of physical pages being a power of 2 and store integer number of + * compressed pages per block which results in determinism and simplicity. + * + * zblock doesn't export any API and is meant to be used via zpool API. + */ + +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt + +#include +#include +#include +#include +#include +#include +#include + +#define SLOT_FREE 0 +#define BIT_SLOT_OCCUPIED 0 +#define BIT_SLOT_MAPPED 1 + +#define SLOT_BITS 5 +#define MAX_SLOTS (1 << SLOT_BITS) +#define SLOT_MASK ((0x1UL << SLOT_BITS) - 1) + +#define ZBLOCK_HEADER_SIZE round_up(sizeof(struct zblock_block), sizeof(long)) +#define BLOCK_DATA_SIZE(order) ((PAGE_SIZE << order) - ZBLOCK_HEADER_SIZE) +#define SLOT_SIZE(nslots, order) (round_down((BLOCK_DATA_SIZE(order) / nslots), sizeof(long))) + +#define BLOCK_CACHE_SIZE 32 + +struct zblock_pool; + +/** + * struct zblock_block - block metadata + * Block consists of several (1/2/4/8) pages and contains fixed + * integer number of slots for allocating compressed pages. + * + * free_slots: number of free slots in the block + * slot_info: contains data about free/occupied slots + * cache_idx: index of the block in cache + */ +struct zblock_block { + atomic_t free_slots; + u64 slot_info[1]; + int cache_idx; +}; + +/** + * struct block_desc - general metadata for block lists + * Each block list 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 list + * slots_per_block: number of slots per block for this list + * order: order for __get_free_pages + */ +static const struct block_desc { + const unsigned int slot_size; + const unsigned short slots_per_block; + const unsigned short order; +} block_desc[] = { + { SLOT_SIZE(32, 0), 32, 0 }, + { SLOT_SIZE(22, 0), 22, 0 }, + { SLOT_SIZE(17, 0), 17, 0 }, + { SLOT_SIZE(13, 0), 13, 0 }, + { SLOT_SIZE(11, 0), 11, 0 }, + { SLOT_SIZE(9, 0), 9, 0 }, + { SLOT_SIZE(8, 0), 8, 0 }, + { SLOT_SIZE(14, 1), 14, 1 }, + { SLOT_SIZE(12, 1), 12, 1 }, + { SLOT_SIZE(11, 1), 11, 1 }, + { SLOT_SIZE(10, 1), 10, 1 }, + { SLOT_SIZE(9, 1), 9, 1 }, + { SLOT_SIZE(8, 1), 8, 1 }, + { SLOT_SIZE(15, 2), 15, 2 }, + { SLOT_SIZE(14, 2), 14, 2 }, + { SLOT_SIZE(13, 2), 13, 2 }, + { SLOT_SIZE(12, 2), 12, 2 }, + { SLOT_SIZE(11, 2), 11, 2 }, + { SLOT_SIZE(10, 2), 10, 2 }, + { SLOT_SIZE(9, 2), 9, 2 }, + { SLOT_SIZE(8, 2), 8, 2 }, + { SLOT_SIZE(15, 3), 15, 3 }, + { SLOT_SIZE(14, 3), 14, 3 }, + { SLOT_SIZE(13, 3), 13, 3 }, + { SLOT_SIZE(12, 3), 12, 3 }, + { SLOT_SIZE(11, 3), 11, 3 }, + { SLOT_SIZE(10, 3), 10, 3 }, + { SLOT_SIZE(9, 3), 9, 3 }, + { SLOT_SIZE(7, 3), 7, 3 } +}; + +/** + * struct block_list - stores metadata of particular list + * lock: protects block_cache + * block_cache: blocks with free slots + * block_count: total number of blocks in the list + */ +struct block_list { + spinlock_t lock; + struct zblock_block *block_cache[BLOCK_CACHE_SIZE]; + unsigned long block_count; +}; + +/** + * struct zblock_pool - stores metadata for each zblock pool + * @block_lists: array of block lists + * @zpool: zpool driver + * @alloc_flag: protects block allocation from memory leak + * + * This structure is allocated at pool creation time and maintains metadata + * for a particular zblock pool. + */ +struct zblock_pool { + struct block_list block_lists[ARRAY_SIZE(block_desc)]; + struct zpool *zpool; + atomic_t alloc_flag; +}; + +/***************** + * Helpers + *****************/ + +static int cache_insert_block(struct zblock_block *block, struct block_list *list) +{ + unsigned int i, min_free_slots = atomic_read(&block->free_slots); + int min_index = -1; + + if (WARN_ON(block->cache_idx != -1)) + return -EINVAL; + + min_free_slots = atomic_read(&block->free_slots); + for (i = 0; i < BLOCK_CACHE_SIZE; i++) { + if (!list->block_cache[i] || !atomic_read(&(list->block_cache[i])->free_slots)) { + min_index = i; + break; + } + if (atomic_read(&(list->block_cache[i])->free_slots) < min_free_slots) { + min_free_slots = atomic_read(&(list->block_cache[i])->free_slots); + min_index = i; + } + } + if (min_index >= 0) { + if (list->block_cache[min_index]) + (list->block_cache[min_index])->cache_idx = -1; + list->block_cache[min_index] = block; + block->cache_idx = min_index; + } + return min_index < 0 ? min_index : 0; +} + +static struct zblock_block *cache_find_block(struct block_list *list) +{ + int i; + struct zblock_block *z = NULL; + + for (i = 0; i < BLOCK_CACHE_SIZE; i++) { + if (list->block_cache[i] && + atomic_dec_if_positive(&list->block_cache[i]->free_slots) >= 0) { + z = list->block_cache[i]; + break; + } + } + return z; +} + +static int cache_remove_block(struct block_list *list, struct zblock_block *block) +{ + int idx = block->cache_idx; + + block->cache_idx = -1; + if (idx >= 0) + list->block_cache[idx] = NULL; + return idx < 0 ? idx : 0; +} + +/* + * Encodes the handle of a particular slot in the pool using metadata + */ +static inline unsigned long metadata_to_handle(struct zblock_block *block, + unsigned int block_type, unsigned int slot) +{ + return (unsigned long)(block) + (block_type << SLOT_BITS) + slot; +} + +/* Returns block, block type and slot in the pool corresponding to handle */ +static inline struct zblock_block *handle_to_metadata(unsigned long handle, + unsigned int *block_type, unsigned int *slot) +{ + *block_type = (handle & (PAGE_SIZE - 1)) >> SLOT_BITS; + *slot = handle & SLOT_MASK; + return (struct zblock_block *)(handle & PAGE_MASK); +} + + +/* + * allocate new block and add it to corresponding block list + */ +static struct zblock_block *alloc_block(struct zblock_pool *pool, + int block_type, gfp_t gfp, + unsigned long *handle) +{ + struct zblock_block *block; + struct block_list *list; + + block = (void *)__get_free_pages(gfp, block_desc[block_type].order); + if (!block) + return NULL; + + list = &(pool->block_lists)[block_type]; + + /* init block data */ + memset(&block->slot_info, 0, sizeof(block->slot_info)); + atomic_set(&block->free_slots, block_desc[block_type].slots_per_block - 1); + block->cache_idx = -1; + set_bit(BIT_SLOT_OCCUPIED, (unsigned long *)block->slot_info); + *handle = metadata_to_handle(block, block_type, 0); + + spin_lock(&list->lock); + cache_insert_block(block, list); + list->block_count++; + spin_unlock(&list->lock); + return block; +} + +/***************** + * API Functions + *****************/ +/** + * zblock_create_pool() - create a new zblock pool + * @gfp: gfp flags when allocating the zblock pool structure + * @ops: user-defined operations for the zblock pool + * + * Return: pointer to the new zblock pool or NULL if the metadata allocation + * failed. + */ +static struct zblock_pool *zblock_create_pool(gfp_t gfp) +{ + struct zblock_pool *pool; + struct block_list *list; + int i, j; + + pool = kmalloc(sizeof(struct zblock_pool), gfp); + if (!pool) + return NULL; + + /* init each block list */ + for (i = 0; i < ARRAY_SIZE(block_desc); i++) { + list = &(pool->block_lists)[i]; + spin_lock_init(&list->lock); + for (j = 0; j < BLOCK_CACHE_SIZE; j++) + list->block_cache[j] = NULL; + list->block_count = 0; + } + atomic_set(&pool->alloc_flag, 0); + return pool; +} + +/** + * zblock_destroy_pool() - destroys an existing zblock pool + * @pool: the zblock pool to be destroyed + * + */ +static void zblock_destroy_pool(struct zblock_pool *pool) +{ + kfree(pool); +} + + +/** + * zblock_alloc() - allocates a slot of appropriate size + * @pool: zblock 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. + */ +static int zblock_alloc(struct zblock_pool *pool, size_t size, gfp_t gfp, + unsigned long *handle) +{ + unsigned int block_type, slot; + struct zblock_block *block; + struct block_list *list; + + 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(block_desc); block_type++) { + if (size <= block_desc[block_type].slot_size) + break; + } + list = &(pool->block_lists[block_type]); + +check: + /* check if there are free slots in cache */ + spin_lock(&list->lock); + block = cache_find_block(list); + spin_unlock(&list->lock); + if (block) + goto found; + + /* not found block with free slots try to allocate new empty block */ + if (atomic_cmpxchg(&pool->alloc_flag, 0, 1)) + goto check; + block = alloc_block(pool, block_type, gfp, handle); + atomic_set(&pool->alloc_flag, 0); + if (block) + return 0; + return -ENOMEM; + +found: + /* find the first free slot in block */ + for (slot = 0; slot < block_desc[block_type].slots_per_block; slot++) { + if (!test_and_set_bit(slot*2 + BIT_SLOT_OCCUPIED, + (unsigned long *)&block->slot_info)) + break; + } + *handle = metadata_to_handle(block, block_type, slot); + return 0; +} + +/** + * zblock_free() - frees the allocation associated with the given handle + * @pool: pool in which the allocation resided + * @handle: handle associated with the allocation returned by zblock_alloc() + * + */ +static void zblock_free(struct zblock_pool *pool, unsigned long handle) +{ + unsigned int slot, block_type; + struct zblock_block *block; + struct block_list *list; + + block = handle_to_metadata(handle, &block_type, &slot); + list = &(pool->block_lists[block_type]); + + spin_lock(&list->lock); + /* if all slots in block are empty delete whole block */ + if (atomic_inc_return(&block->free_slots) == block_desc[block_type].slots_per_block) { + list->block_count--; + cache_remove_block(list, block); + spin_unlock(&list->lock); + free_pages((unsigned long)block, block_desc[block_type].order); + return; + } + + if (atomic_read(&block->free_slots) < block_desc[block_type].slots_per_block/2 + && block->cache_idx == -1) + cache_insert_block(block, list); + spin_unlock(&list->lock); + + clear_bit(slot*2 + BIT_SLOT_OCCUPIED, (unsigned long *)block->slot_info); +} + +/** + * zblock_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 + */ +static void *zblock_map(struct zblock_pool *pool, unsigned long handle) +{ + unsigned int block_type, slot; + struct zblock_block *block; + void *p; + + block = handle_to_metadata(handle, &block_type, &slot); + p = (void *)block + ZBLOCK_HEADER_SIZE + slot * block_desc[block_type].slot_size; + return p; +} + +/** + * zblock_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 + */ +static void zblock_unmap(struct zblock_pool *pool, unsigned long handle) +{ +} + +/** + * zblock_get_total_pages() - gets the zblock pool size in pages + * @pool: pool being queried + * + * Returns: size in bytes of the given pool. + */ +static u64 zblock_get_total_pages(struct zblock_pool *pool) +{ + u64 total_size; + int i; + + total_size = 0; + for (i = 0; i < ARRAY_SIZE(block_desc); i++) + total_size += pool->block_lists[i].block_count << block_desc[i].order; + + return total_size; +} + +/***************** + * zpool + ****************/ + +static void *zblock_zpool_create(const char *name, gfp_t gfp) +{ + return zblock_create_pool(gfp); +} + +static void zblock_zpool_destroy(void *pool) +{ + zblock_destroy_pool(pool); +} + +static int zblock_zpool_malloc(void *pool, size_t size, gfp_t gfp, + unsigned long *handle) +{ + return zblock_alloc(pool, size, gfp, handle); +} + +static void zblock_zpool_free(void *pool, unsigned long handle) +{ + zblock_free(pool, handle); +} + +static void *zblock_zpool_map(void *pool, unsigned long handle, + enum zpool_mapmode mm) +{ + return zblock_map(pool, handle); +} + +static void zblock_zpool_unmap(void *pool, unsigned long handle) +{ + zblock_unmap(pool, handle); +} + +static u64 zblock_zpool_total_pages(void *pool) +{ + return zblock_get_total_pages(pool); +} + +static struct zpool_driver zblock_zpool_driver = { + .type = "zblock", + .owner = THIS_MODULE, + .create = zblock_zpool_create, + .destroy = zblock_zpool_destroy, + .malloc = zblock_zpool_malloc, + .free = zblock_zpool_free, + .map = zblock_zpool_map, + .unmap = zblock_zpool_unmap, + .total_pages = zblock_zpool_total_pages, +}; + +MODULE_ALIAS("zpool-zblock"); + +static int __init init_zblock(void) +{ + pr_info("loaded\n"); + zpool_register_driver(&zblock_zpool_driver); + return 0; +} + +static void __exit exit_zblock(void) +{ + zpool_unregister_driver(&zblock_zpool_driver); + pr_info("unloaded\n"); +} + +module_init(init_zblock); +module_exit(exit_zblock); + +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Vitaly Wool "); +MODULE_DESCRIPTION("Block allocator for compressed pages");