ksm.c 87.1 KB
Newer Older
1
/*
2 3 4 5 6
 * Memory merging support.
 *
 * This code enables dynamic sharing of identical pages found in different
 * memory areas, even if they are not shared by fork()
 *
7
 * Copyright (C) 2008-2009 Red Hat, Inc.
8 9 10 11
 * Authors:
 *	Izik Eidus
 *	Andrea Arcangeli
 *	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 19
#include <linux/mm.h>
#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 25 26 27 28 29 30 31 32 33
#include <linux/rwsem.h>
#include <linux/pagemap.h>
#include <linux/rmap.h>
#include <linux/spinlock.h>
#include <linux/jhash.h>
#include <linux/delay.h>
#include <linux/kthread.h>
#include <linux/wait.h>
#include <linux/slab.h>
#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

Hugh Dickins's avatar
Hugh Dickins committed
46 47 48 49 50 51 52 53
#ifdef CONFIG_NUMA
#define NUMA(x)		(x)
#define DO_NUMA(x)	do { (x); } while (0)
#else
#define NUMA(x)		(0)
#define DO_NUMA(x)	do { } while (0)
#endif

54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
/*
 * A few notes about the KSM scanning process,
 * to make it easier to understand the data structures below:
 *
 * In order to reduce excessive scanning, KSM sorts the memory pages by their
 * contents into a data structure that holds pointers to the pages' locations.
 *
 * Since the contents of the pages may change at any moment, KSM cannot just
 * insert the pages into a normal sorted tree and expect it to find anything.
 * Therefore KSM uses two data structures - the stable and the unstable tree.
 *
 * The stable tree holds pointers to all the merged pages (ksm pages), sorted
 * by their contents.  Because each such page is write-protected, searching on
 * this tree is fully assured to be working (except when pages are unmapped),
 * and therefore this tree is called the stable tree.
 *
 * In addition to the stable tree, KSM uses a second data structure called the
 * unstable tree: this tree holds pointers to pages which have been found to
 * be "unchanged for a period of time".  The unstable tree sorts these pages
 * by their contents, but since they are not write-protected, KSM cannot rely
 * upon the unstable tree to work correctly - the unstable tree is liable to
 * be corrupted as its contents are modified, and so it is called unstable.
 *
 * KSM solves this problem by several techniques:
 *
 * 1) The unstable tree is flushed every time KSM completes scanning all
 *    memory areas, and then the tree is rebuilt again from the beginning.
 * 2) KSM will only insert into the unstable tree, pages whose hash value
 *    has not changed since the previous scan of all memory areas.
 * 3) The unstable tree is a RedBlack Tree - so its balancing is based on the
 *    colors of the nodes and not on their contents, assuring that even when
 *    the tree gets "corrupted" it won't get out of balance, so scanning time
 *    remains the same (also, searching and inserting nodes in an rbtree uses
 *    the same algorithm, so we have no overhead when we flush and rebuild).
 * 4) KSM never flushes the stable tree, which means that even if it were to
 *    take 10 attempts to find a page in the unstable tree, once it is found,
 *    it is secured in the stable tree.  (When we scan a new page, we first
 *    compare it against the stable tree, and then against the unstable tree.)
Hugh Dickins's avatar
Hugh Dickins committed
92 93 94
 *
 * If the merge_across_nodes tunable is unset, then KSM maintains multiple
 * stable trees and multiple unstable trees: one of each for each NUMA node.
95 96 97 98 99 100
 */

/**
 * struct mm_slot - ksm information per mm that is being scanned
 * @link: link to the mm_slots hash list
 * @mm_list: link into the mm_slots list, rooted in ksm_mm_head
101
 * @rmap_list: head for this mm_slot's singly-linked list of rmap_items
102 103 104 105 106
 * @mm: the mm that this information is valid for
 */
struct mm_slot {
	struct hlist_node link;
	struct list_head mm_list;
107
	struct rmap_item *rmap_list;
108 109 110 111 112 113 114
	struct mm_struct *mm;
};

/**
 * struct ksm_scan - cursor for scanning
 * @mm_slot: the current mm_slot we are scanning
 * @address: the next address inside that to be scanned
115
 * @rmap_list: link to the next rmap to be scanned in the rmap_list
116 117 118 119 120 121 122
 * @seqnr: count of completed full scans (needed when removing unstable node)
 *
 * There is only the one ksm_scan instance of this cursor structure.
 */
struct ksm_scan {
	struct mm_slot *mm_slot;
	unsigned long address;
123
	struct rmap_item **rmap_list;
124 125 126
	unsigned long seqnr;
};

Hugh Dickins's avatar
Hugh Dickins committed
127 128 129
/**
 * struct stable_node - node of the stable rbtree
 * @node: rb node of this ksm page in the stable tree
130
 * @head: (overlaying parent) &migrate_nodes indicates temporarily on that list
131
 * @hlist_dup: linked into the stable_node->hlist with a stable_node chain
132
 * @list: linked into migrate_nodes, pending placement in the proper node tree
Hugh Dickins's avatar
Hugh Dickins committed
133
 * @hlist: hlist head of rmap_items using this ksm page
134
 * @kpfn: page frame number of this ksm page (perhaps temporarily on wrong nid)
135 136
 * @chain_prune_time: time of the last full garbage collection
 * @rmap_hlist_len: number of rmap_item entries in hlist or STABLE_NODE_CHAIN
137
 * @nid: NUMA node id of stable tree in which linked (may not match kpfn)
Hugh Dickins's avatar
Hugh Dickins committed
138 139
 */
struct stable_node {
140 141 142 143
	union {
		struct rb_node node;	/* when node of stable tree */
		struct {		/* when listed for migration */
			struct list_head *head;
144 145 146 147
			struct {
				struct hlist_node hlist_dup;
				struct list_head list;
			};
148 149
		};
	};
Hugh Dickins's avatar
Hugh Dickins committed
150
	struct hlist_head hlist;
151 152 153 154 155 156 157 158 159 160 161
	union {
		unsigned long kpfn;
		unsigned long chain_prune_time;
	};
	/*
	 * STABLE_NODE_CHAIN can be any negative number in
	 * rmap_hlist_len negative range, but better not -1 to be able
	 * to reliably detect underflows.
	 */
#define STABLE_NODE_CHAIN -1024
	int rmap_hlist_len;
162 163 164
#ifdef CONFIG_NUMA
	int nid;
#endif
Hugh Dickins's avatar
Hugh Dickins committed
165 166
};

167 168
/**
 * struct rmap_item - reverse mapping item for virtual addresses
169
 * @rmap_list: next rmap_item in mm_slot's singly-linked rmap_list
170
 * @anon_vma: pointer to anon_vma for this mm,address, when in stable tree
171
 * @nid: NUMA node id of unstable tree in which linked (may not match page)
172 173 174
 * @mm: the memory structure this rmap_item is pointing into
 * @address: the virtual address this rmap_item tracks (+ flags in low bits)
 * @oldchecksum: previous checksum of the page at that virtual address
Hugh Dickins's avatar
Hugh Dickins committed
175 176 177
 * @node: rb node of this rmap_item in the unstable tree
 * @head: pointer to stable_node heading this list in the stable tree
 * @hlist: link into hlist of rmap_items hanging off that stable_node
178 179
 */
struct rmap_item {
180
	struct rmap_item *rmap_list;
181 182 183 184 185 186
	union {
		struct anon_vma *anon_vma;	/* when stable */
#ifdef CONFIG_NUMA
		int nid;		/* when node of unstable tree */
#endif
	};
187 188
	struct mm_struct *mm;
	unsigned long address;		/* + low bits used for flags below */
Hugh Dickins's avatar
Hugh Dickins committed
189
	unsigned int oldchecksum;	/* when unstable */
190
	union {
Hugh Dickins's avatar
Hugh Dickins committed
191 192 193 194 195
		struct rb_node node;	/* when node of unstable tree */
		struct {		/* when listed from stable tree */
			struct stable_node *head;
			struct hlist_node hlist;
		};
196 197 198 199
	};
};

