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