From mboxrd@z Thu Jan 1 00:00:00 1970 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 25033C46CA1 for ; Mon, 18 Sep 2023 17:23:05 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id ABF096B03F2; Mon, 18 Sep 2023 13:23:04 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A6F1F6B03F5; Mon, 18 Sep 2023 13:23:04 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 90FA76B03F6; Mon, 18 Sep 2023 13:23:04 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 7A0566B03F2 for ; Mon, 18 Sep 2023 13:23:04 -0400 (EDT) Received: from smtpin23.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 468D31A0275 for ; Mon, 18 Sep 2023 17:23:04 +0000 (UTC) X-FDA: 81250388688.23.C9258F1 Received: from out5-smtp.messagingengine.com (out5-smtp.messagingengine.com [66.111.4.29]) by imf02.hostedemail.com (Postfix) with ESMTP id C817380009 for ; Mon, 18 Sep 2023 17:23:01 +0000 (UTC) Authentication-Results: imf02.hostedemail.com; dkim=pass header.d=devkernel.io header.s=fm3 header.b=DtNkukzI; dkim=pass header.d=messagingengine.com header.s=fm2 header.b=LCR516+M; spf=pass (imf02.hostedemail.com: domain of shr@devkernel.io designates 66.111.4.29 as permitted sender) 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=1695057782; 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-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=jVQBYyUTJJ4XZImO4TIi7G98RVRFmRGFf34VYApWKsE=; b=xdL2UoaFbylh4yGgl/f1WzE8l96WYYesXgV91VBf//FsrY/NjkRVETTZ+Obi9xSdiXqHeJ eiFHgxyZKu87aUT5JN8V/1HZaalB62zIw/ibcGvMEE7PraoXWJ8eFiwTO0IqJkcZaOWBS5 tpefyya7pdOPzpL5dTwl7Kv8pCLw9ds= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1695057782; a=rsa-sha256; cv=none; b=BIc3hE5bPs1nigysCIWM1EempGtCiT5AbGO9V8lQfl0nvEN6Q4eqJJze3ykjBATiaAXmVs T0Onc7uRpaiDVLVQnxSZetKJpSq48fMFuVu8bw8Om9GZPt8iN2GcNh+Rm1XzUyHbqzn+xm YWG1W4Mp3YU91+MiyGoTeK+09JR/bYM= ARC-Authentication-Results: i=1; imf02.hostedemail.com; dkim=pass header.d=devkernel.io header.s=fm3 header.b=DtNkukzI; dkim=pass header.d=messagingengine.com header.s=fm2 header.b=LCR516+M; spf=pass (imf02.hostedemail.com: domain of shr@devkernel.io designates 66.111.4.29 as permitted sender) smtp.mailfrom=shr@devkernel.io; dmarc=none Received: from compute5.internal (compute5.nyi.internal [10.202.2.45]) by mailout.nyi.internal (Postfix) with ESMTP id 0AC3D5C0080; Mon, 18 Sep 2023 13:23:01 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute5.internal (MEProxy); Mon, 18 Sep 2023 13:23:01 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=devkernel.io; h= cc:cc:content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:sender :subject:subject:to:to; s=fm3; t=1695057781; x=1695144181; bh=jV QBYyUTJJ4XZImO4TIi7G98RVRFmRGFf34VYApWKsE=; b=DtNkukzIOJ62UAnf6C KwefgWfUIwqrKygEjFOrzSE3ooTaNAtV3WPx3IUoER9uDpPOU3K637wOPoNWRBTg /eA72QSO5wTidirja8BeVTr396neEnId0eb4BWPMtw7qB4h7m3r3LuHY9gJihqPN LsHfvGYDREabYoeLTqFMKzogxqu75tA1XxuTz+g7sVYv4aRdIFBOkHDRTgK3lRuo PrkmPZyeOtHA02FiVZk1S4p7KDohNX8vJU1wns/ixbvDdxJboHggxZZrvgOHIej7 KvUC5wn5BzIncIjd24ezQTjG4vye+uMSjZd778L+Fd5BXr4QTeFQPxiGJ5M/UnUY sGig== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:sender:subject :subject:to:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm2; t=1695057781; x=1695144181; bh=jVQBYyUTJJ4XZ ImO4TIi7G98RVRFmRGFf34VYApWKsE=; b=LCR516+Mdbgg4foFRNqTUNuQXxt5C AmY0ru7m8gWXUjXtAy/GcW/7mdAm6F1jtfQh0UlGMXlI6u0vowkU4Bqg+SE7b7HV ZvXtm6QuTl/0BqdGp4Qdq3kaJKNWnRB8YSaKXFWRZgQG5UEKcljMvvmPmUA6KktS NElPWfSygEe/PYsT1lN899qYhZxSaXH7H74xoFhpiFQDKnf2/9+Yk7M+kwGiIEbH WOsPeqo8VGxzJqiQtai+sBmlzaw9phR/TXNCAm86QAAwBzwIKPyu82kcmB13jEgG 0oo/33O02n/E9d4vbYX30A+CSkAKcWiLuo9PPGAzQHyqYe0aDCv8EkDNA== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedviedrudejkedgudduudcutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpehffgfhvfevufffjgfkgggtsehttdertddtredtnecuhfhrohhmpefuthgv fhgrnhcutfhovghstghhuceoshhhrhesuggvvhhkvghrnhgvlhdrihhoqeenucggtffrrg htthgvrhhnpeevlefggffhheduiedtheejveehtdfhtedvhfeludetvdegieekgeeggfdu geeutdenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpe hshhhrseguvghvkhgvrhhnvghlrdhioh X-ME-Proxy: Feedback-ID: i84614614:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 18 Sep 2023 13:22:59 -0400 (EDT) References: <20230912175228.952039-1-shr@devkernel.io> <20230912175228.952039-2-shr@devkernel.io> <6447ab02-1a22-efe4-68c9-4f595e2499fc@redhat.com> <5bf3e7ad-b666-ae88-449a-074f17a9cbba@redhat.com> User-agent: mu4e 1.10.1; emacs 28.2.50 From: Stefan Roesch To: David Hildenbrand Cc: kernel-team@fb.com, akpm@linux-foundation.org, hannes@cmpxchg.org, riel@surriel.com, linux-kernel@vger.kernel.org, linux-mm@kvack.org Subject: Re: [PATCH v1 1/4] mm/ksm: add "smart" page scanning mode Date: Mon, 18 Sep 2023 10:22:09 -0700 In-reply-to: <5bf3e7ad-b666-ae88-449a-074f17a9cbba@redhat.com> Message-ID: MIME-Version: 1.0 Content-Type: text/plain X-Rspamd-Queue-Id: C817380009 X-Rspam-User: X-Rspamd-Server: rspam11 X-Stat-Signature: 7dguj77kgnpsunqu8wdi8cjmq1ki4ze1 X-HE-Tag: 1695057781-580332 X-HE-Meta: U2FsdGVkX18u+yYKPg1b+XAvmS6Hk7l80f91OrECDpr0MZvF83P1jnBxg43LjVTOLoFu9iEYfe0AEjDHUHJyHaz4vLBzAgTTaVr4zrtTRyP6p1Se78Ad9BMKtbo9kDgsSuyAAVxXA1wnLTEiKXd+u1pnWh/Jaql0LMByc7lASkCERlTXuKmu3I9kyiw/otBQffnq3n7D0ctfyjp3/quslN57agBAfnGH507hAmplekJGXyiOkmY/ynB6LyPLdQxDI6Tw7D7Onraa6PmAxPkqwaZpQfv5VibWlI1gfaYCN0rr37q3vI3zr18evnFdHLUvTFyZxf9D8quuIQ3L/b0SIbthBEPLX6Lk1+swyutETKBDYKDyh499ODqWJok0pmJUU3/hPYjY6wF6lpwSYDS/u6XuMLtCYHK7WOsu02WM4k1BOlv2U+BtMUxgGdvcHsK0VBqlyONML+34oBceSgrzngNwsZsLcpmAgVCrIgaRaz5cAlOaSzOvrLWiEACaFskvEe9WuLGS5z8aPE31sXgGi7BpraQFBxm8hT5Ljoha5Z6uOHPEKSbkyPQ954JE1MiHJEUsSqpxagqTXpoTKdRU0fVpLEQHKWH5+zZ+Y+iFIoVfpZXPme8jYNijNJOgnPsYTj7grR0h+96GQiqouG9y403MceXXL7AW880uF1QhjuZBR6KJGn22GsxWHJEFkQ8tW52P8YhG15jgylSjKegV1sfZsIKYPNa+oQr8AsTiUlFB56Uc2Tv7yz6VQbKIZcVqiSZHtQGKvpGys+piPkFnrPSs90ajkmfjf48eZBQYau1/wVsMoyaH/0BjXyGhmQdiKJUpu1xS/3FpNV4C+7glRQukeZJFYiIlN8OR+GzAP2dzmdkgmEHYSnmUN77Y8e3Jc5Q0T5Hp+fJ8uQBmGD1kwx/gtiPRfl6kT1rXnNKniZPFCoCPfKWnHohLM9tl4Y+FJb56TOSArhLhmdzn2mV 3U9KBlWz luoTD1Tu8pf+bKIWiQXfmV5OH5/w8e8FHkFwcFp9RdfTX1LUQW9e/OCX0MhcXDFwXucgaE4chUWxtz5NDXoHamNtYS7BxwFprcq4mPvQvPaBBlXDSbuRSByNY+/80Bl9wJlBd4/+x9PrNKhg8DHqqGL936YPg8vCqs3wAifftj2yVYBidOInyrv3H6Q/MP8Jc1CtK 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: David Hildenbrand writes: > On 18.09.23 18:18, Stefan Roesch wrote: >> David Hildenbrand writes: >> >>> On 12.09.23 19:52, Stefan Roesch wrote: >>>> 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 skip_age. age, is the KSM age and skip_page is the age for how >>>> long page scanning of this page is skipped. The age field is incremented >>>> each time the page is scanned and the page cannot be de-duplicated. >>>> 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 currently disable by default and can be enabled 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 >>>> --- >>>> mm/ksm.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ >>>> 1 file changed, 75 insertions(+) >>>> diff --git a/mm/ksm.c b/mm/ksm.c >>>> index 981af9c72e7a..bfd5087c7d5a 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 >>>> + * @skip_age: skip rmap item until age reaches skip_age >>>> */ >>>> struct ksm_rmap_item { >>>> struct ksm_rmap_item *rmap_list; >>>> @@ -212,6 +216,8 @@ struct ksm_rmap_item { >>>> struct hlist_node hlist; >>>> }; >>>> }; >>>> + rmap_age_t age; >>>> + rmap_age_t skip_age; >>>> }; >>>> #define SEQNR_MASK 0x0ff /* low bits of unstable tree seqnr */ >>>> @@ -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; >>>> + >>>> /* The number of zero pages which is placed by KSM */ >>>> unsigned long ksm_zero_pages; >>>> @@ -2305,6 +2314,45 @@ static struct ksm_rmap_item >>>> *get_next_rmap_item(struct ksm_mm_slot *mm_slot, >>>> return rmap_item; >>>> } >>>> +static unsigned int inc_skip_age(rmap_age_t age) >>>> +{ >>>> + if (age <= 3) >>>> + return 1; >>>> + if (age <= 5) >>>> + return 2; >>>> + if (age <= 8) >>>> + return 4; >>>> + >>>> + return 8; >>>> +} >>>> + >>>> +static bool skip_rmap_item(struct page *page, struct ksm_rmap_item *rmap_item) >>>> +{ >>>> + rmap_age_t age; >>>> + >>>> + if (!ksm_smart_scan) >>>> + return false; >>>> + >>>> + if (PageKsm(page)) >>>> + return false; >>> >>> >>> I'm a bit confused about this check here. scan_get_next_rmap_item() would return >>> a PageKsm() page and call cmp_and_merge_page(). >>> >>> cmp_and_merge_page() says: "first see if page can be merged into the stable >>> tree" >>> >>> ... but shouldn't a PageKsm page *already* be in the stable tree? >>> >>> Maybe that's what cmp_and_merge_page() does via: >>> >>> kpage = stable_tree_search(page); >>> if (kpage == page && rmap_item->head == stable_node) { >>> put_page(kpage); >>> return; >>> } >>> >>> >>> Hoping you can enlighten me :) >>> >> The above description sounds correct. During each scan we go through all >> the candidate pages and this includes rmap_items that maps to KSM pages. >> The above check simply skips these pages. > > Can we add a comment why we don't skip them? Like > > /* > * Never skip pages that are already KSM; pages cmp_and_merge_page() > * will essentially ignore them, but we still have to process them > * properly. > */ > I'll add the comment in the next version. >> >>>> + >>>> + age = rmap_item->age++; >>> >>> Can't we overflow here? Is that desired, or would you want to stop at the >>> maximum you can store? >>> >> Yes, we can overflow here and it was a deliberate choice. If we overflow >> after we tried unsuccessfully for 255 times, we re-start with shorter >> skip values, but that should be fine. In return we avoid an if statement. >> The age is defined as unsigned. > > Can we make that explicit instead? Dealing with implicit overflows really makes > the code harder to grasp. > I'll make it explicit. >> >>>> + if (age < 3) >>>> + return false; >>>> + >>>> + if (rmap_item->skip_age == age) { >>>> + rmap_item->skip_age = 0; >>>> + return false; >>>> + } >>>> + >>>> + if (rmap_item->skip_age == 0) { >>>> + rmap_item->skip_age = age + inc_skip_age(age); >>> >>> Can't you overflow here as well? >>> >> Yes, you can. See the above discussion. This skip_age is also an >> unsigned value. > > Dito. > I'll make it explicit. >> >>>> + remove_rmap_item_from_tree(rmap_item); >>> >>> >>> Can you enlighten me why that is required? >>> >> This is required for age calculation and BUG_ON check in >> remove_rmap_item_from_tree. If we don't call remove_rmap_item_from_tree, >> we will hit the BUG_ON for the skipped pages later on. > > I see, thanks!