Merge branches 'topic/slob/cleanups', 'topic/slob/fixes', 'topic/slub/core', 'topic...
[linux-2.6.git] / 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_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/cache.h>
64 #include <linux/init.h>
65 #include <linux/module.h>
66 #include <linux/rcupdate.h>
67 #include <linux/list.h>
68 #include <asm/atomic.h>
69
70 /*
71  * slob_block has a field 'units', which indicates size of block if +ve,
72  * or offset of next block if -ve (in SLOB_UNITs).
73  *
74  * Free blocks of size 1 unit simply contain the offset of the next block.
75  * Those with larger size contain their size in the first SLOB_UNIT of
76  * memory, and the offset of the next free block in the second SLOB_UNIT.
77  */
78 #if PAGE_SIZE <= (32767 * 2)
79 typedef s16 slobidx_t;
80 #else
81 typedef s32 slobidx_t;
82 #endif
83
84 struct slob_block {
85         slobidx_t units;
86 };
87 typedef struct slob_block slob_t;
88
89 /*
90  * We use struct page fields to manage some slob allocation aspects,
91  * however to avoid the horrible mess in include/linux/mm_types.h, we'll
92  * just define our own struct page type variant here.
93  */
94 struct slob_page {
95         union {
96                 struct {
97                         unsigned long flags;    /* mandatory */
98                         atomic_t _count;        /* mandatory */
99                         slobidx_t units;        /* free units left in page */
100                         unsigned long pad[2];
101                         slob_t *free;           /* first free slob_t in page */
102                         struct list_head list;  /* linked list of free pages */
103                 };
104                 struct page page;
105         };
106 };
107 static inline void struct_slob_page_wrong_size(void)
108 { BUILD_BUG_ON(sizeof(struct slob_page) != sizeof(struct page)); }
109
110 /*
111  * free_slob_page: call before a slob_page is returned to the page allocator.
112  */
113 static inline void free_slob_page(struct slob_page *sp)
114 {
115         reset_page_mapcount(&sp->page);
116         sp->page.mapping = NULL;
117 }
118
119 /*
120  * All partially free slob pages go on these lists.
121  */
122 #define SLOB_BREAK1 256
123 #define SLOB_BREAK2 1024
124 static LIST_HEAD(free_slob_small);
125 static LIST_HEAD(free_slob_medium);
126 static LIST_HEAD(free_slob_large);
127
128 /*
129  * is_slob_page: True for all slob pages (false for bigblock pages)
130  */
131 static inline int is_slob_page(struct slob_page *sp)
132 {
133         return PageSlobPage((struct page *)sp);
134 }
135
136 static inline void set_slob_page(struct slob_page *sp)
137 {
138         __SetPageSlobPage((struct page *)sp);
139 }
140
141 static inline void clear_slob_page(struct slob_page *sp)
142 {
143         __ClearPageSlobPage((struct page *)sp);
144 }
145
146 static inline struct slob_page *slob_page(const void *addr)
147 {
148         return (struct slob_page *)virt_to_page(addr);
149 }
150
151 /*
152  * slob_page_free: true for pages on free_slob_pages list.
153  */
154 static inline int slob_page_free(struct slob_page *sp)
155 {
156         return PageSlobFree((struct page *)sp);
157 }
158
159 static void set_slob_page_free(struct slob_page *sp, struct list_head *list)
160 {
161         list_add(&sp->list, list);
162         __SetPageSlobFree((struct page *)sp);
163 }
164
165 static inline void clear_slob_page_free(struct slob_page *sp)
166 {
167         list_del(&sp->list);
168         __ClearPageSlobFree((struct page *)sp);
169 }
170
171 #define SLOB_UNIT sizeof(slob_t)
172 #define SLOB_UNITS(size) (((size) + SLOB_UNIT - 1)/SLOB_UNIT)
173 #define SLOB_ALIGN L1_CACHE_BYTES
174
175 /*
176  * struct slob_rcu is inserted at the tail of allocated slob blocks, which
177  * were created with a SLAB_DESTROY_BY_RCU slab. slob_rcu is used to free
178  * the block using call_rcu.
179  */
180 struct slob_rcu {
181         struct rcu_head head;
182         int size;
183 };
184
185 /*
186  * slob_lock protects all slob allocator structures.
187  */
188 static DEFINE_SPINLOCK(slob_lock);
189
190 /*
191  * Encode the given size and next info into a free slob block s.
192  */
193 static void set_slob(slob_t *s, slobidx_t size, slob_t *next)
194 {
195         slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
196         slobidx_t offset = next - base;
197
198         if (size > 1) {
199                 s[0].units = size;
200                 s[1].units = offset;
201         } else
202                 s[0].units = -offset;
203 }
204
205 /*
206  * Return the size of a slob block.
207  */
208 static slobidx_t slob_units(slob_t *s)
209 {
210         if (s->units > 0)
211                 return s->units;
212         return 1;
213 }
214
215 /*
216  * Return the next free slob block pointer after this one.
217  */
218 static slob_t *slob_next(slob_t *s)
219 {
220         slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
221         slobidx_t next;
222
223         if (s[0].units < 0)
224                 next = -s[0].units;
225         else
226                 next = s[1].units;
227         return base+next;
228 }
229
230 /*
231  * Returns true if s is the last free block in its page.
232  */
233 static int slob_last(slob_t *s)
234 {
235         return !((unsigned long)slob_next(s) & ~PAGE_MASK);
236 }
237
238 static void *slob_new_pages(gfp_t gfp, int order, int node)
239 {
240         void *page;
241
242 #ifdef CONFIG_NUMA
243         if (node != -1)
244                 page = alloc_pages_node(node, gfp, order);
245         else
246 #endif
247                 page = alloc_pages(gfp, order);
248
249         if (!page)
250                 return NULL;
251
252         return page_address(page);
253 }
254
255 static void slob_free_pages(void *b, int order)
256 {
257         free_pages((unsigned long)b, order);
258 }
259
260 /*
261  * Allocate a slob block within a given slob_page sp.
262  */
263 static void *slob_page_alloc(struct slob_page *sp, size_t size, int align)
264 {
265         slob_t *prev, *cur, *aligned = NULL;
266         int delta = 0, units = SLOB_UNITS(size);
267
268         for (prev = NULL, cur = sp->free; ; prev = cur, cur = slob_next(cur)) {
269                 slobidx_t avail = slob_units(cur);
270
271                 if (align) {
272                         aligned = (slob_t *)ALIGN((unsigned long)cur, align);
273                         delta = aligned - cur;
274                 }
275                 if (avail >= units + delta) { /* room enough? */
276                         slob_t *next;
277
278                         if (delta) { /* need to fragment head to align? */
279                                 next = slob_next(cur);
280                                 set_slob(aligned, avail - delta, next);
281                                 set_slob(cur, delta, aligned);
282                                 prev = cur;
283                                 cur = aligned;
284                                 avail = slob_units(cur);
285                         }
286
287                         next = slob_next(cur);
288                         if (avail == units) { /* exact fit? unlink. */
289                                 if (prev)
290                                         set_slob(prev, slob_units(prev), next);
291                                 else
292                                         sp->free = next;
293                         } else { /* fragment */
294                                 if (prev)
295                                         set_slob(prev, slob_units(prev), cur + units);
296                                 else
297                                         sp->free = cur + units;
298                                 set_slob(cur + units, avail - units, next);
299                         }
300
301                         sp->units -= units;
302                         if (!sp->units)
303                                 clear_slob_page_free(sp);
304                         return cur;
305                 }
306                 if (slob_last(cur))
307                         return NULL;
308         }
309 }
310
311 /*
312  * slob_alloc: entry point into the slob allocator.
313  */
314 static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
315 {
316         struct slob_page *sp;
317         struct list_head *prev;
318         struct list_head *slob_list;
319         slob_t *b = NULL;
320         unsigned long flags;
321
322         if (size < SLOB_BREAK1)
323                 slob_list = &free_slob_small;
324         else if (size < SLOB_BREAK2)
325                 slob_list = &free_slob_medium;
326         else
327                 slob_list = &free_slob_large;
328
329         spin_lock_irqsave(&slob_lock, flags);
330         /* Iterate through each partially free page, try to find room */
331         list_for_each_entry(sp, slob_list, list) {
332 #ifdef CONFIG_NUMA
333                 /*
334                  * If there's a node specification, search for a partial
335                  * page with a matching node id in the freelist.
336                  */
337                 if (node != -1 && page_to_nid(&sp->page) != node)
338                         continue;
339 #endif
340                 /* Enough room on this page? */
341                 if (sp->units < SLOB_UNITS(size))
342                         continue;
343
344                 /* Attempt to alloc */
345                 prev = sp->list.prev;
346                 b = slob_page_alloc(sp, size, align);
347                 if (!b)
348                         continue;
349
350                 /* Improve fragment distribution and reduce our average
351                  * search time by starting our next search here. (see
352                  * Knuth vol 1, sec 2.5, pg 449) */
353                 if (prev != slob_list->prev &&
354                                 slob_list->next != prev->next)
355                         list_move_tail(slob_list, prev->next);
356                 break;
357         }
358         spin_unlock_irqrestore(&slob_lock, flags);
359
360         /* Not enough space: must allocate a new page */
361         if (!b) {
362                 b = slob_new_pages(gfp & ~__GFP_ZERO, 0, node);
363                 if (!b)
364                         return NULL;
365                 sp = slob_page(b);
366                 set_slob_page(sp);
367
368                 spin_lock_irqsave(&slob_lock, flags);
369                 sp->units = SLOB_UNITS(PAGE_SIZE);
370                 sp->free = b;
371                 INIT_LIST_HEAD(&sp->list);
372                 set_slob(b, SLOB_UNITS(PAGE_SIZE), b + SLOB_UNITS(PAGE_SIZE));
373                 set_slob_page_free(sp, slob_list);
374                 b = slob_page_alloc(sp, size, align);
375                 BUG_ON(!b);
376                 spin_unlock_irqrestore(&slob_lock, flags);
377         }
378         if (unlikely((gfp & __GFP_ZERO) && b))
379                 memset(b, 0, size);
380         return b;
381 }
382
383 /*
384  * slob_free: entry point into the slob allocator.
385  */
386 static void slob_free(void *block, int size)
387 {
388         struct slob_page *sp;
389         slob_t *prev, *next, *b = (slob_t *)block;
390         slobidx_t units;
391         unsigned long flags;
392
393         if (unlikely(ZERO_OR_NULL_PTR(block)))
394                 return;
395         BUG_ON(!size);
396
397         sp = slob_page(block);
398         units = SLOB_UNITS(size);
399
400         spin_lock_irqsave(&slob_lock, flags);
401
402         if (sp->units + units == SLOB_UNITS(PAGE_SIZE)) {
403                 /* Go directly to page allocator. Do not pass slob allocator */
404                 if (slob_page_free(sp))
405                         clear_slob_page_free(sp);
406                 spin_unlock_irqrestore(&slob_lock, flags);
407                 clear_slob_page(sp);
408                 free_slob_page(sp);
409                 free_page((unsigned long)b);
410                 return;
411         }
412
413         if (!slob_page_free(sp)) {
414                 /* This slob page is about to become partially free. Easy! */
415                 sp->units = units;
416                 sp->free = b;
417                 set_slob(b, units,
418                         (void *)((unsigned long)(b +
419                                         SLOB_UNITS(PAGE_SIZE)) & PAGE_MASK));
420                 set_slob_page_free(sp, &free_slob_small);
421                 goto out;
422         }
423
424         /*
425          * Otherwise the page is already partially free, so find reinsertion
426          * point.
427          */
428         sp->units += units;
429
430         if (b < sp->free) {
431                 if (b + units == sp->free) {
432                         units += slob_units(sp->free);
433                         sp->free = slob_next(sp->free);
434                 }
435                 set_slob(b, units, sp->free);
436                 sp->free = b;
437         } else {
438                 prev = sp->free;
439                 next = slob_next(prev);
440                 while (b > next) {
441                         prev = next;
442                         next = slob_next(prev);
443                 }
444
445                 if (!slob_last(prev) && b + units == next) {
446                         units += slob_units(next);
447                         set_slob(b, units, slob_next(next));
448                 } else
449                         set_slob(b, units, next);
450
451                 if (prev + slob_units(prev) == b) {
452                         units = slob_units(b) + slob_units(prev);
453                         set_slob(prev, units, slob_next(b));
454                 } else
455                         set_slob(prev, slob_units(prev), b);
456         }
457 out:
458         spin_unlock_irqrestore(&slob_lock, flags);
459 }
460
461 /*
462  * End of slob allocator proper. Begin kmem_cache_alloc and kmalloc frontend.
463  */
464
465 #ifndef ARCH_KMALLOC_MINALIGN
466 #define ARCH_KMALLOC_MINALIGN __alignof__(unsigned long)
467 #endif
468
469 #ifndef ARCH_SLAB_MINALIGN
470 #define ARCH_SLAB_MINALIGN __alignof__(unsigned long)
471 #endif
472
473 void *__kmalloc_node(size_t size, gfp_t gfp, int node)
474 {
475         unsigned int *m;
476         int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
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                 if (!m)
484                         return NULL;
485                 *m = size;
486                 return (void *)m + align;
487         } else {
488                 void *ret;
489
490                 ret = slob_new_pages(gfp | __GFP_COMP, get_order(size), node);
491                 if (ret) {
492                         struct page *page;
493                         page = virt_to_page(ret);
494                         page->private = size;
495                 }
496                 return ret;
497         }
498 }
499 EXPORT_SYMBOL(__kmalloc_node);
500
501 void kfree(const void *block)
502 {
503         struct slob_page *sp;
504
505         if (unlikely(ZERO_OR_NULL_PTR(block)))
506                 return;
507
508         sp = slob_page(block);
509         if (is_slob_page(sp)) {
510                 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
511                 unsigned int *m = (unsigned int *)(block - align);
512                 slob_free(m, *m + align);
513         } else
514                 put_page(&sp->page);
515 }
516 EXPORT_SYMBOL(kfree);
517
518 /* can't use ksize for kmem_cache_alloc memory, only kmalloc */
519 size_t ksize(const void *block)
520 {
521         struct slob_page *sp;
522
523         BUG_ON(!block);
524         if (unlikely(block == ZERO_SIZE_PTR))
525                 return 0;
526
527         sp = slob_page(block);
528         if (is_slob_page(sp)) {
529                 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
530                 unsigned int *m = (unsigned int *)(block - align);
531                 return SLOB_UNITS(*m) * SLOB_UNIT;
532         } else
533                 return sp->page.private;
534 }
535 EXPORT_SYMBOL(ksize);
536
537 struct kmem_cache {
538         unsigned int size, align;
539         unsigned long flags;
540         const char *name;
541         void (*ctor)(void *);
542 };
543
544 struct kmem_cache *kmem_cache_create(const char *name, size_t size,
545         size_t align, unsigned long flags, void (*ctor)(void *))
546 {
547         struct kmem_cache *c;
548
549         c = slob_alloc(sizeof(struct kmem_cache),
550                 GFP_KERNEL, ARCH_KMALLOC_MINALIGN, -1);
551
552         if (c) {
553                 c->name = name;
554                 c->size = size;
555                 if (flags & SLAB_DESTROY_BY_RCU) {
556                         /* leave room for rcu footer at the end of object */
557                         c->size += sizeof(struct slob_rcu);
558                 }
559                 c->flags = flags;
560                 c->ctor = ctor;
561                 /* ignore alignment unless it's forced */
562                 c->align = (flags & SLAB_HWCACHE_ALIGN) ? SLOB_ALIGN : 0;
563                 if (c->align < ARCH_SLAB_MINALIGN)
564                         c->align = ARCH_SLAB_MINALIGN;
565                 if (c->align < align)
566                         c->align = align;
567         } else if (flags & SLAB_PANIC)
568                 panic("Cannot create slab cache %s\n", name);
569
570         return c;
571 }
572 EXPORT_SYMBOL(kmem_cache_create);
573
574 void kmem_cache_destroy(struct kmem_cache *c)
575 {
576         slob_free(c, sizeof(struct kmem_cache));
577 }
578 EXPORT_SYMBOL(kmem_cache_destroy);
579
580 void *kmem_cache_alloc_node(struct kmem_cache *c, gfp_t flags, int node)
581 {
582         void *b;
583
584         if (c->size < PAGE_SIZE)
585                 b = slob_alloc(c->size, flags, c->align, node);
586         else
587                 b = slob_new_pages(flags, get_order(c->size), node);
588
589         if (c->ctor)
590                 c->ctor(b);
591
592         return b;
593 }
594 EXPORT_SYMBOL(kmem_cache_alloc_node);
595
596 static void __kmem_cache_free(void *b, int size)
597 {
598         if (size < PAGE_SIZE)
599                 slob_free(b, size);
600         else
601                 slob_free_pages(b, get_order(size));
602 }
603
604 static void kmem_rcu_free(struct rcu_head *head)
605 {
606         struct slob_rcu *slob_rcu = (struct slob_rcu *)head;
607         void *b = (void *)slob_rcu - (slob_rcu->size - sizeof(struct slob_rcu));
608
609         __kmem_cache_free(b, slob_rcu->size);
610 }
611
612 void kmem_cache_free(struct kmem_cache *c, void *b)
613 {
614         if (unlikely(c->flags & SLAB_DESTROY_BY_RCU)) {
615                 struct slob_rcu *slob_rcu;
616                 slob_rcu = b + (c->size - sizeof(struct slob_rcu));
617                 INIT_RCU_HEAD(&slob_rcu->head);
618                 slob_rcu->size = c->size;
619                 call_rcu(&slob_rcu->head, kmem_rcu_free);
620         } else {
621                 __kmem_cache_free(b, c->size);
622         }
623 }
624 EXPORT_SYMBOL(kmem_cache_free);
625
626 unsigned int kmem_cache_size(struct kmem_cache *c)
627 {
628         return c->size;
629 }
630 EXPORT_SYMBOL(kmem_cache_size);
631
632 const char *kmem_cache_name(struct kmem_cache *c)
633 {
634         return c->name;
635 }
636 EXPORT_SYMBOL(kmem_cache_name);
637
638 int kmem_cache_shrink(struct kmem_cache *d)
639 {
640         return 0;
641 }
642 EXPORT_SYMBOL(kmem_cache_shrink);
643
644 int kmem_ptr_validate(struct kmem_cache *a, const void *b)
645 {
646         return 0;
647 }
648
649 static unsigned int slob_ready __read_mostly;
650
651 int slab_is_available(void)
652 {
653         return slob_ready;
654 }
655
656 void __init kmem_cache_init(void)
657 {
658         slob_ready = 1;
659 }