Skip to contentSkip to conversation

Smart scanning mode for KSM

PATCH Superseded Stefan Roesch 3 participants 14 messages Sep 12, 2023 – Sep 18, 2023

Subsystems (4)

v1 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

cover Smart scanning mode for KSM

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

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                             | 87 ++++++++++++++++++++++++++++
 2 files changed, 98 insertions(+)

base-commit: 15bcc9730fcd7526a3b92eff105d6701767a53bb

Signature · 1 line
2.39.3
#1 lore raw

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

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_page 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.

---
 mm/ksm.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 75 insertions(+)
mm/ksm.c +75 -0
index 981af9c72e7a..bfd5087c7d5a 100644
@@ -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,45 @@ static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot,
 	return rmap_item;
 }
 
+static unsigned int inc_skip_age(rmap_age_t age)
+{
+	if (age <= 3)
+		return 1;
+	if (age <= 5)
+		return 2;
+	if (age <= 8)
+		return 4;
+
+	return 8;
+}
+
+static bool skip_rmap_item(struct page *page, struct ksm_rmap_item *rmap_item)
+{
+	rmap_age_t age;
+
+	if (!ksm_smart_scan)
+		return false;
+
+	if (PageKsm(page))
+		return false;
+
+	age = rmap_item->age++;
+	if (age < 3)
+		return false;
+
+	if (rmap_item->skip_age == age) {
+		rmap_item->skip_age = 0;
+		return false;
+	}
+
+	if (rmap_item->skip_age == 0) {
+		rmap_item->skip_age = age + inc_skip_age(age);
+		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 +2457,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 (skip_rmap_item(*page, rmap_item))
+						goto next_page;
+
 					ksm_scan.address += PAGE_SIZE;
 				} else
 					put_page(*page);
@@ -3449,6 +3501,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 +3543,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,
 };
 
Signature · 1 line
2.39.3
maintainer
#2 lore raw

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

Quoted 6 lines · On Tue, 12 Sep 2023 10:52:25 -0700 Stefan Roesch <[email protected]> wrote:

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.

Quoted 6 lines

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_page is the age for how

s/skip_page/skip_age/

Quoted 7 lines

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.

Quoted 7 lines

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.

All seems nice. I'll sit out v1, see what people have to say.

Some nits:

Quoted 10 lines
mm/ksm.c +1 -0
 
...
@@ -2305,6 +2314,45 @@ static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot,
 	return rmap_item;
 }
 
+static unsigned int inc_skip_age(rmap_age_t age)

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2327

Quoted 10 lines
mm/ksm.c +10 -0
+{
+	if (age <= 3)
+		return 1;
+	if (age <= 5)
+		return 2;
+	if (age <= 8)
+		return 4;
+
+	return 8;
+}

"inc_skip_age" sounds like it increments something. Can we give it a better name?

And a nice comment explaining its role in life.

Quoted 16 lines
mm/ksm.c +16 -0
+static bool skip_rmap_item(struct page *page, struct ksm_rmap_item *rmap_item)
+{
+	rmap_age_t age;
+
+	if (!ksm_smart_scan)
+		return false;
+
+	if (PageKsm(page))
+		return false;
+
+	age = rmap_item->age++;
+	if (age < 3)
+		return false;
+
+	if (rmap_item->skip_age == age) {
+		rmap_item->skip_age = 0;

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2354

Quoted 10 lines
mm/ksm.c +10 -0
+		return false;
+	}
+
+	if (rmap_item->skip_age == 0) {
+		rmap_item->skip_age = age + inc_skip_age(age);
+		remove_rmap_item_from_tree(rmap_item);
+	}
+
+	return true;
+}

Would a better name be should_skip_rmap_item()?

