From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1F3CEC433F5 for ; Mon, 16 May 2022 07:45:27 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 563926B0071; Mon, 16 May 2022 03:45:27 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 512AF6B0072; Mon, 16 May 2022 03:45:27 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 401C56B0073; Mon, 16 May 2022 03:45:27 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 314626B0071 for ; Mon, 16 May 2022 03:45:27 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay11.hostedemail.com (Postfix) with ESMTP id E88118111A for ; Mon, 16 May 2022 07:45:26 +0000 (UTC) X-FDA: 79470821052.03.3291094 Received: from server.lespinasse.org (server.lespinasse.org [63.205.204.226]) by imf19.hostedemail.com (Postfix) with ESMTP id 821A01A0007 for ; Mon, 16 May 2022 07:45:16 +0000 (UTC) DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=lespinasse.org; i=@lespinasse.org; q=dns/txt; s=srv-68-ed; t=1652687124; h=date : from : to : cc : subject : message-id : references : mime-version : content-type : content-transfer-encoding : in-reply-to : from; bh=pw3SQmitQZih51+UiGS5tizm1ZvzDcl0PRQC+JGIjCM=; b=XMiPrSOfwdfmHpqwPDiHQ5kwPpaT/PRqvzXgXk5VLI1AHwQkW4UkJ0VyzARjYPT7sJ/ZK VLbsUG4ljRofBY3Cw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=lespinasse.org; i=@lespinasse.org; q=dns/txt; s=srv-68-rsa; t=1652687124; h=date : from : to : cc : subject : message-id : references : mime-version : content-type : content-transfer-encoding : in-reply-to : from; bh=pw3SQmitQZih51+UiGS5tizm1ZvzDcl0PRQC+JGIjCM=; b=MPb39cPFMsmI2rj1zj+Pb9gyBKGgoODiK4tJuDS5g3kU6SPPoHbK9J2Vi8PiOrQqcmBWH YnqFj+i0LEczNHtfZVtKNfNqR3UdteLAV/EMqgllLHV0DGrGJwa0XtXbfcJl36JiM6D6skC HryP9WrMzduqE542Yd5cVOb/b/E/y7rx1wPFhKNnnIOb0o3rWwrqHOYlE3/S8A+ECdnwbNh qiuGS0uQ4Qn+dzjPnxfcR8IKK0JY876iPYoXicmLKwUH/DhoD6ej3yfPE+vpkaezBmrvfz8 Q8c1gjNMwPRmd5SL0HtuQVkSuEYlsTDVvG02jIp84bViTY7fXy5NUOTLQQpA== Received: by server.lespinasse.org (Postfix, from userid 1000) id 36A6E160B7F; Mon, 16 May 2022 00:45:24 -0700 (PDT) Date: Mon, 16 May 2022 00:45:24 -0700 From: Michel Lespinasse To: "lipeifeng@oppo.com" Cc: michel , akpm , hughd , linux-mm , linux-kernel , Barry Song <21cnbao@gmail.com>, zhangshiming , peifengl55 Subject: Re: Re: [PATCH] mm: fix align-error when get_addr in unmapped_area_topdown Message-ID: <20220516074524.GA27455@lespinasse.org> References: <20220412081014.399-1-lipeifeng@oppo.com> <20220412142238.93e36cc4095e4e0b362db348@linux-foundation.org> <2022041310411426044561@oppo.com> <2022050110235766139218@oppo.com> <20220501181041.6d53cb9ed54bf697840e36cc@linux-foundation.org> <2022050211305415626916@oppo.com> <20220509114521.GA9512@lespinasse.org> <2022051610294089439420@oppo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <2022051610294089439420@oppo.com> User-Agent: Mutt/1.10.1 (2018-07-13) X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 821A01A0007 X-Stat-Signature: uwuzabfw7fwofw1cecmfcnjkd6r8sh7b X-Rspam-User: Authentication-Results: imf19.hostedemail.com; dkim=pass header.d=lespinasse.org header.s=srv-68-ed header.b=XMiPrSOf; dkim=pass header.d=lespinasse.org header.s=srv-68-rsa header.b=MPb39cPF; spf=pass (imf19.hostedemail.com: domain of michel@lespinasse.org designates 63.205.204.226 as permitted sender) smtp.mailfrom=michel@lespinasse.org; dmarc=pass (policy=none) header.from=lespinasse.org X-HE-Tag: 1652687116-963506 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000107, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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