genalloc.c 5.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198
  1. /*
  2. * Basic general purpose allocator for managing special purpose memory
  3. * not managed by the regular kmalloc/kfree interface.
  4. * Uses for this includes on-device special memory, uncached memory
  5. * etc.
  6. *
  7. * Copyright 2005 (C) Jes Sorensen <jes@trained-monkey.org>
  8. *
  9. * This source code is licensed under the GNU General Public License,
  10. * Version 2. See the file COPYING for more details.
  11. */
  12. #include <linux/module.h>
  13. #include <linux/genalloc.h>
  14. /**
  15. * gen_pool_create - create a new special memory pool
  16. * @min_alloc_order: log base 2 of number of bytes each bitmap bit represents
  17. * @nid: node id of the node the pool structure should be allocated on, or -1
  18. *
  19. * Create a new special memory pool that can be used to manage special purpose
  20. * memory not managed by the regular kmalloc/kfree interface.
  21. */
  22. struct gen_pool *gen_pool_create(int min_alloc_order, int nid)
  23. {
  24. struct gen_pool *pool;
  25. pool = kmalloc_node(sizeof(struct gen_pool), GFP_KERNEL, nid);
  26. if (pool != NULL) {
  27. rwlock_init(&pool->lock);
  28. INIT_LIST_HEAD(&pool->chunks);
  29. pool->min_alloc_order = min_alloc_order;
  30. }
  31. return pool;
  32. }
  33. EXPORT_SYMBOL(gen_pool_create);
  34. /**
  35. * gen_pool_add - add a new chunk of special memory to the pool
  36. * @pool: pool to add new memory chunk to
  37. * @addr: starting address of memory chunk to add to pool
  38. * @size: size in bytes of the memory chunk to add to pool
  39. * @nid: node id of the node the chunk structure and bitmap should be
  40. * allocated on, or -1
  41. *
  42. * Add a new chunk of special memory to the specified pool.
  43. */
  44. int gen_pool_add(struct gen_pool *pool, unsigned long addr, size_t size,
  45. int nid)
  46. {
  47. struct gen_pool_chunk *chunk;
  48. int nbits = size >> pool->min_alloc_order;
  49. int nbytes = sizeof(struct gen_pool_chunk) +
  50. (nbits + BITS_PER_BYTE - 1) / BITS_PER_BYTE;
  51. chunk = kmalloc_node(nbytes, GFP_KERNEL, nid);
  52. if (unlikely(chunk == NULL))
  53. return -1;
  54. memset(chunk, 0, nbytes);
  55. spin_lock_init(&chunk->lock);
  56. chunk->start_addr = addr;
  57. chunk->end_addr = addr + size;
  58. write_lock(&pool->lock);
  59. list_add(&chunk->next_chunk, &pool->chunks);
  60. write_unlock(&pool->lock);
  61. return 0;
  62. }
  63. EXPORT_SYMBOL(gen_pool_add);
  64. /**
  65. * gen_pool_destroy - destroy a special memory pool
  66. * @pool: pool to destroy
  67. *
  68. * Destroy the specified special memory pool. Verifies that there are no
  69. * outstanding allocations.
  70. */
  71. void gen_pool_destroy(struct gen_pool *pool)
  72. {
  73. struct list_head *_chunk, *_next_chunk;
  74. struct gen_pool_chunk *chunk;
  75. int order = pool->min_alloc_order;
  76. int bit, end_bit;
  77. write_lock(&pool->lock);
  78. list_for_each_safe(_chunk, _next_chunk, &pool->chunks) {
  79. chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk);
  80. list_del(&chunk->next_chunk);
  81. end_bit = (chunk->end_addr - chunk->start_addr) >> order;
  82. bit = find_next_bit(chunk->bits, end_bit, 0);
  83. BUG_ON(bit < end_bit);
  84. kfree(chunk);
  85. }
  86. kfree(pool);
  87. return;
  88. }
  89. EXPORT_SYMBOL(gen_pool_destroy);
  90. /**
  91. * gen_pool_alloc - allocate special memory from the pool
  92. * @pool: pool to allocate from
  93. * @size: number of bytes to allocate from the pool
  94. *
  95. * Allocate the requested number of bytes from the specified pool.
  96. * Uses a first-fit algorithm.
  97. */
  98. unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size)
  99. {
  100. struct list_head *_chunk;
  101. struct gen_pool_chunk *chunk;
  102. unsigned long addr, flags;
  103. int order = pool->min_alloc_order;
  104. int nbits, bit, start_bit, end_bit;
  105. if (size == 0)
  106. return 0;
  107. nbits = (size + (1UL << order) - 1) >> order;
  108. read_lock(&pool->lock);
  109. list_for_each(_chunk, &pool->chunks) {
  110. chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk);
  111. end_bit = (chunk->end_addr - chunk->start_addr) >> order;
  112. end_bit -= nbits + 1;
  113. spin_lock_irqsave(&chunk->lock, flags);
  114. bit = -1;
  115. while (bit + 1 < end_bit) {
  116. bit = find_next_zero_bit(chunk->bits, end_bit, bit + 1);
  117. if (bit >= end_bit)
  118. break;
  119. start_bit = bit;
  120. if (nbits > 1) {
  121. bit = find_next_bit(chunk->bits, bit + nbits,
  122. bit + 1);
  123. if (bit - start_bit < nbits)
  124. continue;
  125. }
  126. addr = chunk->start_addr +
  127. ((unsigned long)start_bit << order);
  128. while (nbits--)
  129. __set_bit(start_bit++, chunk->bits);
  130. spin_unlock_irqrestore(&chunk->lock, flags);
  131. read_unlock(&pool->lock);
  132. return addr;
  133. }
  134. spin_unlock_irqrestore(&chunk->lock, flags);
  135. }
  136. read_unlock(&pool->lock);
  137. return 0;
  138. }
  139. EXPORT_SYMBOL(gen_pool_alloc);
  140. /**
  141. * gen_pool_free - free allocated special memory back to the pool
  142. * @pool: pool to free to
  143. * @addr: starting address of memory to free back to pool
  144. * @size: size in bytes of memory to free
  145. *
  146. * Free previously allocated special memory back to the specified pool.
  147. */
  148. void gen_pool_free(struct gen_pool *pool, unsigned long addr, size_t size)
  149. {
  150. struct list_head *_chunk;
  151. struct gen_pool_chunk *chunk;
  152. unsigned long flags;
  153. int order = pool->min_alloc_order;
  154. int bit, nbits;
  155. nbits = (size + (1UL << order) - 1) >> order;
  156. read_lock(&pool->lock);
  157. list_for_each(_chunk, &pool->chunks) {
  158. chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk);
  159. if (addr >= chunk->start_addr && addr < chunk->end_addr) {
  160. BUG_ON(addr + size > chunk->end_addr);
  161. spin_lock_irqsave(&chunk->lock, flags);
  162. bit = (addr - chunk->start_addr) >> order;
  163. while (nbits--)
  164. __clear_bit(bit++, chunk->bits);
  165. spin_unlock_irqrestore(&chunk->lock, flags);
  166. break;
  167. }
  168. }
  169. BUG_ON(nbits > 0);
  170. read_unlock(&pool->lock);
  171. }
  172. EXPORT_SYMBOL(gen_pool_free);