/*
* zsmalloc memory allocator
*
* Copyright (C) 2011 Nitin Gupta
* Copyright (C) 2012, 2013 Minchan Kim
*
* This code is released using a dual license strategy: BSD/GPL
* You can choose the license that better fits your requirements.
*
* Released under the terms of 3-clause BSD License
* Released under the terms of GNU General Public License Version 2.0
*/
/*
* This allocator is designed for use with zram. Thus, the allocator is
* supposed to work well under low memory conditions. In particular, it
* never attempts higher order page allocation which is very likely to
* fail under memory pressure. On the other hand, if we just use single
* (0-order) pages, it would suffer from very high fragmentation --
* any object of size PAGE_SIZE/2 or larger would occupy an entire page.
* This was one of the major issues with its predecessor (xvmalloc).
*
* To overcome these issues, zsmalloc allocates a bunch of 0-order pages
* and links them together using various 'struct page' fields. These linked
* pages act as a single higher-order page i.e. an object can span 0-order
* page boundaries. The code refers to these linked pages as a single entity
* called zspage.
*
* For simplicity, zsmalloc can only allocate objects of size up to PAGE_SIZE
* since this satisfies the requirements of all its current users (in the
* worst case, page is incompressible and is thus stored "as-is" i.e. in
* uncompressed form). For allocation requests larger than this size, failure
* is returned (see zs_malloc).
*
* Additionally, zs_malloc() does not return a dereferenceable pointer.
* Instead, it returns an opaque handle (unsigned long) which encodes actual
* location of the allocated object. The reason for this indirection is that
* zsmalloc does not keep zspages permanently mapped since that would cause
* issues on 32-bit systems where the VA region for kernel space mappings
* is very small. So, before using the allocating memory, the object has to
* be mapped using zs_map_object() to get a usable pointer and subsequently
* unmapped using zs_unmap_object().
*
* Following is how we use various fields and flags of underlying
* struct page(s) to form a zspage.
*
* Usage of struct page fields:
* page->first_page: points to the first component (0-order) page
* page->index (union with page->freelist): offset of the first object
* starting in this page. For the first page, this is
* always 0, so we use this field (aka freelist) to point
* to the first free object in zspage.
* page->lru: links together all component pages (except the first page)
* of a zspage
*
* For _first_ page only:
*
* page->private (union with page->first_page): refers to the
* component page after the first page
* page->freelist: points to the first free object in zspage.
* Free objects are linked together using in-place
* metadata.
* page->objects: maximum number of objects we can store in this
* zspage (class->zspage_order * PAGE_SIZE / class->size)
* page->lru: links together first pages of various zspages.
* Basically forming list of zspages in a fullness group.
* page->mapping: class index and fullness group of the zspage
*
* Usage of struct page flags:
* PG_private: identifies the first component page
* PG_private2: identifies the last component page
*
*/
#ifdef CONFIG_ZSMALLOC_DEBUG
#define DEBUG
#endif
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/bitops.h>
#include <linux/errno.h>
#include <linux/highmem.h>
#include <linux/string.h>
#include <linux/slab.h>
#include <asm/tlbflush.h>
#include <asm/pgtable.h>
#include <linux/cpumask.h>
#include <linux/cpu.h>
#include <linux/vmalloc.h>
#include <linux/hardirq.h>
#include <linux/spinlock.h>
#include <linux/types.h>
#include <linux/zsmalloc.h>
#include <linux/zpool.h>
/*
* This must be power of 2 and greater than of equal to sizeof(link_free).
* These two conditions ensure that any 'struct link_free' itself doesn't
* span more than 1 page which avoids complex case of mapping 2 pages simply
* to restore link_free pointer values.
*/
#define ZS_ALIGN 8
/*
* A single 'zspage' is composed of up to 2^N discontiguous 0-order (single)
* pages. ZS_MAX_ZSPAGE_ORDER defines upper limit on N.
*/
#define ZS_MAX_ZSPAGE_ORDER 2
#define ZS_MAX_PAGES_PER_ZSPAGE (_AC(1, UL) << ZS_MAX_ZSPAGE_ORDER)
/*
* Object location (<PFN>, <obj_idx>) is encoded as
* as single (unsigned long) handle value.
*
* Note that object index <obj_idx> is relative to system
* page <PFN> it is stored in, so for each sub-page belonging
* to a zspage, obj_idx starts with 0.
*
* This is made more complicated by various memory models and PAE.
*/
#ifndef MAX_PHYSMEM_BITS
#ifdef CONFIG_HIGHMEM64G
#define MAX_PHYSMEM_BITS 36
#else /* !CONFIG_HIGHMEM64G */
/*
* If this definition of MAX_PHYSMEM_BITS is used, OBJ_INDEX_BITS will just
* be PAGE_SHIFT
*/
#define MAX_PHYSMEM_BITS BITS_PER_LONG
#endif
#endif
#define _PFN_BITS (MAX_PHYSMEM_BITS - PAGE_SHIFT)
#define OBJ_INDEX_BITS (BITS_PER_LONG - _PFN_BITS)
#define OBJ_INDEX_MASK ((_AC(1, UL) << OBJ_INDEX_BITS) - 1)
#define MAX(a, b) ((a) >= (b) ? (a) : (b))
/* ZS_MIN_ALLOC_SIZE must be multiple of ZS_ALIGN */
#define ZS_MIN_ALLOC_SIZE \
MAX(32, (ZS_MAX_PAGES_PER_ZSPAGE << PAGE_SHIFT >> OBJ_INDEX_BITS))
#define ZS_MAX_ALLOC_SIZE PAGE_SIZE
/*
* On systems with 4K page size, this gives 255 size classes! There is a
* trader-off here:
* - Large number of size classes is potentially wasteful as free page are
* spread across these classes
* - Small number of size classes causes large internal fragmentation
* - Probably its better to use specific size classes (empirically
* determined). NOTE: all those class sizes must be set as multiple of
* ZS_ALIGN to make sure link_free itself never has to span 2 pages.
*
* ZS_MIN_ALLOC_SIZE and ZS_SIZE_CLASS_DELTA must be multiple of ZS_ALIGN
* (reason above)
*/
#define ZS_SIZE_CLASS_DELTA (PAGE_SIZE >> 8)
/*
* We do not maintain any list for completely empty or full pages
*/
enum fullness_group {
ZS_ALMOST_FULL,
ZS_ALMOST_EMPTY,
_ZS_NR_FULLNESS_GROUPS,
ZS_EMPTY,
ZS_FULL
};
/*
* number of size_classes
*/
static int zs_size_classes;
/*
* We assign a page to ZS_ALMOST_EMPTY fullness group when:
* n <= N / f, where
* n = number of allocated objects
* N = total number of objects zspage can store
* f = fullness_threshold_frac
*
* Similarly, we assign zspage to:
* ZS_ALMOST_FULL when n > N / f
* ZS_EMPTY when n == 0
* ZS_FULL when n == N
*
* (see: fix_fullness_group())
*/
static const int fullness_threshold_frac = 4;
struct size_class {
/*
* Size of objects stored in this class. Must be multiple
* of ZS_ALIGN.
*/