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: 108353 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp489385vqr; Thu, 15 Jun 2023 02:02:10 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ4VXF8qkpMe5VmWeyEZMVuGdLA92jKP9cFbEg8/2YOakEBDs8XfcpWWA8lBWAKQjnYFGZHD X-Received: by 2002:a05:6a00:a08:b0:654:3dac:f107 with SMTP id p8-20020a056a000a0800b006543dacf107mr4974599pfh.4.1686819729791; Thu, 15 Jun 2023 02:02:09 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686819729; cv=none; d=google.com; s=arc-20160816; b=kBPRPjb6PYZyAAHv9I0UQxu9gO/3fY4I3YtzCZWM9CBKO6lhWfE1H3l1mXxfaTJMXy Z/TE0F/XOsq/8gNugH05O/2bMPRRlwcZkAmvBaRHlfxpkpW4vXt/j33dLEqP/+ZBxQkX U/x6IiPMAB10v++p54C4Zw4+rP1tLSD1EcjYLnf0kHr6NOmaiuwlA8tLAY7lKmkRC5b8 8G96jL9D50j3LbBkXKbwYIEVAydqHMjiMw/Q9N7jGlsTKbXuwFUZpY7kabO+eYrmEHHx ckHdNBd423pKKk3gdCOknCMVjzxjWKhPdhiv5vshYlOp18jBe8fkT5oVUYmS9hVvfO5e oJPA== 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=h6we1XLVpJvFDKToAtCSdGG7AESFIveH8POVJHK7ygw=; b=yQiNhmcQNBv4MVUK0oTGkixxblFfxxwKow83isNSb5mC2j13UF/qL56wgbUwUD6FBT 33B2xZdT1gtyN0jDF53DaxKcsv+whWGJS3P++2BmJMOolSlXsh1v6MIW6bXTK3FOtD5Q c8JxIBlY/ow8p3a0s/e7vAAKnVYtWNwn+pl1vAaUz7BIceJ6s/cW8hQGFlmZNji1sdup 2CoAWR6g9sxYz/Tmdg2ruo3J/yC5qmTTYh9zpOXP7XiHpoN8ndEHGw0dcN4rukndkUyJ iAe11b0j44SNGAhkzZBKX/6Wi6tazfM2Tx7R9J2S9Gr8W/gUGe5Dp+w7entFyUJkE8jG Q3hQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=KJqooEgR; 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 az9-20020a056a02004900b0054f962b6558si6777603pgb.134.2023.06.15.02.01.55; Thu, 15 Jun 2023 02:02:09 -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=KJqooEgR; 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 S245222AbjFOIoH (ORCPT + 99 others); Thu, 15 Jun 2023 04:44:07 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33768 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S241037AbjFOIne (ORCPT ); Thu, 15 Jun 2023 04:43:34 -0400 Received: from mail-pf1-x42b.google.com (mail-pf1-x42b.google.com [IPv6:2607:f8b0:4864:20::42b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AB802272E for ; Thu, 15 Jun 2023 01:43:12 -0700 (PDT) Received: by mail-pf1-x42b.google.com with SMTP id d2e1a72fcca58-6664a9f0b10so1173531b3a.0 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=bc5ABhnFyhlOcqd13CCHb187oq2NuOVzxsK7fMg3GeveopdSKeYgcnPA8fNFPc6mJd uxm13k2ISkNx5y4IT9pq7LQqOF0yCde3VBHJDgfVwk/eHyJlrU5cKnGh7h1wMby/rkQE gQ/9oqa2Frq9yCTOu7OsLZ7SxNvQOB/6tn+MkzLZIytjq++SornS1f9gMauP/rPAGHEl bSIjFJRQUETiB42/Gb9gN55CdzPqLcrXOq4ESD05UmnXkiUd9ZvbbGjqeKkmKOgLye7t EITQzZ/LXc4uDm4BnRFgrG0RhkUtB9JBQTwVKloFe/o1YYxA40iwtLf+xfueLRxGc8m/ 1Nig== X-Gm-Message-State: AC+VfDyRhkEGQ1qLNc8NeB62NQphULL1i1oc6XrWKX2EHMIZOWsuAsOA 1fAwyjzLo3y3DlCqB77I+rgizA== 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-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_NONE,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768758684724817320?= X-GMAIL-MSGID: =?utf-8?q?1768758684724817320?= 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: 108352 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp487759vqr; Thu, 15 Jun 2023 01:59:35 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ5Ifcg3dMas7/Wmyx3/svuuk5Ey2Svd+oghLqsQoBw0Rp1dQxTNLj2NjGjfDIWZV+PHZQ5M X-Received: by 2002:a17:907:2683:b0:974:62bb:91cf with SMTP id bn3-20020a170907268300b0097462bb91cfmr20803999ejc.30.1686819574912; Thu, 15 Jun 2023 01:59:34 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686819574; cv=none; d=google.com; s=arc-20160816; b=P55dDC7x7mneV/AtrIowg6XgGZJvpT+PfWZDyDwyucm7hIiNZJr1g7kDPbDtnHYDVo NrxneTpYlz1HypWnMt3nx52QKJgapKV+N5KgDxHgX9xSwfVNCKWrrne9sBkjc38rXa2U Pfh3pLayZ2CLaO0yK9PaXV6F3tSigEoTL72E91TjxX5vlhfJl2OHQvXnHUMVzB9V5+ev ikMQkfi1nCRf3eoPXIucLhsTI03zeq8UoQ4v7+8bjPxh2wLAfBXAVv87mSXns8NXEL4z s2DTn7GglIzzZ55CyhBki+rGhMfM68dUfi9DX1PflQggRbqmZ6EJicsv4YrEw4Z1XT4h tg8Q== 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=FpzykzsbiMOLk6qot3spisUo8VNsB6lkGRakXgvX2Lw=; b=gFSUxQ0/TBPKQWaBYzWaK2ecYFaNSY2wxV6W89UjdmPxJfexE2U3H2NG561DzP4dUe 3+OINBfOV/vb4bC+XHYbXwBT+ZBJo0nrJZ0noiUhZzt2wYk/t7B1qbMUbcEiD5Dw03jj wDJ28C1rjh+m8+ZkXmWmcDbBYI0jiL/n2Sf5XwotRjPdrwETdYBkhHcJkTUZgVaydaf9 nJcBajJt4xFNLcic8evxlz+/3nDWClT23z7OQa4GLQ6SE00Pj9yXc933D3jopJ3v3EPw JWybdDzIDd4JUmPBfkDvNmfr5o8KisGOD05GpNsf/UJgY+FjKyB5pE3R1URvQIKdwKoX 0mzQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=f5u5ND5n; 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 e26-20020a17090681da00b00973e638a646si9568676ejx.439.2023.06.15.01.59.09; Thu, 15 Jun 2023 01:59:34 -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=f5u5ND5n; 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 S245100AbjFOInk (ORCPT + 99 others); Thu, 15 Jun 2023 04:43:40 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33852 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S244453AbjFOInR (ORCPT ); Thu, 15 Jun 2023 04:43:17 -0400 Received: from mail-pf1-x436.google.com (mail-pf1-x436.google.com [IPv6:2607:f8b0:4864:20::436]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 34C3B296C for ; Thu, 15 Jun 2023 01:43:15 -0700 (PDT) Received: by mail-pf1-x436.google.com with SMTP id d2e1a72fcca58-666729f9093so1220153b3a.1 for ; Thu, 15 Jun 2023 01:43:15 -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=Psbl5xZuIsqvurgUGKwWESAEIL6DKvSOseObOi1I8HGvxl9mkcw65ra4iUCaZiUULK kNKwz0dLqZT77RL14R1+YfMRrLB/ENYKGKx4+ZSM2dUUNa3VPD57DvfP3+bMrQN/VGw9 JDqPQf0j27XX3QF6448QTScTzq5wlgA3CkMjAGs7h9T3V2g4HeWBKEnwQNNR0Swu9jiv adRT4wTm5+ee/cF6FL+KET7obFvNEw99HVCh9DEJ8uFtomqDM4G2okjbqxgZ3C5hZzHb kgcKygFxVNBRyX+HwCshrFNIGiAsP7K+qCVh6+1TokzaB1/OV4CD5VSAye8LMG0BI1wi ynww== X-Gm-Message-State: AC+VfDxHQ/XnXsP2sEs+SSw4eYQ1XZ4JaqAElwri6+ROR/ZL8ER5F/BP q3XwTW4CumQf/OsyM0eo/wGnJA== 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-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_NONE,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768758522624018417?= X-GMAIL-MSGID: =?utf-8?q?1768758522624018417?= 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: 108351 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp487025vqr; Thu, 15 Jun 2023 01:57:22 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6WAHzOvHA9hidtOwISmqf+OKyGgzVjYa5ID/wq3VqJzETP+IB5ISdqmpTBLboPxCy+yNXy X-Received: by 2002:a17:907:8a08:b0:982:870f:9e8f with SMTP id sc8-20020a1709078a0800b00982870f9e8fmr2582934ejc.62.1686819442169; Thu, 15 Jun 2023 01:57:22 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686819442; cv=none; d=google.com; s=arc-20160816; b=AxYt33fWtJubkza0wV4Zod6W1SqvtjyeRwrTqG9Yg7n0JfxZpoVLz2dXv1zJmzRhCI WSR8lHv6UJjpYnqrixi1hLoigjjwJrmttIC1wTFY4Da4ljImpGOa5w4PKvJdVcMiSi9i K4lIjbYkGLgzbZmmGThDZ+Om5PCpqbZb0GJmMa/Eq6zsx0AzNZm5IELNiBT7wASaJnlk 78Jq4P1kGV9RifBYNmVv014MUMk8WXnCsQF33Mh/2VKSikPX9u0bKl6TyNzyuDbq9FZh 16wzbcWwU+yTWlASfwwb1x04UmOPUp6je/8ABJi88hU1KFAGmWhkl5Mt9GU+xFkgg+IO a/sg== 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=XtXCNMCToSbvY4lMnhwDqjdw8KEp/J31bkp75I6UIro=; b=s0wET0SjgpTRVWuDs+EVOFo3mPa662dghu2kk+MrtNySQuqbi/e/XvpzzmV3W1lUz3 lzC+VVUHbHXpwKsk47a5qzkgJEjCBq4ZjY/ikXHHVrEpn3OfErYEJEGR26Y+Cd1lck1z QFWyZjKOkUAzE3psOgayWN94IxnJtM0GHY3d6qTU/JqA11IDe0kltJ0YjQ5rU78u18qa V+HG4MhT1uOg0f+5oX7Nqy/+mic5YAXGkLEEFAJOrCKjxxH9cPE+QeLjtCbK+HNcYiHc yry2TF+cMc7vaShqxDZejkNqX8Iu+zfPtUDaWKCoQDXC+M/fjw5wViWccGc9lSoZphUK 2r+A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=l3TDRxu1; 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 e26-20020a17090681da00b00973e638a646si9568676ejx.439.2023.06.15.01.56.58; Thu, 15 Jun 2023 01:57:22 -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=l3TDRxu1; 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 S245241AbjFOIoK (ORCPT + 99 others); Thu, 15 Jun 2023 04:44:10 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33012 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S244696AbjFOInj (ORCPT ); Thu, 15 Jun 2023 04:43:39 -0400 Received: from mail-pf1-x431.google.com (mail-pf1-x431.google.com [IPv6:2607:f8b0:4864:20::431]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id ABEFF297B for ; Thu, 15 Jun 2023 01:43:18 -0700 (PDT) Received: by mail-pf1-x431.google.com with SMTP id d2e1a72fcca58-666aa1b79a3so80635b3a.3 for ; Thu, 15 Jun 2023 01:43:18 -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=fjidC0WvjVjlwAJUzUig0kyFOPEz2pucLtGXW0uQoBs9OqZd4Js+1ksMMo+TRAZqAE NU3VLpZ/931V0eOpQSAzimHr6eJX+I2aicsD9MTEFCBBt+24wD2jq6RrLfsXK0gjtgxX AGvZIHeJQBs3sA+GJdWbid0/CPDYSnHM9gwfipMUWQKlgZthNaEyw5z2eg4n6VGOAgtJ n9IDZjR8yWJjnO/pKjySyOysnOXqzS1TwKf5PTBygcanYBbn4E1jfmhHE+sxPCJ+A+M2 iUzZ3fBSXGIqSNU5lJ6evQbTmgaG+1A1Zgej6tCU/1PLg12hqh4Q2J4gE0ldxXd2KaHd 6ymA== X-Gm-Message-State: AC+VfDyKE0QvaHTisEraSex+sKO60Kw+1HRr8fWITbzmBiHpBtwUDwvA BMtPCvtc4lPWn5EipVOy6pn9EA== 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-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_NONE,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768758383070699933?= X-GMAIL-MSGID: =?utf-8?q?1768758383070699933?= 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: 108354 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp491477vqr; Thu, 15 Jun 2023 02:05:59 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ62rJ5iqEcpNEpud5KtkMLid2CDShl+Ompnd6nm7JzrkIWk8dHHoOPoISWiGlMAbqiVIq7W X-Received: by 2002:a17:907:7249:b0:97d:f8da:1717 with SMTP id ds9-20020a170907724900b0097df8da1717mr15426649ejc.7.1686819958817; Thu, 15 Jun 2023 02:05:58 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686819958; cv=none; d=google.com; s=arc-20160816; b=C2uG8dhe8kYIIpuwbK2yNoI3K0fv7ifQQ6o8Vu/jjw4FB06WGA/nM//E3SDB/SSaet 7yweErWVirpb3LHGiysNPELkNofVtJAhFMHH3LlNH9b/2w1eI2Wz475gEqZhfjiFsAvX CCe44neUQeYTDfNfpAhlp8igMiM30wOG1qtKzPAb+QCXKb0/f2jhOyy3u1DLGosnqXgq 1nFUbMfiyfuSyUgiL3BXpxsmx/yO7X+3yH8pWNMjGILc6aPO+VXk2ssCY4aURtjrVNiY C5Tyg0XYaPRb9vhChWPFRMcRzHpbcxRMlg/wHcsW4HH609R4QqeWIqHpLfiVtmuezJEl xguA== 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=5k+8W6YpzHgSdUoJtesRB/pITjbosIv5ydX8Qu9f+Qw=; b=DnqnmKsH2WDQE0FMt0evp5fKJ50QxyCC4s5+ai3n/EjfYqpLB60tyWUmTOSHSlHylU EfQOdqn6TzoIzp55tTzNB674dWrDoT9TQWNsvOBs1riMvaprLSNNa696cawQ4nNAAd6h zhVg2Hs6z4x8I/lkWbEzqK1TunrZkfZaW/796YIEZiR3vNR+pxG/FfA/xMaxvHNGqezK SJGX65Z1bYQT3pBruoiE0wsatgyuGiDVz/ZwGbJvzYFDJsEB4BGFVQzPEgUTbhDS+1vx LhJRoo1XGFJjdO4amKGTu6Q0QzqkWR0lAcXZgSbMHUk05vUNzjO37JGLnoBeudQJGa+S lEZQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=L9gTbOit; 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 y14-20020a17090614ce00b0095317ae767esi9125462ejc.46.2023.06.15.02.05.33; Thu, 15 Jun 2023 02:05:58 -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=L9gTbOit; 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 S240848AbjFOIo2 (ORCPT + 99 others); Thu, 15 Jun 2023 04:44:28 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:32842 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238198AbjFOInq (ORCPT ); Thu, 15 Jun 2023 04:43:46 -0400 Received: from mail-qt1-x82f.google.com (mail-qt1-x82f.google.com [IPv6:2607:f8b0:4864:20::82f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 066DC294E for ; Thu, 15 Jun 2023 01:43:22 -0700 (PDT) Received: by mail-qt1-x82f.google.com with SMTP id d75a77b69052e-3f9cf20da1dso26909091cf.3 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=O+YOEd8r0emKqihGDHOVCAqPYxtVN0CTL8AvfpJDg4ZBAy89OJt9xQxk0u2SO1uQHy P0cdAoeyePlObMJoykylnMKUCgd3eVu6O45ZcOu6MtfS61gbLRvwmmLmvf1M4S7QBzen CPJkercWkhLBJ48YlQCl/okNfFnzEtgSR8JBRjczYI8TCKxPcJhRFpoY8Pq63MIMBD6L iNgfDuDlAF7Kh46gdpniUSHLeS4PpgmLfF7goSAck4SmFlOYt2HxN8UdV6qtcy5PrIPC Ek2jVHFwVeqnpvHLK0q3WxMrXqnUJ4yzns0SokZl2Y176LrWn7bihskPyAWB1C99XfRV yv8Q== X-Gm-Message-State: AC+VfDzdsL5Urwf8CabMd0pj1y5CHBSJGrGzUC0uCMYWKH0oB1SjNOcl 6WdZARNn99daq7+VqQNeDsEDeA== 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-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_NONE,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768758925351836544?= X-GMAIL-MSGID: =?utf-8?q?1768758925351836544?= 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);