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