#define SEQNR_MASK	0x0ff	/* low bits of unstable tree seqnr */
Hugh Dickins's avatar
Hugh Dickins committed
200 201
#define UNSTABLE_FLAG	0x100	/* is a node of the unstable tree */
#define STABLE_FLAG	0x200	/* is listed from the stable tree */
202 203

/* The stable and unstable tree heads */
204 205 206 207
static struct rb_root one_stable_tree[1] = { RB_ROOT };
static struct rb_root one_unstable_tree[1] = { RB_ROOT };
static struct rb_root *root_stable_tree = one_stable_tree;
static struct rb_root *root_unstable_tree = one_unstable_tree;
208

209 210
/* Recently migrated nodes of stable tree, pending proper placement */
static LIST_HEAD(migrate_nodes);
211
#define STABLE_NODE_DUP_HEAD ((struct list_head *)&migrate_nodes.prev)
212

213 214
#define MM_SLOTS_HASH_BITS 10
static DEFINE_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_BITS);
215 216 217 218 219 220 221 222 223

static struct mm_slot ksm_mm_head = {
	.mm_list = LIST_HEAD_INIT(ksm_mm_head.mm_list),
};
static struct ksm_scan ksm_scan = {
	.mm_slot = &ksm_mm_head,
};

static struct kmem_cache *rmap_item_cache;
Hugh Dickins's avatar
Hugh Dickins committed
224
static struct kmem_cache *stable_node_cache;
225 226 227
static struct kmem_cache *mm_slot_cache;

/* The number of nodes in the stable tree */
228
static unsigned long ksm_pages_shared;
229

230
/* The number of page slots additionally sharing those nodes */
231
static unsigned long ksm_pages_sharing;
232

233 234 235 236 237 238
/* The number of nodes in the unstable tree */
static unsigned long ksm_pages_unshared;

/* The number of rmap_items in use: to calculate pages_volatile */
static unsigned long ksm_rmap_items;

239 240 241 242 243 244 245 246 247 248 249 250
/* The number of stable_node chains */
static unsigned long ksm_stable_node_chains;

/* The number of stable_node dups linked to the stable_node chains */
static unsigned long ksm_stable_node_dups;

/* Delay in pruning stale stable_node_dups in the stable_node_chains */
static int ksm_stable_node_chains_prune_millisecs = 2000;

/* Maximum number of page slots sharing a stable node */
static int ksm_max_page_sharing = 256;

251
/* Number of pages ksmd should scan in one batch */
252
static unsigned int ksm_thread_pages_to_scan = 100;
253 254

/* Milliseconds ksmd should sleep between batches */
Hugh Dickins's avatar
Hugh Dickins committed
255
static unsigned int ksm_thread_sleep_millisecs = 20;
256

257 258 259 260 261 262
/* Checksum of an empty (zeroed) page */
static unsigned int zero_checksum __read_mostly;

/* Whether to merge empty (zeroed) pages with actual zero pages */
static bool ksm_use_zero_pages __read_mostly;

Hugh Dickins's avatar
Hugh Dickins committed
263
#ifdef CONFIG_NUMA
264 265
/* Zeroed when merging across nodes is not allowed */
static unsigned int ksm_merge_across_nodes = 1;
266
static int ksm_nr_node_ids = 1;
Hugh Dickins's avatar
Hugh Dickins committed
267 268
#else
#define ksm_merge_across_nodes	1U
269
#define ksm_nr_node_ids		1
Hugh Dickins's avatar
Hugh Dickins committed
270
#endif
271

272 273 274
#define KSM_RUN_STOP	0
#define KSM_RUN_MERGE	1
#define KSM_RUN_UNMERGE	2
275 276 277
#define KSM_RUN_OFFLINE	4
static unsigned long ksm_run = KSM_RUN_STOP;
static void wait_while_offlining(void);
278 279 280 281 282 283 284 285 286 287 288 289 290 291 292

static DECLARE_WAIT_QUEUE_HEAD(ksm_thread_wait);
static DEFINE_MUTEX(ksm_thread_mutex);
static DEFINE_SPINLOCK(ksm_mmlist_lock);

#define KSM_KMEM_CACHE(__struct, __flags) kmem_cache_create("ksm_"#__struct,\
		sizeof(struct __struct), __alignof__(struct __struct),\
		(__flags), NULL)

static int __init ksm_slab_init(void)
{
	rmap_item_cache = KSM_KMEM_CACHE(rmap_item, 0);
	if (!rmap_item_cache)
		goto out;

Hugh Dickins's avatar
Hugh Dickins committed
293 294 295 296
	stable_node_cache = KSM_KMEM_CACHE(stable_node, 0);
	if (!stable_node_cache)
		goto out_free1;

297 298
	mm_slot_cache = KSM_KMEM_CACHE(mm_slot, 0);
	if (!mm_slot_cache)
Hugh Dickins's avatar
Hugh Dickins committed
299
		goto out_free2;
300 301 302

	return 0;

Hugh Dickins's avatar
Hugh Dickins committed
303 304 305
out_free2:
	kmem_cache_destroy(stable_node_cache);
out_free1:
306 307 308 309 310 311 312 313
	kmem_cache_destroy(rmap_item_cache);
out:
	return -ENOMEM;
}

static void __init ksm_slab_free(void)
{
	kmem_cache_destroy(mm_slot_cache);
Hugh Dickins's avatar
Hugh Dickins committed
314
	kmem_cache_destroy(stable_node_cache);
315 316 317 318
	kmem_cache_destroy(rmap_item_cache);
	mm_slot_cache = NULL;
}

319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340
static __always_inline bool is_stable_node_chain(struct stable_node *chain)
{
	return chain->rmap_hlist_len == STABLE_NODE_CHAIN;
}

static __always_inline bool is_stable_node_dup(struct stable_node *dup)
{
	return dup->head == STABLE_NODE_DUP_HEAD;
}

static inline void stable_node_chain_add_dup(struct stable_node *dup,
					     struct stable_node *chain)
{
	VM_BUG_ON(is_stable_node_dup(dup));
	dup->head = STABLE_NODE_DUP_HEAD;
	VM_BUG_ON(!is_stable_node_chain(chain));
	hlist_add_head(&dup->hlist_dup, &chain->hlist);
	ksm_stable_node_dups++;
}

static inline void __stable_node_dup_del(struct stable_node *dup)
{
341
	VM_BUG_ON(!is_stable_node_dup(dup));
342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357
	hlist_del(&dup->hlist_dup);
	ksm_stable_node_dups--;
}

static inline void stable_node_dup_del(struct stable_node *dup)
{
	VM_BUG_ON(is_stable_node_chain(dup));
	if (is_stable_node_dup(dup))
		__stable_node_dup_del(dup);
	else
		rb_erase(&dup->node, root_stable_tree + NUMA(dup->nid));
#ifdef CONFIG_DEBUG_VM
	dup->head = NULL;
#endif
}

358 359
static inline struct rmap_item *alloc_rmap_item(void)
{
360 361
	struct rmap_item *rmap_item;

362 363
	rmap_item = kmem_cache_zalloc(rmap_item_cache, GFP_KERNEL |
						__GFP_NORETRY | __GFP_NOWARN);
364 365 366
	if (rmap_item)
		ksm_rmap_items++;
	return rmap_item;
367 368 369 370
}

static inline void free_rmap_item(struct rmap_item *rmap_item)
{
371
	ksm_rmap_items--;
372 373 374 375
	rmap_item->mm = NULL;	/* debug safety */
	kmem_cache_free(rmap_item_cache, rmap_item);
}

