blob: 73d43bafd9fbc41ad322b9d26e80e548481a23b4 [file] [log] [blame]
Hugh Dickinsf8af4da2009-09-21 17:01:57 -07001/*
Izik Eidus31dbd012009-09-21 17:02:03 -07002 * Memory merging support.
3 *
4 * This code enables dynamic sharing of identical pages found in different
5 * memory areas, even if they are not shared by fork()
6 *
Izik Eidus36b25282009-09-21 17:02:06 -07007 * Copyright (C) 2008-2009 Red Hat, Inc.
Izik Eidus31dbd012009-09-21 17:02:03 -07008 * Authors:
9 * Izik Eidus
10 * Andrea Arcangeli
11 * Chris Wright
Izik Eidus36b25282009-09-21 17:02:06 -070012 * Hugh Dickins
Izik Eidus31dbd012009-09-21 17:02:03 -070013 *
14 * This work is licensed under the terms of the GNU GPL, version 2.
Hugh Dickinsf8af4da2009-09-21 17:01:57 -070015 */
16
17#include <linux/errno.h>
Izik Eidus31dbd012009-09-21 17:02:03 -070018#include <linux/mm.h>
19#include <linux/fs.h>
Hugh Dickinsf8af4da2009-09-21 17:01:57 -070020#include <linux/mman.h>
Izik Eidus31dbd012009-09-21 17:02:03 -070021#include <linux/sched.h>
22#include <linux/rwsem.h>
23#include <linux/pagemap.h>
24#include <linux/rmap.h>
25#include <linux/spinlock.h>
26#include <linux/jhash.h>
27#include <linux/delay.h>
28#include <linux/kthread.h>
29#include <linux/wait.h>
30#include <linux/slab.h>
31#include <linux/rbtree.h>
Hugh Dickins62b61f62009-12-14 17:59:33 -080032#include <linux/memory.h>
Izik Eidus31dbd012009-09-21 17:02:03 -070033#include <linux/mmu_notifier.h>
Izik Eidus2c6854f2009-09-23 15:56:04 -070034#include <linux/swap.h>
Hugh Dickinsf8af4da2009-09-21 17:01:57 -070035#include <linux/ksm.h>
Sasha Levin4ca3a692013-02-22 16:32:28 -080036#include <linux/hashtable.h>
Andrea Arcangeli878aee72011-01-13 15:47:10 -080037#include <linux/freezer.h>
David Rientjes72788c32011-05-24 17:11:40 -070038#include <linux/oom.h>
Petr Holasek90bd6fd2013-02-22 16:35:00 -080039#include <linux/numa.h>
Hugh Dickinsf8af4da2009-09-21 17:01:57 -070040
Izik Eidus31dbd012009-09-21 17:02:03 -070041#include <asm/tlbflush.h>
Hugh Dickins73848b42009-12-14 17:59:22 -080042#include "internal.h"
Izik Eidus31dbd012009-09-21 17:02:03 -070043
Hugh Dickinse850dcf2013-02-22 16:35:03 -080044#ifdef CONFIG_NUMA
45#define NUMA(x) (x)
46#define DO_NUMA(x) do { (x); } while (0)
47#else
48#define NUMA(x) (0)
49#define DO_NUMA(x) do { } while (0)
50#endif
51
Izik Eidus31dbd012009-09-21 17:02:03 -070052/*
53 * A few notes about the KSM scanning process,
54 * to make it easier to understand the data structures below:
55 *
56 * In order to reduce excessive scanning, KSM sorts the memory pages by their
57 * contents into a data structure that holds pointers to the pages' locations.
58 *
59 * Since the contents of the pages may change at any moment, KSM cannot just
60 * insert the pages into a normal sorted tree and expect it to find anything.
61 * Therefore KSM uses two data structures - the stable and the unstable tree.
62 *
63 * The stable tree holds pointers to all the merged pages (ksm pages), sorted
64 * by their contents. Because each such page is write-protected, searching on
65 * this tree is fully assured to be working (except when pages are unmapped),
66 * and therefore this tree is called the stable tree.
67 *
68 * In addition to the stable tree, KSM uses a second data structure called the
69 * unstable tree: this tree holds pointers to pages which have been found to
70 * be "unchanged for a period of time". The unstable tree sorts these pages
71 * by their contents, but since they are not write-protected, KSM cannot rely
72 * upon the unstable tree to work correctly - the unstable tree is liable to
73 * be corrupted as its contents are modified, and so it is called unstable.
74 *
75 * KSM solves this problem by several techniques:
76 *
77 * 1) The unstable tree is flushed every time KSM completes scanning all
78 * memory areas, and then the tree is rebuilt again from the beginning.
79 * 2) KSM will only insert into the unstable tree, pages whose hash value
80 * has not changed since the previous scan of all memory areas.
81 * 3) The unstable tree is a RedBlack Tree - so its balancing is based on the
82 * colors of the nodes and not on their contents, assuring that even when
83 * the tree gets "corrupted" it won't get out of balance, so scanning time
84 * remains the same (also, searching and inserting nodes in an rbtree uses
85 * the same algorithm, so we have no overhead when we flush and rebuild).
86 * 4) KSM never flushes the stable tree, which means that even if it were to
87 * take 10 attempts to find a page in the unstable tree, once it is found,
88 * it is secured in the stable tree. (When we scan a new page, we first
89 * compare it against the stable tree, and then against the unstable tree.)
Hugh Dickins8fdb3db2013-02-22 16:36:03 -080090 *
91 * If the merge_across_nodes tunable is unset, then KSM maintains multiple
92 * stable trees and multiple unstable trees: one of each for each NUMA node.
Izik Eidus31dbd012009-09-21 17:02:03 -070093 */
94
95/**
96 * struct mm_slot - ksm information per mm that is being scanned
97 * @link: link to the mm_slots hash list
98 * @mm_list: link into the mm_slots list, rooted in ksm_mm_head
Hugh Dickins6514d512009-12-14 17:59:19 -080099 * @rmap_list: head for this mm_slot's singly-linked list of rmap_items
Izik Eidus31dbd012009-09-21 17:02:03 -0700100 * @mm: the mm that this information is valid for
101 */
102struct mm_slot {
103 struct hlist_node link;
104 struct list_head mm_list;
Hugh Dickins6514d512009-12-14 17:59:19 -0800105 struct rmap_item *rmap_list;
Izik Eidus31dbd012009-09-21 17:02:03 -0700106 struct mm_struct *mm;
107};
108
109/**
110 * struct ksm_scan - cursor for scanning
111 * @mm_slot: the current mm_slot we are scanning
112 * @address: the next address inside that to be scanned
Hugh Dickins6514d512009-12-14 17:59:19 -0800113 * @rmap_list: link to the next rmap to be scanned in the rmap_list
Izik Eidus31dbd012009-09-21 17:02:03 -0700114 * @seqnr: count of completed full scans (needed when removing unstable node)
115 *
116 * There is only the one ksm_scan instance of this cursor structure.
117 */
118struct ksm_scan {
119 struct mm_slot *mm_slot;
120 unsigned long address;
Hugh Dickins6514d512009-12-14 17:59:19 -0800121 struct rmap_item **rmap_list;
Izik Eidus31dbd012009-09-21 17:02:03 -0700122 unsigned long seqnr;
123};
124
125/**
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800126 * struct stable_node - node of the stable rbtree
127 * @node: rb node of this ksm page in the stable tree
Hugh Dickins4146d2d2013-02-22 16:35:11 -0800128 * @head: (overlaying parent) &migrate_nodes indicates temporarily on that list
129 * @list: linked into migrate_nodes, pending placement in the proper node tree
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800130 * @hlist: hlist head of rmap_items using this ksm page
Hugh Dickins4146d2d2013-02-22 16:35:11 -0800131 * @kpfn: page frame number of this ksm page (perhaps temporarily on wrong nid)
132 * @nid: NUMA node id of stable tree in which linked (may not match kpfn)
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800133 */
134struct stable_node {
Hugh Dickins4146d2d2013-02-22 16:35:11 -0800135 union {
136 struct rb_node node; /* when node of stable tree */
137 struct { /* when listed for migration */
138 struct list_head *head;
139 struct list_head list;
140 };
141 };
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800142 struct hlist_head hlist;
Hugh Dickins62b61f62009-12-14 17:59:33 -0800143 unsigned long kpfn;
Hugh Dickins4146d2d2013-02-22 16:35:11 -0800144#ifdef CONFIG_NUMA
145 int nid;
146#endif
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800147};
148
149/**
Izik Eidus31dbd012009-09-21 17:02:03 -0700150 * struct rmap_item - reverse mapping item for virtual addresses
Hugh Dickins6514d512009-12-14 17:59:19 -0800151 * @rmap_list: next rmap_item in mm_slot's singly-linked rmap_list
Hugh Dickinsdb114b82009-12-14 17:59:25 -0800152 * @anon_vma: pointer to anon_vma for this mm,address, when in stable tree
Hugh Dickinsbc566202013-02-22 16:36:06 -0800153 * @nid: NUMA node id of unstable tree in which linked (may not match page)
Izik Eidus31dbd012009-09-21 17:02:03 -0700154 * @mm: the memory structure this rmap_item is pointing into
155 * @address: the virtual address this rmap_item tracks (+ flags in low bits)
156 * @oldchecksum: previous checksum of the page at that virtual address
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800157 * @node: rb node of this rmap_item in the unstable tree
158 * @head: pointer to stable_node heading this list in the stable tree
159 * @hlist: link into hlist of rmap_items hanging off that stable_node
Izik Eidus31dbd012009-09-21 17:02:03 -0700160 */
161struct rmap_item {
Hugh Dickins6514d512009-12-14 17:59:19 -0800162 struct rmap_item *rmap_list;
Hugh Dickinsbc566202013-02-22 16:36:06 -0800163 union {
164 struct anon_vma *anon_vma; /* when stable */
165#ifdef CONFIG_NUMA
166 int nid; /* when node of unstable tree */
167#endif
168 };
Izik Eidus31dbd012009-09-21 17:02:03 -0700169 struct mm_struct *mm;
170 unsigned long address; /* + low bits used for flags below */
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800171 unsigned int oldchecksum; /* when unstable */
Izik Eidus31dbd012009-09-21 17:02:03 -0700172 union {
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800173 struct rb_node node; /* when node of unstable tree */
174 struct { /* when listed from stable tree */
175 struct stable_node *head;
176 struct hlist_node hlist;
177 };
Izik Eidus31dbd012009-09-21 17:02:03 -0700178 };
179};
180
181#define SEQNR_MASK 0x0ff /* low bits of unstable tree seqnr */
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800182#define UNSTABLE_FLAG 0x100 /* is a node of the unstable tree */
183#define STABLE_FLAG 0x200 /* is listed from the stable tree */
Izik Eidus31dbd012009-09-21 17:02:03 -0700184
185/* The stable and unstable tree heads */
Hugh Dickinsef53d162013-02-22 16:36:12 -0800186static struct rb_root one_stable_tree[1] = { RB_ROOT };
187static struct rb_root one_unstable_tree[1] = { RB_ROOT };
188static struct rb_root *root_stable_tree = one_stable_tree;
189static struct rb_root *root_unstable_tree = one_unstable_tree;
Izik Eidus31dbd012009-09-21 17:02:03 -0700190
Hugh Dickins4146d2d2013-02-22 16:35:11 -0800191/* Recently migrated nodes of stable tree, pending proper placement */
192static LIST_HEAD(migrate_nodes);
193
Sasha Levin4ca3a692013-02-22 16:32:28 -0800194#define MM_SLOTS_HASH_BITS 10
195static DEFINE_HASHTABLE(mm_slots_hash, MM_SLOTS_HASH_BITS);
Izik Eidus31dbd012009-09-21 17:02:03 -0700196
197static struct mm_slot ksm_mm_head = {
198 .mm_list = LIST_HEAD_INIT(ksm_mm_head.mm_list),
199};
200static struct ksm_scan ksm_scan = {
201 .mm_slot = &ksm_mm_head,
202};
203
204static struct kmem_cache *rmap_item_cache;
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800205static struct kmem_cache *stable_node_cache;
Izik Eidus31dbd012009-09-21 17:02:03 -0700206static struct kmem_cache *mm_slot_cache;
207
208/* The number of nodes in the stable tree */
Hugh Dickinsb4028262009-09-21 17:02:09 -0700209static unsigned long ksm_pages_shared;
Izik Eidus31dbd012009-09-21 17:02:03 -0700210
Hugh Dickinse178dfd2009-09-21 17:02:10 -0700211/* The number of page slots additionally sharing those nodes */
Hugh Dickinsb4028262009-09-21 17:02:09 -0700212static unsigned long ksm_pages_sharing;
Izik Eidus31dbd012009-09-21 17:02:03 -0700213
Hugh Dickins473b0ce2009-09-21 17:02:11 -0700214/* The number of nodes in the unstable tree */
215static unsigned long ksm_pages_unshared;
216
217/* The number of rmap_items in use: to calculate pages_volatile */
218static unsigned long ksm_rmap_items;
219
Izik Eidus31dbd012009-09-21 17:02:03 -0700220/* Number of pages ksmd should scan in one batch */
Izik Eidus2c6854f2009-09-23 15:56:04 -0700221static unsigned int ksm_thread_pages_to_scan = 100;
Izik Eidus31dbd012009-09-21 17:02:03 -0700222
223/* Milliseconds ksmd should sleep between batches */
Hugh Dickins2ffd8672009-09-21 17:02:23 -0700224static unsigned int ksm_thread_sleep_millisecs = 20;
Izik Eidus31dbd012009-09-21 17:02:03 -0700225
Hugh Dickinse850dcf2013-02-22 16:35:03 -0800226#ifdef CONFIG_NUMA
Petr Holasek90bd6fd2013-02-22 16:35:00 -0800227/* Zeroed when merging across nodes is not allowed */
228static unsigned int ksm_merge_across_nodes = 1;
Hugh Dickinsef53d162013-02-22 16:36:12 -0800229static int ksm_nr_node_ids = 1;
Hugh Dickinse850dcf2013-02-22 16:35:03 -0800230#else
231#define ksm_merge_across_nodes 1U
Hugh Dickinsef53d162013-02-22 16:36:12 -0800232#define ksm_nr_node_ids 1
Hugh Dickinse850dcf2013-02-22 16:35:03 -0800233#endif
Petr Holasek90bd6fd2013-02-22 16:35:00 -0800234
Izik Eidus31dbd012009-09-21 17:02:03 -0700235#define KSM_RUN_STOP 0
236#define KSM_RUN_MERGE 1
237#define KSM_RUN_UNMERGE 2
Hugh Dickinsef4d43a2013-02-22 16:35:16 -0800238#define KSM_RUN_OFFLINE 4
239static unsigned long ksm_run = KSM_RUN_STOP;
240static void wait_while_offlining(void);
Izik Eidus31dbd012009-09-21 17:02:03 -0700241
242static DECLARE_WAIT_QUEUE_HEAD(ksm_thread_wait);
243static DEFINE_MUTEX(ksm_thread_mutex);
244static DEFINE_SPINLOCK(ksm_mmlist_lock);
245
246#define KSM_KMEM_CACHE(__struct, __flags) kmem_cache_create("ksm_"#__struct,\
247 sizeof(struct __struct), __alignof__(struct __struct),\
248 (__flags), NULL)
249
250static int __init ksm_slab_init(void)
251{
252 rmap_item_cache = KSM_KMEM_CACHE(rmap_item, 0);
253 if (!rmap_item_cache)
254 goto out;
255
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800256 stable_node_cache = KSM_KMEM_CACHE(stable_node, 0);
257 if (!stable_node_cache)
258 goto out_free1;
259
Izik Eidus31dbd012009-09-21 17:02:03 -0700260 mm_slot_cache = KSM_KMEM_CACHE(mm_slot, 0);
261 if (!mm_slot_cache)
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800262 goto out_free2;
Izik Eidus31dbd012009-09-21 17:02:03 -0700263
264 return 0;
265
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800266out_free2:
267 kmem_cache_destroy(stable_node_cache);
268out_free1:
Izik Eidus31dbd012009-09-21 17:02:03 -0700269 kmem_cache_destroy(rmap_item_cache);
270out:
271 return -ENOMEM;
272}
273
274static void __init ksm_slab_free(void)
275{
276 kmem_cache_destroy(mm_slot_cache);
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800277 kmem_cache_destroy(stable_node_cache);
Izik Eidus31dbd012009-09-21 17:02:03 -0700278 kmem_cache_destroy(rmap_item_cache);
279 mm_slot_cache = NULL;
280}
281
282static inline struct rmap_item *alloc_rmap_item(void)
283{
Hugh Dickins473b0ce2009-09-21 17:02:11 -0700284 struct rmap_item *rmap_item;
285
286 rmap_item = kmem_cache_zalloc(rmap_item_cache, GFP_KERNEL);
287 if (rmap_item)
288 ksm_rmap_items++;
289 return rmap_item;
Izik Eidus31dbd012009-09-21 17:02:03 -0700290}
291
292static inline void free_rmap_item(struct rmap_item *rmap_item)
293{
Hugh Dickins473b0ce2009-09-21 17:02:11 -0700294 ksm_rmap_items--;
Izik Eidus31dbd012009-09-21 17:02:03 -0700295 rmap_item->mm = NULL; /* debug safety */
296 kmem_cache_free(rmap_item_cache, rmap_item);
297}
298
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800299static inline struct stable_node *alloc_stable_node(void)
300{
301 return kmem_cache_alloc(stable_node_cache, GFP_KERNEL);
302}
303
304static inline void free_stable_node(struct stable_node *stable_node)
305{
306 kmem_cache_free(stable_node_cache, stable_node);
307}
308
Izik Eidus31dbd012009-09-21 17:02:03 -0700309static inline struct mm_slot *alloc_mm_slot(void)
310{
311 if (!mm_slot_cache) /* initialization failed */
312 return NULL;
313 return kmem_cache_zalloc(mm_slot_cache, GFP_KERNEL);
314}
315
316static inline void free_mm_slot(struct mm_slot *mm_slot)
317{
318 kmem_cache_free(mm_slot_cache, mm_slot);
319}
320
Izik Eidus31dbd012009-09-21 17:02:03 -0700321static struct mm_slot *get_mm_slot(struct mm_struct *mm)
322{
Sasha Levin4ca3a692013-02-22 16:32:28 -0800323 struct mm_slot *slot;
Izik Eidus31dbd012009-09-21 17:02:03 -0700324
Sasha Levinb67bfe02013-02-27 17:06:00 -0800325 hash_for_each_possible(mm_slots_hash, slot, link, (unsigned long)mm)
Sasha Levin4ca3a692013-02-22 16:32:28 -0800326 if (slot->mm == mm)
327 return slot;
328
Izik Eidus31dbd012009-09-21 17:02:03 -0700329 return NULL;
330}
331
332static void insert_to_mm_slots_hash(struct mm_struct *mm,
333 struct mm_slot *mm_slot)
334{
Izik Eidus31dbd012009-09-21 17:02:03 -0700335 mm_slot->mm = mm;
Sasha Levin4ca3a692013-02-22 16:32:28 -0800336 hash_add(mm_slots_hash, &mm_slot->link, (unsigned long)mm);
Izik Eidus31dbd012009-09-21 17:02:03 -0700337}
338
Izik Eidus31dbd012009-09-21 17:02:03 -0700339/*
Hugh Dickinsa913e182009-09-21 17:02:26 -0700340 * ksmd, and unmerge_and_remove_all_rmap_items(), must not touch an mm's
341 * page tables after it has passed through ksm_exit() - which, if necessary,
342 * takes mmap_sem briefly to serialize against them. ksm_exit() does not set
343 * a special flag: they can just back out as soon as mm_users goes to zero.
344 * ksm_test_exit() is used throughout to make this test for exit: in some
345 * places for correctness, in some places just to avoid unnecessary work.
346 */
347static inline bool ksm_test_exit(struct mm_struct *mm)
348{
349 return atomic_read(&mm->mm_users) == 0;
350}
351
352/*
Izik Eidus31dbd012009-09-21 17:02:03 -0700353 * We use break_ksm to break COW on a ksm page: it's a stripped down
354 *
Dave Hansend4edcf02016-02-12 13:01:56 -0800355 * if (get_user_pages(addr, 1, 1, 1, &page, NULL) == 1)
Izik Eidus31dbd012009-09-21 17:02:03 -0700356 * put_page(page);
357 *
358 * but taking great care only to touch a ksm page, in a VM_MERGEABLE vma,
359 * in case the application has unmapped and remapped mm,addr meanwhile.
360 * Could a ksm page appear anywhere else? Actually yes, in a VM_PFNMAP
361 * mmap of /dev/mem or /dev/kmem, where we would not want to touch it.
Dave Hansen1b2ee122016-02-12 13:02:21 -0800362 *
363 * FAULT_FLAG/FOLL_REMOTE are because we do this outside the context
364 * of the process that owns 'vma'. We also do not want to enforce
365 * protection keys here anyway.
Izik Eidus31dbd012009-09-21 17:02:03 -0700366 */
Hugh Dickinsd952b792009-09-21 17:02:16 -0700367static int break_ksm(struct vm_area_struct *vma, unsigned long addr)
Izik Eidus31dbd012009-09-21 17:02:03 -0700368{
369 struct page *page;
Hugh Dickinsd952b792009-09-21 17:02:16 -0700370 int ret = 0;
Izik Eidus31dbd012009-09-21 17:02:03 -0700371
372 do {
373 cond_resched();
Dave Hansen1b2ee122016-02-12 13:02:21 -0800374 page = follow_page(vma, addr,
375 FOLL_GET | FOLL_MIGRATION | FOLL_REMOTE);
Dan Carpenter22eccdd2010-04-23 13:18:10 -0400376 if (IS_ERR_OR_NULL(page))
Izik Eidus31dbd012009-09-21 17:02:03 -0700377 break;
378 if (PageKsm(page))
Kirill A. Shutemovdcddffd2016-07-26 15:25:18 -0700379 ret = handle_mm_fault(vma, addr,
380 FAULT_FLAG_WRITE | FAULT_FLAG_REMOTE);
Izik Eidus31dbd012009-09-21 17:02:03 -0700381 else
382 ret = VM_FAULT_WRITE;
383 put_page(page);
Linus Torvalds33692f22015-01-29 10:51:32 -0800384 } while (!(ret & (VM_FAULT_WRITE | VM_FAULT_SIGBUS | VM_FAULT_SIGSEGV | VM_FAULT_OOM)));
Hugh Dickinsd952b792009-09-21 17:02:16 -0700385 /*
386 * We must loop because handle_mm_fault() may back out if there's
387 * any difficulty e.g. if pte accessed bit gets updated concurrently.
388 *
389 * VM_FAULT_WRITE is what we have been hoping for: it indicates that
390 * COW has been broken, even if the vma does not permit VM_WRITE;
391 * but note that a concurrent fault might break PageKsm for us.
392 *
393 * VM_FAULT_SIGBUS could occur if we race with truncation of the
394 * backing file, which also invalidates anonymous pages: that's
395 * okay, that truncation will have unmapped the PageKsm for us.
396 *
397 * VM_FAULT_OOM: at the time of writing (late July 2009), setting
398 * aside mem_cgroup limits, VM_FAULT_OOM would only be set if the
399 * current task has TIF_MEMDIE set, and will be OOM killed on return
400 * to user; and ksmd, having no mm, would never be chosen for that.
401 *
402 * But if the mm is in a limited mem_cgroup, then the fault may fail
403 * with VM_FAULT_OOM even if the current task is not TIF_MEMDIE; and
404 * even ksmd can fail in this way - though it's usually breaking ksm
405 * just to undo a merge it made a moment before, so unlikely to oom.
406 *
407 * That's a pity: we might therefore have more kernel pages allocated
408 * than we're counting as nodes in the stable tree; but ksm_do_scan
409 * will retry to break_cow on each pass, so should recover the page
410 * in due course. The important thing is to not let VM_MERGEABLE
411 * be cleared while any such pages might remain in the area.
412 */
413 return (ret & VM_FAULT_OOM) ? -ENOMEM : 0;
Izik Eidus31dbd012009-09-21 17:02:03 -0700414}
415
Bob Liuef694222012-03-21 16:34:11 -0700416static struct vm_area_struct *find_mergeable_vma(struct mm_struct *mm,
417 unsigned long addr)
418{
419 struct vm_area_struct *vma;
420 if (ksm_test_exit(mm))
421 return NULL;
422 vma = find_vma(mm, addr);
423 if (!vma || vma->vm_start > addr)
424 return NULL;
425 if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)
426 return NULL;
427 return vma;
428}
429
Hugh Dickins8dd35572009-12-14 17:59:18 -0800430static void break_cow(struct rmap_item *rmap_item)
Izik Eidus31dbd012009-09-21 17:02:03 -0700431{
Hugh Dickins8dd35572009-12-14 17:59:18 -0800432 struct mm_struct *mm = rmap_item->mm;
433 unsigned long addr = rmap_item->address;
Izik Eidus31dbd012009-09-21 17:02:03 -0700434 struct vm_area_struct *vma;
435
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800436 /*
437 * It is not an accident that whenever we want to break COW
438 * to undo, we also need to drop a reference to the anon_vma.
439 */
Peter Zijlstra9e601092011-03-22 16:32:46 -0700440 put_anon_vma(rmap_item->anon_vma);
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800441
Hugh Dickins81464e302009-09-21 17:02:15 -0700442 down_read(&mm->mmap_sem);
Bob Liuef694222012-03-21 16:34:11 -0700443 vma = find_mergeable_vma(mm, addr);
444 if (vma)
445 break_ksm(vma, addr);
Izik Eidus31dbd012009-09-21 17:02:03 -0700446 up_read(&mm->mmap_sem);
447}
448
449static struct page *get_mergeable_page(struct rmap_item *rmap_item)
450{
451 struct mm_struct *mm = rmap_item->mm;
452 unsigned long addr = rmap_item->address;
453 struct vm_area_struct *vma;
454 struct page *page;
455
456 down_read(&mm->mmap_sem);
Bob Liuef694222012-03-21 16:34:11 -0700457 vma = find_mergeable_vma(mm, addr);
458 if (!vma)
Izik Eidus31dbd012009-09-21 17:02:03 -0700459 goto out;
460
461 page = follow_page(vma, addr, FOLL_GET);
Dan Carpenter22eccdd2010-04-23 13:18:10 -0400462 if (IS_ERR_OR_NULL(page))
Izik Eidus31dbd012009-09-21 17:02:03 -0700463 goto out;
Kirill A. Shutemovf765f542016-01-15 16:53:03 -0800464 if (PageAnon(page)) {
Izik Eidus31dbd012009-09-21 17:02:03 -0700465 flush_anon_page(vma, page, addr);
466 flush_dcache_page(page);
467 } else {
468 put_page(page);
Andrea Arcangelic8f95ed2015-11-05 18:49:19 -0800469out:
470 page = NULL;
Izik Eidus31dbd012009-09-21 17:02:03 -0700471 }
472 up_read(&mm->mmap_sem);
473 return page;
474}
475
Petr Holasek90bd6fd2013-02-22 16:35:00 -0800476/*
477 * This helper is used for getting right index into array of tree roots.
478 * When merge_across_nodes knob is set to 1, there are only two rb-trees for
479 * stable and unstable pages from all nodes with roots in index 0. Otherwise,
480 * every node has its own stable and unstable tree.
481 */
482static inline int get_kpfn_nid(unsigned long kpfn)
483{
Hugh Dickinsd8fc16a2013-03-08 12:43:34 -0800484 return ksm_merge_across_nodes ? 0 : NUMA(pfn_to_nid(kpfn));
Petr Holasek90bd6fd2013-02-22 16:35:00 -0800485}
486
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800487static void remove_node_from_stable_tree(struct stable_node *stable_node)
488{
489 struct rmap_item *rmap_item;
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800490
Sasha Levinb67bfe02013-02-27 17:06:00 -0800491 hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) {
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800492 if (rmap_item->hlist.next)
493 ksm_pages_sharing--;
494 else
495 ksm_pages_shared--;
Peter Zijlstra9e601092011-03-22 16:32:46 -0700496 put_anon_vma(rmap_item->anon_vma);
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800497 rmap_item->address &= PAGE_MASK;
498 cond_resched();
499 }
500
Hugh Dickins4146d2d2013-02-22 16:35:11 -0800501 if (stable_node->head == &migrate_nodes)
502 list_del(&stable_node->list);
503 else
504 rb_erase(&stable_node->node,
Hugh Dickinsef53d162013-02-22 16:36:12 -0800505 root_stable_tree + NUMA(stable_node->nid));
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800506 free_stable_node(stable_node);
507}
508
509/*
510 * get_ksm_page: checks if the page indicated by the stable node
511 * is still its ksm page, despite having held no reference to it.
512 * In which case we can trust the content of the page, and it
513 * returns the gotten page; but if the page has now been zapped,
514 * remove the stale node from the stable tree and return NULL.
Hugh Dickinsc8d65532013-02-22 16:35:10 -0800515 * But beware, the stable node's page might be being migrated.
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800516 *
517 * You would expect the stable_node to hold a reference to the ksm page.
518 * But if it increments the page's count, swapping out has to wait for
519 * ksmd to come around again before it can free the page, which may take
520 * seconds or even minutes: much too unresponsive. So instead we use a
521 * "keyhole reference": access to the ksm page from the stable node peeps
522 * out through its keyhole to see if that page still holds the right key,
523 * pointing back to this stable node. This relies on freeing a PageAnon
524 * page to reset its page->mapping to NULL, and relies on no other use of
525 * a page to put something that might look like our key in page->mapping.
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800526 * is on its way to being freed; but it is an anomaly to bear in mind.
527 */
Hugh Dickins8fdb3db2013-02-22 16:36:03 -0800528static struct page *get_ksm_page(struct stable_node *stable_node, bool lock_it)
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800529{
530 struct page *page;
531 void *expected_mapping;
Hugh Dickinsc8d65532013-02-22 16:35:10 -0800532 unsigned long kpfn;
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800533
Minchan Kimbda807d2016-07-26 15:23:05 -0700534 expected_mapping = (void *)((unsigned long)stable_node |
535 PAGE_MAPPING_KSM);
Hugh Dickinsc8d65532013-02-22 16:35:10 -0800536again:
Jason Low4db0c3c2015-04-15 16:14:08 -0700537 kpfn = READ_ONCE(stable_node->kpfn);
Hugh Dickinsc8d65532013-02-22 16:35:10 -0800538 page = pfn_to_page(kpfn);
539
540 /*
541 * page is computed from kpfn, so on most architectures reading
542 * page->mapping is naturally ordered after reading node->kpfn,
543 * but on Alpha we need to be more careful.
544 */
545 smp_read_barrier_depends();
Jason Low4db0c3c2015-04-15 16:14:08 -0700546 if (READ_ONCE(page->mapping) != expected_mapping)
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800547 goto stale;
Hugh Dickinsc8d65532013-02-22 16:35:10 -0800548
549 /*
550 * We cannot do anything with the page while its refcount is 0.
551 * Usually 0 means free, or tail of a higher-order page: in which
552 * case this node is no longer referenced, and should be freed;
553 * however, it might mean that the page is under page_freeze_refs().
554 * The __remove_mapping() case is easy, again the node is now stale;
555 * but if page is swapcache in migrate_page_move_mapping(), it might
556 * still be our page, in which case it's essential to keep the node.
557 */
558 while (!get_page_unless_zero(page)) {
559 /*
560 * Another check for page->mapping != expected_mapping would
561 * work here too. We have chosen the !PageSwapCache test to
562 * optimize the common case, when the page is or is about to
563 * be freed: PageSwapCache is cleared (under spin_lock_irq)
564 * in the freeze_refs section of __remove_mapping(); but Anon
565 * page->mapping reset to NULL later, in free_pages_prepare().
566 */
567 if (!PageSwapCache(page))
568 goto stale;
569 cpu_relax();
570 }
571
Jason Low4db0c3c2015-04-15 16:14:08 -0700572 if (READ_ONCE(page->mapping) != expected_mapping) {
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800573 put_page(page);
574 goto stale;
575 }
Hugh Dickinsc8d65532013-02-22 16:35:10 -0800576
Hugh Dickins8fdb3db2013-02-22 16:36:03 -0800577 if (lock_it) {
Hugh Dickins8aafa6a2013-02-22 16:35:06 -0800578 lock_page(page);
Jason Low4db0c3c2015-04-15 16:14:08 -0700579 if (READ_ONCE(page->mapping) != expected_mapping) {
Hugh Dickins8aafa6a2013-02-22 16:35:06 -0800580 unlock_page(page);
581 put_page(page);
582 goto stale;
583 }
584 }
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800585 return page;
Hugh Dickinsc8d65532013-02-22 16:35:10 -0800586
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800587stale:
Hugh Dickinsc8d65532013-02-22 16:35:10 -0800588 /*
589 * We come here from above when page->mapping or !PageSwapCache
590 * suggests that the node is stale; but it might be under migration.
591 * We need smp_rmb(), matching the smp_wmb() in ksm_migrate_page(),
592 * before checking whether node->kpfn has been changed.
593 */
594 smp_rmb();
Jason Low4db0c3c2015-04-15 16:14:08 -0700595 if (READ_ONCE(stable_node->kpfn) != kpfn)
Hugh Dickinsc8d65532013-02-22 16:35:10 -0800596 goto again;
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800597 remove_node_from_stable_tree(stable_node);
598 return NULL;
599}
600
Izik Eidus31dbd012009-09-21 17:02:03 -0700601/*
Izik Eidus31dbd012009-09-21 17:02:03 -0700602 * Removing rmap_item from stable or unstable tree.
603 * This function will clean the information from the stable/unstable tree.
604 */
605static void remove_rmap_item_from_tree(struct rmap_item *rmap_item)
606{
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800607 if (rmap_item->address & STABLE_FLAG) {
608 struct stable_node *stable_node;
Hugh Dickins5ad64682009-12-14 17:59:24 -0800609 struct page *page;
Izik Eidus31dbd012009-09-21 17:02:03 -0700610
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800611 stable_node = rmap_item->head;
Hugh Dickins8aafa6a2013-02-22 16:35:06 -0800612 page = get_ksm_page(stable_node, true);
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800613 if (!page)
614 goto out;
615
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800616 hlist_del(&rmap_item->hlist);
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800617 unlock_page(page);
618 put_page(page);
Hugh Dickins08beca42009-12-14 17:59:21 -0800619
Andrea Arcangeli98666f8a2015-11-05 18:49:13 -0800620 if (!hlist_empty(&stable_node->hlist))
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800621 ksm_pages_sharing--;
622 else
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800623 ksm_pages_shared--;
Izik Eidus31dbd012009-09-21 17:02:03 -0700624
Peter Zijlstra9e601092011-03-22 16:32:46 -0700625 put_anon_vma(rmap_item->anon_vma);
Hugh Dickins93d17712009-12-14 17:59:16 -0800626 rmap_item->address &= PAGE_MASK;
Izik Eidus31dbd012009-09-21 17:02:03 -0700627
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -0800628 } else if (rmap_item->address & UNSTABLE_FLAG) {
Izik Eidus31dbd012009-09-21 17:02:03 -0700629 unsigned char age;
630 /*
Hugh Dickins9ba69292009-09-21 17:02:20 -0700631 * Usually ksmd can and must skip the rb_erase, because
Izik Eidus31dbd012009-09-21 17:02:03 -0700632 * root_unstable_tree was already reset to RB_ROOT.
Hugh Dickins9ba69292009-09-21 17:02:20 -0700633 * But be careful when an mm is exiting: do the rb_erase
634 * if this rmap_item was inserted by this scan, rather
635 * than left over from before.
Izik Eidus31dbd012009-09-21 17:02:03 -0700636 */
637 age = (unsigned char)(ksm_scan.seqnr - rmap_item->address);
Hugh Dickinscd551f92009-09-21 17:02:17 -0700638 BUG_ON(age > 1);
Izik Eidus31dbd012009-09-21 17:02:03 -0700639 if (!age)
Petr Holasek90bd6fd2013-02-22 16:35:00 -0800640 rb_erase(&rmap_item->node,
Hugh Dickinsef53d162013-02-22 16:36:12 -0800641 root_unstable_tree + NUMA(rmap_item->nid));
Hugh Dickins93d17712009-12-14 17:59:16 -0800642 ksm_pages_unshared--;
643 rmap_item->address &= PAGE_MASK;
644 }
Hugh Dickins4035c07a2009-12-14 17:59:27 -0800645out:
Izik Eidus31dbd012009-09-21 17:02:03 -0700646 cond_resched(); /* we're called from many long loops */
647}
648
Izik Eidus31dbd012009-09-21 17:02:03 -0700649static void remove_trailing_rmap_items(struct mm_slot *mm_slot,
Hugh Dickins6514d512009-12-14 17:59:19 -0800650 struct rmap_item **rmap_list)
Izik Eidus31dbd012009-09-21 17:02:03 -0700651{
Hugh Dickins6514d512009-12-14 17:59:19 -0800652 while (*rmap_list) {
653 struct rmap_item *rmap_item = *rmap_list;
654 *rmap_list = rmap_item->rmap_list;
Izik Eidus31dbd012009-09-21 17:02:03 -0700655 remove_rmap_item_from_tree(rmap_item);
Izik Eidus31dbd012009-09-21 17:02:03 -0700656 free_rmap_item(rmap_item);
657 }
658}
659
660/*
Hugh Dickinse850dcf2013-02-22 16:35:03 -0800661 * Though it's very tempting to unmerge rmap_items from stable tree rather
Izik Eidus31dbd012009-09-21 17:02:03 -0700662 * than check every pte of a given vma, the locking doesn't quite work for
663 * that - an rmap_item is assigned to the stable tree after inserting ksm
664 * page and upping mmap_sem. Nor does it fit with the way we skip dup'ing
665 * rmap_items from parent to child at fork time (so as not to waste time
666 * if exit comes before the next scan reaches it).
Hugh Dickins81464e302009-09-21 17:02:15 -0700667 *
668 * Similarly, although we'd like to remove rmap_items (so updating counts
669 * and freeing memory) when unmerging an area, it's easier to leave that
670 * to the next pass of ksmd - consider, for example, how ksmd might be
671 * in cmp_and_merge_page on one of the rmap_items we would be removing.
Izik Eidus31dbd012009-09-21 17:02:03 -0700672 */
Hugh Dickinsd952b792009-09-21 17:02:16 -0700673static int unmerge_ksm_pages(struct vm_area_struct *vma,
674 unsigned long start, unsigned long end)
Izik Eidus31dbd012009-09-21 17:02:03 -0700675{
676 unsigned long addr;
Hugh Dickinsd952b792009-09-21 17:02:16 -0700677 int err = 0;
Izik Eidus31dbd012009-09-21 17:02:03 -0700678
Hugh Dickinsd952b792009-09-21 17:02:16 -0700679 for (addr = start; addr < end && !err; addr += PAGE_SIZE) {
Hugh Dickins9ba69292009-09-21 17:02:20 -0700680 if (ksm_test_exit(vma->vm_mm))
681 break;
Hugh Dickinsd952b792009-09-21 17:02:16 -0700682 if (signal_pending(current))
683 err = -ERESTARTSYS;
684 else
685 err = break_ksm(vma, addr);
686 }
687 return err;
Izik Eidus31dbd012009-09-21 17:02:03 -0700688}
689
Hugh Dickins2ffd8672009-09-21 17:02:23 -0700690#ifdef CONFIG_SYSFS
691/*
692 * Only called through the sysfs control interface:
693 */
Hugh Dickinscbf86cf2013-02-22 16:35:08 -0800694static int remove_stable_node(struct stable_node *stable_node)
695{
696 struct page *page;
697 int err;
698
699 page = get_ksm_page(stable_node, true);
700 if (!page) {
701 /*
702 * get_ksm_page did remove_node_from_stable_tree itself.
703 */
704 return 0;
705 }
706
Hugh Dickins8fdb3db2013-02-22 16:36:03 -0800707 if (WARN_ON_ONCE(page_mapped(page))) {
Hugh Dickinscbf86cf2013-02-22 16:35:08 -0800708 /*
Hugh Dickins8fdb3db2013-02-22 16:36:03 -0800709 * This should not happen: but if it does, just refuse to let
710 * merge_across_nodes be switched - there is no need to panic.
711 */
712 err = -EBUSY;
713 } else {
714 /*
715 * The stable node did not yet appear stale to get_ksm_page(),
716 * since that allows for an unmapped ksm page to be recognized
717 * right up until it is freed; but the node is safe to remove.
Hugh Dickinscbf86cf2013-02-22 16:35:08 -0800718 * This page might be in a pagevec waiting to be freed,
719 * or it might be PageSwapCache (perhaps under writeback),
720 * or it might have been removed from swapcache a moment ago.
721 */
722 set_page_stable_node(page, NULL);
723 remove_node_from_stable_tree(stable_node);
724 err = 0;
725 }
726
727 unlock_page(page);
728 put_page(page);
729 return err;
730}
731
732static int remove_all_stable_nodes(void)
733{
Geliang Tang03640412016-01-14 15:20:54 -0800734 struct stable_node *stable_node, *next;
Hugh Dickinscbf86cf2013-02-22 16:35:08 -0800735 int nid;
736 int err = 0;
737
Hugh Dickinsef53d162013-02-22 16:36:12 -0800738 for (nid = 0; nid < ksm_nr_node_ids; nid++) {
Hugh Dickinscbf86cf2013-02-22 16:35:08 -0800739 while (root_stable_tree[nid].rb_node) {
740 stable_node = rb_entry(root_stable_tree[nid].rb_node,
741 struct stable_node, node);
742 if (remove_stable_node(stable_node)) {
743 err = -EBUSY;
744 break; /* proceed to next nid */
745 }
746 cond_resched();
747 }
748 }
Geliang Tang03640412016-01-14 15:20:54 -0800749 list_for_each_entry_safe(stable_node, next, &migrate_nodes, list) {
Hugh Dickins4146d2d2013-02-22 16:35:11 -0800750 if (remove_stable_node(stable_node))
751 err = -EBUSY;
752 cond_resched();
753 }
Hugh Dickinscbf86cf2013-02-22 16:35:08 -0800754 return err;
755}
756
Hugh Dickinsd952b792009-09-21 17:02:16 -0700757static int unmerge_and_remove_all_rmap_items(void)
Izik Eidus31dbd012009-09-21 17:02:03 -0700758{
759 struct mm_slot *mm_slot;
760 struct mm_struct *mm;
761 struct vm_area_struct *vma;
Hugh Dickinsd952b792009-09-21 17:02:16 -0700762 int err = 0;
Izik Eidus31dbd012009-09-21 17:02:03 -0700763
Hugh Dickinsd952b792009-09-21 17:02:16 -0700764 spin_lock(&ksm_mmlist_lock);
Hugh Dickins9ba69292009-09-21 17:02:20 -0700765 ksm_scan.mm_slot = list_entry(ksm_mm_head.mm_list.next,
Hugh Dickinsd952b792009-09-21 17:02:16 -0700766 struct mm_slot, mm_list);
767 spin_unlock(&ksm_mmlist_lock);
768
Hugh Dickins9ba69292009-09-21 17:02:20 -0700769 for (mm_slot = ksm_scan.mm_slot;
770 mm_slot != &ksm_mm_head; mm_slot = ksm_scan.mm_slot) {
Izik Eidus31dbd012009-09-21 17:02:03 -0700771 mm = mm_slot->mm;
772 down_read(&mm->mmap_sem);
773 for (vma = mm->mmap; vma; vma = vma->vm_next) {
Hugh Dickins9ba69292009-09-21 17:02:20 -0700774 if (ksm_test_exit(mm))
775 break;
Izik Eidus31dbd012009-09-21 17:02:03 -0700776 if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)
777 continue;
Hugh Dickinsd952b792009-09-21 17:02:16 -0700778 err = unmerge_ksm_pages(vma,
779 vma->vm_start, vma->vm_end);
Hugh Dickins9ba69292009-09-21 17:02:20 -0700780 if (err)
781 goto error;
Izik Eidus31dbd012009-09-21 17:02:03 -0700782 }
Hugh Dickins9ba69292009-09-21 17:02:20 -0700783
Hugh Dickins6514d512009-12-14 17:59:19 -0800784 remove_trailing_rmap_items(mm_slot, &mm_slot->rmap_list);
Zhou Chengming7496fea2016-05-12 15:42:21 -0700785 up_read(&mm->mmap_sem);
Hugh Dickinsd952b792009-09-21 17:02:16 -0700786
787 spin_lock(&ksm_mmlist_lock);
Hugh Dickins9ba69292009-09-21 17:02:20 -0700788 ksm_scan.mm_slot = list_entry(mm_slot->mm_list.next,
Hugh Dickinsd952b792009-09-21 17:02:16 -0700789 struct mm_slot, mm_list);
Hugh Dickins9ba69292009-09-21 17:02:20 -0700790 if (ksm_test_exit(mm)) {
Sasha Levin4ca3a692013-02-22 16:32:28 -0800791 hash_del(&mm_slot->link);
Hugh Dickins9ba69292009-09-21 17:02:20 -0700792 list_del(&mm_slot->mm_list);
793 spin_unlock(&ksm_mmlist_lock);
794
795 free_mm_slot(mm_slot);
796 clear_bit(MMF_VM_MERGEABLE, &mm->flags);
Hugh Dickins9ba69292009-09-21 17:02:20 -0700797 mmdrop(mm);
Zhou Chengming7496fea2016-05-12 15:42:21 -0700798 } else
Hugh Dickins9ba69292009-09-21 17:02:20 -0700799 spin_unlock(&ksm_mmlist_lock);
Izik Eidus31dbd012009-09-21 17:02:03 -0700800 }
801
Hugh Dickinscbf86cf2013-02-22 16:35:08 -0800802 /* Clean up stable nodes, but don't worry if some are still busy */
803 remove_all_stable_nodes();
Hugh Dickinsd952b792009-09-21 17:02:16 -0700804 ksm_scan.seqnr = 0;
Hugh Dickins9ba69292009-09-21 17:02:20 -0700805 return 0;
806
807error:
808 up_read(&mm->mmap_sem);
Izik Eidus31dbd012009-09-21 17:02:03 -0700809 spin_lock(&ksm_mmlist_lock);
Hugh Dickinsd952b792009-09-21 17:02:16 -0700810 ksm_scan.mm_slot = &ksm_mm_head;
Izik Eidus31dbd012009-09-21 17:02:03 -0700811 spin_unlock(&ksm_mmlist_lock);
Hugh Dickinsd952b792009-09-21 17:02:16 -0700812 return err;
Izik Eidus31dbd012009-09-21 17:02:03 -0700813}
Hugh Dickins2ffd8672009-09-21 17:02:23 -0700814#endif /* CONFIG_SYSFS */
Izik Eidus31dbd012009-09-21 17:02:03 -0700815
Izik Eidus31dbd012009-09-21 17:02:03 -0700816static u32 calc_checksum(struct page *page)
817{
818 u32 checksum;
Cong Wang9b04c5f2011-11-25 23:14:39 +0800819 void *addr = kmap_atomic(page);
Izik Eidus31dbd012009-09-21 17:02:03 -0700820 checksum = jhash2(addr, PAGE_SIZE / 4, 17);
Cong Wang9b04c5f2011-11-25 23:14:39 +0800821 kunmap_atomic(addr);
Izik Eidus31dbd012009-09-21 17:02:03 -0700822 return checksum;
823}
824
825static int memcmp_pages(struct page *page1, struct page *page2)
826{
827 char *addr1, *addr2;
828 int ret;
829
Cong Wang9b04c5f2011-11-25 23:14:39 +0800830 addr1 = kmap_atomic(page1);
831 addr2 = kmap_atomic(page2);
Izik Eidus31dbd012009-09-21 17:02:03 -0700832 ret = memcmp(addr1, addr2, PAGE_SIZE);
Cong Wang9b04c5f2011-11-25 23:14:39 +0800833 kunmap_atomic(addr2);
834 kunmap_atomic(addr1);
Izik Eidus31dbd012009-09-21 17:02:03 -0700835 return ret;
836}
837
838static inline int pages_identical(struct page *page1, struct page *page2)
839{
840 return !memcmp_pages(page1, page2);
841}
842
843static int write_protect_page(struct vm_area_struct *vma, struct page *page,
844 pte_t *orig_pte)
845{
846 struct mm_struct *mm = vma->vm_mm;
847 unsigned long addr;
848 pte_t *ptep;
849 spinlock_t *ptl;
850 int swapped;
851 int err = -EFAULT;
Haggai Eran6bdb9132012-10-08 16:33:35 -0700852 unsigned long mmun_start; /* For mmu_notifiers */
853 unsigned long mmun_end; /* For mmu_notifiers */
Izik Eidus31dbd012009-09-21 17:02:03 -0700854
855 addr = page_address_in_vma(page, vma);
856 if (addr == -EFAULT)
857 goto out;
858
Andrea Arcangeli29ad7682011-01-13 15:47:19 -0800859 BUG_ON(PageTransCompound(page));
Haggai Eran6bdb9132012-10-08 16:33:35 -0700860
861 mmun_start = addr;
862 mmun_end = addr + PAGE_SIZE;
863 mmu_notifier_invalidate_range_start(mm, mmun_start, mmun_end);
864
Izik Eidus31dbd012009-09-21 17:02:03 -0700865 ptep = page_check_address(page, mm, addr, &ptl, 0);
866 if (!ptep)
Haggai Eran6bdb9132012-10-08 16:33:35 -0700867 goto out_mn;
Izik Eidus31dbd012009-09-21 17:02:03 -0700868
Hugh Dickins4e316352010-10-02 17:49:08 -0700869 if (pte_write(*ptep) || pte_dirty(*ptep)) {
Izik Eidus31dbd012009-09-21 17:02:03 -0700870 pte_t entry;
871
872 swapped = PageSwapCache(page);
873 flush_cache_page(vma, addr, page_to_pfn(page));
874 /*
Lucas De Marchi25985ed2011-03-30 22:57:33 -0300875 * Ok this is tricky, when get_user_pages_fast() run it doesn't
Izik Eidus31dbd012009-09-21 17:02:03 -0700876 * take any lock, therefore the check that we are going to make
877 * with the pagecount against the mapcount is racey and
878 * O_DIRECT can happen right after the check.
879 * So we clear the pte and flush the tlb before the check
880 * this assure us that no O_DIRECT can happen after the check
881 * or in the middle of the check.
882 */
Joerg Roedel34ee6452014-11-13 13:46:09 +1100883 entry = ptep_clear_flush_notify(vma, addr, ptep);
Izik Eidus31dbd012009-09-21 17:02:03 -0700884 /*
885 * Check that no O_DIRECT or similar I/O is in progress on the
886 * page
887 */
Hugh Dickins31e855e2009-12-14 17:59:17 -0800888 if (page_mapcount(page) + 1 + swapped != page_count(page)) {
Robin Holtcb532372010-03-23 13:35:26 -0700889 set_pte_at(mm, addr, ptep, entry);
Izik Eidus31dbd012009-09-21 17:02:03 -0700890 goto out_unlock;
891 }
Hugh Dickins4e316352010-10-02 17:49:08 -0700892 if (pte_dirty(entry))
893 set_page_dirty(page);
894 entry = pte_mkclean(pte_wrprotect(entry));
Izik Eidus31dbd012009-09-21 17:02:03 -0700895 set_pte_at_notify(mm, addr, ptep, entry);
896 }
897 *orig_pte = *ptep;
898 err = 0;
899
900out_unlock:
901 pte_unmap_unlock(ptep, ptl);
Haggai Eran6bdb9132012-10-08 16:33:35 -0700902out_mn:
903 mmu_notifier_invalidate_range_end(mm, mmun_start, mmun_end);
Izik Eidus31dbd012009-09-21 17:02:03 -0700904out:
905 return err;
906}
907
908/**
909 * replace_page - replace page in vma by new ksm page
Hugh Dickins8dd35572009-12-14 17:59:18 -0800910 * @vma: vma that holds the pte pointing to page
911 * @page: the page we are replacing by kpage
912 * @kpage: the ksm page we replace page by
Izik Eidus31dbd012009-09-21 17:02:03 -0700913 * @orig_pte: the original value of the pte
914 *
915 * Returns 0 on success, -EFAULT on failure.
916 */
Hugh Dickins8dd35572009-12-14 17:59:18 -0800917static int replace_page(struct vm_area_struct *vma, struct page *page,
918 struct page *kpage, pte_t orig_pte)
Izik Eidus31dbd012009-09-21 17:02:03 -0700919{
920 struct mm_struct *mm = vma->vm_mm;
Izik Eidus31dbd012009-09-21 17:02:03 -0700921 pmd_t *pmd;
922 pte_t *ptep;
923 spinlock_t *ptl;
924 unsigned long addr;
Izik Eidus31dbd012009-09-21 17:02:03 -0700925 int err = -EFAULT;
Haggai Eran6bdb9132012-10-08 16:33:35 -0700926 unsigned long mmun_start; /* For mmu_notifiers */
927 unsigned long mmun_end; /* For mmu_notifiers */
Izik Eidus31dbd012009-09-21 17:02:03 -0700928
Hugh Dickins8dd35572009-12-14 17:59:18 -0800929 addr = page_address_in_vma(page, vma);
Izik Eidus31dbd012009-09-21 17:02:03 -0700930 if (addr == -EFAULT)
931 goto out;
932
Bob Liu62190492012-12-11 16:00:37 -0800933 pmd = mm_find_pmd(mm, addr);
934 if (!pmd)
Izik Eidus31dbd012009-09-21 17:02:03 -0700935 goto out;
Izik Eidus31dbd012009-09-21 17:02:03 -0700936
Haggai Eran6bdb9132012-10-08 16:33:35 -0700937 mmun_start = addr;
938 mmun_end = addr + PAGE_SIZE;
939 mmu_notifier_invalidate_range_start(mm, mmun_start, mmun_end);
940
Izik Eidus31dbd012009-09-21 17:02:03 -0700941 ptep = pte_offset_map_lock(mm, pmd, addr, &ptl);
942 if (!pte_same(*ptep, orig_pte)) {
943 pte_unmap_unlock(ptep, ptl);
Haggai Eran6bdb9132012-10-08 16:33:35 -0700944 goto out_mn;
Izik Eidus31dbd012009-09-21 17:02:03 -0700945 }
946
Hugh Dickins8dd35572009-12-14 17:59:18 -0800947 get_page(kpage);
Kirill A. Shutemovd281ee62016-01-15 16:52:16 -0800948 page_add_anon_rmap(kpage, vma, addr, false);
Izik Eidus31dbd012009-09-21 17:02:03 -0700949
950 flush_cache_page(vma, addr, pte_pfn(*ptep));
Joerg Roedel34ee6452014-11-13 13:46:09 +1100951 ptep_clear_flush_notify(vma, addr, ptep);
Hugh Dickins8dd35572009-12-14 17:59:18 -0800952 set_pte_at_notify(mm, addr, ptep, mk_pte(kpage, vma->vm_page_prot));
Izik Eidus31dbd012009-09-21 17:02:03 -0700953
Kirill A. Shutemovd281ee62016-01-15 16:52:16 -0800954 page_remove_rmap(page, false);
Hugh Dickinsae52a2a2011-01-13 15:46:28 -0800955 if (!page_mapped(page))
956 try_to_free_swap(page);
Hugh Dickins8dd35572009-12-14 17:59:18 -0800957 put_page(page);
Izik Eidus31dbd012009-09-21 17:02:03 -0700958
959 pte_unmap_unlock(ptep, ptl);
960 err = 0;
Haggai Eran6bdb9132012-10-08 16:33:35 -0700961out_mn:
962 mmu_notifier_invalidate_range_end(mm, mmun_start, mmun_end);
Izik Eidus31dbd012009-09-21 17:02:03 -0700963out:
964 return err;
965}
966
967/*
968 * try_to_merge_one_page - take two pages and merge them into one
Hugh Dickins8dd35572009-12-14 17:59:18 -0800969 * @vma: the vma that holds the pte pointing to page
970 * @page: the PageAnon page that we want to replace with kpage
Hugh Dickins80e148222009-12-14 17:59:29 -0800971 * @kpage: the PageKsm page that we want to map instead of page,
972 * or NULL the first time when we want to use page as kpage.
Izik Eidus31dbd012009-09-21 17:02:03 -0700973 *
974 * This function returns 0 if the pages were merged, -EFAULT otherwise.
975 */
976static int try_to_merge_one_page(struct vm_area_struct *vma,
Hugh Dickins8dd35572009-12-14 17:59:18 -0800977 struct page *page, struct page *kpage)
Izik Eidus31dbd012009-09-21 17:02:03 -0700978{
979 pte_t orig_pte = __pte(0);
980 int err = -EFAULT;
981
Hugh Dickinsdb114b82009-12-14 17:59:25 -0800982 if (page == kpage) /* ksm page forked */
983 return 0;
984
Hugh Dickins8dd35572009-12-14 17:59:18 -0800985 if (!PageAnon(page))
Izik Eidus31dbd012009-09-21 17:02:03 -0700986 goto out;
987
Izik Eidus31dbd012009-09-21 17:02:03 -0700988 /*
989 * We need the page lock to read a stable PageSwapCache in
990 * write_protect_page(). We use trylock_page() instead of
991 * lock_page() because we don't want to wait here - we
992 * prefer to continue scanning and merging different pages,
993 * then come back to this page when it is unlocked.
994 */
Hugh Dickins8dd35572009-12-14 17:59:18 -0800995 if (!trylock_page(page))
Hugh Dickins31e855e2009-12-14 17:59:17 -0800996 goto out;
Kirill A. Shutemovf765f542016-01-15 16:53:03 -0800997
998 if (PageTransCompound(page)) {
999 err = split_huge_page(page);
1000 if (err)
1001 goto out_unlock;
1002 }
1003
Izik Eidus31dbd012009-09-21 17:02:03 -07001004 /*
1005 * If this anonymous page is mapped only here, its pte may need
1006 * to be write-protected. If it's mapped elsewhere, all of its
1007 * ptes are necessarily already write-protected. But in either
1008 * case, we need to lock and check page_count is not raised.
1009 */
Hugh Dickins80e148222009-12-14 17:59:29 -08001010 if (write_protect_page(vma, page, &orig_pte) == 0) {
1011 if (!kpage) {
1012 /*
1013 * While we hold page lock, upgrade page from
1014 * PageAnon+anon_vma to PageKsm+NULL stable_node:
1015 * stable_tree_insert() will update stable_node.
1016 */
1017 set_page_stable_node(page, NULL);
1018 mark_page_accessed(page);
Minchan Kim337ed7e2016-01-15 16:55:15 -08001019 /*
1020 * Page reclaim just frees a clean page with no dirty
1021 * ptes: make sure that the ksm page would be swapped.
1022 */
1023 if (!PageDirty(page))
1024 SetPageDirty(page);
Hugh Dickins80e148222009-12-14 17:59:29 -08001025 err = 0;
1026 } else if (pages_identical(page, kpage))
1027 err = replace_page(vma, page, kpage, orig_pte);
1028 }
Izik Eidus31dbd012009-09-21 17:02:03 -07001029
Hugh Dickins80e148222009-12-14 17:59:29 -08001030 if ((vma->vm_flags & VM_LOCKED) && kpage && !err) {
Hugh Dickins73848b42009-12-14 17:59:22 -08001031 munlock_vma_page(page);
Hugh Dickins5ad64682009-12-14 17:59:24 -08001032 if (!PageMlocked(kpage)) {
1033 unlock_page(page);
Hugh Dickins5ad64682009-12-14 17:59:24 -08001034 lock_page(kpage);
1035 mlock_vma_page(kpage);
1036 page = kpage; /* for final unlock */
1037 }
1038 }
Hugh Dickins73848b42009-12-14 17:59:22 -08001039
Kirill A. Shutemovf765f542016-01-15 16:53:03 -08001040out_unlock:
Hugh Dickins8dd35572009-12-14 17:59:18 -08001041 unlock_page(page);
Izik Eidus31dbd012009-09-21 17:02:03 -07001042out:
1043 return err;
1044}
1045
1046/*
Hugh Dickins81464e302009-09-21 17:02:15 -07001047 * try_to_merge_with_ksm_page - like try_to_merge_two_pages,
1048 * but no new kernel page is allocated: kpage must already be a ksm page.
Hugh Dickins8dd35572009-12-14 17:59:18 -08001049 *
1050 * This function returns 0 if the pages were merged, -EFAULT otherwise.
Hugh Dickins81464e302009-09-21 17:02:15 -07001051 */
Hugh Dickins8dd35572009-12-14 17:59:18 -08001052static int try_to_merge_with_ksm_page(struct rmap_item *rmap_item,
1053 struct page *page, struct page *kpage)
Hugh Dickins81464e302009-09-21 17:02:15 -07001054{
Hugh Dickins8dd35572009-12-14 17:59:18 -08001055 struct mm_struct *mm = rmap_item->mm;
Hugh Dickins81464e302009-09-21 17:02:15 -07001056 struct vm_area_struct *vma;
1057 int err = -EFAULT;
1058
Hugh Dickins8dd35572009-12-14 17:59:18 -08001059 down_read(&mm->mmap_sem);
Andrea Arcangeli85c6e8d2015-11-05 18:49:16 -08001060 vma = find_mergeable_vma(mm, rmap_item->address);
1061 if (!vma)
Hugh Dickins9ba69292009-09-21 17:02:20 -07001062 goto out;
1063
Hugh Dickins8dd35572009-12-14 17:59:18 -08001064 err = try_to_merge_one_page(vma, page, kpage);
Hugh Dickinsdb114b82009-12-14 17:59:25 -08001065 if (err)
1066 goto out;
1067
Hugh Dickinsbc566202013-02-22 16:36:06 -08001068 /* Unstable nid is in union with stable anon_vma: remove first */
1069 remove_rmap_item_from_tree(rmap_item);
1070
Hugh Dickinsdb114b82009-12-14 17:59:25 -08001071 /* Must get reference to anon_vma while still holding mmap_sem */
Peter Zijlstra9e601092011-03-22 16:32:46 -07001072 rmap_item->anon_vma = vma->anon_vma;
1073 get_anon_vma(vma->anon_vma);
Hugh Dickins81464e302009-09-21 17:02:15 -07001074out:
Hugh Dickins8dd35572009-12-14 17:59:18 -08001075 up_read(&mm->mmap_sem);
Hugh Dickins81464e302009-09-21 17:02:15 -07001076 return err;
1077}
1078
1079/*
Izik Eidus31dbd012009-09-21 17:02:03 -07001080 * try_to_merge_two_pages - take two identical pages and prepare them
1081 * to be merged into one page.
1082 *
Hugh Dickins8dd35572009-12-14 17:59:18 -08001083 * This function returns the kpage if we successfully merged two identical
1084 * pages into one ksm page, NULL otherwise.
Izik Eidus31dbd012009-09-21 17:02:03 -07001085 *
Hugh Dickins80e148222009-12-14 17:59:29 -08001086 * Note that this function upgrades page to ksm page: if one of the pages
Izik Eidus31dbd012009-09-21 17:02:03 -07001087 * is already a ksm page, try_to_merge_with_ksm_page should be used.
1088 */
Hugh Dickins8dd35572009-12-14 17:59:18 -08001089static struct page *try_to_merge_two_pages(struct rmap_item *rmap_item,
1090 struct page *page,
1091 struct rmap_item *tree_rmap_item,
1092 struct page *tree_page)
Izik Eidus31dbd012009-09-21 17:02:03 -07001093{
Hugh Dickins80e148222009-12-14 17:59:29 -08001094 int err;
Izik Eidus31dbd012009-09-21 17:02:03 -07001095
Hugh Dickins80e148222009-12-14 17:59:29 -08001096 err = try_to_merge_with_ksm_page(rmap_item, page, NULL);
Izik Eidus31dbd012009-09-21 17:02:03 -07001097 if (!err) {
Hugh Dickins8dd35572009-12-14 17:59:18 -08001098 err = try_to_merge_with_ksm_page(tree_rmap_item,
Hugh Dickins80e148222009-12-14 17:59:29 -08001099 tree_page, page);
Izik Eidus31dbd012009-09-21 17:02:03 -07001100 /*
Hugh Dickins81464e302009-09-21 17:02:15 -07001101 * If that fails, we have a ksm page with only one pte
1102 * pointing to it: so break it.
Izik Eidus31dbd012009-09-21 17:02:03 -07001103 */
Hugh Dickins4035c07a2009-12-14 17:59:27 -08001104 if (err)
Hugh Dickins8dd35572009-12-14 17:59:18 -08001105 break_cow(rmap_item);
Izik Eidus31dbd012009-09-21 17:02:03 -07001106 }
Hugh Dickins80e148222009-12-14 17:59:29 -08001107 return err ? NULL : page;
Izik Eidus31dbd012009-09-21 17:02:03 -07001108}
1109
1110/*
Hugh Dickins8dd35572009-12-14 17:59:18 -08001111 * stable_tree_search - search for page inside the stable tree
Izik Eidus31dbd012009-09-21 17:02:03 -07001112 *
1113 * This function checks if there is a page inside the stable tree
1114 * with identical content to the page that we are scanning right now.
1115 *
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001116 * This function returns the stable tree node of identical content if found,
Izik Eidus31dbd012009-09-21 17:02:03 -07001117 * NULL otherwise.
1118 */
Hugh Dickins62b61f62009-12-14 17:59:33 -08001119static struct page *stable_tree_search(struct page *page)
Izik Eidus31dbd012009-09-21 17:02:03 -07001120{
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001121 int nid;
Hugh Dickinsef53d162013-02-22 16:36:12 -08001122 struct rb_root *root;
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001123 struct rb_node **new;
1124 struct rb_node *parent;
1125 struct stable_node *stable_node;
1126 struct stable_node *page_node;
Izik Eidus31dbd012009-09-21 17:02:03 -07001127
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001128 page_node = page_stable_node(page);
1129 if (page_node && page_node->head != &migrate_nodes) {
1130 /* ksm page forked */
Hugh Dickins08beca42009-12-14 17:59:21 -08001131 get_page(page);
Hugh Dickins62b61f62009-12-14 17:59:33 -08001132 return page;
Hugh Dickins08beca42009-12-14 17:59:21 -08001133 }
1134
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001135 nid = get_kpfn_nid(page_to_pfn(page));
Hugh Dickinsef53d162013-02-22 16:36:12 -08001136 root = root_stable_tree + nid;
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001137again:
Hugh Dickinsef53d162013-02-22 16:36:12 -08001138 new = &root->rb_node;
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001139 parent = NULL;
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001140
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001141 while (*new) {
Hugh Dickins4035c07a2009-12-14 17:59:27 -08001142 struct page *tree_page;
Izik Eidus31dbd012009-09-21 17:02:03 -07001143 int ret;
1144
Hugh Dickins08beca42009-12-14 17:59:21 -08001145 cond_resched();
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001146 stable_node = rb_entry(*new, struct stable_node, node);
Hugh Dickins8aafa6a2013-02-22 16:35:06 -08001147 tree_page = get_ksm_page(stable_node, false);
Andrea Arcangelif2e5ff82015-11-05 18:49:10 -08001148 if (!tree_page) {
1149 /*
1150 * If we walked over a stale stable_node,
1151 * get_ksm_page() will call rb_erase() and it
1152 * may rebalance the tree from under us. So
1153 * restart the search from scratch. Returning
1154 * NULL would be safe too, but we'd generate
1155 * false negative insertions just because some
1156 * stable_node was stale.
1157 */
1158 goto again;
1159 }
Izik Eidus31dbd012009-09-21 17:02:03 -07001160
Hugh Dickins4035c07a2009-12-14 17:59:27 -08001161 ret = memcmp_pages(page, tree_page);
Hugh Dickinsc8d65532013-02-22 16:35:10 -08001162 put_page(tree_page);
Izik Eidus31dbd012009-09-21 17:02:03 -07001163
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001164 parent = *new;
Hugh Dickinsc8d65532013-02-22 16:35:10 -08001165 if (ret < 0)
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001166 new = &parent->rb_left;
Hugh Dickinsc8d65532013-02-22 16:35:10 -08001167 else if (ret > 0)
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001168 new = &parent->rb_right;
Hugh Dickinsc8d65532013-02-22 16:35:10 -08001169 else {
1170 /*
1171 * Lock and unlock the stable_node's page (which
1172 * might already have been migrated) so that page
1173 * migration is sure to notice its raised count.
1174 * It would be more elegant to return stable_node
1175 * than kpage, but that involves more changes.
1176 */
1177 tree_page = get_ksm_page(stable_node, true);
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001178 if (tree_page) {
Hugh Dickinsc8d65532013-02-22 16:35:10 -08001179 unlock_page(tree_page);
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001180 if (get_kpfn_nid(stable_node->kpfn) !=
1181 NUMA(stable_node->nid)) {
1182 put_page(tree_page);
1183 goto replace;
1184 }
1185 return tree_page;
1186 }
1187 /*
1188 * There is now a place for page_node, but the tree may
1189 * have been rebalanced, so re-evaluate parent and new.
1190 */
1191 if (page_node)
1192 goto again;
1193 return NULL;
Hugh Dickinsc8d65532013-02-22 16:35:10 -08001194 }
Izik Eidus31dbd012009-09-21 17:02:03 -07001195 }
1196
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001197 if (!page_node)
1198 return NULL;
1199
1200 list_del(&page_node->list);
1201 DO_NUMA(page_node->nid = nid);
1202 rb_link_node(&page_node->node, parent, new);
Hugh Dickinsef53d162013-02-22 16:36:12 -08001203 rb_insert_color(&page_node->node, root);
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001204 get_page(page);
1205 return page;
1206
1207replace:
1208 if (page_node) {
1209 list_del(&page_node->list);
1210 DO_NUMA(page_node->nid = nid);
Hugh Dickinsef53d162013-02-22 16:36:12 -08001211 rb_replace_node(&stable_node->node, &page_node->node, root);
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001212 get_page(page);
1213 } else {
Hugh Dickinsef53d162013-02-22 16:36:12 -08001214 rb_erase(&stable_node->node, root);
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001215 page = NULL;
1216 }
1217 stable_node->head = &migrate_nodes;
1218 list_add(&stable_node->list, stable_node->head);
1219 return page;
Izik Eidus31dbd012009-09-21 17:02:03 -07001220}
1221
1222/*
Hugh Dickinse850dcf2013-02-22 16:35:03 -08001223 * stable_tree_insert - insert stable tree node pointing to new ksm page
Izik Eidus31dbd012009-09-21 17:02:03 -07001224 * into the stable tree.
1225 *
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001226 * This function returns the stable tree node just allocated on success,
1227 * NULL otherwise.
Izik Eidus31dbd012009-09-21 17:02:03 -07001228 */
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001229static struct stable_node *stable_tree_insert(struct page *kpage)
Izik Eidus31dbd012009-09-21 17:02:03 -07001230{
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001231 int nid;
1232 unsigned long kpfn;
Hugh Dickinsef53d162013-02-22 16:36:12 -08001233 struct rb_root *root;
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001234 struct rb_node **new;
Andrea Arcangelif2e5ff82015-11-05 18:49:10 -08001235 struct rb_node *parent;
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001236 struct stable_node *stable_node;
Izik Eidus31dbd012009-09-21 17:02:03 -07001237
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001238 kpfn = page_to_pfn(kpage);
1239 nid = get_kpfn_nid(kpfn);
Hugh Dickinsef53d162013-02-22 16:36:12 -08001240 root = root_stable_tree + nid;
Andrea Arcangelif2e5ff82015-11-05 18:49:10 -08001241again:
1242 parent = NULL;
Hugh Dickinsef53d162013-02-22 16:36:12 -08001243 new = &root->rb_node;
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001244
Izik Eidus31dbd012009-09-21 17:02:03 -07001245 while (*new) {
Hugh Dickins4035c07a2009-12-14 17:59:27 -08001246 struct page *tree_page;
Izik Eidus31dbd012009-09-21 17:02:03 -07001247 int ret;
1248
Hugh Dickins08beca42009-12-14 17:59:21 -08001249 cond_resched();
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001250 stable_node = rb_entry(*new, struct stable_node, node);
Hugh Dickins8aafa6a2013-02-22 16:35:06 -08001251 tree_page = get_ksm_page(stable_node, false);
Andrea Arcangelif2e5ff82015-11-05 18:49:10 -08001252 if (!tree_page) {
1253 /*
1254 * If we walked over a stale stable_node,
1255 * get_ksm_page() will call rb_erase() and it
1256 * may rebalance the tree from under us. So
1257 * restart the search from scratch. Returning
1258 * NULL would be safe too, but we'd generate
1259 * false negative insertions just because some
1260 * stable_node was stale.
1261 */
1262 goto again;
1263 }
Izik Eidus31dbd012009-09-21 17:02:03 -07001264
Hugh Dickins4035c07a2009-12-14 17:59:27 -08001265 ret = memcmp_pages(kpage, tree_page);
1266 put_page(tree_page);
Izik Eidus31dbd012009-09-21 17:02:03 -07001267
1268 parent = *new;
1269 if (ret < 0)
1270 new = &parent->rb_left;
1271 else if (ret > 0)
1272 new = &parent->rb_right;
1273 else {
1274 /*
1275 * It is not a bug that stable_tree_search() didn't
1276 * find this node: because at that time our page was
1277 * not yet write-protected, so may have changed since.
1278 */
1279 return NULL;
1280 }
1281 }
1282
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001283 stable_node = alloc_stable_node();
1284 if (!stable_node)
1285 return NULL;
Izik Eidus31dbd012009-09-21 17:02:03 -07001286
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001287 INIT_HLIST_HEAD(&stable_node->hlist);
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001288 stable_node->kpfn = kpfn;
Hugh Dickins08beca42009-12-14 17:59:21 -08001289 set_page_stable_node(kpage, stable_node);
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001290 DO_NUMA(stable_node->nid = nid);
Hugh Dickinse850dcf2013-02-22 16:35:03 -08001291 rb_link_node(&stable_node->node, parent, new);
Hugh Dickinsef53d162013-02-22 16:36:12 -08001292 rb_insert_color(&stable_node->node, root);
Hugh Dickins08beca42009-12-14 17:59:21 -08001293
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001294 return stable_node;
Izik Eidus31dbd012009-09-21 17:02:03 -07001295}
1296
1297/*
Hugh Dickins8dd35572009-12-14 17:59:18 -08001298 * unstable_tree_search_insert - search for identical page,
1299 * else insert rmap_item into the unstable tree.
Izik Eidus31dbd012009-09-21 17:02:03 -07001300 *
1301 * This function searches for a page in the unstable tree identical to the
1302 * page currently being scanned; and if no identical page is found in the
1303 * tree, we insert rmap_item as a new object into the unstable tree.
1304 *
1305 * This function returns pointer to rmap_item found to be identical
1306 * to the currently scanned page, NULL otherwise.
1307 *
1308 * This function does both searching and inserting, because they share
1309 * the same walking algorithm in an rbtree.
1310 */
Hugh Dickins8dd35572009-12-14 17:59:18 -08001311static
1312struct rmap_item *unstable_tree_search_insert(struct rmap_item *rmap_item,
1313 struct page *page,
1314 struct page **tree_pagep)
Izik Eidus31dbd012009-09-21 17:02:03 -07001315{
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001316 struct rb_node **new;
1317 struct rb_root *root;
Izik Eidus31dbd012009-09-21 17:02:03 -07001318 struct rb_node *parent = NULL;
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001319 int nid;
1320
1321 nid = get_kpfn_nid(page_to_pfn(page));
Hugh Dickinsef53d162013-02-22 16:36:12 -08001322 root = root_unstable_tree + nid;
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001323 new = &root->rb_node;
Izik Eidus31dbd012009-09-21 17:02:03 -07001324
1325 while (*new) {
1326 struct rmap_item *tree_rmap_item;
Hugh Dickins8dd35572009-12-14 17:59:18 -08001327 struct page *tree_page;
Izik Eidus31dbd012009-09-21 17:02:03 -07001328 int ret;
1329
Hugh Dickinsd178f272009-11-09 15:58:23 +00001330 cond_resched();
Izik Eidus31dbd012009-09-21 17:02:03 -07001331 tree_rmap_item = rb_entry(*new, struct rmap_item, node);
Hugh Dickins8dd35572009-12-14 17:59:18 -08001332 tree_page = get_mergeable_page(tree_rmap_item);
Andrea Arcangelic8f95ed2015-11-05 18:49:19 -08001333 if (!tree_page)
Izik Eidus31dbd012009-09-21 17:02:03 -07001334 return NULL;
1335
1336 /*
Hugh Dickins8dd35572009-12-14 17:59:18 -08001337 * Don't substitute a ksm page for a forked page.
Izik Eidus31dbd012009-09-21 17:02:03 -07001338 */
Hugh Dickins8dd35572009-12-14 17:59:18 -08001339 if (page == tree_page) {
1340 put_page(tree_page);
Izik Eidus31dbd012009-09-21 17:02:03 -07001341 return NULL;
1342 }
1343
Hugh Dickins8dd35572009-12-14 17:59:18 -08001344 ret = memcmp_pages(page, tree_page);
Izik Eidus31dbd012009-09-21 17:02:03 -07001345
1346 parent = *new;
1347 if (ret < 0) {
Hugh Dickins8dd35572009-12-14 17:59:18 -08001348 put_page(tree_page);
Izik Eidus31dbd012009-09-21 17:02:03 -07001349 new = &parent->rb_left;
1350 } else if (ret > 0) {
Hugh Dickins8dd35572009-12-14 17:59:18 -08001351 put_page(tree_page);
Izik Eidus31dbd012009-09-21 17:02:03 -07001352 new = &parent->rb_right;
Hugh Dickinsb599cbd2013-02-22 16:36:05 -08001353 } else if (!ksm_merge_across_nodes &&
1354 page_to_nid(tree_page) != nid) {
1355 /*
1356 * If tree_page has been migrated to another NUMA node,
1357 * it will be flushed out and put in the right unstable
1358 * tree next time: only merge with it when across_nodes.
1359 */
1360 put_page(tree_page);
1361 return NULL;
Izik Eidus31dbd012009-09-21 17:02:03 -07001362 } else {
Hugh Dickins8dd35572009-12-14 17:59:18 -08001363 *tree_pagep = tree_page;
Izik Eidus31dbd012009-09-21 17:02:03 -07001364 return tree_rmap_item;
1365 }
1366 }
1367
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001368 rmap_item->address |= UNSTABLE_FLAG;
Izik Eidus31dbd012009-09-21 17:02:03 -07001369 rmap_item->address |= (ksm_scan.seqnr & SEQNR_MASK);
Hugh Dickinse850dcf2013-02-22 16:35:03 -08001370 DO_NUMA(rmap_item->nid = nid);
Izik Eidus31dbd012009-09-21 17:02:03 -07001371 rb_link_node(&rmap_item->node, parent, new);
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001372 rb_insert_color(&rmap_item->node, root);
Izik Eidus31dbd012009-09-21 17:02:03 -07001373
Hugh Dickins473b0ce2009-09-21 17:02:11 -07001374 ksm_pages_unshared++;
Izik Eidus31dbd012009-09-21 17:02:03 -07001375 return NULL;
1376}
1377
1378/*
1379 * stable_tree_append - add another rmap_item to the linked list of
1380 * rmap_items hanging off a given node of the stable tree, all sharing
1381 * the same ksm page.
1382 */
1383static void stable_tree_append(struct rmap_item *rmap_item,
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001384 struct stable_node *stable_node)
Izik Eidus31dbd012009-09-21 17:02:03 -07001385{
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001386 rmap_item->head = stable_node;
Izik Eidus31dbd012009-09-21 17:02:03 -07001387 rmap_item->address |= STABLE_FLAG;
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001388 hlist_add_head(&rmap_item->hlist, &stable_node->hlist);
Hugh Dickinse178dfd2009-09-21 17:02:10 -07001389
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001390 if (rmap_item->hlist.next)
1391 ksm_pages_sharing++;
1392 else
1393 ksm_pages_shared++;
Izik Eidus31dbd012009-09-21 17:02:03 -07001394}
1395
1396/*
Hugh Dickins81464e302009-09-21 17:02:15 -07001397 * cmp_and_merge_page - first see if page can be merged into the stable tree;
1398 * if not, compare checksum to previous and if it's the same, see if page can
1399 * be inserted into the unstable tree, or merged with a page already there and
1400 * both transferred to the stable tree.
Izik Eidus31dbd012009-09-21 17:02:03 -07001401 *
1402 * @page: the page that we are searching identical page to.
1403 * @rmap_item: the reverse mapping into the virtual address of this page
1404 */
1405static void cmp_and_merge_page(struct page *page, struct rmap_item *rmap_item)
1406{
Izik Eidus31dbd012009-09-21 17:02:03 -07001407 struct rmap_item *tree_rmap_item;
Hugh Dickins8dd35572009-12-14 17:59:18 -08001408 struct page *tree_page = NULL;
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001409 struct stable_node *stable_node;
Hugh Dickins8dd35572009-12-14 17:59:18 -08001410 struct page *kpage;
Izik Eidus31dbd012009-09-21 17:02:03 -07001411 unsigned int checksum;
1412 int err;
1413
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001414 stable_node = page_stable_node(page);
1415 if (stable_node) {
1416 if (stable_node->head != &migrate_nodes &&
1417 get_kpfn_nid(stable_node->kpfn) != NUMA(stable_node->nid)) {
1418 rb_erase(&stable_node->node,
Hugh Dickinsef53d162013-02-22 16:36:12 -08001419 root_stable_tree + NUMA(stable_node->nid));
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001420 stable_node->head = &migrate_nodes;
1421 list_add(&stable_node->list, stable_node->head);
1422 }
1423 if (stable_node->head != &migrate_nodes &&
1424 rmap_item->head == stable_node)
1425 return;
1426 }
Izik Eidus31dbd012009-09-21 17:02:03 -07001427
1428 /* We first start with searching the page inside the stable tree */
Hugh Dickins62b61f62009-12-14 17:59:33 -08001429 kpage = stable_tree_search(page);
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001430 if (kpage == page && rmap_item->head == stable_node) {
1431 put_page(kpage);
1432 return;
1433 }
1434
1435 remove_rmap_item_from_tree(rmap_item);
1436
Hugh Dickins62b61f62009-12-14 17:59:33 -08001437 if (kpage) {
Hugh Dickins08beca42009-12-14 17:59:21 -08001438 err = try_to_merge_with_ksm_page(rmap_item, page, kpage);
Izik Eidus31dbd012009-09-21 17:02:03 -07001439 if (!err) {
1440 /*
1441 * The page was successfully merged:
1442 * add its rmap_item to the stable tree.
1443 */
Hugh Dickins5ad64682009-12-14 17:59:24 -08001444 lock_page(kpage);
Hugh Dickins62b61f62009-12-14 17:59:33 -08001445 stable_tree_append(rmap_item, page_stable_node(kpage));
Hugh Dickins5ad64682009-12-14 17:59:24 -08001446 unlock_page(kpage);
Izik Eidus31dbd012009-09-21 17:02:03 -07001447 }
Hugh Dickins8dd35572009-12-14 17:59:18 -08001448 put_page(kpage);
Izik Eidus31dbd012009-09-21 17:02:03 -07001449 return;
1450 }
1451
1452 /*
Hugh Dickins4035c07a2009-12-14 17:59:27 -08001453 * If the hash value of the page has changed from the last time
1454 * we calculated it, this page is changing frequently: therefore we
1455 * don't want to insert it in the unstable tree, and we don't want
1456 * to waste our time searching for something identical to it there.
Izik Eidus31dbd012009-09-21 17:02:03 -07001457 */
1458 checksum = calc_checksum(page);
1459 if (rmap_item->oldchecksum != checksum) {
1460 rmap_item->oldchecksum = checksum;
1461 return;
1462 }
1463
Hugh Dickins8dd35572009-12-14 17:59:18 -08001464 tree_rmap_item =
1465 unstable_tree_search_insert(rmap_item, page, &tree_page);
Izik Eidus31dbd012009-09-21 17:02:03 -07001466 if (tree_rmap_item) {
Hugh Dickins8dd35572009-12-14 17:59:18 -08001467 kpage = try_to_merge_two_pages(rmap_item, page,
1468 tree_rmap_item, tree_page);
1469 put_page(tree_page);
Hugh Dickins8dd35572009-12-14 17:59:18 -08001470 if (kpage) {
Hugh Dickinsbc566202013-02-22 16:36:06 -08001471 /*
1472 * The pages were successfully merged: insert new
1473 * node in the stable tree and add both rmap_items.
1474 */
Hugh Dickins5ad64682009-12-14 17:59:24 -08001475 lock_page(kpage);
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001476 stable_node = stable_tree_insert(kpage);
1477 if (stable_node) {
1478 stable_tree_append(tree_rmap_item, stable_node);
1479 stable_tree_append(rmap_item, stable_node);
1480 }
Hugh Dickins5ad64682009-12-14 17:59:24 -08001481 unlock_page(kpage);
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001482
Izik Eidus31dbd012009-09-21 17:02:03 -07001483 /*
1484 * If we fail to insert the page into the stable tree,
1485 * we will have 2 virtual addresses that are pointing
1486 * to a ksm page left outside the stable tree,
1487 * in which case we need to break_cow on both.
1488 */
Hugh Dickins7b6ba2c2009-12-14 17:59:20 -08001489 if (!stable_node) {
Hugh Dickins8dd35572009-12-14 17:59:18 -08001490 break_cow(tree_rmap_item);
1491 break_cow(rmap_item);
Izik Eidus31dbd012009-09-21 17:02:03 -07001492 }
1493 }
Izik Eidus31dbd012009-09-21 17:02:03 -07001494 }
1495}
1496
1497static struct rmap_item *get_next_rmap_item(struct mm_slot *mm_slot,
Hugh Dickins6514d512009-12-14 17:59:19 -08001498 struct rmap_item **rmap_list,
Izik Eidus31dbd012009-09-21 17:02:03 -07001499 unsigned long addr)
1500{
1501 struct rmap_item *rmap_item;
1502
Hugh Dickins6514d512009-12-14 17:59:19 -08001503 while (*rmap_list) {
1504 rmap_item = *rmap_list;
Hugh Dickins93d17712009-12-14 17:59:16 -08001505 if ((rmap_item->address & PAGE_MASK) == addr)
Izik Eidus31dbd012009-09-21 17:02:03 -07001506 return rmap_item;
Izik Eidus31dbd012009-09-21 17:02:03 -07001507 if (rmap_item->address > addr)
1508 break;
Hugh Dickins6514d512009-12-14 17:59:19 -08001509 *rmap_list = rmap_item->rmap_list;
Izik Eidus31dbd012009-09-21 17:02:03 -07001510 remove_rmap_item_from_tree(rmap_item);
Izik Eidus31dbd012009-09-21 17:02:03 -07001511 free_rmap_item(rmap_item);
1512 }
1513
1514 rmap_item = alloc_rmap_item();
1515 if (rmap_item) {
1516 /* It has already been zeroed */
1517 rmap_item->mm = mm_slot->mm;
1518 rmap_item->address = addr;
Hugh Dickins6514d512009-12-14 17:59:19 -08001519 rmap_item->rmap_list = *rmap_list;
1520 *rmap_list = rmap_item;
Izik Eidus31dbd012009-09-21 17:02:03 -07001521 }
1522 return rmap_item;
1523}
1524
1525static struct rmap_item *scan_get_next_rmap_item(struct page **page)
1526{
1527 struct mm_struct *mm;
1528 struct mm_slot *slot;
1529 struct vm_area_struct *vma;
1530 struct rmap_item *rmap_item;
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001531 int nid;
Izik Eidus31dbd012009-09-21 17:02:03 -07001532
1533 if (list_empty(&ksm_mm_head.mm_list))
1534 return NULL;
1535
1536 slot = ksm_scan.mm_slot;
1537 if (slot == &ksm_mm_head) {
Hugh Dickins2919bfd2011-01-13 15:47:29 -08001538 /*
1539 * A number of pages can hang around indefinitely on per-cpu
1540 * pagevecs, raised page count preventing write_protect_page
1541 * from merging them. Though it doesn't really matter much,
1542 * it is puzzling to see some stuck in pages_volatile until
1543 * other activity jostles them out, and they also prevented
1544 * LTP's KSM test from succeeding deterministically; so drain
1545 * them here (here rather than on entry to ksm_do_scan(),
1546 * so we don't IPI too often when pages_to_scan is set low).
1547 */
1548 lru_add_drain_all();
1549
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001550 /*
1551 * Whereas stale stable_nodes on the stable_tree itself
1552 * get pruned in the regular course of stable_tree_search(),
1553 * those moved out to the migrate_nodes list can accumulate:
1554 * so prune them once before each full scan.
1555 */
1556 if (!ksm_merge_across_nodes) {
Geliang Tang03640412016-01-14 15:20:54 -08001557 struct stable_node *stable_node, *next;
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001558 struct page *page;
1559
Geliang Tang03640412016-01-14 15:20:54 -08001560 list_for_each_entry_safe(stable_node, next,
1561 &migrate_nodes, list) {
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001562 page = get_ksm_page(stable_node, false);
1563 if (page)
1564 put_page(page);
1565 cond_resched();
1566 }
1567 }
1568
Hugh Dickinsef53d162013-02-22 16:36:12 -08001569 for (nid = 0; nid < ksm_nr_node_ids; nid++)
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001570 root_unstable_tree[nid] = RB_ROOT;
Izik Eidus31dbd012009-09-21 17:02:03 -07001571
1572 spin_lock(&ksm_mmlist_lock);
1573 slot = list_entry(slot->mm_list.next, struct mm_slot, mm_list);
1574 ksm_scan.mm_slot = slot;
1575 spin_unlock(&ksm_mmlist_lock);
Hugh Dickins2b472612011-06-15 15:08:58 -07001576 /*
1577 * Although we tested list_empty() above, a racing __ksm_exit
1578 * of the last mm on the list may have removed it since then.
1579 */
1580 if (slot == &ksm_mm_head)
1581 return NULL;
Izik Eidus31dbd012009-09-21 17:02:03 -07001582next_mm:
1583 ksm_scan.address = 0;
Hugh Dickins6514d512009-12-14 17:59:19 -08001584 ksm_scan.rmap_list = &slot->rmap_list;
Izik Eidus31dbd012009-09-21 17:02:03 -07001585 }
1586
1587 mm = slot->mm;
1588 down_read(&mm->mmap_sem);
Hugh Dickins9ba69292009-09-21 17:02:20 -07001589 if (ksm_test_exit(mm))
1590 vma = NULL;
1591 else
1592 vma = find_vma(mm, ksm_scan.address);
1593
1594 for (; vma; vma = vma->vm_next) {
Izik Eidus31dbd012009-09-21 17:02:03 -07001595 if (!(vma->vm_flags & VM_MERGEABLE))
1596 continue;
1597 if (ksm_scan.address < vma->vm_start)
1598 ksm_scan.address = vma->vm_start;
1599 if (!vma->anon_vma)
1600 ksm_scan.address = vma->vm_end;
1601
1602 while (ksm_scan.address < vma->vm_end) {
Hugh Dickins9ba69292009-09-21 17:02:20 -07001603 if (ksm_test_exit(mm))
1604 break;
Izik Eidus31dbd012009-09-21 17:02:03 -07001605 *page = follow_page(vma, ksm_scan.address, FOLL_GET);
Andrea Arcangeli21ae5b02011-01-13 15:47:00 -08001606 if (IS_ERR_OR_NULL(*page)) {
1607 ksm_scan.address += PAGE_SIZE;
1608 cond_resched();
1609 continue;
1610 }
Kirill A. Shutemovf765f542016-01-15 16:53:03 -08001611 if (PageAnon(*page)) {
Izik Eidus31dbd012009-09-21 17:02:03 -07001612 flush_anon_page(vma, *page, ksm_scan.address);
1613 flush_dcache_page(*page);
1614 rmap_item = get_next_rmap_item(slot,
Hugh Dickins6514d512009-12-14 17:59:19 -08001615 ksm_scan.rmap_list, ksm_scan.address);
Izik Eidus31dbd012009-09-21 17:02:03 -07001616 if (rmap_item) {
Hugh Dickins6514d512009-12-14 17:59:19 -08001617 ksm_scan.rmap_list =
1618 &rmap_item->rmap_list;
Izik Eidus31dbd012009-09-21 17:02:03 -07001619 ksm_scan.address += PAGE_SIZE;
1620 } else
1621 put_page(*page);
1622 up_read(&mm->mmap_sem);
1623 return rmap_item;
1624 }
Andrea Arcangeli21ae5b02011-01-13 15:47:00 -08001625 put_page(*page);
Izik Eidus31dbd012009-09-21 17:02:03 -07001626 ksm_scan.address += PAGE_SIZE;
1627 cond_resched();
1628 }
1629 }
1630
Hugh Dickins9ba69292009-09-21 17:02:20 -07001631 if (ksm_test_exit(mm)) {
1632 ksm_scan.address = 0;
Hugh Dickins6514d512009-12-14 17:59:19 -08001633 ksm_scan.rmap_list = &slot->rmap_list;
Hugh Dickins9ba69292009-09-21 17:02:20 -07001634 }
Izik Eidus31dbd012009-09-21 17:02:03 -07001635 /*
1636 * Nuke all the rmap_items that are above this current rmap:
1637 * because there were no VM_MERGEABLE vmas with such addresses.
1638 */
Hugh Dickins6514d512009-12-14 17:59:19 -08001639 remove_trailing_rmap_items(slot, ksm_scan.rmap_list);
Izik Eidus31dbd012009-09-21 17:02:03 -07001640
1641 spin_lock(&ksm_mmlist_lock);
Hugh Dickinscd551f92009-09-21 17:02:17 -07001642 ksm_scan.mm_slot = list_entry(slot->mm_list.next,
1643 struct mm_slot, mm_list);
1644 if (ksm_scan.address == 0) {
1645 /*
1646 * We've completed a full scan of all vmas, holding mmap_sem
1647 * throughout, and found no VM_MERGEABLE: so do the same as
1648 * __ksm_exit does to remove this mm from all our lists now.
Hugh Dickins9ba69292009-09-21 17:02:20 -07001649 * This applies either when cleaning up after __ksm_exit
1650 * (but beware: we can reach here even before __ksm_exit),
1651 * or when all VM_MERGEABLE areas have been unmapped (and
1652 * mmap_sem then protects against race with MADV_MERGEABLE).
Hugh Dickinscd551f92009-09-21 17:02:17 -07001653 */
Sasha Levin4ca3a692013-02-22 16:32:28 -08001654 hash_del(&slot->link);
Hugh Dickinscd551f92009-09-21 17:02:17 -07001655 list_del(&slot->mm_list);
Hugh Dickins9ba69292009-09-21 17:02:20 -07001656 spin_unlock(&ksm_mmlist_lock);
1657
Hugh Dickinscd551f92009-09-21 17:02:17 -07001658 free_mm_slot(slot);
1659 clear_bit(MMF_VM_MERGEABLE, &mm->flags);
Hugh Dickins9ba69292009-09-21 17:02:20 -07001660 up_read(&mm->mmap_sem);
1661 mmdrop(mm);
1662 } else {
Hugh Dickins9ba69292009-09-21 17:02:20 -07001663 up_read(&mm->mmap_sem);
Zhou Chengming7496fea2016-05-12 15:42:21 -07001664 /*
1665 * up_read(&mm->mmap_sem) first because after
1666 * spin_unlock(&ksm_mmlist_lock) run, the "mm" may
1667 * already have been freed under us by __ksm_exit()
1668 * because the "mm_slot" is still hashed and
1669 * ksm_scan.mm_slot doesn't point to it anymore.
1670 */
1671 spin_unlock(&ksm_mmlist_lock);
Hugh Dickinscd551f92009-09-21 17:02:17 -07001672 }
Izik Eidus31dbd012009-09-21 17:02:03 -07001673
1674 /* Repeat until we've completed scanning the whole list */
Hugh Dickinscd551f92009-09-21 17:02:17 -07001675 slot = ksm_scan.mm_slot;
Izik Eidus31dbd012009-09-21 17:02:03 -07001676 if (slot != &ksm_mm_head)
1677 goto next_mm;
1678
Izik Eidus31dbd012009-09-21 17:02:03 -07001679 ksm_scan.seqnr++;
1680 return NULL;
1681}
1682
1683/**
1684 * ksm_do_scan - the ksm scanner main worker function.
1685 * @scan_npages - number of pages we want to scan before we return.
1686 */
1687static void ksm_do_scan(unsigned int scan_npages)
1688{
1689 struct rmap_item *rmap_item;
Dan Carpenter22eccdd2010-04-23 13:18:10 -04001690 struct page *uninitialized_var(page);
Izik Eidus31dbd012009-09-21 17:02:03 -07001691
Andrea Arcangeli878aee72011-01-13 15:47:10 -08001692 while (scan_npages-- && likely(!freezing(current))) {
Izik Eidus31dbd012009-09-21 17:02:03 -07001693 cond_resched();
1694 rmap_item = scan_get_next_rmap_item(&page);
1695 if (!rmap_item)
1696 return;
Hugh Dickins4146d2d2013-02-22 16:35:11 -08001697 cmp_and_merge_page(page, rmap_item);
Izik Eidus31dbd012009-09-21 17:02:03 -07001698 put_page(page);
1699 }
1700}
1701
Hugh Dickins6e1583842009-09-21 17:02:14 -07001702static int ksmd_should_run(void)
1703{
1704 return (ksm_run & KSM_RUN_MERGE) && !list_empty(&ksm_mm_head.mm_list);
1705}
1706
Izik Eidus31dbd012009-09-21 17:02:03 -07001707static int ksm_scan_thread(void *nothing)
1708{
Andrea Arcangeli878aee72011-01-13 15:47:10 -08001709 set_freezable();
Izik Eidus339aa622009-09-21 17:02:07 -07001710 set_user_nice(current, 5);
Izik Eidus31dbd012009-09-21 17:02:03 -07001711
1712 while (!kthread_should_stop()) {
Hugh Dickins6e1583842009-09-21 17:02:14 -07001713 mutex_lock(&ksm_thread_mutex);
Hugh Dickinsef4d43a2013-02-22 16:35:16 -08001714 wait_while_offlining();
Hugh Dickins6e1583842009-09-21 17:02:14 -07001715 if (ksmd_should_run())
Izik Eidus31dbd012009-09-21 17:02:03 -07001716 ksm_do_scan(ksm_thread_pages_to_scan);
Hugh Dickins6e1583842009-09-21 17:02:14 -07001717 mutex_unlock(&ksm_thread_mutex);
1718
Andrea Arcangeli878aee72011-01-13 15:47:10 -08001719 try_to_freeze();
1720
Hugh Dickins6e1583842009-09-21 17:02:14 -07001721 if (ksmd_should_run()) {
Izik Eidus31dbd012009-09-21 17:02:03 -07001722 schedule_timeout_interruptible(
1723 msecs_to_jiffies(ksm_thread_sleep_millisecs));
1724 } else {
Andrea Arcangeli878aee72011-01-13 15:47:10 -08001725 wait_event_freezable(ksm_thread_wait,
Hugh Dickins6e1583842009-09-21 17:02:14 -07001726 ksmd_should_run() || kthread_should_stop());
Izik Eidus31dbd012009-09-21 17:02:03 -07001727 }
1728 }
1729 return 0;
1730}
1731
Hugh Dickinsf8af4da2009-09-21 17:01:57 -07001732int ksm_madvise(struct vm_area_struct *vma, unsigned long start,
1733 unsigned long end, int advice, unsigned long *vm_flags)
1734{
1735 struct mm_struct *mm = vma->vm_mm;
Hugh Dickinsd952b792009-09-21 17:02:16 -07001736 int err;
Hugh Dickinsf8af4da2009-09-21 17:01:57 -07001737
1738 switch (advice) {
1739 case MADV_MERGEABLE:
1740 /*
1741 * Be somewhat over-protective for now!
1742 */
1743 if (*vm_flags & (VM_MERGEABLE | VM_SHARED | VM_MAYSHARE |
1744 VM_PFNMAP | VM_IO | VM_DONTEXPAND |
Kirill A. Shutemov0661a332015-02-10 14:10:04 -08001745 VM_HUGETLB | VM_MIXEDMAP))
Hugh Dickinsf8af4da2009-09-21 17:01:57 -07001746 return 0; /* just ignore the advice */
1747
Konstantin Khlebnikovcc2383e2012-10-08 16:28:37 -07001748#ifdef VM_SAO
1749 if (*vm_flags & VM_SAO)
1750 return 0;
1751#endif
1752
Hugh Dickinsd952b792009-09-21 17:02:16 -07001753 if (!test_bit(MMF_VM_MERGEABLE, &mm->flags)) {
1754 err = __ksm_enter(mm);
1755 if (err)
1756 return err;
1757 }
Hugh Dickinsf8af4da2009-09-21 17:01:57 -07001758
1759 *vm_flags |= VM_MERGEABLE;
1760 break;
1761
1762 case MADV_UNMERGEABLE:
1763 if (!(*vm_flags & VM_MERGEABLE))
1764 return 0; /* just ignore the advice */
1765
Hugh Dickinsd952b792009-09-21 17:02:16 -07001766 if (vma->anon_vma) {
1767 err = unmerge_ksm_pages(vma, start, end);
1768 if (err)
1769 return err;
1770 }
Hugh Dickinsf8af4da2009-09-21 17:01:57 -07001771
1772 *vm_flags &= ~VM_MERGEABLE;
1773 break;
1774 }
1775
1776 return 0;
1777}
1778
1779int __ksm_enter(struct mm_struct *mm)
1780{
Hugh Dickins6e1583842009-09-21 17:02:14 -07001781 struct mm_slot *mm_slot;
1782 int needs_wakeup;
1783
1784 mm_slot = alloc_mm_slot();
Izik Eidus31dbd012009-09-21 17:02:03 -07001785 if (!mm_slot)
1786 return -ENOMEM;
1787
Hugh Dickins6e1583842009-09-21 17:02:14 -07001788 /* Check ksm_run too? Would need tighter locking */
1789 needs_wakeup = list_empty(&ksm_mm_head.mm_list);
1790
Izik Eidus31dbd012009-09-21 17:02:03 -07001791 spin_lock(&ksm_mmlist_lock);
1792 insert_to_mm_slots_hash(mm, mm_slot);
1793 /*
Hugh Dickinscbf86cf2013-02-22 16:35:08 -08001794 * When KSM_RUN_MERGE (or KSM_RUN_STOP),
1795 * insert just behind the scanning cursor, to let the area settle
Izik Eidus31dbd012009-09-21 17:02:03 -07001796 * down a little; when fork is followed by immediate exec, we don't
1797 * want ksmd to waste time setting up and tearing down an rmap_list.
Hugh Dickinscbf86cf2013-02-22 16:35:08 -08001798 *
1799 * But when KSM_RUN_UNMERGE, it's important to insert ahead of its
1800 * scanning cursor, otherwise KSM pages in newly forked mms will be
1801 * missed: then we might as well insert at the end of the list.
Izik Eidus31dbd012009-09-21 17:02:03 -07001802 */
Hugh Dickinscbf86cf2013-02-22 16:35:08 -08001803 if (ksm_run & KSM_RUN_UNMERGE)
1804 list_add_tail(&mm_slot->mm_list, &ksm_mm_head.mm_list);
1805 else
1806 list_add_tail(&mm_slot->mm_list, &ksm_scan.mm_slot->mm_list);
Izik Eidus31dbd012009-09-21 17:02:03 -07001807 spin_unlock(&ksm_mmlist_lock);
1808
Hugh Dickinsf8af4da2009-09-21 17:01:57 -07001809 set_bit(MMF_VM_MERGEABLE, &mm->flags);
Hugh Dickins9ba69292009-09-21 17:02:20 -07001810 atomic_inc(&mm->mm_count);
Hugh Dickins6e1583842009-09-21 17:02:14 -07001811
1812 if (needs_wakeup)
1813 wake_up_interruptible(&ksm_thread_wait);
1814
Hugh Dickinsf8af4da2009-09-21 17:01:57 -07001815 return 0;
1816}
1817
Andrea Arcangeli1c2fb7a2009-09-21 17:02:22 -07001818void __ksm_exit(struct mm_struct *mm)
Hugh Dickinsf8af4da2009-09-21 17:01:57 -07001819{
Hugh Dickinscd551f92009-09-21 17:02:17 -07001820 struct mm_slot *mm_slot;
Hugh Dickins9ba69292009-09-21 17:02:20 -07001821 int easy_to_free = 0;
Hugh Dickinscd551f92009-09-21 17:02:17 -07001822
Izik Eidus31dbd012009-09-21 17:02:03 -07001823 /*
Hugh Dickins9ba69292009-09-21 17:02:20 -07001824 * This process is exiting: if it's straightforward (as is the
1825 * case when ksmd was never running), free mm_slot immediately.
1826 * But if it's at the cursor or has rmap_items linked to it, use
1827 * mmap_sem to synchronize with any break_cows before pagetables
1828 * are freed, and leave the mm_slot on the list for ksmd to free.
1829 * Beware: ksm may already have noticed it exiting and freed the slot.
Izik Eidus31dbd012009-09-21 17:02:03 -07001830 */
Hugh Dickins9ba69292009-09-21 17:02:20 -07001831
Hugh Dickinscd551f92009-09-21 17:02:17 -07001832 spin_lock(&ksm_mmlist_lock);
1833 mm_slot = get_mm_slot(mm);
Hugh Dickins9ba69292009-09-21 17:02:20 -07001834 if (mm_slot && ksm_scan.mm_slot != mm_slot) {
Hugh Dickins6514d512009-12-14 17:59:19 -08001835 if (!mm_slot->rmap_list) {
Sasha Levin4ca3a692013-02-22 16:32:28 -08001836 hash_del(&mm_slot->link);
Hugh Dickins9ba69292009-09-21 17:02:20 -07001837 list_del(&mm_slot->mm_list);
1838 easy_to_free = 1;
1839 } else {
1840 list_move(&mm_slot->mm_list,
1841 &ksm_scan.mm_slot->mm_list);
1842 }
Hugh Dickinscd551f92009-09-21 17:02:17 -07001843 }
Hugh Dickinscd551f92009-09-21 17:02:17 -07001844 spin_unlock(&ksm_mmlist_lock);
1845
Hugh Dickins9ba69292009-09-21 17:02:20 -07001846 if (easy_to_free) {
1847 free_mm_slot(mm_slot);
1848 clear_bit(MMF_VM_MERGEABLE, &mm->flags);
1849 mmdrop(mm);
1850 } else if (mm_slot) {
Hugh Dickins9ba69292009-09-21 17:02:20 -07001851 down_write(&mm->mmap_sem);
1852 up_write(&mm->mmap_sem);
Hugh Dickins9ba69292009-09-21 17:02:20 -07001853 }
Hugh Dickinsf8af4da2009-09-21 17:01:57 -07001854}
Izik Eidus31dbd012009-09-21 17:02:03 -07001855
Hugh Dickinscbf86cf2013-02-22 16:35:08 -08001856struct page *ksm_might_need_to_copy(struct page *page,
Hugh Dickins5ad64682009-12-14 17:59:24 -08001857 struct vm_area_struct *vma, unsigned long address)
1858{
Hugh Dickinscbf86cf2013-02-22 16:35:08 -08001859 struct anon_vma *anon_vma = page_anon_vma(page);
Hugh Dickins5ad64682009-12-14 17:59:24 -08001860 struct page *new_page;
1861
Hugh Dickinscbf86cf2013-02-22 16:35:08 -08001862 if (PageKsm(page)) {
1863 if (page_stable_node(page) &&
1864 !(ksm_run & KSM_RUN_UNMERGE))
1865 return page; /* no need to copy it */
1866 } else if (!anon_vma) {
1867 return page; /* no need to copy it */
1868 } else if (anon_vma->root == vma->anon_vma->root &&
1869 page->index == linear_page_index(vma, address)) {
1870 return page; /* still no need to copy it */
1871 }
1872 if (!PageUptodate(page))
1873 return page; /* let do_swap_page report the error */
1874
Hugh Dickins5ad64682009-12-14 17:59:24 -08001875 new_page = alloc_page_vma(GFP_HIGHUSER_MOVABLE, vma, address);
1876 if (new_page) {
1877 copy_user_highpage(new_page, page, address, vma);
1878
1879 SetPageDirty(new_page);
1880 __SetPageUptodate(new_page);
Kirill A. Shutemov48c935a2016-01-15 16:51:24 -08001881 __SetPageLocked(new_page);
Hugh Dickins5ad64682009-12-14 17:59:24 -08001882 }
1883
Hugh Dickins5ad64682009-12-14 17:59:24 -08001884 return new_page;
1885}
1886
Joonsoo Kim051ac832014-01-21 15:49:48 -08001887int rmap_walk_ksm(struct page *page, struct rmap_walk_control *rwc)
Hugh Dickinse9995ef2009-12-14 17:59:31 -08001888{
1889 struct stable_node *stable_node;
Hugh Dickinse9995ef2009-12-14 17:59:31 -08001890 struct rmap_item *rmap_item;
1891 int ret = SWAP_AGAIN;
1892 int search_new_forks = 0;
1893
Sasha Levin309381fea2014-01-23 15:52:54 -08001894 VM_BUG_ON_PAGE(!PageKsm(page), page);
Joonsoo Kim9f326242014-01-21 15:49:53 -08001895
1896 /*
1897 * Rely on the page lock to protect against concurrent modifications
1898 * to that page's node of the stable tree.
1899 */
Sasha Levin309381fea2014-01-23 15:52:54 -08001900 VM_BUG_ON_PAGE(!PageLocked(page), page);
Hugh Dickinse9995ef2009-12-14 17:59:31 -08001901
1902 stable_node = page_stable_node(page);
1903 if (!stable_node)
1904 return ret;
1905again:
Sasha Levinb67bfe02013-02-27 17:06:00 -08001906 hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist) {
Hugh Dickinse9995ef2009-12-14 17:59:31 -08001907 struct anon_vma *anon_vma = rmap_item->anon_vma;
Rik van Riel5beb4932010-03-05 13:42:07 -08001908 struct anon_vma_chain *vmac;
Hugh Dickinse9995ef2009-12-14 17:59:31 -08001909 struct vm_area_struct *vma;
1910
Andrea Arcangeliad126952015-11-05 18:49:07 -08001911 cond_resched();
Hugh Dickinsb6b19f22012-12-19 17:44:29 -08001912 anon_vma_lock_read(anon_vma);
Michel Lespinassebf181b92012-10-08 16:31:39 -07001913 anon_vma_interval_tree_foreach(vmac, &anon_vma->rb_root,
1914 0, ULONG_MAX) {
Andrea Arcangeliad126952015-11-05 18:49:07 -08001915 cond_resched();
Rik van Riel5beb4932010-03-05 13:42:07 -08001916 vma = vmac->vma;
Hugh Dickinse9995ef2009-12-14 17:59:31 -08001917 if (rmap_item->address < vma->vm_start ||
1918 rmap_item->address >= vma->vm_end)
1919 continue;
1920 /*
1921 * Initially we examine only the vma which covers this
1922 * rmap_item; but later, if there is still work to do,
1923 * we examine covering vmas in other mms: in case they
1924 * were forked from the original since ksmd passed.
1925 */
1926 if ((rmap_item->mm == vma->vm_mm) == search_new_forks)
1927 continue;
1928
Joonsoo Kim0dd1c7b2014-01-21 15:49:49 -08001929 if (rwc->invalid_vma && rwc->invalid_vma(vma, rwc->arg))
1930 continue;
1931
Joonsoo Kim051ac832014-01-21 15:49:48 -08001932 ret = rwc->rmap_one(page, vma,
1933 rmap_item->address, rwc->arg);
Hugh Dickinse9995ef2009-12-14 17:59:31 -08001934 if (ret != SWAP_AGAIN) {
Hugh Dickinsb6b19f22012-12-19 17:44:29 -08001935 anon_vma_unlock_read(anon_vma);
Hugh Dickinse9995ef2009-12-14 17:59:31 -08001936 goto out;
1937 }
Joonsoo Kim0dd1c7b2014-01-21 15:49:49 -08001938 if (rwc->done && rwc->done(page)) {
1939 anon_vma_unlock_read(anon_vma);
1940 goto out;
1941 }
Hugh Dickinse9995ef2009-12-14 17:59:31 -08001942 }
Hugh Dickinsb6b19f22012-12-19 17:44:29 -08001943 anon_vma_unlock_read(anon_vma);
Hugh Dickinse9995ef2009-12-14 17:59:31 -08001944 }
1945 if (!search_new_forks++)
1946 goto again;
1947out:
1948 return ret;
1949}
1950
Joonsoo Kim52629502014-01-21 15:49:50 -08001951#ifdef CONFIG_MIGRATION
Hugh Dickinse9995ef2009-12-14 17:59:31 -08001952void ksm_migrate_page(struct page *newpage, struct page *oldpage)
1953{
1954 struct stable_node *stable_node;
1955
Sasha Levin309381fea2014-01-23 15:52:54 -08001956 VM_BUG_ON_PAGE(!PageLocked(oldpage), oldpage);
1957 VM_BUG_ON_PAGE(!PageLocked(newpage), newpage);
1958 VM_BUG_ON_PAGE(newpage->mapping != oldpage->mapping, newpage);
Hugh Dickinse9995ef2009-12-14 17:59:31 -08001959
1960 stable_node = page_stable_node(newpage);
1961 if (stable_node) {
Sasha Levin309381fea2014-01-23 15:52:54 -08001962 VM_BUG_ON_PAGE(stable_node->kpfn != page_to_pfn(oldpage), oldpage);
Hugh Dickins62b61f62009-12-14 17:59:33 -08001963 stable_node->kpfn = page_to_pfn(newpage);
Hugh Dickinsc8d65532013-02-22 16:35:10 -08001964 /*
1965 * newpage->mapping was set in advance; now we need smp_wmb()
1966 * to make sure that the new stable_node->kpfn is visible
1967 * to get_ksm_page() before it can see that oldpage->mapping
1968 * has gone stale (or that PageSwapCache has been cleared).
1969 */
1970 smp_wmb();
1971 set_page_stable_node(oldpage, NULL);
Hugh Dickinse9995ef2009-12-14 17:59:31 -08001972 }
1973}
1974#endif /* CONFIG_MIGRATION */
1975
Hugh Dickins62b61f62009-12-14 17:59:33 -08001976#ifdef CONFIG_MEMORY_HOTREMOVE
Hugh Dickinsef4d43a2013-02-22 16:35:16 -08001977static void wait_while_offlining(void)
1978{
1979 while (ksm_run & KSM_RUN_OFFLINE) {
1980 mutex_unlock(&ksm_thread_mutex);
1981 wait_on_bit(&ksm_run, ilog2(KSM_RUN_OFFLINE),
NeilBrown74316202014-07-07 15:16:04 +10001982 TASK_UNINTERRUPTIBLE);
Hugh Dickinsef4d43a2013-02-22 16:35:16 -08001983 mutex_lock(&ksm_thread_mutex);
1984 }
1985}
1986
Hugh Dickinsee0ea592013-02-22 16:35:05 -08001987static void ksm_check_stable_tree(unsigned long start_pfn,
1988 unsigned long end_pfn)
Hugh Dickins62b61f62009-12-14 17:59:33 -08001989{
Geliang Tang03640412016-01-14 15:20:54 -08001990 struct stable_node *stable_node, *next;
Hugh Dickins62b61f62009-12-14 17:59:33 -08001991 struct rb_node *node;
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001992 int nid;
Hugh Dickins62b61f62009-12-14 17:59:33 -08001993
Hugh Dickinsef53d162013-02-22 16:36:12 -08001994 for (nid = 0; nid < ksm_nr_node_ids; nid++) {
1995 node = rb_first(root_stable_tree + nid);
Hugh Dickinsee0ea592013-02-22 16:35:05 -08001996 while (node) {
Petr Holasek90bd6fd2013-02-22 16:35:00 -08001997 stable_node = rb_entry(node, struct stable_node, node);
1998 if (stable_node->kpfn >= start_pfn &&
Hugh Dickinsee0ea592013-02-22 16:35:05 -08001999 stable_node->kpfn < end_pfn) {
2000 /*
2001 * Don't get_ksm_page, page has already gone:
2002 * which is why we keep kpfn instead of page*
2003 */
2004 remove_node_from_stable_tree(stable_node);
Hugh Dickinsef53d162013-02-22 16:36:12 -08002005 node = rb_first(root_stable_tree + nid);
Hugh Dickinsee0ea592013-02-22 16:35:05 -08002006 } else
2007 node = rb_next(node);
2008 cond_resched();
Petr Holasek90bd6fd2013-02-22 16:35:00 -08002009 }
Hugh Dickinsee0ea592013-02-22 16:35:05 -08002010 }
Geliang Tang03640412016-01-14 15:20:54 -08002011 list_for_each_entry_safe(stable_node, next, &migrate_nodes, list) {
Hugh Dickins4146d2d2013-02-22 16:35:11 -08002012 if (stable_node->kpfn >= start_pfn &&
2013 stable_node->kpfn < end_pfn)
2014 remove_node_from_stable_tree(stable_node);
2015 cond_resched();
2016 }
Hugh Dickins62b61f62009-12-14 17:59:33 -08002017}
2018
2019static int ksm_memory_callback(struct notifier_block *self,
2020 unsigned long action, void *arg)
2021{
2022 struct memory_notify *mn = arg;
Hugh Dickins62b61f62009-12-14 17:59:33 -08002023
2024 switch (action) {
2025 case MEM_GOING_OFFLINE:
2026 /*
Hugh Dickinsef4d43a2013-02-22 16:35:16 -08002027 * Prevent ksm_do_scan(), unmerge_and_remove_all_rmap_items()
2028 * and remove_all_stable_nodes() while memory is going offline:
2029 * it is unsafe for them to touch the stable tree at this time.
2030 * But unmerge_ksm_pages(), rmap lookups and other entry points
2031 * which do not need the ksm_thread_mutex are all safe.
Hugh Dickins62b61f62009-12-14 17:59:33 -08002032 */
Hugh Dickinsef4d43a2013-02-22 16:35:16 -08002033 mutex_lock(&ksm_thread_mutex);
2034 ksm_run |= KSM_RUN_OFFLINE;
2035 mutex_unlock(&ksm_thread_mutex);
Hugh Dickins62b61f62009-12-14 17:59:33 -08002036 break;
2037
2038 case MEM_OFFLINE:
2039 /*
2040 * Most of the work is done by page migration; but there might
2041 * be a few stable_nodes left over, still pointing to struct
Hugh Dickinsee0ea592013-02-22 16:35:05 -08002042 * pages which have been offlined: prune those from the tree,
2043 * otherwise get_ksm_page() might later try to access a
2044 * non-existent struct page.
Hugh Dickins62b61f62009-12-14 17:59:33 -08002045 */
Hugh Dickinsee0ea592013-02-22 16:35:05 -08002046 ksm_check_stable_tree(mn->start_pfn,
2047 mn->start_pfn + mn->nr_pages);
Hugh Dickins62b61f62009-12-14 17:59:33 -08002048 /* fallthrough */
2049
2050 case MEM_CANCEL_OFFLINE:
Hugh Dickinsef4d43a2013-02-22 16:35:16 -08002051 mutex_lock(&ksm_thread_mutex);
2052 ksm_run &= ~KSM_RUN_OFFLINE;
Hugh Dickins62b61f62009-12-14 17:59:33 -08002053 mutex_unlock(&ksm_thread_mutex);
Hugh Dickinsef4d43a2013-02-22 16:35:16 -08002054
2055 smp_mb(); /* wake_up_bit advises this */
2056 wake_up_bit(&ksm_run, ilog2(KSM_RUN_OFFLINE));
Hugh Dickins62b61f62009-12-14 17:59:33 -08002057 break;
2058 }
2059 return NOTIFY_OK;
2060}
Hugh Dickinsef4d43a2013-02-22 16:35:16 -08002061#else
2062static void wait_while_offlining(void)
2063{
2064}
Hugh Dickins62b61f62009-12-14 17:59:33 -08002065#endif /* CONFIG_MEMORY_HOTREMOVE */
2066
Hugh Dickins2ffd8672009-09-21 17:02:23 -07002067#ifdef CONFIG_SYSFS
2068/*
2069 * This all compiles without CONFIG_SYSFS, but is a waste of space.
2070 */
2071
Izik Eidus31dbd012009-09-21 17:02:03 -07002072#define KSM_ATTR_RO(_name) \
2073 static struct kobj_attribute _name##_attr = __ATTR_RO(_name)
2074#define KSM_ATTR(_name) \
2075 static struct kobj_attribute _name##_attr = \
2076 __ATTR(_name, 0644, _name##_show, _name##_store)
2077
2078static ssize_t sleep_millisecs_show(struct kobject *kobj,
2079 struct kobj_attribute *attr, char *buf)
2080{
2081 return sprintf(buf, "%u\n", ksm_thread_sleep_millisecs);
2082}
2083
2084static ssize_t sleep_millisecs_store(struct kobject *kobj,
2085 struct kobj_attribute *attr,
2086 const char *buf, size_t count)
2087{
2088 unsigned long msecs;
2089 int err;
2090
Jingoo Han3dbb95f2013-09-11 14:20:25 -07002091 err = kstrtoul(buf, 10, &msecs);
Izik Eidus31dbd012009-09-21 17:02:03 -07002092 if (err || msecs > UINT_MAX)
2093 return -EINVAL;
2094
2095 ksm_thread_sleep_millisecs = msecs;
2096
2097 return count;
2098}
2099KSM_ATTR(sleep_millisecs);
2100
2101static ssize_t pages_to_scan_show(struct kobject *kobj,
2102 struct kobj_attribute *attr, char *buf)
2103{
2104 return sprintf(buf, "%u\n", ksm_thread_pages_to_scan);
2105}
2106
2107static ssize_t pages_to_scan_store(struct kobject *kobj,
2108 struct kobj_attribute *attr,
2109 const char *buf, size_t count)
2110{
2111 int err;
2112 unsigned long nr_pages;
2113
Jingoo Han3dbb95f2013-09-11 14:20:25 -07002114 err = kstrtoul(buf, 10, &nr_pages);
Izik Eidus31dbd012009-09-21 17:02:03 -07002115 if (err || nr_pages > UINT_MAX)
2116 return -EINVAL;
2117
2118 ksm_thread_pages_to_scan = nr_pages;
2119
2120 return count;
2121}
2122KSM_ATTR(pages_to_scan);
2123
2124static ssize_t run_show(struct kobject *kobj, struct kobj_attribute *attr,
2125 char *buf)
2126{
Hugh Dickinsef4d43a2013-02-22 16:35:16 -08002127 return sprintf(buf, "%lu\n", ksm_run);
Izik Eidus31dbd012009-09-21 17:02:03 -07002128}
2129
2130static ssize_t run_store(struct kobject *kobj, struct kobj_attribute *attr,
2131 const char *buf, size_t count)
2132{
2133 int err;
2134 unsigned long flags;
2135
Jingoo Han3dbb95f2013-09-11 14:20:25 -07002136 err = kstrtoul(buf, 10, &flags);
Izik Eidus31dbd012009-09-21 17:02:03 -07002137 if (err || flags > UINT_MAX)
2138 return -EINVAL;
2139 if (flags > KSM_RUN_UNMERGE)
2140 return -EINVAL;
2141
2142 /*
2143 * KSM_RUN_MERGE sets ksmd running, and 0 stops it running.
2144 * KSM_RUN_UNMERGE stops it running and unmerges all rmap_items,
Hugh Dickinsd0f209f2009-12-14 17:59:34 -08002145 * breaking COW to free the pages_shared (but leaves mm_slots
2146 * on the list for when ksmd may be set running again).
Izik Eidus31dbd012009-09-21 17:02:03 -07002147 */
2148
2149 mutex_lock(&ksm_thread_mutex);
Hugh Dickinsef4d43a2013-02-22 16:35:16 -08002150 wait_while_offlining();
Izik Eidus31dbd012009-09-21 17:02:03 -07002151 if (ksm_run != flags) {
2152 ksm_run = flags;
Hugh Dickinsd952b792009-09-21 17:02:16 -07002153 if (flags & KSM_RUN_UNMERGE) {
David Rientjese1e12d22012-12-11 16:02:56 -08002154 set_current_oom_origin();
Hugh Dickinsd952b792009-09-21 17:02:16 -07002155 err = unmerge_and_remove_all_rmap_items();
David Rientjese1e12d22012-12-11 16:02:56 -08002156 clear_current_oom_origin();
Hugh Dickinsd952b792009-09-21 17:02:16 -07002157 if (err) {
2158 ksm_run = KSM_RUN_STOP;
2159 count = err;
2160 }
2161 }
Izik Eidus31dbd012009-09-21 17:02:03 -07002162 }
2163 mutex_unlock(&ksm_thread_mutex);
2164
2165 if (flags & KSM_RUN_MERGE)
2166 wake_up_interruptible(&ksm_thread_wait);
2167
2168 return count;
2169}
2170KSM_ATTR(run);
2171
Petr Holasek90bd6fd2013-02-22 16:35:00 -08002172#ifdef CONFIG_NUMA
2173static ssize_t merge_across_nodes_show(struct kobject *kobj,
2174 struct kobj_attribute *attr, char *buf)
2175{
2176 return sprintf(buf, "%u\n", ksm_merge_across_nodes);
2177}
2178
2179static ssize_t merge_across_nodes_store(struct kobject *kobj,
2180 struct kobj_attribute *attr,
2181 const char *buf, size_t count)
2182{
2183 int err;
2184 unsigned long knob;
2185
2186 err = kstrtoul(buf, 10, &knob);
2187 if (err)
2188 return err;
2189 if (knob > 1)
2190 return -EINVAL;
2191
2192 mutex_lock(&ksm_thread_mutex);
Hugh Dickinsef4d43a2013-02-22 16:35:16 -08002193 wait_while_offlining();
Petr Holasek90bd6fd2013-02-22 16:35:00 -08002194 if (ksm_merge_across_nodes != knob) {
Hugh Dickinscbf86cf2013-02-22 16:35:08 -08002195 if (ksm_pages_shared || remove_all_stable_nodes())
Petr Holasek90bd6fd2013-02-22 16:35:00 -08002196 err = -EBUSY;
Hugh Dickinsef53d162013-02-22 16:36:12 -08002197 else if (root_stable_tree == one_stable_tree) {
2198 struct rb_root *buf;
2199 /*
2200 * This is the first time that we switch away from the
2201 * default of merging across nodes: must now allocate
2202 * a buffer to hold as many roots as may be needed.
2203 * Allocate stable and unstable together:
2204 * MAXSMP NODES_SHIFT 10 will use 16kB.
2205 */
Joe Perchesbafe1e12013-11-12 15:07:10 -08002206 buf = kcalloc(nr_node_ids + nr_node_ids, sizeof(*buf),
2207 GFP_KERNEL);
Hugh Dickinsef53d162013-02-22 16:36:12 -08002208 /* Let us assume that RB_ROOT is NULL is zero */
2209 if (!buf)
2210 err = -ENOMEM;
2211 else {
2212 root_stable_tree = buf;
2213 root_unstable_tree = buf + nr_node_ids;
2214 /* Stable tree is empty but not the unstable */
2215 root_unstable_tree[0] = one_unstable_tree[0];
2216 }
2217 }
2218 if (!err) {
Petr Holasek90bd6fd2013-02-22 16:35:00 -08002219 ksm_merge_across_nodes = knob;
Hugh Dickinsef53d162013-02-22 16:36:12 -08002220 ksm_nr_node_ids = knob ? 1 : nr_node_ids;
2221 }
Petr Holasek90bd6fd2013-02-22 16:35:00 -08002222 }
2223 mutex_unlock(&ksm_thread_mutex);
2224
2225 return err ? err : count;
2226}
2227KSM_ATTR(merge_across_nodes);
2228#endif
2229
Hugh Dickinsb4028262009-09-21 17:02:09 -07002230static ssize_t pages_shared_show(struct kobject *kobj,
2231 struct kobj_attribute *attr, char *buf)
2232{
2233 return sprintf(buf, "%lu\n", ksm_pages_shared);
2234}
2235KSM_ATTR_RO(pages_shared);
2236
2237static ssize_t pages_sharing_show(struct kobject *kobj,
2238 struct kobj_attribute *attr, char *buf)
2239{
Hugh Dickinse178dfd2009-09-21 17:02:10 -07002240 return sprintf(buf, "%lu\n", ksm_pages_sharing);
Hugh Dickinsb4028262009-09-21 17:02:09 -07002241}
2242KSM_ATTR_RO(pages_sharing);
2243
Hugh Dickins473b0ce2009-09-21 17:02:11 -07002244static ssize_t pages_unshared_show(struct kobject *kobj,
2245 struct kobj_attribute *attr, char *buf)
2246{
2247 return sprintf(buf, "%lu\n", ksm_pages_unshared);
2248}
2249KSM_ATTR_RO(pages_unshared);
2250
2251static ssize_t pages_volatile_show(struct kobject *kobj,
2252 struct kobj_attribute *attr, char *buf)
2253{
2254 long ksm_pages_volatile;
2255
2256 ksm_pages_volatile = ksm_rmap_items - ksm_pages_shared
2257 - ksm_pages_sharing - ksm_pages_unshared;
2258 /*
2259 * It was not worth any locking to calculate that statistic,
2260 * but it might therefore sometimes be negative: conceal that.
2261 */
2262 if (ksm_pages_volatile < 0)
2263 ksm_pages_volatile = 0;
2264 return sprintf(buf, "%ld\n", ksm_pages_volatile);
2265}
2266KSM_ATTR_RO(pages_volatile);
2267
2268static ssize_t full_scans_show(struct kobject *kobj,
2269 struct kobj_attribute *attr, char *buf)
2270{
2271 return sprintf(buf, "%lu\n", ksm_scan.seqnr);
2272}
2273KSM_ATTR_RO(full_scans);
2274
Izik Eidus31dbd012009-09-21 17:02:03 -07002275static struct attribute *ksm_attrs[] = {
2276 &sleep_millisecs_attr.attr,
2277 &pages_to_scan_attr.attr,
2278 &run_attr.attr,
Hugh Dickinsb4028262009-09-21 17:02:09 -07002279 &pages_shared_attr.attr,
2280 &pages_sharing_attr.attr,
Hugh Dickins473b0ce2009-09-21 17:02:11 -07002281 &pages_unshared_attr.attr,
2282 &pages_volatile_attr.attr,
2283 &full_scans_attr.attr,
Petr Holasek90bd6fd2013-02-22 16:35:00 -08002284#ifdef CONFIG_NUMA
2285 &merge_across_nodes_attr.attr,
2286#endif
Izik Eidus31dbd012009-09-21 17:02:03 -07002287 NULL,
2288};
2289
2290static struct attribute_group ksm_attr_group = {
2291 .attrs = ksm_attrs,
2292 .name = "ksm",
2293};
Hugh Dickins2ffd8672009-09-21 17:02:23 -07002294#endif /* CONFIG_SYSFS */
Izik Eidus31dbd012009-09-21 17:02:03 -07002295
2296static int __init ksm_init(void)
2297{
2298 struct task_struct *ksm_thread;
2299 int err;
2300
2301 err = ksm_slab_init();
2302 if (err)
2303 goto out;
2304
Izik Eidus31dbd012009-09-21 17:02:03 -07002305 ksm_thread = kthread_run(ksm_scan_thread, NULL, "ksmd");
2306 if (IS_ERR(ksm_thread)) {
Paul McQuade25acde32014-10-09 15:29:09 -07002307 pr_err("ksm: creating kthread failed\n");
Izik Eidus31dbd012009-09-21 17:02:03 -07002308 err = PTR_ERR(ksm_thread);
Lai Jiangshand9f89842010-08-09 17:20:02 -07002309 goto out_free;
Izik Eidus31dbd012009-09-21 17:02:03 -07002310 }
2311
Hugh Dickins2ffd8672009-09-21 17:02:23 -07002312#ifdef CONFIG_SYSFS
Izik Eidus31dbd012009-09-21 17:02:03 -07002313 err = sysfs_create_group(mm_kobj, &ksm_attr_group);
2314 if (err) {
Paul McQuade25acde32014-10-09 15:29:09 -07002315 pr_err("ksm: register sysfs failed\n");
Hugh Dickins2ffd8672009-09-21 17:02:23 -07002316 kthread_stop(ksm_thread);
Lai Jiangshand9f89842010-08-09 17:20:02 -07002317 goto out_free;
Izik Eidus31dbd012009-09-21 17:02:03 -07002318 }
Hugh Dickinsc73602a2009-10-07 16:32:22 -07002319#else
2320 ksm_run = KSM_RUN_MERGE; /* no way for user to start it */
2321
Hugh Dickins2ffd8672009-09-21 17:02:23 -07002322#endif /* CONFIG_SYSFS */
Izik Eidus31dbd012009-09-21 17:02:03 -07002323
Hugh Dickins62b61f62009-12-14 17:59:33 -08002324#ifdef CONFIG_MEMORY_HOTREMOVE
Hugh Dickinsef4d43a2013-02-22 16:35:16 -08002325 /* There is no significance to this priority 100 */
Hugh Dickins62b61f62009-12-14 17:59:33 -08002326 hotplug_memory_notifier(ksm_memory_callback, 100);
2327#endif
Izik Eidus31dbd012009-09-21 17:02:03 -07002328 return 0;
2329
Lai Jiangshand9f89842010-08-09 17:20:02 -07002330out_free:
Izik Eidus31dbd012009-09-21 17:02:03 -07002331 ksm_slab_free();
2332out:
2333 return err;
2334}
Paul Gortmakera64fb3c2014-01-23 15:53:30 -08002335subsys_initcall(ksm_init);