ksm: fix oom deadlock
[kernel.git] / mm / ksm.c
1 /*
2  * 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  *
7  * Copyright (C) 2008-2009 Red Hat, Inc.
8  * Authors:
9  *      Izik Eidus
10  *      Andrea Arcangeli
11  *      Chris Wright
12  *      Hugh Dickins
13  *
14  * This work is licensed under the terms of the GNU GPL, version 2.
15  */
16
17 #include <linux/errno.h>
18 #include <linux/mm.h>
19 #include <linux/fs.h>
20 #include <linux/mman.h>
21 #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>
32 #include <linux/mmu_notifier.h>
33 #include <linux/ksm.h>
34
35 #include <asm/tlb.h>
36 #include <asm/tlbflush.h>
37
38 /*
39  * A few notes about the KSM scanning process,
40  * to make it easier to understand the data structures below:
41  *
42  * In order to reduce excessive scanning, KSM sorts the memory pages by their
43  * contents into a data structure that holds pointers to the pages' locations.
44  *
45  * Since the contents of the pages may change at any moment, KSM cannot just
46  * insert the pages into a normal sorted tree and expect it to find anything.
47  * Therefore KSM uses two data structures - the stable and the unstable tree.
48  *
49  * The stable tree holds pointers to all the merged pages (ksm pages), sorted
50  * by their contents.  Because each such page is write-protected, searching on
51  * this tree is fully assured to be working (except when pages are unmapped),
52  * and therefore this tree is called the stable tree.
53  *
54  * In addition to the stable tree, KSM uses a second data structure called the
55  * unstable tree: this tree holds pointers to pages which have been found to
56  * be "unchanged for a period of time".  The unstable tree sorts these pages
57  * by their contents, but since they are not write-protected, KSM cannot rely
58  * upon the unstable tree to work correctly - the unstable tree is liable to
59  * be corrupted as its contents are modified, and so it is called unstable.
60  *
61  * KSM solves this problem by several techniques:
62  *
63  * 1) The unstable tree is flushed every time KSM completes scanning all
64  *    memory areas, and then the tree is rebuilt again from the beginning.
65  * 2) KSM will only insert into the unstable tree, pages whose hash value
66  *    has not changed since the previous scan of all memory areas.
67  * 3) The unstable tree is a RedBlack Tree - so its balancing is based on the
68  *    colors of the nodes and not on their contents, assuring that even when
69  *    the tree gets "corrupted" it won't get out of balance, so scanning time
70  *    remains the same (also, searching and inserting nodes in an rbtree uses
71  *    the same algorithm, so we have no overhead when we flush and rebuild).
72  * 4) KSM never flushes the stable tree, which means that even if it were to
73  *    take 10 attempts to find a page in the unstable tree, once it is found,
74  *    it is secured in the stable tree.  (When we scan a new page, we first
75  *    compare it against the stable tree, and then against the unstable tree.)
76  */
77
78 /**
79  * struct mm_slot - ksm information per mm that is being scanned
80  * @link: link to the mm_slots hash list
81  * @mm_list: link into the mm_slots list, rooted in ksm_mm_head
82  * @rmap_list: head for this mm_slot's list of rmap_items
83  * @mm: the mm that this information is valid for
84  */
85 struct mm_slot {
86         struct hlist_node link;
87         struct list_head mm_list;
88         struct list_head rmap_list;
89         struct mm_struct *mm;
90 };
91
92 /**
93  * struct ksm_scan - cursor for scanning
94  * @mm_slot: the current mm_slot we are scanning
95  * @address: the next address inside that to be scanned
96  * @rmap_item: the current rmap that we are scanning inside the rmap_list
97  * @seqnr: count of completed full scans (needed when removing unstable node)
98  *
99  * There is only the one ksm_scan instance of this cursor structure.
100  */
101 struct ksm_scan {
102         struct mm_slot *mm_slot;
103         unsigned long address;
104         struct rmap_item *rmap_item;
105         unsigned long seqnr;
106 };
107
108 /**
109  * struct rmap_item - reverse mapping item for virtual addresses
110  * @link: link into mm_slot's rmap_list (rmap_list is per mm)
111  * @mm: the memory structure this rmap_item is pointing into
112  * @address: the virtual address this rmap_item tracks (+ flags in low bits)
113  * @oldchecksum: previous checksum of the page at that virtual address
114  * @node: rb_node of this rmap_item in either unstable or stable tree
115  * @next: next rmap_item hanging off the same node of the stable tree
116  * @prev: previous rmap_item hanging off the same node of the stable tree
117  */
118 struct rmap_item {
119         struct list_head link;
120         struct mm_struct *mm;
121         unsigned long address;          /* + low bits used for flags below */
122         union {
123                 unsigned int oldchecksum;               /* when unstable */
124                 struct rmap_item *next;                 /* when stable */
125         };
126         union {
127                 struct rb_node node;                    /* when tree node */
128                 struct rmap_item *prev;                 /* in stable list */
129         };
130 };
131
132 #define SEQNR_MASK      0x0ff   /* low bits of unstable tree seqnr */
133 #define NODE_FLAG       0x100   /* is a node of unstable or stable tree */
134 #define STABLE_FLAG     0x200   /* is a node or list item of stable tree */
135
136 /* The stable and unstable tree heads */
137 static struct rb_root root_stable_tree = RB_ROOT;
138 static struct rb_root root_unstable_tree = RB_ROOT;
139
140 #define MM_SLOTS_HASH_HEADS 1024
141 static struct hlist_head *mm_slots_hash;
142
143 static struct mm_slot ksm_mm_head = {
144         .mm_list = LIST_HEAD_INIT(ksm_mm_head.mm_list),
145 };
146 static struct ksm_scan ksm_scan = {
147         .mm_slot = &ksm_mm_head,
148 };
149
150 static struct kmem_cache *rmap_item_cache;
151 static struct kmem_cache *mm_slot_cache;
152
153 /* The number of nodes in the stable tree */
154 static unsigned long ksm_pages_shared;
155
156 /* The number of page slots additionally sharing those nodes */
157 static unsigned long ksm_pages_sharing;
158
159 /* The number of nodes in the unstable tree */
160 static unsigned long ksm_pages_unshared;
161
162 /* The number of rmap_items in use: to calculate pages_volatile */
163 static unsigned long ksm_rmap_items;
164
165 /* Limit on the number of unswappable pages used */
166 static unsigned long ksm_max_kernel_pages;
167
168 /* Number of pages ksmd should scan in one batch */
169 static unsigned int ksm_thread_pages_to_scan;
170
171 /* Milliseconds ksmd should sleep between batches */
172 static unsigned int ksm_thread_sleep_millisecs;
173
174 #define KSM_RUN_STOP    0
175 #define KSM_RUN_MERGE   1
176 #define KSM_RUN_UNMERGE 2
177 static unsigned int ksm_run;
178
179 static DECLARE_WAIT_QUEUE_HEAD(ksm_thread_wait);
180 static DEFINE_MUTEX(ksm_thread_mutex);
181 static DEFINE_SPINLOCK(ksm_mmlist_lock);
182
183 #define KSM_KMEM_CACHE(__struct, __flags) kmem_cache_create("ksm_"#__struct,\
184                 sizeof(struct __struct), __alignof__(struct __struct),\
185                 (__flags), NULL)
186
187 static int __init ksm_slab_init(void)
188 {
189         rmap_item_cache = KSM_KMEM_CACHE(rmap_item, 0);
190         if (!rmap_item_cache)
191                 goto out;
192
193         mm_slot_cache = KSM_KMEM_CACHE(mm_slot, 0);
194         if (!mm_slot_cache)
195                 goto out_free;
196
197         return 0;
198
199 out_free:
200         kmem_cache_destroy(rmap_item_cache);
201 out:
202         return -ENOMEM;
203 }
204
205 static void __init ksm_slab_free(void)
206 {
207         kmem_cache_destroy(mm_slot_cache);
208         kmem_cache_destroy(rmap_item_cache);
209         mm_slot_cache = NULL;
210 }
211
212 static inline struct rmap_item *alloc_rmap_item(void)
213 {
214         struct rmap_item *rmap_item;
215
216         rmap_item = kmem_cache_zalloc(rmap_item_cache, GFP_KERNEL);
217         if (rmap_item)
218                 ksm_rmap_items++;
219         return rmap_item;
220 }
221
222 static inline void free_rmap_item(struct rmap_item *rmap_item)
223 {
224         ksm_rmap_items--;
225         rmap_item->mm = NULL;   /* debug safety */
226         kmem_cache_free(rmap_item_cache, rmap_item);
227 }
228
229 static inline struct mm_slot *alloc_mm_slot(void)
230 {
231         if (!mm_slot_cache)     /* initialization failed */
232                 return NULL;
233         return kmem_cache_zalloc(mm_slot_cache, GFP_KERNEL);
234 }
235
236 static inline void free_mm_slot(struct mm_slot *mm_slot)
237 {
238         kmem_cache_free(mm_slot_cache, mm_slot);
239 }
240
241 static int __init mm_slots_hash_init(void)
242 {
243         mm_slots_hash = kzalloc(MM_SLOTS_HASH_HEADS * sizeof(struct hlist_head),
244                                 GFP_KERNEL);
245         if (!mm_slots_hash)
246                 return -ENOMEM;
247         return 0;
248 }
249
250 static void __init mm_slots_hash_free(void)
251 {
252         kfree(mm_slots_hash);
253 }
254
255 static struct mm_slot *get_mm_slot(struct mm_struct *mm)
256 {
257         struct mm_slot *mm_slot;
258         struct hlist_head *bucket;
259         struct hlist_node *node;
260
261         bucket = &mm_slots_hash[((unsigned long)mm / sizeof(struct mm_struct))
262                                 % MM_SLOTS_HASH_HEADS];
263         hlist_for_each_entry(mm_slot, node, bucket, link) {
264                 if (mm == mm_slot->mm)
265                         return mm_slot;
266         }
267         return NULL;
268 }
269
270 static void insert_to_mm_slots_hash(struct mm_struct *mm,
271                                     struct mm_slot *mm_slot)
272 {
273         struct hlist_head *bucket;
274
275         bucket = &mm_slots_hash[((unsigned long)mm / sizeof(struct mm_struct))
276                                 % MM_SLOTS_HASH_HEADS];
277         mm_slot->mm = mm;
278         INIT_LIST_HEAD(&mm_slot->rmap_list);
279         hlist_add_head(&mm_slot->link, bucket);
280 }
281
282 static inline int in_stable_tree(struct rmap_item *rmap_item)
283 {
284         return rmap_item->address & STABLE_FLAG;
285 }
286
287 /*
288  * We use break_ksm to break COW on a ksm page: it's a stripped down
289  *
290  *      if (get_user_pages(current, mm, addr, 1, 1, 1, &page, NULL) == 1)
291  *              put_page(page);
292  *
293  * but taking great care only to touch a ksm page, in a VM_MERGEABLE vma,
294  * in case the application has unmapped and remapped mm,addr meanwhile.
295  * Could a ksm page appear anywhere else?  Actually yes, in a VM_PFNMAP
296  * mmap of /dev/mem or /dev/kmem, where we would not want to touch it.
297  */
298 static int break_ksm(struct vm_area_struct *vma, unsigned long addr)
299 {
300         struct page *page;
301         int ret = 0;
302
303         do {
304                 cond_resched();
305                 page = follow_page(vma, addr, FOLL_GET);
306                 if (!page)
307                         break;
308                 if (PageKsm(page))
309                         ret = handle_mm_fault(vma->vm_mm, vma, addr,
310                                                         FAULT_FLAG_WRITE);
311                 else
312                         ret = VM_FAULT_WRITE;
313                 put_page(page);
314         } while (!(ret & (VM_FAULT_WRITE | VM_FAULT_SIGBUS | VM_FAULT_OOM)));
315         /*
316          * We must loop because handle_mm_fault() may back out if there's
317          * any difficulty e.g. if pte accessed bit gets updated concurrently.
318          *
319          * VM_FAULT_WRITE is what we have been hoping for: it indicates that
320          * COW has been broken, even if the vma does not permit VM_WRITE;
321          * but note that a concurrent fault might break PageKsm for us.
322          *
323          * VM_FAULT_SIGBUS could occur if we race with truncation of the
324          * backing file, which also invalidates anonymous pages: that's
325          * okay, that truncation will have unmapped the PageKsm for us.
326          *
327          * VM_FAULT_OOM: at the time of writing (late July 2009), setting
328          * aside mem_cgroup limits, VM_FAULT_OOM would only be set if the
329          * current task has TIF_MEMDIE set, and will be OOM killed on return
330          * to user; and ksmd, having no mm, would never be chosen for that.
331          *
332          * But if the mm is in a limited mem_cgroup, then the fault may fail
333          * with VM_FAULT_OOM even if the current task is not TIF_MEMDIE; and
334          * even ksmd can fail in this way - though it's usually breaking ksm
335          * just to undo a merge it made a moment before, so unlikely to oom.
336          *
337          * That's a pity: we might therefore have more kernel pages allocated
338          * than we're counting as nodes in the stable tree; but ksm_do_scan
339          * will retry to break_cow on each pass, so should recover the page
340          * in due course.  The important thing is to not let VM_MERGEABLE
341          * be cleared while any such pages might remain in the area.
342          */
343         return (ret & VM_FAULT_OOM) ? -ENOMEM : 0;
344 }
345
346 static void break_cow(struct mm_struct *mm, unsigned long addr)
347 {
348         struct vm_area_struct *vma;
349
350         down_read(&mm->mmap_sem);
351         if (ksm_test_exit(mm))
352                 goto out;
353         vma = find_vma(mm, addr);
354         if (!vma || vma->vm_start > addr)
355                 goto out;
356         if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)
357                 goto out;
358         break_ksm(vma, addr);
359 out:
360         up_read(&mm->mmap_sem);
361 }
362
363 static struct page *get_mergeable_page(struct rmap_item *rmap_item)
364 {
365         struct mm_struct *mm = rmap_item->mm;
366         unsigned long addr = rmap_item->address;
367         struct vm_area_struct *vma;
368         struct page *page;
369
370         down_read(&mm->mmap_sem);
371         if (ksm_test_exit(mm))
372                 goto out;
373         vma = find_vma(mm, addr);
374         if (!vma || vma->vm_start > addr)
375                 goto out;
376         if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)
377                 goto out;
378
379         page = follow_page(vma, addr, FOLL_GET);
380         if (!page)
381                 goto out;
382         if (PageAnon(page)) {
383                 flush_anon_page(vma, page, addr);
384                 flush_dcache_page(page);
385         } else {
386                 put_page(page);
387 out:            page = NULL;
388         }
389         up_read(&mm->mmap_sem);
390         return page;
391 }
392
393 /*
394  * get_ksm_page: checks if the page at the virtual address in rmap_item
395  * is still PageKsm, in which case we can trust the content of the page,
396  * and it returns the gotten page; but NULL if the page has been zapped.
397  */
398 static struct page *get_ksm_page(struct rmap_item *rmap_item)
399 {
400         struct page *page;
401
402         page = get_mergeable_page(rmap_item);
403         if (page && !PageKsm(page)) {
404                 put_page(page);
405                 page = NULL;
406         }
407         return page;
408 }
409
410 /*
411  * Removing rmap_item from stable or unstable tree.
412  * This function will clean the information from the stable/unstable tree.
413  */
414 static void remove_rmap_item_from_tree(struct rmap_item *rmap_item)
415 {
416         if (in_stable_tree(rmap_item)) {
417                 struct rmap_item *next_item = rmap_item->next;
418
419                 if (rmap_item->address & NODE_FLAG) {
420                         if (next_item) {
421                                 rb_replace_node(&rmap_item->node,
422                                                 &next_item->node,
423                                                 &root_stable_tree);
424                                 next_item->address |= NODE_FLAG;
425                                 ksm_pages_sharing--;
426                         } else {
427                                 rb_erase(&rmap_item->node, &root_stable_tree);
428                                 ksm_pages_shared--;
429                         }
430                 } else {
431                         struct rmap_item *prev_item = rmap_item->prev;
432
433                         BUG_ON(prev_item->next != rmap_item);
434                         prev_item->next = next_item;
435                         if (next_item) {
436                                 BUG_ON(next_item->prev != rmap_item);
437                                 next_item->prev = rmap_item->prev;
438                         }
439                         ksm_pages_sharing--;
440                 }
441
442                 rmap_item->next = NULL;
443
444         } else if (rmap_item->address & NODE_FLAG) {
445                 unsigned char age;
446                 /*
447                  * Usually ksmd can and must skip the rb_erase, because
448                  * root_unstable_tree was already reset to RB_ROOT.
449                  * But be careful when an mm is exiting: do the rb_erase
450                  * if this rmap_item was inserted by this scan, rather
451                  * than left over from before.
452                  */
453                 age = (unsigned char)(ksm_scan.seqnr - rmap_item->address);
454                 BUG_ON(age > 1);
455                 if (!age)
456                         rb_erase(&rmap_item->node, &root_unstable_tree);
457                 ksm_pages_unshared--;
458         }
459
460         rmap_item->address &= PAGE_MASK;
461
462         cond_resched();         /* we're called from many long loops */
463 }
464
465 static void remove_trailing_rmap_items(struct mm_slot *mm_slot,
466                                        struct list_head *cur)
467 {
468         struct rmap_item *rmap_item;
469
470         while (cur != &mm_slot->rmap_list) {
471                 rmap_item = list_entry(cur, struct rmap_item, link);
472                 cur = cur->next;
473                 remove_rmap_item_from_tree(rmap_item);
474                 list_del(&rmap_item->link);
475                 free_rmap_item(rmap_item);
476         }
477 }
478
479 /*
480  * Though it's very tempting to unmerge in_stable_tree(rmap_item)s rather
481  * than check every pte of a given vma, the locking doesn't quite work for
482  * that - an rmap_item is assigned to the stable tree after inserting ksm
483  * page and upping mmap_sem.  Nor does it fit with the way we skip dup'ing
484  * rmap_items from parent to child at fork time (so as not to waste time
485  * if exit comes before the next scan reaches it).
486  *
487  * Similarly, although we'd like to remove rmap_items (so updating counts
488  * and freeing memory) when unmerging an area, it's easier to leave that
489  * to the next pass of ksmd - consider, for example, how ksmd might be
490  * in cmp_and_merge_page on one of the rmap_items we would be removing.
491  */
492 static int unmerge_ksm_pages(struct vm_area_struct *vma,
493                              unsigned long start, unsigned long end)
494 {
495         unsigned long addr;
496         int err = 0;
497
498         for (addr = start; addr < end && !err; addr += PAGE_SIZE) {
499                 if (ksm_test_exit(vma->vm_mm))
500                         break;
501                 if (signal_pending(current))
502                         err = -ERESTARTSYS;
503                 else
504                         err = break_ksm(vma, addr);
505         }
506         return err;
507 }
508
509 static int unmerge_and_remove_all_rmap_items(void)
510 {
511         struct mm_slot *mm_slot;
512         struct mm_struct *mm;
513         struct vm_area_struct *vma;
514         int err = 0;
515
516         spin_lock(&ksm_mmlist_lock);
517         ksm_scan.mm_slot = list_entry(ksm_mm_head.mm_list.next,
518                                                 struct mm_slot, mm_list);
519         spin_unlock(&ksm_mmlist_lock);
520
521         for (mm_slot = ksm_scan.mm_slot;
522                         mm_slot != &ksm_mm_head; mm_slot = ksm_scan.mm_slot) {
523                 mm = mm_slot->mm;
524                 down_read(&mm->mmap_sem);
525                 for (vma = mm->mmap; vma; vma = vma->vm_next) {
526                         if (ksm_test_exit(mm))
527                                 break;
528                         if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)
529                                 continue;
530                         err = unmerge_ksm_pages(vma,
531                                                 vma->vm_start, vma->vm_end);
532                         if (err)
533                                 goto error;
534                 }
535
536                 remove_trailing_rmap_items(mm_slot, mm_slot->rmap_list.next);
537
538                 spin_lock(&ksm_mmlist_lock);
539                 ksm_scan.mm_slot = list_entry(mm_slot->mm_list.next,
540                                                 struct mm_slot, mm_list);
541                 if (ksm_test_exit(mm)) {
542                         hlist_del(&mm_slot->link);
543                         list_del(&mm_slot->mm_list);
544                         spin_unlock(&ksm_mmlist_lock);
545
546                         free_mm_slot(mm_slot);
547                         clear_bit(MMF_VM_MERGEABLE, &mm->flags);
548                         up_read(&mm->mmap_sem);
549                         mmdrop(mm);
550                 } else {
551                         spin_unlock(&ksm_mmlist_lock);
552                         up_read(&mm->mmap_sem);
553                 }
554         }
555
556         ksm_scan.seqnr = 0;
557         return 0;
558
559 error:
560         up_read(&mm->mmap_sem);
561         spin_lock(&ksm_mmlist_lock);
562         ksm_scan.mm_slot = &ksm_mm_head;
563         spin_unlock(&ksm_mmlist_lock);
564         return err;
565 }
566
567 static u32 calc_checksum(struct page *page)
568 {
569         u32 checksum;
570         void *addr = kmap_atomic(page, KM_USER0);
571         checksum = jhash2(addr, PAGE_SIZE / 4, 17);
572         kunmap_atomic(addr, KM_USER0);
573         return checksum;
574 }
575
576 static int memcmp_pages(struct page *page1, struct page *page2)
577 {
578         char *addr1, *addr2;
579         int ret;
580
581         addr1 = kmap_atomic(page1, KM_USER0);
582         addr2 = kmap_atomic(page2, KM_USER1);
583         ret = memcmp(addr1, addr2, PAGE_SIZE);
584         kunmap_atomic(addr2, KM_USER1);
585         kunmap_atomic(addr1, KM_USER0);
586         return ret;
587 }
588
589 static inline int pages_identical(struct page *page1, struct page *page2)
590 {
591         return !memcmp_pages(page1, page2);
592 }
593
594 static int write_protect_page(struct vm_area_struct *vma, struct page *page,
595                               pte_t *orig_pte)
596 {
597         struct mm_struct *mm = vma->vm_mm;
598         unsigned long addr;
599         pte_t *ptep;
600         spinlock_t *ptl;
601         int swapped;
602         int err = -EFAULT;
603
604         addr = page_address_in_vma(page, vma);
605         if (addr == -EFAULT)
606                 goto out;
607
608         ptep = page_check_address(page, mm, addr, &ptl, 0);
609         if (!ptep)
610                 goto out;
611
612         if (pte_write(*ptep)) {
613                 pte_t entry;
614
615                 swapped = PageSwapCache(page);
616                 flush_cache_page(vma, addr, page_to_pfn(page));
617                 /*
618                  * Ok this is tricky, when get_user_pages_fast() run it doesnt
619                  * take any lock, therefore the check that we are going to make
620                  * with the pagecount against the mapcount is racey and
621                  * O_DIRECT can happen right after the check.
622                  * So we clear the pte and flush the tlb before the check
623                  * this assure us that no O_DIRECT can happen after the check
624                  * or in the middle of the check.
625                  */
626                 entry = ptep_clear_flush(vma, addr, ptep);
627                 /*
628                  * Check that no O_DIRECT or similar I/O is in progress on the
629                  * page
630                  */
631                 if ((page_mapcount(page) + 2 + swapped) != page_count(page)) {
632                         set_pte_at_notify(mm, addr, ptep, entry);
633                         goto out_unlock;
634                 }
635                 entry = pte_wrprotect(entry);
636                 set_pte_at_notify(mm, addr, ptep, entry);
637         }
638         *orig_pte = *ptep;
639         err = 0;
640
641 out_unlock:
642         pte_unmap_unlock(ptep, ptl);
643 out:
644         return err;
645 }
646
647 /**
648  * replace_page - replace page in vma by new ksm page
649  * @vma:      vma that holds the pte pointing to oldpage
650  * @oldpage:  the page we are replacing by newpage
651  * @newpage:  the ksm page we replace oldpage by
652  * @orig_pte: the original value of the pte
653  *
654  * Returns 0 on success, -EFAULT on failure.
655  */
656 static int replace_page(struct vm_area_struct *vma, struct page *oldpage,
657                         struct page *newpage, pte_t orig_pte)
658 {
659         struct mm_struct *mm = vma->vm_mm;
660         pgd_t *pgd;
661         pud_t *pud;
662         pmd_t *pmd;
663         pte_t *ptep;
664         spinlock_t *ptl;
665         unsigned long addr;
666         pgprot_t prot;
667         int err = -EFAULT;
668
669         prot = vm_get_page_prot(vma->vm_flags & ~VM_WRITE);
670
671         addr = page_address_in_vma(oldpage, vma);
672         if (addr == -EFAULT)
673                 goto out;
674
675         pgd = pgd_offset(mm, addr);
676         if (!pgd_present(*pgd))
677                 goto out;
678
679         pud = pud_offset(pgd, addr);
680         if (!pud_present(*pud))
681                 goto out;
682
683         pmd = pmd_offset(pud, addr);
684         if (!pmd_present(*pmd))
685                 goto out;
686
687         ptep = pte_offset_map_lock(mm, pmd, addr, &ptl);
688         if (!pte_same(*ptep, orig_pte)) {
689                 pte_unmap_unlock(ptep, ptl);
690                 goto out;
691         }
692
693         get_page(newpage);
694         page_add_ksm_rmap(newpage);
695
696         flush_cache_page(vma, addr, pte_pfn(*ptep));
697         ptep_clear_flush(vma, addr, ptep);
698         set_pte_at_notify(mm, addr, ptep, mk_pte(newpage, prot));
699
700         page_remove_rmap(oldpage);
701         put_page(oldpage);
702
703         pte_unmap_unlock(ptep, ptl);
704         err = 0;
705 out:
706         return err;
707 }
708
709 /*
710  * try_to_merge_one_page - take two pages and merge them into one
711  * @vma: the vma that hold the pte pointing into oldpage
712  * @oldpage: the page that we want to replace with newpage
713  * @newpage: the page that we want to map instead of oldpage
714  *
715  * Note:
716  * oldpage should be a PageAnon page, while newpage should be a PageKsm page,
717  * or a newly allocated kernel page which page_add_ksm_rmap will make PageKsm.
718  *
719  * This function returns 0 if the pages were merged, -EFAULT otherwise.
720  */
721 static int try_to_merge_one_page(struct vm_area_struct *vma,
722                                  struct page *oldpage,
723                                  struct page *newpage)
724 {
725         pte_t orig_pte = __pte(0);
726         int err = -EFAULT;
727
728         if (!(vma->vm_flags & VM_MERGEABLE))
729                 goto out;
730
731         if (!PageAnon(oldpage))
732                 goto out;
733
734         get_page(newpage);
735         get_page(oldpage);
736
737         /*
738          * We need the page lock to read a stable PageSwapCache in
739          * write_protect_page().  We use trylock_page() instead of
740          * lock_page() because we don't want to wait here - we
741          * prefer to continue scanning and merging different pages,
742          * then come back to this page when it is unlocked.
743          */
744         if (!trylock_page(oldpage))
745                 goto out_putpage;
746         /*
747          * If this anonymous page is mapped only here, its pte may need
748          * to be write-protected.  If it's mapped elsewhere, all of its
749          * ptes are necessarily already write-protected.  But in either
750          * case, we need to lock and check page_count is not raised.
751          */
752         if (write_protect_page(vma, oldpage, &orig_pte)) {
753                 unlock_page(oldpage);
754                 goto out_putpage;
755         }
756         unlock_page(oldpage);
757
758         if (pages_identical(oldpage, newpage))
759                 err = replace_page(vma, oldpage, newpage, orig_pte);
760
761 out_putpage:
762         put_page(oldpage);
763         put_page(newpage);
764 out:
765         return err;
766 }
767
768 /*
769  * try_to_merge_with_ksm_page - like try_to_merge_two_pages,
770  * but no new kernel page is allocated: kpage must already be a ksm page.
771  */
772 static int try_to_merge_with_ksm_page(struct mm_struct *mm1,
773                                       unsigned long addr1,
774                                       struct page *page1,
775                                       struct page *kpage)
776 {
777         struct vm_area_struct *vma;
778         int err = -EFAULT;
779
780         down_read(&mm1->mmap_sem);
781         if (ksm_test_exit(mm1))
782                 goto out;
783
784         vma = find_vma(mm1, addr1);
785         if (!vma || vma->vm_start > addr1)
786                 goto out;
787
788         err = try_to_merge_one_page(vma, page1, kpage);
789 out:
790         up_read(&mm1->mmap_sem);
791         return err;
792 }
793
794 /*
795  * try_to_merge_two_pages - take two identical pages and prepare them
796  * to be merged into one page.
797  *
798  * This function returns 0 if we successfully mapped two identical pages
799  * into one page, -EFAULT otherwise.
800  *
801  * Note that this function allocates a new kernel page: if one of the pages
802  * is already a ksm page, try_to_merge_with_ksm_page should be used.
803  */
804 static int try_to_merge_two_pages(struct mm_struct *mm1, unsigned long addr1,
805                                   struct page *page1, struct mm_struct *mm2,
806                                   unsigned long addr2, struct page *page2)
807 {
808         struct vm_area_struct *vma;
809         struct page *kpage;
810         int err = -EFAULT;
811
812         /*
813          * The number of nodes in the stable tree
814          * is the number of kernel pages that we hold.
815          */
816         if (ksm_max_kernel_pages &&
817             ksm_max_kernel_pages <= ksm_pages_shared)
818                 return err;
819
820         kpage = alloc_page(GFP_HIGHUSER);
821         if (!kpage)
822                 return err;
823
824         down_read(&mm1->mmap_sem);
825         if (ksm_test_exit(mm1)) {
826                 up_read(&mm1->mmap_sem);
827                 goto out;
828         }
829         vma = find_vma(mm1, addr1);
830         if (!vma || vma->vm_start > addr1) {
831                 up_read(&mm1->mmap_sem);
832                 goto out;
833         }
834
835         copy_user_highpage(kpage, page1, addr1, vma);
836         err = try_to_merge_one_page(vma, page1, kpage);
837         up_read(&mm1->mmap_sem);
838
839         if (!err) {
840                 err = try_to_merge_with_ksm_page(mm2, addr2, page2, kpage);
841                 /*
842                  * If that fails, we have a ksm page with only one pte
843                  * pointing to it: so break it.
844                  */
845                 if (err)
846                         break_cow(mm1, addr1);
847         }
848 out:
849         put_page(kpage);
850         return err;
851 }
852
853 /*
854  * stable_tree_search - search page inside the stable tree
855  * @page: the page that we are searching identical pages to.
856  * @page2: pointer into identical page that we are holding inside the stable
857  *         tree that we have found.
858  * @rmap_item: the reverse mapping item
859  *
860  * This function checks if there is a page inside the stable tree
861  * with identical content to the page that we are scanning right now.
862  *
863  * This function return rmap_item pointer to the identical item if found,
864  * NULL otherwise.
865  */
866 static struct rmap_item *stable_tree_search(struct page *page,
867                                             struct page **page2,
868                                             struct rmap_item *rmap_item)
869 {
870         struct rb_node *node = root_stable_tree.rb_node;
871
872         while (node) {
873                 struct rmap_item *tree_rmap_item, *next_rmap_item;
874                 int ret;
875
876                 tree_rmap_item = rb_entry(node, struct rmap_item, node);
877                 while (tree_rmap_item) {
878                         BUG_ON(!in_stable_tree(tree_rmap_item));
879                         cond_resched();
880                         page2[0] = get_ksm_page(tree_rmap_item);
881                         if (page2[0])
882                                 break;
883                         next_rmap_item = tree_rmap_item->next;
884                         remove_rmap_item_from_tree(tree_rmap_item);
885                         tree_rmap_item = next_rmap_item;
886                 }
887                 if (!tree_rmap_item)
888                         return NULL;
889
890                 ret = memcmp_pages(page, page2[0]);
891
892                 if (ret < 0) {
893                         put_page(page2[0]);
894                         node = node->rb_left;
895                 } else if (ret > 0) {
896                         put_page(page2[0]);
897                         node = node->rb_right;
898                 } else {
899                         return tree_rmap_item;
900                 }
901         }
902
903         return NULL;
904 }
905
906 /*
907  * stable_tree_insert - insert rmap_item pointing to new ksm page
908  * into the stable tree.
909  *
910  * @page: the page that we are searching identical page to inside the stable
911  *        tree.
912  * @rmap_item: pointer to the reverse mapping item.
913  *
914  * This function returns rmap_item if success, NULL otherwise.
915  */
916 static struct rmap_item *stable_tree_insert(struct page *page,
917                                             struct rmap_item *rmap_item)
918 {
919         struct rb_node **new = &root_stable_tree.rb_node;
920         struct rb_node *parent = NULL;
921
922         while (*new) {
923                 struct rmap_item *tree_rmap_item, *next_rmap_item;
924                 struct page *tree_page;
925                 int ret;
926
927                 tree_rmap_item = rb_entry(*new, struct rmap_item, node);
928                 while (tree_rmap_item) {
929                         BUG_ON(!in_stable_tree(tree_rmap_item));
930                         cond_resched();
931                         tree_page = get_ksm_page(tree_rmap_item);
932                         if (tree_page)
933                                 break;
934                         next_rmap_item = tree_rmap_item->next;
935                         remove_rmap_item_from_tree(tree_rmap_item);
936                         tree_rmap_item = next_rmap_item;
937                 }
938                 if (!tree_rmap_item)
939                         return NULL;
940
941                 ret = memcmp_pages(page, tree_page);
942                 put_page(tree_page);
943
944                 parent = *new;
945                 if (ret < 0)
946                         new = &parent->rb_left;
947                 else if (ret > 0)
948                         new = &parent->rb_right;
949                 else {
950                         /*
951                          * It is not a bug that stable_tree_search() didn't
952                          * find this node: because at that time our page was
953                          * not yet write-protected, so may have changed since.
954                          */
955                         return NULL;
956                 }
957         }
958
959         rmap_item->address |= NODE_FLAG | STABLE_FLAG;
960         rmap_item->next = NULL;
961         rb_link_node(&rmap_item->node, parent, new);
962         rb_insert_color(&rmap_item->node, &root_stable_tree);
963
964         ksm_pages_shared++;
965         return rmap_item;
966 }
967
968 /*
969  * unstable_tree_search_insert - search and insert items into the unstable tree.
970  *
971  * @page: the page that we are going to search for identical page or to insert
972  *        into the unstable tree
973  * @page2: pointer into identical page that was found inside the unstable tree
974  * @rmap_item: the reverse mapping item of page
975  *
976  * This function searches for a page in the unstable tree identical to the
977  * page currently being scanned; and if no identical page is found in the
978  * tree, we insert rmap_item as a new object into the unstable tree.
979  *
980  * This function returns pointer to rmap_item found to be identical
981  * to the currently scanned page, NULL otherwise.
982  *
983  * This function does both searching and inserting, because they share
984  * the same walking algorithm in an rbtree.
985  */
986 static struct rmap_item *unstable_tree_search_insert(struct page *page,
987                                                 struct page **page2,
988                                                 struct rmap_item *rmap_item)
989 {
990         struct rb_node **new = &root_unstable_tree.rb_node;
991         struct rb_node *parent = NULL;
992
993         while (*new) {
994                 struct rmap_item *tree_rmap_item;
995                 int ret;
996
997                 tree_rmap_item = rb_entry(*new, struct rmap_item, node);
998                 page2[0] = get_mergeable_page(tree_rmap_item);
999                 if (!page2[0])
1000                         return NULL;
1001
1002                 /*
1003                  * Don't substitute an unswappable ksm page
1004                  * just for one good swappable forked page.
1005                  */
1006                 if (page == page2[0]) {
1007                         put_page(page2[0]);
1008                         return NULL;
1009                 }
1010
1011                 ret = memcmp_pages(page, page2[0]);
1012
1013                 parent = *new;
1014                 if (ret < 0) {
1015                         put_page(page2[0]);
1016                         new = &parent->rb_left;
1017                 } else if (ret > 0) {
1018                         put_page(page2[0]);
1019                         new = &parent->rb_right;
1020                 } else {
1021                         return tree_rmap_item;
1022                 }
1023         }
1024
1025         rmap_item->address |= NODE_FLAG;
1026         rmap_item->address |= (ksm_scan.seqnr & SEQNR_MASK);
1027         rb_link_node(&rmap_item->node, parent, new);
1028         rb_insert_color(&rmap_item->node, &root_unstable_tree);
1029
1030         ksm_pages_unshared++;
1031         return NULL;
1032 }
1033
1034 /*
1035  * stable_tree_append - add another rmap_item to the linked list of
1036  * rmap_items hanging off a given node of the stable tree, all sharing
1037  * the same ksm page.
1038  */
1039 static void stable_tree_append(struct rmap_item *rmap_item,
1040                                struct rmap_item *tree_rmap_item)
1041 {
1042         rmap_item->next = tree_rmap_item->next;
1043         rmap_item->prev = tree_rmap_item;
1044
1045         if (tree_rmap_item->next)
1046                 tree_rmap_item->next->prev = rmap_item;
1047
1048         tree_rmap_item->next = rmap_item;
1049         rmap_item->address |= STABLE_FLAG;
1050
1051         ksm_pages_sharing++;
1052 }
1053
1054 /*
1055  * cmp_and_merge_page - first see if page can be merged into the stable tree;
1056  * if not, compare checksum to previous and if it's the same, see if page can
1057  * be inserted into the unstable tree, or merged with a page already there and
1058  * both transferred to the stable tree.
1059  *
1060  * @page: the page that we are searching identical page to.
1061  * @rmap_item: the reverse mapping into the virtual address of this page
1062  */
1063 static void cmp_and_merge_page(struct page *page, struct rmap_item *rmap_item)
1064 {
1065         struct page *page2[1];
1066         struct rmap_item *tree_rmap_item;
1067         unsigned int checksum;
1068         int err;
1069
1070         if (in_stable_tree(rmap_item))
1071                 remove_rmap_item_from_tree(rmap_item);
1072
1073         /* We first start with searching the page inside the stable tree */
1074         tree_rmap_item = stable_tree_search(page, page2, rmap_item);
1075         if (tree_rmap_item) {
1076                 if (page == page2[0])                   /* forked */
1077                         err = 0;
1078                 else
1079                         err = try_to_merge_with_ksm_page(rmap_item->mm,
1080                                                          rmap_item->address,
1081                                                          page, page2[0]);
1082                 put_page(page2[0]);
1083
1084                 if (!err) {
1085                         /*
1086                          * The page was successfully merged:
1087                          * add its rmap_item to the stable tree.
1088                          */
1089                         stable_tree_append(rmap_item, tree_rmap_item);
1090                 }
1091                 return;
1092         }
1093
1094         /*
1095          * A ksm page might have got here by fork, but its other
1096          * references have already been removed from the stable tree.
1097          * Or it might be left over from a break_ksm which failed
1098          * when the mem_cgroup had reached its limit: try again now.
1099          */
1100         if (PageKsm(page))
1101                 break_cow(rmap_item->mm, rmap_item->address);
1102
1103         /*
1104          * In case the hash value of the page was changed from the last time we
1105          * have calculated it, this page to be changed frequely, therefore we
1106          * don't want to insert it to the unstable tree, and we don't want to
1107          * waste our time to search if there is something identical to it there.
1108          */
1109         checksum = calc_checksum(page);
1110         if (rmap_item->oldchecksum != checksum) {
1111                 rmap_item->oldchecksum = checksum;
1112                 return;
1113         }
1114
1115         tree_rmap_item = unstable_tree_search_insert(page, page2, rmap_item);
1116         if (tree_rmap_item) {
1117                 err = try_to_merge_two_pages(rmap_item->mm,
1118                                              rmap_item->address, page,
1119                                              tree_rmap_item->mm,
1120                                              tree_rmap_item->address, page2[0]);
1121                 /*
1122                  * As soon as we merge this page, we want to remove the
1123                  * rmap_item of the page we have merged with from the unstable
1124                  * tree, and insert it instead as new node in the stable tree.
1125                  */
1126                 if (!err) {
1127                         rb_erase(&tree_rmap_item->node, &root_unstable_tree);
1128                         tree_rmap_item->address &= ~NODE_FLAG;
1129                         ksm_pages_unshared--;
1130
1131                         /*
1132                          * If we fail to insert the page into the stable tree,
1133                          * we will have 2 virtual addresses that are pointing
1134                          * to a ksm page left outside the stable tree,
1135                          * in which case we need to break_cow on both.
1136                          */
1137                         if (stable_tree_insert(page2[0], tree_rmap_item))
1138                                 stable_tree_append(rmap_item, tree_rmap_item);
1139                         else {
1140                                 break_cow(tree_rmap_item->mm,
1141                                                 tree_rmap_item->address);
1142                                 break_cow(rmap_item->mm, rmap_item->address);
1143                         }
1144                 }
1145
1146                 put_page(page2[0]);
1147         }
1148 }
1149
1150 static struct rmap_item *get_next_rmap_item(struct mm_slot *mm_slot,
1151                                             struct list_head *cur,
1152                                             unsigned long addr)
1153 {
1154         struct rmap_item *rmap_item;
1155
1156         while (cur != &mm_slot->rmap_list) {
1157                 rmap_item = list_entry(cur, struct rmap_item, link);
1158                 if ((rmap_item->address & PAGE_MASK) == addr) {
1159                         if (!in_stable_tree(rmap_item))
1160                                 remove_rmap_item_from_tree(rmap_item);
1161                         return rmap_item;
1162                 }
1163                 if (rmap_item->address > addr)
1164                         break;
1165                 cur = cur->next;
1166                 remove_rmap_item_from_tree(rmap_item);
1167                 list_del(&rmap_item->link);
1168                 free_rmap_item(rmap_item);
1169         }
1170
1171         rmap_item = alloc_rmap_item();
1172         if (rmap_item) {
1173                 /* It has already been zeroed */
1174                 rmap_item->mm = mm_slot->mm;
1175                 rmap_item->address = addr;
1176                 list_add_tail(&rmap_item->link, cur);
1177         }
1178         return rmap_item;
1179 }
1180
1181 static struct rmap_item *scan_get_next_rmap_item(struct page **page)
1182 {
1183         struct mm_struct *mm;
1184         struct mm_slot *slot;
1185         struct vm_area_struct *vma;
1186         struct rmap_item *rmap_item;
1187
1188         if (list_empty(&ksm_mm_head.mm_list))
1189                 return NULL;
1190
1191         slot = ksm_scan.mm_slot;
1192         if (slot == &ksm_mm_head) {
1193                 root_unstable_tree = RB_ROOT;
1194
1195                 spin_lock(&ksm_mmlist_lock);
1196                 slot = list_entry(slot->mm_list.next, struct mm_slot, mm_list);
1197                 ksm_scan.mm_slot = slot;
1198                 spin_unlock(&ksm_mmlist_lock);
1199 next_mm:
1200                 ksm_scan.address = 0;
1201                 ksm_scan.rmap_item = list_entry(&slot->rmap_list,
1202                                                 struct rmap_item, link);
1203         }
1204
1205         mm = slot->mm;
1206         down_read(&mm->mmap_sem);
1207         if (ksm_test_exit(mm))
1208                 vma = NULL;
1209         else
1210                 vma = find_vma(mm, ksm_scan.address);
1211
1212         for (; vma; vma = vma->vm_next) {
1213                 if (!(vma->vm_flags & VM_MERGEABLE))
1214                         continue;
1215                 if (ksm_scan.address < vma->vm_start)
1216                         ksm_scan.address = vma->vm_start;
1217                 if (!vma->anon_vma)
1218                         ksm_scan.address = vma->vm_end;
1219
1220                 while (ksm_scan.address < vma->vm_end) {
1221                         if (ksm_test_exit(mm))
1222                                 break;
1223                         *page = follow_page(vma, ksm_scan.address, FOLL_GET);
1224                         if (*page && PageAnon(*page)) {
1225                                 flush_anon_page(vma, *page, ksm_scan.address);
1226                                 flush_dcache_page(*page);
1227                                 rmap_item = get_next_rmap_item(slot,
1228                                         ksm_scan.rmap_item->link.next,
1229                                         ksm_scan.address);
1230                                 if (rmap_item) {
1231                                         ksm_scan.rmap_item = rmap_item;
1232                                         ksm_scan.address += PAGE_SIZE;
1233                                 } else
1234                                         put_page(*page);
1235                                 up_read(&mm->mmap_sem);
1236                                 return rmap_item;
1237                         }
1238                         if (*page)
1239                                 put_page(*page);
1240                         ksm_scan.address += PAGE_SIZE;
1241                         cond_resched();
1242                 }
1243         }
1244
1245         if (ksm_test_exit(mm)) {
1246                 ksm_scan.address = 0;
1247                 ksm_scan.rmap_item = list_entry(&slot->rmap_list,
1248                                                 struct rmap_item, link);
1249         }
1250         /*
1251          * Nuke all the rmap_items that are above this current rmap:
1252          * because there were no VM_MERGEABLE vmas with such addresses.
1253          */
1254         remove_trailing_rmap_items(slot, ksm_scan.rmap_item->link.next);
1255
1256         spin_lock(&ksm_mmlist_lock);
1257         ksm_scan.mm_slot = list_entry(slot->mm_list.next,
1258                                                 struct mm_slot, mm_list);
1259         if (ksm_scan.address == 0) {
1260                 /*
1261                  * We've completed a full scan of all vmas, holding mmap_sem
1262                  * throughout, and found no VM_MERGEABLE: so do the same as
1263                  * __ksm_exit does to remove this mm from all our lists now.
1264                  * This applies either when cleaning up after __ksm_exit
1265                  * (but beware: we can reach here even before __ksm_exit),
1266                  * or when all VM_MERGEABLE areas have been unmapped (and
1267                  * mmap_sem then protects against race with MADV_MERGEABLE).
1268                  */
1269                 hlist_del(&slot->link);
1270                 list_del(&slot->mm_list);
1271                 spin_unlock(&ksm_mmlist_lock);
1272
1273                 free_mm_slot(slot);
1274                 clear_bit(MMF_VM_MERGEABLE, &mm->flags);
1275                 up_read(&mm->mmap_sem);
1276                 mmdrop(mm);
1277         } else {
1278                 spin_unlock(&ksm_mmlist_lock);
1279                 up_read(&mm->mmap_sem);
1280         }
1281
1282         /* Repeat until we've completed scanning the whole list */
1283         slot = ksm_scan.mm_slot;
1284         if (slot != &ksm_mm_head)
1285                 goto next_mm;
1286
1287         ksm_scan.seqnr++;
1288         return NULL;
1289 }
1290
1291 /**
1292  * ksm_do_scan  - the ksm scanner main worker function.
1293  * @scan_npages - number of pages we want to scan before we return.
1294  */
1295 static void ksm_do_scan(unsigned int scan_npages)
1296 {
1297         struct rmap_item *rmap_item;
1298         struct page *page;
1299
1300         while (scan_npages--) {
1301                 cond_resched();
1302                 rmap_item = scan_get_next_rmap_item(&page);
1303                 if (!rmap_item)
1304                         return;
1305                 if (!PageKsm(page) || !in_stable_tree(rmap_item))
1306                         cmp_and_merge_page(page, rmap_item);
1307                 else if (page_mapcount(page) == 1) {
1308                         /*
1309                          * Replace now-unshared ksm page by ordinary page.
1310                          */
1311                         break_cow(rmap_item->mm, rmap_item->address);
1312                         remove_rmap_item_from_tree(rmap_item);
1313                         rmap_item->oldchecksum = calc_checksum(page);
1314                 }
1315                 put_page(page);
1316         }
1317 }
1318
1319 static int ksmd_should_run(void)
1320 {
1321         return (ksm_run & KSM_RUN_MERGE) && !list_empty(&ksm_mm_head.mm_list);
1322 }
1323
1324 static int ksm_scan_thread(void *nothing)
1325 {
1326         set_user_nice(current, 5);
1327
1328         while (!kthread_should_stop()) {
1329                 mutex_lock(&ksm_thread_mutex);
1330                 if (ksmd_should_run())
1331                         ksm_do_scan(ksm_thread_pages_to_scan);
1332                 mutex_unlock(&ksm_thread_mutex);
1333
1334                 if (ksmd_should_run()) {
1335                         schedule_timeout_interruptible(
1336                                 msecs_to_jiffies(ksm_thread_sleep_millisecs));
1337                 } else {
1338                         wait_event_interruptible(ksm_thread_wait,
1339                                 ksmd_should_run() || kthread_should_stop());
1340                 }
1341         }
1342         return 0;
1343 }
1344
1345 int ksm_madvise(struct vm_area_struct *vma, unsigned long start,
1346                 unsigned long end, int advice, unsigned long *vm_flags)
1347 {
1348         struct mm_struct *mm = vma->vm_mm;
1349         int err;
1350
1351         switch (advice) {
1352         case MADV_MERGEABLE:
1353                 /*
1354                  * Be somewhat over-protective for now!
1355                  */
1356                 if (*vm_flags & (VM_MERGEABLE | VM_SHARED  | VM_MAYSHARE   |
1357                                  VM_PFNMAP    | VM_IO      | VM_DONTEXPAND |
1358                                  VM_RESERVED  | VM_HUGETLB | VM_INSERTPAGE |
1359                                  VM_MIXEDMAP  | VM_SAO))
1360                         return 0;               /* just ignore the advice */
1361
1362                 if (!test_bit(MMF_VM_MERGEABLE, &mm->flags)) {
1363                         err = __ksm_enter(mm);
1364                         if (err)
1365                                 return err;
1366                 }
1367
1368                 *vm_flags |= VM_MERGEABLE;
1369                 break;
1370
1371         case MADV_UNMERGEABLE:
1372                 if (!(*vm_flags & VM_MERGEABLE))
1373                         return 0;               /* just ignore the advice */
1374
1375                 if (vma->anon_vma) {
1376                         err = unmerge_ksm_pages(vma, start, end);
1377                         if (err)
1378                                 return err;
1379                 }
1380
1381                 *vm_flags &= ~VM_MERGEABLE;
1382                 break;
1383         }
1384
1385         return 0;
1386 }
1387
1388 int __ksm_enter(struct mm_struct *mm)
1389 {
1390         struct mm_slot *mm_slot;
1391         int needs_wakeup;
1392
1393         mm_slot = alloc_mm_slot();
1394         if (!mm_slot)
1395                 return -ENOMEM;
1396
1397         /* Check ksm_run too?  Would need tighter locking */
1398         needs_wakeup = list_empty(&ksm_mm_head.mm_list);
1399
1400         spin_lock(&ksm_mmlist_lock);
1401         insert_to_mm_slots_hash(mm, mm_slot);
1402         /*
1403          * Insert just behind the scanning cursor, to let the area settle
1404          * down a little; when fork is followed by immediate exec, we don't
1405          * want ksmd to waste time setting up and tearing down an rmap_list.
1406          */
1407         list_add_tail(&mm_slot->mm_list, &ksm_scan.mm_slot->mm_list);
1408         spin_unlock(&ksm_mmlist_lock);
1409
1410         set_bit(MMF_VM_MERGEABLE, &mm->flags);
1411         atomic_inc(&mm->mm_count);
1412
1413         if (needs_wakeup)
1414                 wake_up_interruptible(&ksm_thread_wait);
1415
1416         return 0;
1417 }
1418
1419 void __ksm_exit(struct mm_struct *mm,
1420                 struct mmu_gather **tlbp, unsigned long end)
1421 {
1422         struct mm_slot *mm_slot;
1423         int easy_to_free = 0;
1424
1425         /*
1426          * This process is exiting: if it's straightforward (as is the
1427          * case when ksmd was never running), free mm_slot immediately.
1428          * But if it's at the cursor or has rmap_items linked to it, use
1429          * mmap_sem to synchronize with any break_cows before pagetables
1430          * are freed, and leave the mm_slot on the list for ksmd to free.
1431          * Beware: ksm may already have noticed it exiting and freed the slot.
1432          */
1433
1434         spin_lock(&ksm_mmlist_lock);
1435         mm_slot = get_mm_slot(mm);
1436         if (mm_slot && ksm_scan.mm_slot != mm_slot) {
1437                 if (list_empty(&mm_slot->rmap_list)) {
1438                         hlist_del(&mm_slot->link);
1439                         list_del(&mm_slot->mm_list);
1440                         easy_to_free = 1;
1441                 } else {
1442                         list_move(&mm_slot->mm_list,
1443                                   &ksm_scan.mm_slot->mm_list);
1444                 }
1445         }
1446         spin_unlock(&ksm_mmlist_lock);
1447
1448         if (easy_to_free) {
1449                 free_mm_slot(mm_slot);
1450                 clear_bit(MMF_VM_MERGEABLE, &mm->flags);
1451                 mmdrop(mm);
1452         } else if (mm_slot) {
1453                 tlb_finish_mmu(*tlbp, 0, end);
1454                 down_write(&mm->mmap_sem);
1455                 up_write(&mm->mmap_sem);
1456                 *tlbp = tlb_gather_mmu(mm, 1);
1457         }
1458 }
1459
1460 #define KSM_ATTR_RO(_name) \
1461         static struct kobj_attribute _name##_attr = __ATTR_RO(_name)
1462 #define KSM_ATTR(_name) \
1463         static struct kobj_attribute _name##_attr = \
1464                 __ATTR(_name, 0644, _name##_show, _name##_store)
1465
1466 static ssize_t sleep_millisecs_show(struct kobject *kobj,
1467                                     struct kobj_attribute *attr, char *buf)
1468 {
1469         return sprintf(buf, "%u\n", ksm_thread_sleep_millisecs);
1470 }
1471
1472 static ssize_t sleep_millisecs_store(struct kobject *kobj,
1473                                      struct kobj_attribute *attr,
1474                                      const char *buf, size_t count)
1475 {
1476         unsigned long msecs;
1477         int err;
1478
1479         err = strict_strtoul(buf, 10, &msecs);
1480         if (err || msecs > UINT_MAX)
1481                 return -EINVAL;
1482
1483         ksm_thread_sleep_millisecs = msecs;
1484
1485         return count;
1486 }
1487 KSM_ATTR(sleep_millisecs);
1488
1489 static ssize_t pages_to_scan_show(struct kobject *kobj,
1490                                   struct kobj_attribute *attr, char *buf)
1491 {
1492         return sprintf(buf, "%u\n", ksm_thread_pages_to_scan);
1493 }
1494
1495 static ssize_t pages_to_scan_store(struct kobject *kobj,
1496                                    struct kobj_attribute *attr,
1497                                    const char *buf, size_t count)
1498 {
1499         int err;
1500         unsigned long nr_pages;
1501
1502         err = strict_strtoul(buf, 10, &nr_pages);
1503         if (err || nr_pages > UINT_MAX)
1504                 return -EINVAL;
1505
1506         ksm_thread_pages_to_scan = nr_pages;
1507
1508         return count;
1509 }
1510 KSM_ATTR(pages_to_scan);
1511
1512 static ssize_t run_show(struct kobject *kobj, struct kobj_attribute *attr,
1513                         char *buf)
1514 {
1515         return sprintf(buf, "%u\n", ksm_run);
1516 }
1517
1518 static ssize_t run_store(struct kobject *kobj, struct kobj_attribute *attr,
1519                          const char *buf, size_t count)
1520 {
1521         int err;
1522         unsigned long flags;
1523
1524         err = strict_strtoul(buf, 10, &flags);
1525         if (err || flags > UINT_MAX)
1526                 return -EINVAL;
1527         if (flags > KSM_RUN_UNMERGE)
1528                 return -EINVAL;
1529
1530         /*
1531          * KSM_RUN_MERGE sets ksmd running, and 0 stops it running.
1532          * KSM_RUN_UNMERGE stops it running and unmerges all rmap_items,
1533          * breaking COW to free the unswappable pages_shared (but leaves
1534          * mm_slots on the list for when ksmd may be set running again).
1535          */
1536
1537         mutex_lock(&ksm_thread_mutex);
1538         if (ksm_run != flags) {
1539                 ksm_run = flags;
1540                 if (flags & KSM_RUN_UNMERGE) {
1541                         err = unmerge_and_remove_all_rmap_items();
1542                         if (err) {
1543                                 ksm_run = KSM_RUN_STOP;
1544                                 count = err;
1545                         }
1546                 }
1547         }
1548         mutex_unlock(&ksm_thread_mutex);
1549
1550         if (flags & KSM_RUN_MERGE)
1551                 wake_up_interruptible(&ksm_thread_wait);
1552
1553         return count;
1554 }
1555 KSM_ATTR(run);
1556
1557 static ssize_t max_kernel_pages_store(struct kobject *kobj,
1558                                       struct kobj_attribute *attr,
1559                                       const char *buf, size_t count)
1560 {
1561         int err;
1562         unsigned long nr_pages;
1563
1564         err = strict_strtoul(buf, 10, &nr_pages);
1565         if (err)
1566                 return -EINVAL;
1567
1568         ksm_max_kernel_pages = nr_pages;
1569
1570         return count;
1571 }
1572
1573 static ssize_t max_kernel_pages_show(struct kobject *kobj,
1574                                      struct kobj_attribute *attr, char *buf)
1575 {
1576         return sprintf(buf, "%lu\n", ksm_max_kernel_pages);
1577 }
1578 KSM_ATTR(max_kernel_pages);
1579
1580 static ssize_t pages_shared_show(struct kobject *kobj,
1581                                  struct kobj_attribute *attr, char *buf)
1582 {
1583         return sprintf(buf, "%lu\n", ksm_pages_shared);
1584 }
1585 KSM_ATTR_RO(pages_shared);
1586
1587 static ssize_t pages_sharing_show(struct kobject *kobj,
1588                                   struct kobj_attribute *attr, char *buf)
1589 {
1590         return sprintf(buf, "%lu\n", ksm_pages_sharing);
1591 }
1592 KSM_ATTR_RO(pages_sharing);
1593
1594 static ssize_t pages_unshared_show(struct kobject *kobj,
1595                                    struct kobj_attribute *attr, char *buf)
1596 {
1597         return sprintf(buf, "%lu\n", ksm_pages_unshared);
1598 }
1599 KSM_ATTR_RO(pages_unshared);
1600
1601 static ssize_t pages_volatile_show(struct kobject *kobj,
1602                                    struct kobj_attribute *attr, char *buf)
1603 {
1604         long ksm_pages_volatile;
1605
1606         ksm_pages_volatile = ksm_rmap_items - ksm_pages_shared
1607                                 - ksm_pages_sharing - ksm_pages_unshared;
1608         /*
1609          * It was not worth any locking to calculate that statistic,
1610          * but it might therefore sometimes be negative: conceal that.
1611          */
1612         if (ksm_pages_volatile < 0)
1613                 ksm_pages_volatile = 0;
1614         return sprintf(buf, "%ld\n", ksm_pages_volatile);
1615 }
1616 KSM_ATTR_RO(pages_volatile);
1617
1618 static ssize_t full_scans_show(struct kobject *kobj,
1619                                struct kobj_attribute *attr, char *buf)
1620 {
1621         return sprintf(buf, "%lu\n", ksm_scan.seqnr);
1622 }
1623 KSM_ATTR_RO(full_scans);
1624
1625 static struct attribute *ksm_attrs[] = {
1626         &sleep_millisecs_attr.attr,
1627         &pages_to_scan_attr.attr,
1628         &run_attr.attr,
1629         &max_kernel_pages_attr.attr,
1630         &pages_shared_attr.attr,
1631         &pages_sharing_attr.attr,
1632         &pages_unshared_attr.attr,
1633         &pages_volatile_attr.attr,
1634         &full_scans_attr.attr,
1635         NULL,
1636 };
1637
1638 static struct attribute_group ksm_attr_group = {
1639         .attrs = ksm_attrs,
1640         .name = "ksm",
1641 };
1642
1643 static int __init ksm_init(void)
1644 {
1645         struct task_struct *ksm_thread;
1646         int err;
1647
1648         err = ksm_slab_init();
1649         if (err)
1650                 goto out;
1651
1652         err = mm_slots_hash_init();
1653         if (err)
1654                 goto out_free1;
1655
1656         ksm_thread = kthread_run(ksm_scan_thread, NULL, "ksmd");
1657         if (IS_ERR(ksm_thread)) {
1658                 printk(KERN_ERR "ksm: creating kthread failed\n");
1659                 err = PTR_ERR(ksm_thread);
1660                 goto out_free2;
1661         }
1662
1663         err = sysfs_create_group(mm_kobj, &ksm_attr_group);
1664         if (err) {
1665                 printk(KERN_ERR "ksm: register sysfs failed\n");
1666                 goto out_free3;
1667         }
1668
1669         return 0;
1670
1671 out_free3:
1672         kthread_stop(ksm_thread);
1673 out_free2:
1674         mm_slots_hash_free();
1675 out_free1:
1676         ksm_slab_free();
1677 out:
1678         return err;
1679 }
1680 module_init(ksm_init)