Hugh Dickins's avatar
Hugh Dickins committed
376 377
static inline struct stable_node *alloc_stable_node(void)
{
378 379 380 381 382 383
	/*
	 * The allocation can take too long with GFP_KERNEL when memory is under
	 * pressure, which may lead to hung task warnings.  Adding __GFP_HIGH
	 * grants access to memory reserves, helping to avoid this problem.
	 */
	return kmem_cache_alloc(stable_node_cache, GFP_KERNEL | __GFP_HIGH);
Hugh Dickins's avatar
Hugh Dickins committed
384 385 386 387
}

static inline void free_stable_node(struct stable_node *stable_node)
{
388 389
	VM_BUG_ON(stable_node->rmap_hlist_len &&
		  !is_stable_node_chain(stable_node));
Hugh Dickins's avatar
Hugh Dickins committed
390 391 392
	kmem_cache_free(stable_node_cache, stable_node);
}

393 394 395 396 397 398 399 400 401 402 403 404 405 406
static inline struct mm_slot *alloc_mm_slot(void)
{
	if (!mm_slot_cache)	/* initialization failed */
		return NULL;
	return kmem_cache_zalloc(mm_slot_cache, GFP_KERNEL);
}

static inline void free_mm_slot(struct mm_slot *mm_slot)
{
	kmem_cache_free(mm_slot_cache, mm_slot);
}

static struct mm_slot *get_mm_slot(struct mm_struct *mm)
{
407 408
	struct mm_slot *slot;

409
	hash_for_each_possible(mm_slots_hash, slot, link, (unsigned long)mm)
410 411
		if (slot->mm == mm)
			return slot;
412 413 414 415 416 417 418 419

	return NULL;
}

static void insert_to_mm_slots_hash(struct mm_struct *mm,
				    struct mm_slot *mm_slot)
{
	mm_slot->mm = mm;
420
	hash_add(mm_slots_hash, &mm_slot->link, (unsigned long)mm);
421 422
}

423 424 425 426 427 428 429 430 431 432 433 434 435
/*
 * ksmd, and unmerge_and_remove_all_rmap_items(), must not touch an mm's
 * page tables after it has passed through ksm_exit() - which, if necessary,
 * takes mmap_sem briefly to serialize against them.  ksm_exit() does not set
 * a special flag: they can just back out as soon as mm_users goes to zero.
 * ksm_test_exit() is used throughout to make this test for exit: in some
 * places for correctness, in some places just to avoid unnecessary work.
 */
static inline bool ksm_test_exit(struct mm_struct *mm)
{
	return atomic_read(&mm->mm_users) == 0;
}

436 437 438
/*
 * We use break_ksm to break COW on a ksm page: it's a stripped down
 *
439
 *	if (get_user_pages(addr, 1, 1, 1, &page, NULL) == 1)
440 441 442 443 444 445
 *		put_page(page);
 *
 * but taking great care only to touch a ksm page, in a VM_MERGEABLE vma,
 * in case the application has unmapped and remapped mm,addr meanwhile.
 * Could a ksm page appear anywhere else?  Actually yes, in a VM_PFNMAP
 * mmap of /dev/mem or /dev/kmem, where we would not want to touch it.
446 447 448 449
 *
 * FAULT_FLAG/FOLL_REMOTE are because we do this outside the context
 * of the process that owns 'vma'.  We also do not want to enforce
 * protection keys here anyway.
450
 */
451
static int break_ksm(struct vm_area_struct *vma, unsigned long addr)
452 453
{
	struct page *page;
454
	int ret = 0;
455 456 457

	do {
		cond_resched();
458 459
		page = follow_page(vma, addr,
				FOLL_GET | FOLL_MIGRATION | FOLL_REMOTE);
460
		if (IS_ERR_OR_NULL(page))
461 462
			break;
		if (PageKsm(page))
463 464
			ret = handle_mm_fault(vma, addr,
					FAULT_FLAG_WRITE | FAULT_FLAG_REMOTE);
465 466 467
		else
			ret = VM_FAULT_WRITE;
		put_page(page);
468
	} while (!(ret & (VM_FAULT_WRITE | VM_FAULT_SIGBUS | VM_FAULT_SIGSEGV | VM_FAULT_OOM)));
469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497
	/*
	 * We must loop because handle_mm_fault() may back out if there's
	 * any difficulty e.g. if pte accessed bit gets updated concurrently.
	 *
	 * VM_FAULT_WRITE is what we have been hoping for: it indicates that
	 * COW has been broken, even if the vma does not permit VM_WRITE;
	 * but note that a concurrent fault might break PageKsm for us.
	 *
	 * VM_FAULT_SIGBUS could occur if we race with truncation of the
	 * backing file, which also invalidates anonymous pages: that's
	 * okay, that truncation will have unmapped the PageKsm for us.
	 *
	 * VM_FAULT_OOM: at the time of writing (late July 2009), setting
	 * aside mem_cgroup limits, VM_FAULT_OOM would only be set if the
	 * current task has TIF_MEMDIE set, and will be OOM killed on return
	 * to user; and ksmd, having no mm, would never be chosen for that.
	 *
	 * But if the mm is in a limited mem_cgroup, then the fault may fail
	 * with VM_FAULT_OOM even if the current task is not TIF_MEMDIE; and
	 * even ksmd can fail in this way - though it's usually breaking ksm
	 * just to undo a merge it made a moment before, so unlikely to oom.
	 *
	 * That's a pity: we might therefore have more kernel pages allocated
	 * than we're counting as nodes in the stable tree; but ksm_do_scan
	 * will retry to break_cow on each pass, so should recover the page
	 * in due course.  The important thing is to not let VM_MERGEABLE
	 * be cleared while any such pages might remain in the area.
	 */
	return (ret & VM_FAULT_OOM) ? -ENOMEM : 0;
498 499
}

500 501 502 503 504 505 506 507 508 509 510 511 512 513
static struct vm_area_struct *find_mergeable_vma(struct mm_struct *mm,
		unsigned long addr)
{
	struct vm_area_struct *vma;
	if (ksm_test_exit(mm))
		return NULL;
	vma = find_vma(mm, addr);
	if (!vma || vma->vm_start > addr)
		return NULL;
	if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)
		return NULL;
	return vma;
}

514
static void break_cow(struct rmap_item *rmap_item)
515
{
516 517
	struct mm_struct *mm = rmap_item->mm;
	unsigned long addr = rmap_item->address;
518 519
	struct vm_area_struct *vma;

520 521 522 523
	/*
	 * It is not an accident that whenever we want to break COW
	 * to undo, we also need to drop a reference to the anon_vma.
	 */
524
	put_anon_vma(rmap_item->anon_vma);
525

Hugh Dickins's avatar
Hugh Dickins committed
526
	down_read(&mm->mmap_sem);
527 528 529
	vma = find_mergeable_vma(mm, addr);
	if (vma)
		break_ksm(vma, addr);
530 531 532 533 534 535 536 537 538 539 540
	up_read(&mm->mmap_sem);
}

static struct page *get_mergeable_page(struct rmap_item *rmap_item)
{
	struct mm_struct *mm = rmap_item->mm;
	unsigned long addr = rmap_item->address;
	struct vm_area_struct *vma;
	struct page *page;

	down_read(&mm->mmap_sem);
541 542
	vma = find_mergeable_vma(mm, addr);
	if (!vma)
543 544 545
		goto out;

	page = follow_page(vma, addr, FOLL_GET);
546
	if (IS_ERR_OR_NULL(page))
547
		goto out;
548
	if (PageAnon(page)) {
549 550 551 552
		flush_anon_page(vma, page, addr);
		flush_dcache_page(page);
	} else {
		put_page(page);
553 554
out:
		page = NULL;
555 556 557 558 559
	}
	up_read(&mm->mmap_sem);
	return page;
}

