]> git.openfabrics.org - ~shefty/rdma-dev.git/blob - mm/slab.c
2acfa0d9094379ae999c1937dd9d4ed475af1837
[~shefty/rdma-dev.git] / mm / slab.c
1 /*
2  * linux/mm/slab.c
3  * Written by Mark Hemment, 1996/97.
4  * (markhe@nextd.demon.co.uk)
5  *
6  * kmem_cache_destroy() + some cleanup - 1999 Andrea Arcangeli
7  *
8  * Major cleanup, different bufctl logic, per-cpu arrays
9  *      (c) 2000 Manfred Spraul
10  *
11  * Cleanup, make the head arrays unconditional, preparation for NUMA
12  *      (c) 2002 Manfred Spraul
13  *
14  * An implementation of the Slab Allocator as described in outline in;
15  *      UNIX Internals: The New Frontiers by Uresh Vahalia
16  *      Pub: Prentice Hall      ISBN 0-13-101908-2
17  * or with a little more detail in;
18  *      The Slab Allocator: An Object-Caching Kernel Memory Allocator
19  *      Jeff Bonwick (Sun Microsystems).
20  *      Presented at: USENIX Summer 1994 Technical Conference
21  *
22  * The memory is organized in caches, one cache for each object type.
23  * (e.g. inode_cache, dentry_cache, buffer_head, vm_area_struct)
24  * Each cache consists out of many slabs (they are small (usually one
25  * page long) and always contiguous), and each slab contains multiple
26  * initialized objects.
27  *
28  * This means, that your constructor is used only for newly allocated
29  * slabs and you must pass objects with the same initializations to
30  * kmem_cache_free.
31  *
32  * Each cache can only support one memory type (GFP_DMA, GFP_HIGHMEM,
33  * normal). If you need a special memory type, then must create a new
34  * cache for that memory type.
35  *
36  * In order to reduce fragmentation, the slabs are sorted in 3 groups:
37  *   full slabs with 0 free objects
38  *   partial slabs
39  *   empty slabs with no allocated objects
40  *
41  * If partial slabs exist, then new allocations come from these slabs,
42  * otherwise from empty slabs or new slabs are allocated.
43  *
44  * kmem_cache_destroy() CAN CRASH if you try to allocate from the cache
45  * during kmem_cache_destroy(). The caller must prevent concurrent allocs.
46  *
47  * Each cache has a short per-cpu head array, most allocs
48  * and frees go into that array, and if that array overflows, then 1/2
49  * of the entries in the array are given back into the global cache.
50  * The head array is strictly LIFO and should improve the cache hit rates.
51  * On SMP, it additionally reduces the spinlock operations.
52  *
53  * The c_cpuarray may not be read with enabled local interrupts -
54  * it's changed with a smp_call_function().
55  *
56  * SMP synchronization:
57  *  constructors and destructors are called without any locking.
58  *  Several members in struct kmem_cache and struct slab never change, they
59  *      are accessed without any locking.
60  *  The per-cpu arrays are never accessed from the wrong cpu, no locking,
61  *      and local interrupts are disabled so slab code is preempt-safe.
62  *  The non-constant members are protected with a per-cache irq spinlock.
63  *
64  * Many thanks to Mark Hemment, who wrote another per-cpu slab patch
65  * in 2000 - many ideas in the current implementation are derived from
66  * his patch.
67  *
68  * Further notes from the original documentation:
69  *
70  * 11 April '97.  Started multi-threading - markhe
71  *      The global cache-chain is protected by the mutex 'cache_chain_mutex'.
72  *      The sem is only needed when accessing/extending the cache-chain, which
73  *      can never happen inside an interrupt (kmem_cache_create(),
74  *      kmem_cache_shrink() and kmem_cache_reap()).
75  *
76  *      At present, each engine can be growing a cache.  This should be blocked.
77  *
78  * 15 March 2005. NUMA slab allocator.
79  *      Shai Fultheim <shai@scalex86.org>.
80  *      Shobhit Dayal <shobhit@calsoftinc.com>
81  *      Alok N Kataria <alokk@calsoftinc.com>
82  *      Christoph Lameter <christoph@lameter.com>
83  *
84  *      Modified the slab allocator to be node aware on NUMA systems.
85  *      Each node has its own list of partial, free and full slabs.
86  *      All object allocations for a node occur from node specific slab lists.
87  */
88
89 #include        <linux/slab.h>
90 #include        <linux/mm.h>
91 #include        <linux/poison.h>
92 #include        <linux/swap.h>
93 #include        <linux/cache.h>
94 #include        <linux/interrupt.h>
95 #include        <linux/init.h>
96 #include        <linux/compiler.h>
97 #include        <linux/cpuset.h>
98 #include        <linux/proc_fs.h>
99 #include        <linux/seq_file.h>
100 #include        <linux/notifier.h>
101 #include        <linux/kallsyms.h>
102 #include        <linux/cpu.h>
103 #include        <linux/sysctl.h>
104 #include        <linux/module.h>
105 #include        <linux/rcupdate.h>
106 #include        <linux/string.h>
107 #include        <linux/uaccess.h>
108 #include        <linux/nodemask.h>
109 #include        <linux/kmemleak.h>
110 #include        <linux/mempolicy.h>
111 #include        <linux/mutex.h>
112 #include        <linux/fault-inject.h>
113 #include        <linux/rtmutex.h>
114 #include        <linux/reciprocal_div.h>
115 #include        <linux/debugobjects.h>
116 #include        <linux/kmemcheck.h>
117 #include        <linux/memory.h>
118 #include        <linux/prefetch.h>
119
120 #include        <asm/cacheflush.h>
121 #include        <asm/tlbflush.h>
122 #include        <asm/page.h>
123
124 #include <trace/events/kmem.h>
125
126 /*
127  * DEBUG        - 1 for kmem_cache_create() to honour; SLAB_RED_ZONE & SLAB_POISON.
128  *                0 for faster, smaller code (especially in the critical paths).
129  *
130  * STATS        - 1 to collect stats for /proc/slabinfo.
131  *                0 for faster, smaller code (especially in the critical paths).
132  *
133  * FORCED_DEBUG - 1 enables SLAB_RED_ZONE and SLAB_POISON (if possible)
134  */
135
136 #ifdef CONFIG_DEBUG_SLAB
137 #define DEBUG           1
138 #define STATS           1
139 #define FORCED_DEBUG    1
140 #else
141 #define DEBUG           0
142 #define STATS           0
143 #define FORCED_DEBUG    0
144 #endif
145
146 /* Shouldn't this be in a header file somewhere? */
147 #define BYTES_PER_WORD          sizeof(void *)
148 #define REDZONE_ALIGN           max(BYTES_PER_WORD, __alignof__(unsigned long long))
149
150 #ifndef ARCH_KMALLOC_FLAGS
151 #define ARCH_KMALLOC_FLAGS SLAB_HWCACHE_ALIGN
152 #endif
153
154 /* Legal flag mask for kmem_cache_create(). */
155 #if DEBUG
156 # define CREATE_MASK    (SLAB_RED_ZONE | \
157                          SLAB_POISON | SLAB_HWCACHE_ALIGN | \
158                          SLAB_CACHE_DMA | \
159                          SLAB_STORE_USER | \
160                          SLAB_RECLAIM_ACCOUNT | SLAB_PANIC | \
161                          SLAB_DESTROY_BY_RCU | SLAB_MEM_SPREAD | \
162                          SLAB_DEBUG_OBJECTS | SLAB_NOLEAKTRACE | SLAB_NOTRACK)
163 #else
164 # define CREATE_MASK    (SLAB_HWCACHE_ALIGN | \
165                          SLAB_CACHE_DMA | \
166                          SLAB_RECLAIM_ACCOUNT | SLAB_PANIC | \
167                          SLAB_DESTROY_BY_RCU | SLAB_MEM_SPREAD | \
168                          SLAB_DEBUG_OBJECTS | SLAB_NOLEAKTRACE | SLAB_NOTRACK)
169 #endif
170
171 /*
172  * kmem_bufctl_t:
173  *
174  * Bufctl's are used for linking objs within a slab
175  * linked offsets.
176  *
177  * This implementation relies on "struct page" for locating the cache &
178  * slab an object belongs to.
179  * This allows the bufctl structure to be small (one int), but limits
180  * the number of objects a slab (not a cache) can contain when off-slab
181  * bufctls are used. The limit is the size of the largest general cache
182  * that does not use off-slab slabs.
183  * For 32bit archs with 4 kB pages, is this 56.
184  * This is not serious, as it is only for large objects, when it is unwise
185  * to have too many per slab.
186  * Note: This limit can be raised by introducing a general cache whose size
187  * is less than 512 (PAGE_SIZE<<3), but greater than 256.
188  */
189
190 typedef unsigned int kmem_bufctl_t;
191 #define BUFCTL_END      (((kmem_bufctl_t)(~0U))-0)
192 #define BUFCTL_FREE     (((kmem_bufctl_t)(~0U))-1)
193 #define BUFCTL_ACTIVE   (((kmem_bufctl_t)(~0U))-2)
194 #define SLAB_LIMIT      (((kmem_bufctl_t)(~0U))-3)
195
196 /*
197  * struct slab_rcu
198  *
199  * slab_destroy on a SLAB_DESTROY_BY_RCU cache uses this structure to
200  * arrange for kmem_freepages to be called via RCU.  This is useful if
201  * we need to approach a kernel structure obliquely, from its address
202  * obtained without the usual locking.  We can lock the structure to
203  * stabilize it and check it's still at the given address, only if we
204  * can be sure that the memory has not been meanwhile reused for some
205  * other kind of object (which our subsystem's lock might corrupt).
206  *
207  * rcu_read_lock before reading the address, then rcu_read_unlock after
208  * taking the spinlock within the structure expected at that address.
209  */
210 struct slab_rcu {
211         struct rcu_head head;
212         struct kmem_cache *cachep;
213         void *addr;
214 };
215
216 /*
217  * struct slab
218  *
219  * Manages the objs in a slab. Placed either at the beginning of mem allocated
220  * for a slab, or allocated from an general cache.
221  * Slabs are chained into three list: fully used, partial, fully free slabs.
222  */
223 struct slab {
224         union {
225                 struct {
226                         struct list_head list;
227                         unsigned long colouroff;
228                         void *s_mem;            /* including colour offset */
229                         unsigned int inuse;     /* num of objs active in slab */
230                         kmem_bufctl_t free;
231                         unsigned short nodeid;
232                 };
233                 struct slab_rcu __slab_cover_slab_rcu;
234         };
235 };
236
237 /*
238  * struct array_cache
239  *
240  * Purpose:
241  * - LIFO ordering, to hand out cache-warm objects from _alloc
242  * - reduce the number of linked list operations
243  * - reduce spinlock operations
244  *
245  * The limit is stored in the per-cpu structure to reduce the data cache
246  * footprint.
247  *
248  */
249 struct array_cache {
250         unsigned int avail;
251         unsigned int limit;
252         unsigned int batchcount;
253         unsigned int touched;
254         spinlock_t lock;
255         void *entry[];  /*
256                          * Must have this definition in here for the proper
257                          * alignment of array_cache. Also simplifies accessing
258                          * the entries.
259                          */
260 };
261
262 /*
263  * bootstrap: The caches do not work without cpuarrays anymore, but the
264  * cpuarrays are allocated from the generic caches...
265  */
266 #define BOOT_CPUCACHE_ENTRIES   1
267 struct arraycache_init {
268         struct array_cache cache;
269         void *entries[BOOT_CPUCACHE_ENTRIES];
270 };
271
272 /*
273  * The slab lists for all objects.
274  */
275 struct kmem_list3 {
276         struct list_head slabs_partial; /* partial list first, better asm code */
277         struct list_head slabs_full;
278         struct list_head slabs_free;
279         unsigned long free_objects;
280         unsigned int free_limit;
281         unsigned int colour_next;       /* Per-node cache coloring */
282         spinlock_t list_lock;
283         struct array_cache *shared;     /* shared per node */
284         struct array_cache **alien;     /* on other nodes */
285         unsigned long next_reap;        /* updated without locking */
286         int free_touched;               /* updated without locking */
287 };
288
289 /*
290  * Need this for bootstrapping a per node allocator.
291  */
292 #define NUM_INIT_LISTS (3 * MAX_NUMNODES)
293 static struct kmem_list3 __initdata initkmem_list3[NUM_INIT_LISTS];
294 #define CACHE_CACHE 0
295 #define SIZE_AC MAX_NUMNODES
296 #define SIZE_L3 (2 * MAX_NUMNODES)
297
298 static int drain_freelist(struct kmem_cache *cache,
299                         struct kmem_list3 *l3, int tofree);
300 static void free_block(struct kmem_cache *cachep, void **objpp, int len,
301                         int node);
302 static int enable_cpucache(struct kmem_cache *cachep, gfp_t gfp);
303 static void cache_reap(struct work_struct *unused);
304
305 /*
306  * This function must be completely optimized away if a constant is passed to
307  * it.  Mostly the same as what is in linux/slab.h except it returns an index.
308  */
309 static __always_inline int index_of(const size_t size)
310 {
311         extern void __bad_size(void);
312
313         if (__builtin_constant_p(size)) {
314                 int i = 0;
315
316 #define CACHE(x) \
317         if (size <=x) \
318                 return i; \
319         else \
320                 i++;
321 #include <linux/kmalloc_sizes.h>
322 #undef CACHE
323                 __bad_size();
324         } else
325                 __bad_size();
326         return 0;
327 }
328
329 static int slab_early_init = 1;
330
331 #define INDEX_AC index_of(sizeof(struct arraycache_init))
332 #define INDEX_L3 index_of(sizeof(struct kmem_list3))
333
334 static void kmem_list3_init(struct kmem_list3 *parent)
335 {
336         INIT_LIST_HEAD(&parent->slabs_full);
337         INIT_LIST_HEAD(&parent->slabs_partial);
338         INIT_LIST_HEAD(&parent->slabs_free);
339         parent->shared = NULL;
340         parent->alien = NULL;
341         parent->colour_next = 0;
342         spin_lock_init(&parent->list_lock);
343         parent->free_objects = 0;
344         parent->free_touched = 0;
345 }
346
347 #define MAKE_LIST(cachep, listp, slab, nodeid)                          \
348         do {                                                            \
349                 INIT_LIST_HEAD(listp);                                  \
350                 list_splice(&(cachep->nodelists[nodeid]->slab), listp); \
351         } while (0)
352
353 #define MAKE_ALL_LISTS(cachep, ptr, nodeid)                             \
354         do {                                                            \
355         MAKE_LIST((cachep), (&(ptr)->slabs_full), slabs_full, nodeid);  \
356         MAKE_LIST((cachep), (&(ptr)->slabs_partial), slabs_partial, nodeid); \
357         MAKE_LIST((cachep), (&(ptr)->slabs_free), slabs_free, nodeid);  \
358         } while (0)
359
360 #define CFLGS_OFF_SLAB          (0x80000000UL)
361 #define OFF_SLAB(x)     ((x)->flags & CFLGS_OFF_SLAB)
362
363 #define BATCHREFILL_LIMIT       16
364 /*
365  * Optimization question: fewer reaps means less probability for unnessary
366  * cpucache drain/refill cycles.
367  *
368  * OTOH the cpuarrays can contain lots of objects,
369  * which could lock up otherwise freeable slabs.
370  */
371 #define REAPTIMEOUT_CPUC        (2*HZ)
372 #define REAPTIMEOUT_LIST3       (4*HZ)
373
374 #if STATS
375 #define STATS_INC_ACTIVE(x)     ((x)->num_active++)
376 #define STATS_DEC_ACTIVE(x)     ((x)->num_active--)
377 #define STATS_INC_ALLOCED(x)    ((x)->num_allocations++)
378 #define STATS_INC_GROWN(x)      ((x)->grown++)
379 #define STATS_ADD_REAPED(x,y)   ((x)->reaped += (y))
380 #define STATS_SET_HIGH(x)                                               \
381         do {                                                            \
382                 if ((x)->num_active > (x)->high_mark)                   \
383                         (x)->high_mark = (x)->num_active;               \
384         } while (0)
385 #define STATS_INC_ERR(x)        ((x)->errors++)
386 #define STATS_INC_NODEALLOCS(x) ((x)->node_allocs++)
387 #define STATS_INC_NODEFREES(x)  ((x)->node_frees++)
388 #define STATS_INC_ACOVERFLOW(x)   ((x)->node_overflow++)
389 #define STATS_SET_FREEABLE(x, i)                                        \
390         do {                                                            \
391                 if ((x)->max_freeable < i)                              \
392                         (x)->max_freeable = i;                          \
393         } while (0)
394 #define STATS_INC_ALLOCHIT(x)   atomic_inc(&(x)->allochit)
395 #define STATS_INC_ALLOCMISS(x)  atomic_inc(&(x)->allocmiss)
396 #define STATS_INC_FREEHIT(x)    atomic_inc(&(x)->freehit)
397 #define STATS_INC_FREEMISS(x)   atomic_inc(&(x)->freemiss)
398 #else
399 #define STATS_INC_ACTIVE(x)     do { } while (0)
400 #define STATS_DEC_ACTIVE(x)     do { } while (0)
401 #define STATS_INC_ALLOCED(x)    do { } while (0)
402 #define STATS_INC_GROWN(x)      do { } while (0)
403 #define STATS_ADD_REAPED(x,y)   do { (void)(y); } while (0)
404 #define STATS_SET_HIGH(x)       do { } while (0)
405 #define STATS_INC_ERR(x)        do { } while (0)
406 #define STATS_INC_NODEALLOCS(x) do { } while (0)
407 #define STATS_INC_NODEFREES(x)  do { } while (0)
408 #define STATS_INC_ACOVERFLOW(x)   do { } while (0)
409 #define STATS_SET_FREEABLE(x, i) do { } while (0)
410 #define STATS_INC_ALLOCHIT(x)   do { } while (0)
411 #define STATS_INC_ALLOCMISS(x)  do { } while (0)
412 #define STATS_INC_FREEHIT(x)    do { } while (0)
413 #define STATS_INC_FREEMISS(x)   do { } while (0)
414 #endif
415
416 #if DEBUG
417
418 /*
419  * memory layout of objects:
420  * 0            : objp
421  * 0 .. cachep->obj_offset - BYTES_PER_WORD - 1: padding. This ensures that
422  *              the end of an object is aligned with the end of the real
423  *              allocation. Catches writes behind the end of the allocation.
424  * cachep->obj_offset - BYTES_PER_WORD .. cachep->obj_offset - 1:
425  *              redzone word.
426  * cachep->obj_offset: The real object.
427  * cachep->buffer_size - 2* BYTES_PER_WORD: redzone word [BYTES_PER_WORD long]
428  * cachep->buffer_size - 1* BYTES_PER_WORD: last caller address
429  *                                      [BYTES_PER_WORD long]
430  */
431 static int obj_offset(struct kmem_cache *cachep)
432 {
433         return cachep->obj_offset;
434 }
435
436 static int obj_size(struct kmem_cache *cachep)
437 {
438         return cachep->obj_size;
439 }
440
441 static unsigned long long *dbg_redzone1(struct kmem_cache *cachep, void *objp)
442 {
443         BUG_ON(!(cachep->flags & SLAB_RED_ZONE));
444         return (unsigned long long*) (objp + obj_offset(cachep) -
445                                       sizeof(unsigned long long));
446 }
447
448 static unsigned long long *dbg_redzone2(struct kmem_cache *cachep, void *objp)
449 {
450         BUG_ON(!(cachep->flags & SLAB_RED_ZONE));
451         if (cachep->flags & SLAB_STORE_USER)
452                 return (unsigned long long *)(objp + cachep->buffer_size -
453                                               sizeof(unsigned long long) -
454                                               REDZONE_ALIGN);
455         return (unsigned long long *) (objp + cachep->buffer_size -
456                                        sizeof(unsigned long long));
457 }
458
459 static void **dbg_userword(struct kmem_cache *cachep, void *objp)
460 {
461         BUG_ON(!(cachep->flags & SLAB_STORE_USER));
462         return (void **)(objp + cachep->buffer_size - BYTES_PER_WORD);
463 }
464
465 #else
466
467 #define obj_offset(x)                   0
468 #define obj_size(cachep)                (cachep->buffer_size)
469 #define dbg_redzone1(cachep, objp)      ({BUG(); (unsigned long long *)NULL;})
470 #define dbg_redzone2(cachep, objp)      ({BUG(); (unsigned long long *)NULL;})
471 #define dbg_userword(cachep, objp)      ({BUG(); (void **)NULL;})
472
473 #endif
474
475 #ifdef CONFIG_TRACING
476 size_t slab_buffer_size(struct kmem_cache *cachep)
477 {
478         return cachep->buffer_size;
479 }
480 EXPORT_SYMBOL(slab_buffer_size);
481 #endif
482
483 /*
484  * Do not go above this order unless 0 objects fit into the slab.
485  */
486 #define BREAK_GFP_ORDER_HI      1
487 #define BREAK_GFP_ORDER_LO      0
488 static int slab_break_gfp_order = BREAK_GFP_ORDER_LO;
489
490 /*
491  * Functions for storing/retrieving the cachep and or slab from the page
492  * allocator.  These are used to find the slab an obj belongs to.  With kfree(),
493  * these are used to find the cache which an obj belongs to.
494  */
495 static inline void page_set_cache(struct page *page, struct kmem_cache *cache)
496 {
497         page->lru.next = (struct list_head *)cache;
498 }
499
500 static inline struct kmem_cache *page_get_cache(struct page *page)
501 {
502         page = compound_head(page);
503         BUG_ON(!PageSlab(page));
504         return (struct kmem_cache *)page->lru.next;
505 }
506
507 static inline void page_set_slab(struct page *page, struct slab *slab)
508 {
509         page->lru.prev = (struct list_head *)slab;
510 }
511
512 static inline struct slab *page_get_slab(struct page *page)
513 {
514         BUG_ON(!PageSlab(page));
515         return (struct slab *)page->lru.prev;
516 }
517
518 static inline struct kmem_cache *virt_to_cache(const void *obj)
519 {
520         struct page *page = virt_to_head_page(obj);
521         return page_get_cache(page);
522 }
523
524 static inline struct slab *virt_to_slab(const void *obj)
525 {
526         struct page *page = virt_to_head_page(obj);
527         return page_get_slab(page);
528 }
529
530 static inline void *index_to_obj(struct kmem_cache *cache, struct slab *slab,
531                                  unsigned int idx)
532 {
533         return slab->s_mem + cache->buffer_size * idx;
534 }
535
536 /*
537  * We want to avoid an expensive divide : (offset / cache->buffer_size)
538  *   Using the fact that buffer_size is a constant for a particular cache,
539  *   we can replace (offset / cache->buffer_size) by
540  *   reciprocal_divide(offset, cache->reciprocal_buffer_size)
541  */
542 static inline unsigned int obj_to_index(const struct kmem_cache *cache,
543                                         const struct slab *slab, void *obj)
544 {
545         u32 offset = (obj - slab->s_mem);
546         return reciprocal_divide(offset, cache->reciprocal_buffer_size);
547 }
548
549 /*
550  * These are the default caches for kmalloc. Custom caches can have other sizes.
551  */
552 struct cache_sizes malloc_sizes[] = {
553 #define CACHE(x) { .cs_size = (x) },
554 #include <linux/kmalloc_sizes.h>
555         CACHE(ULONG_MAX)
556 #undef CACHE
557 };
558 EXPORT_SYMBOL(malloc_sizes);
559
560 /* Must match cache_sizes above. Out of line to keep cache footprint low. */
561 struct cache_names {
562         char *name;
563         char *name_dma;
564 };
565
566 static struct cache_names __initdata cache_names[] = {
567 #define CACHE(x) { .name = "size-" #x, .name_dma = "size-" #x "(DMA)" },
568 #include <linux/kmalloc_sizes.h>
569         {NULL,}
570 #undef CACHE
571 };
572
573 static struct arraycache_init initarray_cache __initdata =
574     { {0, BOOT_CPUCACHE_ENTRIES, 1, 0} };
575 static struct arraycache_init initarray_generic =
576     { {0, BOOT_CPUCACHE_ENTRIES, 1, 0} };
577
578 /* internal cache of cache description objs */
579 static struct kmem_list3 *cache_cache_nodelists[MAX_NUMNODES];
580 static struct kmem_cache cache_cache = {
581         .nodelists = cache_cache_nodelists,
582         .batchcount = 1,
583         .limit = BOOT_CPUCACHE_ENTRIES,
584         .shared = 1,
585         .buffer_size = sizeof(struct kmem_cache),
586         .name = "kmem_cache",
587 };
588
589 #define BAD_ALIEN_MAGIC 0x01020304ul
590
591 /*
592  * chicken and egg problem: delay the per-cpu array allocation
593  * until the general caches are up.
594  */
595 static enum {
596         NONE,
597         PARTIAL_AC,
598         PARTIAL_L3,
599         EARLY,
600         LATE,
601         FULL
602 } g_cpucache_up;
603
604 /*
605  * used by boot code to determine if it can use slab based allocator
606  */
607 int slab_is_available(void)
608 {
609         return g_cpucache_up >= EARLY;
610 }
611
612 #ifdef CONFIG_LOCKDEP
613
614 /*
615  * Slab sometimes uses the kmalloc slabs to store the slab headers
616  * for other slabs "off slab".
617  * The locking for this is tricky in that it nests within the locks
618  * of all other slabs in a few places; to deal with this special
619  * locking we put on-slab caches into a separate lock-class.
620  *
621  * We set lock class for alien array caches which are up during init.
622  * The lock annotation will be lost if all cpus of a node goes down and
623  * then comes back up during hotplug
624  */
625 static struct lock_class_key on_slab_l3_key;
626 static struct lock_class_key on_slab_alc_key;
627
628 static struct lock_class_key debugobj_l3_key;
629 static struct lock_class_key debugobj_alc_key;
630
631 static void slab_set_lock_classes(struct kmem_cache *cachep,
632                 struct lock_class_key *l3_key, struct lock_class_key *alc_key,
633                 int q)
634 {
635         struct array_cache **alc;
636         struct kmem_list3 *l3;
637         int r;
638
639         l3 = cachep->nodelists[q];
640         if (!l3)
641                 return;
642
643         lockdep_set_class(&l3->list_lock, l3_key);
644         alc = l3->alien;
645         /*
646          * FIXME: This check for BAD_ALIEN_MAGIC
647          * should go away when common slab code is taught to
648          * work even without alien caches.
649          * Currently, non NUMA code returns BAD_ALIEN_MAGIC
650          * for alloc_alien_cache,
651          */
652         if (!alc || (unsigned long)alc == BAD_ALIEN_MAGIC)
653                 return;
654         for_each_node(r) {
655                 if (alc[r])
656                         lockdep_set_class(&alc[r]->lock, alc_key);
657         }
658 }
659
660 static void slab_set_debugobj_lock_classes_node(struct kmem_cache *cachep, int node)
661 {
662         slab_set_lock_classes(cachep, &debugobj_l3_key, &debugobj_alc_key, node);
663 }
664
665 static void slab_set_debugobj_lock_classes(struct kmem_cache *cachep)
666 {
667         int node;
668
669         for_each_online_node(node)
670                 slab_set_debugobj_lock_classes_node(cachep, node);
671 }
672
673 static void init_node_lock_keys(int q)
674 {
675         struct cache_sizes *s = malloc_sizes;
676
677         if (g_cpucache_up < LATE)
678                 return;
679
680         for (s = malloc_sizes; s->cs_size != ULONG_MAX; s++) {
681                 struct kmem_list3 *l3;
682
683                 l3 = s->cs_cachep->nodelists[q];
684                 if (!l3 || OFF_SLAB(s->cs_cachep))
685                         continue;
686
687                 slab_set_lock_classes(s->cs_cachep, &on_slab_l3_key,
688                                 &on_slab_alc_key, q);
689         }
690 }
691
692 static inline void init_lock_keys(void)
693 {
694         int node;
695
696         for_each_node(node)
697                 init_node_lock_keys(node);
698 }
699 #else
700 static void init_node_lock_keys(int q)
701 {
702 }
703
704 static inline void init_lock_keys(void)
705 {
706 }
707
708 static void slab_set_debugobj_lock_classes_node(struct kmem_cache *cachep, int node)
709 {
710 }
711
712 static void slab_set_debugobj_lock_classes(struct kmem_cache *cachep)
713 {
714 }
715 #endif
716
717 /*
718  * Guard access to the cache-chain.
719  */
720 static DEFINE_MUTEX(cache_chain_mutex);
721 static struct list_head cache_chain;
722
723 static DEFINE_PER_CPU(struct delayed_work, slab_reap_work);
724
725 static inline struct array_cache *cpu_cache_get(struct kmem_cache *cachep)
726 {
727         return cachep->array[smp_processor_id()];
728 }
729
730 static inline struct kmem_cache *__find_general_cachep(size_t size,
731                                                         gfp_t gfpflags)
732 {
733         struct cache_sizes *csizep = malloc_sizes;
734
735 #if DEBUG
736         /* This happens if someone tries to call
737          * kmem_cache_create(), or __kmalloc(), before
738          * the generic caches are initialized.
739          */
740         BUG_ON(malloc_sizes[INDEX_AC].cs_cachep == NULL);
741 #endif
742         if (!size)
743                 return ZERO_SIZE_PTR;
744
745         while (size > csizep->cs_size)
746                 csizep++;
747
748         /*
749          * Really subtle: The last entry with cs->cs_size==ULONG_MAX
750          * has cs_{dma,}cachep==NULL. Thus no special case
751          * for large kmalloc calls required.
752          */
753 #ifdef CONFIG_ZONE_DMA
754         if (unlikely(gfpflags & GFP_DMA))
755                 return csizep->cs_dmacachep;
756 #endif
757         return csizep->cs_cachep;
758 }
759
760 static struct kmem_cache *kmem_find_general_cachep(size_t size, gfp_t gfpflags)
761 {
762         return __find_general_cachep(size, gfpflags);
763 }
764
765 static size_t slab_mgmt_size(size_t nr_objs, size_t align)
766 {
767         return ALIGN(sizeof(struct slab)+nr_objs*sizeof(kmem_bufctl_t), align);
768 }
769
770 /*
771  * Calculate the number of objects and left-over bytes for a given buffer size.
772  */
773 static void cache_estimate(unsigned long gfporder, size_t buffer_size,
774                            size_t align, int flags, size_t *left_over,
775                            unsigned int *num)
776 {
777         int nr_objs;
778         size_t mgmt_size;
779         size_t slab_size = PAGE_SIZE << gfporder;
780
781         /*
782          * The slab management structure can be either off the slab or
783          * on it. For the latter case, the memory allocated for a
784          * slab is used for:
785          *
786          * - The struct slab
787          * - One kmem_bufctl_t for each object
788          * - Padding to respect alignment of @align
789          * - @buffer_size bytes for each object
790          *
791          * If the slab management structure is off the slab, then the
792          * alignment will already be calculated into the size. Because
793          * the slabs are all pages aligned, the objects will be at the
794          * correct alignment when allocated.
795          */
796         if (flags & CFLGS_OFF_SLAB) {
797                 mgmt_size = 0;
798                 nr_objs = slab_size / buffer_size;
799
800                 if (nr_objs > SLAB_LIMIT)
801                         nr_objs = SLAB_LIMIT;
802         } else {
803                 /*
804                  * Ignore padding for the initial guess. The padding
805                  * is at most @align-1 bytes, and @buffer_size is at
806                  * least @align. In the worst case, this result will
807                  * be one greater than the number of objects that fit
808                  * into the memory allocation when taking the padding
809                  * into account.
810                  */
811                 nr_objs = (slab_size - sizeof(struct slab)) /
812                           (buffer_size + sizeof(kmem_bufctl_t));
813
814                 /*
815                  * This calculated number will be either the right
816                  * amount, or one greater than what we want.
817                  */
818                 if (slab_mgmt_size(nr_objs, align) + nr_objs*buffer_size
819                        > slab_size)
820                         nr_objs--;
821
822                 if (nr_objs > SLAB_LIMIT)
823                         nr_objs = SLAB_LIMIT;
824
825                 mgmt_size = slab_mgmt_size(nr_objs, align);
826         }
827         *num = nr_objs;
828         *left_over = slab_size - nr_objs*buffer_size - mgmt_size;
829 }
830
831 #define slab_error(cachep, msg) __slab_error(__func__, cachep, msg)
832
833 static void __slab_error(const char *function, struct kmem_cache *cachep,
834                         char *msg)
835 {
836         printk(KERN_ERR "slab error in %s(): cache `%s': %s\n",
837                function, cachep->name, msg);
838         dump_stack();
839 }
840
841 /*
842  * By default on NUMA we use alien caches to stage the freeing of
843  * objects allocated from other nodes. This causes massive memory
844  * inefficiencies when using fake NUMA setup to split memory into a
845  * large number of small nodes, so it can be disabled on the command
846  * line
847   */
848
849 static int use_alien_caches __read_mostly = 1;
850 static int __init noaliencache_setup(char *s)
851 {
852         use_alien_caches = 0;
853         return 1;
854 }
855 __setup("noaliencache", noaliencache_setup);
856
857 #ifdef CONFIG_NUMA
858 /*
859  * Special reaping functions for NUMA systems called from cache_reap().
860  * These take care of doing round robin flushing of alien caches (containing
861  * objects freed on different nodes from which they were allocated) and the
862  * flushing of remote pcps by calling drain_node_pages.
863  */
864 static DEFINE_PER_CPU(unsigned long, slab_reap_node);
865
866 static void init_reap_node(int cpu)
867 {
868         int node;
869
870         node = next_node(cpu_to_mem(cpu), node_online_map);
871         if (node == MAX_NUMNODES)
872                 node = first_node(node_online_map);
873
874         per_cpu(slab_reap_node, cpu) = node;
875 }
876
877 static void next_reap_node(void)
878 {
879         int node = __this_cpu_read(slab_reap_node);
880
881         node = next_node(node, node_online_map);
882         if (unlikely(node >= MAX_NUMNODES))
883                 node = first_node(node_online_map);
884         __this_cpu_write(slab_reap_node, node);
885 }
886
887 #else
888 #define init_reap_node(cpu) do { } while (0)
889 #define next_reap_node(void) do { } while (0)
890 #endif
891
892 /*
893  * Initiate the reap timer running on the target CPU.  We run at around 1 to 2Hz
894  * via the workqueue/eventd.
895  * Add the CPU number into the expiration time to minimize the possibility of
896  * the CPUs getting into lockstep and contending for the global cache chain
897  * lock.
898  */
899 static void __cpuinit start_cpu_timer(int cpu)
900 {
901         struct delayed_work *reap_work = &per_cpu(slab_reap_work, cpu);
902
903         /*
904          * When this gets called from do_initcalls via cpucache_init(),
905          * init_workqueues() has already run, so keventd will be setup
906          * at that time.
907          */
908         if (keventd_up() && reap_work->work.func == NULL) {
909                 init_reap_node(cpu);
910                 INIT_DELAYED_WORK_DEFERRABLE(reap_work, cache_reap);
911                 schedule_delayed_work_on(cpu, reap_work,
912                                         __round_jiffies_relative(HZ, cpu));
913         }
914 }
915
916 static struct array_cache *alloc_arraycache(int node, int entries,
917                                             int batchcount, gfp_t gfp)
918 {
919         int memsize = sizeof(void *) * entries + sizeof(struct array_cache);
920         struct array_cache *nc = NULL;
921
922         nc = kmalloc_node(memsize, gfp, node);
923         /*
924          * The array_cache structures contain pointers to free object.
925          * However, when such objects are allocated or transferred to another
926          * cache the pointers are not cleared and they could be counted as
927          * valid references during a kmemleak scan. Therefore, kmemleak must
928          * not scan such objects.
929          */
930         kmemleak_no_scan(nc);
931         if (nc) {
932                 nc->avail = 0;
933                 nc->limit = entries;
934                 nc->batchcount = batchcount;
935                 nc->touched = 0;
936                 spin_lock_init(&nc->lock);
937         }
938         return nc;
939 }
940
941 /*
942  * Transfer objects in one arraycache to another.
943  * Locking must be handled by the caller.
944  *
945  * Return the number of entries transferred.
946  */
947 static int transfer_objects(struct array_cache *to,
948                 struct array_cache *from, unsigned int max)
949 {
950         /* Figure out how many entries to transfer */
951         int nr = min3(from->avail, max, to->limit - to->avail);
952
953         if (!nr)
954                 return 0;
955
956         memcpy(to->entry + to->avail, from->entry + from->avail -nr,
957                         sizeof(void *) *nr);
958
959         from->avail -= nr;
960         to->avail += nr;
961         return nr;
962 }
963
964 #ifndef CONFIG_NUMA
965
966 #define drain_alien_cache(cachep, alien) do { } while (0)
967 #define reap_alien(cachep, l3) do { } while (0)
968
969 static inline struct array_cache **alloc_alien_cache(int node, int limit, gfp_t gfp)
970 {
971         return (struct array_cache **)BAD_ALIEN_MAGIC;
972 }
973
974 static inline void free_alien_cache(struct array_cache **ac_ptr)
975 {
976 }
977
978 static inline int cache_free_alien(struct kmem_cache *cachep, void *objp)
979 {
980         return 0;
981 }
982
983 static inline void *alternate_node_alloc(struct kmem_cache *cachep,
984                 gfp_t flags)
985 {
986         return NULL;
987 }
988
989 static inline void *____cache_alloc_node(struct kmem_cache *cachep,
990                  gfp_t flags, int nodeid)
991 {
992         return NULL;
993 }
994
995 #else   /* CONFIG_NUMA */
996
997 static void *____cache_alloc_node(struct kmem_cache *, gfp_t, int);
998 static void *alternate_node_alloc(struct kmem_cache *, gfp_t);
999
1000 static struct array_cache **alloc_alien_cache(int node, int limit, gfp_t gfp)
1001 {
1002         struct array_cache **ac_ptr;
1003         int memsize = sizeof(void *) * nr_node_ids;
1004         int i;
1005
1006         if (limit > 1)
1007                 limit = 12;
1008         ac_ptr = kzalloc_node(memsize, gfp, node);
1009         if (ac_ptr) {
1010                 for_each_node(i) {
1011                         if (i == node || !node_online(i))
1012                                 continue;
1013                         ac_ptr[i] = alloc_arraycache(node, limit, 0xbaadf00d, gfp);
1014                         if (!ac_ptr[i]) {
1015                                 for (i--; i >= 0; i--)
1016                                         kfree(ac_ptr[i]);
1017                                 kfree(ac_ptr);
1018                                 return NULL;
1019                         }
1020                 }
1021         }
1022         return ac_ptr;
1023 }
1024
1025 static void free_alien_cache(struct array_cache **ac_ptr)
1026 {
1027         int i;
1028
1029         if (!ac_ptr)
1030                 return;
1031         for_each_node(i)
1032             kfree(ac_ptr[i]);
1033         kfree(ac_ptr);
1034 }
1035
1036 static void __drain_alien_cache(struct kmem_cache *cachep,
1037                                 struct array_cache *ac, int node)
1038 {
1039         struct kmem_list3 *rl3 = cachep->nodelists[node];
1040
1041         if (ac->avail) {
1042                 spin_lock(&rl3->list_lock);
1043                 /*
1044                  * Stuff objects into the remote nodes shared array first.
1045                  * That way we could avoid the overhead of putting the objects
1046                  * into the free lists and getting them back later.
1047                  */
1048                 if (rl3->shared)
1049                         transfer_objects(rl3->shared, ac, ac->limit);
1050
1051                 free_block(cachep, ac->entry, ac->avail, node);
1052                 ac->avail = 0;
1053                 spin_unlock(&rl3->list_lock);
1054         }
1055 }
1056
1057 /*
1058  * Called from cache_reap() to regularly drain alien caches round robin.
1059  */
1060 static void reap_alien(struct kmem_cache *cachep, struct kmem_list3 *l3)
1061 {
1062         int node = __this_cpu_read(slab_reap_node);
1063
1064         if (l3->alien) {
1065                 struct array_cache *ac = l3->alien[node];
1066
1067                 if (ac && ac->avail && spin_trylock_irq(&ac->lock)) {
1068                         __drain_alien_cache(cachep, ac, node);
1069                         spin_unlock_irq(&ac->lock);
1070                 }
1071         }
1072 }
1073
1074 static void drain_alien_cache(struct kmem_cache *cachep,
1075                                 struct array_cache **alien)
1076 {
1077         int i = 0;
1078         struct array_cache *ac;
1079         unsigned long flags;
1080
1081         for_each_online_node(i) {
1082                 ac = alien[i];
1083                 if (ac) {
1084                         spin_lock_irqsave(&ac->lock, flags);
1085                         __drain_alien_cache(cachep, ac, i);
1086                         spin_unlock_irqrestore(&ac->lock, flags);
1087                 }
1088         }
1089 }
1090
1091 static inline int cache_free_alien(struct kmem_cache *cachep, void *objp)
1092 {
1093         struct slab *slabp = virt_to_slab(objp);
1094         int nodeid = slabp->nodeid;
1095         struct kmem_list3 *l3;
1096         struct array_cache *alien = NULL;
1097         int node;
1098
1099         node = numa_mem_id();
1100
1101         /*
1102          * Make sure we are not freeing a object from another node to the array
1103          * cache on this cpu.
1104          */
1105         if (likely(slabp->nodeid == node))
1106                 return 0;
1107
1108         l3 = cachep->nodelists[node];
1109         STATS_INC_NODEFREES(cachep);
1110         if (l3->alien && l3->alien[nodeid]) {
1111                 alien = l3->alien[nodeid];
1112                 spin_lock(&alien->lock);
1113                 if (unlikely(alien->avail == alien->limit)) {
1114                         STATS_INC_ACOVERFLOW(cachep);
1115                         __drain_alien_cache(cachep, alien, nodeid);
1116                 }
1117                 alien->entry[alien->avail++] = objp;
1118                 spin_unlock(&alien->lock);
1119         } else {
1120                 spin_lock(&(cachep->nodelists[nodeid])->list_lock);
1121                 free_block(cachep, &objp, 1, nodeid);
1122                 spin_unlock(&(cachep->nodelists[nodeid])->list_lock);
1123         }
1124         return 1;
1125 }
1126 #endif
1127
1128 /*
1129  * Allocates and initializes nodelists for a node on each slab cache, used for
1130  * either memory or cpu hotplug.  If memory is being hot-added, the kmem_list3
1131  * will be allocated off-node since memory is not yet online for the new node.
1132  * When hotplugging memory or a cpu, existing nodelists are not replaced if
1133  * already in use.
1134  *
1135  * Must hold cache_chain_mutex.
1136  */
1137 static int init_cache_nodelists_node(int node)
1138 {
1139         struct kmem_cache *cachep;
1140         struct kmem_list3 *l3;
1141         const int memsize = sizeof(struct kmem_list3);
1142
1143         list_for_each_entry(cachep, &cache_chain, next) {
1144                 /*
1145                  * Set up the size64 kmemlist for cpu before we can
1146                  * begin anything. Make sure some other cpu on this
1147                  * node has not already allocated this
1148                  */
1149                 if (!cachep->nodelists[node]) {
1150                         l3 = kmalloc_node(memsize, GFP_KERNEL, node);
1151                         if (!l3)
1152                                 return -ENOMEM;
1153                         kmem_list3_init(l3);
1154                         l3->next_reap = jiffies + REAPTIMEOUT_LIST3 +
1155                             ((unsigned long)cachep) % REAPTIMEOUT_LIST3;
1156
1157                         /*
1158                          * The l3s don't come and go as CPUs come and
1159                          * go.  cache_chain_mutex is sufficient
1160                          * protection here.
1161                          */
1162                         cachep->nodelists[node] = l3;
1163                 }
1164
1165                 spin_lock_irq(&cachep->nodelists[node]->list_lock);
1166                 cachep->nodelists[node]->free_limit =
1167                         (1 + nr_cpus_node(node)) *
1168                         cachep->batchcount + cachep->num;
1169                 spin_unlock_irq(&cachep->nodelists[node]->list_lock);
1170         }
1171         return 0;
1172 }
1173
1174 static void __cpuinit cpuup_canceled(long cpu)
1175 {
1176         struct kmem_cache *cachep;
1177         struct kmem_list3 *l3 = NULL;
1178         int node = cpu_to_mem(cpu);
1179         const struct cpumask *mask = cpumask_of_node(node);
1180
1181         list_for_each_entry(cachep, &cache_chain, next) {
1182                 struct array_cache *nc;
1183                 struct array_cache *shared;
1184                 struct array_cache **alien;
1185
1186                 /* cpu is dead; no one can alloc from it. */
1187                 nc = cachep->array[cpu];
1188                 cachep->array[cpu] = NULL;
1189                 l3 = cachep->nodelists[node];
1190
1191                 if (!l3)
1192                         goto free_array_cache;
1193
1194                 spin_lock_irq(&l3->list_lock);
1195
1196                 /* Free limit for this kmem_list3 */
1197                 l3->free_limit -= cachep->batchcount;
1198                 if (nc)
1199                         free_block(cachep, nc->entry, nc->avail, node);
1200
1201                 if (!cpumask_empty(mask)) {
1202                         spin_unlock_irq(&l3->list_lock);
1203                         goto free_array_cache;
1204                 }
1205
1206                 shared = l3->shared;
1207                 if (shared) {
1208                         free_block(cachep, shared->entry,
1209                                    shared->avail, node);
1210                         l3->shared = NULL;
1211                 }
1212
1213                 alien = l3->alien;
1214                 l3->alien = NULL;
1215
1216                 spin_unlock_irq(&l3->list_lock);
1217
1218                 kfree(shared);
1219                 if (alien) {
1220                         drain_alien_cache(cachep, alien);
1221                         free_alien_cache(alien);
1222                 }
1223 free_array_cache:
1224                 kfree(nc);
1225         }
1226         /*
1227          * In the previous loop, all the objects were freed to
1228          * the respective cache's slabs,  now we can go ahead and
1229          * shrink each nodelist to its limit.
1230          */
1231         list_for_each_entry(cachep, &cache_chain, next) {
1232                 l3 = cachep->nodelists[node];
1233                 if (!l3)
1234                         continue;
1235                 drain_freelist(cachep, l3, l3->free_objects);
1236         }
1237 }
1238
1239 static int __cpuinit cpuup_prepare(long cpu)
1240 {
1241         struct kmem_cache *cachep;
1242         struct kmem_list3 *l3 = NULL;
1243         int node = cpu_to_mem(cpu);
1244         int err;
1245
1246         /*
1247          * We need to do this right in the beginning since
1248          * alloc_arraycache's are going to use this list.
1249          * kmalloc_node allows us to add the slab to the right
1250          * kmem_list3 and not this cpu's kmem_list3
1251          */
1252         err = init_cache_nodelists_node(node);
1253         if (err < 0)
1254                 goto bad;
1255
1256         /*
1257          * Now we can go ahead with allocating the shared arrays and
1258          * array caches
1259          */
1260         list_for_each_entry(cachep, &cache_chain, next) {
1261                 struct array_cache *nc;
1262                 struct array_cache *shared = NULL;
1263                 struct array_cache **alien = NULL;
1264
1265                 nc = alloc_arraycache(node, cachep->limit,
1266                                         cachep->batchcount, GFP_KERNEL);
1267                 if (!nc)
1268                         goto bad;
1269                 if (cachep->shared) {
1270                         shared = alloc_arraycache(node,
1271                                 cachep->shared * cachep->batchcount,
1272                                 0xbaadf00d, GFP_KERNEL);
1273                         if (!shared) {
1274                                 kfree(nc);
1275                                 goto bad;
1276                         }
1277                 }
1278                 if (use_alien_caches) {
1279                         alien = alloc_alien_cache(node, cachep->limit, GFP_KERNEL);
1280                         if (!alien) {
1281                                 kfree(shared);
1282                                 kfree(nc);
1283                                 goto bad;
1284                         }
1285                 }
1286                 cachep->array[cpu] = nc;
1287                 l3 = cachep->nodelists[node];
1288                 BUG_ON(!l3);
1289
1290                 spin_lock_irq(&l3->list_lock);
1291                 if (!l3->shared) {
1292                         /*
1293                          * We are serialised from CPU_DEAD or
1294                          * CPU_UP_CANCELLED by the cpucontrol lock
1295                          */
1296                         l3->shared = shared;
1297                         shared = NULL;
1298                 }
1299 #ifdef CONFIG_NUMA
1300                 if (!l3->alien) {
1301                         l3->alien = alien;
1302                         alien = NULL;
1303                 }
1304 #endif
1305                 spin_unlock_irq(&l3->list_lock);
1306                 kfree(shared);
1307                 free_alien_cache(alien);
1308                 if (cachep->flags & SLAB_DEBUG_OBJECTS)
1309                         slab_set_debugobj_lock_classes_node(cachep, node);
1310         }
1311         init_node_lock_keys(node);
1312
1313         return 0;
1314 bad:
1315         cpuup_canceled(cpu);
1316         return -ENOMEM;
1317 }
1318
1319 static int __cpuinit cpuup_callback(struct notifier_block *nfb,
1320                                     unsigned long action, void *hcpu)
1321 {
1322         long cpu = (long)hcpu;
1323         int err = 0;
1324
1325         switch (action) {
1326         case CPU_UP_PREPARE:
1327         case CPU_UP_PREPARE_FROZEN:
1328                 mutex_lock(&cache_chain_mutex);
1329                 err = cpuup_prepare(cpu);
1330                 mutex_unlock(&cache_chain_mutex);
1331                 break;
1332         case CPU_ONLINE:
1333         case CPU_ONLINE_FROZEN:
1334                 start_cpu_timer(cpu);
1335                 break;
1336 #ifdef CONFIG_HOTPLUG_CPU
1337         case CPU_DOWN_PREPARE:
1338         case CPU_DOWN_PREPARE_FROZEN:
1339                 /*
1340                  * Shutdown cache reaper. Note that the cache_chain_mutex is
1341                  * held so that if cache_reap() is invoked it cannot do
1342                  * anything expensive but will only modify reap_work
1343                  * and reschedule the timer.
1344                 */
1345                 cancel_delayed_work_sync(&per_cpu(slab_reap_work, cpu));
1346                 /* Now the cache_reaper is guaranteed to be not running. */
1347                 per_cpu(slab_reap_work, cpu).work.func = NULL;
1348                 break;
1349         case CPU_DOWN_FAILED:
1350         case CPU_DOWN_FAILED_FROZEN:
1351                 start_cpu_timer(cpu);
1352                 break;
1353         case CPU_DEAD:
1354         case CPU_DEAD_FROZEN:
1355                 /*
1356                  * Even if all the cpus of a node are down, we don't free the
1357                  * kmem_list3 of any cache. This to avoid a race between
1358                  * cpu_down, and a kmalloc allocation from another cpu for
1359                  * memory from the node of the cpu going down.  The list3
1360                  * structure is usually allocated from kmem_cache_create() and
1361                  * gets destroyed at kmem_cache_destroy().
1362                  */
1363                 /* fall through */
1364 #endif
1365         case CPU_UP_CANCELED:
1366         case CPU_UP_CANCELED_FROZEN:
1367                 mutex_lock(&cache_chain_mutex);
1368                 cpuup_canceled(cpu);
1369                 mutex_unlock(&cache_chain_mutex);
1370                 break;
1371         }
1372         return notifier_from_errno(err);
1373 }
1374
1375 static struct notifier_block __cpuinitdata cpucache_notifier = {
1376         &cpuup_callback, NULL, 0
1377 };
1378
1379 #if defined(CONFIG_NUMA) && defined(CONFIG_MEMORY_HOTPLUG)
1380 /*
1381  * Drains freelist for a node on each slab cache, used for memory hot-remove.
1382  * Returns -EBUSY if all objects cannot be drained so that the node is not
1383  * removed.
1384  *
1385  * Must hold cache_chain_mutex.
1386  */
1387 static int __meminit drain_cache_nodelists_node(int node)
1388 {
1389         struct kmem_cache *cachep;
1390         int ret = 0;
1391
1392         list_for_each_entry(cachep, &cache_chain, next) {
1393                 struct kmem_list3 *l3;
1394
1395                 l3 = cachep->nodelists[node];
1396                 if (!l3)
1397                         continue;
1398
1399                 drain_freelist(cachep, l3, l3->free_objects);
1400
1401                 if (!list_empty(&l3->slabs_full) ||
1402                     !list_empty(&l3->slabs_partial)) {
1403                         ret = -EBUSY;
1404                         break;
1405                 }
1406         }
1407         return ret;
1408 }
1409
1410 static int __meminit slab_memory_callback(struct notifier_block *self,
1411                                         unsigned long action, void *arg)
1412 {
1413         struct memory_notify *mnb = arg;
1414         int ret = 0;
1415         int nid;
1416
1417         nid = mnb->status_change_nid;
1418         if (nid < 0)
1419                 goto out;
1420
1421         switch (action) {
1422         case MEM_GOING_ONLINE:
1423                 mutex_lock(&cache_chain_mutex);
1424                 ret = init_cache_nodelists_node(nid);
1425                 mutex_unlock(&cache_chain_mutex);
1426                 break;
1427         case MEM_GOING_OFFLINE:
1428                 mutex_lock(&cache_chain_mutex);
1429                 ret = drain_cache_nodelists_node(nid);
1430                 mutex_unlock(&cache_chain_mutex);
1431                 break;
1432         case MEM_ONLINE:
1433         case MEM_OFFLINE:
1434         case MEM_CANCEL_ONLINE:
1435         case MEM_CANCEL_OFFLINE:
1436                 break;
1437         }
1438 out:
1439         return notifier_from_errno(ret);
1440 }
1441 #endif /* CONFIG_NUMA && CONFIG_MEMORY_HOTPLUG */
1442
1443 /*
1444  * swap the static kmem_list3 with kmalloced memory
1445  */
1446 static void __init init_list(struct kmem_cache *cachep, struct kmem_list3 *list,
1447                                 int nodeid)
1448 {
1449         struct kmem_list3 *ptr;
1450
1451         ptr = kmalloc_node(sizeof(struct kmem_list3), GFP_NOWAIT, nodeid);
1452         BUG_ON(!ptr);
1453
1454         memcpy(ptr, list, sizeof(struct kmem_list3));
1455         /*
1456          * Do not assume that spinlocks can be initialized via memcpy:
1457          */
1458         spin_lock_init(&ptr->list_lock);
1459
1460         MAKE_ALL_LISTS(cachep, ptr, nodeid);
1461         cachep->nodelists[nodeid] = ptr;
1462 }
1463
1464 /*
1465  * For setting up all the kmem_list3s for cache whose buffer_size is same as
1466  * size of kmem_list3.
1467  */
1468 static void __init set_up_list3s(struct kmem_cache *cachep, int index)
1469 {
1470         int node;
1471
1472         for_each_online_node(node) {
1473                 cachep->nodelists[node] = &initkmem_list3[index + node];
1474                 cachep->nodelists[node]->next_reap = jiffies +
1475                     REAPTIMEOUT_LIST3 +
1476                     ((unsigned long)cachep) % REAPTIMEOUT_LIST3;
1477         }
1478 }
1479
1480 /*
1481  * Initialisation.  Called after the page allocator have been initialised and
1482  * before smp_init().
1483  */
1484 void __init kmem_cache_init(void)
1485 {
1486         size_t left_over;
1487         struct cache_sizes *sizes;
1488         struct cache_names *names;
1489         int i;
1490         int order;
1491         int node;
1492
1493         if (num_possible_nodes() == 1)
1494                 use_alien_caches = 0;
1495
1496         for (i = 0; i < NUM_INIT_LISTS; i++) {
1497                 kmem_list3_init(&initkmem_list3[i]);
1498                 if (i < MAX_NUMNODES)
1499                         cache_cache.nodelists[i] = NULL;
1500         }
1501         set_up_list3s(&cache_cache, CACHE_CACHE);
1502
1503         /*
1504          * Fragmentation resistance on low memory - only use bigger
1505          * page orders on machines with more than 32MB of memory.
1506          */
1507         if (totalram_pages > (32 << 20) >> PAGE_SHIFT)
1508                 slab_break_gfp_order = BREAK_GFP_ORDER_HI;
1509
1510         /* Bootstrap is tricky, because several objects are allocated
1511          * from caches that do not exist yet:
1512          * 1) initialize the cache_cache cache: it contains the struct
1513          *    kmem_cache structures of all caches, except cache_cache itself:
1514          *    cache_cache is statically allocated.
1515          *    Initially an __init data area is used for the head array and the
1516          *    kmem_list3 structures, it's replaced with a kmalloc allocated
1517          *    array at the end of the bootstrap.
1518          * 2) Create the first kmalloc cache.
1519          *    The struct kmem_cache for the new cache is allocated normally.
1520          *    An __init data area is used for the head array.
1521          * 3) Create the remaining kmalloc caches, with minimally sized
1522          *    head arrays.
1523          * 4) Replace the __init data head arrays for cache_cache and the first
1524          *    kmalloc cache with kmalloc allocated arrays.
1525          * 5) Replace the __init data for kmem_list3 for cache_cache and
1526          *    the other cache's with kmalloc allocated memory.
1527          * 6) Resize the head arrays of the kmalloc caches to their final sizes.
1528          */
1529
1530         node = numa_mem_id();
1531
1532         /* 1) create the cache_cache */
1533         INIT_LIST_HEAD(&cache_chain);
1534         list_add(&cache_cache.next, &cache_chain);
1535         cache_cache.colour_off = cache_line_size();
1536         cache_cache.array[smp_processor_id()] = &initarray_cache.cache;
1537         cache_cache.nodelists[node] = &initkmem_list3[CACHE_CACHE + node];
1538
1539         /*
1540          * struct kmem_cache size depends on nr_node_ids & nr_cpu_ids
1541          */
1542         cache_cache.buffer_size = offsetof(struct kmem_cache, array[nr_cpu_ids]) +
1543                                   nr_node_ids * sizeof(struct kmem_list3 *);
1544 #if DEBUG
1545         cache_cache.obj_size = cache_cache.buffer_size;
1546 #endif
1547         cache_cache.buffer_size = ALIGN(cache_cache.buffer_size,
1548                                         cache_line_size());
1549         cache_cache.reciprocal_buffer_size =
1550                 reciprocal_value(cache_cache.buffer_size);
1551
1552         for (order = 0; order < MAX_ORDER; order++) {
1553                 cache_estimate(order, cache_cache.buffer_size,
1554                         cache_line_size(), 0, &left_over, &cache_cache.num);
1555                 if (cache_cache.num)
1556                         break;
1557         }
1558         BUG_ON(!cache_cache.num);
1559         cache_cache.gfporder = order;
1560         cache_cache.colour = left_over / cache_cache.colour_off;
1561         cache_cache.slab_size = ALIGN(cache_cache.num * sizeof(kmem_bufctl_t) +
1562                                       sizeof(struct slab), cache_line_size());
1563
1564         /* 2+3) create the kmalloc caches */
1565         sizes = malloc_sizes;
1566         names = cache_names;
1567
1568         /*
1569          * Initialize the caches that provide memory for the array cache and the
1570          * kmem_list3 structures first.  Without this, further allocations will
1571          * bug.
1572          */
1573
1574         sizes[INDEX_AC].cs_cachep = kmem_cache_create(names[INDEX_AC].name,
1575                                         sizes[INDEX_AC].cs_size,
1576                                         ARCH_KMALLOC_MINALIGN,
1577                                         ARCH_KMALLOC_FLAGS|SLAB_PANIC,
1578                                         NULL);
1579
1580         if (INDEX_AC != INDEX_L3) {
1581                 sizes[INDEX_L3].cs_cachep =
1582                         kmem_cache_create(names[INDEX_L3].name,
1583                                 sizes[INDEX_L3].cs_size,
1584                                 ARCH_KMALLOC_MINALIGN,
1585                                 ARCH_KMALLOC_FLAGS|SLAB_PANIC,
1586                                 NULL);
1587         }
1588
1589         slab_early_init = 0;
1590
1591         while (sizes->cs_size != ULONG_MAX) {
1592                 /*
1593                  * For performance, all the general caches are L1 aligned.
1594                  * This should be particularly beneficial on SMP boxes, as it
1595                  * eliminates "false sharing".
1596                  * Note for systems short on memory removing the alignment will
1597                  * allow tighter packing of the smaller caches.
1598                  */
1599                 if (!sizes->cs_cachep) {
1600                         sizes->cs_cachep = kmem_cache_create(names->name,
1601                                         sizes->cs_size,
1602                                         ARCH_KMALLOC_MINALIGN,
1603                                         ARCH_KMALLOC_FLAGS|SLAB_PANIC,
1604                                         NULL);
1605                 }
1606 #ifdef CONFIG_ZONE_DMA
1607                 sizes->cs_dmacachep = kmem_cache_create(
1608                                         names->name_dma,
1609                                         sizes->cs_size,
1610                                         ARCH_KMALLOC_MINALIGN,
1611                                         ARCH_KMALLOC_FLAGS|SLAB_CACHE_DMA|
1612                                                 SLAB_PANIC,
1613                                         NULL);
1614 #endif
1615                 sizes++;
1616                 names++;
1617         }
1618         /* 4) Replace the bootstrap head arrays */
1619         {
1620                 struct array_cache *ptr;
1621
1622                 ptr = kmalloc(sizeof(struct arraycache_init), GFP_NOWAIT);
1623
1624                 BUG_ON(cpu_cache_get(&cache_cache) != &initarray_cache.cache);
1625                 memcpy(ptr, cpu_cache_get(&cache_cache),
1626                        sizeof(struct arraycache_init));
1627                 /*
1628                  * Do not assume that spinlocks can be initialized via memcpy:
1629                  */
1630                 spin_lock_init(&ptr->lock);
1631
1632                 cache_cache.array[smp_processor_id()] = ptr;
1633
1634                 ptr = kmalloc(sizeof(struct arraycache_init), GFP_NOWAIT);
1635
1636                 BUG_ON(cpu_cache_get(malloc_sizes[INDEX_AC].cs_cachep)
1637                        != &initarray_generic.cache);
1638                 memcpy(ptr, cpu_cache_get(malloc_sizes[INDEX_AC].cs_cachep),
1639                        sizeof(struct arraycache_init));
1640                 /*
1641                  * Do not assume that spinlocks can be initialized via memcpy:
1642                  */
1643                 spin_lock_init(&ptr->lock);
1644
1645                 malloc_sizes[INDEX_AC].cs_cachep->array[smp_processor_id()] =
1646                     ptr;
1647         }
1648         /* 5) Replace the bootstrap kmem_list3's */
1649         {
1650                 int nid;
1651
1652                 for_each_online_node(nid) {
1653                         init_list(&cache_cache, &initkmem_list3[CACHE_CACHE + nid], nid);
1654
1655                         init_list(malloc_sizes[INDEX_AC].cs_cachep,
1656                                   &initkmem_list3[SIZE_AC + nid], nid);
1657
1658                         if (INDEX_AC != INDEX_L3) {
1659                                 init_list(malloc_sizes[INDEX_L3].cs_cachep,
1660                                           &initkmem_list3[SIZE_L3 + nid], nid);
1661                         }
1662                 }
1663         }
1664
1665         g_cpucache_up = EARLY;
1666 }
1667
1668 void __init kmem_cache_init_late(void)
1669 {
1670         struct kmem_cache *cachep;
1671
1672         g_cpucache_up = LATE;
1673
1674         /* Annotate slab for lockdep -- annotate the malloc caches */
1675         init_lock_keys();
1676
1677         /* 6) resize the head arrays to their final sizes */
1678         mutex_lock(&cache_chain_mutex);
1679         list_for_each_entry(cachep, &cache_chain, next)
1680                 if (enable_cpucache(cachep, GFP_NOWAIT))
1681                         BUG();
1682         mutex_unlock(&cache_chain_mutex);
1683
1684         /* Done! */
1685         g_cpucache_up = FULL;
1686
1687         /*
1688          * Register a cpu startup notifier callback that initializes
1689          * cpu_cache_get for all new cpus
1690          */
1691         register_cpu_notifier(&cpucache_notifier);
1692
1693 #ifdef CONFIG_NUMA
1694         /*
1695          * Register a memory hotplug callback that initializes and frees
1696          * nodelists.
1697          */
1698         hotplug_memory_notifier(slab_memory_callback, SLAB_CALLBACK_PRI);
1699 #endif
1700
1701         /*
1702          * The reap timers are started later, with a module init call: That part
1703          * of the kernel is not yet operational.
1704          */
1705 }
1706
1707 static int __init cpucache_init(void)
1708 {
1709         int cpu;
1710
1711         /*
1712          * Register the timers that return unneeded pages to the page allocator
1713          */
1714         for_each_online_cpu(cpu)
1715                 start_cpu_timer(cpu);
1716         return 0;
1717 }
1718 __initcall(cpucache_init);
1719
1720 /*
1721  * Interface to system's page allocator. No need to hold the cache-lock.
1722  *
1723  * If we requested dmaable memory, we will get it. Even if we
1724  * did not request dmaable memory, we might get it, but that
1725  * would be relatively rare and ignorable.
1726  */
1727 static void *kmem_getpages(struct kmem_cache *cachep, gfp_t flags, int nodeid)
1728 {
1729         struct page *page;
1730         int nr_pages;
1731         int i;
1732
1733 #ifndef CONFIG_MMU
1734         /*
1735          * Nommu uses slab's for process anonymous memory allocations, and thus
1736          * requires __GFP_COMP to properly refcount higher order allocations
1737          */
1738         flags |= __GFP_COMP;
1739 #endif
1740
1741         flags |= cachep->gfpflags;
1742         if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
1743                 flags |= __GFP_RECLAIMABLE;
1744
1745         page = alloc_pages_exact_node(nodeid, flags | __GFP_NOTRACK, cachep->gfporder);
1746         if (!page)
1747                 return NULL;
1748
1749         nr_pages = (1 << cachep->gfporder);
1750         if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
1751                 add_zone_page_state(page_zone(page),
1752                         NR_SLAB_RECLAIMABLE, nr_pages);
1753         else
1754                 add_zone_page_state(page_zone(page),
1755                         NR_SLAB_UNRECLAIMABLE, nr_pages);
1756         for (i = 0; i < nr_pages; i++)
1757                 __SetPageSlab(page + i);
1758
1759         if (kmemcheck_enabled && !(cachep->flags & SLAB_NOTRACK)) {
1760                 kmemcheck_alloc_shadow(page, cachep->gfporder, flags, nodeid);
1761
1762                 if (cachep->ctor)
1763                         kmemcheck_mark_uninitialized_pages(page, nr_pages);
1764                 else
1765                         kmemcheck_mark_unallocated_pages(page, nr_pages);
1766         }
1767
1768         return page_address(page);
1769 }
1770
1771 /*
1772  * Interface to system's page release.
1773  */
1774 static void kmem_freepages(struct kmem_cache *cachep, void *addr)
1775 {
1776         unsigned long i = (1 << cachep->gfporder);
1777         struct page *page = virt_to_page(addr);
1778         const unsigned long nr_freed = i;
1779
1780         kmemcheck_free_shadow(page, cachep->gfporder);
1781
1782         if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
1783                 sub_zone_page_state(page_zone(page),
1784                                 NR_SLAB_RECLAIMABLE, nr_freed);
1785         else
1786                 sub_zone_page_state(page_zone(page),
1787                                 NR_SLAB_UNRECLAIMABLE, nr_freed);
1788         while (i--) {
1789                 BUG_ON(!PageSlab(page));
1790                 __ClearPageSlab(page);
1791                 page++;
1792         }
1793         if (current->reclaim_state)
1794                 current->reclaim_state->reclaimed_slab += nr_freed;
1795         free_pages((unsigned long)addr, cachep->gfporder);
1796 }
1797
1798 static void kmem_rcu_free(struct rcu_head *head)
1799 {
1800         struct slab_rcu *slab_rcu = (struct slab_rcu *)head;
1801         struct kmem_cache *cachep = slab_rcu->cachep;
1802
1803         kmem_freepages(cachep, slab_rcu->addr);
1804         if (OFF_SLAB(cachep))
1805                 kmem_cache_free(cachep->slabp_cache, slab_rcu);
1806 }
1807
1808 #if DEBUG
1809
1810 #ifdef CONFIG_DEBUG_PAGEALLOC
1811 static void store_stackinfo(struct kmem_cache *cachep, unsigned long *addr,
1812                             unsigned long caller)
1813 {
1814         int size = obj_size(cachep);
1815
1816         addr = (unsigned long *)&((char *)addr)[obj_offset(cachep)];
1817
1818         if (size < 5 * sizeof(unsigned long))
1819                 return;
1820
1821         *addr++ = 0x12345678;
1822         *addr++ = caller;
1823         *addr++ = smp_processor_id();
1824         size -= 3 * sizeof(unsigned long);
1825         {
1826                 unsigned long *sptr = &caller;
1827                 unsigned long svalue;
1828
1829                 while (!kstack_end(sptr)) {
1830                         svalue = *sptr++;
1831                         if (kernel_text_address(svalue)) {
1832                                 *addr++ = svalue;
1833                                 size -= sizeof(unsigned long);
1834                                 if (size <= sizeof(unsigned long))
1835                                         break;
1836                         }
1837                 }
1838
1839         }
1840         *addr++ = 0x87654321;
1841 }
1842 #endif
1843
1844 static void poison_obj(struct kmem_cache *cachep, void *addr, unsigned char val)
1845 {
1846         int size = obj_size(cachep);
1847         addr = &((char *)addr)[obj_offset(cachep)];
1848
1849         memset(addr, val, size);
1850         *(unsigned char *)(addr + size - 1) = POISON_END;
1851 }
1852
1853 static void dump_line(char *data, int offset, int limit)
1854 {
1855         int i;
1856         unsigned char error = 0;
1857         int bad_count = 0;
1858
1859         printk(KERN_ERR "%03x: ", offset);
1860         for (i = 0; i < limit; i++) {
1861                 if (data[offset + i] != POISON_FREE) {
1862                         error = data[offset + i];
1863                         bad_count++;
1864                 }
1865         }
1866         print_hex_dump(KERN_CONT, "", 0, 16, 1,
1867                         &data[offset], limit, 1);
1868
1869         if (bad_count == 1) {
1870                 error ^= POISON_FREE;
1871                 if (!(error & (error - 1))) {
1872                         printk(KERN_ERR "Single bit error detected. Probably "
1873                                         "bad RAM.\n");
1874 #ifdef CONFIG_X86
1875                         printk(KERN_ERR "Run memtest86+ or a similar memory "
1876                                         "test tool.\n");
1877 #else
1878                         printk(KERN_ERR "Run a memory test tool.\n");
1879 #endif
1880                 }
1881         }
1882 }
1883 #endif
1884
1885 #if DEBUG
1886
1887 static void print_objinfo(struct kmem_cache *cachep, void *objp, int lines)
1888 {
1889         int i, size;
1890         char *realobj;
1891
1892         if (cachep->flags & SLAB_RED_ZONE) {
1893                 printk(KERN_ERR "Redzone: 0x%llx/0x%llx.\n",
1894                         *dbg_redzone1(cachep, objp),
1895                         *dbg_redzone2(cachep, objp));
1896         }
1897
1898         if (cachep->flags & SLAB_STORE_USER) {
1899                 printk(KERN_ERR "Last user: [<%p>]",
1900                         *dbg_userword(cachep, objp));
1901                 print_symbol("(%s)",
1902                                 (unsigned long)*dbg_userword(cachep, objp));
1903                 printk("\n");
1904         }
1905         realobj = (char *)objp + obj_offset(cachep);
1906         size = obj_size(cachep);
1907         for (i = 0; i < size && lines; i += 16, lines--) {
1908                 int limit;
1909                 limit = 16;
1910                 if (i + limit > size)
1911                         limit = size - i;
1912                 dump_line(realobj, i, limit);
1913         }
1914 }
1915
1916 static void check_poison_obj(struct kmem_cache *cachep, void *objp)
1917 {
1918         char *realobj;
1919         int size, i;
1920         int lines = 0;
1921
1922         realobj = (char *)objp + obj_offset(cachep);
1923         size = obj_size(cachep);
1924
1925         for (i = 0; i < size; i++) {
1926                 char exp = POISON_FREE;
1927                 if (i == size - 1)
1928                         exp = POISON_END;
1929                 if (realobj[i] != exp) {
1930                         int limit;
1931                         /* Mismatch ! */
1932                         /* Print header */
1933                         if (lines == 0) {
1934                                 printk(KERN_ERR
1935                                         "Slab corruption: %s start=%p, len=%d\n",
1936                                         cachep->name, realobj, size);
1937                                 print_objinfo(cachep, objp, 0);
1938                         }
1939                         /* Hexdump the affected line */
1940                         i = (i / 16) * 16;
1941                         limit = 16;
1942                         if (i + limit > size)
1943                                 limit = size - i;
1944                         dump_line(realobj, i, limit);
1945                         i += 16;
1946                         lines++;
1947                         /* Limit to 5 lines */
1948                         if (lines > 5)
1949                                 break;
1950                 }
1951         }
1952         if (lines != 0) {
1953                 /* Print some data about the neighboring objects, if they
1954                  * exist:
1955                  */
1956                 struct slab *slabp = virt_to_slab(objp);
1957                 unsigned int objnr;
1958
1959                 objnr = obj_to_index(cachep, slabp, objp);
1960                 if (objnr) {
1961                         objp = index_to_obj(cachep, slabp, objnr - 1);
1962                         realobj = (char *)objp + obj_offset(cachep);
1963                         printk(KERN_ERR "Prev obj: start=%p, len=%d\n",
1964                                realobj, size);
1965                         print_objinfo(cachep, objp, 2);
1966                 }
1967                 if (objnr + 1 < cachep->num) {
1968                         objp = index_to_obj(cachep, slabp, objnr + 1);
1969                         realobj = (char *)objp + obj_offset(cachep);
1970                         printk(KERN_ERR "Next obj: start=%p, len=%d\n",
1971                                realobj, size);
1972                         print_objinfo(cachep, objp, 2);
1973                 }
1974         }
1975 }
1976 #endif
1977
1978 #if DEBUG
1979 static void slab_destroy_debugcheck(struct kmem_cache *cachep, struct slab *slabp)
1980 {
1981         int i;
1982         for (i = 0; i < cachep->num; i++) {
1983                 void *objp = index_to_obj(cachep, slabp, i);
1984
1985                 if (cachep->flags & SLAB_POISON) {
1986 #ifdef CONFIG_DEBUG_PAGEALLOC
1987                         if (cachep->buffer_size % PAGE_SIZE == 0 &&
1988                                         OFF_SLAB(cachep))
1989                                 kernel_map_pages(virt_to_page(objp),
1990                                         cachep->buffer_size / PAGE_SIZE, 1);
1991                         else
1992                                 check_poison_obj(cachep, objp);
1993 #else
1994                         check_poison_obj(cachep, objp);
1995 #endif
1996                 }
1997                 if (cachep->flags & SLAB_RED_ZONE) {
1998                         if (*dbg_redzone1(cachep, objp) != RED_INACTIVE)
1999                                 slab_error(cachep, "start of a freed object "
2000                                            "was overwritten");
2001                         if (*dbg_redzone2(cachep, objp) != RED_INACTIVE)
2002                                 slab_error(cachep, "end of a freed object "
2003                                            "was overwritten");
2004                 }
2005         }
2006 }
2007 #else
2008 static void slab_destroy_debugcheck(struct kmem_cache *cachep, struct slab *slabp)
2009 {
2010 }
2011 #endif
2012
2013 /**
2014  * slab_destroy - destroy and release all objects in a slab
2015  * @cachep: cache pointer being destroyed
2016  * @slabp: slab pointer being destroyed
2017  *
2018  * Destroy all the objs in a slab, and release the mem back to the system.
2019  * Before calling the slab must have been unlinked from the cache.  The
2020  * cache-lock is not held/needed.
2021  */
2022 static void slab_destroy(struct kmem_cache *cachep, struct slab *slabp)
2023 {
2024         void *addr = slabp->s_mem - slabp->colouroff;
2025
2026         slab_destroy_debugcheck(cachep, slabp);
2027         if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU)) {
2028                 struct slab_rcu *slab_rcu;
2029
2030                 slab_rcu = (struct slab_rcu *)slabp;
2031                 slab_rcu->cachep = cachep;
2032                 slab_rcu->addr = addr;
2033                 call_rcu(&slab_rcu->head, kmem_rcu_free);
2034         } else {
2035                 kmem_freepages(cachep, addr);
2036                 if (OFF_SLAB(cachep))
2037                         kmem_cache_free(cachep->slabp_cache, slabp);
2038         }
2039 }
2040
2041 static void __kmem_cache_destroy(struct kmem_cache *cachep)
2042 {
2043         int i;
2044         struct kmem_list3 *l3;
2045
2046         for_each_online_cpu(i)
2047             kfree(cachep->array[i]);
2048
2049         /* NUMA: free the list3 structures */
2050         for_each_online_node(i) {
2051                 l3 = cachep->nodelists[i];
2052                 if (l3) {
2053                         kfree(l3->shared);
2054                         free_alien_cache(l3->alien);
2055                         kfree(l3);
2056                 }
2057         }
2058         kmem_cache_free(&cache_cache, cachep);
2059 }
2060
2061
2062 /**
2063  * calculate_slab_order - calculate size (page order) of slabs
2064  * @cachep: pointer to the cache that is being created
2065  * @size: size of objects to be created in this cache.
2066  * @align: required alignment for the objects.
2067  * @flags: slab allocation flags
2068  *
2069  * Also calculates the number of objects per slab.
2070  *
2071  * This could be made much more intelligent.  For now, try to avoid using
2072  * high order pages for slabs.  When the gfp() functions are more friendly
2073  * towards high-order requests, this should be changed.
2074  */
2075 static size_t calculate_slab_order(struct kmem_cache *cachep,
2076                         size_t size, size_t align, unsigned long flags)
2077 {
2078         unsigned long offslab_limit;
2079         size_t left_over = 0;
2080         int gfporder;
2081
2082         for (gfporder = 0; gfporder <= KMALLOC_MAX_ORDER; gfporder++) {
2083                 unsigned int num;
2084                 size_t remainder;
2085
2086                 cache_estimate(gfporder, size, align, flags, &remainder, &num);
2087                 if (!num)
2088                         continue;
2089
2090                 if (flags & CFLGS_OFF_SLAB) {
2091                         /*
2092                          * Max number of objs-per-slab for caches which
2093                          * use off-slab slabs. Needed to avoid a possible
2094                          * looping condition in cache_grow().
2095                          */
2096                         offslab_limit = size - sizeof(struct slab);
2097                         offslab_limit /= sizeof(kmem_bufctl_t);
2098
2099                         if (num > offslab_limit)
2100                                 break;
2101                 }
2102
2103                 /* Found something acceptable - save it away */
2104                 cachep->num = num;
2105                 cachep->gfporder = gfporder;
2106                 left_over = remainder;
2107
2108                 /*
2109                  * A VFS-reclaimable slab tends to have most allocations
2110                  * as GFP_NOFS and we really don't want to have to be allocating
2111                  * higher-order pages when we are unable to shrink dcache.
2112                  */
2113                 if (flags & SLAB_RECLAIM_ACCOUNT)
2114                         break;
2115
2116                 /*
2117                  * Large number of objects is good, but very large slabs are
2118                  * currently bad for the gfp()s.
2119                  */
2120                 if (gfporder >= slab_break_gfp_order)
2121                         break;
2122
2123                 /*
2124                  * Acceptable internal fragmentation?
2125                  */
2126                 if (left_over * 8 <= (PAGE_SIZE << gfporder))
2127                         break;
2128         }
2129         return left_over;
2130 }
2131
2132 static int __init_refok setup_cpu_cache(struct kmem_cache *cachep, gfp_t gfp)
2133 {
2134         if (g_cpucache_up == FULL)
2135                 return enable_cpucache(cachep, gfp);
2136
2137         if (g_cpucache_up == NONE) {
2138                 /*
2139                  * Note: the first kmem_cache_create must create the cache
2140                  * that's used by kmalloc(24), otherwise the creation of
2141                  * further caches will BUG().
2142                  */
2143                 cachep->array[smp_processor_id()] = &initarray_generic.cache;
2144
2145                 /*
2146                  * If the cache that's used by kmalloc(sizeof(kmem_list3)) is
2147                  * the first cache, then we need to set up all its list3s,
2148                  * otherwise the creation of further caches will BUG().
2149                  */
2150                 set_up_list3s(cachep, SIZE_AC);
2151                 if (INDEX_AC == INDEX_L3)
2152                         g_cpucache_up = PARTIAL_L3;
2153                 else
2154                         g_cpucache_up = PARTIAL_AC;
2155         } else {
2156                 cachep->array[smp_processor_id()] =
2157                         kmalloc(sizeof(struct arraycache_init), gfp);
2158
2159                 if (g_cpucache_up == PARTIAL_AC) {
2160                         set_up_list3s(cachep, SIZE_L3);
2161                         g_cpucache_up = PARTIAL_L3;
2162                 } else {
2163                         int node;
2164                         for_each_online_node(node) {
2165                                 cachep->nodelists[node] =
2166                                     kmalloc_node(sizeof(struct kmem_list3),
2167                                                 gfp, node);
2168                                 BUG_ON(!cachep->nodelists[node]);
2169                                 kmem_list3_init(cachep->nodelists[node]);
2170                         }
2171                 }
2172         }
2173         cachep->nodelists[numa_mem_id()]->next_reap =
2174                         jiffies + REAPTIMEOUT_LIST3 +
2175                         ((unsigned long)cachep) % REAPTIMEOUT_LIST3;
2176
2177         cpu_cache_get(cachep)->avail = 0;
2178         cpu_cache_get(cachep)->limit = BOOT_CPUCACHE_ENTRIES;
2179         cpu_cache_get(cachep)->batchcount = 1;
2180         cpu_cache_get(cachep)->touched = 0;
2181         cachep->batchcount = 1;
2182         cachep->limit = BOOT_CPUCACHE_ENTRIES;
2183         return 0;
2184 }
2185
2186 /**
2187  * kmem_cache_create - Create a cache.
2188  * @name: A string which is used in /proc/slabinfo to identify this cache.
2189  * @size: The size of objects to be created in this cache.
2190  * @align: The required alignment for the objects.
2191  * @flags: SLAB flags
2192  * @ctor: A constructor for the objects.
2193  *
2194  * Returns a ptr to the cache on success, NULL on failure.
2195  * Cannot be called within a int, but can be interrupted.
2196  * The @ctor is run when new pages are allocated by the cache.
2197  *
2198  * @name must be valid until the cache is destroyed. This implies that
2199  * the module calling this has to destroy the cache before getting unloaded.
2200  *
2201  * The flags are
2202  *
2203  * %SLAB_POISON - Poison the slab with a known test pattern (a5a5a5a5)
2204  * to catch references to uninitialised memory.
2205  *
2206  * %SLAB_RED_ZONE - Insert `Red' zones around the allocated memory to check
2207  * for buffer overruns.
2208  *
2209  * %SLAB_HWCACHE_ALIGN - Align the objects in this cache to a hardware
2210  * cacheline.  This can be beneficial if you're counting cycles as closely
2211  * as davem.
2212  */
2213 struct kmem_cache *
2214 kmem_cache_create (const char *name, size_t size, size_t align,
2215         unsigned long flags, void (*ctor)(void *))
2216 {
2217         size_t left_over, slab_size, ralign;
2218         struct kmem_cache *cachep = NULL, *pc;
2219         gfp_t gfp;
2220
2221         /*
2222          * Sanity checks... these are all serious usage bugs.
2223          */
2224         if (!name || in_interrupt() || (size < BYTES_PER_WORD) ||
2225             size > KMALLOC_MAX_SIZE) {
2226                 printk(KERN_ERR "%s: Early error in slab %s\n", __func__,
2227                                 name);
2228                 BUG();
2229         }
2230
2231         /*
2232          * We use cache_chain_mutex to ensure a consistent view of
2233          * cpu_online_mask as well.  Please see cpuup_callback
2234          */
2235         if (slab_is_available()) {
2236                 get_online_cpus();
2237                 mutex_lock(&cache_chain_mutex);
2238         }
2239
2240         list_for_each_entry(pc, &cache_chain, next) {
2241                 char tmp;
2242                 int res;
2243
2244                 /*
2245                  * This happens when the module gets unloaded and doesn't
2246                  * destroy its slab cache and no-one else reuses the vmalloc
2247                  * area of the module.  Print a warning.
2248                  */
2249                 res = probe_kernel_address(pc->name, tmp);
2250                 if (res) {
2251                         printk(KERN_ERR
2252                                "SLAB: cache with size %d has lost its name\n",
2253                                pc->buffer_size);
2254                         continue;
2255                 }
2256
2257                 if (!strcmp(pc->name, name)) {
2258                         printk(KERN_ERR
2259                                "kmem_cache_create: duplicate cache %s\n", name);
2260                         dump_stack();
2261                         goto oops;
2262                 }
2263         }
2264
2265 #if DEBUG
2266         WARN_ON(strchr(name, ' '));     /* It confuses parsers */
2267 #if FORCED_DEBUG
2268         /*
2269          * Enable redzoning and last user accounting, except for caches with
2270          * large objects, if the increased size would increase the object size
2271          * above the next power of two: caches with object sizes just above a
2272          * power of two have a significant amount of internal fragmentation.
2273          */
2274         if (size < 4096 || fls(size - 1) == fls(size-1 + REDZONE_ALIGN +
2275                                                 2 * sizeof(unsigned long long)))
2276                 flags |= SLAB_RED_ZONE | SLAB_STORE_USER;
2277         if (!(flags & SLAB_DESTROY_BY_RCU))
2278                 flags |= SLAB_POISON;
2279 #endif
2280         if (flags & SLAB_DESTROY_BY_RCU)
2281                 BUG_ON(flags & SLAB_POISON);
2282 #endif
2283         /*
2284          * Always checks flags, a caller might be expecting debug support which
2285          * isn't available.
2286          */
2287         BUG_ON(flags & ~CREATE_MASK);
2288
2289         /*
2290          * Check that size is in terms of words.  This is needed to avoid
2291          * unaligned accesses for some archs when redzoning is used, and makes
2292          * sure any on-slab bufctl's are also correctly aligned.
2293          */
2294         if (size & (BYTES_PER_WORD - 1)) {
2295                 size += (BYTES_PER_WORD - 1);
2296                 size &= ~(BYTES_PER_WORD - 1);
2297         }
2298
2299         /* calculate the final buffer alignment: */
2300
2301         /* 1) arch recommendation: can be overridden for debug */
2302         if (flags & SLAB_HWCACHE_ALIGN) {
2303                 /*
2304                  * Default alignment: as specified by the arch code.  Except if
2305                  * an object is really small, then squeeze multiple objects into
2306                  * one cacheline.
2307                  */
2308                 ralign = cache_line_size();
2309                 while (size <= ralign / 2)
2310                         ralign /= 2;
2311         } else {
2312                 ralign = BYTES_PER_WORD;
2313         }
2314
2315         /*
2316          * Redzoning and user store require word alignment or possibly larger.
2317          * Note this will be overridden by architecture or caller mandated
2318          * alignment if either is greater than BYTES_PER_WORD.
2319          */
2320         if (flags & SLAB_STORE_USER)
2321                 ralign = BYTES_PER_WORD;
2322
2323         if (flags & SLAB_RED_ZONE) {
2324                 ralign = REDZONE_ALIGN;
2325                 /* If redzoning, ensure that the second redzone is suitably
2326                  * aligned, by adjusting the object size accordingly. */
2327                 size += REDZONE_ALIGN - 1;
2328                 size &= ~(REDZONE_ALIGN - 1);
2329         }
2330
2331         /* 2) arch mandated alignment */
2332         if (ralign < ARCH_SLAB_MINALIGN) {
2333                 ralign = ARCH_SLAB_MINALIGN;
2334         }
2335         /* 3) caller mandated alignment */
2336         if (ralign < align) {
2337                 ralign = align;
2338         }
2339         /* disable debug if necessary */
2340         if (ralign > __alignof__(unsigned long long))
2341                 flags &= ~(SLAB_RED_ZONE | SLAB_STORE_USER);
2342         /*
2343          * 4) Store it.
2344          */
2345         align = ralign;
2346
2347         if (slab_is_available())
2348                 gfp = GFP_KERNEL;
2349         else
2350                 gfp = GFP_NOWAIT;
2351
2352         /* Get cache's description obj. */
2353         cachep = kmem_cache_zalloc(&cache_cache, gfp);
2354         if (!cachep)
2355                 goto oops;
2356
2357         cachep->nodelists = (struct kmem_list3 **)&cachep->array[nr_cpu_ids];
2358 #if DEBUG
2359         cachep->obj_size = size;
2360
2361         /*
2362          * Both debugging options require word-alignment which is calculated
2363          * into align above.
2364          */
2365         if (flags & SLAB_RED_ZONE) {
2366                 /* add space for red zone words */
2367                 cachep->obj_offset += sizeof(unsigned long long);
2368                 size += 2 * sizeof(unsigned long long);
2369         }
2370         if (flags & SLAB_STORE_USER) {
2371                 /* user store requires one word storage behind the end of
2372                  * the real object. But if the second red zone needs to be
2373                  * aligned to 64 bits, we must allow that much space.
2374                  */
2375                 if (flags & SLAB_RED_ZONE)
2376                         size += REDZONE_ALIGN;
2377                 else
2378                         size += BYTES_PER_WORD;
2379         }
2380 #if FORCED_DEBUG && defined(CONFIG_DEBUG_PAGEALLOC)
2381         if (size >= malloc_sizes[INDEX_L3 + 1].cs_size
2382             && cachep->obj_size > cache_line_size() && ALIGN(size, align) < PAGE_SIZE) {
2383                 cachep->obj_offset += PAGE_SIZE - ALIGN(size, align);
2384                 size = PAGE_SIZE;
2385         }
2386 #endif
2387 #endif
2388
2389         /*
2390          * Determine if the slab management is 'on' or 'off' slab.
2391          * (bootstrapping cannot cope with offslab caches so don't do
2392          * it too early on. Always use on-slab management when
2393          * SLAB_NOLEAKTRACE to avoid recursive calls into kmemleak)
2394          */
2395         if ((size >= (PAGE_SIZE >> 3)) && !slab_early_init &&
2396             !(flags & SLAB_NOLEAKTRACE))
2397                 /*
2398                  * Size is large, assume best to place the slab management obj
2399                  * off-slab (should allow better packing of objs).
2400                  */
2401                 flags |= CFLGS_OFF_SLAB;
2402
2403         size = ALIGN(size, align);
2404
2405         left_over = calculate_slab_order(cachep, size, align, flags);
2406
2407         if (!cachep->num) {
2408                 printk(KERN_ERR
2409                        "kmem_cache_create: couldn't create cache %s.\n", name);
2410                 kmem_cache_free(&cache_cache, cachep);
2411                 cachep = NULL;
2412                 goto oops;
2413         }
2414         slab_size = ALIGN(cachep->num * sizeof(kmem_bufctl_t)
2415                           + sizeof(struct slab), align);
2416
2417         /*
2418          * If the slab has been placed off-slab, and we have enough space then
2419          * move it on-slab. This is at the expense of any extra colouring.
2420          */
2421         if (flags & CFLGS_OFF_SLAB && left_over >= slab_size) {
2422                 flags &= ~CFLGS_OFF_SLAB;
2423                 left_over -= slab_size;
2424         }
2425
2426         if (flags & CFLGS_OFF_SLAB) {
2427                 /* really off slab. No need for manual alignment */
2428                 slab_size =
2429                     cachep->num * sizeof(kmem_bufctl_t) + sizeof(struct slab);
2430
2431 #ifdef CONFIG_PAGE_POISONING
2432                 /* If we're going to use the generic kernel_map_pages()
2433                  * poisoning, then it's going to smash the contents of
2434                  * the redzone and userword anyhow, so switch them off.
2435                  */
2436                 if (size % PAGE_SIZE == 0 && flags & SLAB_POISON)
2437                         flags &= ~(SLAB_RED_ZONE | SLAB_STORE_USER);
2438 #endif
2439         }
2440
2441         cachep->colour_off = cache_line_size();
2442         /* Offset must be a multiple of the alignment. */
2443         if (cachep->colour_off < align)
2444                 cachep->colour_off = align;
2445         cachep->colour = left_over / cachep->colour_off;
2446         cachep->slab_size = slab_size;
2447         cachep->flags = flags;
2448         cachep->gfpflags = 0;
2449         if (CONFIG_ZONE_DMA_FLAG && (flags & SLAB_CACHE_DMA))
2450                 cachep->gfpflags |= GFP_DMA;
2451         cachep->buffer_size = size;
2452         cachep->reciprocal_buffer_size = reciprocal_value(size);
2453
2454         if (flags & CFLGS_OFF_SLAB) {
2455                 cachep->slabp_cache = kmem_find_general_cachep(slab_size, 0u);
2456                 /*
2457                  * This is a possibility for one of the malloc_sizes caches.
2458                  * But since we go off slab only for object size greater than
2459                  * PAGE_SIZE/8, and malloc_sizes gets created in ascending order,
2460                  * this should not happen at all.
2461                  * But leave a BUG_ON for some lucky dude.
2462                  */
2463                 BUG_ON(ZERO_OR_NULL_PTR(cachep->slabp_cache));
2464         }
2465         cachep->ctor = ctor;
2466         cachep->name = name;
2467
2468         if (setup_cpu_cache(cachep, gfp)) {
2469                 __kmem_cache_destroy(cachep);
2470                 cachep = NULL;
2471                 goto oops;
2472         }
2473
2474         if (flags & SLAB_DEBUG_OBJECTS) {
2475                 /*
2476                  * Would deadlock through slab_destroy()->call_rcu()->
2477                  * debug_object_activate()->kmem_cache_alloc().
2478                  */
2479                 WARN_ON_ONCE(flags & SLAB_DESTROY_BY_RCU);
2480
2481                 slab_set_debugobj_lock_classes(cachep);
2482         }
2483
2484         /* cache setup completed, link it into the list */
2485         list_add(&cachep->next, &cache_chain);
2486 oops:
2487         if (!cachep && (flags & SLAB_PANIC))
2488                 panic("kmem_cache_create(): failed to create slab `%s'\n",
2489                       name);
2490         if (slab_is_available()) {
2491                 mutex_unlock(&cache_chain_mutex);
2492                 put_online_cpus();
2493         }
2494         return cachep;
2495 }
2496 EXPORT_SYMBOL(kmem_cache_create);
2497
2498 #if DEBUG
2499 static void check_irq_off(void)
2500 {
2501         BUG_ON(!irqs_disabled());
2502 }
2503
2504 static void check_irq_on(void)
2505 {
2506         BUG_ON(irqs_disabled());
2507 }
2508
2509 static void check_spinlock_acquired(struct kmem_cache *cachep)
2510 {
2511 #ifdef CONFIG_SMP
2512         check_irq_off();
2513         assert_spin_locked(&cachep->nodelists[numa_mem_id()]->list_lock);
2514 #endif
2515 }
2516
2517 static void check_spinlock_acquired_node(struct kmem_cache *cachep, int node)
2518 {
2519 #ifdef CONFIG_SMP
2520         check_irq_off();
2521         assert_spin_locked(&cachep->nodelists[node]->list_lock);
2522 #endif
2523 }
2524
2525 #else
2526 #define check_irq_off() do { } while(0)
2527 #define check_irq_on()  do { } while(0)
2528 #define check_spinlock_acquired(x) do { } while(0)
2529 #define check_spinlock_acquired_node(x, y) do { } while(0)
2530 #endif
2531
2532 static void drain_array(struct kmem_cache *cachep, struct kmem_list3 *l3,
2533                         struct array_cache *ac,
2534                         int force, int node);
2535
2536 static void do_drain(void *arg)
2537 {
2538         struct kmem_cache *cachep = arg;
2539         struct array_cache *ac;
2540         int node = numa_mem_id();
2541
2542         check_irq_off();
2543         ac = cpu_cache_get(cachep);
2544         spin_lock(&cachep->nodelists[node]->list_lock);
2545         free_block(cachep, ac->entry, ac->avail, node);
2546         spin_unlock(&cachep->nodelists[node]->list_lock);
2547         ac->avail = 0;
2548 }
2549
2550 static void drain_cpu_caches(struct kmem_cache *cachep)
2551 {
2552         struct kmem_list3 *l3;
2553         int node;
2554
2555         on_each_cpu(do_drain, cachep, 1);
2556         check_irq_on();
2557         for_each_online_node(node) {
2558                 l3 = cachep->nodelists[node];
2559                 if (l3 && l3->alien)
2560                         drain_alien_cache(cachep, l3->alien);
2561         }
2562
2563         for_each_online_node(node) {
2564                 l3 = cachep->nodelists[node];
2565                 if (l3)
2566                         drain_array(cachep, l3, l3->shared, 1, node);
2567         }
2568 }
2569
2570 /*
2571  * Remove slabs from the list of free slabs.
2572  * Specify the number of slabs to drain in tofree.
2573  *
2574  * Returns the actual number of slabs released.
2575  */
2576 static int drain_freelist(struct kmem_cache *cache,
2577                         struct kmem_list3 *l3, int tofree)
2578 {
2579         struct list_head *p;
2580         int nr_freed;
2581         struct slab *slabp;
2582
2583         nr_freed = 0;
2584         while (nr_freed < tofree && !list_empty(&l3->slabs_free)) {
2585
2586                 spin_lock_irq(&l3->list_lock);
2587                 p = l3->slabs_free.prev;
2588                 if (p == &l3->slabs_free) {
2589                         spin_unlock_irq(&l3->list_lock);
2590                         goto out;
2591                 }
2592
2593                 slabp = list_entry(p, struct slab, list);
2594 #if DEBUG
2595                 BUG_ON(slabp->inuse);
2596 #endif
2597                 list_del(&slabp->list);
2598                 /*
2599                  * Safe to drop the lock. The slab is no longer linked
2600                  * to the cache.
2601                  */
2602                 l3->free_objects -= cache->num;
2603                 spin_unlock_irq(&l3->list_lock);
2604                 slab_destroy(cache, slabp);
2605                 nr_freed++;
2606         }
2607 out:
2608         return nr_freed;
2609 }
2610
2611 /* Called with cache_chain_mutex held to protect against cpu hotplug */
2612 static int __cache_shrink(struct kmem_cache *cachep)
2613 {
2614         int ret = 0, i = 0;
2615         struct kmem_list3 *l3;
2616
2617         drain_cpu_caches(cachep);
2618
2619         check_irq_on();
2620         for_each_online_node(i) {
2621                 l3 = cachep->nodelists[i];
2622                 if (!l3)
2623                         continue;
2624
2625                 drain_freelist(cachep, l3, l3->free_objects);
2626
2627                 ret += !list_empty(&l3->slabs_full) ||
2628                         !list_empty(&l3->slabs_partial);
2629         }
2630         return (ret ? 1 : 0);
2631 }
2632
2633 /**
2634  * kmem_cache_shrink - Shrink a cache.
2635  * @cachep: The cache to shrink.
2636  *
2637  * Releases as many slabs as possible for a cache.
2638  * To help debugging, a zero exit status indicates all slabs were released.
2639  */
2640 int kmem_cache_shrink(struct kmem_cache *cachep)
2641 {
2642         int ret;
2643         BUG_ON(!cachep || in_interrupt());
2644
2645         get_online_cpus();
2646         mutex_lock(&cache_chain_mutex);
2647         ret = __cache_shrink(cachep);
2648         mutex_unlock(&cache_chain_mutex);
2649         put_online_cpus();
2650         return ret;
2651 }
2652 EXPORT_SYMBOL(kmem_cache_shrink);
2653
2654 /**
2655  * kmem_cache_destroy - delete a cache
2656  * @cachep: the cache to destroy
2657  *
2658  * Remove a &struct kmem_cache object from the slab cache.
2659  *
2660  * It is expected this function will be called by a module when it is
2661  * unloaded.  This will remove the cache completely, and avoid a duplicate
2662  * cache being allocated each time a module is loaded and unloaded, if the
2663  * module doesn't have persistent in-kernel storage across loads and unloads.
2664  *
2665  * The cache must be empty before calling this function.
2666  *
2667  * The caller must guarantee that no one will allocate memory from the cache
2668  * during the kmem_cache_destroy().
2669  */
2670 void kmem_cache_destroy(struct kmem_cache *cachep)
2671 {
2672         BUG_ON(!cachep || in_interrupt());
2673
2674         /* Find the cache in the chain of caches. */
2675         get_online_cpus();
2676         mutex_lock(&cache_chain_mutex);
2677         /*
2678          * the chain is never empty, cache_cache is never destroyed
2679          */
2680         list_del(&cachep->next);
2681         if (__cache_shrink(cachep)) {
2682                 slab_error(cachep, "Can't free all objects");
2683                 list_add(&cachep->next, &cache_chain);
2684                 mutex_unlock(&cache_chain_mutex);
2685                 put_online_cpus();
2686                 return;
2687         }
2688
2689         if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU))
2690                 rcu_barrier();
2691
2692         __kmem_cache_destroy(cachep);
2693         mutex_unlock(&cache_chain_mutex);
2694         put_online_cpus();
2695 }
2696 EXPORT_SYMBOL(kmem_cache_destroy);
2697
2698 /*
2699  * Get the memory for a slab management obj.
2700  * For a slab cache when the slab descriptor is off-slab, slab descriptors
2701  * always come from malloc_sizes caches.  The slab descriptor cannot
2702  * come from the same cache which is getting created because,
2703  * when we are searching for an appropriate cache for these
2704  * descriptors in kmem_cache_create, we search through the malloc_sizes array.
2705  * If we are creating a malloc_sizes cache here it would not be visible to
2706  * kmem_find_general_cachep till the initialization is complete.
2707  * Hence we cannot have slabp_cache same as the original cache.
2708  */
2709 static struct slab *alloc_slabmgmt(struct kmem_cache *cachep, void *objp,
2710                                    int colour_off, gfp_t local_flags,
2711                                    int nodeid)
2712 {
2713         struct slab *slabp;
2714
2715         if (OFF_SLAB(cachep)) {
2716                 /* Slab management obj is off-slab. */
2717                 slabp = kmem_cache_alloc_node(cachep->slabp_cache,
2718                                               local_flags, nodeid);
2719                 /*
2720                  * If the first object in the slab is leaked (it's allocated
2721                  * but no one has a reference to it), we want to make sure
2722                  * kmemleak does not treat the ->s_mem pointer as a reference
2723                  * to the object. Otherwise we will not report the leak.
2724                  */
2725                 kmemleak_scan_area(&slabp->list, sizeof(struct list_head),
2726                                    local_flags);
2727                 if (!slabp)
2728                         return NULL;
2729         } else {
2730                 slabp = objp + colour_off;
2731                 colour_off += cachep->slab_size;
2732         }
2733         slabp->inuse = 0;
2734         slabp->colouroff = colour_off;
2735         slabp->s_mem = objp + colour_off;
2736         slabp->nodeid = nodeid;
2737         slabp->free = 0;
2738         return slabp;
2739 }
2740
2741 static inline kmem_bufctl_t *slab_bufctl(struct slab *slabp)
2742 {
2743         return (kmem_bufctl_t *) (slabp + 1);
2744 }
2745
2746 static void cache_init_objs(struct kmem_cache *cachep,
2747                             struct slab *slabp)
2748 {
2749         int i;
2750
2751         for (i = 0; i < cachep->num; i++) {
2752                 void *objp = index_to_obj(cachep, slabp, i);
2753 #if DEBUG
2754                 /* need to poison the objs? */
2755                 if (cachep->flags & SLAB_POISON)
2756                         poison_obj(cachep, objp, POISON_FREE);
2757                 if (cachep->flags & SLAB_STORE_USER)
2758                         *dbg_userword(cachep, objp) = NULL;
2759
2760                 if (cachep->flags & SLAB_RED_ZONE) {
2761                         *dbg_redzone1(cachep, objp) = RED_INACTIVE;
2762                         *dbg_redzone2(cachep, objp) = RED_INACTIVE;
2763                 }
2764                 /*
2765                  * Constructors are not allowed to allocate memory from the same
2766                  * cache which they are a constructor for.  Otherwise, deadlock.
2767                  * They must also be threaded.
2768                  */
2769                 if (cachep->ctor && !(cachep->flags & SLAB_POISON))
2770                         cachep->ctor(objp + obj_offset(cachep));
2771
2772                 if (cachep->flags & SLAB_RED_ZONE) {
2773                         if (*dbg_redzone2(cachep, objp) != RED_INACTIVE)
2774                                 slab_error(cachep, "constructor overwrote the"
2775                                            " end of an object");
2776                         if (*dbg_redzone1(cachep, objp) != RED_INACTIVE)
2777                                 slab_error(cachep, "constructor overwrote the"
2778                                            " start of an object");
2779                 }
2780                 if ((cachep->buffer_size % PAGE_SIZE) == 0 &&
2781                             OFF_SLAB(cachep) && cachep->flags & SLAB_POISON)
2782                         kernel_map_pages(virt_to_page(objp),
2783                                          cachep->buffer_size / PAGE_SIZE, 0);
2784 #else
2785                 if (cachep->ctor)
2786                         cachep->ctor(objp);
2787 #endif
2788                 slab_bufctl(slabp)[i] = i + 1;
2789         }
2790         slab_bufctl(slabp)[i - 1] = BUFCTL_END;
2791 }
2792
2793 static void kmem_flagcheck(struct kmem_cache *cachep, gfp_t flags)
2794 {
2795         if (CONFIG_ZONE_DMA_FLAG) {
2796                 if (flags & GFP_DMA)
2797                         BUG_ON(!(cachep->gfpflags & GFP_DMA));
2798                 else
2799                         BUG_ON(cachep->gfpflags & GFP_DMA);
2800         }
2801 }
2802
2803 static void *slab_get_obj(struct kmem_cache *cachep, struct slab *slabp,
2804                                 int nodeid)
2805 {
2806         void *objp = index_to_obj(cachep, slabp, slabp->free);
2807         kmem_bufctl_t next;
2808
2809         slabp->inuse++;
2810         next = slab_bufctl(slabp)[slabp->free];
2811 #if DEBUG
2812         slab_bufctl(slabp)[slabp->free] = BUFCTL_FREE;
2813         WARN_ON(slabp->nodeid != nodeid);
2814 #endif
2815         slabp->free = next;
2816
2817         return objp;
2818 }
2819
2820 static void slab_put_obj(struct kmem_cache *cachep, struct slab *slabp,
2821                                 void *objp, int nodeid)
2822 {
2823         unsigned int objnr = obj_to_index(cachep, slabp, objp);
2824
2825 #if DEBUG
2826         /* Verify that the slab belongs to the intended node */
2827         WARN_ON(slabp->nodeid != nodeid);
2828
2829         if (slab_bufctl(slabp)[objnr] + 1 <= SLAB_LIMIT + 1) {
2830                 printk(KERN_ERR "slab: double free detected in cache "
2831                                 "'%s', objp %p\n", cachep->name, objp);
2832                 BUG();
2833         }
2834 #endif
2835         slab_bufctl(slabp)[objnr] = slabp->free;
2836         slabp->free = objnr;
2837         slabp->inuse--;
2838 }
2839
2840 /*
2841  * Map pages beginning at addr to the given cache and slab. This is required
2842  * for the slab allocator to be able to lookup the cache and slab of a
2843  * virtual address for kfree, ksize, and slab debugging.
2844  */
2845 static void slab_map_pages(struct kmem_cache *cache, struct slab *slab,
2846                            void *addr)
2847 {
2848         int nr_pages;
2849         struct page *page;
2850
2851         page = virt_to_page(addr);
2852
2853         nr_pages = 1;
2854         if (likely(!PageCompound(page)))
2855                 nr_pages <<= cache->gfporder;
2856
2857         do {
2858                 page_set_cache(page, cache);
2859                 page_set_slab(page, slab);
2860                 page++;
2861         } while (--nr_pages);
2862 }
2863
2864 /*
2865  * Grow (by 1) the number of slabs within a cache.  This is called by
2866  * kmem_cache_alloc() when there are no active objs left in a cache.
2867  */
2868 static int cache_grow(struct kmem_cache *cachep,
2869                 gfp_t flags, int nodeid, void *objp)
2870 {
2871         struct slab *slabp;
2872         size_t offset;
2873         gfp_t local_flags;
2874         struct kmem_list3 *l3;
2875
2876         /*
2877          * Be lazy and only check for valid flags here,  keeping it out of the
2878          * critical path in kmem_cache_alloc().
2879          */
2880         BUG_ON(flags & GFP_SLAB_BUG_MASK);
2881         local_flags = flags & (GFP_CONSTRAINT_MASK|GFP_RECLAIM_MASK);
2882
2883         /* Take the l3 list lock to change the colour_next on this node */
2884         check_irq_off();
2885         l3 = cachep->nodelists[nodeid];
2886         spin_lock(&l3->list_lock);
2887
2888         /* Get colour for the slab, and cal the next value. */
2889         offset = l3->colour_next;
2890         l3->colour_next++;
2891         if (l3->colour_next >= cachep->colour)
2892                 l3->colour_next = 0;
2893         spin_unlock(&l3->list_lock);
2894
2895         offset *= cachep->colour_off;
2896
2897         if (local_flags & __GFP_WAIT)
2898                 local_irq_enable();
2899
2900         /*
2901          * The test for missing atomic flag is performed here, rather than
2902          * the more obvious place, simply to reduce the critical path length
2903          * in kmem_cache_alloc(). If a caller is seriously mis-behaving they
2904          * will eventually be caught here (where it matters).
2905          */
2906         kmem_flagcheck(cachep, flags);
2907
2908         /*
2909          * Get mem for the objs.  Attempt to allocate a physical page from
2910          * 'nodeid'.
2911          */
2912         if (!objp)
2913                 objp = kmem_getpages(cachep, local_flags, nodeid);
2914         if (!objp)
2915                 goto failed;
2916
2917         /* Get slab management. */
2918         slabp = alloc_slabmgmt(cachep, objp, offset,
2919                         local_flags & ~GFP_CONSTRAINT_MASK, nodeid);
2920         if (!slabp)
2921                 goto opps1;
2922
2923         slab_map_pages(cachep, slabp, objp);
2924
2925         cache_init_objs(cachep, slabp);
2926
2927         if (local_flags & __GFP_WAIT)
2928                 local_irq_disable();
2929         check_irq_off();
2930         spin_lock(&l3->list_lock);
2931
2932         /* Make slab active. */
2933         list_add_tail(&slabp->list, &(l3->slabs_free));
2934         STATS_INC_GROWN(cachep);
2935         l3->free_objects += cachep->num;
2936         spin_unlock(&l3->list_lock);
2937         return 1;
2938 opps1:
2939         kmem_freepages(cachep, objp);
2940 failed:
2941         if (local_flags & __GFP_WAIT)
2942                 local_irq_disable();
2943         return 0;
2944 }
2945
2946 #if DEBUG
2947
2948 /*
2949  * Perform extra freeing checks:
2950  * - detect bad pointers.
2951  * - POISON/RED_ZONE checking
2952  */
2953 static void kfree_debugcheck(const void *objp)
2954 {
2955         if (!virt_addr_valid(objp)) {
2956                 printk(KERN_ERR "kfree_debugcheck: out of range ptr %lxh.\n",
2957                        (unsigned long)objp);
2958                 BUG();
2959         }
2960 }
2961
2962 static inline void verify_redzone_free(struct kmem_cache *cache, void *obj)
2963 {
2964         unsigned long long redzone1, redzone2;
2965
2966         redzone1 = *dbg_redzone1(cache, obj);
2967         redzone2 = *dbg_redzone2(cache, obj);
2968
2969         /*
2970          * Redzone is ok.
2971          */
2972         if (redzone1 == RED_ACTIVE && redzone2 == RED_ACTIVE)
2973                 return;
2974
2975         if (redzone1 == RED_INACTIVE && redzone2 == RED_INACTIVE)
2976                 slab_error(cache, "double free detected");
2977         else
2978                 slab_error(cache, "memory outside object was overwritten");
2979
2980         printk(KERN_ERR "%p: redzone 1:0x%llx, redzone 2:0x%llx.\n",
2981                         obj, redzone1, redzone2);
2982 }
2983
2984 static void *cache_free_debugcheck(struct kmem_cache *cachep, void *objp,
2985                                    void *caller)
2986 {
2987         struct page *page;
2988         unsigned int objnr;
2989         struct slab *slabp;
2990
2991         BUG_ON(virt_to_cache(objp) != cachep);
2992
2993         objp -= obj_offset(cachep);
2994         kfree_debugcheck(objp);
2995         page = virt_to_head_page(objp);
2996
2997         slabp = page_get_slab(page);
2998
2999         if (cachep->flags & SLAB_RED_ZONE) {
3000                 verify_redzone_free(cachep, objp);
3001                 *dbg_redzone1(cachep, objp) = RED_INACTIVE;
3002                 *dbg_redzone2(cachep, objp) = RED_INACTIVE;
3003         }
3004         if (cachep->flags & SLAB_STORE_USER)
3005                 *dbg_userword(cachep, objp) = caller;
3006
3007         objnr = obj_to_index(cachep, slabp, objp);
3008
3009         BUG_ON(objnr >= cachep->num);
3010         BUG_ON(objp != index_to_obj(cachep, slabp, objnr));
3011
3012 #ifdef CONFIG_DEBUG_SLAB_LEAK
3013         slab_bufctl(slabp)[objnr] = BUFCTL_FREE;
3014 #endif
3015         if (cachep->flags & SLAB_POISON) {
3016 #ifdef CONFIG_DEBUG_PAGEALLOC
3017                 if ((cachep->buffer_size % PAGE_SIZE)==0 && OFF_SLAB(cachep)) {
3018                         store_stackinfo(cachep, objp, (unsigned long)caller);
3019                         kernel_map_pages(virt_to_page(objp),
3020                                          cachep->buffer_size / PAGE_SIZE, 0);
3021                 } else {
3022                         poison_obj(cachep, objp, POISON_FREE);
3023                 }
3024 #else
3025                 poison_obj(cachep, objp, POISON_FREE);
3026 #endif
3027         }
3028         return objp;
3029 }
3030
3031 static void check_slabp(struct kmem_cache *cachep, struct slab *slabp)
3032 {
3033         kmem_bufctl_t i;
3034         int entries = 0;
3035
3036         /* Check slab's freelist to see if this obj is there. */
3037         for (i = slabp->free; i != BUFCTL_END; i = slab_bufctl(slabp)[i]) {
3038                 entries++;
3039                 if (entries > cachep->num || i >= cachep->num)
3040                         goto bad;
3041         }
3042         if (entries != cachep->num - slabp->inuse) {
3043 bad:
3044                 printk(KERN_ERR "slab: Internal list corruption detected in "
3045                                 "cache '%s'(%d), slabp %p(%d). Hexdump:\n",
3046                         cachep->name, cachep->num, slabp, slabp->inuse);
3047                 print_hex_dump(KERN_ERR, "", DUMP_PREFIX_OFFSET, 16, 1, slabp,
3048                         sizeof(*slabp) + cachep->num * sizeof(kmem_bufctl_t),
3049                         1);
3050                 BUG();
3051         }
3052 }
3053 #else
3054 #define kfree_debugcheck(x) do { } while(0)
3055 #define cache_free_debugcheck(x,objp,z) (objp)
3056 #define check_slabp(x,y) do { } while(0)
3057 #endif
3058
3059 static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags)
3060 {
3061         int batchcount;
3062         struct kmem_list3 *l3;
3063         struct array_cache *ac;
3064         int node;
3065
3066 retry:
3067         check_irq_off();
3068         node = numa_mem_id();
3069         ac = cpu_cache_get(cachep);
3070         batchcount = ac->batchcount;
3071         if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {
3072                 /*
3073                  * If there was little recent activity on this cache, then
3074                  * perform only a partial refill.  Otherwise we could generate
3075                  * refill bouncing.
3076                  */
3077                 batchcount = BATCHREFILL_LIMIT;
3078         }
3079         l3 = cachep->nodelists[node];
3080
3081         BUG_ON(ac->avail > 0 || !l3);
3082         spin_lock(&l3->list_lock);
3083
3084         /* See if we can refill from the shared array */
3085         if (l3->shared && transfer_objects(ac, l3->shared, batchcount)) {
3086                 l3->shared->touched = 1;
3087                 goto alloc_done;
3088         }
3089
3090         while (batchcount > 0) {
3091                 struct list_head *entry;
3092                 struct slab *slabp;
3093                 /* Get slab alloc is to come from. */
3094                 entry = l3->slabs_partial.next;
3095                 if (entry == &l3->slabs_partial) {
3096                         l3->free_touched = 1;
3097                         entry = l3->slabs_free.next;
3098                         if (entry == &l3->slabs_free)
3099                                 goto must_grow;
3100                 }
3101
3102                 slabp = list_entry(entry, struct slab, list);
3103                 check_slabp(cachep, slabp);
3104                 check_spinlock_acquired(cachep);
3105
3106                 /*
3107                  * The slab was either on partial or free list so
3108                  * there must be at least one object available for
3109                  * allocation.
3110                  */
3111                 BUG_ON(slabp->inuse >= cachep->num);
3112
3113                 while (slabp->inuse < cachep->num && batchcount--) {
3114                         STATS_INC_ALLOCED(cachep);
3115                         STATS_INC_ACTIVE(cachep);
3116                         STATS_SET_HIGH(cachep);
3117
3118                         ac->entry[ac->avail++] = slab_get_obj(cachep, slabp,
3119                                                             node);
3120                 }
3121                 check_slabp(cachep, slabp);
3122
3123                 /* move slabp to correct slabp list: */
3124                 list_del(&slabp->list);
3125                 if (slabp->free == BUFCTL_END)
3126                         list_add(&slabp->list, &l3->slabs_full);
3127                 else
3128                         list_add(&slabp->list, &l3->slabs_partial);
3129         }
3130
3131 must_grow:
3132         l3->free_objects -= ac->avail;
3133 alloc_done:
3134         spin_unlock(&l3->list_lock);
3135
3136         if (unlikely(!ac->avail)) {
3137                 int x;
3138                 x = cache_grow(cachep, flags | GFP_THISNODE, node, NULL);
3139
3140                 /* cache_grow can reenable interrupts, then ac could change. */
3141                 ac = cpu_cache_get(cachep);
3142                 if (!x && ac->avail == 0)       /* no objects in sight? abort */
3143                         return NULL;
3144
3145                 if (!ac->avail)         /* objects refilled by interrupt? */
3146                         goto retry;
3147         }
3148         ac->touched = 1;
3149         return ac->entry[--ac->avail];
3150 }
3151
3152 static inline void cache_alloc_debugcheck_before(struct kmem_cache *cachep,
3153                                                 gfp_t flags)
3154 {
3155         might_sleep_if(flags & __GFP_WAIT);
3156 #if DEBUG
3157         kmem_flagcheck(cachep, flags);
3158 #endif
3159 }
3160
3161 #if DEBUG
3162 static void *cache_alloc_debugcheck_after(struct kmem_cache *cachep,
3163                                 gfp_t flags, void *objp, void *caller)
3164 {
3165         if (!objp)
3166                 return objp;
3167         if (cachep->flags & SLAB_POISON) {
3168 #ifdef CONFIG_DEBUG_PAGEALLOC
3169                 if ((cachep->buffer_size % PAGE_SIZE) == 0 && OFF_SLAB(cachep))
3170                         kernel_map_pages(virt_to_page(objp),
3171                                          cachep->buffer_size / PAGE_SIZE, 1);
3172                 else
3173                         check_poison_obj(cachep, objp);
3174 #else
3175                 check_poison_obj(cachep, objp);
3176 #endif
3177                 poison_obj(cachep, objp, POISON_INUSE);
3178         }
3179         if (cachep->flags & SLAB_STORE_USER)
3180                 *dbg_userword(cachep, objp) = caller;
3181
3182         if (cachep->flags & SLAB_RED_ZONE) {
3183                 if (*dbg_redzone1(cachep, objp) != RED_INACTIVE ||
3184                                 *dbg_redzone2(cachep, objp) != RED_INACTIVE) {
3185                         slab_error(cachep, "double free, or memory outside"
3186                                                 " object was overwritten");
3187                         printk(KERN_ERR
3188                                 "%p: redzone 1:0x%llx, redzone 2:0x%llx\n",
3189                                 objp, *dbg_redzone1(cachep, objp),
3190                                 *dbg_redzone2(cachep, objp));
3191                 }
3192                 *dbg_redzone1(cachep, objp) = RED_ACTIVE;
3193                 *dbg_redzone2(cachep, objp) = RED_ACTIVE;
3194         }
3195 #ifdef CONFIG_DEBUG_SLAB_LEAK
3196         {
3197                 struct slab *slabp;
3198                 unsigned objnr;
3199
3200                 slabp = page_get_slab(virt_to_head_page(objp));
3201                 objnr = (unsigned)(objp - slabp->s_mem) / cachep->buffer_size;
3202                 slab_bufctl(slabp)[objnr] = BUFCTL_ACTIVE;
3203         }
3204 #endif
3205         objp += obj_offset(cachep);
3206         if (cachep->ctor && cachep->flags & SLAB_POISON)
3207                 cachep->ctor(objp);
3208         if (ARCH_SLAB_MINALIGN &&
3209             ((unsigned long)objp & (ARCH_SLAB_MINALIGN-1))) {
3210                 printk(KERN_ERR "0x%p: not aligned to ARCH_SLAB_MINALIGN=%d\n",
3211                        objp, (int)ARCH_SLAB_MINALIGN);
3212         }
3213         return objp;
3214 }
3215 #else
3216 #define cache_alloc_debugcheck_after(a,b,objp,d) (objp)
3217 #endif
3218
3219 static bool slab_should_failslab(struct kmem_cache *cachep, gfp_t flags)
3220 {
3221         if (cachep == &cache_cache)
3222                 return false;
3223
3224         return should_failslab(obj_size(cachep), flags, cachep->flags);
3225 }
3226
3227 static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)
3228 {
3229         void *objp;
3230         struct array_cache *ac;
3231
3232         check_irq_off();
3233
3234         ac = cpu_cache_get(cachep);
3235         if (likely(ac->avail)) {
3236                 STATS_INC_ALLOCHIT(cachep);
3237                 ac->touched = 1;
3238                 objp = ac->entry[--ac->avail];
3239         } else {
3240                 STATS_INC_ALLOCMISS(cachep);
3241                 objp = cache_alloc_refill(cachep, flags);
3242                 /*
3243                  * the 'ac' may be updated by cache_alloc_refill(),
3244                  * and kmemleak_erase() requires its correct value.
3245                  */
3246                 ac = cpu_cache_get(cachep);
3247         }
3248         /*
3249          * To avoid a false negative, if an object that is in one of the
3250          * per-CPU caches is leaked, we need to make sure kmemleak doesn't
3251          * treat the array pointers as a reference to the object.
3252          */
3253         if (objp)
3254                 kmemleak_erase(&ac->entry[ac->avail]);
3255         return objp;
3256 }
3257
3258 #ifdef CONFIG_NUMA
3259 /*
3260  * Try allocating on another node if PF_SPREAD_SLAB|PF_MEMPOLICY.
3261  *
3262  * If we are in_interrupt, then process context, including cpusets and
3263  * mempolicy, may not apply and should not be used for allocation policy.
3264  */
3265 static void *alternate_node_alloc(struct kmem_cache *cachep, gfp_t flags)
3266 {
3267         int nid_alloc, nid_here;
3268
3269         if (in_interrupt() || (flags & __GFP_THISNODE))
3270                 return NULL;
3271         nid_alloc = nid_here = numa_mem_id();
3272         get_mems_allowed();
3273         if (cpuset_do_slab_mem_spread() && (cachep->flags & SLAB_MEM_SPREAD))
3274                 nid_alloc = cpuset_slab_spread_node();
3275         else if (current->mempolicy)
3276                 nid_alloc = slab_node(current->mempolicy);
3277         put_mems_allowed();
3278         if (nid_alloc != nid_here)
3279                 return ____cache_alloc_node(cachep, flags, nid_alloc);
3280         return NULL;
3281 }
3282
3283 /*
3284  * Fallback function if there was no memory available and no objects on a
3285  * certain node and fall back is permitted. First we scan all the
3286  * available nodelists for available objects. If that fails then we
3287  * perform an allocation without specifying a node. This allows the page
3288  * allocator to do its reclaim / fallback magic. We then insert the
3289  * slab into the proper nodelist and then allocate from it.
3290  */
3291 static void *fallback_alloc(struct kmem_cache *cache, gfp_t flags)
3292 {
3293         struct zonelist *zonelist;
3294         gfp_t local_flags;
3295         struct zoneref *z;
3296         struct zone *zone;
3297         enum zone_type high_zoneidx = gfp_zone(flags);
3298         void *obj = NULL;
3299         int nid;
3300
3301         if (flags & __GFP_THISNODE)
3302                 return NULL;
3303
3304         get_mems_allowed();
3305         zonelist = node_zonelist(slab_node(current->mempolicy), flags);
3306         local_flags = flags & (GFP_CONSTRAINT_MASK|GFP_RECLAIM_MASK);
3307
3308 retry:
3309         /*
3310          * Look through allowed nodes for objects available
3311          * from existing per node queues.
3312          */
3313         for_each_zone_zonelist(zone, z, zonelist, high_zoneidx) {
3314                 nid = zone_to_nid(zone);
3315
3316                 if (cpuset_zone_allowed_hardwall(zone, flags) &&
3317                         cache->nodelists[nid] &&
3318                         cache->nodelists[nid]->free_objects) {
3319                                 obj = ____cache_alloc_node(cache,
3320                                         flags | GFP_THISNODE, nid);
3321                                 if (obj)
3322                                         break;
3323                 }
3324         }
3325
3326         if (!obj) {
3327                 /*
3328                  * This allocation will be performed within the constraints
3329                  * of the current cpuset / memory policy requirements.
3330                  * We may trigger various forms of reclaim on the allowed
3331                  * set and go into memory reserves if necessary.
3332                  */
3333                 if (local_flags & __GFP_WAIT)
3334                         local_irq_enable();
3335                 kmem_flagcheck(cache, flags);
3336                 obj = kmem_getpages(cache, local_flags, numa_mem_id());
3337                 if (local_flags & __GFP_WAIT)
3338                         local_irq_disable();
3339                 if (obj) {
3340                         /*
3341                          * Insert into the appropriate per node queues
3342                          */
3343                         nid = page_to_nid(virt_to_page(obj));
3344                         if (cache_grow(cache, flags, nid, obj)) {
3345                                 obj = ____cache_alloc_node(cache,
3346                                         flags | GFP_THISNODE, nid);
3347                                 if (!obj)
3348                                         /*
3349                                          * Another processor may allocate the
3350                                          * objects in the slab since we are
3351                                          * not holding any locks.
3352                                          */
3353                                         goto retry;
3354                         } else {
3355                                 /* cache_grow already freed obj */
3356                                 obj = NULL;
3357                         }
3358                 }
3359         }
3360         put_mems_allowed();
3361         return obj;
3362 }
3363
3364 /*
3365  * A interface to enable slab creation on nodeid
3366  */
3367 static void *____cache_alloc_node(struct kmem_cache *cachep, gfp_t flags,
3368                                 int nodeid)
3369 {
3370         struct list_head *entry;
3371         struct slab *slabp;
3372         struct kmem_list3 *l3;
3373         void *obj;
3374         int x;
3375
3376         l3 = cachep->nodelists[nodeid];
3377         BUG_ON(!l3);
3378
3379 retry:
3380         check_irq_off();
3381         spin_lock(&l3->list_lock);
3382         entry = l3->slabs_partial.next;
3383         if (entry == &l3->slabs_partial) {
3384                 l3->free_touched = 1;
3385                 entry = l3->slabs_free.next;
3386                 if (entry == &l3->slabs_free)
3387                         goto must_grow;
3388         }
3389
3390         slabp = list_entry(entry, struct slab, list);
3391         check_spinlock_acquired_node(cachep, nodeid);
3392         check_slabp(cachep, slabp);
3393
3394         STATS_INC_NODEALLOCS(cachep);
3395         STATS_INC_ACTIVE(cachep);
3396         STATS_SET_HIGH(cachep);
3397
3398         BUG_ON(slabp->inuse == cachep->num);
3399
3400         obj = slab_get_obj(cachep, slabp, nodeid);
3401         check_slabp(cachep, slabp);
3402         l3->free_objects--;
3403         /* move slabp to correct slabp list: */
3404         list_del(&slabp->list);
3405
3406         if (slabp->free == BUFCTL_END)
3407                 list_add(&slabp->list, &l3->slabs_full);
3408         else
3409                 list_add(&slabp->list, &l3->slabs_partial);
3410
3411         spin_unlock(&l3->list_lock);
3412         goto done;
3413
3414 must_grow:
3415         spin_unlock(&l3->list_lock);
3416         x = cache_grow(cachep, flags | GFP_THISNODE, nodeid, NULL);
3417         if (x)
3418                 goto retry;
3419
3420         return fallback_alloc(cachep, flags);
3421
3422 done:
3423         return obj;
3424 }
3425
3426 /**
3427  * kmem_cache_alloc_node - Allocate an object on the specified node
3428  * @cachep: The cache to allocate from.
3429  * @flags: See kmalloc().
3430  * @nodeid: node number of the target node.
3431  * @caller: return address of caller, used for debug information
3432  *
3433  * Identical to kmem_cache_alloc but it will allocate memory on the given
3434  * node, which can improve the performance for cpu bound structures.
3435  *
3436  * Fallback to other node is possible if __GFP_THISNODE is not set.
3437  */
3438 static __always_inline void *
3439 __cache_alloc_node(struct kmem_cache *cachep, gfp_t flags, int nodeid,
3440                    void *caller)
3441 {
3442         unsigned long save_flags;
3443         void *ptr;
3444         int slab_node = numa_mem_id();
3445
3446         flags &= gfp_allowed_mask;
3447
3448         lockdep_trace_alloc(flags);
3449
3450         if (slab_should_failslab(cachep, flags))
3451                 return NULL;
3452
3453         cache_alloc_debugcheck_before(cachep, flags);
3454         local_irq_save(save_flags);
3455
3456         if (nodeid == NUMA_NO_NODE)
3457                 nodeid = slab_node;
3458
3459         if (unlikely(!cachep->nodelists[nodeid])) {
3460                 /* Node not bootstrapped yet */
3461                 ptr = fallback_alloc(cachep, flags);
3462                 goto out;
3463         }
3464
3465         if (nodeid == slab_node) {
3466                 /*
3467                  * Use the locally cached objects if possible.
3468                  * However ____cache_alloc does not allow fallback
3469                  * to other nodes. It may fail while we still have
3470                  * objects on other nodes available.
3471                  */
3472                 ptr = ____cache_alloc(cachep, flags);
3473                 if (ptr)
3474                         goto out;
3475         }
3476         /* ___cache_alloc_node can fall back to other nodes */
3477         ptr = ____cache_alloc_node(cachep, flags, nodeid);
3478   out:
3479         local_irq_restore(save_flags);
3480         ptr = cache_alloc_debugcheck_after(cachep, flags, ptr, caller);
3481         kmemleak_alloc_recursive(ptr, obj_size(cachep), 1, cachep->flags,
3482                                  flags);
3483
3484         if (likely(ptr))
3485                 kmemcheck_slab_alloc(cachep, flags, ptr, obj_size(cachep));
3486
3487         if (unlikely((flags & __GFP_ZERO) && ptr))
3488                 memset(ptr, 0, obj_size(cachep));
3489
3490         return ptr;
3491 }
3492
3493 static __always_inline void *
3494 __do_cache_alloc(struct kmem_cache *cache, gfp_t flags)
3495 {
3496         void *objp;
3497
3498         if (unlikely(current->flags & (PF_SPREAD_SLAB | PF_MEMPOLICY))) {
3499                 objp = alternate_node_alloc(cache, flags);
3500                 if (objp)
3501                         goto out;
3502         }
3503         objp = ____cache_alloc(cache, flags);
3504
3505         /*
3506          * We may just have run out of memory on the local node.
3507          * ____cache_alloc_node() knows how to locate memory on other nodes
3508          */
3509         if (!objp)
3510                 objp = ____cache_alloc_node(cache, flags, numa_mem_id());
3511
3512   out:
3513         return objp;
3514 }
3515 #else
3516
3517 static __always_inline void *
3518 __do_cache_alloc(struct kmem_cache *cachep, gfp_t flags)
3519 {
3520         return ____cache_alloc(cachep, flags);
3521 }
3522