[PATCH] mm: fix align-error when get_addr in unmapped_area_topdown

[PATCH] mm: fix align-error when get_addr in unmapped_area_topdown

[lipeifeng]

From: lipeifeng <lipeifeng@oppo.com>

when we found a suitable gap_end(> info->high_limit), gap_end
must be set to info->high_limit. And we will get the gap_end
after computing highest gap address at the desired alignment.

2096 found:
2097         if (gap_end > info->high_limit)
2098                 gap_end = info->high_limit;
2099
2100 found_highest:
2101         gap_end -= info->length;
2102         gap_end -= (gap_end - info->align_offset) & info->align_mask;
2103
2104         VM_BUG_ON(gap_end < info->low_limit);
2105         VM_BUG_ON(gap_end < gap_start);
2106         return gap_end;

so we must promise: info->high_limit - info->low_limit >=
info->length + info->align_mask.
Or in rare cases(info->high_limit - info->low_limit <
info->length + info->align_mask) we will get the addr in
align-error if found suitable gap_end(> info->high_limit).

Signed-off-by: lipeifeng <lipeifeng@oppo.com>
---
 mm/mmap.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/mm/mmap.c b/mm/mmap.c
index 30e33d3..a28ea5c 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -2009,7 +2009,6 @@ static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)
 	if (length < info->length)
 		return -ENOMEM;
 
-	length = info->length;
 	/*
 	 * Adjust search limits by the desired length.
 	 * See implementation comment at top of unmapped_area().
@@ -2021,6 +2020,8 @@ static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)
 
 	if (info->low_limit > high_limit)
 		return -ENOMEM;
+
+	length = info->length;
 	low_limit = info->low_limit + length;
 
 	/* Check highest gap, which does not precede any rbtree node */
-- 
2.7.4

Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown

[Andrew Morton]

On Tue, 12 Apr 2022 16:10:14 +0800 lipeifeng@oppo.com wrote:

> From: lipeifeng <lipeifeng@oppo.com>
> 
> when we found a suitable gap_end(> info->high_limit), gap_end
> must be set to info->high_limit. And we will get the gap_end
> after computing highest gap address at the desired alignment.
> 
> 2096 found:
> 2097         if (gap_end > info->high_limit)
> 2098                 gap_end = info->high_limit;
> 2099
> 2100 found_highest:
> 2101         gap_end -= info->length;
> 2102         gap_end -= (gap_end - info->align_offset) & info->align_mask;
> 2103
> 2104         VM_BUG_ON(gap_end < info->low_limit);
> 2105         VM_BUG_ON(gap_end < gap_start);
> 2106         return gap_end;
> 
> so we must promise: info->high_limit - info->low_limit >=
> info->length + info->align_mask.
> Or in rare cases(info->high_limit - info->low_limit <
> info->length + info->align_mask) we will get the addr in
> align-error if found suitable gap_end(> info->high_limit).
> 

Thanks.

What are the runtime affects of this bug, and how are you able to
trigger it?

> --- a/mm/mmap.c
> +++ b/mm/mmap.c
> @@ -2009,7 +2009,6 @@ static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)
>  	if (length < info->length)
>  		return -ENOMEM;
>  
> -	length = info->length;
>  	/*
>  	 * Adjust search limits by the desired length.
>  	 * See implementation comment at top of unmapped_area().
> @@ -2021,6 +2020,8 @@ static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)
>  
>  	if (info->low_limit > high_limit)
>  		return -ENOMEM;
> +
> +	length = info->length;
>  	low_limit = info->low_limit + length;
>  
>  	/* Check highest gap, which does not precede any rbtree node */
> -- 
> 2.7.4

Re: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown

[lipeifeng]

Hi Andrew：

Excuse me, here is a question to consult:

Why did the two patches suddenly disappear without any email or notice for us?
And they had been merged in linux-next.git on April 5 and 13.


1. mm-modify-the-method-to-search-addr-in-unmapped_area_topdown.patch added to -mm tree
This patch should soon appear at
https://ozlabs.org/~akpm/mmots/broken-out/mm-modify-the-method-to-search-addr-in-unmapped_area_topdown.patch
and later at
https://ozlabs.org/~akpm/mmotm/broken-out/mm-modify-the-method-to-search-addr-in-unmapped_area_topdown.patch


2. mm-fix-align-error-when-get_addr-in-unmapped_area_topdown.patch added to -mm tree
This patch should soon appear at
https://ozlabs.org/~akpm/mmots/broken-out/mm-fix-align-error-when-get_addr-in-unmapped_area_topdown.patch
and later at
https://ozlabs.org/~akpm/mmotm/broken-out/mm-fix-align-error-when-get_addr-in-unmapped_area_topdown.patch