560 561 562 563 564 565 566 567
/*
 * This helper is used for getting right index into array of tree roots.
 * When merge_across_nodes knob is set to 1, there are only two rb-trees for
 * stable and unstable pages from all nodes with roots in index 0. Otherwise,
 * every node has its own stable and unstable tree.
 */
static inline int get_kpfn_nid(unsigned long kpfn)
{
568
	return ksm_merge_across_nodes ? 0 : NUMA(pfn_to_nid(kpfn));
569 570
}

571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611
static struct stable_node *alloc_stable_node_chain(struct stable_node *dup,
						   struct rb_root *root)
{
	struct stable_node *chain = alloc_stable_node();
	VM_BUG_ON(is_stable_node_chain(dup));
	if (likely(chain)) {
		INIT_HLIST_HEAD(&chain->hlist);
		chain->chain_prune_time = jiffies;
		chain->rmap_hlist_len = STABLE_NODE_CHAIN;
#if defined (CONFIG_DEBUG_VM) && defined(CONFIG_NUMA)
		chain->nid = -1; /* debug */
#endif
		ksm_stable_node_chains++;

		/*
		 * Put the stable node chain in the first dimension of
		 * the stable tree and at the same time remove the old
		 * stable node.
		 */
		rb_replace_node(&dup->node, &chain->node, root);

		/*
		 * Move the old stable node to the second dimension
		 * queued in the hlist_dup. The invariant is that all
		 * dup stable_nodes in the chain->hlist point to pages
		 * that are wrprotected and have the exact same
		 * content.
		 */
		stable_node_chain_add_dup(dup, chain);
	}
	return chain;
}

static inline void free_stable_node_chain(struct stable_node *chain,
					  struct rb_root *root)
{
	rb_erase(&chain->node, root);
	free_stable_node(chain);
	ksm_stable_node_chains--;
}

612 613 614 615
static void remove_node_from_stable_tree(struct stable_node *stable_node)
{
	struct rmap_item *rmap_item;

616 617 618
	/* check it's not STABLE_NODE_CHAIN or negative */
	BUG_ON(stable_node->rmap_hlist_len < 0);

619
	hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) {
620 621 622 623
		if (rmap_item->hlist.next)
			ksm_pages_sharing--;
		else
			ksm_pages_shared--;
624 625
		VM_BUG_ON(stable_node->rmap_hlist_len <= 0);
		stable_node->rmap_hlist_len--;
626
		put_anon_vma(rmap_item->anon_vma);
627 628 629 630
		rmap_item->address &= PAGE_MASK;
		cond_resched();
	}

631 632 633 634 635 636 637 638 639 640 641 642
	/*
	 * We need the second aligned pointer of the migrate_nodes
	 * list_head to stay clear from the rb_parent_color union
	 * (aligned and different than any node) and also different
	 * from &migrate_nodes. This will verify that future list.h changes
	 * don't break STABLE_NODE_DUP_HEAD.
	 */
#if GCC_VERSION >= 40903 /* only recent gcc can handle it */
	BUILD_BUG_ON(STABLE_NODE_DUP_HEAD <= &migrate_nodes);
	BUILD_BUG_ON(STABLE_NODE_DUP_HEAD >= &migrate_nodes + 1);
#endif

643 644 645
	if (stable_node->head == &migrate_nodes)
		list_del(&stable_node->list);
	else
646
		stable_node_dup_del(stable_node);
647 648 649 650 651 652 653 654 655
	free_stable_node(stable_node);
}

/*
 * get_ksm_page: checks if the page indicated by the stable node
 * is still its ksm page, despite having held no reference to it.
 * In which case we can trust the content of the page, and it
 * returns the gotten page; but if the page has now been zapped,
 * remove the stale node from the stable tree and return NULL.
656
 * But beware, the stable node's page might be being migrated.
657 658 659 660 661 662 663 664 665 666 667 668
 *
 * You would expect the stable_node to hold a reference to the ksm page.
 * But if it increments the page's count, swapping out has to wait for
 * ksmd to come around again before it can free the page, which may take
 * seconds or even minutes: much too unresponsive.  So instead we use a
 * "keyhole reference": access to the ksm page from the stable node peeps
 * out through its keyhole to see if that page still holds the right key,
 * pointing back to this stable node.  This relies on freeing a PageAnon
 * page to reset its page->mapping to NULL, and relies on no other use of
 * a page to put something that might look like our key in page->mapping.
 * is on its way to being freed; but it is an anomaly to bear in mind.
 */
Hugh Dickins's avatar
Hugh Dickins committed
669
static struct page *get_ksm_page(struct stable_node *stable_node, bool lock_it)
670 671 672
{
	struct page *page;
	void *expected_mapping;
673
	unsigned long kpfn;
674

675 676
	expected_mapping = (void *)((unsigned long)stable_node |
					PAGE_MAPPING_KSM);
677
again:
678
	kpfn = READ_ONCE(stable_node->kpfn); /* Address dependency. */
679
	page = pfn_to_page(kpfn);
680
	if (READ_ONCE(page->mapping) != expected_mapping)
681
		goto stale;
682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705

	/*
	 * We cannot do anything with the page while its refcount is 0.
	 * Usually 0 means free, or tail of a higher-order page: in which
	 * case this node is no longer referenced, and should be freed;
	 * however, it might mean that the page is under page_freeze_refs().
	 * The __remove_mapping() case is easy, again the node is now stale;
	 * but if page is swapcache in migrate_page_move_mapping(), it might
	 * still be our page, in which case it's essential to keep the node.
	 */
	while (!get_page_unless_zero(page)) {
		/*
		 * Another check for page->mapping != expected_mapping would
		 * work here too.  We have chosen the !PageSwapCache test to
		 * optimize the common case, when the page is or is about to
		 * be freed: PageSwapCache is cleared (under spin_lock_irq)
		 * in the freeze_refs section of __remove_mapping(); but Anon
		 * page->mapping reset to NULL later, in free_pages_prepare().
		 */
		if (!PageSwapCache(page))
			goto stale;
		cpu_relax();
	}

706
	if (READ_ONCE(page->mapping) != expected_mapping) {
707 708 709
		put_page(page);
		goto stale;
	}
710

Hugh Dickins's avatar
Hugh Dickins committed
711
	if (lock_it) {
Hugh Dickins's avatar
Hugh Dickins committed
712
		lock_page(page);
713
		if (READ_ONCE(page->mapping) != expected_mapping) {
Hugh Dickins's avatar
Hugh Dickins committed
714 715 716 717 718
			unlock_page(page);
			put_page(page);
			goto stale;
		}
	}
719
	return page;
720

721
stale:
722 723 724 725 726 727 728
	/*
	 * We come here from above when page->mapping or !PageSwapCache
	 * suggests that the node is stale; but it might be under migration.
	 * We need smp_rmb(), matching the smp_wmb() in ksm_migrate_page(),
	 * before checking whether node->kpfn has been changed.
	 */
	smp_rmb();
729
	if (READ_ONCE(stable_node->kpfn) != kpfn)
730
		goto again;
731 732 733 734
	remove_node_from_stable_tree(stable_node);
	return NULL;
}

735 736 737 738 739 740
/*
 * Removing rmap_item from stable or unstable tree.
 * This function will clean the information from the stable/unstable tree.
 */
