{"push_id":1115236579,"size":1,"distinct_size":1,"ref":"refs/heads/master","head":"a8242d6bf9d0028c7e1d676d61f05671cc8b1905","before":"7e30893c2f12eb134b67fcf0c48292fffc12b8cf","commits":[{"sha":"a8242d6bf9d0028c7e1d676d61f05671cc8b1905","author":{"email":"5cb699227be62d301a8938d918ca915ca6724ab0@gmail.com","name":"robcore"},"message":"From 6cef6daf1ee182427293fd1e8c53350e1fc377a0 Mon Sep 17 00:00:00 2001\nFrom: Dorimanx <yuri@bynet.co.il>\nDate: Tue, 1 Sep 2015 18:13:56 +0300\nSubject: [PATCH 1809/3429] MM: Merge UKSM 0.1.2.3 from 3.10.y + adapt and fix\n for my tree.\n\n---\n Documentation/vm/00-INDEX     |    2 +\n Documentation/vm/uksm.txt     |   58 +\n fs/exec.c                     |    9 +-\n fs/proc/meminfo.c             |    6 +\n include/asm-generic/pgtable.h |   17 +-\n include/linux/ksm.h           |   44 +-\n include/linux/mm_types.h      |    3 +\n include/linux/mmzone.h        |    5 +-\n include/linux/sradix-tree.h   |   77 +\n include/linux/uksm.h          |  146 ++\n kernel/fork.c                 |    4 +-\n lib/Makefile                  |    2 +-\n lib/sradix-tree.c             |  476 ++++\n mm/Kconfig                    |   26 +\n mm/Makefile                   |    3 +-\n mm/memory.c                   |   45 +-\n mm/mmap.c                     |   49 +-\n mm/rmap.c                     |    4 +-\n mm/uksm.c                     | 5649 +++++++++++++++++++++++++++++++++++++++++\n mm/vmstat.c                   |    3 +\n 20 files changed, 6589 insertions(+), 39 deletions(-)\n create mode 100644 Documentation/vm/uksm.txt\n create mode 100644 include/linux/sradix-tree.h\n create mode 100644 include/linux/uksm.h\n create mode 100644 lib/sradix-tree.c\n create mode 100644 mm/uksm.c\n\ndiff --git a/Documentation/vm/00-INDEX b/Documentation/vm/00-INDEX\nindex 5481c8b..7141876 100644\n--- a/Documentation/vm/00-INDEX\n+++ b/Documentation/vm/00-INDEX\n@@ -14,6 +14,8 @@ hwpoison.txt\n \t- explains what hwpoison is\n ksm.txt\n \t- how to use the Kernel Samepage Merging feature.\n+uksm.txt\n+\t- Introduction to Ultra KSM\n locking\n \t- info on how locking and synchronization is done in the Linux vm code.\n map_hugetlb.c\ndiff --git a/Documentation/vm/uksm.txt b/Documentation/vm/uksm.txt\nnew file mode 100644\nindex 0000000..08bd645\n--- /dev/null\n+++ b/Documentation/vm/uksm.txt\n@@ -0,0 +1,58 @@\n+The Ultra Kernel Samepage Merging feature\n+----------------------------------------------\n+/*\n+ * Ultra KSM. Copyright (C) 2011-2012 Nai Xia\n+ *\n+ * This is an improvement upon KSM. Some basic data structures and routines\n+ * are borrowed from ksm.c .\n+ *\n+ * Its new features:\n+ * 1. Full system scan:\n+ *      It automatically scans all user processes' anonymous VMAs. Kernel-user\n+ *      interaction to submit a memory area to KSM is no longer needed.\n+ *\n+ * 2. Rich area detection:\n+ *      It automatically detects rich areas containing abundant duplicated\n+ *      pages based. Rich areas are given a full scan speed. Poor areas are\n+ *      sampled at a reasonable speed with very low CPU consumption.\n+ *\n+ * 3. Ultra Per-page scan speed improvement:\n+ *      A new hash algorithm is proposed. As a result, on a machine with\n+ *      Core(TM)2 Quad Q9300 CPU in 32-bit mode and 800MHZ DDR2 main memory, it\n+ *      can scan memory areas that does not contain duplicated pages at speed of\n+ *      627MB/sec ~ 2445MB/sec and can merge duplicated areas at speed of\n+ *      477MB/sec ~ 923MB/sec.\n+ *\n+ * 4. Thrashing area avoidance:\n+ *      Thrashing area(an VMA that has frequent Ksm page break-out) can be\n+ *      filtered out. My benchmark shows it's more efficient than KSM's per-page\n+ *      hash value based volatile page detection.\n+ *\n+ *\n+ * 5. Misc changes upon KSM:\n+ *      * It has a fully x86-opitmized memcmp dedicated for 4-byte-aligned page\n+ *        comparison. It's much faster than default C version on x86.\n+ *      * rmap_item now has an struct *page member to loosely cache a\n+ *        address-->page mapping, which reduces too much time-costly\n+ *        follow_page().\n+ *      * The VMA creation/exit procedures are hooked to let the Ultra KSM know.\n+ *      * try_to_merge_two_pages() now can revert a pte if it fails. No break_\n+ *        ksm is needed for this case.\n+ *\n+ * 6. Full Zero Page consideration(contributed by Figo Zhang)\n+ *    Now uksmd consider full zero pages as special pages and merge them to an\n+ *    special unswappable uksm zero page.\n+ */\n+\n+ChangeLog:\n+\n+2012-05-05 The creation of this Doc\n+2012-05-08 UKSM 0.1.1.1 libc crash bug fix, api clean up, doc clean up.\n+2012-05-28 UKSM 0.1.1.2 bug fix release\n+2012-06-26 UKSM 0.1.2-beta1 first beta release for 0.1.2\n+2012-07-2  UKSM 0.1.2-beta2\n+2012-07-10 UKSM 0.1.2-beta3\n+2012-07-26 UKSM 0.1.2 Fine grained speed control, more scan optimization.\n+2012-10-13 UKSM 0.1.2.1 Bug fixes.\n+2012-12-31 UKSM 0.1.2.2 Minor bug fixes\n+2014-07-02 UKSM 0.1.2.3 Fix a \" __this_cpu_read() in preemptible bug\"\ndiff --git a/fs/exec.c b/fs/exec.c\nindex 0289864..4e0eddc 100644\n--- a/fs/exec.c\n+++ b/fs/exec.c\n@@ -19,7 +19,7 @@\n  * current->executable is only used by the procfs.  This allows a dispatch\n  * table to check for several different types  of binary formats.  We keep\n  * trying until we recognize the file or we run out of supported binary\n- * formats.\n+ * formats.\n  */\n\n #include <linux/slab.h>\n@@ -55,6 +55,7 @@\n #include <linux/pipe_fs_i.h>\n #include <linux/oom.h>\n #include <linux/compat.h>\n+#include <linux/ksm.h>\n\n #include <asm/uaccess.h>\n #include <asm/mmu_context.h>\n@@ -1173,7 +1174,7 @@ void setup_new_exec(struct linux_binprm * bprm)\n \t   group */\n\n \tcurrent->self_exec_id++;\n-\n+\n \tflush_signal_handlers(current, 0);\n \tdo_close_on_exec(current->files);\n }\n@@ -1338,8 +1339,8 @@ static int check_unsafe_exec(struct linux_binprm *bprm)\n \treturn res;\n }\n\n-/*\n- * Fill the binprm structure from the inode.\n+/*\n+ * Fill the binprm structure from the inode.\n  * Check permissions, then read the first 128 (BINPRM_BUF_SIZE) bytes\n  *\n  * This may be called multiple times for binary chains (scripts for example).\ndiff --git a/fs/proc/meminfo.c b/fs/proc/meminfo.c\nindex 5aa847a..c6c5553 100644\n--- a/fs/proc/meminfo.c\n+++ b/fs/proc/meminfo.c\n@@ -88,6 +88,9 @@ static int meminfo_proc_show(struct seq_file *m, void *v)\n \t\t\"SUnreclaim:     %8lu kB\\n\"\n \t\t\"KernelStack:    %8lu kB\\n\"\n \t\t\"PageTables:     %8lu kB\\n\"\n+#ifdef CONFIG_UKSM\n+\t\t\"KsmZeroPages:   %8lu kB\\n\"\n+#endif\n #ifdef CONFIG_QUICKLIST\n \t\t\"Quicklists:     %8lu kB\\n\"\n #endif\n@@ -147,6 +150,9 @@ static int meminfo_proc_show(struct seq_file *m, void *v)\n \t\tK(global_page_state(NR_SLAB_UNRECLAIMABLE)),\n \t\tglobal_page_state(NR_KERNEL_STACK) * THREAD_SIZE / 1024,\n \t\tK(global_page_state(NR_PAGETABLE)),\n+#ifdef CONFIG_UKSM\n+\t\tK(global_page_state(NR_UKSM_ZERO_PAGES)),\n+#endif\n #ifdef CONFIG_QUICKLIST\n \t\tK(quicklist_total_size()),\n #endif\ndiff --git a/include/asm-generic/pgtable.h b/include/asm-generic/pgtable.h\nindex 2e0ef04..29da4bf 100644\n--- a/include/asm-generic/pgtable.h\n+++ b/include/asm-generic/pgtable.h\n@@ -453,12 +453,25 @@ extern void untrack_pfn(struct vm_area_struct *vma, unsigned long pfn,\n \t\t\tunsigned long size);\n #endif\n\n+#ifdef CONFIG_UKSM\n+static inline int is_uksm_zero_pfn(unsigned long pfn)\n+{\n+\textern unsigned long uksm_zero_pfn;\n+        return pfn == uksm_zero_pfn;\n+}\n+#else\n+static inline int is_uksm_zero_pfn(unsigned long pfn)\n+{\n+        return 0;\n+}\n+#endif\n+\n #ifdef __HAVE_COLOR_ZERO_PAGE\n static inline int is_zero_pfn(unsigned long pfn)\n {\n \textern unsigned long zero_pfn;\n \tunsigned long offset_from_zero_pfn = pfn - zero_pfn;\n-\treturn offset_from_zero_pfn <= (zero_page_mask >> PAGE_SHIFT);\n+\treturn offset_from_zero_pfn <= (zero_page_mask >> PAGE_SHIFT) || is_uksm_zero_pfn(pfn);\n }\n\n #define my_zero_pfn(addr)\tpage_to_pfn(ZERO_PAGE(addr))\n@@ -467,7 +480,7 @@ static inline int is_zero_pfn(unsigned long pfn)\n static inline int is_zero_pfn(unsigned long pfn)\n {\n \textern unsigned long zero_pfn;\n-\treturn pfn == zero_pfn;\n+\treturn (pfn == zero_pfn) || (is_uksm_zero_pfn(pfn));\n }\n\n static inline unsigned long my_zero_pfn(unsigned long addr)\ndiff --git a/include/linux/ksm.h b/include/linux/ksm.h\nindex d8e556b..c7102b4 100644\n--- a/include/linux/ksm.h\n+++ b/include/linux/ksm.h\n@@ -19,21 +19,6 @@ struct mem_cgroup;\n #ifdef CONFIG_KSM\n int ksm_madvise(struct vm_area_struct *vma, unsigned long start,\n \t\tunsigned long end, int advice, unsigned long *vm_flags);\n-int __ksm_enter(struct mm_struct *mm);\n-void __ksm_exit(struct mm_struct *mm);\n-\n-static inline int ksm_fork(struct mm_struct *mm, struct mm_struct *oldmm)\n-{\n-\tif (test_bit(MMF_VM_MERGEABLE, &oldmm->flags))\n-\t\treturn __ksm_enter(mm);\n-\treturn 0;\n-}\n-\n-static inline void ksm_exit(struct mm_struct *mm)\n-{\n-\tif (test_bit(MMF_VM_MERGEABLE, &mm->flags))\n-\t\t__ksm_exit(mm);\n-}\n\n /*\n  * A KSM page is one of those write-protected \"shared pages\" or \"merged pages\"\n@@ -81,6 +66,33 @@ int rmap_walk_ksm(struct page *page, int (*rmap_one)(struct page *,\n \t\t  struct vm_area_struct *, unsigned long, void *), void *arg);\n void ksm_migrate_page(struct page *newpage, struct page *oldpage);\n\n+#ifdef CONFIG_KSM_LEGACY\n+int __ksm_enter(struct mm_struct *mm);\n+void __ksm_exit(struct mm_struct *mm);\n+static inline int ksm_fork(struct mm_struct *mm, struct mm_struct *oldmm)\n+{\n+\tif (test_bit(MMF_VM_MERGEABLE, &oldmm->flags))\n+\t\treturn __ksm_enter(mm);\n+\treturn 0;\n+}\n+\n+static inline void ksm_exit(struct mm_struct *mm)\n+{\n+\tif (test_bit(MMF_VM_MERGEABLE, &mm->flags))\n+\t\t__ksm_exit(mm);\n+}\n+\n+#elif defined(CONFIG_UKSM)\n+static inline int ksm_fork(struct mm_struct *mm, struct mm_struct *oldmm)\n+{\n+\treturn 0;\n+}\n+\n+static inline void ksm_exit(struct mm_struct *mm)\n+{\n+}\n+#endif /* !CONFIG_UKSM */\n+\n #else  /* !CONFIG_KSM */\n\n static inline int ksm_fork(struct mm_struct *mm, struct mm_struct *oldmm)\n@@ -134,4 +146,6 @@ static inline void ksm_migrate_page(struct page *newpage, struct page *oldpage)\n #endif /* CONFIG_MMU */\n #endif /* !CONFIG_KSM */\n\n+#include <linux/uksm.h>\n+\n #endif /* __LINUX_KSM_H */\ndiff --git a/include/linux/mm_types.h b/include/linux/mm_types.h\nindex 4c827d3..7683937 100644\n--- a/include/linux/mm_types.h\n+++ b/include/linux/mm_types.h\n@@ -300,6 +300,9 @@ struct vm_area_struct {\n #ifdef CONFIG_NUMA\n \tstruct mempolicy *vm_policy;\t/* NUMA policy for the VMA */\n #endif\n+#ifdef CONFIG_UKSM\n+\tstruct vma_slot *uksm_vma_slot;\n+#endif\n };\n\n struct core_thread {\ndiff --git a/include/linux/mmzone.h b/include/linux/mmzone.h\nindex 3ae0ba1..47d039a 100644\n--- a/include/linux/mmzone.h\n+++ b/include/linux/mmzone.h\n@@ -153,6 +153,9 @@ enum zone_stat_item {\n #endif\n \tNR_ANON_TRANSPARENT_HUGEPAGES,\n \tNR_FREE_CMA_PAGES,\n+#ifdef CONFIG_UKSM\n+\tNR_UKSM_ZERO_PAGES,\n+#endif\n \tNR_VM_ZONE_STAT_ITEMS };\n\n /*\n@@ -894,7 +897,7 @@ static inline int is_normal_idx(enum zone_type idx)\n }\n\n /**\n- * is_highmem - helper function to quickly check if a struct zone is a\n+ * is_highmem - helper function to quickly check if a struct zone is a\n  *              highmem zone or not.  This is an attempt to keep references\n  *              to ZONE_{DMA/NORMAL/HIGHMEM/etc} in general code to a minimum.\n  * @zone - pointer to struct zone variable\ndiff --git a/include/linux/sradix-tree.h b/include/linux/sradix-tree.h\nnew file mode 100644\nindex 0000000..6780fdb\n--- /dev/null\n+++ b/include/linux/sradix-tree.h\n@@ -0,0 +1,77 @@\n+#ifndef _LINUX_SRADIX_TREE_H\n+#define _LINUX_SRADIX_TREE_H\n+\n+\n+#define INIT_SRADIX_TREE(root, mask)\t\t\t\t\t\\\n+do {\t\t\t\t\t\t\t\t\t\\\n+\t(root)->height = 0;\t\t\t\t\t\t\\\n+\t(root)->gfp_mask = (mask);\t\t\t\t\t\\\n+\t(root)->rnode = NULL;\t\t\t\t\t\t\\\n+} while (0)\n+\n+#define ULONG_BITS\t(sizeof(unsigned long) * 8)\n+#define SRADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))\n+//#define SRADIX_TREE_MAP_SHIFT\t6\n+//#define SRADIX_TREE_MAP_SIZE\t(1UL << SRADIX_TREE_MAP_SHIFT)\n+//#define SRADIX_TREE_MAP_MASK\t(SRADIX_TREE_MAP_SIZE-1)\n+\n+struct sradix_tree_node {\n+\tunsigned int\theight;\t\t/* Height from the bottom */\n+\tunsigned int\tcount;\n+\tunsigned int\tfulls;\t\t/* Number of full sublevel trees */\n+\tstruct sradix_tree_node *parent;\n+\tvoid *stores[0];\n+};\n+\n+/* A simple radix tree implementation */\n+struct sradix_tree_root {\n+        unsigned int            height;\n+        struct sradix_tree_node *rnode;\n+\n+\t/* Where found to have available empty stores in its sublevels */\n+        struct sradix_tree_node *enter_node;\n+\tunsigned int shift;\n+\tunsigned int stores_size;\n+\tunsigned int mask;\n+\tunsigned long min;\t/* The first hole index */\n+\tunsigned long num;\n+\t//unsigned long *height_to_maxindex;\n+\n+\t/* How the node is allocated and freed. */\n+\tstruct sradix_tree_node *(*alloc)(void);\n+\tvoid (*free)(struct sradix_tree_node *node);\n+\n+\t/* When a new node is added and removed */\n+\tvoid (*extend)(struct sradix_tree_node *parent, struct sradix_tree_node *child);\n+\tvoid (*assign)(struct sradix_tree_node *node, unsigned index, void *item);\n+\tvoid (*rm)(struct sradix_tree_node *node, unsigned offset);\n+};\n+\n+struct sradix_tree_path {\n+\tstruct sradix_tree_node *node;\n+\tint offset;\n+};\n+\n+static inline\n+void init_sradix_tree_root(struct sradix_tree_root *root, unsigned long shift)\n+{\n+\troot->height = 0;\n+\troot->rnode = NULL;\n+\troot->shift = shift;\n+\troot->stores_size = 1UL << shift;\n+\troot->mask = root->stores_size - 1;\n+}\n+\n+\n+extern void *sradix_tree_next(struct sradix_tree_root *root,\n+\t\t       struct sradix_tree_node *node, unsigned long index,\n+\t\t       int (*iter)(void *, unsigned long));\n+\n+extern int sradix_tree_enter(struct sradix_tree_root *root, void **item, int num);\n+\n+extern void sradix_tree_delete_from_leaf(struct sradix_tree_root *root,\n+\t\t\tstruct sradix_tree_node *node, unsigned long index);\n+\n+extern void *sradix_tree_lookup(struct sradix_tree_root *root, unsigned long index);\n+\n+#endif /* _LINUX_SRADIX_TREE_H */\ndiff --git a/include/linux/uksm.h b/include/linux/uksm.h\nnew file mode 100644\nindex 0000000..a644bca\n--- /dev/null\n+++ b/include/linux/uksm.h\n@@ -0,0 +1,146 @@\n+#ifndef __LINUX_UKSM_H\n+#define __LINUX_UKSM_H\n+/*\n+ * Memory merging support.\n+ *\n+ * This code enables dynamic sharing of identical pages found in different\n+ * memory areas, even if they are not shared by fork().\n+ */\n+\n+/* if !CONFIG_UKSM this file should not be compiled at all. */\n+#ifdef CONFIG_UKSM\n+\n+#include <linux/bitops.h>\n+#include <linux/mm.h>\n+#include <linux/pagemap.h>\n+#include <linux/rmap.h>\n+#include <linux/sched.h>\n+\n+extern unsigned long zero_pfn __read_mostly;\n+extern unsigned long uksm_zero_pfn __read_mostly;\n+extern struct page *empty_uksm_zero_page;\n+\n+/* must be done before linked to mm */\n+extern void uksm_vma_add_new(struct vm_area_struct *vma);\n+extern void uksm_remove_vma(struct vm_area_struct *vma);\n+\n+#define UKSM_SLOT_NEED_SORT\t(1 << 0)\n+#define UKSM_SLOT_NEED_RERAND \t(1 << 1)\n+#define UKSM_SLOT_SCANNED     \t(1 << 2) /* It's scanned in this round */\n+#define UKSM_SLOT_FUL_SCANNED \t(1 << 3)\n+#define UKSM_SLOT_IN_UKSM \t(1 << 4)\n+\n+struct vma_slot {\n+\tstruct sradix_tree_node *snode;\n+\tunsigned long sindex;\n+\n+\tstruct list_head slot_list;\n+\tunsigned long fully_scanned_round;\n+\tunsigned long dedup_num;\n+\tunsigned long pages_scanned;\n+\tunsigned long last_scanned;\n+\tunsigned long pages_to_scan;\n+\tstruct scan_rung *rung;\n+\tstruct page **rmap_list_pool;\n+\tunsigned int *pool_counts;\n+\tunsigned long pool_size;\n+\tstruct vm_area_struct *vma;\n+\tstruct mm_struct *mm;\n+\tunsigned long ctime_j;\n+\tunsigned long pages;\n+\tunsigned long flags;\n+\tunsigned long pages_cowed; /* pages cowed this round */\n+\tunsigned long pages_merged; /* pages merged this round */\n+\tunsigned long pages_bemerged;\n+\n+\t/* when it has page merged in this eval round */\n+\tstruct list_head dedup_list;\n+};\n+\n+static inline void uksm_unmap_zero_page(pte_t pte)\n+{\n+\tif (pte_pfn(pte) == uksm_zero_pfn)\n+\t\t__dec_zone_page_state(empty_uksm_zero_page, NR_UKSM_ZERO_PAGES);\n+}\n+\n+static inline void uksm_map_zero_page(pte_t pte)\n+{\n+\tif (pte_pfn(pte) == uksm_zero_pfn)\n+\t\t__inc_zone_page_state(empty_uksm_zero_page, NR_UKSM_ZERO_PAGES);\n+}\n+\n+static inline void uksm_cow_page(struct vm_area_struct *vma, struct page *page)\n+{\n+\tif (vma->uksm_vma_slot && PageKsm(page))\n+\t\tvma->uksm_vma_slot->pages_cowed++;\n+}\n+\n+static inline void uksm_cow_pte(struct vm_area_struct *vma, pte_t pte)\n+{\n+\tif (vma->uksm_vma_slot && pte_pfn(pte) == uksm_zero_pfn)\n+\t\tvma->uksm_vma_slot->pages_cowed++;\n+}\n+\n+static inline int uksm_flags_can_scan(unsigned long vm_flags)\n+{\n+#ifndef VM_SAO\n+#define VM_SAO 0\n+#endif\n+\treturn !(vm_flags & (VM_PFNMAP | VM_IO  | VM_DONTEXPAND |\n+\t\t\t     VM_HUGETLB | VM_NONLINEAR | VM_MIXEDMAP |\n+\t\t\t     VM_SHARED  | VM_MAYSHARE | VM_GROWSUP | VM_GROWSDOWN | VM_SAO));\n+}\n+\n+static inline void uksm_vm_flags_mod(unsigned long *vm_flags_p)\n+{\n+\tif (uksm_flags_can_scan(*vm_flags_p))\n+\t\t*vm_flags_p |= VM_MERGEABLE;\n+}\n+\n+/*\n+ * Just a wrapper for BUG_ON for where ksm_zeropage must not be. TODO: it will\n+ * be removed when uksm zero page patch is stable enough.\n+ */\n+static inline void uksm_bugon_zeropage(pte_t pte)\n+{\n+\tBUG_ON(pte_pfn(pte) == uksm_zero_pfn);\n+}\n+#else\n+static inline void uksm_vma_add_new(struct vm_area_struct *vma)\n+{\n+}\n+\n+static inline void uksm_remove_vma(struct vm_area_struct *vma)\n+{\n+}\n+\n+static inline void uksm_unmap_zero_page(pte_t pte)\n+{\n+}\n+\n+static inline void uksm_map_zero_page(pte_t pte)\n+{\n+}\n+\n+static inline void uksm_cow_page(struct vm_area_struct *vma, struct page *page)\n+{\n+}\n+\n+static inline void uksm_cow_pte(struct vm_area_struct *vma, pte_t pte)\n+{\n+}\n+\n+static inline int uksm_flags_can_scan(unsigned long vm_flags)\n+{\n+\treturn 0;\n+}\n+\n+static inline void uksm_vm_flags_mod(unsigned long *vm_flags_p)\n+{\n+}\n+\n+static inline void uksm_bugon_zeropage(pte_t pte)\n+{\n+}\n+#endif /* !CONFIG_UKSM */\n+#endif /* __LINUX_UKSM_H */\ndiff --git a/kernel/fork.c b/kernel/fork.c\nindex 04464f9..a028c76 100644\n--- a/kernel/fork.c\n+++ b/kernel/fork.c\n@@ -390,7 +390,7 @@ static int dup_mmap(struct mm_struct *mm, struct mm_struct *oldmm)\n \t\t\t\tgoto fail_nomem;\n \t\t\tcharge = len;\n \t\t}\n-\t\ttmp = kmem_cache_alloc(vm_area_cachep, GFP_KERNEL);\n+\t\ttmp = kmem_cache_zalloc(vm_area_cachep, GFP_KERNEL);\n \t\tif (!tmp)\n \t\t\tgoto fail_nomem;\n \t\t*tmp = *mpnt;\n@@ -447,7 +447,7 @@ static int dup_mmap(struct mm_struct *mm, struct mm_struct *oldmm)\n \t\t__vma_link_rb(mm, tmp, rb_link, rb_parent);\n \t\trb_link = &tmp->vm_rb.rb_right;\n \t\trb_parent = &tmp->vm_rb;\n-\n+\t\tuksm_vma_add_new(tmp);\n \t\tmm->map_count++;\n \t\tretval = copy_page_range(mm, oldmm, mpnt);\n\ndiff --git a/lib/Makefile b/lib/Makefile\nindex 5314888..bccd82f 100644\n--- a/lib/Makefile\n+++ b/lib/Makefile\n@@ -8,7 +8,7 @@ KBUILD_CFLAGS = $(subst -pg,,$(ORIG_CFLAGS))\n endif\n\n lib-y := ctype.o string.o vsprintf.o cmdline.o \\\n-\t rbtree.o radix-tree.o dump_stack.o timerqueue.o\\\n+\t rbtree.o radix-tree.o sradix-tree.o dump_stack.o timerqueue.o\\\n \t idr.o int_sqrt.o extable.o prio_tree.o \\\n \t sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \\\n \t proportions.o flex_proportions.o prio_heap.o ratelimit.o show_mem.o \\\ndiff --git a/lib/sradix-tree.c b/lib/sradix-tree.c\nnew file mode 100644\nindex 0000000..8d06329\n--- /dev/null\n+++ b/lib/sradix-tree.c\n@@ -0,0 +1,476 @@\n+#include <linux/errno.h>\n+#include <linux/mm.h>\n+#include <linux/mman.h>\n+#include <linux/spinlock.h>\n+#include <linux/slab.h>\n+#include <linux/gcd.h>\n+#include <linux/sradix-tree.h>\n+\n+static inline int sradix_node_full(struct sradix_tree_root *root, struct sradix_tree_node *node)\n+{\n+\treturn node->fulls == root->stores_size ||\n+\t\t(node->height == 1 && node->count == root->stores_size);\n+}\n+\n+/*\n+ *\tExtend a sradix tree so it can store key @index.\n+ */\n+static int sradix_tree_extend(struct sradix_tree_root *root, unsigned long index)\n+{\n+\tstruct sradix_tree_node *node;\n+\tunsigned int height;\n+\n+\tif (unlikely(root->rnode == NULL)) {\n+\t\tif (!(node = root->alloc()))\n+\t\t\treturn -ENOMEM;\n+\n+\t\tnode->height = 1;\n+\t\troot->rnode = node;\n+\t\troot->height = 1;\n+\t}\n+\n+\t/* Figure out what the height should be.  */\n+\theight = root->height;\n+\tindex >>= root->shift * height;\n+\n+\twhile (index) {\n+\t\tindex >>= root->shift;\n+\t\theight++;\n+\t}\n+\n+\twhile (height > root->height) {\n+\t\tunsigned int newheight;\n+\t\tif (!(node = root->alloc()))\n+\t\t\treturn -ENOMEM;\n+\n+\t\t/* Increase the height.  */\n+\t\tnode->stores[0] = root->rnode;\n+\t\troot->rnode->parent = node;\n+\t\tif (root->extend)\n+\t\t\troot->extend(node, root->rnode);\n+\n+\t\tnewheight = root->height + 1;\n+\t\tnode->height = newheight;\n+\t\tnode->count = 1;\n+\t\tif (sradix_node_full(root, root->rnode))\n+\t\t\tnode->fulls = 1;\n+\n+\t\troot->rnode = node;\n+\t\troot->height = newheight;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+/*\n+ * Search the next item from the current node, that is not NULL\n+ * and can satify root->iter().\n+ */\n+void *sradix_tree_next(struct sradix_tree_root *root,\n+\t\t       struct sradix_tree_node *node, unsigned long index,\n+\t\t       int (*iter)(void *item, unsigned long height))\n+{\n+\tunsigned long offset;\n+\tvoid *item;\n+\n+\tif (unlikely(node == NULL)) {\n+\t\tnode = root->rnode;\n+\t\tfor (offset = 0; offset < root->stores_size; offset++) {\n+\t\t\titem = node->stores[offset];\n+\t\t\tif (item && (!iter || iter(item, node->height)))\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\tif (unlikely(offset >= root->stores_size))\n+\t\t\treturn NULL;\n+\n+\t\tif (node->height == 1)\n+\t\t\treturn item;\n+\t\telse\n+\t\t\tgoto go_down;\n+\t}\n+\n+\twhile (node) {\n+\t\toffset = (index & root->mask) + 1;\n+\t\tfor (;offset < root->stores_size; offset++) {\n+\t\t\titem = node->stores[offset];\n+\t\t\tif (item && (!iter || iter(item, node->height)))\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\tif (offset < root->stores_size)\n+\t\t\tbreak;\n+\n+\t\tnode = node->parent;\n+\t\tindex >>= root->shift;\n+\t}\n+\n+\tif (!node)\n+\t\treturn NULL;\n+\n+\twhile (node->height > 1) {\n+go_down:\n+\t\tnode = item;\n+\t\tfor (offset = 0; offset < root->stores_size; offset++) {\n+\t\t\titem = node->stores[offset];\n+\t\t\tif (item && (!iter || iter(item, node->height)))\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\tif (unlikely(offset >= root->stores_size))\n+\t\t\treturn NULL;\n+\t}\n+\n+\tBUG_ON(offset > root->stores_size);\n+\n+\treturn item;\n+}\n+\n+/*\n+ * Blindly insert the item to the tree. Typically, we reuse the\n+ * first empty store item.\n+ */\n+int sradix_tree_enter(struct sradix_tree_root *root, void **item, int num)\n+{\n+\tunsigned long index;\n+\tunsigned int height;\n+\tstruct sradix_tree_node *node, *tmp = NULL;\n+\tint offset, offset_saved;\n+\tvoid **store = NULL;\n+\tint error, i, j, shift;\n+\n+go_on:\n+\tindex = root->min;\n+\n+\tif (root->enter_node && !sradix_node_full(root, root->enter_node)) {\n+\t\tnode = root->enter_node;\n+\t\tBUG_ON((index >> (root->shift * root->height)));\n+\t} else {\n+\t\tnode = root->rnode;\n+\t\tif (node == NULL || (index >> (root->shift * root->height))\n+\t\t    || sradix_node_full(root, node)) {\n+\t\t\terror = sradix_tree_extend(root, index);\n+\t\t\tif (error)\n+\t\t\t\treturn error;\n+\n+\t\t\tnode = root->rnode;\n+\t\t}\n+\t}\n+\n+\n+\theight = node->height;\n+\tshift = (height - 1) * root->shift;\n+\toffset = (index >> shift) & root->mask;\n+\twhile (shift > 0) {\n+\t\toffset_saved = offset;\n+\t\tfor (; offset < root->stores_size; offset++) {\n+\t\t\tstore = &node->stores[offset];\n+\t\t\ttmp = *store;\n+\n+\t\t\tif (!tmp || !sradix_node_full(root, tmp))\n+\t\t\t\tbreak;\n+\t\t}\n+\t\tBUG_ON(offset >= root->stores_size);\n+\n+\t\tif (offset != offset_saved) {\n+\t\t\tindex += (offset - offset_saved) << shift;\n+\t\t\tindex &= ~((1UL << shift) - 1);\n+\t\t}\n+\n+\t\tif (!tmp) {\n+\t\t\tif (!(tmp = root->alloc()))\n+\t\t\t\treturn -ENOMEM;\n+\n+\t\t\ttmp->height = shift / root->shift;\n+\t\t\t*store = tmp;\n+\t\t\ttmp->parent = node;\n+\t\t\tnode->count++;\n+//\t\t\tif (root->extend)\n+//\t\t\t\troot->extend(node, tmp);\n+\t\t}\n+\n+\t\tnode = tmp;\n+\t\tshift -= root->shift;\n+\t\toffset = (index >> shift) & root->mask;\n+\t}\n+\n+\tBUG_ON(node->height != 1);\n+\n+\n+\tstore = &node->stores[offset];\n+\tfor (i = 0, j = 0;\n+\t      j < root->stores_size - node->count &&\n+\t      i < root->stores_size - offset && j < num; i++) {\n+\t\tif (!store[i]) {\n+\t\t\tstore[i] = item[j];\n+\t\t\tif (root->assign)\n+\t\t\t\troot->assign(node, index + i, item[j]);\n+\t\t\tj++;\n+\t\t}\n+\t}\n+\n+\tnode->count += j;\n+\troot->num += j;\n+\tnum -= j;\n+\n+\twhile (sradix_node_full(root, node)) {\n+\t\tnode = node->parent;\n+\t\tif (!node)\n+\t\t\tbreak;\n+\n+\t\tnode->fulls++;\n+\t}\n+\n+\tif (unlikely(!node)) {\n+\t\t/* All nodes are full */\n+\t\troot->min = 1 << (root->height * root->shift);\n+\t\troot->enter_node = NULL;\n+\t} else {\n+\t\troot->min = index + i - 1;\n+\t\troot->min |= (1UL << (node->height - 1)) - 1;\n+\t\troot->min++;\n+\t\troot->enter_node = node;\n+\t}\n+\n+\tif (num) {\n+\t\titem += j;\n+\t\tgoto go_on;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+\n+/**\n+ *\tsradix_tree_shrink    -    shrink height of a sradix tree to minimal\n+ *      @root\t\tsradix tree root\n+ *\n+ */\n+static inline void sradix_tree_shrink(struct sradix_tree_root *root)\n+{\n+\t/* try to shrink tree height */\n+\twhile (root->height > 1) {\n+\t\tstruct sradix_tree_node *to_free = root->rnode;\n+\n+\t\t/*\n+\t\t * The candidate node has more than one child, or its child\n+\t\t * is not at the leftmost store, we cannot shrink.\n+\t\t */\n+\t\tif (to_free->count != 1 || !to_free->stores[0])\n+\t\t\tbreak;\n+\n+\t\troot->rnode = to_free->stores[0];\n+\t\troot->rnode->parent = NULL;\n+\t\troot->height--;\n+\t\tif (unlikely(root->enter_node == to_free)) {\n+\t\t\troot->enter_node = NULL;\n+\t\t}\n+\t\troot->free(to_free);\n+\t}\n+}\n+\n+/*\n+ * Del the item on the known leaf node and index\n+ */\n+void sradix_tree_delete_from_leaf(struct sradix_tree_root *root,\n+\t\t\t\t  struct sradix_tree_node *node, unsigned long index)\n+{\n+\tunsigned int offset;\n+\tstruct sradix_tree_node *start, *end;\n+\n+\tBUG_ON(node->height != 1);\n+\n+\tstart = node;\n+\twhile (node && !(--node->count))\n+\t\tnode = node->parent;\n+\n+\tend = node;\n+\tif (!node) {\n+\t\troot->rnode = NULL;\n+\t\troot->height = 0;\n+\t\troot->min = 0;\n+\t\troot->num = 0;\n+\t\troot->enter_node = NULL;\n+\t} else {\n+\t\toffset = (index >> (root->shift * (node->height - 1))) & root->mask;\n+\t\tif (root->rm)\n+\t\t\troot->rm(node, offset);\n+\t\tnode->stores[offset] = NULL;\n+\t\troot->num--;\n+\t\tif (root->min > index) {\n+\t\t\troot->min = index;\n+\t\t\troot->enter_node = node;\n+\t\t}\n+\t}\n+\n+\tif (start != end) {\n+\t\tdo {\n+\t\t\tnode = start;\n+\t\t\tstart = start->parent;\n+\t\t\tif (unlikely(root->enter_node == node))\n+\t\t\t\troot->enter_node = end;\n+\t\t\troot->free(node);\n+\t\t} while (start != end);\n+\n+\t\t/*\n+\t\t * Note that shrink may free \"end\", so enter_node still need to\n+\t\t * be checked inside.\n+\t\t */\n+\t\tsradix_tree_shrink(root);\n+\t} else if (node->count == root->stores_size - 1) {\n+\t\t/* It WAS a full leaf node. Update the ancestors */\n+\t\tnode = node->parent;\n+\t\twhile (node) {\n+\t\t\tnode->fulls--;\n+\t\t\tif (node->fulls != root->stores_size - 1)\n+\t\t\t\tbreak;\n+\n+\t\t\tnode = node->parent;\n+\t\t}\n+\t}\n+}\n+\n+void *sradix_tree_lookup(struct sradix_tree_root *root, unsigned long index)\n+{\n+\tunsigned int height, offset;\n+\tstruct sradix_tree_node *node;\n+\tint shift;\n+\n+\tnode = root->rnode;\n+\tif (node == NULL || (index >> (root->shift * root->height)))\n+\t\treturn NULL;\n+\n+\theight = root->height;\n+\tshift = (height - 1) * root->shift;\n+\n+\tdo {\n+\t\toffset = (index >> shift) & root->mask;\n+\t\tnode = node->stores[offset];\n+\t\tif (!node)\n+\t\t\treturn NULL;\n+\n+\t\tshift -= root->shift;\n+\t} while (shift >= 0);\n+\n+\treturn node;\n+}\n+\n+/*\n+ * Return the item if it exists, otherwise create it in place\n+ * and return the created item.\n+ */\n+void *sradix_tree_lookup_create(struct sradix_tree_root *root,\n+\t\t\tunsigned long index, void *(*item_alloc)(void))\n+{\n+\tunsigned int height, offset;\n+\tstruct sradix_tree_node *node, *tmp;\n+\tvoid *item;\n+\tint shift, error;\n+\n+\tif (root->rnode == NULL || (index >> (root->shift * root->height))) {\n+\t\tif (item_alloc) {\n+\t\t\terror = sradix_tree_extend(root, index);\n+\t\t\tif (error)\n+\t\t\t\treturn NULL;\n+\t\t} else {\n+\t\t\treturn NULL;\n+\t\t}\n+\t}\n+\n+\tnode = root->rnode;\n+\theight = root->height;\n+\tshift = (height - 1) * root->shift;\n+\n+\tdo {\n+\t\toffset = (index >> shift) & root->mask;\n+\t\tif (!node->stores[offset]) {\n+\t\t\tif (!(tmp = root->alloc()))\n+\t\t\t\treturn NULL;\n+\n+\t\t\ttmp->height = shift / root->shift;\n+\t\t\tnode->stores[offset] = tmp;\n+\t\t\ttmp->parent = node;\n+\t\t\tnode->count++;\n+\t\t\tnode = tmp;\n+\t\t} else {\n+\t\t\tnode = node->stores[offset];\n+\t\t}\n+\n+\t\tshift -= root->shift;\n+\t} while (shift > 0);\n+\n+\tBUG_ON(node->height != 1);\n+\toffset = index & root->mask;\n+\tif (node->stores[offset]) {\n+\t\treturn node->stores[offset];\n+\t} else if (item_alloc) {\n+\t\tif (!(item = item_alloc()))\n+\t\t\treturn NULL;\n+\n+\t\tnode->stores[offset] = item;\n+\n+\t\t/*\n+\t\t * NOTE: we do NOT call root->assign here, since this item is\n+\t\t * newly created by us having no meaning. Caller can call this\n+\t\t * if it's necessary to do so.\n+\t\t */\n+\n+\t\tnode->count++;\n+\t\troot->num++;\n+\n+\t\twhile (sradix_node_full(root, node)) {\n+\t\t\tnode = node->parent;\n+\t\t\tif (!node)\n+\t\t\t\tbreak;\n+\n+\t\t\tnode->fulls++;\n+\t\t}\n+\n+\t\tif (unlikely(!node)) {\n+\t\t\t/* All nodes are full */\n+\t\t\troot->min = 1 << (root->height * root->shift);\n+\t\t} else {\n+\t\t\tif (root->min == index) {\n+\t\t\t\troot->min |= (1UL << (node->height - 1)) - 1;\n+\t\t\t\troot->min++;\n+\t\t\t\troot->enter_node = node;\n+\t\t\t}\n+\t\t}\n+\n+\t\treturn item;\n+\t} else {\n+\t\treturn NULL;\n+\t}\n+\n+}\n+\n+int sradix_tree_delete(struct sradix_tree_root *root, unsigned long index)\n+{\n+\tunsigned int height, offset;\n+\tstruct sradix_tree_node *node;\n+\tint shift;\n+\n+\tnode = root->rnode;\n+\tif (node == NULL || (index >> (root->shift * root->height)))\n+\t\treturn -ENOENT;\n+\n+\theight = root->height;\n+\tshift = (height - 1) * root->shift;\n+\n+\tdo {\n+\t\toffset = (index >> shift) & root->mask;\n+\t\tnode = node->stores[offset];\n+\t\tif (!node)\n+\t\t\treturn -ENOENT;\n+\n+\t\tshift -= root->shift;\n+\t} while (shift > 0);\n+\n+\toffset = index & root->mask;\n+\tif (!node->stores[offset])\n+\t\treturn -ENOENT;\n+\n+\tsradix_tree_delete_from_leaf(root, node, index);\n+\n+\treturn 0;\n+}\ndiff --git a/mm/Kconfig b/mm/Kconfig\nindex cdcedb7..02f8a77 100644\n--- a/mm/Kconfig\n+++ b/mm/Kconfig\n@@ -302,6 +302,32 @@ config KSM\n \t  See Documentation/vm/ksm.txt for more information: KSM is inactive\n \t  until a program has madvised that an area is MADV_MERGEABLE, and\n \t  root has set /sys/kernel/mm/ksm/run to 1 (if CONFIG_SYSFS is set).\n+choice\n+\tprompt \"Choose UKSM/KSM strategy\"\n+\tdefault UKSM\n+\tdepends on KSM\n+\thelp\n+\t  This option allows to select a UKSM/KSM stragety.\n+\n+config UKSM\n+\tbool \"Ultra-KSM for page merging\"\n+\tdepends on KSM\n+\thelp\n+\tUKSM is inspired by the Linux kernel project \\u2014 KSM(Kernel Same\n+\tpage Merging), but with a fundamentally rewritten core algorithm. With\n+\tan advanced algorithm, UKSM now can transparently scans all anonymously\n+\tmapped user space applications with an significantly improved scan speed\n+\tand CPU efficiency. Since KVM is friendly to KSM, KVM can also benefit from\n+\tUKSM. Now UKSM has its first stable release and first real world enterprise user.\n+\tFor more information, please goto its project page.\n+\t(www.kerneldedup.org)\n+\n+config KSM_LEGACY\n+\tbool \"Legacy KSM implementation\"\n+\tdepends on KSM\n+\thelp\n+\tThe legacy KSM implementation from Redhat.\n+endchoice\n\n config DEFAULT_MMAP_MIN_ADDR\n         int \"Low address space to protect from user allocation\"\ndiff --git a/mm/Makefile b/mm/Makefile\nindex 8481e42..0f8af9d 100644\n--- a/mm/Makefile\n+++ b/mm/Makefile\n@@ -41,7 +41,8 @@ obj-$(CONFIG_SPARSEMEM)\t+= sparse.o\n obj-$(CONFIG_SPARSEMEM_VMEMMAP) += sparse-vmemmap.o\n obj-$(CONFIG_SLOB) += slob.o\n obj-$(CONFIG_MMU_NOTIFIER) += mmu_notifier.o\n-obj-$(CONFIG_KSM) += ksm.o\n+obj-$(CONFIG_KSM_LEGACY) += ksm.o\n+obj-$(CONFIG_UKSM) += uksm.o\n obj-$(CONFIG_PAGE_POISONING) += debug-pagealloc.o\n obj-$(CONFIG_SLAB) += slab.o\n obj-$(CONFIG_SLUB) += slub.o\ndiff --git a/mm/memory.c b/mm/memory.c\nindex c10c6fb..cefd809 100644\n--- a/mm/memory.c\n+++ b/mm/memory.c\n@@ -120,6 +120,27 @@ __setup(\"norandmaps\", disable_randmaps);\n unsigned long zero_pfn __read_mostly;\n unsigned long highest_memmap_pfn __read_mostly;\n\n+#ifdef CONFIG_UKSM\n+unsigned long uksm_zero_pfn __read_mostly;\n+struct page *empty_uksm_zero_page;\n+\n+static int __init setup_uksm_zero_page(void)\n+{\n+\tunsigned long addr;\n+\taddr = __get_free_pages(GFP_KERNEL | __GFP_ZERO, 0);\n+\tif (!addr)\n+\t\tpanic(\"Oh boy, that early out of memory?\");\n+\n+\tempty_uksm_zero_page = virt_to_page((void *) addr);\n+\tSetPageReserved(empty_uksm_zero_page);\n+\n+\tuksm_zero_pfn = page_to_pfn(empty_uksm_zero_page);\n+\n+\treturn 0;\n+}\n+core_initcall(setup_uksm_zero_page);\n+#endif\n+\n /*\n  * CONFIG_MMU architectures set up ZERO_PAGE in their paging_init()\n  */\n@@ -131,6 +152,7 @@ static int __init init_zero_pfn(void)\n core_initcall(init_zero_pfn);\n\n+\n #if defined(SPLIT_RSS_COUNTING)\n\n void sync_mm_rss(struct mm_struct *mm)\n@@ -900,6 +922,11 @@ copy_one_pte(struct mm_struct *dst_mm, struct mm_struct *src_mm,\n \t\t\trss[MM_ANONPAGES]++;\n \t\telse\n \t\t\trss[MM_FILEPAGES]++;\n+\n+\t\t/* Should return NULL in vm_normal_page() */\n+\t\tuksm_bugon_zeropage(pte);\n+\t} else {\n+\t\tuksm_map_zero_page(pte);\n \t}\n\n out_set_pte:\n@@ -1142,8 +1169,10 @@ again:\n \t\t\tptent = ptep_get_and_clear_full(mm, addr, pte,\n \t\t\t\t\t\t\ttlb->fullmm);\n \t\t\ttlb_remove_tlb_entry(tlb, pte, addr);\n-\t\t\tif (unlikely(!page))\n+\t\t\tif (unlikely(!page)) {\n+\t\t\t\tuksm_unmap_zero_page(ptent);\n \t\t\t\tcontinue;\n+\t\t\t}\n \t\t\tif (unlikely(details) && details->nonlinear_vma\n \t\t\t    && linear_page_index(details->nonlinear_vma,\n \t\t\t\t\t\taddr) != page->index)\n@@ -1722,7 +1751,7 @@ long __get_user_pages(struct task_struct *tsk, struct mm_struct *mm,\n\n \tVM_BUG_ON(!!pages != !!(gup_flags & FOLL_GET));\n\n-\t/*\n+\t/*\n \t * Require read or write permissions.\n \t * If FOLL_FORCE is set, we only require the \"MAY\" flags.\n \t */\n@@ -1782,7 +1811,7 @@ long __get_user_pages(struct task_struct *tsk, struct mm_struct *mm,\n \t\t\t\tpage = vm_normal_page(vma, start, *pte);\n \t\t\t\tif (!page) {\n \t\t\t\t\tif (!(gup_flags & FOLL_DUMP) &&\n-\t\t\t\t\t     is_zero_pfn(pte_pfn(*pte)))\n+\t\t\t\t\t    (is_zero_pfn(pte_pfn(*pte))))\n \t\t\t\t\t\tpage = pte_page(*pte);\n \t\t\t\t\telse {\n \t\t\t\t\t\tpte_unmap(pte);\n@@ -2616,8 +2645,10 @@ static inline void cow_user_page(struct page *dst, struct page *src, unsigned lo\n \t\t\tclear_page(kaddr);\n \t\tkunmap_atomic(kaddr);\n \t\tflush_dcache_page(dst);\n-\t} else\n+\t} else {\n \t\tcopy_user_highpage(dst, src, va, vma);\n+\t\tuksm_cow_page(vma, src);\n+\t}\n }\n\n /*\n@@ -2823,6 +2854,7 @@ gotten:\n \t\tnew_page = alloc_zeroed_user_highpage_movable(vma, address);\n \t\tif (!new_page)\n \t\t\tgoto oom;\n+\t\tuksm_cow_pte(vma, orig_pte);\n \t} else {\n \t\tnew_page = alloc_page_vma(GFP_HIGHUSER_MOVABLE, vma, address);\n \t\tif (!new_page)\n@@ -2848,8 +2880,11 @@ gotten:\n \t\t\t\tdec_mm_counter_fast(mm, MM_FILEPAGES);\n \t\t\t\tinc_mm_counter_fast(mm, MM_ANONPAGES);\n \t\t\t}\n-\t\t} else\n+\t\t\tuksm_bugon_zeropage(orig_pte);\n+\t\t} else {\n+\t\t\tuksm_unmap_zero_page(orig_pte);\n \t\t\tinc_mm_counter_fast(mm, MM_ANONPAGES);\n+\t\t}\n \t\tflush_cache_page(vma, address, pte_pfn(orig_pte));\n \t\tentry = mk_pte(new_page, vma->vm_page_prot);\n \t\tentry = maybe_mkwrite(pte_mkdirty(entry), vma);\ndiff --git a/mm/mmap.c b/mm/mmap.c\nindex 3978cfa..55f512b 100644\n--- a/mm/mmap.c\n+++ b/mm/mmap.c\n@@ -35,6 +35,7 @@\n #include <linux/sched/sysctl.h>\n #include <linux/notifier.h>\n #include <linux/memory.h>\n+#include <linux/ksm.h>\n\n #include <asm/uaccess.h>\n #include <asm/cacheflush.h>\n@@ -64,7 +65,7 @@ static void unmap_region(struct mm_struct *mm,\n  * MAP_SHARED\tr: (no) no\tr: (yes) yes\tr: (no) yes\tr: (no) yes\n  *\t\tw: (no) no\tw: (no) no\tw: (yes) yes\tw: (no) no\n  *\t\tx: (no) no\tx: (no) yes\tx: (no) yes\tx: (yes) yes\n- *\n+ *\n  * MAP_PRIVATE\tr: (no) no\tr: (yes) yes\tr: (no) yes\tr: (no) yes\n  *\t\tw: (no) no\tw: (no) no\tw: (copy) copy\tw: (no) no\n  *\t\tx: (no) no\tx: (no) yes\tx: (no) yes\tx: (yes) yes\n@@ -251,6 +252,7 @@ static struct vm_area_struct *remove_vma(struct vm_area_struct *vma)\n \tif (vma->vm_file)\n \t\tfput(vma->vm_file);\n \tmpol_put(vma_policy(vma));\n+\tuksm_remove_vma(vma);\n \tkmem_cache_free(vm_area_cachep, vma);\n \treturn next;\n }\n@@ -706,9 +708,16 @@ int vma_adjust(struct vm_area_struct *vma, unsigned long start,\n \tlong adjust_next = 0;\n \tint remove_next = 0;\n\n+/*\n+ * to avoid deadlock, ksm_remove_vma must be done before any spin_lock is\n+ * acquired\n+ */\n+\tuksm_remove_vma(vma);\n+\n \tif (next && !insert) {\n \t\tstruct vm_area_struct *exporter = NULL;\n\n+\t\tuksm_remove_vma(next);\n \t\tif (end >= next->vm_end) {\n \t\t\t/*\n \t\t\t * vma expands, overlapping all the next, and\n@@ -798,6 +807,7 @@ again:\t\t\tremove_next = 1 + (end > next->vm_end);\n \t\tend_changed = true;\n \t}\n \tvma->vm_pgoff = pgoff;\n+\n \tif (adjust_next) {\n \t\tnext->vm_start += adjust_next << PAGE_SHIFT;\n \t\tnext->vm_pgoff += adjust_next;\n@@ -860,14 +870,20 @@ again:\t\t\tremove_next = 1 + (end > next->vm_end);\n \t\t * up the code too much to do both in one go.\n \t\t */\n \t\tnext = vma->vm_next;\n-\t\tif (remove_next == 2)\n+\t\tif (remove_next == 2) {\n+\t\t\tuksm_remove_vma(next);\n \t\t\tgoto again;\n-\t\telse if (next)\n+\t\t} else if (next) {\n \t\t\tvma_gap_update(next);\n-\t\telse\n+\t\t} else {\n \t\t\tmm->highest_vm_end = end;\n+\t\t}\n+\t} else {\n+\t\tif (next && !insert)\n+\t\t\tuksm_vma_add_new(next);\n \t}\n\n+\tuksm_vma_add_new(vma);\n \tvalidate_mm(mm);\n\n \treturn 0;\n@@ -1241,6 +1257,9 @@ unsigned long do_mmap_pgoff(struct file *file, unsigned long addr,\n \tvm_flags = calc_vm_prot_bits(prot) | calc_vm_flag_bits(flags) |\n \t\t\tmm->def_flags | VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC;\n\n+\t/* If uksm is enabled, we add VM_MERGABLE to new VMAs. */\n+\tuksm_vm_flags_mod(&vm_flags);\n+\n \tif (flags & MAP_LOCKED)\n \t\tif (!can_do_mlock())\n \t\t\treturn -EPERM;\n@@ -1604,6 +1623,7 @@ munmap_back:\n\n \tvma_link(mm, vma, prev, rb_link, rb_parent);\n \tfile = vma->vm_file;\n+\tuksm_vma_add_new(vma);\n\n \t/* Once vma denies write, undo our temporary denial count */\n \tif (correct_wcount)\n@@ -1632,6 +1652,7 @@ unmap_and_free_vma:\n \tunmap_region(mm, vma, prev, vma->vm_start, vma->vm_end);\n \tcharged = 0;\n free_vma:\n+\tuksm_remove_vma(vma);\n \tkmem_cache_free(vm_area_cachep, vma);\n unacct_error:\n \tif (charged)\n@@ -1880,7 +1901,7 @@ arch_get_unmapped_area(struct file *filp, unsigned long addr,\n \tinfo.align_mask = 0;\n \treturn vm_unmapped_area(&info);\n }\n-#endif\n+#endif\n\n void arch_unmap_area(struct mm_struct *mm, unsigned long addr)\n {\n@@ -2461,6 +2482,8 @@ static int __split_vma(struct mm_struct * mm, struct vm_area_struct * vma,\n \telse\n \t\terr = vma_adjust(vma, vma->vm_start, addr, vma->vm_pgoff, new);\n\n+\tuksm_vma_add_new(new);\n+\n \t/* Success. */\n \tif (!err)\n \t\treturn 0;\n@@ -2626,6 +2649,7 @@ static unsigned long do_brk(unsigned long addr, unsigned long len)\n \t\treturn addr;\n\n \tflags = VM_DATA_DEFAULT_FLAGS | VM_ACCOUNT | mm->def_flags;\n+\tuksm_vm_flags_mod(&flags);\n\n \terror = get_unmapped_area(NULL, addr, len, 0, MAP_FIXED);\n \tif (error & ~PAGE_MASK)\n@@ -2693,6 +2717,7 @@ static unsigned long do_brk(unsigned long addr, unsigned long len)\n \tvma->vm_flags = flags;\n \tvma->vm_page_prot = vm_get_page_prot(flags);\n \tvma_link(mm, vma, prev, rb_link, rb_parent);\n+\tuksm_vma_add_new(vma);\n out:\n \tperf_event_mmap(vma);\n \tmm->total_vm += len >> PAGE_SHIFT;\n@@ -2727,6 +2752,12 @@ void exit_mmap(struct mm_struct *mm)\n \t/* mm's last user has gone, and its about to be pulled down */\n \tmmu_notifier_release(mm);\n\n+\t/*\n+\t * Taking write lock on mmap_sem does not harm others,\n+\t * but it's crucial for uksm to avoid races.\n+\t */\n+\tdown_write(&mm->mmap_sem);\n+\n \tif (mm->locked_vm) {\n \t\tvma = mm->mmap;\n \t\twhile (vma) {\n@@ -2763,6 +2794,11 @@ void exit_mmap(struct mm_struct *mm)\n \t}\n \tvm_unacct_memory(nr_accounted);\n\n+\tmm->mmap = NULL;\n+\tmm->mm_rb = RB_ROOT;\n+\tmm->mmap_cache = NULL;\n+\tup_write(&mm->mmap_sem);\n+\n \tWARN_ON(mm->nr_ptes > (FIRST_USER_ADDRESS+PMD_SIZE-1)>>PMD_SHIFT);\n }\n\n@@ -2874,6 +2910,7 @@ struct vm_area_struct *copy_vma(struct vm_area_struct **vmap,\n \t\t\t\tnew_vma->vm_ops->open(new_vma);\n \t\t\tvma_link(mm, new_vma, prev, rb_link, rb_parent);\n \t\t\t*need_rmap_locks = false;\n+\t\t\tuksm_vma_add_new(new_vma);\n \t\t}\n \t}\n \treturn new_vma;\n@@ -2975,10 +3012,10 @@ int install_special_mapping(struct mm_struct *mm,\n \tret = insert_vm_struct(mm, vma);\n \tif (ret)\n \t\tgoto out;\n-\n \tmm->total_vm += len >> PAGE_SHIFT;\n\n \tperf_event_mmap(vma);\n+\tuksm_vma_add_new(vma);\n\n \treturn 0;\n\ndiff --git a/mm/rmap.c b/mm/rmap.c\nindex 482ae65..583bc3c 100644\n--- a/mm/rmap.c\n+++ b/mm/rmap.c\n@@ -1026,9 +1026,9 @@ void page_move_anon_rmap(struct page *page,\n\n /**\n  * __page_set_anon_rmap - set up new anonymous rmap\n- * @page:\tPage to add to rmap\n+ * @page:\tPage to add to rmap\n  * @vma:\tVM area to add page to.\n- * @address:\tUser virtual address of the mapping\n+ * @address:\tUser virtual address of the mapping\n  * @exclusive:\tthe page is exclusively owned by the current process\n  */\n static void __page_set_anon_rmap(struct page *page,\ndiff --git a/mm/uksm.c b/mm/uksm.c\nnew file mode 100644\nindex 0000000..9217be7\n--- /dev/null\n+++ b/mm/uksm.c\n@@ -0,0 +1,5649 @@\n+/*\n+ * Ultra KSM. Copyright (C) 2011-2012 Nai Xia\n+ *\n+ * This is an improvement upon KSM. Some basic data structures and routines\n+ * are borrowed from ksm.c .\n+ *\n+ * Its new features:\n+ * 1. Full system scan:\n+ *      It automatically scans all user processes' anonymous VMAs. Kernel-user\n+ *      interaction to submit a memory area to KSM is no longer needed.\n+ *\n+ * 2. Rich area detection:\n+ *      It automatically detects rich areas containing abundant duplicated\n+ *      pages based. Rich areas are given a full scan speed. Poor areas are\n+ *      sampled at a reasonable speed with very low CPU consumption.\n+ *\n+ * 3. Ultra Per-page scan speed improvement:\n+ *      A new hash algorithm is proposed. As a result, on a machine with\n+ *      Core(TM)2 Quad Q9300 CPU in 32-bit mode and 800MHZ DDR2 main memory, it\n+ *      can scan memory areas that does not contain duplicated pages at speed of\n+ *      627MB/sec ~ 2445MB/sec and can merge duplicated areas at speed of\n+ *      477MB/sec ~ 923MB/sec.\n+ *\n+ * 4. Thrashing area avoidance:\n+ *      Thrashing area(an VMA that has frequent Ksm page break-out) can be\n+ *      filtered out. My benchmark shows it's more efficient than KSM's per-page\n+ *      hash value based volatile page detection.\n+ *\n+ *\n+ * 5. Misc changes upon KSM:\n+ *      * It has a fully x86-opitmized memcmp dedicated for 4-byte-aligned page\n+ *        comparison. It's much faster than default C version on x86.\n+ *      * rmap_item now has an struct *page member to loosely cache a\n+ *        address-->page mapping, which reduces too much time-costly\n+ *        follow_page().\n+ *      * The VMA creation/exit procedures are hooked to let the Ultra KSM know.\n+ *      * try_to_merge_two_pages() now can revert a pte if it fails. No break_\n+ *        ksm is needed for this case.\n+ *\n+ * 6. Full Zero Page consideration(contributed by Figo Zhang)\n+ *    Now uksmd consider full zero pages as special pages and merge them to an\n+ *    special unswappable uksm zero page.\n+ */\n+\n+#include <linux/errno.h>\n+#include <linux/mm.h>\n+#include <linux/fs.h>\n+#include <linux/mman.h>\n+#include <linux/sched.h>\n+#include <linux/rwsem.h>\n+#include <linux/pagemap.h>\n+#include <linux/rmap.h>\n+#include <linux/spinlock.h>\n+#include <linux/jhash.h>\n+#include <linux/delay.h>\n+#include <linux/kthread.h>\n+#include <linux/wait.h>\n+#include <linux/slab.h>\n+#include <linux/rbtree.h>\n+#include <linux/memory.h>\n+#include <linux/mmu_notifier.h>\n+#include <linux/swap.h>\n+#include <linux/ksm.h>\n+#include <linux/crypto.h>\n+#include <linux/scatterlist.h>\n+#include <crypto/hash.h>\n+#include <linux/random.h>\n+#include <linux/math64.h>\n+#include <linux/gcd.h>\n+#include <linux/freezer.h>\n+#include <linux/sradix-tree.h>\n+\n+#include <asm/tlbflush.h>\n+#include \"internal.h\"\n+\n+#ifdef CONFIG_X86\n+#undef memcmp\n+\n+#ifdef CONFIG_X86_32\n+#define memcmp memcmpx86_32\n+/*\n+ * Compare 4-byte-aligned address s1 and s2, with length n\n+ */\n+int memcmpx86_32(void *s1, void *s2, size_t n)\n+{\n+\tsize_t num = n / 4;\n+\tregister int res;\n+\n+\t__asm__ __volatile__\n+\t(\n+\t \"testl %3,%3\\n\\t\"\n+\t \"repe; cmpsd\\n\\t\"\n+\t \"je        1f\\n\\t\"\n+\t \"sbbl      %0,%0\\n\\t\"\n+\t \"orl       $1,%0\\n\"\n+\t \"1:\"\n+\t : \"=&a\" (res), \"+&S\" (s1), \"+&D\" (s2), \"+&c\" (num)\n+\t : \"0\" (0)\n+\t : \"cc\");\n+\n+\treturn res;\n+}\n+\n+/*\n+ * Check the page is all zero ?\n+ */\n+static int is_full_zero(const void *s1, size_t len)\n+{\n+\tunsigned char same;\n+\n+\tlen /= 4;\n+\n+\t__asm__ __volatile__\n+\t(\"repe; scasl;\"\n+\t \"sete %0\"\n+\t : \"=qm\" (same), \"+D\" (s1), \"+c\" (len)\n+\t : \"a\" (0)\n+\t : \"cc\");\n+\n+\treturn same;\n+}\n+\n+\n+#elif defined(CONFIG_X86_64)\n+#define memcmp memcmpx86_64\n+/*\n+ * Compare 8-byte-aligned address s1 and s2, with length n\n+ */\n+int memcmpx86_64(void *s1, void *s2, size_t n)\n+{\n+\tsize_t num = n / 8;\n+\tregister int res;\n+\n+\t__asm__ __volatile__\n+\t(\n+\t \"testq %q3,%q3\\n\\t\"\n+\t \"repe; cmpsq\\n\\t\"\n+\t \"je        1f\\n\\t\"\n+\t \"sbbq      %q0,%q0\\n\\t\"\n+\t \"orq       $1,%q0\\n\"\n+\t \"1:\"\n+\t : \"=&a\" (res), \"+&S\" (s1), \"+&D\" (s2), \"+&c\" (num)\n+\t : \"0\" (0)\n+\t : \"cc\");\n+\n+\treturn res;\n+}\n+\n+static int is_full_zero(const void *s1, size_t len)\n+{\n+\tunsigned char same;\n+\n+\tlen /= 8;\n+\n+\t__asm__ __volatile__\n+\t(\"repe; scasq;\"\n+\t \"sete %0\"\n+\t : \"=qm\" (same), \"+D\" (s1), \"+c\" (len)\n+\t : \"a\" (0)\n+\t : \"cc\");\n+\n+\treturn same;\n+}\n+\n+#endif\n+#else\n+static int is_full_zero(const void *s1, size_t len)\n+{\n+\tconst unsigned long *src = s1;\n+\tint i;\n+\n+\tlen /= sizeof(*src);\n+\n+\tfor (i = 0; i < len; i++) {\n+\t\tif (src[i])\n+\t\t\treturn 0;\n+\t}\n+\n+\treturn 1;\n+}\n+#endif\n+\n+#define U64_MAX\t\t(~((u64)0))\n+#define UKSM_RUNG_ROUND_FINISHED  (1 << 0)\n+#define TIME_RATIO_SCALE\t10000\n+\n+#define SLOT_TREE_NODE_SHIFT\t8\n+#define SLOT_TREE_NODE_STORE_SIZE\t(1UL << SLOT_TREE_NODE_SHIFT)\n+struct slot_tree_node {\n+\tunsigned long size;\n+\tstruct sradix_tree_node snode;\n+\tvoid *stores[SLOT_TREE_NODE_STORE_SIZE];\n+};\n+\n+static struct kmem_cache *slot_tree_node_cachep;\n+\n+static struct sradix_tree_node *slot_tree_node_alloc(void)\n+{\n+\tstruct slot_tree_node *p;\n+\tp = kmem_cache_zalloc(slot_tree_node_cachep, GFP_KERNEL);\n+\tif (!p)\n+\t\treturn NULL;\n+\n+\treturn &p->snode;\n+}\n+\n+static void slot_tree_node_free(struct sradix_tree_node *node)\n+{\n+\tstruct slot_tree_node *p;\n+\n+\tp = container_of(node, struct slot_tree_node, snode);\n+\tkmem_cache_free(slot_tree_node_cachep, p);\n+}\n+\n+static void slot_tree_node_extend(struct sradix_tree_node *parent,\n+\t\t\t\t  struct sradix_tree_node *child)\n+{\n+\tstruct slot_tree_node *p, *c;\n+\n+\tp = container_of(parent, struct slot_tree_node, snode);\n+\tc = container_of(child, struct slot_tree_node, snode);\n+\n+\tp->size += c->size;\n+}\n+\n+void slot_tree_node_assign(struct sradix_tree_node *node,\n+\t\t\t   unsigned index, void *item)\n+{\n+\tstruct vma_slot *slot = item;\n+\tstruct slot_tree_node *cur;\n+\n+\tslot->snode = node;\n+\tslot->sindex = index;\n+\n+\twhile (node) {\n+\t\tcur = container_of(node, struct slot_tree_node, snode);\n+\t\tcur->size += slot->pages;\n+\t\tnode = node->parent;\n+\t}\n+}\n+\n+void slot_tree_node_rm(struct sradix_tree_node *node, unsigned offset)\n+{\n+\tstruct vma_slot *slot;\n+\tstruct slot_tree_node *cur;\n+\tunsigned long pages;\n+\n+\tif (node->height == 1) {\n+\t\tslot = node->stores[offset];\n+\t\tpages = slot->pages;\n+\t} else {\n+\t\tcur = container_of(node->stores[offset],\n+\t\t\t\t   struct slot_tree_node, snode);\n+\t\tpages = cur->size;\n+\t}\n+\n+\twhile (node) {\n+\t\tcur = container_of(node, struct slot_tree_node, snode);\n+\t\tcur->size -= pages;\n+\t\tnode = node->parent;\n+\t}\n+}\n+\n+unsigned long slot_iter_index;\n+int slot_iter(void *item,  unsigned long height)\n+{\n+\tstruct slot_tree_node *node;\n+\tstruct vma_slot *slot;\n+\n+\tif (height == 1) {\n+\t\tslot = item;\n+\t\tif (slot_iter_index < slot->pages) {\n+\t\t\t/*in this one*/\n+\t\t\treturn 1;\n+\t\t} else {\n+\t\t\tslot_iter_index -= slot->pages;\n+\t\t\treturn 0;\n+\t\t}\n+\n+\t} else {\n+\t\tnode = container_of(item, struct slot_tree_node, snode);\n+\t\tif (slot_iter_index < node->size) {\n+\t\t\t/*in this one*/\n+\t\t\treturn 1;\n+\t\t} else {\n+\t\t\tslot_iter_index -= node->size;\n+\t\t\treturn 0;\n+\t\t}\n+\t}\n+}\n+\n+\n+static inline void slot_tree_init_root(struct sradix_tree_root *root)\n+{\n+\tinit_sradix_tree_root(root, SLOT_TREE_NODE_SHIFT);\n+\troot->alloc = slot_tree_node_alloc;\n+\troot->free = slot_tree_node_free;\n+\troot->extend = slot_tree_node_extend;\n+\troot->assign = slot_tree_node_assign;\n+\troot->rm = slot_tree_node_rm;\n+}\n+\n+void slot_tree_init(void)\n+{\n+\tslot_tree_node_cachep = kmem_cache_create(\"slot_tree_node\",\n+\t\t\t\tsizeof(struct slot_tree_node), 0,\n+\t\t\t\tSLAB_PANIC | SLAB_RECLAIM_ACCOUNT,\n+\t\t\t\tNULL);\n+}\n+\n+\n+/* Each rung of this ladder is a list of VMAs having a same scan ratio */\n+struct scan_rung {\n+\t//struct list_head scanned_list;\n+\tstruct sradix_tree_root vma_root;\n+\tstruct sradix_tree_root vma_root2;\n+\n+\tstruct vma_slot *current_scan;\n+\tunsigned long current_offset;\n+\n+\t/*\n+\t * The initial value for current_offset, it should loop over\n+\t * [0~ step - 1] to let all slot have its chance to be scanned.\n+\t */\n+\tunsigned long offset_init;\n+\tunsigned long step; /* dynamic step for current_offset */\n+\tunsigned int flags;\n+\tunsigned long pages_to_scan;\n+\t//unsigned long fully_scanned_slots;\n+\t/*\n+\t * a little bit tricky - if cpu_time_ratio > 0, then the value is the\n+\t * the cpu time ratio it can spend in rung_i for every scan\n+\t * period. if < 0, then it is the cpu time ratio relative to the\n+\t * max cpu percentage user specified. Both in unit of\n+\t * 1/TIME_RATIO_SCALE\n+\t */\n+\tint cpu_ratio;\n+\n+\t/*\n+\t * How long it will take for all slots in this rung to be fully\n+\t * scanned? If it's zero, we don't care about the cover time:\n+\t * it's fully scanned.\n+\t */\n+\tunsigned int cover_msecs;\n+\t//unsigned long vma_num;\n+\t//unsigned long pages; /* Sum of all slot's pages in rung */\n+};\n+\n+/**\n+ * node of either the stable or unstale rbtree\n+ *\n+ */\n+struct tree_node {\n+\tstruct rb_node node; /* link in the main (un)stable rbtree */\n+\tstruct rb_root sub_root; /* rb_root for sublevel collision rbtree */\n+\tu32 hash;\n+\tunsigned long count; /* TODO: merged with sub_root */\n+\tstruct list_head all_list; /* all tree nodes in stable/unstable tree */\n+};\n+\n+/**\n+ * struct stable_node - node of the stable rbtree\n+ * @node: rb node of this ksm page in the stable tree\n+ * @hlist: hlist head of rmap_items using this ksm page\n+ * @kpfn: page frame number of this ksm page\n+ */\n+struct stable_node {\n+\tstruct rb_node node; /* link in sub-rbtree */\n+\tstruct tree_node *tree_node; /* it's tree node root in stable tree, NULL if it's in hell list */\n+\tstruct hlist_head hlist;\n+\tunsigned long kpfn;\n+\tu32 hash_max; /* if ==0 then it's not been calculated yet */\n+\tstruct list_head all_list; /* in a list for all stable nodes */\n+};\n+\n+/**\n+ * struct node_vma - group rmap_items linked in a same stable\n+ * node together.\n+ */\n+struct node_vma {\n+\tunion {\n+\t\tstruct vma_slot *slot;\n+\t\tunsigned long key;  /* slot is used as key sorted on hlist */\n+\t};\n+\tstruct hlist_node hlist;\n+\tstruct hlist_head rmap_hlist;\n+\tstruct stable_node *head;\n+};\n+\n+/**\n+ * struct rmap_item - reverse mapping item for virtual addresses\n+ * @rmap_list: next rmap_item in mm_slot's singly-linked rmap_list\n+ * @anon_vma: pointer to anon_vma for this mm,address, when in stable tree\n+ * @mm: the memory structure this rmap_item is pointing into\n+ * @address: the virtual address this rmap_item tracks (+ flags in low bits)\n+ * @node: rb node of this rmap_item in the unstable tree\n+ * @head: pointer to stable_node heading this list in the stable tree\n+ * @hlist: link into hlist of rmap_items hanging off that stable_node\n+ */\n+struct rmap_item {\n+\tstruct vma_slot *slot;\n+\tstruct page *page;\n+\tunsigned long address;\t/* + low bits used for flags below */\n+\tunsigned long hash_round;\n+\tunsigned long entry_index;\n+\tunion {\n+\t\tstruct {/* when in unstable tree */\n+\t\t\tstruct rb_node node;\n+\t\t\tstruct tree_node *tree_node;\n+\t\t\tu32 hash_max;\n+\t\t};\n+\t\tstruct { /* when in stable tree */\n+\t\t\tstruct node_vma *head;\n+\t\t\tstruct hlist_node hlist;\n+\t\t\tstruct anon_vma *anon_vma;\n+\t\t};\n+\t};\n+} __attribute__((aligned(4)));\n+\n+struct rmap_list_entry {\n+\tunion {\n+\t\tstruct rmap_item *item;\n+\t\tunsigned long addr;\n+\t};\n+\t/* lowest bit is used for is_addr tag */\n+} __attribute__((aligned(4))); /* 4 aligned to fit in to pages*/\n+\n+\n+/* Basic data structure definition ends */\n+\n+\n+/*\n+ * Flags for rmap_item to judge if it's listed in the stable/unstable tree.\n+ * The flags use the low bits of rmap_item.address\n+ */\n+#define UNSTABLE_FLAG\t0x1\n+#define STABLE_FLAG\t0x2\n+#define get_rmap_addr(x)\t((x)->address & PAGE_MASK)\n+\n+/*\n+ * rmap_list_entry helpers\n+ */\n+#define IS_ADDR_FLAG\t1\n+#define is_addr(ptr)\t\t((unsigned long)(ptr) & IS_ADDR_FLAG)\n+#define set_is_addr(ptr)\t((ptr) |= IS_ADDR_FLAG)\n+#define get_clean_addr(ptr)\t(((ptr) & ~(__typeof__(ptr))IS_ADDR_FLAG))\n+\n+\n+/*\n+ * High speed caches for frequently allocated and freed structs\n+ */\n+static struct kmem_cache *rmap_item_cache;\n+static struct kmem_cache *stable_node_cache;\n+static struct kmem_cache *node_vma_cache;\n+static struct kmem_cache *vma_slot_cache;\n+static struct kmem_cache *tree_node_cache;\n+#define UKSM_KMEM_CACHE(__struct, __flags) kmem_cache_create(\"uksm_\"#__struct,\\\n+\t\tsizeof(struct __struct), __alignof__(struct __struct),\\\n+\t\t(__flags), NULL)\n+\n+/* Array of all scan_rung, uksm_scan_ladder[0] having the minimum scan ratio */\n+#define SCAN_LADDER_SIZE 4\n+static struct scan_rung uksm_scan_ladder[SCAN_LADDER_SIZE];\n+\n+/* The evaluation rounds uksmd has finished */\n+static unsigned long long uksm_eval_round = 1;\n+\n+/*\n+ * we add 1 to this var when we consider we should rebuild the whole\n+ * unstable tree.\n+ */\n+static unsigned long uksm_hash_round = 1;\n+\n+/*\n+ * How many times the whole memory is scanned.\n+ */\n+static unsigned long long fully_scanned_round = 1;\n+\n+/* The total number of virtual pages of all vma slots */\n+static u64 uksm_pages_total;\n+\n+/* The number of pages has been scanned since the start up */\n+static u64 uksm_pages_scanned;\n+\n+static u64 scanned_virtual_pages;\n+\n+/* The number of pages has been scanned since last encode_benefit call */\n+static u64 uksm_pages_scanned_last;\n+\n+/* If the scanned number is tooo large, we encode it here */\n+static u64 pages_scanned_stored;\n+\n+static unsigned long pages_scanned_base;\n+\n+/* The number of nodes in the stable tree */\n+static unsigned long uksm_pages_shared;\n+\n+/* The number of page slots additionally sharing those nodes */\n+static unsigned long uksm_pages_sharing;\n+\n+/* The number of nodes in the unstable tree */\n+static unsigned long uksm_pages_unshared;\n+\n+/*\n+ * Milliseconds ksmd should sleep between scans,\n+ * >= 100ms to be consistent with\n+ * scan_time_to_sleep_msec()\n+ */\n+static unsigned int uksm_sleep_jiffies;\n+\n+/* The real value for the uksmd next sleep */\n+static unsigned int uksm_sleep_real;\n+\n+/* Saved value for user input uksm_sleep_jiffies when it's enlarged */\n+static unsigned int uksm_sleep_saved;\n+\n+/* Max percentage of cpu utilization ksmd can take to scan in one batch */\n+static unsigned int uksm_max_cpu_percentage;\n+\n+static int uksm_cpu_governor;\n+\n+static char *uksm_cpu_governor_str[4] = { \"full\", \"medium\", \"low\", \"quiet\" };\n+\n+struct uksm_cpu_preset_s {\n+\tint cpu_ratio[SCAN_LADDER_SIZE];\n+\tunsigned int cover_msecs[SCAN_LADDER_SIZE];\n+\tunsigned int max_cpu; /* percentage */\n+};\n+\n+struct uksm_cpu_preset_s uksm_cpu_preset[4] = {\n+\t{ {20, 40, -2500, -10000}, {1000, 500, 200, 50}, 95},\n+\t{ {20, 30, -2500, -10000}, {1000, 500, 400, 100}, 50},\n+\t{ {10, 20, -5000, -10000}, {1500, 1000, 1000, 250}, 20},\n+\t{ {10, 20, 40, 75}, {2000, 1000, 1000, 1000}, 1},\n+};\n+\n+/* The default value for uksm_ema_page_time if it's not initialized */\n+#define UKSM_PAGE_TIME_DEFAULT\t500\n+\n+/*cost to scan one page by expotional moving average in nsecs */\n+static unsigned long uksm_ema_page_time = UKSM_PAGE_TIME_DEFAULT;\n+\n+/* The expotional moving average alpha weight, in percentage. */\n+#define EMA_ALPHA\t20\n+\n+/*\n+ * The threshold used to filter out thrashing areas,\n+ * If it == 0, filtering is disabled, otherwise it's the percentage up-bound\n+ * of the thrashing ratio of all areas. Any area with a bigger thrashing ratio\n+ * will be considered as having a zero duplication ratio.\n+ */\n+static unsigned int uksm_thrash_threshold = 50;\n+\n+/* How much dedup ratio is considered to be abundant*/\n+static unsigned int uksm_abundant_threshold = 10;\n+\n+/* All slots having merged pages in this eval round. */\n+struct list_head vma_slot_dedup = LIST_HEAD_INIT(vma_slot_dedup);\n+\n+/* How many times the ksmd has slept since startup */\n+static unsigned long long uksm_sleep_times;\n+\n+#define UKSM_RUN_STOP\t0\n+#define UKSM_RUN_MERGE\t1\n+static unsigned int uksm_run = 0;\n+\n+static DECLARE_WAIT_QUEUE_HEAD(uksm_thread_wait);\n+static DEFINE_MUTEX(uksm_thread_mutex);\n+\n+/*\n+ * List vma_slot_new is for newly created vma_slot waiting to be added by\n+ * ksmd. If one cannot be added(e.g. due to it's too small), it's moved to\n+ * vma_slot_noadd. vma_slot_del is the list for vma_slot whose corresponding\n+ * VMA has been removed/freed.\n+ */\n+struct list_head vma_slot_new = LIST_HEAD_INIT(vma_slot_new);\n+struct list_head vma_slot_noadd = LIST_HEAD_INIT(vma_slot_noadd);\n+struct list_head vma_slot_del = LIST_HEAD_INIT(vma_slot_del);\n+static DEFINE_SPINLOCK(vma_slot_list_lock);\n+\n+/* The unstable tree heads */\n+static struct rb_root root_unstable_tree = RB_ROOT;\n+\n+/*\n+ * All tree_nodes are in a list to be freed at once when unstable tree is\n+ * freed after each scan round.\n+ */\n+static struct list_head unstable_tree_node_list =\n+\t\t\t\tLIST_HEAD_INIT(unstable_tree_node_list);\n+\n+/* List contains all stable nodes */\n+static struct list_head stable_node_list = LIST_HEAD_INIT(stable_node_list);\n+\n+/*\n+ * When the hash strength is changed, the stable tree must be delta_hashed and\n+ * re-structured. We use two set of below structs to speed up the\n+ * re-structuring of stable tree.\n+ */\n+static struct list_head\n+stable_tree_node_list[2] = {LIST_HEAD_INIT(stable_tree_node_list[0]),\n+\t\t\t    LIST_HEAD_INIT(stable_tree_node_list[1])};\n+\n+static struct list_head *stable_tree_node_listp = &stable_tree_node_list[0];\n+static struct rb_root root_stable_tree[2] = {RB_ROOT, RB_ROOT};\n+static struct rb_root *root_stable_treep = &root_stable_tree[0];\n+static unsigned long stable_tree_index;\n+\n+/* The hash strength needed to hash a full page */\n+#define HASH_STRENGTH_FULL\t\t(PAGE_SIZE / sizeof(u32))\n+\n+/* The hash strength needed for loop-back hashing */\n+#define HASH_STRENGTH_MAX\t\t(HASH_STRENGTH_FULL + 10)\n+\n+/* The random offsets in a page */\n+static u32 *random_nums;\n+\n+/* The hash strength */\n+static unsigned long hash_strength = HASH_STRENGTH_FULL >> 4;\n+\n+/* The delta value each time the hash strength increases or decreases */\n+static unsigned long hash_strength_delta;\n+#define HASH_STRENGTH_DELTA_MAX\t5\n+\n+/* The time we have saved due to random_sample_hash */\n+static u64 rshash_pos;\n+\n+/* The time we have wasted due to hash collision */\n+static u64 rshash_neg;\n+\n+struct uksm_benefit {\n+\tu64 pos;\n+\tu64 neg;\n+\tu64 scanned;\n+\tunsigned long base;\n+} benefit;\n+\n+/*\n+ * The relative cost of memcmp, compared to 1 time unit of random sample\n+ * hash, this value is tested when ksm module is initialized\n+ */\n+static unsigned long memcmp_cost;\n+\n+static unsigned long  rshash_neg_cont_zero;\n+static unsigned long  rshash_cont_obscure;\n+\n+/* The possible states of hash strength adjustment heuristic */\n+enum rshash_states {\n+\t\tRSHASH_STILL,\n+\t\tRSHASH_TRYUP,\n+\t\tRSHASH_TRYDOWN,\n+\t\tRSHASH_NEW,\n+\t\tRSHASH_PRE_STILL,\n+};\n+\n+/* The possible direction we are about to adjust hash strength */\n+enum rshash_direct {\n+\tGO_UP,\n+\tGO_DOWN,\n+\tOBSCURE,\n+\tSTILL,\n+};\n+\n+/* random sampling hash state machine */\n+static struct {\n+\tenum rshash_states state;\n+\tenum rshash_direct pre_direct;\n+\tu8 below_count;\n+\t/* Keep a lookup window of size 5, iff above_count/below_count > 3\n+\t * in this window we stop trying.\n+\t */\n+\tu8 lookup_window_index;\n+\tu64 stable_benefit;\n+\tunsigned long turn_point_down;\n+\tunsigned long turn_benefit_down;\n+\tunsigned long turn_point_up;\n+\tunsigned long turn_benefit_up;\n+\tunsigned long stable_point;\n+} rshash_state;\n+\n+/*zero page hash table, hash_strength [0 ~ HASH_STRENGTH_MAX]*/\n+static u32 *zero_hash_table;\n+\n+static inline struct node_vma *alloc_node_vma(void)\n+{\n+\tstruct node_vma *node_vma;\n+\tnode_vma = kmem_cache_zalloc(node_vma_cache, GFP_KERNEL);\n+\tif (node_vma) {\n+\t\tINIT_HLIST_HEAD(&node_vma->rmap_hlist);\n+\t\tINIT_HLIST_NODE(&node_vma->hlist);\n+\t}\n+\treturn node_vma;\n+}\n+\n+static inline void free_node_vma(struct node_vma *node_vma)\n+{\n+\tkmem_cache_free(node_vma_cache, node_vma);\n+}\n+\n+\n+static inline struct vma_slot *alloc_vma_slot(void)\n+{\n+\tstruct vma_slot *slot;\n+\n+\t/*\n+\t * In case ksm is not initialized by now.\n+\t * Oops, we need to consider the call site of uksm_init() in the future.\n+\t */\n+\tif (!vma_slot_cache)\n+\t\treturn NULL;\n+\n+\tslot = kmem_cache_zalloc(vma_slot_cache, GFP_KERNEL);\n+\tif (slot) {\n+\t\tINIT_LIST_HEAD(&slot->slot_list);\n+\t\tINIT_LIST_HEAD(&slot->dedup_list);\n+\t\tslot->flags |= UKSM_SLOT_NEED_RERAND;\n+\t}\n+\treturn slot;\n+}\n+\n+static inline void free_vma_slot(struct vma_slot *vma_slot)\n+{\n+\tkmem_cache_free(vma_slot_cache, vma_slot);\n+}\n+\n+\n+\n+static inline struct rmap_item *alloc_rmap_item(void)\n+{\n+\tstruct rmap_item *rmap_item;\n+\n+\trmap_item = kmem_cache_zalloc(rmap_item_cache, GFP_KERNEL);\n+\tif (rmap_item) {\n+\t\t/* bug on lowest bit is not clear for flag use */\n+\t\tBUG_ON(is_addr(rmap_item));\n+\t}\n+\treturn rmap_item;\n+}\n+\n+static inline void free_rmap_item(struct rmap_item *rmap_item)\n+{\n+\trmap_item->slot = NULL;\t/* debug safety */\n+\tkmem_cache_free(rmap_item_cache, rmap_item);\n+}\n+\n+static inline struct stable_node *alloc_stable_node(void)\n+{\n+\tstruct stable_node *node;\n+\tnode = kmem_cache_alloc(stable_node_cache, GFP_KERNEL | GFP_ATOMIC);\n+\tif (!node)\n+\t\treturn NULL;\n+\n+\tINIT_HLIST_HEAD(&node->hlist);\n+\tlist_add(&node->all_list, &stable_node_list);\n+\treturn node;\n+}\n+\n+static inline void free_stable_node(struct stable_node *stable_node)\n+{\n+\tlist_del(&stable_node->all_list);\n+\tkmem_cache_free(stable_node_cache, stable_node);\n+}\n+\n+static inline struct tree_node *alloc_tree_node(struct list_head *list)\n+{\n+\tstruct tree_node *node;\n+\tnode = kmem_cache_zalloc(tree_node_cache, GFP_KERNEL | GFP_ATOMIC);\n+\tif (!node)\n+\t\treturn NULL;\n+\n+\tlist_add(&node->all_list, list);\n+\treturn node;\n+}\n+\n+static inline void free_tree_node(struct tree_node *node)\n+{\n+\tlist_del(&node->all_list);\n+\tkmem_cache_free(tree_node_cache, node);\n+}\n+\n+static void uksm_drop_anon_vma(struct rmap_item *rmap_item)\n+{\n+\tstruct anon_vma *anon_vma = rmap_item->anon_vma;\n+\n+\tput_anon_vma(anon_vma);\n+}\n+\n+\n+/**\n+ * Remove a stable node from stable_tree, may unlink from its tree_node and\n+ * may remove its parent tree_node if no other stable node is pending.\n+ *\n+ * @stable_node \tThe node need to be removed\n+ * @unlink_rb \t\tWill this node be unlinked from the rbtree?\n+ * @remove_tree_\tnode Will its tree_node be removed if empty?\n+ */\n+static void remove_node_from_stable_tree(struct stable_node *stable_node,\n+\t\t\t\t\t int unlink_rb,  int remove_tree_node)\n+{\n+\tstruct node_vma *node_vma;\n+\tstruct rmap_item *rmap_item;\n+\tstruct hlist_node *hlist, *rmap_hlist, *n;\n+\n+\tif (!hlist_empty(&stable_node->hlist)) {\n+\t\thlist_for_each_entry_safe(node_vma, hlist, n,\n+\t\t\t\t\t  &stable_node->hlist, hlist) {\n+\t\t\thlist_for_each_entry(rmap_item, rmap_hlist,\n+\t\t\t\t\t     &node_vma->rmap_hlist, hlist) {\n+\t\t\t\tuksm_pages_sharing--;\n+\n+\t\t\t\tuksm_drop_anon_vma(rmap_item);\n+\t\t\t\trmap_item->address &= PAGE_MASK;\n+\t\t\t}\n+\t\t\tfree_node_vma(node_vma);\n+\t\t\tcond_resched();\n+\t\t}\n+\n+\t\t/* the last one is counted as shared */\n+\t\tuksm_pages_shared--;\n+\t\tuksm_pages_sharing++;\n+\t}\n+\n+\tif (stable_node->tree_node && unlink_rb) {\n+\t\trb_erase(&stable_node->node,\n+\t\t\t &stable_node->tree_node->sub_root);\n+\n+\t\tif (RB_EMPTY_ROOT(&stable_node->tree_node->sub_root) &&\n+\t\t    remove_tree_node) {\n+\t\t\trb_erase(&stable_node->tree_node->node,\n+\t\t\t\t root_stable_treep);\n+\t\t\tfree_tree_node(stable_node->tree_node);\n+\t\t} else {\n+\t\t\tstable_node->tree_node->count--;\n+\t\t}\n+\t}\n+\n+\tfree_stable_node(stable_node);\n+}\n+\n+\n+/*\n+ * get_uksm_page: checks if the page indicated by the stable node\n+ * is still its ksm page, despite having held no reference to it.\n+ * In which case we can trust the content of the page, and it\n+ * returns the gotten page; but if the page has now been zapped,\n+ * remove the stale node from the stable tree and return NULL.\n+ *\n+ * You would expect the stable_node to hold a reference to the ksm page.\n+ * But if it increments the page's count, swapping out has to wait for\n+ * ksmd to come around again before it can free the page, which may take\n+ * seconds or even minutes: much too unresponsive.  So instead we use a\n+ * \"keyhole reference\": access to the ksm page from the stable node peeps\n+ * out through its keyhole to see if that page still holds the right key,\n+ * pointing back to this stable node.  This relies on freeing a PageAnon\n+ * page to reset its page->mapping to NULL, and relies on no other use of\n+ * a page to put something that might look like our key in page->mapping.\n+ *\n+ * include/linux/pagemap.h page_cache_get_speculative() is a good reference,\n+ * but this is different - made simpler by uksm_thread_mutex being held, but\n+ * interesting for assuming that no other use of the struct page could ever\n+ * put our expected_mapping into page->mapping (or a field of the union which\n+ * coincides with page->mapping).  The RCU calls are not for KSM at all, but\n+ * to keep the page_count protocol described with page_cache_get_speculative.\n+ *\n+ * Note: it is possible that get_uksm_page() will return NULL one moment,\n+ * then page the next, if the page is in between page_freeze_refs() and\n+ * page_unfreeze_refs(): this shouldn't be a problem anywhere, the page\n+ * is on its way to being freed; but it is an anomaly to bear in mind.\n+ *\n+ * @unlink_rb: \t\tif the removal of this node will firstly unlink from\n+ * its rbtree. stable_node_reinsert will prevent this when restructuring the\n+ * node from its old tree.\n+ *\n+ * @remove_tree_node:\tif this is the last one of its tree_node, will the\n+ * tree_node be freed ? If we are inserting stable node, this tree_node may\n+ * be reused, so don't free it.\n+ */\n+static struct page *get_uksm_page(struct stable_node *stable_node,\n+\t\t\t\t int unlink_rb, int remove_tree_node)\n+{\n+\tstruct page *page;\n+\tvoid *expected_mapping;\n+\n+\tpage = pfn_to_page(stable_node->kpfn);\n+\texpected_mapping = (void *)stable_node +\n+\t\t\t\t(PAGE_MAPPING_ANON | PAGE_MAPPING_KSM);\n+\trcu_read_lock();\n+\tif (page->mapping != expected_mapping)\n+\t\tgoto stale;\n+\tif (!get_page_unless_zero(page))\n+\t\tgoto stale;\n+\tif (page->mapping != expected_mapping) {\n+\t\tput_page(page);\n+\t\tgoto stale;\n…","distinct":true,"url":"https://api.github.com/repos/robcore/Alucard-Kernel-jfltexx/commits/a8242d6bf9d0028c7e1d676d61f05671cc8b1905"}]}