I observe that it is unlikely for KSM to merge new pages from an area
that has already been scanned twice on Android mobile devices, so it's
a waste of power to continue to scan these areas in high frequency.
In this patch a defer mechanism is introduced which is borrowed from
page compaction to KSM. This defer mechanism can automatic lower the scan
frequency in the above case.

Signed-off-by: Wenwei Tao <wenweitaowen...@gmail.com>
---
 mm/ksm.c |  230 ++++++++++++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 203 insertions(+), 27 deletions(-)

diff --git a/mm/ksm.c b/mm/ksm.c
index 4162dce..54ffcb2 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -104,6 +104,7 @@ struct mm_slot {
        struct list_head mm_list;
        struct rmap_item *rmap_list;
        struct mm_struct *mm;
+       unsigned long seqnr;
 };
 
 /**
@@ -117,9 +118,12 @@ struct mm_slot {
  */
 struct ksm_scan {
        struct mm_slot *mm_slot;
+       struct mm_slot *active_slot;
        unsigned long address;
        struct rmap_item **rmap_list;
        unsigned long seqnr;
+       unsigned long ksm_considered;
+       unsigned int ksm_defer_shift;
 };
 
 /**
@@ -182,6 +186,11 @@ struct rmap_item {
 #define UNSTABLE_FLAG  0x100   /* is a node of the unstable tree */
 #define STABLE_FLAG    0x200   /* is listed from the stable tree */
 
+#define ACTIVE_SLOT_FLAG       0x100
+#define ACTIVE_SLOT_SEQNR      0x200
+#define KSM_MAX_DEFER_SHIFT    6
+
+
 /* The stable and unstable tree heads */
 static struct rb_root one_stable_tree[1] = { RB_ROOT };
 static struct rb_root one_unstable_tree[1] = { RB_ROOT };
@@ -197,14 +206,22 @@ static DEFINE_HASHTABLE(mm_slots_hash, 
MM_SLOTS_HASH_BITS);
 static struct mm_slot ksm_mm_head = {
        .mm_list = LIST_HEAD_INIT(ksm_mm_head.mm_list),
 };
+
+static struct mm_slot ksm_mm_active = {
+       .mm_list = LIST_HEAD_INIT(ksm_mm_active.mm_list),
+};
+
 static struct ksm_scan ksm_scan = {
        .mm_slot = &ksm_mm_head,
+       .active_slot = &ksm_mm_active,
 };
 
 static struct kmem_cache *rmap_item_cache;
 static struct kmem_cache *stable_node_cache;
 static struct kmem_cache *mm_slot_cache;
 
+static bool ksm_merged_or_unstable;
+
 /* The number of nodes in the stable tree */
 static unsigned long ksm_pages_shared;
 
@@ -336,6 +353,23 @@ static void insert_to_mm_slots_hash(struct mm_struct *mm,
        hash_add(mm_slots_hash, &mm_slot->link, (unsigned long)mm);
 }
 
