From patchwork Fri Jul 7 10:10:50 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13304699 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 DCE86C001B0 for ; Fri, 7 Jul 2023 10:11:18 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 5E5558D0003; Fri, 7 Jul 2023 06:11:18 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 56E208D0001; Fri, 7 Jul 2023 06:11:18 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 3C1358D0003; Fri, 7 Jul 2023 06:11:18 -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 293D98D0001 for ; Fri, 7 Jul 2023 06:11:18 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id EA1AF160D52 for ; Fri, 7 Jul 2023 10:11:17 +0000 (UTC) X-FDA: 80984398194.03.2AD2429 Received: from mail-pf1-f182.google.com (mail-pf1-f182.google.com [209.85.210.182]) by imf29.hostedemail.com (Postfix) with ESMTP id 1613A120016 for ; Fri, 7 Jul 2023 10:11:15 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=ahfJjKcj; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.182 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=1688724676; 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=obQkYhgKS4HY8GCkScMSh7+VaHIuzmq4BqEaENwQoNQ=; b=ElJ2n3W1KI7QyYmJpAkZpfX4ZzllRYHeVWcsXfPp475LtvzvaBWw3q1lBNxF0zzZM2zS1g MxCIz7XXiE4WsAQO3+2ZFwDObZ28hyHfKPSBJS4v9sz0oMRHNsfAAbxLUrEr8tsqqoNyIy 01sZfYZUEOMkA8Ymk5+jkXUYbh8doFw= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=ahfJjKcj; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.182 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1688724676; a=rsa-sha256; cv=none; b=TRQ9phgG34ZRTSPs/UV7oc1asIhMO7xwUqgWZbVu+4ILQIhJ/HiSLMzUoZNPpn82F7ql55 e1ytojTN46yja2jNDjRayJkCyLqwh1rtQlTrSfAtL7rbEbfDs0iNOuPdQ1EBI5kHI09Vv1 4pmdayhcyNqT2PrQgJsDAlhJ8IznLmk= Received: by mail-pf1-f182.google.com with SMTP id d2e1a72fcca58-666e6ecb52dso1052703b3a.2 for ; Fri, 07 Jul 2023 03:11:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1688724675; x=1691316675; 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=obQkYhgKS4HY8GCkScMSh7+VaHIuzmq4BqEaENwQoNQ=; b=ahfJjKcjkN3t/H/Kibyt7ZUmq5o9Qf9MqO0YUCMAE1gwMas3raqn7C91lMkIMWWa+T IJpR/S9MoSPTB0GA9vEeaHbA3kmXN2W7SWysLZhJs6HexLH13doyrOLey8REwDAcdRPN fP8HOY0sup0QDoYEw9uvVF3G2q+51TJo0nXFR7bTMRyT5OacgzLxQE9frW/AKpX+AWNR /D2sk7Q+gPL7mw1O1vqKgXJGKmWY5ytglXmVVnGG1IqqW4I012Ywz9z/LyJ6/oJGZlRb r8NHFBGoZggHXSbLeAun3FT8PlbYYDJt1ZBk1/8+08pOsZ9cvnyjpIIiC2BX2Ly1YlQ6 H0SA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1688724675; x=1691316675; 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=obQkYhgKS4HY8GCkScMSh7+VaHIuzmq4BqEaENwQoNQ=; b=UZLprgnjhd9GOea3R2gBU+g3BLIy4bBqqZ221b7mEirp2dMF86umI9Y/QmCQliAnUv 7PL+h0+81Xw1RQDZSNXA6WWgZtZoNhhwIkqMIqH8yAMkKoaT2uSYW+DUMBkZtwaf+N16 GMbl5dopzkdhK6+Z74c3/sDPIaGgUrn+rcHYq558xNyd/t/jp2zgO2FyZPCqSDC2gJMT qW0gBgRniarnfGrMO/8u3cpLPGDHKaFlk3IQQn0YzvGcBYcsTMhSxyz/Cl7PfRvOU8j+ aQ6MQpeaMqzBW7AYx0HMA2KHCj2rdKFm8VioVHsO8R2liQmnh8ta+PYRDlB2RVbjzVHH uT8A== X-Gm-Message-State: ABy/qLZh7vZ3NUbr6EPgCrfzM5DfIvUtzIkieDLqutyZC9q4Fc9gX2V5 sfUf+rg3Kn7nIF3BiI1Ujz0/YePgHDjsIWme5Fs= X-Google-Smtp-Source: APBJJlHDXMs7auQxKm6lk5bZ49tnnErX5Li8AtE/l8/sNkUBvdMUGaUh5L2J1GdM5UfG+EeVA+sVlg== X-Received: by 2002:a05:6a00:1593:b0:65e:ec60:b019 with SMTP id u19-20020a056a00159300b0065eec60b019mr4460571pfk.25.1688724674907; Fri, 07 Jul 2023 03:11:14 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id x11-20020a056a00270b00b0068288aaf23esm2602549pfv.100.2023.07.07.03.11.12 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 07 Jul 2023 03:11:14 -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: [RESEND PATCH 1/8] maple_tree: set the node limit when creating a new root node Date: Fri, 7 Jul 2023 18:10:50 +0800 Message-Id: <20230707101057.29326-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230707101057.29326-1-zhangpeng.00@bytedance.com> References: <20230707101057.29326-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 1613A120016 X-Stat-Signature: wicrcunopdcffohwxa4oyo711zh9dyei X-Rspam-User: X-HE-Tag: 1688724675-678958 X-HE-Meta: U2FsdGVkX1/XYgnQ61R1GVD1IzZOoImcaymaOVwAduwIV/QdlmlVCgbakFgqTRO0EwBRDkgHoUcAZBSB0n9Ej/LU2trPWDUUZofleQrjndKFH9G8GwNxYUjic9Q6u4r6VTk9iw1gIqOfOzdoUhFLvVfdd27XQ5gRGYJIlrq5Gn0GHiI19I1wulQNg7fMAVswB+pmJrMBktPunLUQcMIyemtPn51JYp3OFus7B9JMZ9iSRzx14XGmSewvXk+lzx+xri0LCw9N6iK/W8PkosBc/W2na8ZZOTZqlvjaMEqbwZkCvkK4H3NjjzqdxccM3c/zOTRRXs+VsFC55P+7A4qLAJfyVKdEwK/UkP6HWDw/J+3D5VSWl+FI8qaZI/kwSTGKb3vqr5Dk8UUApi+2rpLiUksvJ9PXUKlC8dmHizjFplj+Wa/9n80TUXHjeJMV5gm99vjd913m59JTmPmxPK0dzfVSFLrH6IYX3flUi77NqQntTTDb2IBdNUIHmYGtkSXs/sagbCjQF5k+ddtAtExpfz4Muu6gO7avx0j7Bn5K1GH4E62hMNjWKBoGv3QGRjHfqmH+ehBsiMrILgGtBOafdZIMWPTUtfTxqZ/COwm3F13HC8zStDGF3KeVqvawXlXiHlLGR8W0tSxfzjf8roZ3W4NLvRmBkkSbJYxeXJctmy60t86opIxAFysR9G3j0tcCt4aG7IZgiRUCYrbRtSObZWFvuX0v8u6FgXwbB/V2jXdPw1tJU0eT284x5YeEv3SR7CNXkYLUQTeufR+dt8tZrY2L8WKZLqnonF+Oo919N6HEiTLMNE+0/gKpl0UlwskNRFGXegOAINI0VRHXD/sHQ/BM7Um7DbVWZDW1LfJqHDdhJomzRr2t23tjT7B+iM8YqOrgXokdZgBzpsPGaBBSJw/1N+Aryq6vr+ccz9No4rvA3jrdRcBNdFFMb0nmujbJiqI0WMf8ir1RB8Fw4oq fv4Oa41T 3aGo2e3d4Nk3wRLAy5Fb7aRZKj77UcV24nUAPPnONkuyR1xmsyjxqY9bieiC/N4Lv0Kg8fSSemWm+4NgarGPIx7v+NJeA5/4Aq6gh+yYalIwp9dvIIUJ9eocIdssNLkd/x5eZS7HlPsDMZ2zqBNXnhKVmA0Zq9mHH9A+GYPJWZ6ceEx1xVBcP1PWm0B/UAJ8Au08r/3K57NxDgmHtMK9lOfo7pN5FpCvn0maBGVC5nN2eA3iP/xICViH7fD9MAn9zo5gwbzFlDi+xioMaLNV2Z7udPNMCUq0KSD1BfrUtXTbzDSUAk/Y460v6Z3fdrbJhw0xpVIsk2k2/m3HYYeSdlYimRnDYU9AwLKWhqLXTOOzxQPLBsEAujclFa+c6t2ENwl+DTosiKMfmTSB3aFJzebUUOQIh6QO5e3FddqlYADmsktgjPZDKawJv0E8uyB8KPkXfI5KIeV9SAJkOY9eAVkbuoA== 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 Reviewed-by: Liam R. Howlett --- 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 Fri Jul 7 10:10:51 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13304700 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 97BF7EB64D9 for ; Fri, 7 Jul 2023 10:11:21 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 3260C8D0005; Fri, 7 Jul 2023 06:11:21 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 2D56B8D0001; Fri, 7 Jul 2023 06:11:21 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 19D8D8D0005; Fri, 7 Jul 2023 06:11:21 -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 0932C8D0001 for ; Fri, 7 Jul 2023 06:11:21 -0400 (EDT) Received: from smtpin30.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id D06C3160D47 for ; Fri, 7 Jul 2023 10:11:20 +0000 (UTC) X-FDA: 80984398320.30.1FA9C5F Received: from mail-oi1-f175.google.com (mail-oi1-f175.google.com [209.85.167.175]) by imf23.hostedemail.com (Postfix) with ESMTP id 0A9F314000C for ; Fri, 7 Jul 2023 10:11:18 +0000 (UTC) Authentication-Results: imf23.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="PH/CUggz"; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf23.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.167.175 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=1688724679; 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=376wTeQ3MEMNHnxgt+OCJ0TDActL9tQSOLamj68yJ5U=; b=RnOrlkiyffA9VkvULHU3ko/lYzIoNnQ7BF54xokYl4W0bNJ6605h2xCAZrzEtQqUjqFA4g K7ANLRPkQAFIvJScDPbIfbXIUTzu1ezwjuG/U4KdXeNnC7PLmhBuWK7dJnpCadzPIevE3m PvcizpbmOXihjSjAtbAo2CZu39lO11o= ARC-Authentication-Results: i=1; imf23.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="PH/CUggz"; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf23.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.167.175 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1688724679; a=rsa-sha256; cv=none; b=b41LELVgUnohIoQIiyqmSrwwYxDW25yesh5N5YrE/MjuqJ/enXap+DM7H2PqBbJb8J06zw K6kcprcJVplV8A67WHs0O90bumkDLkFX2RGlDJyeA8ByO065LsXSs7GmipUFklHkrsj4m6 P02zFEn1PDhnD0q5GurLkvLdphpxnMA= Received: by mail-oi1-f175.google.com with SMTP id 5614622812f47-38e04d1b2b4so1462639b6e.3 for ; Fri, 07 Jul 2023 03:11:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1688724678; x=1691316678; 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=376wTeQ3MEMNHnxgt+OCJ0TDActL9tQSOLamj68yJ5U=; b=PH/CUggzy+Hxz5qtH/dAxeLKw8S9A4JGuhCxm6hb0Ho8ugH8PNZPXdHsNK/dF3dXgb j6aJl9zqPLPGAp0yGJXE0K3vu8RluCKZlgl4NGeIqNSGN8HJZn0b19LlAKncVwYP4SSU VP/hrp0Tvg4zU+zYj4sdffzcqwQV/Ns5I2BhsH/1gU23wwSEka9ZxHnVAbJ2y+HtMRDI dW9Tpmv/4fOobkulXGSHkUdl3dPtG1Ti2HrYQtwhoxgxdjnm0RCcNJIP5yxgrMlY8rV3 a9rOZaQQML7Pd33PczJIEt2/kZ4Ypaz04/ehaYYH+NkctzWpjhoUMuPNQXxMCNi14HgL mdug== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1688724678; x=1691316678; 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=376wTeQ3MEMNHnxgt+OCJ0TDActL9tQSOLamj68yJ5U=; b=FRQkqtBaTve4132Dkd/74zhoxbC54ZSWrLs3vjGdve71wYMPh0Ylqn9zrWvlIMqoY9 by6HhBlcvqXvWvYhHyQdCG1mOluKmLZVBqNPoCpdK3dE+2BfaFj4z2T69llhPlpC19qz aP1mOY9gh7/tf8iDDphh8LHGPMHQIGfjNeo0n2Xw3ohh/tQdqxz0SofHG9DD48ewI03h 68fmWjoq3j2z5Ug/plRfgu9MaHMAjp1ndb7/09wHsqMPZh1Z/l/LhIvBoN0rPXqUxzPa GSBDH/WfxMqg7zE2QExI/jHF+I4FIVqSfwFCimK4BnR8SNJzAiGc7QLr9buk101C1pIb 4Q3Q== X-Gm-Message-State: ABy/qLa4WsRnbQUn2jT5v+gHQNhHIS04s2+PKFf9u0kaZfcTIGaDCuuz rGckxU35kBM4Q30iNk1cbC+lrA== X-Google-Smtp-Source: APBJJlE96i/YYNYS+fT4KqAljST0vit2oDr5jySn4ZcFemFzRqybxbcHYXwxFe67VUmmDE8I/GOxMg== X-Received: by 2002:a05:6808:1496:b0:3a3:ece5:83e0 with SMTP id e22-20020a056808149600b003a3ece583e0mr1237051oiw.26.1688724677972; Fri, 07 Jul 2023 03:11:17 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id x11-20020a056a00270b00b0068288aaf23esm2602549pfv.100.2023.07.07.03.11.15 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 07 Jul 2023 03:11:17 -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: [RESEND PATCH 2/8] maple_tree: don't use MAPLE_ARANGE64_META_MAX to indicate no gap Date: Fri, 7 Jul 2023 18:10:51 +0800 Message-Id: <20230707101057.29326-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230707101057.29326-1-zhangpeng.00@bytedance.com> References: <20230707101057.29326-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: 0A9F314000C X-Stat-Signature: c8eug4kxtdcuinc4buwrm1efwcrfcw6w X-HE-Tag: 1688724678-256310 X-HE-Meta: U2FsdGVkX18H017LaGj3Z//MzFIfwQWM0Qs5XOjK6+HIttJ7T2Idj2YVWs+RAuMsL7o3+aY3DocAfFeEqYWWrcKf+cFOxRoJWvLInVHMKPYgv/2Wh8nIAgGRgiS74AnWGlfVv+27vm90QOD2bqG/4wZM/EPqdGXDFW9KsSC2Dd/AJtdkvu17MOCR9Q3TAzB5x/KoyiljaLV9vt384e4D9fiqO6vlUIDsRSpxst6eLyaX2xcOH7BP5TDfQMXAe/GGyQGtmK4ECsNiEoJxg6zFbzSW0jd3zjKxNuPU6dRVvwKwY4mIB3oSNRA3Kk5fpaBAZMzfUc9PF6NpJa796rRQUWqpi/f3AqUPFuZYveubwqlKzr9RL3PvD784Y9BY8HQEftj6fHoRUnsrJq0ethEb4e8bq3bMC2V0JSATGgn9DWCWmKNpDG0z8Ylqcp+qtw1uNjwiSOHbUvZelhQXjR7spmhsNSxlVBYTfNd93zn1A+A/D70PhMjXMaHzE0G8GKrgFv1mOizEB0HRrzgnZYHsap3kEWU7bvszHaEKWty8up9QvTD2+SOHRu3aTvmMs3g8vWuTC9SDIzI2sXORO6YFIaQSjGqRr6bd1qELhPC+4wq5S1Cx22b/SKUvn37unwBfVEtRUjzDVKHYqZvM2ppObyceypOw6GghD+abDZ8gd1T4aY+ffpSy8nnbI7j3HPAseTHy7OHAT4RXwhg7/NXGEhZaslUjoFPxaF7bTSvQYTA8jdEJuAaAB3l41RU5uHdPLD9Y2TiHuD7bcRzTns234IYekox1SaqjofoTjllK6DnDfd2v3nboXs2ST4NPktD8Yx34W2+vHqZKwn8MkEqU30rKPYW+HGVsge7h1d5zMsD6GjHPdfIYTMVAZ0RmrtqhleTR7zv5Esv/r046ZYf4O13z7laqrYsmwLfsjsmhka8eymlIeTqLUhiL2eoi+FG/SPk6if7Lb6FxhT0YWfM UeO67Iib gjF8yP8NZbvpY2KuIcNjXCB0qZWJ5Y0J4rEVN/Zv53LxwVNugb9XALWCR2Dz1OE/Y042v/dnfgHS0bWPEbiJEDpZpi7mCpaL2gSjGhgNKPP6YhN6gafliz5bUfd3ru4cTR8ILgVrekBS5UUIG2lJy3yTh4xwEHzsZPpT2sKaKqMBHPCKtmHGgBycdmIqR0VzPz43KHUv8EcqVc3Mskc0HvjSqx1jTUp4iwl4MBaj3hC+RwTu78Ja+ZnpUwMVYBurY/OtnoJ8TtHkA/EUCXlEsLPVglvKQwE4N2D76T2w4zzS4cLk9Sf7UNBIeS75Yip2Xm85z5OnPv+61sc0w/vZaWZC59wr7nbfdKkOD1l47QdZDLw92HGvjGHDeojCiTzJIOPZi+GQ97Z5K6szmvVVDxDsZnr0ZXHyl5an0wZ3TzugAv1nVb5uGcsYoLdWmLGKXacCnbBnQzSkaXvU= 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 Fri Jul 7 10:10: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: 13304701 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 6CB24EB64D9 for ; Fri, 7 Jul 2023 10:11:25 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id B639B8D0006; Fri, 7 Jul 2023 06:11:24 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id B12808D0001; Fri, 7 Jul 2023 06:11:24 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 9DB508D0006; Fri, 7 Jul 2023 06:11:24 -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 8ED528D0001 for ; Fri, 7 Jul 2023 06:11:24 -0400 (EDT) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 55AC0140723 for ; Fri, 7 Jul 2023 10:11:24 +0000 (UTC) X-FDA: 80984398488.19.EA3604A Received: from mail-pg1-f179.google.com (mail-pg1-f179.google.com [209.85.215.179]) by imf06.hostedemail.com (Postfix) with ESMTP id 5E116180011 for ; Fri, 7 Jul 2023 10:11:22 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=hOQ+fMw+; spf=pass (imf06.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.179 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=1688724682; 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=HNMajAjya5LH1cr0h8UcY7AWKYluSf3DNGPBuMzeW+I=; b=phKUgwRqe06WQ2v5mClKNKgzvVy682BrDNofb2N54RwSY/VA9iGAYWn/5rr/6biKpz49jh gSQ54mepR84ZPjNG9nyPqEmLAVO5AXEXBtp7Ffc0FvcDIxApzfuoqQo5Of5XeCT7DLH6PY vQWxv+GtOzI2KqrN21caQ6Goj2T+U1g= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=hOQ+fMw+; spf=pass (imf06.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.179 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=1688724682; a=rsa-sha256; cv=none; b=yyNykIffDaFUEvmqRL1euILj1/8ghXlBqYVcJtGqwfGk8iaQJDA+/nL/mTDymBafg373e0 R7bNvD0HJ7ZHSAA5O5JgP4vPPRq/+/1+mzSAG4y5yLZIlOSm4Mt1l/SfcLenqBlDJExXP0 afX/5ZTcwuQhHI5euqBBTEuY22TPd+g= Received: by mail-pg1-f179.google.com with SMTP id 41be03b00d2f7-54290603887so990852a12.1 for ; Fri, 07 Jul 2023 03:11:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1688724681; x=1691316681; 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=HNMajAjya5LH1cr0h8UcY7AWKYluSf3DNGPBuMzeW+I=; b=hOQ+fMw+BoiKkHf4LQFjJnXVHwgx2GGmC/dU+wccE2ou+6cHm99YqltRcJg7kqi77w zjJuucAdKRHBItZe1kbAqEj3SOEHXVqcT+vtsgJH9vPZ1sQHFHGQMUAd73UPZ+IuncE+ PxN6UdZ/JpdNDMEMv9hq8FfOUobjmEvmd0t1+SSb+rvuDL4J5mp6pm8ZeaTupFiAkyn/ 6NBrEumoORrpUSnZ6eOh0MaZQltxZBWELIm9f4h7m4hIOFxH6pHCn/DAtuZ0RgiNSFCL 6GX4aHss9kmIE3DU40cuEcPA98gWIB5scldrp5GwlCikrV/AtjDreQKvRxCIPaVcO+Zd Ssqg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1688724681; x=1691316681; 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=HNMajAjya5LH1cr0h8UcY7AWKYluSf3DNGPBuMzeW+I=; b=AyTKeEYfaIc40GKUx7xKYP2IMERj+TkftRzLlczsNmlzsLrBlHrcJLq6iZWHeTqJ3s Ai6APbRqKPIy6KX7XGzU8Hfbuc3M3ep/YxSwbtmitZPEkpYwC7ZcfxLNduMiJcrVHsQF Ywro/gJardyM6WaiVnkUO4PvKbdB9gZ8A4ZjJ8+JqgR9123z4qTKyiIApr4/Yw0nVMGv 9P2V3kgXPdIpw+YIXumAk3hrbcxYcBF38vXBiEPa2XCLpkRg5fywijvkivX/SWzy+hBJ NB8MzDWAslIcd+2aveT40fiO8UlUtYnnj7a+zD013ySDUae1YdN30MdGcK73jCKXkseZ Xqgg== X-Gm-Message-State: ABy/qLZhrnrWTVt+xzEmQQcNWIJY0VWArJyMV3AjGQjdM1ErQMW9iTZo 705GQqmMOjPx2KhJK+CktddssQwzpVySf9qfxHo= X-Google-Smtp-Source: APBJJlFF6iwtClAEjjI0g2PkdpD1KpvblVyCvkJamsMfzMjqpTWoEpTSQSc6Wdy/cPKbmJxSQP1qIA== X-Received: by 2002:a05:6a20:d7:b0:12d:2abd:73f4 with SMTP id 23-20020a056a2000d700b0012d2abd73f4mr3051324pzh.26.1688724681045; Fri, 07 Jul 2023 03:11:21 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id x11-20020a056a00270b00b0068288aaf23esm2602549pfv.100.2023.07.07.03.11.18 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 07 Jul 2023 03:11:20 -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: [RESEND PATCH 3/8] maple_tree: make mas_validate_gaps() to check metadata Date: Fri, 7 Jul 2023 18:10:52 +0800 Message-Id: <20230707101057.29326-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230707101057.29326-1-zhangpeng.00@bytedance.com> References: <20230707101057.29326-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 5E116180011 X-Rspam-User: X-Stat-Signature: oqry661pbi3zpygk7u8fi4ibeyb6eq4d X-Rspamd-Server: rspam01 X-HE-Tag: 1688724682-291142 X-HE-Meta: U2FsdGVkX1+yMA3W32sjGaP/Bjc6I7Y3xLyoc+InVkhhk4lCVyov+6a0QwGrnhZySKEigF5/jvrR5Xp2JbAX6kfA/s3d2AvR7UKigLrxkDU1FPjpGxfrdgDE4qH5fCznHH4IZpJRDJbxrNx8luxNKeSc0Cwrxbe8UG9nrmy1gCtW99DiUdq3filxCn/qPSvQw+zg1rYygghslNwCNtBs2/5XUQkssbfb1QlQFxrLLLtnRnmCnIFlBE7IbrA6ZFxImXHoew0+0mOJe/sQRZfdMJe4kCSUNWmD22jpJYHcrBg14TKdm509sM2FcMAD/l5Ix4uKf3g9IY7b8hrVotumlbkrzqoMZjArZHzl4Yf4QVdg37HjVzu+0ZEGN54U3zasM7imq9ecZ6fzJfFtHTp1lswDXRgABkdCjUNrRvvwMA/2HSBHu3XdpVSzxQKLLdF6M+93oEeDdZORg+hEIuC0t3bnM8vfD0bdtzeb5oVgHz3nQKGozquV1L4kYwhzt1T3E9QZiq/e81W5qOy+kuVwsaO68bGm11NBn8vSJR9NyffMiK4gKDumWvdxUkK6HrBvIgXfglSFNpdFRf3sOowQXtlmRiCD6yuyh3q5f/M98KRgHYFKdqOpU1b0IB7iONiZUozbjhRNDD5wy/p7FLnfqHq0IYxQmrfDc4/B42Pu9QiCboKWm8qyFW1hARaZLK9Zg/nIkvS1YkJFhR65lOGLxT4J/+gITlDNJtPUxRLjGMzf+5pW7ReiovZ+yCZep3VYETWi4CD8DWn1A3YA2b9wkHm0C6VXfNJjQVz5qHAbO5nyjJ/+3gYgq+vKv1LMcAyaRKyvKHekZnlqQ5y3psLW7GRNEmZ3OlTTgm8Zk5TcMD+je5Iftf1eGQXhUoOhbbSki4NNR6LGIR7DebriZXkuTTFKhROeoCs+Ad06vxRQ5sqxOQsMO3aDJSeftN7LsJK1LErgXBTN9nrPKf5CW3N ndP/Uaib nIn7UdhUJM95OeNbhTT6zfqpA1PnBi9O8hlyIm5b5a+cyTX9WkpKrVKsKCXu+LTzrnTTVCgI1SF09b4poY4LgrpwyQC59LjRwVZJHCoVhD4E/A//X4d25oECrUhus2iWaOedzYKgDXhIaQeGKdh/V4wfjPyUpOQFPJ8ofl32LYc46legtIh+gx94IR3Sm5Funpb2eYhewrWYYoALzWRURm+s+Lq8PuRtTKU6SpECSriomwIW7Gkg9YldD4xfjtjeTXxQsUp5pQpjk3tfuu789m8J6FCVmL8FrhJKqcEha2OIzt//RuOZK0JheS5S6hIFnm97Of/eB3ll2URTeg14LLztxfb4PmAkLiLq5h+2JZcEQipnwmGUWy2bJOcb0XKdgP+gI1cZmmtFiimGpdtudgby6G3x6p42+d8C03RLOsXcBQitZsGOYBn+/cry64bOP/UVyXVqzCJbofxo= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000005, 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 6a8982146338..1fe8b6a787dd 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)); + 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) @@ -7004,52 +7005,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; @@ -7059,10 +7059,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 Fri Jul 7 10:10: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: 13304702 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 D2812C001B0 for ; Fri, 7 Jul 2023 10:11:27 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 548798D0007; Fri, 7 Jul 2023 06:11:27 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 4F7F68D0001; Fri, 7 Jul 2023 06:11:27 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 3C0478D0007; Fri, 7 Jul 2023 06:11:27 -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 2D8D38D0001 for ; Fri, 7 Jul 2023 06:11:27 -0400 (EDT) Received: from smtpin22.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id EAA9F80D22 for ; Fri, 7 Jul 2023 10:11:26 +0000 (UTC) X-FDA: 80984398572.22.3F00655 Received: from mail-pg1-f182.google.com (mail-pg1-f182.google.com [209.85.215.182]) by imf11.hostedemail.com (Postfix) with ESMTP id 0AA1D4000E for ; Fri, 7 Jul 2023 10:11:24 +0000 (UTC) Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=QfdtXzib; spf=pass (imf11.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.182 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=1688724685; 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=VE13/bSU+7HEsPPuu+3SI81hgRU4W8DBIsnfpeEf3iw=; b=R0zhUrUw7cz3N/auA3Xy+wDA/7zxI6PZfLtFgj5zIaLLu5SVTDY09m308t0QimBo/DPv3W /fnO54QLLnNBWuNGDRT7e+g6t5G78tUTE1YkXF7FKTbuJPU8WPUTAUHSUvGVwHFiGYZ39n TppiE6cag8mMjAVMEVeeJD9hpwxpiX8= ARC-Authentication-Results: i=1; imf11.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=QfdtXzib; spf=pass (imf11.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.182 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=1688724685; a=rsa-sha256; cv=none; b=3c9D+q6hR5Q5tiGQ2OCHByzzhqeAGiDhObdnSqPoqw87CjZ1EPzQpgYDf0IRCKoCk+y6Jm k4W7uFgmZU3gcdSrDnYyDHzr6xjd5iBQy3lys9nmVHU94XIG1OqCgNPAa0MM1tAeVvxeDh boNxqx4UgCOq5zdLf97ARBEZuObSRM4= Received: by mail-pg1-f182.google.com with SMTP id 41be03b00d2f7-55767141512so985517a12.3 for ; Fri, 07 Jul 2023 03:11:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1688724684; x=1691316684; 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=VE13/bSU+7HEsPPuu+3SI81hgRU4W8DBIsnfpeEf3iw=; b=QfdtXzibF52G1Tv3CudmdGlATyS59CcgsOu6Yx2koGrpC74+8yd+xWT7sFR6R2XDrO gLuqLE0iQGKZdOWHpMCvXK6wF3hpQJ2EHnzTEB5S7e3pI8W8gv7WPZ8DUDfaaqwZCOuH F4h98U2DmLpnD0IvL2M9FbjL0G77/y888wjKbLXS79WcMX/Ga6KUkSkLCB+PHy7ZStcX bK+SrmMCjPox6KOZsAiGtXVXBFtJq1xqS4MTotYtaou3nIWhmDuwlDa0Aphz8y+ii/Rn dJ+t5kSMAr2Ep6yUvfN2iaHaXG3bEUMxRZPcbMo8BDViD3Yv/fGmVaamFhCuCeZcJ1Tm CXxQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1688724684; x=1691316684; 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=VE13/bSU+7HEsPPuu+3SI81hgRU4W8DBIsnfpeEf3iw=; b=feSAlPtE5648PO2UoZatf8VMs2+OQWdnjL9C9vl6jwN6RUGbXReHMGj8XKjl/1cgWd GI49xZSg6XvDj70GN/BW8fIAfvqFI6WqZdHFGZAMoAxYU8E/dHAEHPCY/yopsQrRvDxK mJm4MqNrjwMwJdFzDfcLFMfDAx3svruSIFMR6vLL3zYlzgqSBqY5PL/z5uCbjD+e94TK R3FODkt4ATjwNFO9ovn1SDGUHBITNFhashtM8YQewlpcGIKMJ0A8PZVhjii/vDoazbPU PAymDJCjRrVqVvs7fUDC18fMTjrVUeikM2aHTmGn0ZXV0EQ7+FiFJXSimRMRrL5iNghX D37w== X-Gm-Message-State: ABy/qLbqU0KS2sNaQdhdi8NZ69Bu/9JuQbLGT+DsnnymH8MEBlp2QIGq m++PWBc6gzEcJZtZh+1KJp96HA== X-Google-Smtp-Source: APBJJlHLtVaSHtwyC+RDJwQld7xxpdLz2jT4V8stnsV2QVLZYFcHbHnSXhSnU0cJ6Mez8qp0sxmKeA== X-Received: by 2002:a05:6a20:3d8b:b0:12f:952:11fb with SMTP id s11-20020a056a203d8b00b0012f095211fbmr4370514pzi.52.1688724683859; Fri, 07 Jul 2023 03:11:23 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id x11-20020a056a00270b00b0068288aaf23esm2602549pfv.100.2023.07.07.03.11.21 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 07 Jul 2023 03:11:23 -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: [RESEND PATCH 4/8] maple_tree: fix mas_validate_child_slot() to check last missed slot Date: Fri, 7 Jul 2023 18:10:53 +0800 Message-Id: <20230707101057.29326-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230707101057.29326-1-zhangpeng.00@bytedance.com> References: <20230707101057.29326-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 0AA1D4000E X-Rspam-User: X-Stat-Signature: h657bxawx69o144663ez6x4pz5xghu6a X-Rspamd-Server: rspam01 X-HE-Tag: 1688724684-816180 X-HE-Meta: U2FsdGVkX1/mi1J0Q3N+Vpmh5pfngfBQ3lCazL+TpZBcKfx+JLxkpJcq2mnwf0XuUDD0n5F7Zljxxgbfdja8UK13i7OIgGOLnC3NQgs+50DQyeC4T2uOieU0sFa+n7lydqhnBOy5u9NO36KqeCtAQOey9zAuN8S03Vyg2oqan9MxQGI74YURyXbJbXT68xOSa483R94AbUBs+KF+Q6/8cNwqE+RlW7M7mHCSVjrz1loPNUKaJUX1L0a6iBLhHeu24rzx+4TS7jzHts6FK3HPIIa6WCXKXU5lJt8o6Hzf0/4ryw05T/cGAWKp8ymbGcnx/nRpQgkV2U+xIzsaYqGWgCfGNSrJdthB+80tF8JmjBba315wH0aL1Oy3z1SAXGeAG41L9p4rmlgQJPjkyaPOT/l4/yP9ZxxSiZWw/wlYJdY6DvTwxsUH3+Iz5uBthrs2BoKkBNq2e1AQEIj3pPY2LkvAk5xyE//UIMnXi9jDbO/lq86K+51vm1KIe2QadXe6rLBh5zoxF6M4DknnrYW/2pj/wQ3oQjV9qaWEgkwlJFEnvbT3YEmcrwBAIGjH6eNY0soSYK+9lIY+HIt4nsdECEzD+rJ35Xs4jcYGublzsRsEaobYt/zNvg9bJmgMw45fDX84qxcnRQiZvORc93qkq2kMuQFQhbFavWyhszeH735/JvYiXLMDzEFj2Tw3OdOjrQb2hz+JI6N2Ult/zKDj75fiYzqJjcuXLamwJHiKoqiDZKblZnw/x5jScrcfgIgU25RW5QgIqL7PDK8bQDSxhIBfSqg1bS81gmwV2f/bidfbN0vqraHtK5jb75fqYtSXv+H9U5bczf2mKIYKdeHBRyshIdIUSgm/GmHEZfBidjEY8ok1idgp11H8/GDD3qWO6Xnz9SjsuyWqvae+cgtrg7KdiEZ0hTclojm0ooruovRGlHx/3IBw5dhzZ156EUFaFyB56PD7RC0Y7nPv3Ga +0PRqDL+ DNtrAKeV4b4j3ZyOmuFy6znKhOVCeIjpWPxA4C9/BOomku4MrA3DAbJcVq+Zs+vOnBbnfsX3r6n9D2YbnxhuoGOonxnydjFchTSi1ZL9RhNPeygailZg7UmnmzauYGCy1ewh68vmVJAitlkwIXdqNvUjPAZePTfy/91naX/QAx3LemhPND65Iw7+Kzjh8mqQZ4VFYUTP/A36gQknOQjGBlv2zG5RdPa1UGHWOSmw5d0Fd96GBYIT0x7RrtRQruHi0ByKpQ8kps7i8cIeM5PKJYfZ6H2DS88R6HSkK1Jrdq4onwp3lC1z2YpCP0FkSaLb/SBNcacuA0ZLibj6Prd0vPXzcoOVAfHsVSv3D6L/isOdVgAqTEyGY1JhwuVx1JqnnM7cjEDcnGXX8I3Auf/pH9Isbf40TTHaBkXVu2tV3jpXTf+8RXQtnJGhzGEFS3Tjn5qBQbuyCoDZy3kDiUigWkN5EFGQyB6Zs2qbFWV26knwgfpa+Wq6akrrP1g== 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: 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 1fe8b6a787dd..88d6373f37b0 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7111,11 +7111,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", @@ -7130,6 +7131,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 Fri Jul 7 10:10: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: 13304703 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 01F16EB64D9 for ; Fri, 7 Jul 2023 10:11:30 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 919198D0008; Fri, 7 Jul 2023 06:11:30 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 8C9E18D0001; Fri, 7 Jul 2023 06:11:30 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 769C28D0008; Fri, 7 Jul 2023 06:11:30 -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 690948D0001 for ; Fri, 7 Jul 2023 06:11:30 -0400 (EDT) Received: from smtpin18.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 259971C90E4 for ; Fri, 7 Jul 2023 10:11:30 +0000 (UTC) X-FDA: 80984398740.18.E7B7B47 Received: from mail-pf1-f176.google.com (mail-pf1-f176.google.com [209.85.210.176]) by imf05.hostedemail.com (Postfix) with ESMTP id 17B88100019 for ; Fri, 7 Jul 2023 10:11:27 +0000 (UTC) Authentication-Results: imf05.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=XtBGxnqT; spf=pass (imf05.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.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=1688724688; 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=RsMt13COde274ttCMoaZF2YE95cjQIf4f286siNaW/E=; b=UNDZbDUAAinOH7cQ11cdtopv5OV0mba6PScQ5iVoHDQC3T9BqEp9BsXHiI0N553R2Fnzif jnekh/OObUBuRGwsx6w448BA+DcDAENxYBVfMRKbfbdkz8bf8f85Zt6oYertTJ/APsAiPG N+m9LhVZVpZ1JoV35R2lenGUsbAzgzc= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1688724688; a=rsa-sha256; cv=none; b=SKAQYDXSbYUzJ2mvGjzpaiDQDELxEM2OJ+K/qGc8+SVgbO0GF6Vy3heF5ApKwQEI0981rr wqefKMAJvA2n/PkoEtduoutEaoGt2W67ZfqPxP0cV2B9P5PEFRtEPz0/mL1Zx7FRXbLr+O YTg4JsZrDPldh11tBed32JCeqadTEKo= ARC-Authentication-Results: i=1; imf05.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=XtBGxnqT; spf=pass (imf05.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.176 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pf1-f176.google.com with SMTP id d2e1a72fcca58-66767d628e2so1305762b3a.2 for ; Fri, 07 Jul 2023 03:11:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1688724687; x=1691316687; 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=RsMt13COde274ttCMoaZF2YE95cjQIf4f286siNaW/E=; b=XtBGxnqToLGpm+wz6UZHE9Z3Yyxmjqg7q/72evlzQgOrt67p/JLRMjJAMrFv64XiNW ZfNIFHx8T6s60FA+P6V7/qQ/4y1QQs0E/n5KE/7dmVz96wUjBNbODxKCxTfFaJ9jLt2H laFNuDh3JK1SqIMoLaYkBZW1pM75vCISZxsvdxkPotXveDzGUwaBGWVWnIyP7Z0I7RCR zgII0JY9Fk1buneVD/uJGvPj4QSx+CBBeH9ivoDSr3ms/fjZUANEfKwaROGQINSOs2Xk zQlMEdoB+G418aYhQibOq/MhMhBWs4Saqurzw5bMTc1VTdZiJ693s6MQD+BFBUaoxYYe 3QuQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1688724687; x=1691316687; 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=RsMt13COde274ttCMoaZF2YE95cjQIf4f286siNaW/E=; b=VeQgiSajxSfWnHHzBG4/vMzmXnNEKKrs1ypCcMNcru3jhORyH9NPgOBF8NHCsy5SA6 SYnE8QGNlCcG2A+Li+ozB5MX/bz4xbz3wLLT/jENJP/LtyWj2NAmp35I6HPJWssfI5M9 qItnsdVXw9tIbnzH92rh/Rl7EX2I1m4st911SdLsDaXfcKBREOGthnlYwZsE+816Xc3f QpKChJh/lJEo1tCI1wpvOgpyU2ShQg0M6HV5XwMTjeLSwn/mNw0rGXhBCu6ohi55e048 L5V5Yk7+wPgY1/9Gaxh96cMc9+wgZbsdttURNaYy6bAIixIOxeY3F5OWGlqB0HzGNiM4 fBMg== X-Gm-Message-State: ABy/qLZjafttm2QGEkGR3/bub1sxNPOeWgGNWMjxQ8guvLIYrlIBC5Ns PrQEJwA+9SWId94BkcLPBNrE7w== X-Google-Smtp-Source: APBJJlF0ImEh0lWSBujHgiGl3Eem6V0jD/6IH2Qzj54mjY4tPYvtVOMeeD3PwEtW49AKgrd4d9B+5A== X-Received: by 2002:a05:6a00:c89:b0:668:711a:7d93 with SMTP id a9-20020a056a000c8900b00668711a7d93mr4048082pfv.19.1688724686695; Fri, 07 Jul 2023 03:11:26 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id x11-20020a056a00270b00b0068288aaf23esm2602549pfv.100.2023.07.07.03.11.24 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 07 Jul 2023 03:11:26 -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: [RESEND PATCH 5/8] maple_tree: make mas_validate_limits() check root node and node limit Date: Fri, 7 Jul 2023 18:10:54 +0800 Message-Id: <20230707101057.29326-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230707101057.29326-1-zhangpeng.00@bytedance.com> References: <20230707101057.29326-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 17B88100019 X-Rspam-User: X-Stat-Signature: qt6ukea3r7bcsz9ptbwy3d4teyu1s6dp X-Rspamd-Server: rspam03 X-HE-Tag: 1688724687-50026 X-HE-Meta: U2FsdGVkX18jZq1h0LO7bog6DNdkAa0FUvyJpp5M+8vmsP8T21EBQjAIYMpe3ASdQi0+rNJR+MP+k1dy6EZP5loaw9bn9gcC9Snc84yF9fqfYgKB+9nekj2eBX6mdicWd2J6qJaumxz7VEslXsx6k+MnTgHCqLjbN1s0OBgwmS5QIYffRQyAnnl91lOSxVj273e+gLei3YnZy8Sx2FDfa49gPeVDYNTeFPZ3D76O599hwT6sxT/JKD+WNvzWFrs3JBdSs4gtbcWEU+Q8fu5dRDw1CrZ71+zcH5IlcbFiacMcUiFXNhz4B+TerKgDQVKaeayf5ZWBmWIiChsbLTv9XDeTo18aUu3sZvz/oNBG0Dqh+08zz4OhlMqGTc0m0fyS5o8TYXJqDFtvrMs2syrdl1Aj4THmaaUczA7ForFDdEmkUFII1a7rqG1I+k91ME3Q95RJWJK8hRSGEjmmxD8cXaOc7WiZn+GPkmgWq+Q5h1ZWRoRUyRCOKj3WfMMb6liSh1Y3CBCy0nKAFiY58a0yZ0jmGOAEufTbxAq/GifCsgiB2w+RYQG8aWxCawG7CE4CloNZJ5SDmW/SJKiC0T03Kd6JbMuCTCEXO3UlJsyjYmipTolH6K0ihRyuiMX6fmm0KQTOfIBL2x0Wh7iB35SyMGrqLvI+Tm5MfxPVVL/CsuNnG+fvIvcRBzAKEiH+FnLvUMZBZvO0R5N2z3uwzR+vxaMZmz4K3Du/QCPzTmiug7YyzbeaIrxJ6N3AIqOprNBqBAVK50BByqmRohjbQabyK071jjQ9KYIz4MZssryJBGLNvWojboh+JpOidiBp80JIwqDJijAM6Qky+DLE797x++uzVnDpOzAgsyRxUIBxjVGA2+BaXG4P1td0rO5xCvSQTc2gHo4VIdo3XDs3ncKK8OhmGEJYJ6G2FaeaOTbGlJZPZbEsWbJcxQB756g0Mv4y+jSN2dU67wuid2fuJYt de3KsiMo nQfTBzYS6X86hFQGmMmTBYXmkrsqYekz37nbnmrPlcEY1+e4X6LgINIHNUfAZskFNPsnGVhjQuDtF+8Ehk+EWRq2Ia1DUXrLHw3roq425WPOqrMT+HfLEqH6krpjqni48BdbtDungbKdyOpsLVWChzxI3fgcI/amrDtUmKYxZZk8g+jhon56rmZ4QV0SVcMKswhztNxKclKkCSDvXROr+49WL7ojpi2r5ghO50GLbTnlvTJB+E36fEF8THqYTIsGsSkTWoSkiazQTJTPDjSVsxRUue0GepDSjTdruFoQWHNAAtipALBCBVWBYYICR5cQccGNutM+2NQobi6M1MEyB1VvQL08bvrz/4TIuKGijljPyDYgGMIMmAf7gI2x3V8IWAFXeT2/R2PMnv6Lih/wiwo+rMmUcurfAaV4nuJyizTyPV9vHBnrJ6nz7DdxvRJ/zPLGGcvtQ5AACWkY= X-Bogosity: Ham, tests=bogofilter, spamicity=0.002813, 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 88d6373f37b0..e84a042b6d84 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7148,26 +7148,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) { @@ -7190,6 +7179,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 Fri Jul 7 10:10: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: 13304704 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 BEFF5EB64DA for ; Fri, 7 Jul 2023 10:11:33 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 596D88D0009; Fri, 7 Jul 2023 06:11:33 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 546108D0001; Fri, 7 Jul 2023 06:11:33 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 40E538D0009; Fri, 7 Jul 2023 06:11: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 333F38D0001 for ; Fri, 7 Jul 2023 06:11:33 -0400 (EDT) Received: from smtpin16.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id F31C9140D11 for ; Fri, 7 Jul 2023 10:11:32 +0000 (UTC) X-FDA: 80984398824.16.00A71A3 Received: from mail-pf1-f180.google.com (mail-pf1-f180.google.com [209.85.210.180]) by imf29.hostedemail.com (Postfix) with ESMTP id 109DD120016 for ; Fri, 7 Jul 2023 10:11:30 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=B8xF1e++; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.180 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=1688724691; 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=gEWeKyXLPJ0PG2fEoqETtxFILv9OUYojo6yQ5hMHc4U=; b=2jiyX7d9z2tXdx3jmxalofUX1wygBMK6ID8SYobchXTWJ09L7LZHTnsvmJhisXbvjzT9q9 noDI3gWfeBh5EqwpwAJEqmhueHyY8xK83cJqwW2ysyvvB6vWpcIDC/b96+RdsfTDE/IoVL VAVgfGbjeEXHBJYRZaIM4GFj+daIOb0= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=B8xF1e++; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.180 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=1688724691; a=rsa-sha256; cv=none; b=AZB2l9wfVz/V26Mf/yjVpf2PKqyk+LhxMb6ZB20jItEi309APC4/VxWl9UFVrcPYw/8dlB XOnXFk7dC9cxIuVd01wvFak5FpcNJ4Vy6XMfPrUVzIGckB7vLXkg0CuQ6CqOMujbXdV2oQ 4Zzj+VzXgpNzNYtU31Q+JjkSEy53im0= Received: by mail-pf1-f180.google.com with SMTP id d2e1a72fcca58-66872d4a141so1314880b3a.1 for ; Fri, 07 Jul 2023 03:11:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1688724689; x=1691316689; 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=gEWeKyXLPJ0PG2fEoqETtxFILv9OUYojo6yQ5hMHc4U=; b=B8xF1e++nc2JK5igG1lRrToeULOMcAypzITpfCyb3DCd4SKc70mSmGIhGIi/STBaBr gBsxzOdvx9mkBv/Ex6hKK5zFJLPo95GXk/dAhn3EvyNMXS4KXlpYbQAoQ9fjheogI6Bd u+/ETK4yU9jnqi6x5oy7p3rJOucDfsIw8f6c5CvVIesOTy+HlQ+llHxs1OrSz0U264RF R1pkWyCFzpZSWlkDZcJgTmZtvNoALV4dfXycYb71T5oLvbJxWn8lWTG2UxBThp9YYMd2 Y/sZsvhpeX4GTDWL0T5EOc5HamZodxSPwyC07+vfSEzCLmJCLFRA+UFBnLZti3OkntdU i1qw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1688724689; x=1691316689; 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=gEWeKyXLPJ0PG2fEoqETtxFILv9OUYojo6yQ5hMHc4U=; b=VDhhkLc7K0nOQ7CK+qV1WyV5tMjqACHBOvCE5WjmJtuBQcectvdb7cikegDu3uO32Z mjeR4wf6IIIp5t4Y3eHGdTJcISCHbnA7obZ1f4enfYzu2/+7sgz4Gw6v/IWm79XAvxaC Zgwozb4WsHZPlde3PmW0f0UFUL5L0vCZKEwJFwhO8aVHy0bWM6NRS9cbltHfxrhWuo4l eZ0aAZTNsywGuiIGq49ELJLJGWlJQmWmXmHlHKL8bwFp7vjZKKpyK/w7zgypBTC4Dp/X oubM0XwV2M2/uQpgCUPclNYbRELlCL8ii+i2jHSjzIVRJ+abn5oAykJMJEJtvWH81dWm 2vKQ== X-Gm-Message-State: ABy/qLZ6n02kTtee4KmomaW4UdaS/46llnt1rJngnlAREOICxq/iWav0 uPvqQ5LJ7ianYJZNg6cgbKtreA== X-Google-Smtp-Source: APBJJlFWSdBdYSs8R5cKFkzoi15V1LLf8Zsq8gk3QkxoL0LpEY7Lxuhz5qgh7k49XyEoJowJcAMYbA== X-Received: by 2002:a05:6a00:1acd:b0:678:5629:fd43 with SMTP id f13-20020a056a001acd00b006785629fd43mr4104877pfv.9.1688724689568; Fri, 07 Jul 2023 03:11:29 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id x11-20020a056a00270b00b0068288aaf23esm2602549pfv.100.2023.07.07.03.11.27 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 07 Jul 2023 03:11:29 -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: [RESEND PATCH 6/8] maple_tree: update mt_validate() Date: Fri, 7 Jul 2023 18:10:55 +0800 Message-Id: <20230707101057.29326-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230707101057.29326-1-zhangpeng.00@bytedance.com> References: <20230707101057.29326-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 109DD120016 X-Rspam-User: X-Stat-Signature: t5a3y3epb7oxr5n3fibk7go8puyzfr7h X-Rspamd-Server: rspam01 X-HE-Tag: 1688724690-775918 X-HE-Meta: U2FsdGVkX1+THfy9lwvPuUv4p+aPYtGiubyzDVDdk0nVf24eyXm86k4YW8RcAE+QB2lLxuEE5twBrHWuf8boBf/15yT70Wz4rip+EcABViqBGvmfm+G8BSvUWwIiyusJzwda6EehhEpqYo1OIyWO1h0KnfZRlpCcQ7j/DonT2Ql0D8vWIQZzvxl1NRa5OxQknuI40MUAx9PzqCHSVOUi+saa4zr1/ixHpzMZKTWxy9J6NDM0NwYTGcE2mdVucdNsgUVxswNasHgsTadKq4PsYkPJF90MyQASVgAiUNli/yLoBRGEhtMpX0DjSdOcgk33ev8EyrrwHboRHi7UQjm4PBbvluFtt6c4Su72XBDPWLOUNrB30Pn6LucdpFnAXQaEdP2dETxrhmf+G7w3+7JYKYDUSwtxqT60+BQiHDFKmbCjhU22qQregKRVK2y2WnsqF22K/Dw2z3m7ccPBuRSCAJCl3WuS0bhcbM2jdWTHk2bOLCwtQud7eXNQmGJ9uFMDLkLE23lBwbRoTEhxLraS+r1X/Do5JgvaAOEpwTxSsvDCwscmY7+wx1cfjMRmdAVt+bW8bom0xRG5UtyrP6IMNS5ube/98kVz8s8BV741GVd9Xba6rV4QCYxlC7F8d9K6z63z5gow74APJAvlfmcI8V3XbnzMauHkvPXeoKyPPqG1RqdKzKALc7VV8UIzzsxKNCkB4tLTllawUYnP84Asx6Mqx9WbXeIQR3ltSxEuEsPE89zE8B9rCSeQbose47/jE0m5hLqkzKV4pnnEvl5D9jue8ERI7QB+aYD8pn0mWqGl/rxNfkaHk75P22EREKOwwLaOWwaIDo1TCdVfZwpPbJiqYm2EqzYpTMbkTcJgRKzav/XzCJT3SnRpG9Km5gzF8bHO6XY447dR+XMVl0gXWnEvZNLHOABFJhS+h5KkJ3RsID+Al13TUD5N8qvc6Ny1IyQ7eQ3vo0EkAhgZKVE d+hWfbZ4 9wipanCD2Y89MyY6lWzIR8TJuGD96s0EtkTWjrA9I/O/8fR7YUDCmH8Jfhv1LvV1Tbp00Hg8xhMc+rVaIvzTdk/54PwIKIuhsXzqJTFJT4O6UiNnrivq4ApZzZm/uAUkPaFHH+mI0EF9CWhXRsBHP9TiIQCUZ8s5KwpB/cDWLSqbsZHhuou0utCkdTdcOw7FUGkMs7n66sf6aFr9beWYqYZJxi1nDjadSvQ2Dr2JGC9FIV/qBhFAkVBiTRsApVb+lxjKWVS8c4dJNU2wGF2y/Ty9KNdVE9dpbARzRt4Wch1re/oeUNfqWc9Da4EoazoTmlnDilsZNdeT1+v2XrsaXLeauPbgyAvgVcVhp/wfqPcnp73TUmxRRYQwO8yPcPVPh3pN78zdkiJCpP0Ygwh/3XIyQTcMaNbz40R3K97d1CS/BI8H5nzW0ccc6BJHbvncB6e0xq6KJX/z/IrUVH0Qktxn1sg== 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 e84a042b6d84..3aede7deaa26 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7260,21 +7260,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 Fri Jul 7 10:10: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: 13304705 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 B2588EB64D9 for ; Fri, 7 Jul 2023 10:11:36 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4D2B58D000A; Fri, 7 Jul 2023 06:11:36 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 483338D0001; Fri, 7 Jul 2023 06:11:36 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 371F58D000A; Fri, 7 Jul 2023 06:11:36 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 291F78D0001 for ; Fri, 7 Jul 2023 06:11:36 -0400 (EDT) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id B6CDAC0CEC for ; Fri, 7 Jul 2023 10:11:35 +0000 (UTC) X-FDA: 80984398950.19.810FCE6 Received: from mail-pg1-f176.google.com (mail-pg1-f176.google.com [209.85.215.176]) by imf27.hostedemail.com (Postfix) with ESMTP id BF73440004 for ; Fri, 7 Jul 2023 10:11:33 +0000 (UTC) Authentication-Results: imf27.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="j7/AtuKs"; spf=pass (imf27.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.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=1688724693; 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=BaVLJjip61EeAZP607ZyqgslEXeB0JVkPTMnfDPq3fs=; b=z08KEeGF/68X6fyL90wpSCnliOU0eN4rJnTdE/oWyoPgIXeNfVq96l93uv6N/RUNN/6l/h G6guuqMCgLy7JAAsCE+EQ0mK18LaFoH9M3pE2tojUBBhXThB1ISUfihHUaL29o2noIakxj 2NfJu8fQ28Jw98mqJ8XUr0XBj0wZRdw= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1688724693; a=rsa-sha256; cv=none; b=Nkh2TMie6y1tzIU6iNv1ktEuCXlXYf3FNa1J6NILD8hOaeqmtMIOuAfe/mZRSPiYNJYp1i JpQZyhdZGqTs45msWSHgp6uYyTAGOiOve1bM4UW3KAkri4sA54zJvv1LDvEl6PeeMtVThJ Sdon9z7ucggG7uL1WZy/lCYivZVqL3w= ARC-Authentication-Results: i=1; imf27.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="j7/AtuKs"; spf=pass (imf27.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.176 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pg1-f176.google.com with SMTP id 41be03b00d2f7-55b1238a013so1216840a12.3 for ; Fri, 07 Jul 2023 03:11:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1688724692; x=1691316692; 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=BaVLJjip61EeAZP607ZyqgslEXeB0JVkPTMnfDPq3fs=; b=j7/AtuKsMBfQml5gsk08AByvKeWMYp3cLlXFl0h5wiOOFzwno2s4JDdbZz1gMZegRg rUPpYnw3sChLJYJ5e3QUubyJfUOyVs4Sxfwp3gXSItOXsfbv7HJPaQbn6gAbTh/ZPqaV ekyATJifF5X1WMznSIRLogfSQIfzoA/6iKyuIUHQvX/pYsVQrksJXosKt1koWCPqLmr/ 8lGymmUdBB5ALohe7dC4q04z2Xn9QetC+T7YC6d2v8+plOlEBZZAh9rLk8KoAk+MzKt1 xlBw08hirYh31Bb63VHYl8VtCkX8xxXIzIIfEDitAobM42DMTBKpybRaYKHBMuVy8Mty vQpA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1688724692; x=1691316692; 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=BaVLJjip61EeAZP607ZyqgslEXeB0JVkPTMnfDPq3fs=; b=cB/TyweTXuYvHaexA9DaLTufAl7xwcro0bNuNHvE1RkbGofAeVqctr8AvvVbZOtVnx iuiSp+pLL8h/lr4fD60YHVPKOk7edr/GU0EK/OPqFTuejiFB4/YkrzCdSkbOByIijO4v rsXmAAk7LPnW0fS4uJieiRQSSgUzGTs0Ms44ShDuQrr2WeC31FfIX2S0NQOhg6WP940d 9JVRyFKb7Efm2l+RT3iWIJsY5sVQUGcs2qApCX7SmuohjAedni6LJrzybsYZc7OrGsfy sDkTltnGVGPK/funET6ttLP04m+LN089UC1YPnk0ruH/JVR6oq0vc0hiQ9JVppL/LKMd vvhw== X-Gm-Message-State: ABy/qLb8sBuOty8r5aoy2DxIXYh0Au/oqPjksP5cZApjYCipRnco/5oj HxkOQP4mFqy5p3a8g6Y6v05ErBTkGR0LygalRTI= X-Google-Smtp-Source: APBJJlGcNKKZKkWKc1iP3UjBr/HMi0EvrSAMn7bPU1cexh4uo9XIVJnNzuQXc9KlBQEaQksmKfv7+Q== X-Received: by 2002:a05:6a20:8c1a:b0:12e:7fc9:5c44 with SMTP id j26-20020a056a208c1a00b0012e7fc95c44mr3641814pzh.14.1688724692583; Fri, 07 Jul 2023 03:11:32 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id x11-20020a056a00270b00b0068288aaf23esm2602549pfv.100.2023.07.07.03.11.30 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 07 Jul 2023 03:11: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: [RESEND PATCH 7/8] maple_tree: replace mas_logical_pivot() with mas_safe_pivot() Date: Fri, 7 Jul 2023 18:10:56 +0800 Message-Id: <20230707101057.29326-8-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230707101057.29326-1-zhangpeng.00@bytedance.com> References: <20230707101057.29326-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: BF73440004 X-Rspam-User: X-Stat-Signature: u1atdzsr9juw6brntgmke1pqnta7z3tj X-Rspamd-Server: rspam03 X-HE-Tag: 1688724693-508088 X-HE-Meta: U2FsdGVkX1/H18VXrNAwdo4WXKOYPJdjzOzOq0MRBwa1+rK089e7DvUbQYghSqniPo4Zt24jJxKdVI5gfKNEx0d7rwmPt7hYpgs5LDPtfBf04m1XYzPo7sWRXmU/XTfBVtigml4EzK8FaCBKjBGaZWyIJ3Sjm6SE5iTzM6enTHOtgB+BCrteM2sW2xlDOysEbgkZ/om8bM61pOIqQqi6EByVa65bt/KfdCwlde+1jKC/pNHa6+0Nr7Uy1o+O25ODbr/sVx1RnAn7PRdTmWFgxXxeLNqLUpFEY7reO/kchKGXg2VPL1W/RfXjKys+lTRB/aC3ZRn/M/+wV6UTiK8s6+PLjcr9ilsE/adnwb9/KzT8DbJWC0bNiI+/8rIABUmjFSxkTtDaqXJ4Rg9ucAIeH9Futah9gKPV9LxBALcpk3gvBGA45Y02LpOGOAhhnTMm6ZPF2/IIhTTC+7QFawesuO/w4TMSJcTKGXYAKw+zx+J/Fma4/ZiuD3g9L+F+XOmJGq7bWhivzkEyb4tYFuaYmhabmUa1Xh/f301NC39J4yQplaeyiFJthPmuK0Umn6vsAFmv436sMTpgrcLgF9ZyjCZatnCKu2w1DH/6aYqmQIS74T8ZHcIuzQdTlJOK/gQg2/5l7qRwraBesfP+KViS3fDM0lwezEFKbtW6Oaj1ON14oEJS46FPITq/4lgd6lq7KYiH0JwbbCb7S9+lwTWkXcAUZPkdRcLY7rnlpNIJC7Jd+h1H7e23RJVq1G+NfOebLx7iy93u/w2rRDW6pFPoNmw2xIDrH6Opj2YEFcgT3nItcs/XljllCmI19aMhRUXJ5Cwn3/hZuIIypyXQpzbUEWUwpkMMAH3XsoxbkXBZ9kKCb8HT10xcQxcefAJ5CIWt2DJsrxrNpCroo2y1Emy4Xb3RynggMHJxjSMWkzOtSb9NwMJYYKac8WzkdthQm7EeBnGurfNo/QvmNyOkSU9 PWkbejav CgMPfT7yHDU2kBB92OBmV4x4N0RNyDB+52Ct71kbrwrbmBKE7otUmai2/WsWrz8uPaM4wIRkWLkcUo7i1StiZRnIsDseaUZwRomTiT8NNRxNffsiw8ehfLVk66TjeUlWL3hQwwPaXgiRCpXr009nL1etT0neOLdgXBhWgQO4iyrNcDJ2TVAr1l6WUHEjVbSW8tfKnk06xD3oZ1jBgpXRiZ3yEPhIQxy39pgHdTcbBMROS+4vRIRXcVNOugxwZoGJTfiJPlCGwKsIUzffRg4KEpAcwvK/RjgJuvep68oP7w/rJG9G1R2O5+9j8YWeDCDQxlj++AfsnVQN2S2QboCtBSY9hFnEazllAVQyyT8PmryK2LKyUmHBSyZzBN4scOlbBPJWqnSVZXvNEgE8o/etKf9JKaNWd8L6EULWBJ8aYVBOU/mKCnyrHB1O2tQr/BSpxIQMH245C/bVx4A8= 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 3aede7deaa26..8c08bfdc99cf 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 Fri Jul 7 10:10: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: 13304706 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 95EEBEB64DA for ; Fri, 7 Jul 2023 10:11:39 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 23C268D000B; Fri, 7 Jul 2023 06:11:39 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 1EAAC8D0001; Fri, 7 Jul 2023 06:11:39 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 0B3788D000B; Fri, 7 Jul 2023 06:11:39 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id F15C88D0001 for ; Fri, 7 Jul 2023 06:11:38 -0400 (EDT) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id B8C0A404ED for ; Fri, 7 Jul 2023 10:11:38 +0000 (UTC) X-FDA: 80984399076.20.1C8D862 Received: from mail-pf1-f172.google.com (mail-pf1-f172.google.com [209.85.210.172]) by imf24.hostedemail.com (Postfix) with ESMTP id B312C180017 for ; Fri, 7 Jul 2023 10:11:36 +0000 (UTC) Authentication-Results: imf24.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=TwikCOYR; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf24.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.172 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1688724696; a=rsa-sha256; cv=none; b=n9kL6XJTf69Sgth5zF4X90r6f1+h4tkGMIKAe3f15ZZaygHKbjH5Do0zndbG1WG5ObTtgc aInfCcmNIuK5fOectlS7Re+VjJPpuQhfeJLEPFtCRhKwvgYiG634ikAPhYVqrWKI26gTsL 7e8ioS68HbPBhhyq/nBDpOaUBABmHUc= ARC-Authentication-Results: i=1; imf24.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=TwikCOYR; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf24.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.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=1688724696; 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=yY4TunAJnA6iguq2KmXgFYhvimBAhbgzT6svnqGIOfg=; b=45jZkI+LfDXSk2LCrBpqEIUtbFEDZjhZsKJSSwQxYXxMu5sHgj5szpZ8QWi1zd7ikjdIKi OfdQJgfoJcG8lgMWcX/TpPvzcIaMoTxcFjU6X2T1oJrT7yiYazFycA+8kf7VFk3wbBFtTZ tghWspYc5/L7VJbWyC0qPRrcyE6tdZE= Received: by mail-pf1-f172.google.com with SMTP id d2e1a72fcca58-666eef03ebdso854409b3a.1 for ; Fri, 07 Jul 2023 03:11:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1688724695; x=1691316695; 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=yY4TunAJnA6iguq2KmXgFYhvimBAhbgzT6svnqGIOfg=; b=TwikCOYRmU+nyw+rmp7MTLs8kn7oQmLYMUPlGa5onDJKbZD+caFPZZVqhYAO97Qaft QB6VUxVy1E8B8h4sze4YpSbZzy4Oq0Wi4aYOLBvH4+5bHA3REbmHK7K1Kro83eyWNXpD kjrtAO8mhRni83vhBplNMpN21fI0BmOMYJWKJCXYfaxGVMZ5jtGOlvcBSALSZYVzYoX1 Y81STm8yu1BFJk0KgM5I2K6Xad67IwG4ysqFRtz1xDKDJiYVhBKg9JoibVdVYgUnVj9V hOA2JFfZQh5DZ42J7yvDlEVPaiv///gb1Eef6ncsfg45HBtheJ83ejYQNVbFHuWsQVnA H//w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1688724695; x=1691316695; 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=yY4TunAJnA6iguq2KmXgFYhvimBAhbgzT6svnqGIOfg=; b=QvWUjcLXdyQ90Yrs9wHtuAfeGuzU7/QKtVf2x5Fk1vFnYSoyzeDezS3MC9Dt0yThRc mHwzj+TnlegW2PpJMuOqoGC2HisdaLqrrybP3mCKEIMqnDm3b1flfwWoRXbHVskr0Swg ietejbjpMoZmeyPRWSBlDE9Wm7zSKnfyU9r6pUiCi8Dstv2siisTW1iyfyZG/Ws86GTO SfG14pjkOG0kMWyHLKxVL/fuTF67tFTCkxA5/xwdzhUGLSVy3r5s+XI0I+XHYpPgS7Uo LfpeNtMP8ynIDkK1oX39JSy7udqa3whkG/6gaFNw4U6fiWSjdjJEdw/tnOpdnSP1wg98 sMnw== X-Gm-Message-State: ABy/qLaXhSdA2pIE5s0okSfwuFU/V+IIXsXOhXw+bT7vFO6kS8GVR+VQ 6/qMFb6PrIYyQZWZwl9i7Y9mdw== X-Google-Smtp-Source: APBJJlFjCMbAOzxsCyuIBwr6DxRyBFBt6k0SyguxrnyEO1kLu9Y/81oZNUcDOwMa+uQ985BVpNsqSw== X-Received: by 2002:a05:6a00:1409:b0:66a:613f:87e1 with SMTP id l9-20020a056a00140900b0066a613f87e1mr4556377pfu.8.1688724695433; Fri, 07 Jul 2023 03:11:35 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id x11-20020a056a00270b00b0068288aaf23esm2602549pfv.100.2023.07.07.03.11.32 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 07 Jul 2023 03:11:35 -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: [RESEND PATCH 8/8] maple_tree: drop mas_first_entry() Date: Fri, 7 Jul 2023 18:10:57 +0800 Message-Id: <20230707101057.29326-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230707101057.29326-1-zhangpeng.00@bytedance.com> References: <20230707101057.29326-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam06 X-Rspamd-Queue-Id: B312C180017 X-Stat-Signature: i6j47fcwchm6stmofcxa3rf15oc36qcm X-HE-Tag: 1688724696-871209 X-HE-Meta: U2FsdGVkX1/Yw618QM+OQmG2N1EsiKg2XaKoBEVJzkqPFFtLhaiMS/qgAu2UmZ6JOoNWe1rU0st+durQe2HyGKuKG9PUi9+tU4JNjAW4ntgDURWscso6e8urruLwu+DEGdRgEDtVBDjcBqsMnXY2BWcl7DFkhFfJPwj/obRHfm8c4wMQV5rcYH11ep2Ye2Cn8pV5YVEUTWIOyICG7M/qT5E9jsUdLGX1IcpMJWxCUU9FiTg7aQ0DZTc95hjhsmrxr3NW+jA9agVhoG0OzPWwtBhKccKLY8zcX4KRFymxh7iZg9B+DVN4yESRnSdPmgYCyfFcDWOGvUUky3P6xoXg/u0mlcytH5EtCD4jK5ekLvmEL6ag4KQv22MEhnSxlyCu3t/HJ6IpLVjd4cFkILi6EvrJVch4iXqm1187T6KpyKaBqsuxRBTcAFyjfCh6PS7g56UCPA2hgbmbmJpNDjqqJxUvHg/uH0Cb45MgjcMaOto95bQKaqMTq0QTpnS5OJSLiBFjrNKIHjfbl4AjXMgOy0ZozQ1c1/SjrUOJhttP6Z6J5sODpx3dPJsFCwrzgKzm3+NzOf5hPOZ056NDh+hnNZ559NKN5Pate+GfW9EA7k/1sqD8HAYbGj7tkTiDOXXwjDNXA6hEg39M1vrTKP27tQVU6ivbCkfWqjmsbBVO211UFka2sg0t7ICNqynFi7cGRTE5NH5gih5P1WC6wGSBFx5X8imzulFi2H2tYmJFaBgdnziRI9d8ShE7lrYgdvniPa+lf00LXbcNqgT3UpVUMpAIKHxDdHfWTD0Bj+tgHXdrVeyzNSgwzW3GniJcgQGNsiXPVZlAWR+jmYKXCtgFn5R7nm3QZfoIPJk16WOkpfDTCZmabF9/15PCSj3sVHk3TR17UB+Cjq3BT2B+k2gH/ry6xs6GXhrs9AEfNIpqw6McZt6o8RAOZkPSticquO0z0n0HAdJXzjzvK3aKe80 ZJ1drXju W/R/mFMbnDa/XW65hfpbGRBo7jhhGBd/pMWs3LyPtUbJiLR8FAvumRllcuB0BtEMcV4B2IV1JZskLw3j9D75hiezFnL424lU2q8GYkmgTMdWO7PsoiL/M3v6FWTc7YQGJHUkcQTcJnQvkFQULSxCZkR42ka37Aa8Ku69joqc7iNzNdIQmTyjzmicuI0oKVRz9MiOSqLudEbZCN80C/hrBdEgO/ouvY1pFyA/pBpdYZ/8527B6QK8x5bnoJKwGVA1lESG64vlokcU85iCJpDeHK+FV02SpOoqJR31os7kZvNmnV4ryTu5ecVXZmjmxqF0bRaWQwP9S5WN8HrKg/GDCN2TADyWEcQGtpRkY0IP+wE5ViIgZtuWUOEltkR8hkLbDOO3aKAK4lAq6nWEUt2sr8kxcy8xpvxasLsHjERx970dPdW5OMv6fqeDVibzt5wYCBoGnuD0M0ex50bQ= 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 8c08bfdc99cf..ad6810ed3231 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) {