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