+static void move_to_active_list(struct mm_slot *mm_slot)
+{
+       if (mm_slot && !(mm_slot->seqnr & ACTIVE_SLOT_FLAG)) {
+               if (ksm_run & KSM_RUN_UNMERGE && mm_slot->rmap_list)
+                       return;
+               if (mm_slot == ksm_scan.mm_slot) {
+                       if (ksm_scan.active_slot == &ksm_mm_active)
+                               return;
+                       ksm_scan.mm_slot = list_entry(mm_slot->mm_list.next,
+                                               struct mm_slot, mm_list);
+               }
+               list_move_tail(&mm_slot->mm_list,
+                       &ksm_scan.active_slot->mm_list);
+               mm_slot->seqnr |= (ACTIVE_SLOT_FLAG | ACTIVE_SLOT_SEQNR);
+       }
+}
+
 /*
  * ksmd, and unmerge_and_remove_all_rmap_items(), must not touch an mm's
  * page tables after it has passed through ksm_exit() - which, if necessary,
@@ -772,6 +806,15 @@ static int unmerge_and_remove_all_rmap_items(void)
        int err = 0;
 
        spin_lock(&ksm_mmlist_lock);
+       mm_slot = list_entry(ksm_mm_active.mm_list.next,
+                       struct mm_slot, mm_list);
+       while (mm_slot != &ksm_mm_active) {
+               list_move_tail(&mm_slot->mm_list, &ksm_mm_head.mm_list);
+               mm_slot->seqnr &= ~(ACTIVE_SLOT_FLAG | ACTIVE_SLOT_SEQNR);
+               mm_slot = list_entry(ksm_mm_active.mm_list.next,
+                               struct mm_slot, mm_list);
+       }
+       ksm_scan.active_slot = &ksm_mm_active;
        ksm_scan.mm_slot = list_entry(ksm_mm_head.mm_list.next,
                                                struct mm_slot, mm_list);
        spin_unlock(&ksm_mmlist_lock);
@@ -790,8 +833,8 @@ static int unmerge_and_remove_all_rmap_items(void)
                        if (err)
                                goto error;
                }
-
                remove_trailing_rmap_items(mm_slot, &mm_slot->rmap_list);
+               mm_slot->seqnr = 0;
 
                spin_lock(&ksm_mmlist_lock);
                ksm_scan.mm_slot = list_entry(mm_slot->mm_list.next,
@@ -806,6 +849,7 @@ static int unmerge_and_remove_all_rmap_items(void)
                        up_read(&mm->mmap_sem);
                        mmdrop(mm);
                } else {
+                       move_to_active_list(mm_slot);
                        spin_unlock(&ksm_mmlist_lock);
                        up_read(&mm->mmap_sem);
                }
@@ -1401,6 +1445,9 @@ static void stable_tree_append(struct rmap_item 
*rmap_item,
                ksm_pages_sharing++;
        else
                ksm_pages_shared++;
+
+       if (!ksm_merged_or_unstable)
+               ksm_merged_or_unstable = true;
 }
 
 /*
@@ -1468,6 +1515,9 @@ static void cmp_and_merge_page(struct page *page, struct 
rmap_item *rmap_item)
        checksum = calc_checksum(page);
        if (rmap_item->oldchecksum != checksum) {
                rmap_item->oldchecksum = checksum;
+               if ((rmap_item->address & UNSTABLE_FLAG) &&
+                               !ksm_merged_or_unstable)
+                       ksm_merged_or_unstable = true;
                return;
        }
 
@@ -1504,6 +1554,31 @@ static void cmp_and_merge_page(struct page *page, struct 
rmap_item *rmap_item)
        }
 }
 
+static bool skip_active_slot_vma(struct rmap_item ***rmap_list,
+               struct vm_area_struct *vma, struct mm_slot *mm_slot)
+{
+       unsigned char age;
+       struct rmap_item *rmap_item = **rmap_list;
+
+       age = (unsigned char)(ksm_scan.seqnr - mm_slot->seqnr);
+       if (age > 0)
+               return false;
+       if (!(vma->vm_flags & VM_HUGETLB)) {
+               while (rmap_item && rmap_item->address < vma->vm_end) {
+                       if (rmap_item->address < vma->vm_start) {
+                               **rmap_list = rmap_item->rmap_list;
+                               remove_rmap_item_from_tree(rmap_item);
+                               free_rmap_item(rmap_item);
+                               rmap_item = **rmap_list;
+                       } else {
+                               *rmap_list = &rmap_item->rmap_list;
+                               rmap_item = rmap_item->rmap_list;
+                       }
+               }
+               return true;
+       } else
+               return false;
+}
 static struct rmap_item *get_next_rmap_item(struct mm_slot *mm_slot,
                                            struct rmap_item **rmap_list,
                                            unsigned long addr)
@@ -1535,15 +1610,18 @@ static struct rmap_item *get_next_rmap_item(struct 
mm_slot *mm_slot,
 static struct rmap_item *scan_get_next_rmap_item(struct page **page)
 {
        struct mm_struct *mm;
-       struct mm_slot *slot;
+       struct mm_slot *slot, *next_slot;
        struct vm_area_struct *vma;
        struct rmap_item *rmap_item;
        int nid;
 
-       if (list_empty(&ksm_mm_head.mm_list))
+       if (list_empty(&ksm_mm_head.mm_list) &&
+               list_empty(&ksm_mm_active.mm_list))
                return NULL;
-
-       slot = ksm_scan.mm_slot;
+       if (ksm_scan.active_slot != &ksm_mm_active)
+               slot = ksm_scan.active_slot;
+       else
+               slot = ksm_scan.mm_slot;
        if (slot == &ksm_mm_head) {
                /*
                 * A number of pages can hang around indefinitely on per-cpu
@@ -1582,8 +1660,16 @@ static struct rmap_item *scan_get_next_rmap_item(struct 
page **page)
                        root_unstable_tree[nid] = RB_ROOT;
 
                spin_lock(&ksm_mmlist_lock);
-               slot = list_entry(slot->mm_list.next, struct mm_slot, mm_list);
-               ksm_scan.mm_slot = slot;
+               if (unlikely(ksm_scan.seqnr == 0 &&
+                       !list_empty(&ksm_mm_active.mm_list))) {
+                       slot = list_entry(ksm_mm_active.mm_list.next,
+                               struct mm_slot, mm_list);
+                       ksm_scan.active_slot = slot;
+               } else {
+                       slot = list_entry(slot->mm_list.next,
+                               struct mm_slot, mm_list);
+                       ksm_scan.mm_slot = slot;
+               }
                spin_unlock(&ksm_mmlist_lock);
                /*
                 * Although we tested list_empty() above, a racing __ksm_exit
@@ -1608,7 +1694,8 @@ next_mm:
                        continue;
                if (ksm_scan.address < vma->vm_start)
                        ksm_scan.address = vma->vm_start;
-               if (!vma->anon_vma)
+               if (!vma->anon_vma || (ksm_scan.active_slot == slot &&
+                       skip_active_slot_vma(&ksm_scan.rmap_list, vma, slot)))
                        ksm_scan.address = vma->vm_end;
 
                while (ksm_scan.address < vma->vm_end) {
@@ -1639,6 +1726,9 @@ next_mm:
                        ksm_scan.address += PAGE_SIZE;
                        cond_resched();
                }
+               if ((slot->seqnr & (ACTIVE_SLOT_FLAG | ACTIVE_SLOT_SEQNR)) ==
+                       ACTIVE_SLOT_FLAG && vma->vm_flags & VM_HUGETLB)
+                       vma->vm_flags &= ~VM_HUGETLB;
        }
 
        if (ksm_test_exit(mm)) {
@@ -1652,8 +1742,25 @@ next_mm:
        remove_trailing_rmap_items(slot, ksm_scan.rmap_list);
 
        spin_lock(&ksm_mmlist_lock);
-       ksm_scan.mm_slot = list_entry(slot->mm_list.next,
-                                               struct mm_slot, mm_list);
+       slot->seqnr &= ~SEQNR_MASK;
+       slot->seqnr |= (ksm_scan.seqnr & SEQNR_MASK);
+       next_slot = list_entry(slot->mm_list.next,
+               struct mm_slot, mm_list);
+       if (slot == ksm_scan.active_slot) {
+               if (slot->seqnr & ACTIVE_SLOT_SEQNR)
+                       slot->seqnr &= ~ACTIVE_SLOT_SEQNR;
+               else {
+                       slot->seqnr &= ~ACTIVE_SLOT_FLAG;
+                       list_move_tail(&slot->mm_list,
+                               &ksm_scan.mm_slot->mm_list);
+               }
+               ksm_scan.active_slot = next_slot;
+       } else
+               ksm_scan.mm_slot = next_slot;
+
+       if (ksm_scan.active_slot == &ksm_mm_active)
+               ksm_scan.active_slot = list_entry(ksm_mm_active.mm_list.next,
+                                       struct mm_slot, mm_list);
        if (ksm_scan.address == 0) {
                /*
                 * We've completed a full scan of all vmas, holding mmap_sem
@@ -1664,6 +1771,9 @@ next_mm:
                 * or when all VM_MERGEABLE areas have been unmapped (and
                 * mmap_sem then protects against race with MADV_MERGEABLE).
                 */
