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