Merge branch 'master'
[linux-2.6] / 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 intializations 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/config.h>
90 #include        <linux/slab.h>
91 #include        <linux/mm.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/seq_file.h>
99 #include        <linux/notifier.h>
100 #include        <linux/kallsyms.h>
101 #include        <linux/cpu.h>
102 #include        <linux/sysctl.h>
103 #include        <linux/module.h>
104 #include        <linux/rcupdate.h>
105 #include        <linux/string.h>
106 #include        <linux/nodemask.h>
107 #include        <linux/mempolicy.h>
108 #include        <linux/mutex.h>
109
110 #include        <asm/uaccess.h>
111 #include        <asm/cacheflush.h>
112 #include        <asm/tlbflush.h>
113 #include        <asm/page.h>
114
115 /*
116  * DEBUG        - 1 for kmem_cache_create() to honour; SLAB_DEBUG_INITIAL,
117  *                SLAB_RED_ZONE & SLAB_POISON.
118  *                0 for faster, smaller code (especially in the critical paths).
119  *
120  * STATS        - 1 to collect stats for /proc/slabinfo.
121  *                0 for faster, smaller code (especially in the critical paths).
122  *
123  * FORCED_DEBUG - 1 enables SLAB_RED_ZONE and SLAB_POISON (if possible)
124  */
125
126 #ifdef CONFIG_DEBUG_SLAB
127 #define DEBUG           1
128 #define STATS           1
129 #define FORCED_DEBUG    1
130 #else
131 #define DEBUG           0
132 #define STATS           0
133 #define FORCED_DEBUG    0
134 #endif
135
136 /* Shouldn't this be in a header file somewhere? */
137 #define BYTES_PER_WORD          sizeof(void *)
138
139 #ifndef cache_line_size
140 #define cache_line_size()       L1_CACHE_BYTES
141 #endif
142
143 #ifndef ARCH_KMALLOC_MINALIGN
144 /*
145  * Enforce a minimum alignment for the kmalloc caches.
146  * Usually, the kmalloc caches are cache_line_size() aligned, except when
147  * DEBUG and FORCED_DEBUG are enabled, then they are BYTES_PER_WORD aligned.
148  * Some archs want to perform DMA into kmalloc caches and need a guaranteed
149  * alignment larger than BYTES_PER_WORD. ARCH_KMALLOC_MINALIGN allows that.
150  * Note that this flag disables some debug features.
151  */
152 #define ARCH_KMALLOC_MINALIGN 0
153 #endif
154
155 #ifndef ARCH_SLAB_MINALIGN
156 /*
157  * Enforce a minimum alignment for all caches.
158  * Intended for archs that get misalignment faults even for BYTES_PER_WORD
159  * aligned buffers. Includes ARCH_KMALLOC_MINALIGN.
160  * If possible: Do not enable this flag for CONFIG_DEBUG_SLAB, it disables
161  * some debug features.
162  */
163 #define ARCH_SLAB_MINALIGN 0
164 #endif
165
166 #ifndef ARCH_KMALLOC_FLAGS
167 #define ARCH_KMALLOC_FLAGS SLAB_HWCACHE_ALIGN
168 #endif
169
170 /* Legal flag mask for kmem_cache_create(). */
171 #if DEBUG
172 # define CREATE_MASK    (SLAB_DEBUG_INITIAL | SLAB_RED_ZONE | \
173                          SLAB_POISON | SLAB_HWCACHE_ALIGN | \
174                          SLAB_CACHE_DMA | \
175                          SLAB_MUST_HWCACHE_ALIGN | SLAB_STORE_USER | \
176                          SLAB_RECLAIM_ACCOUNT | SLAB_PANIC | \
177                          SLAB_DESTROY_BY_RCU | SLAB_MEM_SPREAD)
178 #else
179 # define CREATE_MASK    (SLAB_HWCACHE_ALIGN | \
180                          SLAB_CACHE_DMA | SLAB_MUST_HWCACHE_ALIGN | \
181                          SLAB_RECLAIM_ACCOUNT | SLAB_PANIC | \
182                          SLAB_DESTROY_BY_RCU | SLAB_MEM_SPREAD)
183 #endif
184
185 /*
186  * kmem_bufctl_t:
187  *
188  * Bufctl's are used for linking objs within a slab
189  * linked offsets.
190  *
191  * This implementation relies on "struct page" for locating the cache &
192  * slab an object belongs to.
193  * This allows the bufctl structure to be small (one int), but limits
194  * the number of objects a slab (not a cache) can contain when off-slab
195  * bufctls are used. The limit is the size of the largest general cache
196  * that does not use off-slab slabs.
197  * For 32bit archs with 4 kB pages, is this 56.
198  * This is not serious, as it is only for large objects, when it is unwise
199  * to have too many per slab.
200  * Note: This limit can be raised by introducing a general cache whose size
201  * is less than 512 (PAGE_SIZE<<3), but greater than 256.
202  */
203
204 typedef unsigned int kmem_bufctl_t;
205 #define BUFCTL_END      (((kmem_bufctl_t)(~0U))-0)
206 #define BUFCTL_FREE     (((kmem_bufctl_t)(~0U))-1)
207 #define BUFCTL_ACTIVE   (((kmem_bufctl_t)(~0U))-2)
208 #define SLAB_LIMIT      (((kmem_bufctl_t)(~0U))-3)
209
210 /* Max number of objs-per-slab for caches which use off-slab slabs.
211  * Needed to avoid a possible looping condition in cache_grow().
212  */
213 static unsigned long offslab_limit;
214
215 /*
216  * struct slab
217  *
218  * Manages the objs in a slab. Placed either at the beginning of mem allocated
219  * for a slab, or allocated from an general cache.
220  * Slabs are chained into three list: fully used, partial, fully free slabs.
221  */
222 struct slab {
223         struct list_head list;
224         unsigned long colouroff;
225         void *s_mem;            /* including colour offset */
226         unsigned int inuse;     /* num of objs active in slab */
227         kmem_bufctl_t free;
228         unsigned short nodeid;
229 };
230
231 /*
232  * struct slab_rcu
233  *
234  * slab_destroy on a SLAB_DESTROY_BY_RCU cache uses this structure to
235  * arrange for kmem_freepages to be called via RCU.  This is useful if
236  * we need to approach a kernel structure obliquely, from its address
237  * obtained without the usual locking.  We can lock the structure to
238  * stabilize it and check it's still at the given address, only if we
239  * can be sure that the memory has not been meanwhile reused for some
240  * other kind of object (which our subsystem's lock might corrupt).
241  *
242  * rcu_read_lock before reading the address, then rcu_read_unlock after
243  * taking the spinlock within the structure expected at that address.
244  *
245  * We assume struct slab_rcu can overlay struct slab when destroying.
246  */
247 struct slab_rcu {
248         struct rcu_head head;
249         struct kmem_cache *cachep;
250         void *addr;
251 };
252
253 /*
254  * struct array_cache
255  *
256  * Purpose:
257  * - LIFO ordering, to hand out cache-warm objects from _alloc
258  * - reduce the number of linked list operations
259  * - reduce spinlock operations
260  *
261  * The limit is stored in the per-cpu structure to reduce the data cache
262  * footprint.
263  *
264  */
265 struct array_cache {
266         unsigned int avail;
267         unsigned int limit;
268         unsigned int batchcount;
269         unsigned int touched;
270         spinlock_t lock;
271         void *entry[0]; /*
272                          * Must have this definition in here for the proper
273                          * alignment of array_cache. Also simplifies accessing
274                          * the entries.
275                          * [0] is for gcc 2.95. It should really be [].
276                          */
277 };
278
279 /*
280  * bootstrap: The caches do not work without cpuarrays anymore, but the
281  * cpuarrays are allocated from the generic caches...
282  */
283 #define BOOT_CPUCACHE_ENTRIES   1
284 struct arraycache_init {
285         struct array_cache cache;
286         void *entries[BOOT_CPUCACHE_ENTRIES];
287 };
288
289 /*
290  * The slab lists for all objects.
291  */
292 struct kmem_list3 {
293         struct list_head slabs_partial; /* partial list first, better asm code */
294         struct list_head slabs_full;
295         struct list_head slabs_free;
296         unsigned long free_objects;
297         unsigned int free_limit;
298         unsigned int colour_next;       /* Per-node cache coloring */
299         spinlock_t list_lock;
300         struct array_cache *shared;     /* shared per node */
301         struct array_cache **alien;     /* on other nodes */
302         unsigned long next_reap;        /* updated without locking */
303         int free_touched;               /* updated without locking */
304 };
305
306 /*
307  * Need this for bootstrapping a per node allocator.
308  */
309 #define NUM_INIT_LISTS (2 * MAX_NUMNODES + 1)
310 struct kmem_list3 __initdata initkmem_list3[NUM_INIT_LISTS];
311 #define CACHE_CACHE 0
312 #define SIZE_AC 1
313 #define SIZE_L3 (1 + MAX_NUMNODES)
314
315 /*
316  * This function must be completely optimized away if a constant is passed to
317  * it.  Mostly the same as what is in linux/slab.h except it returns an index.
318  */
319 static __always_inline int index_of(const size_t size)
320 {
321         extern void __bad_size(void);
322
323         if (__builtin_constant_p(size)) {
324                 int i = 0;
325
326 #define CACHE(x) \
327         if (size <=x) \
328                 return i; \
329         else \
330                 i++;
331 #include "linux/kmalloc_sizes.h"
332 #undef CACHE
333                 __bad_size();
334         } else
335                 __bad_size();
336         return 0;
337 }
338
339 #define INDEX_AC index_of(sizeof(struct arraycache_init))
340 #define INDEX_L3 index_of(sizeof(struct kmem_list3))
341
342 static void kmem_list3_init(struct kmem_list3 *parent)
343 {
344         INIT_LIST_HEAD(&parent->slabs_full);
345         INIT_LIST_HEAD(&parent->slabs_partial);
346         INIT_LIST_HEAD(&parent->slabs_free);
347         parent->shared = NULL;
348         parent->alien = NULL;
349         parent->colour_next = 0;
350         spin_lock_init(&parent->list_lock);
351         parent->free_objects = 0;
352         parent->free_touched = 0;
353 }
354
355 #define MAKE_LIST(cachep, listp, slab, nodeid)                          \
356         do {                                                            \
357                 INIT_LIST_HEAD(listp);                                  \
358                 list_splice(&(cachep->nodelists[nodeid]->slab), listp); \
359         } while (0)
360
361 #define MAKE_ALL_LISTS(cachep, ptr, nodeid)                             \
362         do {                                                            \
363         MAKE_LIST((cachep), (&(ptr)->slabs_full), slabs_full, nodeid);  \
364         MAKE_LIST((cachep), (&(ptr)->slabs_partial), slabs_partial, nodeid); \
365         MAKE_LIST((cachep), (&(ptr)->slabs_free), slabs_free, nodeid);  \
366         } while (0)
367
368 /*
369  * struct kmem_cache
370  *
371  * manages a cache.
372  */
373
374 struct kmem_cache {
375 /* 1) per-cpu data, touched during every alloc/free */
376         struct array_cache *array[NR_CPUS];
377 /* 2) Cache tunables. Protected by cache_chain_mutex */
378         unsigned int batchcount;
379         unsigned int limit;
380         unsigned int shared;
381
382         unsigned int buffer_size;
383 /* 3) touched by every alloc & free from the backend */
384         struct kmem_list3 *nodelists[MAX_NUMNODES];
385
386         unsigned int flags;             /* constant flags */
387         unsigned int num;               /* # of objs per slab */
388
389 /* 4) cache_grow/shrink */
390         /* order of pgs per slab (2^n) */
391         unsigned int gfporder;
392
393         /* force GFP flags, e.g. GFP_DMA */
394         gfp_t gfpflags;
395
396         size_t colour;                  /* cache colouring range */
397         unsigned int colour_off;        /* colour offset */
398         struct kmem_cache *slabp_cache;
399         unsigned int slab_size;
400         unsigned int dflags;            /* dynamic flags */
401
402         /* constructor func */
403         void (*ctor) (void *, struct kmem_cache *, unsigned long);
404
405         /* de-constructor func */
406         void (*dtor) (void *, struct kmem_cache *, unsigned long);
407
408 /* 5) cache creation/removal */
409         const char *name;
410         struct list_head next;
411
412 /* 6) statistics */
413 #if STATS
414         unsigned long num_active;
415         unsigned long num_allocations;
416         unsigned long high_mark;
417         unsigned long grown;
418         unsigned long reaped;
419         unsigned long errors;
420         unsigned long max_freeable;
421         unsigned long node_allocs;
422         unsigned long node_frees;
423         unsigned long node_overflow;
424         atomic_t allochit;
425         atomic_t allocmiss;
426         atomic_t freehit;
427         atomic_t freemiss;
428 #endif
429 #if DEBUG
430         /*
431          * If debugging is enabled, then the allocator can add additional
432          * fields and/or padding to every object. buffer_size contains the total
433          * object size including these internal fields, the following two
434          * variables contain the offset to the user object and its size.
435          */
436         int obj_offset;
437         int obj_size;
438 #endif
439 };
440
441 #define CFLGS_OFF_SLAB          (0x80000000UL)
442 #define OFF_SLAB(x)     ((x)->flags & CFLGS_OFF_SLAB)
443
444 #define BATCHREFILL_LIMIT       16
445 /*
446  * Optimization question: fewer reaps means less probability for unnessary
447  * cpucache drain/refill cycles.
448  *
449  * OTOH the cpuarrays can contain lots of objects,
450  * which could lock up otherwise freeable slabs.
451  */
452 #define REAPTIMEOUT_CPUC        (2*HZ)
453 #define REAPTIMEOUT_LIST3       (4*HZ)
454
455 #if STATS
456 #define STATS_INC_ACTIVE(x)     ((x)->num_active++)
457 #define STATS_DEC_ACTIVE(x)     ((x)->num_active--)
458 #define STATS_INC_ALLOCED(x)    ((x)->num_allocations++)
459 #define STATS_INC_GROWN(x)      ((x)->grown++)
460 #define STATS_INC_REAPED(x)     ((x)->reaped++)
461 #define STATS_SET_HIGH(x)                                               \
462         do {                                                            \
463                 if ((x)->num_active > (x)->high_mark)                   \
464                         (x)->high_mark = (x)->num_active;               \
465         } while (0)
466 #define STATS_INC_ERR(x)        ((x)->errors++)
467 #define STATS_INC_NODEALLOCS(x) ((x)->node_allocs++)
468 #define STATS_INC_NODEFREES(x)  ((x)->node_frees++)
469 #define STATS_INC_ACOVERFLOW(x)   ((x)->node_overflow++)
470 #define STATS_SET_FREEABLE(x, i)                                        \
471         do {                                                            \
472                 if ((x)->max_freeable < i)                              \
473                         (x)->max_freeable = i;                          \
474         } while (0)
475 #define STATS_INC_ALLOCHIT(x)   atomic_inc(&(x)->allochit)
476 #define STATS_INC_ALLOCMISS(x)  atomic_inc(&(x)->allocmiss)
477 #define STATS_INC_FREEHIT(x)    atomic_inc(&(x)->freehit)
478 #define STATS_INC_FREEMISS(x)   atomic_inc(&(x)->freemiss)
479 #else
480 #define STATS_INC_ACTIVE(x)     do { } while (0)
481 #define STATS_DEC_ACTIVE(x)     do { } while (0)
482 #define STATS_INC_ALLOCED(x)    do { } while (0)
483 #define STATS_INC_GROWN(x)      do { } while (0)
484 #define STATS_INC_REAPED(x)     do { } while (0)
485 #define STATS_SET_HIGH(x)       do { } while (0)
486 #define STATS_INC_ERR(x)        do { } while (0)
487 #define STATS_INC_NODEALLOCS(x) do { } while (0)
488 #define STATS_INC_NODEFREES(x)  do { } while (0)
489 #define STATS_INC_ACOVERFLOW(x)   do { } while (0)
490 #define STATS_SET_FREEABLE(x, i) do { } while (0)
491 #define STATS_INC_ALLOCHIT(x)   do { } while (0)
492 #define STATS_INC_ALLOCMISS(x)  do { } while (0)
493 #define STATS_INC_FREEHIT(x)    do { } while (0)
494 #define STATS_INC_FREEMISS(x)   do { } while (0)
495 #endif
496
497 #if DEBUG
498 /*
499  * Magic nums for obj red zoning.
500  * Placed in the first word before and the first word after an obj.
501  */
502 #define RED_INACTIVE    0x5A2CF071UL    /* when obj is inactive */
503 #define RED_ACTIVE      0x170FC2A5UL    /* when obj is active */
504
505 /* ...and for poisoning */
506 #define POISON_INUSE    0x5a    /* for use-uninitialised poisoning */
507 #define POISON_FREE     0x6b    /* for use-after-free poisoning */
508 #define POISON_END      0xa5    /* end-byte of poisoning */
509
510 /*
511  * memory layout of objects:
512  * 0            : objp
513  * 0 .. cachep->obj_offset - BYTES_PER_WORD - 1: padding. This ensures that
514  *              the end of an object is aligned with the end of the real
515  *              allocation. Catches writes behind the end of the allocation.
516  * cachep->obj_offset - BYTES_PER_WORD .. cachep->obj_offset - 1:
517  *              redzone word.
518  * cachep->obj_offset: The real object.
519  * cachep->buffer_size - 2* BYTES_PER_WORD: redzone word [BYTES_PER_WORD long]
520  * cachep->buffer_size - 1* BYTES_PER_WORD: last caller address
521  *                                      [BYTES_PER_WORD long]
522  */
523 static int obj_offset(struct kmem_cache *cachep)
524 {
525         return cachep->obj_offset;
526 }
527
528 static int obj_size(struct kmem_cache *cachep)
529 {
530         return cachep->obj_size;
531 }
532
533 static unsigned long *dbg_redzone1(struct kmem_cache *cachep, void *objp)
534 {
535         BUG_ON(!(cachep->flags & SLAB_RED_ZONE));
536         return (unsigned long*) (objp+obj_offset(cachep)-BYTES_PER_WORD);
537 }
538
539 static unsigned long *dbg_redzone2(struct kmem_cache *cachep, void *objp)
540 {
541         BUG_ON(!(cachep->flags & SLAB_RED_ZONE));
542         if (cachep->flags & SLAB_STORE_USER)
543                 return (unsigned long *)(objp + cachep->buffer_size -
544                                          2 * BYTES_PER_WORD);
545         return (unsigned long *)(objp + cachep->buffer_size - BYTES_PER_WORD);
546 }
547
548 static void **dbg_userword(struct kmem_cache *cachep, void *objp)
549 {
550         BUG_ON(!(cachep->flags & SLAB_STORE_USER));
551         return (void **)(objp + cachep->buffer_size - BYTES_PER_WORD);
552 }
553
554 #else
555
556 #define obj_offset(x)                   0
557 #define obj_size(cachep)                (cachep->buffer_size)
558 #define dbg_redzone1(cachep, objp)      ({BUG(); (unsigned long *)NULL;})
559 #define dbg_redzone2(cachep, objp)      ({BUG(); (unsigned long *)NULL;})
560 #define dbg_userword(cachep, objp)      ({BUG(); (void **)NULL;})
561
562 #endif
563
564 /*
565  * Maximum size of an obj (in 2^order pages) and absolute limit for the gfp
566  * order.
567  */
568 #if defined(CONFIG_LARGE_ALLOCS)
569 #define MAX_OBJ_ORDER   13      /* up to 32Mb */
570 #define MAX_GFP_ORDER   13      /* up to 32Mb */
571 #elif defined(CONFIG_MMU)
572 #define MAX_OBJ_ORDER   5       /* 32 pages */
573 #define MAX_GFP_ORDER   5       /* 32 pages */
574 #else
575 #define MAX_OBJ_ORDER   8       /* up to 1Mb */
576 #define MAX_GFP_ORDER   8       /* up to 1Mb */
577 #endif
578
579 /*
580  * Do not go above this order unless 0 objects fit into the slab.
581  */
582 #define BREAK_GFP_ORDER_HI      1
583 #define BREAK_GFP_ORDER_LO      0
584 static int slab_break_gfp_order = BREAK_GFP_ORDER_LO;
585
586 /*
587  * Functions for storing/retrieving the cachep and or slab from the page
588  * allocator.  These are used to find the slab an obj belongs to.  With kfree(),
589  * these are used to find the cache which an obj belongs to.
590  */
591 static inline void page_set_cache(struct page *page, struct kmem_cache *cache)
592 {
593         page->lru.next = (struct list_head *)cache;
594 }
595
596 static inline struct kmem_cache *page_get_cache(struct page *page)
597 {
598         if (unlikely(PageCompound(page)))
599                 page = (struct page *)page_private(page);
600         return (struct kmem_cache *)page->lru.next;
601 }
602
603 static inline void page_set_slab(struct page *page, struct slab *slab)
604 {
605         page->lru.prev = (struct list_head *)slab;
606 }
607
608 static inline struct slab *page_get_slab(struct page *page)
609 {
610         if (unlikely(PageCompound(page)))
611                 page = (struct page *)page_private(page);
612         return (struct slab *)page->lru.prev;
613 }
614
615 static inline struct kmem_cache *virt_to_cache(const void *obj)
616 {
617         struct page *page = virt_to_page(obj);
618         return page_get_cache(page);
619 }
620
621 static inline struct slab *virt_to_slab(const void *obj)
622 {
623         struct page *page = virt_to_page(obj);
624         return page_get_slab(page);
625 }
626
627 static inline void *index_to_obj(struct kmem_cache *cache, struct slab *slab,
628                                  unsigned int idx)
629 {
630         return slab->s_mem + cache->buffer_size * idx;
631 }
632
633 static inline unsigned int obj_to_index(struct kmem_cache *cache,
634                                         struct slab *slab, void *obj)
635 {
636         return (unsigned)(obj - slab->s_mem) / cache->buffer_size;
637 }
638
639 /*
640  * These are the default caches for kmalloc. Custom caches can have other sizes.
641  */
642 struct cache_sizes malloc_sizes[] = {
643 #define CACHE(x) { .cs_size = (x) },
644 #include <linux/kmalloc_sizes.h>
645         CACHE(ULONG_MAX)
646 #undef CACHE
647 };
648 EXPORT_SYMBOL(malloc_sizes);
649
650 /* Must match cache_sizes above. Out of line to keep cache footprint low. */
651 struct cache_names {
652         char *name;
653         char *name_dma;
654 };
655
656 static struct cache_names __initdata cache_names[] = {
657 #define CACHE(x) { .name = "size-" #x, .name_dma = "size-" #x "(DMA)" },
658 #include <linux/kmalloc_sizes.h>
659         {NULL,}
660 #undef CACHE
661 };
662
663 static struct arraycache_init initarray_cache __initdata =
664     { {0, BOOT_CPUCACHE_ENTRIES, 1, 0} };
665 static struct arraycache_init initarray_generic =
666     { {0, BOOT_CPUCACHE_ENTRIES, 1, 0} };
667
668 /* internal cache of cache description objs */
669 static struct kmem_cache cache_cache = {
670         .batchcount = 1,
671         .limit = BOOT_CPUCACHE_ENTRIES,
672         .shared = 1,
673         .buffer_size = sizeof(struct kmem_cache),
674         .name = "kmem_cache",
675 #if DEBUG
676         .obj_size = sizeof(struct kmem_cache),
677 #endif
678 };
679
680 /* Guard access to the cache-chain. */
681 static DEFINE_MUTEX(cache_chain_mutex);
682 static struct list_head cache_chain;
683
684 /*
685  * vm_enough_memory() looks at this to determine how many slab-allocated pages
686  * are possibly freeable under pressure
687  *
688  * SLAB_RECLAIM_ACCOUNT turns this on per-slab
689  */
690 atomic_t slab_reclaim_pages;
691
692 /*
693  * chicken and egg problem: delay the per-cpu array allocation
694  * until the general caches are up.
695  */
696 static enum {
697         NONE,
698         PARTIAL_AC,
699         PARTIAL_L3,
700         FULL
701 } g_cpucache_up;
702
703 static DEFINE_PER_CPU(struct work_struct, reap_work);
704
705 static void free_block(struct kmem_cache *cachep, void **objpp, int len,
706                         int node);
707 static void enable_cpucache(struct kmem_cache *cachep);
708 static void cache_reap(void *unused);
709 static int __node_shrink(struct kmem_cache *cachep, int node);
710
711 static inline struct array_cache *cpu_cache_get(struct kmem_cache *cachep)
712 {
713         return cachep->array[smp_processor_id()];
714 }
715
716 static inline struct kmem_cache *__find_general_cachep(size_t size,
717                                                         gfp_t gfpflags)
718 {
719         struct cache_sizes *csizep = malloc_sizes;
720
721 #if DEBUG
722         /* This happens if someone tries to call
723          * kmem_cache_create(), or __kmalloc(), before
724          * the generic caches are initialized.
725          */
726         BUG_ON(malloc_sizes[INDEX_AC].cs_cachep == NULL);
727 #endif
728         while (size > csizep->cs_size)
729                 csizep++;
730
731         /*
732          * Really subtle: The last entry with cs->cs_size==ULONG_MAX
733          * has cs_{dma,}cachep==NULL. Thus no special case
734          * for large kmalloc calls required.
735          */
736         if (unlikely(gfpflags & GFP_DMA))
737                 return csizep->cs_dmacachep;
738         return csizep->cs_cachep;
739 }
740
741 struct kmem_cache *kmem_find_general_cachep(size_t size, gfp_t gfpflags)
742 {
743         return __find_general_cachep(size, gfpflags);
744 }
745 EXPORT_SYMBOL(kmem_find_general_cachep);
746
747 static size_t slab_mgmt_size(size_t nr_objs, size_t align)
748 {
749         return ALIGN(sizeof(struct slab)+nr_objs*sizeof(kmem_bufctl_t), align);
750 }
751
752 /*
753  * Calculate the number of objects and left-over bytes for a given buffer size.
754  */
755 static void cache_estimate(unsigned long gfporder, size_t buffer_size,
756                            size_t align, int flags, size_t *left_over,
757                            unsigned int *num)
758 {
759         int nr_objs;
760         size_t mgmt_size;
761         size_t slab_size = PAGE_SIZE << gfporder;
762
763         /*
764          * The slab management structure can be either off the slab or
765          * on it. For the latter case, the memory allocated for a
766          * slab is used for:
767          *
768          * - The struct slab
769          * - One kmem_bufctl_t for each object
770          * - Padding to respect alignment of @align
771          * - @buffer_size bytes for each object
772          *
773          * If the slab management structure is off the slab, then the
774          * alignment will already be calculated into the size. Because
775          * the slabs are all pages aligned, the objects will be at the
776          * correct alignment when allocated.
777          */
778         if (flags & CFLGS_OFF_SLAB) {
779                 mgmt_size = 0;
780                 nr_objs = slab_size / buffer_size;
781
782                 if (nr_objs > SLAB_LIMIT)
783                         nr_objs = SLAB_LIMIT;
784         } else {
785                 /*
786                  * Ignore padding for the initial guess. The padding
787                  * is at most @align-1 bytes, and @buffer_size is at
788                  * least @align. In the worst case, this result will
789                  * be one greater than the number of objects that fit
790                  * into the memory allocation when taking the padding
791                  * into account.
792                  */
793                 nr_objs = (slab_size - sizeof(struct slab)) /
794                           (buffer_size + sizeof(kmem_bufctl_t));
795
796                 /*
797                  * This calculated number will be either the right
798                  * amount, or one greater than what we want.
799                  */
800                 if (slab_mgmt_size(nr_objs, align) + nr_objs*buffer_size
801                        > slab_size)
802                         nr_objs--;
803
804                 if (nr_objs > SLAB_LIMIT)
805                         nr_objs = SLAB_LIMIT;
806
807                 mgmt_size = slab_mgmt_size(nr_objs, align);
808         }
809         *num = nr_objs;
810         *left_over = slab_size - nr_objs*buffer_size - mgmt_size;
811 }
812
813 #define slab_error(cachep, msg) __slab_error(__FUNCTION__, cachep, msg)
814
815 static void __slab_error(const char *function, struct kmem_cache *cachep,
816                         char *msg)
817 {
818         printk(KERN_ERR "slab error in %s(): cache `%s': %s\n",
819                function, cachep->name, msg);
820         dump_stack();
821 }
822
823 #ifdef CONFIG_NUMA
824 /*
825  * Special reaping functions for NUMA systems called from cache_reap().
826  * These take care of doing round robin flushing of alien caches (containing
827  * objects freed on different nodes from which they were allocated) and the
828  * flushing of remote pcps by calling drain_node_pages.
829  */
830 static DEFINE_PER_CPU(unsigned long, reap_node);
831
832 static void init_reap_node(int cpu)
833 {
834         int node;
835
836         node = next_node(cpu_to_node(cpu), node_online_map);
837         if (node == MAX_NUMNODES)
838                 node = first_node(node_online_map);
839
840         __get_cpu_var(reap_node) = node;
841 }
842
843 static void next_reap_node(void)
844 {
845         int node = __get_cpu_var(reap_node);
846
847         /*
848          * Also drain per cpu pages on remote zones
849          */
850         if (node != numa_node_id())
851                 drain_node_pages(node);
852
853         node = next_node(node, node_online_map);
854         if (unlikely(node >= MAX_NUMNODES))
855                 node = first_node(node_online_map);
856         __get_cpu_var(reap_node) = node;
857 }
858
859 #else
860 #define init_reap_node(cpu) do { } while (0)
861 #define next_reap_node(void) do { } while (0)
862 #endif
863
864 /*
865  * Initiate the reap timer running on the target CPU.  We run at around 1 to 2Hz
866  * via the workqueue/eventd.
867  * Add the CPU number into the expiration time to minimize the possibility of
868  * the CPUs getting into lockstep and contending for the global cache chain
869  * lock.
870  */
871 static void __devinit start_cpu_timer(int cpu)
872 {
873         struct work_struct *reap_work = &per_cpu(reap_work, cpu);
874
875         /*
876          * When this gets called from do_initcalls via cpucache_init(),
877          * init_workqueues() has already run, so keventd will be setup
878          * at that time.
879          */
880         if (keventd_up() && reap_work->func == NULL) {
881                 init_reap_node(cpu);
882                 INIT_WORK(reap_work, cache_reap, NULL);
883                 schedule_delayed_work_on(cpu, reap_work, HZ + 3 * cpu);
884         }
885 }
886
887 static struct array_cache *alloc_arraycache(int node, int entries,
888                                             int batchcount)
889 {
890         int memsize = sizeof(void *) * entries + sizeof(struct array_cache);
891         struct array_cache *nc = NULL;
892
893         nc = kmalloc_node(memsize, GFP_KERNEL, node);
894         if (nc) {
895                 nc->avail = 0;
896                 nc->limit = entries;
897                 nc->batchcount = batchcount;
898                 nc->touched = 0;
899                 spin_lock_init(&nc->lock);
900         }
901         return nc;
902 }
903
904 /*
905  * Transfer objects in one arraycache to another.
906  * Locking must be handled by the caller.
907  *
908  * Return the number of entries transferred.
909  */
910 static int transfer_objects(struct array_cache *to,
911                 struct array_cache *from, unsigned int max)
912 {
913         /* Figure out how many entries to transfer */
914         int nr = min(min(from->avail, max), to->limit - to->avail);
915
916         if (!nr)
917                 return 0;
918
919         memcpy(to->entry + to->avail, from->entry + from->avail -nr,
920                         sizeof(void *) *nr);
921
922         from->avail -= nr;
923         to->avail += nr;
924         to->touched = 1;
925         return nr;
926 }
927
928 #ifdef CONFIG_NUMA
929 static void *__cache_alloc_node(struct kmem_cache *, gfp_t, int);
930 static void *alternate_node_alloc(struct kmem_cache *, gfp_t);
931
932 static struct array_cache **alloc_alien_cache(int node, int limit)
933 {
934         struct array_cache **ac_ptr;
935         int memsize = sizeof(void *) * MAX_NUMNODES;
936         int i;
937
938         if (limit > 1)
939                 limit = 12;
940         ac_ptr = kmalloc_node(memsize, GFP_KERNEL, node);
941         if (ac_ptr) {
942                 for_each_node(i) {
943                         if (i == node || !node_online(i)) {
944                                 ac_ptr[i] = NULL;
945                                 continue;
946                         }
947                         ac_ptr[i] = alloc_arraycache(node, limit, 0xbaadf00d);
948                         if (!ac_ptr[i]) {
949                                 for (i--; i <= 0; i--)
950                                         kfree(ac_ptr[i]);
951                                 kfree(ac_ptr);
952                                 return NULL;
953                         }
954                 }
955         }
956         return ac_ptr;
957 }
958
959 static void free_alien_cache(struct array_cache **ac_ptr)
960 {
961         int i;
962
963         if (!ac_ptr)
964                 return;
965         for_each_node(i)
966             kfree(ac_ptr[i]);
967         kfree(ac_ptr);
968 }
969
970 static void __drain_alien_cache(struct kmem_cache *cachep,
971                                 struct array_cache *ac, int node)
972 {
973         struct kmem_list3 *rl3 = cachep->nodelists[node];
974
975         if (ac->avail) {
976                 spin_lock(&rl3->list_lock);
977                 /*
978                  * Stuff objects into the remote nodes shared array first.
979                  * That way we could avoid the overhead of putting the objects
980                  * into the free lists and getting them back later.
981                  */
982                 transfer_objects(rl3->shared, ac, ac->limit);
983
984                 free_block(cachep, ac->entry, ac->avail, node);
985                 ac->avail = 0;
986                 spin_unlock(&rl3->list_lock);
987         }
988 }
989
990 /*
991  * Called from cache_reap() to regularly drain alien caches round robin.
992  */
993 static void reap_alien(struct kmem_cache *cachep, struct kmem_list3 *l3)
994 {
995         int node = __get_cpu_var(reap_node);
996
997         if (l3->alien) {
998                 struct array_cache *ac = l3->alien[node];
999
1000                 if (ac && ac->avail && spin_trylock_irq(&ac->lock)) {
1001                         __drain_alien_cache(cachep, ac, node);
1002                         spin_unlock_irq(&ac->lock);
1003                 }
1004         }
1005 }
1006
1007 static void drain_alien_cache(struct kmem_cache *cachep,
1008                                 struct array_cache **alien)
1009 {
1010         int i = 0;
1011         struct array_cache *ac;
1012         unsigned long flags;
1013
1014         for_each_online_node(i) {
1015                 ac = alien[i];
1016                 if (ac) {
1017                         spin_lock_irqsave(&ac->lock, flags);
1018                         __drain_alien_cache(cachep, ac, i);
1019                         spin_unlock_irqrestore(&ac->lock, flags);
1020                 }
1021         }
1022 }
1023 #else
1024
1025 #define drain_alien_cache(cachep, alien) do { } while (0)
1026 #define reap_alien(cachep, l3) do { } while (0)
1027
1028 static inline struct array_cache **alloc_alien_cache(int node, int limit)
1029 {
1030         return (struct array_cache **) 0x01020304ul;
1031 }
1032
1033 static inline void free_alien_cache(struct array_cache **ac_ptr)
1034 {
1035 }
1036
1037 #endif
1038
1039 static int __devinit cpuup_callback(struct notifier_block *nfb,
1040                                     unsigned long action, void *hcpu)
1041 {
1042         long cpu = (long)hcpu;
1043         struct kmem_cache *cachep;
1044         struct kmem_list3 *l3 = NULL;
1045         int node = cpu_to_node(cpu);
1046         int memsize = sizeof(struct kmem_list3);
1047
1048         switch (action) {
1049         case CPU_UP_PREPARE:
1050                 mutex_lock(&cache_chain_mutex);
1051                 /*
1052                  * We need to do this right in the beginning since
1053                  * alloc_arraycache's are going to use this list.
1054                  * kmalloc_node allows us to add the slab to the right
1055                  * kmem_list3 and not this cpu's kmem_list3
1056                  */
1057
1058                 list_for_each_entry(cachep, &cache_chain, next) {
1059                         /*
1060                          * Set up the size64 kmemlist for cpu before we can
1061                          * begin anything. Make sure some other cpu on this
1062                          * node has not already allocated this
1063                          */
1064                         if (!cachep->nodelists[node]) {
1065                                 l3 = kmalloc_node(memsize, GFP_KERNEL, node);
1066                                 if (!l3)
1067                                         goto bad;
1068                                 kmem_list3_init(l3);
1069                                 l3->next_reap = jiffies + REAPTIMEOUT_LIST3 +
1070                                     ((unsigned long)cachep) % REAPTIMEOUT_LIST3;
1071
1072                                 /*
1073                                  * The l3s don't come and go as CPUs come and
1074                                  * go.  cache_chain_mutex is sufficient
1075                                  * protection here.
1076                                  */
1077                                 cachep->nodelists[node] = l3;
1078                         }
1079
1080                         spin_lock_irq(&cachep->nodelists[node]->list_lock);
1081                         cachep->nodelists[node]->free_limit =
1082                                 (1 + nr_cpus_node(node)) *
1083                                 cachep->batchcount + cachep->num;
1084                         spin_unlock_irq(&cachep->nodelists[node]->list_lock);
1085                 }
1086
1087                 /*
1088                  * Now we can go ahead with allocating the shared arrays and
1089                  * array caches
1090                  */
1091                 list_for_each_entry(cachep, &cache_chain, next) {
1092                         struct array_cache *nc;
1093                         struct array_cache *shared;
1094                         struct array_cache **alien;
1095
1096                         nc = alloc_arraycache(node, cachep->limit,
1097                                                 cachep->batchcount);
1098                         if (!nc)
1099                                 goto bad;
1100                         shared = alloc_arraycache(node,
1101                                         cachep->shared * cachep->batchcount,
1102                                         0xbaadf00d);
1103                         if (!shared)
1104                                 goto bad;
1105
1106                         alien = alloc_alien_cache(node, cachep->limit);
1107                         if (!alien)
1108                                 goto bad;
1109                         cachep->array[cpu] = nc;
1110                         l3 = cachep->nodelists[node];
1111                         BUG_ON(!l3);
1112
1113                         spin_lock_irq(&l3->list_lock);
1114                         if (!l3->shared) {
1115                                 /*
1116                                  * We are serialised from CPU_DEAD or
1117                                  * CPU_UP_CANCELLED by the cpucontrol lock
1118                                  */
1119                                 l3->shared = shared;
1120                                 shared = NULL;
1121                         }
1122 #ifdef CONFIG_NUMA
1123                         if (!l3->alien) {
1124                                 l3->alien = alien;
1125                                 alien = NULL;
1126                         }
1127 #endif
1128                         spin_unlock_irq(&l3->list_lock);
1129                         kfree(shared);
1130                         free_alien_cache(alien);
1131                 }
1132                 mutex_unlock(&cache_chain_mutex);
1133                 break;
1134         case CPU_ONLINE:
1135                 start_cpu_timer(cpu);
1136                 break;
1137 #ifdef CONFIG_HOTPLUG_CPU
1138         case CPU_DEAD:
1139                 /*
1140                  * Even if all the cpus of a node are down, we don't free the
1141                  * kmem_list3 of any cache. This to avoid a race between
1142                  * cpu_down, and a kmalloc allocation from another cpu for
1143                  * memory from the node of the cpu going down.  The list3
1144                  * structure is usually allocated from kmem_cache_create() and
1145                  * gets destroyed at kmem_cache_destroy().
1146                  */
1147                 /* fall thru */
1148         case CPU_UP_CANCELED:
1149                 mutex_lock(&cache_chain_mutex);
1150                 list_for_each_entry(cachep, &cache_chain, next) {
1151                         struct array_cache *nc;
1152                         struct array_cache *shared;
1153                         struct array_cache **alien;
1154                         cpumask_t mask;
1155
1156                         mask = node_to_cpumask(node);
1157                         /* cpu is dead; no one can alloc from it. */
1158                         nc = cachep->array[cpu];
1159                         cachep->array[cpu] = NULL;
1160                         l3 = cachep->nodelists[node];
1161
1162                         if (!l3)
1163                                 goto free_array_cache;
1164
1165                         spin_lock_irq(&l3->list_lock);
1166
1167                         /* Free limit for this kmem_list3 */
1168                         l3->free_limit -= cachep->batchcount;
1169                         if (nc)
1170                                 free_block(cachep, nc->entry, nc->avail, node);
1171
1172                         if (!cpus_empty(mask)) {
1173                                 spin_unlock_irq(&l3->list_lock);
1174                                 goto free_array_cache;
1175                         }
1176
1177                         shared = l3->shared;
1178                         if (shared) {
1179                                 free_block(cachep, l3->shared->entry,
1180                                            l3->shared->avail, node);
1181                                 l3->shared = NULL;
1182                         }
1183
1184                         alien = l3->alien;
1185                         l3->alien = NULL;
1186
1187                         spin_unlock_irq(&l3->list_lock);
1188
1189                         kfree(shared);
1190                         if (alien) {
1191                                 drain_alien_cache(cachep, alien);
1192                                 free_alien_cache(alien);
1193                         }
1194 free_array_cache:
1195                         kfree(nc);
1196                 }
1197                 /*
1198                  * In the previous loop, all the objects were freed to
1199                  * the respective cache's slabs,  now we can go ahead and
1200                  * shrink each nodelist to its limit.
1201                  */
1202                 list_for_each_entry(cachep, &cache_chain, next) {
1203                         l3 = cachep->nodelists[node];
1204                         if (!l3)
1205                                 continue;
1206                         spin_lock_irq(&l3->list_lock);
1207                         /* free slabs belonging to this node */
1208                         __node_shrink(cachep, node);
1209                         spin_unlock_irq(&l3->list_lock);
1210                 }
1211                 mutex_unlock(&cache_chain_mutex);
1212                 break;
1213 #endif
1214         }
1215         return NOTIFY_OK;
1216 bad:
1217         mutex_unlock(&cache_chain_mutex);
1218         return NOTIFY_BAD;
1219 }
1220
1221 static struct notifier_block cpucache_notifier = { &cpuup_callback, NULL, 0 };
1222
1223 /*
1224  * swap the static kmem_list3 with kmalloced memory
1225  */
1226 static void init_list(struct kmem_cache *cachep, struct kmem_list3 *list,
1227                         int nodeid)
1228 {
1229         struct kmem_list3 *ptr;
1230
1231         BUG_ON(cachep->nodelists[nodeid] != list);
1232         ptr = kmalloc_node(sizeof(struct kmem_list3), GFP_KERNEL, nodeid);
1233         BUG_ON(!ptr);
1234
1235         local_irq_disable();
1236         memcpy(ptr, list, sizeof(struct kmem_list3));
1237         MAKE_ALL_LISTS(cachep, ptr, nodeid);
1238         cachep->nodelists[nodeid] = ptr;
1239         local_irq_enable();
1240 }
1241
1242 /*
1243  * Initialisation.  Called after the page allocator have been initialised and
1244  * before smp_init().
1245  */
1246 void __init kmem_cache_init(void)
1247 {
1248         size_t left_over;
1249         struct cache_sizes *sizes;
1250         struct cache_names *names;
1251         int i;
1252         int order;
1253
1254         for (i = 0; i < NUM_INIT_LISTS; i++) {
1255                 kmem_list3_init(&initkmem_list3[i]);
1256                 if (i < MAX_NUMNODES)
1257                         cache_cache.nodelists[i] = NULL;
1258         }
1259
1260         /*
1261          * Fragmentation resistance on low memory - only use bigger
1262          * page orders on machines with more than 32MB of memory.
1263          */
1264         if (num_physpages > (32 << 20) >> PAGE_SHIFT)
1265                 slab_break_gfp_order = BREAK_GFP_ORDER_HI;
1266
1267         /* Bootstrap is tricky, because several objects are allocated
1268          * from caches that do not exist yet:
1269          * 1) initialize the cache_cache cache: it contains the struct
1270          *    kmem_cache structures of all caches, except cache_cache itself:
1271          *    cache_cache is statically allocated.
1272          *    Initially an __init data area is used for the head array and the
1273          *    kmem_list3 structures, it's replaced with a kmalloc allocated
1274          *    array at the end of the bootstrap.
1275          * 2) Create the first kmalloc cache.
1276          *    The struct kmem_cache for the new cache is allocated normally.
1277          *    An __init data area is used for the head array.
1278          * 3) Create the remaining kmalloc caches, with minimally sized
1279          *    head arrays.
1280          * 4) Replace the __init data head arrays for cache_cache and the first
1281          *    kmalloc cache with kmalloc allocated arrays.
1282          * 5) Replace the __init data for kmem_list3 for cache_cache and
1283          *    the other cache's with kmalloc allocated memory.
1284          * 6) Resize the head arrays of the kmalloc caches to their final sizes.
1285          */
1286
1287         /* 1) create the cache_cache */
1288         INIT_LIST_HEAD(&cache_chain);
1289         list_add(&cache_cache.next, &cache_chain);
1290         cache_cache.colour_off = cache_line_size();
1291         cache_cache.array[smp_processor_id()] = &initarray_cache.cache;
1292         cache_cache.nodelists[numa_node_id()] = &initkmem_list3[CACHE_CACHE];
1293
1294         cache_cache.buffer_size = ALIGN(cache_cache.buffer_size,
1295                                         cache_line_size());
1296
1297         for (order = 0; order < MAX_ORDER; order++) {
1298                 cache_estimate(order, cache_cache.buffer_size,
1299                         cache_line_size(), 0, &left_over, &cache_cache.num);
1300                 if (cache_cache.num)
1301                         break;
1302         }
1303         BUG_ON(!cache_cache.num);
1304         cache_cache.gfporder = order;
1305         cache_cache.colour = left_over / cache_cache.colour_off;
1306         cache_cache.slab_size = ALIGN(cache_cache.num * sizeof(kmem_bufctl_t) +
1307                                       sizeof(struct slab), cache_line_size());
1308
1309         /* 2+3) create the kmalloc caches */
1310         sizes = malloc_sizes;
1311         names = cache_names;
1312
1313         /*
1314          * Initialize the caches that provide memory for the array cache and the
1315          * kmem_list3 structures first.  Without this, further allocations will
1316          * bug.
1317          */
1318
1319         sizes[INDEX_AC].cs_cachep = kmem_cache_create(names[INDEX_AC].name,
1320                                         sizes[INDEX_AC].cs_size,
1321                                         ARCH_KMALLOC_MINALIGN,
1322                                         ARCH_KMALLOC_FLAGS|SLAB_PANIC,
1323                                         NULL, NULL);
1324
1325         if (INDEX_AC != INDEX_L3) {
1326                 sizes[INDEX_L3].cs_cachep =
1327                         kmem_cache_create(names[INDEX_L3].name,
1328                                 sizes[INDEX_L3].cs_size,
1329                                 ARCH_KMALLOC_MINALIGN,
1330                                 ARCH_KMALLOC_FLAGS|SLAB_PANIC,
1331                                 NULL, NULL);
1332         }
1333
1334         while (sizes->cs_size != ULONG_MAX) {
1335                 /*
1336                  * For performance, all the general caches are L1 aligned.
1337                  * This should be particularly beneficial on SMP boxes, as it
1338                  * eliminates "false sharing".
1339                  * Note for systems short on memory removing the alignment will
1340                  * allow tighter packing of the smaller caches.
1341                  */
1342                 if (!sizes->cs_cachep) {
1343                         sizes->cs_cachep = kmem_cache_create(names->name,
1344                                         sizes->cs_size,
1345                                         ARCH_KMALLOC_MINALIGN,
1346                                         ARCH_KMALLOC_FLAGS|SLAB_PANIC,
1347                                         NULL, NULL);
1348                 }
1349
1350                 /* Inc off-slab bufctl limit until the ceiling is hit. */
1351                 if (!(OFF_SLAB(sizes->cs_cachep))) {
1352                         offslab_limit = sizes->cs_size - sizeof(struct slab);
1353                         offslab_limit /= sizeof(kmem_bufctl_t);
1354                 }
1355
1356                 sizes->cs_dmacachep = kmem_cache_create(names->name_dma,
1357                                         sizes->cs_size,
1358                                         ARCH_KMALLOC_MINALIGN,
1359                                         ARCH_KMALLOC_FLAGS|SLAB_CACHE_DMA|
1360                                                 SLAB_PANIC,
1361                                         NULL, NULL);
1362                 sizes++;
1363                 names++;
1364         }
1365         /* 4) Replace the bootstrap head arrays */
1366         {
1367                 void *ptr;
1368
1369                 ptr = kmalloc(sizeof(struct arraycache_init), GFP_KERNEL);
1370
1371                 local_irq_disable();
1372                 BUG_ON(cpu_cache_get(&cache_cache) != &initarray_cache.cache);
1373                 memcpy(ptr, cpu_cache_get(&cache_cache),
1374                        sizeof(struct arraycache_init));
1375                 cache_cache.array[smp_processor_id()] = ptr;
1376                 local_irq_enable();
1377
1378                 ptr = kmalloc(sizeof(struct arraycache_init), GFP_KERNEL);
1379
1380                 local_irq_disable();
1381                 BUG_ON(cpu_cache_get(malloc_sizes[INDEX_AC].cs_cachep)
1382                        != &initarray_generic.cache);
1383                 memcpy(ptr, cpu_cache_get(malloc_sizes[INDEX_AC].cs_cachep),
1384                        sizeof(struct arraycache_init));
1385                 malloc_sizes[INDEX_AC].cs_cachep->array[smp_processor_id()] =
1386                     ptr;
1387                 local_irq_enable();
1388         }
1389         /* 5) Replace the bootstrap kmem_list3's */
1390         {
1391                 int node;
1392                 /* Replace the static kmem_list3 structures for the boot cpu */
1393                 init_list(&cache_cache, &initkmem_list3[CACHE_CACHE],
1394                           numa_node_id());
1395
1396                 for_each_online_node(node) {
1397                         init_list(malloc_sizes[INDEX_AC].cs_cachep,
1398                                   &initkmem_list3[SIZE_AC + node], node);
1399
1400                         if (INDEX_AC != INDEX_L3) {
1401                                 init_list(malloc_sizes[INDEX_L3].cs_cachep,
1402                                           &initkmem_list3[SIZE_L3 + node],
1403                                           node);
1404                         }
1405                 }
1406         }
1407
1408         /* 6) resize the head arrays to their final sizes */
1409         {
1410                 struct kmem_cache *cachep;
1411                 mutex_lock(&cache_chain_mutex);
1412                 list_for_each_entry(cachep, &cache_chain, next)
1413                         enable_cpucache(cachep);
1414                 mutex_unlock(&cache_chain_mutex);
1415         }
1416
1417         /* Done! */
1418         g_cpucache_up = FULL;
1419
1420         /*
1421          * Register a cpu startup notifier callback that initializes
1422          * cpu_cache_get for all new cpus
1423          */
1424         register_cpu_notifier(&cpucache_notifier);
1425
1426         /*
1427          * The reap timers are started later, with a module init call: That part
1428          * of the kernel is not yet operational.
1429          */
1430 }
1431
1432 static int __init cpucache_init(void)
1433 {
1434         int cpu;
1435
1436         /*
1437          * Register the timers that return unneeded pages to the page allocator
1438          */
1439         for_each_online_cpu(cpu)
1440                 start_cpu_timer(cpu);
1441         return 0;
1442 }
1443 __initcall(cpucache_init);
1444
1445 /*
1446  * Interface to system's page allocator. No need to hold the cache-lock.
1447  *
1448  * If we requested dmaable memory, we will get it. Even if we
1449  * did not request dmaable memory, we might get it, but that
1450  * would be relatively rare and ignorable.
1451  */
1452 static void *kmem_getpages(struct kmem_cache *cachep, gfp_t flags, int nodeid)
1453 {
1454         struct page *page;
1455         void *addr;
1456         int i;
1457
1458         flags |= cachep->gfpflags;
1459 #ifndef CONFIG_MMU
1460         /* nommu uses slab's for process anonymous memory allocations, so
1461          * requires __GFP_COMP to properly refcount higher order allocations"
1462          */
1463         page = alloc_pages_node(nodeid, (flags | __GFP_COMP), cachep->gfporder);
1464 #else
1465         page = alloc_pages_node(nodeid, flags, cachep->gfporder);
1466 #endif
1467         if (!page)
1468                 return NULL;
1469         addr = page_address(page);
1470
1471         i = (1 << cachep->gfporder);
1472         if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
1473                 atomic_add(i, &slab_reclaim_pages);
1474         add_page_state(nr_slab, i);
1475         while (i--) {
1476                 __SetPageSlab(page);
1477                 page++;
1478         }
1479         return addr;
1480 }
1481
1482 /*
1483  * Interface to system's page release.
1484  */
1485 static void kmem_freepages(struct kmem_cache *cachep, void *addr)
1486 {
1487         unsigned long i = (1 << cachep->gfporder);
1488         struct page *page = virt_to_page(addr);
1489         const unsigned long nr_freed = i;
1490
1491         while (i--) {
1492                 BUG_ON(!PageSlab(page));
1493                 __ClearPageSlab(page);
1494                 page++;
1495         }
1496         sub_page_state(nr_slab, nr_freed);
1497         if (current->reclaim_state)
1498                 current->reclaim_state->reclaimed_slab += nr_freed;
1499         free_pages((unsigned long)addr, cachep->gfporder);
1500         if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
1501                 atomic_sub(1 << cachep->gfporder, &slab_reclaim_pages);
1502 }
1503
1504 static void kmem_rcu_free(struct rcu_head *head)
1505 {
1506         struct slab_rcu *slab_rcu = (struct slab_rcu *)head;
1507         struct kmem_cache *cachep = slab_rcu->cachep;
1508
1509         kmem_freepages(cachep, slab_rcu->addr);
1510         if (OFF_SLAB(cachep))
1511                 kmem_cache_free(cachep->slabp_cache, slab_rcu);
1512 }
1513
1514 #if DEBUG
1515
1516 #ifdef CONFIG_DEBUG_PAGEALLOC
1517 static void store_stackinfo(struct kmem_cache *cachep, unsigned long *addr,
1518                             unsigned long caller)
1519 {
1520         int size = obj_size(cachep);
1521
1522         addr = (unsigned long *)&((char *)addr)[obj_offset(cachep)];
1523
1524         if (size < 5 * sizeof(unsigned long))
1525                 return;
1526
1527         *addr++ = 0x12345678;
1528         *addr++ = caller;
1529         *addr++ = smp_processor_id();
1530         size -= 3 * sizeof(unsigned long);
1531         {
1532                 unsigned long *sptr = &caller;
1533                 unsigned long svalue;
1534
1535                 while (!kstack_end(sptr)) {
1536                         svalue = *sptr++;
1537                         if (kernel_text_address(svalue)) {
1538                                 *addr++ = svalue;
1539                                 size -= sizeof(unsigned long);
1540                                 if (size <= sizeof(unsigned long))
1541                                         break;
1542                         }
1543                 }
1544
1545         }
1546         *addr++ = 0x87654321;
1547 }
1548 #endif
1549
1550 static void poison_obj(struct kmem_cache *cachep, void *addr, unsigned char val)
1551 {
1552         int size = obj_size(cachep);
1553         addr = &((char *)addr)[obj_offset(cachep)];
1554
1555         memset(addr, val, size);
1556         *(unsigned char *)(addr + size - 1) = POISON_END;
1557 }
1558
1559 static void dump_line(char *data, int offset, int limit)
1560 {
1561         int i;
1562         printk(KERN_ERR "%03x:", offset);
1563         for (i = 0; i < limit; i++)
1564                 printk(" %02x", (unsigned char)data[offset + i]);
1565         printk("\n");
1566 }
1567 #endif
1568
1569 #if DEBUG
1570
1571 static void print_objinfo(struct kmem_cache *cachep, void *objp, int lines)
1572 {
1573         int i, size;
1574         char *realobj;
1575
1576         if (cachep->flags & SLAB_RED_ZONE) {
1577                 printk(KERN_ERR "Redzone: 0x%lx/0x%lx.\n",
1578                         *dbg_redzone1(cachep, objp),
1579                         *dbg_redzone2(cachep, objp));
1580         }
1581
1582         if (cachep->flags & SLAB_STORE_USER) {
1583                 printk(KERN_ERR "Last user: [<%p>]",
1584                         *dbg_userword(cachep, objp));
1585                 print_symbol("(%s)",
1586                                 (unsigned long)*dbg_userword(cachep, objp));
1587                 printk("\n");
1588         }
1589         realobj = (char *)objp + obj_offset(cachep);
1590         size = obj_size(cachep);
1591         for (i = 0; i < size && lines; i += 16, lines--) {
1592                 int limit;
1593                 limit = 16;
1594                 if (i + limit > size)
1595                         limit = size - i;
1596                 dump_line(realobj, i, limit);
1597         }
1598 }
1599
1600 static void check_poison_obj(struct kmem_cache *cachep, void *objp)
1601 {
1602         char *realobj;
1603         int size, i;
1604         int lines = 0;
1605
1606         realobj = (char *)objp + obj_offset(cachep);
1607         size = obj_size(cachep);
1608
1609         for (i = 0; i < size; i++) {
1610                 char exp = POISON_FREE;
1611                 if (i == size - 1)
1612                         exp = POISON_END;
1613                 if (realobj[i] != exp) {
1614                         int limit;
1615                         /* Mismatch ! */
1616                         /* Print header */
1617                         if (lines == 0) {
1618                                 printk(KERN_ERR
1619                                         "Slab corruption: start=%p, len=%d\n",
1620                                         realobj, size);
1621                                 print_objinfo(cachep, objp, 0);
1622                         }
1623                         /* Hexdump the affected line */
1624                         i = (i / 16) * 16;
1625                         limit = 16;
1626                         if (i + limit > size)
1627                                 limit = size - i;
1628                         dump_line(realobj, i, limit);
1629                         i += 16;
1630                         lines++;
1631                         /* Limit to 5 lines */
1632                         if (lines > 5)
1633                                 break;
1634                 }
1635         }
1636         if (lines != 0) {
1637                 /* Print some data about the neighboring objects, if they
1638                  * exist:
1639                  */
1640                 struct slab *slabp = virt_to_slab(objp);
1641                 unsigned int objnr;
1642
1643                 objnr = obj_to_index(cachep, slabp, objp);
1644                 if (objnr) {
1645                         objp = index_to_obj(cachep, slabp, objnr - 1);
1646                         realobj = (char *)objp + obj_offset(cachep);
1647                         printk(KERN_ERR "Prev obj: start=%p, len=%d\n",
1648                                realobj, size);
1649                         print_objinfo(cachep, objp, 2);
1650                 }
1651                 if (objnr + 1 < cachep->num) {
1652                         objp = index_to_obj(cachep, slabp, objnr + 1);
1653                         realobj = (char *)objp + obj_offset(cachep);
1654                         printk(KERN_ERR "Next obj: start=%p, len=%d\n",
1655                                realobj, size);
1656                         print_objinfo(cachep, objp, 2);
1657                 }
1658         }
1659 }
1660 #endif
1661
1662 #if DEBUG
1663 /**
1664  * slab_destroy_objs - destroy a slab and its objects
1665  * @cachep: cache pointer being destroyed
1666  * @slabp: slab pointer being destroyed
1667  *
1668  * Call the registered destructor for each object in a slab that is being
1669  * destroyed.
1670  */
1671 static void slab_destroy_objs(struct kmem_cache *cachep, struct slab *slabp)
1672 {
1673         int i;
1674         for (i = 0; i < cachep->num; i++) {
1675                 void *objp = index_to_obj(cachep, slabp, i);
1676
1677                 if (cachep->flags & SLAB_POISON) {
1678 #ifdef CONFIG_DEBUG_PAGEALLOC
1679                         if (cachep->buffer_size % PAGE_SIZE == 0 &&
1680                                         OFF_SLAB(cachep))
1681                                 kernel_map_pages(virt_to_page(objp),
1682                                         cachep->buffer_size / PAGE_SIZE, 1);
1683                         else
1684                                 check_poison_obj(cachep, objp);
1685 #else
1686                         check_poison_obj(cachep, objp);
1687 #endif
1688                 }
1689                 if (cachep->flags & SLAB_RED_ZONE) {
1690                         if (*dbg_redzone1(cachep, objp) != RED_INACTIVE)
1691                                 slab_error(cachep, "start of a freed object "
1692                                            "was overwritten");
1693                         if (*dbg_redzone2(cachep, objp) != RED_INACTIVE)
1694                                 slab_error(cachep, "end of a freed object "
1695                                            "was overwritten");
1696                 }
1697                 if (cachep->dtor && !(cachep->flags & SLAB_POISON))
1698                         (cachep->dtor) (objp + obj_offset(cachep), cachep, 0);
1699         }
1700 }
1701 #else
1702 static void slab_destroy_objs(struct kmem_cache *cachep, struct slab *slabp)
1703 {
1704         if (cachep->dtor) {
1705                 int i;
1706                 for (i = 0; i < cachep->num; i++) {
1707                         void *objp = index_to_obj(cachep, slabp, i);
1708                         (cachep->dtor) (objp, cachep, 0);
1709                 }
1710         }
1711 }
1712 #endif
1713
1714 /**
1715  * slab_destroy - destroy and release all objects in a slab
1716  * @cachep: cache pointer being destroyed
1717  * @slabp: slab pointer being destroyed
1718  *
1719  * Destroy all the objs in a slab, and release the mem back to the system.
1720  * Before calling the slab must have been unlinked from the cache.  The
1721  * cache-lock is not held/needed.
1722  */
1723 static void slab_destroy(struct kmem_cache *cachep, struct slab *slabp)
1724 {
1725         void *addr = slabp->s_mem - slabp->colouroff;
1726
1727         slab_destroy_objs(cachep, slabp);
1728         if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU)) {
1729                 struct slab_rcu *slab_rcu;
1730
1731                 slab_rcu = (struct slab_rcu *)slabp;
1732                 slab_rcu->cachep = cachep;
1733                 slab_rcu->addr = addr;
1734                 call_rcu(&slab_rcu->head, kmem_rcu_free);
1735         } else {
1736                 kmem_freepages(cachep, addr);
1737                 if (OFF_SLAB(cachep))
1738                         kmem_cache_free(cachep->slabp_cache, slabp);
1739         }
1740 }
1741
1742 /*
1743  * For setting up all the kmem_list3s for cache whose buffer_size is same as
1744  * size of kmem_list3.
1745  */
1746 static void set_up_list3s(struct kmem_cache *cachep, int index)
1747 {
1748         int node;
1749
1750         for_each_online_node(node) {
1751                 cachep->nodelists[node] = &initkmem_list3[index + node];
1752                 cachep->nodelists[node]->next_reap = jiffies +
1753                     REAPTIMEOUT_LIST3 +
1754                     ((unsigned long)cachep) % REAPTIMEOUT_LIST3;
1755         }
1756 }
1757
1758 /**
1759  * calculate_slab_order - calculate size (page order) of slabs
1760  * @cachep: pointer to the cache that is being created
1761  * @size: size of objects to be created in this cache.
1762  * @align: required alignment for the objects.
1763  * @flags: slab allocation flags
1764  *
1765  * Also calculates the number of objects per slab.
1766  *
1767  * This could be made much more intelligent.  For now, try to avoid using
1768  * high order pages for slabs.  When the gfp() functions are more friendly
1769  * towards high-order requests, this should be changed.
1770  */
1771 static size_t calculate_slab_order(struct kmem_cache *cachep,
1772                         size_t size, size_t align, unsigned long flags)
1773 {
1774         size_t left_over = 0;
1775         int gfporder;
1776
1777         for (gfporder = 0; gfporder <= MAX_GFP_ORDER; gfporder++) {
1778                 unsigned int num;
1779                 size_t remainder;
1780
1781                 cache_estimate(gfporder, size, align, flags, &remainder, &num);
1782                 if (!num)
1783                         continue;
1784
1785                 /* More than offslab_limit objects will cause problems */
1786                 if ((flags & CFLGS_OFF_SLAB) && num > offslab_limit)
1787                         break;
1788
1789                 /* Found something acceptable - save it away */
1790                 cachep->num = num;
1791                 cachep->gfporder = gfporder;
1792                 left_over = remainder;
1793
1794                 /*
1795                  * A VFS-reclaimable slab tends to have most allocations
1796                  * as GFP_NOFS and we really don't want to have to be allocating
1797                  * higher-order pages when we are unable to shrink dcache.
1798                  */
1799                 if (flags & SLAB_RECLAIM_ACCOUNT)
1800                         break;
1801
1802                 /*
1803                  * Large number of objects is good, but very large slabs are
1804                  * currently bad for the gfp()s.
1805                  */
1806                 if (gfporder >= slab_break_gfp_order)
1807                         break;
1808
1809                 /*
1810                  * Acceptable internal fragmentation?
1811                  */
1812                 if (left_over * 8 <= (PAGE_SIZE << gfporder))
1813                         break;
1814         }
1815         return left_over;
1816 }
1817
1818 static void setup_cpu_cache(struct kmem_cache *cachep)
1819 {
1820         if (g_cpucache_up == FULL) {
1821                 enable_cpucache(cachep);
1822                 return;
1823         }
1824         if (g_cpucache_up == NONE) {
1825                 /*
1826                  * Note: the first kmem_cache_create must create the cache
1827                  * that's used by kmalloc(24), otherwise the creation of
1828                  * further caches will BUG().
1829                  */
1830                 cachep->array[smp_processor_id()] = &initarray_generic.cache;
1831
1832                 /*
1833                  * If the cache that's used by kmalloc(sizeof(kmem_list3)) is
1834                  * the first cache, then we need to set up all its list3s,
1835                  * otherwise the creation of further caches will BUG().
1836                  */
1837                 set_up_list3s(cachep, SIZE_AC);
1838                 if (INDEX_AC == INDEX_L3)
1839                         g_cpucache_up = PARTIAL_L3;
1840                 else
1841                         g_cpucache_up = PARTIAL_AC;
1842         } else {
1843                 cachep->array[smp_processor_id()] =
1844                         kmalloc(sizeof(struct arraycache_init), GFP_KERNEL);
1845
1846                 if (g_cpucache_up == PARTIAL_AC) {
1847                         set_up_list3s(cachep, SIZE_L3);
1848                         g_cpucache_up = PARTIAL_L3;
1849                 } else {
1850                         int node;
1851                         for_each_online_node(node) {
1852                                 cachep->nodelists[node] =
1853                                     kmalloc_node(sizeof(struct kmem_list3),
1854                                                 GFP_KERNEL, node);
1855                                 BUG_ON(!cachep->nodelists[node]);
1856                                 kmem_list3_init(cachep->nodelists[node]);
1857                         }
1858                 }
1859         }
1860         cachep->nodelists[numa_node_id()]->next_reap =
1861                         jiffies + REAPTIMEOUT_LIST3 +
1862                         ((unsigned long)cachep) % REAPTIMEOUT_LIST3;
1863
1864         cpu_cache_get(cachep)->avail = 0;
1865         cpu_cache_get(cachep)->limit = BOOT_CPUCACHE_ENTRIES;
1866         cpu_cache_get(cachep)->batchcount = 1;
1867         cpu_cache_get(cachep)->touched = 0;
1868         cachep->batchcount = 1;
1869         cachep->limit = BOOT_CPUCACHE_ENTRIES;
1870 }
1871
1872 /**
1873  * kmem_cache_create - Create a cache.
1874  * @name: A string which is used in /proc/slabinfo to identify this cache.
1875  * @size: The size of objects to be created in this cache.
1876  * @align: The required alignment for the objects.
1877  * @flags: SLAB flags
1878  * @ctor: A constructor for the objects.
1879  * @dtor: A destructor for the objects.
1880  *
1881  * Returns a ptr to the cache on success, NULL on failure.
1882  * Cannot be called within a int, but can be interrupted.
1883  * The @ctor is run when new pages are allocated by the cache
1884  * and the @dtor is run before the pages are handed back.
1885  *
1886  * @name must be valid until the cache is destroyed. This implies that
1887  * the module calling this has to destroy the cache before getting unloaded.
1888  *
1889  * The flags are
1890  *
1891  * %SLAB_POISON - Poison the slab with a known test pattern (a5a5a5a5)
1892  * to catch references to uninitialised memory.
1893  *
1894  * %SLAB_RED_ZONE - Insert `Red' zones around the allocated memory to check
1895  * for buffer overruns.
1896  *
1897  * %SLAB_HWCACHE_ALIGN - Align the objects in this cache to a hardware
1898  * cacheline.  This can be beneficial if you're counting cycles as closely
1899  * as davem.
1900  */
1901 struct kmem_cache *
1902 kmem_cache_create (const char *name, size_t size, size_t align,
1903         unsigned long flags,
1904         void (*ctor)(void*, struct kmem_cache *, unsigned long),
1905         void (*dtor)(void*, struct kmem_cache *, unsigned long))
1906 {
1907         size_t left_over, slab_size, ralign;
1908         struct kmem_cache *cachep = NULL;
1909         struct list_head *p;
1910
1911         /*
1912          * Sanity checks... these are all serious usage bugs.
1913          */
1914         if (!name || in_interrupt() || (size < BYTES_PER_WORD) ||
1915             (size > (1 << MAX_OBJ_ORDER) * PAGE_SIZE) || (dtor && !ctor)) {
1916                 printk(KERN_ERR "%s: Early error in slab %s\n", __FUNCTION__,
1917                                 name);
1918                 BUG();
1919         }
1920
1921         /*
1922          * Prevent CPUs from coming and going.
1923          * lock_cpu_hotplug() nests outside cache_chain_mutex
1924          */
1925         lock_cpu_hotplug();
1926
1927         mutex_lock(&cache_chain_mutex);
1928
1929         list_for_each(p, &cache_chain) {
1930                 struct kmem_cache *pc = list_entry(p, struct kmem_cache, next);
1931                 mm_segment_t old_fs = get_fs();
1932                 char tmp;
1933                 int res;
1934
1935                 /*
1936                  * This happens when the module gets unloaded and doesn't
1937                  * destroy its slab cache and no-one else reuses the vmalloc
1938                  * area of the module.  Print a warning.
1939                  */
1940                 set_fs(KERNEL_DS);
1941                 res = __get_user(tmp, pc->name);
1942                 set_fs(old_fs);
1943                 if (res) {
1944                         printk("SLAB: cache with size %d has lost its name\n",
1945                                pc->buffer_size);
1946                         continue;
1947                 }
1948
1949                 if (!strcmp(pc->name, name)) {
1950                         printk("kmem_cache_create: duplicate cache %s\n", name);
1951                         dump_stack();
1952                         goto oops;
1953                 }
1954         }
1955
1956 #if DEBUG
1957         WARN_ON(strchr(name, ' '));     /* It confuses parsers */
1958         if ((flags & SLAB_DEBUG_INITIAL) && !ctor) {
1959                 /* No constructor, but inital state check requested */
1960                 printk(KERN_ERR "%s: No con, but init state check "
1961                        "requested - %s\n", __FUNCTION__, name);
1962                 flags &= ~SLAB_DEBUG_INITIAL;
1963         }
1964 #if FORCED_DEBUG
1965         /*
1966          * Enable redzoning and last user accounting, except for caches with
1967          * large objects, if the increased size would increase the object size
1968          * above the next power of two: caches with object sizes just above a
1969          * power of two have a significant amount of internal fragmentation.
1970          */
1971         if (size < 4096 || fls(size - 1) == fls(size-1 + 3 * BYTES_PER_WORD))
1972                 flags |= SLAB_RED_ZONE | SLAB_STORE_USER;
1973         if (!(flags & SLAB_DESTROY_BY_RCU))
1974                 flags |= SLAB_POISON;
1975 #endif
1976         if (flags & SLAB_DESTROY_BY_RCU)
1977                 BUG_ON(flags & SLAB_POISON);
1978 #endif
1979         if (flags & SLAB_DESTROY_BY_RCU)
1980                 BUG_ON(dtor);
1981
1982         /*
1983          * Always checks flags, a caller might be expecting debug support which
1984          * isn't available.
1985          */
1986         BUG_ON(flags & ~CREATE_MASK);
1987
1988         /*
1989          * Check that size is in terms of words.  This is needed to avoid
1990          * unaligned accesses for some archs when redzoning is used, and makes
1991          * sure any on-slab bufctl's are also correctly aligned.
1992          */
1993         if (size & (BYTES_PER_WORD - 1)) {
1994                 size += (BYTES_PER_WORD - 1);
1995                 size &= ~(BYTES_PER_WORD - 1);
1996         }
1997
1998         /* calculate the final buffer alignment: */
1999
2000         /* 1) arch recommendation: can be overridden for debug */
2001         if (flags & SLAB_HWCACHE_ALIGN) {
2002                 /*
2003                  * Default alignment: as specified by the arch code.  Except if
2004                  * an object is really small, then squeeze multiple objects into
2005                  * one cacheline.
2006                  */
2007                 ralign = cache_line_size();
2008                 while (size <= ralign / 2)
2009                         ralign /= 2;
2010         } else {
2011                 ralign = BYTES_PER_WORD;
2012         }
2013         /* 2) arch mandated alignment: disables debug if necessary */
2014         if (ralign < ARCH_SLAB_MINALIGN) {
2015                 ralign = ARCH_SLAB_MINALIGN;
2016                 if (ralign > BYTES_PER_WORD)
2017                         flags &= ~(SLAB_RED_ZONE | SLAB_STORE_USER);
2018         }
2019         /* 3) caller mandated alignment: disables debug if necessary */
2020         if (ralign < align) {
2021                 ralign = align;
2022                 if (ralign > BYTES_PER_WORD)
2023                         flags &= ~(SLAB_RED_ZONE | SLAB_STORE_USER);
2024         }
2025         /*
2026          * 4) Store it. Note that the debug code below can reduce
2027          *    the alignment to BYTES_PER_WORD.
2028          */
2029         align = ralign;
2030
2031         /* Get cache's description obj. */
2032         cachep = kmem_cache_zalloc(&cache_cache, SLAB_KERNEL);
2033         if (!cachep)
2034                 goto oops;
2035
2036 #if DEBUG
2037         cachep->obj_size = size;
2038
2039         if (flags & SLAB_RED_ZONE) {
2040                 /* redzoning only works with word aligned caches */
2041                 align = BYTES_PER_WORD;
2042
2043                 /* add space for red zone words */
2044                 cachep->obj_offset += BYTES_PER_WORD;
2045                 size += 2 * BYTES_PER_WORD;
2046         }
2047         if (flags & SLAB_STORE_USER) {
2048                 /* user store requires word alignment and
2049                  * one word storage behind the end of the real
2050                  * object.
2051                  */
2052                 align = BYTES_PER_WORD;
2053                 size += BYTES_PER_WORD;
2054         }
2055 #if FORCED_DEBUG && defined(CONFIG_DEBUG_PAGEALLOC)
2056         if (size >= malloc_sizes[INDEX_L3 + 1].cs_size
2057             && cachep->obj_size > cache_line_size() && size < PAGE_SIZE) {
2058                 cachep->obj_offset += PAGE_SIZE - size;
2059                 size = PAGE_SIZE;
2060         }
2061 #endif
2062 #endif
2063
2064         /* Determine if the slab management is 'on' or 'off' slab. */
2065         if (size >= (PAGE_SIZE >> 3))
2066                 /*
2067                  * Size is large, assume best to place the slab management obj
2068                  * off-slab (should allow better packing of objs).
2069                  */
2070                 flags |= CFLGS_OFF_SLAB;
2071
2072         size = ALIGN(size, align);
2073
2074         left_over = calculate_slab_order(cachep, size, align, flags);
2075
2076         if (!cachep->num) {
2077                 printk("kmem_cache_create: couldn't create cache %s.\n", name);
2078                 kmem_cache_free(&cache_cache, cachep);
2079                 cachep = NULL;
2080                 goto oops;
2081         }
2082         slab_size = ALIGN(cachep->num * sizeof(kmem_bufctl_t)
2083                           + sizeof(struct slab), align);
2084
2085         /*
2086          * If the slab has been placed off-slab, and we have enough space then
2087          * move it on-slab. This is at the expense of any extra colouring.
2088          */
2089         if (flags & CFLGS_OFF_SLAB && left_over >= slab_size) {
2090                 flags &= ~CFLGS_OFF_SLAB;
2091                 left_over -= slab_size;
2092         }
2093
2094         if (flags & CFLGS_OFF_SLAB) {
2095                 /* really off slab. No need for manual alignment */
2096                 slab_size =
2097                     cachep->num * sizeof(kmem_bufctl_t) + sizeof(struct slab);
2098         }
2099
2100         cachep->colour_off = cache_line_size();
2101         /* Offset must be a multiple of the alignment. */
2102         if (cachep->colour_off < align)
2103                 cachep->colour_off = align;
2104         cachep->colour = left_over / cachep->colour_off;
2105         cachep->slab_size = slab_size;
2106         cachep->flags = flags;
2107         cachep->gfpflags = 0;
2108         if (flags & SLAB_CACHE_DMA)
2109                 cachep->gfpflags |= GFP_DMA;
2110         cachep->buffer_size = size;
2111
2112         if (flags & CFLGS_OFF_SLAB)
2113                 cachep->slabp_cache = kmem_find_general_cachep(slab_size, 0u);
2114         cachep->ctor = ctor;
2115         cachep->dtor = dtor;
2116         cachep->name = name;
2117
2118
2119         setup_cpu_cache(cachep);
2120
2121         /* cache setup completed, link it into the list */
2122         list_add(&cachep->next, &cache_chain);
2123 oops:
2124         if (!cachep && (flags & SLAB_PANIC))
2125                 panic("kmem_cache_create(): failed to create slab `%s'\n",
2126                       name);
2127         mutex_unlock(&cache_chain_mutex);
2128         unlock_cpu_hotplug();
2129         return cachep;
2130 }
2131 EXPORT_SYMBOL(kmem_cache_create);
2132
2133 #if DEBUG
2134 static void check_irq_off(void)
2135 {
2136         BUG_ON(!irqs_disabled());
2137 }
2138
2139 static void check_irq_on(void)
2140 {
2141         BUG_ON(irqs_disabled());
2142 }
2143
2144 static void check_spinlock_acquired(struct kmem_cache *cachep)
2145 {
2146 #ifdef CONFIG_SMP
2147         check_irq_off();
2148         assert_spin_locked(&cachep->nodelists[numa_node_id()]->list_lock);
2149 #endif
2150 }
2151
2152 static void check_spinlock_acquired_node(struct kmem_cache *cachep, int node)
2153 {
2154 #ifdef CONFIG_SMP
2155         check_irq_off();
2156         assert_spin_locked(&cachep->nodelists[node]->list_lock);
2157 #endif
2158 }
2159
2160 #else
2161 #define check_irq_off() do { } while(0)
2162 #define check_irq_on()  do { } while(0)
2163 #define check_spinlock_acquired(x) do { } while(0)
2164 #define check_spinlock_acquired_node(x, y) do { } while(0)
2165 #endif
2166
2167 static void drain_array(struct kmem_cache *cachep, struct kmem_list3 *l3,
2168                         struct array_cache *ac,
2169                         int force, int node);
2170
2171 static void do_drain(void *arg)
2172 {
2173         struct kmem_cache *cachep = arg;
2174         struct array_cache *ac;
2175         int node = numa_node_id();
2176
2177         check_irq_off();
2178         ac = cpu_cache_get(cachep);
2179         spin_lock(&cachep->nodelists[node]->list_lock);
2180         free_block(cachep, ac->entry, ac->avail, node);
2181         spin_unlock(&cachep->nodelists[node]->list_lock);
2182         ac->avail = 0;
2183 }
2184
2185 static void drain_cpu_caches(struct kmem_cache *cachep)
2186 {
2187         struct kmem_list3 *l3;
2188         int node;
2189
2190         on_each_cpu(do_drain, cachep, 1, 1);
2191         check_irq_on();
2192         for_each_online_node(node) {
2193                 l3 = cachep->nodelists[node];
2194                 if (l3) {
2195                         drain_array(cachep, l3, l3->shared, 1, node);
2196                         if (l3->alien)
2197                                 drain_alien_cache(cachep, l3->alien);
2198                 }
2199         }
2200 }
2201
2202 static int __node_shrink(struct kmem_cache *cachep, int node)
2203 {
2204         struct slab *slabp;
2205         struct kmem_list3 *l3 = cachep->nodelists[node];
2206         int ret;
2207
2208         for (;;) {
2209                 struct list_head *p;
2210
2211                 p = l3->slabs_free.prev;
2212                 if (p == &l3->slabs_free)
2213                         break;
2214
2215                 slabp = list_entry(l3->slabs_free.prev, struct slab, list);
2216 #if DEBUG
2217                 BUG_ON(slabp->inuse);
2218 #endif
2219                 list_del(&slabp->list);
2220
2221                 l3->free_objects -= cachep->num;
2222                 spin_unlock_irq(&l3->list_lock);
2223                 slab_destroy(cachep, slabp);
2224                 spin_lock_irq(&l3->list_lock);
2225         }
2226         ret = !list_empty(&l3->slabs_full) || !list_empty(&l3->slabs_partial);
2227         return ret;
2228 }
2229
2230 static int __cache_shrink(struct kmem_cache *cachep)
2231 {
2232         int ret = 0, i = 0;
2233         struct kmem_list3 *l3;
2234
2235         drain_cpu_caches(cachep);
2236
2237         check_irq_on();
2238         for_each_online_node(i) {
2239                 l3 = cachep->nodelists[i];
2240                 if (l3) {
2241                         spin_lock_irq(&l3->list_lock);
2242                         ret += __node_shrink(cachep, i);
2243                         spin_unlock_irq(&l3->list_lock);
2244                 }
2245         }
2246         return (ret ? 1 : 0);
2247 }
2248
2249 /**
2250  * kmem_cache_shrink - Shrink a cache.
2251  * @cachep: The cache to shrink.
2252  *
2253  * Releases as many slabs as possible for a cache.
2254  * To help debugging, a zero exit status indicates all slabs were released.
2255  */
2256 int kmem_cache_shrink(struct kmem_cache *cachep)
2257 {
2258         BUG_ON(!cachep || in_interrupt());
2259
2260         return __cache_shrink(cachep);
2261 }
2262 EXPORT_SYMBOL(kmem_cache_shrink);
2263
2264 /**
2265  * kmem_cache_destroy - delete a cache
2266  * @cachep: the cache to destroy
2267  *
2268  * Remove a struct kmem_cache object from the slab cache.
2269  * Returns 0 on success.
2270  *
2271  * It is expected this function will be called by a module when it is
2272  * unloaded.  This will remove the cache completely, and avoid a duplicate
2273  * cache being allocated each time a module is loaded and unloaded, if the
2274  * module doesn't have persistent in-kernel storage across loads and unloads.
2275  *
2276  * The cache must be empty before calling this function.
2277  *
2278  * The caller must guarantee that noone will allocate memory from the cache
2279  * during the kmem_cache_destroy().
2280  */
2281 int kmem_cache_destroy(struct kmem_cache *cachep)
2282 {
2283         int i;
2284         struct kmem_list3 *l3;
2285
2286         BUG_ON(!cachep || in_interrupt());
2287
2288         /* Don't let CPUs to come and go */
2289         lock_cpu_hotplug();
2290
2291         /* Find the cache in the chain of caches. */
2292         mutex_lock(&cache_chain_mutex);
2293         /*
2294          * the chain is never empty, cache_cache is never destroyed
2295          */
2296         list_del(&cachep->next);
2297         mutex_unlock(&cache_chain_mutex);
2298
2299         if (__cache_shrink(cachep)) {
2300                 slab_error(cachep, "Can't free all objects");
2301                 mutex_lock(&cache_chain_mutex);
2302                 list_add(&cachep->next, &cache_chain);
2303                 mutex_unlock(&cache_chain_mutex);
2304                 unlock_cpu_hotplug();
2305                 return 1;
2306         }
2307
2308         if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU))
2309                 synchronize_rcu();
2310
2311         for_each_online_cpu(i)
2312             kfree(cachep->array[i]);
2313
2314         /* NUMA: free the list3 structures */
2315         for_each_online_node(i) {
2316                 l3 = cachep->nodelists[i];
2317                 if (l3) {
2318                         kfree(l3->shared);
2319                         free_alien_cache(l3->alien);
2320                         kfree(l3);
2321                 }
2322         }
2323         kmem_cache_free(&cache_cache, cachep);
2324         unlock_cpu_hotplug();
2325         return 0;
2326 }
2327 EXPORT_SYMBOL(kmem_cache_destroy);
2328
2329 /* Get the memory for a slab management obj. */
2330 static struct slab *alloc_slabmgmt(struct kmem_cache *cachep, void *objp,
2331                                    int colour_off, gfp_t local_flags,
2332                                    int nodeid)
2333 {
2334         struct slab *slabp;
2335
2336         if (OFF_SLAB(cachep)) {
2337                 /* Slab management obj is off-slab. */
2338                 slabp = kmem_cache_alloc_node(cachep->slabp_cache,
2339                                               local_flags, nodeid);
2340                 if (!slabp)
2341                         return NULL;
2342         } else {
2343                 slabp = objp + colour_off;
2344                 colour_off += cachep->slab_size;
2345         }
2346         slabp->inuse = 0;
2347         slabp->colouroff = colour_off;
2348         slabp->s_mem = objp + colour_off;
2349         slabp->nodeid = nodeid;
2350         return slabp;
2351 }
2352
2353 static inline kmem_bufctl_t *slab_bufctl(struct slab *slabp)
2354 {
2355         return (kmem_bufctl_t *) (slabp + 1);
2356 }
2357
2358 static void cache_init_objs(struct kmem_cache *cachep,
2359                             struct slab *slabp, unsigned long ctor_flags)
2360 {
2361         int i;
2362
2363         for (i = 0; i < cachep->num; i++) {
2364                 void *objp = index_to_obj(cachep, slabp, i);
2365 #if DEBUG
2366                 /* need to poison the objs? */
2367                 if (cachep->flags & SLAB_POISON)
2368                         poison_obj(cachep, objp, POISON_FREE);
2369                 if (cachep->flags & SLAB_STORE_USER)
2370                         *dbg_userword(cachep, objp) = NULL;
2371
2372                 if (cachep->flags & SLAB_RED_ZONE) {
2373                         *dbg_redzone1(cachep, objp) = RED_INACTIVE;
2374                         *dbg_redzone2(cachep, objp) = RED_INACTIVE;
2375                 }
2376                 /*
2377                  * Constructors are not allowed to allocate memory from the same
2378                  * cache which they are a constructor for.  Otherwise, deadlock.
2379                  * They must also be threaded.
2380                  */
2381                 if (cachep->ctor && !(cachep->flags & SLAB_POISON))
2382                         cachep->ctor(objp + obj_offset(cachep), cachep,
2383                                      ctor_flags);
2384
2385                 if (cachep->flags & SLAB_RED_ZONE) {
2386                         if (*dbg_redzone2(cachep, objp) != RED_INACTIVE)
2387                                 slab_error(cachep, "constructor overwrote the"
2388                                            " end of an object");
2389                         if (*dbg_redzone1(cachep, objp) != RED_INACTIVE)
2390                                 slab_error(cachep, "constructor overwrote the"
2391                                            " start of an object");
2392                 }
2393                 if ((cachep->buffer_size % PAGE_SIZE) == 0 &&
2394                             OFF_SLAB(cachep) && cachep->flags & SLAB_POISON)
2395                         kernel_map_pages(virt_to_page(objp),
2396                                          cachep->buffer_size / PAGE_SIZE, 0);
2397 #else
2398                 if (cachep->ctor)
2399                         cachep->ctor(objp, cachep, ctor_flags);
2400 #endif
2401                 slab_bufctl(slabp)[i] = i + 1;
2402         }
2403         slab_bufctl(slabp)[i - 1] = BUFCTL_END;
2404         slabp->free = 0;
2405 }
2406
2407 static void kmem_flagcheck(struct kmem_cache *cachep, gfp_t flags)
2408 {
2409         if (flags & SLAB_DMA)
2410                 BUG_ON(!(cachep->gfpflags & GFP_DMA));
2411         else
2412                 BUG_ON(cachep->gfpflags & GFP_DMA);
2413 }
2414
2415 static void *slab_get_obj(struct kmem_cache *cachep, struct slab *slabp,
2416                                 int nodeid)
2417 {
2418         void *objp = index_to_obj(cachep, slabp, slabp->free);
2419         kmem_bufctl_t next;
2420
2421         slabp->inuse++;
2422         next = slab_bufctl(slabp)[slabp->free];
2423 #if DEBUG
2424         slab_bufctl(slabp)[slabp->free] = BUFCTL_FREE;
2425         WARN_ON(slabp->nodeid != nodeid);
2426 #endif
2427         slabp->free = next;
2428
2429         return objp;
2430 }
2431
2432 static void slab_put_obj(struct kmem_cache *cachep, struct slab *slabp,
2433                                 void *objp, int nodeid)
2434 {
2435         unsigned int objnr = obj_to_index(cachep, slabp, objp);
2436
2437 #if DEBUG
2438         /* Verify that the slab belongs to the intended node */
2439         WARN_ON(slabp->nodeid != nodeid);
2440
2441         if (slab_bufctl(slabp)[objnr] + 1 <= SLAB_LIMIT + 1) {
2442                 printk(KERN_ERR "slab: double free detected in cache "
2443                                 "'%s', objp %p\n", cachep->name, objp);
2444                 BUG();
2445         }
2446 #endif
2447         slab_bufctl(slabp)[objnr] = slabp->free;
2448         slabp->free = objnr;
2449         slabp->inuse--;
2450 }
2451
2452 static void set_slab_attr(struct kmem_cache *cachep, struct slab *slabp,
2453                         void *objp)
2454 {
2455         int i;
2456         struct page *page;
2457
2458         /* Nasty!!!!!! I hope this is OK. */
2459         page = virt_to_page(objp);
2460
2461         i = 1;
2462         if (likely(!PageCompound(page)))
2463                 i <<= cachep->gfporder;
2464         do {
2465                 page_set_cache(page, cachep);
2466                 page_set_slab(page, slabp);
2467                 page++;
2468         } while (--i);
2469 }
2470
2471 /*
2472  * Grow (by 1) the number of slabs within a cache.  This is called by
2473  * kmem_cache_alloc() when there are no active objs left in a cache.
2474  */
2475 static int cache_grow(struct kmem_cache *cachep, gfp_t flags, int nodeid)
2476 {
2477         struct slab *slabp;
2478         void *objp;
2479         size_t offset;
2480         gfp_t local_flags;
2481         unsigned long ctor_flags;
2482         struct kmem_list3 *l3;
2483
2484         /*
2485          * Be lazy and only check for valid flags here,  keeping it out of the
2486          * critical path in kmem_cache_alloc().
2487          */
2488         BUG_ON(flags & ~(SLAB_DMA | SLAB_LEVEL_MASK | SLAB_NO_GROW));
2489         if (flags & SLAB_NO_GROW)
2490                 return 0;
2491
2492         ctor_flags = SLAB_CTOR_CONSTRUCTOR;
2493         local_flags = (flags & SLAB_LEVEL_MASK);
2494         if (!(local_flags & __GFP_WAIT))
2495                 /*
2496                  * Not allowed to sleep.  Need to tell a constructor about
2497                  * this - it might need to know...
2498                  */
2499                 ctor_flags |= SLAB_CTOR_ATOMIC;
2500
2501         /* Take the l3 list lock to change the colour_next on this node */
2502         check_irq_off();
2503         l3 = cachep->nodelists[nodeid];
2504         spin_lock(&l3->list_lock);
2505
2506         /* Get colour for the slab, and cal the next value. */
2507         offset = l3->colour_next;
2508         l3->colour_next++;
2509         if (l3->colour_next >= cachep->colour)
2510                 l3->colour_next = 0;
2511         spin_unlock(&l3->list_lock);
2512
2513         offset *= cachep->colour_off;
2514
2515         if (local_flags & __GFP_WAIT)
2516                 local_irq_enable();
2517
2518         /*
2519          * The test for missing atomic flag is performed here, rather than
2520          * the more obvious place, simply to reduce the critical path length
2521          * in kmem_cache_alloc(). If a caller is seriously mis-behaving they
2522          * will eventually be caught here (where it matters).
2523          */
2524         kmem_flagcheck(cachep, flags);
2525
2526         /*
2527          * Get mem for the objs.  Attempt to allocate a physical page from
2528          * 'nodeid'.
2529          */
2530         objp = kmem_getpages(cachep, flags, nodeid);
2531         if (!objp)
2532                 goto failed;
2533
2534         /* Get slab management. */
2535         slabp = alloc_slabmgmt(cachep, objp, offset, local_flags, nodeid);
2536         if (!slabp)
2537                 goto opps1;
2538
2539         slabp->nodeid = nodeid;
2540         set_slab_attr(cachep, slabp, objp);
2541
2542         cache_init_objs(cachep, slabp, ctor_flags);
2543
2544         if (local_flags & __GFP_WAIT)
2545                 local_irq_disable();
2546         check_irq_off();
2547         spin_lock(&l3->list_lock);
2548
2549         /* Make slab active. */
2550         list_add_tail(&slabp->list, &(l3->slabs_free));
2551         STATS_INC_GROWN(cachep);
2552         l3->free_objects += cachep->num;
2553         spin_unlock(&l3->list_lock);
2554         return 1;
2555 opps1:
2556         kmem_freepages(cachep, objp);
2557 failed:
2558         if (local_flags & __GFP_WAIT)
2559                 local_irq_disable();
2560         return 0;
2561 }
2562
2563 #if DEBUG
2564
2565 /*
2566  * Perform extra freeing checks:
2567  * - detect bad pointers.
2568  * - POISON/RED_ZONE checking
2569  * - destructor calls, for caches with POISON+dtor
2570  */
2571 static void kfree_debugcheck(const void *objp)
2572 {
2573         struct page *page;
2574
2575         if (!virt_addr_valid(objp)) {
2576                 printk(KERN_ERR "kfree_debugcheck: out of range ptr %lxh.\n",
2577                        (unsigned long)objp);
2578                 BUG();
2579         }
2580         page = virt_to_page(objp);
2581         if (!PageSlab(page)) {
2582                 printk(KERN_ERR "kfree_debugcheck: bad ptr %lxh.\n",
2583                        (unsigned long)objp);
2584                 BUG();
2585         }
2586 }
2587
2588 static void *cache_free_debugcheck(struct kmem_cache *cachep, void *objp,
2589                                    void *caller)
2590 {
2591         struct page *page;
2592         unsigned int objnr;
2593         struct slab *slabp;
2594
2595         objp -= obj_offset(cachep);
2596         kfree_debugcheck(objp);
2597         page = virt_to_page(objp);
2598
2599         if (page_get_cache(page) != cachep) {
2600                 printk(KERN_ERR "mismatch in kmem_cache_free: expected "
2601                                 "cache %p, got %p\n",
2602                        page_get_cache(page), cachep);
2603                 printk(KERN_ERR "%p is %s.\n", cachep, cachep->name);
2604                 printk(KERN_ERR "%p is %s.\n", page_get_cache(page),
2605                        page_get_cache(page)->name);
2606                 WARN_ON(1);
2607         }
2608         slabp = page_get_slab(page);
2609
2610         if (cachep->flags & SLAB_RED_ZONE) {
2611                 if (*dbg_redzone1(cachep, objp) != RED_ACTIVE ||
2612                                 *dbg_redzone2(cachep, objp) != RED_ACTIVE) {
2613                         slab_error(cachep, "double free, or memory outside"
2614                                                 " object was overwritten");
2615                         printk(KERN_ERR "%p: redzone 1:0x%lx, "
2616                                         "redzone 2:0x%lx.\n",
2617                                objp, *dbg_redzone1(cachep, objp),
2618                                *dbg_redzone2(cachep, objp));
2619                 }
2620                 *dbg_redzone1(cachep, objp) = RED_INACTIVE;
2621                 *dbg_redzone2(cachep, objp) = RED_INACTIVE;
2622         }
2623         if (cachep->flags & SLAB_STORE_USER)
2624                 *dbg_userword(cachep, objp) = caller;
2625
2626         objnr = obj_to_index(cachep, slabp, objp);
2627
2628         BUG_ON(objnr >= cachep->num);
2629         BUG_ON(objp != index_to_obj(cachep, slabp, objnr));
2630
2631         if (cachep->flags & SLAB_DEBUG_INITIAL) {
2632                 /*
2633                  * Need to call the slab's constructor so the caller can
2634                  * perform a verify of its state (debugging).  Called without
2635                  * the cache-lock held.
2636                  */
2637                 cachep->ctor(objp + obj_offset(cachep),
2638                              cachep, SLAB_CTOR_CONSTRUCTOR | SLAB_CTOR_VERIFY);
2639         }
2640         if (cachep->flags & SLAB_POISON && cachep->dtor) {
2641                 /* we want to cache poison the object,
2642                  * call the destruction callback
2643                  */
2644                 cachep->dtor(objp + obj_offset(cachep), cachep, 0);
2645         }
2646 #ifdef CONFIG_DEBUG_SLAB_LEAK
2647         slab_bufctl(slabp)[objnr] = BUFCTL_FREE;
2648 #endif
2649         if (cachep->flags & SLAB_POISON) {
2650 #ifdef CONFIG_DEBUG_PAGEALLOC
2651                 if ((cachep->buffer_size % PAGE_SIZE)==0 && OFF_SLAB(cachep)) {
2652                         store_stackinfo(cachep, objp, (unsigned long)caller);
2653                         kernel_map_pages(virt_to_page(objp),
2654                                          cachep->buffer_size / PAGE_SIZE, 0);
2655                 } else {
2656                         poison_obj(cachep, objp, POISON_FREE);
2657                 }
2658 #else
2659                 poison_obj(cachep, objp, POISON_FREE);
2660 #endif
2661         }
2662         return objp;
2663 }
2664
2665 static void check_slabp(struct kmem_cache *cachep, struct slab *slabp)
2666 {
2667         kmem_bufctl_t i;
2668         int entries = 0;
2669
2670         /* Check slab's freelist to see if this obj is there. */
2671         for (i = slabp->free; i != BUFCTL_END; i = slab_bufctl(slabp)[i]) {
2672                 entries++;
2673                 if (entries > cachep->num || i >= cachep->num)
2674                         goto bad;
2675         }
2676         if (entries != cachep->num - slabp->inuse) {
2677 bad:
2678                 printk(KERN_ERR "slab: Internal list corruption detected in "
2679                                 "cache '%s'(%d), slabp %p(%d). Hexdump:\n",
2680                         cachep->name, cachep->num, slabp, slabp->inuse);
2681                 for (i = 0;
2682                      i < sizeof(*slabp) + cachep->num * sizeof(kmem_bufctl_t);
2683                      i++) {
2684                         if (i % 16 == 0)
2685                                 printk("\n%03x:", i);
2686                         printk(" %02x", ((unsigned char *)slabp)[i]);
2687                 }
2688                 printk("\n");
2689                 BUG();
2690         }
2691 }
2692 #else
2693 #define kfree_debugcheck(x) do { } while(0)
2694 #define cache_free_debugcheck(x,objp,z) (objp)
2695 #define check_slabp(x,y) do { } while(0)
2696 #endif
2697
2698 static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags)
2699 {
2700         int batchcount;
2701         struct kmem_list3 *l3;
2702         struct array_cache *ac;
2703
2704         check_irq_off();
2705         ac = cpu_cache_get(cachep);
2706 retry:
2707         batchcount = ac->batchcount;
2708         if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {
2709                 /*
2710                  * If there was little recent activity on this cache, then
2711                  * perform only a partial refill.  Otherwise we could generate
2712                  * refill bouncing.
2713                  */
2714                 batchcount = BATCHREFILL_LIMIT;
2715         }
2716         l3 = cachep->nodelists[numa_node_id()];
2717
2718         BUG_ON(ac->avail > 0 || !l3);
2719         spin_lock(&l3->list_lock);
2720
2721         /* See if we can refill from the shared array */
2722         if (l3->shared && transfer_objects(ac, l3->shared, batchcount))
2723                 goto alloc_done;
2724
2725         while (batchcount > 0) {
2726                 struct list_head *entry;
2727                 struct slab *slabp;
2728                 /* Get slab alloc is to come from. */
2729                 entry = l3->slabs_partial.next;
2730                 if (entry == &l3->slabs_partial) {
2731                         l3->free_touched = 1;
2732                         entry = l3->slabs_free.next;
2733                         if (entry == &l3->slabs_free)
2734                                 goto must_grow;
2735                 }
2736
2737                 slabp = list_entry(entry, struct slab, list);
2738                 check_slabp(cachep, slabp);
2739                 check_spinlock_acquired(cachep);
2740                 while (slabp->inuse < cachep->num && batchcount--) {
2741                         STATS_INC_ALLOCED(cachep);
2742                         STATS_INC_ACTIVE(cachep);
2743                         STATS_SET_HIGH(cachep);
2744
2745                         ac->entry[ac->avail++] = slab_get_obj(cachep, slabp,
2746                                                             numa_node_id());
2747                 }
2748                 check_slabp(cachep, slabp);
2749
2750                 /* move slabp to correct slabp list: */
2751                 list_del(&slabp->list);
2752                 if (slabp->free == BUFCTL_END)
2753                         list_add(&slabp->list, &l3->slabs_full);
2754                 else
2755                         list_add(&slabp->list, &l3->slabs_partial);
2756         }
2757
2758 must_grow:
2759         l3->free_objects -= ac->avail;
2760 alloc_done:
2761         spin_unlock(&l3->list_lock);
2762
2763         if (unlikely(!ac->avail)) {
2764                 int x;
2765                 x = cache_grow(cachep, flags, numa_node_id());
2766
2767                 /* cache_grow can reenable interrupts, then ac could change. */
2768                 ac = cpu_cache_get(cachep);
2769                 if (!x && ac->avail == 0)       /* no objects in sight? abort */
2770                         return NULL;
2771
2772                 if (!ac->avail)         /* objects refilled by interrupt? */
2773                         goto retry;
2774         }
2775         ac->touched = 1;
2776         return ac->entry[--ac->avail];
2777 }
2778
2779 static inline void cache_alloc_debugcheck_before(struct kmem_cache *cachep,
2780                                                 gfp_t flags)
2781 {
2782         might_sleep_if(flags & __GFP_WAIT);
2783 #if DEBUG
2784         kmem_flagcheck(cachep, flags);
2785 #endif
2786 }
2787
2788 #if DEBUG
2789 static void *cache_alloc_debugcheck_after(struct kmem_cache *cachep,
2790                                 gfp_t flags, void *objp, void *caller)
2791 {
2792         if (!objp)
2793                 return objp;
2794         if (cachep->flags & SLAB_POISON) {
2795 #ifdef CONFIG_DEBUG_PAGEALLOC
2796                 if ((cachep->buffer_size % PAGE_SIZE) == 0 && OFF_SLAB(cachep))
2797                         kernel_map_pages(virt_to_page(objp),
2798                                          cachep->buffer_size / PAGE_SIZE, 1);
2799                 else
2800                         check_poison_obj(cachep, objp);
2801 #else
2802                 check_poison_obj(cachep, objp);
2803 #endif
2804                 poison_obj(cachep, objp, POISON_INUSE);
2805         }
2806         if (cachep->flags & SLAB_STORE_USER)
2807                 *dbg_userword(cachep, objp) = caller;
2808
2809         if (cachep->flags & SLAB_RED_ZONE) {
2810                 if (*dbg_redzone1(cachep, objp) != RED_INACTIVE ||
2811                                 *dbg_redzone2(cachep, objp) != RED_INACTIVE) {
2812                         slab_error(cachep, "double free, or memory outside"
2813                                                 " object was overwritten");
2814                         printk(KERN_ERR
2815                                 "%p: redzone 1:0x%lx, redzone 2:0x%lx\n",
2816                                 objp, *dbg_redzone1(cachep, objp),
2817                                 *dbg_redzone2(cachep, objp));
2818                 }
2819                 *dbg_redzone1(cachep, objp) = RED_ACTIVE;
2820                 *dbg_redzone2(cachep, objp) = RED_ACTIVE;
2821         }
2822 #ifdef CONFIG_DEBUG_SLAB_LEAK
2823         {
2824                 struct slab *slabp;
2825                 unsigned objnr;
2826
2827                 slabp = page_get_slab(virt_to_page(objp));
2828                 objnr = (unsigned)(objp - slabp->s_mem) / cachep->buffer_size;
2829                 slab_bufctl(slabp)[objnr] = BUFCTL_ACTIVE;
2830         }
2831 #endif
2832         objp += obj_offset(cachep);
2833         if (cachep->ctor && cachep->flags & SLAB_POISON) {
2834                 unsigned long ctor_flags = SLAB_CTOR_CONSTRUCTOR;
2835
2836                 if (!(flags & __GFP_WAIT))
2837                         ctor_flags |= SLAB_CTOR_ATOMIC;
2838
2839                 cachep->ctor(objp, cachep, ctor_flags);
2840         }
2841         return objp;
2842 }
2843 #else
2844 #define cache_alloc_debugcheck_after(a,b,objp,d) (objp)
2845 #endif
2846
2847 static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)
2848 {
2849         void *objp;
2850         struct array_cache *ac;
2851
2852 #ifdef CONFIG_NUMA
2853         if (unlikely(current->flags & (PF_SPREAD_SLAB | PF_MEMPOLICY))) {
2854                 objp = alternate_node_alloc(cachep, flags);
2855                 if (objp != NULL)
2856                         return objp;
2857         }
2858 #endif
2859
2860         check_irq_off();
2861         ac = cpu_cache_get(cachep);
2862         if (likely(ac->avail)) {
2863                 STATS_INC_ALLOCHIT(cachep);
2864                 ac->touched = 1;
2865                 objp = ac->entry[--ac->avail];
2866         } else {
2867                 STATS_INC_ALLOCMISS(cachep);
2868                 objp = cache_alloc_refill(cachep, flags);
2869         }
2870         return objp;
2871 }
2872
2873 static __always_inline void *__cache_alloc(struct kmem_cache *cachep,
2874                                                 gfp_t flags, void *caller)
2875 {
2876         unsigned long save_flags;
2877         void *objp;
2878
2879         cache_alloc_debugcheck_before(cachep, flags);
2880
2881         local_irq_save(save_flags);
2882         objp = ____cache_alloc(cachep, flags);
2883         local_irq_restore(save_flags);
2884         objp = cache_alloc_debugcheck_after(cachep, flags, objp,
2885                                             caller);
2886         prefetchw(objp);
2887         return objp;
2888 }
2889
2890 #ifdef CONFIG_NUMA
2891 /*
2892  * Try allocating on another node if PF_SPREAD_SLAB|PF_MEMPOLICY.
2893  *
2894  * If we are in_interrupt, then process context, including cpusets and
2895  * mempolicy, may not apply and should not be used for allocation policy.
2896  */
2897 static void *alternate_node_alloc(struct kmem_cache *cachep, gfp_t flags)
2898 {
2899         int nid_alloc, nid_here;
2900
2901         if (in_interrupt())
2902                 return NULL;
2903         nid_alloc = nid_here = numa_node_id();
2904         if (cpuset_do_slab_mem_spread() && (cachep->flags & SLAB_MEM_SPREAD))
2905                 nid_alloc = cpuset_mem_spread_node();
2906         else if (current->mempolicy)
2907                 nid_alloc = slab_node(current->mempolicy);
2908         if (nid_alloc != nid_here)
2909                 return __cache_alloc_node(cachep, flags, nid_alloc);
2910         return NULL;
2911 }
2912
2913 /*
2914  * A interface to enable slab creation on nodeid
2915  */
2916 static void *__cache_alloc_node(struct kmem_cache *cachep, gfp_t flags,
2917                                 int nodeid)
2918 {
2919         struct list_head *entry;
2920         struct slab *slabp;
2921         struct kmem_list3 *l3;
2922         void *obj;
2923         int x;
2924
2925         l3 = cachep->nodelists[nodeid];
2926         BUG_ON(!l3);
2927
2928 retry:
2929         check_irq_off();
2930         spin_lock(&l3->list_lock);
2931         entry = l3->slabs_partial.next;
2932         if (entry == &l3->slabs_partial) {
2933                 l3->free_touched = 1;
2934                 entry = l3->slabs_free.next;
2935                 if (entry == &l3->slabs_free)
2936                         goto must_grow;
2937         }
2938
2939         slabp = list_entry(entry, struct slab, list);
2940         check_spinlock_acquired_node(cachep, nodeid);
2941         check_slabp(cachep, slabp);
2942
2943         STATS_INC_NODEALLOCS(cachep);
2944         STATS_INC_ACTIVE(cachep);
2945         STATS_SET_HIGH(cachep);
2946
2947         BUG_ON(slabp->inuse == cachep->num);
2948
2949         obj = slab_get_obj(cachep, slabp, nodeid);
2950         check_slabp(cachep, slabp);
2951         l3->free_objects--;
2952         /* move slabp to correct slabp list: */
2953         list_del(&slabp->list);
2954
2955         if (slabp->free == BUFCTL_END)
2956                 list_add(&slabp->list, &l3->slabs_full);
2957         else
2958                 list_add(&slabp->list, &l3->slabs_partial);
2959
2960         spin_unlock(&l3->list_lock);
2961         goto done;
2962
2963 must_grow:
2964         spin_unlock(&l3->list_lock);
2965         x = cache_grow(cachep, flags, nodeid);
2966
2967         if (!x)
2968                 return NULL;
2969
2970         goto retry;
2971 done:
2972         return obj;
2973 }
2974 #endif
2975
2976 /*
2977  * Caller needs to acquire correct kmem_list's list_lock
2978  */
2979 static void free_block(struct kmem_cache *cachep, void **objpp, int nr_objects,
2980                        int node)
2981 {
2982         int i;
2983         struct kmem_list3 *l3;
2984
2985         for (i = 0; i < nr_objects; i++) {
2986                 void *objp = objpp[i];
2987                 struct slab *slabp;
2988
2989                 slabp = virt_to_slab(objp);
2990                 l3 = cachep->nodelists[node];
2991                 list_del(&slabp->list);
2992                 check_spinlock_acquired_node(cachep, node);
2993                 check_slabp(cachep, slabp);
2994                 slab_put_obj(cachep, slabp, objp, node);
2995                 STATS_DEC_ACTIVE(cachep);
2996                 l3->free_objects++;
2997                 check_slabp(cachep, slabp);
2998
2999                 /* fixup slab chains */
3000                 if (slabp->inuse == 0) {
3001                         if (l3->free_objects > l3->free_limit) {
3002                                 l3->free_objects -= cachep->num;
3003                                 slab_destroy(cachep, slabp);
3004                         } else {
3005                                 list_add(&slabp->list, &l3->slabs_free);
3006                         }
3007                 } else {
3008                         /* Unconditionally move a slab to the end of the
3009                          * partial list on free - maximum time for the
3010                          * other objects to be freed, too.
3011                          */
3012                         list_add_tail(&slabp->list, &l3->slabs_partial);
3013                 }
3014         }
3015 }
3016
3017 static void cache_flusharray(struct kmem_cache *cachep, struct array_cache *ac)
3018 {
3019         int batchcount;
3020         struct kmem_list3 *l3;
3021         int node = numa_node_id();
3022
3023         batchcount = ac->batchcount;
3024 #if DEBUG
3025         BUG_ON(!batchcount || batchcount > ac->avail);
3026 #endif
3027         check_irq_off();
3028         l3 = cachep->nodelists[node];
3029         spin_lock(&l3->list_lock);
3030         if (l3->shared) {
3031                 struct array_cache *shared_array = l3->shared;
3032                 int max = shared_array->limit - shared_array->avail;
3033                 if (max) {
3034                         if (batchcount > max)
3035                                 batchcount = max;
3036                         memcpy(&(shared_array->entry[shared_array->avail]),
3037                                ac->entry, sizeof(void *) * batchcount);
3038                         shared_array->avail += batchcount;
3039                         goto free_done;
3040                 }
3041         }
3042
3043         free_block(cachep, ac->entry, batchcount, node);
3044 free_done:
3045 #if STATS
3046         {
3047                 int i = 0;
3048                 struct list_head *p;
3049
3050                 p = l3->slabs_free.next;
3051                 while (p != &(l3->slabs_free)) {
3052                         struct slab *slabp;
3053
3054                         slabp = list_entry(p, struct slab, list);
3055                         BUG_ON(slabp->inuse);
3056
3057                         i++;
3058                         p = p->next;
3059                 }
3060                 STATS_SET_FREEABLE(cachep, i);
3061         }
3062 #endif
3063         spin_unlock(&l3->list_lock);
3064         ac->avail -= batchcount;
3065         memmove(ac->entry, &(ac->entry[batchcount]), sizeof(void *)*ac->avail);
3066 }
3067
3068 /*
3069  * Release an obj back to its cache. If the obj has a constructed state, it must
3070  * be in this state _before_ it is released.  Called with disabled ints.
3071  */
3072 static inline void __cache_free(struct kmem_cache *cachep, void *objp)
3073 {
3074         struct array_cache *ac = cpu_cache_get(cachep);
3075
3076         check_irq_off();
3077         objp = cache_free_debugcheck(cachep, objp, __builtin_return_address(0));
3078
3079         /* Make sure we are not freeing a object from another
3080          * node to the array cache on this cpu.
3081          */
3082 #ifdef CONFIG_NUMA
3083         {
3084                 struct slab *slabp;
3085                 slabp = virt_to_slab(objp);
3086                 if (unlikely(slabp->nodeid != numa_node_id())) {
3087                         struct array_cache *alien = NULL;
3088                         int nodeid = slabp->nodeid;
3089                         struct kmem_list3 *l3;
3090
3091                         l3 = cachep->nodelists[numa_node_id()];
3092                         STATS_INC_NODEFREES(cachep);
3093                         if (l3->alien && l3->alien[nodeid]) {
3094                                 alien = l3->alien[nodeid];
3095                                 spin_lock(&alien->lock);
3096                                 if (unlikely(alien->avail == alien->limit)) {
3097                                         STATS_INC_ACOVERFLOW(cachep);
3098                                         __drain_alien_cache(cachep,
3099                                                             alien, nodeid);
3100                                 }
3101                                 alien->entry[alien->avail++] = objp;
3102                                 spin_unlock(&alien->lock);
3103                         } else {
3104                                 spin_lock(&(cachep->nodelists[nodeid])->
3105                                           list_lock);
3106                                 free_block(cachep, &objp, 1, nodeid);
3107                                 spin_unlock(&(cachep->nodelists[nodeid])->
3108                                             list_lock);
3109                         }
3110                         return;
3111                 }
3112         }
3113 #endif
3114         if (likely(ac->avail < ac->limit)) {
3115                 STATS_INC_FREEHIT(cachep);
3116                 ac->entry[ac->avail++] = objp;
3117                 return;
3118         } else {
3119                 STATS_INC_FREEMISS(cachep);
3120                 cache_flusharray(cachep, ac);
3121                 ac->entry[ac->avail++] = objp;
3122         }
3123 }
3124
3125 /**
3126  * kmem_cache_alloc - Allocate an object
3127  * @cachep: The cache to allocate from.
3128  * @flags: See kmalloc().
3129  *
3130  * Allocate an object from this cache.  The flags are only relevant
3131  * if the cache has no available objects.
3132  */
3133 void *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags)
3134 {
3135         return __cache_alloc(cachep, flags, __builtin_return_address(0));
3136 }
3137 EXPORT_SYMBOL(kmem_cache_alloc);
3138
3139 /**
3140  * kmem_cache_alloc - Allocate an object. The memory is set to zero.
3141  * @cache: The cache to allocate from.
3142  * @flags: See kmalloc().
3143  *
3144  * Allocate an object from this cache and set the allocated memory to zero.
3145  * The flags are only relevant if the cache has no available objects.
3146  */
3147 void *kmem_cache_zalloc(struct kmem_cache *cache, gfp_t flags)
3148 {
3149         void *ret = __cache_alloc(cache, flags, __builtin_return_address(0));
3150         if (ret)
3151                 memset(ret, 0, obj_size(cache));
3152         return ret;
3153 }
3154 EXPORT_SYMBOL(kmem_cache_zalloc);
3155
3156 /**
3157  * kmem_ptr_validate - check if an untrusted pointer might
3158  *      be a slab entry.
3159  * @cachep: the cache we're checking against
3160  * @ptr: pointer to validate
3161  *
3162  * This verifies that the untrusted pointer looks sane:
3163  * it is _not_ a guarantee that the pointer is actually
3164  * part of the slab cache in question, but it at least
3165  * validates that the pointer can be dereferenced and
3166  * looks half-way sane.
3167  *
3168  * Currently only used for dentry validation.
3169  */
3170 int fastcall kmem_ptr_validate(struct kmem_cache *cachep, void *ptr)
3171 {
3172         unsigned long addr = (unsigned long)ptr;
3173         unsigned long min_addr = PAGE_OFFSET;
3174         unsigned long align_mask = BYTES_PER_WORD - 1;
3175         unsigned long size = cachep->buffer_size;
3176         struct page *page;
3177
3178         if (unlikely(addr < min_addr))
3179                 goto out;
3180         if (unlikely(addr > (unsigned long)high_memory - size))
3181                 goto out;
3182         if (unlikely(addr & align_mask))
3183                 goto out;
3184         if (unlikely(!kern_addr_valid(addr)))
3185                 goto out;
3186         if (unlikely(!kern_addr_valid(addr + size - 1)))
3187                 goto out;
3188         page = virt_to_page(ptr);
3189         if (unlikely(!PageSlab(page)))
3190                 goto out;
3191         if (unlikely(page_get_cache(page) != cachep))
3192                 goto out;
3193         return 1;
3194 out:
3195         return 0;
3196 }
3197
3198 #ifdef CONFIG_NUMA
3199 /**
3200  * kmem_cache_alloc_node - Allocate an object on the specified node
3201  * @cachep: The cache to allocate from.
3202  * @flags: See kmalloc().
3203  * @nodeid: node number of the target node.
3204  *
3205  * Identical to kmem_cache_alloc, except that this function is slow
3206  * and can sleep. And it will allocate memory on the given node, which
3207  * can improve the performance for cpu bound structures.
3208  * New and improved: it will now make sure that the object gets
3209  * put on the correct node list so that there is no false sharing.
3210  */
3211 void *kmem_cache_alloc_node(struct kmem_cache *cachep, gfp_t flags, int nodeid)
3212 {
3213         unsigned long save_flags;
3214         void *ptr;
3215
3216         cache_alloc_debugcheck_before(cachep, flags);
3217         local_irq_save(save_flags);
3218
3219         if (nodeid == -1 || nodeid == numa_node_id() ||
3220                         !cachep->nodelists[nodeid])
3221                 ptr = ____cache_alloc(cachep, flags);
3222         else
3223                 ptr = __cache_alloc_node(cachep, flags, nodeid);
3224         local_irq_restore(save_flags);
3225
3226         ptr = cache_alloc_debugcheck_after(cachep, flags, ptr,
3227                                            __builtin_return_address(0));
3228
3229         return ptr;
3230 }
3231 EXPORT_SYMBOL(kmem_cache_alloc_node);
3232
3233 void *kmalloc_node(size_t size, gfp_t flags, int node)
3234 {
3235         struct kmem_cache *cachep;
3236
3237         cachep = kmem_find_general_cachep(size, flags);
3238         if (unlikely(cachep == NULL))
3239                 return NULL;
3240         return kmem_cache_alloc_node(cachep, flags, node);
3241 }
3242 EXPORT_SYMBOL(kmalloc_node);
3243 #endif
3244
3245 /**
3246  * kmalloc - allocate memory
3247  * @size: how many bytes of memory are required.
3248  * @flags: the type of memory to allocate.
3249  * @caller: function caller for debug tracking of the caller
3250  *
3251  * kmalloc is the normal method of allocating memory
3252  * in the kernel.
3253  *
3254  * The @flags argument may be one of:
3255  *
3256  * %GFP_USER - Allocate memory on behalf of user.  May sleep.
3257  *
3258  * %GFP_KERNEL - Allocate normal kernel ram.  May sleep.
3259  *
3260  * %GFP_ATOMIC - Allocation will not sleep.  Use inside interrupt handlers.
3261  *
3262  * Additionally, the %GFP_DMA flag may be set to indicate the memory
3263  * must be suitable for DMA.  This can mean different things on different
3264  * platforms.  For example, on i386, it means that the memory must come
3265  * from the first 16MB.
3266  */
3267 static __always_inline void *__do_kmalloc(size_t size, gfp_t flags,
3268                                           void *caller)
3269 {
3270         struct kmem_cache *cachep;
3271
3272         /* If you want to save a few bytes .text space: replace
3273          * __ with kmem_.
3274          * Then kmalloc uses the uninlined functions instead of the inline
3275          * functions.
3276          */
3277         cachep = __find_general_cachep(size, flags);
3278         if (unlikely(cachep == NULL))
3279                 return NULL;
3280         return __cache_alloc(cachep, flags, caller);
3281 }
3282
3283
3284 void *__kmalloc(size_t size, gfp_t flags)
3285 {
3286 #ifndef CONFIG_DEBUG_SLAB
3287         return __do_kmalloc(size, flags, NULL);
3288 #else
3289         return __do_kmalloc(size, flags, __builtin_return_address(0));
3290 #endif
3291 }
3292 EXPORT_SYMBOL(__kmalloc);
3293
3294 #ifdef CONFIG_DEBUG_SLAB
3295 void *__kmalloc_track_caller(size_t size, gfp_t flags, void *caller)
3296 {
3297         return __do_kmalloc(size, flags, caller);
3298 }
3299 EXPORT_SYMBOL(__kmalloc_track_caller);
3300 #endif
3301
3302 #ifdef CONFIG_SMP
3303 /**
3304  * __alloc_percpu - allocate one copy of the object for every present
3305  * cpu in the system, zeroing them.
3306  * Objects should be dereferenced using the per_cpu_ptr macro only.
3307  *
3308  * @size: how many bytes of memory are required.
3309  */
3310 void *__alloc_percpu(size_t size)
3311 {
3312         int i;
3313         struct percpu_data *pdata = kmalloc(sizeof(*pdata), GFP_KERNEL);
3314
3315         if (!pdata)
3316                 return NULL;
3317
3318         /*
3319          * Cannot use for_each_online_cpu since a cpu may come online
3320          * and we have no way of figuring out how to fix the array
3321          * that we have allocated then....
3322          */
3323         for_each_possible_cpu(i) {
3324                 int node = cpu_to_node(i);
3325
3326                 if (node_online(node))
3327                         pdata->ptrs[i] = kmalloc_node(size, GFP_KERNEL, node);
3328                 else
3329                         pdata->ptrs[i] = kmalloc(size, GFP_KERNEL);
3330
3331                 if (!pdata->ptrs[i])
3332                         goto unwind_oom;
3333                 memset(pdata->ptrs[i], 0, size);
3334         }
3335
3336         /* Catch derefs w/o wrappers */
3337         return (void *)(~(unsigned long)pdata);
3338
3339 unwind_oom:
3340         while (--i >= 0) {
3341                 if (!cpu_possible(i))
3342                         continue;
3343                 kfree(pdata->ptrs[i]);
3344         }
3345         kfree(pdata);
3346         return NULL;
3347 }
3348 EXPORT_SYMBOL(__alloc_percpu);
3349 #endif
3350
3351 /**
3352  * kmem_cache_free - Deallocate an object
3353  * @cachep: The cache the allocation was from.
3354  * @objp: The previously allocated object.
3355  *
3356  * Free an object which was previously allocated from this
3357  * cache.
3358  */
3359 void kmem_cache_free(struct kmem_cache *cachep, void *objp)
3360 {
3361         unsigned long flags;
3362
3363         local_irq_save(flags);
3364         __cache_free(cachep, objp);
3365         local_irq_restore(flags);
3366 }
3367 EXPORT_SYMBOL(kmem_cache_free);
3368
3369 /**
3370  * kfree - free previously allocated memory
3371  * @objp: pointer returned by kmalloc.
3372  *
3373  * If @objp is NULL, no operation is performed.
3374  *
3375  * Don't free memory not originally allocated by kmalloc()
3376  * or you will run into trouble.
3377  */
3378 void kfree(const void *objp)
3379 {
3380         struct kmem_cache *c;
3381         unsigned long flags;
3382
3383         if (unlikely(!objp))
3384                 return;
3385         local_irq_save(flags);
3386         kfree_debugcheck(objp);
3387         c = virt_to_cache(objp);
3388         mutex_debug_check_no_locks_freed(objp, obj_size(c));
3389         __cache_free(c, (void *)objp);
3390         local_irq_restore(flags);
3391 }
3392 EXPORT_SYMBOL(kfree);
3393
3394 #ifdef CONFIG_SMP
3395 /**
3396  * free_percpu - free previously allocated percpu memory
3397  * @objp: pointer returned by alloc_percpu.
3398  *
3399  * Don't free memory not originally allocated by alloc_percpu()
3400  * The complemented objp is to check for that.
3401  */
3402 void free_percpu(const void *objp)
3403 {
3404         int i;
3405         struct percpu_data *p = (struct percpu_data *)(~(unsigned long)objp);
3406
3407         /*
3408          * We allocate for all cpus so we cannot use for online cpu here.
3409          */
3410         for_each_possible_cpu(i)
3411             kfree(p->ptrs[i]);
3412         kfree(p);
3413 }
3414 EXPORT_SYMBOL(free_percpu);
3415 #endif
3416
3417 unsigned int kmem_cache_size(struct kmem_cache *cachep)
3418 {
3419         return obj_size(cachep);
3420 }
3421 EXPORT_SYMBOL(kmem_cache_size);
3422
3423 const char *kmem_cache_name(struct kmem_cache *cachep)
3424 {
3425         return cachep->name;
3426 }
3427 EXPORT_SYMBOL_GPL(kmem_cache_name);
3428
3429 /*
3430  * This initializes kmem_list3 or resizes varioius caches for all nodes.
3431  */
3432 static int alloc_kmemlist(struct kmem_cache *cachep)
3433 {
3434         int node;
3435         struct kmem_list3 *l3;
3436         struct array_cache *new_shared;
3437         struct array_cache **new_alien;
3438
3439         for_each_online_node(node) {
3440
3441                 new_alien = alloc_alien_cache(node, cachep->limit);
3442                 if (!new_alien)
3443                         goto fail;
3444
3445                 new_shared = alloc_arraycache(node,
3446                                 cachep->shared*cachep->batchcount,
3447                                         0xbaadf00d);
3448                 if (!new_shared) {
3449                         free_alien_cache(new_alien);
3450                         goto fail;
3451                 }
3452
3453                 l3 = cachep->nodelists[node];
3454                 if (l3) {
3455                         struct array_cache *shared = l3->shared;
3456
3457                         spin_lock_irq(&l3->list_lock);
3458
3459                         if (shared)
3460                                 free_block(cachep, shared->entry,
3461                                                 shared->avail, node);
3462
3463                         l3->shared = new_shared;
3464                         if (!l3->alien) {
3465                                 l3->alien = new_alien;
3466                                 new_alien = NULL;
3467                         }
3468                         l3->free_limit = (1 + nr_cpus_node(node)) *
3469                                         cachep->batchcount + cachep->num;
3470                         spin_unlock_irq(&l3->list_lock);
3471                         kfree(shared);
3472                         free_alien_cache(new_alien);
3473                         continue;
3474                 }
3475                 l3 = kmalloc_node(sizeof(struct kmem_list3), GFP_KERNEL, node);
3476                 if (!l3) {
3477                         free_alien_cache(new_alien);
3478                         kfree(new_shared);
3479                         goto fail;
3480                 }
3481
3482                 kmem_list3_init(l3);
3483                 l3->next_reap = jiffies + REAPTIMEOUT_LIST3 +
3484                                 ((unsigned long)cachep) % REAPTIMEOUT_LIST3;
3485                 l3->shared = new_shared;
3486                 l3->alien = new_alien;
3487                 l3->free_limit = (1 + nr_cpus_node(node)) *
3488                                         cachep->batchcount + cachep->num;
3489                 cachep->nodelists[node] = l3;
3490         }
3491         return 0;
3492
3493 fail:
3494         if (!cachep->next.next) {
3495                 /* Cache is not active yet. Roll back what we did */
3496                 node--;
3497                 while (node >= 0) {
3498                         if (cachep->nodelists[node]) {
3499                                 l3 = cachep->nodelists[node];
3500
3501                                 kfree(l3->shared);
3502                                 free_alien_cache(l3->alien);
3503                                 kfree(l3);
3504                                 cachep->nodelists[node] = NULL;
3505                         }
3506                         node--;
3507                 }
3508         }
3509         return -ENOMEM;
3510 }
3511
3512 struct ccupdate_struct {
3513         struct kmem_cache *cachep;
3514         struct array_cache *new[NR_CPUS];
3515 };
3516
3517 static void do_ccupdate_local(void *info)
3518 {
3519         struct ccupdate_struct *new = info;
3520         struct array_cache *old;
3521
3522         check_irq_off();
3523         old = cpu_cache_get(new->cachep);
3524
3525         new->cachep->array[smp_processor_id()] = new->new[smp_processor_id()];
3526         new->new[smp_processor_id()] = old;
3527 }
3528
3529 /* Always called with the cache_chain_mutex held */
3530 static int do_tune_cpucache(struct kmem_cache *cachep, int limit,
3531                                 int batchcount, int shared)
3532 {
3533         struct ccupdate_struct new;
3534         int i, err;
3535
3536         memset(&new.new, 0, sizeof(new.new));
3537         for_each_online_cpu(i) {
3538                 new.new[i] = alloc_arraycache(cpu_to_node(i), limit,
3539                                                 batchcount);
3540                 if (!new.new[i]) {
3541                         for (i--; i >= 0; i--)
3542                                 kfree(new.new[i]);
3543                         return -ENOMEM;
3544                 }
3545         }
3546         new.cachep = cachep;
3547
3548         on_each_cpu(do_ccupdate_local, (void *)&new, 1, 1);
3549
3550         check_irq_on();
3551         cachep->batchcount = batchcount;
3552         cachep->limit = limit;
3553         cachep->shared = shared;
3554
3555         for_each_online_cpu(i) {
3556                 struct array_cache *ccold = new.new[i];
3557                 if (!ccold)
3558                         continue;
3559                 spin_lock_irq(&cachep->nodelists[cpu_to_node(i)]->list_lock);
3560                 free_block(cachep, ccold->entry, ccold->avail, cpu_to_node(i));
3561                 spin_unlock_irq(&cachep->nodelists[cpu_to_node(i)]->list_lock);
3562                 kfree(ccold);
3563         }
3564
3565         err = alloc_kmemlist(cachep);
3566         if (err) {
3567                 printk(KERN_ERR "alloc_kmemlist failed for %s, error %d.\n",
3568                        cachep->name, -err);
3569                 BUG();
3570         }
3571         return 0;
3572 }
3573
3574 /* Called with cache_chain_mutex held always */
3575 static void enable_cpucache(struct kmem_cache *cachep)
3576 {
3577         int err;
3578         int limit, shared;
3579
3580         /*
3581          * The head array serves three purposes:
3582          * - create a LIFO ordering, i.e. return objects that are cache-warm
3583          * - reduce the number of spinlock operations.
3584          * - reduce the number of linked list operations on the slab and
3585          *   bufctl chains: array operations are cheaper.
3586          * The numbers are guessed, we should auto-tune as described by
3587          * Bonwick.
3588          */
3589         if (cachep->buffer_size > 131072)
3590                 limit = 1;
3591         else if (cachep->buffer_size > PAGE_SIZE)
3592                 limit = 8;
3593         else if (cachep->buffer_size > 1024)
3594                 limit = 24;
3595         else if (cachep->buffer_size > 256)
3596                 limit = 54;
3597         else
3598                 limit = 120;
3599
3600         /*
3601          * CPU bound tasks (e.g. network routing) can exhibit cpu bound
3602          * allocation behaviour: Most allocs on one cpu, most free operations
3603          * on another cpu. For these cases, an efficient object passing between
3604          * cpus is necessary. This is provided by a shared array. The array
3605          * replaces Bonwick's magazine layer.
3606          * On uniprocessor, it's functionally equivalent (but less efficient)
3607          * to a larger limit. Thus disabled by default.
3608          */
3609         shared = 0;
3610 #ifdef CONFIG_SMP
3611         if (cachep->buffer_size <= PAGE_SIZE)
3612                 shared = 8;
3613 #endif
3614
3615 #if DEBUG
3616         /*
3617          * With debugging enabled, large batchcount lead to excessively long
3618          * periods with disabled local interrupts. Limit the batchcount
3619          */
3620         if (limit > 32)
3621                 limit = 32;
3622 #endif
3623         err = do_tune_cpucache(cachep, limit, (limit + 1) / 2, shared);
3624         if (err)
3625                 printk(KERN_ERR "enable_cpucache failed for %s, error %d.\n",
3626                        cachep->name, -err);
3627 }
3628
3629 /*
3630  * Drain an array if it contains any elements taking the l3 lock only if
3631  * necessary. Note that the l3 listlock also protects the array_cache
3632  * if drain_array() is used on the shared array.
3633  */
3634 void drain_array(struct kmem_cache *cachep, struct kmem_list3 *l3,
3635                          struct array_cache *ac, int force, int node)
3636 {
3637         int tofree;
3638
3639         if (!ac || !ac->avail)
3640                 return;
3641         if (ac->touched && !force) {
3642                 ac->touched = 0;
3643         } else {
3644                 spin_lock_irq(&l3->list_lock);
3645                 if (ac->avail) {
3646                         tofree = force ? ac->avail : (ac->limit + 4) / 5;
3647                         if (tofree > ac->avail)
3648                                 tofree = (ac->avail + 1) / 2;
3649                         free_block(cachep, ac->entry, tofree, node);
3650                         ac->avail -= tofree;
3651                         memmove(ac->entry, &(ac->entry[tofree]),
3652                                 sizeof(void *) * ac->avail);
3653                 }
3654                 spin_unlock_irq(&l3->list_lock);
3655         }
3656 }
3657
3658 /**
3659  * cache_reap - Reclaim memory from caches.
3660  * @unused: unused parameter
3661  *
3662  * Called from workqueue/eventd every few seconds.
3663  * Purpose:
3664  * - clear the per-cpu caches for this CPU.
3665  * - return freeable pages to the main free memory pool.
3666  *
3667  * If we cannot acquire the cache chain mutex then just give up - we'll try
3668  * again on the next iteration.
3669  */
3670 static void cache_reap(void *unused)
3671 {
3672         struct list_head *walk;
3673         struct kmem_list3 *l3;
3674         int node = numa_node_id();
3675
3676         if (!mutex_trylock(&cache_chain_mutex)) {
3677                 /* Give up. Setup the next iteration. */
3678                 schedule_delayed_work(&__get_cpu_var(reap_work),
3679                                       REAPTIMEOUT_CPUC);
3680                 return;
3681         }
3682
3683         list_for_each(walk, &cache_chain) {
3684                 struct kmem_cache *searchp;
3685                 struct list_head *p;
3686                 int tofree;
3687                 struct slab *slabp;
3688
3689                 searchp = list_entry(walk, struct kmem_cache, next);
3690                 check_irq_on();
3691
3692                 /*
3693                  * We only take the l3 lock if absolutely necessary and we
3694                  * have established with reasonable certainty that
3695                  * we can do some work if the lock was obtained.
3696                  */
3697                 l3 = searchp->nodelists[node];
3698
3699                 reap_alien(searchp, l3);
3700
3701                 drain_array(searchp, l3, cpu_cache_get(searchp), 0, node);
3702
3703                 /*
3704                  * These are racy checks but it does not matter
3705                  * if we skip one check or scan twice.
3706                  */
3707                 if (time_after(l3->next_reap, jiffies))
3708                         goto next;
3709
3710                 l3->next_reap = jiffies + REAPTIMEOUT_LIST3;
3711
3712                 drain_array(searchp, l3, l3->shared, 0, node);
3713
3714                 if (l3->free_touched) {
3715                         l3->free_touched = 0;
3716                         goto next;
3717                 }
3718
3719                 tofree = (l3->free_limit + 5 * searchp->num - 1) /
3720                                 (5 * searchp->num);
3721                 do {
3722                         /*
3723                          * Do not lock if there are no free blocks.
3724                          */
3725                         if (list_empty(&l3->slabs_free))
3726                                 break;
3727
3728                         spin_lock_irq(&l3->list_lock);
3729                         p = l3->slabs_free.next;
3730                         if (p == &(l3->slabs_free)) {
3731                                 spin_unlock_irq(&l3->list_lock);
3732                                 break;
3733                         }
3734
3735                         slabp = list_entry(p, struct slab, list);
3736                         BUG_ON(slabp->inuse);
3737                         list_del(&slabp->list);
3738                         STATS_INC_REAPED(searchp);
3739
3740                         /*
3741                          * Safe to drop the lock. The slab is no longer linked
3742                          * to the cache. searchp cannot disappear, we hold
3743                          * cache_chain_lock
3744                          */
3745                         l3->free_objects -= searchp->num;
3746                         spin_unlock_irq(&l3->list_lock);
3747                         slab_destroy(searchp, slabp);
3748                 } while (--tofree > 0);
3749 next:
3750                 cond_resched();
3751         }
3752         check_irq_on();
3753         mutex_unlock(&cache_chain_mutex);
3754         next_reap_node();
3755         /* Set up the next iteration */
3756         schedule_delayed_work(&__get_cpu_var(reap_work), REAPTIMEOUT_CPUC);
3757 }
3758
3759 #ifdef CONFIG_PROC_FS
3760
3761 static void print_slabinfo_header(struct seq_file *m)
3762 {
3763         /*
3764          * Output format version, so at least we can change it
3765          * without _too_ many complaints.
3766          */
3767 #if STATS
3768         seq_puts(m, "slabinfo - version: 2.1 (statistics)\n");
3769 #else
3770         seq_puts(m, "slabinfo - version: 2.1\n");
3771 #endif
3772         seq_puts(m, "# name            <active_objs> <num_objs> <objsize> "
3773                  "<objperslab> <pagesperslab>");
3774         seq_puts(m, " : tunables <limit> <batchcount> <sharedfactor>");
3775         seq_puts(m, " : slabdata <active_slabs> <num_slabs> <sharedavail>");
3776 #if STATS
3777         seq_puts(m, " : globalstat <listallocs> <maxobjs> <grown> <reaped> "
3778                  "<error> <maxfreeable> <nodeallocs> <remotefrees> <alienoverflow>");
3779         seq_puts(m, " : cpustat <allochit> <allocmiss> <freehit> <freemiss>");
3780 #endif
3781         seq_putc(m, '\n');
3782 }
3783
3784 static void *s_start(struct seq_file *m, loff_t *pos)
3785 {
3786         loff_t n = *pos;
3787         struct list_head *p;
3788
3789         mutex_lock(&cache_chain_mutex);
3790         if (!n)
3791                 print_slabinfo_header(m);
3792         p = cache_chain.next;
3793         while (n--) {
3794                 p = p->next;
3795                 if (p == &cache_chain)
3796                         return NULL;
3797         }
3798         return list_entry(p, struct kmem_cache, next);
3799 }
3800
3801 static void *s_next(struct seq_file *m, void *p, loff_t *pos)
3802 {
3803         struct kmem_cache *cachep = p;
3804         ++*pos;
3805         return cachep->next.next == &cache_chain ?
3806                 NULL : list_entry(cachep->next.next, struct kmem_cache, next);
3807 }
3808
3809 static void s_stop(struct seq_file *m, void *p)
3810 {
3811         mutex_unlock(&cache_chain_mutex);
3812 }
3813
3814 static int s_show(struct seq_file *m, void *p)
3815 {
3816         struct kmem_cache *cachep = p;
3817         struct list_head *q;
3818         struct slab *slabp;
3819         unsigned long active_objs;
3820         unsigned long num_objs;
3821         unsigned long active_slabs = 0;
3822         unsigned long num_slabs, free_objects = 0, shared_avail = 0;
3823         const char *name;
3824         char *error = NULL;
3825         int node;
3826         struct kmem_list3 *l3;
3827
3828         active_objs = 0;
3829         num_slabs = 0;
3830         for_each_online_node(node) {
3831                 l3 = cachep->nodelists[node];
3832                 if (!l3)
3833                         continue;
3834
3835                 check_irq_on();
3836                 spin_lock_irq(&l3->list_lock);
3837
3838                 list_for_each(q, &l3->slabs_full) {
3839                         slabp = list_entry(q, struct slab, list);
3840                         if (slabp->inuse != cachep->num && !error)
3841                                 error = "slabs_full accounting error";
3842                         active_objs += cachep->num;
3843                         active_slabs++;
3844                 }
3845                 list_for_each(q, &l3->slabs_partial) {
3846                         slabp = list_entry(q, struct slab, list);
3847                         if (slabp->inuse == cachep->num && !error)
3848                                 error = "slabs_partial inuse accounting error";
3849                         if (!slabp->inuse && !error)
3850                                 error = "slabs_partial/inuse accounting error";
3851                         active_objs += slabp->inuse;
3852                         active_slabs++;
3853                 }
3854                 list_for_each(q, &l3->slabs_free) {
3855                         slabp = list_entry(q, struct slab, list);
3856                         if (slabp->inuse && !error)
3857                                 error = "slabs_free/inuse accounting error";
3858                         num_slabs++;
3859                 }
3860                 free_objects += l3->free_objects;
3861                 if (l3->shared)
3862                         shared_avail += l3->shared->avail;
3863
3864                 spin_unlock_irq(&l3->list_lock);
3865         }
3866         num_slabs += active_slabs;
3867         num_objs = num_slabs * cachep->num;
3868         if (num_objs - active_objs != free_objects && !error)
3869                 error = "free_objects accounting error";
3870
3871         name = cachep->name;
3872         if (error)
3873                 printk(KERN_ERR "slab: cache %s error: %s\n", name, error);
3874
3875         seq_printf(m, "%-17s %6lu %6lu %6u %4u %4d",
3876                    name, active_objs, num_objs, cachep->buffer_size,
3877                    cachep->num, (1 << cachep->gfporder));
3878         seq_printf(m, " : tunables %4u %4u %4u",
3879                    cachep->limit, cachep->batchcount, cachep->shared);
3880         seq_printf(m, " : slabdata %6lu %6lu %6lu",
3881                    active_slabs, num_slabs, shared_avail);
3882 #if STATS
3883         {                       /* list3 stats */
3884                 unsigned long high = cachep->high_mark;
3885                 unsigned long allocs = cachep->num_allocations;
3886                 unsigned long grown = cachep->grown;
3887                 unsigned long reaped = cachep->reaped;
3888                 unsigned long errors = cachep->errors;
3889                 unsigned long max_freeable = cachep->max_freeable;
3890                 unsigned long node_allocs = cachep->node_allocs;
3891                 unsigned long node_frees = cachep->node_frees;
3892                 unsigned long overflows = cachep->node_overflow;
3893
3894                 seq_printf(m, " : globalstat %7lu %6lu %5lu %4lu \
3895                                 %4lu %4lu %4lu %4lu %4lu", allocs, high, grown,
3896                                 reaped, errors, max_freeable, node_allocs,
3897                                 node_frees, overflows);
3898         }
3899         /* cpu stats */
3900         {
3901                 unsigned long allochit = atomic_read(&cachep->allochit);
3902                 unsigned long allocmiss = atomic_read(&cachep->allocmiss);
3903                 unsigned long freehit = atomic_read(&cachep->freehit);
3904                 unsigned long freemiss = atomic_read(&cachep->freemiss);
3905
3906                 seq_printf(m, " : cpustat %6lu %6lu %6lu %6lu",
3907                            allochit, allocmiss, freehit, freemiss);
3908         }
3909 #endif
3910         seq_putc(m, '\n');
3911         return 0;
3912 }
3913
3914 /*
3915  * slabinfo_op - iterator that generates /proc/slabinfo
3916  *
3917  * Output layout:
3918  * cache-name
3919  * num-active-objs
3920  * total-objs
3921  * object size
3922  * num-active-slabs
3923  * total-slabs
3924  * num-pages-per-slab
3925  * + further values on SMP and with statistics enabled
3926  */
3927
3928 struct seq_operations slabinfo_op = {
3929         .start = s_start,
3930         .next = s_next,
3931         .stop = s_stop,
3932         .show = s_show,
3933 };
3934
3935 #define MAX_SLABINFO_WRITE 128
3936 /**
3937  * slabinfo_write - Tuning for the slab allocator
3938  * @file: unused
3939  * @buffer: user buffer
3940  * @count: data length
3941  * @ppos: unused
3942  */
3943 ssize_t slabinfo_write(struct file *file, const char __user * buffer,
3944                        size_t count, loff_t *ppos)
3945 {
3946         char kbuf[MAX_SLABINFO_WRITE + 1], *tmp;
3947         int limit, batchcount, shared, res;
3948         struct list_head *p;
3949
3950         if (count > MAX_SLABINFO_WRITE)
3951                 return -EINVAL;
3952         if (copy_from_user(&kbuf, buffer, count))
3953                 return -EFAULT;
3954         kbuf[MAX_SLABINFO_WRITE] = '\0';
3955
3956         tmp = strchr(kbuf, ' ');
3957         if (!tmp)
3958                 return -EINVAL;
3959         *tmp = '\0';
3960         tmp++;
3961         if (sscanf(tmp, " %d %d %d", &limit, &batchcount, &shared) != 3)
3962                 return -EINVAL;
3963
3964         /* Find the cache in the chain of caches. */
3965         mutex_lock(&cache_chain_mutex);
3966         res = -EINVAL;
3967         list_for_each(p, &cache_chain) {
3968                 struct kmem_cache *cachep;
3969
3970                 cachep = list_entry(p, struct kmem_cache, next);
3971                 if (!strcmp(cachep->name, kbuf)) {
3972                         if (limit < 1 || batchcount < 1 ||
3973                                         batchcount > limit || shared < 0) {
3974                                 res = 0;
3975                         } else {
3976                                 res = do_tune_cpucache(cachep, limit,
3977                                                        batchcount, shared);
3978                         }
3979                         break;
3980                 }
3981         }
3982         mutex_unlock(&cache_chain_mutex);
3983         if (res >= 0)
3984                 res = count;
3985         return res;
3986 }
3987
3988 #ifdef CONFIG_DEBUG_SLAB_LEAK
3989
3990 static void *leaks_start(struct seq_file *m, loff_t *pos)
3991 {
3992         loff_t n = *pos;
3993         struct list_head *p;
3994
3995         mutex_lock(&cache_chain_mutex);
3996         p = cache_chain.next;
3997         while (n--) {
3998                 p = p->next;
3999                 if (p == &cache_chain)
4000                         return NULL;
4001         }
4002         return list_entry(p, struct kmem_cache, next);
4003 }
4004
4005 static inline int add_caller(unsigned long *n, unsigned long v)
4006 {
4007         unsigned long *p;
4008         int l;
4009         if (!v)
4010                 return 1;
4011         l = n[1];
4012         p = n + 2;
4013         while (l) {
4014                 int i = l/2;
4015                 unsigned long *q = p + 2 * i;
4016                 if (*q == v) {
4017                         q[1]++;
4018                         return 1;
4019                 }
4020                 if (*q > v) {
4021                         l = i;
4022                 } else {
4023                         p = q + 2;
4024                         l -= i + 1;
4025                 }
4026         }
4027         if (++n[1] == n[0])
4028                 return 0;
4029         memmove(p + 2, p, n[1] * 2 * sizeof(unsigned long) - ((void *)p - (void *)n));
4030         p[0] = v;
4031         p[1] = 1;
4032         return 1;
4033 }
4034
4035 static void handle_slab(unsigned long *n, struct kmem_cache *c, struct slab *s)
4036 {
4037         void *p;
4038         int i;
4039         if (n[0] == n[1])
4040                 return;
4041         for (i = 0, p = s->s_mem; i < c->num; i++, p += c->buffer_size) {
4042                 if (slab_bufctl(s)[i] != BUFCTL_ACTIVE)
4043                         continue;
4044                 if (!add_caller(n, (unsigned long)*dbg_userword(c, p)))
4045                         return;
4046         }
4047 }
4048
4049 static void show_symbol(struct seq_file *m, unsigned long address)
4050 {
4051 #ifdef CONFIG_KALLSYMS
4052         char *modname;
4053         const char *name;
4054         unsigned long offset, size;
4055         char namebuf[KSYM_NAME_LEN+1];
4056
4057         name = kallsyms_lookup(address, &size, &offset, &modname, namebuf);
4058
4059         if (name) {
4060                 seq_printf(m, "%s+%#lx/%#lx", name, offset, size);
4061                 if (modname)
4062                         seq_printf(m, " [%s]", modname);
4063                 return;
4064         }
4065 #endif
4066         seq_printf(m, "%p", (void *)address);
4067 }
4068
4069 static int leaks_show(struct seq_file *m, void *p)
4070 {
4071         struct kmem_cache *cachep = p;
4072         struct list_head *q;
4073         struct slab *slabp;
4074         struct kmem_list3 *l3;
4075         const char *name;
4076         unsigned long *n = m->private;
4077         int node;
4078         int i;
4079
4080         if (!(cachep->flags & SLAB_STORE_USER))
4081                 return 0;
4082         if (!(cachep->flags & SLAB_RED_ZONE))
4083                 return 0;
4084
4085         /* OK, we can do it */
4086
4087         n[1] = 0;
4088
4089         for_each_online_node(node) {
4090                 l3 = cachep->nodelists[node];
4091                 if (!l3)
4092                         continue;
4093
4094                 check_irq_on();
4095                 spin_lock_irq(&l3->list_lock);
4096
4097                 list_for_each(q, &l3->slabs_full) {
4098                         slabp = list_entry(q, struct slab, list);
4099                         handle_slab(n, cachep, slabp);
4100                 }
4101                 list_for_each(q, &l3->slabs_partial) {
4102                         slabp = list_entry(q, struct slab, list);
4103                         handle_slab(n, cachep, slabp);
4104                 }
4105                 spin_unlock_irq(&l3->list_lock);
4106         }
4107         name = cachep->name;
4108         if (n[0] == n[1]) {
4109                 /* Increase the buffer size */
4110                 mutex_unlock(&cache_chain_mutex);
4111                 m->private = kzalloc(n[0] * 4 * sizeof(unsigned long), GFP_KERNEL);
4112                 if (!m->private) {
4113                         /* Too bad, we are really out */
4114                         m->private = n;
4115                         mutex_lock(&cache_chain_mutex);
4116                         return -ENOMEM;
4117                 }
4118                 *(unsigned long *)m->private = n[0] * 2;
4119                 kfree(n);
4120                 mutex_lock(&cache_chain_mutex);
4121                 /* Now make sure this entry will be retried */
4122                 m->count = m->size;
4123                 return 0;
4124         }
4125         for (i = 0; i < n[1]; i++) {
4126                 seq_printf(m, "%s: %lu ", name, n[2*i+3]);
4127                 show_symbol(m, n[2*i+2]);
4128                 seq_putc(m, '\n');
4129         }
4130         return 0;
4131 }
4132
4133 struct seq_operations slabstats_op = {
4134         .start = leaks_start,
4135         .next = s_next,
4136         .stop = s_stop,
4137         .show = leaks_show,
4138 };
4139 #endif
4140 #endif
4141
4142 /**
4143  * ksize - get the actual amount of memory allocated for a given object
4144  * @objp: Pointer to the object
4145  *
4146  * kmalloc may internally round up allocations and return more memory
4147  * than requested. ksize() can be used to determine the actual amount of
4148  * memory allocated. The caller may use this additional memory, even though
4149  * a smaller amount of memory was initially specified with the kmalloc call.
4150  * The caller must guarantee that objp points to a valid object previously
4151  * allocated with either kmalloc() or kmem_cache_alloc(). The object
4152  * must not be freed during the duration of the call.
4153  */
4154 unsigned int ksize(const void *objp)
4155 {
4156         if (unlikely(objp == NULL))
4157                 return 0;
4158
4159         return obj_size(virt_to_cache(objp));
4160 }