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 99564C4345F for ; Mon, 22 Apr 2024 02:55:06 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id DD1566B0083; Sun, 21 Apr 2024 22:55:05 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id D81FD6B0087; Sun, 21 Apr 2024 22:55:05 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C49286B0088; Sun, 21 Apr 2024 22:55:05 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id A6B376B0083 for ; Sun, 21 Apr 2024 22:55:05 -0400 (EDT) Received: from smtpin27.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 502C4C0762 for ; Mon, 22 Apr 2024 02:55:05 +0000 (UTC) X-FDA: 82035650970.27.234E1D2 Received: from mail-wr1-f52.google.com (mail-wr1-f52.google.com [209.85.221.52]) by imf13.hostedemail.com (Postfix) with ESMTP id 5B87E20007 for ; Mon, 22 Apr 2024 02:55:03 +0000 (UTC) Authentication-Results: imf13.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=EfDPKPT9; spf=pass (imf13.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.221.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1713754503; h=from:from:sender:reply-to: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=QRJCa35xITgA3o6nJAzVX5FmK968RqVJUIvKbBC3Xao=; b=qncyNhHj+ffoLbGvojbOfzPuOCmrzQQLj8ddS8hiQRYdn36B2r+qJKGbyOVwqaVO8NGsAu GPd6uf2Ltv7+pswjBVVcDWB/e5GHLWNP0Qgp2yE6zZk9MsV1jYUlPzmP+fI32/Z8+/cbFT PGqoHfAVTw/CMkwA3T+lmnwLs0pFuM8= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1713754503; a=rsa-sha256; cv=none; b=iifB002XWJv62ftamMPq4Z6zJ/ZbVtj0l2QNiGH0HrhB+zEtTRnIhAHvLYUP3EAKhO9XPk oVT8RVivXs0jIRQDu/BQ/7Wd/++1KJpAIo9lBnPXIEF+E8pbCBWsmzAYqi5kmcmNAvzRZ1 q9kN5sx062negD1fDXrxuSRqEM0rsMo= ARC-Authentication-Results: i=1; imf13.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=EfDPKPT9; spf=pass (imf13.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.221.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-wr1-f52.google.com with SMTP id ffacd0b85a97d-343f62d8124so3179664f8f.2 for ; Sun, 21 Apr 2024 19:55:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1713754502; x=1714359302; darn=kvack.org; h=user-agent:in-reply-to:content-disposition:mime-version:references :reply-to:message-id:subject:cc:to:from:date:from:to:cc:subject:date :message-id:reply-to; bh=QRJCa35xITgA3o6nJAzVX5FmK968RqVJUIvKbBC3Xao=; b=EfDPKPT9M6QTs8CZDlcQOm1NB7eIk7hD8M+dNeq892w5JbGcra+Fuz1TyR2JOJ6tY1 TPqbqTqIhTD48Rqy2itkZdyrdpWHSG2MpSjHmLtuKqaX+RB6599DDAWc18B6eLBryFym +JmBHz46OUKC3B5lHv7TWyjXtO0bEoxGlx6bLZcl1eRTWlL/0crJaxdjQSYlh1GUvC/D KX/nhxbGmdAhEA2fCXZ34AFfAHM/1PFL6fDTXhJ/vGv7dBW7xcVeT807SzrgJkGdpXry Xs9GcGkBOjNMOe8jegJE07jn/FWHtDgQhTrSHQGfgerKs1nkUNo7VLZxyFotsX/7qBuk WNaQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1713754502; x=1714359302; h=user-agent:in-reply-to:content-disposition:mime-version:references :reply-to:message-id:subject:cc:to:from:date:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=QRJCa35xITgA3o6nJAzVX5FmK968RqVJUIvKbBC3Xao=; b=OFYO1xs4q8FkqNBjwd+HWoRFtGT/Ra3/p7uUwiFZFiTQXkT2j861qwYIr4tNydcbsd 3WBJUb34Qg9SOILef2saCL82Ljk0WxxMW4atZDS2+VWZNvqAeQhZj0EOaW3OWcxDrkdc D/X66vCgt7oeLyuYEI55UwOFKZpme8E3Txn0Fy/KMxNw4rVQA/dxtlDU0AZMshj6j8Sx qzR3J7katcUnyIHXUlRanPeGOhXFR4yNGwy7HxTK9j3NLkfDnPbQbqcd8KoxsJz42irD LBmwbTXLWDeVW5UcvfaznPmT8PY3XM4p+tUdaXWW3SdwyHEaG9ey2KfXOLh8g11745xY KQZw== X-Forwarded-Encrypted: i=1; AJvYcCUYQdybNoUmX3VD4F9nzNCRWE1Kjo2hOrmeyOlGBfEbSS7WgwR2z2VVWe7nls21CvBehu/cW//AJSwT4xgt7FJ29+M= X-Gm-Message-State: AOJu0YxeapNQTArQ3dGICqNkM08a8carJyK9XfoIQK9szr4AmMoWXpwQ yIN7ACBZ5tPekUr47iMyTBnYQyjV0RHh44K9pfedGYB+Q/HswCqz X-Google-Smtp-Source: AGHT+IGY3je4HxjaCTqBF72gxtNufrsNYYGLDYq5X+QmcSkg5tF93IsOBpaTTzfQWeyMawrLoTQgHw== X-Received: by 2002:a5d:62cb:0:b0:34b:eb7:f389 with SMTP id o11-20020a5d62cb000000b0034b0eb7f389mr766655wrv.71.1713754501492; Sun, 21 Apr 2024 19:55:01 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id z13-20020a170906434d00b00a51e5813f4fsm5267310ejm.19.2024.04.21.19.55.00 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Sun, 21 Apr 2024 19:55:00 -0700 (PDT) Date: Mon, 22 Apr 2024 02:55:00 +0000 From: Wei Yang To: Mike Rapoport Cc: Wei Yang , akpm@linux-foundation.org, linux-mm@kvack.org, Jinyu Tang , Peng Zhang Subject: Re: [PATCH 1/6] mm/memblock: reduce the two round insertion of memblock_add_range() Message-ID: <20240422025500.n5542xmrc3zy4qgb@master> Reply-To: Wei Yang References: <20240414004531.6601-1-richard.weiyang@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: NeoMutt/20170113 (1.7.2) X-Rspamd-Server: rspam01 X-Rspamd-Queue-Id: 5B87E20007 X-Stat-Signature: 6k1qy5h9zm39jp5pomxi5spzumpxp7c7 X-Rspam-User: X-HE-Tag: 1713754503-33495 X-HE-Meta: U2FsdGVkX19JydYxK77NDe9IpCTEHZhQNtVundYSG3zQt4gywStcggJ7+EY0Uopc5go53t4Ln3Lw1KxoaGMskTKqvWNJkwsO0gZF/k4JZ3VEXrV+N1vRRSz9BPTF18HdjtBzpwg8+0Z9HZ/+dJfacrMZ7o3RG0YjkBlVGVg1pBjcwMUBlDf+GWY3CyzQ0QxhYHN/DaiKzYdJN7QG7KOVik/w3/19nCY0tfUaN/zEOk7536vdfM0f+1P/fysHeHjMeapDbyvU0f7F9oKsQ4Ux6R0q/cF2KkvPW1kiL08kVi8E3SXyhLmfTQwVNB0KxiQGCXr8T8mNrug8IRZBVfQ5/7sT4IAh3+vlOWnXDFPU4DPd+2pngZaB0obS1OvOz6AqpGab2bYXu+BAUh+CEjQUeFnxPbZrWfClfFph04zdYk+ta96P1JdDnarzdo7p8KUDgvSqr2+uVKzj+TAAgCIvoZjDF5LV2KAQnaajl9rFLeYY6Gu0CuBB4wJf9blttEPEkuzXBLpSWopoggwarjq1ueY+9Uyg1dK4/TMCsW5r/TVBHU+LYgR4Rhek0pBx9vhroRTiZwnyuD/HuhXm39G5kYZAb/fcvm3j0FJmnZrneEmVeC9HM4wfqxsERKF3YetZS2anWoXMr82v87Y7uBM8eRH8Gr+FaK7Mf1Wcaom+UAM+k7pDdf+pKkpikjdU5FaP0xz4lBBjPl/Zksfz0XZdFxaIxU+OSAGBcBYpKQmb9vvidGmc5atSm4RQWV+O11MKvnBY4Udi3GkRBJK88U0V1TWhlvuY8rpUFRmJ/Krrs9qRl1fcmnniCjf4IhPM6kszKR0xaBA/BG/5A2HamZq2nWoZzxTKjJzXxoak16aEUZIabMFVF+Sn61OMU6nYGQQcw3b+aJ1+TZ0Gp88ifSV8RZApBBgr4IzX0PX4T0523v+s1cN7gEuixROmBVizTjmnSzviOlkxLYmMRtFQSIz /jr4Vzk9 GnHtfO2UV5QOCqS8zLcsYpuzdEy0VnMepmTsX2nuTuIe/L6KXotjXWKy/8xcc6iWDl0zd82zMiptc9f9gAei7BIEjXdvaD0Y+Pn7jp5LcB8J7mwKaOsnRsU5c9JDNnIw2D0x51M7XvVbqo8FJ1hX0G/zyS2Nkdql+KSN0/5VLDd1wYapoIn79Ywqxuht0sSMggX46qPhnero3ULlzcHd3dFEu7pzn7iGUjRt5ciBZjleg1RDszs04Wl/hwBcwBN9tTu/3Dli021liYTUIikFO5ouxnP+GH0L8ljhOYVbaapLxbRGj7lM6NeihwpUEjjSL1IRpIN3mQbjmOmn5h0EA9u1+3n2SZ6VBAHoj5KmKsAxpZtcB5EQjMvb6NL+LABvIFIpJQ/I5t3U8+GYYaLfpF51Hm9z1ktHFWaphgdgen6b57nxFg8USfcYzkVF4j8YVd73SXO8v1Mprb062/3w2XX3LDm27ndV8mI/YPv4P4K/0+fwo/T0ty8nVOezFoYirlzsYiRfWDZI4mPeJtJZJsYqrt89Jpof0oxtvcgJXLj2c+6ySfn1qOUewJtzU425aMzY0dYySkmTr2XjAAVJlHYAPnTAGsIbNkchhay15/xPr4lg71ACWuUQD34YmhRw0p6MV8Dym9wagtAjb153EpZI5GcLZ+QTjWKaOF4lE5z/wfyfaraX6WZEYDmGAmw9hp6TQ0sNl2FEonUx1y/yJ0DI6f2Syb7+JRETRiYPz+OxzlHVsql8EkWWqo/hrxQWZbc0kI105U/5/KtrPWH+bLc5GNw== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000187, 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 Mon, Apr 15, 2024 at 06:17:56PM +0300, Mike Rapoport wrote: >On Sun, Apr 14, 2024 at 12:45:26AM +0000, Wei Yang wrote: >> Current memblock_add_range() does the insertion with two round >> iteration. >> >> First round does the calculation of new region required, and second >> round does the actual insertion. Between them, if current max can't meet >> new region requirement, it is expanded. >> >> The worst case is: >> >> 1. cnt == max >> 2. new range overlaps all existing region >> >> This means the final cnt should be (2 * max + 1). Since we always double >> the array size, this means we only need to double the array twice at the >> worst case, which is fairly rare. For other cases, only once array >> double is enough. >> >> Let's double the array immediately when there is no room for new region. >> This simplify the code a little. > >Very similar patch was posted a while ago: >https://lore.kernel.org/all/20221025070943.363578-1-yajun.deng@linux.dev > >and it caused boot regression: >https://lore.kernel.org/linux-mm/Y2oLYB7Tu7J91tVm@linux.ibm.com > Got the reason for the error. When we add range to reserved and need double array, following call happends: memblock_add_range() idx <- where we want to insert new range memblock_double_array() find available range for new regions memblock_reserve() available range memblock_insert_region() at idx The error case happens when find available range below what we want to add, the idx may change after memblock_reserve(). The following change looks could fix it. diff --git a/mm/memblock.c b/mm/memblock.c index 98d25689cf10..52bc9a4b20da 100644 --- a/mm/memblock.c +++ b/mm/memblock.c @@ -395,6 +395,7 @@ void __init memblock_discard(void) /** * memblock_double_array - double the size of the memblock regions array * @type: memblock type of the regions array being doubled + * @idx: current region index if we are iterating * @new_area_start: starting address of memory range to avoid overlap with * @new_area_size: size of memory range to avoid overlap with * @@ -408,6 +409,7 @@ void __init memblock_discard(void) * 0 on success, -1 on failure. */ static int __init_memblock memblock_double_array(struct memblock_type *type, + int *idx, phys_addr_t new_area_start, phys_addr_t new_area_size) { @@ -490,8 +492,24 @@ static int __init_memblock memblock_double_array(struct memblock_type *type, * Reserve the new array if that comes from the memblock. Otherwise, we * needn't do it */ - if (!use_slab) + if (!use_slab) { + /* + * When double array for reserved.regions, we may need to + * adjust the index on finding new_array below + * new_area_start. This is because memblock_reserve() below + * will insert the range ahead of us. + * While the insertion may result into three cases: + * 1. not adjacent any region, increase one index + * 2. adjacent one region, not change index + * 3. adjacent two regions, reduce one index + */ + int ocnt = -1; + if (idx && type == &memblock.reserved && addr <= new_area_start) + ocnt = type->cnt; BUG_ON(memblock_reserve(addr, new_alloc_size)); + if (ocnt >= 0) + *idx += type->cnt - ocnt; + } /* Update slab flag */ *in_slab = use_slab; -- Wei Yang Help you, Help me