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