Hope to receive your reply and thank you for your guidance.
lipeifeng@oppo.com
 
From: lipeifeng@oppo.com
Date: 2022-04-13 11:28
To: akpm
CC: michel; hughd; linux-mm; linux-kernel; Barry Song; zhangshiming
Subject: Re: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown

and 
Hi Andrew Morton：

> What are the runtime affects of this bug?
It will give a bad addr which is not at the desired aligment to user if trigger, 
which maybe cause some device addr access exception.

My understanding was that it is really rare to trigger and i don't know
whether it will tirgger in user-scence, the reason is in "how to trigger it".

> how are you able to trigger it?
My understanding was that it is really rare to trigger,
only if the following conditions are met:

1. (info->high_limit - info->low_limit) < (info->length + info->align_mask)
2. There is a addr space in mm->mm_rb
     ----
       |
       |
       |
      gap_end = vma_start_gap(vma0_uesd)    -------------------------------- -------------------|
       |                                                                                                                                           |
       |                                                                                                                                           |
       |                                                                                                                                           |
      info->high_limit                   -------------------|                                                                   |   > info->length
       |                                                                       |                                                                   |  
       |                                                                       |                                                                   |
       |                                                                       |   < info->length +   info->align_mask     |
      info->low_limit                                                |                                                                   |
       |                                                                       |                                                                   |
     gap_start =  vma_end_gap(vma1_used)    -----|----------------------------------------------|       
       |
    
In the above case,:
2.1 we will get gep_end firstly：
>	while (true) {
>	/* Visit right subtree if it looks promising */
>	gap_start = vma->vm_prev ? vm_end_gap(vma->vm_prev) : 0;
>	if (gap_start <= high_limit && vma->vm_rb.rb_right) {
>	struct vm_area_struct *right =
>	rb_entry(vma->vm_rb.rb_right,
>	struct vm_area_struct, vm_rb);
>	if (right->rb_subtree_gap >= length) {
>	vma = right;
>	continue;
>	}
>	}
>
> check_current:
>	/* Check if current node has a suitable gap */
>	gap_end = vm_start_gap(vma);
>	if (gap_end < low_limit)
>	return -ENOMEM;
>	if (gap_start <= high_limit &&
>	   gap_end > gap_start && gap_end - gap_start >= length) {
>	gap_end_tmp = gap_end - info->length;
>	gap_end_tmp -= (gap_end_tmp - info->align_offset) & info->align_mask;
>	if (gap_end_tmp >= gap_start)
>	goto found;
>
>	}

2.2 we clip it with the original high_limit:
but if info->high_limit - info->low_limit < info->length + info->align_mask,
we can not promise get a addr at the desired alignment, it will cause to return a addr in align error.
   
> found:
>	/* We found a suitable gap. Clip it with the original high_limit. */
>	if (gap_end > info->high_limit)
>	gap_end = info->high_limit;
>
> found_highest:
>	/* Compute highest gap address at the desired alignment */
>	gap_end -= info->length;
>	gap_end -= (gap_end - info->align_offset) & info->align_mask;
>	VM_BUG_ON(gap_end < info->low_limit);
>	VM_BUG_ON(gap_end < gap_start);
>	return gap_end;


The patch must require: info->high_limit - gap_start  > info->length + info->align_mask.
So that when gap_end = info->high_limit, we can get a right addr at the desired alignment by gap_end.

Thank you very much indeed for asking such nice problems 
so that i can try my best to explain how the patch work.

pls let me know if there are any problem in the patch, thxs.

lipeifeng@oppo.com
 
From: Andrew Morton
Date: 2022-04-13 05:22
To: lipeifeng
CC: michel; hughd; linux-mm; linux-kernel; 21cnbao; zhangshiming
Subject: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown
On Tue, 12 Apr 2022 16:10:14 +0800 lipeifeng@oppo.com wrote:
 
> From: lipeifeng <lipeifeng@oppo.com>
>
> when we found a suitable gap_end(> info->high_limit), gap_end
> must be set to info->high_limit. And we will get the gap_end
> after computing highest gap address at the desired alignment.
>
> 2096 found:
> 2097         if (gap_end > info->high_limit)
> 2098                 gap_end = info->high_limit;
> 2099
> 2100 found_highest:
> 2101         gap_end -= info->length;
> 2102         gap_end -= (gap_end - info->align_offset) & info->align_mask;
> 2103
> 2104         VM_BUG_ON(gap_end < info->low_limit);
> 2105         VM_BUG_ON(gap_end < gap_start);
> 2106         return gap_end;
>
> so we must promise: info->high_limit - info->low_limit >=
> info->length + info->align_mask.
> Or in rare cases(info->high_limit - info->low_limit <
> info->length + info->align_mask) we will get the addr in
> align-error if found suitable gap_end(> info->high_limit).
>
 
Thanks.
 
What are the runtime affects of this bug, and how are you able to
trigger it?
 
> --- a/mm/mmap.c
> +++ b/mm/mmap.c
> @@ -2009,7 +2009,6 @@ static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)
>  if (length < info->length)
>  return -ENOMEM;
> 
> -	length = info->length;
>  /*
>  * Adjust search limits by the desired length.
>  * See implementation comment at top of unmapped_area().
> @@ -2021,6 +2020,8 @@ static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)
> 
>  if (info->low_limit > high_limit)
>  return -ENOMEM;
> +
> +	length = info->length;
>  low_limit = info->low_limit + length;
> 
>  /* Check highest gap, which does not precede any rbtree node */
> --
> 2.7.4

Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown

