[PATCH] Hitshield : Something new eviction process for MGLRU

[PATCH] Hitshield : Something new eviction process for MGLRU

[Minwoo Jo]

Signed-off-by: Minwoo Jo <chminoo@g.cbnu.ac.kr>

This commit addresses the page space occupancy issue that arose
in the previous commit with the HitShield technology.

The HitShield technology is based on the observation that MGLRU
does not take into account the state of the folio during eviction.

I assumed that if a folio, which has been updated only 1 to 3 times,
has increased in generation until the point of eviction,
it is likely to be referenced less in the future.

Therefore, I implemented this technology to protect frequently updated folios.

I added the hitshield_0, hitshield_1, and hitshield flags to the page flag.

Upon my review, I confirmed that the flags occupy positions 0 to 28.

Thus, I believe that allocating 3 flags, or 3 bits, is sufficient.

The hitshield_0 and hitshield_1 flags serve as count flags, representing the digit positions in binary.

The hitshield flag is a boolean flag used to verify whether the HitShield is actually enabled.

Each time a folio is added to lrugen, the hitshield_0 and hitshield_1 flags are cleared to reset them.

Subsequently, in the folio_update_gen function, I added the following code:

if (!folio_test_hitshield(folio))
    if (folio_test_change_hitshield_0(folio))
        if (folio_test_change_hitshield_1(folio))
            folio_set_hitshield(folio);

This code counts the HitShield, and if it exceeds 5, it sets the hitshield flag.

In the sort_folio function, which is executed for eviction, if the folio's hitshield flag is set,
it ages the folio to max_gen and resets the flag.

The testing was conducted on Ubuntu 24.04 LTS (Kernel 6.8.0)
with an AMD Ryzen 9 5950X 16Core (32Threads) environment, restricting DRAM to 750MiB through Docker.

In this environment, the ycsb benchmark was tested using the following command:

./bin/ycsb load mongodb -s -P workloads/workloadf -p recordcount=100000000 -p mongodb.batchsize=1024
-threads 32 -p mongodb.url="mongodb://localhost:27017/ycsb"

During testing, a reduction of 78.9% in pswpin and 75.6% in pswpout was measured.

Additionally, the runtime for the Load command decreased by 18.3%,
and the runtime for the Run command decreased by 9.3%.

However, when running a single-threaded program with the current implementation,
while a decrease in swap counts was observed, the runtime increased compared to the native MGLRU.

A thorough analysis is needed to understand why this occurs, but I think it appears
that there is significant overhead from the flag calculations.

Therefore, it seems that if we activate this functionality through an ifdef statement
only in certain situations, we could achieve performance benefits.

As an undergraduate student who is still self-studying the kernel, I am not very familiar with using ifdef,
so I did not write that part separately.

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      |  4 ++++
 include/linux/page-flags.h     | 26 ++++++++++++++++++++++++++
 include/trace/events/mmflags.h |  5 ++++-
 mm/vmscan.c                    | 22 ++++++++++++++++++++++
 4 files changed, 56 insertions(+), 1 deletion(-)

diff --git a/include/linux/mm_inline.h b/include/linux/mm_inline.h
index f4fe593c1400..dea613b2785c 100644
--- a/include/linux/mm_inline.h
+++ b/include/linux/mm_inline.h
@@ -266,6 +266,10 @@ static inline bool lru_gen_add_folio(struct lruvec *lruvec, struct folio *folio,
 	else
 		list_add(&folio->lru, &lrugen->folios[gen][type][zone]);
 
+	folio_clear_hitshield_0(folio);
+	folio_clear_hitshield_1(folio);
+	/* This for initialize hit_shield by 0 when folio add to gen */
+
 	return true;
 }
 
