From patchwork Tue Jul 11 03:54:37 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13308092 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 BFFA5EB64DD for ; Tue, 11 Jul 2023 03:55:06 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 2205F8D0001; Mon, 10 Jul 2023 23:55:06 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 1D1FD8E0002; Mon, 10 Jul 2023 23:55:06 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 072C98D0002; Mon, 10 Jul 2023 23:55:05 -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 EA0808D0001 for ; Mon, 10 Jul 2023 23:55:05 -0400 (EDT) Received: from smtpin09.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id AFBE51402F4 for ; Tue, 11 Jul 2023 03:55:05 +0000 (UTC) X-FDA: 80997965370.09.0A25A81 Received: from mail-oo1-f45.google.com (mail-oo1-f45.google.com [209.85.161.45]) by imf30.hostedemail.com (Postfix) with ESMTP id DACB880003 for ; Tue, 11 Jul 2023 03:55:02 +0000 (UTC) Authentication-Results: imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Z4IrWlz1; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.161.45 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=1689047702; 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=vnneOZGmz+RJtivDvKZ74LFhvf3KlKhvaFlPPXT7kZI=; b=YOsMQyvql2k1rjhJWp+Noj2RrMg/uEzMgHqBPNki4GEq/Rab+DMOjQaRaWZCL0qRYAkBEl kBb3nmU4/lhHbVk6G73nr0kxt4dGCkMFX2LBvJSLOhnnrm34l+iCo8xf1q7wyxudrO6rLu AcUgyipuoC8QGQ6JjdJjwgz9N1Vf/0s= ARC-Authentication-Results: i=1; imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Z4IrWlz1; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.161.45 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1689047702; a=rsa-sha256; cv=none; b=xpzKPCyGH1nR3OonDuvvmHP5se8Iz3RogIAzpT40BImjbjbgMqUq9NC8rm2lkjwgKMk460 HFA+t49gZAn6zSTl8WAzKX/PA0xFdhA6djP0D84QRyZxmvGEls7Nb9cw5T3YGURu6DZkl2 kEUgePcJPyYFTVxZvVOWLihAvr8h+wU= Received: by mail-oo1-f45.google.com with SMTP id 006d021491bc7-56344354e2cso3732206eaf.1 for ; Mon, 10 Jul 2023 20:55:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047702; x=1691639702; 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=vnneOZGmz+RJtivDvKZ74LFhvf3KlKhvaFlPPXT7kZI=; b=Z4IrWlz1AVjCsHQerCU8etu0x4fMRgmj78dqWxOaEVokcj5JlvJ48wbsN1nYAt8aCx GyIG4fljUcmd36IPAIMorw1pVL0WKa1lCiJxTeiR8S2f1WdwstlfNNXOLV/lPYXe6w1h DVjrFkjamSlpBL0rycqTgq+TECck80TZzdXkKOcfQH4QVOG0MGoHytPkEiIPLoB+jvOb bIEAdvF5OtUo3o2laMkrVhKHijhKrDznzeOUJ0gGzpAgJ1tYhDAcKvPIU5b6T4kPx4Gg OKUPDT72H3ElLV4oau0mU8I3UjQjAbd0NEcN69RmvH/J8FLOzK114dRUY492oyqnmudr BFgA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047702; x=1691639702; 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=vnneOZGmz+RJtivDvKZ74LFhvf3KlKhvaFlPPXT7kZI=; b=Q5+0qixoTk3irA4wiCtVU87/3FkvQ2SS4mjRbEB+1RYhFUusYYhfQ4zRXJ2adzCQT4 YoUmjHq5CNbHU7bCoM5VBepvTsS9ApZt+BAG3YuU9cASRcCyjBZ6fq0KzrZ9bWbZux8w u2hfmS6IS54KgbeNFYmfeKFo/ITA9c9JYk3B67tAH6c4NpMxwQ7N16z3Solpkg8dpqlp fQSxiUrT0O51KDqcGT+VDR+r7WzDJKeqlZK6N8GaaqStaBp9mlu6By5zurxLi8STWX3i rU/F0wkiGI+xvi4kqsKCAGdpebMvW2d43jvZtD48GUkkW0WVTMsbOP0kvtHr1Z9VqDlS /VYQ== X-Gm-Message-State: ABy/qLbLWEpQwLSlGbMUAY8L/B/Eihg5R/vNYtoi6KJ2UAvVOoeRAzhh D30r5SRBmQNzVzKoVlySd2xZww== X-Google-Smtp-Source: APBJJlEIEZOJHFzFjqHdn5Rtin4l+6JxK3vqqJKAQWR7goZOnHNKOij7NoyuIfZwPg9ro0YTA3YksA== X-Received: by 2002:a05:6358:5e02:b0:134:c8ee:e451 with SMTP id q2-20020a0563585e0200b00134c8eee451mr10966324rwn.13.1689047701778; Mon, 10 Jul 2023 20:55:01 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.54.58 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:01 -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 , stable@vger.kernel.org, Geert Uytterhoeven Subject: [PATCH v2 1/8] maple_tree: set the node limit when creating a new root node Date: Tue, 11 Jul 2023 11:54:37 +0800 Message-Id: <20230711035444.526-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Stat-Signature: hiabihwkdwkyd1npgc1box53ojgnuteu X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: DACB880003 X-HE-Tag: 1689047702-558877 X-HE-Meta: U2FsdGVkX1/AYTsqycppSu9b7xsitTMkQEHnLlZ56ZS9p8Pp8K4nQRfbRavn8fvGCACMmw7XzbrqjerpVJePxmIPEcPVI+22nR4D56wQQ0lB0iQw++SNoSGqXToe7bsT8NWCtL72F9/Yv0HIcCbLtxWUoI0KRXaoM9nLqx0+d1F+7psnsrqnUl9gNbD4zHonsYGSNd1flP/aRIuGuV8eLE/ZhIESL7kSLfyj/dBy11UNlZmTyA94iZqU0fKCXHYt4M3Zy8rITJ6aDRCH7wCWo/Pw5W/Pjy25zZkyEhb8/rXBrzFOPwAFmU67/eAAA18TDEP9rOYc7cqILerFyBbxhXxO56tfRM1Tzb41bl3ZmOd45lPNnDz2PJ7JXG2R1hsYFPISIc+shSMoPgo6cm4LnKzF7PoGHcabmTdi4wsf6ApAO8wKp7YignJAowvXjsrvuM8yImFtMMLhpDqiSwIB/LaAztkhH0AlOdYuCs+Uk0NJR14DNAgTU2riyfjQep5nbhira2GZi5ptF4V66WtQ9MRo7oMycBnTtX0gesPhg/yV/wm5AUMvj1EpgFnVPFn30IKanxtLav/Pjecgull53lUgIUKJVyIbp6JvGTJbBE1e+m+HUWKm40yyeL1KeE5cXWGIylGGEdM5jjpd8NY7NcdwyO27HNMsLvdHuWtzV4fVr0vkrtdGxr5QT6USEXuAaujCu6Vdw1Mk7ov5XDqVDEzOtZIUTciM2OWMI3/s/S3NGbE2QhfCQlSizk6TvdNm91B19aOiqMh+Sa9g4xS6O3SeInfSqNVOKs6FTR39mXERXTGblgP9KwdsnWGMYhGhNdO9LoqjOVA3JITlbeCfSgIrMaEtUYJHiJZYUQFq3LvAdmi00Lq/WmEsLZsDV346+AFOE7vpWdBDt+AI1vmLRXm5rvPa1Asg6MyZKpYZ0LXaeMXMrCxrU3LdVU/YWxmjk5k5Dh2AJSNd2eJHdw+ M9Zqz6A3 W8BkyS9mNI6Cia2hFWrBFQtqNde6rr+uboELHv31dqNs63VuNH9YP1WlJ7NmvhXUWUKox6bGqpPwhu5siwbvKCdLDRB41zpP6qDDKZrVVTXvPxcq9JnIbDOs9knEe9tNJUMaI0JBVC5snjQVZatKqNNAP32S32VndBPO+JgdWdaxXE9tHGeon4+l9qXB2Y9YOhae3CKdrFb+kLRd6EgIQJXSLS/0mgoIK2PG3WDLiuYreHU6bNZb5RcXlSfQ/x+gq6nDbh0pcr90D8ZFUx1gcfi4mSixOOeOrwJNh30Y2/RJBtEPpbeLm/Qd+tV2p8k22PsQxjtvs6uc2sheOc14wl3yc3+GRvg6WXivh0ivpyz4WOMc2RgiPjXtBd+gjk3DLbM4Lkh4Twfx4G/cyrhcAr0la1ehmGOFYbi5KibzPVe0ML0MLmK7N32YNNJ7NrZVC5/gv4srlbCdJCTMhj5tHvUGCEo/DSaUAQCHYlvrbVUD/oeQjG65EBDttLeHUYtcA9eOpoqtXtmTRSB2Ke4YBW4u/qScIlnC6ip79qCz+S8DJuqPg1S8uqKo6xK29h0hRxzs6lGwoMX8SgyzzRyum6wteYq+sIFHrqLFu/le5EeuE63HYVBfaffO/4A== 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). This patch also fixes a bug in mas_rev_awalk(). Effectively, always setting a maximum makes mas_logical_pivot() behave as mas_safe_pivot(). Without this fix, it is possible that very small tasks would fail to find the correct gap. Although this has not been observed with real tasks, it has been reported to happen in m68k nommu running the maple tree tests. Link: https://lore.kernel.org/linux-mm/CAMuHMdV4T53fOw7VPoBgPR7fP6RYqf=CBhD_y_vOg53zZX_DnA@mail.gmail.com/ Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett Cc: Cc: Geert Uytterhoeven --- 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 d3072858c280..f55e59bd9122 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 Tue Jul 11 03:54:38 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13308093 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 B9A68EB64DC for ; Tue, 11 Jul 2023 03:55:08 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 2E4018E0003; Mon, 10 Jul 2023 23:55:08 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 294468E0002; Mon, 10 Jul 2023 23:55:08 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 15BA18E0003; Mon, 10 Jul 2023 23:55:08 -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 09D978E0002 for ; Mon, 10 Jul 2023 23:55:08 -0400 (EDT) Received: from smtpin21.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id D20BAA02F2 for ; Tue, 11 Jul 2023 03:55:07 +0000 (UTC) X-FDA: 80997965454.21.9AC025D Received: from mail-pg1-f178.google.com (mail-pg1-f178.google.com [209.85.215.178]) by imf30.hostedemail.com (Postfix) with ESMTP id EF96B80003 for ; Tue, 11 Jul 2023 03:55:05 +0000 (UTC) Authentication-Results: imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Rxbx43is; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.178 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=1689047706; 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=fTNORhAMfZiekvn/WZoJTK6LhdTh4U3lAjASoHlporQ=; b=e0lPlnJqvQ7u2Ra9JEbBcHHFxI8SGB0XrqQ5T/tlary/g+yW4IWO/i87nQuc8ikykeQD/P hANX2+FzBngHTq/sXsqEqLVtaKcfLHk3uXsp0jSntWgMSWTwlIFSlYMW3eBMzs0xxwkFKr NfFTBVGFrpndkfWSByT5/4Lm/tJuhNs= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1689047706; a=rsa-sha256; cv=none; b=vigFRuWsdfaWCG2ak6yzJfvcl+kyIuntrGadMfhQ+zeJM5t6ujWNlCfqHXasDdxhIr583g n9v6hDR7XXlCyKoi0NcIX8Pu7Y0mIA5GtiFdzZRysYf1jwtsk+Q46vXTOagoNKzCc3WcsT PC09aMdmPdr/HhQbVJA6g1LJwkcM3eo= ARC-Authentication-Results: i=1; imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Rxbx43is; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.178 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pg1-f178.google.com with SMTP id 41be03b00d2f7-5577900c06bso3990743a12.2 for ; Mon, 10 Jul 2023 20:55:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047704; x=1691639704; 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=fTNORhAMfZiekvn/WZoJTK6LhdTh4U3lAjASoHlporQ=; b=Rxbx43isig3S+GFU16br5sALnoQtHUSEfGe8cb+ol6pqYx3UiUAaexdoL7DR65ZV81 3BODyot5ZjoWbtgXrORsNGEWWtJ8jdaf2v8QLo99182QN4+QD5t7R2T05RsHZ+/W79Zv TwWyCEEUja+pliatca1lfjHTT5nZ6/CwqIIW8MyHzRJ/10vt2Kw7wPEfjwzbDzjkbW8L oRk3casJ7rRn20xOrC09xX6p1x+1YVSWI1WJNd8e+wU6yNu5GRbwhqi7LWhFFPDyuAWz +6A0BSCS9J/6Mu2Ku/InixWET9G+pAzYMPbE3oiCwyI7VkhzmRHkrRpGcj64xjJvPZ0Q BbmQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047704; x=1691639704; 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=fTNORhAMfZiekvn/WZoJTK6LhdTh4U3lAjASoHlporQ=; b=GUgry8NFE2+K01kTB1OvEWEaqlZtMbxI8MdjMiXlMHta4rhHvSvoD/O2E4dW8GliqM R7KRJqOvLkuRuccjPfL5qYVX/fPb6YwchCgWxaDIwMc7uyhVLyM4mlM/12tQDfeGEvo8 bIMLorl1ETVVIzjPhuOtJVN0Gy96p0X8i0XnrKUPV9snAt0JJVBRiXE6AB/6B3pJrNuJ OI2dUruS73FIU6eEbwq/be+p7gBO5iOcnYGBJ2XGIvZbf2rs61Zq4ZcamD7d/EBmkJnY 5k8ANpM6uRIxTOMdXzYzDdg6PtPzhql1u52jYt+FEBMzfQBLq+0Fh5isrIoNE3FpJkHo 0/TQ== X-Gm-Message-State: ABy/qLaSiJG/4BS+WxBRf5ORJXznyW4Jei6kDbpKbtWzQOBpZ7x0xpeL tXFzedTrZU0apZqEF31Leh7KkMgpEHFpbJDxxp8= X-Google-Smtp-Source: APBJJlHl4mfJ9Y+/M0jhzcC8s4QeCj9XHWKUmY872oNAImgfWhir2FpEPfZ6WWSLjO/pMZSofQvtWA== X-Received: by 2002:a17:903:26d3:b0:1b8:a88c:4dc6 with SMTP id jg19-20020a17090326d300b001b8a88c4dc6mr14392136plb.45.1689047704708; Mon, 10 Jul 2023 20:55:04 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.02 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:04 -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 v2 2/8] maple_tree: don't use MAPLE_ARANGE64_META_MAX to indicate no gap Date: Tue, 11 Jul 2023 11:54:38 +0800 Message-Id: <20230711035444.526-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Stat-Signature: jkab367yzxg8jgk34y99jw6ia5qy6g38 X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: EF96B80003 X-Rspam-User: X-HE-Tag: 1689047705-80420 X-HE-Meta: U2FsdGVkX1/C38uuS9MfSS7nmG8Ysp2aV5ywakFdtk/tY8JOqRkT8/AQUI7HEXwzh9zHwdrI/u5GTVwIV4bqwRQkJLSLJEQOt/QXOXvaPiFYbQHgcZHgDVTVJAkaLoysqkwDq9k+Py9Xpml5ltr0V93/bNHj/ZI2S6B3a1jq2QRbgNHKNfZjWizYbXIwvgBiaMLKgOVgrk0IxQq3uViBKIyiLWK2IIX5R83G09tsxlC625xIU0Dc429cqJR+AGqHi7EH3VonD/BOmx937XthX/3S4uG/ha/+4c8fILS6SwykTFTXr651PJFpwpbNSVya9rpX3w52Uw4QbAn+MfQCq5TZhUXSUk1ykGQq634VNUruCyksTfuIrPoRkVrxrnMIS31skMvCvYwUacyOXLvE87843tgtTXsxTUJ2Ou0ylTIRqCfa/NTj8cA9Jav1RUwWSPs5nUuoqcKq/6xPWUhuIyn3rI7QeDyfW1FnTawssIkFLnj1fJK2lnwNaKwN1KqW/nX+fX4PhxU6McP3p/LMcm0YG0r7DqGfWuu/Z28lGBgyGkwFg59Flwym4CZhRwTch0swQI97kCQ4mGdwXi/NeBn+tnKIE5Q11LPc1fKc9YMXeAh0sS2MOmZMnO5ytJeWF9lJq0TT3oBxapm8dzQJ/cwNnntWfXy0GlzqHr4DvEF5JIuW4E841a0BcVY4+4WV0qBl2pW8bF3kGylE5Tkc6S69ClBB3KD3rh4k0VkgUquTowDdG6oAbDtcAzmc+12afoabA4HEJ+vKkT5tgKldlk57mDsqCwE+NnJ+qau9LcydEwBTYv5jkl/RyKub6PCMjm+WkpCDvU00igYAMKUsW5+o2N/xhK9JbxV85SULyLYcGK0p6gftWBMvtm3QPgUq7XTAR2394yDmnx0tgxHgPObOp6pmKEQGz+jIMd4zMrjTncUixWzgCEgZcM/iYIalDptia4AAbKTXbZQrTbF 4AbFvJnS uKTfScIzfQbjR1Uu6ZlyRTmm+aR6hlCaszXTrfBzRzAfib2plWQTFvXbRVENkuBxqLBmVXah9FeTy9kTJhvODKKjYJBAAsql6pWQzmX63GXGRUsrUgi1162rWK1IG394y5Ilr/OAbjXTIcfnIb03yqgaOOM2avOcg5APlIHRyrk+7X+PMqjdhe0zWPHtNW1gNfmPPAk6XEXN64BSZ/W8VqJRvsfev4TyMaHGQq7/3TQuxKa7TtguhEkHk9G+EdS2UsROo62I0G0FMsg7zrR8FNzKgRO40CtOPrxQYrxQLusFNqfPm3A0+0KGQHvShGzThmYO/J33WdKfwOvENxxioDwGRUWB/22H+RLh5lKZR5z2NZhT8+/6AyumeA8qjnpPig8Ed6QiF1/jx+uYZU22h4evCyvG53JVqBKA76hzg3//VnkwoiKJTp1fPAA/k+EJRY/qNdhhQt0tEIcIaDjN7ADDL9XAMj6LdNow0 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 Reviewed-by: Liam R. Howlett --- 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 f55e59bd9122..6a8982146338 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 Tue Jul 11 03:54:39 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13308094 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 EACC0C001B0 for ; Tue, 11 Jul 2023 03:55:10 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 83B0A8E0005; Mon, 10 Jul 2023 23:55:10 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 7EB518E0002; Mon, 10 Jul 2023 23:55:10 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 665178E0005; Mon, 10 Jul 2023 23:55:10 -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 586BC8E0002 for ; Mon, 10 Jul 2023 23:55:10 -0400 (EDT) Received: from smtpin10.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 380CCAFD81 for ; Tue, 11 Jul 2023 03:55:10 +0000 (UTC) X-FDA: 80997965580.10.87FDCE0 Received: from mail-oo1-f46.google.com (mail-oo1-f46.google.com [209.85.161.46]) by imf09.hostedemail.com (Postfix) with ESMTP id 68BD214000C for ; Tue, 11 Jul 2023 03:55:08 +0000 (UTC) Authentication-Results: imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="ba93/Clp"; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.161.46 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=1689047708; 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=8nUv2eBUflOVJLrJw9mH1jkiLbgnM6ws75Pkn4jd+6E=; b=3Sf1yS5B6eneELaNlZqL5FMfT0vCM5ltJ3mVgEmAAb+UxSN48hCD78LepUy2eB6KZke8Ra AK0TUSnzxeb0s1GSo9es0Alehrd4d2Ho/RPI44AaSfZFQeNs3Ky/peACgMUJsjNYfUS34p womKtShjYH+GQvH3rMDBGJ2qnJHmXdw= ARC-Authentication-Results: i=1; imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="ba93/Clp"; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.161.46 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=1689047708; a=rsa-sha256; cv=none; b=O64bdy5Q8r3bWrNYp8uHjadIa05pu8t4Vs4LH2jMhTzeJu/ovRHrUDZpp1m6J45U4v/RGR tpOqZllhtwSWkD1wPMLU6qN4kZNeSe/m7g5tGy4gHG5bzDiLo4cw12SzJIFadHuc7ORQlH GRapjQ5+Alsbzz8Ln2sFSGKEjKXYFUY= Received: by mail-oo1-f46.google.com with SMTP id 006d021491bc7-55e1ae72dceso3772972eaf.3 for ; Mon, 10 Jul 2023 20:55:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047707; x=1691639707; 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=8nUv2eBUflOVJLrJw9mH1jkiLbgnM6ws75Pkn4jd+6E=; b=ba93/ClplBNkeT536iWxDiRxrvDKLuk5KzbRIGlkNS/wjSUDSw0YG2fdY+wocAKY5f QIcaK5gsT/UKH1/j1gmInqnQydQtLdFwMoEaVF8Y0JynNst6O2va9pZ58iQ78jbDHz4R ndraKp96OKm6JzDpx9nPiOKqPRN6160Rbdcb2ka3yKuAnldcB1vGQArUyhhiXyJmqeu2 DFn5VI06R0dhs/J0QOYB+u8lmCI5Mtr0NqjaEOG+OIxk4KMQHM16azCfVmq9ldF6/EYQ M/n4PHfRcWMdYBEYL/VcaBdPlvczwae5dmhcz/2jNwPFqIr4m2+KUs+sIdqrqveJOrb2 UMtA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047707; x=1691639707; 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=8nUv2eBUflOVJLrJw9mH1jkiLbgnM6ws75Pkn4jd+6E=; b=ZUFJ2+V9nXYWosI0TAQAHUlkAZS+g5ljkEyVCeDJHdASYf5Wvi7+TzKw/brB7mDheM UtgRrI1hywNXHav3rWzqn/BKBUs3GCjKt7neViQfvJ2vWnitj4JjXIxCXnUFXLd/cypX n7HRrpjqUvQk2H9B9tmE5Gp7uEXozW0IOw57EkA2HfoYGUzhY5PlHSVpuKQ3jv6Bb+k8 dMppHDRdO/Ma+DOgcTGfiGVb6W0N5PaWhFVo1nn9LbHLDTK2HN0MvsklqHEtm9l3srHW v81zoOa1hsR+j/+G2nbhreldwoZEghLOgrnRE5J34Vu8K8JA0igsmzTRgD3qCHvSYHt9 j5bQ== X-Gm-Message-State: ABy/qLYWcQMPMjYPeBdyN66CtzimYLcELtNi05o1ZNl0jwpDL3EPK7GK H9U51BKZfUAYgQOQiCitV7uEIg== X-Google-Smtp-Source: APBJJlFQdZ5ouen7AkuwOFPVNmD1rUP/WKxjeZ5E1cKkHpCB9W7ANQJv0/FGjEcF/RHwquL0uQTEFg== X-Received: by 2002:a05:6358:c0f:b0:135:4dcf:9a2a with SMTP id f15-20020a0563580c0f00b001354dcf9a2amr10478949rwj.7.1689047707525; Mon, 10 Jul 2023 20:55:07 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.05 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:07 -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 v2 3/8] maple_tree: make mas_validate_gaps() to check metadata Date: Tue, 11 Jul 2023 11:54:39 +0800 Message-Id: <20230711035444.526-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 68BD214000C X-Rspam-User: X-Stat-Signature: 8tsu6fbuig33g6ipqe15xjtjxh8w36xr X-Rspamd-Server: rspam01 X-HE-Tag: 1689047708-45670 X-HE-Meta: U2FsdGVkX19kzXP2gXiwl/KEQgi8iequnG22tBq3bxtyMrEwTUgFYeHXtzjgogFz85ZDrJWc/dJ94QEzWRu4I6QPVKh4muK3CGt4mIm3I3DzhEyTrn4PWXUQc37KWR7Q/jnH1/WvkBHGUEBj5etofUXtt4BKZl41sIlokTvoP0bQ+myKPXwgq7YknFVUVGTczNXVVnomEvST+4WgkG8l5S0QcDqJ+CPS4FXlqO158ZJSKKyoGK++XGlVKv1fswxkzsL1RT+F0IrSv9Az5cvkJObK2C/FxuOwKZqFMBs4Pv9PMy/Fyt244x6HthJc8ecH09evSCnehOI0QmsQ88n7FXuf/+R1OU9YKFcejZavTLKqGlhXQe71Ow7JdSGz/gZpbxzNs+pi2F7JLzD4SbviWJKbRt+VfbkkrIaM3M+i6nGaT3RMVSUzh2111r9dKHLjEmOIZNEuwYBSL3M/kYewVO/2FyhV5CmeAAxJYGKIu/cFx5FBeRfC4YPwO8nz5vEOD47jYIDHzPE+N6bKVausMPeCdrvqXLhh5RQk/eEAHM5Inxj9OXcO3aYwNf2TZmOaxHCaGgPa7sjom7mFVw8U2eEGXImoIhl7FITkZ0R9NEW41NzlleWV826cDF57QA3rssd7zzD2qU9fjFbSJyO7i1G1HnKBo0Hg8rTomCLglzUOwSIwUymgKXbWD/Kc7XboVwSJ/q6+X+rcy6gxzwt76pabeOJ+HKfUJLZ/14bfBWnwBc+A+M1DTXXc2T00jqDQGS5OvpMmBeRszJ0Vb6sOXeMxTZmL00qXWjSgcJfm+SoHY5cFBCBwEWLi68eM8UR+VQf7jYK82aCou692Fch/bN4wuIT9VsXxvhKsWVNDt2hYKXyXYN4UdPUSos6rnjzuVPopgOZMGBYdHGfUQBSwM/bJ0ODNHFDRTqiEa78zrG7NF098kXT7YMBMSyUEWx2hXzPajgcJQlRhhGJM4Je AjRAi+dE I8AfSbOQUcVljoe2ueSNjfI8kz7k/zTa7acZ2JRfV38S/IKWTgxI/W5EJI8iNXfBsAbRgLJGiSYubLYYc+Zsohs95jQ8k15kAqjYlxvOyx7nRCaSSlR2LFfjI+ucHZJGn5L/1smzSzY35zc4KhUDJtZ76bk5Np6qRkVqilpLpWDek7Dfgm7AnAcu4jB8s3d+AnA+dmlhEzqZMyyeGoRTh8EljwW8of7pL8R8ZmAeMrw+4dMuIJdSmoVzRU4a79g/NaknM7NTOsLfZN874eVQFwzB6w0aHgi1H1fTsXi5yXrSOAmTvIlb/dktgwwh96se8JWrSQoZdc57GgpMDc29NP6wmHqk7XJcTgR8AFpECtcJQoN1E8c5RB/G+Fn7rFuOKQOmey8GLMW6EFhbBsKVRCKRml5eQa342f07hS/onX0tPnmAxdA84s50BLuGGTXEwRQMZ+jnSpUHsY0Q= 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. Add the verification that gaps beyond the node limit are zero. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 78 ++++++++++++++++++++++++++---------------------- 1 file changed, 42 insertions(+), 36 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6a8982146338..a5776fab1875 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6983,15 +6983,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)); - int i; + unsigned long *pivots = ma_pivots(node, mt); + unsigned 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) @@ -7004,52 +7005,59 @@ 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 > i) { + 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); + } + + MT_BUG_ON(mas->tree, !gaps); + for (i++ ; i < mt_slot_count(mte); i++) { + if (gaps[i] != 0) { + pr_err("gap %p[%u] beyond node limit != 0\n", + node, i); + MT_BUG_ON(mas->tree, 1); + } + } + } + if (mte_is_root(mte)) return; @@ -7059,10 +7067,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 Tue Jul 11 03:54:40 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13308095 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 82BD8EB64DC for ; Tue, 11 Jul 2023 03:55:14 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id ECB2C8E0006; Mon, 10 Jul 2023 23:55:13 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id E7B408E0002; Mon, 10 Jul 2023 23:55:13 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D435F8E0006; Mon, 10 Jul 2023 23:55:13 -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 C5F8F8E0002 for ; Mon, 10 Jul 2023 23:55:13 -0400 (EDT) Received: from smtpin24.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 8582CAFE3F for ; Tue, 11 Jul 2023 03:55:13 +0000 (UTC) X-FDA: 80997965706.24.D5F47B3 Received: from mail-pl1-f176.google.com (mail-pl1-f176.google.com [209.85.214.176]) by imf18.hostedemail.com (Postfix) with ESMTP id AE0911C0005 for ; Tue, 11 Jul 2023 03:55:11 +0000 (UTC) Authentication-Results: imf18.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=RBwCD953; spf=pass (imf18.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.176 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=1689047711; 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=trWG5ZcTEhQeGdiIh695WKCYOeE3HbrZ9Lquw5Sy0DA=; b=7A11U3TKJ/o2ycgwoDBzB0wE9bi0AFd5mNDrrDQsrhxxtAgwud86v2DnY7D5wsDeqmJZFl lXMptgd6GsaHpudarObEQviAbhfUA+4AprPScGFtmaoGqXLTs7BgLjImexTmGE9SQ425Nt OCDX1s+bcgyIaGWymv8BOF3z0E4elIA= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1689047711; a=rsa-sha256; cv=none; b=rWW/TQ+h5ymVAB/22IGmbEH6c3RowJc+cBWvVhogdpqkJGfIewd4M1vZw0b12I2wLn1P1C hyAVe7VZCIl+gIwtk+P7eUoEuHENhWVSZ3phQ3KP9na7jDDuuLVTMuThCiGHYmWNNmogFx SX/+w6I1vDek7lD31sWwBljFMoxItOU= ARC-Authentication-Results: i=1; imf18.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=RBwCD953; spf=pass (imf18.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.176 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pl1-f176.google.com with SMTP id d9443c01a7336-1b9c368f4b5so23801005ad.0 for ; Mon, 10 Jul 2023 20:55:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047710; x=1691639710; 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=trWG5ZcTEhQeGdiIh695WKCYOeE3HbrZ9Lquw5Sy0DA=; b=RBwCD953n8uZsMTFBTHHBrqSeGPAwgTiNB4mn19QAWfXCNEYcpGV1kO3pwrVNg8yiO 4ChpEv1ST7jhjL5P3juHp3AxjrYpZOoUZVhD2YQEdnop9cODo0HrY8a0kzrHUNaUIvkj O1spSqlg3rieSeSLBfw8jVSeQ+y/GqBPmyB5Avs2d2g6U18ZtSVO+yG2hZ8l0KZkCgPf 9sjA0l8IF0bLaMPCEax3vXMEOqTK9Cbi/czByHRMN1o+xEe1N1f+PJx1K+l/9/PeL/cF /WpOb15CGoZm3QwOcSnNOf9bHQ47bs7GLBz7f6r8m2UpoVAIMjkZhz0huGnDN+G6zPf1 oDpg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047710; x=1691639710; 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=trWG5ZcTEhQeGdiIh695WKCYOeE3HbrZ9Lquw5Sy0DA=; b=lV3tYWP5MfaG5Gy/jzHCENwDzN4zPgI+OC17DOW0etVvoLVuqWnx9VvMkgZb8WgOD9 DHQ4fPQhi6LSDiRzXekmAEToWvtDVsGc2ePFjsLx9woO1fprmKm99vCuIidXuN7qF7Hd 5oCMcfkrRm85xrJXw0AyyHprZm7vjDYbQNQGzPHJ1SNosKdwZv68Xtrj6Au2BfnXM/ht eCuhyExvwf5mgqvwBNMOhSEVNMlMZUPAyuQ+9iJpNUWHjIPhIYo1BzQ7csxoV1YaL3H/ ccqnQKY3h57ZdGSBgmL0P2BuXeXIjr/Q/yUsu/zTEKoAE9Ry1YXcz8IaVRZD1D/9bA79 ViaQ== X-Gm-Message-State: ABy/qLZDtTnbrYXK9RbYtuizBfAiQ/WPpAbnA3T6BcSuuKWeeqVwdW3u GrxLoIiO+IkWagyqayBHiXmmAg== X-Google-Smtp-Source: APBJJlGAHImLe3JwZyPyDVH1VXMjy9vrBysT74mOvTPUwjlmymGLtnOZwnAIUkbTS+FLwMQi0gLuzg== X-Received: by 2002:a17:903:2441:b0:1b8:a39e:ff4b with SMTP id l1-20020a170903244100b001b8a39eff4bmr26118175pls.32.1689047710631; Mon, 10 Jul 2023 20:55:10 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.07 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:10 -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 v2 4/8] maple_tree: fix mas_validate_child_slot() to check last missed slot Date: Tue, 11 Jul 2023 11:54:40 +0800 Message-Id: <20230711035444.526-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: AE0911C0005 X-Rspam-User: X-Stat-Signature: 96c1qzf9mwxhai3pi68g8a9rmq1nijb6 X-Rspamd-Server: rspam03 X-HE-Tag: 1689047711-918690 X-HE-Meta: U2FsdGVkX1/fTFAnbMnMzeBRc8iG+lALJM8H0yEDVWT9EbDqc10gbvOA94qNV12RnMpvd34GRD4UOr2zPPSQhN5wYtJAwlDg7uvOGY5QsFon8AtXqrJYbSR8Vy2Ce7Bx4L5xdn8KJAS8IrWnCtFb0qEWPGGP0nvRL6JaQWIZl1dmpDLiydWTRN3gvzTun9gorLpV9PH87vNTpVhAgLNrBA/Knno40i9NAh3xNKdtnxCEmRKsQL8xxM+5hjDIISfQkMzQWz1bsNBqkU03bnwm4caJm8wCUoSCKSe/5hHS7w96Aq7d/ZVR1/55jkG/vA8kse8owEP5yylKb0XFNYhV8wJw9NcRvjMClhPPkaEgo+JJivNmd/rUE9YnjwfGJ63uz/DPeGghdMcMdBfnThQWcAtiNLQpZAscXZ0ys2gA6rrcgAUY5THKhvnxv32Yxe9oU1A+jADUoSJlKAq2A01/f4E2zih1Y0FmP+6la8B07oogbLCmkPYcBAU36vW4g15F3IHmlWYWS23T9v7tJ5gNFnN+myIe8idU2cinIKL+gpXLYo37cxWc+vGDu03I+bSmqt+RA8FAggczL/M3gCO5Wtkg9prcj0XGZyq9ARbHqAp9mGDZw7BnJQ1fspxg2VxUNtl6GV2qn05Z5zATz+10t4l7pJrR6cvSYUDVfAZakOwov/ILlSHmLgciMuWJ9/vwNAafTxPJdOHp+f8dXpiVPp5mnnU8owbDxYxdjg629lVqcuU512G3/b0UXURarigDtZV6hvVbvzZfVsXoiO/ERFhIdtwDeceyTCvhLEk1PFEP+VlbiDlfzBSIvEFfv49GCoZm5mYGrBmdoeh8PxbS5B+1Zr3kcZaJcQIxTlrRZyIhqHjxRTMY30xccOfjZBB0npdn6Czbm/nzEm1/0fEHiFyDej4GB8U2va1CewwhPFnYeabn4n50xBcwDmYHr5ZfvDXFoElpDPCIxSGaA6P Cc7ptTl8 4kQSJ4U1soMx/0pZcjhE+4p4LFw0q1CYuFaiweBs4xqNN35Aiuv956rlUxQCW2kE2lqgB5UBu9MXmgJQEpqSxxTd0dPJMrhfWB57D3jeiRNUfPLme/sJ8pQxHANDTIw1J+t67VGYYWfUUhdoprSYgdKxZfDUaT8Ppv2VGV7wtxdvwPmEvqMjFkD97mROkibOb5rCIA0NlUSuv+q3rNoWb8IFQ+4crGYD3HT/10GJWFSxmVTGK8uvGZesVPZVdpRBdz3+vvSvK3RVRuJLh9XkeXyfw7z6r3KaOrYxmUR9x6L9jxtia6HcIeYc72SMANHWJOX0enrWdhPf8oeZpqyF+c5OGZb1ih9uv5viv7tdVzEA8VE4kjqZf75II/Z9XgtvCsHVbETXBgLYkHSvto4/FaC6g61SsDZvWtmPo+jsqarQZUlnlTp2kybheM6iTob8RzJklf81AEGL9f7dB1BTVUW4siy7LB+cBTUdS X-Bogosity: Ham, tests=bogofilter, spamicity=0.000036, 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 Reviewed-by: Liam R. Howlett --- 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 a5776fab1875..f750ebef595f 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7119,11 +7119,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", @@ -7138,6 +7139,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 Tue Jul 11 03:54:41 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13308096 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 1FD82EB64DD for ; Tue, 11 Jul 2023 03:55:18 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A5DED8E0007; Mon, 10 Jul 2023 23:55:17 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A0DBD8E0002; Mon, 10 Jul 2023 23:55:17 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 8D5558E0007; Mon, 10 Jul 2023 23:55:17 -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 824A88E0002 for ; Mon, 10 Jul 2023 23:55:17 -0400 (EDT) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 5A019802D7 for ; Tue, 11 Jul 2023 03:55:17 +0000 (UTC) X-FDA: 80997965874.07.5707476 Received: from mail-ot1-f51.google.com (mail-ot1-f51.google.com [209.85.210.51]) by imf18.hostedemail.com (Postfix) with ESMTP id 888C31C0005 for ; Tue, 11 Jul 2023 03:55:14 +0000 (UTC) Authentication-Results: imf18.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=CmxeKRs4; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf18.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.51 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=1689047714; 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=IIlxgDREFu6LlOiulF242HoL+hhnsQmd+OCvzSb0WTY=; b=i7rMCqL4sX97LAcoCX+2L+zgY2zwYA33opA6SWQ1xnvI4+O5wRoXnoW+OmtASV+Z1NmoXG FrEk9LoBCQvC6ggV+eoHbDNtDGA361lozfkq5KPFx/1j/tIoHmGWejPnmLWpgU0+E+FHoA OvrDZ3hc6ZxsbVjHAhj/vu4BQ0famDw= ARC-Authentication-Results: i=1; imf18.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=CmxeKRs4; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf18.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.51 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1689047714; a=rsa-sha256; cv=none; b=cQaF2ROEt3kG1J6RgglmzRbUmOtq9LehgBg/Ez//E1cmf28QiaYcp057HFxMtq29OBqTHk GfnmHW6DpYAoeHyMSS3p6Ls7gMJPL/UTXen42Ixlp9696wr+CiyNmVRBHE0mja/X18KlZh g8OvHquXgZGQebqlWu05Pby2c7AO8b8= Received: by mail-ot1-f51.google.com with SMTP id 46e09a7af769-6b5ef64bca6so4623900a34.3 for ; Mon, 10 Jul 2023 20:55:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047713; x=1691639713; 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=IIlxgDREFu6LlOiulF242HoL+hhnsQmd+OCvzSb0WTY=; b=CmxeKRs4gLnyTQYT+priT1hS2JdubJC5Dw/d7haZ/eUhfQ5DQq8hVuNMfRYn0YrKfY Ere1opP+H09ay1uUCmD9kh4UFVcpIbi2SR7/v45hmGGedCsFMQP3NOr8I/oahWOEG28L FHyHWHEStwZS08cCmBqv+KoceYbwE0k6jnZbqJUp6YvpwzUaFpP3wuoCSAXRC90ZVPbe k/DY6/mOEVsGugOyMCCTxcwo56s6Afhsnl9I6hbNxTGvNYu938n6abLjmyi171Pg75zw ytktelZVA+im/0Vpnwlp4JUajcIfcJ3I6n3qCfLCrBjvPngSvJou6nOA9Hu6O7kxYWyl bFsQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047713; x=1691639713; 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=IIlxgDREFu6LlOiulF242HoL+hhnsQmd+OCvzSb0WTY=; b=VjGUrxdYLSDsn4ssd9viNsu6eYZv4X4wnhodJMTHV0MDXcNAf+Jj9O90jNzv0oa47x hU0e95McaZVgcrpe0lN0YITQNIChzOoN383T/vL2AnnvcaiZelRTKPYc97yOfkExFBh8 Z9jf9RuSNirfG30ghI9JeM8D7PggOZGgQouY5ZJ9OLaXHoJs8ouS6AAbMZeQ7pS280wO NS/ltNEOQq83iXEJlYjwX20cQyUFhlJM/Wb+jD/i6cQY5C1LiYSNnrv2FAQ+QW8yHByZ /H7RDypyc0yv1WuUbIzyD6mb32O4rX2/NxnsYS8YJXfGq92+gudAPVKk8L73mcBeYZie wPTw== X-Gm-Message-State: ABy/qLZ/dCWnI+GKvpGYOzU9NWarrbdWa/86c51v15kxYmQrZUWAD3nh zAuTG52O1Siwoe+8eKTX5nXE1/mEnS67yfyMk7I= X-Google-Smtp-Source: APBJJlFAdlFH4yOpWh33A5jHeiNI5op1t/pJadGZ9w0dOd23WdGLfmf+wGdZ+cMymmOd7GxyhBWwlg== X-Received: by 2002:a05:6358:9929:b0:134:c984:ab87 with SMTP id w41-20020a056358992900b00134c984ab87mr13040684rwa.4.1689047713510; Mon, 10 Jul 2023 20:55:13 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.11 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:13 -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 v2 5/8] maple_tree: make mas_validate_limits() check root node and node limit Date: Tue, 11 Jul 2023 11:54:41 +0800 Message-Id: <20230711035444.526-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: 888C31C0005 X-Stat-Signature: kwxra8s1syj68146d9gsgi85rcaufzux X-HE-Tag: 1689047714-678823 X-HE-Meta: U2FsdGVkX1+ctYyO/7k2fFyKk3EMIBkiH0vLK/zI+TMEoXWJxzvC9aU9tyzw8pvo9IAjMXV5si1dVKIIIc6Qy2YpEob2OONNTKzidnexs8BLWdLXu8bXvhv+Si5uxLsr3eEQAPPR/s8N2HA/q4+TE3y/tvWurTW09v9zT9LfQc1mI+YMZM6GN4gRxVox1Easnrs4sMncFyWK9DV+3ho7LQgywL1NRA6fJldEwAYEfpf+VRVOo0DUiPYKoa5/7HZzXQLXVF9AuGzgurTVuxRJZu8HVIDxhAWFr8Mupir+rEZ98O/zx+H0RniU5eTXxRIU/oG5yMeUNXvwHpqJMjWSWaui8otYoJahmcsK+JPJXqcuyfrATpPjAcYiS2yXv2lvjuO+smBTkudvSx7VYkG4so1LYLgiljVvOVTpqcEZ9M1CfOjvXWFNaEAej2hqbLRDt+HOA5akTTQ06RaEr19OUGCiapCLSUfilKb/8JKCZv4F1E3J20+4OvfNuAoWQDSNLCCt+pzL0DxEnb+aqi1zy8u9xiqI5OLr5pLo14cQSfnl1xaLMh0UzsJdi0SALkvkhdppuZMxpXJ/OP4GPSlOf75KSC2+SIBgFnkjjqB170wC+L5tWucgNwI1Nbtp0VGqBhDs5W9/n87oTi68PsDrEeOot+ZJTxI8/HQB2l/WFYktmji7/JokWXwbuGF9boxXX8EAU9/xlHR4jM6LxcwKW6zrWBUMWukSj2bbBn2Y0DLQh+77a8IrTy7f4JhMMeOWTXPtDzHWCzV13cujacRsJn4xsC7UpNByIcHBr7gD2P7Gka6EmbI/SMfHuljQjx+YK/4VKmMuR0DmHM59NDkwxCwr8eTF7/VUJrKwITBVxIlwI9x48brOSmF/+YsjqaeHt0R4SnDPYSb4vvnNgxBYXrrak4hwWSrg1dQeNXWdsuzZC3BO363r1UJaaez1XpGJ+39uZH8K33JOsGRDYWo EYWjUm37 NbPUKPK9TlUxX4IqebP4E06fDqy1LDaa8p2CaQSWX7z5f5TVqkkErY1WfGL1GGlHAVsF8FULxgb6rA4lNVYIOBXsnCGp51Qd7nmUP07Scx5iQz1K141i4yqkhSpn/EyaDyC8F9LedUqt101OTYx9XeRkLwd+QhJSE1N4Ym+uGpe2prdRsNVw/hK45JzPxECc7xGwcqJIbNMlGrXFchXFhR34E3EKRQQfU67MjGb7yHkKtU52l/GSzAlcz8xpEzaTNP22cL9xCBIdIsP+YPPZFXYnm+/zXocdozfzhJZjgdzh2qMGKu/MG/ue2710bNO3Le6ZyICTclt1gkswIzWRE6mw26BU7rlCY9gJ5y1XtSLdCnKsAfsdA9GyoUOPjAH1LShp0mVXSl6yIETYtlVdxQ+a3Yrj72Rc8t7At2xBLhogKBG0z2qn06ZwRBruKrdVBzSdiOMaL4QV2a/Y= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000057, 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 Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 30 ++++++++++++++---------------- 1 file changed, 14 insertions(+), 16 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index f750ebef595f..072532fa18ee 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7146,7 +7146,9 @@ static void mas_validate_child_slot(struct ma_state *mas) } /* - * Validate all pivots are within mas->min and mas->max. + * Validate all pivots are within mas->min and mas->max, check metadata ends + * where the maximum ends and ensure there is no slots or pivots set outside of + * the end of the data. */ static void mas_validate_limits(struct ma_state *mas) { @@ -7156,26 +7158,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) { @@ -7198,6 +7189,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 Tue Jul 11 03:54:42 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13308097 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 ECD7AEB64DC for ; Tue, 11 Jul 2023 03:55:19 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 889128E0008; Mon, 10 Jul 2023 23:55:19 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 838C88E0002; Mon, 10 Jul 2023 23:55:19 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 6DA218E0008; Mon, 10 Jul 2023 23:55:19 -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 5CFA48E0002 for ; Mon, 10 Jul 2023 23:55:19 -0400 (EDT) Received: from smtpin15.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 24ADDA0301 for ; Tue, 11 Jul 2023 03:55:19 +0000 (UTC) X-FDA: 80997965958.15.A13E3E4 Received: from mail-qv1-f42.google.com (mail-qv1-f42.google.com [209.85.219.42]) by imf26.hostedemail.com (Postfix) with ESMTP id 4F99214000F for ; Tue, 11 Jul 2023 03:55:17 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=LSWgQLIm; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf26.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.219.42 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=1689047717; 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=VB6Zk8yx2k+1HDLx/vyMhcB3cYhsChcAv55Bv4rEWns=; b=a1UXppfJXCV2SHVPoIFQ8xkTlpbOxERexfqN4SbDy42qz/PUCKuclIzzZo6DDQxM5e3pfG 2feD9Va+vR4KSe7egE0rTHXoHu8SUiDezJRWJS1V3CW8kL5Dfs5TFboCtkmGIGwQOqSyFK imTfbp6WJjyH0UOVzcDrfEIY6IacRJA= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=LSWgQLIm; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf26.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.219.42 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1689047717; a=rsa-sha256; cv=none; b=XIVYolZmXaG9aZqX0tDoSuvsdqK39h77XHgC7WUBwUEYOGYtalqubEGdbzIhmVS0tFdZoF spoLFicdj8WdRJTDVG9wTWz82JBEsYL5OV+hk+InlmG9IzIJOwWXYPfDECHdBETWQiECgb 9jVPpT9XtmN/KxiuCyKeGdeyQ1U4BrM= Received: by mail-qv1-f42.google.com with SMTP id 6a1803df08f44-63770af327fso35891386d6.2 for ; Mon, 10 Jul 2023 20:55:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047716; x=1691639716; 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=VB6Zk8yx2k+1HDLx/vyMhcB3cYhsChcAv55Bv4rEWns=; b=LSWgQLIm1PFWUmQi+43SqOstxpJoc3S5KiF0uBqZBj+yhFOyw31mF12pOmarXSQTwl ftLznRUeQW71nK3PQ10DqNTXANC+OzuxYtBuC6dEParOiiStsUCAqTUuuFV87HYUI7ju uOT3WQoFhn8iH8thH0rnasi0ozRlnz9v4G5nx3FuT0HEGBIojQ/P+EgU7XeHHOcdTwEh rl+muaqKcxNVqi50mRjNkFJGUYhKZNbiZ5e5AgdmWuRmWeKMzDDYIM9TwleGcI9Tyy4U r/iL1UYkK2+O5mX+8p+GRA3Z6xTt3Qt+4LVhqHd9F8RAsfoU1ZlSZcV1hsh0tp7hekj6 kCDQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047716; x=1691639716; 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=VB6Zk8yx2k+1HDLx/vyMhcB3cYhsChcAv55Bv4rEWns=; b=fwvWERiw86dYEVhoWJWbYoK4/vAd4wpyjjHu2WnzQD5vbSoiR5eR5+DAbawe27bk7q NUEAbJOxHdBpStGCdpToDhXXGupanhdqEPyJZUyDQJQK3YsqMJTkGwpmrfQ12hq+JoPD mPyYCs6rEMdV1rjT9GNvMUf6XlpKkG5XZexDng81KEn74UOZjBhlz3hTvFSRupYQQgav A8IIf6TRaFvIx7gnz5fQwH73X7ESkzWFNONddwbR+ILapYzYCgzw4ZL7wWxwkR9acSYO f2x+C6qVe+NJbiNUCVRyak6SVuiGJUv0YHkK7ap3SPYuI5aDrSn6nc5FX16BXw0uZzIe IKMw== X-Gm-Message-State: ABy/qLabMUIXMhQMayzAvLqvZelZbk2wAVMO37uCS8vbz3l7rJn6+23Z 7ZuD8PwRoahOGMvJ9TN8tWMTZw== X-Google-Smtp-Source: APBJJlEnW9Zfp2okquSeGO/JAFM7vrs2pnSVclOfwaHYw3+NqS7kqVlvETzZeA0RLZFxlJazP5po8w== X-Received: by 2002:a0c:e28c:0:b0:635:de52:8385 with SMTP id r12-20020a0ce28c000000b00635de528385mr13630151qvl.65.1689047716426; Mon, 10 Jul 2023 20:55:16 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.13 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:16 -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 v2 6/8] maple_tree: update mt_validate() Date: Tue, 11 Jul 2023 11:54:42 +0800 Message-Id: <20230711035444.526-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 4F99214000F X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: yzgiqhy6kxzm5hrt88xofs7pwd6bs3ir X-HE-Tag: 1689047717-512567 X-HE-Meta: U2FsdGVkX1+zj4dGiX241fgcQ9gWGvReySjE9VU3Zv6Aomem54TvlYKrgIZ+0MIPZ1bLLs4FHC6qjM6XBO68jKgWb83HW9ssXbr5XReXLpFLkKyEkTQ9fEnNEOHYJfAeJPCHVIdZQKChCE097UOswcnipdRHk4jVAJuf75ToJJJqjtW+Ruc46TLQMzVxtTOz+pxa33uf5OjkBaI8S6pkr4fC6+iA8PuseOyUG57I7q/vnVlP/AVJLlAqWemw0hOoOsjopqfQ5ZsByg51oGOR0AONXVzys6nf8YvZlv3WQcxuH/iyQHq1BsIe927FPkI8cahp/zvQ1+Az9B1GWCDPrX+FzKVnFUOVD0/oR4YHrXcYljefz76cb1CaYxT0FYG7rGI6ke9G9WkXT5PpaxDvbTEQOfeeNh4zFtWOkJvWU6e3fiZNX0jzwyuPJiLn3s2U0riI9JEI+qXs14z+z6m71byFazIMCwt6JnKxAtx5nXfV7BXrOi6K2UP81/WWkEPvxuktDk/y2aYeZWAIRhshoi4f0kFANc9yfZp/Bdg6BAPxCuA7JY/EfWfzCLp1G6lvab3FNssLsgbC5uPgV3k4uiLvgWVX1lpFgGaEe5pwV1JGVvk+2+jvtqUgaaxQlIST2UcNjFfWoRqXt9Z82BvNPeELwIoaIYxpsiZ9viySV7TnI/9qWdOED6a+z+5clis1LRJWJVsBPsNKwdn3EwiTHMjkIHSGQoC+v2jUMetJrFnWx9klp+f9wGg5M6RHXckKuW7zbWR1hJOPgeT4KjQ9vhTLPIyDvJ5AgFYh7xam3sq8l6ke0jpFdvOcLbgPwx5FI5CfMIfAVm6Ht0tdJRl3DArN8xeL+HCkRn/aOlc1hU4F5WSDirIheVHKLugNCMhWPU5H854CD5osCZcl6biRLou7eAN5c2gJ8OhTibUyQv2/SFvgedRk3ROz0IrCQerfE5vJwo6wqrWcViEeu3z 0Wr8agL2 2M3md5JboAdFlDl/NHAL1chqutO8Q0+umNIlYt2JY3oU18RfZOEIx3Kal6cCP51Nl5VwiX2oAHMrhoKRCYAMwFLzC5pKW9OnSanV5a85xy6PkP0p0sU0paShPDutZlsJWSnZUyd43kZCCjrxVjr/itKOU5lrnx+EdS+MTcaYfYCycP4AfrM+3jdbpa/BtfwQjHeJ1KKja09vEEFPe+Rwu0J6ajVZzBq7197xgiL4xRQ59MzSslNcWHNn/4piKW1Ypndj3x8I7ewxH+JQJxbV5Qls2VHZAgPBDtp5APdPWV0aOoCik1sQDyBEobQVF7IRmyLRkG2O37EskN/MfdaPA3Op/juf1q/Uw9wdYs05axGSYm9y6HA/s/hp5gkhVQkClLTVAhHoJIpiVU/An8gcXbx+zVJiWJJhfMlh5Itmwb4OuRtC1yhEpYl6nVSA62miT6searU6+d5jjnRE= X-Bogosity: Ham, tests=bogofilter, spamicity=0.002836, 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 Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 19 +++++++++---------- 1 file changed, 9 insertions(+), 10 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 072532fa18ee..1ad11799e197 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7270,21 +7270,20 @@ 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 Tue Jul 11 03:54:43 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13308098 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 E5F29EB64DC for ; Tue, 11 Jul 2023 03:55:22 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 813978E0009; Mon, 10 Jul 2023 23:55:22 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 7C32B8E0002; Mon, 10 Jul 2023 23:55:22 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 6B32A8E0009; Mon, 10 Jul 2023 23:55:22 -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 5ED8A8E0002 for ; Mon, 10 Jul 2023 23:55:22 -0400 (EDT) Received: from smtpin04.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 27755402E7 for ; Tue, 11 Jul 2023 03:55:22 +0000 (UTC) X-FDA: 80997966084.04.E7422F8 Received: from mail-oi1-f179.google.com (mail-oi1-f179.google.com [209.85.167.179]) by imf08.hostedemail.com (Postfix) with ESMTP id 53B18160008 for ; Tue, 11 Jul 2023 03:55:20 +0000 (UTC) Authentication-Results: imf08.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=iULxRDLC; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf08.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.167.179 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=1689047720; 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=DbarY+W3CHTFGsKxfdT0v+U7T4eLSEDHZXXVmyxXdNU=; b=8GG5h+pdJvw0YSJY4HY3Ks2jHxyU2rFnm53Mon299g4M7kGuIgyKhrIvVmLtsoy+gIXIOz cakeon+DkbJfafpaDpshLJ1M8FEJWI169GjtFdBq+CNn7a3Fb/1L7k2T+zeZmV5NOWKig0 AahAmPhG23gz0xDoOdiETf+cogPzT1M= ARC-Authentication-Results: i=1; imf08.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=iULxRDLC; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf08.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.167.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1689047720; a=rsa-sha256; cv=none; b=ZiKozaGCvTVlNAKRPA9mkL4wc33jczTRA+gIG44YOQXUqsWWjU5b1V8vLCZfQM3DWu/Pk2 ePybBLufUcnvh8u2LYYyBY9BumwYVFVXU6EcCTA3EufFneNXx7V9iICNdaeqE7OUDcYbVf PH5/6gGSoJcQCF1b4r1O/+k76Z46mZM= Received: by mail-oi1-f179.google.com with SMTP id 5614622812f47-3a3373211a1so3475407b6e.0 for ; Mon, 10 Jul 2023 20:55:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047719; x=1691639719; 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=DbarY+W3CHTFGsKxfdT0v+U7T4eLSEDHZXXVmyxXdNU=; b=iULxRDLCYTw8LCbKROb4TXPoBYnA1v18DTCUhinG5JOrzgwyPzolG/GbPjP0Ghw877 ZeFhZ6pfEHNACpMhdSEdi8M0CIttf3djc5hRG285cAP0/TdP5VIo1CJhiMnrYxLq2Br4 TEqxemWUZJVJquPT6NkviWia/MOosyK5GroVKnwfWkNPWYGHKqQef5iwhDlsHOTZiv5s zvAcmE2osWi2vEjvqYWeu+/GQVnyI/4GTgGh5h0cTmgsCE+9IIyvbxoaE62+oKyUht+O n1EFaO4uQsZ5zcdikocUiGLossOZB6cy46l+rMKDTASMmpejL7ZdcoSghLjWjYdkEzQq WZTA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047719; x=1691639719; 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=DbarY+W3CHTFGsKxfdT0v+U7T4eLSEDHZXXVmyxXdNU=; b=kl5KORBQfFxm34SNhE95L2JziiwV9FswT3Dmsz9w1JjZSzPdJLJFeyr8a+O/+GCESj U6Ok33/rTLFoi34JOs3DrzKVVBwKoBKljEMpQA49zG3IFRCDxD+3AIm+fbMfIfLh1tlf 5jtLHGp8EL/YaVBOfUAAbJP6CsWy4d8WZtJWaBVbUL9t41omrNtTi8MdwggPcUa+WIm1 yq36zvJvvqlUyr/s2CQ3V53ONzAYLv36xxOqgYvSok9S9oRTcXmXbScYTXDqPnzwnwat 4ayx8pb/8tAAv9Lqo6e9hkK/5ykjCSUa7J/NFi+kj/hEz0WWehHX6UNvdF3RM+d7FQik kczQ== X-Gm-Message-State: ABy/qLYbfuRbwrpLzwvBWLYVjkwwjkF7t88KyOxWYzDeGZLvqRXXsk4/ ZY2nM2t5aKA/Cr7EdeaSMKpC4gOP9IHc+Z1A1rE= X-Google-Smtp-Source: APBJJlGxjfe+8f0dueDM8FJVBeqmo8FaV87lH6hxyhw26brAOEDJLkiIqQISGZnXhuRl933BiJpaSQ== X-Received: by 2002:a05:6358:5923:b0:135:43da:b16d with SMTP id g35-20020a056358592300b0013543dab16dmr13986782rwf.11.1689047719453; Mon, 10 Jul 2023 20:55:19 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.17 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:19 -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 v2 7/8] maple_tree: replace mas_logical_pivot() with mas_safe_pivot() Date: Tue, 11 Jul 2023 11:54:43 +0800 Message-Id: <20230711035444.526-8-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: 53B18160008 X-Stat-Signature: zbkayiu9xr7jcfftk6h3jx3h9hy77q1j X-HE-Tag: 1689047720-297527 X-HE-Meta: U2FsdGVkX191Yw7d7dxI+HI2MkTwDMP3rmBg6sBzrBr2wNuEtGfyefitwCEDBe91NBVWJjn6CF84fCHUCbnA2hJpQik9p2nSF3DIsRX0KiTf+Xsqtzv7SgS1vlJ0k5e9QzeJWv2xYFUHqU6xm6Ag4uFQ5rikLC4xmrjOeRDHcAPItfW4ZwN9eLA2+IJ0Uqb9ynUt+fQNh8b9OecEgzb7a2eZmbADti8e9I0iDxEW7JRo2IeYDd3B7ThFn60N8/8rVqmmvixvh/3Nal2iwyhsAxbckgN2DAzg5+XeUCqtkj7ZCo0zRnCBzGB2RpktMvDBZHm1IS5EMm3aLcygu+bHcb9lDYiufPd0zpdkyolq2a++Z4kbw12kSmY2oP4CPEDN61vEWeC48aT9j7tLi0bk5x0xqjyHmfLy3/JLlQ1pUAYrtyDOCrWH9bgONnvhdxlqt87lCuj+PgGucsuUQk/grnEV5R747AYVC7BTyLYaeIioGdAlWenFUcovEgKka15ZUtFyoeuQo3cUtdjb12cezG9NX39ZYhGeuLEmm0x2B2ZEJ3KFN3c3uVk0BcIvuveiwMrbdZCAGnjNIUBqgivzkicHIsDKVurPYtaJRzpZ6u3ovkxVsUAiQBwQU99z+egDB83A/gEBrA9HY5qimCEERBF+9TJ/PjSx7E6ZEQvZw+KIS54LSBf0hWvmnKE4kgSAdbYMcmsTs/yofusXRteqymbzy5CnG5RuTbNje5XqcaTUdByQTNxmic71enN5Y/LYF/dv2Jj8/6NKIlUtEHR4Clqb8aF/qBpu+l4O8fDLZEVJDOWDDbjY7pBALYOdAQopKT94bIu9ZeJuJgQLCQiDupzIuSXC1BRkOgInswhcmqtKWvORlmu7bEOu3d0E0PS20JTQuV6MJZ64xtuuTRyST2bav91LX+DBiS1jRsfLCjOLvvnzC6y+EMKjJHdX67NTMMw0AOkwrATZ+G69Lpi bKMDElPl FJTFr9tj8Zp/Bwv3m2aHTwgAyfbNj7KgFnBO/8Cvrfr8a6+7Uq3EZeyJEkVjU/x6oD1XZKdiQIVZL7ETCcbjum6fIZq7Ngmlf3tj3eVwUHZpT3hhU/ZFxgpQbFjpidUw3uAVOjxE3Es+WyR/6eOo1nhbM/G7uchTvCly5MIjchlZJM6TurfMlWLq0d5Yaf7uqZCSziX6YbWLmik4Us9bPq/xVG8DquEdTi6Xp9pWIJOeX2w1yMjiUMuxNi+l7JEpSJwlUwhPeBNYTEwZdNtamcYcJCIQ8/2g2bpkqlvb4BGlxTBJwqYXKtg6xCl0FWMpUbFmTAm5m+HYeIScl5te8EJD6r2iXdrq7wDfwxYkQQrMIGWWoX9dawPRQXvP/yEwxlFO1DcumRwEJSsvemNtA0luJVb78N/A4BdxXXm20UlOeLxInoDlg5FY1iITJd1HJP4/zKcPMr5BUbCZWBnpnnFLt7e2JIPU+sAtQRh4pBBc9AGw= 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 Reviewed-by: Liam R. Howlett --- 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 1ad11799e197..5eb5eede2727 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); @@ -4934,7 +4907,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) @@ -7007,7 +6980,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 Tue Jul 11 03:54:44 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13308099 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 DAD4AEB64DC for ; Tue, 11 Jul 2023 03:55:25 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 7ECD08E000A; Mon, 10 Jul 2023 23:55:25 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 79CAE8E0002; Mon, 10 Jul 2023 23:55:25 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 63D6E8E000A; Mon, 10 Jul 2023 23:55:25 -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 57E6E8E0002 for ; Mon, 10 Jul 2023 23:55:25 -0400 (EDT) Received: from smtpin14.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 2135AAFE3F for ; Tue, 11 Jul 2023 03:55:25 +0000 (UTC) X-FDA: 80997966210.14.8A0CA49 Received: from mail-pl1-f180.google.com (mail-pl1-f180.google.com [209.85.214.180]) by imf25.hostedemail.com (Postfix) with ESMTP id 2991EA0004 for ; Tue, 11 Jul 2023 03:55:22 +0000 (UTC) Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=FG0CUQd2; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf25.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=1689047723; 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=9OtSvFihiDnLwRXPS16aFXYvoQJZK7qgLbCrmPMdkz4=; b=01DxzP/OiGUrJvxbbjxZuUa/xHpVG0MilYzGfb56pIJslLkDnVVKMIDkxWyjrOynf4VZXk a/zyr4pBuDmTIkHmIoE4xlMEZMFCBoTUTGfH6a1W87DFpx33Qo+LvsaBP5LxphrhbK9P6Q +Y8o/k4bk6eBQejn3saE+y0f20SJq2I= ARC-Authentication-Results: i=1; imf25.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=FG0CUQd2; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf25.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=1689047723; a=rsa-sha256; cv=none; b=Nz59CC23IwOfQB8AeQ8l0LI69oNLkXWBoqMtjyCFmbsC/TaFsyooDM+U5j4SnUKcwhfpO6 li4BTRBOnw4ZSLHY/orazzWUfinTiWEpM8LmFfuor7iM0ZKemKwYA9unLwSzV4FO3BcXPE 6BM4fEXnbat6C+esnSnbFnt3jURGED8= Received: by mail-pl1-f180.google.com with SMTP id d9443c01a7336-1b8bd586086so39283255ad.2 for ; Mon, 10 Jul 2023 20:55:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047722; x=1691639722; 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=9OtSvFihiDnLwRXPS16aFXYvoQJZK7qgLbCrmPMdkz4=; b=FG0CUQd2LZZyzjMyMvHehaF916WG7DrINm7YYqYYtJ5WS2xrMsL6v25DynuNojHGcY wxJHLbsZd3VzymebJe3AbpxVxh8p92JQt1W7oYL6JGZPHChw5F2mpgzCFQjPgG/pRgrG R9SdhrLWfRfpui4ajHnLe7B+Ce7DB6fG7EHTKc6H4b6krsWfzkslA3A6kJ65n57EMi67 r7wGoSifkbrij6l+nuuX6+RLAvIa2M1VBQhNUZmrtD8uC9zIzrLOoK3lLbRmmWWH00zi F5dCS62bKbff4y7LupnA6PVUNnnxTM6u1aOsADrPYPfQ8pjREh97a5YCVgY0pq0yCm7r /dzg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047722; x=1691639722; 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=9OtSvFihiDnLwRXPS16aFXYvoQJZK7qgLbCrmPMdkz4=; b=BVriuLGK31rOo+7nKRWF6pWHk+hqvk031VD2VUntJpPTAqMV0/XaTQNUg7+do5P1GE IbQIBlB24v0xSV2byojW+kZGxXGKk5cR1UTIS2ykohZUlPyYbMdF69XSzsmBd+ZCjBTK R6f8GiMIw4b4060cXlhvhiq6wG8pbAWuNOKn7uUswp3z1mBONYGdulPeAO58ZguOYHbt QlleEsbrK8gsQmyp3c+Pej4DJ8YicFy8WRZoJwM9sqIIDtgNJsR7aUUaDslKq4Mw4eii SuC8RiHlSpK/RZkJViKxEvlafC10pgmv6EF+NSEe/xL71sUF38vqalPgJ8fxph5TBVXA ULWA== X-Gm-Message-State: ABy/qLbwrGdxOUmeOJyWOnX5do/TzqHTOP4yXgG0PbK46eSFu6SiUkvD E31j8ScP0N56Z0QChcu6N38inw== X-Google-Smtp-Source: APBJJlEH9ks+ldoqWiak1C46jFp9K+PHzKkaAAEHH5o80WCKWCeDBoMcB9O6Ge8DSYjubjyST3RT1w== X-Received: by 2002:a17:902:ecc2:b0:1b9:d439:c009 with SMTP id a2-20020a170902ecc200b001b9d439c009mr10667995plh.57.1689047722210; Mon, 10 Jul 2023 20:55:22 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.19 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:22 -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 v2 8/8] maple_tree: drop mas_first_entry() Date: Tue, 11 Jul 2023 11:54:44 +0800 Message-Id: <20230711035444.526-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 2991EA0004 X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: rf3mpqd7pn389jcoj354k7gh47n6ok7y X-HE-Tag: 1689047722-107624 X-HE-Meta: U2FsdGVkX1+l5LyUmbcyvmQHtlqAmTTjdZwgr2cAaxigjN1u/2lbltjrmhSJF0vq4MW3TBppLgyD27IeIKiGt3qkknmlIo640wSf7fFuZuHtFLeZT9g2MKL3QzZTKSiEM5uv5wbhmXOBEq8dXzjwcITQwfSGLbLWqyfaJn+8CrgphvkodbTY8nvig09AVL3biWk8nziQAAOcgH0IzoWHHiPQpGv208SzlOo751YCf+amJaYATpWXkFb+yZzKRhejbPe9uhf6MGqpMtni1NNAzDiznUqR1eZOIGtFEUMEMwdzCzcPSjuWbB7r8OqKlnH/GUZjnMyS9eh0TaLAdO829YAz/moX82syG0zXA+BD6x/M8NsBlXBNAaxf7BoPtrTa1n1SbD8RcTBujBpSe0pfQZ88AdDrrVffCpzMSmuiqyUsvMYDLp263YhAkUSbWhcHvcIzpkDxB8wGZVqUf951kbD4i/dTA3MKroIDwaLQ7sXlmXkWCzrzpTXSEOIo8IkJd2sWV31RDBi8kCCs7/L3xSffPzMKzLF8M1Y1iJ9VOpJMNIy7BJtw1Ktvzc6Mh9vZxwvMJa0p5fH7oV61QJ7M0F6hW7Q5cpOQg0KqD8QEDCtwe5viG1BUT5i37s9j378HQHW4c0Sx8Q6yI/YvDil/vzEAnfqDdW/gfOZPYoKrvG9CmS3nLlcSKuZv+Om/HcnPO19OHOrs8RQc7euS2/9Aoi1Eey6cAFoZhOicxXZjREeNG4kIzlLzafdPIr3tyUOnU4l52qfg9GG6VQXHTnP/FTRsevzc1faGWkoN5t4unYfWV2jzAH4HbYdkWlpD2fRjP6sH9Mq7VcY6iEhQbbEyTVLpoZAfrnwAEWnf9jgFeqTiI3WJxID1dk0jihiWzTv2F34RtVt5Rjzyfk0LXp/MPlqQnHxYU54y6IG1fn9Ux095GQsCcwmrionPVX0xOELbvYWNPYJRlrhPcqKPPwB Dw242nhQ 3Wpkv8mMBLEhr+2ElQx85uFGNdz9A0eA1bR79I+Yf645Zjh8e3ncLME54G9PPFdJTz+g60hDgTEa2fgCxrL/3HFE7LKmWW5MX6L5b3c5CyWySwXceE9xdfcIZAqu284uty1eGmiMYBzzWJh4yBlRFe0wzOyiiTP4x9md7iASs9uiWwueo/PXaAM5aMLpJdLiRup1S02fapyo1ogBq4XEUp31gvcgPETfkq7ExFBhGXp61Mo5bkcZZdH5/GGKpaZExgSUPZG2GZoxNGacSWi6Ri7yz2ChDxIUjstNi2fvLSKIiWsU8ji4sjiWGDz8XjtMd8MkXLIFg/EIoSvrE069dQqv6H3Mxr66SYuMo/Ve3FrrIAAm9/IBoUYvs9owSj5xdqWy0CmAezVdOzVf6irFYwUsPGz7+9DXnJxfcEKDOHNHbAqkux776Y7AB+1chE5c42Xc3FA8fJlIgFOxoOKvEPdhP2VNhdRiSPDC+S6H/YIarwZs= 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 Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 72 ------------------------------------------------ 1 file changed, 72 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 5eb5eede2727..bd4557eeb42c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6662,78 +6662,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) {