[PATCH v2 0/4] Smart scanning mode for KSM

[PATCH v2 0/4] Smart scanning mode for KSM

[Stefan Roesch]

This patch series adds "smart scanning" for KSM.

What is smart scanning?
=======================
KSM evaluates all the candidate pages for each scan. It does not use historic
information from previous scans. This has the effect that candidate pages that
couldn't be used for KSM de-duplication continue to be evaluated for each scan.

The idea of "smart scanning" is to keep historic information. With the historic
information we can temporarily skip the candidate page for one or several scans.

Details:
========
"Smart scanning" is to keep two small counters to store if the page has been
used for KSM. One counter stores how often we already tried to use the page for
KSM and the other counter stores when a page will be used as a candidate page
again.

How often we skip the candidate page depends how often a page failed KSM
de-duplication. The code skips a maximum of 8 times. During testing this has
shown to be a good compromise for different workloads.

New sysfs knob:
===============
Smart scanning is not enabled by default. With /sys/kernel/mm/ksm/smart_scan
smart scanning can be enabled.

Monitoring:
===========
To monitor how effective smart scanning is a new sysfs knob has been introduced.
/sys/kernel/mm/pages_skipped report how many pages have been skipped by smart
scanning.

Results:
========
- Various workloads have shown a 20% - 25% reduction in page scans
  For the instagram workload for instance, the number of pages scanned has been
  reduced from over 20M pages per scan to less than 15M pages.
- Less pages scans also resulted in an overall higher de-duplication rate as
  some shorter lived pages could be de-duplicated additionally
- Less pages scanned allows to reduce the pages_to_scan parameter
  and this resulted in  a 25% reduction in terms of CPU.
- The improvements have been observed for workloads that enable KSM with
  madvise as well as prctl


Changes:
  - V2:
    - Renamed function inc_skip_age() to skip_age()
    - Added comment to skip_age() function
    - Renamed function skip_rmap_item() to should_skip_rmap_item()
    - Added more comments to should_skip_rmap_item function
    - Added explicit modification of age with overflow check



Stefan Roesch (4):
  mm/ksm: add "smart" page scanning mode
  mm/ksm: add pages_skipped metric
  mm/ksm: document smart scan mode
  mm/ksm: document pages_skipped sysfs knob

 Documentation/admin-guide/mm/ksm.rst |  11 +++
 mm/ksm.c                             | 120 +++++++++++++++++++++++++++
 2 files changed, 131 insertions(+)


base-commit: 15bcc9730fcd7526a3b92eff105d6701767a53bb
-- 
2.39.3

[PATCH v2 1/4] mm/ksm: add "smart" page scanning mode

[Stefan Roesch]

This change adds a "smart" page scanning mode for KSM. So far all the
candidate pages are continuously scanned to find candidates for
de-duplication. There are a considerably number of pages that cannot be
de-duplicated. This is costly in terms of CPU. By using smart scanning
considerable CPU savings can be achieved.

This change takes the history of scanning pages into account and skips
the page scanning of certain pages for a while if de-deduplication for
this page has not been successful in the past.

To do this it introduces two new fields in the ksm_rmap_item structure:
age and skip_age. age, is the KSM age and skip_age is the age for how
long page scanning of this page is skipped. The age field is incremented
each time the page is scanned and the page cannot be de-duplicated.

How often a page is skipped is dependent how often de-duplication has
been tried so far and the number of skips is currently limited to 8.
This value has shown to be effective with different workloads.

The feature is currently disable by default and can be enabled with the
new smart_scan knob.

The feature has shown to be very effective: upt to 25% of the page scans
can be eliminated; the pages_to_scan rate can be reduced by 40 - 50% and
a similar de-duplication rate can be maintained.

Signed-off-by: Stefan Roesch <shr@devkernel.io>
---
 mm/ksm.c | 108 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 108 insertions(+)

diff --git a/mm/ksm.c b/mm/ksm.c
index 981af9c72e7a..7a1aa3872cf4 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -56,6 +56,8 @@
 #define DO_NUMA(x)	do { } while (0)
 #endif
 