But even that name implies that the function is idempotent (has no side-effects). Again, an explanatory comment would be good. And simple comments over each non-obvious `if' statement.

Quoted 3 lines

...

#3 lore raw

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

Quoted 8 lines · Andrew Morton
Quoted 6 lines · On Tue, 12 Sep 2023 10:52:25 -0700 Stefan Roesch <[email protected]> wrote:

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.

Quoted 9 lines
Quoted 6 lines

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_page is the age for how

s/skip_page/skip_age/

Fixed in the next version.

Quoted 43 lines
Quoted 7 lines

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.

Quoted 7 lines

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.

All seems nice. I'll sit out v1, see what people have to say.

Some nits:

Quoted 10 lines
mm/ksm.c +1 -0
 
...
@@ -2305,6 +2314,45 @@ static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot,
 	return rmap_item;
 }
 
+static unsigned int inc_skip_age(rmap_age_t age)

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2327

Quoted 10 lines
mm/ksm.c +10 -0
+{
+	if (age <= 3)
+		return 1;
+	if (age <= 5)
+		return 2;
+	if (age <= 8)
+		return 4;
+
+	return 8;
+}

"inc_skip_age" sounds like it increments something. Can we give it a better name?

Quoted 2 lines

And a nice comment explaining its role in life.

Renamed it to skip_age in the next version and added a comment.

Quoted 20 lines
Quoted 20 lines
mm/ksm.c +20 -0
+static bool skip_rmap_item(struct page *page, struct ksm_rmap_item *rmap_item)
+{
+	rmap_age_t age;
+
+	if (!ksm_smart_scan)
+		return false;
+
+	if (PageKsm(page))
+		return false;
+
+	age = rmap_item->age++;
+	if (age < 3)
+		return false;
+
+	if (rmap_item->skip_age == age) {
+		rmap_item->skip_age = 0;
+		return false;
+	}
+
+	if (rmap_item->skip_age == 0) {
Quoted 9 lines

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2354

Quoted 6 lines
mm/ksm.c +6 -0
+		rmap_item->skip_age = age + inc_skip_age(age);
+		remove_rmap_item_from_tree(rmap_item);
+	}
+
+	return true;
+}

Would a better name be should_skip_rmap_item()?

Renamed it to should_skip_rmap_item().

Quoted 4 lines

But even that name implies that the function is idempotent (has no side-effects). Again, an explanatory comment would be good. And simple comments over each non-obvious `if' statement.

Added more comments to the function to explain the different cases.

Quoted 3 lines
Quoted 3 lines

...

#4 lore raw

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

In reply to Stefan Roesch
Quoted 87 lines · 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_page 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.

---
  mm/ksm.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
  1 file changed, 75 insertions(+)
mm/ksm.c +20 -0
index 981af9c72e7a..bfd5087c7d5a 100644
@@ -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,45 @@ static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot,
  	return rmap_item;
  }
 
+static unsigned int inc_skip_age(rmap_age_t age)
+{
+	if (age <= 3)
+		return 1;
+	if (age <= 5)
+		return 2;
+	if (age <= 8)
+		return 4;
+
+	return 8;
+}

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2337

Quoted 10 lines
mm/ksm.c +10 -0
+
+static bool skip_rmap_item(struct page *page, struct ksm_rmap_item *rmap_item)
+{
+	rmap_age_t age;
+
+	if (!ksm_smart_scan)
+		return false;
+
+	if (PageKsm(page))
+		return false;

I'm a bit confused about this check here. scan_get_next_rmap_item() would return a PageKsm() page and call cmp_and_merge_page().

cmp_and_merge_page() says: "first see if page can be merged into the stable tree"

... but shouldn't a PageKsm page *already* be in the stable tree?

Maybe that's what cmp_and_merge_page() does via:

	kpage = stable_tree_search(page);
	if (kpage == page && rmap_item->head == stable_node) {
		put_page(kpage);
		return;
	}

Hoping you can enlighten me :)

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2339

Quoted 2 lines
mm/ksm.c +2 -0
+
+	age = rmap_item->age++;

Can't we overflow here? Is that desired, or would you want to stop at the maximum you can store?

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2349

Quoted 10 lines
mm/ksm.c +10 -0
+	if (age < 3)
+		return false;
+
+	if (rmap_item->skip_age == age) {
+		rmap_item->skip_age = 0;
+		return false;
+	}
+
+	if (rmap_item->skip_age == 0) {
+		rmap_item->skip_age = age + inc_skip_age(age);

Can't you overflow here as well?

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2350

Quoted 1 line
mm/ksm.c +1 -0
+		remove_rmap_item_from_tree(rmap_item);

Can you enlighten me why that is required?

Quoted 5 lines
mm/ksm.c +5 -0
+	}
+
+	return true;
+}
+
Signature · 3 lines
Cheers,

David / dhildenb
#5 lore raw

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

Quoted 99 lines · David Hildenbrand
Quoted 76 lines · 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_page 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.

---
  mm/ksm.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
  1 file changed, 75 insertions(+)
mm/ksm.c +7 -0
index 981af9c72e7a..bfd5087c7d5a 100644
@@ -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,45 @@ static struct ksm_rmap_item

*get_next_rmap_item(struct ksm_mm_slot *mm_slot,
return rmap_item;
}
+static unsigned int inc_skip_age(rmap_age_t age)

mm/ksm.c +10 -0
+{
+	if (age <= 3)
+		return 1;
+	if (age <= 5)
+		return 2;
+	if (age <= 8)
+		return 4;
+
+	return 8;
+}

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2337