diff --git a/include/linux/page-flags.h b/include/linux/page-flags.h
index 5769fe6e4950..70951c6fe4ce 100644
--- a/include/linux/page-flags.h
+++ b/include/linux/page-flags.h
@@ -130,6 +130,16 @@ enum pageflags {
 	PG_arch_2,
 	PG_arch_3,
 #endif
+	PG_hitshield_0,
+	PG_hitshield_1,
+	PG_hitshield,
+
+	/*
+	 * The flags consist of two types: one for counting the update occurrences
+	 * of the folio and another boolean flag to check whether the HitShield is activated.
+	 */
+
+
 	__NR_PAGEFLAGS,
 
 	PG_readahead = PG_reclaim,
@@ -504,6 +514,14 @@ static inline int TestClearPage##uname(struct page *page) { return 0; }
 #define TESTSCFLAG_FALSE(uname, lname)					\
 	TESTSETFLAG_FALSE(uname, lname) TESTCLEARFLAG_FALSE(uname, lname)
 
+#define TESTCHANGEPAGEFLAG(uname, lname, policy)                        \
+static __always_inline                                                  \
+bool folio_test_change_##lname(struct folio *folio)                     \
+{ return test_and_change_bit(PG_##lname, folio_flags(folio, FOLIO_##policy)); } \
+static __always_inline int TestChangePage##uname(struct page *page)             \
+{ return test_and_change_bit(PG_##lname, &policy(page, 0)->flags); }
+/* This macro function allows the use of the change operation defined in bitops. */
+
 __PAGEFLAG(Locked, locked, PF_NO_TAIL)
 FOLIO_FLAG(waiters, FOLIO_HEAD_PAGE)
 PAGEFLAG(Error, error, PF_NO_TAIL) TESTCLEARFLAG(Error, error, PF_NO_TAIL)
@@ -559,6 +577,14 @@ PAGEFLAG(Reclaim, reclaim, PF_NO_TAIL)
 PAGEFLAG(Readahead, readahead, PF_NO_COMPOUND)
 	TESTCLEARFLAG(Readahead, readahead, PF_NO_COMPOUND)
 
+/*
+ * hitshield_0 and 1 use only clear and test_change functions, also
+ * hitshield flag uses only set, test, test_clear function
+ */
+PAGEFLAG(Hitshield0, hitshield_0, PF_HEAD) TESTCHANGEPAGEFLAG(Hitshield0, hitshield_0, PF_HEAD)
+PAGEFLAG(Hitshield1, hitshield_1, PF_HEAD) TESTCHANGEPAGEFLAG(Hitshield1, hitshield_1, PF_HEAD)
+PAGEFLAG(Hitshield, hitshield, PF_HEAD) TESTSCFLAG(Hitshield, hitshield, PF_HEAD)
+
 #ifdef CONFIG_HIGHMEM
 /*
  * Must use a macro here due to header dependency issues. page_zone() is not
diff --git a/include/trace/events/mmflags.h b/include/trace/events/mmflags.h
index b63d211bd141..d7ef9c503876 100644
--- a/include/trace/events/mmflags.h
+++ b/include/trace/events/mmflags.h
@@ -117,7 +117,10 @@
 	DEF_PAGEFLAG_NAME(mappedtodisk),				\
 	DEF_PAGEFLAG_NAME(reclaim),					\
 	DEF_PAGEFLAG_NAME(swapbacked),					\
-	DEF_PAGEFLAG_NAME(unevictable)					\
+	DEF_PAGEFLAG_NAME(unevictable),					\
+	DEF_PAGEFLAG_NAME(hitshield_0),					\
+	DEF_PAGEFLAG_NAME(hitshield_1),					\
+	DEF_PAGEFLAG_NAME(hitshield)					\
 IF_HAVE_PG_MLOCK(mlocked)						\
 IF_HAVE_PG_UNCACHED(uncached)						\
 IF_HAVE_PG_HWPOISON(hwpoison)						\
diff --git a/mm/vmscan.c b/mm/vmscan.c
index cfa839284b92..b44371dddb33 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -3148,6 +3148,18 @@ static int folio_update_gen(struct folio *folio, int gen)
 		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_test_hitshield(folio))
+		if (folio_test_change_hitshield_0(folio))
+			if (folio_test_change_hitshield_1(folio))
+				folio_set_hitshield(folio);
+
 	return ((old_flags & LRU_GEN_MASK) >> LRU_GEN_PGOFF) - 1;
 }
 
@@ -4334,6 +4346,16 @@ static bool sort_folio(struct lruvec *lruvec, struct folio *folio, struct scan_c
 		return true;
 	}
 
+	/* this when hit_shield is enabled
+	 * init hit_shield again, and protect this folio like second chance algorithm
+	 */
+
+	if (folio_test_clear_hitshield(folio)) {
+		gen = folio_inc_gen(lruvec, folio, true);
+		list_move(&folio->lru, &lrugen->folios[gen][type][zone]);
+		return true;
+	}
+
 	return false;
 }
 
-- 
2.43.0

Re: [PATCH] Hitshield : Something new eviction process for MGLRU

[Vlastimil Babka]

+Cc Yu Zhao

On 8/2/24 02:05, Minwoo Jo wrote:
> Signed-off-by: Minwoo Jo <chminoo@g.cbnu.ac.kr>
> 
> This commit addresses the page space occupancy issue that arose
> in the previous commit with the HitShield technology.
> 
> The HitShield technology is based on the observation that MGLRU
> does not take into account the state of the folio during eviction.
> 
> I assumed that if a folio, which has been updated only 1 to 3 times,
> has increased in generation until the point of eviction,
> it is likely to be referenced less in the future.
> 
> Therefore, I implemented this technology to protect frequently updated folios.
> 
> I added the hitshield_0, hitshield_1, and hitshield flags to the page flag.
> 
> Upon my review, I confirmed that the flags occupy positions 0 to 28.
> 
> Thus, I believe that allocating 3 flags, or 3 bits, is sufficient.
> 
> The hitshield_0 and hitshield_1 flags serve as count flags, representing the digit positions in binary.
> 
> The hitshield flag is a boolean flag used to verify whether the HitShield is actually enabled.
> 
> Each time a folio is added to lrugen, the hitshield_0 and hitshield_1 flags are cleared to reset them.
> 
> Subsequently, in the folio_update_gen function, I added the following code:
> 
> if (!folio_test_hitshield(folio))
>     if (folio_test_change_hitshield_0(folio))
>         if (folio_test_change_hitshield_1(folio))
>             folio_set_hitshield(folio);
> 
> This code counts the HitShield, and if it exceeds 5, it sets the hitshield flag.
> 
> In the sort_folio function, which is executed for eviction, if the folio's hitshield flag is set,
> it ages the folio to max_gen and resets the flag.
> 
> The testing was conducted on Ubuntu 24.04 LTS (Kernel 6.8.0)
> with an AMD Ryzen 9 5950X 16Core (32Threads) environment, restricting DRAM to 750MiB through Docker.
> 
> In this environment, the ycsb benchmark was tested using the following command:
> 
> ./bin/ycsb load mongodb -s -P workloads/workloadf -p recordcount=100000000 -p mongodb.batchsize=1024
> -threads 32 -p mongodb.url="mongodb://localhost:27017/ycsb"
> 
> During testing, a reduction of 78.9% in pswpin and 75.6% in pswpout was measured.
> 
> Additionally, the runtime for the Load command decreased by 18.3%,
> and the runtime for the Run command decreased by 9.3%.
> 
> However, when running a single-threaded program with the current implementation,
> while a decrease in swap counts was observed, the runtime increased compared to the native MGLRU.
> 
> A thorough analysis is needed to understand why this occurs, but I think it appears
> that there is significant overhead from the flag calculations.
> 
> Therefore, it seems that if we activate this functionality through an ifdef statement
> only in certain situations, we could achieve performance benefits.
> 
> As an undergraduate student who is still self-studying the kernel, I am not very familiar with using ifdef,
> so I did not write that part separately.
> 
> 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      |  4 ++++
>  include/linux/page-flags.h     | 26 ++++++++++++++++++++++++++
>  include/trace/events/mmflags.h |  5 ++++-
>  mm/vmscan.c                    | 22 ++++++++++++++++++++++
>  4 files changed, 56 insertions(+), 1 deletion(-)
> 
> diff --git a/include/linux/mm_inline.h b/include/linux/mm_inline.h
> index f4fe593c1400..dea613b2785c 100644
> --- a/include/linux/mm_inline.h
> +++ b/include/linux/mm_inline.h
> @@ -266,6 +266,10 @@ static inline bool lru_gen_add_folio(struct lruvec *lruvec, struct folio *folio,
>  	else
>  		list_add(&folio->lru, &lrugen->folios[gen][type][zone]);
>  
> +	folio_clear_hitshield_0(folio);
> +	folio_clear_hitshield_1(folio);
> +	/* This for initialize hit_shield by 0 when folio add to gen */
> +
>  	return true;
>  }
>  
> diff --git a/include/linux/page-flags.h b/include/linux/page-flags.h
> index 5769fe6e4950..70951c6fe4ce 100644
> --- a/include/linux/page-flags.h
> +++ b/include/linux/page-flags.h
> @@ -130,6 +130,16 @@ enum pageflags {
>  	PG_arch_2,
>  	PG_arch_3,
>  #endif
> +	PG_hitshield_0,
> +	PG_hitshield_1,
> +	PG_hitshield,
> +
> +	/*
> +	 * The flags consist of two types: one for counting the update occurrences
> +	 * of the folio and another boolean flag to check whether the HitShield is activated.
> +	 */
> +
> +
>  	__NR_PAGEFLAGS,
>  
>  	PG_readahead = PG_reclaim,
> @@ -504,6 +514,14 @@ static inline int TestClearPage##uname(struct page *page) { return 0; }
>  #define TESTSCFLAG_FALSE(uname, lname)					\
>  	TESTSETFLAG_FALSE(uname, lname) TESTCLEARFLAG_FALSE(uname, lname)
>  
> +#define TESTCHANGEPAGEFLAG(uname, lname, policy)                        \
> +static __always_inline                                                  \
> +bool folio_test_change_##lname(struct folio *folio)                     \
> +{ return test_and_change_bit(PG_##lname, folio_flags(folio, FOLIO_##policy)); } \
> +static __always_inline int TestChangePage##uname(struct page *page)             \
> +{ return test_and_change_bit(PG_##lname, &policy(page, 0)->flags); }
> +/* This macro function allows the use of the change operation defined in bitops. */
> +
>  __PAGEFLAG(Locked, locked, PF_NO_TAIL)
>  FOLIO_FLAG(waiters, FOLIO_HEAD_PAGE)
>  PAGEFLAG(Error, error, PF_NO_TAIL) TESTCLEARFLAG(Error, error, PF_NO_TAIL)
> @@ -559,6 +577,14 @@ PAGEFLAG(Reclaim, reclaim, PF_NO_TAIL)
>  PAGEFLAG(Readahead, readahead, PF_NO_COMPOUND)
>  	TESTCLEARFLAG(Readahead, readahead, PF_NO_COMPOUND)
>  
> +/*
> + * hitshield_0 and 1 use only clear and test_change functions, also
> + * hitshield flag uses only set, test, test_clear function
> + */
> +PAGEFLAG(Hitshield0, hitshield_0, PF_HEAD) TESTCHANGEPAGEFLAG(Hitshield0, hitshield_0, PF_HEAD)
> +PAGEFLAG(Hitshield1, hitshield_1, PF_HEAD) TESTCHANGEPAGEFLAG(Hitshield1, hitshield_1, PF_HEAD)
> +PAGEFLAG(Hitshield, hitshield, PF_HEAD) TESTSCFLAG(Hitshield, hitshield, PF_HEAD)
> +
>  #ifdef CONFIG_HIGHMEM
>  /*
>   * Must use a macro here due to header dependency issues. page_zone() is not
> diff --git a/include/trace/events/mmflags.h b/include/trace/events/mmflags.h
> index b63d211bd141..d7ef9c503876 100644
> --- a/include/trace/events/mmflags.h
> +++ b/include/trace/events/mmflags.h
> @@ -117,7 +117,10 @@
>  	DEF_PAGEFLAG_NAME(mappedtodisk),				\
>  	DEF_PAGEFLAG_NAME(reclaim),					\
>  	DEF_PAGEFLAG_NAME(swapbacked),					\
> -	DEF_PAGEFLAG_NAME(unevictable)					\
> +	DEF_PAGEFLAG_NAME(unevictable),					\
> +	DEF_PAGEFLAG_NAME(hitshield_0),					\
> +	DEF_PAGEFLAG_NAME(hitshield_1),					\
> +	DEF_PAGEFLAG_NAME(hitshield)					\
>  IF_HAVE_PG_MLOCK(mlocked)						\
>  IF_HAVE_PG_UNCACHED(uncached)						\
>  IF_HAVE_PG_HWPOISON(hwpoison)						\
> diff --git a/mm/vmscan.c b/mm/vmscan.c
> index cfa839284b92..b44371dddb33 100644
> --- a/mm/vmscan.c
> +++ b/mm/vmscan.c
> @@ -3148,6 +3148,18 @@ static int folio_update_gen(struct folio *folio, int gen)
>  		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_test_hitshield(folio))
> +		if (folio_test_change_hitshield_0(folio))
> +			if (folio_test_change_hitshield_1(folio))
> +				folio_set_hitshield(folio);
> +
>  	return ((old_flags & LRU_GEN_MASK) >> LRU_GEN_PGOFF) - 1;
>  }
>  
> @@ -4334,6 +4346,16 @@ static bool sort_folio(struct lruvec *lruvec, struct folio *folio, struct scan_c
>  		return true;
>  	}
>  
> +	/* this when hit_shield is enabled
> +	 * init hit_shield again, and protect this folio like second chance algorithm
> +	 */
> +
> +	if (folio_test_clear_hitshield(folio)) {
> +		gen = folio_inc_gen(lruvec, folio, true);
> +		list_move(&folio->lru, &lrugen->folios[gen][type][zone]);
> +		return true;
> +	}
> +
>  	return false;
>  }
>  

Re: [PATCH] Hitshield : Something new eviction process for MGLRU

[David Hildenbrand]

On 02.08.24 02:05, Minwoo Jo wrote:
> Signed-off-by: Minwoo Jo <chminoo@g.cbnu.ac.kr>
> 
> This commit addresses the page space occupancy issue that arose
> in the previous commit with the HitShield technology.
> 
> The HitShield technology is based on the observation that MGLRU
> does not take into account the state of the folio during eviction.
> 
> I assumed that if a folio, which has been updated only 1 to 3 times,
> has increased in generation until the point of eviction,
> it is likely to be referenced less in the future.
> 
> Therefore, I implemented this technology to protect frequently updated folios.
> 
> I added the hitshield_0, hitshield_1, and hitshield flags to the page flag.
> 
> Upon my review, I confirmed that the flags occupy positions 0 to 28.
> 
> Thus, I believe that allocating 3 flags, or 3 bits, is sufficient.
> 
> The hitshield_0 and hitshield_1 flags serve as count flags, representing the digit positions in binary.
> 
> The hitshield flag is a boolean flag used to verify whether the HitShield is actually enabled.
> 
> Each time a folio is added to lrugen, the hitshield_0 and hitshield_1 flags are cleared to reset them.
> 
> Subsequently, in the folio_update_gen function, I added the following code:
> 
> if (!folio_test_hitshield(folio))
>      if (folio_test_change_hitshield_0(folio))
>          if (folio_test_change_hitshield_1(folio))
>              folio_set_hitshield(folio);
> 
> This code counts the HitShield, and if it exceeds 5, it sets the hitshield flag.
> 
> In the sort_folio function, which is executed for eviction, if the folio's hitshield flag is set,
> it ages the folio to max_gen and resets the flag.
> 
> The testing was conducted on Ubuntu 24.04 LTS (Kernel 6.8.0)
> with an AMD Ryzen 9 5950X 16Core (32Threads) environment, restricting DRAM to 750MiB through Docker.
> 
> In this environment, the ycsb benchmark was tested using the following command:
> 
> ./bin/ycsb load mongodb -s -P workloads/workloadf -p recordcount=100000000 -p mongodb.batchsize=1024
> -threads 32 -p mongodb.url="mongodb://localhost:27017/ycsb"
> 
> During testing, a reduction of 78.9% in pswpin and 75.6% in pswpout was measured.
> 
> Additionally, the runtime for the Load command decreased by 18.3%,
> and the runtime for the Run command decreased by 9.3%.
> 
> However, when running a single-threaded program with the current implementation,
> while a decrease in swap counts was observed, the runtime increased compared to the native MGLRU.
> 
> A thorough analysis is needed to understand why this occurs, but I think it appears
> that there is significant overhead from the flag calculations.
> 
> Therefore, it seems that if we activate this functionality through an ifdef statement
> only in certain situations, we could achieve performance benefits.
> 
> As an undergraduate student who is still self-studying the kernel, I am not very familiar with using ifdef,
> so I did not write that part separately.
> 
> 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      |  4 ++++
>   include/linux/page-flags.h     | 26 ++++++++++++++++++++++++++
>   include/trace/events/mmflags.h |  5 ++++-
>   mm/vmscan.c                    | 22 ++++++++++++++++++++++
>   4 files changed, 56 insertions(+), 1 deletion(-)
> 
> diff --git a/include/linux/mm_inline.h b/include/linux/mm_inline.h
> index f4fe593c1400..dea613b2785c 100644
> --- a/include/linux/mm_inline.h
> +++ b/include/linux/mm_inline.h
> @@ -266,6 +266,10 @@ static inline bool lru_gen_add_folio(struct lruvec *lruvec, struct folio *folio,
>   	else
>   		list_add(&folio->lru, &lrugen->folios[gen][type][zone]);
>   
> +	folio_clear_hitshield_0(folio);
> +	folio_clear_hitshield_1(folio);
> +	/* This for initialize hit_shield by 0 when folio add to gen */
> +
>   	return true;
>   }
>   
> diff --git a/include/linux/page-flags.h b/include/linux/page-flags.h
> index 5769fe6e4950..70951c6fe4ce 100644
> --- a/include/linux/page-flags.h
> +++ b/include/linux/page-flags.h
> @@ -130,6 +130,16 @@ enum pageflags {
>   	PG_arch_2,
>   	PG_arch_3,
>   #endif
> +	PG_hitshield_0,
> +	PG_hitshield_1,
> +	PG_hitshield,
> +
> +	/*
> +	 * The flags consist of two types: one for counting the update occurrences
> +	 * of the folio and another boolean flag to check whether the HitShield is activated.
> +	 */

Note that adding new pageflags is frowned upon -- we're actually trying 
to get rid of some of them, like PG_error. Getting another 3 added seems 
very .. unlikely :)

Especially when done unconditionally on 32bit as well this might just 
not work at all, and as you state, would require #ifdefery.

-- 
Cheers,

David / dhildenb

Re: [PATCH] Hitshield : Something new eviction process for MGLRU

[SeongJae Park]

Hello Minwoo,

On Fri, 2 Aug 2024 00:05:46 +0000 Minwoo Jo <chminoo@g.cbnu.ac.kr> wrote:

> Signed-off-by: Minwoo Jo <chminoo@g.cbnu.ac.kr>
> 
> This commit addresses the page space occupancy issue that arose
> in the previous commit with the HitShield technology.
> 
> The HitShield technology is based on the observation that MGLRU
> does not take into account the state of the folio during eviction.
> 
> I assumed that if a folio, which has been updated only 1 to 3 times,
> has increased in generation until the point of eviction,
> it is likely to be referenced less in the future.

So, my humble understanding of the point is that, you want to improve the
kernel's reclamation logic by making it awares not only recency, but also
frequency?

Given existence of several previous frequency based page placement algorithm
optimization researches including LRFU, CAR and CART, I think the overall idea
might make sense at least in some use cases.  I'm not sure whether the
threshold value and the mechanism to measure the frequency make sense and/or
can be applied to general cases, though.

> 
> Therefore, I implemented this technology to protect frequently updated folios.
> 
> I added the hitshield_0, hitshield_1, and hitshield flags to the page flag.
> 
> Upon my review, I confirmed that the flags occupy positions 0 to 28.
> 
> Thus, I believe that allocating 3 flags, or 3 bits, is sufficient.

As others also mentioned, I think even three bits could be challinging to add.

In my humble opinion, frequency monitoring could be done using data structures
and access check mechanisms other than folio/LRU and reclamation logic.  Then,
the monitoring mechanism could manipulate LRU lists based on the frequency
data.  Modifying reclamation code to refer to the frequency data could also be
another way.

DAMON_LRU_SORT [1,2] could be an example of such approaches (driven by the
monitoring mechanism without reclamation code modification).  Of course,
DAMON_LRU_SORT would have many limitations and rooms for improvements.  I'm
curious if you also had a time to consider that kind of approaches?  If you did
so but found some critical problems and resulted in this patch, it would be
great if you can further share the found problems.

[1] https://lwn.net/Articles/905370/
[2] https://www.kernel.org/doc/html/latest/admin-guide/mm/damon/lru_sort.html


Thanks,
SJ

[...]

Re: [PATCH] Hitshield : Something new eviction process for MGLRU

[Minwoo Jo]

2024년 10월 9일 (수) 오전 3:50, SeongJae Park <sj@kernel.org>님이 작성:
>
> Hello Minwoo,
>
> On Fri, 2 Aug 2024 00:05:46 +0000 Minwoo Jo <chminoo@g.cbnu.ac.kr> wrote:
>
> > Signed-off-by: Minwoo Jo <chminoo@g.cbnu.ac.kr>
> >
> > This commit addresses the page space occupancy issue that arose
> > in the previous commit with the HitShield technology.
> >
> > The HitShield technology is based on the observation that MGLRU
> > does not take into account the state of the folio during eviction.
> >
> > I assumed that if a folio, which has been updated only 1 to 3 times,
> > has increased in generation until the point of eviction,
> > it is likely to be referenced less in the future.
>
> So, my humble understanding of the point is that, you want to improve the
> kernel's reclamation logic by making it awares not only recency, but also
> frequency?
>
> Given existence of several previous frequency based page placement algorithm
> optimization researches including LRFU, CAR and CART, I think the overall idea
> might make sense at least in some use cases.  I'm not sure whether the
> threshold value and the mechanism to measure the frequency make sense and/or
> can be applied to general cases, though.
>
> >
> > Therefore, I implemented this technology to protect frequently updated folios.
> >
> > I added the hitshield_0, hitshield_1, and hitshield flags to the page flag.
> >
> > Upon my review, I confirmed that the flags occupy positions 0 to 28.
> >
> > Thus, I believe that allocating 3 flags, or 3 bits, is sufficient.
>
> As others also mentioned, I think even three bits could be challinging to add.
>
> In my humble opinion, frequency monitoring could be done using data structures
> and access check mechanisms other than folio/LRU and reclamation logic.  Then,
> the monitoring mechanism could manipulate LRU lists based on the frequency
> data.  Modifying reclamation code to refer to the frequency data could also be
> another way.
>
> DAMON_LRU_SORT [1,2] could be an example of such approaches (driven by the
> monitoring mechanism without reclamation code modification).  Of course,
> DAMON_LRU_SORT would have many limitations and rooms for improvements.  I'm
> curious if you also had a time to consider that kind of approaches?  If you did
> so but found some critical problems and resulted in this patch, it would be
> great if you can further share the found problems.
>
> [1] https://lwn.net/Articles/905370/
> [2] https://www.kernel.org/doc/html/latest/admin-guide/mm/damon/lru_sort.html
>
>
> Thanks,
> SJ
>
> [...]

I apologize for the late response to your message.

Based on my limited understanding, the LRU manipulation in DAMON appears
to assist LRU by tracking data access to identify Hot Pages and Cold Pages,
subsequently lowering the priority of Cold Pages.

Additionally, this approach goes beyond simply measuring frequency,
as it analyzes patterns, which I believe could lead to greater performance.

By appropriately utilizing the lru_prio and lru_deprio mechanisms of DAMON's
LRU_SORT, I think it could also be implemented in MGLRU.

While HitShield differs from DAMON_LRU_SORT in that it checks counters
during internal operations rather than monitoring the internals,
I believe that by appropriately modifying this approach, we could implement
the HitShield mechanism without altering the folio's internal
structure or using flags.

Thank you for your insights; I will definitely consider them.

Thank you.
Minwoo, Jo

Re: [PATCH] Hitshield : Something new eviction process for MGLRU

[Minwoo Jo]

[-- Attachment #1: Type: text/plain, Size: 2462 bytes --]

2024년 10월 8일 (화) 오후 10:21, Mathieu Desnoyers <mathieu.desnoyers@efficios.com>님이
작성:

> On 2024-10-08 15:02, Mathieu Desnoyers wrote:
> > On 2024-10-08 10:44, Minwoo Jo wrote:
> >> Signed-off-by: Minwoo Jo <chminoo@g.cbnu.ac.kr>
> >>
> >
> > [ Any reason why no mailing lists are CC'd ? ]
> >
>
> [...]
> > Please consider CCing LKML and the linux-mm mailing lists on your reply.
>
> The Documentation/process/submitting-patches.rst document describes who
> should be CC'd when submitting patches.
>
> The script scripts/get_maintainer.pl will help you identify which
> email recipients are relevant for your patch.
>
> Thanks,
>
> Mathieu
>
> --
> Mathieu Desnoyers
> EfficiOS Inc.
> https://www.efficios.com
>
>
> [ Any reason why no mailing lists are CC'd ? ]

I think I did some mistake when I mail, so I add CC to
linux-mm@kvack.org (open list:MEMORY MANAGEMENT)
linux-kernel@vger.kernel.org (open list)
linux-trace-kernel@vger.kernel.org (open list:TRACING)

> Have you considered alternative approaches, and why is this approach
> better ?

I used an alternative approach of creating another wrapper or value
approach, but this was not good because it increased memory usage per
folio, resulting in more swaps.

> Do you have benchmarks of workloads that regress with this feature
> enabled ? How are they affected ?

I tried another two benchmarks, 7zip benchmark, YCSB.

The 7zip benchmark shows a 3.1% reduction in pswpin, 2.8% reduction in
pswpout,
and a 2.9% reduction in runtime under 1G constraints.
Under 2G constraints, pswpin decreased by 22.4%, pswpout decreased by
21.2%,
and Runtime decreased by 14.8%.
On 3G constraints, pswpin decreased by 3.3%, pswpout decreased by 1.3%,
and runtime decreased by 1.9%.

We also measured the Yahoo! Cloud Service Benchmark.
YCSB showed a 69.9% decrease in pswpin, 67.1% decrease in pswpout,
and a 5.1% decrease in Runtime at the 500M constraint.
At 750M constraints, pswpin decreased by 83.8%, pswpout decreased by 81.0%,
and runtime decreased by 2.4%.
On 1G constraints, pswpin decreased by 79.5%, pswpout decreased by 76.7%,
and runtime decreased by 3.8%.

> Documentation should be there first, or at least something explaining
> the rationale and design.

I think my previous commit mail might be helpful.
https://lore.kernel.org/linux-mm/ZpvY_aZV4VtMmXP-@casper.infradead.org/T/

Thank you for your response.

[-- Attachment #2: Type: text/html, Size: 3401 bytes --]

Re: [PATCH] HitShield:Something new eviction process for MGLRU

[Matthew Wilcox]

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] HitShield:Something new eviction process for MGLRU

[Minwoo Jo]

From: Minwoo <chminoo@g.cbnu.ac.kr>

Signed-off-by: Minwoo Jo <chminoo@g.cbnu.ac.kr>

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(-)

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;
 }
 
-- 
2.34.1