From patchwork Thu Jun 15 13:08:52 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13281264 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 B31A0EB64D9 for ; Thu, 15 Jun 2023 13:10:33 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 3F9C36B0072; Thu, 15 Jun 2023 09:10:33 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 384748E0005; Thu, 15 Jun 2023 09:10:33 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1D56A8E0003; Thu, 15 Jun 2023 09:10:33 -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 0506D6B0072 for ; Thu, 15 Jun 2023 09:10:33 -0400 (EDT) Received: from smtpin29.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id D255C1A08B7 for ; Thu, 15 Jun 2023 13:10:32 +0000 (UTC) X-FDA: 80905016304.29.AFE9635 Received: from mail-pl1-f172.google.com (mail-pl1-f172.google.com [209.85.214.172]) by imf19.hostedemail.com (Postfix) with ESMTP id EAF0C1A001A for ; Thu, 15 Jun 2023 13:10:30 +0000 (UTC) Authentication-Results: imf19.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=l1V7kQJL; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf19.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.172 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1686834631; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=t8uMjI1Tkwt5zl80wRd5zFszf8LWrgvycYShg8nZg9U=; b=PY/q8MsYCHygn8kVATSWWOSSwB/hzRwendqFVKwP6POOOrtClNHObXslgaP14Mig8fRKq5 Fq51OSrGfda7I7eHDbbnohl9EpKWgbtIxX+8GWMZAAyUfzP9qofwOqGeuoisHJQBDbgoNt KGCN6ObGqMnGSRx9bruQIm6VD5iuLMo= ARC-Authentication-Results: i=1; imf19.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=l1V7kQJL; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf19.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.172 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686834631; a=rsa-sha256; cv=none; b=35OjF4jEA64fjFTYzvk5Hkug704KFjD3Pi5s5NL77SiPOiNvIJyVEC6agR66/vbRIbIoXv GmjbITCwQ2TFJqPs+9/eF+U1kBE1FOicp3dk1uV8Dd6KgKxIwUM4s7WKCdMegnqGZpCqeb A4nDYiMwdBc1ef5tTZK+B/G0siHPEKw= Received: by mail-pl1-f172.google.com with SMTP id d9443c01a7336-1b51414b080so7076015ad.0 for ; Thu, 15 Jun 2023 06:10:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834629; x=1689426629; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=t8uMjI1Tkwt5zl80wRd5zFszf8LWrgvycYShg8nZg9U=; b=l1V7kQJL3oyDCiUF/OX7fjrtf7DZRR7RI2GYk9oEhjuwS5LI2YqP0f4o3ddXjCWQWS xXdKgruRFLIYy+1PhD7MZSSVXOb6BErBtCQdSZQMObTLlY0qM+CKupkWJNruRGfSEmfc oW41beRbt3HRy9w2l2O1DcWBYDVPZiSG2DRRkkjsbHsDACrSHKZOVAp8ZqhW1aIdEUbH Au/zWMZPo2SzO8wN9yNtmxVPcruM3FvQe3k5BqqCXDFBmNRDX1koxSPrzHPpuCff26iy h7xcxA0B3BRnkC6K8fQClPedS2wE6D3qIGnyt/NxBtZZFqlppa+0JXPsytq4Fu6UJTAy HIiA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834629; x=1689426629; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=t8uMjI1Tkwt5zl80wRd5zFszf8LWrgvycYShg8nZg9U=; b=Bm00sp30riWVKGYKnqq9cMtlfs38bkB5mdFHh9CFJfR5coOW/usrH4yYgL9ztPKB6K fz3L7mO0BGmsNAza5R8lkQXX6LhX3bFmfnQts/c7oaiCVLrNWPGOATNkic21UjieaxMm IEW1KkHpLwiIyNOlQKT3PwQzSoOUO7+0JxETMUIa87k6hLuVQCr6ZDcPTjaHt1JSlQyo QB8w6EVvt7wZQaFRxvyl3piJGnRIBKwL7oXu5Q8kTW/fvU9NGBxtf+f4rP4Fa02GuMPG GtrgpXifkLS2e+VXFUjHdeH3g/bakVsy408ScGcBUFgBvxqK8N77r1KCMTePR6Fgz85Z E0kQ== X-Gm-Message-State: AC+VfDz7waq2jnrIOmsFUOG+fDl023OjfOaqX73cTUGRqWxR4nL8OmEh +WVpxNo9G+yD9lv2WBruCPPx/g== X-Google-Smtp-Source: ACHHUZ5rliJjSYTDmlWHluKhK3fS/k6VkVj5cW2hkY6zYL+BLggnSeHKeKWIJy07Iu0sbBZ66yxn1A== X-Received: by 2002:a17:903:41ce:b0:1ac:8837:df8 with SMTP id u14-20020a17090341ce00b001ac88370df8mr17054187ple.6.1686834629690; Thu, 15 Jun 2023 06:10:29 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.24 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:28 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 1/8] maple_tree: set the node limit when creating a new root node Date: Thu, 15 Jun 2023 21:08:52 +0800 Message-Id: <20230615130859.21858-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: EAF0C1A001A X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: exet3xwya9shsofr43uf8yy715f797m3 X-HE-Tag: 1686834630-913397 X-HE-Meta: U2FsdGVkX1+Wn4GtMq4mK5QxngLHld1bUS54HyaLfjLt0PZOmGGxwfLrlw1ZW7NHaVbkw6oKiW+jkY3VMw64Hms/B63yDpFI5DTPeyK6upGQt2+zd3EZaBlgFsW5f0Mff8REQ72dZ2WZSHvo+Aa4S0OO61h7iqMSLeQ1Dj7w1WqyUGWvEywt2qSnbt9dRnpFMzNFqOnVPRAPhcyxafbwwAsidE2F8ihTJh4rZJYWMeglWMBzqswf6BX531O5H3+OmV3Wh6i3ISB6VPvbZU1+WHHvX5gMd0a0KqhmqM4uwyW1POIIVcTX6vgAAbbMWBBco6llQzNEmXP1ecSTIxr6BmSlyXowEVCFOqHxCu6pK5KHOHJ6f1i11fErikIPiYjRfJxZG234hIcoidb95ENr8PqBJ4yNhMohpons8pGFszMRpkIELZdGh4TIJNvz9UlPGedg3WeONBXrAv8HbBlJXmcrRBP21kX/G2yGl0euCgJw5zNuKkedm+eWBctOFannoAQN7xI3NYvZJ8zvQLKxSrehTeeSGQfbrcSmTS/FdLf5tw+upTcHo43fXInZMblSkxM6Nhw/6cDqOmvRpP2oANw0BYEJTNt+GaviKh0+kvfQnRuCU2PP4DJXB9XjO9fr5024ZlOxNVjsVf70sAspYYruVvVBJifEP+OuInROuPiiGR7xc5C89tzd3hF8Z+LMUrvHdJOyjOQfgx1EcF+lbQBXyhsvWw8d638ZqD3AUJwnwfa0j8b7agn37RWk+Bf3DAQe7H7g7YHfyNSDt2eCc4yveiVsIYATEb3PAf/Ftd1Q2ri+OTeb13QCeI6aD/Mf/pVPov+2nCVuH+JigyCYB6h19KVIAnHN1RwYoDYDfh2fUzJWM/+RQ6HQ3ggbap175UTxgeGk+k+Cf+X0gmNp4jRh9v7k4gtUk3MdVnl/6c+KrDe/s1E44+WYxGPDV8rN96Or5AG6FaXKhNhZBoN 3IsqQ2o1 bOIqXMaGu9FzstvJnb0vx+3XdFEhvFDehfy+60eSF3frx7WrtV0o5y5wJBxG7yfvrDuCQliErBOaSPkxvoSHv98vFq3IWXWLwx0Ro0bxhbvrX8up1vZ65SWnnwtkF0BigFy5cVdQqEBr9zceneWTwk9LmanqJP+ZdwHTnKSUoONllSTR21qOkQoIL/4AHmaFY5FI8riQUshXgfYBPyQfRoRpvJWAgA04QZSQ/VHBUE5AAKEeAdphVrcSbLVks8b8xcTts0WdmAd52Q6uhtJShNxiW8cIQI5ysfEOfG0htmVherclLOv/UOEsi35F0usEIeSm9yyYbnwJE7DZwtDecryWCKCS+9Vo84MAGuhgv32PSZX0y0ABWuXzFnihxVBOb52DhcmMz0+2qDoB0qJm3wrG1kw/fpZQAybTSlu0fQpoXI0szX/v58peqghe/vxE+y9dzl6X8E1oTi1c= 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: Set the node limit of the root node so that the last pivot of all nodes is the node limit (if the node is not full). Signed-off-by: Peng Zhang --- lib/maple_tree.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 279b871f21a6..23202edb9f1e 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3692,7 +3692,8 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry) mas->offset = slot; pivots[slot] = mas->last; if (mas->last != ULONG_MAX) - slot++; + pivots[++slot] = ULONG_MAX; + mas->depth = 1; mas_set_height(mas); ma_set_meta(node, maple_leaf_64, 0, slot); From patchwork Thu Jun 15 13:08:53 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13281265 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 4482FEB64D9 for ; Thu, 15 Jun 2023 13:10:37 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D96296B0074; Thu, 15 Jun 2023 09:10:36 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id D1F658E0005; Thu, 15 Jun 2023 09:10:36 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B99368E0003; Thu, 15 Jun 2023 09:10:36 -0400 (EDT) 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 A49DE6B0074 for ; Thu, 15 Jun 2023 09:10:36 -0400 (EDT) Received: from smtpin16.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 6E9B2808A7 for ; Thu, 15 Jun 2023 13:10:36 +0000 (UTC) X-FDA: 80905016472.16.E75FDC9 Received: from mail-pl1-f170.google.com (mail-pl1-f170.google.com [209.85.214.170]) by imf09.hostedemail.com (Postfix) with ESMTP id 87808140002 for ; Thu, 15 Jun 2023 13:10:34 +0000 (UTC) Authentication-Results: imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=lacYI1rd; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.170 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1686834634; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=h6/zuKtdX43AYOwkx8Y/LcH+jU9PgkVm8ZKPRILAQQ4=; b=2EaHvGRC5X09ukgvIEN2RWNY0UP6bmuXhniyWyhS5jF9oH6vMGAR1I+29r13iiH+Oz9ynt JmZCgfKlb8qUpM6rJamAMyoiJmn6QB+6v7noYmPdCzpdbv94XKbxecAs6PUOI5TzRD+4tK 5NqEuWgKPbLhs0zvSqD2yH8f9NS+HNw= ARC-Authentication-Results: i=1; imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=lacYI1rd; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.170 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686834634; a=rsa-sha256; cv=none; b=5ApJGzEVObs/VGboqnsJmFnWfGJysLHw6ap9ZwXcostNNfibnED9C9CfxpZR4atHUTyVl6 GcbbID6T8lBxw+HwK2yJA5SLuGKE3PTH6jdHsV7VCeqI4xLDCSIvwAf62LZVbDTkfCWcX+ tCJz2fRHMcaZ7ybPYCPB64cPxsRQUOA= Received: by mail-pl1-f170.google.com with SMTP id d9443c01a7336-1b3db8f3d07so25465505ad.2 for ; Thu, 15 Jun 2023 06:10:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834633; x=1689426633; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=h6/zuKtdX43AYOwkx8Y/LcH+jU9PgkVm8ZKPRILAQQ4=; b=lacYI1rdr01pCdKfMnHhOKSCgbbBcVdmvwoMpr0oZyI57wLUeehSv5VQlOckRsf5J3 QwhNEOl0DD1FfI3cPy9Z9ARfNVfzViCEPcpq03XbXk5so1vLbh7DPPRvpWO1zi4bomBO 5EbytiQEqeWF2jRC+LaPbXlHtXlCG4qOPd7q7hU8lFSMsJL5SL0LGE4TM/XGlK6GPGuJ iXGq9IAho5nY3K2O6BfuUmtjOhLdtYDQ2x1ilR7xqptKeCyr9ahA4zheIQqe3U2QGjsA xUmmiKov49NhTlzUKrGnBWPBapM+IwdvYyEfaCSov4WzDmpMBvBIQUcB1Z2ef64knjTX tz/Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834633; x=1689426633; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=h6/zuKtdX43AYOwkx8Y/LcH+jU9PgkVm8ZKPRILAQQ4=; b=eLC+y3yiZfYeBpTHy/d6Kjl92OxPCbcpyu/+3tFM6BlIbn1MsvrB4hqdNhaqcTq8Ki UFaHT0UJrk2ZIn6p7BJqRbsxA0yAmVqHIsupu1acFHisuwJotUVtkOrdIZHYECxtxv1M pZO6F+v6kfmiulhKGcCYAnObyMhr238JRjY5FeagxINBUEmdwEv8Ly8Tv/zOuH4SQCCz c7O2zjbGGh8BBdr/c2PP46tbulYe+8lDN7qKF8KzK+nxfxNB2wJepgYTUiUCvXECdtks DLcaIrC7HZMz/F9eYMSHDNtGL8gJ/aQenXbbXXEZINLuzgp6zI531vJyw+bv9LHcoZpY o8qA== X-Gm-Message-State: AC+VfDzHhZWoPJN37CbUZToH8xCvLOVcSWKvHk3tpkAfckCYoaWxVC+F CXlBJfeMffNwSdhCoZfrCRmadrHU9GzTyu5++zY= X-Google-Smtp-Source: ACHHUZ6ClsMMuqONIhSHw0V4cLgVblslnQbletm4QH4BqdufHG1FhyUbrsEu2gxGbJhTSD33t7/k6Q== X-Received: by 2002:a17:903:32c3:b0:1b3:d8ac:8db5 with SMTP id i3-20020a17090332c300b001b3d8ac8db5mr10723526plr.40.1686834633447; Thu, 15 Jun 2023 06:10:33 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.30 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:32 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 2/8] maple_tree: don't use MAPLE_ARANGE64_META_MAX to indicate no gap Date: Thu, 15 Jun 2023 21:08:53 +0800 Message-Id: <20230615130859.21858-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 87808140002 X-Stat-Signature: 7epkjd7qwgf9of3uqofw7cstkhnmse89 X-Rspam-User: X-HE-Tag: 1686834634-56453 X-HE-Meta: U2FsdGVkX19jf8QdUZ/TD4Ii0CA8U1aNjMdzQoWx7DN0x5MwcM8r52G8j/Rl5QAAe87Zixz/vIhPlLo1pkdjB6377Ojfo5xroW64/POUSpEiLA4WKbrnEOIMYd3BLM8UJzPaQwFg7VcJtvrqHOsXwHfjHbiNb6ODIZimNu3/iCXZX+0bToGnMvy5LmaX2+kowNq3YK2I5fKb0wA5uc2EiJgNhwJesHBTVI5cBV5cwzfH9CNXXd2KGflrvOCABq8joQGyzix8tQHB+976TlVnLcIszAN3IzlLyWCJOWB9i7wzGLzdFopqcPKb/QHP42WRUIcZw8zeV0XixphNwQCzLOWiPqBiJzXTxrLmP77PnZ/rRN1g9zg1XwQBnY/joMbIw2YgAmEkd9bpn2Al9uLeNU4k7b5BarQcYHlWgZtE/HR0HhFouoj+4Jv521eexy3+FAmYIY0i5S57+2i+7wzC86LotPmHKCgLrMgTZqQ5yHGcjxEKUF+835nFyXvGIzbu1BX/bAu+F0u8GgfP2ka51F5dGGh7MHNSjZaL47CUM1+JV7TJh8+L9wB/C3Ubu3AttuxLQqHIi+8EN6Q5zOs4opM2dM0XGM4ko32YnrJ2+Nz9FqS10/kgH44JY3KAANcNUOcAa38QetIZFDsrZpfBgRtRPVVYLvGvWV0vAviGuslNdyhZKxiVMKSficwPV9jC28/rlxGNFexuNgj0lrvtUGnWeebCW306h3wdceKAFj7+cZpO4xiB8s8mWj5U98imby0oDPZEkxyx1t+PDT+4+HfsvKXalwJPmFQzHpTQbjCzgwmK8/EC36Xr2418eMz/qJ9ceAGNoWHSb3/K7aL0ZrfWIstNYCZ5lsQ25G2kTCmSc/xTSjb4/4ONfkg+8o0r9z3+/ZgKmFBG/S/XnaInuIzQ2jnm5RYKGmejKPoHgHCzQnkhiuREqxIbYiuS0o3GQ/6pXsB80kD8kRJAuNc pFCAudMu OzE830p1CemXIZpJ4Yo02HuKp8c4EUdUAth3am7cFez5/G+93wxnllqW3XratVmPZmjpCmVcYuf5zhgg0wECFOnkmhVRtP/JHp76fHVCV3PCgUs8rWD/Pf0HfJ38hll86jQyvCwytzIMUvRWVoqxnK9EmOyIllbNSrOH2FGXbAOEb/HNr5SEh3G1rCYL5cXLBxBHIQqoGv6OY1r+b5c5JINajsErJbhGkhHvcvLyp5miRhZSvjNR0+y22OpF7QGLTGNRQCYqKWPvrf77KBVCStMZI8OQBuJ8XfGJhExxWMwmsbQ8DI056p60guKROBcyb/+2mv5nyuSBZoWEISsbDEKvanIPIHebcpEkmMpjdh3tIm4pUIPdspqbZ86VIdWY9YD4ml1aUzk+zRszRYRLrKtB1JYOe7HgdHZbTgPvISDkM6vLAKwdv6vLvM+zk95Cj5p+LRUvAooltTFg= 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: Do not use a special offset to indicate that there is no gap. When there is no gap, offset can point to any valid slots because its gap is 0. Signed-off-by: Peng Zhang --- include/linux/maple_tree.h | 2 -- lib/maple_tree.c | 13 ++----------- 2 files changed, 2 insertions(+), 13 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index e18ecbefc7f7..4e004d86c780 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -29,14 +29,12 @@ #define MAPLE_NODE_SLOTS 31 /* 256 bytes including ->parent */ #define MAPLE_RANGE64_SLOTS 16 /* 256 bytes */ #define MAPLE_ARANGE64_SLOTS 10 /* 240 bytes */ -#define MAPLE_ARANGE64_META_MAX 15 /* Out of range for metadata */ #define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 1) #else /* 32bit sizes */ #define MAPLE_NODE_SLOTS 63 /* 256 bytes including ->parent */ #define MAPLE_RANGE64_SLOTS 32 /* 256 bytes */ #define MAPLE_ARANGE64_SLOTS 21 /* 240 bytes */ -#define MAPLE_ARANGE64_META_MAX 31 /* Out of range for metadata */ #define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 2) #endif /* defined(CONFIG_64BIT) || defined(BUILD_VDSO32_64) */ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 23202edb9f1e..8aba9e419e08 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1610,8 +1610,6 @@ ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt, * mas_max_gap() - find the largest gap in a non-leaf node and set the slot. * @mas: The maple state. * - * If the metadata gap is set to MAPLE_ARANGE64_META_MAX, there is no gap. - * * Return: The gap value. */ static inline unsigned long mas_max_gap(struct ma_state *mas) @@ -1628,9 +1626,6 @@ static inline unsigned long mas_max_gap(struct ma_state *mas) node = mas_mn(mas); MAS_BUG_ON(mas, mt != maple_arange_64); offset = ma_meta_gap(node, mt); - if (offset == MAPLE_ARANGE64_META_MAX) - return 0; - gaps = ma_gaps(node, mt); return gaps[offset]; } @@ -1662,10 +1657,7 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, ascend: MAS_BUG_ON(mas, pmt != maple_arange_64); meta_offset = ma_meta_gap(pnode, pmt); - if (meta_offset == MAPLE_ARANGE64_META_MAX) - meta_gap = 0; - else - meta_gap = pgaps[meta_offset]; + meta_gap = pgaps[meta_offset]; pgaps[offset] = new; @@ -1678,7 +1670,6 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, ma_set_meta_gap(pnode, pmt, offset); } else if (new < meta_gap) { - meta_offset = 15; new = ma_max_gap(pnode, pgaps, pmt, &meta_offset); ma_set_meta_gap(pnode, pmt, meta_offset); } @@ -2076,7 +2067,7 @@ static inline void mab_mas_cp(struct maple_big_node *b_node, end = j - 1; if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) { unsigned long max_gap = 0; - unsigned char offset = 15; + unsigned char offset = 0; gaps = ma_gaps(node, mt); do { From patchwork Thu Jun 15 13:08:54 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13281266 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 5D370EB64DB for ; Thu, 15 Jun 2023 13:10:41 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A89B06B0078; Thu, 15 Jun 2023 09:10:40 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A12688E0005; Thu, 15 Jun 2023 09:10:40 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 8655F8E0003; Thu, 15 Jun 2023 09:10:40 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 729246B0078 for ; Thu, 15 Jun 2023 09:10:40 -0400 (EDT) Received: from smtpin25.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 4882D1607F5 for ; Thu, 15 Jun 2023 13:10:40 +0000 (UTC) X-FDA: 80905016640.25.201614B Received: from mail-pl1-f181.google.com (mail-pl1-f181.google.com [209.85.214.181]) by imf22.hostedemail.com (Postfix) with ESMTP id 6BBF2C0002 for ; Thu, 15 Jun 2023 13:10:38 +0000 (UTC) Authentication-Results: imf22.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=JBdX1l1x; spf=pass (imf22.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.181 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1686834638; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=MG8wEkfZhYGC5aupLXEONPEpLbQPJyBuYKNQETRNYXQ=; b=GF+pVeRWfxIWL1jbBA9Y49XZ1eWx0KnnUfqIn1fcttft7feDdeCAGli6MCnWd2U1RXagNL dXvp2MtcReznynWsBDSIkTloVvK2lB5g41lo2subS2cZ6J1JRVJO8rr1mUxYH83lj+/mi2 vmcclE/rhOPCZebHX0kSA3DdDY/WvSQ= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686834638; a=rsa-sha256; cv=none; b=BTAJ7x5/hpZPr/G2SeNmj0+bGanVxL/lhJUkTPV4R8lq0gnpsLLDVkTDrgVl0kvD7T8tlW WWE8UJHaS8Z1zmNZdxCTO/59JxFZWe4osWHwVX1m8cObtzIpTELGC2OqZGMi21XGXKzxqf 1v0g8F4IBm+tEkXy/rz7TsfioREZE3s= ARC-Authentication-Results: i=1; imf22.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=JBdX1l1x; spf=pass (imf22.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.181 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pl1-f181.google.com with SMTP id d9443c01a7336-1b50e309602so10889145ad.0 for ; Thu, 15 Jun 2023 06:10:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834637; x=1689426637; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=MG8wEkfZhYGC5aupLXEONPEpLbQPJyBuYKNQETRNYXQ=; b=JBdX1l1x+iSg2CpjvKE+gC3fQ5LWgXkFJ7O3qRqfSLsduXgNEEnfZyRZYD+aaDtn7N uSkoiI3TK2NJb/opjoa/il1l5jtgGuKT70/3p9YVeEph/4m8CwB62pWy40V19y6b3aBt T+3f4gBTnPVMNomBZwR+rHzM3IPEpaFZKEVHjpr3cDYsT085CBjG839Y0kDt0RG7zprr cs36S3Z9fzu8SZxcfDKFdL14UvqkXTGVFkmjRRMVFjUSG++ubc5+L0lc0JrsYkImHvD1 qPTGQOAli/Oa9AWBv0XxRDill+ZhjXzuiBCDJbggf+iwNECB11Vh4LZldV3czFsyeBDD w8IQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834637; x=1689426637; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=MG8wEkfZhYGC5aupLXEONPEpLbQPJyBuYKNQETRNYXQ=; b=dxmgAswPwuBzubmmdwcs97NoCHy1R85PsJEKsbSuwD9AGnWx+TB6u2nqVGVdWx5CM7 6oWkA8mhZGp2rkrxFMsnOgwYX+pOOKcFuCMsiDu+EDLLIfhT54yw1Eg7pF3yZZxisVXC 7oCCMfKJqof7e3nkMLbB8lm7ZG4hwppRyTXZteQ5akvksXo/fzSeSBMtF+pWd8aJmICv zLOXq3lzEFByyOUOv68oxFCLThkWFPR+nsrUq2h4wsjk7IfXIJzZSmbwHbGCY8ScyV2G ulTSi/L9uyAjy/KTy56eC2pW5RXXkzWjm8yXsHPE1i8pIdth5oBxbCDYPbXQ2aFcMXZr ZRSg== X-Gm-Message-State: AC+VfDwP3AKWOw/UyDktmjHwbV/8SkST5njt8ugw/gBSv1gPdi7AcLTQ gRFLhDpyYN5eC6OQ7UbD18TjreCYducSJR97WVk= X-Google-Smtp-Source: ACHHUZ7WKJVUJ+SDKFA9ptbKZMIDGFAgwrtvXxZ4yz/AJGuNYEZLYBZtCRPVCyj7PJ8FHVY00ecTSg== X-Received: by 2002:a17:903:1390:b0:1b2:28ca:d16 with SMTP id jx16-20020a170903139000b001b228ca0d16mr13196115plb.44.1686834637281; Thu, 15 Jun 2023 06:10:37 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.33 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:36 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 3/8] maple_tree: make mas_validate_gaps() to check metadata Date: Thu, 15 Jun 2023 21:08:54 +0800 Message-Id: <20230615130859.21858-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 6BBF2C0002 X-Rspam-User: X-Rspamd-Server: rspam11 X-Stat-Signature: k4zdbyyd4gpajj855imx983fuxpd9qsj X-HE-Tag: 1686834638-591114 X-HE-Meta: U2FsdGVkX19YkRUZ6RAyI0pIK3FLWoa7g7utGYCRMojxJRAC6VcHv+hm8X71StfrJff31mCnUwSyTJHYZmoPJSYTkv13JUp448G9a5ugDoCaYOiHezXOUSeQmgndtXRLtSCAOXcAc6zscj4NNEFR+PlFra2J6RqE7VdAkXx12Ejd6AjslFHZq6MlehjCpqZa24ZRw2cSy99DXa3mhsx3r/1bYGQiEWfV85EXbJ6ub6Enx8kN2TvnT/XahUzamckv/s48WaXW8XOUqpNT4HqnZlKJDdoghZ+sFVdpSVa1y6LDOJ65VWArsA1cS9PghD0pFywav+2Yf2wkdOHLVE5R+1wLG5KRTPGWCBxjWE0I6PL+k/U1SVUpZupYBSVXtFpio7L10zZs42cEEbWrkiQO4W24nzuPxsbQjl/oVWt/YlNRZ7Zec1ZgMF4BGjN3OLDnmGzN3wWJTipoBQNp7AHCe2Ai8Jw9tUjfyimYuM+qn+EbtVw3YnOYJPp7IbDZIgwplLMlQhtuqWdQLU7eVw5Rlc6Osoh09f5AZN+ZpnvFD1jagRCbYmdLZMEM1cr/WZXWfyP5vyaNx5z0e6D+LSaR+N+Zucg0g/uWB7SfRzPkqddIqnBsCGbCgPqfb2cZ3/5aeCqiA0g2kueupyGfyYp07BkYeZASPqOqHCtZZoOmCP4Xrz0YeyhrCiVP9h09YbPh1sG3zxroD4dfhZZFIq7p0AQ8UWyxjZKzQyf1zV4ESoTGHO5jLcpOHSRx+wx06AuEbYmM7HwMtiiAt0DbIWVnqsKPlftALByai+1M4/dfc8Y1imwh3ot9QXeA30Iy31A4Ekb/LnnOqglJc2uKjwC6LMPt/YkTF50+A4SkDG7X1eP+YZGcuNpmms/cCC/hM2zuxMdOOEwMC95vCN/YYCg4s43TOIEZny6BnbOOpfLnua+SPhGJ6tjOyYqBSYGnIrdfcyZU0VGrLDzjvhUIEA9 jH39oCyv PtxVyxs/P1Qbf/qHgvdCVBCTWStiPnj38P/Dg0R+su97W2qpMNvnh7RSviwFQji34AivMKJudNi1VgATasC+FSq3PWL3rvUhmJgkjGr04hY7IXRiDBYjLbjj4lQ5xewqIcLsPmFDJIcYvNF9LynusXcoXPulFrK56OgPDpl0GZtNfolN20xGKYyUSCPOpY3G6NCsMttP+gLjdc3oxVTTXS+f5MaPWQIk/U0cD6TAbacvL7LRj6zWO/UQgEXkQMr7oWYl9uYICoabaYS5xeNEaTyrLYbRJ187YOkziM6ezN8KTc01PGU1XeVBq3dBdJD34l1B4QX5/DeQz9Cbmp3R/GwLwdnwv8pndvFyVanxOsKyivIo6Yo5+f3rUo/JfvJojSjva+rxyu3kQQUwIIY1yY5F8IYx7//SXWrwcmOE4194Oxeovlhn3zJQq/YuN7l2Yn+1f11h3AgL+s2E= 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: Make mas_validate_gaps() check whether the offset in the metadata points to the largest gap. By the way, simplify this function. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 68 +++++++++++++++++++++++------------------------- 1 file changed, 33 insertions(+), 35 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 8aba9e419e08..799afd590cf3 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6979,15 +6979,16 @@ EXPORT_SYMBOL_GPL(mt_dump); static void mas_validate_gaps(struct ma_state *mas) { struct maple_enode *mte = mas->node; - struct maple_node *p_mn; + struct maple_node *p_mn, *node = mte_to_node(mte); + enum maple_type mt = mte_node_type(mas->node); unsigned long gap = 0, max_gap = 0; unsigned long p_end, p_start = mas->min; - unsigned char p_slot; + unsigned char p_slot, offset; unsigned long *gaps = NULL; - unsigned long *pivots = ma_pivots(mte_to_node(mte), mte_node_type(mte)); + unsigned long *pivots = ma_pivots(node, mt); int i; - if (ma_is_dense(mte_node_type(mte))) { + if (ma_is_dense(mt)) { for (i = 0; i < mt_slot_count(mte); i++) { if (mas_get_slot(mas, i)) { if (gap > max_gap) @@ -7000,52 +7001,51 @@ static void mas_validate_gaps(struct ma_state *mas) goto counted; } - gaps = ma_gaps(mte_to_node(mte), mte_node_type(mte)); + gaps = ma_gaps(node, mt); for (i = 0; i < mt_slot_count(mte); i++) { - p_end = mas_logical_pivot(mas, pivots, i, mte_node_type(mte)); + p_end = mas_logical_pivot(mas, pivots, i, mt); if (!gaps) { - if (mas_get_slot(mas, i)) { - gap = 0; - goto not_empty; - } - - gap += p_end - p_start + 1; + if (!mas_get_slot(mas, i)) + gap = p_end - p_start + 1; } else { void *entry = mas_get_slot(mas, i); gap = gaps[i]; - if (!entry) { - if (gap != p_end - p_start + 1) { - pr_err("%p[%u] -> %p %lu != %lu - %lu + 1\n", - mas_mn(mas), i, - mas_get_slot(mas, i), gap, - p_end, p_start); - mt_dump(mas->tree, mt_dump_hex); - - MT_BUG_ON(mas->tree, - gap != p_end - p_start + 1); - } - } else { - if (gap > p_end - p_start + 1) { - pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", - mas_mn(mas), i, gap, p_end, p_start, - p_end - p_start + 1); - MT_BUG_ON(mas->tree, - gap > p_end - p_start + 1); - } + MT_BUG_ON(mas->tree, !entry); + + if (gap > p_end - p_start + 1) { + pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", + mas_mn(mas), i, gap, p_end, p_start, + p_end - p_start + 1); + MT_BUG_ON(mas->tree, + gap > p_end - p_start + 1); } } if (gap > max_gap) max_gap = gap; -not_empty: + p_start = p_end + 1; if (p_end >= mas->max) break; } counted: + if (mt == maple_arange_64) { + offset = ma_meta_gap(node, mt); + if (offset > mt_slots[mt]) { + pr_err("gap offset %p[%u] is invalid\n", node, offset); + MT_BUG_ON(mas->tree, 1); + } + + if (gaps[offset] != max_gap) { + pr_err("gap %p[%u] is not the largest gap %lu\n", + node, offset, max_gap); + MT_BUG_ON(mas->tree, 1); + } + } + if (mte_is_root(mte)) return; @@ -7055,10 +7055,8 @@ static void mas_validate_gaps(struct ma_state *mas) if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) { pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap); mt_dump(mas->tree, mt_dump_hex); + MT_BUG_ON(mas->tree, 1); } - - MT_BUG_ON(mas->tree, - ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap); } static void mas_validate_parent_slot(struct ma_state *mas) From patchwork Thu Jun 15 13:08:55 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13281267 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 C2876EB64DB for ; Thu, 15 Jun 2023 13:10:44 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 5F5F38E0003; Thu, 15 Jun 2023 09:10:44 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 57E266B007E; Thu, 15 Jun 2023 09:10:44 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 41FC98E0003; Thu, 15 Jun 2023 09:10:44 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 339676B007B for ; Thu, 15 Jun 2023 09:10:44 -0400 (EDT) Received: from smtpin10.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 0A092C07F3 for ; Thu, 15 Jun 2023 13:10:43 +0000 (UTC) X-FDA: 80905016808.10.EC03571 Received: from mail-pf1-f181.google.com (mail-pf1-f181.google.com [209.85.210.181]) by imf12.hostedemail.com (Postfix) with ESMTP id 0858940032 for ; Thu, 15 Jun 2023 13:10:41 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=LrTA+ywK; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf12.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.181 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1686834642; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=Bwu5nVhZqsw5mJk5ySAZ1ZJzvb1s8FXMcsj+5u++1nw=; b=A8R7Un6pZ6Syxf/8oBFIc6SkvrjtRvBgb31g9CgcluudSSzlOuz55VIKL18vZldA3pLCU7 iWu2uxmCBeRDYJNsoB/P2e3f35AjlYbOU3DqjhAiGp1CS9BeayC71pZbGiA3Cr4yyEu5io t0shTJ7fWkBZnr4rkX34c3lAwRzD+WM= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=LrTA+ywK; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf12.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.181 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686834642; a=rsa-sha256; cv=none; b=Z4zr6JPGKNnpRVBdsyTU0b3u5eYdCowJBEWBOcyy4MlZn8CQvlVxHSw+AfhgY8b0wjdo/U Vrcg4v5IEquGl5qkmpSgE7+67m/I5DywerRCjUkrnInlX4dyzPhrY8IATeFxlmdrhWrEZa LKeJlkhd46TqeBJBlQQBFIUd41KPI2w= Received: by mail-pf1-f181.google.com with SMTP id d2e1a72fcca58-6667a0811a2so1100250b3a.0 for ; Thu, 15 Jun 2023 06:10:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834641; x=1689426641; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Bwu5nVhZqsw5mJk5ySAZ1ZJzvb1s8FXMcsj+5u++1nw=; b=LrTA+ywKAk48Bks9Q4FIitMp7HeDcqRRmwSAPNDfOScb1TlK19naIDVZsu9SNJhp6G ciB+6/O0g2mQqQX1sYbvq7XQfe99l+pDofZVgNgI1ECqI/a60Da4LqfrqBLqBIZqOWfJ Qq65teJ95eepYbYMyebJySZ2X2SGYHiRzJJLO0LNbNBD5OVSG/AF2nHuunjE0XDabsfP Ulxt1D4JlWwsqIQMKZH+6ewgYdkFIXWrZeV/FWvTTvt7rie24HSlfngK1US75VQF9sYI vsHBI+uRXhuNMCQRhYA2VAwekjD63+3P+055GGksZ+oQ/yYfTrbpB76riVW5lnmnIa25 FQ4A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834641; x=1689426641; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Bwu5nVhZqsw5mJk5ySAZ1ZJzvb1s8FXMcsj+5u++1nw=; b=eS0C0EEhLyJY02Ht0UB4+XEe+srRky8mIjzKVfI0/dQMZS0PzdcIVMW3xb8V3GPhpr 3G0dov59i05fu6rTNK5mtH5obcTNyoropO1NjeBVUrsJQkpu/6iONDZT1FUDeYI2UPBB SwvO71/lyXZTH6Jcah7yJEP1o9ZIxMgPWsFoIo8tu2en6wV9zq0Xs6WCoUS9S5t75xra 665MrTGRkrCfAsned+YbGjjlXo3OhelbGDcnFVRxuwVJ7pp+631Py0asNfrAnzaxqqIq HhgXnRzR36kKHcikkaz6/66BMzRrRdnNGomWA7QqZYJ5rQ4xIRigROe31tb7HGZd42FK u6eQ== X-Gm-Message-State: AC+VfDzJnJk3O8Q2bLsjkDM+QDJF6vrdQwmC6TQgaQKzJZ4Ub31HW36W +vJV8DTo7P0yoAPbyu3Cj1qy3A== X-Google-Smtp-Source: ACHHUZ5G6bKVtrru3zNeSvvNc0GB4q9oRK4nDb5nNbnQpx/pnVkdXtJengeUj4TSq9YeSBkOwEW+kA== X-Received: by 2002:a05:6a20:7da7:b0:10b:6e18:b690 with SMTP id v39-20020a056a207da700b0010b6e18b690mr4629377pzj.32.1686834640813; Thu, 15 Jun 2023 06:10:40 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.37 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:40 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 4/8] maple_tree: fix mas_validate_child_slot() to check last missed slot Date: Thu, 15 Jun 2023 21:08:55 +0800 Message-Id: <20230615130859.21858-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 0858940032 X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: onnsy386839xzdpts5oseh6muzciwmfk X-HE-Tag: 1686834641-916532 X-HE-Meta: U2FsdGVkX19hZrzL0MI3997D0rRZXq/qre6IY0xFiiYE50FOJvpCEhsLh+3c12yDwcwWbSNTsB/jQo5ftz6jv86MHIBqaedkdcDD8aOu1yXn9hKCAkIBQEnUGwJd/7F/WzIn/YNDUAiRShiQe0rWSJoIK8X10nghbo7rN1xcmnu43MpEajTDAQxnvjF5ql4OZFFJmikawQ/cOAX27qEjDBc2ijS6LZyIYjin5fLgZez5h9kd6b6IJXL3Bncw4qymOcQWcEjKNGc4x080lnWw49Nlkifcc+9hooTPhBI5CwJPj6RVGmQBfdAxWMhCtCgtmNXncjmnaQWu7qA6mJbUg+r/vR1PYilLL3fORERNke3K5sCVUFQUF7S7BnuGpxVZC7xrJnU6RtUgntKYIPTomLluUMaqJxvROuYrTCCG+aLLs4jrNo3oG0INf7omB5ZS2QpQT4Yz5w7AhAPLMyYA6u7eoiQDPG2KI0nygDa29Z9cM3zAMco89fYcZAH4yhHh9g0mUyKWy7eY3JLsARxmkLMBhZswgbFRjLpasMqgdRYDba9Q4+Jv+fo2/veeQkGaK3RwYGZiqfAkObWHATS1RXjbatQlRgdas7YplLi38Pb19o5o0DR/IjvUjlm5BRKjvnLlxhh5Q8qR1NoHdEu5hQJp6LVLzsqXVpudyAZTjDmokuiackUYYrtvO27zhkcAgAugNqVM3d25Ea7jGELSV46BHEHYGmGSOH4rJpABatSFUTjLolA+C1Zm2xoN2pbj37pK2pYXcWw3sUPb7hqlZUyAu83URCgGrJYv2P/9iKa3sSzOFoP3L3vtB09D9wxYZfTqHbqSbMUYqfsYiNP672hI1c6sDDu+RiUGigtapJgHa4+JK8vEiIHy15PvK9HCLn5UOnJXaVL7Y6dxclWAQbFGm577K4W7NgitQtIRTkasIiHulB0YE41uUZ31tk89uekrF/i423Qbi9Jr1Fh 6uecFVUq I90o5aICJU7IDWKecV0ZUJLB/r/xcqD1Ovzm7Nf0cVNVTeaig2LWDhugjNdD5S+ICrSciJxDL1RCWCzfovaeqh+xPX7uTNt4y7aPb8mVJtz5mJzc6+qYXx+jqehlK3U51kKV0t2F0dhcPdY+sARJ7TGeXthd/2uoQMiNTjP7Kj/qW7DDxfOzbZg9on1p1TVsLW4bqPTUX2tJgHBFrnMrqq4iZ3uJUe7f4VQE5G5H/cur5vZMbj9LZqACsiSbh06aLTe4x9hJ20IPodohHk0/Ky0QS5H6Nxv8oYdgk7UaNr2X4D24JY8Dd7BHGhZYhvnCC1s5/pZXiKMfyV4hKBg+UaMG6H3N5P/3RMLodamczXhSJHOYrDIDa/YVn4MYp89NhamjNcoLXAbMfsCA1dWhYTQmXSIt9UzFLsLP95SLGJq8V1Cl+Pprw/niUdxVXlMhFOfdXuxPMZ6M+V+mFVqYfge6SUoHHbcBUjONaD8BsxdRDGr02OY/UM6AJUw== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000004, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Don't break the loop before checking the last slot. Also here check if non-leaf nodes are missing children. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 799afd590cf3..d91e66ea223f 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7107,11 +7107,12 @@ static void mas_validate_child_slot(struct ma_state *mas) for (i = 0; i < mt_slots[type]; i++) { child = mas_slot(mas, slots, i); - if (!pivots[i] || pivots[i] == mas->max) - break; - if (!child) - break; + if (!child) { + pr_err("Non-leaf node lacks child at %p[%u]\n", + mas_mn(mas), i); + MT_BUG_ON(mas->tree, 1); + } if (mte_parent_slot(child) != i) { pr_err("Slot error at %p[%u]: child %p has pslot %u\n", @@ -7126,6 +7127,9 @@ static void mas_validate_child_slot(struct ma_state *mas) mte_to_node(mas->node)); MT_BUG_ON(mas->tree, 1); } + + if (i < mt_pivots[type] && pivots[i] == mas->max) + break; } } From patchwork Thu Jun 15 13:08:56 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13281268 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 36CD4EB64DB for ; Thu, 15 Jun 2023 13:10:48 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id CABC38E0005; Thu, 15 Jun 2023 09:10:47 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id C35156B007E; Thu, 15 Jun 2023 09:10:47 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id AD6718E0005; Thu, 15 Jun 2023 09:10:47 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 9D3B06B007B for ; Thu, 15 Jun 2023 09:10:47 -0400 (EDT) Received: from smtpin23.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 6418FA0821 for ; Thu, 15 Jun 2023 13:10:47 +0000 (UTC) X-FDA: 80905016934.23.CD0EEDD Received: from mail-pl1-f180.google.com (mail-pl1-f180.google.com [209.85.214.180]) by imf10.hostedemail.com (Postfix) with ESMTP id 5AB39C0013 for ; Thu, 15 Jun 2023 13:10:45 +0000 (UTC) Authentication-Results: imf10.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=XHxv1DOD; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf10.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.180 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686834645; a=rsa-sha256; cv=none; b=KQHTrx+fYoByJlOAHDgAr2gYQKpigr9+Ke85iwzTczkQqYw9iglysSDSRXt93hhKc8nBBO +lbZZYY2zDHG//xhXMN5m3tZAuckLftnqzyYU0/Patzqf2B9MA83WA1YqvhuikzNF+Qp+Z eNCiKNlfVIKLXODWHS4UwP3FltSGOec= ARC-Authentication-Results: i=1; imf10.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=XHxv1DOD; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf10.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.180 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1686834645; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=Bi6s0yfXuBjDVA++TIrUvyqPyk4i8//b9rD0tFMY+rQ=; b=4dQnWEEqvcUG5hzIxYxJkpYyPSmkm43InVSJRGen2uy13U5lnTiFQBq2HNPDPka+TVckGf ksEtfqqb4qDAqrfROfefvrBIdtqbzNk9O1xWIY1yMfOXkJSPZn3WfrXFKu1OQ5kRSP6vP1 immvFQOYDAjNM3aniJviA9ssRZ6R+h8= Received: by mail-pl1-f180.google.com with SMTP id d9443c01a7336-1b3db8f3d94so25488845ad.1 for ; Thu, 15 Jun 2023 06:10:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834644; x=1689426644; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Bi6s0yfXuBjDVA++TIrUvyqPyk4i8//b9rD0tFMY+rQ=; b=XHxv1DODKYeQKwjzJy2jt+aDwBfZOEIQt0yctlrkqvR3AsFSf1ORSYqAly/zx/7VwZ WE5pC8UGcgZNqDWgJwiEsDt408rwNq/NyGormCqefHQz7iV/7MM+SPvUXcgj8DIwhdjM pdca/N3EZmE6EUlzP8ejwoyLpAGzBriRcJ0sZ40piq4tT04sS0ciN2/ZenkJeOM+P7Ig G51gduTFS2c7/RsbPS1J745FnYsdE+Lck2dn1qUXKvwp0gv2Tm588fL14wsSgM//puEw TH6gPvmuoROUn2NJ4SgKKQZxGmklUQUJUdHsGkpDt0dog3/OQShcgpNHl+zGO18WjK26 ebrw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834644; x=1689426644; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Bi6s0yfXuBjDVA++TIrUvyqPyk4i8//b9rD0tFMY+rQ=; b=E3Bok0qXTgc0EQLvtzji9FPgwCSpJGNJrL2MkWeJ5kUeLrpqfVHf3IUZo7PDXO94rO J9ccNMM4TOSBqOAg4gZ2YFbt5bB71Ja7wDzC6/ICLNbJlyAwh6LwbML29XcBZAHm/HqX qNdQ9lBfaxQsULVWxsyTz9VFZ4Hgvdz+mMWL432h84FkDw7GlMJ+5zeaGsZySZBjAtZ4 D/UVq+v0hw10MsuLvfga6udYma0A9Gj4Ts42Zqp1I9SlDL9rgwCtwpATpTTIKLYWmcwd a2wEoJrtiSttH9+dThQOpKtyJE/DhoKw47AcxQl0FEvTt/1UO/LlX2XWBZuyad0ZElip geSg== X-Gm-Message-State: AC+VfDxpkvB3LY7qLARO7HkMnfFRWQ6jzLIhbWX4MrB3skCi0zzcx+jg 7vMpuqM8gO5oLhIqXNpppQ/dJw== X-Google-Smtp-Source: ACHHUZ52MGd9EC/zQoRkcmWexYmu12qqZKGDLmgxc8TYFK9fADOrTtHJMU75US+EdruywsgRdY2x2A== X-Received: by 2002:a17:902:ab1b:b0:1b5:26d4:517d with SMTP id ik27-20020a170902ab1b00b001b526d4517dmr140399plb.29.1686834644205; Thu, 15 Jun 2023 06:10:44 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.41 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:43 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 5/8] maple_tree: make mas_validate_limits() check root node and node limit Date: Thu, 15 Jun 2023 21:08:56 +0800 Message-Id: <20230615130859.21858-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam06 X-Rspamd-Queue-Id: 5AB39C0013 X-Stat-Signature: ktsmioqdfwqpeyg3mfj6q15qkdsim873 X-HE-Tag: 1686834645-817568 X-HE-Meta: U2FsdGVkX192Tdj160uxLT77v2Dnf0ByahMUCMoknDQl9h8lqO5o3pwiwvTTZavCCVCB/hONVpuHw4FsdC5bhcg8mMsettd6AAXVJ0DlyMYou+hwGLMK05BVoxPB+nSxvd7WBODo74r/QP2U1E3pwrepM8nzdXuG2XJlwZH7d0iuxBQOEYzw2qWR+up4aBDGe68lKNeb0RDpszXj/X2h9iBCizE+1a8d5LLFqfOXPAp+GtpQQBwjX1Z1u6QwG+UBDAfPvnoPF0Y+PSGD7ZOl5BpYTswxxVSOLFRDzoPw4bVkPFKZWVYfbP1LQuQkF4rkVqkXLj8KjkNJ7BXmv4REFfmOVIsgq00t1ORCQLMLDT/DdfanJ0ztyAykNOWK9ylZ4ckepWjqU22ARjRWteuDharmyt03kW+HAzY2OYrcsawLnn3G6PQv28XQ2jT2+vzwGB1e2wS7TmWuzj9z3iDkOEULexEUDPwoEgT+RiZ9GKkeSU3AT/8Fp1UuN0KOQtT5NvpauOWU2mvU8+e5qg5Gj55MuOyJsArQBDFF3/YYq4nyDuBGu3bxez8YETpvWZm1fW82FKEdTXMAMVjk4/MdBmJKZAohGalIfrDWkb29V+jnrCCGsIq1u/REyJxT5L6zmKX7DJuos6Xpa+oYac9ItJIC4I1SLLPBoSRlG9sdct2yt0XAZTYXbZbpS7dMdO/WoxtvMg9a8HEsf59YGNzJa0g/APJRXKemjWeijDy4j/ajmSTWjgwPa4FGwIk0wF0fMYlDAmVUJYbtj6hgAP/Wme0uY4tcWS68GqcZHj5IaqOhL2IKJ5HES94e6tmmFwpVEyqg84NbYU9ehcnFabC+3WetbzNyX0IZTdMCFrr8+OskySnLvECx/Du4J6eiwTHV8yZcbJOtXK0L3sijhhjzz0xzRZKsBmDwekHJSYE1cROqOhXzDdJFlRFbFxT3bjH5Va8Ajk4ovb7XwxzeHqa bF3/rX8E YpZCn+13HWsNI3cYJEXQjbiw9KHn9cK9+O8I512x5/YsQW+6mCOOQvKS/2ezElk3C+u8Nl2COjjGkBHpJ709qrpHsrz15D9kpM52Iuh/SiinNy6v8ZRzG13Xexeuz0FFhAPmjeBfZjWh3JdeA0CE+rmg7mpS2yBz97Wc4iBDytN5+PhbCTy+3MHggTQPiJNv06ug+qE28O3nVauen04E7UHu/N2DkZZKwIReRcMmulIFdrO1vdyVAad2QE+7NhSUpdchR8MlEHK77gLzgSn7twB9tUhMtExeyOC+3pG4v3NPft5/yd4QzlbugNxJYPslX9gbaWeezxJXBeprLZEbjUwK8JXbPgV+2rOFu3WX4M7cEYUvbh7YQ+5gkaYmyEmdYRf+Htjnx/IEAh6WqTyNFa3klNo68YVND+TggTQB9Cap3jlc1SSh7ljZDC0FuOfSDmBMOx3eIOFVLmZQ= 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: Update mas_validate_limits() to check root node, check node limit pivot if there is enough room for it to exist and check data_end. Remove the check for child existence as it is done in mas_validate_child_slot(). Signed-off-by: Peng Zhang --- lib/maple_tree.c | 26 +++++++++++--------------- 1 file changed, 11 insertions(+), 15 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index d91e66ea223f..6c9b62e41605 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7144,26 +7144,15 @@ static void mas_validate_limits(struct ma_state *mas) void __rcu **slots = ma_slots(mte_to_node(mas->node), type); unsigned long *pivots = ma_pivots(mas_mn(mas), type); - /* all limits are fine here. */ - if (mte_is_root(mas->node)) - return; - for (i = 0; i < mt_slots[type]; i++) { unsigned long piv; piv = mas_safe_pivot(mas, pivots, i, type); - if (!piv && (i != 0)) - break; - - if (!mte_is_leaf(mas->node)) { - void *entry = mas_slot(mas, slots, i); - - if (!entry) - pr_err("%p[%u] cannot be null\n", - mas_mn(mas), i); - - MT_BUG_ON(mas->tree, !entry); + if (!piv && (i != 0)) { + pr_err("Missing node limit pivot at %p[%u]", + mas_mn(mas), i); + MAS_WARN_ON(mas, 1); } if (prev_piv > piv) { @@ -7186,6 +7175,13 @@ static void mas_validate_limits(struct ma_state *mas) if (piv == mas->max) break; } + + if (mas_data_end(mas) != i) { + pr_err("node%p: data_end %u != the last slot offset %u\n", + mas_mn(mas), mas_data_end(mas), i); + MT_BUG_ON(mas->tree, 1); + } + for (i += 1; i < mt_slots[type]; i++) { void *entry = mas_slot(mas, slots, i); From patchwork Thu Jun 15 13:08:57 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13281269 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 BD1F9EB64DB for ; Thu, 15 Jun 2023 13:10:51 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4BCA08E0006; Thu, 15 Jun 2023 09:10:51 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 4458C6B007E; Thu, 15 Jun 2023 09:10:51 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 24AA18E0006; Thu, 15 Jun 2023 09:10:51 -0400 (EDT) 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 1400C6B007B for ; Thu, 15 Jun 2023 09:10:51 -0400 (EDT) Received: from smtpin09.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id DE19BA0892 for ; Thu, 15 Jun 2023 13:10:50 +0000 (UTC) X-FDA: 80905017060.09.2DA4BD2 Received: from mail-pl1-f176.google.com (mail-pl1-f176.google.com [209.85.214.176]) by imf02.hostedemail.com (Postfix) with ESMTP id C03D680022 for ; Thu, 15 Jun 2023 13:10:48 +0000 (UTC) Authentication-Results: imf02.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=bB1QL+mm; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf02.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.176 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1686834648; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=6ZGxNZsIpnMBQhUNXCsRmhhDB1lIsi8lU2hwxHUwfjk=; b=hE0VLPah1/pyMTy2HrAIaeY+VWkfOiFsRqjOAUqTz8BSPEgc5FzOBkuxWyrs3BZ6jkrmaR FSdR8Mk/dQUgJanvAufeMGPpcTXLDESGVccW4IxoFuIZwUin+EBcx3NwJgw3d4qE7okdEP CRAKYwD+3QthSL7mPw798TuVBDm1120= ARC-Authentication-Results: i=1; imf02.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=bB1QL+mm; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf02.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.176 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686834648; a=rsa-sha256; cv=none; b=FT+r6aDiGPgoypOUiC53KE7LhDm+twuH2pC0m9//Ak9a7WeQ+DcLJSxdzmohScRC3lh2Fd ogAiwB039Fe1SPYDHe+nyCIkFDaFXWsDLZSOajVGoI2nV7FrS1ZJO7IpHTiVB/c4LfSCJF pZDpYw5C4G+3x9MNdKZKRTISwiiJj0U= Received: by mail-pl1-f176.google.com with SMTP id d9443c01a7336-1b3a6fc8067so36350625ad.3 for ; Thu, 15 Jun 2023 06:10:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834647; x=1689426647; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=6ZGxNZsIpnMBQhUNXCsRmhhDB1lIsi8lU2hwxHUwfjk=; b=bB1QL+mmf56nkMSsfv598qN2fllo5bMGUfYXT445+ukRmpKPsuk9VT0wAtXq00tXeY WeK6VnfC6+czbq/PAw1qbKx7hPjEooLS3/e1llNQeBCEMEXRS3MUgv6jIThk9gqloXRU BsnD43Jj3AIUQNECtE2YygfsbaSk9n7L1Bh6WyE0EiLSeyCxZFUvNDtPlPA0X8aPjihM RATB0sV7gU9LvQ64TF2MqqfgGgXt9z292CVR1zak0IJpJq+TIO1K7agY+R8kNbQ+AGBP eaBkO0j8yCfFJSwgITxQoJek7mvOUQ92gsgUJAtfhMEvls0y8GeNKpYUifxw40BfhDrj UAcQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834647; x=1689426647; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=6ZGxNZsIpnMBQhUNXCsRmhhDB1lIsi8lU2hwxHUwfjk=; b=iuzJqiAP0sAOYRY80mheFFXDuMF7S/luaFXQig9+GVwEiOhhlXFIOIkn658jVl77q0 1jJlJ1iw7Q4ryvuoJLHkScOEtS6Tv2e+ycadsT1G6kZZ1okoKyTy2MDl9HgF7oxHQO4J R1wIkuMcyUwmTFbsWoMpxz/nukhQ9R4YnuM4TL8HY5d310Eywh4Z2bgzqc7e/riFJcCI +XaXerUbLDgUZleZhUAcpxGqtPNkFSmYMDMO/hihAloffeUZT+ubAIhdW7za/YBlXECj vYnc4nFnyau30iDYCGIeqgYlHvelwPqBzYi/Dr+NSHRiNWUAQxXB1fXu1Lfrpf6mj+G+ KjtQ== X-Gm-Message-State: AC+VfDxlAZuy9jWuspJ354CCErCCVn6ydjiwdPdMh/TWOh8G516VgalF te5rY+Ow2AmonnT2bUGMLTLXkA== X-Google-Smtp-Source: ACHHUZ77QznaSKTOxUniU+ofsuaOVvEBwnEahJwvt9I8exZIRYa7o7wYFzGK+enMy1u1bh5l88rW+w== X-Received: by 2002:a17:902:c20d:b0:1b5:253f:d05f with SMTP id 13-20020a170902c20d00b001b5253fd05fmr279675pll.29.1686834647381; Thu, 15 Jun 2023 06:10:47 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.44 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:46 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 6/8] maple_tree: update mt_validate() Date: Thu, 15 Jun 2023 21:08:57 +0800 Message-Id: <20230615130859.21858-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Stat-Signature: xezukijd138mdbupd8coze3xc46q5ykx X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: C03D680022 X-HE-Tag: 1686834648-714063 X-HE-Meta: U2FsdGVkX1+YX9S7+DbPYiQ6Z/NCcDMfeuiXy+yTfb5EGxBJ0K6WYBpIkDpEGobukImn5phb396lZJnv351gPHPJhi4j641Ty2QGQ5ODffrm6VkQtS83h5ZcKUpgD+qVoDUutVGfa+yJCMup4MEIJbFQuQ0kWXeMHoXLgVGAxN/utqGdFdGl9Z1BCEZ66wxjgDRP70dBSFZDMgIrWkzsun1onVs1LrPGrhIJqb8SzXkhxKDeYcWMFJLZKdO/1Kly8ka14gH32b9qG2jhCZZujPO54HfNZfMPkoyfm0QtOw5/3a+I4LmB1RFGsHoh3jlssSjKZtP4+/NzdEa9Q/TDmb5iix41vdS+uHc04NzITA3b16klsNd1ewZz2t13QoRVE5kjUZCMHgffalx+CkELdaA7BfqZp9tPg7lKzzPCoq0hyqDP2E9cqLOCJsyHUbmcjNJDjBNKSm0cW9tkiYgqrKu59QRK6+Vlbp4Tn/iUOERfp211MMPj9tz0OTimUeEQt8+EbKPgKf6WF9a1Gw0qvxEFkJn9JnSpYWGvgebcZ6sFfJliyQ84jRzlYXS1A/XpBvmIbh3HexBmfEMJljrMXizd43Ibjv0HfyDduS45nEQo9ie9tiW3aXL+4gsq1bFkckf5TbeKMuWuY9vwgGwvpZzBZQk4L9uwR58jic0E3pNN4FR68v52Zss43FxqLThj8kPAx/GSSJfG3/3Tpl4w1Y4CRBggIVxSxbnV1Kbnlp15I/vVqYrbJaPXv+oEOf75qYrcG8K4Ba6bZsJH69xJJvidE1B4P7w9Vj/h2W+7sbMankPbAOaZp5vRgucaCF1cvQOsvLL2n6800sotpBYHuRHgKCMn20n/gx5pebPMOg0mNZCbc14uayP5CFYDnlAVPsLbw0KWARzCy6o6SvE9fsHPfSnUoRWzV0U9yPQu4n7nxRDLeuVitULaM/VpRAFXCKdUlxujCwPJr09B3td qGYZkamA xdkV5IS1ojzTJrsaC04rCV958hVeRJPVlMNhyvuPz2YI+d8FLhu36fTVTYqw/kERHfRDKwQQbEXC+TEetSDKQdTEWTCOwQKCqv2cO7ZzW+LJ1nLAsNyG/hri8znYx8mjuzIT0WULdDvLOTThmLHa9bY8M20EggW/uuRoOwz9vugP+H9ctA9ggjryPW1PKDGrbVZ7Ymbp/ZF1t+206opexJ6FiKvStMqpfVKjmgJwM7I30DbylIWxepirJ4/67phI+/nv3/PAArhaRdH90ZHtCiBjstSGbff2ZAzaxuSbkJ6Aj93ulgB5GbpL4V46qr2KHJ/YwBAORNl2MEOgfJMqoKryW8ArCnkEH/aCuuCugow1CedLjpu7vJjsxX5KZF6Xne1/lQHpDZPRRq9Xx5RLkcSOvtERz4qVyq+M7huvwC5PiK1TA9oclLZxBHx5c4xfmdhpqpyfKnhr/UcU= 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: Instead of using mas_first_entry() to find the leftmost leaf, use a simple loop instead. Remove an unneeded check for root node. To make the error message more accurate, check pivots first and then slots, because checking slots depend on the node limit pivot to break the loop. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 21 +++++++++++---------- 1 file changed, 11 insertions(+), 10 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6c9b62e41605..becb4c224e57 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7256,21 +7256,22 @@ void mt_validate(struct maple_tree *mt) if (!mas_searchable(&mas)) goto done; - mas_first_entry(&mas, mas_mn(&mas), ULONG_MAX, mte_node_type(mas.node)); + while (!mte_is_leaf(mas.node)) + mas_descend(&mas); + while (!mas_is_none(&mas)) { MAS_WARN_ON(&mas, mte_dead_node(mas.node)); - if (!mte_is_root(mas.node)) { - end = mas_data_end(&mas); - if (MAS_WARN_ON(&mas, - (end < mt_min_slot_count(mas.node)) && - (mas.max != ULONG_MAX))) { - pr_err("Invalid size %u of %p\n", end, - mas_mn(&mas)); - } + end = mas_data_end(&mas); + if (MAS_WARN_ON(&mas, + (end < mt_min_slot_count(mas.node)) && + (mas.max != ULONG_MAX))) { + pr_err("Invalid size %u of %p\n", end, + mas_mn(&mas)); } + mas_validate_parent_slot(&mas); - mas_validate_child_slot(&mas); mas_validate_limits(&mas); + mas_validate_child_slot(&mas); if (mt_is_alloc(mt)) mas_validate_gaps(&mas); mas_dfs_postorder(&mas, ULONG_MAX); From patchwork Thu Jun 15 13:08:58 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13281270 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 AE15DEB64DB for ; Thu, 15 Jun 2023 13:10:54 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 5330F8E0007; Thu, 15 Jun 2023 09:10:54 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 46D916B007E; Thu, 15 Jun 2023 09:10:54 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2E75E8E0007; Thu, 15 Jun 2023 09:10:54 -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 1A66C6B007B for ; Thu, 15 Jun 2023 09:10:54 -0400 (EDT) Received: from smtpin25.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id DA6A416066C for ; Thu, 15 Jun 2023 13:10:53 +0000 (UTC) X-FDA: 80905017186.25.8B082FB Received: from mail-pl1-f173.google.com (mail-pl1-f173.google.com [209.85.214.173]) by imf23.hostedemail.com (Postfix) with ESMTP id 12E7A14002D for ; Thu, 15 Jun 2023 13:10:51 +0000 (UTC) Authentication-Results: imf23.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=PnvoyOBW; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf23.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.173 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1686834652; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=rh1upVsLkWtnKrYRXZBQpn/CVX3v0vcX/4UFjQ1Vcrw=; b=QC1LUtz3zSIje/rpfKq0Iz3Ewq3bf7MccFkeuk68WL63A2w3lw0XvmM+/21wcXo+UPGikQ vP9M2musuWR2OPOucA6TS7GLCWjuT06CQRl8vN7EzK/fpcXC2w/FqbS5IKnLss1wM/LKga dHY4Hy8G9a1CYUWQ3hrL8MKcApC27tM= ARC-Authentication-Results: i=1; imf23.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=PnvoyOBW; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf23.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.173 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686834652; a=rsa-sha256; cv=none; b=2xD4SGQxrF6OqHf2L5BFkjTvudsD+g0Ds1MZGBpAJAZ8Jo9Nv977C9gajW9al2HEAooETQ IF5n3SZol2tW4D3le+EDZPfbUZXLNYupzkUSZx/3C7NFfEkKtm3gCPtgVuGHfn6mDwdbEX 4yRO01SVnNGD6WObHcf8xorrR8xLU2Q= Received: by mail-pl1-f173.google.com with SMTP id d9443c01a7336-1b3db8f3d07so25467575ad.2 for ; Thu, 15 Jun 2023 06:10:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834651; x=1689426651; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=rh1upVsLkWtnKrYRXZBQpn/CVX3v0vcX/4UFjQ1Vcrw=; b=PnvoyOBWI0174VERzdCx/bjEaYkDquh7yUGjQ50/UMkljqo5RjJXjL/cpgyU0TzpL0 eH4VXPKnzVaqjcP0gOrMx+1QHFabhbbyvY/b0lpA7NNL3TpSSbiM5VkBsMKRfz9VcWo2 lFwoUO7O78+d9CNvG3CfhEJFuWdZ8b1+UY+22FceCZ1Z5L8AhIi7hCMxeK3Nv8H36S9l rpau8waC19HwkB9lNxumaKNM/lwcYVUZc1+ee++CYY+F7cyGfZ46ler+HLrq1LcRvZAN eQsUxGjTPIwUCUuGKYO2Lmqr+uiqKzT6QsnoYFz+N2wYgGq3hiijfpQwjmPzO1Qqg6X7 no0g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834651; x=1689426651; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=rh1upVsLkWtnKrYRXZBQpn/CVX3v0vcX/4UFjQ1Vcrw=; b=c+Uc2B9IweVRsQptioHHlh2tx23wMcK7tXBciJje8ABIpKJ+8TFNaEvhwomB+sKPMV Q2CrMte1m8di52Hy8GFObM37GhQqZ1nYCHXZDeI7a6pDXa5riR69V4rTrRXJhxfs1dfB oMd5FjXbi/Fj5w0KJUdb6imkGNC5Cx+BEExqTEJFmlWINBG9AStgAzmeTpnXNRKYkcPu XRkoY7q+0zYHi6wqCuygVRoqBgCGUCpEz1Yq6biSmwTrt6WwW6j5ahgAjLdmsuPaTNrT NBlp7a6rboLl4XNsGxPx0djBjWw4RYGx8BNioo9L/UM60AC5bUvJSeRrgjPpfxIic2gO 6KaA== X-Gm-Message-State: AC+VfDyWKfRDWMHwlzxP62T86jPg7STIxD5Rc/8QWFhQEX96b3jxid9h lkWB86hLGClD1caHinCwcDX3gA== X-Google-Smtp-Source: ACHHUZ6kYlTrHFDEkqjnopSe0wt5bMIuHrwtTI/7vuPr5aH9vc14N6FGbaSoQP1LNTuYXmE9OOVpYg== X-Received: by 2002:a17:902:7042:b0:1af:fd3a:2b7d with SMTP id h2-20020a170902704200b001affd3a2b7dmr12733721plt.48.1686834650878; Thu, 15 Jun 2023 06:10:50 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.47 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:50 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 7/8] maple_tree: replace mas_logical_pivot() with mas_safe_pivot() Date: Thu, 15 Jun 2023 21:08:58 +0800 Message-Id: <20230615130859.21858-8-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 12E7A14002D X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: cto9cn8n95muhqjbtqfmfwe49o1jue5i X-HE-Tag: 1686834651-779381 X-HE-Meta: U2FsdGVkX1/qNe41uZDCx8YYuIqpu3ztAZob47sJ1u1ziTWN8WLscr6J1hl/OE/BJ56L8ws8uaSQmy2th8zyHr/PoyR8ubWDATUAzflJUEBQLQrlKKc+F/l6fOY7FwuDlAl9A+xqpIxXD/u6WAgsJjfvSvba+PLku+SZK2FoE11zc/aHKxEm8xcu+QJsLccf5CJ0fOHL6Hm7khyn60rKLGf+sLyYp7Kjw1s8Zg1Ft5p529fRePVzz9om3S1Fr/jo/1QQNh+ZXjh9QKr3Mc/vbvI/+j26EdnlrUyprr+tSxhvbe3nkrCrNcY6yEPLexgI2sb13jqNimtn3zCD8xSLsoVIdFIi8L75js4PY5wrja3+J3tBs34RevZRqTyKouWQZYY4/ONJw5pFXrS8tPq70/G0gjpPByFySnrUZiDlhMqRBCix7eLwtUYiWq4fjK6KOwpc4J1PZAdwxB6Qx09CCqKHQdDu+K+JcXKeYsqO/jVL0vrgatn9+7P1+IAYOkvnvEDSx/1UmJSdoVQuLJ5C83+nsc+uGWxRaBM4PjOg1ZLMEMMnn9/u7wfuX1l1zvp3SgaP9bgBU9tw6L3R5sy7WIMEbfanCYLowFtdcB7bR7asQwAl+eAPxfZXPT5MK5fGFELT82yUSqKVXIHkOgqHDLSx5J8sZVA6RiWllCWxRLfNOjIPEf+8Qi0lhkK0G+yKnN2hRfsJTrdUPJiRhybyw19BjLmbcRR0s4tMNY+32ylQ/1CwL3km8wlD1SVQzKwUMUqFavWyWe5fwUKXq7JAtZafmrBeVWKKP1zDBDNrqRiqB1Dk4jAZuHD7lNC1DjOKX2u93Vv4r+I+A3yILiLyZ7vOVaw471/+rDP8NUQ8EMyr8P/JUWRjVxv0gPCKNIeGd5dYxKHCtFheVmK4JghaTSNZ8TzurrlQogrmtova7qW2sB7A7QbcntAkPgs0wOdydP8FrpLc14+WXfYj4OP CAOeXVGN ghVf/Z92VZ634A5TwC02uopsdP9lbkEsZIvMFjyLb/sNVg2hCBKki4oKZcao0qmsIbPYH7tPwag489MCxfuMEAM5l0AG6mED5ChK29J6UvAHzMQ246GLrmAiTFgkHa0ekkUq09ZSHBiEA/l4pUuf54De2A64g49ImOJsLEDaYfMs/x9vcNLsbQrg4Cb4y3Pie5KUW5nHp6PcUkjG2+hin00LvGvnKtiFmfbArbm2seQiqrp7sXVVUAw9QW9QPVV9tt54YVrQylOan8U5+aJcMijaDSRHSld7G4hye3QvDKtK2sSP8Nq5RkVGBrWYNSr8ysB19ajrcPGEAvZyoLmMFDNKe/W+QsCkCttxSW+a2OLUgiLa0RWenvjLGWW3Fe9iYlrP2EE3IH68V0dh+YYPFMpw1rqre9yBkRn3rqQbMyX7m75XdTTZUpR0rSkdwF+lpKSX1LzxumWzlZog= 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: Replace mas_logical_pivot() with mas_safe_pivot() and drop mas_logical_pivot() since it won't be used anymore. We can do this since now all nodes will have node limit pivot (if it is not full node). Signed-off-by: Peng Zhang --- lib/maple_tree.c | 33 +++------------------------------ 1 file changed, 3 insertions(+), 30 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index becb4c224e57..4c9f40322f5f 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -728,33 +728,6 @@ mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset) return mas->min; } -/* - * mas_logical_pivot() - Get the logical pivot of a given offset. - * @mas: The maple state - * @pivots: The pointer to the maple node pivots - * @offset: The offset into the pivot array - * @type: The maple node type - * - * When there is no value at a pivot (beyond the end of the data), then the - * pivot is actually @mas->max. - * - * Return: the logical pivot of a given @offset. - */ -static inline unsigned long -mas_logical_pivot(struct ma_state *mas, unsigned long *pivots, - unsigned char offset, enum maple_type type) -{ - unsigned long lpiv = mas_safe_pivot(mas, pivots, offset, type); - - if (likely(lpiv)) - return lpiv; - - if (likely(offset)) - return mas->max; - - return lpiv; -} - /* * mte_set_pivot() - Set a pivot to a value in an encoded maple node. * @mn: The encoded maple node @@ -2202,7 +2175,7 @@ static noinline_for_kasan void mas_store_b_node(struct ma_wr_state *wr_mas, goto b_end; /* Handle new range ending before old range ends */ - piv = mas_logical_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type); + piv = mas_safe_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type); if (piv > mas->last) { if (piv == ULONG_MAX) mas_bulk_rebalance(mas, b_node->b_end, wr_mas->type); @@ -4911,7 +4884,7 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size) min = mas_safe_min(mas, pivots, offset); data_end = ma_data_end(node, type, pivots, mas->max); for (; offset <= data_end; offset++) { - pivot = mas_logical_pivot(mas, pivots, offset, type); + pivot = mas_safe_pivot(mas, pivots, offset, type); /* Not within lower bounds */ if (mas->index > pivot) @@ -7003,7 +6976,7 @@ static void mas_validate_gaps(struct ma_state *mas) gaps = ma_gaps(node, mt); for (i = 0; i < mt_slot_count(mte); i++) { - p_end = mas_logical_pivot(mas, pivots, i, mt); + p_end = mas_safe_pivot(mas, pivots, i, mt); if (!gaps) { if (!mas_get_slot(mas, i)) From patchwork Thu Jun 15 13:08:59 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13281271 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 60768EB64DB for ; Thu, 15 Jun 2023 13:11:01 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A3B096B007B; Thu, 15 Jun 2023 09:11:00 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 9C45D8E0009; Thu, 15 Jun 2023 09:11:00 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 83D958E0008; Thu, 15 Jun 2023 09:11:00 -0400 (EDT) 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 754276B007B for ; Thu, 15 Jun 2023 09:11:00 -0400 (EDT) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 55839120850 for ; Thu, 15 Jun 2023 13:11:00 +0000 (UTC) X-FDA: 80905017480.19.FB727AC Received: from mail-pf1-f170.google.com (mail-pf1-f170.google.com [209.85.210.170]) by imf22.hostedemail.com (Postfix) with ESMTP id 393D1C0021 for ; Thu, 15 Jun 2023 13:10:56 +0000 (UTC) Authentication-Results: imf22.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=EF9Lkit8; spf=pass (imf22.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.170 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686834657; a=rsa-sha256; cv=none; b=YQOcsBNY3Cb09LW/iIgX73QzM5UZJesSzP60ZXGDHcVVBXPFQH+OMAqCBM6WXoGMo2d7rr Cc1JeUUKbOdA2J/UtaYW954XCe5Y2l+7HMMrNOKibtXQ5seA9l4FDwF1WGcIctFL8bbgPd T9dx2x928V3U7IWQTSLGEHKPrheYPb4= ARC-Authentication-Results: i=1; imf22.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=EF9Lkit8; spf=pass (imf22.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.170 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1686834657; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=CEErg3d4yT8esB8KpwjYxwMfJsf51/geZ+6n58UDGJs=; b=MGTQiKDDBuzALgph7tHKzBwiBeQAcBJzxi5lS89NcMfGgRJOaDC5Rr/DgBhAIHGnz7BjhT yWhZ7pJgNJzXh+DwAjnWP9mNBDF5a1NoOuS7QxXJ7WlpQb+lWVQdxM/ArSquPT2FXIuDSN t0DznFLrTuez/DkwbiMI5JddrvOOnYc= Received: by mail-pf1-f170.google.com with SMTP id d2e1a72fcca58-6667defb5a3so1240436b3a.3 for ; Thu, 15 Jun 2023 06:10:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834656; x=1689426656; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=CEErg3d4yT8esB8KpwjYxwMfJsf51/geZ+6n58UDGJs=; b=EF9Lkit8KeZA+6lEZX30z4AtzxQeXjXaFk3VG1hfh2/OEXDrTUs+QkddvuqbwKFGw5 NNqqQL7MJRL8o5afvaoXGXt4M2Y5EUJhZvfO8yDoT8KKFGuNv4uRv4JQKKveXRRez2CH cpC9z+LFWjAtvwcmvfv1o236zgBYalBIf6twvsjmnqLecvTIgrQrJMwXOCE6tXnTXFMn ctm9NYACNGn6WIX2bZXp0PHMVPzmFZkGkETZdQjMNpURRfxtWpaAKdqsjVwGkcyG/1Et nnhuWEUU1xw2Jry13IAXUIyr1+L4D2uCbd0+m403S9gXx0X5hRfXAZ2XQQ4MIGqEJL4k 3rtg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834656; x=1689426656; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=CEErg3d4yT8esB8KpwjYxwMfJsf51/geZ+6n58UDGJs=; b=J8ByFOfEnRdqbFKTDslImYBhsy4ve7aQMCUBz3ezRQjWvQ7kp6ukBhwd4LBs3RTR++ jiSxWhgY3mKgAqxyxWMKmbL23hxB4j1OneA+rBNYUINHOhL7fZV7iyl5NMepGJsXRVI9 pM+jY9Q2emN9djiixxdMyhFqSzTZqIUteZbJF2dtg7l8wMh4ITvPqhDU1jIy5pI44XtO tIHknFAcj4FloP/H4bhqeJKQUrZ4R5lfKD80X50/YGxrehT3etK98xVZli17timppJh9 +/EvdPCyxiBOT35XG9zbjlpvMfAmyeFFu5q/8UHMIAYe9xG2RP5I3a2vgQWTqLUVjOhl y23g== X-Gm-Message-State: AC+VfDxGmOTKjuMEVKJAGaqGT/9QdjsG0wIHWQc9uUTWDoSo539MS88/ k0VuJgYhHQC2eJgshuZpUA3cdQ== X-Google-Smtp-Source: ACHHUZ66o8V5eliveHpTDDCN4qg3tEA6UrvtjbBXn2YuCrBWuT9CqkfigWT9RVAiW4pUBar41PkAow== X-Received: by 2002:a05:6a20:72ac:b0:10c:2349:459d with SMTP id o44-20020a056a2072ac00b0010c2349459dmr5255910pzk.11.1686834656065; Thu, 15 Jun 2023 06:10:56 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.51 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:54 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 8/8] maple_tree: drop mas_first_entry() Date: Thu, 15 Jun 2023 21:08:59 +0800 Message-Id: <20230615130859.21858-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 393D1C0021 X-Stat-Signature: u9iy5teqkd89z55fcid6n4anfnm3iu6s X-Rspam-User: X-HE-Tag: 1686834656-846801 X-HE-Meta: U2FsdGVkX19T4AwlxxVB+V+AcLo9pD5AVS3eI8ev4dCFLalU+63+RhFXMheQYRooXigT8uB67ZYsi9q9LpYigRRJ9DAhwk6/3P3hMJ66H6ZlgdvQLqTyD3/OC6V3mu1S8kE8ZJqnuN2sdA9dyWB2HCgIgSZBEHO4bT0CgCEQbc+WwgkGqg9MDP9iqmTFsQ/sBlcd1zInTZliy5HrQPWM6evWX/SP92+8adj2Y+nMO34QqEDJ1FqDWp3QZCKu+JiZu4pkzbncNXE4JPHH1K8Qjy/cc8hoSo43zlHhj3yJCAequFr/1EFZfus85FafBMukDmslYxPmKj51slNpfSoT5VGeiedBxQ4FWAwRGc0ElrD3ykRktvZ9glAMNCnbJ1F+b+XmwBvsvfy+YKc3i9QgrlPAJ3OVwpWdxY6V97P53n+ps++a3Xrp2iZUGOSYQh2HhumVXEL16PDYkK8VcnqtGftU1LI5KS6ClZXvYz2pTo7lJLIXX1PcBpfHfckdOqjTf0wys8CpG37upIEFkzEIuRIrW0OIL5lOfEwI2wAwdiUCENBFGxa3BwFugn4aim7DejFgycfHOnUJiL5CWEGaC+Fq4fgmeaVJ2w+Ssr7f1PHxzIStO4MNA0UvIXy8Z6apSWMNa97a+DucLsLNvrbCoY5fkGju2bQLcIOUkb3NGlI789PUJHRXi0coxWWnsrhF+hBefv1AT4iOx0fpJE0+mLMMqOycZ5gas3tStSOBjBbC8P0dh5A8bW+jFAfrHpzFJFWUOsuD/cuUpWA2XXM/FkGTVkxmLvJ+/YqM/AbfKxy7u4sjFpO+gJVSWkmJmzT6P324KD/aWnKlV2t/e2kVcBvRr79cB9CFko+Rka7dZTASUqS76n6H7v4WQaB+k66m5gw8teoUaMfJZWjJwj3MAD1O5Haz53VqwYlqp/jMsjc4TSTMbCtiYbUPhR9eiZxYrCS9WSN/AC8obXdy3A/ j8wc9svS M682Suvq67/nKE/MManWGF8Tk8RUTldilUTvsIoOkLt3DfULtr8YNa/6KYTb8jeFzCaymjGSqxJ/wbY07p3tXu8nvmD6/nZ1PZUFaB3J9dhJQBZZ3Fh+la7+C7/3S9PAfBhWiNY4xXq6AzItQTLo8Uy+H2hnTs8c3bsAxo7t4F4UB97LNYqjGvJR0XTzShpV8/5oIdreLsjy1n4R9u3yUa3eoHSbe2XmJ69U+ekbm+uegCCxLyGY7lU/aOdT9ajlHv09pQhbgTaqs8L4C0mUR5EKmqqNNI4Vd4PEdkRIfZN0klMHU/2knMuB2fee/WfQR6oTHt6J1RMMD4xHCeEMLFKL7pmoJMpMWTKNWFC9OemCQb4v7Bnr9Ziq8j1U82414RtTmapX5oxin9SNhtSN/CRLnB4dntVXX20Hc7nZuxBzOZvDPeyRzILf8HUxluIyFWr2i54bvIUDaSqE= 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: The internal function mas_first_entry() is no longer used, so drop it. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 72 ------------------------------------------------ 1 file changed, 72 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 4c9f40322f5f..3908a3937214 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6658,78 +6658,6 @@ static inline struct maple_enode *mas_get_slot(struct ma_state *mas, offset); } - -/* - * mas_first_entry() - Go the first leaf and find the first entry. - * @mas: the maple state. - * @limit: the maximum index to check. - * @*r_start: Pointer to set to the range start. - * - * Sets mas->offset to the offset of the entry, r_start to the range minimum. - * - * Return: The first entry or MAS_NONE. - */ -static inline void *mas_first_entry(struct ma_state *mas, struct maple_node *mn, - unsigned long limit, enum maple_type mt) - -{ - unsigned long max; - unsigned long *pivots; - void __rcu **slots; - void *entry = NULL; - - mas->index = mas->min; - if (mas->index > limit) - goto none; - - max = mas->max; - mas->offset = 0; - while (likely(!ma_is_leaf(mt))) { - MAS_WARN_ON(mas, mte_dead_node(mas->node)); - slots = ma_slots(mn, mt); - entry = mas_slot(mas, slots, 0); - pivots = ma_pivots(mn, mt); - if (unlikely(ma_dead_node(mn))) - return NULL; - max = pivots[0]; - mas->node = entry; - mn = mas_mn(mas); - mt = mte_node_type(mas->node); - } - MAS_WARN_ON(mas, mte_dead_node(mas->node)); - - mas->max = max; - slots = ma_slots(mn, mt); - entry = mas_slot(mas, slots, 0); - if (unlikely(ma_dead_node(mn))) - return NULL; - - /* Slot 0 or 1 must be set */ - if (mas->index > limit) - goto none; - - if (likely(entry)) - return entry; - - mas->offset = 1; - entry = mas_slot(mas, slots, 1); - pivots = ma_pivots(mn, mt); - if (unlikely(ma_dead_node(mn))) - return NULL; - - mas->index = pivots[0] + 1; - if (mas->index > limit) - goto none; - - if (likely(entry)) - return entry; - -none: - if (likely(!ma_dead_node(mn))) - mas->node = MAS_NONE; - return NULL; -} - /* Depth first search, post-order */ static void mas_dfs_postorder(struct ma_state *mas, unsigned long max) {