[Andrew Morton]

On Sun, 1 May 2022 10:26:35 +0800 "lipeifeng@oppo.com" <lipeifeng@oppo.com> wrote:

> Why did the two patches suddenly disappear without any email or notice for us?
> And they had been merged in linux-next.git on April 5 and 13.

They caused me some merge issues against mapletree, which I had
resolved.  Mapletree is dropped at present so I set these patches aside
until the next version of the mapletree patches are available.


I've been holding your patches until Michel Lespinasse has had time to
review them (and hopefully explain them to me ;)).  Please review
earlier comments which Michel has provided and ensure that those
comments have been fully addressed so we can hopefully move forward on
this.

Re: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown

[lipeifeng]

Hi Andrew：

Thanks for your quick response.

> They caused me some merge issues against mapletree, which I had
> resolved.  Mapletree is dropped at present so I set these patches aside
> until the next version of the mapletree patches are available.

Do we have a definite time for the next available version of the mapletree patches?
Excuse me, is it possible for our patch to be independent of mapletree and brought in separately?

> I've been holding your patches until Michel Lespinasse has had time to
> review them (and hopefully explain them to me ;)).  Please review
> earlier comments which Michel has provided and ensure that those
> comments have been fully addressed so we can hopefully move forward on
> this.

We will reply soon if Mr.Lespinasse provideds any advices or question.
And I haven't received any reply from Mr.Lespinasse yet, pls let me know
if i missed the reply.

Thank you very much indeed.

lipeifeng@oppo.com
 
From: Andrew Morton
Date: 2022-05-02 09:10
To: lipeifeng@oppo.com
CC: michel; hughd; linux-mm; linux-kernel; Barry Song; zhangshiming; peifengl55
Subject: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown
On Sun, 1 May 2022 10:26:35 +0800 "lipeifeng@oppo.com" <lipeifeng@oppo.com> wrote:
 
> Why did the two patches suddenly disappear without any email or notice for us?
> And they had been merged in linux-next.git on April 5 and 13.
 
They caused me some merge issues against mapletree, which I had
resolved.  Mapletree is dropped at present so I set these patches aside
until the next version of the mapletree patches are available.
 
 
I've been holding your patches until Michel Lespinasse has had time to
review them (and hopefully explain them to me ;)).  Please review
earlier comments which Michel has provided and ensure that those
comments have been fully addressed so we can hopefully move forward on
this.
 
 

Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown

[Andrew Morton]

On Mon, 2 May 2022 11:33:18 +0800 "lipeifeng@oppo.com" <lipeifeng@oppo.com> wrote:

> Hi Andrew：
> 
> Thanks for your quick response.
> 
> > They caused me some merge issues against mapletree, which I had
> > resolved.  Mapletree is dropped at present so I set these patches aside
> > until the next version of the mapletree patches are available.
> 
> Do we have a definite time for the next available version of the mapletree patches?

I merged v2 a couple of days ago.  It should be in mm-unstable then
linux-next early next week.

> Excuse me, is it possible for our patch to be independent of mapletree and brought in separately?

Well, the changelog was rather unclear on the real-world end-user
visible effects of the defect.  When these prioritization decisions are
to be made, it really helps to have a clear view of the impact to our
users.

> 
> > I've been holding your patches until Michel Lespinasse has had time to
> > review them (and hopefully explain them to me ;)).  Please review
> > earlier comments which Michel has provided and ensure that those
> > comments have been fully addressed so we can hopefully move forward on
> > this.
> 
> We will reply soon if Mr.Lespinasse provideds any advices or question.
> And I haven't received any reply from Mr.Lespinasse yet, pls let me know
> if i missed the reply.

