From patchwork Thu Jun 15 08:42: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: 13280888 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 15B68EB64DC for ; Thu, 15 Jun 2023 08:43:16 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 858346B0074; Thu, 15 Jun 2023 04:43:15 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 791C58E0001; Thu, 15 Jun 2023 04:43:15 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 56DD16B007B; Thu, 15 Jun 2023 04:43:15 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 443736B0074 for ; Thu, 15 Jun 2023 04:43:15 -0400 (EDT) Received: from smtpin05.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 18ED14092C for ; Thu, 15 Jun 2023 08:43:15 +0000 (UTC) X-FDA: 80904342750.05.F171146 Received: from mail-pf1-f174.google.com (mail-pf1-f174.google.com [209.85.210.174]) by imf30.hostedemail.com (Postfix) with ESMTP id 40D478000E for ; Thu, 15 Jun 2023 08:43:13 +0000 (UTC) Authentication-Results: imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=KJqooEgR; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.174 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1686818593; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=h6we1XLVpJvFDKToAtCSdGG7AESFIveH8POVJHK7ygw=; b=NylcG13P+Mwumn6n6hP4j3BUhG7yGgYQEQNVXdfFlhZNw2zdoNiEprytKxE2EBMGM4+5tr KiA86lZP08W+xm2x6LPqz6TD2/BI+8YzaSoO31rEennBHvT3YieC2zyu3HSCo4e43ctGeO N8CyuEKOhZ2L7kUdkXKNPL6qWHjA9Vk= ARC-Authentication-Results: i=1; imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=KJqooEgR; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.174 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686818593; a=rsa-sha256; cv=none; b=OPjojnWgv8TKTbOEp6n5zQUERvdAoVkNLYkrsnmosnf4qd10OeCFYoktCQZpG+8uL//VsZ LId1ZdaAx8uFqw4dlIdn7gDdr/2deg/jxraYP+5zyQqwW2dl5l977KVvfTeFCn0VfB37YN C7iqRD31MJgYfJEOjHrRcJtaaSfFfLs= Received: by mail-pf1-f174.google.com with SMTP id d2e1a72fcca58-652328c18d5so5769053b3a.1 for ; Thu, 15 Jun 2023 01:43:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686818592; x=1689410592; 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=h6we1XLVpJvFDKToAtCSdGG7AESFIveH8POVJHK7ygw=; b=KJqooEgRb2iG8G1YEwQaqnb6yEyBC3iktDlEuCSBmlCh99KVdbC4uXKwyOEWcJ/vOP DIqo86HSGslqIkVliO7JkAyqCgamZvnuTKyKqN4AbrShWmLI8k5Ca37sxCWu0JtQEQ9K ol0WmAJ3q9Y2U4SIj4Vx039gw/b6Hns2IJDVLd99kDe5nheMueLD1C9GADpQ7Xqq0y6S 992BUsR57Tu/AIwGg5EIyEIr7FlnvDWdZ2OGQBBbIBiKEp1+lnu066CqqEsTMIn7mRCo +ag3+4ZmKY4vks40xwKEB5VEbwCyTezKBcyE443UrMi+13WctUK8zwBk/BSkby+dhEDv 8kMQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686818592; x=1689410592; 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=h6we1XLVpJvFDKToAtCSdGG7AESFIveH8POVJHK7ygw=; b=K5rjh8kKY4aNl/1NWrE3p5JZJBowI/xPM8mDOwh56I1PuekmwQPkZ7t/7Cqqj3TBHL kK/b6JbznJYsmt1fFuXemC3g7/KzdioJEKnexCqgDIvVFabOxi3dbl1IUk2UCfjVRL6O 4QYCbwafec9ATcnad4rU+Ly6i7jr63cELtuo5Xxp/juBE5GN/if6JYAFOF+NLkjRjTML dJMHkyNdK4iBq+mmB0tvRjjpaF1HEKtI1qpU+fLc4BBT+oMism5L2OczE+G9Pvje9GAq 9BCMCsKEeNk6WCoS6t5SVL4JaVYaKaY6uZBkwcZAVMQ+bCA41okP6hu66AB181HSvUZw Dmsw== X-Gm-Message-State: AC+VfDxDFmAlooyOBNgy5rlfUlxAjH/MZcUo42riLFw58GRHcG+8yWjn AO1fCNKUN6zHVwGkVXqwxnmIBQ== X-Google-Smtp-Source: ACHHUZ7OxUHpAAt4DVa7Yj5aKyir5I7RaKxitjppVwOvFNh7V119bUWSksBzFLFq7Hpwse3+/gV1zQ== X-Received: by 2002:a05:6a20:8419:b0:10b:bad9:1d31 with SMTP id c25-20020a056a20841900b0010bbad91d31mr3987449pzd.26.1686818592167; Thu, 15 Jun 2023 01:43:12 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id i21-20020aa78b55000000b0064fe06fe712sm11139783pfd.129.2023.06.15.01.43.09 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 01:43:11 -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 v3 1/4] maple_tree: add test for mas_wr_modify() fast path Date: Thu, 15 Jun 2023 16:42:58 +0800 Message-Id: <20230615084301.97701-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615084301.97701-1-zhangpeng.00@bytedance.com> References: <20230615084301.97701-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 40D478000E X-Rspam-User: X-Rspamd-Server: rspam04 X-Stat-Signature: 7hce1jdfnqkttmx4p6gx16j3x7stnnq1 X-HE-Tag: 1686818593-218710 X-HE-Meta: U2FsdGVkX1+mXwSvvBf03EHSVVNSLWLqAKoXxPF2LaWcXZa/vOWX389Y80fBY6C6fvL6hc9gbhztsEjmlFyX9obrKDqP4GU+9T/LHl5Dz8bx2rwkPNK6aR0XXCuKPMgYdXJtKu9h4a07a+kFbDTG3HKF9ejEY3dPN6vpOln2opqImFShKphLy1yMKkKuTXe5V4unPOlO3w20oUt7sj3HYo0YmytPQQAlkf/rLzxJshuJmU9MkfIYDG26UXrbW5J9/1yxVVNUAlWiZW33KyRAYp8kXeRZdK3thvxkmLFe+9nSS40pDylNoYqYjPx2+vP7M+WcyJ8WdYcrZhAGayrl1ofMfPHjEQVQNWNHWIzFsdnJE2ScoAFqTqxF3ZdOfxH+uleBqPay874SAwSiSKeWPs+FWg0EBQ7MQ1Urx3jg8Xufkl/W5M+4cJkqloSaGjbrIwJJtmPWMBy6MSE5XmIXyvDgYrahba4o6ljMLIULxOp4r+F9wif00iz+uimGRfT/U0aYUYRPljmyAN9vCnwB6Q+NB2o2jyzFWgWkH361SVKLcKPeur4R6nXI4hG1aZ9teW3cquFovPj9/47ykQ2UcJ6j+/8cbfMoh7KUptNCP4rCJ4JobHtx55Lc0aC/ciGrJ6BLXhnca6kjIl0HZTMyKZ69rdQKq4toF3Yjh6zDHumVsyPGxzxWeXxwGqp/QLNgXDZ5FdX3czWU8jgnNye2wP4G6VIUSE3YG+ObBDFeVMFZUUEZgQ0ysgVVSOgaDJluarXdWxztFof3LwR6Ac745IDtqrV+aYsXekvTkvHcNOWNJ3yqciCR/N7cL70SZU0MGxLokOJGr6/n9Ru1cxwYcSEBd5IsIj9PYrOz1LnAQ2Dm/UReScOfDKnGbb3pL5bTniPEFQUsi6LU9fJw1fDKMrNqZtdibm9ek8NLnTDNG7u808XeI0pPsv3LAmlPFc9uc3pCewJs7/ity8e/fdC HrJp3pEc 807kP0hq1hYtJnKWursUHImoCjPVi9YVV/xeVZZ90ZzR73pG0vY/yrt37y2+vBb4xn10cLMdyjsjsS7d1goD9o47xirXSRscJhHpHbd1A+r9iEJ6fTEEWaS7Y9QTiYS37UH2cnSWbddxU6DmN/NIZ95pD03a8eHaE4Bl2NBfy28Jcrra5v3rnO+ZQbGaRiQC/HE4H2dmVU3+LGpnWCz1ErLSO4cuY16BSNDYvjKQfKsx3MOUNhb703Jm2ryC6nQBFO7z2BbX6S0r59t1Gj7wsoN8jiimjyh4BV9oScPGXbJDg1gvvmbsgiCHh347hiOTFBtNvxrSDXRxiVp1JzN03dXv2FYH964tuunxO49UFebd25b9D5IlJqdVeFskzPFjCzs08ARIcwvnEhF6I666vLsOgCpU2KWKHMWKA/i2zHMM3JDUenWOpJxZmJaiqTsTIyw9Sg27L282jmIE= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Add tests for all cases of mas_wr_append() and mas_wr_slot_store(). Signed-off-by: Peng Zhang --- lib/test_maple_tree.c | 65 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 65 insertions(+) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 15d7b7bce7d6..9403472af3d7 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1159,6 +1159,71 @@ static noinline void __init check_ranges(struct maple_tree *mt) MT_BUG_ON(mt, !mt_height(mt)); mtree_destroy(mt); + /* Check in-place modifications */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + /* Append to the start of last range */ + mt_set_non_kernel(50); + for (i = 0; i <= 500; i++) { + val = i * 5 + 1; + val2 = val + 4; + check_store_range(mt, val, val2, xa_mk_value(val), 0); + } + + /* Append to the last range without touching any boundaries */ + for (i = 0; i < 10; i++) { + val = val2 + 5; + val2 = val + 4; + check_store_range(mt, val, val2, xa_mk_value(val), 0); + } + + /* Append to the end of last range */ + val = val2; + for (i = 0; i < 10; i++) { + val += 5; + MT_BUG_ON(mt, mtree_test_store_range(mt, val, ULONG_MAX, + xa_mk_value(val)) != 0); + } + + /* Overwriting the range and over a part of the next range */ + for (i = 10; i < 30; i += 2) { + val = i * 5 + 1; + val2 = val + 5; + check_store_range(mt, val, val2, xa_mk_value(val), 0); + } + + /* Overwriting a part of the range and over the next range */ + for (i = 50; i < 70; i += 2) { + val2 = i * 5; + val = val2 - 5; + check_store_range(mt, val, val2, xa_mk_value(val), 0); + } + + /* + * Expand the range, only partially overwriting the previous and + * next ranges + */ + for (i = 100; i < 130; i += 3) { + val = i * 5 - 5; + val2 = i * 5 + 1; + check_store_range(mt, val, val2, xa_mk_value(val), 0); + } + + /* + * Expand the range, only partially overwriting the previous and + * next ranges, in RCU mode + */ + mt_set_in_rcu(mt); + for (i = 150; i < 180; i += 3) { + val = i * 5 - 5; + val2 = i * 5 + 1; + check_store_range(mt, val, val2, xa_mk_value(val), 0); + } + + MT_BUG_ON(mt, !mt_height(mt)); + mt_validate(mt); + mt_set_non_kernel(0); + mtree_destroy(mt); + /* Test rebalance gaps */ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); mt_set_non_kernel(50); From patchwork Thu Jun 15 08:42: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: 13280889 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3602CEB64D9 for ; Thu, 15 Jun 2023 08:43:19 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id C9BB18E0001; Thu, 15 Jun 2023 04:43:18 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id BFDE76B007B; Thu, 15 Jun 2023 04:43:18 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id A77418E0001; Thu, 15 Jun 2023 04:43:18 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 96C6C6B0078 for ; Thu, 15 Jun 2023 04:43:18 -0400 (EDT) Received: from smtpin08.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 74706120B4C for ; Thu, 15 Jun 2023 08:43:18 +0000 (UTC) X-FDA: 80904342876.08.BBC88DE Received: from mail-pf1-f182.google.com (mail-pf1-f182.google.com [209.85.210.182]) by imf02.hostedemail.com (Postfix) with ESMTP id 95C3980006 for ; Thu, 15 Jun 2023 08:43:16 +0000 (UTC) Authentication-Results: imf02.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=f5u5ND5n; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf02.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.182 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1686818596; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=FpzykzsbiMOLk6qot3spisUo8VNsB6lkGRakXgvX2Lw=; b=mDkAAKx6fDqnLUQX15R7pUGZlXcsnGNjOf+G0nsqfAkVAUUFZgM/cVPVjCr/okqxf+biop 7tSfSLKyCLkQJKGdRQOp0QniVceGm+AnnR9KzXlIkCuaFr5w9mOAqnsLOyA5b4vdIKEMlp MAz1e20wfaN7Vn/p05fYK5ybHUOLzV4= ARC-Authentication-Results: i=1; imf02.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=f5u5ND5n; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf02.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.182 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686818596; a=rsa-sha256; cv=none; b=5DedxLX6MQIhBWpxfuZ3psxqab9txoMyrmSh5hpOufQ+HzenpLlsPR7EZFJHOB3U7aWwgD 1b4Djye2/GxqGkIwdKO7tQg1VzVLJpJO1/0kWZZRxIUcMtjPlPgAPLuYeQNClm683guqlX n1eshf6Sm+IEaGHYOJua3sNvuvlCyeo= Received: by mail-pf1-f182.google.com with SMTP id d2e1a72fcca58-666779dcc8aso1158346b3a.0 for ; Thu, 15 Jun 2023 01:43:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686818595; x=1689410595; 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=FpzykzsbiMOLk6qot3spisUo8VNsB6lkGRakXgvX2Lw=; b=f5u5ND5nwplGrN2UmPJkv0viCKJSKGsY/UI4A0vMG82lz601xyYPuSRYCh50ZPBdKc xZfMnrR2BUQmQZD1dLgTlZgt6DHNqhuw1uWV17tAjGf8aTLgGuQJOB5Rp+ETMqhBhEIe e9xOrmZd7CJebdQh/HkiPyMeMSA1f3mVlQ2WRanzU9FQhLWN2EZhlhLxjOVdUnOVFOk6 nF7tkC5CoW4iBhGnjs59/j96iVnqhzidhQy9ukii/QT/USuxV+nT/U3Z7DEL4MmyKltJ yM0d3URmYutsVKMrFIr75MB8eACGTg3uOEE/J2eqxWFngrikhAAOtOUSirS1ATZyVLqe c3Cg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686818595; x=1689410595; 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=FpzykzsbiMOLk6qot3spisUo8VNsB6lkGRakXgvX2Lw=; b=P1nbXKlFzyPjujseledjSBzsI2kBo0UGpMaBGwahRD8un5NUEYps4PA9B9AWbRVwwZ QOSWmOyK1c/dw0pZz5YV6v0hHj3tkk+F50iuQ+fIbHOycNItG0NmmhYfq1mDarRtVs1m 1HUOOuuCEhAIgpT7/QyrnjnosBS0+frNTjgsALprefCAmo4+pwtsikxBeBQ7PTCX68vA nm0WrQ/jtB0Uq8orLvBTDT4e3OYWLL2aWQKeVQ/oh8MIT7/Tk9Dm48/haPIXPpt2Pk/T fO2kBVq7sEbIPgQpL62ZiuoeIrjbXF9i4rtLyFjbA6GX04DPsSTJl4HCt6vaAbakY9eE xK8w== X-Gm-Message-State: AC+VfDwjWEPKb5XVD3L18U5wKw8TavL55+R+ixhTA8k2nmOCww9nsOJo 3w7aSZ9WD/oLJMf1oRnBkZ4740GUun7lCEzfx/E= X-Google-Smtp-Source: ACHHUZ4VQWfVCwhn8hOlPVP9rhgoXWi3pKF2VBEqo221ku0kE/CNCTN7a+kbBIJsTlD3klPehwhA6w== X-Received: by 2002:a05:6a00:c92:b0:64c:a554:f577 with SMTP id a18-20020a056a000c9200b0064ca554f577mr5393636pfv.11.1686818595126; Thu, 15 Jun 2023 01:43:15 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id i21-20020aa78b55000000b0064fe06fe712sm11139783pfd.129.2023.06.15.01.43.12 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 01:43:14 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v3 2/4] maple_tree: add test for expanding range in RCU mode Date: Thu, 15 Jun 2023 16:42:59 +0800 Message-Id: <20230615084301.97701-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615084301.97701-1-zhangpeng.00@bytedance.com> References: <20230615084301.97701-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Stat-Signature: f811dcu5zui9no87mcar64xm81o3wpsk X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 95C3980006 X-HE-Tag: 1686818596-595913 X-HE-Meta: U2FsdGVkX19n6xwf+FTI+t8QCnbBzomIvUmsxIt2NzG3IdsdgSdMfx1cs42TiZ8iDR4OfithXPL9C4zz0l0bjN/L4Ye1O24wzWdTHmTrScZMlxrP849v06N+2q7r3YrvBPIYjjS1igCtaL1RFanDlOxUy8mtYP1GhfDJujamxJnAm+aonXcfYD8GESo4cv1kBg4qWE9qByt16OBnIe/EtNKDBTdfJha7fuTd8djr5ddWSbXw4+/UlG7J2Zg9hi+JjzL+JmE49QkXGCiTifMhXsPEfE5NcHo6ZGdRWbKadOWLkpN8ZzR17c8KQ2Awi5jTV7IhruExuxDmv2F/xydnQdffuAyLUL6mVmsvYB8A9WkmEXpG+eqEoutx+ObXmC6P0czDGld/7b2PdI+do7Sx5XXSESIkRDk/b4kthRmRifBecjWx7giqWVjIkaMVmAn88573tJQM0kvRgJyppgMMdJTf4WK75c4smaFufzstxI8EyedYn8kCTAJIb7h+7DqzzGbVSmeOSaFvc9JId1TqYYEDGLmR/5RXbHMfXOpCH81DQsJCYVNxgiQmnECDQIo2dXzT2rrf8If8NbfovyaBIAKsCUb5Dr7rWXq6Jnm1dnWBwJlVNqpGGPrE/9vl80fyOmZkJXW0x7UK+nLoWvObRmgs8ia5aUPbCtdzzgbOYoWyG2tnZBDR9c/eE8te1Xm3l4VhmB/kt6qTpZa0x/kqOvxzmWsZtujsTa3KJ6nHl4+wcd4iOr4nxGWAs+h9l2ec4JeaDH/QdkbCix0fPZXf/SPO55TQ3uUaoGpNG9yinx0yRYdsdw2uuH/Y/2pfQWmZIg0UAlyJtGMXd1p3TqMBe1fUjvhqnRScpMbYOrsrgkd/ik8OfuyOVvYyPNwgHgAzZ1oHtAcwqg8gX9OmTUAxCKCoHzzgx39Mo4KD4NqaMdONkeCMf+FJmfGiF1ELWG4NNPYafP1sTSnDXZCFtqn Q2WDOG23 2M1gLNQnvshYrPCcea9c+gj0KVNUJewvKXjqPbZBRt/eupLuLNekWppZUYV8I+fSwwBw+InCQyJRhB2/TeKNXAY+c1dDWHpfoSwP59IQDS4DMgvbE0sXICtpzGhbixIILy+Ozct7crTF+lnqFjfGlNLZ2thO6h6HvJF0OD1sRYCw3+ZFVJCLjOJA/tWzSIFqGbt9HnnbZXQQwLQR9zj5QpyFASiu9U+COazA0im4uwCnG+26oF0NiIYpVzs13ZN3FgDtXlZHhxJUF6HPIXVUlHy2QGkRL2m4QTmPKMcF2A0BgaCfmZGbn6pHgWS+tvMq4A8nvJTa6SYRbolieVEvxcxLHoGf1BCMALUZv0yXiHLVhThprFuTLTsqq3S4Qj4xkU23V/C+Zq306TLs6mgJoh/Q/ytHeZIwg82fSf0rjvSLvZt3ziw4FggpV8bFjZpHUsKGqczzgSNvMAss= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Add test for expanding range in RCU mode. If we use the fast path of the slot store to expand range in RCU mode, this test will fail. Signed-off-by: Peng Zhang --- tools/testing/radix-tree/maple.c | 75 ++++++++++++++++++++++++++++++++ 1 file changed, 75 insertions(+) diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index c42033172276..0887826946f9 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -45,6 +45,13 @@ struct rcu_test_struct2 { unsigned long last[RCU_RANGE_COUNT]; }; +struct rcu_test_struct3 { + struct maple_tree *mt; + unsigned long index; + unsigned long last; + bool stop; +}; + struct rcu_reader_struct { unsigned int id; int mod; @@ -34954,6 +34961,70 @@ void run_check_rcu(struct maple_tree *mt, struct rcu_test_struct *vals) MT_BUG_ON(mt, !vals->seen_entry2); } +static void *rcu_slot_store_reader(void *ptr) +{ + struct rcu_test_struct3 *test = ptr; + MA_STATE(mas, test->mt, test->index, test->index); + + rcu_register_thread(); + + rcu_read_lock(); + while (!test->stop) { + mas_walk(&mas); + /* The length of growth to both sides must be equal. */ + RCU_MT_BUG_ON(test, (test->index - mas.index) != + (mas.last - test->last)); + } + rcu_read_unlock(); + + rcu_unregister_thread(); + return NULL; +} + +static noinline void run_check_rcu_slot_store(struct maple_tree *mt) +{ + pthread_t readers[20]; + int range_cnt = 200, i, limit = 10000; + unsigned long len = ULONG_MAX / range_cnt, start, end; + struct rcu_test_struct3 test = {.stop = false, .mt = mt}; + + start = range_cnt / 2 * len; + end = start + len - 1; + test.index = start; + test.last = end; + + for (i = 0; i < range_cnt; i++) { + mtree_store_range(mt, i * len, i * len + len - 1, + xa_mk_value(i * 100), GFP_KERNEL); + } + + mt_set_in_rcu(mt); + MT_BUG_ON(mt, !mt_in_rcu(mt)); + + for (i = 0; i < ARRAY_SIZE(readers); i++) { + if (pthread_create(&readers[i], NULL, rcu_slot_store_reader, + &test)) { + perror("creating reader thread"); + exit(1); + } + } + + usleep(5); + + while (limit--) { + /* Step by step, expand the most middle range to both sides. */ + mtree_store_range(mt, --start, ++end, xa_mk_value(100), + GFP_KERNEL); + } + + test.stop = true; + + while (i--) + pthread_join(readers[i], NULL); + + mt_validate(mt); +} + static noinline void run_check_rcu_slowread(struct maple_tree *mt, struct rcu_test_struct *vals) { @@ -35206,6 +35277,10 @@ static noinline void __init check_rcu_threaded(struct maple_tree *mt) run_check_rcu(mt, &vals); mtree_destroy(mt); + /* Check expanding range in RCU mode */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + run_check_rcu_slot_store(mt); + mtree_destroy(mt); /* Forward writer for rcu stress */ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); From patchwork Thu Jun 15 08:43:00 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13280890 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 20B3DEB64DC for ; Thu, 15 Jun 2023 08:43:22 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id AC8176B0078; Thu, 15 Jun 2023 04:43:21 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A4FA88E0003; Thu, 15 Jun 2023 04:43:21 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 8CC2E8E0002; Thu, 15 Jun 2023 04:43:21 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 77FCD6B0078 for ; Thu, 15 Jun 2023 04:43:21 -0400 (EDT) Received: from smtpin18.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 248C9160B19 for ; Thu, 15 Jun 2023 08:43:21 +0000 (UTC) X-FDA: 80904343002.18.A2A91B4 Received: from mail-pf1-f176.google.com (mail-pf1-f176.google.com [209.85.210.176]) by imf06.hostedemail.com (Postfix) with ESMTP id 56F05180017 for ; Thu, 15 Jun 2023 08:43:19 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=l3TDRxu1; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf06.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.176 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1686818599; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=XtXCNMCToSbvY4lMnhwDqjdw8KEp/J31bkp75I6UIro=; b=W/CXzWv2glVp8+DYkT+2MwkDt5+ZwcZLHcPD5MvFGkxM1ikxRmvoigBmnNGn8icDPcJj9B jvifiy3x5aLlthRpt2eB5y5IwnVesbf6qfWA+lm4Gahc00OfXMZ5JWjms0fkDWclp2AyA4 o5ovTK2DlZPmbBPugfOK91Ji2o00GoM= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=l3TDRxu1; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf06.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.176 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686818599; a=rsa-sha256; cv=none; b=6iRgHAQwByhrxPDbB+vpXZpspC8boPZg59tVIluETUoDOM90z4CM3NYPuzcMS9MyZBt/RV g1dZAndEj8TM0NO0qqFznYnks0N9SrfeKWnM5cGthS5UBDpWFnYGphDqX/pCDJNAmUhymd oE1JOhzMGBQJBlv+0ZIMXZPBWDPEiZM= Received: by mail-pf1-f176.google.com with SMTP id d2e1a72fcca58-6668c030ec9so538609b3a.1 for ; Thu, 15 Jun 2023 01:43:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686818598; x=1689410598; 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=XtXCNMCToSbvY4lMnhwDqjdw8KEp/J31bkp75I6UIro=; b=l3TDRxu1IZeyZNvWGdJOFqtHd+LYhlWJeVIRmuLAkF0iPL/Q4KJgpGWeh7yt2KT390 KzCL+z04k59mTjKNc1qkFngmiEIN7AEVfPul0AZh9evDVDjlwvB62qsNc0qk1cODg5op c5ZcfjgPq4iTWVmfJGSM2rtBKFqryJoMm4+M8PPPckeA9qg2gVriJbfcAwUAQBPIeVXu YMm0+kwc4VoVWFYaesVj4e8F5hPwX8K5ZwSWddqC5b8kzgp76myGhJZxg9jm+Ptz3mtX cai+VRJ32w9/dUu3CoeZE60WbitOBrdrPjWnPzWbuqC7KE5tPbmfNbKrOtB+3Y5qgmcQ QROg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686818598; x=1689410598; 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=XtXCNMCToSbvY4lMnhwDqjdw8KEp/J31bkp75I6UIro=; b=GDh9c5LLzUMuXKTbxbeU19/1u4P8ty8fckKO4Vg3oFXPO/opFZQqrJrALLPkcBc8Am F2Q8OetcQ6GyTajYgxBu7Ak5zSuyu/5u5wH9S6g6nmpyXQWWrGQwdO43+LHYh4OUAJ7f uMWYliTg06Rvz9qtvtM967jSsj+47eDdTf2rP8SzXLXRLpACzNzIps+nBcWa0aJue8QR s44eOX9zkd2RmT4Z+HklblHwrIQvR8WgQeD+NiF9kWF9LTtJTUnFX5S+oMqwCVmxXRZE YGBdDQ6tmv5NDesVmz7XBCgyaTAG23ZK44SN846WEmulVztNhFBbCASFRqJ6PQK2nsB7 ybeg== X-Gm-Message-State: AC+VfDxlZp+bYUBZPGI9nYYoL9oOa9vJUrVbXGCoclzLTPVz56Kv34jI UFv/4deouYfypIT8Ay5q8uGMdw== X-Google-Smtp-Source: ACHHUZ5q9AP+JpvTGeNeOKfaSVbGfzkXtHUw8eqE+etHTDoY4NTa38tMPtfWroY21eD2WL8zxFFROQ== X-Received: by 2002:a05:6a00:391e:b0:643:aa8d:8cd7 with SMTP id fh30-20020a056a00391e00b00643aa8d8cd7mr4292787pfb.32.1686818598107; Thu, 15 Jun 2023 01:43:18 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id i21-20020aa78b55000000b0064fe06fe712sm11139783pfd.129.2023.06.15.01.43.15 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 01:43:17 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v3 3/4] maple_tree: optimize mas_wr_append(), also improve duplicating VMAs Date: Thu, 15 Jun 2023 16:43:00 +0800 Message-Id: <20230615084301.97701-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615084301.97701-1-zhangpeng.00@bytedance.com> References: <20230615084301.97701-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 56F05180017 X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: 4c8mauqs5pmra1mt7js6ag4rd968fkd4 X-HE-Tag: 1686818599-555675 X-HE-Meta: U2FsdGVkX1/nNNsaQVK87qQNfpuoqv3m/bcnmSvtfBxgR59ZmNdKGZfA7dtc9MRjE9kduUVuj/Y9qn0Tboqf2+Am01chY11gOkG6pgq4MGsabkbB1iGoU6vWHOCdt2ZD95QcAfqefY3GrTBUSDErgYO69qRRvBLVEcbRWt/9vGDuxHr/7yKSopVZr959x3eQpxGnUxqfLvpV1pQ/SO0P+8gZNR1XHfDkRfFrCIIEIlTKrW5Wn10arjqm8bFvAeH9bE/4lF3nEWmnBJ8cL/zHJ3GZeGI6ifIyCWVEUsLZSr3TC/CngpxbW3hkqpKC7qYww6WJ5HUlxEFm9SzuMxwFxKG3oOHyzbMU4ASs0CCqtbt+LkJoCHHTMfTaQjxMWbroFOWalWiig2q8CaAQjsI6jComMxegZTACH4qbcH936CzJSANn8WZ85d9kF12Nhav0Pm8246WlttA+jnCiHUrKpp7Q9WmqPncCdJiQncwvLzWPHbYPgLbakUe74A02gwG42uoa5gepJv+BWb2WRNyOdeSbA+aipnEUi60VlnMlFBbsKR4fzLBQTKq2rZFhiybqLaPz2PhmrsTuUbLRWqmVxPICdvLfid9P1ESJsP7x6LVJhmXvA7K0BY/aGmuWkUMMO5jpP3uOE00nzX0ITyi5qS1Rke2Fq+VwpOB/lTnBzCh5Zflc3FG3AfOUQ8YPt6PZzFrkFs3tllCYruD3hHfncyQxXfaRvCeMj4eq8hK5EPWO0rONOxOj+peyRw5wgMBWsFbOebcQMnw4hm7vUXgkij07R5XMtaRII0XsAFC5od0zocQMMweAlLlqHxu13DDAyJrB/EbBcCnwSo9JaavVBHwVrhOqs/RZVdmkjmNg95uiBe5RLPAUJmwyLvZGVVbx+Y35sWhlZHdpBPac6Q1Pd1FzE7myt9UrbtW63gqf0empHMAhcn46p4zUPP7ZrYgQ/EoqR5fZsw+cPe/uvgF 8IXT+IiI yx28pYUyCF697vZTJKOEyTd0BmTLj5GVfAs81mb74FJxCzIpEw/JzdIbdNneQgYS72tBD5bnlAo2dCrpdM4mc/CmqrEu7ZpktkdFmUkjCj0KEa5V8bhAMv8eazPaMbMuFHP5KC8OrGCTdM8K9kueB++e4IiSebmDc76aMXM7QaQjc8cbr18sjgLZKFL0HkSI0d6s5zq3/a27Zbu+0/EZmT+6DkTQ/VWlWSWB0JJ027CZQsmqj4K3a8MJJle+wSO8q6ytnKB6Z5vXSqipt/EO2U03ZbsVxWSP43LG7ZEjTkc2tXNlO9GvAWS8ZS3AJYr6UTFD01xhmBVrvm+KLC/TRxrU5gHc3oI0FcMY9jhkOqZIdCka73CDbodC09gIdldNn3ZteLzbiXByYVB5KrGEDMp1zJw9be1lERx29NCCJukxsubfsJ66qzudgDKYtQ0D7RIb6/+QhY2WvgqnD+yKRA/+SLhd8PZaUpvAN X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: When the new range can be completely covered by the original last range without touching the boundaries on both sides, two new entries can be appended to the end as a fast path. We update the original last pivot at the end, and the newly appended two entries will not be accessed before this, so it is also safe in RCU mode. This is useful for sequential insertion, which is what we do in dup_mmap(). Enabling BENCH_FORK in test_maple_tree and just running bench_forking() gives the following time-consuming numbers: before: after: 17,874.83 msec 15,738.38 msec It shows about a 12% performance improvement for duplicating VMAs. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 33 ++++++++++++++++++++++----------- 1 file changed, 22 insertions(+), 11 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index d2799c69a669..da4af6743b30 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4202,10 +4202,10 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) * * Return: True if appended, false otherwise */ -static inline bool mas_wr_append(struct ma_wr_state *wr_mas) +static inline bool mas_wr_append(struct ma_wr_state *wr_mas, + unsigned char new_end) { unsigned char end = wr_mas->node_end; - unsigned char new_end = end + 1; struct ma_state *mas = wr_mas->mas; unsigned char node_pivots = mt_pivots[wr_mas->type]; @@ -4217,16 +4217,27 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas) ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end); } - if (mas->last == wr_mas->r_max) { - /* Append to end of range */ - rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry); - wr_mas->pivots[end] = mas->index - 1; - mas->offset = new_end; + if (new_end == wr_mas->node_end + 1) { + if (mas->last == wr_mas->r_max) { + /* Append to end of range */ + rcu_assign_pointer(wr_mas->slots[new_end], + wr_mas->entry); + wr_mas->pivots[end] = mas->index - 1; + mas->offset = new_end; + } else { + /* Append to start of range */ + rcu_assign_pointer(wr_mas->slots[new_end], + wr_mas->content); + wr_mas->pivots[end] = mas->last; + rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry); + } } else { - /* Append to start of range */ + /* Append to the range without touching any boundaries. */ rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->content); - wr_mas->pivots[end] = mas->last; - rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry); + wr_mas->pivots[end + 1] = mas->last; + rcu_assign_pointer(wr_mas->slots[end + 1], wr_mas->entry); + wr_mas->pivots[end] = mas->index - 1; + mas->offset = end + 1; } if (!wr_mas->content || !wr_mas->entry) @@ -4273,7 +4284,7 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas) goto slow_path; /* Attempt to append */ - if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas)) + if (mas_wr_append(wr_mas, new_end)) return; if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas)) From patchwork Thu Jun 15 08:43:01 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13280891 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id DCB0CEB64DD for ; Thu, 15 Jun 2023 08:43:24 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 7E36D8E0002; Thu, 15 Jun 2023 04:43:24 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 7699B6B007E; Thu, 15 Jun 2023 04:43:24 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 5E42A8E0002; Thu, 15 Jun 2023 04:43:24 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 4C44D6B007B for ; Thu, 15 Jun 2023 04:43:24 -0400 (EDT) Received: from smtpin23.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 21E96160B0E for ; Thu, 15 Jun 2023 08:43:24 +0000 (UTC) X-FDA: 80904343128.23.1606AD3 Received: from mail-qt1-f170.google.com (mail-qt1-f170.google.com [209.85.160.170]) by imf29.hostedemail.com (Postfix) with ESMTP id 3E6CF120010 for ; Thu, 15 Jun 2023 08:43:22 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=L9gTbOit; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.160.170 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1686818602; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=5k+8W6YpzHgSdUoJtesRB/pITjbosIv5ydX8Qu9f+Qw=; b=x9hmYRUB0aCplB7a+yukKFhjrJqm2AuxKcBiLaX9TqyFDtcZ+kXSXS6H2JZ41iPWlXjn3M mHBgAmnA2UI+RPtjPXdBJdQKFa0ohiLwlBbVwL7mcqHDjekczQ/N56yVGL5//2nvA7xpAa zzFxKJpdfFL1XJzBY5bknGMCCNJIC08= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686818602; a=rsa-sha256; cv=none; b=1XEz1X57VP5lJMUWID7WhHAUFcvaXHHdobpC8Cf5y0OsNLvd9GpSjvw1FRtUykif4gpA5c r7EJ6tbK+7dpdDKv6AmZ3lUIJBIon2ejdS7L5AHH2yCHs6gEb4ZuhbCk+6rnjWJy6VlsvL Hmn0xOdlzbAsw+995BNaYD6fwY14SkY= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=L9gTbOit; spf=pass (imf29.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.160.170 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-qt1-f170.google.com with SMTP id d75a77b69052e-3f9df7eb837so26840991cf.2 for ; Thu, 15 Jun 2023 01:43:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686818601; x=1689410601; 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=5k+8W6YpzHgSdUoJtesRB/pITjbosIv5ydX8Qu9f+Qw=; b=L9gTbOitjaiPVT1mPvKyA+1gkxVyHMUzILsZcki0A+ChBTywUw6NohiYLb1g1Ardc1 kMAEK5cFZZyUlbGGsMPuTdcRTmS+qB9DFC4KgbL+jedtkpUufHaDhGxSORQtenv5dxno 53zz55fJrTGOcwFkp3egUxDvqcto70rlu4gNyigvXcG/YlYSDa5Yehb8/c3sY9VPVH+W OTskE0Q7hvjBIGv50tIr95U8WiwV8dHyfjmjSvCSn45KdtpRTCdehu9SH6SLo2PF+1ik scfWicjFjDVMCw1azV116jpQLpvcldBAYY2FooqN0XwEDKBgjANfcgs0fzIgdXbiEPZC MxJw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686818601; x=1689410601; 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=5k+8W6YpzHgSdUoJtesRB/pITjbosIv5ydX8Qu9f+Qw=; b=MFxtvQV7noWMJcLIykmdELYzQfzfMucJhIC9Nu4RbUiymYHlvYNszFkEiCkmGEBzVB DsnvsGyTBlbcS5loI3q8e5rS5bQFEjaMiIBF2GdnZE3I62yJO9zbwGjy277rbr1tzYy6 ngJBnWRiZ3QR7P4UhXSMdkuecZP1+j6PpsbA3m8Bht4Z5DUU3T/oD0uSNl7F/XKQGcHb 14ZafnP+hl4CUEtMGyM5LE233DPwy4HlMOrAo9dwFZRWM1xK7pr8V9qPcEgRdxhAEtRj DLRLmRSPAaoV9b+0UDHaiXzwuQLVFoVHuYnNWXwQPxa5Qg6b1/vtTjgWBTE/4AW10c7F D5wg== X-Gm-Message-State: AC+VfDx61nGyflymPBMd0u3lHA0+G+B+WAbjzdGIryWf0JN8ZND4bNmM S5U+o2hzXfJqDBieF8+QV5VQNQ== X-Google-Smtp-Source: ACHHUZ56d5EfqOSVGPZP9YSkx1pVZ80Ypp/B7oY4uWraBWTQMEVsdq6dzt7z8dyRJ7J/IUMgpqTn6Q== X-Received: by 2002:a05:622a:1a9d:b0:3f8:64ea:9f5c with SMTP id s29-20020a05622a1a9d00b003f864ea9f5cmr5909163qtc.35.1686818601115; Thu, 15 Jun 2023 01:43:21 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id i21-20020aa78b55000000b0064fe06fe712sm11139783pfd.129.2023.06.15.01.43.18 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 15 Jun 2023 01:43:20 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v3 4/4] maple_tree: add a fast path case in mas_wr_slot_store() Date: Thu, 15 Jun 2023 16:43:01 +0800 Message-Id: <20230615084301.97701-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230615084301.97701-1-zhangpeng.00@bytedance.com> References: <20230615084301.97701-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Stat-Signature: o6k5r7izfnronyn7368zjpthfx15w6ni X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: 3E6CF120010 X-Rspam-User: X-HE-Tag: 1686818602-438957 X-HE-Meta: U2FsdGVkX1/VvKDAjSFWf/8p79sBRqF4xeinyStw8d9f27KN4XRedJJByfVEbAzB3K6TouD+LxlcWz3zzz4V7Ch0fGqpWTKNg6XYALAGlwMg44xVnuSUvvram/WECIBsKlzfUcVo2dFpDhaYBTsha+ASCoDRoTDytl+8IqzW4d45CBa75sOl7ZTYlKm1snLx9V3fcROkZpzgI8Q0YC33E9BCP0GU6l7SBrnicelxndI2YGmvNLBMxiqvMRW8u/dnBUPJ6OpY1xJ/uV99jVYtU6V7ddh3RdDLrmlyq8LjsGmoOgkAUoqc0sq0yFJlJ6g/kkU1X3K4diF/3Vy4pSijtb6nAVSAM8hxk6TAVjwyf+hkr/vxdQAyygGn7XuG2d+mvEsyuI2Euiu2F/NoFxp0ZGeTOV+MRal5M211d2mkP3htJEjKJll+1GmrRDseaYAvBzMmt7aARUWRVeGItpQJ/9Sxk+OVP3BPk86GysRlO0Xabmo/zuSG6gKpc+bVSiq80AZvt7I7cY2H1pC9dbhQWsn0lPG+xqJH2wY2aB1OVMc8GQEm12jHtogI8A9ILbS/vM5JxCWXwxk0nlG91qVzETPaSy/gr7cRNr0+DX/1vMUUpSIktaa3KuDQGCAMloQcKRBfd2tzGnUO27JCbZJ64qw8RuPX5pixMRUlGfXlw5zvDEeRg2CrRM807PkVUwCpYKV95ph/hL0YFPf6yFrwoeWMQKm+n8uygJC/fdshfzJOdUULkjbJIpAygcj6DKflRa8BOhPQnhUNfkxpMc3Q+FJv2mYAn2gthIcvC1GDX7RMktIraeL/RH1XQSEfjwZSt2LxFXW+mcxgxagA3XGw9L5oq9ZDCejlkD52dZBkTSQPtkK+DvCr01STMLFUW6iSyzs1Eds1ySqlmZSs4qCwCnaiBXp0PpU7d3yoiref0cCR9XjnxTKt8L+Y7EnQ/reirttYNhmQmcgWdBpT/pD Jq2A00si p9eaw8yar7oEZTWfDEz3MgaRTOVMInhyOKJH8SnpWYYrldFSPU/FfWdE6jRjpVxkXs4CJr6TQz7rHx5PgfPZ7Q/+SgsSF7HwYN8mJmIg4HeGS2c0XjdukR9zE8q7x1wpy22j79BmdBWAU/pAEkt4NqwsTLfEaKV1m6kiGQRl0/yahXL3rcZ4fcuqBumhdXvx8CmLwxsmClrj4PDZZwb/+0GHoD4dNKfEjTpxnuSNyF+CMEHqw0WKUgGGw4apf8uFN3rZGFO5fi5mG8AJEpUW9Z8O0Ivq2Jqm2Kk/qOkexV/QxaTiwskaHxoYRub+d6J7PBe2El3TypvGKhy+HeAyZo0F8p5YTCAjs/Px2OBHphtJKNPXosgBOF7fv0rwHhnNT1NjWtJif/EfQjHg121OgzIcb6GZSyjQM6f2xdu0GWpqCZPhLwAkkmAmCAdCVhCdFCabEJRtJmkf/lYM= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: When expanding a range in two directions, only partially overwriting the previous and next ranges, the number of entries will not be increased, so we can just update the pivots as a fast path. However, it may introduce potential risks in RCU mode (although it may pass the test), because it updates two pivots. We only enable it in non-RCU mode for now. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 36 ++++++++++++++++++++++++------------ 1 file changed, 24 insertions(+), 12 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index da4af6743b30..bff6531fd0bc 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4100,23 +4100,35 @@ static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas) { struct ma_state *mas = wr_mas->mas; unsigned char offset = mas->offset; + void __rcu **slots = wr_mas->slots; bool gap = false; - if (wr_mas->offset_end - offset != 1) - return false; - - gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset); - gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1); + gap |= !mt_slot_locked(mas->tree, slots, offset); + gap |= !mt_slot_locked(mas->tree, slots, offset + 1); - if (mas->index == wr_mas->r_min) { - /* Overwriting the range and over a part of the next range. */ - rcu_assign_pointer(wr_mas->slots[offset], wr_mas->entry); - wr_mas->pivots[offset] = mas->last; - } else { - /* Overwriting a part of the range and over the next range */ - rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry); + if (wr_mas->offset_end - offset == 1) { + if (mas->index == wr_mas->r_min) { + /* Overwriting the range and a part of the next one */ + rcu_assign_pointer(slots[offset], wr_mas->entry); + wr_mas->pivots[offset] = mas->last; + } else { + /* Overwriting a part of the range and the next one */ + rcu_assign_pointer(slots[offset + 1], wr_mas->entry); + wr_mas->pivots[offset] = mas->index - 1; + mas->offset++; /* Keep mas accurate. */ + } + } else if (!mt_in_rcu(mas->tree)) { + /* + * Expand the range, only partially overwriting the previous and + * next ranges + */ + gap |= !mt_slot_locked(mas->tree, slots, offset + 2); + rcu_assign_pointer(slots[offset + 1], wr_mas->entry); wr_mas->pivots[offset] = mas->index - 1; + wr_mas->pivots[offset + 1] = mas->last; mas->offset++; /* Keep mas accurate. */ + } else { + return false; } trace_ma_write(__func__, mas, 0, wr_mas->entry);