mm/slub.c: use register_hotmemory_notifier()
[linux-3.10.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 or atomic operatios
6  * and only uses a centralized lock to manage a pool of partial slabs.
7  *
8  * (C) 2007 SGI, Christoph Lameter
9  * (C) 2011 Linux Foundation, Christoph Lameter
10  */
11
12 #include <linux/mm.h>
13 #include <linux/swap.h> /* struct reclaim_state */
14 #include <linux/module.h>
15 #include <linux/bit_spinlock.h>
16 #include <linux/interrupt.h>
17 #include <linux/bitops.h>
18 #include <linux/slab.h>
19 #include "slab.h"
20 #include <linux/proc_fs.h>
21 #include <linux/notifier.h>
22 #include <linux/seq_file.h>
23 #include <linux/kmemcheck.h>
24 #include <linux/cpu.h>
25 #include <linux/cpuset.h>
26 #include <linux/mempolicy.h>
27 #include <linux/ctype.h>
28 #include <linux/debugobjects.h>
29 #include <linux/kallsyms.h>
30 #include <linux/memory.h>
31 #include <linux/math64.h>
32 #include <linux/fault-inject.h>
33 #include <linux/stacktrace.h>
34 #include <linux/prefetch.h>
35 #include <linux/memcontrol.h>
36
37 #include <trace/events/kmem.h>
38
39 #include "internal.h"
40
41 /*
42  * Lock order:
43  *   1. slab_mutex (Global Mutex)
44  *   2. node->list_lock
45  *   3. slab_lock(page) (Only on some arches and for debugging)
46  *
47  *   slab_mutex
48  *
49  *   The role of the slab_mutex is to protect the list of all the slabs
50  *   and to synchronize major metadata changes to slab cache structures.
51  *
52  *   The slab_lock is only used for debugging and on arches that do not
53  *   have the ability to do a cmpxchg_double. It only protects the second
54  *   double word in the page struct. Meaning
55  *      A. page->freelist       -> List of object free in a page
56  *      B. page->counters       -> Counters of objects
57  *      C. page->frozen         -> frozen state
58  *
59  *   If a slab is frozen then it is exempt from list management. It is not
60  *   on any list. The processor that froze the slab is the one who can
61  *   perform list operations on the page. Other processors may put objects
62  *   onto the freelist but the processor that froze the slab is the only
63  *   one that can retrieve the objects from the page's freelist.
64  *
65  *   The list_lock protects the partial and full list on each node and
66  *   the partial slab counter. If taken then no new slabs may be added or
67  *   removed from the lists nor make the number of partial slabs be modified.
68  *   (Note that the total number of slabs is an atomic value that may be
69  *   modified without taking the list lock).
70  *
71  *   The list_lock is a centralized lock and thus we avoid taking it as
72  *   much as possible. As long as SLUB does not have to handle partial
73  *   slabs, operations can continue without any centralized lock. F.e.
74  *   allocating a long series of objects that fill up slabs does not require
75  *   the list lock.
76  *   Interrupts are disabled during allocation and deallocation in order to
77  *   make the slab allocator safe to use in the context of an irq. In addition
78  *   interrupts are disabled to ensure that the processor does not change
79  *   while handling per_cpu slabs, due to kernel preemption.
80  *
81  * SLUB assigns one slab for allocation to each processor.
82  * Allocations only occur from these slabs called cpu slabs.
83  *
84  * Slabs with free elements are kept on a partial list and during regular
85  * operations no list for full slabs is used. If an object in a full slab is
86  * freed then the slab will show up again on the partial lists.
87  * We track full slabs for debugging purposes though because otherwise we
88  * cannot scan all objects.
89  *
90  * Slabs are freed when they become empty. Teardown and setup is
91  * minimal so we rely on the page allocators per cpu caches for
92  * fast frees and allocs.
93  *
94  * Overloading of page flags that are otherwise used for LRU management.
95  *
96  * PageActive           The slab is frozen and exempt from list processing.
97  *                      This means that the slab is dedicated to a purpose
98  *                      such as satisfying allocations for a specific
99  *                      processor. Objects may be freed in the slab while
100  *                      it is frozen but slab_free will then skip the usual
101  *                      list operations. It is up to the processor holding
102  *                      the slab to integrate the slab into the slab lists
103  *                      when the slab is no longer needed.
104  *
105  *                      One use of this flag is to mark slabs that are
106  *                      used for allocations. Then such a slab becomes a cpu
107  *                      slab. The cpu slab may be equipped with an additional
108  *                      freelist that allows lockless access to
109  *                      free objects in addition to the regular freelist
110  *                      that requires the slab lock.
111  *
112  * PageError            Slab requires special handling due to debug
113  *                      options set. This moves slab handling out of
114  *                      the fast path and disables lockless freelists.
115  */
116
117 static inline int kmem_cache_debug(struct kmem_cache *s)
118 {
119 #ifdef CONFIG_SLUB_DEBUG
120         return unlikely(s->flags & SLAB_DEBUG_FLAGS);
121 #else
122         return 0;
123 #endif
124 }
125
126 /*
127  * Issues still to be resolved:
128  *
129  * - Support PAGE_ALLOC_DEBUG. Should be easy to do.
130  *
131  * - Variable sizing of the per node arrays
132  */
133
134 /* Enable to test recovery from slab corruption on boot */
135 #undef SLUB_RESILIENCY_TEST
136
137 /* Enable to log cmpxchg failures */
138 #undef SLUB_DEBUG_CMPXCHG
139
140 /*
141  * Mininum number of partial slabs. These will be left on the partial
142  * lists even if they are empty. kmem_cache_shrink may reclaim them.
143  */
144 #define MIN_PARTIAL 5
145
146 /*
147  * Maximum number of desirable partial slabs.
148  * The existence of more partial slabs makes kmem_cache_shrink
149  * sort the partial list by the number of objects in the.
150  */
151 #define MAX_PARTIAL 10
152
153 #define DEBUG_DEFAULT_FLAGS (SLAB_DEBUG_FREE | SLAB_RED_ZONE | \
154                                 SLAB_POISON | SLAB_STORE_USER)
155
156 /*
157  * Debugging flags that require metadata to be stored in the slab.  These get
158  * disabled when slub_debug=O is used and a cache's min order increases with
159  * metadata.
160  */
161 #define DEBUG_METADATA_FLAGS (SLAB_RED_ZONE | SLAB_POISON | SLAB_STORE_USER)
162
163 /*
164  * Set of flags that will prevent slab merging
165  */
166 #define SLUB_NEVER_MERGE (SLAB_RED_ZONE | SLAB_POISON | SLAB_STORE_USER | \
167                 SLAB_TRACE | SLAB_DESTROY_BY_RCU | SLAB_NOLEAKTRACE | \
168                 SLAB_FAILSLAB)
169
170 #define SLUB_MERGE_SAME (SLAB_DEBUG_FREE | SLAB_RECLAIM_ACCOUNT | \
171                 SLAB_CACHE_DMA | SLAB_NOTRACK)
172
173 #define OO_SHIFT        16
174 #define OO_MASK         ((1 << OO_SHIFT) - 1)
175 #define MAX_OBJS_PER_PAGE       32767 /* since page.objects is u15 */
176
177 /* Internal SLUB flags */
178 #define __OBJECT_POISON         0x80000000UL /* Poison object */
179 #define __CMPXCHG_DOUBLE        0x40000000UL /* Use cmpxchg_double */
180
181 #ifdef CONFIG_SMP
182 static struct notifier_block slab_notifier;
183 #endif
184
185 /*
186  * Tracking user of a slab.
187  */
188 #define TRACK_ADDRS_COUNT 16
189 struct track {
190         unsigned long addr;     /* Called from address */
191 #ifdef CONFIG_STACKTRACE
192         unsigned long addrs[TRACK_ADDRS_COUNT]; /* Called from address */
193 #endif
194         int cpu;                /* Was running on cpu */
195         int pid;                /* Pid context */
196         unsigned long when;     /* When did the operation occur */
197 };
198
199 enum track_item { TRACK_ALLOC, TRACK_FREE };
200
201 #ifdef CONFIG_SYSFS
202 static int sysfs_slab_add(struct kmem_cache *);
203 static int sysfs_slab_alias(struct kmem_cache *, const char *);
204 static void sysfs_slab_remove(struct kmem_cache *);
205 static void memcg_propagate_slab_attrs(struct kmem_cache *s);
206 #else
207 static inline int sysfs_slab_add(struct kmem_cache *s) { return 0; }
208 static inline int sysfs_slab_alias(struct kmem_cache *s, const char *p)
209                                                         { return 0; }
210 static inline void sysfs_slab_remove(struct kmem_cache *s) { }
211
212 static inline void memcg_propagate_slab_attrs(struct kmem_cache *s) { }
213 #endif
214
215 static inline void stat(const struct kmem_cache *s, enum stat_item si)
216 {
217 #ifdef CONFIG_SLUB_STATS
218         __this_cpu_inc(s->cpu_slab->stat[si]);
219 #endif
220 }
221
222 /********************************************************************
223  *                      Core slab cache functions
224  *******************************************************************/
225
226 static inline struct kmem_cache_node *get_node(struct kmem_cache *s, int node)
227 {
228         return s->node[node];
229 }
230
231 /* Verify that a pointer has an address that is valid within a slab page */
232 static inline int check_valid_pointer(struct kmem_cache *s,
233                                 struct page *page, const void *object)
234 {
235         void *base;
236
237         if (!object)
238                 return 1;
239
240         base = page_address(page);
241         if (object < base || object >= base + page->objects * s->size ||
242                 (object - base) % s->size) {
243                 return 0;
244         }
245
246         return 1;
247 }
248
249 static inline void *get_freepointer(struct kmem_cache *s, void *object)
250 {
251         return *(void **)(object + s->offset);
252 }
253
254 static void prefetch_freepointer(const struct kmem_cache *s, void *object)
255 {
256         prefetch(object + s->offset);
257 }
258
259 static inline void *get_freepointer_safe(struct kmem_cache *s, void *object)
260 {
261         void *p;
262
263 #ifdef CONFIG_DEBUG_PAGEALLOC
264         probe_kernel_read(&p, (void **)(object + s->offset), sizeof(p));
265 #else
266         p = get_freepointer(s, object);
267 #endif
268         return p;
269 }
270
271 static inline void set_freepointer(struct kmem_cache *s, void *object, void *fp)
272 {
273         *(void **)(object + s->offset) = fp;
274 }
275
276 /* Loop over all objects in a slab */
277 #define for_each_object(__p, __s, __addr, __objects) \
278         for (__p = (__addr); __p < (__addr) + (__objects) * (__s)->size;\
279                         __p += (__s)->size)
280
281 /* Determine object index from a given position */
282 static inline int slab_index(void *p, struct kmem_cache *s, void *addr)
283 {
284         return (p - addr) / s->size;
285 }
286
287 static inline size_t slab_ksize(const struct kmem_cache *s)
288 {
289 #ifdef CONFIG_SLUB_DEBUG
290         /*
291          * Debugging requires use of the padding between object
292          * and whatever may come after it.
293          */
294         if (s->flags & (SLAB_RED_ZONE | SLAB_POISON))
295                 return s->object_size;
296
297 #endif
298         /*
299          * If we have the need to store the freelist pointer
300          * back there or track user information then we can
301          * only use the space before that information.
302          */
303         if (s->flags & (SLAB_DESTROY_BY_RCU | SLAB_STORE_USER))
304                 return s->inuse;
305         /*
306          * Else we can use all the padding etc for the allocation
307          */
308         return s->size;
309 }
310
311 static inline int order_objects(int order, unsigned long size, int reserved)
312 {
313         return ((PAGE_SIZE << order) - reserved) / size;
314 }
315
316 static inline struct kmem_cache_order_objects oo_make(int order,
317                 unsigned long size, int reserved)
318 {
319         struct kmem_cache_order_objects x = {
320                 (order << OO_SHIFT) + order_objects(order, size, reserved)
321         };
322
323         return x;
324 }
325
326 static inline int oo_order(struct kmem_cache_order_objects x)
327 {
328         return x.x >> OO_SHIFT;
329 }
330
331 static inline int oo_objects(struct kmem_cache_order_objects x)
332 {
333         return x.x & OO_MASK;
334 }
335
336 /*
337  * Per slab locking using the pagelock
338  */
339 static __always_inline void slab_lock(struct page *page)
340 {
341         bit_spin_lock(PG_locked, &page->flags);
342 }
343
344 static __always_inline void slab_unlock(struct page *page)
345 {
346         __bit_spin_unlock(PG_locked, &page->flags);
347 }
348
349 /* Interrupts must be disabled (for the fallback code to work right) */
350 static inline bool __cmpxchg_double_slab(struct kmem_cache *s, struct page *page,
351                 void *freelist_old, unsigned long counters_old,
352                 void *freelist_new, unsigned long counters_new,
353                 const char *n)
354 {
355         VM_BUG_ON(!irqs_disabled());
356 #if defined(CONFIG_HAVE_CMPXCHG_DOUBLE) && \
357     defined(CONFIG_HAVE_ALIGNED_STRUCT_PAGE)
358         if (s->flags & __CMPXCHG_DOUBLE) {
359                 if (cmpxchg_double(&page->freelist, &page->counters,
360                         freelist_old, counters_old,
361                         freelist_new, counters_new))
362                 return 1;
363         } else
364 #endif
365         {
366                 slab_lock(page);
367                 if (page->freelist == freelist_old && page->counters == counters_old) {
368                         page->freelist = freelist_new;
369                         page->counters = counters_new;
370                         slab_unlock(page);
371                         return 1;
372                 }
373                 slab_unlock(page);
374         }
375
376         cpu_relax();
377         stat(s, CMPXCHG_DOUBLE_FAIL);
378
379 #ifdef SLUB_DEBUG_CMPXCHG
380         printk(KERN_INFO "%s %s: cmpxchg double redo ", n, s->name);
381 #endif
382
383         return 0;
384 }
385
386 static inline bool cmpxchg_double_slab(struct kmem_cache *s, struct page *page,
387                 void *freelist_old, unsigned long counters_old,
388                 void *freelist_new, unsigned long counters_new,
389                 const char *n)
390 {
391 #if defined(CONFIG_HAVE_CMPXCHG_DOUBLE) && \
392     defined(CONFIG_HAVE_ALIGNED_STRUCT_PAGE)
393         if (s->flags & __CMPXCHG_DOUBLE) {
394                 if (cmpxchg_double(&page->freelist, &page->counters,
395                         freelist_old, counters_old,
396                         freelist_new, counters_new))
397                 return 1;
398         } else
399 #endif
400         {
401                 unsigned long flags;
402
403                 local_irq_save(flags);
404                 slab_lock(page);
405                 if (page->freelist == freelist_old && page->counters == counters_old) {
406                         page->freelist = freelist_new;
407                         page->counters = counters_new;
408                         slab_unlock(page);
409                         local_irq_restore(flags);
410                         return 1;
411                 }
412                 slab_unlock(page);
413                 local_irq_restore(flags);
414         }
415
416         cpu_relax();
417         stat(s, CMPXCHG_DOUBLE_FAIL);
418
419 #ifdef SLUB_DEBUG_CMPXCHG
420         printk(KERN_INFO "%s %s: cmpxchg double redo ", n, s->name);
421 #endif
422
423         return 0;
424 }
425
426 #ifdef CONFIG_SLUB_DEBUG
427 /*
428  * Determine a map of object in use on a page.
429  *
430  * Node listlock must be held to guarantee that the page does
431  * not vanish from under us.
432  */
433 static void get_map(struct kmem_cache *s, struct page *page, unsigned long *map)
434 {
435         void *p;
436         void *addr = page_address(page);
437
438         for (p = page->freelist; p; p = get_freepointer(s, p))
439                 set_bit(slab_index(p, s, addr), map);
440 }
441
442 /*
443  * Debug settings:
444  */
445 #ifdef CONFIG_SLUB_DEBUG_ON
446 static int slub_debug = DEBUG_DEFAULT_FLAGS;
447 #else
448 static int slub_debug;
449 #endif
450
451 static char *slub_debug_slabs;
452 static int disable_higher_order_debug;
453
454 /*
455  * Object debugging
456  */
457 static void print_section(char *text, u8 *addr, unsigned int length)
458 {
459         print_hex_dump(KERN_ERR, text, DUMP_PREFIX_ADDRESS, 16, 1, addr,
460                         length, 1);
461 }
462
463 static struct track *get_track(struct kmem_cache *s, void *object,
464         enum track_item alloc)
465 {
466         struct track *p;
467
468         if (s->offset)
469                 p = object + s->offset + sizeof(void *);
470         else
471                 p = object + s->inuse;
472
473         return p + alloc;
474 }
475
476 static void set_track(struct kmem_cache *s, void *object,
477                         enum track_item alloc, unsigned long addr)
478 {
479         struct track *p = get_track(s, object, alloc);
480
481         if (addr) {
482 #ifdef CONFIG_STACKTRACE
483                 struct stack_trace trace;
484                 int i;
485
486                 trace.nr_entries = 0;
487                 trace.max_entries = TRACK_ADDRS_COUNT;
488                 trace.entries = p->addrs;
489                 trace.skip = 3;
490                 save_stack_trace(&trace);
491
492                 /* See rant in lockdep.c */
493                 if (trace.nr_entries != 0 &&
494                     trace.entries[trace.nr_entries - 1] == ULONG_MAX)
495                         trace.nr_entries--;
496
497                 for (i = trace.nr_entries; i < TRACK_ADDRS_COUNT; i++)
498                         p->addrs[i] = 0;
499 #endif
500                 p->addr = addr;
501                 p->cpu = smp_processor_id();
502                 p->pid = current->pid;
503                 p->when = jiffies;
504         } else
505                 memset(p, 0, sizeof(struct track));
506 }
507
508 static void init_tracking(struct kmem_cache *s, void *object)
509 {
510         if (!(s->flags & SLAB_STORE_USER))
511                 return;
512
513         set_track(s, object, TRACK_FREE, 0UL);
514         set_track(s, object, TRACK_ALLOC, 0UL);
515 }
516
517 static void print_track(const char *s, struct track *t)
518 {
519         if (!t->addr)
520                 return;
521
522         printk(KERN_ERR "INFO: %s in %pS age=%lu cpu=%u pid=%d\n",
523                 s, (void *)t->addr, jiffies - t->when, t->cpu, t->pid);
524 #ifdef CONFIG_STACKTRACE
525         {
526                 int i;
527                 for (i = 0; i < TRACK_ADDRS_COUNT; i++)
528                         if (t->addrs[i])
529                                 printk(KERN_ERR "\t%pS\n", (void *)t->addrs[i]);
530                         else
531                                 break;
532         }
533 #endif
534 }
535
536 static void print_tracking(struct kmem_cache *s, void *object)
537 {
538         if (!(s->flags & SLAB_STORE_USER))
539                 return;
540
541         print_track("Allocated", get_track(s, object, TRACK_ALLOC));
542         print_track("Freed", get_track(s, object, TRACK_FREE));
543 }
544
545 static void print_page_info(struct page *page)
546 {
547         printk(KERN_ERR "INFO: Slab 0x%p objects=%u used=%u fp=0x%p flags=0x%04lx\n",
548                 page, page->objects, page->inuse, page->freelist, page->flags);
549
550 }
551
552 static void slab_bug(struct kmem_cache *s, char *fmt, ...)
553 {
554         va_list args;
555         char buf[100];
556
557         va_start(args, fmt);
558         vsnprintf(buf, sizeof(buf), fmt, args);
559         va_end(args);
560         printk(KERN_ERR "========================================"
561                         "=====================================\n");
562         printk(KERN_ERR "BUG %s (%s): %s\n", s->name, print_tainted(), buf);
563         printk(KERN_ERR "----------------------------------------"
564                         "-------------------------------------\n\n");
565
566         add_taint(TAINT_BAD_PAGE, LOCKDEP_NOW_UNRELIABLE);
567 }
568
569 static void slab_fix(struct kmem_cache *s, char *fmt, ...)
570 {
571         va_list args;
572         char buf[100];
573
574         va_start(args, fmt);
575         vsnprintf(buf, sizeof(buf), fmt, args);
576         va_end(args);
577         printk(KERN_ERR "FIX %s: %s\n", s->name, buf);
578 }
579
580 static void print_trailer(struct kmem_cache *s, struct page *page, u8 *p)
581 {
582         unsigned int off;       /* Offset of last byte */
583         u8 *addr = page_address(page);
584
585         print_tracking(s, p);
586
587         print_page_info(page);
588
589         printk(KERN_ERR "INFO: Object 0x%p @offset=%tu fp=0x%p\n\n",
590                         p, p - addr, get_freepointer(s, p));
591
592         if (p > addr + 16)
593                 print_section("Bytes b4 ", p - 16, 16);
594
595         print_section("Object ", p, min_t(unsigned long, s->object_size,
596                                 PAGE_SIZE));
597         if (s->flags & SLAB_RED_ZONE)
598                 print_section("Redzone ", p + s->object_size,
599                         s->inuse - s->object_size);
600
601         if (s->offset)
602                 off = s->offset + sizeof(void *);
603         else
604                 off = s->inuse;
605
606         if (s->flags & SLAB_STORE_USER)
607                 off += 2 * sizeof(struct track);
608
609         if (off != s->size)
610                 /* Beginning of the filler is the free pointer */
611                 print_section("Padding ", p + off, s->size - off);
612
613         dump_stack();
614 }
615
616 static void object_err(struct kmem_cache *s, struct page *page,
617                         u8 *object, char *reason)
618 {
619         slab_bug(s, "%s", reason);
620         print_trailer(s, page, object);
621 }
622
623 static void slab_err(struct kmem_cache *s, struct page *page, const char *fmt, ...)
624 {
625         va_list args;
626         char buf[100];
627
628         va_start(args, fmt);
629         vsnprintf(buf, sizeof(buf), fmt, args);
630         va_end(args);
631         slab_bug(s, "%s", buf);
632         print_page_info(page);
633         dump_stack();
634 }
635
636 static void init_object(struct kmem_cache *s, void *object, u8 val)
637 {
638         u8 *p = object;
639
640         if (s->flags & __OBJECT_POISON) {
641                 memset(p, POISON_FREE, s->object_size - 1);
642                 p[s->object_size - 1] = POISON_END;
643         }
644
645         if (s->flags & SLAB_RED_ZONE)
646                 memset(p + s->object_size, val, s->inuse - s->object_size);
647 }
648
649 static void restore_bytes(struct kmem_cache *s, char *message, u8 data,
650                                                 void *from, void *to)
651 {
652         slab_fix(s, "Restoring 0x%p-0x%p=0x%x\n", from, to - 1, data);
653         memset(from, data, to - from);
654 }
655
656 static int check_bytes_and_report(struct kmem_cache *s, struct page *page,
657                         u8 *object, char *what,
658                         u8 *start, unsigned int value, unsigned int bytes)
659 {
660         u8 *fault;
661         u8 *end;
662
663         fault = memchr_inv(start, value, bytes);
664         if (!fault)
665                 return 1;
666
667         end = start + bytes;
668         while (end > fault && end[-1] == value)
669                 end--;
670
671         slab_bug(s, "%s overwritten", what);
672         printk(KERN_ERR "INFO: 0x%p-0x%p. First byte 0x%x instead of 0x%x\n",
673                                         fault, end - 1, fault[0], value);
674         print_trailer(s, page, object);
675
676         restore_bytes(s, what, value, fault, end);
677         return 0;
678 }
679
680 /*
681  * Object layout:
682  *
683  * object address
684  *      Bytes of the object to be managed.
685  *      If the freepointer may overlay the object then the free
686  *      pointer is the first word of the object.
687  *
688  *      Poisoning uses 0x6b (POISON_FREE) and the last byte is
689  *      0xa5 (POISON_END)
690  *
691  * object + s->object_size
692  *      Padding to reach word boundary. This is also used for Redzoning.
693  *      Padding is extended by another word if Redzoning is enabled and
694  *      object_size == inuse.
695  *
696  *      We fill with 0xbb (RED_INACTIVE) for inactive objects and with
697  *      0xcc (RED_ACTIVE) for objects in use.
698  *
699  * object + s->inuse
700  *      Meta data starts here.
701  *
702  *      A. Free pointer (if we cannot overwrite object on free)
703  *      B. Tracking data for SLAB_STORE_USER
704  *      C. Padding to reach required alignment boundary or at mininum
705  *              one word if debugging is on to be able to detect writes
706  *              before the word boundary.
707  *
708  *      Padding is done using 0x5a (POISON_INUSE)
709  *
710  * object + s->size
711  *      Nothing is used beyond s->size.
712  *
713  * If slabcaches are merged then the object_size and inuse boundaries are mostly
714  * ignored. And therefore no slab options that rely on these boundaries
715  * may be used with merged slabcaches.
716  */
717
718 static int check_pad_bytes(struct kmem_cache *s, struct page *page, u8 *p)
719 {
720         unsigned long off = s->inuse;   /* The end of info */
721
722         if (s->offset)
723                 /* Freepointer is placed after the object. */
724                 off += sizeof(void *);
725
726         if (s->flags & SLAB_STORE_USER)
727                 /* We also have user information there */
728                 off += 2 * sizeof(struct track);
729
730         if (s->size == off)
731                 return 1;
732
733         return check_bytes_and_report(s, page, p, "Object padding",
734                                 p + off, POISON_INUSE, s->size - off);
735 }
736
737 /* Check the pad bytes at the end of a slab page */
738 static int slab_pad_check(struct kmem_cache *s, struct page *page)
739 {
740         u8 *start;
741         u8 *fault;
742         u8 *end;
743         int length;
744         int remainder;
745
746         if (!(s->flags & SLAB_POISON))
747                 return 1;
748
749         start = page_address(page);
750         length = (PAGE_SIZE << compound_order(page)) - s->reserved;
751         end = start + length;
752         remainder = length % s->size;
753         if (!remainder)
754                 return 1;
755
756         fault = memchr_inv(end - remainder, POISON_INUSE, remainder);
757         if (!fault)
758                 return 1;
759         while (end > fault && end[-1] == POISON_INUSE)
760                 end--;
761
762         slab_err(s, page, "Padding overwritten. 0x%p-0x%p", fault, end - 1);
763         print_section("Padding ", end - remainder, remainder);
764
765         restore_bytes(s, "slab padding", POISON_INUSE, end - remainder, end);
766         return 0;
767 }
768
769 static int check_object(struct kmem_cache *s, struct page *page,
770                                         void *object, u8 val)
771 {
772         u8 *p = object;
773         u8 *endobject = object + s->object_size;
774
775         if (s->flags & SLAB_RED_ZONE) {
776                 if (!check_bytes_and_report(s, page, object, "Redzone",
777                         endobject, val, s->inuse - s->object_size))
778                         return 0;
779         } else {
780                 if ((s->flags & SLAB_POISON) && s->object_size < s->inuse) {
781                         check_bytes_and_report(s, page, p, "Alignment padding",
782                                 endobject, POISON_INUSE, s->inuse - s->object_size);
783                 }
784         }
785
786         if (s->flags & SLAB_POISON) {
787                 if (val != SLUB_RED_ACTIVE && (s->flags & __OBJECT_POISON) &&
788                         (!check_bytes_and_report(s, page, p, "Poison", p,
789                                         POISON_FREE, s->object_size - 1) ||
790                          !check_bytes_and_report(s, page, p, "Poison",
791                                 p + s->object_size - 1, POISON_END, 1)))
792                         return 0;
793                 /*
794                  * check_pad_bytes cleans up on its own.
795                  */
796                 check_pad_bytes(s, page, p);
797         }
798
799         if (!s->offset && val == SLUB_RED_ACTIVE)
800                 /*
801                  * Object and freepointer overlap. Cannot check
802                  * freepointer while object is allocated.
803                  */
804                 return 1;
805
806         /* Check free pointer validity */
807         if (!check_valid_pointer(s, page, get_freepointer(s, p))) {
808                 object_err(s, page, p, "Freepointer corrupt");
809                 /*
810                  * No choice but to zap it and thus lose the remainder
811                  * of the free objects in this slab. May cause
812                  * another error because the object count is now wrong.
813                  */
814                 set_freepointer(s, p, NULL);
815                 return 0;
816         }
817         return 1;
818 }
819
820 static int check_slab(struct kmem_cache *s, struct page *page)
821 {
822         int maxobj;
823
824         VM_BUG_ON(!irqs_disabled());
825
826         if (!PageSlab(page)) {
827                 slab_err(s, page, "Not a valid slab page");
828                 return 0;
829         }
830
831         maxobj = order_objects(compound_order(page), s->size, s->reserved);
832         if (page->objects > maxobj) {
833                 slab_err(s, page, "objects %u > max %u",
834                         s->name, page->objects, maxobj);
835                 return 0;
836         }
837         if (page->inuse > page->objects) {
838                 slab_err(s, page, "inuse %u > max %u",
839                         s->name, page->inuse, page->objects);
840                 return 0;
841         }
842         /* Slab_pad_check fixes things up after itself */
843         slab_pad_check(s, page);
844         return 1;
845 }
846
847 /*
848  * Determine if a certain object on a page is on the freelist. Must hold the
849  * slab lock to guarantee that the chains are in a consistent state.
850  */
851 static int on_freelist(struct kmem_cache *s, struct page *page, void *search)
852 {
853         int nr = 0;
854         void *fp;
855         void *object = NULL;
856         unsigned long max_objects;
857
858         fp = page->freelist;
859         while (fp && nr <= page->objects) {
860                 if (fp == search)
861                         return 1;
862                 if (!check_valid_pointer(s, page, fp)) {
863                         if (object) {
864                                 object_err(s, page, object,
865                                         "Freechain corrupt");
866                                 set_freepointer(s, object, NULL);
867                                 break;
868                         } else {
869                                 slab_err(s, page, "Freepointer corrupt");
870                                 page->freelist = NULL;
871                                 page->inuse = page->objects;
872                                 slab_fix(s, "Freelist cleared");
873                                 return 0;
874                         }
875                         break;
876                 }
877                 object = fp;
878                 fp = get_freepointer(s, object);
879                 nr++;
880         }
881
882         max_objects = order_objects(compound_order(page), s->size, s->reserved);
883         if (max_objects > MAX_OBJS_PER_PAGE)
884                 max_objects = MAX_OBJS_PER_PAGE;
885
886         if (page->objects != max_objects) {
887                 slab_err(s, page, "Wrong number of objects. Found %d but "
888                         "should be %d", page->objects, max_objects);
889                 page->objects = max_objects;
890                 slab_fix(s, "Number of objects adjusted.");
891         }
892         if (page->inuse != page->objects - nr) {
893                 slab_err(s, page, "Wrong object count. Counter is %d but "
894                         "counted were %d", page->inuse, page->objects - nr);
895                 page->inuse = page->objects - nr;
896                 slab_fix(s, "Object count adjusted.");
897         }
898         return search == NULL;
899 }
900
901 static void trace(struct kmem_cache *s, struct page *page, void *object,
902                                                                 int alloc)
903 {
904         if (s->flags & SLAB_TRACE) {
905                 printk(KERN_INFO "TRACE %s %s 0x%p inuse=%d fp=0x%p\n",
906                         s->name,
907                         alloc ? "alloc" : "free",
908                         object, page->inuse,
909                         page->freelist);
910
911                 if (!alloc)
912                         print_section("Object ", (void *)object, s->object_size);
913
914                 dump_stack();
915         }
916 }
917
918 /*
919  * Hooks for other subsystems that check memory allocations. In a typical
920  * production configuration these hooks all should produce no code at all.
921  */
922 static inline int slab_pre_alloc_hook(struct kmem_cache *s, gfp_t flags)
923 {
924         flags &= gfp_allowed_mask;
925         lockdep_trace_alloc(flags);
926         might_sleep_if(flags & __GFP_WAIT);
927
928         return should_failslab(s->object_size, flags, s->flags);
929 }
930
931 static inline void slab_post_alloc_hook(struct kmem_cache *s, gfp_t flags, void *object)
932 {
933         flags &= gfp_allowed_mask;
934         kmemcheck_slab_alloc(s, flags, object, slab_ksize(s));
935         kmemleak_alloc_recursive(object, s->object_size, 1, s->flags, flags);
936 }
937
938 static inline void slab_free_hook(struct kmem_cache *s, void *x)
939 {
940         kmemleak_free_recursive(x, s->flags);
941
942         /*
943          * Trouble is that we may no longer disable interupts in the fast path
944          * So in order to make the debug calls that expect irqs to be
945          * disabled we need to disable interrupts temporarily.
946          */
947 #if defined(CONFIG_KMEMCHECK) || defined(CONFIG_LOCKDEP)
948         {
949                 unsigned long flags;
950
951                 local_irq_save(flags);
952                 kmemcheck_slab_free(s, x, s->object_size);
953                 debug_check_no_locks_freed(x, s->object_size);
954                 local_irq_restore(flags);
955         }
956 #endif
957         if (!(s->flags & SLAB_DEBUG_OBJECTS))
958                 debug_check_no_obj_freed(x, s->object_size);
959 }
960
961 /*
962  * Tracking of fully allocated slabs for debugging purposes.
963  *
964  * list_lock must be held.
965  */
966 static void add_full(struct kmem_cache *s,
967         struct kmem_cache_node *n, struct page *page)
968 {
969         if (!(s->flags & SLAB_STORE_USER))
970                 return;
971
972         list_add(&page->lru, &n->full);
973 }
974
975 /*
976  * list_lock must be held.
977  */
978 static void remove_full(struct kmem_cache *s, struct page *page)
979 {
980         if (!(s->flags & SLAB_STORE_USER))
981                 return;
982
983         list_del(&page->lru);
984 }
985
986 /* Tracking of the number of slabs for debugging purposes */
987 static inline unsigned long slabs_node(struct kmem_cache *s, int node)
988 {
989         struct kmem_cache_node *n = get_node(s, node);
990
991         return atomic_long_read(&n->nr_slabs);
992 }
993
994 static inline unsigned long node_nr_slabs(struct kmem_cache_node *n)
995 {
996         return atomic_long_read(&n->nr_slabs);
997 }
998
999 static inline void inc_slabs_node(struct kmem_cache *s, int node, int objects)
1000 {
1001         struct kmem_cache_node *n = get_node(s, node);
1002
1003         /*
1004          * May be called early in order to allocate a slab for the
1005          * kmem_cache_node structure. Solve the chicken-egg
1006          * dilemma by deferring the increment of the count during
1007          * bootstrap (see early_kmem_cache_node_alloc).
1008          */
1009         if (n) {
1010                 atomic_long_inc(&n->nr_slabs);
1011                 atomic_long_add(objects, &n->total_objects);
1012         }
1013 }
1014 static inline void dec_slabs_node(struct kmem_cache *s, int node, int objects)
1015 {
1016         struct kmem_cache_node *n = get_node(s, node);
1017
1018         atomic_long_dec(&n->nr_slabs);
1019         atomic_long_sub(objects, &n->total_objects);
1020 }
1021
1022 /* Object debug checks for alloc/free paths */
1023 static void setup_object_debug(struct kmem_cache *s, struct page *page,
1024                                                                 void *object)
1025 {
1026         if (!(s->flags & (SLAB_STORE_USER|SLAB_RED_ZONE|__OBJECT_POISON)))
1027                 return;
1028
1029         init_object(s, object, SLUB_RED_INACTIVE);
1030         init_tracking(s, object);
1031 }
1032
1033 static noinline int alloc_debug_processing(struct kmem_cache *s, struct page *page,
1034                                         void *object, unsigned long addr)
1035 {
1036         if (!check_slab(s, page))
1037                 goto bad;
1038
1039         if (!check_valid_pointer(s, page, object)) {
1040                 object_err(s, page, object, "Freelist Pointer check fails");
1041                 goto bad;
1042         }
1043
1044         if (!check_object(s, page, object, SLUB_RED_INACTIVE))
1045                 goto bad;
1046
1047         /* Success perform special debug activities for allocs */
1048         if (s->flags & SLAB_STORE_USER)
1049                 set_track(s, object, TRACK_ALLOC, addr);
1050         trace(s, page, object, 1);
1051         init_object(s, object, SLUB_RED_ACTIVE);
1052         return 1;
1053
1054 bad:
1055         if (PageSlab(page)) {
1056                 /*
1057                  * If this is a slab page then lets do the best we can
1058                  * to avoid issues in the future. Marking all objects
1059                  * as used avoids touching the remaining objects.
1060                  */
1061                 slab_fix(s, "Marking all objects used");
1062                 page->inuse = page->objects;
1063                 page->freelist = NULL;
1064         }
1065         return 0;
1066 }
1067
1068 static noinline struct kmem_cache_node *free_debug_processing(
1069         struct kmem_cache *s, struct page *page, void *object,
1070         unsigned long addr, unsigned long *flags)
1071 {
1072         struct kmem_cache_node *n = get_node(s, page_to_nid(page));
1073
1074         spin_lock_irqsave(&n->list_lock, *flags);
1075         slab_lock(page);
1076
1077         if (!check_slab(s, page))
1078                 goto fail;
1079
1080         if (!check_valid_pointer(s, page, object)) {
1081                 slab_err(s, page, "Invalid object pointer 0x%p", object);
1082                 goto fail;
1083         }
1084
1085         if (on_freelist(s, page, object)) {
1086                 object_err(s, page, object, "Object already free");
1087                 goto fail;
1088         }
1089
1090         if (!check_object(s, page, object, SLUB_RED_ACTIVE))
1091                 goto out;
1092
1093         if (unlikely(s != page->slab_cache)) {
1094                 if (!PageSlab(page)) {
1095                         slab_err(s, page, "Attempt to free object(0x%p) "
1096                                 "outside of slab", object);
1097                 } else if (!page->slab_cache) {
1098                         printk(KERN_ERR
1099                                 "SLUB <none>: no slab for object 0x%p.\n",
1100                                                 object);
1101                         dump_stack();
1102                 } else
1103                         object_err(s, page, object,
1104                                         "page slab pointer corrupt.");
1105                 goto fail;
1106         }
1107
1108         if (s->flags & SLAB_STORE_USER)
1109                 set_track(s, object, TRACK_FREE, addr);
1110         trace(s, page, object, 0);
1111         init_object(s, object, SLUB_RED_INACTIVE);
1112 out:
1113         slab_unlock(page);
1114         /*
1115          * Keep node_lock to preserve integrity
1116          * until the object is actually freed
1117          */
1118         return n;
1119
1120 fail:
1121         slab_unlock(page);
1122         spin_unlock_irqrestore(&n->list_lock, *flags);
1123         slab_fix(s, "Object at 0x%p not freed", object);
1124         return NULL;
1125 }
1126
1127 static int __init setup_slub_debug(char *str)
1128 {
1129         slub_debug = DEBUG_DEFAULT_FLAGS;
1130         if (*str++ != '=' || !*str)
1131                 /*
1132                  * No options specified. Switch on full debugging.
1133                  */
1134                 goto out;
1135
1136         if (*str == ',')
1137                 /*
1138                  * No options but restriction on slabs. This means full
1139                  * debugging for slabs matching a pattern.
1140                  */
1141                 goto check_slabs;
1142
1143         if (tolower(*str) == 'o') {
1144                 /*
1145                  * Avoid enabling debugging on caches if its minimum order
1146                  * would increase as a result.
1147                  */
1148                 disable_higher_order_debug = 1;
1149                 goto out;
1150         }
1151
1152         slub_debug = 0;
1153         if (*str == '-')
1154                 /*
1155                  * Switch off all debugging measures.
1156                  */
1157                 goto out;
1158
1159         /*
1160          * Determine which debug features should be switched on
1161          */
1162         for (; *str && *str != ','; str++) {
1163                 switch (tolower(*str)) {
1164                 case 'f':
1165                         slub_debug |= SLAB_DEBUG_FREE;
1166                         break;
1167                 case 'z':
1168                         slub_debug |= SLAB_RED_ZONE;
1169                         break;
1170                 case 'p':
1171                         slub_debug |= SLAB_POISON;
1172                         break;
1173                 case 'u':
1174                         slub_debug |= SLAB_STORE_USER;
1175                         break;
1176                 case 't':
1177                         slub_debug |= SLAB_TRACE;
1178                         break;
1179                 case 'a':
1180                         slub_debug |= SLAB_FAILSLAB;
1181                         break;
1182                 default:
1183                         printk(KERN_ERR "slub_debug option '%c' "
1184                                 "unknown. skipped\n", *str);
1185                 }
1186         }
1187
1188 check_slabs:
1189         if (*str == ',')
1190                 slub_debug_slabs = str + 1;
1191 out:
1192         return 1;
1193 }
1194
1195 __setup("slub_debug", setup_slub_debug);
1196
1197 static unsigned long kmem_cache_flags(unsigned long object_size,
1198         unsigned long flags, const char *name,
1199         void (*ctor)(void *))
1200 {
1201         /*
1202          * Enable debugging if selected on the kernel commandline.
1203          */
1204         if (slub_debug && (!slub_debug_slabs ||
1205                 !strncmp(slub_debug_slabs, name, strlen(slub_debug_slabs))))
1206                 flags |= slub_debug;
1207
1208         return flags;
1209 }
1210 #else
1211 static inline void setup_object_debug(struct kmem_cache *s,
1212                         struct page *page, void *object) {}
1213
1214 static inline int alloc_debug_processing(struct kmem_cache *s,
1215         struct page *page, void *object, unsigned long addr) { return 0; }
1216
1217 static inline struct kmem_cache_node *free_debug_processing(
1218         struct kmem_cache *s, struct page *page, void *object,
1219         unsigned long addr, unsigned long *flags) { return NULL; }
1220
1221 static inline int slab_pad_check(struct kmem_cache *s, struct page *page)
1222                         { return 1; }
1223 static inline int check_object(struct kmem_cache *s, struct page *page,
1224                         void *object, u8 val) { return 1; }
1225 static inline void add_full(struct kmem_cache *s, struct kmem_cache_node *n,
1226                                         struct page *page) {}
1227 static inline void remove_full(struct kmem_cache *s, struct page *page) {}
1228 static inline unsigned long kmem_cache_flags(unsigned long object_size,
1229         unsigned long flags, const char *name,
1230         void (*ctor)(void *))
1231 {
1232         return flags;
1233 }
1234 #define slub_debug 0
1235
1236 #define disable_higher_order_debug 0
1237
1238 static inline unsigned long slabs_node(struct kmem_cache *s, int node)
1239                                                         { return 0; }
1240 static inline unsigned long node_nr_slabs(struct kmem_cache_node *n)
1241                                                         { return 0; }
1242 static inline void inc_slabs_node(struct kmem_cache *s, int node,
1243                                                         int objects) {}
1244 static inline void dec_slabs_node(struct kmem_cache *s, int node,
1245                                                         int objects) {}
1246
1247 static inline int slab_pre_alloc_hook(struct kmem_cache *s, gfp_t flags)
1248                                                         { return 0; }
1249
1250 static inline void slab_post_alloc_hook(struct kmem_cache *s, gfp_t flags,
1251                 void *object) {}
1252
1253 static inline void slab_free_hook(struct kmem_cache *s, void *x) {}
1254
1255 #endif /* CONFIG_SLUB_DEBUG */
1256
1257 /*
1258  * Slab allocation and freeing
1259  */
1260 static inline struct page *alloc_slab_page(gfp_t flags, int node,
1261                                         struct kmem_cache_order_objects oo)
1262 {
1263         int order = oo_order(oo);
1264
1265         flags |= __GFP_NOTRACK;
1266
1267         if (node == NUMA_NO_NODE)
1268                 return alloc_pages(flags, order);
1269         else
1270                 return alloc_pages_exact_node(node, flags, order);
1271 }
1272
1273 static struct page *allocate_slab(struct kmem_cache *s, gfp_t flags, int node)
1274 {
1275         struct page *page;
1276         struct kmem_cache_order_objects oo = s->oo;
1277         gfp_t alloc_gfp;
1278
1279         flags &= gfp_allowed_mask;
1280
1281         if (flags & __GFP_WAIT)
1282                 local_irq_enable();
1283
1284         flags |= s->allocflags;
1285
1286         /*
1287          * Let the initial higher-order allocation fail under memory pressure
1288          * so we fall-back to the minimum order allocation.
1289          */
1290         alloc_gfp = (flags | __GFP_NOWARN | __GFP_NORETRY) & ~__GFP_NOFAIL;
1291
1292         page = alloc_slab_page(alloc_gfp, node, oo);
1293         if (unlikely(!page)) {
1294                 oo = s->min;
1295                 /*
1296                  * Allocation may have failed due to fragmentation.
1297                  * Try a lower order alloc if possible
1298                  */
1299                 page = alloc_slab_page(flags, node, oo);
1300
1301                 if (page)
1302                         stat(s, ORDER_FALLBACK);
1303         }
1304
1305         if (kmemcheck_enabled && page
1306                 && !(s->flags & (SLAB_NOTRACK | DEBUG_DEFAULT_FLAGS))) {
1307                 int pages = 1 << oo_order(oo);
1308
1309                 kmemcheck_alloc_shadow(page, oo_order(oo), flags, node);
1310
1311                 /*
1312                  * Objects from caches that have a constructor don't get
1313                  * cleared when they're allocated, so we need to do it here.
1314                  */
1315                 if (s->ctor)
1316                         kmemcheck_mark_uninitialized_pages(page, pages);
1317                 else
1318                         kmemcheck_mark_unallocated_pages(page, pages);
1319         }
1320
1321         if (flags & __GFP_WAIT)
1322                 local_irq_disable();
1323         if (!page)
1324                 return NULL;
1325
1326         page->objects = oo_objects(oo);
1327         mod_zone_page_state(page_zone(page),
1328                 (s->flags & SLAB_RECLAIM_ACCOUNT) ?
1329                 NR_SLAB_RECLAIMABLE : NR_SLAB_UNRECLAIMABLE,
1330                 1 << oo_order(oo));
1331
1332         return page;
1333 }
1334
1335 static void setup_object(struct kmem_cache *s, struct page *page,
1336                                 void *object)
1337 {
1338         setup_object_debug(s, page, object);
1339         if (unlikely(s->ctor))
1340                 s->ctor(object);
1341 }
1342
1343 static struct page *new_slab(struct kmem_cache *s, gfp_t flags, int node)
1344 {
1345         struct page *page;
1346         void *start;
1347         void *last;
1348         void *p;
1349         int order;
1350
1351         BUG_ON(flags & GFP_SLAB_BUG_MASK);
1352
1353         page = allocate_slab(s,
1354                 flags & (GFP_RECLAIM_MASK | GFP_CONSTRAINT_MASK), node);
1355         if (!page)
1356                 goto out;
1357
1358         order = compound_order(page);
1359         inc_slabs_node(s, page_to_nid(page), page->objects);
1360         memcg_bind_pages(s, order);
1361         page->slab_cache = s;
1362         __SetPageSlab(page);
1363         if (page->pfmemalloc)
1364                 SetPageSlabPfmemalloc(page);
1365
1366         start = page_address(page);
1367
1368         if (unlikely(s->flags & SLAB_POISON))
1369                 memset(start, POISON_INUSE, PAGE_SIZE << order);
1370
1371         last = start;
1372         for_each_object(p, s, start, page->objects) {
1373                 setup_object(s, page, last);
1374                 set_freepointer(s, last, p);
1375                 last = p;
1376         }
1377         setup_object(s, page, last);
1378         set_freepointer(s, last, NULL);
1379
1380         page->freelist = start;
1381         page->inuse = page->objects;
1382         page->frozen = 1;
1383 out:
1384         return page;
1385 }
1386
1387 static void __free_slab(struct kmem_cache *s, struct page *page)
1388 {
1389         int order = compound_order(page);
1390         int pages = 1 << order;
1391
1392         if (kmem_cache_debug(s)) {
1393                 void *p;
1394
1395                 slab_pad_check(s, page);
1396                 for_each_object(p, s, page_address(page),
1397                                                 page->objects)
1398                         check_object(s, page, p, SLUB_RED_INACTIVE);
1399         }
1400
1401         kmemcheck_free_shadow(page, compound_order(page));
1402
1403         mod_zone_page_state(page_zone(page),
1404                 (s->flags & SLAB_RECLAIM_ACCOUNT) ?
1405                 NR_SLAB_RECLAIMABLE : NR_SLAB_UNRECLAIMABLE,
1406                 -pages);
1407
1408         __ClearPageSlabPfmemalloc(page);
1409         __ClearPageSlab(page);
1410
1411         memcg_release_pages(s, order);
1412         page_mapcount_reset(page);
1413         if (current->reclaim_state)
1414                 current->reclaim_state->reclaimed_slab += pages;
1415         __free_memcg_kmem_pages(page, order);
1416 }
1417
1418 #define need_reserve_slab_rcu                                           \
1419         (sizeof(((struct page *)NULL)->lru) < sizeof(struct rcu_head))
1420
1421 static void rcu_free_slab(struct rcu_head *h)
1422 {
1423         struct page *page;
1424
1425         if (need_reserve_slab_rcu)
1426                 page = virt_to_head_page(h);
1427         else
1428                 page = container_of((struct list_head *)h, struct page, lru);
1429
1430         __free_slab(page->slab_cache, page);
1431 }
1432
1433 static void free_slab(struct kmem_cache *s, struct page *page)
1434 {
1435         if (unlikely(s->flags & SLAB_DESTROY_BY_RCU)) {
1436                 struct rcu_head *head;
1437
1438                 if (need_reserve_slab_rcu) {
1439                         int order = compound_order(page);
1440                         int offset = (PAGE_SIZE << order) - s->reserved;
1441
1442                         VM_BUG_ON(s->reserved != sizeof(*head));
1443                         head = page_address(page) + offset;
1444                 } else {
1445                         /*
1446                          * RCU free overloads the RCU head over the LRU
1447                          */
1448                         head = (void *)&page->lru;
1449                 }
1450
1451                 call_rcu(head, rcu_free_slab);
1452         } else
1453                 __free_slab(s, page);
1454 }
1455
1456 static void discard_slab(struct kmem_cache *s, struct page *page)
1457 {
1458         dec_slabs_node(s, page_to_nid(page), page->objects);
1459         free_slab(s, page);
1460 }
1461
1462 /*
1463  * Management of partially allocated slabs.
1464  *
1465  * list_lock must be held.
1466  */
1467 static inline void add_partial(struct kmem_cache_node *n,
1468                                 struct page *page, int tail)
1469 {
1470         n->nr_partial++;
1471         if (tail == DEACTIVATE_TO_TAIL)
1472                 list_add_tail(&page->lru, &n->partial);
1473         else
1474                 list_add(&page->lru, &n->partial);
1475 }
1476
1477 /*
1478  * list_lock must be held.
1479  */
1480 static inline void remove_partial(struct kmem_cache_node *n,
1481                                         struct page *page)
1482 {
1483         list_del(&page->lru);
1484         n->nr_partial--;
1485 }
1486
1487 /*
1488  * Remove slab from the partial list, freeze it and
1489  * return the pointer to the freelist.
1490  *
1491  * Returns a list of objects or NULL if it fails.
1492  *
1493  * Must hold list_lock since we modify the partial list.
1494  */
1495 static inline void *acquire_slab(struct kmem_cache *s,
1496                 struct kmem_cache_node *n, struct page *page,
1497                 int mode)
1498 {
1499         void *freelist;
1500         unsigned long counters;
1501         struct page new;
1502
1503         /*
1504          * Zap the freelist and set the frozen bit.
1505          * The old freelist is the list of objects for the
1506          * per cpu allocation list.
1507          */
1508         freelist = page->freelist;
1509         counters = page->counters;
1510         new.counters = counters;
1511         if (mode) {
1512                 new.inuse = page->objects;
1513                 new.freelist = NULL;
1514         } else {
1515                 new.freelist = freelist;
1516         }
1517
1518         VM_BUG_ON(new.frozen);
1519         new.frozen = 1;
1520
1521         if (!__cmpxchg_double_slab(s, page,
1522                         freelist, counters,
1523                         new.freelist, new.counters,
1524                         "acquire_slab"))
1525                 return NULL;
1526
1527         remove_partial(n, page);
1528         WARN_ON(!freelist);
1529         return freelist;
1530 }
1531
1532 static int put_cpu_partial(struct kmem_cache *s, struct page *page, int drain);
1533 static inline bool pfmemalloc_match(struct page *page, gfp_t gfpflags);
1534
1535 /*
1536  * Try to allocate a partial slab from a specific node.
1537  */
1538 static void *get_partial_node(struct kmem_cache *s, struct kmem_cache_node *n,
1539                                 struct kmem_cache_cpu *c, gfp_t flags)
1540 {
1541         struct page *page, *page2;
1542         void *object = NULL;
1543
1544         /*
1545          * Racy check. If we mistakenly see no partial slabs then we
1546          * just allocate an empty slab. If we mistakenly try to get a
1547          * partial slab and there is none available then get_partials()
1548          * will return NULL.
1549          */
1550         if (!n || !n->nr_partial)
1551                 return NULL;
1552
1553         spin_lock(&n->list_lock);
1554         list_for_each_entry_safe(page, page2, &n->partial, lru) {
1555                 void *t;
1556                 int available;
1557
1558                 if (!pfmemalloc_match(page, flags))
1559                         continue;
1560
1561                 t = acquire_slab(s, n, page, object == NULL);
1562                 if (!t)
1563                         break;
1564
1565                 if (!object) {
1566                         c->page = page;
1567                         stat(s, ALLOC_FROM_PARTIAL);
1568                         object = t;
1569                         available =  page->objects - page->inuse;
1570                 } else {
1571                         available = put_cpu_partial(s, page, 0);
1572                         stat(s, CPU_PARTIAL_NODE);
1573                 }
1574                 if (kmem_cache_debug(s) || available > s->cpu_partial / 2)
1575                         break;
1576
1577         }
1578         spin_unlock(&n->list_lock);
1579         return object;
1580 }
1581
1582 /*
1583  * Get a page from somewhere. Search in increasing NUMA distances.
1584  */
1585 static void *get_any_partial(struct kmem_cache *s, gfp_t flags,
1586                 struct kmem_cache_cpu *c)
1587 {
1588 #ifdef CONFIG_NUMA
1589         struct zonelist *zonelist;
1590         struct zoneref *z;
1591         struct zone *zone;
1592         enum zone_type high_zoneidx = gfp_zone(flags);
1593         void *object;
1594         unsigned int cpuset_mems_cookie;
1595
1596         /*
1597          * The defrag ratio allows a configuration of the tradeoffs between
1598          * inter node defragmentation and node local allocations. A lower
1599          * defrag_ratio increases the tendency to do local allocations
1600          * instead of attempting to obtain partial slabs from other nodes.
1601          *
1602          * If the defrag_ratio is set to 0 then kmalloc() always
1603          * returns node local objects. If the ratio is higher then kmalloc()
1604          * may return off node objects because partial slabs are obtained
1605          * from other nodes and filled up.
1606          *
1607          * If /sys/kernel/slab/xx/defrag_ratio is set to 100 (which makes
1608          * defrag_ratio = 1000) then every (well almost) allocation will
1609          * first attempt to defrag slab caches on other nodes. This means
1610          * scanning over all nodes to look for partial slabs which may be
1611          * expensive if we do it every time we are trying to find a slab
1612          * with available objects.
1613          */
1614         if (!s->remote_node_defrag_ratio ||
1615                         get_cycles() % 1024 > s->remote_node_defrag_ratio)
1616                 return NULL;
1617
1618         do {
1619                 cpuset_mems_cookie = get_mems_allowed();
1620                 zonelist = node_zonelist(slab_node(), flags);
1621                 for_each_zone_zonelist(zone, z, zonelist, high_zoneidx) {
1622                         struct kmem_cache_node *n;
1623
1624                         n = get_node(s, zone_to_nid(zone));
1625
1626                         if (n && cpuset_zone_allowed_hardwall(zone, flags) &&
1627                                         n->nr_partial > s->min_partial) {
1628                                 object = get_partial_node(s, n, c, flags);
1629                                 if (object) {
1630                                         /*
1631                                          * Return the object even if
1632                                          * put_mems_allowed indicated that
1633                                          * the cpuset mems_allowed was
1634                                          * updated in parallel. It's a
1635                                          * harmless race between the alloc
1636                                          * and the cpuset update.
1637                                          */
1638                                         put_mems_allowed(cpuset_mems_cookie);
1639                                         return object;
1640                                 }
1641                         }
1642                 }
1643         } while (!put_mems_allowed(cpuset_mems_cookie));
1644 #endif
1645         return NULL;
1646 }
1647
1648 /*
1649  * Get a partial page, lock it and return it.
1650  */
1651 static void *get_partial(struct kmem_cache *s, gfp_t flags, int node,
1652                 struct kmem_cache_cpu *c)
1653 {
1654         void *object;
1655         int searchnode = (node == NUMA_NO_NODE) ? numa_node_id() : node;
1656
1657         object = get_partial_node(s, get_node(s, searchnode), c, flags);
1658         if (object || node != NUMA_NO_NODE)
1659                 return object;
1660
1661         return get_any_partial(s, flags, c);
1662 }
1663
1664 #ifdef CONFIG_PREEMPT
1665 /*
1666  * Calculate the next globally unique transaction for disambiguiation
1667  * during cmpxchg. The transactions start with the cpu number and are then
1668  * incremented by CONFIG_NR_CPUS.
1669  */
1670 #define TID_STEP  roundup_pow_of_two(CONFIG_NR_CPUS)
1671 #else
1672 /*
1673  * No preemption supported therefore also no need to check for
1674  * different cpus.
1675  */
1676 #define TID_STEP 1
1677 #endif
1678
1679 static inline unsigned long next_tid(unsigned long tid)
1680 {
1681         return tid + TID_STEP;
1682 }
1683
1684 static inline unsigned int tid_to_cpu(unsigned long tid)
1685 {
1686         return tid % TID_STEP;
1687 }
1688
1689 static inline unsigned long tid_to_event(unsigned long tid)
1690 {
1691         return tid / TID_STEP;
1692 }
1693
1694 static inline unsigned int init_tid(int cpu)
1695 {
1696         return cpu;
1697 }
1698
1699 static inline void note_cmpxchg_failure(const char *n,
1700                 const struct kmem_cache *s, unsigned long tid)
1701 {
1702 #ifdef SLUB_DEBUG_CMPXCHG
1703         unsigned long actual_tid = __this_cpu_read(s->cpu_slab->tid);
1704
1705         printk(KERN_INFO "%s %s: cmpxchg redo ", n, s->name);
1706
1707 #ifdef CONFIG_PREEMPT
1708         if (tid_to_cpu(tid) != tid_to_cpu(actual_tid))
1709                 printk("due to cpu change %d -> %d\n",
1710                         tid_to_cpu(tid), tid_to_cpu(actual_tid));
1711         else
1712 #endif
1713         if (tid_to_event(tid) != tid_to_event(actual_tid))
1714                 printk("due to cpu running other code. Event %ld->%ld\n",
1715                         tid_to_event(tid), tid_to_event(actual_tid));
1716         else
1717                 printk("for unknown reason: actual=%lx was=%lx target=%lx\n",
1718                         actual_tid, tid, next_tid(tid));
1719 #endif
1720         stat(s, CMPXCHG_DOUBLE_CPU_FAIL);
1721 }
1722
1723 static void init_kmem_cache_cpus(struct kmem_cache *s)
1724 {
1725         int cpu;
1726
1727         for_each_possible_cpu(cpu)
1728                 per_cpu_ptr(s->cpu_slab, cpu)->tid = init_tid(cpu);
1729 }
1730
1731 /*
1732  * Remove the cpu slab
1733  */
1734 static void deactivate_slab(struct kmem_cache *s, struct page *page, void *freelist)
1735 {
1736         enum slab_modes { M_NONE, M_PARTIAL, M_FULL, M_FREE };
1737         struct kmem_cache_node *n = get_node(s, page_to_nid(page));
1738         int lock = 0;
1739         enum slab_modes l = M_NONE, m = M_NONE;
1740         void *nextfree;
1741         int tail = DEACTIVATE_TO_HEAD;
1742         struct page new;
1743         struct page old;
1744
1745         if (page->freelist) {
1746                 stat(s, DEACTIVATE_REMOTE_FREES);
1747                 tail = DEACTIVATE_TO_TAIL;
1748         }
1749
1750         /*
1751          * Stage one: Free all available per cpu objects back
1752          * to the page freelist while it is still frozen. Leave the
1753          * last one.
1754          *
1755          * There is no need to take the list->lock because the page
1756          * is still frozen.
1757          */
1758         while (freelist && (nextfree = get_freepointer(s, freelist))) {
1759                 void *prior;
1760                 unsigned long counters;
1761
1762                 do {
1763                         prior = page->freelist;
1764                         counters = page->counters;
1765                         set_freepointer(s, freelist, prior);
1766                         new.counters = counters;
1767                         new.inuse--;
1768                         VM_BUG_ON(!new.frozen);
1769
1770                 } while (!__cmpxchg_double_slab(s, page,
1771                         prior, counters,
1772                         freelist, new.counters,
1773                         "drain percpu freelist"));
1774
1775                 freelist = nextfree;
1776         }
1777
1778         /*
1779          * Stage two: Ensure that the page is unfrozen while the
1780          * list presence reflects the actual number of objects
1781          * during unfreeze.
1782          *
1783          * We setup the list membership and then perform a cmpxchg
1784          * with the count. If there is a mismatch then the page
1785          * is not unfrozen but the page is on the wrong list.
1786          *
1787          * Then we restart the process which may have to remove
1788          * the page from the list that we just put it on again
1789          * because the number of objects in the slab may have
1790          * changed.
1791          */
1792 redo:
1793
1794         old.freelist = page->freelist;
1795         old.counters = page->counters;
1796         VM_BUG_ON(!old.frozen);
1797
1798         /* Determine target state of the slab */
1799         new.counters = old.counters;
1800         if (freelist) {
1801                 new.inuse--;
1802                 set_freepointer(s, freelist, old.freelist);
1803                 new.freelist = freelist;
1804         } else
1805                 new.freelist = old.freelist;
1806
1807         new.frozen = 0;
1808
1809         if (!new.inuse && n->nr_partial > s->min_partial)
1810                 m = M_FREE;
1811         else if (new.freelist) {
1812                 m = M_PARTIAL;
1813                 if (!lock) {
1814                         lock = 1;
1815                         /*
1816                          * Taking the spinlock removes the possiblity
1817                          * that acquire_slab() will see a slab page that
1818                          * is frozen
1819                          */
1820                         spin_lock(&n->list_lock);
1821                 }
1822         } else {
1823                 m = M_FULL;
1824                 if (kmem_cache_debug(s) && !lock) {
1825                         lock = 1;
1826                         /*
1827                          * This also ensures that the scanning of full
1828                          * slabs from diagnostic functions will not see
1829                          * any frozen slabs.
1830                          */
1831                         spin_lock(&n->list_lock);
1832                 }
1833         }
1834
1835         if (l != m) {
1836
1837                 if (l == M_PARTIAL)
1838
1839                         remove_partial(n, page);
1840
1841                 else if (l == M_FULL)
1842
1843                         remove_full(s, page);
1844
1845                 if (m == M_PARTIAL) {
1846
1847                         add_partial(n, page, tail);
1848                         stat(s, tail);
1849
1850                 } else if (m == M_FULL) {
1851
1852                         stat(s, DEACTIVATE_FULL);
1853                         add_full(s, n, page);
1854
1855                 }
1856         }
1857
1858         l = m;
1859         if (!__cmpxchg_double_slab(s, page,
1860                                 old.freelist, old.counters,
1861                                 new.freelist, new.counters,
1862                                 "unfreezing slab"))
1863                 goto redo;
1864
1865         if (lock)
1866                 spin_unlock(&n->list_lock);
1867
1868         if (m == M_FREE) {
1869                 stat(s, DEACTIVATE_EMPTY);
1870                 discard_slab(s, page);
1871                 stat(s, FREE_SLAB);
1872         }
1873 }
1874
1875 /*
1876  * Unfreeze all the cpu partial slabs.
1877  *
1878  * This function must be called with interrupts disabled
1879  * for the cpu using c (or some other guarantee must be there
1880  * to guarantee no concurrent accesses).
1881  */
1882 static void unfreeze_partials(struct kmem_cache *s,
1883                 struct kmem_cache_cpu *c)
1884 {
1885         struct kmem_cache_node *n = NULL, *n2 = NULL;
1886         struct page *page, *discard_page = NULL;
1887
1888         while ((page = c->partial)) {
1889                 struct page new;
1890                 struct page old;
1891
1892                 c->partial = page->next;
1893
1894                 n2 = get_node(s, page_to_nid(page));
1895                 if (n != n2) {
1896                         if (n)
1897                                 spin_unlock(&n->list_lock);
1898
1899                         n = n2;
1900                         spin_lock(&n->list_lock);
1901                 }
1902
1903                 do {
1904
1905                         old.freelist = page->freelist;
1906                         old.counters = page->counters;
1907                         VM_BUG_ON(!old.frozen);
1908
1909                         new.counters = old.counters;
1910                         new.freelist = old.freelist;
1911
1912                         new.frozen = 0;
1913
1914                 } while (!__cmpxchg_double_slab(s, page,
1915                                 old.freelist, old.counters,
1916                                 new.freelist, new.counters,
1917                                 "unfreezing slab"));
1918
1919                 if (unlikely(!new.inuse && n->nr_partial > s->min_partial)) {
1920                         page->next = discard_page;
1921                         discard_page = page;
1922                 } else {
1923                         add_partial(n, page, DEACTIVATE_TO_TAIL);
1924                         stat(s, FREE_ADD_PARTIAL);
1925                 }
1926         }
1927
1928         if (n)
1929                 spin_unlock(&n->list_lock);
1930
1931         while (discard_page) {
1932                 page = discard_page;
1933                 discard_page = discard_page->next;
1934
1935                 stat(s, DEACTIVATE_EMPTY);
1936                 discard_slab(s, page);
1937                 stat(s, FREE_SLAB);
1938         }
1939 }
1940
1941 /*
1942  * Put a page that was just frozen (in __slab_free) into a partial page
1943  * slot if available. This is done without interrupts disabled and without
1944  * preemption disabled. The cmpxchg is racy and may put the partial page
1945  * onto a random cpus partial slot.
1946  *
1947  * If we did not find a slot then simply move all the partials to the
1948  * per node partial list.
1949  */
1950 static int put_cpu_partial(struct kmem_cache *s, struct page *page, int drain)
1951 {
1952         struct page *oldpage;
1953         int pages;
1954         int pobjects;
1955
1956         do {
1957                 pages = 0;
1958                 pobjects = 0;
1959                 oldpage = this_cpu_read(s->cpu_slab->partial);
1960
1961                 if (oldpage) {
1962                         pobjects = oldpage->pobjects;
1963                         pages = oldpage->pages;
1964                         if (drain && pobjects > s->cpu_partial) {
1965                                 unsigned long flags;
1966                                 /*
1967                                  * partial array is full. Move the existing
1968                                  * set to the per node partial list.
1969                                  */
1970                                 local_irq_save(flags);
1971                                 unfreeze_partials(s, this_cpu_ptr(s->cpu_slab));
1972                                 local_irq_restore(flags);
1973                                 oldpage = NULL;
1974                                 pobjects = 0;
1975                                 pages = 0;
1976                                 stat(s, CPU_PARTIAL_DRAIN);
1977                         }
1978                 }
1979
1980                 pages++;
1981                 pobjects += page->objects - page->inuse;
1982
1983                 page->pages = pages;
1984                 page->pobjects = pobjects;
1985                 page->next = oldpage;
1986
1987         } while (this_cpu_cmpxchg(s->cpu_slab->partial, oldpage, page) != oldpage);
1988         return pobjects;
1989 }
1990
1991 static inline void flush_slab(struct kmem_cache *s, struct kmem_cache_cpu *c)
1992 {
1993         stat(s, CPUSLAB_FLUSH);
1994         deactivate_slab(s, c->page, c->freelist);
1995
1996         c->tid = next_tid(c->tid);
1997         c->page = NULL;
1998         c->freelist = NULL;
1999 }
2000
2001 /*
2002  * Flush cpu slab.
2003  *
2004  * Called from IPI handler with interrupts disabled.
2005  */
2006 static inline void __flush_cpu_slab(struct kmem_cache *s, int cpu)
2007 {
2008         struct kmem_cache_cpu *c = per_cpu_ptr(s->cpu_slab, cpu);
2009
2010         if (likely(c)) {
2011                 if (c->page)
2012                         flush_slab(s, c);
2013
2014                 unfreeze_partials(s, c);
2015         }
2016 }
2017
2018 static void flush_cpu_slab(void *d)
2019 {
2020         struct kmem_cache *s = d;
2021
2022         __flush_cpu_slab(s, smp_processor_id());
2023 }
2024
2025 static bool has_cpu_slab(int cpu, void *info)
2026 {
2027         struct kmem_cache *s = info;
2028         struct kmem_cache_cpu *c = per_cpu_ptr(s->cpu_slab, cpu);
2029
2030         return c->page || c->partial;
2031 }
2032
2033 static void flush_all(struct kmem_cache *s)
2034 {
2035         on_each_cpu_cond(has_cpu_slab, flush_cpu_slab, s, 1, GFP_ATOMIC);
2036 }
2037
2038 /*
2039  * Check if the objects in a per cpu structure fit numa
2040  * locality expectations.
2041  */
2042 static inline int node_match(struct page *page, int node)
2043 {
2044 #ifdef CONFIG_NUMA
2045         if (node != NUMA_NO_NODE && page_to_nid(page) != node)
2046                 return 0;
2047 #endif
2048         return 1;
2049 }
2050
2051 static int count_free(struct page *page)
2052 {
2053         return page->objects - page->inuse;
2054 }
2055
2056 static unsigned long count_partial(struct kmem_cache_node *n,
2057                                         int (*get_count)(struct page *))
2058 {
2059         unsigned long flags;
2060         unsigned long x = 0;
2061         struct page *page;
2062
2063         spin_lock_irqsave(&n->list_lock, flags);
2064         list_for_each_entry(page, &n->partial, lru)
2065                 x += get_count(page);
2066         spin_unlock_irqrestore(&n->list_lock, flags);
2067         return x;
2068 }
2069
2070 static inline unsigned long node_nr_objs(struct kmem_cache_node *n)
2071 {
2072 #ifdef CONFIG_SLUB_DEBUG
2073         return atomic_long_read(&n->total_objects);
2074 #else
2075         return 0;
2076 #endif
2077 }
2078
2079 static noinline void
2080 slab_out_of_memory(struct kmem_cache *s, gfp_t gfpflags, int nid)
2081 {
2082         int node;
2083
2084         printk(KERN_WARNING
2085                 "SLUB: Unable to allocate memory on node %d (gfp=0x%x)\n",
2086                 nid, gfpflags);
2087         printk(KERN_WARNING "  cache: %s, object size: %d, buffer size: %d, "
2088                 "default order: %d, min order: %d\n", s->name, s->object_size,
2089                 s->size, oo_order(s->oo), oo_order(s->min));
2090
2091         if (oo_order(s->min) > get_order(s->object_size))
2092                 printk(KERN_WARNING "  %s debugging increased min order, use "
2093                        "slub_debug=O to disable.\n", s->name);
2094
2095         for_each_online_node(node) {
2096                 struct kmem_cache_node *n = get_node(s, node);
2097                 unsigned long nr_slabs;
2098                 unsigned long nr_objs;
2099                 unsigned long nr_free;
2100
2101                 if (!n)
2102                         continue;
2103
2104                 nr_free  = count_partial(n, count_free);
2105                 nr_slabs = node_nr_slabs(n);
2106                 nr_objs  = node_nr_objs(n);
2107
2108                 printk(KERN_WARNING
2109                         "  node %d: slabs: %ld, objs: %ld, free: %ld\n",
2110                         node, nr_slabs, nr_objs, nr_free);
2111         }
2112 }
2113
2114 static inline void *new_slab_objects(struct kmem_cache *s, gfp_t flags,
2115                         int node, struct kmem_cache_cpu **pc)
2116 {
2117         void *freelist;
2118         struct kmem_cache_cpu *c = *pc;
2119         struct page *page;
2120
2121         freelist = get_partial(s, flags, node, c);
2122
2123         if (freelist)
2124                 return freelist;
2125
2126         page = new_slab(s, flags, node);
2127         if (page) {
2128                 c = __this_cpu_ptr(s->cpu_slab);
2129                 if (c->page)
2130                         flush_slab(s, c);
2131
2132                 /*
2133                  * No other reference to the page yet so we can
2134                  * muck around with it freely without cmpxchg
2135                  */
2136                 freelist = page->freelist;
2137                 page->freelist = NULL;
2138
2139                 stat(s, ALLOC_SLAB);
2140                 c->page = page;
2141                 *pc = c;
2142         } else
2143                 freelist = NULL;
2144
2145         return freelist;
2146 }
2147
2148 static inline bool pfmemalloc_match(struct page *page, gfp_t gfpflags)
2149 {
2150         if (unlikely(PageSlabPfmemalloc(page)))
2151                 return gfp_pfmemalloc_allowed(gfpflags);
2152
2153         return true;
2154 }
2155
2156 /*
2157  * Check the page->freelist of a page and either transfer the freelist to the per cpu freelist
2158  * or deactivate the page.
2159  *
2160  * The page is still frozen if the return value is not NULL.
2161  *
2162  * If this function returns NULL then the page has been unfrozen.
2163  *
2164  * This function must be called with interrupt disabled.
2165  */
2166 static inline void *get_freelist(struct kmem_cache *s, struct page *page)
2167 {
2168         struct page new;
2169         unsigned long counters;
2170         void *freelist;
2171
2172         do {
2173                 freelist = page->freelist;
2174                 counters = page->counters;
2175
2176                 new.counters = counters;
2177                 VM_BUG_ON(!new.frozen);
2178
2179                 new.inuse = page->objects;
2180                 new.frozen = freelist != NULL;
2181
2182         } while (!__cmpxchg_double_slab(s, page,
2183                 freelist, counters,
2184                 NULL, new.counters,
2185                 "get_freelist"));
2186
2187         return freelist;
2188 }
2189
2190 /*
2191  * Slow path. The lockless freelist is empty or we need to perform
2192  * debugging duties.
2193  *
2194  * Processing is still very fast if new objects have been freed to the
2195  * regular freelist. In that case we simply take over the regular freelist
2196  * as the lockless freelist and zap the regular freelist.
2197  *
2198  * If that is not working then we fall back to the partial lists. We take the
2199  * first element of the freelist as the object to allocate now and move the
2200  * rest of the freelist to the lockless freelist.
2201  *
2202  * And if we were unable to get a new slab from the partial slab lists then
2203  * we need to allocate a new slab. This is the slowest path since it involves
2204  * a call to the page allocator and the setup of a new slab.
2205  */
2206 static void *__slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
2207                           unsigned long addr, struct kmem_cache_cpu *c)
2208 {
2209         void *freelist;
2210         struct page *page;
2211         unsigned long flags;
2212
2213         local_irq_save(flags);
2214 #ifdef CONFIG_PREEMPT
2215         /*
2216          * We may have been preempted and rescheduled on a different
2217          * cpu before disabling interrupts. Need to reload cpu area
2218          * pointer.
2219          */
2220         c = this_cpu_ptr(s->cpu_slab);
2221 #endif
2222
2223         page = c->page;
2224         if (!page)
2225                 goto new_slab;
2226 redo:
2227
2228         if (unlikely(!node_match(page, node))) {
2229                 stat(s, ALLOC_NODE_MISMATCH);
2230                 deactivate_slab(s, page, c->freelist);
2231                 c->page = NULL;
2232                 c->freelist = NULL;
2233                 goto new_slab;
2234         }
2235
2236         /*
2237          * By rights, we should be searching for a slab page that was
2238          * PFMEMALLOC but right now, we are losing the pfmemalloc
2239          * information when the page leaves the per-cpu allocator
2240          */
2241         if (unlikely(!pfmemalloc_match(page, gfpflags))) {
2242                 deactivate_slab(s, page, c->freelist);
2243                 c->page = NULL;
2244                 c->freelist = NULL;
2245                 goto new_slab;
2246         }
2247
2248         /* must check again c->freelist in case of cpu migration or IRQ */
2249         freelist = c->freelist;
2250         if (freelist)
2251                 goto load_freelist;
2252
2253         stat(s, ALLOC_SLOWPATH);
2254
2255         freelist = get_freelist(s, page);
2256
2257         if (!freelist) {
2258                 c->page = NULL;
2259                 stat(s, DEACTIVATE_BYPASS);
2260                 goto new_slab;
2261         }
2262
2263         stat(s, ALLOC_REFILL);
2264
2265 load_freelist:
2266         /*
2267          * freelist is pointing to the list of objects to be used.
2268          * page is pointing to the page from which the objects are obtained.
2269          * That page must be frozen for per cpu allocations to work.
2270          */
2271         VM_BUG_ON(!c->page->frozen);
2272         c->freelist = get_freepointer(s, freelist);
2273         c->tid = next_tid(c->tid);
2274         local_irq_restore(flags);
2275         return freelist;
2276
2277 new_slab:
2278
2279         if (c->partial) {
2280                 page = c->page = c->partial;
2281                 c->partial = page->next;
2282                 stat(s, CPU_PARTIAL_ALLOC);
2283                 c->freelist = NULL;
2284                 goto redo;
2285         }
2286
2287         freelist = new_slab_objects(s, gfpflags, node, &c);
2288
2289         if (unlikely(!freelist)) {
2290                 if (!(gfpflags & __GFP_NOWARN) && printk_ratelimit())
2291                         slab_out_of_memory(s, gfpflags, node);
2292
2293                 local_irq_restore(flags);
2294                 return NULL;
2295         }
2296
2297         page = c->page;
2298         if (likely(!kmem_cache_debug(s) && pfmemalloc_match(page, gfpflags)))
2299                 goto load_freelist;
2300
2301         /* Only entered in the debug case */
2302         if (kmem_cache_debug(s) && !alloc_debug_processing(s, page, freelist, addr))
2303                 goto new_slab;  /* Slab failed checks. Next slab needed */
2304
2305         deactivate_slab(s, page, get_freepointer(s, freelist));
2306         c->page = NULL;
2307         c->freelist = NULL;
2308         local_irq_restore(flags);
2309         return freelist;
2310 }
2311
2312 /*
2313  * Inlined fastpath so that allocation functions (kmalloc, kmem_cache_alloc)
2314  * have the fastpath folded into their functions. So no function call
2315  * overhead for requests that can be satisfied on the fastpath.
2316  *
2317  * The fastpath works by first checking if the lockless freelist can be used.
2318  * If not then __slab_alloc is called for slow processing.
2319  *
2320  * Otherwise we can simply pick the next object from the lockless free list.
2321  */
2322 static __always_inline void *slab_alloc_node(struct kmem_cache *s,
2323                 gfp_t gfpflags, int node, unsigned long addr)
2324 {
2325         void **object;
2326         struct kmem_cache_cpu *c;
2327         struct page *page;
2328         unsigned long tid;
2329
2330         if (slab_pre_alloc_hook(s, gfpflags))
2331                 return NULL;
2332
2333         s = memcg_kmem_get_cache(s, gfpflags);
2334 redo:
2335
2336         /*
2337          * Must read kmem_cache cpu data via this cpu ptr. Preemption is
2338          * enabled. We may switch back and forth between cpus while
2339          * reading from one cpu area. That does not matter as long
2340          * as we end up on the original cpu again when doing the cmpxchg.
2341          */
2342         c = __this_cpu_ptr(s->cpu_slab);
2343
2344         /*
2345          * The transaction ids are globally unique per cpu and per operation on
2346          * a per cpu queue. Thus they can be guarantee that the cmpxchg_double
2347          * occurs on the right processor and that there was no operation on the
2348          * linked list in between.
2349          */
2350         tid = c->tid;
2351         barrier();
2352
2353         object = c->freelist;
2354         page = c->page;
2355         if (unlikely(!object || !node_match(page, node)))
2356                 object = __slab_alloc(s, gfpflags, node, addr, c);
2357
2358         else {
2359                 void *next_object = get_freepointer_safe(s, object);
2360
2361                 /*
2362                  * The cmpxchg will only match if there was no additional
2363                  * operation and if we are on the right processor.
2364                  *
2365                  * The cmpxchg does the following atomically (without lock semantics!)
2366                  * 1. Relocate first pointer to the current per cpu area.
2367                  * 2. Verify that tid and freelist have not been changed
2368                  * 3. If they were not changed replace tid and freelist
2369                  *
2370                  * Since this is without lock semantics the protection is only against
2371                  * code executing on this cpu *not* from access by other cpus.
2372                  */
2373                 if (unlikely(!this_cpu_cmpxchg_double(
2374                                 s->cpu_slab->freelist, s->cpu_slab->tid,
2375                                 object, tid,
2376                                 next_object, next_tid(tid)))) {
2377
2378                         note_cmpxchg_failure("slab_alloc", s, tid);
2379                         goto redo;
2380                 }
2381                 prefetch_freepointer(s, next_object);
2382                 stat(s, ALLOC_FASTPATH);
2383         }
2384
2385         if (unlikely(gfpflags & __GFP_ZERO) && object)
2386                 memset(object, 0, s->object_size);
2387
2388         slab_post_alloc_hook(s, gfpflags, object);
2389
2390         return object;
2391 }
2392
2393 static __always_inline void *slab_alloc(struct kmem_cache *s,
2394                 gfp_t gfpflags, unsigned long addr)
2395 {
2396         return slab_alloc_node(s, gfpflags, NUMA_NO_NODE, addr);
2397 }
2398
2399 void *kmem_cache_alloc(struct kmem_cache *s, gfp_t gfpflags)
2400 {
2401         void *ret = slab_alloc(s, gfpflags, _RET_IP_);
2402
2403         trace_kmem_cache_alloc(_RET_IP_, ret, s->object_size, s->size, gfpflags);
2404
2405         return ret;
2406 }
2407 EXPORT_SYMBOL(kmem_cache_alloc);
2408
2409 #ifdef CONFIG_TRACING
2410 void *kmem_cache_alloc_trace(struct kmem_cache *s, gfp_t gfpflags, size_t size)
2411 {
2412         void *ret = slab_alloc(s, gfpflags, _RET_IP_);
2413         trace_kmalloc(_RET_IP_, ret, size, s->size, gfpflags);
2414         return ret;
2415 }
2416 EXPORT_SYMBOL(kmem_cache_alloc_trace);
2417
2418 void *kmalloc_order_trace(size_t size, gfp_t flags, unsigned int order)
2419 {
2420         void *ret = kmalloc_order(size, flags, order);
2421         trace_kmalloc(_RET_IP_, ret, size, PAGE_SIZE << order, flags);
2422         return ret;
2423 }
2424 EXPORT_SYMBOL(kmalloc_order_trace);
2425 #endif
2426
2427 #ifdef CONFIG_NUMA
2428 void *kmem_cache_alloc_node(struct kmem_cache *s, gfp_t gfpflags, int node)
2429 {
2430         void *ret = slab_alloc_node(s, gfpflags, node, _RET_IP_);
2431
2432         trace_kmem_cache_alloc_node(_RET_IP_, ret,
2433                                     s->object_size, s->size, gfpflags, node);
2434
2435         return ret;
2436 }
2437 EXPORT_SYMBOL(kmem_cache_alloc_node);
2438
2439 #ifdef CONFIG_TRACING
2440 void *kmem_cache_alloc_node_trace(struct kmem_cache *s,
2441                                     gfp_t gfpflags,
2442                                     int node, size_t size)
2443 {
2444         void *ret = slab_alloc_node(s, gfpflags, node, _RET_IP_);
2445
2446         trace_kmalloc_node(_RET_IP_, ret,
2447                            size, s->size, gfpflags, node);
2448         return ret;
2449 }
2450 EXPORT_SYMBOL(kmem_cache_alloc_node_trace);
2451 #endif
2452 #endif
2453
2454 /*
2455  * Slow patch handling. This may still be called frequently since objects
2456  * have a longer lifetime than the cpu slabs in most processing loads.
2457  *
2458  * So we still attempt to reduce cache line usage. Just take the slab
2459  * lock and free the item. If there is no additional partial page
2460  * handling required then we can return immediately.
2461  */
2462 static void __slab_free(struct kmem_cache *s, struct page *page,
2463                         void *x, unsigned long addr)
2464 {
2465         void *prior;
2466         void **object = (void *)x;
2467         int was_frozen;
2468         struct page new;
2469         unsigned long counters;
2470         struct kmem_cache_node *n = NULL;
2471         unsigned long uninitialized_var(flags);
2472
2473         stat(s, FREE_SLOWPATH);
2474
2475         if (kmem_cache_debug(s) &&
2476                 !(n = free_debug_processing(s, page, x, addr, &flags)))
2477                 return;
2478
2479         do {
2480                 if (unlikely(n)) {
2481                         spin_unlock_irqrestore(&n->list_lock, flags);
2482                         n = NULL;
2483                 }
2484                 prior = page->freelist;
2485                 counters = page->counters;
2486                 set_freepointer(s, object, prior);
2487                 new.counters = counters;
2488                 was_frozen = new.frozen;
2489                 new.inuse--;
2490                 if ((!new.inuse || !prior) && !was_frozen) {
2491
2492                         if (!kmem_cache_debug(s) && !prior)
2493
2494                                 /*
2495                                  * Slab was on no list before and will be partially empty
2496                                  * We can defer the list move and instead freeze it.
2497                                  */
2498                                 new.frozen = 1;
2499
2500                         else { /* Needs to be taken off a list */
2501
2502                                 n = get_node(s, page_to_nid(page));
2503                                 /*
2504                                  * Speculatively acquire the list_lock.
2505                                  * If the cmpxchg does not succeed then we may
2506                                  * drop the list_lock without any processing.
2507                                  *
2508                                  * Otherwise the list_lock will synchronize with
2509                                  * other processors updating the list of slabs.
2510                                  */
2511                                 spin_lock_irqsave(&n->list_lock, flags);
2512
2513                         }
2514                 }
2515
2516         } while (!cmpxchg_double_slab(s, page,
2517                 prior, counters,
2518                 object, new.counters,
2519                 "__slab_free"));
2520
2521         if (likely(!n)) {
2522
2523                 /*
2524                  * If we just froze the page then put it onto the
2525                  * per cpu partial list.
2526                  */
2527                 if (new.frozen && !was_frozen) {
2528                         put_cpu_partial(s, page, 1);
2529                         stat(s, CPU_PARTIAL_FREE);
2530                 }
2531                 /*
2532                  * The list lock was not taken therefore no list
2533                  * activity can be necessary.
2534                  */
2535                 if (was_frozen)
2536                         stat(s, FREE_FROZEN);
2537                 return;
2538         }
2539
2540         if (unlikely(!new.inuse && n->nr_partial > s->min_partial))
2541                 goto slab_empty;
2542
2543         /*
2544          * Objects left in the slab. If it was not on the partial list before
2545          * then add it.
2546          */
2547         if (kmem_cache_debug(s) && unlikely(!prior)) {
2548                 remove_full(s, page);
2549                 add_partial(n, page, DEACTIVATE_TO_TAIL);
2550                 stat(s, FREE_ADD_PARTIAL);
2551         }
2552         spin_unlock_irqrestore(&n->list_lock, flags);
2553         return;
2554
2555 slab_empty:
2556         if (prior) {
2557                 /*
2558                  * Slab on the partial list.
2559                  */
2560                 remove_partial(n, page);
2561                 stat(s, FREE_REMOVE_PARTIAL);
2562         } else
2563                 /* Slab must be on the full list */
2564                 remove_full(s, page);
2565
2566         spin_unlock_irqrestore(&n->list_lock, flags);
2567         stat(s, FREE_SLAB);
2568         discard_slab(s, page);
2569 }
2570
2571 /*
2572  * Fastpath with forced inlining to produce a kfree and kmem_cache_free that
2573  * can perform fastpath freeing without additional function calls.
2574  *
2575  * The fastpath is only possible if we are freeing to the current cpu slab
2576  * of this processor. This typically the case if we have just allocated
2577  * the item before.
2578  *
2579  * If fastpath is not possible then fall back to __slab_free where we deal
2580  * with all sorts of special processing.
2581  */
2582 static __always_inline void slab_free(struct kmem_cache *s,
2583                         struct page *page, void *x, unsigned long addr)
2584 {
2585         void **object = (void *)x;
2586         struct kmem_cache_cpu *c;
2587         unsigned long tid;
2588
2589         slab_free_hook(s, x);
2590
2591 redo:
2592         /*
2593          * Determine the currently cpus per cpu slab.
2594          * The cpu may change afterward. However that does not matter since
2595          * data is retrieved via this pointer. If we are on the same cpu
2596          * during the cmpxchg then the free will succedd.
2597          */
2598         c = __this_cpu_ptr(s->cpu_slab);
2599
2600         tid = c->tid;
2601         barrier();
2602
2603         if (likely(page == c->page)) {
2604                 set_freepointer(s, object, c->freelist);
2605
2606                 if (unlikely(!this_cpu_cmpxchg_double(
2607                                 s->cpu_slab->freelist, s->cpu_slab->tid,
2608                                 c->freelist, tid,
2609                                 object, next_tid(tid)))) {
2610
2611                         note_cmpxchg_failure("slab_free", s, tid);
2612                         goto redo;
2613                 }
2614                 stat(s, FREE_FASTPATH);
2615         } else
2616                 __slab_free(s, page, x, addr);
2617
2618 }
2619
2620 void kmem_cache_free(struct kmem_cache *s, void *x)
2621 {
2622         s = cache_from_obj(s, x);
2623         if (!s)
2624                 return;
2625         slab_free(s, virt_to_head_page(x), x, _RET_IP_);
2626         trace_kmem_cache_free(_RET_IP_, x);
2627 }
2628 EXPORT_SYMBOL(kmem_cache_free);
2629
2630 /*
2631  * Object placement in a slab is made very easy because we always start at
2632  * offset 0. If we tune the size of the object to the alignment then we can
2633  * get the required alignment by putting one properly sized object after
2634  * another.
2635  *
2636  * Notice that the allocation order determines the sizes of the per cpu
2637  * caches. Each processor has always one slab available for allocations.
2638  * Increasing the allocation order reduces the number of times that slabs
2639  * must be moved on and off the partial lists and is therefore a factor in
2640  * locking overhead.
2641  */
2642
2643 /*
2644  * Mininum / Maximum order of slab pages. This influences locking overhead
2645  * and slab fragmentation. A higher order reduces the number of partial slabs
2646  * and increases the number of allocations possible without having to
2647  * take the list_lock.
2648  */
2649 static int slub_min_order;
2650 static int slub_max_order = PAGE_ALLOC_COSTLY_ORDER;
2651 static int slub_min_objects;
2652
2653 /*
2654  * Merge control. If this is set then no merging of slab caches will occur.
2655  * (Could be removed. This was introduced to pacify the merge skeptics.)
2656  */
2657 static int slub_nomerge;
2658
2659 /*
2660  * Calculate the order of allocation given an slab object size.
2661  *
2662  * The order of allocation has significant impact on performance and other
2663  * system components. Generally order 0 allocations should be preferred since
2664  * order 0 does not cause fragmentation in the page allocator. Larger objects
2665  * be problematic to put into order 0 slabs because there may be too much
2666  * unused space left. We go to a higher order if more than 1/16th of the slab
2667  * would be wasted.
2668  *
2669  * In order to reach satisfactory performance we must ensure that a minimum
2670  * number of objects is in one slab. Otherwise we may generate too much
2671  * activity on the partial lists which requires taking the list_lock. This is
2672  * less a concern for large slabs though which are rarely used.
2673  *
2674  * slub_max_order specifies the order where we begin to stop considering the
2675  * number of objects in a slab as critical. If we reach slub_max_order then
2676  * we try to keep the page order as low as possible. So we accept more waste
2677  * of space in favor of a small page order.
2678  *
2679  * Higher order allocations also allow the placement of more objects in a
2680  * slab and thereby reduce object handling overhead. If the user has
2681  * requested a higher mininum order then we start with that one instead of
2682  * the smallest order which will fit the object.
2683  */
2684 static inline int slab_order(int size, int min_objects,
2685                                 int max_order, int fract_leftover, int reserved)
2686 {
2687         int order;
2688         int rem;
2689         int min_order = slub_min_order;
2690
2691         if (order_objects(min_order, size, reserved) > MAX_OBJS_PER_PAGE)
2692                 return get_order(size * MAX_OBJS_PER_PAGE) - 1;
2693
2694         for (order = max(min_order,
2695                                 fls(min_objects * size - 1) - PAGE_SHIFT);
2696                         order <= max_order; order++) {
2697
2698                 unsigned long slab_size = PAGE_SIZE << order;
2699
2700                 if (slab_size < min_objects * size + reserved)
2701                         continue;
2702
2703                 rem = (slab_size - reserved) % size;
2704
2705                 if (rem <= slab_size / fract_leftover)
2706                         break;
2707
2708         }
2709
2710         return order;
2711 }
2712
2713 static inline int calculate_order(int size, int reserved)
2714 {
2715         int order;
2716         int min_objects;
2717         int fraction;
2718         int max_objects;
2719
2720         /*
2721          * Attempt to find best configuration for a slab. This
2722          * works by first attempting to generate a layout with
2723          * the best configuration and backing off gradually.
2724          *
2725          * First we reduce the acceptable waste in a slab. Then
2726          * we reduce the minimum objects required in a slab.
2727          */
2728         min_objects = slub_min_objects;
2729         if (!min_objects)
2730                 min_objects = 4 * (fls(nr_cpu_ids) + 1);
2731         max_objects = order_objects(slub_max_order, size, reserved);
2732         min_objects = min(min_objects, max_objects);
2733
2734         while (min_objects > 1) {
2735                 fraction = 16;
2736                 while (fraction >= 4) {
2737                         order = slab_order(size, min_objects,
2738                                         slub_max_order, fraction, reserved);
2739                         if (order <= slub_max_order)
2740                                 return order;
2741                         fraction /= 2;
2742                 }
2743                 min_objects--;
2744         }
2745
2746         /*
2747          * We were unable to place multiple objects in a slab. Now
2748          * lets see if we can place a single object there.
2749          */
2750         order = slab_order(size, 1, slub_max_order, 1, reserved);
2751         if (order <= slub_max_order)
2752                 return order;
2753
2754         /*
2755          * Doh this slab cannot be placed using slub_max_order.
2756          */
2757         order = slab_order(size, 1, MAX_ORDER, 1, reserved);
2758         if (order < MAX_ORDER)
2759                 return order;
2760         return -ENOSYS;
2761 }
2762
2763 static void
2764 init_kmem_cache_node(struct kmem_cache_node *n)
2765 {
2766         n->nr_partial = 0;
2767         spin_lock_init(&n->list_lock);
2768         INIT_LIST_HEAD(&n->partial);
2769 #ifdef CONFIG_SLUB_DEBUG
2770         atomic_long_set(&n->nr_slabs, 0);
2771         atomic_long_set(&n->total_objects, 0);
2772         INIT_LIST_HEAD(&n->full);
2773 #endif
2774 }
2775
2776 static inline int alloc_kmem_cache_cpus(struct kmem_cache *s)
2777 {
2778         BUILD_BUG_ON(PERCPU_DYNAMIC_EARLY_SIZE <
2779                         SLUB_PAGE_SHIFT * sizeof(struct kmem_cache_cpu));
2780
2781         /*
2782          * Must align to double word boundary for the double cmpxchg
2783          * instructions to work; see __pcpu_double_call_return_bool().
2784          */
2785         s->cpu_slab = __alloc_percpu(sizeof(struct kmem_cache_cpu),
2786                                      2 * sizeof(void *));
2787
2788         if (!s->cpu_slab)
2789                 return 0;
2790
2791         init_kmem_cache_cpus(s);
2792
2793         return 1;
2794 }
2795
2796 static struct kmem_cache *kmem_cache_node;
2797
2798 /*
2799  * No kmalloc_node yet so do it by hand. We know that this is the first
2800  * slab on the node for this slabcache. There are no concurrent accesses
2801  * possible.
2802  *
2803  * Note that this function only works on the kmalloc_node_cache
2804  * when allocating for the kmalloc_node_cache. This is used for bootstrapping
2805  * memory on a fresh node that has no slab structures yet.
2806  */
2807 static void early_kmem_cache_node_alloc(int node)
2808 {
2809         struct page *page;
2810         struct kmem_cache_node *n;
2811
2812         BUG_ON(kmem_cache_node->size < sizeof(struct kmem_cache_node));
2813
2814         page = new_slab(kmem_cache_node, GFP_NOWAIT, node);
2815
2816         BUG_ON(!page);
2817         if (page_to_nid(page) != node) {
2818                 printk(KERN_ERR "SLUB: Unable to allocate memory from "
2819                                 "node %d\n", node);
2820                 printk(KERN_ERR "SLUB: Allocating a useless per node structure "
2821                                 "in order to be able to continue\n");
2822         }
2823
2824         n = page->freelist;
2825         BUG_ON(!n);
2826         page->freelist = get_freepointer(kmem_cache_node, n);
2827         page->inuse = 1;
2828         page->frozen = 0;
2829         kmem_cache_node->node[node] = n;
2830 #ifdef CONFIG_SLUB_DEBUG
2831         init_object(kmem_cache_node, n, SLUB_RED_ACTIVE);
2832         init_tracking(kmem_cache_node, n);
2833 #endif
2834         init_kmem_cache_node(n);
2835         inc_slabs_node(kmem_cache_node, node, page->objects);
2836
2837         add_partial(n, page, DEACTIVATE_TO_HEAD);
2838 }
2839
2840 static void free_kmem_cache_nodes(struct kmem_cache *s)
2841 {
2842         int node;
2843
2844         for_each_node_state(node, N_NORMAL_MEMORY) {
2845                 struct kmem_cache_node *n = s->node[node];
2846
2847                 if (n)
2848                         kmem_cache_free(kmem_cache_node, n);
2849
2850                 s->node[node] = NULL;
2851         }
2852 }
2853
2854 static int init_kmem_cache_nodes(struct kmem_cache *s)
2855 {
2856         int node;
2857
2858         for_each_node_state(node, N_NORMAL_MEMORY) {
2859                 struct kmem_cache_node *n;
2860
2861                 if (slab_state == DOWN) {
2862                         early_kmem_cache_node_alloc(node);
2863                         continue;
2864                 }
2865                 n = kmem_cache_alloc_node(kmem_cache_node,
2866                                                 GFP_KERNEL, node);
2867
2868                 if (!n) {
2869                         free_kmem_cache_nodes(s);
2870                         return 0;
2871                 }
2872
2873                 s->node[node] = n;
2874                 init_kmem_cache_node(n);
2875         }
2876         return 1;
2877 }
2878
2879 static void set_min_partial(struct kmem_cache *s, unsigned long min)
2880 {
2881         if (min < MIN_PARTIAL)
2882                 min = MIN_PARTIAL;
2883         else if (min > MAX_PARTIAL)
2884                 min = MAX_PARTIAL;
2885         s->min_partial = min;
2886 }
2887
2888 /*
2889  * calculate_sizes() determines the order and the distribution of data within
2890  * a slab object.
2891  */
2892 static int calculate_sizes(struct kmem_cache *s, int forced_order)
2893 {
2894         unsigned long flags = s->flags;
2895         unsigned long size = s->object_size;
2896         int order;
2897
2898         /*
2899          * Round up object size to the next word boundary. We can only
2900          * place the free pointer at word boundaries and this determines
2901          * the possible location of the free pointer.
2902          */
2903         size = ALIGN(size, sizeof(void *));
2904
2905 #ifdef CONFIG_SLUB_DEBUG
2906         /*
2907          * Determine if we can poison the object itself. If the user of
2908          * the slab may touch the object after free or before allocation
2909          * then we should never poison the object itself.
2910          */
2911         if ((flags & SLAB_POISON) && !(flags & SLAB_DESTROY_BY_RCU) &&
2912                         !s->ctor)
2913                 s->flags |= __OBJECT_POISON;
2914         else
2915                 s->flags &= ~__OBJECT_POISON;
2916
2917
2918         /*
2919          * If we are Redzoning then check if there is some space between the
2920          * end of the object and the free pointer. If not then add an
2921          * additional word to have some bytes to store Redzone information.
2922          */
2923         if ((flags & SLAB_RED_ZONE) && size == s->object_size)
2924                 size += sizeof(void *);
2925 #endif
2926
2927         /*
2928          * With that we have determined the number of bytes in actual use
2929          * by the object. This is the potential offset to the free pointer.
2930          */
2931         s->inuse = size;
2932
2933         if (((flags & (SLAB_DESTROY_BY_RCU | SLAB_POISON)) ||
2934                 s->ctor)) {
2935                 /*
2936                  * Relocate free pointer after the object if it is not
2937                  * permitted to overwrite the first word of the object on
2938                  * kmem_cache_free.
2939                  *
2940                  * This is the case if we do RCU, have a constructor or
2941                  * destructor or are poisoning the objects.
2942                  */
2943                 s->offset = size;
2944                 size += sizeof(void *);
2945         }
2946
2947 #ifdef CONFIG_SLUB_DEBUG
2948         if (flags & SLAB_STORE_USER)
2949                 /*
2950                  * Need to store information about allocs and frees after
2951                  * the object.
2952                  */
2953                 size += 2 * sizeof(struct track);
2954
2955         if (flags & SLAB_RED_ZONE)
2956                 /*
2957                  * Add some empty padding so that we can catch
2958                  * overwrites from earlier objects rather than let
2959                  * tracking information or the free pointer be
2960                  * corrupted if a user writes before the start
2961                  * of the object.
2962                  */
2963                 size += sizeof(void *);
2964 #endif
2965
2966         /*
2967          * SLUB stores one object immediately after another beginning from
2968          * offset 0. In order to align the objects we have to simply size
2969          * each object to conform to the alignment.
2970          */
2971         size = ALIGN(size, s->align);
2972         s->size = size;
2973         if (forced_order >= 0)
2974                 order = forced_order;
2975         else
2976                 order = calculate_order(size, s->reserved);
2977
2978         if (order < 0)
2979                 return 0;
2980
2981         s->allocflags = 0;
2982         if (order)
2983                 s->allocflags |= __GFP_COMP;
2984
2985         if (s->flags & SLAB_CACHE_DMA)
2986                 s->allocflags |= SLUB_DMA;
2987
2988         if (s->flags & SLAB_RECLAIM_ACCOUNT)
2989                 s->allocflags |= __GFP_RECLAIMABLE;
2990
2991         /*
2992          * Determine the number of objects per slab
2993          */
2994         s->oo = oo_make(order, size, s->reserved);
2995         s->min = oo_make(get_order(size), size, s->reserved);
2996         if (oo_objects(s->oo) > oo_objects(s->max))
2997                 s->max = s->oo;
2998
2999         return !!oo_objects(s->oo);
3000 }
3001
3002 static int kmem_cache_open(struct kmem_cache *s, unsigned long flags)
3003 {
3004         s->flags = kmem_cache_flags(s->size, flags, s->name, s->ctor);
3005         s->reserved = 0;
3006
3007         if (need_reserve_slab_rcu && (s->flags & SLAB_DESTROY_BY_RCU))
3008                 s->reserved = sizeof(struct rcu_head);
3009
3010         if (!calculate_sizes(s, -1))
3011                 goto error;
3012         if (disable_higher_order_debug) {
3013                 /*
3014                  * Disable debugging flags that store metadata if the min slab
3015                  * order increased.
3016                  */
3017                 if (get_order(s->size) > get_order(s->object_size)) {
3018                         s->flags &= ~DEBUG_METADATA_FLAGS;
3019                         s->offset = 0;
3020                         if (!calculate_sizes(s, -1))
3021                                 goto error;
3022                 }
3023         }
3024
3025 #if defined(CONFIG_HAVE_CMPXCHG_DOUBLE) && \
3026     defined(CONFIG_HAVE_ALIGNED_STRUCT_PAGE)
3027         if (system_has_cmpxchg_double() && (s->flags & SLAB_DEBUG_FLAGS) == 0)
3028                 /* Enable fast mode */
3029                 s->flags |= __CMPXCHG_DOUBLE;
3030 #endif
3031
3032         /*
3033          * The larger the object size is, the more pages we want on the partial
3034          * list to avoid pounding the page allocator excessively.
3035          */
3036         set_min_partial(s, ilog2(s->size) / 2);
3037
3038         /*
3039          * cpu_partial determined the maximum number of objects kept in the
3040          * per cpu partial lists of a processor.
3041          *
3042          * Per cpu partial lists mainly contain slabs that just have one
3043          * object freed. If they are used for allocation then they can be
3044          * filled up again with minimal effort. The slab will never hit the
3045          * per node partial lists and therefore no locking will be required.
3046          *
3047          * This setting also determines
3048          *
3049          * A) The number of objects from per cpu partial slabs dumped to the
3050          *    per node list when we reach the limit.
3051          * B) The number of objects in cpu partial slabs to extract from the
3052          *    per node list when we run out of per cpu objects. We only fetch 50%
3053          *    to keep some capacity around for frees.
3054          */
3055         if (kmem_cache_debug(s))
3056                 s->cpu_partial = 0;
3057         else if (s->size >= PAGE_SIZE)
3058                 s->cpu_partial = 2;
3059         else if (s->size >= 1024)
3060                 s->cpu_partial = 6;
3061         else if (s->size >= 256)
3062                 s->cpu_partial = 13;
3063         else
3064                 s->cpu_partial = 30;
3065
3066 #ifdef CONFIG_NUMA
3067         s->remote_node_defrag_ratio = 1000;
3068 #endif
3069         if (!init_kmem_cache_nodes(s))
3070                 goto error;
3071
3072         if (alloc_kmem_cache_cpus(s))
3073                 return 0;
3074
3075         free_kmem_cache_nodes(s);
3076 error:
3077         if (flags & SLAB_PANIC)
3078                 panic("Cannot create slab %s size=%lu realsize=%u "
3079                         "order=%u offset=%u flags=%lx\n",
3080                         s->name, (unsigned long)s->size, s->size, oo_order(s->oo),
3081                         s->offset, flags);
3082         return -EINVAL;
3083 }
3084
3085 static void list_slab_objects(struct kmem_cache *s, struct page *page,
3086                                                         const char *text)
3087 {
3088 #ifdef CONFIG_SLUB_DEBUG
3089         void *addr = page_address(page);
3090         void *p;
3091         unsigned long *map = kzalloc(BITS_TO_LONGS(page->objects) *
3092                                      sizeof(long), GFP_ATOMIC);
3093         if (!map)
3094                 return;
3095         slab_err(s, page, text, s->name);
3096         slab_lock(page);
3097
3098         get_map(s, page, map);
3099         for_each_object(p, s, addr, page->objects) {
3100
3101                 if (!test_bit(slab_index(p, s, addr), map)) {
3102                         printk(KERN_ERR "INFO: Object 0x%p @offset=%tu\n",
3103                                                         p, p - addr);
3104                         print_tracking(s, p);
3105                 }
3106         }
3107         slab_unlock(page);
3108         kfree(map);
3109 #endif
3110 }
3111
3112 /*
3113  * Attempt to free all partial slabs on a node.
3114  * This is called from kmem_cache_close(). We must be the last thread
3115  * using the cache and therefore we do not need to lock anymore.
3116  */
3117 static void free_partial(struct kmem_cache *s, struct kmem_cache_node *n)
3118 {
3119         struct page *page, *h;
3120
3121         list_for_each_entry_safe(page, h, &n->partial, lru) {
3122                 if (!page->inuse) {
3123                         remove_partial(n, page);
3124                         discard_slab(s, page);
3125                 } else {
3126                         list_slab_objects(s, page,
3127                         "Objects remaining in %s on kmem_cache_close()");
3128                 }
3129         }
3130 }
3131
3132 /*
3133  * Release all resources used by a slab cache.
3134  */
3135 static inline int kmem_cache_close(struct kmem_cache *s)
3136 {
3137         int node;
3138
3139         flush_all(s);
3140         /* Attempt to free all objects */
3141         for_each_node_state(node, N_NORMAL_MEMORY) {
3142                 struct kmem_cache_node *n = get_node(s, node);
3143
3144                 free_partial(s, n);
3145                 if (n->nr_partial || slabs_node(s, node))
3146                         return 1;
3147         }
3148         free_percpu(s->cpu_slab);
3149         free_kmem_cache_nodes(s);
3150         return 0;
3151 }
3152
3153 int __kmem_cache_shutdown(struct kmem_cache *s)
3154 {
3155         int rc = kmem_cache_close(s);
3156
3157         if (!rc) {
3158                 /*
3159                  * We do the same lock strategy around sysfs_slab_add, see
3160                  * __kmem_cache_create. Because this is pretty much the last
3161                  * operation we do and the lock will be released shortly after
3162                  * that in slab_common.c, we could just move sysfs_slab_remove
3163                  * to a later point in common code. We should do that when we
3164                  * have a common sysfs framework for all allocators.
3165                  */
3166                 mutex_unlock(&slab_mutex);
3167                 sysfs_slab_remove(s);
3168                 mutex_lock(&slab_mutex);
3169         }
3170
3171         return rc;
3172 }
3173
3174 /********************************************************************
3175  *              Kmalloc subsystem
3176  *******************************************************************/
3177
3178 struct kmem_cache *kmalloc_caches[SLUB_PAGE_SHIFT];
3179 EXPORT_SYMBOL(kmalloc_caches);
3180
3181 #ifdef CONFIG_ZONE_DMA
3182 static struct kmem_cache *kmalloc_dma_caches[SLUB_PAGE_SHIFT];
3183 #endif
3184
3185 static int __init setup_slub_min_order(char *str)
3186 {
3187         get_option(&str, &slub_min_order);
3188
3189         return 1;
3190 }
3191
3192 __setup("slub_min_order=", setup_slub_min_order);
3193
3194 static int __init setup_slub_max_order(char *str)
3195 {
3196         get_option(&str, &slub_max_order);
3197         slub_max_order = min(slub_max_order, MAX_ORDER - 1);
3198
3199         return 1;
3200 }
3201
3202 __setup("slub_max_order=", setup_slub_max_order);
3203
3204 static int __init setup_slub_min_objects(char *str)
3205 {
3206         get_option(&str, &slub_min_objects);
3207
3208         return 1;
3209 }
3210
3211 __setup("slub_min_objects=", setup_slub_min_objects);
3212
3213 static int __init setup_slub_nomerge(char *str)
3214 {
3215         slub_nomerge = 1;
3216         return 1;
3217 }
3218
3219 __setup("slub_nomerge", setup_slub_nomerge);
3220
3221 /*
3222  * Conversion table for small slabs sizes / 8 to the index in the
3223  * kmalloc array. This is necessary for slabs < 192 since we have non power
3224  * of two cache sizes there. The size of larger slabs can be determined using
3225  * fls.
3226  */
3227 static s8 size_index[24] = {
3228         3,      /* 8 */
3229         4,      /* 16 */
3230         5,      /* 24 */
3231         5,      /* 32 */
3232         6,      /* 40 */
3233         6,      /* 48 */
3234         6,      /* 56 */
3235         6,      /* 64 */
3236         1,      /* 72 */
3237         1,      /* 80 */
3238         1,      /* 88 */
3239         1,      /* 96 */
3240         7,      /* 104 */
3241         7,      /* 112 */
3242         7,      /* 120 */
3243         7,      /* 128 */
3244         2,      /* 136 */
3245         2,      /* 144 */
3246         2,      /* 152 */
3247         2,      /* 160 */
3248         2,      /* 168 */
3249         2,      /* 176 */
3250         2,      /* 184 */
3251         2       /* 192 */
3252 };
3253
3254 static inline int size_index_elem(size_t bytes)
3255 {
3256         return (bytes - 1) / 8;
3257 }
3258
3259 static struct kmem_cache *get_slab(size_t size, gfp_t flags)
3260 {
3261         int index;
3262
3263         if (size <= 192) {
3264                 if (!size)
3265                         return ZERO_SIZE_PTR;
3266
3267                 index = size_index[size_index_elem(size)];
3268         } else
3269                 index = fls(size - 1);
3270
3271 #ifdef CONFIG_ZONE_DMA
3272         if (unlikely((flags & SLUB_DMA)))
3273                 return kmalloc_dma_caches[index];
3274
3275 #endif
3276         return kmalloc_caches[index];
3277 }
3278
3279 void *__kmalloc(size_t size, gfp_t flags)
3280 {
3281         struct kmem_cache *s;
3282         void *ret;
3283
3284         if (unlikely(size > SLUB_MAX_SIZE))
3285                 return kmalloc_large(size, flags);
3286
3287         s = get_slab(size, flags);
3288
3289         if (unlikely(ZERO_OR_NULL_PTR(s)))
3290                 return s;
3291
3292         ret = slab_alloc(s, flags, _RET_IP_);
3293
3294         trace_kmalloc(_RET_IP_, ret, size, s->size, flags);
3295
3296         return ret;
3297 }
3298 EXPORT_SYMBOL(__kmalloc);
3299
3300 #ifdef CONFIG_NUMA
3301 static void *kmalloc_large_node(size_t size, gfp_t flags, int node)
3302 {
3303         struct page *page;
3304         void *ptr = NULL;
3305
3306         flags |= __GFP_COMP | __GFP_NOTRACK | __GFP_KMEMCG;
3307         page = alloc_pages_node(node, flags, get_order(size));
3308         if (page)
3309                 ptr = page_address(page);
3310
3311         kmemleak_alloc(ptr, size, 1, flags);
3312         return ptr;
3313 }
3314
3315 void *__kmalloc_node(size_t size, gfp_t flags, int node)
3316 {
3317         struct kmem_cache *s;
3318         void *ret;
3319
3320         if (unlikely(size > SLUB_MAX_SIZE)) {
3321                 ret = kmalloc_large_node(size, flags, node);
3322
3323                 trace_kmalloc_node(_RET_IP_, ret,
3324                                    size, PAGE_SIZE << get_order(size),
3325                                    flags, node);
3326
3327                 return ret;
3328         }
3329
3330         s = get_slab(size, flags);
3331
3332         if (unlikely(ZERO_OR_NULL_PTR(s)))
3333                 return s;
3334
3335         ret = slab_alloc_node(s, flags, node, _RET_IP_);
3336
3337         trace_kmalloc_node(_RET_IP_, ret, size, s->size, flags, node);
3338
3339         return ret;
3340 }
3341 EXPORT_SYMBOL(__kmalloc_node);
3342 #endif
3343
3344 size_t ksize(const void *object)
3345 {
3346         struct page *page;
3347
3348         if (unlikely(object == ZERO_SIZE_PTR))
3349                 return 0;
3350
3351         page = virt_to_head_page(object);
3352
3353         if (unlikely(!PageSlab(page))) {
3354                 WARN_ON(!PageCompound(page));
3355                 return PAGE_SIZE << compound_order(page);
3356         }
3357
3358         return slab_ksize(page->slab_cache);
3359 }
3360 EXPORT_SYMBOL(ksize);
3361
3362 #ifdef CONFIG_SLUB_DEBUG
3363 bool verify_mem_not_deleted(const void *x)
3364 {
3365         struct page *page;
3366         void *object = (void *)x;
3367         unsigned long flags;
3368         bool rv;
3369
3370         if (unlikely(ZERO_OR_NULL_PTR(x)))
3371                 return false;
3372
3373         local_irq_save(flags);
3374
3375         page = virt_to_head_page(x);
3376         if (unlikely(!PageSlab(page))) {
3377                 /* maybe it was from stack? */
3378                 rv = true;
3379                 goto out_unlock;
3380         }
3381
3382         slab_lock(page);
3383         if (on_freelist(page->slab_cache, page, object)) {
3384                 object_err(page->slab_cache, page, object, "Object is on free-list");
3385                 rv = false;
3386         } else {
3387                 rv = true;
3388         }
3389         slab_unlock(page);
3390
3391 out_unlock:
3392         local_irq_restore(flags);
3393         return rv;
3394 }
3395 EXPORT_SYMBOL(verify_mem_not_deleted);
3396 #endif
3397
3398 void kfree(const void *x)
3399 {
3400         struct page *page;
3401         void *object = (void *)x;
3402
3403         trace_kfree(_RET_IP_, x);
3404
3405         if (unlikely(ZERO_OR_NULL_PTR(x)))
3406                 return;
3407
3408         page = virt_to_head_page(x);
3409         if (unlikely(!PageSlab(page))) {
3410                 BUG_ON(!PageCompound(page));
3411                 kmemleak_free(x);
3412                 __free_memcg_kmem_pages(page, compound_order(page));
3413                 return;
3414         }
3415         slab_free(page->slab_cache, page, object, _RET_IP_);
3416 }
3417 EXPORT_SYMBOL(kfree);
3418
3419 /*
3420  * kmem_cache_shrink removes empty slabs from the partial lists and sorts
3421  * the remaining slabs by the number of items in use. The slabs with the
3422  * most items in use come first. New allocations will then fill those up
3423  * and thus they can be removed from the partial lists.
3424  *
3425  * The slabs with the least items are placed last. This results in them
3426  * being allocated from last increasing the chance that the last objects
3427  * are freed in them.
3428  */
3429 int kmem_cache_shrink(struct kmem_cache *s)
3430 {
3431         int node;
3432         int i;
3433         struct kmem_cache_node *n;
3434         struct page *page;
3435         struct page *t;
3436         int objects = oo_objects(s->max);
3437         struct list_head *slabs_by_inuse =
3438                 kmalloc(sizeof(struct list_head) * objects, GFP_KERNEL);
3439         unsigned long flags;
3440
3441         if (!slabs_by_inuse)
3442                 return -ENOMEM;
3443
3444         flush_all(s);
3445         for_each_node_state(node, N_NORMAL_MEMORY) {
3446                 n = get_node(s, node);
3447
3448                 if (!n->nr_partial)
3449                         continue;
3450
3451                 for (i = 0; i < objects; i++)
3452                         INIT_LIST_HEAD(slabs_by_inuse + i);
3453
3454                 spin_lock_irqsave(&n->list_lock, flags);
3455
3456                 /*
3457                  * Build lists indexed by the items in use in each slab.
3458                  *
3459                  * Note that concurrent frees may occur while we hold the
3460                  * list_lock. page->inuse here is the upper limit.
3461                  */
3462                 list_for_each_entry_safe(page, t, &n->partial, lru) {
3463                         list_move(&page->lru, slabs_by_inuse + page->inuse);
3464                         if (!page->inuse)
3465                                 n->nr_partial--;
3466                 }
3467
3468                 /*
3469                  * Rebuild the partial list with the slabs filled up most
3470                  * first and the least used slabs at the end.
3471                  */
3472                 for (i = objects - 1; i > 0; i--)
3473                         list_splice(slabs_by_inuse + i, n->partial.prev);
3474
3475                 spin_unlock_irqrestore(&n->list_lock, flags);
3476
3477                 /* Release empty slabs */
3478                 list_for_each_entry_safe(page, t, slabs_by_inuse, lru)
3479                         discard_slab(s, page);
3480         }
3481
3482         kfree(slabs_by_inuse);
3483         return 0;
3484 }
3485 EXPORT_SYMBOL(kmem_cache_shrink);
3486
3487 static int slab_mem_going_offline_callback(void *arg)
3488 {
3489         struct kmem_cache *s;
3490
3491         mutex_lock(&slab_mutex);
3492         list_for_each_entry(s, &slab_caches, list)
3493                 kmem_cache_shrink(s);
3494         mutex_unlock(&slab_mutex);
3495
3496         return 0;
3497 }
3498
3499 static void slab_mem_offline_callback(void *arg)
3500 {
3501         struct kmem_cache_node *n;
3502         struct kmem_cache *s;
3503         struct memory_notify *marg = arg;
3504         int offline_node;
3505
3506         offline_node = marg->status_change_nid_normal;
3507
3508         /*
3509          * If the node still has available memory. we need kmem_cache_node
3510          * for it yet.
3511          */
3512         if (offline_node < 0)
3513                 return;
3514
3515         mutex_lock(&slab_mutex);
3516         list_for_each_entry(s, &slab_caches, list) {
3517                 n = get_node(s, offline_node);
3518                 if (n) {
3519                         /*
3520                          * if n->nr_slabs > 0, slabs still exist on the node
3521                          * that is going down. We were unable to free them,
3522                          * and offline_pages() function shouldn't call this
3523                          * callback. So, we must fail.
3524                          */
3525                         BUG_ON(slabs_node(s, offline_node));
3526
3527                         s->node[offline_node] = NULL;
3528                         kmem_cache_free(kmem_cache_node, n);
3529                 }
3530         }
3531         mutex_unlock(&slab_mutex);
3532 }
3533
3534 static int slab_mem_going_online_callback(void *arg)
3535 {
3536         struct kmem_cache_node *n;
3537         struct kmem_cache *s;
3538         struct memory_notify *marg = arg;
3539         int nid = marg->status_change_nid_normal;
3540         int ret = 0;
3541
3542         /*
3543          * If the node's memory is already available, then kmem_cache_node is
3544          * already created. Nothing to do.
3545          */
3546         if (nid < 0)
3547                 return 0;
3548
3549         /*
3550          * We are bringing a node online. No memory is available yet. We must
3551          * allocate a kmem_cache_node structure in order to bring the node
3552          * online.
3553          */
3554         mutex_lock(&slab_mutex);
3555         list_for_each_entry(s, &slab_caches, list) {
3556                 /*
3557                  * XXX: kmem_cache_alloc_node will fallback to other nodes
3558                  *      since memory is not yet available from the node that
3559                  *      is brought up.
3560                  */
3561                 n = kmem_cache_alloc(kmem_cache_node, GFP_KERNEL);
3562                 if (!n) {
3563                         ret = -ENOMEM;
3564                         goto out;
3565                 }
3566                 init_kmem_cache_node(n);
3567                 s->node[nid] = n;
3568         }
3569 out:
3570         mutex_unlock(&slab_mutex);
3571         return ret;
3572 }
3573
3574 static int slab_memory_callback(struct notifier_block *self,
3575                                 unsigned long action, void *arg)
3576 {
3577         int ret = 0;
3578
3579         switch (action) {
3580         case MEM_GOING_ONLINE:
3581                 ret = slab_mem_going_online_callback(arg);
3582                 break;
3583         case MEM_GOING_OFFLINE:
3584                 ret = slab_mem_going_offline_callback(arg);
3585                 break;
3586         case MEM_OFFLINE:
3587         case MEM_CANCEL_ONLINE:
3588                 slab_mem_offline_callback(arg);
3589                 break;
3590         case MEM_ONLINE:
3591         case MEM_CANCEL_OFFLINE:
3592                 break;
3593         }
3594         if (ret)
3595                 ret = notifier_from_errno(ret);
3596         else
3597                 ret = NOTIFY_OK;
3598         return ret;
3599 }
3600
3601 static struct notifier_block slab_memory_callback_nb = {
3602         .notifier_call = slab_memory_callback,
3603         .priority = SLAB_CALLBACK_PRI,
3604 };
3605
3606 /********************************************************************
3607  *                      Basic setup of slabs
3608  *******************************************************************/
3609
3610 /*
3611  * Used for early kmem_cache structures that were allocated using
3612  * the page allocator. Allocate them properly then fix up the pointers
3613  * that may be pointing to the wrong kmem_cache structure.
3614  */
3615
3616 static struct kmem_cache * __init bootstrap(struct kmem_cache *static_cache)
3617 {
3618         int node;
3619         struct kmem_cache *s = kmem_cache_zalloc(kmem_cache, GFP_NOWAIT);
3620
3621         memcpy(s, static_cache, kmem_cache->object_size);
3622
3623         for_each_node_state(node, N_NORMAL_MEMORY) {
3624                 struct kmem_cache_node *n = get_node(s, node);
3625                 struct page *p;
3626
3627                 if (n) {
3628                         list_for_each_entry(p, &n->partial, lru)
3629                                 p->slab_cache = s;
3630
3631 #ifdef CONFIG_SLUB_DEBUG
3632                         list_for_each_entry(p, &n->full, lru)
3633                                 p->slab_cache = s;
3634 #endif
3635                 }
3636         }
3637         list_add(&s->list, &slab_caches);
3638         return s;
3639 }
3640
3641 void __init kmem_cache_init(void)
3642 {
3643         static __initdata struct kmem_cache boot_kmem_cache,
3644                 boot_kmem_cache_node;
3645         int i;
3646         int caches = 2;
3647
3648         if (debug_guardpage_minorder())
3649                 slub_max_order = 0;
3650
3651         kmem_cache_node = &boot_kmem_cache_node;
3652         kmem_cache = &boot_kmem_cache;
3653
3654         create_boot_cache(kmem_cache_node, "kmem_cache_node",
3655                 sizeof(struct kmem_cache_node), SLAB_HWCACHE_ALIGN);
3656
3657         register_hotmemory_notifier(&slab_memory_callback_nb);
3658
3659         /* Able to allocate the per node structures */
3660         slab_state = PARTIAL;
3661
3662         create_boot_cache(kmem_cache, "kmem_cache",
3663                         offsetof(struct kmem_cache, node) +
3664                                 nr_node_ids * sizeof(struct kmem_cache_node *),
3665                        SLAB_HWCACHE_ALIGN);
3666
3667         kmem_cache = bootstrap(&boot_kmem_cache);
3668
3669         /*
3670          * Allocate kmem_cache_node properly from the kmem_cache slab.
3671          * kmem_cache_node is separately allocated so no need to
3672          * update any list pointers.
3673          */
3674         kmem_cache_node = bootstrap(&boot_kmem_cache_node);
3675
3676         /* Now we can use the kmem_cache to allocate kmalloc slabs */
3677
3678         /*
3679          * Patch up the size_index table if we have strange large alignment
3680          * requirements for the kmalloc array. This is only the case for
3681          * MIPS it seems. The standard arches will not generate any code here.
3682          *
3683          * Largest permitted alignment is 256 bytes due to the way we
3684          * handle the index determination for the smaller caches.
3685          *
3686          * Make sure that nothing crazy happens if someone starts tinkering
3687          * around with ARCH_KMALLOC_MINALIGN
3688          */
3689         BUILD_BUG_ON(KMALLOC_MIN_SIZE > 256 ||
3690                 (KMALLOC_MIN_SIZE & (KMALLOC_MIN_SIZE - 1)));
3691
3692         for (i = 8; i < KMALLOC_MIN_SIZE; i += 8) {
3693                 int elem = size_index_elem(i);
3694                 if (elem >= ARRAY_SIZE(size_index))
3695                         break;
3696                 size_index[elem] = KMALLOC_SHIFT_LOW;
3697         }
3698
3699         if (KMALLOC_MIN_SIZE == 64) {
3700                 /*
3701                  * The 96 byte size cache is not used if the alignment
3702                  * is 64 byte.
3703                  */
3704                 for (i = 64 + 8; i <= 96; i += 8)
3705                         size_index[size_index_elem(i)] = 7;
3706         } else if (KMALLOC_MIN_SIZE == 128) {
3707                 /*
3708                  * The 192 byte sized cache is not used if the alignment
3709                  * is 128 byte. Redirect kmalloc to use the 256 byte cache
3710                  * instead.
3711                  */
3712                 for (i = 128 + 8; i <= 192; i += 8)
3713                         size_index[size_index_elem(i)] = 8;
3714         }
3715
3716         /* Caches that are not of the two-to-the-power-of size */
3717         if (KMALLOC_MIN_SIZE <= 32) {
3718                 kmalloc_caches[1] = create_kmalloc_cache("kmalloc-96", 96, 0);
3719                 caches++;
3720         }
3721
3722         if (KMALLOC_MIN_SIZE <= 64) {
3723                 kmalloc_caches[2] = create_kmalloc_cache("kmalloc-192", 192, 0);
3724                 caches++;
3725         }
3726
3727         for (i = KMALLOC_SHIFT_LOW; i < SLUB_PAGE_SHIFT; i++) {
3728                 kmalloc_caches[i] = create_kmalloc_cache("kmalloc", 1 << i, 0);
3729                 caches++;
3730         }
3731
3732         slab_state = UP;
3733
3734         /* Provide the correct kmalloc names now that the caches are up */
3735         if (KMALLOC_MIN_SIZE <= 32) {
3736                 kmalloc_caches[1]->name = kstrdup(kmalloc_caches[1]->name, GFP_NOWAIT);
3737                 BUG_ON(!kmalloc_caches[1]->name);
3738         }
3739
3740         if (KMALLOC_MIN_SIZE <= 64) {
3741                 kmalloc_caches[2]->name = kstrdup(kmalloc_caches[2]->name, GFP_NOWAIT);
3742                 BUG_ON(!kmalloc_caches[2]->name);
3743         }
3744
3745         for (i = KMALLOC_SHIFT_LOW; i < SLUB_PAGE_SHIFT; i++) {
3746                 char *s = kasprintf(GFP_NOWAIT, "kmalloc-%d", 1 << i);
3747
3748                 BUG_ON(!s);
3749                 kmalloc_caches[i]->name = s;
3750         }
3751
3752 #ifdef CONFIG_SMP
3753         register_cpu_notifier(&slab_notifier);
3754 #endif
3755
3756 #ifdef CONFIG_ZONE_DMA
3757         for (i = 0; i < SLUB_PAGE_SHIFT; i++) {
3758                 struct kmem_cache *s = kmalloc_caches[i];
3759
3760                 if (s && s->size) {
3761                         char *name = kasprintf(GFP_NOWAIT,
3762                                  "dma-kmalloc-%d", s->object_size);
3763
3764                         BUG_ON(!name);
3765                         kmalloc_dma_caches[i] = create_kmalloc_cache(name,
3766                                 s->object_size, SLAB_CACHE_DMA);
3767                 }
3768         }
3769 #endif
3770         printk(KERN_INFO
3771                 "SLUB: Genslabs=%d, HWalign=%d, Order=%d-%d, MinObjects=%d,"
3772                 " CPUs=%d, Nodes=%d\n",
3773                 caches, cache_line_size(),
3774                 slub_min_order, slub_max_order, slub_min_objects,
3775                 nr_cpu_ids, nr_node_ids);
3776 }
3777
3778 void __init kmem_cache_init_late(void)
3779 {
3780 }
3781
3782 /*
3783  * Find a mergeable slab cache
3784  */
3785 static int slab_unmergeable(struct kmem_cache *s)
3786 {
3787         if (slub_nomerge || (s->flags & SLUB_NEVER_MERGE))
3788                 return 1;
3789
3790         if (s->ctor)
3791                 return 1;
3792
3793         /*
3794          * We may have set a slab to be unmergeable during bootstrap.
3795          */
3796         if (s->refcount < 0)
3797                 return 1;
3798
3799         return 0;
3800 }
3801
3802 static struct kmem_cache *find_mergeable(struct mem_cgroup *memcg, size_t size,
3803                 size_t align, unsigned long flags, const char *name,
3804                 void (*ctor)(void *))
3805 {
3806         struct kmem_cache *s;
3807
3808         if (slub_nomerge || (flags & SLUB_NEVER_MERGE))
3809                 return NULL;
3810
3811         if (ctor)
3812                 return NULL;
3813
3814         size = ALIGN(size, sizeof(void *));
3815         align = calculate_alignment(flags, align, size);
3816         size = ALIGN(size, align);
3817         flags = kmem_cache_flags(size, flags, name, NULL);
3818
3819         list_for_each_entry(s, &slab_caches, list) {
3820                 if (slab_unmergeable(s))
3821                         continue;
3822
3823                 if (size > s->size)
3824                         continue;
3825
3826                 if ((flags & SLUB_MERGE_SAME) != (s->flags & SLUB_MERGE_SAME))
3827                                 continue;
3828                 /*
3829                  * Check if alignment is compatible.
3830                  * Courtesy of Adrian Drzewiecki
3831                  */
3832                 if ((s->size & ~(align - 1)) != s->size)
3833                         continue;
3834
3835                 if (s->size - size >= sizeof(void *))
3836                         continue;
3837
3838                 if (!cache_match_memcg(s, memcg))
3839                         continue;
3840
3841                 return s;
3842         }
3843         return NULL;
3844 }
3845
3846 struct kmem_cache *
3847 __kmem_cache_alias(struct mem_cgroup *memcg, const char *name, size_t size,
3848                    size_t align, unsigned long flags, void (*ctor)(void *))
3849 {
3850         struct kmem_cache *s;
3851
3852         s = find_mergeable(memcg, size, align, flags, name, ctor);
3853         if (s) {
3854                 s->refcount++;
3855                 /*
3856                  * Adjust the object sizes so that we clear
3857                  * the complete object on kzalloc.
3858                  */
3859                 s->object_size = max(s->object_size, (int)size);
3860                 s->inuse = max_t(int, s->inuse, ALIGN(size, sizeof(void *)));
3861
3862                 if (sysfs_slab_alias(s, name)) {
3863                         s->refcount--;
3864                         s = NULL;
3865                 }
3866         }
3867
3868         return s;
3869 }
3870
3871 int __kmem_cache_create(struct kmem_cache *s, unsigned long flags)
3872 {
3873         int err;
3874
3875         err = kmem_cache_open(s, flags);
3876         if (err)
3877                 return err;
3878
3879         /* Mutex is not taken during early boot */
3880         if (slab_state <= UP)
3881                 return 0;
3882
3883         memcg_propagate_slab_attrs(s);
3884         mutex_unlock(&slab_mutex);
3885         err = sysfs_slab_add(s);
3886         mutex_lock(&slab_mutex);
3887
3888         if (err)
3889                 kmem_cache_close(s);
3890
3891         return err;
3892 }
3893
3894 #ifdef CONFIG_SMP
3895 /*
3896  * Use the cpu notifier to insure that the cpu slabs are flushed when
3897  * necessary.
3898  */
3899 static int __cpuinit slab_cpuup_callback(struct notifier_block *nfb,
3900                 unsigned long action, void *hcpu)
3901 {
3902         long cpu = (long)hcpu;
3903         struct kmem_cache *s;
3904         unsigned long flags;
3905
3906         switch (action) {
3907         case CPU_UP_CANCELED:
3908         case CPU_UP_CANCELED_FROZEN:
3909         case CPU_DEAD:
3910         case CPU_DEAD_FROZEN:
3911                 mutex_lock(&slab_mutex);
3912                 list_for_each_entry(s, &slab_caches, list) {
3913                         local_irq_save(flags);
3914                         __flush_cpu_slab(s, cpu);
3915                         local_irq_restore(flags);
3916                 }
3917                 mutex_unlock(&slab_mutex);
3918                 break;
3919         default:
3920                 break;
3921         }
3922         return NOTIFY_OK;
3923 }
3924
3925 static struct notifier_block __cpuinitdata slab_notifier = {
3926         .notifier_call = slab_cpuup_callback
3927 };
3928
3929 #endif
3930
3931 void *__kmalloc_track_caller(size_t size, gfp_t gfpflags, unsigned long caller)
3932 {
3933         struct kmem_cache *s;
3934         void *ret;
3935
3936         if (unlikely(size > SLUB_MAX_SIZE))
3937                 return kmalloc_large(size, gfpflags);
3938
3939         s = get_slab(size, gfpflags);
3940
3941         if (unlikely(ZERO_OR_NULL_PTR(s)))
3942                 return s;
3943
3944         ret = slab_alloc(s, gfpflags, caller);
3945
3946         /* Honor the call site pointer we received. */
3947         trace_kmalloc(caller, ret, size, s->size, gfpflags);
3948
3949         return ret;
3950 }
3951
3952 #ifdef CONFIG_NUMA
3953 void *__kmalloc_node_track_caller(size_t size, gfp_t gfpflags,
3954                                         int node, unsigned long caller)
3955 {
3956         struct kmem_cache *s;
3957         void *ret;
3958
3959         if (unlikely(size > SLUB_MAX_SIZE)) {
3960                 ret = kmalloc_large_node(size, gfpflags, node);
3961
3962                 trace_kmalloc_node(caller, ret,
3963                                    size, PAGE_SIZE << get_order(size),
3964                                    gfpflags, node);
3965
3966                 return ret;
3967         }
3968
3969         s = get_slab(size, gfpflags);
3970
3971         if (unlikely(ZERO_OR_NULL_PTR(s)))
3972                 return s;
3973
3974         ret = slab_alloc_node(s, gfpflags, node, caller);
3975
3976         /* Honor the call site pointer we received. */
3977         trace_kmalloc_node(caller, ret, size, s->size, gfpflags, node);
3978
3979         return ret;
3980 }
3981 #endif
3982
3983 #ifdef CONFIG_SYSFS
3984 static int count_inuse(struct page *page)
3985 {
3986         return page->inuse;
3987 }
3988
3989 static int count_total(struct page *page)
3990 {
3991         return page->objects;
3992 }
3993 #endif
3994
3995 #ifdef CONFIG_SLUB_DEBUG
3996 static int validate_slab(struct kmem_cache *s, struct page *page,
3997                                                 unsigned long *map)
3998 {
3999         void *p;
4000         void *addr = page_address(page);
4001
4002         if (!check_slab(s, page) ||
4003                         !on_freelist(s, page, NULL))
4004                 return 0;
4005
4006         /* Now we know that a valid freelist exists */
4007         bitmap_zero(map, page->objects);
4008
4009         get_map(s, page, map);
4010         for_each_object(p, s, addr, page->objects) {
4011                 if (test_bit(slab_index(p, s, addr), map))
4012                         if (!check_object(s, page, p, SLUB_RED_INACTIVE))
4013                                 return 0;
4014         }
4015
4016         for_each_object(p, s, addr, page->objects)
4017                 if (!test_bit(slab_index(p, s, addr), map))
4018                         if (!check_object(s, page, p, SLUB_RED_ACTIVE))
4019                                 return 0;
4020         return 1;
4021 }
4022
4023 static void validate_slab_slab(struct kmem_cache *s, struct page *page,
4024                                                 unsigned long *map)
4025 {
4026         slab_lock(page);
4027         validate_slab(s, page, map);
4028         slab_unlock(page);
4029 }
4030
4031 static int validate_slab_node(struct kmem_cache *s,
4032                 struct kmem_cache_node *n, unsigned long *map)
4033 {
4034         unsigned long count = 0;
4035         struct page *page;
4036         unsigned long flags;
4037
4038         spin_lock_irqsave(&n->list_lock, flags);
4039
4040         list_for_each_entry(page, &n->partial, lru) {
4041                 validate_slab_slab(s, page, map);
4042                 count++;
4043         }
4044         if (count != n->nr_partial)
4045                 printk(KERN_ERR "SLUB %s: %ld partial slabs counted but "
4046                         "counter=%ld\n", s->name, count, n->nr_partial);
4047
4048         if (!(s->flags & SLAB_STORE_USER))
4049                 goto out;
4050
4051         list_for_each_entry(page, &n->full, lru) {
4052                 validate_slab_slab(s, page, map);
4053                 count++;
4054         }
4055         if (count != atomic_long_read(&n->nr_slabs))
4056                 printk(KERN_ERR "SLUB: %s %ld slabs counted but "
4057                         "counter=%ld\n", s->name, count,
4058                         atomic_long_read(&n->nr_slabs));
4059
4060 out:
4061         spin_unlock_irqrestore(&n->list_lock, flags);
4062         return count;
4063 }
4064
4065 static long validate_slab_cache(struct kmem_cache *s)
4066 {
4067         int node;
4068         unsigned long count = 0;
4069         unsigned long *map = kmalloc(BITS_TO_LONGS(oo_objects(s->max)) *
4070                                 sizeof(unsigned long), GFP_KERNEL);
4071
4072         if (!map)
4073                 return -ENOMEM;
4074
4075         flush_all(s);
4076         for_each_node_state(node, N_NORMAL_MEMORY) {
4077                 struct kmem_cache_node *n = get_node(s, node);
4078
4079                 count += validate_slab_node(s, n, map);
4080         }
4081         kfree(map);
4082         return count;
4083 }
4084 /*
4085  * Generate lists of code addresses where slabcache objects are allocated
4086  * and freed.
4087  */
4088
4089 struct location {
4090         unsigned long count;
4091         unsigned long addr;
4092         long long sum_time;
4093         long min_time;
4094         long max_time;
4095         long min_pid;
4096         long max_pid;
4097         DECLARE_BITMAP(cpus, NR_CPUS);
4098         nodemask_t nodes;
4099 };
4100
4101 struct loc_track {
4102         unsigned long max;
4103         unsigned long count;
4104         struct location *loc;
4105 };
4106
4107 static void free_loc_track(struct loc_track *t)
4108 {
4109         if (t->max)
4110                 free_pages((unsigned long)t->loc,
4111                         get_order(sizeof(struct location) * t->max));
4112 }
4113
4114 static int alloc_loc_track(struct loc_track *t, unsigned long max, gfp_t flags)
4115 {
4116         struct location *l;
4117         int order;
4118
4119         order = get_order(sizeof(struct location) * max);
4120
4121         l = (void *)__get_free_pages(flags, order);
4122         if (!l)
4123                 return 0;
4124
4125         if (t->count) {
4126                 memcpy(l, t->loc, sizeof(struct location) * t->count);
4127                 free_loc_track(t);
4128         }
4129         t->max = max;
4130         t->loc = l;
4131         return 1;
4132 }
4133
4134 static int add_location(struct loc_track *t, struct kmem_cache *s,
4135                                 const struct track *track)
4136 {
4137         long start, end, pos;
4138         struct location *l;
4139         unsigned long caddr;
4140         unsigned long age = jiffies - track->when;
4141
4142         start = -1;
4143         end = t->count;
4144
4145         for ( ; ; ) {
4146                 pos = start + (end - start + 1) / 2;
4147
4148                 /*
4149                  * There is nothing at "end". If we end up there
4150                  * we need to add something to before end.
4151                  */
4152                 if (pos == end)
4153                         break;
4154
4155                 caddr = t->loc[pos].addr;
4156                 if (track->addr == caddr) {
4157
4158                         l = &t->loc[pos];
4159                         l->count++;
4160                         if (track->when) {
4161                                 l->sum_time += age;
4162                                 if (age < l->min_time)
4163                                         l->min_time = age;
4164                                 if (age > l->max_time)
4165                                         l->max_time = age;
4166
4167                                 if (track->pid < l->min_pid)
4168                                         l->min_pid = track->pid;
4169                                 if (track->pid > l->max_pid)
4170                                         l->max_pid = track->pid;
4171
4172                                 cpumask_set_cpu(track->cpu,
4173                                                 to_cpumask(l->cpus));
4174                         }
4175                         node_set(page_to_nid(virt_to_page(track)), l->nodes);
4176                         return 1;
4177                 }
4178
4179                 if (track->addr < caddr)
4180                         end = pos;
4181                 else
4182                         start = pos;
4183         }
4184
4185         /*
4186          * Not found. Insert new tracking element.
4187          */
4188         if (t->count >= t->max && !alloc_loc_track(t, 2 * t->max, GFP_ATOMIC))
4189                 return 0;
4190
4191         l = t->loc + pos;
4192         if (pos < t->count)
4193                 memmove(l + 1, l,
4194                         (t->count - pos) * sizeof(struct location));
4195         t->count++;
4196         l->count = 1;
4197         l->addr = track->addr;
4198         l->sum_time = age;
4199         l->min_time = age;
4200         l->max_time = age;
4201         l->min_pid = track->pid;
4202         l->max_pid = track->pid;
4203         cpumask_clear(to_cpumask(l->cpus));
4204         cpumask_set_cpu(track->cpu, to_cpumask(l->cpus));
4205         nodes_clear(l->nodes);
4206         node_set(page_to_nid(virt_to_page(track)), l->nodes);
4207         return 1;
4208 }
4209
4210 static void process_slab(struct loc_track *t, struct kmem_cache *s,
4211                 struct page *page, enum track_item alloc,
4212                 unsigned long *map)
4213 {
4214         void *addr = page_address(page);
4215         void *p;
4216
4217         bitmap_zero(map, page->objects);
4218         get_map(s, page, map);
4219
4220         for_each_object(p, s, addr, page->objects)
4221                 if (!test_bit(slab_index(p, s, addr), map))
4222                         add_location(t, s, get_track(s, p, alloc));
4223 }
4224
4225 static int list_locations(struct kmem_cache *s, char *buf,
4226                                         enum track_item alloc)
4227 {
4228         int len = 0;
4229         unsigned long i;
4230         struct loc_track t = { 0, 0, NULL };
4231         int node;
4232         unsigned long *map = kmalloc(BITS_TO_LONGS(oo_objects(s->max)) *
4233                                      sizeof(unsigned long), GFP_KERNEL);
4234
4235         if (!map || !alloc_loc_track(&t, PAGE_SIZE / sizeof(struct location),
4236                                      GFP_TEMPORARY)) {
4237                 kfree(map);
4238                 return sprintf(buf, "Out of memory\n");
4239         }
4240         /* Push back cpu slabs */
4241         flush_all(s);
4242
4243         for_each_node_state(node, N_NORMAL_MEMORY) {
4244                 struct kmem_cache_node *n = get_node(s, node);
4245                 unsigned long flags;
4246                 struct page *page;
4247
4248                 if (!atomic_long_read(&n->nr_slabs))
4249                         continue;
4250
4251                 spin_lock_irqsave(&n->list_lock, flags);
4252                 list_for_each_entry(page, &n->partial, lru)
4253                         process_slab(&t, s, page, alloc, map);
4254                 list_for_each_entry(page, &n->full, lru)
4255                         process_slab(&t, s, page, alloc, map);
4256                 spin_unlock_irqrestore(&n->list_lock, flags);
4257         }
4258
4259         for (i = 0; i < t.count; i++) {
4260                 struct location *l = &t.loc[i];
4261
4262                 if (len > PAGE_SIZE - KSYM_SYMBOL_LEN - 100)
4263                         break;
4264                 len += sprintf(buf + len, "%7ld ", l->count);
4265
4266                 if (l->addr)
4267                         len += sprintf(buf + len, "%pS", (void *)l->addr);
4268                 else
4269                         len += sprintf(buf + len, "<not-available>");
4270
4271                 if (l->sum_time != l->min_time) {
4272                         len += sprintf(buf + len, " age=%ld/%ld/%ld",
4273                                 l->min_time,
4274                                 (long)div_u64(l->sum_time, l->count),
4275                                 l->max_time);
4276                 } else
4277                         len += sprintf(buf + len, " age=%ld",
4278                                 l->min_time);
4279
4280                 if (l->min_pid != l->max_pid)
4281                         len += sprintf(buf + len, " pid=%ld-%ld",
4282                                 l->min_pid, l->max_pid);
4283                 else
4284                         len += sprintf(buf + len, " pid=%ld",
4285                                 l->min_pid);
4286
4287                 if (num_online_cpus() > 1 &&
4288                                 !cpumask_empty(to_cpumask(l->cpus)) &&
4289                                 len < PAGE_SIZE - 60) {
4290                         len += sprintf(buf + len, " cpus=");
4291                         len += cpulist_scnprintf(buf + len, PAGE_SIZE - len - 50,
4292                                                  to_cpumask(l->cpus));
4293                 }
4294
4295                 if (nr_online_nodes > 1 && !nodes_empty(l->nodes) &&
4296                                 len < PAGE_SIZE - 60) {
4297                         len += sprintf(buf + len, " nodes=");
4298                         len += nodelist_scnprintf(buf + len, PAGE_SIZE - len - 50,
4299                                         l->nodes);
4300                 }
4301
4302                 len += sprintf(buf + len, "\n");
4303         }
4304
4305         free_loc_track(&t);
4306         kfree(map);
4307         if (!t.count)
4308                 len += sprintf(buf, "No data\n");
4309         return len;
4310 }
4311 #endif
4312
4313 #ifdef SLUB_RESILIENCY_TEST
4314 static void resiliency_test(void)
4315 {
4316         u8 *p;
4317
4318         BUILD_BUG_ON(KMALLOC_MIN_SIZE > 16 || SLUB_PAGE_SHIFT < 10);
4319
4320         printk(KERN_ERR "SLUB resiliency testing\n");
4321         printk(KERN_ERR "-----------------------\n");
4322         printk(KERN_ERR "A. Corruption after allocation\n");
4323
4324         p = kzalloc(16, GFP_KERNEL);
4325         p[16] = 0x12;
4326         printk(KERN_ERR "\n1. kmalloc-16: Clobber Redzone/next pointer"
4327                         " 0x12->0x%p\n\n", p + 16);
4328
4329         validate_slab_cache(kmalloc_caches[4]);
4330
4331         /* Hmmm... The next two are dangerous */
4332         p = kzalloc(32, GFP_KERNEL);
4333         p[32 + sizeof(void *)] = 0x34;
4334         printk(KERN_ERR "\n2. kmalloc-32: Clobber next pointer/next slab"
4335                         " 0x34 -> -0x%p\n", p);
4336         printk(KERN_ERR
4337                 "If allocated object is overwritten then not detectable\n\n");
4338
4339         validate_slab_cache(kmalloc_caches[5]);
4340         p = kzalloc(64, GFP_KERNEL);
4341         p += 64 + (get_cycles() & 0xff) * sizeof(void *);
4342         *p = 0x56;
4343         printk(KERN_ERR "\n3. kmalloc-64: corrupting random byte 0x56->0x%p\n",
4344                                                                         p);
4345         printk(KERN_ERR
4346                 "If allocated object is overwritten then not detectable\n\n");
4347         validate_slab_cache(kmalloc_caches[6]);
4348
4349         printk(KERN_ERR "\nB. Corruption after free\n");
4350         p = kzalloc(128, GFP_KERNEL);
4351         kfree(p);
4352         *p = 0x78;
4353         printk(KERN_ERR "1. kmalloc-128: Clobber first word 0x78->0x%p\n\n", p);
4354         validate_slab_cache(kmalloc_caches[7]);
4355
4356         p = kzalloc(256, GFP_KERNEL);
4357         kfree(p);
4358         p[50] = 0x9a;
4359         printk(KERN_ERR "\n2. kmalloc-256: Clobber 50th byte 0x9a->0x%p\n\n",
4360                         p);
4361         validate_slab_cache(kmalloc_caches[8]);
4362
4363         p = kzalloc(512, GFP_KERNEL);
4364         kfree(p);
4365         p[512] = 0xab;
4366         printk(KERN_ERR "\n3. kmalloc-512: Clobber redzone 0xab->0x%p\n\n", p);
4367         validate_slab_cache(kmalloc_caches[9]);
4368 }
4369 #else
4370 #ifdef CONFIG_SYSFS
4371 static void resiliency_test(void) {};
4372 #endif
4373 #endif
4374
4375 #ifdef CONFIG_SYSFS
4376 enum slab_stat_type {
4377         SL_ALL,                 /* All slabs */
4378         SL_PARTIAL,             /* Only partially allocated slabs */
4379         SL_CPU,                 /* Only slabs used for cpu caches */
4380         SL_OBJECTS,             /* Determine allocated objects not slabs */
4381         SL_TOTAL                /* Determine object capacity not slabs */
4382 };
4383
4384 #define SO_ALL          (1 << SL_ALL)
4385 #define SO_PARTIAL      (1 << SL_PARTIAL)
4386 #define SO_CPU          (1 << SL_CPU)
4387 #define SO_OBJECTS      (1 << SL_OBJECTS)
4388 #define SO_TOTAL        (1 << SL_TOTAL)
4389
4390 static ssize_t show_slab_objects(struct kmem_cache *s,
4391                             char *buf, unsigned long flags)
4392 {
4393         unsigned long total = 0;
4394         int node;
4395         int x;
4396         unsigned long *nodes;
4397         unsigned long *per_cpu;
4398
4399         nodes = kzalloc(2 * sizeof(unsigned long) * nr_node_ids, GFP_KERNEL);
4400         if (!nodes)
4401                 return -ENOMEM;
4402         per_cpu = nodes + nr_node_ids;
4403
4404         if (flags & SO_CPU) {
4405                 int cpu;
4406
4407                 for_each_possible_cpu(cpu) {
4408                         struct kmem_cache_cpu *c = per_cpu_ptr(s->cpu_slab, cpu);
4409                         int node;
4410                         struct page *page;
4411
4412                         page = ACCESS_ONCE(c->page);
4413                         if (!page)
4414                                 continue;
4415
4416                         node = page_to_nid(page);
4417                         if (flags & SO_TOTAL)
4418                                 x = page->objects;
4419                         else if (flags & SO_OBJECTS)
4420                                 x = page->inuse;
4421                         else
4422                                 x = 1;
4423
4424                         total += x;
4425                         nodes[node] += x;
4426
4427                         page = ACCESS_ONCE(c->partial);
4428                         if (page) {
4429                                 x = page->pobjects;
4430                                 total += x;
4431                                 nodes[node] += x;
4432                         }
4433
4434                         per_cpu[node]++;
4435                 }
4436         }
4437
4438         lock_memory_hotplug();
4439 #ifdef CONFIG_SLUB_DEBUG
4440         if (flags & SO_ALL) {
4441                 for_each_node_state(node, N_NORMAL_MEMORY) {
4442                         struct kmem_cache_node *n = get_node(s, node);
4443
4444                 if (flags & SO_TOTAL)
4445                         x = atomic_long_read(&n->total_objects);
4446                 else if (flags & SO_OBJECTS)
4447                         x = atomic_long_read(&n->total_objects) -
4448                                 count_partial(n, count_free);
4449
4450                         else
4451                                 x = atomic_long_read(&n->nr_slabs);
4452                         total += x;
4453                         nodes[node] += x;
4454                 }
4455
4456         } else
4457 #endif
4458         if (flags & SO_PARTIAL) {
4459                 for_each_node_state(node, N_NORMAL_MEMORY) {
4460                         struct kmem_cache_node *n = get_node(s, node);
4461
4462                         if (flags & SO_TOTAL)
4463                                 x = count_partial(n, count_total);
4464                         else if (flags & SO_OBJECTS)
4465                                 x = count_partial(n, count_inuse);
4466                         else
4467                                 x = n->nr_partial;
4468                         total += x;
4469                         nodes[node] += x;
4470                 }
4471         }
4472         x = sprintf(buf, "%lu", total);
4473 #ifdef CONFIG_NUMA
4474         for_each_node_state(node, N_NORMAL_MEMORY)
4475                 if (nodes[node])
4476                         x += sprintf(buf + x, " N%d=%lu",
4477                                         node, nodes[node]);
4478 #endif
4479         unlock_memory_hotplug();
4480         kfree(nodes);
4481         return x + sprintf(buf + x, "\n");
4482 }
4483
4484 #ifdef CONFIG_SLUB_DEBUG
4485 static int any_slab_objects(struct kmem_cache *s)
4486 {
4487         int node;
4488
4489         for_each_online_node(node) {
4490                 struct kmem_cache_node *n = get_node(s, node);
4491
4492                 if (!n)
4493                         continue;
4494
4495                 if (atomic_long_read(&n->total_objects))
4496                         return 1;
4497         }
4498         return 0;
4499 }
4500 #endif
4501
4502 #define to_slab_attr(n) container_of(n, struct slab_attribute, attr)
4503 #define to_slab(n) container_of(n, struct kmem_cache, kobj)
4504
4505 struct slab_attribute {
4506         struct attribute attr;
4507         ssize_t (*show)(struct kmem_cache *s, char *buf);
4508         ssize_t (*store)(struct kmem_cache *s, const char *x, size_t count);
4509 };
4510
4511 #define SLAB_ATTR_RO(_name) \
4512         static struct slab_attribute _name##_attr = \
4513         __ATTR(_name, 0400, _name##_show, NULL)
4514
4515 #define SLAB_ATTR(_name) \
4516         static struct slab_attribute _name##_attr =  \
4517         __ATTR(_name, 0600, _name##_show, _name##_store)
4518
4519 static ssize_t slab_size_show(struct kmem_cache *s, char *buf)
4520 {
4521         return sprintf(buf, "%d\n", s->size);
4522 }
4523 SLAB_ATTR_RO(slab_size);
4524
4525 static ssize_t align_show(struct kmem_cache *s, char *buf)
4526 {
4527         return sprintf(buf, "%d\n", s->align);
4528 }
4529 SLAB_ATTR_RO(align);
4530
4531 static ssize_t object_size_show(struct kmem_cache *s, char *buf)
4532 {
4533         return sprintf(buf, "%d\n", s->object_size);
4534 }
4535 SLAB_ATTR_RO(object_size);
4536
4537 static ssize_t objs_per_slab_show(struct kmem_cache *s, char *buf)
4538 {
4539         return sprintf(buf, "%d\n", oo_objects(s->oo));
4540 }
4541 SLAB_ATTR_RO(objs_per_slab);
4542
4543 static ssize_t order_store(struct kmem_cache *s,
4544                                 const char *buf, size_t length)
4545 {
4546         unsigned long order;
4547         int err;
4548
4549         err = strict_strtoul(buf, 10, &order);
4550         if (err)
4551                 return err;
4552
4553         if (order > slub_max_order || order < slub_min_order)
4554                 return -EINVAL;
4555
4556         calculate_sizes(s, order);
4557         return length;
4558 }
4559
4560 static ssize_t order_show(struct kmem_cache *s, char *buf)
4561 {
4562         return sprintf(buf, "%d\n", oo_order(s->oo));
4563 }
4564 SLAB_ATTR(order);
4565
4566 static ssize_t min_partial_show(struct kmem_cache *s, char *buf)
4567 {
4568         return sprintf(buf, "%lu\n", s->min_partial);
4569 }
4570
4571 static ssize_t min_partial_store(struct kmem_cache *s, const char *buf,
4572                                  size_t length)
4573 {
4574         unsigned long min;
4575         int err;
4576
4577         err = strict_strtoul(buf, 10, &min);
4578         if (err)
4579                 return err;
4580
4581         set_min_partial(s, min);
4582         return length;
4583 }
4584 SLAB_ATTR(min_partial);
4585
4586 static ssize_t cpu_partial_show(struct kmem_cache *s, char *buf)
4587 {
4588         return sprintf(buf, "%u\n", s->cpu_partial);
4589 }
4590
4591 static ssize_t cpu_partial_store(struct kmem_cache *s, const char *buf,
4592                                  size_t length)
4593 {
4594         unsigned long objects;
4595         int err;
4596
4597         err = strict_strtoul(buf, 10, &objects);
4598         if (err)
4599                 return err;
4600         if (objects && kmem_cache_debug(s))
4601                 return -EINVAL;
4602
4603         s->cpu_partial = objects;
4604         flush_all(s);
4605         return length;
4606 }
4607 SLAB_ATTR(cpu_partial);
4608
4609 static ssize_t ctor_show(struct kmem_cache *s, char *buf)
4610 {
4611         if (!s->ctor)
4612                 return 0;
4613         return sprintf(buf, "%pS\n", s->ctor);
4614 }
4615 SLAB_ATTR_RO(ctor);
4616
4617 static ssize_t aliases_show(struct kmem_cache *s, char *buf)
4618 {
4619         return sprintf(buf, "%d\n", s->refcount - 1);
4620 }
4621 SLAB_ATTR_RO(aliases);
4622
4623 static ssize_t partial_show(struct kmem_cache *s, char *buf)
4624 {
4625         return show_slab_objects(s, buf, SO_PARTIAL);
4626 }
4627 SLAB_ATTR_RO(partial);
4628
4629 static ssize_t cpu_slabs_show(struct kmem_cache *s, char *buf)
4630 {
4631         return show_slab_objects(s, buf, SO_CPU);
4632 }
4633 SLAB_ATTR_RO(cpu_slabs);
4634
4635 static ssize_t objects_show(struct kmem_cache *s, char *buf)
4636 {
4637         return show_slab_objects(s, buf, SO_ALL|SO_OBJECTS);
4638 }
4639 SLAB_ATTR_RO(objects);
4640
4641 static ssize_t objects_partial_show(struct kmem_cache *s, char *buf)
4642 {
4643         return show_slab_objects(s, buf, SO_PARTIAL|SO_OBJECTS);
4644 }
4645 SLAB_ATTR_RO(objects_partial);
4646
4647 static ssize_t slabs_cpu_partial_show(struct kmem_cache *s, char *buf)
4648 {
4649         int objects = 0;
4650         int pages = 0;
4651         int cpu;
4652         int len;
4653
4654         for_each_online_cpu(cpu) {
4655                 struct page *page = per_cpu_ptr(s->cpu_slab, cpu)->partial;
4656
4657                 if (page) {
4658                         pages += page->pages;
4659                         objects += page->pobjects;
4660                 }
4661         }
4662
4663         len = sprintf(buf, "%d(%d)", objects, pages);
4664
4665 #ifdef CONFIG_SMP
4666         for_each_online_cpu(cpu) {
4667                 struct page *page = per_cpu_ptr(s->cpu_slab, cpu) ->partial;
4668
4669                 if (page && len < PAGE_SIZE - 20)
4670                         len += sprintf(buf + len, " C%d=%d(%d)", cpu,
4671                                 page->pobjects, page->pages);
4672         }
4673 #endif
4674         return len + sprintf(buf + len, "\n");
4675 }
4676 SLAB_ATTR_RO(slabs_cpu_partial);
4677
4678 static ssize_t reclaim_account_show(struct kmem_cache *s, char *buf)
4679 {
4680         return sprintf(buf, "%d\n", !!(s->flags & SLAB_RECLAIM_ACCOUNT));
4681 }
4682
4683 static ssize_t reclaim_account_store(struct kmem_cache *s,
4684                                 const char *buf, size_t length)
4685 {
4686         s->flags &= ~SLAB_RECLAIM_ACCOUNT;
4687         if (buf[0] == '1')
4688                 s->flags |= SLAB_RECLAIM_ACCOUNT;
4689         return length;
4690 }
4691 SLAB_ATTR(reclaim_account);
4692
4693 static ssize_t hwcache_align_show(struct kmem_cache *s, char *buf)
4694 {
4695         return sprintf(buf, "%d\n", !!(s->flags & SLAB_HWCACHE_ALIGN));
4696 }
4697 SLAB_ATTR_RO(hwcache_align);
4698
4699 #ifdef CONFIG_ZONE_DMA
4700 static ssize_t cache_dma_show(struct kmem_cache *s, char *buf)
4701 {
4702         return sprintf(buf, "%d\n", !!(s->flags & SLAB_CACHE_DMA));
4703 }
4704 SLAB_ATTR_RO(cache_dma);
4705 #endif
4706
4707 static ssize_t destroy_by_rcu_show(struct kmem_cache *s, char *buf)
4708 {
4709         return sprintf(buf, "%d\n", !!(s->flags & SLAB_DESTROY_BY_RCU));
4710 }
4711 SLAB_ATTR_RO(destroy_by_rcu);
4712
4713 static ssize_t reserved_show(struct kmem_cache *s, char *buf)
4714 {
4715         return sprintf(buf, "%d\n", s->reserved);
4716 }
4717 SLAB_ATTR_RO(reserved);
4718
4719 #ifdef CONFIG_SLUB_DEBUG
4720 static ssize_t slabs_show(struct kmem_cache *s, char *buf)
4721 {
4722         return show_slab_objects(s, buf, SO_ALL);
4723 }
4724 SLAB_ATTR_RO(slabs);
4725
4726 static ssize_t total_objects_show(struct kmem_cache *s, char *buf)
4727 {
4728         return show_slab_objects(s, buf, SO_ALL|SO_TOTAL);
4729 }
4730 SLAB_ATTR_RO(total_objects);
4731
4732 static ssize_t sanity_checks_show(struct kmem_cache *s, char *buf)
4733 {
4734         return sprintf(buf, "%d\n", !!(s->flags & SLAB_DEBUG_FREE));
4735 }
4736
4737 static ssize_t sanity_checks_store(struct kmem_cache *s,
4738                                 const char *buf, size_t length)
4739 {
4740         s->flags &= ~SLAB_DEBUG_FREE;
4741         if (buf[0] == '1') {
4742                 s->flags &= ~__CMPXCHG_DOUBLE;
4743                 s->flags |= SLAB_DEBUG_FREE;
4744         }
4745         return length;
4746 }
4747 SLAB_ATTR(sanity_checks);
4748
4749 static ssize_t trace_show(struct kmem_cache *s, char *buf)
4750 {
4751         return sprintf(buf, "%d\n", !!(s->flags & SLAB_TRACE));
4752 }
4753
4754 static ssize_t trace_store(struct kmem_cache *s, const char *buf,
4755                                                         size_t length)
4756 {
4757         s->flags &= ~SLAB_TRACE;
4758         if (buf[0] == '1') {
4759                 s->flags &= ~__CMPXCHG_DOUBLE;
4760                 s->flags |= SLAB_TRACE;
4761         }
4762         return length;
4763 }
4764 SLAB_ATTR(trace);
4765
4766 static ssize_t red_zone_show(struct kmem_cache *s, char *buf)
4767 {
4768         return sprintf(buf, "%d\n", !!(s->flags & SLAB_RED_ZONE));
4769 }
4770
4771 static ssize_t red_zone_store(struct kmem_cache *s,
4772                                 const char *buf, size_t length)
4773 {
4774         if (any_slab_objects(s))
4775                 return -EBUSY;
4776
4777         s->flags &= ~SLAB_RED_ZONE;
4778         if (buf[0] == '1') {
4779                 s->flags &= ~__CMPXCHG_DOUBLE;
4780                 s->flags |= SLAB_RED_ZONE;
4781         }
4782         calculate_sizes(s, -1);
4783         return length;
4784 }
4785 SLAB_ATTR(red_zone);
4786
4787 static ssize_t poison_show(struct kmem_cache *s, char *buf)
4788 {
4789         return sprintf(buf, "%d\n", !!(s->flags & SLAB_POISON));
4790 }
4791
4792 static ssize_t poison_store(struct kmem_cache *s,
4793                                 const char *buf, size_t length)
4794 {
4795         if (any_slab_objects(s))
4796                 return -EBUSY;
4797
4798         s->flags &= ~SLAB_POISON;
4799         if (buf[0] == '1') {
4800                 s->flags &= ~__CMPXCHG_DOUBLE;
4801                 s->flags |= SLAB_POISON;
4802         }
4803         calculate_sizes(s, -1);
4804         return length;
4805 }
4806 SLAB_ATTR(poison);
4807
4808 static ssize_t store_user_show(struct kmem_cache *s, char *buf)
4809 {
4810         return sprintf(buf, "%d\n", !!(s->flags & SLAB_STORE_USER));
4811 }
4812
4813 static ssize_t store_user_store(struct kmem_cache *s,
4814                                 const char *buf, size_t length)
4815 {
4816         if (any_slab_objects(s))
4817                 return -EBUSY;
4818
4819         s->flags &= ~SLAB_STORE_USER;
4820         if (buf[0] == '1') {
4821                 s->flags &= ~__CMPXCHG_DOUBLE;
4822                 s->flags |= SLAB_STORE_USER;
4823         }
4824         calculate_sizes(s, -1);
4825         return length;
4826 }
4827 SLAB_ATTR(store_user);
4828
4829 static ssize_t validate_show(struct kmem_cache *s, char *buf)
4830 {
4831         return 0;
4832 }
4833
4834 static ssize_t validate_store(struct kmem_cache *s,
4835                         const char *buf, size_t length)
4836 {
4837         int ret = -EINVAL;
4838
4839         if (buf[0] == '1') {
4840                 ret = validate_slab_cache(s);
4841                 if (ret >= 0)
4842                         ret = length;
4843         }
4844         return ret;
4845 }
4846 SLAB_ATTR(validate);
4847
4848 static ssize_t alloc_calls_show(struct kmem_cache *s, char *buf)
4849 {
4850         if (!(s->flags & SLAB_STORE_USER))
4851                 return -ENOSYS;
4852         return list_locations(s, buf, TRACK_ALLOC);
4853 }
4854 SLAB_ATTR_RO(alloc_calls);
4855
4856 static ssize_t free_calls_show(struct kmem_cache *s, char *buf)
4857 {
4858         if (!(s->flags & SLAB_STORE_USER))
4859                 return -ENOSYS;
4860         return list_locations(s, buf, TRACK_FREE);
4861 }
4862 SLAB_ATTR_RO(free_calls);
4863 #endif /* CONFIG_SLUB_DEBUG */
4864
4865 #ifdef CONFIG_FAILSLAB
4866 static ssize_t failslab_show(struct kmem_cache *s, char *buf)
4867 {
4868         return sprintf(buf, "%d\n", !!(s->flags & SLAB_FAILSLAB));
4869 }
4870
4871 static ssize_t failslab_store(struct kmem_cache *s, const char *buf,
4872                                                         size_t length)
4873 {
4874         s->flags &= ~SLAB_FAILSLAB;
4875         if (buf[0] == '1')
4876                 s->flags |= SLAB_FAILSLAB;
4877         return length;
4878 }
4879 SLAB_ATTR(failslab);
4880 #endif
4881
4882 static ssize_t shrink_show(struct kmem_cache *s, char *buf)
4883 {
4884         return 0;
4885 }
4886
4887 static ssize_t shrink_store(struct kmem_cache *s,
4888                         const char *buf, size_t length)
4889 {
4890         if (buf[0] == '1') {
4891                 int rc = kmem_cache_shrink(s);
4892
4893                 if (rc)
4894                         return rc;
4895         } else
4896                 return -EINVAL;
4897         return length;
4898 }
4899 SLAB_ATTR(shrink);
4900
4901 #ifdef CONFIG_NUMA
4902 static ssize_t remote_node_defrag_ratio_show(struct kmem_cache *s, char *buf)
4903 {
4904         return sprintf(buf, "%d\n", s->remote_node_defrag_ratio / 10);
4905 }
4906
4907 static ssize_t remote_node_defrag_ratio_store(struct kmem_cache *s,
4908                                 const char *buf, size_t length)
4909 {
4910         unsigned long ratio;
4911         int err;
4912
4913         err = strict_strtoul(buf, 10, &ratio);
4914         if (err)
4915                 return err;
4916
4917         if (ratio <= 100)
4918                 s->remote_node_defrag_ratio = ratio * 10;
4919
4920         return length;
4921 }
4922 SLAB_ATTR(remote_node_defrag_ratio);
4923 #endif
4924
4925 #ifdef CONFIG_SLUB_STATS
4926 static int show_stat(struct kmem_cache *s, char *buf, enum stat_item si)
4927 {
4928         unsigned long sum  = 0;
4929         int cpu;
4930         int len;
4931         int *data = kmalloc(nr_cpu_ids * sizeof(int), GFP_KERNEL);
4932
4933         if (!data)
4934                 return -ENOMEM;
4935
4936         for_each_online_cpu(cpu) {
4937                 unsigned x = per_cpu_ptr(s->cpu_slab, cpu)->stat[si];
4938
4939                 data[cpu] = x;
4940                 sum += x;
4941         }
4942
4943         len = sprintf(buf, "%lu", sum);
4944
4945 #ifdef CONFIG_SMP
4946         for_each_online_cpu(cpu) {
4947                 if (data[cpu] && len < PAGE_SIZE - 20)
4948                         len += sprintf(buf + len, " C%d=%u", cpu, data[cpu]);
4949         }
4950 #endif
4951         kfree(data);
4952         return len + sprintf(buf + len, "\n");
4953 }
4954
4955 static void clear_stat(struct kmem_cache *s, enum stat_item si)
4956 {
4957         int cpu;
4958
4959         for_each_online_cpu(cpu)
4960                 per_cpu_ptr(s->cpu_slab, cpu)->stat[si] = 0;
4961 }
4962
4963 #define STAT_ATTR(si, text)                                     \
4964 static ssize_t text##_show(struct kmem_cache *s, char *buf)     \
4965 {                                                               \
4966         return show_stat(s, buf, si);                           \
4967 }                                                               \
4968 static ssize_t text##_store(struct kmem_cache *s,               \
4969                                 const char *buf, size_t length) \
4970 {                                                               \
4971         if (buf[0] != '0')                                      \
4972                 return -EINVAL;                                 \
4973         clear_stat(s, si);                                      \
4974         return length;                                          \
4975 }                                                               \
4976 SLAB_ATTR(text);                                                \
4977
4978 STAT_ATTR(ALLOC_FASTPATH, alloc_fastpath);
4979 STAT_ATTR(ALLOC_SLOWPATH, alloc_slowpath);
4980 STAT_ATTR(FREE_FASTPATH, free_fastpath);
4981 STAT_ATTR(FREE_SLOWPATH, free_slowpath);
4982 STAT_ATTR(FREE_FROZEN, free_frozen);
4983 STAT_ATTR(FREE_ADD_PARTIAL, free_add_partial);
4984 STAT_ATTR(FREE_REMOVE_PARTIAL, free_remove_partial);
4985 STAT_ATTR(ALLOC_FROM_PARTIAL, alloc_from_partial);
4986 STAT_ATTR(ALLOC_SLAB, alloc_slab);
4987 STAT_ATTR(ALLOC_REFILL, alloc_refill);
4988 STAT_ATTR(ALLOC_NODE_MISMATCH, alloc_node_mismatch);
4989 STAT_ATTR(FREE_SLAB, free_slab);
4990 STAT_ATTR(CPUSLAB_FLUSH, cpuslab_flush);
4991 STAT_ATTR(DEACTIVATE_FULL, deactivate_full);
4992 STAT_ATTR(DEACTIVATE_EMPTY, deactivate_empty);
4993 STAT_ATTR(DEACTIVATE_TO_HEAD, deactivate_to_head);
4994 STAT_ATTR(DEACTIVATE_TO_TAIL, deactivate_to_tail);
4995 STAT_ATTR(DEACTIVATE_REMOTE_FREES, deactivate_remote_frees);
4996 STAT_ATTR(DEACTIVATE_BYPASS, deactivate_bypass);
4997 STAT_ATTR(ORDER_FALLBACK, order_fallback);
4998 STAT_ATTR(CMPXCHG_DOUBLE_CPU_FAIL, cmpxchg_double_cpu_fail);
4999 STAT_ATTR(CMPXCHG_DOUBLE_FAIL, cmpxchg_double_fail);
5000 STAT_ATTR(CPU_PARTIAL_ALLOC, cpu_partial_alloc);
5001 STAT_ATTR(CPU_PARTIAL_FREE, cpu_partial_free);
5002 STAT_ATTR(CPU_PARTIAL_NODE, cpu_partial_node);
5003 STAT_ATTR(CPU_PARTIAL_DRAIN, cpu_partial_drain);
5004 #endif
5005
5006 static struct attribute *slab_attrs[] = {
5007         &slab_size_attr.attr,
5008         &object_size_attr.attr,
5009         &objs_per_slab_attr.attr,
5010         &order_attr.attr,
5011         &min_partial_attr.attr,
5012         &cpu_partial_attr.attr,
5013         &objects_attr.attr,
5014         &objects_partial_attr.attr,
5015         &partial_attr.attr,
5016         &cpu_slabs_attr.attr,
5017         &ctor_attr.attr,
5018         &aliases_attr.attr,
5019         &align_attr.attr,
5020         &hwcache_align_attr.attr,
5021         &reclaim_account_attr.attr,
5022         &destroy_by_rcu_attr.attr,
5023         &shrink_attr.attr,
5024         &reserved_attr.attr,
5025         &slabs_cpu_partial_attr.attr,
5026 #ifdef CONFIG_SLUB_DEBUG
5027         &total_objects_attr.attr,
5028         &slabs_attr.attr,
5029         &sanity_checks_attr.attr,
5030         &trace_attr.attr,
5031         &red_zone_attr.attr,
5032         &poison_attr.attr,
5033         &store_user_attr.attr,
5034         &validate_attr.attr,
5035         &alloc_calls_attr.attr,
5036         &free_calls_attr.attr,
5037 #endif
5038 #ifdef CONFIG_ZONE_DMA
5039         &cache_dma_attr.attr,
5040 #endif
5041 #ifdef CONFIG_NUMA
5042         &remote_node_defrag_ratio_attr.attr,
5043 #endif
5044 #ifdef CONFIG_SLUB_STATS
5045         &alloc_fastpath_attr.attr,
5046         &alloc_slowpath_attr.attr,
5047         &free_fastpath_attr.attr,
5048         &free_slowpath_attr.attr,
5049         &free_frozen_attr.attr,
5050         &free_add_partial_attr.attr,
5051         &free_remove_partial_attr.attr,
5052         &alloc_from_partial_attr.attr,
5053         &alloc_slab_attr.attr,
5054         &alloc_refill_attr.attr,
5055         &alloc_node_mismatch_attr.attr,
5056         &free_slab_attr.attr,
5057         &cpuslab_flush_attr.attr,
5058         &deactivate_full_attr.attr,
5059         &deactivate_empty_attr.attr,
5060         &deactivate_to_head_attr.attr,
5061         &deactivate_to_tail_attr.attr,
5062         &deactivate_remote_frees_attr.attr,
5063         &deactivate_bypass_attr.attr,
5064         &order_fallback_attr.attr,
5065         &cmpxchg_double_fail_attr.attr,
5066         &cmpxchg_double_cpu_fail_attr.attr,
5067         &cpu_partial_alloc_attr.attr,
5068         &cpu_partial_free_attr.attr,
5069         &cpu_partial_node_attr.attr,
5070         &cpu_partial_drain_attr.attr,
5071 #endif
5072 #ifdef CONFIG_FAILSLAB
5073         &failslab_attr.attr,
5074 #endif
5075
5076         NULL
5077 };
5078
5079 static struct attribute_group slab_attr_group = {
5080         .attrs = slab_attrs,
5081 };
5082
5083 static ssize_t slab_attr_show(struct kobject *kobj,
5084                                 struct attribute *attr,
5085                                 char *buf)
5086 {
5087         struct slab_attribute *attribute;
5088         struct kmem_cache *s;
5089         int err;
5090
5091         attribute = to_slab_attr(attr);
5092         s = to_slab(kobj);
5093
5094         if (!attribute->show)
5095                 return -EIO;
5096
5097         err = attribute->show(s, buf);
5098
5099         return err;
5100 }
5101
5102 static ssize_t slab_attr_store(struct kobject *kobj,
5103                                 struct attribute *attr,
5104                                 const char *buf, size_t len)
5105 {
5106         struct slab_attribute *attribute;
5107         struct kmem_cache *s;
5108         int err;
5109
5110         attribute = to_slab_attr(attr);
5111         s = to_slab(kobj);
5112
5113         if (!attribute->store)
5114                 return -EIO;
5115
5116         err = attribute->store(s, buf, len);
5117 #ifdef CONFIG_MEMCG_KMEM
5118         if (slab_state >= FULL && err >= 0 && is_root_cache(s)) {
5119                 int i;
5120
5121                 mutex_lock(&slab_mutex);
5122                 if (s->max_attr_size < len)
5123                         s->max_attr_size = len;
5124
5125                 /*
5126                  * This is a best effort propagation, so this function's return
5127                  * value will be determined by the parent cache only. This is
5128                  * basically because not all attributes will have a well
5129                  * defined semantics for rollbacks - most of the actions will
5130                  * have permanent effects.
5131                  *
5132                  * Returning the error value of any of the children that fail
5133                  * is not 100 % defined, in the sense that users seeing the
5134                  * error code won't be able to know anything about the state of
5135                  * the cache.
5136                  *
5137                  * Only returning the error code for the parent cache at least
5138                  * has well defined semantics. The cache being written to
5139                  * directly either failed or succeeded, in which case we loop
5140                  * through the descendants with best-effort propagation.
5141                  */
5142                 for_each_memcg_cache_index(i) {
5143                         struct kmem_cache *c = cache_from_memcg(s, i);
5144                         if (c)
5145                                 attribute->store(c, buf, len);
5146                 }
5147                 mutex_unlock(&slab_mutex);
5148         }
5149 #endif
5150         return err;
5151 }
5152
5153 static void memcg_propagate_slab_attrs(struct kmem_cache *s)
5154 {
5155 #ifdef CONFIG_MEMCG_KMEM
5156         int i;
5157         char *buffer = NULL;
5158
5159         if (!is_root_cache(s))
5160                 return;
5161
5162         /*
5163          * This mean this cache had no attribute written. Therefore, no point
5164          * in copying default values around
5165          */
5166         if (!s->max_attr_size)
5167                 return;
5168
5169         for (i = 0; i < ARRAY_SIZE(slab_attrs); i++) {
5170                 char mbuf[64];
5171                 char *buf;
5172                 struct slab_attribute *attr = to_slab_attr(slab_attrs[i]);
5173
5174                 if (!attr || !attr->store || !attr->show)
5175                         continue;
5176
5177                 /*
5178                  * It is really bad that we have to allocate here, so we will
5179                  * do it only as a fallback. If we actually allocate, though,
5180                  * we can just use the allocated buffer until the end.
5181                  *
5182                  * Most of the slub attributes will tend to be very small in
5183                  * size, but sysfs allows buffers up to a page, so they can
5184                  * theoretically happen.
5185                  */
5186                 if (buffer)
5187                         buf = buffer;
5188                 else if (s->max_attr_size < ARRAY_SIZE(mbuf))
5189                         buf = mbuf;
5190                 else {
5191                         buffer = (char *) get_zeroed_page(GFP_KERNEL);
5192                         if (WARN_ON(!buffer))
5193                                 continue;
5194                         buf = buffer;
5195                 }
5196
5197                 attr->show(s->memcg_params->root_cache, buf);
5198                 attr->store(s, buf, strlen(buf));
5199         }
5200
5201         if (buffer)
5202                 free_page((unsigned long)buffer);
5203 #endif
5204 }
5205
5206 static const struct sysfs_ops slab_sysfs_ops = {
5207         .show = slab_attr_show,
5208         .store = slab_attr_store,
5209 };
5210
5211 static struct kobj_type slab_ktype = {
5212         .sysfs_ops = &slab_sysfs_ops,
5213 };
5214
5215 static int uevent_filter(struct kset *kset, struct kobject *kobj)
5216 {
5217         struct kobj_type *ktype = get_ktype(kobj);
5218
5219         if (ktype == &slab_ktype)
5220                 return 1;
5221         return 0;
5222 }
5223
5224 static const struct kset_uevent_ops slab_uevent_ops = {
5225         .filter = uevent_filter,
5226 };
5227
5228 static struct kset *slab_kset;
5229
5230 #define ID_STR_LENGTH 64
5231
5232 /* Create a unique string id for a slab cache:
5233  *
5234  * Format       :[flags-]size
5235  */
5236 static char *create_unique_id(struct kmem_cache *s)
5237 {
5238         char *name = kmalloc(ID_STR_LENGTH, GFP_KERNEL);
5239         char *p = name;
5240
5241         BUG_ON(!name);
5242
5243         *p++ = ':';
5244         /*
5245          * First flags affecting slabcache operations. We will only
5246          * get here for aliasable slabs so we do not need to support
5247          * too many flags. The flags here must cover all flags that
5248          * are matched during merging to guarantee that the id is
5249          * unique.
5250          */
5251         if (s->flags & SLAB_CACHE_DMA)
5252                 *p++ = 'd';
5253         if (s->flags & SLAB_RECLAIM_ACCOUNT)
5254                 *p++ = 'a';
5255         if (s->flags & SLAB_DEBUG_FREE)
5256                 *p++ = 'F';
5257         if (!(s->flags & SLAB_NOTRACK))
5258                 *p++ = 't';
5259         if (p != name + 1)
5260                 *p++ = '-';
5261         p += sprintf(p, "%07d", s->size);
5262
5263 #ifdef CONFIG_MEMCG_KMEM
5264         if (!is_root_cache(s))
5265                 p += sprintf(p, "-%08d", memcg_cache_id(s->memcg_params->memcg));
5266 #endif
5267
5268         BUG_ON(p > name + ID_STR_LENGTH - 1);
5269         return name;
5270 }
5271
5272 static int sysfs_slab_add(struct kmem_cache *s)
5273 {
5274         int err;
5275         const char *name;
5276         int unmergeable = slab_unmergeable(s);
5277
5278         if (unmergeable) {
5279                 /*
5280                  * Slabcache can never be merged so we can use the name proper.
5281                  * This is typically the case for debug situations. In that
5282                  * case we can catch duplicate names easily.
5283                  */
5284                 sysfs_remove_link(&slab_kset->kobj, s->name);
5285                 name = s->name;
5286         } else {
5287                 /*
5288                  * Create a unique name for the slab as a target
5289                  * for the symlinks.
5290                  */
5291                 name = create_unique_id(s);
5292         }
5293
5294         s->kobj.kset = slab_kset;
5295         err = kobject_init_and_add(&s->kobj, &slab_ktype, NULL, name);
5296         if (err) {
5297                 kobject_put(&s->kobj);
5298                 return err;
5299         }
5300
5301         err = sysfs_create_group(&s->kobj, &slab_attr_group);
5302         if (err) {
5303                 kobject_del(&s->kobj);
5304                 kobject_put(&s->kobj);
5305                 return err;
5306         }
5307         kobject_uevent(&s->kobj, KOBJ_ADD);
5308         if (!unmergeable) {
5309                 /* Setup first alias */
5310                 sysfs_slab_alias(s, s->name);
5311                 kfree(name);
5312         }
5313         return 0;
5314 }
5315
5316 static void sysfs_slab_remove(struct kmem_cache *s)
5317 {
5318         if (slab_state < FULL)
5319                 /*
5320                  * Sysfs has not been setup yet so no need to remove the
5321                  * cache from sysfs.
5322                  */
5323                 return;
5324
5325         kobject_uevent(&s->kobj, KOBJ_REMOVE);
5326         kobject_del(&s->kobj);
5327         kobject_put(&s->kobj);
5328 }
5329
5330 /*
5331  * Need to buffer aliases during bootup until sysfs becomes
5332  * available lest we lose that information.
5333  */
5334 struct saved_alias {
5335         struct kmem_cache *s;
5336         const char *name;
5337         struct saved_alias *next;
5338 };
5339
5340 static struct saved_alias *alias_list;
5341
5342 static int sysfs_slab_alias(struct kmem_cache *s, const char *name)
5343 {
5344         struct saved_alias *al;
5345
5346         if (slab_state == FULL) {
5347                 /*
5348                  * If we have a leftover link then remove it.
5349                  */
5350                 sysfs_remove_link(&slab_kset->kobj, name);
5351                 return sysfs_create_link(&slab_kset->kobj, &s->kobj, name);
5352         }
5353
5354         al = kmalloc(sizeof(struct saved_alias), GFP_KERNEL);
5355         if (!al)
5356                 return -ENOMEM;
5357
5358         al->s = s;
5359         al->name = name;
5360         al->next = alias_list;
5361         alias_list = al;
5362         return 0;
5363 }
5364
5365 static int __init slab_sysfs_init(void)
5366 {
5367         struct kmem_cache *s;
5368         int err;
5369
5370         mutex_lock(&slab_mutex);
5371
5372         slab_kset = kset_create_and_add("slab", &slab_uevent_ops, kernel_kobj);
5373         if (!slab_kset) {
5374                 mutex_unlock(&slab_mutex);
5375                 printk(KERN_ERR "Cannot register slab subsystem.\n");
5376                 return -ENOSYS;
5377         }
5378
5379         slab_state = FULL;
5380
5381         list_for_each_entry(s, &slab_caches, list) {
5382                 err = sysfs_slab_add(s);
5383                 if (err)
5384                         printk(KERN_ERR "SLUB: Unable to add boot slab %s"
5385                                                 " to sysfs\n", s->name);
5386         }
5387
5388         while (alias_list) {
5389                 struct saved_alias *al = alias_list;
5390
5391                 alias_list = alias_list->next;
5392                 err = sysfs_slab_alias(al->s, al->name);
5393                 if (err)
5394                         printk(KERN_ERR "SLUB: Unable to add boot slab alias"
5395                                         " %s to sysfs\n", al->name);
5396                 kfree(al);
5397         }
5398
5399         mutex_unlock(&slab_mutex);
5400         resiliency_test();
5401         return 0;
5402 }
5403
5404 __initcall(slab_sysfs_init);
5405 #endif /* CONFIG_SYSFS */
5406
5407 /*
5408  * The /proc/slabinfo ABI
5409  */
5410 #ifdef CONFIG_SLABINFO
5411 void get_slabinfo(struct kmem_cache *s, struct slabinfo *sinfo)
5412 {
5413         unsigned long nr_partials = 0;
5414         unsigned long nr_slabs = 0;
5415         unsigned long nr_objs = 0;
5416         unsigned long nr_free = 0;
5417         int node;
5418
5419         for_each_online_node(node) {
5420                 struct kmem_cache_node *n = get_node(s, node);
5421
5422                 if (!n)
5423                         continue;
5424
5425                 nr_partials += n->nr_partial;
5426                 nr_slabs += atomic_long_read(&n->nr_slabs);
5427                 nr_objs += atomic_long_read(&n->total_objects);
5428                 nr_free += count_partial(n, count_free);
5429         }
5430
5431         sinfo->active_objs = nr_objs - nr_free;
5432         sinfo->num_objs = nr_objs;
5433         sinfo->active_slabs = nr_slabs;
5434         sinfo->num_slabs = nr_slabs;
5435         sinfo->objects_per_slab = oo_objects(s->oo);
5436         sinfo->cache_order = oo_order(s->oo);
5437 }
5438
5439 void slabinfo_show_stats(struct seq_file *m, struct kmem_cache *s)
5440 {
5441 }
5442
5443 ssize_t slabinfo_write(struct file *file, const char __user *buffer,
5444                        size_t count, loff_t *ppos)
5445 {
5446         return -EIO;
5447 }
5448 #endif /* CONFIG_SLABINFO */