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 <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/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 * as 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_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: /* fall through */
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)
895{
896 bit_spin_lock(HANDLE_PIN_BIT, (unsigned long *)handle);
897}
898
899static void unpin_tag(unsigned long handle)
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_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 BUG_ON(map_vm_area(area->vm, PAGE_KERNEL, pages));
1142 area->vm_addr = area->vm->addr;
1143 return area->vm_addr + off;
1144}
1145
1146static inline void __zs_unmap_object(struct mapping_area *area,
1147 struct page *pages[2], int off, int size)
1148{
1149 unsigned long addr = (unsigned long)area->vm_addr;
1150
1151 unmap_kernel_range(addr, PAGE_SIZE * 2);
1152}
1153
1154#else /* CONFIG_PGTABLE_MAPPING */
1155
1156static inline int __zs_cpu_up(struct mapping_area *area)
1157{
1158 /*
1159 * Make sure we don't leak memory if a cpu UP notification
1160 * and zs_init() race and both call zs_cpu_up() on the same cpu
1161 */
1162 if (area->vm_buf)
1163 return 0;
1164 area->vm_buf = kmalloc(ZS_MAX_ALLOC_SIZE, GFP_KERNEL);
1165 if (!area->vm_buf)
1166 return -ENOMEM;
1167 return 0;
1168}
1169
1170static inline void __zs_cpu_down(struct mapping_area *area)
1171{
1172 kfree(area->vm_buf);
1173 area->vm_buf = NULL;
1174}
1175
1176static void *__zs_map_object(struct mapping_area *area,
1177 struct page *pages[2], int off, int size)
1178{
1179 int sizes[2];
1180 void *addr;
1181 char *buf = area->vm_buf;
1182
1183 /* disable page faults to match kmap_atomic() return conditions */
1184 pagefault_disable();
1185
1186 /* no read fastpath */
1187 if (area->vm_mm == ZS_MM_WO)
1188 goto out;
1189
1190 sizes[0] = PAGE_SIZE - off;
1191 sizes[1] = size - sizes[0];
1192
1193 /* copy object to per-cpu buffer */
1194 addr = kmap_atomic(pages[0]);
1195 memcpy(buf, addr + off, sizes[0]);
1196 kunmap_atomic(addr);
1197 addr = kmap_atomic(pages[1]);
1198 memcpy(buf + sizes[0], addr, sizes[1]);
1199 kunmap_atomic(addr);
1200out:
1201 return area->vm_buf;
1202}
1203
1204static void __zs_unmap_object(struct mapping_area *area,
1205 struct page *pages[2], int off, int size)
1206{
1207 int sizes[2];
1208 void *addr;
1209 char *buf;
1210
1211 /* no write fastpath */
1212 if (area->vm_mm == ZS_MM_RO)
1213 goto out;
1214
1215 buf = area->vm_buf;
1216 buf = buf + ZS_HANDLE_SIZE;
1217 size -= ZS_HANDLE_SIZE;
1218 off += ZS_HANDLE_SIZE;
1219
1220 sizes[0] = PAGE_SIZE - off;
1221 sizes[1] = size - sizes[0];
1222
1223 /* copy per-cpu buffer to object */
1224 addr = kmap_atomic(pages[0]);
1225 memcpy(addr + off, buf, sizes[0]);
1226 kunmap_atomic(addr);
1227 addr = kmap_atomic(pages[1]);
1228 memcpy(addr, buf + sizes[0], sizes[1]);
1229 kunmap_atomic(addr);
1230
1231out:
1232 /* enable page faults to match kunmap_atomic() return conditions */
1233 pagefault_enable();
1234}
1235
1236#endif /* CONFIG_PGTABLE_MAPPING */
1237
1238static int zs_cpu_prepare(unsigned int cpu)
1239{
1240 struct mapping_area *area;
1241
1242 area = &per_cpu(zs_map_area, cpu);
1243 return __zs_cpu_up(area);
1244}
1245
1246static int zs_cpu_dead(unsigned int cpu)
1247{
1248 struct mapping_area *area;
1249
1250 area = &per_cpu(zs_map_area, cpu);
1251 __zs_cpu_down(area);
1252 return 0;
1253}
1254
1255static bool can_merge(struct size_class *prev, int pages_per_zspage,
1256 int objs_per_zspage)
1257{
1258 if (prev->pages_per_zspage == pages_per_zspage &&
1259 prev->objs_per_zspage == objs_per_zspage)
1260 return true;
1261
1262 return false;
1263}
1264
1265static bool zspage_full(struct size_class *class, struct zspage *zspage)
1266{
1267 return get_zspage_inuse(zspage) == class->objs_per_zspage;
1268}
1269
1270unsigned long zs_get_total_pages(struct zs_pool *pool)
1271{
1272 return atomic_long_read(&pool->pages_allocated);
1273}
1274EXPORT_SYMBOL_GPL(zs_get_total_pages);
1275
1276/**
1277 * zs_map_object - get address of allocated object from handle.
1278 * @pool: pool from which the object was allocated
1279 * @handle: handle returned from zs_malloc
1280 * @mm: maping mode to use
1281 *
1282 * Before using an object allocated from zs_malloc, it must be mapped using
1283 * this function. When done with the object, it must be unmapped using
1284 * zs_unmap_object.
1285 *
1286 * Only one object can be mapped per cpu at a time. There is no protection
1287 * against nested mappings.
1288 *
1289 * This function returns with preemption and page faults disabled.
1290 */
1291void *zs_map_object(struct zs_pool *pool, unsigned long handle,
1292 enum zs_mapmode mm)
1293{
1294 struct zspage *zspage;
1295 struct page *page;
1296 unsigned long obj, off;
1297 unsigned int obj_idx;
1298
1299 unsigned int class_idx;
1300 enum fullness_group fg;
1301 struct size_class *class;
1302 struct mapping_area *area;
1303 struct page *pages[2];
1304 void *ret;
1305
1306 /*
1307 * Because we use per-cpu mapping areas shared among the
1308 * pools/users, we can't allow mapping in interrupt context
1309 * because it can corrupt another users mappings.
1310 */
1311 BUG_ON(in_interrupt());
1312
1313 /* From now on, migration cannot move the object */
1314 pin_tag(handle);
1315
1316 obj = handle_to_obj(handle);
1317 obj_to_location(obj, &page, &obj_idx);
1318 zspage = get_zspage(page);
1319
1320 /* migration cannot move any subpage in this zspage */
1321 migrate_read_lock(zspage);
1322
1323 get_zspage_mapping(zspage, &class_idx, &fg);
1324 class = pool->size_class[class_idx];
1325 off = (class->size * obj_idx) & ~PAGE_MASK;
1326
1327 area = &get_cpu_var(zs_map_area);
1328 area->vm_mm = mm;
1329 if (off + class->size <= PAGE_SIZE) {
1330 /* this object is contained entirely within a page */
1331 area->vm_addr = kmap_atomic(page);
1332 ret = area->vm_addr + off;
1333 goto out;
1334 }
1335
1336 /* this object spans two pages */
1337 pages[0] = page;
1338 pages[1] = get_next_page(page);
1339 BUG_ON(!pages[1]);
1340
1341 ret = __zs_map_object(area, pages, off, class->size);
1342out:
1343 if (likely(!PageHugeObject(page)))
1344 ret += ZS_HANDLE_SIZE;
1345
1346 return ret;
1347}
1348EXPORT_SYMBOL_GPL(zs_map_object);
1349
1350void zs_unmap_object(struct zs_pool *pool, unsigned long handle)
1351{
1352 struct zspage *zspage;
1353 struct page *page;
1354 unsigned long obj, off;
1355 unsigned int obj_idx;
1356
1357 unsigned int class_idx;
1358 enum fullness_group fg;
1359 struct size_class *class;
1360 struct mapping_area *area;
1361
1362 obj = handle_to_obj(handle);
1363 obj_to_location(obj, &page, &obj_idx);
1364 zspage = get_zspage(page);
1365 get_zspage_mapping(zspage, &class_idx, &fg);
1366 class = pool->size_class[class_idx];
1367 off = (class->size * obj_idx) & ~PAGE_MASK;
1368
1369 area = this_cpu_ptr(&zs_map_area);
1370 if (off + class->size <= PAGE_SIZE)
1371 kunmap_atomic(area->vm_addr);
1372 else {
1373 struct page *pages[2];
1374
1375 pages[0] = page;
1376 pages[1] = get_next_page(page);
1377 BUG_ON(!pages[1]);
1378
1379 __zs_unmap_object(area, pages, off, class->size);
1380 }
1381 put_cpu_var(zs_map_area);
1382
1383 migrate_read_unlock(zspage);
1384 unpin_tag(handle);
1385}
1386EXPORT_SYMBOL_GPL(zs_unmap_object);
1387
1388/**
1389 * zs_huge_class_size() - Returns the size (in bytes) of the first huge
1390 * zsmalloc &size_class.
1391 * @pool: zsmalloc pool to use
1392 *
1393 * The function returns the size of the first huge class - any object of equal
1394 * or bigger size will be stored in zspage consisting of a single physical
1395 * page.
1396 *
1397 * Context: Any context.
1398 *
1399 * Return: the size (in bytes) of the first huge zsmalloc &size_class.
1400 */
1401size_t zs_huge_class_size(struct zs_pool *pool)
1402{
1403 return huge_class_size;
1404}
1405EXPORT_SYMBOL_GPL(zs_huge_class_size);
1406
1407static unsigned long obj_malloc(struct size_class *class,
1408 struct zspage *zspage, unsigned long handle)
1409{
1410 int i, nr_page, offset;
1411 unsigned long obj;
1412 struct link_free *link;
1413
1414 struct page *m_page;
1415 unsigned long m_offset;
1416 void *vaddr;
1417
1418 handle |= OBJ_ALLOCATED_TAG;
1419 obj = get_freeobj(zspage);
1420
1421 offset = obj * class->size;
1422 nr_page = offset >> PAGE_SHIFT;
1423 m_offset = offset & ~PAGE_MASK;
1424 m_page = get_first_page(zspage);
1425
1426 for (i = 0; i < nr_page; i++)
1427 m_page = get_next_page(m_page);
1428
1429 vaddr = kmap_atomic(m_page);
1430 link = (struct link_free *)vaddr + m_offset / sizeof(*link);
1431 set_freeobj(zspage, link->next >> OBJ_TAG_BITS);
1432 if (likely(!PageHugeObject(m_page)))
1433 /* record handle in the header of allocated chunk */
1434 link->handle = handle;
1435 else
1436 /* record handle to page->index */
1437 zspage->first_page->index = handle;
1438
1439 kunmap_atomic(vaddr);
1440 mod_zspage_inuse(zspage, 1);
1441 zs_stat_inc(class, OBJ_USED, 1);
1442
1443 obj = location_to_obj(m_page, obj);
1444
1445 return obj;
1446}
1447
1448
1449/**
1450 * zs_malloc - Allocate block of given size from pool.
1451 * @pool: pool to allocate from
1452 * @size: size of block to allocate
1453 * @gfp: gfp flags when allocating object
1454 *
1455 * On success, handle to the allocated object is returned,
1456 * otherwise 0.
1457 * Allocation requests with size > ZS_MAX_ALLOC_SIZE will fail.
1458 */
1459unsigned long zs_malloc(struct zs_pool *pool, size_t size, gfp_t gfp)
1460{
1461 unsigned long handle, obj;
1462 struct size_class *class;
1463 enum fullness_group newfg;
1464 struct zspage *zspage;
1465
1466 if (unlikely(!size || size > ZS_MAX_ALLOC_SIZE))
1467 return 0;
1468
1469 handle = cache_alloc_handle(pool, gfp);
1470 if (!handle)
1471 return 0;
1472
1473 /* extra space in chunk to keep the handle */
1474 size += ZS_HANDLE_SIZE;
1475 class = pool->size_class[get_size_class_index(size)];
1476
1477 spin_lock(&class->lock);
1478 zspage = find_get_zspage(class);
1479 if (likely(zspage)) {
1480 obj = obj_malloc(class, zspage, handle);
1481 /* Now move the zspage to another fullness group, if required */
1482 fix_fullness_group(class, zspage);
1483 record_obj(handle, obj);
1484 spin_unlock(&class->lock);
1485
1486 return handle;
1487 }
1488
1489 spin_unlock(&class->lock);
1490
1491 zspage = alloc_zspage(pool, class, gfp);
1492 if (!zspage) {
1493 cache_free_handle(pool, handle);
1494 return 0;
1495 }
1496
1497 spin_lock(&class->lock);
1498 obj = obj_malloc(class, zspage, handle);
1499 newfg = get_fullness_group(class, zspage);
1500 insert_zspage(class, zspage, newfg);
1501 set_zspage_mapping(zspage, class->index, newfg);
1502 record_obj(handle, obj);
1503 atomic_long_add(class->pages_per_zspage,
1504 &pool->pages_allocated);
1505 zs_stat_inc(class, OBJ_ALLOCATED, class->objs_per_zspage);
1506
1507 /* We completely set up zspage so mark them as movable */
1508 SetZsPageMovable(pool, zspage);
1509 spin_unlock(&class->lock);
1510
1511 return handle;
1512}
1513EXPORT_SYMBOL_GPL(zs_malloc);
1514
1515static void obj_free(struct size_class *class, unsigned long obj)
1516{
1517 struct link_free *link;
1518 struct zspage *zspage;
1519 struct page *f_page;
1520 unsigned long f_offset;
1521 unsigned int f_objidx;
1522 void *vaddr;
1523
1524 obj &= ~OBJ_ALLOCATED_TAG;
1525 obj_to_location(obj, &f_page, &f_objidx);
1526 f_offset = (class->size * f_objidx) & ~PAGE_MASK;
1527 zspage = get_zspage(f_page);
1528
1529 vaddr = kmap_atomic(f_page);
1530
1531 /* Insert this object in containing zspage's freelist */
1532 link = (struct link_free *)(vaddr + f_offset);
1533 link->next = get_freeobj(zspage) << OBJ_TAG_BITS;
1534 kunmap_atomic(vaddr);
1535 set_freeobj(zspage, f_objidx);
1536 mod_zspage_inuse(zspage, -1);
1537 zs_stat_dec(class, OBJ_USED, 1);
1538}
1539
1540void zs_free(struct zs_pool *pool, unsigned long handle)
1541{
1542 struct zspage *zspage;
1543 struct page *f_page;
1544 unsigned long obj;
1545 unsigned int f_objidx;
1546 int class_idx;
1547 struct size_class *class;
1548 enum fullness_group fullness;
1549 bool isolated;
1550
1551 if (unlikely(!handle))
1552 return;
1553
1554 pin_tag(handle);
1555 obj = handle_to_obj(handle);
1556 obj_to_location(obj, &f_page, &f_objidx);
1557 zspage = get_zspage(f_page);
1558
1559 migrate_read_lock(zspage);
1560
1561 get_zspage_mapping(zspage, &class_idx, &fullness);
1562 class = pool->size_class[class_idx];
1563
1564 spin_lock(&class->lock);
1565 obj_free(class, obj);
1566 fullness = fix_fullness_group(class, zspage);
1567 if (fullness != ZS_EMPTY) {
1568 migrate_read_unlock(zspage);
1569 goto out;
1570 }
1571
1572 isolated = is_zspage_isolated(zspage);
1573 migrate_read_unlock(zspage);
1574 /* If zspage is isolated, zs_page_putback will free the zspage */
1575 if (likely(!isolated))
1576 free_zspage(pool, class, zspage);
1577out:
1578
1579 spin_unlock(&class->lock);
1580 unpin_tag(handle);
1581 cache_free_handle(pool, handle);
1582}
1583EXPORT_SYMBOL_GPL(zs_free);
1584
1585static void zs_object_copy(struct size_class *class, unsigned long dst,
1586 unsigned long src)
1587{
1588 struct page *s_page, *d_page;
1589 unsigned int s_objidx, d_objidx;
1590 unsigned long s_off, d_off;
1591 void *s_addr, *d_addr;
1592 int s_size, d_size, size;
1593 int written = 0;
1594
1595 s_size = d_size = class->size;
1596
1597 obj_to_location(src, &s_page, &s_objidx);
1598 obj_to_location(dst, &d_page, &d_objidx);
1599
1600 s_off = (class->size * s_objidx) & ~PAGE_MASK;
1601 d_off = (class->size * d_objidx) & ~PAGE_MASK;
1602
1603 if (s_off + class->size > PAGE_SIZE)
1604 s_size = PAGE_SIZE - s_off;
1605
1606 if (d_off + class->size > PAGE_SIZE)
1607 d_size = PAGE_SIZE - d_off;
1608
1609 s_addr = kmap_atomic(s_page);
1610 d_addr = kmap_atomic(d_page);
1611
1612 while (1) {
1613 size = min(s_size, d_size);
1614 memcpy(d_addr + d_off, s_addr + s_off, size);
1615 written += size;
1616
1617 if (written == class->size)
1618 break;
1619
1620 s_off += size;
1621 s_size -= size;
1622 d_off += size;
1623 d_size -= size;
1624
1625 if (s_off >= PAGE_SIZE) {
1626 kunmap_atomic(d_addr);
1627 kunmap_atomic(s_addr);
1628 s_page = get_next_page(s_page);
1629 s_addr = kmap_atomic(s_page);
1630 d_addr = kmap_atomic(d_page);
1631 s_size = class->size - written;
1632 s_off = 0;
1633 }
1634
1635 if (d_off >= PAGE_SIZE) {
1636 kunmap_atomic(d_addr);
1637 d_page = get_next_page(d_page);
1638 d_addr = kmap_atomic(d_page);
1639 d_size = class->size - written;
1640 d_off = 0;
1641 }
1642 }
1643
1644 kunmap_atomic(d_addr);
1645 kunmap_atomic(s_addr);
1646}
1647
1648/*
1649 * Find alloced object in zspage from index object and
1650 * return handle.
1651 */
1652static unsigned long find_alloced_obj(struct size_class *class,
1653 struct page *page, int *obj_idx)
1654{
1655 unsigned long head;
1656 int offset = 0;
1657 int index = *obj_idx;
1658 unsigned long handle = 0;
1659 void *addr = kmap_atomic(page);
1660
1661 offset = get_first_obj_offset(page);
1662 offset += class->size * index;
1663
1664 while (offset < PAGE_SIZE) {
1665 head = obj_to_head(page, addr + offset);
1666 if (head & OBJ_ALLOCATED_TAG) {
1667 handle = head & ~OBJ_ALLOCATED_TAG;
1668 if (trypin_tag(handle))
1669 break;
1670 handle = 0;
1671 }
1672
1673 offset += class->size;
1674 index++;
1675 }
1676
1677 kunmap_atomic(addr);
1678
1679 *obj_idx = index;
1680
1681 return handle;
1682}
1683
1684struct zs_compact_control {
1685 /* Source spage for migration which could be a subpage of zspage */
1686 struct page *s_page;
1687 /* Destination page for migration which should be a first page
1688 * of zspage. */
1689 struct page *d_page;
1690 /* Starting object index within @s_page which used for live object
1691 * in the subpage. */
1692 int obj_idx;
1693};
1694
1695static int migrate_zspage(struct zs_pool *pool, struct size_class *class,
1696 struct zs_compact_control *cc)
1697{
1698 unsigned long used_obj, free_obj;
1699 unsigned long handle;
1700 struct page *s_page = cc->s_page;
1701 struct page *d_page = cc->d_page;
1702 int obj_idx = cc->obj_idx;
1703 int ret = 0;
1704
1705 while (1) {
1706 handle = find_alloced_obj(class, s_page, &obj_idx);
1707 if (!handle) {
1708 s_page = get_next_page(s_page);
1709 if (!s_page)
1710 break;
1711 obj_idx = 0;
1712 continue;
1713 }
1714
1715 /* Stop if there is no more space */
1716 if (zspage_full(class, get_zspage(d_page))) {
1717 unpin_tag(handle);
1718 ret = -ENOMEM;
1719 break;
1720 }
1721
1722 used_obj = handle_to_obj(handle);
1723 free_obj = obj_malloc(class, get_zspage(d_page), handle);
1724 zs_object_copy(class, free_obj, used_obj);
1725 obj_idx++;
1726 /*
1727 * record_obj updates handle's value to free_obj and it will
1728 * invalidate lock bit(ie, HANDLE_PIN_BIT) of handle, which
1729 * breaks synchronization using pin_tag(e,g, zs_free) so
1730 * let's keep the lock bit.
1731 */
1732 free_obj |= BIT(HANDLE_PIN_BIT);
1733 record_obj(handle, free_obj);
1734 unpin_tag(handle);
1735 obj_free(class, used_obj);
1736 }
1737
1738 /* Remember last position in this iteration */
1739 cc->s_page = s_page;
1740 cc->obj_idx = obj_idx;
1741
1742 return ret;
1743}
1744
1745static struct zspage *isolate_zspage(struct size_class *class, bool source)
1746{
1747 int i;
1748 struct zspage *zspage;
1749 enum fullness_group fg[2] = {ZS_ALMOST_EMPTY, ZS_ALMOST_FULL};
1750
1751 if (!source) {
1752 fg[0] = ZS_ALMOST_FULL;
1753 fg[1] = ZS_ALMOST_EMPTY;
1754 }
1755
1756 for (i = 0; i < 2; i++) {
1757 zspage = list_first_entry_or_null(&class->fullness_list[fg[i]],
1758 struct zspage, list);
1759 if (zspage) {
1760 VM_BUG_ON(is_zspage_isolated(zspage));
1761 remove_zspage(class, zspage, fg[i]);
1762 return zspage;
1763 }
1764 }
1765
1766 return zspage;
1767}
1768
1769/*
1770 * putback_zspage - add @zspage into right class's fullness list
1771 * @class: destination class
1772 * @zspage: target page
1773 *
1774 * Return @zspage's fullness_group
1775 */
1776static enum fullness_group putback_zspage(struct size_class *class,
1777 struct zspage *zspage)
1778{
1779 enum fullness_group fullness;
1780
1781 VM_BUG_ON(is_zspage_isolated(zspage));
1782
1783 fullness = get_fullness_group(class, zspage);
1784 insert_zspage(class, zspage, fullness);
1785 set_zspage_mapping(zspage, class->index, fullness);
1786
1787 return fullness;
1788}
1789
1790#ifdef CONFIG_COMPACTION
1791/*
1792 * To prevent zspage destroy during migration, zspage freeing should
1793 * hold locks of all pages in the zspage.
1794 */
1795static void lock_zspage(struct zspage *zspage)
1796{
1797 struct page *page = get_first_page(zspage);
1798
1799 do {
1800 lock_page(page);
1801 } while ((page = get_next_page(page)) != NULL);
1802}
1803
1804static int zs_init_fs_context(struct fs_context *fc)
1805{
1806 return init_pseudo(fc, ZSMALLOC_MAGIC) ? 0 : -ENOMEM;
1807}
1808
1809static struct file_system_type zsmalloc_fs = {
1810 .name = "zsmalloc",
1811 .init_fs_context = zs_init_fs_context,
1812 .kill_sb = kill_anon_super,
1813};
1814
1815static int zsmalloc_mount(void)
1816{
1817 int ret = 0;
1818
1819 zsmalloc_mnt = kern_mount(&zsmalloc_fs);
1820 if (IS_ERR(zsmalloc_mnt))
1821 ret = PTR_ERR(zsmalloc_mnt);
1822
1823 return ret;
1824}
1825
1826static void zsmalloc_unmount(void)
1827{
1828 kern_unmount(zsmalloc_mnt);
1829}
1830
1831static void migrate_lock_init(struct zspage *zspage)
1832{
1833 rwlock_init(&zspage->lock);
1834}
1835
1836static void migrate_read_lock(struct zspage *zspage)
1837{
1838 read_lock(&zspage->lock);
1839}
1840
1841static void migrate_read_unlock(struct zspage *zspage)
1842{
1843 read_unlock(&zspage->lock);
1844}
1845
1846static void migrate_write_lock(struct zspage *zspage)
1847{
1848 write_lock(&zspage->lock);
1849}
1850
1851static void migrate_write_unlock(struct zspage *zspage)
1852{
1853 write_unlock(&zspage->lock);
1854}
1855
1856/* Number of isolated subpage for *page migration* in this zspage */
1857static void inc_zspage_isolation(struct zspage *zspage)
1858{
1859 zspage->isolated++;
1860}
1861
1862static void dec_zspage_isolation(struct zspage *zspage)
1863{
1864 zspage->isolated--;
1865}
1866
1867static void putback_zspage_deferred(struct zs_pool *pool,
1868 struct size_class *class,
1869 struct zspage *zspage)
1870{
1871 enum fullness_group fg;
1872
1873 fg = putback_zspage(class, zspage);
1874 if (fg == ZS_EMPTY)
1875 schedule_work(&pool->free_work);
1876
1877}
1878
1879static inline void zs_pool_dec_isolated(struct zs_pool *pool)
1880{
1881 VM_BUG_ON(atomic_long_read(&pool->isolated_pages) <= 0);
1882 atomic_long_dec(&pool->isolated_pages);
1883 /*
1884 * There's no possibility of racing, since wait_for_isolated_drain()
1885 * checks the isolated count under &class->lock after enqueuing
1886 * on migration_wait.
1887 */
1888 if (atomic_long_read(&pool->isolated_pages) == 0 && pool->destroying)
1889 wake_up_all(&pool->migration_wait);
1890}
1891
1892static void replace_sub_page(struct size_class *class, struct zspage *zspage,
1893 struct page *newpage, struct page *oldpage)
1894{
1895 struct page *page;
1896 struct page *pages[ZS_MAX_PAGES_PER_ZSPAGE] = {NULL, };
1897 int idx = 0;
1898
1899 page = get_first_page(zspage);
1900 do {
1901 if (page == oldpage)
1902 pages[idx] = newpage;
1903 else
1904 pages[idx] = page;
1905 idx++;
1906 } while ((page = get_next_page(page)) != NULL);
1907
1908 create_page_chain(class, zspage, pages);
1909 set_first_obj_offset(newpage, get_first_obj_offset(oldpage));
1910 if (unlikely(PageHugeObject(oldpage)))
1911 newpage->index = oldpage->index;
1912 __SetPageMovable(newpage, page_mapping(oldpage));
1913}
1914
1915static bool zs_page_isolate(struct page *page, isolate_mode_t mode)
1916{
1917 struct zs_pool *pool;
1918 struct size_class *class;
1919 int class_idx;
1920 enum fullness_group fullness;
1921 struct zspage *zspage;
1922 struct address_space *mapping;
1923
1924 /*
1925 * Page is locked so zspage couldn't be destroyed. For detail, look at
1926 * lock_zspage in free_zspage.
1927 */
1928 VM_BUG_ON_PAGE(!PageMovable(page), page);
1929 VM_BUG_ON_PAGE(PageIsolated(page), page);
1930
1931 zspage = get_zspage(page);
1932
1933 /*
1934 * Without class lock, fullness could be stale while class_idx is okay
1935 * because class_idx is constant unless page is freed so we should get
1936 * fullness again under class lock.
1937 */
1938 get_zspage_mapping(zspage, &class_idx, &fullness);
1939 mapping = page_mapping(page);
1940 pool = mapping->private_data;
1941 class = pool->size_class[class_idx];
1942
1943 spin_lock(&class->lock);
1944 if (get_zspage_inuse(zspage) == 0) {
1945 spin_unlock(&class->lock);
1946 return false;
1947 }
1948
1949 /* zspage is isolated for object migration */
1950 if (list_empty(&zspage->list) && !is_zspage_isolated(zspage)) {
1951 spin_unlock(&class->lock);
1952 return false;
1953 }
1954
1955 /*
1956 * If this is first time isolation for the zspage, isolate zspage from
1957 * size_class to prevent further object allocation from the zspage.
1958 */
1959 if (!list_empty(&zspage->list) && !is_zspage_isolated(zspage)) {
1960 get_zspage_mapping(zspage, &class_idx, &fullness);
1961 atomic_long_inc(&pool->isolated_pages);
1962 remove_zspage(class, zspage, fullness);
1963 }
1964
1965 inc_zspage_isolation(zspage);
1966 spin_unlock(&class->lock);
1967
1968 return true;
1969}
1970
1971static int zs_page_migrate(struct address_space *mapping, struct page *newpage,
1972 struct page *page, enum migrate_mode mode)
1973{
1974 struct zs_pool *pool;
1975 struct size_class *class;
1976 int class_idx;
1977 enum fullness_group fullness;
1978 struct zspage *zspage;
1979 struct page *dummy;
1980 void *s_addr, *d_addr, *addr;
1981 int offset, pos;
1982 unsigned long handle, head;
1983 unsigned long old_obj, new_obj;
1984 unsigned int obj_idx;
1985 int ret = -EAGAIN;
1986
1987 /*
1988 * We cannot support the _NO_COPY case here, because copy needs to
1989 * happen under the zs lock, which does not work with
1990 * MIGRATE_SYNC_NO_COPY workflow.
1991 */
1992 if (mode == MIGRATE_SYNC_NO_COPY)
1993 return -EINVAL;
1994
1995 VM_BUG_ON_PAGE(!PageMovable(page), page);
1996 VM_BUG_ON_PAGE(!PageIsolated(page), page);
1997
1998 zspage = get_zspage(page);
1999
2000 /* Concurrent compactor cannot migrate any subpage in zspage */
2001 migrate_write_lock(zspage);
2002 get_zspage_mapping(zspage, &class_idx, &fullness);
2003 pool = mapping->private_data;
2004 class = pool->size_class[class_idx];
2005 offset = get_first_obj_offset(page);
2006
2007 spin_lock(&class->lock);
2008 if (!get_zspage_inuse(zspage)) {
2009 /*
2010 * Set "offset" to end of the page so that every loops
2011 * skips unnecessary object scanning.
2012 */
2013 offset = PAGE_SIZE;
2014 }
2015
2016 pos = offset;
2017 s_addr = kmap_atomic(page);
2018 while (pos < PAGE_SIZE) {
2019 head = obj_to_head(page, s_addr + pos);
2020 if (head & OBJ_ALLOCATED_TAG) {
2021 handle = head & ~OBJ_ALLOCATED_TAG;
2022 if (!trypin_tag(handle))
2023 goto unpin_objects;
2024 }
2025 pos += class->size;
2026 }
2027
2028 /*
2029 * Here, any user cannot access all objects in the zspage so let's move.
2030 */
2031 d_addr = kmap_atomic(newpage);
2032 memcpy(d_addr, s_addr, PAGE_SIZE);
2033 kunmap_atomic(d_addr);
2034
2035 for (addr = s_addr + offset; addr < s_addr + pos;
2036 addr += class->size) {
2037 head = obj_to_head(page, addr);
2038 if (head & OBJ_ALLOCATED_TAG) {
2039 handle = head & ~OBJ_ALLOCATED_TAG;
2040 if (!testpin_tag(handle))
2041 BUG();
2042
2043 old_obj = handle_to_obj(handle);
2044 obj_to_location(old_obj, &dummy, &obj_idx);
2045 new_obj = (unsigned long)location_to_obj(newpage,
2046 obj_idx);
2047 new_obj |= BIT(HANDLE_PIN_BIT);
2048 record_obj(handle, new_obj);
2049 }
2050 }
2051
2052 replace_sub_page(class, zspage, newpage, page);
2053 get_page(newpage);
2054
2055 dec_zspage_isolation(zspage);
2056
2057 /*
2058 * Page migration is done so let's putback isolated zspage to
2059 * the list if @page is final isolated subpage in the zspage.
2060 */
2061 if (!is_zspage_isolated(zspage)) {
2062 /*
2063 * We cannot race with zs_destroy_pool() here because we wait
2064 * for isolation to hit zero before we start destroying.
2065 * Also, we ensure that everyone can see pool->destroying before
2066 * we start waiting.
2067 */
2068 putback_zspage_deferred(pool, class, zspage);
2069 zs_pool_dec_isolated(pool);
2070 }
2071
2072 reset_page(page);
2073 put_page(page);
2074 page = newpage;
2075
2076 ret = MIGRATEPAGE_SUCCESS;
2077unpin_objects:
2078 for (addr = s_addr + offset; addr < s_addr + pos;
2079 addr += class->size) {
2080 head = obj_to_head(page, addr);
2081 if (head & OBJ_ALLOCATED_TAG) {
2082 handle = head & ~OBJ_ALLOCATED_TAG;
2083 if (!testpin_tag(handle))
2084 BUG();
2085 unpin_tag(handle);
2086 }
2087 }
2088 kunmap_atomic(s_addr);
2089 spin_unlock(&class->lock);
2090 migrate_write_unlock(zspage);
2091
2092 return ret;
2093}
2094
2095static void zs_page_putback(struct page *page)
2096{
2097 struct zs_pool *pool;
2098 struct size_class *class;
2099 int class_idx;
2100 enum fullness_group fg;
2101 struct address_space *mapping;
2102 struct zspage *zspage;
2103
2104 VM_BUG_ON_PAGE(!PageMovable(page), page);
2105 VM_BUG_ON_PAGE(!PageIsolated(page), page);
2106
2107 zspage = get_zspage(page);
2108 get_zspage_mapping(zspage, &class_idx, &fg);
2109 mapping = page_mapping(page);
2110 pool = mapping->private_data;
2111 class = pool->size_class[class_idx];
2112
2113 spin_lock(&class->lock);
2114 dec_zspage_isolation(zspage);
2115 if (!is_zspage_isolated(zspage)) {
2116 /*
2117 * Due to page_lock, we cannot free zspage immediately
2118 * so let's defer.
2119 */
2120 putback_zspage_deferred(pool, class, zspage);
2121 zs_pool_dec_isolated(pool);
2122 }
2123 spin_unlock(&class->lock);
2124}
2125
2126static const struct address_space_operations zsmalloc_aops = {
2127 .isolate_page = zs_page_isolate,
2128 .migratepage = zs_page_migrate,
2129 .putback_page = zs_page_putback,
2130};
2131
2132static int zs_register_migration(struct zs_pool *pool)
2133{
2134 pool->inode = alloc_anon_inode(zsmalloc_mnt->mnt_sb);
2135 if (IS_ERR(pool->inode)) {
2136 pool->inode = NULL;
2137 return 1;
2138 }
2139
2140 pool->inode->i_mapping->private_data = pool;
2141 pool->inode->i_mapping->a_ops = &zsmalloc_aops;
2142 return 0;
2143}
2144
2145static bool pool_isolated_are_drained(struct zs_pool *pool)
2146{
2147 return atomic_long_read(&pool->isolated_pages) == 0;
2148}
2149
2150/* Function for resolving migration */
2151static void wait_for_isolated_drain(struct zs_pool *pool)
2152{
2153
2154 /*
2155 * We're in the process of destroying the pool, so there are no
2156 * active allocations. zs_page_isolate() fails for completely free
2157 * zspages, so we need only wait for the zs_pool's isolated
2158 * count to hit zero.
2159 */
2160 wait_event(pool->migration_wait,
2161 pool_isolated_are_drained(pool));
2162}
2163
2164static void zs_unregister_migration(struct zs_pool *pool)
2165{
2166 pool->destroying = true;
2167 /*
2168 * We need a memory barrier here to ensure global visibility of
2169 * pool->destroying. Thus pool->isolated pages will either be 0 in which
2170 * case we don't care, or it will be > 0 and pool->destroying will
2171 * ensure that we wake up once isolation hits 0.
2172 */
2173 smp_mb();
2174 wait_for_isolated_drain(pool); /* This can block */
2175 flush_work(&pool->free_work);
2176 iput(pool->inode);
2177}
2178
2179/*
2180 * Caller should hold page_lock of all pages in the zspage
2181 * In here, we cannot use zspage meta data.
2182 */
2183static void async_free_zspage(struct work_struct *work)
2184{
2185 int i;
2186 struct size_class *class;
2187 unsigned int class_idx;
2188 enum fullness_group fullness;
2189 struct zspage *zspage, *tmp;
2190 LIST_HEAD(free_pages);
2191 struct zs_pool *pool = container_of(work, struct zs_pool,
2192 free_work);
2193
2194 for (i = 0; i < ZS_SIZE_CLASSES; i++) {
2195 class = pool->size_class[i];
2196 if (class->index != i)
2197 continue;
2198
2199 spin_lock(&class->lock);
2200 list_splice_init(&class->fullness_list[ZS_EMPTY], &free_pages);
2201 spin_unlock(&class->lock);
2202 }
2203
2204
2205 list_for_each_entry_safe(zspage, tmp, &free_pages, list) {
2206 list_del(&zspage->list);
2207 lock_zspage(zspage);
2208
2209 get_zspage_mapping(zspage, &class_idx, &fullness);
2210 VM_BUG_ON(fullness != ZS_EMPTY);
2211 class = pool->size_class[class_idx];
2212 spin_lock(&class->lock);
2213 __free_zspage(pool, pool->size_class[class_idx], zspage);
2214 spin_unlock(&class->lock);
2215 }
2216};
2217
2218static void kick_deferred_free(struct zs_pool *pool)
2219{
2220 schedule_work(&pool->free_work);
2221}
2222
2223static void init_deferred_free(struct zs_pool *pool)
2224{
2225 INIT_WORK(&pool->free_work, async_free_zspage);
2226}
2227
2228static void SetZsPageMovable(struct zs_pool *pool, struct zspage *zspage)
2229{
2230 struct page *page = get_first_page(zspage);
2231
2232 do {
2233 WARN_ON(!trylock_page(page));
2234 __SetPageMovable(page, pool->inode->i_mapping);
2235 unlock_page(page);
2236 } while ((page = get_next_page(page)) != NULL);
2237}
2238#endif
2239
2240/*
2241 *
2242 * Based on the number of unused allocated objects calculate
2243 * and return the number of pages that we can free.
2244 */
2245static unsigned long zs_can_compact(struct size_class *class)
2246{
2247 unsigned long obj_wasted;
2248 unsigned long obj_allocated = zs_stat_get(class, OBJ_ALLOCATED);
2249 unsigned long obj_used = zs_stat_get(class, OBJ_USED);
2250
2251 if (obj_allocated <= obj_used)
2252 return 0;
2253
2254 obj_wasted = obj_allocated - obj_used;
2255 obj_wasted /= class->objs_per_zspage;
2256
2257 return obj_wasted * class->pages_per_zspage;
2258}
2259
2260static void __zs_compact(struct zs_pool *pool, struct size_class *class)
2261{
2262 struct zs_compact_control cc;
2263 struct zspage *src_zspage;
2264 struct zspage *dst_zspage = NULL;
2265
2266 spin_lock(&class->lock);
2267 while ((src_zspage = isolate_zspage(class, true))) {
2268
2269 if (!zs_can_compact(class))
2270 break;
2271
2272 cc.obj_idx = 0;
2273 cc.s_page = get_first_page(src_zspage);
2274
2275 while ((dst_zspage = isolate_zspage(class, false))) {
2276 cc.d_page = get_first_page(dst_zspage);
2277 /*
2278 * If there is no more space in dst_page, resched
2279 * and see if anyone had allocated another zspage.
2280 */
2281 if (!migrate_zspage(pool, class, &cc))
2282 break;
2283
2284 putback_zspage(class, dst_zspage);
2285 }
2286
2287 /* Stop if we couldn't find slot */
2288 if (dst_zspage == NULL)
2289 break;
2290
2291 putback_zspage(class, dst_zspage);
2292 if (putback_zspage(class, src_zspage) == ZS_EMPTY) {
2293 free_zspage(pool, class, src_zspage);
2294 pool->stats.pages_compacted += class->pages_per_zspage;
2295 }
2296 spin_unlock(&class->lock);
2297 cond_resched();
2298 spin_lock(&class->lock);
2299 }
2300
2301 if (src_zspage)
2302 putback_zspage(class, src_zspage);
2303
2304 spin_unlock(&class->lock);
2305}
2306
2307unsigned long zs_compact(struct zs_pool *pool)
2308{
2309 int i;
2310 struct size_class *class;
2311
2312 for (i = ZS_SIZE_CLASSES - 1; i >= 0; i--) {
2313 class = pool->size_class[i];
2314 if (!class)
2315 continue;
2316 if (class->index != i)
2317 continue;
2318 __zs_compact(pool, class);
2319 }
2320
2321 return pool->stats.pages_compacted;
2322}
2323EXPORT_SYMBOL_GPL(zs_compact);
2324
2325void zs_pool_stats(struct zs_pool *pool, struct zs_pool_stats *stats)
2326{
2327 memcpy(stats, &pool->stats, sizeof(struct zs_pool_stats));
2328}
2329EXPORT_SYMBOL_GPL(zs_pool_stats);
2330
2331static unsigned long zs_shrinker_scan(struct shrinker *shrinker,
2332 struct shrink_control *sc)
2333{
2334 unsigned long pages_freed;
2335 struct zs_pool *pool = container_of(shrinker, struct zs_pool,
2336 shrinker);
2337
2338 pages_freed = pool->stats.pages_compacted;
2339 /*
2340 * Compact classes and calculate compaction delta.
2341 * Can run concurrently with a manually triggered
2342 * (by user) compaction.
2343 */
2344 pages_freed = zs_compact(pool) - pages_freed;
2345
2346 return pages_freed ? pages_freed : SHRINK_STOP;
2347}
2348
2349static unsigned long zs_shrinker_count(struct shrinker *shrinker,
2350 struct shrink_control *sc)
2351{
2352 int i;
2353 struct size_class *class;
2354 unsigned long pages_to_free = 0;
2355 struct zs_pool *pool = container_of(shrinker, struct zs_pool,
2356 shrinker);
2357
2358 for (i = ZS_SIZE_CLASSES - 1; i >= 0; i--) {
2359 class = pool->size_class[i];
2360 if (!class)
2361 continue;
2362 if (class->index != i)
2363 continue;
2364
2365 pages_to_free += zs_can_compact(class);
2366 }
2367
2368 return pages_to_free;
2369}
2370
2371static void zs_unregister_shrinker(struct zs_pool *pool)
2372{
2373 unregister_shrinker(&pool->shrinker);
2374}
2375
2376static int zs_register_shrinker(struct zs_pool *pool)
2377{
2378 pool->shrinker.scan_objects = zs_shrinker_scan;
2379 pool->shrinker.count_objects = zs_shrinker_count;
2380 pool->shrinker.batch = 0;
2381 pool->shrinker.seeks = DEFAULT_SEEKS;
2382
2383 return register_shrinker(&pool->shrinker);
2384}
2385
2386/**
2387 * zs_create_pool - Creates an allocation pool to work from.
2388 * @name: pool name to be created
2389 *
2390 * This function must be called before anything when using
2391 * the zsmalloc allocator.
2392 *
2393 * On success, a pointer to the newly created pool is returned,
2394 * otherwise NULL.
2395 */
2396struct zs_pool *zs_create_pool(const char *name)
2397{
2398 int i;
2399 struct zs_pool *pool;
2400 struct size_class *prev_class = NULL;
2401
2402 pool = kzalloc(sizeof(*pool), GFP_KERNEL);
2403 if (!pool)
2404 return NULL;
2405
2406 init_deferred_free(pool);
2407
2408 pool->name = kstrdup(name, GFP_KERNEL);
2409 if (!pool->name)
2410 goto err;
2411
2412#ifdef CONFIG_COMPACTION
2413 init_waitqueue_head(&pool->migration_wait);
2414#endif
2415
2416 if (create_cache(pool))
2417 goto err;
2418
2419 /*
2420 * Iterate reversely, because, size of size_class that we want to use
2421 * for merging should be larger or equal to current size.
2422 */
2423 for (i = ZS_SIZE_CLASSES - 1; i >= 0; i--) {
2424 int size;
2425 int pages_per_zspage;
2426 int objs_per_zspage;
2427 struct size_class *class;
2428 int fullness = 0;
2429
2430 size = ZS_MIN_ALLOC_SIZE + i * ZS_SIZE_CLASS_DELTA;
2431 if (size > ZS_MAX_ALLOC_SIZE)
2432 size = ZS_MAX_ALLOC_SIZE;
2433 pages_per_zspage = get_pages_per_zspage(size);
2434 objs_per_zspage = pages_per_zspage * PAGE_SIZE / size;
2435
2436 /*
2437 * We iterate from biggest down to smallest classes,
2438 * so huge_class_size holds the size of the first huge
2439 * class. Any object bigger than or equal to that will
2440 * endup in the huge class.
2441 */
2442 if (pages_per_zspage != 1 && objs_per_zspage != 1 &&
2443 !huge_class_size) {
2444 huge_class_size = size;
2445 /*
2446 * The object uses ZS_HANDLE_SIZE bytes to store the
2447 * handle. We need to subtract it, because zs_malloc()
2448 * unconditionally adds handle size before it performs
2449 * size class search - so object may be smaller than
2450 * huge class size, yet it still can end up in the huge
2451 * class because it grows by ZS_HANDLE_SIZE extra bytes
2452 * right before class lookup.
2453 */
2454 huge_class_size -= (ZS_HANDLE_SIZE - 1);
2455 }
2456
2457 /*
2458 * size_class is used for normal zsmalloc operation such
2459 * as alloc/free for that size. Although it is natural that we
2460 * have one size_class for each size, there is a chance that we
2461 * can get more memory utilization if we use one size_class for
2462 * many different sizes whose size_class have same
2463 * characteristics. So, we makes size_class point to
2464 * previous size_class if possible.
2465 */
2466 if (prev_class) {
2467 if (can_merge(prev_class, pages_per_zspage, objs_per_zspage)) {
2468 pool->size_class[i] = prev_class;
2469 continue;
2470 }
2471 }
2472
2473 class = kzalloc(sizeof(struct size_class), GFP_KERNEL);
2474 if (!class)
2475 goto err;
2476
2477 class->size = size;
2478 class->index = i;
2479 class->pages_per_zspage = pages_per_zspage;
2480 class->objs_per_zspage = objs_per_zspage;
2481 spin_lock_init(&class->lock);
2482 pool->size_class[i] = class;
2483 for (fullness = ZS_EMPTY; fullness < NR_ZS_FULLNESS;
2484 fullness++)
2485 INIT_LIST_HEAD(&class->fullness_list[fullness]);
2486
2487 prev_class = class;
2488 }
2489
2490 /* debug only, don't abort if it fails */
2491 zs_pool_stat_create(pool, name);
2492
2493 if (zs_register_migration(pool))
2494 goto err;
2495
2496 /*
2497 * Not critical since shrinker is only used to trigger internal
2498 * defragmentation of the pool which is pretty optional thing. If
2499 * registration fails we still can use the pool normally and user can
2500 * trigger compaction manually. Thus, ignore return code.
2501 */
2502 zs_register_shrinker(pool);
2503
2504 return pool;
2505
2506err:
2507 zs_destroy_pool(pool);
2508 return NULL;
2509}
2510EXPORT_SYMBOL_GPL(zs_create_pool);
2511
2512void zs_destroy_pool(struct zs_pool *pool)
2513{
2514 int i;
2515
2516 zs_unregister_shrinker(pool);
2517 zs_unregister_migration(pool);
2518 zs_pool_stat_destroy(pool);
2519
2520 for (i = 0; i < ZS_SIZE_CLASSES; i++) {
2521 int fg;
2522 struct size_class *class = pool->size_class[i];
2523
2524 if (!class)
2525 continue;
2526
2527 if (class->index != i)
2528 continue;
2529
2530 for (fg = ZS_EMPTY; fg < NR_ZS_FULLNESS; fg++) {
2531 if (!list_empty(&class->fullness_list[fg])) {
2532 pr_info("Freeing non-empty class with size %db, fullness group %d\n",
2533 class->size, fg);
2534 }
2535 }
2536 kfree(class);
2537 }
2538
2539 destroy_cache(pool);
2540 kfree(pool->name);
2541 kfree(pool);
2542}
2543EXPORT_SYMBOL_GPL(zs_destroy_pool);
2544
2545static int __init zs_init(void)
2546{
2547 int ret;
2548
2549 ret = zsmalloc_mount();
2550 if (ret)
2551 goto out;
2552
2553 ret = cpuhp_setup_state(CPUHP_MM_ZS_PREPARE, "mm/zsmalloc:prepare",
2554 zs_cpu_prepare, zs_cpu_dead);
2555 if (ret)
2556 goto hp_setup_fail;
2557
2558#ifdef CONFIG_ZPOOL
2559 zpool_register_driver(&zs_zpool_driver);
2560#endif
2561
2562 zs_stat_init();
2563
2564 return 0;
2565
2566hp_setup_fail:
2567 zsmalloc_unmount();
2568out:
2569 return ret;
2570}
2571
2572static void __exit zs_exit(void)
2573{
2574#ifdef CONFIG_ZPOOL
2575 zpool_unregister_driver(&zs_zpool_driver);
2576#endif
2577 zsmalloc_unmount();
2578 cpuhp_remove_state(CPUHP_MM_ZS_PREPARE);
2579
2580 zs_stat_exit();
2581}
2582
2583module_init(zs_init);
2584module_exit(zs_exit);
2585
2586MODULE_LICENSE("Dual BSD/GPL");
2587MODULE_AUTHOR("Nitin Gupta <ngupta@vflare.org>");