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 E6E1BC46CA1 for ; Mon, 18 Sep 2023 16:54:17 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4B9116B03E8; Mon, 18 Sep 2023 12:54:17 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 467DE6B03E9; Mon, 18 Sep 2023 12:54:17 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2BA776B03EA; Mon, 18 Sep 2023 12:54:17 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 0EF276B03E8 for ; Mon, 18 Sep 2023 12:54:17 -0400 (EDT) Received: from smtpin02.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id C44A0160483 for ; Mon, 18 Sep 2023 16:54:16 +0000 (UTC) X-FDA: 81250316112.02.45341D9 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by imf27.hostedemail.com (Postfix) with ESMTP id 8629C40026 for ; Mon, 18 Sep 2023 16:54:14 +0000 (UTC) Authentication-Results: imf27.hostedemail.com; dkim=pass header.d=redhat.com header.s=mimecast20190719 header.b=K4WqOYyk; spf=pass (imf27.hostedemail.com: domain of david@redhat.com designates 170.10.129.124 as permitted sender) smtp.mailfrom=david@redhat.com; dmarc=pass (policy=none) header.from=redhat.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1695056054; 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:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=ZjTO4gcP//nadUXVqj2GJXmrM//YlftQ98yc81HL0J0=; b=v6ivsArGfZzoDNwNc/O1McVKt/hpaxTbgHl8+eFawZb5TNusjcxX46yT8WEB0M/qFXwwDR WNwO2E8niQ5rAOESl70c7FVO9CXjos/SJP8Dro78JScIPpxsg3S4TAXd2g1wOTFLhBxd8U sG/8IZmbTLqIt8yfXdCj4ituKZ43fGU= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1695056054; a=rsa-sha256; cv=none; b=XivivIGwT9n1iFV+ul7tH4tpFWzlMSgKS8M8Xe5A4Y86C6jqIab5enCwCq27fozMbk4auv iGMlN+TXZLG4ljgYlMCz91N5oeQmfAb4h+XLmedEprk+rULorAnEb6Qlv0oHELxNyxP8At dtF4VkWzpCpHfKxdQzy9qMXasaWtmW4= ARC-Authentication-Results: i=1; imf27.hostedemail.com; dkim=pass header.d=redhat.com header.s=mimecast20190719 header.b=K4WqOYyk; spf=pass (imf27.hostedemail.com: domain of david@redhat.com designates 170.10.129.124 as permitted sender) smtp.mailfrom=david@redhat.com; dmarc=pass (policy=none) header.from=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1695056053; h=from:from: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:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=ZjTO4gcP//nadUXVqj2GJXmrM//YlftQ98yc81HL0J0=; b=K4WqOYyk3HTMjvuKdglp8DlDU34+UXtVezCZOV1AUiGpf57LHjOe03NAMNXhEXYj8g/Onx usLnSs3mfPKPg7vvzXtbPDhRWxvKpaxPxeocAvZmbkQSDt0dwDoWQVA7bo5udXCtGMV7nr M+9UCTfZofftDduDPwI1eq8U5oXF3bY= Received: from mail-wr1-f72.google.com (mail-wr1-f72.google.com [209.85.221.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-241-LZZtGvZmN0qXZJ1jc3AYXg-1; Mon, 18 Sep 2023 12:54:12 -0400 X-MC-Unique: LZZtGvZmN0qXZJ1jc3AYXg-1 Received: by mail-wr1-f72.google.com with SMTP id ffacd0b85a97d-320bf1de0a6so904900f8f.3 for ; Mon, 18 Sep 2023 09:54:12 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1695056051; x=1695660851; h=content-transfer-encoding:in-reply-to:subject:organization:from :references:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=ZjTO4gcP//nadUXVqj2GJXmrM//YlftQ98yc81HL0J0=; b=xED5EQ7YZRpdCPiofnZbqXQIiEGJMHRDRQGjsgDY/o19S8hGs4Ae8MD1mq5Q3lCCLL WRt8g9sZEMndDyiy5dqigHJAnm0b4NlmsRy6qsj4WSb44ZQp+bDVvIh+4m3sjpWLxwTr 4/YiJAbXkqiG5BdPQaIZKSvfBwYMa7xXJLG90e2y3Clrv8fsPuEldvYpLq99h3ZJBvvy HHepnrd8nTMOwUZ4CKeibyF3e9winPsHkAV1OHiS4qdYX0nXbeOIEInHhjP9bBxMYPvu 4FWF0ecb2QzAgUQetdDYFGaTD41VcthKIfihcZQirUJELGZDoTBjeT8fKTB2SFaviVFi 6kog== X-Gm-Message-State: AOJu0YzKxulRVc//dtcthtBywtQRwagfUMONnsYwn3AMM/5CMuIhFrsq 3yP98fKYRNE8rVUQrJc9jggKrnyBWFwzhn5L0sVYFjArPqFiTouJ2AAEW5PrPmUNX1WK+RNcEr4 CAOMXC/9uLZw= X-Received: by 2002:adf:f4c4:0:b0:31a:b3aa:d19b with SMTP id h4-20020adff4c4000000b0031ab3aad19bmr7868091wrp.23.1695056051160; Mon, 18 Sep 2023 09:54:11 -0700 (PDT) X-Google-Smtp-Source: AGHT+IGSeM+WczwIA0+o+BhBMrxmfrQVLuEo097XU3cOCry/hI/9ThoSt5ebPOS9r5LJ4D6k5M7gTA== X-Received: by 2002:adf:f4c4:0:b0:31a:b3aa:d19b with SMTP id h4-20020adff4c4000000b0031ab3aad19bmr7868075wrp.23.1695056050706; Mon, 18 Sep 2023 09:54:10 -0700 (PDT) Received: from ?IPV6:2003:cb:c702:9d00:cf36:8603:a1f5:d07? (p200300cbc7029d00cf368603a1f50d07.dip0.t-ipconnect.de. [2003:cb:c702:9d00:cf36:8603:a1f5:d07]) by smtp.gmail.com with ESMTPSA id j3-20020a056000124300b0031fb91f23e9sm13227346wrx.43.2023.09.18.09.54.09 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 18 Sep 2023 09:54:10 -0700 (PDT) Message-ID: <5bf3e7ad-b666-ae88-449a-074f17a9cbba@redhat.com> Date: Mon, 18 Sep 2023 18:54:09 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.13.0 To: Stefan Roesch Cc: kernel-team@fb.com, akpm@linux-foundation.org, hannes@cmpxchg.org, riel@surriel.com, linux-kernel@vger.kernel.org, linux-mm@kvack.org References: <20230912175228.952039-1-shr@devkernel.io> <20230912175228.952039-2-shr@devkernel.io> <6447ab02-1a22-efe4-68c9-4f595e2499fc@redhat.com> From: David Hildenbrand Organization: Red Hat Subject: Re: [PATCH v1 1/4] mm/ksm: add "smart" page scanning mode In-Reply-To: X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Stat-Signature: prgcp1i1gc16kkykz9k557us5ouikp86 X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: 8629C40026 X-Rspam-User: X-HE-Tag: 1695056054-776370 X-HE-Meta: U2FsdGVkX1+Ht4x54Xnrqlhpzw5m7lFWGeJBK3R1FV35A6D7J6dZ00YHxaMw98rpAIM/xvUeKoOxqWjAxUpFaRSP2BksNWcssp0asZwsG7Ki7wEMezpn4BKm1Z10+A+i30HKTwmVLlnYZ/xseoLUYfaQHLdgbX2PMt3MXfQz45khrAcfbPQ0FsVxHLp4ikv1KWoBbgmxFNt7q9UuUNLtGwa9G6lhCEDYb/enzpf9Sle53/i33pJGov+1jEn3NabxqIAtZj8m0gTFGX7iFpcChxtDErG5182AZ/UqYPazlviTZvYvX2D1pmGEW0KUdtL5LW0D1zOHlVDLtqRawAEq9pQ1Jc3RM0K7Ak0kAAokH+QUt5bnc1wfcZUBrFe63EsI6rXqy7/mzr40XOkB61yXStAge8qdCvjPCPSJA6DlRGiBMKL2smXGPKtogeBhewEnaXCGxM6OdIEZBzWRRsmHVPOYHBfYB6bc9SldTvU5ILe9sNFOZogcKVL87/No4+OkfUHcG/03wvjOV+PsSFtp+Q1jxsM6we9TBUNcAKsDYwDZcBV8hkL1VHplyr/jZr9cwdJ2OeqJJ7Pkq1hehBVWVWVVlNT+0SmqGJXN1/8yPDBFXTgICmAymqQ2PuWPXwbRBaBAdJu2jtRQ7G0X730v9JELFo/RCgk5I1yZtPa+j85u7bAMN/+EIl1zCLsMJAs3A6hMM6OPyI2H9x+UuKWZL/1vf9Egfjq6NrT9gSW79ZV+BRQDRpIa5kwcGTjwq+RD67nVi5TCdCh22UG6ManYmWdke7TEFos611O/4ZjQteiENHgbzjl9rCmkhywx7aESF0AuqoK49d7DsiXoJHpg4aXdL+fpgxkGOUZOCzuu9OivhQApSyA7pJutDWvCvGfqB8HF9vKOp0YG1iK9pjwnuqqIOF4+q9/RihKn9SXBUTmtuUGlEjNaZFc9mHHQxb/zneEnKoFjxlv7CushUiL 7/mon7Zi JrfwEQqpxx6Kq7d/HmV0OuICVR26Y+vK0y+ohqakmoCS+K0toVfHB14fvL5AquQkBTurb9cJ+8ofLR9/w79BI432JCMcb2gK1S3enjlDADuFhbMK8Q5OOYIczjcOMxHkD9kDzjRQrd93nDuBegDya6qbxYznv3ZxVX6VOziQoioVgV2o0DlVIl2CwTIyPTNkivGkHLH9ztTZ6AXd+j4AVFLIG8Du6x4Tx1sX5dWVVZBgJlLmw7B1yWpxz6ldaALWNqRU8FcgISWpUgLiS6yGKYkvW67f0quvAcK0K+wtGukMXA4NBBbpG6FHNz9Dw9N2ufzTGXeoibQNuLVG3RXzaw2pXvigKAST25ZhFI+mL4D/+M5ZDnneUZOuIGDkdFxbgLJDL3hm1isLgkWO2HwNOpuxkAg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000008, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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. */ > >>> + >>> + 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. > >>> + 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. > >>> + 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! -- Cheers, David / dhildenb