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 45B41C0219C for ; Fri, 7 Feb 2025 14:25:51 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id AE817280004; Fri, 7 Feb 2025 09:25:50 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id A97A4280001; Fri, 7 Feb 2025 09:25:50 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 95DBD280004; Fri, 7 Feb 2025 09:25:50 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 781B1280001 for ; Fri, 7 Feb 2025 09:25:50 -0500 (EST) Received: from smtpin02.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id D41A6161AC8 for ; Fri, 7 Feb 2025 14:25:45 +0000 (UTC) X-FDA: 83093372250.02.8F43E55 Received: from casper.infradead.org (casper.infradead.org [90.155.50.34]) by imf15.hostedemail.com (Postfix) with ESMTP id 3A736A0025 for ; Fri, 7 Feb 2025 14:25:40 +0000 (UTC) Authentication-Results: imf15.hostedemail.com; dkim=pass header.d=infradead.org header.s=casper.20170209 header.b=rMcoJToQ; spf=none (imf15.hostedemail.com: domain of willy@infradead.org has no SPF policy when checking 90.155.50.34) smtp.mailfrom=willy@infradead.org; dmarc=none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1738938342; 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: in-reply-to:in-reply-to:references:references:dkim-signature; bh=yMVdJszBaJdWZfMzBrdhAbDbfib9SbTXaAtSt2p0jvA=; b=iTlBfKlkPnrGaP2A7bqcO/ivAcoGGkmu+miIwaqM+yxpiUd9SUKbjhso4SDMgAQTyOd1IL wLveuHiU6EvnhGSWowMQILld3vcUocAIX60t055resT4O9lW3ddM8cR2ORQoJvI02xqOJw DkJ6AS3aUA++BQU6QNZU668yzkHee+g= ARC-Authentication-Results: i=1; imf15.hostedemail.com; dkim=pass header.d=infradead.org header.s=casper.20170209 header.b=rMcoJToQ; spf=none (imf15.hostedemail.com: domain of willy@infradead.org has no SPF policy when checking 90.155.50.34) smtp.mailfrom=willy@infradead.org; dmarc=none ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1738938342; a=rsa-sha256; cv=none; b=j4Cp/PP1HFoxz4rc54FdZkcqE5GPhQRHFZhLnzUtVe7MhMceQAexbxl6FIxluyOOKTynqQ yncSKHfsun5s141ivM3Lbzxbyd0TsHFfZRWyo7m4XvOg1C6Djn5q5hayHCLVXq1uZN3haV Bkh9Sl1kmEw3KiXmLyzFAunGrm8K6Ss= DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=casper.20170209; h=In-Reply-To:Content-Type:MIME-Version: References:Message-ID:Subject:Cc:To:From:Date:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description; bh=yMVdJszBaJdWZfMzBrdhAbDbfib9SbTXaAtSt2p0jvA=; b=rMcoJToQeFy2UP+/3OdmTSurWq 61Ai1zOjD8PuYuT7Sm2uHn4y7NjxDjg4VyI1gJnjul/40si7h50+iAaqCbxHb/EDyG4+pEpooDsxZ jt4tiyrKhyvATVcsFtPXZAQ5b1/2hQSdXL2V9YJ16x+OyAk1Qzc/igbyIayLW5oMxj5uwnMwSTcSE HXA56gRV0Ygxhcs1oboCqBy6zZdfL8pKs0DduY3SD6g0cFAlMUayMvxi0atuu7zJlYwJir17wAvj3 dVmNwihsONhWCAkivxFgYeDYjXdn6X6dYf7A0wDk4kSBohYrfjFQskqLSBY0TJX5IRJHZn6Fv0Mz8 5D4X3ypQ==; Received: from willy by casper.infradead.org with local (Exim 4.98 #2 (Red Hat Linux)) id 1tgPIT-00000007wru-2G8d; Fri, 07 Feb 2025 14:25:33 +0000 Date: Fri, 7 Feb 2025 14:25:33 +0000 From: Matthew Wilcox To: Zi Yan Cc: Andrew Morton , linux-mm@kvack.org, "Kirill A . Shutemov" , Ryan Roberts , Hugh Dickins , David Hildenbrand , Yang Shi , Miaohe Lin , Kefeng Wang , Yu Zhao , John Hubbard , Baolin Wang , linux-kselftest@vger.kernel.org, linux-kernel@vger.kernel.org Subject: Re: [PATCH v6 0/7] Buddy allocator like (or non-uniform) folio split Message-ID: References: <20250205031417.1771278-1-ziy@nvidia.com> <20250206000111.6c54e67d1933f8bbc01a46cd@linux-foundation.org> <019EB6CA-0F4B-496A-B2AE-A3A553585281@nvidia.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <019EB6CA-0F4B-496A-B2AE-A3A553585281@nvidia.com> X-Rspam-User: X-Rspamd-Server: rspam11 X-Rspamd-Queue-Id: 3A736A0025 X-Stat-Signature: 3rzaanbq8yooqo6u1mszyh5xnjiyy37b X-HE-Tag: 1738938340-729834 X-HE-Meta: U2FsdGVkX19DF4T3AvJlvZZAlouHsytRhPKd7kWt9mlRrVvqIx5rgVtD+XMpEfYFfEYRAPkmWxlghn9B468FrmSq5TGifnoaYNgXrMJkZL/F6tyd5QiLhkteXutZfZDMAddU9EdOoXjbUDfWugYVH6MBQHxVfVFRfXi5XKiiuqkXv9Oy5fq0nDVg1t57QsoVEt/wXjiL4OKgQUbu/pRIqnWt3rd0M9kdweXwnYRwq3g+jFkxCAdsO65VlSz7VW+m5ajpt23bZqzhaKr9HCQwB10EtpJqS2c4HD6056wUWjO7fvCqn6uW1uc/RwEFaULGd6VcCy3qppSprgg4VUV4PASb1YFqhf8xoqE+KWX5OA09mVe0Vb+DzYGH90nYK7H72Jfmoep2X6ONr7CyitKodF7/GPhuLXaQBlfDM+m2ahQd5OHyc8HWe3mHTX8iE+0M0rF1pxltFDa/q8ZtvWOxzFfToWpaniN5rjSCOOFYaqpaU09/Ho47Rly4OAkhtxbq2w416i47HvmVuycrV4bC/Azxt0rjECVYVbDruewRJlRsM3OSsT8NlAnsI/AJc62el0s3xlMrL71FWbcadndw3efpdlrO4VXO/o0aQjk1ECG2fa8KVKkaxBE3BjwuZzNlZMJ64WuqeT8Cva1QA5UQfuF+GUPSQ7RJvq6nz7jcSwKWr/35Pw3tXhvsSQzLAUf0CvlCLxeZRMINivailjarV+ZeJKnuILSQ8g83ssw5NCiodNtUMuB1yBeoMya8e887OfBext+hMYx0tLMlOzcNP8DuX4JvuTUYJHXHkgfvZjHzBC6qKtSTqzfAol4Fkj0zE1yG9Sb6QK51xQPb6HU+7U07QRX0Hk9ZdXa/zdqKMLS1VeMHzMTwKIw6GgiHHz85MEYVMRfON44WuWqrKeKvsP+qUnu4PahGv8wQ8vKeBH8MG9tqzSwZhVb2uYqgVAwHimNA07WIwbLG9J/Zv0w FIUIxdJy uwtDPxOtHkMam8ZnQH5qzRTjIrsCJPJI3biluvY2Sh9d7XBR/EtlWa1oIk9mE9gcnHT5LZshS3faDLq92pKtEg1lzFZ78ECQ0mcPlcHebJmmJtFCa2my3P4d2dapJJWw954ZxkdZlRhiGmlFHKbtGrgCerHGDU7mhTaH1WUYb46U+e9ZtsF4+nzWRglZgS01Sky/04jEk+9l46iCj3oga/mFV9d+cWkB1XlDZM3HWO27U8Qk= 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: List-Subscribe: List-Unsubscribe: On Fri, Feb 07, 2025 at 09:11:39AM -0500, Zi Yan wrote: > Existing uniform split requires 2^(order % XA_CHUNK_SHIFT) xa_node allocations > during split, when the folio needs to be split to order-0. But non-uniform split > only requires at most 1 xa_node allocation. For example, to split an order-9 > folio, 8 xa_nodes are needed for uniform split, since the folio takes 8 > multi-index slots in the xarray. But for non-uniform split, only the slot > containing the given struct page needs a xa_node after the split. There will be > a 7 xa_node saving. > > Hi Matthew, > > Do you mind checking my statement above on xarray memory saving? And correct me > if I miss anything. Thanks. We currently have a bug where we can't split order-12 (or above) to order-0 (or anything in the range 0-5) as we'd need to allocate two layers of nodes, and the preallocation can't do that. As part of your series, I'd like to remove that limitation, so we'd need to allocate log_64(n - m) [ok, more complex than that, but ykwim]. So it's not quite "only allocate one node", but it's allocate O(log(current number of nodes needed to be allocated)). Makes sense?