From patchwork Tue Oct 24 08:32:49 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 157291 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:ce89:0:b0:403:3b70:6f57 with SMTP id p9csp1798526vqx; Tue, 24 Oct 2023 01:34:29 -0700 (PDT) X-Google-Smtp-Source: AGHT+IGt8qsbAvIj+f1icuM5iuiOFTvSVR9Wr+R7qb5bZkqpG8lj0lpoHJGUNTdGkkzXsYYbIaAn X-Received: by 2002:a05:6808:5c5:b0:3ae:1358:fafc with SMTP id d5-20020a05680805c500b003ae1358fafcmr11659024oij.58.1698136469390; Tue, 24 Oct 2023 01:34:29 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1698136469; cv=none; d=google.com; s=arc-20160816; b=Yy0WUJv8VKvUh3+T70zLqcseyOwUU0CjCMQPJ7DMt9OFKVSftVjuvgIBdZvmg7yIuC RwxRXrFys9l4wpRSBm91pjkD5RuIsiZHu2wJxHJIfbpYdhf4gnP3+ABLVxGtYW35m38q 337MbF8p6/1gxislXG1vgsuwFm/UeJFadBcvxo/Y1TW0/TVJc51qbFqU4Yq8x/zGLJU/ 88iLVHnadhTvkjdys7i1sfbbZtV6fWmp+mqV8CSPH9VC2Ua0Z+/59aRZ30mO05XI1GMt eewIh98hNOsfwcvbBGVmTCvlJfN7M81wpNKyfpx2Kd+8hjShZHOyQAF31ODz4rxZmKZp iJgg== 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=7MLK4HxQMsxrLAQzNmdHMtQCN++SQMztyyHR1MHkRQQ=; fh=W1ujNbDikRM6mL+MA7cZ93eipzimk+g+Mb7QYnlff5s=; b=bdcNs7brO3xzOJQQJFCNK/m5CwCnM4EoENbZMvs6EPcF78UrhViOBGeQeAcgHK9RO0 J6mSqRPd0jXoxIiUMuM5XxFAkOJN+0ndowXpCKF2RbwrApcKggAFWe82gsFzAvWJbDyU S5d7lnH9DzKG5KnUVT+BZ80N5ywhb1lU5XVTTeuBoTGj2siDDD4VYb6cnY6UJU3qEN8h fjv/gqN1AJOOcZ1Tt9gJok0ZDjeW4h9/oNylR/J/qAogp7skXieL/ouEALSWtiZJHhYH 6bEIddSWqIF1tAK3gVnvKq1dCzqA1PtzboMhnIPtAn4O4QbjTX+ouZCXheA4MsK8TR78 h25A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=B94SZKzS; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:8 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 fry.vger.email (fry.vger.email. [2620:137:e000::3:8]) by mx.google.com with ESMTPS id b20-20020a639314000000b005ad9894a223si7911962pge.326.2023.10.24.01.34.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Oct 2023 01:34:29 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:8 as permitted sender) client-ip=2620:137:e000::3:8; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=B94SZKzS; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:8 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 (depot.vger.email [IPv6:2620:137:e000::3:0]) by fry.vger.email (Postfix) with ESMTP id B735180B9F8F; Tue, 24 Oct 2023 01:34:25 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at fry.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233980AbjJXIds (ORCPT + 26 others); Tue, 24 Oct 2023 04:33:48 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55288 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233928AbjJXIdl (ORCPT ); Tue, 24 Oct 2023 04:33:41 -0400 Received: from mail-pf1-x42c.google.com (mail-pf1-x42c.google.com [IPv6:2607:f8b0:4864:20::42c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EA64E99 for ; Tue, 24 Oct 2023 01:33:17 -0700 (PDT) Received: by mail-pf1-x42c.google.com with SMTP id d2e1a72fcca58-6be0277c05bso3277371b3a.0 for ; Tue, 24 Oct 2023 01:33:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136397; x=1698741197; darn=vger.kernel.org; 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=7MLK4HxQMsxrLAQzNmdHMtQCN++SQMztyyHR1MHkRQQ=; b=B94SZKzSqsawfuayEI/UehMSGtS4IxKFKCX0IwoUmRF+6j0ja4TTqt59k0u7TDRF1p v8R7VVFKp8LBp57ATeW2It8DKLS65pyhb/4rSN1Fuow/XilrMzprvcYO9Ib6AryUsYvt YNxAebFQw7nuEBiyji2mdf1YCtIejq8msAXlzACmiB0SxmPyLjHzQ+MhHyFxUncgRaNY ET7bPkppLatdrhxoRPCaGsHcAf3WK9yj1xKa7paPjkbbjhvUENO6mKi7Wn9+gnuaK01H k5wygUCn0Bb+cF+rTWWBJX3aTMOhgtQZfmuJc8fNMRgGXEcKy9AQYfv8VFC5ClTASV/b OPpA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136397; x=1698741197; 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=7MLK4HxQMsxrLAQzNmdHMtQCN++SQMztyyHR1MHkRQQ=; b=Po8hkhLgdT11zcGD1J746JWFuw482mcI5gZ8Dv79Ub7LsT9XJtFdMeWM77cuINTKQ+ KYKqLpYStSFxlwWKmdd3lHnsSIoD4Bm57Mb52JAeajKd5n6HhCs/uYY5uMUc0M455nv3 nv05JMqjRpHQJSAK2cv9he/t103fsU7BFFpff0nd/IAcU2evpgK6cuUXUmwz8HUfl5B1 K7AlCYireDI0O7wteykmu1qSYu3MYhRLQsaJuVRH/RA6xwLLwrFhCjHQrzmnu/XrvKJG MWb9ZdhcWzDxhuIeZS12ke+AlefOfsusuOesDbCJAiA2m4KOSQ1dMcTYS3z7xqDlwI/A a/yw== X-Gm-Message-State: AOJu0Yz6T33oI/jsy3To7uFkmef2VVHzHFZkGN65TJDFflUMXAoTpug9 EOHVxh4DYTq1IO+E0F89eCbdMA== X-Received: by 2002:a05:6a00:2292:b0:6bd:7cbd:15a2 with SMTP id f18-20020a056a00229200b006bd7cbd15a2mr10659966pfe.26.1698136397397; Tue, 24 Oct 2023 01:33:17 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.11 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:17 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v6 01/10] maple_tree: Add mt_free_one() and mt_attr() helpers Date: Tue, 24 Oct 2023 16:32:49 +0800 Message-Id: <20231024083258.65750-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on fry.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (fry.vger.email [0.0.0.0]); Tue, 24 Oct 2023 01:34:25 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1780625146520112466 X-GMAIL-MSGID: 1780625146520112466 Add two helpers: 1. mt_free_one(), used to free a maple node. 2. mt_attr(), used to obtain the attributes of maple tree. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index bb24d84a4922..ca7039633844 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -165,6 +165,11 @@ static inline int mt_alloc_bulk(gfp_t gfp, size_t size, void **nodes) return kmem_cache_alloc_bulk(maple_node_cache, gfp, size, nodes); } +static inline void mt_free_one(struct maple_node *node) +{ + kmem_cache_free(maple_node_cache, node); +} + static inline void mt_free_bulk(size_t size, void __rcu **nodes) { kmem_cache_free_bulk(maple_node_cache, size, (void **)nodes); @@ -205,6 +210,11 @@ static unsigned int mas_mt_height(struct ma_state *mas) return mt_height(mas->tree); } +static inline unsigned int mt_attr(struct maple_tree *mt) +{ + return mt->ma_flags & ~MT_FLAGS_HEIGHT_MASK; +} + static inline enum maple_type mte_node_type(const struct maple_enode *entry) { return ((unsigned long)entry >> MAPLE_NODE_TYPE_SHIFT) & @@ -5573,7 +5583,7 @@ void mas_destroy(struct ma_state *mas) mt_free_bulk(count, (void __rcu **)&node->slot[1]); total -= count; } - kmem_cache_free(maple_node_cache, node); + mt_free_one(ma_mnode_ptr(node)); total--; } From patchwork Tue Oct 24 08:32:50 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 157288 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:ce89:0:b0:403:3b70:6f57 with SMTP id p9csp1798159vqx; Tue, 24 Oct 2023 01:33:34 -0700 (PDT) X-Google-Smtp-Source: AGHT+IGMTS/iEV6bHti+87LLqhLVyprzux4XBurvwxcZSw8Cv1ZVwNGbgLthy1X8kS3bLLMAnibj X-Received: by 2002:aa7:8424:0:b0:6bc:d1ad:d1c5 with SMTP id q4-20020aa78424000000b006bcd1add1c5mr8403634pfn.17.1698136414509; Tue, 24 Oct 2023 01:33:34 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1698136414; cv=none; d=google.com; s=arc-20160816; b=zqDMlewq9y1+PmGSxdG65GtlZBydjCsp0yosvbpUl6Z+RRYJfkJMQA3z48f9qmJLFJ 2Bb+ZJAOUe3rJ8Yl2VhKGjih0XfIE8CnIHN/M0Pc8/5j8RIFcS97dN5fFuTlFogvcFET 01C8iha4WUIygU9MCIDE6hxMzU07pD2Y2Y5NiwMYzjnv9cPrtyi/WFtltes6LfyOhJ2e 4wVbEk1z/7FEP6JJmMzzj7Zw6Z1gOM3psbm9wf3+UU59zBjT5678uP/cebr+MGZhEibL g1yPze2GRJ+XR9gjFcEHw5+Mk6s2O5ztm5WKluIYOI0bqHb0mFrAnNwF81hF0j4NlAAP 5Ovw== 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=r3L72Q2C0A6XyhsC7UMGOLSZK5Azm/i+GpPRU3MZq4Q=; fh=W1ujNbDikRM6mL+MA7cZ93eipzimk+g+Mb7QYnlff5s=; b=Tlh8ktL7kx71tBi1Rfz1uFUjcGLbScwjhiZdcJ09W3v9S2UzbEhBxqcQYM/97R+TB6 5zchyqbvhpwQK2Qnjn4UljEYr7/Q5j740/oPKRIozl1la0kEy7yi4znCm+SDenkyGqww FfLRwaPkmP9NlcUoooVz0mv0x3S88JKgW2tlwOOywTYD8jN090sE8t1gInfoP3VnPJ3a T75Bgkx+qypouQBA2JvS+hz8yQfG+NscOhsmRS7wQRTtBTWhuoB9eMpkQY56Z8CvTpuS GIDaWs+q8u/dIFjTN0ZJSzmbmkrKO9v8Rrvbnv6BrQ6ziNLagKciHx1Qu3N6jfttpgYX elfw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=kuVRWVg+; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.37 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 snail.vger.email (snail.vger.email. [23.128.96.37]) by mx.google.com with ESMTPS id u189-20020a6385c6000000b005b8ac0af52csi4533991pgd.1.2023.10.24.01.33.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Oct 2023 01:33:34 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.37 as permitted sender) client-ip=23.128.96.37; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=kuVRWVg+; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.37 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 (depot.vger.email [IPv6:2620:137:e000::3:0]) by snail.vger.email (Postfix) with ESMTP id 73BAB8030B8D; Tue, 24 Oct 2023 01:33:33 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at snail.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233905AbjJXId2 (ORCPT + 26 others); Tue, 24 Oct 2023 04:33:28 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55294 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232620AbjJXId0 (ORCPT ); Tue, 24 Oct 2023 04:33:26 -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 54E4F120 for ; Tue, 24 Oct 2023 01:33:24 -0700 (PDT) Received: by mail-pf1-x42e.google.com with SMTP id d2e1a72fcca58-6b36e1fcea0so3271569b3a.1 for ; Tue, 24 Oct 2023 01:33:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136404; x=1698741204; darn=vger.kernel.org; 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=r3L72Q2C0A6XyhsC7UMGOLSZK5Azm/i+GpPRU3MZq4Q=; b=kuVRWVg+GOfFDNXgWomsTeaxeDK5DweWacq3Eh7wQKXo50OjyMnBfSUMh2r9xGvEfT 5cOPGlpVkPwNjL5sT+eqGivC285OAWO8LyWrQejCOA69F4FNVQSJZesTTLXPm5Z7jVf0 83RE/i4wmr4jYUpiwAG5MjzsexAlzEWSxlHjM7teRNWIqujqCbSdIzKR61K71/dOJOXm Ezu6Uj0oBQqxu7nSaliDAlNU2sROr908almnzcXk7xG/Hbj5dCZiS/sDebWuYuaDGMQh IwWnYpTQWHDBYu9DMf9ChpeGRgyLtAAncNwBf4dpxn3UARsGA4r93f7Mbmj6w+OyVbZW Ubeg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136404; x=1698741204; 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=r3L72Q2C0A6XyhsC7UMGOLSZK5Azm/i+GpPRU3MZq4Q=; b=BNYfmdconYl863i4K598x44j7q7naRViVC7lvn4vym6O9AtDxyeVEmBPTlSWdZQrEw k8/Mqd3wdrKwEY+t/xAmxMINr0r+UjoGHObEGXq9YcqsIb3/Sce2Fr7tDBo+huDKEyd3 c+UlWb3esqgurE/5LCB46xmQ1vvJsWZZCpbMR24NhofGdkuK+fA+d3LN0k56BpWV5VBu YT89JkErKN0OM02PsGbkLF5gRLSTIWcDXJWY3+60eXbgR9PsWCbz8G8yDT9Rbp4G10eH W0M4NnReGTSQ2f8+TrBdik77fieHxRC6TuRm6MFxeHegfLnIekRlQjH8IoH1BuZRA7jW SHVQ== X-Gm-Message-State: AOJu0YxbmlmhrAKpFwiqhXHppIQWbucDteg2utf7V+mEOJMv0Fptvei7 uGfakq1pkWWahsvZlCA6+4hRfw== X-Received: by 2002:a05:6a21:a108:b0:17a:e79c:c5ab with SMTP id aq8-20020a056a21a10800b0017ae79cc5abmr1692896pzc.48.1698136403796; Tue, 24 Oct 2023 01:33:23 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.17 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:23 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v6 02/10] maple_tree: Introduce {mtree,mas}_lock_nested() Date: Tue, 24 Oct 2023 16:32:50 +0800 Message-Id: <20231024083258.65750-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_BLOCKED, SPF_HELO_NONE,SPF_NONE autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (snail.vger.email [0.0.0.0]); Tue, 24 Oct 2023 01:33:33 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1780625088812314915 X-GMAIL-MSGID: 1780625088812314915 In some cases, nested locks may be needed, so {mtree,mas}_lock_nested is introduced. For example, when duplicating maple tree, we need to hold the locks of two trees, in which case nested locks are needed. At the same time, add the definition of spin_lock_nested() in tools for testing. Signed-off-by: Peng Zhang --- include/linux/maple_tree.h | 4 ++++ tools/include/linux/spinlock.h | 1 + 2 files changed, 5 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index d01e850b570f..f91dbc7fe091 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -256,6 +256,8 @@ struct maple_tree { struct maple_tree name = MTREE_INIT(name, 0) #define mtree_lock(mt) spin_lock((&(mt)->ma_lock)) +#define mtree_lock_nested(mas, subclass) \ + spin_lock_nested((&(mt)->ma_lock), subclass) #define mtree_unlock(mt) spin_unlock((&(mt)->ma_lock)) /* @@ -406,6 +408,8 @@ struct ma_wr_state { }; #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock)) +#define mas_lock_nested(mas, subclass) \ + spin_lock_nested(&((mas)->tree->ma_lock), subclass) #define mas_unlock(mas) spin_unlock(&((mas)->tree->ma_lock)) diff --git a/tools/include/linux/spinlock.h b/tools/include/linux/spinlock.h index 622266b197d0..a6cdf25b6b9d 100644 --- a/tools/include/linux/spinlock.h +++ b/tools/include/linux/spinlock.h @@ -11,6 +11,7 @@ #define spin_lock_init(x) pthread_mutex_init(x, NULL) #define spin_lock(x) pthread_mutex_lock(x) +#define spin_lock_nested(x, subclass) pthread_mutex_lock(x) #define spin_unlock(x) pthread_mutex_unlock(x) #define spin_lock_bh(x) pthread_mutex_lock(x) #define spin_unlock_bh(x) pthread_mutex_unlock(x) From patchwork Tue Oct 24 08:32:51 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 157290 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:ce89:0:b0:403:3b70:6f57 with SMTP id p9csp1798491vqx; Tue, 24 Oct 2023 01:34:24 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHPAMfnZhtNBqNKULvDlR6zliRMJiZAaBLLM8UCol3dw4s1hEw9mOIzrJcC1L0VTk/Fm4Zi X-Received: by 2002:a17:90a:164f:b0:27c:f016:49a2 with SMTP id x15-20020a17090a164f00b0027cf01649a2mr8851506pje.7.1698136464110; Tue, 24 Oct 2023 01:34:24 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1698136464; cv=none; d=google.com; s=arc-20160816; b=AjYC6yh5196AsrtKwcf0w7Y5Bw+2zFq3GeOk0uZEbdsxljBpfnNxSAS5qpjeNnZvr5 EdogrJ03IBhsPgVcZIzWPLtSy2F6v5p15odhqZ03wLPzXuN7pnnvNfeoXSqqRA+sbEI2 FKRhawr+tE077aydAuVDjg0p0oHRoSSdY4jcZYRU2thjP26dfp0TrKnhK7nwv6OoVx2M DhE8pH7YAbowSetFGUoJ61n+1MnUIrav4pjAyX6myGkQjHLMS4afn+MPcP+WmLvKi5ti YmTfbDWzHS8JRQbgsImZfKfBBx2BlUnKawWjmAXvQarHd/Q4DAYC6CnJsN1iHHxQd/rI teUg== 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=lHQENXHqQ4J1FF/RY259IZhkjTrimWDCVwtt+ghNomI=; fh=W1ujNbDikRM6mL+MA7cZ93eipzimk+g+Mb7QYnlff5s=; b=vICRhVpGAVpc3vvKGjsrx85xCVdA2jY/2rJVIaqi8NGJljc08dXxKAzWfOwGw9R4Rx FfD/egSpBgn3/Vqfn/n/p8eW4t8Dlq5XTqdww83k+cY/s/zFWgToiZCEJoslK71LXxYr iuTnh9QDIVczPM1+K5TJ2IUiDLTzknStznSYRvDle5Cvd53kgyPWezG81AjL+LOP/eKP 2KKVu8tpQzCU3//JFXKvsaNUoN6oWrBbSZL13Wu8QPcd9c7oUcOlCU56a79sYbEOEVID HUYGfRQbOHr2Vm8qMa4ohCXKQU/hKZg5Es2rt839gVlFEqc+M955CtDIEF3Ss9rlV2Pi 1NkQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=CRCwxaG4; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:1 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 morse.vger.email (morse.vger.email. [2620:137:e000::3:1]) by mx.google.com with ESMTPS id c14-20020a17090a020e00b002766bd6d3f3si9022882pjc.10.2023.10.24.01.34.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Oct 2023 01:34:24 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:1 as permitted sender) client-ip=2620:137:e000::3:1; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=CRCwxaG4; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:1 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 (depot.vger.email [IPv6:2620:137:e000::3:0]) by morse.vger.email (Postfix) with ESMTP id 44C5E803BEF2; Tue, 24 Oct 2023 01:34:21 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at morse.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234024AbjJXIeI (ORCPT + 26 others); Tue, 24 Oct 2023 04:34:08 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:44442 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234103AbjJXId7 (ORCPT ); Tue, 24 Oct 2023 04:33:59 -0400 Received: from mail-oo1-xc2b.google.com (mail-oo1-xc2b.google.com [IPv6:2607:f8b0:4864:20::c2b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 38CF5D78 for ; Tue, 24 Oct 2023 01:33:31 -0700 (PDT) Received: by mail-oo1-xc2b.google.com with SMTP id 006d021491bc7-581e5a9413bso2494217eaf.1 for ; Tue, 24 Oct 2023 01:33:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136410; x=1698741210; darn=vger.kernel.org; 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=lHQENXHqQ4J1FF/RY259IZhkjTrimWDCVwtt+ghNomI=; b=CRCwxaG40xfFuG+dF24NNvdOixTbkaWt+bc4Eey/MsONgmDw7KGdZ+lB6Ij5/OTiai UPdwSqULccRu5AHv1HuSZciXVdfQcAWkUs//OGBMHBqyQ5/r9KzizZChkwQt7Vts9nDE +Rx97bkGz3D38xFthui5vqZaqa+Mr5TkYBAYKn6hbSSHPhJQHDTyD9Fu890tFN64VM6K Qhtsr5D35FBEjDmnwu7oLAc+iw2Xns1FjdfBdKpwUOTZ9Z0sIE6FQ+w8YuatwWS3XgZC jFoFwrOc1ZqaA4hBMssMdeJ9dXwXajdse0YS34JlTH+3BLbTrEhBhOIZHmDL/e+UHunQ xcaw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136410; x=1698741210; 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=lHQENXHqQ4J1FF/RY259IZhkjTrimWDCVwtt+ghNomI=; b=n9LGsz3QgGwEL8RSKjYewPPy17aYnpRm+G7aBhbbUxdaOgisyecGpkSuLlG7e/hjRL 3aCKOwLNP+yThNZAk+Anb3ITik2Folx4GSyKTXs3rOkWxOiwUK5I50Spw4NuPGk1qnon SqCxpCDZYsIn3WuD3gkAWhVA1BZV8osKwuawSaYhzFUardgSOESlYmpcyReaRNEUggCG 4tAoYdTaI5JdpmR1cjhIKrxMpXh7zHVHYOpTDPg60bh+1PTdlu+AYVdIeEqdC0L4m3Hj F+c0//FJkJ6+FF+uJb5LAz96C44AZB+9Mw9fShcF8CGTF2MwmXPdWoMdC4/7PcYMUs1e 3WLw== X-Gm-Message-State: AOJu0YziVIQQZtQgzj17yCDqB4dl7T3sP/Fa319fuD6HhCLGYWuuHH96 ahHz8QkP/V0pzX694sUNm9SKXw== X-Received: by 2002:a05:6359:8003:b0:168:dbfd:cec8 with SMTP id rc3-20020a056359800300b00168dbfdcec8mr4800441rwb.13.1698136410342; Tue, 24 Oct 2023 01:33:30 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.24 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:30 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v6 03/10] maple_tree: Introduce interfaces __mt_dup() and mtree_dup() Date: Tue, 24 Oct 2023 16:32:51 +0800 Message-Id: <20231024083258.65750-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on morse.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (morse.vger.email [0.0.0.0]); Tue, 24 Oct 2023 01:34:21 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1780625141074235122 X-GMAIL-MSGID: 1780625141074235122 Introduce interfaces __mt_dup() and mtree_dup(), which are used to duplicate a maple tree. They duplicate a maple tree in Depth-First Search (DFS) pre-order traversal. It uses memcopy() to copy nodes in the source tree and allocate new child nodes in non-leaf nodes. The new node is exactly the same as the source node except for all the addresses stored in it. It will be faster than traversing all elements in the source tree and inserting them one by one into the new tree. The time complexity of these two functions is O(n). The difference between __mt_dup() and mtree_dup() is that mtree_dup() handles locks internally. Analysis of the average time complexity of this algorithm: For simplicity, let's assume that the maximum branching factor of all non-leaf nodes is 16 (in allocation mode, it is 10), and the tree is a full tree. Under the given conditions, if there is a maple tree with n elements, the number of its leaves is n/16. From bottom to top, the number of nodes in each level is 1/16 of the number of nodes in the level below. So the total number of nodes in the entire tree is given by the sum of n/16 + n/16^2 + n/16^3 + ... + 1. This is a geometric series, and it has log(n) terms with base 16. According to the formula for the sum of a geometric series, the sum of this series can be calculated as (n-1)/15. Each node has only one parent node pointer, which can be considered as an edge. In total, there are (n-1)/15-1 edges. This algorithm consists of two operations: 1. Traversing all nodes in DFS order. 2. For each node, making a copy and performing necessary modifications to create a new node. For the first part, DFS traversal will visit each edge twice. Let T(ascend) represent the cost of taking one step downwards, and T(descend) represent the cost of taking one step upwards. And both of them are constants (although mas_ascend() may not be, as it contains a loop, but here we ignore it and treat it as a constant). So the time spent on the first part can be represented as ((n-1)/15-1) * (T(ascend) + T(descend)). For the second part, each node will be copied, and the cost of copying a node is denoted as T(copy_node). For each non-leaf node, it is necessary to reallocate all child nodes, and the cost of this operation is denoted as T(dup_alloc). The behavior behind memory allocation is complex and not specific to the maple tree operation. Here, we assume that the time required for a single allocation is constant. Since the size of a node is fixed, both of these symbols are also constants. We can calculate that the time spent on the second part is ((n-1)/15) * T(copy_node) + ((n-1)/15 - n/16) * T(dup_alloc). Adding both parts together, the total time spent by the algorithm can be represented as: ((n-1)/15) * (T(ascend) + T(descend) + T(copy_node) + T(dup_alloc)) - n/16 * T(dup_alloc) - (T(ascend) + T(descend)) Let C1 = T(ascend) + T(descend) + T(copy_node) + T(dup_alloc) Let C2 = T(dup_alloc) Let C3 = T(ascend) + T(descend) Finally, the expression can be simplified as: ((16 * C1 - 15 * C2) / (15 * 16)) * n - (C1 / 15 + C3). This is a linear function, so the average time complexity is O(n). Signed-off-by: Peng Zhang Suggested-by: Liam R. Howlett --- include/linux/maple_tree.h | 3 + lib/maple_tree.c | 276 +++++++++++++++++++++++++++++++++++++ 2 files changed, 279 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index f91dbc7fe091..a452dd8a1e5c 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -329,6 +329,9 @@ int mtree_store(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp); void *mtree_erase(struct maple_tree *mt, unsigned long index); +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp); +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp); + void mtree_destroy(struct maple_tree *mt); void __mt_destroy(struct maple_tree *mt); diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ca7039633844..6704b5c507b2 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4,6 +4,10 @@ * Copyright (c) 2018-2022 Oracle Corporation * Authors: Liam R. Howlett * Matthew Wilcox + * + * Implementation of algorithm for duplicating Maple Tree + * Copyright (c) 2023 ByteDance + * Author: Peng Zhang */ /* @@ -6475,6 +6479,278 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index) } EXPORT_SYMBOL(mtree_erase); +/* + * mas_dup_free() - Free an incomplete duplication of a tree. + * @mas: The maple state of a incomplete tree. + * + * The parameter @mas->node passed in indicates that the allocation failed on + * this node. This function frees all nodes starting from @mas->node in the + * reverse order of mas_dup_build(). There is no need to hold the source tree + * lock at this time. + */ +static void mas_dup_free(struct ma_state *mas) +{ + struct maple_node *node; + enum maple_type type; + void __rcu **slots; + unsigned char count, i; + + /* Maybe the first node allocation failed. */ + if (mas_is_none(mas)) + return; + + while (!mte_is_root(mas->node)) { + mas_ascend(mas); + if (mas->offset) { + mas->offset--; + do { + mas_descend(mas); + mas->offset = mas_data_end(mas); + } while (!mte_is_leaf(mas->node)); + + mas_ascend(mas); + } + + node = mte_to_node(mas->node); + type = mte_node_type(mas->node); + slots = ma_slots(node, type); + count = mas_data_end(mas) + 1; + for (i = 0; i < count; i++) + ((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK; + mt_free_bulk(count, slots); + } + + node = mte_to_node(mas->node); + mt_free_one(node); +} + +/* + * mas_copy_node() - Copy a maple node and replace the parent. + * @mas: The maple state of source tree. + * @new_mas: The maple state of new tree. + * @parent: The parent of the new node. + * + * Copy @mas->node to @new_mas->node, set @parent to be the parent of + * @new_mas->node. If memory allocation fails, @mas is set to -ENOMEM. + */ +static inline void mas_copy_node(struct ma_state *mas, struct ma_state *new_mas, + struct maple_pnode *parent) +{ + struct maple_node *node = mte_to_node(mas->node); + struct maple_node *new_node = mte_to_node(new_mas->node); + unsigned long val; + + /* Copy the node completely. */ + memcpy(new_node, node, sizeof(struct maple_node)); + /* Update the parent node pointer. */ + val = (unsigned long)node->parent & MAPLE_NODE_MASK; + new_node->parent = ma_parent_ptr(val | (unsigned long)parent); +} + +/* + * mas_dup_alloc() - Allocate child nodes for a maple node. + * @mas: The maple state of source tree. + * @new_mas: The maple state of new tree. + * @gfp: The GFP_FLAGS to use for allocations. + * + * This function allocates child nodes for @new_mas->node during the duplication + * process. If memory allocation fails, @mas is set to -ENOMEM. + */ +static inline void mas_dup_alloc(struct ma_state *mas, struct ma_state *new_mas, + gfp_t gfp) +{ + struct maple_node *node = mte_to_node(mas->node); + struct maple_node *new_node = mte_to_node(new_mas->node); + enum maple_type type; + unsigned char request, count, i; + void __rcu **slots; + void __rcu **new_slots; + unsigned long val; + + /* Allocate memory for child nodes. */ + type = mte_node_type(mas->node); + new_slots = ma_slots(new_node, type); + request = mas_data_end(mas) + 1; + count = mt_alloc_bulk(gfp, request, (void **)new_slots); + if (unlikely(count < request)) { + memset(new_slots, 0, request * sizeof(void *)); + mas_set_err(mas, -ENOMEM); + return; + } + + /* Restore node type information in slots. */ + slots = ma_slots(node, type); + for (i = 0; i < count; i++) { + val = (unsigned long)mt_slot_locked(mas->tree, slots, i); + val &= MAPLE_NODE_MASK; + ((unsigned long *)new_slots)[i] |= val; + } +} + +/* + * mas_dup_build() - Build a new maple tree from a source tree + * @mas: The maple state of source tree, need to be in MAS_START state. + * @new_mas: The maple state of new tree, need to be in MAS_START state. + * @gfp: The GFP_FLAGS to use for allocations. + * + * This function builds a new tree in DFS preorder. If the memory allocation + * fails, the error code -ENOMEM will be set in @mas, and @new_mas points to the + * last node. mas_dup_free() will free the incomplete duplication of a tree. + * + * Note that the attributes of the two trees need to be exactly the same, and the + * new tree needs to be empty, otherwise -EINVAL will be set in @mas. + */ +static inline void mas_dup_build(struct ma_state *mas, struct ma_state *new_mas, + gfp_t gfp) +{ + struct maple_node *node; + struct maple_pnode *parent = NULL; + struct maple_enode *root; + enum maple_type type; + + if (unlikely(mt_attr(mas->tree) != mt_attr(new_mas->tree)) || + unlikely(!mtree_empty(new_mas->tree))) { + mas_set_err(mas, -EINVAL); + return; + } + + root = mas_start(mas); + if (mas_is_ptr(mas) || mas_is_none(mas)) + goto set_new_tree; + + node = mt_alloc_one(gfp); + if (!node) { + new_mas->node = MAS_NONE; + mas_set_err(mas, -ENOMEM); + return; + } + + type = mte_node_type(mas->node); + root = mt_mk_node(node, type); + new_mas->node = root; + new_mas->min = 0; + new_mas->max = ULONG_MAX; + root = mte_mk_root(root); + while (1) { + mas_copy_node(mas, new_mas, parent); + if (!mte_is_leaf(mas->node)) { + /* Only allocate child nodes for non-leaf nodes. */ + mas_dup_alloc(mas, new_mas, gfp); + if (unlikely(mas_is_err(mas))) + return; + } else { + /* + * This is the last leaf node and duplication is + * completed. + */ + if (mas->max == ULONG_MAX) + goto done; + + /* This is not the last leaf node and needs to go up. */ + do { + mas_ascend(mas); + mas_ascend(new_mas); + } while (mas->offset == mas_data_end(mas)); + + /* Move to the next subtree. */ + mas->offset++; + new_mas->offset++; + } + + mas_descend(mas); + parent = ma_parent_ptr(mte_to_node(new_mas->node)); + mas_descend(new_mas); + mas->offset = 0; + new_mas->offset = 0; + } +done: + /* Specially handle the parent of the root node. */ + mte_to_node(root)->parent = ma_parent_ptr(mas_tree_parent(new_mas)); +set_new_tree: + /* Make them the same height */ + new_mas->tree->ma_flags = mas->tree->ma_flags; + rcu_assign_pointer(new_mas->tree->ma_root, root); +} + +/** + * __mt_dup(): Duplicate an entire maple tree + * @mt: The source maple tree + * @new: The new maple tree + * @gfp: The GFP_FLAGS to use for allocations + * + * This function duplicates a maple tree in Depth-First Search (DFS) pre-order + * traversal. It uses memcpy() to copy nodes in the source tree and allocate + * new child nodes in non-leaf nodes. The new node is exactly the same as the + * source node except for all the addresses stored in it. It will be faster than + * traversing all elements in the source tree and inserting them one by one into + * the new tree. + * The user needs to ensure that the attributes of the source tree and the new + * tree are the same, and the new tree needs to be an empty tree, otherwise + * -EINVAL will be returned. + * Note that the user needs to manually lock the source tree and the new tree. + * + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If + * the attributes of the two trees are different or the new tree is not an empty + * tree. + */ +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) +{ + int ret = 0; + MA_STATE(mas, mt, 0, 0); + MA_STATE(new_mas, new, 0, 0); + + mas_dup_build(&mas, &new_mas, gfp); + if (unlikely(mas_is_err(&mas))) { + ret = xa_err(mas.node); + if (ret == -ENOMEM) + mas_dup_free(&new_mas); + } + + return ret; +} +EXPORT_SYMBOL(__mt_dup); + +/** + * mtree_dup(): Duplicate an entire maple tree + * @mt: The source maple tree + * @new: The new maple tree + * @gfp: The GFP_FLAGS to use for allocations + * + * This function duplicates a maple tree in Depth-First Search (DFS) pre-order + * traversal. It uses memcpy() to copy nodes in the source tree and allocate + * new child nodes in non-leaf nodes. The new node is exactly the same as the + * source node except for all the addresses stored in it. It will be faster than + * traversing all elements in the source tree and inserting them one by one into + * the new tree. + * The user needs to ensure that the attributes of the source tree and the new + * tree are the same, and the new tree needs to be an empty tree, otherwise + * -EINVAL will be returned. + * + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If + * the attributes of the two trees are different or the new tree is not an empty + * tree. + */ +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) +{ + int ret = 0; + MA_STATE(mas, mt, 0, 0); + MA_STATE(new_mas, new, 0, 0); + + mas_lock(&new_mas); + mas_lock_nested(&mas, SINGLE_DEPTH_NESTING); + mas_dup_build(&mas, &new_mas, gfp); + mas_unlock(&mas); + if (unlikely(mas_is_err(&mas))) { + ret = xa_err(mas.node); + if (ret == -ENOMEM) + mas_dup_free(&new_mas); + } + + mas_unlock(&new_mas); + return ret; +} +EXPORT_SYMBOL(mtree_dup); + /** * __mt_destroy() - Walk and free all nodes of a locked maple tree. * @mt: The maple tree From patchwork Tue Oct 24 08:32:52 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 157289 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:ce89:0:b0:403:3b70:6f57 with SMTP id p9csp1798440vqx; Tue, 24 Oct 2023 01:34:15 -0700 (PDT) X-Google-Smtp-Source: AGHT+IFGrHWKQU1fV/BGXWSw2Glo2ellFaK23YIR9pO7oYHrzZmJRcvkSZZV9sEhwBx4qmGqghDf X-Received: by 2002:a17:903:11cc:b0:1c3:3363:8aea with SMTP id q12-20020a17090311cc00b001c333638aeamr9862283plh.61.1698136455534; Tue, 24 Oct 2023 01:34:15 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1698136455; cv=none; d=google.com; s=arc-20160816; b=T1m09TL/5djsMSBOAkQsXC8DxeZWe5jTIB92yUnSbWykcnCpXXcRQj56E9DJLj4pgE knwMD+6aI647huUDoWqpEo2RWpppe+mHZh04o9QGyIATWaP8X+ZEVHdsAPcVHbMR6VlF XvUMglwGymj1n0jxajsNdRsVA/DVNAiKhV+i7PxPNAVO+yk0f569rGiWpAGkeFBRt+Pg xFpQGvpqf5LibpJhtqUIxJjPrB4oz44cBfC3AecRGVgsXNBiQikwG3ybA5neb3q2/BSN aj4ZOocv7sfpK89zrRcCM21w7PiSMdB4rlHe2B55g5mgtyhlB4c4cQrfI9q3aAyvbwvl DnKg== 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=XXZWHgZHrQ6fRhi1dWH8Hwu+H4KBhNEo2ODkb4cUdHA=; fh=W1ujNbDikRM6mL+MA7cZ93eipzimk+g+Mb7QYnlff5s=; b=iDV74+BCLpd5vKjUpYL1Ga0Z+qHfX2yiVg0Im0eSGAwhUJkyRjpV8IsM4dG2eGkq9m bgUPxV3ywYkFdHZBzybco9CK/VzwZjCI1/urayXJB+bnufZFS4UGQdOkBldJOClVNQFx kOR9Fmj+Jf3vnkhQfDuzJw1Pa6sJnku5XqlF6qjHqvHAM952aMoB23eFpozAeJJxU7tf eJWXWrr1e3ZjAnQdGcOFn8mLx5K1ReE5aOdeJQrc1zph8QvTHnLS6IOdmhfgI9vImGio GJs7EqZw3w/IAZcZcy+s8Pux/Lsqjs2Q8HroZvoQiYEqAoRP19bt/ODYRNry0qcWxIHz O09A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b="ad9/LY11"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.31 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 morse.vger.email (morse.vger.email. [23.128.96.31]) by mx.google.com with ESMTPS id m15-20020a170902db0f00b001b8a4954be1si8306400plx.595.2023.10.24.01.34.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Oct 2023 01:34:15 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.31 as permitted sender) client-ip=23.128.96.31; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b="ad9/LY11"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.31 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 (depot.vger.email [IPv6:2620:137:e000::3:0]) by morse.vger.email (Postfix) with ESMTP id 77196803B3A6; Tue, 24 Oct 2023 01:34:12 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at morse.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232620AbjJXIdn (ORCPT + 26 others); Tue, 24 Oct 2023 04:33:43 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38438 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233950AbjJXIdj (ORCPT ); Tue, 24 Oct 2023 04:33:39 -0400 Received: from mail-pf1-x42c.google.com (mail-pf1-x42c.google.com [IPv6:2607:f8b0:4864:20::42c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7310510C9 for ; Tue, 24 Oct 2023 01:33:37 -0700 (PDT) Received: by mail-pf1-x42c.google.com with SMTP id d2e1a72fcca58-6b6f4c118b7so3441708b3a.0 for ; Tue, 24 Oct 2023 01:33:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136417; x=1698741217; darn=vger.kernel.org; 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=XXZWHgZHrQ6fRhi1dWH8Hwu+H4KBhNEo2ODkb4cUdHA=; b=ad9/LY11n2zGMzPzBh4fY7fh5YoLYIO5lCS4THCEnf8iUXJ1ZkmiVmkcUJb1y10BzE e+rVe/nmlQlI9e2ayDW0UK87kqxTxHttxQtNLOeiOZbb9KnkdD1x2uJBmWayO9W/PRsH G5EqV1WubywAOgxPDuo6rpmT4UFqWQG655cFP+PUjHwk8yVGJvYuejXvehc6CYnJtzoP DUpvCc7VZWchpLThQCmQCvpBkPOQjpNePY5uuDdUu0Mn9p1d0ovgO5DPc9vWLyuBH0zW 5GMVjg87SGZ9EP+Yt2U6CD3lpkGPnMCNPyd7pl715oa+bCKYQFCN7nQcUDXTcJ1XjPgG 79pA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136417; x=1698741217; 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=XXZWHgZHrQ6fRhi1dWH8Hwu+H4KBhNEo2ODkb4cUdHA=; b=vqbfSJf6E4btPUZN6/nOjuFBm8zcgWRSJ6H2IMJBUNLAOhS+ChkWv/VoY+IlPrZCCb cPxzd4RdyC6w3me0FAO8hvlBeHiOmzR2y6u6AtBqeHCAVnyzyLHzUiD//p+y1nHrogob YuCcF7KgntLXbz2eanvUESHUP/hZASCbTh8CCbAHurSHz3uCqXiC4cJ8qSJamN66s0tt wh7XqXH9XxiK7ILaceQSNlVslTuMo9kEMrdDh1hX8/ZcutRTGwaiMsm9Au25RlBRSWSF 0U8lB2nxSv3zg0lrjYKhwHDX1D2aZ1+V3CC5j4aw/qKotrtkMUlMjFeyZXLb4wJsPzpK kUYw== X-Gm-Message-State: AOJu0YyYTMNhkQuu/byFMf1u+r86zd+LnSqS7bBmHqjr5eMX25DJxsw7 ilbzLWqnL2+zTbRVhp7p3KAfFQ== X-Received: by 2002:a05:6a20:9381:b0:130:d5a:e40e with SMTP id x1-20020a056a20938100b001300d5ae40emr2254231pzh.7.1698136416831; Tue, 24 Oct 2023 01:33:36 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.30 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:36 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v6 04/10] radix tree test suite: Align kmem_cache_alloc_bulk() with kernel behavior. Date: Tue, 24 Oct 2023 16:32:52 +0800 Message-Id: <20231024083258.65750-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on morse.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (morse.vger.email [0.0.0.0]); Tue, 24 Oct 2023 01:34:12 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1780625131721839049 X-GMAIL-MSGID: 1780625131721839049 When kmem_cache_alloc_bulk() fails to allocate, leave the freed pointers in the array. This enables a more accurate simulation of the kernel's behavior and allows for testing potential double-free scenarios. Signed-off-by: Peng Zhang --- tools/testing/radix-tree/linux.c | 45 +++++++++++++++++++++++--------- 1 file changed, 33 insertions(+), 12 deletions(-) diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c index 61fe2601cb3a..4eb442206d01 100644 --- a/tools/testing/radix-tree/linux.c +++ b/tools/testing/radix-tree/linux.c @@ -93,13 +93,9 @@ void *kmem_cache_alloc_lru(struct kmem_cache *cachep, struct list_lru *lru, return p; } -void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) +void __kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) { assert(objp); - uatomic_dec(&nr_allocated); - uatomic_dec(&cachep->nr_allocated); - if (kmalloc_verbose) - printf("Freeing %p to slab\n", objp); if (cachep->nr_objs > 10 || cachep->align) { memset(objp, POISON_FREE, cachep->size); free(objp); @@ -111,6 +107,15 @@ void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) } } +void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) +{ + uatomic_dec(&nr_allocated); + uatomic_dec(&cachep->nr_allocated); + if (kmalloc_verbose) + printf("Freeing %p to slab\n", objp); + __kmem_cache_free_locked(cachep, objp); +} + void kmem_cache_free(struct kmem_cache *cachep, void *objp) { pthread_mutex_lock(&cachep->lock); @@ -141,18 +146,17 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size, if (kmalloc_verbose) pr_debug("Bulk alloc %lu\n", size); - if (!(gfp & __GFP_DIRECT_RECLAIM)) { - if (cachep->non_kernel < size) - return 0; - - cachep->non_kernel -= size; - } - pthread_mutex_lock(&cachep->lock); if (cachep->nr_objs >= size) { struct radix_tree_node *node; for (i = 0; i < size; i++) { + if (!(gfp & __GFP_DIRECT_RECLAIM)) { + if (!cachep->non_kernel) + break; + cachep->non_kernel--; + } + node = cachep->objs; cachep->nr_objs--; cachep->objs = node->parent; @@ -163,11 +167,19 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size, } else { pthread_mutex_unlock(&cachep->lock); for (i = 0; i < size; i++) { + if (!(gfp & __GFP_DIRECT_RECLAIM)) { + if (!cachep->non_kernel) + break; + cachep->non_kernel--; + } + if (cachep->align) { posix_memalign(&p[i], cachep->align, cachep->size); } else { p[i] = malloc(cachep->size); + if (!p[i]) + break; } if (cachep->ctor) cachep->ctor(p[i]); @@ -176,6 +188,15 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size, } } + if (i < size) { + size = i; + pthread_mutex_lock(&cachep->lock); + for (i = 0; i < size; i++) + __kmem_cache_free_locked(cachep, p[i]); + pthread_mutex_unlock(&cachep->lock); + return 0; + } + for (i = 0; i < size; i++) { uatomic_inc(&nr_allocated); uatomic_inc(&cachep->nr_allocated); From patchwork Tue Oct 24 08:32:53 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 157295 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:ce89:0:b0:403:3b70:6f57 with SMTP id p9csp1798750vqx; Tue, 24 Oct 2023 01:35:02 -0700 (PDT) X-Google-Smtp-Source: AGHT+IG2iq4giuvNwykP8dNX3F6bmm5FKgUZJjDk3pF4tUgLW9mqtAPnk/pKT38fY8mwItlETmBD X-Received: by 2002:a05:6a21:78a6:b0:17d:d272:7954 with SMTP id bf38-20020a056a2178a600b0017dd2727954mr2630353pzc.9.1698136502204; Tue, 24 Oct 2023 01:35:02 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1698136502; cv=none; d=google.com; s=arc-20160816; b=Yb8iLyWSAgfaUoVUVMyxmnUM90gCqaoRZTew07ee75j4MTpbdKemp+8KOrvnG+L6BG 7rBYqonMkn8hWzmtSMO5IrpScmVxL8WqBKRHJk7i5pjssA1dyv78faYMxxuMtK/3NLTr UkY9qqQpn6fmpPL4ZNjVMQN/X0FL6MMo2W8vTM8xyJYnnEAzIW9+83H2cgCTop+ppOUv mEEmqO5ou7EejlmKhfk1HNnB6t7hePoqWUn49ZdI/BIHC1ivghkkjXryqDeETShaSRxc 3AV6XM16ZJZPmq1pdFT9EljckdpkzBcUYcEMA7CzypNdeYjIUGq2iZToMdh3Am3MDLlN LlYg== 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=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; fh=W1ujNbDikRM6mL+MA7cZ93eipzimk+g+Mb7QYnlff5s=; b=OmsLe93eIVTgyi8q63lPbdlDl4b8DGwEs5RGkYfuNS2z0YS8DtXOrx49dVOzpdRDHl NhpEdGdYhyER70t0jZDCsYiLN6rgQQ9P0qAtkPi1lJSI2O/bTFilrEYuYwKRLbwrZTTl Pa6umN46BkGvjjIaUbuGk5tygiGDO+8j3XuHeWMQZCxprbslIb8T8Vid4atjHvcfNYaS MtSI+OCoS6+dOxpmtmjPVmAQiLI+CeuI2PKde+9LyEADqEwvA2joyWbN4JyK5w7vfiD8 r0LLX3XG0mRzzGR/M7xBXg3YBvSNIFDTccSQK0G9+vmn78GmlvCl116ec+AFim6KgD9z CkNQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=BpaBI1sO; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:2 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 agentk.vger.email (agentk.vger.email. [2620:137:e000::3:2]) by mx.google.com with ESMTPS id k198-20020a633dcf000000b00578b4082453si7582530pga.712.2023.10.24.01.35.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Oct 2023 01:35:02 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:2 as permitted sender) client-ip=2620:137:e000::3:2; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=BpaBI1sO; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:2 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 (depot.vger.email [IPv6:2620:137:e000::3:0]) by agentk.vger.email (Postfix) with ESMTP id 56C0080B133A; Tue, 24 Oct 2023 01:34:59 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at agentk.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233954AbjJXIe3 (ORCPT + 26 others); Tue, 24 Oct 2023 04:34:29 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:44486 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234054AbjJXIeP (ORCPT ); Tue, 24 Oct 2023 04:34:15 -0400 Received: from mail-pf1-x42f.google.com (mail-pf1-x42f.google.com [IPv6:2607:f8b0:4864:20::42f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 16A5F10D3 for ; Tue, 24 Oct 2023 01:33:44 -0700 (PDT) Received: by mail-pf1-x42f.google.com with SMTP id d2e1a72fcca58-6b77ab73c6fso3055083b3a.1 for ; Tue, 24 Oct 2023 01:33:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136423; x=1698741223; darn=vger.kernel.org; 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=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=BpaBI1sOF3Vg2KWjcsoFc4eim7j4goubh7vr5fO7yf2OFD6D9u1NMFfP02JsctFh3f RjrZj7xmjaiO8WKTinKenvS1pnIthT7wHbInAcO7wdsbdIhKDKeUIuW6Xnw7chgSF5c3 XUut4DcoOKbHzPiTQ7ipTErqYzgTUULhl7DKqTNX3TM5umNYe8+F2J0Kz5ecZDYi2/Fb VJHfFf5fDFJv6327DGsR7BcKcTU6gvuJepgnJBqv6u6pGAdWDFmAhIcEyt3V61K4hrxZ 6JtRRJW/9f9AoyfBktlOtv5y48UHGSVpAlB9XJ2pk4PkG2toX8WTfRP8De1y7EGYoXCE 2/hg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136423; x=1698741223; 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=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=TTOqf5L+9+bfRkOwXiSMMksIzKdzWwFf+ISo5rZ9RwVLv0+JDsSQ8Qfxk34g60UDvG aWufTiyGWQ8VuLhgPtSRgCUkH1cKJpu6JAV29gxWKk1TplCa/zKdC/ljaQr92WWJw8kX HtB9p7EGu7U+POyU/c5QbJ0Y32PSBCYzYg+4UGbazmPcN6yVShBvoIPOQ2XuV+ZEUUvK cD7kPvNRXN/2kGYnXnH6x+Sp7YSzO9vQCva73efOcuOb+03rtlnU998rn5rxt0PesdS2 18v5ySL5VKCa9aY3WFgmrF2n5vKnHlNReO9rE+52DZsB1pzZ0wXgRpq4mC6I3amgkH4p FsRg== X-Gm-Message-State: AOJu0YzNIekEhhLCHnzZG1N+o7ENbL+ttrkIWl9hoPjUADU9CszBJK6K SIuVARAgCVnz+TxbFxA0+n17ig== X-Received: by 2002:a05:6a00:10c5:b0:68f:b5a3:5ec6 with SMTP id d5-20020a056a0010c500b0068fb5a35ec6mr14426161pfu.0.1698136423347; Tue, 24 Oct 2023 01:33:43 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.37 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:43 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v6 05/10] maple_tree: Add test for mtree_dup() Date: Tue, 24 Oct 2023 16:32:53 +0800 Message-Id: <20231024083258.65750-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on agentk.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (agentk.vger.email [0.0.0.0]); Tue, 24 Oct 2023 01:34:59 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1780625180720435577 X-GMAIL-MSGID: 1780625180720435577 Add test for mtree_dup(). Test by duplicating different maple trees and then comparing the two trees. Includes tests for duplicating full trees and memory allocation failures on different nodes. Signed-off-by: Peng Zhang --- tools/testing/radix-tree/maple.c | 361 +++++++++++++++++++++++++++++++ 1 file changed, 361 insertions(+) diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index e5da1cad70ba..12b3390e9591 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35857,6 +35857,363 @@ static noinline void __init check_locky(struct maple_tree *mt) mt_clear_in_rcu(mt); } +/* + * Compares two nodes except for the addresses stored in the nodes. + * Returns zero if they are the same, otherwise returns non-zero. + */ +static int __init compare_node(struct maple_enode *enode_a, + struct maple_enode *enode_b) +{ + struct maple_node *node_a, *node_b; + struct maple_node a, b; + void **slots_a, **slots_b; /* Do not use the rcu tag. */ + enum maple_type type; + int i; + + if (((unsigned long)enode_a & MAPLE_NODE_MASK) != + ((unsigned long)enode_b & MAPLE_NODE_MASK)) { + pr_err("The lower 8 bits of enode are different.\n"); + return -1; + } + + type = mte_node_type(enode_a); + node_a = mte_to_node(enode_a); + node_b = mte_to_node(enode_b); + a = *node_a; + b = *node_b; + + /* Do not compare addresses. */ + if (ma_is_root(node_a) || ma_is_root(node_b)) { + a.parent = (struct maple_pnode *)((unsigned long)a.parent & + MA_ROOT_PARENT); + b.parent = (struct maple_pnode *)((unsigned long)b.parent & + MA_ROOT_PARENT); + } else { + a.parent = (struct maple_pnode *)((unsigned long)a.parent & + MAPLE_NODE_MASK); + b.parent = (struct maple_pnode *)((unsigned long)b.parent & + MAPLE_NODE_MASK); + } + + if (a.parent != b.parent) { + pr_err("The lower 8 bits of parents are different. %p %p\n", + a.parent, b.parent); + return -1; + } + + /* + * If it is a leaf node, the slots do not contain the node address, and + * no special processing of slots is required. + */ + if (ma_is_leaf(type)) + goto cmp; + + slots_a = ma_slots(&a, type); + slots_b = ma_slots(&b, type); + + for (i = 0; i < mt_slots[type]; i++) { + if (!slots_a[i] && !slots_b[i]) + break; + + if (!slots_a[i] || !slots_b[i]) { + pr_err("The number of slots is different.\n"); + return -1; + } + + /* Do not compare addresses in slots. */ + ((unsigned long *)slots_a)[i] &= MAPLE_NODE_MASK; + ((unsigned long *)slots_b)[i] &= MAPLE_NODE_MASK; + } + +cmp: + /* + * Compare all contents of two nodes, including parent (except address), + * slots (except address), pivots, gaps and metadata. + */ + return memcmp(&a, &b, sizeof(struct maple_node)); +} + +/* + * Compare two trees and return 0 if they are the same, non-zero otherwise. + */ +static int __init compare_tree(struct maple_tree *mt_a, struct maple_tree *mt_b) +{ + MA_STATE(mas_a, mt_a, 0, 0); + MA_STATE(mas_b, mt_b, 0, 0); + + if (mt_a->ma_flags != mt_b->ma_flags) { + pr_err("The flags of the two trees are different.\n"); + return -1; + } + + mas_dfs_preorder(&mas_a); + mas_dfs_preorder(&mas_b); + + if (mas_is_ptr(&mas_a) || mas_is_ptr(&mas_b)) { + if (!(mas_is_ptr(&mas_a) && mas_is_ptr(&mas_b))) { + pr_err("One is MAS_ROOT and the other is not.\n"); + return -1; + } + return 0; + } + + while (!mas_is_none(&mas_a) || !mas_is_none(&mas_b)) { + + if (mas_is_none(&mas_a) || mas_is_none(&mas_b)) { + pr_err("One is MAS_NONE and the other is not.\n"); + return -1; + } + + if (mas_a.min != mas_b.min || + mas_a.max != mas_b.max) { + pr_err("mas->min, mas->max do not match.\n"); + return -1; + } + + if (compare_node(mas_a.node, mas_b.node)) { + pr_err("The contents of nodes %p and %p are different.\n", + mas_a.node, mas_b.node); + mt_dump(mt_a, mt_dump_dec); + mt_dump(mt_b, mt_dump_dec); + return -1; + } + + mas_dfs_preorder(&mas_a); + mas_dfs_preorder(&mas_b); + } + + return 0; +} + +static __init void mas_subtree_max_range(struct ma_state *mas) +{ + unsigned long limit = mas->max; + MA_STATE(newmas, mas->tree, 0, 0); + void *entry; + + mas_for_each(mas, entry, limit) { + if (mas->last - mas->index >= + newmas.last - newmas.index) { + newmas = *mas; + } + } + + *mas = newmas; +} + +/* + * build_full_tree() - Build a full tree. + * @mt: The tree to build. + * @flags: Use @flags to build the tree. + * @height: The height of the tree to build. + * + * Build a tree with full leaf nodes and internal nodes. Note that the height + * should not exceed 3, otherwise it will take a long time to build. + * Return: zero if the build is successful, non-zero if it fails. + */ +static __init int build_full_tree(struct maple_tree *mt, unsigned int flags, + int height) +{ + MA_STATE(mas, mt, 0, 0); + unsigned long step; + int ret = 0, cnt = 1; + enum maple_type type; + + mt_init_flags(mt, flags); + mtree_insert_range(mt, 0, ULONG_MAX, xa_mk_value(5), GFP_KERNEL); + + mtree_lock(mt); + + while (1) { + mas_set(&mas, 0); + if (mt_height(mt) < height) { + mas.max = ULONG_MAX; + goto store; + } + + while (1) { + mas_dfs_preorder(&mas); + if (mas_is_none(&mas)) + goto unlock; + + type = mte_node_type(mas.node); + if (mas_data_end(&mas) + 1 < mt_slots[type]) { + mas_set(&mas, mas.min); + goto store; + } + } +store: + mas_subtree_max_range(&mas); + step = mas.last - mas.index; + if (step < 1) { + ret = -1; + goto unlock; + } + + step /= 2; + mas.last = mas.index + step; + mas_store_gfp(&mas, xa_mk_value(5), + GFP_KERNEL); + ++cnt; + } +unlock: + mtree_unlock(mt); + + MT_BUG_ON(mt, mt_height(mt) != height); + /* pr_info("height:%u number of elements:%d\n", mt_height(mt), cnt); */ + return ret; +} + +static noinline void __init check_mtree_dup(struct maple_tree *mt) +{ + DEFINE_MTREE(new); + int i, j, ret, count = 0; + unsigned int rand_seed = 17, rand; + + /* store a value at [0, 0] */ + mt_init_flags(mt, 0); + mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL); + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + + /* The two trees have different attributes. */ + mt_init_flags(mt, 0); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret != -EINVAL); + mtree_destroy(mt); + mtree_destroy(&new); + + /* The new tree is not empty */ + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + mtree_store(&new, 5, xa_mk_value(5), GFP_KERNEL); + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret != -EINVAL); + mtree_destroy(mt); + mtree_destroy(&new); + + /* Test for duplicating full trees. */ + for (i = 1; i <= 3; i++) { + ret = build_full_tree(mt, 0, i); + MT_BUG_ON(mt, ret); + mt_init_flags(&new, 0); + + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + for (i = 1; i <= 3; i++) { + ret = build_full_tree(mt, MT_FLAGS_ALLOC_RANGE, i); + MT_BUG_ON(mt, ret); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + /* Test for normal duplicating. */ + for (i = 0; i < 1000; i += 3) { + if (i & 1) { + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + } else { + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + } + + for (j = 0; j < i; j++) { + mtree_store_range(mt, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + /* Test memory allocation failed. */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (i = 0; i < 30; i += 3) { + mtree_store_range(mt, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + + /* Failed at the first node. */ + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + mt_set_non_kernel(0); + ret = mtree_dup(mt, &new, GFP_NOWAIT); + mt_set_non_kernel(0); + MT_BUG_ON(&new, ret != -ENOMEM); + mtree_destroy(mt); + mtree_destroy(&new); + + /* Random maple tree fails at a random node. */ + for (i = 0; i < 1000; i += 3) { + if (i & 1) { + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + } else { + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + } + + for (j = 0; j < i; j++) { + mtree_store_range(mt, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + /* + * The rand() library function is not used, so we can generate + * the same random numbers on any platform. + */ + rand_seed = rand_seed * 1103515245 + 12345; + rand = rand_seed / 65536 % 128; + mt_set_non_kernel(rand); + + ret = mtree_dup(mt, &new, GFP_NOWAIT); + mt_set_non_kernel(0); + if (ret != 0) { + MT_BUG_ON(&new, ret != -ENOMEM); + count++; + mtree_destroy(mt); + continue; + } + + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + /* pr_info("mtree_dup() fail %d times\n", count); */ + BUG_ON(!count); +} + extern void test_kmem_cache_bulk(void); void farmer_tests(void) @@ -35904,6 +36261,10 @@ void farmer_tests(void) check_null_expand(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, 0); + check_mtree_dup(&tree); + mtree_destroy(&tree); + /* RCU testing */ mt_init_flags(&tree, 0); check_erase_testset(&tree); From patchwork Tue Oct 24 08:32:54 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 157294 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:ce89:0:b0:403:3b70:6f57 with SMTP id p9csp1798751vqx; Tue, 24 Oct 2023 01:35:02 -0700 (PDT) X-Google-Smtp-Source: AGHT+IGFwqgRtcqHYjF0D+hAqGok10yYJbLgeAhUm65MZqNLdAR4mj40acLK2VAYVc4stWN1Ixjj X-Received: by 2002:a17:90b:8ca:b0:27c:f282:adac with SMTP id ds10-20020a17090b08ca00b0027cf282adacmr21079864pjb.0.1698136502211; Tue, 24 Oct 2023 01:35:02 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1698136502; cv=none; d=google.com; s=arc-20160816; b=xLgTpecRrIvrGLJ3motbeoGkTg6d67MyBmrXkYfrosBCDB/Nf3gnDwuGcpi+Gl9kV5 DTXKbfwAJbWxIZxgwjUJjJAFxvUINUCdtSGq/Q2t/CdSp2nGGrBKjjTNh1eGxIj3NR1W FhH2elqMAZk196Ai6g3UeE6UzzONLiJGh1PuVrQ6Ho+bcJohmjifLbxb4OpoebU7+ECa b8NiTnTTlNb9ASyuZ+vuig96nnYivNvlx1aj2ACVA66Dyo9GcCVgvoBfCoxQ3Ei+DWeF pjfXbywSEF+8DsDBuOuJLhX0MI2783aGMJpGNwNwPIGJye0EyL3emhkWGE+BIjnQksnZ Kgtw== 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=mFyp/FJQdSo4OvDS2koRMpNI0AcMCWskpm09jBYSG+0=; fh=W1ujNbDikRM6mL+MA7cZ93eipzimk+g+Mb7QYnlff5s=; b=mYaM5Q9iwxBDJ58k9tpUM6s6oWrp9tpyMgxKRIOJpKjFnKPf8rJFiGXYGqP5v4JYaA B6x/kEBN9V7juUuKtKo8HqoFUYoeoxBv4jnf13xXgs9ah0T/Ymybl+U4b6olkfKbeC9m HO+y3ayENnKIKerHtTJFiGugRIbXAB47E4SxCt/cbMHW5LmxvhRmWmnfHAZnBvc1y6Sj B6iWZoNJWHhGwwJbXphr6tcH5jrxjM+ohSE2Cd9x5EF3D/MTpWWRrUZwjJpSg7+KZAyQ 8srQomJiYzDQV3ZwwID9IROMzLB+9dTsS5nIwh4ThDFe4qqJQSptIBwnKKNntuw5+KJ7 1MGg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=DFkldGMd; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:3 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 lipwig.vger.email (lipwig.vger.email. [2620:137:e000::3:3]) by mx.google.com with ESMTPS id gz18-20020a17090b0ed200b0027e480d1f4asi3350523pjb.69.2023.10.24.01.35.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Oct 2023 01:35:02 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:3 as permitted sender) client-ip=2620:137:e000::3:3; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=DFkldGMd; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:3 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 (depot.vger.email [IPv6:2620:137:e000::3:0]) by lipwig.vger.email (Postfix) with ESMTP id 9E1AD802F57D; Tue, 24 Oct 2023 01:34:59 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at lipwig.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233903AbjJXIed (ORCPT + 26 others); Tue, 24 Oct 2023 04:34:33 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40354 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233991AbjJXIeR (ORCPT ); Tue, 24 Oct 2023 04:34:17 -0400 Received: from mail-pf1-x432.google.com (mail-pf1-x432.google.com [IPv6:2607:f8b0:4864:20::432]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 59B711713 for ; Tue, 24 Oct 2023 01:33:50 -0700 (PDT) Received: by mail-pf1-x432.google.com with SMTP id d2e1a72fcca58-6bd73395bceso3079606b3a.0 for ; Tue, 24 Oct 2023 01:33:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136430; x=1698741230; darn=vger.kernel.org; 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=mFyp/FJQdSo4OvDS2koRMpNI0AcMCWskpm09jBYSG+0=; b=DFkldGMdV2JxmJtnJ2BwYAUGwWXjuXpH7vMPy9/txF2bmv7IAxzKNlda7tFnfBzhrE Z7pWAxLLI6z0aHZ9pJ3N4u2AiEcqqd0J3CzRIyyASI7VkE997XKLXtrWN/KMGzl6av5r K61YgrGTJA97Gs5yThZ1YggtD87zhHjGzq3XRBF6NsJJmB5vU7VO8WVUOgCFtdEmY59z gKN0xeDUcGgkUDHBiU3yxZ6jGIF25XZdFLc9dSDO4DrexPZo7pV+xNoy957cUer4tTwN HjNj3vtdAQ99teS4CFZ1Sv3c107vn+9NFYi0Iykdk3lkVbogEJdgilgF7oAvh6u0h1fC xP2Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136430; x=1698741230; 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=mFyp/FJQdSo4OvDS2koRMpNI0AcMCWskpm09jBYSG+0=; b=Wv7rHIXXCiqwvyLEWhzSakM3XB/m59b/ro9UZ+NXxqE+NgwSn6SJoQ62/onxXpVR3l 9+WuUIThEBqtr1UucogZZ0TT75wX06o0pGHITQQ77HlWo27spIa3UczqbjOKH2XdCwyt ZMdS9+6VWkjJCfUPIiu2F/9E8hMtoJC6c/EE/GCjT1vEkbLF2dKt1YAwyL9Jgw5dIRwy tmlbKv8fREYGjMw00RWvGBBr4p+36fj4zM/jjz3UOjpg3ETYGUsu42HWGvWKMForRNhU WeM4XrKLgD8sm9b0Nbpvat0UtCyAUEHCf3+j8Uq5uEOT27cC1RgF9MmnIhqvuUSZ0ejm 1KlA== X-Gm-Message-State: AOJu0YzuPu6TyYBiUs2NqspoldqqWuoUPw4Kds1BxJtJO5hvT3pfKiEq VF+exTi1wb578gEWfcxkqBauEA== X-Received: by 2002:aa7:8885:0:b0:68e:2c2a:5172 with SMTP id z5-20020aa78885000000b0068e2c2a5172mr16021661pfe.6.1698136429778; Tue, 24 Oct 2023 01:33:49 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.43 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:49 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v6 06/10] maple_tree: Update the documentation of maple tree Date: Tue, 24 Oct 2023 16:32:54 +0800 Message-Id: <20231024083258.65750-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lipwig.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (lipwig.vger.email [0.0.0.0]); Tue, 24 Oct 2023 01:34:59 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1780625180502765654 X-GMAIL-MSGID: 1780625180502765654 Introduce the new interface mtree_dup() in the documentation. Signed-off-by: Peng Zhang --- Documentation/core-api/maple_tree.rst | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst index 45defcf15da7..285e2d2b21ae 100644 --- a/Documentation/core-api/maple_tree.rst +++ b/Documentation/core-api/maple_tree.rst @@ -81,6 +81,9 @@ section. Sometimes it is necessary to ensure the next call to store to a maple tree does not allocate memory, please see :ref:`maple-tree-advanced-api` for this use case. +You can use mtree_dup() to duplicate an entire maple tree. It is a more +efficient way than inserting all elements one by one into a new tree. + Finally, you can remove all entries from a maple tree by calling mtree_destroy(). If the maple tree entries are pointers, you may wish to free the entries first. @@ -112,6 +115,7 @@ Takes ma_lock internally: * mtree_insert() * mtree_insert_range() * mtree_erase() + * mtree_dup() * mtree_destroy() * mt_set_in_rcu() * mt_clear_in_rcu() From patchwork Tue Oct 24 08:32:55 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 157292 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:ce89:0:b0:403:3b70:6f57 with SMTP id p9csp1798617vqx; Tue, 24 Oct 2023 01:34:42 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHKbx5MOsqN8aL+0AUguxSW2pIlxhpbIoNztMPKfmO4+xDtJhCThCmVSnUOFC6WbwWUisvK X-Received: by 2002:a05:6a21:7983:b0:15d:9ee7:1811 with SMTP id bh3-20020a056a21798300b0015d9ee71811mr1522652pzc.36.1698136482327; Tue, 24 Oct 2023 01:34:42 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1698136482; cv=none; d=google.com; s=arc-20160816; b=ZVcy4I2uausNT/39WGikJQfImadWMgRhB/FOOYACNTiMUCkKCTju/GZI0MQpcPdtod /QE862QmdYFtKIwuKYnrtl/gRWXAbz84yyUU3a5EhOgB4NR1jEemsPCp3vqoM1qrV4Em T6kwwlNUE43MltcxUmq5XwzOldHiluKZcAqCspVelpXM8XFZSdzRWuHGgbwoLE5TMoit qc3IdNKoYHyY+fIM3YVgS7YEecr3gGKZEpdxb+wEnGNVcJPVK2hVSwyMo6dpwNWB89F6 /SPybQuUvxIwMMFKHu38fZ0plO9iVMRUdEpBGUPjGsoMhTwv9QirSdSoMeMWlSOelKeR tTSQ== 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=QmT9t2gNl7JC/Wj/BeBLe/fYUtz3EaMSD0bTELVUlD4=; fh=W1ujNbDikRM6mL+MA7cZ93eipzimk+g+Mb7QYnlff5s=; b=oQQUe79DeZXzq4tm758wv0LOulRUA5pvkqiAT+I0N0fJi6UAD8VF/VU+yR4i7Pkhyr 5wFr97wFglliO586WJG2Feb9UmA5GuHOK5UbJ0aKmQMsrOAdnzVU5Oz2c8W10IYPkfA8 1q1K1cf3YFJZFG0ntdHuLG+2IDqx0+Rvu9mX4QoomG49rPh5lM5m2wMpeK/oytQkMv3Y 0DXxLAeP2ECaxkx9EneVJhl0jGWNR+yTzcO33zhJ8sGWFQ/UOMRT3levJ44tM0NcTNXn g8wYIg62y96OZjYyeXJD4rtcUKuHUWvCv9Lbljii6FuobjhThGzaGWM9WN21fW+yTxUw S+5A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=GqvjHc99; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 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 howler.vger.email (howler.vger.email. [2620:137:e000::3:4]) by mx.google.com with ESMTPS id ij22-20020a170902ab5600b001c9d03042b6si7591114plb.7.2023.10.24.01.34.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Oct 2023 01:34:42 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 as permitted sender) client-ip=2620:137:e000::3:4; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=GqvjHc99; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 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 (depot.vger.email [IPv6:2620:137:e000::3:0]) by howler.vger.email (Postfix) with ESMTP id 4C6D080ACFF7; Tue, 24 Oct 2023 01:34:34 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at howler.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234037AbjJXIeL (ORCPT + 26 others); Tue, 24 Oct 2023 04:34:11 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40546 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234127AbjJXIeB (ORCPT ); Tue, 24 Oct 2023 04:34:01 -0400 Received: from mail-pg1-x529.google.com (mail-pg1-x529.google.com [IPv6:2607:f8b0:4864:20::529]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9BDCBD7E for ; Tue, 24 Oct 2023 01:33:57 -0700 (PDT) Received: by mail-pg1-x529.google.com with SMTP id 41be03b00d2f7-5a1d89ff4b9so2314198a12.0 for ; Tue, 24 Oct 2023 01:33:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136436; x=1698741236; darn=vger.kernel.org; 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=QmT9t2gNl7JC/Wj/BeBLe/fYUtz3EaMSD0bTELVUlD4=; b=GqvjHc99IbEBZlveybU0D8fTBBlqe+5Ky0UCXDZB8PFwd279bHDMYd6DNStGBbmDYj ZrF/X5gQG3+6FzoP+wo6/xV+JHpxmEVyFE/bEp5FlnONxxEArr8+kVhdgW6brSJdenIc rW3fn0k6u9xzNZJQuCfokK9CMcg+LzehC2U6+Rnq6+97/iB8CKp+vYDsQDzvwpJOLMOK x9axsO7Bj0h7Qd5rjO9oW3CQVyvmNFRhqhcONU818lCuH7DkZswcSOL+lib8Zy33LKI3 dMjmrg6dEawPdgMnDNO0ezM0C20fT2vrXjVCQ/ElhZpQc0LbBrg6MmtMQutR1LgExcSM 4dSA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136436; x=1698741236; 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=QmT9t2gNl7JC/Wj/BeBLe/fYUtz3EaMSD0bTELVUlD4=; b=GFMzOYwWd+Dj+n67yd76VMaI6bt2Z62fFC+fGHXaQRDgWIcljFPt6C7NF+inZCahu7 jWo6h45Zy2es7tF0KYTIevN4lGRV8vfqPFMuApN0tTzDlNbJ+G9CLdpFG6LXN4U/DpaM +46V03llrZ/isVwAUSCr8465weTj5gInSNL+Hs6kfN1xtg2KPbgSEKwI85ED5yM30pW9 PSnn0Llvyq89NNoOxbTOOVfEbFHdQhPpBYpJ72R9AxztFMECEr2Rba7vakEZKjRuDfkj I5k/OwBlQaitPFcBsnhZjzveECPXAzk2o+58tn41UHjyAhQAhtiUCTJ2jtXqVOqsU9Mi bVUw== X-Gm-Message-State: AOJu0YzJ98Cyp+cKlfc+JlhArbF0JIK0S3NN2/fBvsv+wHGjIWab8F+M 3IpDT1H5V5TyYFoK5yLQIG01QA== X-Received: by 2002:a05:6a20:6a28:b0:161:28e0:9abd with SMTP id p40-20020a056a206a2800b0016128e09abdmr2218020pzk.16.1698136436387; Tue, 24 Oct 2023 01:33:56 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.50 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:56 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v6 07/10] maple_tree: Skip other tests when BENCH is enabled Date: Tue, 24 Oct 2023 16:32:55 +0800 Message-Id: <20231024083258.65750-8-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on howler.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (howler.vger.email [0.0.0.0]); Tue, 24 Oct 2023 01:34:34 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1780625160514907786 X-GMAIL-MSGID: 1780625160514907786 Skip other tests when BENCH is enabled so that performance can be measured in user space. Signed-off-by: Peng Zhang --- lib/test_maple_tree.c | 8 ++++---- tools/testing/radix-tree/maple.c | 2 ++ 2 files changed, 6 insertions(+), 4 deletions(-) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 464eeb90d5ad..de470950714f 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -3585,10 +3585,6 @@ static int __init maple_tree_seed(void) pr_info("\nTEST STARTING\n\n"); - mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); - check_root_expand(&tree); - mtree_destroy(&tree); - #if defined(BENCH_SLOT_STORE) #define BENCH mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); @@ -3646,6 +3642,10 @@ static int __init maple_tree_seed(void) goto skip; #endif + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_root_expand(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_iteration(&tree); mtree_destroy(&tree); diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 12b3390e9591..cb5358674521 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36299,7 +36299,9 @@ void farmer_tests(void) void maple_tree_tests(void) { +#if !defined(BENCH) farmer_tests(); +#endif maple_tree_seed(); maple_tree_harvest(); } From patchwork Tue Oct 24 08:32:56 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 157296 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:ce89:0:b0:403:3b70:6f57 with SMTP id p9csp1799039vqx; Tue, 24 Oct 2023 01:35:45 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHkXdC17iqvHFlrjprvlBP1TmDRZV9bm7oZuZ/8yZjP+OpefOvcWWsZO2KO+1dsbPOtwOoq X-Received: by 2002:a9d:6858:0:b0:6b9:c51c:f4d5 with SMTP id c24-20020a9d6858000000b006b9c51cf4d5mr9339934oto.10.1698136545335; Tue, 24 Oct 2023 01:35:45 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1698136545; cv=none; d=google.com; s=arc-20160816; b=TlCXva8/lXsW9QCSemFtKgRf6N3/VuXto+3NAMYMhQjYkRxrUgPqVh3SbuaXAU/bvs yRT01m3QG+hpzMpl9BrihMwubv2PWwo7zNBjW9Xl4/7XKJWbUsa/fNma0Xd4ybWunhAe 73hJzVsPzJPQZFCOapV7jb7n9x5nXjECqBtYzuw0UCwCeseYHJs7c3zn6wVeXVa5q1cU vaeKtz7LThJDiq2qznuoDyTCSFDXqi6/gse9Jsn9s4CH2S3ObFq2QvKfTBkG2g92joZ7 /J2pFj7DWTfyrfnD6xICBMoEjP35QIAz1t07V2MGAltzKWqHVvBw1Nb71dXWVF97myV2 Pbjg== 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=dqxLSD3NSY9H2G/bHFoEqq0XRO6Fu01n0ZJ8sfPfXdw=; fh=W1ujNbDikRM6mL+MA7cZ93eipzimk+g+Mb7QYnlff5s=; b=wuFvorWkq/UZIiV/gtkJ/kfkOuAdZx01+KBQ9RhMhpJi8V3ELFXh4QhziA8M0kH5g3 B8b1eHSbQwtIBXSCRa+7DRo0N9lzAceYVXUv/S9eG9sVJhK4Gm2T0rxYI3t9uU0mfxXO g+B4X9UX3PIGvzSsdL9HsEjeTfpkYmPEnO1GRtmM6yIAasibXqoX4C9V4j56Q1KrXOA2 rbbRf7V96oYIQ5lq2jV3/Owkn1bsOaTUSiuRUvJeFx3avPa5q2R2KSV7jpIRWuE5RPYH FDy50IoIWGYMfhdZ3yTSQP8BvJAF8EInH+Cc3b+gJkEjXbBB6/r5oLhyT1vK361618dy 4OEw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=MKdirIRH; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.33 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 lipwig.vger.email (lipwig.vger.email. [23.128.96.33]) by mx.google.com with ESMTPS id r25-20020a632059000000b0056f7f18bbfdsi7789671pgm.632.2023.10.24.01.35.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Oct 2023 01:35:45 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.33 as permitted sender) client-ip=23.128.96.33; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=MKdirIRH; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.33 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 (depot.vger.email [IPv6:2620:137:e000::3:0]) by lipwig.vger.email (Postfix) with ESMTP id BF525807E897; Tue, 24 Oct 2023 01:35:04 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at lipwig.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234135AbjJXIes (ORCPT + 26 others); Tue, 24 Oct 2023 04:34:48 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34056 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233939AbjJXIeY (ORCPT ); Tue, 24 Oct 2023 04:34:24 -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 6A0ECBD for ; Tue, 24 Oct 2023 01:34:03 -0700 (PDT) Received: by mail-pf1-x42b.google.com with SMTP id d2e1a72fcca58-6ba172c5f3dso3475584b3a.0 for ; Tue, 24 Oct 2023 01:34:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136443; x=1698741243; darn=vger.kernel.org; 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=dqxLSD3NSY9H2G/bHFoEqq0XRO6Fu01n0ZJ8sfPfXdw=; b=MKdirIRHDWMXrZldlkKkyv45rQvdYsahrjj3ySkW2re3bNgn/usFmkmjrvG1A+X+ZG Qa5pbzWhIglQAdjMGoVOBRt/GbewDXZcBnd/3Pu4lnhtnEpe+BJhpKA6bl+30m1oADFQ xmWMo77z9vSOk/4u6n5+BSJbc0gARiBvOANsFOpOK/YcaC/pvckjLtimdFLQ/ieVBoLD qyyzEo85Mhg95wBbyVrRot7Q+mk4K511nB+XeamATfWM8ndtfOLpjP79DeDsI5wkvMJz 3fE9AjE0p8Vu87Y/KuNMfvSEhISNhN1Zl6LXXcGi69ONJY7MmRE2cl3hBeuTH78rTUok U3nA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136443; x=1698741243; 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=dqxLSD3NSY9H2G/bHFoEqq0XRO6Fu01n0ZJ8sfPfXdw=; b=u/U0voDEeuyPQREfUMeVjV0HJlqpEg3OMReAS3GG46xtg0y8wKCXI2FAblZy6Zy6nw YQemqvxyOW1Hp+LO+fEQGRWKC5xHw3sElpmqOnHTNgdYXsFq/W7L8w0+ZcorBpIGy0dG lOO9q+RoBkZ8QJ4c4yNAe5Q8wpvhiEH21NZ6lFdQfeg42QKHgL3rhQk8LSjVZC4eUJJ0 7YgZ5F/KHF++LDlniabD/6e/JgPEsxSxrE7xPi4/YIqLvEOQM0Ngedbk5TOIG3x8EX+J SGWY5qDHn46QCwFMriPza++YRQFQ2rKoBHC9hxjAuvsd2sEC4NGrN8eHKnISb1zafDjb CzKA== X-Gm-Message-State: AOJu0YxMWqS1ORyM2iTON34jAwo8eKyRJ0Wusca2NkRGOR8mNuSDSrQG Uf42lajJ7U39on60S56C08PACw== X-Received: by 2002:a05:6a21:7189:b0:17b:4b61:a907 with SMTP id wq9-20020a056a21718900b0017b4b61a907mr1679463pzb.50.1698136442907; Tue, 24 Oct 2023 01:34:02 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.56 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:34:02 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v6 08/10] maple_tree: Update check_forking() and bench_forking() Date: Tue, 24 Oct 2023 16:32:56 +0800 Message-Id: <20231024083258.65750-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lipwig.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (lipwig.vger.email [0.0.0.0]); Tue, 24 Oct 2023 01:35:04 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1780625226322806458 X-GMAIL-MSGID: 1780625226322806458 Updated check_forking() and bench_forking() to use __mt_dup() to duplicate maple tree. Signed-off-by: Peng Zhang --- lib/test_maple_tree.c | 117 ++++++++++++++++++------------------ tools/include/linux/rwsem.h | 4 ++ 2 files changed, 62 insertions(+), 59 deletions(-) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index de470950714f..3e4597fb49d3 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1834,47 +1834,48 @@ static noinline void __init bench_mas_prev(struct maple_tree *mt) } #endif /* check_forking - simulate the kernel forking sequence with the tree. */ -static noinline void __init check_forking(struct maple_tree *mt) +static noinline void __init check_forking(void) { - - struct maple_tree newmt; - int i, nr_entries = 134; + struct maple_tree mt, newmt; + int i, nr_entries = 134, ret; void *val; - MA_STATE(mas, mt, 0, 0); - MA_STATE(newmas, mt, 0, 0); - struct rw_semaphore newmt_lock; + MA_STATE(mas, &mt, 0, 0); + MA_STATE(newmas, &newmt, 0, 0); + struct rw_semaphore mt_lock, newmt_lock; + init_rwsem(&mt_lock); init_rwsem(&newmt_lock); - for (i = 0; i <= nr_entries; i++) - mtree_store_range(mt, i*10, i*10 + 5, - xa_mk_value(i), GFP_KERNEL); + mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); + mt_set_external_lock(&mt, &mt_lock); - mt_set_non_kernel(99999); mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); mt_set_external_lock(&newmt, &newmt_lock); - newmas.tree = &newmt; - mas_reset(&newmas); - mas_reset(&mas); - down_write(&newmt_lock); - mas.index = 0; - mas.last = 0; - if (mas_expected_entries(&newmas, nr_entries)) { + + down_write(&mt_lock); + for (i = 0; i <= nr_entries; i++) { + mas_set_range(&mas, i*10, i*10 + 5); + mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL); + } + + down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING); + ret = __mt_dup(&mt, &newmt, GFP_KERNEL); + if (ret) { pr_err("OOM!"); BUG_ON(1); } - rcu_read_lock(); - mas_for_each(&mas, val, ULONG_MAX) { - newmas.index = mas.index; - newmas.last = mas.last; + + mas_set(&newmas, 0); + mas_for_each(&newmas, val, ULONG_MAX) mas_store(&newmas, val); - } - rcu_read_unlock(); + mas_destroy(&newmas); + mas_destroy(&mas); mt_validate(&newmt); - mt_set_non_kernel(0); __mt_destroy(&newmt); + __mt_destroy(&mt); up_write(&newmt_lock); + up_write(&mt_lock); } static noinline void __init check_iteration(struct maple_tree *mt) @@ -1977,49 +1978,51 @@ static noinline void __init check_mas_store_gfp(struct maple_tree *mt) } #if defined(BENCH_FORK) -static noinline void __init bench_forking(struct maple_tree *mt) +static noinline void __init bench_forking(void) { - - struct maple_tree newmt; - int i, nr_entries = 134, nr_fork = 80000; + struct maple_tree mt, newmt; + int i, nr_entries = 134, nr_fork = 80000, ret; void *val; - MA_STATE(mas, mt, 0, 0); - MA_STATE(newmas, mt, 0, 0); - struct rw_semaphore newmt_lock; + MA_STATE(mas, &mt, 0, 0); + MA_STATE(newmas, &newmt, 0, 0); + struct rw_semaphore mt_lock, newmt_lock; + init_rwsem(&mt_lock); init_rwsem(&newmt_lock); - mt_set_external_lock(&newmt, &newmt_lock); - for (i = 0; i <= nr_entries; i++) - mtree_store_range(mt, i*10, i*10 + 5, - xa_mk_value(i), GFP_KERNEL); + mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); + mt_set_external_lock(&mt, &mt_lock); + + down_write(&mt_lock); + for (i = 0; i <= nr_entries; i++) { + mas_set_range(&mas, i*10, i*10 + 5); + mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL); + } for (i = 0; i < nr_fork; i++) { - mt_set_non_kernel(99999); - mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE); - newmas.tree = &newmt; - mas_reset(&newmas); - mas_reset(&mas); - mas.index = 0; - mas.last = 0; - rcu_read_lock(); - down_write(&newmt_lock); - if (mas_expected_entries(&newmas, nr_entries)) { - printk("OOM!"); + mt_init_flags(&newmt, + MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); + mt_set_external_lock(&newmt, &newmt_lock); + + down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING); + ret = __mt_dup(&mt, &newmt, GFP_KERNEL); + if (ret) { + pr_err("OOM!"); BUG_ON(1); } - mas_for_each(&mas, val, ULONG_MAX) { - newmas.index = mas.index; - newmas.last = mas.last; + + mas_set(&newmas, 0); + mas_for_each(&newmas, val, ULONG_MAX) mas_store(&newmas, val); - } + mas_destroy(&newmas); - rcu_read_unlock(); mt_validate(&newmt); - mt_set_non_kernel(0); __mt_destroy(&newmt); up_write(&newmt_lock); } + mas_destroy(&mas); + __mt_destroy(&mt); + up_write(&mt_lock); } #endif @@ -3615,9 +3618,7 @@ static int __init maple_tree_seed(void) #endif #if defined(BENCH_FORK) #define BENCH - mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); - bench_forking(&tree); - mtree_destroy(&tree); + bench_forking(); goto skip; #endif #if defined(BENCH_MT_FOR_EACH) @@ -3650,9 +3651,7 @@ static int __init maple_tree_seed(void) check_iteration(&tree); mtree_destroy(&tree); - mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); - check_forking(&tree); - mtree_destroy(&tree); + check_forking(); mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_mas_store_gfp(&tree); diff --git a/tools/include/linux/rwsem.h b/tools/include/linux/rwsem.h index 83971b3cbfce..f8bffd4a987c 100644 --- a/tools/include/linux/rwsem.h +++ b/tools/include/linux/rwsem.h @@ -37,4 +37,8 @@ static inline int up_write(struct rw_semaphore *sem) { return pthread_rwlock_unlock(&sem->lock); } + +#define down_read_nested(sem, subclass) down_read(sem) +#define down_write_nested(sem, subclass) down_write(sem) + #endif /* _TOOLS_RWSEM_H */ From patchwork Tue Oct 24 08:32:57 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 157293 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:ce89:0:b0:403:3b70:6f57 with SMTP id p9csp1798620vqx; Tue, 24 Oct 2023 01:34:42 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHbjPIG9bjBZLQ2dl1u2/Pe9Q5xEwn+FxYVcTV4QQxEarX0jyQlIgr5ZvW9QydkH1CefGpP X-Received: by 2002:a05:6a21:4889:b0:17b:61a7:e163 with SMTP id av9-20020a056a21488900b0017b61a7e163mr1781280pzc.55.1698136482521; Tue, 24 Oct 2023 01:34:42 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1698136482; cv=none; d=google.com; s=arc-20160816; b=Ix8nDxp+9b+ENLRPfws00xYNnzHXePxHxjsJIvPR1hzQPIJICPAHkkxlddtM4puViR WVH8F7S3xBycpuECPYmhXrzQz3rUtD/pbAKgHk2AHuGf2NVm27goH10gJUHtTX/Q0OZW YI8wbm3cJ8u8/E6PfPxD6lUHYcILlJfbktLrylPg2pwx3Bw5RrAv3cF1oDyrn9JOiQ3H o3Qi9diywF6QRPWzezD4XRFIPWidJcigAnj1rlisX3z+JNjmP6kVLkqEaovrsd7sQn8A Kss6RwJZc4wb+VyqIZBkLu29sZAFq5zpR1vbEYi2smpUAOp0C98ktjnk1ftsPw2tHdpv mR7Q== 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=bzccM6C4HLhaCIv/SAdijHFdTidMSXBWQyZ1w5RDJYw=; fh=W1ujNbDikRM6mL+MA7cZ93eipzimk+g+Mb7QYnlff5s=; b=NJMlWZ2DO+6RrlDU15D08cpupZaB8t15sqs9ov38LkJtA+j0U/sJKQh2akpHGkBIOD mCuudTZmjZT6laUopV7rxRuDLQHbtgPvvwGMjVrbQKjwRBtmjdM0/UxNBaYrmdPPrEjJ iplnXLGVaJkZqtU85qIDvtwH06xDz8vIVOkUIjGseeiBv3nTxAbF4GK1hrB2PYfXjhsd SF7v6pSMEA684pgKMfuIBYmF/KYlY3Eij9Bagmq1ZUFw1Jfga0A3To1sAMmqxv5Ml17o ITzlSqJ5ZTJj/zX6U+3GkwLCDSHSEYh/FBqPcdbZmqW9aAkJzc1joIpzgFumt3UnAvL/ Bbtw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=SNEB0fqk; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:3 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 lipwig.vger.email (lipwig.vger.email. [2620:137:e000::3:3]) by mx.google.com with ESMTPS id bz9-20020a056a02060900b005775e2a7951si8377763pgb.345.2023.10.24.01.34.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Oct 2023 01:34:42 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:3 as permitted sender) client-ip=2620:137:e000::3:3; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=SNEB0fqk; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:3 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 (depot.vger.email [IPv6:2620:137:e000::3:0]) by lipwig.vger.email (Postfix) with ESMTP id 9FECD8040C49; Tue, 24 Oct 2023 01:34:40 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at lipwig.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233983AbjJXIe0 (ORCPT + 26 others); Tue, 24 Oct 2023 04:34:26 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37992 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234058AbjJXIeN (ORCPT ); Tue, 24 Oct 2023 04:34:13 -0400 Received: from mail-oi1-x235.google.com (mail-oi1-x235.google.com [IPv6:2607:f8b0:4864:20::235]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CAA1210E2 for ; Tue, 24 Oct 2023 01:34:10 -0700 (PDT) Received: by mail-oi1-x235.google.com with SMTP id 5614622812f47-3b2ec5ee2e4so2865068b6e.3 for ; Tue, 24 Oct 2023 01:34:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136449; x=1698741249; darn=vger.kernel.org; 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=bzccM6C4HLhaCIv/SAdijHFdTidMSXBWQyZ1w5RDJYw=; b=SNEB0fqkUuNyllJMMihVQAlGEvxlD846I1ZA7TkiLKmn/zyiO9QTOKglOHgTOcy7cw YaQlyKeiffS0uBl0lsyehChNpguuAEKJpZsQ442epIy4bfYmwaCX82TCvQ9KN0h3NGUV mxBJaH2rWV1QYqjdWxijJtnCIpnOTP9hu7rIzjFqVqMUYJZUP42NmhsYjTqDZpdFVIa2 rH4ZlQYIjLZVgBGvDx1lkWCUz+ETFTNWdf3q5XYEi5MWtUfNqfG7SY9kwJI6VQ7LHvzy ccFB3SBBXl2A7Qla4vYnkGr+P0ogb5fKONd6b26qNaUv4Jvq4fW3EDpC0hAgGT5zTGbV NUcg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136449; x=1698741249; 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=bzccM6C4HLhaCIv/SAdijHFdTidMSXBWQyZ1w5RDJYw=; b=DJuO2ePYeNl5jQu59XzFHLr1A8ZrQj+1aZgHPNHhVyYaNiQMUEY2MoYJuiHWe3ql0W a8oGaNqSZUtBD4OAxMddPZkPhbOUamLmz0HTxNHWiHK/H/BoNCOZ5EQgpuW3IsLi41Cw qXCtO6WN9XtwfB9xP6hB/9G8q7xR1PiN6VVLBjv+TYuMWIfhbfayvR/XXRTyJ5xC7pGe xUlRJv5GUBXry7Xo48w4BnU9LAVYmawf4TGBBPk6FJQ7bvTOqiuZJauAk/g4koPii6Uj 90gYTSdwiZMjjClZ66KW3cZC4e4yx5mj6jQV6/cAcUkOoh/yBP4TTJPfCeiwiE1QTc93 c+Mw== X-Gm-Message-State: AOJu0YwrlXDyUMfTBSoXIUgHWcyyO5oojOJmGJ/YAGQIbsAXqLCWNbLX XSezpLY84AcTaZpNr9m5SMU2pQ== X-Received: by 2002:a05:6358:810c:b0:168:d6cd:7b2e with SMTP id p12-20020a056358810c00b00168d6cd7b2emr7924030rwk.29.1698136449463; Tue, 24 Oct 2023 01:34:09 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.34.03 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:34:09 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v6 09/10] maple_tree: Preserve the tree attributes when destroying maple tree Date: Tue, 24 Oct 2023 16:32:57 +0800 Message-Id: <20231024083258.65750-10-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lipwig.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (lipwig.vger.email [0.0.0.0]); Tue, 24 Oct 2023 01:34:40 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1780625160580986042 X-GMAIL-MSGID: 1780625160580986042 When destroying maple tree, preserve its attributes and then turn it into an empty tree. This allows it to be reused without needing to be reinitialized. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6704b5c507b2..b9e238e7a7af 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6765,7 +6765,7 @@ void __mt_destroy(struct maple_tree *mt) if (xa_is_node(root)) mte_destroy_walk(root, mt); - mt->ma_flags = 0; + mt->ma_flags = mt_attr(mt); } EXPORT_SYMBOL_GPL(__mt_destroy); From patchwork Tue Oct 24 08:32: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: 157297 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:ce89:0:b0:403:3b70:6f57 with SMTP id p9csp1799213vqx; Tue, 24 Oct 2023 01:36:09 -0700 (PDT) X-Google-Smtp-Source: AGHT+IEJEf2S36YLpj8MDdwPbwoUh9ktcfm7ReC1xfipQtUYoL7iq2K2n7rM8DlS3BkGmkcMiuBi X-Received: by 2002:a05:6a00:248d:b0:6b2:5992:9e89 with SMTP id c13-20020a056a00248d00b006b259929e89mr14305684pfv.9.1698136569615; Tue, 24 Oct 2023 01:36:09 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1698136569; cv=none; d=google.com; s=arc-20160816; b=dt9/kK4kE7gRGMpFUQ8q1A0bIPlU+OQUojirHovfzTs9A37rbRguTzXK6CVYeQd71u 8NyLp8O3UZZUUNk3zuiSZ6tL08MbNwhweML77qFTffKe57Kwfkb0bkgOwHQBUCDVHOkZ lBIbcjt13N39HebPh69ogLEFmMKW8c1CGt7ZJuXlOcWtqL69KZEKP9E5RKXGKFruiuvn ofSO7jqFQunJWx5tlKWTHegvUZPXQUk6PWoF/0U6qHCLS9GXLVnTypcFFW6VKERhoMFf zaQzbmn79UzzWN3oF2xQiFDc7gGircNelkJ5LCFXWTDiysL0OrF9aOee6jhYn9uPf6nw QCNA== 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=NhuvPcTMRDCD3VOBYhVRa0kZDnR2cgXp2fXq7JVV3pE=; fh=W1ujNbDikRM6mL+MA7cZ93eipzimk+g+Mb7QYnlff5s=; b=Ajwvni0S1noEAlMtx+ukGO2oIA448lh5astvAhMFsO387bgCO2t3XXmSVEUxo5rQVH fB2mMYxj+8fZjACwKKntWcB4WFtvGuWD7346uNa5wcX1FVO+2QfvvC1Msl0IlqiShjJd LqMgZh+WDeJ8G5zQSCw21LSSXgzsxUwhRyOjQl/eztiX4+d33n25ukHr0yptlw2vxKML bw83VwLeYaERDrdNuxDpcDXSZ84ygoyfzwcpCI12D4sX28A2vx1n/Cjk/2kY5pypDD1Z 8tf/FRgqKeLp2nmbGbmlM71XwJeK2fjlmQI8iO4x+PonixNKR2Hx9+C/bo9c4Tkl2z4c 5jTg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=cDbOB552; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.38 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 fry.vger.email (fry.vger.email. [23.128.96.38]) by mx.google.com with ESMTPS id x32-20020a634a20000000b005b42f4443b7si8103834pga.653.2023.10.24.01.36.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Oct 2023 01:36:09 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.38 as permitted sender) client-ip=23.128.96.38; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=cDbOB552; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.38 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 (depot.vger.email [IPv6:2620:137:e000::3:0]) by fry.vger.email (Postfix) with ESMTP id 8A7AA80B9F8F; Tue, 24 Oct 2023 01:35:35 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at fry.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232982AbjJXIfR (ORCPT + 26 others); Tue, 24 Oct 2023 04:35:17 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40486 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233988AbjJXIem (ORCPT ); Tue, 24 Oct 2023 04:34:42 -0400 Received: from mail-pf1-x432.google.com (mail-pf1-x432.google.com [IPv6:2607:f8b0:4864:20::432]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 166AA172C for ; Tue, 24 Oct 2023 01:34:16 -0700 (PDT) Received: by mail-pf1-x432.google.com with SMTP id d2e1a72fcca58-6b497c8575aso4179705b3a.1 for ; Tue, 24 Oct 2023 01:34:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136456; x=1698741256; darn=vger.kernel.org; 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=NhuvPcTMRDCD3VOBYhVRa0kZDnR2cgXp2fXq7JVV3pE=; b=cDbOB552h6db4BuaCuIYz243RmuvKZ+aUfLpkVe4LVKmgFYFETTGlPNrIudPP4bmyk tM1Z0+r+O6TOBOTZzRqW6ltrR1KLFBeBpH95P1RcxfyZH7CNhaEMacg8J7qJY6fAGnS4 lKV7c5ei7X9V6noPFGKsDC5Af4uJybdUrpfMdS6F8sEfeOcFJwnL9xlFjg4wEjHfP2sN JNQ8uaCcx2IggFkZPhw3iA4Sxvq25BF3Lvo+RFc45gMVneG/TF7vSQWrbkl6FbcMds08 Tt7bP2JrFPC8saqs1nDuF6PVUfTgYuDedyXL45QxuUV2Y9FMjDS0BE6z8QfoZekY8Y5M 94BQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136456; x=1698741256; 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=NhuvPcTMRDCD3VOBYhVRa0kZDnR2cgXp2fXq7JVV3pE=; b=iDgnFN6m1EAZPa69rrKphuCmdP+buJn6+c0kmZuvApOE1Nfjky9OEGfOeq+mNwto4K IDkAwirVe6044Mzez7J4lRwQRyt9omLXceJVtcGt4pKnN479Jp6WP1SuI6td7KPpUnVT VUxzyM5yy8nLRzpqRuHfoDMmOhGMBUv5zKn44H8m/dc5L0ymX4Ou+B3/IIPjYMmHl3YB edHTPXjarE6nxeYKaCaEcoKlJgeHV33JEpUo4hyMtEU1lfjsTkfDHr5iCO4zrK1iv2n2 3aMfXXelHuv7diGau/GQNX7PYVooW3Uc5V6W10ucbOOU442I/H85USeC1bCmJ1g2MFyW 7uUw== X-Gm-Message-State: AOJu0Yz2b9cBk1+HU2qyqzwg1rOYaqehOYXty3TOyttg/aGcDWO67jPX DFb7JMH17ehx7Vvy94z9GZCjRA== X-Received: by 2002:a05:6a00:c8b:b0:6be:5a1a:3bb8 with SMTP id a11-20020a056a000c8b00b006be5a1a3bb8mr14049796pfv.28.1698136456363; Tue, 24 Oct 2023 01:34:16 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.34.09 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:34:16 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v6 10/10] fork: Use __mt_dup() to duplicate maple tree in dup_mmap() Date: Tue, 24 Oct 2023 16:32:58 +0800 Message-Id: <20231024083258.65750-11-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on fry.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (fry.vger.email [0.0.0.0]); Tue, 24 Oct 2023 01:35:35 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1780625251697617990 X-GMAIL-MSGID: 1780625251697617990 In dup_mmap(), using __mt_dup() to duplicate the old maple tree and then directly replacing the entries of VMAs in the new maple tree can result in better performance. __mt_dup() uses DFS pre-order to duplicate the maple tree, so it is efficient. The average time complexity of __mt_dup() is O(n), where n is the number of VMAs. The proof of the time complexity is provided in the commit log that introduces __mt_dup(). After duplicating the maple tree, each element is traversed and replaced (ignoring the cases of deletion, which are rare). Since it is only a replacement operation for each element, this process is also O(n). Analyzing the exact time complexity of the previous algorithm is challenging because each insertion can involve appending to a node, pushing data to adjacent nodes, or even splitting nodes. The frequency of each action is difficult to calculate. The worst-case scenario for a single insertion is when the tree undergoes splitting at every level. If we consider each insertion as the worst-case scenario, we can determine that the upper bound of the time complexity is O(n*log(n)), although this is a loose upper bound. However, based on the test data, it appears that the actual time complexity is likely to be O(n). As the entire maple tree is duplicated using __mt_dup(), if dup_mmap() fails, there will be a portion of VMAs that have not been duplicated in the maple tree. To handle this, we mark the failure point with XA_ZERO_ENTRY. In exit_mmap(), if this marker is encountered, stop releasing VMAs that have not been duplicated after this point. There is a "spawn" in byte-unixbench[1], which can be used to test the performance of fork(). I modified it slightly to make it work with different number of VMAs. Below are the test results. The first row shows the number of VMAs. The second and third rows show the number of fork() calls per ten seconds, corresponding to next-20231006 and the this patchset, respectively. The test results were obtained with CPU binding to avoid scheduler load balancing that could cause unstable results. There are still some fluctuations in the test results, but at least they are better than the original performance. 21 121 221 421 821 1621 3221 6421 12821 25621 51221 112100 76261 54227 34035 20195 11112 6017 3161 1606 802 393 114558 83067 65008 45824 28751 16072 8922 4747 2436 1233 599 2.19% 8.92% 19.88% 34.64% 42.37% 44.64% 48.28% 50.17% 51.68% 53.74% 52.42% [1] https://github.com/kdlucas/byte-unixbench/tree/master Signed-off-by: Peng Zhang Suggested-by: Liam R. Howlett --- include/linux/mm.h | 11 +++++++++++ kernel/fork.c | 40 +++++++++++++++++++++++++++++----------- mm/internal.h | 11 ----------- mm/memory.c | 7 ++++++- mm/mmap.c | 9 ++++++--- 5 files changed, 52 insertions(+), 26 deletions(-) diff --git a/include/linux/mm.h b/include/linux/mm.h index 14d5aaff96d0..e9111ec5808c 100644 --- a/include/linux/mm.h +++ b/include/linux/mm.h @@ -996,6 +996,17 @@ static inline int vma_iter_bulk_alloc(struct vma_iterator *vmi, return mas_expected_entries(&vmi->mas, count); } +static inline int vma_iter_clear_gfp(struct vma_iterator *vmi, + unsigned long start, unsigned long end, gfp_t gfp) +{ + __mas_set_range(&vmi->mas, start, end - 1); + mas_store_gfp(&vmi->mas, NULL, gfp); + if (unlikely(mas_is_err(&vmi->mas))) + return -ENOMEM; + + return 0; +} + /* Free any unused preallocations */ static inline void vma_iter_free(struct vma_iterator *vmi) { diff --git a/kernel/fork.c b/kernel/fork.c index 1e6c656e0857..1552ee66517b 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -650,7 +650,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, int retval; unsigned long charge = 0; LIST_HEAD(uf); - VMA_ITERATOR(old_vmi, oldmm, 0); VMA_ITERATOR(vmi, mm, 0); uprobe_start_dup_mmap(); @@ -678,16 +677,22 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, goto out; khugepaged_fork(mm, oldmm); - retval = vma_iter_bulk_alloc(&vmi, oldmm->map_count); - if (retval) + /* Use __mt_dup() to efficiently build an identical maple tree. */ + retval = __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_KERNEL); + if (unlikely(retval)) goto out; mt_clear_in_rcu(vmi.mas.tree); - for_each_vma(old_vmi, mpnt) { + for_each_vma(vmi, mpnt) { struct file *file; vma_start_write(mpnt); if (mpnt->vm_flags & VM_DONTCOPY) { + retval = vma_iter_clear_gfp(&vmi, mpnt->vm_start, + mpnt->vm_end, GFP_KERNEL); + if (retval) + goto loop_out; + vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt)); continue; } @@ -749,9 +754,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, if (is_vm_hugetlb_page(tmp)) hugetlb_dup_vma_private(tmp); - /* Link the vma into the MT */ - if (vma_iter_bulk_store(&vmi, tmp)) - goto fail_nomem_vmi_store; + /* + * Link the vma into the MT. After using __mt_dup(), memory + * allocation is not necessary here, so it cannot fail. + */ + vma_iter_bulk_store(&vmi, tmp); mm->map_count++; if (!(tmp->vm_flags & VM_WIPEONFORK)) @@ -760,15 +767,28 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, if (tmp->vm_ops && tmp->vm_ops->open) tmp->vm_ops->open(tmp); - if (retval) + if (retval) { + mpnt = vma_next(&vmi); goto loop_out; + } } /* a new mm has just been created */ retval = arch_dup_mmap(oldmm, mm); loop_out: vma_iter_free(&vmi); - if (!retval) + if (!retval) { mt_set_in_rcu(vmi.mas.tree); + } else if (mpnt) { + /* + * The entire maple tree has already been duplicated. If the + * mmap duplication fails, mark the failure point with + * XA_ZERO_ENTRY. In exit_mmap(), if this marker is encountered, + * stop releasing VMAs that have not been duplicated after this + * point. + */ + mas_set_range(&vmi.mas, mpnt->vm_start, mpnt->vm_end - 1); + mas_store(&vmi.mas, XA_ZERO_ENTRY); + } out: mmap_write_unlock(mm); flush_tlb_mm(oldmm); @@ -778,8 +798,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, uprobe_end_dup_mmap(); return retval; -fail_nomem_vmi_store: - unlink_anon_vmas(tmp); fail_nomem_anon_vma_fork: mpol_put(vma_policy(tmp)); fail_nomem_policy: diff --git a/mm/internal.h b/mm/internal.h index b52a526d239d..1825c3b2e15c 100644 --- a/mm/internal.h +++ b/mm/internal.h @@ -1154,17 +1154,6 @@ static inline void vma_iter_clear(struct vma_iterator *vmi) mas_store_prealloc(&vmi->mas, NULL); } -static inline int vma_iter_clear_gfp(struct vma_iterator *vmi, - unsigned long start, unsigned long end, gfp_t gfp) -{ - __mas_set_range(&vmi->mas, start, end - 1); - mas_store_gfp(&vmi->mas, NULL, gfp); - if (unlikely(mas_is_err(&vmi->mas))) - return -ENOMEM; - - return 0; -} - static inline struct vm_area_struct *vma_iter_load(struct vma_iterator *vmi) { return mas_walk(&vmi->mas); diff --git a/mm/memory.c b/mm/memory.c index 4f0dfbd5e4bf..163d8f09dafc 100644 --- a/mm/memory.c +++ b/mm/memory.c @@ -374,6 +374,8 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, * be 0. This will underflow and is okay. */ next = mas_find(mas, ceiling - 1); + if (unlikely(xa_is_zero(next))) + next = NULL; /* * Hide vma from rmap and truncate_pagecache before freeing @@ -395,6 +397,8 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, && !is_vm_hugetlb_page(next)) { vma = next; next = mas_find(mas, ceiling - 1); + if (unlikely(xa_is_zero(next))) + next = NULL; if (mm_wr_locked) vma_start_write(vma); unlink_anon_vmas(vma); @@ -1743,7 +1747,8 @@ void unmap_vmas(struct mmu_gather *tlb, struct ma_state *mas, unmap_single_vma(tlb, vma, start, end, &details, mm_wr_locked); hugetlb_zap_end(vma, &details); - } while ((vma = mas_find(mas, tree_end - 1)) != NULL); + vma = mas_find(mas, tree_end - 1); + } while (vma && likely(!xa_is_zero(vma))); mmu_notifier_invalidate_range_end(&range); } diff --git a/mm/mmap.c b/mm/mmap.c index 8b57e42fd980..9d9f124ef38b 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -3300,10 +3300,11 @@ void exit_mmap(struct mm_struct *mm) arch_exit_mmap(mm); vma = mas_find(&mas, ULONG_MAX); - if (!vma) { + if (!vma || unlikely(xa_is_zero(vma))) { /* Can happen if dup_mmap() received an OOM */ mmap_read_unlock(mm); - return; + mmap_write_lock(mm); + goto destroy; } lru_add_drain(); @@ -3338,11 +3339,13 @@ void exit_mmap(struct mm_struct *mm) remove_vma(vma, true); count++; cond_resched(); - } while ((vma = mas_find(&mas, ULONG_MAX)) != NULL); + vma = mas_find(&mas, ULONG_MAX); + } while (vma && likely(!xa_is_zero(vma))); BUG_ON(count != mm->map_count); trace_exit_mmap(mm); +destroy: __mt_destroy(&mm->mm_mt); mmap_write_unlock(mm); vm_unacct_memory(nr_accounted);