// SPDX-License-Identifier: GPL-2.0-only

/*

* Memory merging support.

*

* This code enables dynamic sharing of identical pages found in different

* memory areas, even if they are not shared by fork()

*

* Copyright (C) 2008-2009 Red Hat, Inc.

* Authors:

* Izik Eidus

* Andrea Arcangeli

* Chris Wright

* Hugh Dickins

*/

#include <linux/errno.h>

#include <linux/mm.h>

#include <linux/mm_inline.h>

#include <linux/fs.h>

#include <linux/mman.h>

#include <linux/sched.h>

#include <linux/sched/mm.h>

#include <linux/sched/cputime.h>

#include <linux/rwsem.h>

#include <linux/pagemap.h>

#include <linux/rmap.h>

#include <linux/spinlock.h>

#include <linux/xxhash.h>

#include <linux/delay.h>

#include <linux/kthread.h>

#include <linux/wait.h>

#include <linux/slab.h>

#include <linux/rbtree.h>

#include <linux/memory.h>

#include <linux/mmu_notifier.h>

#include <linux/swap.h>

#include <linux/ksm.h>

#include <linux/hashtable.h>

#include <linux/freezer.h>

#include <linux/oom.h>

#include <linux/numa.h>

#include <linux/pagewalk.h>

#include <asm/tlbflush.h>

#include "internal.h"

#include "mm_slot.h"

#define CREATE_TRACE_POINTS

#include <trace/events/ksm.h>

#ifdef CONFIG_NUMA

#define NUMA(x) (x)

#define DO_NUMA(x) do { (x); } while (0)

#else

#define NUMA(x) (0)

#define DO_NUMA(x) do { } while (0)

#endif

typedef u8 rmap_age_t;

/**

* DOC: Overview

*

* A few notes about the KSM scanning process,

* to make it easier to understand the data structures below:

*

* In order to reduce excessive scanning, KSM sorts the memory pages by their

* contents into a data structure that holds pointers to the pages' locations.

*

* Since the contents of the pages may change at any moment, KSM cannot just

* insert the pages into a normal sorted tree and expect it to find anything.

* Therefore KSM uses two data structures - the stable and the unstable tree.

*

* The stable tree holds pointers to all the merged pages (ksm pages), sorted

* by their contents. Because each such page is write-protected, searching on

* this tree is fully assured to be working (except when pages are unmapped),

* and therefore this tree is called the stable tree.

*

* The stable tree node includes information required for reverse

* mapping from a KSM page to virtual addresses that map this page.

*

* In order to avoid large latencies of the rmap walks on KSM pages,

* KSM maintains two types of nodes in the stable tree:

*

* * the regular nodes that keep the reverse mapping structures in a

* linked list

* * the "chains" that link nodes ("dups") that represent the same

* write protected memory content, but each "dup" corresponds to a

* different KSM page copy of that content

*

* Internally, the regular nodes, "dups" and "chains" are represented

* using the same struct ksm_stable_node structure.

*

* In addition to the stable tree, KSM uses a second data structure called the

* unstable tree: this tree holds pointers to pages which have been found to

* be "unchanged for a period of time". The unstable tree sorts these pages

* by their contents, but since they are not write-protected, KSM cannot rely

* upon the unstable tree to work correctly - the unstable tree is liable to

* be corrupted as its contents are modified, and so it is called unstable.

*

* KSM solves this problem by several techniques:

*

* 1) The unstable tree is flushed every time KSM completes scanning all

* memory areas, and then the tree is rebuilt again from the beginning.

* 2) KSM will only insert into the unstable tree, pages whose hash value

* has not changed since the previous scan of all memory areas.

* 3) The unstable tree is a RedBlack Tree - so its balancing is based on the

* colors of the nodes and not on their contents, assuring that even when

* the tree gets "corrupted" it won't get out of balance, so scanning time

* remains the same (also, searching and inserting nodes in an rbtree uses

* the same algorithm, so we have no overhead when we flush and rebuild).

* 4) KSM never flushes the stable tree, which means that even if it were to

* take 10 attempts to find a page in the unstable tree, once it is found,

* it is secured in the stable tree. (When we scan a new page, we first

* compare it against the stable tree, and then against the unstable tree.)

*

* If the merge_across_nodes tunable is unset, then KSM maintains multiple

* stable trees and multiple unstable trees: one of each for each NUMA node.

*/

/**

* struct ksm_mm_slot - ksm information per mm that is being scanned

* @slot: hash lookup from mm to mm_slot

* @rmap_list: head for this mm_slot's singly-linked list of rmap_items

*/

