Message ID | 20220412081014.399-1-lipeifeng@oppo.com (mailing list archive) |
---|---|
State | New |
Headers | show |
Series | mm: fix align-error when get_addr in unmapped_area_topdown | expand |
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
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
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
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.
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.
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.
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. > >
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
> > > 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
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 */