+typedef u8 rmap_age_t;
+
 /**
  * DOC: Overview
  *
@@ -193,6 +195,8 @@ struct ksm_stable_node {
  * @node: rb node of this rmap_item in the unstable tree
  * @head: pointer to stable_node heading this list in the stable tree
  * @hlist: link into hlist of rmap_items hanging off that stable_node
+ * @age: number of scan iterations since creation
+ * @skip_age: skip rmap item until age reaches skip_age
  */
 struct ksm_rmap_item {
 	struct ksm_rmap_item *rmap_list;
@@ -212,6 +216,8 @@ struct ksm_rmap_item {
 			struct hlist_node hlist;
 		};
 	};
+	rmap_age_t age;
+	rmap_age_t skip_age;
 };
 
 #define SEQNR_MASK	0x0ff	/* low bits of unstable tree seqnr */
@@ -281,6 +287,9 @@ 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;
 
+/* Skip pages that couldn't be de-duplicated previously  */
+static bool ksm_smart_scan;
+
 /* The number of zero pages which is placed by KSM */
 unsigned long ksm_zero_pages;
 
@@ -2305,6 +2314,78 @@ static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot,
 	return rmap_item;
 }
 
+/*
+ * Calculate skip age for the ksm page age. The age determines how often
+ * de-duplicating has already been tried unsuccessfully. If the age is
+ * smaller, the scanning of this page is skipped for less scans.
+ *
+ * @age: rmap_item age of page
+ */
+static unsigned int skip_age(rmap_age_t age)
+{
+	if (age <= 3)
+		return 1;
+	if (age <= 5)
+		return 2;
+	if (age <= 8)
+		return 4;
+
+	return 8;
+}
+
+/*
+ * Determines if a page should be skipped for the current scan.
+ *
+ * @page: page to check
+ * @rmap_item: associated rmap_item of page
+ */
+static bool should_skip_rmap_item(struct page *page,
+				  struct ksm_rmap_item *rmap_item)
+{
+	rmap_age_t age;
+
+	if (!ksm_smart_scan)
+		return false;
+
+	/*
+	 * Never skip pages that are already KSM; pages cmp_and_merge_page()
+	 * will essentially ignore them, but we still have to process them
+	 * properly.
+	 */
+	if (PageKsm(page))
+		return false;
+
+	/*
+	 * Smaller ages are not skipped, they need to get a chance to go
+	 * through the different phases of the KSM merging.
+	 */
+	age = rmap_item->age;
+	rmap_item->age = (rmap_item->age + 1) & 0xFF;
+
+	if (age < 3)
+		return false;
+
+	/*
+	 * Page has been skipped and reached its target age to re-enable
+	 * scanning the page.
+	 */
+	if (rmap_item->skip_age == age) {
+		rmap_item->skip_age = 0;
+		return false;
+	}
+
+	/*
+	 * Skip the page and calculate skip_age on when to re-enable scanning
+	 * for this page.
+	 */
+	if (rmap_item->skip_age == 0) {
+		rmap_item->skip_age = (age + skip_age(age)) & 0xFF;
+		remove_rmap_item_from_tree(rmap_item);
+	}
+
+	return true;
+}
+
 static struct ksm_rmap_item *scan_get_next_rmap_item(struct page **page)
 {
 	struct mm_struct *mm;
@@ -2409,6 +2490,10 @@ static struct ksm_rmap_item *scan_get_next_rmap_item(struct page **page)
 				if (rmap_item) {
 					ksm_scan.rmap_list =
 							&rmap_item->rmap_list;
+
+					if (should_skip_rmap_item(*page, rmap_item))
+						goto next_page;
+
 					ksm_scan.address += PAGE_SIZE;
 				} else
 					put_page(*page);
@@ -3449,6 +3534,28 @@ static ssize_t full_scans_show(struct kobject *kobj,
 }
 KSM_ATTR_RO(full_scans);
 
+static ssize_t smart_scan_show(struct kobject *kobj,
+			       struct kobj_attribute *attr, char *buf)
+{
+	return sysfs_emit(buf, "%u\n", ksm_smart_scan);
+}
+
+static ssize_t smart_scan_store(struct kobject *kobj,
+				struct kobj_attribute *attr,
+				const char *buf, size_t count)
+{
+	int err;
+	bool value;
+
+	err = kstrtobool(buf, &value);
+	if (err)
+		return -EINVAL;
+
+	ksm_smart_scan = value;
+	return count;
+}
+KSM_ATTR(smart_scan);
+
 static struct attribute *ksm_attrs[] = {
 	&sleep_millisecs_attr.attr,
 	&pages_to_scan_attr.attr,
@@ -3469,6 +3576,7 @@ static struct attribute *ksm_attrs[] = {
 	&stable_node_chains_prune_millisecs_attr.attr,
 	&use_zero_pages_attr.attr,
 	&general_profit_attr.attr,
+	&smart_scan_attr.attr,
 	NULL,
 };
 
-- 
2.39.3

[PATCH v2 2/4] mm/ksm: add pages_skipped metric

[Stefan Roesch]

This change adds the "pages skipped" metric. To be able to evaluate how
successful smart page scanning is, the pages skipped metric can be
compared to the pages scanned metric.

The pages skipped metric is a cumulative counter. The counter is stored
under /sys/kernel/mm/ksm/pages_skipped.

Signed-off-by: Stefan Roesch <shr@devkernel.io>
Reviewed-by: David Hildenbrand <david@redhat.com>
---
 mm/ksm.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/mm/ksm.c b/mm/ksm.c
index 7a1aa3872cf4..7fbf22814c8d 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -293,6 +293,9 @@ static bool ksm_smart_scan;
 /* The number of zero pages which is placed by KSM */
 unsigned long ksm_zero_pages;
 
+/* The number of pages that have been skipped due to "smart scanning" */
+static unsigned long ksm_pages_skipped;
+
 #ifdef CONFIG_NUMA
 /* Zeroed when merging across nodes is not allowed */
 static unsigned int ksm_merge_across_nodes = 1;
@@ -2378,6 +2381,7 @@ static bool should_skip_rmap_item(struct page *page,
 	 * Skip the page and calculate skip_age on when to re-enable scanning
 	 * for this page.
 	 */
+	++ksm_pages_skipped;
 	if (rmap_item->skip_age == 0) {
 		rmap_item->skip_age = (age + skip_age(age)) & 0xFF;
 		remove_rmap_item_from_tree(rmap_item);
@@ -3468,6 +3472,13 @@ static ssize_t pages_volatile_show(struct kobject *kobj,
 }
 KSM_ATTR_RO(pages_volatile);
 
+static ssize_t pages_skipped_show(struct kobject *kobj,
+				  struct kobj_attribute *attr, char *buf)
+{
+	return sysfs_emit(buf, "%lu\n", ksm_pages_skipped);
+}
+KSM_ATTR_RO(pages_skipped);
+
 static ssize_t ksm_zero_pages_show(struct kobject *kobj,
 				struct kobj_attribute *attr, char *buf)
 {
@@ -3565,6 +3576,7 @@ static struct attribute *ksm_attrs[] = {
 	&pages_sharing_attr.attr,
 	&pages_unshared_attr.attr,
 	&pages_volatile_attr.attr,
+	&pages_skipped_attr.attr,
 	&ksm_zero_pages_attr.attr,
 	&full_scans_attr.attr,
 #ifdef CONFIG_NUMA
-- 
2.39.3

[PATCH v2 3/4] mm/ksm: document smart scan mode

[Stefan Roesch]

This adds documentation for the smart scan mode of KSM.

Signed-off-by: Stefan Roesch <shr@devkernel.io>
Reviewed-by: David Hildenbrand <david@redhat.com>
---
 Documentation/admin-guide/mm/ksm.rst | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/Documentation/admin-guide/mm/ksm.rst b/Documentation/admin-guide/mm/ksm.rst
index 776f244bdae4..1762219baf51 100644
--- a/Documentation/admin-guide/mm/ksm.rst
+++ b/Documentation/admin-guide/mm/ksm.rst
@@ -155,6 +155,15 @@ stable_node_chains_prune_millisecs
         scan. It's a noop if not a single KSM page hit the
         ``max_page_sharing`` yet.
 
+smart_scan
+        By default KSM checks every candidate page for each scan. It does
+        not take into account historic information. When smart scan is
+        enabled, pages that have previously not been de-duplicated get
+        skipped. How often these pages are skipped depends on how often
+        de-duplication has already been tried and failed. By default this
+        optimization is disabled. The ``pages_skipped`` metric shows how
+        effetive the setting is.
+
 The effectiveness of KSM and MADV_MERGEABLE is shown in ``/sys/kernel/mm/ksm/``:
 
 general_profit
-- 
2.39.3

[PATCH v2 4/4] mm/ksm: document pages_skipped sysfs knob

[Stefan Roesch]

This adds documentation for the new metric pages_skipped.

Signed-off-by: Stefan Roesch <shr@devkernel.io>
Reviewed-by: David Hildenbrand <david@redhat.com>
---
 Documentation/admin-guide/mm/ksm.rst | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/Documentation/admin-guide/mm/ksm.rst b/Documentation/admin-guide/mm/ksm.rst
index 1762219baf51..27d949250b67 100644
--- a/Documentation/admin-guide/mm/ksm.rst
+++ b/Documentation/admin-guide/mm/ksm.rst
@@ -178,6 +178,8 @@ pages_unshared
         how many pages unique but repeatedly checked for merging
 pages_volatile
         how many pages changing too fast to be placed in a tree
+pages_skipped
+        how many pages did the "smart" page scanning algorithm skip
 full_scans
         how many times all mergeable areas have been scanned
 stable_node_chains
-- 
2.39.3

Re: [PATCH v2 1/4] mm/ksm: add "smart" page scanning mode

[David Hildenbrand]

> +typedef u8 rmap_age_t;
> +
>   /**
>    * DOC: Overview
>    *
> @@ -193,6 +195,8 @@ struct ksm_stable_node {
>    * @node: rb node of this rmap_item in the unstable tree
>    * @head: pointer to stable_node heading this list in the stable tree
>    * @hlist: link into hlist of rmap_items hanging off that stable_node
> + * @age: number of scan iterations since creation
> + * @skip_age: skip rmap item until age reaches skip_age
>    */
>   struct ksm_rmap_item {
>   	struct ksm_rmap_item *rmap_list;
> @@ -212,6 +216,8 @@ struct ksm_rmap_item {
>   			struct hlist_node hlist;
>   		};
>   	};
> +	rmap_age_t age;
> +	rmap_age_t skip_age;

I *think* of you move that after "oldchecksum", the size of the struct 
might not necessarily increase.

[...]

>   
> +/*
> + * Calculate skip age for the ksm page age. The age determines how often
> + * de-duplicating has already been tried unsuccessfully. If the age is
> + * smaller, the scanning of this page is skipped for less scans.
> + *
> + * @age: rmap_item age of page
> + */
> +static unsigned int skip_age(rmap_age_t age)
> +{
> +	if (age <= 3)
> +		return 1;
> +	if (age <= 5)
> +		return 2;
> +	if (age <= 8)
> +		return 4;
> +
> +	return 8;
> +}
> +
> +/*
> + * Determines if a page should be skipped for the current scan.
> + *
> + * @page: page to check
> + * @rmap_item: associated rmap_item of page
> + */
> +static bool should_skip_rmap_item(struct page *page,
> +				  struct ksm_rmap_item *rmap_item)
> +{
> +	rmap_age_t age;
> +
> +	if (!ksm_smart_scan)
> +		return false;
> +
> +	/*
> +	 * Never skip pages that are already KSM; pages cmp_and_merge_page()
> +	 * will essentially ignore them, but we still have to process them
> +	 * properly.
> +	 */
> +	if (PageKsm(page))
> +		return false;
> +
> +	/*
> +	 * Smaller ages are not skipped, they need to get a chance to go
> +	 * through the different phases of the KSM merging.
> +	 */

Sorry, had to set some time aside to think this through. Wouldn't it be 
cleaner to just not rely on this overflow?

Instead, we could track the page age (which we would freeze at U8_MAX) 
and simply track how much more often we are allowed to skip.

Something like the following (which, I am sure, is completely broken, 
but should express what I have in mind)



age = rmap_item->age;
if (age != U8_MAX)
	rmap_item->age++;

/*
  * Smaller ages are not skipped, they need to get a chance to go
  * through the different phases of the KSM merging.
  */
if (age < 3)
	return false;

/*
  * Are we still allowed to skip? If not, then don't skip it
  * and determine how much more often we are allowed to skip next.
  */
if (!rmap_item->remaining_skips) {
	rmap_item->remaining_skips = skip_age(age);
	return false;
}

/* Skip this page. */
rmap_item->remaining_skips--;
remove_rmap_item_from_tree(rmap_item);
return true;



Would that miss anything important? Was the overflow handling (and 
scanning more often one we overflow again IIUC) important?

-- 
Cheers,

David / dhildenb

Re: [PATCH v2 1/4] mm/ksm: add "smart" page scanning mode

[Stefan Roesch]

David Hildenbrand <david@redhat.com> writes:

>> +typedef u8 rmap_age_t;
>> +
>>   /**
>>    * DOC: Overview
>>    *
>> @@ -193,6 +195,8 @@ struct ksm_stable_node {
>>    * @node: rb node of this rmap_item in the unstable tree
>>    * @head: pointer to stable_node heading this list in the stable tree
>>    * @hlist: link into hlist of rmap_items hanging off that stable_node
>> + * @age: number of scan iterations since creation
>> + * @skip_age: skip rmap item until age reaches skip_age
>>    */
>>   struct ksm_rmap_item {
>>   	struct ksm_rmap_item *rmap_list;
>> @@ -212,6 +216,8 @@ struct ksm_rmap_item {
>>   			struct hlist_node hlist;
>>   		};
>>   	};
>> +	rmap_age_t age;
>> +	rmap_age_t skip_age;
>
> I *think* of you move that after "oldchecksum", the size of the struct might not
> necessarily increase.
>
> [...]
>
>>   +/*
>> + * Calculate skip age for the ksm page age. The age determines how often
>> + * de-duplicating has already been tried unsuccessfully. If the age is
>> + * smaller, the scanning of this page is skipped for less scans.
>> + *
>> + * @age: rmap_item age of page
>> + */
>> +static unsigned int skip_age(rmap_age_t age)
>> +{
>> +	if (age <= 3)
>> +		return 1;
>> +	if (age <= 5)
>> +		return 2;
>> +	if (age <= 8)
>> +		return 4;
>> +
>> +	return 8;
>> +}
>> +
>> +/*
>> + * Determines if a page should be skipped for the current scan.
>> + *
>> + * @page: page to check
>> + * @rmap_item: associated rmap_item of page
>> + */
>> +static bool should_skip_rmap_item(struct page *page,
>> +				  struct ksm_rmap_item *rmap_item)
>> +{
>> +	rmap_age_t age;
>> +
>> +	if (!ksm_smart_scan)
>> +		return false;
>> +
>> +	/*
>> +	 * Never skip pages that are already KSM; pages cmp_and_merge_page()
>> +	 * will essentially ignore them, but we still have to process them
>> +	 * properly.
>> +	 */
>> +	if (PageKsm(page))
>> +		return false;
>> +
>> +	/*
>> +	 * Smaller ages are not skipped, they need to get a chance to go
>> +	 * through the different phases of the KSM merging.
>> +	 */
>
> Sorry, had to set some time aside to think this through. Wouldn't it be cleaner
> to just not rely on this overflow?
>
> Instead, we could track the page age (which we would freeze at U8_MAX) and
> simply track how much more often we are allowed to skip.
>
> Something like the following (which, I am sure, is completely broken, but should
> express what I have in mind)
>
>
>
> age = rmap_item->age;
> if (age != U8_MAX)
> 	rmap_item->age++;
>
> /*
>  * Smaller ages are not skipped, they need to get a chance to go
>  * through the different phases of the KSM merging.
>  */
> if (age < 3)
> 	return false;
>
> /*
>  * Are we still allowed to skip? If not, then don't skip it
>  * and determine how much more often we are allowed to skip next.
>  */
> if (!rmap_item->remaining_skips) {
> 	rmap_item->remaining_skips = skip_age(age);
> 	return false;
> }
>
> /* Skip this page. */
> rmap_item->remaining_skips--;
> remove_rmap_item_from_tree(rmap_item);
> return true;
>
>
>
> Would that miss anything important? Was the overflow handling (and scanning more
> often one we overflow again IIUC) important?
>

That sounds reasonable. I'll incorporate the two suggestions in the next version.