struct ksm_mm_slot {

struct mm_slot slot;

struct ksm_rmap_item *rmap_list;

};

/**

* struct ksm_scan - cursor for scanning

* @mm_slot: the current mm_slot we are scanning

* @address: the next address inside that to be scanned

* @rmap_list: link to the next rmap to be scanned in the rmap_list

* @seqnr: count of completed full scans (needed when removing unstable node)

*

* There is only the one ksm_scan instance of this cursor structure.

*/

struct ksm_scan {

struct ksm_mm_slot *mm_slot;

unsigned long address;

struct ksm_rmap_item **rmap_list;

unsigned long seqnr;

};

/**

* struct ksm_stable_node - node of the stable rbtree

* @node: rb node of this ksm page in the stable tree

* @head: (overlaying parent) &migrate_nodes indicates temporarily on that list

* @hlist_dup: linked into the stable_node->hlist with a stable_node chain

* @list: linked into migrate_nodes, pending placement in the proper node tree

* @hlist: hlist head of rmap_items using this ksm page

* @kpfn: page frame number of this ksm page (perhaps temporarily on wrong nid)

* @chain_prune_time: time of the last full garbage collection

* @rmap_hlist_len: number of rmap_item entries in hlist or STABLE_NODE_CHAIN

* @nid: NUMA node id of stable tree in which linked (may not match kpfn)

*/

struct ksm_stable_node {

union {

struct rb_node node; /* when node of stable tree */

struct { /* when listed for migration */

struct list_head *head;

struct {

struct hlist_node hlist_dup;

struct list_head list;

};

};

};

struct hlist_head hlist;

union {

unsigned long kpfn;

unsigned long chain_prune_time;

};

/*

* STABLE_NODE_CHAIN can be any negative number in

* rmap_hlist_len negative range, but better not -1 to be able

* to reliably detect underflows.

*/

#define STABLE_NODE_CHAIN -1024

int rmap_hlist_len;

#ifdef CONFIG_NUMA

int nid;

#endif

};

/**

* struct ksm_rmap_item - reverse mapping item for virtual addresses

* @rmap_list: next rmap_item in mm_slot's singly-linked rmap_list

* @anon_vma: pointer to anon_vma for this mm,address, when in stable tree

* @nid: NUMA node id of unstable tree in which linked (may not match page)

* @mm: the memory structure this rmap_item is pointing into

* @address: the virtual address this rmap_item tracks (+ flags in low bits)

* @oldchecksum: previous checksum of the page at that virtual address

* @node: rb node of this rmap_item in the unstable tree

* @head: pointer to stable_node heading this list in the stable tree

* @hlist: link into hlist of rmap_items hanging off that stable_node

* @age: number of scan iterations since creation

* @remaining_skips: how many scans to skip

*/

struct ksm_rmap_item {

struct ksm_rmap_item *rmap_list;

union {

struct anon_vma *anon_vma; /* when stable */

#ifdef CONFIG_NUMA

int nid; /* when node of unstable tree */

#endif

};

struct mm_struct *mm;

unsigned long address; /* + low bits used for flags below */

unsigned int oldchecksum; /* when unstable */

rmap_age_t age;

rmap_age_t remaining_skips;

union {

struct rb_node node; /* when node of unstable tree */

struct { /* when listed from stable tree */

struct ksm_stable_node *head;

struct hlist_node hlist;

};

};

};

#define SEQNR_MASK 0x0ff /* low bits of unstable tree seqnr */

#define UNSTABLE_FLAG 0x100 /* is a node of the unstable tree */

#define STABLE_FLAG 0x200 /* is listed from the stable tree */

/* The stable and unstable tree heads */

static struct rb_root one_stable_tree[1] = { RB_ROOT };

static struct rb_root one_unstable_tree[1] = { RB_ROOT };

static struct rb_root *root_stable_tree = one_stable_tree;

static struct rb_root *root_unstable_tree = one_unstable_tree;

/* Recently migrated nodes of stable tree, pending proper placement */

static LIST_HEAD(migrate_nodes);

#define STABLE_NODE_DUP_HEAD ((struct list_head *)&migrate_nodes.prev)

#define MM_SLOTS_HASH_BITS 10

static DEFINE_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_BITS);

static struct ksm_mm_slot ksm_mm_head = {

.slot.mm_node = LIST_HEAD_INIT(ksm_mm_head.slot.mm_node),

};

