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 89D31CD98F7 for ; Wed, 11 Oct 2023 07:40:27 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id E3F9A80047; Wed, 11 Oct 2023 03:40:26 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id DEFFA8D0002; Wed, 11 Oct 2023 03:40:26 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id CB86780047; Wed, 11 Oct 2023 03:40:26 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id BB80D8D0002 for ; Wed, 11 Oct 2023 03:40:26 -0400 (EDT) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 935951CA4DC for ; Wed, 11 Oct 2023 07:40:26 +0000 (UTC) X-FDA: 81332382852.01.8D3A496 Received: from mail-pf1-f181.google.com (mail-pf1-f181.google.com [209.85.210.181]) by imf05.hostedemail.com (Postfix) with ESMTP id 0E3B4100017 for ; Wed, 11 Oct 2023 07:40:23 +0000 (UTC) Authentication-Results: imf05.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="NepJB/+h"; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf05.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.181 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1697010024; 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=4pnqGnKI3R6wKiF3/G2J0E58yKUrzfwZftwQBcsaBg4=; b=PIWpz8QzVR88sttTkWLRvMl+xC8Zz2cfnS+acJt/+3kS4PHpWcXVRR6bjCEJQ1FbMI+699 ltEeDkHqzkVVKr/DmbWcFw2YTzWPGtnicIWBkygLm++Bvs2zNpC4HkvqsPgp/yq9Zto/nA hGCtb+ddbAS49wcFBoF5i4msyCFQbZA= ARC-Authentication-Results: i=1; imf05.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="NepJB/+h"; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf05.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.181 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1697010024; a=rsa-sha256; cv=none; b=fYdpkjL2hK6IRMKC40+rsAXtfdGP8f4XO/gPVCu8t+gCoYnUgCn55pMtMjsCB0HpLjZubp 9lgDGhq9cnVddEvcn/Dx7gs74slOwiT0TnbQcqRJAbVkz+yL9GWxwHt/cCrg3HfO5PgHog s5Ppk2DhL6LUoPPYo1RT2caSK0T23+s= Received: by mail-pf1-f181.google.com with SMTP id d2e1a72fcca58-694ed847889so4998686b3a.2 for ; Wed, 11 Oct 2023 00:40:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1697010022; x=1697614822; darn=kvack.org; h=content-transfer-encoding:in-reply-to:from:references:cc:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=4pnqGnKI3R6wKiF3/G2J0E58yKUrzfwZftwQBcsaBg4=; b=NepJB/+h5dA5xNtfhD6jF02Y4AzUHx5inkPf4EzHXvye1Dg1zuNVnOlWz4ISpEY3M6 BtQnvjn441wttycDMLqT9XoWPqhzN/P2/hWibkkhSwsQtMHYC0o5KDjjCFUmEh/u4YQ6 PWfBkfcBgYzYo11PAYPvGl7HqvZawnCvhtm58KwJWhL0ZcBhj3I9zrjhjhXhwml4Pshc /RK29TAOjP5K33DKDnSux3eocO86XlXA/J5bVGUV2RZlN4/7G+H7eMt+N5Sqya1Fkx4h Vu2HKSeLhoY1VVWnALBLAiaodnnbJcFxghWXHzmZY6AnhVNcz6TeHZAoxpSiAxo3btVw Jwxw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1697010022; x=1697614822; h=content-transfer-encoding:in-reply-to:from:references:cc:to:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=4pnqGnKI3R6wKiF3/G2J0E58yKUrzfwZftwQBcsaBg4=; b=BqnSicz7C6Uh+hjy72cqpfRV07NZ1QHboCxY0HivdkcUYKZc6CAXznQd+sXZR2ZJ7g E1hD04FxB425QIZTmziH9guYuRmX5AszpyeXj1cyS5t3s/0P4L0ZOpZt7CgahJFnIh3l 3xO0YizgzTHv9acax2eIC1NExfyQgENTuR0hFXtPwxxo4WCWGUy8zQpNqWDUtBPLanuF gMW1Mc4LxhMN/QztV6OFlKXsHHOdtxJJ3+djc+1UyH9iqEg2ytnozaMLpj4SUQOYhpvV e6F7qQOZ2Q/D/A/X57k40VRpcl9J2E3nKTVIiPNhz2apJMZT+jOINse1iYGM3gGnJLRU 30QQ== X-Gm-Message-State: AOJu0YzyHJCAXZn26TfpRKsOe7NkcQmTqdIBDwlEV4cHzlZNaLxUPWL8 VfxWEhZ8uCQ5lANKo/WKH1D8dA== X-Google-Smtp-Source: AGHT+IEt6pc4aozDoEfiAYwvPPkMRaJ0qWY33t9qGYwKCPWOwMsrrkyWEQ9pdIwTyHNy7FOWTiakvA== X-Received: by 2002:a05:6a20:6a28:b0:15e:5e8c:e45c with SMTP id p40-20020a056a206a2800b0015e5e8ce45cmr20109168pzk.30.1697010022705; Wed, 11 Oct 2023 00:40:22 -0700 (PDT) Received: from [10.84.146.237] ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id x6-20020a170902820600b001c99b3a1e45sm5962532pln.84.2023.10.11.00.40.19 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 11 Oct 2023 00:40:22 -0700 (PDT) Message-ID: <3342fd24-84f5-430f-8900-fd2d8ddae639@bytedance.com> Date: Wed, 11 Oct 2023 15:40:17 +0800 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH 2/3] maple_tree: use preallocations in mas_store_gfp() To: Sidhartha Kumar Cc: akpm@linux-foundation.org, willy@infradead.org, liam.howlett@oracle.com, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, Peng Zhang References: <20231009201639.920512-1-sidhartha.kumar@oracle.com> <20231009201639.920512-3-sidhartha.kumar@oracle.com> <205f093a-8b43-5b3b-7e87-2dcbe434f519@oracle.com> From: Peng Zhang In-Reply-To: <205f093a-8b43-5b3b-7e87-2dcbe434f519@oracle.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 0E3B4100017 X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: 6x8injajh5knwuch37zay9nioij6xf16 X-HE-Tag: 1697010023-280672 X-HE-Meta: U2FsdGVkX18wvgywC429LyYNsj9M9/U8SUKxc10l+uEKL4PnbPNtLW8V/c88+KShbqiJtbm1lvEqCT7VjpE26LczqqTqYv1ILzTD/tsjeH35Cboz+20P6XwSexhJUalbeTX9sRA5YoHBE+b3Mv7eGsOY7ib21NGN243doiunGRzkoJUB3nIaHHEj1BwX0fr/dxlVPyvIUfPGkJ28KhEv8uVo7ZRqGkVybsqzpBWsI3/Fo+JwECz3JbdyZ135sCvn4604glwUlQPyGk3HCStOu2z5/A78YmsYKREhCCyRaCTpp8M4YcLdpjxM6c8U1vc22grSKtxryot0aaUMVWBburJIPSbQTYKR12xnyi5L+CMDiM/a7pokiioBPv95Wssaa2XL+hegDH8pbSLEpNp8peA5cdEfIezZV0cBqutuXHWBpY1uTaQ4t2fDQglhmCyWfG/wOnfjtHV2Nlh1Zk86qPWpWXnFxBt05W0hgAkAonfVGdA/hosepQUEU+yB7R3m3XUCVORDALb++2aNGxwlafeoykChpUuNPAmTII/a2a5jnXND65elXFNeKklMaqOIG1a9WpRe1iBvwS3mZb7UgQWKu79fmNBNZYYlixvtYoUjOakIm4U77/fLYbMuqE8ann6joLl+NnsbDg7EbPJfIhW1cBxpnKYRNZBCNIukKagQAPqaIHFAerPsDQAI5TKefyZwENZI8ASyZOU1JfaM62y4vQ9XVgT1AhsqVnhIEBskQIk8oQHxZTbuSaCxg8410sPZDmzRFoUE4+lR5zt1j8iI8B2b63cgaPvo7q690iA7xoC2k3NVVZAIHopxGQYba2gDYdNzzSPeDOpu4OD9+2SQiEbwV+JGA8HZaprGyC19g2CBAoTYspBlY+4Los76gD7IqactZzdYSefG5pJPQjptU2ZxHuhBNo7Z+mO6dttXo60L3IX01AzfcdeIr6VZMwDKekFG42SVKFFmT1o 6KTKm1n0 wy0WyJ8WRG4f+aV/LK+7nxWfRdhgANXh9DLwn/On9In9c0n1SaXr7laJjpQX2SUq+a0hVxMfDEpFZvbyPT9J+EHzcXMmbTfyEiQeAur4WKtjN2Zb/szFroNAUa/1/r4IKcWzDABR9wn3t28m4iTVTJniqfKxgX18V21SEJv3GPFeqgOnT9IiUVHnsCzvbKnnJ7n+Gw+n1tD8kAMPVbNwYsHMNX2bfbZyygQy0HXUp5YO4wGdM52Q5Ri2NAAVScZuU26AOmbs/2yGFXldrdHghPwmxvAeaNbqOiJdNm6epZmKa65nGcRqaEIeyekdSlhg0YIPt0oXfg1Zzj2sE33jv8CFQM2jA1WmBIqzZoTpbv3EPIId1WzN5f4JipGq5c9K0HoUpYMd6d/3gRAjXu+4mfYovNqcn3k0+HwzIHq/ignKlcnV0YxMUNZKSD5s3phyideo5qWOJsuhHm/erJ/7RwRp/nKnNH4P9x/nFupzk0eoFjTURUp+GQBLoyg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000003, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 在 2023/10/11 08:17, Sidhartha Kumar 写道: > On 10/9/23 8:03 PM, Peng Zhang wrote: >> Hi, >> >> 在 2023/10/10 04:16, Sidhartha Kumar 写道: >>> Preallocate maple nodes before call to mas_wr_store_entry(). If a new >>> node is not needed, go directly to mas_wr_store_entry(), otherwise >>> allocate the needed nodes and set the MA_STATE_PREALLOC flag. >>> >>> Signed-off-by: Sidhartha Kumar >>> --- >>>   lib/maple_tree.c | 22 +++++++++++++++++++--- >>>   1 file changed, 19 insertions(+), 3 deletions(-) >>> >>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c >>> index e239197a57fc..25ae66e585f4 100644 >>> --- a/lib/maple_tree.c >>> +++ b/lib/maple_tree.c >>> @@ -5478,17 +5478,33 @@ int mas_prealloc_calc(struct ma_wr_state *wr_mas) >>>   int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp) >>>   { >>>       MA_WR_STATE(wr_mas, mas, entry); >>> +    int request; >>>       mas_wr_store_setup(&wr_mas); >>> -    trace_ma_write(__func__, mas, 0, entry); >>> -retry: >>> +    wr_mas.content = mas_start(mas); >>> + >>> +    request = mas_prealloc_calc(&wr_mas); >> mas_wr_store_entry() does something similar to mas_prealloc_calc(). >> Now, making it do it twice would incur additional overhead. >> We encountered this issue while optimizing preallocation, but it >> hasn't been resolved yet. Previously, this problem only occurred >> when using mas_preallocate(). Now, this change would bring this >> impact to all write operations on maple tree. What do you think >> about it? >> > > After talking to Liam, I will have to implement the store type enum feature on the Maple Tree Work list so that mas_prealloc_calc() can start a partial walk and write that information to the enum. mas_wr_store_entry() can then read that enum to continue the walk that was already started rather than having to redo the whole walk. This could also be used in mas_preallocate(). Do you have any suggestions for the implementation of this enum? There is another scenario where this enum can be useful, as seen in the implementation of mas_replace_entry() in [1]. It is a faster alternative to mas_store(), but it is not safe. If we can determine through the enum while writing the maple tree that a faster write operation can be performed, it would be beneficial. Some performance improvements can also be observed in [1]. [1] https://lore.kernel.org/lkml/49f0181a-55a4-41aa-8596-877560c8b802@bytedance.com/ > > Thanks, > Sid > >> Thanks, >> Peng >>> +    if (!request) >>> +        goto store_entry; >>> + >>> +    mas_node_count_gfp(mas, request, gfp); >>> +    if (unlikely(mas_is_err(mas))) { >>> +        mas_set_alloc_req(mas, 0); >>> +        mas_destroy(mas); >>> +        mas_reset(mas); >>> +        return xa_err(mas->node); >>> +    } >>> +    mas->mas_flags |= MA_STATE_PREALLOC; >>> + >>> +store_entry: >>>       mas_wr_store_entry(&wr_mas); >>>       if (unlikely(mas_nomem(mas, gfp))) >>> -        goto retry; >>> +        goto store_entry; >>>       if (unlikely(mas_is_err(mas))) >>>           return xa_err(mas->node); >>> +    trace_ma_write(__func__, mas, 0, entry); >>>       return 0; >>>   } >>>   EXPORT_SYMBOL_GPL(mas_store_gfp); >> > >