Merge branch 'locking-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git...
[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         lockdep_trace_alloc(gfp);
479
480         if (size < PAGE_SIZE - align) {
481                 if (!size)
482                         return ZERO_SIZE_PTR;
483
484                 m = slob_alloc(size + align, gfp, align, node);
485                 if (!m)
486                         return NULL;
487                 *m = size;
488                 return (void *)m + align;
489         } else {
490                 void *ret;
491
492                 ret = slob_new_pages(gfp | __GFP_COMP, get_order(size), node);
493                 if (ret) {
494                         struct page *page;
495                         page = virt_to_page(ret);
496                         page->private = size;
497                 }
498                 return ret;
499         }
500 }
501 EXPORT_SYMBOL(__kmalloc_node);
502
503 void kfree(const void *block)
504 {
505         struct slob_page *sp;
506
507         if (unlikely(ZERO_OR_NULL_PTR(block)))
508                 return;
509
510         sp = slob_page(block);
511         if (is_slob_page(sp)) {
512                 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
513                 unsigned int *m = (unsigned int *)(block - align);
514                 slob_free(m, *m + align);
515         } else
516                 put_page(&sp->page);
517 }
518 EXPORT_SYMBOL(kfree);
519
520 /* can't use ksize for kmem_cache_alloc memory, only kmalloc */
521 size_t ksize(const void *block)
522 {
523         struct slob_page *sp;
524
525         BUG_ON(!block);
526         if (unlikely(block == ZERO_SIZE_PTR))
527                 return 0;
528
529         sp = slob_page(block);
530         if (is_slob_page(sp)) {
531                 int align = max(ARCH_KMALLOC_MINALIGN, ARCH_SLAB_MINALIGN);
532                 unsigned int *m = (unsigned int *)(block - align);
533                 return SLOB_UNITS(*m) * SLOB_UNIT;
534         } else
535                 return sp->page.private;
536 }
537 EXPORT_SYMBOL(ksize);
538
539 struct kmem_cache {
540         unsigned int size, align;
541         unsigned long flags;
542         const char *name;
543         void (*ctor)(void *);
544 };
545
546 struct kmem_cache *kmem_cache_create(const char *name, size_t size,
547         size_t align, unsigned long flags, void (*ctor)(void *))
548 {
549         struct kmem_cache *c;
550
551         c = slob_alloc(sizeof(struct kmem_cache),
552                 GFP_KERNEL, ARCH_KMALLOC_MINALIGN, -1);
553
554         if (c) {
555                 c->name = name;
556                 c->size = size;
557                 if (flags & SLAB_DESTROY_BY_RCU) {
558                         /* leave room for rcu footer at the end of object */
559                         c->size += sizeof(struct slob_rcu);
560                 }
561                 c->flags = flags;
562                 c->ctor = ctor;
563                 /* ignore alignment unless it's forced */
564                 c->align = (flags & SLAB_HWCACHE_ALIGN) ? SLOB_ALIGN : 0;
565                 if (c->align < ARCH_SLAB_MINALIGN)
566                         c->align = ARCH_SLAB_MINALIGN;
567                 if (c->align < align)
568                         c->align = align;
569         } else if (flags & SLAB_PANIC)
570                 panic("Cannot create slab cache %s\n", name);
571
572         return c;
573 }
574 EXPORT_SYMBOL(kmem_cache_create);
575
576 void kmem_cache_destroy(struct kmem_cache *c)
577 {
578         slob_free(c, sizeof(struct kmem_cache));
579 }
580 EXPORT_SYMBOL(kmem_cache_destroy);
581
582 void *kmem_cache_alloc_node(struct kmem_cache *c, gfp_t flags, int node)
583 {
584         void *b;
585
586         if (c->size < PAGE_SIZE)
587                 b = slob_alloc(c->size, flags, c->align, node);
588         else
589                 b = slob_new_pages(flags, get_order(c->size), node);
590
591         if (c->ctor)
592                 c->ctor(b);
593
594         return b;
595 }
596 EXPORT_SYMBOL(kmem_cache_alloc_node);
597
598 static void __kmem_cache_free(void *b, int size)
599 {
600         if (size < PAGE_SIZE)
601                 slob_free(b, size);
602         else
603                 slob_free_pages(b, get_order(size));
604 }
605
606 static void kmem_rcu_free(struct rcu_head *head)
607 {
608         struct slob_rcu *slob_rcu = (struct slob_rcu *)head;
609         void *b = (void *)slob_rcu - (slob_rcu->size - sizeof(struct slob_rcu));
610
611         __kmem_cache_free(b, slob_rcu->size);
612 }
613
614 void kmem_cache_free(struct kmem_cache *c, void *b)
615 {
616         if (unlikely(c->flags & SLAB_DESTROY_BY_RCU)) {
617                 struct slob_rcu *slob_rcu;
618                 slob_rcu = b + (c->size - sizeof(struct slob_rcu));
619                 INIT_RCU_HEAD(&slob_rcu->head);
620                 slob_rcu->size = c->size;
621                 call_rcu(&slob_rcu->head, kmem_rcu_free);
622         } else {
623                 __kmem_cache_free(b, c->size);
624         }
625 }
626 EXPORT_SYMBOL(kmem_cache_free);
627
628 unsigned int kmem_cache_size(struct kmem_cache *c)
629 {
630         return c->size;
631 }
632 EXPORT_SYMBOL(kmem_cache_size);
633
634 const char *kmem_cache_name(struct kmem_cache *c)
635 {
636         return c->name;
637 }
638 EXPORT_SYMBOL(kmem_cache_name);
639
640 int kmem_cache_shrink(struct kmem_cache *d)
641 {
642         return 0;
643 }
644 EXPORT_SYMBOL(kmem_cache_shrink);
645
646 int kmem_ptr_validate(struct kmem_cache *a, const void *b)
647 {
648         return 0;
649 }
650
651 static unsigned int slob_ready __read_mostly;
652
653 int slab_is_available(void)
654 {
655         return slob_ready;
656 }
657
658 void __init kmem_cache_init(void)
659 {
660         slob_ready = 1;
661 }