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