From patchwork Fri Aug 2 00:05:46 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Minwoo Jo X-Patchwork-Id: 13750936 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id ADF8DC3DA4A for ; Fri, 2 Aug 2024 00:06:15 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 42D246B0085; Thu, 1 Aug 2024 20:06:15 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 3DD4E6B0088; Thu, 1 Aug 2024 20:06:15 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2A69D6B0089; Thu, 1 Aug 2024 20:06:15 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 0D53C6B0085 for ; Thu, 1 Aug 2024 20:06:15 -0400 (EDT) Received: from smtpin28.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 6330E160637 for ; Fri, 2 Aug 2024 00:06:14 +0000 (UTC) X-FDA: 82405363068.28.A3489BA Received: from mail-pg1-f174.google.com (mail-pg1-f174.google.com [209.85.215.174]) by imf06.hostedemail.com (Postfix) with ESMTP id 70DC2180003 for ; Fri, 2 Aug 2024 00:06:11 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=g-cbnu-ac-kr.20230601.gappssmtp.com header.s=20230601 header.b=Lbms3Fl+; spf=none (imf06.hostedemail.com: domain of chminoo@g.cbnu.ac.kr has no SPF policy when checking 209.85.215.174) smtp.mailfrom=chminoo@g.cbnu.ac.kr; dmarc=fail reason="No valid SPF, DKIM not aligned (relaxed)" header.from=cbnu.ac.kr (policy=none) ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1722557144; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:references:dkim-signature; bh=FZbMpX3CH4dcans5zkom77VwVpU6vtt39eKmHcfmjsk=; b=m19JvmFhY4KSUp1OLHaasBGC+LwdCcRLSkBlxBLQGvG7OaLSzzhZs7ek+gbBGlSGX03r4M 22TzZnaOp4UU0tDhDXo5ivbcURegQzIV9A4WHVBfju0JLS7y/npe866BTMPztgnXcnjLI9 TGEjzG1eWodna8DBTDLFWPtbx8JG5QU= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=g-cbnu-ac-kr.20230601.gappssmtp.com header.s=20230601 header.b=Lbms3Fl+; spf=none (imf06.hostedemail.com: domain of chminoo@g.cbnu.ac.kr has no SPF policy when checking 209.85.215.174) smtp.mailfrom=chminoo@g.cbnu.ac.kr; dmarc=fail reason="No valid SPF, DKIM not aligned (relaxed)" header.from=cbnu.ac.kr (policy=none) ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1722557144; a=rsa-sha256; cv=none; b=1dO1hPzX5bD46jQyDwqS/KMXXLJ+ybyyq98AE30tSZ5elT1VacsfKJzmq4xM/A1ZvoU2Wx Sq0HfB49TCgIsHFcWSMN5hpWJYUY4XkuaZJZIssnjKqrRxJRHOh+vM/19mzHgVEShj7Bum 6t08vZbTPacKE3KVSIWI8HrzvN00xRY= Received: by mail-pg1-f174.google.com with SMTP id 41be03b00d2f7-7a115c427f1so4781664a12.0 for ; Thu, 01 Aug 2024 17:06:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=g-cbnu-ac-kr.20230601.gappssmtp.com; s=20230601; t=1722557169; x=1723161969; darn=kvack.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=FZbMpX3CH4dcans5zkom77VwVpU6vtt39eKmHcfmjsk=; b=Lbms3Fl+K8eII4nyRbSfv9gJSibDr9tUCOew7SZjjXA/a/0WiWgbudKK9W1p0s1M4h xIpQ1/ieo9qkw6qMwa5OouhFEbGIIfadnNeS61CLqTLwE3JIt1mHAqq81/lCToRG9EJz z8d1gCab893pulTSz+Og6RIZuPX33hK8MyFLSzoASoyPZAV6zDKRAmQAPHPsgKVH68hN jWTpq+eTYDLG+Y8lNVRH5oFP843ylVQPABDyt3PTetvv2lKWtDrAoP6DiVHyodlg38sl ykLDx9zVRRJdiGyVi7Bmy0q+nC1rQQZI1rhTpwVBXuwYRVNJEKqJmr4Cd4PR74MgWcwT bYOQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722557169; x=1723161969; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=FZbMpX3CH4dcans5zkom77VwVpU6vtt39eKmHcfmjsk=; b=bBp+eebArsVNzVLe0y/JluHCXd0kTCjV9HmxOdMA1hX7snDCNspvfOWpAir+SqLnbZ g6qCBxC3lxHsIAh1TmJJeBffC14adBp0m3O4IPWWS2qp4zpBlCm4MWzDFl2zEp6cGIi/ aGf/V3GKpibtdL6HrzO8ldfsyv0fXCuJcLeqpG5Yp0FmKiFREDJJ8ZTI7mqYinr2bkMo fSVZu/ht8/sG1QFP2oeL5qLt+xKP9fRPTOekJjzCPewvkG4RftFHdpRcqj4gXkgU3Eqh hOauV5r/oczgsrNuVv2h7fxNrGxWtgc3nwGLUuArvvat8xlfrLfb1U1DMdrP9V/yBD1a Hs6A== X-Forwarded-Encrypted: i=1; AJvYcCX+Q8uWrq+oQz8sFq/2bf8lsGxQoCNJNBbRTERGOl4fLZ67vd1dyHQ6CAR2qZ3cKEWJQ/GMjfewZrAfOsFdw/ujVxQ= X-Gm-Message-State: AOJu0YwZ7g5KDhMnSgljrK/C0LIn9ru7eqteRS0Fu+ZjBQ/JaV2dfvQJ D+Y+ne51orWn12BiaJl1AJqzMOqlNnO3IXXTWZCFtIEdrnYVvlR6yObGTtDL+cc= X-Google-Smtp-Source: AGHT+IGNmmRorvwmKCmI3/w74/o5Ze6Hq204J0XKsXYeIgMX4lLqOqGkQZQWxqKDKqYuPPxnAZj+NA== X-Received: by 2002:a05:6a21:6d8a:b0:1c4:2134:dd52 with SMTP id adf61e73a8af0-1c69953c6b8mr2737407637.3.1722557169007; Thu, 01 Aug 2024 17:06:09 -0700 (PDT) Received: from swist1.. ([113.198.137.2]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2cffaf69acbsm531546a91.1.2024.08.01.17.06.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 01 Aug 2024 17:06:08 -0700 (PDT) From: Minwoo Jo To: akpm@linux-foundation.org Cc: rostedt@goodmis.org, mhiramat@kernel.org, willy@infradead.org, linux-mm@kvack.org, Minwoo Jo Subject: [PATCH] Hitshield : Something new eviction process for MGLRU Date: Fri, 2 Aug 2024 00:05:46 +0000 Message-ID: <20240802000546.322036-1-chminoo@g.cbnu.ac.kr> X-Mailer: git-send-email 2.43.0 MIME-Version: 1.0 X-Rspamd-Server: rspam03 X-Rspam-User: X-Rspamd-Queue-Id: 70DC2180003 X-Stat-Signature: wegzuuebacq8tut6c653up3ob1ne1u78 X-HE-Tag: 1722557171-494769 X-HE-Meta: U2FsdGVkX1/6KlmjT5apwLDRKQNxM4SD547V14qI+ZWG363sVbOspl1Tji6V9X9c7WV+8itUVtzetJ/4Vl+oP80sRJ+OMesMJFQWJmopXnnIYZMCZoEG4Pu3laRx0CrM5+iHOEJh9kXbmQGqm2f9aKvdBuXDuiqnyT89rXS0NhTnqFsnPId+QlUHtJUpG3JNoNvoc+KwTNXKnq2dJfTDbvJ3UP7o2sEQ+iKeXpnBkgiRQsA1RBZeGZkG4TDPgy6NNLZ0nXP0NkBzpBgMpR3jfKzPxgXPJwccCIxn07eixS57Fvw9aCZXdCgYWNag9SbwdUOhceOMwCBHxrUc0aovxWgOGLXAdVNtVjg464FH0O/M48c5Oqdx6XrJhUdnTZq+Satx0i6/T3DHH70QDHE6lmuwOuTYrIYwDgGWoN4UimqjjBrLI+JNjNeOhtuUSEpGk2fi5J9PDq7A4u37h2OQUtsdHnJyV/YnpJa8L/n1VSOZU+lIfkoJOmsikh2EdKq1PI7RtxPQDftBstHpiaR5YPhX5WKmmsOCofnoquK3zKahsoAFiDZpX1cL7/X7rgz7xT1kFlHRK/eUU8RMxtObABkx2SFrS86Q9eJpaDf86FQaB/jNIFhawY0/NAm/KmpoEiqk8JroLeBNFZ0iJsAD52siRpRFUh96Mgewld938mC0BMNpR5rIjY4l7PVMMurBy5hzMnYdjPNnZGP7OuALu6nlNr17Ape1jQUMx9JiZynjnOxHfnl477QifpUpFFK6Gk6NOvDQF0nEdIWhugvWvq+0gqIYKVH1nUr6S5p3W+u6Ir989Belvw+QaNT1+NIMoSh4A6bLfQmatDG0BaBY6LYpqACK3Ym/h5URgrwylsPEjEVb+mKMKisNaBeJjyATPFPWJ0p34dgK3zu3cU3IfTLlbVrqi62VHBk1/pH5j9F0eU+zBoL0WqNHjpqD0VCxiVa1KTZEBeYW3Nq+/w4 c43VbFxE p16SfmgyjFK8FrTUVPozgME44YfBYdaVsZ976XmZgKLlagH2KUDMkVR7QDg6sYHciWtESdHpzoWNVZT5Oa2cZdtYze30v37l+1kNbczcOQHhoiRZU2gwybiwQJQZUfUQdD4Pf688qShwUlBl+xJVAicIw/664L8Tl35uO6kpu+iMX/NXOg40KSWgS5EEkMq7PLWlM8dQ/UuhC2aD32PJ7Hrrd8Bey9tB+ON2H0N1XMOmQNrUmyGC/jyNx3xwW54WpDl82R8MmSVJFkuHQDD59Nx4axXlJevqok79GqoeEGJJ6/NZo0abfJZ/+SvcffiEJZcBr0vo7aSCVuW/cO1r307Pj1+UO1V1o7Uz1 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: Signed-off-by: Minwoo Jo 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; }