Root/mm/slob.c

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)
82typedef s16 slobidx_t;
83#else
84typedef s32 slobidx_t;
85#endif
86
87struct slob_block {
88    slobidx_t units;
89};
90typedef 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 */
97struct 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};
110static inline void struct_slob_page_wrong_size(void)
111{ BUILD_BUG_ON(sizeof(struct slob_page) != sizeof(struct page)); }
112
113/*
114 * free_slob_page: call before a slob_page is returned to the page allocator.
115 */
116static inline void free_slob_page(struct slob_page *sp)
117{
118    reset_page_mapcount(&sp->page);
119    sp->page.mapping = NULL;
120}
121
122/*
123 * All partially free slob pages go on these lists.
124 */
125#define SLOB_BREAK1 256
126#define SLOB_BREAK2 1024
127static LIST_HEAD(free_slob_small);
128static LIST_HEAD(free_slob_medium);
129static LIST_HEAD(free_slob_large);
130
131/*
132 * is_slob_page: True for all slob pages (false for bigblock pages)
133 */
134static inline int is_slob_page(struct slob_page *sp)
135{
136    return PageSlab((struct page *)sp);
137}
138
139static inline void set_slob_page(struct slob_page *sp)
140{
141    __SetPageSlab((struct page *)sp);
142}
143
144static inline void clear_slob_page(struct slob_page *sp)
145{
146    __ClearPageSlab((struct page *)sp);
147}
148
149static inline struct slob_page *slob_page(const void *addr)
150{
151    return (struct slob_page *)virt_to_page(addr);
152}
153
154/*
155 * slob_page_free: true for pages on free_slob_pages list.
156 */
157static inline int slob_page_free(struct slob_page *sp)
158{
159    return PageSlobFree((struct page *)sp);
160}
161
162static 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}
167
168static inline void clear_slob_page_free(struct slob_page *sp)
169{
170    list_del(&sp->list);
171    __ClearPageSlobFree((struct page *)sp);
172}
173
174#define SLOB_UNIT sizeof(slob_t)
175#define SLOB_UNITS(size) (((size) + SLOB_UNIT - 1)/SLOB_UNIT)
176#define SLOB_ALIGN L1_CACHE_BYTES
177
178/*
179 * struct slob_rcu is inserted at the tail of allocated slob blocks, which
180 * were created with a SLAB_DESTROY_BY_RCU slab. slob_rcu is used to free
181 * the block using call_rcu.
182 */
183struct slob_rcu {
184    struct rcu_head head;
185    int size;
186};
187
188/*
189 * slob_lock protects all slob allocator structures.
190 */
191static DEFINE_SPINLOCK(slob_lock);
192
193/*
194 * Encode the given size and next info into a free slob block s.
195 */
196static 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;
200
201    if (size > 1) {
202        s[0].units = size;
203        s[1].units = offset;
204    } else
205        s[0].units = -offset;
206}
207
208/*
209 * Return the size of a slob block.
210 */
211static slobidx_t slob_units(slob_t *s)
212{
213    if (s->units > 0)
214        return s->units;
215    return 1;
216}
217
218/*
219 * Return the next free slob block pointer after this one.
220 */
221static slob_t *slob_next(slob_t *s)
222{
223    slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
224    slobidx_t next;
225
226    if (s[0].units < 0)
227        next = -s[0].units;
228    else
229        next = s[1].units;
230    return base+next;
231}
232
233/*
234 * Returns true if s is the last free block in its page.
235 */
236static int slob_last(slob_t *s)
237{
238    return !((unsigned long)slob_next(s) & ~PAGE_MASK);
239}
240
241static void *slob_new_pages(gfp_t gfp, int order, int node)
242{
243    void *page;
244
245#ifdef CONFIG_NUMA
246    if (node != -1)
247        page = alloc_pages_exact_node(node, gfp, order);
248    else
249#endif
250        page = alloc_pages(gfp, order);
251
252    if (!page)
253        return NULL;
254
255    return page_address(page);
256}
257
258static 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}
264
265/*
266 * Allocate a slob block within a given slob_page sp.
267 */
268static void *slob_page_alloc(struct slob_page *sp, size_t size, int align)
269{
270    slob_t *prev, *cur, *aligned = NULL;
271    int delta = 0, units = SLOB_UNITS(size);
272
273    for (prev = NULL, cur = sp->free; ; prev = cur, cur = slob_next(cur)) {
274        slobidx_t avail = slob_units(cur);
275
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;
282
283            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            }
291
292            next = slob_next(cur);
293            if (avail == units) { /* exact fit? unlink. */
294                if (prev)
295                    set_slob(prev, slob_units(prev), next);
296                else
297                    sp->free = next;
298            } else { /* fragment */
299                if (prev)
300                    set_slob(prev, slob_units(prev), cur + units);
301                else
302                    sp->free = cur + units;
303                set_slob(cur + units, avail - units, next);
304            }
305
306            sp->units -= units;
307            if (!sp->units)
308                clear_slob_page_free(sp);
309            return cur;
310        }
311        if (slob_last(cur))
312            return NULL;
313    }
314}
315
316/*
317 * slob_alloc: entry point into the slob allocator.
318 */
319static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
320{
321    struct slob_page *sp;
322    struct list_head *prev;
323    struct list_head *slob_list;
324    slob_t *b = NULL;
325    unsigned long flags;
326
327    if (size < SLOB_BREAK1)
328        slob_list = &free_slob_small;
329    else if (size < SLOB_BREAK2)
330        slob_list = &free_slob_medium;
331    else
332        slob_list = &free_slob_large;
333
334    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_NUMA
338        /*
339         * If there's a node specification, search for a partial
340         * page with a matching node id in the freelist.
341         */
342        if (node != -1 && page_to_nid(&sp->page) != node)
343            continue;
344#endif
345        /* Enough room on this page? */
346        if (sp->units < SLOB_UNITS(size))
347            continue;
348
349        /* Attempt to alloc */
350        prev = sp->list.prev;
351        b = slob_page_alloc(sp, size, align);
352        if (!b)
353            continue;
354
355        /* Improve fragment distribution and reduce our average
356         * search time by starting our next search here. (see
357         * Knuth vol 1, sec 2.5, pg 449) */
358        if (prev != slob_list->prev &&
359                slob_list->next != prev->next)
360            list_move_tail(slob_list, prev->next);
361        break;
362    }
363    spin_unlock_irqrestore(&slob_lock, flags);
364
365    /* 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);
372
373        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}
387
388/*
389 * slob_free: entry point into the slob allocator.
390 */
391static 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;
397
398    if (unlikely(ZERO_OR_NULL_PTR(block)))
399        return;
400    BUG_ON(!size);
401
402    sp = slob_page(block);
403    units = SLOB_UNITS(size);
404
405    spin_lock_irqsave(&slob_lock, flags);
406
407    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    }
417
418    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    }
428
429    /*
430     * Otherwise the page is already partially free, so find reinsertion
431     * point.
432     */
433    sp->units += units;
434
435    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        }
449
450        if (!slob_last(prev) && b + units == next) {
451            units += slob_units(next);
452            set_slob(b, units, slob_next(next));
453        } else
454            set_slob(b, units, next);
455
456        if (prev + slob_units(prev) == b) {
457            units = slob_units(b) + slob_units(prev);
458            set_slob(prev, units, slob_next(b));
459        } else
460            set_slob(prev, slob_units(prev), b);
461    }
462out:
463    spin_unlock_irqrestore(&slob_lock, flags);
464}
465
466/*
467 * End of slob allocator proper. Begin kmem_cache_alloc and kmalloc frontend.
468 */
469
470void *__kmalloc_node(size_t size, gfp_t gfp, int node)
471{
472    unsigned int *m;
473    int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
474    void *ret;
475
476    lockdep_trace_alloc(gfp);
477
478    if (size < PAGE_SIZE - align) {
479        if (!size)
480            return ZERO_SIZE_PTR;
481
482        m = slob_alloc(size + align, gfp, align, node);
483
484        if (!m)
485            return NULL;
486        *m = size;
487        ret = (void *)m + align;
488
489        trace_kmalloc_node(_RET_IP_, ret,
490                   size, size + align, gfp, node);
491    } else {
492        unsigned int order = get_order(size);
493
494        ret = slob_new_pages(gfp | __GFP_COMP, get_order(size), node);
495        if (ret) {
496            struct page *page;
497            page = virt_to_page(ret);
498            page->private = size;
499        }
500
501        trace_kmalloc_node(_RET_IP_, ret,
502                   size, PAGE_SIZE << order, gfp, node);
503    }
504
505    kmemleak_alloc(ret, size, 1, gfp);
506    return ret;
507}
508EXPORT_SYMBOL(__kmalloc_node);
509
510void kfree(const void *block)
511{
512    struct slob_page *sp;
513
514    trace_kfree(_RET_IP_, block);
515
516    if (unlikely(ZERO_OR_NULL_PTR(block)))
517        return;
518    kmemleak_free(block);
519
520    sp = slob_page(block);
521    if (is_slob_page(sp)) {
522        int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
523        unsigned int *m = (unsigned int *)(block - align);
524        slob_free(m, *m + align);
525    } else
526        put_page(&sp->page);
527}
528EXPORT_SYMBOL(kfree);
529
530/* can't use ksize for kmem_cache_alloc memory, only kmalloc */
531size_t ksize(const void *block)
532{
533    struct slob_page *sp;
534
535    BUG_ON(!block);
536    if (unlikely(block == ZERO_SIZE_PTR))
537        return 0;
538
539    sp = slob_page(block);
540    if (is_slob_page(sp)) {
541        int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
542        unsigned int *m = (unsigned int *)(block - align);
543        return SLOB_UNITS(*m) * SLOB_UNIT;
544    } else
545        return sp->page.private;
546}
547EXPORT_SYMBOL(ksize);
548
549struct kmem_cache {
550    unsigned int size, align;
551    unsigned long flags;
552    const char *name;
553    void (*ctor)(void *);
554};
555
556struct kmem_cache *kmem_cache_create(const char *name, size_t size,
557    size_t align, unsigned long flags, void (*ctor)(void *))
558{
559    struct kmem_cache *c;
560
561    c = slob_alloc(sizeof(struct kmem_cache),
562        GFP_KERNEL, ARCH_KMALLOC_MINALIGN, -1);
563
564    if (c) {
565        c->name = name;
566        c->size = size;
567        if (flags & SLAB_DESTROY_BY_RCU) {
568            /* leave room for rcu footer at the end of object */
569            c->size += sizeof(struct slob_rcu);
570        }
571        c->flags = flags;
572        c->ctor = ctor;
573        /* ignore alignment unless it's forced */
574        c->align = (flags & SLAB_HWCACHE_ALIGN) ? SLOB_ALIGN : 0;
575        if (c->align < ARCH_SLAB_MINALIGN)
576            c->align = ARCH_SLAB_MINALIGN;
577        if (c->align < align)
578            c->align = align;
579    } else if (flags & SLAB_PANIC)
580        panic("Cannot create slab cache %s\n", name);
581
582    kmemleak_alloc(c, sizeof(struct kmem_cache), 1, GFP_KERNEL);
583    return c;
584}
585EXPORT_SYMBOL(kmem_cache_create);
586
587void kmem_cache_destroy(struct kmem_cache *c)
588{
589    kmemleak_free(c);
590    if (c->flags & SLAB_DESTROY_BY_RCU)
591        rcu_barrier();
592    slob_free(c, sizeof(struct kmem_cache));
593}
594EXPORT_SYMBOL(kmem_cache_destroy);
595
596void *kmem_cache_alloc_node(struct kmem_cache *c, gfp_t flags, int node)
597{
598    void *b;
599
600    if (c->size < PAGE_SIZE) {
601        b = slob_alloc(c->size, flags, c->align, node);
602        trace_kmem_cache_alloc_node(_RET_IP_, b, c->size,
603                        SLOB_UNITS(c->size) * SLOB_UNIT,
604                        flags, node);
605    } else {
606        b = slob_new_pages(flags, get_order(c->size), node);
607        trace_kmem_cache_alloc_node(_RET_IP_, b, c->size,
608                        PAGE_SIZE << get_order(c->size),
609                        flags, node);
610    }
611
612    if (c->ctor)
613        c->ctor(b);
614
615    kmemleak_alloc_recursive(b, c->size, 1, c->flags, flags);
616    return b;
617}
618EXPORT_SYMBOL(kmem_cache_alloc_node);
619
620static void __kmem_cache_free(void *b, int size)
621{
622    if (size < PAGE_SIZE)
623        slob_free(b, size);
624    else
625        slob_free_pages(b, get_order(size));
626}
627
628static void kmem_rcu_free(struct rcu_head *head)
629{
630    struct slob_rcu *slob_rcu = (struct slob_rcu *)head;
631    void *b = (void *)slob_rcu - (slob_rcu->size - sizeof(struct slob_rcu));
632
633    __kmem_cache_free(b, slob_rcu->size);
634}
635
636void kmem_cache_free(struct kmem_cache *c, void *b)
637{
638    kmemleak_free_recursive(b, c->flags);
639    if (unlikely(c->flags & SLAB_DESTROY_BY_RCU)) {
640        struct slob_rcu *slob_rcu;
641        slob_rcu = b + (c->size - sizeof(struct slob_rcu));
642        INIT_RCU_HEAD(&slob_rcu->head);
643        slob_rcu->size = c->size;
644        call_rcu(&slob_rcu->head, kmem_rcu_free);
645    } else {
646        __kmem_cache_free(b, c->size);
647    }
648
649    trace_kmem_cache_free(_RET_IP_, b);
650}
651EXPORT_SYMBOL(kmem_cache_free);
652
653unsigned int kmem_cache_size(struct kmem_cache *c)
654{
655    return c->size;
656}
657EXPORT_SYMBOL(kmem_cache_size);
658
659const char *kmem_cache_name(struct kmem_cache *c)
660{
661    return c->name;
662}
663EXPORT_SYMBOL(kmem_cache_name);
664
665int kmem_cache_shrink(struct kmem_cache *d)
666{
667    return 0;
668}
669EXPORT_SYMBOL(kmem_cache_shrink);
670
671int kmem_ptr_validate(struct kmem_cache *a, const void *b)
672{
673    return 0;
674}
675
676static unsigned int slob_ready __read_mostly;
677
678int slab_is_available(void)
679{
680    return slob_ready;
681}
682
683void __init kmem_cache_init(void)
684{
685    slob_ready = 1;
686}
687
688void __init kmem_cache_init_late(void)
689{
690    /* Nothing to do */
691}
692

Archive Download this file



interactive