ksm.c revision 21ae5b01750f14140809508a478a4413792e0261
1/* 2 * Memory merging support. 3 * 4 * This code enables dynamic sharing of identical pages found in different 5 * memory areas, even if they are not shared by fork() 6 * 7 * Copyright (C) 2008-2009 Red Hat, Inc. 8 * Authors: 9 * Izik Eidus 10 * Andrea Arcangeli 11 * Chris Wright 12 * Hugh Dickins 13 * 14 * This work is licensed under the terms of the GNU GPL, version 2. 15 */ 16 17#include <linux/errno.h> 18#include <linux/mm.h> 19#include <linux/fs.h> 20#include <linux/mman.h> 21#include <linux/sched.h> 22#include <linux/rwsem.h> 23#include <linux/pagemap.h> 24#include <linux/rmap.h> 25#include <linux/spinlock.h> 26#include <linux/jhash.h> 27#include <linux/delay.h> 28#include <linux/kthread.h> 29#include <linux/wait.h> 30#include <linux/slab.h> 31#include <linux/rbtree.h> 32#include <linux/memory.h> 33#include <linux/mmu_notifier.h> 34#include <linux/swap.h> 35#include <linux/ksm.h> 36#include <linux/hash.h> 37 38#include <asm/tlbflush.h> 39#include "internal.h" 40 41/* 42 * A few notes about the KSM scanning process, 43 * to make it easier to understand the data structures below: 44 * 45 * In order to reduce excessive scanning, KSM sorts the memory pages by their 46 * contents into a data structure that holds pointers to the pages' locations. 47 * 48 * Since the contents of the pages may change at any moment, KSM cannot just 49 * insert the pages into a normal sorted tree and expect it to find anything. 50 * Therefore KSM uses two data structures - the stable and the unstable tree. 51 * 52 * The stable tree holds pointers to all the merged pages (ksm pages), sorted 53 * by their contents. Because each such page is write-protected, searching on 54 * this tree is fully assured to be working (except when pages are unmapped), 55 * and therefore this tree is called the stable tree. 56 * 57 * In addition to the stable tree, KSM uses a second data structure called the 58 * unstable tree: this tree holds pointers to pages which have been found to 59 * be "unchanged for a period of time". The unstable tree sorts these pages 60 * by their contents, but since they are not write-protected, KSM cannot rely 61 * upon the unstable tree to work correctly - the unstable tree is liable to 62 * be corrupted as its contents are modified, and so it is called unstable. 63 * 64 * KSM solves this problem by several techniques: 65 * 66 * 1) The unstable tree is flushed every time KSM completes scanning all 67 * memory areas, and then the tree is rebuilt again from the beginning. 68 * 2) KSM will only insert into the unstable tree, pages whose hash value 69 * has not changed since the previous scan of all memory areas. 70 * 3) The unstable tree is a RedBlack Tree - so its balancing is based on the 71 * colors of the nodes and not on their contents, assuring that even when 72 * the tree gets "corrupted" it won't get out of balance, so scanning time 73 * remains the same (also, searching and inserting nodes in an rbtree uses 74 * the same algorithm, so we have no overhead when we flush and rebuild). 75 * 4) KSM never flushes the stable tree, which means that even if it were to 76 * take 10 attempts to find a page in the unstable tree, once it is found, 77 * it is secured in the stable tree. (When we scan a new page, we first 78 * compare it against the stable tree, and then against the unstable tree.) 79 */ 80 81/** 82 * struct mm_slot - ksm information per mm that is being scanned 83 * @link: link to the mm_slots hash list 84 * @mm_list: link into the mm_slots list, rooted in ksm_mm_head 85 * @rmap_list: head for this mm_slot's singly-linked list of rmap_items 86 * @mm: the mm that this information is valid for 87 */ 88struct mm_slot { 89 struct hlist_node link; 90 struct list_head mm_list; 91 struct rmap_item *rmap_list; 92 struct mm_struct *mm; 93}; 94 95/** 96 * struct ksm_scan - cursor for scanning 97 * @mm_slot: the current mm_slot we are scanning 98 * @address: the next address inside that to be scanned 99 * @rmap_list: link to the next rmap to be scanned in the rmap_list 100 * @seqnr: count of completed full scans (needed when removing unstable node) 101 * 102 * There is only the one ksm_scan instance of this cursor structure. 103 */ 104struct ksm_scan { 105 struct mm_slot *mm_slot; 106 unsigned long address; 107 struct rmap_item **rmap_list; 108 unsigned long seqnr; 109}; 110 111/** 112 * struct stable_node - node of the stable rbtree 113 * @node: rb node of this ksm page in the stable tree 114 * @hlist: hlist head of rmap_items using this ksm page 115 * @kpfn: page frame number of this ksm page 116 */ 117struct stable_node { 118 struct rb_node node; 119 struct hlist_head hlist; 120 unsigned long kpfn; 121}; 122 123/** 124 * struct rmap_item - reverse mapping item for virtual addresses 125 * @rmap_list: next rmap_item in mm_slot's singly-linked rmap_list 126 * @anon_vma: pointer to anon_vma for this mm,address, when in stable tree 127 * @mm: the memory structure this rmap_item is pointing into 128 * @address: the virtual address this rmap_item tracks (+ flags in low bits) 129 * @oldchecksum: previous checksum of the page at that virtual address 130 * @node: rb node of this rmap_item in the unstable tree 131 * @head: pointer to stable_node heading this list in the stable tree 132 * @hlist: link into hlist of rmap_items hanging off that stable_node 133 */ 134struct rmap_item { 135 struct rmap_item *rmap_list; 136 struct anon_vma *anon_vma; /* when stable */ 137 struct mm_struct *mm; 138 unsigned long address; /* + low bits used for flags below */ 139 unsigned int oldchecksum; /* when unstable */ 140 union { 141 struct rb_node node; /* when node of unstable tree */ 142 struct { /* when listed from stable tree */ 143 struct stable_node *head; 144 struct hlist_node hlist; 145 }; 146 }; 147}; 148 149#define SEQNR_MASK 0x0ff /* low bits of unstable tree seqnr */ 150#define UNSTABLE_FLAG 0x100 /* is a node of the unstable tree */ 151#define STABLE_FLAG 0x200 /* is listed from the stable tree */ 152 153/* The stable and unstable tree heads */ 154static struct rb_root root_stable_tree = RB_ROOT; 155static struct rb_root root_unstable_tree = RB_ROOT; 156 157#define MM_SLOTS_HASH_SHIFT 10 158#define MM_SLOTS_HASH_HEADS (1 << MM_SLOTS_HASH_SHIFT) 159static struct hlist_head mm_slots_hash[MM_SLOTS_HASH_HEADS]; 160 161static struct mm_slot ksm_mm_head = { 162 .mm_list = LIST_HEAD_INIT(ksm_mm_head.mm_list), 163}; 164static struct ksm_scan ksm_scan = { 165 .mm_slot = &ksm_mm_head, 166}; 167 168static struct kmem_cache *rmap_item_cache; 169static struct kmem_cache *stable_node_cache; 170static struct kmem_cache *mm_slot_cache; 171 172/* The number of nodes in the stable tree */ 173static unsigned long ksm_pages_shared; 174 175/* The number of page slots additionally sharing those nodes */ 176static unsigned long ksm_pages_sharing; 177 178/* The number of nodes in the unstable tree */ 179static unsigned long ksm_pages_unshared; 180 181/* The number of rmap_items in use: to calculate pages_volatile */ 182static unsigned long ksm_rmap_items; 183 184/* Number of pages ksmd should scan in one batch */ 185static unsigned int ksm_thread_pages_to_scan = 100; 186 187/* Milliseconds ksmd should sleep between batches */ 188static unsigned int ksm_thread_sleep_millisecs = 20; 189 190#define KSM_RUN_STOP 0 191#define KSM_RUN_MERGE 1 192#define KSM_RUN_UNMERGE 2 193static unsigned int ksm_run = KSM_RUN_STOP; 194 195static DECLARE_WAIT_QUEUE_HEAD(ksm_thread_wait); 196static DEFINE_MUTEX(ksm_thread_mutex); 197static DEFINE_SPINLOCK(ksm_mmlist_lock); 198 199#define KSM_KMEM_CACHE(__struct, __flags) kmem_cache_create("ksm_"#__struct,\ 200 sizeof(struct __struct), __alignof__(struct __struct),\ 201 (__flags), NULL) 202 203static int __init ksm_slab_init(void) 204{ 205 rmap_item_cache = KSM_KMEM_CACHE(rmap_item, 0); 206 if (!rmap_item_cache) 207 goto out; 208 209 stable_node_cache = KSM_KMEM_CACHE(stable_node, 0); 210 if (!stable_node_cache) 211 goto out_free1; 212 213 mm_slot_cache = KSM_KMEM_CACHE(mm_slot, 0); 214 if (!mm_slot_cache) 215 goto out_free2; 216 217 return 0; 218 219out_free2: 220 kmem_cache_destroy(stable_node_cache); 221out_free1: 222 kmem_cache_destroy(rmap_item_cache); 223out: 224 return -ENOMEM; 225} 226 227static void __init ksm_slab_free(void) 228{ 229 kmem_cache_destroy(mm_slot_cache); 230 kmem_cache_destroy(stable_node_cache); 231 kmem_cache_destroy(rmap_item_cache); 232 mm_slot_cache = NULL; 233} 234 235static inline struct rmap_item *alloc_rmap_item(void) 236{ 237 struct rmap_item *rmap_item; 238 239 rmap_item = kmem_cache_zalloc(rmap_item_cache, GFP_KERNEL); 240 if (rmap_item) 241 ksm_rmap_items++; 242 return rmap_item; 243} 244 245static inline void free_rmap_item(struct rmap_item *rmap_item) 246{ 247 ksm_rmap_items--; 248 rmap_item->mm = NULL; /* debug safety */ 249 kmem_cache_free(rmap_item_cache, rmap_item); 250} 251 252static inline struct stable_node *alloc_stable_node(void) 253{ 254 return kmem_cache_alloc(stable_node_cache, GFP_KERNEL); 255} 256 257static inline void free_stable_node(struct stable_node *stable_node) 258{ 259 kmem_cache_free(stable_node_cache, stable_node); 260} 261 262static inline struct mm_slot *alloc_mm_slot(void) 263{ 264 if (!mm_slot_cache) /* initialization failed */ 265 return NULL; 266 return kmem_cache_zalloc(mm_slot_cache, GFP_KERNEL); 267} 268 269static inline void free_mm_slot(struct mm_slot *mm_slot) 270{ 271 kmem_cache_free(mm_slot_cache, mm_slot); 272} 273 274static struct mm_slot *get_mm_slot(struct mm_struct *mm) 275{ 276 struct mm_slot *mm_slot; 277 struct hlist_head *bucket; 278 struct hlist_node *node; 279 280 bucket = &mm_slots_hash[hash_ptr(mm, MM_SLOTS_HASH_SHIFT)]; 281 hlist_for_each_entry(mm_slot, node, bucket, link) { 282 if (mm == mm_slot->mm) 283 return mm_slot; 284 } 285 return NULL; 286} 287 288static void insert_to_mm_slots_hash(struct mm_struct *mm, 289 struct mm_slot *mm_slot) 290{ 291 struct hlist_head *bucket; 292 293 bucket = &mm_slots_hash[hash_ptr(mm, MM_SLOTS_HASH_SHIFT)]; 294 mm_slot->mm = mm; 295 hlist_add_head(&mm_slot->link, bucket); 296} 297 298static inline int in_stable_tree(struct rmap_item *rmap_item) 299{ 300 return rmap_item->address & STABLE_FLAG; 301} 302 303static void hold_anon_vma(struct rmap_item *rmap_item, 304 struct anon_vma *anon_vma) 305{ 306 rmap_item->anon_vma = anon_vma; 307 get_anon_vma(anon_vma); 308} 309 310static void ksm_drop_anon_vma(struct rmap_item *rmap_item) 311{ 312 struct anon_vma *anon_vma = rmap_item->anon_vma; 313 314 drop_anon_vma(anon_vma); 315} 316 317/* 318 * ksmd, and unmerge_and_remove_all_rmap_items(), must not touch an mm's 319 * page tables after it has passed through ksm_exit() - which, if necessary, 320 * takes mmap_sem briefly to serialize against them. ksm_exit() does not set 321 * a special flag: they can just back out as soon as mm_users goes to zero. 322 * ksm_test_exit() is used throughout to make this test for exit: in some 323 * places for correctness, in some places just to avoid unnecessary work. 324 */ 325static inline bool ksm_test_exit(struct mm_struct *mm) 326{ 327 return atomic_read(&mm->mm_users) == 0; 328} 329 330/* 331 * We use break_ksm to break COW on a ksm page: it's a stripped down 332 * 333 * if (get_user_pages(current, mm, addr, 1, 1, 1, &page, NULL) == 1) 334 * put_page(page); 335 * 336 * but taking great care only to touch a ksm page, in a VM_MERGEABLE vma, 337 * in case the application has unmapped and remapped mm,addr meanwhile. 338 * Could a ksm page appear anywhere else? Actually yes, in a VM_PFNMAP 339 * mmap of /dev/mem or /dev/kmem, where we would not want to touch it. 340 */ 341static int break_ksm(struct vm_area_struct *vma, unsigned long addr) 342{ 343 struct page *page; 344 int ret = 0; 345 346 do { 347 cond_resched(); 348 page = follow_page(vma, addr, FOLL_GET); 349 if (IS_ERR_OR_NULL(page)) 350 break; 351 if (PageKsm(page)) 352 ret = handle_mm_fault(vma->vm_mm, vma, addr, 353 FAULT_FLAG_WRITE); 354 else 355 ret = VM_FAULT_WRITE; 356 put_page(page); 357 } while (!(ret & (VM_FAULT_WRITE | VM_FAULT_SIGBUS | VM_FAULT_OOM))); 358 /* 359 * We must loop because handle_mm_fault() may back out if there's 360 * any difficulty e.g. if pte accessed bit gets updated concurrently. 361 * 362 * VM_FAULT_WRITE is what we have been hoping for: it indicates that 363 * COW has been broken, even if the vma does not permit VM_WRITE; 364 * but note that a concurrent fault might break PageKsm for us. 365 * 366 * VM_FAULT_SIGBUS could occur if we race with truncation of the 367 * backing file, which also invalidates anonymous pages: that's 368 * okay, that truncation will have unmapped the PageKsm for us. 369 * 370 * VM_FAULT_OOM: at the time of writing (late July 2009), setting 371 * aside mem_cgroup limits, VM_FAULT_OOM would only be set if the 372 * current task has TIF_MEMDIE set, and will be OOM killed on return 373 * to user; and ksmd, having no mm, would never be chosen for that. 374 * 375 * But if the mm is in a limited mem_cgroup, then the fault may fail 376 * with VM_FAULT_OOM even if the current task is not TIF_MEMDIE; and 377 * even ksmd can fail in this way - though it's usually breaking ksm 378 * just to undo a merge it made a moment before, so unlikely to oom. 379 * 380 * That's a pity: we might therefore have more kernel pages allocated 381 * than we're counting as nodes in the stable tree; but ksm_do_scan 382 * will retry to break_cow on each pass, so should recover the page 383 * in due course. The important thing is to not let VM_MERGEABLE 384 * be cleared while any such pages might remain in the area. 385 */ 386 return (ret & VM_FAULT_OOM) ? -ENOMEM : 0; 387} 388 389static void break_cow(struct rmap_item *rmap_item) 390{ 391 struct mm_struct *mm = rmap_item->mm; 392 unsigned long addr = rmap_item->address; 393 struct vm_area_struct *vma; 394 395 /* 396 * It is not an accident that whenever we want to break COW 397 * to undo, we also need to drop a reference to the anon_vma. 398 */ 399 ksm_drop_anon_vma(rmap_item); 400 401 down_read(&mm->mmap_sem); 402 if (ksm_test_exit(mm)) 403 goto out; 404 vma = find_vma(mm, addr); 405 if (!vma || vma->vm_start > addr) 406 goto out; 407 if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma) 408 goto out; 409 break_ksm(vma, addr); 410out: 411 up_read(&mm->mmap_sem); 412} 413 414static struct page *get_mergeable_page(struct rmap_item *rmap_item) 415{ 416 struct mm_struct *mm = rmap_item->mm; 417 unsigned long addr = rmap_item->address; 418 struct vm_area_struct *vma; 419 struct page *page; 420 421 down_read(&mm->mmap_sem); 422 if (ksm_test_exit(mm)) 423 goto out; 424 vma = find_vma(mm, addr); 425 if (!vma || vma->vm_start > addr) 426 goto out; 427 if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma) 428 goto out; 429 430 page = follow_page(vma, addr, FOLL_GET); 431 if (IS_ERR_OR_NULL(page)) 432 goto out; 433 if (PageAnon(page) && !PageTransCompound(page)) { 434 flush_anon_page(vma, page, addr); 435 flush_dcache_page(page); 436 } else { 437 put_page(page); 438out: page = NULL; 439 } 440 up_read(&mm->mmap_sem); 441 return page; 442} 443 444static void remove_node_from_stable_tree(struct stable_node *stable_node) 445{ 446 struct rmap_item *rmap_item; 447 struct hlist_node *hlist; 448 449 hlist_for_each_entry(rmap_item, hlist, &stable_node->hlist, hlist) { 450 if (rmap_item->hlist.next) 451 ksm_pages_sharing--; 452 else 453 ksm_pages_shared--; 454 ksm_drop_anon_vma(rmap_item); 455 rmap_item->address &= PAGE_MASK; 456 cond_resched(); 457 } 458 459 rb_erase(&stable_node->node, &root_stable_tree); 460 free_stable_node(stable_node); 461} 462 463/* 464 * get_ksm_page: checks if the page indicated by the stable node 465 * is still its ksm page, despite having held no reference to it. 466 * In which case we can trust the content of the page, and it 467 * returns the gotten page; but if the page has now been zapped, 468 * remove the stale node from the stable tree and return NULL. 469 * 470 * You would expect the stable_node to hold a reference to the ksm page. 471 * But if it increments the page's count, swapping out has to wait for 472 * ksmd to come around again before it can free the page, which may take 473 * seconds or even minutes: much too unresponsive. So instead we use a 474 * "keyhole reference": access to the ksm page from the stable node peeps 475 * out through its keyhole to see if that page still holds the right key, 476 * pointing back to this stable node. This relies on freeing a PageAnon 477 * page to reset its page->mapping to NULL, and relies on no other use of 478 * a page to put something that might look like our key in page->mapping. 479 * 480 * include/linux/pagemap.h page_cache_get_speculative() is a good reference, 481 * but this is different - made simpler by ksm_thread_mutex being held, but 482 * interesting for assuming that no other use of the struct page could ever 483 * put our expected_mapping into page->mapping (or a field of the union which 484 * coincides with page->mapping). The RCU calls are not for KSM at all, but 485 * to keep the page_count protocol described with page_cache_get_speculative. 486 * 487 * Note: it is possible that get_ksm_page() will return NULL one moment, 488 * then page the next, if the page is in between page_freeze_refs() and 489 * page_unfreeze_refs(): this shouldn't be a problem anywhere, the page 490 * is on its way to being freed; but it is an anomaly to bear in mind. 491 */ 492static struct page *get_ksm_page(struct stable_node *stable_node) 493{ 494 struct page *page; 495 void *expected_mapping; 496 497 page = pfn_to_page(stable_node->kpfn); 498 expected_mapping = (void *)stable_node + 499 (PAGE_MAPPING_ANON | PAGE_MAPPING_KSM); 500 rcu_read_lock(); 501 if (page->mapping != expected_mapping) 502 goto stale; 503 if (!get_page_unless_zero(page)) 504 goto stale; 505 if (page->mapping != expected_mapping) { 506 put_page(page); 507 goto stale; 508 } 509 rcu_read_unlock(); 510 return page; 511stale: 512 rcu_read_unlock(); 513 remove_node_from_stable_tree(stable_node); 514 return NULL; 515} 516 517/* 518 * Removing rmap_item from stable or unstable tree. 519 * This function will clean the information from the stable/unstable tree. 520 */ 521static void remove_rmap_item_from_tree(struct rmap_item *rmap_item) 522{ 523 if (rmap_item->address & STABLE_FLAG) { 524 struct stable_node *stable_node; 525 struct page *page; 526 527 stable_node = rmap_item->head; 528 page = get_ksm_page(stable_node); 529 if (!page) 530 goto out; 531 532 lock_page(page); 533 hlist_del(&rmap_item->hlist); 534 unlock_page(page); 535 put_page(page); 536 537 if (stable_node->hlist.first) 538 ksm_pages_sharing--; 539 else 540 ksm_pages_shared--; 541 542 ksm_drop_anon_vma(rmap_item); 543 rmap_item->address &= PAGE_MASK; 544 545 } else if (rmap_item->address & UNSTABLE_FLAG) { 546 unsigned char age; 547 /* 548 * Usually ksmd can and must skip the rb_erase, because 549 * root_unstable_tree was already reset to RB_ROOT. 550 * But be careful when an mm is exiting: do the rb_erase 551 * if this rmap_item was inserted by this scan, rather 552 * than left over from before. 553 */ 554 age = (unsigned char)(ksm_scan.seqnr - rmap_item->address); 555 BUG_ON(age > 1); 556 if (!age) 557 rb_erase(&rmap_item->node, &root_unstable_tree); 558 559 ksm_pages_unshared--; 560 rmap_item->address &= PAGE_MASK; 561 } 562out: 563 cond_resched(); /* we're called from many long loops */ 564} 565 566static void remove_trailing_rmap_items(struct mm_slot *mm_slot, 567 struct rmap_item **rmap_list) 568{ 569 while (*rmap_list) { 570 struct rmap_item *rmap_item = *rmap_list; 571 *rmap_list = rmap_item->rmap_list; 572 remove_rmap_item_from_tree(rmap_item); 573 free_rmap_item(rmap_item); 574 } 575} 576 577/* 578 * Though it's very tempting to unmerge in_stable_tree(rmap_item)s rather 579 * than check every pte of a given vma, the locking doesn't quite work for 580 * that - an rmap_item is assigned to the stable tree after inserting ksm 581 * page and upping mmap_sem. Nor does it fit with the way we skip dup'ing 582 * rmap_items from parent to child at fork time (so as not to waste time 583 * if exit comes before the next scan reaches it). 584 * 585 * Similarly, although we'd like to remove rmap_items (so updating counts 586 * and freeing memory) when unmerging an area, it's easier to leave that 587 * to the next pass of ksmd - consider, for example, how ksmd might be 588 * in cmp_and_merge_page on one of the rmap_items we would be removing. 589 */ 590static int unmerge_ksm_pages(struct vm_area_struct *vma, 591 unsigned long start, unsigned long end) 592{ 593 unsigned long addr; 594 int err = 0; 595 596 for (addr = start; addr < end && !err; addr += PAGE_SIZE) { 597 if (ksm_test_exit(vma->vm_mm)) 598 break; 599 if (signal_pending(current)) 600 err = -ERESTARTSYS; 601 else 602 err = break_ksm(vma, addr); 603 } 604 return err; 605} 606 607#ifdef CONFIG_SYSFS 608/* 609 * Only called through the sysfs control interface: 610 */ 611static int unmerge_and_remove_all_rmap_items(void) 612{ 613 struct mm_slot *mm_slot; 614 struct mm_struct *mm; 615 struct vm_area_struct *vma; 616 int err = 0; 617 618 spin_lock(&ksm_mmlist_lock); 619 ksm_scan.mm_slot = list_entry(ksm_mm_head.mm_list.next, 620 struct mm_slot, mm_list); 621 spin_unlock(&ksm_mmlist_lock); 622 623 for (mm_slot = ksm_scan.mm_slot; 624 mm_slot != &ksm_mm_head; mm_slot = ksm_scan.mm_slot) { 625 mm = mm_slot->mm; 626 down_read(&mm->mmap_sem); 627 for (vma = mm->mmap; vma; vma = vma->vm_next) { 628 if (ksm_test_exit(mm)) 629 break; 630 if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma) 631 continue; 632 err = unmerge_ksm_pages(vma, 633 vma->vm_start, vma->vm_end); 634 if (err) 635 goto error; 636 } 637 638 remove_trailing_rmap_items(mm_slot, &mm_slot->rmap_list); 639 640 spin_lock(&ksm_mmlist_lock); 641 ksm_scan.mm_slot = list_entry(mm_slot->mm_list.next, 642 struct mm_slot, mm_list); 643 if (ksm_test_exit(mm)) { 644 hlist_del(&mm_slot->link); 645 list_del(&mm_slot->mm_list); 646 spin_unlock(&ksm_mmlist_lock); 647 648 free_mm_slot(mm_slot); 649 clear_bit(MMF_VM_MERGEABLE, &mm->flags); 650 up_read(&mm->mmap_sem); 651 mmdrop(mm); 652 } else { 653 spin_unlock(&ksm_mmlist_lock); 654 up_read(&mm->mmap_sem); 655 } 656 } 657 658 ksm_scan.seqnr = 0; 659 return 0; 660 661error: 662 up_read(&mm->mmap_sem); 663 spin_lock(&ksm_mmlist_lock); 664 ksm_scan.mm_slot = &ksm_mm_head; 665 spin_unlock(&ksm_mmlist_lock); 666 return err; 667} 668#endif /* CONFIG_SYSFS */ 669 670static u32 calc_checksum(struct page *page) 671{ 672 u32 checksum; 673 void *addr = kmap_atomic(page, KM_USER0); 674 checksum = jhash2(addr, PAGE_SIZE / 4, 17); 675 kunmap_atomic(addr, KM_USER0); 676 return checksum; 677} 678 679static int memcmp_pages(struct page *page1, struct page *page2) 680{ 681 char *addr1, *addr2; 682 int ret; 683 684 addr1 = kmap_atomic(page1, KM_USER0); 685 addr2 = kmap_atomic(page2, KM_USER1); 686 ret = memcmp(addr1, addr2, PAGE_SIZE); 687 kunmap_atomic(addr2, KM_USER1); 688 kunmap_atomic(addr1, KM_USER0); 689 return ret; 690} 691 692static inline int pages_identical(struct page *page1, struct page *page2) 693{ 694 return !memcmp_pages(page1, page2); 695} 696 697static int write_protect_page(struct vm_area_struct *vma, struct page *page, 698 pte_t *orig_pte) 699{ 700 struct mm_struct *mm = vma->vm_mm; 701 unsigned long addr; 702 pte_t *ptep; 703 spinlock_t *ptl; 704 int swapped; 705 int err = -EFAULT; 706 707 addr = page_address_in_vma(page, vma); 708 if (addr == -EFAULT) 709 goto out; 710 711 ptep = page_check_address(page, mm, addr, &ptl, 0); 712 if (!ptep) 713 goto out; 714 715 if (pte_write(*ptep) || pte_dirty(*ptep)) { 716 pte_t entry; 717 718 swapped = PageSwapCache(page); 719 flush_cache_page(vma, addr, page_to_pfn(page)); 720 /* 721 * Ok this is tricky, when get_user_pages_fast() run it doesnt 722 * take any lock, therefore the check that we are going to make 723 * with the pagecount against the mapcount is racey and 724 * O_DIRECT can happen right after the check. 725 * So we clear the pte and flush the tlb before the check 726 * this assure us that no O_DIRECT can happen after the check 727 * or in the middle of the check. 728 */ 729 entry = ptep_clear_flush(vma, addr, ptep); 730 /* 731 * Check that no O_DIRECT or similar I/O is in progress on the 732 * page 733 */ 734 if (page_mapcount(page) + 1 + swapped != page_count(page)) { 735 set_pte_at(mm, addr, ptep, entry); 736 goto out_unlock; 737 } 738 if (pte_dirty(entry)) 739 set_page_dirty(page); 740 entry = pte_mkclean(pte_wrprotect(entry)); 741 set_pte_at_notify(mm, addr, ptep, entry); 742 } 743 *orig_pte = *ptep; 744 err = 0; 745 746out_unlock: 747 pte_unmap_unlock(ptep, ptl); 748out: 749 return err; 750} 751 752/** 753 * replace_page - replace page in vma by new ksm page 754 * @vma: vma that holds the pte pointing to page 755 * @page: the page we are replacing by kpage 756 * @kpage: the ksm page we replace page by 757 * @orig_pte: the original value of the pte 758 * 759 * Returns 0 on success, -EFAULT on failure. 760 */ 761static int replace_page(struct vm_area_struct *vma, struct page *page, 762 struct page *kpage, pte_t orig_pte) 763{ 764 struct mm_struct *mm = vma->vm_mm; 765 pgd_t *pgd; 766 pud_t *pud; 767 pmd_t *pmd; 768 pte_t *ptep; 769 spinlock_t *ptl; 770 unsigned long addr; 771 int err = -EFAULT; 772 773 addr = page_address_in_vma(page, vma); 774 if (addr == -EFAULT) 775 goto out; 776 777 pgd = pgd_offset(mm, addr); 778 if (!pgd_present(*pgd)) 779 goto out; 780 781 pud = pud_offset(pgd, addr); 782 if (!pud_present(*pud)) 783 goto out; 784 785 pmd = pmd_offset(pud, addr); 786 if (!pmd_present(*pmd)) 787 goto out; 788 789 ptep = pte_offset_map_lock(mm, pmd, addr, &ptl); 790 if (!pte_same(*ptep, orig_pte)) { 791 pte_unmap_unlock(ptep, ptl); 792 goto out; 793 } 794 795 get_page(kpage); 796 page_add_anon_rmap(kpage, vma, addr); 797 798 flush_cache_page(vma, addr, pte_pfn(*ptep)); 799 ptep_clear_flush(vma, addr, ptep); 800 set_pte_at_notify(mm, addr, ptep, mk_pte(kpage, vma->vm_page_prot)); 801 802 page_remove_rmap(page); 803 if (!page_mapped(page)) 804 try_to_free_swap(page); 805 put_page(page); 806 807 pte_unmap_unlock(ptep, ptl); 808 err = 0; 809out: 810 return err; 811} 812 813/* 814 * try_to_merge_one_page - take two pages and merge them into one 815 * @vma: the vma that holds the pte pointing to page 816 * @page: the PageAnon page that we want to replace with kpage 817 * @kpage: the PageKsm page that we want to map instead of page, 818 * or NULL the first time when we want to use page as kpage. 819 * 820 * This function returns 0 if the pages were merged, -EFAULT otherwise. 821 */ 822static int try_to_merge_one_page(struct vm_area_struct *vma, 823 struct page *page, struct page *kpage) 824{ 825 pte_t orig_pte = __pte(0); 826 int err = -EFAULT; 827 828 if (page == kpage) /* ksm page forked */ 829 return 0; 830 831 if (!(vma->vm_flags & VM_MERGEABLE)) 832 goto out; 833 if (!PageAnon(page)) 834 goto out; 835 836 /* 837 * We need the page lock to read a stable PageSwapCache in 838 * write_protect_page(). We use trylock_page() instead of 839 * lock_page() because we don't want to wait here - we 840 * prefer to continue scanning and merging different pages, 841 * then come back to this page when it is unlocked. 842 */ 843 if (!trylock_page(page)) 844 goto out; 845 /* 846 * If this anonymous page is mapped only here, its pte may need 847 * to be write-protected. If it's mapped elsewhere, all of its 848 * ptes are necessarily already write-protected. But in either 849 * case, we need to lock and check page_count is not raised. 850 */ 851 if (write_protect_page(vma, page, &orig_pte) == 0) { 852 if (!kpage) { 853 /* 854 * While we hold page lock, upgrade page from 855 * PageAnon+anon_vma to PageKsm+NULL stable_node: 856 * stable_tree_insert() will update stable_node. 857 */ 858 set_page_stable_node(page, NULL); 859 mark_page_accessed(page); 860 err = 0; 861 } else if (pages_identical(page, kpage)) 862 err = replace_page(vma, page, kpage, orig_pte); 863 } 864 865 if ((vma->vm_flags & VM_LOCKED) && kpage && !err) { 866 munlock_vma_page(page); 867 if (!PageMlocked(kpage)) { 868 unlock_page(page); 869 lock_page(kpage); 870 mlock_vma_page(kpage); 871 page = kpage; /* for final unlock */ 872 } 873 } 874 875 unlock_page(page); 876out: 877 return err; 878} 879 880/* 881 * try_to_merge_with_ksm_page - like try_to_merge_two_pages, 882 * but no new kernel page is allocated: kpage must already be a ksm page. 883 * 884 * This function returns 0 if the pages were merged, -EFAULT otherwise. 885 */ 886static int try_to_merge_with_ksm_page(struct rmap_item *rmap_item, 887 struct page *page, struct page *kpage) 888{ 889 struct mm_struct *mm = rmap_item->mm; 890 struct vm_area_struct *vma; 891 int err = -EFAULT; 892 893 down_read(&mm->mmap_sem); 894 if (ksm_test_exit(mm)) 895 goto out; 896 vma = find_vma(mm, rmap_item->address); 897 if (!vma || vma->vm_start > rmap_item->address) 898 goto out; 899 900 err = try_to_merge_one_page(vma, page, kpage); 901 if (err) 902 goto out; 903 904 /* Must get reference to anon_vma while still holding mmap_sem */ 905 hold_anon_vma(rmap_item, vma->anon_vma); 906out: 907 up_read(&mm->mmap_sem); 908 return err; 909} 910 911/* 912 * try_to_merge_two_pages - take two identical pages and prepare them 913 * to be merged into one page. 914 * 915 * This function returns the kpage if we successfully merged two identical 916 * pages into one ksm page, NULL otherwise. 917 * 918 * Note that this function upgrades page to ksm page: if one of the pages 919 * is already a ksm page, try_to_merge_with_ksm_page should be used. 920 */ 921static struct page *try_to_merge_two_pages(struct rmap_item *rmap_item, 922 struct page *page, 923 struct rmap_item *tree_rmap_item, 924 struct page *tree_page) 925{ 926 int err; 927 928 err = try_to_merge_with_ksm_page(rmap_item, page, NULL); 929 if (!err) { 930 err = try_to_merge_with_ksm_page(tree_rmap_item, 931 tree_page, page); 932 /* 933 * If that fails, we have a ksm page with only one pte 934 * pointing to it: so break it. 935 */ 936 if (err) 937 break_cow(rmap_item); 938 } 939 return err ? NULL : page; 940} 941 942/* 943 * stable_tree_search - search for page inside the stable tree 944 * 945 * This function checks if there is a page inside the stable tree 946 * with identical content to the page that we are scanning right now. 947 * 948 * This function returns the stable tree node of identical content if found, 949 * NULL otherwise. 950 */ 951static struct page *stable_tree_search(struct page *page) 952{ 953 struct rb_node *node = root_stable_tree.rb_node; 954 struct stable_node *stable_node; 955 956 stable_node = page_stable_node(page); 957 if (stable_node) { /* ksm page forked */ 958 get_page(page); 959 return page; 960 } 961 962 while (node) { 963 struct page *tree_page; 964 int ret; 965 966 cond_resched(); 967 stable_node = rb_entry(node, struct stable_node, node); 968 tree_page = get_ksm_page(stable_node); 969 if (!tree_page) 970 return NULL; 971 972 ret = memcmp_pages(page, tree_page); 973 974 if (ret < 0) { 975 put_page(tree_page); 976 node = node->rb_left; 977 } else if (ret > 0) { 978 put_page(tree_page); 979 node = node->rb_right; 980 } else 981 return tree_page; 982 } 983 984 return NULL; 985} 986 987/* 988 * stable_tree_insert - insert rmap_item pointing to new ksm page 989 * into the stable tree. 990 * 991 * This function returns the stable tree node just allocated on success, 992 * NULL otherwise. 993 */ 994static struct stable_node *stable_tree_insert(struct page *kpage) 995{ 996 struct rb_node **new = &root_stable_tree.rb_node; 997 struct rb_node *parent = NULL; 998 struct stable_node *stable_node; 999 1000 while (*new) { 1001 struct page *tree_page; 1002 int ret; 1003 1004 cond_resched(); 1005 stable_node = rb_entry(*new, struct stable_node, node); 1006 tree_page = get_ksm_page(stable_node); 1007 if (!tree_page) 1008 return NULL; 1009 1010 ret = memcmp_pages(kpage, tree_page); 1011 put_page(tree_page); 1012 1013 parent = *new; 1014 if (ret < 0) 1015 new = &parent->rb_left; 1016 else if (ret > 0) 1017 new = &parent->rb_right; 1018 else { 1019 /* 1020 * It is not a bug that stable_tree_search() didn't 1021 * find this node: because at that time our page was 1022 * not yet write-protected, so may have changed since. 1023 */ 1024 return NULL; 1025 } 1026 } 1027 1028 stable_node = alloc_stable_node(); 1029 if (!stable_node) 1030 return NULL; 1031 1032 rb_link_node(&stable_node->node, parent, new); 1033 rb_insert_color(&stable_node->node, &root_stable_tree); 1034 1035 INIT_HLIST_HEAD(&stable_node->hlist); 1036 1037 stable_node->kpfn = page_to_pfn(kpage); 1038 set_page_stable_node(kpage, stable_node); 1039 1040 return stable_node; 1041} 1042 1043/* 1044 * unstable_tree_search_insert - search for identical page, 1045 * else insert rmap_item into the unstable tree. 1046 * 1047 * This function searches for a page in the unstable tree identical to the 1048 * page currently being scanned; and if no identical page is found in the 1049 * tree, we insert rmap_item as a new object into the unstable tree. 1050 * 1051 * This function returns pointer to rmap_item found to be identical 1052 * to the currently scanned page, NULL otherwise. 1053 * 1054 * This function does both searching and inserting, because they share 1055 * the same walking algorithm in an rbtree. 1056 */ 1057static 1058struct rmap_item *unstable_tree_search_insert(struct rmap_item *rmap_item, 1059 struct page *page, 1060 struct page **tree_pagep) 1061 1062{ 1063 struct rb_node **new = &root_unstable_tree.rb_node; 1064 struct rb_node *parent = NULL; 1065 1066 while (*new) { 1067 struct rmap_item *tree_rmap_item; 1068 struct page *tree_page; 1069 int ret; 1070 1071 cond_resched(); 1072 tree_rmap_item = rb_entry(*new, struct rmap_item, node); 1073 tree_page = get_mergeable_page(tree_rmap_item); 1074 if (IS_ERR_OR_NULL(tree_page)) 1075 return NULL; 1076 1077 /* 1078 * Don't substitute a ksm page for a forked page. 1079 */ 1080 if (page == tree_page) { 1081 put_page(tree_page); 1082 return NULL; 1083 } 1084 1085 ret = memcmp_pages(page, tree_page); 1086 1087 parent = *new; 1088 if (ret < 0) { 1089 put_page(tree_page); 1090 new = &parent->rb_left; 1091 } else if (ret > 0) { 1092 put_page(tree_page); 1093 new = &parent->rb_right; 1094 } else { 1095 *tree_pagep = tree_page; 1096 return tree_rmap_item; 1097 } 1098 } 1099 1100 rmap_item->address |= UNSTABLE_FLAG; 1101 rmap_item->address |= (ksm_scan.seqnr & SEQNR_MASK); 1102 rb_link_node(&rmap_item->node, parent, new); 1103 rb_insert_color(&rmap_item->node, &root_unstable_tree); 1104 1105 ksm_pages_unshared++; 1106 return NULL; 1107} 1108 1109/* 1110 * stable_tree_append - add another rmap_item to the linked list of 1111 * rmap_items hanging off a given node of the stable tree, all sharing 1112 * the same ksm page. 1113 */ 1114static void stable_tree_append(struct rmap_item *rmap_item, 1115 struct stable_node *stable_node) 1116{ 1117 rmap_item->head = stable_node; 1118 rmap_item->address |= STABLE_FLAG; 1119 hlist_add_head(&rmap_item->hlist, &stable_node->hlist); 1120 1121 if (rmap_item->hlist.next) 1122 ksm_pages_sharing++; 1123 else 1124 ksm_pages_shared++; 1125} 1126 1127/* 1128 * cmp_and_merge_page - first see if page can be merged into the stable tree; 1129 * if not, compare checksum to previous and if it's the same, see if page can 1130 * be inserted into the unstable tree, or merged with a page already there and 1131 * both transferred to the stable tree. 1132 * 1133 * @page: the page that we are searching identical page to. 1134 * @rmap_item: the reverse mapping into the virtual address of this page 1135 */ 1136static void cmp_and_merge_page(struct page *page, struct rmap_item *rmap_item) 1137{ 1138 struct rmap_item *tree_rmap_item; 1139 struct page *tree_page = NULL; 1140 struct stable_node *stable_node; 1141 struct page *kpage; 1142 unsigned int checksum; 1143 int err; 1144 1145 remove_rmap_item_from_tree(rmap_item); 1146 1147 /* We first start with searching the page inside the stable tree */ 1148 kpage = stable_tree_search(page); 1149 if (kpage) { 1150 err = try_to_merge_with_ksm_page(rmap_item, page, kpage); 1151 if (!err) { 1152 /* 1153 * The page was successfully merged: 1154 * add its rmap_item to the stable tree. 1155 */ 1156 lock_page(kpage); 1157 stable_tree_append(rmap_item, page_stable_node(kpage)); 1158 unlock_page(kpage); 1159 } 1160 put_page(kpage); 1161 return; 1162 } 1163 1164 /* 1165 * If the hash value of the page has changed from the last time 1166 * we calculated it, this page is changing frequently: therefore we 1167 * don't want to insert it in the unstable tree, and we don't want 1168 * to waste our time searching for something identical to it there. 1169 */ 1170 checksum = calc_checksum(page); 1171 if (rmap_item->oldchecksum != checksum) { 1172 rmap_item->oldchecksum = checksum; 1173 return; 1174 } 1175 1176 tree_rmap_item = 1177 unstable_tree_search_insert(rmap_item, page, &tree_page); 1178 if (tree_rmap_item) { 1179 kpage = try_to_merge_two_pages(rmap_item, page, 1180 tree_rmap_item, tree_page); 1181 put_page(tree_page); 1182 /* 1183 * As soon as we merge this page, we want to remove the 1184 * rmap_item of the page we have merged with from the unstable 1185 * tree, and insert it instead as new node in the stable tree. 1186 */ 1187 if (kpage) { 1188 remove_rmap_item_from_tree(tree_rmap_item); 1189 1190 lock_page(kpage); 1191 stable_node = stable_tree_insert(kpage); 1192 if (stable_node) { 1193 stable_tree_append(tree_rmap_item, stable_node); 1194 stable_tree_append(rmap_item, stable_node); 1195 } 1196 unlock_page(kpage); 1197 1198 /* 1199 * If we fail to insert the page into the stable tree, 1200 * we will have 2 virtual addresses that are pointing 1201 * to a ksm page left outside the stable tree, 1202 * in which case we need to break_cow on both. 1203 */ 1204 if (!stable_node) { 1205 break_cow(tree_rmap_item); 1206 break_cow(rmap_item); 1207 } 1208 } 1209 } 1210} 1211 1212static struct rmap_item *get_next_rmap_item(struct mm_slot *mm_slot, 1213 struct rmap_item **rmap_list, 1214 unsigned long addr) 1215{ 1216 struct rmap_item *rmap_item; 1217 1218 while (*rmap_list) { 1219 rmap_item = *rmap_list; 1220 if ((rmap_item->address & PAGE_MASK) == addr) 1221 return rmap_item; 1222 if (rmap_item->address > addr) 1223 break; 1224 *rmap_list = rmap_item->rmap_list; 1225 remove_rmap_item_from_tree(rmap_item); 1226 free_rmap_item(rmap_item); 1227 } 1228 1229 rmap_item = alloc_rmap_item(); 1230 if (rmap_item) { 1231 /* It has already been zeroed */ 1232 rmap_item->mm = mm_slot->mm; 1233 rmap_item->address = addr; 1234 rmap_item->rmap_list = *rmap_list; 1235 *rmap_list = rmap_item; 1236 } 1237 return rmap_item; 1238} 1239 1240static struct rmap_item *scan_get_next_rmap_item(struct page **page) 1241{ 1242 struct mm_struct *mm; 1243 struct mm_slot *slot; 1244 struct vm_area_struct *vma; 1245 struct rmap_item *rmap_item; 1246 1247 if (list_empty(&ksm_mm_head.mm_list)) 1248 return NULL; 1249 1250 slot = ksm_scan.mm_slot; 1251 if (slot == &ksm_mm_head) { 1252 root_unstable_tree = RB_ROOT; 1253 1254 spin_lock(&ksm_mmlist_lock); 1255 slot = list_entry(slot->mm_list.next, struct mm_slot, mm_list); 1256 ksm_scan.mm_slot = slot; 1257 spin_unlock(&ksm_mmlist_lock); 1258next_mm: 1259 ksm_scan.address = 0; 1260 ksm_scan.rmap_list = &slot->rmap_list; 1261 } 1262 1263 mm = slot->mm; 1264 down_read(&mm->mmap_sem); 1265 if (ksm_test_exit(mm)) 1266 vma = NULL; 1267 else 1268 vma = find_vma(mm, ksm_scan.address); 1269 1270 for (; vma; vma = vma->vm_next) { 1271 if (!(vma->vm_flags & VM_MERGEABLE)) 1272 continue; 1273 if (ksm_scan.address < vma->vm_start) 1274 ksm_scan.address = vma->vm_start; 1275 if (!vma->anon_vma) 1276 ksm_scan.address = vma->vm_end; 1277 1278 while (ksm_scan.address < vma->vm_end) { 1279 if (ksm_test_exit(mm)) 1280 break; 1281 *page = follow_page(vma, ksm_scan.address, FOLL_GET); 1282 if (IS_ERR_OR_NULL(*page)) { 1283 ksm_scan.address += PAGE_SIZE; 1284 cond_resched(); 1285 continue; 1286 } 1287 if (PageTransCompound(*page)) { 1288 put_page(*page); 1289 ksm_scan.address &= HPAGE_PMD_MASK; 1290 ksm_scan.address += HPAGE_PMD_SIZE; 1291 cond_resched(); 1292 continue; 1293 } 1294 if (PageAnon(*page)) { 1295 flush_anon_page(vma, *page, ksm_scan.address); 1296 flush_dcache_page(*page); 1297 rmap_item = get_next_rmap_item(slot, 1298 ksm_scan.rmap_list, ksm_scan.address); 1299 if (rmap_item) { 1300 ksm_scan.rmap_list = 1301 &rmap_item->rmap_list; 1302 ksm_scan.address += PAGE_SIZE; 1303 } else 1304 put_page(*page); 1305 up_read(&mm->mmap_sem); 1306 return rmap_item; 1307 } 1308 put_page(*page); 1309 ksm_scan.address += PAGE_SIZE; 1310 cond_resched(); 1311 } 1312 } 1313 1314 if (ksm_test_exit(mm)) { 1315 ksm_scan.address = 0; 1316 ksm_scan.rmap_list = &slot->rmap_list; 1317 } 1318 /* 1319 * Nuke all the rmap_items that are above this current rmap: 1320 * because there were no VM_MERGEABLE vmas with such addresses. 1321 */ 1322 remove_trailing_rmap_items(slot, ksm_scan.rmap_list); 1323 1324 spin_lock(&ksm_mmlist_lock); 1325 ksm_scan.mm_slot = list_entry(slot->mm_list.next, 1326 struct mm_slot, mm_list); 1327 if (ksm_scan.address == 0) { 1328 /* 1329 * We've completed a full scan of all vmas, holding mmap_sem 1330 * throughout, and found no VM_MERGEABLE: so do the same as 1331 * __ksm_exit does to remove this mm from all our lists now. 1332 * This applies either when cleaning up after __ksm_exit 1333 * (but beware: we can reach here even before __ksm_exit), 1334 * or when all VM_MERGEABLE areas have been unmapped (and 1335 * mmap_sem then protects against race with MADV_MERGEABLE). 1336 */ 1337 hlist_del(&slot->link); 1338 list_del(&slot->mm_list); 1339 spin_unlock(&ksm_mmlist_lock); 1340 1341 free_mm_slot(slot); 1342 clear_bit(MMF_VM_MERGEABLE, &mm->flags); 1343 up_read(&mm->mmap_sem); 1344 mmdrop(mm); 1345 } else { 1346 spin_unlock(&ksm_mmlist_lock); 1347 up_read(&mm->mmap_sem); 1348 } 1349 1350 /* Repeat until we've completed scanning the whole list */ 1351 slot = ksm_scan.mm_slot; 1352 if (slot != &ksm_mm_head) 1353 goto next_mm; 1354 1355 ksm_scan.seqnr++; 1356 return NULL; 1357} 1358 1359/** 1360 * ksm_do_scan - the ksm scanner main worker function. 1361 * @scan_npages - number of pages we want to scan before we return. 1362 */ 1363static void ksm_do_scan(unsigned int scan_npages) 1364{ 1365 struct rmap_item *rmap_item; 1366 struct page *uninitialized_var(page); 1367 1368 while (scan_npages--) { 1369 cond_resched(); 1370 rmap_item = scan_get_next_rmap_item(&page); 1371 if (!rmap_item) 1372 return; 1373 if (!PageKsm(page) || !in_stable_tree(rmap_item)) 1374 cmp_and_merge_page(page, rmap_item); 1375 put_page(page); 1376 } 1377} 1378 1379static int ksmd_should_run(void) 1380{ 1381 return (ksm_run & KSM_RUN_MERGE) && !list_empty(&ksm_mm_head.mm_list); 1382} 1383 1384static int ksm_scan_thread(void *nothing) 1385{ 1386 set_user_nice(current, 5); 1387 1388 while (!kthread_should_stop()) { 1389 mutex_lock(&ksm_thread_mutex); 1390 if (ksmd_should_run()) 1391 ksm_do_scan(ksm_thread_pages_to_scan); 1392 mutex_unlock(&ksm_thread_mutex); 1393 1394 if (ksmd_should_run()) { 1395 schedule_timeout_interruptible( 1396 msecs_to_jiffies(ksm_thread_sleep_millisecs)); 1397 } else { 1398 wait_event_interruptible(ksm_thread_wait, 1399 ksmd_should_run() || kthread_should_stop()); 1400 } 1401 } 1402 return 0; 1403} 1404 1405int ksm_madvise(struct vm_area_struct *vma, unsigned long start, 1406 unsigned long end, int advice, unsigned long *vm_flags) 1407{ 1408 struct mm_struct *mm = vma->vm_mm; 1409 int err; 1410 1411 switch (advice) { 1412 case MADV_MERGEABLE: 1413 /* 1414 * Be somewhat over-protective for now! 1415 */ 1416 if (*vm_flags & (VM_MERGEABLE | VM_SHARED | VM_MAYSHARE | 1417 VM_PFNMAP | VM_IO | VM_DONTEXPAND | 1418 VM_RESERVED | VM_HUGETLB | VM_INSERTPAGE | 1419 VM_NONLINEAR | VM_MIXEDMAP | VM_SAO)) 1420 return 0; /* just ignore the advice */ 1421 1422 if (!test_bit(MMF_VM_MERGEABLE, &mm->flags)) { 1423 err = __ksm_enter(mm); 1424 if (err) 1425 return err; 1426 } 1427 1428 *vm_flags |= VM_MERGEABLE; 1429 break; 1430 1431 case MADV_UNMERGEABLE: 1432 if (!(*vm_flags & VM_MERGEABLE)) 1433 return 0; /* just ignore the advice */ 1434 1435 if (vma->anon_vma) { 1436 err = unmerge_ksm_pages(vma, start, end); 1437 if (err) 1438 return err; 1439 } 1440 1441 *vm_flags &= ~VM_MERGEABLE; 1442 break; 1443 } 1444 1445 return 0; 1446} 1447 1448int __ksm_enter(struct mm_struct *mm) 1449{ 1450 struct mm_slot *mm_slot; 1451 int needs_wakeup; 1452 1453 mm_slot = alloc_mm_slot(); 1454 if (!mm_slot) 1455 return -ENOMEM; 1456 1457 /* Check ksm_run too? Would need tighter locking */ 1458 needs_wakeup = list_empty(&ksm_mm_head.mm_list); 1459 1460 spin_lock(&ksm_mmlist_lock); 1461 insert_to_mm_slots_hash(mm, mm_slot); 1462 /* 1463 * Insert just behind the scanning cursor, to let the area settle 1464 * down a little; when fork is followed by immediate exec, we don't 1465 * want ksmd to waste time setting up and tearing down an rmap_list. 1466 */ 1467 list_add_tail(&mm_slot->mm_list, &ksm_scan.mm_slot->mm_list); 1468 spin_unlock(&ksm_mmlist_lock); 1469 1470 set_bit(MMF_VM_MERGEABLE, &mm->flags); 1471 atomic_inc(&mm->mm_count); 1472 1473 if (needs_wakeup) 1474 wake_up_interruptible(&ksm_thread_wait); 1475 1476 return 0; 1477} 1478 1479void __ksm_exit(struct mm_struct *mm) 1480{ 1481 struct mm_slot *mm_slot; 1482 int easy_to_free = 0; 1483 1484 /* 1485 * This process is exiting: if it's straightforward (as is the 1486 * case when ksmd was never running), free mm_slot immediately. 1487 * But if it's at the cursor or has rmap_items linked to it, use 1488 * mmap_sem to synchronize with any break_cows before pagetables 1489 * are freed, and leave the mm_slot on the list for ksmd to free. 1490 * Beware: ksm may already have noticed it exiting and freed the slot. 1491 */ 1492 1493 spin_lock(&ksm_mmlist_lock); 1494 mm_slot = get_mm_slot(mm); 1495 if (mm_slot && ksm_scan.mm_slot != mm_slot) { 1496 if (!mm_slot->rmap_list) { 1497 hlist_del(&mm_slot->link); 1498 list_del(&mm_slot->mm_list); 1499 easy_to_free = 1; 1500 } else { 1501 list_move(&mm_slot->mm_list, 1502 &ksm_scan.mm_slot->mm_list); 1503 } 1504 } 1505 spin_unlock(&ksm_mmlist_lock); 1506 1507 if (easy_to_free) { 1508 free_mm_slot(mm_slot); 1509 clear_bit(MMF_VM_MERGEABLE, &mm->flags); 1510 mmdrop(mm); 1511 } else if (mm_slot) { 1512 down_write(&mm->mmap_sem); 1513 up_write(&mm->mmap_sem); 1514 } 1515} 1516 1517struct page *ksm_does_need_to_copy(struct page *page, 1518 struct vm_area_struct *vma, unsigned long address) 1519{ 1520 struct page *new_page; 1521 1522 new_page = alloc_page_vma(GFP_HIGHUSER_MOVABLE, vma, address); 1523 if (new_page) { 1524 copy_user_highpage(new_page, page, address, vma); 1525 1526 SetPageDirty(new_page); 1527 __SetPageUptodate(new_page); 1528 SetPageSwapBacked(new_page); 1529 __set_page_locked(new_page); 1530 1531 if (page_evictable(new_page, vma)) 1532 lru_cache_add_lru(new_page, LRU_ACTIVE_ANON); 1533 else 1534 add_page_to_unevictable_list(new_page); 1535 } 1536 1537 return new_page; 1538} 1539 1540int page_referenced_ksm(struct page *page, struct mem_cgroup *memcg, 1541 unsigned long *vm_flags) 1542{ 1543 struct stable_node *stable_node; 1544 struct rmap_item *rmap_item; 1545 struct hlist_node *hlist; 1546 unsigned int mapcount = page_mapcount(page); 1547 int referenced = 0; 1548 int search_new_forks = 0; 1549 1550 VM_BUG_ON(!PageKsm(page)); 1551 VM_BUG_ON(!PageLocked(page)); 1552 1553 stable_node = page_stable_node(page); 1554 if (!stable_node) 1555 return 0; 1556again: 1557 hlist_for_each_entry(rmap_item, hlist, &stable_node->hlist, hlist) { 1558 struct anon_vma *anon_vma = rmap_item->anon_vma; 1559 struct anon_vma_chain *vmac; 1560 struct vm_area_struct *vma; 1561 1562 anon_vma_lock(anon_vma); 1563 list_for_each_entry(vmac, &anon_vma->head, same_anon_vma) { 1564 vma = vmac->vma; 1565 if (rmap_item->address < vma->vm_start || 1566 rmap_item->address >= vma->vm_end) 1567 continue; 1568 /* 1569 * Initially we examine only the vma which covers this 1570 * rmap_item; but later, if there is still work to do, 1571 * we examine covering vmas in other mms: in case they 1572 * were forked from the original since ksmd passed. 1573 */ 1574 if ((rmap_item->mm == vma->vm_mm) == search_new_forks) 1575 continue; 1576 1577 if (memcg && !mm_match_cgroup(vma->vm_mm, memcg)) 1578 continue; 1579 1580 referenced += page_referenced_one(page, vma, 1581 rmap_item->address, &mapcount, vm_flags); 1582 if (!search_new_forks || !mapcount) 1583 break; 1584 } 1585 anon_vma_unlock(anon_vma); 1586 if (!mapcount) 1587 goto out; 1588 } 1589 if (!search_new_forks++) 1590 goto again; 1591out: 1592 return referenced; 1593} 1594 1595int try_to_unmap_ksm(struct page *page, enum ttu_flags flags) 1596{ 1597 struct stable_node *stable_node; 1598 struct hlist_node *hlist; 1599 struct rmap_item *rmap_item; 1600 int ret = SWAP_AGAIN; 1601 int search_new_forks = 0; 1602 1603 VM_BUG_ON(!PageKsm(page)); 1604 VM_BUG_ON(!PageLocked(page)); 1605 1606 stable_node = page_stable_node(page); 1607 if (!stable_node) 1608 return SWAP_FAIL; 1609again: 1610 hlist_for_each_entry(rmap_item, hlist, &stable_node->hlist, hlist) { 1611 struct anon_vma *anon_vma = rmap_item->anon_vma; 1612 struct anon_vma_chain *vmac; 1613 struct vm_area_struct *vma; 1614 1615 anon_vma_lock(anon_vma); 1616 list_for_each_entry(vmac, &anon_vma->head, same_anon_vma) { 1617 vma = vmac->vma; 1618 if (rmap_item->address < vma->vm_start || 1619 rmap_item->address >= vma->vm_end) 1620 continue; 1621 /* 1622 * Initially we examine only the vma which covers this 1623 * rmap_item; but later, if there is still work to do, 1624 * we examine covering vmas in other mms: in case they 1625 * were forked from the original since ksmd passed. 1626 */ 1627 if ((rmap_item->mm == vma->vm_mm) == search_new_forks) 1628 continue; 1629 1630 ret = try_to_unmap_one(page, vma, 1631 rmap_item->address, flags); 1632 if (ret != SWAP_AGAIN || !page_mapped(page)) { 1633 anon_vma_unlock(anon_vma); 1634 goto out; 1635 } 1636 } 1637 anon_vma_unlock(anon_vma); 1638 } 1639 if (!search_new_forks++) 1640 goto again; 1641out: 1642 return ret; 1643} 1644 1645#ifdef CONFIG_MIGRATION 1646int rmap_walk_ksm(struct page *page, int (*rmap_one)(struct page *, 1647 struct vm_area_struct *, unsigned long, void *), void *arg) 1648{ 1649 struct stable_node *stable_node; 1650 struct hlist_node *hlist; 1651 struct rmap_item *rmap_item; 1652 int ret = SWAP_AGAIN; 1653 int search_new_forks = 0; 1654 1655 VM_BUG_ON(!PageKsm(page)); 1656 VM_BUG_ON(!PageLocked(page)); 1657 1658 stable_node = page_stable_node(page); 1659 if (!stable_node) 1660 return ret; 1661again: 1662 hlist_for_each_entry(rmap_item, hlist, &stable_node->hlist, hlist) { 1663 struct anon_vma *anon_vma = rmap_item->anon_vma; 1664 struct anon_vma_chain *vmac; 1665 struct vm_area_struct *vma; 1666 1667 anon_vma_lock(anon_vma); 1668 list_for_each_entry(vmac, &anon_vma->head, same_anon_vma) { 1669 vma = vmac->vma; 1670 if (rmap_item->address < vma->vm_start || 1671 rmap_item->address >= vma->vm_end) 1672 continue; 1673 /* 1674 * Initially we examine only the vma which covers this 1675 * rmap_item; but later, if there is still work to do, 1676 * we examine covering vmas in other mms: in case they 1677 * were forked from the original since ksmd passed. 1678 */ 1679 if ((rmap_item->mm == vma->vm_mm) == search_new_forks) 1680 continue; 1681 1682 ret = rmap_one(page, vma, rmap_item->address, arg); 1683 if (ret != SWAP_AGAIN) { 1684 anon_vma_unlock(anon_vma); 1685 goto out; 1686 } 1687 } 1688 anon_vma_unlock(anon_vma); 1689 } 1690 if (!search_new_forks++) 1691 goto again; 1692out: 1693 return ret; 1694} 1695 1696void ksm_migrate_page(struct page *newpage, struct page *oldpage) 1697{ 1698 struct stable_node *stable_node; 1699 1700 VM_BUG_ON(!PageLocked(oldpage)); 1701 VM_BUG_ON(!PageLocked(newpage)); 1702 VM_BUG_ON(newpage->mapping != oldpage->mapping); 1703 1704 stable_node = page_stable_node(newpage); 1705 if (stable_node) { 1706 VM_BUG_ON(stable_node->kpfn != page_to_pfn(oldpage)); 1707 stable_node->kpfn = page_to_pfn(newpage); 1708 } 1709} 1710#endif /* CONFIG_MIGRATION */ 1711 1712#ifdef CONFIG_MEMORY_HOTREMOVE 1713static struct stable_node *ksm_check_stable_tree(unsigned long start_pfn, 1714 unsigned long end_pfn) 1715{ 1716 struct rb_node *node; 1717 1718 for (node = rb_first(&root_stable_tree); node; node = rb_next(node)) { 1719 struct stable_node *stable_node; 1720 1721 stable_node = rb_entry(node, struct stable_node, node); 1722 if (stable_node->kpfn >= start_pfn && 1723 stable_node->kpfn < end_pfn) 1724 return stable_node; 1725 } 1726 return NULL; 1727} 1728 1729static int ksm_memory_callback(struct notifier_block *self, 1730 unsigned long action, void *arg) 1731{ 1732 struct memory_notify *mn = arg; 1733 struct stable_node *stable_node; 1734 1735 switch (action) { 1736 case MEM_GOING_OFFLINE: 1737 /* 1738 * Keep it very simple for now: just lock out ksmd and 1739 * MADV_UNMERGEABLE while any memory is going offline. 1740 * mutex_lock_nested() is necessary because lockdep was alarmed 1741 * that here we take ksm_thread_mutex inside notifier chain 1742 * mutex, and later take notifier chain mutex inside 1743 * ksm_thread_mutex to unlock it. But that's safe because both 1744 * are inside mem_hotplug_mutex. 1745 */ 1746 mutex_lock_nested(&ksm_thread_mutex, SINGLE_DEPTH_NESTING); 1747 break; 1748 1749 case MEM_OFFLINE: 1750 /* 1751 * Most of the work is done by page migration; but there might 1752 * be a few stable_nodes left over, still pointing to struct 1753 * pages which have been offlined: prune those from the tree. 1754 */ 1755 while ((stable_node = ksm_check_stable_tree(mn->start_pfn, 1756 mn->start_pfn + mn->nr_pages)) != NULL) 1757 remove_node_from_stable_tree(stable_node); 1758 /* fallthrough */ 1759 1760 case MEM_CANCEL_OFFLINE: 1761 mutex_unlock(&ksm_thread_mutex); 1762 break; 1763 } 1764 return NOTIFY_OK; 1765} 1766#endif /* CONFIG_MEMORY_HOTREMOVE */ 1767 1768#ifdef CONFIG_SYSFS 1769/* 1770 * This all compiles without CONFIG_SYSFS, but is a waste of space. 1771 */ 1772 1773#define KSM_ATTR_RO(_name) \ 1774 static struct kobj_attribute _name##_attr = __ATTR_RO(_name) 1775#define KSM_ATTR(_name) \ 1776 static struct kobj_attribute _name##_attr = \ 1777 __ATTR(_name, 0644, _name##_show, _name##_store) 1778 1779static ssize_t sleep_millisecs_show(struct kobject *kobj, 1780 struct kobj_attribute *attr, char *buf) 1781{ 1782 return sprintf(buf, "%u\n", ksm_thread_sleep_millisecs); 1783} 1784 1785static ssize_t sleep_millisecs_store(struct kobject *kobj, 1786 struct kobj_attribute *attr, 1787 const char *buf, size_t count) 1788{ 1789 unsigned long msecs; 1790 int err; 1791 1792 err = strict_strtoul(buf, 10, &msecs); 1793 if (err || msecs > UINT_MAX) 1794 return -EINVAL; 1795 1796 ksm_thread_sleep_millisecs = msecs; 1797 1798 return count; 1799} 1800KSM_ATTR(sleep_millisecs); 1801 1802static ssize_t pages_to_scan_show(struct kobject *kobj, 1803 struct kobj_attribute *attr, char *buf) 1804{ 1805 return sprintf(buf, "%u\n", ksm_thread_pages_to_scan); 1806} 1807 1808static ssize_t pages_to_scan_store(struct kobject *kobj, 1809 struct kobj_attribute *attr, 1810 const char *buf, size_t count) 1811{ 1812 int err; 1813 unsigned long nr_pages; 1814 1815 err = strict_strtoul(buf, 10, &nr_pages); 1816 if (err || nr_pages > UINT_MAX) 1817 return -EINVAL; 1818 1819 ksm_thread_pages_to_scan = nr_pages; 1820 1821 return count; 1822} 1823KSM_ATTR(pages_to_scan); 1824 1825static ssize_t run_show(struct kobject *kobj, struct kobj_attribute *attr, 1826 char *buf) 1827{ 1828 return sprintf(buf, "%u\n", ksm_run); 1829} 1830 1831static ssize_t run_store(struct kobject *kobj, struct kobj_attribute *attr, 1832 const char *buf, size_t count) 1833{ 1834 int err; 1835 unsigned long flags; 1836 1837 err = strict_strtoul(buf, 10, &flags); 1838 if (err || flags > UINT_MAX) 1839 return -EINVAL; 1840 if (flags > KSM_RUN_UNMERGE) 1841 return -EINVAL; 1842 1843 /* 1844 * KSM_RUN_MERGE sets ksmd running, and 0 stops it running. 1845 * KSM_RUN_UNMERGE stops it running and unmerges all rmap_items, 1846 * breaking COW to free the pages_shared (but leaves mm_slots 1847 * on the list for when ksmd may be set running again). 1848 */ 1849 1850 mutex_lock(&ksm_thread_mutex); 1851 if (ksm_run != flags) { 1852 ksm_run = flags; 1853 if (flags & KSM_RUN_UNMERGE) { 1854 current->flags |= PF_OOM_ORIGIN; 1855 err = unmerge_and_remove_all_rmap_items(); 1856 current->flags &= ~PF_OOM_ORIGIN; 1857 if (err) { 1858 ksm_run = KSM_RUN_STOP; 1859 count = err; 1860 } 1861 } 1862 } 1863 mutex_unlock(&ksm_thread_mutex); 1864 1865 if (flags & KSM_RUN_MERGE) 1866 wake_up_interruptible(&ksm_thread_wait); 1867 1868 return count; 1869} 1870KSM_ATTR(run); 1871 1872static ssize_t pages_shared_show(struct kobject *kobj, 1873 struct kobj_attribute *attr, char *buf) 1874{ 1875 return sprintf(buf, "%lu\n", ksm_pages_shared); 1876} 1877KSM_ATTR_RO(pages_shared); 1878 1879static ssize_t pages_sharing_show(struct kobject *kobj, 1880 struct kobj_attribute *attr, char *buf) 1881{ 1882 return sprintf(buf, "%lu\n", ksm_pages_sharing); 1883} 1884KSM_ATTR_RO(pages_sharing); 1885 1886static ssize_t pages_unshared_show(struct kobject *kobj, 1887 struct kobj_attribute *attr, char *buf) 1888{ 1889 return sprintf(buf, "%lu\n", ksm_pages_unshared); 1890} 1891KSM_ATTR_RO(pages_unshared); 1892 1893static ssize_t pages_volatile_show(struct kobject *kobj, 1894 struct kobj_attribute *attr, char *buf) 1895{ 1896 long ksm_pages_volatile; 1897 1898 ksm_pages_volatile = ksm_rmap_items - ksm_pages_shared 1899 - ksm_pages_sharing - ksm_pages_unshared; 1900 /* 1901 * It was not worth any locking to calculate that statistic, 1902 * but it might therefore sometimes be negative: conceal that. 1903 */ 1904 if (ksm_pages_volatile < 0) 1905 ksm_pages_volatile = 0; 1906 return sprintf(buf, "%ld\n", ksm_pages_volatile); 1907} 1908KSM_ATTR_RO(pages_volatile); 1909 1910static ssize_t full_scans_show(struct kobject *kobj, 1911 struct kobj_attribute *attr, char *buf) 1912{ 1913 return sprintf(buf, "%lu\n", ksm_scan.seqnr); 1914} 1915KSM_ATTR_RO(full_scans); 1916 1917static struct attribute *ksm_attrs[] = { 1918 &sleep_millisecs_attr.attr, 1919 &pages_to_scan_attr.attr, 1920 &run_attr.attr, 1921 &pages_shared_attr.attr, 1922 &pages_sharing_attr.attr, 1923 &pages_unshared_attr.attr, 1924 &pages_volatile_attr.attr, 1925 &full_scans_attr.attr, 1926 NULL, 1927}; 1928 1929static struct attribute_group ksm_attr_group = { 1930 .attrs = ksm_attrs, 1931 .name = "ksm", 1932}; 1933#endif /* CONFIG_SYSFS */ 1934 1935static int __init ksm_init(void) 1936{ 1937 struct task_struct *ksm_thread; 1938 int err; 1939 1940 err = ksm_slab_init(); 1941 if (err) 1942 goto out; 1943 1944 ksm_thread = kthread_run(ksm_scan_thread, NULL, "ksmd"); 1945 if (IS_ERR(ksm_thread)) { 1946 printk(KERN_ERR "ksm: creating kthread failed\n"); 1947 err = PTR_ERR(ksm_thread); 1948 goto out_free; 1949 } 1950 1951#ifdef CONFIG_SYSFS 1952 err = sysfs_create_group(mm_kobj, &ksm_attr_group); 1953 if (err) { 1954 printk(KERN_ERR "ksm: register sysfs failed\n"); 1955 kthread_stop(ksm_thread); 1956 goto out_free; 1957 } 1958#else 1959 ksm_run = KSM_RUN_MERGE; /* no way for user to start it */ 1960 1961#endif /* CONFIG_SYSFS */ 1962 1963#ifdef CONFIG_MEMORY_HOTREMOVE 1964 /* 1965 * Choose a high priority since the callback takes ksm_thread_mutex: 1966 * later callbacks could only be taking locks which nest within that. 1967 */ 1968 hotplug_memory_notifier(ksm_memory_callback, 100); 1969#endif 1970 return 0; 1971 1972out_free: 1973 ksm_slab_free(); 1974out: 1975 return err; 1976} 1977module_init(ksm_init) 1978