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