[RFC PATCH 2/4] ksm: implement scan-enhanced algorithm of auto mode

[cgel.zte@gmail.com]

From: xu xin <xu.xin16@zte.com.cn>

Implement the scan-enhanced algorithm of auto mode. In this algorithm,
after every time of scanning, if new ksm pages are obtained, it will
double pages_to_scan for the next scanning until the general
multiplying factor is not less than max_scanning_factor. If no new ksm
pages are obtained, then reset pages_to_scan to the default value.

We add the sysfs klob of max_scanning_factor to limit scanning factor's
excessive growth.

Signed-off-by: CGEL <cgel.zte@gmail.com>
Signed-off-by: xu xin <xu.xin16@zte.com.cn>
---
 mm/ksm.c | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 86 insertions(+), 2 deletions(-)

diff --git a/mm/ksm.c b/mm/ksm.c
index c80d908221a4..8acc893e4d61 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -131,6 +131,8 @@ struct mm_slot {
  * @address: the next address inside that to be scanned
  * @rmap_list: link to the next rmap to be scanned in the rmap_list
  * @seqnr: count of completed full scans (needed when removing unstable node)
+ * @new_ksmpages_of_this_scanning: count of the new merged KSM pages in the
+ *		current scanning of mm_lists (cleared after ksm_do_scan() ends)
  *
  * There is only the one ksm_scan instance of this cursor structure.
  */
@@ -139,6 +141,7 @@ struct ksm_scan {
 	unsigned long address;
 	struct rmap_item **rmap_list;
 	unsigned long seqnr;
+	unsigned long new_ksmpages_of_this_scanning;
 };
 
 /**
@@ -277,6 +280,20 @@ static unsigned int zero_checksum __read_mostly;
 /* Whether to merge empty (zeroed) pages with actual zero pages */
 static bool ksm_use_zero_pages __read_mostly;
 
+/*
+ * Work in auto-mode.
+ * Maximum number of multiplicative factor of pages_to_scan.
+ */
+static unsigned int ksm_max_scanning_factor = 32;
+
+/*
+ * Work in auto-mode.
+ * The multiplicative factor of pages_to_scan.
+ * Real pages to scan equals to the product of scanning_factor
+ * and pages_to_scan
+ */
+static unsigned int scanning_factor = 1;
+
 #ifdef CONFIG_NUMA
 /* Zeroed when merging across nodes is not allowed */
 static unsigned int ksm_merge_across_nodes = 1;
@@ -2031,6 +2048,8 @@ static void stable_tree_append(struct rmap_item *rmap_item,
 	rmap_item->address |= STABLE_FLAG;
 	hlist_add_head(&rmap_item->hlist, &stable_node->hlist);
 
+	ksm_scan.new_ksmpages_of_this_scanning++;
+
 	if (rmap_item->hlist.next)
 		ksm_pages_sharing++;
 	else
@@ -2396,6 +2415,23 @@ static struct rmap_item *scan_get_next_rmap_item(struct page **page)
 	return NULL;
 }
 
+/*
+ * enhance_scanning_factor():
+ * double the values of scanning_factor, but not more than
+ * ksm_max_scanning_factor.
+ */
+static inline void enhance_scanning_factor(void)
+{
+	scanning_factor = scanning_factor << 1;
+	if (scanning_factor > ksm_max_scanning_factor)
+		scanning_factor = ksm_max_scanning_factor;
+}
+
+static inline void reset_scanning_factor(void)
+{
+	scanning_factor = 1;
+}
+
 /**
  * ksm_do_scan  - the ksm scanner main worker function.
  * @scan_npages:  number of pages we want to scan before we return.
@@ -2432,10 +2468,31 @@ static int ksm_scan_thread(void *nothing)
 	while (!kthread_should_stop()) {
 		mutex_lock(&ksm_thread_mutex);
 		wait_while_offlining();
-		if (ksmd_should_run())
-			ksm_do_scan(ksm_thread_pages_to_scan);
+		if (ksmd_should_run()) {
+			if (ksm_run & KSM_RUN_AUTO)
+				ksm_do_scan(ksm_thread_pages_to_scan * scanning_factor);
+			else
+				ksm_do_scan(ksm_thread_pages_to_scan);
+		}
 		mutex_unlock(&ksm_thread_mutex);
 
+		/*
+		 * If there are new ksm pages after scanning, then we
+		 * can enhance scanning_factor to improve ksm_thread's
+		 * pages_to_scan to speed up scanning. Otherwaise, we
+		 * reset scanning_factor to be one, so that to recover
+		 * the normal state because there is greater probability
+		 * of getting no new KsmPages in the next scanning.
+		 */
+		if (ksm_run & KSM_RUN_AUTO) {
+			if (ksm_scan.new_ksmpages_of_this_scanning > 0)
+				enhance_scanning_factor();
+			else
+				reset_scanning_factor();
+
+			ksm_scan.new_ksmpages_of_this_scanning = 0;
+		}
+
 		try_to_freeze();
 
 		if (ksmd_should_run()) {
@@ -2952,6 +3009,32 @@ static ssize_t run_store(struct kobject *kobj, struct kobj_attribute *attr,
 }
 KSM_ATTR(run);
 
+static ssize_t max_scanning_factor_show(struct kobject *kobj,
+						struct kobj_attribute *attr, char *buf)
+{
+	return sysfs_emit(buf, "%u\n", ksm_max_scanning_factor);
+}
+
+static ssize_t max_scanning_factor_store(struct kobject *kobj,
+								struct kobj_attribute *attr,
+								const char *buf, size_t count)
+{
+		unsigned int value;
+		int err;
+
+		err = kstrtouint(buf, 10, &value);
+		if (err)
+			return -EINVAL;
+
+		if (value < 1)
+			return -EINVAL;
+
+		ksm_max_scanning_factor = value;
+
+		return count;
+}
+KSM_ATTR(max_scanning_factor);
+
 #ifdef CONFIG_NUMA
 static ssize_t merge_across_nodes_show(struct kobject *kobj,
 				       struct kobj_attribute *attr, char *buf)
@@ -3162,6 +3245,7 @@ static struct attribute *ksm_attrs[] = {
 	&sleep_millisecs_attr.attr,
 	&pages_to_scan_attr.attr,
 	&run_attr.attr,
+	&max_scanning_factor_attr.attr,
 	&pages_shared_attr.attr,
 	&pages_sharing_attr.attr,
 	&pages_unshared_attr.attr,
-- 
2.25.1