There was a big conference last week.

Re: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown

[lipeifeng]

Hi Andrew：

Thank you for your response.

> > > They caused me some merge issues against mapletree, which I had
> > > resolved.  Mapletree is dropped at present so I set these patches aside
>> > until the next version of the mapletree patches are available.
>>
>> Do we have a definite time for the next available version of the mapletree patches?
 
> I merged v2 a couple of days ago.  It should be in mm-unstable then
> linux-next early next week.

Ok, is "v2 merged" the patch from me?
1. mm-modify-the-method-to-search-addr-in-unmapped_area_topdown.patch added to -mm tree
This patch should soon appear at
https://ozlabs.org/~akpm/mmots/broken-out/mm-modify-the-method-to-search-addr-in-unmapped_area_topdown.patch
and later at
https://ozlabs.org/~akpm/mmotm/broken-out/mm-modify-the-method-to-search-addr-in-unmapped_area_topdown.patch


2. mm-fix-align-error-when-get_addr-in-unmapped_area_topdown.patch added to -mm tree
This patch should soon appear at
https://ozlabs.org/~akpm/mmots/broken-out/mm-fix-align-error-when-get_addr-in-unmapped_area_topdown.patch
and later at
https://ozlabs.org/~akpm/mmotm/broken-out/mm-fix-align-error-when-get_addr-in-unmapped_area_topdown.patch


> > Excuse me, is it possible for our patch to be independent of mapletree and brought in separately?
 
> Well, the changelog was rather unclear on the real-world end-user
> visible effects of the defect.  When these prioritization decisions are
> to be made, it really helps to have a clear view of the impact to our
> users.

Well, we had found that some apps-crash(TIF_32BIT) due to "Out of memory",  which the single largest remaining
free-addr-space is 12Mbytes in some case, we found that the processes wound fail to alloc
a 12Mbytes(align 1M) in the old methods so that Out-of-Memory.
such as Wechat and others Android apps.

> >
> > > I've been holding your patches until Michel Lespinasse has had time to
> > > review them (and hopefully explain them to me ;)).  Please review
> > > earlier comments which Michel has provided and ensure that those
> > > comments have been fully addressed so we can hopefully move forward on
> > > this.
> >
> > We will reply soon if Mr.Lespinasse provideds any advices or question.
> > And I haven't received any reply from Mr.Lespinasse yet, pls let me know
> > if i missed the reply.
>
> There was a big conference last week.

I missed it and if there any problems about the patches which need me to answer,
pls let me know and i hope i can give a clear reply.

Thank you very much indeed.

lipeifeng@oppo.com
 
From: Andrew Morton
Date: 2022-05-08 05:59
To: lipeifeng@oppo.com
CC: michel; hughd; linux-mm; linux-kernel; Barry Song; zhangshiming; peifengl55
Subject: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown
On Mon, 2 May 2022 11:33:18 +0800 "lipeifeng@oppo.com" <lipeifeng@oppo.com> wrote:
 
> Hi Andrew：
>
> Thanks for your quick response.
>
> > They caused me some merge issues against mapletree, which I had
> > resolved.  Mapletree is dropped at present so I set these patches aside
> > until the next version of the mapletree patches are available.
>
> Do we have a definite time for the next available version of the mapletree patches?
 
I merged v2 a couple of days ago.  It should be in mm-unstable then
linux-next early next week.
 
> Excuse me, is it possible for our patch to be independent of mapletree and brought in separately?
 
Well, the changelog was rather unclear on the real-world end-user
visible effects of the defect.  When these prioritization decisions are
to be made, it really helps to have a clear view of the impact to our
users.
 
>
> > I've been holding your patches until Michel Lespinasse has had time to
> > review them (and hopefully explain them to me ;)).  Please review
> > earlier comments which Michel has provided and ensure that those
> > comments have been fully addressed so we can hopefully move forward on
> > this.
>
> We will reply soon if Mr.Lespinasse provideds any advices or question.
> And I haven't received any reply from Mr.Lespinasse yet, pls let me know
> if i missed the reply.
 
There was a big conference last week.

Re: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown

[Michel Lespinasse]

On Mon, May 02, 2022 at 11:33:18AM +0800, lipeifeng@oppo.com wrote:
> Hi Andrew：
> 
> Thanks for your quick response.
> 
> > They caused me some merge issues against mapletree, which I had
> > resolved.  Mapletree is dropped at present so I set these patches aside
> > until the next version of the mapletree patches are available.
> 
> Do we have a definite time for the next available version of the mapletree patches?
> Excuse me, is it possible for our patch to be independent of mapletree and brought in separately?

