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 39815EB64DC for ; Sun, 25 Jun 2023 03:28:16 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id C43F68D0002; Sat, 24 Jun 2023 23:28:15 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id BF3358D0001; Sat, 24 Jun 2023 23:28:15 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id ABB468D0002; Sat, 24 Jun 2023 23:28:15 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 9E2598D0001 for ; Sat, 24 Jun 2023 23:28:15 -0400 (EDT) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 650C214021A for ; Sun, 25 Jun 2023 03:28:15 +0000 (UTC) X-FDA: 80939836950.01.6A8E82A Received: from mail-pg1-f194.google.com (mail-pg1-f194.google.com [209.85.215.194]) by imf11.hostedemail.com (Postfix) with ESMTP id 6F12B40008 for ; Sun, 25 Jun 2023 03:28:12 +0000 (UTC) Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=gmail.com header.s=20221208 header.b="RL4mR2J/"; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf11.hostedemail.com: domain of perlyzhang@gmail.com designates 209.85.215.194 as permitted sender) smtp.mailfrom=perlyzhang@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1687663692; 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=vXRtEpdmgfttImvo4Tlut0TWnE+Ckr8vokO7ZMeuBLM=; b=gfGqv7h+6KLrCRRFXUyXgCneS+l010fNmFhDDlJcHMXFHE4zFZ4X1Ivhj2IOyZS4c3ielI at8TgBNPdM/Y0rE995tA5WI1YJxSZuIhBYTXSFuiE2SQJ6SiSMCiwy9yVM2HY16CiYpv1i sVwsOrKaCIAHp4s1BwRZXQ4f6Bo78QI= ARC-Authentication-Results: i=1; imf11.hostedemail.com; dkim=pass header.d=gmail.com header.s=20221208 header.b="RL4mR2J/"; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf11.hostedemail.com: domain of perlyzhang@gmail.com designates 209.85.215.194 as permitted sender) smtp.mailfrom=perlyzhang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1687663692; a=rsa-sha256; cv=none; b=jg2HbNZdTVI0HGLkcLdOV2/oXZr3mZg9OpTuV+v/UxM8suBhK2tSElxtNtxl2BU6ZedaM2 hbtoO9Zixy6OqUZSi6xZFE/HFPbI4dVSg+kqoL2V3KBBA20OYLVfYu/bPt3+Rdn9+zZBMU 0pNW8BPQ/DpginqrrOjHYI8eUGv1ePw= Received: by mail-pg1-f194.google.com with SMTP id 41be03b00d2f7-53fbf2c42bfso1800948a12.3 for ; Sat, 24 Jun 2023 20:28:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1687663691; x=1690255691; 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=vXRtEpdmgfttImvo4Tlut0TWnE+Ckr8vokO7ZMeuBLM=; b=RL4mR2J/CzoGZKeE5gS1E48Mle26Ex9HrMTY30RKImfVczJiSZ9qABlLaqZwxcZCr6 d/+IRXua66++r90KhY9PzQf9AEoBuMes9k2qNIpIMYF38C8/V9HmvKUvWkxuguz86JIg HCotmGZq8Ks6cV54D+erhoM1XnheNsFZzpsqbs/bTd2B927jR7wnEuWW/reKzAuEqEyT 51SIKJ/qTxy+JO4Y+5tYztXZrBhyBWI+F8EwepH+MyB5zRuhs7DXiZrRux3dLpmMGk7p Y5GnLuNmIhHNVULvkfhBy3mcLZeBIxKQ8CnBJxaoHdNX2aohN9MZcKhYBe3Y6R9NSOnE /SOA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1687663691; x=1690255691; 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=vXRtEpdmgfttImvo4Tlut0TWnE+Ckr8vokO7ZMeuBLM=; b=OlrtXEshuncV8Ahzj58SzB+n9p1aVS3Vo1DXdct83sUWOoBZQZZzzmFmsS9wi+TZVR bhWZTg43wkfv10Gnv6axr5e7fIpj4+kW3qTgwnp77Xw4BGCChb8jSvhSTecCSQx/qFdd jH9N4qfw8Qwz2dtlOT2OjbgcXkP5yBnNwHxAbkNp+d/nLyxEsLtATpCFc+gcNNdwTs6u j9V9HD5dYgUqu1HNz+cIiGlUIM62iia1uLqktvQCRJM8Ii6HFHqXKB3BSdsyC5iduFQj 7YuvL36GGHKzVzsnn7HbB6wu852yE3jIFDgmrw/qqzbvx/vSOMZAjSjCYSJ8YmkRM8nE u4GA== X-Gm-Message-State: AC+VfDzQWbfzBBbCeOINXXLDttG4uC6oN/xb+FXOmqKw7FwJkUaAgI/H UJcFoSreXHNMiE8kHB1IgL0= X-Google-Smtp-Source: ACHHUZ5ZuhVDIpm1fi1amylnvldyYN8z0ivw9cfv9vm/U4wGZ63/8kdhzR6H7eYNJ1ys7s1tVWWk2w== X-Received: by 2002:a05:6a20:6a23:b0:117:1ffb:a14 with SMTP id p35-20020a056a206a2300b001171ffb0a14mr33978752pzk.13.1687663690919; Sat, 24 Jun 2023 20:28:10 -0700 (PDT) Received: from [10.255.209.141] ([139.177.225.255]) by smtp.gmail.com with ESMTPSA id x16-20020a62fb10000000b0066875f17266sm1633091pfm.135.2023.06.24.20.28.07 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sat, 24 Jun 2023 20:28:10 -0700 (PDT) Message-ID: Date: Sun, 25 Jun 2023 11:28:04 +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 References: <20230612203953.2093911-1-Liam.Howlett@oracle.com> <20230612203953.2093911-15-Liam.Howlett@oracle.com> <26d8fbcf-d34f-0a79-9d91-8c60e66f7341@redhat.com> From: Peng Zhang In-Reply-To: <26d8fbcf-d34f-0a79-9d91-8c60e66f7341@redhat.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 6F12B40008 X-Rspam-User: X-Rspamd-Server: rspam05 X-Stat-Signature: jq3mj1y3d7rndjickxxh6j9dd8k8h5ne X-HE-Tag: 1687663692-97969 X-HE-Meta: U2FsdGVkX1+I9ikZQkwc7eCOFozQY4JldDh90JyIWOthyYd2xS+cLCSY1soWBKgxOnzNobq/9z8NmS0v5THKQB6MBCklVqkBbM6x/IZHyWdz+3vqBTC2b6BTjG1N+f2L5iuBZBMB1JnSkQVA6NpS3xlZPRfar719xkexkjrxRZC+iRGELi9E73qYdLGhCPQFUdsn5so3urJXuH95ybpH5QqreElqbqfkLxy0r+u11wkQ8jNveuUg1TnCIhn71xd5jKKLe6tFiBOn1SmCxFSf1VP8Sx1bwe08yG4Bv9M0bDxKBckOj+Tw7DizmF+b2ZIXzDu++jfbAwdY+9WMWm3b7o6h+RXNNL3/MwueXsKMj/g8FIjVShClq7Sq8SZkary1iyXyS0F98GAxU/OzpDvjIKQEOHoUrcdAqV3Mu1Zkem6jUb8/HBnhPI9G8nerzFq+/mSpVty+Ai1lMGRGrcCrq7AXwsnuypLUFUEohj9lA5OuvTQSVU3t0wqtNUXIVDf6w1IMZX/tuiGVPrLmpL/oXamEZEaLTpHPmr9AlYjGKy6Ee7290Ryr7YiTxw1UnlAiuhNNFWdBmQqhZBnbVH9dH60Cjh73i4TvZc2RmMTaYvTkFpMfgEISbpCci1DTiwfDBSlNjAmCRQ08PHR5Y/E8v78F9BZegH1+1neieirLqkguzz8OX7bkYGYSfZymJhnxHTIISRQJal/ofCbpit7r07+dQ9w5Fbg2QDQPJNqJB5q8HTV9RwoX8CMMfefDyGyv9+cYhEQCmRb8+4AsQwmTuVJz008TAnR9TloN6mnOHGz8xuH3/p2aQZPP8GOa6jX2W1SgLRi17UcIWzWqVLwXoteo988ar2ey62iUHtzINbhFGSaLAIBUAdYabZfXfNz68k+xzhn2SE02xuFp3EUFWv0yjXi7tcPMRi1Jy1HO67JRzbwAIsEP5vW3ANX3c4j9bQzoby9mcm1idiZdV7B GMuWISRJ cHRW4+VtQ9OTQOq5Vygqr/+XYiY5sU9+Si/G1pKVhz46j3rin7zw3H78R8kXwrsg2vX62O7fTtD1Gi9YvoIXSvmpM+bzB3widaR8EMrGcTTgi4rpQYvFnSQQZHdYzVhz2U2ZXvAXkBrWDV7zKfMNUOZBIowcMJzFSyAdt4gkJqyaORgORAZTdtGaMPRUOyZFfhhabYnoU3VY2lX335fFFnb9+0J5khBJYLS0n5TRQ+eRIl3v2V/GledinNKBOqx0FV4rabHfZz8xR5RtQeblrDCZuPfJZAaGZKOZGZ6TNwz0WLxknbRicjm0IYetq4r6OHSLm83bYw1oxpqsdNuPCP7IoWL0c+yBTMmPlcBcaxvqEXNZGvPxERRC9XFYDGZMNpVlR9SErQm0XC6Yy7jj9LZv7e0Z3bwNvGOsYwcSKMv83FAcVxbbeGZCUpfvbzMuJef1C0qQGCXPjNfypETVmtJegSqE801l56ialmIRSiTy/Of/snCXB1DYglQHeOnXvgUfpFqUTImVK7vvoRft7BGb7pbY3aF1ESt17 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/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. 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; > >