From patchwork Wed Aug 14 16:19:36 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13763694 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 7DA5BC52D7B for ; Wed, 14 Aug 2024 16:20:05 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 1F74F6B007B; Wed, 14 Aug 2024 12:20:05 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 1A70F6B0083; Wed, 14 Aug 2024 12:20:05 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 06EE46B0088; Wed, 14 Aug 2024 12:20:04 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id DD0CD6B007B for ; Wed, 14 Aug 2024 12:20:04 -0400 (EDT) Received: from smtpin02.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 0E07A121284 for ; Wed, 14 Aug 2024 16:20:04 +0000 (UTC) X-FDA: 82451362728.02.000040C Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf04.hostedemail.com (Postfix) with ESMTP id CAFB240023 for ; Wed, 14 Aug 2024 16:20:01 +0000 (UTC) Authentication-Results: imf04.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=UOpT1u7X; spf=pass (imf04.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1723652330; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=QE3jLMhbqm5q5B6AQVQeAXFLzswsHx3Oigu5M+migRk=; b=EPOUHlp7yuQgdefzPStfE2MEjwzRsgwfvYv3Ow7up/s8ceIWWlXV0Zgg+ThCojbNEImftI PtzTOjxqnbp8RFTnsVgOSPSk7TxvnW92BCtDZyjvZdBO49AxnE7L3aAqSTN/POXF/YEIAw Vfas+SZ6TpR0UMYR/EHT+nkqlg+Fxe0= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1723652330; a=rsa-sha256; cv=none; b=YgrsaeQvc6qzzpwFXJrfhCscTKTbnDQp3TgYRMaMKJEc0+JFbE5AvW6nZGY8e9EH2sRfCj n8qJYGuCI81UiZcT2IjNGPk51x1ONsPVQ62eawyzoGU9EDOuahIMJACwzeQmsx/NkyDgME 68HVBUR5mAbjRqzqBmGH90MPPQ8/4uI= ARC-Authentication-Results: i=1; imf04.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=UOpT1u7X; spf=pass (imf04.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com Received: from pps.filterd (m0246629.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 47EBtaej007052; Wed, 14 Aug 2024 16:19:56 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h= from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; s=corp-2023-11-20; bh=Q E3jLMhbqm5q5B6AQVQeAXFLzswsHx3Oigu5M+migRk=; b=UOpT1u7XABBNy9u6n 11Ws01wlN2+kvSwhXk28LE/xqi+hBvd3YJs++RDwwG1LZjkX63Zvl0IApuP+Qs6E jGRmFGuqNKC+iIJWLp/j8A6KrqaMOXM50qwHCZueMqdV/U3KXeGrdu5yDsCWluqq esVO9bB++EfwfM48H4dSExTQG3OtvtlZAPKp3t3UfAtXZlJqQcuJbxcEFmQP9+vO gTI/MVWKyKB5CDk5ui/kXKq0sXeckur0B/0Sg0WEMau4+YUrto4GE1VSD1Ea6dun DQMGiNqHRTLj5L3vn9dVYuu+TDmUx2ku8Z6HlitF+JE9ZZ1+PL3mpCqk6+kBFvS/ OfUjA== Received: from iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta02.appoci.oracle.com [147.154.18.20]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 40x0398m0j-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 14 Aug 2024 16:19:56 +0000 (GMT) Received: from pps.filterd (iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (8.17.1.19/8.17.1.19) with ESMTP id 47EGCmUe020856; Wed, 14 Aug 2024 16:19:55 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 40wxngn7pu-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 14 Aug 2024 16:19:55 +0000 Received: from iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 47EGIvCE035951; Wed, 14 Aug 2024 16:19:54 GMT Received: from sidkumar-mac.us.oracle.com (dhcp-10-65-174-212.vpn.oracle.com [10.65.174.212]) by iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 40wxngn7gt-10; Wed, 14 Aug 2024 16:19:54 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, willy@infradead.org, surenb@google.com, Sidhartha Kumar , "Liam R. Howlett" Subject: [PATCH v4 09/17] maple_tree: use store type in mas_wr_store_entry() Date: Wed, 14 Aug 2024 12:19:36 -0400 Message-ID: <20240814161944.55347-10-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.46.0 In-Reply-To: <20240814161944.55347-1-sidhartha.kumar@oracle.com> References: <20240814161944.55347-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1039,Hydra:6.0.680,FMLib:17.12.28.16 definitions=2024-08-14_12,2024-08-13_02,2024-05-17_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 adultscore=0 mlxscore=0 bulkscore=0 phishscore=0 malwarescore=0 suspectscore=0 spamscore=0 mlxlogscore=999 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2407110000 definitions=main-2408140111 X-Proofpoint-ORIG-GUID: bg50TrhVVWz8g9rwKKayfyCa375nXiqW X-Proofpoint-GUID: bg50TrhVVWz8g9rwKKayfyCa375nXiqW X-Rspam-User: X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: CAFB240023 X-Stat-Signature: pnwsr4cfoai9guqtspxo9dzc1c5fkcs8 X-HE-Tag: 1723652401-741105 X-HE-Meta: U2FsdGVkX1+4svopUzyY/cBlUjY9dTcqG/4gyYWvYpIVbtU/vyKMZ9/ZKonEr6VkObWBBOUkxXGoL54zrDk4rQCpQoOPMedOtseaOpssPW/U7IOpPWEPxfyOVABtGc7VIjGwGlCauxN8LZaT54HeOw5GZsyYIv6RRyo2/mBB371/TVpY7GQg/98iZ5RN17pc75jqrotseuCYv8udgrgB9dbP/oRl1YZQKllMdNoTbJG0B1f0ZSbUg8JSLBz6iGv3JG/X8FSz2JtsYwbjallQ29J+2G9IhXciUlU7nKwd1MhaY9thYvgLHcNV57b6hyrI7CF7i5Ew0J97YtSem85iChiQtmUgWvk6DbsVcsgOPYrD2jCuvIhK9L5Dnaj1bjeuqW+B1zgeQcL9l0PY9Xe+mYkPrqMUkI1op6bgDkRGLOjqLvPBoyjp+1uj/elFQsncB7HSDiHVTmLPsRPhWhElu3DuP8SA5tANIV9fWCHvvaLkmPF6OFDKnUfTqFGqKEFPO6qX0tAgrevO1powGYUAT5VmiSlGF4QmMS2t0VL6xBKHV7J1Aj1k1MMWudxS9mXMmPcjB9aP/xmgYJfkJL3ZadsrSufKW0yf4Tg9mV50j3RvQyocumQ8+FY+SdIbVEh1nJBqcFRBlmruuEioUvanNHVBKGOzbGEvFp5F2WhhTGjjWJEXO+tfdnMROHMMmCqjjb40+zu19Sk7sfOGnYARG0cAjECNzkClTQFP2KHolkWIY1uRB3zttflUn1qLc12I0hVyeso+i04YA33rrWNgCiOJOdZosh4FrBDpbaltUwZZL39VrHK39TZu9v9x6TLRdfev416eJU//defoPmdLU/v5Ea2xrgC/fVPdvdyumjSGPMv8ixqo5YMiFBViHiDWbGR3rYhzDcTtuF3bEKddlekolCCeA2dJPy3vggjjvu7jMuaKPYK+qCWyx1QLrgOw9Ifwmx2YUFsy82qTN9p l0TJ8dSv jaVca6sEYmlJL766gs91U6b19tFfMwIBsnF6foFYONiQ/+SrFI8Ze5iYcJ7OP+SHW9HyLTH39BrejjD4zLA33g8ltMGuEpj77u39NueNfuwtgJlPqDLl7am3KnTfBmalFxvGQN6lwyy6QixL2JIOpGmBnqXlaqXc701i92b+KInWfBPIPQz+LaT+nX09DV5BQ9cqZ3u8wnBrZ2zFpm7I44JKg3TpmhDOt9dPwXEmpI82HULYO++cdWGy2DnRv8+15QUPkoMPI+RaVs+o= 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: List-Subscribe: List-Unsubscribe: When storing an entry, we can read the store type that was set from a previous partial walk of the tree. Now that the type of store is known, select the correct write helper function to use to complete the store. Also noinline mas_wr_spanning_store() to limit stack frame usage in mas_wr_store_entry() as it allocates a maple_big_node on the stack. Reviewed-by: Liam R. Howlett Signed-off-by: Sidhartha Kumar --- lib/maple_tree.c | 90 ++++++++++++++++++++++++++++-------------------- 1 file changed, 52 insertions(+), 38 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index a1689fc6227b..2242e07a46dc 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3780,7 +3780,7 @@ static inline int mas_new_root(struct ma_state *mas, void *entry) * * Return: 0 on error, positive on success. */ -static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas) +static noinline int mas_wr_spanning_store(struct ma_wr_state *wr_mas) { struct maple_subtree_state mast; struct maple_big_node b_node; @@ -4206,43 +4206,62 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas) static inline void mas_wr_store_entry(struct ma_wr_state *wr_mas) { struct ma_state *mas = wr_mas->mas; + unsigned char new_end = mas_wr_new_end(wr_mas); - wr_mas->content = mas_start(mas); - if (mas_is_none(mas) || mas_is_ptr(mas)) { - mas_store_root(mas, wr_mas->entry); + switch (mas->store_type) { + case wr_invalid: + MT_BUG_ON(mas->tree, 1); return; - } - - if (unlikely(!mas_wr_walk(wr_mas))) { + case wr_new_root: + mas_new_root(mas, wr_mas->entry); + break; + case wr_store_root: + mas_store_root(mas, wr_mas->entry); + break; + case wr_exact_fit: + rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry); + if (!!wr_mas->entry ^ !!wr_mas->content) + mas_update_gap(mas); + break; + case wr_append: + mas_wr_append(wr_mas, new_end); + break; + case wr_slot_store: + mas_wr_slot_store(wr_mas); + break; + case wr_node_store: + mas_wr_node_store(wr_mas, new_end); + break; + case wr_spanning_store: mas_wr_spanning_store(wr_mas); - return; + break; + case wr_split_store: + case wr_rebalance: + mas_wr_bnode(wr_mas); + break; } - /* At this point, we are at the leaf node that needs to be altered. */ - mas_wr_end_piv(wr_mas); - /* New root for a single pointer */ - if (unlikely(!mas->index && mas->last == ULONG_MAX)) - mas_new_root(mas, wr_mas->entry); - else - mas_wr_modify(wr_mas); + return; } -static void mas_wr_store_setup(struct ma_wr_state *wr_mas) +static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas) { - if (!mas_is_active(wr_mas->mas)) { - if (mas_is_start(wr_mas->mas)) - return; + struct ma_state *mas = wr_mas->mas; + + if (!mas_is_active(mas)) { + if (mas_is_start(mas)) + goto set_content; - if (unlikely(mas_is_paused(wr_mas->mas))) + if (unlikely(mas_is_paused(mas))) goto reset; - if (unlikely(mas_is_none(wr_mas->mas))) + if (unlikely(mas_is_none(mas))) goto reset; - if (unlikely(mas_is_overflow(wr_mas->mas))) + if (unlikely(mas_is_overflow(mas))) goto reset; - if (unlikely(mas_is_underflow(wr_mas->mas))) + if (unlikely(mas_is_underflow(mas))) goto reset; } @@ -4251,27 +4270,20 @@ static void mas_wr_store_setup(struct ma_wr_state *wr_mas) * writes within this node. This is to stop partial walks in * mas_prealloc() from being reset. */ - if (wr_mas->mas->last > wr_mas->mas->max) + if (mas->last > mas->max) goto reset; if (wr_mas->entry) - return; + goto set_content; - if (mte_is_leaf(wr_mas->mas->node) && - wr_mas->mas->last == wr_mas->mas->max) + if (mte_is_leaf(mas->node) && mas->last == mas->max) goto reset; - return; + goto set_content; reset: - mas_reset(wr_mas->mas); -} - -static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas) -{ - struct ma_state *mas = wr_mas->mas; - - mas_wr_store_setup(wr_mas); + mas_reset(mas); +set_content: wr_mas->content = mas_start(mas); } @@ -5582,7 +5594,8 @@ void *mas_store(struct ma_state *mas, void *entry) * want to examine what happens if a single store operation was to * overwrite multiple entries within a self-balancing B-Tree. */ - mas_wr_store_setup(&wr_mas); + mas_wr_prealloc_setup(&wr_mas); + mas_wr_store_type(&wr_mas); mas_wr_store_entry(&wr_mas); return wr_mas.content; } @@ -5634,7 +5647,8 @@ void mas_store_prealloc(struct ma_state *mas, void *entry) { MA_WR_STATE(wr_mas, mas, entry); - mas_wr_store_setup(&wr_mas); + mas_wr_prealloc_setup(&wr_mas); + mas_wr_store_type(&wr_mas); trace_ma_write(__func__, mas, 0, entry); mas_wr_store_entry(&wr_mas); MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas));