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: 13273776 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 29957C7EE2E for ; Fri, 9 Jun 2023 12:04:39 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8F2038E0005; Fri, 9 Jun 2023 08:04:38 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 8A2898E0001; Fri, 9 Jun 2023 08:04:38 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 741BE8E0005; Fri, 9 Jun 2023 08:04:38 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 6464F8E0001 for ; Fri, 9 Jun 2023 08:04:38 -0400 (EDT) Received: from smtpin06.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id E8BA1C0219 for ; Fri, 9 Jun 2023 12:04:37 +0000 (UTC) X-FDA: 80883077394.06.F4B040E Received: from mail-pg1-f182.google.com (mail-pg1-f182.google.com [209.85.215.182]) by imf22.hostedemail.com (Postfix) with ESMTP id DEBE4C000C for ; Fri, 9 Jun 2023 12:04:35 +0000 (UTC) Authentication-Results: imf22.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=PC+79P6z; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf22.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.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=1686312276; 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=Pr1UDkerQ5a+fCCegLZYkrGdXsawupSGYdGvSF+y4bZh1vNNQGdex/6BXtPqrRSGpWLb8X K5SzDr9IxSNHoguYflD41MheY9x9OJZkv697QqYnZw1WrUDLB91mQUbk6kHsOjKQOk8RII Cvr+duFR7NHrysl8AoXwGx2jGWsOhA0= ARC-Authentication-Results: i=1; imf22.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=PC+79P6z; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf22.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.182 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686312276; a=rsa-sha256; cv=none; b=jZy/JRZY4TEOACZev0VdOsVnV4XbUCHzF+95rIP7h8A0obRfbS8yvH5crkX7ZTABePM/iY 4dNeeH4pvLIUA6P9yrq3dd0hlWrjlvjVfQYCq//Ye2x5/ZZjVFpU3/aIQfwryVtTwrRpFH BH87utDNoaqzfGVoJ2c18hbGuLoiw1U= Received: by mail-pg1-f182.google.com with SMTP id 41be03b00d2f7-5428f63c73aso548959a12.1 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=IZZ+1D2mN2pPxP0nzUxCAaRBCZplfHAeIgi8hTON8DSaIjkl89BqLOEozlofIwYzbG U3CGOrTmB/f9wuhvvZZkas0r0vpyaYoRddLglYGorl6uwWEzHLDUIgAxk3WCoruxQ3uE 4M1OxUJsyGjMYbuGS4lwoU+WlLuNibt2s+Z1RSgzBqX4QW1tXR/3DCK4nQFhbSeyqIs6 RIvmpRRUxTAAjY3CRNcF+XwjZX1lsNfqog0NPCq7tKk89oFjSXh1M5ooAGphxuA38hVn f/hmpkpCZhDVU3sPLUgWBgyoL5iKyPRqmx2+dUrasijaFdev6v2MPK2cwm92JGg9/hcm r+bg== X-Gm-Message-State: AC+VfDyCpjbsfZifbGK6iI0VrlCmjOGsHr/ZDHISm+xVwtsBWPx6pGHc 0kVrYKupx4ZtFSbnTjbrUVV8bA== X-Google-Smtp-Source: ACHHUZ4c7S/hhzd9J/cuoih1FnFVo/eBjSB6PM9tKj0JZeYoff2Wj+X+185zSOQly4NC+px2oyVHDw== 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-Rspamd-Queue-Id: DEBE4C000C X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: yi7at4uuj8qkfbbac6u9ak9qapqadtzs X-HE-Tag: 1686312275-904817 X-HE-Meta: U2FsdGVkX18muX4mVtelXzZZZa61bR9o+lQbthzEnOh0zDzsCtAtTZJzBbAFL9d5uWfvfK7GTmB0/GcMZ17j1A7dSFUK5b2yeSsmsjyoyOJayzEG5MUrsqNEwEtJ9ejOh3lCuUvrFPHAFrtoOY9gC/JM9y+bg67ZtYeUYLni7bt/7YKBMMbZzWI7LQtC6IMZvh2gNzhtAchchjbenRmAgyv1Q5twAjChM6TCIBfz0m2g249Yqjnvu30vjrf6RpaCo20dfRrD4mybiA/lv7ndato36TxuNHwiFxmDJ+kO9s5l8U4nlsWlE/43j8FDBv8IJxwR5Z0Sm15Bj6DFglxeqCkqy/ly+Do4P8E+OJFWHvHnuC2bnyF3bHMFn28o0SJZTTIJzW8JFb8MPxnK54WlirCK878Zdal2XOUOuTPA1LKQflUZW5ifV4/msFE2VwlpWaEk5CCGmHqetdZZRsio2QOhNhBqhnuC4xVhKOo8umjPAaOa24imOrIWTCLsJAoXiPRtNEcsO7yZkZhboVc6c5J0vrA0ZwgU3rQAgbmRpd++Ife+RodCMNJV0UzSMCDqC/Qfg9oiG1AYKDJWclukL3lKzSj9vAb3e06xyNvuLVptggUfjYpoOiZKdr7y+ru9uxUfUFCFNwgKroQY8pwj2EWfeL2iy2OUOL+chjmTPwsq76MPd7IPtxJBOEt5neIfapVdT4hX6GNzE7msn8kBBmJELfJ4yrZ4bSMdUP6JbEQlREstP2S+DfWsAP45UHpBvPCZ68lPwgKpkE6LuNJKwNwre/nRDOshS7qLCrgl2hXy+n1dmyNZAjw0F1Dla0+o9zKmwzjO7LhFp9oICRaYShhlns/R6LmkLX8MuDfXQmb6sKpbT8xgysBvVmej5P4RL3Aliuo3uqRmFukQEHSRA75mUrVDwD9fg6NQbBPL3pJp1HQ9Gg3d5M0x+Gg/+cZBtF6f5+GiOr9Fm34S5OX PVcj+ZH5 IZOxAQdYaUBF1iQ96V0tpj+MMfCrNU4DOkUkDobj7Li/VYqmF1xviRv/x6iSUJ6XG2rs94KX0ZsXL8V9WzRzTZIfPFtlUmS6IDjxgMkgCKr6heRZdBpQ7L4BtRb43PR+QbjYhdKAkAoD8quq27MV2H6bvAg3fA6SXgEyK/RrqJLXKGmGANw/e6nE0+62BTJfTuacghp5/4wc37NDnVhvOX19Y4RAdj2AuYPJutP71A37CkeYl+BYkZZbRpQTvF9Gx2SmSMOo7QewjSH/7EZrjV62pHqclCKRiD4JkNTsAPC/Yk2DD3lbqMmimk4mAxuNEHacWOIHyLNfVO2DwClAtL6l+FB1Wx6K6olEoBZIAttIrwY1z1ZHKzowkeCXOJi4qo+C/St476OskkMjX0z3w0CCyEx+J09ONuqgeP8CWTyUBQcOf4MZa/ewLdXqm8aWuYR8NECOjNLj/9AQ= 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 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: 13273777 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 41F27C7EE29 for ; Fri, 9 Jun 2023 12:04:41 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D5E548E0006; Fri, 9 Jun 2023 08:04:40 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id C984A8E0001; Fri, 9 Jun 2023 08:04:40 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B605D8E0006; Fri, 9 Jun 2023 08:04:40 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id A8AD48E0001 for ; Fri, 9 Jun 2023 08:04:40 -0400 (EDT) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 753561C7640 for ; Fri, 9 Jun 2023 12:04:40 +0000 (UTC) X-FDA: 80883077520.20.0E34D61 Received: from mail-pf1-f169.google.com (mail-pf1-f169.google.com [209.85.210.169]) by imf01.hostedemail.com (Postfix) with ESMTP id A10F04001C for ; Fri, 9 Jun 2023 12:04:38 +0000 (UTC) Authentication-Results: imf01.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Gsx26ftx; spf=pass (imf01.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.169 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=1686312278; 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=jL1zyrCsP3IyIQZEOeNmddZJSl3qkO5SMTODoFeq2wM=; b=a0yU4AsCD2fM/l2ljt0vpzh0ahBNtfcA7kCPrjxD7o/4SF++w/4OG8EgNBdP7pHd0HwtRG 2F8nbOn/HOlH72rvukXTsvQuigTgc5iwHZTcSVsRs2Gw8qMw35AxqMQwCYaEk+j9vJ3/0u SX8iYde0okNmQMarCEdr/qG9C5Lmt4w= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686312278; a=rsa-sha256; cv=none; b=1B/vOpXX9EmDw11nFCU7atbhA4ELfjfDl9yXVnR5rN2JPGNKX6hO1XY9VclIkkpbgiu+QY VpwsvA9t285CUqtMh8V+HXBfUZCnIvlYKLS2n4bm874aTV2DDJ1kvV91VHsPISAfy69Rvm 7oe+9Bbb+e++xlJFkXEAH7qOypI8lGE= ARC-Authentication-Results: i=1; imf01.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Gsx26ftx; spf=pass (imf01.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.169 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pf1-f169.google.com with SMTP id d2e1a72fcca58-653f9c7b3e4so1324731b3a.2 for ; Fri, 09 Jun 2023 05:04:38 -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=ctm7Ty7AUU9VMirg5JEbUoP9zx5Ze5+1VAgFIFyFmtjZp6jHXE0sYuiTA+kGalBzzR F6LCiOlINkK6wxL+EE3r/IDC3MxFC/g66lO/0RYyJPfM3V2sIkdVolF8iUIfd0SJDRcc 5Bvax1i6zYLrrrOSjMZo221YRHozM3oOnFo54iKlrWGGCg4II+9JWAWCcTBToaeNCm0h ypaQV8UOrcf6J+1X+OEsXGhF5+R0gyxNEUpULmjwh4YFzn0VuC2PXDsEhdxUJePfShWW uNHj5+FB/nBdhwg79Fx8NEtQwcVDvGJvU7E35wdi04YIogPkALTYzFJckLNLaKVTdoXQ 0gCg== X-Gm-Message-State: AC+VfDxzu6rHA8OUab/Uu2o7Uylhtmqymig8Ne9LwXnKyoDqGpzMkqZx xgsewtlqtcbmCq8gMnEHoNNTDA== X-Google-Smtp-Source: ACHHUZ6F7zQNdvlQlu66gpRu8wSi/BuDCO9wkbiibbLKyy50iBdhniNxE0EEiDy15hFiNJ/jReow8w== 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-Rspamd-Queue-Id: A10F04001C X-Rspam-User: X-Stat-Signature: 9z1hz4xzbjs5jo9warmpfzzmi9o73t6z X-Rspamd-Server: rspam03 X-HE-Tag: 1686312278-212262 X-HE-Meta: U2FsdGVkX1/0eD6lBkWxyZj0wjTClmpl0H/j9ZmOVBXLb04S4rT/+7SejN7Ndn9GOSwETxkYvJfMBa27KguWGW5ohzOfP8R+cCWyuBLZyjyhbp0eBMsqIsbsxXQorKTpaLmXGCt9mYJXSFQVXBb0prDWRQnMKe2devZd4S0gwBCsD2XyzSSrpHwY4Nalzzyb6uihZUyPwxQuwRRpliAiLPWNK4Gegu33vdREiYTMn3co0gTur+ke87mFEg5+TpOMbWCk6XoiiBkrGwIG4xsyGAJwqTDsP0HFT5AmYDGaPVMUxG3Dv3qxS+QnDQClGYTmiDrEPiAd8+cFrBbXkx66+WemXdA4rwA36Ag+sbf1/zIZCf2IwIeeJw+GdipZ2dB8lQhAQvavMM/OASYT1eyP2MxIMUMA+BofVBEXLH++Rw+KBh3RYtGn0jgDn+HNQ/Wcbu6LMKYVjNJM74cXMKO0yKCxtjtExB0+c34SaLsj5hFVd7ep9fHmuCUdmXLkCe6AOI0Ud2pB0BSiIfxKCHvyk2y+Hewq/yp2CKID93bSfzYKaUVwKc/kDJ2Ds0zXGXbSJqvb+Y0IfMOCLWYNw5N64yvPAQDeGTf6DZ2SXRiualr2TtSdeMZd10n9zEwJ1SjQVRp8itBsFYd82HuG+S9WG+A/eIdkDrJ+nYV84/R78HYDnAZ8bmZAzmnRES5n6XvN+UHqq9rV/PEmAmhpYeuwYETEnQrNUMepG+UlQCtfQKyyT9I6x0aJTVsdIV/1/kF5rz79/qL928kmbAxjSn/5xfDiizhWLKYUa8pFoYzTamP8hoTSa28+fo4W38rLERbbDb5KFariECDZYNOPSBUm9Zl+5oFYVcZmY89aoOAB9keSzZXL4Az0XPH/iQ/E3VEDgCtemAlBWwj1El4sfeAlFcV/+o9yF7/yXrA/QZHMeym/Wkk6sTT96KEaVLmVqWlaKfHYIVfTI24qiBlGZ1V QtteoNjP AsSo2qOc+S3P6yBfFeS1yQpexYdCytlXOiMeq1L1Mtq7OjzxguanoJ3k52L9zdXu9Ozu4cpm6uUnig/G8fiqgK+JKTJcrfq7/ava+vYg7V1SyxiOdyAcLTRR9bC9p21ds9WpO4cmbp1ulvBxCqcoezNqrhOlzHPGEQOHv2GLeMjz3Ui9UMwESjXg8VR+4K9AI07NJRy3p5QgIv16b97Xm6/UN48//LPFSm5i2x+m0yhHMFEfNZqNip81zTgpdEe3vaoGKpM9UBM0cD0v2wNPU4uvylYPWVXxS+09BxlXx7KB+1Hn5Zfqc710wd20rG5DxTm2zJvpY5/+bShR9SeSD6R4aLU+dLuSaEYQTY1v9QA54AoKI8biA+v+hfJopDTMy6V3g283epBDGl9pxMOVIQHVfFVWrPyQGRzdS5EsP3jUZzFHIhXmnff0MIoGiYpumEriQTVhhq1sI4riJ9SQiz+htsAP8VrYhvwdT 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 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: 13273778 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 770BDC7EE29 for ; Fri, 9 Jun 2023 12:04:44 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 1287C8E0007; Fri, 9 Jun 2023 08:04:44 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 0B1A18E0001; Fri, 9 Jun 2023 08:04:44 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id EBBBE8E0007; Fri, 9 Jun 2023 08:04:43 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id DD6028E0001 for ; Fri, 9 Jun 2023 08:04:43 -0400 (EDT) Received: from smtpin08.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 633D116021C for ; Fri, 9 Jun 2023 12:04:43 +0000 (UTC) X-FDA: 80883077646.08.41F2F2D Received: from mail-pf1-f179.google.com (mail-pf1-f179.google.com [209.85.210.179]) by imf05.hostedemail.com (Postfix) with ESMTP id 524A510001C for ; Fri, 9 Jun 2023 12:04:41 +0000 (UTC) Authentication-Results: imf05.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=kMMLpjBw; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf05.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.179 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=1686312281; 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=ThxP1hd6NEaJLYq/dTfUmO4X1zEOytHqUc71DH0irxQ=; b=k9Wtvi6SQyPj96YArZh3nfcV77XYFcKmG6gGJA5JSjoeqwqj5uPLD4GkQPLtc9zvFfWwdJ L3EDZwkfaNgOIBFT2niBXmF/r4HNlyWhHietK3dQr+8rSz3Dc2IVKsW1QLEzxgGWVX1pCx rFHPUh7sbVlclioqkM+Vhy5qBGCRvzY= ARC-Authentication-Results: i=1; imf05.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=kMMLpjBw; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf05.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1686312281; a=rsa-sha256; cv=none; b=5RA9rExC0bnwgw6rrMkGX3jnRQYK3L05k4vHlAxru5w9YtYcrCe/nYd1opevpCM5Z9TXvE yOV1aTXs7dO/8q5CFZy0B8tHPSjXlAwRFhGtkY6dTokStFApfJZ4jssXNAa7oQUrxXedba 1dnT7uGTUuCo+hyVZV6QfX6aX/ajOuc= Received: by mail-pf1-f179.google.com with SMTP id d2e1a72fcca58-651ffcc1d3dso1328120b3a.3 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=IVHW8jMs/cYl3CoQ8SH96fHG92TjyvsThuxefu191Tb0c3F6PdRgfPdNYDA7a/3Ttx 8dzW9r34B8o2pufnCPxSuOEs7cCfoKFg2myZ0OiwKxL5umEBX3vxiSRZLw1EkQ1hzKQh ccseEFr0CgV6S8gcMBVXcKiZT6L+cUNI+vVgwqykWgSkoVR6f8YuRH1GEMs7X5mlX1Cw JQBERc/0IWfr37kDqizkhoxyOCNQr47nsGRlu4pXsmBM0oS4gFvOGqLpFddMJ0Zk4vjX LyleV0toFAaH+bd0ddRPxfdPH8jc8o+qrRdUbSjlqXiSkSB7+QZObpXYxs4i07CLVOWt jGzg== X-Gm-Message-State: AC+VfDzEU5QPSTUiQu38fYToxOAUO0oYKGfcpfp/+THj3r76LML3jVJH Eies5q9wQv7X5tdr2SZU9cD+bw== X-Google-Smtp-Source: ACHHUZ5VTTHHjw53wUTNz1vUMTc24VjUz/r/h9LU8ikZx7DTRD/CLTI0AgOZICIklb1Pe/GoYz6dvw== 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-Rspamd-Queue-Id: 524A510001C X-Rspam-User: X-Rspamd-Server: rspam04 X-Stat-Signature: 4u6f9au8cxztdah6dfjw5sgzi975rcio X-HE-Tag: 1686312281-245293 X-HE-Meta: U2FsdGVkX1/PjP6zyC7d+uRtB+xQa9392S00QtMYkyPYw0whmbesYwnyH16DtKWEO0R8K37TXOOuZ06pIck83B59ObhYydEdFCRQvVQhzo2MshVWAkz4CcV6CID1ldpSTsw6etBt0lhvikGicJpIlNm988ynisWMlgCiVeF4Bp47yjB0KnAq3NhlzRkxYx8+lKPFo0xy0zop/uPdOIcpjeNaZQzfJdgjDkOtDQR1xXfcEypj1lWx7M6aV1eC8BSe9Ww5DPP25zH1B47bBApw9sLyWSvd2Y9X/hQyFvaDDgvODx6BXkcf1Ce7wlhdR2BOtTdBRQ8sCgc3NM3HcBEPUCsw4zC1KyP0tl/mVXTswwIo4vHom6dhM8hBUu7Tc+0IjsfhcW9D8T3bznDcY3pUFJBQ/fK/sN5Jds5E5Mbwn8ktk9q45d5CTgFk1lorkY4L4ToD7OWFcdbp/o00SwIKIZUQUCmirGmEaFj7SFkFaMNjsDF7pwkjqItvRPtAsRD80rxTQezrVfarWftMh+hn5trnEY00WRK3mxBxhITJh6itX8K3ehPpMkFiQrETzD0zxR/a1aKlwDAXFzDwn2mM+cajW8jqHncMH+FKfTIpyqsWvBOvAG4T+UHwl8md0dmGCO3fdLPNS1pyqWKe3mNbc3lmGSF9SZV9325EPwgIVHYmikh6qsax8Z/WQNFmYwZ3yhWP8WjrmjkszoS1a+Np9JH5SOxDjVoxif2Z92NR+rjlAUtswFgPX1wG4YHvYcOUuIZZVFDdyea8C2SdCa2gJM0WE5qWAqJm7x0H5XrV06UCMZm1GkALV3SyREsn8fL+Jsv4Uvg2kJB+ScTWUGrwcWjLALKUvQBYtEC6NXIYX6Dw1je44KBcYj8QEE8sg7xt38bjK6QvL9OvkhqHzhAlCqMChUP5tTk20kgqOD4IOX72Y01dA34otwINufGmAk4NMW7y0jonRdnFqldEdM/ DyIK/7lm ehxkWrvF5yRDou6aSnCnsc+tDLf38SRGf26V9V7EcEeNkjsYY00C5bEsVPHBvZMyWrmUJ0Gdzw3uN9thcGo5pa5WXq1flvVPKZfdF2Sf6pkYnJh2OFpDtjFGvGdfEaEU96dX+PBM8zR25ioRLXEdqX4lvSIAcQoEKl+oZNcchlvWrNIopMiQJNbIliQrTb2Rd0FBMfN/Ifo7LEvbuHt0QpG9Sde2ZvnpQUiYm8AVHPgjLMR6/FlWg7HV8sYjS8jDLh54kessMpb16ca5KxnbUm+Wbtrw2MXB7W/cIYXbmEOHycVh5PeGO91N9IrwbaGQuQMC9jsDOk4E9QEyW+fG1RFmbVtiDuM0ARDS3B6RAtUMt4De1AkSLRiB/ZlYrniBwL3oskTbVz51yimFGILCcdEYzoGBq/jU1uDFP1fcTzmbZL/ZiUtzw5fsSwmcwY6bEnM7lWgB02mrtqGk= 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 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);