Re: [PATCH v2 2/2] mm: Compute first_set_pte to eliminate evaluating redundant ranges

[Dev Jain <dev.jain@arm.com>]

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 <dev.jain@arm.com> 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 <ryan.roberts@arm.com>
>>>> Signed-off-by: Dev Jain <dev.jain@arm.com>
>>>> ---
>>>>    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