From patchwork Tue Jul 11 03:54:37 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 118232 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp228714vqm; Mon, 10 Jul 2023 21:03:41 -0700 (PDT) X-Google-Smtp-Source: APBJJlFKaKX95moBgvKjES6NwczKNjcaGh8Pod02Q0jXFhJQ2ppw8FrCGgjiWgr0F8cU5jwvX60O X-Received: by 2002:a05:620a:2a0c:b0:765:6524:8458 with SMTP id o12-20020a05620a2a0c00b0076565248458mr18085637qkp.36.1689048220748; Mon, 10 Jul 2023 21:03:40 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689048220; cv=none; d=google.com; s=arc-20160816; b=rq/nfaTHQ/1/bJbl/qeYoywMeblnx0XR4zTJGzgYUmgX8MK1LPUNw/EDYDDQA+IUE9 jI47PvD1rv7PRgys+5rFFOE7j9SgDCXeNH0qKrYGgh+TTeGwDU26LCIKyfSTGzcmU76K X1CVSmC/7F9ZkRnO6X+bBu5QwVOFqQn8BbikHDMmqJJYzUp1ZrpA3Yn4HSShy0b7EwkE szTsAnrRIgqe6doSFsNrqsd3Z+f68iPh08THpACeTiWRUxoucJLxUncQZh7cCpXT09dK /FLfNYjQ9z0jCKR7/pyaM9FJGQKB/hYVn4OBsD+vwYJWaHxrKJQK1ZsTJUf3G2z9NNoz PVrA== 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=vnneOZGmz+RJtivDvKZ74LFhvf3KlKhvaFlPPXT7kZI=; fh=81zMPXlJ/0mWSoVHoYJN4yrrEe0a3g481gzTjD4iBRs=; b=b/Zef0e5HB34MMfS8CSxIkIa/K0oIbLcqZz41pyjX3g/lEhA+eik71sXdQQdIRqRdn 6KEX+STTI9EuPIzk8PiljCTy+D1vyjf3VYMey3fqfjdrSDa6+V60Q/RUmmwJP871Jlwn A8jCDEBUf+fJez35l/A7cEZmaadSnJLLgCeEryydkB3ny29d6lYIYFG21s2JiSWQ1Xlm o8FKiO+Sg0dkfDDt8S5UhZ9kKTBx/7okCN/pjWbGfVcsgHY1nt/nKB/L45UfCCsCCRDr ljEHQS4Plf+AlDUIBLkS3MDDYrl5h6uMTphSPyz1exOv8l3nvq47iH/uAj2g491PCVl5 TRZQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=Z4IrWlz1; 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 z6-20020a656646000000b0054ff8291783si682025pgv.424.2023.07.10.21.03.25; Mon, 10 Jul 2023 21:03:40 -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=Z4IrWlz1; 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 S231241AbjGKDzg (ORCPT + 99 others); Mon, 10 Jul 2023 23:55:36 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35080 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231139AbjGKDzY (ORCPT ); Mon, 10 Jul 2023 23:55:24 -0400 Received: from mail-oo1-xc2b.google.com (mail-oo1-xc2b.google.com [IPv6:2607:f8b0:4864:20::c2b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8856BE42 for ; Mon, 10 Jul 2023 20:55:02 -0700 (PDT) Received: by mail-oo1-xc2b.google.com with SMTP id 006d021491bc7-5634808e16eso3725675eaf.2 for ; Mon, 10 Jul 2023 20:55:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047702; x=1691639702; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=vnneOZGmz+RJtivDvKZ74LFhvf3KlKhvaFlPPXT7kZI=; b=Z4IrWlz1AVjCsHQerCU8etu0x4fMRgmj78dqWxOaEVokcj5JlvJ48wbsN1nYAt8aCx GyIG4fljUcmd36IPAIMorw1pVL0WKa1lCiJxTeiR8S2f1WdwstlfNNXOLV/lPYXe6w1h DVjrFkjamSlpBL0rycqTgq+TECck80TZzdXkKOcfQH4QVOG0MGoHytPkEiIPLoB+jvOb bIEAdvF5OtUo3o2laMkrVhKHijhKrDznzeOUJ0gGzpAgJ1tYhDAcKvPIU5b6T4kPx4Gg OKUPDT72H3ElLV4oau0mU8I3UjQjAbd0NEcN69RmvH/J8FLOzK114dRUY492oyqnmudr BFgA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047702; x=1691639702; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=vnneOZGmz+RJtivDvKZ74LFhvf3KlKhvaFlPPXT7kZI=; b=hn5dIHyIlfLSOrZfzIEetLoCnTBlRnsdj8456s9GlWYGDEQu2se17A6Do7u+jo5IDF wwj4LFGqm6QxapxAl3YgSAI8AJECj8TiLynqCr0cxplO2iiaWOTURpXsvsk30YbGxQbz nm0BkkEK6v1667QPWh8TsvPXZegzUAXI99goOVDK8ZSwbutDjsUHlipw0Mwcfr3i6Jwz tly6wcoru++QnmAleaiy8IXvEkMIVhQherNdBil2EgXoYyINHC5zxSGP53WSJsZnVMPf 79W3ca74xxBVzDhPWHCDyCMPQEDPe3zso0Sw2fJDKr2UtMwIQV7cnM6vHqm5fUMxH4bH 1kfw== X-Gm-Message-State: ABy/qLZ4Kn1G6kPTusx/e7OEqlnc9out6J48FKjay7JjpjxEWGhiYZ7r xEH0fc7QmOfo7Vjj9OaknhLj5g== X-Received: by 2002:a05:6358:5e02:b0:134:c8ee:e451 with SMTP id q2-20020a0563585e0200b00134c8eee451mr10966324rwn.13.1689047701778; Mon, 10 Jul 2023 20:55:01 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.54.58 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:01 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang , stable@vger.kernel.org, Geert Uytterhoeven Subject: [PATCH v2 1/8] maple_tree: set the node limit when creating a new root node Date: Tue, 11 Jul 2023 11:54:37 +0800 Message-Id: <20230711035444.526-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-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_BLOCKED, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE,URIBL_BLOCKED autolearn=unavailable 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: INBOX X-GMAIL-THRID: 1771095427336612726 X-GMAIL-MSGID: 1771095427336612726 Set the node limit of the root node so that the last pivot of all nodes is the node limit (if the node is not full). This patch also fixes a bug in mas_rev_awalk(). Effectively, always setting a maximum makes mas_logical_pivot() behave as mas_safe_pivot(). Without this fix, it is possible that very small tasks would fail to find the correct gap. Although this has not been observed with real tasks, it has been reported to happen in m68k nommu running the maple tree tests. Link: https://lore.kernel.org/linux-mm/CAMuHMdV4T53fOw7VPoBgPR7fP6RYqf=CBhD_y_vOg53zZX_DnA@mail.gmail.com/ Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett Cc: Cc: Geert Uytterhoeven --- lib/maple_tree.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index d3072858c280..f55e59bd9122 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3692,7 +3692,8 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry) mas->offset = slot; pivots[slot] = mas->last; if (mas->last != ULONG_MAX) - slot++; + pivots[++slot] = ULONG_MAX; + mas->depth = 1; mas_set_height(mas); ma_set_meta(node, maple_leaf_64, 0, slot); From patchwork Tue Jul 11 03:54:38 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 118241 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp236782vqm; Mon, 10 Jul 2023 21:29:38 -0700 (PDT) X-Google-Smtp-Source: APBJJlGpDslEy/pfl8FBAZUPrVPzUViW+KUDSXe1XEPRha9Dxvc/R3AGO+yQSqE+AbnLouXMXEzj X-Received: by 2002:a17:902:7007:b0:1b8:ae11:bf5b with SMTP id y7-20020a170902700700b001b8ae11bf5bmr14708403plk.62.1689049778203; Mon, 10 Jul 2023 21:29:38 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689049778; cv=none; d=google.com; s=arc-20160816; b=y5phhiPx0IEquXzz3Vikw2c3wtBTuJft/doh4GuOcvTJiqRdNylqi7Kq0JbBLS4Bqy TVpt9zi52cbjFitlf1dOUkG46Nvo3mgkyeG3iLK4GimlaTfsaAFe179M7UDNJRtjhh/8 Y+XPyhL/vBhbaYAU4+OAn5FD1ryL9CPNgYA7ZImylJ7xGe2Pi/CXTgcHgXD1tVL75H7e hFDSP/B7tGyqrv2ePMkDibHtNNCrSQk0ra2ZP6vO+x13wI07KBjZXv3xsixLayXnn3JB 21yMLO0rBF4aEXB/I5s3ieXuS49fSnPSbK7M9Uvp7oNiy1hypFtLrn6tFJRunxdQBIv5 Wo0Q== 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=fTNORhAMfZiekvn/WZoJTK6LhdTh4U3lAjASoHlporQ=; fh=U74fmUEemPw7sqchHJfHUOA5IBfFk+e2fZn/jtR8IqU=; b=KnJAm5l473LZiTmvG6VjgtwndoRwSyqaRottg8Tu8dmgSA3GG8xFSGvgn7pFWF41Tw oA9PWcbZTiYUx8CNwCND25q54nTYWkLxaoS1DKJf4jPWCi5A1bsep6JRb8p09ujNs2AF r2IjNwK/y/2U0dczAdH4L0V0ro2/CjDAZhjHDaOQ5E2C0SHTRyzlIZcV2QI6hIDUi9fX OGqtruP/ER5KOdXtGqA1obDkARen8rfJuFIFqaKWR/x3ujS7DKWcQadcDK8MK19hSyWC zOPwaiiULRyYh4GHgr8XtkHnBb+QOgVZspWapdBUXLf/2J+Olm6aCGRDxbgI+AXdWzQB +r6w== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=Rxbx43is; 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 f4-20020a170902ce8400b001b8c6890612si884219plg.594.2023.07.10.21.29.25; Mon, 10 Jul 2023 21:29:38 -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=Rxbx43is; 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 S231139AbjGKDzn (ORCPT + 99 others); Mon, 10 Jul 2023 23:55:43 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35104 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231131AbjGKDzY (ORCPT ); Mon, 10 Jul 2023 23:55:24 -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 2BC7CE4D for ; Mon, 10 Jul 2023 20:55:05 -0700 (PDT) Received: by mail-pl1-x631.google.com with SMTP id d9443c01a7336-1b8b318c5a7so38828905ad.3 for ; Mon, 10 Jul 2023 20:55:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047704; x=1691639704; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=fTNORhAMfZiekvn/WZoJTK6LhdTh4U3lAjASoHlporQ=; b=Rxbx43isig3S+GFU16br5sALnoQtHUSEfGe8cb+ol6pqYx3UiUAaexdoL7DR65ZV81 3BODyot5ZjoWbtgXrORsNGEWWtJ8jdaf2v8QLo99182QN4+QD5t7R2T05RsHZ+/W79Zv TwWyCEEUja+pliatca1lfjHTT5nZ6/CwqIIW8MyHzRJ/10vt2Kw7wPEfjwzbDzjkbW8L oRk3casJ7rRn20xOrC09xX6p1x+1YVSWI1WJNd8e+wU6yNu5GRbwhqi7LWhFFPDyuAWz +6A0BSCS9J/6Mu2Ku/InixWET9G+pAzYMPbE3oiCwyI7VkhzmRHkrRpGcj64xjJvPZ0Q BbmQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047704; x=1691639704; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=fTNORhAMfZiekvn/WZoJTK6LhdTh4U3lAjASoHlporQ=; b=CqXT+dOr2SBMPew24VIEQbhcacscxKJf4P5WIp+bzD3N4DvxqqDzYQOcJUQ+R4mJaB LuP5qCQTgbN3UI+JWYN54zvQMDTYis7PlW62Pv/bIwCaou4+JxE050eSUuNDkcGxSheP EV2E3DQvfa5TI8v+uXvJkQTrkBBzWuIY466EHyVyF3wvIzLqoNL2cmRptzUoAsf6fQSg oLkYyqgrGWenOLmqoFYE9YM6nBwheN8Y1ddOt7au+ZVF/8REbaGjH3n/nj4qDZLhnHW+ j1Vh6Rk1xQPK4W/E+9f3bxN5eFgFyNOTYhZMUCq1BN4beptiW+D5Dwp4ADUG3JllFJG6 4NKQ== X-Gm-Message-State: ABy/qLZ7x6BZBaRVmslDIFaSL+4z3RjFcSSK3aXb3UXtRLYBAYazzcwh BCrpYoQIdABCSOxGqntJ3iSyOQ== X-Received: by 2002:a17:903:26d3:b0:1b8:a88c:4dc6 with SMTP id jg19-20020a17090326d300b001b8a88c4dc6mr14392136plb.45.1689047704708; Mon, 10 Jul 2023 20:55:04 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.02 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:04 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v2 2/8] maple_tree: don't use MAPLE_ARANGE64_META_MAX to indicate no gap Date: Tue, 11 Jul 2023 11:54:38 +0800 Message-Id: <20230711035444.526-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-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_BLOCKED, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE,URIBL_BLOCKED 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: INBOX X-GMAIL-THRID: 1771097060254862478 X-GMAIL-MSGID: 1771097060254862478 Do not use a special offset to indicate that there is no gap. When there is no gap, offset can point to any valid slots because its gap is 0. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- include/linux/maple_tree.h | 2 -- lib/maple_tree.c | 13 ++----------- 2 files changed, 2 insertions(+), 13 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index e18ecbefc7f7..4e004d86c780 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -29,14 +29,12 @@ #define MAPLE_NODE_SLOTS 31 /* 256 bytes including ->parent */ #define MAPLE_RANGE64_SLOTS 16 /* 256 bytes */ #define MAPLE_ARANGE64_SLOTS 10 /* 240 bytes */ -#define MAPLE_ARANGE64_META_MAX 15 /* Out of range for metadata */ #define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 1) #else /* 32bit sizes */ #define MAPLE_NODE_SLOTS 63 /* 256 bytes including ->parent */ #define MAPLE_RANGE64_SLOTS 32 /* 256 bytes */ #define MAPLE_ARANGE64_SLOTS 21 /* 240 bytes */ -#define MAPLE_ARANGE64_META_MAX 31 /* Out of range for metadata */ #define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 2) #endif /* defined(CONFIG_64BIT) || defined(BUILD_VDSO32_64) */ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index f55e59bd9122..6a8982146338 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1610,8 +1610,6 @@ ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt, * mas_max_gap() - find the largest gap in a non-leaf node and set the slot. * @mas: The maple state. * - * If the metadata gap is set to MAPLE_ARANGE64_META_MAX, there is no gap. - * * Return: The gap value. */ static inline unsigned long mas_max_gap(struct ma_state *mas) @@ -1628,9 +1626,6 @@ static inline unsigned long mas_max_gap(struct ma_state *mas) node = mas_mn(mas); MAS_BUG_ON(mas, mt != maple_arange_64); offset = ma_meta_gap(node, mt); - if (offset == MAPLE_ARANGE64_META_MAX) - return 0; - gaps = ma_gaps(node, mt); return gaps[offset]; } @@ -1662,10 +1657,7 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, ascend: MAS_BUG_ON(mas, pmt != maple_arange_64); meta_offset = ma_meta_gap(pnode, pmt); - if (meta_offset == MAPLE_ARANGE64_META_MAX) - meta_gap = 0; - else - meta_gap = pgaps[meta_offset]; + meta_gap = pgaps[meta_offset]; pgaps[offset] = new; @@ -1678,7 +1670,6 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, ma_set_meta_gap(pnode, pmt, offset); } else if (new < meta_gap) { - meta_offset = 15; new = ma_max_gap(pnode, pgaps, pmt, &meta_offset); ma_set_meta_gap(pnode, pmt, meta_offset); } @@ -2076,7 +2067,7 @@ static inline void mab_mas_cp(struct maple_big_node *b_node, end = j - 1; if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) { unsigned long max_gap = 0; - unsigned char offset = 15; + unsigned char offset = 0; gaps = ma_gaps(node, mt); do { From patchwork Tue Jul 11 03:54:39 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 118236 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp230002vqm; Mon, 10 Jul 2023 21:07:03 -0700 (PDT) X-Google-Smtp-Source: APBJJlEj461qoGXLcM9qQMofRcUFQ4JbdYitQtajixueQ4xRP5k9gLoz98SBFdXRZXwsedos7aV+ X-Received: by 2002:a05:620a:d88:b0:767:a4b8:8d4 with SMTP id q8-20020a05620a0d8800b00767a4b808d4mr15332918qkl.0.1689048423454; Mon, 10 Jul 2023 21:07:03 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689048423; cv=none; d=google.com; s=arc-20160816; b=H0Xuj5ZMN+8zLbNU7PEeCgp2+h3Sf1Dvj7rYTngYL8gKThND5yG9GMf2QtoolgfHUg dklyJ9VY9wle2IHf7XRwtWmggrYiNH4TSpfXGXqgzBt6QsWPeq+LNC5ery1tNuBKGSxC 3Vkx8c3ZIOFNlJgxqI/0KDU3dYbv9sC9C+vACFQ/eCAM+0/yO2IhOfHE3uZ1TmRaoiRk rbA8Eazwwg3iZ44sB4hljrpjVUYA6VnrzRxoO8G8U4ZgSLGyvniTYqJylBeXB3Ix7b1N 0gGhgadQM69FySTKHCRV6uxVFC965c5t04R3eEOpSKe/W4pkDF6CIQZ2MSw19m5P9aSc iwog== 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=8nUv2eBUflOVJLrJw9mH1jkiLbgnM6ws75Pkn4jd+6E=; fh=U74fmUEemPw7sqchHJfHUOA5IBfFk+e2fZn/jtR8IqU=; b=jzIKqCwm7lMHLshu5cTxmb3OoCSOHeaJgI+6eKWraJX2cFGcFDSw90QARX7PWsclQN 2bI8HzMrcpfYM2km1ywyI0a7qvgm3CLDbmMkuFH+KUfuPmYd4eYrWOH7BtwQYZQXhW5X hiVmtySzoz+nfMb0mRQdFJScTogj93bi2hE/595wW9yNun8tfoiyUvc/T0uwayMIbYhj B0HCU6rza3O0NhEwmTJJTQOIBtjKNobk/cenYv4hdmliCQb9ueaUSeM54t0G0MBGurQK Dcatr/1JWjERItbSOT0OYn5x40bh/AuVP0d/cME0umn0px14AyM1jhHCYleuAB4A6dpT aS9Q== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b="ba93/Clp"; 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 r5-20020a632045000000b0053ee9b21820si732153pgm.72.2023.07.10.21.06.50; Mon, 10 Jul 2023 21:07:03 -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="ba93/Clp"; 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 S230467AbjGKDzO (ORCPT + 99 others); Mon, 10 Jul 2023 23:55:14 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35110 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230457AbjGKDzK (ORCPT ); Mon, 10 Jul 2023 23:55:10 -0400 Received: from mail-oo1-xc33.google.com (mail-oo1-xc33.google.com [IPv6:2607:f8b0:4864:20::c33]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 53F0EE57 for ; Mon, 10 Jul 2023 20:55:08 -0700 (PDT) Received: by mail-oo1-xc33.google.com with SMTP id 006d021491bc7-560b7ac3cbfso3764694eaf.2 for ; Mon, 10 Jul 2023 20:55:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047707; x=1691639707; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=8nUv2eBUflOVJLrJw9mH1jkiLbgnM6ws75Pkn4jd+6E=; b=ba93/ClplBNkeT536iWxDiRxrvDKLuk5KzbRIGlkNS/wjSUDSw0YG2fdY+wocAKY5f QIcaK5gsT/UKH1/j1gmInqnQydQtLdFwMoEaVF8Y0JynNst6O2va9pZ58iQ78jbDHz4R ndraKp96OKm6JzDpx9nPiOKqPRN6160Rbdcb2ka3yKuAnldcB1vGQArUyhhiXyJmqeu2 DFn5VI06R0dhs/J0QOYB+u8lmCI5Mtr0NqjaEOG+OIxk4KMQHM16azCfVmq9ldF6/EYQ M/n4PHfRcWMdYBEYL/VcaBdPlvczwae5dmhcz/2jNwPFqIr4m2+KUs+sIdqrqveJOrb2 UMtA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047707; x=1691639707; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=8nUv2eBUflOVJLrJw9mH1jkiLbgnM6ws75Pkn4jd+6E=; b=IH0XITFDDkGKoYhBniSbzmMVczUwm5DyGLvU9LP7Wo7/4cKXI/xNDystSx3md24gxS IyvqA5TKAaZctE4kqVvotysps18pvAPVV6FmxrQQxFGq/OCHDY2ljriBdg5wJucSLva1 8cIj7EE6wnTZUWYh+OROGJ18SksifLdUHzPNvlRgtB7OULme7FOwf2BV15Twf7cPQVuV Xet42VN/iTfxP5shU1PRfmsc0L9AteEg4CyEeTftsZ9hksER+pk8fo+MyRieQlwZutcY u/iMfaPc+5M9lEKKzE/5/ADITGADMByryqDjQrnil7896Z3dB73ugVVfiL8CRJVIn4gG RpeQ== X-Gm-Message-State: ABy/qLYnguV8GhT90EtZMa+cIHrhDmRLOgsO29Sb9cvOkg1XEh7UGjZ5 yMxNaMoGLVIGVwF9ZlMrmJLAlw== X-Received: by 2002:a05:6358:c0f:b0:135:4dcf:9a2a with SMTP id f15-20020a0563580c0f00b001354dcf9a2amr10478949rwj.7.1689047707525; Mon, 10 Jul 2023 20:55:07 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.05 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:07 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v2 3/8] maple_tree: make mas_validate_gaps() to check metadata Date: Tue, 11 Jul 2023 11:54:39 +0800 Message-Id: <20230711035444.526-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-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_BLOCKED, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE,URIBL_BLOCKED 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: INBOX X-GMAIL-THRID: 1771095639180575566 X-GMAIL-MSGID: 1771095639180575566 Make mas_validate_gaps() check whether the offset in the metadata points to the largest gap. By the way, simplify this function. Add the verification that gaps beyond the node limit are zero. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 78 ++++++++++++++++++++++++++---------------------- 1 file changed, 42 insertions(+), 36 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6a8982146338..a5776fab1875 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6983,15 +6983,16 @@ EXPORT_SYMBOL_GPL(mt_dump); static void mas_validate_gaps(struct ma_state *mas) { struct maple_enode *mte = mas->node; - struct maple_node *p_mn; + struct maple_node *p_mn, *node = mte_to_node(mte); + enum maple_type mt = mte_node_type(mas->node); unsigned long gap = 0, max_gap = 0; unsigned long p_end, p_start = mas->min; - unsigned char p_slot; + unsigned char p_slot, offset; unsigned long *gaps = NULL; - unsigned long *pivots = ma_pivots(mte_to_node(mte), mte_node_type(mte)); - int i; + unsigned long *pivots = ma_pivots(node, mt); + unsigned int i; - if (ma_is_dense(mte_node_type(mte))) { + if (ma_is_dense(mt)) { for (i = 0; i < mt_slot_count(mte); i++) { if (mas_get_slot(mas, i)) { if (gap > max_gap) @@ -7004,52 +7005,59 @@ static void mas_validate_gaps(struct ma_state *mas) goto counted; } - gaps = ma_gaps(mte_to_node(mte), mte_node_type(mte)); + gaps = ma_gaps(node, mt); for (i = 0; i < mt_slot_count(mte); i++) { - p_end = mas_logical_pivot(mas, pivots, i, mte_node_type(mte)); + p_end = mas_logical_pivot(mas, pivots, i, mt); if (!gaps) { - if (mas_get_slot(mas, i)) { - gap = 0; - goto not_empty; - } - - gap += p_end - p_start + 1; + if (!mas_get_slot(mas, i)) + gap = p_end - p_start + 1; } else { void *entry = mas_get_slot(mas, i); gap = gaps[i]; - if (!entry) { - if (gap != p_end - p_start + 1) { - pr_err("%p[%u] -> %p %lu != %lu - %lu + 1\n", - mas_mn(mas), i, - mas_get_slot(mas, i), gap, - p_end, p_start); - mt_dump(mas->tree, mt_dump_hex); - - MT_BUG_ON(mas->tree, - gap != p_end - p_start + 1); - } - } else { - if (gap > p_end - p_start + 1) { - pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", - mas_mn(mas), i, gap, p_end, p_start, - p_end - p_start + 1); - MT_BUG_ON(mas->tree, - gap > p_end - p_start + 1); - } + MT_BUG_ON(mas->tree, !entry); + + if (gap > p_end - p_start + 1) { + pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", + mas_mn(mas), i, gap, p_end, p_start, + p_end - p_start + 1); + MT_BUG_ON(mas->tree, gap > p_end - p_start + 1); } } if (gap > max_gap) max_gap = gap; -not_empty: + p_start = p_end + 1; if (p_end >= mas->max) break; } counted: + if (mt == maple_arange_64) { + offset = ma_meta_gap(node, mt); + if (offset > i) { + pr_err("gap offset %p[%u] is invalid\n", node, offset); + MT_BUG_ON(mas->tree, 1); + } + + if (gaps[offset] != max_gap) { + pr_err("gap %p[%u] is not the largest gap %lu\n", + node, offset, max_gap); + MT_BUG_ON(mas->tree, 1); + } + + MT_BUG_ON(mas->tree, !gaps); + for (i++ ; i < mt_slot_count(mte); i++) { + if (gaps[i] != 0) { + pr_err("gap %p[%u] beyond node limit != 0\n", + node, i); + MT_BUG_ON(mas->tree, 1); + } + } + } + if (mte_is_root(mte)) return; @@ -7059,10 +7067,8 @@ static void mas_validate_gaps(struct ma_state *mas) if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) { pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap); mt_dump(mas->tree, mt_dump_hex); + MT_BUG_ON(mas->tree, 1); } - - MT_BUG_ON(mas->tree, - ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap); } static void mas_validate_parent_slot(struct ma_state *mas) From patchwork Tue Jul 11 03:54:40 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 118240 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp236688vqm; Mon, 10 Jul 2023 21:29:18 -0700 (PDT) X-Google-Smtp-Source: APBJJlFTsxJXBNOdPzU38Hbwk1jetop1n3rsAkVsQLLxDf8BOUso26G1c1cXLmVdVkAxyoN4Iaav X-Received: by 2002:a17:902:9a03:b0:1b7:ca9c:4f5c with SMTP id v3-20020a1709029a0300b001b7ca9c4f5cmr19208417plp.28.1689049758074; Mon, 10 Jul 2023 21:29:18 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689049758; cv=none; d=google.com; s=arc-20160816; b=kY06rqVh1jAsngIacNRXbL7tAq562wOrX1vrjSWEFRe3tKxBHnQp3+7y/IGxO+ryG5 kAGvPfkBxXWhv3RkSizwsGk8pbcS1rt1J5lAFFfFOLVIHVL/bKvhzDCwgxMLyMMFL/oP SwEsf+k6vPIHWiTgIG2HsYdsPwBkPE0tuIMplVOnGNZQ1MjSQA5HnF+kxFLO5MYXuqAl ZtAalx5yJI+Gnru54xzbzUi/gHPmfpPYIUrgJ1NMWISKE12WcDCc1TlgYc8qGJYkrQs2 1gA/fwsobWwx7aDB3+aA+gON7JhLy6ZlmchFH/OlRtADNy8j1hvkhsLNHVlAkz91JEbu eLKg== 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=trWG5ZcTEhQeGdiIh695WKCYOeE3HbrZ9Lquw5Sy0DA=; fh=U74fmUEemPw7sqchHJfHUOA5IBfFk+e2fZn/jtR8IqU=; b=SomvmnzBs0TE3EVEvwmV3lZtYj1/S0tOoy/gXo6epEubqFuSpS2CwlGI0H/AAcbOM0 14AOIEZGtV/Eaph3fGbxdzXknHQVgobPoQ0hwLKkKHF/rbCZGs6BCGqfhXdg/j+4w7ZY n6NbHHCgCC4ViN5eeexW3IAPGXnC8JDCM7DSu6dLgA2nKX6iAwYVeLFbUjFP3NE/3Yvy cvIKiEgUp67TvKgRNT8gTG0lv5Kg+HxCnqnBhQGKoORJB8dnHXBu1qmBd4bIfbRiRXg4 RUK5ib68EJnsTWd/4bFb9WGsN8wFOgo6Dfpcd2GNaXOBbR6uXcWKnEx6hK62PjC0mTwa JiiQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=RBwCD953; 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 f4-20020a170902ce8400b001b8c6890612si884219plg.594.2023.07.10.21.29.04; Mon, 10 Jul 2023 21:29:18 -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=RBwCD953; 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 S231145AbjGKD4A (ORCPT + 99 others); Mon, 10 Jul 2023 23:56:00 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35146 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231219AbjGKDze (ORCPT ); Mon, 10 Jul 2023 23:55:34 -0400 Received: from mail-pl1-x62b.google.com (mail-pl1-x62b.google.com [IPv6:2607:f8b0:4864:20::62b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1C5B4E5C for ; Mon, 10 Jul 2023 20:55:11 -0700 (PDT) Received: by mail-pl1-x62b.google.com with SMTP id d9443c01a7336-1b89b75dc1cso40859145ad.1 for ; Mon, 10 Jul 2023 20:55:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047710; x=1691639710; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=trWG5ZcTEhQeGdiIh695WKCYOeE3HbrZ9Lquw5Sy0DA=; b=RBwCD953n8uZsMTFBTHHBrqSeGPAwgTiNB4mn19QAWfXCNEYcpGV1kO3pwrVNg8yiO 4ChpEv1ST7jhjL5P3juHp3AxjrYpZOoUZVhD2YQEdnop9cODo0HrY8a0kzrHUNaUIvkj O1spSqlg3rieSeSLBfw8jVSeQ+y/GqBPmyB5Avs2d2g6U18ZtSVO+yG2hZ8l0KZkCgPf 9sjA0l8IF0bLaMPCEax3vXMEOqTK9Cbi/czByHRMN1o+xEe1N1f+PJx1K+l/9/PeL/cF /WpOb15CGoZm3QwOcSnNOf9bHQ47bs7GLBz7f6r8m2UpoVAIMjkZhz0huGnDN+G6zPf1 oDpg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047710; x=1691639710; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=trWG5ZcTEhQeGdiIh695WKCYOeE3HbrZ9Lquw5Sy0DA=; b=LmK3u0j4pqpDSWkauYFSd+kh27Jm7LHXLDEOVQWQpYKDYQ+NTPHZ/YigeRrTw0recJ rukRUlLKMqa4gPmTYAXgaMrv2AgmdA7xNbdqhHCa30DrjZZ5yX5CoXoQDiLyQJziPmVZ rWiEcgGnkjTnp21wgfcUPcAKdlBmW0vP6k7QkQBkk1bPKd3aRPeo22621e37PI1mj6AJ smdrZ/cx5WBd3CgNdm9PDxGLPWtb8QONKgz1948bgzv3/VvOLXwaGf0DXge9Tj9aLOQN B+KYOcM9YhFRO8ygPuV4B+OgsJPyE4cLfJeLpyFVc6sCiuaG4tnfaDW+N0EqMHrWPwAs L25g== X-Gm-Message-State: ABy/qLYxcPOtXS9kVa0YJoY1eSeH06CVCOV8Zm1+2HAb4tUoVaHNioAy OHHJigHkBDwzIzDtmwEY9oWCkw== X-Received: by 2002:a17:903:2441:b0:1b8:a39e:ff4b with SMTP id l1-20020a170903244100b001b8a39eff4bmr26118175pls.32.1689047710631; Mon, 10 Jul 2023 20:55:10 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.07 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:10 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v2 4/8] maple_tree: fix mas_validate_child_slot() to check last missed slot Date: Tue, 11 Jul 2023 11:54:40 +0800 Message-Id: <20230711035444.526-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-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,URIBL_BLOCKED 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: INBOX X-GMAIL-THRID: 1771097039180394824 X-GMAIL-MSGID: 1771097039180394824 Don't break the loop before checking the last slot. Also here check if non-leaf nodes are missing children. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index a5776fab1875..f750ebef595f 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7119,11 +7119,12 @@ static void mas_validate_child_slot(struct ma_state *mas) for (i = 0; i < mt_slots[type]; i++) { child = mas_slot(mas, slots, i); - if (!pivots[i] || pivots[i] == mas->max) - break; - if (!child) - break; + if (!child) { + pr_err("Non-leaf node lacks child at %p[%u]\n", + mas_mn(mas), i); + MT_BUG_ON(mas->tree, 1); + } if (mte_parent_slot(child) != i) { pr_err("Slot error at %p[%u]: child %p has pslot %u\n", @@ -7138,6 +7139,9 @@ static void mas_validate_child_slot(struct ma_state *mas) mte_to_node(mas->node)); MT_BUG_ON(mas->tree, 1); } + + if (i < mt_pivots[type] && pivots[i] == mas->max) + break; } } From patchwork Tue Jul 11 03:54:41 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 118243 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp238731vqm; Mon, 10 Jul 2023 21:35:16 -0700 (PDT) X-Google-Smtp-Source: APBJJlGWhPeuwW2S0CdT8UEypgxGwha+VcVQuLy0xcgCE6zIDL4Z4W7fFMifYKxr/R39xumZQi5s X-Received: by 2002:a17:906:5946:b0:982:bbc7:15c0 with SMTP id g6-20020a170906594600b00982bbc715c0mr1910815ejr.66.1689050116107; Mon, 10 Jul 2023 21:35:16 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689050116; cv=none; d=google.com; s=arc-20160816; b=dmMK48OnYkG8tHfph/9mFBDq41t1hXKWyv83jldBCxCjHF6twcuAFIPSrMXdH0/mDc h6YGyB7qhGMvMEZxOjC4K8pw96J2s9rXIZ42fUYuebY7KvqDj9ibA6apR0xRjg/dZjJ1 TfPLbhHIAobJwCeE2vb/AXm2I0fWrTTLK/wFpszyz7nn3U2QzestGy4G9RQx4OvzaR6r zgQw2gaEXtRe1joQkUdgzDQ/2iWNni3OFpFUXpitzkTtGFWt3DfLrC7ODPwQGT9pMCSq 6g5K7lVadzf5APrWeDRitd5SYodttBKJrcSfTk8pgFaB7fbMRNcdcVzFnDvsXQRLH5QV D9sg== 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=IIlxgDREFu6LlOiulF242HoL+hhnsQmd+OCvzSb0WTY=; fh=U74fmUEemPw7sqchHJfHUOA5IBfFk+e2fZn/jtR8IqU=; b=MyjhdSp+b//bDr1QhDMgsk/1MpQwOlWnn4RXZUSdmD+CRipTsL++p4PPirxQAnj/Ka E7Rqijlebo2OnnqzIjUC4AyWgrXZVOq/FwqnIPSDVdEm6UHkfvm4xAQs/pyUKZUyPxeX SHQXOW12pdntqyBu15tbmTy4hbJ2qXNLzjcFsO+J0SW4qQmpgDXH7r0bS4Pwekiudt6r wXvJB/Z1eDNXCvQ1sSLlkinaNtZzTngy81fG2VYQ4r6tWUvNfSC9eZPCn5zm1qB/vdB0 GTMkugIHO9MDviNxxyKLofwZ+3elcpKdM/FmiYpNxdSLPUx6Fi8FGYGNqm6nf94GDr1v tUBA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=CmxeKRs4; 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 bx17-20020a170906a1d100b00993a68a3af5si1081210ejb.529.2023.07.10.21.34.52; Mon, 10 Jul 2023 21:35:16 -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=CmxeKRs4; 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 S230505AbjGKDzT (ORCPT + 99 others); Mon, 10 Jul 2023 23:55:19 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35152 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230474AbjGKDzP (ORCPT ); Mon, 10 Jul 2023 23:55:15 -0400 Received: from mail-oi1-x22e.google.com (mail-oi1-x22e.google.com [IPv6:2607:f8b0:4864:20::22e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3FB841BC for ; Mon, 10 Jul 2023 20:55:14 -0700 (PDT) Received: by mail-oi1-x22e.google.com with SMTP id 5614622812f47-3a3e1152c23so3678792b6e.2 for ; Mon, 10 Jul 2023 20:55:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047713; x=1691639713; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=IIlxgDREFu6LlOiulF242HoL+hhnsQmd+OCvzSb0WTY=; b=CmxeKRs4gLnyTQYT+priT1hS2JdubJC5Dw/d7haZ/eUhfQ5DQq8hVuNMfRYn0YrKfY Ere1opP+H09ay1uUCmD9kh4UFVcpIbi2SR7/v45hmGGedCsFMQP3NOr8I/oahWOEG28L FHyHWHEStwZS08cCmBqv+KoceYbwE0k6jnZbqJUp6YvpwzUaFpP3wuoCSAXRC90ZVPbe k/DY6/mOEVsGugOyMCCTxcwo56s6Afhsnl9I6hbNxTGvNYu938n6abLjmyi171Pg75zw ytktelZVA+im/0Vpnwlp4JUajcIfcJ3I6n3qCfLCrBjvPngSvJou6nOA9Hu6O7kxYWyl bFsQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047713; x=1691639713; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=IIlxgDREFu6LlOiulF242HoL+hhnsQmd+OCvzSb0WTY=; b=IriQrcCcKfMCrHpcn4R5EAAFHg5fyWd1xMVQUvSEPoEuEw6/zVfgFOePKiobm+W9tW u8+EDPAWE4999kDcAWYYq99wiSEgEcdsCqLeaRA4dkGxziM3RKmjokLbnVpuIREfEBA3 WqueCksmAZSRAtzYCqMBUBrG2nsRqULZNXYJBmbojJS4eTThj6yjsHeChUBvdM+hrgg2 96FFTC/QK9YwC5kpv9MEafTb5F9JBPKnDnvn90ErjOGzdvJmSj15GiuX5DbbeWhVyiB6 kO1ou1XjtnTVRAzkhfjlCvp/rnJUot/M/HRN8yYysDQpecUXrj8q+h0mx/vkIWA+7ADs g5xw== X-Gm-Message-State: ABy/qLbaFSHgEhLlHM9zcm2HlUtTmJdXiSUKY3OO95Ec+rvpn3cf+tY4 B8507gCAF6uZ5NvAn27zuNVMgw== X-Received: by 2002:a05:6358:9929:b0:134:c984:ab87 with SMTP id w41-20020a056358992900b00134c984ab87mr13040684rwa.4.1689047713510; Mon, 10 Jul 2023 20:55:13 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.11 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:13 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v2 5/8] maple_tree: make mas_validate_limits() check root node and node limit Date: Tue, 11 Jul 2023 11:54:41 +0800 Message-Id: <20230711035444.526-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-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_BLOCKED, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE,URIBL_BLOCKED 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: INBOX X-GMAIL-THRID: 1771097414441127223 X-GMAIL-MSGID: 1771097414441127223 Update mas_validate_limits() to check root node, check node limit pivot if there is enough room for it to exist and check data_end. Remove the check for child existence as it is done in mas_validate_child_slot(). Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 30 ++++++++++++++---------------- 1 file changed, 14 insertions(+), 16 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index f750ebef595f..072532fa18ee 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7146,7 +7146,9 @@ static void mas_validate_child_slot(struct ma_state *mas) } /* - * Validate all pivots are within mas->min and mas->max. + * Validate all pivots are within mas->min and mas->max, check metadata ends + * where the maximum ends and ensure there is no slots or pivots set outside of + * the end of the data. */ static void mas_validate_limits(struct ma_state *mas) { @@ -7156,26 +7158,15 @@ static void mas_validate_limits(struct ma_state *mas) void __rcu **slots = ma_slots(mte_to_node(mas->node), type); unsigned long *pivots = ma_pivots(mas_mn(mas), type); - /* all limits are fine here. */ - if (mte_is_root(mas->node)) - return; - for (i = 0; i < mt_slots[type]; i++) { unsigned long piv; piv = mas_safe_pivot(mas, pivots, i, type); - if (!piv && (i != 0)) - break; - - if (!mte_is_leaf(mas->node)) { - void *entry = mas_slot(mas, slots, i); - - if (!entry) - pr_err("%p[%u] cannot be null\n", - mas_mn(mas), i); - - MT_BUG_ON(mas->tree, !entry); + if (!piv && (i != 0)) { + pr_err("Missing node limit pivot at %p[%u]", + mas_mn(mas), i); + MAS_WARN_ON(mas, 1); } if (prev_piv > piv) { @@ -7198,6 +7189,13 @@ static void mas_validate_limits(struct ma_state *mas) if (piv == mas->max) break; } + + if (mas_data_end(mas) != i) { + pr_err("node%p: data_end %u != the last slot offset %u\n", + mas_mn(mas), mas_data_end(mas), i); + MT_BUG_ON(mas->tree, 1); + } + for (i += 1; i < mt_slots[type]; i++) { void *entry = mas_slot(mas, slots, i); From patchwork Tue Jul 11 03:54:42 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 118233 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp228775vqm; Mon, 10 Jul 2023 21:03:52 -0700 (PDT) X-Google-Smtp-Source: APBJJlEGyIRnC/orx1B1+UuTOp7RUIMtAFUgaSusg1KNo3yEYhKqZEgQWQo1jGdKkVkySJBz9Oef X-Received: by 2002:a05:6808:1302:b0:3a1:df16:2eed with SMTP id y2-20020a056808130200b003a1df162eedmr18131897oiv.30.1689048232688; Mon, 10 Jul 2023 21:03:52 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689048232; cv=none; d=google.com; s=arc-20160816; b=WpkMMd725xZ3EeEXifiFtlAv27YboVuwkDKNv+zaCnvQ7O4o4zimp+kLpLVhXzQW8Z vKCqB9p4KJ6ST9a7uVi4IDoZBwN9WlOcv3q1nx/516vRikfWanNrl5mhgH41YqYpKzQ5 HzQhFoMw15w8n1fHG+n+1c8vh0xHXCVI3+Jly0JSUihg9pN77R8n9sPIxoy0nUwJFk9X NrZo5NrDpZMIcHnWTnRv6wBZLC5ICeiZJH+OsZVEINHWT0SPcPXYixG67iIA5mFXI48Y iWppfG3slgkZN3H9hr/oXdZMwRf8vMjsO3V/DKAJMJe9Ubgq7DX+U/kJwUHzbgKxJbAp /bfQ== 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=VB6Zk8yx2k+1HDLx/vyMhcB3cYhsChcAv55Bv4rEWns=; fh=U74fmUEemPw7sqchHJfHUOA5IBfFk+e2fZn/jtR8IqU=; b=B8x30ZgkZgKRnhGUGcPeyptkYPlV/kFnD0MaioV0YQYN9vV/TahrQ5gMU6z7NT2TeY 27Ituq+Eaqo8aQF3oJowpomCBjIkrB0Ufuqy3B8o+cvrM9pqn2Y4WF13XT2K3hHKeG0C mwZSXNH20SvZi/mIVRo1WVFiXNX9rw1p+U618cQS3Fwc11F6n2usFCF96nhBmn3kKHa4 IvQdmJw0m1/Uqz3u0Wz6Up47UVn0bPfQtEgfDapkJnPHqGe/87rvBq3rj09PgqbOs+7f pwwtcykFOQHZB7inYpiIjoH6iuACTEXvjfeMeHwBJA2EZCfUJPPiAwSCoHfkUljqeAI2 fWJg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=LSWgQLIm; 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 126-20020a630084000000b0055ba896f567si714552pga.585.2023.07.10.21.03.39; Mon, 10 Jul 2023 21:03:52 -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=LSWgQLIm; 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 S231260AbjGKD4D (ORCPT + 99 others); Mon, 10 Jul 2023 23:56:03 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35196 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231238AbjGKDzg (ORCPT ); Mon, 10 Jul 2023 23:55:36 -0400 Received: from mail-qv1-xf2e.google.com (mail-qv1-xf2e.google.com [IPv6:2607:f8b0:4864:20::f2e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 562F0E59 for ; Mon, 10 Jul 2023 20:55:17 -0700 (PDT) Received: by mail-qv1-xf2e.google.com with SMTP id 6a1803df08f44-635eb5b0320so35857276d6.3 for ; Mon, 10 Jul 2023 20:55:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047716; x=1691639716; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=VB6Zk8yx2k+1HDLx/vyMhcB3cYhsChcAv55Bv4rEWns=; b=LSWgQLIm1PFWUmQi+43SqOstxpJoc3S5KiF0uBqZBj+yhFOyw31mF12pOmarXSQTwl ftLznRUeQW71nK3PQ10DqNTXANC+OzuxYtBuC6dEParOiiStsUCAqTUuuFV87HYUI7ju uOT3WQoFhn8iH8thH0rnasi0ozRlnz9v4G5nx3FuT0HEGBIojQ/P+EgU7XeHHOcdTwEh rl+muaqKcxNVqi50mRjNkFJGUYhKZNbiZ5e5AgdmWuRmWeKMzDDYIM9TwleGcI9Tyy4U r/iL1UYkK2+O5mX+8p+GRA3Z6xTt3Qt+4LVhqHd9F8RAsfoU1ZlSZcV1hsh0tp7hekj6 kCDQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047716; x=1691639716; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=VB6Zk8yx2k+1HDLx/vyMhcB3cYhsChcAv55Bv4rEWns=; b=dNkbFa0iHFpWhkvce60hePIg2/M3RCIcwL6K+Baz+IQIyuoYrjPpfhsJ612E7oZFMe EWBR6P+ukm4Ua5AqN4GLKNvB0DlfxNcNClPbSakWtD5sYL7ydarQRuYxpfBuyGn5J71m fVWWcvO0VND7kPCkU2XSBDBc9ZhfZGFO1dXaNgH0Xb3sdVpBul40f22Ip3vweTc2sAB7 RQ12hngk5udDIr3l6FWxZ98Zglir0opwaqyKkX9+qUGkQW8n34lHSN6lNKrf9LVZvkth vjg1Ud5w6DZHVgrPrSbzZM2S+92SqPxFPjugMRdBTzzG1Se1Irhr1gNdLvvcf4T/d5Ya Vldg== X-Gm-Message-State: ABy/qLZxi7vOJ7nxpM+foN4CxiSGMo/9rVJGRCsJrWB6Q3EJDmSW3+G1 nR9DLoHTqerH7t51bVECLqEMF7D+MnHp4GkNCEo= X-Received: by 2002:a0c:e28c:0:b0:635:de52:8385 with SMTP id r12-20020a0ce28c000000b00635de528385mr13630151qvl.65.1689047716426; Mon, 10 Jul 2023 20:55:16 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.13 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:16 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v2 6/8] maple_tree: update mt_validate() Date: Tue, 11 Jul 2023 11:54:42 +0800 Message-Id: <20230711035444.526-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-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_BLOCKED, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE,URIBL_BLOCKED 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: INBOX X-GMAIL-THRID: 1771095439491204913 X-GMAIL-MSGID: 1771095439491204913 Instead of using mas_first_entry() to find the leftmost leaf, use a simple loop instead. Remove an unneeded check for root node. To make the error message more accurate, check pivots first and then slots, because checking slots depend on the node limit pivot to break the loop. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 19 +++++++++---------- 1 file changed, 9 insertions(+), 10 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 072532fa18ee..1ad11799e197 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7270,21 +7270,20 @@ void mt_validate(struct maple_tree *mt) if (!mas_searchable(&mas)) goto done; - mas_first_entry(&mas, mas_mn(&mas), ULONG_MAX, mte_node_type(mas.node)); + while (!mte_is_leaf(mas.node)) + mas_descend(&mas); + while (!mas_is_none(&mas)) { MAS_WARN_ON(&mas, mte_dead_node(mas.node)); - if (!mte_is_root(mas.node)) { - end = mas_data_end(&mas); - if (MAS_WARN_ON(&mas, - (end < mt_min_slot_count(mas.node)) && - (mas.max != ULONG_MAX))) { - pr_err("Invalid size %u of %p\n", end, - mas_mn(&mas)); - } + end = mas_data_end(&mas); + if (MAS_WARN_ON(&mas, (end < mt_min_slot_count(mas.node)) && + (mas.max != ULONG_MAX))) { + pr_err("Invalid size %u of %p\n", end, mas_mn(&mas)); } + mas_validate_parent_slot(&mas); - mas_validate_child_slot(&mas); mas_validate_limits(&mas); + mas_validate_child_slot(&mas); if (mt_is_alloc(mt)) mas_validate_gaps(&mas); mas_dfs_postorder(&mas, ULONG_MAX); From patchwork Tue Jul 11 03:54:43 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 118231 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp226370vqm; Mon, 10 Jul 2023 20:57:26 -0700 (PDT) X-Google-Smtp-Source: APBJJlEoxWhfNaruPtuMOm+IRCdaX2+xVMfT0qINSIBdp5+UjZa3bvx2RLtHXTWGAfgFRmX48acw X-Received: by 2002:a05:6512:32d0:b0:4f8:6dfd:faa0 with SMTP id f16-20020a05651232d000b004f86dfdfaa0mr11172255lfg.2.1689047845914; Mon, 10 Jul 2023 20:57:25 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689047845; cv=none; d=google.com; s=arc-20160816; b=KBvzkap/GVTSWisi18YULjeBrI2InR5NAjSRpme6sUJVNUwZoFIc+g2IFTVuU0gU3F QnOATQaVxsDpiY6p7+kDLucqJ6nAmKUb5YZRhshUYOk0QDkL6uzmRyfnhf8rJZf2P2j+ FA9+jaDWU55n+P/YxaGdF+a7Lxmuyy369HFlqofSyfURBtTDLPvnAYSvgXcS2Z5NXqtZ ljxDNgS6ca/T2JpvrHMzUTo3rDncX2Qxp6HjNlhC+TjaveFOMYkTrRAsbEd7uLFFAAHz qmimFxC3tO9V39bn647vSVszODQ9V6Rb1+rT5wU6INTl+QShgGGFYLWIZYixrDveTOrC PoSg== 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=DbarY+W3CHTFGsKxfdT0v+U7T4eLSEDHZXXVmyxXdNU=; fh=U74fmUEemPw7sqchHJfHUOA5IBfFk+e2fZn/jtR8IqU=; b=taXKdSv7ZrZMcizKDZSfX1t35QXvH/NgTHFGQXz7sgf1FEHdpEtFP9GtPcsquqYZUP +wn2jROvX21VoNL03Gb3kPB0+PQJJtFpb6svd54kxf0sZ3R4mk4Yae68cDuFPY1eLFN/ YrahUYhq4VjIq0foIHrRw/wMp6peutEI8GKPL6pZgLUM1ubKpZHMrNd4HCPNWCawu1LD zffWEFPKSyDwmTZEqfa5bnKqVpiynww040yxFxqWur83JrD3GFti7dM5bIdL5DKMJTUl tGUhuIEJ/j7VUGQQZA1WfYLesOKVpq+kprZYktSYN4Qrz//lUt4uqrw4qi6Tut+S9g6C VpUg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=iULxRDLC; 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 e20-20020a056402089400b0051e27e00a96si1061219edy.126.2023.07.10.20.57.03; Mon, 10 Jul 2023 20:57:25 -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=iULxRDLC; 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 S231205AbjGKDzc (ORCPT + 99 others); Mon, 10 Jul 2023 23:55:32 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35284 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231136AbjGKDzY (ORCPT ); Mon, 10 Jul 2023 23:55:24 -0400 Received: from mail-oi1-x22e.google.com (mail-oi1-x22e.google.com [IPv6:2607:f8b0:4864:20::22e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2BDD3E69 for ; Mon, 10 Jul 2023 20:55:20 -0700 (PDT) Received: by mail-oi1-x22e.google.com with SMTP id 5614622812f47-3a412653335so689510b6e.1 for ; Mon, 10 Jul 2023 20:55:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047719; x=1691639719; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=DbarY+W3CHTFGsKxfdT0v+U7T4eLSEDHZXXVmyxXdNU=; b=iULxRDLCYTw8LCbKROb4TXPoBYnA1v18DTCUhinG5JOrzgwyPzolG/GbPjP0Ghw877 ZeFhZ6pfEHNACpMhdSEdi8M0CIttf3djc5hRG285cAP0/TdP5VIo1CJhiMnrYxLq2Br4 TEqxemWUZJVJquPT6NkviWia/MOosyK5GroVKnwfWkNPWYGHKqQef5iwhDlsHOTZiv5s zvAcmE2osWi2vEjvqYWeu+/GQVnyI/4GTgGh5h0cTmgsCE+9IIyvbxoaE62+oKyUht+O n1EFaO4uQsZ5zcdikocUiGLossOZB6cy46l+rMKDTASMmpejL7ZdcoSghLjWjYdkEzQq WZTA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047719; x=1691639719; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=DbarY+W3CHTFGsKxfdT0v+U7T4eLSEDHZXXVmyxXdNU=; b=HDtyRLM+ItX9swBELfpOO6pEX0A+6ue0qj5rL8u+TIStq3KoLXsZcU3rN8qxK2Cnvd KK1XMpa99k7Sn8UUFtsJl0Puxk8/tlRCcOX9pRpPlociOUOEns4Rg2UZ1AfQUo1ttFP5 wou+GsetwANiOvepCorh9CUXlSBwO+EwHsxj9LYr10cdyoALeBLNKrmb8mQbYhkvdg4c GxoG25JAlAZWsaDT4dMzpvE8Kn8JIDJN09gqAx2iJSOlNgiex/HenQz1wNOiiaWJsWqO uSXXfX8kqLNEaGPUntzUOfue53yd2477kZyHah1Xdtryxm/wxFyl+EbpeT06TGBtu+FA GfHA== X-Gm-Message-State: ABy/qLYK6iltl0S5uU7jYxmyfoy3Fy+rK8NdfOz+l9MLvD4s0F61DF5m 7wZIOZ7UEY7U0ACyGDWasRDc0Q== X-Received: by 2002:a05:6358:5923:b0:135:43da:b16d with SMTP id g35-20020a056358592300b0013543dab16dmr13986782rwf.11.1689047719453; Mon, 10 Jul 2023 20:55:19 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.17 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:19 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v2 7/8] maple_tree: replace mas_logical_pivot() with mas_safe_pivot() Date: Tue, 11 Jul 2023 11:54:43 +0800 Message-Id: <20230711035444.526-8-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-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_BLOCKED, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE,URIBL_BLOCKED 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: INBOX X-GMAIL-THRID: 1771095033709698452 X-GMAIL-MSGID: 1771095033709698452 Replace mas_logical_pivot() with mas_safe_pivot() and drop mas_logical_pivot() since it won't be used anymore. We can do this since now all nodes will have node limit pivot (if it is not full node). Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 33 +++------------------------------ 1 file changed, 3 insertions(+), 30 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 1ad11799e197..5eb5eede2727 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -728,33 +728,6 @@ mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset) return mas->min; } -/* - * mas_logical_pivot() - Get the logical pivot of a given offset. - * @mas: The maple state - * @pivots: The pointer to the maple node pivots - * @offset: The offset into the pivot array - * @type: The maple node type - * - * When there is no value at a pivot (beyond the end of the data), then the - * pivot is actually @mas->max. - * - * Return: the logical pivot of a given @offset. - */ -static inline unsigned long -mas_logical_pivot(struct ma_state *mas, unsigned long *pivots, - unsigned char offset, enum maple_type type) -{ - unsigned long lpiv = mas_safe_pivot(mas, pivots, offset, type); - - if (likely(lpiv)) - return lpiv; - - if (likely(offset)) - return mas->max; - - return lpiv; -} - /* * mte_set_pivot() - Set a pivot to a value in an encoded maple node. * @mn: The encoded maple node @@ -2202,7 +2175,7 @@ static noinline_for_kasan void mas_store_b_node(struct ma_wr_state *wr_mas, goto b_end; /* Handle new range ending before old range ends */ - piv = mas_logical_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type); + piv = mas_safe_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type); if (piv > mas->last) { if (piv == ULONG_MAX) mas_bulk_rebalance(mas, b_node->b_end, wr_mas->type); @@ -4934,7 +4907,7 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size) min = mas_safe_min(mas, pivots, offset); data_end = ma_data_end(node, type, pivots, mas->max); for (; offset <= data_end; offset++) { - pivot = mas_logical_pivot(mas, pivots, offset, type); + pivot = mas_safe_pivot(mas, pivots, offset, type); /* Not within lower bounds */ if (mas->index > pivot) @@ -7007,7 +6980,7 @@ static void mas_validate_gaps(struct ma_state *mas) gaps = ma_gaps(node, mt); for (i = 0; i < mt_slot_count(mte); i++) { - p_end = mas_logical_pivot(mas, pivots, i, mt); + p_end = mas_safe_pivot(mas, pivots, i, mt); if (!gaps) { if (!mas_get_slot(mas, i)) From patchwork Tue Jul 11 03:54:44 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 118235 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:a6b2:0:b0:3e4:2afc:c1 with SMTP id c18csp229890vqm; Mon, 10 Jul 2023 21:06:43 -0700 (PDT) X-Google-Smtp-Source: APBJJlFJg5xRbufCYunGxIpYTwSC/Wjd4b4FxcgT9vhJuNCZC2jCq992ue2LZSDkNXYPxONznF8E X-Received: by 2002:a05:6a20:605:b0:106:5dff:5dc6 with SMTP id 5-20020a056a20060500b001065dff5dc6mr13765494pzl.16.1689048403324; Mon, 10 Jul 2023 21:06:43 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1689048403; cv=none; d=google.com; s=arc-20160816; b=HrKae0nCr4nKJ2OPf2HglXuky0Y+OD+sRzH499KVfJ72Kb3FErPdLSuzs4vQ1B8Xgr +bmBCk7ED6WDaRHzhQlI70Ck56Gr5kIq9hvJoLEFW1QJMq5M6inyBwr4pDLtWzgtFJK3 bEWBsWpHyXOxas/NMP4KXmNliTaBkzPW68Oa/AFylNYmrQgEblofbd6JFczrtxiTYU/7 NRrx7KcrmDSslZ7ncs7wTd9IwDpejuocZDIgiVlbnsSOI61BiAm/pf6RSxSQMsPQfxem qr4SaAmiJw4gj2WKUVCejE7sInx3D97NCbGMZoIYjghawwHY34HvF82OVFfZxscvK1tF UNKA== 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=9OtSvFihiDnLwRXPS16aFXYvoQJZK7qgLbCrmPMdkz4=; fh=U74fmUEemPw7sqchHJfHUOA5IBfFk+e2fZn/jtR8IqU=; b=stGw7GsoUrOvAN9/QXHBMlhybW47nbpby08gp7tm6A56Bhh8/IYNoEd0DtdlEtvtrc K6prZ5Xp7/QXBweSAnj8Y1ZRnKQDQ/RiSbxhtvpFQfRdRjYi9FtneEKZU1S02Kp+QiW2 zpEQkxGCEXbe5pnx4aUawilEMSiW9nj9MnWcWQ/duQ41zSQ3mUMS1D/E4sXTf15EwD7C ABTHoUBzs2BrO47EtGqudvOZFvwcVKBs9hHK7LZom+MCQdAf3Ipz6elKcuyXQSyxpg4t zojJG3KLxc8rhCNR2SnvQuRkUdiuch3ldLTbM+8NrR9iQ6pO1DQELHTrCn8oqVuylk+d D8xw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=FG0CUQd2; 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 r5-20020a632045000000b0053ee9b21820si732153pgm.72.2023.07.10.21.06.29; Mon, 10 Jul 2023 21:06:43 -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=FG0CUQd2; 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 S231510AbjGKD4Q (ORCPT + 99 others); Mon, 10 Jul 2023 23:56:16 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35162 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231179AbjGKDzv (ORCPT ); Mon, 10 Jul 2023 23:55:51 -0400 Received: from mail-pl1-x629.google.com (mail-pl1-x629.google.com [IPv6:2607:f8b0:4864:20::629]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AE43510C2 for ; Mon, 10 Jul 2023 20:55:22 -0700 (PDT) Received: by mail-pl1-x629.google.com with SMTP id d9443c01a7336-1b8bd586086so39283265ad.2 for ; Mon, 10 Jul 2023 20:55:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1689047722; x=1691639722; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=9OtSvFihiDnLwRXPS16aFXYvoQJZK7qgLbCrmPMdkz4=; b=FG0CUQd2LZZyzjMyMvHehaF916WG7DrINm7YYqYYtJ5WS2xrMsL6v25DynuNojHGcY wxJHLbsZd3VzymebJe3AbpxVxh8p92JQt1W7oYL6JGZPHChw5F2mpgzCFQjPgG/pRgrG R9SdhrLWfRfpui4ajHnLe7B+Ce7DB6fG7EHTKc6H4b6krsWfzkslA3A6kJ65n57EMi67 r7wGoSifkbrij6l+nuuX6+RLAvIa2M1VBQhNUZmrtD8uC9zIzrLOoK3lLbRmmWWH00zi F5dCS62bKbff4y7LupnA6PVUNnnxTM6u1aOsADrPYPfQ8pjREh97a5YCVgY0pq0yCm7r /dzg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689047722; x=1691639722; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=9OtSvFihiDnLwRXPS16aFXYvoQJZK7qgLbCrmPMdkz4=; b=G0NP3W+3fPLpFQ1DbsgJPjkwo3ODmuZ5aDzqICwDsAfHIz1Yt9hnbgq8wXcs+1yLwa PlSHxVYjl1rtct1EQNBnDv3qN6nrnkI/UHC64TAunhD4PyZ1JvZ6r5ZniCIhoF9wb6lx o61+ZwYpd61BSqJ+0qm2+cPMEHg72tM7sUBhH5G1A3KXRTnyOp8DKbM5b/88UNyBW5oe 9tHxVuYM5zdcSWZHVCNFcsylY5SW95HDyR/nCoauHpR+HfpdTH6HKltaYpaH0i8M2mS7 XISYbNcAcFO141TmJxuGGDFdQeCg4tGRNXs1H7+o/MGYWhjLOVtd4KAyq7Bl45EncgRF azQw== X-Gm-Message-State: ABy/qLYHTfNN0aGwGAle2dmB4hT3LXO8kbb82/IYVRUrAFrwyW1WPmbM em0nf83MPdpULKH8+Dn7r4IKtw== X-Received: by 2002:a17:902:ecc2:b0:1b9:d439:c009 with SMTP id a2-20020a170902ecc200b001b9d439c009mr10667995plh.57.1689047722210; Mon, 10 Jul 2023 20:55:22 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.243]) by smtp.gmail.com with ESMTPSA id b15-20020a170903228f00b001b872c17535sm688329plh.13.2023.07.10.20.55.19 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Mon, 10 Jul 2023 20:55:22 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v2 8/8] maple_tree: drop mas_first_entry() Date: Tue, 11 Jul 2023 11:54:44 +0800 Message-Id: <20230711035444.526-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230711035444.526-1-zhangpeng.00@bytedance.com> References: <20230711035444.526-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-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_BLOCKED, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE,URIBL_BLOCKED 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: INBOX X-GMAIL-THRID: 1771095618506917039 X-GMAIL-MSGID: 1771095618506917039 The internal function mas_first_entry() is no longer used, so drop it. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 72 ------------------------------------------------ 1 file changed, 72 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 5eb5eede2727..bd4557eeb42c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6662,78 +6662,6 @@ static inline struct maple_enode *mas_get_slot(struct ma_state *mas, offset); } - -/* - * mas_first_entry() - Go the first leaf and find the first entry. - * @mas: the maple state. - * @limit: the maximum index to check. - * @*r_start: Pointer to set to the range start. - * - * Sets mas->offset to the offset of the entry, r_start to the range minimum. - * - * Return: The first entry or MAS_NONE. - */ -static inline void *mas_first_entry(struct ma_state *mas, struct maple_node *mn, - unsigned long limit, enum maple_type mt) - -{ - unsigned long max; - unsigned long *pivots; - void __rcu **slots; - void *entry = NULL; - - mas->index = mas->min; - if (mas->index > limit) - goto none; - - max = mas->max; - mas->offset = 0; - while (likely(!ma_is_leaf(mt))) { - MAS_WARN_ON(mas, mte_dead_node(mas->node)); - slots = ma_slots(mn, mt); - entry = mas_slot(mas, slots, 0); - pivots = ma_pivots(mn, mt); - if (unlikely(ma_dead_node(mn))) - return NULL; - max = pivots[0]; - mas->node = entry; - mn = mas_mn(mas); - mt = mte_node_type(mas->node); - } - MAS_WARN_ON(mas, mte_dead_node(mas->node)); - - mas->max = max; - slots = ma_slots(mn, mt); - entry = mas_slot(mas, slots, 0); - if (unlikely(ma_dead_node(mn))) - return NULL; - - /* Slot 0 or 1 must be set */ - if (mas->index > limit) - goto none; - - if (likely(entry)) - return entry; - - mas->offset = 1; - entry = mas_slot(mas, slots, 1); - pivots = ma_pivots(mn, mt); - if (unlikely(ma_dead_node(mn))) - return NULL; - - mas->index = pivots[0] + 1; - if (mas->index > limit) - goto none; - - if (likely(entry)) - return entry; - -none: - if (likely(!ma_dead_node(mn))) - mas->node = MAS_NONE; - return NULL; -} - /* Depth first search, post-order */ static void mas_dfs_postorder(struct ma_state *mas, unsigned long max) {