Quoted 10 lines
mm/ksm.c +10 -0
+
+static bool skip_rmap_item(struct page *page, struct ksm_rmap_item *rmap_item)
+{
+	rmap_age_t age;
+
+	if (!ksm_smart_scan)
+		return false;
+
+	if (PageKsm(page))
+		return false;

I'm a bit confused about this check here. scan_get_next_rmap_item() would return a PageKsm() page and call cmp_and_merge_page().

cmp_and_merge_page() says: "first see if page can be merged into the stable tree"

... but shouldn't a PageKsm page *already* be in the stable tree?

Maybe that's what cmp_and_merge_page() does via:

Quoted 9 lines
	kpage = stable_tree_search(page);
	if (kpage == page && rmap_item->head == stable_node) {
		put_page(kpage);
		return;
	}

Hoping you can enlighten me :)

The above description sounds correct. During each scan we go through all the candidate pages and this includes rmap_items that maps to KSM pages. The above check simply skips these pages.

Quoted 6 lines

mm/ksm.c

Quoted 2 lines
mm/ksm.c +2 -0
+
+	age = rmap_item->age++;

Can't we overflow here? Is that desired, or would you want to stop at the maximum you can store?

Yes, we can overflow here and it was a deliberate choice. If we overflow after we tried unsuccessfully for 255 times, we re-start with shorter skip values, but that should be fine. In return we avoid an if statement. The age is defined as unsigned.

Quoted 4 lines
Quoted 4 lines
mm/ksm.c +4 -0
+	if (age < 3)
+		return false;
+
+	if (rmap_item->skip_age == age) {
Quoted 9 lines

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2349

Quoted 6 lines
mm/ksm.c +6 -0
+		rmap_item->skip_age = 0;
+		return false;
+	}
+
+	if (rmap_item->skip_age == 0) {
+		rmap_item->skip_age = age + inc_skip_age(age);

Can't you overflow here as well?

Yes, you can. See the above discussion. This skip_age is also an unsigned value.

Quoted 5 lines

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2350

Quoted 1 line
mm/ksm.c +1 -0
+		remove_rmap_item_from_tree(rmap_item);

Can you enlighten me why that is required?

This is required for age calculation and BUG_ON check in remove_rmap_item_from_tree. If we don't call remove_rmap_item_from_tree, we will hit the BUG_ON for the skipped pages later on.

Quoted 5 lines
Quoted 5 lines
mm/ksm.c +5 -0
+	}
+
+	return true;
+}
+
#6 lore raw

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

Quoted 109 lines · Stefan Roesch
Quoted 106 lines · David Hildenbrand
Quoted 76 lines · 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_page 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.

---
   mm/ksm.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   1 file changed, 75 insertions(+)
mm/ksm.c +7 -0
index 981af9c72e7a..bfd5087c7d5a 100644
@@ -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,45 @@ static struct ksm_rmap_item

*get_next_rmap_item(struct ksm_mm_slot *mm_slot,
return rmap_item;
}
+static unsigned int inc_skip_age(rmap_age_t age)

mm/ksm.c +10 -0
+{
+	if (age <= 3)
+		return 1;
+	if (age <= 5)
+		return 2;
+	if (age <= 8)
+		return 4;
+
+	return 8;
+}

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2337

Quoted 10 lines
mm/ksm.c +10 -0
+
+static bool skip_rmap_item(struct page *page, struct ksm_rmap_item *rmap_item)
+{
+	rmap_age_t age;
+
+	if (!ksm_smart_scan)
+		return false;
+
+	if (PageKsm(page))
+		return false;

I'm a bit confused about this check here. scan_get_next_rmap_item() would return a PageKsm() page and call cmp_and_merge_page().

cmp_and_merge_page() says: "first see if page can be merged into the stable tree"

... but shouldn't a PageKsm page *already* be in the stable tree?

Maybe that's what cmp_and_merge_page() does via:

	kpage = stable_tree_search(page);
	if (kpage == page && rmap_item->head == stable_node) {
		put_page(kpage);
		return;
	}
Quoted 6 lines
Quoted 2 lines

Hoping you can enlighten me :)

The above description sounds correct. During each scan we go through all the candidate pages and this includes rmap_items that maps to KSM pages. The above check simply skips these pages.

Can we add a comment why we don't skip them? Like

/*
* Never skip pages that are already KSM; pages cmp_and_merge_page()
* will essentially ignore them, but we still have to process them
* properly.
*/

Quoted 8 lines
Quoted 7 lines

mm/ksm.c

