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