static void remove_rmap_item_from_tree(struct rmap_item *rmap_item)
{
Hugh Dickins's avatar
Hugh Dickins committed
741 742
	if (rmap_item->address & STABLE_FLAG) {
		struct stable_node *stable_node;
743
		struct page *page;
744

Hugh Dickins's avatar
Hugh Dickins committed
745
		stable_node = rmap_item->head;
Hugh Dickins's avatar
Hugh Dickins committed
746
		page = get_ksm_page(stable_node, true);
747 748
		if (!page)
			goto out;
749

Hugh Dickins's avatar
Hugh Dickins committed
750
		hlist_del(&rmap_item->hlist);
751 752
		unlock_page(page);
		put_page(page);
753

754
		if (!hlist_empty(&stable_node->hlist))
755 756
			ksm_pages_sharing--;
		else
Hugh Dickins's avatar
Hugh Dickins committed
757
			ksm_pages_shared--;
758 759
		VM_BUG_ON(stable_node->rmap_hlist_len <= 0);
		stable_node->rmap_hlist_len--;
760

761
		put_anon_vma(rmap_item->anon_vma);
762
		rmap_item->address &= PAGE_MASK;
763

Hugh Dickins's avatar
Hugh Dickins committed
764
	} else if (rmap_item->address & UNSTABLE_FLAG) {
765 766
		unsigned char age;
		/*
Hugh Dickins's avatar
Hugh Dickins committed
767
		 * Usually ksmd can and must skip the rb_erase, because
768
		 * root_unstable_tree was already reset to RB_ROOT.
Hugh Dickins's avatar
Hugh Dickins committed
769 770 771
		 * But be careful when an mm is exiting: do the rb_erase
		 * if this rmap_item was inserted by this scan, rather
		 * than left over from before.
772 773
		 */
		age = (unsigned char)(ksm_scan.seqnr - rmap_item->address);
774
		BUG_ON(age > 1);
775
		if (!age)
776
			rb_erase(&rmap_item->node,
777
				 root_unstable_tree + NUMA(rmap_item->nid));
778
		ksm_pages_unshared--;
779
		rmap_item->address &= PAGE_MASK;
780
	}
781
out:
782 783 784 785
	cond_resched();		/* we're called from many long loops */
}

static void remove_trailing_rmap_items(struct mm_slot *mm_slot,
786
				       struct rmap_item **rmap_list)
787
{
788 789 790
	while (*rmap_list) {
		struct rmap_item *rmap_item = *rmap_list;
		*rmap_list = rmap_item->rmap_list;
791 792 793 794 795 796
		remove_rmap_item_from_tree(rmap_item);
		free_rmap_item(rmap_item);
	}
}

/*
Hugh Dickins's avatar
Hugh Dickins committed
797
 * Though it's very tempting to unmerge rmap_items from stable tree rather
798 799 800 801 802
 * than check every pte of a given vma, the locking doesn't quite work for
 * that - an rmap_item is assigned to the stable tree after inserting ksm
 * page and upping mmap_sem.  Nor does it fit with the way we skip dup'ing
 * rmap_items from parent to child at fork time (so as not to waste time
 * if exit comes before the next scan reaches it).
Hugh Dickins's avatar
Hugh Dickins committed
803 804 805 806 807
 *
 * Similarly, although we'd like to remove rmap_items (so updating counts
 * and freeing memory) when unmerging an area, it's easier to leave that
 * to the next pass of ksmd - consider, for example, how ksmd might be
 * in cmp_and_merge_page on one of the rmap_items we would be removing.
808
 */
809 810
static int unmerge_ksm_pages(struct vm_area_struct *vma,
			     unsigned long start, unsigned long end)
811 812
{
	unsigned long addr;
813
	int err = 0;
814

815
	for (addr = start; addr < end && !err; addr += PAGE_SIZE) {
Hugh Dickins's avatar
Hugh Dickins committed
816 817
		if (ksm_test_exit(vma->vm_mm))
			break;
818 819 820 821 822 823
		if (signal_pending(current))
			err = -ERESTARTSYS;
		else
			err = break_ksm(vma, addr);
	}
	return err;
824 825
}

Hugh Dickins's avatar
Hugh Dickins committed
826 827 828 829
#ifdef CONFIG_SYSFS
/*
 * Only called through the sysfs control interface:
 */
830 831 832 833 834 835 836 837 838 839 840 841 842
static int remove_stable_node(struct stable_node *stable_node)
{
	struct page *page;
	int err;

	page = get_ksm_page(stable_node, true);
	if (!page) {
		/*
		 * get_ksm_page did remove_node_from_stable_tree itself.
		 */
		return 0;
	}

Hugh Dickins's avatar
Hugh Dickins committed
843 844 845 846 847
	if (WARN_ON_ONCE(page_mapped(page))) {
		/*
		 * This should not happen: but if it does, just refuse to let
		 * merge_across_nodes be switched - there is no need to panic.
		 */
848
		err = -EBUSY;
Hugh Dickins's avatar
Hugh Dickins committed
849
	} else {
850
		/*
Hugh Dickins's avatar
Hugh Dickins committed
851 852 853
		 * The stable node did not yet appear stale to get_ksm_page(),
		 * since that allows for an unmapped ksm page to be recognized
		 * right up until it is freed; but the node is safe to remove.
854 855 856 857 858 859 860 861 862 863 864 865 866 867
		 * This page might be in a pagevec waiting to be freed,
		 * or it might be PageSwapCache (perhaps under writeback),
		 * or it might have been removed from swapcache a moment ago.
		 */
		set_page_stable_node(page, NULL);
		remove_node_from_stable_tree(stable_node);
		err = 0;
	}

	unlock_page(page);
	put_page(page);
	return err;
}

868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892
static int remove_stable_node_chain(struct stable_node *stable_node,
				    struct rb_root *root)
{
	struct stable_node *dup;
	struct hlist_node *hlist_safe;

	if (!is_stable_node_chain(stable_node)) {
		VM_BUG_ON(is_stable_node_dup(stable_node));
		if (remove_stable_node(stable_node))
			return true;
		else
			return false;
	}

	hlist_for_each_entry_safe(dup, hlist_safe,
				  &stable_node->hlist, hlist_dup) {
		VM_BUG_ON(!is_stable_node_dup(dup));
		if (remove_stable_node(dup))
			return true;
	}
	BUG_ON(!hlist_empty(&stable_node->hlist));
	free_stable_node_chain(stable_node, root);
	return false;
}

893 894
static int remove_all_stable_nodes(void)
{
895
	struct stable_node *stable_node, *next;
896 897 898
	int nid;
	int err = 0;

899
	for (nid = 0; nid < ksm_nr_node_ids; nid++) {
900 901 902
		while (root_stable_tree[nid].rb_node) {
			stable_node = rb_entry(root_stable_tree[nid].rb_node,
						struct stable_node, node);
903 904
			if (remove_stable_node_chain(stable_node,
						     root_stable_tree + nid)) {
905 906 907 908 909 910
				err = -EBUSY;
				break;	/* proceed to next nid */
			}
			cond_resched();
		}
	}
911
	list_for_each_entry_safe(stable_node, next, &migrate_nodes, list) {
912 913 914 915
		if (remove_stable_node(stable_node))
			err = -EBUSY;
		cond_resched();
	}
916 917 918
	return err;
}

