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