drivers/staging/zram/xvmalloc.c

   1 /*
   2  * xvmalloc memory allocator
   3  *
   4  * Copyright (C) 2008, 2009, 2010  Nitin Gupta
   5  *
   6  * This code is released using a dual license strategy: BSD/GPL
   7  * You can choose the licence that better fits your requirements.
   8  *
   9  * Released under the terms of 3-clause BSD License
  10  * Released under the terms of GNU General Public License Version 2.0
  11  */
  12
  13 #ifdef CONFIG_ZRAM_DEBUG
  14 #define DEBUG
  15 #endif
  16
  17 #include <linux/module.h>
  18 #include <linux/kernel.h>
  19 #include <linux/bitops.h>
  20 #include <linux/errno.h>
  21 #include <linux/highmem.h>
  22 #include <linux/init.h>
  23 #include <linux/string.h>
  24 #include <linux/slab.h>
  25
  26 #include "xvmalloc.h"
  27 #include "xvmalloc_int.h"
  28
  29 static void stat_inc(u64 *value)
  30 {
  31         *value = *value + 1;
  32 }
  33
  34 static void stat_dec(u64 *value)
  35 {
  36         *value = *value - 1;
  37 }
  38
  39 static int test_flag(struct block_header *block, enum blockflags flag)
  40 {
  41         return block->prev & BIT(flag);
  42 }
  43
  44 static void set_flag(struct block_header *block, enum blockflags flag)
  45 {
  46         block->prev |= BIT(flag);
  47 }
  48
  49 static void clear_flag(struct block_header *block, enum blockflags flag)
  50 {
  51         block->prev &= ~BIT(flag);
  52 }
  53
  54 /*
  55  * Given <page, offset> pair, provide a dereferencable pointer.
  56  * This is called from xv_malloc/xv_free path, so it
  57  * needs to be fast.
  58  */
  59 static void *get_ptr_atomic(struct page *page, u16 offset, enum km_type type)
  60 {
  61         unsigned char *base;
  62
  63         base = kmap_atomic(page, type);
  64         return base + offset;
  65 }
  66
  67 static void put_ptr_atomic(void *ptr, enum km_type type)
  68 {
  69         kunmap_atomic(ptr, type);
  70 }
  71
  72 static u32 get_blockprev(struct block_header *block)
  73 {
  74         return block->prev & PREV_MASK;
  75 }
  76
  77 static void set_blockprev(struct block_header *block, u16 new_offset)
  78 {
  79         block->prev = new_offset | (block->prev & FLAGS_MASK);
  80 }
  81
  82 static struct block_header *BLOCK_NEXT(struct block_header *block)
  83 {
  84         return (struct block_header *)
  85                 ((char *)block + block->size + XV_ALIGN);
  86 }
  87
  88 /*
  89  * Get index of free list containing blocks of maximum size
  90  * which is less than or equal to given size.
  91  */
  92 static u32 get_index_for_insert(u32 size)
  93 {
  94         if (unlikely(size > XV_MAX_ALLOC_SIZE))
  95                 size = XV_MAX_ALLOC_SIZE;
  96         size &= ~FL_DELTA_MASK;
  97         return (size - XV_MIN_ALLOC_SIZE) >> FL_DELTA_SHIFT;
  98 }
  99
 100 /*
 101  * Get index of free list having blocks of size greater than
 102  * or equal to requested size.
 103  */
 104 static u32 get_index(u32 size)
 105 {
 106         if (unlikely(size < XV_MIN_ALLOC_SIZE))
 107                 size = XV_MIN_ALLOC_SIZE;
 108         size = ALIGN(size, FL_DELTA);
 109         return (size - XV_MIN_ALLOC_SIZE) >> FL_DELTA_SHIFT;
 110 }
 111
 112 /**
 113  * find_block - find block of at least given size
 114  * @pool: memory pool to search from
 115  * @size: size of block required
 116  * @page: page containing required block
 117  * @offset: offset within the page where block is located.
 118  *
 119  * Searches two level bitmap to locate block of at least
 120  * the given size. If such a block is found, it provides
 121  * <page, offset> to identify this block and returns index
 122  * in freelist where we found this block.
 123  * Otherwise, returns 0 and <page, offset> params are not touched.
 124  */
 125 static u32 find_block(struct xv_pool *pool, u32 size,
 126                         struct page **page, u32 *offset)
 127 {
 128         ulong flbitmap, slbitmap;
 129         u32 flindex, slindex, slbitstart;
 130
 131         /* There are no free blocks in this pool */
 132         if (!pool->flbitmap)
 133                 return 0;
 134
 135         /* Get freelist index correspoding to this size */
 136         slindex = get_index(size);
 137         slbitmap = pool->slbitmap[slindex / BITS_PER_LONG];
 138         slbitstart = slindex % BITS_PER_LONG;
 139
 140         /*
 141          * If freelist is not empty at this index, we found the
 142          * block - head of this list. This is approximate best-fit match.
 143          */
 144         if (test_bit(slbitstart, &slbitmap)) {
 145                 *page = pool->freelist[slindex].page;
 146                 *offset = pool->freelist[slindex].offset;
 147                 return slindex;
 148         }
 149
 150         /*
 151          * No best-fit found. Search a bit further in bitmap for a free block.
 152          * Second level bitmap consists of series of 32-bit chunks. Search
 153          * further in the chunk where we expected a best-fit, starting from
 154          * index location found above.
 155          */
 156         slbitstart++;
 157         slbitmap >>= slbitstart;
 158
 159         /* Skip this search if we were already at end of this bitmap chunk */
 160         if ((slbitstart != BITS_PER_LONG) && slbitmap) {
 161                 slindex += __ffs(slbitmap) + 1;
 162                 *page = pool->freelist[slindex].page;
 163                 *offset = pool->freelist[slindex].offset;
 164                 return slindex;
 165         }
 166
 167         /* Now do a full two-level bitmap search to find next nearest fit */
 168         flindex = slindex / BITS_PER_LONG;
 169
 170         flbitmap = (pool->flbitmap) >> (flindex + 1);
 171         if (!flbitmap)
 172                 return 0;
 173
 174         flindex += __ffs(flbitmap) + 1;
 175         slbitmap = pool->slbitmap[flindex];
 176         slindex = (flindex * BITS_PER_LONG) + __ffs(slbitmap);
 177         *page = pool->freelist[slindex].page;
 178         *offset = pool->freelist[slindex].offset;
 179
 180         return slindex;
 181 }
 182
 183 /*
 184  * Insert block at <page, offset> in freelist of given pool.
 185  * freelist used depends on block size.
 186  */
 187 static void insert_block(struct xv_pool *pool, struct page *page, u32 offset,
 188                         struct block_header *block)
 189 {
 190         u32 flindex, slindex;
 191         struct block_header *nextblock;
 192
 193         slindex = get_index_for_insert(block->size);
 194         flindex = slindex / BITS_PER_LONG;
 195
 196         block->link.prev_page = NULL;
 197         block->link.prev_offset = 0;
 198         block->link.next_page = pool->freelist[slindex].page;
 199         block->link.next_offset = pool->freelist[slindex].offset;
 200         pool->freelist[slindex].page = page;
 201         pool->freelist[slindex].offset = offset;
 202
 203         if (block->link.next_page) {
 204                 nextblock = get_ptr_atomic(block->link.next_page,
 205                                         block->link.next_offset, KM_USER1);
 206                 nextblock->link.prev_page = page;
 207                 nextblock->link.prev_offset = offset;
 208                 put_ptr_atomic(nextblock, KM_USER1);
 209                 /* If there was a next page then the free bits are set. */
 210                 return;
 211         }
 212
 213         __set_bit(slindex % BITS_PER_LONG, &pool->slbitmap[flindex]);
 214         __set_bit(flindex, &pool->flbitmap);
 215 }
 216
 217 /*
 218  * Remove block from freelist. Index 'slindex' identifies the freelist.
 219  */
 220 static void remove_block(struct xv_pool *pool, struct page *page, u32 offset,
 221                         struct block_header *block, u32 slindex)
 222 {
 223         u32 flindex = slindex / BITS_PER_LONG;
 224         struct block_header *tmpblock;
 225
 226         if (block->link.prev_page) {
 227                 tmpblock = get_ptr_atomic(block->link.prev_page,
 228                                 block->link.prev_offset, KM_USER1);
 229                 tmpblock->link.next_page = block->link.next_page;
 230                 tmpblock->link.next_offset = block->link.next_offset;
 231                 put_ptr_atomic(tmpblock, KM_USER1);
 232         }
 233
 234         if (block->link.next_page) {
 235                 tmpblock = get_ptr_atomic(block->link.next_page,
 236                                 block->link.next_offset, KM_USER1);
 237                 tmpblock->link.prev_page = block->link.prev_page;
 238                 tmpblock->link.prev_offset = block->link.prev_offset;
 239                 put_ptr_atomic(tmpblock, KM_USER1);
 240         }
 241
 242         /* Is this block is at the head of the freelist? */
 243         if (pool->freelist[slindex].page == page
 244            && pool->freelist[slindex].offset == offset) {
 245
 246                 pool->freelist[slindex].page = block->link.next_page;
 247                 pool->freelist[slindex].offset = block->link.next_offset;
 248
 249                 if (pool->freelist[slindex].page) {
 250                         struct block_header *tmpblock;
 251                         tmpblock = get_ptr_atomic(pool->freelist[slindex].page,
 252                                         pool->freelist[slindex].offset,
 253                                         KM_USER1);
 254                         tmpblock->link.prev_page = NULL;
 255                         tmpblock->link.prev_offset = 0;
 256                         put_ptr_atomic(tmpblock, KM_USER1);
 257                 } else {
 258                         /* This freelist bucket is empty */
 259                         __clear_bit(slindex % BITS_PER_LONG,
 260                                     &pool->slbitmap[flindex]);
 261                         if (!pool->slbitmap[flindex])
 262                                 __clear_bit(flindex, &pool->flbitmap);
 263                 }
 264         }
 265
 266         block->link.prev_page = NULL;
 267         block->link.prev_offset = 0;
 268         block->link.next_page = NULL;
 269         block->link.next_offset = 0;
 270 }
 271
 272 /*
 273  * Allocate a page and add it to freelist of given pool.
 274  */
 275 static int grow_pool(struct xv_pool *pool, gfp_t flags)
 276 {
 277         struct page *page;
 278         struct block_header *block;
 279
 280         page = alloc_page(flags);
 281         if (unlikely(!page))
 282                 return -ENOMEM;
 283
 284         stat_inc(&pool->total_pages);
 285
 286         spin_lock(&pool->lock);
 287         block = get_ptr_atomic(page, 0, KM_USER0);
 288
 289         block->size = PAGE_SIZE - XV_ALIGN;
 290         set_flag(block, BLOCK_FREE);
 291         clear_flag(block, PREV_FREE);
 292         set_blockprev(block, 0);
 293
 294         insert_block(pool, page, 0, block);
 295
 296         put_ptr_atomic(block, KM_USER0);
 297         spin_unlock(&pool->lock);
 298
 299         return 0;
 300 }
 301
 302 /*
 303  * Create a memory pool. Allocates freelist, bitmaps and other
 304  * per-pool metadata.
 305  */
 306 struct xv_pool *xv_create_pool(void)
 307 {
 308         u32 ovhd_size;
 309         struct xv_pool *pool;
 310
 311         ovhd_size = roundup(sizeof(*pool), PAGE_SIZE);
 312         pool = kzalloc(ovhd_size, GFP_KERNEL);
 313         if (!pool)
 314                 return NULL;
 315
 316         spin_lock_init(&pool->lock);
 317
 318         return pool;
 319 }
 320 EXPORT_SYMBOL_GPL(xv_create_pool);
 321
 322 void xv_destroy_pool(struct xv_pool *pool)
 323 {
 324         kfree(pool);
 325 }
 326 EXPORT_SYMBOL_GPL(xv_destroy_pool);
 327
 328 /**
 329  * xv_malloc - Allocate block of given size from pool.
 330  * @pool: pool to allocate from
 331  * @size: size of block to allocate
 332  * @page: page no. that holds the object
 333  * @offset: location of object within page
 334  *
 335  * On success, <page, offset> identifies block allocated
 336  * and 0 is returned. On failure, <page, offset> is set to
 337  * 0 and -ENOMEM is returned.
 338  *
 339  * Allocation requests with size > XV_MAX_ALLOC_SIZE will fail.
 340  */
 341 int xv_malloc(struct xv_pool *pool, u32 size, struct page **page,
 342                 u32 *offset, gfp_t flags)
 343 {
 344         int error;
 345         u32 index, tmpsize, origsize, tmpoffset;
 346         struct block_header *block, *tmpblock;
 347
 348         *page = NULL;
 349         *offset = 0;
 350         origsize = size;
 351
 352         if (unlikely(!size || size > XV_MAX_ALLOC_SIZE))
 353                 return -ENOMEM;
 354
 355         size = ALIGN(size, XV_ALIGN);
 356
 357         spin_lock(&pool->lock);
 358
 359         index = find_block(pool, size, page, offset);
 360
 361         if (!*page) {
 362                 spin_unlock(&pool->lock);
 363                 if (flags & GFP_NOWAIT)
 364                         return -ENOMEM;
 365                 error = grow_pool(pool, flags);
 366                 if (unlikely(error))
 367                         return error;
 368
 369                 spin_lock(&pool->lock);
 370                 index = find_block(pool, size, page, offset);
 371         }
 372
 373         if (!*page) {
 374                 spin_unlock(&pool->lock);
 375                 return -ENOMEM;
 376         }
 377
 378         block = get_ptr_atomic(*page, *offset, KM_USER0);
 379
 380         remove_block(pool, *page, *offset, block, index);
 381
 382         /* Split the block if required */
 383         tmpoffset = *offset + size + XV_ALIGN;
 384         tmpsize = block->size - size;
 385         tmpblock = (struct block_header *)((char *)block + size + XV_ALIGN);
 386         if (tmpsize) {
 387                 tmpblock->size = tmpsize - XV_ALIGN;
 388                 set_flag(tmpblock, BLOCK_FREE);
 389                 clear_flag(tmpblock, PREV_FREE);
 390
 391                 set_blockprev(tmpblock, *offset);
 392                 if (tmpblock->size >= XV_MIN_ALLOC_SIZE)
 393                         insert_block(pool, *page, tmpoffset, tmpblock);
 394
 395                 if (tmpoffset + XV_ALIGN + tmpblock->size != PAGE_SIZE) {
 396                         tmpblock = BLOCK_NEXT(tmpblock);
 397                         set_blockprev(tmpblock, tmpoffset);
 398                 }
 399         } else {
 400                 /* This block is exact fit */
 401                 if (tmpoffset != PAGE_SIZE)
 402                         clear_flag(tmpblock, PREV_FREE);
 403         }
 404
 405         block->size = origsize;
 406         clear_flag(block, BLOCK_FREE);
 407
 408         put_ptr_atomic(block, KM_USER0);
 409         spin_unlock(&pool->lock);
 410
 411         *offset += XV_ALIGN;
 412
 413         return 0;
 414 }
 415 EXPORT_SYMBOL_GPL(xv_malloc);
 416
 417 /*
 418  * Free block identified with <page, offset>
 419  */
 420 void xv_free(struct xv_pool *pool, struct page *page, u32 offset)
 421 {
 422         void *page_start;
 423         struct block_header *block, *tmpblock;
 424
 425         offset -= XV_ALIGN;
 426
 427         spin_lock(&pool->lock);
 428
 429         page_start = get_ptr_atomic(page, 0, KM_USER0);
 430         block = (struct block_header *)((char *)page_start + offset);
 431
 432         /* Catch double free bugs */
 433         BUG_ON(test_flag(block, BLOCK_FREE));
 434
 435         block->size = ALIGN(block->size, XV_ALIGN);
 436
 437         tmpblock = BLOCK_NEXT(block);
 438         if (offset + block->size + XV_ALIGN == PAGE_SIZE)
 439                 tmpblock = NULL;
 440
 441         /* Merge next block if its free */
 442         if (tmpblock && test_flag(tmpblock, BLOCK_FREE)) {
 443                 /*
 444                  * Blocks smaller than XV_MIN_ALLOC_SIZE
 445                  * are not inserted in any free list.
 446                  */
 447                 if (tmpblock->size >= XV_MIN_ALLOC_SIZE) {
 448                         remove_block(pool, page,
 449                                     offset + block->size + XV_ALIGN, tmpblock,
 450                                     get_index_for_insert(tmpblock->size));
 451                 }
 452                 block->size += tmpblock->size + XV_ALIGN;
 453         }
 454
 455         /* Merge previous block if its free */
 456         if (test_flag(block, PREV_FREE)) {
 457                 tmpblock = (struct block_header *)((char *)(page_start) +
 458                                                 get_blockprev(block));
 459                 offset = offset - tmpblock->size - XV_ALIGN;
 460
 461                 if (tmpblock->size >= XV_MIN_ALLOC_SIZE)
 462                         remove_block(pool, page, offset, tmpblock,
 463                                     get_index_for_insert(tmpblock->size));
 464
 465                 tmpblock->size += block->size + XV_ALIGN;
 466                 block = tmpblock;
 467         }
 468
 469         /* No used objects in this page. Free it. */
 470         if (block->size == PAGE_SIZE - XV_ALIGN) {
 471                 put_ptr_atomic(page_start, KM_USER0);
 472                 spin_unlock(&pool->lock);
 473
 474                 __free_page(page);
 475                 stat_dec(&pool->total_pages);
 476                 return;
 477         }
 478
 479         set_flag(block, BLOCK_FREE);
 480         if (block->size >= XV_MIN_ALLOC_SIZE)
 481                 insert_block(pool, page, offset, block);
 482
 483         if (offset + block->size + XV_ALIGN != PAGE_SIZE) {
 484                 tmpblock = BLOCK_NEXT(block);
 485                 set_flag(tmpblock, PREV_FREE);
 486                 set_blockprev(tmpblock, offset);
 487         }
 488
 489         put_ptr_atomic(page_start, KM_USER0);
 490         spin_unlock(&pool->lock);
 491 }
 492 EXPORT_SYMBOL_GPL(xv_free);
 493
 494 u32 xv_get_object_size(void *obj)
 495 {
 496         struct block_header *blk;
 497
 498         blk = (struct block_header *)((char *)(obj) - XV_ALIGN);
 499         return blk->size;
 500 }
 501 EXPORT_SYMBOL_GPL(xv_get_object_size);
 502
 503 /*
 504  * Returns total memory used by allocator (userdata + metadata)
 505  */
 506 u64 xv_get_total_size_bytes(struct xv_pool *pool)
 507 {
 508         return pool->total_pages << PAGE_SHIFT;
 509 }
 510 EXPORT_SYMBOL_GPL(xv_get_total_size_bytes);