Quoted 3 lines
mm/ksm.c +2 -0
+
+	age = rmap_item->age++;

Can't we overflow here? Is that desired, or would you want to stop at the maximum you can store?

Quoted 4 lines

Yes, we can overflow here and it was a deliberate choice. If we overflow after we tried unsuccessfully for 255 times, we re-start with shorter skip values, but that should be fine. In return we avoid an if statement. The age is defined as unsigned.

Can we make that explicit instead? Dealing with implicit overflows really makes the code harder to grasp.

Quoted 15 lines
Quoted 14 lines

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2349

Quoted 11 lines
mm/ksm.c +10 -0
+	if (age < 3)
+		return false;
+
+	if (rmap_item->skip_age == age) {
+		rmap_item->skip_age = 0;
+		return false;
+	}
+
+	if (rmap_item->skip_age == 0) {
+		rmap_item->skip_age = age + inc_skip_age(age);

Can't you overflow here as well?

Quoted 2 lines

Yes, you can. See the above discussion. This skip_age is also an unsigned value.

Dito.

Quoted 10 lines
Quoted 6 lines

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2350

Quoted 2 lines
mm/ksm.c +1 -0
+		remove_rmap_item_from_tree(rmap_item);

Can you enlighten me why that is required?

This is required for age calculation and BUG_ON check in remove_rmap_item_from_tree. If we don't call remove_rmap_item_from_tree, we will hit the BUG_ON for the skipped pages later on.

I see, thanks!

Signature · 3 lines
Cheers,

David / dhildenb
#7 lore raw

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

Quoted 115 lines · David Hildenbrand
Quoted 108 lines · Stefan Roesch
Quoted 106 lines · David Hildenbrand
Quoted 76 lines · 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_page 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.

---
   mm/ksm.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   1 file changed, 75 insertions(+)
mm/ksm.c +7 -0
index 981af9c72e7a..bfd5087c7d5a 100644
@@ -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,45 @@ static struct ksm_rmap_item

*get_next_rmap_item(struct ksm_mm_slot *mm_slot,
return rmap_item;
}
+static unsigned int inc_skip_age(rmap_age_t age)

mm/ksm.c +10 -0
+{
+	if (age <= 3)
+		return 1;
+	if (age <= 5)
+		return 2;
+	if (age <= 8)
+		return 4;
+
+	return 8;
+}

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2337

Quoted 10 lines
mm/ksm.c +10 -0
+
+static bool skip_rmap_item(struct page *page, struct ksm_rmap_item *rmap_item)
+{
+	rmap_age_t age;
+
+	if (!ksm_smart_scan)
+		return false;
+
+	if (PageKsm(page))
+		return false;

I'm a bit confused about this check here. scan_get_next_rmap_item() would return a PageKsm() page and call cmp_and_merge_page().

cmp_and_merge_page() says: "first see if page can be merged into the stable tree"

... but shouldn't a PageKsm page *already* be in the stable tree?

Maybe that's what cmp_and_merge_page() does via:

	kpage = stable_tree_search(page);
	if (kpage == page && rmap_item->head == stable_node) {
		put_page(kpage);
		return;
	}
Quoted 5 lines
Quoted 2 lines

Hoping you can enlighten me :)

The above description sounds correct. During each scan we go through all the candidate pages and this includes rmap_items that maps to KSM pages. The above check simply skips these pages.

Quoted 8 lines

Can we add a comment why we don't skip them? Like

/*
* Never skip pages that are already KSM; pages cmp_and_merge_page()
* will essentially ignore them, but we still have to process them
* properly.
*/

I'll add the comment in the next version.

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

mm/ksm.c

Quoted 3 lines
mm/ksm.c +2 -0
+
+	age = rmap_item->age++;

Can't we overflow here? Is that desired, or would you want to stop at the maximum you can store?

Quoted 8 lines
Quoted 4 lines

Yes, we can overflow here and it was a deliberate choice. If we overflow after we tried unsuccessfully for 255 times, we re-start with shorter skip values, but that should be fine. In return we avoid an if statement. The age is defined as unsigned.

Can we make that explicit instead? Dealing with implicit overflows really makes the code harder to grasp.

I'll make it explicit.

Quoted 14 lines
Quoted 14 lines
Quoted 14 lines

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2349

Quoted 11 lines
mm/ksm.c +10 -0
+	if (age < 3)
+		return false;
+
+	if (rmap_item->skip_age == age) {
+		rmap_item->skip_age = 0;
+		return false;
+	}
+
+	if (rmap_item->skip_age == 0) {
+		rmap_item->skip_age = age + inc_skip_age(age);

Can't you overflow here as well?

Quoted 5 lines
Quoted 2 lines

Yes, you can. See the above discussion. This skip_age is also an unsigned value.

Dito.

I'll make it explicit.

Quoted 11 lines
Quoted 9 lines
Quoted 6 lines

mm/ksm.c static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, · line 2350

Quoted 2 lines
mm/ksm.c +1 -0
+		remove_rmap_item_from_tree(rmap_item);

Can you enlighten me why that is required?

This is required for age calculation and BUG_ON check in remove_rmap_item_from_tree. If we don't call remove_rmap_item_from_tree, we will hit the BUG_ON for the skipped pages later on.

I see, thanks!

#8 lore raw

PATCH 2/4 mm/ksm: add pages_skipped metric

In reply to 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.

---
 mm/ksm.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)
mm/ksm.c +12 -0
index bfd5087c7d5a..728574a3033e 100644
@@ -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;
@@ -2345,6 +2348,7 @@ static bool skip_rmap_item(struct page *page, struct ksm_rmap_item *rmap_item)
 		return false;
 	}
 
