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 1CFD0C02194 for ; Fri, 7 Feb 2025 15:00:05 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A928B280004; Fri, 7 Feb 2025 10:00:04 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id A427B280001; Fri, 7 Feb 2025 10:00:04 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 90A8A280004; Fri, 7 Feb 2025 10:00:04 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 70EBD280001 for ; Fri, 7 Feb 2025 10:00:04 -0500 (EST) Received: from smtpin24.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id CB9BF121CFD for ; Fri, 7 Feb 2025 14:59:03 +0000 (UTC) X-FDA: 83093456208.24.0C5566D Received: from nyc.source.kernel.org (nyc.source.kernel.org [147.75.193.91]) by imf28.hostedemail.com (Postfix) with ESMTP id 2C051C0003 for ; Fri, 7 Feb 2025 14:59:01 +0000 (UTC) Authentication-Results: imf28.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=ur0X6sr6; spf=pass (imf28.hostedemail.com: domain of rppt@kernel.org designates 147.75.193.91 as permitted sender) smtp.mailfrom=rppt@kernel.org; dmarc=pass (policy=quarantine) header.from=kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1738940342; 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=uPbPeumziN+HR86QSDUB7FjMYF2oojrLViWrfDRUqr4=; b=rXukvdjSS95V8McKsOpPZo4PsMSAvOvUFD/b7GHMrzmNT5UvTS/rxq9vo6JzCmWwV7wPmW 4UsLZCoLiticmJUuShkKxtp4o7VjW2Zot8po7mrQkzsn4F0cVco7TUSRGcQqlSIKuLCnsI 4jRrPvOcdnpEfGAMJIokgeSHU/uQf8A= ARC-Authentication-Results: i=1; imf28.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=ur0X6sr6; spf=pass (imf28.hostedemail.com: domain of rppt@kernel.org designates 147.75.193.91 as permitted sender) smtp.mailfrom=rppt@kernel.org; dmarc=pass (policy=quarantine) header.from=kernel.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1738940342; a=rsa-sha256; cv=none; b=XajvW3uKMIVUaCwzsAcuGf0x5JJ75k3KauO9aw6zrL5ZWdY5LUMgB2jVhbOfTssYuKHvy1 AW++UZmcZ8cB7AkuvSJNDwgub+Yl5/KS4x6K+TIljBwZVRUibdv48r7rJciy8/gTNs8PJW lUKZN1sU/78us82I2Jm+1VWZZ3j0Jjo= Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by nyc.source.kernel.org (Postfix) with ESMTP id 78D2DA435C3; Fri, 7 Feb 2025 14:57:15 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 3FF05C4CED1; Fri, 7 Feb 2025 14:58:58 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1738940341; bh=i9CKeB+XfrWpQq7i8mHZmhwLBDP4pruyNo0uHrMgtbk=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=ur0X6sr6Et2Hi2aaNUIVFYQNjeC4cRof9bKRYSIE6vpmcvxVWWRXsQrjBaDFP6ef+ lfK9WLYVVAbgXXjB/um4zEnwlrqdaCSfUXVj0UJqXdT6WVVB32c8TFjAYyGUsn8L5D QO+qsD1pHFHwgLhhrJMXR0T9IBO8fw7d8kdSMkDtyCBsLxJarwngv8E9PsqfRtxIMC 0UtlIhrVhXkZ62hFvIrqej4KDAMXXuBfjyS2pDsk1k6GNbqgc+0WxjBiBKwvUBijA7 Gjs/n6JCUUqP2Jd/nQPtUEE2WRKyuz7gJ3nLmFsCqOqBuphKJhiCT4NxSeeM+GUMvm urcdasQs5wVYA== Date: Fri, 7 Feb 2025 16:58:49 +0200 From: Mike Rapoport To: Stephen Eta Zhou Cc: "akpm@linux-foundation.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" Subject: Re: [PATCH] mm: optimize memblock_add_range() for improved performance Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: X-Rspamd-Queue-Id: 2C051C0003 X-Stat-Signature: eyw7tp9oeu8fmdxhxyht7586aoxfst5o X-Rspam-User: X-Rspamd-Server: rspam01 X-HE-Tag: 1738940341-802976 X-HE-Meta: U2FsdGVkX1+jHUQEZPtDzYF7c5WzwHZp4G0HlII4KG8AF3SQUqBexZNGH4vy5VTFjOQOeY47H8lVVHo4FBMgsCivEVNkj2wVE9ZU09uJ+UqalBlQPW0eWMeUjG/ZDyJ1wxaEo0qx3GjmB6bw8eVkgzg83UWJwv+OozBv5FGlZir9QoPQ9R2Ybu6y7MRYPsQNpmlibsVXHpWa+3GEPULKh6dRoRkN+wiVMDq56Qa12+IL/MAfLdTfkmBip3rnT0WahmqoGGFSuzjdXYwy4pD7kDkyHQ8Ulyly4AIgKEdrYydf/YofIcol4Kbhu86pDzDM7tVXYnRcG9cv17TqLYL3lgkl2NcvItHqfnq9zJusYawkLZApNQxNFiKZKlwRwnt1tvnwjQetbzhesCNYC+0tKlSioZTdlhoJCgIYd1mIAZVP5bJkLghNuFQ2+BTSgZiTudCwkyU5KpiAf0R2w2fsaGV+BN0P+HtifE+J7fbqWMuiOKEYMlm2tHSZM8q0FDmw1LgJfxREWFRhA9CxKWVXLTolaHQF6Lh/jDn4qOx+j7dWjWpUwJZyR0U2suhlvF67pZdFe3PXBwsoaSutrC0EzHmAUOzUWNRYniXYwQPaZg+TB+mj+FedqcXfyGaQ9VZCR6MZgvc3maLC9Gif6ShW5mmY4O7mXleQYoGos2QwB1/NGj/hWZvHAwiDoc3wF56jrjO46VFFv5+r9RKukXX0iJCZ1KFAGobzYaodRSzSAa3Q7Dsm+Z2xaoZO7A7uJTppU7pWG9ZvNI8OYzjXIL4o14jc3aIM6tGCDF31blTo23Iw5sTfOK+yuXfXFGPNmc80kOroU6V7HdGpewiVkrqcvwtEZR9+iQnCtGnF8OwYWZ8eoaBevIJDXWu0yvEFZLbFdLrOYsbpeRiAziqRnhD9RWrUVVItg2ybiGWeJDiaXi7tvOuVn0F9pogTVMPYfT9Uvis4ijQlNglXnYNyaQX 9b+aYBe6 cYRpZHbKHTCPAb92LO+mVqYaRhBVWKXVj9HMkG7jMKpEbtANUbVprhnDwqZnrpt5ESTVILO8oIAb4DeDRP3SUnLfSrEYnIYKOwnQ5Y5SjvrbFNO3IWr3yjMM8deZNoy5Sb4/Ck2fbmRwL7gQktApbaTYA4SvJVg64YoDecPaQaIpGa4upfD9DUdKlhuqlxt2f4WOzUiWYL2kfQ3Pa+bmuyRAiQ8d5uBdxEbdqBeT8mvhGvCCrL7oIs76+77MWRJfxZFg7TKy9HCPB7mVvqbvwiPOkAW6k4LLTVVrJNq+eixLctxGWVQvg5QAQGybVP1rY2P7Pe26zK3J/qCvoAYsx+JhbIT6ro+x/gpMxE8dlJivWIJU= 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: Hi Stephen, On Wed, Feb 05, 2025 at 05:55:50AM +0000, Stephen Eta Zhou wrote: > Hi Mike Rapoport、Andrew Morton > I have recently been researching the mm subsystem of the Linux kernel, > and I came across the memblock_add_range function, which piqued my > interest. I found the implementation approach quite interesting, so I > analyzed it and identified some areas for optimization. Starting with > this part of the code: > > if (type->cnt * 2 + 1 <= type->max) >       insert = true; > The idea here is good, but it has a certain flaw. The condition is rather > restrictive, and it cannot be executed initially. Moreover, it is only > valid when the remaining space is (2/1) + 1. If there is enough memory, > but it does not satisfy (2/1) + 1, the insertion operation still needs to > be performed twice. The code in memblock_add_range() is very fragile, and many attempts to remove the second pass that looked correct at the first glance failed for some corner case. Unfortunately, it's impossible to capture all possible memory configurations and reservations in the memblock test suite, so even it it passes, there is a chance the kernel will fail to boot on an actual HW. > - Before the patch: > - Average: 1.22% > - Max: 1.63%, Min: 0.93% > > - After the patch: > - Average: 0.69% > - Max: 0.94%, Min: 0.50% > These numbers do not represent what's actually interesting: the boot time speedup. -- Sincerely yours, Mike.