brintos / linux-shallow public Read only

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