[PATCH v2 2/5] ksm: implement scan-enhanced algorithm

[cgel . zte]

From: xu xin <xu.xin16@xxxxxxxxxx>

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@xxxxxxxxx>
Signed-off-by: xu xin <xu.xin16@xxxxxxxxxx>
---
 mm/ksm.c | 100 +++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 98 insertions(+), 2 deletions(-)

diff --git a/mm/ksm.c b/mm/ksm.c
index c80d908221a4..f416f168a6da 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -131,6 +131,10 @@ 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: count of the new merged KSM pages in the current scanning
+ *	              of mm_lists (cleared after every turn of ksm_do_scan() ends)
+ * @prev_ksmpages: the record of the new merged KSM pages in the last turn of
+ *	               scanning by ksm_do_scan().
  *
  * There is only the one ksm_scan instance of this cursor structure.
  */
@@ -139,6 +143,8 @@ struct ksm_scan {
 	unsigned long address;
 	struct rmap_item **rmap_list;
 	unsigned long seqnr;
+	unsigned long new_ksmpages;
+	unsigned long prev_ksmpages;
 };
 
 /**
@@ -277,6 +283,19 @@ 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.
+ * The multiplicative factor of pages_to_scan.
+ * Real pages to scan equals to the product of scanning_factor
+ * and pages_to_scan
+ */
+#define INIT_SCANNING_FACTOR	1
+static unsigned int scanning_factor = INIT_SCANNING_FACTOR;
+
+/* The upper limit of scanning_factor */
+#define DEFAULT_MAX_SCANNING_FACTOR	16
+static unsigned int max_scanning_factor	= DEFAULT_MAX_SCANNING_FACTOR;
+
 #ifdef CONFIG_NUMA
 /* Zeroed when merging across nodes is not allowed */
 static unsigned int ksm_merge_across_nodes = 1;
@@ -2031,6 +2050,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++;
+
 	if (rmap_item->hlist.next)
 		ksm_pages_sharing++;
 	else
@@ -2422,6 +2443,41 @@ static int ksmd_should_run(void)
 	return 0;
 }
 
+/*
+ * Work in auto mode, the scan-enhanced algorithm.
+ * current_factor: the current scanning_factor.
+ * return: the scanning_factor caculated by scan-enhanced algorithm.
+ */
+static unsigned int scan_enhanced_algorithm(unsigned int current_factor)
+{
+	unsigned int next_factor;
+	unsigned int max, min;
+
+	/*
+	 * The calculation is divied into three cases as follows:
+	 *
+	 * Case 1: when new_ksmpages > prev_ksmpages * 1/2, get the
+	 *         next factor by double the current factor.
+	 * Case 2: when 0 < new_ksmpages < prev_ksmpages * 1/2, keep
+	 *         the factor unchanged.
+	 * Case 3: when new_ksmpages equals 0, then get the next
+	 *         factor by halfing the current factor.
+	 */
+	max = READ_ONCE(max_scanning_factor);
+	min = INIT_SCANNING_FACTOR;
+	if (ksm_scan.new_ksmpages * 2 > ksm_scan.prev_ksmpages) {
+		next_factor = current_factor << 1; /* Doubling */
+		if (next_factor > max)
+			next_factor = max;
+	} else if (ksm_scan.new_ksmpages == 0) {
+		next_factor = current_factor >> 1; /* Halfing */
+		next_factor = next_factor < min ? min : next_factor;
+	} else
+		next_factor = current_factor;
+
+	return next_factor;
+}
+
 static int ksm_scan_thread(void *nothing)
 {
 	unsigned int sleep_ms;
@@ -2432,8 +2488,19 @@ 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);
+
+				scanning_factor = scan_enhanced_algorithm(scanning_factor);
+				/*
+				 * Reset ksm_scan.new_ksmpages after
+				 * updating scanning_factor by scan_enhanced_algorithm.
+				 */
+				ksm_scan.new_ksmpages = 0;
+			} else
+				ksm_do_scan(ksm_thread_pages_to_scan);
+		}
 		mutex_unlock(&ksm_thread_mutex);
 
 		try_to_freeze();
@@ -2904,6 +2971,34 @@ static ssize_t pages_to_scan_store(struct kobject *kobj,
 }
 KSM_ATTR(pages_to_scan);
 
+static ssize_t max_scanning_factor_show(struct kobject *kobj,
+						struct kobj_attribute *attr, char *buf)
+{
+	return sysfs_emit(buf, "%u\n", 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, max;
+		int err;
+
+		err = kstrtouint(buf, 10, &value);
+		if (err)
+			return -EINVAL;
+
+		max = totalram_pages() / ksm_thread_pages_to_scan;
+
+		if (value < 1 && value > max)
+			return -EINVAL;
+
+		max_scanning_factor = value;
+
+		return count;
+}
+KSM_ATTR(max_scanning_factor);
+
 static ssize_t run_show(struct kobject *kobj, struct kobj_attribute *attr,
 			char *buf)
 {
@@ -3161,6 +3256,7 @@ KSM_ATTR_RO(full_scans);
 static struct attribute *ksm_attrs[] = {
 	&sleep_millisecs_attr.attr,
 	&pages_to_scan_attr.attr,
+	&max_scanning_factor_attr.attr,
 	&run_attr.attr,
 	&pages_shared_attr.attr,
 	&pages_sharing_attr.attr,
-- 
2.25.1