1 // SPDX-License-Identifier: GPL-2.0-only
5 * Copyright (C) 2013, Seth Jennings, IBM
7 * Concepts based on zcache internal zbud allocator by Dan Magenheimer.
9 * zbud is an special purpose allocator for storing compressed pages. Contrary
10 * to what its name may suggest, zbud is not a buddy allocator, but rather an
11 * allocator that "buddies" two compressed pages together in a single memory
14 * While this design limits storage density, it has simple and deterministic
15 * reclaim properties that make it preferable to a higher density approach when
16 * reclaim will be used.
18 * zbud works by storing compressed pages, or "zpages", together in pairs in a
19 * single memory page called a "zbud page". The first buddy is "left
20 * justified" at the beginning of the zbud page, and the last buddy is "right
21 * justified" at the end of the zbud page. The benefit is that if either
22 * buddy is freed, the freed buddy space, coalesced with whatever slack space
23 * that existed between the buddies, results in the largest possible free region
24 * within the zbud page.
26 * zbud also provides an attractive lower bound on density. The ratio of zpages
27 * to zbud pages can not be less than 1. This ensures that zbud can never "do
28 * harm" by using more pages to store zpages than the uncompressed zpages would
29 * have used on their own.
31 * zbud pages are divided into "chunks". The size of the chunks is fixed at
32 * compile time and determined by NCHUNKS_ORDER below. Dividing zbud pages
33 * into chunks allows organizing unbuddied zbud pages into a manageable number
34 * of unbuddied lists according to the number of free chunks available in the
37 * The zbud API differs from that of conventional allocators in that the
38 * allocation function, zbud_alloc(), returns an opaque handle to the user,
39 * not a dereferenceable pointer. The user must map the handle using
40 * zbud_map() in order to get a usable pointer by which to access the
41 * allocation data and unmap the handle with zbud_unmap() when operations
42 * on the allocation data are complete.
45 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
47 #include <linux/atomic.h>
48 #include <linux/list.h>
50 #include <linux/module.h>
51 #include <linux/preempt.h>
52 #include <linux/slab.h>
53 #include <linux/spinlock.h>
54 #include <linux/zbud.h>
55 #include <linux/zpool.h>
61 * NCHUNKS_ORDER determines the internal allocation granularity, effectively
62 * adjusting internal fragmentation. It also determines the number of
63 * freelists maintained in each pool. NCHUNKS_ORDER of 6 means that the
64 * allocation granularity will be in chunks of size PAGE_SIZE/64. As one chunk
65 * in allocated page is occupied by zbud header, NCHUNKS will be calculated to
66 * 63 which shows the max number of free chunks in zbud page, also there will be
67 * 63 freelists per pool.
69 #define NCHUNKS_ORDER 6
71 #define CHUNK_SHIFT (PAGE_SHIFT - NCHUNKS_ORDER)
72 #define CHUNK_SIZE (1 << CHUNK_SHIFT)
73 #define ZHDR_SIZE_ALIGNED CHUNK_SIZE
74 #define NCHUNKS ((PAGE_SIZE - ZHDR_SIZE_ALIGNED) >> CHUNK_SHIFT)
77 * struct zbud_pool - stores metadata for each zbud pool
78 * @lock: protects all pool fields and first|last_chunk fields of any
79 * zbud page in the pool
80 * @unbuddied: array of lists tracking zbud pages that only contain one buddy;
81 * the lists each zbud page is added to depends on the size of
83 * @buddied: list tracking the zbud pages that contain two buddies;
84 * these zbud pages are full
85 * @lru: list tracking the zbud pages in LRU order by most recently
87 * @pages_nr: number of zbud pages in the pool.
88 * @ops: pointer to a structure of user defined operations specified at
91 * This structure is allocated at pool creation time and maintains metadata
92 * pertaining to a particular zbud pool.
98 * Reuse unbuddied[0] as buddied on the ground that
99 * unbuddied[0] is unused.
101 struct list_head buddied;
102 struct list_head unbuddied[NCHUNKS];
104 struct list_head lru;
106 const struct zbud_ops *ops;
109 const struct zpool_ops *zpool_ops;
114 * struct zbud_header - zbud page metadata occupying the first chunk of each
116 * @buddy: links the zbud page into the unbuddied/buddied lists in the pool
117 * @lru: links the zbud page into the lru list in the pool
118 * @first_chunks: the size of the first buddy in chunks, 0 if free
119 * @last_chunks: the size of the last buddy in chunks, 0 if free
122 struct list_head buddy;
123 struct list_head lru;
124 unsigned int first_chunks;
125 unsigned int last_chunks;
135 static int zbud_zpool_evict(struct zbud_pool *pool, unsigned long handle)
137 if (pool->zpool && pool->zpool_ops && pool->zpool_ops->evict)
138 return pool->zpool_ops->evict(pool->zpool, handle);
143 static const struct zbud_ops zbud_zpool_ops = {
144 .evict = zbud_zpool_evict
147 static void *zbud_zpool_create(const char *name, gfp_t gfp,
148 const struct zpool_ops *zpool_ops,
151 struct zbud_pool *pool;
153 pool = zbud_create_pool(gfp, zpool_ops ? &zbud_zpool_ops : NULL);
156 pool->zpool_ops = zpool_ops;
161 static void zbud_zpool_destroy(void *pool)
163 zbud_destroy_pool(pool);
166 static int zbud_zpool_malloc(void *pool, size_t size, gfp_t gfp,
167 unsigned long *handle)
169 return zbud_alloc(pool, size, gfp, handle);
171 static void zbud_zpool_free(void *pool, unsigned long handle)
173 zbud_free(pool, handle);
176 static int zbud_zpool_shrink(void *pool, unsigned int pages,
177 unsigned int *reclaimed)
179 unsigned int total = 0;
182 while (total < pages) {
183 ret = zbud_reclaim_page(pool, 8);
195 static void *zbud_zpool_map(void *pool, unsigned long handle,
196 enum zpool_mapmode mm)
198 return zbud_map(pool, handle);
200 static void zbud_zpool_unmap(void *pool, unsigned long handle)
202 zbud_unmap(pool, handle);
205 static u64 zbud_zpool_total_size(void *pool)
207 return zbud_get_pool_size(pool) * PAGE_SIZE;
210 static struct zpool_driver zbud_zpool_driver = {
212 .sleep_mapped = true,
213 .owner = THIS_MODULE,
214 .create = zbud_zpool_create,
215 .destroy = zbud_zpool_destroy,
216 .malloc = zbud_zpool_malloc,
217 .free = zbud_zpool_free,
218 .shrink = zbud_zpool_shrink,
219 .map = zbud_zpool_map,
220 .unmap = zbud_zpool_unmap,
221 .total_size = zbud_zpool_total_size,
224 MODULE_ALIAS("zpool-zbud");
225 #endif /* CONFIG_ZPOOL */
230 /* Just to make the code easier to read */
236 /* Converts an allocation size in bytes to size in zbud chunks */
237 static int size_to_chunks(size_t size)
239 return (size + CHUNK_SIZE - 1) >> CHUNK_SHIFT;
242 #define for_each_unbuddied_list(_iter, _begin) \
243 for ((_iter) = (_begin); (_iter) < NCHUNKS; (_iter)++)
245 /* Initializes the zbud header of a newly allocated zbud page */
246 static struct zbud_header *init_zbud_page(struct page *page)
248 struct zbud_header *zhdr = page_address(page);
249 zhdr->first_chunks = 0;
250 zhdr->last_chunks = 0;
251 INIT_LIST_HEAD(&zhdr->buddy);
252 INIT_LIST_HEAD(&zhdr->lru);
253 zhdr->under_reclaim = false;
257 /* Resets the struct page fields and frees the page */
258 static void free_zbud_page(struct zbud_header *zhdr)
260 __free_page(virt_to_page(zhdr));
264 * Encodes the handle of a particular buddy within a zbud page
265 * Pool lock should be held as this function accesses first|last_chunks
267 static unsigned long encode_handle(struct zbud_header *zhdr, enum buddy bud)
269 unsigned long handle;
272 * For now, the encoded handle is actually just the pointer to the data
273 * but this might not always be the case. A little information hiding.
274 * Add CHUNK_SIZE to the handle if it is the first allocation to jump
275 * over the zbud header in the first chunk.
277 handle = (unsigned long)zhdr;
279 /* skip over zbud header */
280 handle += ZHDR_SIZE_ALIGNED;
281 else /* bud == LAST */
282 handle += PAGE_SIZE - (zhdr->last_chunks << CHUNK_SHIFT);
286 /* Returns the zbud page where a given handle is stored */
287 static struct zbud_header *handle_to_zbud_header(unsigned long handle)
289 return (struct zbud_header *)(handle & PAGE_MASK);
292 /* Returns the number of free chunks in a zbud page */
293 static int num_free_chunks(struct zbud_header *zhdr)
296 * Rather than branch for different situations, just use the fact that
297 * free buddies have a length of zero to simplify everything.
299 return NCHUNKS - zhdr->first_chunks - zhdr->last_chunks;
306 * zbud_create_pool() - create a new zbud pool
307 * @gfp: gfp flags when allocating the zbud pool structure
308 * @ops: user-defined operations for the zbud pool
310 * Return: pointer to the new zbud pool or NULL if the metadata allocation
313 struct zbud_pool *zbud_create_pool(gfp_t gfp, const struct zbud_ops *ops)
315 struct zbud_pool *pool;
318 pool = kzalloc(sizeof(struct zbud_pool), gfp);
321 spin_lock_init(&pool->lock);
322 for_each_unbuddied_list(i, 0)
323 INIT_LIST_HEAD(&pool->unbuddied[i]);
324 INIT_LIST_HEAD(&pool->buddied);
325 INIT_LIST_HEAD(&pool->lru);
332 * zbud_destroy_pool() - destroys an existing zbud pool
333 * @pool: the zbud pool to be destroyed
335 * The pool should be emptied before this function is called.
337 void zbud_destroy_pool(struct zbud_pool *pool)
343 * zbud_alloc() - allocates a region of a given size
344 * @pool: zbud pool from which to allocate
345 * @size: size in bytes of the desired allocation
346 * @gfp: gfp flags used if the pool needs to grow
347 * @handle: handle of the new allocation
349 * This function will attempt to find a free region in the pool large enough to
350 * satisfy the allocation request. A search of the unbuddied lists is
351 * performed first. If no suitable free region is found, then a new page is
352 * allocated and added to the pool to satisfy the request.
354 * gfp should not set __GFP_HIGHMEM as highmem pages cannot be used
355 * as zbud pool pages.
357 * Return: 0 if success and handle is set, otherwise -EINVAL if the size or
358 * gfp arguments are invalid or -ENOMEM if the pool was unable to allocate
361 int zbud_alloc(struct zbud_pool *pool, size_t size, gfp_t gfp,
362 unsigned long *handle)
364 int chunks, i, freechunks;
365 struct zbud_header *zhdr = NULL;
369 if (!size || (gfp & __GFP_HIGHMEM))
371 if (size > PAGE_SIZE - ZHDR_SIZE_ALIGNED - CHUNK_SIZE)
373 chunks = size_to_chunks(size);
374 spin_lock(&pool->lock);
376 /* First, try to find an unbuddied zbud page. */
377 for_each_unbuddied_list(i, chunks) {
378 if (!list_empty(&pool->unbuddied[i])) {
379 zhdr = list_first_entry(&pool->unbuddied[i],
380 struct zbud_header, buddy);
381 list_del(&zhdr->buddy);
382 if (zhdr->first_chunks == 0)
390 /* Couldn't find unbuddied zbud page, create new one */
391 spin_unlock(&pool->lock);
392 page = alloc_page(gfp);
395 spin_lock(&pool->lock);
397 zhdr = init_zbud_page(page);
402 zhdr->first_chunks = chunks;
404 zhdr->last_chunks = chunks;
406 if (zhdr->first_chunks == 0 || zhdr->last_chunks == 0) {
407 /* Add to unbuddied list */
408 freechunks = num_free_chunks(zhdr);
409 list_add(&zhdr->buddy, &pool->unbuddied[freechunks]);
411 /* Add to buddied list */
412 list_add(&zhdr->buddy, &pool->buddied);
415 /* Add/move zbud page to beginning of LRU */
416 if (!list_empty(&zhdr->lru))
417 list_del(&zhdr->lru);
418 list_add(&zhdr->lru, &pool->lru);
420 *handle = encode_handle(zhdr, bud);
421 spin_unlock(&pool->lock);
427 * zbud_free() - frees the allocation associated with the given handle
428 * @pool: pool in which the allocation resided
429 * @handle: handle associated with the allocation returned by zbud_alloc()
431 * In the case that the zbud page in which the allocation resides is under
432 * reclaim, as indicated by the PG_reclaim flag being set, this function
433 * only sets the first|last_chunks to 0. The page is actually freed
434 * once both buddies are evicted (see zbud_reclaim_page() below).
436 void zbud_free(struct zbud_pool *pool, unsigned long handle)
438 struct zbud_header *zhdr;
441 spin_lock(&pool->lock);
442 zhdr = handle_to_zbud_header(handle);
444 /* If first buddy, handle will be page aligned */
445 if ((handle - ZHDR_SIZE_ALIGNED) & ~PAGE_MASK)
446 zhdr->last_chunks = 0;
448 zhdr->first_chunks = 0;
450 if (zhdr->under_reclaim) {
451 /* zbud page is under reclaim, reclaim will free */
452 spin_unlock(&pool->lock);
456 /* Remove from existing buddy list */
457 list_del(&zhdr->buddy);
459 if (zhdr->first_chunks == 0 && zhdr->last_chunks == 0) {
460 /* zbud page is empty, free */
461 list_del(&zhdr->lru);
462 free_zbud_page(zhdr);
465 /* Add to unbuddied list */
466 freechunks = num_free_chunks(zhdr);
467 list_add(&zhdr->buddy, &pool->unbuddied[freechunks]);
470 spin_unlock(&pool->lock);
474 * zbud_reclaim_page() - evicts allocations from a pool page and frees it
475 * @pool: pool from which a page will attempt to be evicted
476 * @retries: number of pages on the LRU list for which eviction will
477 * be attempted before failing
479 * zbud reclaim is different from normal system reclaim in that the reclaim is
480 * done from the bottom, up. This is because only the bottom layer, zbud, has
481 * information on how the allocations are organized within each zbud page. This
482 * has the potential to create interesting locking situations between zbud and
485 * To avoid these, this is how zbud_reclaim_page() should be called:
487 * The user detects a page should be reclaimed and calls zbud_reclaim_page().
488 * zbud_reclaim_page() will remove a zbud page from the pool LRU list and call
489 * the user-defined eviction handler with the pool and handle as arguments.
491 * If the handle can not be evicted, the eviction handler should return
492 * non-zero. zbud_reclaim_page() will add the zbud page back to the
493 * appropriate list and try the next zbud page on the LRU up to
494 * a user defined number of retries.
496 * If the handle is successfully evicted, the eviction handler should
497 * return 0 _and_ should have called zbud_free() on the handle. zbud_free()
498 * contains logic to delay freeing the page if the page is under reclaim,
499 * as indicated by the setting of the PG_reclaim flag on the underlying page.
501 * If all buddies in the zbud page are successfully evicted, then the
502 * zbud page can be freed.
504 * Returns: 0 if page is successfully freed, otherwise -EINVAL if there are
505 * no pages to evict or an eviction handler is not registered, -EAGAIN if
506 * the retry limit was hit.
508 int zbud_reclaim_page(struct zbud_pool *pool, unsigned int retries)
510 int i, ret, freechunks;
511 struct zbud_header *zhdr;
512 unsigned long first_handle = 0, last_handle = 0;
514 spin_lock(&pool->lock);
515 if (!pool->ops || !pool->ops->evict || list_empty(&pool->lru) ||
517 spin_unlock(&pool->lock);
520 for (i = 0; i < retries; i++) {
521 zhdr = list_last_entry(&pool->lru, struct zbud_header, lru);
522 list_del(&zhdr->lru);
523 list_del(&zhdr->buddy);
524 /* Protect zbud page against free */
525 zhdr->under_reclaim = true;
527 * We need encode the handles before unlocking, since we can
528 * race with free that will set (first|last)_chunks to 0
532 if (zhdr->first_chunks)
533 first_handle = encode_handle(zhdr, FIRST);
534 if (zhdr->last_chunks)
535 last_handle = encode_handle(zhdr, LAST);
536 spin_unlock(&pool->lock);
538 /* Issue the eviction callback(s) */
540 ret = pool->ops->evict(pool, first_handle);
545 ret = pool->ops->evict(pool, last_handle);
550 spin_lock(&pool->lock);
551 zhdr->under_reclaim = false;
552 if (zhdr->first_chunks == 0 && zhdr->last_chunks == 0) {
554 * Both buddies are now free, free the zbud page and
557 free_zbud_page(zhdr);
559 spin_unlock(&pool->lock);
561 } else if (zhdr->first_chunks == 0 ||
562 zhdr->last_chunks == 0) {
563 /* add to unbuddied list */
564 freechunks = num_free_chunks(zhdr);
565 list_add(&zhdr->buddy, &pool->unbuddied[freechunks]);
567 /* add to buddied list */
568 list_add(&zhdr->buddy, &pool->buddied);
571 /* add to beginning of LRU */
572 list_add(&zhdr->lru, &pool->lru);
574 spin_unlock(&pool->lock);
579 * zbud_map() - maps the allocation associated with the given handle
580 * @pool: pool in which the allocation resides
581 * @handle: handle associated with the allocation to be mapped
583 * While trivial for zbud, the mapping functions for others allocators
584 * implementing this allocation API could have more complex information encoded
585 * in the handle and could create temporary mappings to make the data
586 * accessible to the user.
588 * Returns: a pointer to the mapped allocation
590 void *zbud_map(struct zbud_pool *pool, unsigned long handle)
592 return (void *)(handle);
596 * zbud_unmap() - maps the allocation associated with the given handle
597 * @pool: pool in which the allocation resides
598 * @handle: handle associated with the allocation to be unmapped
600 void zbud_unmap(struct zbud_pool *pool, unsigned long handle)
605 * zbud_get_pool_size() - gets the zbud pool size in pages
606 * @pool: pool whose size is being queried
608 * Returns: size in pages of the given pool. The pool lock need not be
609 * taken to access pages_nr.
611 u64 zbud_get_pool_size(struct zbud_pool *pool)
613 return pool->pages_nr;
616 static int __init init_zbud(void)
618 /* Make sure the zbud header will fit in one chunk */
619 BUILD_BUG_ON(sizeof(struct zbud_header) > ZHDR_SIZE_ALIGNED);
623 zpool_register_driver(&zbud_zpool_driver);
629 static void __exit exit_zbud(void)
632 zpool_unregister_driver(&zbud_zpool_driver);
635 pr_info("unloaded\n");
638 module_init(init_zbud);
639 module_exit(exit_zbud);
641 MODULE_LICENSE("GPL");
642 MODULE_AUTHOR("Seth Jennings <sjennings@variantweb.net>");
643 MODULE_DESCRIPTION("Buddy Allocator for Compressed Pages");