linux-imx

/*

 * zbud.c

 *

 * Copyright (C) 2013, Seth Jennings, IBM

 *

 * Concepts based on zcache internal zbud allocator by Dan Magenheimer.

 *

 * zbud is an special purpose allocator for storing compressed pages.  Contrary

 * to what its name may suggest, zbud is not a buddy allocator, but rather an

 * allocator that "buddies" two compressed pages together in a single memory

 * page.

 *

 * While this design limits storage density, it has simple and deterministic

 * reclaim properties that make it preferable to a higher density approach when

 * reclaim will be used.

 *

 * zbud works by storing compressed pages, or "zpages", together in pairs in a

 * single memory page called a "zbud page".  The first buddy is "left

 * justified" at the beginning of the zbud page, and the last buddy is "right

 * justified" at the end of the zbud page.  The benefit is that if either

 * buddy is freed, the freed buddy space, coalesced with whatever slack space

 * that existed between the buddies, results in the largest possible free region

 * within the zbud page.

 *

 * zbud also provides an attractive lower bound on density. The ratio of zpages

 * to zbud pages can not be less than 1.  This ensures that zbud can never "do

 * harm" by using more pages to store zpages than the uncompressed zpages would

 * have used on their own.

 *

 * zbud pages are divided into "chunks".  The size of the chunks is fixed at

 * compile time and determined by NCHUNKS_ORDER below.  Dividing zbud pages

 * into chunks allows organizing unbuddied zbud pages into a manageable number

 * of unbuddied lists according to the number of free chunks available in the

 * zbud page.

 *

 * The zbud API differs from that of conventional allocators in that the

 * allocation function, zbud_alloc(), returns an opaque handle to the user,

 * not a dereferenceable pointer.  The user must map the handle using

 * zbud_map() in order to get a usable pointer by which to access the

 * allocation data and unmap the handle with zbud_unmap() when operations

 * on the allocation data are complete.

 */

​

#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt

​

#include <linux/atomic.h>

#include <linux/list.h>

#include <linux/mm.h>

#include <linux/module.h>

#include <linux/preempt.h>

#include <linux/slab.h>

#include <linux/spinlock.h>

#include <linux/zbud.h>

#include <linux/zpool.h>

​

/*****************

 * Structures

*****************/

/*

 * NCHUNKS_ORDER determines the internal allocation granularity, effectively

 * adjusting internal fragmentation.  It also determines the number of

 * freelists maintained in each pool. NCHUNKS_ORDER of 6 means that the

 * allocation granularity will be in chunks of size PAGE_SIZE/64. As one chunk

 * in allocated page is occupied by zbud header, NCHUNKS will be calculated to

 * 63 which shows the max number of free chunks in zbud page, also there will be

 * 63 freelists per pool.

 */

#define NCHUNKS_ORDER   6

​

#define CHUNK_SHIFT (PAGE_SHIFT - NCHUNKS_ORDER)

#define CHUNK_SIZE  (1 << CHUNK_SHIFT)

#define ZHDR_SIZE_ALIGNED CHUNK_SIZE

#define NCHUNKS     ((PAGE_SIZE - ZHDR_SIZE_ALIGNED) >> CHUNK_SHIFT)

​

/**

 * struct zbud_pool - stores metadata for each zbud pool

 * @lock:   protects all pool fields and first|last_chunk fields of any

 *      zbud page in the pool

 * @unbuddied:  array of lists tracking zbud pages that only contain one buddy;

 *      the lists each zbud page is added to depends on the size of

 *      its free region.

 * @buddied:    list tracking the zbud pages that contain two buddies;

 *      these zbud pages are full

 * @lru:    list tracking the zbud pages in LRU order by most recently

 *      added buddy.

 * @pages_nr:   number of zbud pages in the pool.

 * @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

 * pertaining to a particular zbud pool.

 */