static struct ksm_scan ksm_scan = {

.mm_slot = &ksm_mm_head,

};

static struct kmem_cache *rmap_item_cache;

static struct kmem_cache *stable_node_cache;

static struct kmem_cache *mm_slot_cache;

/* Default number of pages to scan per batch */

#define DEFAULT_PAGES_TO_SCAN 100

/* The number of pages scanned */

static unsigned long ksm_pages_scanned;

/* The number of nodes in the stable tree */

static unsigned long ksm_pages_shared;

/* The number of page slots additionally sharing those nodes */

static unsigned long ksm_pages_sharing;

/* The number of nodes in the unstable tree */

static unsigned long ksm_pages_unshared;

/* The number of rmap_items in use: to calculate pages_volatile */

static unsigned long ksm_rmap_items;

/* The number of stable_node chains */

static unsigned long ksm_stable_node_chains;

/* The number of stable_node dups linked to the stable_node chains */

static unsigned long ksm_stable_node_dups;

/* Delay in pruning stale stable_node_dups in the stable_node_chains */

static unsigned int ksm_stable_node_chains_prune_millisecs = 2000;

/* Maximum number of page slots sharing a stable node */

static int ksm_max_page_sharing = 256;

/* Number of pages ksmd should scan in one batch */

static unsigned int ksm_thread_pages_to_scan = DEFAULT_PAGES_TO_SCAN;

/* Milliseconds ksmd should sleep between batches */

static unsigned int ksm_thread_sleep_millisecs = 20;

/* Checksum of an empty (zeroed) page */

static unsigned int zero_checksum __read_mostly;

/* Whether to merge empty (zeroed) pages with actual zero pages */

static bool ksm_use_zero_pages __read_mostly;

/* Skip pages that couldn't be de-duplicated previously */

/* Default to true at least temporarily, for testing */

static bool ksm_smart_scan = true;

/* The number of zero pages which is placed by KSM */

atomic_long_t ksm_zero_pages = ATOMIC_LONG_INIT(0);

/* The number of pages that have been skipped due to "smart scanning" */

static unsigned long ksm_pages_skipped;

/* Don't scan more than max pages per batch. */

static unsigned long ksm_advisor_max_pages_to_scan = 30000;

/* Min CPU for scanning pages per scan */

#define KSM_ADVISOR_MIN_CPU 10

/* Max CPU for scanning pages per scan */

static unsigned int ksm_advisor_max_cpu = 70;

/* Target scan time in seconds to analyze all KSM candidate pages. */

static unsigned long ksm_advisor_target_scan_time = 200;

/* Exponentially weighted moving average. */

#define EWMA_WEIGHT 30

/**

* struct advisor_ctx - metadata for KSM advisor

* @start_scan: start time of the current scan

* @scan_time: scan time of previous scan

* @change: change in percent to pages_to_scan parameter

* @cpu_time: cpu time consumed by the ksmd thread in the previous scan

*/

struct advisor_ctx {

ktime_t start_scan;

unsigned long scan_time;

unsigned long change;

unsigned long long cpu_time;

};

static struct advisor_ctx advisor_ctx;

/* Define different advisor's */

enum ksm_advisor_type {

KSM_ADVISOR_NONE,

KSM_ADVISOR_SCAN_TIME,

};

static enum ksm_advisor_type ksm_advisor;

#ifdef CONFIG_SYSFS

/*

* Only called through the sysfs control interface:

*/

/* At least scan this many pages per batch. */

static unsigned long ksm_advisor_min_pages_to_scan = 500;

static void set_advisor_defaults(void)

{

if (ksm_advisor == KSM_ADVISOR_NONE) {

ksm_thread_pages_to_scan = DEFAULT_PAGES_TO_SCAN;

} else if (ksm_advisor == KSM_ADVISOR_SCAN_TIME) {

advisor_ctx = (const struct advisor_ctx){ 0 };

ksm_thread_pages_to_scan = ksm_advisor_min_pages_to_scan;

}

}

#endif /* CONFIG_SYSFS */

static inline void advisor_start_scan(void)

{

if (ksm_advisor == KSM_ADVISOR_SCAN_TIME)

advisor_ctx.start_scan = ktime_get();

}

/*

* Use previous scan time if available, otherwise use current scan time as an

* approximation for the previous scan time.

*/

static inline unsigned long prev_scan_time(struct advisor_ctx *ctx,

unsigned long scan_time)

{

return ctx->scan_time ? ctx->scan_time : scan_time;

}

