mm/z3fold.c

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