Version:  2.0.40 2.2.26 2.4.37 3.13 3.14 3.15 3.16 3.17 3.18 3.19 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10

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

This page was automatically generated by LXR 0.3.1 (source).  •  Linux is a registered trademark of Linus Torvalds  •  Contact us