Merge branch 'master' of /home/trondmy/repositories/git/linux-2.6/
[linux-2.6] / mm / slub.c
1 /*
2  * SLUB: A slab allocator that limits cache line use instead of queuing
3  * objects in per cpu and per node lists.
4  *
5  * The allocator synchronizes using per slab locks and only
6  * uses a centralized lock to manage a pool of partial slabs.
7  *
8  * (C) 2007 SGI, Christoph Lameter <clameter@sgi.com>
9  */
10
11 #include <linux/mm.h>
12 #include <linux/module.h>
13 #include <linux/bit_spinlock.h>
14 #include <linux/interrupt.h>
15 #include <linux/bitops.h>
16 #include <linux/slab.h>
17 #include <linux/seq_file.h>
18 #include <linux/cpu.h>
19 #include <linux/cpuset.h>
20 #include <linux/mempolicy.h>
21 #include <linux/ctype.h>
22 #include <linux/kallsyms.h>
23
24 /*
25  * Lock order:
26  *   1. slab_lock(page)
27  *   2. slab->list_lock
28  *
29  *   The slab_lock protects operations on the object of a particular
30  *   slab and its metadata in the page struct. If the slab lock
31  *   has been taken then no allocations nor frees can be performed
32  *   on the objects in the slab nor can the slab be added or removed
33  *   from the partial or full lists since this would mean modifying
34  *   the page_struct of the slab.
35  *
36  *   The list_lock protects the partial and full list on each node and
37  *   the partial slab counter. If taken then no new slabs may be added or
38  *   removed from the lists nor make the number of partial slabs be modified.
39  *   (Note that the total number of slabs is an atomic value that may be
40  *   modified without taking the list lock).
41  *
42  *   The list_lock is a centralized lock and thus we avoid taking it as
43  *   much as possible. As long as SLUB does not have to handle partial
44  *   slabs, operations can continue without any centralized lock. F.e.
45  *   allocating a long series of objects that fill up slabs does not require
46  *   the list lock.
47  *
48  *   The lock order is sometimes inverted when we are trying to get a slab
49  *   off a list. We take the list_lock and then look for a page on the list
50  *   to use. While we do that objects in the slabs may be freed. We can
51  *   only operate on the slab if we have also taken the slab_lock. So we use
52  *   a slab_trylock() on the slab. If trylock was successful then no frees
53  *   can occur anymore and we can use the slab for allocations etc. If the
54  *   slab_trylock() does not succeed then frees are in progress in the slab and
55  *   we must stay away from it for a while since we may cause a bouncing
56  *   cacheline if we try to acquire the lock. So go onto the next slab.
57  *   If all pages are busy then we may allocate a new slab instead of reusing
58  *   a partial slab. A new slab has noone operating on it and thus there is
59  *   no danger of cacheline contention.
60  *
61  *   Interrupts are disabled during allocation and deallocation in order to
62  *   make the slab allocator safe to use in the context of an irq. In addition
63  *   interrupts are disabled to ensure that the processor does not change
64  *   while handling per_cpu slabs, due to kernel preemption.
65  *
66  * SLUB assigns one slab for allocation to each processor.
67  * Allocations only occur from these slabs called cpu slabs.
68  *
69  * Slabs with free elements are kept on a partial list and during regular
70  * operations no list for full slabs is used. If an object in a full slab is
71  * freed then the slab will show up again on the partial lists.
72  * We track full slabs for debugging purposes though because otherwise we
73  * cannot scan all objects.
74  *
75  * Slabs are freed when they become empty. Teardown and setup is
76  * minimal so we rely on the page allocators per cpu caches for
77  * fast frees and allocs.
78  *
79  * Overloading of page flags that are otherwise used for LRU management.
80  *
81  * PageActive           The slab is used as a cpu cache. Allocations
82  *                      may be performed from the slab. The slab is not
83  *                      on any slab list and cannot be moved onto one.
84  *                      The cpu slab may be equipped with an additioanl
85  *                      lockless_freelist that allows lockless access to
86  *                      free objects in addition to the regular freelist
87  *                      that requires the slab lock.
88  *
89  * PageError            Slab requires special handling due to debug
90  *                      options set. This moves slab handling out of
91  *                      the fast path and disables lockless freelists.
92  */
93
94 static inline int SlabDebug(struct page *page)
95 {
96 #ifdef CONFIG_SLUB_DEBUG
97         return PageError(page);
98 #else
99         return 0;
100 #endif
101 }
102
103 static inline void SetSlabDebug(struct page *page)
104 {
105 #ifdef CONFIG_SLUB_DEBUG
106         SetPageError(page);
107 #endif
108 }
109
110 static inline void ClearSlabDebug(struct page *page)
111 {
112 #ifdef CONFIG_SLUB_DEBUG
113         ClearPageError(page);
114 #endif
115 }
116
117 /*
118  * Issues still to be resolved:
119  *
120  * - The per cpu array is updated for each new slab and and is a remote
121  *   cacheline for most nodes. This could become a bouncing cacheline given
122  *   enough frequent updates. There are 16 pointers in a cacheline, so at
123  *   max 16 cpus could compete for the cacheline which may be okay.
124  *
125  * - Support PAGE_ALLOC_DEBUG. Should be easy to do.
126  *
127  * - Variable sizing of the per node arrays
128  */
129
130 /* Enable to test recovery from slab corruption on boot */
131 #undef SLUB_RESILIENCY_TEST
132
133 #if PAGE_SHIFT <= 12
134
135 /*
136  * Small page size. Make sure that we do not fragment memory
137  */
138 #define DEFAULT_MAX_ORDER 1
139 #define DEFAULT_MIN_OBJECTS 4
140
141 #else
142
143 /*
144  * Large page machines are customarily able to handle larger
145  * page orders.
146  */
147 #define DEFAULT_MAX_ORDER 2
148 #define DEFAULT_MIN_OBJECTS 8
149
150 #endif
151
152 /*
153  * Mininum number of partial slabs. These will be left on the partial
154  * lists even if they are empty. kmem_cache_shrink may reclaim them.
155  */
156 #define MIN_PARTIAL 2
157
158 /*
159  * Maximum number of desirable partial slabs.
160  * The existence of more partial slabs makes kmem_cache_shrink
161  * sort the partial list by the number of objects in the.
162  */
163 #define MAX_PARTIAL 10
164
165 #define DEBUG_DEFAULT_FLAGS (SLAB_DEBUG_FREE | SLAB_RED_ZONE | \
166                                 SLAB_POISON | SLAB_STORE_USER)
167
168 /*
169  * Set of flags that will prevent slab merging
170  */
171 #define SLUB_NEVER_MERGE (SLAB_RED_ZONE | SLAB_POISON | SLAB_STORE_USER | \
172                 SLAB_TRACE | SLAB_DESTROY_BY_RCU)
173
174 #define SLUB_MERGE_SAME (SLAB_DEBUG_FREE | SLAB_RECLAIM_ACCOUNT | \
175                 SLAB_CACHE_DMA)
176
177 #ifndef ARCH_KMALLOC_MINALIGN
178 #define ARCH_KMALLOC_MINALIGN __alignof__(unsigned long long)
179 #endif
180
181 #ifndef ARCH_SLAB_MINALIGN
182 #define ARCH_SLAB_MINALIGN __alignof__(unsigned long long)
183 #endif
184
185 /* Internal SLUB flags */
186 #define __OBJECT_POISON 0x80000000      /* Poison object */
187
188 /* Not all arches define cache_line_size */
189 #ifndef cache_line_size
190 #define cache_line_size()       L1_CACHE_BYTES
191 #endif
192
193 static int kmem_size = sizeof(struct kmem_cache);
194
195 #ifdef CONFIG_SMP
196 static struct notifier_block slab_notifier;
197 #endif
198
199 static enum {
200         DOWN,           /* No slab functionality available */
201         PARTIAL,        /* kmem_cache_open() works but kmalloc does not */
202         UP,             /* Everything works but does not show up in sysfs */
203         SYSFS           /* Sysfs up */
204 } slab_state = DOWN;
205
206 /* A list of all slab caches on the system */
207 static DECLARE_RWSEM(slub_lock);
208 LIST_HEAD(slab_caches);
209
210 /*
211  * Tracking user of a slab.
212  */
213 struct track {
214         void *addr;             /* Called from address */
215         int cpu;                /* Was running on cpu */
216         int pid;                /* Pid context */
217         unsigned long when;     /* When did the operation occur */
218 };
219
220 enum track_item { TRACK_ALLOC, TRACK_FREE };
221
222 #if defined(CONFIG_SYSFS) && defined(CONFIG_SLUB_DEBUG)
223 static int sysfs_slab_add(struct kmem_cache *);
224 static int sysfs_slab_alias(struct kmem_cache *, const char *);
225 static void sysfs_slab_remove(struct kmem_cache *);
226 #else
227 static int sysfs_slab_add(struct kmem_cache *s) { return 0; }
228 static int sysfs_slab_alias(struct kmem_cache *s, const char *p) { return 0; }
229 static void sysfs_slab_remove(struct kmem_cache *s) {}
230 #endif
231
232 /********************************************************************
233  *                      Core slab cache functions
234  *******************************************************************/
235
236 int slab_is_available(void)
237 {
238         return slab_state >= UP;
239 }
240
241 static inline struct kmem_cache_node *get_node(struct kmem_cache *s, int node)
242 {
243 #ifdef CONFIG_NUMA
244         return s->node[node];
245 #else
246         return &s->local_node;
247 #endif
248 }
249
250 static inline int check_valid_pointer(struct kmem_cache *s,
251                                 struct page *page, const void *object)
252 {
253         void *base;
254
255         if (!object)
256                 return 1;
257
258         base = page_address(page);
259         if (object < base || object >= base + s->objects * s->size ||
260                 (object - base) % s->size) {
261                 return 0;
262         }
263
264         return 1;
265 }
266
267 /*
268  * Slow version of get and set free pointer.
269  *
270  * This version requires touching the cache lines of kmem_cache which
271  * we avoid to do in the fast alloc free paths. There we obtain the offset
272  * from the page struct.
273  */
274 static inline void *get_freepointer(struct kmem_cache *s, void *object)
275 {
276         return *(void **)(object + s->offset);
277 }
278
279 static inline void set_freepointer(struct kmem_cache *s, void *object, void *fp)
280 {
281         *(void **)(object + s->offset) = fp;
282 }
283
284 /* Loop over all objects in a slab */
285 #define for_each_object(__p, __s, __addr) \
286         for (__p = (__addr); __p < (__addr) + (__s)->objects * (__s)->size;\
287                         __p += (__s)->size)
288
289 /* Scan freelist */
290 #define for_each_free_object(__p, __s, __free) \
291         for (__p = (__free); __p; __p = get_freepointer((__s), __p))
292
293 /* Determine object index from a given position */
294 static inline int slab_index(void *p, struct kmem_cache *s, void *addr)
295 {
296         return (p - addr) / s->size;
297 }
298
299 #ifdef CONFIG_SLUB_DEBUG
300 /*
301  * Debug settings:
302  */
303 static int slub_debug;
304
305 static char *slub_debug_slabs;
306
307 /*
308  * Object debugging
309  */
310 static void print_section(char *text, u8 *addr, unsigned int length)
311 {
312         int i, offset;
313         int newline = 1;
314         char ascii[17];
315
316         ascii[16] = 0;
317
318         for (i = 0; i < length; i++) {
319                 if (newline) {
320                         printk(KERN_ERR "%10s 0x%p: ", text, addr + i);
321                         newline = 0;
322                 }
323                 printk(" %02x", addr[i]);
324                 offset = i % 16;
325                 ascii[offset] = isgraph(addr[i]) ? addr[i] : '.';
326                 if (offset == 15) {
327                         printk(" %s\n",ascii);
328                         newline = 1;
329                 }
330         }
331         if (!newline) {
332                 i %= 16;
333                 while (i < 16) {
334                         printk("   ");
335                         ascii[i] = ' ';
336                         i++;
337                 }
338                 printk(" %s\n", ascii);
339         }
340 }
341
342 static struct track *get_track(struct kmem_cache *s, void *object,
343         enum track_item alloc)
344 {
345         struct track *p;
346
347         if (s->offset)
348                 p = object + s->offset + sizeof(void *);
349         else
350                 p = object + s->inuse;
351
352         return p + alloc;
353 }
354
355 static void set_track(struct kmem_cache *s, void *object,
356                                 enum track_item alloc, void *addr)
357 {
358         struct track *p;
359
360         if (s->offset)
361                 p = object + s->offset + sizeof(void *);
362         else
363                 p = object + s->inuse;
364
365         p += alloc;
366         if (addr) {
367                 p->addr = addr;
368                 p->cpu = smp_processor_id();
369                 p->pid = current ? current->pid : -1;
370                 p->when = jiffies;
371         } else
372                 memset(p, 0, sizeof(struct track));
373 }
374
375 static void init_tracking(struct kmem_cache *s, void *object)
376 {
377         if (s->flags & SLAB_STORE_USER) {
378                 set_track(s, object, TRACK_FREE, NULL);
379                 set_track(s, object, TRACK_ALLOC, NULL);
380         }
381 }
382
383 static void print_track(const char *s, struct track *t)
384 {
385         if (!t->addr)
386                 return;
387
388         printk(KERN_ERR "%s: ", s);
389         __print_symbol("%s", (unsigned long)t->addr);
390         printk(" jiffies_ago=%lu cpu=%u pid=%d\n", jiffies - t->when, t->cpu, t->pid);
391 }
392
393 static void print_trailer(struct kmem_cache *s, u8 *p)
394 {
395         unsigned int off;       /* Offset of last byte */
396
397         if (s->flags & SLAB_RED_ZONE)
398                 print_section("Redzone", p + s->objsize,
399                         s->inuse - s->objsize);
400
401         printk(KERN_ERR "FreePointer 0x%p -> 0x%p\n",
402                         p + s->offset,
403                         get_freepointer(s, p));
404
405         if (s->offset)
406                 off = s->offset + sizeof(void *);
407         else
408                 off = s->inuse;
409
410         if (s->flags & SLAB_STORE_USER) {
411                 print_track("Last alloc", get_track(s, p, TRACK_ALLOC));
412                 print_track("Last free ", get_track(s, p, TRACK_FREE));
413                 off += 2 * sizeof(struct track);
414         }
415
416         if (off != s->size)
417                 /* Beginning of the filler is the free pointer */
418                 print_section("Filler", p + off, s->size - off);
419 }
420
421 static void object_err(struct kmem_cache *s, struct page *page,
422                         u8 *object, char *reason)
423 {
424         u8 *addr = page_address(page);
425
426         printk(KERN_ERR "*** SLUB %s: %s@0x%p slab 0x%p\n",
427                         s->name, reason, object, page);
428         printk(KERN_ERR "    offset=%tu flags=0x%04lx inuse=%u freelist=0x%p\n",
429                 object - addr, page->flags, page->inuse, page->freelist);
430         if (object > addr + 16)
431                 print_section("Bytes b4", object - 16, 16);
432         print_section("Object", object, min(s->objsize, 128));
433         print_trailer(s, object);
434         dump_stack();
435 }
436
437 static void slab_err(struct kmem_cache *s, struct page *page, char *reason, ...)
438 {
439         va_list args;
440         char buf[100];
441
442         va_start(args, reason);
443         vsnprintf(buf, sizeof(buf), reason, args);
444         va_end(args);
445         printk(KERN_ERR "*** SLUB %s: %s in slab @0x%p\n", s->name, buf,
446                 page);
447         dump_stack();
448 }
449
450 static void init_object(struct kmem_cache *s, void *object, int active)
451 {
452         u8 *p = object;
453
454         if (s->flags & __OBJECT_POISON) {
455                 memset(p, POISON_FREE, s->objsize - 1);
456                 p[s->objsize -1] = POISON_END;
457         }
458
459         if (s->flags & SLAB_RED_ZONE)
460                 memset(p + s->objsize,
461                         active ? SLUB_RED_ACTIVE : SLUB_RED_INACTIVE,
462                         s->inuse - s->objsize);
463 }
464
465 static int check_bytes(u8 *start, unsigned int value, unsigned int bytes)
466 {
467         while (bytes) {
468                 if (*start != (u8)value)
469                         return 0;
470                 start++;
471                 bytes--;
472         }
473         return 1;
474 }
475
476 /*
477  * Object layout:
478  *
479  * object address
480  *      Bytes of the object to be managed.
481  *      If the freepointer may overlay the object then the free
482  *      pointer is the first word of the object.
483  *
484  *      Poisoning uses 0x6b (POISON_FREE) and the last byte is
485  *      0xa5 (POISON_END)
486  *
487  * object + s->objsize
488  *      Padding to reach word boundary. This is also used for Redzoning.
489  *      Padding is extended by another word if Redzoning is enabled and
490  *      objsize == inuse.
491  *
492  *      We fill with 0xbb (RED_INACTIVE) for inactive objects and with
493  *      0xcc (RED_ACTIVE) for objects in use.
494  *
495  * object + s->inuse
496  *      Meta data starts here.
497  *
498  *      A. Free pointer (if we cannot overwrite object on free)
499  *      B. Tracking data for SLAB_STORE_USER
500  *      C. Padding to reach required alignment boundary or at mininum
501  *              one word if debuggin is on to be able to detect writes
502  *              before the word boundary.
503  *
504  *      Padding is done using 0x5a (POISON_INUSE)
505  *
506  * object + s->size
507  *      Nothing is used beyond s->size.
508  *
509  * If slabcaches are merged then the objsize and inuse boundaries are mostly
510  * ignored. And therefore no slab options that rely on these boundaries
511  * may be used with merged slabcaches.
512  */
513
514 static void restore_bytes(struct kmem_cache *s, char *message, u8 data,
515                                                 void *from, void *to)
516 {
517         printk(KERN_ERR "@@@ SLUB %s: Restoring %s (0x%x) from 0x%p-0x%p\n",
518                 s->name, message, data, from, to - 1);
519         memset(from, data, to - from);
520 }
521
522 static int check_pad_bytes(struct kmem_cache *s, struct page *page, u8 *p)
523 {
524         unsigned long off = s->inuse;   /* The end of info */
525
526         if (s->offset)
527                 /* Freepointer is placed after the object. */
528                 off += sizeof(void *);
529
530         if (s->flags & SLAB_STORE_USER)
531                 /* We also have user information there */
532                 off += 2 * sizeof(struct track);
533
534         if (s->size == off)
535                 return 1;
536
537         if (check_bytes(p + off, POISON_INUSE, s->size - off))
538                 return 1;
539
540         object_err(s, page, p, "Object padding check fails");
541
542         /*
543          * Restore padding
544          */
545         restore_bytes(s, "object padding", POISON_INUSE, p + off, p + s->size);
546         return 0;
547 }
548
549 static int slab_pad_check(struct kmem_cache *s, struct page *page)
550 {
551         u8 *p;
552         int length, remainder;
553
554         if (!(s->flags & SLAB_POISON))
555                 return 1;
556
557         p = page_address(page);
558         length = s->objects * s->size;
559         remainder = (PAGE_SIZE << s->order) - length;
560         if (!remainder)
561                 return 1;
562
563         if (!check_bytes(p + length, POISON_INUSE, remainder)) {
564                 slab_err(s, page, "Padding check failed");
565                 restore_bytes(s, "slab padding", POISON_INUSE, p + length,
566                         p + length + remainder);
567                 return 0;
568         }
569         return 1;
570 }
571
572 static int check_object(struct kmem_cache *s, struct page *page,
573                                         void *object, int active)
574 {
575         u8 *p = object;
576         u8 *endobject = object + s->objsize;
577
578         if (s->flags & SLAB_RED_ZONE) {
579                 unsigned int red =
580                         active ? SLUB_RED_ACTIVE : SLUB_RED_INACTIVE;
581
582                 if (!check_bytes(endobject, red, s->inuse - s->objsize)) {
583                         object_err(s, page, object,
584                         active ? "Redzone Active" : "Redzone Inactive");
585                         restore_bytes(s, "redzone", red,
586                                 endobject, object + s->inuse);
587                         return 0;
588                 }
589         } else {
590                 if ((s->flags & SLAB_POISON) && s->objsize < s->inuse &&
591                         !check_bytes(endobject, POISON_INUSE,
592                                         s->inuse - s->objsize)) {
593                 object_err(s, page, p, "Alignment padding check fails");
594                 /*
595                  * Fix it so that there will not be another report.
596                  *
597                  * Hmmm... We may be corrupting an object that now expects
598                  * to be longer than allowed.
599                  */
600                 restore_bytes(s, "alignment padding", POISON_INUSE,
601                         endobject, object + s->inuse);
602                 }
603         }
604
605         if (s->flags & SLAB_POISON) {
606                 if (!active && (s->flags & __OBJECT_POISON) &&
607                         (!check_bytes(p, POISON_FREE, s->objsize - 1) ||
608                                 p[s->objsize - 1] != POISON_END)) {
609
610                         object_err(s, page, p, "Poison check failed");
611                         restore_bytes(s, "Poison", POISON_FREE,
612                                                 p, p + s->objsize -1);
613                         restore_bytes(s, "Poison", POISON_END,
614                                         p + s->objsize - 1, p + s->objsize);
615                         return 0;
616                 }
617                 /*
618                  * check_pad_bytes cleans up on its own.
619                  */
620                 check_pad_bytes(s, page, p);
621         }
622
623         if (!s->offset && active)
624                 /*
625                  * Object and freepointer overlap. Cannot check
626                  * freepointer while object is allocated.
627                  */
628                 return 1;
629
630         /* Check free pointer validity */
631         if (!check_valid_pointer(s, page, get_freepointer(s, p))) {
632                 object_err(s, page, p, "Freepointer corrupt");
633                 /*
634                  * No choice but to zap it and thus loose the remainder
635                  * of the free objects in this slab. May cause
636                  * another error because the object count is now wrong.
637                  */
638                 set_freepointer(s, p, NULL);
639                 return 0;
640         }
641         return 1;
642 }
643
644 static int check_slab(struct kmem_cache *s, struct page *page)
645 {
646         VM_BUG_ON(!irqs_disabled());
647
648         if (!PageSlab(page)) {
649                 slab_err(s, page, "Not a valid slab page flags=%lx "
650                         "mapping=0x%p count=%d", page->flags, page->mapping,
651                         page_count(page));
652                 return 0;
653         }
654         if (page->offset * sizeof(void *) != s->offset) {
655                 slab_err(s, page, "Corrupted offset %lu flags=0x%lx "
656                         "mapping=0x%p count=%d",
657                         (unsigned long)(page->offset * sizeof(void *)),
658                         page->flags,
659                         page->mapping,
660                         page_count(page));
661                 return 0;
662         }
663         if (page->inuse > s->objects) {
664                 slab_err(s, page, "inuse %u > max %u @0x%p flags=%lx "
665                         "mapping=0x%p count=%d",
666                         s->name, page->inuse, s->objects, page->flags,
667                         page->mapping, page_count(page));
668                 return 0;
669         }
670         /* Slab_pad_check fixes things up after itself */
671         slab_pad_check(s, page);
672         return 1;
673 }
674
675 /*
676  * Determine if a certain object on a page is on the freelist. Must hold the
677  * slab lock to guarantee that the chains are in a consistent state.
678  */
679 static int on_freelist(struct kmem_cache *s, struct page *page, void *search)
680 {
681         int nr = 0;
682         void *fp = page->freelist;
683         void *object = NULL;
684
685         while (fp && nr <= s->objects) {
686                 if (fp == search)
687                         return 1;
688                 if (!check_valid_pointer(s, page, fp)) {
689                         if (object) {
690                                 object_err(s, page, object,
691                                         "Freechain corrupt");
692                                 set_freepointer(s, object, NULL);
693                                 break;
694                         } else {
695                                 slab_err(s, page, "Freepointer 0x%p corrupt",
696                                                                         fp);
697                                 page->freelist = NULL;
698                                 page->inuse = s->objects;
699                                 printk(KERN_ERR "@@@ SLUB %s: Freelist "
700                                         "cleared. Slab 0x%p\n",
701                                         s->name, page);
702                                 return 0;
703                         }
704                         break;
705                 }
706                 object = fp;
707                 fp = get_freepointer(s, object);
708                 nr++;
709         }
710
711         if (page->inuse != s->objects - nr) {
712                 slab_err(s, page, "Wrong object count. Counter is %d but "
713                         "counted were %d", s, page, page->inuse,
714                                                         s->objects - nr);
715                 page->inuse = s->objects - nr;
716                 printk(KERN_ERR "@@@ SLUB %s: Object count adjusted. "
717                         "Slab @0x%p\n", s->name, page);
718         }
719         return search == NULL;
720 }
721
722 /*
723  * Tracking of fully allocated slabs for debugging purposes.
724  */
725 static void add_full(struct kmem_cache_node *n, struct page *page)
726 {
727         spin_lock(&n->list_lock);
728         list_add(&page->lru, &n->full);
729         spin_unlock(&n->list_lock);
730 }
731
732 static void remove_full(struct kmem_cache *s, struct page *page)
733 {
734         struct kmem_cache_node *n;
735
736         if (!(s->flags & SLAB_STORE_USER))
737                 return;
738
739         n = get_node(s, page_to_nid(page));
740
741         spin_lock(&n->list_lock);
742         list_del(&page->lru);
743         spin_unlock(&n->list_lock);
744 }
745
746 static int alloc_object_checks(struct kmem_cache *s, struct page *page,
747                                                         void *object)
748 {
749         if (!check_slab(s, page))
750                 goto bad;
751
752         if (object && !on_freelist(s, page, object)) {
753                 slab_err(s, page, "Object 0x%p already allocated", object);
754                 goto bad;
755         }
756
757         if (!check_valid_pointer(s, page, object)) {
758                 object_err(s, page, object, "Freelist Pointer check fails");
759                 goto bad;
760         }
761
762         if (!object)
763                 return 1;
764
765         if (!check_object(s, page, object, 0))
766                 goto bad;
767
768         return 1;
769 bad:
770         if (PageSlab(page)) {
771                 /*
772                  * If this is a slab page then lets do the best we can
773                  * to avoid issues in the future. Marking all objects
774                  * as used avoids touching the remaining objects.
775                  */
776                 printk(KERN_ERR "@@@ SLUB: %s slab 0x%p. Marking all objects used.\n",
777                         s->name, page);
778                 page->inuse = s->objects;
779                 page->freelist = NULL;
780                 /* Fix up fields that may be corrupted */
781                 page->offset = s->offset / sizeof(void *);
782         }
783         return 0;
784 }
785
786 static int free_object_checks(struct kmem_cache *s, struct page *page,
787                                                         void *object)
788 {
789         if (!check_slab(s, page))
790                 goto fail;
791
792         if (!check_valid_pointer(s, page, object)) {
793                 slab_err(s, page, "Invalid object pointer 0x%p", object);
794                 goto fail;
795         }
796
797         if (on_freelist(s, page, object)) {
798                 slab_err(s, page, "Object 0x%p already free", object);
799                 goto fail;
800         }
801
802         if (!check_object(s, page, object, 1))
803                 return 0;
804
805         if (unlikely(s != page->slab)) {
806                 if (!PageSlab(page))
807                         slab_err(s, page, "Attempt to free object(0x%p) "
808                                 "outside of slab", object);
809                 else
810                 if (!page->slab) {
811                         printk(KERN_ERR
812                                 "SLUB <none>: no slab for object 0x%p.\n",
813                                                 object);
814                         dump_stack();
815                 }
816                 else
817                         slab_err(s, page, "object at 0x%p belongs "
818                                 "to slab %s", object, page->slab->name);
819                 goto fail;
820         }
821         return 1;
822 fail:
823         printk(KERN_ERR "@@@ SLUB: %s slab 0x%p object at 0x%p not freed.\n",
824                 s->name, page, object);
825         return 0;
826 }
827
828 static void trace(struct kmem_cache *s, struct page *page, void *object, int alloc)
829 {
830         if (s->flags & SLAB_TRACE) {
831                 printk(KERN_INFO "TRACE %s %s 0x%p inuse=%d fp=0x%p\n",
832                         s->name,
833                         alloc ? "alloc" : "free",
834                         object, page->inuse,
835                         page->freelist);
836
837                 if (!alloc)
838                         print_section("Object", (void *)object, s->objsize);
839
840                 dump_stack();
841         }
842 }
843
844 static int __init setup_slub_debug(char *str)
845 {
846         if (!str || *str != '=')
847                 slub_debug = DEBUG_DEFAULT_FLAGS;
848         else {
849                 str++;
850                 if (*str == 0 || *str == ',')
851                         slub_debug = DEBUG_DEFAULT_FLAGS;
852                 else
853                 for( ;*str && *str != ','; str++)
854                         switch (*str) {
855                         case 'f' : case 'F' :
856                                 slub_debug |= SLAB_DEBUG_FREE;
857                                 break;
858                         case 'z' : case 'Z' :
859                                 slub_debug |= SLAB_RED_ZONE;
860                                 break;
861                         case 'p' : case 'P' :
862                                 slub_debug |= SLAB_POISON;
863                                 break;
864                         case 'u' : case 'U' :
865                                 slub_debug |= SLAB_STORE_USER;
866                                 break;
867                         case 't' : case 'T' :
868                                 slub_debug |= SLAB_TRACE;
869                                 break;
870                         default:
871                                 printk(KERN_ERR "slub_debug option '%c' "
872                                         "unknown. skipped\n",*str);
873                         }
874         }
875
876         if (*str == ',')
877                 slub_debug_slabs = str + 1;
878         return 1;
879 }
880
881 __setup("slub_debug", setup_slub_debug);
882
883 static void kmem_cache_open_debug_check(struct kmem_cache *s)
884 {
885         /*
886          * The page->offset field is only 16 bit wide. This is an offset
887          * in units of words from the beginning of an object. If the slab
888          * size is bigger then we cannot move the free pointer behind the
889          * object anymore.
890          *
891          * On 32 bit platforms the limit is 256k. On 64bit platforms
892          * the limit is 512k.
893          *
894          * Debugging or ctor/dtors may create a need to move the free
895          * pointer. Fail if this happens.
896          */
897         if (s->size >= 65535 * sizeof(void *)) {
898                 BUG_ON(s->flags & (SLAB_RED_ZONE | SLAB_POISON |
899                                 SLAB_STORE_USER | SLAB_DESTROY_BY_RCU));
900                 BUG_ON(s->ctor || s->dtor);
901         }
902         else
903                 /*
904                  * Enable debugging if selected on the kernel commandline.
905                  */
906                 if (slub_debug && (!slub_debug_slabs ||
907                     strncmp(slub_debug_slabs, s->name,
908                         strlen(slub_debug_slabs)) == 0))
909                                 s->flags |= slub_debug;
910 }
911 #else
912
913 static inline int alloc_object_checks(struct kmem_cache *s,
914                 struct page *page, void *object) { return 0; }
915
916 static inline int free_object_checks(struct kmem_cache *s,
917                 struct page *page, void *object) { return 0; }
918
919 static inline void add_full(struct kmem_cache_node *n, struct page *page) {}
920 static inline void remove_full(struct kmem_cache *s, struct page *page) {}
921 static inline void trace(struct kmem_cache *s, struct page *page,
922                         void *object, int alloc) {}
923 static inline void init_object(struct kmem_cache *s,
924                         void *object, int active) {}
925 static inline void init_tracking(struct kmem_cache *s, void *object) {}
926 static inline int slab_pad_check(struct kmem_cache *s, struct page *page)
927                         { return 1; }
928 static inline int check_object(struct kmem_cache *s, struct page *page,
929                         void *object, int active) { return 1; }
930 static inline void set_track(struct kmem_cache *s, void *object,
931                         enum track_item alloc, void *addr) {}
932 static inline void kmem_cache_open_debug_check(struct kmem_cache *s) {}
933 #define slub_debug 0
934 #endif
935 /*
936  * Slab allocation and freeing
937  */
938 static struct page *allocate_slab(struct kmem_cache *s, gfp_t flags, int node)
939 {
940         struct page * page;
941         int pages = 1 << s->order;
942
943         if (s->order)
944                 flags |= __GFP_COMP;
945
946         if (s->flags & SLAB_CACHE_DMA)
947                 flags |= SLUB_DMA;
948
949         if (node == -1)
950                 page = alloc_pages(flags, s->order);
951         else
952                 page = alloc_pages_node(node, flags, s->order);
953
954         if (!page)
955                 return NULL;
956
957         mod_zone_page_state(page_zone(page),
958                 (s->flags & SLAB_RECLAIM_ACCOUNT) ?
959                 NR_SLAB_RECLAIMABLE : NR_SLAB_UNRECLAIMABLE,
960                 pages);
961
962         return page;
963 }
964
965 static void setup_object(struct kmem_cache *s, struct page *page,
966                                 void *object)
967 {
968         if (SlabDebug(page)) {
969                 init_object(s, object, 0);
970                 init_tracking(s, object);
971         }
972
973         if (unlikely(s->ctor))
974                 s->ctor(object, s, SLAB_CTOR_CONSTRUCTOR);
975 }
976
977 static struct page *new_slab(struct kmem_cache *s, gfp_t flags, int node)
978 {
979         struct page *page;
980         struct kmem_cache_node *n;
981         void *start;
982         void *end;
983         void *last;
984         void *p;
985
986         BUG_ON(flags & ~(GFP_DMA | GFP_LEVEL_MASK));
987
988         if (flags & __GFP_WAIT)
989                 local_irq_enable();
990
991         page = allocate_slab(s, flags & GFP_LEVEL_MASK, node);
992         if (!page)
993                 goto out;
994
995         n = get_node(s, page_to_nid(page));
996         if (n)
997                 atomic_long_inc(&n->nr_slabs);
998         page->offset = s->offset / sizeof(void *);
999         page->slab = s;
1000         page->flags |= 1 << PG_slab;
1001         if (s->flags & (SLAB_DEBUG_FREE | SLAB_RED_ZONE | SLAB_POISON |
1002                         SLAB_STORE_USER | SLAB_TRACE))
1003                 SetSlabDebug(page);
1004
1005         start = page_address(page);
1006         end = start + s->objects * s->size;
1007
1008         if (unlikely(s->flags & SLAB_POISON))
1009                 memset(start, POISON_INUSE, PAGE_SIZE << s->order);
1010
1011         last = start;
1012         for_each_object(p, s, start) {
1013                 setup_object(s, page, last);
1014                 set_freepointer(s, last, p);
1015                 last = p;
1016         }
1017         setup_object(s, page, last);
1018         set_freepointer(s, last, NULL);
1019
1020         page->freelist = start;
1021         page->lockless_freelist = NULL;
1022         page->inuse = 0;
1023 out:
1024         if (flags & __GFP_WAIT)
1025                 local_irq_disable();
1026         return page;
1027 }
1028
1029 static void __free_slab(struct kmem_cache *s, struct page *page)
1030 {
1031         int pages = 1 << s->order;
1032
1033         if (unlikely(SlabDebug(page) || s->dtor)) {
1034                 void *p;
1035
1036                 slab_pad_check(s, page);
1037                 for_each_object(p, s, page_address(page)) {
1038                         if (s->dtor)
1039                                 s->dtor(p, s, 0);
1040                         check_object(s, page, p, 0);
1041                 }
1042         }
1043
1044         mod_zone_page_state(page_zone(page),
1045                 (s->flags & SLAB_RECLAIM_ACCOUNT) ?
1046                 NR_SLAB_RECLAIMABLE : NR_SLAB_UNRECLAIMABLE,
1047                 - pages);
1048
1049         page->mapping = NULL;
1050         __free_pages(page, s->order);
1051 }
1052
1053 static void rcu_free_slab(struct rcu_head *h)
1054 {
1055         struct page *page;
1056
1057         page = container_of((struct list_head *)h, struct page, lru);
1058         __free_slab(page->slab, page);
1059 }
1060
1061 static void free_slab(struct kmem_cache *s, struct page *page)
1062 {
1063         if (unlikely(s->flags & SLAB_DESTROY_BY_RCU)) {
1064                 /*
1065                  * RCU free overloads the RCU head over the LRU
1066                  */
1067                 struct rcu_head *head = (void *)&page->lru;
1068
1069                 call_rcu(head, rcu_free_slab);
1070         } else
1071                 __free_slab(s, page);
1072 }
1073
1074 static void discard_slab(struct kmem_cache *s, struct page *page)
1075 {
1076         struct kmem_cache_node *n = get_node(s, page_to_nid(page));
1077
1078         atomic_long_dec(&n->nr_slabs);
1079         reset_page_mapcount(page);
1080         ClearSlabDebug(page);
1081         __ClearPageSlab(page);
1082         free_slab(s, page);
1083 }
1084
1085 /*
1086  * Per slab locking using the pagelock
1087  */
1088 static __always_inline void slab_lock(struct page *page)
1089 {
1090         bit_spin_lock(PG_locked, &page->flags);
1091 }
1092
1093 static __always_inline void slab_unlock(struct page *page)
1094 {
1095         bit_spin_unlock(PG_locked, &page->flags);
1096 }
1097
1098 static __always_inline int slab_trylock(struct page *page)
1099 {
1100         int rc = 1;
1101
1102         rc = bit_spin_trylock(PG_locked, &page->flags);
1103         return rc;
1104 }
1105
1106 /*
1107  * Management of partially allocated slabs
1108  */
1109 static void add_partial_tail(struct kmem_cache_node *n, struct page *page)
1110 {
1111         spin_lock(&n->list_lock);
1112         n->nr_partial++;
1113         list_add_tail(&page->lru, &n->partial);
1114         spin_unlock(&n->list_lock);
1115 }
1116
1117 static void add_partial(struct kmem_cache_node *n, struct page *page)
1118 {
1119         spin_lock(&n->list_lock);
1120         n->nr_partial++;
1121         list_add(&page->lru, &n->partial);
1122         spin_unlock(&n->list_lock);
1123 }
1124
1125 static void remove_partial(struct kmem_cache *s,
1126                                                 struct page *page)
1127 {
1128         struct kmem_cache_node *n = get_node(s, page_to_nid(page));
1129
1130         spin_lock(&n->list_lock);
1131         list_del(&page->lru);
1132         n->nr_partial--;
1133         spin_unlock(&n->list_lock);
1134 }
1135
1136 /*
1137  * Lock slab and remove from the partial list.
1138  *
1139  * Must hold list_lock.
1140  */
1141 static int lock_and_del_slab(struct kmem_cache_node *n, struct page *page)
1142 {
1143         if (slab_trylock(page)) {
1144                 list_del(&page->lru);
1145                 n->nr_partial--;
1146                 return 1;
1147         }
1148         return 0;
1149 }
1150
1151 /*
1152  * Try to allocate a partial slab from a specific node.
1153  */
1154 static struct page *get_partial_node(struct kmem_cache_node *n)
1155 {
1156         struct page *page;
1157
1158         /*
1159          * Racy check. If we mistakenly see no partial slabs then we
1160          * just allocate an empty slab. If we mistakenly try to get a
1161          * partial slab and there is none available then get_partials()
1162          * will return NULL.
1163          */
1164         if (!n || !n->nr_partial)
1165                 return NULL;
1166
1167         spin_lock(&n->list_lock);
1168         list_for_each_entry(page, &n->partial, lru)
1169                 if (lock_and_del_slab(n, page))
1170                         goto out;
1171         page = NULL;
1172 out:
1173         spin_unlock(&n->list_lock);
1174         return page;
1175 }
1176
1177 /*
1178  * Get a page from somewhere. Search in increasing NUMA distances.
1179  */
1180 static struct page *get_any_partial(struct kmem_cache *s, gfp_t flags)
1181 {
1182 #ifdef CONFIG_NUMA
1183         struct zonelist *zonelist;
1184         struct zone **z;
1185         struct page *page;
1186
1187         /*
1188          * The defrag ratio allows a configuration of the tradeoffs between
1189          * inter node defragmentation and node local allocations. A lower
1190          * defrag_ratio increases the tendency to do local allocations
1191          * instead of attempting to obtain partial slabs from other nodes.
1192          *
1193          * If the defrag_ratio is set to 0 then kmalloc() always
1194          * returns node local objects. If the ratio is higher then kmalloc()
1195          * may return off node objects because partial slabs are obtained
1196          * from other nodes and filled up.
1197          *
1198          * If /sys/slab/xx/defrag_ratio is set to 100 (which makes
1199          * defrag_ratio = 1000) then every (well almost) allocation will
1200          * first attempt to defrag slab caches on other nodes. This means
1201          * scanning over all nodes to look for partial slabs which may be
1202          * expensive if we do it every time we are trying to find a slab
1203          * with available objects.
1204          */
1205         if (!s->defrag_ratio || get_cycles() % 1024 > s->defrag_ratio)
1206                 return NULL;
1207
1208         zonelist = &NODE_DATA(slab_node(current->mempolicy))
1209                                         ->node_zonelists[gfp_zone(flags)];
1210         for (z = zonelist->zones; *z; z++) {
1211                 struct kmem_cache_node *n;
1212
1213                 n = get_node(s, zone_to_nid(*z));
1214
1215                 if (n && cpuset_zone_allowed_hardwall(*z, flags) &&
1216                                 n->nr_partial > MIN_PARTIAL) {
1217                         page = get_partial_node(n);
1218                         if (page)
1219                                 return page;
1220                 }
1221         }
1222 #endif
1223         return NULL;
1224 }
1225
1226 /*
1227  * Get a partial page, lock it and return it.
1228  */
1229 static struct page *get_partial(struct kmem_cache *s, gfp_t flags, int node)
1230 {
1231         struct page *page;
1232         int searchnode = (node == -1) ? numa_node_id() : node;
1233
1234         page = get_partial_node(get_node(s, searchnode));
1235         if (page || (flags & __GFP_THISNODE))
1236                 return page;
1237
1238         return get_any_partial(s, flags);
1239 }
1240
1241 /*
1242  * Move a page back to the lists.
1243  *
1244  * Must be called with the slab lock held.
1245  *
1246  * On exit the slab lock will have been dropped.
1247  */
1248 static void putback_slab(struct kmem_cache *s, struct page *page)
1249 {
1250         struct kmem_cache_node *n = get_node(s, page_to_nid(page));
1251
1252         if (page->inuse) {
1253
1254                 if (page->freelist)
1255                         add_partial(n, page);
1256                 else if (SlabDebug(page) && (s->flags & SLAB_STORE_USER))
1257                         add_full(n, page);
1258                 slab_unlock(page);
1259
1260         } else {
1261                 if (n->nr_partial < MIN_PARTIAL) {
1262                         /*
1263                          * Adding an empty slab to the partial slabs in order
1264                          * to avoid page allocator overhead. This slab needs
1265                          * to come after the other slabs with objects in
1266                          * order to fill them up. That way the size of the
1267                          * partial list stays small. kmem_cache_shrink can
1268                          * reclaim empty slabs from the partial list.
1269                          */
1270                         add_partial_tail(n, page);
1271                         slab_unlock(page);
1272                 } else {
1273                         slab_unlock(page);
1274                         discard_slab(s, page);
1275                 }
1276         }
1277 }
1278
1279 /*
1280  * Remove the cpu slab
1281  */
1282 static void deactivate_slab(struct kmem_cache *s, struct page *page, int cpu)
1283 {
1284         /*
1285          * Merge cpu freelist into freelist. Typically we get here
1286          * because both freelists are empty. So this is unlikely
1287          * to occur.
1288          */
1289         while (unlikely(page->lockless_freelist)) {
1290                 void **object;
1291
1292                 /* Retrieve object from cpu_freelist */
1293                 object = page->lockless_freelist;
1294                 page->lockless_freelist = page->lockless_freelist[page->offset];
1295
1296                 /* And put onto the regular freelist */
1297                 object[page->offset] = page->freelist;
1298                 page->freelist = object;
1299                 page->inuse--;
1300         }
1301         s->cpu_slab[cpu] = NULL;
1302         ClearPageActive(page);
1303
1304         putback_slab(s, page);
1305 }
1306
1307 static void flush_slab(struct kmem_cache *s, struct page *page, int cpu)
1308 {
1309         slab_lock(page);
1310         deactivate_slab(s, page, cpu);
1311 }
1312
1313 /*
1314  * Flush cpu slab.
1315  * Called from IPI handler with interrupts disabled.
1316  */
1317 static void __flush_cpu_slab(struct kmem_cache *s, int cpu)
1318 {
1319         struct page *page = s->cpu_slab[cpu];
1320
1321         if (likely(page))
1322                 flush_slab(s, page, cpu);
1323 }
1324
1325 static void flush_cpu_slab(void *d)
1326 {
1327         struct kmem_cache *s = d;
1328         int cpu = smp_processor_id();
1329
1330         __flush_cpu_slab(s, cpu);
1331 }
1332
1333 static void flush_all(struct kmem_cache *s)
1334 {
1335 #ifdef CONFIG_SMP
1336         on_each_cpu(flush_cpu_slab, s, 1, 1);
1337 #else
1338         unsigned long flags;
1339
1340         local_irq_save(flags);
1341         flush_cpu_slab(s);
1342         local_irq_restore(flags);
1343 #endif
1344 }
1345
1346 /*
1347  * Slow path. The lockless freelist is empty or we need to perform
1348  * debugging duties.
1349  *
1350  * Interrupts are disabled.
1351  *
1352  * Processing is still very fast if new objects have been freed to the
1353  * regular freelist. In that case we simply take over the regular freelist
1354  * as the lockless freelist and zap the regular freelist.
1355  *
1356  * If that is not working then we fall back to the partial lists. We take the
1357  * first element of the freelist as the object to allocate now and move the
1358  * rest of the freelist to the lockless freelist.
1359  *
1360  * And if we were unable to get a new slab from the partial slab lists then
1361  * we need to allocate a new slab. This is slowest path since we may sleep.
1362  */
1363 static void *__slab_alloc(struct kmem_cache *s,
1364                 gfp_t gfpflags, int node, void *addr, struct page *page)
1365 {
1366         void **object;
1367         int cpu = smp_processor_id();
1368
1369         if (!page)
1370                 goto new_slab;
1371
1372         slab_lock(page);
1373         if (unlikely(node != -1 && page_to_nid(page) != node))
1374                 goto another_slab;
1375 load_freelist:
1376         object = page->freelist;
1377         if (unlikely(!object))
1378                 goto another_slab;
1379         if (unlikely(SlabDebug(page)))
1380                 goto debug;
1381
1382         object = page->freelist;
1383         page->lockless_freelist = object[page->offset];
1384         page->inuse = s->objects;
1385         page->freelist = NULL;
1386         slab_unlock(page);
1387         return object;
1388
1389 another_slab:
1390         deactivate_slab(s, page, cpu);
1391
1392 new_slab:
1393         page = get_partial(s, gfpflags, node);
1394         if (page) {
1395 have_slab:
1396                 s->cpu_slab[cpu] = page;
1397                 SetPageActive(page);
1398                 goto load_freelist;
1399         }
1400
1401         page = new_slab(s, gfpflags, node);
1402         if (page) {
1403                 cpu = smp_processor_id();
1404                 if (s->cpu_slab[cpu]) {
1405                         /*
1406                          * Someone else populated the cpu_slab while we
1407                          * enabled interrupts, or we have gotten scheduled
1408                          * on another cpu. The page may not be on the
1409                          * requested node even if __GFP_THISNODE was
1410                          * specified. So we need to recheck.
1411                          */
1412                         if (node == -1 ||
1413                                 page_to_nid(s->cpu_slab[cpu]) == node) {
1414                                 /*
1415                                  * Current cpuslab is acceptable and we
1416                                  * want the current one since its cache hot
1417                                  */
1418                                 discard_slab(s, page);
1419                                 page = s->cpu_slab[cpu];
1420                                 slab_lock(page);
1421                                 goto load_freelist;
1422                         }
1423                         /* New slab does not fit our expectations */
1424                         flush_slab(s, s->cpu_slab[cpu], cpu);
1425                 }
1426                 slab_lock(page);
1427                 goto have_slab;
1428         }
1429         return NULL;
1430 debug:
1431         object = page->freelist;
1432         if (!alloc_object_checks(s, page, object))
1433                 goto another_slab;
1434         if (s->flags & SLAB_STORE_USER)
1435                 set_track(s, object, TRACK_ALLOC, addr);
1436         trace(s, page, object, 1);
1437         init_object(s, object, 1);
1438
1439         page->inuse++;
1440         page->freelist = object[page->offset];
1441         slab_unlock(page);
1442         return object;
1443 }
1444
1445 /*
1446  * Inlined fastpath so that allocation functions (kmalloc, kmem_cache_alloc)
1447  * have the fastpath folded into their functions. So no function call
1448  * overhead for requests that can be satisfied on the fastpath.
1449  *
1450  * The fastpath works by first checking if the lockless freelist can be used.
1451  * If not then __slab_alloc is called for slow processing.
1452  *
1453  * Otherwise we can simply pick the next object from the lockless free list.
1454  */
1455 static void __always_inline *slab_alloc(struct kmem_cache *s,
1456                                 gfp_t gfpflags, int node, void *addr)
1457 {
1458         struct page *page;
1459         void **object;
1460         unsigned long flags;
1461
1462         local_irq_save(flags);
1463         page = s->cpu_slab[smp_processor_id()];
1464         if (unlikely(!page || !page->lockless_freelist ||
1465                         (node != -1 && page_to_nid(page) != node)))
1466
1467                 object = __slab_alloc(s, gfpflags, node, addr, page);
1468
1469         else {
1470                 object = page->lockless_freelist;
1471                 page->lockless_freelist = object[page->offset];
1472         }
1473         local_irq_restore(flags);
1474         return object;
1475 }
1476
1477 void *kmem_cache_alloc(struct kmem_cache *s, gfp_t gfpflags)
1478 {
1479         return slab_alloc(s, gfpflags, -1, __builtin_return_address(0));
1480 }
1481 EXPORT_SYMBOL(kmem_cache_alloc);
1482
1483 #ifdef CONFIG_NUMA
1484 void *kmem_cache_alloc_node(struct kmem_cache *s, gfp_t gfpflags, int node)
1485 {
1486         return slab_alloc(s, gfpflags, node, __builtin_return_address(0));
1487 }
1488 EXPORT_SYMBOL(kmem_cache_alloc_node);
1489 #endif
1490
1491 /*
1492  * Slow patch handling. This may still be called frequently since objects
1493  * have a longer lifetime than the cpu slabs in most processing loads.
1494  *
1495  * So we still attempt to reduce cache line usage. Just take the slab
1496  * lock and free the item. If there is no additional partial page
1497  * handling required then we can return immediately.
1498  */
1499 static void __slab_free(struct kmem_cache *s, struct page *page,
1500                                         void *x, void *addr)
1501 {
1502         void *prior;
1503         void **object = (void *)x;
1504
1505         slab_lock(page);
1506
1507         if (unlikely(SlabDebug(page)))
1508                 goto debug;
1509 checks_ok:
1510         prior = object[page->offset] = page->freelist;
1511         page->freelist = object;
1512         page->inuse--;
1513
1514         if (unlikely(PageActive(page)))
1515                 /*
1516                  * Cpu slabs are never on partial lists and are
1517                  * never freed.
1518                  */
1519                 goto out_unlock;
1520
1521         if (unlikely(!page->inuse))
1522                 goto slab_empty;
1523
1524         /*
1525          * Objects left in the slab. If it
1526          * was not on the partial list before
1527          * then add it.
1528          */
1529         if (unlikely(!prior))
1530                 add_partial(get_node(s, page_to_nid(page)), page);
1531
1532 out_unlock:
1533         slab_unlock(page);
1534         return;
1535
1536 slab_empty:
1537         if (prior)
1538                 /*
1539                  * Slab still on the partial list.
1540                  */
1541                 remove_partial(s, page);
1542
1543         slab_unlock(page);
1544         discard_slab(s, page);
1545         return;
1546
1547 debug:
1548         if (!free_object_checks(s, page, x))
1549                 goto out_unlock;
1550         if (!PageActive(page) && !page->freelist)
1551                 remove_full(s, page);
1552         if (s->flags & SLAB_STORE_USER)
1553                 set_track(s, x, TRACK_FREE, addr);
1554         trace(s, page, object, 0);
1555         init_object(s, object, 0);
1556         goto checks_ok;
1557 }
1558
1559 /*
1560  * Fastpath with forced inlining to produce a kfree and kmem_cache_free that
1561  * can perform fastpath freeing without additional function calls.
1562  *
1563  * The fastpath is only possible if we are freeing to the current cpu slab
1564  * of this processor. This typically the case if we have just allocated
1565  * the item before.
1566  *
1567  * If fastpath is not possible then fall back to __slab_free where we deal
1568  * with all sorts of special processing.
1569  */
1570 static void __always_inline slab_free(struct kmem_cache *s,
1571                         struct page *page, void *x, void *addr)
1572 {
1573         void **object = (void *)x;
1574         unsigned long flags;
1575
1576         local_irq_save(flags);
1577         if (likely(page == s->cpu_slab[smp_processor_id()] &&
1578                                                 !SlabDebug(page))) {
1579                 object[page->offset] = page->lockless_freelist;
1580                 page->lockless_freelist = object;
1581         } else
1582                 __slab_free(s, page, x, addr);
1583
1584         local_irq_restore(flags);
1585 }
1586
1587 void kmem_cache_free(struct kmem_cache *s, void *x)
1588 {
1589         struct page *page;
1590
1591         page = virt_to_head_page(x);
1592
1593         slab_free(s, page, x, __builtin_return_address(0));
1594 }
1595 EXPORT_SYMBOL(kmem_cache_free);
1596
1597 /* Figure out on which slab object the object resides */
1598 static struct page *get_object_page(const void *x)
1599 {
1600         struct page *page = virt_to_head_page(x);
1601
1602         if (!PageSlab(page))
1603                 return NULL;
1604
1605         return page;
1606 }
1607
1608 /*
1609  * Object placement in a slab is made very easy because we always start at
1610  * offset 0. If we tune the size of the object to the alignment then we can
1611  * get the required alignment by putting one properly sized object after
1612  * another.
1613  *
1614  * Notice that the allocation order determines the sizes of the per cpu
1615  * caches. Each processor has always one slab available for allocations.
1616  * Increasing the allocation order reduces the number of times that slabs
1617  * must be moved on and off the partial lists and is therefore a factor in
1618  * locking overhead.
1619  */
1620
1621 /*
1622  * Mininum / Maximum order of slab pages. This influences locking overhead
1623  * and slab fragmentation. A higher order reduces the number of partial slabs
1624  * and increases the number of allocations possible without having to
1625  * take the list_lock.
1626  */
1627 static int slub_min_order;
1628 static int slub_max_order = DEFAULT_MAX_ORDER;
1629 static int slub_min_objects = DEFAULT_MIN_OBJECTS;
1630
1631 /*
1632  * Merge control. If this is set then no merging of slab caches will occur.
1633  * (Could be removed. This was introduced to pacify the merge skeptics.)
1634  */
1635 static int slub_nomerge;
1636
1637 /*
1638  * Calculate the order of allocation given an slab object size.
1639  *
1640  * The order of allocation has significant impact on performance and other
1641  * system components. Generally order 0 allocations should be preferred since
1642  * order 0 does not cause fragmentation in the page allocator. Larger objects
1643  * be problematic to put into order 0 slabs because there may be too much
1644  * unused space left. We go to a higher order if more than 1/8th of the slab
1645  * would be wasted.
1646  *
1647  * In order to reach satisfactory performance we must ensure that a minimum
1648  * number of objects is in one slab. Otherwise we may generate too much
1649  * activity on the partial lists which requires taking the list_lock. This is
1650  * less a concern for large slabs though which are rarely used.
1651  *
1652  * slub_max_order specifies the order where we begin to stop considering the
1653  * number of objects in a slab as critical. If we reach slub_max_order then
1654  * we try to keep the page order as low as possible. So we accept more waste
1655  * of space in favor of a small page order.
1656  *
1657  * Higher order allocations also allow the placement of more objects in a
1658  * slab and thereby reduce object handling overhead. If the user has
1659  * requested a higher mininum order then we start with that one instead of
1660  * the smallest order which will fit the object.
1661  */
1662 static inline int slab_order(int size, int min_objects,
1663                                 int max_order, int fract_leftover)
1664 {
1665         int order;
1666         int rem;
1667
1668         for (order = max(slub_min_order,
1669                                 fls(min_objects * size - 1) - PAGE_SHIFT);
1670                         order <= max_order; order++) {
1671
1672                 unsigned long slab_size = PAGE_SIZE << order;
1673
1674                 if (slab_size < min_objects * size)
1675                         continue;
1676
1677                 rem = slab_size % size;
1678
1679                 if (rem <= slab_size / fract_leftover)
1680                         break;
1681
1682         }
1683
1684         return order;
1685 }
1686
1687 static inline int calculate_order(int size)
1688 {
1689         int order;
1690         int min_objects;
1691         int fraction;
1692
1693         /*
1694          * Attempt to find best configuration for a slab. This
1695          * works by first attempting to generate a layout with
1696          * the best configuration and backing off gradually.
1697          *
1698          * First we reduce the acceptable waste in a slab. Then
1699          * we reduce the minimum objects required in a slab.
1700          */
1701         min_objects = slub_min_objects;
1702         while (min_objects > 1) {
1703                 fraction = 8;
1704                 while (fraction >= 4) {
1705                         order = slab_order(size, min_objects,
1706                                                 slub_max_order, fraction);
1707                         if (order <= slub_max_order)
1708                                 return order;
1709                         fraction /= 2;
1710                 }
1711                 min_objects /= 2;
1712         }
1713
1714         /*
1715          * We were unable to place multiple objects in a slab. Now
1716          * lets see if we can place a single object there.
1717          */
1718         order = slab_order(size, 1, slub_max_order, 1);
1719         if (order <= slub_max_order)
1720                 return order;
1721
1722         /*
1723          * Doh this slab cannot be placed using slub_max_order.
1724          */
1725         order = slab_order(size, 1, MAX_ORDER, 1);
1726         if (order <= MAX_ORDER)
1727                 return order;
1728         return -ENOSYS;
1729 }
1730
1731 /*
1732  * Figure out what the alignment of the objects will be.
1733  */
1734 static unsigned long calculate_alignment(unsigned long flags,
1735                 unsigned long align, unsigned long size)
1736 {
1737         /*
1738          * If the user wants hardware cache aligned objects then
1739          * follow that suggestion if the object is sufficiently
1740          * large.
1741          *
1742          * The hardware cache alignment cannot override the
1743          * specified alignment though. If that is greater
1744          * then use it.
1745          */
1746         if ((flags & SLAB_HWCACHE_ALIGN) &&
1747                         size > cache_line_size() / 2)
1748                 return max_t(unsigned long, align, cache_line_size());
1749
1750         if (align < ARCH_SLAB_MINALIGN)
1751                 return ARCH_SLAB_MINALIGN;
1752
1753         return ALIGN(align, sizeof(void *));
1754 }
1755
1756 static void init_kmem_cache_node(struct kmem_cache_node *n)
1757 {
1758         n->nr_partial = 0;
1759         atomic_long_set(&n->nr_slabs, 0);
1760         spin_lock_init(&n->list_lock);
1761         INIT_LIST_HEAD(&n->partial);
1762         INIT_LIST_HEAD(&n->full);
1763 }
1764
1765 #ifdef CONFIG_NUMA
1766 /*
1767  * No kmalloc_node yet so do it by hand. We know that this is the first
1768  * slab on the node for this slabcache. There are no concurrent accesses
1769  * possible.
1770  *
1771  * Note that this function only works on the kmalloc_node_cache
1772  * when allocating for the kmalloc_node_cache.
1773  */
1774 static struct kmem_cache_node * __init early_kmem_cache_node_alloc(gfp_t gfpflags,
1775                                                                 int node)
1776 {
1777         struct page *page;
1778         struct kmem_cache_node *n;
1779
1780         BUG_ON(kmalloc_caches->size < sizeof(struct kmem_cache_node));
1781
1782         page = new_slab(kmalloc_caches, gfpflags | GFP_THISNODE, node);
1783         /* new_slab() disables interupts */
1784         local_irq_enable();
1785
1786         BUG_ON(!page);
1787         n = page->freelist;
1788         BUG_ON(!n);
1789         page->freelist = get_freepointer(kmalloc_caches, n);
1790         page->inuse++;
1791         kmalloc_caches->node[node] = n;
1792         init_object(kmalloc_caches, n, 1);
1793         init_kmem_cache_node(n);
1794         atomic_long_inc(&n->nr_slabs);
1795         add_partial(n, page);
1796         return n;
1797 }
1798
1799 static void free_kmem_cache_nodes(struct kmem_cache *s)
1800 {
1801         int node;
1802
1803         for_each_online_node(node) {
1804                 struct kmem_cache_node *n = s->node[node];
1805                 if (n && n != &s->local_node)
1806                         kmem_cache_free(kmalloc_caches, n);
1807                 s->node[node] = NULL;
1808         }
1809 }
1810
1811 static int init_kmem_cache_nodes(struct kmem_cache *s, gfp_t gfpflags)
1812 {
1813         int node;
1814         int local_node;
1815
1816         if (slab_state >= UP)
1817                 local_node = page_to_nid(virt_to_page(s));
1818         else
1819                 local_node = 0;
1820
1821         for_each_online_node(node) {
1822                 struct kmem_cache_node *n;
1823
1824                 if (local_node == node)
1825                         n = &s->local_node;
1826                 else {
1827                         if (slab_state == DOWN) {
1828                                 n = early_kmem_cache_node_alloc(gfpflags,
1829                                                                 node);
1830                                 continue;
1831                         }
1832                         n = kmem_cache_alloc_node(kmalloc_caches,
1833                                                         gfpflags, node);
1834
1835                         if (!n) {
1836                                 free_kmem_cache_nodes(s);
1837                                 return 0;
1838                         }
1839
1840                 }
1841                 s->node[node] = n;
1842                 init_kmem_cache_node(n);
1843         }
1844         return 1;
1845 }
1846 #else
1847 static void free_kmem_cache_nodes(struct kmem_cache *s)
1848 {
1849 }
1850
1851 static int init_kmem_cache_nodes(struct kmem_cache *s, gfp_t gfpflags)
1852 {
1853         init_kmem_cache_node(&s->local_node);
1854         return 1;
1855 }
1856 #endif
1857
1858 /*
1859  * calculate_sizes() determines the order and the distribution of data within
1860  * a slab object.
1861  */
1862 static int calculate_sizes(struct kmem_cache *s)
1863 {
1864         unsigned long flags = s->flags;
1865         unsigned long size = s->objsize;
1866         unsigned long align = s->align;
1867
1868         /*
1869          * Determine if we can poison the object itself. If the user of
1870          * the slab may touch the object after free or before allocation
1871          * then we should never poison the object itself.
1872          */
1873         if ((flags & SLAB_POISON) && !(flags & SLAB_DESTROY_BY_RCU) &&
1874                         !s->ctor && !s->dtor)
1875                 s->flags |= __OBJECT_POISON;
1876         else
1877                 s->flags &= ~__OBJECT_POISON;
1878
1879         /*
1880          * Round up object size to the next word boundary. We can only
1881          * place the free pointer at word boundaries and this determines
1882          * the possible location of the free pointer.
1883          */
1884         size = ALIGN(size, sizeof(void *));
1885
1886 #ifdef CONFIG_SLUB_DEBUG
1887         /*
1888          * If we are Redzoning then check if there is some space between the
1889          * end of the object and the free pointer. If not then add an
1890          * additional word to have some bytes to store Redzone information.
1891          */
1892         if ((flags & SLAB_RED_ZONE) && size == s->objsize)
1893                 size += sizeof(void *);
1894 #endif
1895
1896         /*
1897          * With that we have determined the number of bytes in actual use
1898          * by the object. This is the potential offset to the free pointer.
1899          */
1900         s->inuse = size;
1901
1902 #ifdef CONFIG_SLUB_DEBUG
1903         if (((flags & (SLAB_DESTROY_BY_RCU | SLAB_POISON)) ||
1904                 s->ctor || s->dtor)) {
1905                 /*
1906                  * Relocate free pointer after the object if it is not
1907                  * permitted to overwrite the first word of the object on
1908                  * kmem_cache_free.
1909                  *
1910                  * This is the case if we do RCU, have a constructor or
1911                  * destructor or are poisoning the objects.
1912                  */
1913                 s->offset = size;
1914                 size += sizeof(void *);
1915         }
1916
1917         if (flags & SLAB_STORE_USER)
1918                 /*
1919                  * Need to store information about allocs and frees after
1920                  * the object.
1921                  */
1922                 size += 2 * sizeof(struct track);
1923
1924         if (flags & SLAB_RED_ZONE)
1925                 /*
1926                  * Add some empty padding so that we can catch
1927                  * overwrites from earlier objects rather than let
1928                  * tracking information or the free pointer be
1929                  * corrupted if an user writes before the start
1930                  * of the object.
1931                  */
1932                 size += sizeof(void *);
1933 #endif
1934
1935         /*
1936          * Determine the alignment based on various parameters that the
1937          * user specified and the dynamic determination of cache line size
1938          * on bootup.
1939          */
1940         align = calculate_alignment(flags, align, s->objsize);
1941
1942         /*
1943          * SLUB stores one object immediately after another beginning from
1944          * offset 0. In order to align the objects we have to simply size
1945          * each object to conform to the alignment.
1946          */
1947         size = ALIGN(size, align);
1948         s->size = size;
1949
1950         s->order = calculate_order(size);
1951         if (s->order < 0)
1952                 return 0;
1953
1954         /*
1955          * Determine the number of objects per slab
1956          */
1957         s->objects = (PAGE_SIZE << s->order) / size;
1958
1959         /*
1960          * Verify that the number of objects is within permitted limits.
1961          * The page->inuse field is only 16 bit wide! So we cannot have
1962          * more than 64k objects per slab.
1963          */
1964         if (!s->objects || s->objects > 65535)
1965                 return 0;
1966         return 1;
1967
1968 }
1969
1970 static int kmem_cache_open(struct kmem_cache *s, gfp_t gfpflags,
1971                 const char *name, size_t size,
1972                 size_t align, unsigned long flags,
1973                 void (*ctor)(void *, struct kmem_cache *, unsigned long),
1974                 void (*dtor)(void *, struct kmem_cache *, unsigned long))
1975 {
1976         memset(s, 0, kmem_size);
1977         s->name = name;
1978         s->ctor = ctor;
1979         s->dtor = dtor;
1980         s->objsize = size;
1981         s->flags = flags;
1982         s->align = align;
1983         kmem_cache_open_debug_check(s);
1984
1985         if (!calculate_sizes(s))
1986                 goto error;
1987
1988         s->refcount = 1;
1989 #ifdef CONFIG_NUMA
1990         s->defrag_ratio = 100;
1991 #endif
1992
1993         if (init_kmem_cache_nodes(s, gfpflags & ~SLUB_DMA))
1994                 return 1;
1995 error:
1996         if (flags & SLAB_PANIC)
1997                 panic("Cannot create slab %s size=%lu realsize=%u "
1998                         "order=%u offset=%u flags=%lx\n",
1999                         s->name, (unsigned long)size, s->size, s->order,
2000                         s->offset, flags);
2001         return 0;
2002 }
2003 EXPORT_SYMBOL(kmem_cache_open);
2004
2005 /*
2006  * Check if a given pointer is valid
2007  */
2008 int kmem_ptr_validate(struct kmem_cache *s, const void *object)
2009 {
2010         struct page * page;
2011
2012         page = get_object_page(object);
2013
2014         if (!page || s != page->slab)
2015                 /* No slab or wrong slab */
2016                 return 0;
2017
2018         if (!check_valid_pointer(s, page, object))
2019                 return 0;
2020
2021         /*
2022          * We could also check if the object is on the slabs freelist.
2023          * But this would be too expensive and it seems that the main
2024          * purpose of kmem_ptr_valid is to check if the object belongs
2025          * to a certain slab.
2026          */
2027         return 1;
2028 }
2029 EXPORT_SYMBOL(kmem_ptr_validate);
2030
2031 /*
2032  * Determine the size of a slab object
2033  */
2034 unsigned int kmem_cache_size(struct kmem_cache *s)
2035 {
2036         return s->objsize;
2037 }
2038 EXPORT_SYMBOL(kmem_cache_size);
2039
2040 const char *kmem_cache_name(struct kmem_cache *s)
2041 {
2042         return s->name;
2043 }
2044 EXPORT_SYMBOL(kmem_cache_name);
2045
2046 /*
2047  * Attempt to free all slabs on a node. Return the number of slabs we
2048  * were unable to free.
2049  */
2050 static int free_list(struct kmem_cache *s, struct kmem_cache_node *n,
2051                         struct list_head *list)
2052 {
2053         int slabs_inuse = 0;
2054         unsigned long flags;
2055         struct page *page, *h;
2056
2057         spin_lock_irqsave(&n->list_lock, flags);
2058         list_for_each_entry_safe(page, h, list, lru)
2059                 if (!page->inuse) {
2060                         list_del(&page->lru);
2061                         discard_slab(s, page);
2062                 } else
2063                         slabs_inuse++;
2064         spin_unlock_irqrestore(&n->list_lock, flags);
2065         return slabs_inuse;
2066 }
2067
2068 /*
2069  * Release all resources used by a slab cache.
2070  */
2071 static int kmem_cache_close(struct kmem_cache *s)
2072 {
2073         int node;
2074
2075         flush_all(s);
2076
2077         /* Attempt to free all objects */
2078         for_each_online_node(node) {
2079                 struct kmem_cache_node *n = get_node(s, node);
2080
2081                 n->nr_partial -= free_list(s, n, &n->partial);
2082                 if (atomic_long_read(&n->nr_slabs))
2083                         return 1;
2084         }
2085         free_kmem_cache_nodes(s);
2086         return 0;
2087 }
2088
2089 /*
2090  * Close a cache and release the kmem_cache structure
2091  * (must be used for caches created using kmem_cache_create)
2092  */
2093 void kmem_cache_destroy(struct kmem_cache *s)
2094 {
2095         down_write(&slub_lock);
2096         s->refcount--;
2097         if (!s->refcount) {
2098                 list_del(&s->list);
2099                 if (kmem_cache_close(s))
2100                         WARN_ON(1);
2101                 sysfs_slab_remove(s);
2102                 kfree(s);
2103         }
2104         up_write(&slub_lock);
2105 }
2106 EXPORT_SYMBOL(kmem_cache_destroy);
2107
2108 /********************************************************************
2109  *              Kmalloc subsystem
2110  *******************************************************************/
2111
2112 struct kmem_cache kmalloc_caches[KMALLOC_SHIFT_HIGH + 1] __cacheline_aligned;
2113 EXPORT_SYMBOL(kmalloc_caches);
2114
2115 #ifdef CONFIG_ZONE_DMA
2116 static struct kmem_cache *kmalloc_caches_dma[KMALLOC_SHIFT_HIGH + 1];
2117 #endif
2118
2119 static int __init setup_slub_min_order(char *str)
2120 {
2121         get_option (&str, &slub_min_order);
2122
2123         return 1;
2124 }
2125
2126 __setup("slub_min_order=", setup_slub_min_order);
2127
2128 static int __init setup_slub_max_order(char *str)
2129 {
2130         get_option (&str, &slub_max_order);
2131
2132         return 1;
2133 }
2134
2135 __setup("slub_max_order=", setup_slub_max_order);
2136
2137 static int __init setup_slub_min_objects(char *str)
2138 {
2139         get_option (&str, &slub_min_objects);
2140
2141         return 1;
2142 }
2143
2144 __setup("slub_min_objects=", setup_slub_min_objects);
2145
2146 static int __init setup_slub_nomerge(char *str)
2147 {
2148         slub_nomerge = 1;
2149         return 1;
2150 }
2151
2152 __setup("slub_nomerge", setup_slub_nomerge);
2153
2154 static struct kmem_cache *create_kmalloc_cache(struct kmem_cache *s,
2155                 const char *name, int size, gfp_t gfp_flags)
2156 {
2157         unsigned int flags = 0;
2158
2159         if (gfp_flags & SLUB_DMA)
2160                 flags = SLAB_CACHE_DMA;
2161
2162         down_write(&slub_lock);
2163         if (!kmem_cache_open(s, gfp_flags, name, size, ARCH_KMALLOC_MINALIGN,
2164                         flags, NULL, NULL))
2165                 goto panic;
2166
2167         list_add(&s->list, &slab_caches);
2168         up_write(&slub_lock);
2169         if (sysfs_slab_add(s))
2170                 goto panic;
2171         return s;
2172
2173 panic:
2174         panic("Creation of kmalloc slab %s size=%d failed.\n", name, size);
2175 }
2176
2177 static struct kmem_cache *get_slab(size_t size, gfp_t flags)
2178 {
2179         int index = kmalloc_index(size);
2180
2181         if (!index)
2182                 return NULL;
2183
2184         /* Allocation too large? */
2185         BUG_ON(index < 0);
2186
2187 #ifdef CONFIG_ZONE_DMA
2188         if ((flags & SLUB_DMA)) {
2189                 struct kmem_cache *s;
2190                 struct kmem_cache *x;
2191                 char *text;
2192                 size_t realsize;
2193
2194                 s = kmalloc_caches_dma[index];
2195                 if (s)
2196                         return s;
2197
2198                 /* Dynamically create dma cache */
2199                 x = kmalloc(kmem_size, flags & ~SLUB_DMA);
2200                 if (!x)
2201                         panic("Unable to allocate memory for dma cache\n");
2202
2203                 if (index <= KMALLOC_SHIFT_HIGH)
2204                         realsize = 1 << index;
2205                 else {
2206                         if (index == 1)
2207                                 realsize = 96;
2208                         else
2209                                 realsize = 192;
2210                 }
2211
2212                 text = kasprintf(flags & ~SLUB_DMA, "kmalloc_dma-%d",
2213                                 (unsigned int)realsize);
2214                 s = create_kmalloc_cache(x, text, realsize, flags);
2215                 kmalloc_caches_dma[index] = s;
2216                 return s;
2217         }
2218 #endif
2219         return &kmalloc_caches[index];
2220 }
2221
2222 void *__kmalloc(size_t size, gfp_t flags)
2223 {
2224         struct kmem_cache *s = get_slab(size, flags);
2225
2226         if (s)
2227                 return slab_alloc(s, flags, -1, __builtin_return_address(0));
2228         return NULL;
2229 }
2230 EXPORT_SYMBOL(__kmalloc);
2231
2232 #ifdef CONFIG_NUMA
2233 void *__kmalloc_node(size_t size, gfp_t flags, int node)
2234 {
2235         struct kmem_cache *s = get_slab(size, flags);
2236
2237         if (s)
2238                 return slab_alloc(s, flags, node, __builtin_return_address(0));
2239         return NULL;
2240 }
2241 EXPORT_SYMBOL(__kmalloc_node);
2242 #endif
2243
2244 size_t ksize(const void *object)
2245 {
2246         struct page *page = get_object_page(object);
2247         struct kmem_cache *s;
2248
2249         BUG_ON(!page);
2250         s = page->slab;
2251         BUG_ON(!s);
2252
2253         /*
2254          * Debugging requires use of the padding between object
2255          * and whatever may come after it.
2256          */
2257         if (s->flags & (SLAB_RED_ZONE | SLAB_POISON))
2258                 return s->objsize;
2259
2260         /*
2261          * If we have the need to store the freelist pointer
2262          * back there or track user information then we can
2263          * only use the space before that information.
2264          */
2265         if (s->flags & (SLAB_DESTROY_BY_RCU | SLAB_STORE_USER))
2266                 return s->inuse;
2267
2268         /*
2269          * Else we can use all the padding etc for the allocation
2270          */
2271         return s->size;
2272 }
2273 EXPORT_SYMBOL(ksize);
2274
2275 void kfree(const void *x)
2276 {
2277         struct kmem_cache *s;
2278         struct page *page;
2279
2280         if (!x)
2281                 return;
2282
2283         page = virt_to_head_page(x);
2284         s = page->slab;
2285
2286         slab_free(s, page, (void *)x, __builtin_return_address(0));
2287 }
2288 EXPORT_SYMBOL(kfree);
2289
2290 /*
2291  * kmem_cache_shrink removes empty slabs from the partial lists and sorts
2292  * the remaining slabs by the number of items in use. The slabs with the
2293  * most items in use come first. New allocations will then fill those up
2294  * and thus they can be removed from the partial lists.
2295  *
2296  * The slabs with the least items are placed last. This results in them
2297  * being allocated from last increasing the chance that the last objects
2298  * are freed in them.
2299  */
2300 int kmem_cache_shrink(struct kmem_cache *s)
2301 {
2302         int node;
2303         int i;
2304         struct kmem_cache_node *n;
2305         struct page *page;
2306         struct page *t;
2307         struct list_head *slabs_by_inuse =
2308                 kmalloc(sizeof(struct list_head) * s->objects, GFP_KERNEL);
2309         unsigned long flags;
2310
2311         if (!slabs_by_inuse)
2312                 return -ENOMEM;
2313
2314         flush_all(s);
2315         for_each_online_node(node) {
2316                 n = get_node(s, node);
2317
2318                 if (!n->nr_partial)
2319                         continue;
2320
2321                 for (i = 0; i < s->objects; i++)
2322                         INIT_LIST_HEAD(slabs_by_inuse + i);
2323
2324                 spin_lock_irqsave(&n->list_lock, flags);
2325
2326                 /*
2327                  * Build lists indexed by the items in use in each slab.
2328                  *
2329                  * Note that concurrent frees may occur while we hold the
2330                  * list_lock. page->inuse here is the upper limit.
2331                  */
2332                 list_for_each_entry_safe(page, t, &n->partial, lru) {
2333                         if (!page->inuse && slab_trylock(page)) {
2334                                 /*
2335                                  * Must hold slab lock here because slab_free
2336                                  * may have freed the last object and be
2337                                  * waiting to release the slab.
2338                                  */
2339                                 list_del(&page->lru);
2340                                 n->nr_partial--;
2341                                 slab_unlock(page);
2342                                 discard_slab(s, page);
2343                         } else {
2344                                 if (n->nr_partial > MAX_PARTIAL)
2345                                         list_move(&page->lru,
2346                                         slabs_by_inuse + page->inuse);
2347                         }
2348                 }
2349
2350                 if (n->nr_partial <= MAX_PARTIAL)
2351                         goto out;
2352
2353                 /*
2354                  * Rebuild the partial list with the slabs filled up most
2355                  * first and the least used slabs at the end.
2356                  */
2357                 for (i = s->objects - 1; i >= 0; i--)
2358                         list_splice(slabs_by_inuse + i, n->partial.prev);
2359
2360         out:
2361                 spin_unlock_irqrestore(&n->list_lock, flags);
2362         }
2363
2364         kfree(slabs_by_inuse);
2365         return 0;
2366 }
2367 EXPORT_SYMBOL(kmem_cache_shrink);
2368
2369 /**
2370  * krealloc - reallocate memory. The contents will remain unchanged.
2371  * @p: object to reallocate memory for.
2372  * @new_size: how many bytes of memory are required.
2373  * @flags: the type of memory to allocate.
2374  *
2375  * The contents of the object pointed to are preserved up to the
2376  * lesser of the new and old sizes.  If @p is %NULL, krealloc()
2377  * behaves exactly like kmalloc().  If @size is 0 and @p is not a
2378  * %NULL pointer, the object pointed to is freed.
2379  */
2380 void *krealloc(const void *p, size_t new_size, gfp_t flags)
2381 {
2382         void *ret;
2383         size_t ks;
2384
2385         if (unlikely(!p))
2386                 return kmalloc(new_size, flags);
2387
2388         if (unlikely(!new_size)) {
2389                 kfree(p);
2390                 return NULL;
2391         }
2392
2393         ks = ksize(p);
2394         if (ks >= new_size)
2395                 return (void *)p;
2396
2397         ret = kmalloc(new_size, flags);
2398         if (ret) {
2399                 memcpy(ret, p, min(new_size, ks));
2400                 kfree(p);
2401         }
2402         return ret;
2403 }
2404 EXPORT_SYMBOL(krealloc);
2405
2406 /********************************************************************
2407  *                      Basic setup of slabs
2408  *******************************************************************/
2409
2410 void __init kmem_cache_init(void)
2411 {
2412         int i;
2413
2414 #ifdef CONFIG_NUMA
2415         /*
2416          * Must first have the slab cache available for the allocations of the
2417          * struct kmem_cache_node's. There is special bootstrap code in
2418          * kmem_cache_open for slab_state == DOWN.
2419          */
2420         create_kmalloc_cache(&kmalloc_caches[0], "kmem_cache_node",
2421                 sizeof(struct kmem_cache_node), GFP_KERNEL);
2422 #endif
2423
2424         /* Able to allocate the per node structures */
2425         slab_state = PARTIAL;
2426
2427         /* Caches that are not of the two-to-the-power-of size */
2428         create_kmalloc_cache(&kmalloc_caches[1],
2429                                 "kmalloc-96", 96, GFP_KERNEL);
2430         create_kmalloc_cache(&kmalloc_caches[2],
2431                                 "kmalloc-192", 192, GFP_KERNEL);
2432
2433         for (i = KMALLOC_SHIFT_LOW; i <= KMALLOC_SHIFT_HIGH; i++)
2434                 create_kmalloc_cache(&kmalloc_caches[i],
2435                         "kmalloc", 1 << i, GFP_KERNEL);
2436
2437         slab_state = UP;
2438
2439         /* Provide the correct kmalloc names now that the caches are up */
2440         for (i = KMALLOC_SHIFT_LOW; i <= KMALLOC_SHIFT_HIGH; i++)
2441                 kmalloc_caches[i]. name =
2442                         kasprintf(GFP_KERNEL, "kmalloc-%d", 1 << i);
2443
2444 #ifdef CONFIG_SMP
2445         register_cpu_notifier(&slab_notifier);
2446 #endif
2447
2448         kmem_size = offsetof(struct kmem_cache, cpu_slab) +
2449                                 nr_cpu_ids * sizeof(struct page *);
2450
2451         printk(KERN_INFO "SLUB: Genslabs=%d, HWalign=%d, Order=%d-%d, MinObjects=%d,"
2452                 " Processors=%d, Nodes=%d\n",
2453                 KMALLOC_SHIFT_HIGH, cache_line_size(),
2454                 slub_min_order, slub_max_order, slub_min_objects,
2455                 nr_cpu_ids, nr_node_ids);
2456 }
2457
2458 /*
2459  * Find a mergeable slab cache
2460  */
2461 static int slab_unmergeable(struct kmem_cache *s)
2462 {
2463         if (slub_nomerge || (s->flags & SLUB_NEVER_MERGE))
2464                 return 1;
2465
2466         if (s->ctor || s->dtor)
2467                 return 1;
2468
2469         return 0;
2470 }
2471
2472 static struct kmem_cache *find_mergeable(size_t size,
2473                 size_t align, unsigned long flags,
2474                 void (*ctor)(void *, struct kmem_cache *, unsigned long),
2475                 void (*dtor)(void *, struct kmem_cache *, unsigned long))
2476 {
2477         struct list_head *h;
2478
2479         if (slub_nomerge || (flags & SLUB_NEVER_MERGE))
2480                 return NULL;
2481
2482         if (ctor || dtor)
2483                 return NULL;
2484
2485         size = ALIGN(size, sizeof(void *));
2486         align = calculate_alignment(flags, align, size);
2487         size = ALIGN(size, align);
2488
2489         list_for_each(h, &slab_caches) {
2490                 struct kmem_cache *s =
2491                         container_of(h, struct kmem_cache, list);
2492
2493                 if (slab_unmergeable(s))
2494                         continue;
2495
2496                 if (size > s->size)
2497                         continue;
2498
2499                 if (((flags | slub_debug) & SLUB_MERGE_SAME) !=
2500                         (s->flags & SLUB_MERGE_SAME))
2501                                 continue;
2502                 /*
2503                  * Check if alignment is compatible.
2504                  * Courtesy of Adrian Drzewiecki
2505                  */
2506                 if ((s->size & ~(align -1)) != s->size)
2507                         continue;
2508
2509                 if (s->size - size >= sizeof(void *))
2510                         continue;
2511
2512                 return s;
2513         }
2514         return NULL;
2515 }
2516
2517 struct kmem_cache *kmem_cache_create(const char *name, size_t size,
2518                 size_t align, unsigned long flags,
2519                 void (*ctor)(void *, struct kmem_cache *, unsigned long),
2520                 void (*dtor)(void *, struct kmem_cache *, unsigned long))
2521 {
2522         struct kmem_cache *s;
2523
2524         down_write(&slub_lock);
2525         s = find_mergeable(size, align, flags, ctor, dtor);
2526         if (s) {
2527                 s->refcount++;
2528                 /*
2529                  * Adjust the object sizes so that we clear
2530                  * the complete object on kzalloc.
2531                  */
2532                 s->objsize = max(s->objsize, (int)size);
2533                 s->inuse = max_t(int, s->inuse, ALIGN(size, sizeof(void *)));
2534                 if (sysfs_slab_alias(s, name))
2535                         goto err;
2536         } else {
2537                 s = kmalloc(kmem_size, GFP_KERNEL);
2538                 if (s && kmem_cache_open(s, GFP_KERNEL, name,
2539                                 size, align, flags, ctor, dtor)) {
2540                         if (sysfs_slab_add(s)) {
2541                                 kfree(s);
2542                                 goto err;
2543                         }
2544                         list_add(&s->list, &slab_caches);
2545                 } else
2546                         kfree(s);
2547         }
2548         up_write(&slub_lock);
2549         return s;
2550
2551 err:
2552         up_write(&slub_lock);
2553         if (flags & SLAB_PANIC)
2554                 panic("Cannot create slabcache %s\n", name);
2555         else
2556                 s = NULL;
2557         return s;
2558 }
2559 EXPORT_SYMBOL(kmem_cache_create);
2560
2561 void *kmem_cache_zalloc(struct kmem_cache *s, gfp_t flags)
2562 {
2563         void *x;
2564
2565         x = slab_alloc(s, flags, -1, __builtin_return_address(0));
2566         if (x)
2567                 memset(x, 0, s->objsize);
2568         return x;
2569 }
2570 EXPORT_SYMBOL(kmem_cache_zalloc);
2571
2572 #ifdef CONFIG_SMP
2573 static void for_all_slabs(void (*func)(struct kmem_cache *, int), int cpu)
2574 {
2575         struct list_head *h;
2576
2577         down_read(&slub_lock);
2578         list_for_each(h, &slab_caches) {
2579                 struct kmem_cache *s =
2580                         container_of(h, struct kmem_cache, list);
2581
2582                 func(s, cpu);
2583         }
2584         up_read(&slub_lock);
2585 }
2586
2587 /*
2588  * Use the cpu notifier to insure that the cpu slabs are flushed when
2589  * necessary.
2590  */
2591 static int __cpuinit slab_cpuup_callback(struct notifier_block *nfb,
2592                 unsigned long action, void *hcpu)
2593 {
2594         long cpu = (long)hcpu;
2595
2596         switch (action) {
2597         case CPU_UP_CANCELED:
2598         case CPU_UP_CANCELED_FROZEN:
2599         case CPU_DEAD:
2600         case CPU_DEAD_FROZEN:
2601                 for_all_slabs(__flush_cpu_slab, cpu);
2602                 break;
2603         default:
2604                 break;
2605         }
2606         return NOTIFY_OK;
2607 }
2608
2609 static struct notifier_block __cpuinitdata slab_notifier =
2610         { &slab_cpuup_callback, NULL, 0 };
2611
2612 #endif
2613
2614 void *__kmalloc_track_caller(size_t size, gfp_t gfpflags, void *caller)
2615 {
2616         struct kmem_cache *s = get_slab(size, gfpflags);
2617
2618         if (!s)
2619                 return NULL;
2620
2621         return slab_alloc(s, gfpflags, -1, caller);
2622 }
2623
2624 void *__kmalloc_node_track_caller(size_t size, gfp_t gfpflags,
2625                                         int node, void *caller)
2626 {
2627         struct kmem_cache *s = get_slab(size, gfpflags);
2628
2629         if (!s)
2630                 return NULL;
2631
2632         return slab_alloc(s, gfpflags, node, caller);
2633 }
2634
2635 #if defined(CONFIG_SYSFS) && defined(CONFIG_SLUB_DEBUG)
2636 static int validate_slab(struct kmem_cache *s, struct page *page)
2637 {
2638         void *p;
2639         void *addr = page_address(page);
2640         DECLARE_BITMAP(map, s->objects);
2641
2642         if (!check_slab(s, page) ||
2643                         !on_freelist(s, page, NULL))
2644                 return 0;
2645
2646         /* Now we know that a valid freelist exists */
2647         bitmap_zero(map, s->objects);
2648
2649         for_each_free_object(p, s, page->freelist) {
2650                 set_bit(slab_index(p, s, addr), map);
2651                 if (!check_object(s, page, p, 0))
2652                         return 0;
2653         }
2654
2655         for_each_object(p, s, addr)
2656                 if (!test_bit(slab_index(p, s, addr), map))
2657                         if (!check_object(s, page, p, 1))
2658                                 return 0;
2659         return 1;
2660 }
2661
2662 static void validate_slab_slab(struct kmem_cache *s, struct page *page)
2663 {
2664         if (slab_trylock(page)) {
2665                 validate_slab(s, page);
2666                 slab_unlock(page);
2667         } else
2668                 printk(KERN_INFO "SLUB %s: Skipped busy slab 0x%p\n",
2669                         s->name, page);
2670
2671         if (s->flags & DEBUG_DEFAULT_FLAGS) {
2672                 if (!SlabDebug(page))
2673                         printk(KERN_ERR "SLUB %s: SlabDebug not set "
2674                                 "on slab 0x%p\n", s->name, page);
2675         } else {
2676                 if (SlabDebug(page))
2677                         printk(KERN_ERR "SLUB %s: SlabDebug set on "
2678                                 "slab 0x%p\n", s->name, page);
2679         }
2680 }
2681
2682 static int validate_slab_node(struct kmem_cache *s, struct kmem_cache_node *n)
2683 {
2684         unsigned long count = 0;
2685         struct page *page;
2686         unsigned long flags;
2687
2688         spin_lock_irqsave(&n->list_lock, flags);
2689
2690         list_for_each_entry(page, &n->partial, lru) {
2691                 validate_slab_slab(s, page);
2692                 count++;
2693         }
2694         if (count != n->nr_partial)
2695                 printk(KERN_ERR "SLUB %s: %ld partial slabs counted but "
2696                         "counter=%ld\n", s->name, count, n->nr_partial);
2697
2698         if (!(s->flags & SLAB_STORE_USER))
2699                 goto out;
2700
2701         list_for_each_entry(page, &n->full, lru) {
2702                 validate_slab_slab(s, page);
2703                 count++;
2704         }
2705         if (count != atomic_long_read(&n->nr_slabs))
2706                 printk(KERN_ERR "SLUB: %s %ld slabs counted but "
2707                         "counter=%ld\n", s->name, count,
2708                         atomic_long_read(&n->nr_slabs));
2709
2710 out:
2711         spin_unlock_irqrestore(&n->list_lock, flags);
2712         return count;
2713 }
2714
2715 static unsigned long validate_slab_cache(struct kmem_cache *s)
2716 {
2717         int node;
2718         unsigned long count = 0;
2719
2720         flush_all(s);
2721         for_each_online_node(node) {
2722                 struct kmem_cache_node *n = get_node(s, node);
2723
2724                 count += validate_slab_node(s, n);
2725         }
2726         return count;
2727 }
2728
2729 #ifdef SLUB_RESILIENCY_TEST
2730 static void resiliency_test(void)
2731 {
2732         u8 *p;
2733
2734         printk(KERN_ERR "SLUB resiliency testing\n");
2735         printk(KERN_ERR "-----------------------\n");
2736         printk(KERN_ERR "A. Corruption after allocation\n");
2737
2738         p = kzalloc(16, GFP_KERNEL);
2739         p[16] = 0x12;
2740         printk(KERN_ERR "\n1. kmalloc-16: Clobber Redzone/next pointer"
2741                         " 0x12->0x%p\n\n", p + 16);
2742
2743         validate_slab_cache(kmalloc_caches + 4);
2744
2745         /* Hmmm... The next two are dangerous */
2746         p = kzalloc(32, GFP_KERNEL);
2747         p[32 + sizeof(void *)] = 0x34;
2748         printk(KERN_ERR "\n2. kmalloc-32: Clobber next pointer/next slab"
2749                         " 0x34 -> -0x%p\n", p);
2750         printk(KERN_ERR "If allocated object is overwritten then not detectable\n\n");
2751
2752         validate_slab_cache(kmalloc_caches + 5);
2753         p = kzalloc(64, GFP_KERNEL);
2754         p += 64 + (get_cycles() & 0xff) * sizeof(void *);
2755         *p = 0x56;
2756         printk(KERN_ERR "\n3. kmalloc-64: corrupting random byte 0x56->0x%p\n",
2757                                                                         p);
2758         printk(KERN_ERR "If allocated object is overwritten then not detectable\n\n");
2759         validate_slab_cache(kmalloc_caches + 6);
2760
2761         printk(KERN_ERR "\nB. Corruption after free\n");
2762         p = kzalloc(128, GFP_KERNEL);
2763         kfree(p);
2764         *p = 0x78;
2765         printk(KERN_ERR "1. kmalloc-128: Clobber first word 0x78->0x%p\n\n", p);
2766         validate_slab_cache(kmalloc_caches + 7);
2767
2768         p = kzalloc(256, GFP_KERNEL);
2769         kfree(p);
2770         p[50] = 0x9a;
2771         printk(KERN_ERR "\n2. kmalloc-256: Clobber 50th byte 0x9a->0x%p\n\n", p);
2772         validate_slab_cache(kmalloc_caches + 8);
2773
2774         p = kzalloc(512, GFP_KERNEL);
2775         kfree(p);
2776         p[512] = 0xab;
2777         printk(KERN_ERR "\n3. kmalloc-512: Clobber redzone 0xab->0x%p\n\n", p);
2778         validate_slab_cache(kmalloc_caches + 9);
2779 }
2780 #else
2781 static void resiliency_test(void) {};
2782 #endif
2783
2784 /*
2785  * Generate lists of code addresses where slabcache objects are allocated
2786  * and freed.
2787  */
2788
2789 struct location {
2790         unsigned long count;
2791         void *addr;
2792         long long sum_time;
2793         long min_time;
2794         long max_time;
2795         long min_pid;
2796         long max_pid;
2797         cpumask_t cpus;
2798         nodemask_t nodes;
2799 };
2800
2801 struct loc_track {
2802         unsigned long max;
2803         unsigned long count;
2804         struct location *loc;
2805 };
2806
2807 static void free_loc_track(struct loc_track *t)
2808 {
2809         if (t->max)
2810                 free_pages((unsigned long)t->loc,
2811                         get_order(sizeof(struct location) * t->max));
2812 }
2813
2814 static int alloc_loc_track(struct loc_track *t, unsigned long max)
2815 {
2816         struct location *l;
2817         int order;
2818
2819         if (!max)
2820                 max = PAGE_SIZE / sizeof(struct location);
2821
2822         order = get_order(sizeof(struct location) * max);
2823
2824         l = (void *)__get_free_pages(GFP_KERNEL, order);
2825
2826         if (!l)
2827                 return 0;
2828
2829         if (t->count) {
2830                 memcpy(l, t->loc, sizeof(struct location) * t->count);
2831                 free_loc_track(t);
2832         }
2833         t->max = max;
2834         t->loc = l;
2835         return 1;
2836 }
2837
2838 static int add_location(struct loc_track *t, struct kmem_cache *s,
2839                                 const struct track *track)
2840 {
2841         long start, end, pos;
2842         struct location *l;
2843         void *caddr;
2844         unsigned long age = jiffies - track->when;
2845
2846         start = -1;
2847         end = t->count;
2848
2849         for ( ; ; ) {
2850                 pos = start + (end - start + 1) / 2;
2851
2852                 /*
2853                  * There is nothing at "end". If we end up there
2854                  * we need to add something to before end.
2855                  */
2856                 if (pos == end)
2857                         break;
2858
2859                 caddr = t->loc[pos].addr;
2860                 if (track->addr == caddr) {
2861
2862                         l = &t->loc[pos];
2863                         l->count++;
2864                         if (track->when) {
2865                                 l->sum_time += age;
2866                                 if (age < l->min_time)
2867                                         l->min_time = age;
2868                                 if (age > l->max_time)
2869                                         l->max_time = age;
2870
2871                                 if (track->pid < l->min_pid)
2872                                         l->min_pid = track->pid;
2873                                 if (track->pid > l->max_pid)
2874                                         l->max_pid = track->pid;
2875
2876                                 cpu_set(track->cpu, l->cpus);
2877                         }
2878                         node_set(page_to_nid(virt_to_page(track)), l->nodes);
2879                         return 1;
2880                 }
2881
2882                 if (track->addr < caddr)
2883                         end = pos;
2884                 else
2885                         start = pos;
2886         }
2887
2888         /*
2889          * Not found. Insert new tracking element.
2890          */
2891         if (t->count >= t->max && !alloc_loc_track(t, 2 * t->max))
2892                 return 0;
2893
2894         l = t->loc + pos;
2895         if (pos < t->count)
2896                 memmove(l + 1, l,
2897                         (t->count - pos) * sizeof(struct location));
2898         t->count++;
2899         l->count = 1;
2900         l->addr = track->addr;
2901         l->sum_time = age;
2902         l->min_time = age;
2903         l->max_time = age;
2904         l->min_pid = track->pid;
2905         l->max_pid = track->pid;
2906         cpus_clear(l->cpus);
2907         cpu_set(track->cpu, l->cpus);
2908         nodes_clear(l->nodes);
2909         node_set(page_to_nid(virt_to_page(track)), l->nodes);
2910         return 1;
2911 }
2912
2913 static void process_slab(struct loc_track *t, struct kmem_cache *s,
2914                 struct page *page, enum track_item alloc)
2915 {
2916         void *addr = page_address(page);
2917         DECLARE_BITMAP(map, s->objects);
2918         void *p;
2919
2920         bitmap_zero(map, s->objects);
2921         for_each_free_object(p, s, page->freelist)
2922                 set_bit(slab_index(p, s, addr), map);
2923
2924         for_each_object(p, s, addr)
2925                 if (!test_bit(slab_index(p, s, addr), map))
2926                         add_location(t, s, get_track(s, p, alloc));
2927 }
2928
2929 static int list_locations(struct kmem_cache *s, char *buf,
2930                                         enum track_item alloc)
2931 {
2932         int n = 0;
2933         unsigned long i;
2934         struct loc_track t;
2935         int node;
2936
2937         t.count = 0;
2938         t.max = 0;
2939
2940         /* Push back cpu slabs */
2941         flush_all(s);
2942
2943         for_each_online_node(node) {
2944                 struct kmem_cache_node *n = get_node(s, node);
2945                 unsigned long flags;
2946                 struct page *page;
2947
2948                 if (!atomic_read(&n->nr_slabs))
2949                         continue;
2950
2951                 spin_lock_irqsave(&n->list_lock, flags);
2952                 list_for_each_entry(page, &n->partial, lru)
2953                         process_slab(&t, s, page, alloc);
2954                 list_for_each_entry(page, &n->full, lru)
2955                         process_slab(&t, s, page, alloc);
2956                 spin_unlock_irqrestore(&n->list_lock, flags);
2957         }
2958
2959         for (i = 0; i < t.count; i++) {
2960                 struct location *l = &t.loc[i];
2961
2962                 if (n > PAGE_SIZE - 100)
2963                         break;
2964                 n += sprintf(buf + n, "%7ld ", l->count);
2965
2966                 if (l->addr)
2967                         n += sprint_symbol(buf + n, (unsigned long)l->addr);
2968                 else
2969                         n += sprintf(buf + n, "<not-available>");
2970
2971                 if (l->sum_time != l->min_time) {
2972                         unsigned long remainder;
2973
2974                         n += sprintf(buf + n, " age=%ld/%ld/%ld",
2975                         l->min_time,
2976                         div_long_long_rem(l->sum_time, l->count, &remainder),
2977                         l->max_time);
2978                 } else
2979                         n += sprintf(buf + n, " age=%ld",
2980                                 l->min_time);
2981
2982                 if (l->min_pid != l->max_pid)
2983                         n += sprintf(buf + n, " pid=%ld-%ld",
2984                                 l->min_pid, l->max_pid);
2985                 else
2986                         n += sprintf(buf + n, " pid=%ld",
2987                                 l->min_pid);
2988
2989                 if (num_online_cpus() > 1 && !cpus_empty(l->cpus)) {
2990                         n += sprintf(buf + n, " cpus=");
2991                         n += cpulist_scnprintf(buf + n, PAGE_SIZE - n - 50,
2992                                         l->cpus);
2993                 }
2994
2995                 if (num_online_nodes() > 1 && !nodes_empty(l->nodes)) {
2996                         n += sprintf(buf + n, " nodes=");
2997                         n += nodelist_scnprintf(buf + n, PAGE_SIZE - n - 50,
2998                                         l->nodes);
2999                 }
3000
3001                 n += sprintf(buf + n, "\n");
3002         }
3003
3004         free_loc_track(&t);
3005         if (!t.count)
3006                 n += sprintf(buf, "No data\n");
3007         return n;
3008 }
3009
3010 static unsigned long count_partial(struct kmem_cache_node *n)
3011 {
3012         unsigned long flags;
3013         unsigned long x = 0;
3014         struct page *page;
3015
3016         spin_lock_irqsave(&n->list_lock, flags);
3017         list_for_each_entry(page, &n->partial, lru)
3018                 x += page->inuse;
3019         spin_unlock_irqrestore(&n->list_lock, flags);
3020         return x;
3021 }
3022
3023 enum slab_stat_type {
3024         SL_FULL,
3025         SL_PARTIAL,
3026         SL_CPU,
3027         SL_OBJECTS
3028 };
3029
3030 #define SO_FULL         (1 << SL_FULL)
3031 #define SO_PARTIAL      (1 << SL_PARTIAL)
3032 #define SO_CPU          (1 << SL_CPU)
3033 #define SO_OBJECTS      (1 << SL_OBJECTS)
3034
3035 static unsigned long slab_objects(struct kmem_cache *s,
3036                         char *buf, unsigned long flags)
3037 {
3038         unsigned long total = 0;
3039         int cpu;
3040         int node;
3041         int x;
3042         unsigned long *nodes;
3043         unsigned long *per_cpu;
3044
3045         nodes = kzalloc(2 * sizeof(unsigned long) * nr_node_ids, GFP_KERNEL);
3046         per_cpu = nodes + nr_node_ids;
3047
3048         for_each_possible_cpu(cpu) {
3049                 struct page *page = s->cpu_slab[cpu];
3050                 int node;
3051
3052                 if (page) {
3053                         node = page_to_nid(page);
3054                         if (flags & SO_CPU) {
3055                                 int x = 0;
3056
3057                                 if (flags & SO_OBJECTS)
3058                                         x = page->inuse;
3059                                 else
3060                                         x = 1;
3061                                 total += x;
3062                                 nodes[node] += x;
3063                         }
3064                         per_cpu[node]++;
3065                 }
3066         }
3067
3068         for_each_online_node(node) {
3069                 struct kmem_cache_node *n = get_node(s, node);
3070
3071                 if (flags & SO_PARTIAL) {
3072                         if (flags & SO_OBJECTS)
3073                                 x = count_partial(n);
3074                         else
3075                                 x = n->nr_partial;
3076                         total += x;
3077                         nodes[node] += x;
3078                 }
3079
3080                 if (flags & SO_FULL) {
3081                         int full_slabs = atomic_read(&n->nr_slabs)
3082                                         - per_cpu[node]
3083                                         - n->nr_partial;
3084
3085                         if (flags & SO_OBJECTS)
3086                                 x = full_slabs * s->objects;
3087                         else
3088                                 x = full_slabs;
3089                         total += x;
3090                         nodes[node] += x;
3091                 }
3092         }
3093
3094         x = sprintf(buf, "%lu", total);
3095 #ifdef CONFIG_NUMA
3096         for_each_online_node(node)
3097                 if (nodes[node])
3098                         x += sprintf(buf + x, " N%d=%lu",
3099                                         node, nodes[node]);
3100 #endif
3101         kfree(nodes);
3102         return x + sprintf(buf + x, "\n");
3103 }
3104
3105 static int any_slab_objects(struct kmem_cache *s)
3106 {
3107         int node;
3108         int cpu;
3109
3110         for_each_possible_cpu(cpu)
3111                 if (s->cpu_slab[cpu])
3112                         return 1;
3113
3114         for_each_node(node) {
3115                 struct kmem_cache_node *n = get_node(s, node);
3116
3117                 if (n->nr_partial || atomic_read(&n->nr_slabs))
3118                         return 1;
3119         }
3120         return 0;
3121 }
3122
3123 #define to_slab_attr(n) container_of(n, struct slab_attribute, attr)
3124 #define to_slab(n) container_of(n, struct kmem_cache, kobj);
3125
3126 struct slab_attribute {
3127         struct attribute attr;
3128         ssize_t (*show)(struct kmem_cache *s, char *buf);
3129         ssize_t (*store)(struct kmem_cache *s, const char *x, size_t count);
3130 };
3131
3132 #define SLAB_ATTR_RO(_name) \
3133         static struct slab_attribute _name##_attr = __ATTR_RO(_name)
3134
3135 #define SLAB_ATTR(_name) \
3136         static struct slab_attribute _name##_attr =  \
3137         __ATTR(_name, 0644, _name##_show, _name##_store)
3138
3139 static ssize_t slab_size_show(struct kmem_cache *s, char *buf)
3140 {
3141         return sprintf(buf, "%d\n", s->size);
3142 }
3143 SLAB_ATTR_RO(slab_size);
3144
3145 static ssize_t align_show(struct kmem_cache *s, char *buf)
3146 {
3147         return sprintf(buf, "%d\n", s->align);
3148 }
3149 SLAB_ATTR_RO(align);
3150
3151 static ssize_t object_size_show(struct kmem_cache *s, char *buf)
3152 {
3153         return sprintf(buf, "%d\n", s->objsize);
3154 }
3155 SLAB_ATTR_RO(object_size);
3156
3157 static ssize_t objs_per_slab_show(struct kmem_cache *s, char *buf)
3158 {
3159         return sprintf(buf, "%d\n", s->objects);
3160 }
3161 SLAB_ATTR_RO(objs_per_slab);
3162
3163 static ssize_t order_show(struct kmem_cache *s, char *buf)
3164 {
3165         return sprintf(buf, "%d\n", s->order);
3166 }
3167 SLAB_ATTR_RO(order);
3168
3169 static ssize_t ctor_show(struct kmem_cache *s, char *buf)
3170 {
3171         if (s->ctor) {
3172                 int n = sprint_symbol(buf, (unsigned long)s->ctor);
3173
3174                 return n + sprintf(buf + n, "\n");
3175         }
3176         return 0;
3177 }
3178 SLAB_ATTR_RO(ctor);
3179
3180 static ssize_t dtor_show(struct kmem_cache *s, char *buf)
3181 {
3182         if (s->dtor) {
3183                 int n = sprint_symbol(buf, (unsigned long)s->dtor);
3184
3185                 return n + sprintf(buf + n, "\n");
3186         }
3187         return 0;
3188 }
3189 SLAB_ATTR_RO(dtor);
3190
3191 static ssize_t aliases_show(struct kmem_cache *s, char *buf)
3192 {
3193         return sprintf(buf, "%d\n", s->refcount - 1);
3194 }
3195 SLAB_ATTR_RO(aliases);
3196
3197 static ssize_t slabs_show(struct kmem_cache *s, char *buf)
3198 {
3199         return slab_objects(s, buf, SO_FULL|SO_PARTIAL|SO_CPU);
3200 }
3201 SLAB_ATTR_RO(slabs);
3202
3203 static ssize_t partial_show(struct kmem_cache *s, char *buf)
3204 {
3205         return slab_objects(s, buf, SO_PARTIAL);
3206 }
3207 SLAB_ATTR_RO(partial);
3208
3209 static ssize_t cpu_slabs_show(struct kmem_cache *s, char *buf)
3210 {
3211         return slab_objects(s, buf, SO_CPU);
3212 }
3213 SLAB_ATTR_RO(cpu_slabs);
3214
3215 static ssize_t objects_show(struct kmem_cache *s, char *buf)
3216 {
3217         return slab_objects(s, buf, SO_FULL|SO_PARTIAL|SO_CPU|SO_OBJECTS);
3218 }
3219 SLAB_ATTR_RO(objects);
3220
3221 static ssize_t sanity_checks_show(struct kmem_cache *s, char *buf)
3222 {
3223         return sprintf(buf, "%d\n", !!(s->flags & SLAB_DEBUG_FREE));
3224 }
3225
3226 static ssize_t sanity_checks_store(struct kmem_cache *s,
3227                                 const char *buf, size_t length)
3228 {
3229         s->flags &= ~SLAB_DEBUG_FREE;
3230         if (buf[0] == '1')
3231                 s->flags |= SLAB_DEBUG_FREE;
3232         return length;
3233 }
3234 SLAB_ATTR(sanity_checks);
3235
3236 static ssize_t trace_show(struct kmem_cache *s, char *buf)
3237 {
3238         return sprintf(buf, "%d\n", !!(s->flags & SLAB_TRACE));
3239 }
3240
3241 static ssize_t trace_store(struct kmem_cache *s, const char *buf,
3242                                                         size_t length)
3243 {
3244         s->flags &= ~SLAB_TRACE;
3245         if (buf[0] == '1')
3246                 s->flags |= SLAB_TRACE;
3247         return length;
3248 }
3249 SLAB_ATTR(trace);
3250
3251 static ssize_t reclaim_account_show(struct kmem_cache *s, char *buf)
3252 {
3253         return sprintf(buf, "%d\n", !!(s->flags & SLAB_RECLAIM_ACCOUNT));
3254 }
3255
3256 static ssize_t reclaim_account_store(struct kmem_cache *s,
3257                                 const char *buf, size_t length)
3258 {
3259         s->flags &= ~SLAB_RECLAIM_ACCOUNT;
3260         if (buf[0] == '1')
3261                 s->flags |= SLAB_RECLAIM_ACCOUNT;
3262         return length;
3263 }
3264 SLAB_ATTR(reclaim_account);
3265
3266 static ssize_t hwcache_align_show(struct kmem_cache *s, char *buf)
3267 {
3268         return sprintf(buf, "%d\n", !!(s->flags & SLAB_HWCACHE_ALIGN));
3269 }
3270 SLAB_ATTR_RO(hwcache_align);
3271
3272 #ifdef CONFIG_ZONE_DMA
3273 static ssize_t cache_dma_show(struct kmem_cache *s, char *buf)
3274 {
3275         return sprintf(buf, "%d\n", !!(s->flags & SLAB_CACHE_DMA));
3276 }
3277 SLAB_ATTR_RO(cache_dma);
3278 #endif
3279
3280 static ssize_t destroy_by_rcu_show(struct kmem_cache *s, char *buf)
3281 {
3282         return sprintf(buf, "%d\n", !!(s->flags & SLAB_DESTROY_BY_RCU));
3283 }
3284 SLAB_ATTR_RO(destroy_by_rcu);
3285
3286 static ssize_t red_zone_show(struct kmem_cache *s, char *buf)
3287 {
3288         return sprintf(buf, "%d\n", !!(s->flags & SLAB_RED_ZONE));
3289 }
3290
3291 static ssize_t red_zone_store(struct kmem_cache *s,
3292                                 const char *buf, size_t length)
3293 {
3294         if (any_slab_objects(s))
3295                 return -EBUSY;
3296
3297         s->flags &= ~SLAB_RED_ZONE;
3298         if (buf[0] == '1')
3299                 s->flags |= SLAB_RED_ZONE;
3300         calculate_sizes(s);
3301         return length;
3302 }
3303 SLAB_ATTR(red_zone);
3304
3305 static ssize_t poison_show(struct kmem_cache *s, char *buf)
3306 {
3307         return sprintf(buf, "%d\n", !!(s->flags & SLAB_POISON));
3308 }
3309
3310 static ssize_t poison_store(struct kmem_cache *s,
3311                                 const char *buf, size_t length)
3312 {
3313         if (any_slab_objects(s))
3314                 return -EBUSY;
3315
3316         s->flags &= ~SLAB_POISON;
3317         if (buf[0] == '1')
3318                 s->flags |= SLAB_POISON;
3319         calculate_sizes(s);
3320         return length;
3321 }
3322 SLAB_ATTR(poison);
3323
3324 static ssize_t store_user_show(struct kmem_cache *s, char *buf)
3325 {
3326         return sprintf(buf, "%d\n", !!(s->flags & SLAB_STORE_USER));
3327 }
3328
3329 static ssize_t store_user_store(struct kmem_cache *s,
3330                                 const char *buf, size_t length)
3331 {
3332         if (any_slab_objects(s))
3333                 return -EBUSY;
3334
3335         s->flags &= ~SLAB_STORE_USER;
3336         if (buf[0] == '1')
3337                 s->flags |= SLAB_STORE_USER;
3338         calculate_sizes(s);
3339         return length;
3340 }
3341 SLAB_ATTR(store_user);
3342
3343 static ssize_t validate_show(struct kmem_cache *s, char *buf)
3344 {
3345         return 0;
3346 }
3347
3348 static ssize_t validate_store(struct kmem_cache *s,
3349                         const char *buf, size_t length)
3350 {
3351         if (buf[0] == '1')
3352                 validate_slab_cache(s);
3353         else
3354                 return -EINVAL;
3355         return length;
3356 }
3357 SLAB_ATTR(validate);
3358
3359 static ssize_t shrink_show(struct kmem_cache *s, char *buf)
3360 {
3361         return 0;
3362 }
3363
3364 static ssize_t shrink_store(struct kmem_cache *s,
3365                         const char *buf, size_t length)
3366 {
3367         if (buf[0] == '1') {
3368                 int rc = kmem_cache_shrink(s);
3369
3370                 if (rc)
3371                         return rc;
3372         } else
3373                 return -EINVAL;
3374         return length;
3375 }
3376 SLAB_ATTR(shrink);
3377
3378 static ssize_t alloc_calls_show(struct kmem_cache *s, char *buf)
3379 {
3380         if (!(s->flags & SLAB_STORE_USER))
3381                 return -ENOSYS;
3382         return list_locations(s, buf, TRACK_ALLOC);
3383 }
3384 SLAB_ATTR_RO(alloc_calls);
3385
3386 static ssize_t free_calls_show(struct kmem_cache *s, char *buf)
3387 {
3388         if (!(s->flags & SLAB_STORE_USER))
3389                 return -ENOSYS;
3390         return list_locations(s, buf, TRACK_FREE);
3391 }
3392 SLAB_ATTR_RO(free_calls);
3393
3394 #ifdef CONFIG_NUMA
3395 static ssize_t defrag_ratio_show(struct kmem_cache *s, char *buf)
3396 {
3397         return sprintf(buf, "%d\n", s->defrag_ratio / 10);
3398 }
3399
3400 static ssize_t defrag_ratio_store(struct kmem_cache *s,
3401                                 const char *buf, size_t length)
3402 {
3403         int n = simple_strtoul(buf, NULL, 10);
3404
3405         if (n < 100)
3406                 s->defrag_ratio = n * 10;
3407         return length;
3408 }
3409 SLAB_ATTR(defrag_ratio);
3410 #endif
3411
3412 static struct attribute * slab_attrs[] = {
3413         &slab_size_attr.attr,
3414         &object_size_attr.attr,
3415         &objs_per_slab_attr.attr,
3416         &order_attr.attr,
3417         &objects_attr.attr,
3418         &slabs_attr.attr,
3419         &partial_attr.attr,
3420         &cpu_slabs_attr.attr,
3421         &ctor_attr.attr,
3422         &dtor_attr.attr,
3423         &aliases_attr.attr,
3424         &align_attr.attr,
3425         &sanity_checks_attr.attr,
3426         &trace_attr.attr,
3427         &hwcache_align_attr.attr,
3428         &reclaim_account_attr.attr,
3429         &destroy_by_rcu_attr.attr,
3430         &red_zone_attr.attr,
3431         &poison_attr.attr,
3432         &store_user_attr.attr,
3433         &validate_attr.attr,
3434         &shrink_attr.attr,
3435         &alloc_calls_attr.attr,
3436         &free_calls_attr.attr,
3437 #ifdef CONFIG_ZONE_DMA
3438         &cache_dma_attr.attr,
3439 #endif
3440 #ifdef CONFIG_NUMA
3441         &defrag_ratio_attr.attr,
3442 #endif
3443         NULL
3444 };
3445
3446 static struct attribute_group slab_attr_group = {
3447         .attrs = slab_attrs,
3448 };
3449
3450 static ssize_t slab_attr_show(struct kobject *kobj,
3451                                 struct attribute *attr,
3452                                 char *buf)
3453 {
3454         struct slab_attribute *attribute;
3455         struct kmem_cache *s;
3456         int err;
3457
3458         attribute = to_slab_attr(attr);
3459         s = to_slab(kobj);
3460
3461         if (!attribute->show)
3462                 return -EIO;
3463
3464         err = attribute->show(s, buf);
3465
3466         return err;
3467 }
3468
3469 static ssize_t slab_attr_store(struct kobject *kobj,
3470                                 struct attribute *attr,
3471                                 const char *buf, size_t len)
3472 {
3473         struct slab_attribute *attribute;
3474         struct kmem_cache *s;
3475         int err;
3476
3477         attribute = to_slab_attr(attr);
3478         s = to_slab(kobj);
3479
3480         if (!attribute->store)
3481                 return -EIO;
3482
3483         err = attribute->store(s, buf, len);
3484
3485         return err;
3486 }
3487
3488 static struct sysfs_ops slab_sysfs_ops = {
3489         .show = slab_attr_show,
3490         .store = slab_attr_store,
3491 };
3492
3493 static struct kobj_type slab_ktype = {
3494         .sysfs_ops = &slab_sysfs_ops,
3495 };
3496
3497 static int uevent_filter(struct kset *kset, struct kobject *kobj)
3498 {
3499         struct kobj_type *ktype = get_ktype(kobj);
3500
3501         if (ktype == &slab_ktype)
3502                 return 1;
3503         return 0;
3504 }
3505
3506 static struct kset_uevent_ops slab_uevent_ops = {
3507         .filter = uevent_filter,
3508 };
3509
3510 decl_subsys(slab, &slab_ktype, &slab_uevent_ops);
3511
3512 #define ID_STR_LENGTH 64
3513
3514 /* Create a unique string id for a slab cache:
3515  * format
3516  * :[flags-]size:[memory address of kmemcache]
3517  */
3518 static char *create_unique_id(struct kmem_cache *s)
3519 {
3520         char *name = kmalloc(ID_STR_LENGTH, GFP_KERNEL);
3521         char *p = name;
3522
3523         BUG_ON(!name);
3524
3525         *p++ = ':';
3526         /*
3527          * First flags affecting slabcache operations. We will only
3528          * get here for aliasable slabs so we do not need to support
3529          * too many flags. The flags here must cover all flags that
3530          * are matched during merging to guarantee that the id is
3531          * unique.
3532          */
3533         if (s->flags & SLAB_CACHE_DMA)
3534                 *p++ = 'd';
3535         if (s->flags & SLAB_RECLAIM_ACCOUNT)
3536                 *p++ = 'a';
3537         if (s->flags & SLAB_DEBUG_FREE)
3538                 *p++ = 'F';
3539         if (p != name + 1)
3540                 *p++ = '-';
3541         p += sprintf(p, "%07d", s->size);
3542         BUG_ON(p > name + ID_STR_LENGTH - 1);
3543         return name;
3544 }
3545
3546 static int sysfs_slab_add(struct kmem_cache *s)
3547 {
3548         int err;
3549         const char *name;
3550         int unmergeable;
3551
3552         if (slab_state < SYSFS)
3553                 /* Defer until later */
3554                 return 0;
3555
3556         unmergeable = slab_unmergeable(s);
3557         if (unmergeable) {
3558                 /*
3559                  * Slabcache can never be merged so we can use the name proper.
3560                  * This is typically the case for debug situations. In that
3561                  * case we can catch duplicate names easily.
3562                  */
3563                 sysfs_remove_link(&slab_subsys.kobj, s->name);
3564                 name = s->name;
3565         } else {
3566                 /*
3567                  * Create a unique name for the slab as a target
3568                  * for the symlinks.
3569                  */
3570                 name = create_unique_id(s);
3571         }
3572
3573         kobj_set_kset_s(s, slab_subsys);
3574         kobject_set_name(&s->kobj, name);
3575         kobject_init(&s->kobj);
3576         err = kobject_add(&s->kobj);
3577         if (err)
3578                 return err;
3579
3580         err = sysfs_create_group(&s->kobj, &slab_attr_group);
3581         if (err)
3582                 return err;
3583         kobject_uevent(&s->kobj, KOBJ_ADD);
3584         if (!unmergeable) {
3585                 /* Setup first alias */
3586                 sysfs_slab_alias(s, s->name);
3587                 kfree(name);
3588         }
3589         return 0;
3590 }
3591
3592 static void sysfs_slab_remove(struct kmem_cache *s)
3593 {
3594         kobject_uevent(&s->kobj, KOBJ_REMOVE);
3595         kobject_del(&s->kobj);
3596 }
3597
3598 /*
3599  * Need to buffer aliases during bootup until sysfs becomes
3600  * available lest we loose that information.
3601  */
3602 struct saved_alias {
3603         struct kmem_cache *s;
3604         const char *name;
3605         struct saved_alias *next;
3606 };
3607
3608 struct saved_alias *alias_list;
3609
3610 static int sysfs_slab_alias(struct kmem_cache *s, const char *name)
3611 {
3612         struct saved_alias *al;
3613
3614         if (slab_state == SYSFS) {
3615                 /*
3616                  * If we have a leftover link then remove it.
3617                  */
3618                 sysfs_remove_link(&slab_subsys.kobj, name);
3619                 return sysfs_create_link(&slab_subsys.kobj,
3620                                                 &s->kobj, name);
3621         }
3622
3623         al = kmalloc(sizeof(struct saved_alias), GFP_KERNEL);
3624         if (!al)
3625                 return -ENOMEM;
3626
3627         al->s = s;
3628         al->name = name;
3629         al->next = alias_list;
3630         alias_list = al;
3631         return 0;
3632 }
3633
3634 static int __init slab_sysfs_init(void)
3635 {
3636         struct list_head *h;
3637         int err;
3638
3639         err = subsystem_register(&slab_subsys);
3640         if (err) {
3641                 printk(KERN_ERR "Cannot register slab subsystem.\n");
3642                 return -ENOSYS;
3643         }
3644
3645         slab_state = SYSFS;
3646
3647         list_for_each(h, &slab_caches) {
3648                 struct kmem_cache *s =
3649                         container_of(h, struct kmem_cache, list);
3650
3651                 err = sysfs_slab_add(s);
3652                 BUG_ON(err);
3653         }
3654
3655         while (alias_list) {
3656                 struct saved_alias *al = alias_list;
3657
3658                 alias_list = alias_list->next;
3659                 err = sysfs_slab_alias(al->s, al->name);
3660                 BUG_ON(err);
3661                 kfree(al);
3662         }
3663
3664         resiliency_test();
3665         return 0;
3666 }
3667
3668 __initcall(slab_sysfs_init);
3669 #endif