blob: be8b56e21c2d97c007f328c0846ebdeaa7c489d1 [file] [log] [blame]
Vitaly Wool9a001fc2016-05-20 16:58:30 -07001/*
2 * z3fold.c
3 *
4 * Author: Vitaly Wool <vitaly.wool@konsulko.com>
5 * Copyright (C) 2016, Sony Mobile Communications Inc.
6 *
7 * This implementation is based on zbud written by Seth Jennings.
8 *
9 * z3fold is an special purpose allocator for storing compressed pages. It
10 * can store up to three compressed pages per page which improves the
11 * compression ratio of zbud while retaining its main concepts (e. g. always
12 * storing an integral number of objects per page) and simplicity.
13 * It still has simple and deterministic reclaim properties that make it
14 * preferable to a higher density approach (with no requirement on integral
15 * number of object per page) when reclaim is used.
16 *
17 * As in zbud, pages are divided into "chunks". The size of the chunks is
18 * fixed at compile time and is determined by NCHUNKS_ORDER below.
19 *
20 * z3fold doesn't export any API and is meant to be used via zpool API.
21 */
22
23#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
24
25#include <linux/atomic.h>
26#include <linux/list.h>
27#include <linux/mm.h>
28#include <linux/module.h>
29#include <linux/preempt.h>
30#include <linux/slab.h>
31#include <linux/spinlock.h>
32#include <linux/zpool.h>
33
34/*****************
35 * Structures
36*****************/
Vitaly Woolede93212017-02-24 14:57:17 -080037struct z3fold_pool;
38struct z3fold_ops {
39 int (*evict)(struct z3fold_pool *pool, unsigned long handle);
40};
41
42enum buddy {
43 HEADLESS = 0,
44 FIRST,
45 MIDDLE,
46 LAST,
47 BUDDIES_MAX
48};
49
50/*
51 * struct z3fold_header - z3fold page metadata occupying the first chunk of each
52 * z3fold page, except for HEADLESS pages
53 * @buddy: links the z3fold page into the relevant list in the pool
54 * @first_chunks: the size of the first buddy in chunks, 0 if free
55 * @middle_chunks: the size of the middle buddy in chunks, 0 if free
56 * @last_chunks: the size of the last buddy in chunks, 0 if free
57 * @first_num: the starting number (for the first handle)
58 */
59struct z3fold_header {
60 struct list_head buddy;
61 unsigned short first_chunks;
62 unsigned short middle_chunks;
63 unsigned short last_chunks;
64 unsigned short start_middle;
65 unsigned short first_num:2;
66};
67
Vitaly Wool9a001fc2016-05-20 16:58:30 -070068/*
69 * NCHUNKS_ORDER determines the internal allocation granularity, effectively
70 * adjusting internal fragmentation. It also determines the number of
71 * freelists maintained in each pool. NCHUNKS_ORDER of 6 means that the
Vitaly Woolede93212017-02-24 14:57:17 -080072 * allocation granularity will be in chunks of size PAGE_SIZE/64. Some chunks
73 * in the beginning of an allocated page are occupied by z3fold header, so
74 * NCHUNKS will be calculated to 63 (or 62 in case CONFIG_DEBUG_SPINLOCK=y),
75 * which shows the max number of free chunks in z3fold page, also there will
76 * be 63, or 62, respectively, freelists per pool.
Vitaly Wool9a001fc2016-05-20 16:58:30 -070077 */
78#define NCHUNKS_ORDER 6
79
80#define CHUNK_SHIFT (PAGE_SHIFT - NCHUNKS_ORDER)
81#define CHUNK_SIZE (1 << CHUNK_SHIFT)
Vitaly Woolede93212017-02-24 14:57:17 -080082#define ZHDR_SIZE_ALIGNED round_up(sizeof(struct z3fold_header), CHUNK_SIZE)
83#define ZHDR_CHUNKS (ZHDR_SIZE_ALIGNED >> CHUNK_SHIFT)
84#define TOTAL_CHUNKS (PAGE_SIZE >> CHUNK_SHIFT)
Vitaly Wool9a001fc2016-05-20 16:58:30 -070085#define NCHUNKS ((PAGE_SIZE - ZHDR_SIZE_ALIGNED) >> CHUNK_SHIFT)
86
zhong jiangf201ebd2017-02-22 15:46:51 -080087#define BUDDY_MASK (0x3)
Vitaly Wool9a001fc2016-05-20 16:58:30 -070088
Vitaly Wool9a001fc2016-05-20 16:58:30 -070089/**
90 * struct z3fold_pool - stores metadata for each z3fold pool
91 * @lock: protects all pool fields and first|last_chunk fields of any
92 * z3fold page in the pool
93 * @unbuddied: array of lists tracking z3fold pages that contain 2- buddies;
94 * the lists each z3fold page is added to depends on the size of
95 * its free region.
96 * @buddied: list tracking the z3fold pages that contain 3 buddies;
97 * these z3fold pages are full
98 * @lru: list tracking the z3fold pages in LRU order by most recently
99 * added buddy.
100 * @pages_nr: number of z3fold pages in the pool.
101 * @ops: pointer to a structure of user defined operations specified at
102 * pool creation time.
103 *
104 * This structure is allocated at pool creation time and maintains metadata
105 * pertaining to a particular z3fold pool.
106 */
107struct z3fold_pool {
108 spinlock_t lock;
109 struct list_head unbuddied[NCHUNKS];
110 struct list_head buddied;
111 struct list_head lru;
Vitaly Wool12d59ae2017-02-24 14:57:15 -0800112 atomic64_t pages_nr;
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700113 const struct z3fold_ops *ops;
114 struct zpool *zpool;
115 const struct zpool_ops *zpool_ops;
116};
117
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700118/*
119 * Internal z3fold page flags
120 */
121enum z3fold_page_flags {
122 UNDER_RECLAIM = 0,
123 PAGE_HEADLESS,
124 MIDDLE_CHUNK_MAPPED,
125};
126
Vitaly Woolede93212017-02-24 14:57:17 -0800127
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700128/*****************
129 * Helpers
130*****************/
131
132/* Converts an allocation size in bytes to size in z3fold chunks */
133static int size_to_chunks(size_t size)
134{
135 return (size + CHUNK_SIZE - 1) >> CHUNK_SHIFT;
136}
137
138#define for_each_unbuddied_list(_iter, _begin) \
139 for ((_iter) = (_begin); (_iter) < NCHUNKS; (_iter)++)
140
141/* Initializes the z3fold header of a newly allocated z3fold page */
142static struct z3fold_header *init_z3fold_page(struct page *page)
143{
144 struct z3fold_header *zhdr = page_address(page);
145
146 INIT_LIST_HEAD(&page->lru);
147 clear_bit(UNDER_RECLAIM, &page->private);
148 clear_bit(PAGE_HEADLESS, &page->private);
149 clear_bit(MIDDLE_CHUNK_MAPPED, &page->private);
150
151 zhdr->first_chunks = 0;
152 zhdr->middle_chunks = 0;
153 zhdr->last_chunks = 0;
154 zhdr->first_num = 0;
155 zhdr->start_middle = 0;
156 INIT_LIST_HEAD(&zhdr->buddy);
157 return zhdr;
158}
159
160/* Resets the struct page fields and frees the page */
161static void free_z3fold_page(struct z3fold_header *zhdr)
162{
163 __free_page(virt_to_page(zhdr));
164}
165
166/*
167 * Encodes the handle of a particular buddy within a z3fold page
168 * Pool lock should be held as this function accesses first_num
169 */
170static unsigned long encode_handle(struct z3fold_header *zhdr, enum buddy bud)
171{
172 unsigned long handle;
173
174 handle = (unsigned long)zhdr;
175 if (bud != HEADLESS)
176 handle += (bud + zhdr->first_num) & BUDDY_MASK;
177 return handle;
178}
179
180/* Returns the z3fold page where a given handle is stored */
181static struct z3fold_header *handle_to_z3fold_header(unsigned long handle)
182{
183 return (struct z3fold_header *)(handle & PAGE_MASK);
184}
185
zhong jiangf201ebd2017-02-22 15:46:51 -0800186/*
187 * (handle & BUDDY_MASK) < zhdr->first_num is possible in encode_handle
188 * but that doesn't matter. because the masking will result in the
189 * correct buddy number.
190 */
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700191static enum buddy handle_to_buddy(unsigned long handle)
192{
193 struct z3fold_header *zhdr = handle_to_z3fold_header(handle);
194 return (handle - zhdr->first_num) & BUDDY_MASK;
195}
196
197/*
198 * Returns the number of free chunks in a z3fold page.
199 * NB: can't be used with HEADLESS pages.
200 */
201static int num_free_chunks(struct z3fold_header *zhdr)
202{
203 int nfree;
204 /*
205 * If there is a middle object, pick up the bigger free space
206 * either before or after it. Otherwise just subtract the number
207 * of chunks occupied by the first and the last objects.
208 */
209 if (zhdr->middle_chunks != 0) {
210 int nfree_before = zhdr->first_chunks ?
Vitaly Woolede93212017-02-24 14:57:17 -0800211 0 : zhdr->start_middle - ZHDR_CHUNKS;
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700212 int nfree_after = zhdr->last_chunks ?
Vitaly Woolede93212017-02-24 14:57:17 -0800213 0 : TOTAL_CHUNKS -
214 (zhdr->start_middle + zhdr->middle_chunks);
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700215 nfree = max(nfree_before, nfree_after);
216 } else
217 nfree = NCHUNKS - zhdr->first_chunks - zhdr->last_chunks;
218 return nfree;
219}
220
221/*****************
222 * API Functions
223*****************/
224/**
225 * z3fold_create_pool() - create a new z3fold pool
226 * @gfp: gfp flags when allocating the z3fold pool structure
227 * @ops: user-defined operations for the z3fold pool
228 *
229 * Return: pointer to the new z3fold pool or NULL if the metadata allocation
230 * failed.
231 */
232static struct z3fold_pool *z3fold_create_pool(gfp_t gfp,
233 const struct z3fold_ops *ops)
234{
235 struct z3fold_pool *pool;
236 int i;
237
238 pool = kzalloc(sizeof(struct z3fold_pool), gfp);
239 if (!pool)
240 return NULL;
241 spin_lock_init(&pool->lock);
242 for_each_unbuddied_list(i, 0)
243 INIT_LIST_HEAD(&pool->unbuddied[i]);
244 INIT_LIST_HEAD(&pool->buddied);
245 INIT_LIST_HEAD(&pool->lru);
Vitaly Wool12d59ae2017-02-24 14:57:15 -0800246 atomic64_set(&pool->pages_nr, 0);
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700247 pool->ops = ops;
248 return pool;
249}
250
251/**
252 * z3fold_destroy_pool() - destroys an existing z3fold pool
253 * @pool: the z3fold pool to be destroyed
254 *
255 * The pool should be emptied before this function is called.
256 */
257static void z3fold_destroy_pool(struct z3fold_pool *pool)
258{
259 kfree(pool);
260}
261
Vitaly Woolede93212017-02-24 14:57:17 -0800262static inline void *mchunk_memmove(struct z3fold_header *zhdr,
263 unsigned short dst_chunk)
264{
265 void *beg = zhdr;
266 return memmove(beg + (dst_chunk << CHUNK_SHIFT),
267 beg + (zhdr->start_middle << CHUNK_SHIFT),
268 zhdr->middle_chunks << CHUNK_SHIFT);
269}
270
Vitaly Wool1b096e52017-02-24 14:57:20 -0800271#define BIG_CHUNK_GAP 3
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700272/* Has to be called with lock held */
273static int z3fold_compact_page(struct z3fold_header *zhdr)
274{
275 struct page *page = virt_to_page(zhdr);
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700276
Vitaly Woolede93212017-02-24 14:57:17 -0800277 if (test_bit(MIDDLE_CHUNK_MAPPED, &page->private))
278 return 0; /* can't move middle chunk, it's used */
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700279
Vitaly Woolede93212017-02-24 14:57:17 -0800280 if (zhdr->middle_chunks == 0)
281 return 0; /* nothing to compact */
282
283 if (zhdr->first_chunks == 0 && zhdr->last_chunks == 0) {
284 /* move to the beginning */
285 mchunk_memmove(zhdr, ZHDR_CHUNKS);
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700286 zhdr->first_chunks = zhdr->middle_chunks;
287 zhdr->middle_chunks = 0;
288 zhdr->start_middle = 0;
289 zhdr->first_num++;
Vitaly Wool1b096e52017-02-24 14:57:20 -0800290 return 1;
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700291 }
Vitaly Wool1b096e52017-02-24 14:57:20 -0800292
293 /*
294 * moving data is expensive, so let's only do that if
295 * there's substantial gain (at least BIG_CHUNK_GAP chunks)
296 */
297 if (zhdr->first_chunks != 0 && zhdr->last_chunks == 0 &&
298 zhdr->start_middle - (zhdr->first_chunks + ZHDR_CHUNKS) >=
299 BIG_CHUNK_GAP) {
300 mchunk_memmove(zhdr, zhdr->first_chunks + ZHDR_CHUNKS);
301 zhdr->start_middle = zhdr->first_chunks + ZHDR_CHUNKS;
302 return 1;
303 } else if (zhdr->last_chunks != 0 && zhdr->first_chunks == 0 &&
304 TOTAL_CHUNKS - (zhdr->last_chunks + zhdr->start_middle
305 + zhdr->middle_chunks) >=
306 BIG_CHUNK_GAP) {
307 unsigned short new_start = TOTAL_CHUNKS - zhdr->last_chunks -
308 zhdr->middle_chunks;
309 mchunk_memmove(zhdr, new_start);
310 zhdr->start_middle = new_start;
311 return 1;
312 }
313
314 return 0;
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700315}
316
317/**
318 * z3fold_alloc() - allocates a region of a given size
319 * @pool: z3fold pool from which to allocate
320 * @size: size in bytes of the desired allocation
321 * @gfp: gfp flags used if the pool needs to grow
322 * @handle: handle of the new allocation
323 *
324 * This function will attempt to find a free region in the pool large enough to
325 * satisfy the allocation request. A search of the unbuddied lists is
326 * performed first. If no suitable free region is found, then a new page is
327 * allocated and added to the pool to satisfy the request.
328 *
329 * gfp should not set __GFP_HIGHMEM as highmem pages cannot be used
330 * as z3fold pool pages.
331 *
332 * Return: 0 if success and handle is set, otherwise -EINVAL if the size or
333 * gfp arguments are invalid or -ENOMEM if the pool was unable to allocate
334 * a new page.
335 */
336static int z3fold_alloc(struct z3fold_pool *pool, size_t size, gfp_t gfp,
337 unsigned long *handle)
338{
339 int chunks = 0, i, freechunks;
340 struct z3fold_header *zhdr = NULL;
341 enum buddy bud;
342 struct page *page;
343
344 if (!size || (gfp & __GFP_HIGHMEM))
345 return -EINVAL;
346
347 if (size > PAGE_SIZE)
348 return -ENOSPC;
349
350 if (size > PAGE_SIZE - ZHDR_SIZE_ALIGNED - CHUNK_SIZE)
351 bud = HEADLESS;
352 else {
353 chunks = size_to_chunks(size);
354 spin_lock(&pool->lock);
355
356 /* First, try to find an unbuddied z3fold page. */
357 zhdr = NULL;
358 for_each_unbuddied_list(i, chunks) {
359 if (!list_empty(&pool->unbuddied[i])) {
360 zhdr = list_first_entry(&pool->unbuddied[i],
361 struct z3fold_header, buddy);
362 page = virt_to_page(zhdr);
363 if (zhdr->first_chunks == 0) {
364 if (zhdr->middle_chunks != 0 &&
365 chunks >= zhdr->start_middle)
366 bud = LAST;
367 else
368 bud = FIRST;
369 } else if (zhdr->last_chunks == 0)
370 bud = LAST;
371 else if (zhdr->middle_chunks == 0)
372 bud = MIDDLE;
373 else {
374 pr_err("No free chunks in unbuddied\n");
375 WARN_ON(1);
376 continue;
377 }
378 list_del(&zhdr->buddy);
379 goto found;
380 }
381 }
382 bud = FIRST;
383 spin_unlock(&pool->lock);
384 }
385
386 /* Couldn't find unbuddied z3fold page, create new one */
387 page = alloc_page(gfp);
388 if (!page)
389 return -ENOMEM;
390 spin_lock(&pool->lock);
Vitaly Wool12d59ae2017-02-24 14:57:15 -0800391 atomic64_inc(&pool->pages_nr);
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700392 zhdr = init_z3fold_page(page);
393
394 if (bud == HEADLESS) {
395 set_bit(PAGE_HEADLESS, &page->private);
396 goto headless;
397 }
398
399found:
400 if (bud == FIRST)
401 zhdr->first_chunks = chunks;
402 else if (bud == LAST)
403 zhdr->last_chunks = chunks;
404 else {
405 zhdr->middle_chunks = chunks;
Vitaly Woolede93212017-02-24 14:57:17 -0800406 zhdr->start_middle = zhdr->first_chunks + ZHDR_CHUNKS;
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700407 }
408
409 if (zhdr->first_chunks == 0 || zhdr->last_chunks == 0 ||
410 zhdr->middle_chunks == 0) {
411 /* Add to unbuddied list */
412 freechunks = num_free_chunks(zhdr);
413 list_add(&zhdr->buddy, &pool->unbuddied[freechunks]);
414 } else {
415 /* Add to buddied list */
416 list_add(&zhdr->buddy, &pool->buddied);
417 }
418
419headless:
420 /* Add/move z3fold page to beginning of LRU */
421 if (!list_empty(&page->lru))
422 list_del(&page->lru);
423
424 list_add(&page->lru, &pool->lru);
425
426 *handle = encode_handle(zhdr, bud);
427 spin_unlock(&pool->lock);
428
429 return 0;
430}
431
432/**
433 * z3fold_free() - frees the allocation associated with the given handle
434 * @pool: pool in which the allocation resided
435 * @handle: handle associated with the allocation returned by z3fold_alloc()
436 *
437 * In the case that the z3fold page in which the allocation resides is under
438 * reclaim, as indicated by the PG_reclaim flag being set, this function
439 * only sets the first|last_chunks to 0. The page is actually freed
440 * once both buddies are evicted (see z3fold_reclaim_page() below).
441 */
442static void z3fold_free(struct z3fold_pool *pool, unsigned long handle)
443{
444 struct z3fold_header *zhdr;
445 int freechunks;
446 struct page *page;
447 enum buddy bud;
448
449 spin_lock(&pool->lock);
450 zhdr = handle_to_z3fold_header(handle);
451 page = virt_to_page(zhdr);
452
453 if (test_bit(PAGE_HEADLESS, &page->private)) {
454 /* HEADLESS page stored */
455 bud = HEADLESS;
456 } else {
Vitaly Wool43afc192016-06-03 14:55:47 -0700457 bud = handle_to_buddy(handle);
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700458
459 switch (bud) {
460 case FIRST:
461 zhdr->first_chunks = 0;
462 break;
463 case MIDDLE:
464 zhdr->middle_chunks = 0;
465 zhdr->start_middle = 0;
466 break;
467 case LAST:
468 zhdr->last_chunks = 0;
469 break;
470 default:
471 pr_err("%s: unknown bud %d\n", __func__, bud);
472 WARN_ON(1);
473 spin_unlock(&pool->lock);
474 return;
475 }
476 }
477
478 if (test_bit(UNDER_RECLAIM, &page->private)) {
479 /* z3fold page is under reclaim, reclaim will free */
480 spin_unlock(&pool->lock);
481 return;
482 }
483
Vitaly Wool12d59ae2017-02-24 14:57:15 -0800484 /* Remove from existing buddy list */
485 if (bud != HEADLESS)
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700486 list_del(&zhdr->buddy);
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700487
488 if (bud == HEADLESS ||
489 (zhdr->first_chunks == 0 && zhdr->middle_chunks == 0 &&
490 zhdr->last_chunks == 0)) {
491 /* z3fold page is empty, free */
492 list_del(&page->lru);
493 clear_bit(PAGE_HEADLESS, &page->private);
494 free_z3fold_page(zhdr);
Vitaly Wool12d59ae2017-02-24 14:57:15 -0800495 atomic64_dec(&pool->pages_nr);
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700496 } else {
497 z3fold_compact_page(zhdr);
498 /* Add to the unbuddied list */
499 freechunks = num_free_chunks(zhdr);
500 list_add(&zhdr->buddy, &pool->unbuddied[freechunks]);
501 }
502
503 spin_unlock(&pool->lock);
504}
505
506/**
507 * z3fold_reclaim_page() - evicts allocations from a pool page and frees it
508 * @pool: pool from which a page will attempt to be evicted
509 * @retires: number of pages on the LRU list for which eviction will
510 * be attempted before failing
511 *
512 * z3fold reclaim is different from normal system reclaim in that it is done
513 * from the bottom, up. This is because only the bottom layer, z3fold, has
514 * information on how the allocations are organized within each z3fold page.
515 * This has the potential to create interesting locking situations between
516 * z3fold and the user, however.
517 *
518 * To avoid these, this is how z3fold_reclaim_page() should be called:
519
520 * The user detects a page should be reclaimed and calls z3fold_reclaim_page().
521 * z3fold_reclaim_page() will remove a z3fold page from the pool LRU list and
522 * call the user-defined eviction handler with the pool and handle as
523 * arguments.
524 *
525 * If the handle can not be evicted, the eviction handler should return
526 * non-zero. z3fold_reclaim_page() will add the z3fold page back to the
527 * appropriate list and try the next z3fold page on the LRU up to
528 * a user defined number of retries.
529 *
530 * If the handle is successfully evicted, the eviction handler should
531 * return 0 _and_ should have called z3fold_free() on the handle. z3fold_free()
532 * contains logic to delay freeing the page if the page is under reclaim,
533 * as indicated by the setting of the PG_reclaim flag on the underlying page.
534 *
535 * If all buddies in the z3fold page are successfully evicted, then the
536 * z3fold page can be freed.
537 *
538 * Returns: 0 if page is successfully freed, otherwise -EINVAL if there are
539 * no pages to evict or an eviction handler is not registered, -EAGAIN if
540 * the retry limit was hit.
541 */
542static int z3fold_reclaim_page(struct z3fold_pool *pool, unsigned int retries)
543{
544 int i, ret = 0, freechunks;
545 struct z3fold_header *zhdr;
546 struct page *page;
547 unsigned long first_handle = 0, middle_handle = 0, last_handle = 0;
548
549 spin_lock(&pool->lock);
550 if (!pool->ops || !pool->ops->evict || list_empty(&pool->lru) ||
551 retries == 0) {
552 spin_unlock(&pool->lock);
553 return -EINVAL;
554 }
555 for (i = 0; i < retries; i++) {
556 page = list_last_entry(&pool->lru, struct page, lru);
557 list_del(&page->lru);
558
559 /* Protect z3fold page against free */
560 set_bit(UNDER_RECLAIM, &page->private);
561 zhdr = page_address(page);
562 if (!test_bit(PAGE_HEADLESS, &page->private)) {
563 list_del(&zhdr->buddy);
564 /*
565 * We need encode the handles before unlocking, since
566 * we can race with free that will set
567 * (first|last)_chunks to 0
568 */
569 first_handle = 0;
570 last_handle = 0;
571 middle_handle = 0;
572 if (zhdr->first_chunks)
573 first_handle = encode_handle(zhdr, FIRST);
574 if (zhdr->middle_chunks)
575 middle_handle = encode_handle(zhdr, MIDDLE);
576 if (zhdr->last_chunks)
577 last_handle = encode_handle(zhdr, LAST);
578 } else {
579 first_handle = encode_handle(zhdr, HEADLESS);
580 last_handle = middle_handle = 0;
581 }
582
583 spin_unlock(&pool->lock);
584
585 /* Issue the eviction callback(s) */
586 if (middle_handle) {
587 ret = pool->ops->evict(pool, middle_handle);
588 if (ret)
589 goto next;
590 }
591 if (first_handle) {
592 ret = pool->ops->evict(pool, first_handle);
593 if (ret)
594 goto next;
595 }
596 if (last_handle) {
597 ret = pool->ops->evict(pool, last_handle);
598 if (ret)
599 goto next;
600 }
601next:
602 spin_lock(&pool->lock);
603 clear_bit(UNDER_RECLAIM, &page->private);
604 if ((test_bit(PAGE_HEADLESS, &page->private) && ret == 0) ||
605 (zhdr->first_chunks == 0 && zhdr->last_chunks == 0 &&
606 zhdr->middle_chunks == 0)) {
607 /*
608 * All buddies are now free, free the z3fold page and
609 * return success.
610 */
611 clear_bit(PAGE_HEADLESS, &page->private);
612 free_z3fold_page(zhdr);
Vitaly Wool12d59ae2017-02-24 14:57:15 -0800613 atomic64_dec(&pool->pages_nr);
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700614 spin_unlock(&pool->lock);
615 return 0;
Vitaly Wool43afc192016-06-03 14:55:47 -0700616 } else if (!test_bit(PAGE_HEADLESS, &page->private)) {
617 if (zhdr->first_chunks != 0 &&
618 zhdr->last_chunks != 0 &&
619 zhdr->middle_chunks != 0) {
620 /* Full, add to buddied list */
621 list_add(&zhdr->buddy, &pool->buddied);
622 } else {
623 z3fold_compact_page(zhdr);
624 /* add to unbuddied list */
625 freechunks = num_free_chunks(zhdr);
626 list_add(&zhdr->buddy,
627 &pool->unbuddied[freechunks]);
628 }
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700629 }
630
631 /* add to beginning of LRU */
632 list_add(&page->lru, &pool->lru);
633 }
634 spin_unlock(&pool->lock);
635 return -EAGAIN;
636}
637
638/**
639 * z3fold_map() - maps the allocation associated with the given handle
640 * @pool: pool in which the allocation resides
641 * @handle: handle associated with the allocation to be mapped
642 *
643 * Extracts the buddy number from handle and constructs the pointer to the
644 * correct starting chunk within the page.
645 *
646 * Returns: a pointer to the mapped allocation
647 */
648static void *z3fold_map(struct z3fold_pool *pool, unsigned long handle)
649{
650 struct z3fold_header *zhdr;
651 struct page *page;
652 void *addr;
653 enum buddy buddy;
654
655 spin_lock(&pool->lock);
656 zhdr = handle_to_z3fold_header(handle);
657 addr = zhdr;
658 page = virt_to_page(zhdr);
659
660 if (test_bit(PAGE_HEADLESS, &page->private))
661 goto out;
662
663 buddy = handle_to_buddy(handle);
664 switch (buddy) {
665 case FIRST:
666 addr += ZHDR_SIZE_ALIGNED;
667 break;
668 case MIDDLE:
669 addr += zhdr->start_middle << CHUNK_SHIFT;
670 set_bit(MIDDLE_CHUNK_MAPPED, &page->private);
671 break;
672 case LAST:
673 addr += PAGE_SIZE - (zhdr->last_chunks << CHUNK_SHIFT);
674 break;
675 default:
676 pr_err("unknown buddy id %d\n", buddy);
677 WARN_ON(1);
678 addr = NULL;
679 break;
680 }
681out:
682 spin_unlock(&pool->lock);
683 return addr;
684}
685
686/**
687 * z3fold_unmap() - unmaps the allocation associated with the given handle
688 * @pool: pool in which the allocation resides
689 * @handle: handle associated with the allocation to be unmapped
690 */
691static void z3fold_unmap(struct z3fold_pool *pool, unsigned long handle)
692{
693 struct z3fold_header *zhdr;
694 struct page *page;
695 enum buddy buddy;
696
697 spin_lock(&pool->lock);
698 zhdr = handle_to_z3fold_header(handle);
699 page = virt_to_page(zhdr);
700
701 if (test_bit(PAGE_HEADLESS, &page->private)) {
702 spin_unlock(&pool->lock);
703 return;
704 }
705
706 buddy = handle_to_buddy(handle);
707 if (buddy == MIDDLE)
708 clear_bit(MIDDLE_CHUNK_MAPPED, &page->private);
709 spin_unlock(&pool->lock);
710}
711
712/**
713 * z3fold_get_pool_size() - gets the z3fold pool size in pages
714 * @pool: pool whose size is being queried
715 *
Vitaly Wool12d59ae2017-02-24 14:57:15 -0800716 * Returns: size in pages of the given pool.
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700717 */
718static u64 z3fold_get_pool_size(struct z3fold_pool *pool)
719{
Vitaly Wool12d59ae2017-02-24 14:57:15 -0800720 return atomic64_read(&pool->pages_nr);
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700721}
722
723/*****************
724 * zpool
725 ****************/
726
727static int z3fold_zpool_evict(struct z3fold_pool *pool, unsigned long handle)
728{
729 if (pool->zpool && pool->zpool_ops && pool->zpool_ops->evict)
730 return pool->zpool_ops->evict(pool->zpool, handle);
731 else
732 return -ENOENT;
733}
734
735static const struct z3fold_ops z3fold_zpool_ops = {
736 .evict = z3fold_zpool_evict
737};
738
739static void *z3fold_zpool_create(const char *name, gfp_t gfp,
740 const struct zpool_ops *zpool_ops,
741 struct zpool *zpool)
742{
743 struct z3fold_pool *pool;
744
745 pool = z3fold_create_pool(gfp, zpool_ops ? &z3fold_zpool_ops : NULL);
746 if (pool) {
747 pool->zpool = zpool;
748 pool->zpool_ops = zpool_ops;
749 }
750 return pool;
751}
752
753static void z3fold_zpool_destroy(void *pool)
754{
755 z3fold_destroy_pool(pool);
756}
757
758static int z3fold_zpool_malloc(void *pool, size_t size, gfp_t gfp,
759 unsigned long *handle)
760{
761 return z3fold_alloc(pool, size, gfp, handle);
762}
763static void z3fold_zpool_free(void *pool, unsigned long handle)
764{
765 z3fold_free(pool, handle);
766}
767
768static int z3fold_zpool_shrink(void *pool, unsigned int pages,
769 unsigned int *reclaimed)
770{
771 unsigned int total = 0;
772 int ret = -EINVAL;
773
774 while (total < pages) {
775 ret = z3fold_reclaim_page(pool, 8);
776 if (ret < 0)
777 break;
778 total++;
779 }
780
781 if (reclaimed)
782 *reclaimed = total;
783
784 return ret;
785}
786
787static void *z3fold_zpool_map(void *pool, unsigned long handle,
788 enum zpool_mapmode mm)
789{
790 return z3fold_map(pool, handle);
791}
792static void z3fold_zpool_unmap(void *pool, unsigned long handle)
793{
794 z3fold_unmap(pool, handle);
795}
796
797static u64 z3fold_zpool_total_size(void *pool)
798{
799 return z3fold_get_pool_size(pool) * PAGE_SIZE;
800}
801
802static struct zpool_driver z3fold_zpool_driver = {
803 .type = "z3fold",
804 .owner = THIS_MODULE,
805 .create = z3fold_zpool_create,
806 .destroy = z3fold_zpool_destroy,
807 .malloc = z3fold_zpool_malloc,
808 .free = z3fold_zpool_free,
809 .shrink = z3fold_zpool_shrink,
810 .map = z3fold_zpool_map,
811 .unmap = z3fold_zpool_unmap,
812 .total_size = z3fold_zpool_total_size,
813};
814
815MODULE_ALIAS("zpool-z3fold");
816
817static int __init init_z3fold(void)
818{
Vitaly Woolede93212017-02-24 14:57:17 -0800819 /* Make sure the z3fold header is not larger than the page size */
820 BUILD_BUG_ON(ZHDR_SIZE_ALIGNED > PAGE_SIZE);
Vitaly Wool9a001fc2016-05-20 16:58:30 -0700821 zpool_register_driver(&z3fold_zpool_driver);
822
823 return 0;
824}
825
826static void __exit exit_z3fold(void)
827{
828 zpool_unregister_driver(&z3fold_zpool_driver);
829}
830
831module_init(init_z3fold);
832module_exit(exit_z3fold);
833
834MODULE_LICENSE("GPL");
835MODULE_AUTHOR("Vitaly Wool <vitalywool@gmail.com>");
836MODULE_DESCRIPTION("3-Fold Allocator for Compressed Pages");