path: root/mm/zsmalloc.c (plain)
blob: e331312ec4cde667ab93998fea1a5e062c4085f3

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->freelist(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->units: first object offset in a subpage of zspage
24	*
25	* Usage of struct page flags:
26	* PG_private: identifies the first component page
27	* PG_private2: identifies the last component page
28	* PG_owner_priv_1: indentifies the huge component page
29	*
30	*/
31
32	#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
33
34	#include <linux/module.h>
35	#include <linux/kernel.h>
36	#include <linux/sched.h>
37	#include <linux/bitops.h>
38	#include <linux/errno.h>
39	#include <linux/highmem.h>
40	#include <linux/string.h>
41	#include <linux/slab.h>
42	#include <asm/tlbflush.h>
43	#include <asm/pgtable.h>
44	#include <linux/cpumask.h>
45	#include <linux/cpu.h>
46	#include <linux/vmalloc.h>
47	#include <linux/preempt.h>
48	#include <linux/spinlock.h>
49	#include <linux/types.h>
50	#include <linux/debugfs.h>
51	#include <linux/zsmalloc.h>
52	#include <linux/zpool.h>
53	#include <linux/mount.h>
54	#include <linux/migrate.h>
55	#include <linux/pagemap.h>
56
57	#define ZSPAGE_MAGIC 0x58
58
59	/*
60	* This must be power of 2 and greater than of equal to sizeof(link_free).
61	* These two conditions ensure that any 'struct link_free' itself doesn't
62	* span more than 1 page which avoids complex case of mapping 2 pages simply
63	* to restore link_free pointer values.
64	*/
65	#define ZS_ALIGN 8
66
67	/*
68	* A single 'zspage' is composed of up to 2^N discontiguous 0-order (single)
69	* pages. ZS_MAX_ZSPAGE_ORDER defines upper limit on N.
70	*/
71	#define ZS_MAX_ZSPAGE_ORDER 2
72	#define ZS_MAX_PAGES_PER_ZSPAGE (_AC(1, UL) << ZS_MAX_ZSPAGE_ORDER)
73
74	#define ZS_HANDLE_SIZE (sizeof(unsigned long))
75
76	/*
77	* Object location (<PFN>, <obj_idx>) is encoded as
78	* as single (unsigned long) handle value.
79	*
80	* Note that object index <obj_idx> starts from 0.
81	*
82	* This is made more complicated by various memory models and PAE.
83	*/
84
85	#ifndef MAX_PHYSMEM_BITS
86	#ifdef CONFIG_HIGHMEM64G
87	#define MAX_PHYSMEM_BITS 36
88	#else /* !CONFIG_HIGHMEM64G */
89	/*
90	* If this definition of MAX_PHYSMEM_BITS is used, OBJ_INDEX_BITS will just
91	* be PAGE_SHIFT
92	*/
93	#define MAX_PHYSMEM_BITS BITS_PER_LONG
94	#endif
95	#endif
96	#define _PFN_BITS (MAX_PHYSMEM_BITS - PAGE_SHIFT)
97
98	/*
99	* Memory for allocating for handle keeps object position by
100	* encoding <page, obj_idx> and the encoded value has a room
101	* in least bit(ie, look at obj_to_location).
102	* We use the bit to synchronize between object access by
103	* user and migration.
104	*/
105	#define HANDLE_PIN_BIT 0
106
107	/*
108	* Head in allocated object should have OBJ_ALLOCATED_TAG
109	* to identify the object was allocated or not.
110	* It's okay to add the status bit in the least bit because
111	* header keeps handle which is 4byte-aligned address so we
112	* have room for two bit at least.
113	*/
114	#define OBJ_ALLOCATED_TAG 1
115	#define OBJ_TAG_BITS 1
116	#define OBJ_INDEX_BITS (BITS_PER_LONG - _PFN_BITS - OBJ_TAG_BITS)
117	#define OBJ_INDEX_MASK ((_AC(1, UL) << OBJ_INDEX_BITS) - 1)
118
119	#define MAX(a, b) ((a) >= (b) ? (a) : (b))
120	/* ZS_MIN_ALLOC_SIZE must be multiple of ZS_ALIGN */
121	#define ZS_MIN_ALLOC_SIZE \
122	MAX(32, (ZS_MAX_PAGES_PER_ZSPAGE << PAGE_SHIFT >> OBJ_INDEX_BITS))
123	/* each chunk includes extra space to keep handle */
124	#define ZS_MAX_ALLOC_SIZE PAGE_SIZE
125
126	/*
127	* On systems with 4K page size, this gives 255 size classes! There is a
128	* trader-off here:
129	* - Large number of size classes is potentially wasteful as free page are
130	* spread across these classes
131	* - Small number of size classes causes large internal fragmentation
132	* - Probably its better to use specific size classes (empirically
133	* determined). NOTE: all those class sizes must be set as multiple of
134	* ZS_ALIGN to make sure link_free itself never has to span 2 pages.
135	*
136	* ZS_MIN_ALLOC_SIZE and ZS_SIZE_CLASS_DELTA must be multiple of ZS_ALIGN
137	* (reason above)
138	*/
139	#define ZS_SIZE_CLASS_DELTA (PAGE_SIZE >> CLASS_BITS)
140
141	enum fullness_group {
142	ZS_EMPTY,
143	ZS_ALMOST_EMPTY,
144	ZS_ALMOST_FULL,
145	ZS_FULL,
146	NR_ZS_FULLNESS,
147	};
148
149	enum zs_stat_type {
150	CLASS_EMPTY,
151	CLASS_ALMOST_EMPTY,
152	CLASS_ALMOST_FULL,
153	CLASS_FULL,
154	OBJ_ALLOCATED,
155	OBJ_USED,
156	NR_ZS_STAT_TYPE,
157	};
158
159	struct zs_size_stat {
160	unsigned long objs[NR_ZS_STAT_TYPE];
161	};
162
163	#ifdef CONFIG_ZSMALLOC_STAT
164	static struct dentry *zs_stat_root;
165	#endif
166
167	#ifdef CONFIG_COMPACTION
168	static struct vfsmount *zsmalloc_mnt;
169	#endif
170
171	/*
172	* number of size_classes
173	*/
174	static int zs_size_classes;
175
176	/*
177	* We assign a page to ZS_ALMOST_EMPTY fullness group when:
178	* n <= N / f, where
179	* n = number of allocated objects
180	* N = total number of objects zspage can store
181	* f = fullness_threshold_frac
182	*
183	* Similarly, we assign zspage to:
184	* ZS_ALMOST_FULL when n > N / f
185	* ZS_EMPTY when n == 0
186	* ZS_FULL when n == N
187	*
188	* (see: fix_fullness_group())
189	*/
190	static const int fullness_threshold_frac = 4;
191	static size_t huge_class_size;
192
193	struct size_class {
194	spinlock_t lock;
195	struct list_head fullness_list[NR_ZS_FULLNESS];
196	/*
197	* Size of objects stored in this class. Must be multiple
198	* of ZS_ALIGN.
199	*/
200	int size;
201	int objs_per_zspage;
202	/* Number of PAGE_SIZE sized pages to combine to form a 'zspage' */
203	int pages_per_zspage;
204
205	unsigned int index;
206	struct zs_size_stat stats;
207	};
208
209	/* huge object: pages_per_zspage == 1 && maxobj_per_zspage == 1 */
210	static void SetPageHugeObject(struct page *page)
211	{
212	SetPageOwnerPriv1(page);
213	}
214
215	static void ClearPageHugeObject(struct page *page)
216	{
217	ClearPageOwnerPriv1(page);
218	}
219
220	static int PageHugeObject(struct page *page)
221	{
222	return PageOwnerPriv1(page);
223	}
224
225	/*
226	* Placed within free objects to form a singly linked list.
227	* For every zspage, zspage->freeobj gives head of this list.
228	*
229	* This must be power of 2 and less than or equal to ZS_ALIGN
230	*/
231	struct link_free {
232	union {
233	/*
234	* Free object index;
235	* It's valid for non-allocated object
236	*/
237	unsigned long next;
238	/*
239	* Handle of allocated object.
240	*/
241	unsigned long handle;
242	};
243	};
244
245	struct zs_pool {
246	const char *name;
247
248	struct size_class **size_class;
249	struct kmem_cache *handle_cachep;
250	struct kmem_cache *zspage_cachep;
251
252	atomic_long_t pages_allocated;
253
254	struct zs_pool_stats stats;
255
256	/* Compact classes */
257	struct shrinker shrinker;
258	/*
259	* To signify that register_shrinker() was successful
260	* and unregister_shrinker() will not Oops.
261	*/
262	bool shrinker_enabled;
263	#ifdef CONFIG_ZSMALLOC_STAT
264	struct dentry *stat_dentry;
265	#endif
266	#ifdef CONFIG_COMPACTION
267	struct inode *inode;
268	struct work_struct free_work;
269	#endif
270	};
271
272	/*
273	* A zspage's class index and fullness group
274	* are encoded in its (first)page->mapping
275	*/
276	#define FULLNESS_BITS 2
277	#define CLASS_BITS 8
278	#define ISOLATED_BITS 3
279	#define MAGIC_VAL_BITS 8
280
281	struct zspage {
282	struct {
283	unsigned int fullness:FULLNESS_BITS;
284	unsigned int class:CLASS_BITS + 1;
285	unsigned int isolated:ISOLATED_BITS;
286	unsigned int magic:MAGIC_VAL_BITS;
287	};
288	unsigned int inuse;
289	unsigned int freeobj;
290	struct page *first_page;
291	struct list_head list; /* fullness list */
292	#ifdef CONFIG_COMPACTION
293	rwlock_t lock;
294	#endif
295	};
296
297	struct mapping_area {
298	#ifdef CONFIG_PGTABLE_MAPPING
299	struct vm_struct *vm; /* vm area for mapping object that span pages */
300	#else
301	char *vm_buf; /* copy buffer for objects that span pages */
302	#endif
303	char *vm_addr; /* address of kmap_atomic()'ed pages */
304	enum zs_mapmode vm_mm; /* mapping mode */
305	};
306
307	#ifdef CONFIG_COMPACTION
308	static int zs_register_migration(struct zs_pool *pool);
309	static void zs_unregister_migration(struct zs_pool *pool);
310	static void migrate_lock_init(struct zspage *zspage);
311	static void migrate_read_lock(struct zspage *zspage);
312	static void migrate_read_unlock(struct zspage *zspage);
313	static void kick_deferred_free(struct zs_pool *pool);
314	static void init_deferred_free(struct zs_pool *pool);
315	static void SetZsPageMovable(struct zs_pool *pool, struct zspage *zspage);
316	#else
317	static int zsmalloc_mount(void) { return 0; }
318	static void zsmalloc_unmount(void) {}
319	static int zs_register_migration(struct zs_pool *pool) { return 0; }
320	static void zs_unregister_migration(struct zs_pool *pool) {}
321	static void migrate_lock_init(struct zspage *zspage) {}
322	static void migrate_read_lock(struct zspage *zspage) {}
323	static void migrate_read_unlock(struct zspage *zspage) {}
324	static void kick_deferred_free(struct zs_pool *pool) {}
325	static void init_deferred_free(struct zs_pool *pool) {}
326	static void SetZsPageMovable(struct zs_pool *pool, struct zspage *zspage) {}
327	#endif
328
329	static int create_cache(struct zs_pool *pool)
330	{
331	pool->handle_cachep = kmem_cache_create("zs_handle", ZS_HANDLE_SIZE,
332	0, 0, NULL);
333	if (!pool->handle_cachep)
334	return 1;
335
336	pool->zspage_cachep = kmem_cache_create("zspage", sizeof(struct zspage),
337	0, 0, NULL);
338	if (!pool->zspage_cachep) {
339	kmem_cache_destroy(pool->handle_cachep);
340	pool->handle_cachep = NULL;
341	return 1;
342	}
343
344	return 0;
345	}
346
347	static void destroy_cache(struct zs_pool *pool)
348	{
349	kmem_cache_destroy(pool->handle_cachep);
350	kmem_cache_destroy(pool->zspage_cachep);
351	}
352
353	static unsigned long cache_alloc_handle(struct zs_pool *pool, gfp_t gfp)
354	{
355	return (unsigned long)kmem_cache_alloc(pool->handle_cachep,
356	gfp & ~(__GFP_HIGHMEM|__GFP_MOVABLE));
357	}
358
359	static void cache_free_handle(struct zs_pool *pool, unsigned long handle)
360	{
361	kmem_cache_free(pool->handle_cachep, (void *)handle);
362	}
363
364	static struct zspage *cache_alloc_zspage(struct zs_pool *pool, gfp_t flags)
365	{
366	return kmem_cache_alloc(pool->zspage_cachep,
367	flags & ~(__GFP_HIGHMEM|__GFP_MOVABLE));
368	};
369
370	static void cache_free_zspage(struct zs_pool *pool, struct zspage *zspage)
371	{
372	kmem_cache_free(pool->zspage_cachep, zspage);
373	}
374
375	static void record_obj(unsigned long handle, unsigned long obj)
376	{
377	/*
378	* lsb of @obj represents handle lock while other bits
379	* represent object value the handle is pointing so
380	* updating shouldn't do store tearing.
381	*/
382	WRITE_ONCE(*(unsigned long *)handle, obj);
383	}
384
385	/* zpool driver */
386
387	#ifdef CONFIG_ZPOOL
388
389	static void *zs_zpool_create(const char *name, gfp_t gfp,
390	const struct zpool_ops *zpool_ops,
391	struct zpool *zpool)
392	{
393	/*
394	* Ignore global gfp flags: zs_malloc() may be invoked from
395	* different contexts and its caller must provide a valid
396	* gfp mask.
397	*/
398	return zs_create_pool(name);
399	}
400
401	static void zs_zpool_destroy(void *pool)
402	{
403	zs_destroy_pool(pool);
404	}
405
406	static int zs_zpool_malloc(void *pool, size_t size, gfp_t gfp,
407	unsigned long *handle)
408	{
409	*handle = zs_malloc(pool, size, gfp);
410	return *handle ? 0 : -1;
411	}
412	static void zs_zpool_free(void *pool, unsigned long handle)
413	{
414	zs_free(pool, handle);
415	}
416
417	static int zs_zpool_shrink(void *pool, unsigned int pages,
418	unsigned int *reclaimed)
419	{
420	return -EINVAL;
421	}
422
423	static void *zs_zpool_map(void *pool, unsigned long handle,
424	enum zpool_mapmode mm)
425	{
426	enum zs_mapmode zs_mm;
427
428	switch (mm) {
429	case ZPOOL_MM_RO:
430	zs_mm = ZS_MM_RO;
431	break;
432	case ZPOOL_MM_WO:
433	zs_mm = ZS_MM_WO;
434	break;
435	case ZPOOL_MM_RW: /* fallthru */
436	default:
437	zs_mm = ZS_MM_RW;
438	break;
439	}
440
441	return zs_map_object(pool, handle, zs_mm);
442	}
443	static void zs_zpool_unmap(void *pool, unsigned long handle)
444	{
445	zs_unmap_object(pool, handle);
446	}
447
448	static u64 zs_zpool_total_size(void *pool)
449	{
450	return zs_get_total_pages(pool) << PAGE_SHIFT;
451	}
452
453	static struct zpool_driver zs_zpool_driver = {
454	.type = "zsmalloc",
455	.owner = THIS_MODULE,
456	.create = zs_zpool_create,
457	.destroy = zs_zpool_destroy,
458	.malloc = zs_zpool_malloc,
459	.free = zs_zpool_free,
460	.shrink = zs_zpool_shrink,
461	.map = zs_zpool_map,
462	.unmap = zs_zpool_unmap,
463	.total_size = zs_zpool_total_size,
464	};
465
466	MODULE_ALIAS("zpool-zsmalloc");
467	#endif /* CONFIG_ZPOOL */
468
469	/* per-cpu VM mapping areas for zspage accesses that cross page boundaries */
470	static DEFINE_PER_CPU(struct mapping_area, zs_map_area);
471
472	static bool is_zspage_isolated(struct zspage *zspage)
473	{
474	return zspage->isolated;
475	}
476
477	static __maybe_unused int is_first_page(struct page *page)
478	{
479	return PagePrivate(page);
480	}
481
482	/* Protected by class->lock */
483	static inline int get_zspage_inuse(struct zspage *zspage)
484	{
485	return zspage->inuse;
486	}
487
488	static inline void set_zspage_inuse(struct zspage *zspage, int val)
489	{
490	zspage->inuse = val;
491	}
492
493	static inline void mod_zspage_inuse(struct zspage *zspage, int val)
494	{
495	zspage->inuse += val;
496	}
497
498	static inline struct page *get_first_page(struct zspage *zspage)
499	{
500	struct page *first_page = zspage->first_page;
501
502	VM_BUG_ON_PAGE(!is_first_page(first_page), first_page);
503	return first_page;
504	}
505
506	static inline int get_first_obj_offset(struct page *page)
507	{
508	return page->units;
509	}
510
511	static inline void set_first_obj_offset(struct page *page, int offset)
512	{
513	page->units = offset;
514	}
515
516	static inline unsigned int get_freeobj(struct zspage *zspage)
517	{
518	return zspage->freeobj;
519	}
520
521	static inline void set_freeobj(struct zspage *zspage, unsigned int obj)
522	{
523	zspage->freeobj = obj;
524	}
525
526	static void get_zspage_mapping(struct zspage *zspage,
527	unsigned int *class_idx,
528	enum fullness_group *fullness)
529	{
530	BUG_ON(zspage->magic != ZSPAGE_MAGIC);
531
532	*fullness = zspage->fullness;
533	*class_idx = zspage->class;
534	}
535
536	static void set_zspage_mapping(struct zspage *zspage,
537	unsigned int class_idx,
538	enum fullness_group fullness)
539	{
540	zspage->class = class_idx;
541	zspage->fullness = fullness;
542	}
543
544	/*
545	* zsmalloc divides the pool into various size classes where each
546	* class maintains a list of zspages where each zspage is divided
547	* into equal sized chunks. Each allocation falls into one of these
548	* classes depending on its size. This function returns index of the
549	* size class which has chunk size big enough to hold the give size.
550	*/
551	static int get_size_class_index(int size)
552	{
553	int idx = 0;
554
555	if (likely(size > ZS_MIN_ALLOC_SIZE))
556	idx = DIV_ROUND_UP(size - ZS_MIN_ALLOC_SIZE,
557	ZS_SIZE_CLASS_DELTA);
558
559	return min(zs_size_classes - 1, idx);
560	}
561
562	/* type can be of enum type zs_stat_type or fullness_group */
563	static inline void zs_stat_inc(struct size_class *class,
564	int type, unsigned long cnt)
565	{
566	class->stats.objs[type] += cnt;
567	}
568
569	/* type can be of enum type zs_stat_type or fullness_group */
570	static inline void zs_stat_dec(struct size_class *class,
571	int type, unsigned long cnt)
572	{
573	class->stats.objs[type] -= cnt;
574	}
575
576	/* type can be of enum type zs_stat_type or fullness_group */
577	static inline unsigned long zs_stat_get(struct size_class *class,
578	int type)
579	{
580	return class->stats.objs[type];
581	}
582
583	#ifdef CONFIG_ZSMALLOC_STAT
584
585	static void __init zs_stat_init(void)
586	{
587	if (!debugfs_initialized()) {
588	pr_warn("debugfs not available, stat dir not created\n");
589	return;
590	}
591
592	zs_stat_root = debugfs_create_dir("zsmalloc", NULL);
593	if (!zs_stat_root)
594	pr_warn("debugfs 'zsmalloc' stat dir creation failed\n");
595	}
596
597	static void __exit zs_stat_exit(void)
598	{
599	debugfs_remove_recursive(zs_stat_root);
600	}
601
602	static unsigned long zs_can_compact(struct size_class *class);
603
604	static int zs_stats_size_show(struct seq_file *s, void *v)
605	{
606	int i;
607	struct zs_pool *pool = s->private;
608	struct size_class *class;
609	int objs_per_zspage;
610	unsigned long class_almost_full, class_almost_empty;
611	unsigned long obj_allocated, obj_used, pages_used, freeable;
612	unsigned long total_class_almost_full = 0, total_class_almost_empty = 0;
613	unsigned long total_objs = 0, total_used_objs = 0, total_pages = 0;
614	unsigned long total_freeable = 0;
615
616	seq_printf(s, " %5s %5s %11s %12s %13s %10s %10s %16s %8s\n",
617	"class", "size", "almost_full", "almost_empty",
618	"obj_allocated", "obj_used", "pages_used",
619	"pages_per_zspage", "freeable");
620
621	for (i = 0; i < zs_size_classes; i++) {
622	class = pool->size_class[i];
623
624	if (class->index != i)
625	continue;
626
627	spin_lock(&class->lock);
628	class_almost_full = zs_stat_get(class, CLASS_ALMOST_FULL);
629	class_almost_empty = zs_stat_get(class, CLASS_ALMOST_EMPTY);
630	obj_allocated = zs_stat_get(class, OBJ_ALLOCATED);
631	obj_used = zs_stat_get(class, OBJ_USED);
632	freeable = zs_can_compact(class);
633	spin_unlock(&class->lock);
634
635	objs_per_zspage = class->objs_per_zspage;
636	pages_used = obj_allocated / objs_per_zspage *
637	class->pages_per_zspage;
638
639	seq_printf(s, " %5u %5u %11lu %12lu %13lu"
640	" %10lu %10lu %16d %8lu\n",
641	i, class->size, class_almost_full, class_almost_empty,
642	obj_allocated, obj_used, pages_used,
643	class->pages_per_zspage, freeable);
644
645	total_class_almost_full += class_almost_full;
646	total_class_almost_empty += class_almost_empty;
647	total_objs += obj_allocated;
648	total_used_objs += obj_used;
649	total_pages += pages_used;
650	total_freeable += freeable;
651	}
652
653	seq_puts(s, "\n");
654	seq_printf(s, " %5s %5s %11lu %12lu %13lu %10lu %10lu %16s %8lu\n",
655	"Total", "", total_class_almost_full,
656	total_class_almost_empty, total_objs,
657	total_used_objs, total_pages, "", total_freeable);
658
659	return 0;
660	}
661
662	static int zs_stats_size_open(struct inode *inode, struct file *file)
663	{
664	return single_open(file, zs_stats_size_show, inode->i_private);
665	}
666
667	static const struct file_operations zs_stat_size_ops = {
668	.open = zs_stats_size_open,
669	.read = seq_read,
670	.llseek = seq_lseek,
671	.release = single_release,
672	};
673
674	static void zs_pool_stat_create(struct zs_pool *pool, const char *name)
675	{
676	struct dentry *entry;
677
678	if (!zs_stat_root) {
679	pr_warn("no root stat dir, not creating <%s> stat dir\n", name);
680	return;
681	}
682
683	entry = debugfs_create_dir(name, zs_stat_root);
684	if (!entry) {
685	pr_warn("debugfs dir <%s> creation failed\n", name);
686	return;
687	}
688	pool->stat_dentry = entry;
689
690	entry = debugfs_create_file("classes", S_IFREG | S_IRUGO,
691	pool->stat_dentry, pool, &zs_stat_size_ops);
692	if (!entry) {
693	pr_warn("%s: debugfs file entry <%s> creation failed\n",
694	name, "classes");
695	debugfs_remove_recursive(pool->stat_dentry);
696	pool->stat_dentry = NULL;
697	}
698	}
699
700	static void zs_pool_stat_destroy(struct zs_pool *pool)
701	{
702	debugfs_remove_recursive(pool->stat_dentry);
703	}
704
705	#else /* CONFIG_ZSMALLOC_STAT */
706	static void __init zs_stat_init(void)
707	{
708	}
709
710	static void __exit zs_stat_exit(void)
711	{
712	}
713
714	static inline void zs_pool_stat_create(struct zs_pool *pool, const char *name)
715	{
716	}
717
718	static inline void zs_pool_stat_destroy(struct zs_pool *pool)
719	{
720	}
721	#endif
722
723
724	/*
725	* For each size class, zspages are divided into different groups
726	* depending on how "full" they are. This was done so that we could
727	* easily find empty or nearly empty zspages when we try to shrink
728	* the pool (not yet implemented). This function returns fullness
729	* status of the given page.
730	*/
731	static enum fullness_group get_fullness_group(struct size_class *class,
732	struct zspage *zspage)
733	{
734	int inuse, objs_per_zspage;
735	enum fullness_group fg;
736
737	inuse = get_zspage_inuse(zspage);
738	objs_per_zspage = class->objs_per_zspage;
739
740	if (inuse == 0)
741	fg = ZS_EMPTY;
742	else if (inuse == objs_per_zspage)
743	fg = ZS_FULL;
744	else if (inuse <= 3 * objs_per_zspage / fullness_threshold_frac)
745	fg = ZS_ALMOST_EMPTY;
746	else
747	fg = ZS_ALMOST_FULL;
748
749	return fg;
750	}
751
752	/*
753	* Each size class maintains various freelists and zspages are assigned
754	* to one of these freelists based on the number of live objects they
755	* have. This functions inserts the given zspage into the freelist
756	* identified by <class, fullness_group>.
757	*/
758	static void insert_zspage(struct size_class *class,
759	struct zspage *zspage,
760	enum fullness_group fullness)
761	{
762	struct zspage *head;
763
764	zs_stat_inc(class, fullness, 1);
765	head = list_first_entry_or_null(&class->fullness_list[fullness],
766	struct zspage, list);
767	/*
768	* We want to see more ZS_FULL pages and less almost empty/full.
769	* Put pages with higher ->inuse first.
770	*/
771	if (head) {
772	if (get_zspage_inuse(zspage) < get_zspage_inuse(head)) {
773	list_add(&zspage->list, &head->list);
774	return;
775	}
776	}
777	list_add(&zspage->list, &class->fullness_list[fullness]);
778	}
779
780	/*
781	* This function removes the given zspage from the freelist identified
782	* by <class, fullness_group>.
783	*/
784	static void remove_zspage(struct size_class *class,
785	struct zspage *zspage,
786	enum fullness_group fullness)
787	{
788	VM_BUG_ON(list_empty(&class->fullness_list[fullness]));
789	VM_BUG_ON(is_zspage_isolated(zspage));
790
791	list_del_init(&zspage->list);
792	zs_stat_dec(class, fullness, 1);
793	}
794
795	/*
796	* Each size class maintains zspages in different fullness groups depending
797	* on the number of live objects they contain. When allocating or freeing
798	* objects, the fullness status of the page can change, say, from ALMOST_FULL
799	* to ALMOST_EMPTY when freeing an object. This function checks if such
800	* a status change has occurred for the given page and accordingly moves the
801	* page from the freelist of the old fullness group to that of the new
802	* fullness group.
803	*/
804	static enum fullness_group fix_fullness_group(struct size_class *class,
805	struct zspage *zspage)
806	{
807	int class_idx;
808	enum fullness_group currfg, newfg;
809
810	get_zspage_mapping(zspage, &class_idx, &currfg);
811	newfg = get_fullness_group(class, zspage);
812	if (newfg == currfg)
813	goto out;
814
815	if (!is_zspage_isolated(zspage)) {
816	remove_zspage(class, zspage, currfg);
817	insert_zspage(class, zspage, newfg);
818	}
819
820	set_zspage_mapping(zspage, class_idx, newfg);
821
822	out:
823	return newfg;
824	}
825
826	/*
827	* We have to decide on how many pages to link together
828	* to form a zspage for each size class. This is important
829	* to reduce wastage due to unusable space left at end of
830	* each zspage which is given as:
831	* wastage = Zp % class_size
832	* usage = Zp - wastage
833	* where Zp = zspage size = k * PAGE_SIZE where k = 1, 2, ...
834	*
835	* For example, for size class of 3/8 * PAGE_SIZE, we should
836	* link together 3 PAGE_SIZE sized pages to form a zspage
837	* since then we can perfectly fit in 8 such objects.
838	*/
839	static int get_pages_per_zspage(int class_size)
840	{
841	int i, max_usedpc = 0;
842	/* zspage order which gives maximum used size per KB */
843	int max_usedpc_order = 1;
844
845	for (i = 1; i <= ZS_MAX_PAGES_PER_ZSPAGE; i++) {
846	int zspage_size;
847	int waste, usedpc;
848
849	zspage_size = i * PAGE_SIZE;
850	waste = zspage_size % class_size;
851	usedpc = (zspage_size - waste) * 100 / zspage_size;
852
853	if (usedpc > max_usedpc) {
854	max_usedpc = usedpc;
855	max_usedpc_order = i;
856	}
857	}
858
859	return max_usedpc_order;
860	}
861
862	static struct zspage *get_zspage(struct page *page)
863	{
864	struct zspage *zspage = (struct zspage *)page->private;
865
866	BUG_ON(zspage->magic != ZSPAGE_MAGIC);
867	return zspage;
868	}
869
870	static struct page *get_next_page(struct page *page)
871	{
872	if (unlikely(PageHugeObject(page)))
873	return NULL;
874
875	return page->freelist;
876	}
877
878	/**
879	* obj_to_location - get (<page>, <obj_idx>) from encoded object value
880	* @page: page object resides in zspage
881	* @obj_idx: object index
882	*/
883	static void obj_to_location(unsigned long obj, struct page **page,
884	unsigned int *obj_idx)
885	{
886	obj >>= OBJ_TAG_BITS;
887	*page = pfn_to_page(obj >> OBJ_INDEX_BITS);
888	*obj_idx = (obj & OBJ_INDEX_MASK);
889	}
890
891	/**
892	* location_to_obj - get obj value encoded from (<page>, <obj_idx>)
893	* @page: page object resides in zspage
894	* @obj_idx: object index
895	*/
896	static unsigned long location_to_obj(struct page *page, unsigned int obj_idx)
897	{
898	unsigned long obj;
899
900	obj = page_to_pfn(page) << OBJ_INDEX_BITS;
901	obj |= obj_idx & OBJ_INDEX_MASK;
902	obj <<= OBJ_TAG_BITS;
903
904	return obj;
905	}
906
907	static unsigned long handle_to_obj(unsigned long handle)
908	{
909	return *(unsigned long *)handle;
910	}
911
912	static unsigned long obj_to_head(struct page *page, void *obj)
913	{
914	if (unlikely(PageHugeObject(page))) {
915	VM_BUG_ON_PAGE(!is_first_page(page), page);
916	return page->index;
917	} else
918	return *(unsigned long *)obj;
919	}
920
921	static inline int testpin_tag(unsigned long handle)
922	{
923	return bit_spin_is_locked(HANDLE_PIN_BIT, (unsigned long *)handle);
924	}
925
926	static inline int trypin_tag(unsigned long handle)
927	{
928	return bit_spin_trylock(HANDLE_PIN_BIT, (unsigned long *)handle);
929	}
930
931	static void pin_tag(unsigned long handle)
932	{
933	bit_spin_lock(HANDLE_PIN_BIT, (unsigned long *)handle);
934	}
935
936	static void unpin_tag(unsigned long handle)
937	{
938	bit_spin_unlock(HANDLE_PIN_BIT, (unsigned long *)handle);
939	}
940
941	static void reset_page(struct page *page)
942	{
943	__ClearPageMovable(page);
944	ClearPagePrivate(page);
945	ClearPagePrivate2(page);
946	set_page_private(page, 0);
947	page_mapcount_reset(page);
948	ClearPageHugeObject(page);
949	page->freelist = NULL;
950	}
951
952	/*
953	* To prevent zspage destroy during migration, zspage freeing should
954	* hold locks of all pages in the zspage.
955	*/
956	void lock_zspage(struct zspage *zspage)
957	{
958	struct page *page = get_first_page(zspage);
959
960	do {
961	lock_page(page);
962	} while ((page = get_next_page(page)) != NULL);
963	}
964
965	int trylock_zspage(struct zspage *zspage)
966	{
967	struct page *cursor, *fail;
968
969	for (cursor = get_first_page(zspage); cursor != NULL; cursor =
970	get_next_page(cursor)) {
971	if (!trylock_page(cursor)) {
972	fail = cursor;
973	goto unlock;
974	}
975	}
976
977	return 1;
978	unlock:
979	for (cursor = get_first_page(zspage); cursor != fail; cursor =
980	get_next_page(cursor))
981	unlock_page(cursor);
982
983	return 0;
984	}
985
986	static void __free_zspage(struct zs_pool *pool, struct size_class *class,
987	struct zspage *zspage)
988	{
989	struct page *page, *next;
990	enum fullness_group fg;
991	unsigned int class_idx;
992
993	get_zspage_mapping(zspage, &class_idx, &fg);
994
995	assert_spin_locked(&class->lock);
996
997	VM_BUG_ON(get_zspage_inuse(zspage));
998	VM_BUG_ON(fg != ZS_EMPTY);
999
1000	next = page = get_first_page(zspage);
1001	do {
1002	VM_BUG_ON_PAGE(!PageLocked(page), page);
1003	next = get_next_page(page);
1004	reset_page(page);
1005	unlock_page(page);
1006	dec_zone_page_state(page, NR_ZSPAGES);
1007	put_page(page);
1008	page = next;
1009	} while (page != NULL);
1010
1011	cache_free_zspage(pool, zspage);
1012
1013	zs_stat_dec(class, OBJ_ALLOCATED, class->objs_per_zspage);
1014	atomic_long_sub(class->pages_per_zspage,
1015	&pool->pages_allocated);
1016	}
1017
1018	static void free_zspage(struct zs_pool *pool, struct size_class *class,
1019	struct zspage *zspage)
1020	{
1021	VM_BUG_ON(get_zspage_inuse(zspage));
1022	VM_BUG_ON(list_empty(&zspage->list));
1023
1024	if (!trylock_zspage(zspage)) {
1025	kick_deferred_free(pool);
1026	return;
1027	}
1028
1029	remove_zspage(class, zspage, ZS_EMPTY);
1030	__free_zspage(pool, class, zspage);
1031	}
1032
1033	/* Initialize a newly allocated zspage */
1034	static void init_zspage(struct size_class *class, struct zspage *zspage)
1035	{
1036	unsigned int freeobj = 1;
1037	unsigned long off = 0;
1038	struct page *page = get_first_page(zspage);
1039
1040	while (page) {
1041	struct page *next_page;
1042	struct link_free *link;
1043	void *vaddr;
1044
1045	set_first_obj_offset(page, off);
1046
1047	vaddr = kmap_atomic(page);
1048	link = (struct link_free *)vaddr + off / sizeof(*link);
1049
1050	while ((off += class->size) < PAGE_SIZE) {
1051	link->next = freeobj++ << OBJ_TAG_BITS;
1052	link += class->size / sizeof(*link);
1053	}
1054
1055	/*
1056	* We now come to the last (full or partial) object on this
1057	* page, which must point to the first object on the next
1058	* page (if present)
1059	*/
1060	next_page = get_next_page(page);
1061	if (next_page) {
1062	link->next = freeobj++ << OBJ_TAG_BITS;
1063	} else {
1064	/*
1065	* Reset OBJ_TAG_BITS bit to last link to tell
1066	* whether it's allocated object or not.
1067	*/
1068	link->next = -1 << OBJ_TAG_BITS;
1069	}
1070	kunmap_atomic(vaddr);
1071	page = next_page;
1072	off %= PAGE_SIZE;
1073	}
1074
1075	set_freeobj(zspage, 0);
1076	}
1077
1078	static void create_page_chain(struct size_class *class, struct zspage *zspage,
1079	struct page *pages[])
1080	{
1081	int i;
1082	struct page *page;
1083	struct page *prev_page = NULL;
1084	int nr_pages = class->pages_per_zspage;
1085
1086	/*
1087	* Allocate individual pages and link them together as:
1088	* 1. all pages are linked together using page->freelist
1089	* 2. each sub-page point to zspage using page->private
1090	*
1091	* we set PG_private to identify the first page (i.e. no other sub-page
1092	* has this flag set) and PG_private_2 to identify the last page.
1093	*/
1094	for (i = 0; i < nr_pages; i++) {
1095	page = pages[i];
1096	set_page_private(page, (unsigned long)zspage);
1097	page->freelist = NULL;
1098	if (i == 0) {
1099	zspage->first_page = page;
1100	SetPagePrivate(page);
1101	if (unlikely(class->objs_per_zspage == 1 &&
1102	class->pages_per_zspage == 1))
1103	SetPageHugeObject(page);
1104	} else {
1105	prev_page->freelist = page;
1106	}
1107	if (i == nr_pages - 1)
1108	SetPagePrivate2(page);
1109	prev_page = page;
1110	}
1111	}
1112
1113	/*
1114	* Allocate a zspage for the given size class
1115	*/
1116	static struct zspage *alloc_zspage(struct zs_pool *pool,
1117	struct size_class *class,
1118	gfp_t gfp)
1119	{
1120	int i;
1121	struct page *pages[ZS_MAX_PAGES_PER_ZSPAGE];
1122	struct zspage *zspage = cache_alloc_zspage(pool, gfp);
1123
1124	if (!zspage)
1125	return NULL;
1126
1127	memset(zspage, 0, sizeof(struct zspage));
1128	zspage->magic = ZSPAGE_MAGIC;
1129	migrate_lock_init(zspage);
1130
1131	for (i = 0; i < class->pages_per_zspage; i++) {
1132	struct page *page;
1133
1134	page = alloc_page(gfp);
1135	if (!page) {
1136	while (--i >= 0) {
1137	dec_zone_page_state(pages[i], NR_ZSPAGES);
1138	__free_page(pages[i]);
1139	}
1140	cache_free_zspage(pool, zspage);
1141	return NULL;
1142	}
1143
1144	inc_zone_page_state(page, NR_ZSPAGES);
1145	pages[i] = page;
1146	}
1147
1148	create_page_chain(class, zspage, pages);
1149	init_zspage(class, zspage);
1150
1151	return zspage;
1152	}
1153
1154	static struct zspage *find_get_zspage(struct size_class *class)
1155	{
1156	int i;
1157	struct zspage *zspage;
1158
1159	for (i = ZS_ALMOST_FULL; i >= ZS_EMPTY; i--) {
1160	zspage = list_first_entry_or_null(&class->fullness_list[i],
1161	struct zspage, list);
1162	if (zspage)
1163	break;
1164	}
1165
1166	return zspage;
1167	}
1168
1169	#ifdef CONFIG_PGTABLE_MAPPING
1170	static inline int __zs_cpu_up(struct mapping_area *area)
1171	{
1172	/*
1173	* Make sure we don't leak memory if a cpu UP notification
1174	* and zs_init() race and both call zs_cpu_up() on the same cpu
1175	*/
1176	if (area->vm)
1177	return 0;
1178	area->vm = alloc_vm_area(PAGE_SIZE * 2, NULL);
1179	if (!area->vm)
1180	return -ENOMEM;
1181	return 0;
1182	}
1183
1184	static inline void __zs_cpu_down(struct mapping_area *area)
1185	{
1186	if (area->vm)
1187	free_vm_area(area->vm);
1188	area->vm = NULL;
1189	}
1190
1191	static inline void *__zs_map_object(struct mapping_area *area,
1192	struct page *pages[2], int off, int size)
1193	{
1194	BUG_ON(map_vm_area(area->vm, PAGE_KERNEL, pages));
1195	area->vm_addr = area->vm->addr;
1196	return area->vm_addr + off;
1197	}
1198
1199	static inline void __zs_unmap_object(struct mapping_area *area,
1200	struct page *pages[2], int off, int size)
1201	{
1202	unsigned long addr = (unsigned long)area->vm_addr;
1203
1204	unmap_kernel_range(addr, PAGE_SIZE * 2);
1205	}
1206
1207	#else /* CONFIG_PGTABLE_MAPPING */
1208
1209	static inline int __zs_cpu_up(struct mapping_area *area)
1210	{
1211	/*
1212	* Make sure we don't leak memory if a cpu UP notification
1213	* and zs_init() race and both call zs_cpu_up() on the same cpu
1214	*/
1215	if (area->vm_buf)
1216	return 0;
1217	area->vm_buf = kmalloc(ZS_MAX_ALLOC_SIZE, GFP_KERNEL);
1218	if (!area->vm_buf)
1219	return -ENOMEM;
1220	return 0;
1221	}
1222
1223	static inline void __zs_cpu_down(struct mapping_area *area)
1224	{
1225	kfree(area->vm_buf);
1226	area->vm_buf = NULL;
1227	}
1228
1229	static void *__zs_map_object(struct mapping_area *area,
1230	struct page *pages[2], int off, int size)
1231	{
1232	int sizes[2];
1233	void *addr;
1234	char *buf = area->vm_buf;
1235
1236	/* disable page faults to match kmap_atomic() return conditions */
1237	pagefault_disable();
1238
1239	/* no read fastpath */
1240	if (area->vm_mm == ZS_MM_WO)
1241	goto out;
1242
1243	sizes[0] = PAGE_SIZE - off;
1244	sizes[1] = size - sizes[0];
1245
1246	/* copy object to per-cpu buffer */
1247	addr = kmap_atomic(pages[0]);
1248	memcpy(buf, addr + off, sizes[0]);
1249	kunmap_atomic(addr);
1250	addr = kmap_atomic(pages[1]);
1251	memcpy(buf + sizes[0], addr, sizes[1]);
1252	kunmap_atomic(addr);
1253	out:
1254	return area->vm_buf;
1255	}
1256
1257	static void __zs_unmap_object(struct mapping_area *area,
1258	struct page *pages[2], int off, int size)
1259	{
1260	int sizes[2];
1261	void *addr;
1262	char *buf;
1263
1264	/* no write fastpath */
1265	if (area->vm_mm == ZS_MM_RO)
1266	goto out;
1267
1268	buf = area->vm_buf;
1269	buf = buf + ZS_HANDLE_SIZE;
1270	size -= ZS_HANDLE_SIZE;
1271	off += ZS_HANDLE_SIZE;
1272
1273	sizes[0] = PAGE_SIZE - off;
1274	sizes[1] = size - sizes[0];
1275
1276	/* copy per-cpu buffer to object */
1277	addr = kmap_atomic(pages[0]);
1278	memcpy(addr + off, buf, sizes[0]);
1279	kunmap_atomic(addr);
1280	addr = kmap_atomic(pages[1]);
1281	memcpy(addr, buf + sizes[0], sizes[1]);
1282	kunmap_atomic(addr);
1283
1284	out:
1285	/* enable page faults to match kunmap_atomic() return conditions */
1286	pagefault_enable();
1287	}
1288
1289	#endif /* CONFIG_PGTABLE_MAPPING */
1290
1291	static int zs_cpu_notifier(struct notifier_block *nb, unsigned long action,
1292	void *pcpu)
1293	{
1294	int ret, cpu = (long)pcpu;
1295	struct mapping_area *area;
1296
1297	switch (action) {
1298	case CPU_UP_PREPARE:
1299	area = &per_cpu(zs_map_area, cpu);
1300	ret = __zs_cpu_up(area);
1301	if (ret)
1302	return notifier_from_errno(ret);
1303	break;
1304	case CPU_DEAD:
1305	case CPU_UP_CANCELED:
1306	area = &per_cpu(zs_map_area, cpu);
1307	__zs_cpu_down(area);
1308	break;
1309	}
1310
1311	return NOTIFY_OK;
1312	}
1313
1314	static struct notifier_block zs_cpu_nb = {
1315	.notifier_call = zs_cpu_notifier
1316	};
1317
1318	static int zs_register_cpu_notifier(void)
1319	{
1320	int cpu, uninitialized_var(ret);
1321
1322	cpu_notifier_register_begin();
1323
1324	__register_cpu_notifier(&zs_cpu_nb);
1325	for_each_online_cpu(cpu) {
1326	ret = zs_cpu_notifier(NULL, CPU_UP_PREPARE, (void *)(long)cpu);
1327	if (notifier_to_errno(ret))
1328	break;
1329	}
1330
1331	cpu_notifier_register_done();
1332	return notifier_to_errno(ret);
1333	}
1334
1335	static void zs_unregister_cpu_notifier(void)
1336	{
1337	int cpu;
1338
1339	cpu_notifier_register_begin();
1340
1341	for_each_online_cpu(cpu)
1342	zs_cpu_notifier(NULL, CPU_DEAD, (void *)(long)cpu);
1343	__unregister_cpu_notifier(&zs_cpu_nb);
1344
1345	cpu_notifier_register_done();
1346	}
1347
1348	static void __init init_zs_size_classes(void)
1349	{
1350	int nr;
1351
1352	nr = (ZS_MAX_ALLOC_SIZE - ZS_MIN_ALLOC_SIZE) / ZS_SIZE_CLASS_DELTA + 1;
1353	if ((ZS_MAX_ALLOC_SIZE - ZS_MIN_ALLOC_SIZE) % ZS_SIZE_CLASS_DELTA)
1354	nr += 1;
1355
1356	zs_size_classes = nr;
1357	}
1358
1359	static bool can_merge(struct size_class *prev, int pages_per_zspage,
1360	int objs_per_zspage)
1361	{
1362	if (prev->pages_per_zspage == pages_per_zspage &&
1363	prev->objs_per_zspage == objs_per_zspage)
1364	return true;
1365
1366	return false;
1367	}
1368
1369	static bool zspage_full(struct size_class *class, struct zspage *zspage)
1370	{
1371	return get_zspage_inuse(zspage) == class->objs_per_zspage;
1372	}
1373
1374	unsigned long zs_get_total_pages(struct zs_pool *pool)
1375	{
1376	return atomic_long_read(&pool->pages_allocated);
1377	}
1378	EXPORT_SYMBOL_GPL(zs_get_total_pages);
1379
1380	/**
1381	* zs_map_object - get address of allocated object from handle.
1382	* @pool: pool from which the object was allocated
1383	* @handle: handle returned from zs_malloc
1384	*
1385	* Before using an object allocated from zs_malloc, it must be mapped using
1386	* this function. When done with the object, it must be unmapped using
1387	* zs_unmap_object.
1388	*
1389	* Only one object can be mapped per cpu at a time. There is no protection
1390	* against nested mappings.
1391	*
1392	* This function returns with preemption and page faults disabled.
1393	*/
1394	void *zs_map_object(struct zs_pool *pool, unsigned long handle,
1395	enum zs_mapmode mm)
1396	{
1397	struct zspage *zspage;
1398	struct page *page;
1399	unsigned long obj, off;
1400	unsigned int obj_idx;
1401
1402	unsigned int class_idx;
1403	enum fullness_group fg;
1404	struct size_class *class;
1405	struct mapping_area *area;
1406	struct page *pages[2];
1407	void *ret;
1408
1409	/*
1410	* Because we use per-cpu mapping areas shared among the
1411	* pools/users, we can't allow mapping in interrupt context
1412	* because it can corrupt another users mappings.
1413	*/
1414	BUG_ON(in_interrupt());
1415
1416	/* From now on, migration cannot move the object */
1417	pin_tag(handle);
1418
1419	obj = handle_to_obj(handle);
1420	obj_to_location(obj, &page, &obj_idx);
1421	zspage = get_zspage(page);
1422
1423	/* migration cannot move any subpage in this zspage */
1424	migrate_read_lock(zspage);
1425
1426	get_zspage_mapping(zspage, &class_idx, &fg);
1427	class = pool->size_class[class_idx];
1428	off = (class->size * obj_idx) & ~PAGE_MASK;
1429
1430	area = &get_cpu_var(zs_map_area);
1431	area->vm_mm = mm;
1432	if (off + class->size <= PAGE_SIZE) {
1433	/* this object is contained entirely within a page */
1434	area->vm_addr = kmap_atomic(page);
1435	ret = area->vm_addr + off;
1436	goto out;
1437	}
1438
1439	/* this object spans two pages */
1440	pages[0] = page;
1441	pages[1] = get_next_page(page);
1442	BUG_ON(!pages[1]);
1443
1444	ret = __zs_map_object(area, pages, off, class->size);
1445	out:
1446	if (likely(!PageHugeObject(page)))
1447	ret += ZS_HANDLE_SIZE;
1448
1449	return ret;
1450	}
1451	EXPORT_SYMBOL_GPL(zs_map_object);
1452
1453	void zs_unmap_object(struct zs_pool *pool, unsigned long handle)
1454	{
1455	struct zspage *zspage;
1456	struct page *page;
1457	unsigned long obj, off;
1458	unsigned int obj_idx;
1459
1460	unsigned int class_idx;
1461	enum fullness_group fg;
1462	struct size_class *class;
1463	struct mapping_area *area;
1464
1465	obj = handle_to_obj(handle);
1466	obj_to_location(obj, &page, &obj_idx);
1467	zspage = get_zspage(page);
1468	get_zspage_mapping(zspage, &class_idx, &fg);
1469	class = pool->size_class[class_idx];
1470	off = (class->size * obj_idx) & ~PAGE_MASK;
1471
1472	area = this_cpu_ptr(&zs_map_area);
1473	if (off + class->size <= PAGE_SIZE)
1474	kunmap_atomic(area->vm_addr);
1475	else {
1476	struct page *pages[2];
1477
1478	pages[0] = page;
1479	pages[1] = get_next_page(page);
1480	BUG_ON(!pages[1]);
1481
1482	__zs_unmap_object(area, pages, off, class->size);
1483	}
1484	put_cpu_var(zs_map_area);
1485
1486	migrate_read_unlock(zspage);
1487	unpin_tag(handle);
1488	}
1489	EXPORT_SYMBOL_GPL(zs_unmap_object);
1490
1491	/**
1492	* zs_huge_class_size() - Returns the size (in bytes) of the first huge
1493	* zsmalloc &size_class.
1494	* @pool: zsmalloc pool to use
1495	*
1496	* The function returns the size of the first huge class - any object of equal
1497	* or bigger size will be stored in zspage consisting of a single physical
1498	* page.
1499	*
1500	* Context: Any context.
1501	*
1502	* Return: the size (in bytes) of the first huge zsmalloc &size_class.
1503	*/
1504	size_t zs_huge_class_size(struct zs_pool *pool)
1505	{
1506	return huge_class_size;
1507	}
1508	EXPORT_SYMBOL_GPL(zs_huge_class_size);
1509
1510	static unsigned long obj_malloc(struct size_class *class,
1511	struct zspage *zspage, unsigned long handle)
1512	{
1513	int i, nr_page, offset;
1514	unsigned long obj;
1515	struct link_free *link;
1516
1517	struct page *m_page;
1518	unsigned long m_offset;
1519	void *vaddr;
1520
1521	handle |= OBJ_ALLOCATED_TAG;
1522	obj = get_freeobj(zspage);
1523
1524	offset = obj * class->size;
1525	nr_page = offset >> PAGE_SHIFT;
1526	m_offset = offset & ~PAGE_MASK;
1527	m_page = get_first_page(zspage);
1528
1529	for (i = 0; i < nr_page; i++)
1530	m_page = get_next_page(m_page);
1531
1532	vaddr = kmap_atomic(m_page);
1533	link = (struct link_free *)vaddr + m_offset / sizeof(*link);
1534	set_freeobj(zspage, link->next >> OBJ_TAG_BITS);
1535	if (likely(!PageHugeObject(m_page)))
1536	/* record handle in the header of allocated chunk */
1537	link->handle = handle;
1538	else
1539	/* record handle to page->index */
1540	zspage->first_page->index = handle;
1541
1542	kunmap_atomic(vaddr);
1543	mod_zspage_inuse(zspage, 1);
1544	zs_stat_inc(class, OBJ_USED, 1);
1545
1546	obj = location_to_obj(m_page, obj);
1547
1548	return obj;
1549	}
1550
1551
1552	/**
1553	* zs_malloc - Allocate block of given size from pool.
1554	* @pool: pool to allocate from
1555	* @size: size of block to allocate
1556	* @gfp: gfp flags when allocating object
1557	*
1558	* On success, handle to the allocated object is returned,
1559	* otherwise 0.
1560	* Allocation requests with size > ZS_MAX_ALLOC_SIZE will fail.
1561	*/
1562	unsigned long zs_malloc(struct zs_pool *pool, size_t size, gfp_t gfp)
1563	{
1564	unsigned long handle, obj;
1565	struct size_class *class;
1566	enum fullness_group newfg;
1567	struct zspage *zspage;
1568
1569	if (unlikely(!size || size > ZS_MAX_ALLOC_SIZE))
1570	return 0;
1571
1572	handle = cache_alloc_handle(pool, gfp);
1573	if (!handle)
1574	return 0;
1575
1576	/* extra space in chunk to keep the handle */
1577	size += ZS_HANDLE_SIZE;
1578	class = pool->size_class[get_size_class_index(size)];
1579
1580	spin_lock(&class->lock);
1581	zspage = find_get_zspage(class);
1582	if (likely(zspage)) {
1583	obj = obj_malloc(class, zspage, handle);
1584	/* Now move the zspage to another fullness group, if required */
1585	fix_fullness_group(class, zspage);
1586	record_obj(handle, obj);
1587	spin_unlock(&class->lock);
1588
1589	return handle;
1590	}
1591
1592	spin_unlock(&class->lock);
1593
1594	zspage = alloc_zspage(pool, class, gfp);
1595	if (!zspage) {
1596	cache_free_handle(pool, handle);
1597	return 0;
1598	}
1599
1600	spin_lock(&class->lock);
1601	obj = obj_malloc(class, zspage, handle);
1602	newfg = get_fullness_group(class, zspage);
1603	insert_zspage(class, zspage, newfg);
1604	set_zspage_mapping(zspage, class->index, newfg);
1605	record_obj(handle, obj);
1606	atomic_long_add(class->pages_per_zspage,
1607	&pool->pages_allocated);
1608	zs_stat_inc(class, OBJ_ALLOCATED, class->objs_per_zspage);
1609
1610	/* We completely set up zspage so mark them as movable */
1611	SetZsPageMovable(pool, zspage);
1612	spin_unlock(&class->lock);
1613
1614	return handle;
1615	}
1616	EXPORT_SYMBOL_GPL(zs_malloc);
1617
1618	static void obj_free(struct size_class *class, unsigned long obj)
1619	{
1620	struct link_free *link;
1621	struct zspage *zspage;
1622	struct page *f_page;
1623	unsigned long f_offset;
1624	unsigned int f_objidx;
1625	void *vaddr;
1626
1627	obj &= ~OBJ_ALLOCATED_TAG;
1628	obj_to_location(obj, &f_page, &f_objidx);
1629	f_offset = (class->size * f_objidx) & ~PAGE_MASK;
1630	zspage = get_zspage(f_page);
1631
1632	vaddr = kmap_atomic(f_page);
1633
1634	/* Insert this object in containing zspage's freelist */
1635	link = (struct link_free *)(vaddr + f_offset);
1636	link->next = get_freeobj(zspage) << OBJ_TAG_BITS;
1637	kunmap_atomic(vaddr);
1638	set_freeobj(zspage, f_objidx);
1639	mod_zspage_inuse(zspage, -1);
1640	zs_stat_dec(class, OBJ_USED, 1);
1641	}
1642
1643	void zs_free(struct zs_pool *pool, unsigned long handle)
1644	{
1645	struct zspage *zspage;
1646	struct page *f_page;
1647	unsigned long obj;
1648	unsigned int f_objidx;
1649	int class_idx;
1650	struct size_class *class;
1651	enum fullness_group fullness;
1652	bool isolated;
1653
1654	if (unlikely(!handle))
1655	return;
1656
1657	pin_tag(handle);
1658	obj = handle_to_obj(handle);
1659	obj_to_location(obj, &f_page, &f_objidx);
1660	zspage = get_zspage(f_page);
1661
1662	migrate_read_lock(zspage);
1663
1664	get_zspage_mapping(zspage, &class_idx, &fullness);
1665	class = pool->size_class[class_idx];
1666
1667	spin_lock(&class->lock);
1668	obj_free(class, obj);
1669	fullness = fix_fullness_group(class, zspage);
1670	if (fullness != ZS_EMPTY) {
1671	migrate_read_unlock(zspage);
1672	goto out;
1673	}
1674
1675	isolated = is_zspage_isolated(zspage);
1676	migrate_read_unlock(zspage);
1677	/* If zspage is isolated, zs_page_putback will free the zspage */
1678	if (likely(!isolated))
1679	free_zspage(pool, class, zspage);
1680	out:
1681
1682	spin_unlock(&class->lock);
1683	unpin_tag(handle);
1684	cache_free_handle(pool, handle);
1685	}
1686	EXPORT_SYMBOL_GPL(zs_free);
1687
1688	static void zs_object_copy(struct size_class *class, unsigned long dst,
1689	unsigned long src)
1690	{
1691	struct page *s_page, *d_page;
1692	unsigned int s_objidx, d_objidx;
1693	unsigned long s_off, d_off;
1694	void *s_addr, *d_addr;
1695	int s_size, d_size, size;
1696	int written = 0;
1697
1698	s_size = d_size = class->size;
1699
1700	obj_to_location(src, &s_page, &s_objidx);
1701	obj_to_location(dst, &d_page, &d_objidx);
1702
1703	s_off = (class->size * s_objidx) & ~PAGE_MASK;
1704	d_off = (class->size * d_objidx) & ~PAGE_MASK;
1705
1706	if (s_off + class->size > PAGE_SIZE)
1707	s_size = PAGE_SIZE - s_off;
1708
1709	if (d_off + class->size > PAGE_SIZE)
1710	d_size = PAGE_SIZE - d_off;
1711
1712	s_addr = kmap_atomic(s_page);
1713	d_addr = kmap_atomic(d_page);
1714
1715	while (1) {
1716	size = min(s_size, d_size);
1717	memcpy(d_addr + d_off, s_addr + s_off, size);
1718	written += size;
1719
1720	if (written == class->size)
1721	break;
1722
1723	s_off += size;
1724	s_size -= size;
1725	d_off += size;
1726	d_size -= size;
1727
1728	if (s_off >= PAGE_SIZE) {
1729	kunmap_atomic(d_addr);
1730	kunmap_atomic(s_addr);
1731	s_page = get_next_page(s_page);
1732	s_addr = kmap_atomic(s_page);
1733	d_addr = kmap_atomic(d_page);
1734	s_size = class->size - written;
1735	s_off = 0;
1736	}
1737
1738	if (d_off >= PAGE_SIZE) {
1739	kunmap_atomic(d_addr);
1740	d_page = get_next_page(d_page);
1741	d_addr = kmap_atomic(d_page);
1742	d_size = class->size - written;
1743	d_off = 0;
1744	}
1745	}
1746
1747	kunmap_atomic(d_addr);
1748	kunmap_atomic(s_addr);
1749	}
1750
1751	/*
1752	* Find alloced object in zspage from index object and
1753	* return handle.
1754	*/
1755	static unsigned long find_alloced_obj(struct size_class *class,
1756	struct page *page, int *obj_idx)
1757	{
1758	unsigned long head;
1759	int offset = 0;
1760	int index = *obj_idx;
1761	unsigned long handle = 0;
1762	void *addr = kmap_atomic(page);
1763
1764	offset = get_first_obj_offset(page);
1765	offset += class->size * index;
1766
1767	while (offset < PAGE_SIZE) {
1768	head = obj_to_head(page, addr + offset);
1769	if (head & OBJ_ALLOCATED_TAG) {
1770	handle = head & ~OBJ_ALLOCATED_TAG;
1771	if (trypin_tag(handle))
1772	break;
1773	handle = 0;
1774	}
1775
1776	offset += class->size;
1777	index++;
1778	}
1779
1780	kunmap_atomic(addr);
1781
1782	*obj_idx = index;
1783
1784	return handle;
1785	}
1786
1787	struct zs_compact_control {
1788	/* Source spage for migration which could be a subpage of zspage */
1789	struct page *s_page;
1790	/* Destination page for migration which should be a first page
1791	* of zspage. */
1792	struct page *d_page;
1793	/* Starting object index within @s_page which used for live object
1794	* in the subpage. */
1795	int obj_idx;
1796	};
1797
1798	static int migrate_zspage(struct zs_pool *pool, struct size_class *class,
1799	struct zs_compact_control *cc)
1800	{
1801	unsigned long used_obj, free_obj;
1802	unsigned long handle;
1803	struct page *s_page = cc->s_page;
1804	struct page *d_page = cc->d_page;
1805	int obj_idx = cc->obj_idx;
1806	int ret = 0;
1807
1808	while (1) {
1809	handle = find_alloced_obj(class, s_page, &obj_idx);
1810	if (!handle) {
1811	s_page = get_next_page(s_page);
1812	if (!s_page)
1813	break;
1814	obj_idx = 0;
1815	continue;
1816	}
1817
1818	/* Stop if there is no more space */
1819	if (zspage_full(class, get_zspage(d_page))) {
1820	unpin_tag(handle);
1821	ret = -ENOMEM;
1822	break;
1823	}
1824
1825	used_obj = handle_to_obj(handle);
1826	free_obj = obj_malloc(class, get_zspage(d_page), handle);
1827	zs_object_copy(class, free_obj, used_obj);
1828	obj_idx++;
1829	/*
1830	* record_obj updates handle's value to free_obj and it will
1831	* invalidate lock bit(ie, HANDLE_PIN_BIT) of handle, which
1832	* breaks synchronization using pin_tag(e,g, zs_free) so
1833	* let's keep the lock bit.
1834	*/
1835	free_obj |= BIT(HANDLE_PIN_BIT);
1836	record_obj(handle, free_obj);
1837	unpin_tag(handle);
1838	obj_free(class, used_obj);
1839	}
1840
1841	/* Remember last position in this iteration */
1842	cc->s_page = s_page;
1843	cc->obj_idx = obj_idx;
1844
1845	return ret;
1846	}
1847
1848	static struct zspage *isolate_zspage(struct size_class *class, bool source)
1849	{
1850	int i;
1851	struct zspage *zspage;
1852	enum fullness_group fg[2] = {ZS_ALMOST_EMPTY, ZS_ALMOST_FULL};
1853
1854	if (!source) {
1855	fg[0] = ZS_ALMOST_FULL;
1856	fg[1] = ZS_ALMOST_EMPTY;
1857	}
1858
1859	for (i = 0; i < 2; i++) {
1860	zspage = list_first_entry_or_null(&class->fullness_list[fg[i]],
1861	struct zspage, list);
1862	if (zspage) {
1863	VM_BUG_ON(is_zspage_isolated(zspage));
1864	remove_zspage(class, zspage, fg[i]);
1865	return zspage;
1866	}
1867	}
1868
1869	return zspage;
1870	}
1871
1872	/*
1873	* putback_zspage - add @zspage into right class's fullness list
1874	* @class: destination class
1875	* @zspage: target page
1876	*
1877	* Return @zspage's fullness_group
1878	*/
1879	static enum fullness_group putback_zspage(struct size_class *class,
1880	struct zspage *zspage)
1881	{
1882	enum fullness_group fullness;
1883
1884	VM_BUG_ON(is_zspage_isolated(zspage));
1885
1886	fullness = get_fullness_group(class, zspage);
1887	insert_zspage(class, zspage, fullness);
1888	set_zspage_mapping(zspage, class->index, fullness);
1889
1890	return fullness;
1891	}
1892
1893	#ifdef CONFIG_COMPACTION
1894	static struct dentry *zs_mount(struct file_system_type *fs_type,
1895	int flags, const char *dev_name, void *data)
1896	{
1897	static const struct dentry_operations ops = {
1898	.d_dname = simple_dname,
1899	};
1900
1901	return mount_pseudo(fs_type, "zsmalloc:", NULL, &ops, ZSMALLOC_MAGIC);
1902	}
1903
1904	static struct file_system_type zsmalloc_fs = {
1905	.name = "zsmalloc",
1906	.mount = zs_mount,
1907	.kill_sb = kill_anon_super,
1908	};
1909
1910	static int zsmalloc_mount(void)
1911	{
1912	int ret = 0;
1913
1914	zsmalloc_mnt = kern_mount(&zsmalloc_fs);
1915	if (IS_ERR(zsmalloc_mnt))
1916	ret = PTR_ERR(zsmalloc_mnt);
1917
1918	return ret;
1919	}
1920
1921	static void zsmalloc_unmount(void)
1922	{
1923	kern_unmount(zsmalloc_mnt);
1924	}
1925
1926	static void migrate_lock_init(struct zspage *zspage)
1927	{
1928	rwlock_init(&zspage->lock);
1929	}
1930
1931	static void migrate_read_lock(struct zspage *zspage)
1932	{
1933	read_lock(&zspage->lock);
1934	}
1935
1936	static void migrate_read_unlock(struct zspage *zspage)
1937	{
1938	read_unlock(&zspage->lock);
1939	}
1940
1941	static void migrate_write_lock(struct zspage *zspage)
1942	{
1943	write_lock(&zspage->lock);
1944	}
1945
1946	static void migrate_write_unlock(struct zspage *zspage)
1947	{
1948	write_unlock(&zspage->lock);
1949	}
1950
1951	/* Number of isolated subpage for *page migration* in this zspage */
1952	static void inc_zspage_isolation(struct zspage *zspage)
1953	{
1954	zspage->isolated++;
1955	}
1956
1957	static void dec_zspage_isolation(struct zspage *zspage)
1958	{
1959	zspage->isolated--;
1960	}
1961
1962	static void replace_sub_page(struct size_class *class, struct zspage *zspage,
1963	struct page *newpage, struct page *oldpage)
1964	{
1965	struct page *page;
1966	struct page *pages[ZS_MAX_PAGES_PER_ZSPAGE] = {NULL, };
1967	int idx = 0;
1968
1969	page = get_first_page(zspage);
1970	do {
1971	if (page == oldpage)
1972	pages[idx] = newpage;
1973	else
1974	pages[idx] = page;
1975	idx++;
1976	} while ((page = get_next_page(page)) != NULL);
1977
1978	create_page_chain(class, zspage, pages);
1979	set_first_obj_offset(newpage, get_first_obj_offset(oldpage));
1980	if (unlikely(PageHugeObject(oldpage)))
1981	newpage->index = oldpage->index;
1982	__SetPageMovable(newpage, page_mapping(oldpage));
1983	}
1984
1985	bool zs_page_isolate(struct page *page, isolate_mode_t mode)
1986	{
1987	struct zs_pool *pool;
1988	struct size_class *class;
1989	int class_idx;
1990	enum fullness_group fullness;
1991	struct zspage *zspage;
1992	struct address_space *mapping;
1993
1994	/*
1995	* Page is locked so zspage couldn't be destroyed. For detail, look at
1996	* lock_zspage in free_zspage.
1997	*/
1998	VM_BUG_ON_PAGE(!PageMovable(page), page);
1999	VM_BUG_ON_PAGE(PageIsolated(page), page);
2000
2001	zspage = get_zspage(page);
2002
2003	/*
2004	* Without class lock, fullness could be stale while class_idx is okay
2005	* because class_idx is constant unless page is freed so we should get
2006	* fullness again under class lock.
2007	*/
2008	get_zspage_mapping(zspage, &class_idx, &fullness);
2009	mapping = page_mapping(page);
2010	pool = mapping->private_data;
2011	class = pool->size_class[class_idx];
2012
2013	spin_lock(&class->lock);
2014	if (get_zspage_inuse(zspage) == 0) {
2015	spin_unlock(&class->lock);
2016	return false;
2017	}
2018
2019	/* zspage is isolated for object migration */
2020	if (list_empty(&zspage->list) && !is_zspage_isolated(zspage)) {
2021	spin_unlock(&class->lock);
2022	return false;
2023	}
2024
2025	/*
2026	* If this is first time isolation for the zspage, isolate zspage from
2027	* size_class to prevent further object allocation from the zspage.
2028	*/
2029	if (!list_empty(&zspage->list) && !is_zspage_isolated(zspage)) {
2030	get_zspage_mapping(zspage, &class_idx, &fullness);
2031	remove_zspage(class, zspage, fullness);
2032	}
2033
2034	inc_zspage_isolation(zspage);
2035	spin_unlock(&class->lock);
2036
2037	return true;
2038	}
2039
2040	int zs_page_migrate(struct address_space *mapping, struct page *newpage,
2041	struct page *page, enum migrate_mode mode)
2042	{
2043	struct zs_pool *pool;
2044	struct size_class *class;
2045	int class_idx;
2046	enum fullness_group fullness;
2047	struct zspage *zspage;
2048	struct page *dummy;
2049	void *s_addr, *d_addr, *addr;
2050	int offset, pos;
2051	unsigned long handle, head;
2052	unsigned long old_obj, new_obj;
2053	unsigned int obj_idx;
2054	int ret = -EAGAIN;
2055
2056	VM_BUG_ON_PAGE(!PageMovable(page), page);
2057	VM_BUG_ON_PAGE(!PageIsolated(page), page);
2058
2059	zspage = get_zspage(page);
2060
2061	/* Concurrent compactor cannot migrate any subpage in zspage */
2062	migrate_write_lock(zspage);
2063	get_zspage_mapping(zspage, &class_idx, &fullness);
2064	pool = mapping->private_data;
2065	class = pool->size_class[class_idx];
2066	offset = get_first_obj_offset(page);
2067
2068	spin_lock(&class->lock);
2069	if (!get_zspage_inuse(zspage)) {
2070	ret = -EBUSY;
2071	goto unlock_class;
2072	}
2073
2074	pos = offset;
2075	s_addr = kmap_atomic(page);
2076	while (pos < PAGE_SIZE) {
2077	head = obj_to_head(page, s_addr + pos);
2078	if (head & OBJ_ALLOCATED_TAG) {
2079	handle = head & ~OBJ_ALLOCATED_TAG;
2080	if (!trypin_tag(handle))
2081	goto unpin_objects;
2082	}
2083	pos += class->size;
2084	}
2085
2086	/*
2087	* Here, any user cannot access all objects in the zspage so let's move.
2088	*/
2089	d_addr = kmap_atomic(newpage);
2090	memcpy(d_addr, s_addr, PAGE_SIZE);
2091	kunmap_atomic(d_addr);
2092
2093	for (addr = s_addr + offset; addr < s_addr + pos;
2094	addr += class->size) {
2095	head = obj_to_head(page, addr);
2096	if (head & OBJ_ALLOCATED_TAG) {
2097	handle = head & ~OBJ_ALLOCATED_TAG;
2098	if (!testpin_tag(handle))
2099	BUG();
2100
2101	old_obj = handle_to_obj(handle);
2102	obj_to_location(old_obj, &dummy, &obj_idx);
2103	new_obj = (unsigned long)location_to_obj(newpage,
2104	obj_idx);
2105	new_obj |= BIT(HANDLE_PIN_BIT);
2106	record_obj(handle, new_obj);
2107	}
2108	}
2109
2110	replace_sub_page(class, zspage, newpage, page);
2111	get_page(newpage);
2112
2113	dec_zspage_isolation(zspage);
2114
2115	/*
2116	* Page migration is done so let's putback isolated zspage to
2117	* the list if @page is final isolated subpage in the zspage.
2118	*/
2119	if (!is_zspage_isolated(zspage))
2120	putback_zspage(class, zspage);
2121
2122	reset_page(page);
2123	put_page(page);
2124	page = newpage;
2125
2126	ret = MIGRATEPAGE_SUCCESS;
2127	unpin_objects:
2128	for (addr = s_addr + offset; addr < s_addr + pos;
2129	addr += class->size) {
2130	head = obj_to_head(page, addr);
2131	if (head & OBJ_ALLOCATED_TAG) {
2132	handle = head & ~OBJ_ALLOCATED_TAG;
2133	if (!testpin_tag(handle))
2134	BUG();
2135	unpin_tag(handle);
2136	}
2137	}
2138	kunmap_atomic(s_addr);
2139	unlock_class:
2140	spin_unlock(&class->lock);
2141	migrate_write_unlock(zspage);
2142
2143	return ret;
2144	}
2145
2146	void zs_page_putback(struct page *page)
2147	{
2148	struct zs_pool *pool;
2149	struct size_class *class;
2150	int class_idx;
2151	enum fullness_group fg;
2152	struct address_space *mapping;
2153	struct zspage *zspage;
2154
2155	VM_BUG_ON_PAGE(!PageMovable(page), page);
2156	VM_BUG_ON_PAGE(!PageIsolated(page), page);
2157
2158	zspage = get_zspage(page);
2159	get_zspage_mapping(zspage, &class_idx, &fg);
2160	mapping = page_mapping(page);
2161	pool = mapping->private_data;
2162	class = pool->size_class[class_idx];
2163
2164	spin_lock(&class->lock);
2165	dec_zspage_isolation(zspage);
2166	if (!is_zspage_isolated(zspage)) {
2167	fg = putback_zspage(class, zspage);
2168	/*
2169	* Due to page_lock, we cannot free zspage immediately
2170	* so let's defer.
2171	*/
2172	if (fg == ZS_EMPTY)
2173	schedule_work(&pool->free_work);
2174	}
2175	spin_unlock(&class->lock);
2176	}
2177
2178	const struct address_space_operations zsmalloc_aops = {
2179	.isolate_page = zs_page_isolate,
2180	.migratepage = zs_page_migrate,
2181	.putback_page = zs_page_putback,
2182	};
2183
2184	static int zs_register_migration(struct zs_pool *pool)
2185	{
2186	pool->inode = alloc_anon_inode(zsmalloc_mnt->mnt_sb);
2187	if (IS_ERR(pool->inode)) {
2188	pool->inode = NULL;
2189	return 1;
2190	}
2191
2192	pool->inode->i_mapping->private_data = pool;
2193	pool->inode->i_mapping->a_ops = &zsmalloc_aops;
2194	return 0;
2195	}
2196
2197	static void zs_unregister_migration(struct zs_pool *pool)
2198	{
2199	flush_work(&pool->free_work);
2200	iput(pool->inode);
2201	}
2202
2203	/*
2204	* Caller should hold page_lock of all pages in the zspage
2205	* In here, we cannot use zspage meta data.
2206	*/
2207	static void async_free_zspage(struct work_struct *work)
2208	{
2209	int i;
2210	struct size_class *class;
2211	unsigned int class_idx;
2212	enum fullness_group fullness;
2213	struct zspage *zspage, *tmp;
2214	LIST_HEAD(free_pages);
2215	struct zs_pool *pool = container_of(work, struct zs_pool,
2216	free_work);
2217
2218	for (i = 0; i < zs_size_classes; i++) {
2219	class = pool->size_class[i];
2220	if (class->index != i)
2221	continue;
2222
2223	spin_lock(&class->lock);
2224	list_splice_init(&class->fullness_list[ZS_EMPTY], &free_pages);
2225	spin_unlock(&class->lock);
2226	}
2227
2228
2229	list_for_each_entry_safe(zspage, tmp, &free_pages, list) {
2230	list_del(&zspage->list);
2231	lock_zspage(zspage);
2232
2233	get_zspage_mapping(zspage, &class_idx, &fullness);
2234	VM_BUG_ON(fullness != ZS_EMPTY);
2235	class = pool->size_class[class_idx];
2236	spin_lock(&class->lock);
2237	__free_zspage(pool, pool->size_class[class_idx], zspage);
2238	spin_unlock(&class->lock);
2239	}
2240	};
2241
2242	static void kick_deferred_free(struct zs_pool *pool)
2243	{
2244	schedule_work(&pool->free_work);
2245	}
2246
2247	static void init_deferred_free(struct zs_pool *pool)
2248	{
2249	INIT_WORK(&pool->free_work, async_free_zspage);
2250	}
2251
2252	static void SetZsPageMovable(struct zs_pool *pool, struct zspage *zspage)
2253	{
2254	struct page *page = get_first_page(zspage);
2255
2256	do {
2257	WARN_ON(!trylock_page(page));
2258	__SetPageMovable(page, pool->inode->i_mapping);
2259	unlock_page(page);
2260	} while ((page = get_next_page(page)) != NULL);
2261	}
2262	#endif
2263
2264	/*
2265	*
2266	* Based on the number of unused allocated objects calculate
2267	* and return the number of pages that we can free.
2268	*/
2269	static unsigned long zs_can_compact(struct size_class *class)
2270	{
2271	unsigned long obj_wasted;
2272	unsigned long obj_allocated = zs_stat_get(class, OBJ_ALLOCATED);
2273	unsigned long obj_used = zs_stat_get(class, OBJ_USED);
2274
2275	if (obj_allocated <= obj_used)
2276	return 0;
2277
2278	obj_wasted = obj_allocated - obj_used;
2279	obj_wasted /= class->objs_per_zspage;
2280
2281	return obj_wasted * class->pages_per_zspage;
2282	}
2283
2284	static void __zs_compact(struct zs_pool *pool, struct size_class *class)
2285	{
2286	struct zs_compact_control cc;
2287	struct zspage *src_zspage;
2288	struct zspage *dst_zspage = NULL;
2289
2290	spin_lock(&class->lock);
2291	while ((src_zspage = isolate_zspage(class, true))) {
2292
2293	if (!zs_can_compact(class))
2294	break;
2295
2296	cc.obj_idx = 0;
2297	cc.s_page = get_first_page(src_zspage);
2298
2299	while ((dst_zspage = isolate_zspage(class, false))) {
2300	cc.d_page = get_first_page(dst_zspage);
2301	/*
2302	* If there is no more space in dst_page, resched
2303	* and see if anyone had allocated another zspage.
2304	*/
2305	if (!migrate_zspage(pool, class, &cc))
2306	break;
2307
2308	putback_zspage(class, dst_zspage);
2309	}
2310
2311	/* Stop if we couldn't find slot */
2312	if (dst_zspage == NULL)
2313	break;
2314
2315	putback_zspage(class, dst_zspage);
2316	if (putback_zspage(class, src_zspage) == ZS_EMPTY) {
2317	free_zspage(pool, class, src_zspage);
2318	pool->stats.pages_compacted += class->pages_per_zspage;
2319	}
2320	spin_unlock(&class->lock);
2321	cond_resched();
2322	spin_lock(&class->lock);
2323	}
2324
2325	if (src_zspage)
2326	putback_zspage(class, src_zspage);
2327
2328	spin_unlock(&class->lock);
2329	}
2330
2331	unsigned long zs_compact(struct zs_pool *pool)
2332	{
2333	int i;
2334	struct size_class *class;
2335
2336	for (i = zs_size_classes - 1; i >= 0; i--) {
2337	class = pool->size_class[i];
2338	if (!class)
2339	continue;
2340	if (class->index != i)
2341	continue;
2342	__zs_compact(pool, class);
2343	}
2344
2345	return pool->stats.pages_compacted;
2346	}
2347	EXPORT_SYMBOL_GPL(zs_compact);
2348
2349	void zs_pool_stats(struct zs_pool *pool, struct zs_pool_stats *stats)
2350	{
2351	memcpy(stats, &pool->stats, sizeof(struct zs_pool_stats));
2352	}
2353	EXPORT_SYMBOL_GPL(zs_pool_stats);
2354
2355	static unsigned long zs_shrinker_scan(struct shrinker *shrinker,
2356	struct shrink_control *sc)
2357	{
2358	unsigned long pages_freed;
2359	struct zs_pool *pool = container_of(shrinker, struct zs_pool,
2360	shrinker);
2361
2362	pages_freed = pool->stats.pages_compacted;
2363	/*
2364	* Compact classes and calculate compaction delta.
2365	* Can run concurrently with a manually triggered
2366	* (by user) compaction.
2367	*/
2368	pages_freed = zs_compact(pool) - pages_freed;
2369
2370	return pages_freed ? pages_freed : SHRINK_STOP;
2371	}
2372
2373	static unsigned long zs_shrinker_count(struct shrinker *shrinker,
2374	struct shrink_control *sc)
2375	{
2376	int i;
2377	struct size_class *class;
2378	unsigned long pages_to_free = 0;
2379	struct zs_pool *pool = container_of(shrinker, struct zs_pool,
2380	shrinker);
2381
2382	for (i = zs_size_classes - 1; i >= 0; i--) {
2383	class = pool->size_class[i];
2384	if (!class)
2385	continue;
2386	if (class->index != i)
2387	continue;
2388
2389	pages_to_free += zs_can_compact(class);
2390	}
2391
2392	return pages_to_free;
2393	}
2394
2395	static void zs_unregister_shrinker(struct zs_pool *pool)
2396	{
2397	if (pool->shrinker_enabled) {
2398	unregister_shrinker(&pool->shrinker);
2399	pool->shrinker_enabled = false;
2400	}
2401	}
2402
2403	static int zs_register_shrinker(struct zs_pool *pool)
2404	{
2405	pool->shrinker.scan_objects = zs_shrinker_scan;
2406	pool->shrinker.count_objects = zs_shrinker_count;
2407	pool->shrinker.batch = 0;
2408	pool->shrinker.seeks = DEFAULT_SEEKS;
2409
2410	return register_shrinker(&pool->shrinker);
2411	}
2412
2413	/**
2414	* zs_create_pool - Creates an allocation pool to work from.
2415	* @name: pool name to be created
2416	*
2417	* This function must be called before anything when using
2418	* the zsmalloc allocator.
2419	*
2420	* On success, a pointer to the newly created pool is returned,
2421	* otherwise NULL.
2422	*/
2423	struct zs_pool *zs_create_pool(const char *name)
2424	{
2425	int i;
2426	struct zs_pool *pool;
2427	struct size_class *prev_class = NULL;
2428
2429	pool = kzalloc(sizeof(*pool), GFP_KERNEL);
2430	if (!pool)
2431	return NULL;
2432
2433	init_deferred_free(pool);
2434	pool->size_class = kcalloc(zs_size_classes, sizeof(struct size_class *),
2435	GFP_KERNEL);
2436	if (!pool->size_class) {
2437	kfree(pool);
2438	return NULL;
2439	}
2440
2441	pool->name = kstrdup(name, GFP_KERNEL);
2442	if (!pool->name)
2443	goto err;
2444
2445	if (create_cache(pool))
2446	goto err;
2447
2448	/*
2449	* Iterate reversly, because, size of size_class that we want to use
2450	* for merging should be larger or equal to current size.
2451	*/
2452	for (i = zs_size_classes - 1; i >= 0; i--) {
2453	int size;
2454	int pages_per_zspage;
2455	int objs_per_zspage;
2456	struct size_class *class;
2457	int fullness = 0;
2458
2459	size = ZS_MIN_ALLOC_SIZE + i * ZS_SIZE_CLASS_DELTA;
2460	if (size > ZS_MAX_ALLOC_SIZE)
2461	size = ZS_MAX_ALLOC_SIZE;
2462	pages_per_zspage = get_pages_per_zspage(size);
2463	objs_per_zspage = pages_per_zspage * PAGE_SIZE / size;
2464
2465	/*
2466	* We iterate from biggest down to smallest classes,
2467	* so huge_class_size holds the size of the first huge
2468	* class. Any object bigger than or equal to that will
2469	* endup in the huge class.
2470	*/
2471	if (pages_per_zspage != 1 && objs_per_zspage != 1 &&
2472	!huge_class_size) {
2473	huge_class_size = size;
2474	/*
2475	* The object uses ZS_HANDLE_SIZE bytes to store the
2476	* handle. We need to subtract it, because zs_malloc()
2477	* unconditionally adds handle size before it performs
2478	* size class search - so object may be smaller than
2479	* huge class size, yet it still can end up in the huge
2480	* class because it grows by ZS_HANDLE_SIZE extra bytes
2481	* right before class lookup.
2482	*/
2483	huge_class_size -= (ZS_HANDLE_SIZE - 1);
2484	}
2485
2486	/*
2487	* size_class is used for normal zsmalloc operation such
2488	* as alloc/free for that size. Although it is natural that we
2489	* have one size_class for each size, there is a chance that we
2490	* can get more memory utilization if we use one size_class for
2491	* many different sizes whose size_class have same
2492	* characteristics. So, we makes size_class point to
2493	* previous size_class if possible.
2494	*/
2495	if (prev_class) {
2496	if (can_merge(prev_class, pages_per_zspage, objs_per_zspage)) {
2497	pool->size_class[i] = prev_class;
2498	continue;
2499	}
2500	}
2501
2502	class = kzalloc(sizeof(struct size_class), GFP_KERNEL);
2503	if (!class)
2504	goto err;
2505
2506	class->size = size;
2507	class->index = i;
2508	class->pages_per_zspage = pages_per_zspage;
2509	class->objs_per_zspage = objs_per_zspage;
2510	spin_lock_init(&class->lock);
2511	pool->size_class[i] = class;
2512	for (fullness = ZS_EMPTY; fullness < NR_ZS_FULLNESS;
2513	fullness++)
2514	INIT_LIST_HEAD(&class->fullness_list[fullness]);
2515
2516	prev_class = class;
2517	}
2518
2519	/* debug only, don't abort if it fails */
2520	zs_pool_stat_create(pool, name);
2521
2522	if (zs_register_migration(pool))
2523	goto err;
2524
2525	/*
2526	* Not critical, we still can use the pool
2527	* and user can trigger compaction manually.
2528	*/
2529	if (zs_register_shrinker(pool) == 0)
2530	pool->shrinker_enabled = true;
2531	return pool;
2532
2533	err:
2534	zs_destroy_pool(pool);
2535	return NULL;
2536	}
2537	EXPORT_SYMBOL_GPL(zs_create_pool);
2538
2539	void zs_destroy_pool(struct zs_pool *pool)
2540	{
2541	int i;
2542
2543	zs_unregister_shrinker(pool);
2544	zs_unregister_migration(pool);
2545	zs_pool_stat_destroy(pool);
2546
2547	for (i = 0; i < zs_size_classes; i++) {
2548	int fg;
2549	struct size_class *class = pool->size_class[i];
2550
2551	if (!class)
2552	continue;
2553
2554	if (class->index != i)
2555	continue;
2556
2557	for (fg = ZS_EMPTY; fg < NR_ZS_FULLNESS; fg++) {
2558	if (!list_empty(&class->fullness_list[fg])) {
2559	pr_info("Freeing non-empty class with size %db, fullness group %d\n",
2560	class->size, fg);
2561	}
2562	}
2563	kfree(class);
2564	}
2565
2566	destroy_cache(pool);
2567	kfree(pool->size_class);
2568	kfree(pool->name);
2569	kfree(pool);
2570	}
2571	EXPORT_SYMBOL_GPL(zs_destroy_pool);
2572
2573	static int __init zs_init(void)
2574	{
2575	int ret;
2576
2577	ret = zsmalloc_mount();
2578	if (ret)
2579	goto out;
2580
2581	ret = zs_register_cpu_notifier();
2582
2583	if (ret)
2584	goto notifier_fail;
2585
2586	init_zs_size_classes();
2587
2588	#ifdef CONFIG_ZPOOL
2589	zpool_register_driver(&zs_zpool_driver);
2590	#endif
2591
2592	zs_stat_init();
2593
2594	return 0;
2595
2596	notifier_fail:
2597	zs_unregister_cpu_notifier();
2598	zsmalloc_unmount();
2599	out:
2600	return ret;
2601	}
2602
2603	static void __exit zs_exit(void)
2604	{
2605	#ifdef CONFIG_ZPOOL
2606	zpool_unregister_driver(&zs_zpool_driver);
2607	#endif
2608	zsmalloc_unmount();
2609	zs_unregister_cpu_notifier();
2610
2611	zs_stat_exit();
2612	}
2613
2614	module_init(zs_init);
2615	module_exit(zs_exit);
2616
2617	MODULE_LICENSE("Dual BSD/GPL");
2618	MODULE_AUTHOR("Nitin Gupta <ngupta@vflare.org>");
2619