919
static int unmerge_and_remove_all_rmap_items(void)
920 921 922 923
{
	struct mm_slot *mm_slot;
	struct mm_struct *mm;
	struct vm_area_struct *vma;
924 925 926
	int err = 0;

	spin_lock(&ksm_mmlist_lock);
Hugh Dickins's avatar
Hugh Dickins committed
927
	ksm_scan.mm_slot = list_entry(ksm_mm_head.mm_list.next,
928 929
						struct mm_slot, mm_list);
	spin_unlock(&ksm_mmlist_lock);
930

Hugh Dickins's avatar
Hugh Dickins committed
931 932
	for (mm_slot = ksm_scan.mm_slot;
			mm_slot != &ksm_mm_head; mm_slot = ksm_scan.mm_slot) {
933 934 935
		mm = mm_slot->mm;
		down_read(&mm->mmap_sem);
		for (vma = mm->mmap; vma; vma = vma->vm_next) {
Hugh Dickins's avatar
Hugh Dickins committed
936 937
			if (ksm_test_exit(mm))
				break;
938 939
			if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)
				continue;
940 941
			err = unmerge_ksm_pages(vma,
						vma->vm_start, vma->vm_end);
Hugh Dickins's avatar
Hugh Dickins committed
942 943
			if (err)
				goto error;
944
		}
Hugh Dickins's avatar
Hugh Dickins committed
945

946
		remove_trailing_rmap_items(mm_slot, &mm_slot->rmap_list);
947
		up_read(&mm->mmap_sem);
948 949

		spin_lock(&ksm_mmlist_lock);
Hugh Dickins's avatar
Hugh Dickins committed
950
		ksm_scan.mm_slot = list_entry(mm_slot->mm_list.next,
951
						struct mm_slot, mm_list);
Hugh Dickins's avatar
Hugh Dickins committed
952
		if (ksm_test_exit(mm)) {
953
			hash_del(&mm_slot->link);
Hugh Dickins's avatar
Hugh Dickins committed
954 955 956 957 958 959
			list_del(&mm_slot->mm_list);
			spin_unlock(&ksm_mmlist_lock);

			free_mm_slot(mm_slot);
			clear_bit(MMF_VM_MERGEABLE, &mm->flags);
			mmdrop(mm);
960
		} else
Hugh Dickins's avatar
Hugh Dickins committed
961
			spin_unlock(&ksm_mmlist_lock);
962 963
	}

964 965
	/* Clean up stable nodes, but don't worry if some are still busy */
	remove_all_stable_nodes();
966
	ksm_scan.seqnr = 0;
Hugh Dickins's avatar
Hugh Dickins committed
967 968 969 970
	return 0;

error:
	up_read(&mm->mmap_sem);
971
	spin_lock(&ksm_mmlist_lock);
972
	ksm_scan.mm_slot = &ksm_mm_head;
973
	spin_unlock(&ksm_mmlist_lock);
974
	return err;
975
}
Hugh Dickins's avatar
Hugh Dickins committed
976
#endif /* CONFIG_SYSFS */
977 978 979 980

static u32 calc_checksum(struct page *page)
{
	u32 checksum;
981
	void *addr = kmap_atomic(page);
982
	checksum = jhash2(addr, PAGE_SIZE / 4, 17);
983
	kunmap_atomic(addr);
984 985 986 987 988 989 990 991
	return checksum;
}

static int memcmp_pages(struct page *page1, struct page *page2)
{
	char *addr1, *addr2;
	int ret;

992 993
	addr1 = kmap_atomic(page1);
	addr2 = kmap_atomic(page2);
994
	ret = memcmp(addr1, addr2, PAGE_SIZE);
995 996
	kunmap_atomic(addr2);
	kunmap_atomic(addr1);
997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008
	return ret;
}

static inline int pages_identical(struct page *page1, struct page *page2)
{
	return !memcmp_pages(page1, page2);
}

static int write_protect_page(struct vm_area_struct *vma, struct page *page,
			      pte_t *orig_pte)
{
	struct mm_struct *mm = vma->vm_mm;
1009 1010 1011 1012
	struct page_vma_mapped_walk pvmw = {
		.page = page,
		.vma = vma,
	};
1013 1014
	int swapped;
	int err = -EFAULT;
1015 1016
	unsigned long mmun_start;	/* For mmu_notifiers */
	unsigned long mmun_end;		/* For mmu_notifiers */
1017

1018 1019
	pvmw.address = page_address_in_vma(page, vma);
	if (pvmw.address == -EFAULT)
1020 1021
		goto out;

Andrea Arcangeli's avatar
Andrea Arcangeli committed
1022
	BUG_ON(PageTransCompound(page));
1023

1024 1025
	mmun_start = pvmw.address;
	mmun_end   = pvmw.address + PAGE_SIZE;
1026 1027
	mmu_notifier_invalidate_range_start(mm, mmun_start, mmun_end);

1028
	if (!page_vma_mapped_walk(&pvmw))
1029
		goto out_mn;
1030 1031
	if (WARN_ONCE(!pvmw.pte, "Unexpected PMD mapping?"))
		goto out_unlock;
1032

1033
	if (pte_write(*pvmw.pte) || pte_dirty(*pvmw.pte) ||
1034 1035
	    (pte_protnone(*pvmw.pte) && pte_savedwrite(*pvmw.pte)) ||
						mm_tlb_flush_pending(mm)) {
1036 1037 1038
		pte_t entry;

		swapped = PageSwapCache(page);
1039
		flush_cache_page(vma, pvmw.address, page_to_pfn(page));
1040
		/*
1041
		 * Ok this is tricky, when get_user_pages_fast() run it doesn't
1042 1043 1044 1045 1046 1047
		 * take any lock, therefore the check that we are going to make
		 * with the pagecount against the mapcount is racey and
		 * O_DIRECT can happen right after the check.
		 * So we clear the pte and flush the tlb before the check
		 * this assure us that no O_DIRECT can happen after the check
		 * or in the middle of the check.
1048 1049 1050 1051 1052
		 *
		 * No need to notify as we are downgrading page table to read
		 * only not changing it to point to a new page.
		 *
		 * See Documentation/vm/mmu_notifier.txt
1053
		 */
1054
		entry = ptep_clear_flush(vma, pvmw.address, pvmw.pte);
1055 1056 1057 1058
		/*
		 * Check that no O_DIRECT or similar I/O is in progress on the
		 * page
		 */
1059
		if (page_mapcount(page) + 1 + swapped != page_count(page)) {
1060
			set_pte_at(mm, pvmw.address, pvmw.pte, entry);
1061 1062
			goto out_unlock;
		}
1063 1064
		if (pte_dirty(entry))
			set_page_dirty(page);
1065 1066 1067 1068 1069

		if (pte_protnone(entry))
			entry = pte_mkclean(pte_clear_savedwrite(entry));
		else
			entry = pte_mkclean(pte_wrprotect(entry));
1070
		set_pte_at_notify(mm, pvmw.address, pvmw.pte, entry);
1071
	}
1072
	*orig_pte = *pvmw.pte;
1073 1074 1075
	err = 0;

out_unlock:
1076
	page_vma_mapped_walk_done(&pvmw);
1077 1078
out_mn:
	mmu_notifier_invalidate_range_end(mm, mmun_start, mmun_end);
1079 1080 1081 1082 1083 1084
out:
	return err;
}

/**
 * replace_page - replace page in vma by new ksm page
1085 1086 1087
 * @vma:      vma that holds the pte pointing to page
 * @page:     the page we are replacing by kpage
 * @kpage:    the ksm page we replace page by
1088 1089 1090 1091
 * @orig_pte: the original value of the pte
 *
 * Returns 0 on success, -EFAULT on failure.
 */
1092 1093
static int replace_page(struct vm_area_struct *vma, struct page *page,
			struct page *kpage, pte_t orig_pte)
