From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 30669EB64D8 for ; Thu, 22 Jun 2023 16:41:39 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 313D88D0002; Thu, 22 Jun 2023 12:41:38 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 2C40E8D0001; Thu, 22 Jun 2023 12:41:38 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 18D9B8D0002; Thu, 22 Jun 2023 12:41:38 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 09CE08D0001 for ; Thu, 22 Jun 2023 12:41:38 -0400 (EDT) Received: from smtpin02.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id C7D931C8959 for ; Thu, 22 Jun 2023 16:41:37 +0000 (UTC) X-FDA: 80930949834.02.8C526C6 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by imf07.hostedemail.com (Postfix) with ESMTP id 8ED1840007 for ; Thu, 22 Jun 2023 16:41:35 +0000 (UTC) Authentication-Results: imf07.hostedemail.com; dkim=pass header.d=redhat.com header.s=mimecast20190719 header.b=WsjznGXZ; spf=pass (imf07.hostedemail.com: domain of dakr@redhat.com designates 170.10.133.124 as permitted sender) smtp.mailfrom=dakr@redhat.com; dmarc=pass (policy=none) header.from=redhat.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1687452095; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=pKQxo2ybKG3VitBeJfoexX4S6PJQFIvYCFny4nwoy3Y=; b=bPcatQ0RE63ygAbtPcC29vhwN3fgZ7Np41cynZ9FhH0zdAqLm9l6jNttEdiIzaIrQXm00C 0EtFbXW0C+FK7FtdQ3VaqperObNBdIMiQAnHSn70YSnO32zUIpgWbguLLbPrT2WNuUEF9j iyqq2gBQ36WXMVqrJhwzJGviF0HJT9Y= ARC-Authentication-Results: i=1; imf07.hostedemail.com; dkim=pass header.d=redhat.com header.s=mimecast20190719 header.b=WsjznGXZ; spf=pass (imf07.hostedemail.com: domain of dakr@redhat.com designates 170.10.133.124 as permitted sender) smtp.mailfrom=dakr@redhat.com; dmarc=pass (policy=none) header.from=redhat.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1687452095; a=rsa-sha256; cv=none; b=zlkei1M5lF14hsURimJTEotchTcPZh7DHRa9c6Klb0rR3NB/kQhH74SNXM4+9hh0eVOpQ4 557VhreYw5d3BGFDnrgeSbAVekwrDEDwNxXbjf7x5sLSAqZ/HDy2a3Gj1eGL5Bha0eJDkp AdfEHy/yg24kjRj7A82PSdunBXpDTns= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1687452094; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=pKQxo2ybKG3VitBeJfoexX4S6PJQFIvYCFny4nwoy3Y=; b=WsjznGXZD908GUhsO2Ni0CgSoPEGUyuwUaUj3TX2Is1K78xSVLkaonBJei0fIAL7UMpM1s mz17r6YUu6FnJkV+KwT2Bk3wJyH5LtFZLkUsaJt4qfmxnUvbK+Vvgjla83gdBrPsGc0Ctk /wIBjm65HVfdjm/sXdUJNc150Krz2pQ= Received: from mail-pl1-f199.google.com (mail-pl1-f199.google.com [209.85.214.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-402-8rko9s49Pxyl-6aOJhl6OQ-1; Thu, 22 Jun 2023 12:41:27 -0400 X-MC-Unique: 8rko9s49Pxyl-6aOJhl6OQ-1 Received: by mail-pl1-f199.google.com with SMTP id d9443c01a7336-1b679ec24f7so21557125ad.0 for ; Thu, 22 Jun 2023 09:41:27 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1687452086; x=1690044086; h=content-transfer-encoding:in-reply-to:organization:from:references :cc:to:content-language:subject:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=pKQxo2ybKG3VitBeJfoexX4S6PJQFIvYCFny4nwoy3Y=; b=fg9QLTyEUTK5nWMIcniLeCY0CG2qbsUbdoJg4//7uB3N8UzhdZXIfaztzpXRv3C6vv D0dOeH04EYRk8PymR/IQo2pEOtL6tqG5JRdBzSJ1SFiKv+romykGFullWLRtUR6yGqrj tocg5jkM0YxHjnkw7TNJTzQue7p7zuNkUmP/g87tapdo3F4G7Pak7yiaspVhc8t+SKTf F5Rjz662lDfMsfuLH91he2o9eapp3C8x6jo641foELh69TbQ+jpnyFoaWf6X/JmTD+3/ WwKOBlzuuCd29goLt9/y5880MpJm4eL+Bk9YxRJRg/XBqKL4okdvBWcTY6RRRtocjaZL oCxA== X-Gm-Message-State: AC+VfDydJ34KnC7jKnP9+KahvlBBTC/dFOLEJ5u7MVKHGwfm9ajxNr7V GIg3itvgqDB8k7pItLNpM0SWctRD1jVIdQ5ccK5ItRkOhdfQXdhNlBuygdKcvZeJXLZp4CrYycN k4Mpac4fULKo= X-Received: by 2002:a17:902:d682:b0:1b2:a63:9587 with SMTP id v2-20020a170902d68200b001b20a639587mr8026091ply.36.1687452086555; Thu, 22 Jun 2023 09:41:26 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ70F0+HQZlh5eNwYNO6SGbE2N5G7FJeFBkwR3g4WVuO3ZqYMiBjBKa4G94Qgr+Vu1E+d8T3Jw== X-Received: by 2002:a17:902:d682:b0:1b2:a63:9587 with SMTP id v2-20020a170902d68200b001b20a639587mr8026077ply.36.1687452086223; Thu, 22 Jun 2023 09:41:26 -0700 (PDT) Received: from ?IPV6:2a02:810d:4b3f:de9c:642:1aff:fe31:a15c? ([2a02:810d:4b3f:de9c:642:1aff:fe31:a15c]) by smtp.gmail.com with ESMTPSA id jk14-20020a170903330e00b001b536aaf7c2sm5639127plb.189.2023.06.22.09.41.21 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 22 Jun 2023 09:41:25 -0700 (PDT) Message-ID: <26d8fbcf-d34f-0a79-9d91-8c60e66f7341@redhat.com> Date: Thu, 22 Jun 2023 18:41:19 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.10.0 Subject: Re: [PATCH v2 14/16] maple_tree: Refine mas_preallocate() node calculations To: "Liam R. Howlett" , Andrew Morton Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, Peng Zhang , David Airlie , Boris Brezillon References: <20230612203953.2093911-1-Liam.Howlett@oracle.com> <20230612203953.2093911-15-Liam.Howlett@oracle.com> From: Danilo Krummrich Organization: RedHat In-Reply-To: <20230612203953.2093911-15-Liam.Howlett@oracle.com> X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Rspamd-Queue-Id: 8ED1840007 X-Rspam-User: X-Stat-Signature: bsfbgrskw8ko8mc35z6m8djpb8a1wuob X-Rspamd-Server: rspam01 X-HE-Tag: 1687452095-647997 X-HE-Meta: U2FsdGVkX1/kIaHsUgF6qWPRpEqUcFp4zJVjTYl1oKjmFcDnaGD6qHPsOBWvfjoz1yzhNwxJAEDN1Cx3OW89ceZsy1e9Teto1OZUS3dN9NHGNNgo+GF2UYuXsiKH6X2KCos4UHn3d1/zN3uxB0cxvlweCYTS1PuuAEyquf1sVpSxmIiWriNBNO/ItSVmSdqnGDq1P7k7pPStGob0Q1gLkpq9ncdVIRxOqeEl5d51ZYy0OCQQulG4GgnQxgrgepln8jo4hLYGXM8/jRaONlI7ea/bB77ptldYlhvv7cnkqkdt8IDXmei65toazGo4sOo4tW5AYp0lvU/t00912UIic3GQgwO0PxkynN3/ZgvVQMf3/54/Ud4hwS/HflumKspJnVhx36Vuc+6PFVPKSMzMGRYccoG9moYQiM2jy2qYlh7yCU2qerw0f647bHZQKvc1G9qLdsGT9XY8LlMUCeFPWm1owsv8UbQ8GoLp56DCunknMEtR7ugo+NxHXTCkYJ8ri00VLVxXufqm3wU3FdvL43hw0/DBnDSO+R14b7uTiU14YKCli5+rAkiRYkahVqRBefeD9R4RLJMP/tsRz3Ck2+4/NeemYvdLGWYpjYLW5MLYZVAXst+s2afsaOoytFzxMJwRvYvX0Ljoy2SfYb9xxXgVCuOZlqKo0ARNVDcJo7sTfGEvyF7tz0tmJAS+yHQmNjTdWY2gZkWjh7Am4v03VQiJLEsv184HYbgK4HAviXaSznUEygl03yr+VWia2lWZtnl3W76G8UT1SYEfgUXYVKlaJV+gKTffp9BRsYJSvidEnY1x5ZuHsgjjuqNDB0Fxz18PwXoPHBIviUGxF8ZncAl5/Iv1lRofY2Jo1R+lUJ+mMLTM/eLDpBvMo0q5iMJt/eFNzvHmWMRbJRBTrS08FiPJ7uKwQsRzWDEIjYYItL+ECjbwl/GJr5AiMWw9kZJ9mg4RwtBEV2DmY6KzlnC Vt2b7xm0 zTJBjpwF+lZ66tEu9CLPjgTz+M5hJkNOZ08it8g9F4pnVkD+eAXkm7b1bgnjOmFuQ9aXMgGWjDYcNKMnQ266hBhswlm+oTb16WaXr3OC/N7BrLfm/5APhPhaKa7h1Qez6AFwLH+JdtJno/zZ4JpntEiIUYzNTIMfvv0xCQN1YujBcpZ9GmFji02u5vHupY01Yb+sMkfZ9tjfCmgxWwhQ8uC1wvftyQjQJvp9aXfJ9rMONYDPd0tpWVhCuwCWyi3y01o9AGnFfP+qyRdc1COoK75TwL8zNhuR4BYswejCdLZRRtf85eIS+qcCGiKenhv+Vjmyms7cxrgj6vc9MmwkOPdnW8yBupNSxbE19zwS1cfHtH2tvcfGv2QYPV4eBYgToDcmkRPVwZuyd5ctsWCAvNdRH2pZBHY3nXCDfTyrjYGnyQAwsCjgtsokTzS8RAThVsA7vogFw4qJX7k4ElvckfHSs6tv5mUa/m8BMGdSHZBY3kl0wFF5/0Sr0GDHhyqbtr6AsAmaCdF/wGyRNr2F60uXQmQTvpeg0lx2Eekn0CX63mahBnhlUnCrJgA== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: On 6/12/23 22:39, Liam R. Howlett wrote: > Calculate the number of nodes based on the pending write action instead > of assuming the worst case. Liam already gave me a heads-up on this patch, which I already replied to [1]. However, I think it might make sense to also reply to this patch directly. For a mas_preallocate() calculating the actual required nodes to be allocated instead of assuming the worst to work, it is required to ensure that the tree does not change between calling mas_preallocate() and mas_store_prealloc() if my understanding is correct. In DRM however, more specifically the DRM GPUVA Manager [2], we do have the case that we are not able to ensure this: Jobs to create GPU mappings can be submitted by userspace, are queued up by the kernel and are processed asynchronously in dma-fence signalling critical paths, e.g. by using the drm_gpu_scheduler. Hence, we must be able to allocate the worst case amount of node, since at the time a job is submitted we can't predict the state the maple tree keeping track of mappings has once a mapping is inserted in the (asynchronous) dma-fence signalling critical path. A more detailed explanation can be found in [1]. Could we keep a separate function for allocating the worst case amount of nodes additionally to this optimization? E.g. something like mas_preallocate_worst_case() or mas_preallocate_unlocked() (since I guess the new one requires the maple tree to be kept locked in order not to change)? [1] https://lore.kernel.org/nouveau/68cd25de-e767-725e-2e7b-703217230bb0@redhat.com/T/#ma326e200b1de1e3c9df4e9fcb3bf243061fee8b5 [2] https://lore.kernel.org/linux-mm/20230620004217.4700-8-dakr@redhat.com/T/#m47ab82310f87793d0f0cc1825a316eb30ad5b653 - Danilo > > This addresses a performance regression introduced in platforms that > have longer allocation timing. > > Signed-off-by: Liam R. Howlett > --- > lib/maple_tree.c | 48 +++++++++++++++++++++++++++++++++++++++++++++++- > 1 file changed, 47 insertions(+), 1 deletion(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index 048d6413a114..7ac5b5457603 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -5541,9 +5541,55 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc); > */ > int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) > { > + MA_WR_STATE(wr_mas, mas, entry); > + unsigned char node_size; > + int request = 1; > int ret; > > - mas_node_count_gfp(mas, 1 + mas_mt_height(mas) * 3, gfp); > + > + if (unlikely(!mas->index && mas->last == ULONG_MAX)) > + goto ask_now; > + > + mas_wr_store_setup(&wr_mas); > + wr_mas.content = mas_start(mas); > + /* Root expand */ > + if (unlikely(mas_is_none(mas) || mas_is_ptr(mas))) > + goto ask_now; > + > + if (unlikely(!mas_wr_walk(&wr_mas))) { > + /* Spanning store, use worst case for now */ > + request = 1 + mas_mt_height(mas) * 3; > + goto ask_now; > + } > + > + /* At this point, we are at the leaf node that needs to be altered. */ > + /* Exact fit, no nodes needed. */ > + if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last) > + return 0; > + > + mas_wr_end_piv(&wr_mas); > + node_size = mas_wr_new_end(&wr_mas); > + /* Slot store can avoid using any nodes */ > + if (node_size == wr_mas.node_end && wr_mas.offset_end - mas->offset == 1) > + return 0; > + > + if (node_size >= mt_slots[wr_mas.type]) { > + /* Split, worst case for now. */ > + request = 1 + mas_mt_height(mas) * 2; > + goto ask_now; > + } > + > + /* Appending does not need any nodes */ > + if (node_size == wr_mas.node_end + 1 && mas->offset == wr_mas.node_end) > + return 0; > + > + /* Potential spanning rebalance collapsing a node, use worst-case */ > + if (node_size - 1 <= mt_min_slots[wr_mas.type]) > + request = mas_mt_height(mas) * 2 - 1; > + > + /* node store needs one node */ > +ask_now: > + mas_node_count_gfp(mas, request, gfp); > mas->mas_flags |= MA_STATE_PREALLOC; > if (likely(!mas_is_err(mas))) > return 0;