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 45676C25B75 for ; Sat, 1 Jun 2024 02:55:57 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A1EDF6B007B; Fri, 31 May 2024 22:55:56 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 9CE866B0082; Fri, 31 May 2024 22:55:56 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 86F316B008C; Fri, 31 May 2024 22:55:56 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 6454F6B007B for ; Fri, 31 May 2024 22:55:56 -0400 (EDT) Received: from smtpin12.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id DFE4BA3640 for ; Sat, 1 Jun 2024 02:55:55 +0000 (UTC) X-FDA: 82180805070.12.C55B84E Received: from mail-oi1-f171.google.com (mail-oi1-f171.google.com [209.85.167.171]) by imf19.hostedemail.com (Postfix) with ESMTP id 347F31A000C for ; Sat, 1 Jun 2024 02:55:54 +0000 (UTC) Authentication-Results: imf19.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=iEBMTlxK; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf19.hostedemail.com: domain of rgbi3307@gmail.com designates 209.85.167.171 as permitted sender) smtp.mailfrom=rgbi3307@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1717210554; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:references:dkim-signature; bh=6cuT18JOZza/4e5QCGWHwOGAqlrdJNqLc1S/ZVkgtOY=; b=o+i5ae8CV13pt38rUxSmwxb1DsFuP8BIG3J7jOhRMUqVPK0xuNndBF7Q9RFr/h15D9RqLO kPu7W1456eePUYpbs0rmdbxhvEdJSdVyKu8wes/SWPh+x8o2tf1YVWHMc67wFNbAv6EHv0 LAbDzDmskPVF7YmcpXeLqeIcLrZo8g8= ARC-Authentication-Results: i=1; imf19.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=iEBMTlxK; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf19.hostedemail.com: domain of rgbi3307@gmail.com designates 209.85.167.171 as permitted sender) smtp.mailfrom=rgbi3307@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1717210554; a=rsa-sha256; cv=none; b=MqcC51ScEsqMyS6bWa5dY0PoMDf7D56XU0dtJQf6t/EqrqR5OauGhA04/JEUnC27hJ3fav xXciLGcB7gYfQTRSAT6kiYV78g3dw10gHqUqLFIsCrAEZ/wKAeuwRw7qsXZrFtPt6hhrrd V0bBSph4lLFD75XyiGDrGaK1aeB+OdE= Received: by mail-oi1-f171.google.com with SMTP id 5614622812f47-3d1d78b7418so1575754b6e.1 for ; Fri, 31 May 2024 19:55:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1717210553; x=1717815353; darn=kvack.org; h=message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=6cuT18JOZza/4e5QCGWHwOGAqlrdJNqLc1S/ZVkgtOY=; b=iEBMTlxKWKlEge66DoztwX9M/hq2uQ3AgQ9iqiQJNifEibTUv6GwdLBl8Y4FysnfJQ xWkgnNetcgOknSyW1u520gAuxE9nQio+ofhA6yPI2HMwoZlSYvrj27uRN3vHPvhapQG4 +tNpk6sSx6J/xyIfw0lSIp1FEglEtCuRo3Q18nP10Vfw+oCb5BjbWuDtgLQImJKWhW3n zPncxsl0Tzb4/0vBL0jgJvki6xm3MDxFfd7JghGHXuPywiaADwkNRHQBkKuV4sltkcjE PRmhpHQmL5jEuJi8UhHyf9voYYdSESTj49IV4/4M72PgEJ7iZ9/5SnGsiD36aQqJW6o3 mBaw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717210553; x=1717815353; h=message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=6cuT18JOZza/4e5QCGWHwOGAqlrdJNqLc1S/ZVkgtOY=; b=Ux8sDaYmyzbd9PiWofEVpusvFJ5+7bgmW2QyOhBgSG4qsuXxc+6UGtSiUA8F84ncJ9 Ogc5mb4VuGQAzbYrF6ii7pMcLmy32xcv4Lusk4L1i6sw227BiZZOI7FFTzbfs7Dr3VW0 Cm4RBELGutGTzEvHkcuIy5lf/BiK9FsBlUHoBjbCWLqGzxRf3mBRgeEkejr7dz/kADIy FQR+18l280P+xS1VgUu6CSD4DcugcbA5M+rZ24/A8uO/KuXR5z7Cn1QqKVF2mNzp+RRS 19+t8gCoafKBFtdnDlZLrxj9Q74t0wAzvxqLPqTtstJwKoFg02Iibtp/MG21gOw8Wzh5 CxIA== X-Forwarded-Encrypted: i=1; AJvYcCWaxJCZJLpaFFHYQH0V+Or/jtAqHtR0eHOju+mLXbm5MzetZzMQX5DJcNOK2VAnnT/G7rhewXTZoGZeKFfM1tAD1nI= X-Gm-Message-State: AOJu0YyO/9G1jeFbd1mMV6UakUeA1ANewGJPvGnGX4rXSDG/Y3HyYJ6w o2eUhjoBu+co5AzZP9Ji1oxpZiiVJQsWnn6lGaqu0SlaMdq7WUsB X-Google-Smtp-Source: AGHT+IFrOEgn2sLNc0d61WpIO9wZGaBK1cdMn0rPjsa2MBX+KCqZ7pFkGa07RP4vK6dSCwRJrb8JBg== X-Received: by 2002:a05:6808:b06:b0:3c8:4dcb:3d34 with SMTP id 5614622812f47-3d1e347668amr3484293b6e.7.1717210553073; Fri, 31 May 2024 19:55:53 -0700 (PDT) Received: from localhost.localdomain ([180.69.210.41]) by smtp.googlemail.com with ESMTPSA id d2e1a72fcca58-70242b2effbsm2035817b3a.206.2024.05.31.19.55.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 31 May 2024 19:55:52 -0700 (PDT) From: Jung-JaeJoon X-Google-Original-From: Jung-JaeJoon To: "Liam R. Howlett" Cc: Jung-JaeJoon , maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: [PATCH] maple_tree: add mas_node_count() before going to slow_path in mas_wr_modify() Date: Sat, 1 Jun 2024 11:55:36 +0900 Message-Id: <20240601025536.25682-1-rgbi3307@naver.com> X-Mailer: git-send-email 2.17.1 X-Rspamd-Queue-Id: 347F31A000C X-Stat-Signature: 9g67pp3ipea1bs3kne8qop3p6fjoccwu X-Rspam-User: X-Rspamd-Server: rspam08 X-HE-Tag: 1717210554-666249 X-HE-Meta: U2FsdGVkX1+b/Dz0pZGuqeMn2ekqPHB12mX4vSSkW+2z37Ix6Kx6SI1mnop5BcwfdFZJRIuHMw68TakcecR3a0ekkFpnAy7Zo2Oma6OLNU+w3FsKnV23Lz787kBYpnbuSSyC/efHdi3ec88A1FOCB9vLWq+bflGjg0nrB/S3GXiOrZnkV79nv28gObp+v/TEpwyHVE4rzwV3etkJStqLuCBLJM0Rhy1tV+ht0al+82cgJHwtRTamEuPNfznoiSa07XmT1LaK4sILB5uS2JRNTp2N/lHAnv2dPj1c3EQvXPl7bj0B4IBJyd3irP+q9Z16AE7b9xKb2TopZXGnFMzW8FmfAhREXufBAr71TUZkmbF6yMkt8t8+NTlJ+byyUXcC6u2CyorRDTRow/y5E2YmhHYUO6qsBfbY9z58rAOse5olUatEQ+KCWIKCCk+yC5VTLc1j8KM9q44jjC58rScYieCy8pxdq2DHMjuDgwpjviQASCfheBX26muoGxPWsThggq5x4z9GoiZj9TObaMeYhDTkHBJZdHmsHXUhrrWdNrbvz8/nYTAd1lU31s3Kxp4Y/Go/jgLDXdemxjKa98j1A445DS6jWm3y/S6yjb+2LapT55szyCEkegh3zegJ/tpRhzBqquLi0zGQ+ULDDaWHkyUFolP3LoFifo6uV1rkYKHScXEkD9+Twi41zkHVi2vsuUgzKJkUGu8y5mjWXmrmoCATOdCSaPty6QarnbzWpU19yPDdLn3g4cN72Sd70tq2fzaydLg/Xpq+jR4OC6RQ5VDgTY9IEK0WrKt50+OdcHoF0V1onm/3zo0yP88F0wIluGM9oBFz3W3yNvAxo5akUQNEKoGYTg2Aw+0ozhac/YGd9q7Ce52veQ0rocc3ZFfzrurU3fQKFVLBLKCWcnIgCNO241T3T2ZInzg4Yi+iJzVd/cOifQj4o3viK31LwcLqUaXWk1O7/SgGtxXoE4p WsHEII2a 1U7Tq9bKEAQRqbiPOnr3+m+SRHhWuTOgmrNEbjM4O+lZUFwGOh1/3sQu5ngEcpIKC1QUddSTwfE95etWIvTIo8hbsgJC1hXY8N4nqaEs21WU3lYLJ2kgeu2GUYQE7kKV1MK8QciMZcMMXRgdq/syZZoT8nGI88T35qteivJXDu/Ue6HdkDApUsNbVBrT/PJatDzJcpI4fszz2GU69x4JWPEU11AMfGo4W5HAZJHaK5+k2Xb2NBDl9F1ofNrATgcceXnqCb4tZM1Zq+P0JNx2LiIqxvYpBfX/26LdxfJdoxHHKAsjPgewxkrsbWSTnYZ4rYohK+dOdu1PCyRh66g+wXSuSG52OMlXMXP1UElkRo+AbaC4X6IfyplWmlCH/PnsF3/vKxWJ7g3CPuV67u8tNFHCYSDTTRF7EKJOc X-Bogosity: Ham, tests=bogofilter, spamicity=0.007466, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: From: Jung-JaeJoon If there are not enough nodes, mas_node_count() set an error state via mas_set_err() and return control flow to the beginning. In the return flow, mas_nomem() checks the error status, allocates new nodes, and resumes execution again. In particular, if this happens in mas_split() in the slow_path section executed in mas_wr_modify(), unnecessary work is repeated, causing a slowdown in speed as below flow: _begin: mas_wr_modify() --> if (new_end >= mt_slots[wr_mas->type]) --> goto slow_path slow_path: --> mas_wr_bnode() --> mas_store_b_node() --> mas_commit_b_node() --> mas_split() --> mas_node_count() return to _begin But, in the above flow, if mas_node_count() is executed before entering slow_path, execution efficiency is improved by allocating nodes without entering slow_path repeatedly. Signed-off-by: JaeJoon Jung --- lib/maple_tree.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 2d7d27e6ae3c..8ffabd73619f 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4176,8 +4176,13 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas) * path. */ new_end = mas_wr_new_end(wr_mas); - if (new_end >= mt_slots[wr_mas->type]) + if (new_end >= mt_slots[wr_mas->type]) { + mas->depth = mas_mt_height(mas); + mas_node_count(mas, 1 + mas->depth * 2); + if (mas_is_err(mas)) + return; goto slow_path; + } /* Attempt to append */ if (mas_wr_append(wr_mas, new_end)) -- 2.17.1