1094 1095 1096 1097
{
	struct mm_struct *mm = vma->vm_mm;
	pmd_t *pmd;
	pte_t *ptep;
1098
	pte_t newpte;
1099 1100 1101
	spinlock_t *ptl;
	unsigned long addr;
	int err = -EFAULT;
1102 1103
	unsigned long mmun_start;	/* For mmu_notifiers */
	unsigned long mmun_end;		/* For mmu_notifiers */
1104

1105
	addr = page_address_in_vma(page, vma);
1106 1107 1108
	if (addr == -EFAULT)
		goto out;

Bob Liu's avatar
Bob Liu committed
1109 1110
	pmd = mm_find_pmd(mm, addr);
	if (!pmd)
1111 1112
		goto out;

1113 1114 1115 1116
	mmun_start = addr;
	mmun_end   = addr + PAGE_SIZE;
	mmu_notifier_invalidate_range_start(mm, mmun_start, mmun_end);

1117 1118 1119
	ptep = pte_offset_map_lock(mm, pmd, addr, &ptl);
	if (!pte_same(*ptep, orig_pte)) {
		pte_unmap_unlock(ptep, ptl);
1120
		goto out_mn;
1121 1122
	}

1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133
	/*
	 * No need to check ksm_use_zero_pages here: we can only have a
	 * zero_page here if ksm_use_zero_pages was enabled alreaady.
	 */
	if (!is_zero_pfn(page_to_pfn(kpage))) {
		get_page(kpage);
		page_add_anon_rmap(kpage, vma, addr, false);
		newpte = mk_pte(kpage, vma->vm_page_prot);
	} else {
		newpte = pte_mkspecial(pfn_pte(page_to_pfn(kpage),
					       vma->vm_page_prot));
1134 1135 1136 1137 1138 1139 1140
		/*
		 * We're replacing an anonymous page with a zero page, which is
		 * not anonymous. We need to do proper accounting otherwise we
		 * will get wrong values in /proc, and a BUG message in dmesg
		 * when tearing down the mm.
		 */
		dec_mm_counter(mm, MM_ANONPAGES);
1141
	}
1142 1143

	flush_cache_page(vma, addr, pte_pfn(*ptep));
1144 1145 1146 1147 1148 1149 1150
	/*
	 * No need to notify as we are replacing a read only page with another
	 * read only page with the same content.
	 *
	 * See Documentation/vm/mmu_notifier.txt
	 */
	ptep_clear_flush(vma, addr, ptep);
1151
	set_pte_at_notify(mm, addr, ptep, newpte);
1152

1153
	page_remove_rmap(page, false);
1154 1155
	if (!page_mapped(page))
		try_to_free_swap(page);
1156
	put_page(page);
1157 1158 1159

	pte_unmap_unlock(ptep, ptl);
	err = 0;
1160 1161
out_mn:
	mmu_notifier_invalidate_range_end(mm, mmun_start, mmun_end);
1162 1163 1164 1165 1166 1167
out:
	return err;
}

/*
 * try_to_merge_one_page - take two pages and merge them into one
1168 1169
 * @vma: the vma that holds the pte pointing to page
 * @page: the PageAnon page that we want to replace with kpage
1170 1171
 * @kpage: the PageKsm page that we want to map instead of page,
 *         or NULL the first time when we want to use page as kpage.
1172 1173 1174 1175
 *
 * This function returns 0 if the pages were merged, -EFAULT otherwise.
 */
static int try_to_merge_one_page(struct vm_area_struct *vma,
1176
				 struct page *page, struct page *kpage)
1177 1178 1179 1180
{
	pte_t orig_pte = __pte(0);
	int err = -EFAULT;

1181 1182 1183
	if (page == kpage)			/* ksm page forked */
		return 0;

1184
	if (!PageAnon(page))
1185 1186 1187 1188 1189 1190 1191 1192 1193
		goto out;

	/*
	 * We need the page lock to read a stable PageSwapCache in
	 * write_protect_page().  We use trylock_page() instead of
	 * lock_page() because we don't want to wait here - we
	 * prefer to continue scanning and merging different pages,
	 * then come back to this page when it is unlocked.
	 */
1194
	if (!trylock_page(page))
1195
		goto out;
1196 1197

	if (PageTransCompound(page)) {
1198
		if (split_huge_page(page))
1199 1200 1201
			goto out_unlock;
	}

1202 1203 1204 1205 1206 1207
	/*
	 * If this anonymous page is mapped only here, its pte may need
	 * to be write-protected.  If it's mapped elsewhere, all of its
	 * ptes are necessarily already write-protected.  But in either
	 * case, we need to lock and check page_count is not raised.
	 */
1208 1209 1210 1211 1212 1213 1214 1215 1216
	if (write_protect_page(vma, page, &orig_pte) == 0) {
		if (!kpage) {
			/*
			 * While we hold page lock, upgrade page from
			 * PageAnon+anon_vma to PageKsm+NULL stable_node:
			 * stable_tree_insert() will update stable_node.
			 */
			set_page_stable_node(page, NULL);
			mark_page_accessed(page);
1217 1218 1219 1220 1221 1222
			/*
			 * Page reclaim just frees a clean page with no dirty
			 * ptes: make sure that the ksm page would be swapped.
			 */
			if (!PageDirty(page))
				SetPageDirty(page);
1223 1224 1225 1226
			err = 0;
		} else if (pages_identical(page, kpage))
			err = replace_page(vma, page, kpage, orig_pte);
	}
1227

1228
	if ((vma->vm_flags & VM_LOCKED) && kpage && !err) {
1229
		munlock_vma_page(page);
1230 1231 1232 1233 1234 1235 1236
		if (!PageMlocked(kpage)) {
			unlock_page(page);
			lock_page(kpage);
			mlock_vma_page(kpage);
			page = kpage;		/* for final unlock */
		}
	}
1237

1238
out_unlock:
1239
	unlock_page(page);
1240 1241 1242 1243
out:
	return err;
}

Hugh Dickins's avatar
Hugh Dickins committed
1244 1245 1246
/*
 * try_to_merge_with_ksm_page - like try_to_merge_two_pages,
 * but no new kernel page is allocated: kpage must already be a ksm page.
1247 1248
 *
 * This function returns 0 if the pages were merged, -EFAULT otherwise.
Hugh Dickins's avatar
Hugh Dickins committed
1249
 */
1250 1251
static int try_to_merge_with_ksm_page(struct rmap_item *rmap_item,
				      struct page *page, struct page *kpage)
Hugh Dickins's avatar
Hugh Dickins committed
1252
{
1253
	struct mm_struct *mm = rmap_item->mm;
Hugh Dickins's avatar
Hugh Dickins committed
1254 1255 1256
	struct vm_area_struct *vma;
	int err = -EFAULT;

1257
	down_read(&mm->mmap_sem);
1258 1259
	vma = find_mergeable_vma(mm, rmap_item->address);
	if (!vma)
Hugh Dickins's avatar
Hugh Dickins committed
1260 1261
		goto out;

1262
	err = try_to_merge_one_page(vma, page, kpage);
1263 1264 1265
	if (err)
		goto out;

1266 1267 1268
	/* Unstable nid is in union with stable anon_vma: remove first */
	remove_rmap_item_from_tree(rmap_item);

1269
	/* Must get reference to anon_vma while still holding mmap_sem */
1270 1271
	rmap_item->anon_vma = vma->anon_vma;
	get_anon_vma(vma->anon_vma);
Hugh Dickins's avatar
Hugh Dickins committed
1272
out:
1273
	up_read(&mm->mmap_sem);
Hugh Dickins's avatar
Hugh Dickins committed
1274 1275 1276
	return err;
}

1277 1278 1279 1280
/*
 * try_to_merge_two_pages - take two identical pages and prepare them
 * to be merged into one page.
 *
1281 1282
 * This function returns the kpage if we successfully merged two identical
 * pages into one ksm page, NULL otherwise.
1283
 *
1284
 * Note that this function upgrades page to ksm page: if one of the pages
1285 1286
 * is already a ksm page, try_to_merge_with_ksm_page should be used.
 */
1287 1288 1289 1290
static struct page *try_to_merge_two_pages(struct rmap_item *rmap_item,
					   struct page *page,
					   struct rmap_item *tree_rmap_item,
					   struct page *tree_page)
1291
{
1292
	int err;
1293

1294
	err = try_to_merge_with_ksm_page(rmap_item, page, NULL);
1295
	if (!err) {
1296
		err = try_to_merge_with_ksm_page(tree_rmap_item,
1297
							tree_page, page);
1298
		/*
Hugh Dickins's avatar
Hugh Dickins committed
1299 1300
		 * If that fails, we have a ksm page with only one pte
		 * pointing to it: so break it.
1301
		 */
1302
		if (err)
1303
			break_cow(rmap_item);
1304
	}
1305
	return err ? NULL : page;
1306 1307
}