/* Calculate exponential weighted moving average */

static unsigned long ewma(unsigned long prev, unsigned long curr)

{

return ((100 - EWMA_WEIGHT) * prev + EWMA_WEIGHT * curr) / 100;

}

/*

* The scan time advisor is based on the current scan rate and the target

* scan rate.

*

* new_pages_to_scan = pages_to_scan * (scan_time / target_scan_time)

*

* To avoid perturbations it calculates a change factor of previous changes.

* A new change factor is calculated for each iteration and it uses an

* exponentially weighted moving average. The new pages_to_scan value is

* multiplied with that change factor:

*

* new_pages_to_scan *= change factor

*

* The new_pages_to_scan value is limited by the cpu min and max values. It

* calculates the cpu percent for the last scan and calculates the new

* estimated cpu percent cost for the next scan. That value is capped by the

* cpu min and max setting.

*

* In addition the new pages_to_scan value is capped by the max and min

* limits.

*/

static void scan_time_advisor(void)

{

unsigned int cpu_percent;

unsigned long cpu_time;

unsigned long cpu_time_diff;

unsigned long cpu_time_diff_ms;

unsigned long pages;

unsigned long per_page_cost;

unsigned long factor;

unsigned long change;

unsigned long last_scan_time;

unsigned long scan_time;

/* Convert scan time to seconds */

scan_time = div_s64(ktime_ms_delta(ktime_get(), advisor_ctx.start_scan),

MSEC_PER_SEC);

scan_time = scan_time ? scan_time : 1;

/* Calculate CPU consumption of ksmd background thread */

cpu_time = task_sched_runtime(current);

cpu_time_diff = cpu_time - advisor_ctx.cpu_time;

cpu_time_diff_ms = cpu_time_diff / 1000 / 1000;

cpu_percent = (cpu_time_diff_ms * 100) / (scan_time * 1000);

cpu_percent = cpu_percent ? cpu_percent : 1;

last_scan_time = prev_scan_time(&advisor_ctx, scan_time);

/* Calculate scan time as percentage of target scan time */

factor = ksm_advisor_target_scan_time * 100 / scan_time;

factor = factor ? factor : 1;

/*

* Calculate scan time as percentage of last scan time and use

* exponentially weighted average to smooth it

*/

change = scan_time * 100 / last_scan_time;

change = change ? change : 1;

change = ewma(advisor_ctx.change, change);

/* Calculate new scan rate based on target scan rate. */

pages = ksm_thread_pages_to_scan * 100 / factor;

/* Update pages_to_scan by weighted change percentage. */

pages = pages * change / 100;

/* Cap new pages_to_scan value */

per_page_cost = ksm_thread_pages_to_scan / cpu_percent;

per_page_cost = per_page_cost ? per_page_cost : 1;

pages = min(pages, per_page_cost * ksm_advisor_max_cpu);

pages = max(pages, per_page_cost * KSM_ADVISOR_MIN_CPU);

pages = min(pages, ksm_advisor_max_pages_to_scan);

/* Update advisor context */

advisor_ctx.change = change;

advisor_ctx.scan_time = scan_time;

advisor_ctx.cpu_time = cpu_time;

ksm_thread_pages_to_scan = pages;

trace_ksm_advisor(scan_time, pages, cpu_percent);

}

static void advisor_stop_scan(void)

{

if (ksm_advisor == KSM_ADVISOR_SCAN_TIME)

scan_time_advisor();

}

#ifdef CONFIG_NUMA

/* Zeroed when merging across nodes is not allowed */

static unsigned int ksm_merge_across_nodes = 1;

static int ksm_nr_node_ids = 1;

#else

#define ksm_merge_across_nodes 1U

#define ksm_nr_node_ids 1

#endif

#define KSM_RUN_STOP 0

#define KSM_RUN_MERGE 1

#define KSM_RUN_UNMERGE 2

#define KSM_RUN_OFFLINE 4

static unsigned long ksm_run = KSM_RUN_STOP;

static void wait_while_offlining(void);

static DECLARE_WAIT_QUEUE_HEAD(ksm_thread_wait);

static DECLARE_WAIT_QUEUE_HEAD(ksm_iter_wait);

static DEFINE_MUTEX(ksm_thread_mutex);

static DEFINE_SPINLOCK(ksm_mmlist_lock);

static int __init ksm_slab_init(void)