+               if (ksm_scan.active_slot == slot)
+                       ksm_scan.active_slot = list_entry(slot->mm_list.next,
+                                               struct mm_slot, mm_list);
                hash_del(&slot->link);
                list_del(&slot->mm_list);
                spin_unlock(&ksm_mmlist_lock);
@@ -1678,10 +1788,13 @@ next_mm:
        }
 
        /* Repeat until we've completed scanning the whole list */
-       slot = ksm_scan.mm_slot;
-       if (slot != &ksm_mm_head)
+       if (ksm_scan.active_slot != &ksm_mm_active) {
+               slot = ksm_scan.active_slot;
                goto next_mm;
-
+       } else if (ksm_scan.mm_slot != &ksm_mm_head) {
+               slot = ksm_scan.mm_slot;
+               goto next_mm;
+       }
        ksm_scan.seqnr++;
        return NULL;
 }
@@ -1705,9 +1818,40 @@ static void ksm_do_scan(unsigned int scan_npages)
        }
 }
 
+/*This is copyed from page compaction*/
+
+static inline void defer_ksm(void)
+{
+       ksm_scan.ksm_considered = 0;
+       if (++ksm_scan.ksm_defer_shift > KSM_MAX_DEFER_SHIFT)
+               ksm_scan.ksm_defer_shift = KSM_MAX_DEFER_SHIFT;
+
+}
+
+static inline bool ksm_defered(void)
+{
+       unsigned long defer_limit = 1UL << ksm_scan.ksm_defer_shift;
+
+       if (++ksm_scan.ksm_considered > defer_limit)
+               ksm_scan.ksm_considered = defer_limit;
+       return ksm_scan.ksm_considered < defer_limit &&
+                       list_empty(&ksm_mm_active.mm_list);
+}
+
+static inline void reset_ksm_defer(void)
+{
+       if (ksm_scan.ksm_defer_shift != 0) {
+               ksm_scan.ksm_considered = 0;
+               ksm_scan.ksm_defer_shift = 0;
+       }
+}
+
+
 static int ksmd_should_run(void)
 {
-       return (ksm_run & KSM_RUN_MERGE) && !list_empty(&ksm_mm_head.mm_list);
+       return (ksm_run & KSM_RUN_MERGE) &&
+               !(list_empty(&ksm_mm_head.mm_list) &&
+                       list_empty(&ksm_mm_active.mm_list));
 }
 
 static int ksm_scan_thread(void *nothing)