1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327
static __always_inline
bool __is_page_sharing_candidate(struct stable_node *stable_node, int offset)
{
	VM_BUG_ON(stable_node->rmap_hlist_len < 0);
	/*
	 * Check that at least one mapping still exists, otherwise
	 * there's no much point to merge and share with this
	 * stable_node, as the underlying tree_page of the other
	 * sharer is going to be freed soon.
	 */
	return stable_node->rmap_hlist_len &&
		stable_node->rmap_hlist_len + offset < ksm_max_page_sharing;
}

static __always_inline
bool is_page_sharing_candidate(struct stable_node *stable_node)
{
	return __is_page_sharing_candidate(stable_node, 0);
}

1328 1329 1330 1331
static struct page *stable_node_dup(struct stable_node **_stable_node_dup,
				    struct stable_node **_stable_node,
				    struct rb_root *root,
				    bool prune_stale_stable_nodes)
1332
{
1333
	struct stable_node *dup, *found = NULL, *stable_node = *_stable_node;
1334
	struct hlist_node *hlist_safe;
1335
	struct page *_tree_page, *tree_page = NULL;
1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367
	int nr = 0;
	int found_rmap_hlist_len;

	if (!prune_stale_stable_nodes ||
	    time_before(jiffies, stable_node->chain_prune_time +
			msecs_to_jiffies(
				ksm_stable_node_chains_prune_millisecs)))
		prune_stale_stable_nodes = false;
	else
		stable_node->chain_prune_time = jiffies;

	hlist_for_each_entry_safe(dup, hlist_safe,
				  &stable_node->hlist, hlist_dup) {
		cond_resched();
		/*
		 * We must walk all stable_node_dup to prune the stale
		 * stable nodes during lookup.
		 *
		 * get_ksm_page can drop the nodes from the
		 * stable_node->hlist if they point to freed pages
		 * (that's why we do a _safe walk). The "dup"
		 * stable_node parameter itself will be freed from
		 * under us if it returns NULL.
		 */
		_tree_page = get_ksm_page(dup, false);
		if (!_tree_page)
			continue;
		nr += 1;
		if (is_page_sharing_candidate(dup)) {
			if (!found ||
			    dup->rmap_hlist_len > found_rmap_hlist_len) {
				if (found)
1368
					put_page(tree_page);
1369 1370
				found = dup;
				found_rmap_hlist_len = found->rmap_hlist_len;
1371
				tree_page = _tree_page;
1372

1373
				/* skip put_page for found dup */
1374 1375 1376 1377 1378 1379 1380 1381
				if (!prune_stale_stable_nodes)
					break;
				continue;
			}
		}
		put_page(_tree_page);
	}

1382 1383 1384 1385 1386 1387 1388 1389
	if (found) {
		/*
		 * nr is counting all dups in the chain only if
		 * prune_stale_stable_nodes is true, otherwise we may
		 * break the loop at nr == 1 even if there are
		 * multiple entries.
		 */
		if (prune_stale_stable_nodes && nr == 1) {
1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406
			/*
			 * If there's not just one entry it would
			 * corrupt memory, better BUG_ON. In KSM
			 * context with no lock held it's not even
			 * fatal.
			 */
			BUG_ON(stable_node->hlist.first->next);

			/*
			 * There's just one entry and it is below the
			 * deduplication limit so drop the chain.
			 */
			rb_replace_node(&stable_node->node, &found->node,
					root);
			free_stable_node(stable_node);
			ksm_stable_node_chains--;
			ksm_stable_node_dups--;
1407
			/*
1408 1409 1410
			 * NOTE: the caller depends on the stable_node
			 * to be equal to stable_node_dup if the chain
			 * was collapsed.
1411
			 */
1412 1413 1414 1415 1416 1417 1418 1419
			*_stable_node = found;
			/*
			 * Just for robustneess as stable_node is
			 * otherwise left as a stable pointer, the
			 * compiler shall optimize it away at build
			 * time.
			 */
			stable_node = NULL;
1420 1421
		} else if (stable_node->hlist.first != &found->hlist_dup &&
			   __is_page_sharing_candidate(found, 1)) {
1422
			/*
1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435
			 * If the found stable_node dup can accept one
			 * more future merge (in addition to the one
			 * that is underway) and is not at the head of
			 * the chain, put it there so next search will
			 * be quicker in the !prune_stale_stable_nodes
			 * case.
			 *
			 * NOTE: it would be inaccurate to use nr > 1
			 * instead of checking the hlist.first pointer
			 * directly, because in the
			 * prune_stale_stable_nodes case "nr" isn't
			 * the position of the found dup in the chain,
			 * but the total number of dups in the chain.
1436 1437 1438 1439 1440 1441 1442
			 */
			hlist_del(&found->hlist_dup);
			hlist_add_head(&found->hlist_dup,
				       &stable_node->hlist);
		}
	}

1443 1444
	*_stable_node_dup = found;
	return tree_page;
1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459
}

static struct stable_node *stable_node_dup_any(struct stable_node *stable_node,
					       struct rb_root *root)
{
	if (!is_stable_node_chain(stable_node))
		return stable_node;
	if (hlist_empty(&stable_node->hlist)) {
		free_stable_node_chain(stable_node, root);
		return NULL;
	}
	return hlist_entry(stable_node->hlist.first,
			   typeof(*stable_node), hlist_dup);
}

1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477
/*
 * Like for get_ksm_page, this function can free the *_stable_node and
 * *_stable_node_dup if the returned tree_page is NULL.
 *
 * It can also free and overwrite *_stable_node with the found
 * stable_node_dup if the chain is collapsed (in which case
 * *_stable_node will be equal to *_stable_node_dup like if the chain
 * never existed). It's up to the caller to verify tree_page is not
 * NULL before dereferencing *_stable_node or *_stable_node_dup.
 *
 * *_stable_node_dup is really a second output parameter of this
 * function and will be overwritten in all cases, the caller doesn't
 * need to initialize it.
 */
static struct page *__stable_node_chain(struct stable_node **_stable_node_dup,
					struct stable_node **_stable_node,
					struct rb_root *root,
					bool prune_stale_stable_nodes)
1478
{
1479
	struct stable_node *stable_node = *_stable_node;
1480 1481
	if (!is_stable_node_chain(stable_node)) {
		if (is_page_sharing_candidate(stable_node)) {
1482 1483
			*_stable_node_dup = stable_node;
			return get_ksm_page(stable_node, false);
1484
		}
1485 1486 1487 1488 1489
		/*
		 * _stable_node_dup set to NULL means the stable_node
		 * reached the ksm_max_page_sharing limit.
		 */
		*_stable_node_dup = NULL;
1490 1491
		return NULL;
	}
1492
	return stable_node_dup(_stable_node_dup, _stable_node, root,
1493 1494 1495
			       prune_stale_stable_nodes);
}

1496 1497 1498
static __always_inline struct page *chain_prune(struct stable_node **s_n_d,
						struct stable_node **s_n,
						struct rb_root *root)
1499
{
1500
	return __stable_node_chain(s_n_d, s_n, root, true);
1501 1502
}

1503 1504 1505
static __always_inline struct page *chain(struct stable_node **s_n_d,
					  struct stable_node *s_n,
					  struct rb_root *root)
1506
{
1507 1508 1509 1510 1511 1512 1513
	struct stable_node *old_stable_node = s_n;
	struct page *tree_page;

	tree_page = __stable_node_chain(s_n_d, &s_n, root, false);
	/* not pruning dups so s_n cannot have changed */
	VM_BUG_ON(s_n != old_stable_node);
	return tree_page;
1514 1515
}

1516
/*
1517
 * stable_tree_search - search for page inside the stable tree
1518 1519