{

rmap_item_cache = KMEM_CACHE(ksm_rmap_item, 0);

if (!rmap_item_cache)

goto out;

stable_node_cache = KMEM_CACHE(ksm_stable_node, 0);

if (!stable_node_cache)

goto out_free1;

mm_slot_cache = KMEM_CACHE(ksm_mm_slot, 0);

if (!mm_slot_cache)

goto out_free2;

return 0;

out_free2:

kmem_cache_destroy(stable_node_cache);

out_free1:

kmem_cache_destroy(rmap_item_cache);

out:

return -ENOMEM;

}

static void __init ksm_slab_free(void)

{

kmem_cache_destroy(mm_slot_cache);

kmem_cache_destroy(stable_node_cache);

kmem_cache_destroy(rmap_item_cache);

mm_slot_cache = NULL;

}

static __always_inline bool is_stable_node_chain(struct ksm_stable_node *chain)

{

return chain->rmap_hlist_len == STABLE_NODE_CHAIN;

}

static __always_inline bool is_stable_node_dup(struct ksm_stable_node *dup)

{

return dup->head == STABLE_NODE_DUP_HEAD;

}

static inline void stable_node_chain_add_dup(struct ksm_stable_node *dup,

struct ksm_stable_node *chain)

{

VM_BUG_ON(is_stable_node_dup(dup));

dup->head = STABLE_NODE_DUP_HEAD;

VM_BUG_ON(!is_stable_node_chain(chain));

hlist_add_head(&dup->hlist_dup, &chain->hlist);

ksm_stable_node_dups++;

}

static inline void __stable_node_dup_del(struct ksm_stable_node *dup)

{

VM_BUG_ON(!is_stable_node_dup(dup));

hlist_del(&dup->hlist_dup);

ksm_stable_node_dups--;

}

static inline void stable_node_dup_del(struct ksm_stable_node *dup)

{

VM_BUG_ON(is_stable_node_chain(dup));

if (is_stable_node_dup(dup))

__stable_node_dup_del(dup);

else

rb_erase(&dup->node, root_stable_tree + NUMA(dup->nid));

#ifdef CONFIG_DEBUG_VM

dup->head = NULL;

#endif

}

static inline struct ksm_rmap_item *alloc_rmap_item(void)

{

struct ksm_rmap_item *rmap_item;

rmap_item = kmem_cache_zalloc(rmap_item_cache, GFP_KERNEL |

__GFP_NORETRY | __GFP_NOWARN);

if (rmap_item)

ksm_rmap_items++;

return rmap_item;

}

static inline void free_rmap_item(struct ksm_rmap_item *rmap_item)

{

ksm_rmap_items--;

rmap_item->mm->ksm_rmap_items--;

rmap_item->mm = NULL; /* debug safety */

kmem_cache_free(rmap_item_cache, rmap_item);

}

static inline struct ksm_stable_node *alloc_stable_node(void)

{

/*

* The allocation can take too long with GFP_KERNEL when memory is under

* pressure, which may lead to hung task warnings. Adding __GFP_HIGH

* grants access to memory reserves, helping to avoid this problem.

*/

return kmem_cache_alloc(stable_node_cache, GFP_KERNEL | __GFP_HIGH);

}

static inline void free_stable_node(struct ksm_stable_node *stable_node)

{

VM_BUG_ON(stable_node->rmap_hlist_len &&

!is_stable_node_chain(stable_node));

kmem_cache_free(stable_node_cache, stable_node);

}

/*

* ksmd, and unmerge_and_remove_all_rmap_items(), must not touch an mm's

* page tables after it has passed through ksm_exit() - which, if necessary,

* takes mmap_lock briefly to serialize against them. ksm_exit() does not set

* a special flag: they can just back out as soon as mm_users goes to zero.

* ksm_test_exit() is used throughout to make this test for exit: in some

* places for correctness, in some places just to avoid unnecessary work.

*/

static inline bool ksm_test_exit(struct mm_struct *mm)

{

return atomic_read(&mm->mm_users) == 0;

}

static int break_ksm_pmd_entry(pmd_t *pmdp, unsigned long addr, unsigned long end,

struct mm_walk *walk)

