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 E1006EB64DC for ; Mon, 26 Jun 2023 14:10:32 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 36B408D0005; Mon, 26 Jun 2023 10:10:32 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 31A078D0001; Mon, 26 Jun 2023 10:10:32 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1E1C38D0005; Mon, 26 Jun 2023 10:10:32 -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 0BA6B8D0001 for ; Mon, 26 Jun 2023 10:10:32 -0400 (EDT) Received: from smtpin13.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id B1B75A02BC for ; Mon, 26 Jun 2023 14:10:31 +0000 (UTC) X-FDA: 80945084262.13.384CEF3 Received: from mail-pl1-f173.google.com (mail-pl1-f173.google.com [209.85.214.173]) by imf21.hostedemail.com (Postfix) with ESMTP id 7AEE31C02A3 for ; Mon, 26 Jun 2023 14:08:11 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=dzGKLkbv; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf21.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.173 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=1687788492; 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=lBN8blGYXvnxlXBIVOSTpTlppcCRsXOaHTKDN6AwyzQ=; b=GmboECkj+TyVpri6bjxK/e/SzJtCKQHm3icZRgLW0OyjixzRtkdAss0CTsB1KmWu69mnPp H9cUCAziN8HsBEmB3onWMGqwmlTzrhkk7qB4eBr+J6QTjJk3p9+l7xnnlmbsstK8XDP1xR 9wMOLFmO1fHw+FRNBuymg4FwMqoco98= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=dzGKLkbv; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf21.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.173 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1687788492; a=rsa-sha256; cv=none; b=4QWg9c3gGHzGt7Dfd5tIvw2ypA69SLak7+UHf9tDduB75roENIp4J6TgRNxgft61Squwz0 5Ki492AAPpbA1WUC9JMLT0xs2K/aFa1a3TXUcRxUL1z+64RLyIIeg6xkOAPS+nY2ThYoIy HqJNTtBArKhUpYHmIosekwz66bYB4dw= Received: by mail-pl1-f173.google.com with SMTP id d9443c01a7336-1b7fb02edfaso11657495ad.3 for ; Mon, 26 Jun 2023 07:08:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1687788490; x=1690380490; 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=lBN8blGYXvnxlXBIVOSTpTlppcCRsXOaHTKDN6AwyzQ=; b=dzGKLkbvt/18pINM4BAdCzeMA7heFFExgGSN5O/dVJ4hZpl6Neb9d3mM1ZWu3kJCz9 6lALUwhHQy62gBR9gPNCQ2PcLVBDAIwE6Z7CSAtAoLIo/k8Ls5lbe8/Rg+60+Yb5jYpn Ija4O7Ne1kh4yJltZD7Wjoj3FNQhA6PlnP5k1FtN9pSTf0aIiw7Jh4htjbWDeBLklCvf Rp2UdeOuNq3QdtyfbEi0LJledSlFv18XIncFskMRyjm/ymT1T/zSFXUfQ5H9b0/qwbX5 IEsNWN5iGQvGS331KgkQCwUJgWU91bjwqo+Gr7yLxRgBCMTn00H2hk4pTAoxgke8hmNA vNqg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1687788490; x=1690380490; 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=lBN8blGYXvnxlXBIVOSTpTlppcCRsXOaHTKDN6AwyzQ=; b=VYUP+BqRqalv3/USX/kHCAyoP/AZ2zQGpu9oXZIIcLcq4enE0iyn1dC6BFb6qF/rKC Gf7sTi5Dnegx1/lK3Btqe0/5fFuFCMks9glyo5IJ+cwEbMZE4K8a1HJprtk18qtmEoVf /hFTzwNjcB/zlJInCoa2ME/H2HKAGFL2GbxvaKGgKcm0Q0jGfG+q2GxClHiij1L0NdrA lVXfr+3EFBS6w96IShB14KidkP8lHBAV1rssSPmyIfytzkR8NXs9WQZbZJP0qexSF6BY H2ay1EbYUq0GegrazoRAR8ha/jM6e+6RNecFgA4uPvWftkukaRoTXJ1sFY5A9zyym7n3 5+mQ== X-Gm-Message-State: AC+VfDzBBWPAxHEp5OgWAY085AyDJcds7spq+rOxAe0bS1QCrzhFYUF5 nIb/3CR02Izyvg84GtF8Up07bQ== X-Google-Smtp-Source: ACHHUZ6EWq0b7ssc5mx6VHgRCMYEBCOBoTqqG2cF8Q1iJSu7eIvWnLrwfscQt8+XTTuNf0iaVeF22A== X-Received: by 2002:a17:902:c10c:b0:1b5:4709:fa0e with SMTP id 12-20020a170902c10c00b001b54709fa0emr7199079pli.10.1687788489653; Mon, 26 Jun 2023 07:08:09 -0700 (PDT) Received: from [10.255.209.141] ([139.177.225.255]) by smtp.gmail.com with ESMTPSA id e18-20020a17090301d200b001b682336f83sm4259302plh.42.2023.06.26.07.08.05 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 26 Jun 2023 07:08:09 -0700 (PDT) Message-ID: Date: Mon, 26 Jun 2023 22:08:03 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.11.2 Subject: Re: [PATCH v2 14/16] maple_tree: Refine mas_preallocate() node calculations To: Danilo Krummrich Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, Andrew Morton , "Liam R. Howlett" , linux-kernel@vger.kernel.org, Peng Zhang , David Airlie , Boris Brezillon , Matthew Wilcox References: <20230612203953.2093911-1-Liam.Howlett@oracle.com> <20230612203953.2093911-15-Liam.Howlett@oracle.com> <26d8fbcf-d34f-0a79-9d91-8c60e66f7341@redhat.com> <43ce08db-210a-fec8-51b4-351625b3cdfb@redhat.com> From: Peng Zhang In-Reply-To: <43ce08db-210a-fec8-51b4-351625b3cdfb@redhat.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 7AEE31C02A3 X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: xrpmk41c4tw6hquu8b9htyje6p6btj8g X-HE-Tag: 1687788491-59964 X-HE-Meta: U2FsdGVkX18SoHUXGhssKonLV34uMRCvBPcplfsJG0RnQx4zSVc0H12L6MJ3AjrVY1zcVaGiQvoSIISnWNnUQ5Le34aGIv7MAPun3XvdaOh+m81iG/V0BnnycnjraHDtBsFuQOxKvifI9f5EamjRZyZH1gb3fVk0qw4+hv1G4D56jyxPh7LUGa96E7tSyyBbeD4zg97HJIaCWWAi69AKinfePBnu/NmfWJAswz1QC8oKfoQJPs9+PSUgVs5LsnhepJ1pi6fFuPRVagbTH5AQebvctmNtD3hSZoqq39fV13HPwspTBVS//7r3c3HVF/oCuixoqNDtFc+FMA+BLAAU7DQP/jXAOvFS1VtVjSIqDmGJxTWV4+Hsd9UCzlnAiMtwZ5Biz3biCOr2p7A1y+H7kFCivNv/xtBVKABZPCe+XZg0uC8p4uu7Ctplbx26cPNhoR6FiSnRqv85Iciq6ktTDpi7Sz+slHUKDa3bQAtTi8hbP7h0TGX04DYExDeCfzwwOTW+Hf7hAHnfb0QA2lR2qyzHp6HMv3ypcA87SwYFp4+WYJ6p++kW9BjahAmrGk6yhzzkxou7BdvpPzNULYNI99fwCiSNrBoG7Gi4xOxstDxh2ywoGNEn/2OT7A4ys4wZYo/a7FLdq6+SWJoXoKUsfpk2AoowjTLghGODlOLckSPJH+YbzXfxJnP3TZRCcvyzyTcrcDSMOh90reH2ri4tRyEuF6OkRqAj3OgBD95N/sp/YCJ+qi4T3l7nzc8YIUlLhJt6Sj+r0huAe98OqQI4LaQlJOlo/UStwj0ScpyE35g+/DYWZlGHoxiZ9YJS7rgnhsyUQxqn0bkK0e5syU4rGit03vYcObki4XBZqWvMzX+eHX0GW3se6rMzv1YfdMpHHJHmoAzwKuLbw0Rj1lAk+iT7/L5YPH562siCuou27dmPpCx9b5jdqcIVTSXBN9cej0uTS5IiJWFvqem4SaE rjONW2ES bZ9XH+aD+tERp3ZAGy19k+tANzlp1KppXTNDEBQU79rR6ZbTzfVFq4pX8FxOOmtW+9nefnujgdQ9z9mrr1DGD+jSu7jZRv1FeYABuY/XonGR3n3kXQAtSv/3nlci2rBffw//zpHOyuZB4x0yEXgKVzZIsyaJ0aJwgOQcm6pyKQlToG9CUcm/pn7xrWvZNoCZ9hQB5j5LqdTu9ET5OiCuNTNNx7howxsOc4eWqqG1YU2bgRlms9u8PU7NyGSDL54ss6JqzLUOYwNaWhcRKKpHd1h6760vxpR0+w8AFn33I9R7hPvYcOzR2TAHPGtlx+IGI5bNvvj5//CJsZHGAQZcjENF4ob+b4huep4PjFUQscq94th22dlVTGm/lybrwCTHUov5Gzr2p4B4Mq87VA402nBM1Cyx7eVO7dUbJuTLNwot6JNDxfodyEEDXGjG+cU1DglPl+cEN+6VO8jv33Q8cDhVpFXYVkqFH6zG+7NGuFst77fnToriIuodRY5v3v647W8FV7OvNUznVGDs= 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: 在 2023/6/26 08:38, Danilo Krummrich 写道: > Hi Peng, > > On 6/25/23 05:28, Peng Zhang wrote: >> >> >> 在 2023/6/23 00:41, Danilo Krummrich 写道: >>> 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)? >> Hi Danilo, >> >> Your understanding seems incorrect. Even with previously unoptimized >> mas_preallocate(), the maple tree cannot be modified between calls to >> mas_preallocate() and mas_store_prealloc(). The calculation of the >> number of pre-allocated nodes depends on the structure of the maple >> tree. In the unoptimized mas_preallocate(), it depends on the height of >> the tree. If the maple tree is modified before mas_store_prealloc() and >> the height of the tree changes, the number of pre-allocated nodes is >> inaccurate. > > Thanks for pointing this out! > > First of all, it's probably fair to say "naive me", it totally makes > sense the tree height is needed - it's a b-tree. > > On the other hand, unless I miss something (and if so, please let me > know), something is bogus with the API then. > > While the documentation of the Advanced API of the maple tree explicitly > claims that the user of the API is responsible for locking, this should > be limited to the bounds set by the maple tree implementation. Which > means, the user must decide for either the internal (spin-) lock or an > external lock (which possibly goes away in the future) and acquire and > release it according to the rules maple tree enforces through lockdep > checks. > > Let's say one picks the internal lock. How is one supposed to ensure the > tree isn't modified using the internal lock with mas_preallocate()? > > Besides that, I think the documentation should definitely mention this > limitation and give some guidance for the locking. Yes, the documentation of maple tree is not detailed and complete. > > Currently, from an API perspective, I can't see how anyone not familiar > with the implementation details would be able to recognize this limitation. > > In terms of the GPUVA manager, unfortunately, it seems like I need to > drop the maple tree and go back to using a rb-tree, since it seems there > is no sane way doing a worst-case pre-allocation that does not suffer > from this limitation. I also think preallocation may not be necessary, and I agree with what Matthew said. Preallocation should be used in some cases where preallocation has to be used. If preallocation is used, but the number of preallocated nodes is insufficient because the tree is modified midway, GFP_NOWAIT will be used for memory allocation during the tree modification process, and the user may not notice that more nodes are not from preallocation. > > - Danilo > >> >> Regards, >> Peng >> >>> >>> [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; >>> >>> >> >