Skip to contentSkip to conversation

mm: fix align-error when get_addr in unmapped_area_topdown

PATCH In review [email protected] 3 participants 12 messages Apr 12, 2022 – May 17, 2022

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 mm: fix align-error when get_addr in unmapped_area_topdown

From: lipeifeng <[email protected]>

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).

---
 mm/mmap.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
mm/mmap.c +2 -1
index 30e33d3..a28ea5c 100644
@@ -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 */
Signature · 1 line
2.7.4
maintainer
#1 lore raw
Quoted 18 lines · On Tue, 12 Apr 2022 16:10:14 +0800 [email protected] wrote:

From: lipeifeng <[email protected]>

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;
Quoted 6 lines

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?

Quoted 21 lines
mm/mmap.c +2 -1
@@ -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 */
Signature · 1 line
2.7.4
#2 lore raw

and
Hi Andrew Morton:

Quoted 1 line

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".

Quoted 1 line

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:

Quoted 25 lines

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;

Quoted 1 line

}

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.

Quoted 5 lines

found:
/* We found a suitable gap. Clip it with the original high_limit. */ if (gap_end > info->high_limit)
gap_end = info->high_limit;

Quoted 7 lines

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.

[email protected]

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

Quoted 18 lines · On Tue, 12 Apr 2022 16:10:14 +0800 [email protected] wrote:

From: lipeifeng <[email protected]>

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;
Quoted 6 lines

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?

Quoted 21 lines
mm/mmap.c +2 -1
@@ -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 */
Signature · 1 line
2.7.4
#3 lore raw

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. [email protected]

From: [email protected]
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:

Quoted 1 line

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".

Quoted 1 line

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:

Quoted 14 lines
	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:

Quoted 12 lines
	/* 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.

Quoted 5 lines

found:

	/* We found a suitable gap. Clip it with the original high_limit. */
	if (gap_end > info->high_limit)
	gap_end = info->high_limit;
Quoted 7 lines

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.

[email protected]

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 [email protected] wrote:

Quoted 18 lines

From: lipeifeng <[email protected]>

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;

Quoted 6 lines

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?

Quoted 21 lines
mm/mmap.c +0 -0
@@ -2009,7 +2009,6 @@ static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)
   if (length < info->length)
   return -ENOMEM;

mm/mmap.c +0 -1
-	length = info->length;

  /*
  * Adjust search limits by the desired length.
  * See implementation comment at top of unmapped_area().

mm/mmap.c +0 -0
@@ -2021,6 +2020,8 @@ static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)


  if (info->low_limit > high_limit)
  return -ENOMEM;

mm/mmap.c +2 -0
+
+	length = info->length;

  low_limit = info->low_limit + length;

  /* Check highest gap, which does not precede any rbtree node */ --
2.7.4

maintainer
#4 lore raw
Quoted 2 lines · On Sun, 1 May 2022 10:26:35 +0800 "[email protected]" <[email protected]>…

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.

#5 lore raw

Hi Andrew:

Thanks for your quick response.

Quoted 3 lines

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?

Quoted 5 lines

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.

[email protected]

From: Andrew Morton
Date: 2022-05-02 09:10
To: [email protected]
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 "[email protected]" <[email protected]> wrote:

Quoted 2 lines

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.

maintainer
#6 lore raw
Quoted 9 lines · On Mon, 2 May 2022 11:33:18 +0800 "[email protected]" <[email protected]>…

Hi Andrew:

Thanks for your quick response.

Quoted 3 lines

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.

Quoted 1 line

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.

Quoted 10 lines
Quoted 6 lines

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.

#7 lore raw

Hi Andrew:

Thank you for your response.

Quoted 5 lines
Quoted 5 lines
Quoted 3 lines

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?

Quoted 2 lines

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

Quoted 1 line
Quoted 1 line

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

Quoted 4 lines

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.

Quoted 7 lines
Quoted 7 lines
Quoted 6 lines

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.

Quoted 5 lines
Quoted 3 lines

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.

[email protected]

From: Andrew Morton
Date: 2022-05-08 05:59
To: [email protected]
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 "[email protected]" <[email protected]> wrote:

Quoted 9 lines

Hi Andrew:

Thanks for your quick response.

Quoted 3 lines

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.

Quoted 1 line

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.

Quoted 10 lines
Quoted 6 lines

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.

#8 lore raw
In reply to [email protected]
Quoted 10 lines · On Mon, May 02, 2022 at 11:33:18AM +0800, [email protected] wrote:

Hi Andrew:

Thanks for your quick response.

Quoted 3 lines

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.

Quoted 9 lines
Quoted 5 lines

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/[email protected]/ ,
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 ?

Quoted 26 lines

Thank you very much indeed.

[email protected]

From: Andrew Morton
Date: 2022-05-02 09:10
To: [email protected]
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 "[email protected]" <[email protected]> wrote:

Quoted 2 lines

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.

#9 lore raw

Hi michel:

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

Quoted 2 lines

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

Quoted 10 lines

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.

Quoted 4 lines

If I understand your message at
https://lore.kernel.org/lkml/[email protected]/ , 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

Quoted 8 lines

(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.

[email protected]

From: Michel Lespinasse
Date: 2022-05-09 19:45
To: [email protected]
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

Quoted 10 lines · On Mon, May 02, 2022 at 11:33:18AM +0800, [email protected] wrote:

Hi Andrew:

Thanks for your quick response.

Quoted 3 lines

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.

Quoted 9 lines
Quoted 5 lines

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/[email protected]/ ,
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 ?

Quoted 26 lines

Thank you very much indeed.

[email protected]

From: Andrew Morton
Date: 2022-05-02 09:10
To: [email protected]
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 "[email protected]" <[email protected]> wrote:

Quoted 2 lines

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.

#10 lore raw
Quoted 2 lines · On Mon, May 16, 2022 at 10:43:39AM +0800, [email protected] 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 :)

Quoted 14 lines
Quoted 13 lines

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.

Quoted 3 lines

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....

Quoted 13 lines
Quoted 4 lines

If I understand your message at
https://lore.kernel.org/lkml/[email protected]/ , 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

Quoted 8 lines

(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 ?

Quoted 4 lines

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

#11 lore raw
Quoted 13 lines
Quoted 13 lines
Quoted 12 lines

If I understand your message atabd
https://lore.kernel.org/lkml/[email protected]/ ,
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 ?

Quoted 4 lines
Quoted 4 lines

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.

Quoted 1 line

Are such apps running on current android devices ? If so, how ?

Yes, we found many apps(only 32-TIF) faces the problems.

Quoted 1 line

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.

Quoted 2 lines

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.
[email protected]

From: Michel Lespinasse
Date: 2022-05-16 15:45
To: [email protected]
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

Quoted 2 lines · On Mon, May 16, 2022 at 10:43:39AM +0800, [email protected] 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 :)

Quoted 14 lines
Quoted 13 lines

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.

Quoted 3 lines

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....

Quoted 13 lines
Quoted 4 lines

If I understand your message atabd
https://lore.kernel.org/lkml/[email protected]/ , 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

Quoted 8 lines

(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 ?

Quoted 4 lines

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