lib/genalloc.c

   1 /*
   2  * Basic general purpose allocator for managing special purpose
   3  * memory, for example, memory that is not managed by the regular
   4  * kmalloc/kfree interface.  Uses for this includes on-device special
   5  * memory, uncached memory etc.
   6  *
   7  * It is safe to use the allocator in NMI handlers and other special
   8  * unblockable contexts that could otherwise deadlock on locks.  This
   9  * is implemented by using atomic operations and retries on any
  10  * conflicts.  The disadvantage is that there may be livelocks in
  11  * extreme cases.  For better scalability, one allocator can be used
  12  * for each CPU.
  13  *
  14  * The lockless operation only works if there is enough memory
  15  * available.  If new memory is added to the pool a lock has to be
  16  * still taken.  So any user relying on locklessness has to ensure
  17  * that sufficient memory is preallocated.
  18  *
  19  * The basic atomic operation of this allocator is cmpxchg on long.
  20  * On architectures that don't have NMI-safe cmpxchg implementation,
  21  * the allocator can NOT be used in NMI handler.  So code uses the
  22  * allocator in NMI handler should depend on
  23  * CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
  24  *
  25  * Copyright 2005 (C) Jes Sorensen <jes@trained-monkey.org>
  26  *
  27  * This source code is licensed under the GNU General Public License,
  28  * Version 2.  See the file COPYING for more details.
  29  */
  30
  31 #include <linux/slab.h>
  32 #include <linux/export.h>
  33 #include <linux/bitmap.h>
  34 #include <linux/rculist.h>
  35 #include <linux/interrupt.h>
  36 #include <linux/genalloc.h>
  37
  38 static int set_bits_ll(unsigned long *addr, unsigned long mask_to_set)
  39 {
  40         unsigned long val, nval;
  41
  42         nval = *addr;
  43         do {
  44                 val = nval;
  45                 if (val & mask_to_set)
  46                         return -EBUSY;
  47                 cpu_relax();
  48         } while ((nval = cmpxchg(addr, val, val | mask_to_set)) != val);
  49
  50         return 0;
  51 }
  52
  53 static int clear_bits_ll(unsigned long *addr, unsigned long mask_to_clear)
  54 {
  55         unsigned long val, nval;
  56
  57         nval = *addr;
  58         do {
  59                 val = nval;
  60                 if ((val & mask_to_clear) != mask_to_clear)
  61                         return -EBUSY;
  62                 cpu_relax();
  63         } while ((nval = cmpxchg(addr, val, val & ~mask_to_clear)) != val);
  64
  65         return 0;
  66 }
  67
  68 /*
  69  * bitmap_set_ll - set the specified number of bits at the specified position
  70  * @map: pointer to a bitmap
  71  * @start: a bit position in @map
  72  * @nr: number of bits to set
  73  *
  74  * Set @nr bits start from @start in @map lock-lessly. Several users
  75  * can set/clear the same bitmap simultaneously without lock. If two
  76  * users set the same bit, one user will return remain bits, otherwise
  77  * return 0.
  78  */
  79 static int bitmap_set_ll(unsigned long *map, int start, int nr)
  80 {
  81         unsigned long *p = map + BIT_WORD(start);
  82         const int size = start + nr;
  83         int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
  84         unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
  85
  86         while (nr - bits_to_set >= 0) {
  87                 if (set_bits_ll(p, mask_to_set))
  88                         return nr;
  89                 nr -= bits_to_set;
  90                 bits_to_set = BITS_PER_LONG;
  91                 mask_to_set = ~0UL;
  92                 p++;
  93         }
  94         if (nr) {
  95                 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
  96                 if (set_bits_ll(p, mask_to_set))
  97                         return nr;
  98         }
  99
 100         return 0;
 101 }
 102
 103 /*
 104  * bitmap_clear_ll - clear the specified number of bits at the specified position
 105  * @map: pointer to a bitmap
 106  * @start: a bit position in @map
 107  * @nr: number of bits to set
 108  *
 109  * Clear @nr bits start from @start in @map lock-lessly. Several users
 110  * can set/clear the same bitmap simultaneously without lock. If two
 111  * users clear the same bit, one user will return remain bits,
 112  * otherwise return 0.
 113  */
 114 static int bitmap_clear_ll(unsigned long *map, int start, int nr)
 115 {
 116         unsigned long *p = map + BIT_WORD(start);
 117         const int size = start + nr;
 118         int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
 119         unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 120
 121         while (nr - bits_to_clear >= 0) {
 122                 if (clear_bits_ll(p, mask_to_clear))
 123                         return nr;
 124                 nr -= bits_to_clear;
 125                 bits_to_clear = BITS_PER_LONG;
 126                 mask_to_clear = ~0UL;
 127                 p++;
 128         }
 129         if (nr) {
 130                 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
 131                 if (clear_bits_ll(p, mask_to_clear))
 132                         return nr;
 133         }
 134
 135         return 0;
 136 }
 137
 138 /**
 139  * gen_pool_create - create a new special memory pool
 140  * @min_alloc_order: log base 2 of number of bytes each bitmap bit represents
 141  * @nid: node id of the node the pool structure should be allocated on, or -1
 142  *
 143  * Create a new special memory pool that can be used to manage special purpose
 144  * memory not managed by the regular kmalloc/kfree interface.
 145  */
 146 struct gen_pool *gen_pool_create(int min_alloc_order, int nid)
 147 {
 148         struct gen_pool *pool;
 149
 150         pool = kmalloc_node(sizeof(struct gen_pool), GFP_KERNEL, nid);
 151         if (pool != NULL) {
 152                 spin_lock_init(&pool->lock);
 153                 INIT_LIST_HEAD(&pool->chunks);
 154                 pool->min_alloc_order = min_alloc_order;
 155                 pool->algo = gen_pool_first_fit;
 156                 pool->data = NULL;
 157         }
 158         return pool;
 159 }
 160 EXPORT_SYMBOL(gen_pool_create);
 161
 162 /**
 163  * gen_pool_add_virt - add a new chunk of special memory to the pool
 164  * @pool: pool to add new memory chunk to
 165  * @virt: virtual starting address of memory chunk to add to pool
 166  * @phys: physical starting address of memory chunk to add to pool
 167  * @size: size in bytes of the memory chunk to add to pool
 168  * @nid: node id of the node the chunk structure and bitmap should be
 169  *       allocated on, or -1
 170  *
 171  * Add a new chunk of special memory to the specified pool.
 172  *
 173  * Returns 0 on success or a -ve errno on failure.
 174  */
 175 int gen_pool_add_virt(struct gen_pool *pool, unsigned long virt, phys_addr_t phys,
 176                  size_t size, int nid)
 177 {
 178         struct gen_pool_chunk *chunk;
 179         int nbits = size >> pool->min_alloc_order;
 180         int nbytes = sizeof(struct gen_pool_chunk) +
 181                                 (nbits + BITS_PER_BYTE - 1) / BITS_PER_BYTE;
 182
 183         chunk = kmalloc_node(nbytes, GFP_KERNEL | __GFP_ZERO, nid);
 184         if (unlikely(chunk == NULL))
 185                 return -ENOMEM;
 186
 187         chunk->phys_addr = phys;
 188         chunk->start_addr = virt;
 189         chunk->end_addr = virt + size;
 190         atomic_set(&chunk->avail, size);
 191
 192         spin_lock(&pool->lock);
 193         list_add_rcu(&chunk->next_chunk, &pool->chunks);
 194         spin_unlock(&pool->lock);
 195
 196         return 0;
 197 }
 198 EXPORT_SYMBOL(gen_pool_add_virt);
 199
 200 /**
 201  * gen_pool_virt_to_phys - return the physical address of memory
 202  * @pool: pool to allocate from
 203  * @addr: starting address of memory
 204  *
 205  * Returns the physical address on success, or -1 on error.
 206  */
 207 phys_addr_t gen_pool_virt_to_phys(struct gen_pool *pool, unsigned long addr)
 208 {
 209         struct gen_pool_chunk *chunk;
 210         phys_addr_t paddr = -1;
 211
 212         rcu_read_lock();
 213         list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) {
 214                 if (addr >= chunk->start_addr && addr < chunk->end_addr) {
 215                         paddr = chunk->phys_addr + (addr - chunk->start_addr);
 216                         break;
 217                 }
 218         }
 219         rcu_read_unlock();
 220
 221         return paddr;
 222 }
 223 EXPORT_SYMBOL(gen_pool_virt_to_phys);
 224
 225 /**
 226  * gen_pool_destroy - destroy a special memory pool
 227  * @pool: pool to destroy
 228  *
 229  * Destroy the specified special memory pool. Verifies that there are no
 230  * outstanding allocations.
 231  */
 232 void gen_pool_destroy(struct gen_pool *pool)
 233 {
 234         struct list_head *_chunk, *_next_chunk;
 235         struct gen_pool_chunk *chunk;
 236         int order = pool->min_alloc_order;
 237         int bit, end_bit;
 238
 239         list_for_each_safe(_chunk, _next_chunk, &pool->chunks) {
 240                 chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk);
 241                 list_del(&chunk->next_chunk);
 242
 243                 end_bit = (chunk->end_addr - chunk->start_addr) >> order;
 244                 bit = find_next_bit(chunk->bits, end_bit, 0);
 245                 BUG_ON(bit < end_bit);
 246
 247                 kfree(chunk);
 248         }
 249         kfree(pool);
 250         return;
 251 }
 252 EXPORT_SYMBOL(gen_pool_destroy);
 253
 254 /**
 255  * gen_pool_alloc - allocate special memory from the pool
 256  * @pool: pool to allocate from
 257  * @size: number of bytes to allocate from the pool
 258  *
 259  * Allocate the requested number of bytes from the specified pool.
 260  * Uses the pool allocation function (with first-fit algorithm by default).
 261  * Can not be used in NMI handler on architectures without
 262  * NMI-safe cmpxchg implementation.
 263  */
 264 unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size)
 265 {
 266         struct gen_pool_chunk *chunk;
 267         unsigned long addr = 0;
 268         int order = pool->min_alloc_order;
 269         int nbits, start_bit = 0, end_bit, remain;
 270
 271 #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
 272         BUG_ON(in_nmi());
 273 #endif
 274
 275         if (size == 0)
 276                 return 0;
 277
 278         nbits = (size + (1UL << order) - 1) >> order;
 279         rcu_read_lock();
 280         list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) {
 281                 if (size > atomic_read(&chunk->avail))
 282                         continue;
 283
 284                 end_bit = (chunk->end_addr - chunk->start_addr) >> order;
 285 retry:
 286                 start_bit = pool->algo(chunk->bits, end_bit, start_bit, nbits,
 287                                 pool->data);
 288                 if (start_bit >= end_bit)
 289                         continue;
 290                 remain = bitmap_set_ll(chunk->bits, start_bit, nbits);
 291                 if (remain) {
 292                         remain = bitmap_clear_ll(chunk->bits, start_bit,
 293                                                  nbits - remain);
 294                         BUG_ON(remain);
 295                         goto retry;
 296                 }
 297
 298                 addr = chunk->start_addr + ((unsigned long)start_bit << order);
 299                 size = nbits << order;
 300                 atomic_sub(size, &chunk->avail);
 301                 break;
 302         }
 303         rcu_read_unlock();
 304         return addr;
 305 }
 306 EXPORT_SYMBOL(gen_pool_alloc);
 307
 308 /**
 309  * gen_pool_free - free allocated special memory back to the pool
 310  * @pool: pool to free to
 311  * @addr: starting address of memory to free back to pool
 312  * @size: size in bytes of memory to free
 313  *
 314  * Free previously allocated special memory back to the specified
 315  * pool.  Can not be used in NMI handler on architectures without
 316  * NMI-safe cmpxchg implementation.
 317  */
 318 void gen_pool_free(struct gen_pool *pool, unsigned long addr, size_t size)
 319 {
 320         struct gen_pool_chunk *chunk;
 321         int order = pool->min_alloc_order;
 322         int start_bit, nbits, remain;
 323
 324 #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
 325         BUG_ON(in_nmi());
 326 #endif
 327
 328         nbits = (size + (1UL << order) - 1) >> order;
 329         rcu_read_lock();
 330         list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) {
 331                 if (addr >= chunk->start_addr && addr < chunk->end_addr) {
 332                         BUG_ON(addr + size > chunk->end_addr);
 333                         start_bit = (addr - chunk->start_addr) >> order;
 334                         remain = bitmap_clear_ll(chunk->bits, start_bit, nbits);
 335                         BUG_ON(remain);
 336                         size = nbits << order;
 337                         atomic_add(size, &chunk->avail);
 338                         rcu_read_unlock();
 339                         return;
 340                 }
 341         }
 342         rcu_read_unlock();
 343         BUG();
 344 }
 345 EXPORT_SYMBOL(gen_pool_free);
 346
 347 /**
 348  * gen_pool_for_each_chunk - call func for every chunk of generic memory pool
 349  * @pool:       the generic memory pool
 350  * @func:       func to call
 351  * @data:       additional data used by @func
 352  *
 353  * Call @func for every chunk of generic memory pool.  The @func is
 354  * called with rcu_read_lock held.
 355  */
 356 void gen_pool_for_each_chunk(struct gen_pool *pool,
 357         void (*func)(struct gen_pool *pool, struct gen_pool_chunk *chunk, void *data),
 358         void *data)
 359 {
 360         struct gen_pool_chunk *chunk;
 361
 362         rcu_read_lock();
 363         list_for_each_entry_rcu(chunk, &(pool)->chunks, next_chunk)
 364                 func(pool, chunk, data);
 365         rcu_read_unlock();
 366 }
 367 EXPORT_SYMBOL(gen_pool_for_each_chunk);
 368
 369 /**
 370  * gen_pool_avail - get available free space of the pool
 371  * @pool: pool to get available free space
 372  *
 373  * Return available free space of the specified pool.
 374  */
 375 size_t gen_pool_avail(struct gen_pool *pool)
 376 {
 377         struct gen_pool_chunk *chunk;
 378         size_t avail = 0;
 379
 380         rcu_read_lock();
 381         list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk)
 382                 avail += atomic_read(&chunk->avail);
 383         rcu_read_unlock();
 384         return avail;
 385 }
 386 EXPORT_SYMBOL_GPL(gen_pool_avail);
 387
 388 /**
 389  * gen_pool_size - get size in bytes of memory managed by the pool
 390  * @pool: pool to get size
 391  *
 392  * Return size in bytes of memory managed by the pool.
 393  */
 394 size_t gen_pool_size(struct gen_pool *pool)
 395 {
 396         struct gen_pool_chunk *chunk;
 397         size_t size = 0;
 398
 399         rcu_read_lock();
 400         list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk)
 401                 size += chunk->end_addr - chunk->start_addr;
 402         rcu_read_unlock();
 403         return size;
 404 }
 405 EXPORT_SYMBOL_GPL(gen_pool_size);
 406
 407 /**
 408  * gen_pool_set_algo - set the allocation algorithm
 409  * @pool: pool to change allocation algorithm
 410  * @algo: custom algorithm function
 411  * @data: additional data used by @algo
 412  *
 413  * Call @algo for each memory allocation in the pool.
 414  * If @algo is NULL use gen_pool_first_fit as default
 415  * memory allocation function.
 416  */
 417 void gen_pool_set_algo(struct gen_pool *pool, genpool_algo_t algo, void *data)
 418 {
 419         rcu_read_lock();
 420
 421         pool->algo = algo;
 422         if (!pool->algo)
 423                 pool->algo = gen_pool_first_fit;
 424
 425         pool->data = data;
 426
 427         rcu_read_unlock();
 428 }
 429 EXPORT_SYMBOL(gen_pool_set_algo);
 430
 431 /**
 432  * gen_pool_first_fit - find the first available region
 433  * of memory matching the size requirement (no alignment constraint)
 434  * @map: The address to base the search on
 435  * @size: The bitmap size in bits
 436  * @start: The bitnumber to start searching at
 437  * @nr: The number of zeroed bits we're looking for
 438  * @data: additional data - unused
 439  */
 440 unsigned long gen_pool_first_fit(unsigned long *map, unsigned long size,
 441                 unsigned long start, unsigned int nr, void *data)
 442 {
 443         return bitmap_find_next_zero_area(map, size, start, nr, 0);
 444 }
 445 EXPORT_SYMBOL(gen_pool_first_fit);
 446
 447 /**
 448  * gen_pool_best_fit - find the best fitting region of memory
 449  * macthing the size requirement (no alignment constraint)
 450  * @map: The address to base the search on
 451  * @size: The bitmap size in bits
 452  * @start: The bitnumber to start searching at
 453  * @nr: The number of zeroed bits we're looking for
 454  * @data: additional data - unused
 455  *
 456  * Iterate over the bitmap to find the smallest free region
 457  * which we can allocate the memory.
 458  */
 459 unsigned long gen_pool_best_fit(unsigned long *map, unsigned long size,
 460                 unsigned long start, unsigned int nr, void *data)
 461 {
 462         unsigned long start_bit = size;
 463         unsigned long len = size + 1;
 464         unsigned long index;
 465
 466         index = bitmap_find_next_zero_area(map, size, start, nr, 0);
 467
 468         while (index < size) {
 469                 int next_bit = find_next_bit(map, size, index + nr);
 470                 if ((next_bit - index) < len) {
 471                         len = next_bit - index;
 472                         start_bit = index;
 473                         if (len == nr)
 474                                 return start_bit;
 475                 }
 476                 index = bitmap_find_next_zero_area(map, size,
 477                                                    next_bit + 1, nr, 0);
 478         }
 479
 480         return start_bit;
 481 }
 482 EXPORT_SYMBOL(gen_pool_best_fit);