diff options
Diffstat (limited to 'mm/slob.c')
-rw-r--r-- | mm/slob.c | 600 |
1 files changed, 402 insertions, 198 deletions
diff --git a/mm/slob.c b/mm/slob.c index 71976c5d40d3..ec33fcdc852e 100644 --- a/mm/slob.c +++ b/mm/slob.c @@ -3,57 +3,159 @@ * * Matt Mackall <mpm@selenic.com> 12/30/03 * + * NUMA support by Paul Mundt, 2007. + * * How SLOB works: * * The core of SLOB is a traditional K&R style heap allocator, with * support for returning aligned objects. The granularity of this - * allocator is 8 bytes on x86, though it's perhaps possible to reduce - * this to 4 if it's deemed worth the effort. The slob heap is a - * singly-linked list of pages from __get_free_page, grown on demand - * and allocation from the heap is currently first-fit. + * allocator is as little as 2 bytes, however typically most architectures + * will require 4 bytes on 32-bit and 8 bytes on 64-bit. + * + * The slob heap is a linked list of pages from alloc_pages(), and + * within each page, there is a singly-linked list of free blocks (slob_t). + * The heap is grown on demand and allocation from the heap is currently + * first-fit. * * Above this is an implementation of kmalloc/kfree. Blocks returned - * from kmalloc are 8-byte aligned and prepended with a 8-byte header. + * from kmalloc are prepended with a 4-byte header with the kmalloc size. * If kmalloc is asked for objects of PAGE_SIZE or larger, it calls - * __get_free_pages directly so that it can return page-aligned blocks - * and keeps a linked list of such pages and their orders. These - * objects are detected in kfree() by their page alignment. + * alloc_pages() directly, allocating compound pages so the page order + * does not have to be separately tracked, and also stores the exact + * allocation size in page->private so that it can be used to accurately + * provide ksize(). These objects are detected in kfree() because slob_page() + * is false for them. * * SLAB is emulated on top of SLOB by simply calling constructors and - * destructors for every SLAB allocation. Objects are returned with - * the 8-byte alignment unless the SLAB_HWCACHE_ALIGN flag is - * set, in which case the low-level allocator will fragment blocks to - * create the proper alignment. Again, objects of page-size or greater - * are allocated by calling __get_free_pages. As SLAB objects know - * their size, no separate size bookkeeping is necessary and there is - * essentially no allocation space overhead. + * destructors for every SLAB allocation. Objects are returned with the + * 4-byte alignment unless the SLAB_HWCACHE_ALIGN flag is set, in which + * case the low-level allocator will fragment blocks to create the proper + * alignment. Again, objects of page-size or greater are allocated by + * calling alloc_pages(). As SLAB objects know their size, no separate + * size bookkeeping is necessary and there is essentially no allocation + * space overhead, and compound pages aren't needed for multi-page + * allocations. + * + * NUMA support in SLOB is fairly simplistic, pushing most of the real + * logic down to the page allocator, and simply doing the node accounting + * on the upper levels. In the event that a node id is explicitly + * provided, alloc_pages_node() with the specified node id is used + * instead. The common case (or when the node id isn't explicitly provided) + * will default to the current node, as per numa_node_id(). + * + * Node aware pages are still inserted in to the global freelist, and + * these are scanned for by matching against the node id encoded in the + * page flags. As a result, block allocations that can be satisfied from + * the freelist will only be done so on pages residing on the same node, + * in order to prevent random node placement. */ +#include <linux/kernel.h> #include <linux/slab.h> #include <linux/mm.h> #include <linux/cache.h> #include <linux/init.h> #include <linux/module.h> -#include <linux/timer.h> #include <linux/rcupdate.h> +#include <linux/list.h> +#include <asm/atomic.h> + +/* + * slob_block has a field 'units', which indicates size of block if +ve, + * or offset of next block if -ve (in SLOB_UNITs). + * + * Free blocks of size 1 unit simply contain the offset of the next block. + * Those with larger size contain their size in the first SLOB_UNIT of + * memory, and the offset of the next free block in the second SLOB_UNIT. + */ +#if PAGE_SIZE <= (32767 * 2) +typedef s16 slobidx_t; +#else +typedef s32 slobidx_t; +#endif struct slob_block { - int units; - struct slob_block *next; + slobidx_t units; }; typedef struct slob_block slob_t; +/* + * We use struct page fields to manage some slob allocation aspects, + * however to avoid the horrible mess in include/linux/mm_types.h, we'll + * just define our own struct page type variant here. + */ +struct slob_page { + union { + struct { + unsigned long flags; /* mandatory */ + atomic_t _count; /* mandatory */ + slobidx_t units; /* free units left in page */ + unsigned long pad[2]; + slob_t *free; /* first free slob_t in page */ + struct list_head list; /* linked list of free pages */ + }; + struct page page; + }; +}; +static inline void struct_slob_page_wrong_size(void) +{ BUILD_BUG_ON(sizeof(struct slob_page) != sizeof(struct page)); } + +/* + * free_slob_page: call before a slob_page is returned to the page allocator. + */ +static inline void free_slob_page(struct slob_page *sp) +{ + reset_page_mapcount(&sp->page); + sp->page.mapping = NULL; +} + +/* + * All (partially) free slob pages go on this list. + */ +static LIST_HEAD(free_slob_pages); + +/* + * slob_page: True for all slob pages (false for bigblock pages) + */ +static inline int slob_page(struct slob_page *sp) +{ + return test_bit(PG_active, &sp->flags); +} + +static inline void set_slob_page(struct slob_page *sp) +{ + __set_bit(PG_active, &sp->flags); +} + +static inline void clear_slob_page(struct slob_page *sp) +{ + __clear_bit(PG_active, &sp->flags); +} + +/* + * slob_page_free: true for pages on free_slob_pages list. + */ +static inline int slob_page_free(struct slob_page *sp) +{ + return test_bit(PG_private, &sp->flags); +} + +static inline void set_slob_page_free(struct slob_page *sp) +{ + list_add(&sp->list, &free_slob_pages); + __set_bit(PG_private, &sp->flags); +} + +static inline void clear_slob_page_free(struct slob_page *sp) +{ + list_del(&sp->list); + __clear_bit(PG_private, &sp->flags); +} + #define SLOB_UNIT sizeof(slob_t) #define SLOB_UNITS(size) (((size) + SLOB_UNIT - 1)/SLOB_UNIT) #define SLOB_ALIGN L1_CACHE_BYTES -struct bigblock { - int order; - void *pages; - struct bigblock *next; -}; -typedef struct bigblock bigblock_t; - /* * struct slob_rcu is inserted at the tail of allocated slob blocks, which * were created with a SLAB_DESTROY_BY_RCU slab. slob_rcu is used to free @@ -64,215 +166,332 @@ struct slob_rcu { int size; }; -static slob_t arena = { .next = &arena, .units = 1 }; -static slob_t *slobfree = &arena; -static bigblock_t *bigblocks; +/* + * slob_lock protects all slob allocator structures. + */ static DEFINE_SPINLOCK(slob_lock); -static DEFINE_SPINLOCK(block_lock); -static void slob_free(void *b, int size); -static void slob_timer_cbk(void); +/* + * Encode the given size and next info into a free slob block s. + */ +static void set_slob(slob_t *s, slobidx_t size, slob_t *next) +{ + slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK); + slobidx_t offset = next - base; + + if (size > 1) { + s[0].units = size; + s[1].units = offset; + } else + s[0].units = -offset; +} + +/* + * Return the size of a slob block. + */ +static slobidx_t slob_units(slob_t *s) +{ + if (s->units > 0) + return s->units; + return 1; +} + +/* + * Return the next free slob block pointer after this one. + */ +static slob_t *slob_next(slob_t *s) +{ + slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK); + slobidx_t next; + + if (s[0].units < 0) + next = -s[0].units; + else + next = s[1].units; + return base+next; +} + +/* + * Returns true if s is the last free block in its page. + */ +static int slob_last(slob_t *s) +{ + return !((unsigned long)slob_next(s) & ~PAGE_MASK); +} + +static void *slob_new_page(gfp_t gfp, int order, int node) +{ + void *page; + +#ifdef CONFIG_NUMA + if (node != -1) + page = alloc_pages_node(node, gfp, order); + else +#endif + page = alloc_pages(gfp, order); + if (!page) + return NULL; -static void *slob_alloc(size_t size, gfp_t gfp, int align) + return page_address(page); +} + +/* + * Allocate a slob block within a given slob_page sp. + */ +static void *slob_page_alloc(struct slob_page *sp, size_t size, int align) { slob_t *prev, *cur, *aligned = 0; int delta = 0, units = SLOB_UNITS(size); - unsigned long flags; - spin_lock_irqsave(&slob_lock, flags); - prev = slobfree; - for (cur = prev->next; ; prev = cur, cur = cur->next) { + for (prev = NULL, cur = sp->free; ; prev = cur, cur = slob_next(cur)) { + slobidx_t avail = slob_units(cur); + if (align) { aligned = (slob_t *)ALIGN((unsigned long)cur, align); delta = aligned - cur; } - if (cur->units >= units + delta) { /* room enough? */ + if (avail >= units + delta) { /* room enough? */ + slob_t *next; + if (delta) { /* need to fragment head to align? */ - aligned->units = cur->units - delta; - aligned->next = cur->next; - cur->next = aligned; - cur->units = delta; + next = slob_next(cur); + set_slob(aligned, avail - delta, next); + set_slob(cur, delta, aligned); prev = cur; cur = aligned; + avail = slob_units(cur); } - if (cur->units == units) /* exact fit? */ - prev->next = cur->next; /* unlink */ - else { /* fragment */ - prev->next = cur + units; - prev->next->units = cur->units - units; - prev->next->next = cur->next; - cur->units = units; + next = slob_next(cur); + if (avail == units) { /* exact fit? unlink. */ + if (prev) + set_slob(prev, slob_units(prev), next); + else + sp->free = next; + } else { /* fragment */ + if (prev) + set_slob(prev, slob_units(prev), cur + units); + else + sp->free = cur + units; + set_slob(cur + units, avail - units, next); } - slobfree = prev; - spin_unlock_irqrestore(&slob_lock, flags); + sp->units -= units; + if (!sp->units) + clear_slob_page_free(sp); return cur; } - if (cur == slobfree) { - spin_unlock_irqrestore(&slob_lock, flags); + if (slob_last(cur)) + return NULL; + } +} - if (size == PAGE_SIZE) /* trying to shrink arena? */ - return 0; +/* + * slob_alloc: entry point into the slob allocator. + */ +static void *slob_alloc(size_t size, gfp_t gfp, int align, int node) +{ + struct slob_page *sp; + struct list_head *prev; + slob_t *b = NULL; + unsigned long flags; - cur = (slob_t *)__get_free_page(gfp); - if (!cur) - return 0; + spin_lock_irqsave(&slob_lock, flags); + /* Iterate through each partially free page, try to find room */ + list_for_each_entry(sp, &free_slob_pages, list) { +#ifdef CONFIG_NUMA + /* + * If there's a node specification, search for a partial + * page with a matching node id in the freelist. + */ + if (node != -1 && page_to_nid(&sp->page) != node) + continue; +#endif + /* Enough room on this page? */ + if (sp->units < SLOB_UNITS(size)) + continue; + + /* Attempt to alloc */ + prev = sp->list.prev; + b = slob_page_alloc(sp, size, align); + if (!b) + continue; + + /* Improve fragment distribution and reduce our average + * search time by starting our next search here. (see + * Knuth vol 1, sec 2.5, pg 449) */ + if (free_slob_pages.next != prev->next) + list_move_tail(&free_slob_pages, prev->next); + break; + } + spin_unlock_irqrestore(&slob_lock, flags); - slob_free(cur, PAGE_SIZE); - spin_lock_irqsave(&slob_lock, flags); - cur = slobfree; - } + /* Not enough space: must allocate a new page */ + if (!b) { + b = slob_new_page(gfp, 0, node); + if (!b) + return 0; + sp = (struct slob_page *)virt_to_page(b); + set_slob_page(sp); + + spin_lock_irqsave(&slob_lock, flags); + sp->units = SLOB_UNITS(PAGE_SIZE); + sp->free = b; + INIT_LIST_HEAD(&sp->list); + set_slob(b, SLOB_UNITS(PAGE_SIZE), b + SLOB_UNITS(PAGE_SIZE)); + set_slob_page_free(sp); + b = slob_page_alloc(sp, size, align); + BUG_ON(!b); + spin_unlock_irqrestore(&slob_lock, flags); } + if (unlikely((gfp & __GFP_ZERO) && b)) + memset(b, 0, size); + return b; } +/* + * slob_free: entry point into the slob allocator. + */ static void slob_free(void *block, int size) { - slob_t *cur, *b = (slob_t *)block; + struct slob_page *sp; + slob_t *prev, *next, *b = (slob_t *)block; + slobidx_t units; unsigned long flags; - if (!block) + if (ZERO_OR_NULL_PTR(block)) return; + BUG_ON(!size); - if (size) - b->units = SLOB_UNITS(size); + sp = (struct slob_page *)virt_to_page(block); + units = SLOB_UNITS(size); - /* Find reinsertion point */ spin_lock_irqsave(&slob_lock, flags); - for (cur = slobfree; !(b > cur && b < cur->next); cur = cur->next) - if (cur >= cur->next && (b > cur || b < cur->next)) - break; - - if (b + b->units == cur->next) { - b->units += cur->next->units; - b->next = cur->next->next; - } else - b->next = cur->next; - - if (cur + cur->units == b) { - cur->units += b->units; - cur->next = b->next; - } else - cur->next = b; - slobfree = cur; - - spin_unlock_irqrestore(&slob_lock, flags); -} - -void *__kmalloc(size_t size, gfp_t gfp) -{ - slob_t *m; - bigblock_t *bb; - unsigned long flags; + if (sp->units + units == SLOB_UNITS(PAGE_SIZE)) { + /* Go directly to page allocator. Do not pass slob allocator */ + if (slob_page_free(sp)) + clear_slob_page_free(sp); + clear_slob_page(sp); + free_slob_page(sp); + free_page((unsigned long)b); + goto out; + } - if (size < PAGE_SIZE - SLOB_UNIT) { - m = slob_alloc(size + SLOB_UNIT, gfp, 0); - return m ? (void *)(m + 1) : 0; + if (!slob_page_free(sp)) { + /* This slob page is about to become partially free. Easy! */ + sp->units = units; + sp->free = b; + set_slob(b, units, + (void *)((unsigned long)(b + + SLOB_UNITS(PAGE_SIZE)) & PAGE_MASK)); + set_slob_page_free(sp); + goto out; } - bb = slob_alloc(sizeof(bigblock_t), gfp, 0); - if (!bb) - return 0; + /* + * Otherwise the page is already partially free, so find reinsertion + * point. + */ + sp->units += units; - bb->order = get_order(size); - bb->pages = (void *)__get_free_pages(gfp, bb->order); + if (b < sp->free) { + set_slob(b, units, sp->free); + sp->free = b; + } else { + prev = sp->free; + next = slob_next(prev); + while (b > next) { + prev = next; + next = slob_next(prev); + } - if (bb->pages) { - spin_lock_irqsave(&block_lock, flags); - bb->next = bigblocks; - bigblocks = bb; - spin_unlock_irqrestore(&block_lock, flags); - return bb->pages; + if (!slob_last(prev) && b + units == next) { + units += slob_units(next); + set_slob(b, units, slob_next(next)); + } else + set_slob(b, units, next); + + if (prev + slob_units(prev) == b) { + units = slob_units(b) + slob_units(prev); + set_slob(prev, units, slob_next(b)); + } else + set_slob(prev, slob_units(prev), b); } - - slob_free(bb, sizeof(bigblock_t)); - return 0; +out: + spin_unlock_irqrestore(&slob_lock, flags); } -EXPORT_SYMBOL(__kmalloc); -/** - * krealloc - reallocate memory. The contents will remain unchanged. - * - * @p: object to reallocate memory for. - * @new_size: how many bytes of memory are required. - * @flags: the type of memory to allocate. - * - * The contents of the object pointed to are preserved up to the - * lesser of the new and old sizes. If @p is %NULL, krealloc() - * behaves exactly like kmalloc(). If @size is 0 and @p is not a - * %NULL pointer, the object pointed to is freed. +/* + * End of slob allocator proper. Begin kmem_cache_alloc and kmalloc frontend. */ -void *krealloc(const void *p, size_t new_size, gfp_t flags) + +#ifndef ARCH_KMALLOC_MINALIGN +#define ARCH_KMALLOC_MINALIGN __alignof__(unsigned long) +#endif + +#ifndef ARCH_SLAB_MINALIGN +#define ARCH_SLAB_MINALIGN __alignof__(unsigned long) +#endif + +void *__kmalloc_node(size_t size, gfp_t gfp, int node) { - void *ret; + unsigned int *m; + int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN); - if (unlikely(!p)) - return kmalloc_track_caller(new_size, flags); + if (size < PAGE_SIZE - align) { + if (!size) + return ZERO_SIZE_PTR; - if (unlikely(!new_size)) { - kfree(p); - return NULL; - } + m = slob_alloc(size + align, gfp, align, node); + if (m) + *m = size; + return (void *)m + align; + } else { + void *ret; - ret = kmalloc_track_caller(new_size, flags); - if (ret) { - memcpy(ret, p, min(new_size, ksize(p))); - kfree(p); + ret = slob_new_page(gfp | __GFP_COMP, get_order(size), node); + if (ret) { + struct page *page; + page = virt_to_page(ret); + page->private = size; + } + return ret; } - return ret; } -EXPORT_SYMBOL(krealloc); +EXPORT_SYMBOL(__kmalloc_node); void kfree(const void *block) { - bigblock_t *bb, **last = &bigblocks; - unsigned long flags; + struct slob_page *sp; - if (!block) + if (ZERO_OR_NULL_PTR(block)) return; - if (!((unsigned long)block & (PAGE_SIZE-1))) { - /* might be on the big block list */ - spin_lock_irqsave(&block_lock, flags); - for (bb = bigblocks; bb; last = &bb->next, bb = bb->next) { - if (bb->pages == block) { - *last = bb->next; - spin_unlock_irqrestore(&block_lock, flags); - free_pages((unsigned long)block, bb->order); - slob_free(bb, sizeof(bigblock_t)); - return; - } - } - spin_unlock_irqrestore(&block_lock, flags); - } - - slob_free((slob_t *)block - 1, 0); - return; + sp = (struct slob_page *)virt_to_page(block); + if (slob_page(sp)) { + int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN); + unsigned int *m = (unsigned int *)(block - align); + slob_free(m, *m + align); + } else + put_page(&sp->page); } - EXPORT_SYMBOL(kfree); +/* can't use ksize for kmem_cache_alloc memory, only kmalloc */ size_t ksize(const void *block) { - bigblock_t *bb; - unsigned long flags; + struct slob_page *sp; - if (!block) + if (ZERO_OR_NULL_PTR(block)) return 0; - if (!((unsigned long)block & (PAGE_SIZE-1))) { - spin_lock_irqsave(&block_lock, flags); - for (bb = bigblocks; bb; bb = bb->next) - if (bb->pages == block) { - spin_unlock_irqrestore(&slob_lock, flags); - return PAGE_SIZE << bb->order; - } - spin_unlock_irqrestore(&block_lock, flags); - } - - return ((slob_t *)block - 1)->units * SLOB_UNIT; + sp = (struct slob_page *)virt_to_page(block); + if (slob_page(sp)) + return ((slob_t *)block - 1)->units + SLOB_UNIT; + else + return sp->page.private; } struct kmem_cache { @@ -284,12 +503,11 @@ struct kmem_cache { struct kmem_cache *kmem_cache_create(const char *name, size_t size, size_t align, unsigned long flags, - void (*ctor)(void*, struct kmem_cache *, unsigned long), - void (*dtor)(void*, struct kmem_cache *, unsigned long)) + void (*ctor)(void*, struct kmem_cache *, unsigned long)) { struct kmem_cache *c; - c = slob_alloc(sizeof(struct kmem_cache), flags, 0); + c = slob_alloc(sizeof(struct kmem_cache), flags, 0, -1); if (c) { c->name = name; @@ -302,6 +520,8 @@ struct kmem_cache *kmem_cache_create(const char *name, size_t size, c->ctor = ctor; /* ignore alignment unless it's forced */ c->align = (flags & SLAB_HWCACHE_ALIGN) ? SLOB_ALIGN : 0; + if (c->align < ARCH_SLAB_MINALIGN) + c->align = ARCH_SLAB_MINALIGN; if (c->align < align) c->align = align; } else if (flags & SLAB_PANIC) @@ -317,31 +537,21 @@ void kmem_cache_destroy(struct kmem_cache *c) } EXPORT_SYMBOL(kmem_cache_destroy); -void *kmem_cache_alloc(struct kmem_cache *c, gfp_t flags) +void *kmem_cache_alloc_node(struct kmem_cache *c, gfp_t flags, int node) { void *b; if (c->size < PAGE_SIZE) - b = slob_alloc(c->size, flags, c->align); + b = slob_alloc(c->size, flags, c->align, node); else - b = (void *)__get_free_pages(flags, get_order(c->size)); + b = slob_new_page(flags, get_order(c->size), node); if (c->ctor) c->ctor(b, c, 0); return b; } -EXPORT_SYMBOL(kmem_cache_alloc); - -void *kmem_cache_zalloc(struct kmem_cache *c, gfp_t flags) -{ - void *ret = kmem_cache_alloc(c, flags); - if (ret) - memset(ret, 0, c->size); - - return ret; -} -EXPORT_SYMBOL(kmem_cache_zalloc); +EXPORT_SYMBOL(kmem_cache_alloc_node); static void __kmem_cache_free(void *b, int size) { @@ -385,9 +595,6 @@ const char *kmem_cache_name(struct kmem_cache *c) } EXPORT_SYMBOL(kmem_cache_name); -static struct timer_list slob_timer = TIMER_INITIALIZER( - (void (*)(unsigned long))slob_timer_cbk, 0, 0); - int kmem_cache_shrink(struct kmem_cache *d) { return 0; @@ -399,17 +606,14 @@ int kmem_ptr_validate(struct kmem_cache *a, const void *b) return 0; } -void __init kmem_cache_init(void) +static unsigned int slob_ready __read_mostly; + +int slab_is_available(void) { - slob_timer_cbk(); + return slob_ready; } -static void slob_timer_cbk(void) +void __init kmem_cache_init(void) { - void *p = slob_alloc(PAGE_SIZE, 0, PAGE_SIZE-1); - - if (p) - free_page((unsigned long)p); - - mod_timer(&slob_timer, jiffies + HZ); + slob_ready = 1; } |