From patchwork Thu Jun 15 13:08:52 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 108519 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp640350vqr; Thu, 15 Jun 2023 06:35:22 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ4eI7vHlXerNpbHYLgBhjd8opqowXBDryUynDaL14/4jk7EfFXu7bzkt8WRsHN9N/HcsXYi X-Received: by 2002:a17:90b:38c4:b0:258:8731:4e3f with SMTP id nn4-20020a17090b38c400b0025887314e3fmr3775178pjb.44.1686836121828; Thu, 15 Jun 2023 06:35:21 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686836121; cv=none; d=google.com; s=arc-20160816; b=fOMTtSDHOc3kw5IAuIpvRTrjdY0ABJYUP7M6ruzJssZONVS2J/cr5KfNVkfYo+bvz4 YhAV05/e9b/TC0l65O+baMKABTYDdqAOgSOoxCZi2WbuMLTM1Iu3Jn2LczGJ0DGAQObq pJ6tkygoNnVZPy9MqLrIj9P66MANtFFYrDhkWmLLT17B2ooP85Ree+Al4P4qc4Vz/lDw 1YhKfiyndnUSbiJ/yDvTw/EK3T7G0Q7aakJv6+MO3XF9vDD+cJqoFkkR8Qh6wtVOTBka 7/TBdmB/h2Y4+fe+1Wm/7+2+EJ8FB0dji0Hl83nDgcd7KEbWL8RtWLIgGtLWfQpYZpI+ SxMg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=t8uMjI1Tkwt5zl80wRd5zFszf8LWrgvycYShg8nZg9U=; b=o+R7N8GWaVJj/GWSHRxpvw/w8z/2jw2QFgxKEUKyklkhhaiccls1+2v17F5/mYrs/R TKEbReT7uPI304lQ46hcJnflvR79o7XRmE8z9tPFfl8P2X99MBmELiOlC3D3/ieuZ1g5 33lvIdnkYGNWZa3itzEv5px1JL1npwevO5ywYwJ4TS6PItLy9TpNr2bMRDRQ/FfUUJlb +Ne/Z14Dr4EySheUh/vhkztNkbHvoBCjMm9HLtrvbF3AdVvFj4+HickwfV3zBhX0Yspq EttzXDSorlmjJuGr2vOb0m+DedsN5AiNWRCQZriC+rc0lknpm3cOcd09/kDik4ZZ8n8J 1Uzg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=l1V7kQJL; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id f9-20020a17090a120900b00259be05b1eesi10391973pja.138.2023.06.15.06.34.33; Thu, 15 Jun 2023 06:35:21 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=l1V7kQJL; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S240217AbjFONKh (ORCPT + 99 others); Thu, 15 Jun 2023 09:10:37 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59152 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S245732AbjFONKb (ORCPT ); Thu, 15 Jun 2023 09:10:31 -0400 Received: from mail-pl1-x632.google.com (mail-pl1-x632.google.com [IPv6:2607:f8b0:4864:20::632]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4E08B270A for ; Thu, 15 Jun 2023 06:10:30 -0700 (PDT) Received: by mail-pl1-x632.google.com with SMTP id d9443c01a7336-1b3c578c602so33358115ad.2 for ; Thu, 15 Jun 2023 06:10:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834629; x=1689426629; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=t8uMjI1Tkwt5zl80wRd5zFszf8LWrgvycYShg8nZg9U=; b=l1V7kQJL3oyDCiUF/OX7fjrtf7DZRR7RI2GYk9oEhjuwS5LI2YqP0f4o3ddXjCWQWS xXdKgruRFLIYy+1PhD7MZSSVXOb6BErBtCQdSZQMObTLlY0qM+CKupkWJNruRGfSEmfc oW41beRbt3HRy9w2l2O1DcWBYDVPZiSG2DRRkkjsbHsDACrSHKZOVAp8ZqhW1aIdEUbH Au/zWMZPo2SzO8wN9yNtmxVPcruM3FvQe3k5BqqCXDFBmNRDX1koxSPrzHPpuCff26iy h7xcxA0B3BRnkC6K8fQClPedS2wE6D3qIGnyt/NxBtZZFqlppa+0JXPsytq4Fu6UJTAy HIiA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834629; x=1689426629; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=t8uMjI1Tkwt5zl80wRd5zFszf8LWrgvycYShg8nZg9U=; b=PLgyLAUmFImtLKtIwn38q17KfDTPb2HlwFEbaA+ORjqtmhM+7sQv8VF1zxvomf8J45 fIBcGeNCnHzHZXKPSuDoS1uPLPbvcCOM5r5lJPgZ8uhBkwhnNbNrdZ3neA+pdgj34ayV cZVAD1++TdxIdC5P7oqu1lbdqSYRrAGtvVrNkKJ/jCGzbLpwZ6Qs0/ghjBNrLW1HSEVH qPhiXiYGxNkPKuM/XLQBdTiqNBwq/yhi0Di8mz76SS3lAzGmFFzHroFRX2LEJz4H2eLr 58dJhOK90/0ZO9QPUbKbD1nb5EWwsYBnI/jgNS2W/rwXA3hGzLDgNbAtfMcvvc0vz3ie C8Hg== X-Gm-Message-State: AC+VfDzDg44Y1QaJjL/vJmxudUNS8j6fgthik5usRnf6BZvVi6fD7FCB zf+c6nh7yMV/SAuia2aFIvlqXw== X-Received: by 2002:a17:903:41ce:b0:1ac:8837:df8 with SMTP id u14-20020a17090341ce00b001ac88370df8mr17054187ple.6.1686834629690; Thu, 15 Jun 2023 06:10:29 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.24 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:28 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 1/8] maple_tree: set the node limit when creating a new root node Date: Thu, 15 Jun 2023 21:08:52 +0800 Message-Id: <20230615130859.21858-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768775873468094929?= X-GMAIL-MSGID: =?utf-8?q?1768775873468094929?= Set the node limit of the root node so that the last pivot of all nodes is the node limit (if the node is not full). Signed-off-by: Peng Zhang --- lib/maple_tree.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 279b871f21a6..23202edb9f1e 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3692,7 +3692,8 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry) mas->offset = slot; pivots[slot] = mas->last; if (mas->last != ULONG_MAX) - slot++; + pivots[++slot] = ULONG_MAX; + mas->depth = 1; mas_set_height(mas); ma_set_meta(node, maple_leaf_64, 0, slot); From patchwork Thu Jun 15 13:08:53 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 108516 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp635749vqr; Thu, 15 Jun 2023 06:28:51 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ4PJxJ6H1eeNMS2P4ibaNgNIkZ7L/yrrQtuYUBM0+MngOVhCbi3smq5fxsmrCYQjQKr210O X-Received: by 2002:a05:6808:3014:b0:39c:59e2:dd79 with SMTP id ay20-20020a056808301400b0039c59e2dd79mr14454605oib.36.1686835731116; Thu, 15 Jun 2023 06:28:51 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686835731; cv=none; d=google.com; s=arc-20160816; b=mv3Cpgwknnvp69NBAZ5P3600EFoxrkzRtPaphlTF4rxXefrYE3W+5dJ+zItQMlAEfJ cTjl1LP+L+UJvpgxr5w+SUJsHbnrzqY9cf0O4yrZCAoHRjdp0MtIa7xmdYb27SNj+uiR 4NNWakFjbqaVg4pQX/hqqN/STJpv3esAz24SXxGsJCLOIjoXuC+uvh/ycGzr//Pc6CF3 IkIlt47YSFQzLhdvwUirRPPOjlIXrj/FcQe7lCQOcS8kTZjWFnQr9nlYjiOuNTdWgSF7 tEsrKPOYumH4nCvmU5E5XbNpal7Ais6QjsZDLUjHnkDYn0S7bQZZm/v+d+0JuWL7fML0 gfGw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=h6/zuKtdX43AYOwkx8Y/LcH+jU9PgkVm8ZKPRILAQQ4=; b=GYB1zvI5fxS/GC0n0DRJvvsRSQR0TRAdOF7vUJm/0i6EA5mCclwWGV9G2lpz1gubIC YGSHizS0dhPwCK2v1qpzDc5As5pF16gNgn5K9j/5qi12jIGOhNLP6pc7V7i+u6aCeGPc LyYLNK6w7zcapTYqjdEFnCKk/nrEM069YobQpVI6UCowqlhKVLsLgjHrATiL8gqmcK1Z Pu8y74X+JW6DCJ3JN2YtSeKv9fk1laigVSVPikBylRkMm+jZ92DW9/jnaw1QF7tHS8b2 ZEjMOAZjv2ZiuAcJm3kt5SorisMQV6fUguwbx1zSB6jD++sXJmUuGgT45J9ASHdLR/eX VzOA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=lacYI1rd; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id ls8-20020a17090b350800b00250a6b87c76si13861780pjb.142.2023.06.15.06.28.38; Thu, 15 Jun 2023 06:28:51 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=lacYI1rd; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S240387AbjFONLF (ORCPT + 99 others); Thu, 15 Jun 2023 09:11:05 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59130 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1343637AbjFONK4 (ORCPT ); Thu, 15 Jun 2023 09:10:56 -0400 Received: from mail-pl1-x62a.google.com (mail-pl1-x62a.google.com [IPv6:2607:f8b0:4864:20::62a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id DE2B926AF for ; Thu, 15 Jun 2023 06:10:33 -0700 (PDT) Received: by mail-pl1-x62a.google.com with SMTP id d9443c01a7336-1b51488ad67so6044445ad.3 for ; Thu, 15 Jun 2023 06:10:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834633; x=1689426633; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=h6/zuKtdX43AYOwkx8Y/LcH+jU9PgkVm8ZKPRILAQQ4=; b=lacYI1rdr01pCdKfMnHhOKSCgbbBcVdmvwoMpr0oZyI57wLUeehSv5VQlOckRsf5J3 QwhNEOl0DD1FfI3cPy9Z9ARfNVfzViCEPcpq03XbXk5so1vLbh7DPPRvpWO1zi4bomBO 5EbytiQEqeWF2jRC+LaPbXlHtXlCG4qOPd7q7hU8lFSMsJL5SL0LGE4TM/XGlK6GPGuJ iXGq9IAho5nY3K2O6BfuUmtjOhLdtYDQ2x1ilR7xqptKeCyr9ahA4zheIQqe3U2QGjsA xUmmiKov49NhTlzUKrGnBWPBapM+IwdvYyEfaCSov4WzDmpMBvBIQUcB1Z2ef64knjTX tz/Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834633; x=1689426633; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=h6/zuKtdX43AYOwkx8Y/LcH+jU9PgkVm8ZKPRILAQQ4=; b=Tk09dPvHJOMzFdrm26mNez1GWk1SZKASNTJQiOOVVlvydxhvYYTF4jrdtjDy5viX1e yBSzqhSxFgQxmPjqbizuF/hRsjS/pF0QLW/9eYMBvsJWXUMyJ2DHNp11KcNUi3cgnhbu ipmY740+8YCo0R3FABG7DGrBAbfTK9jwAaA4yAyCKV9QGqCPbKs8qkAIEt/KwAeYex6R ZJ151raIrPQ/O8i8iHRHPLgzw3gZoIACD07B2zmDRziHEQ+h52MpR4FrJMlkTQexdXiG UjsqIzLTj0QHXY3CSi+tg5CwCkOZZSXsWzpxv5Jrn1VL1uyBsvkqHIzjq7P3grMX2JJw iIjA== X-Gm-Message-State: AC+VfDxx/qbkPhRe9Nr+vfSbAt4DhZRCuKCq5TblY7Lfi3e6ga0RYZ/M 2A7rbk7qVckYlybGx3sM4RBszQ== X-Received: by 2002:a17:903:32c3:b0:1b3:d8ac:8db5 with SMTP id i3-20020a17090332c300b001b3d8ac8db5mr10723526plr.40.1686834633447; Thu, 15 Jun 2023 06:10:33 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.30 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:32 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 2/8] maple_tree: don't use MAPLE_ARANGE64_META_MAX to indicate no gap Date: Thu, 15 Jun 2023 21:08:53 +0800 Message-Id: <20230615130859.21858-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768775463725150887?= X-GMAIL-MSGID: =?utf-8?q?1768775463725150887?= Do not use a special offset to indicate that there is no gap. When there is no gap, offset can point to any valid slots because its gap is 0. Signed-off-by: Peng Zhang --- include/linux/maple_tree.h | 2 -- lib/maple_tree.c | 13 ++----------- 2 files changed, 2 insertions(+), 13 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index e18ecbefc7f7..4e004d86c780 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -29,14 +29,12 @@ #define MAPLE_NODE_SLOTS 31 /* 256 bytes including ->parent */ #define MAPLE_RANGE64_SLOTS 16 /* 256 bytes */ #define MAPLE_ARANGE64_SLOTS 10 /* 240 bytes */ -#define MAPLE_ARANGE64_META_MAX 15 /* Out of range for metadata */ #define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 1) #else /* 32bit sizes */ #define MAPLE_NODE_SLOTS 63 /* 256 bytes including ->parent */ #define MAPLE_RANGE64_SLOTS 32 /* 256 bytes */ #define MAPLE_ARANGE64_SLOTS 21 /* 240 bytes */ -#define MAPLE_ARANGE64_META_MAX 31 /* Out of range for metadata */ #define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 2) #endif /* defined(CONFIG_64BIT) || defined(BUILD_VDSO32_64) */ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 23202edb9f1e..8aba9e419e08 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1610,8 +1610,6 @@ ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt, * mas_max_gap() - find the largest gap in a non-leaf node and set the slot. * @mas: The maple state. * - * If the metadata gap is set to MAPLE_ARANGE64_META_MAX, there is no gap. - * * Return: The gap value. */ static inline unsigned long mas_max_gap(struct ma_state *mas) @@ -1628,9 +1626,6 @@ static inline unsigned long mas_max_gap(struct ma_state *mas) node = mas_mn(mas); MAS_BUG_ON(mas, mt != maple_arange_64); offset = ma_meta_gap(node, mt); - if (offset == MAPLE_ARANGE64_META_MAX) - return 0; - gaps = ma_gaps(node, mt); return gaps[offset]; } @@ -1662,10 +1657,7 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, ascend: MAS_BUG_ON(mas, pmt != maple_arange_64); meta_offset = ma_meta_gap(pnode, pmt); - if (meta_offset == MAPLE_ARANGE64_META_MAX) - meta_gap = 0; - else - meta_gap = pgaps[meta_offset]; + meta_gap = pgaps[meta_offset]; pgaps[offset] = new; @@ -1678,7 +1670,6 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, ma_set_meta_gap(pnode, pmt, offset); } else if (new < meta_gap) { - meta_offset = 15; new = ma_max_gap(pnode, pgaps, pmt, &meta_offset); ma_set_meta_gap(pnode, pmt, meta_offset); } @@ -2076,7 +2067,7 @@ static inline void mab_mas_cp(struct maple_big_node *b_node, end = j - 1; if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) { unsigned long max_gap = 0; - unsigned char offset = 15; + unsigned char offset = 0; gaps = ma_gaps(node, mt); do { From patchwork Thu Jun 15 13:08:54 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 108513 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp627459vqr; Thu, 15 Jun 2023 06:16:01 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ4g/XniWP3y4ATwNpgpFmOtJCWFMDWMxZ1jzjdqBr/2eFGb4qIV1/Dy5/kUH7yZnGszRp8Y X-Received: by 2002:a05:6808:d3:b0:39c:7a71:957 with SMTP id t19-20020a05680800d300b0039c7a710957mr12289899oic.46.1686834960809; Thu, 15 Jun 2023 06:16:00 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686834960; cv=none; d=google.com; s=arc-20160816; b=Ei7p1CsOnqeatJjM9Ad+FoX3/iAG4E/4lhu9PIjtf+It2paEdxlJ2boNZ3k8CsaVx5 iRyQKXBrkguaeOeIuu7Fkkx4D76hrdCsYl38JDjDF5JMIdClfIt3DK8B8/fDFFxC4ct6 NkVn13/1RAGrJRR291vPnlWaNiB0qYZtASM0TYXr9ZzuMIte1BTVbzJO4K8qu4hAzzZJ qib4gfMqtp6H8tmfrBgjDXl3jRxINuaQawoq1TVlhvmPG6bTcTjbIVRRhk8KDxaf3FAm eWcgYgO0v6npAud++hziDDQW2iNnwERCNUFi9Lh7DPhxWuXpDK/VX//MpoTYIV5lajpF 1ubw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=MG8wEkfZhYGC5aupLXEONPEpLbQPJyBuYKNQETRNYXQ=; b=t+PpswwliX/t4CYXVQzpTjnkuuLdBuNojeU+azGEHwcOj0tyKSu5LGDhtxGzssQDTZ 6gKMHfsCOwLleGetz77pHT4azxnQCDG2AOtG+Jmu65R3KqJC+wcCWIaqbPlHDR855SCw DBhIeHpiE80b68COG6AHzm5OO5FIAA3lQF/Ik4zFDMqQlIGi+i16xVSydNuQsU+CCdfC J6WZRRW2CBCmg6ucdrXCHFd6UXKnm7xbsc7txk9PoTtIDSEz3x4kwpMtwwhu1oTzBh67 XXIhKU7LnEGtlQcHffEqy/+FIZuCTT9RZZI5hRtZfsNcyBvb0Z7V79TsJLw6f/vA8DtP quVw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=JBdX1l1x; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id z189-20020a6333c6000000b00553361ff1a9si473993pgz.746.2023.06.15.06.15.47; Thu, 15 Jun 2023 06:16:00 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=JBdX1l1x; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1343644AbjFONLH (ORCPT + 99 others); Thu, 15 Jun 2023 09:11:07 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59144 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1343724AbjFONLC (ORCPT ); Thu, 15 Jun 2023 09:11:02 -0400 Received: from mail-pl1-x630.google.com (mail-pl1-x630.google.com [IPv6:2607:f8b0:4864:20::630]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CDA0626BA for ; Thu, 15 Jun 2023 06:10:37 -0700 (PDT) Received: by mail-pl1-x630.google.com with SMTP id d9443c01a7336-1b3b3f67ad6so45418965ad.3 for ; Thu, 15 Jun 2023 06:10:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834637; x=1689426637; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=MG8wEkfZhYGC5aupLXEONPEpLbQPJyBuYKNQETRNYXQ=; b=JBdX1l1x+iSg2CpjvKE+gC3fQ5LWgXkFJ7O3qRqfSLsduXgNEEnfZyRZYD+aaDtn7N uSkoiI3TK2NJb/opjoa/il1l5jtgGuKT70/3p9YVeEph/4m8CwB62pWy40V19y6b3aBt T+3f4gBTnPVMNomBZwR+rHzM3IPEpaFZKEVHjpr3cDYsT085CBjG839Y0kDt0RG7zprr cs36S3Z9fzu8SZxcfDKFdL14UvqkXTGVFkmjRRMVFjUSG++ubc5+L0lc0JrsYkImHvD1 qPTGQOAli/Oa9AWBv0XxRDill+ZhjXzuiBCDJbggf+iwNECB11Vh4LZldV3czFsyeBDD w8IQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834637; x=1689426637; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=MG8wEkfZhYGC5aupLXEONPEpLbQPJyBuYKNQETRNYXQ=; b=PTBuDcuCCjQGnNSP9tkcK1jvgAaGBGJ4B1OU/p88C/vN5B+q/nvnbCq8tn1qsBdTny nvnZAmiJeAGcs3p/eqmRB3PXnuK0zRiu2F+yHNrLILp1uqzEj8PkxuJ7gPL4QvUjNh4a +gbQCiKrFWuJVBiV3Td2g3CirOQDAlo6o6WO9E/g7qT4/vyYiJGVNyv/50BfsjNn7SKq hIaVHJnPnt8ymuxZujqAijC9+KGxETtiJHhntltbICpDUl9iMLy341amXwEsEXTtHEVE YmONHeSis+uW5V+47Q9OJZoVoZitneEJfNp6Qc8qRrYCOhstsg/Lc7JNnrVSuRgV/35C oVeQ== X-Gm-Message-State: AC+VfDxnSTTS6nIAe3TzGfBX6OSte7S4xHAbfVnwU2FmuMbtkNSohLQ+ mnDwPRa/pS42eNXcc4qsRjKa2A== X-Received: by 2002:a17:903:1390:b0:1b2:28ca:d16 with SMTP id jx16-20020a170903139000b001b228ca0d16mr13196115plb.44.1686834637281; Thu, 15 Jun 2023 06:10:37 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.33 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:36 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 3/8] maple_tree: make mas_validate_gaps() to check metadata Date: Thu, 15 Jun 2023 21:08:54 +0800 Message-Id: <20230615130859.21858-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768774655560107213?= X-GMAIL-MSGID: =?utf-8?q?1768774655560107213?= Make mas_validate_gaps() check whether the offset in the metadata points to the largest gap. By the way, simplify this function. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 68 +++++++++++++++++++++++------------------------- 1 file changed, 33 insertions(+), 35 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 8aba9e419e08..799afd590cf3 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6979,15 +6979,16 @@ EXPORT_SYMBOL_GPL(mt_dump); static void mas_validate_gaps(struct ma_state *mas) { struct maple_enode *mte = mas->node; - struct maple_node *p_mn; + struct maple_node *p_mn, *node = mte_to_node(mte); + enum maple_type mt = mte_node_type(mas->node); unsigned long gap = 0, max_gap = 0; unsigned long p_end, p_start = mas->min; - unsigned char p_slot; + unsigned char p_slot, offset; unsigned long *gaps = NULL; - unsigned long *pivots = ma_pivots(mte_to_node(mte), mte_node_type(mte)); + unsigned long *pivots = ma_pivots(node, mt); int i; - if (ma_is_dense(mte_node_type(mte))) { + if (ma_is_dense(mt)) { for (i = 0; i < mt_slot_count(mte); i++) { if (mas_get_slot(mas, i)) { if (gap > max_gap) @@ -7000,52 +7001,51 @@ static void mas_validate_gaps(struct ma_state *mas) goto counted; } - gaps = ma_gaps(mte_to_node(mte), mte_node_type(mte)); + gaps = ma_gaps(node, mt); for (i = 0; i < mt_slot_count(mte); i++) { - p_end = mas_logical_pivot(mas, pivots, i, mte_node_type(mte)); + p_end = mas_logical_pivot(mas, pivots, i, mt); if (!gaps) { - if (mas_get_slot(mas, i)) { - gap = 0; - goto not_empty; - } - - gap += p_end - p_start + 1; + if (!mas_get_slot(mas, i)) + gap = p_end - p_start + 1; } else { void *entry = mas_get_slot(mas, i); gap = gaps[i]; - if (!entry) { - if (gap != p_end - p_start + 1) { - pr_err("%p[%u] -> %p %lu != %lu - %lu + 1\n", - mas_mn(mas), i, - mas_get_slot(mas, i), gap, - p_end, p_start); - mt_dump(mas->tree, mt_dump_hex); - - MT_BUG_ON(mas->tree, - gap != p_end - p_start + 1); - } - } else { - if (gap > p_end - p_start + 1) { - pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", - mas_mn(mas), i, gap, p_end, p_start, - p_end - p_start + 1); - MT_BUG_ON(mas->tree, - gap > p_end - p_start + 1); - } + MT_BUG_ON(mas->tree, !entry); + + if (gap > p_end - p_start + 1) { + pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", + mas_mn(mas), i, gap, p_end, p_start, + p_end - p_start + 1); + MT_BUG_ON(mas->tree, + gap > p_end - p_start + 1); } } if (gap > max_gap) max_gap = gap; -not_empty: + p_start = p_end + 1; if (p_end >= mas->max) break; } counted: + if (mt == maple_arange_64) { + offset = ma_meta_gap(node, mt); + if (offset > mt_slots[mt]) { + pr_err("gap offset %p[%u] is invalid\n", node, offset); + MT_BUG_ON(mas->tree, 1); + } + + if (gaps[offset] != max_gap) { + pr_err("gap %p[%u] is not the largest gap %lu\n", + node, offset, max_gap); + MT_BUG_ON(mas->tree, 1); + } + } + if (mte_is_root(mte)) return; @@ -7055,10 +7055,8 @@ static void mas_validate_gaps(struct ma_state *mas) if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) { pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap); mt_dump(mas->tree, mt_dump_hex); + MT_BUG_ON(mas->tree, 1); } - - MT_BUG_ON(mas->tree, - ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap); } static void mas_validate_parent_slot(struct ma_state *mas) From patchwork Thu Jun 15 13:08:55 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 108523 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp641297vqr; Thu, 15 Jun 2023 06:37:04 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ7sDN/U2uju8YR+VwRv/diXiElh7OrGzlHzk6kGqsgf6jYwkXyVDIcDJw5P4dKF6naCpSqJ X-Received: by 2002:a17:90a:3808:b0:25e:a6ab:77d5 with SMTP id w8-20020a17090a380800b0025ea6ab77d5mr421592pjb.20.1686836224429; Thu, 15 Jun 2023 06:37:04 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686836224; cv=none; d=google.com; s=arc-20160816; b=SYfIr5NsNQ/Mb6l1/b6nvraTxsWIHM1RQVs5adKi9OEKHUp2ACuvS4OxJUz79KyGuW yHDIDcBKOOKBPHOqG8NTFMaLDVGFMjkuUIBDzS+sCAw1FK1NWAWw1AKE/pNHksh/lKSq HzuDUEVGxrpNpHNz9vGOFzHBSBmrtMiTXiyI9JS0TK+GYex1A9wfpRfBsmRCjldwMxQ8 0VnDeRQCupnJTYScgfTT/L9KB5K4Osmy81xVrmFeWCVZMK0rMmL/BGSSeOHyF2Rz2XaL Ga/xCHbOYNBJ1nrCFn8kUiCvBn/c19ZxAVuSrnE5tfFoPXMRjRZFpKOW05CRhyJwaFxg vr4A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=Bwu5nVhZqsw5mJk5ySAZ1ZJzvb1s8FXMcsj+5u++1nw=; b=SY5wbW9Bwh0hup0Ztfs1Wdt2K01wjFzjP0fAEJtEg6MyYUg6MLIM/oHKTlC/QDAl7m 7BggJ0ek8tFb4ZyinqWpcIN3pXI/iVbohUwRGexkhC65HdKEQluUkmOvT0XdyUtSUmK+ zLSsav4wNHXKLgM56igCULra4gQXJsd8XM2W0ZtSAlh+QZdzbEdTTRVMDW+RFEXfyGwm 8t47WLAlq7ZzCEQr5gFon2k1uW6SNNSHaJzPgz+NA0vEMlgU0RoYOXNcPHRnXfNkANIZ 1hDKMEoNrWpfB9tXc1vEmYtNsZCiGtdID95rIhx7geaNXmloWQ9IO9G5z0WOuZJcdpZG TrqQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=LrTA+ywK; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id mj4-20020a17090b368400b0025bf7aa38ccsi6769129pjb.157.2023.06.15.06.36.52; Thu, 15 Jun 2023 06:37:04 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=LrTA+ywK; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1343811AbjFONLK (ORCPT + 99 others); Thu, 15 Jun 2023 09:11:10 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59268 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1343710AbjFONLC (ORCPT ); Thu, 15 Jun 2023 09:11:02 -0400 Received: from mail-pf1-x42e.google.com (mail-pf1-x42e.google.com [IPv6:2607:f8b0:4864:20::42e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 471E526B6 for ; Thu, 15 Jun 2023 06:10:41 -0700 (PDT) Received: by mail-pf1-x42e.google.com with SMTP id d2e1a72fcca58-6669be8288bso433036b3a.2 for ; Thu, 15 Jun 2023 06:10:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834641; x=1689426641; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Bwu5nVhZqsw5mJk5ySAZ1ZJzvb1s8FXMcsj+5u++1nw=; b=LrTA+ywKAk48Bks9Q4FIitMp7HeDcqRRmwSAPNDfOScb1TlK19naIDVZsu9SNJhp6G ciB+6/O0g2mQqQX1sYbvq7XQfe99l+pDofZVgNgI1ECqI/a60Da4LqfrqBLqBIZqOWfJ Qq65teJ95eepYbYMyebJySZ2X2SGYHiRzJJLO0LNbNBD5OVSG/AF2nHuunjE0XDabsfP Ulxt1D4JlWwsqIQMKZH+6ewgYdkFIXWrZeV/FWvTTvt7rie24HSlfngK1US75VQF9sYI vsHBI+uRXhuNMCQRhYA2VAwekjD63+3P+055GGksZ+oQ/yYfTrbpB76riVW5lnmnIa25 FQ4A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834641; x=1689426641; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Bwu5nVhZqsw5mJk5ySAZ1ZJzvb1s8FXMcsj+5u++1nw=; b=Frzl2UW+ADleYnP8jnqsIAtYgRL+KfCE2Apfk1/7jblaPnU06j3ZX20Kh11VTavuvS ql1jmWwWVbslq5lhVVw57rNQurUOfy/PFCeXq4tSZGA885pRdP8TUA6l7+qs4ePdJRSM RhpdzYz+AGtgEMbFF/bVweGi8hWLs1dkBf9rRZ3zyMQb0s5JyFBbIPSkz9/vpwyjkNdL mmGcOvuxhzAdyEy31aaDkHQ3Gff3MW3jmPLt+wxClIFQ2VcPWuSF6TTqyA/mVY7Sn+t9 3ZNwal8BVAPsScu5pu4NV6uoaNlQ+zq0zV9l2rqBmw/OL6wPIXHkgO14o7dUCGGSGPKV EFCA== X-Gm-Message-State: AC+VfDyNeLC48fVMIOpm5/09g7giKmigTAnF235s5UcjfvOSi95S657C yb4smb8rdXoRbbCwchscztzP9Q== X-Received: by 2002:a05:6a20:7da7:b0:10b:6e18:b690 with SMTP id v39-20020a056a207da700b0010b6e18b690mr4629377pzj.32.1686834640813; Thu, 15 Jun 2023 06:10:40 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.37 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:40 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 4/8] maple_tree: fix mas_validate_child_slot() to check last missed slot Date: Thu, 15 Jun 2023 21:08:55 +0800 Message-Id: <20230615130859.21858-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768775980922065052?= X-GMAIL-MSGID: =?utf-8?q?1768775980922065052?= Don't break the loop before checking the last slot. Also here check if non-leaf nodes are missing children. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 799afd590cf3..d91e66ea223f 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7107,11 +7107,12 @@ static void mas_validate_child_slot(struct ma_state *mas) for (i = 0; i < mt_slots[type]; i++) { child = mas_slot(mas, slots, i); - if (!pivots[i] || pivots[i] == mas->max) - break; - if (!child) - break; + if (!child) { + pr_err("Non-leaf node lacks child at %p[%u]\n", + mas_mn(mas), i); + MT_BUG_ON(mas->tree, 1); + } if (mte_parent_slot(child) != i) { pr_err("Slot error at %p[%u]: child %p has pslot %u\n", @@ -7126,6 +7127,9 @@ static void mas_validate_child_slot(struct ma_state *mas) mte_to_node(mas->node)); MT_BUG_ON(mas->tree, 1); } + + if (i < mt_pivots[type] && pivots[i] == mas->max) + break; } } From patchwork Thu Jun 15 13:08:56 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 108517 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp636246vqr; Thu, 15 Jun 2023 06:29:45 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ7pFc0JslYpgyJI58H0ZGhKi2zxPUKzeiBR/sBXfRvJ0iVNZc/oe/y3h6SPMv0MkjxOxRUM X-Received: by 2002:a05:6830:1db9:b0:6b1:5f48:6b06 with SMTP id z25-20020a0568301db900b006b15f486b06mr14988167oti.30.1686835784950; Thu, 15 Jun 2023 06:29:44 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686835784; cv=none; d=google.com; s=arc-20160816; b=v1haEnXgcEuRVd57vnN732PvuHK7KjaqkeLG+84B3SGfuNPAG19l3LMPtYLqIDvWCN Oqv1617u1KvEeMf1NP5RP9c5BozEvTq3LlAWFBCeG6PszOv+Y0F2xFX+MpWgJZedp6PA fwGvsENODs5iHGsU2pASIMxmi1mUt1ma2rYW+67UfBeqb125RnE0coZHqsGyMVvpLJJo tc83pQ63ApyJbAxAgYjPfx3bVtzSzsWa3s7AVNPERec4v4iBK9NJW4qDbZ0MUtvT6OF5 igsqwHFUnEJeGX0/AjzfYgGxG0RfXLzJhC0nODMnanKIc9dIfnec4Q8bZyqhF3fy8PMj v0QQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=Bi6s0yfXuBjDVA++TIrUvyqPyk4i8//b9rD0tFMY+rQ=; b=eKb9VzA8aYZMqEhZbKFacZ3QAvombTinSG7kOFTBH7u0g3UkGQNHDbwVEDgV4GQQJ8 Wy9v770u3QoAjQe4Rb8mmhjscN6t/CdTZHH73OH85aPe0NrVS+2rhGpR8ZrQIO+ytiG1 6GpTc/uVYfoznYxCp8PdcYlpSLeshrU3Nejbh52TXCZcEMViN957kNDFYrCXg04J9bYH +TUmQaV4aIgWdA0y3v6ljq5YHfYgsu7MMYaEApCu2XS0OtwI4ET5Kd31Q0SocT6soHco z+DqAVgqjOpymVj70HmNiZ0QxD5wbIzWUfmqJuKBP4kN0xL1F7KHBPGE3ba6mmxX89Sd 7QsQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=XHxv1DOD; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id o24-20020a639218000000b0054290a76b1csi10079357pgd.112.2023.06.15.06.29.31; Thu, 15 Jun 2023 06:29:44 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=XHxv1DOD; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1343853AbjFONLQ (ORCPT + 99 others); Thu, 15 Jun 2023 09:11:16 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59162 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S241356AbjFONLI (ORCPT ); Thu, 15 Jun 2023 09:11:08 -0400 Received: from mail-pl1-x62d.google.com (mail-pl1-x62d.google.com [IPv6:2607:f8b0:4864:20::62d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C37CA2702 for ; Thu, 15 Jun 2023 06:10:44 -0700 (PDT) Received: by mail-pl1-x62d.google.com with SMTP id d9443c01a7336-1b01d3bb571so45009565ad.2 for ; Thu, 15 Jun 2023 06:10:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834644; x=1689426644; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Bi6s0yfXuBjDVA++TIrUvyqPyk4i8//b9rD0tFMY+rQ=; b=XHxv1DODKYeQKwjzJy2jt+aDwBfZOEIQt0yctlrkqvR3AsFSf1ORSYqAly/zx/7VwZ WE5pC8UGcgZNqDWgJwiEsDt408rwNq/NyGormCqefHQz7iV/7MM+SPvUXcgj8DIwhdjM pdca/N3EZmE6EUlzP8ejwoyLpAGzBriRcJ0sZ40piq4tT04sS0ciN2/ZenkJeOM+P7Ig G51gduTFS2c7/RsbPS1J745FnYsdE+Lck2dn1qUXKvwp0gv2Tm588fL14wsSgM//puEw TH6gPvmuoROUn2NJ4SgKKQZxGmklUQUJUdHsGkpDt0dog3/OQShcgpNHl+zGO18WjK26 ebrw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834644; x=1689426644; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Bi6s0yfXuBjDVA++TIrUvyqPyk4i8//b9rD0tFMY+rQ=; b=V0USobmeu2ufKnsXcj/ddyTGUKhMUdmY4r/gx20zunAOKtHgjX1ZgiV6sPitRQ/3EA Kl2xE5h8N/IYheiMJTZrBQhR6KoKFRAehBp9qFetNtEwDgU/2iu/CWzxNSXm392CxUzw t5gSe52pA+KbkE7KPHTbNntx46+XVyS12IxkYtJT9J6oCawfdGIhQd6NziMny9VBOS6H QekpDjfgvuz9P2aL95K9NKjtbhyZqTWeb7pS2+WqAu95tbl3MoST2iBzL+Mx5ejh3OK6 fexx9/fKhVaO6J+g0QDLJr7jMrUb83K+DLeIAN7QmzqBfzGQHjMf7fJdxdlRYfHPrPMT 7x1g== X-Gm-Message-State: AC+VfDy9mCUlF9uW6/+0ml23WMymwfFFolTieqCVZ0DCV0ZjsALJYuV2 WPQK1VTvdML0Ma0H/MsGwtmd3Q== X-Received: by 2002:a17:902:ab1b:b0:1b5:26d4:517d with SMTP id ik27-20020a170902ab1b00b001b526d4517dmr140399plb.29.1686834644205; Thu, 15 Jun 2023 06:10:44 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.41 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:43 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 5/8] maple_tree: make mas_validate_limits() check root node and node limit Date: Thu, 15 Jun 2023 21:08:56 +0800 Message-Id: <20230615130859.21858-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768775520284645636?= X-GMAIL-MSGID: =?utf-8?q?1768775520284645636?= Update mas_validate_limits() to check root node, check node limit pivot if there is enough room for it to exist and check data_end. Remove the check for child existence as it is done in mas_validate_child_slot(). Signed-off-by: Peng Zhang --- lib/maple_tree.c | 26 +++++++++++--------------- 1 file changed, 11 insertions(+), 15 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index d91e66ea223f..6c9b62e41605 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7144,26 +7144,15 @@ static void mas_validate_limits(struct ma_state *mas) void __rcu **slots = ma_slots(mte_to_node(mas->node), type); unsigned long *pivots = ma_pivots(mas_mn(mas), type); - /* all limits are fine here. */ - if (mte_is_root(mas->node)) - return; - for (i = 0; i < mt_slots[type]; i++) { unsigned long piv; piv = mas_safe_pivot(mas, pivots, i, type); - if (!piv && (i != 0)) - break; - - if (!mte_is_leaf(mas->node)) { - void *entry = mas_slot(mas, slots, i); - - if (!entry) - pr_err("%p[%u] cannot be null\n", - mas_mn(mas), i); - - MT_BUG_ON(mas->tree, !entry); + if (!piv && (i != 0)) { + pr_err("Missing node limit pivot at %p[%u]", + mas_mn(mas), i); + MAS_WARN_ON(mas, 1); } if (prev_piv > piv) { @@ -7186,6 +7175,13 @@ static void mas_validate_limits(struct ma_state *mas) if (piv == mas->max) break; } + + if (mas_data_end(mas) != i) { + pr_err("node%p: data_end %u != the last slot offset %u\n", + mas_mn(mas), mas_data_end(mas), i); + MT_BUG_ON(mas->tree, 1); + } + for (i += 1; i < mt_slots[type]; i++) { void *entry = mas_slot(mas, slots, i); From patchwork Thu Jun 15 13:08:57 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 108518 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp638350vqr; Thu, 15 Jun 2023 06:32:28 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ7vMnllruZOC682Ckm0pXvLPLEDrQZMBDJz+wD98xS5MuNplFhJ4NS93FfxzJeHd/PuPWvV X-Received: by 2002:a17:90a:1909:b0:25b:dae4:205 with SMTP id 9-20020a17090a190900b0025bdae40205mr3942020pjg.32.1686835948309; Thu, 15 Jun 2023 06:32:28 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686835948; cv=none; d=google.com; s=arc-20160816; b=ceGDNjE3S76G97l8CFa1pzkYiFmPLqiKGgL2Tb3N4Z5jdw3R9iDZdY5EKqbRkedk7+ ZG4y78mrTrPuCeCsVn83RHbA052rjBCIERFLuted1kmq4/Ry3JDcPgFHAPRN0P511Wvq /2Co/G2ii1T3skcxprwPQp+Fp8ReTGQLvn+n9s/rpczr8tggtj0FMhMtSN6Kxb9PS2yF WHRlkAkv4EndsPNjFWMYl9FNRw/Gt7A9Vs1/KEGMDBX27g3efD8PcXaiNuujiwB7FynP 4Cvr4ZjbYrDkMqK16uiYvH25I4xALJkHrcOuUZlslFP+0t4PD0jQ0ocLVGPp0spOtRPg hQVQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=6ZGxNZsIpnMBQhUNXCsRmhhDB1lIsi8lU2hwxHUwfjk=; b=G4njeMDgN+2Ip1uYKc+b+Cx2d+zzxl2x89IJ1Ii7hTTAsSwjXMU1u7VYeLvqhnGmnd mMNQbI5S+xNQyo9FADYWMwtYKtrzU5OVlE9QBFyxttnaUdMED43g3W1jzqRqNosv49Ha O3lfv+iAxyA3H11apMsAmT3ejCuP4pjy93rgCU1hJCNUZh2OHJSIwTuc1l6QtdlZ19d0 m0fXBwaU7d/rfAN16lZEOoECi/IwGg/XQSqtNPh1uDuqZmeSxICZq0DjjDBIjfYZAhX4 OdrZF4xOpAto31BVEAFblR0V33rc4VONjobgQ+T4qhCOv+L9kx+Yu9kJwvTQxqJhntMX pBnA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=bB1QL+mm; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id d123-20020a633681000000b0054ff3d84101si1718228pga.317.2023.06.15.06.32.14; Thu, 15 Jun 2023 06:32:28 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=bB1QL+mm; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S245732AbjFONKu (ORCPT + 99 others); Thu, 15 Jun 2023 09:10:50 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59298 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S245160AbjFONKs (ORCPT ); Thu, 15 Jun 2023 09:10:48 -0400 Received: from mail-pl1-x62d.google.com (mail-pl1-x62d.google.com [IPv6:2607:f8b0:4864:20::62d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E5619123 for ; Thu, 15 Jun 2023 06:10:47 -0700 (PDT) Received: by mail-pl1-x62d.google.com with SMTP id d9443c01a7336-1b5251e5774so916795ad.1 for ; Thu, 15 Jun 2023 06:10:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834647; x=1689426647; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=6ZGxNZsIpnMBQhUNXCsRmhhDB1lIsi8lU2hwxHUwfjk=; b=bB1QL+mmf56nkMSsfv598qN2fllo5bMGUfYXT445+ukRmpKPsuk9VT0wAtXq00tXeY WeK6VnfC6+czbq/PAw1qbKx7hPjEooLS3/e1llNQeBCEMEXRS3MUgv6jIThk9gqloXRU BsnD43Jj3AIUQNECtE2YygfsbaSk9n7L1Bh6WyE0EiLSeyCxZFUvNDtPlPA0X8aPjihM RATB0sV7gU9LvQ64TF2MqqfgGgXt9z292CVR1zak0IJpJq+TIO1K7agY+R8kNbQ+AGBP eaBkO0j8yCfFJSwgITxQoJek7mvOUQ92gsgUJAtfhMEvls0y8GeNKpYUifxw40BfhDrj UAcQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834647; x=1689426647; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=6ZGxNZsIpnMBQhUNXCsRmhhDB1lIsi8lU2hwxHUwfjk=; b=bxc5LxB7vTM0RO/5SqGwPgO+UG0srM6nUssKHdWowD0il1R3Tq4grX6+AonTKlNIWc EWwEzVpSSdvPp/lb3WmT2542P1hqgAReb1/mKeIihUTo9kZF37lzGQ+euRnRP52krvZc wEbR0Rwe0JfWIepDPOU3E4bThGF/ceZesqOyV3SEvb0/+hQKQ/CQOMb6XI2hjYFn3KwN UGfIFXhp1hdqIY6tZYqsWqjCWtBNWSbxtT41sbwkwtFrXeBj3w5US+VrbfQb8sz2+YDR hCfRe0HnUAIaqlLJz+sPlGi4ojLww2P2K0J2G2ARQK6mkcD61+kO7g0VW5uNaLEHDI+I 0baQ== X-Gm-Message-State: AC+VfDwZ1+zgX3KXMj16OuQghg9MQkFS/9RA7rgw99I6zvWjoBHTCiBx LJofBhzcCYTC0RwtllMUECkDNx3EZ/Pu4WVYFWA= X-Received: by 2002:a17:902:c20d:b0:1b5:253f:d05f with SMTP id 13-20020a170902c20d00b001b5253fd05fmr279675pll.29.1686834647381; Thu, 15 Jun 2023 06:10:47 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.44 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:46 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 6/8] maple_tree: update mt_validate() Date: Thu, 15 Jun 2023 21:08:57 +0800 Message-Id: <20230615130859.21858-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768775691179246296?= X-GMAIL-MSGID: =?utf-8?q?1768775691179246296?= Instead of using mas_first_entry() to find the leftmost leaf, use a simple loop instead. Remove an unneeded check for root node. To make the error message more accurate, check pivots first and then slots, because checking slots depend on the node limit pivot to break the loop. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 21 +++++++++++---------- 1 file changed, 11 insertions(+), 10 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6c9b62e41605..becb4c224e57 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7256,21 +7256,22 @@ void mt_validate(struct maple_tree *mt) if (!mas_searchable(&mas)) goto done; - mas_first_entry(&mas, mas_mn(&mas), ULONG_MAX, mte_node_type(mas.node)); + while (!mte_is_leaf(mas.node)) + mas_descend(&mas); + while (!mas_is_none(&mas)) { MAS_WARN_ON(&mas, mte_dead_node(mas.node)); - if (!mte_is_root(mas.node)) { - end = mas_data_end(&mas); - if (MAS_WARN_ON(&mas, - (end < mt_min_slot_count(mas.node)) && - (mas.max != ULONG_MAX))) { - pr_err("Invalid size %u of %p\n", end, - mas_mn(&mas)); - } + end = mas_data_end(&mas); + if (MAS_WARN_ON(&mas, + (end < mt_min_slot_count(mas.node)) && + (mas.max != ULONG_MAX))) { + pr_err("Invalid size %u of %p\n", end, + mas_mn(&mas)); } + mas_validate_parent_slot(&mas); - mas_validate_child_slot(&mas); mas_validate_limits(&mas); + mas_validate_child_slot(&mas); if (mt_is_alloc(mt)) mas_validate_gaps(&mas); mas_dfs_postorder(&mas, ULONG_MAX); From patchwork Thu Jun 15 13:08:58 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 108522 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp641144vqr; Thu, 15 Jun 2023 06:36:50 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6y9VyAXmGHUAFsZupTHYrcV2aGvet+aDaK3+11Gte0hYPUXeEf8XF/7bex9NtjjRNh8Gbe X-Received: by 2002:a92:90a:0:b0:340:bbae:140d with SMTP id y10-20020a92090a000000b00340bbae140dmr3471245ilg.21.1686836209962; Thu, 15 Jun 2023 06:36:49 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686836209; cv=none; d=google.com; s=arc-20160816; b=ZVgHELyGJVfC+QRD8FwTARUr6t7wT+kq5oOz9rbn3cn/diKYB1mbEo9FuxMbV/90do RHKlmWMzebpApkoOdXn5w38kmFvq0In3KZD7CO0yMzsPBKNXU7D5UJJbQW7T15UfpRJ3 dkiT+20J9F7zdNHIy0hRaRwxmVuhg4YOL/+BkBbs0DWojehOcvRWPqO57Pc24u8hVXLd Ivhz/v4VHXCx2ENSS/alFup7Z7sBUMB4qhe3Naq24rVWsaBwGjLitZEv1c/BJLT/uArj 0Etn/Sp+m7iJu6zGi4IevHaYoHCbM6wFm4aMC/5QjmfrnxKsO8wCgLztPuES56YL6NVY s8ew== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=rh1upVsLkWtnKrYRXZBQpn/CVX3v0vcX/4UFjQ1Vcrw=; b=PQ8caqQ3VFLWfGflCqoQClz81sBY/j5i8Xt81v7C+3RO1CqABibHN1xYbu1pxm46oo aZB0z9PKMryLyrACja79D9splRJG98DgOnmhu7mxScowqFjNDRKvMAwj9WHCShZYlvYP G+ZRAa5BvBdr1tfMIgSggasARSgj1SbT/pT2DusE/lFUUHkxtsFUW2R+YymQ3B0waC80 f/O/gIa+6PpWNJmSzULrgaDmju7K+KPWDrs8Qqz1Tosa1TpncpL++u8I+U6ReaQcRUp5 ybBRKkDH9Jj7aOyrYz5xRtZBUMawncnmDvYIhAU5oBKKzbExjqX+5si2dwSgWPxwb1zd trVw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=PnvoyOBW; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id b9-20020a633409000000b0054fce84303dsi3718445pga.792.2023.06.15.06.36.37; Thu, 15 Jun 2023 06:36:49 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=PnvoyOBW; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1343810AbjFONLX (ORCPT + 99 others); Thu, 15 Jun 2023 09:11:23 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59322 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1343710AbjFONLO (ORCPT ); Thu, 15 Jun 2023 09:11:14 -0400 Received: from mail-pl1-x631.google.com (mail-pl1-x631.google.com [IPv6:2607:f8b0:4864:20::631]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 648B226B1 for ; Thu, 15 Jun 2023 06:10:51 -0700 (PDT) Received: by mail-pl1-x631.google.com with SMTP id d9443c01a7336-1b4f95833c7so12705665ad.1 for ; Thu, 15 Jun 2023 06:10:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834651; x=1689426651; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=rh1upVsLkWtnKrYRXZBQpn/CVX3v0vcX/4UFjQ1Vcrw=; b=PnvoyOBWI0174VERzdCx/bjEaYkDquh7yUGjQ50/UMkljqo5RjJXjL/cpgyU0TzpL0 eH4VXPKnzVaqjcP0gOrMx+1QHFabhbbyvY/b0lpA7NNL3TpSSbiM5VkBsMKRfz9VcWo2 lFwoUO7O78+d9CNvG3CfhEJFuWdZ8b1+UY+22FceCZ1Z5L8AhIi7hCMxeK3Nv8H36S9l rpau8waC19HwkB9lNxumaKNM/lwcYVUZc1+ee++CYY+F7cyGfZ46ler+HLrq1LcRvZAN eQsUxGjTPIwUCUuGKYO2Lmqr+uiqKzT6QsnoYFz+N2wYgGq3hiijfpQwjmPzO1Qqg6X7 no0g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834651; x=1689426651; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=rh1upVsLkWtnKrYRXZBQpn/CVX3v0vcX/4UFjQ1Vcrw=; b=FPjfkBK4VscN6vbOSofvMw2Qw4FD1Kehmudr4zvuVhzHroHobCxBsS5vEtfrR8T6pp en2esUDEdONuqo7iRVScA9lW1Z4UDFnq44FPd5salKoe8LlxAbmJGeGKnpnn3QUKftdv ZaAlivtHoKwJI8J19zWGRc/1L2tHa2wfkQ7c25vF9fZ2hh08QMwqNynAO+GWz00XNFCI kF9ihrIgts0H6OHBPv1daHPDCPVkH5IxHKOIhxB3DDN++FUH1OscON8JQJbLPYUTz2pF BzwOJASeFASmsRWbJC4FFkfU60UdC4zMoMQpgjdRCYBWF7wtKNIgIbvnnKNF4lgV+HFo Ul8g== X-Gm-Message-State: AC+VfDw9Zj4+JRxytXvRCC5uvjhhEfHzqa2PuQD87HYDluwZlRTM5KRK f/vBkHcaIRVkTV390pYUjsnoGl9/yfFA2Xv5/XE= X-Received: by 2002:a17:902:7042:b0:1af:fd3a:2b7d with SMTP id h2-20020a170902704200b001affd3a2b7dmr12733721plt.48.1686834650878; Thu, 15 Jun 2023 06:10:50 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.47 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:50 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 7/8] maple_tree: replace mas_logical_pivot() with mas_safe_pivot() Date: Thu, 15 Jun 2023 21:08:58 +0800 Message-Id: <20230615130859.21858-8-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768775965614986408?= X-GMAIL-MSGID: =?utf-8?q?1768775965614986408?= Replace mas_logical_pivot() with mas_safe_pivot() and drop mas_logical_pivot() since it won't be used anymore. We can do this since now all nodes will have node limit pivot (if it is not full node). Signed-off-by: Peng Zhang --- lib/maple_tree.c | 33 +++------------------------------ 1 file changed, 3 insertions(+), 30 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index becb4c224e57..4c9f40322f5f 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -728,33 +728,6 @@ mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset) return mas->min; } -/* - * mas_logical_pivot() - Get the logical pivot of a given offset. - * @mas: The maple state - * @pivots: The pointer to the maple node pivots - * @offset: The offset into the pivot array - * @type: The maple node type - * - * When there is no value at a pivot (beyond the end of the data), then the - * pivot is actually @mas->max. - * - * Return: the logical pivot of a given @offset. - */ -static inline unsigned long -mas_logical_pivot(struct ma_state *mas, unsigned long *pivots, - unsigned char offset, enum maple_type type) -{ - unsigned long lpiv = mas_safe_pivot(mas, pivots, offset, type); - - if (likely(lpiv)) - return lpiv; - - if (likely(offset)) - return mas->max; - - return lpiv; -} - /* * mte_set_pivot() - Set a pivot to a value in an encoded maple node. * @mn: The encoded maple node @@ -2202,7 +2175,7 @@ static noinline_for_kasan void mas_store_b_node(struct ma_wr_state *wr_mas, goto b_end; /* Handle new range ending before old range ends */ - piv = mas_logical_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type); + piv = mas_safe_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type); if (piv > mas->last) { if (piv == ULONG_MAX) mas_bulk_rebalance(mas, b_node->b_end, wr_mas->type); @@ -4911,7 +4884,7 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size) min = mas_safe_min(mas, pivots, offset); data_end = ma_data_end(node, type, pivots, mas->max); for (; offset <= data_end; offset++) { - pivot = mas_logical_pivot(mas, pivots, offset, type); + pivot = mas_safe_pivot(mas, pivots, offset, type); /* Not within lower bounds */ if (mas->index > pivot) @@ -7003,7 +6976,7 @@ static void mas_validate_gaps(struct ma_state *mas) gaps = ma_gaps(node, mt); for (i = 0; i < mt_slot_count(mte); i++) { - p_end = mas_logical_pivot(mas, pivots, i, mt); + p_end = mas_safe_pivot(mas, pivots, i, mt); if (!gaps) { if (!mas_get_slot(mas, i)) From patchwork Thu Jun 15 13:08:59 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 108514 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp628620vqr; Thu, 15 Jun 2023 06:17:33 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ5bgoZf8P72UufrAUktx4olXgCAt/JRb3cOdsJOHLx4TSocIRYeXLqNFp0gSjdG6FntMtb+ X-Received: by 2002:a05:6808:bc7:b0:39a:ba9c:ec9 with SMTP id o7-20020a0568080bc700b0039aba9c0ec9mr14791252oik.14.1686835053137; Thu, 15 Jun 2023 06:17:33 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686835053; cv=none; d=google.com; s=arc-20160816; b=b1HGLd+agcb6zkyaKTcrfChRohBUriz1iXkVe74KV+YngPNH1FeiZvhD6jqK1+Vvvd Q+ARsdWdE3h0QOwlrUqBZVAQQW/xFFd002JkNlzuj6rz0OH/9XQZ4r4eLAuRC1XfYWV+ 24du05BYHmc9XDmWFrZ9UR4EgNaf7ZyM67losZPzcAfciHSlRm2frA+8vHDkD6qLIq4E Ot/9lyeva4NTJXu6UL1sJVC5ge+kFxcBx7qeX85VNlFHPLHrw580azcbfDR1CMMTWIZ5 uinpG5Ib6Bmrfn/Si23lBEtUqD+dFxU8Yr34WAbHXIc/o70OKua4Q1btSqkbErkLZIu8 +6uQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=CEErg3d4yT8esB8KpwjYxwMfJsf51/geZ+6n58UDGJs=; b=wao9SLUZj1w3CIhlrHXI9JQ5JDOWZ5ulsEr10+9UO255U9r0xF1VuWrpeXpZ4RZZc1 sdCv7KAdqioSXkW0r9D1QS0WjBZwfuS/B2WLUl2xpw0Cu/JfYewqmY1hvHM/ZsxwQlqW rgqvW0hy5fWoZ5chamKFMeS1WLUBKkGo3ALuiCuVLGN0O0WQcJrFzKFtr4vBceTVMMpj S9SLLVWfgQ9KsP4zJMxK3eILF3d0DD7QYjB3XQyNGLTTXx2PFnE3YRWlmAwI8oDmTJEP IHjiCn0SHRgYmhq2oKRXItwNJ/688NcTxaqe5rvEzz5V6GTqAlCAKxKdWnhhrb+qn314 /KcA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=EF9Lkit8; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id j66-20020a636e45000000b005348b4f79f1si12305127pgc.345.2023.06.15.06.17.18; Thu, 15 Jun 2023 06:17:33 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=EF9Lkit8; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232615AbjFONLc (ORCPT + 99 others); Thu, 15 Jun 2023 09:11:32 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59332 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1343749AbjFONLV (ORCPT ); Thu, 15 Jun 2023 09:11:21 -0400 Received: from mail-pf1-x436.google.com (mail-pf1-x436.google.com [IPv6:2607:f8b0:4864:20::436]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8FB2B2700 for ; Thu, 15 Jun 2023 06:10:56 -0700 (PDT) Received: by mail-pf1-x436.google.com with SMTP id d2e1a72fcca58-666a63f7907so386521b3a.2 for ; Thu, 15 Jun 2023 06:10:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686834656; x=1689426656; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=CEErg3d4yT8esB8KpwjYxwMfJsf51/geZ+6n58UDGJs=; b=EF9Lkit8KeZA+6lEZX30z4AtzxQeXjXaFk3VG1hfh2/OEXDrTUs+QkddvuqbwKFGw5 NNqqQL7MJRL8o5afvaoXGXt4M2Y5EUJhZvfO8yDoT8KKFGuNv4uRv4JQKKveXRRez2CH cpC9z+LFWjAtvwcmvfv1o236zgBYalBIf6twvsjmnqLecvTIgrQrJMwXOCE6tXnTXFMn ctm9NYACNGn6WIX2bZXp0PHMVPzmFZkGkETZdQjMNpURRfxtWpaAKdqsjVwGkcyG/1Et nnhuWEUU1xw2Jry13IAXUIyr1+L4D2uCbd0+m403S9gXx0X5hRfXAZ2XQQ4MIGqEJL4k 3rtg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686834656; x=1689426656; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=CEErg3d4yT8esB8KpwjYxwMfJsf51/geZ+6n58UDGJs=; b=CpVBy0MX9Iy1NR7lulxhqIceILJReRzqp023YcZfOEAuWlFMTtq7w9fTyNPHmIUPKF 9AIQabK/0YVyqp1v/kbNLBRr+nkeTNFUzsv0Ww9oydDFAEYqG3iB9BMqBDuAiMbjzBMf +4cXAujwGM9PERvXBjorAg2m6X1saV5f/AkF36l2Ss+xrLnO7Tsuzun+kASKYGSy89QT C1ZhvdRWbQRgpKEpyIAsfLNyLGKBROp2hHi8yM8K3XTJVkJP/lO6ISm16NXeYVoewO2b fxGaHIUqaMA4/435NaD7OM/oi1PFWM8H59zce+fBgmdNsKY4AF8uad9ww1/xGrXvJl48 kgYQ== X-Gm-Message-State: AC+VfDxpAi/XC22tMyjTpdgtdVJy2Cmw6gTwRJMCWvlj+U8jUD+0fyzf IDWrA/hRWQrINO0NbKFDOJ0DfA== X-Received: by 2002:a05:6a20:72ac:b0:10c:2349:459d with SMTP id o44-20020a056a2072ac00b0010c2349459dmr5255910pzk.11.1686834656065; Thu, 15 Jun 2023 06:10:56 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id x1-20020a170902b40100b001a804b16e38sm14036019plr.150.2023.06.15.06.10.51 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 06:10:54 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 8/8] maple_tree: drop mas_first_entry() Date: Thu, 15 Jun 2023 21:08:59 +0800 Message-Id: <20230615130859.21858-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615130859.21858-1-zhangpeng.00@bytedance.com> References: <20230615130859.21858-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768774753111563622?= X-GMAIL-MSGID: =?utf-8?q?1768774753111563622?= The internal function mas_first_entry() is no longer used, so drop it. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 72 ------------------------------------------------ 1 file changed, 72 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 4c9f40322f5f..3908a3937214 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6658,78 +6658,6 @@ static inline struct maple_enode *mas_get_slot(struct ma_state *mas, offset); } - -/* - * mas_first_entry() - Go the first leaf and find the first entry. - * @mas: the maple state. - * @limit: the maximum index to check. - * @*r_start: Pointer to set to the range start. - * - * Sets mas->offset to the offset of the entry, r_start to the range minimum. - * - * Return: The first entry or MAS_NONE. - */ -static inline void *mas_first_entry(struct ma_state *mas, struct maple_node *mn, - unsigned long limit, enum maple_type mt) - -{ - unsigned long max; - unsigned long *pivots; - void __rcu **slots; - void *entry = NULL; - - mas->index = mas->min; - if (mas->index > limit) - goto none; - - max = mas->max; - mas->offset = 0; - while (likely(!ma_is_leaf(mt))) { - MAS_WARN_ON(mas, mte_dead_node(mas->node)); - slots = ma_slots(mn, mt); - entry = mas_slot(mas, slots, 0); - pivots = ma_pivots(mn, mt); - if (unlikely(ma_dead_node(mn))) - return NULL; - max = pivots[0]; - mas->node = entry; - mn = mas_mn(mas); - mt = mte_node_type(mas->node); - } - MAS_WARN_ON(mas, mte_dead_node(mas->node)); - - mas->max = max; - slots = ma_slots(mn, mt); - entry = mas_slot(mas, slots, 0); - if (unlikely(ma_dead_node(mn))) - return NULL; - - /* Slot 0 or 1 must be set */ - if (mas->index > limit) - goto none; - - if (likely(entry)) - return entry; - - mas->offset = 1; - entry = mas_slot(mas, slots, 1); - pivots = ma_pivots(mn, mt); - if (unlikely(ma_dead_node(mn))) - return NULL; - - mas->index = pivots[0] + 1; - if (mas->index > limit) - goto none; - - if (likely(entry)) - return entry; - -none: - if (likely(!ma_dead_node(mn))) - mas->node = MAS_NONE; - return NULL; -} - /* Depth first search, post-order */ static void mas_dfs_postorder(struct ma_state *mas, unsigned long max) {