{

unsigned long *found_addr = (unsigned long *) walk->private;

struct mm_struct *mm = walk->mm;

pte_t *start_ptep, *ptep;

spinlock_t *ptl;

int found = 0;

if (ksm_test_exit(walk->mm))

return 0;

if (signal_pending(current))

return -ERESTARTSYS;

start_ptep = pte_offset_map_lock(mm, pmdp, addr, &ptl);

if (!start_ptep)

return 0;

for (ptep = start_ptep; addr < end; ptep++, addr += PAGE_SIZE) {

pte_t pte = ptep_get(ptep);

struct folio *folio = NULL;

if (pte_present(pte)) {

folio = vm_normal_folio(walk->vma, addr, pte);

} else if (!pte_none(pte)) {

const softleaf_t entry = softleaf_from_pte(pte);

/*

* As KSM pages remain KSM pages until freed, no need to wait

* here for migration to end.

*/

if (softleaf_is_migration(entry))

folio = softleaf_to_folio(entry);

}

/* return 1 if the page is an normal ksm page or KSM-placed zero page */

found = (folio && folio_test_ksm(folio)) ||

(pte_present(pte) && is_ksm_zero_pte(pte));

if (found) {

*found_addr = addr;

goto out_unlock;

}

}

out_unlock:

pte_unmap_unlock(start_ptep, ptl);

return found;

}

static const struct mm_walk_ops break_ksm_ops = {

.pmd_entry = break_ksm_pmd_entry,

.walk_lock = PGWALK_RDLOCK,

};

static const struct mm_walk_ops break_ksm_lock_vma_ops = {

.pmd_entry = break_ksm_pmd_entry,

.walk_lock = PGWALK_WRLOCK,

};

/*

* Though it's very tempting to unmerge rmap_items from stable tree rather

* than check every pte of a given vma, the locking doesn't quite work for

* that - an rmap_item is assigned to the stable tree after inserting ksm

* page and upping mmap_lock. Nor does it fit with the way we skip dup'ing

* rmap_items from parent to child at fork time (so as not to waste time

* if exit comes before the next scan reaches it).

*

* Similarly, although we'd like to remove rmap_items (so updating counts

* and freeing memory) when unmerging an area, it's easier to leave that

* to the next pass of ksmd - consider, for example, how ksmd might be

* in cmp_and_merge_page on one of the rmap_items we would be removing.

*

* We use break_ksm to break COW on a ksm page by triggering unsharing,

* such that the ksm page will get replaced by an exclusive anonymous page.

*

* We take great care only to touch a ksm page, in a VM_MERGEABLE vma,

* in case the application has unmapped and remapped mm,addr meanwhile.

* Could a ksm page appear anywhere else? Actually yes, in a VM_PFNMAP

* mmap of /dev/mem, where we would not want to touch it.

*

* FAULT_FLAG_REMOTE/FOLL_REMOTE are because we do this outside the context

* of the process that owns 'vma'. We also do not want to enforce

* protection keys here anyway.

*/

static int break_ksm(struct vm_area_struct *vma, unsigned long addr,

unsigned long end, bool lock_vma)

{

vm_fault_t ret = 0;

const struct mm_walk_ops *ops = lock_vma ?

&break_ksm_lock_vma_ops : &break_ksm_ops;

do {

int ksm_page;

cond_resched();

ksm_page = walk_page_range_vma(vma, addr, end, ops, &addr);

if (ksm_page <= 0)

return ksm_page;

ret = handle_mm_fault(vma, addr,

FAULT_FLAG_UNSHARE | FAULT_FLAG_REMOTE,

NULL);

} while (!(ret & (VM_FAULT_SIGBUS | VM_FAULT_SIGSEGV | VM_FAULT_OOM)));

/*

* We must loop until we no longer find a KSM page because

* handle_mm_fault() may back out if there's any difficulty e.g. if

* pte accessed bit gets updated concurrently.

*

* VM_FAULT_SIGBUS could occur if we race with truncation of the

* backing file, which also invalidates anonymous pages: that's

* okay, that truncation will have unmapped the KSM page for us.

*

* VM_FAULT_OOM: at the time of writing (late July 2009), setting

* aside mem_cgroup limits, VM_FAULT_OOM would only be set if the

* current task has TIF_MEMDIE set, and will be OOM killed on return

* to user; and ksmd, having no mm, would never be chosen for that.

*

* But if the mm is in a limited mem_cgroup, then the fault may fail

* with VM_FAULT_OOM even if the current task is not TIF_MEMDIE; and

* even ksmd can fail in this way - though it's usually breaking ksm

* just to undo a merge it made a moment before, so unlikely to oom.

*

* That's a pity: we might therefore have more kernel pages allocated

* than we're counting as nodes in the stable tree; but ksm_do_scan

* will retry to break_cow on each pass, so should recover the page

* in due course. The important thing is to not let VM_MERGEABLE

* be cleared while any such pages might remain in the area.

*/

return (ret & VM_FAULT_OOM) ? -ENOMEM : 0;

}

