From patchwork Wed Sep 27 16:22:19 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Stefan Roesch X-Patchwork-Id: 13401341 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 E89C2E82CB2 for ; Wed, 27 Sep 2023 16:22:52 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 1E2F58D009B; Wed, 27 Sep 2023 12:22:49 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 0F6468D0098; Wed, 27 Sep 2023 12:22:49 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C8F128D009C; Wed, 27 Sep 2023 12:22:48 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id B3A368D0098 for ; Wed, 27 Sep 2023 12:22:48 -0400 (EDT) Received: from smtpin18.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 852BB160255 for ; Wed, 27 Sep 2023 16:22:48 +0000 (UTC) X-FDA: 81282896016.18.5EB431A Received: from 66-220-144-179.mail-mxout.facebook.com (66-220-144-179.mail-mxout.facebook.com [66.220.144.179]) by imf10.hostedemail.com (Postfix) with ESMTP id E09C6C0016 for ; Wed, 27 Sep 2023 16:22:46 +0000 (UTC) Authentication-Results: imf10.hostedemail.com; dkim=none; spf=neutral (imf10.hostedemail.com: 66.220.144.179 is neither permitted nor denied by domain of shr@devkernel.io) smtp.mailfrom=shr@devkernel.io; dmarc=none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1695831767; 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:in-reply-to:references:references; bh=ekjszAzCmJfqkUJ4plMMs/7OpHGzCtoSFSggNtD/+So=; b=PENnmRC3KOJxUPbaQmfUCiy0hgKN4obgpBBEiIFJ9vlFPt4V5uRJ6z6opORJOhEc0eQl9u C386yHOzP49KycVTkJbLZKeZs+GHpfRtJ+v85XX1hm/3JErSRGaQwM3iNyUKw/ExhaZ5/p x5cFlkj05ecRoxdB19bQNgNnmikIWL4= ARC-Authentication-Results: i=1; imf10.hostedemail.com; dkim=none; spf=neutral (imf10.hostedemail.com: 66.220.144.179 is neither permitted nor denied by domain of shr@devkernel.io) smtp.mailfrom=shr@devkernel.io; dmarc=none ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1695831767; a=rsa-sha256; cv=none; b=EM7mD1oAUpyW/3R2cwfvI/VvnY4U4lB7WVrr4QJRchbbeli4LfuNvkwdhzIrmKflJFQwfr LwXFOIEr6LCh/B8GuWuKmCeo0s46kjlEKL0qlTvkbDOXVdj1WUkdLQm2jZF5gYakLiimr8 TT2vZob+useYzyP6rOW0cr65dbxKDGY= Received: by devbig1114.prn1.facebook.com (Postfix, from userid 425415) id 3B9BDCA4DC0F; Wed, 27 Sep 2023 09:22:32 -0700 (PDT) From: Stefan Roesch To: kernel-team@fb.com Cc: shr@devkernel.io, akpm@linux-foundation.org, david@redhat.com, hannes@cmpxchg.org, riel@surriel.com, linux-kernel@vger.kernel.org, linux-mm@kvack.org Subject: [PATCH v4 1/4] mm/ksm: add "smart" page scanning mode Date: Wed, 27 Sep 2023 09:22:19 -0700 Message-Id: <20230927162222.3827551-2-shr@devkernel.io> X-Mailer: git-send-email 2.39.3 In-Reply-To: <20230927162222.3827551-1-shr@devkernel.io> References: <20230927162222.3827551-1-shr@devkernel.io> MIME-Version: 1.0 X-Rspamd-Queue-Id: E09C6C0016 X-Rspam-User: X-Stat-Signature: jk8afe74j56nmnbpbo9sw4mity1qfcup X-Rspamd-Server: rspam01 X-HE-Tag: 1695831766-120261 X-HE-Meta: U2FsdGVkX1+8py5Y97uCjia9ZI8a5qAOaDr0COdU7dXe6LMg2nWYlCBc7XvkYJQT7ocVGHj067tOPW06XzAHCskb8A0M/h7qE+n7AV9WM7odGZKp/bNJglDEtzAYLyBrl4Q6U6xmvpbspP+jYRGaplsb25dasW4fC+1qdZ359SYSTQigIitjyKZp0CvNjMjZJRDJ6PXjSbtTD5yCkXNd5g1wrdtGO/Lu1ApCQP3G6cHW3Fv+t76xH1Fq+sgQDzbiX/+ylBnaViaMThIcFF6KNJMfVDQaClQFG4TJqSRNzQpzOW3YXMl0gXyqXo4UITrqs3dZpECsOynbJL4MGjQYP5Ab+fSgoEJzLiDLK7zUcpVzoAGSdKVwJmmQbMVMjtrAzsned2gNjxMc+zXF4Dkgog4eO2uKxIkXwwkorJA2awChuXUl+vBEz0eYMQheFarFqeVpqQ9PB30en4p2QJo2uBc0TSZSnuBAnzHsSLrSLfQQ+4DBQ22T72M1W6+0+PTZX2eqqYu3aYtMEiUR1LFSD7AqbKeo66bNeoQdMu7DIwYQ5243HR6KtLgtiTIUrFbclnZznR8XR4wR0yM7dkl3iAQuKBZ+EgHZbVNK5lPnkFm8YK97nktwM/FE3FDM7LCXL5xbhDUJxasro+xrBh+Hc0AlcushwE+SQbEyueM2Zo9MJfg+UqMnHcJQZi+jwIHZWMOjMV+/as70uMD3Anl24sM6v0+fk31hfPUDZYca+NWkdgcVYlCWJsrySanD8J8K2gZ4MNhdWv5gDDtlceYpEutbtmOTsoNFnOgINPWMYmjYbYN/KvjGZ4l7KgM60QUYvAUcYmH2ZPgmyci/HI4GxboaKQ4xQKm4b9n7FtfAwa8a5IkxykinaM+AdaFQTaBF4GbuhFUwzznRGgUPw/O9opsb1QmbDCs5vefmcJeGYBu0gTVe2aRJqD6Muh/M4ZXAssv68RjnTQp93YQeAN6 QH16pJrs jaEP2HIMsnf2DS4ovdqPuRosFMsEw1A32yKwgkj0T0Az16fE= 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: 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 remaining_skips. age, is the KSM age and remaining_skips determines how often scanning of this page is skipped. The age field is incremented each time the page is scanned and the page cannot be de- duplicated. age updated is capped at U8_MAX. 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 enabled by default and can be disabled 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. Signed-off-by: Stefan Roesch Reviewed-by: David Hildenbrand --- mm/ksm.c | 103 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 103 insertions(+) diff --git a/mm/ksm.c b/mm/ksm.c index 981af9c72e7a..c0a2e7759365 100644 --- a/mm/ksm.c +++ b/mm/ksm.c @@ -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 + * @remaining_skips: how many scans to skip */ struct ksm_rmap_item { struct ksm_rmap_item *rmap_list; @@ -205,6 +209,8 @@ struct ksm_rmap_item { struct mm_struct *mm; unsigned long address; /* + low bits used for flags below */ unsigned int oldchecksum; /* when unstable */ + rmap_age_t age; + rmap_age_t remaining_skips; union { struct rb_node node; /* when node of unstable tree */ struct { /* when listed from stable tree */ @@ -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 = 1; + /* The number of zero pages which is placed by KSM */ unsigned long ksm_zero_pages; @@ -2305,6 +2314,73 @@ static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot, return rmap_item; } +/* + * Calculate skip age for the ksm page age. The age determines how often + * de-duplicating has already been tried unsuccessfully. If the age is + * smaller, the scanning of this page is skipped for less scans. + * + * @age: rmap_item age of page + */ +static unsigned int skip_age(rmap_age_t age) +{ + if (age <= 3) + return 1; + if (age <= 5) + return 2; + if (age <= 8) + return 4; + + return 8; +} + +/* + * Determines if a page should be skipped for the current scan. + * + * @page: page to check + * @rmap_item: associated rmap_item of page + */ +static bool should_skip_rmap_item(struct page *page, + struct ksm_rmap_item *rmap_item) +{ + rmap_age_t age; + + if (!ksm_smart_scan) + return false; + + /* + * Never skip pages that are already KSM; pages cmp_and_merge_page() + * will essentially ignore them, but we still have to process them + * properly. + */ + if (PageKsm(page)) + return false; + + age = rmap_item->age; + if (age != U8_MAX) + rmap_item->age++; + + /* + * Smaller ages are not skipped, they need to get a chance to go + * through the different phases of the KSM merging. + */ + if (age < 3) + return false; + + /* + * Are we still allowed to skip? If not, then don't skip it + * and determine how much more often we are allowed to skip next. + */ + if (!rmap_item->remaining_skips) { + rmap_item->remaining_skips = skip_age(age); + return false; + } + + /* Skip this page */ + rmap_item->remaining_skips--; + 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 +2485,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 (should_skip_rmap_item(*page, rmap_item)) + goto next_page; + ksm_scan.address += PAGE_SIZE; } else put_page(*page); @@ -3449,6 +3529,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 +3571,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, };