I think it's unavoidable that there will be a conflict with maple tree
because they are changing the way we track gaps between vmas.

> > I've been holding your patches until Michel Lespinasse has had time to
> > review them (and hopefully explain them to me ;)).  Please review
> > earlier comments which Michel has provided and ensure that those
> > comments have been fully addressed so we can hopefully move forward on
> > this.
> 
> We will reply soon if Mr.Lespinasse provideds any advices or question.
> And I haven't received any reply from Mr.Lespinasse yet, pls let me know
> if I missed the reply.

This previous thread is very relevant here:
https://lore.kernel.org/lkml/CANN689G6mGLSOkyj31ympGgnqxnJosPVc4EakW5gYGtA_45L7g@mail.gmail.com/

I am sorry that I had confused you with the original poster on that
thread - your proposed changes are very similar. That said, I still
have the exact same concerns that I had at the time. The current
search algorithm is guaranteed to find a gap in O(log N) time, if there
is an available gap of size (requested_size + alignment - page_size).
The modified search only requires an available gap of the requested
size and alignment, but it can take O(N) time which might be too slow.
Maybe we could afford the slow search if it's only used as a fallback
when the fast search fails, but very few people would ever execute
that fallback and that makes it hard to test / easy for bugs to hide in.

If I understand your message at
https://lore.kernel.org/lkml/202204241833454848958@oppo.com/ ,
it seems like some andoid apps such as wechat are filling up
a 32-bit address space such as there is no 13MB gap available anymore
(as would be required by the current search), but there are still some
12MB gaps aligned on a 1MB boundary, which they are then trying to
allocate from. It seems very odd to me that one would find themselves
in that situation, could you give us some details as to how that happened ?
Do you know what the app is trying to do to fill the address space that way ?
Also, why is this odd behavior considered to be a kernel issue - was the
app previously running on a (quite old !) kernel that didn't have the fast
vma gap search, and is now failing when ported to a more recent kernel ?

> Thank you very much indeed.
> 
> lipeifeng@oppo.com
>  
> From: Andrew Morton
> Date: 2022-05-02 09:10
> To: lipeifeng@oppo.com
> CC: michel; hughd; linux-mm; linux-kernel; Barry Song; zhangshiming; peifengl55
> Subject: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown
> On Sun, 1 May 2022 10:26:35 +0800 "lipeifeng@oppo.com" <lipeifeng@oppo.com> wrote:
>  
> > Why did the two patches suddenly disappear without any email or notice for us?
> > And they had been merged in linux-next.git on April 5 and 13.
>  
> They caused me some merge issues against mapletree, which I had
> resolved.  Mapletree is dropped at present so I set these patches aside
> until the next version of the mapletree patches are available.
>  
>  
> I've been holding your patches until Michel Lespinasse has had time to
> review them (and hopefully explain them to me ;)).  Please review
> earlier comments which Michel has provided and ensure that those
> comments have been fully addressed so we can hopefully move forward on
> this.
>  
>  

Re: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown

[lipeifeng]

Hi michel:

Thank you for your reply.
I am sorry for my late reply.

> This previous thread is very relevant here:
> https://lore.kernel.org/lkml/CANN689G6mGLSOkyj31ympGgnqxnJosPVc4EakW5gYGtA_45L7g@mail.gmail.com/
 
> I am sorry that I had confused you with the original poster on that
> thread - your proposed changes are very similar. That said, I still
> have the exact same concerns that I had at the time. The current
> search algorithm is guaranteed to find a gap in O(log N) time, if there
> is an available gap of size (requested_size + alignment - page_size).
> The modified search only requires an available gap of the requested
> size and alignment, but it can take O(N) time which might be too slow.
> Maybe we could afford the slow search if it's only used as a fallback
> when the fast search fails, but very few people would ever execute
> that fallback and that makes it hard to test / easy for bugs to hide in.

In my opions, my new methods to search addr take O(log N) time too,
is it right? i will only add more action to judge if the space is available
at the same time.

> If I understand your message at
> https://lore.kernel.org/lkml/202204241833454848958@oppo.com/ ,
> it seems like some andoid apps such as wechat are filling up
> a 32-bit address space such as there is no 13MB gap available anymore
> (as would be required by the current search), but there are still some
> 12MB gaps aligned on a 1MB boundary, which they are then trying to
> allocate from. It seems very odd to me that one would find themselves
> in that situation, could you give us some details as to how that happened ?
> Do you know what the app is trying to do to fill the address space that way ?
> Also, why is this odd behavior considered to be a kernel issue - was the
> app previously running on a (quite old !) kernel that didn't have the fast
> vma gap search, and is now failing when ported to a more recent kernel ?