static bool ksm_compatible(const struct file *file, vma_flags_t vma_flags)

{

/* Just ignore the advice. */

if (vma_flags_test_any(&vma_flags, VMA_SHARED_BIT, VMA_MAYSHARE_BIT,

VMA_HUGETLB_BIT))

return false;

if (vma_flags_test_single_mask(&vma_flags, VMA_DROPPABLE))

return false;

if (vma_flags_test_any_mask(&vma_flags, VMA_SPECIAL_FLAGS))

return false;

if (file_is_dax(file))

return false;

#ifdef VM_SAO

if (vma_flags_test(&vma_flags, VMA_SAO_BIT))

return false;

#endif

#ifdef VM_SPARC_ADI

if (vma_flags_test(&vma_flags, VMA_SPARC_ADI_BIT))

return false;

#endif

return true;

}

static bool vma_ksm_compatible(struct vm_area_struct *vma)

{

return ksm_compatible(vma->vm_file, vma->flags);

}

static struct vm_area_struct *find_mergeable_vma(struct mm_struct *mm,

unsigned long addr)

{

struct vm_area_struct *vma;

if (ksm_test_exit(mm))

return NULL;

vma = vma_lookup(mm, addr);

if (!vma || !(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)

return NULL;

return vma;

}

static void break_cow(struct ksm_rmap_item *rmap_item)

{

struct mm_struct *mm = rmap_item->mm;

unsigned long addr = rmap_item->address;

struct vm_area_struct *vma;

/*

* It is not an accident that whenever we want to break COW

* to undo, we also need to drop a reference to the anon_vma.

*/

put_anon_vma(rmap_item->anon_vma);

mmap_read_lock(mm);

vma = find_mergeable_vma(mm, addr);

if (vma)

break_ksm(vma, addr, addr + PAGE_SIZE, false);

mmap_read_unlock(mm);

}

static struct page *get_mergeable_page(struct ksm_rmap_item *rmap_item)

{

struct mm_struct *mm = rmap_item->mm;

unsigned long addr = rmap_item->address;

struct vm_area_struct *vma;

struct page *page = NULL;

struct folio_walk fw;

struct folio *folio;

mmap_read_lock(mm);

vma = find_mergeable_vma(mm, addr);

if (!vma)

goto out;

folio = folio_walk_start(&fw, vma, addr, 0);

if (folio) {

if (!folio_is_zone_device(folio) &&

folio_test_anon(folio)) {

folio_get(folio);

page = fw.page;

}

folio_walk_end(&fw, vma);

}

out:

if (page) {

flush_anon_page(vma, page, addr);

flush_dcache_page(page);

}

mmap_read_unlock(mm);

return page;

}

/*

* This helper is used for getting right index into array of tree roots.

* When merge_across_nodes knob is set to 1, there are only two rb-trees for

* stable and unstable pages from all nodes with roots in index 0. Otherwise,

* every node has its own stable and unstable tree.

*/

static inline int get_kpfn_nid(unsigned long kpfn)

{

return ksm_merge_across_nodes ? 0 : NUMA(pfn_to_nid(kpfn));

}

static struct ksm_stable_node *alloc_stable_node_chain(struct ksm_stable_node *dup,

struct rb_root *root)

{

struct ksm_stable_node *chain = alloc_stable_node();

VM_BUG_ON(is_stable_node_chain(dup));

if (likely(chain)) {

INIT_HLIST_HEAD(&chain->hlist);

chain->chain_prune_time = jiffies;

chain->rmap_hlist_len = STABLE_NODE_CHAIN;

#if defined (CONFIG_DEBUG_VM) && defined(CONFIG_NUMA)

chain->nid = NUMA_NO_NODE; /* debug */

#endif

ksm_stable_node_chains++;

/*

* Put the stable node chain in the first dimension of

* the stable tree and at the same time remove the old

* stable node.

*/

rb_replace_node(&dup->node, &chain->node, root);

/*

* Move the old stable node to the second dimension

* queued in the hlist_dup. The invariant is that all

* dup stable_nodes in the chain->hlist point to pages

* that are write protected and have the exact same

* content.

*/

stable_node_chain_add_dup(dup, chain);

}

return chain;

}

static inline void free_stable_node_chain(struct ksm_stable_node *chain,

struct rb_root *root)

{

rb_erase(&chain->node, root);

free_stable_node(chain);

ksm_stable_node_chains--;

}

static void remove_node_from_stable_tree(struct ksm_stable_node *stable_node)

{

struct ksm_rmap_item *rmap_item;

/* check it's not STABLE_NODE_CHAIN or negative */

BUG_ON(stable_node->rmap_hlist_len < 0);

hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) {

if (rmap_item->hlist.next) {

ksm_pages_sharing--;

trace_ksm_remove_rmap_item(stable_node->kpfn, rmap_item, rmap_item->mm);

} else {

ksm_pages_shared--;

}

rmap_item->mm->ksm_merging_pages--;

VM_BUG_ON(stable_node->rmap_hlist_len <= 0);

stable_node->rmap_hlist_len--;

put_anon_vma(rmap_item->anon_vma);

rmap_item->address &= PAGE_MASK;

cond_resched();

}

/*

* We need the second aligned pointer of the migrate_nodes

* list_head to stay clear from the rb_parent_color union

* (aligned and different than any node) and also different

* from &migrate_nodes. This will verify that future list.h changes

* don't break STABLE_NODE_DUP_HEAD. Only recent gcc can handle it.

*/

BUILD_BUG_ON(STABLE_NODE_DUP_HEAD <= &migrate_nodes);

BUILD_BUG_ON(STABLE_NODE_DUP_HEAD >= &migrate_nodes + 1);

trace_ksm_remove_ksm_page(stable_node->kpfn);

if (stable_node->head == &migrate_nodes)

list_del(&stable_node->list);

else

stable_node_dup_del(stable_node);

free_stable_node(stable_node);

}

