slob.c 8.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348
  1. /*
  2. * SLOB Allocator: Simple List Of Blocks
  3. *
  4. * Matt Mackall <mpm@selenic.com> 12/30/03
  5. *
  6. * How SLOB works:
  7. *
  8. * The core of SLOB is a traditional K&R style heap allocator, with
  9. * support for returning aligned objects. The granularity of this
  10. * allocator is 8 bytes on x86, though it's perhaps possible to reduce
  11. * this to 4 if it's deemed worth the effort. The slob heap is a
  12. * singly-linked list of pages from __get_free_page, grown on demand
  13. * and allocation from the heap is currently first-fit.
  14. *
  15. * Above this is an implementation of kmalloc/kfree. Blocks returned
  16. * from kmalloc are 8-byte aligned and prepended with a 8-byte header.
  17. * If kmalloc is asked for objects of PAGE_SIZE or larger, it calls
  18. * __get_free_pages directly so that it can return page-aligned blocks
  19. * and keeps a linked list of such pages and their orders. These
  20. * objects are detected in kfree() by their page alignment.
  21. *
  22. * SLAB is emulated on top of SLOB by simply calling constructors and
  23. * destructors for every SLAB allocation. Objects are returned with
  24. * the 8-byte alignment unless the SLAB_MUST_HWCACHE_ALIGN flag is
  25. * set, in which case the low-level allocator will fragment blocks to
  26. * create the proper alignment. Again, objects of page-size or greater
  27. * are allocated by calling __get_free_pages. As SLAB objects know
  28. * their size, no separate size bookkeeping is necessary and there is
  29. * essentially no allocation space overhead.
  30. */
  31. #include <linux/slab.h>
  32. #include <linux/mm.h>
  33. #include <linux/cache.h>
  34. #include <linux/init.h>
  35. #include <linux/module.h>
  36. #include <linux/timer.h>
  37. struct slob_block {
  38. int units;
  39. struct slob_block *next;
  40. };
  41. typedef struct slob_block slob_t;
  42. #define SLOB_UNIT sizeof(slob_t)
  43. #define SLOB_UNITS(size) (((size) + SLOB_UNIT - 1)/SLOB_UNIT)
  44. #define SLOB_ALIGN L1_CACHE_BYTES
  45. struct bigblock {
  46. int order;
  47. void *pages;
  48. struct bigblock *next;
  49. };
  50. typedef struct bigblock bigblock_t;
  51. static slob_t arena = { .next = &arena, .units = 1 };
  52. static slob_t *slobfree = &arena;
  53. static bigblock_t *bigblocks;
  54. static DEFINE_SPINLOCK(slob_lock);
  55. static DEFINE_SPINLOCK(block_lock);
  56. static void slob_free(void *b, int size);
  57. static void slob_timer_cbk(void);
  58. static void *slob_alloc(size_t size, gfp_t gfp, int align)
  59. {
  60. slob_t *prev, *cur, *aligned = 0;
  61. int delta = 0, units = SLOB_UNITS(size);
  62. unsigned long flags;
  63. spin_lock_irqsave(&slob_lock, flags);
  64. prev = slobfree;
  65. for (cur = prev->next; ; prev = cur, cur = cur->next) {
  66. if (align) {
  67. aligned = (slob_t *)ALIGN((unsigned long)cur, align);
  68. delta = aligned - cur;
  69. }
  70. if (cur->units >= units + delta) { /* room enough? */
  71. if (delta) { /* need to fragment head to align? */
  72. aligned->units = cur->units - delta;
  73. aligned->next = cur->next;
  74. cur->next = aligned;
  75. cur->units = delta;
  76. prev = cur;
  77. cur = aligned;
  78. }
  79. if (cur->units == units) /* exact fit? */
  80. prev->next = cur->next; /* unlink */
  81. else { /* fragment */
  82. prev->next = cur + units;
  83. prev->next->units = cur->units - units;
  84. prev->next->next = cur->next;
  85. cur->units = units;
  86. }
  87. slobfree = prev;
  88. spin_unlock_irqrestore(&slob_lock, flags);
  89. return cur;
  90. }
  91. if (cur == slobfree) {
  92. spin_unlock_irqrestore(&slob_lock, flags);
  93. if (size == PAGE_SIZE) /* trying to shrink arena? */
  94. return 0;
  95. cur = (slob_t *)__get_free_page(gfp);
  96. if (!cur)
  97. return 0;
  98. slob_free(cur, PAGE_SIZE);
  99. spin_lock_irqsave(&slob_lock, flags);
  100. cur = slobfree;
  101. }
  102. }
  103. }
  104. static void slob_free(void *block, int size)
  105. {
  106. slob_t *cur, *b = (slob_t *)block;
  107. unsigned long flags;
  108. if (!block)
  109. return;
  110. if (size)
  111. b->units = SLOB_UNITS(size);
  112. /* Find reinsertion point */
  113. spin_lock_irqsave(&slob_lock, flags);
  114. for (cur = slobfree; !(b > cur && b < cur->next); cur = cur->next)
  115. if (cur >= cur->next && (b > cur || b < cur->next))
  116. break;
  117. if (b + b->units == cur->next) {
  118. b->units += cur->next->units;
  119. b->next = cur->next->next;
  120. } else
  121. b->next = cur->next;
  122. if (cur + cur->units == b) {
  123. cur->units += b->units;
  124. cur->next = b->next;
  125. } else
  126. cur->next = b;
  127. slobfree = cur;
  128. spin_unlock_irqrestore(&slob_lock, flags);
  129. }
  130. void *__kmalloc(size_t size, gfp_t gfp)
  131. {
  132. slob_t *m;
  133. bigblock_t *bb;
  134. unsigned long flags;
  135. if (size < PAGE_SIZE - SLOB_UNIT) {
  136. m = slob_alloc(size + SLOB_UNIT, gfp, 0);
  137. return m ? (void *)(m + 1) : 0;
  138. }
  139. bb = slob_alloc(sizeof(bigblock_t), gfp, 0);
  140. if (!bb)
  141. return 0;
  142. bb->order = get_order(size);
  143. bb->pages = (void *)__get_free_pages(gfp, bb->order);
  144. if (bb->pages) {
  145. spin_lock_irqsave(&block_lock, flags);
  146. bb->next = bigblocks;
  147. bigblocks = bb;
  148. spin_unlock_irqrestore(&block_lock, flags);
  149. return bb->pages;
  150. }
  151. slob_free(bb, sizeof(bigblock_t));
  152. return 0;
  153. }
  154. EXPORT_SYMBOL(__kmalloc);
  155. void kfree(const void *block)
  156. {
  157. bigblock_t *bb, **last = &bigblocks;
  158. unsigned long flags;
  159. if (!block)
  160. return;
  161. if (!((unsigned long)block & (PAGE_SIZE-1))) {
  162. /* might be on the big block list */
  163. spin_lock_irqsave(&block_lock, flags);
  164. for (bb = bigblocks; bb; last = &bb->next, bb = bb->next) {
  165. if (bb->pages == block) {
  166. *last = bb->next;
  167. spin_unlock_irqrestore(&block_lock, flags);
  168. free_pages((unsigned long)block, bb->order);
  169. slob_free(bb, sizeof(bigblock_t));
  170. return;
  171. }
  172. }
  173. spin_unlock_irqrestore(&block_lock, flags);
  174. }
  175. slob_free((slob_t *)block - 1, 0);
  176. return;
  177. }
  178. EXPORT_SYMBOL(kfree);
  179. unsigned int ksize(const void *block)
  180. {
  181. bigblock_t *bb;
  182. unsigned long flags;
  183. if (!block)
  184. return 0;
  185. if (!((unsigned long)block & (PAGE_SIZE-1))) {
  186. spin_lock_irqsave(&block_lock, flags);
  187. for (bb = bigblocks; bb; bb = bb->next)
  188. if (bb->pages == block) {
  189. spin_unlock_irqrestore(&slob_lock, flags);
  190. return PAGE_SIZE << bb->order;
  191. }
  192. spin_unlock_irqrestore(&block_lock, flags);
  193. }
  194. return ((slob_t *)block - 1)->units * SLOB_UNIT;
  195. }
  196. struct kmem_cache {
  197. unsigned int size, align;
  198. const char *name;
  199. void (*ctor)(void *, struct kmem_cache *, unsigned long);
  200. void (*dtor)(void *, struct kmem_cache *, unsigned long);
  201. };
  202. struct kmem_cache *kmem_cache_create(const char *name, size_t size,
  203. size_t align, unsigned long flags,
  204. void (*ctor)(void*, struct kmem_cache *, unsigned long),
  205. void (*dtor)(void*, struct kmem_cache *, unsigned long))
  206. {
  207. struct kmem_cache *c;
  208. c = slob_alloc(sizeof(struct kmem_cache), flags, 0);
  209. if (c) {
  210. c->name = name;
  211. c->size = size;
  212. c->ctor = ctor;
  213. c->dtor = dtor;
  214. /* ignore alignment unless it's forced */
  215. c->align = (flags & SLAB_MUST_HWCACHE_ALIGN) ? SLOB_ALIGN : 0;
  216. if (c->align < align)
  217. c->align = align;
  218. }
  219. return c;
  220. }
  221. EXPORT_SYMBOL(kmem_cache_create);
  222. void kmem_cache_destroy(struct kmem_cache *c)
  223. {
  224. slob_free(c, sizeof(struct kmem_cache));
  225. }
  226. EXPORT_SYMBOL(kmem_cache_destroy);
  227. void *kmem_cache_alloc(struct kmem_cache *c, gfp_t flags)
  228. {
  229. void *b;
  230. if (c->size < PAGE_SIZE)
  231. b = slob_alloc(c->size, flags, c->align);
  232. else
  233. b = (void *)__get_free_pages(flags, get_order(c->size));
  234. if (c->ctor)
  235. c->ctor(b, c, SLAB_CTOR_CONSTRUCTOR);
  236. return b;
  237. }
  238. EXPORT_SYMBOL(kmem_cache_alloc);
  239. void *kmem_cache_zalloc(struct kmem_cache *c, gfp_t flags)
  240. {
  241. void *ret = kmem_cache_alloc(c, flags);
  242. if (ret)
  243. memset(ret, 0, c->size);
  244. return ret;
  245. }
  246. EXPORT_SYMBOL(kmem_cache_zalloc);
  247. void kmem_cache_free(struct kmem_cache *c, void *b)
  248. {
  249. if (c->dtor)
  250. c->dtor(b, c, 0);
  251. if (c->size < PAGE_SIZE)
  252. slob_free(b, c->size);
  253. else
  254. free_pages((unsigned long)b, get_order(c->size));
  255. }
  256. EXPORT_SYMBOL(kmem_cache_free);
  257. unsigned int kmem_cache_size(struct kmem_cache *c)
  258. {
  259. return c->size;
  260. }
  261. EXPORT_SYMBOL(kmem_cache_size);
  262. const char *kmem_cache_name(struct kmem_cache *c)
  263. {
  264. return c->name;
  265. }
  266. EXPORT_SYMBOL(kmem_cache_name);
  267. static struct timer_list slob_timer = TIMER_INITIALIZER(
  268. (void (*)(unsigned long))slob_timer_cbk, 0, 0);
  269. int kmem_cache_shrink(struct kmem_cache *d)
  270. {
  271. return 0;
  272. }
  273. EXPORT_SYMBOL(kmem_cache_shrink);
  274. int kmem_ptr_validate(struct kmem_cache *a, const void *b)
  275. {
  276. return 0;
  277. }
  278. void __init kmem_cache_init(void)
  279. {
  280. slob_timer_cbk();
  281. }
  282. static void slob_timer_cbk(void)
  283. {
  284. void *p = slob_alloc(PAGE_SIZE, 0, PAGE_SIZE-1);
  285. if (p)
  286. free_page((unsigned long)p);
  287. mod_timer(&slob_timer, jiffies + HZ);
  288. }