1. Wechat just one of the case we found to space unsuccessfully by the old way,
others app, like sgame、taobao and so on， which have been found the same
issue(The allocated size is 1M~12M).  Unfortunately, we can not see how the 
above apps operate.

2. the patch will sovle the another problems, it can add more vma-merge in some
case. e.g., some gpu will alloc vma-space  on a 1MB boundary, if there are much
vma-free-space(less than 1M+64kytes) in system, it can not be alloced to 64kbtes
on a 1MB boundary, so that more vma would be need.



lipeifeng@oppo.com
 
From: Michel Lespinasse
Date: 2022-05-09 19:45
To: lipeifeng@oppo.com
CC: akpm; michel; hughd; linux-mm; linux-kernel; Barry Song; zhangshiming; peifengl55
Subject: Re: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown
On Mon, May 02, 2022 at 11:33:18AM +0800, lipeifeng@oppo.com wrote:
> Hi Andrew：
>
> Thanks for your quick response.
>
> > They caused me some merge issues against mapletree, which I had
> > resolved.  Mapletree is dropped at present so I set these patches aside
> > until the next version of the mapletree patches are available.
>
> Do we have a definite time for the next available version of the mapletree patches?
> Excuse me, is it possible for our patch to be independent of mapletree and brought in separately?
 
I think it's unavoidable that there will be a conflict with maple tree
because they are changing the way we track gaps between vmas.
 
> > I've been holding your patches until Michel Lespinasse has had time to
> > review them (and hopefully explain them to me ;)).  Please review
> > earlier comments which Michel has provided and ensure that those
> > comments have been fully addressed so we can hopefully move forward on
> > this.
>
> We will reply soon if Mr.Lespinasse provideds any advices or question.
> And I haven't received any reply from Mr.Lespinasse yet, pls let me know
> if I missed the reply.
 
This previous thread is very relevant here:
https://lore.kernel.org/lkml/CANN689G6mGLSOkyj31ympGgnqxnJosPVc4EakW5gYGtA_45L7g@mail.gmail.com/
 
I am sorry that I had confused you with the original poster on that
thread - your proposed changes are very similar. That said, I still
have the exact same concerns that I had at the time. The current
search algorithm is guaranteed to find a gap in O(log N) time, if there
is an available gap of size (requested_size + alignment - page_size).
The modified search only requires an available gap of the requested
size and alignment, but it can take O(N) time which might be too slow.
Maybe we could afford the slow search if it's only used as a fallback
when the fast search fails, but very few people would ever execute
that fallback and that makes it hard to test / easy for bugs to hide in.
 
If I understand your message at
https://lore.kernel.org/lkml/202204241833454848958@oppo.com/ ,
it seems like some andoid apps such as wechat are filling up
a 32-bit address space such as there is no 13MB gap available anymore
(as would be required by the current search), but there are still some
12MB gaps aligned on a 1MB boundary, which they are then trying to
allocate from. It seems very odd to me that one would find themselves
in that situation, could you give us some details as to how that happened ?
Do you know what the app is trying to do to fill the address space that way ?
Also, why is this odd behavior considered to be a kernel issue - was the
app previously running on a (quite old !) kernel that didn't have the fast
vma gap search, and is now failing when ported to a more recent kernel ?
 
> Thank you very much indeed.
>
> lipeifeng@oppo.com
>  
> From: Andrew Morton
> Date: 2022-05-02 09:10
> To: lipeifeng@oppo.com
> CC: michel; hughd; linux-mm; linux-kernel; Barry Song; zhangshiming; peifengl55
> Subject: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown
> On Sun, 1 May 2022 10:26:35 +0800 "lipeifeng@oppo.com" <lipeifeng@oppo.com> wrote:
>  
> > Why did the two patches suddenly disappear without any email or notice for us?
> > And they had been merged in linux-next.git on April 5 and 13.
>  
> They caused me some merge issues against mapletree, which I had
> resolved.  Mapletree is dropped at present so I set these patches aside
> until the next version of the mapletree patches are available.
>  
>  
> I've been holding your patches until Michel Lespinasse has had time to
> review them (and hopefully explain them to me ;)).  Please review
> earlier comments which Michel has provided and ensure that those
> comments have been fully addressed so we can hopefully move forward on
> this.
>  
>  

Re: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown

[Michel Lespinasse]

On Mon, May 16, 2022 at 10:43:39AM +0800, lipeifeng@oppo.com wrote:
> Thank you for your reply.
> I am sorry for my late reply.

I understand, I was pretty slow to answer myself.
Let's stop it there with the apologies :)

> > This previous thread is very relevant here:
> > https://lore.kernel.org/lkml/CANN689G6mGLSOkyj31ympGgnqxnJosPVc4EakW5gYGtA_45L7g@mail.gmail.com/
>
> > I am sorry that I had confused you with the original poster on that
> > thread - your proposed changes are very similar. That said, I still
> > have the exact same concerns that I had at the time. The current
> > search algorithm is guaranteed to find a gap in O(log N) time, if there
> > is an available gap of size (requested_size + alignment - page_size).
> > The modified search only requires an available gap of the requested
> > size and alignment, but it can take O(N) time which might be too slow.
> > Maybe we could afford the slow search if it's only used as a fallback
> > when the fast search fails, but very few people would ever execute
> > that fallback and that makes it hard to test / easy for bugs to hide in.
> 
> In my opions, my new methods to search addr take O(log N) time too,
> is it right? i will only add more action to judge if the space is available
> at the same time.

Candidate gaps, large enough for an unaligned allocation of the
desired size, can still be found in O(log N) time. The problem with
your proposal, is that it might inspect and reject many candidates due
to being too small for an aligned allocation. In the worst case, there
might be candidate gaps (again, large enough for an unaligned
allocation) between every VMA, and every one of them might be too
small for an aligned allocation. That worst case then becomes O(N) as
it has to inspect and reject every vma gap.

The current allocation code avoids that issue by only looking for gaps
of size (requested + alignment - page_size), which are guaranteed to
be large enough to satisfy an aligned allocation. By being more restrictive
in the gaps it is looking for, it guarantees that the first gap returned by
the O(log N) search will always work, thus keeping the overall complexity
at O(log N). Of course, the issue is if it is so restrictive that it won't
find any gaps - the design assumption was that virtual address space
shouldn't be so saturated to make this an issue, but that doesn't seem to
hold in the use case you are trying to address....

> > If I understand your message at
> > https://lore.kernel.org/lkml/202204241833454848958@oppo.com/ ,
> > it seems like some andoid apps such as wechat are filling up
> > a 32-bit address space such as there is no 13MB gap available anymore
> > (as would be required by the current search), but there are still some
> > 12MB gaps aligned on a 1MB boundary, which they are then trying to
> > allocate from. It seems very odd to me that one would find themselves
> > in that situation, could you give us some details as to how that happened ?
> > Do you know what the app is trying to do to fill the address space that way ?
> > Also, why is this odd behavior considered to be a kernel issue - was the
> > app previously running on a (quite old !) kernel that didn't have the fast
> > vma gap search, and is now failing when ported to a more recent kernel ?
> 
> 1. Wechat just one of the case we found to space unsuccessfully by the old way,
> others app, like sgame、taobao and so on， which have been found the same
> issue(The allocated size is 1M~12M). Unfortunately, we can not see how the 
> above apps operate.

Are such apps running on current android devices ? If so, how ? Do these
devices ship with kernel patches similar to what you are proposing ?
Or, are they based on a kernel that is so old (we are talking 8+ years now)
that it doesn't have the current fast gap search algorithm ?

--
Michel "walken" Lespinasse

Re: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown

[lipeifeng]

> > > If I understand your message atabd 
> > > https://lore.kernel.org/lkml/202204241833454848958@oppo.com/ ,
> > > it seems like some andoid apps such as wechat are filling up
> > > a 32-bit address space such as there is no 13MB gap available anymore
> > > (as would be required by the current search), but there are still some
> > > 12MB gaps aligned on a 1MB boundary, which they are then trying to
> > > allocate from. It seems very odd to me that one would find themselves
> > > in that situation, could you give us some details as to how that happened ?
> > > Do you know what the app is trying to do to fill the address space that way ?
> > > Also, why is this odd behavior considered to be a kernel issue - was the
> > > app previously running on a (quite old !) kernel that didn't have the fast
> > > vma gap search, and is now failing when ported to a more recent kernel ?
> >
> > 1. Wechat just one of the case we found to space unsuccessfully by the old way,
> > others app, like sgame、taobao and so on， which have been found the same
> > issue(The allocated size is 1M~12M). Unfortunately, we can not see how the
> > above apps operate.
 
> Are such apps running on current android devices ? If so, how ?
Yes, we found many apps(only 32-TIF) faces the problems.

