From patchwork Sat Jul 20 14:25:28 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Minwoo Jo X-Patchwork-Id: 13737837 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 C5D30C3DA49 for ; Sat, 20 Jul 2024 14:26:40 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 1C5236B0082; Sat, 20 Jul 2024 10:26:40 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 14D726B0085; Sat, 20 Jul 2024 10:26:40 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id F09366B0088; Sat, 20 Jul 2024 10:26:39 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id CE0A26B0082 for ; Sat, 20 Jul 2024 10:26:39 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 318E180511 for ; Sat, 20 Jul 2024 14:26:39 +0000 (UTC) X-FDA: 82360356918.03.DF81012 Received: from mail-pl1-f173.google.com (mail-pl1-f173.google.com [209.85.214.173]) by imf26.hostedemail.com (Postfix) with ESMTP id 623B514001C for ; Sat, 20 Jul 2024 14:26:36 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=g-cbnu-ac-kr.20230601.gappssmtp.com header.s=20230601 header.b=PzlPuhtR; spf=none (imf26.hostedemail.com: domain of chminoo@g.cbnu.ac.kr has no SPF policy when checking 209.85.214.173) 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=1721485554; 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=bDGTV2ZtgPNUjM4NFptlvFB0dC7iEZm96p1OUviJvXc=; b=SGGeDkHb1JdFXMH4vZS2Ze4WmEBLlbwrX4o7kwWAWn6ZvZR3DjgT4Jg61I2NU1zHeRpYoN W6Iql9CWLQvzshpbLq8qQKLAN04nJErXfp0MHUlqGzXJtUgiyTfW8rpiKu+b3TQOBxsMSm k2+Mmht+8fylsOKsRSOhskp8EY6OjXs= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1721485554; a=rsa-sha256; cv=none; b=IkkLV3rqfbAYAiI4yzoK1sLhpeLjZJYcvV/v4CtvZYnNnTiQCQ3hiahPgECbxa8pa01zCc AaOmX8BKpHNfpS7St2J0/LrFdLRIw3RZR2zFQxC+e/6F065JhnG2igmal1Hdhro56iGVhH zhLrvznQ5Z9Qpjd36Glj+HqjvB9+gj4= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=g-cbnu-ac-kr.20230601.gappssmtp.com header.s=20230601 header.b=PzlPuhtR; spf=none (imf26.hostedemail.com: domain of chminoo@g.cbnu.ac.kr has no SPF policy when checking 209.85.214.173) smtp.mailfrom=chminoo@g.cbnu.ac.kr; dmarc=fail reason="No valid SPF, DKIM not aligned (relaxed)" header.from=cbnu.ac.kr (policy=none) Received: by mail-pl1-f173.google.com with SMTP id d9443c01a7336-1fc6a017abdso15592415ad.0 for ; Sat, 20 Jul 2024 07:26:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=g-cbnu-ac-kr.20230601.gappssmtp.com; s=20230601; t=1721485594; x=1722090394; 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=bDGTV2ZtgPNUjM4NFptlvFB0dC7iEZm96p1OUviJvXc=; b=PzlPuhtRpa1uwKDiBKyLFTR6UHKhqw8c26XSCVserA6zi7p/eAweYd2o87Ex1PYYxM ot3cbFTN1mCPct52R3BPKQR2JmtVGqh9yqigi+Vya1Ke3MZZiBAYFBq+jIyRD9RwNZ5b FJSdktdbSL07Q8bj8YSlo9fUATxrkZUIzDAqc6v3DqthlwnivwJhbjeyHpRIb7MeSE0i ekG/6QxnJ1liw9uN87+fZUXMZ/mIO96tliN07VpiP0DGe2M4Rh5LCwjOlSaqFvL5PhzV jGx5fYqFTg0uojjmvktQro7mKPsw9EozRMX/CKspzSA8AJ14+2O6cky7ZFmAe3cPOoJR 6Ogg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1721485594; x=1722090394; 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=bDGTV2ZtgPNUjM4NFptlvFB0dC7iEZm96p1OUviJvXc=; b=ZI6IuvSVriRjSjNeXyMvj8xxmT3QwohcBKaQQRlUXLUA5q0qkDmLDxZYKdHNPBoMBh YPlskQgxuLSFjMJGmFlSwjzc8JkEquTklX7kIiaVHi2MZrUR0A99b1Si31SzGJfp6NzS V9JSPmcGu7svZHjaJeUpXz1gg2S/0JCE1RNxKm//64wKzfOKPAOMfmGuP4/EUZ/oD6GV cYEwcbVdVXVtB9RNLvKaAct1VA7xY9DHMv5Ali6yud9Rmw9m0/y7g2yo8y/Fenro0wgm 77kcKxLVbeLBUz5J7lyHlo3q/icCFe6vIBdLScJJn+/oV9z8C6S9w7Z5qqHkO9ph8tz1 06QA== X-Gm-Message-State: AOJu0Yy7DX7U96VqZmSnIXLXg9I4wHDF34eNKAxFGzpCDQv6krKaCGIU HdNH7ZrihIhM9+1fg76xTy6n/M16vTnNJlGIuSNUG2PatB47DzZzoP45zoJ6KFq3+W51tAMHOif EvUNKmg== X-Google-Smtp-Source: AGHT+IHDlGiXIgUdMZu0eJDbVuvxLDC6THcZJmfL954YOR7Q7oRgr2LFq0nSrVb5MerT6XHO0PHN3Q== X-Received: by 2002:a17:902:dac7:b0:1fd:8904:ecf6 with SMTP id d9443c01a7336-1fd8904f0f1mr2916575ad.21.1721485594115; Sat, 20 Jul 2024 07:26:34 -0700 (PDT) Received: from swist1.168.126.63.1 ([113.198.137.2]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-1fd6f4647f5sm22459995ad.252.2024.07.20.07.26.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 20 Jul 2024 07:26:33 -0700 (PDT) From: Minwoo Jo To: akpm@linux-foundation.org Cc: linux-mm@kvack.org, Minwoo Subject: [PATCH] HitShield:Something new eviction process for MGLRU Date: Sat, 20 Jul 2024 23:25:28 +0900 Message-Id: <20240720142528.276861-1-chminoo@g.cbnu.ac.kr> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 623B514001C X-Stat-Signature: ohy4nyfoj3h1fw3aifg64u19azwswpm8 X-HE-Tag: 1721485596-284987 X-HE-Meta: U2FsdGVkX192GxRqwkqzQ+bvw8uozLMmu8llvMvUXOp9/aX97ETkOlXblvx50ITZE9BlhvyaSqNzMNWvbt9qYTNZPFr9uZwmBDdETRQcuzW0UYG7QZViIFtYD4mU1yQCi8El7IGMTRROYd9sV63rVhti8oAyPC2JyGjUxgiIUjNp955zwHdBXu84GCdL0m9yiUUYr0/613IqvJmzGOUDJ9s6PCObDY6kAPFWfMv/c28kR1k1031IQYLzLeehFR+lJYD4SMlrP/PqixICvpCNoU6WDIjLImkONVumEozxZIbffWsAkuwdm0BFCntbOMT9oPUHjaYFfdTzQAWZN7KFrgFYmSXu91wHI0Q/M7r0JE2EHKIw/YGgb4v7XFbpIkWVRt7Vio0BzNH6Tw6Q0yLg7FPCIp5GsOBE8eN3uUNVwBo6v1sW04oJ7Uzock1u7h841xt5cLXgSu99/fefYL5TL7EeNQZvG+tKeHqIIe3vId4Hlz929wVhVQ83zBud6qN+ywzCmtRCWCgHHCEKQ30k0FiKLXXcN8b530nNymbklm6AnjqpKVnkM1fB5h62mkTPaEAy2+jZ13skE4PYrU3BibWrG+U7f9iXqJv1JaBtMw6qTXCeJKOKiMqjrC3DlWQd4r4XTBMHGv6uKBvT99DW2ASlmwF8XXOOUztacpThN54PUlx3eIRyIorx3OUe8ef4eC8DaFg4gUnEeSDx091husD/aB00tWcjCUcuavZ/nRK8riqizA680BYRynUTrbdWm/9CNz/fzfc66QVpiMxF7rBJ9LAnS73BKPlvjTZkGU98k+i//b5FcvhzQsxGGtwDkdyZ95txp32r9FuGnLTSMO9hm5xE2uG++6AUv5BoaUGWX66RFvr/91x8zDvSzUf3dWHeV0w74OPIkExill23BzFOfdZrxUk1l6xZmmHm0NfBL+uAYfdJMx2MaUKvX/xBMdC92HXypq6/Ga3atHk 2ZaUl9J8 75SLgcevN2uSL8VzjU0yWoYaZHa26TV7/D5t+7qzXG8fVg1f5iipGPeh/kYs/cDQ/AyLXnqSAPRQKhxnIPOErMtPF4jeozsDSZOu4U9AzOTyT0TicIGWiKZtkOpmW8x3E+C7w3S81/51jX8G0VZV4EpItszD9XeLVnR4Hs4tW0n1hzqftX8sn8J1j7Tx9mFlxArtCIzF3+K9PKdbSR/AVoi1aC+uEVmLh1cbB0Cq3dLrcjVLD9dZzBWhqSCtQPmkkA+8Xl/EssiGpsVgLc0VFbb5fj7bKov8C4CiugI8+IRMdfVdDJyc0ZrRWqobdnTsdAIeercaJ2U/DspjWGGBqQy+/rPyPzyfpsGwm 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: From: Minwoo Signed-off-by: Minwoo Jo 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; }