HitShield:Something new eviction process for MGLRU

Commit Message

Minwoo Jo July 20, 2024, 2:25 p.m. UTC

From: Minwoo <[e-mail]>

Signed-off-by: Minwoo Jo <[e-mail]>

This hitshield technique was devised based on the observation that MGLRU
does not consider the state of the folio when performing eviction.

The assumption is that if a folio that has been updated 1-3 times and not
frequently updated accumulates generations until it is evicted, it is
likely to have a low probability of being referenced in the future.

Therefore, this was implemented as a way to protect frequently updated folios.

A variable called hit_shield of type unsigned char was added to the folio
struct to track the update count.

It is initialized to 1 and incremented by 1 in folio_update_gen until it reaches
5 (MAX_NR_GENS+1). (If it doesn't reach 5, the folio will be evicted.)

If it exceeds 5, it is set to 0 using the % 5 operation.
(Then it will not be incremented further.)

In the sort_folio function executed for eviction, the hit_shield value of the
folio is checked, and if it is 0, the folio is promoted to max_gen, similar to a
second-chance algorithm, to protect it.

As a undergraduate student with limited experience in the Linux kernel, I still
need to further optimize this approach.

However, in the DELL T320 environment I tested, with memory limited to 750MiB through
Docker and using swap, the hitshield technique showed significant performance
improvements, reducing pswpin and pswpout counts by 3.63% and 5.73% in the 7zip
benchmark (7zr b), and 38.6% and 32.4% in the YCSB benchmark (./bin/ycsb load
mongodb -s -P workloads/workloadf -p recordcount=8000000 -p mongodb.batchsize=1024
-p mongodb.url="mongodb://localhost:27017/ycsb").

I apologize for not being able to test it with large memory swap workloads, as
I was unsure what would be appropriate.

I would appreciate your review and feedback on this approach.

Thank you.
---
 include/linux/mm_inline.h |  2 ++
 include/linux/mm_types.h  | 12 ++++++++++++
 mm/vmscan.c               | 19 ++++++++++++++++++-
 3 files changed, 32 insertions(+), 1 deletion(-)

Comments

Matthew Wilcox July 20, 2024, 3:34 p.m. UTC | #1

On Sat, Jul 20, 2024 at 11:25:28PM +0900, Minwoo Jo wrote:
> This hitshield technique was devised based on the observation that MGLRU
> does not consider the state of the folio when performing eviction.
> 
> The assumption is that if a folio that has been updated 1-3 times and not
> frequently updated accumulates generations until it is evicted, it is
> likely to have a low probability of being referenced in the future.

Hi Minwoo.  This is interesting work.  Thank you for sending it out.
I do not consider myself qualified to comment on your assumption, but
I have some feedback on your implementation.

> diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h
> index a199c48bc462..053d5620574e 100644
> --- a/include/linux/mm_types.h
> +++ b/include/linux/mm_types.h
> @@ -189,6 +189,12 @@ struct page {
>  	void *virtual;			/* Kernel virtual address (NULL if
>  					   not kmapped, ie. highmem) */
>  #endif /* WANT_PAGE_VIRTUAL */
> +	unsigned char hit_shield;	/*
> +					 * The hit_shield variable I added to the page
> +					 * This variable is responsible for counting
> +					 * the number of times this
> +					 * page's generation has been updated.
> +					 */

We don't really have space in struct page for this kind of thing,
unfortunately.  There are a _few_ bits available in page->flags on
64-bit, but even that is a bit tenuous.

Patch

diff --git a/include/linux/mm_inline.h b/include/linux/mm_inline.h
index f4fe593c1400..4fece03fc314 100644
--- a/include/linux/mm_inline.h
+++ b/include/linux/mm_inline.h
@@ -261,6 +261,8 @@  static inline bool lru_gen_add_folio(struct lruvec *lruvec, struct folio *folio,
 
 	lru_gen_update_size(lruvec, folio, -1, gen);
 	/* for folio_rotate_reclaimable() */
+	folio->hit_shield = 1;
+	/* This for initialize hit_shield by 1 when folio add to gen */
 	if (reclaiming)
 		list_add_tail(&folio->lru, &lrugen->folios[gen][type][zone]);
 	else
diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h
index a199c48bc462..053d5620574e 100644
--- a/include/linux/mm_types.h
+++ b/include/linux/mm_types.h
@@ -189,6 +189,12 @@  struct page {
 	void *virtual;			/* Kernel virtual address (NULL if
 					   not kmapped, ie. highmem) */
 #endif /* WANT_PAGE_VIRTUAL */
+	unsigned char hit_shield;	/*
+					 * The hit_shield variable I added to the page
+					 * This variable is responsible for counting
+					 * the number of times this
+					 * page's generation has been updated.
+					 */
 
 #ifdef LAST_CPUPID_NOT_IN_PAGE_FLAGS
 	int _last_cpupid;
@@ -343,6 +349,10 @@  struct folio {
 #if defined(WANT_PAGE_VIRTUAL)
 			void *virtual;
 #endif
+			unsigned char hit_shield;	/*
+							 * Variable added to the folio that
+							 * exists to offset the page structure.
+							 */
 #ifdef LAST_CPUPID_NOT_IN_PAGE_FLAGS
 			int _last_cpupid;
 #endif
@@ -404,6 +414,8 @@  FOLIO_MATCH(memcg_data, memcg_data);
 #if defined(WANT_PAGE_VIRTUAL)
 FOLIO_MATCH(virtual, virtual);
 #endif
+FOLIO_MATCH(hit_shield, hit_shield);
+/* A match macro for hit_shield */
 #ifdef LAST_CPUPID_NOT_IN_PAGE_FLAGS
 FOLIO_MATCH(_last_cpupid, _last_cpupid);
 #endif
diff --git a/mm/vmscan.c b/mm/vmscan.c
index 2e34de9cd0d4..6059f9736caa 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -3132,7 +3132,14 @@  static int folio_update_gen(struct folio *folio, int gen)
 		new_flags = old_flags & ~(LRU_GEN_MASK | LRU_REFS_MASK | LRU_REFS_FLAGS);
 		new_flags |= (gen + 1UL) << LRU_GEN_PGOFF;
 	} while (!try_cmpxchg(&folio->flags, &old_flags, new_flags));
-
+	/*
+	 * This part is core of hit_shield : Has this folio been updated frequently?
+	 * I chose 5 as the number of times to grant shield because of MAX_NR_GENS is 4,
+	 * so if this folio has been updated for more than a generation's length,
+	 * it has additional survivability equal to the generation's length.
+	 */
+	if (folio->hit_shield)
+		folio->hit_shield = (folio->hit_shield + 1) % 5;
 	return ((old_flags & LRU_GEN_MASK) >> LRU_GEN_PGOFF) - 1;
 }
 
@@ -4307,6 +4314,16 @@  static bool sort_folio(struct lruvec *lruvec, struct folio *folio, struct scan_c
 		return true;
 	}
 
+	/* this when hit_shield is enabled (if 0)
+	 * init hit_shield again, and protect this folio like second chance algorithm
+	 */
+	if (!folio->hit_shield) {
+		folio->hit_shield = 1;
+		gen = folio_inc_gen(lruvec, folio, true);
+		list_move(&folio->lru, &lrugen->folios[gen][type][zone]);
+		return true;
+	}
+
 	return false;
 }