ksm.c

   1// SPDX-License-Identifier: GPL-2.0-only
   2/*
   3 * Memory merging support.
   4 *
   5 * This code enables dynamic sharing of identical pages found in different
   6 * memory areas, even if they are not shared by fork()
   7 *
   8 * Copyright (C) 2008-2009 Red Hat, Inc.
   9 * Authors:
  10 *	Izik Eidus
  11 *	Andrea Arcangeli
  12 *	Chris Wright
  13 *	Hugh Dickins
  14 */
  15
  16#include <linux/errno.h>
  17#include <linux/mm.h>
  18#include <linux/mm_inline.h>
  19#include <linux/fs.h>
  20#include <linux/mman.h>
  21#include <linux/sched.h>
  22#include <linux/sched/mm.h>
  23#include <linux/sched/cputime.h>
  24#include <linux/rwsem.h>
  25#include <linux/pagemap.h>
  26#include <linux/rmap.h>
  27#include <linux/spinlock.h>
  28#include <linux/xxhash.h>
  29#include <linux/delay.h>
  30#include <linux/kthread.h>
  31#include <linux/wait.h>
  32#include <linux/slab.h>
  33#include <linux/rbtree.h>
  34#include <linux/memory.h>
  35#include <linux/mmu_notifier.h>
  36#include <linux/swap.h>
  37#include <linux/ksm.h>
  38#include <linux/hashtable.h>
  39#include <linux/freezer.h>
  40#include <linux/oom.h>
  41#include <linux/numa.h>
  42#include <linux/pagewalk.h>
  43
  44#include <asm/tlbflush.h>
  45#include "internal.h"
  46#include "mm_slot.h"
  47
  48#define CREATE_TRACE_POINTS
  49#include <trace/events/ksm.h>
  50
  51#ifdef CONFIG_NUMA
  52#define NUMA(x)		(x)
  53#define DO_NUMA(x)	do { (x); } while (0)
  54#else
  55#define NUMA(x)		(0)
  56#define DO_NUMA(x)	do { } while (0)
  57#endif
  58
  59typedef u8 rmap_age_t;
  60
  61/**
  62 * DOC: Overview
  63 *
  64 * A few notes about the KSM scanning process,
  65 * to make it easier to understand the data structures below:
  66 *
  67 * In order to reduce excessive scanning, KSM sorts the memory pages by their
  68 * contents into a data structure that holds pointers to the pages' locations.
  69 *
  70 * Since the contents of the pages may change at any moment, KSM cannot just
  71 * insert the pages into a normal sorted tree and expect it to find anything.
  72 * Therefore KSM uses two data structures - the stable and the unstable tree.
  73 *
  74 * The stable tree holds pointers to all the merged pages (ksm pages), sorted
  75 * by their contents.  Because each such page is write-protected, searching on
  76 * this tree is fully assured to be working (except when pages are unmapped),
  77 * and therefore this tree is called the stable tree.
  78 *
  79 * The stable tree node includes information required for reverse
  80 * mapping from a KSM page to virtual addresses that map this page.
  81 *
  82 * In order to avoid large latencies of the rmap walks on KSM pages,
  83 * KSM maintains two types of nodes in the stable tree:
  84 *
  85 * * the regular nodes that keep the reverse mapping structures in a
  86 *   linked list
  87 * * the "chains" that link nodes ("dups") that represent the same
  88 *   write protected memory content, but each "dup" corresponds to a
  89 *   different KSM page copy of that content
  90 *
  91 * Internally, the regular nodes, "dups" and "chains" are represented
  92 * using the same struct ksm_stable_node structure.
  93 *
  94 * In addition to the stable tree, KSM uses a second data structure called the
  95 * unstable tree: this tree holds pointers to pages which have been found to
  96 * be "unchanged for a period of time".  The unstable tree sorts these pages
  97 * by their contents, but since they are not write-protected, KSM cannot rely
  98 * upon the unstable tree to work correctly - the unstable tree is liable to
  99 * be corrupted as its contents are modified, and so it is called unstable.
 100 *
 101 * KSM solves this problem by several techniques:
 102 *
 103 * 1) The unstable tree is flushed every time KSM completes scanning all
 104 *    memory areas, and then the tree is rebuilt again from the beginning.
 105 * 2) KSM will only insert into the unstable tree, pages whose hash value
 106 *    has not changed since the previous scan of all memory areas.
 107 * 3) The unstable tree is a RedBlack Tree - so its balancing is based on the
 108 *    colors of the nodes and not on their contents, assuring that even when
 109 *    the tree gets "corrupted" it won't get out of balance, so scanning time
 110 *    remains the same (also, searching and inserting nodes in an rbtree uses
 111 *    the same algorithm, so we have no overhead when we flush and rebuild).
 112 * 4) KSM never flushes the stable tree, which means that even if it were to
 113 *    take 10 attempts to find a page in the unstable tree, once it is found,
 114 *    it is secured in the stable tree.  (When we scan a new page, we first
 115 *    compare it against the stable tree, and then against the unstable tree.)
 116 *
 117 * If the merge_across_nodes tunable is unset, then KSM maintains multiple
 118 * stable trees and multiple unstable trees: one of each for each NUMA node.
 119 */
 120
 121/**
 122 * struct ksm_mm_slot - ksm information per mm that is being scanned
 123 * @slot: hash lookup from mm to mm_slot
 124 * @rmap_list: head for this mm_slot's singly-linked list of rmap_items
 125 */
 126struct ksm_mm_slot {
 127	struct mm_slot slot;
 128	struct ksm_rmap_item *rmap_list;
 129};
 130
 131/**
 132 * struct ksm_scan - cursor for scanning
 133 * @mm_slot: the current mm_slot we are scanning
 134 * @address: the next address inside that to be scanned
 135 * @rmap_list: link to the next rmap to be scanned in the rmap_list
 136 * @seqnr: count of completed full scans (needed when removing unstable node)
 137 *
 138 * There is only the one ksm_scan instance of this cursor structure.
 139 */
 140struct ksm_scan {
 141	struct ksm_mm_slot *mm_slot;
 142	unsigned long address;
 143	struct ksm_rmap_item **rmap_list;
 144	unsigned long seqnr;
 145};
 146
 147/**
 148 * struct ksm_stable_node - node of the stable rbtree
 149 * @node: rb node of this ksm page in the stable tree
 150 * @head: (overlaying parent) &migrate_nodes indicates temporarily on that list
 151 * @hlist_dup: linked into the stable_node->hlist with a stable_node chain
 152 * @list: linked into migrate_nodes, pending placement in the proper node tree
 153 * @hlist: hlist head of rmap_items using this ksm page
 154 * @kpfn: page frame number of this ksm page (perhaps temporarily on wrong nid)
 155 * @chain_prune_time: time of the last full garbage collection
 156 * @rmap_hlist_len: number of rmap_item entries in hlist or STABLE_NODE_CHAIN
 157 * @nid: NUMA node id of stable tree in which linked (may not match kpfn)
 158 */
 159struct ksm_stable_node {
 160	union {
 161		struct rb_node node;	/* when node of stable tree */
 162		struct {		/* when listed for migration */
 163			struct list_head *head;
 164			struct {
 165				struct hlist_node hlist_dup;
 166				struct list_head list;
 167			};
 168		};
 169	};
 170	struct hlist_head hlist;
 171	union {
 172		unsigned long kpfn;
 173		unsigned long chain_prune_time;
 174	};
 175	/*
 176	 * STABLE_NODE_CHAIN can be any negative number in
 177	 * rmap_hlist_len negative range, but better not -1 to be able
 178	 * to reliably detect underflows.
 179	 */
 180#define STABLE_NODE_CHAIN -1024
 181	int rmap_hlist_len;
 182#ifdef CONFIG_NUMA
 183	int nid;
 184#endif
 185};
 186
 187/**
 188 * struct ksm_rmap_item - reverse mapping item for virtual addresses
 189 * @rmap_list: next rmap_item in mm_slot's singly-linked rmap_list
 190 * @anon_vma: pointer to anon_vma for this mm,address, when in stable tree
 191 * @nid: NUMA node id of unstable tree in which linked (may not match page)
 192 * @mm: the memory structure this rmap_item is pointing into
 193 * @address: the virtual address this rmap_item tracks (+ flags in low bits)
 194 * @oldchecksum: previous checksum of the page at that virtual address
 195 * @node: rb node of this rmap_item in the unstable tree
 196 * @head: pointer to stable_node heading this list in the stable tree
 197 * @hlist: link into hlist of rmap_items hanging off that stable_node
 198 * @age: number of scan iterations since creation
 199 * @remaining_skips: how many scans to skip
 200 */
 201struct ksm_rmap_item {
 202	struct ksm_rmap_item *rmap_list;
 203	union {
 204		struct anon_vma *anon_vma;	/* when stable */
 205#ifdef CONFIG_NUMA
 206		int nid;		/* when node of unstable tree */
 207#endif
 208	};
 209	struct mm_struct *mm;
 210	unsigned long address;		/* + low bits used for flags below */
 211	unsigned int oldchecksum;	/* when unstable */
 212	rmap_age_t age;
 213	rmap_age_t remaining_skips;
 214	union {
 215		struct rb_node node;	/* when node of unstable tree */
 216		struct {		/* when listed from stable tree */
 217			struct ksm_stable_node *head;
 218			struct hlist_node hlist;
 219		};
 220	};
 221};
 222
 223#define SEQNR_MASK	0x0ff	/* low bits of unstable tree seqnr */
 224#define UNSTABLE_FLAG	0x100	/* is a node of the unstable tree */
 225#define STABLE_FLAG	0x200	/* is listed from the stable tree */
 226
 227/* The stable and unstable tree heads */
 228static struct rb_root one_stable_tree[1] = { RB_ROOT };
 229static struct rb_root one_unstable_tree[1] = { RB_ROOT };
 230static struct rb_root *root_stable_tree = one_stable_tree;
 231static struct rb_root *root_unstable_tree = one_unstable_tree;
 232
 233/* Recently migrated nodes of stable tree, pending proper placement */
 234static LIST_HEAD(migrate_nodes);
 235#define STABLE_NODE_DUP_HEAD ((struct list_head *)&migrate_nodes.prev)
 236
 237#define MM_SLOTS_HASH_BITS 10
 238static DEFINE_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_BITS);
 239
 240static struct ksm_mm_slot ksm_mm_head = {
 241	.slot.mm_node = LIST_HEAD_INIT(ksm_mm_head.slot.mm_node),
 242};
 243static struct ksm_scan ksm_scan = {
 244	.mm_slot = &ksm_mm_head,
 245};
 246
 247static struct kmem_cache *rmap_item_cache;
 248static struct kmem_cache *stable_node_cache;
 249static struct kmem_cache *mm_slot_cache;
 250
 251/* Default number of pages to scan per batch */
 252#define DEFAULT_PAGES_TO_SCAN 100
 253
 254/* The number of pages scanned */
 255static unsigned long ksm_pages_scanned;
 256
 257/* The number of nodes in the stable tree */
 258static unsigned long ksm_pages_shared;
 259
 260/* The number of page slots additionally sharing those nodes */
 261static unsigned long ksm_pages_sharing;
 262
 263/* The number of nodes in the unstable tree */
 264static unsigned long ksm_pages_unshared;
 265
 266/* The number of rmap_items in use: to calculate pages_volatile */
 267static unsigned long ksm_rmap_items;
 268
 269/* The number of stable_node chains */
 270static unsigned long ksm_stable_node_chains;
 271
 272/* The number of stable_node dups linked to the stable_node chains */
 273static unsigned long ksm_stable_node_dups;
 274
 275/* Delay in pruning stale stable_node_dups in the stable_node_chains */
 276static unsigned int ksm_stable_node_chains_prune_millisecs = 2000;
 277
 278/* Maximum number of page slots sharing a stable node */
 279static int ksm_max_page_sharing = 256;
 280
 281/* Number of pages ksmd should scan in one batch */
 282static unsigned int ksm_thread_pages_to_scan = DEFAULT_PAGES_TO_SCAN;
 283
 284/* Milliseconds ksmd should sleep between batches */
 285static unsigned int ksm_thread_sleep_millisecs = 20;
 286
 287/* Checksum of an empty (zeroed) page */
 288static unsigned int zero_checksum __read_mostly;
 289
 290/* Whether to merge empty (zeroed) pages with actual zero pages */
 291static bool ksm_use_zero_pages __read_mostly;
 292
 293/* Skip pages that couldn't be de-duplicated previously */
 294/* Default to true at least temporarily, for testing */
 295static bool ksm_smart_scan = true;
 296
 297/* The number of zero pages which is placed by KSM */
 298atomic_long_t ksm_zero_pages = ATOMIC_LONG_INIT(0);
 299
 300/* The number of pages that have been skipped due to "smart scanning" */
 301static unsigned long ksm_pages_skipped;
 302
 303/* Don't scan more than max pages per batch. */
 304static unsigned long ksm_advisor_max_pages_to_scan = 30000;
 305
 306/* Min CPU for scanning pages per scan */
 307#define KSM_ADVISOR_MIN_CPU 10
 308
 309/* Max CPU for scanning pages per scan */
 310static unsigned int ksm_advisor_max_cpu =  70;
 311
 312/* Target scan time in seconds to analyze all KSM candidate pages. */
 313static unsigned long ksm_advisor_target_scan_time = 200;
 314
 315/* Exponentially weighted moving average. */
 316#define EWMA_WEIGHT 30
 317
 318/**
 319 * struct advisor_ctx - metadata for KSM advisor
 320 * @start_scan: start time of the current scan
 321 * @scan_time: scan time of previous scan
 322 * @change: change in percent to pages_to_scan parameter
 323 * @cpu_time: cpu time consumed by the ksmd thread in the previous scan
 324 */
 325struct advisor_ctx {
 326	ktime_t start_scan;
 327	unsigned long scan_time;
 328	unsigned long change;
 329	unsigned long long cpu_time;
 330};
 331static struct advisor_ctx advisor_ctx;
 332
 333/* Define different advisor's */
 334enum ksm_advisor_type {
 335	KSM_ADVISOR_NONE,
 336	KSM_ADVISOR_SCAN_TIME,
 337};
 338static enum ksm_advisor_type ksm_advisor;
 339
 340#ifdef CONFIG_SYSFS
 341/*
 342 * Only called through the sysfs control interface:
 343 */
 344
 345/* At least scan this many pages per batch. */
 346static unsigned long ksm_advisor_min_pages_to_scan = 500;
 347
 348static void set_advisor_defaults(void)
 349{
 350	if (ksm_advisor == KSM_ADVISOR_NONE) {
 351		ksm_thread_pages_to_scan = DEFAULT_PAGES_TO_SCAN;
 352	} else if (ksm_advisor == KSM_ADVISOR_SCAN_TIME) {
 353		advisor_ctx = (const struct advisor_ctx){ 0 };
 354		ksm_thread_pages_to_scan = ksm_advisor_min_pages_to_scan;
 355	}
 356}
 357#endif /* CONFIG_SYSFS */
 358
 359static inline void advisor_start_scan(void)
 360{
 361	if (ksm_advisor == KSM_ADVISOR_SCAN_TIME)
 362		advisor_ctx.start_scan = ktime_get();
 363}
 364
 365/*
 366 * Use previous scan time if available, otherwise use current scan time as an
 367 * approximation for the previous scan time.
 368 */
 369static inline unsigned long prev_scan_time(struct advisor_ctx *ctx,
 370					   unsigned long scan_time)
 371{
 372	return ctx->scan_time ? ctx->scan_time : scan_time;
 373}
 374
 375/* Calculate exponential weighted moving average */
 376static unsigned long ewma(unsigned long prev, unsigned long curr)
 377{
 378	return ((100 - EWMA_WEIGHT) * prev + EWMA_WEIGHT * curr) / 100;
 379}
 380
 381/*
 382 * The scan time advisor is based on the current scan rate and the target
 383 * scan rate.
 384 *
 385 *      new_pages_to_scan = pages_to_scan * (scan_time / target_scan_time)
 386 *
 387 * To avoid perturbations it calculates a change factor of previous changes.
 388 * A new change factor is calculated for each iteration and it uses an
 389 * exponentially weighted moving average. The new pages_to_scan value is
 390 * multiplied with that change factor:
 391 *
 392 *      new_pages_to_scan *= change factor
 393 *
 394 * The new_pages_to_scan value is limited by the cpu min and max values. It
 395 * calculates the cpu percent for the last scan and calculates the new
 396 * estimated cpu percent cost for the next scan. That value is capped by the
 397 * cpu min and max setting.
 398 *
 399 * In addition the new pages_to_scan value is capped by the max and min
 400 * limits.
 401 */
 402static void scan_time_advisor(void)
 403{
 404	unsigned int cpu_percent;
 405	unsigned long cpu_time;
 406	unsigned long cpu_time_diff;
 407	unsigned long cpu_time_diff_ms;
 408	unsigned long pages;
 409	unsigned long per_page_cost;
 410	unsigned long factor;
 411	unsigned long change;
 412	unsigned long last_scan_time;
 413	unsigned long scan_time;
 414
 415	/* Convert scan time to seconds */
 416	scan_time = div_s64(ktime_ms_delta(ktime_get(), advisor_ctx.start_scan),
 417			    MSEC_PER_SEC);
 418	scan_time = scan_time ? scan_time : 1;
 419
 420	/* Calculate CPU consumption of ksmd background thread */
 421	cpu_time = task_sched_runtime(current);
 422	cpu_time_diff = cpu_time - advisor_ctx.cpu_time;
 423	cpu_time_diff_ms = cpu_time_diff / 1000 / 1000;
 424
 425	cpu_percent = (cpu_time_diff_ms * 100) / (scan_time * 1000);
 426	cpu_percent = cpu_percent ? cpu_percent : 1;
 427	last_scan_time = prev_scan_time(&advisor_ctx, scan_time);
 428
 429	/* Calculate scan time as percentage of target scan time */
 430	factor = ksm_advisor_target_scan_time * 100 / scan_time;
 431	factor = factor ? factor : 1;
 432
 433	/*
 434	 * Calculate scan time as percentage of last scan time and use
 435	 * exponentially weighted average to smooth it
 436	 */
 437	change = scan_time * 100 / last_scan_time;
 438	change = change ? change : 1;
 439	change = ewma(advisor_ctx.change, change);
 440
 441	/* Calculate new scan rate based on target scan rate. */
 442	pages = ksm_thread_pages_to_scan * 100 / factor;
 443	/* Update pages_to_scan by weighted change percentage. */
 444	pages = pages * change / 100;
 445
 446	/* Cap new pages_to_scan value */
 447	per_page_cost = ksm_thread_pages_to_scan / cpu_percent;
 448	per_page_cost = per_page_cost ? per_page_cost : 1;
 449
 450	pages = min(pages, per_page_cost * ksm_advisor_max_cpu);
 451	pages = max(pages, per_page_cost * KSM_ADVISOR_MIN_CPU);
 452	pages = min(pages, ksm_advisor_max_pages_to_scan);
 453
 454	/* Update advisor context */
 455	advisor_ctx.change = change;
 456	advisor_ctx.scan_time = scan_time;
 457	advisor_ctx.cpu_time = cpu_time;
 458
 459	ksm_thread_pages_to_scan = pages;
 460	trace_ksm_advisor(scan_time, pages, cpu_percent);
 461}
 462
 463static void advisor_stop_scan(void)
 464{
 465	if (ksm_advisor == KSM_ADVISOR_SCAN_TIME)
 466		scan_time_advisor();
 467}
 468
 469#ifdef CONFIG_NUMA
 470/* Zeroed when merging across nodes is not allowed */
 471static unsigned int ksm_merge_across_nodes = 1;
 472static int ksm_nr_node_ids = 1;
 473#else
 474#define ksm_merge_across_nodes	1U
 475#define ksm_nr_node_ids		1
 476#endif
 477
 478#define KSM_RUN_STOP	0
 479#define KSM_RUN_MERGE	1
 480#define KSM_RUN_UNMERGE	2
 481#define KSM_RUN_OFFLINE	4
 482static unsigned long ksm_run = KSM_RUN_STOP;
 483static void wait_while_offlining(void);
 484
 485static DECLARE_WAIT_QUEUE_HEAD(ksm_thread_wait);
 486static DECLARE_WAIT_QUEUE_HEAD(ksm_iter_wait);
 487static DEFINE_MUTEX(ksm_thread_mutex);
 488static DEFINE_SPINLOCK(ksm_mmlist_lock);
 489
 490static int __init ksm_slab_init(void)
 491{
 492	rmap_item_cache = KMEM_CACHE(ksm_rmap_item, 0);
 493	if (!rmap_item_cache)
 494		goto out;
 495
 496	stable_node_cache = KMEM_CACHE(ksm_stable_node, 0);
 497	if (!stable_node_cache)
 498		goto out_free1;
 499
 500	mm_slot_cache = KMEM_CACHE(ksm_mm_slot, 0);
 501	if (!mm_slot_cache)
 502		goto out_free2;
 503
 504	return 0;
 505
 506out_free2:
 507	kmem_cache_destroy(stable_node_cache);
 508out_free1:
 509	kmem_cache_destroy(rmap_item_cache);
 510out:
 511	return -ENOMEM;
 512}
 513
 514static void __init ksm_slab_free(void)
 515{
 516	kmem_cache_destroy(mm_slot_cache);
 517	kmem_cache_destroy(stable_node_cache);
 518	kmem_cache_destroy(rmap_item_cache);
 519	mm_slot_cache = NULL;
 520}
 521
 522static __always_inline bool is_stable_node_chain(struct ksm_stable_node *chain)
 523{
 524	return chain->rmap_hlist_len == STABLE_NODE_CHAIN;
 525}
 526
 527static __always_inline bool is_stable_node_dup(struct ksm_stable_node *dup)
 528{
 529	return dup->head == STABLE_NODE_DUP_HEAD;
 530}
 531
 532static inline void stable_node_chain_add_dup(struct ksm_stable_node *dup,
 533					     struct ksm_stable_node *chain)
 534{
 535	VM_BUG_ON(is_stable_node_dup(dup));
 536	dup->head = STABLE_NODE_DUP_HEAD;
 537	VM_BUG_ON(!is_stable_node_chain(chain));
 538	hlist_add_head(&dup->hlist_dup, &chain->hlist);
 539	ksm_stable_node_dups++;
 540}
 541
 542static inline void __stable_node_dup_del(struct ksm_stable_node *dup)
 543{
 544	VM_BUG_ON(!is_stable_node_dup(dup));
 545	hlist_del(&dup->hlist_dup);
 546	ksm_stable_node_dups--;
 547}
 548
 549static inline void stable_node_dup_del(struct ksm_stable_node *dup)
 550{
 551	VM_BUG_ON(is_stable_node_chain(dup));
 552	if (is_stable_node_dup(dup))
 553		__stable_node_dup_del(dup);
 554	else
 555		rb_erase(&dup->node, root_stable_tree + NUMA(dup->nid));
 556#ifdef CONFIG_DEBUG_VM
 557	dup->head = NULL;
 558#endif
 559}
 560
 561static inline struct ksm_rmap_item *alloc_rmap_item(void)
 562{
 563	struct ksm_rmap_item *rmap_item;
 564
 565	rmap_item = kmem_cache_zalloc(rmap_item_cache, GFP_KERNEL |
 566						__GFP_NORETRY | __GFP_NOWARN);
 567	if (rmap_item)
 568		ksm_rmap_items++;
 569	return rmap_item;
 570}
 571
 572static inline void free_rmap_item(struct ksm_rmap_item *rmap_item)
 573{
 574	ksm_rmap_items--;
 575	rmap_item->mm->ksm_rmap_items--;
 576	rmap_item->mm = NULL;	/* debug safety */
 577	kmem_cache_free(rmap_item_cache, rmap_item);
 578}
 579
 580static inline struct ksm_stable_node *alloc_stable_node(void)
 581{
 582	/*
 583	 * The allocation can take too long with GFP_KERNEL when memory is under
 584	 * pressure, which may lead to hung task warnings.  Adding __GFP_HIGH
 585	 * grants access to memory reserves, helping to avoid this problem.
 586	 */
 587	return kmem_cache_alloc(stable_node_cache, GFP_KERNEL | __GFP_HIGH);
 588}
 589
 590static inline void free_stable_node(struct ksm_stable_node *stable_node)
 591{
 592	VM_BUG_ON(stable_node->rmap_hlist_len &&
 593		  !is_stable_node_chain(stable_node));
 594	kmem_cache_free(stable_node_cache, stable_node);
 595}
 596
 597/*
 598 * ksmd, and unmerge_and_remove_all_rmap_items(), must not touch an mm's
 599 * page tables after it has passed through ksm_exit() - which, if necessary,
 600 * takes mmap_lock briefly to serialize against them.  ksm_exit() does not set
 601 * a special flag: they can just back out as soon as mm_users goes to zero.
 602 * ksm_test_exit() is used throughout to make this test for exit: in some
 603 * places for correctness, in some places just to avoid unnecessary work.
 604 */
 605static inline bool ksm_test_exit(struct mm_struct *mm)
 606{
 607	return atomic_read(&mm->mm_users) == 0;
 608}
 609
 610static int break_ksm_pmd_entry(pmd_t *pmdp, unsigned long addr, unsigned long end,
 611			struct mm_walk *walk)
 612{
 613	unsigned long *found_addr = (unsigned long *) walk->private;
 614	struct mm_struct *mm = walk->mm;
 615	pte_t *start_ptep, *ptep;
 616	spinlock_t *ptl;
 617	int found = 0;
 618
 619	if (ksm_test_exit(walk->mm))
 620		return 0;
 621	if (signal_pending(current))
 622		return -ERESTARTSYS;
 623
 624	start_ptep = pte_offset_map_lock(mm, pmdp, addr, &ptl);
 625	if (!start_ptep)
 626		return 0;
 627
 628	for (ptep = start_ptep; addr < end; ptep++, addr += PAGE_SIZE) {
 629		pte_t pte = ptep_get(ptep);
 630		struct folio *folio = NULL;
 631
 632		if (pte_present(pte)) {
 633			folio = vm_normal_folio(walk->vma, addr, pte);
 634		} else if (!pte_none(pte)) {
 635			const softleaf_t entry = softleaf_from_pte(pte);
 636
 637			/*
 638			 * As KSM pages remain KSM pages until freed, no need to wait
 639			 * here for migration to end.
 640			 */
 641			if (softleaf_is_migration(entry))
 642				folio = softleaf_to_folio(entry);
 643		}
 644		/* return 1 if the page is an normal ksm page or KSM-placed zero page */
 645		found = (folio && folio_test_ksm(folio)) ||
 646			(pte_present(pte) && is_ksm_zero_pte(pte));
 647		if (found) {
 648			*found_addr = addr;
 649			goto out_unlock;
 650		}
 651	}
 652out_unlock:
 653	pte_unmap_unlock(start_ptep, ptl);
 654	return found;
 655}
 656
 657static const struct mm_walk_ops break_ksm_ops = {
 658	.pmd_entry = break_ksm_pmd_entry,
 659	.walk_lock = PGWALK_RDLOCK,
 660};
 661
 662static const struct mm_walk_ops break_ksm_lock_vma_ops = {
 663	.pmd_entry = break_ksm_pmd_entry,
 664	.walk_lock = PGWALK_WRLOCK,
 665};
 666
 667/*
 668 * Though it's very tempting to unmerge rmap_items from stable tree rather
 669 * than check every pte of a given vma, the locking doesn't quite work for
 670 * that - an rmap_item is assigned to the stable tree after inserting ksm
 671 * page and upping mmap_lock.  Nor does it fit with the way we skip dup'ing
 672 * rmap_items from parent to child at fork time (so as not to waste time
 673 * if exit comes before the next scan reaches it).
 674 *
 675 * Similarly, although we'd like to remove rmap_items (so updating counts
 676 * and freeing memory) when unmerging an area, it's easier to leave that
 677 * to the next pass of ksmd - consider, for example, how ksmd might be
 678 * in cmp_and_merge_page on one of the rmap_items we would be removing.
 679 *
 680 * We use break_ksm to break COW on a ksm page by triggering unsharing,
 681 * such that the ksm page will get replaced by an exclusive anonymous page.
 682 *
 683 * We take great care only to touch a ksm page, in a VM_MERGEABLE vma,
 684 * in case the application has unmapped and remapped mm,addr meanwhile.
 685 * Could a ksm page appear anywhere else?  Actually yes, in a VM_PFNMAP
 686 * mmap of /dev/mem, where we would not want to touch it.
 687 *
 688 * FAULT_FLAG_REMOTE/FOLL_REMOTE are because we do this outside the context
 689 * of the process that owns 'vma'.  We also do not want to enforce
 690 * protection keys here anyway.
 691 */
 692static int break_ksm(struct vm_area_struct *vma, unsigned long addr,
 693		unsigned long end, bool lock_vma)
 694{
 695	vm_fault_t ret = 0;
 696	const struct mm_walk_ops *ops = lock_vma ?
 697				&break_ksm_lock_vma_ops : &break_ksm_ops;
 698
 699	do {
 700		int ksm_page;
 701
 702		cond_resched();
 703		ksm_page = walk_page_range_vma(vma, addr, end, ops, &addr);
 704		if (ksm_page <= 0)
 705			return ksm_page;
 706		ret = handle_mm_fault(vma, addr,
 707				      FAULT_FLAG_UNSHARE | FAULT_FLAG_REMOTE,
 708				      NULL);
 709	} while (!(ret & (VM_FAULT_SIGBUS | VM_FAULT_SIGSEGV | VM_FAULT_OOM)));
 710	/*
 711	 * We must loop until we no longer find a KSM page because
 712	 * handle_mm_fault() may back out if there's any difficulty e.g. if
 713	 * pte accessed bit gets updated concurrently.
 714	 *
 715	 * VM_FAULT_SIGBUS could occur if we race with truncation of the
 716	 * backing file, which also invalidates anonymous pages: that's
 717	 * okay, that truncation will have unmapped the KSM page for us.
 718	 *
 719	 * VM_FAULT_OOM: at the time of writing (late July 2009), setting
 720	 * aside mem_cgroup limits, VM_FAULT_OOM would only be set if the
 721	 * current task has TIF_MEMDIE set, and will be OOM killed on return
 722	 * to user; and ksmd, having no mm, would never be chosen for that.
 723	 *
 724	 * But if the mm is in a limited mem_cgroup, then the fault may fail
 725	 * with VM_FAULT_OOM even if the current task is not TIF_MEMDIE; and
 726	 * even ksmd can fail in this way - though it's usually breaking ksm
 727	 * just to undo a merge it made a moment before, so unlikely to oom.
 728	 *
 729	 * That's a pity: we might therefore have more kernel pages allocated
 730	 * than we're counting as nodes in the stable tree; but ksm_do_scan
 731	 * will retry to break_cow on each pass, so should recover the page
 732	 * in due course.  The important thing is to not let VM_MERGEABLE
 733	 * be cleared while any such pages might remain in the area.
 734	 */
 735	return (ret & VM_FAULT_OOM) ? -ENOMEM : 0;
 736}
 737
 738static bool ksm_compatible(const struct file *file, vm_flags_t vm_flags)
 739{
 740	if (vm_flags & (VM_SHARED  | VM_MAYSHARE | VM_SPECIAL |
 741			VM_HUGETLB | VM_DROPPABLE))
 742		return false;		/* just ignore the advice */
 743
 744	if (file_is_dax(file))
 745		return false;
 746
 747#ifdef VM_SAO
 748	if (vm_flags & VM_SAO)
 749		return false;
 750#endif
 751#ifdef VM_SPARC_ADI
 752	if (vm_flags & VM_SPARC_ADI)
 753		return false;
 754#endif
 755
 756	return true;
 757}
 758
 759static bool vma_ksm_compatible(struct vm_area_struct *vma)
 760{
 761	return ksm_compatible(vma->vm_file, vma->vm_flags);
 762}
 763
 764static struct vm_area_struct *find_mergeable_vma(struct mm_struct *mm,
 765		unsigned long addr)
 766{
 767	struct vm_area_struct *vma;
 768	if (ksm_test_exit(mm))
 769		return NULL;
 770	vma = vma_lookup(mm, addr);
 771	if (!vma || !(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)
 772		return NULL;
 773	return vma;
 774}
 775
 776static void break_cow(struct ksm_rmap_item *rmap_item)
 777{
 778	struct mm_struct *mm = rmap_item->mm;
 779	unsigned long addr = rmap_item->address;
 780	struct vm_area_struct *vma;
 781
 782	/*
 783	 * It is not an accident that whenever we want to break COW
 784	 * to undo, we also need to drop a reference to the anon_vma.
 785	 */
 786	put_anon_vma(rmap_item->anon_vma);
 787
 788	mmap_read_lock(mm);
 789	vma = find_mergeable_vma(mm, addr);
 790	if (vma)
 791		break_ksm(vma, addr, addr + PAGE_SIZE, false);
 792	mmap_read_unlock(mm);
 793}
 794
 795static struct page *get_mergeable_page(struct ksm_rmap_item *rmap_item)
 796{
 797	struct mm_struct *mm = rmap_item->mm;
 798	unsigned long addr = rmap_item->address;
 799	struct vm_area_struct *vma;
 800	struct page *page = NULL;
 801	struct folio_walk fw;
 802	struct folio *folio;
 803
 804	mmap_read_lock(mm);
 805	vma = find_mergeable_vma(mm, addr);
 806	if (!vma)
 807		goto out;
 808
 809	folio = folio_walk_start(&fw, vma, addr, 0);
 810	if (folio) {
 811		if (!folio_is_zone_device(folio) &&
 812		    folio_test_anon(folio)) {
 813			folio_get(folio);
 814			page = fw.page;
 815		}
 816		folio_walk_end(&fw, vma);
 817	}
 818out:
 819	if (page) {
 820		flush_anon_page(vma, page, addr);
 821		flush_dcache_page(page);
 822	}
 823	mmap_read_unlock(mm);
 824	return page;
 825}
 826
 827/*
 828 * This helper is used for getting right index into array of tree roots.
 829 * When merge_across_nodes knob is set to 1, there are only two rb-trees for
 830 * stable and unstable pages from all nodes with roots in index 0. Otherwise,
 831 * every node has its own stable and unstable tree.
 832 */
 833static inline int get_kpfn_nid(unsigned long kpfn)
 834{
 835	return ksm_merge_across_nodes ? 0 : NUMA(pfn_to_nid(kpfn));
 836}
 837
 838static struct ksm_stable_node *alloc_stable_node_chain(struct ksm_stable_node *dup,
 839						   struct rb_root *root)
 840{
 841	struct ksm_stable_node *chain = alloc_stable_node();
 842	VM_BUG_ON(is_stable_node_chain(dup));
 843	if (likely(chain)) {
 844		INIT_HLIST_HEAD(&chain->hlist);
 845		chain->chain_prune_time = jiffies;
 846		chain->rmap_hlist_len = STABLE_NODE_CHAIN;
 847#if defined (CONFIG_DEBUG_VM) && defined(CONFIG_NUMA)
 848		chain->nid = NUMA_NO_NODE; /* debug */
 849#endif
 850		ksm_stable_node_chains++;
 851
 852		/*
 853		 * Put the stable node chain in the first dimension of
 854		 * the stable tree and at the same time remove the old
 855		 * stable node.
 856		 */
 857		rb_replace_node(&dup->node, &chain->node, root);
 858
 859		/*
 860		 * Move the old stable node to the second dimension
 861		 * queued in the hlist_dup. The invariant is that all
 862		 * dup stable_nodes in the chain->hlist point to pages
 863		 * that are write protected and have the exact same
 864		 * content.
 865		 */
 866		stable_node_chain_add_dup(dup, chain);
 867	}
 868	return chain;
 869}
 870
 871static inline void free_stable_node_chain(struct ksm_stable_node *chain,
 872					  struct rb_root *root)
 873{
 874	rb_erase(&chain->node, root);
 875	free_stable_node(chain);
 876	ksm_stable_node_chains--;
 877}
 878
 879static void remove_node_from_stable_tree(struct ksm_stable_node *stable_node)
 880{
 881	struct ksm_rmap_item *rmap_item;
 882
 883	/* check it's not STABLE_NODE_CHAIN or negative */
 884	BUG_ON(stable_node->rmap_hlist_len < 0);
 885
 886	hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) {
 887		if (rmap_item->hlist.next) {
 888			ksm_pages_sharing--;
 889			trace_ksm_remove_rmap_item(stable_node->kpfn, rmap_item, rmap_item->mm);
 890		} else {
 891			ksm_pages_shared--;
 892		}
 893
 894		rmap_item->mm->ksm_merging_pages--;
 895
 896		VM_BUG_ON(stable_node->rmap_hlist_len <= 0);
 897		stable_node->rmap_hlist_len--;
 898		put_anon_vma(rmap_item->anon_vma);
 899		rmap_item->address &= PAGE_MASK;
 900		cond_resched();
 901	}
 902
 903	/*
 904	 * We need the second aligned pointer of the migrate_nodes
 905	 * list_head to stay clear from the rb_parent_color union
 906	 * (aligned and different than any node) and also different
 907	 * from &migrate_nodes. This will verify that future list.h changes
 908	 * don't break STABLE_NODE_DUP_HEAD. Only recent gcc can handle it.
 909	 */
 910	BUILD_BUG_ON(STABLE_NODE_DUP_HEAD <= &migrate_nodes);
 911	BUILD_BUG_ON(STABLE_NODE_DUP_HEAD >= &migrate_nodes + 1);
 912
 913	trace_ksm_remove_ksm_page(stable_node->kpfn);
 914	if (stable_node->head == &migrate_nodes)
 915		list_del(&stable_node->list);
 916	else
 917		stable_node_dup_del(stable_node);
 918	free_stable_node(stable_node);
 919}
 920
 921enum ksm_get_folio_flags {
 922	KSM_GET_FOLIO_NOLOCK,
 923	KSM_GET_FOLIO_LOCK,
 924	KSM_GET_FOLIO_TRYLOCK
 925};
 926
 927/*
 928 * ksm_get_folio: checks if the page indicated by the stable node
 929 * is still its ksm page, despite having held no reference to it.
 930 * In which case we can trust the content of the page, and it
 931 * returns the gotten page; but if the page has now been zapped,
 932 * remove the stale node from the stable tree and return NULL.
 933 * But beware, the stable node's page might be being migrated.
 934 *
 935 * You would expect the stable_node to hold a reference to the ksm page.
 936 * But if it increments the page's count, swapping out has to wait for
 937 * ksmd to come around again before it can free the page, which may take
 938 * seconds or even minutes: much too unresponsive.  So instead we use a
 939 * "keyhole reference": access to the ksm page from the stable node peeps
 940 * out through its keyhole to see if that page still holds the right key,
 941 * pointing back to this stable node.  This relies on freeing a PageAnon
 942 * page to reset its page->mapping to NULL, and relies on no other use of
 943 * a page to put something that might look like our key in page->mapping.
 944 * is on its way to being freed; but it is an anomaly to bear in mind.
 945 */
 946static struct folio *ksm_get_folio(struct ksm_stable_node *stable_node,
 947				 enum ksm_get_folio_flags flags)
 948{
 949	struct folio *folio;
 950	void *expected_mapping;
 951	unsigned long kpfn;
 952
 953	expected_mapping = (void *)((unsigned long)stable_node |
 954					FOLIO_MAPPING_KSM);
 955again:
 956	kpfn = READ_ONCE(stable_node->kpfn); /* Address dependency. */
 957	folio = pfn_folio(kpfn);
 958	if (READ_ONCE(folio->mapping) != expected_mapping)
 959		goto stale;
 960
 961	/*
 962	 * We cannot do anything with the page while its refcount is 0.
 963	 * Usually 0 means free, or tail of a higher-order page: in which
 964	 * case this node is no longer referenced, and should be freed;
 965	 * however, it might mean that the page is under page_ref_freeze().
 966	 * The __remove_mapping() case is easy, again the node is now stale;
 967	 * the same is in reuse_ksm_page() case; but if page is swapcache
 968	 * in folio_migrate_mapping(), it might still be our page,
 969	 * in which case it's essential to keep the node.
 970	 */
 971	while (!folio_try_get(folio)) {
 972		/*
 973		 * Another check for folio->mapping != expected_mapping
 974		 * would work here too.  We have chosen to test the
 975		 * swapcache flag to optimize the common case, when the
 976		 * folio is or is about to be freed: the swapcache flag
 977		 * is cleared (under spin_lock_irq) in the ref_freeze
 978		 * section of __remove_mapping(); but anon folio->mapping
 979		 * is reset to NULL later, in free_pages_prepare().
 980		 */
 981		if (!folio_test_swapcache(folio))
 982			goto stale;
 983		cpu_relax();
 984	}
 985
 986	if (READ_ONCE(folio->mapping) != expected_mapping) {
 987		folio_put(folio);
 988		goto stale;
 989	}
 990
 991	if (flags == KSM_GET_FOLIO_TRYLOCK) {
 992		if (!folio_trylock(folio)) {
 993			folio_put(folio);
 994			return ERR_PTR(-EBUSY);
 995		}
 996	} else if (flags == KSM_GET_FOLIO_LOCK)
 997		folio_lock(folio);
 998
 999	if (flags != KSM_GET_FOLIO_NOLOCK) {
1000		if (READ_ONCE(folio->mapping) != expected_mapping) {
1001			folio_unlock(folio);
1002			folio_put(folio);
1003			goto stale;
1004		}
1005	}
1006	return folio;
1007
1008stale:
1009	/*
1010	 * We come here from above when folio->mapping or the swapcache flag
1011	 * suggests that the node is stale; but it might be under migration.
1012	 * We need smp_rmb(), matching the smp_wmb() in folio_migrate_ksm(),
1013	 * before checking whether node->kpfn has been changed.
1014	 */
1015	smp_rmb();
1016	if (READ_ONCE(stable_node->kpfn) != kpfn)
1017		goto again;
1018	remove_node_from_stable_tree(stable_node);
1019	return NULL;
1020}
1021
1022/*
1023 * Removing rmap_item from stable or unstable tree.
1024 * This function will clean the information from the stable/unstable tree.
1025 */
1026static void remove_rmap_item_from_tree(struct ksm_rmap_item *rmap_item)
1027{
1028	if (rmap_item->address & STABLE_FLAG) {
1029		struct ksm_stable_node *stable_node;
1030		struct folio *folio;
1031
1032		stable_node = rmap_item->head;
1033		folio = ksm_get_folio(stable_node, KSM_GET_FOLIO_LOCK);
1034		if (!folio)
1035			goto out;
1036
1037		hlist_del(&rmap_item->hlist);
1038		folio_unlock(folio);
1039		folio_put(folio);
1040
1041		if (!hlist_empty(&stable_node->hlist))
1042			ksm_pages_sharing--;
1043		else
1044			ksm_pages_shared--;
1045
1046		rmap_item->mm->ksm_merging_pages--;
1047
1048		VM_BUG_ON(stable_node->rmap_hlist_len <= 0);
1049		stable_node->rmap_hlist_len--;
1050
1051		put_anon_vma(rmap_item->anon_vma);
1052		rmap_item->head = NULL;
1053		rmap_item->address &= PAGE_MASK;
1054
1055	} else if (rmap_item->address & UNSTABLE_FLAG) {
1056		unsigned char age;
1057		/*
1058		 * Usually ksmd can and must skip the rb_erase, because
1059		 * root_unstable_tree was already reset to RB_ROOT.
1060		 * But be careful when an mm is exiting: do the rb_erase
1061		 * if this rmap_item was inserted by this scan, rather
1062		 * than left over from before.
1063		 */
1064		age = (unsigned char)(ksm_scan.seqnr - rmap_item->address);
1065		BUG_ON(age > 1);
1066		if (!age)
1067			rb_erase(&rmap_item->node,
1068				 root_unstable_tree + NUMA(rmap_item->nid));
1069		ksm_pages_unshared--;
1070		rmap_item->address &= PAGE_MASK;
1071	}
1072out:
1073	cond_resched();		/* we're called from many long loops */
1074}
1075
1076static void remove_trailing_rmap_items(struct ksm_rmap_item **rmap_list)
1077{
1078	while (*rmap_list) {
1079		struct ksm_rmap_item *rmap_item = *rmap_list;
1080		*rmap_list = rmap_item->rmap_list;
1081		remove_rmap_item_from_tree(rmap_item);
1082		free_rmap_item(rmap_item);
1083	}
1084}
1085
1086static inline
1087struct ksm_stable_node *folio_stable_node(const struct folio *folio)
1088{
1089	return folio_test_ksm(folio) ? folio_raw_mapping(folio) : NULL;
1090}
1091
1092static inline void folio_set_stable_node(struct folio *folio,
1093					 struct ksm_stable_node *stable_node)
1094{
1095	VM_WARN_ON_FOLIO(folio_test_anon(folio) && PageAnonExclusive(&folio->page), folio);
1096	folio->mapping = (void *)((unsigned long)stable_node | FOLIO_MAPPING_KSM);
1097}
1098
1099#ifdef CONFIG_SYSFS
1100/*
1101 * Only called through the sysfs control interface:
1102 */
1103static int remove_stable_node(struct ksm_stable_node *stable_node)
1104{
1105	struct folio *folio;
1106	int err;
1107
1108	folio = ksm_get_folio(stable_node, KSM_GET_FOLIO_LOCK);
1109	if (!folio) {
1110		/*
1111		 * ksm_get_folio did remove_node_from_stable_tree itself.
1112		 */
1113		return 0;
1114	}
1115
1116	/*
1117	 * Page could be still mapped if this races with __mmput() running in
1118	 * between ksm_exit() and exit_mmap(). Just refuse to let
1119	 * merge_across_nodes/max_page_sharing be switched.
1120	 */
1121	err = -EBUSY;
1122	if (!folio_mapped(folio)) {
1123		/*
1124		 * The stable node did not yet appear stale to ksm_get_folio(),
1125		 * since that allows for an unmapped ksm folio to be recognized
1126		 * right up until it is freed; but the node is safe to remove.
1127		 * This folio might be in an LRU cache waiting to be freed,
1128		 * or it might be in the swapcache (perhaps under writeback),
1129		 * or it might have been removed from swapcache a moment ago.
1130		 */
1131		folio_set_stable_node(folio, NULL);
1132		remove_node_from_stable_tree(stable_node);
1133		err = 0;
1134	}
1135
1136	folio_unlock(folio);
1137	folio_put(folio);
1138	return err;
1139}
1140
1141static int remove_stable_node_chain(struct ksm_stable_node *stable_node,
1142				    struct rb_root *root)
1143{
1144	struct ksm_stable_node *dup;
1145	struct hlist_node *hlist_safe;
1146
1147	if (!is_stable_node_chain(stable_node)) {
1148		VM_BUG_ON(is_stable_node_dup(stable_node));
1149		if (remove_stable_node(stable_node))
1150			return true;
1151		else
1152			return false;
1153	}
1154
1155	hlist_for_each_entry_safe(dup, hlist_safe,
1156				  &stable_node->hlist, hlist_dup) {
1157		VM_BUG_ON(!is_stable_node_dup(dup));
1158		if (remove_stable_node(dup))
1159			return true;
1160	}
1161	BUG_ON(!hlist_empty(&stable_node->hlist));
1162	free_stable_node_chain(stable_node, root);
1163	return false;
1164}
1165
1166static int remove_all_stable_nodes(void)
1167{
1168	struct ksm_stable_node *stable_node, *next;
1169	int nid;
1170	int err = 0;
1171
1172	for (nid = 0; nid < ksm_nr_node_ids; nid++) {
1173		while (root_stable_tree[nid].rb_node) {
1174			stable_node = rb_entry(root_stable_tree[nid].rb_node,
1175						struct ksm_stable_node, node);
1176			if (remove_stable_node_chain(stable_node,
1177						     root_stable_tree + nid)) {
1178				err = -EBUSY;
1179				break;	/* proceed to next nid */
1180			}
1181			cond_resched();
1182		}
1183	}
1184	list_for_each_entry_safe(stable_node, next, &migrate_nodes, list) {
1185		if (remove_stable_node(stable_node))
1186			err = -EBUSY;
1187		cond_resched();
1188	}
1189	return err;
1190}
1191
1192static int unmerge_and_remove_all_rmap_items(void)
1193{
1194	struct ksm_mm_slot *mm_slot;
1195	struct mm_slot *slot;
1196	struct mm_struct *mm;
1197	struct vm_area_struct *vma;
1198	int err = 0;
1199
1200	spin_lock(&ksm_mmlist_lock);
1201	slot = list_entry(ksm_mm_head.slot.mm_node.next,
1202			  struct mm_slot, mm_node);
1203	ksm_scan.mm_slot = mm_slot_entry(slot, struct ksm_mm_slot, slot);
1204	spin_unlock(&ksm_mmlist_lock);
1205
1206	for (mm_slot = ksm_scan.mm_slot; mm_slot != &ksm_mm_head;
1207	     mm_slot = ksm_scan.mm_slot) {
1208		VMA_ITERATOR(vmi, mm_slot->slot.mm, 0);
1209
1210		mm = mm_slot->slot.mm;
1211		mmap_read_lock(mm);
1212
1213		/*
1214		 * Exit right away if mm is exiting to avoid lockdep issue in
1215		 * the maple tree
1216		 */
1217		if (ksm_test_exit(mm))
1218			goto mm_exiting;
1219
1220		for_each_vma(vmi, vma) {
1221			if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)
1222				continue;
1223			err = break_ksm(vma, vma->vm_start, vma->vm_end, false);
1224			if (err)
1225				goto error;
1226		}
1227
1228mm_exiting:
1229		remove_trailing_rmap_items(&mm_slot->rmap_list);
1230		mmap_read_unlock(mm);
1231
1232		spin_lock(&ksm_mmlist_lock);
1233		slot = list_entry(mm_slot->slot.mm_node.next,
1234				  struct mm_slot, mm_node);
1235		ksm_scan.mm_slot = mm_slot_entry(slot, struct ksm_mm_slot, slot);
1236		if (ksm_test_exit(mm)) {
1237			hash_del(&mm_slot->slot.hash);
1238			list_del(&mm_slot->slot.mm_node);
1239			spin_unlock(&ksm_mmlist_lock);
1240
1241			mm_slot_free(mm_slot_cache, mm_slot);
1242			mm_flags_clear(MMF_VM_MERGEABLE, mm);
1243			mm_flags_clear(MMF_VM_MERGE_ANY, mm);
1244			mmdrop(mm);
1245		} else
1246			spin_unlock(&ksm_mmlist_lock);
1247	}
1248
1249	/* Clean up stable nodes, but don't worry if some are still busy */
1250	remove_all_stable_nodes();
1251	ksm_scan.seqnr = 0;
1252	return 0;
1253
1254error:
1255	mmap_read_unlock(mm);
1256	spin_lock(&ksm_mmlist_lock);
1257	ksm_scan.mm_slot = &ksm_mm_head;
1258	spin_unlock(&ksm_mmlist_lock);
1259	return err;
1260}
1261#endif /* CONFIG_SYSFS */
1262
1263static u32 calc_checksum(struct page *page)
1264{
1265	u32 checksum;
1266	void *addr = kmap_local_page(page);
1267	checksum = xxhash(addr, PAGE_SIZE, 0);
1268	kunmap_local(addr);
1269	return checksum;
1270}
1271
1272static int write_protect_page(struct vm_area_struct *vma, struct folio *folio,
1273			      pte_t *orig_pte)
1274{
1275	struct mm_struct *mm = vma->vm_mm;
1276	DEFINE_FOLIO_VMA_WALK(pvmw, folio, vma, 0, 0);
1277	int swapped;
1278	int err = -EFAULT;
1279	struct mmu_notifier_range range;
1280	bool anon_exclusive;
1281	pte_t entry;
1282
1283	if (WARN_ON_ONCE(folio_test_large(folio)))
1284		return err;
1285
1286	pvmw.address = page_address_in_vma(folio, folio_page(folio, 0), vma);
1287	if (pvmw.address == -EFAULT)
1288		goto out;
1289
1290	mmu_notifier_range_init(&range, MMU_NOTIFY_CLEAR, 0, mm, pvmw.address,
1291				pvmw.address + PAGE_SIZE);
1292	mmu_notifier_invalidate_range_start(&range);
1293
1294	if (!page_vma_mapped_walk(&pvmw))
1295		goto out_mn;
1296	if (WARN_ONCE(!pvmw.pte, "Unexpected PMD mapping?"))
1297		goto out_unlock;
1298
1299	entry = ptep_get(pvmw.pte);
1300	/*
1301	 * Handle PFN swap PTEs, such as device-exclusive ones, that actually
1302	 * map pages: give up just like the next folio_walk would.
1303	 */
1304	if (unlikely(!pte_present(entry)))
1305		goto out_unlock;
1306
1307	anon_exclusive = PageAnonExclusive(&folio->page);
1308	if (pte_write(entry) || pte_dirty(entry) ||
1309	    anon_exclusive || mm_tlb_flush_pending(mm)) {
1310		swapped = folio_test_swapcache(folio);
1311		flush_cache_page(vma, pvmw.address, folio_pfn(folio));
1312		/*
1313		 * Ok this is tricky, when get_user_pages_fast() run it doesn't
1314		 * take any lock, therefore the check that we are going to make
1315		 * with the pagecount against the mapcount is racy and
1316		 * O_DIRECT can happen right after the check.
1317		 * So we clear the pte and flush the tlb before the check
1318		 * this assure us that no O_DIRECT can happen after the check
1319		 * or in the middle of the check.
1320		 *
1321		 * No need to notify as we are downgrading page table to read
1322		 * only not changing it to point to a new page.
1323		 *
1324		 * See Documentation/mm/mmu_notifier.rst
1325		 */
1326		entry = ptep_clear_flush(vma, pvmw.address, pvmw.pte);
1327		/*
1328		 * Check that no O_DIRECT or similar I/O is in progress on the
1329		 * page
1330		 */
1331		if (folio_mapcount(folio) + 1 + swapped != folio_ref_count(folio)) {
1332			set_pte_at(mm, pvmw.address, pvmw.pte, entry);
1333			goto out_unlock;
1334		}
1335
1336		/* See folio_try_share_anon_rmap_pte(): clear PTE first. */
1337		if (anon_exclusive &&
1338		    folio_try_share_anon_rmap_pte(folio, &folio->page)) {
1339			set_pte_at(mm, pvmw.address, pvmw.pte, entry);
1340			goto out_unlock;
1341		}
1342
1343		if (pte_dirty(entry))
1344			folio_mark_dirty(folio);
1345		entry = pte_mkclean(entry);
1346
1347		if (pte_write(entry))
1348			entry = pte_wrprotect(entry);
1349
1350		set_pte_at(mm, pvmw.address, pvmw.pte, entry);
1351	}
1352	*orig_pte = entry;
1353	err = 0;
1354
1355out_unlock:
1356	page_vma_mapped_walk_done(&pvmw);
1357out_mn:
1358	mmu_notifier_invalidate_range_end(&range);
1359out:
1360	return err;
1361}
1362
1363/**
1364 * replace_page - replace page in vma by new ksm page
1365 * @vma:      vma that holds the pte pointing to page
1366 * @page:     the page we are replacing by kpage
1367 * @kpage:    the ksm page we replace page by
1368 * @orig_pte: the original value of the pte
1369 *
1370 * Returns 0 on success, -EFAULT on failure.
1371 */
1372static int replace_page(struct vm_area_struct *vma, struct page *page,
1373			struct page *kpage, pte_t orig_pte)
1374{
1375	struct folio *kfolio = page_folio(kpage);
1376	struct mm_struct *mm = vma->vm_mm;
1377	struct folio *folio = page_folio(page);
1378	pmd_t *pmd;
1379	pmd_t pmde;
1380	pte_t *ptep;
1381	pte_t newpte;
1382	spinlock_t *ptl;
1383	unsigned long addr;
1384	int err = -EFAULT;
1385	struct mmu_notifier_range range;
1386
1387	addr = page_address_in_vma(folio, page, vma);
1388	if (addr == -EFAULT)
1389		goto out;
1390
1391	pmd = mm_find_pmd(mm, addr);
1392	if (!pmd)
1393		goto out;
1394	/*
1395	 * Some THP functions use the sequence pmdp_huge_clear_flush(), set_pmd_at()
1396	 * without holding anon_vma lock for write.  So when looking for a
1397	 * genuine pmde (in which to find pte), test present and !THP together.
1398	 */
1399	pmde = pmdp_get_lockless(pmd);
1400	if (!pmd_present(pmde) || pmd_trans_huge(pmde))
1401		goto out;
1402
1403	mmu_notifier_range_init(&range, MMU_NOTIFY_CLEAR, 0, mm, addr,
1404				addr + PAGE_SIZE);
1405	mmu_notifier_invalidate_range_start(&range);
1406
1407	ptep = pte_offset_map_lock(mm, pmd, addr, &ptl);
1408	if (!ptep)
1409		goto out_mn;
1410	if (!pte_same(ptep_get(ptep), orig_pte)) {
1411		pte_unmap_unlock(ptep, ptl);
1412		goto out_mn;
1413	}
1414	VM_BUG_ON_PAGE(PageAnonExclusive(page), page);
1415	VM_BUG_ON_FOLIO(folio_test_anon(kfolio) && PageAnonExclusive(kpage),
1416			kfolio);
1417
1418	/*
1419	 * No need to check ksm_use_zero_pages here: we can only have a
1420	 * zero_page here if ksm_use_zero_pages was enabled already.
1421	 */
1422	if (!is_zero_pfn(page_to_pfn(kpage))) {
1423		folio_get(kfolio);
1424		folio_add_anon_rmap_pte(kfolio, kpage, vma, addr, RMAP_NONE);
1425		newpte = mk_pte(kpage, vma->vm_page_prot);
1426	} else {
1427		/*
1428		 * Use pte_mkdirty to mark the zero page mapped by KSM, and then
1429		 * we can easily track all KSM-placed zero pages by checking if
1430		 * the dirty bit in zero page's PTE is set.
1431		 */
1432		newpte = pte_mkdirty(pte_mkspecial(pfn_pte(page_to_pfn(kpage), vma->vm_page_prot)));
1433		ksm_map_zero_page(mm);
1434		/*
1435		 * We're replacing an anonymous page with a zero page, which is
1436		 * not anonymous. We need to do proper accounting otherwise we
1437		 * will get wrong values in /proc, and a BUG message in dmesg
1438		 * when tearing down the mm.
1439		 */
1440		dec_mm_counter(mm, MM_ANONPAGES);
1441	}
1442
1443	flush_cache_page(vma, addr, pte_pfn(ptep_get(ptep)));
1444	/*
1445	 * No need to notify as we are replacing a read only page with another
1446	 * read only page with the same content.
1447	 *
1448	 * See Documentation/mm/mmu_notifier.rst
1449	 */
1450	ptep_clear_flush(vma, addr, ptep);
1451	set_pte_at(mm, addr, ptep, newpte);
1452
1453	folio_remove_rmap_pte(folio, page, vma);
1454	if (!folio_mapped(folio))
1455		folio_free_swap(folio);
1456	folio_put(folio);
1457
1458	pte_unmap_unlock(ptep, ptl);
1459	err = 0;
1460out_mn:
1461	mmu_notifier_invalidate_range_end(&range);
1462out:
1463	return err;
1464}
1465
1466/*
1467 * try_to_merge_one_page - take two pages and merge them into one
1468 * @vma: the vma that holds the pte pointing to page
1469 * @page: the PageAnon page that we want to replace with kpage
1470 * @kpage: the KSM page that we want to map instead of page,
1471 *         or NULL the first time when we want to use page as kpage.
1472 *
1473 * This function returns 0 if the pages were merged, -EFAULT otherwise.
1474 */
1475static int try_to_merge_one_page(struct vm_area_struct *vma,
1476				 struct page *page, struct page *kpage)
1477{
1478	struct folio *folio = page_folio(page);
1479	pte_t orig_pte = __pte(0);
1480	int err = -EFAULT;
1481
1482	if (page == kpage)			/* ksm page forked */
1483		return 0;
1484
1485	if (!folio_test_anon(folio))
1486		goto out;
1487
1488	/*
1489	 * We need the folio lock to read a stable swapcache flag in
1490	 * write_protect_page().  We trylock because we don't want to wait
1491	 * here - we prefer to continue scanning and merging different
1492	 * pages, then come back to this page when it is unlocked.
1493	 */
1494	if (!folio_trylock(folio))
1495		goto out;
1496
1497	if (folio_test_large(folio)) {
1498		if (split_huge_page(page))
1499			goto out_unlock;
1500		folio = page_folio(page);
1501	}
1502
1503	/*
1504	 * If this anonymous page is mapped only here, its pte may need
1505	 * to be write-protected.  If it's mapped elsewhere, all of its
1506	 * ptes are necessarily already write-protected.  But in either
1507	 * case, we need to lock and check page_count is not raised.
1508	 */
1509	if (write_protect_page(vma, folio, &orig_pte) == 0) {
1510		if (!kpage) {
1511			/*
1512			 * While we hold folio lock, upgrade folio from
1513			 * anon to a NULL stable_node with the KSM flag set:
1514			 * stable_tree_insert() will update stable_node.
1515			 */
1516			folio_set_stable_node(folio, NULL);
1517			folio_mark_accessed(folio);
1518			/*
1519			 * Page reclaim just frees a clean folio with no dirty
1520			 * ptes: make sure that the ksm page would be swapped.
1521			 */
1522			if (!folio_test_dirty(folio))
1523				folio_mark_dirty(folio);
1524			err = 0;
1525		} else if (pages_identical(page, kpage))
1526			err = replace_page(vma, page, kpage, orig_pte);
1527	}
1528
1529out_unlock:
1530	folio_unlock(folio);
1531out:
1532	return err;
1533}
1534
1535/*
1536 * This function returns 0 if the pages were merged or if they are
1537 * no longer merging candidates (e.g., VMA stale), -EFAULT otherwise.
1538 */
1539static int try_to_merge_with_zero_page(struct ksm_rmap_item *rmap_item,
1540				       struct page *page)
1541{
1542	struct mm_struct *mm = rmap_item->mm;
1543	int err = -EFAULT;
1544
1545	/*
1546	 * Same checksum as an empty page. We attempt to merge it with the
1547	 * appropriate zero page if the user enabled this via sysfs.
1548	 */
1549	if (ksm_use_zero_pages && (rmap_item->oldchecksum == zero_checksum)) {
1550		struct vm_area_struct *vma;
1551
1552		mmap_read_lock(mm);
1553		vma = find_mergeable_vma(mm, rmap_item->address);
1554		if (vma) {
1555			err = try_to_merge_one_page(vma, page,
1556					ZERO_PAGE(rmap_item->address));
1557			trace_ksm_merge_one_page(
1558				page_to_pfn(ZERO_PAGE(rmap_item->address)),
1559				rmap_item, mm, err);
1560		} else {
1561			/*
1562			 * If the vma is out of date, we do not need to
1563			 * continue.
1564			 */
1565			err = 0;
1566		}
1567		mmap_read_unlock(mm);
1568	}
1569
1570	return err;
1571}
1572
1573/*
1574 * try_to_merge_with_ksm_page - like try_to_merge_two_pages,
1575 * but no new kernel page is allocated: kpage must already be a ksm page.
1576 *
1577 * This function returns 0 if the pages were merged, -EFAULT otherwise.
1578 */
1579static int try_to_merge_with_ksm_page(struct ksm_rmap_item *rmap_item,
1580				      struct page *page, struct page *kpage)
1581{
1582	struct mm_struct *mm = rmap_item->mm;
1583	struct vm_area_struct *vma;
1584	int err = -EFAULT;
1585
1586	mmap_read_lock(mm);
1587	vma = find_mergeable_vma(mm, rmap_item->address);
1588	if (!vma)
1589		goto out;
1590
1591	err = try_to_merge_one_page(vma, page, kpage);
1592	if (err)
1593		goto out;
1594
1595	/* Unstable nid is in union with stable anon_vma: remove first */
1596	remove_rmap_item_from_tree(rmap_item);
1597
1598	/* Must get reference to anon_vma while still holding mmap_lock */
1599	rmap_item->anon_vma = vma->anon_vma;
1600	get_anon_vma(vma->anon_vma);
1601out:
1602	mmap_read_unlock(mm);
1603	trace_ksm_merge_with_ksm_page(kpage, page_to_pfn(kpage ? kpage : page),
1604				rmap_item, mm, err);
1605	return err;
1606}
1607
1608/*
1609 * try_to_merge_two_pages - take two identical pages and prepare them
1610 * to be merged into one page.
1611 *
1612 * This function returns the kpage if we successfully merged two identical
1613 * pages into one ksm page, NULL otherwise.
1614 *
1615 * Note that this function upgrades page to ksm page: if one of the pages
1616 * is already a ksm page, try_to_merge_with_ksm_page should be used.
1617 */
1618static struct folio *try_to_merge_two_pages(struct ksm_rmap_item *rmap_item,
1619					   struct page *page,
1620					   struct ksm_rmap_item *tree_rmap_item,
1621					   struct page *tree_page)
1622{
1623	int err;
1624
1625	err = try_to_merge_with_ksm_page(rmap_item, page, NULL);
1626	if (!err) {
1627		err = try_to_merge_with_ksm_page(tree_rmap_item,
1628							tree_page, page);
1629		/*
1630		 * If that fails, we have a ksm page with only one pte
1631		 * pointing to it: so break it.
1632		 */
1633		if (err)
1634			break_cow(rmap_item);
1635	}
1636	return err ? NULL : page_folio(page);
1637}
1638
1639static __always_inline
1640bool __is_page_sharing_candidate(struct ksm_stable_node *stable_node, int offset)
1641{
1642	VM_BUG_ON(stable_node->rmap_hlist_len < 0);
1643	/*
1644	 * Check that at least one mapping still exists, otherwise
1645	 * there's no much point to merge and share with this
1646	 * stable_node, as the underlying tree_page of the other
1647	 * sharer is going to be freed soon.
1648	 */
1649	return stable_node->rmap_hlist_len &&
1650		stable_node->rmap_hlist_len + offset < ksm_max_page_sharing;
1651}
1652
1653static __always_inline
1654bool is_page_sharing_candidate(struct ksm_stable_node *stable_node)
1655{
1656	return __is_page_sharing_candidate(stable_node, 0);
1657}
1658
1659static struct folio *stable_node_dup(struct ksm_stable_node **_stable_node_dup,
1660				     struct ksm_stable_node **_stable_node,
1661				     struct rb_root *root,
1662				     bool prune_stale_stable_nodes)
1663{
1664	struct ksm_stable_node *dup, *found = NULL, *stable_node = *_stable_node;
1665	struct hlist_node *hlist_safe;
1666	struct folio *folio, *tree_folio = NULL;
1667	int found_rmap_hlist_len;
1668
1669	if (!prune_stale_stable_nodes ||
1670	    time_before(jiffies, stable_node->chain_prune_time +
1671			msecs_to_jiffies(
1672				ksm_stable_node_chains_prune_millisecs)))
1673		prune_stale_stable_nodes = false;
1674	else
1675		stable_node->chain_prune_time = jiffies;
1676
1677	hlist_for_each_entry_safe(dup, hlist_safe,
1678				  &stable_node->hlist, hlist_dup) {
1679		cond_resched();
1680		/*
1681		 * We must walk all stable_node_dup to prune the stale
1682		 * stable nodes during lookup.
1683		 *
1684		 * ksm_get_folio can drop the nodes from the
1685		 * stable_node->hlist if they point to freed pages
1686		 * (that's why we do a _safe walk). The "dup"
1687		 * stable_node parameter itself will be freed from
1688		 * under us if it returns NULL.
1689		 */
1690		folio = ksm_get_folio(dup, KSM_GET_FOLIO_NOLOCK);
1691		if (!folio)
1692			continue;
1693		/* Pick the best candidate if possible. */
1694		if (!found || (is_page_sharing_candidate(dup) &&
1695		    (!is_page_sharing_candidate(found) ||
1696		     dup->rmap_hlist_len > found_rmap_hlist_len))) {
1697			if (found)
1698				folio_put(tree_folio);
1699			found = dup;
1700			found_rmap_hlist_len = found->rmap_hlist_len;
1701			tree_folio = folio;
1702			/* skip put_page for found candidate */
1703			if (!prune_stale_stable_nodes &&
1704			    is_page_sharing_candidate(found))
1705				break;
1706			continue;
1707		}
1708		folio_put(folio);
1709	}
1710
1711	if (found) {
1712		if (hlist_is_singular_node(&found->hlist_dup, &stable_node->hlist)) {
1713			/*
1714			 * If there's not just one entry it would
1715			 * corrupt memory, better BUG_ON. In KSM
1716			 * context with no lock held it's not even
1717			 * fatal.
1718			 */
1719			BUG_ON(stable_node->hlist.first->next);
1720
1721			/*
1722			 * There's just one entry and it is below the
1723			 * deduplication limit so drop the chain.
1724			 */
1725			rb_replace_node(&stable_node->node, &found->node,
1726					root);
1727			free_stable_node(stable_node);
1728			ksm_stable_node_chains--;
1729			ksm_stable_node_dups--;
1730			/*
1731			 * NOTE: the caller depends on the stable_node
1732			 * to be equal to stable_node_dup if the chain
1733			 * was collapsed.
1734			 */
1735			*_stable_node = found;
1736			/*
1737			 * Just for robustness, as stable_node is
1738			 * otherwise left as a stable pointer, the
1739			 * compiler shall optimize it away at build
1740			 * time.
1741			 */
1742			stable_node = NULL;
1743		} else if (stable_node->hlist.first != &found->hlist_dup &&
1744			   __is_page_sharing_candidate(found, 1)) {
1745			/*
1746			 * If the found stable_node dup can accept one
1747			 * more future merge (in addition to the one
1748			 * that is underway) and is not at the head of
1749			 * the chain, put it there so next search will
1750			 * be quicker in the !prune_stale_stable_nodes
1751			 * case.
1752			 *
1753			 * NOTE: it would be inaccurate to use nr > 1
1754			 * instead of checking the hlist.first pointer
1755			 * directly, because in the
1756			 * prune_stale_stable_nodes case "nr" isn't
1757			 * the position of the found dup in the chain,
1758			 * but the total number of dups in the chain.
1759			 */
1760			hlist_del(&found->hlist_dup);
1761			hlist_add_head(&found->hlist_dup,
1762				       &stable_node->hlist);
1763		}
1764	} else {
1765		/* Its hlist must be empty if no one found. */
1766		free_stable_node_chain(stable_node, root);
1767	}
1768
1769	*_stable_node_dup = found;
1770	return tree_folio;
1771}
1772
1773/*
1774 * Like for ksm_get_folio, this function can free the *_stable_node and
1775 * *_stable_node_dup if the returned tree_page is NULL.
1776 *
1777 * It can also free and overwrite *_stable_node with the found
1778 * stable_node_dup if the chain is collapsed (in which case
1779 * *_stable_node will be equal to *_stable_node_dup like if the chain
1780 * never existed). It's up to the caller to verify tree_page is not
1781 * NULL before dereferencing *_stable_node or *_stable_node_dup.
1782 *
1783 * *_stable_node_dup is really a second output parameter of this
1784 * function and will be overwritten in all cases, the caller doesn't
1785 * need to initialize it.
1786 */
1787static struct folio *__stable_node_chain(struct ksm_stable_node **_stable_node_dup,
1788					 struct ksm_stable_node **_stable_node,
1789					 struct rb_root *root,
1790					 bool prune_stale_stable_nodes)
1791{
1792	struct ksm_stable_node *stable_node = *_stable_node;
1793
1794	if (!is_stable_node_chain(stable_node)) {
1795		*_stable_node_dup = stable_node;
1796		return ksm_get_folio(stable_node, KSM_GET_FOLIO_NOLOCK);
1797	}
1798	return stable_node_dup(_stable_node_dup, _stable_node, root,
1799			       prune_stale_stable_nodes);
1800}
1801
1802static __always_inline struct folio *chain_prune(struct ksm_stable_node **s_n_d,
1803						 struct ksm_stable_node **s_n,
1804						 struct rb_root *root)
1805{
1806	return __stable_node_chain(s_n_d, s_n, root, true);
1807}
1808
1809static __always_inline struct folio *chain(struct ksm_stable_node **s_n_d,
1810					   struct ksm_stable_node **s_n,
1811					   struct rb_root *root)
1812{
1813	return __stable_node_chain(s_n_d, s_n, root, false);
1814}
1815
1816/*
1817 * stable_tree_search - search for page inside the stable tree
1818 *
1819 * This function checks if there is a page inside the stable tree
1820 * with identical content to the page that we are scanning right now.
1821 *
1822 * This function returns the stable tree node of identical content if found,
1823 * -EBUSY if the stable node's page is being migrated, NULL otherwise.
1824 */
1825static struct folio *stable_tree_search(struct page *page)
1826{
1827	int nid;
1828	struct rb_root *root;
1829	struct rb_node **new;
1830	struct rb_node *parent;
1831	struct ksm_stable_node *stable_node, *stable_node_dup;
1832	struct ksm_stable_node *page_node;
1833	struct folio *folio;
1834
1835	folio = page_folio(page);
1836	page_node = folio_stable_node(folio);
1837	if (page_node && page_node->head != &migrate_nodes) {
1838		/* ksm page forked */
1839		folio_get(folio);
1840		return folio;
1841	}
1842
1843	nid = get_kpfn_nid(folio_pfn(folio));
1844	root = root_stable_tree + nid;
1845again:
1846	new = &root->rb_node;
1847	parent = NULL;
1848
1849	while (*new) {
1850		struct folio *tree_folio;
1851		int ret;
1852
1853		cond_resched();
1854		stable_node = rb_entry(*new, struct ksm_stable_node, node);
1855		tree_folio = chain_prune(&stable_node_dup, &stable_node, root);
1856		if (!tree_folio) {
1857			/*
1858			 * If we walked over a stale stable_node,
1859			 * ksm_get_folio() will call rb_erase() and it
1860			 * may rebalance the tree from under us. So
1861			 * restart the search from scratch. Returning
1862			 * NULL would be safe too, but we'd generate
1863			 * false negative insertions just because some
1864			 * stable_node was stale.
1865			 */
1866			goto again;
1867		}
1868
1869		ret = memcmp_pages(page, &tree_folio->page);
1870		folio_put(tree_folio);
1871
1872		parent = *new;
1873		if (ret < 0)
1874			new = &parent->rb_left;
1875		else if (ret > 0)
1876			new = &parent->rb_right;
1877		else {
1878			if (page_node) {
1879				VM_BUG_ON(page_node->head != &migrate_nodes);
1880				/*
1881				 * If the mapcount of our migrated KSM folio is
1882				 * at most 1, we can merge it with another
1883				 * KSM folio where we know that we have space
1884				 * for one more mapping without exceeding the
1885				 * ksm_max_page_sharing limit: see
1886				 * chain_prune(). This way, we can avoid adding
1887				 * this stable node to the chain.
1888				 */
1889				if (folio_mapcount(folio) > 1)
1890					goto chain_append;
1891			}
1892
1893			if (!is_page_sharing_candidate(stable_node_dup)) {
1894				/*
1895				 * If the stable_node is a chain and
1896				 * we got a payload match in memcmp
1897				 * but we cannot merge the scanned
1898				 * page in any of the existing
1899				 * stable_node dups because they're
1900				 * all full, we need to wait the
1901				 * scanned page to find itself a match
1902				 * in the unstable tree to create a
1903				 * brand new KSM page to add later to
1904				 * the dups of this stable_node.
1905				 */
1906				return NULL;
1907			}
1908
1909			/*
1910			 * Lock and unlock the stable_node's page (which
1911			 * might already have been migrated) so that page
1912			 * migration is sure to notice its raised count.
1913			 * It would be more elegant to return stable_node
1914			 * than kpage, but that involves more changes.
1915			 */
1916			tree_folio = ksm_get_folio(stable_node_dup,
1917						   KSM_GET_FOLIO_TRYLOCK);
1918
1919			if (PTR_ERR(tree_folio) == -EBUSY)
1920				return ERR_PTR(-EBUSY);
1921
1922			if (unlikely(!tree_folio))
1923				/*
1924				 * The tree may have been rebalanced,
1925				 * so re-evaluate parent and new.
1926				 */
1927				goto again;
1928			folio_unlock(tree_folio);
1929
1930			if (get_kpfn_nid(stable_node_dup->kpfn) !=
1931			    NUMA(stable_node_dup->nid)) {
1932				folio_put(tree_folio);
1933				goto replace;
1934			}
1935			return tree_folio;
1936		}
1937	}
1938
1939	if (!page_node)
1940		return NULL;
1941
1942	list_del(&page_node->list);
1943	DO_NUMA(page_node->nid = nid);
1944	rb_link_node(&page_node->node, parent, new);
1945	rb_insert_color(&page_node->node, root);
1946out:
1947	if (is_page_sharing_candidate(page_node)) {
1948		folio_get(folio);
1949		return folio;
1950	} else
1951		return NULL;
1952
1953replace:
1954	/*
1955	 * If stable_node was a chain and chain_prune collapsed it,
1956	 * stable_node has been updated to be the new regular
1957	 * stable_node. A collapse of the chain is indistinguishable
1958	 * from the case there was no chain in the stable
1959	 * rbtree. Otherwise stable_node is the chain and
1960	 * stable_node_dup is the dup to replace.
1961	 */
1962	if (stable_node_dup == stable_node) {
1963		VM_BUG_ON(is_stable_node_chain(stable_node_dup));
1964		VM_BUG_ON(is_stable_node_dup(stable_node_dup));
1965		/* there is no chain */
1966		if (page_node) {
1967			VM_BUG_ON(page_node->head != &migrate_nodes);
1968			list_del(&page_node->list);
1969			DO_NUMA(page_node->nid = nid);
1970			rb_replace_node(&stable_node_dup->node,
1971					&page_node->node,
1972					root);
1973			if (is_page_sharing_candidate(page_node))
1974				folio_get(folio);
1975			else
1976				folio = NULL;
1977		} else {
1978			rb_erase(&stable_node_dup->node, root);
1979			folio = NULL;
1980		}
1981	} else {
1982		VM_BUG_ON(!is_stable_node_chain(stable_node));
1983		__stable_node_dup_del(stable_node_dup);
1984		if (page_node) {
1985			VM_BUG_ON(page_node->head != &migrate_nodes);
1986			list_del(&page_node->list);
1987			DO_NUMA(page_node->nid = nid);
1988			stable_node_chain_add_dup(page_node, stable_node);
1989			if (is_page_sharing_candidate(page_node))
1990				folio_get(folio);
1991			else
1992				folio = NULL;
1993		} else {
1994			folio = NULL;
1995		}
1996	}
1997	stable_node_dup->head = &migrate_nodes;
1998	list_add(&stable_node_dup->list, stable_node_dup->head);
1999	return folio;
2000
2001chain_append:
2002	/*
2003	 * If stable_node was a chain and chain_prune collapsed it,
2004	 * stable_node has been updated to be the new regular
2005	 * stable_node. A collapse of the chain is indistinguishable
2006	 * from the case there was no chain in the stable
2007	 * rbtree. Otherwise stable_node is the chain and
2008	 * stable_node_dup is the dup to replace.
2009	 */
2010	if (stable_node_dup == stable_node) {
2011		VM_BUG_ON(is_stable_node_dup(stable_node_dup));
2012		/* chain is missing so create it */
2013		stable_node = alloc_stable_node_chain(stable_node_dup,
2014						      root);
2015		if (!stable_node)
2016			return NULL;
2017	}
2018	/*
2019	 * Add this stable_node dup that was
2020	 * migrated to the stable_node chain
2021	 * of the current nid for this page
2022	 * content.
2023	 */
2024	VM_BUG_ON(!is_stable_node_dup(stable_node_dup));
2025	VM_BUG_ON(page_node->head != &migrate_nodes);
2026	list_del(&page_node->list);
2027	DO_NUMA(page_node->nid = nid);
2028	stable_node_chain_add_dup(page_node, stable_node);
2029	goto out;
2030}
2031
2032/*
2033 * stable_tree_insert - insert stable tree node pointing to new ksm page
2034 * into the stable tree.
2035 *
2036 * This function returns the stable tree node just allocated on success,
2037 * NULL otherwise.
2038 */
2039static struct ksm_stable_node *stable_tree_insert(struct folio *kfolio)
2040{
2041	int nid;
2042	unsigned long kpfn;
2043	struct rb_root *root;
2044	struct rb_node **new;
2045	struct rb_node *parent;
2046	struct ksm_stable_node *stable_node, *stable_node_dup;
2047	bool need_chain = false;
2048
2049	kpfn = folio_pfn(kfolio);
2050	nid = get_kpfn_nid(kpfn);
2051	root = root_stable_tree + nid;
2052again:
2053	parent = NULL;
2054	new = &root->rb_node;
2055
2056	while (*new) {
2057		struct folio *tree_folio;
2058		int ret;
2059
2060		cond_resched();
2061		stable_node = rb_entry(*new, struct ksm_stable_node, node);
2062		tree_folio = chain(&stable_node_dup, &stable_node, root);
2063		if (!tree_folio) {
2064			/*
2065			 * If we walked over a stale stable_node,
2066			 * ksm_get_folio() will call rb_erase() and it
2067			 * may rebalance the tree from under us. So
2068			 * restart the search from scratch. Returning
2069			 * NULL would be safe too, but we'd generate
2070			 * false negative insertions just because some
2071			 * stable_node was stale.
2072			 */
2073			goto again;
2074		}
2075
2076		ret = memcmp_pages(&kfolio->page, &tree_folio->page);
2077		folio_put(tree_folio);
2078
2079		parent = *new;
2080		if (ret < 0)
2081			new = &parent->rb_left;
2082		else if (ret > 0)
2083			new = &parent->rb_right;
2084		else {
2085			need_chain = true;
2086			break;
2087		}
2088	}
2089
2090	stable_node_dup = alloc_stable_node();
2091	if (!stable_node_dup)
2092		return NULL;
2093
2094	INIT_HLIST_HEAD(&stable_node_dup->hlist);
2095	stable_node_dup->kpfn = kpfn;
2096	stable_node_dup->rmap_hlist_len = 0;
2097	DO_NUMA(stable_node_dup->nid = nid);
2098	if (!need_chain) {
2099		rb_link_node(&stable_node_dup->node, parent, new);
2100		rb_insert_color(&stable_node_dup->node, root);
2101	} else {
2102		if (!is_stable_node_chain(stable_node)) {
2103			struct ksm_stable_node *orig = stable_node;
2104			/* chain is missing so create it */
2105			stable_node = alloc_stable_node_chain(orig, root);
2106			if (!stable_node) {
2107				free_stable_node(stable_node_dup);
2108				return NULL;
2109			}
2110		}
2111		stable_node_chain_add_dup(stable_node_dup, stable_node);
2112	}
2113
2114	folio_set_stable_node(kfolio, stable_node_dup);
2115
2116	return stable_node_dup;
2117}
2118
2119/*
2120 * unstable_tree_search_insert - search for identical page,
2121 * else insert rmap_item into the unstable tree.
2122 *
2123 * This function searches for a page in the unstable tree identical to the
2124 * page currently being scanned; and if no identical page is found in the
2125 * tree, we insert rmap_item as a new object into the unstable tree.
2126 *
2127 * This function returns pointer to rmap_item found to be identical
2128 * to the currently scanned page, NULL otherwise.
2129 *
2130 * This function does both searching and inserting, because they share
2131 * the same walking algorithm in an rbtree.
2132 */
2133static
2134struct ksm_rmap_item *unstable_tree_search_insert(struct ksm_rmap_item *rmap_item,
2135					      struct page *page,
2136					      struct page **tree_pagep)
2137{
2138	struct rb_node **new;
2139	struct rb_root *root;
2140	struct rb_node *parent = NULL;
2141	int nid;
2142
2143	nid = get_kpfn_nid(page_to_pfn(page));
2144	root = root_unstable_tree + nid;
2145	new = &root->rb_node;
2146
2147	while (*new) {
2148		struct ksm_rmap_item *tree_rmap_item;
2149		struct page *tree_page;
2150		int ret;
2151
2152		cond_resched();
2153		tree_rmap_item = rb_entry(*new, struct ksm_rmap_item, node);
2154		tree_page = get_mergeable_page(tree_rmap_item);
2155		if (!tree_page)
2156			return NULL;
2157
2158		/*
2159		 * Don't substitute a ksm page for a forked page.
2160		 */
2161		if (page == tree_page) {
2162			put_page(tree_page);
2163			return NULL;
2164		}
2165
2166		ret = memcmp_pages(page, tree_page);
2167
2168		parent = *new;
2169		if (ret < 0) {
2170			put_page(tree_page);
2171			new = &parent->rb_left;
2172		} else if (ret > 0) {
2173			put_page(tree_page);
2174			new = &parent->rb_right;
2175		} else if (!ksm_merge_across_nodes &&
2176			   page_to_nid(tree_page) != nid) {
2177			/*
2178			 * If tree_page has been migrated to another NUMA node,
2179			 * it will be flushed out and put in the right unstable
2180			 * tree next time: only merge with it when across_nodes.
2181			 */
2182			put_page(tree_page);
2183			return NULL;
2184		} else {
2185			*tree_pagep = tree_page;
2186			return tree_rmap_item;
2187		}
2188	}
2189
2190	rmap_item->address |= UNSTABLE_FLAG;
2191	rmap_item->address |= (ksm_scan.seqnr & SEQNR_MASK);
2192	DO_NUMA(rmap_item->nid = nid);
2193	rb_link_node(&rmap_item->node, parent, new);
2194	rb_insert_color(&rmap_item->node, root);
2195
2196	ksm_pages_unshared++;
2197	return NULL;
2198}
2199
2200/*
2201 * stable_tree_append - add another rmap_item to the linked list of
2202 * rmap_items hanging off a given node of the stable tree, all sharing
2203 * the same ksm page.
2204 */
2205static void stable_tree_append(struct ksm_rmap_item *rmap_item,
2206			       struct ksm_stable_node *stable_node,
2207			       bool max_page_sharing_bypass)
2208{
2209	/*
2210	 * rmap won't find this mapping if we don't insert the
2211	 * rmap_item in the right stable_node
2212	 * duplicate. page_migration could break later if rmap breaks,
2213	 * so we can as well crash here. We really need to check for
2214	 * rmap_hlist_len == STABLE_NODE_CHAIN, but we can as well check
2215	 * for other negative values as an underflow if detected here
2216	 * for the first time (and not when decreasing rmap_hlist_len)
2217	 * would be sign of memory corruption in the stable_node.
2218	 */
2219	BUG_ON(stable_node->rmap_hlist_len < 0);
2220
2221	stable_node->rmap_hlist_len++;
2222	if (!max_page_sharing_bypass)
2223		/* possibly non fatal but unexpected overflow, only warn */
2224		WARN_ON_ONCE(stable_node->rmap_hlist_len >
2225			     ksm_max_page_sharing);
2226
2227	rmap_item->head = stable_node;
2228	rmap_item->address |= STABLE_FLAG;
2229	hlist_add_head(&rmap_item->hlist, &stable_node->hlist);
2230
2231	if (rmap_item->hlist.next)
2232		ksm_pages_sharing++;
2233	else
2234		ksm_pages_shared++;
2235
2236	rmap_item->mm->ksm_merging_pages++;
2237}
2238
2239/*
2240 * cmp_and_merge_page - first see if page can be merged into the stable tree;
2241 * if not, compare checksum to previous and if it's the same, see if page can
2242 * be inserted into the unstable tree, or merged with a page already there and
2243 * both transferred to the stable tree.
2244 *
2245 * @page: the page that we are searching identical page to.
2246 * @rmap_item: the reverse mapping into the virtual address of this page
2247 */
2248static void cmp_and_merge_page(struct page *page, struct ksm_rmap_item *rmap_item)
2249{
2250	struct folio *folio = page_folio(page);
2251	struct ksm_rmap_item *tree_rmap_item;
2252	struct page *tree_page = NULL;
2253	struct ksm_stable_node *stable_node;
2254	struct folio *kfolio;
2255	unsigned int checksum;
2256	int err;
2257	bool max_page_sharing_bypass = false;
2258
2259	stable_node = folio_stable_node(folio);
2260	if (stable_node) {
2261		if (stable_node->head != &migrate_nodes &&
2262		    get_kpfn_nid(READ_ONCE(stable_node->kpfn)) !=
2263		    NUMA(stable_node->nid)) {
2264			stable_node_dup_del(stable_node);
2265			stable_node->head = &migrate_nodes;
2266			list_add(&stable_node->list, stable_node->head);
2267		}
2268		if (stable_node->head != &migrate_nodes &&
2269		    rmap_item->head == stable_node)
2270			return;
2271		/*
2272		 * If it's a KSM fork, allow it to go over the sharing limit
2273		 * without warnings.
2274		 */
2275		if (!is_page_sharing_candidate(stable_node))
2276			max_page_sharing_bypass = true;
2277	} else {
2278		remove_rmap_item_from_tree(rmap_item);
2279
2280		/*
2281		 * If the hash value of the page has changed from the last time
2282		 * we calculated it, this page is changing frequently: therefore we
2283		 * don't want to insert it in the unstable tree, and we don't want
2284		 * to waste our time searching for something identical to it there.
2285		 */
2286		checksum = calc_checksum(page);
2287		if (rmap_item->oldchecksum != checksum) {
2288			rmap_item->oldchecksum = checksum;
2289			return;
2290		}
2291
2292		if (!try_to_merge_with_zero_page(rmap_item, page))
2293			return;
2294	}
2295
2296	/* Start by searching for the folio in the stable tree */
2297	kfolio = stable_tree_search(page);
2298	if (kfolio == folio && rmap_item->head == stable_node) {
2299		folio_put(kfolio);
2300		return;
2301	}
2302
2303	remove_rmap_item_from_tree(rmap_item);
2304
2305	if (kfolio) {
2306		if (kfolio == ERR_PTR(-EBUSY))
2307			return;
2308
2309		err = try_to_merge_with_ksm_page(rmap_item, page, &kfolio->page);
2310		if (!err) {
2311			/*
2312			 * The page was successfully merged:
2313			 * add its rmap_item to the stable tree.
2314			 */
2315			folio_lock(kfolio);
2316			stable_tree_append(rmap_item, folio_stable_node(kfolio),
2317					   max_page_sharing_bypass);
2318			folio_unlock(kfolio);
2319		}
2320		folio_put(kfolio);
2321		return;
2322	}
2323
2324	tree_rmap_item =
2325		unstable_tree_search_insert(rmap_item, page, &tree_page);
2326	if (tree_rmap_item) {
2327		bool split;
2328
2329		kfolio = try_to_merge_two_pages(rmap_item, page,
2330						tree_rmap_item, tree_page);
2331		/*
2332		 * If both pages we tried to merge belong to the same compound
2333		 * page, then we actually ended up increasing the reference
2334		 * count of the same compound page twice, and split_huge_page
2335		 * failed.
2336		 * Here we set a flag if that happened, and we use it later to
2337		 * try split_huge_page again. Since we call put_page right
2338		 * afterwards, the reference count will be correct and
2339		 * split_huge_page should succeed.
2340		 */
2341		split = PageTransCompound(page)
2342			&& compound_head(page) == compound_head(tree_page);
2343		put_page(tree_page);
2344		if (kfolio) {
2345			/*
2346			 * The pages were successfully merged: insert new
2347			 * node in the stable tree and add both rmap_items.
2348			 */
2349			folio_lock(kfolio);
2350			stable_node = stable_tree_insert(kfolio);
2351			if (stable_node) {
2352				stable_tree_append(tree_rmap_item, stable_node,
2353						   false);
2354				stable_tree_append(rmap_item, stable_node,
2355						   false);
2356			}
2357			folio_unlock(kfolio);
2358
2359			/*
2360			 * If we fail to insert the page into the stable tree,
2361			 * we will have 2 virtual addresses that are pointing
2362			 * to a ksm page left outside the stable tree,
2363			 * in which case we need to break_cow on both.
2364			 */
2365			if (!stable_node) {
2366				break_cow(tree_rmap_item);
2367				break_cow(rmap_item);
2368			}
2369		} else if (split) {
2370			/*
2371			 * We are here if we tried to merge two pages and
2372			 * failed because they both belonged to the same
2373			 * compound page. We will split the page now, but no
2374			 * merging will take place.
2375			 * We do not want to add the cost of a full lock; if
2376			 * the page is locked, it is better to skip it and
2377			 * perhaps try again later.
2378			 */
2379			if (!folio_trylock(folio))
2380				return;
2381			split_huge_page(page);
2382			folio = page_folio(page);
2383			folio_unlock(folio);
2384		}
2385	}
2386}
2387
2388static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot,
2389					    struct ksm_rmap_item **rmap_list,
2390					    unsigned long addr)
2391{
2392	struct ksm_rmap_item *rmap_item;
2393
2394	while (*rmap_list) {
2395		rmap_item = *rmap_list;
2396		if ((rmap_item->address & PAGE_MASK) == addr)
2397			return rmap_item;
2398		if (rmap_item->address > addr)
2399			break;
2400		*rmap_list = rmap_item->rmap_list;
2401		remove_rmap_item_from_tree(rmap_item);
2402		free_rmap_item(rmap_item);
2403	}
2404
2405	rmap_item = alloc_rmap_item();
2406	if (rmap_item) {
2407		/* It has already been zeroed */
2408		rmap_item->mm = mm_slot->slot.mm;
2409		rmap_item->mm->ksm_rmap_items++;
2410		rmap_item->address = addr;
2411		rmap_item->rmap_list = *rmap_list;
2412		*rmap_list = rmap_item;
2413	}
2414	return rmap_item;
2415}
2416
2417/*
2418 * Calculate skip age for the ksm page age. The age determines how often
2419 * de-duplicating has already been tried unsuccessfully. If the age is
2420 * smaller, the scanning of this page is skipped for less scans.
2421 *
2422 * @age: rmap_item age of page
2423 */
2424static unsigned int skip_age(rmap_age_t age)
2425{
2426	if (age <= 3)
2427		return 1;
2428	if (age <= 5)
2429		return 2;
2430	if (age <= 8)
2431		return 4;
2432
2433	return 8;
2434}
2435
2436/*
2437 * Determines if a page should be skipped for the current scan.
2438 *
2439 * @folio: folio containing the page to check
2440 * @rmap_item: associated rmap_item of page
2441 */
2442static bool should_skip_rmap_item(struct folio *folio,
2443				  struct ksm_rmap_item *rmap_item)
2444{
2445	rmap_age_t age;
2446
2447	if (!ksm_smart_scan)
2448		return false;
2449
2450	/*
2451	 * Never skip pages that are already KSM; pages cmp_and_merge_page()
2452	 * will essentially ignore them, but we still have to process them
2453	 * properly.
2454	 */
2455	if (folio_test_ksm(folio))
2456		return false;
2457
2458	age = rmap_item->age;
2459	if (age != U8_MAX)
2460		rmap_item->age++;
2461
2462	/*
2463	 * Smaller ages are not skipped, they need to get a chance to go
2464	 * through the different phases of the KSM merging.
2465	 */
2466	if (age < 3)
2467		return false;
2468
2469	/*
2470	 * Are we still allowed to skip? If not, then don't skip it
2471	 * and determine how much more often we are allowed to skip next.
2472	 */
2473	if (!rmap_item->remaining_skips) {
2474		rmap_item->remaining_skips = skip_age(age);
2475		return false;
2476	}
2477
2478	/* Skip this page */
2479	ksm_pages_skipped++;
2480	rmap_item->remaining_skips--;
2481	remove_rmap_item_from_tree(rmap_item);
2482	return true;
2483}
2484
2485struct ksm_next_page_arg {
2486	struct folio *folio;
2487	struct page *page;
2488	unsigned long addr;
2489};
2490
2491static int ksm_next_page_pmd_entry(pmd_t *pmdp, unsigned long addr, unsigned long end,
2492		struct mm_walk *walk)
2493{
2494	struct ksm_next_page_arg *private = walk->private;
2495	struct vm_area_struct *vma = walk->vma;
2496	pte_t *start_ptep = NULL, *ptep, pte;
2497	struct mm_struct *mm = walk->mm;
2498	struct folio *folio;
2499	struct page *page;
2500	spinlock_t *ptl;
2501	pmd_t pmd;
2502
2503	if (ksm_test_exit(mm))
2504		return 0;
2505
2506	cond_resched();
2507
2508	pmd = pmdp_get_lockless(pmdp);
2509	if (!pmd_present(pmd))
2510		return 0;
2511
2512	if (IS_ENABLED(CONFIG_TRANSPARENT_HUGEPAGE) && pmd_leaf(pmd)) {
2513		ptl = pmd_lock(mm, pmdp);
2514		pmd = pmdp_get(pmdp);
2515
2516		if (!pmd_present(pmd)) {
2517			goto not_found_unlock;
2518		} else if (pmd_leaf(pmd)) {
2519			page = vm_normal_page_pmd(vma, addr, pmd);
2520			if (!page)
2521				goto not_found_unlock;
2522			folio = page_folio(page);
2523
2524			if (folio_is_zone_device(folio) || !folio_test_anon(folio))
2525				goto not_found_unlock;
2526
2527			page += ((addr & (PMD_SIZE - 1)) >> PAGE_SHIFT);
2528			goto found_unlock;
2529		}
2530		spin_unlock(ptl);
2531	}
2532
2533	start_ptep = pte_offset_map_lock(mm, pmdp, addr, &ptl);
2534	if (!start_ptep)
2535		return 0;
2536
2537	for (ptep = start_ptep; addr < end; ptep++, addr += PAGE_SIZE) {
2538		pte = ptep_get(ptep);
2539
2540		if (!pte_present(pte))
2541			continue;
2542
2543		page = vm_normal_page(vma, addr, pte);
2544		if (!page)
2545			continue;
2546		folio = page_folio(page);
2547
2548		if (folio_is_zone_device(folio) || !folio_test_anon(folio))
2549			continue;
2550		goto found_unlock;
2551	}
2552
2553not_found_unlock:
2554	spin_unlock(ptl);
2555	if (start_ptep)
2556		pte_unmap(start_ptep);
2557	return 0;
2558found_unlock:
2559	folio_get(folio);
2560	spin_unlock(ptl);
2561	if (start_ptep)
2562		pte_unmap(start_ptep);
2563	private->page = page;
2564	private->folio = folio;
2565	private->addr = addr;
2566	return 1;
2567}
2568
2569static struct mm_walk_ops ksm_next_page_ops = {
2570	.pmd_entry = ksm_next_page_pmd_entry,
2571	.walk_lock = PGWALK_RDLOCK,
2572};
2573
2574static struct ksm_rmap_item *scan_get_next_rmap_item(struct page **page)
2575{
2576	struct mm_struct *mm;
2577	struct ksm_mm_slot *mm_slot;
2578	struct mm_slot *slot;
2579	struct vm_area_struct *vma;
2580	struct ksm_rmap_item *rmap_item;
2581	struct vma_iterator vmi;
2582	int nid;
2583
2584	if (list_empty(&ksm_mm_head.slot.mm_node))
2585		return NULL;
2586
2587	mm_slot = ksm_scan.mm_slot;
2588	if (mm_slot == &ksm_mm_head) {
2589		advisor_start_scan();
2590		trace_ksm_start_scan(ksm_scan.seqnr, ksm_rmap_items);
2591
2592		/*
2593		 * A number of pages can hang around indefinitely in per-cpu
2594		 * LRU cache, raised page count preventing write_protect_page
2595		 * from merging them.  Though it doesn't really matter much,
2596		 * it is puzzling to see some stuck in pages_volatile until
2597		 * other activity jostles them out, and they also prevented
2598		 * LTP's KSM test from succeeding deterministically; so drain
2599		 * them here (here rather than on entry to ksm_do_scan(),
2600		 * so we don't IPI too often when pages_to_scan is set low).
2601		 */
2602		lru_add_drain_all();
2603
2604		/*
2605		 * Whereas stale stable_nodes on the stable_tree itself
2606		 * get pruned in the regular course of stable_tree_search(),
2607		 * those moved out to the migrate_nodes list can accumulate:
2608		 * so prune them once before each full scan.
2609		 */
2610		if (!ksm_merge_across_nodes) {
2611			struct ksm_stable_node *stable_node, *next;
2612			struct folio *folio;
2613
2614			list_for_each_entry_safe(stable_node, next,
2615						 &migrate_nodes, list) {
2616				folio = ksm_get_folio(stable_node,
2617						      KSM_GET_FOLIO_NOLOCK);
2618				if (folio)
2619					folio_put(folio);
2620				cond_resched();
2621			}
2622		}
2623
2624		for (nid = 0; nid < ksm_nr_node_ids; nid++)
2625			root_unstable_tree[nid] = RB_ROOT;
2626
2627		spin_lock(&ksm_mmlist_lock);
2628		slot = list_entry(mm_slot->slot.mm_node.next,
2629				  struct mm_slot, mm_node);
2630		mm_slot = mm_slot_entry(slot, struct ksm_mm_slot, slot);
2631		ksm_scan.mm_slot = mm_slot;
2632		spin_unlock(&ksm_mmlist_lock);
2633		/*
2634		 * Although we tested list_empty() above, a racing __ksm_exit
2635		 * of the last mm on the list may have removed it since then.
2636		 */
2637		if (mm_slot == &ksm_mm_head)
2638			return NULL;
2639next_mm:
2640		ksm_scan.address = 0;
2641		ksm_scan.rmap_list = &mm_slot->rmap_list;
2642	}
2643
2644	slot = &mm_slot->slot;
2645	mm = slot->mm;
2646	vma_iter_init(&vmi, mm, ksm_scan.address);
2647
2648	mmap_read_lock(mm);
2649	if (ksm_test_exit(mm))
2650		goto no_vmas;
2651
2652	for_each_vma(vmi, vma) {
2653		if (!(vma->vm_flags & VM_MERGEABLE))
2654			continue;
2655		if (ksm_scan.address < vma->vm_start)
2656			ksm_scan.address = vma->vm_start;
2657		if (!vma->anon_vma)
2658			ksm_scan.address = vma->vm_end;
2659
2660		while (ksm_scan.address < vma->vm_end) {
2661			struct ksm_next_page_arg ksm_next_page_arg;
2662			struct page *tmp_page = NULL;
2663			struct folio *folio;
2664
2665			if (ksm_test_exit(mm))
2666				break;
2667
2668			int found;
2669
2670			found = walk_page_range_vma(vma, ksm_scan.address,
2671						    vma->vm_end,
2672						    &ksm_next_page_ops,
2673						    &ksm_next_page_arg);
2674
2675			if (found > 0) {
2676				folio = ksm_next_page_arg.folio;
2677				tmp_page = ksm_next_page_arg.page;
2678				ksm_scan.address = ksm_next_page_arg.addr;
2679			} else {
2680				VM_WARN_ON_ONCE(found < 0);
2681				ksm_scan.address = vma->vm_end - PAGE_SIZE;
2682			}
2683
2684			if (tmp_page) {
2685				flush_anon_page(vma, tmp_page, ksm_scan.address);
2686				flush_dcache_page(tmp_page);
2687				rmap_item = get_next_rmap_item(mm_slot,
2688					ksm_scan.rmap_list, ksm_scan.address);
2689				if (rmap_item) {
2690					ksm_scan.rmap_list =
2691							&rmap_item->rmap_list;
2692
2693					if (should_skip_rmap_item(folio, rmap_item)) {
2694						folio_put(folio);
2695						goto next_page;
2696					}
2697
2698					ksm_scan.address += PAGE_SIZE;
2699					*page = tmp_page;
2700				} else {
2701					folio_put(folio);
2702				}
2703				mmap_read_unlock(mm);
2704				return rmap_item;
2705			}
2706next_page:
2707			ksm_scan.address += PAGE_SIZE;
2708			cond_resched();
2709		}
2710	}
2711
2712	if (ksm_test_exit(mm)) {
2713no_vmas:
2714		ksm_scan.address = 0;
2715		ksm_scan.rmap_list = &mm_slot->rmap_list;
2716	}
2717	/*
2718	 * Nuke all the rmap_items that are above this current rmap:
2719	 * because there were no VM_MERGEABLE vmas with such addresses.
2720	 */
2721	remove_trailing_rmap_items(ksm_scan.rmap_list);
2722
2723	spin_lock(&ksm_mmlist_lock);
2724	slot = list_entry(mm_slot->slot.mm_node.next,
2725			  struct mm_slot, mm_node);
2726	ksm_scan.mm_slot = mm_slot_entry(slot, struct ksm_mm_slot, slot);
2727	if (ksm_scan.address == 0) {
2728		/*
2729		 * We've completed a full scan of all vmas, holding mmap_lock
2730		 * throughout, and found no VM_MERGEABLE: so do the same as
2731		 * __ksm_exit does to remove this mm from all our lists now.
2732		 * This applies either when cleaning up after __ksm_exit
2733		 * (but beware: we can reach here even before __ksm_exit),
2734		 * or when all VM_MERGEABLE areas have been unmapped (and
2735		 * mmap_lock then protects against race with MADV_MERGEABLE).
2736		 */
2737		hash_del(&mm_slot->slot.hash);
2738		list_del(&mm_slot->slot.mm_node);
2739		spin_unlock(&ksm_mmlist_lock);
2740
2741		mm_slot_free(mm_slot_cache, mm_slot);
2742		/*
2743		 * Only clear MMF_VM_MERGEABLE. We must not clear
2744		 * MMF_VM_MERGE_ANY, because for those MMF_VM_MERGE_ANY process,
2745		 * perhaps their mm_struct has just been added to ksm_mm_slot
2746		 * list, and its process has not yet officially started running
2747		 * or has not yet performed mmap/brk to allocate anonymous VMAS.
2748		 */
2749		mm_flags_clear(MMF_VM_MERGEABLE, mm);
2750		mmap_read_unlock(mm);
2751		mmdrop(mm);
2752	} else {
2753		mmap_read_unlock(mm);
2754		/*
2755		 * mmap_read_unlock(mm) first because after
2756		 * spin_unlock(&ksm_mmlist_lock) run, the "mm" may
2757		 * already have been freed under us by __ksm_exit()
2758		 * because the "mm_slot" is still hashed and
2759		 * ksm_scan.mm_slot doesn't point to it anymore.
2760		 */
2761		spin_unlock(&ksm_mmlist_lock);
2762	}
2763
2764	/* Repeat until we've completed scanning the whole list */
2765	mm_slot = ksm_scan.mm_slot;
2766	if (mm_slot != &ksm_mm_head)
2767		goto next_mm;
2768
2769	advisor_stop_scan();
2770
2771	trace_ksm_stop_scan(ksm_scan.seqnr, ksm_rmap_items);
2772	ksm_scan.seqnr++;
2773	return NULL;
2774}
2775
2776/**
2777 * ksm_do_scan  - the ksm scanner main worker function.
2778 * @scan_npages:  number of pages we want to scan before we return.
2779 */
2780static void ksm_do_scan(unsigned int scan_npages)
2781{
2782	struct ksm_rmap_item *rmap_item;
2783	struct page *page;
2784
2785	while (scan_npages-- && likely(!freezing(current))) {
2786		cond_resched();
2787		rmap_item = scan_get_next_rmap_item(&page);
2788		if (!rmap_item)
2789			return;
2790		cmp_and_merge_page(page, rmap_item);
2791		put_page(page);
2792		ksm_pages_scanned++;
2793	}
2794}
2795
2796static int ksmd_should_run(void)
2797{
2798	return (ksm_run & KSM_RUN_MERGE) && !list_empty(&ksm_mm_head.slot.mm_node);
2799}
2800
2801static int ksm_scan_thread(void *nothing)
2802{
2803	unsigned int sleep_ms;
2804
2805	set_freezable();
2806	set_user_nice(current, 5);
2807
2808	while (!kthread_should_stop()) {
2809		mutex_lock(&ksm_thread_mutex);
2810		wait_while_offlining();
2811		if (ksmd_should_run())
2812			ksm_do_scan(ksm_thread_pages_to_scan);
2813		mutex_unlock(&ksm_thread_mutex);
2814
2815		if (ksmd_should_run()) {
2816			sleep_ms = READ_ONCE(ksm_thread_sleep_millisecs);
2817			wait_event_freezable_timeout(ksm_iter_wait,
2818				sleep_ms != READ_ONCE(ksm_thread_sleep_millisecs),
2819				msecs_to_jiffies(sleep_ms));
2820		} else {
2821			wait_event_freezable(ksm_thread_wait,
2822				ksmd_should_run() || kthread_should_stop());
2823		}
2824	}
2825	return 0;
2826}
2827
2828static bool __ksm_should_add_vma(const struct file *file, vm_flags_t vm_flags)
2829{
2830	if (vm_flags & VM_MERGEABLE)
2831		return false;
2832
2833	return ksm_compatible(file, vm_flags);
2834}
2835
2836static void __ksm_add_vma(struct vm_area_struct *vma)
2837{
2838	if (__ksm_should_add_vma(vma->vm_file, vma->vm_flags))
2839		vm_flags_set(vma, VM_MERGEABLE);
2840}
2841
2842static int __ksm_del_vma(struct vm_area_struct *vma)
2843{
2844	int err;
2845
2846	if (!(vma->vm_flags & VM_MERGEABLE))
2847		return 0;
2848
2849	if (vma->anon_vma) {
2850		err = break_ksm(vma, vma->vm_start, vma->vm_end, true);
2851		if (err)
2852			return err;
2853	}
2854
2855	vm_flags_clear(vma, VM_MERGEABLE);
2856	return 0;
2857}
2858/**
2859 * ksm_vma_flags - Update VMA flags to mark as mergeable if compatible
2860 *
2861 * @mm:       Proposed VMA's mm_struct
2862 * @file:     Proposed VMA's file-backed mapping, if any.
2863 * @vm_flags: Proposed VMA"s flags.
2864 *
2865 * Returns: @vm_flags possibly updated to mark mergeable.
2866 */
2867vm_flags_t ksm_vma_flags(struct mm_struct *mm, const struct file *file,
2868			 vm_flags_t vm_flags)
2869{
2870	if (mm_flags_test(MMF_VM_MERGE_ANY, mm) &&
2871	    __ksm_should_add_vma(file, vm_flags)) {
2872		vm_flags |= VM_MERGEABLE;
2873		/*
2874		 * Generally, the flags here always include MMF_VM_MERGEABLE.
2875		 * However, in rare cases, this flag may be cleared by ksmd who
2876		 * scans a cycle without finding any mergeable vma.
2877		 */
2878		if (unlikely(!mm_flags_test(MMF_VM_MERGEABLE, mm)))
2879			__ksm_enter(mm);
2880	}
2881
2882	return vm_flags;
2883}
2884
2885static void ksm_add_vmas(struct mm_struct *mm)
2886{
2887	struct vm_area_struct *vma;
2888
2889	VMA_ITERATOR(vmi, mm, 0);
2890	for_each_vma(vmi, vma)
2891		__ksm_add_vma(vma);
2892}
2893
2894static int ksm_del_vmas(struct mm_struct *mm)
2895{
2896	struct vm_area_struct *vma;
2897	int err;
2898
2899	VMA_ITERATOR(vmi, mm, 0);
2900	for_each_vma(vmi, vma) {
2901		err = __ksm_del_vma(vma);
2902		if (err)
2903			return err;
2904	}
2905	return 0;
2906}
2907
2908/**
2909 * ksm_enable_merge_any - Add mm to mm ksm list and enable merging on all
2910 *                        compatible VMA's
2911 *
2912 * @mm:  Pointer to mm
2913 *
2914 * Returns 0 on success, otherwise error code
2915 */
2916int ksm_enable_merge_any(struct mm_struct *mm)
2917{
2918	int err;
2919
2920	if (mm_flags_test(MMF_VM_MERGE_ANY, mm))
2921		return 0;
2922
2923	if (!mm_flags_test(MMF_VM_MERGEABLE, mm)) {
2924		err = __ksm_enter(mm);
2925		if (err)
2926			return err;
2927	}
2928
2929	mm_flags_set(MMF_VM_MERGE_ANY, mm);
2930	ksm_add_vmas(mm);
2931
2932	return 0;
2933}
2934
2935/**
2936 * ksm_disable_merge_any - Disable merging on all compatible VMA's of the mm,
2937 *			   previously enabled via ksm_enable_merge_any().
2938 *
2939 * Disabling merging implies unmerging any merged pages, like setting
2940 * MADV_UNMERGEABLE would. If unmerging fails, the whole operation fails and
2941 * merging on all compatible VMA's remains enabled.
2942 *
2943 * @mm: Pointer to mm
2944 *
2945 * Returns 0 on success, otherwise error code
2946 */
2947int ksm_disable_merge_any(struct mm_struct *mm)
2948{
2949	int err;
2950
2951	if (!mm_flags_test(MMF_VM_MERGE_ANY, mm))
2952		return 0;
2953
2954	err = ksm_del_vmas(mm);
2955	if (err) {
2956		ksm_add_vmas(mm);
2957		return err;
2958	}
2959
2960	mm_flags_clear(MMF_VM_MERGE_ANY, mm);
2961	return 0;
2962}
2963
2964int ksm_disable(struct mm_struct *mm)
2965{
2966	mmap_assert_write_locked(mm);
2967
2968	if (!mm_flags_test(MMF_VM_MERGEABLE, mm))
2969		return 0;
2970	if (mm_flags_test(MMF_VM_MERGE_ANY, mm))
2971		return ksm_disable_merge_any(mm);
2972	return ksm_del_vmas(mm);
2973}
2974
2975int ksm_madvise(struct vm_area_struct *vma, unsigned long start,
2976		unsigned long end, int advice, vm_flags_t *vm_flags)
2977{
2978	struct mm_struct *mm = vma->vm_mm;
2979	int err;
2980
2981	switch (advice) {
2982	case MADV_MERGEABLE:
2983		if (vma->vm_flags & VM_MERGEABLE)
2984			return 0;
2985		if (!vma_ksm_compatible(vma))
2986			return 0;
2987
2988		if (!mm_flags_test(MMF_VM_MERGEABLE, mm)) {
2989			err = __ksm_enter(mm);
2990			if (err)
2991				return err;
2992		}
2993
2994		*vm_flags |= VM_MERGEABLE;
2995		break;
2996
2997	case MADV_UNMERGEABLE:
2998		if (!(*vm_flags & VM_MERGEABLE))
2999			return 0;		/* just ignore the advice */
3000
3001		if (vma->anon_vma) {
3002			err = break_ksm(vma, start, end, true);
3003			if (err)
3004				return err;
3005		}
3006
3007		*vm_flags &= ~VM_MERGEABLE;
3008		break;
3009	}
3010
3011	return 0;
3012}
3013EXPORT_SYMBOL_GPL(ksm_madvise);
3014
3015int __ksm_enter(struct mm_struct *mm)
3016{
3017	struct ksm_mm_slot *mm_slot;
3018	struct mm_slot *slot;
3019	int needs_wakeup;
3020
3021	mm_slot = mm_slot_alloc(mm_slot_cache);
3022	if (!mm_slot)
3023		return -ENOMEM;
3024
3025	slot = &mm_slot->slot;
3026
3027	/* Check ksm_run too?  Would need tighter locking */
3028	needs_wakeup = list_empty(&ksm_mm_head.slot.mm_node);
3029
3030	spin_lock(&ksm_mmlist_lock);
3031	mm_slot_insert(mm_slots_hash, mm, slot);
3032	/*
3033	 * When KSM_RUN_MERGE (or KSM_RUN_STOP),
3034	 * insert just behind the scanning cursor, to let the area settle
3035	 * down a little; when fork is followed by immediate exec, we don't
3036	 * want ksmd to waste time setting up and tearing down an rmap_list.
3037	 *
3038	 * But when KSM_RUN_UNMERGE, it's important to insert ahead of its
3039	 * scanning cursor, otherwise KSM pages in newly forked mms will be
3040	 * missed: then we might as well insert at the end of the list.
3041	 */
3042	if (ksm_run & KSM_RUN_UNMERGE)
3043		list_add_tail(&slot->mm_node, &ksm_mm_head.slot.mm_node);
3044	else
3045		list_add_tail(&slot->mm_node, &ksm_scan.mm_slot->slot.mm_node);
3046	spin_unlock(&ksm_mmlist_lock);
3047
3048	mm_flags_set(MMF_VM_MERGEABLE, mm);
3049	mmgrab(mm);
3050
3051	if (needs_wakeup)
3052		wake_up_interruptible(&ksm_thread_wait);
3053
3054	trace_ksm_enter(mm);
3055	return 0;
3056}
3057
3058void __ksm_exit(struct mm_struct *mm)
3059{
3060	struct ksm_mm_slot *mm_slot = NULL;
3061	struct mm_slot *slot;
3062	int easy_to_free = 0;
3063
3064	/*
3065	 * This process is exiting: if it's straightforward (as is the
3066	 * case when ksmd was never running), free mm_slot immediately.
3067	 * But if it's at the cursor or has rmap_items linked to it, use
3068	 * mmap_lock to synchronize with any break_cows before pagetables
3069	 * are freed, and leave the mm_slot on the list for ksmd to free.
3070	 * Beware: ksm may already have noticed it exiting and freed the slot.
3071	 */
3072
3073	spin_lock(&ksm_mmlist_lock);
3074	slot = mm_slot_lookup(mm_slots_hash, mm);
3075	if (!slot)
3076		goto unlock;
3077	mm_slot = mm_slot_entry(slot, struct ksm_mm_slot, slot);
3078	if (ksm_scan.mm_slot == mm_slot)
3079		goto unlock;
3080	if (!mm_slot->rmap_list) {
3081		hash_del(&slot->hash);
3082		list_del(&slot->mm_node);
3083		easy_to_free = 1;
3084	} else {
3085		list_move(&slot->mm_node,
3086			  &ksm_scan.mm_slot->slot.mm_node);
3087	}
3088unlock:
3089	spin_unlock(&ksm_mmlist_lock);
3090
3091	if (easy_to_free) {
3092		mm_slot_free(mm_slot_cache, mm_slot);
3093		mm_flags_clear(MMF_VM_MERGE_ANY, mm);
3094		mm_flags_clear(MMF_VM_MERGEABLE, mm);
3095		mmdrop(mm);
3096	} else if (mm_slot) {
3097		mmap_write_lock(mm);
3098		mmap_write_unlock(mm);
3099	}
3100
3101	trace_ksm_exit(mm);
3102}
3103
3104struct folio *ksm_might_need_to_copy(struct folio *folio,
3105			struct vm_area_struct *vma, unsigned long addr)
3106{
3107	struct page *page = folio_page(folio, 0);
3108	struct anon_vma *anon_vma = folio_anon_vma(folio);
3109	struct folio *new_folio;
3110
3111	if (folio_test_large(folio))
3112		return folio;
3113
3114	if (folio_test_ksm(folio)) {
3115		if (folio_stable_node(folio) &&
3116		    !(ksm_run & KSM_RUN_UNMERGE))
3117			return folio;	/* no need to copy it */
3118	} else if (!anon_vma) {
3119		return folio;		/* no need to copy it */
3120	} else if (folio->index == linear_page_index(vma, addr) &&
3121			anon_vma->root == vma->anon_vma->root) {
3122		return folio;		/* still no need to copy it */
3123	}
3124	if (PageHWPoison(page))
3125		return ERR_PTR(-EHWPOISON);
3126	if (!folio_test_uptodate(folio))
3127		return folio;		/* let do_swap_page report the error */
3128
3129	new_folio = vma_alloc_folio(GFP_HIGHUSER_MOVABLE, 0, vma, addr);
3130	if (new_folio &&
3131	    mem_cgroup_charge(new_folio, vma->vm_mm, GFP_KERNEL)) {
3132		folio_put(new_folio);
3133		new_folio = NULL;
3134	}
3135	if (new_folio) {
3136		if (copy_mc_user_highpage(folio_page(new_folio, 0), page,
3137								addr, vma)) {
3138			folio_put(new_folio);
3139			return ERR_PTR(-EHWPOISON);
3140		}
3141		folio_set_dirty(new_folio);
3142		__folio_mark_uptodate(new_folio);
3143		__folio_set_locked(new_folio);
3144#ifdef CONFIG_SWAP
3145		count_vm_event(KSM_SWPIN_COPY);
3146#endif
3147	}
3148
3149	return new_folio;
3150}
3151
3152void rmap_walk_ksm(struct folio *folio, struct rmap_walk_control *rwc)
3153{
3154	struct ksm_stable_node *stable_node;
3155	struct ksm_rmap_item *rmap_item;
3156	int search_new_forks = 0;
3157
3158	VM_BUG_ON_FOLIO(!folio_test_ksm(folio), folio);
3159
3160	/*
3161	 * Rely on the page lock to protect against concurrent modifications
3162	 * to that page's node of the stable tree.
3163	 */
3164	VM_BUG_ON_FOLIO(!folio_test_locked(folio), folio);
3165
3166	stable_node = folio_stable_node(folio);
3167	if (!stable_node)
3168		return;
3169again:
3170	hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) {
3171		struct anon_vma *anon_vma = rmap_item->anon_vma;
3172		struct anon_vma_chain *vmac;
3173		struct vm_area_struct *vma;
3174
3175		cond_resched();
3176		if (!anon_vma_trylock_read(anon_vma)) {
3177			if (rwc->try_lock) {
3178				rwc->contended = true;
3179				return;
3180			}
3181			anon_vma_lock_read(anon_vma);
3182		}
3183		anon_vma_interval_tree_foreach(vmac, &anon_vma->rb_root,
3184					       0, ULONG_MAX) {
3185			unsigned long addr;
3186
3187			cond_resched();
3188			vma = vmac->vma;
3189
3190			/* Ignore the stable/unstable/sqnr flags */
3191			addr = rmap_item->address & PAGE_MASK;
3192
3193			if (addr < vma->vm_start || addr >= vma->vm_end)
3194				continue;
3195			/*
3196			 * Initially we examine only the vma which covers this
3197			 * rmap_item; but later, if there is still work to do,
3198			 * we examine covering vmas in other mms: in case they
3199			 * were forked from the original since ksmd passed.
3200			 */
3201			if ((rmap_item->mm == vma->vm_mm) == search_new_forks)
3202				continue;
3203
3204			if (rwc->invalid_vma && rwc->invalid_vma(vma, rwc->arg))
3205				continue;
3206
3207			if (!rwc->rmap_one(folio, vma, addr, rwc->arg)) {
3208				anon_vma_unlock_read(anon_vma);
3209				return;
3210			}
3211			if (rwc->done && rwc->done(folio)) {
3212				anon_vma_unlock_read(anon_vma);
3213				return;
3214			}
3215		}
3216		anon_vma_unlock_read(anon_vma);
3217	}
3218	if (!search_new_forks++)
3219		goto again;
3220}
3221
3222#ifdef CONFIG_MEMORY_FAILURE
3223/*
3224 * Collect processes when the error hit an ksm page.
3225 */
3226void collect_procs_ksm(const struct folio *folio, const struct page *page,
3227		struct list_head *to_kill, int force_early)
3228{
3229	struct ksm_stable_node *stable_node;
3230	struct ksm_rmap_item *rmap_item;
3231	struct vm_area_struct *vma;
3232	struct task_struct *tsk;
3233
3234	stable_node = folio_stable_node(folio);
3235	if (!stable_node)
3236		return;
3237	hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) {
3238		struct anon_vma *av = rmap_item->anon_vma;
3239
3240		anon_vma_lock_read(av);
3241		rcu_read_lock();
3242		for_each_process(tsk) {
3243			struct anon_vma_chain *vmac;
3244			unsigned long addr;
3245			struct task_struct *t =
3246				task_early_kill(tsk, force_early);
3247			if (!t)
3248				continue;
3249			anon_vma_interval_tree_foreach(vmac, &av->rb_root, 0,
3250						       ULONG_MAX)
3251			{
3252				vma = vmac->vma;
3253				if (vma->vm_mm == t->mm) {
3254					addr = rmap_item->address & PAGE_MASK;
3255					add_to_kill_ksm(t, page, vma, to_kill,
3256							addr);
3257				}
3258			}
3259		}
3260		rcu_read_unlock();
3261		anon_vma_unlock_read(av);
3262	}
3263}
3264#endif
3265
3266#ifdef CONFIG_MIGRATION
3267void folio_migrate_ksm(struct folio *newfolio, struct folio *folio)
3268{
3269	struct ksm_stable_node *stable_node;
3270
3271	VM_BUG_ON_FOLIO(!folio_test_locked(folio), folio);
3272	VM_BUG_ON_FOLIO(!folio_test_locked(newfolio), newfolio);
3273	VM_BUG_ON_FOLIO(newfolio->mapping != folio->mapping, newfolio);
3274
3275	stable_node = folio_stable_node(folio);
3276	if (stable_node) {
3277		VM_BUG_ON_FOLIO(stable_node->kpfn != folio_pfn(folio), folio);
3278		stable_node->kpfn = folio_pfn(newfolio);
3279		/*
3280		 * newfolio->mapping was set in advance; now we need smp_wmb()
3281		 * to make sure that the new stable_node->kpfn is visible
3282		 * to ksm_get_folio() before it can see that folio->mapping
3283		 * has gone stale (or that the swapcache flag has been cleared).
3284		 */
3285		smp_wmb();
3286		folio_set_stable_node(folio, NULL);
3287	}
3288}
3289#endif /* CONFIG_MIGRATION */
3290
3291#ifdef CONFIG_MEMORY_HOTREMOVE
3292static void wait_while_offlining(void)
3293{
3294	while (ksm_run & KSM_RUN_OFFLINE) {
3295		mutex_unlock(&ksm_thread_mutex);
3296		wait_on_bit(&ksm_run, ilog2(KSM_RUN_OFFLINE),
3297			    TASK_UNINTERRUPTIBLE);
3298		mutex_lock(&ksm_thread_mutex);
3299	}
3300}
3301
3302static bool stable_node_dup_remove_range(struct ksm_stable_node *stable_node,
3303					 unsigned long start_pfn,
3304					 unsigned long end_pfn)
3305{
3306	if (stable_node->kpfn >= start_pfn &&
3307	    stable_node->kpfn < end_pfn) {
3308		/*
3309		 * Don't ksm_get_folio, page has already gone:
3310		 * which is why we keep kpfn instead of page*
3311		 */
3312		remove_node_from_stable_tree(stable_node);
3313		return true;
3314	}
3315	return false;
3316}
3317
3318static bool stable_node_chain_remove_range(struct ksm_stable_node *stable_node,
3319					   unsigned long start_pfn,
3320					   unsigned long end_pfn,
3321					   struct rb_root *root)
3322{
3323	struct ksm_stable_node *dup;
3324	struct hlist_node *hlist_safe;
3325
3326	if (!is_stable_node_chain(stable_node)) {
3327		VM_BUG_ON(is_stable_node_dup(stable_node));
3328		return stable_node_dup_remove_range(stable_node, start_pfn,
3329						    end_pfn);
3330	}
3331
3332	hlist_for_each_entry_safe(dup, hlist_safe,
3333				  &stable_node->hlist, hlist_dup) {
3334		VM_BUG_ON(!is_stable_node_dup(dup));
3335		stable_node_dup_remove_range(dup, start_pfn, end_pfn);
3336	}
3337	if (hlist_empty(&stable_node->hlist)) {
3338		free_stable_node_chain(stable_node, root);
3339		return true; /* notify caller that tree was rebalanced */
3340	} else
3341		return false;
3342}
3343
3344static void ksm_check_stable_tree(unsigned long start_pfn,
3345				  unsigned long end_pfn)
3346{
3347	struct ksm_stable_node *stable_node, *next;
3348	struct rb_node *node;
3349	int nid;
3350
3351	for (nid = 0; nid < ksm_nr_node_ids; nid++) {
3352		node = rb_first(root_stable_tree + nid);
3353		while (node) {
3354			stable_node = rb_entry(node, struct ksm_stable_node, node);
3355			if (stable_node_chain_remove_range(stable_node,
3356							   start_pfn, end_pfn,
3357							   root_stable_tree +
3358							   nid))
3359				node = rb_first(root_stable_tree + nid);
3360			else
3361				node = rb_next(node);
3362			cond_resched();
3363		}
3364	}
3365	list_for_each_entry_safe(stable_node, next, &migrate_nodes, list) {
3366		if (stable_node->kpfn >= start_pfn &&
3367		    stable_node->kpfn < end_pfn)
3368			remove_node_from_stable_tree(stable_node);
3369		cond_resched();
3370	}
3371}
3372
3373static int ksm_memory_callback(struct notifier_block *self,
3374			       unsigned long action, void *arg)
3375{
3376	struct memory_notify *mn = arg;
3377
3378	switch (action) {
3379	case MEM_GOING_OFFLINE:
3380		/*
3381		 * Prevent ksm_do_scan(), unmerge_and_remove_all_rmap_items()
3382		 * and remove_all_stable_nodes() while memory is going offline:
3383		 * it is unsafe for them to touch the stable tree at this time.
3384		 * But break_ksm(), rmap lookups and other entry points
3385		 * which do not need the ksm_thread_mutex are all safe.
3386		 */
3387		mutex_lock(&ksm_thread_mutex);
3388		ksm_run |= KSM_RUN_OFFLINE;
3389		mutex_unlock(&ksm_thread_mutex);
3390		break;
3391
3392	case MEM_OFFLINE:
3393		/*
3394		 * Most of the work is done by page migration; but there might
3395		 * be a few stable_nodes left over, still pointing to struct
3396		 * pages which have been offlined: prune those from the tree,
3397		 * otherwise ksm_get_folio() might later try to access a
3398		 * non-existent struct page.
3399		 */
3400		ksm_check_stable_tree(mn->start_pfn,
3401				      mn->start_pfn + mn->nr_pages);
3402		fallthrough;
3403	case MEM_CANCEL_OFFLINE:
3404		mutex_lock(&ksm_thread_mutex);
3405		ksm_run &= ~KSM_RUN_OFFLINE;
3406		mutex_unlock(&ksm_thread_mutex);
3407
3408		smp_mb();	/* wake_up_bit advises this */
3409		wake_up_bit(&ksm_run, ilog2(KSM_RUN_OFFLINE));
3410		break;
3411	}
3412	return NOTIFY_OK;
3413}
3414#else
3415static void wait_while_offlining(void)
3416{
3417}
3418#endif /* CONFIG_MEMORY_HOTREMOVE */
3419
3420#ifdef CONFIG_PROC_FS
3421/*
3422 * The process is mergeable only if any VMA is currently
3423 * applicable to KSM.
3424 *
3425 * The mmap lock must be held in read mode.
3426 */
3427bool ksm_process_mergeable(struct mm_struct *mm)
3428{
3429	struct vm_area_struct *vma;
3430
3431	mmap_assert_locked(mm);
3432	VMA_ITERATOR(vmi, mm, 0);
3433	for_each_vma(vmi, vma)
3434		if (vma->vm_flags & VM_MERGEABLE)
3435			return true;
3436
3437	return false;
3438}
3439
3440long ksm_process_profit(struct mm_struct *mm)
3441{
3442	return (long)(mm->ksm_merging_pages + mm_ksm_zero_pages(mm)) * PAGE_SIZE -
3443		mm->ksm_rmap_items * sizeof(struct ksm_rmap_item);
3444}
3445#endif /* CONFIG_PROC_FS */
3446
3447#ifdef CONFIG_SYSFS
3448/*
3449 * This all compiles without CONFIG_SYSFS, but is a waste of space.
3450 */
3451
3452#define KSM_ATTR_RO(_name) \
3453	static struct kobj_attribute _name##_attr = __ATTR_RO(_name)
3454#define KSM_ATTR(_name) \
3455	static struct kobj_attribute _name##_attr = __ATTR_RW(_name)
3456
3457static ssize_t sleep_millisecs_show(struct kobject *kobj,
3458				    struct kobj_attribute *attr, char *buf)
3459{
3460	return sysfs_emit(buf, "%u\n", ksm_thread_sleep_millisecs);
3461}
3462
3463static ssize_t sleep_millisecs_store(struct kobject *kobj,
3464				     struct kobj_attribute *attr,
3465				     const char *buf, size_t count)
3466{
3467	unsigned int msecs;
3468	int err;
3469
3470	err = kstrtouint(buf, 10, &msecs);
3471	if (err)
3472		return -EINVAL;
3473
3474	ksm_thread_sleep_millisecs = msecs;
3475	wake_up_interruptible(&ksm_iter_wait);
3476
3477	return count;
3478}
3479KSM_ATTR(sleep_millisecs);
3480
3481static ssize_t pages_to_scan_show(struct kobject *kobj,
3482				  struct kobj_attribute *attr, char *buf)
3483{
3484	return sysfs_emit(buf, "%u\n", ksm_thread_pages_to_scan);
3485}
3486
3487static ssize_t pages_to_scan_store(struct kobject *kobj,
3488				   struct kobj_attribute *attr,
3489				   const char *buf, size_t count)
3490{
3491	unsigned int nr_pages;
3492	int err;
3493
3494	if (ksm_advisor != KSM_ADVISOR_NONE)
3495		return -EINVAL;
3496
3497	err = kstrtouint(buf, 10, &nr_pages);
3498	if (err)
3499		return -EINVAL;
3500
3501	ksm_thread_pages_to_scan = nr_pages;
3502
3503	return count;
3504}
3505KSM_ATTR(pages_to_scan);
3506
3507static ssize_t run_show(struct kobject *kobj, struct kobj_attribute *attr,
3508			char *buf)
3509{
3510	return sysfs_emit(buf, "%lu\n", ksm_run);
3511}
3512
3513static ssize_t run_store(struct kobject *kobj, struct kobj_attribute *attr,
3514			 const char *buf, size_t count)
3515{
3516	unsigned int flags;
3517	int err;
3518
3519	err = kstrtouint(buf, 10, &flags);
3520	if (err)
3521		return -EINVAL;
3522	if (flags > KSM_RUN_UNMERGE)
3523		return -EINVAL;
3524
3525	/*
3526	 * KSM_RUN_MERGE sets ksmd running, and 0 stops it running.
3527	 * KSM_RUN_UNMERGE stops it running and unmerges all rmap_items,
3528	 * breaking COW to free the pages_shared (but leaves mm_slots
3529	 * on the list for when ksmd may be set running again).
3530	 */
3531
3532	mutex_lock(&ksm_thread_mutex);
3533	wait_while_offlining();
3534	if (ksm_run != flags) {
3535		ksm_run = flags;
3536		if (flags & KSM_RUN_UNMERGE) {
3537			set_current_oom_origin();
3538			err = unmerge_and_remove_all_rmap_items();
3539			clear_current_oom_origin();
3540			if (err) {
3541				ksm_run = KSM_RUN_STOP;
3542				count = err;
3543			}
3544		}
3545	}
3546	mutex_unlock(&ksm_thread_mutex);
3547
3548	if (flags & KSM_RUN_MERGE)
3549		wake_up_interruptible(&ksm_thread_wait);
3550
3551	return count;
3552}
3553KSM_ATTR(run);
3554
3555#ifdef CONFIG_NUMA
3556static ssize_t merge_across_nodes_show(struct kobject *kobj,
3557				       struct kobj_attribute *attr, char *buf)
3558{
3559	return sysfs_emit(buf, "%u\n", ksm_merge_across_nodes);
3560}
3561
3562static ssize_t merge_across_nodes_store(struct kobject *kobj,
3563				   struct kobj_attribute *attr,
3564				   const char *buf, size_t count)
3565{
3566	int err;
3567	unsigned long knob;
3568
3569	err = kstrtoul(buf, 10, &knob);
3570	if (err)
3571		return err;
3572	if (knob > 1)
3573		return -EINVAL;
3574
3575	mutex_lock(&ksm_thread_mutex);
3576	wait_while_offlining();
3577	if (ksm_merge_across_nodes != knob) {
3578		if (ksm_pages_shared || remove_all_stable_nodes())
3579			err = -EBUSY;
3580		else if (root_stable_tree == one_stable_tree) {
3581			struct rb_root *buf;
3582			/*
3583			 * This is the first time that we switch away from the
3584			 * default of merging across nodes: must now allocate
3585			 * a buffer to hold as many roots as may be needed.
3586			 * Allocate stable and unstable together:
3587			 * MAXSMP NODES_SHIFT 10 will use 16kB.
3588			 */
3589			buf = kcalloc(nr_node_ids + nr_node_ids, sizeof(*buf),
3590				      GFP_KERNEL);
3591			/* Let us assume that RB_ROOT is NULL is zero */
3592			if (!buf)
3593				err = -ENOMEM;
3594			else {
3595				root_stable_tree = buf;
3596				root_unstable_tree = buf + nr_node_ids;
3597				/* Stable tree is empty but not the unstable */
3598				root_unstable_tree[0] = one_unstable_tree[0];
3599			}
3600		}
3601		if (!err) {
3602			ksm_merge_across_nodes = knob;
3603			ksm_nr_node_ids = knob ? 1 : nr_node_ids;
3604		}
3605	}
3606	mutex_unlock(&ksm_thread_mutex);
3607
3608	return err ? err : count;
3609}
3610KSM_ATTR(merge_across_nodes);
3611#endif
3612
3613static ssize_t use_zero_pages_show(struct kobject *kobj,
3614				   struct kobj_attribute *attr, char *buf)
3615{
3616	return sysfs_emit(buf, "%u\n", ksm_use_zero_pages);
3617}
3618static ssize_t use_zero_pages_store(struct kobject *kobj,
3619				   struct kobj_attribute *attr,
3620				   const char *buf, size_t count)
3621{
3622	int err;
3623	bool value;
3624
3625	err = kstrtobool(buf, &value);
3626	if (err)
3627		return -EINVAL;
3628
3629	ksm_use_zero_pages = value;
3630
3631	return count;
3632}
3633KSM_ATTR(use_zero_pages);
3634
3635static ssize_t max_page_sharing_show(struct kobject *kobj,
3636				     struct kobj_attribute *attr, char *buf)
3637{
3638	return sysfs_emit(buf, "%u\n", ksm_max_page_sharing);
3639}
3640
3641static ssize_t max_page_sharing_store(struct kobject *kobj,
3642				      struct kobj_attribute *attr,
3643				      const char *buf, size_t count)
3644{
3645	int err;
3646	int knob;
3647
3648	err = kstrtoint(buf, 10, &knob);
3649	if (err)
3650		return err;
3651	/*
3652	 * When a KSM page is created it is shared by 2 mappings. This
3653	 * being a signed comparison, it implicitly verifies it's not
3654	 * negative.
3655	 */
3656	if (knob < 2)
3657		return -EINVAL;
3658
3659	if (READ_ONCE(ksm_max_page_sharing) == knob)
3660		return count;
3661
3662	mutex_lock(&ksm_thread_mutex);
3663	wait_while_offlining();
3664	if (ksm_max_page_sharing != knob) {
3665		if (ksm_pages_shared || remove_all_stable_nodes())
3666			err = -EBUSY;
3667		else
3668			ksm_max_page_sharing = knob;
3669	}
3670	mutex_unlock(&ksm_thread_mutex);
3671
3672	return err ? err : count;
3673}
3674KSM_ATTR(max_page_sharing);
3675
3676static ssize_t pages_scanned_show(struct kobject *kobj,
3677				  struct kobj_attribute *attr, char *buf)
3678{
3679	return sysfs_emit(buf, "%lu\n", ksm_pages_scanned);
3680}
3681KSM_ATTR_RO(pages_scanned);
3682
3683static ssize_t pages_shared_show(struct kobject *kobj,
3684				 struct kobj_attribute *attr, char *buf)
3685{
3686	return sysfs_emit(buf, "%lu\n", ksm_pages_shared);
3687}
3688KSM_ATTR_RO(pages_shared);
3689
3690static ssize_t pages_sharing_show(struct kobject *kobj,
3691				  struct kobj_attribute *attr, char *buf)
3692{
3693	return sysfs_emit(buf, "%lu\n", ksm_pages_sharing);
3694}
3695KSM_ATTR_RO(pages_sharing);
3696
3697static ssize_t pages_unshared_show(struct kobject *kobj,
3698				   struct kobj_attribute *attr, char *buf)
3699{
3700	return sysfs_emit(buf, "%lu\n", ksm_pages_unshared);
3701}
3702KSM_ATTR_RO(pages_unshared);
3703
3704static ssize_t pages_volatile_show(struct kobject *kobj,
3705				   struct kobj_attribute *attr, char *buf)
3706{
3707	long ksm_pages_volatile;
3708
3709	ksm_pages_volatile = ksm_rmap_items - ksm_pages_shared
3710				- ksm_pages_sharing - ksm_pages_unshared;
3711	/*
3712	 * It was not worth any locking to calculate that statistic,
3713	 * but it might therefore sometimes be negative: conceal that.
3714	 */
3715	if (ksm_pages_volatile < 0)
3716		ksm_pages_volatile = 0;
3717	return sysfs_emit(buf, "%ld\n", ksm_pages_volatile);
3718}
3719KSM_ATTR_RO(pages_volatile);
3720
3721static ssize_t pages_skipped_show(struct kobject *kobj,
3722				  struct kobj_attribute *attr, char *buf)
3723{
3724	return sysfs_emit(buf, "%lu\n", ksm_pages_skipped);
3725}
3726KSM_ATTR_RO(pages_skipped);
3727
3728static ssize_t ksm_zero_pages_show(struct kobject *kobj,
3729				struct kobj_attribute *attr, char *buf)
3730{
3731	return sysfs_emit(buf, "%ld\n", atomic_long_read(&ksm_zero_pages));
3732}
3733KSM_ATTR_RO(ksm_zero_pages);
3734
3735static ssize_t general_profit_show(struct kobject *kobj,
3736				   struct kobj_attribute *attr, char *buf)
3737{
3738	long general_profit;
3739
3740	general_profit = (ksm_pages_sharing + atomic_long_read(&ksm_zero_pages)) * PAGE_SIZE -
3741				ksm_rmap_items * sizeof(struct ksm_rmap_item);
3742
3743	return sysfs_emit(buf, "%ld\n", general_profit);
3744}
3745KSM_ATTR_RO(general_profit);
3746
3747static ssize_t stable_node_dups_show(struct kobject *kobj,
3748				     struct kobj_attribute *attr, char *buf)
3749{
3750	return sysfs_emit(buf, "%lu\n", ksm_stable_node_dups);
3751}
3752KSM_ATTR_RO(stable_node_dups);
3753
3754static ssize_t stable_node_chains_show(struct kobject *kobj,
3755				       struct kobj_attribute *attr, char *buf)
3756{
3757	return sysfs_emit(buf, "%lu\n", ksm_stable_node_chains);
3758}
3759KSM_ATTR_RO(stable_node_chains);
3760
3761static ssize_t
3762stable_node_chains_prune_millisecs_show(struct kobject *kobj,
3763					struct kobj_attribute *attr,
3764					char *buf)
3765{
3766	return sysfs_emit(buf, "%u\n", ksm_stable_node_chains_prune_millisecs);
3767}
3768
3769static ssize_t
3770stable_node_chains_prune_millisecs_store(struct kobject *kobj,
3771					 struct kobj_attribute *attr,
3772					 const char *buf, size_t count)
3773{
3774	unsigned int msecs;
3775	int err;
3776
3777	err = kstrtouint(buf, 10, &msecs);
3778	if (err)
3779		return -EINVAL;
3780
3781	ksm_stable_node_chains_prune_millisecs = msecs;
3782
3783	return count;
3784}
3785KSM_ATTR(stable_node_chains_prune_millisecs);
3786
3787static ssize_t full_scans_show(struct kobject *kobj,
3788			       struct kobj_attribute *attr, char *buf)
3789{
3790	return sysfs_emit(buf, "%lu\n", ksm_scan.seqnr);
3791}
3792KSM_ATTR_RO(full_scans);
3793
3794static ssize_t smart_scan_show(struct kobject *kobj,
3795			       struct kobj_attribute *attr, char *buf)
3796{
3797	return sysfs_emit(buf, "%u\n", ksm_smart_scan);
3798}
3799
3800static ssize_t smart_scan_store(struct kobject *kobj,
3801				struct kobj_attribute *attr,
3802				const char *buf, size_t count)
3803{
3804	int err;
3805	bool value;
3806
3807	err = kstrtobool(buf, &value);
3808	if (err)
3809		return -EINVAL;
3810
3811	ksm_smart_scan = value;
3812	return count;
3813}
3814KSM_ATTR(smart_scan);
3815
3816static ssize_t advisor_mode_show(struct kobject *kobj,
3817				 struct kobj_attribute *attr, char *buf)
3818{
3819	const char *output;
3820
3821	if (ksm_advisor == KSM_ADVISOR_SCAN_TIME)
3822		output = "none [scan-time]";
3823	else
3824		output = "[none] scan-time";
3825
3826	return sysfs_emit(buf, "%s\n", output);
3827}
3828
3829static ssize_t advisor_mode_store(struct kobject *kobj,
3830				  struct kobj_attribute *attr, const char *buf,
3831				  size_t count)
3832{
3833	enum ksm_advisor_type curr_advisor = ksm_advisor;
3834
3835	if (sysfs_streq("scan-time", buf))
3836		ksm_advisor = KSM_ADVISOR_SCAN_TIME;
3837	else if (sysfs_streq("none", buf))
3838		ksm_advisor = KSM_ADVISOR_NONE;
3839	else
3840		return -EINVAL;
3841
3842	/* Set advisor default values */
3843	if (curr_advisor != ksm_advisor)
3844		set_advisor_defaults();
3845
3846	return count;
3847}
3848KSM_ATTR(advisor_mode);
3849
3850static ssize_t advisor_max_cpu_show(struct kobject *kobj,
3851				    struct kobj_attribute *attr, char *buf)
3852{
3853	return sysfs_emit(buf, "%u\n", ksm_advisor_max_cpu);
3854}
3855
3856static ssize_t advisor_max_cpu_store(struct kobject *kobj,
3857				     struct kobj_attribute *attr,
3858				     const char *buf, size_t count)
3859{
3860	int err;
3861	unsigned long value;
3862
3863	err = kstrtoul(buf, 10, &value);
3864	if (err)
3865		return -EINVAL;
3866
3867	ksm_advisor_max_cpu = value;
3868	return count;
3869}
3870KSM_ATTR(advisor_max_cpu);
3871
3872static ssize_t advisor_min_pages_to_scan_show(struct kobject *kobj,
3873					struct kobj_attribute *attr, char *buf)
3874{
3875	return sysfs_emit(buf, "%lu\n", ksm_advisor_min_pages_to_scan);
3876}
3877
3878static ssize_t advisor_min_pages_to_scan_store(struct kobject *kobj,
3879					struct kobj_attribute *attr,
3880					const char *buf, size_t count)
3881{
3882	int err;
3883	unsigned long value;
3884
3885	err = kstrtoul(buf, 10, &value);
3886	if (err)
3887		return -EINVAL;
3888
3889	ksm_advisor_min_pages_to_scan = value;
3890	return count;
3891}
3892KSM_ATTR(advisor_min_pages_to_scan);
3893
3894static ssize_t advisor_max_pages_to_scan_show(struct kobject *kobj,
3895					struct kobj_attribute *attr, char *buf)
3896{
3897	return sysfs_emit(buf, "%lu\n", ksm_advisor_max_pages_to_scan);
3898}
3899
3900static ssize_t advisor_max_pages_to_scan_store(struct kobject *kobj,
3901					struct kobj_attribute *attr,
3902					const char *buf, size_t count)
3903{
3904	int err;
3905	unsigned long value;
3906
3907	err = kstrtoul(buf, 10, &value);
3908	if (err)
3909		return -EINVAL;
3910
3911	ksm_advisor_max_pages_to_scan = value;
3912	return count;
3913}
3914KSM_ATTR(advisor_max_pages_to_scan);
3915
3916static ssize_t advisor_target_scan_time_show(struct kobject *kobj,
3917					     struct kobj_attribute *attr, char *buf)
3918{
3919	return sysfs_emit(buf, "%lu\n", ksm_advisor_target_scan_time);
3920}
3921
3922static ssize_t advisor_target_scan_time_store(struct kobject *kobj,
3923					      struct kobj_attribute *attr,
3924					      const char *buf, size_t count)
3925{
3926	int err;
3927	unsigned long value;
3928
3929	err = kstrtoul(buf, 10, &value);
3930	if (err)
3931		return -EINVAL;
3932	if (value < 1)
3933		return -EINVAL;
3934
3935	ksm_advisor_target_scan_time = value;
3936	return count;
3937}
3938KSM_ATTR(advisor_target_scan_time);
3939
3940static struct attribute *ksm_attrs[] = {
3941	&sleep_millisecs_attr.attr,
3942	&pages_to_scan_attr.attr,
3943	&run_attr.attr,
3944	&pages_scanned_attr.attr,
3945	&pages_shared_attr.attr,
3946	&pages_sharing_attr.attr,
3947	&pages_unshared_attr.attr,
3948	&pages_volatile_attr.attr,
3949	&pages_skipped_attr.attr,
3950	&ksm_zero_pages_attr.attr,
3951	&full_scans_attr.attr,
3952#ifdef CONFIG_NUMA
3953	&merge_across_nodes_attr.attr,
3954#endif
3955	&max_page_sharing_attr.attr,
3956	&stable_node_chains_attr.attr,
3957	&stable_node_dups_attr.attr,
3958	&stable_node_chains_prune_millisecs_attr.attr,
3959	&use_zero_pages_attr.attr,
3960	&general_profit_attr.attr,
3961	&smart_scan_attr.attr,
3962	&advisor_mode_attr.attr,
3963	&advisor_max_cpu_attr.attr,
3964	&advisor_min_pages_to_scan_attr.attr,
3965	&advisor_max_pages_to_scan_attr.attr,
3966	&advisor_target_scan_time_attr.attr,
3967	NULL,
3968};
3969
3970static const struct attribute_group ksm_attr_group = {
3971	.attrs = ksm_attrs,
3972	.name = "ksm",
3973};
3974#endif /* CONFIG_SYSFS */
3975
3976static int __init ksm_init(void)
3977{
3978	struct task_struct *ksm_thread;
3979	int err;
3980
3981	/* The correct value depends on page size and endianness */
3982	zero_checksum = calc_checksum(ZERO_PAGE(0));
3983	/* Default to false for backwards compatibility */
3984	ksm_use_zero_pages = false;
3985
3986	err = ksm_slab_init();
3987	if (err)
3988		goto out;
3989
3990	ksm_thread = kthread_run(ksm_scan_thread, NULL, "ksmd");
3991	if (IS_ERR(ksm_thread)) {
3992		pr_err("ksm: creating kthread failed\n");
3993		err = PTR_ERR(ksm_thread);
3994		goto out_free;
3995	}
3996
3997#ifdef CONFIG_SYSFS
3998	err = sysfs_create_group(mm_kobj, &ksm_attr_group);
3999	if (err) {
4000		pr_err("ksm: register sysfs failed\n");
4001		kthread_stop(ksm_thread);
4002		goto out_free;
4003	}
4004#else
4005	ksm_run = KSM_RUN_MERGE;	/* no way for user to start it */
4006
4007#endif /* CONFIG_SYSFS */
4008
4009#ifdef CONFIG_MEMORY_HOTREMOVE
4010	/* There is no significance to this priority 100 */
4011	hotplug_memory_notifier(ksm_memory_callback, KSM_CALLBACK_PRI);
4012#endif
4013	return 0;
4014
4015out_free:
4016	ksm_slab_free();
4017out:
4018	return err;
4019}
4020subsys_initcall(ksm_init);