On Mon, May 16, 2022 at 10:43:39AM +0800, lipeifeng@xxxxxxxx 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@xxxxxxxxxxxxxx/ > > > 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@xxxxxxxx/ , > > 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