@@ -1718,8 +1862,14 @@ static int ksm_scan_thread(void *nothing)
        while (!kthread_should_stop()) {
                mutex_lock(&ksm_thread_mutex);
                wait_while_offlining();
-               if (ksmd_should_run())
+               if (ksmd_should_run() && !ksm_defered()) {
+                       ksm_merged_or_unstable = false;
                        ksm_do_scan(ksm_thread_pages_to_scan);
+                       if (ksm_merged_or_unstable)
+                               reset_ksm_defer();
+                       else
+                               defer_ksm();
+               }
                mutex_unlock(&ksm_thread_mutex);
 
                try_to_freeze();
@@ -1739,6 +1889,8 @@ int ksm_madvise(struct vm_area_struct *vma, unsigned long 
start,
                unsigned long end, int advice, unsigned long *vm_flags)
 {
        struct mm_struct *mm = vma->vm_mm;
+       unsigned long vma_length =
+                       (vma->vm_end - vma->vm_start) >> PAGE_SHIFT;
        int err;
 
        switch (advice) {
@@ -1761,8 +1913,19 @@ int ksm_madvise(struct vm_area_struct *vma, unsigned 
long start,
                        if (err)
                                return err;
                }
-
-               *vm_flags |= VM_MERGEABLE;
+               /*
+               * Since hugetlb vma is not supported by ksm
+               * use VM_HUGETLB to indicate new mergeable vma
+               */
+               *vm_flags |= VM_MERGEABLE | VM_HUGETLB;
+               if (vma_length > ksm_thread_pages_to_scan) {
+                       struct mm_slot *mm_slot;
+
+                       spin_lock(&ksm_mmlist_lock);
+                       mm_slot = get_mm_slot(mm);
+                       move_to_active_list(mm_slot);
+                       spin_unlock(&ksm_mmlist_lock);
+               }
                break;
 
        case MADV_UNMERGEABLE:
@@ -1775,7 +1938,7 @@ int ksm_madvise(struct vm_area_struct *vma, unsigned long 
start,
                                return err;
                }
 
-               *vm_flags &= ~VM_MERGEABLE;
+               *vm_flags &= ~(VM_MERGEABLE | VM_HUGETLB);
                break;
        }
 
@@ -1792,7 +1955,8 @@ int __ksm_enter(struct mm_struct *mm)
                return -ENOMEM;
 
        /* Check ksm_run too?  Would need tighter locking */
-       needs_wakeup = list_empty(&ksm_mm_head.mm_list);
+       needs_wakeup = list_empty(&ksm_mm_head.mm_list) &&
+                       list_empty(&ksm_mm_active.mm_list);
 
        spin_lock(&ksm_mmlist_lock);
        insert_to_mm_slots_hash(mm, mm_slot);
@@ -1806,10 +1970,8 @@ int __ksm_enter(struct mm_struct *mm)
         * scanning cursor, otherwise KSM pages in newly forked mms will be
         * missed: then we might as well insert at the end of the list.
         */
-       if (ksm_run & KSM_RUN_UNMERGE)
-               list_add_tail(&mm_slot->mm_list, &ksm_mm_head.mm_list);
-       else
-               list_add_tail(&mm_slot->mm_list, &ksm_scan.mm_slot->mm_list);
+       list_add_tail(&mm_slot->mm_list, &ksm_scan.active_slot->mm_list);
+       mm_slot->seqnr |= (ACTIVE_SLOT_FLAG | ACTIVE_SLOT_SEQNR);
        spin_unlock(&ksm_mmlist_lock);
 
        set_bit(MMF_VM_MERGEABLE, &mm->flags);
@@ -1823,7 +1985,7 @@ int __ksm_enter(struct mm_struct *mm)
 
 void __ksm_exit(struct mm_struct *mm)
 {
-       struct mm_slot *mm_slot;
+       struct mm_slot *mm_slot, *current_slot;
        int easy_to_free = 0;
 
        /*
@@ -1837,14 +1999,28 @@ void __ksm_exit(struct mm_struct *mm)
 
        spin_lock(&ksm_mmlist_lock);
        mm_slot = get_mm_slot(mm);
-       if (mm_slot && ksm_scan.mm_slot != mm_slot) {
+       if (ksm_scan.active_slot != &ksm_mm_active)
+               current_slot = ksm_scan.active_slot;
+       else
+               current_slot = ksm_scan.mm_slot;
+       if (mm_slot && mm_slot != current_slot) {
                if (!mm_slot->rmap_list) {
                        hash_del(&mm_slot->link);
                        list_del(&mm_slot->mm_list);
                        easy_to_free = 1;
                } else {
-                       list_move(&mm_slot->mm_list,
-                                 &ksm_scan.mm_slot->mm_list);
+                       if (mm_slot == ksm_scan.mm_slot)
+                               ksm_scan.mm_slot =
+                                       list_entry(mm_slot->mm_list.next,
+                                               struct mm_slot, mm_list);
+                       if (ksm_run & KSM_RUN_UNMERGE)
+                               list_move(&mm_slot->mm_list,
+                                       &ksm_scan.mm_slot->mm_list);
+                       else {
+                               list_move(&mm_slot->mm_list,
+                                       &ksm_scan.active_slot->mm_list);
+                               mm_slot->seqnr |= ACTIVE_SLOT_FLAG;
+                       }
                }
        }
        spin_unlock(&ksm_mmlist_lock);
-- 
1.7.9.5

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Reply via email to