slob: remove bigblock tracking
[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  * How SLOB works:
7  *
8  * The core of SLOB is a traditional K&R style heap allocator, with
9  * support for returning aligned objects. The granularity of this
10  * allocator is 4 bytes on 32-bit and 8 bytes on 64-bit, though it
11  * could be as low as 2 if the compiler alignment requirements allow.
12  *
13  * The slob heap is a linked list of pages from __get_free_page, and
14  * within each page, there is a singly-linked list of free blocks (slob_t).
15  * The heap is grown on demand and allocation from the heap is currently
16  * first-fit.
17  *
18  * Above this is an implementation of kmalloc/kfree. Blocks returned
19  * from kmalloc are 4-byte aligned and prepended with a 4-byte header.
20  * If kmalloc is asked for objects of PAGE_SIZE or larger, it calls
21  * __get_free_pages directly, allocating compound pages so the page order
22  * does not have to be separately tracked, and also stores the exact
23  * allocation size in page->private so that it can be used to accurately
24  * provide ksize(). These objects are detected in kfree() because slob_page()
25  * is false for them.
26  *
27  * SLAB is emulated on top of SLOB by simply calling constructors and
28  * destructors for every SLAB allocation. Objects are returned with the
29  * 4-byte alignment unless the SLAB_HWCACHE_ALIGN flag is set, in which
30  * case the low-level allocator will fragment blocks to create the proper
31  * alignment. Again, objects of page-size or greater are allocated by
32  * calling __get_free_pages. As SLAB objects know their size, no separate
33  * size bookkeeping is necessary and there is essentially no allocation
34  * space overhead, and compound pages aren't needed for multi-page
35  * allocations.
36  */
37
38 #include <linux/kernel.h>
39 #include <linux/slab.h>
40 #include <linux/mm.h>
41 #include <linux/cache.h>
42 #include <linux/init.h>
43 #include <linux/module.h>
44 #include <linux/rcupdate.h>
45 #include <linux/list.h>
46 #include <asm/atomic.h>
47
48 /* SLOB_MIN_ALIGN == sizeof(long) */
49 #if BITS_PER_BYTE == 32
50 #define SLOB_MIN_ALIGN  4
51 #else
52 #define SLOB_MIN_ALIGN  8
53 #endif
54
55 /*
56  * slob_block has a field 'units', which indicates size of block if +ve,
57  * or offset of next block if -ve (in SLOB_UNITs).
58  *
59  * Free blocks of size 1 unit simply contain the offset of the next block.
60  * Those with larger size contain their size in the first SLOB_UNIT of
61  * memory, and the offset of the next free block in the second SLOB_UNIT.
62  */
63 #if PAGE_SIZE <= (32767 * SLOB_MIN_ALIGN)
64 typedef s16 slobidx_t;
65 #else
66 typedef s32 slobidx_t;
67 #endif
68
69 /*
70  * Align struct slob_block to long for now, but can some embedded
71  * architectures get away with less?
72  */
73 struct slob_block {
74         slobidx_t units;
75 } __attribute__((aligned(SLOB_MIN_ALIGN)));
76 typedef struct slob_block slob_t;
77
78 /*
79  * We use struct page fields to manage some slob allocation aspects,
80  * however to avoid the horrible mess in include/linux/mm_types.h, we'll
81  * just define our own struct page type variant here.
82  */
83 struct slob_page {
84         union {
85                 struct {
86                         unsigned long flags;    /* mandatory */
87                         atomic_t _count;        /* mandatory */
88                         slobidx_t units;        /* free units left in page */
89                         unsigned long pad[2];
90                         slob_t *free;           /* first free slob_t in page */
91                         struct list_head list;  /* linked list of free pages */
92                 };
93                 struct page page;
94         };
95 };
96 static inline void struct_slob_page_wrong_size(void)
97 { BUILD_BUG_ON(sizeof(struct slob_page) != sizeof(struct page)); }
98
99 /*
100  * free_slob_page: call before a slob_page is returned to the page allocator.
101  */
102 static inline void free_slob_page(struct slob_page *sp)
103 {
104         reset_page_mapcount(&sp->page);
105         sp->page.mapping = NULL;
106 }
107
108 /*
109  * All (partially) free slob pages go on this list.
110  */
111 static LIST_HEAD(free_slob_pages);
112
113 /*
114  * slob_page: True for all slob pages (false for bigblock pages)
115  */
116 static inline int slob_page(struct slob_page *sp)
117 {
118         return test_bit(PG_active, &sp->flags);
119 }
120
121 static inline void set_slob_page(struct slob_page *sp)
122 {
123         __set_bit(PG_active, &sp->flags);
124 }
125
126 static inline void clear_slob_page(struct slob_page *sp)
127 {
128         __clear_bit(PG_active, &sp->flags);
129 }
130
131 /*
132  * slob_page_free: true for pages on free_slob_pages list.
133  */
134 static inline int slob_page_free(struct slob_page *sp)
135 {
136         return test_bit(PG_private, &sp->flags);
137 }
138
139 static inline void set_slob_page_free(struct slob_page *sp)
140 {
141         list_add(&sp->list, &free_slob_pages);
142         __set_bit(PG_private, &sp->flags);
143 }
144
145 static inline void clear_slob_page_free(struct slob_page *sp)
146 {
147         list_del(&sp->list);
148         __clear_bit(PG_private, &sp->flags);
149 }
150
151 #define SLOB_UNIT sizeof(slob_t)
152 #define SLOB_UNITS(size) (((size) + SLOB_UNIT - 1)/SLOB_UNIT)
153 #define SLOB_ALIGN L1_CACHE_BYTES
154
155 /*
156  * struct slob_rcu is inserted at the tail of allocated slob blocks, which
157  * were created with a SLAB_DESTROY_BY_RCU slab. slob_rcu is used to free
158  * the block using call_rcu.
159  */
160 struct slob_rcu {
161         struct rcu_head head;
162         int size;
163 };
164
165 /*
166  * slob_lock protects all slob allocator structures.
167  */
168 static DEFINE_SPINLOCK(slob_lock);
169
170 /*
171  * Encode the given size and next info into a free slob block s.
172  */
173 static void set_slob(slob_t *s, slobidx_t size, slob_t *next)
174 {
175         slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
176         slobidx_t offset = next - base;
177
178         if (size > 1) {
179                 s[0].units = size;
180                 s[1].units = offset;
181         } else
182                 s[0].units = -offset;
183 }
184
185 /*
186  * Return the size of a slob block.
187  */
188 static slobidx_t slob_units(slob_t *s)
189 {
190         if (s->units > 0)
191                 return s->units;
192         return 1;
193 }
194
195 /*
196  * Return the next free slob block pointer after this one.
197  */
198 static slob_t *slob_next(slob_t *s)
199 {
200         slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
201         slobidx_t next;
202
203         if (s[0].units < 0)
204                 next = -s[0].units;
205         else
206                 next = s[1].units;
207         return base+next;
208 }
209
210 /*
211  * Returns true if s is the last free block in its page.
212  */
213 static int slob_last(slob_t *s)
214 {
215         return !((unsigned long)slob_next(s) & ~PAGE_MASK);
216 }
217
218 /*
219  * Allocate a slob block within a given slob_page sp.
220  */
221 static void *slob_page_alloc(struct slob_page *sp, size_t size, int align)
222 {
223         slob_t *prev, *cur, *aligned = 0;
224         int delta = 0, units = SLOB_UNITS(size);
225
226         for (prev = NULL, cur = sp->free; ; prev = cur, cur = slob_next(cur)) {
227                 slobidx_t avail = slob_units(cur);
228
229                 if (align) {
230                         aligned = (slob_t *)ALIGN((unsigned long)cur, align);
231                         delta = aligned - cur;
232                 }
233                 if (avail >= units + delta) { /* room enough? */
234                         slob_t *next;
235
236                         if (delta) { /* need to fragment head to align? */
237                                 next = slob_next(cur);
238                                 set_slob(aligned, avail - delta, next);
239                                 set_slob(cur, delta, aligned);
240                                 prev = cur;
241                                 cur = aligned;
242                                 avail = slob_units(cur);
243                         }
244
245                         next = slob_next(cur);
246                         if (avail == units) { /* exact fit? unlink. */
247                                 if (prev)
248                                         set_slob(prev, slob_units(prev), next);
249                                 else
250                                         sp->free = next;
251                         } else { /* fragment */
252                                 if (prev)
253                                         set_slob(prev, slob_units(prev), cur + units);
254                                 else
255                                         sp->free = cur + units;
256                                 set_slob(cur + units, avail - units, next);
257                         }
258
259                         sp->units -= units;
260                         if (!sp->units)
261                                 clear_slob_page_free(sp);
262                         return cur;
263                 }
264                 if (slob_last(cur))
265                         return NULL;
266         }
267 }
268
269 /*
270  * slob_alloc: entry point into the slob allocator.
271  */
272 static void *slob_alloc(size_t size, gfp_t gfp, int align)
273 {
274         struct slob_page *sp;
275         slob_t *b = NULL;
276         unsigned long flags;
277
278         spin_lock_irqsave(&slob_lock, flags);
279         /* Iterate through each partially free page, try to find room */
280         list_for_each_entry(sp, &free_slob_pages, list) {
281                 if (sp->units >= SLOB_UNITS(size)) {
282                         b = slob_page_alloc(sp, size, align);
283                         if (b)
284                                 break;
285                 }
286         }
287         spin_unlock_irqrestore(&slob_lock, flags);
288
289         /* Not enough space: must allocate a new page */
290         if (!b) {
291                 b = (slob_t *)__get_free_page(gfp);
292                 if (!b)
293                         return 0;
294                 sp = (struct slob_page *)virt_to_page(b);
295                 set_slob_page(sp);
296
297                 spin_lock_irqsave(&slob_lock, flags);
298                 sp->units = SLOB_UNITS(PAGE_SIZE);
299                 sp->free = b;
300                 INIT_LIST_HEAD(&sp->list);
301                 set_slob(b, SLOB_UNITS(PAGE_SIZE), b + SLOB_UNITS(PAGE_SIZE));
302                 set_slob_page_free(sp);
303                 b = slob_page_alloc(sp, size, align);
304                 BUG_ON(!b);
305                 spin_unlock_irqrestore(&slob_lock, flags);
306         }
307         return b;
308 }
309
310 /*
311  * slob_free: entry point into the slob allocator.
312  */
313 static void slob_free(void *block, int size)
314 {
315         struct slob_page *sp;
316         slob_t *prev, *next, *b = (slob_t *)block;
317         slobidx_t units;
318         unsigned long flags;
319
320         if (!block)
321                 return;
322         BUG_ON(!size);
323
324         sp = (struct slob_page *)virt_to_page(block);
325         units = SLOB_UNITS(size);
326
327         spin_lock_irqsave(&slob_lock, flags);
328
329         if (sp->units + units == SLOB_UNITS(PAGE_SIZE)) {
330                 /* Go directly to page allocator. Do not pass slob allocator */
331                 if (slob_page_free(sp))
332                         clear_slob_page_free(sp);
333                 clear_slob_page(sp);
334                 free_slob_page(sp);
335                 free_page((unsigned long)b);
336                 goto out;
337         }
338
339         if (!slob_page_free(sp)) {
340                 /* This slob page is about to become partially free. Easy! */
341                 sp->units = units;
342                 sp->free = b;
343                 set_slob(b, units,
344                         (void *)((unsigned long)(b +
345                                         SLOB_UNITS(PAGE_SIZE)) & PAGE_MASK));
346                 set_slob_page_free(sp);
347                 goto out;
348         }
349
350         /*
351          * Otherwise the page is already partially free, so find reinsertion
352          * point.
353          */
354         sp->units += units;
355
356         if (b < sp->free) {
357                 set_slob(b, units, sp->free);
358                 sp->free = b;
359         } else {
360                 prev = sp->free;
361                 next = slob_next(prev);
362                 while (b > next) {
363                         prev = next;
364                         next = slob_next(prev);
365                 }
366
367                 if (!slob_last(prev) && b + units == next) {
368                         units += slob_units(next);
369                         set_slob(b, units, slob_next(next));
370                 } else
371                         set_slob(b, units, next);
372
373                 if (prev + slob_units(prev) == b) {
374                         units = slob_units(b) + slob_units(prev);
375                         set_slob(prev, units, slob_next(b));
376                 } else
377                         set_slob(prev, slob_units(prev), b);
378         }
379 out:
380         spin_unlock_irqrestore(&slob_lock, flags);
381 }
382
383 /*
384  * End of slob allocator proper. Begin kmem_cache_alloc and kmalloc frontend.
385  */
386
387 void *__kmalloc(size_t size, gfp_t gfp)
388 {
389         if (size < PAGE_SIZE - SLOB_UNIT) {
390                 slob_t *m;
391                 m = slob_alloc(size + SLOB_UNIT, gfp, 0);
392                 if (m)
393                         m->units = size;
394                 return m+1;
395         } else {
396                 void *ret;
397
398                 ret = (void *) __get_free_pages(gfp | __GFP_COMP,
399                                                 get_order(size));
400                 if (ret) {
401                         struct page *page;
402                         page = virt_to_page(ret);
403                         page->private = size;
404                 }
405                 return ret;
406         }
407 }
408 EXPORT_SYMBOL(__kmalloc);
409
410 /**
411  * krealloc - reallocate memory. The contents will remain unchanged.
412  *
413  * @p: object to reallocate memory for.
414  * @new_size: how many bytes of memory are required.
415  * @flags: the type of memory to allocate.
416  *
417  * The contents of the object pointed to are preserved up to the
418  * lesser of the new and old sizes.  If @p is %NULL, krealloc()
419  * behaves exactly like kmalloc().  If @size is 0 and @p is not a
420  * %NULL pointer, the object pointed to is freed.
421  */
422 void *krealloc(const void *p, size_t new_size, gfp_t flags)
423 {
424         void *ret;
425
426         if (unlikely(!p))
427                 return kmalloc_track_caller(new_size, flags);
428
429         if (unlikely(!new_size)) {
430                 kfree(p);
431                 return NULL;
432         }
433
434         ret = kmalloc_track_caller(new_size, flags);
435         if (ret) {
436                 memcpy(ret, p, min(new_size, ksize(p)));
437                 kfree(p);
438         }
439         return ret;
440 }
441 EXPORT_SYMBOL(krealloc);
442
443 void kfree(const void *block)
444 {
445         struct slob_page *sp;
446
447         if (!block)
448                 return;
449
450         sp = (struct slob_page *)virt_to_page(block);
451         if (slob_page(sp)) {
452                 slob_t *m = (slob_t *)block - 1;
453                 slob_free(m, m->units + SLOB_UNIT);
454         } else
455                 put_page(&sp->page);
456 }
457
458 EXPORT_SYMBOL(kfree);
459
460 /* can't use ksize for kmem_cache_alloc memory, only kmalloc */
461 size_t ksize(const void *block)
462 {
463         struct slob_page *sp;
464
465         if (!block)
466                 return 0;
467
468         sp = (struct slob_page *)virt_to_page(block);
469         if (slob_page(sp))
470                 return ((slob_t *)block - 1)->units + SLOB_UNIT;
471         else
472                 return sp->page.private;
473 }
474
475 struct kmem_cache {
476         unsigned int size, align;
477         unsigned long flags;
478         const char *name;
479         void (*ctor)(void *, struct kmem_cache *, unsigned long);
480 };
481
482 struct kmem_cache *kmem_cache_create(const char *name, size_t size,
483         size_t align, unsigned long flags,
484         void (*ctor)(void*, struct kmem_cache *, unsigned long),
485         void (*dtor)(void*, struct kmem_cache *, unsigned long))
486 {
487         struct kmem_cache *c;
488
489         c = slob_alloc(sizeof(struct kmem_cache), flags, 0);
490
491         if (c) {
492                 c->name = name;
493                 c->size = size;
494                 if (flags & SLAB_DESTROY_BY_RCU) {
495                         /* leave room for rcu footer at the end of object */
496                         c->size += sizeof(struct slob_rcu);
497                 }
498                 c->flags = flags;
499                 c->ctor = ctor;
500                 /* ignore alignment unless it's forced */
501                 c->align = (flags & SLAB_HWCACHE_ALIGN) ? SLOB_ALIGN : 0;
502                 if (c->align < align)
503                         c->align = align;
504         } else if (flags & SLAB_PANIC)
505                 panic("Cannot create slab cache %s\n", name);
506
507         return c;
508 }
509 EXPORT_SYMBOL(kmem_cache_create);
510
511 void kmem_cache_destroy(struct kmem_cache *c)
512 {
513         slob_free(c, sizeof(struct kmem_cache));
514 }
515 EXPORT_SYMBOL(kmem_cache_destroy);
516
517 void *kmem_cache_alloc(struct kmem_cache *c, gfp_t flags)
518 {
519         void *b;
520
521         if (c->size < PAGE_SIZE)
522                 b = slob_alloc(c->size, flags, c->align);
523         else
524                 b = (void *)__get_free_pages(flags, get_order(c->size));
525
526         if (c->ctor)
527                 c->ctor(b, c, 0);
528
529         return b;
530 }
531 EXPORT_SYMBOL(kmem_cache_alloc);
532
533 void *kmem_cache_zalloc(struct kmem_cache *c, gfp_t flags)
534 {
535         void *ret = kmem_cache_alloc(c, flags);
536         if (ret)
537                 memset(ret, 0, c->size);
538
539         return ret;
540 }
541 EXPORT_SYMBOL(kmem_cache_zalloc);
542
543 static void __kmem_cache_free(void *b, int size)
544 {
545         if (size < PAGE_SIZE)
546                 slob_free(b, size);
547         else
548                 free_pages((unsigned long)b, get_order(size));
549 }
550
551 static void kmem_rcu_free(struct rcu_head *head)
552 {
553         struct slob_rcu *slob_rcu = (struct slob_rcu *)head;
554         void *b = (void *)slob_rcu - (slob_rcu->size - sizeof(struct slob_rcu));
555
556         __kmem_cache_free(b, slob_rcu->size);
557 }
558
559 void kmem_cache_free(struct kmem_cache *c, void *b)
560 {
561         if (unlikely(c->flags & SLAB_DESTROY_BY_RCU)) {
562                 struct slob_rcu *slob_rcu;
563                 slob_rcu = b + (c->size - sizeof(struct slob_rcu));
564                 INIT_RCU_HEAD(&slob_rcu->head);
565                 slob_rcu->size = c->size;
566                 call_rcu(&slob_rcu->head, kmem_rcu_free);
567         } else {
568                 __kmem_cache_free(b, c->size);
569         }
570 }
571 EXPORT_SYMBOL(kmem_cache_free);
572
573 unsigned int kmem_cache_size(struct kmem_cache *c)
574 {
575         return c->size;
576 }
577 EXPORT_SYMBOL(kmem_cache_size);
578
579 const char *kmem_cache_name(struct kmem_cache *c)
580 {
581         return c->name;
582 }
583 EXPORT_SYMBOL(kmem_cache_name);
584
585 int kmem_cache_shrink(struct kmem_cache *d)
586 {
587         return 0;
588 }
589 EXPORT_SYMBOL(kmem_cache_shrink);
590
591 int kmem_ptr_validate(struct kmem_cache *a, const void *b)
592 {
593         return 0;
594 }
595
596 void __init kmem_cache_init(void)
597 {
598 }