1 /* 2 * SLOB Allocator: Simple List Of Blocks 3 * 4 * Matt Mackall <mpm@selenic.com> 12/30/03 5 * 6 * NUMA support by Paul Mundt, 2007. 7 * 8 * How SLOB works: 9 * 10 * The core of SLOB is a traditional K&R style heap allocator, with 11 * support for returning aligned objects. The granularity of this 12 * allocator is as little as 2 bytes, however typically most architectures 13 * will require 4 bytes on 32-bit and 8 bytes on 64-bit. 14 * 15 * The slob heap is a set of linked list of pages from alloc_pages(), 16 * and within each page, there is a singly-linked list of free blocks 17 * (slob_t). The heap is grown on demand. To reduce fragmentation, 18 * heap pages are segregated into three lists, with objects less than 19 * 256 bytes, objects less than 1024 bytes, and all other objects. 20 * 21 * Allocation from heap involves first searching for a page with 22 * sufficient free blocks (using a next-fit-like approach) followed by 23 * a first-fit scan of the page. Deallocation inserts objects back 24 * into the free list in address order, so this is effectively an 25 * address-ordered first fit. 26 * 27 * Above this is an implementation of kmalloc/kfree. Blocks returned 28 * from kmalloc are prepended with a 4-byte header with the kmalloc size. 29 * If kmalloc is asked for objects of PAGE_SIZE or larger, it calls 30 * alloc_pages() directly, allocating compound pages so the page order 31 * does not have to be separately tracked, and also stores the exact 32 * allocation size in page->private so that it can be used to accurately 33 * provide ksize(). These objects are detected in kfree() because slob_page() 34 * is false for them. 35 * 36 * SLAB is emulated on top of SLOB by simply calling constructors and 37 * destructors for every SLAB allocation. Objects are returned with the 38 * 4-byte alignment unless the SLAB_HWCACHE_ALIGN flag is set, in which 39 * case the low-level allocator will fragment blocks to create the proper 40 * alignment. Again, objects of page-size or greater are allocated by 41 * calling alloc_pages(). As SLAB objects know their size, no separate 42 * size bookkeeping is necessary and there is essentially no allocation 43 * space overhead, and compound pages aren't needed for multi-page 44 * allocations. 45 * 46 * NUMA support in SLOB is fairly simplistic, pushing most of the real 47 * logic down to the page allocator, and simply doing the node accounting 48 * on the upper levels. In the event that a node id is explicitly 49 * provided, alloc_pages_exact_node() with the specified node id is used 50 * instead. The common case (or when the node id isn't explicitly provided) 51 * will default to the current node, as per numa_node_id(). 52 * 53 * Node aware pages are still inserted in to the global freelist, and 54 * these are scanned for by matching against the node id encoded in the 55 * page flags. As a result, block allocations that can be satisfied from 56 * the freelist will only be done so on pages residing on the same node, 57 * in order to prevent random node placement. 58 */ 59 60 #include <linux/kernel.h> 61 #include <linux/slab.h> 62 #include <linux/mm.h> 63 #include <linux/swap.h> /* struct reclaim_state */ 64 #include <linux/cache.h> 65 #include <linux/init.h> 66 #include <linux/module.h> 67 #include <linux/rcupdate.h> 68 #include <linux/list.h> 69 #include <linux/kmemtrace.h> 70 #include <linux/kmemleak.h> 71 #include <asm/atomic.h> 72 73 /* 74 * slob_block has a field 'units', which indicates size of block if +ve, 75 * or offset of next block if -ve (in SLOB_UNITs). 76 * 77 * Free blocks of size 1 unit simply contain the offset of the next block. 78 * Those with larger size contain their size in the first SLOB_UNIT of 79 * memory, and the offset of the next free block in the second SLOB_UNIT. 80 */ 81 #if PAGE_SIZE <= (32767 * 2) 82 typedef s16 slobidx_t; 83 #else 84 typedef s32 slobidx_t; 85 #endif 86 87 struct slob_block { 88 slobidx_t units; 89 }; 90 typedef struct slob_block slob_t; 91 92 /* 93 * We use struct page fields to manage some slob allocation aspects, 94 * however to avoid the horrible mess in include/linux/mm_types.h, we'll 95 * just define our own struct page type variant here. 96 */ 97 struct slob_page { 98 union { 99 struct {100 unsigned long flags; /* mandatory */101 atomic_t _count; /* mandatory */102 slobidx_t units; /* free units left in page */103 unsigned long pad[2];104 slob_t *free; /* first free slob_t in page */105 struct list_head list; /* linked list of free pages */106 };107 struct page page;108 };109 };110 static inline void struct_slob_page_wrong_size(void)111 { BUILD_BUG_ON(sizeof(struct slob_page) != sizeof(struct page)); }112113 /*114 * free_slob_page: call before a slob_page is returned to the page allocator.115 */116 static inline void free_slob_page(struct slob_page *sp)117 {118 reset_page_mapcount(&sp->page);119 sp->page.mapping = NULL;120 }121122 /*123 * All partially free slob pages go on these lists.124 */125 #define SLOB_BREAK1 256126 #define SLOB_BREAK2 1024127 static LIST_HEAD(free_slob_small);128 static LIST_HEAD(free_slob_medium);129 static LIST_HEAD(free_slob_large);131 /*132 * is_slob_page: True for all slob pages (false for bigblock pages)133 */134 static inline int is_slob_page(struct slob_page *sp)135 {136 return PageSlab((struct page *)sp);137 }138139 static inline void set_slob_page(struct slob_page *sp)140 {141 __SetPageSlab((struct page *)sp);142 }143144 static inline void clear_slob_page(struct slob_page *sp)145 {146 __ClearPageSlab((struct page *)sp);147 }148149 static inline struct slob_page *slob_page(const void *addr)150 {151 return (struct slob_page *)virt_to_page(addr);152 }153154 /*155 * slob_page_free: true for pages on free_slob_pages list.156 */157 static inline int slob_page_free(struct slob_page *sp)158 {159 return PageSlobFree((struct page *)sp);160 }161162 static void set_slob_page_free(struct slob_page *sp, struct list_head *list)163 {164 list_add(&sp->list, list);165 __SetPageSlobFree((struct page *)sp);166 }167168 static inline void clear_slob_page_free(struct slob_page *sp)169 {170 list_del(&sp->list);171 __ClearPageSlobFree((struct page *)sp);172 }173174 #define SLOB_UNIT sizeof(slob_t)175 #define SLOB_UNITS(size) (((size) + SLOB_UNIT - 1)/SLOB_UNIT)176 #define SLOB_ALIGN L1_CACHE_BYTES177178 /*179 * struct slob_rcu is inserted at the tail of allocated slob blocks, which180 * were created with a SLAB_DESTROY_BY_RCU slab. slob_rcu is used to free181 * the block using call_rcu.182 */183 struct slob_rcu {184 struct rcu_head head;185 int size;186 };187188 /*189 * slob_lock protects all slob allocator structures.190 */191 static DEFINE_SPINLOCK(slob_lock);192193 /*194 * Encode the given size and next info into a free slob block s.195 */196 static void set_slob(slob_t *s, slobidx_t size, slob_t *next)197 {198 slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);199 slobidx_t offset = next - base;200201 if (size > 1) {202 s[0].units = size;203 s[1].units = offset;204 } else205 s[0].units = -offset;206 }207208 /*209 * Return the size of a slob block.210 */211 static slobidx_t slob_units(slob_t *s)212 {213 if (s->units > 0)214 return s->units;215 return 1;216 }217218 /*219 * Return the next free slob block pointer after this one.220 */221 static slob_t *slob_next(slob_t *s)222 {223 slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);224 slobidx_t next;225226 if (s[0].units < 0)227 next = -s[0].units;228 else229 next = s[1].units;230 return base+next;231 }232233 /*234 * Returns true if s is the last free block in its page.235 */236 static int slob_last(slob_t *s)237 {238 return !((unsigned long)slob_next(s) & ~PAGE_MASK);239 }240241 static void *slob_new_pages(gfp_t gfp, int order, int node)242 {243 void *page;244245 #ifdef CONFIG_NUMA246 if (node != -1)247 page = alloc_pages_exact_node(node, gfp, order);248 else249 #endif250 page = alloc_pages(gfp, order);251252 if (!page)253 return NULL;254255 return page_address(page);256 }257258 static void slob_free_pages(void *b, int order)259 {260 if (current->reclaim_state)261 current->reclaim_state->reclaimed_slab += 1 << order;262 free_pages((unsigned long)b, order);263 }264265 /*266 * Allocate a slob block within a given slob_page sp.267 *//* seiriaka diatrexw ola ta pages me tin for pou idi uparxei kai se ka8e page elegxo ola ta blocks kai blepw pou xwraw kai poso upoloipo afinw kai epistrefw enan pointer sto block auto * kai allazw tin timi enos pointer se integer o opoios mou leei poso einai to upoloipo autou tou block kai ka8e fora elegxo tin timi auth gia ton poion pointer 8a krataw */268 static void *slob_page_find(struct slob_page *sp, size_t size, int align )269 { static unsigned int printer = 0;270 slob_t *prev,*min_p, *cur, *aligned = NULL; int cur_min = 10000000; int diafora;271 int delta = 0, units = SLOB_UNITS(size);272 // prepei mesa se auto to page na brw pio block me xwraei kai afinei to mikrotero ipoloipo diladi diatrexw ola eleu8era block kai briskw auto me tin mikroteri 8etiki diafora kai to epistefw min_p = NULL;273 for (prev = NULL, cur = sp->free; ; prev = cur, cur = slob_next(cur)) {274 slobidx_t avail = slob_units(cur); if ( printer == 0 ) { }275276 if (align) {277 aligned = (slob_t *)ALIGN((unsigned long)cur, align);278 delta = aligned - cur;279 } if (avail >= units + delta) { diafora = avail - units + delta; if(cur_min > diafora){ cur_min = diafora; min_p = cur; } } } return(min_p);}268 static void *slob_page_alloc(struct slob_page *sp, size_t size, int align, slob_t *cur)269 {271 int delta = 0, units = SLOB_UNITS(size);272 // prepei mesa se auto to page na brw pio block me xwraei kai afinei to mikrotero ipoloipo diladi diatrexw ola eleu8era block kai briskw auto me tin mikroteri 8etiki diafora kai to epistefw slob_t *prev,*next; prev = NULL; next = sp->free; printer = (printer+1)%6000; if ( printer == 0 ) { printk("slob_alloc: Slob_Request: %d\n", size); printk("slob_alloc: Candidate blocks size:"); } while(next!=cur){ aligned = (slob_t *)ALIGN((unsigned long)next, align); delta = aligned - next; if ( printer == 0 ) { printk("%d ", slob_units(next)-delta); } prev = next; next = slob_next(next); } if ( printer == 0 ) { if ( cur != NULL ) { aligned = (slob_t *)ALIGN((unsigned long)next, align); delta = aligned - next; printf("slob_alloc: Best Fit: %d\n\n", slob_units(cur) - delta); } else { printf("slob_alloc: Best Fit: NONE\n\n"); return NULL; } }273 slobidx_t avail = slob_units(cur);276 if (align) {277 aligned = (slob_t *)ALIGN((unsigned long)cur, align);278 delta = aligned - cur;279 }280 if (avail >= units + delta) { /* room enough? */281 slob_t *next;282283 if (delta) { /* need to fragment head to align? */284 next = slob_next(cur);285 set_slob(aligned, avail - delta, next);286 set_slob(cur, delta, aligned);287 prev = cur;288 cur = aligned;289 avail = slob_units(cur);290 }291292 next = slob_next(cur);293 if (avail == units) { /* exact fit? unlink. */294 if (prev)295 set_slob(prev, slob_units(prev), next);296 else297 sp->free = next;298 } else { /* fragment */299 if (prev)300 set_slob(prev, slob_units(prev), cur + units);301 else302 sp->free = cur + units;// 303 set_slob(cur + units, avail - units, next);304 }305306 sp->units -= units;307 if (!sp->units)308 clear_slob_page_free(sp);309 return cur;310 }311314 }315316 /*317 * slob_alloc: entry point into the slob allocator.318 */319 static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)320 {321 struct slob_page *sp,*min_page;322 struct list_head *prev; slob_t *min_p = NULL;323 struct list_head *slob_list;324 slob_t *b = NULL; min_page = NULL;325 unsigned long flags;326327 if (size < SLOB_BREAK1)328 slob_list = &free_slob_small;329 else if (size < SLOB_BREAK2)330 slob_list = &free_slob_medium;331 else332 slob_list = &free_slob_large;333334 spin_lock_irqsave(&slob_lock, flags);335 /* Iterate through each partially free page, try to find room */336 list_for_each_entry(sp, slob_list, list) {337 #ifdef CONFIG_NUMA338 /*339 * If there's a node specification, search for a partial340 * page with a matching node id in the freelist.341 */342 if (node != -1 && page_to_nid(&sp->page) != node)343 continue;344 #endif345 /* Enough room on this page? */346 if (sp->units < SLOB_UNITS(size))347 continue;348349 /* Attempt to alloc */350 prev = sp->list.prev; b = NULL; if(min_page == NULL || sp->units < min_page->units) 351 b = slob_page_find(sp, size, align);352 if (!b)353 continue; min_p = b; min_page = sp; }363 spin_unlock_irqrestore(&slob_lock, flags); b = slob_page_alloc(min_page, size, align,min_p);354358364365 /* Not enough space: must allocate a new page */366 if (!b) {367 b = slob_new_pages(gfp & ~__GFP_ZERO, 0, node);368 if (!b)369 return NULL;370 sp = slob_page(b);371 set_slob_page(sp);372373 spin_lock_irqsave(&slob_lock, flags);374 sp->units = SLOB_UNITS(PAGE_SIZE);375 sp->free = b;376 INIT_LIST_HEAD(&sp->list);377 set_slob(b, SLOB_UNITS(PAGE_SIZE), b + SLOB_UNITS(PAGE_SIZE));378 set_slob_page_free(sp, slob_list);379 b = slob_page_alloc(sp, size, align);380 BUG_ON(!b);381 spin_unlock_irqrestore(&slob_lock, flags);382 }383 if (unlikely((gfp & __GFP_ZERO) && b))384 memset(b, 0, size);385 return b;386 }387388 /*389 * slob_free: entry point into the slob allocator.390 */391 static void slob_free(void *block, int size)392 {393 struct slob_page *sp;394 slob_t *prev, *next, *b = (slob_t *)block;395 slobidx_t units;396 unsigned long flags;397398 if (unlikely(ZERO_OR_NULL_PTR(block)))399 return;400 BUG_ON(!size);401402 sp = slob_page(block);403 units = SLOB_UNITS(size);404405 spin_lock_irqsave(&slob_lock, flags);406407 if (sp->units + units == SLOB_UNITS(PAGE_SIZE)) {408 /* Go directly to page allocator. Do not pass slob allocator */409 if (slob_page_free(sp))410 clear_slob_page_free(sp);411 spin_unlock_irqrestore(&slob_lock, flags);412 clear_slob_page(sp);413 free_slob_page(sp);414 slob_free_pages(b, 0);415 return;416 }417418 if (!slob_page_free(sp)) {419 /* This slob page is about to become partially free. Easy! */420 sp->units = units;421 sp->free = b;422 set_slob(b, units,423 (void *)((unsigned long)(b +424 SLOB_UNITS(PAGE_SIZE)) & PAGE_MASK));425 set_slob_page_free(sp, &free_slob_small);426 goto out;427 }428429 /*430 * Otherwise the page is already partially free, so find reinsertion431 * point.432 */433 sp->units += units;434435 if (b < sp->free) {436 if (b + units == sp->free) {437 units += slob_units(sp->free);438 sp->free = slob_next(sp->free);439 }440 set_slob(b, units, sp->free);441 sp->free = b;442 } else {443 prev = sp->free;444 next = slob_next(prev);445 while (b > next) {446 prev = next;447 next = slob_next(prev);448 }449450 if (!slob_last(prev) && b + units == next) {451 units += slob_units(next);452 set_slob(b, units, slob_next(next));453 } else454 set_slob(b, units, next);455456 if (prev + slob_units(prev) == b) {457 units = slob_units(b) + slob_units(prev);458 set_slob(prev, units, slob_next(b));459 } else460 set_slob(prev, slob_units(prev), b);461 }462 out:463 spin_unlock_irqrestore(&slob_lock, flags);464 }465466 /*467 * End of slob allocator proper. Begin kmem_cache_alloc and kmalloc frontend.468 */469470 #ifndef ARCH_KMALLOC_MINALIGN471 #define ARCH_KMALLOC_MINALIGN __alignof__(unsigned long)472 #endif473474 #ifndef ARCH_SLAB_MINALIGN475 #define ARCH_SLAB_MINALIGN __alignof__(unsigned long)476 #endif477478 void *__kmalloc_node(size_t size, gfp_t gfp, int node)479 {480 unsigned int *m;481 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);482 void *ret;483484 lockdep_trace_alloc(gfp);485486 if (size < PAGE_SIZE - align) {487 if (!size)488 return ZERO_SIZE_PTR;489490 m = slob_alloc(size + align, gfp, align, node);491492 if (!m)493 return NULL;494 *m = size;495 ret = (void *)m + align;496497 trace_kmalloc_node(_RET_IP_, ret,498 size, size + align, gfp, node);499 } else {500 unsigned int order = get_order(size);501502 ret = slob_new_pages(gfp | __GFP_COMP, get_order(size), node);503 if (ret) {504 struct page *page;505 page = virt_to_page(ret);506 page->private = size;507 }508509 trace_kmalloc_node(_RET_IP_, ret,510 size, PAGE_SIZE << order, gfp, node);511 }512513 kmemleak_alloc(ret, size, 1, gfp);514 return ret;515 }516 EXPORT_SYMBOL(__kmalloc_node);517518 void kfree(const void *block)519 {520 struct slob_page *sp;521522 trace_kfree(_RET_IP_, block);523524 if (unlikely(ZERO_OR_NULL_PTR(block)))525 return;526 kmemleak_free(block);527528 sp = slob_page(block);529 if (is_slob_page(sp)) {530 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);531 unsigned int *m = (unsigned int *)(block - align);532 slob_free(m, *m + align);533 } else534 put_page(&sp->page);535 }536 EXPORT_SYMBOL(kfree);537538 /* can't use ksize for kmem_cache_alloc memory, only kmalloc */539 size_t ksize(const void *block)540 {541 struct slob_page *sp;542543 BUG_ON(!block);544 if (unlikely(block == ZERO_SIZE_PTR))545 return 0;546547 sp = slob_page(block);548 if (is_slob_page(sp)) {549 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);550 unsigned int *m = (unsigned int *)(block - align);551 return SLOB_UNITS(*m) * SLOB_UNIT;552 } else553 return sp->page.private;554 }555 EXPORT_SYMBOL(ksize);556557 struct kmem_cache {558 unsigned int size, align;559 unsigned long flags;560 const char *name;561 void (*ctor)(void *);562 };563564 struct kmem_cache *kmem_cache_create(const char *name, size_t size,565 size_t align, unsigned long flags, void (*ctor)(void *))566 {567 struct kmem_cache *c;568569 c = slob_alloc(sizeof(struct kmem_cache),570 GFP_KERNEL, ARCH_KMALLOC_MINALIGN, -1);571572 if (c) {573 c->name = name;574 c->size = size;575 if (flags & SLAB_DESTROY_BY_RCU) {576 /* leave room for rcu footer at the end of object */577 c->size += sizeof(struct slob_rcu);578 }579 c->flags = flags;580 c->ctor = ctor;581 /* ignore alignment unless it's forced */582 c->align = (flags & SLAB_HWCACHE_ALIGN) ? SLOB_ALIGN : 0;583 if (c->align < ARCH_SLAB_MINALIGN)584 c->align = ARCH_SLAB_MINALIGN;585 if (c->align < align)586 c->align = align;587 } else if (flags & SLAB_PANIC)588 panic("Cannot create slab cache %s\n", name);589590 kmemleak_alloc(c, sizeof(struct kmem_cache), 1, GFP_KERNEL);591 return c;592 }593 EXPORT_SYMBOL(kmem_cache_create);594595 void kmem_cache_destroy(struct kmem_cache *c)596 {597 kmemleak_free(c);598 if (c->flags & SLAB_DESTROY_BY_RCU)599 rcu_barrier();600 slob_free(c, sizeof(struct kmem_cache));601 }602 EXPORT_SYMBOL(kmem_cache_destroy);603604 void *kmem_cache_alloc_node(struct kmem_cache *c, gfp_t flags, int node)605 {606 void *b;607608 if (c->size < PAGE_SIZE) {609 b = slob_alloc(c->size, flags, c->align, node);610 trace_kmem_cache_alloc_node(_RET_IP_, b, c->size,611 SLOB_UNITS(c->size) * SLOB_UNIT,612 flags, node);613 } else {614 b = slob_new_pages(flags, get_order(c->size), node);615 trace_kmem_cache_alloc_node(_RET_IP_, b, c->size,616 PAGE_SIZE << get_order(c->size),617 flags, node);618 }619620 if (c->ctor)621 c->ctor(b);622623 kmemleak_alloc_recursive(b, c->size, 1, c->flags, flags);624 return b;625 }626 EXPORT_SYMBOL(kmem_cache_alloc_node);627628 static void __kmem_cache_free(void *b, int size)629 {630 if (size < PAGE_SIZE)631 slob_free(b, size);632 else633 slob_free_pages(b, get_order(size));634 }635636 static void kmem_rcu_free(struct rcu_head *head)637 {638 struct slob_rcu *slob_rcu = (struct slob_rcu *)head;639 void *b = (void *)slob_rcu - (slob_rcu->size - sizeof(struct slob_rcu));640641 __kmem_cache_free(b, slob_rcu->size);642 }643644 void kmem_cache_free(struct kmem_cache *c, void *b)645 {646 kmemleak_free_recursive(b, c->flags);647 if (unlikely(c->flags & SLAB_DESTROY_BY_RCU)) {648 struct slob_rcu *slob_rcu;649 slob_rcu = b + (c->size - sizeof(struct slob_rcu));650 INIT_RCU_HEAD(&slob_rcu->head);651 slob_rcu->size = c->size;652 call_rcu(&slob_rcu->head, kmem_rcu_free);653 } else {654 __kmem_cache_free(b, c->size);655 }656657 trace_kmem_cache_free(_RET_IP_, b);658 }659 EXPORT_SYMBOL(kmem_cache_free);660661 unsigned int kmem_cache_size(struct kmem_cache *c)662 {663 return c->size;664 }665 EXPORT_SYMBOL(kmem_cache_size);666667 const char *kmem_cache_name(struct kmem_cache *c)668 {669 return c->name;670 }671 EXPORT_SYMBOL(kmem_cache_name);672673 int kmem_cache_shrink(struct kmem_cache *d)674 {675 return 0;676 }677 EXPORT_SYMBOL(kmem_cache_shrink);678679 int kmem_ptr_validate(struct kmem_cache *a, const void *b)680 {681 return 0;682 }683684 static unsigned int slob_ready __read_mostly;685686 int slab_is_available(void)687 {688 return slob_ready;689 }690691 void __init kmem_cache_init(void)692 {693 slob_ready = 1;694 }695 This page was automatically generated by the LXR engine.