Back to home page

LXR

 
 

    


0001 /*
0002  * zbud.c
0003  *
0004  * Copyright (C) 2013, Seth Jennings, IBM
0005  *
0006  * Concepts based on zcache internal zbud allocator by Dan Magenheimer.
0007  *
0008  * zbud is an special purpose allocator for storing compressed pages.  Contrary
0009  * to what its name may suggest, zbud is not a buddy allocator, but rather an
0010  * allocator that "buddies" two compressed pages together in a single memory
0011  * page.
0012  *
0013  * While this design limits storage density, it has simple and deterministic
0014  * reclaim properties that make it preferable to a higher density approach when
0015  * reclaim will be used.
0016  *
0017  * zbud works by storing compressed pages, or "zpages", together in pairs in a
0018  * single memory page called a "zbud page".  The first buddy is "left
0019  * justified" at the beginning of the zbud page, and the last buddy is "right
0020  * justified" at the end of the zbud page.  The benefit is that if either
0021  * buddy is freed, the freed buddy space, coalesced with whatever slack space
0022  * that existed between the buddies, results in the largest possible free region
0023  * within the zbud page.
0024  *
0025  * zbud also provides an attractive lower bound on density. The ratio of zpages
0026  * to zbud pages can not be less than 1.  This ensures that zbud can never "do
0027  * harm" by using more pages to store zpages than the uncompressed zpages would
0028  * have used on their own.
0029  *
0030  * zbud pages are divided into "chunks".  The size of the chunks is fixed at
0031  * compile time and determined by NCHUNKS_ORDER below.  Dividing zbud pages
0032  * into chunks allows organizing unbuddied zbud pages into a manageable number
0033  * of unbuddied lists according to the number of free chunks available in the
0034  * zbud page.
0035  *
0036  * The zbud API differs from that of conventional allocators in that the
0037  * allocation function, zbud_alloc(), returns an opaque handle to the user,
0038  * not a dereferenceable pointer.  The user must map the handle using
0039  * zbud_map() in order to get a usable pointer by which to access the
0040  * allocation data and unmap the handle with zbud_unmap() when operations
0041  * on the allocation data are complete.
0042  */
0043 
0044 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
0045 
0046 #include <linux/atomic.h>
0047 #include <linux/list.h>
0048 #include <linux/mm.h>
0049 #include <linux/module.h>
0050 #include <linux/preempt.h>
0051 #include <linux/slab.h>
0052 #include <linux/spinlock.h>
0053 #include <linux/zbud.h>
0054 #include <linux/zpool.h>
0055 
0056 /*****************
0057  * Structures
0058 *****************/
0059 /*
0060  * NCHUNKS_ORDER determines the internal allocation granularity, effectively
0061  * adjusting internal fragmentation.  It also determines the number of
0062  * freelists maintained in each pool. NCHUNKS_ORDER of 6 means that the
0063  * allocation granularity will be in chunks of size PAGE_SIZE/64. As one chunk
0064  * in allocated page is occupied by zbud header, NCHUNKS will be calculated to
0065  * 63 which shows the max number of free chunks in zbud page, also there will be
0066  * 63 freelists per pool.
0067  */
0068 #define NCHUNKS_ORDER   6
0069 
0070 #define CHUNK_SHIFT (PAGE_SHIFT - NCHUNKS_ORDER)
0071 #define CHUNK_SIZE  (1 << CHUNK_SHIFT)
0072 #define ZHDR_SIZE_ALIGNED CHUNK_SIZE
0073 #define NCHUNKS     ((PAGE_SIZE - ZHDR_SIZE_ALIGNED) >> CHUNK_SHIFT)
0074 
0075 /**
0076  * struct zbud_pool - stores metadata for each zbud pool
0077  * @lock:   protects all pool fields and first|last_chunk fields of any
0078  *      zbud page in the pool
0079  * @unbuddied:  array of lists tracking zbud pages that only contain one buddy;
0080  *      the lists each zbud page is added to depends on the size of
0081  *      its free region.
0082  * @buddied:    list tracking the zbud pages that contain two buddies;
0083  *      these zbud pages are full
0084  * @lru:    list tracking the zbud pages in LRU order by most recently
0085  *      added buddy.
0086  * @pages_nr:   number of zbud pages in the pool.
0087  * @ops:    pointer to a structure of user defined operations specified at
0088  *      pool creation time.
0089  *
0090  * This structure is allocated at pool creation time and maintains metadata
0091  * pertaining to a particular zbud pool.
0092  */
0093 struct zbud_pool {
0094     spinlock_t lock;
0095     struct list_head unbuddied[NCHUNKS];
0096     struct list_head buddied;
0097     struct list_head lru;
0098     u64 pages_nr;
0099     const struct zbud_ops *ops;
0100 #ifdef CONFIG_ZPOOL
0101     struct zpool *zpool;
0102     const struct zpool_ops *zpool_ops;
0103 #endif
0104 };
0105 
0106 /*
0107  * struct zbud_header - zbud page metadata occupying the first chunk of each
0108  *          zbud page.
0109  * @buddy:  links the zbud page into the unbuddied/buddied lists in the pool
0110  * @lru:    links the zbud page into the lru list in the pool
0111  * @first_chunks:   the size of the first buddy in chunks, 0 if free
0112  * @last_chunks:    the size of the last buddy in chunks, 0 if free
0113  */
0114 struct zbud_header {
0115     struct list_head buddy;
0116     struct list_head lru;
0117     unsigned int first_chunks;
0118     unsigned int last_chunks;
0119     bool under_reclaim;
0120 };
0121 
0122 /*****************
0123  * zpool
0124  ****************/
0125 
0126 #ifdef CONFIG_ZPOOL
0127 
0128 static int zbud_zpool_evict(struct zbud_pool *pool, unsigned long handle)
0129 {
0130     if (pool->zpool && pool->zpool_ops && pool->zpool_ops->evict)
0131         return pool->zpool_ops->evict(pool->zpool, handle);
0132     else
0133         return -ENOENT;
0134 }
0135 
0136 static const struct zbud_ops zbud_zpool_ops = {
0137     .evict =    zbud_zpool_evict
0138 };
0139 
0140 static void *zbud_zpool_create(const char *name, gfp_t gfp,
0141                    const struct zpool_ops *zpool_ops,
0142                    struct zpool *zpool)
0143 {
0144     struct zbud_pool *pool;
0145 
0146     pool = zbud_create_pool(gfp, zpool_ops ? &zbud_zpool_ops : NULL);
0147     if (pool) {
0148         pool->zpool = zpool;
0149         pool->zpool_ops = zpool_ops;
0150     }
0151     return pool;
0152 }
0153 
0154 static void zbud_zpool_destroy(void *pool)
0155 {
0156     zbud_destroy_pool(pool);
0157 }
0158 
0159 static int zbud_zpool_malloc(void *pool, size_t size, gfp_t gfp,
0160             unsigned long *handle)
0161 {
0162     return zbud_alloc(pool, size, gfp, handle);
0163 }
0164 static void zbud_zpool_free(void *pool, unsigned long handle)
0165 {
0166     zbud_free(pool, handle);
0167 }
0168 
0169 static int zbud_zpool_shrink(void *pool, unsigned int pages,
0170             unsigned int *reclaimed)
0171 {
0172     unsigned int total = 0;
0173     int ret = -EINVAL;
0174 
0175     while (total < pages) {
0176         ret = zbud_reclaim_page(pool, 8);
0177         if (ret < 0)
0178             break;
0179         total++;
0180     }
0181 
0182     if (reclaimed)
0183         *reclaimed = total;
0184 
0185     return ret;
0186 }
0187 
0188 static void *zbud_zpool_map(void *pool, unsigned long handle,
0189             enum zpool_mapmode mm)
0190 {
0191     return zbud_map(pool, handle);
0192 }
0193 static void zbud_zpool_unmap(void *pool, unsigned long handle)
0194 {
0195     zbud_unmap(pool, handle);
0196 }
0197 
0198 static u64 zbud_zpool_total_size(void *pool)
0199 {
0200     return zbud_get_pool_size(pool) * PAGE_SIZE;
0201 }
0202 
0203 static struct zpool_driver zbud_zpool_driver = {
0204     .type =     "zbud",
0205     .owner =    THIS_MODULE,
0206     .create =   zbud_zpool_create,
0207     .destroy =  zbud_zpool_destroy,
0208     .malloc =   zbud_zpool_malloc,
0209     .free =     zbud_zpool_free,
0210     .shrink =   zbud_zpool_shrink,
0211     .map =      zbud_zpool_map,
0212     .unmap =    zbud_zpool_unmap,
0213     .total_size =   zbud_zpool_total_size,
0214 };
0215 
0216 MODULE_ALIAS("zpool-zbud");
0217 #endif /* CONFIG_ZPOOL */
0218 
0219 /*****************
0220  * Helpers
0221 *****************/
0222 /* Just to make the code easier to read */
0223 enum buddy {
0224     FIRST,
0225     LAST
0226 };
0227 
0228 /* Converts an allocation size in bytes to size in zbud chunks */
0229 static int size_to_chunks(size_t size)
0230 {
0231     return (size + CHUNK_SIZE - 1) >> CHUNK_SHIFT;
0232 }
0233 
0234 #define for_each_unbuddied_list(_iter, _begin) \
0235     for ((_iter) = (_begin); (_iter) < NCHUNKS; (_iter)++)
0236 
0237 /* Initializes the zbud header of a newly allocated zbud page */
0238 static struct zbud_header *init_zbud_page(struct page *page)
0239 {
0240     struct zbud_header *zhdr = page_address(page);
0241     zhdr->first_chunks = 0;
0242     zhdr->last_chunks = 0;
0243     INIT_LIST_HEAD(&zhdr->buddy);
0244     INIT_LIST_HEAD(&zhdr->lru);
0245     zhdr->under_reclaim = 0;
0246     return zhdr;
0247 }
0248 
0249 /* Resets the struct page fields and frees the page */
0250 static void free_zbud_page(struct zbud_header *zhdr)
0251 {
0252     __free_page(virt_to_page(zhdr));
0253 }
0254 
0255 /*
0256  * Encodes the handle of a particular buddy within a zbud page
0257  * Pool lock should be held as this function accesses first|last_chunks
0258  */
0259 static unsigned long encode_handle(struct zbud_header *zhdr, enum buddy bud)
0260 {
0261     unsigned long handle;
0262 
0263     /*
0264      * For now, the encoded handle is actually just the pointer to the data
0265      * but this might not always be the case.  A little information hiding.
0266      * Add CHUNK_SIZE to the handle if it is the first allocation to jump
0267      * over the zbud header in the first chunk.
0268      */
0269     handle = (unsigned long)zhdr;
0270     if (bud == FIRST)
0271         /* skip over zbud header */
0272         handle += ZHDR_SIZE_ALIGNED;
0273     else /* bud == LAST */
0274         handle += PAGE_SIZE - (zhdr->last_chunks  << CHUNK_SHIFT);
0275     return handle;
0276 }
0277 
0278 /* Returns the zbud page where a given handle is stored */
0279 static struct zbud_header *handle_to_zbud_header(unsigned long handle)
0280 {
0281     return (struct zbud_header *)(handle & PAGE_MASK);
0282 }
0283 
0284 /* Returns the number of free chunks in a zbud page */
0285 static int num_free_chunks(struct zbud_header *zhdr)
0286 {
0287     /*
0288      * Rather than branch for different situations, just use the fact that
0289      * free buddies have a length of zero to simplify everything.
0290      */
0291     return NCHUNKS - zhdr->first_chunks - zhdr->last_chunks;
0292 }
0293 
0294 /*****************
0295  * API Functions
0296 *****************/
0297 /**
0298  * zbud_create_pool() - create a new zbud pool
0299  * @gfp:    gfp flags when allocating the zbud pool structure
0300  * @ops:    user-defined operations for the zbud pool
0301  *
0302  * Return: pointer to the new zbud pool or NULL if the metadata allocation
0303  * failed.
0304  */
0305 struct zbud_pool *zbud_create_pool(gfp_t gfp, const struct zbud_ops *ops)
0306 {
0307     struct zbud_pool *pool;
0308     int i;
0309 
0310     pool = kzalloc(sizeof(struct zbud_pool), gfp);
0311     if (!pool)
0312         return NULL;
0313     spin_lock_init(&pool->lock);
0314     for_each_unbuddied_list(i, 0)
0315         INIT_LIST_HEAD(&pool->unbuddied[i]);
0316     INIT_LIST_HEAD(&pool->buddied);
0317     INIT_LIST_HEAD(&pool->lru);
0318     pool->pages_nr = 0;
0319     pool->ops = ops;
0320     return pool;
0321 }
0322 
0323 /**
0324  * zbud_destroy_pool() - destroys an existing zbud pool
0325  * @pool:   the zbud pool to be destroyed
0326  *
0327  * The pool should be emptied before this function is called.
0328  */
0329 void zbud_destroy_pool(struct zbud_pool *pool)
0330 {
0331     kfree(pool);
0332 }
0333 
0334 /**
0335  * zbud_alloc() - allocates a region of a given size
0336  * @pool:   zbud pool from which to allocate
0337  * @size:   size in bytes of the desired allocation
0338  * @gfp:    gfp flags used if the pool needs to grow
0339  * @handle: handle of the new allocation
0340  *
0341  * This function will attempt to find a free region in the pool large enough to
0342  * satisfy the allocation request.  A search of the unbuddied lists is
0343  * performed first. If no suitable free region is found, then a new page is
0344  * allocated and added to the pool to satisfy the request.
0345  *
0346  * gfp should not set __GFP_HIGHMEM as highmem pages cannot be used
0347  * as zbud pool pages.
0348  *
0349  * Return: 0 if success and handle is set, otherwise -EINVAL if the size or
0350  * gfp arguments are invalid or -ENOMEM if the pool was unable to allocate
0351  * a new page.
0352  */
0353 int zbud_alloc(struct zbud_pool *pool, size_t size, gfp_t gfp,
0354             unsigned long *handle)
0355 {
0356     int chunks, i, freechunks;
0357     struct zbud_header *zhdr = NULL;
0358     enum buddy bud;
0359     struct page *page;
0360 
0361     if (!size || (gfp & __GFP_HIGHMEM))
0362         return -EINVAL;
0363     if (size > PAGE_SIZE - ZHDR_SIZE_ALIGNED - CHUNK_SIZE)
0364         return -ENOSPC;
0365     chunks = size_to_chunks(size);
0366     spin_lock(&pool->lock);
0367 
0368     /* First, try to find an unbuddied zbud page. */
0369     zhdr = NULL;
0370     for_each_unbuddied_list(i, chunks) {
0371         if (!list_empty(&pool->unbuddied[i])) {
0372             zhdr = list_first_entry(&pool->unbuddied[i],
0373                     struct zbud_header, buddy);
0374             list_del(&zhdr->buddy);
0375             if (zhdr->first_chunks == 0)
0376                 bud = FIRST;
0377             else
0378                 bud = LAST;
0379             goto found;
0380         }
0381     }
0382 
0383     /* Couldn't find unbuddied zbud page, create new one */
0384     spin_unlock(&pool->lock);
0385     page = alloc_page(gfp);
0386     if (!page)
0387         return -ENOMEM;
0388     spin_lock(&pool->lock);
0389     pool->pages_nr++;
0390     zhdr = init_zbud_page(page);
0391     bud = FIRST;
0392 
0393 found:
0394     if (bud == FIRST)
0395         zhdr->first_chunks = chunks;
0396     else
0397         zhdr->last_chunks = chunks;
0398 
0399     if (zhdr->first_chunks == 0 || zhdr->last_chunks == 0) {
0400         /* Add to unbuddied list */
0401         freechunks = num_free_chunks(zhdr);
0402         list_add(&zhdr->buddy, &pool->unbuddied[freechunks]);
0403     } else {
0404         /* Add to buddied list */
0405         list_add(&zhdr->buddy, &pool->buddied);
0406     }
0407 
0408     /* Add/move zbud page to beginning of LRU */
0409     if (!list_empty(&zhdr->lru))
0410         list_del(&zhdr->lru);
0411     list_add(&zhdr->lru, &pool->lru);
0412 
0413     *handle = encode_handle(zhdr, bud);
0414     spin_unlock(&pool->lock);
0415 
0416     return 0;
0417 }
0418 
0419 /**
0420  * zbud_free() - frees the allocation associated with the given handle
0421  * @pool:   pool in which the allocation resided
0422  * @handle: handle associated with the allocation returned by zbud_alloc()
0423  *
0424  * In the case that the zbud page in which the allocation resides is under
0425  * reclaim, as indicated by the PG_reclaim flag being set, this function
0426  * only sets the first|last_chunks to 0.  The page is actually freed
0427  * once both buddies are evicted (see zbud_reclaim_page() below).
0428  */
0429 void zbud_free(struct zbud_pool *pool, unsigned long handle)
0430 {
0431     struct zbud_header *zhdr;
0432     int freechunks;
0433 
0434     spin_lock(&pool->lock);
0435     zhdr = handle_to_zbud_header(handle);
0436 
0437     /* If first buddy, handle will be page aligned */
0438     if ((handle - ZHDR_SIZE_ALIGNED) & ~PAGE_MASK)
0439         zhdr->last_chunks = 0;
0440     else
0441         zhdr->first_chunks = 0;
0442 
0443     if (zhdr->under_reclaim) {
0444         /* zbud page is under reclaim, reclaim will free */
0445         spin_unlock(&pool->lock);
0446         return;
0447     }
0448 
0449     /* Remove from existing buddy list */
0450     list_del(&zhdr->buddy);
0451 
0452     if (zhdr->first_chunks == 0 && zhdr->last_chunks == 0) {
0453         /* zbud page is empty, free */
0454         list_del(&zhdr->lru);
0455         free_zbud_page(zhdr);
0456         pool->pages_nr--;
0457     } else {
0458         /* Add to unbuddied list */
0459         freechunks = num_free_chunks(zhdr);
0460         list_add(&zhdr->buddy, &pool->unbuddied[freechunks]);
0461     }
0462 
0463     spin_unlock(&pool->lock);
0464 }
0465 
0466 /**
0467  * zbud_reclaim_page() - evicts allocations from a pool page and frees it
0468  * @pool:   pool from which a page will attempt to be evicted
0469  * @retires:    number of pages on the LRU list for which eviction will
0470  *      be attempted before failing
0471  *
0472  * zbud reclaim is different from normal system reclaim in that the reclaim is
0473  * done from the bottom, up.  This is because only the bottom layer, zbud, has
0474  * information on how the allocations are organized within each zbud page. This
0475  * has the potential to create interesting locking situations between zbud and
0476  * the user, however.
0477  *
0478  * To avoid these, this is how zbud_reclaim_page() should be called:
0479 
0480  * The user detects a page should be reclaimed and calls zbud_reclaim_page().
0481  * zbud_reclaim_page() will remove a zbud page from the pool LRU list and call
0482  * the user-defined eviction handler with the pool and handle as arguments.
0483  *
0484  * If the handle can not be evicted, the eviction handler should return
0485  * non-zero. zbud_reclaim_page() will add the zbud page back to the
0486  * appropriate list and try the next zbud page on the LRU up to
0487  * a user defined number of retries.
0488  *
0489  * If the handle is successfully evicted, the eviction handler should
0490  * return 0 _and_ should have called zbud_free() on the handle. zbud_free()
0491  * contains logic to delay freeing the page if the page is under reclaim,
0492  * as indicated by the setting of the PG_reclaim flag on the underlying page.
0493  *
0494  * If all buddies in the zbud page are successfully evicted, then the
0495  * zbud page can be freed.
0496  *
0497  * Returns: 0 if page is successfully freed, otherwise -EINVAL if there are
0498  * no pages to evict or an eviction handler is not registered, -EAGAIN if
0499  * the retry limit was hit.
0500  */
0501 int zbud_reclaim_page(struct zbud_pool *pool, unsigned int retries)
0502 {
0503     int i, ret, freechunks;
0504     struct zbud_header *zhdr;
0505     unsigned long first_handle = 0, last_handle = 0;
0506 
0507     spin_lock(&pool->lock);
0508     if (!pool->ops || !pool->ops->evict || list_empty(&pool->lru) ||
0509             retries == 0) {
0510         spin_unlock(&pool->lock);
0511         return -EINVAL;
0512     }
0513     for (i = 0; i < retries; i++) {
0514         zhdr = list_last_entry(&pool->lru, struct zbud_header, lru);
0515         list_del(&zhdr->lru);
0516         list_del(&zhdr->buddy);
0517         /* Protect zbud page against free */
0518         zhdr->under_reclaim = true;
0519         /*
0520          * We need encode the handles before unlocking, since we can
0521          * race with free that will set (first|last)_chunks to 0
0522          */
0523         first_handle = 0;
0524         last_handle = 0;
0525         if (zhdr->first_chunks)
0526             first_handle = encode_handle(zhdr, FIRST);
0527         if (zhdr->last_chunks)
0528             last_handle = encode_handle(zhdr, LAST);
0529         spin_unlock(&pool->lock);
0530 
0531         /* Issue the eviction callback(s) */
0532         if (first_handle) {
0533             ret = pool->ops->evict(pool, first_handle);
0534             if (ret)
0535                 goto next;
0536         }
0537         if (last_handle) {
0538             ret = pool->ops->evict(pool, last_handle);
0539             if (ret)
0540                 goto next;
0541         }
0542 next:
0543         spin_lock(&pool->lock);
0544         zhdr->under_reclaim = false;
0545         if (zhdr->first_chunks == 0 && zhdr->last_chunks == 0) {
0546             /*
0547              * Both buddies are now free, free the zbud page and
0548              * return success.
0549              */
0550             free_zbud_page(zhdr);
0551             pool->pages_nr--;
0552             spin_unlock(&pool->lock);
0553             return 0;
0554         } else if (zhdr->first_chunks == 0 ||
0555                 zhdr->last_chunks == 0) {
0556             /* add to unbuddied list */
0557             freechunks = num_free_chunks(zhdr);
0558             list_add(&zhdr->buddy, &pool->unbuddied[freechunks]);
0559         } else {
0560             /* add to buddied list */
0561             list_add(&zhdr->buddy, &pool->buddied);
0562         }
0563 
0564         /* add to beginning of LRU */
0565         list_add(&zhdr->lru, &pool->lru);
0566     }
0567     spin_unlock(&pool->lock);
0568     return -EAGAIN;
0569 }
0570 
0571 /**
0572  * zbud_map() - maps the allocation associated with the given handle
0573  * @pool:   pool in which the allocation resides
0574  * @handle: handle associated with the allocation to be mapped
0575  *
0576  * While trivial for zbud, the mapping functions for others allocators
0577  * implementing this allocation API could have more complex information encoded
0578  * in the handle and could create temporary mappings to make the data
0579  * accessible to the user.
0580  *
0581  * Returns: a pointer to the mapped allocation
0582  */
0583 void *zbud_map(struct zbud_pool *pool, unsigned long handle)
0584 {
0585     return (void *)(handle);
0586 }
0587 
0588 /**
0589  * zbud_unmap() - maps the allocation associated with the given handle
0590  * @pool:   pool in which the allocation resides
0591  * @handle: handle associated with the allocation to be unmapped
0592  */
0593 void zbud_unmap(struct zbud_pool *pool, unsigned long handle)
0594 {
0595 }
0596 
0597 /**
0598  * zbud_get_pool_size() - gets the zbud pool size in pages
0599  * @pool:   pool whose size is being queried
0600  *
0601  * Returns: size in pages of the given pool.  The pool lock need not be
0602  * taken to access pages_nr.
0603  */
0604 u64 zbud_get_pool_size(struct zbud_pool *pool)
0605 {
0606     return pool->pages_nr;
0607 }
0608 
0609 static int __init init_zbud(void)
0610 {
0611     /* Make sure the zbud header will fit in one chunk */
0612     BUILD_BUG_ON(sizeof(struct zbud_header) > ZHDR_SIZE_ALIGNED);
0613     pr_info("loaded\n");
0614 
0615 #ifdef CONFIG_ZPOOL
0616     zpool_register_driver(&zbud_zpool_driver);
0617 #endif
0618 
0619     return 0;
0620 }
0621 
0622 static void __exit exit_zbud(void)
0623 {
0624 #ifdef CONFIG_ZPOOL
0625     zpool_unregister_driver(&zbud_zpool_driver);
0626 #endif
0627 
0628     pr_info("unloaded\n");
0629 }
0630 
0631 module_init(init_zbud);
0632 module_exit(exit_zbud);
0633 
0634 MODULE_LICENSE("GPL");
0635 MODULE_AUTHOR("Seth Jennings <sjennings@variantweb.net>");
0636 MODULE_DESCRIPTION("Buddy Allocator for Compressed Pages");