/*
* 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.