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 DA37DD6DDDB for ; Fri, 15 Nov 2024 07:52:10 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 321ED6B0083; Fri, 15 Nov 2024 02:52:10 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 2D2A86B0085; Fri, 15 Nov 2024 02:52:10 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 19A4B6B0089; Fri, 15 Nov 2024 02:52:10 -0500 (EST) 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 EAA926B0083 for ; Fri, 15 Nov 2024 02:52:09 -0500 (EST) Received: from smtpin13.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 671E6ACF74 for ; Fri, 15 Nov 2024 07:52:09 +0000 (UTC) X-FDA: 82787558868.13.92083E9 Received: from mail-ej1-f49.google.com (mail-ej1-f49.google.com [209.85.218.49]) by imf03.hostedemail.com (Postfix) with ESMTP id BF2F220002 for ; Fri, 15 Nov 2024 07:51:46 +0000 (UTC) Authentication-Results: imf03.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=B2PQIUyF; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf03.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.49 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731656948; a=rsa-sha256; cv=none; b=SSrc2MhAPqIV2YnsqlESu9QbPF4syDPZa3jqtwJRqpuWwM4bC4+O6a0eZjAjnOmmkSxOOS 4deTpC6NNMOXFdv1bj6RENPqojh5gFAkBML7uEbRCxV9IWNvf+6UlV9Vj6hk/wue3d4cCK glfXH4ALz5sXnPWDJGJ0Ge9rXS2LmYY= ARC-Authentication-Results: i=1; imf03.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=B2PQIUyF; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf03.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.49 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1731656948; h=from:from:sender:reply-to: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: in-reply-to:in-reply-to:references:references:dkim-signature; bh=ak51RbAOf5ag9k2fqB3j10uDW53SBC7LHip6uj8Et3I=; b=aNy5Ib80qmCGDW3p5DAo6GETx8728OFBfAaCSgsIXniPwvxRynMO4LkfYT9mSfWNMR7K5d ACk0iRTGEx25uW5U4NmQ13k3hQIi0yqa+1KoVzTOSCfG0tuB0d8HVTaFewe8i/acd9LuNm Hiv04bUUgeskFrcYBGM/EF4M7gZXeBs= Received: by mail-ej1-f49.google.com with SMTP id a640c23a62f3a-a9a0c7abaa6so180796366b.2 for ; Thu, 14 Nov 2024 23:52:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731657126; x=1732261926; darn=kvack.org; h=user-agent:in-reply-to:content-disposition:mime-version:references :reply-to:message-id:subject:cc:to:from:date:from:to:cc:subject:date :message-id:reply-to; bh=ak51RbAOf5ag9k2fqB3j10uDW53SBC7LHip6uj8Et3I=; b=B2PQIUyFd8d525NUFCrgoeq0M9eh+cxBURuflDVeZn3pRErt9WB38lDJKMEJWLjEoB JldWsXzBkOJ0cTP9gFIKzX3qKHqh2FAE2usdBn4yQeKgmHuCtQQh7/IiDEqFJ8meR34Y 1CrF1YbL5IoxqLRVk47VLtA2Hru68gS5Xf2LTHZME1j9VaicPL8ZJimDH+slqQJQ2rD/ DXlLy4hm8H/9CNb+MAgkkoNNWm5mrxXM0sijP/7shD4es61pRMLJGbjPEu+TNO0jkSlY DbsO8Km+mG6siS/dxluB+JlMUfHxmBRH4Xf9pujxTDCKwR5kpR/n74zUngPj7+lFAA/h LmEQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731657126; x=1732261926; h=user-agent:in-reply-to:content-disposition:mime-version:references :reply-to:message-id:subject:cc:to:from:date:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=ak51RbAOf5ag9k2fqB3j10uDW53SBC7LHip6uj8Et3I=; b=v2nVmK68o7+4sjYo096RbHzSOebGHDNxza6N58vK+Wn6Rywn3D+em61xOMW8yfRSd9 ho6xUHR0/HPcdbrTW3Aa4Yatgo0XbQcTVY0UP2BoVwZajJUdOORDrfcJwJLkywb/+n65 XTog5/4rAPvMaGonaWFO3/YfNT1qLlf53lj7KNK80/djiKAI8V6z3tqg+n/vusmiD6aQ 6YGx8BWOCUH9qswesBWJldz61lolepdNp+3Trp+nmUloxdTVwLgsPu+ODXHIdCq/9swl sss0BeAOH0QupnDH/gyP7Ah31/KyNdzWLa1cA2Rg9eucqZC7gp8riEkEnrP9cOdp7jIX m3yA== X-Forwarded-Encrypted: i=1; AJvYcCVZyeyuQtQEJUrGlmUAXs8wGtFBPM8BV5OVtADebR9aN3NrTEdx6XkbSfqimzSOPBkisU5vEeL0jQ==@kvack.org X-Gm-Message-State: AOJu0YwQea6RYi5UiCAJhxA0VQE+R5mGQ8nPLoPw6xMwJkeduARaiBcr KURC2ITLm0V4xRIm6Pohr3hHQPvcP+5QsKKVNF8VuxpErydiEvtQ X-Google-Smtp-Source: AGHT+IGeUUCALONSY/DirIy3E7MjqDCgjI19kTQd0vXvuk/ibTsIesE3PfVGRjSRcDeb/U+GiWPb6g== X-Received: by 2002:a17:906:6a20:b0:a9e:c267:78c5 with SMTP id a640c23a62f3a-aa483553e28mr129250866b.55.1731657125577; Thu, 14 Nov 2024 23:52:05 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-aa20df2649esm150606766b.39.2024.11.14.23.52.04 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Thu, 14 Nov 2024 23:52:04 -0800 (PST) Date: Fri, 15 Nov 2024 07:52:03 +0000 From: Wei Yang To: Sidhartha Kumar Cc: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com Subject: Re: [PATCH 3/5] maple_tree: use vacant nodes to reduce worst case allocations Message-ID: <20241115075203.ojspk255cw3sr3s3@master> Reply-To: Wei Yang References: <20241114170524.64391-1-sidhartha.kumar@oracle.com> <20241114170524.64391-4-sidhartha.kumar@oracle.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20241114170524.64391-4-sidhartha.kumar@oracle.com> User-Agent: NeoMutt/20170113 (1.7.2) X-Stat-Signature: fo4f3pbf5bi16qma6643zf3fxz5r5em6 X-Rspamd-Queue-Id: BF2F220002 X-Rspamd-Server: rspam08 X-Rspam-User: X-HE-Tag: 1731657106-144232 X-HE-Meta: U2FsdGVkX1+kFPonP6eKtUXYKGkAvAwhxBErnmFnUYcXZrUMwrrbLDJoriq5VwX+BqTMjnp3y0+eaZEVUBkmRopWqTLUmwnduZX77S+GdN2/5JCuV1C3yVCJ8CSdxhxGuBRdZ0OS1IVyQAHR7JUIKhPb2WXIfOdVxKJ/PQqgZzZ0eXUTwfvB5r3PFMHmoBAw8rLs7TpTGeorWwr8b6+HBbUrkU4oxRd1ayEs6GGZMA2vVbAkC4LtOKbFt6XL4sUC4oE9H3mb14mVglD2wbR2JNU9pdlrGh0VXHF118Pe9cyjGN2k1rYr11gZHkiHFVF93JdRKeCjIY1bL2I8jMHH9oWEnsew+mUwnT0s87bkbNZNiOxPGU211JGBuGGhmZ4VpDdo2PeCIEsnhDmr4Ao+cn5lNpvBmOEJba+PCwdlmwSVKWvwk8w2H65CIU205tsVcfUbQacVXmaSidlQtsvZMJj7fIzLM3/0kzZLdUVGKp9iXMHh5M6SVE/erBG1ax2v7Qye90/rc398dHz0tmbYniHuccsRyv5ezh/aWumMtEg4iVtQf2G3HNOHK+YKBY9g4FJuTyudIdQhqX/ve6tR4JwdQahF+wFSkcm/s7XfZJPUsqZf1NGPjejEUhww9zoJbxryfimnqH6xtN9zVebB7npMADoMgDfvC+fLNxuOyt5HKLa6gr5HL32psbGAB+GdWUKN/pJi3coAl1QWxxjL6azd5lnoJft27cpfhyg6ADnVAkvKbhlbkQbfnYf/v3jARIlg5vxG4ixj7CRX7cdoxiXgm5eLdUNdCkqQ/AVn1uv/irS1GTznplhSyzOtfNWtPX/E2NXqJMSjM1F44heMLdjwP9fIxGkCtrSK3+3LOtjQIEQT29pIUQ4q10+Wd1QNKTuiT93Zlkvu3O3jGn6aM4XywmSAcOzTNSVPAwNc+tBXVAK6VUuggxOlTmbhOrEsuiyhvR1HYhPE6ibDa7l Bga8roc4 hpb7Sd86JEhMNID/mufT2b8DpRIWCnAKih7m9wit3yiwSzXKVXme83uAhMfKQC7w4g83+v24k4rRGR8NQ7gMDTNp6FvORtJNr1UVo7fCVSjXkjbU9qgLKmNxDBsrGjoRo+Uic1I/Qdp0/ZkWPrDDNCWmeteivuSYPK/bec+fE35qBD+NCkHrlWvLq2KkTzvKi+jysUb6ts4Mi94ntCS6osJyexxEglU/kkESILInVTY5O5K5490PvRQIImuCb6H40L53Lzf4vGWqNwn+SuoCMFs51FRN7ZrrSi+TNjQ9dTuqIJR2IqLUWH4kDZXw7M1bacOg9aJ2nmWAGJ4268KGPDtb/C2xh9KYVcBLQBF7MWU36jOBOFSQ6lougW9rgVnP1PHKM9VWzUHy7xRJwgqu68dDBLMCfaXzEXAbUOPYgtTZgcb8XQdM6M7wEbpILoKnkwVcXlCy01aU+ypyWPPjBYCl+xuD25xxliNhy/NUOILbYfJ9Vnu6hWECgZN1jIyPos4LKuoIVGXetXwzZY0xkUo1KJoLyHlJOW2lQEZwwIjhqwy6PndTHzpQWsiEJ2lQ19pOX8DRVGrJ17vAu5fqSyPfCamSZ21LaZNf2cjS8JP56EhwKZv1cuceZCg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000300, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: On Thu, Nov 14, 2024 at 12:05:22PM -0500, Sidhartha Kumar wrote: >In order to determine the store type for a maple tree operation, a walk >of the tree is done through mas_wr_walk(). This function descends the >tree until a spanning write is detected or we reach a leaf node. While >descending, keep track of the height at which we encounter a node with >available space. This is done by checking if mas->end is less than the >number of slots a given node type can fit. > >Now that the height of the vacant node is tracked, we can use the >difference between the height of the tree and the height of the vacant >node to know how many levels we will have to propagate creating new >nodes. Update mas_prealloc_calc() to consider the vacant height and >reduce the number of worst allocations. > >Rebalancing stores are not supported and fall back to using the full >height of the tree for allocations. > >Update preallocation testing assertions to take into account vacant >height. > >Signed-off-by: Sidhartha >--- > include/linux/maple_tree.h | 2 + > lib/maple_tree.c | 13 +++-- > tools/testing/radix-tree/maple.c | 97 +++++++++++++++++++++++++++++--- > 3 files changed, 100 insertions(+), 12 deletions(-) > >diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h >index cbbcd18d4186..7d777aa2d9ed 100644 >--- a/include/linux/maple_tree.h >+++ b/include/linux/maple_tree.h >@@ -463,6 +463,7 @@ struct ma_wr_state { > void __rcu **slots; /* mas->node->slots pointer */ > void *entry; /* The entry to write */ > void *content; /* The existing entry that is being overwritten */ >+ unsigned char vacant_height; /* Depth of lowest node with free space */ ^^^ ^^^ Would this be a little misleading? > }; > > #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock)) >@@ -498,6 +499,7 @@ struct ma_wr_state { > .mas = ma_state, \ > .content = NULL, \ > .entry = wr_entry, \ >+ .vacant_height = 0 \ > } > > #define MA_TOPIARY(name, tree) \ >diff --git a/lib/maple_tree.c b/lib/maple_tree.c >index 21289e350382..f14d70c171c2 100644 >--- a/lib/maple_tree.c >+++ b/lib/maple_tree.c >@@ -3545,6 +3545,9 @@ static bool mas_wr_walk(struct ma_wr_state *wr_mas) > if (ma_is_leaf(wr_mas->type)) > return true; > >+ if (mas->end < mt_slots[wr_mas->type] - 1) >+ wr_mas->vacant_height = mas->depth + 1; For some cases in rebalance, we may split data into three parts, which means we need 2 extra vacant slot. Maybe this check is not accurate? >+ > mas_wr_walk_traverse(wr_mas); > } > >@@ -4159,7 +4162,9 @@ static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas) > static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry) > { > struct ma_state *mas = wr_mas->mas; >- int ret = mas_mt_height(mas) * 3 + 1; >+ unsigned char height = mas_mt_height(mas); >+ int ret = height * 3 + 1; >+ unsigned char delta = height - wr_mas->vacant_height; > > switch (mas->store_type) { > case wr_invalid: >@@ -4177,13 +4182,13 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry) > ret = 0; > break; > case wr_spanning_store: >- ret = mas_mt_height(mas) * 3 + 1; >+ ret = delta * 3 + 1; Hmm... I am afraid we need to put this patch after next one. Without the change in next patch, we still need to go up the tree till root to rebalance. > break; > case wr_split_store: >- ret = mas_mt_height(mas) * 2 + 1; >+ ret = delta * 2 + 1; > break; > case wr_rebalance: >- ret = mas_mt_height(mas) * 2 - 1; >+ ret = height * 2 + 1; Looks current calculation is not correct? If so, do we need to have a fix to be backported? -- Wei Yang Help you, Help me