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 9C16ACF58C0 for ; Fri, 20 Sep 2024 04:05:07 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8F0AA6B0082; Fri, 20 Sep 2024 00:05:06 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 8A0626B0083; Fri, 20 Sep 2024 00:05:06 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 78ECC6B0085; Fri, 20 Sep 2024 00:05:06 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 5A07C6B0082 for ; Fri, 20 Sep 2024 00:05:06 -0400 (EDT) Received: from smtpin05.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id CC9C4161164 for ; Fri, 20 Sep 2024 04:05:04 +0000 (UTC) X-FDA: 82583776128.05.8DA1823 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by imf25.hostedemail.com (Postfix) with ESMTP id 1EBECA0011 for ; Fri, 20 Sep 2024 04:05:01 +0000 (UTC) Authentication-Results: imf25.hostedemail.com; dkim=none; spf=pass (imf25.hostedemail.com: domain of dev.jain@arm.com designates 217.140.110.172 as permitted sender) smtp.mailfrom=dev.jain@arm.com; dmarc=pass (policy=none) header.from=arm.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1726804988; 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=ZrlcRw/pxS1s2H+0qNmHYzjmd3gpwc0/i+Cs+OLVO6I=; b=Y+ka7pa01XRBWnGfZqvuCFkstLPJcquPEzvOmQYa901XaAwVcQyA5axTvKGbPjoPbI3Q/H njtq8achnd6j/AwG1ibvJ1zuW43NOhUBAksAPZ6XFUoyjb82P5UmzVOjvs60N0b/DPX2/l qBd+gJRrtUSq2dY1iZPmB+aYdqGd/r8= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1726804988; a=rsa-sha256; cv=none; b=LmU4GPC4uFicJ4IqUJW9QbQri5kK9R8Cd4Y+M/p+Blbr3nlIWDnGhJlGBs+aO851bAmlF7 smfThpiZplgHjSZTiea8uFMS0L/EV+vsWbxL40zfQZhGeny4wVt7Ik6io5r+rnfhpouWyc U2Zv1eh3y7fu/FgsGz36AN1tLMlhVeM= ARC-Authentication-Results: i=1; imf25.hostedemail.com; dkim=none; spf=pass (imf25.hostedemail.com: domain of dev.jain@arm.com designates 217.140.110.172 as permitted sender) smtp.mailfrom=dev.jain@arm.com; dmarc=pass (policy=none) header.from=arm.com 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 76F65FEC; Thu, 19 Sep 2024 21:05:30 -0700 (PDT) Received: from [10.162.43.22] (e116581.arm.com [10.162.43.22]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id CDAD23F71A; Thu, 19 Sep 2024 21:04:56 -0700 (PDT) Message-ID: Date: Fri, 20 Sep 2024 09:34:53 +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: Ryan Roberts , Barry Song Cc: akpm@linux-foundation.org, david@redhat.com, willy@infradead.org, 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> <8700274f-b521-444e-8d17-c06039a1376c@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-Stat-Signature: 7xyp6f7hac8u1cwtorc5ub8rnsiojmr1 X-Rspamd-Queue-Id: 1EBECA0011 X-Rspam-User: X-Rspamd-Server: rspam08 X-HE-Tag: 1726805101-800027 X-HE-Meta: U2FsdGVkX19GK2QMmyJNTbI5Uplgm2yDFiXI2Zq/1MxZjbp5qhj5OrcEe5Sm2/1/UsIGELwaM8QZsdT2OwY7sIPAV8t5iZ1he7y3M6v5EZaf4zc28Y7MOOUB+T2iOpdvUFnNNODlfnmjRn26R9xly/9CAQmnvcLKR7OtTM7yydRMrAcMdbSbf4PS7H2/rezBvWnwjZdTa7X91/LI3hfGqaODjXWq1BDAu2m/XgGS47Cj0pxe8GXM4TxSoLCuyxqW7k3Cp/5R/qQvEOPqt1YagzihlbEUCOGmQkaz8zUWWfi2wiV3GkUo3i5UfSdL1Mk9dz/fuX5fgL1NEbhMqGoEmjQpsAORNCmYzeiD/rqE8hlzqKJ3NBXMQwKz94CG3fdLPjQgPDRDTI+Vwftzp6+B4loZAb9qC/5gyaTJ+FnGfmk9YIKdoWiOXDJo3bm3OCovLMOOixnAND7V2p/KamzA9kQk2HfcS3xEh+v/bLhpnVou6RfLIab9Dwc9IR4d/3cDDBGU3l4OAPwbEqGqkyWqS1d2bBxbEOkU+rocRr8QbdVjraQA4KzGZuoG7ipBXdErblTMvv0ZqnaK2jJY4aLBOcyuwOfb4nU5bkB/txs+FShZDJg0EFp/D/6Yu20TA4bzZ4M2y1kr423KDST7x2B6SKmmfUj57WIbx777sevYSqrSvhufogwvGiDwSYIfQMPgYYOwK7+qUCq1HPuNw1p86OURkNSEXh76xHw21ZCUh9nT4xwoC3EJSFrs/rdOD46G7d/PRGTp0K7dW96NMeWvb+KWviyIYTtFJRH/kMQtz3ppTIPbg3m9s5NJeur3Ic8XnbgBXFiV7eL0agM+r0RydruNwq9Dw4nKR5KuFbV8OPyTeqhxHOmsPWSengPNqJFQPp0P0mqFaDVlOJHir6BZcDg2WAMMxc9CVO7Bd5SlVrUkKjGf1+j2BpUb7Cx2ML0GwFFtSGpWKHkZyKfyrKm ajQF25gg nkCul/SKi24LPvUzIJ7UpUuShVfGJjA8JdNgG6oIBjzMrwZO9EnOyr8djWt4TjOOJHaW2nJsw+YSA0svPPupeFr9D5pGFl0uYwW8EWOYXDNn6SMg10Kj7T1tIg+48QzpS1YKDEI+FpJpcpeFHhdc9T9InLp9LktUroPf+SiOCKLCDW4PJEv6lVdmZLU5oQLmaFF2uWzAiWZTQjgomNGL0nLKzCL7cX0XW0/ZQACPAoNIpvMwLZlRTWPIODM4E1GGeZaRf9BtmexSBdcgpVSDnxqTVnTn0T0K8WxSf5ON2ES5mSNtaW/nWpfAUfvzpRhetvt0mCdRAl0QNfhFTLt3gu7F6rkjuyhTGDcyqiB4O2beRaxBbGdYOnkz0p/JnADQd6Ddhp6hTT0tIZCwh85815ym9/6itFxe7EZWwR3GuAX0HhUjee4/z0bFj9NWxB8P0SkD/X2YPEZVJ6o294vGlBRJTrEurHeuVqXdk 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 22:25, Ryan Roberts wrote: > On 19/09/2024 09:40, Dev Jain wrote: >> 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 > Some brief comments on the test code: > > - You don't need to enable/disable the top-level control. Regardless, I don't > think this breaks the benchmark. > > - I think you have an off-by-1 in your for loop condition: > > for (unsigned long i = 1; (i * border) < size; ++i) { > > I think this needs to be: > > for (unsigned long i = 1; (i * border) <= size; ++i) { > > It just means that the final 32K block will get a single 32K mapping. > > - You're measuring the whole program; including mmap/munmap and > enabling/disabling mTHP. It would be much better to just measure the loop that > writes to each page after mTHP is enabled. > > > I modified the code to iterate for 10 seconds and on each iteration, measure > only the time spent in the interesting loop. Running on Apple M2 VM: > > Before the change: > > ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte > Average: 0.070028 seconds per GB (iterations=98) > ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte > Average: 0.068495 seconds per GB (iterations=96) > ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte > Average: 0.070207 seconds per GB (iterations=93) > > After the change: > > ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte > Average: 0.076923 seconds per GB (iterations=88) > ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte > Average: 0.072206 seconds per GB (iterations=96) > ubuntu@ubuntuvm:~/scan-pte$ sudo ./scan-pte > Average: 0.072397 seconds per GB (iterations=89) > > So this looks pretty clearly slower to me. So suggest we shouldn't take this patch. Thanks for testing! > > >> 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 > What HW did you measure this on? I'm guessing this is measuring multiple > iterations, otherwise it looks extremely slow. If you were measuring on FVP, for > example, that would not give representative performance numbers. I measured with qemu. > > Thanks, > Ryan > >> 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