Kernel

Kernel Git Source Tree

Root/mm/slab.c

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

Download this file

Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.2
jz-3.3
jz-3.4
jz47xx
jz47xx-2.6.38
master
xiangfu/openwrt/v3.0.0
xiangfu/openwrt/v3.2.1

Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7

Kernel

Kernel Git Source Tree

Root/mm/slab.c

interactive