> Do these devices ship with kernel patches similar to what you are proposing ?
We had make a series of patch to improve the performance of issue and we would
submit the patchs in the feature. We plan to submit them one by one.

The patch we discussed can improve some problems of the issue but not all.

> Or, are they based on a kernel that is so old (we are talking 8+ years now)
> that it doesn't have the current fast gap search algorithm ?
we found the issue in kernel-4.14/kernl-4.19/kernel-5.4 + androidQ/R.


I agree that your advices:
we could get_addr in fast gap search algorithm.
And try slow gap search glgorithm if we fail to get addr above.

Reasons are as follows:
1. only process-32-TIF would care about the thing we discussed.
2. Failing to get addr in first algorithm is the event of Low probability so that
   we could solve the problems we discussed with the fewest adverse effects.

Do you agree to take the above fallback-methoed, if so, i will submit the new
patch.

Thank you very much for your guildance.
lipeifeng@oppo.com
 
From: Michel Lespinasse
Date: 2022-05-16 15:45
To: lipeifeng@oppo.com
CC: michel; akpm; hughd; linux-mm; linux-kernel; Barry Song; zhangshiming; peifengl55
Subject: Re: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown
On Mon, May 16, 2022 at 10:43:39AM +0800, lipeifeng@oppo.com wrote:
> Thank you for your reply.
> I am sorry for my late reply.
 
I understand, I was pretty slow to answer myself.
Let's stop it there with the apologies :)
 
> > This previous thread is very relevant here:
> > https://lore.kernel.org/lkml/CANN689G6mGLSOkyj31ympGgnqxnJosPVc4EakW5gYGtA_45L7g@mail.gmail.com/
>
> > I am sorry that I had confused you with the original poster on that
> > thread - your proposed changes are very similar. That said, I still
> > have the exact same concerns that I had at the time. The current
> > search algorithm is guaranteed to find a gap in O(log N) time, if there
> > is an available gap of size (requested_size + alignment - page_size).
> > The modified search only requires an available gap of the requested
> > size and alignment, but it can take O(N) time which might be too slow.
> > Maybe we could afford the slow search if it's only used as a fallback
> > when the fast search fails, but very few people would ever execute
> > that fallback and that makes it hard to test / easy for bugs to hide in.
>
> In my opions, my new methods to search addr take O(log N) time too,
> is it right? i will only add more action to judge if the space is available
> at the same time.
 
Candidate gaps, large enough for an unaligned allocation of the
desired size, can still be found in O(log N) time. The problem with
your proposal, is that it might inspect and reject many candidates due
to being too small for an aligned allocation. In the worst case, there
might be candidate gaps (again, large enough for an unaligned
allocation) between every VMA, and every one of them might be too
small for an aligned allocation. That worst case then becomes O(N) as
it has to inspect and reject every vma gap.
 
The current allocation code avoids that issue by only looking for gaps
of size (requested + alignment - page_size), which are guaranteed to
be large enough to satisfy an aligned allocation. By being more restrictive
in the gaps it is looking for, it guarantees that the first gap returned by
the O(log N) search will always work, thus keeping the overall complexity
at O(log N). Of course, the issue is if it is so restrictive that it won't
find any gaps - the design assumption was that virtual address space
shouldn't be so saturated to make this an issue, but that doesn't seem to
hold in the use case you are trying to address....
 
> > If I understand your message atabd 
> > https://lore.kernel.org/lkml/202204241833454848958@oppo.com/ ,
> > it seems like some andoid apps such as wechat are filling up
> > a 32-bit address space such as there is no 13MB gap available anymore
> > (as would be required by the current search), but there are still some
> > 12MB gaps aligned on a 1MB boundary, which they are then trying to
> > allocate from. It seems very odd to me that one would find themselves
> > in that situation, could you give us some details as to how that happened ?
> > Do you know what the app is trying to do to fill the address space that way ?
> > Also, why is this odd behavior considered to be a kernel issue - was the
> > app previously running on a (quite old !) kernel that didn't have the fast
> > vma gap search, and is now failing when ported to a more recent kernel ?
>
> 1. Wechat just one of the case we found to space unsuccessfully by the old way,
> others app, like sgame、taobao and so on， which have been found the same
> issue(The allocated size is 1M~12M). Unfortunately, we can not see how the
> above apps operate.
 
Are such apps running on current android devices ? If so, how ? Do these
devices ship with kernel patches similar to what you are proposing ?
Or, are they based on a kernel that is so old (we are talking 8+ years now)
that it doesn't have the current fast gap search algorithm ?
 
--
Michel "walken" Lespinasse