xref: /linux/mm/zsmalloc.c (revision 42b16d3ac371a2fac9b6f08fd75f23f34ba3955a)
1 /*
2  * zsmalloc memory allocator
3  *
4  * Copyright (C) 2011  Nitin Gupta
5  * Copyright (C) 2012, 2013 Minchan Kim
6  *
7  * This code is released using a dual license strategy: BSD/GPL
8  * You can choose the license that better fits your requirements.
9  *
10  * Released under the terms of 3-clause BSD License
11  * Released under the terms of GNU General Public License Version 2.0
12  */
13 
14 /*
15  * Following is how we use various fields and flags of underlying
16  * struct page(s) to form a zspage.
17  *
18  * Usage of struct page fields:
19  *	page->private: points to zspage
20  *	page->index: links together all component pages of a zspage
21  *		For the huge page, this is always 0, so we use this field
22  *		to store handle.
23  *	page->page_type: PGTY_zsmalloc, lower 24 bits locate the first object
24  *		offset in a subpage of a zspage
25  *
26  * Usage of struct page flags:
27  *	PG_private: identifies the first component page
28  *	PG_owner_priv_1: identifies the huge component page
29  *
30  */
31 
32 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
33 
34 /*
35  * lock ordering:
36  *	page_lock
37  *	pool->migrate_lock
38  *	class->lock
39  *	zspage->lock
40  */
41 
42 #include <linux/module.h>
43 #include <linux/kernel.h>
44 #include <linux/sched.h>
45 #include <linux/bitops.h>
46 #include <linux/errno.h>
47 #include <linux/highmem.h>
48 #include <linux/string.h>
49 #include <linux/slab.h>
50 #include <linux/pgtable.h>
51 #include <asm/tlbflush.h>
52 #include <linux/cpumask.h>
53 #include <linux/cpu.h>
54 #include <linux/vmalloc.h>
55 #include <linux/preempt.h>
56 #include <linux/spinlock.h>
57 #include <linux/sprintf.h>
58 #include <linux/shrinker.h>
59 #include <linux/types.h>
60 #include <linux/debugfs.h>
61 #include <linux/zsmalloc.h>
62 #include <linux/zpool.h>
63 #include <linux/migrate.h>
64 #include <linux/wait.h>
65 #include <linux/pagemap.h>
66 #include <linux/fs.h>
67 #include <linux/local_lock.h>
68 
69 #define ZSPAGE_MAGIC	0x58
70 
71 /*
72  * This must be power of 2 and greater than or equal to sizeof(link_free).
73  * These two conditions ensure that any 'struct link_free' itself doesn't
74  * span more than 1 page which avoids complex case of mapping 2 pages simply
75  * to restore link_free pointer values.
76  */
77 #define ZS_ALIGN		8
78 
79 #define ZS_HANDLE_SIZE (sizeof(unsigned long))
80 
81 /*
82  * Object location (<PFN>, <obj_idx>) is encoded as
83  * a single (unsigned long) handle value.
84  *
85  * Note that object index <obj_idx> starts from 0.
86  *
87  * This is made more complicated by various memory models and PAE.
88  */
89 
90 #ifndef MAX_POSSIBLE_PHYSMEM_BITS
91 #ifdef MAX_PHYSMEM_BITS
92 #define MAX_POSSIBLE_PHYSMEM_BITS MAX_PHYSMEM_BITS
93 #else
94 /*
95  * If this definition of MAX_PHYSMEM_BITS is used, OBJ_INDEX_BITS will just
96  * be PAGE_SHIFT
97  */
98 #define MAX_POSSIBLE_PHYSMEM_BITS BITS_PER_LONG
99 #endif
100 #endif
101 
102 #define _PFN_BITS		(MAX_POSSIBLE_PHYSMEM_BITS - PAGE_SHIFT)
103 
104 /*
105  * Head in allocated object should have OBJ_ALLOCATED_TAG
106  * to identify the object was allocated or not.
107  * It's okay to add the status bit in the least bit because
108  * header keeps handle which is 4byte-aligned address so we
109  * have room for two bit at least.
110  */
111 #define OBJ_ALLOCATED_TAG 1
112 
113 #define OBJ_TAG_BITS	1
114 #define OBJ_TAG_MASK	OBJ_ALLOCATED_TAG
115 
116 #define OBJ_INDEX_BITS	(BITS_PER_LONG - _PFN_BITS)
117 #define OBJ_INDEX_MASK	((_AC(1, UL) << OBJ_INDEX_BITS) - 1)
118 
119 #define HUGE_BITS	1
120 #define FULLNESS_BITS	4
121 #define CLASS_BITS	8
122 #define MAGIC_VAL_BITS	8
123 
124 #define ZS_MAX_PAGES_PER_ZSPAGE	(_AC(CONFIG_ZSMALLOC_CHAIN_SIZE, UL))
125 
126 /* ZS_MIN_ALLOC_SIZE must be multiple of ZS_ALIGN */
127 #define ZS_MIN_ALLOC_SIZE \
128 	MAX(32, (ZS_MAX_PAGES_PER_ZSPAGE << PAGE_SHIFT >> OBJ_INDEX_BITS))
129 /* each chunk includes extra space to keep handle */
130 #define ZS_MAX_ALLOC_SIZE	PAGE_SIZE
131 
132 /*
133  * On systems with 4K page size, this gives 255 size classes! There is a
134  * trader-off here:
135  *  - Large number of size classes is potentially wasteful as free page are
136  *    spread across these classes
137  *  - Small number of size classes causes large internal fragmentation
138  *  - Probably its better to use specific size classes (empirically
139  *    determined). NOTE: all those class sizes must be set as multiple of
140  *    ZS_ALIGN to make sure link_free itself never has to span 2 pages.
141  *
142  *  ZS_MIN_ALLOC_SIZE and ZS_SIZE_CLASS_DELTA must be multiple of ZS_ALIGN
143  *  (reason above)
144  */
145 #define ZS_SIZE_CLASS_DELTA	(PAGE_SIZE >> CLASS_BITS)
146 #define ZS_SIZE_CLASSES	(DIV_ROUND_UP(ZS_MAX_ALLOC_SIZE - ZS_MIN_ALLOC_SIZE, \
147 				      ZS_SIZE_CLASS_DELTA) + 1)
148 
149 /*
150  * Pages are distinguished by the ratio of used memory (that is the ratio
151  * of ->inuse objects to all objects that page can store). For example,
152  * INUSE_RATIO_10 means that the ratio of used objects is > 0% and <= 10%.
153  *
154  * The number of fullness groups is not random. It allows us to keep
155  * difference between the least busy page in the group (minimum permitted
156  * number of ->inuse objects) and the most busy page (maximum permitted
157  * number of ->inuse objects) at a reasonable value.
158  */
159 enum fullness_group {
160 	ZS_INUSE_RATIO_0,
161 	ZS_INUSE_RATIO_10,
162 	/* NOTE: 8 more fullness groups here */
163 	ZS_INUSE_RATIO_99       = 10,
164 	ZS_INUSE_RATIO_100,
165 	NR_FULLNESS_GROUPS,
166 };
167 
168 enum class_stat_type {
169 	/* NOTE: stats for 12 fullness groups here: from inuse 0 to 100 */
170 	ZS_OBJS_ALLOCATED       = NR_FULLNESS_GROUPS,
171 	ZS_OBJS_INUSE,
172 	NR_CLASS_STAT_TYPES,
173 };
174 
175 struct zs_size_stat {
176 	unsigned long objs[NR_CLASS_STAT_TYPES];
177 };
178 
179 #ifdef CONFIG_ZSMALLOC_STAT
180 static struct dentry *zs_stat_root;
181 #endif
182 
183 static size_t huge_class_size;
184 
185 struct size_class {
186 	spinlock_t lock;
187 	struct list_head fullness_list[NR_FULLNESS_GROUPS];
188 	/*
189 	 * Size of objects stored in this class. Must be multiple
190 	 * of ZS_ALIGN.
191 	 */
192 	int size;
193 	int objs_per_zspage;
194 	/* Number of PAGE_SIZE sized pages to combine to form a 'zspage' */
195 	int pages_per_zspage;
196 
197 	unsigned int index;
198 	struct zs_size_stat stats;
199 };
200 
201 /*
202  * Placed within free objects to form a singly linked list.
203  * For every zspage, zspage->freeobj gives head of this list.
204  *
205  * This must be power of 2 and less than or equal to ZS_ALIGN
206  */
207 struct link_free {
208 	union {
209 		/*
210 		 * Free object index;
211 		 * It's valid for non-allocated object
212 		 */
213 		unsigned long next;
214 		/*
215 		 * Handle of allocated object.
216 		 */
217 		unsigned long handle;
218 	};
219 };
220 
221 struct zs_pool {
222 	const char *name;
223 
224 	struct size_class *size_class[ZS_SIZE_CLASSES];
225 	struct kmem_cache *handle_cachep;
226 	struct kmem_cache *zspage_cachep;
227 
228 	atomic_long_t pages_allocated;
229 
230 	struct zs_pool_stats stats;
231 
232 	/* Compact classes */
233 	struct shrinker *shrinker;
234 
235 #ifdef CONFIG_ZSMALLOC_STAT
236 	struct dentry *stat_dentry;
237 #endif
238 #ifdef CONFIG_COMPACTION
239 	struct work_struct free_work;
240 #endif
241 	/* protect page/zspage migration */
242 	rwlock_t migrate_lock;
243 	atomic_t compaction_in_progress;
244 };
245 
246 struct zspage {
247 	struct {
248 		unsigned int huge:HUGE_BITS;
249 		unsigned int fullness:FULLNESS_BITS;
250 		unsigned int class:CLASS_BITS + 1;
251 		unsigned int magic:MAGIC_VAL_BITS;
252 	};
253 	unsigned int inuse;
254 	unsigned int freeobj;
255 	struct page *first_page;
256 	struct list_head list; /* fullness list */
257 	struct zs_pool *pool;
258 	rwlock_t lock;
259 };
260 
261 struct mapping_area {
262 	local_lock_t lock;
263 	char *vm_buf; /* copy buffer for objects that span pages */
264 	char *vm_addr; /* address of kmap_atomic()'ed pages */
265 	enum zs_mapmode vm_mm; /* mapping mode */
266 };
267 
268 /* huge object: pages_per_zspage == 1 && maxobj_per_zspage == 1 */
SetZsHugePage(struct zspage * zspage)269 static void SetZsHugePage(struct zspage *zspage)
270 {
271 	zspage->huge = 1;
272 }
273 
ZsHugePage(struct zspage * zspage)274 static bool ZsHugePage(struct zspage *zspage)
275 {
276 	return zspage->huge;
277 }
278 
279 static void migrate_lock_init(struct zspage *zspage);
280 static void migrate_read_lock(struct zspage *zspage);
281 static void migrate_read_unlock(struct zspage *zspage);
282 static void migrate_write_lock(struct zspage *zspage);
283 static void migrate_write_unlock(struct zspage *zspage);
284 
285 #ifdef CONFIG_COMPACTION
286 static void kick_deferred_free(struct zs_pool *pool);
287 static void init_deferred_free(struct zs_pool *pool);
288 static void SetZsPageMovable(struct zs_pool *pool, struct zspage *zspage);
289 #else
kick_deferred_free(struct zs_pool * pool)290 static void kick_deferred_free(struct zs_pool *pool) {}
init_deferred_free(struct zs_pool * pool)291 static void init_deferred_free(struct zs_pool *pool) {}
SetZsPageMovable(struct zs_pool * pool,struct zspage * zspage)292 static void SetZsPageMovable(struct zs_pool *pool, struct zspage *zspage) {}
293 #endif
294 
create_cache(struct zs_pool * pool)295 static int create_cache(struct zs_pool *pool)
296 {
297 	char *name;
298 
299 	name = kasprintf(GFP_KERNEL, "zs_handle-%s", pool->name);
300 	if (!name)
301 		return -ENOMEM;
302 	pool->handle_cachep = kmem_cache_create(name, ZS_HANDLE_SIZE,
303 						0, 0, NULL);
304 	kfree(name);
305 	if (!pool->handle_cachep)
306 		return -EINVAL;
307 
308 	name = kasprintf(GFP_KERNEL, "zspage-%s", pool->name);
309 	if (!name)
310 		return -ENOMEM;
311 	pool->zspage_cachep = kmem_cache_create(name, sizeof(struct zspage),
312 						0, 0, NULL);
313 	kfree(name);
314 	if (!pool->zspage_cachep) {
315 		kmem_cache_destroy(pool->handle_cachep);
316 		pool->handle_cachep = NULL;
317 		return -EINVAL;
318 	}
319 
320 	return 0;
321 }
322 
destroy_cache(struct zs_pool * pool)323 static void destroy_cache(struct zs_pool *pool)
324 {
325 	kmem_cache_destroy(pool->handle_cachep);
326 	kmem_cache_destroy(pool->zspage_cachep);
327 }
328 
cache_alloc_handle(struct zs_pool * pool,gfp_t gfp)329 static unsigned long cache_alloc_handle(struct zs_pool *pool, gfp_t gfp)
330 {
331 	return (unsigned long)kmem_cache_alloc(pool->handle_cachep,
332 			gfp & ~(__GFP_HIGHMEM|__GFP_MOVABLE));
333 }
334 
cache_free_handle(struct zs_pool * pool,unsigned long handle)335 static void cache_free_handle(struct zs_pool *pool, unsigned long handle)
336 {
337 	kmem_cache_free(pool->handle_cachep, (void *)handle);
338 }
339 
cache_alloc_zspage(struct zs_pool * pool,gfp_t flags)340 static struct zspage *cache_alloc_zspage(struct zs_pool *pool, gfp_t flags)
341 {
342 	return kmem_cache_zalloc(pool->zspage_cachep,
343 			flags & ~(__GFP_HIGHMEM|__GFP_MOVABLE));
344 }
345 
cache_free_zspage(struct zs_pool * pool,struct zspage * zspage)346 static void cache_free_zspage(struct zs_pool *pool, struct zspage *zspage)
347 {
348 	kmem_cache_free(pool->zspage_cachep, zspage);
349 }
350 
351 /* class->lock(which owns the handle) synchronizes races */
record_obj(unsigned long handle,unsigned long obj)352 static void record_obj(unsigned long handle, unsigned long obj)
353 {
354 	*(unsigned long *)handle = obj;
355 }
356 
357 /* zpool driver */
358 
359 #ifdef CONFIG_ZPOOL
360 
zs_zpool_create(const char * name,gfp_t gfp)361 static void *zs_zpool_create(const char *name, gfp_t gfp)
362 {
363 	/*
364 	 * Ignore global gfp flags: zs_malloc() may be invoked from
365 	 * different contexts and its caller must provide a valid
366 	 * gfp mask.
367 	 */
368 	return zs_create_pool(name);
369 }
370 
zs_zpool_destroy(void * pool)371 static void zs_zpool_destroy(void *pool)
372 {
373 	zs_destroy_pool(pool);
374 }
375 
zs_zpool_malloc(void * pool,size_t size,gfp_t gfp,unsigned long * handle)376 static int zs_zpool_malloc(void *pool, size_t size, gfp_t gfp,
377 			unsigned long *handle)
378 {
379 	*handle = zs_malloc(pool, size, gfp);
380 
381 	if (IS_ERR_VALUE(*handle))
382 		return PTR_ERR((void *)*handle);
383 	return 0;
384 }
zs_zpool_free(void * pool,unsigned long handle)385 static void zs_zpool_free(void *pool, unsigned long handle)
386 {
387 	zs_free(pool, handle);
388 }
389 
zs_zpool_map(void * pool,unsigned long handle,enum zpool_mapmode mm)390 static void *zs_zpool_map(void *pool, unsigned long handle,
391 			enum zpool_mapmode mm)
392 {
393 	enum zs_mapmode zs_mm;
394 
395 	switch (mm) {
396 	case ZPOOL_MM_RO:
397 		zs_mm = ZS_MM_RO;
398 		break;
399 	case ZPOOL_MM_WO:
400 		zs_mm = ZS_MM_WO;
401 		break;
402 	case ZPOOL_MM_RW:
403 	default:
404 		zs_mm = ZS_MM_RW;
405 		break;
406 	}
407 
408 	return zs_map_object(pool, handle, zs_mm);
409 }
zs_zpool_unmap(void * pool,unsigned long handle)410 static void zs_zpool_unmap(void *pool, unsigned long handle)
411 {
412 	zs_unmap_object(pool, handle);
413 }
414 
zs_zpool_total_pages(void * pool)415 static u64 zs_zpool_total_pages(void *pool)
416 {
417 	return zs_get_total_pages(pool);
418 }
419 
420 static struct zpool_driver zs_zpool_driver = {
421 	.type =			  "zsmalloc",
422 	.owner =		  THIS_MODULE,
423 	.create =		  zs_zpool_create,
424 	.destroy =		  zs_zpool_destroy,
425 	.malloc_support_movable = true,
426 	.malloc =		  zs_zpool_malloc,
427 	.free =			  zs_zpool_free,
428 	.map =			  zs_zpool_map,
429 	.unmap =		  zs_zpool_unmap,
430 	.total_pages =		  zs_zpool_total_pages,
431 };
432 
433 MODULE_ALIAS("zpool-zsmalloc");
434 #endif /* CONFIG_ZPOOL */
435 
436 /* per-cpu VM mapping areas for zspage accesses that cross page boundaries */
437 static DEFINE_PER_CPU(struct mapping_area, zs_map_area) = {
438 	.lock	= INIT_LOCAL_LOCK(lock),
439 };
440 
is_first_page(struct page * page)441 static __maybe_unused int is_first_page(struct page *page)
442 {
443 	return PagePrivate(page);
444 }
445 
446 /* Protected by class->lock */
get_zspage_inuse(struct zspage * zspage)447 static inline int get_zspage_inuse(struct zspage *zspage)
448 {
449 	return zspage->inuse;
450 }
451 
452 
mod_zspage_inuse(struct zspage * zspage,int val)453 static inline void mod_zspage_inuse(struct zspage *zspage, int val)
454 {
455 	zspage->inuse += val;
456 }
457 
get_first_page(struct zspage * zspage)458 static inline struct page *get_first_page(struct zspage *zspage)
459 {
460 	struct page *first_page = zspage->first_page;
461 
462 	VM_BUG_ON_PAGE(!is_first_page(first_page), first_page);
463 	return first_page;
464 }
465 
466 #define FIRST_OBJ_PAGE_TYPE_MASK	0xffffff
467 
get_first_obj_offset(struct page * page)468 static inline unsigned int get_first_obj_offset(struct page *page)
469 {
470 	VM_WARN_ON_ONCE(!PageZsmalloc(page));
471 	return page->page_type & FIRST_OBJ_PAGE_TYPE_MASK;
472 }
473 
set_first_obj_offset(struct page * page,unsigned int offset)474 static inline void set_first_obj_offset(struct page *page, unsigned int offset)
475 {
476 	/* With 24 bits available, we can support offsets into 16 MiB pages. */
477 	BUILD_BUG_ON(PAGE_SIZE > SZ_16M);
478 	VM_WARN_ON_ONCE(!PageZsmalloc(page));
479 	VM_WARN_ON_ONCE(offset & ~FIRST_OBJ_PAGE_TYPE_MASK);
480 	page->page_type &= ~FIRST_OBJ_PAGE_TYPE_MASK;
481 	page->page_type |= offset & FIRST_OBJ_PAGE_TYPE_MASK;
482 }
483 
get_freeobj(struct zspage * zspage)484 static inline unsigned int get_freeobj(struct zspage *zspage)
485 {
486 	return zspage->freeobj;
487 }
488 
set_freeobj(struct zspage * zspage,unsigned int obj)489 static inline void set_freeobj(struct zspage *zspage, unsigned int obj)
490 {
491 	zspage->freeobj = obj;
492 }
493 
zspage_class(struct zs_pool * pool,struct zspage * zspage)494 static struct size_class *zspage_class(struct zs_pool *pool,
495 				       struct zspage *zspage)
496 {
497 	return pool->size_class[zspage->class];
498 }
499 
500 /*
501  * zsmalloc divides the pool into various size classes where each
502  * class maintains a list of zspages where each zspage is divided
503  * into equal sized chunks. Each allocation falls into one of these
504  * classes depending on its size. This function returns index of the
505  * size class which has chunk size big enough to hold the given size.
506  */
get_size_class_index(int size)507 static int get_size_class_index(int size)
508 {
509 	int idx = 0;
510 
511 	if (likely(size > ZS_MIN_ALLOC_SIZE))
512 		idx = DIV_ROUND_UP(size - ZS_MIN_ALLOC_SIZE,
513 				ZS_SIZE_CLASS_DELTA);
514 
515 	return min_t(int, ZS_SIZE_CLASSES - 1, idx);
516 }
517 
class_stat_add(struct size_class * class,int type,unsigned long cnt)518 static inline void class_stat_add(struct size_class *class, int type,
519 				  unsigned long cnt)
520 {
521 	class->stats.objs[type] += cnt;
522 }
523 
class_stat_sub(struct size_class * class,int type,unsigned long cnt)524 static inline void class_stat_sub(struct size_class *class, int type,
525 				  unsigned long cnt)
526 {
527 	class->stats.objs[type] -= cnt;
528 }
529 
class_stat_read(struct size_class * class,int type)530 static inline unsigned long class_stat_read(struct size_class *class, int type)
531 {
532 	return class->stats.objs[type];
533 }
534 
535 #ifdef CONFIG_ZSMALLOC_STAT
536 
zs_stat_init(void)537 static void __init zs_stat_init(void)
538 {
539 	if (!debugfs_initialized()) {
540 		pr_warn("debugfs not available, stat dir not created\n");
541 		return;
542 	}
543 
544 	zs_stat_root = debugfs_create_dir("zsmalloc", NULL);
545 }
546 
zs_stat_exit(void)547 static void __exit zs_stat_exit(void)
548 {
549 	debugfs_remove_recursive(zs_stat_root);
550 }
551 
552 static unsigned long zs_can_compact(struct size_class *class);
553 
zs_stats_size_show(struct seq_file * s,void * v)554 static int zs_stats_size_show(struct seq_file *s, void *v)
555 {
556 	int i, fg;
557 	struct zs_pool *pool = s->private;
558 	struct size_class *class;
559 	int objs_per_zspage;
560 	unsigned long obj_allocated, obj_used, pages_used, freeable;
561 	unsigned long total_objs = 0, total_used_objs = 0, total_pages = 0;
562 	unsigned long total_freeable = 0;
563 	unsigned long inuse_totals[NR_FULLNESS_GROUPS] = {0, };
564 
565 	seq_printf(s, " %5s %5s %9s %9s %9s %9s %9s %9s %9s %9s %9s %9s %9s %13s %10s %10s %16s %8s\n",
566 			"class", "size", "10%", "20%", "30%", "40%",
567 			"50%", "60%", "70%", "80%", "90%", "99%", "100%",
568 			"obj_allocated", "obj_used", "pages_used",
569 			"pages_per_zspage", "freeable");
570 
571 	for (i = 0; i < ZS_SIZE_CLASSES; i++) {
572 
573 		class = pool->size_class[i];
574 
575 		if (class->index != i)
576 			continue;
577 
578 		spin_lock(&class->lock);
579 
580 		seq_printf(s, " %5u %5u ", i, class->size);
581 		for (fg = ZS_INUSE_RATIO_10; fg < NR_FULLNESS_GROUPS; fg++) {
582 			inuse_totals[fg] += class_stat_read(class, fg);
583 			seq_printf(s, "%9lu ", class_stat_read(class, fg));
584 		}
585 
586 		obj_allocated = class_stat_read(class, ZS_OBJS_ALLOCATED);
587 		obj_used = class_stat_read(class, ZS_OBJS_INUSE);
588 		freeable = zs_can_compact(class);
589 		spin_unlock(&class->lock);
590 
591 		objs_per_zspage = class->objs_per_zspage;
592 		pages_used = obj_allocated / objs_per_zspage *
593 				class->pages_per_zspage;
594 
595 		seq_printf(s, "%13lu %10lu %10lu %16d %8lu\n",
596 			   obj_allocated, obj_used, pages_used,
597 			   class->pages_per_zspage, freeable);
598 
599 		total_objs += obj_allocated;
600 		total_used_objs += obj_used;
601 		total_pages += pages_used;
602 		total_freeable += freeable;
603 	}
604 
605 	seq_puts(s, "\n");
606 	seq_printf(s, " %5s %5s ", "Total", "");
607 
608 	for (fg = ZS_INUSE_RATIO_10; fg < NR_FULLNESS_GROUPS; fg++)
609 		seq_printf(s, "%9lu ", inuse_totals[fg]);
610 
611 	seq_printf(s, "%13lu %10lu %10lu %16s %8lu\n",
612 		   total_objs, total_used_objs, total_pages, "",
613 		   total_freeable);
614 
615 	return 0;
616 }
617 DEFINE_SHOW_ATTRIBUTE(zs_stats_size);
618 
zs_pool_stat_create(struct zs_pool * pool,const char * name)619 static void zs_pool_stat_create(struct zs_pool *pool, const char *name)
620 {
621 	if (!zs_stat_root) {
622 		pr_warn("no root stat dir, not creating <%s> stat dir\n", name);
623 		return;
624 	}
625 
626 	pool->stat_dentry = debugfs_create_dir(name, zs_stat_root);
627 
628 	debugfs_create_file("classes", S_IFREG | 0444, pool->stat_dentry, pool,
629 			    &zs_stats_size_fops);
630 }
631 
zs_pool_stat_destroy(struct zs_pool * pool)632 static void zs_pool_stat_destroy(struct zs_pool *pool)
633 {
634 	debugfs_remove_recursive(pool->stat_dentry);
635 }
636 
637 #else /* CONFIG_ZSMALLOC_STAT */
zs_stat_init(void)638 static void __init zs_stat_init(void)
639 {
640 }
641 
zs_stat_exit(void)642 static void __exit zs_stat_exit(void)
643 {
644 }
645 
zs_pool_stat_create(struct zs_pool * pool,const char * name)646 static inline void zs_pool_stat_create(struct zs_pool *pool, const char *name)
647 {
648 }
649 
zs_pool_stat_destroy(struct zs_pool * pool)650 static inline void zs_pool_stat_destroy(struct zs_pool *pool)
651 {
652 }
653 #endif
654 
655 
656 /*
657  * For each size class, zspages are divided into different groups
658  * depending on their usage ratio. This function returns fullness
659  * status of the given page.
660  */
get_fullness_group(struct size_class * class,struct zspage * zspage)661 static int get_fullness_group(struct size_class *class, struct zspage *zspage)
662 {
663 	int inuse, objs_per_zspage, ratio;
664 
665 	inuse = get_zspage_inuse(zspage);
666 	objs_per_zspage = class->objs_per_zspage;
667 
668 	if (inuse == 0)
669 		return ZS_INUSE_RATIO_0;
670 	if (inuse == objs_per_zspage)
671 		return ZS_INUSE_RATIO_100;
672 
673 	ratio = 100 * inuse / objs_per_zspage;
674 	/*
675 	 * Take integer division into consideration: a page with one inuse
676 	 * object out of 127 possible, will end up having 0 usage ratio,
677 	 * which is wrong as it belongs in ZS_INUSE_RATIO_10 fullness group.
678 	 */
679 	return ratio / 10 + 1;
680 }
681 
682 /*
683  * Each size class maintains various freelists and zspages are assigned
684  * to one of these freelists based on the number of live objects they
685  * have. This functions inserts the given zspage into the freelist
686  * identified by <class, fullness_group>.
687  */
insert_zspage(struct size_class * class,struct zspage * zspage,int fullness)688 static void insert_zspage(struct size_class *class,
689 				struct zspage *zspage,
690 				int fullness)
691 {
692 	class_stat_add(class, fullness, 1);
693 	list_add(&zspage->list, &class->fullness_list[fullness]);
694 	zspage->fullness = fullness;
695 }
696 
697 /*
698  * This function removes the given zspage from the freelist identified
699  * by <class, fullness_group>.
700  */
remove_zspage(struct size_class * class,struct zspage * zspage)701 static void remove_zspage(struct size_class *class, struct zspage *zspage)
702 {
703 	int fullness = zspage->fullness;
704 
705 	VM_BUG_ON(list_empty(&class->fullness_list[fullness]));
706 
707 	list_del_init(&zspage->list);
708 	class_stat_sub(class, fullness, 1);
709 }
710 
711 /*
712  * Each size class maintains zspages in different fullness groups depending
713  * on the number of live objects they contain. When allocating or freeing
714  * objects, the fullness status of the page can change, for instance, from
715  * INUSE_RATIO_80 to INUSE_RATIO_70 when freeing an object. This function
716  * checks if such a status change has occurred for the given page and
717  * accordingly moves the page from the list of the old fullness group to that
718  * of the new fullness group.
719  */
fix_fullness_group(struct size_class * class,struct zspage * zspage)720 static int fix_fullness_group(struct size_class *class, struct zspage *zspage)
721 {
722 	int newfg;
723 
724 	newfg = get_fullness_group(class, zspage);
725 	if (newfg == zspage->fullness)
726 		goto out;
727 
728 	remove_zspage(class, zspage);
729 	insert_zspage(class, zspage, newfg);
730 out:
731 	return newfg;
732 }
733 
get_zspage(struct page * page)734 static struct zspage *get_zspage(struct page *page)
735 {
736 	struct zspage *zspage = (struct zspage *)page_private(page);
737 
738 	BUG_ON(zspage->magic != ZSPAGE_MAGIC);
739 	return zspage;
740 }
741 
get_next_page(struct page * page)742 static struct page *get_next_page(struct page *page)
743 {
744 	struct zspage *zspage = get_zspage(page);
745 
746 	if (unlikely(ZsHugePage(zspage)))
747 		return NULL;
748 
749 	return (struct page *)page->index;
750 }
751 
752 /**
753  * obj_to_location - get (<page>, <obj_idx>) from encoded object value
754  * @obj: the encoded object value
755  * @page: page object resides in zspage
756  * @obj_idx: object index
757  */
obj_to_location(unsigned long obj,struct page ** page,unsigned int * obj_idx)758 static void obj_to_location(unsigned long obj, struct page **page,
759 				unsigned int *obj_idx)
760 {
761 	*page = pfn_to_page(obj >> OBJ_INDEX_BITS);
762 	*obj_idx = (obj & OBJ_INDEX_MASK);
763 }
764 
obj_to_page(unsigned long obj,struct page ** page)765 static void obj_to_page(unsigned long obj, struct page **page)
766 {
767 	*page = pfn_to_page(obj >> OBJ_INDEX_BITS);
768 }
769 
770 /**
771  * location_to_obj - get obj value encoded from (<page>, <obj_idx>)
772  * @page: page object resides in zspage
773  * @obj_idx: object index
774  */
location_to_obj(struct page * page,unsigned int obj_idx)775 static unsigned long location_to_obj(struct page *page, unsigned int obj_idx)
776 {
777 	unsigned long obj;
778 
779 	obj = page_to_pfn(page) << OBJ_INDEX_BITS;
780 	obj |= obj_idx & OBJ_INDEX_MASK;
781 
782 	return obj;
783 }
784 
handle_to_obj(unsigned long handle)785 static unsigned long handle_to_obj(unsigned long handle)
786 {
787 	return *(unsigned long *)handle;
788 }
789 
obj_allocated(struct page * page,void * obj,unsigned long * phandle)790 static inline bool obj_allocated(struct page *page, void *obj,
791 				 unsigned long *phandle)
792 {
793 	unsigned long handle;
794 	struct zspage *zspage = get_zspage(page);
795 
796 	if (unlikely(ZsHugePage(zspage))) {
797 		VM_BUG_ON_PAGE(!is_first_page(page), page);
798 		handle = page->index;
799 	} else
800 		handle = *(unsigned long *)obj;
801 
802 	if (!(handle & OBJ_ALLOCATED_TAG))
803 		return false;
804 
805 	/* Clear all tags before returning the handle */
806 	*phandle = handle & ~OBJ_TAG_MASK;
807 	return true;
808 }
809 
reset_page(struct page * page)810 static void reset_page(struct page *page)
811 {
812 	__ClearPageMovable(page);
813 	ClearPagePrivate(page);
814 	set_page_private(page, 0);
815 	page->index = 0;
816 	__ClearPageZsmalloc(page);
817 }
818 
trylock_zspage(struct zspage * zspage)819 static int trylock_zspage(struct zspage *zspage)
820 {
821 	struct page *cursor, *fail;
822 
823 	for (cursor = get_first_page(zspage); cursor != NULL; cursor =
824 					get_next_page(cursor)) {
825 		if (!trylock_page(cursor)) {
826 			fail = cursor;
827 			goto unlock;
828 		}
829 	}
830 
831 	return 1;
832 unlock:
833 	for (cursor = get_first_page(zspage); cursor != fail; cursor =
834 					get_next_page(cursor))
835 		unlock_page(cursor);
836 
837 	return 0;
838 }
839 
__free_zspage(struct zs_pool * pool,struct size_class * class,struct zspage * zspage)840 static void __free_zspage(struct zs_pool *pool, struct size_class *class,
841 				struct zspage *zspage)
842 {
843 	struct page *page, *next;
844 
845 	assert_spin_locked(&class->lock);
846 
847 	VM_BUG_ON(get_zspage_inuse(zspage));
848 	VM_BUG_ON(zspage->fullness != ZS_INUSE_RATIO_0);
849 
850 	next = page = get_first_page(zspage);
851 	do {
852 		VM_BUG_ON_PAGE(!PageLocked(page), page);
853 		next = get_next_page(page);
854 		reset_page(page);
855 		unlock_page(page);
856 		dec_zone_page_state(page, NR_ZSPAGES);
857 		put_page(page);
858 		page = next;
859 	} while (page != NULL);
860 
861 	cache_free_zspage(pool, zspage);
862 
863 	class_stat_sub(class, ZS_OBJS_ALLOCATED, class->objs_per_zspage);
864 	atomic_long_sub(class->pages_per_zspage, &pool->pages_allocated);
865 }
866 
free_zspage(struct zs_pool * pool,struct size_class * class,struct zspage * zspage)867 static void free_zspage(struct zs_pool *pool, struct size_class *class,
868 				struct zspage *zspage)
869 {
870 	VM_BUG_ON(get_zspage_inuse(zspage));
871 	VM_BUG_ON(list_empty(&zspage->list));
872 
873 	/*
874 	 * Since zs_free couldn't be sleepable, this function cannot call
875 	 * lock_page. The page locks trylock_zspage got will be released
876 	 * by __free_zspage.
877 	 */
878 	if (!trylock_zspage(zspage)) {
879 		kick_deferred_free(pool);
880 		return;
881 	}
882 
883 	remove_zspage(class, zspage);
884 	__free_zspage(pool, class, zspage);
885 }
886 
887 /* Initialize a newly allocated zspage */
init_zspage(struct size_class * class,struct zspage * zspage)888 static void init_zspage(struct size_class *class, struct zspage *zspage)
889 {
890 	unsigned int freeobj = 1;
891 	unsigned long off = 0;
892 	struct page *page = get_first_page(zspage);
893 
894 	while (page) {
895 		struct page *next_page;
896 		struct link_free *link;
897 		void *vaddr;
898 
899 		set_first_obj_offset(page, off);
900 
901 		vaddr = kmap_atomic(page);
902 		link = (struct link_free *)vaddr + off / sizeof(*link);
903 
904 		while ((off += class->size) < PAGE_SIZE) {
905 			link->next = freeobj++ << OBJ_TAG_BITS;
906 			link += class->size / sizeof(*link);
907 		}
908 
909 		/*
910 		 * We now come to the last (full or partial) object on this
911 		 * page, which must point to the first object on the next
912 		 * page (if present)
913 		 */
914 		next_page = get_next_page(page);
915 		if (next_page) {
916 			link->next = freeobj++ << OBJ_TAG_BITS;
917 		} else {
918 			/*
919 			 * Reset OBJ_TAG_BITS bit to last link to tell
920 			 * whether it's allocated object or not.
921 			 */
922 			link->next = -1UL << OBJ_TAG_BITS;
923 		}
924 		kunmap_atomic(vaddr);
925 		page = next_page;
926 		off %= PAGE_SIZE;
927 	}
928 
929 	set_freeobj(zspage, 0);
930 }
931 
create_page_chain(struct size_class * class,struct zspage * zspage,struct page * pages[])932 static void create_page_chain(struct size_class *class, struct zspage *zspage,
933 				struct page *pages[])
934 {
935 	int i;
936 	struct page *page;
937 	struct page *prev_page = NULL;
938 	int nr_pages = class->pages_per_zspage;
939 
940 	/*
941 	 * Allocate individual pages and link them together as:
942 	 * 1. all pages are linked together using page->index
943 	 * 2. each sub-page point to zspage using page->private
944 	 *
945 	 * we set PG_private to identify the first page (i.e. no other sub-page
946 	 * has this flag set).
947 	 */
948 	for (i = 0; i < nr_pages; i++) {
949 		page = pages[i];
950 		set_page_private(page, (unsigned long)zspage);
951 		page->index = 0;
952 		if (i == 0) {
953 			zspage->first_page = page;
954 			SetPagePrivate(page);
955 			if (unlikely(class->objs_per_zspage == 1 &&
956 					class->pages_per_zspage == 1))
957 				SetZsHugePage(zspage);
958 		} else {
959 			prev_page->index = (unsigned long)page;
960 		}
961 		prev_page = page;
962 	}
963 }
964 
965 /*
966  * Allocate a zspage for the given size class
967  */
alloc_zspage(struct zs_pool * pool,struct size_class * class,gfp_t gfp)968 static struct zspage *alloc_zspage(struct zs_pool *pool,
969 					struct size_class *class,
970 					gfp_t gfp)
971 {
972 	int i;
973 	struct page *pages[ZS_MAX_PAGES_PER_ZSPAGE];
974 	struct zspage *zspage = cache_alloc_zspage(pool, gfp);
975 
976 	if (!zspage)
977 		return NULL;
978 
979 	zspage->magic = ZSPAGE_MAGIC;
980 	migrate_lock_init(zspage);
981 
982 	for (i = 0; i < class->pages_per_zspage; i++) {
983 		struct page *page;
984 
985 		page = alloc_page(gfp);
986 		if (!page) {
987 			while (--i >= 0) {
988 				dec_zone_page_state(pages[i], NR_ZSPAGES);
989 				__ClearPageZsmalloc(pages[i]);
990 				__free_page(pages[i]);
991 			}
992 			cache_free_zspage(pool, zspage);
993 			return NULL;
994 		}
995 		__SetPageZsmalloc(page);
996 
997 		inc_zone_page_state(page, NR_ZSPAGES);
998 		pages[i] = page;
999 	}
1000 
1001 	create_page_chain(class, zspage, pages);
1002 	init_zspage(class, zspage);
1003 	zspage->pool = pool;
1004 	zspage->class = class->index;
1005 
1006 	return zspage;
1007 }
1008 
find_get_zspage(struct size_class * class)1009 static struct zspage *find_get_zspage(struct size_class *class)
1010 {
1011 	int i;
1012 	struct zspage *zspage;
1013 
1014 	for (i = ZS_INUSE_RATIO_99; i >= ZS_INUSE_RATIO_0; i--) {
1015 		zspage = list_first_entry_or_null(&class->fullness_list[i],
1016 						  struct zspage, list);
1017 		if (zspage)
1018 			break;
1019 	}
1020 
1021 	return zspage;
1022 }
1023 
__zs_cpu_up(struct mapping_area * area)1024 static inline int __zs_cpu_up(struct mapping_area *area)
1025 {
1026 	/*
1027 	 * Make sure we don't leak memory if a cpu UP notification
1028 	 * and zs_init() race and both call zs_cpu_up() on the same cpu
1029 	 */
1030 	if (area->vm_buf)
1031 		return 0;
1032 	area->vm_buf = kmalloc(ZS_MAX_ALLOC_SIZE, GFP_KERNEL);
1033 	if (!area->vm_buf)
1034 		return -ENOMEM;
1035 	return 0;
1036 }
1037 
__zs_cpu_down(struct mapping_area * area)1038 static inline void __zs_cpu_down(struct mapping_area *area)
1039 {
1040 	kfree(area->vm_buf);
1041 	area->vm_buf = NULL;
1042 }
1043 
__zs_map_object(struct mapping_area * area,struct page * pages[2],int off,int size)1044 static void *__zs_map_object(struct mapping_area *area,
1045 			struct page *pages[2], int off, int size)
1046 {
1047 	int sizes[2];
1048 	void *addr;
1049 	char *buf = area->vm_buf;
1050 
1051 	/* disable page faults to match kmap_atomic() return conditions */
1052 	pagefault_disable();
1053 
1054 	/* no read fastpath */
1055 	if (area->vm_mm == ZS_MM_WO)
1056 		goto out;
1057 
1058 	sizes[0] = PAGE_SIZE - off;
1059 	sizes[1] = size - sizes[0];
1060 
1061 	/* copy object to per-cpu buffer */
1062 	addr = kmap_atomic(pages[0]);
1063 	memcpy(buf, addr + off, sizes[0]);
1064 	kunmap_atomic(addr);
1065 	addr = kmap_atomic(pages[1]);
1066 	memcpy(buf + sizes[0], addr, sizes[1]);
1067 	kunmap_atomic(addr);
1068 out:
1069 	return area->vm_buf;
1070 }
1071 
__zs_unmap_object(struct mapping_area * area,struct page * pages[2],int off,int size)1072 static void __zs_unmap_object(struct mapping_area *area,
1073 			struct page *pages[2], int off, int size)
1074 {
1075 	int sizes[2];
1076 	void *addr;
1077 	char *buf;
1078 
1079 	/* no write fastpath */
1080 	if (area->vm_mm == ZS_MM_RO)
1081 		goto out;
1082 
1083 	buf = area->vm_buf;
1084 	buf = buf + ZS_HANDLE_SIZE;
1085 	size -= ZS_HANDLE_SIZE;
1086 	off += ZS_HANDLE_SIZE;
1087 
1088 	sizes[0] = PAGE_SIZE - off;
1089 	sizes[1] = size - sizes[0];
1090 
1091 	/* copy per-cpu buffer to object */
1092 	addr = kmap_atomic(pages[0]);
1093 	memcpy(addr + off, buf, sizes[0]);
1094 	kunmap_atomic(addr);
1095 	addr = kmap_atomic(pages[1]);
1096 	memcpy(addr, buf + sizes[0], sizes[1]);
1097 	kunmap_atomic(addr);
1098 
1099 out:
1100 	/* enable page faults to match kunmap_atomic() return conditions */
1101 	pagefault_enable();
1102 }
1103 
zs_cpu_prepare(unsigned int cpu)1104 static int zs_cpu_prepare(unsigned int cpu)
1105 {
1106 	struct mapping_area *area;
1107 
1108 	area = &per_cpu(zs_map_area, cpu);
1109 	return __zs_cpu_up(area);
1110 }
1111 
zs_cpu_dead(unsigned int cpu)1112 static int zs_cpu_dead(unsigned int cpu)
1113 {
1114 	struct mapping_area *area;
1115 
1116 	area = &per_cpu(zs_map_area, cpu);
1117 	__zs_cpu_down(area);
1118 	return 0;
1119 }
1120 
can_merge(struct size_class * prev,int pages_per_zspage,int objs_per_zspage)1121 static bool can_merge(struct size_class *prev, int pages_per_zspage,
1122 					int objs_per_zspage)
1123 {
1124 	if (prev->pages_per_zspage == pages_per_zspage &&
1125 		prev->objs_per_zspage == objs_per_zspage)
1126 		return true;
1127 
1128 	return false;
1129 }
1130 
zspage_full(struct size_class * class,struct zspage * zspage)1131 static bool zspage_full(struct size_class *class, struct zspage *zspage)
1132 {
1133 	return get_zspage_inuse(zspage) == class->objs_per_zspage;
1134 }
1135 
zspage_empty(struct zspage * zspage)1136 static bool zspage_empty(struct zspage *zspage)
1137 {
1138 	return get_zspage_inuse(zspage) == 0;
1139 }
1140 
1141 /**
1142  * zs_lookup_class_index() - Returns index of the zsmalloc &size_class
1143  * that hold objects of the provided size.
1144  * @pool: zsmalloc pool to use
1145  * @size: object size
1146  *
1147  * Context: Any context.
1148  *
1149  * Return: the index of the zsmalloc &size_class that hold objects of the
1150  * provided size.
1151  */
zs_lookup_class_index(struct zs_pool * pool,unsigned int size)1152 unsigned int zs_lookup_class_index(struct zs_pool *pool, unsigned int size)
1153 {
1154 	struct size_class *class;
1155 
1156 	class = pool->size_class[get_size_class_index(size)];
1157 
1158 	return class->index;
1159 }
1160 EXPORT_SYMBOL_GPL(zs_lookup_class_index);
1161 
zs_get_total_pages(struct zs_pool * pool)1162 unsigned long zs_get_total_pages(struct zs_pool *pool)
1163 {
1164 	return atomic_long_read(&pool->pages_allocated);
1165 }
1166 EXPORT_SYMBOL_GPL(zs_get_total_pages);
1167 
1168 /**
1169  * zs_map_object - get address of allocated object from handle.
1170  * @pool: pool from which the object was allocated
1171  * @handle: handle returned from zs_malloc
1172  * @mm: mapping mode to use
1173  *
1174  * Before using an object allocated from zs_malloc, it must be mapped using
1175  * this function. When done with the object, it must be unmapped using
1176  * zs_unmap_object.
1177  *
1178  * Only one object can be mapped per cpu at a time. There is no protection
1179  * against nested mappings.
1180  *
1181  * This function returns with preemption and page faults disabled.
1182  */
zs_map_object(struct zs_pool * pool,unsigned long handle,enum zs_mapmode mm)1183 void *zs_map_object(struct zs_pool *pool, unsigned long handle,
1184 			enum zs_mapmode mm)
1185 {
1186 	struct zspage *zspage;
1187 	struct page *page;
1188 	unsigned long obj, off;
1189 	unsigned int obj_idx;
1190 
1191 	struct size_class *class;
1192 	struct mapping_area *area;
1193 	struct page *pages[2];
1194 	void *ret;
1195 
1196 	/*
1197 	 * Because we use per-cpu mapping areas shared among the
1198 	 * pools/users, we can't allow mapping in interrupt context
1199 	 * because it can corrupt another users mappings.
1200 	 */
1201 	BUG_ON(in_interrupt());
1202 
1203 	/* It guarantees it can get zspage from handle safely */
1204 	read_lock(&pool->migrate_lock);
1205 	obj = handle_to_obj(handle);
1206 	obj_to_location(obj, &page, &obj_idx);
1207 	zspage = get_zspage(page);
1208 
1209 	/*
1210 	 * migration cannot move any zpages in this zspage. Here, class->lock
1211 	 * is too heavy since callers would take some time until they calls
1212 	 * zs_unmap_object API so delegate the locking from class to zspage
1213 	 * which is smaller granularity.
1214 	 */
1215 	migrate_read_lock(zspage);
1216 	read_unlock(&pool->migrate_lock);
1217 
1218 	class = zspage_class(pool, zspage);
1219 	off = offset_in_page(class->size * obj_idx);
1220 
1221 	local_lock(&zs_map_area.lock);
1222 	area = this_cpu_ptr(&zs_map_area);
1223 	area->vm_mm = mm;
1224 	if (off + class->size <= PAGE_SIZE) {
1225 		/* this object is contained entirely within a page */
1226 		area->vm_addr = kmap_atomic(page);
1227 		ret = area->vm_addr + off;
1228 		goto out;
1229 	}
1230 
1231 	/* this object spans two pages */
1232 	pages[0] = page;
1233 	pages[1] = get_next_page(page);
1234 	BUG_ON(!pages[1]);
1235 
1236 	ret = __zs_map_object(area, pages, off, class->size);
1237 out:
1238 	if (likely(!ZsHugePage(zspage)))
1239 		ret += ZS_HANDLE_SIZE;
1240 
1241 	return ret;
1242 }
1243 EXPORT_SYMBOL_GPL(zs_map_object);
1244 
zs_unmap_object(struct zs_pool * pool,unsigned long handle)1245 void zs_unmap_object(struct zs_pool *pool, unsigned long handle)
1246 {
1247 	struct zspage *zspage;
1248 	struct page *page;
1249 	unsigned long obj, off;
1250 	unsigned int obj_idx;
1251 
1252 	struct size_class *class;
1253 	struct mapping_area *area;
1254 
1255 	obj = handle_to_obj(handle);
1256 	obj_to_location(obj, &page, &obj_idx);
1257 	zspage = get_zspage(page);
1258 	class = zspage_class(pool, zspage);
1259 	off = offset_in_page(class->size * obj_idx);
1260 
1261 	area = this_cpu_ptr(&zs_map_area);
1262 	if (off + class->size <= PAGE_SIZE)
1263 		kunmap_atomic(area->vm_addr);
1264 	else {
1265 		struct page *pages[2];
1266 
1267 		pages[0] = page;
1268 		pages[1] = get_next_page(page);
1269 		BUG_ON(!pages[1]);
1270 
1271 		__zs_unmap_object(area, pages, off, class->size);
1272 	}
1273 	local_unlock(&zs_map_area.lock);
1274 
1275 	migrate_read_unlock(zspage);
1276 }
1277 EXPORT_SYMBOL_GPL(zs_unmap_object);
1278 
1279 /**
1280  * zs_huge_class_size() - Returns the size (in bytes) of the first huge
1281  *                        zsmalloc &size_class.
1282  * @pool: zsmalloc pool to use
1283  *
1284  * The function returns the size of the first huge class - any object of equal
1285  * or bigger size will be stored in zspage consisting of a single physical
1286  * page.
1287  *
1288  * Context: Any context.
1289  *
1290  * Return: the size (in bytes) of the first huge zsmalloc &size_class.
1291  */
zs_huge_class_size(struct zs_pool * pool)1292 size_t zs_huge_class_size(struct zs_pool *pool)
1293 {
1294 	return huge_class_size;
1295 }
1296 EXPORT_SYMBOL_GPL(zs_huge_class_size);
1297 
obj_malloc(struct zs_pool * pool,struct zspage * zspage,unsigned long handle)1298 static unsigned long obj_malloc(struct zs_pool *pool,
1299 				struct zspage *zspage, unsigned long handle)
1300 {
1301 	int i, nr_page, offset;
1302 	unsigned long obj;
1303 	struct link_free *link;
1304 	struct size_class *class;
1305 
1306 	struct page *m_page;
1307 	unsigned long m_offset;
1308 	void *vaddr;
1309 
1310 	class = pool->size_class[zspage->class];
1311 	obj = get_freeobj(zspage);
1312 
1313 	offset = obj * class->size;
1314 	nr_page = offset >> PAGE_SHIFT;
1315 	m_offset = offset_in_page(offset);
1316 	m_page = get_first_page(zspage);
1317 
1318 	for (i = 0; i < nr_page; i++)
1319 		m_page = get_next_page(m_page);
1320 
1321 	vaddr = kmap_atomic(m_page);
1322 	link = (struct link_free *)vaddr + m_offset / sizeof(*link);
1323 	set_freeobj(zspage, link->next >> OBJ_TAG_BITS);
1324 	if (likely(!ZsHugePage(zspage)))
1325 		/* record handle in the header of allocated chunk */
1326 		link->handle = handle | OBJ_ALLOCATED_TAG;
1327 	else
1328 		/* record handle to page->index */
1329 		zspage->first_page->index = handle | OBJ_ALLOCATED_TAG;
1330 
1331 	kunmap_atomic(vaddr);
1332 	mod_zspage_inuse(zspage, 1);
1333 
1334 	obj = location_to_obj(m_page, obj);
1335 	record_obj(handle, obj);
1336 
1337 	return obj;
1338 }
1339 
1340 
1341 /**
1342  * zs_malloc - Allocate block of given size from pool.
1343  * @pool: pool to allocate from
1344  * @size: size of block to allocate
1345  * @gfp: gfp flags when allocating object
1346  *
1347  * On success, handle to the allocated object is returned,
1348  * otherwise an ERR_PTR().
1349  * Allocation requests with size > ZS_MAX_ALLOC_SIZE will fail.
1350  */
zs_malloc(struct zs_pool * pool,size_t size,gfp_t gfp)1351 unsigned long zs_malloc(struct zs_pool *pool, size_t size, gfp_t gfp)
1352 {
1353 	unsigned long handle;
1354 	struct size_class *class;
1355 	int newfg;
1356 	struct zspage *zspage;
1357 
1358 	if (unlikely(!size))
1359 		return (unsigned long)ERR_PTR(-EINVAL);
1360 
1361 	if (unlikely(size > ZS_MAX_ALLOC_SIZE))
1362 		return (unsigned long)ERR_PTR(-ENOSPC);
1363 
1364 	handle = cache_alloc_handle(pool, gfp);
1365 	if (!handle)
1366 		return (unsigned long)ERR_PTR(-ENOMEM);
1367 
1368 	/* extra space in chunk to keep the handle */
1369 	size += ZS_HANDLE_SIZE;
1370 	class = pool->size_class[get_size_class_index(size)];
1371 
1372 	/* class->lock effectively protects the zpage migration */
1373 	spin_lock(&class->lock);
1374 	zspage = find_get_zspage(class);
1375 	if (likely(zspage)) {
1376 		obj_malloc(pool, zspage, handle);
1377 		/* Now move the zspage to another fullness group, if required */
1378 		fix_fullness_group(class, zspage);
1379 		class_stat_add(class, ZS_OBJS_INUSE, 1);
1380 
1381 		goto out;
1382 	}
1383 
1384 	spin_unlock(&class->lock);
1385 
1386 	zspage = alloc_zspage(pool, class, gfp);
1387 	if (!zspage) {
1388 		cache_free_handle(pool, handle);
1389 		return (unsigned long)ERR_PTR(-ENOMEM);
1390 	}
1391 
1392 	spin_lock(&class->lock);
1393 	obj_malloc(pool, zspage, handle);
1394 	newfg = get_fullness_group(class, zspage);
1395 	insert_zspage(class, zspage, newfg);
1396 	atomic_long_add(class->pages_per_zspage, &pool->pages_allocated);
1397 	class_stat_add(class, ZS_OBJS_ALLOCATED, class->objs_per_zspage);
1398 	class_stat_add(class, ZS_OBJS_INUSE, 1);
1399 
1400 	/* We completely set up zspage so mark them as movable */
1401 	SetZsPageMovable(pool, zspage);
1402 out:
1403 	spin_unlock(&class->lock);
1404 
1405 	return handle;
1406 }
1407 EXPORT_SYMBOL_GPL(zs_malloc);
1408 
obj_free(int class_size,unsigned long obj)1409 static void obj_free(int class_size, unsigned long obj)
1410 {
1411 	struct link_free *link;
1412 	struct zspage *zspage;
1413 	struct page *f_page;
1414 	unsigned long f_offset;
1415 	unsigned int f_objidx;
1416 	void *vaddr;
1417 
1418 	obj_to_location(obj, &f_page, &f_objidx);
1419 	f_offset = offset_in_page(class_size * f_objidx);
1420 	zspage = get_zspage(f_page);
1421 
1422 	vaddr = kmap_atomic(f_page);
1423 	link = (struct link_free *)(vaddr + f_offset);
1424 
1425 	/* Insert this object in containing zspage's freelist */
1426 	if (likely(!ZsHugePage(zspage)))
1427 		link->next = get_freeobj(zspage) << OBJ_TAG_BITS;
1428 	else
1429 		f_page->index = 0;
1430 	set_freeobj(zspage, f_objidx);
1431 
1432 	kunmap_atomic(vaddr);
1433 	mod_zspage_inuse(zspage, -1);
1434 }
1435 
zs_free(struct zs_pool * pool,unsigned long handle)1436 void zs_free(struct zs_pool *pool, unsigned long handle)
1437 {
1438 	struct zspage *zspage;
1439 	struct page *f_page;
1440 	unsigned long obj;
1441 	struct size_class *class;
1442 	int fullness;
1443 
1444 	if (IS_ERR_OR_NULL((void *)handle))
1445 		return;
1446 
1447 	/*
1448 	 * The pool->migrate_lock protects the race with zpage's migration
1449 	 * so it's safe to get the page from handle.
1450 	 */
1451 	read_lock(&pool->migrate_lock);
1452 	obj = handle_to_obj(handle);
1453 	obj_to_page(obj, &f_page);
1454 	zspage = get_zspage(f_page);
1455 	class = zspage_class(pool, zspage);
1456 	spin_lock(&class->lock);
1457 	read_unlock(&pool->migrate_lock);
1458 
1459 	class_stat_sub(class, ZS_OBJS_INUSE, 1);
1460 	obj_free(class->size, obj);
1461 
1462 	fullness = fix_fullness_group(class, zspage);
1463 	if (fullness == ZS_INUSE_RATIO_0)
1464 		free_zspage(pool, class, zspage);
1465 
1466 	spin_unlock(&class->lock);
1467 	cache_free_handle(pool, handle);
1468 }
1469 EXPORT_SYMBOL_GPL(zs_free);
1470 
zs_object_copy(struct size_class * class,unsigned long dst,unsigned long src)1471 static void zs_object_copy(struct size_class *class, unsigned long dst,
1472 				unsigned long src)
1473 {
1474 	struct page *s_page, *d_page;
1475 	unsigned int s_objidx, d_objidx;
1476 	unsigned long s_off, d_off;
1477 	void *s_addr, *d_addr;
1478 	int s_size, d_size, size;
1479 	int written = 0;
1480 
1481 	s_size = d_size = class->size;
1482 
1483 	obj_to_location(src, &s_page, &s_objidx);
1484 	obj_to_location(dst, &d_page, &d_objidx);
1485 
1486 	s_off = offset_in_page(class->size * s_objidx);
1487 	d_off = offset_in_page(class->size * d_objidx);
1488 
1489 	if (s_off + class->size > PAGE_SIZE)
1490 		s_size = PAGE_SIZE - s_off;
1491 
1492 	if (d_off + class->size > PAGE_SIZE)
1493 		d_size = PAGE_SIZE - d_off;
1494 
1495 	s_addr = kmap_atomic(s_page);
1496 	d_addr = kmap_atomic(d_page);
1497 
1498 	while (1) {
1499 		size = min(s_size, d_size);
1500 		memcpy(d_addr + d_off, s_addr + s_off, size);
1501 		written += size;
1502 
1503 		if (written == class->size)
1504 			break;
1505 
1506 		s_off += size;
1507 		s_size -= size;
1508 		d_off += size;
1509 		d_size -= size;
1510 
1511 		/*
1512 		 * Calling kunmap_atomic(d_addr) is necessary. kunmap_atomic()
1513 		 * calls must occurs in reverse order of calls to kmap_atomic().
1514 		 * So, to call kunmap_atomic(s_addr) we should first call
1515 		 * kunmap_atomic(d_addr). For more details see
1516 		 * Documentation/mm/highmem.rst.
1517 		 */
1518 		if (s_off >= PAGE_SIZE) {
1519 			kunmap_atomic(d_addr);
1520 			kunmap_atomic(s_addr);
1521 			s_page = get_next_page(s_page);
1522 			s_addr = kmap_atomic(s_page);
1523 			d_addr = kmap_atomic(d_page);
1524 			s_size = class->size - written;
1525 			s_off = 0;
1526 		}
1527 
1528 		if (d_off >= PAGE_SIZE) {
1529 			kunmap_atomic(d_addr);
1530 			d_page = get_next_page(d_page);
1531 			d_addr = kmap_atomic(d_page);
1532 			d_size = class->size - written;
1533 			d_off = 0;
1534 		}
1535 	}
1536 
1537 	kunmap_atomic(d_addr);
1538 	kunmap_atomic(s_addr);
1539 }
1540 
1541 /*
1542  * Find alloced object in zspage from index object and
1543  * return handle.
1544  */
find_alloced_obj(struct size_class * class,struct page * page,int * obj_idx)1545 static unsigned long find_alloced_obj(struct size_class *class,
1546 				      struct page *page, int *obj_idx)
1547 {
1548 	unsigned int offset;
1549 	int index = *obj_idx;
1550 	unsigned long handle = 0;
1551 	void *addr = kmap_atomic(page);
1552 
1553 	offset = get_first_obj_offset(page);
1554 	offset += class->size * index;
1555 
1556 	while (offset < PAGE_SIZE) {
1557 		if (obj_allocated(page, addr + offset, &handle))
1558 			break;
1559 
1560 		offset += class->size;
1561 		index++;
1562 	}
1563 
1564 	kunmap_atomic(addr);
1565 
1566 	*obj_idx = index;
1567 
1568 	return handle;
1569 }
1570 
migrate_zspage(struct zs_pool * pool,struct zspage * src_zspage,struct zspage * dst_zspage)1571 static void migrate_zspage(struct zs_pool *pool, struct zspage *src_zspage,
1572 			   struct zspage *dst_zspage)
1573 {
1574 	unsigned long used_obj, free_obj;
1575 	unsigned long handle;
1576 	int obj_idx = 0;
1577 	struct page *s_page = get_first_page(src_zspage);
1578 	struct size_class *class = pool->size_class[src_zspage->class];
1579 
1580 	while (1) {
1581 		handle = find_alloced_obj(class, s_page, &obj_idx);
1582 		if (!handle) {
1583 			s_page = get_next_page(s_page);
1584 			if (!s_page)
1585 				break;
1586 			obj_idx = 0;
1587 			continue;
1588 		}
1589 
1590 		used_obj = handle_to_obj(handle);
1591 		free_obj = obj_malloc(pool, dst_zspage, handle);
1592 		zs_object_copy(class, free_obj, used_obj);
1593 		obj_idx++;
1594 		obj_free(class->size, used_obj);
1595 
1596 		/* Stop if there is no more space */
1597 		if (zspage_full(class, dst_zspage))
1598 			break;
1599 
1600 		/* Stop if there are no more objects to migrate */
1601 		if (zspage_empty(src_zspage))
1602 			break;
1603 	}
1604 }
1605 
isolate_src_zspage(struct size_class * class)1606 static struct zspage *isolate_src_zspage(struct size_class *class)
1607 {
1608 	struct zspage *zspage;
1609 	int fg;
1610 
1611 	for (fg = ZS_INUSE_RATIO_10; fg <= ZS_INUSE_RATIO_99; fg++) {
1612 		zspage = list_first_entry_or_null(&class->fullness_list[fg],
1613 						  struct zspage, list);
1614 		if (zspage) {
1615 			remove_zspage(class, zspage);
1616 			return zspage;
1617 		}
1618 	}
1619 
1620 	return zspage;
1621 }
1622 
isolate_dst_zspage(struct size_class * class)1623 static struct zspage *isolate_dst_zspage(struct size_class *class)
1624 {
1625 	struct zspage *zspage;
1626 	int fg;
1627 
1628 	for (fg = ZS_INUSE_RATIO_99; fg >= ZS_INUSE_RATIO_10; fg--) {
1629 		zspage = list_first_entry_or_null(&class->fullness_list[fg],
1630 						  struct zspage, list);
1631 		if (zspage) {
1632 			remove_zspage(class, zspage);
1633 			return zspage;
1634 		}
1635 	}
1636 
1637 	return zspage;
1638 }
1639 
1640 /*
1641  * putback_zspage - add @zspage into right class's fullness list
1642  * @class: destination class
1643  * @zspage: target page
1644  *
1645  * Return @zspage's fullness status
1646  */
putback_zspage(struct size_class * class,struct zspage * zspage)1647 static int putback_zspage(struct size_class *class, struct zspage *zspage)
1648 {
1649 	int fullness;
1650 
1651 	fullness = get_fullness_group(class, zspage);
1652 	insert_zspage(class, zspage, fullness);
1653 
1654 	return fullness;
1655 }
1656 
1657 #ifdef CONFIG_COMPACTION
1658 /*
1659  * To prevent zspage destroy during migration, zspage freeing should
1660  * hold locks of all pages in the zspage.
1661  */
lock_zspage(struct zspage * zspage)1662 static void lock_zspage(struct zspage *zspage)
1663 {
1664 	struct page *curr_page, *page;
1665 
1666 	/*
1667 	 * Pages we haven't locked yet can be migrated off the list while we're
1668 	 * trying to lock them, so we need to be careful and only attempt to
1669 	 * lock each page under migrate_read_lock(). Otherwise, the page we lock
1670 	 * may no longer belong to the zspage. This means that we may wait for
1671 	 * the wrong page to unlock, so we must take a reference to the page
1672 	 * prior to waiting for it to unlock outside migrate_read_lock().
1673 	 */
1674 	while (1) {
1675 		migrate_read_lock(zspage);
1676 		page = get_first_page(zspage);
1677 		if (trylock_page(page))
1678 			break;
1679 		get_page(page);
1680 		migrate_read_unlock(zspage);
1681 		wait_on_page_locked(page);
1682 		put_page(page);
1683 	}
1684 
1685 	curr_page = page;
1686 	while ((page = get_next_page(curr_page))) {
1687 		if (trylock_page(page)) {
1688 			curr_page = page;
1689 		} else {
1690 			get_page(page);
1691 			migrate_read_unlock(zspage);
1692 			wait_on_page_locked(page);
1693 			put_page(page);
1694 			migrate_read_lock(zspage);
1695 		}
1696 	}
1697 	migrate_read_unlock(zspage);
1698 }
1699 #endif /* CONFIG_COMPACTION */
1700 
migrate_lock_init(struct zspage * zspage)1701 static void migrate_lock_init(struct zspage *zspage)
1702 {
1703 	rwlock_init(&zspage->lock);
1704 }
1705 
migrate_read_lock(struct zspage * zspage)1706 static void migrate_read_lock(struct zspage *zspage) __acquires(&zspage->lock)
1707 {
1708 	read_lock(&zspage->lock);
1709 }
1710 
migrate_read_unlock(struct zspage * zspage)1711 static void migrate_read_unlock(struct zspage *zspage) __releases(&zspage->lock)
1712 {
1713 	read_unlock(&zspage->lock);
1714 }
1715 
migrate_write_lock(struct zspage * zspage)1716 static void migrate_write_lock(struct zspage *zspage)
1717 {
1718 	write_lock(&zspage->lock);
1719 }
1720 
migrate_write_unlock(struct zspage * zspage)1721 static void migrate_write_unlock(struct zspage *zspage)
1722 {
1723 	write_unlock(&zspage->lock);
1724 }
1725 
1726 #ifdef CONFIG_COMPACTION
1727 
1728 static const struct movable_operations zsmalloc_mops;
1729 
replace_sub_page(struct size_class * class,struct zspage * zspage,struct page * newpage,struct page * oldpage)1730 static void replace_sub_page(struct size_class *class, struct zspage *zspage,
1731 				struct page *newpage, struct page *oldpage)
1732 {
1733 	struct page *page;
1734 	struct page *pages[ZS_MAX_PAGES_PER_ZSPAGE] = {NULL, };
1735 	int idx = 0;
1736 
1737 	page = get_first_page(zspage);
1738 	do {
1739 		if (page == oldpage)
1740 			pages[idx] = newpage;
1741 		else
1742 			pages[idx] = page;
1743 		idx++;
1744 	} while ((page = get_next_page(page)) != NULL);
1745 
1746 	create_page_chain(class, zspage, pages);
1747 	set_first_obj_offset(newpage, get_first_obj_offset(oldpage));
1748 	if (unlikely(ZsHugePage(zspage)))
1749 		newpage->index = oldpage->index;
1750 	__SetPageMovable(newpage, &zsmalloc_mops);
1751 }
1752 
zs_page_isolate(struct page * page,isolate_mode_t mode)1753 static bool zs_page_isolate(struct page *page, isolate_mode_t mode)
1754 {
1755 	/*
1756 	 * Page is locked so zspage couldn't be destroyed. For detail, look at
1757 	 * lock_zspage in free_zspage.
1758 	 */
1759 	VM_BUG_ON_PAGE(PageIsolated(page), page);
1760 
1761 	return true;
1762 }
1763 
zs_page_migrate(struct page * newpage,struct page * page,enum migrate_mode mode)1764 static int zs_page_migrate(struct page *newpage, struct page *page,
1765 		enum migrate_mode mode)
1766 {
1767 	struct zs_pool *pool;
1768 	struct size_class *class;
1769 	struct zspage *zspage;
1770 	struct page *dummy;
1771 	void *s_addr, *d_addr, *addr;
1772 	unsigned int offset;
1773 	unsigned long handle;
1774 	unsigned long old_obj, new_obj;
1775 	unsigned int obj_idx;
1776 
1777 	VM_BUG_ON_PAGE(!PageIsolated(page), page);
1778 
1779 	/* We're committed, tell the world that this is a Zsmalloc page. */
1780 	__SetPageZsmalloc(newpage);
1781 
1782 	/* The page is locked, so this pointer must remain valid */
1783 	zspage = get_zspage(page);
1784 	pool = zspage->pool;
1785 
1786 	/*
1787 	 * The pool migrate_lock protects the race between zpage migration
1788 	 * and zs_free.
1789 	 */
1790 	write_lock(&pool->migrate_lock);
1791 	class = zspage_class(pool, zspage);
1792 
1793 	/*
1794 	 * the class lock protects zpage alloc/free in the zspage.
1795 	 */
1796 	spin_lock(&class->lock);
1797 	/* the migrate_write_lock protects zpage access via zs_map_object */
1798 	migrate_write_lock(zspage);
1799 
1800 	offset = get_first_obj_offset(page);
1801 	s_addr = kmap_atomic(page);
1802 
1803 	/*
1804 	 * Here, any user cannot access all objects in the zspage so let's move.
1805 	 */
1806 	d_addr = kmap_atomic(newpage);
1807 	copy_page(d_addr, s_addr);
1808 	kunmap_atomic(d_addr);
1809 
1810 	for (addr = s_addr + offset; addr < s_addr + PAGE_SIZE;
1811 					addr += class->size) {
1812 		if (obj_allocated(page, addr, &handle)) {
1813 
1814 			old_obj = handle_to_obj(handle);
1815 			obj_to_location(old_obj, &dummy, &obj_idx);
1816 			new_obj = (unsigned long)location_to_obj(newpage,
1817 								obj_idx);
1818 			record_obj(handle, new_obj);
1819 		}
1820 	}
1821 	kunmap_atomic(s_addr);
1822 
1823 	replace_sub_page(class, zspage, newpage, page);
1824 	/*
1825 	 * Since we complete the data copy and set up new zspage structure,
1826 	 * it's okay to release migration_lock.
1827 	 */
1828 	write_unlock(&pool->migrate_lock);
1829 	spin_unlock(&class->lock);
1830 	migrate_write_unlock(zspage);
1831 
1832 	get_page(newpage);
1833 	if (page_zone(newpage) != page_zone(page)) {
1834 		dec_zone_page_state(page, NR_ZSPAGES);
1835 		inc_zone_page_state(newpage, NR_ZSPAGES);
1836 	}
1837 
1838 	reset_page(page);
1839 	put_page(page);
1840 
1841 	return MIGRATEPAGE_SUCCESS;
1842 }
1843 
zs_page_putback(struct page * page)1844 static void zs_page_putback(struct page *page)
1845 {
1846 	VM_BUG_ON_PAGE(!PageIsolated(page), page);
1847 }
1848 
1849 static const struct movable_operations zsmalloc_mops = {
1850 	.isolate_page = zs_page_isolate,
1851 	.migrate_page = zs_page_migrate,
1852 	.putback_page = zs_page_putback,
1853 };
1854 
1855 /*
1856  * Caller should hold page_lock of all pages in the zspage
1857  * In here, we cannot use zspage meta data.
1858  */
async_free_zspage(struct work_struct * work)1859 static void async_free_zspage(struct work_struct *work)
1860 {
1861 	int i;
1862 	struct size_class *class;
1863 	struct zspage *zspage, *tmp;
1864 	LIST_HEAD(free_pages);
1865 	struct zs_pool *pool = container_of(work, struct zs_pool,
1866 					free_work);
1867 
1868 	for (i = 0; i < ZS_SIZE_CLASSES; i++) {
1869 		class = pool->size_class[i];
1870 		if (class->index != i)
1871 			continue;
1872 
1873 		spin_lock(&class->lock);
1874 		list_splice_init(&class->fullness_list[ZS_INUSE_RATIO_0],
1875 				 &free_pages);
1876 		spin_unlock(&class->lock);
1877 	}
1878 
1879 	list_for_each_entry_safe(zspage, tmp, &free_pages, list) {
1880 		list_del(&zspage->list);
1881 		lock_zspage(zspage);
1882 
1883 		class = zspage_class(pool, zspage);
1884 		spin_lock(&class->lock);
1885 		class_stat_sub(class, ZS_INUSE_RATIO_0, 1);
1886 		__free_zspage(pool, class, zspage);
1887 		spin_unlock(&class->lock);
1888 	}
1889 };
1890 
kick_deferred_free(struct zs_pool * pool)1891 static void kick_deferred_free(struct zs_pool *pool)
1892 {
1893 	schedule_work(&pool->free_work);
1894 }
1895 
zs_flush_migration(struct zs_pool * pool)1896 static void zs_flush_migration(struct zs_pool *pool)
1897 {
1898 	flush_work(&pool->free_work);
1899 }
1900 
init_deferred_free(struct zs_pool * pool)1901 static void init_deferred_free(struct zs_pool *pool)
1902 {
1903 	INIT_WORK(&pool->free_work, async_free_zspage);
1904 }
1905 
SetZsPageMovable(struct zs_pool * pool,struct zspage * zspage)1906 static void SetZsPageMovable(struct zs_pool *pool, struct zspage *zspage)
1907 {
1908 	struct page *page = get_first_page(zspage);
1909 
1910 	do {
1911 		WARN_ON(!trylock_page(page));
1912 		__SetPageMovable(page, &zsmalloc_mops);
1913 		unlock_page(page);
1914 	} while ((page = get_next_page(page)) != NULL);
1915 }
1916 #else
zs_flush_migration(struct zs_pool * pool)1917 static inline void zs_flush_migration(struct zs_pool *pool) { }
1918 #endif
1919 
1920 /*
1921  *
1922  * Based on the number of unused allocated objects calculate
1923  * and return the number of pages that we can free.
1924  */
zs_can_compact(struct size_class * class)1925 static unsigned long zs_can_compact(struct size_class *class)
1926 {
1927 	unsigned long obj_wasted;
1928 	unsigned long obj_allocated = class_stat_read(class, ZS_OBJS_ALLOCATED);
1929 	unsigned long obj_used = class_stat_read(class, ZS_OBJS_INUSE);
1930 
1931 	if (obj_allocated <= obj_used)
1932 		return 0;
1933 
1934 	obj_wasted = obj_allocated - obj_used;
1935 	obj_wasted /= class->objs_per_zspage;
1936 
1937 	return obj_wasted * class->pages_per_zspage;
1938 }
1939 
__zs_compact(struct zs_pool * pool,struct size_class * class)1940 static unsigned long __zs_compact(struct zs_pool *pool,
1941 				  struct size_class *class)
1942 {
1943 	struct zspage *src_zspage = NULL;
1944 	struct zspage *dst_zspage = NULL;
1945 	unsigned long pages_freed = 0;
1946 
1947 	/*
1948 	 * protect the race between zpage migration and zs_free
1949 	 * as well as zpage allocation/free
1950 	 */
1951 	write_lock(&pool->migrate_lock);
1952 	spin_lock(&class->lock);
1953 	while (zs_can_compact(class)) {
1954 		int fg;
1955 
1956 		if (!dst_zspage) {
1957 			dst_zspage = isolate_dst_zspage(class);
1958 			if (!dst_zspage)
1959 				break;
1960 		}
1961 
1962 		src_zspage = isolate_src_zspage(class);
1963 		if (!src_zspage)
1964 			break;
1965 
1966 		migrate_write_lock(src_zspage);
1967 		migrate_zspage(pool, src_zspage, dst_zspage);
1968 		migrate_write_unlock(src_zspage);
1969 
1970 		fg = putback_zspage(class, src_zspage);
1971 		if (fg == ZS_INUSE_RATIO_0) {
1972 			free_zspage(pool, class, src_zspage);
1973 			pages_freed += class->pages_per_zspage;
1974 		}
1975 		src_zspage = NULL;
1976 
1977 		if (get_fullness_group(class, dst_zspage) == ZS_INUSE_RATIO_100
1978 		    || rwlock_is_contended(&pool->migrate_lock)) {
1979 			putback_zspage(class, dst_zspage);
1980 			dst_zspage = NULL;
1981 
1982 			spin_unlock(&class->lock);
1983 			write_unlock(&pool->migrate_lock);
1984 			cond_resched();
1985 			write_lock(&pool->migrate_lock);
1986 			spin_lock(&class->lock);
1987 		}
1988 	}
1989 
1990 	if (src_zspage)
1991 		putback_zspage(class, src_zspage);
1992 
1993 	if (dst_zspage)
1994 		putback_zspage(class, dst_zspage);
1995 
1996 	spin_unlock(&class->lock);
1997 	write_unlock(&pool->migrate_lock);
1998 
1999 	return pages_freed;
2000 }
2001 
zs_compact(struct zs_pool * pool)2002 unsigned long zs_compact(struct zs_pool *pool)
2003 {
2004 	int i;
2005 	struct size_class *class;
2006 	unsigned long pages_freed = 0;
2007 
2008 	/*
2009 	 * Pool compaction is performed under pool->migrate_lock so it is basically
2010 	 * single-threaded. Having more than one thread in __zs_compact()
2011 	 * will increase pool->migrate_lock contention, which will impact other
2012 	 * zsmalloc operations that need pool->migrate_lock.
2013 	 */
2014 	if (atomic_xchg(&pool->compaction_in_progress, 1))
2015 		return 0;
2016 
2017 	for (i = ZS_SIZE_CLASSES - 1; i >= 0; i--) {
2018 		class = pool->size_class[i];
2019 		if (class->index != i)
2020 			continue;
2021 		pages_freed += __zs_compact(pool, class);
2022 	}
2023 	atomic_long_add(pages_freed, &pool->stats.pages_compacted);
2024 	atomic_set(&pool->compaction_in_progress, 0);
2025 
2026 	return pages_freed;
2027 }
2028 EXPORT_SYMBOL_GPL(zs_compact);
2029 
zs_pool_stats(struct zs_pool * pool,struct zs_pool_stats * stats)2030 void zs_pool_stats(struct zs_pool *pool, struct zs_pool_stats *stats)
2031 {
2032 	memcpy(stats, &pool->stats, sizeof(struct zs_pool_stats));
2033 }
2034 EXPORT_SYMBOL_GPL(zs_pool_stats);
2035 
zs_shrinker_scan(struct shrinker * shrinker,struct shrink_control * sc)2036 static unsigned long zs_shrinker_scan(struct shrinker *shrinker,
2037 		struct shrink_control *sc)
2038 {
2039 	unsigned long pages_freed;
2040 	struct zs_pool *pool = shrinker->private_data;
2041 
2042 	/*
2043 	 * Compact classes and calculate compaction delta.
2044 	 * Can run concurrently with a manually triggered
2045 	 * (by user) compaction.
2046 	 */
2047 	pages_freed = zs_compact(pool);
2048 
2049 	return pages_freed ? pages_freed : SHRINK_STOP;
2050 }
2051 
zs_shrinker_count(struct shrinker * shrinker,struct shrink_control * sc)2052 static unsigned long zs_shrinker_count(struct shrinker *shrinker,
2053 		struct shrink_control *sc)
2054 {
2055 	int i;
2056 	struct size_class *class;
2057 	unsigned long pages_to_free = 0;
2058 	struct zs_pool *pool = shrinker->private_data;
2059 
2060 	for (i = ZS_SIZE_CLASSES - 1; i >= 0; i--) {
2061 		class = pool->size_class[i];
2062 		if (class->index != i)
2063 			continue;
2064 
2065 		pages_to_free += zs_can_compact(class);
2066 	}
2067 
2068 	return pages_to_free;
2069 }
2070 
zs_unregister_shrinker(struct zs_pool * pool)2071 static void zs_unregister_shrinker(struct zs_pool *pool)
2072 {
2073 	shrinker_free(pool->shrinker);
2074 }
2075 
zs_register_shrinker(struct zs_pool * pool)2076 static int zs_register_shrinker(struct zs_pool *pool)
2077 {
2078 	pool->shrinker = shrinker_alloc(0, "mm-zspool:%s", pool->name);
2079 	if (!pool->shrinker)
2080 		return -ENOMEM;
2081 
2082 	pool->shrinker->scan_objects = zs_shrinker_scan;
2083 	pool->shrinker->count_objects = zs_shrinker_count;
2084 	pool->shrinker->batch = 0;
2085 	pool->shrinker->private_data = pool;
2086 
2087 	shrinker_register(pool->shrinker);
2088 
2089 	return 0;
2090 }
2091 
calculate_zspage_chain_size(int class_size)2092 static int calculate_zspage_chain_size(int class_size)
2093 {
2094 	int i, min_waste = INT_MAX;
2095 	int chain_size = 1;
2096 
2097 	if (is_power_of_2(class_size))
2098 		return chain_size;
2099 
2100 	for (i = 1; i <= ZS_MAX_PAGES_PER_ZSPAGE; i++) {
2101 		int waste;
2102 
2103 		waste = (i * PAGE_SIZE) % class_size;
2104 		if (waste < min_waste) {
2105 			min_waste = waste;
2106 			chain_size = i;
2107 		}
2108 	}
2109 
2110 	return chain_size;
2111 }
2112 
2113 /**
2114  * zs_create_pool - Creates an allocation pool to work from.
2115  * @name: pool name to be created
2116  *
2117  * This function must be called before anything when using
2118  * the zsmalloc allocator.
2119  *
2120  * On success, a pointer to the newly created pool is returned,
2121  * otherwise NULL.
2122  */
zs_create_pool(const char * name)2123 struct zs_pool *zs_create_pool(const char *name)
2124 {
2125 	int i;
2126 	struct zs_pool *pool;
2127 	struct size_class *prev_class = NULL;
2128 
2129 	pool = kzalloc(sizeof(*pool), GFP_KERNEL);
2130 	if (!pool)
2131 		return NULL;
2132 
2133 	init_deferred_free(pool);
2134 	rwlock_init(&pool->migrate_lock);
2135 	atomic_set(&pool->compaction_in_progress, 0);
2136 
2137 	pool->name = kstrdup(name, GFP_KERNEL);
2138 	if (!pool->name)
2139 		goto err;
2140 
2141 	if (create_cache(pool))
2142 		goto err;
2143 
2144 	/*
2145 	 * Iterate reversely, because, size of size_class that we want to use
2146 	 * for merging should be larger or equal to current size.
2147 	 */
2148 	for (i = ZS_SIZE_CLASSES - 1; i >= 0; i--) {
2149 		int size;
2150 		int pages_per_zspage;
2151 		int objs_per_zspage;
2152 		struct size_class *class;
2153 		int fullness;
2154 
2155 		size = ZS_MIN_ALLOC_SIZE + i * ZS_SIZE_CLASS_DELTA;
2156 		if (size > ZS_MAX_ALLOC_SIZE)
2157 			size = ZS_MAX_ALLOC_SIZE;
2158 		pages_per_zspage = calculate_zspage_chain_size(size);
2159 		objs_per_zspage = pages_per_zspage * PAGE_SIZE / size;
2160 
2161 		/*
2162 		 * We iterate from biggest down to smallest classes,
2163 		 * so huge_class_size holds the size of the first huge
2164 		 * class. Any object bigger than or equal to that will
2165 		 * endup in the huge class.
2166 		 */
2167 		if (pages_per_zspage != 1 && objs_per_zspage != 1 &&
2168 				!huge_class_size) {
2169 			huge_class_size = size;
2170 			/*
2171 			 * The object uses ZS_HANDLE_SIZE bytes to store the
2172 			 * handle. We need to subtract it, because zs_malloc()
2173 			 * unconditionally adds handle size before it performs
2174 			 * size class search - so object may be smaller than
2175 			 * huge class size, yet it still can end up in the huge
2176 			 * class because it grows by ZS_HANDLE_SIZE extra bytes
2177 			 * right before class lookup.
2178 			 */
2179 			huge_class_size -= (ZS_HANDLE_SIZE - 1);
2180 		}
2181 
2182 		/*
2183 		 * size_class is used for normal zsmalloc operation such
2184 		 * as alloc/free for that size. Although it is natural that we
2185 		 * have one size_class for each size, there is a chance that we
2186 		 * can get more memory utilization if we use one size_class for
2187 		 * many different sizes whose size_class have same
2188 		 * characteristics. So, we makes size_class point to
2189 		 * previous size_class if possible.
2190 		 */
2191 		if (prev_class) {
2192 			if (can_merge(prev_class, pages_per_zspage, objs_per_zspage)) {
2193 				pool->size_class[i] = prev_class;
2194 				continue;
2195 			}
2196 		}
2197 
2198 		class = kzalloc(sizeof(struct size_class), GFP_KERNEL);
2199 		if (!class)
2200 			goto err;
2201 
2202 		class->size = size;
2203 		class->index = i;
2204 		class->pages_per_zspage = pages_per_zspage;
2205 		class->objs_per_zspage = objs_per_zspage;
2206 		spin_lock_init(&class->lock);
2207 		pool->size_class[i] = class;
2208 
2209 		fullness = ZS_INUSE_RATIO_0;
2210 		while (fullness < NR_FULLNESS_GROUPS) {
2211 			INIT_LIST_HEAD(&class->fullness_list[fullness]);
2212 			fullness++;
2213 		}
2214 
2215 		prev_class = class;
2216 	}
2217 
2218 	/* debug only, don't abort if it fails */
2219 	zs_pool_stat_create(pool, name);
2220 
2221 	/*
2222 	 * Not critical since shrinker is only used to trigger internal
2223 	 * defragmentation of the pool which is pretty optional thing.  If
2224 	 * registration fails we still can use the pool normally and user can
2225 	 * trigger compaction manually. Thus, ignore return code.
2226 	 */
2227 	zs_register_shrinker(pool);
2228 
2229 	return pool;
2230 
2231 err:
2232 	zs_destroy_pool(pool);
2233 	return NULL;
2234 }
2235 EXPORT_SYMBOL_GPL(zs_create_pool);
2236 
zs_destroy_pool(struct zs_pool * pool)2237 void zs_destroy_pool(struct zs_pool *pool)
2238 {
2239 	int i;
2240 
2241 	zs_unregister_shrinker(pool);
2242 	zs_flush_migration(pool);
2243 	zs_pool_stat_destroy(pool);
2244 
2245 	for (i = 0; i < ZS_SIZE_CLASSES; i++) {
2246 		int fg;
2247 		struct size_class *class = pool->size_class[i];
2248 
2249 		if (!class)
2250 			continue;
2251 
2252 		if (class->index != i)
2253 			continue;
2254 
2255 		for (fg = ZS_INUSE_RATIO_0; fg < NR_FULLNESS_GROUPS; fg++) {
2256 			if (list_empty(&class->fullness_list[fg]))
2257 				continue;
2258 
2259 			pr_err("Class-%d fullness group %d is not empty\n",
2260 			       class->size, fg);
2261 		}
2262 		kfree(class);
2263 	}
2264 
2265 	destroy_cache(pool);
2266 	kfree(pool->name);
2267 	kfree(pool);
2268 }
2269 EXPORT_SYMBOL_GPL(zs_destroy_pool);
2270 
zs_init(void)2271 static int __init zs_init(void)
2272 {
2273 	int ret;
2274 
2275 	ret = cpuhp_setup_state(CPUHP_MM_ZS_PREPARE, "mm/zsmalloc:prepare",
2276 				zs_cpu_prepare, zs_cpu_dead);
2277 	if (ret)
2278 		goto out;
2279 
2280 #ifdef CONFIG_ZPOOL
2281 	zpool_register_driver(&zs_zpool_driver);
2282 #endif
2283 
2284 	zs_stat_init();
2285 
2286 	return 0;
2287 
2288 out:
2289 	return ret;
2290 }
2291 
zs_exit(void)2292 static void __exit zs_exit(void)
2293 {
2294 #ifdef CONFIG_ZPOOL
2295 	zpool_unregister_driver(&zs_zpool_driver);
2296 #endif
2297 	cpuhp_remove_state(CPUHP_MM_ZS_PREPARE);
2298 
2299 	zs_stat_exit();
2300 }
2301 
2302 module_init(zs_init);
2303 module_exit(zs_exit);
2304 
2305 MODULE_LICENSE("Dual BSD/GPL");
2306 MODULE_AUTHOR("Nitin Gupta <ngupta@vflare.org>");
2307 MODULE_DESCRIPTION("zsmalloc memory allocator");
2308