enum ksm_get_folio_flags {

KSM_GET_FOLIO_NOLOCK,

KSM_GET_FOLIO_LOCK,

KSM_GET_FOLIO_TRYLOCK

};

/*

* ksm_get_folio: checks if the page indicated by the stable node

* is still its ksm page, despite having held no reference to it.

* In which case we can trust the content of the page, and it

* returns the gotten page; but if the page has now been zapped,

* remove the stale node from the stable tree and return NULL.

* But beware, the stable node's page might be being migrated.

*

* You would expect the stable_node to hold a reference to the ksm page.

* But if it increments the page's count, swapping out has to wait for

* ksmd to come around again before it can free the page, which may take

* seconds or even minutes: much too unresponsive. So instead we use a

* "keyhole reference": access to the ksm page from the stable node peeps

* out through its keyhole to see if that page still holds the right key,

* pointing back to this stable node. This relies on freeing a PageAnon

* page to reset its page->mapping to NULL, and relies on no other use of

* a page to put something that might look like our key in page->mapping.

* is on its way to being freed; but it is an anomaly to bear in mind.

*/

static struct folio *ksm_get_folio(struct ksm_stable_node *stable_node,

enum ksm_get_folio_flags flags)

{

struct folio *folio;

void *expected_mapping;

unsigned long kpfn;

expected_mapping = (void *)((unsigned long)stable_node |

FOLIO_MAPPING_KSM);

again:

kpfn = READ_ONCE(stable_node->kpfn); /* Address dependency. */

folio = pfn_folio(kpfn);

if (READ_ONCE(folio->mapping) != expected_mapping)

goto stale;

/*

* We cannot do anything with the page while its refcount is 0.

* Usually 0 means free, or tail of a higher-order page: in which

* case this node is no longer referenced, and should be freed;

* however, it might mean that the page is under page_ref_freeze().

* The __remove_mapping() case is easy, again the node is now stale;

* the same is in reuse_ksm_page() case; but if page is swapcache

* in folio_migrate_mapping(), it might still be our page,

* in which case it's essential to keep the node.

*/

while (!folio_try_get(folio)) {

/*

* Another check for folio->mapping != expected_mapping

* would work here too. We have chosen to test the

* swapcache flag to optimize the common case, when the

* folio is or is about to be freed: the swapcache flag

* is cleared (under spin_lock_irq) in the ref_freeze

* section of __remove_mapping(); but anon folio->mapping

* is reset to NULL later, in free_pages_prepare().

*/

if (!folio_test_swapcache(folio))

goto stale;

cpu_relax();

}

if (READ_ONCE(folio->mapping) != expected_mapping) {

folio_put(folio);

goto stale;

}

if (flags == KSM_GET_FOLIO_TRYLOCK) {

if (!folio_trylock(folio)) {

folio_put(folio);

return ERR_PTR(-EBUSY);

}

} else if (flags == KSM_GET_FOLIO_LOCK)

folio_lock(folio);