19a001fc1SVitaly Wool /* 29a001fc1SVitaly Wool * z3fold.c 39a001fc1SVitaly Wool * 49a001fc1SVitaly Wool * Author: Vitaly Wool <vitaly.wool@konsulko.com> 59a001fc1SVitaly Wool * Copyright (C) 2016, Sony Mobile Communications Inc. 69a001fc1SVitaly Wool * 79a001fc1SVitaly Wool * This implementation is based on zbud written by Seth Jennings. 89a001fc1SVitaly Wool * 99a001fc1SVitaly Wool * z3fold is an special purpose allocator for storing compressed pages. It 109a001fc1SVitaly Wool * can store up to three compressed pages per page which improves the 119a001fc1SVitaly Wool * compression ratio of zbud while retaining its main concepts (e. g. always 129a001fc1SVitaly Wool * storing an integral number of objects per page) and simplicity. 139a001fc1SVitaly Wool * It still has simple and deterministic reclaim properties that make it 149a001fc1SVitaly Wool * preferable to a higher density approach (with no requirement on integral 159a001fc1SVitaly Wool * number of object per page) when reclaim is used. 169a001fc1SVitaly Wool * 179a001fc1SVitaly Wool * As in zbud, pages are divided into "chunks". The size of the chunks is 189a001fc1SVitaly Wool * fixed at compile time and is determined by NCHUNKS_ORDER below. 199a001fc1SVitaly Wool * 209a001fc1SVitaly Wool * z3fold doesn't export any API and is meant to be used via zpool API. 219a001fc1SVitaly Wool */ 229a001fc1SVitaly Wool 239a001fc1SVitaly Wool #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt 249a001fc1SVitaly Wool 259a001fc1SVitaly Wool #include <linux/atomic.h> 26d30561c5SVitaly Wool #include <linux/sched.h> 279a001fc1SVitaly Wool #include <linux/list.h> 289a001fc1SVitaly Wool #include <linux/mm.h> 299a001fc1SVitaly Wool #include <linux/module.h> 30d30561c5SVitaly Wool #include <linux/percpu.h> 319a001fc1SVitaly Wool #include <linux/preempt.h> 32d30561c5SVitaly Wool #include <linux/workqueue.h> 339a001fc1SVitaly Wool #include <linux/slab.h> 349a001fc1SVitaly Wool #include <linux/spinlock.h> 359a001fc1SVitaly Wool #include <linux/zpool.h> 369a001fc1SVitaly Wool 379a001fc1SVitaly Wool /***************** 389a001fc1SVitaly Wool * Structures 399a001fc1SVitaly Wool *****************/ 40ede93213SVitaly Wool struct z3fold_pool; 41ede93213SVitaly Wool struct z3fold_ops { 42ede93213SVitaly Wool int (*evict)(struct z3fold_pool *pool, unsigned long handle); 43ede93213SVitaly Wool }; 44ede93213SVitaly Wool 45ede93213SVitaly Wool enum buddy { 46ede93213SVitaly Wool HEADLESS = 0, 47ede93213SVitaly Wool FIRST, 48ede93213SVitaly Wool MIDDLE, 49ede93213SVitaly Wool LAST, 50ede93213SVitaly Wool BUDDIES_MAX 51ede93213SVitaly Wool }; 52ede93213SVitaly Wool 53ede93213SVitaly Wool /* 54d30561c5SVitaly Wool * struct z3fold_header - z3fold page metadata occupying first chunks of each 55ede93213SVitaly Wool * z3fold page, except for HEADLESS pages 56d30561c5SVitaly Wool * @buddy: links the z3fold page into the relevant list in the 57d30561c5SVitaly Wool * pool 582f1e5e4dSVitaly Wool * @page_lock: per-page lock 59d30561c5SVitaly Wool * @refcount: reference count for the z3fold page 60d30561c5SVitaly Wool * @work: work_struct for page layout optimization 61d30561c5SVitaly Wool * @pool: pointer to the pool which this page belongs to 62d30561c5SVitaly Wool * @cpu: CPU which this page "belongs" to 63ede93213SVitaly Wool * @first_chunks: the size of the first buddy in chunks, 0 if free 64ede93213SVitaly Wool * @middle_chunks: the size of the middle buddy in chunks, 0 if free 65ede93213SVitaly Wool * @last_chunks: the size of the last buddy in chunks, 0 if free 66ede93213SVitaly Wool * @first_num: the starting number (for the first handle) 67ede93213SVitaly Wool */ 68ede93213SVitaly Wool struct z3fold_header { 69ede93213SVitaly Wool struct list_head buddy; 702f1e5e4dSVitaly Wool spinlock_t page_lock; 715a27aa82SVitaly Wool struct kref refcount; 72d30561c5SVitaly Wool struct work_struct work; 73d30561c5SVitaly Wool struct z3fold_pool *pool; 74d30561c5SVitaly Wool short cpu; 75ede93213SVitaly Wool unsigned short first_chunks; 76ede93213SVitaly Wool unsigned short middle_chunks; 77ede93213SVitaly Wool unsigned short last_chunks; 78ede93213SVitaly Wool unsigned short start_middle; 79ede93213SVitaly Wool unsigned short first_num:2; 80ede93213SVitaly Wool }; 81ede93213SVitaly Wool 829a001fc1SVitaly Wool /* 839a001fc1SVitaly Wool * NCHUNKS_ORDER determines the internal allocation granularity, effectively 849a001fc1SVitaly Wool * adjusting internal fragmentation. It also determines the number of 859a001fc1SVitaly Wool * freelists maintained in each pool. NCHUNKS_ORDER of 6 means that the 86ede93213SVitaly Wool * allocation granularity will be in chunks of size PAGE_SIZE/64. Some chunks 87ede93213SVitaly Wool * in the beginning of an allocated page are occupied by z3fold header, so 88ede93213SVitaly Wool * NCHUNKS will be calculated to 63 (or 62 in case CONFIG_DEBUG_SPINLOCK=y), 89ede93213SVitaly Wool * which shows the max number of free chunks in z3fold page, also there will 90ede93213SVitaly Wool * be 63, or 62, respectively, freelists per pool. 919a001fc1SVitaly Wool */ 929a001fc1SVitaly Wool #define NCHUNKS_ORDER 6 939a001fc1SVitaly Wool 949a001fc1SVitaly Wool #define CHUNK_SHIFT (PAGE_SHIFT - NCHUNKS_ORDER) 959a001fc1SVitaly Wool #define CHUNK_SIZE (1 << CHUNK_SHIFT) 96ede93213SVitaly Wool #define ZHDR_SIZE_ALIGNED round_up(sizeof(struct z3fold_header), CHUNK_SIZE) 97ede93213SVitaly Wool #define ZHDR_CHUNKS (ZHDR_SIZE_ALIGNED >> CHUNK_SHIFT) 98ede93213SVitaly Wool #define TOTAL_CHUNKS (PAGE_SIZE >> CHUNK_SHIFT) 999a001fc1SVitaly Wool #define NCHUNKS ((PAGE_SIZE - ZHDR_SIZE_ALIGNED) >> CHUNK_SHIFT) 1009a001fc1SVitaly Wool 101f201ebd8Szhong jiang #define BUDDY_MASK (0x3) 1029a001fc1SVitaly Wool 1039a001fc1SVitaly Wool /** 1049a001fc1SVitaly Wool * struct z3fold_pool - stores metadata for each z3fold pool 105d30561c5SVitaly Wool * @name: pool name 106d30561c5SVitaly Wool * @lock: protects pool unbuddied/lru lists 107d30561c5SVitaly Wool * @stale_lock: protects pool stale page list 108d30561c5SVitaly Wool * @unbuddied: per-cpu array of lists tracking z3fold pages that contain 2- 109d30561c5SVitaly Wool * buddies; the list each z3fold page is added to depends on 110d30561c5SVitaly Wool * the size of its free region. 1119a001fc1SVitaly Wool * @lru: list tracking the z3fold pages in LRU order by most recently 1129a001fc1SVitaly Wool * added buddy. 113d30561c5SVitaly Wool * @stale: list of pages marked for freeing 1149a001fc1SVitaly Wool * @pages_nr: number of z3fold pages in the pool. 1159a001fc1SVitaly Wool * @ops: pointer to a structure of user defined operations specified at 1169a001fc1SVitaly Wool * pool creation time. 117d30561c5SVitaly Wool * @compact_wq: workqueue for page layout background optimization 118d30561c5SVitaly Wool * @release_wq: workqueue for safe page release 119d30561c5SVitaly Wool * @work: work_struct for safe page release 1209a001fc1SVitaly Wool * 1219a001fc1SVitaly Wool * This structure is allocated at pool creation time and maintains metadata 1229a001fc1SVitaly Wool * pertaining to a particular z3fold pool. 1239a001fc1SVitaly Wool */ 1249a001fc1SVitaly Wool struct z3fold_pool { 125d30561c5SVitaly Wool const char *name; 1269a001fc1SVitaly Wool spinlock_t lock; 127d30561c5SVitaly Wool spinlock_t stale_lock; 128d30561c5SVitaly Wool struct list_head *unbuddied; 1299a001fc1SVitaly Wool struct list_head lru; 130d30561c5SVitaly Wool struct list_head stale; 13112d59ae6SVitaly Wool atomic64_t pages_nr; 1329a001fc1SVitaly Wool const struct z3fold_ops *ops; 1339a001fc1SVitaly Wool struct zpool *zpool; 1349a001fc1SVitaly Wool const struct zpool_ops *zpool_ops; 135d30561c5SVitaly Wool struct workqueue_struct *compact_wq; 136d30561c5SVitaly Wool struct workqueue_struct *release_wq; 137d30561c5SVitaly Wool struct work_struct work; 1389a001fc1SVitaly Wool }; 1399a001fc1SVitaly Wool 1409a001fc1SVitaly Wool /* 1419a001fc1SVitaly Wool * Internal z3fold page flags 1429a001fc1SVitaly Wool */ 1439a001fc1SVitaly Wool enum z3fold_page_flags { 1445a27aa82SVitaly Wool PAGE_HEADLESS = 0, 1459a001fc1SVitaly Wool MIDDLE_CHUNK_MAPPED, 146d30561c5SVitaly Wool NEEDS_COMPACTING, 147d30561c5SVitaly Wool PAGE_STALE 1489a001fc1SVitaly Wool }; 1499a001fc1SVitaly Wool 1509a001fc1SVitaly Wool /***************** 1519a001fc1SVitaly Wool * Helpers 1529a001fc1SVitaly Wool *****************/ 1539a001fc1SVitaly Wool 1549a001fc1SVitaly Wool /* Converts an allocation size in bytes to size in z3fold chunks */ 1559a001fc1SVitaly Wool static int size_to_chunks(size_t size) 1569a001fc1SVitaly Wool { 1579a001fc1SVitaly Wool return (size + CHUNK_SIZE - 1) >> CHUNK_SHIFT; 1589a001fc1SVitaly Wool } 1599a001fc1SVitaly Wool 1609a001fc1SVitaly Wool #define for_each_unbuddied_list(_iter, _begin) \ 1619a001fc1SVitaly Wool for ((_iter) = (_begin); (_iter) < NCHUNKS; (_iter)++) 1629a001fc1SVitaly Wool 163d30561c5SVitaly Wool static void compact_page_work(struct work_struct *w); 164d30561c5SVitaly Wool 1659a001fc1SVitaly Wool /* Initializes the z3fold header of a newly allocated z3fold page */ 166d30561c5SVitaly Wool static struct z3fold_header *init_z3fold_page(struct page *page, 167d30561c5SVitaly Wool struct z3fold_pool *pool) 1689a001fc1SVitaly Wool { 1699a001fc1SVitaly Wool struct z3fold_header *zhdr = page_address(page); 1709a001fc1SVitaly Wool 1719a001fc1SVitaly Wool INIT_LIST_HEAD(&page->lru); 1729a001fc1SVitaly Wool clear_bit(PAGE_HEADLESS, &page->private); 1739a001fc1SVitaly Wool clear_bit(MIDDLE_CHUNK_MAPPED, &page->private); 174d30561c5SVitaly Wool clear_bit(NEEDS_COMPACTING, &page->private); 175d30561c5SVitaly Wool clear_bit(PAGE_STALE, &page->private); 1769a001fc1SVitaly Wool 1772f1e5e4dSVitaly Wool spin_lock_init(&zhdr->page_lock); 1785a27aa82SVitaly Wool kref_init(&zhdr->refcount); 1799a001fc1SVitaly Wool zhdr->first_chunks = 0; 1809a001fc1SVitaly Wool zhdr->middle_chunks = 0; 1819a001fc1SVitaly Wool zhdr->last_chunks = 0; 1829a001fc1SVitaly Wool zhdr->first_num = 0; 1839a001fc1SVitaly Wool zhdr->start_middle = 0; 184d30561c5SVitaly Wool zhdr->cpu = -1; 185d30561c5SVitaly Wool zhdr->pool = pool; 1869a001fc1SVitaly Wool INIT_LIST_HEAD(&zhdr->buddy); 187d30561c5SVitaly Wool INIT_WORK(&zhdr->work, compact_page_work); 1889a001fc1SVitaly Wool return zhdr; 1899a001fc1SVitaly Wool } 1909a001fc1SVitaly Wool 1919a001fc1SVitaly Wool /* Resets the struct page fields and frees the page */ 1925a27aa82SVitaly Wool static void free_z3fold_page(struct page *page) 1939a001fc1SVitaly Wool { 1945a27aa82SVitaly Wool __free_page(page); 1955a27aa82SVitaly Wool } 1965a27aa82SVitaly Wool 1972f1e5e4dSVitaly Wool /* Lock a z3fold page */ 1982f1e5e4dSVitaly Wool static inline void z3fold_page_lock(struct z3fold_header *zhdr) 1992f1e5e4dSVitaly Wool { 2002f1e5e4dSVitaly Wool spin_lock(&zhdr->page_lock); 2012f1e5e4dSVitaly Wool } 2022f1e5e4dSVitaly Wool 20376e32a2aSVitaly Wool /* Try to lock a z3fold page */ 20476e32a2aSVitaly Wool static inline int z3fold_page_trylock(struct z3fold_header *zhdr) 20576e32a2aSVitaly Wool { 20676e32a2aSVitaly Wool return spin_trylock(&zhdr->page_lock); 20776e32a2aSVitaly Wool } 20876e32a2aSVitaly Wool 2092f1e5e4dSVitaly Wool /* Unlock a z3fold page */ 2102f1e5e4dSVitaly Wool static inline void z3fold_page_unlock(struct z3fold_header *zhdr) 2112f1e5e4dSVitaly Wool { 2122f1e5e4dSVitaly Wool spin_unlock(&zhdr->page_lock); 2132f1e5e4dSVitaly Wool } 2142f1e5e4dSVitaly Wool 2159a001fc1SVitaly Wool /* 2169a001fc1SVitaly Wool * Encodes the handle of a particular buddy within a z3fold page 2179a001fc1SVitaly Wool * Pool lock should be held as this function accesses first_num 2189a001fc1SVitaly Wool */ 2199a001fc1SVitaly Wool static unsigned long encode_handle(struct z3fold_header *zhdr, enum buddy bud) 2209a001fc1SVitaly Wool { 2219a001fc1SVitaly Wool unsigned long handle; 2229a001fc1SVitaly Wool 2239a001fc1SVitaly Wool handle = (unsigned long)zhdr; 2249a001fc1SVitaly Wool if (bud != HEADLESS) 2259a001fc1SVitaly Wool handle += (bud + zhdr->first_num) & BUDDY_MASK; 2269a001fc1SVitaly Wool return handle; 2279a001fc1SVitaly Wool } 2289a001fc1SVitaly Wool 2299a001fc1SVitaly Wool /* Returns the z3fold page where a given handle is stored */ 2309a001fc1SVitaly Wool static struct z3fold_header *handle_to_z3fold_header(unsigned long handle) 2319a001fc1SVitaly Wool { 2329a001fc1SVitaly Wool return (struct z3fold_header *)(handle & PAGE_MASK); 2339a001fc1SVitaly Wool } 2349a001fc1SVitaly Wool 235f201ebd8Szhong jiang /* 236f201ebd8Szhong jiang * (handle & BUDDY_MASK) < zhdr->first_num is possible in encode_handle 237f201ebd8Szhong jiang * but that doesn't matter. because the masking will result in the 238f201ebd8Szhong jiang * correct buddy number. 239f201ebd8Szhong jiang */ 2409a001fc1SVitaly Wool static enum buddy handle_to_buddy(unsigned long handle) 2419a001fc1SVitaly Wool { 2429a001fc1SVitaly Wool struct z3fold_header *zhdr = handle_to_z3fold_header(handle); 2439a001fc1SVitaly Wool return (handle - zhdr->first_num) & BUDDY_MASK; 2449a001fc1SVitaly Wool } 2459a001fc1SVitaly Wool 246d30561c5SVitaly Wool static void __release_z3fold_page(struct z3fold_header *zhdr, bool locked) 247d30561c5SVitaly Wool { 248d30561c5SVitaly Wool struct page *page = virt_to_page(zhdr); 249d30561c5SVitaly Wool struct z3fold_pool *pool = zhdr->pool; 250d30561c5SVitaly Wool 251d30561c5SVitaly Wool WARN_ON(!list_empty(&zhdr->buddy)); 252d30561c5SVitaly Wool set_bit(PAGE_STALE, &page->private); 253*35529357SVitaly Wool clear_bit(NEEDS_COMPACTING, &page->private); 254d30561c5SVitaly Wool spin_lock(&pool->lock); 255d30561c5SVitaly Wool if (!list_empty(&page->lru)) 256d30561c5SVitaly Wool list_del(&page->lru); 257d30561c5SVitaly Wool spin_unlock(&pool->lock); 258d30561c5SVitaly Wool if (locked) 259d30561c5SVitaly Wool z3fold_page_unlock(zhdr); 260d30561c5SVitaly Wool spin_lock(&pool->stale_lock); 261d30561c5SVitaly Wool list_add(&zhdr->buddy, &pool->stale); 262d30561c5SVitaly Wool queue_work(pool->release_wq, &pool->work); 263d30561c5SVitaly Wool spin_unlock(&pool->stale_lock); 264d30561c5SVitaly Wool } 265d30561c5SVitaly Wool 266d30561c5SVitaly Wool static void __attribute__((__unused__)) 267d30561c5SVitaly Wool release_z3fold_page(struct kref *ref) 268d30561c5SVitaly Wool { 269d30561c5SVitaly Wool struct z3fold_header *zhdr = container_of(ref, struct z3fold_header, 270d30561c5SVitaly Wool refcount); 271d30561c5SVitaly Wool __release_z3fold_page(zhdr, false); 272d30561c5SVitaly Wool } 273d30561c5SVitaly Wool 274d30561c5SVitaly Wool static void release_z3fold_page_locked(struct kref *ref) 275d30561c5SVitaly Wool { 276d30561c5SVitaly Wool struct z3fold_header *zhdr = container_of(ref, struct z3fold_header, 277d30561c5SVitaly Wool refcount); 278d30561c5SVitaly Wool WARN_ON(z3fold_page_trylock(zhdr)); 279d30561c5SVitaly Wool __release_z3fold_page(zhdr, true); 280d30561c5SVitaly Wool } 281d30561c5SVitaly Wool 282d30561c5SVitaly Wool static void release_z3fold_page_locked_list(struct kref *ref) 283d30561c5SVitaly Wool { 284d30561c5SVitaly Wool struct z3fold_header *zhdr = container_of(ref, struct z3fold_header, 285d30561c5SVitaly Wool refcount); 286d30561c5SVitaly Wool spin_lock(&zhdr->pool->lock); 287d30561c5SVitaly Wool list_del_init(&zhdr->buddy); 288d30561c5SVitaly Wool spin_unlock(&zhdr->pool->lock); 289d30561c5SVitaly Wool 290d30561c5SVitaly Wool WARN_ON(z3fold_page_trylock(zhdr)); 291d30561c5SVitaly Wool __release_z3fold_page(zhdr, true); 292d30561c5SVitaly Wool } 293d30561c5SVitaly Wool 294d30561c5SVitaly Wool static void free_pages_work(struct work_struct *w) 295d30561c5SVitaly Wool { 296d30561c5SVitaly Wool struct z3fold_pool *pool = container_of(w, struct z3fold_pool, work); 297d30561c5SVitaly Wool 298d30561c5SVitaly Wool spin_lock(&pool->stale_lock); 299d30561c5SVitaly Wool while (!list_empty(&pool->stale)) { 300d30561c5SVitaly Wool struct z3fold_header *zhdr = list_first_entry(&pool->stale, 301d30561c5SVitaly Wool struct z3fold_header, buddy); 302d30561c5SVitaly Wool struct page *page = virt_to_page(zhdr); 303d30561c5SVitaly Wool 304d30561c5SVitaly Wool list_del(&zhdr->buddy); 305d30561c5SVitaly Wool if (WARN_ON(!test_bit(PAGE_STALE, &page->private))) 306d30561c5SVitaly Wool continue; 307d30561c5SVitaly Wool spin_unlock(&pool->stale_lock); 308d30561c5SVitaly Wool cancel_work_sync(&zhdr->work); 309d30561c5SVitaly Wool free_z3fold_page(page); 310d30561c5SVitaly Wool cond_resched(); 311d30561c5SVitaly Wool spin_lock(&pool->stale_lock); 312d30561c5SVitaly Wool } 313d30561c5SVitaly Wool spin_unlock(&pool->stale_lock); 314d30561c5SVitaly Wool } 315d30561c5SVitaly Wool 3169a001fc1SVitaly Wool /* 3179a001fc1SVitaly Wool * Returns the number of free chunks in a z3fold page. 3189a001fc1SVitaly Wool * NB: can't be used with HEADLESS pages. 3199a001fc1SVitaly Wool */ 3209a001fc1SVitaly Wool static int num_free_chunks(struct z3fold_header *zhdr) 3219a001fc1SVitaly Wool { 3229a001fc1SVitaly Wool int nfree; 3239a001fc1SVitaly Wool /* 3249a001fc1SVitaly Wool * If there is a middle object, pick up the bigger free space 3259a001fc1SVitaly Wool * either before or after it. Otherwise just subtract the number 3269a001fc1SVitaly Wool * of chunks occupied by the first and the last objects. 3279a001fc1SVitaly Wool */ 3289a001fc1SVitaly Wool if (zhdr->middle_chunks != 0) { 3299a001fc1SVitaly Wool int nfree_before = zhdr->first_chunks ? 330ede93213SVitaly Wool 0 : zhdr->start_middle - ZHDR_CHUNKS; 3319a001fc1SVitaly Wool int nfree_after = zhdr->last_chunks ? 332ede93213SVitaly Wool 0 : TOTAL_CHUNKS - 333ede93213SVitaly Wool (zhdr->start_middle + zhdr->middle_chunks); 3349a001fc1SVitaly Wool nfree = max(nfree_before, nfree_after); 3359a001fc1SVitaly Wool } else 3369a001fc1SVitaly Wool nfree = NCHUNKS - zhdr->first_chunks - zhdr->last_chunks; 3379a001fc1SVitaly Wool return nfree; 3389a001fc1SVitaly Wool } 3399a001fc1SVitaly Wool 340ede93213SVitaly Wool static inline void *mchunk_memmove(struct z3fold_header *zhdr, 341ede93213SVitaly Wool unsigned short dst_chunk) 342ede93213SVitaly Wool { 343ede93213SVitaly Wool void *beg = zhdr; 344ede93213SVitaly Wool return memmove(beg + (dst_chunk << CHUNK_SHIFT), 345ede93213SVitaly Wool beg + (zhdr->start_middle << CHUNK_SHIFT), 346ede93213SVitaly Wool zhdr->middle_chunks << CHUNK_SHIFT); 347ede93213SVitaly Wool } 348ede93213SVitaly Wool 3491b096e5aSVitaly Wool #define BIG_CHUNK_GAP 3 3509a001fc1SVitaly Wool /* Has to be called with lock held */ 3519a001fc1SVitaly Wool static int z3fold_compact_page(struct z3fold_header *zhdr) 3529a001fc1SVitaly Wool { 3539a001fc1SVitaly Wool struct page *page = virt_to_page(zhdr); 3549a001fc1SVitaly Wool 355ede93213SVitaly Wool if (test_bit(MIDDLE_CHUNK_MAPPED, &page->private)) 356ede93213SVitaly Wool return 0; /* can't move middle chunk, it's used */ 3579a001fc1SVitaly Wool 358ede93213SVitaly Wool if (zhdr->middle_chunks == 0) 359ede93213SVitaly Wool return 0; /* nothing to compact */ 360ede93213SVitaly Wool 361ede93213SVitaly Wool if (zhdr->first_chunks == 0 && zhdr->last_chunks == 0) { 362ede93213SVitaly Wool /* move to the beginning */ 363ede93213SVitaly Wool mchunk_memmove(zhdr, ZHDR_CHUNKS); 3649a001fc1SVitaly Wool zhdr->first_chunks = zhdr->middle_chunks; 3659a001fc1SVitaly Wool zhdr->middle_chunks = 0; 3669a001fc1SVitaly Wool zhdr->start_middle = 0; 3679a001fc1SVitaly Wool zhdr->first_num++; 368ede93213SVitaly Wool return 1; 3699a001fc1SVitaly Wool } 3709a001fc1SVitaly Wool 3711b096e5aSVitaly Wool /* 3721b096e5aSVitaly Wool * moving data is expensive, so let's only do that if 3731b096e5aSVitaly Wool * there's substantial gain (at least BIG_CHUNK_GAP chunks) 3741b096e5aSVitaly Wool */ 3751b096e5aSVitaly Wool if (zhdr->first_chunks != 0 && zhdr->last_chunks == 0 && 3761b096e5aSVitaly Wool zhdr->start_middle - (zhdr->first_chunks + ZHDR_CHUNKS) >= 3771b096e5aSVitaly Wool BIG_CHUNK_GAP) { 3781b096e5aSVitaly Wool mchunk_memmove(zhdr, zhdr->first_chunks + ZHDR_CHUNKS); 3791b096e5aSVitaly Wool zhdr->start_middle = zhdr->first_chunks + ZHDR_CHUNKS; 3801b096e5aSVitaly Wool return 1; 3811b096e5aSVitaly Wool } else if (zhdr->last_chunks != 0 && zhdr->first_chunks == 0 && 3821b096e5aSVitaly Wool TOTAL_CHUNKS - (zhdr->last_chunks + zhdr->start_middle 3831b096e5aSVitaly Wool + zhdr->middle_chunks) >= 3841b096e5aSVitaly Wool BIG_CHUNK_GAP) { 3851b096e5aSVitaly Wool unsigned short new_start = TOTAL_CHUNKS - zhdr->last_chunks - 3861b096e5aSVitaly Wool zhdr->middle_chunks; 3871b096e5aSVitaly Wool mchunk_memmove(zhdr, new_start); 3881b096e5aSVitaly Wool zhdr->start_middle = new_start; 3891b096e5aSVitaly Wool return 1; 3901b096e5aSVitaly Wool } 3911b096e5aSVitaly Wool 3921b096e5aSVitaly Wool return 0; 3931b096e5aSVitaly Wool } 3941b096e5aSVitaly Wool 395d30561c5SVitaly Wool static void do_compact_page(struct z3fold_header *zhdr, bool locked) 396d30561c5SVitaly Wool { 397d30561c5SVitaly Wool struct z3fold_pool *pool = zhdr->pool; 398d30561c5SVitaly Wool struct page *page; 399d30561c5SVitaly Wool struct list_head *unbuddied; 400d30561c5SVitaly Wool int fchunks; 401d30561c5SVitaly Wool 402d30561c5SVitaly Wool page = virt_to_page(zhdr); 403d30561c5SVitaly Wool if (locked) 404d30561c5SVitaly Wool WARN_ON(z3fold_page_trylock(zhdr)); 405d30561c5SVitaly Wool else 406d30561c5SVitaly Wool z3fold_page_lock(zhdr); 407d30561c5SVitaly Wool if (test_bit(PAGE_STALE, &page->private) || 408d30561c5SVitaly Wool !test_and_clear_bit(NEEDS_COMPACTING, &page->private)) { 409d30561c5SVitaly Wool z3fold_page_unlock(zhdr); 410d30561c5SVitaly Wool return; 411d30561c5SVitaly Wool } 412d30561c5SVitaly Wool spin_lock(&pool->lock); 413d30561c5SVitaly Wool list_del_init(&zhdr->buddy); 414d30561c5SVitaly Wool spin_unlock(&pool->lock); 415d30561c5SVitaly Wool 416d30561c5SVitaly Wool z3fold_compact_page(zhdr); 417d30561c5SVitaly Wool unbuddied = get_cpu_ptr(pool->unbuddied); 418d30561c5SVitaly Wool fchunks = num_free_chunks(zhdr); 419d30561c5SVitaly Wool if (fchunks < NCHUNKS && 420d30561c5SVitaly Wool (!zhdr->first_chunks || !zhdr->middle_chunks || 421d30561c5SVitaly Wool !zhdr->last_chunks)) { 422d30561c5SVitaly Wool /* the page's not completely free and it's unbuddied */ 423d30561c5SVitaly Wool spin_lock(&pool->lock); 424d30561c5SVitaly Wool list_add(&zhdr->buddy, &unbuddied[fchunks]); 425d30561c5SVitaly Wool spin_unlock(&pool->lock); 426d30561c5SVitaly Wool zhdr->cpu = smp_processor_id(); 427d30561c5SVitaly Wool } 428d30561c5SVitaly Wool put_cpu_ptr(pool->unbuddied); 429d30561c5SVitaly Wool z3fold_page_unlock(zhdr); 430d30561c5SVitaly Wool } 431d30561c5SVitaly Wool 432d30561c5SVitaly Wool static void compact_page_work(struct work_struct *w) 433d30561c5SVitaly Wool { 434d30561c5SVitaly Wool struct z3fold_header *zhdr = container_of(w, struct z3fold_header, 435d30561c5SVitaly Wool work); 436d30561c5SVitaly Wool 437d30561c5SVitaly Wool do_compact_page(zhdr, false); 438d30561c5SVitaly Wool } 439d30561c5SVitaly Wool 440d30561c5SVitaly Wool 441d30561c5SVitaly Wool /* 442d30561c5SVitaly Wool * API Functions 443d30561c5SVitaly Wool */ 444d30561c5SVitaly Wool 445d30561c5SVitaly Wool /** 446d30561c5SVitaly Wool * z3fold_create_pool() - create a new z3fold pool 447d30561c5SVitaly Wool * @name: pool name 448d30561c5SVitaly Wool * @gfp: gfp flags when allocating the z3fold pool structure 449d30561c5SVitaly Wool * @ops: user-defined operations for the z3fold pool 450d30561c5SVitaly Wool * 451d30561c5SVitaly Wool * Return: pointer to the new z3fold pool or NULL if the metadata allocation 452d30561c5SVitaly Wool * failed. 453d30561c5SVitaly Wool */ 454d30561c5SVitaly Wool static struct z3fold_pool *z3fold_create_pool(const char *name, gfp_t gfp, 455d30561c5SVitaly Wool const struct z3fold_ops *ops) 456d30561c5SVitaly Wool { 457d30561c5SVitaly Wool struct z3fold_pool *pool = NULL; 458d30561c5SVitaly Wool int i, cpu; 459d30561c5SVitaly Wool 460d30561c5SVitaly Wool pool = kzalloc(sizeof(struct z3fold_pool), gfp); 461d30561c5SVitaly Wool if (!pool) 462d30561c5SVitaly Wool goto out; 463d30561c5SVitaly Wool spin_lock_init(&pool->lock); 464d30561c5SVitaly Wool spin_lock_init(&pool->stale_lock); 465d30561c5SVitaly Wool pool->unbuddied = __alloc_percpu(sizeof(struct list_head)*NCHUNKS, 2); 466d30561c5SVitaly Wool for_each_possible_cpu(cpu) { 467d30561c5SVitaly Wool struct list_head *unbuddied = 468d30561c5SVitaly Wool per_cpu_ptr(pool->unbuddied, cpu); 469d30561c5SVitaly Wool for_each_unbuddied_list(i, 0) 470d30561c5SVitaly Wool INIT_LIST_HEAD(&unbuddied[i]); 471d30561c5SVitaly Wool } 472d30561c5SVitaly Wool INIT_LIST_HEAD(&pool->lru); 473d30561c5SVitaly Wool INIT_LIST_HEAD(&pool->stale); 474d30561c5SVitaly Wool atomic64_set(&pool->pages_nr, 0); 475d30561c5SVitaly Wool pool->name = name; 476d30561c5SVitaly Wool pool->compact_wq = create_singlethread_workqueue(pool->name); 477d30561c5SVitaly Wool if (!pool->compact_wq) 478d30561c5SVitaly Wool goto out; 479d30561c5SVitaly Wool pool->release_wq = create_singlethread_workqueue(pool->name); 480d30561c5SVitaly Wool if (!pool->release_wq) 481d30561c5SVitaly Wool goto out_wq; 482d30561c5SVitaly Wool INIT_WORK(&pool->work, free_pages_work); 483d30561c5SVitaly Wool pool->ops = ops; 484d30561c5SVitaly Wool return pool; 485d30561c5SVitaly Wool 486d30561c5SVitaly Wool out_wq: 487d30561c5SVitaly Wool destroy_workqueue(pool->compact_wq); 488d30561c5SVitaly Wool out: 489d30561c5SVitaly Wool kfree(pool); 490d30561c5SVitaly Wool return NULL; 491d30561c5SVitaly Wool } 492d30561c5SVitaly Wool 493d30561c5SVitaly Wool /** 494d30561c5SVitaly Wool * z3fold_destroy_pool() - destroys an existing z3fold pool 495d30561c5SVitaly Wool * @pool: the z3fold pool to be destroyed 496d30561c5SVitaly Wool * 497d30561c5SVitaly Wool * The pool should be emptied before this function is called. 498d30561c5SVitaly Wool */ 499d30561c5SVitaly Wool static void z3fold_destroy_pool(struct z3fold_pool *pool) 500d30561c5SVitaly Wool { 501d30561c5SVitaly Wool destroy_workqueue(pool->release_wq); 502d30561c5SVitaly Wool destroy_workqueue(pool->compact_wq); 503d30561c5SVitaly Wool kfree(pool); 504d30561c5SVitaly Wool } 505d30561c5SVitaly Wool 5069a001fc1SVitaly Wool /** 5079a001fc1SVitaly Wool * z3fold_alloc() - allocates a region of a given size 5089a001fc1SVitaly Wool * @pool: z3fold pool from which to allocate 5099a001fc1SVitaly Wool * @size: size in bytes of the desired allocation 5109a001fc1SVitaly Wool * @gfp: gfp flags used if the pool needs to grow 5119a001fc1SVitaly Wool * @handle: handle of the new allocation 5129a001fc1SVitaly Wool * 5139a001fc1SVitaly Wool * This function will attempt to find a free region in the pool large enough to 5149a001fc1SVitaly Wool * satisfy the allocation request. A search of the unbuddied lists is 5159a001fc1SVitaly Wool * performed first. If no suitable free region is found, then a new page is 5169a001fc1SVitaly Wool * allocated and added to the pool to satisfy the request. 5179a001fc1SVitaly Wool * 5189a001fc1SVitaly Wool * gfp should not set __GFP_HIGHMEM as highmem pages cannot be used 5199a001fc1SVitaly Wool * as z3fold pool pages. 5209a001fc1SVitaly Wool * 5219a001fc1SVitaly Wool * Return: 0 if success and handle is set, otherwise -EINVAL if the size or 5229a001fc1SVitaly Wool * gfp arguments are invalid or -ENOMEM if the pool was unable to allocate 5239a001fc1SVitaly Wool * a new page. 5249a001fc1SVitaly Wool */ 5259a001fc1SVitaly Wool static int z3fold_alloc(struct z3fold_pool *pool, size_t size, gfp_t gfp, 5269a001fc1SVitaly Wool unsigned long *handle) 5279a001fc1SVitaly Wool { 5289a001fc1SVitaly Wool int chunks = 0, i, freechunks; 5299a001fc1SVitaly Wool struct z3fold_header *zhdr = NULL; 530d30561c5SVitaly Wool struct page *page = NULL; 5319a001fc1SVitaly Wool enum buddy bud; 532d30561c5SVitaly Wool bool can_sleep = (gfp & __GFP_RECLAIM) == __GFP_RECLAIM; 5339a001fc1SVitaly Wool 5349a001fc1SVitaly Wool if (!size || (gfp & __GFP_HIGHMEM)) 5359a001fc1SVitaly Wool return -EINVAL; 5369a001fc1SVitaly Wool 5379a001fc1SVitaly Wool if (size > PAGE_SIZE) 5389a001fc1SVitaly Wool return -ENOSPC; 5399a001fc1SVitaly Wool 5409a001fc1SVitaly Wool if (size > PAGE_SIZE - ZHDR_SIZE_ALIGNED - CHUNK_SIZE) 5419a001fc1SVitaly Wool bud = HEADLESS; 5429a001fc1SVitaly Wool else { 543d30561c5SVitaly Wool struct list_head *unbuddied; 5449a001fc1SVitaly Wool chunks = size_to_chunks(size); 5459a001fc1SVitaly Wool 546d30561c5SVitaly Wool lookup: 5479a001fc1SVitaly Wool /* First, try to find an unbuddied z3fold page. */ 548d30561c5SVitaly Wool unbuddied = get_cpu_ptr(pool->unbuddied); 5499a001fc1SVitaly Wool for_each_unbuddied_list(i, chunks) { 550d30561c5SVitaly Wool struct list_head *l = &unbuddied[i]; 551d30561c5SVitaly Wool 552d30561c5SVitaly Wool zhdr = list_first_entry_or_null(READ_ONCE(l), 5539a001fc1SVitaly Wool struct z3fold_header, buddy); 554d30561c5SVitaly Wool 555d30561c5SVitaly Wool if (!zhdr) 5562f1e5e4dSVitaly Wool continue; 557d30561c5SVitaly Wool 558d30561c5SVitaly Wool /* Re-check under lock. */ 559d30561c5SVitaly Wool spin_lock(&pool->lock); 560d30561c5SVitaly Wool l = &unbuddied[i]; 561d30561c5SVitaly Wool if (unlikely(zhdr != list_first_entry(READ_ONCE(l), 562d30561c5SVitaly Wool struct z3fold_header, buddy)) || 563d30561c5SVitaly Wool !z3fold_page_trylock(zhdr)) { 564d30561c5SVitaly Wool spin_unlock(&pool->lock); 565d30561c5SVitaly Wool put_cpu_ptr(pool->unbuddied); 566d30561c5SVitaly Wool goto lookup; 5672f1e5e4dSVitaly Wool } 5682f1e5e4dSVitaly Wool list_del_init(&zhdr->buddy); 569d30561c5SVitaly Wool zhdr->cpu = -1; 5702f1e5e4dSVitaly Wool spin_unlock(&pool->lock); 5712f1e5e4dSVitaly Wool 5729a001fc1SVitaly Wool page = virt_to_page(zhdr); 573d30561c5SVitaly Wool if (test_bit(NEEDS_COMPACTING, &page->private)) { 574d30561c5SVitaly Wool z3fold_page_unlock(zhdr); 575d30561c5SVitaly Wool zhdr = NULL; 576d30561c5SVitaly Wool put_cpu_ptr(pool->unbuddied); 577d30561c5SVitaly Wool if (can_sleep) 578d30561c5SVitaly Wool cond_resched(); 579d30561c5SVitaly Wool goto lookup; 580d30561c5SVitaly Wool } 581d30561c5SVitaly Wool 582d30561c5SVitaly Wool /* 583d30561c5SVitaly Wool * this page could not be removed from its unbuddied 584d30561c5SVitaly Wool * list while pool lock was held, and then we've taken 585d30561c5SVitaly Wool * page lock so kref_put could not be called before 586d30561c5SVitaly Wool * we got here, so it's safe to just call kref_get() 587d30561c5SVitaly Wool */ 588d30561c5SVitaly Wool kref_get(&zhdr->refcount); 589d30561c5SVitaly Wool break; 590d30561c5SVitaly Wool } 591d30561c5SVitaly Wool put_cpu_ptr(pool->unbuddied); 592d30561c5SVitaly Wool 593d30561c5SVitaly Wool if (zhdr) { 5949a001fc1SVitaly Wool if (zhdr->first_chunks == 0) { 5959a001fc1SVitaly Wool if (zhdr->middle_chunks != 0 && 5969a001fc1SVitaly Wool chunks >= zhdr->start_middle) 5979a001fc1SVitaly Wool bud = LAST; 5989a001fc1SVitaly Wool else 5999a001fc1SVitaly Wool bud = FIRST; 6009a001fc1SVitaly Wool } else if (zhdr->last_chunks == 0) 6019a001fc1SVitaly Wool bud = LAST; 6029a001fc1SVitaly Wool else if (zhdr->middle_chunks == 0) 6039a001fc1SVitaly Wool bud = MIDDLE; 6049a001fc1SVitaly Wool else { 6055a27aa82SVitaly Wool if (kref_put(&zhdr->refcount, 606d30561c5SVitaly Wool release_z3fold_page_locked)) 6075a27aa82SVitaly Wool atomic64_dec(&pool->pages_nr); 608d30561c5SVitaly Wool else 609d30561c5SVitaly Wool z3fold_page_unlock(zhdr); 6109a001fc1SVitaly Wool pr_err("No free chunks in unbuddied\n"); 6119a001fc1SVitaly Wool WARN_ON(1); 612d30561c5SVitaly Wool goto lookup; 6139a001fc1SVitaly Wool } 6149a001fc1SVitaly Wool goto found; 6159a001fc1SVitaly Wool } 6169a001fc1SVitaly Wool bud = FIRST; 6179a001fc1SVitaly Wool } 6189a001fc1SVitaly Wool 619d30561c5SVitaly Wool spin_lock(&pool->stale_lock); 620d30561c5SVitaly Wool zhdr = list_first_entry_or_null(&pool->stale, 621d30561c5SVitaly Wool struct z3fold_header, buddy); 622d30561c5SVitaly Wool /* 623d30561c5SVitaly Wool * Before allocating a page, let's see if we can take one from the 624d30561c5SVitaly Wool * stale pages list. cancel_work_sync() can sleep so we must make 625d30561c5SVitaly Wool * sure it won't be called in case we're in atomic context. 626d30561c5SVitaly Wool */ 627*35529357SVitaly Wool if (zhdr && (can_sleep || !work_pending(&zhdr->work))) { 628d30561c5SVitaly Wool list_del(&zhdr->buddy); 629d30561c5SVitaly Wool spin_unlock(&pool->stale_lock); 630d30561c5SVitaly Wool if (can_sleep) 631d30561c5SVitaly Wool cancel_work_sync(&zhdr->work); 632d30561c5SVitaly Wool page = virt_to_page(zhdr); 633d30561c5SVitaly Wool } else { 634d30561c5SVitaly Wool spin_unlock(&pool->stale_lock); 6359a001fc1SVitaly Wool page = alloc_page(gfp); 636d30561c5SVitaly Wool } 637d30561c5SVitaly Wool 6389a001fc1SVitaly Wool if (!page) 6399a001fc1SVitaly Wool return -ENOMEM; 6402f1e5e4dSVitaly Wool 64112d59ae6SVitaly Wool atomic64_inc(&pool->pages_nr); 642d30561c5SVitaly Wool zhdr = init_z3fold_page(page, pool); 6439a001fc1SVitaly Wool 6449a001fc1SVitaly Wool if (bud == HEADLESS) { 6459a001fc1SVitaly Wool set_bit(PAGE_HEADLESS, &page->private); 6469a001fc1SVitaly Wool goto headless; 6479a001fc1SVitaly Wool } 6482f1e5e4dSVitaly Wool z3fold_page_lock(zhdr); 6499a001fc1SVitaly Wool 6509a001fc1SVitaly Wool found: 6519a001fc1SVitaly Wool if (bud == FIRST) 6529a001fc1SVitaly Wool zhdr->first_chunks = chunks; 6539a001fc1SVitaly Wool else if (bud == LAST) 6549a001fc1SVitaly Wool zhdr->last_chunks = chunks; 6559a001fc1SVitaly Wool else { 6569a001fc1SVitaly Wool zhdr->middle_chunks = chunks; 657ede93213SVitaly Wool zhdr->start_middle = zhdr->first_chunks + ZHDR_CHUNKS; 6589a001fc1SVitaly Wool } 6599a001fc1SVitaly Wool 6609a001fc1SVitaly Wool if (zhdr->first_chunks == 0 || zhdr->last_chunks == 0 || 6619a001fc1SVitaly Wool zhdr->middle_chunks == 0) { 662d30561c5SVitaly Wool struct list_head *unbuddied = get_cpu_ptr(pool->unbuddied); 663d30561c5SVitaly Wool 6649a001fc1SVitaly Wool /* Add to unbuddied list */ 6659a001fc1SVitaly Wool freechunks = num_free_chunks(zhdr); 666d30561c5SVitaly Wool spin_lock(&pool->lock); 667d30561c5SVitaly Wool list_add(&zhdr->buddy, &unbuddied[freechunks]); 668d30561c5SVitaly Wool spin_unlock(&pool->lock); 669d30561c5SVitaly Wool zhdr->cpu = smp_processor_id(); 670d30561c5SVitaly Wool put_cpu_ptr(pool->unbuddied); 6719a001fc1SVitaly Wool } 6729a001fc1SVitaly Wool 6739a001fc1SVitaly Wool headless: 674d30561c5SVitaly Wool spin_lock(&pool->lock); 6759a001fc1SVitaly Wool /* Add/move z3fold page to beginning of LRU */ 6769a001fc1SVitaly Wool if (!list_empty(&page->lru)) 6779a001fc1SVitaly Wool list_del(&page->lru); 6789a001fc1SVitaly Wool 6799a001fc1SVitaly Wool list_add(&page->lru, &pool->lru); 6809a001fc1SVitaly Wool 6819a001fc1SVitaly Wool *handle = encode_handle(zhdr, bud); 6829a001fc1SVitaly Wool spin_unlock(&pool->lock); 6832f1e5e4dSVitaly Wool if (bud != HEADLESS) 6842f1e5e4dSVitaly Wool z3fold_page_unlock(zhdr); 6859a001fc1SVitaly Wool 6869a001fc1SVitaly Wool return 0; 6879a001fc1SVitaly Wool } 6889a001fc1SVitaly Wool 6899a001fc1SVitaly Wool /** 6909a001fc1SVitaly Wool * z3fold_free() - frees the allocation associated with the given handle 6919a001fc1SVitaly Wool * @pool: pool in which the allocation resided 6929a001fc1SVitaly Wool * @handle: handle associated with the allocation returned by z3fold_alloc() 6939a001fc1SVitaly Wool * 6949a001fc1SVitaly Wool * In the case that the z3fold page in which the allocation resides is under 6959a001fc1SVitaly Wool * reclaim, as indicated by the PG_reclaim flag being set, this function 6969a001fc1SVitaly Wool * only sets the first|last_chunks to 0. The page is actually freed 6979a001fc1SVitaly Wool * once both buddies are evicted (see z3fold_reclaim_page() below). 6989a001fc1SVitaly Wool */ 6999a001fc1SVitaly Wool static void z3fold_free(struct z3fold_pool *pool, unsigned long handle) 7009a001fc1SVitaly Wool { 7019a001fc1SVitaly Wool struct z3fold_header *zhdr; 7029a001fc1SVitaly Wool struct page *page; 7039a001fc1SVitaly Wool enum buddy bud; 7049a001fc1SVitaly Wool 7059a001fc1SVitaly Wool zhdr = handle_to_z3fold_header(handle); 7069a001fc1SVitaly Wool page = virt_to_page(zhdr); 7079a001fc1SVitaly Wool 7089a001fc1SVitaly Wool if (test_bit(PAGE_HEADLESS, &page->private)) { 7099a001fc1SVitaly Wool /* HEADLESS page stored */ 7109a001fc1SVitaly Wool bud = HEADLESS; 7119a001fc1SVitaly Wool } else { 7122f1e5e4dSVitaly Wool z3fold_page_lock(zhdr); 71343afc194SVitaly Wool bud = handle_to_buddy(handle); 7149a001fc1SVitaly Wool 7159a001fc1SVitaly Wool switch (bud) { 7169a001fc1SVitaly Wool case FIRST: 7179a001fc1SVitaly Wool zhdr->first_chunks = 0; 7189a001fc1SVitaly Wool break; 7199a001fc1SVitaly Wool case MIDDLE: 7209a001fc1SVitaly Wool zhdr->middle_chunks = 0; 7219a001fc1SVitaly Wool zhdr->start_middle = 0; 7229a001fc1SVitaly Wool break; 7239a001fc1SVitaly Wool case LAST: 7249a001fc1SVitaly Wool zhdr->last_chunks = 0; 7259a001fc1SVitaly Wool break; 7269a001fc1SVitaly Wool default: 7279a001fc1SVitaly Wool pr_err("%s: unknown bud %d\n", __func__, bud); 7289a001fc1SVitaly Wool WARN_ON(1); 7292f1e5e4dSVitaly Wool z3fold_page_unlock(zhdr); 7309a001fc1SVitaly Wool return; 7319a001fc1SVitaly Wool } 7329a001fc1SVitaly Wool } 7339a001fc1SVitaly Wool 7345a27aa82SVitaly Wool if (bud == HEADLESS) { 7352f1e5e4dSVitaly Wool spin_lock(&pool->lock); 7369a001fc1SVitaly Wool list_del(&page->lru); 7372f1e5e4dSVitaly Wool spin_unlock(&pool->lock); 7385a27aa82SVitaly Wool free_z3fold_page(page); 73912d59ae6SVitaly Wool atomic64_dec(&pool->pages_nr); 740d30561c5SVitaly Wool return; 7419a001fc1SVitaly Wool } 7429a001fc1SVitaly Wool 743d30561c5SVitaly Wool if (kref_put(&zhdr->refcount, release_z3fold_page_locked_list)) { 744d30561c5SVitaly Wool atomic64_dec(&pool->pages_nr); 745d30561c5SVitaly Wool return; 746d30561c5SVitaly Wool } 747d30561c5SVitaly Wool if (test_and_set_bit(NEEDS_COMPACTING, &page->private)) { 748d30561c5SVitaly Wool z3fold_page_unlock(zhdr); 749d30561c5SVitaly Wool return; 750d30561c5SVitaly Wool } 751d30561c5SVitaly Wool if (zhdr->cpu < 0 || !cpu_online(zhdr->cpu)) { 752d30561c5SVitaly Wool spin_lock(&pool->lock); 753d30561c5SVitaly Wool list_del_init(&zhdr->buddy); 754d30561c5SVitaly Wool spin_unlock(&pool->lock); 755d30561c5SVitaly Wool zhdr->cpu = -1; 756d30561c5SVitaly Wool do_compact_page(zhdr, true); 757d30561c5SVitaly Wool return; 758d30561c5SVitaly Wool } 759d30561c5SVitaly Wool queue_work_on(zhdr->cpu, pool->compact_wq, &zhdr->work); 760d30561c5SVitaly Wool z3fold_page_unlock(zhdr); 7619a001fc1SVitaly Wool } 7629a001fc1SVitaly Wool 7639a001fc1SVitaly Wool /** 7649a001fc1SVitaly Wool * z3fold_reclaim_page() - evicts allocations from a pool page and frees it 7659a001fc1SVitaly Wool * @pool: pool from which a page will attempt to be evicted 7669a001fc1SVitaly Wool * @retires: number of pages on the LRU list for which eviction will 7679a001fc1SVitaly Wool * be attempted before failing 7689a001fc1SVitaly Wool * 7699a001fc1SVitaly Wool * z3fold reclaim is different from normal system reclaim in that it is done 7709a001fc1SVitaly Wool * from the bottom, up. This is because only the bottom layer, z3fold, has 7719a001fc1SVitaly Wool * information on how the allocations are organized within each z3fold page. 7729a001fc1SVitaly Wool * This has the potential to create interesting locking situations between 7739a001fc1SVitaly Wool * z3fold and the user, however. 7749a001fc1SVitaly Wool * 7759a001fc1SVitaly Wool * To avoid these, this is how z3fold_reclaim_page() should be called: 7769a001fc1SVitaly Wool 7779a001fc1SVitaly Wool * The user detects a page should be reclaimed and calls z3fold_reclaim_page(). 7789a001fc1SVitaly Wool * z3fold_reclaim_page() will remove a z3fold page from the pool LRU list and 7799a001fc1SVitaly Wool * call the user-defined eviction handler with the pool and handle as 7809a001fc1SVitaly Wool * arguments. 7819a001fc1SVitaly Wool * 7829a001fc1SVitaly Wool * If the handle can not be evicted, the eviction handler should return 7839a001fc1SVitaly Wool * non-zero. z3fold_reclaim_page() will add the z3fold page back to the 7849a001fc1SVitaly Wool * appropriate list and try the next z3fold page on the LRU up to 7859a001fc1SVitaly Wool * a user defined number of retries. 7869a001fc1SVitaly Wool * 7879a001fc1SVitaly Wool * If the handle is successfully evicted, the eviction handler should 7889a001fc1SVitaly Wool * return 0 _and_ should have called z3fold_free() on the handle. z3fold_free() 7899a001fc1SVitaly Wool * contains logic to delay freeing the page if the page is under reclaim, 7909a001fc1SVitaly Wool * as indicated by the setting of the PG_reclaim flag on the underlying page. 7919a001fc1SVitaly Wool * 7929a001fc1SVitaly Wool * If all buddies in the z3fold page are successfully evicted, then the 7939a001fc1SVitaly Wool * z3fold page can be freed. 7949a001fc1SVitaly Wool * 7959a001fc1SVitaly Wool * Returns: 0 if page is successfully freed, otherwise -EINVAL if there are 7969a001fc1SVitaly Wool * no pages to evict or an eviction handler is not registered, -EAGAIN if 7979a001fc1SVitaly Wool * the retry limit was hit. 7989a001fc1SVitaly Wool */ 7999a001fc1SVitaly Wool static int z3fold_reclaim_page(struct z3fold_pool *pool, unsigned int retries) 8009a001fc1SVitaly Wool { 801d30561c5SVitaly Wool int i, ret = 0; 802d30561c5SVitaly Wool struct z3fold_header *zhdr = NULL; 803d30561c5SVitaly Wool struct page *page = NULL; 804d30561c5SVitaly Wool struct list_head *pos; 8059a001fc1SVitaly Wool unsigned long first_handle = 0, middle_handle = 0, last_handle = 0; 8069a001fc1SVitaly Wool 8079a001fc1SVitaly Wool spin_lock(&pool->lock); 8082f1e5e4dSVitaly Wool if (!pool->ops || !pool->ops->evict || retries == 0) { 8099a001fc1SVitaly Wool spin_unlock(&pool->lock); 8109a001fc1SVitaly Wool return -EINVAL; 8119a001fc1SVitaly Wool } 8129a001fc1SVitaly Wool for (i = 0; i < retries; i++) { 8132f1e5e4dSVitaly Wool if (list_empty(&pool->lru)) { 8142f1e5e4dSVitaly Wool spin_unlock(&pool->lock); 8152f1e5e4dSVitaly Wool return -EINVAL; 8162f1e5e4dSVitaly Wool } 817d30561c5SVitaly Wool list_for_each_prev(pos, &pool->lru) { 818d30561c5SVitaly Wool page = list_entry(pos, struct page, lru); 819d30561c5SVitaly Wool if (test_bit(PAGE_HEADLESS, &page->private)) 820d30561c5SVitaly Wool /* candidate found */ 821d30561c5SVitaly Wool break; 8229a001fc1SVitaly Wool 8239a001fc1SVitaly Wool zhdr = page_address(page); 824d30561c5SVitaly Wool if (!z3fold_page_trylock(zhdr)) 825d30561c5SVitaly Wool continue; /* can't evict at this point */ 8265a27aa82SVitaly Wool kref_get(&zhdr->refcount); 827d30561c5SVitaly Wool list_del_init(&zhdr->buddy); 828d30561c5SVitaly Wool zhdr->cpu = -1; 829d30561c5SVitaly Wool } 830d30561c5SVitaly Wool 831d30561c5SVitaly Wool list_del_init(&page->lru); 8322f1e5e4dSVitaly Wool spin_unlock(&pool->lock); 833d30561c5SVitaly Wool 834d30561c5SVitaly Wool if (!test_bit(PAGE_HEADLESS, &page->private)) { 8359a001fc1SVitaly Wool /* 8369a001fc1SVitaly Wool * We need encode the handles before unlocking, since 8379a001fc1SVitaly Wool * we can race with free that will set 8389a001fc1SVitaly Wool * (first|last)_chunks to 0 8399a001fc1SVitaly Wool */ 8409a001fc1SVitaly Wool first_handle = 0; 8419a001fc1SVitaly Wool last_handle = 0; 8429a001fc1SVitaly Wool middle_handle = 0; 8439a001fc1SVitaly Wool if (zhdr->first_chunks) 8449a001fc1SVitaly Wool first_handle = encode_handle(zhdr, FIRST); 8459a001fc1SVitaly Wool if (zhdr->middle_chunks) 8469a001fc1SVitaly Wool middle_handle = encode_handle(zhdr, MIDDLE); 8479a001fc1SVitaly Wool if (zhdr->last_chunks) 8489a001fc1SVitaly Wool last_handle = encode_handle(zhdr, LAST); 849d30561c5SVitaly Wool /* 850d30561c5SVitaly Wool * it's safe to unlock here because we hold a 851d30561c5SVitaly Wool * reference to this page 852d30561c5SVitaly Wool */ 8532f1e5e4dSVitaly Wool z3fold_page_unlock(zhdr); 8549a001fc1SVitaly Wool } else { 8559a001fc1SVitaly Wool first_handle = encode_handle(zhdr, HEADLESS); 8569a001fc1SVitaly Wool last_handle = middle_handle = 0; 8572f1e5e4dSVitaly Wool } 8589a001fc1SVitaly Wool 8599a001fc1SVitaly Wool /* Issue the eviction callback(s) */ 8609a001fc1SVitaly Wool if (middle_handle) { 8619a001fc1SVitaly Wool ret = pool->ops->evict(pool, middle_handle); 8629a001fc1SVitaly Wool if (ret) 8639a001fc1SVitaly Wool goto next; 8649a001fc1SVitaly Wool } 8659a001fc1SVitaly Wool if (first_handle) { 8669a001fc1SVitaly Wool ret = pool->ops->evict(pool, first_handle); 8679a001fc1SVitaly Wool if (ret) 8689a001fc1SVitaly Wool goto next; 8699a001fc1SVitaly Wool } 8709a001fc1SVitaly Wool if (last_handle) { 8719a001fc1SVitaly Wool ret = pool->ops->evict(pool, last_handle); 8729a001fc1SVitaly Wool if (ret) 8739a001fc1SVitaly Wool goto next; 8749a001fc1SVitaly Wool } 8759a001fc1SVitaly Wool next: 876d5567c9dSVitaly Wool spin_lock(&pool->lock); 8775a27aa82SVitaly Wool if (test_bit(PAGE_HEADLESS, &page->private)) { 8785a27aa82SVitaly Wool if (ret == 0) { 879d5567c9dSVitaly Wool spin_unlock(&pool->lock); 8805a27aa82SVitaly Wool free_z3fold_page(page); 8819a001fc1SVitaly Wool return 0; 8825a27aa82SVitaly Wool } 883d30561c5SVitaly Wool } else if (kref_put(&zhdr->refcount, release_z3fold_page)) { 8845a27aa82SVitaly Wool atomic64_dec(&pool->pages_nr); 885d5567c9dSVitaly Wool spin_unlock(&pool->lock); 8865a27aa82SVitaly Wool return 0; 8875a27aa82SVitaly Wool } 8889a001fc1SVitaly Wool 8895a27aa82SVitaly Wool /* 8905a27aa82SVitaly Wool * Add to the beginning of LRU. 8915a27aa82SVitaly Wool * Pool lock has to be kept here to ensure the page has 8925a27aa82SVitaly Wool * not already been released 8935a27aa82SVitaly Wool */ 8949a001fc1SVitaly Wool list_add(&page->lru, &pool->lru); 8959a001fc1SVitaly Wool } 8969a001fc1SVitaly Wool spin_unlock(&pool->lock); 8979a001fc1SVitaly Wool return -EAGAIN; 8989a001fc1SVitaly Wool } 8999a001fc1SVitaly Wool 9009a001fc1SVitaly Wool /** 9019a001fc1SVitaly Wool * z3fold_map() - maps the allocation associated with the given handle 9029a001fc1SVitaly Wool * @pool: pool in which the allocation resides 9039a001fc1SVitaly Wool * @handle: handle associated with the allocation to be mapped 9049a001fc1SVitaly Wool * 9059a001fc1SVitaly Wool * Extracts the buddy number from handle and constructs the pointer to the 9069a001fc1SVitaly Wool * correct starting chunk within the page. 9079a001fc1SVitaly Wool * 9089a001fc1SVitaly Wool * Returns: a pointer to the mapped allocation 9099a001fc1SVitaly Wool */ 9109a001fc1SVitaly Wool static void *z3fold_map(struct z3fold_pool *pool, unsigned long handle) 9119a001fc1SVitaly Wool { 9129a001fc1SVitaly Wool struct z3fold_header *zhdr; 9139a001fc1SVitaly Wool struct page *page; 9149a001fc1SVitaly Wool void *addr; 9159a001fc1SVitaly Wool enum buddy buddy; 9169a001fc1SVitaly Wool 9179a001fc1SVitaly Wool zhdr = handle_to_z3fold_header(handle); 9189a001fc1SVitaly Wool addr = zhdr; 9199a001fc1SVitaly Wool page = virt_to_page(zhdr); 9209a001fc1SVitaly Wool 9219a001fc1SVitaly Wool if (test_bit(PAGE_HEADLESS, &page->private)) 9229a001fc1SVitaly Wool goto out; 9239a001fc1SVitaly Wool 9242f1e5e4dSVitaly Wool z3fold_page_lock(zhdr); 9259a001fc1SVitaly Wool buddy = handle_to_buddy(handle); 9269a001fc1SVitaly Wool switch (buddy) { 9279a001fc1SVitaly Wool case FIRST: 9289a001fc1SVitaly Wool addr += ZHDR_SIZE_ALIGNED; 9299a001fc1SVitaly Wool break; 9309a001fc1SVitaly Wool case MIDDLE: 9319a001fc1SVitaly Wool addr += zhdr->start_middle << CHUNK_SHIFT; 9329a001fc1SVitaly Wool set_bit(MIDDLE_CHUNK_MAPPED, &page->private); 9339a001fc1SVitaly Wool break; 9349a001fc1SVitaly Wool case LAST: 9359a001fc1SVitaly Wool addr += PAGE_SIZE - (zhdr->last_chunks << CHUNK_SHIFT); 9369a001fc1SVitaly Wool break; 9379a001fc1SVitaly Wool default: 9389a001fc1SVitaly Wool pr_err("unknown buddy id %d\n", buddy); 9399a001fc1SVitaly Wool WARN_ON(1); 9409a001fc1SVitaly Wool addr = NULL; 9419a001fc1SVitaly Wool break; 9429a001fc1SVitaly Wool } 9432f1e5e4dSVitaly Wool 9442f1e5e4dSVitaly Wool z3fold_page_unlock(zhdr); 9459a001fc1SVitaly Wool out: 9469a001fc1SVitaly Wool return addr; 9479a001fc1SVitaly Wool } 9489a001fc1SVitaly Wool 9499a001fc1SVitaly Wool /** 9509a001fc1SVitaly Wool * z3fold_unmap() - unmaps the allocation associated with the given handle 9519a001fc1SVitaly Wool * @pool: pool in which the allocation resides 9529a001fc1SVitaly Wool * @handle: handle associated with the allocation to be unmapped 9539a001fc1SVitaly Wool */ 9549a001fc1SVitaly Wool static void z3fold_unmap(struct z3fold_pool *pool, unsigned long handle) 9559a001fc1SVitaly Wool { 9569a001fc1SVitaly Wool struct z3fold_header *zhdr; 9579a001fc1SVitaly Wool struct page *page; 9589a001fc1SVitaly Wool enum buddy buddy; 9599a001fc1SVitaly Wool 9609a001fc1SVitaly Wool zhdr = handle_to_z3fold_header(handle); 9619a001fc1SVitaly Wool page = virt_to_page(zhdr); 9629a001fc1SVitaly Wool 9632f1e5e4dSVitaly Wool if (test_bit(PAGE_HEADLESS, &page->private)) 9649a001fc1SVitaly Wool return; 9659a001fc1SVitaly Wool 9662f1e5e4dSVitaly Wool z3fold_page_lock(zhdr); 9679a001fc1SVitaly Wool buddy = handle_to_buddy(handle); 9689a001fc1SVitaly Wool if (buddy == MIDDLE) 9699a001fc1SVitaly Wool clear_bit(MIDDLE_CHUNK_MAPPED, &page->private); 9702f1e5e4dSVitaly Wool z3fold_page_unlock(zhdr); 9719a001fc1SVitaly Wool } 9729a001fc1SVitaly Wool 9739a001fc1SVitaly Wool /** 9749a001fc1SVitaly Wool * z3fold_get_pool_size() - gets the z3fold pool size in pages 9759a001fc1SVitaly Wool * @pool: pool whose size is being queried 9769a001fc1SVitaly Wool * 97712d59ae6SVitaly Wool * Returns: size in pages of the given pool. 9789a001fc1SVitaly Wool */ 9799a001fc1SVitaly Wool static u64 z3fold_get_pool_size(struct z3fold_pool *pool) 9809a001fc1SVitaly Wool { 98112d59ae6SVitaly Wool return atomic64_read(&pool->pages_nr); 9829a001fc1SVitaly Wool } 9839a001fc1SVitaly Wool 9849a001fc1SVitaly Wool /***************** 9859a001fc1SVitaly Wool * zpool 9869a001fc1SVitaly Wool ****************/ 9879a001fc1SVitaly Wool 9889a001fc1SVitaly Wool static int z3fold_zpool_evict(struct z3fold_pool *pool, unsigned long handle) 9899a001fc1SVitaly Wool { 9909a001fc1SVitaly Wool if (pool->zpool && pool->zpool_ops && pool->zpool_ops->evict) 9919a001fc1SVitaly Wool return pool->zpool_ops->evict(pool->zpool, handle); 9929a001fc1SVitaly Wool else 9939a001fc1SVitaly Wool return -ENOENT; 9949a001fc1SVitaly Wool } 9959a001fc1SVitaly Wool 9969a001fc1SVitaly Wool static const struct z3fold_ops z3fold_zpool_ops = { 9979a001fc1SVitaly Wool .evict = z3fold_zpool_evict 9989a001fc1SVitaly Wool }; 9999a001fc1SVitaly Wool 10009a001fc1SVitaly Wool static void *z3fold_zpool_create(const char *name, gfp_t gfp, 10019a001fc1SVitaly Wool const struct zpool_ops *zpool_ops, 10029a001fc1SVitaly Wool struct zpool *zpool) 10039a001fc1SVitaly Wool { 10049a001fc1SVitaly Wool struct z3fold_pool *pool; 10059a001fc1SVitaly Wool 1006d30561c5SVitaly Wool pool = z3fold_create_pool(name, gfp, 1007d30561c5SVitaly Wool zpool_ops ? &z3fold_zpool_ops : NULL); 10089a001fc1SVitaly Wool if (pool) { 10099a001fc1SVitaly Wool pool->zpool = zpool; 10109a001fc1SVitaly Wool pool->zpool_ops = zpool_ops; 10119a001fc1SVitaly Wool } 10129a001fc1SVitaly Wool return pool; 10139a001fc1SVitaly Wool } 10149a001fc1SVitaly Wool 10159a001fc1SVitaly Wool static void z3fold_zpool_destroy(void *pool) 10169a001fc1SVitaly Wool { 10179a001fc1SVitaly Wool z3fold_destroy_pool(pool); 10189a001fc1SVitaly Wool } 10199a001fc1SVitaly Wool 10209a001fc1SVitaly Wool static int z3fold_zpool_malloc(void *pool, size_t size, gfp_t gfp, 10219a001fc1SVitaly Wool unsigned long *handle) 10229a001fc1SVitaly Wool { 10239a001fc1SVitaly Wool return z3fold_alloc(pool, size, gfp, handle); 10249a001fc1SVitaly Wool } 10259a001fc1SVitaly Wool static void z3fold_zpool_free(void *pool, unsigned long handle) 10269a001fc1SVitaly Wool { 10279a001fc1SVitaly Wool z3fold_free(pool, handle); 10289a001fc1SVitaly Wool } 10299a001fc1SVitaly Wool 10309a001fc1SVitaly Wool static int z3fold_zpool_shrink(void *pool, unsigned int pages, 10319a001fc1SVitaly Wool unsigned int *reclaimed) 10329a001fc1SVitaly Wool { 10339a001fc1SVitaly Wool unsigned int total = 0; 10349a001fc1SVitaly Wool int ret = -EINVAL; 10359a001fc1SVitaly Wool 10369a001fc1SVitaly Wool while (total < pages) { 10379a001fc1SVitaly Wool ret = z3fold_reclaim_page(pool, 8); 10389a001fc1SVitaly Wool if (ret < 0) 10399a001fc1SVitaly Wool break; 10409a001fc1SVitaly Wool total++; 10419a001fc1SVitaly Wool } 10429a001fc1SVitaly Wool 10439a001fc1SVitaly Wool if (reclaimed) 10449a001fc1SVitaly Wool *reclaimed = total; 10459a001fc1SVitaly Wool 10469a001fc1SVitaly Wool return ret; 10479a001fc1SVitaly Wool } 10489a001fc1SVitaly Wool 10499a001fc1SVitaly Wool static void *z3fold_zpool_map(void *pool, unsigned long handle, 10509a001fc1SVitaly Wool enum zpool_mapmode mm) 10519a001fc1SVitaly Wool { 10529a001fc1SVitaly Wool return z3fold_map(pool, handle); 10539a001fc1SVitaly Wool } 10549a001fc1SVitaly Wool static void z3fold_zpool_unmap(void *pool, unsigned long handle) 10559a001fc1SVitaly Wool { 10569a001fc1SVitaly Wool z3fold_unmap(pool, handle); 10579a001fc1SVitaly Wool } 10589a001fc1SVitaly Wool 10599a001fc1SVitaly Wool static u64 z3fold_zpool_total_size(void *pool) 10609a001fc1SVitaly Wool { 10619a001fc1SVitaly Wool return z3fold_get_pool_size(pool) * PAGE_SIZE; 10629a001fc1SVitaly Wool } 10639a001fc1SVitaly Wool 10649a001fc1SVitaly Wool static struct zpool_driver z3fold_zpool_driver = { 10659a001fc1SVitaly Wool .type = "z3fold", 10669a001fc1SVitaly Wool .owner = THIS_MODULE, 10679a001fc1SVitaly Wool .create = z3fold_zpool_create, 10689a001fc1SVitaly Wool .destroy = z3fold_zpool_destroy, 10699a001fc1SVitaly Wool .malloc = z3fold_zpool_malloc, 10709a001fc1SVitaly Wool .free = z3fold_zpool_free, 10719a001fc1SVitaly Wool .shrink = z3fold_zpool_shrink, 10729a001fc1SVitaly Wool .map = z3fold_zpool_map, 10739a001fc1SVitaly Wool .unmap = z3fold_zpool_unmap, 10749a001fc1SVitaly Wool .total_size = z3fold_zpool_total_size, 10759a001fc1SVitaly Wool }; 10769a001fc1SVitaly Wool 10779a001fc1SVitaly Wool MODULE_ALIAS("zpool-z3fold"); 10789a001fc1SVitaly Wool 10799a001fc1SVitaly Wool static int __init init_z3fold(void) 10809a001fc1SVitaly Wool { 1081ede93213SVitaly Wool /* Make sure the z3fold header is not larger than the page size */ 1082ede93213SVitaly Wool BUILD_BUG_ON(ZHDR_SIZE_ALIGNED > PAGE_SIZE); 10839a001fc1SVitaly Wool zpool_register_driver(&z3fold_zpool_driver); 10849a001fc1SVitaly Wool 10859a001fc1SVitaly Wool return 0; 10869a001fc1SVitaly Wool } 10879a001fc1SVitaly Wool 10889a001fc1SVitaly Wool static void __exit exit_z3fold(void) 10899a001fc1SVitaly Wool { 10909a001fc1SVitaly Wool zpool_unregister_driver(&z3fold_zpool_driver); 10919a001fc1SVitaly Wool } 10929a001fc1SVitaly Wool 10939a001fc1SVitaly Wool module_init(init_z3fold); 10949a001fc1SVitaly Wool module_exit(exit_z3fold); 10959a001fc1SVitaly Wool 10969a001fc1SVitaly Wool MODULE_LICENSE("GPL"); 10979a001fc1SVitaly Wool MODULE_AUTHOR("Vitaly Wool <vitalywool@gmail.com>"); 10989a001fc1SVitaly Wool MODULE_DESCRIPTION("3-Fold Allocator for Compressed Pages"); 1099