1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Memory merging support. 4 * 5 * This code enables dynamic sharing of identical pages found in different 6 * memory areas, even if they are not shared by fork() 7 * 8 * Copyright (C) 2008-2009 Red Hat, Inc. 9 * Authors: 10 * Izik Eidus 11 * Andrea Arcangeli 12 * Chris Wright 13 * Hugh Dickins 14 */ 15 16 #include <linux/errno.h> 17 #include <linux/mm.h> 18 #include <linux/mm_inline.h> 19 #include <linux/fs.h> 20 #include <linux/mman.h> 21 #include <linux/sched.h> 22 #include <linux/sched/mm.h> 23 #include <linux/sched/coredump.h> 24 #include <linux/rwsem.h> 25 #include <linux/pagemap.h> 26 #include <linux/rmap.h> 27 #include <linux/spinlock.h> 28 #include <linux/xxhash.h> 29 #include <linux/delay.h> 30 #include <linux/kthread.h> 31 #include <linux/wait.h> 32 #include <linux/slab.h> 33 #include <linux/rbtree.h> 34 #include <linux/memory.h> 35 #include <linux/mmu_notifier.h> 36 #include <linux/swap.h> 37 #include <linux/ksm.h> 38 #include <linux/hashtable.h> 39 #include <linux/freezer.h> 40 #include <linux/oom.h> 41 #include <linux/numa.h> 42 43 #include <asm/tlbflush.h> 44 #include "internal.h" 45 46 #ifdef CONFIG_NUMA 47 #define NUMA(x) (x) 48 #define DO_NUMA(x) do { (x); } while (0) 49 #else 50 #define NUMA(x) (0) 51 #define DO_NUMA(x) do { } while (0) 52 #endif 53 54 /** 55 * DOC: Overview 56 * 57 * A few notes about the KSM scanning process, 58 * to make it easier to understand the data structures below: 59 * 60 * In order to reduce excessive scanning, KSM sorts the memory pages by their 61 * contents into a data structure that holds pointers to the pages' locations. 62 * 63 * Since the contents of the pages may change at any moment, KSM cannot just 64 * insert the pages into a normal sorted tree and expect it to find anything. 65 * Therefore KSM uses two data structures - the stable and the unstable tree. 66 * 67 * The stable tree holds pointers to all the merged pages (ksm pages), sorted 68 * by their contents. Because each such page is write-protected, searching on 69 * this tree is fully assured to be working (except when pages are unmapped), 70 * and therefore this tree is called the stable tree. 71 * 72 * The stable tree node includes information required for reverse 73 * mapping from a KSM page to virtual addresses that map this page. 74 * 75 * In order to avoid large latencies of the rmap walks on KSM pages, 76 * KSM maintains two types of nodes in the stable tree: 77 * 78 * * the regular nodes that keep the reverse mapping structures in a 79 * linked list 80 * * the "chains" that link nodes ("dups") that represent the same 81 * write protected memory content, but each "dup" corresponds to a 82 * different KSM page copy of that content 83 * 84 * Internally, the regular nodes, "dups" and "chains" are represented 85 * using the same struct stable_node structure. 86 * 87 * In addition to the stable tree, KSM uses a second data structure called the 88 * unstable tree: this tree holds pointers to pages which have been found to 89 * be "unchanged for a period of time". The unstable tree sorts these pages 90 * by their contents, but since they are not write-protected, KSM cannot rely 91 * upon the unstable tree to work correctly - the unstable tree is liable to 92 * be corrupted as its contents are modified, and so it is called unstable. 93 * 94 * KSM solves this problem by several techniques: 95 * 96 * 1) The unstable tree is flushed every time KSM completes scanning all 97 * memory areas, and then the tree is rebuilt again from the beginning. 98 * 2) KSM will only insert into the unstable tree, pages whose hash value 99 * has not changed since the previous scan of all memory areas. 100 * 3) The unstable tree is a RedBlack Tree - so its balancing is based on the 101 * colors of the nodes and not on their contents, assuring that even when 102 * the tree gets "corrupted" it won't get out of balance, so scanning time 103 * remains the same (also, searching and inserting nodes in an rbtree uses 104 * the same algorithm, so we have no overhead when we flush and rebuild). 105 * 4) KSM never flushes the stable tree, which means that even if it were to 106 * take 10 attempts to find a page in the unstable tree, once it is found, 107 * it is secured in the stable tree. (When we scan a new page, we first 108 * compare it against the stable tree, and then against the unstable tree.) 109 * 110 * If the merge_across_nodes tunable is unset, then KSM maintains multiple 111 * stable trees and multiple unstable trees: one of each for each NUMA node. 112 */ 113 114 /** 115 * struct mm_slot - ksm information per mm that is being scanned 116 * @link: link to the mm_slots hash list 117 * @mm_list: link into the mm_slots list, rooted in ksm_mm_head 118 * @rmap_list: head for this mm_slot's singly-linked list of rmap_items 119 * @mm: the mm that this information is valid for 120 */ 121 struct mm_slot { 122 struct hlist_node link; 123 struct list_head mm_list; 124 struct rmap_item *rmap_list; 125 struct mm_struct *mm; 126 }; 127 128 /** 129 * struct ksm_scan - cursor for scanning 130 * @mm_slot: the current mm_slot we are scanning 131 * @address: the next address inside that to be scanned 132 * @rmap_list: link to the next rmap to be scanned in the rmap_list 133 * @seqnr: count of completed full scans (needed when removing unstable node) 134 * 135 * There is only the one ksm_scan instance of this cursor structure. 136 */ 137 struct ksm_scan { 138 struct mm_slot *mm_slot; 139 unsigned long address; 140 struct rmap_item **rmap_list; 141 unsigned long seqnr; 142 }; 143 144 /** 145 * struct stable_node - node of the stable rbtree 146 * @node: rb node of this ksm page in the stable tree 147 * @head: (overlaying parent) &migrate_nodes indicates temporarily on that list 148 * @hlist_dup: linked into the stable_node->hlist with a stable_node chain 149 * @list: linked into migrate_nodes, pending placement in the proper node tree 150 * @hlist: hlist head of rmap_items using this ksm page 151 * @kpfn: page frame number of this ksm page (perhaps temporarily on wrong nid) 152 * @chain_prune_time: time of the last full garbage collection 153 * @rmap_hlist_len: number of rmap_item entries in hlist or STABLE_NODE_CHAIN 154 * @nid: NUMA node id of stable tree in which linked (may not match kpfn) 155 */ 156 struct stable_node { 157 union { 158 struct rb_node node; /* when node of stable tree */ 159 struct { /* when listed for migration */ 160 struct list_head *head; 161 struct { 162 struct hlist_node hlist_dup; 163 struct list_head list; 164 }; 165 }; 166 }; 167 struct hlist_head hlist; 168 union { 169 unsigned long kpfn; 170 unsigned long chain_prune_time; 171 }; 172 /* 173 * STABLE_NODE_CHAIN can be any negative number in 174 * rmap_hlist_len negative range, but better not -1 to be able 175 * to reliably detect underflows. 176 */ 177 #define STABLE_NODE_CHAIN -1024 178 int rmap_hlist_len; 179 #ifdef CONFIG_NUMA 180 int nid; 181 #endif 182 }; 183 184 /** 185 * struct rmap_item - reverse mapping item for virtual addresses 186 * @rmap_list: next rmap_item in mm_slot's singly-linked rmap_list 187 * @anon_vma: pointer to anon_vma for this mm,address, when in stable tree 188 * @nid: NUMA node id of unstable tree in which linked (may not match page) 189 * @mm: the memory structure this rmap_item is pointing into 190 * @address: the virtual address this rmap_item tracks (+ flags in low bits) 191 * @oldchecksum: previous checksum of the page at that virtual address 192 * @node: rb node of this rmap_item in the unstable tree 193 * @head: pointer to stable_node heading this list in the stable tree 194 * @hlist: link into hlist of rmap_items hanging off that stable_node 195 */ 196 struct rmap_item { 197 struct rmap_item *rmap_list; 198 union { 199 struct anon_vma *anon_vma; /* when stable */ 200 #ifdef CONFIG_NUMA 201 int nid; /* when node of unstable tree */ 202 #endif 203 }; 204 struct mm_struct *mm; 205 unsigned long address; /* + low bits used for flags below */ 206 unsigned int oldchecksum; /* when unstable */ 207 union { 208 struct rb_node node; /* when node of unstable tree */ 209 struct { /* when listed from stable tree */ 210 struct stable_node *head; 211 struct hlist_node hlist; 212 }; 213 }; 214 }; 215 216 #define SEQNR_MASK 0x0ff /* low bits of unstable tree seqnr */ 217 #define UNSTABLE_FLAG 0x100 /* is a node of the unstable tree */ 218 #define STABLE_FLAG 0x200 /* is listed from the stable tree */ 219 220 /* The stable and unstable tree heads */ 221 static struct rb_root one_stable_tree[1] = { RB_ROOT }; 222 static struct rb_root one_unstable_tree[1] = { RB_ROOT }; 223 static struct rb_root *root_stable_tree = one_stable_tree; 224 static struct rb_root *root_unstable_tree = one_unstable_tree; 225 226 /* Recently migrated nodes of stable tree, pending proper placement */ 227 static LIST_HEAD(migrate_nodes); 228 #define STABLE_NODE_DUP_HEAD ((struct list_head *)&migrate_nodes.prev) 229 230 #define MM_SLOTS_HASH_BITS 10 231 static DEFINE_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_BITS); 232 233 static struct mm_slot ksm_mm_head = { 234 .mm_list = LIST_HEAD_INIT(ksm_mm_head.mm_list), 235 }; 236 static struct ksm_scan ksm_scan = { 237 .mm_slot = &ksm_mm_head, 238 }; 239 240 static struct kmem_cache *rmap_item_cache; 241 static struct kmem_cache *stable_node_cache; 242 static struct kmem_cache *mm_slot_cache; 243 244 /* The number of nodes in the stable tree */ 245 static unsigned long ksm_pages_shared; 246 247 /* The number of page slots additionally sharing those nodes */ 248 static unsigned long ksm_pages_sharing; 249 250 /* The number of nodes in the unstable tree */ 251 static unsigned long ksm_pages_unshared; 252 253 /* The number of rmap_items in use: to calculate pages_volatile */ 254 static unsigned long ksm_rmap_items; 255 256 /* The number of stable_node chains */ 257 static unsigned long ksm_stable_node_chains; 258 259 /* The number of stable_node dups linked to the stable_node chains */ 260 static unsigned long ksm_stable_node_dups; 261 262 /* Delay in pruning stale stable_node_dups in the stable_node_chains */ 263 static unsigned int ksm_stable_node_chains_prune_millisecs = 2000; 264 265 /* Maximum number of page slots sharing a stable node */ 266 static int ksm_max_page_sharing = 256; 267 268 /* Number of pages ksmd should scan in one batch */ 269 static unsigned int ksm_thread_pages_to_scan = 100; 270 271 /* Milliseconds ksmd should sleep between batches */ 272 static unsigned int ksm_thread_sleep_millisecs = 20; 273 274 /* Checksum of an empty (zeroed) page */ 275 static unsigned int zero_checksum __read_mostly; 276 277 /* Whether to merge empty (zeroed) pages with actual zero pages */ 278 static bool ksm_use_zero_pages __read_mostly; 279 280 #ifdef CONFIG_NUMA 281 /* Zeroed when merging across nodes is not allowed */ 282 static unsigned int ksm_merge_across_nodes = 1; 283 static int ksm_nr_node_ids = 1; 284 #else 285 #define ksm_merge_across_nodes 1U 286 #define ksm_nr_node_ids 1 287 #endif 288 289 #define KSM_RUN_STOP 0 290 #define KSM_RUN_MERGE 1 291 #define KSM_RUN_UNMERGE 2 292 #define KSM_RUN_OFFLINE 4 293 static unsigned long ksm_run = KSM_RUN_STOP; 294 static void wait_while_offlining(void); 295 296 static DECLARE_WAIT_QUEUE_HEAD(ksm_thread_wait); 297 static DECLARE_WAIT_QUEUE_HEAD(ksm_iter_wait); 298 static DEFINE_MUTEX(ksm_thread_mutex); 299 static DEFINE_SPINLOCK(ksm_mmlist_lock); 300 301 #define KSM_KMEM_CACHE(__struct, __flags) kmem_cache_create("ksm_"#__struct,\ 302 sizeof(struct __struct), __alignof__(struct __struct),\ 303 (__flags), NULL) 304 305 static int __init ksm_slab_init(void) 306 { 307 rmap_item_cache = KSM_KMEM_CACHE(rmap_item, 0); 308 if (!rmap_item_cache) 309 goto out; 310 311 stable_node_cache = KSM_KMEM_CACHE(stable_node, 0); 312 if (!stable_node_cache) 313 goto out_free1; 314 315 mm_slot_cache = KSM_KMEM_CACHE(mm_slot, 0); 316 if (!mm_slot_cache) 317 goto out_free2; 318 319 return 0; 320 321 out_free2: 322 kmem_cache_destroy(stable_node_cache); 323 out_free1: 324 kmem_cache_destroy(rmap_item_cache); 325 out: 326 return -ENOMEM; 327 } 328 329 static void __init ksm_slab_free(void) 330 { 331 kmem_cache_destroy(mm_slot_cache); 332 kmem_cache_destroy(stable_node_cache); 333 kmem_cache_destroy(rmap_item_cache); 334 mm_slot_cache = NULL; 335 } 336 337 static __always_inline bool is_stable_node_chain(struct stable_node *chain) 338 { 339 return chain->rmap_hlist_len == STABLE_NODE_CHAIN; 340 } 341 342 static __always_inline bool is_stable_node_dup(struct stable_node *dup) 343 { 344 return dup->head == STABLE_NODE_DUP_HEAD; 345 } 346 347 static inline void stable_node_chain_add_dup(struct stable_node *dup, 348 struct stable_node *chain) 349 { 350 VM_BUG_ON(is_stable_node_dup(dup)); 351 dup->head = STABLE_NODE_DUP_HEAD; 352 VM_BUG_ON(!is_stable_node_chain(chain)); 353 hlist_add_head(&dup->hlist_dup, &chain->hlist); 354 ksm_stable_node_dups++; 355 } 356 357 static inline void __stable_node_dup_del(struct stable_node *dup) 358 { 359 VM_BUG_ON(!is_stable_node_dup(dup)); 360 hlist_del(&dup->hlist_dup); 361 ksm_stable_node_dups--; 362 } 363 364 static inline void stable_node_dup_del(struct stable_node *dup) 365 { 366 VM_BUG_ON(is_stable_node_chain(dup)); 367 if (is_stable_node_dup(dup)) 368 __stable_node_dup_del(dup); 369 else 370 rb_erase(&dup->node, root_stable_tree + NUMA(dup->nid)); 371 #ifdef CONFIG_DEBUG_VM 372 dup->head = NULL; 373 #endif 374 } 375 376 static inline struct rmap_item *alloc_rmap_item(void) 377 { 378 struct rmap_item *rmap_item; 379 380 rmap_item = kmem_cache_zalloc(rmap_item_cache, GFP_KERNEL | 381 __GFP_NORETRY | __GFP_NOWARN); 382 if (rmap_item) 383 ksm_rmap_items++; 384 return rmap_item; 385 } 386 387 static inline void free_rmap_item(struct rmap_item *rmap_item) 388 { 389 ksm_rmap_items--; 390 rmap_item->mm = NULL; /* debug safety */ 391 kmem_cache_free(rmap_item_cache, rmap_item); 392 } 393 394 static inline struct stable_node *alloc_stable_node(void) 395 { 396 /* 397 * The allocation can take too long with GFP_KERNEL when memory is under 398 * pressure, which may lead to hung task warnings. Adding __GFP_HIGH 399 * grants access to memory reserves, helping to avoid this problem. 400 */ 401 return kmem_cache_alloc(stable_node_cache, GFP_KERNEL | __GFP_HIGH); 402 } 403 404 static inline void free_stable_node(struct stable_node *stable_node) 405 { 406 VM_BUG_ON(stable_node->rmap_hlist_len && 407 !is_stable_node_chain(stable_node)); 408 kmem_cache_free(stable_node_cache, stable_node); 409 } 410 411 static inline struct mm_slot *alloc_mm_slot(void) 412 { 413 if (!mm_slot_cache) /* initialization failed */ 414 return NULL; 415 return kmem_cache_zalloc(mm_slot_cache, GFP_KERNEL); 416 } 417 418 static inline void free_mm_slot(struct mm_slot *mm_slot) 419 { 420 kmem_cache_free(mm_slot_cache, mm_slot); 421 } 422 423 static struct mm_slot *get_mm_slot(struct mm_struct *mm) 424 { 425 struct mm_slot *slot; 426 427 hash_for_each_possible(mm_slots_hash, slot, link, (unsigned long)mm) 428 if (slot->mm == mm) 429 return slot; 430 431 return NULL; 432 } 433 434 static void insert_to_mm_slots_hash(struct mm_struct *mm, 435 struct mm_slot *mm_slot) 436 { 437 mm_slot->mm = mm; 438 hash_add(mm_slots_hash, &mm_slot->link, (unsigned long)mm); 439 } 440 441 /* 442 * ksmd, and unmerge_and_remove_all_rmap_items(), must not touch an mm's 443 * page tables after it has passed through ksm_exit() - which, if necessary, 444 * takes mmap_lock briefly to serialize against them. ksm_exit() does not set 445 * a special flag: they can just back out as soon as mm_users goes to zero. 446 * ksm_test_exit() is used throughout to make this test for exit: in some 447 * places for correctness, in some places just to avoid unnecessary work. 448 */ 449 static inline bool ksm_test_exit(struct mm_struct *mm) 450 { 451 return atomic_read(&mm->mm_users) == 0; 452 } 453 454 /* 455 * We use break_ksm to break COW on a ksm page: it's a stripped down 456 * 457 * if (get_user_pages(addr, 1, FOLL_WRITE, &page, NULL) == 1) 458 * put_page(page); 459 * 460 * but taking great care only to touch a ksm page, in a VM_MERGEABLE vma, 461 * in case the application has unmapped and remapped mm,addr meanwhile. 462 * Could a ksm page appear anywhere else? Actually yes, in a VM_PFNMAP 463 * mmap of /dev/mem, where we would not want to touch it. 464 * 465 * FAULT_FLAG/FOLL_REMOTE are because we do this outside the context 466 * of the process that owns 'vma'. We also do not want to enforce 467 * protection keys here anyway. 468 */ 469 static int break_ksm(struct vm_area_struct *vma, unsigned long addr) 470 { 471 struct page *page; 472 vm_fault_t ret = 0; 473 474 do { 475 cond_resched(); 476 page = follow_page(vma, addr, 477 FOLL_GET | FOLL_MIGRATION | FOLL_REMOTE); 478 if (IS_ERR_OR_NULL(page) || is_zone_device_page(page)) 479 break; 480 if (PageKsm(page)) 481 ret = handle_mm_fault(vma, addr, 482 FAULT_FLAG_WRITE | FAULT_FLAG_REMOTE, 483 NULL); 484 else 485 ret = VM_FAULT_WRITE; 486 put_page(page); 487 } while (!(ret & (VM_FAULT_WRITE | VM_FAULT_SIGBUS | VM_FAULT_SIGSEGV | VM_FAULT_OOM))); 488 /* 489 * We must loop because handle_mm_fault() may back out if there's 490 * any difficulty e.g. if pte accessed bit gets updated concurrently. 491 * 492 * VM_FAULT_WRITE is what we have been hoping for: it indicates that 493 * COW has been broken, even if the vma does not permit VM_WRITE; 494 * but note that a concurrent fault might break PageKsm for us. 495 * 496 * VM_FAULT_SIGBUS could occur if we race with truncation of the 497 * backing file, which also invalidates anonymous pages: that's 498 * okay, that truncation will have unmapped the PageKsm for us. 499 * 500 * VM_FAULT_OOM: at the time of writing (late July 2009), setting 501 * aside mem_cgroup limits, VM_FAULT_OOM would only be set if the 502 * current task has TIF_MEMDIE set, and will be OOM killed on return 503 * to user; and ksmd, having no mm, would never be chosen for that. 504 * 505 * But if the mm is in a limited mem_cgroup, then the fault may fail 506 * with VM_FAULT_OOM even if the current task is not TIF_MEMDIE; and 507 * even ksmd can fail in this way - though it's usually breaking ksm 508 * just to undo a merge it made a moment before, so unlikely to oom. 509 * 510 * That's a pity: we might therefore have more kernel pages allocated 511 * than we're counting as nodes in the stable tree; but ksm_do_scan 512 * will retry to break_cow on each pass, so should recover the page 513 * in due course. The important thing is to not let VM_MERGEABLE 514 * be cleared while any such pages might remain in the area. 515 */ 516 return (ret & VM_FAULT_OOM) ? -ENOMEM : 0; 517 } 518 519 static struct vm_area_struct *find_mergeable_vma(struct mm_struct *mm, 520 unsigned long addr) 521 { 522 struct vm_area_struct *vma; 523 if (ksm_test_exit(mm)) 524 return NULL; 525 vma = vma_lookup(mm, addr); 526 if (!vma || !(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma) 527 return NULL; 528 return vma; 529 } 530 531 static void break_cow(struct rmap_item *rmap_item) 532 { 533 struct mm_struct *mm = rmap_item->mm; 534 unsigned long addr = rmap_item->address; 535 struct vm_area_struct *vma; 536 537 /* 538 * It is not an accident that whenever we want to break COW 539 * to undo, we also need to drop a reference to the anon_vma. 540 */ 541 put_anon_vma(rmap_item->anon_vma); 542 543 mmap_read_lock(mm); 544 vma = find_mergeable_vma(mm, addr); 545 if (vma) 546 break_ksm(vma, addr); 547 mmap_read_unlock(mm); 548 } 549 550 static struct page *get_mergeable_page(struct rmap_item *rmap_item) 551 { 552 struct mm_struct *mm = rmap_item->mm; 553 unsigned long addr = rmap_item->address; 554 struct vm_area_struct *vma; 555 struct page *page; 556 557 mmap_read_lock(mm); 558 vma = find_mergeable_vma(mm, addr); 559 if (!vma) 560 goto out; 561 562 page = follow_page(vma, addr, FOLL_GET); 563 if (IS_ERR_OR_NULL(page) || is_zone_device_page(page)) 564 goto out; 565 if (PageAnon(page)) { 566 flush_anon_page(vma, page, addr); 567 flush_dcache_page(page); 568 } else { 569 put_page(page); 570 out: 571 page = NULL; 572 } 573 mmap_read_unlock(mm); 574 return page; 575 } 576 577 /* 578 * This helper is used for getting right index into array of tree roots. 579 * When merge_across_nodes knob is set to 1, there are only two rb-trees for 580 * stable and unstable pages from all nodes with roots in index 0. Otherwise, 581 * every node has its own stable and unstable tree. 582 */ 583 static inline int get_kpfn_nid(unsigned long kpfn) 584 { 585 return ksm_merge_across_nodes ? 0 : NUMA(pfn_to_nid(kpfn)); 586 } 587 588 static struct stable_node *alloc_stable_node_chain(struct stable_node *dup, 589 struct rb_root *root) 590 { 591 struct stable_node *chain = alloc_stable_node(); 592 VM_BUG_ON(is_stable_node_chain(dup)); 593 if (likely(chain)) { 594 INIT_HLIST_HEAD(&chain->hlist); 595 chain->chain_prune_time = jiffies; 596 chain->rmap_hlist_len = STABLE_NODE_CHAIN; 597 #if defined (CONFIG_DEBUG_VM) && defined(CONFIG_NUMA) 598 chain->nid = NUMA_NO_NODE; /* debug */ 599 #endif 600 ksm_stable_node_chains++; 601 602 /* 603 * Put the stable node chain in the first dimension of 604 * the stable tree and at the same time remove the old 605 * stable node. 606 */ 607 rb_replace_node(&dup->node, &chain->node, root); 608 609 /* 610 * Move the old stable node to the second dimension 611 * queued in the hlist_dup. The invariant is that all 612 * dup stable_nodes in the chain->hlist point to pages 613 * that are write protected and have the exact same 614 * content. 615 */ 616 stable_node_chain_add_dup(dup, chain); 617 } 618 return chain; 619 } 620 621 static inline void free_stable_node_chain(struct stable_node *chain, 622 struct rb_root *root) 623 { 624 rb_erase(&chain->node, root); 625 free_stable_node(chain); 626 ksm_stable_node_chains--; 627 } 628 629 static void remove_node_from_stable_tree(struct stable_node *stable_node) 630 { 631 struct rmap_item *rmap_item; 632 633 /* check it's not STABLE_NODE_CHAIN or negative */ 634 BUG_ON(stable_node->rmap_hlist_len < 0); 635 636 hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) { 637 if (rmap_item->hlist.next) 638 ksm_pages_sharing--; 639 else 640 ksm_pages_shared--; 641 642 rmap_item->mm->ksm_merging_pages--; 643 644 VM_BUG_ON(stable_node->rmap_hlist_len <= 0); 645 stable_node->rmap_hlist_len--; 646 put_anon_vma(rmap_item->anon_vma); 647 rmap_item->address &= PAGE_MASK; 648 cond_resched(); 649 } 650 651 /* 652 * We need the second aligned pointer of the migrate_nodes 653 * list_head to stay clear from the rb_parent_color union 654 * (aligned and different than any node) and also different 655 * from &migrate_nodes. This will verify that future list.h changes 656 * don't break STABLE_NODE_DUP_HEAD. Only recent gcc can handle it. 657 */ 658 BUILD_BUG_ON(STABLE_NODE_DUP_HEAD <= &migrate_nodes); 659 BUILD_BUG_ON(STABLE_NODE_DUP_HEAD >= &migrate_nodes + 1); 660 661 if (stable_node->head == &migrate_nodes) 662 list_del(&stable_node->list); 663 else 664 stable_node_dup_del(stable_node); 665 free_stable_node(stable_node); 666 } 667 668 enum get_ksm_page_flags { 669 GET_KSM_PAGE_NOLOCK, 670 GET_KSM_PAGE_LOCK, 671 GET_KSM_PAGE_TRYLOCK 672 }; 673 674 /* 675 * get_ksm_page: checks if the page indicated by the stable node 676 * is still its ksm page, despite having held no reference to it. 677 * In which case we can trust the content of the page, and it 678 * returns the gotten page; but if the page has now been zapped, 679 * remove the stale node from the stable tree and return NULL. 680 * But beware, the stable node's page might be being migrated. 681 * 682 * You would expect the stable_node to hold a reference to the ksm page. 683 * But if it increments the page's count, swapping out has to wait for 684 * ksmd to come around again before it can free the page, which may take 685 * seconds or even minutes: much too unresponsive. So instead we use a 686 * "keyhole reference": access to the ksm page from the stable node peeps 687 * out through its keyhole to see if that page still holds the right key, 688 * pointing back to this stable node. This relies on freeing a PageAnon 689 * page to reset its page->mapping to NULL, and relies on no other use of 690 * a page to put something that might look like our key in page->mapping. 691 * is on its way to being freed; but it is an anomaly to bear in mind. 692 */ 693 static struct page *get_ksm_page(struct stable_node *stable_node, 694 enum get_ksm_page_flags flags) 695 { 696 struct page *page; 697 void *expected_mapping; 698 unsigned long kpfn; 699 700 expected_mapping = (void *)((unsigned long)stable_node | 701 PAGE_MAPPING_KSM); 702 again: 703 kpfn = READ_ONCE(stable_node->kpfn); /* Address dependency. */ 704 page = pfn_to_page(kpfn); 705 if (READ_ONCE(page->mapping) != expected_mapping) 706 goto stale; 707 708 /* 709 * We cannot do anything with the page while its refcount is 0. 710 * Usually 0 means free, or tail of a higher-order page: in which 711 * case this node is no longer referenced, and should be freed; 712 * however, it might mean that the page is under page_ref_freeze(). 713 * The __remove_mapping() case is easy, again the node is now stale; 714 * the same is in reuse_ksm_page() case; but if page is swapcache 715 * in folio_migrate_mapping(), it might still be our page, 716 * in which case it's essential to keep the node. 717 */ 718 while (!get_page_unless_zero(page)) { 719 /* 720 * Another check for page->mapping != expected_mapping would 721 * work here too. We have chosen the !PageSwapCache test to 722 * optimize the common case, when the page is or is about to 723 * be freed: PageSwapCache is cleared (under spin_lock_irq) 724 * in the ref_freeze section of __remove_mapping(); but Anon 725 * page->mapping reset to NULL later, in free_pages_prepare(). 726 */ 727 if (!PageSwapCache(page)) 728 goto stale; 729 cpu_relax(); 730 } 731 732 if (READ_ONCE(page->mapping) != expected_mapping) { 733 put_page(page); 734 goto stale; 735 } 736 737 if (flags == GET_KSM_PAGE_TRYLOCK) { 738 if (!trylock_page(page)) { 739 put_page(page); 740 return ERR_PTR(-EBUSY); 741 } 742 } else if (flags == GET_KSM_PAGE_LOCK) 743 lock_page(page); 744 745 if (flags != GET_KSM_PAGE_NOLOCK) { 746 if (READ_ONCE(page->mapping) != expected_mapping) { 747 unlock_page(page); 748 put_page(page); 749 goto stale; 750 } 751 } 752 return page; 753 754 stale: 755 /* 756 * We come here from above when page->mapping or !PageSwapCache 757 * suggests that the node is stale; but it might be under migration. 758 * We need smp_rmb(), matching the smp_wmb() in folio_migrate_ksm(), 759 * before checking whether node->kpfn has been changed. 760 */ 761 smp_rmb(); 762 if (READ_ONCE(stable_node->kpfn) != kpfn) 763 goto again; 764 remove_node_from_stable_tree(stable_node); 765 return NULL; 766 } 767 768 /* 769 * Removing rmap_item from stable or unstable tree. 770 * This function will clean the information from the stable/unstable tree. 771 */ 772 static void remove_rmap_item_from_tree(struct rmap_item *rmap_item) 773 { 774 if (rmap_item->address & STABLE_FLAG) { 775 struct stable_node *stable_node; 776 struct page *page; 777 778 stable_node = rmap_item->head; 779 page = get_ksm_page(stable_node, GET_KSM_PAGE_LOCK); 780 if (!page) 781 goto out; 782 783 hlist_del(&rmap_item->hlist); 784 unlock_page(page); 785 put_page(page); 786 787 if (!hlist_empty(&stable_node->hlist)) 788 ksm_pages_sharing--; 789 else 790 ksm_pages_shared--; 791 792 rmap_item->mm->ksm_merging_pages--; 793 794 VM_BUG_ON(stable_node->rmap_hlist_len <= 0); 795 stable_node->rmap_hlist_len--; 796 797 put_anon_vma(rmap_item->anon_vma); 798 rmap_item->head = NULL; 799 rmap_item->address &= PAGE_MASK; 800 801 } else if (rmap_item->address & UNSTABLE_FLAG) { 802 unsigned char age; 803 /* 804 * Usually ksmd can and must skip the rb_erase, because 805 * root_unstable_tree was already reset to RB_ROOT. 806 * But be careful when an mm is exiting: do the rb_erase 807 * if this rmap_item was inserted by this scan, rather 808 * than left over from before. 809 */ 810 age = (unsigned char)(ksm_scan.seqnr - rmap_item->address); 811 BUG_ON(age > 1); 812 if (!age) 813 rb_erase(&rmap_item->node, 814 root_unstable_tree + NUMA(rmap_item->nid)); 815 ksm_pages_unshared--; 816 rmap_item->address &= PAGE_MASK; 817 } 818 out: 819 cond_resched(); /* we're called from many long loops */ 820 } 821 822 static void remove_trailing_rmap_items(struct rmap_item **rmap_list) 823 { 824 while (*rmap_list) { 825 struct rmap_item *rmap_item = *rmap_list; 826 *rmap_list = rmap_item->rmap_list; 827 remove_rmap_item_from_tree(rmap_item); 828 free_rmap_item(rmap_item); 829 } 830 } 831 832 /* 833 * Though it's very tempting to unmerge rmap_items from stable tree rather 834 * than check every pte of a given vma, the locking doesn't quite work for 835 * that - an rmap_item is assigned to the stable tree after inserting ksm 836 * page and upping mmap_lock. Nor does it fit with the way we skip dup'ing 837 * rmap_items from parent to child at fork time (so as not to waste time 838 * if exit comes before the next scan reaches it). 839 * 840 * Similarly, although we'd like to remove rmap_items (so updating counts 841 * and freeing memory) when unmerging an area, it's easier to leave that 842 * to the next pass of ksmd - consider, for example, how ksmd might be 843 * in cmp_and_merge_page on one of the rmap_items we would be removing. 844 */ 845 static int unmerge_ksm_pages(struct vm_area_struct *vma, 846 unsigned long start, unsigned long end) 847 { 848 unsigned long addr; 849 int err = 0; 850 851 for (addr = start; addr < end && !err; addr += PAGE_SIZE) { 852 if (ksm_test_exit(vma->vm_mm)) 853 break; 854 if (signal_pending(current)) 855 err = -ERESTARTSYS; 856 else 857 err = break_ksm(vma, addr); 858 } 859 return err; 860 } 861 862 static inline struct stable_node *folio_stable_node(struct folio *folio) 863 { 864 return folio_test_ksm(folio) ? folio_raw_mapping(folio) : NULL; 865 } 866 867 static inline struct stable_node *page_stable_node(struct page *page) 868 { 869 return folio_stable_node(page_folio(page)); 870 } 871 872 static inline void set_page_stable_node(struct page *page, 873 struct stable_node *stable_node) 874 { 875 VM_BUG_ON_PAGE(PageAnon(page) && PageAnonExclusive(page), page); 876 page->mapping = (void *)((unsigned long)stable_node | PAGE_MAPPING_KSM); 877 } 878 879 #ifdef CONFIG_SYSFS 880 /* 881 * Only called through the sysfs control interface: 882 */ 883 static int remove_stable_node(struct stable_node *stable_node) 884 { 885 struct page *page; 886 int err; 887 888 page = get_ksm_page(stable_node, GET_KSM_PAGE_LOCK); 889 if (!page) { 890 /* 891 * get_ksm_page did remove_node_from_stable_tree itself. 892 */ 893 return 0; 894 } 895 896 /* 897 * Page could be still mapped if this races with __mmput() running in 898 * between ksm_exit() and exit_mmap(). Just refuse to let 899 * merge_across_nodes/max_page_sharing be switched. 900 */ 901 err = -EBUSY; 902 if (!page_mapped(page)) { 903 /* 904 * The stable node did not yet appear stale to get_ksm_page(), 905 * since that allows for an unmapped ksm page to be recognized 906 * right up until it is freed; but the node is safe to remove. 907 * This page might be in a pagevec waiting to be freed, 908 * or it might be PageSwapCache (perhaps under writeback), 909 * or it might have been removed from swapcache a moment ago. 910 */ 911 set_page_stable_node(page, NULL); 912 remove_node_from_stable_tree(stable_node); 913 err = 0; 914 } 915 916 unlock_page(page); 917 put_page(page); 918 return err; 919 } 920 921 static int remove_stable_node_chain(struct stable_node *stable_node, 922 struct rb_root *root) 923 { 924 struct stable_node *dup; 925 struct hlist_node *hlist_safe; 926 927 if (!is_stable_node_chain(stable_node)) { 928 VM_BUG_ON(is_stable_node_dup(stable_node)); 929 if (remove_stable_node(stable_node)) 930 return true; 931 else 932 return false; 933 } 934 935 hlist_for_each_entry_safe(dup, hlist_safe, 936 &stable_node->hlist, hlist_dup) { 937 VM_BUG_ON(!is_stable_node_dup(dup)); 938 if (remove_stable_node(dup)) 939 return true; 940 } 941 BUG_ON(!hlist_empty(&stable_node->hlist)); 942 free_stable_node_chain(stable_node, root); 943 return false; 944 } 945 946 static int remove_all_stable_nodes(void) 947 { 948 struct stable_node *stable_node, *next; 949 int nid; 950 int err = 0; 951 952 for (nid = 0; nid < ksm_nr_node_ids; nid++) { 953 while (root_stable_tree[nid].rb_node) { 954 stable_node = rb_entry(root_stable_tree[nid].rb_node, 955 struct stable_node, node); 956 if (remove_stable_node_chain(stable_node, 957 root_stable_tree + nid)) { 958 err = -EBUSY; 959 break; /* proceed to next nid */ 960 } 961 cond_resched(); 962 } 963 } 964 list_for_each_entry_safe(stable_node, next, &migrate_nodes, list) { 965 if (remove_stable_node(stable_node)) 966 err = -EBUSY; 967 cond_resched(); 968 } 969 return err; 970 } 971 972 static int unmerge_and_remove_all_rmap_items(void) 973 { 974 struct mm_slot *mm_slot; 975 struct mm_struct *mm; 976 struct vm_area_struct *vma; 977 int err = 0; 978 979 spin_lock(&ksm_mmlist_lock); 980 ksm_scan.mm_slot = list_entry(ksm_mm_head.mm_list.next, 981 struct mm_slot, mm_list); 982 spin_unlock(&ksm_mmlist_lock); 983 984 for (mm_slot = ksm_scan.mm_slot; 985 mm_slot != &ksm_mm_head; mm_slot = ksm_scan.mm_slot) { 986 mm = mm_slot->mm; 987 mmap_read_lock(mm); 988 for (vma = mm->mmap; vma; vma = vma->vm_next) { 989 if (ksm_test_exit(mm)) 990 break; 991 if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma) 992 continue; 993 err = unmerge_ksm_pages(vma, 994 vma->vm_start, vma->vm_end); 995 if (err) 996 goto error; 997 } 998 999 remove_trailing_rmap_items(&mm_slot->rmap_list); 1000 mmap_read_unlock(mm); 1001 1002 spin_lock(&ksm_mmlist_lock); 1003 ksm_scan.mm_slot = list_entry(mm_slot->mm_list.next, 1004 struct mm_slot, mm_list); 1005 if (ksm_test_exit(mm)) { 1006 hash_del(&mm_slot->link); 1007 list_del(&mm_slot->mm_list); 1008 spin_unlock(&ksm_mmlist_lock); 1009 1010 free_mm_slot(mm_slot); 1011 clear_bit(MMF_VM_MERGEABLE, &mm->flags); 1012 mmdrop(mm); 1013 } else 1014 spin_unlock(&ksm_mmlist_lock); 1015 } 1016 1017 /* Clean up stable nodes, but don't worry if some are still busy */ 1018 remove_all_stable_nodes(); 1019 ksm_scan.seqnr = 0; 1020 return 0; 1021 1022 error: 1023 mmap_read_unlock(mm); 1024 spin_lock(&ksm_mmlist_lock); 1025 ksm_scan.mm_slot = &ksm_mm_head; 1026 spin_unlock(&ksm_mmlist_lock); 1027 return err; 1028 } 1029 #endif /* CONFIG_SYSFS */ 1030 1031 static u32 calc_checksum(struct page *page) 1032 { 1033 u32 checksum; 1034 void *addr = kmap_atomic(page); 1035 checksum = xxhash(addr, PAGE_SIZE, 0); 1036 kunmap_atomic(addr); 1037 return checksum; 1038 } 1039 1040 static int write_protect_page(struct vm_area_struct *vma, struct page *page, 1041 pte_t *orig_pte) 1042 { 1043 struct mm_struct *mm = vma->vm_mm; 1044 DEFINE_PAGE_VMA_WALK(pvmw, page, vma, 0, 0); 1045 int swapped; 1046 int err = -EFAULT; 1047 struct mmu_notifier_range range; 1048 bool anon_exclusive; 1049 1050 pvmw.address = page_address_in_vma(page, vma); 1051 if (pvmw.address == -EFAULT) 1052 goto out; 1053 1054 BUG_ON(PageTransCompound(page)); 1055 1056 mmu_notifier_range_init(&range, MMU_NOTIFY_CLEAR, 0, vma, mm, 1057 pvmw.address, 1058 pvmw.address + PAGE_SIZE); 1059 mmu_notifier_invalidate_range_start(&range); 1060 1061 if (!page_vma_mapped_walk(&pvmw)) 1062 goto out_mn; 1063 if (WARN_ONCE(!pvmw.pte, "Unexpected PMD mapping?")) 1064 goto out_unlock; 1065 1066 anon_exclusive = PageAnonExclusive(page); 1067 if (pte_write(*pvmw.pte) || pte_dirty(*pvmw.pte) || 1068 (pte_protnone(*pvmw.pte) && pte_savedwrite(*pvmw.pte)) || 1069 anon_exclusive || mm_tlb_flush_pending(mm)) { 1070 pte_t entry; 1071 1072 swapped = PageSwapCache(page); 1073 flush_cache_page(vma, pvmw.address, page_to_pfn(page)); 1074 /* 1075 * Ok this is tricky, when get_user_pages_fast() run it doesn't 1076 * take any lock, therefore the check that we are going to make 1077 * with the pagecount against the mapcount is racy and 1078 * O_DIRECT can happen right after the check. 1079 * So we clear the pte and flush the tlb before the check 1080 * this assure us that no O_DIRECT can happen after the check 1081 * or in the middle of the check. 1082 * 1083 * No need to notify as we are downgrading page table to read 1084 * only not changing it to point to a new page. 1085 * 1086 * See Documentation/mm/mmu_notifier.rst 1087 */ 1088 entry = ptep_clear_flush(vma, pvmw.address, pvmw.pte); 1089 /* 1090 * Check that no O_DIRECT or similar I/O is in progress on the 1091 * page 1092 */ 1093 if (page_mapcount(page) + 1 + swapped != page_count(page)) { 1094 set_pte_at(mm, pvmw.address, pvmw.pte, entry); 1095 goto out_unlock; 1096 } 1097 1098 /* See page_try_share_anon_rmap(): clear PTE first. */ 1099 if (anon_exclusive && page_try_share_anon_rmap(page)) { 1100 set_pte_at(mm, pvmw.address, pvmw.pte, entry); 1101 goto out_unlock; 1102 } 1103 1104 if (pte_dirty(entry)) 1105 set_page_dirty(page); 1106 1107 if (pte_protnone(entry)) 1108 entry = pte_mkclean(pte_clear_savedwrite(entry)); 1109 else 1110 entry = pte_mkclean(pte_wrprotect(entry)); 1111 set_pte_at_notify(mm, pvmw.address, pvmw.pte, entry); 1112 } 1113 *orig_pte = *pvmw.pte; 1114 err = 0; 1115 1116 out_unlock: 1117 page_vma_mapped_walk_done(&pvmw); 1118 out_mn: 1119 mmu_notifier_invalidate_range_end(&range); 1120 out: 1121 return err; 1122 } 1123 1124 /** 1125 * replace_page - replace page in vma by new ksm page 1126 * @vma: vma that holds the pte pointing to page 1127 * @page: the page we are replacing by kpage 1128 * @kpage: the ksm page we replace page by 1129 * @orig_pte: the original value of the pte 1130 * 1131 * Returns 0 on success, -EFAULT on failure. 1132 */ 1133 static int replace_page(struct vm_area_struct *vma, struct page *page, 1134 struct page *kpage, pte_t orig_pte) 1135 { 1136 struct mm_struct *mm = vma->vm_mm; 1137 pmd_t *pmd; 1138 pmd_t pmde; 1139 pte_t *ptep; 1140 pte_t newpte; 1141 spinlock_t *ptl; 1142 unsigned long addr; 1143 int err = -EFAULT; 1144 struct mmu_notifier_range range; 1145 1146 addr = page_address_in_vma(page, vma); 1147 if (addr == -EFAULT) 1148 goto out; 1149 1150 pmd = mm_find_pmd(mm, addr); 1151 if (!pmd) 1152 goto out; 1153 /* 1154 * Some THP functions use the sequence pmdp_huge_clear_flush(), set_pmd_at() 1155 * without holding anon_vma lock for write. So when looking for a 1156 * genuine pmde (in which to find pte), test present and !THP together. 1157 */ 1158 pmde = *pmd; 1159 barrier(); 1160 if (!pmd_present(pmde) || pmd_trans_huge(pmde)) 1161 goto out; 1162 1163 mmu_notifier_range_init(&range, MMU_NOTIFY_CLEAR, 0, vma, mm, addr, 1164 addr + PAGE_SIZE); 1165 mmu_notifier_invalidate_range_start(&range); 1166 1167 ptep = pte_offset_map_lock(mm, pmd, addr, &ptl); 1168 if (!pte_same(*ptep, orig_pte)) { 1169 pte_unmap_unlock(ptep, ptl); 1170 goto out_mn; 1171 } 1172 VM_BUG_ON_PAGE(PageAnonExclusive(page), page); 1173 VM_BUG_ON_PAGE(PageAnon(kpage) && PageAnonExclusive(kpage), kpage); 1174 1175 /* 1176 * No need to check ksm_use_zero_pages here: we can only have a 1177 * zero_page here if ksm_use_zero_pages was enabled already. 1178 */ 1179 if (!is_zero_pfn(page_to_pfn(kpage))) { 1180 get_page(kpage); 1181 page_add_anon_rmap(kpage, vma, addr, RMAP_NONE); 1182 newpte = mk_pte(kpage, vma->vm_page_prot); 1183 } else { 1184 newpte = pte_mkspecial(pfn_pte(page_to_pfn(kpage), 1185 vma->vm_page_prot)); 1186 /* 1187 * We're replacing an anonymous page with a zero page, which is 1188 * not anonymous. We need to do proper accounting otherwise we 1189 * will get wrong values in /proc, and a BUG message in dmesg 1190 * when tearing down the mm. 1191 */ 1192 dec_mm_counter(mm, MM_ANONPAGES); 1193 } 1194 1195 flush_cache_page(vma, addr, pte_pfn(*ptep)); 1196 /* 1197 * No need to notify as we are replacing a read only page with another 1198 * read only page with the same content. 1199 * 1200 * See Documentation/mm/mmu_notifier.rst 1201 */ 1202 ptep_clear_flush(vma, addr, ptep); 1203 set_pte_at_notify(mm, addr, ptep, newpte); 1204 1205 page_remove_rmap(page, vma, false); 1206 if (!page_mapped(page)) 1207 try_to_free_swap(page); 1208 put_page(page); 1209 1210 pte_unmap_unlock(ptep, ptl); 1211 err = 0; 1212 out_mn: 1213 mmu_notifier_invalidate_range_end(&range); 1214 out: 1215 return err; 1216 } 1217 1218 /* 1219 * try_to_merge_one_page - take two pages and merge them into one 1220 * @vma: the vma that holds the pte pointing to page 1221 * @page: the PageAnon page that we want to replace with kpage 1222 * @kpage: the PageKsm page that we want to map instead of page, 1223 * or NULL the first time when we want to use page as kpage. 1224 * 1225 * This function returns 0 if the pages were merged, -EFAULT otherwise. 1226 */ 1227 static int try_to_merge_one_page(struct vm_area_struct *vma, 1228 struct page *page, struct page *kpage) 1229 { 1230 pte_t orig_pte = __pte(0); 1231 int err = -EFAULT; 1232 1233 if (page == kpage) /* ksm page forked */ 1234 return 0; 1235 1236 if (!PageAnon(page)) 1237 goto out; 1238 1239 /* 1240 * We need the page lock to read a stable PageSwapCache in 1241 * write_protect_page(). We use trylock_page() instead of 1242 * lock_page() because we don't want to wait here - we 1243 * prefer to continue scanning and merging different pages, 1244 * then come back to this page when it is unlocked. 1245 */ 1246 if (!trylock_page(page)) 1247 goto out; 1248 1249 if (PageTransCompound(page)) { 1250 if (split_huge_page(page)) 1251 goto out_unlock; 1252 } 1253 1254 /* 1255 * If this anonymous page is mapped only here, its pte may need 1256 * to be write-protected. If it's mapped elsewhere, all of its 1257 * ptes are necessarily already write-protected. But in either 1258 * case, we need to lock and check page_count is not raised. 1259 */ 1260 if (write_protect_page(vma, page, &orig_pte) == 0) { 1261 if (!kpage) { 1262 /* 1263 * While we hold page lock, upgrade page from 1264 * PageAnon+anon_vma to PageKsm+NULL stable_node: 1265 * stable_tree_insert() will update stable_node. 1266 */ 1267 set_page_stable_node(page, NULL); 1268 mark_page_accessed(page); 1269 /* 1270 * Page reclaim just frees a clean page with no dirty 1271 * ptes: make sure that the ksm page would be swapped. 1272 */ 1273 if (!PageDirty(page)) 1274 SetPageDirty(page); 1275 err = 0; 1276 } else if (pages_identical(page, kpage)) 1277 err = replace_page(vma, page, kpage, orig_pte); 1278 } 1279 1280 out_unlock: 1281 unlock_page(page); 1282 out: 1283 return err; 1284 } 1285 1286 /* 1287 * try_to_merge_with_ksm_page - like try_to_merge_two_pages, 1288 * but no new kernel page is allocated: kpage must already be a ksm page. 1289 * 1290 * This function returns 0 if the pages were merged, -EFAULT otherwise. 1291 */ 1292 static int try_to_merge_with_ksm_page(struct rmap_item *rmap_item, 1293 struct page *page, struct page *kpage) 1294 { 1295 struct mm_struct *mm = rmap_item->mm; 1296 struct vm_area_struct *vma; 1297 int err = -EFAULT; 1298 1299 mmap_read_lock(mm); 1300 vma = find_mergeable_vma(mm, rmap_item->address); 1301 if (!vma) 1302 goto out; 1303 1304 err = try_to_merge_one_page(vma, page, kpage); 1305 if (err) 1306 goto out; 1307 1308 /* Unstable nid is in union with stable anon_vma: remove first */ 1309 remove_rmap_item_from_tree(rmap_item); 1310 1311 /* Must get reference to anon_vma while still holding mmap_lock */ 1312 rmap_item->anon_vma = vma->anon_vma; 1313 get_anon_vma(vma->anon_vma); 1314 out: 1315 mmap_read_unlock(mm); 1316 return err; 1317 } 1318 1319 /* 1320 * try_to_merge_two_pages - take two identical pages and prepare them 1321 * to be merged into one page. 1322 * 1323 * This function returns the kpage if we successfully merged two identical 1324 * pages into one ksm page, NULL otherwise. 1325 * 1326 * Note that this function upgrades page to ksm page: if one of the pages 1327 * is already a ksm page, try_to_merge_with_ksm_page should be used. 1328 */ 1329 static struct page *try_to_merge_two_pages(struct rmap_item *rmap_item, 1330 struct page *page, 1331 struct rmap_item *tree_rmap_item, 1332 struct page *tree_page) 1333 { 1334 int err; 1335 1336 err = try_to_merge_with_ksm_page(rmap_item, page, NULL); 1337 if (!err) { 1338 err = try_to_merge_with_ksm_page(tree_rmap_item, 1339 tree_page, page); 1340 /* 1341 * If that fails, we have a ksm page with only one pte 1342 * pointing to it: so break it. 1343 */ 1344 if (err) 1345 break_cow(rmap_item); 1346 } 1347 return err ? NULL : page; 1348 } 1349 1350 static __always_inline 1351 bool __is_page_sharing_candidate(struct stable_node *stable_node, int offset) 1352 { 1353 VM_BUG_ON(stable_node->rmap_hlist_len < 0); 1354 /* 1355 * Check that at least one mapping still exists, otherwise 1356 * there's no much point to merge and share with this 1357 * stable_node, as the underlying tree_page of the other 1358 * sharer is going to be freed soon. 1359 */ 1360 return stable_node->rmap_hlist_len && 1361 stable_node->rmap_hlist_len + offset < ksm_max_page_sharing; 1362 } 1363 1364 static __always_inline 1365 bool is_page_sharing_candidate(struct stable_node *stable_node) 1366 { 1367 return __is_page_sharing_candidate(stable_node, 0); 1368 } 1369 1370 static struct page *stable_node_dup(struct stable_node **_stable_node_dup, 1371 struct stable_node **_stable_node, 1372 struct rb_root *root, 1373 bool prune_stale_stable_nodes) 1374 { 1375 struct stable_node *dup, *found = NULL, *stable_node = *_stable_node; 1376 struct hlist_node *hlist_safe; 1377 struct page *_tree_page, *tree_page = NULL; 1378 int nr = 0; 1379 int found_rmap_hlist_len; 1380 1381 if (!prune_stale_stable_nodes || 1382 time_before(jiffies, stable_node->chain_prune_time + 1383 msecs_to_jiffies( 1384 ksm_stable_node_chains_prune_millisecs))) 1385 prune_stale_stable_nodes = false; 1386 else 1387 stable_node->chain_prune_time = jiffies; 1388 1389 hlist_for_each_entry_safe(dup, hlist_safe, 1390 &stable_node->hlist, hlist_dup) { 1391 cond_resched(); 1392 /* 1393 * We must walk all stable_node_dup to prune the stale 1394 * stable nodes during lookup. 1395 * 1396 * get_ksm_page can drop the nodes from the 1397 * stable_node->hlist if they point to freed pages 1398 * (that's why we do a _safe walk). The "dup" 1399 * stable_node parameter itself will be freed from 1400 * under us if it returns NULL. 1401 */ 1402 _tree_page = get_ksm_page(dup, GET_KSM_PAGE_NOLOCK); 1403 if (!_tree_page) 1404 continue; 1405 nr += 1; 1406 if (is_page_sharing_candidate(dup)) { 1407 if (!found || 1408 dup->rmap_hlist_len > found_rmap_hlist_len) { 1409 if (found) 1410 put_page(tree_page); 1411 found = dup; 1412 found_rmap_hlist_len = found->rmap_hlist_len; 1413 tree_page = _tree_page; 1414 1415 /* skip put_page for found dup */ 1416 if (!prune_stale_stable_nodes) 1417 break; 1418 continue; 1419 } 1420 } 1421 put_page(_tree_page); 1422 } 1423 1424 if (found) { 1425 /* 1426 * nr is counting all dups in the chain only if 1427 * prune_stale_stable_nodes is true, otherwise we may 1428 * break the loop at nr == 1 even if there are 1429 * multiple entries. 1430 */ 1431 if (prune_stale_stable_nodes && nr == 1) { 1432 /* 1433 * If there's not just one entry it would 1434 * corrupt memory, better BUG_ON. In KSM 1435 * context with no lock held it's not even 1436 * fatal. 1437 */ 1438 BUG_ON(stable_node->hlist.first->next); 1439 1440 /* 1441 * There's just one entry and it is below the 1442 * deduplication limit so drop the chain. 1443 */ 1444 rb_replace_node(&stable_node->node, &found->node, 1445 root); 1446 free_stable_node(stable_node); 1447 ksm_stable_node_chains--; 1448 ksm_stable_node_dups--; 1449 /* 1450 * NOTE: the caller depends on the stable_node 1451 * to be equal to stable_node_dup if the chain 1452 * was collapsed. 1453 */ 1454 *_stable_node = found; 1455 /* 1456 * Just for robustness, as stable_node is 1457 * otherwise left as a stable pointer, the 1458 * compiler shall optimize it away at build 1459 * time. 1460 */ 1461 stable_node = NULL; 1462 } else if (stable_node->hlist.first != &found->hlist_dup && 1463 __is_page_sharing_candidate(found, 1)) { 1464 /* 1465 * If the found stable_node dup can accept one 1466 * more future merge (in addition to the one 1467 * that is underway) and is not at the head of 1468 * the chain, put it there so next search will 1469 * be quicker in the !prune_stale_stable_nodes 1470 * case. 1471 * 1472 * NOTE: it would be inaccurate to use nr > 1 1473 * instead of checking the hlist.first pointer 1474 * directly, because in the 1475 * prune_stale_stable_nodes case "nr" isn't 1476 * the position of the found dup in the chain, 1477 * but the total number of dups in the chain. 1478 */ 1479 hlist_del(&found->hlist_dup); 1480 hlist_add_head(&found->hlist_dup, 1481 &stable_node->hlist); 1482 } 1483 } 1484 1485 *_stable_node_dup = found; 1486 return tree_page; 1487 } 1488 1489 static struct stable_node *stable_node_dup_any(struct stable_node *stable_node, 1490 struct rb_root *root) 1491 { 1492 if (!is_stable_node_chain(stable_node)) 1493 return stable_node; 1494 if (hlist_empty(&stable_node->hlist)) { 1495 free_stable_node_chain(stable_node, root); 1496 return NULL; 1497 } 1498 return hlist_entry(stable_node->hlist.first, 1499 typeof(*stable_node), hlist_dup); 1500 } 1501 1502 /* 1503 * Like for get_ksm_page, this function can free the *_stable_node and 1504 * *_stable_node_dup if the returned tree_page is NULL. 1505 * 1506 * It can also free and overwrite *_stable_node with the found 1507 * stable_node_dup if the chain is collapsed (in which case 1508 * *_stable_node will be equal to *_stable_node_dup like if the chain 1509 * never existed). It's up to the caller to verify tree_page is not 1510 * NULL before dereferencing *_stable_node or *_stable_node_dup. 1511 * 1512 * *_stable_node_dup is really a second output parameter of this 1513 * function and will be overwritten in all cases, the caller doesn't 1514 * need to initialize it. 1515 */ 1516 static struct page *__stable_node_chain(struct stable_node **_stable_node_dup, 1517 struct stable_node **_stable_node, 1518 struct rb_root *root, 1519 bool prune_stale_stable_nodes) 1520 { 1521 struct stable_node *stable_node = *_stable_node; 1522 if (!is_stable_node_chain(stable_node)) { 1523 if (is_page_sharing_candidate(stable_node)) { 1524 *_stable_node_dup = stable_node; 1525 return get_ksm_page(stable_node, GET_KSM_PAGE_NOLOCK); 1526 } 1527 /* 1528 * _stable_node_dup set to NULL means the stable_node 1529 * reached the ksm_max_page_sharing limit. 1530 */ 1531 *_stable_node_dup = NULL; 1532 return NULL; 1533 } 1534 return stable_node_dup(_stable_node_dup, _stable_node, root, 1535 prune_stale_stable_nodes); 1536 } 1537 1538 static __always_inline struct page *chain_prune(struct stable_node **s_n_d, 1539 struct stable_node **s_n, 1540 struct rb_root *root) 1541 { 1542 return __stable_node_chain(s_n_d, s_n, root, true); 1543 } 1544 1545 static __always_inline struct page *chain(struct stable_node **s_n_d, 1546 struct stable_node *s_n, 1547 struct rb_root *root) 1548 { 1549 struct stable_node *old_stable_node = s_n; 1550 struct page *tree_page; 1551 1552 tree_page = __stable_node_chain(s_n_d, &s_n, root, false); 1553 /* not pruning dups so s_n cannot have changed */ 1554 VM_BUG_ON(s_n != old_stable_node); 1555 return tree_page; 1556 } 1557 1558 /* 1559 * stable_tree_search - search for page inside the stable tree 1560 * 1561 * This function checks if there is a page inside the stable tree 1562 * with identical content to the page that we are scanning right now. 1563 * 1564 * This function returns the stable tree node of identical content if found, 1565 * NULL otherwise. 1566 */ 1567 static struct page *stable_tree_search(struct page *page) 1568 { 1569 int nid; 1570 struct rb_root *root; 1571 struct rb_node **new; 1572 struct rb_node *parent; 1573 struct stable_node *stable_node, *stable_node_dup, *stable_node_any; 1574 struct stable_node *page_node; 1575 1576 page_node = page_stable_node(page); 1577 if (page_node && page_node->head != &migrate_nodes) { 1578 /* ksm page forked */ 1579 get_page(page); 1580 return page; 1581 } 1582 1583 nid = get_kpfn_nid(page_to_pfn(page)); 1584 root = root_stable_tree + nid; 1585 again: 1586 new = &root->rb_node; 1587 parent = NULL; 1588 1589 while (*new) { 1590 struct page *tree_page; 1591 int ret; 1592 1593 cond_resched(); 1594 stable_node = rb_entry(*new, struct stable_node, node); 1595 stable_node_any = NULL; 1596 tree_page = chain_prune(&stable_node_dup, &stable_node, root); 1597 /* 1598 * NOTE: stable_node may have been freed by 1599 * chain_prune() if the returned stable_node_dup is 1600 * not NULL. stable_node_dup may have been inserted in 1601 * the rbtree instead as a regular stable_node (in 1602 * order to collapse the stable_node chain if a single 1603 * stable_node dup was found in it). In such case the 1604 * stable_node is overwritten by the callee to point 1605 * to the stable_node_dup that was collapsed in the 1606 * stable rbtree and stable_node will be equal to 1607 * stable_node_dup like if the chain never existed. 1608 */ 1609 if (!stable_node_dup) { 1610 /* 1611 * Either all stable_node dups were full in 1612 * this stable_node chain, or this chain was 1613 * empty and should be rb_erased. 1614 */ 1615 stable_node_any = stable_node_dup_any(stable_node, 1616 root); 1617 if (!stable_node_any) { 1618 /* rb_erase just run */ 1619 goto again; 1620 } 1621 /* 1622 * Take any of the stable_node dups page of 1623 * this stable_node chain to let the tree walk 1624 * continue. All KSM pages belonging to the 1625 * stable_node dups in a stable_node chain 1626 * have the same content and they're 1627 * write protected at all times. Any will work 1628 * fine to continue the walk. 1629 */ 1630 tree_page = get_ksm_page(stable_node_any, 1631 GET_KSM_PAGE_NOLOCK); 1632 } 1633 VM_BUG_ON(!stable_node_dup ^ !!stable_node_any); 1634 if (!tree_page) { 1635 /* 1636 * If we walked over a stale stable_node, 1637 * get_ksm_page() will call rb_erase() and it 1638 * may rebalance the tree from under us. So 1639 * restart the search from scratch. Returning 1640 * NULL would be safe too, but we'd generate 1641 * false negative insertions just because some 1642 * stable_node was stale. 1643 */ 1644 goto again; 1645 } 1646 1647 ret = memcmp_pages(page, tree_page); 1648 put_page(tree_page); 1649 1650 parent = *new; 1651 if (ret < 0) 1652 new = &parent->rb_left; 1653 else if (ret > 0) 1654 new = &parent->rb_right; 1655 else { 1656 if (page_node) { 1657 VM_BUG_ON(page_node->head != &migrate_nodes); 1658 /* 1659 * Test if the migrated page should be merged 1660 * into a stable node dup. If the mapcount is 1661 * 1 we can migrate it with another KSM page 1662 * without adding it to the chain. 1663 */ 1664 if (page_mapcount(page) > 1) 1665 goto chain_append; 1666 } 1667 1668 if (!stable_node_dup) { 1669 /* 1670 * If the stable_node is a chain and 1671 * we got a payload match in memcmp 1672 * but we cannot merge the scanned 1673 * page in any of the existing 1674 * stable_node dups because they're 1675 * all full, we need to wait the 1676 * scanned page to find itself a match 1677 * in the unstable tree to create a 1678 * brand new KSM page to add later to 1679 * the dups of this stable_node. 1680 */ 1681 return NULL; 1682 } 1683 1684 /* 1685 * Lock and unlock the stable_node's page (which 1686 * might already have been migrated) so that page 1687 * migration is sure to notice its raised count. 1688 * It would be more elegant to return stable_node 1689 * than kpage, but that involves more changes. 1690 */ 1691 tree_page = get_ksm_page(stable_node_dup, 1692 GET_KSM_PAGE_TRYLOCK); 1693 1694 if (PTR_ERR(tree_page) == -EBUSY) 1695 return ERR_PTR(-EBUSY); 1696 1697 if (unlikely(!tree_page)) 1698 /* 1699 * The tree may have been rebalanced, 1700 * so re-evaluate parent and new. 1701 */ 1702 goto again; 1703 unlock_page(tree_page); 1704 1705 if (get_kpfn_nid(stable_node_dup->kpfn) != 1706 NUMA(stable_node_dup->nid)) { 1707 put_page(tree_page); 1708 goto replace; 1709 } 1710 return tree_page; 1711 } 1712 } 1713 1714 if (!page_node) 1715 return NULL; 1716 1717 list_del(&page_node->list); 1718 DO_NUMA(page_node->nid = nid); 1719 rb_link_node(&page_node->node, parent, new); 1720 rb_insert_color(&page_node->node, root); 1721 out: 1722 if (is_page_sharing_candidate(page_node)) { 1723 get_page(page); 1724 return page; 1725 } else 1726 return NULL; 1727 1728 replace: 1729 /* 1730 * If stable_node was a chain and chain_prune collapsed it, 1731 * stable_node has been updated to be the new regular 1732 * stable_node. A collapse of the chain is indistinguishable 1733 * from the case there was no chain in the stable 1734 * rbtree. Otherwise stable_node is the chain and 1735 * stable_node_dup is the dup to replace. 1736 */ 1737 if (stable_node_dup == stable_node) { 1738 VM_BUG_ON(is_stable_node_chain(stable_node_dup)); 1739 VM_BUG_ON(is_stable_node_dup(stable_node_dup)); 1740 /* there is no chain */ 1741 if (page_node) { 1742 VM_BUG_ON(page_node->head != &migrate_nodes); 1743 list_del(&page_node->list); 1744 DO_NUMA(page_node->nid = nid); 1745 rb_replace_node(&stable_node_dup->node, 1746 &page_node->node, 1747 root); 1748 if (is_page_sharing_candidate(page_node)) 1749 get_page(page); 1750 else 1751 page = NULL; 1752 } else { 1753 rb_erase(&stable_node_dup->node, root); 1754 page = NULL; 1755 } 1756 } else { 1757 VM_BUG_ON(!is_stable_node_chain(stable_node)); 1758 __stable_node_dup_del(stable_node_dup); 1759 if (page_node) { 1760 VM_BUG_ON(page_node->head != &migrate_nodes); 1761 list_del(&page_node->list); 1762 DO_NUMA(page_node->nid = nid); 1763 stable_node_chain_add_dup(page_node, stable_node); 1764 if (is_page_sharing_candidate(page_node)) 1765 get_page(page); 1766 else 1767 page = NULL; 1768 } else { 1769 page = NULL; 1770 } 1771 } 1772 stable_node_dup->head = &migrate_nodes; 1773 list_add(&stable_node_dup->list, stable_node_dup->head); 1774 return page; 1775 1776 chain_append: 1777 /* stable_node_dup could be null if it reached the limit */ 1778 if (!stable_node_dup) 1779 stable_node_dup = stable_node_any; 1780 /* 1781 * If stable_node was a chain and chain_prune collapsed it, 1782 * stable_node has been updated to be the new regular 1783 * stable_node. A collapse of the chain is indistinguishable 1784 * from the case there was no chain in the stable 1785 * rbtree. Otherwise stable_node is the chain and 1786 * stable_node_dup is the dup to replace. 1787 */ 1788 if (stable_node_dup == stable_node) { 1789 VM_BUG_ON(is_stable_node_dup(stable_node_dup)); 1790 /* chain is missing so create it */ 1791 stable_node = alloc_stable_node_chain(stable_node_dup, 1792 root); 1793 if (!stable_node) 1794 return NULL; 1795 } 1796 /* 1797 * Add this stable_node dup that was 1798 * migrated to the stable_node chain 1799 * of the current nid for this page 1800 * content. 1801 */ 1802 VM_BUG_ON(!is_stable_node_dup(stable_node_dup)); 1803 VM_BUG_ON(page_node->head != &migrate_nodes); 1804 list_del(&page_node->list); 1805 DO_NUMA(page_node->nid = nid); 1806 stable_node_chain_add_dup(page_node, stable_node); 1807 goto out; 1808 } 1809 1810 /* 1811 * stable_tree_insert - insert stable tree node pointing to new ksm page 1812 * into the stable tree. 1813 * 1814 * This function returns the stable tree node just allocated on success, 1815 * NULL otherwise. 1816 */ 1817 static struct stable_node *stable_tree_insert(struct page *kpage) 1818 { 1819 int nid; 1820 unsigned long kpfn; 1821 struct rb_root *root; 1822 struct rb_node **new; 1823 struct rb_node *parent; 1824 struct stable_node *stable_node, *stable_node_dup, *stable_node_any; 1825 bool need_chain = false; 1826 1827 kpfn = page_to_pfn(kpage); 1828 nid = get_kpfn_nid(kpfn); 1829 root = root_stable_tree + nid; 1830 again: 1831 parent = NULL; 1832 new = &root->rb_node; 1833 1834 while (*new) { 1835 struct page *tree_page; 1836 int ret; 1837 1838 cond_resched(); 1839 stable_node = rb_entry(*new, struct stable_node, node); 1840 stable_node_any = NULL; 1841 tree_page = chain(&stable_node_dup, stable_node, root); 1842 if (!stable_node_dup) { 1843 /* 1844 * Either all stable_node dups were full in 1845 * this stable_node chain, or this chain was 1846 * empty and should be rb_erased. 1847 */ 1848 stable_node_any = stable_node_dup_any(stable_node, 1849 root); 1850 if (!stable_node_any) { 1851 /* rb_erase just run */ 1852 goto again; 1853 } 1854 /* 1855 * Take any of the stable_node dups page of 1856 * this stable_node chain to let the tree walk 1857 * continue. All KSM pages belonging to the 1858 * stable_node dups in a stable_node chain 1859 * have the same content and they're 1860 * write protected at all times. Any will work 1861 * fine to continue the walk. 1862 */ 1863 tree_page = get_ksm_page(stable_node_any, 1864 GET_KSM_PAGE_NOLOCK); 1865 } 1866 VM_BUG_ON(!stable_node_dup ^ !!stable_node_any); 1867 if (!tree_page) { 1868 /* 1869 * If we walked over a stale stable_node, 1870 * get_ksm_page() will call rb_erase() and it 1871 * may rebalance the tree from under us. So 1872 * restart the search from scratch. Returning 1873 * NULL would be safe too, but we'd generate 1874 * false negative insertions just because some 1875 * stable_node was stale. 1876 */ 1877 goto again; 1878 } 1879 1880 ret = memcmp_pages(kpage, tree_page); 1881 put_page(tree_page); 1882 1883 parent = *new; 1884 if (ret < 0) 1885 new = &parent->rb_left; 1886 else if (ret > 0) 1887 new = &parent->rb_right; 1888 else { 1889 need_chain = true; 1890 break; 1891 } 1892 } 1893 1894 stable_node_dup = alloc_stable_node(); 1895 if (!stable_node_dup) 1896 return NULL; 1897 1898 INIT_HLIST_HEAD(&stable_node_dup->hlist); 1899 stable_node_dup->kpfn = kpfn; 1900 set_page_stable_node(kpage, stable_node_dup); 1901 stable_node_dup->rmap_hlist_len = 0; 1902 DO_NUMA(stable_node_dup->nid = nid); 1903 if (!need_chain) { 1904 rb_link_node(&stable_node_dup->node, parent, new); 1905 rb_insert_color(&stable_node_dup->node, root); 1906 } else { 1907 if (!is_stable_node_chain(stable_node)) { 1908 struct stable_node *orig = stable_node; 1909 /* chain is missing so create it */ 1910 stable_node = alloc_stable_node_chain(orig, root); 1911 if (!stable_node) { 1912 free_stable_node(stable_node_dup); 1913 return NULL; 1914 } 1915 } 1916 stable_node_chain_add_dup(stable_node_dup, stable_node); 1917 } 1918 1919 return stable_node_dup; 1920 } 1921 1922 /* 1923 * unstable_tree_search_insert - search for identical page, 1924 * else insert rmap_item into the unstable tree. 1925 * 1926 * This function searches for a page in the unstable tree identical to the 1927 * page currently being scanned; and if no identical page is found in the 1928 * tree, we insert rmap_item as a new object into the unstable tree. 1929 * 1930 * This function returns pointer to rmap_item found to be identical 1931 * to the currently scanned page, NULL otherwise. 1932 * 1933 * This function does both searching and inserting, because they share 1934 * the same walking algorithm in an rbtree. 1935 */ 1936 static 1937 struct rmap_item *unstable_tree_search_insert(struct rmap_item *rmap_item, 1938 struct page *page, 1939 struct page **tree_pagep) 1940 { 1941 struct rb_node **new; 1942 struct rb_root *root; 1943 struct rb_node *parent = NULL; 1944 int nid; 1945 1946 nid = get_kpfn_nid(page_to_pfn(page)); 1947 root = root_unstable_tree + nid; 1948 new = &root->rb_node; 1949 1950 while (*new) { 1951 struct rmap_item *tree_rmap_item; 1952 struct page *tree_page; 1953 int ret; 1954 1955 cond_resched(); 1956 tree_rmap_item = rb_entry(*new, struct rmap_item, node); 1957 tree_page = get_mergeable_page(tree_rmap_item); 1958 if (!tree_page) 1959 return NULL; 1960 1961 /* 1962 * Don't substitute a ksm page for a forked page. 1963 */ 1964 if (page == tree_page) { 1965 put_page(tree_page); 1966 return NULL; 1967 } 1968 1969 ret = memcmp_pages(page, tree_page); 1970 1971 parent = *new; 1972 if (ret < 0) { 1973 put_page(tree_page); 1974 new = &parent->rb_left; 1975 } else if (ret > 0) { 1976 put_page(tree_page); 1977 new = &parent->rb_right; 1978 } else if (!ksm_merge_across_nodes && 1979 page_to_nid(tree_page) != nid) { 1980 /* 1981 * If tree_page has been migrated to another NUMA node, 1982 * it will be flushed out and put in the right unstable 1983 * tree next time: only merge with it when across_nodes. 1984 */ 1985 put_page(tree_page); 1986 return NULL; 1987 } else { 1988 *tree_pagep = tree_page; 1989 return tree_rmap_item; 1990 } 1991 } 1992 1993 rmap_item->address |= UNSTABLE_FLAG; 1994 rmap_item->address |= (ksm_scan.seqnr & SEQNR_MASK); 1995 DO_NUMA(rmap_item->nid = nid); 1996 rb_link_node(&rmap_item->node, parent, new); 1997 rb_insert_color(&rmap_item->node, root); 1998 1999 ksm_pages_unshared++; 2000 return NULL; 2001 } 2002 2003 /* 2004 * stable_tree_append - add another rmap_item to the linked list of 2005 * rmap_items hanging off a given node of the stable tree, all sharing 2006 * the same ksm page. 2007 */ 2008 static void stable_tree_append(struct rmap_item *rmap_item, 2009 struct stable_node *stable_node, 2010 bool max_page_sharing_bypass) 2011 { 2012 /* 2013 * rmap won't find this mapping if we don't insert the 2014 * rmap_item in the right stable_node 2015 * duplicate. page_migration could break later if rmap breaks, 2016 * so we can as well crash here. We really need to check for 2017 * rmap_hlist_len == STABLE_NODE_CHAIN, but we can as well check 2018 * for other negative values as an underflow if detected here 2019 * for the first time (and not when decreasing rmap_hlist_len) 2020 * would be sign of memory corruption in the stable_node. 2021 */ 2022 BUG_ON(stable_node->rmap_hlist_len < 0); 2023 2024 stable_node->rmap_hlist_len++; 2025 if (!max_page_sharing_bypass) 2026 /* possibly non fatal but unexpected overflow, only warn */ 2027 WARN_ON_ONCE(stable_node->rmap_hlist_len > 2028 ksm_max_page_sharing); 2029 2030 rmap_item->head = stable_node; 2031 rmap_item->address |= STABLE_FLAG; 2032 hlist_add_head(&rmap_item->hlist, &stable_node->hlist); 2033 2034 if (rmap_item->hlist.next) 2035 ksm_pages_sharing++; 2036 else 2037 ksm_pages_shared++; 2038 2039 rmap_item->mm->ksm_merging_pages++; 2040 } 2041 2042 /* 2043 * cmp_and_merge_page - first see if page can be merged into the stable tree; 2044 * if not, compare checksum to previous and if it's the same, see if page can 2045 * be inserted into the unstable tree, or merged with a page already there and 2046 * both transferred to the stable tree. 2047 * 2048 * @page: the page that we are searching identical page to. 2049 * @rmap_item: the reverse mapping into the virtual address of this page 2050 */ 2051 static void cmp_and_merge_page(struct page *page, struct rmap_item *rmap_item) 2052 { 2053 struct mm_struct *mm = rmap_item->mm; 2054 struct rmap_item *tree_rmap_item; 2055 struct page *tree_page = NULL; 2056 struct stable_node *stable_node; 2057 struct page *kpage; 2058 unsigned int checksum; 2059 int err; 2060 bool max_page_sharing_bypass = false; 2061 2062 stable_node = page_stable_node(page); 2063 if (stable_node) { 2064 if (stable_node->head != &migrate_nodes && 2065 get_kpfn_nid(READ_ONCE(stable_node->kpfn)) != 2066 NUMA(stable_node->nid)) { 2067 stable_node_dup_del(stable_node); 2068 stable_node->head = &migrate_nodes; 2069 list_add(&stable_node->list, stable_node->head); 2070 } 2071 if (stable_node->head != &migrate_nodes && 2072 rmap_item->head == stable_node) 2073 return; 2074 /* 2075 * If it's a KSM fork, allow it to go over the sharing limit 2076 * without warnings. 2077 */ 2078 if (!is_page_sharing_candidate(stable_node)) 2079 max_page_sharing_bypass = true; 2080 } 2081 2082 /* We first start with searching the page inside the stable tree */ 2083 kpage = stable_tree_search(page); 2084 if (kpage == page && rmap_item->head == stable_node) { 2085 put_page(kpage); 2086 return; 2087 } 2088 2089 remove_rmap_item_from_tree(rmap_item); 2090 2091 if (kpage) { 2092 if (PTR_ERR(kpage) == -EBUSY) 2093 return; 2094 2095 err = try_to_merge_with_ksm_page(rmap_item, page, kpage); 2096 if (!err) { 2097 /* 2098 * The page was successfully merged: 2099 * add its rmap_item to the stable tree. 2100 */ 2101 lock_page(kpage); 2102 stable_tree_append(rmap_item, page_stable_node(kpage), 2103 max_page_sharing_bypass); 2104 unlock_page(kpage); 2105 } 2106 put_page(kpage); 2107 return; 2108 } 2109 2110 /* 2111 * If the hash value of the page has changed from the last time 2112 * we calculated it, this page is changing frequently: therefore we 2113 * don't want to insert it in the unstable tree, and we don't want 2114 * to waste our time searching for something identical to it there. 2115 */ 2116 checksum = calc_checksum(page); 2117 if (rmap_item->oldchecksum != checksum) { 2118 rmap_item->oldchecksum = checksum; 2119 return; 2120 } 2121 2122 /* 2123 * Same checksum as an empty page. We attempt to merge it with the 2124 * appropriate zero page if the user enabled this via sysfs. 2125 */ 2126 if (ksm_use_zero_pages && (checksum == zero_checksum)) { 2127 struct vm_area_struct *vma; 2128 2129 mmap_read_lock(mm); 2130 vma = find_mergeable_vma(mm, rmap_item->address); 2131 if (vma) { 2132 err = try_to_merge_one_page(vma, page, 2133 ZERO_PAGE(rmap_item->address)); 2134 } else { 2135 /* 2136 * If the vma is out of date, we do not need to 2137 * continue. 2138 */ 2139 err = 0; 2140 } 2141 mmap_read_unlock(mm); 2142 /* 2143 * In case of failure, the page was not really empty, so we 2144 * need to continue. Otherwise we're done. 2145 */ 2146 if (!err) 2147 return; 2148 } 2149 tree_rmap_item = 2150 unstable_tree_search_insert(rmap_item, page, &tree_page); 2151 if (tree_rmap_item) { 2152 bool split; 2153 2154 kpage = try_to_merge_two_pages(rmap_item, page, 2155 tree_rmap_item, tree_page); 2156 /* 2157 * If both pages we tried to merge belong to the same compound 2158 * page, then we actually ended up increasing the reference 2159 * count of the same compound page twice, and split_huge_page 2160 * failed. 2161 * Here we set a flag if that happened, and we use it later to 2162 * try split_huge_page again. Since we call put_page right 2163 * afterwards, the reference count will be correct and 2164 * split_huge_page should succeed. 2165 */ 2166 split = PageTransCompound(page) 2167 && compound_head(page) == compound_head(tree_page); 2168 put_page(tree_page); 2169 if (kpage) { 2170 /* 2171 * The pages were successfully merged: insert new 2172 * node in the stable tree and add both rmap_items. 2173 */ 2174 lock_page(kpage); 2175 stable_node = stable_tree_insert(kpage); 2176 if (stable_node) { 2177 stable_tree_append(tree_rmap_item, stable_node, 2178 false); 2179 stable_tree_append(rmap_item, stable_node, 2180 false); 2181 } 2182 unlock_page(kpage); 2183 2184 /* 2185 * If we fail to insert the page into the stable tree, 2186 * we will have 2 virtual addresses that are pointing 2187 * to a ksm page left outside the stable tree, 2188 * in which case we need to break_cow on both. 2189 */ 2190 if (!stable_node) { 2191 break_cow(tree_rmap_item); 2192 break_cow(rmap_item); 2193 } 2194 } else if (split) { 2195 /* 2196 * We are here if we tried to merge two pages and 2197 * failed because they both belonged to the same 2198 * compound page. We will split the page now, but no 2199 * merging will take place. 2200 * We do not want to add the cost of a full lock; if 2201 * the page is locked, it is better to skip it and 2202 * perhaps try again later. 2203 */ 2204 if (!trylock_page(page)) 2205 return; 2206 split_huge_page(page); 2207 unlock_page(page); 2208 } 2209 } 2210 } 2211 2212 static struct rmap_item *get_next_rmap_item(struct mm_slot *mm_slot, 2213 struct rmap_item **rmap_list, 2214 unsigned long addr) 2215 { 2216 struct rmap_item *rmap_item; 2217 2218 while (*rmap_list) { 2219 rmap_item = *rmap_list; 2220 if ((rmap_item->address & PAGE_MASK) == addr) 2221 return rmap_item; 2222 if (rmap_item->address > addr) 2223 break; 2224 *rmap_list = rmap_item->rmap_list; 2225 remove_rmap_item_from_tree(rmap_item); 2226 free_rmap_item(rmap_item); 2227 } 2228 2229 rmap_item = alloc_rmap_item(); 2230 if (rmap_item) { 2231 /* It has already been zeroed */ 2232 rmap_item->mm = mm_slot->mm; 2233 rmap_item->address = addr; 2234 rmap_item->rmap_list = *rmap_list; 2235 *rmap_list = rmap_item; 2236 } 2237 return rmap_item; 2238 } 2239 2240 static struct rmap_item *scan_get_next_rmap_item(struct page **page) 2241 { 2242 struct mm_struct *mm; 2243 struct mm_slot *slot; 2244 struct vm_area_struct *vma; 2245 struct rmap_item *rmap_item; 2246 int nid; 2247 2248 if (list_empty(&ksm_mm_head.mm_list)) 2249 return NULL; 2250 2251 slot = ksm_scan.mm_slot; 2252 if (slot == &ksm_mm_head) { 2253 /* 2254 * A number of pages can hang around indefinitely on per-cpu 2255 * pagevecs, raised page count preventing write_protect_page 2256 * from merging them. Though it doesn't really matter much, 2257 * it is puzzling to see some stuck in pages_volatile until 2258 * other activity jostles them out, and they also prevented 2259 * LTP's KSM test from succeeding deterministically; so drain 2260 * them here (here rather than on entry to ksm_do_scan(), 2261 * so we don't IPI too often when pages_to_scan is set low). 2262 */ 2263 lru_add_drain_all(); 2264 2265 /* 2266 * Whereas stale stable_nodes on the stable_tree itself 2267 * get pruned in the regular course of stable_tree_search(), 2268 * those moved out to the migrate_nodes list can accumulate: 2269 * so prune them once before each full scan. 2270 */ 2271 if (!ksm_merge_across_nodes) { 2272 struct stable_node *stable_node, *next; 2273 struct page *page; 2274 2275 list_for_each_entry_safe(stable_node, next, 2276 &migrate_nodes, list) { 2277 page = get_ksm_page(stable_node, 2278 GET_KSM_PAGE_NOLOCK); 2279 if (page) 2280 put_page(page); 2281 cond_resched(); 2282 } 2283 } 2284 2285 for (nid = 0; nid < ksm_nr_node_ids; nid++) 2286 root_unstable_tree[nid] = RB_ROOT; 2287 2288 spin_lock(&ksm_mmlist_lock); 2289 slot = list_entry(slot->mm_list.next, struct mm_slot, mm_list); 2290 ksm_scan.mm_slot = slot; 2291 spin_unlock(&ksm_mmlist_lock); 2292 /* 2293 * Although we tested list_empty() above, a racing __ksm_exit 2294 * of the last mm on the list may have removed it since then. 2295 */ 2296 if (slot == &ksm_mm_head) 2297 return NULL; 2298 next_mm: 2299 ksm_scan.address = 0; 2300 ksm_scan.rmap_list = &slot->rmap_list; 2301 } 2302 2303 mm = slot->mm; 2304 mmap_read_lock(mm); 2305 if (ksm_test_exit(mm)) 2306 vma = NULL; 2307 else 2308 vma = find_vma(mm, ksm_scan.address); 2309 2310 for (; vma; vma = vma->vm_next) { 2311 if (!(vma->vm_flags & VM_MERGEABLE)) 2312 continue; 2313 if (ksm_scan.address < vma->vm_start) 2314 ksm_scan.address = vma->vm_start; 2315 if (!vma->anon_vma) 2316 ksm_scan.address = vma->vm_end; 2317 2318 while (ksm_scan.address < vma->vm_end) { 2319 if (ksm_test_exit(mm)) 2320 break; 2321 *page = follow_page(vma, ksm_scan.address, FOLL_GET); 2322 if (IS_ERR_OR_NULL(*page) || is_zone_device_page(*page)) { 2323 ksm_scan.address += PAGE_SIZE; 2324 cond_resched(); 2325 continue; 2326 } 2327 if (PageAnon(*page)) { 2328 flush_anon_page(vma, *page, ksm_scan.address); 2329 flush_dcache_page(*page); 2330 rmap_item = get_next_rmap_item(slot, 2331 ksm_scan.rmap_list, ksm_scan.address); 2332 if (rmap_item) { 2333 ksm_scan.rmap_list = 2334 &rmap_item->rmap_list; 2335 ksm_scan.address += PAGE_SIZE; 2336 } else 2337 put_page(*page); 2338 mmap_read_unlock(mm); 2339 return rmap_item; 2340 } 2341 put_page(*page); 2342 ksm_scan.address += PAGE_SIZE; 2343 cond_resched(); 2344 } 2345 } 2346 2347 if (ksm_test_exit(mm)) { 2348 ksm_scan.address = 0; 2349 ksm_scan.rmap_list = &slot->rmap_list; 2350 } 2351 /* 2352 * Nuke all the rmap_items that are above this current rmap: 2353 * because there were no VM_MERGEABLE vmas with such addresses. 2354 */ 2355 remove_trailing_rmap_items(ksm_scan.rmap_list); 2356 2357 spin_lock(&ksm_mmlist_lock); 2358 ksm_scan.mm_slot = list_entry(slot->mm_list.next, 2359 struct mm_slot, mm_list); 2360 if (ksm_scan.address == 0) { 2361 /* 2362 * We've completed a full scan of all vmas, holding mmap_lock 2363 * throughout, and found no VM_MERGEABLE: so do the same as 2364 * __ksm_exit does to remove this mm from all our lists now. 2365 * This applies either when cleaning up after __ksm_exit 2366 * (but beware: we can reach here even before __ksm_exit), 2367 * or when all VM_MERGEABLE areas have been unmapped (and 2368 * mmap_lock then protects against race with MADV_MERGEABLE). 2369 */ 2370 hash_del(&slot->link); 2371 list_del(&slot->mm_list); 2372 spin_unlock(&ksm_mmlist_lock); 2373 2374 free_mm_slot(slot); 2375 clear_bit(MMF_VM_MERGEABLE, &mm->flags); 2376 mmap_read_unlock(mm); 2377 mmdrop(mm); 2378 } else { 2379 mmap_read_unlock(mm); 2380 /* 2381 * mmap_read_unlock(mm) first because after 2382 * spin_unlock(&ksm_mmlist_lock) run, the "mm" may 2383 * already have been freed under us by __ksm_exit() 2384 * because the "mm_slot" is still hashed and 2385 * ksm_scan.mm_slot doesn't point to it anymore. 2386 */ 2387 spin_unlock(&ksm_mmlist_lock); 2388 } 2389 2390 /* Repeat until we've completed scanning the whole list */ 2391 slot = ksm_scan.mm_slot; 2392 if (slot != &ksm_mm_head) 2393 goto next_mm; 2394 2395 ksm_scan.seqnr++; 2396 return NULL; 2397 } 2398 2399 /** 2400 * ksm_do_scan - the ksm scanner main worker function. 2401 * @scan_npages: number of pages we want to scan before we return. 2402 */ 2403 static void ksm_do_scan(unsigned int scan_npages) 2404 { 2405 struct rmap_item *rmap_item; 2406 struct page *page; 2407 2408 while (scan_npages-- && likely(!freezing(current))) { 2409 cond_resched(); 2410 rmap_item = scan_get_next_rmap_item(&page); 2411 if (!rmap_item) 2412 return; 2413 cmp_and_merge_page(page, rmap_item); 2414 put_page(page); 2415 } 2416 } 2417 2418 static int ksmd_should_run(void) 2419 { 2420 return (ksm_run & KSM_RUN_MERGE) && !list_empty(&ksm_mm_head.mm_list); 2421 } 2422 2423 static int ksm_scan_thread(void *nothing) 2424 { 2425 unsigned int sleep_ms; 2426 2427 set_freezable(); 2428 set_user_nice(current, 5); 2429 2430 while (!kthread_should_stop()) { 2431 mutex_lock(&ksm_thread_mutex); 2432 wait_while_offlining(); 2433 if (ksmd_should_run()) 2434 ksm_do_scan(ksm_thread_pages_to_scan); 2435 mutex_unlock(&ksm_thread_mutex); 2436 2437 try_to_freeze(); 2438 2439 if (ksmd_should_run()) { 2440 sleep_ms = READ_ONCE(ksm_thread_sleep_millisecs); 2441 wait_event_interruptible_timeout(ksm_iter_wait, 2442 sleep_ms != READ_ONCE(ksm_thread_sleep_millisecs), 2443 msecs_to_jiffies(sleep_ms)); 2444 } else { 2445 wait_event_freezable(ksm_thread_wait, 2446 ksmd_should_run() || kthread_should_stop()); 2447 } 2448 } 2449 return 0; 2450 } 2451 2452 int ksm_madvise(struct vm_area_struct *vma, unsigned long start, 2453 unsigned long end, int advice, unsigned long *vm_flags) 2454 { 2455 struct mm_struct *mm = vma->vm_mm; 2456 int err; 2457 2458 switch (advice) { 2459 case MADV_MERGEABLE: 2460 /* 2461 * Be somewhat over-protective for now! 2462 */ 2463 if (*vm_flags & (VM_MERGEABLE | VM_SHARED | VM_MAYSHARE | 2464 VM_PFNMAP | VM_IO | VM_DONTEXPAND | 2465 VM_HUGETLB | VM_MIXEDMAP)) 2466 return 0; /* just ignore the advice */ 2467 2468 if (vma_is_dax(vma)) 2469 return 0; 2470 2471 #ifdef VM_SAO 2472 if (*vm_flags & VM_SAO) 2473 return 0; 2474 #endif 2475 #ifdef VM_SPARC_ADI 2476 if (*vm_flags & VM_SPARC_ADI) 2477 return 0; 2478 #endif 2479 2480 if (!test_bit(MMF_VM_MERGEABLE, &mm->flags)) { 2481 err = __ksm_enter(mm); 2482 if (err) 2483 return err; 2484 } 2485 2486 *vm_flags |= VM_MERGEABLE; 2487 break; 2488 2489 case MADV_UNMERGEABLE: 2490 if (!(*vm_flags & VM_MERGEABLE)) 2491 return 0; /* just ignore the advice */ 2492 2493 if (vma->anon_vma) { 2494 err = unmerge_ksm_pages(vma, start, end); 2495 if (err) 2496 return err; 2497 } 2498 2499 *vm_flags &= ~VM_MERGEABLE; 2500 break; 2501 } 2502 2503 return 0; 2504 } 2505 EXPORT_SYMBOL_GPL(ksm_madvise); 2506 2507 int __ksm_enter(struct mm_struct *mm) 2508 { 2509 struct mm_slot *mm_slot; 2510 int needs_wakeup; 2511 2512 mm_slot = alloc_mm_slot(); 2513 if (!mm_slot) 2514 return -ENOMEM; 2515 2516 /* Check ksm_run too? Would need tighter locking */ 2517 needs_wakeup = list_empty(&ksm_mm_head.mm_list); 2518 2519 spin_lock(&ksm_mmlist_lock); 2520 insert_to_mm_slots_hash(mm, mm_slot); 2521 /* 2522 * When KSM_RUN_MERGE (or KSM_RUN_STOP), 2523 * insert just behind the scanning cursor, to let the area settle 2524 * down a little; when fork is followed by immediate exec, we don't 2525 * want ksmd to waste time setting up and tearing down an rmap_list. 2526 * 2527 * But when KSM_RUN_UNMERGE, it's important to insert ahead of its 2528 * scanning cursor, otherwise KSM pages in newly forked mms will be 2529 * missed: then we might as well insert at the end of the list. 2530 */ 2531 if (ksm_run & KSM_RUN_UNMERGE) 2532 list_add_tail(&mm_slot->mm_list, &ksm_mm_head.mm_list); 2533 else 2534 list_add_tail(&mm_slot->mm_list, &ksm_scan.mm_slot->mm_list); 2535 spin_unlock(&ksm_mmlist_lock); 2536 2537 set_bit(MMF_VM_MERGEABLE, &mm->flags); 2538 mmgrab(mm); 2539 2540 if (needs_wakeup) 2541 wake_up_interruptible(&ksm_thread_wait); 2542 2543 return 0; 2544 } 2545 2546 void __ksm_exit(struct mm_struct *mm) 2547 { 2548 struct mm_slot *mm_slot; 2549 int easy_to_free = 0; 2550 2551 /* 2552 * This process is exiting: if it's straightforward (as is the 2553 * case when ksmd was never running), free mm_slot immediately. 2554 * But if it's at the cursor or has rmap_items linked to it, use 2555 * mmap_lock to synchronize with any break_cows before pagetables 2556 * are freed, and leave the mm_slot on the list for ksmd to free. 2557 * Beware: ksm may already have noticed it exiting and freed the slot. 2558 */ 2559 2560 spin_lock(&ksm_mmlist_lock); 2561 mm_slot = get_mm_slot(mm); 2562 if (mm_slot && ksm_scan.mm_slot != mm_slot) { 2563 if (!mm_slot->rmap_list) { 2564 hash_del(&mm_slot->link); 2565 list_del(&mm_slot->mm_list); 2566 easy_to_free = 1; 2567 } else { 2568 list_move(&mm_slot->mm_list, 2569 &ksm_scan.mm_slot->mm_list); 2570 } 2571 } 2572 spin_unlock(&ksm_mmlist_lock); 2573 2574 if (easy_to_free) { 2575 free_mm_slot(mm_slot); 2576 clear_bit(MMF_VM_MERGEABLE, &mm->flags); 2577 mmdrop(mm); 2578 } else if (mm_slot) { 2579 mmap_write_lock(mm); 2580 mmap_write_unlock(mm); 2581 } 2582 } 2583 2584 struct page *ksm_might_need_to_copy(struct page *page, 2585 struct vm_area_struct *vma, unsigned long address) 2586 { 2587 struct folio *folio = page_folio(page); 2588 struct anon_vma *anon_vma = folio_anon_vma(folio); 2589 struct page *new_page; 2590 2591 if (PageKsm(page)) { 2592 if (page_stable_node(page) && 2593 !(ksm_run & KSM_RUN_UNMERGE)) 2594 return page; /* no need to copy it */ 2595 } else if (!anon_vma) { 2596 return page; /* no need to copy it */ 2597 } else if (page->index == linear_page_index(vma, address) && 2598 anon_vma->root == vma->anon_vma->root) { 2599 return page; /* still no need to copy it */ 2600 } 2601 if (!PageUptodate(page)) 2602 return page; /* let do_swap_page report the error */ 2603 2604 new_page = alloc_page_vma(GFP_HIGHUSER_MOVABLE, vma, address); 2605 if (new_page && 2606 mem_cgroup_charge(page_folio(new_page), vma->vm_mm, GFP_KERNEL)) { 2607 put_page(new_page); 2608 new_page = NULL; 2609 } 2610 if (new_page) { 2611 copy_user_highpage(new_page, page, address, vma); 2612 2613 SetPageDirty(new_page); 2614 __SetPageUptodate(new_page); 2615 __SetPageLocked(new_page); 2616 #ifdef CONFIG_SWAP 2617 count_vm_event(KSM_SWPIN_COPY); 2618 #endif 2619 } 2620 2621 return new_page; 2622 } 2623 2624 void rmap_walk_ksm(struct folio *folio, struct rmap_walk_control *rwc) 2625 { 2626 struct stable_node *stable_node; 2627 struct rmap_item *rmap_item; 2628 int search_new_forks = 0; 2629 2630 VM_BUG_ON_FOLIO(!folio_test_ksm(folio), folio); 2631 2632 /* 2633 * Rely on the page lock to protect against concurrent modifications 2634 * to that page's node of the stable tree. 2635 */ 2636 VM_BUG_ON_FOLIO(!folio_test_locked(folio), folio); 2637 2638 stable_node = folio_stable_node(folio); 2639 if (!stable_node) 2640 return; 2641 again: 2642 hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) { 2643 struct anon_vma *anon_vma = rmap_item->anon_vma; 2644 struct anon_vma_chain *vmac; 2645 struct vm_area_struct *vma; 2646 2647 cond_resched(); 2648 if (!anon_vma_trylock_read(anon_vma)) { 2649 if (rwc->try_lock) { 2650 rwc->contended = true; 2651 return; 2652 } 2653 anon_vma_lock_read(anon_vma); 2654 } 2655 anon_vma_interval_tree_foreach(vmac, &anon_vma->rb_root, 2656 0, ULONG_MAX) { 2657 unsigned long addr; 2658 2659 cond_resched(); 2660 vma = vmac->vma; 2661 2662 /* Ignore the stable/unstable/sqnr flags */ 2663 addr = rmap_item->address & PAGE_MASK; 2664 2665 if (addr < vma->vm_start || addr >= vma->vm_end) 2666 continue; 2667 /* 2668 * Initially we examine only the vma which covers this 2669 * rmap_item; but later, if there is still work to do, 2670 * we examine covering vmas in other mms: in case they 2671 * were forked from the original since ksmd passed. 2672 */ 2673 if ((rmap_item->mm == vma->vm_mm) == search_new_forks) 2674 continue; 2675 2676 if (rwc->invalid_vma && rwc->invalid_vma(vma, rwc->arg)) 2677 continue; 2678 2679 if (!rwc->rmap_one(folio, vma, addr, rwc->arg)) { 2680 anon_vma_unlock_read(anon_vma); 2681 return; 2682 } 2683 if (rwc->done && rwc->done(folio)) { 2684 anon_vma_unlock_read(anon_vma); 2685 return; 2686 } 2687 } 2688 anon_vma_unlock_read(anon_vma); 2689 } 2690 if (!search_new_forks++) 2691 goto again; 2692 } 2693 2694 #ifdef CONFIG_MIGRATION 2695 void folio_migrate_ksm(struct folio *newfolio, struct folio *folio) 2696 { 2697 struct stable_node *stable_node; 2698 2699 VM_BUG_ON_FOLIO(!folio_test_locked(folio), folio); 2700 VM_BUG_ON_FOLIO(!folio_test_locked(newfolio), newfolio); 2701 VM_BUG_ON_FOLIO(newfolio->mapping != folio->mapping, newfolio); 2702 2703 stable_node = folio_stable_node(folio); 2704 if (stable_node) { 2705 VM_BUG_ON_FOLIO(stable_node->kpfn != folio_pfn(folio), folio); 2706 stable_node->kpfn = folio_pfn(newfolio); 2707 /* 2708 * newfolio->mapping was set in advance; now we need smp_wmb() 2709 * to make sure that the new stable_node->kpfn is visible 2710 * to get_ksm_page() before it can see that folio->mapping 2711 * has gone stale (or that folio_test_swapcache has been cleared). 2712 */ 2713 smp_wmb(); 2714 set_page_stable_node(&folio->page, NULL); 2715 } 2716 } 2717 #endif /* CONFIG_MIGRATION */ 2718 2719 #ifdef CONFIG_MEMORY_HOTREMOVE 2720 static void wait_while_offlining(void) 2721 { 2722 while (ksm_run & KSM_RUN_OFFLINE) { 2723 mutex_unlock(&ksm_thread_mutex); 2724 wait_on_bit(&ksm_run, ilog2(KSM_RUN_OFFLINE), 2725 TASK_UNINTERRUPTIBLE); 2726 mutex_lock(&ksm_thread_mutex); 2727 } 2728 } 2729 2730 static bool stable_node_dup_remove_range(struct stable_node *stable_node, 2731 unsigned long start_pfn, 2732 unsigned long end_pfn) 2733 { 2734 if (stable_node->kpfn >= start_pfn && 2735 stable_node->kpfn < end_pfn) { 2736 /* 2737 * Don't get_ksm_page, page has already gone: 2738 * which is why we keep kpfn instead of page* 2739 */ 2740 remove_node_from_stable_tree(stable_node); 2741 return true; 2742 } 2743 return false; 2744 } 2745 2746 static bool stable_node_chain_remove_range(struct stable_node *stable_node, 2747 unsigned long start_pfn, 2748 unsigned long end_pfn, 2749 struct rb_root *root) 2750 { 2751 struct stable_node *dup; 2752 struct hlist_node *hlist_safe; 2753 2754 if (!is_stable_node_chain(stable_node)) { 2755 VM_BUG_ON(is_stable_node_dup(stable_node)); 2756 return stable_node_dup_remove_range(stable_node, start_pfn, 2757 end_pfn); 2758 } 2759 2760 hlist_for_each_entry_safe(dup, hlist_safe, 2761 &stable_node->hlist, hlist_dup) { 2762 VM_BUG_ON(!is_stable_node_dup(dup)); 2763 stable_node_dup_remove_range(dup, start_pfn, end_pfn); 2764 } 2765 if (hlist_empty(&stable_node->hlist)) { 2766 free_stable_node_chain(stable_node, root); 2767 return true; /* notify caller that tree was rebalanced */ 2768 } else 2769 return false; 2770 } 2771 2772 static void ksm_check_stable_tree(unsigned long start_pfn, 2773 unsigned long end_pfn) 2774 { 2775 struct stable_node *stable_node, *next; 2776 struct rb_node *node; 2777 int nid; 2778 2779 for (nid = 0; nid < ksm_nr_node_ids; nid++) { 2780 node = rb_first(root_stable_tree + nid); 2781 while (node) { 2782 stable_node = rb_entry(node, struct stable_node, node); 2783 if (stable_node_chain_remove_range(stable_node, 2784 start_pfn, end_pfn, 2785 root_stable_tree + 2786 nid)) 2787 node = rb_first(root_stable_tree + nid); 2788 else 2789 node = rb_next(node); 2790 cond_resched(); 2791 } 2792 } 2793 list_for_each_entry_safe(stable_node, next, &migrate_nodes, list) { 2794 if (stable_node->kpfn >= start_pfn && 2795 stable_node->kpfn < end_pfn) 2796 remove_node_from_stable_tree(stable_node); 2797 cond_resched(); 2798 } 2799 } 2800 2801 static int ksm_memory_callback(struct notifier_block *self, 2802 unsigned long action, void *arg) 2803 { 2804 struct memory_notify *mn = arg; 2805 2806 switch (action) { 2807 case MEM_GOING_OFFLINE: 2808 /* 2809 * Prevent ksm_do_scan(), unmerge_and_remove_all_rmap_items() 2810 * and remove_all_stable_nodes() while memory is going offline: 2811 * it is unsafe for them to touch the stable tree at this time. 2812 * But unmerge_ksm_pages(), rmap lookups and other entry points 2813 * which do not need the ksm_thread_mutex are all safe. 2814 */ 2815 mutex_lock(&ksm_thread_mutex); 2816 ksm_run |= KSM_RUN_OFFLINE; 2817 mutex_unlock(&ksm_thread_mutex); 2818 break; 2819 2820 case MEM_OFFLINE: 2821 /* 2822 * Most of the work is done by page migration; but there might 2823 * be a few stable_nodes left over, still pointing to struct 2824 * pages which have been offlined: prune those from the tree, 2825 * otherwise get_ksm_page() might later try to access a 2826 * non-existent struct page. 2827 */ 2828 ksm_check_stable_tree(mn->start_pfn, 2829 mn->start_pfn + mn->nr_pages); 2830 fallthrough; 2831 case MEM_CANCEL_OFFLINE: 2832 mutex_lock(&ksm_thread_mutex); 2833 ksm_run &= ~KSM_RUN_OFFLINE; 2834 mutex_unlock(&ksm_thread_mutex); 2835 2836 smp_mb(); /* wake_up_bit advises this */ 2837 wake_up_bit(&ksm_run, ilog2(KSM_RUN_OFFLINE)); 2838 break; 2839 } 2840 return NOTIFY_OK; 2841 } 2842 #else 2843 static void wait_while_offlining(void) 2844 { 2845 } 2846 #endif /* CONFIG_MEMORY_HOTREMOVE */ 2847 2848 #ifdef CONFIG_SYSFS 2849 /* 2850 * This all compiles without CONFIG_SYSFS, but is a waste of space. 2851 */ 2852 2853 #define KSM_ATTR_RO(_name) \ 2854 static struct kobj_attribute _name##_attr = __ATTR_RO(_name) 2855 #define KSM_ATTR(_name) \ 2856 static struct kobj_attribute _name##_attr = __ATTR_RW(_name) 2857 2858 static ssize_t sleep_millisecs_show(struct kobject *kobj, 2859 struct kobj_attribute *attr, char *buf) 2860 { 2861 return sysfs_emit(buf, "%u\n", ksm_thread_sleep_millisecs); 2862 } 2863 2864 static ssize_t sleep_millisecs_store(struct kobject *kobj, 2865 struct kobj_attribute *attr, 2866 const char *buf, size_t count) 2867 { 2868 unsigned int msecs; 2869 int err; 2870 2871 err = kstrtouint(buf, 10, &msecs); 2872 if (err) 2873 return -EINVAL; 2874 2875 ksm_thread_sleep_millisecs = msecs; 2876 wake_up_interruptible(&ksm_iter_wait); 2877 2878 return count; 2879 } 2880 KSM_ATTR(sleep_millisecs); 2881 2882 static ssize_t pages_to_scan_show(struct kobject *kobj, 2883 struct kobj_attribute *attr, char *buf) 2884 { 2885 return sysfs_emit(buf, "%u\n", ksm_thread_pages_to_scan); 2886 } 2887 2888 static ssize_t pages_to_scan_store(struct kobject *kobj, 2889 struct kobj_attribute *attr, 2890 const char *buf, size_t count) 2891 { 2892 unsigned int nr_pages; 2893 int err; 2894 2895 err = kstrtouint(buf, 10, &nr_pages); 2896 if (err) 2897 return -EINVAL; 2898 2899 ksm_thread_pages_to_scan = nr_pages; 2900 2901 return count; 2902 } 2903 KSM_ATTR(pages_to_scan); 2904 2905 static ssize_t run_show(struct kobject *kobj, struct kobj_attribute *attr, 2906 char *buf) 2907 { 2908 return sysfs_emit(buf, "%lu\n", ksm_run); 2909 } 2910 2911 static ssize_t run_store(struct kobject *kobj, struct kobj_attribute *attr, 2912 const char *buf, size_t count) 2913 { 2914 unsigned int flags; 2915 int err; 2916 2917 err = kstrtouint(buf, 10, &flags); 2918 if (err) 2919 return -EINVAL; 2920 if (flags > KSM_RUN_UNMERGE) 2921 return -EINVAL; 2922 2923 /* 2924 * KSM_RUN_MERGE sets ksmd running, and 0 stops it running. 2925 * KSM_RUN_UNMERGE stops it running and unmerges all rmap_items, 2926 * breaking COW to free the pages_shared (but leaves mm_slots 2927 * on the list for when ksmd may be set running again). 2928 */ 2929 2930 mutex_lock(&ksm_thread_mutex); 2931 wait_while_offlining(); 2932 if (ksm_run != flags) { 2933 ksm_run = flags; 2934 if (flags & KSM_RUN_UNMERGE) { 2935 set_current_oom_origin(); 2936 err = unmerge_and_remove_all_rmap_items(); 2937 clear_current_oom_origin(); 2938 if (err) { 2939 ksm_run = KSM_RUN_STOP; 2940 count = err; 2941 } 2942 } 2943 } 2944 mutex_unlock(&ksm_thread_mutex); 2945 2946 if (flags & KSM_RUN_MERGE) 2947 wake_up_interruptible(&ksm_thread_wait); 2948 2949 return count; 2950 } 2951 KSM_ATTR(run); 2952 2953 #ifdef CONFIG_NUMA 2954 static ssize_t merge_across_nodes_show(struct kobject *kobj, 2955 struct kobj_attribute *attr, char *buf) 2956 { 2957 return sysfs_emit(buf, "%u\n", ksm_merge_across_nodes); 2958 } 2959 2960 static ssize_t merge_across_nodes_store(struct kobject *kobj, 2961 struct kobj_attribute *attr, 2962 const char *buf, size_t count) 2963 { 2964 int err; 2965 unsigned long knob; 2966 2967 err = kstrtoul(buf, 10, &knob); 2968 if (err) 2969 return err; 2970 if (knob > 1) 2971 return -EINVAL; 2972 2973 mutex_lock(&ksm_thread_mutex); 2974 wait_while_offlining(); 2975 if (ksm_merge_across_nodes != knob) { 2976 if (ksm_pages_shared || remove_all_stable_nodes()) 2977 err = -EBUSY; 2978 else if (root_stable_tree == one_stable_tree) { 2979 struct rb_root *buf; 2980 /* 2981 * This is the first time that we switch away from the 2982 * default of merging across nodes: must now allocate 2983 * a buffer to hold as many roots as may be needed. 2984 * Allocate stable and unstable together: 2985 * MAXSMP NODES_SHIFT 10 will use 16kB. 2986 */ 2987 buf = kcalloc(nr_node_ids + nr_node_ids, sizeof(*buf), 2988 GFP_KERNEL); 2989 /* Let us assume that RB_ROOT is NULL is zero */ 2990 if (!buf) 2991 err = -ENOMEM; 2992 else { 2993 root_stable_tree = buf; 2994 root_unstable_tree = buf + nr_node_ids; 2995 /* Stable tree is empty but not the unstable */ 2996 root_unstable_tree[0] = one_unstable_tree[0]; 2997 } 2998 } 2999 if (!err) { 3000 ksm_merge_across_nodes = knob; 3001 ksm_nr_node_ids = knob ? 1 : nr_node_ids; 3002 } 3003 } 3004 mutex_unlock(&ksm_thread_mutex); 3005 3006 return err ? err : count; 3007 } 3008 KSM_ATTR(merge_across_nodes); 3009 #endif 3010 3011 static ssize_t use_zero_pages_show(struct kobject *kobj, 3012 struct kobj_attribute *attr, char *buf) 3013 { 3014 return sysfs_emit(buf, "%u\n", ksm_use_zero_pages); 3015 } 3016 static ssize_t use_zero_pages_store(struct kobject *kobj, 3017 struct kobj_attribute *attr, 3018 const char *buf, size_t count) 3019 { 3020 int err; 3021 bool value; 3022 3023 err = kstrtobool(buf, &value); 3024 if (err) 3025 return -EINVAL; 3026 3027 ksm_use_zero_pages = value; 3028 3029 return count; 3030 } 3031 KSM_ATTR(use_zero_pages); 3032 3033 static ssize_t max_page_sharing_show(struct kobject *kobj, 3034 struct kobj_attribute *attr, char *buf) 3035 { 3036 return sysfs_emit(buf, "%u\n", ksm_max_page_sharing); 3037 } 3038 3039 static ssize_t max_page_sharing_store(struct kobject *kobj, 3040 struct kobj_attribute *attr, 3041 const char *buf, size_t count) 3042 { 3043 int err; 3044 int knob; 3045 3046 err = kstrtoint(buf, 10, &knob); 3047 if (err) 3048 return err; 3049 /* 3050 * When a KSM page is created it is shared by 2 mappings. This 3051 * being a signed comparison, it implicitly verifies it's not 3052 * negative. 3053 */ 3054 if (knob < 2) 3055 return -EINVAL; 3056 3057 if (READ_ONCE(ksm_max_page_sharing) == knob) 3058 return count; 3059 3060 mutex_lock(&ksm_thread_mutex); 3061 wait_while_offlining(); 3062 if (ksm_max_page_sharing != knob) { 3063 if (ksm_pages_shared || remove_all_stable_nodes()) 3064 err = -EBUSY; 3065 else 3066 ksm_max_page_sharing = knob; 3067 } 3068 mutex_unlock(&ksm_thread_mutex); 3069 3070 return err ? err : count; 3071 } 3072 KSM_ATTR(max_page_sharing); 3073 3074 static ssize_t pages_shared_show(struct kobject *kobj, 3075 struct kobj_attribute *attr, char *buf) 3076 { 3077 return sysfs_emit(buf, "%lu\n", ksm_pages_shared); 3078 } 3079 KSM_ATTR_RO(pages_shared); 3080 3081 static ssize_t pages_sharing_show(struct kobject *kobj, 3082 struct kobj_attribute *attr, char *buf) 3083 { 3084 return sysfs_emit(buf, "%lu\n", ksm_pages_sharing); 3085 } 3086 KSM_ATTR_RO(pages_sharing); 3087 3088 static ssize_t pages_unshared_show(struct kobject *kobj, 3089 struct kobj_attribute *attr, char *buf) 3090 { 3091 return sysfs_emit(buf, "%lu\n", ksm_pages_unshared); 3092 } 3093 KSM_ATTR_RO(pages_unshared); 3094 3095 static ssize_t pages_volatile_show(struct kobject *kobj, 3096 struct kobj_attribute *attr, char *buf) 3097 { 3098 long ksm_pages_volatile; 3099 3100 ksm_pages_volatile = ksm_rmap_items - ksm_pages_shared 3101 - ksm_pages_sharing - ksm_pages_unshared; 3102 /* 3103 * It was not worth any locking to calculate that statistic, 3104 * but it might therefore sometimes be negative: conceal that. 3105 */ 3106 if (ksm_pages_volatile < 0) 3107 ksm_pages_volatile = 0; 3108 return sysfs_emit(buf, "%ld\n", ksm_pages_volatile); 3109 } 3110 KSM_ATTR_RO(pages_volatile); 3111 3112 static ssize_t stable_node_dups_show(struct kobject *kobj, 3113 struct kobj_attribute *attr, char *buf) 3114 { 3115 return sysfs_emit(buf, "%lu\n", ksm_stable_node_dups); 3116 } 3117 KSM_ATTR_RO(stable_node_dups); 3118 3119 static ssize_t stable_node_chains_show(struct kobject *kobj, 3120 struct kobj_attribute *attr, char *buf) 3121 { 3122 return sysfs_emit(buf, "%lu\n", ksm_stable_node_chains); 3123 } 3124 KSM_ATTR_RO(stable_node_chains); 3125 3126 static ssize_t 3127 stable_node_chains_prune_millisecs_show(struct kobject *kobj, 3128 struct kobj_attribute *attr, 3129 char *buf) 3130 { 3131 return sysfs_emit(buf, "%u\n", ksm_stable_node_chains_prune_millisecs); 3132 } 3133 3134 static ssize_t 3135 stable_node_chains_prune_millisecs_store(struct kobject *kobj, 3136 struct kobj_attribute *attr, 3137 const char *buf, size_t count) 3138 { 3139 unsigned int msecs; 3140 int err; 3141 3142 err = kstrtouint(buf, 10, &msecs); 3143 if (err) 3144 return -EINVAL; 3145 3146 ksm_stable_node_chains_prune_millisecs = msecs; 3147 3148 return count; 3149 } 3150 KSM_ATTR(stable_node_chains_prune_millisecs); 3151 3152 static ssize_t full_scans_show(struct kobject *kobj, 3153 struct kobj_attribute *attr, char *buf) 3154 { 3155 return sysfs_emit(buf, "%lu\n", ksm_scan.seqnr); 3156 } 3157 KSM_ATTR_RO(full_scans); 3158 3159 static struct attribute *ksm_attrs[] = { 3160 &sleep_millisecs_attr.attr, 3161 &pages_to_scan_attr.attr, 3162 &run_attr.attr, 3163 &pages_shared_attr.attr, 3164 &pages_sharing_attr.attr, 3165 &pages_unshared_attr.attr, 3166 &pages_volatile_attr.attr, 3167 &full_scans_attr.attr, 3168 #ifdef CONFIG_NUMA 3169 &merge_across_nodes_attr.attr, 3170 #endif 3171 &max_page_sharing_attr.attr, 3172 &stable_node_chains_attr.attr, 3173 &stable_node_dups_attr.attr, 3174 &stable_node_chains_prune_millisecs_attr.attr, 3175 &use_zero_pages_attr.attr, 3176 NULL, 3177 }; 3178 3179 static const struct attribute_group ksm_attr_group = { 3180 .attrs = ksm_attrs, 3181 .name = "ksm", 3182 }; 3183 #endif /* CONFIG_SYSFS */ 3184 3185 static int __init ksm_init(void) 3186 { 3187 struct task_struct *ksm_thread; 3188 int err; 3189 3190 /* The correct value depends on page size and endianness */ 3191 zero_checksum = calc_checksum(ZERO_PAGE(0)); 3192 /* Default to false for backwards compatibility */ 3193 ksm_use_zero_pages = false; 3194 3195 err = ksm_slab_init(); 3196 if (err) 3197 goto out; 3198 3199 ksm_thread = kthread_run(ksm_scan_thread, NULL, "ksmd"); 3200 if (IS_ERR(ksm_thread)) { 3201 pr_err("ksm: creating kthread failed\n"); 3202 err = PTR_ERR(ksm_thread); 3203 goto out_free; 3204 } 3205 3206 #ifdef CONFIG_SYSFS 3207 err = sysfs_create_group(mm_kobj, &ksm_attr_group); 3208 if (err) { 3209 pr_err("ksm: register sysfs failed\n"); 3210 kthread_stop(ksm_thread); 3211 goto out_free; 3212 } 3213 #else 3214 ksm_run = KSM_RUN_MERGE; /* no way for user to start it */ 3215 3216 #endif /* CONFIG_SYSFS */ 3217 3218 #ifdef CONFIG_MEMORY_HOTREMOVE 3219 /* There is no significance to this priority 100 */ 3220 hotplug_memory_notifier(ksm_memory_callback, 100); 3221 #endif 3222 return 0; 3223 3224 out_free: 3225 ksm_slab_free(); 3226 out: 3227 return err; 3228 } 3229 subsys_initcall(ksm_init); 3230