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 7CBB9CE8D5F for ; Thu, 19 Sep 2024 08:40:19 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id B523B6B0082; Thu, 19 Sep 2024 04:40:18 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id B01D86B0083; Thu, 19 Sep 2024 04:40:18 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 9F05A6B0085; Thu, 19 Sep 2024 04:40:18 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 82CD36B0082 for ; Thu, 19 Sep 2024 04:40:18 -0400 (EDT) Received: from smtpin27.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 01FB8AACF6 for ; Thu, 19 Sep 2024 08:40:17 +0000 (UTC) X-FDA: 82580840916.27.653E366 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by imf19.hostedemail.com (Postfix) with ESMTP id 261971A000D for ; Thu, 19 Sep 2024 08:40:14 +0000 (UTC) Authentication-Results: imf19.hostedemail.com; dkim=none; dmarc=pass (policy=none) header.from=arm.com; spf=pass (imf19.hostedemail.com: domain of dev.jain@arm.com designates 217.140.110.172 as permitted sender) smtp.mailfrom=dev.jain@arm.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1726735132; a=rsa-sha256; cv=none; b=hYy6wDnoKa1hbHARXXCvN/VSgb6KEn00co+NoNzigqirnaXXifchEJHBp/XgLGNf2UaACc np9amN4VkeaZnQQCuesUkgAAsGVHBiD1nkhreNQIcq+/iJHyv945GJZhpZ2o/DktjyW5QS Hpt4G3/D/Q/gzNGJ39VvYFxwL6dSdAI= ARC-Authentication-Results: i=1; imf19.hostedemail.com; dkim=none; dmarc=pass (policy=none) header.from=arm.com; spf=pass (imf19.hostedemail.com: domain of dev.jain@arm.com designates 217.140.110.172 as permitted sender) smtp.mailfrom=dev.jain@arm.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1726735132; 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; bh=J9bo5b/r/KisW82cu4rb+W37tiD/t64pKa9LH5A8AkM=; b=uKU+yt4MT8eZSu+Io9jfs69lsvm/QL/NmDLyVIBQN3vidWni+CAkE6iURHM+iBg7h39N6B rY/9WB9cw6R4zFlh06uv2dUZiMdaFG6Xck4ZXVTm44dDKyTXZhJeAixkzfqylcbT2YcyC/ r6QnOS0WmLD1lxyEBfJRI/lm6/P5oTs= Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id BC3641007; Thu, 19 Sep 2024 01:40:43 -0700 (PDT) Received: from [10.162.41.21] (e116581.arm.com [10.162.41.21]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id E9EC63F71A; Thu, 19 Sep 2024 01:40:09 -0700 (PDT) Message-ID: <8700274f-b521-444e-8d17-c06039a1376c@arm.com> Date: Thu, 19 Sep 2024 14:10:03 +0530 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH v2 2/2] mm: Compute first_set_pte to eliminate evaluating redundant ranges To: Barry Song Cc: akpm@linux-foundation.org, david@redhat.com, willy@infradead.org, ryan.roberts@arm.com, anshuman.khandual@arm.com, hughd@google.com, ioworker0@gmail.com, wangkefeng.wang@huawei.com, baolin.wang@linux.alibaba.com, gshan@redhat.com, linux-kernel@vger.kernel.org, linux-mm@kvack.org References: <20240916110754.1236200-1-dev.jain@arm.com> <20240916110754.1236200-3-dev.jain@arm.com> Content-Language: en-US From: Dev Jain In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 261971A000D X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: stfw3ujk9bfgmn8tf9gnfqiycis1hfx8 X-HE-Tag: 1726735214-230661 X-HE-Meta: U2FsdGVkX1/OA/qa8EfZ7cg3QrW6MAZeyDw1FU+F89ikLEhgn63E1t8Nf9LWcEjFpNkTrw+g2KDWXadjHlf76UZRBrvUVIH0isBNWJavkFqVIRDoDomxG8hTBkbPtrasc5EolupHykq8uFpB0MtasySQetH0vQXYdyfF8Nnh7975Ty+ip74sm7cABGJDRCOfsyrGsb2EAiiZZl3uUUysLs2pmaiRdUvxbM2mg5F2veV/V5lkCNo9yt6Y0pZjF8ESp+gujO05KorptHSytec0CKgOcNQ9OAifFgXAw5RbarXOoUXtVG9gHMRdawr4UhsUpVgtcg4wx4m6Qt6WNpSV3yqvX+SkI9g3d/J49udOAX+oNFhLAZKCzfc1VmcprhApbq/Vs1SsYILwkiYS6xQ3n2fVrHA0/bzxw9eXYFqZP1MluaGdhhBlxllF4Q/+EdgUiSRYB/it0rElXQYR5JGHLvR1XxJURzkbzr48ityH6ZEDkXQ3AaIp4hSiVBhq/zRBag8+y/N59C4tmCrvbtfwGjfo0f9cihBuP8/lQbMYEBdPmrAAtggLJ55ZEi1H0FLdVPJe0K0CjJpqhtWraaQL7nisUH0FvVZbPMp0PBSq7RDN2y39FZMPQzTjlSMoYZeVdg8E/bQQrL3xSo/NS0yY7bTIApkZq6uUnqopYFyd977bwJdfxUr0obK4YNCoKBrTkBo6yYAL9P0ltbPLRGHIvaAep8033WCIvKRuZasT3HsEYtH+p+nyNd6XICUPmntovfqYz/4Kmf9IYWB6+8QR4p1r78FJamdl9JBzxRv4Os+Fk+jzW4wTTZdG+z6F40RI0IX85HSxQQmr3tm1qBkEE8vFg9WdVFtlZXUwOc9mB54HrI1PdR0Pxtfb0AbgKfdR4bOU+u8XW80l9Ql2mgbXZW9tnpHFYpY+OhQ4MqiPv+FXykHDQICXvTbrXIBzjEG45qTA7ENp/GTBh5BaxW6 RRcmy1JR EZrKzzyoAA9QSdcfC7j03iF/B16TUy/Itx+AeuWhRtil32lJHuHWXPJh4X00t/scXGMvbO8z3wK/SbpyaFTm0Nuhz9xHNhZjtEbIUmg87Ba8bXtXeHBioivz5E3l4EecclcUrQVcrMaoFfaEm/tOm1ZuV4WCPJCe1787A6xZ0y6xSfurP67U+VerJU7ML7ZR6U+2Z6O7pF9zcU859XA19SlZew8LGAm00GhMjO8fiTXuBoUSCoctPtmHWsJTsleJ+RvYCVj5YrOSVQ3Po+sjkNtwBbwu22mJvfXxg7dfQ7gRW0K6MAvgZZBW+xWClRDS3/soT53K/W2wHzvQSmPngiJyeWZXbu+h0WeHt0OL+7SVGoOWtXh5iMAWBLCdZMJO0k4S+mDsax/+f6EYHhAc1EUzGj1SBi/81550yc76SmjsJK6Sms6LediPul0lOXSmDg/n4IwUcgOpeYNHXy3ODZGUCjq2tTNETXP/1SRPTmT2e31mmQSveEAvMMKC1k1s6LG/q 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: On 9/19/24 07:04, Barry Song wrote: > On Mon, Sep 16, 2024 at 11:08 PM Dev Jain wrote: >> For an mTHP allocation, we need to check, for every order, whether for >> that order, we have enough number of contiguous PTEs empty. Instead of >> iterating the while loop for every order, use some information, which >> is the first set PTE found, from the previous iteration to eliminate >> some cases. The key to understanding the correctness of the patch >> is that the ranges we want to examine form a strictly decreasing >> sequence of nested intervals. > Could we include some benchmark data here, as suggested by Ryan in this thread? > > https://lore.kernel.org/linux-mm/58f91a56-890a-45d0-8b1f-47c4c70c9600@arm.com/ Can you please verify and get some numbers for the following program, because if I am doing this correctly, it would be a regression :) https://www.codedump.xyz/cpp/Zuvf8FwvRPH21UO2 The program does this: disable THP completely -> mmap 1G VMA -> touch the last page of a 32K sized boundary. That is, 0th till 32K/4K - 2 pages are empty, while the 32K/4K - 1'th page is touched, and so on -> madvise the entire VMA -> enable all THPs except 2M -> touch all pages. Therefore, we have 0 - 6 PTEs empty, 7th is filled, and so on. Eventually, kernel will fall down to finding 4 contiguous PTEs empty and allocate 4K * 4 = 16K mTHP. The result without the patches: real: 8.250s user: 0.941s sys: 7.077s real: 8.175s user: 0.939s sys: 7.021s With the patches: real: 8.584s user: 1.089s sys: 7.234s real: 8.429s user: 0.954s sys: 7.220s You can change the #iterations in the for loop to magnify this, and the current code surprisingly wins. > >> Suggested-by: Ryan Roberts >> Signed-off-by: Dev Jain >> --- >> mm/memory.c | 20 ++++++++++++++++++-- >> 1 file changed, 18 insertions(+), 2 deletions(-) >> >> diff --git a/mm/memory.c b/mm/memory.c >> index 8bb1236de93c..e81c6abe09ce 100644 >> --- a/mm/memory.c >> +++ b/mm/memory.c >> @@ -4633,10 +4633,11 @@ static struct folio *alloc_anon_folio(struct vm_fault *vmf) >> { >> struct vm_area_struct *vma = vmf->vma; >> #ifdef CONFIG_TRANSPARENT_HUGEPAGE >> + pte_t *first_set_pte = NULL, *align_pte, *pte; >> unsigned long orders; >> struct folio *folio; >> unsigned long addr; >> - pte_t *pte; >> + int max_empty; >> gfp_t gfp; >> int order; >> >> @@ -4671,8 +4672,23 @@ static struct folio *alloc_anon_folio(struct vm_fault *vmf) >> order = highest_order(orders); >> while (orders) { >> addr = ALIGN_DOWN(vmf->address, PAGE_SIZE << order); >> - if (pte_range_none(pte + pte_index(addr), 1 << order) == 1 << order) >> + align_pte = pte + pte_index(addr); >> + >> + /* Range to be scanned known to be empty */ >> + if (align_pte + (1 << order) <= first_set_pte) >> + break; >> + >> + /* Range to be scanned contains first_set_pte */ >> + if (align_pte <= first_set_pte) >> + goto repeat; >> + >> + /* align_pte > first_set_pte, so need to check properly */ >> + max_empty = pte_range_none(align_pte, 1 << order); >> + if (max_empty == 1 << order) >> break; >> + >> + first_set_pte = align_pte + max_empty; >> +repeat: >> order = next_order(&orders, order); >> } >> >> -- >> 2.30.2 >> > Thanks > barry