slob.c revision 6ab3d5624e172c553004ecc862bfeac16d9d68b7
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 32#include <linux/slab.h> 33#include <linux/mm.h> 34#include <linux/cache.h> 35#include <linux/init.h> 36#include <linux/module.h> 37#include <linux/timer.h> 38 39struct slob_block { 40 int units; 41 struct slob_block *next; 42}; 43typedef struct slob_block slob_t; 44 45#define SLOB_UNIT sizeof(slob_t) 46#define SLOB_UNITS(size) (((size) + SLOB_UNIT - 1)/SLOB_UNIT) 47#define SLOB_ALIGN L1_CACHE_BYTES 48 49struct bigblock { 50 int order; 51 void *pages; 52 struct bigblock *next; 53}; 54typedef struct bigblock bigblock_t; 55 56static slob_t arena = { .next = &arena, .units = 1 }; 57static slob_t *slobfree = &arena; 58static bigblock_t *bigblocks; 59static DEFINE_SPINLOCK(slob_lock); 60static DEFINE_SPINLOCK(block_lock); 61 62static void slob_free(void *b, int size); 63 64static void *slob_alloc(size_t size, gfp_t gfp, int align) 65{ 66 slob_t *prev, *cur, *aligned = 0; 67 int delta = 0, units = SLOB_UNITS(size); 68 unsigned long flags; 69 70 spin_lock_irqsave(&slob_lock, flags); 71 prev = slobfree; 72 for (cur = prev->next; ; prev = cur, cur = cur->next) { 73 if (align) { 74 aligned = (slob_t *)ALIGN((unsigned long)cur, align); 75 delta = aligned - cur; 76 } 77 if (cur->units >= units + delta) { /* room enough? */ 78 if (delta) { /* need to fragment head to align? */ 79 aligned->units = cur->units - delta; 80 aligned->next = cur->next; 81 cur->next = aligned; 82 cur->units = delta; 83 prev = cur; 84 cur = aligned; 85 } 86 87 if (cur->units == units) /* exact fit? */ 88 prev->next = cur->next; /* unlink */ 89 else { /* fragment */ 90 prev->next = cur + units; 91 prev->next->units = cur->units - units; 92 prev->next->next = cur->next; 93 cur->units = units; 94 } 95 96 slobfree = prev; 97 spin_unlock_irqrestore(&slob_lock, flags); 98 return cur; 99 } 100 if (cur == slobfree) { 101 spin_unlock_irqrestore(&slob_lock, flags); 102 103 if (size == PAGE_SIZE) /* trying to shrink arena? */ 104 return 0; 105 106 cur = (slob_t *)__get_free_page(gfp); 107 if (!cur) 108 return 0; 109 110 slob_free(cur, PAGE_SIZE); 111 spin_lock_irqsave(&slob_lock, flags); 112 cur = slobfree; 113 } 114 } 115} 116 117static void slob_free(void *block, int size) 118{ 119 slob_t *cur, *b = (slob_t *)block; 120 unsigned long flags; 121 122 if (!block) 123 return; 124 125 if (size) 126 b->units = SLOB_UNITS(size); 127 128 /* Find reinsertion point */ 129 spin_lock_irqsave(&slob_lock, flags); 130 for (cur = slobfree; !(b > cur && b < cur->next); cur = cur->next) 131 if (cur >= cur->next && (b > cur || b < cur->next)) 132 break; 133 134 if (b + b->units == cur->next) { 135 b->units += cur->next->units; 136 b->next = cur->next->next; 137 } else 138 b->next = cur->next; 139 140 if (cur + cur->units == b) { 141 cur->units += b->units; 142 cur->next = b->next; 143 } else 144 cur->next = b; 145 146 slobfree = cur; 147 148 spin_unlock_irqrestore(&slob_lock, flags); 149} 150 151static int FASTCALL(find_order(int size)); 152static int fastcall find_order(int size) 153{ 154 int order = 0; 155 for ( ; size > 4096 ; size >>=1) 156 order++; 157 return order; 158} 159 160void *kmalloc(size_t size, gfp_t gfp) 161{ 162 slob_t *m; 163 bigblock_t *bb; 164 unsigned long flags; 165 166 if (size < PAGE_SIZE - SLOB_UNIT) { 167 m = slob_alloc(size + SLOB_UNIT, gfp, 0); 168 return m ? (void *)(m + 1) : 0; 169 } 170 171 bb = slob_alloc(sizeof(bigblock_t), gfp, 0); 172 if (!bb) 173 return 0; 174 175 bb->order = find_order(size); 176 bb->pages = (void *)__get_free_pages(gfp, bb->order); 177 178 if (bb->pages) { 179 spin_lock_irqsave(&block_lock, flags); 180 bb->next = bigblocks; 181 bigblocks = bb; 182 spin_unlock_irqrestore(&block_lock, flags); 183 return bb->pages; 184 } 185 186 slob_free(bb, sizeof(bigblock_t)); 187 return 0; 188} 189 190EXPORT_SYMBOL(kmalloc); 191 192void kfree(const void *block) 193{ 194 bigblock_t *bb, **last = &bigblocks; 195 unsigned long flags; 196 197 if (!block) 198 return; 199 200 if (!((unsigned long)block & (PAGE_SIZE-1))) { 201 /* might be on the big block list */ 202 spin_lock_irqsave(&block_lock, flags); 203 for (bb = bigblocks; bb; last = &bb->next, bb = bb->next) { 204 if (bb->pages == block) { 205 *last = bb->next; 206 spin_unlock_irqrestore(&block_lock, flags); 207 free_pages((unsigned long)block, bb->order); 208 slob_free(bb, sizeof(bigblock_t)); 209 return; 210 } 211 } 212 spin_unlock_irqrestore(&block_lock, flags); 213 } 214 215 slob_free((slob_t *)block - 1, 0); 216 return; 217} 218 219EXPORT_SYMBOL(kfree); 220 221unsigned int ksize(const void *block) 222{ 223 bigblock_t *bb; 224 unsigned long flags; 225 226 if (!block) 227 return 0; 228 229 if (!((unsigned long)block & (PAGE_SIZE-1))) { 230 spin_lock_irqsave(&block_lock, flags); 231 for (bb = bigblocks; bb; bb = bb->next) 232 if (bb->pages == block) { 233 spin_unlock_irqrestore(&slob_lock, flags); 234 return PAGE_SIZE << bb->order; 235 } 236 spin_unlock_irqrestore(&block_lock, flags); 237 } 238 239 return ((slob_t *)block - 1)->units * SLOB_UNIT; 240} 241 242struct kmem_cache { 243 unsigned int size, align; 244 const char *name; 245 void (*ctor)(void *, struct kmem_cache *, unsigned long); 246 void (*dtor)(void *, struct kmem_cache *, unsigned long); 247}; 248 249struct kmem_cache *kmem_cache_create(const char *name, size_t size, 250 size_t align, unsigned long flags, 251 void (*ctor)(void*, struct kmem_cache *, unsigned long), 252 void (*dtor)(void*, struct kmem_cache *, unsigned long)) 253{ 254 struct kmem_cache *c; 255 256 c = slob_alloc(sizeof(struct kmem_cache), flags, 0); 257 258 if (c) { 259 c->name = name; 260 c->size = size; 261 c->ctor = ctor; 262 c->dtor = dtor; 263 /* ignore alignment unless it's forced */ 264 c->align = (flags & SLAB_MUST_HWCACHE_ALIGN) ? SLOB_ALIGN : 0; 265 if (c->align < align) 266 c->align = align; 267 } 268 269 return c; 270} 271EXPORT_SYMBOL(kmem_cache_create); 272 273int kmem_cache_destroy(struct kmem_cache *c) 274{ 275 slob_free(c, sizeof(struct kmem_cache)); 276 return 0; 277} 278EXPORT_SYMBOL(kmem_cache_destroy); 279 280void *kmem_cache_alloc(struct kmem_cache *c, gfp_t flags) 281{ 282 void *b; 283 284 if (c->size < PAGE_SIZE) 285 b = slob_alloc(c->size, flags, c->align); 286 else 287 b = (void *)__get_free_pages(flags, find_order(c->size)); 288 289 if (c->ctor) 290 c->ctor(b, c, SLAB_CTOR_CONSTRUCTOR); 291 292 return b; 293} 294EXPORT_SYMBOL(kmem_cache_alloc); 295 296void *kmem_cache_zalloc(struct kmem_cache *c, gfp_t flags) 297{ 298 void *ret = kmem_cache_alloc(c, flags); 299 if (ret) 300 memset(ret, 0, c->size); 301 302 return ret; 303} 304EXPORT_SYMBOL(kmem_cache_zalloc); 305 306void kmem_cache_free(struct kmem_cache *c, void *b) 307{ 308 if (c->dtor) 309 c->dtor(b, c, 0); 310 311 if (c->size < PAGE_SIZE) 312 slob_free(b, c->size); 313 else 314 free_pages((unsigned long)b, find_order(c->size)); 315} 316EXPORT_SYMBOL(kmem_cache_free); 317 318unsigned int kmem_cache_size(struct kmem_cache *c) 319{ 320 return c->size; 321} 322EXPORT_SYMBOL(kmem_cache_size); 323 324const char *kmem_cache_name(struct kmem_cache *c) 325{ 326 return c->name; 327} 328EXPORT_SYMBOL(kmem_cache_name); 329 330static struct timer_list slob_timer = TIMER_INITIALIZER( 331 (void (*)(unsigned long))kmem_cache_init, 0, 0); 332 333void kmem_cache_init(void) 334{ 335 void *p = slob_alloc(PAGE_SIZE, 0, PAGE_SIZE-1); 336 337 if (p) 338 free_page((unsigned long)p); 339 340 mod_timer(&slob_timer, jiffies + HZ); 341} 342 343atomic_t slab_reclaim_pages = ATOMIC_INIT(0); 344EXPORT_SYMBOL(slab_reclaim_pages); 345 346#ifdef CONFIG_SMP 347 348void *__alloc_percpu(size_t size) 349{ 350 int i; 351 struct percpu_data *pdata = kmalloc(sizeof (*pdata), GFP_KERNEL); 352 353 if (!pdata) 354 return NULL; 355 356 for_each_possible_cpu(i) { 357 pdata->ptrs[i] = kmalloc(size, GFP_KERNEL); 358 if (!pdata->ptrs[i]) 359 goto unwind_oom; 360 memset(pdata->ptrs[i], 0, size); 361 } 362 363 /* Catch derefs w/o wrappers */ 364 return (void *) (~(unsigned long) pdata); 365 366unwind_oom: 367 while (--i >= 0) { 368 if (!cpu_possible(i)) 369 continue; 370 kfree(pdata->ptrs[i]); 371 } 372 kfree(pdata); 373 return NULL; 374} 375EXPORT_SYMBOL(__alloc_percpu); 376 377void 378free_percpu(const void *objp) 379{ 380 int i; 381 struct percpu_data *p = (struct percpu_data *) (~(unsigned long) objp); 382 383 for_each_possible_cpu(i) 384 kfree(p->ptrs[i]); 385 386 kfree(p); 387} 388EXPORT_SYMBOL(free_percpu); 389 390#endif 391