From patchwork Fri Jun 9 12:03:45 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 105586 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp902388vqr; Fri, 9 Jun 2023 05:17:27 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6VsDYXX0oBI8YlExW6jaQYy0hy31bAXJqx42uaPKcHYokq19MGV3irsF1/pFlPz7VQPISw X-Received: by 2002:a17:90a:d786:b0:258:71e6:1c24 with SMTP id z6-20020a17090ad78600b0025871e61c24mr864069pju.12.1686313047163; Fri, 09 Jun 2023 05:17:27 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686313047; cv=none; d=google.com; s=arc-20160816; b=SRgcbbdjfRLQO7NNWwUKtE5zZwzlHWbPyQrqYdpwBh21dsPz6ZJqcadqB7uvE+P0Pd oSj9EZkSJ7o6oooaGJEt7GEYtKhYcVFUhXGEFCv4RzXfDOGXun396GcGgPcgoCztQtny tMvS+stp1wz8WrT+qOS8LWZLwwWc6iJhS9/+cxvng/l6lbk7kr5G+q+9RoF6cdx+YGDT lVEvNHcsW249th+YMvMcN1SRmCDpRgsf+4iRccMEwEz95XjqCTAAwWzl91X8hhKDgAZf qtExacjjX9xn1BcRjsOWUsauYgptKxVPi/GgSH8APS7O8n6x4h4h29TNUfCKWjveqzrV hRJw== 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=Owqt/RtERZW6/SmElzGKo3+oyss5zFU0+cH0zNQUbkeWEd1XO9At9Qb+PZo/lHhQvk ZU01huKKSSAp9NCBJ8OfSGP2oZ3q9k+KeBongr5imDt37v5A2sMPXEbBsmNeOkccEB+9 gOWlThjr1UqPsDhXrlzOGiEWCAErhQ/kb1kkFklR3TIWTeX/9CxHZ4SHv4+CBM07/zj6 xuCUgbuVeYCrnguDI8FE4focznZq0+h2SLDfkV3AN8JShXrdTyIfCNiWD+K/IkbnJw0f glwnKMyhzOomUQze2wne9PeVoVW7KPfL56jTJYRcOP6L3h4UJ2ZJAq9yqtV1Ze7Fpu58 KhEA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=PC+79P6z; 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 cl7-20020a17090af68700b0024df68db37bsi2627381pjb.158.2023.06.09.05.17.04; Fri, 09 Jun 2023 05:17:27 -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=PC+79P6z; 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 S239258AbjFIMFJ (ORCPT + 99 others); Fri, 9 Jun 2023 08:05:09 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51968 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S240233AbjFIME7 (ORCPT ); Fri, 9 Jun 2023 08:04:59 -0400 Received: from mail-pg1-x531.google.com (mail-pg1-x531.google.com [IPv6:2607:f8b0:4864:20::531]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 092C1185 for ; Fri, 9 Jun 2023 05:04:35 -0700 (PDT) Received: by mail-pg1-x531.google.com with SMTP id 41be03b00d2f7-51452556acdso543718a12.2 for ; Fri, 09 Jun 2023 05:04:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686312274; x=1688904274; 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=PC+79P6zld1xHv0iEHUypxLnb5f8t146nEumIY8vCPreM6HtGZs171xPu43YSEfAf/ 8tXWLXLwlc9ooEQ0fJ6wWh/m089QFWFXnDemDLdCN5bCHqmnsrgAp5e+NsT6yw3mkXir ONjMHZPTMPaCQHufwndsdcuzCIi3Z/SyDW63FuzJnKgNWFlnvj7rSG5G+1t0nZda0KAK lJ80H5jIzAP1DLiE7cyVTtFL1ZkvrkP/2cU6O8ZxpsMwaVfyV5TyCHDVztVhJftPdBjD VQj+jNKOkuTjUvSwWOZbkIWpLkhLxZJ7dtq0gV1dqRvurp41kzdhjk9GF0xDSl4gljnC iOWQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686312274; x=1688904274; 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=M6FZGKd0AnvfmmoZo4qmplVsKRppDRBjSu1Z7G0t1SoupaUtBx6ftcYvXDwmX1aUmo Cquq5icrbBKHg8WqFZ84NJL1TasdGhWrtSrZByhtxQ1V8aLHcqGJx3t3QBrNPA091eM4 UDdenEWQ5b+3ZugBg9o4LYpNmb+k17dKy9k1gMBfp2lrHvZkoAVeDTB8bUKnjjs9wWRX plj2FDk+w3vPXdK5jlhTuwY3D5LdB+mnJ9w2acKKyupbpdXgk4jUhG0dlzzaOwIYr6QU c4oKpcXmw1NjU+Rb0juU68UaNlbMVboT6KGc9iROVY3z93qffYSb43B0Lk+TMrDAPkAv ow2Q== X-Gm-Message-State: AC+VfDxRpsb5ziyRzVx8ZM299xgT3Eb7i3gAI8UKa3pKNj2zzhdO6shz /5qScELYqPdYmj6QDbx3vK+caw== X-Received: by 2002:a17:90b:164c:b0:259:c73:65e6 with SMTP id il12-20020a17090b164c00b002590c7365e6mr816107pjb.23.1686312274507; Fri, 09 Jun 2023 05:04:34 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id v12-20020a65568c000000b00514256c05c2sm2619168pgs.7.2023.06.09.05.04.32 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 09 Jun 2023 05:04:34 -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 1/3] maple_tree: add test for mas_wr_modify() fast path Date: Fri, 9 Jun 2023 20:03:45 +0800 Message-Id: <20230609120347.63936-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230609120347.63936-1-zhangpeng.00@bytedance.com> References: <20230609120347.63936-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: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768227389810432342?= X-GMAIL-MSGID: =?utf-8?q?1768227389810432342?= 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 Fri Jun 9 12:03:46 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 105589 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp903091vqr; Fri, 9 Jun 2023 05:18:37 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ7iTYLj4S+a6MvXuwVyQcGjd04B4UMKDDMRVrbSBHhHNTbiUNTiXetZipQw7/8wMr3baN0p X-Received: by 2002:a05:6a00:17a2:b0:64f:7a9c:cb15 with SMTP id s34-20020a056a0017a200b0064f7a9ccb15mr1126141pfg.11.1686313117186; Fri, 09 Jun 2023 05:18:37 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686313117; cv=none; d=google.com; s=arc-20160816; b=puQB981JjrAxxQ/WySfBFjzfXFiEOHowAN+w9P7g0Y7wQeBxN73u7Zn27Q+yXO/zYF PYJm4A+XAlGeIaTOZDk731ENEA4wf4bYQ//ZOwm3M3DAUEx4Ai0PIJ+VhpwdttstBQB5 +RGvFQ2Ip5pbwg54MSmDIWKL4tVJON1wCMyVW1XVdH2KhEouYzccHNaOhT555Pif8R0r EEzr8QfPggyN4Q+BkBdpofQRWtN0IMTbieyHe3eUdH+HOhsZ7RVzH9SIMfVUNTzOLXs7 fpp3AJk0RDFPxv/pHxNSmV2AFq6acVbmuZztyqyKnLqZkRY/ir//D0bFxOjS+QWjANs5 duqw== 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=jL1zyrCsP3IyIQZEOeNmddZJSl3qkO5SMTODoFeq2wM=; b=M74lnxH2dzTirRF6FRFe10I/JWk8p0aqFZBYA54A5huKqpLD8U2rnfq8AXMr82YUZr q6POqGa0kv+kqbQjmHnv1cilqEw3wf0qmbyjwfjb2LrYzztn/ufTf1BgiMhSn+R2AR5t fLN8PiGjIPWqEPaiGIHeOmeTMwk44ySIC4/KpueW2pBrt+yyWzDI4uDVa10f4CBnphsd +ZIQt29xGJ18pKsDHuel2v7nKuKazMKFmEk7cT0REH0DrX682/eXivyNoP8Tyxxo6dTJ pyYKGPAwYq7EgNH2IyW84BSQ0d8yz63piPIMt6qzXzukcg3mTLPp0xXaPYiQT12+Bd/C SAvw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=Gsx26ftx; 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 g3-20020aa796a3000000b0063732344e2fsi2409524pfk.190.2023.06.09.05.18.22; Fri, 09 Jun 2023 05:18:37 -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=Gsx26ftx; 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 S239495AbjFIMEk (ORCPT + 99 others); Fri, 9 Jun 2023 08:04:40 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51988 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231183AbjFIMEi (ORCPT ); Fri, 9 Jun 2023 08:04:38 -0400 Received: from mail-pf1-x42e.google.com (mail-pf1-x42e.google.com [IPv6:2607:f8b0:4864:20::42e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CD9C11A2 for ; Fri, 9 Jun 2023 05:04:37 -0700 (PDT) Received: by mail-pf1-x42e.google.com with SMTP id d2e1a72fcca58-651ffcc1d3dso1328085b3a.3 for ; Fri, 09 Jun 2023 05:04:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686312277; x=1688904277; 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=jL1zyrCsP3IyIQZEOeNmddZJSl3qkO5SMTODoFeq2wM=; b=Gsx26ftx1CyOLFjHK1Iey0HHbvMHRqZFye9C373qPvnSfcCcMpNYFN2Z57E2PqB9am NbEYjnVKZUxWntdqaCW5M8xWUXHWcwX4lvW3/HiJV4NIyKczYExvZC58nr8Ty/u1q/UF kAyymqAnVU/kjJi3Qh1Yu4z6k9bJdZBbZRwTHkrzA41DfdmuJxRoVFdoz9bawNnffH2V sjePu9crSP9w9NvNlT6zn+KdBRotkeVlUEwamMNtmUlafxWjSPCt2iqDitqqcRKrZ7H6 aXhB5+ydO++F08JoNLBn96lp/nHrJ19Sf1XX7PaxX3VNnjfplmFR4GjOuK03MtXxUjjt n/lA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686312277; x=1688904277; 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=jL1zyrCsP3IyIQZEOeNmddZJSl3qkO5SMTODoFeq2wM=; b=C1vlNOW3iSM/ZAyd0Zogrv3Ist5Az7v7KGtD6owecNlYVMkGbG5JsWI7v1yA9hjoqA 2aWI4ynETmGVmUAVXTAapgDORkpFygW8EWsn2nwebaD1SDnIU3E0q9VLR8obrCrkqibO bBiqijWcC+VFOqSCURyCIDzngG0isBLPxWAnWhJhXJRTybUQ96B7jtzLbsOw3QZliVMP nheqyI7i5k67CrLvb7BL954GRhKtEAup4X5pJTWBcciUPk+1GmUuE0bETbzxVxXi7/6a I7XjH2vyx+8kqYd27ThsCXHusA5oI6KhJ7pQDqlZ4e3m+rVVjTafm5K2/ElD44hR6nrs jFDA== X-Gm-Message-State: AC+VfDwDmNJHb+4wS0rmwbs47rsNtilNVPksRVaPDfm/od4rtCHooJCw 7HxM5RR3PqhPp8aQ7Set+J8vkA== X-Received: by 2002:a05:6a00:21d0:b0:654:100f:bffc with SMTP id t16-20020a056a0021d000b00654100fbffcmr938338pfj.4.1686312277267; Fri, 09 Jun 2023 05:04:37 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id v12-20020a65568c000000b00514256c05c2sm2619168pgs.7.2023.06.09.05.04.34 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 09 Jun 2023 05:04:37 -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/3] maple_tree: optimize mas_wr_append(), also improve duplicating VMAs Date: Fri, 9 Jun 2023 20:03:46 +0800 Message-Id: <20230609120347.63936-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230609120347.63936-1-zhangpeng.00@bytedance.com> References: <20230609120347.63936-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: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768227462705658166?= X-GMAIL-MSGID: =?utf-8?q?1768227462705658166?= 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 5ea211c3f186..a96eb646e839 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4269,10 +4269,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]; @@ -4284,16 +4284,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) @@ -4340,7 +4351,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 Fri Jun 9 12:03:47 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 105587 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp902650vqr; Fri, 9 Jun 2023 05:17:51 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ43G1ptxX/rPJndEK2X6AmD6IrJpLWCq0NC64hKqYVdBWOs7Z3f2qxPCOOjaWRnBzsQjOm3 X-Received: by 2002:a17:902:ab10:b0:1b1:8900:5211 with SMTP id ik16-20020a170902ab1000b001b189005211mr658148plb.28.1686313070635; Fri, 09 Jun 2023 05:17:50 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1686313070; cv=none; d=google.com; s=arc-20160816; b=k34xeU2AuR8Mgl3znPupZFV6SZI8NoP5MBlJN58Ge421wE12PqleCgPH+923ae+FL1 LPoP9TFyr3WzfQYi6yG6KNrpalGizEex4OGe7yzBwsp36JTB/OcozHv6+y6uqY9b4L/a Kfv5w/bYVhyy+ZqBMBWzUV/g8gtzaqIY+Vfjcfa01ZsKHxhbmvYczXzkUSIXEwWEl3dh oYehr/3SycFzYuodDK3fvjPy3pD/89z39O751XJ6Q7fb/408IVYsmOF9KwuRt0pkfQG2 MWzf9Ulz5ZRU3j32mlYh19pf0m0Ud0tYgUd1KELlXscFoG7f3G64MotzFON+ljobAZT8 O8fA== 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=ThxP1hd6NEaJLYq/dTfUmO4X1zEOytHqUc71DH0irxQ=; b=rDJxAdXjLsa8sQ7HiVPd1MwEHx4yazRd51LB1xEvo9i/J1XmKV8ORDl4nK/vdNbSem ZCT/73G4MSAdeoJA9jRgDJLcbrT29W39pOw4yxbG0MbJk1mE0yInDyqOgmI2zaoWmsSg BSePgJupx5T3rKzruw4Bo6bngocZPRb4sLC9ickMvnJuQhiYKY7CATHYZ4qilP1nitd+ L2LcjkjSj8DOI26B7NMLb97eaGU7/OflekR0c67NySmFuPtG1NgFy2ih/FuxwRZN7ctE I+Y0cRe/6PJFDX9lZ/+CF+Yg3HB+T/2tijpA9eBZaz+RpJcIv2cBCKfDQDnDoJK+KBSm 5raQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=kMMLpjBw; 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 p13-20020a170902e74d00b001b0424c4f88si601890plf.182.2023.06.09.05.17.35; Fri, 09 Jun 2023 05:17:50 -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=kMMLpjBw; 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 S239852AbjFIMFW (ORCPT + 99 others); Fri, 9 Jun 2023 08:05:22 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51998 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S240295AbjFIMFF (ORCPT ); Fri, 9 Jun 2023 08:05:05 -0400 Received: from mail-pf1-x435.google.com (mail-pf1-x435.google.com [IPv6:2607:f8b0:4864:20::435]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8F01D1A2 for ; Fri, 9 Jun 2023 05:04:40 -0700 (PDT) Received: by mail-pf1-x435.google.com with SMTP id d2e1a72fcca58-653f9c7b3e4so1324755b3a.2 for ; Fri, 09 Jun 2023 05:04:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1686312280; x=1688904280; 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=ThxP1hd6NEaJLYq/dTfUmO4X1zEOytHqUc71DH0irxQ=; b=kMMLpjBwxBk6nSkMVj2MvpBmf13W42BxXy8TzuQQLpO1GcgdjEnhCRcGYOseOwBWN9 p2PamcOYR13FsRJBqxk/qPIzItSO1QQIWMo7G3dN+QyrlK9Grk8SkdJxDikiQeP4Es7U y+z7xVJIbraUjhaDT0+yEkT8TIBWpFLDTvMhgkiXeO+iqB/LcWp6nufUcz+Vwh06+eIv K1H3DsHCciHA0j6sg69MIn40X2CsiibTE9IiJuYta8HibBzJWhjRYVzwj1oYEJHlu8Ws TnEQvPGQulRU6wMKpNfJX3UD6UnfTmez4XNWpUcZFQHLg6hAQILHJUG+xr9h8u8nRftx jFQw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1686312280; x=1688904280; 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=ThxP1hd6NEaJLYq/dTfUmO4X1zEOytHqUc71DH0irxQ=; b=Dl+2NqHRATFZ4s9UL6qmw2GGHCCnrv1+oB2dDxJJzV3SVsQrUueuV603jE8dVSadfw aaLtigw4aL1WgvgVLJF2WwNe+BDCh2SnPl8n+KoEFfx69h7hwtAlhc/fLlW47trZjzez JU0HGfAw2v4vyYXNzP6c7nIwV8YprAqNH5ag9T3k25jZ6+x5Ia5hmiEZmbn3oT++VeVh bJiLZAu6ZRLHqRCk4NW2MpRfO6jQX2Pgqw8kSRBZuYKWULD2ahGd/6dTnox064ZoZojP O89si2Pn/UM2Hwi9/BUFuPJcSIC9tikftqBq4njgjNqWoJnWUmuLZCZAw8hQT0Wo7jSY vCAA== X-Gm-Message-State: AC+VfDx6JKAjmfnagYmh1HAE41zAGpqkQ5f+5/vrCgXTP+tWvjbAD78Q f0BFxT0SJl95posDMad9n+iCjg== X-Received: by 2002:a05:6a20:1445:b0:111:2f20:d48f with SMTP id a5-20020a056a20144500b001112f20d48fmr803105pzi.53.1686312280069; Fri, 09 Jun 2023 05:04:40 -0700 (PDT) Received: from localhost.localdomain ([139.177.225.249]) by smtp.gmail.com with ESMTPSA id v12-20020a65568c000000b00514256c05c2sm2619168pgs.7.2023.06.09.05.04.37 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 09 Jun 2023 05:04:39 -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/3] maple_tree: add a fast path case in mas_wr_slot_store() Date: Fri, 9 Jun 2023 20:03:47 +0800 Message-Id: <20230609120347.63936-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230609120347.63936-1-zhangpeng.00@bytedance.com> References: <20230609120347.63936-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: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1768227414356184164?= X-GMAIL-MSGID: =?utf-8?q?1768227414356184164?= 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 a96eb646e839..d3072858c280 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4167,23 +4167,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);