+	ksm_pages_skipped++;
 	if (rmap_item->skip_age == 0) {
 		rmap_item->skip_age = age + inc_skip_age(age);
 		remove_rmap_item_from_tree(rmap_item);
@@ -3435,6 +3439,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)
 {
@@ -3532,6 +3543,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
Signature · 1 line
2.39.3
Reviewed-by on v1 2/4
#9 lore raw

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

Quoted 49 lines · 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.

---
  mm/ksm.c | 12 ++++++++++++
  1 file changed, 12 insertions(+)
mm/ksm.c +11 -0
index bfd5087c7d5a..728574a3033e 100644
@@ -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;
@@ -2345,6 +2348,7 @@ static bool skip_rmap_item(struct page *page, struct ksm_rmap_item *rmap_item)
  		return false;
  	}
 
+	ksm_pages_skipped++;
  	if (rmap_item->skip_age == 0) {
  		rmap_item->skip_age = age + inc_skip_age(age);
  		remove_rmap_item_from_tree(rmap_item);
@@ -3435,6 +3439,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)
  {

mm/ksm.c static struct attribute *ksm_attrs[] = { · line 3549

Quoted 7 lines
mm/ksm.c +1 -0
@@ -3532,6 +3543,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
Signature · 3 lines
Cheers,

David / dhildenb
#10 lore raw

PATCH 3/4 mm/ksm: document smart scan mode

In reply to Stefan Roesch

This adds documentation for the smart scan mode of KSM.

---
 Documentation/admin-guide/mm/ksm.rst | 9 +++++++++
 1 file changed, 9 insertions(+)
Documentation/admin-guide/mm/ksm.rst +9 -0
index 776f244bdae4..1762219baf51 100644
@@ -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
Signature · 1 line
2.39.3
Reviewed-by on v1 3/4
#11 lore raw

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

Quoted 17 lines · Stefan Roesch

This adds documentation for the smart scan mode of KSM.

---
  Documentation/admin-guide/mm/ksm.rst | 9 +++++++++
  1 file changed, 9 insertions(+)
Documentation/admin-guide/mm/ksm.rst +2 -0
index 776f244bdae4..1762219baf51 100644
@@ -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

Documentation/admin-guide/mm/ksm.rst stable_node_chains_prune_millisecs · line 169

Quoted 10 lines
Documentation/admin-guide/mm/ksm.rst +7 -0
+        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
Signature · 3 lines
Cheers,

David / dhildenb
#12 lore raw

PATCH 4/4 mm/ksm: document pages_skipped sysfs knob

In reply to Stefan Roesch

This adds documentation for the new metric pages_skipped.

---
 Documentation/admin-guide/mm/ksm.rst | 2 ++
 1 file changed, 2 insertions(+)
Documentation/admin-guide/mm/ksm.rst +2 -0
index 1762219baf51..27d949250b67 100644
@@ -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
Signature · 1 line
2.39.3
Reviewed-by on v1 4/4
#13 lore raw

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

Quoted 12 lines · Stefan Roesch

This adds documentation for the new metric pages_skipped.

---
  Documentation/admin-guide/mm/ksm.rst | 2 ++
  1 file changed, 2 insertions(+)
Documentation/admin-guide/mm/ksm.rst +0 -0
index 1762219baf51..27d949250b67 100644

Documentation/admin-guide/mm/ksm.rst pages_unshared · line 185

Quoted 8 lines
Documentation/admin-guide/mm/ksm.rst +2 -0
@@ -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
Signature · 3 lines
Cheers,

David / dhildenb