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 A705DC77B7D for ; Thu, 18 May 2023 19:15:19 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id E471F900005; Thu, 18 May 2023 15:15:18 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id DF6E5900003; Thu, 18 May 2023 15:15:18 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id CE5E8900005; Thu, 18 May 2023 15:15:18 -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 BEA6B900003 for ; Thu, 18 May 2023 15:15:18 -0400 (EDT) Received: from smtpin21.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 8B7F5402D1 for ; Thu, 18 May 2023 19:15:18 +0000 (UTC) X-FDA: 80804329116.21.3B9D455 Received: from out-6.mta0.migadu.com (out-6.mta0.migadu.com [91.218.175.6]) by imf20.hostedemail.com (Postfix) with ESMTP id 59FF31C0017 for ; Thu, 18 May 2023 19:15:16 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=linux.dev header.s=key1 header.b=UQPwjzIZ; spf=pass (imf20.hostedemail.com: domain of kent.overstreet@linux.dev designates 91.218.175.6 as permitted sender) smtp.mailfrom=kent.overstreet@linux.dev; dmarc=pass (policy=none) header.from=linux.dev ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1684437316; a=rsa-sha256; cv=none; b=1yIBQunT+5K/uB46qtIZJ7LP7rEHhR4fBW3ZhO5p6xacyTDsYooIzZ71eauTPXwfc20yPg YDqqBiqSm48W0j0ygF7y5tNKXsfo+i5F4uYPJotvKBvVHXYS/GTLL3f0INrdknpUsWwGY+ Zh04LTnhVdyOU0g0qL5Nia547XDkGU4= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=linux.dev header.s=key1 header.b=UQPwjzIZ; spf=pass (imf20.hostedemail.com: domain of kent.overstreet@linux.dev designates 91.218.175.6 as permitted sender) smtp.mailfrom=kent.overstreet@linux.dev; dmarc=pass (policy=none) header.from=linux.dev ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1684437316; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=iJOcOo25k/wjXyas4+FHmqw1p9KvUt01mEjs8lvvZV8=; b=wyfiXOPv+YOvPOiJuPp4CAz9O+xUNZmHDkq2Wv4LT6MNYhncH5Jio1kWibOIa5dSj3MvjP WKdv2nLqe3bELRxTOGO+moS+Cmjq8kkK1rHoknpqTnugBExY+l/NqUAOjtRyDpcgJuBFWv sYVBwj3WXm9bHgeE3ujc6cyZ3XH5QLM= Date: Thu, 18 May 2023 15:15:10 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.dev; s=key1; t=1684437313; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=iJOcOo25k/wjXyas4+FHmqw1p9KvUt01mEjs8lvvZV8=; b=UQPwjzIZOMERMSv3XDHRDtcnkGzMKBEQ6yX9N4FHhDUNLB5Iy9LafDBREGZ94SM+U/fzWe zJzi5CPNEMSCP9TtcpEmr5cMT8eDwPtWLqQStII4YNUT8PIZ+UF/WOCbg3YB9TxdWNhYGC WlR+T9+6vMcBdBJqBeGx6GekxSFNhIQ= X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. From: Kent Overstreet To: Song Liu Cc: Mike Rapoport , linux-mm@kvack.org, Andrew Morton , Dave Hansen , Peter Zijlstra , Rick Edgecombe , Thomas Gleixner , Vlastimil Babka , linux-kernel@vger.kernel.org, x86@kernel.org Subject: Re: [RFC PATCH 1/5] mm: intorduce __GFP_UNMAPPED and unmapped_alloc() Message-ID: References: <20230308094106.227365-1-rppt@kernel.org> <20230308094106.227365-2-rppt@kernel.org> <20230518152354.GD4967@kernel.org> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: X-Migadu-Flow: FLOW_OUT X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 59FF31C0017 X-Stat-Signature: d4p6ja1f8m6y3m4eo619p7qhnit6mgko X-Rspam-User: X-HE-Tag: 1684437316-544827 X-HE-Meta: U2FsdGVkX18zMLMZPIeY0MSDd6+UN6MDJR+yof7LsdV9A1O2tbYJ2zdT1KzEvxPa0j1oL+8IGh3eH5dp+Br3dx+hdWg1SD99wdBySn1nqHAQ7AKGfZVAfFua14LIhEd9rpGCCYJwyJDYa6jSoFsAoA8nj37z3253/QgMan9earovgICU6OsyhuMvE/JO7sypVAVyTYw47ZStOmONfk6dwjdLhi9Yes5sMjyS1jbvH0+fG4demADFW2qYqA1ocueFo4JI5fWVFsi8nyECyAlllnd9P70mauK8bM4HzrdFn4ifb8weL0lYgF8izJvowz1v2RTfnaC6hF6SjqTgn4euBz6nR799+75h6kiUsFpzFqcDYDyNDcHr3AkiE8ZERkG32NJ8JXOcM0SIBKJ1bKr1kw3KZw1+k3OOZ9f8gSWdZzdf/4R3/Cs7zNcKpjKPAs8F48KRfC5oNTQClkmp/b9rEwz+MzyewJAR3QSJGgwcgdt2MW8xbK7xb527P/0RBh3SZwWLg9w5+fmIvLlUGvkRhNWbEkeYHSsQm2ZBU+397Rut/IQrx6ikxc1zi5VTTRp1ZBAeh0k90jivw0ADQyV4mNRuQQifElfF6oijNAyyb4aOHQBDdJdm0GlQ9HKoKyPar+YSYCUlUA/9ov5VYNY9PdMB6qMQbnN+yitSqwCeCbEbrBtH4NTW9L/G+/skcZiqpQYXuBTMS818oAwcoNaKS6gUhMsXD0taXalw35mkBYFRnoJnGdR6yfPgV/V7MEYdCEGW4XD9mnpF+5Wxl78PdRwngi+kYHz8YS1SPSVBHUK3mmxWhYU8yIyJ3DdpJrOO1Ie2YvNuAnQPNyDO2VoAswFYNm1tiZuCq0LF5//lz6mbxjr29WOOnXUF3ixa3OYzUW0Pw7prmA1BVGtEBc+jNKfhxNjTdaI/Dc01QvjW1U1SkCC74RdU0r9dwnqA33EsYnKhyaSVX8byZv3WjkK eY1zkV1Z HBe39CLWUKAvtBdmpwg51YjjkAFpaeMsWP1Y04SLgt477kjJ8VA4xr4yvOE/ZX7c2+vGvHDAb4oN1kmbAS4lqijFvp7wZgwgCpfhEIMxx/bnQz1uDTXGt8h/Bxdg+A3dZchnCOFJyKbwfYAFquZvlPppnjS4kW4moaCjJ X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: On Thu, May 18, 2023 at 12:03:03PM -0700, Song Liu wrote: > On Thu, May 18, 2023 at 11:47 AM Song Liu wrote: > > > > On Thu, May 18, 2023 at 10:24 AM Kent Overstreet > > wrote: > > > > > > On Thu, May 18, 2023 at 10:00:39AM -0700, Song Liu wrote: > > > > On Thu, May 18, 2023 at 9:48 AM Kent Overstreet > > > > wrote: > > > > > > > > > > On Thu, May 18, 2023 at 09:33:20AM -0700, Song Liu wrote: > > > > > > I am working on patches based on the discussion in [1]. I am planning to > > > > > > send v1 for review in a week or so. > > > > > > > > > > Hey Song, I was reviewing that thread too, > > > > > > > > > > Are you taking a different approach based on Thomas's feedback? I think > > > > > he had some fair points in that thread. > > > > > > > > Yes, the API is based on Thomas's suggestion, like 90% from the discussions. > > > > > > > > > > > > > > My own feeling is that the buddy allocator is our tool for allocating > > > > > larger variable sized physically contiguous allocations, so I'd like to > > > > > see something based on that - I think we could do a hybrid buddy/slab > > > > > allocator approach, like we have for regular memory allocations. > > > > > > > > I am planning to implement the allocator based on this (reuse > > > > vmap_area logic): > > > > > > Ah, you're still doing vmap_area approach. > > > > > > Mike's approach looks like it'll be _much_ lighter weight and higher > > > performance, to me. vmalloc is known to be slow compared to the buddy > > > allocator, and with Mike's approach we're only modifying mappings once > > > per 2 MB chunk. > > > > > > I don't see anything in your code for sub-page sized allocations too, so > > > perhaps I should keep going with my slab allocator. > > > > The vmap_area approach handles sub-page allocations. In 5/5 of set [2], > > we showed that multiple BPF programs share the same page with some > > kernel text (_etext). > > > > > Could you share your thoughts on your approach vs. Mike's? I'm newer to > > > this area of the code than you two so maybe there's an angle I've missed > > > :) > > > > AFAICT, tree based solution (vmap_area) is more efficient than bitmap > > based solution. Tree based requires quite a bit of overhead for the rbtree pointers, and additional vmap_area structs. With a buddy allocator based approach, there's no additional state that needs to be allocated, since it all fits in struct page. > > First, for 2MiB page with 64B chunk size, we need a bitmap of > > 2MiB / 64B = 32k bit = 4k bytes > > While the tree based solution can adapt to the number of allocations within > > This 2MiB page. Also, searching a free range within 4kB of bitmap may > > actually be slower than searching in the tree. > > > > Second, bitmap based solution cannot handle > 2MiB allocation cleanly, > > while tree based solution can. For example, if a big driver uses 3MiB, the > > tree based allocator can allocate 4MiB for it, and use the rest 1MiB for > > smaller allocations. We're not talking about a bitmap based solution for >= PAGE_SIZE allocations, the alternative is a buddy allocator - so no searching, just per power-of-two freelists. > > Missed one: > > Third, bitmap based solution requires a "size" parameter in free(). It is an > overhead for the user. Tree based solution doesn't have this issue. No, we can recover the size of the allocation via compound_order() - hasn't historically been done for alloc_pages() allocations to avoid setting up the state in each page for compound head/tail, but it perhaps should be (and is with folios, which we've generally been switching to).