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 EE03CC77B78 for ; Wed, 19 Apr 2023 09:02:17 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 2A5788E0002; Wed, 19 Apr 2023 05:02:17 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 2553E8E0001; Wed, 19 Apr 2023 05:02:17 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 11D768E0002; Wed, 19 Apr 2023 05:02:17 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id F3EA68E0001 for ; Wed, 19 Apr 2023 05:02:16 -0400 (EDT) Received: from smtpin10.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id AF8CBAC175 for ; Wed, 19 Apr 2023 09:02:16 +0000 (UTC) X-FDA: 80697549072.10.F481656 Received: from mail-pl1-f172.google.com (mail-pl1-f172.google.com [209.85.214.172]) by imf06.hostedemail.com (Postfix) with ESMTP id 609E7180012 for ; Wed, 19 Apr 2023 09:02:13 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=VqMdtfuj; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf06.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.172 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=1681894934; 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=79PwKIpTwwaVU82r+U4/sK48h5bR61sbuArdiDnpPEo=; b=kzFiI7hK1TmVp7J9pX0VZZfzYNFI2p3U5EebRv0GBbE+xe7GEQI22oG2IO45tDnD+ZHG7a rjQxv3af1wzLSNexMSOWbaxU7qc9HE6NogiAVMKV5ln91DqKkAChf4xTQQyG/xK/ZpeBWQ gc0MVXbWpYxisJia6n6+G0PIjlUcPHo= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=VqMdtfuj; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf06.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.172 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1681894934; a=rsa-sha256; cv=none; b=WHukG6AWrmDy/dFHk00gjrpx3sapDncRkrqIMYBk3jj4pg/QIMobLPliUOTeEOBJa/v9UW xv4mMVL+B75rWmpv/bl5HZ5OHmea85zQCtHSoiHVH9kfhvDBaUFXM2pLUw0EgnvyXidNx/ wHh52rQ457FnUdA42yeJmrgFYQ3fbTY= Received: by mail-pl1-f172.google.com with SMTP id d9443c01a7336-1a66888cb89so24539965ad.3 for ; Wed, 19 Apr 2023 02:02:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1681894932; x=1684486932; 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=79PwKIpTwwaVU82r+U4/sK48h5bR61sbuArdiDnpPEo=; b=VqMdtfuj6C2mrAI6yBezO+vvPulybbVN53rDsaeUShooyCwrV3Iz0fFfj07Utjp0cY mYqM4WGvsXfcjOFUlDUGwRwLZlh5xRogbtYBDh4E/TL2IDVIS8BKmwOiSIHdvXKIeXFK niMvIVIXWrzMxiw3/LcIdW4lZn4NgUZIw0i/1225WGpyMnIBrkJceWOg2AmJFiV4vS38 W/b7q/KIVcvEsgGBkn4BChla5oOdA6TcS2a9WEH2+j6HLVg2qgVTU5O/1B0WjRcPeCK+ lzmmBh+gaTXkzrb48EVnC1+V/aznAVBNVBY8QVw/fUDIH3JiZ9k3TRmmvhi5cp3XgjI8 KMqg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1681894932; x=1684486932; 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=79PwKIpTwwaVU82r+U4/sK48h5bR61sbuArdiDnpPEo=; b=P3XdPJ2qv5hN3UauTf4Ouylg3E73gmMdKWlj+crkgtPvZrywEIZxzizwPvnPyH1Se5 C/cl4erRR901ZN4aRt13OZs2fQpFRHNSyhghMwcJ6TdzNA6rUrYnxYkXTT3TyfLwLoI6 l4ok20tg8OI9rAQzO8DFNZQW1vOCHAgDpUW7yTNZ++nb+LjR/XNrHECZ5oNHNOu80PC+ mx7qBukWIzRMf0Ew/74awpZOdgsFIIrEtldCe8uC5/ryRNNZlUZ15SLBVu7jX2du8qnf Q9p+IA72wwUrV3co2SlqTZWtSsPZbmZis0HgsbjqWgf2/V+R+g+tJ4kaC42zSdsPM2f/ 78pw== X-Gm-Message-State: AAQBX9c3rGbRE/T7BN8uxv96iEDe6tErMAHyeZLhxQ0/DPhc/wR7nD9V 0XF/VYG9cFjb2e1zszDFffFogPCfEQuALa2EiUc= X-Google-Smtp-Source: AKy350Zyon11ZRmLF1eWKBAifnjG/I/XA1S6Cs0fCVKPdxotC+oeh4/lZy4dm+NPRfZHbcK23TeLMw== X-Received: by 2002:a17:90a:38a5:b0:246:818c:d8e4 with SMTP id x34-20020a17090a38a500b00246818cd8e4mr2493452pjb.11.1681894931889; Wed, 19 Apr 2023 02:02:11 -0700 (PDT) Received: from [10.200.10.217] ([139.177.225.248]) by smtp.gmail.com with ESMTPSA id lx3-20020a17090b4b0300b00246cc751c6bsm929701pjb.46.2023.04.19.02.02.09 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 19 Apr 2023 02:02:11 -0700 (PDT) Message-ID: <90fd5cfa-5ed9-495f-fdef-0130adaf591b@bytedance.com> Date: Wed, 19 Apr 2023 17:02:06 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.9.1 Subject: Re: [PATCH 1/3] maple_tree: Make maple state reusable after mas_empty_area_rev() To: "Liam R. Howlett" Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, Rick Edgecombe , Andrew Morton References: <20230414145728.4067069-1-Liam.Howlett@oracle.com> From: Peng Zhang In-Reply-To: <20230414145728.4067069-1-Liam.Howlett@oracle.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspam-User: X-Rspamd-Server: rspam02 X-Rspamd-Queue-Id: 609E7180012 X-Stat-Signature: j3xxy6fib785ywu95jkbpczsa1p45ss1 X-HE-Tag: 1681894933-544301 X-HE-Meta: U2FsdGVkX1+igLvLuiLGWjHZ0VRNbzTTltee65pEFlGlKYkVQNolxP6IAAnReSuIRN2dV1YeWUQEKhh8QRE7sHJfc/DH7RUMGBbOR87PYlJDlwxgn+z9XIO/pgwBR8Dfsb1qvd5bYrQ27ZkaVEjCqPsugy21PzdDW/EZMpMCadN1TRj9f+OoE9JKbZbbT3gdT/yx9wLZfyPdKd8VkVhgn7FGbzQMd0HSYy1idAKxxxvUUlMLk1fy4zaTnBUDVxY5+aqo3jwE+xpOecP8jH3LDEsB1IhZyVAwQCiOKI0kW8AwYQneB3U0V9Wn9r2sJK7zkpnZxBAi0H4MkJW9H6QPOJFQm9eOdjNjC4BqzVHh6nDWA9V4hdVHAmPhCHApfnfHYEC3bnxY2a1vwVpPxP01228m3oD0hpXXAQK5rGslEfIhPk0NtQCb5Q+HKifUVUI+0t12Bs3j9ZmXYEzqmErSfp8i1SPRSsSGfxLX1+GSwDlTBKwIEIAnrQUMGvCN9VQ2fQTAszgXHST7WX4y/VQT0YbP260HArn3jodTK6iHvd859lbfod8KS2lCmRHkJrWVo37KHYL7MaXuXgKqX3I6+TqPND6ikHee8fvijAxAFJZQfxjP2t6MiF5Tm0JyNEtD+lkt1DFmlbB58MF17uXzNP4eF55NTGYdsvmcokh0eWfzEfQjHeFnve5qyHXhbXqHPJCa1d/E1Rxn3SFkYuLIidg2Fk4SPsJjELHL4BbZM6MM1lVmnnRGlUUzectO6+HVbB/x8qY4Drb9/ltXtB1Aj4LEwlIDMImcH8TcpkZgF6z3XgtVJ9HHGxJTVQFU5jjWvaJ24Pm3r31ZzEjtuqrXDTJKu3jn72XXqwMmS14xfzSuqeBQkDBVozWDxLSyO2/8BgbhxzcQ2Ow2PrTpM3GKc2EozkodLrRDgjBakzrj3QKfpM+q1qhwQhmJWO/rHjcFfuv2hRFKBU67ncrjIsU G/+jCZ0w 67acHiwcx6puM4e3ekTuz4I2yHH/mW9iK4QYqAaSAjCp1kwXr9ZUnOpWaF4LH6Q7y+zT9Ny1/GsFR37ndRX5k7G3tFxv8z9xcV53CMG/R7EZvL290mizhzPXJpX9Gj+CXsBCTZwE9yQquSMS/tFTQDAAmPphCl82gJeU70yNtQhgEVUufucsmDpUCz2QTLRpcIiadU7gQDTn8W+HubQtaJYAyxo/DtOqwaXKCLWJV9EAbrjD5RYI9WkbtPBUln3k6Gtsp3K/Xfgur55AHbDU93NhiDyKoxK9lVeqZWJo/+lVn6PbogNG5vf5PnLNV+RESYV2ZweNgTJN9G9D/vLLgktjE3iUL/ZQlARCC1Tz+aU37cBPWBO5twU4g+NvJR5xRaLAzKZWC1O4WN9AdAWVOH2igdKgTOeXJIBI83Tt0C4siG6TEXycXR6/ZE8mIbeAA1IG+9MFo2MmVPCM= 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/4/14 22:57, Liam R. Howlett 写道: > Stop using maple state min/max for the range by passing through pointers > for those values. This will allow the maple state to be reused without > resetting. > > Also add some logic to fail out early on searching with invalid > arguments. > > Fixes: 54a611b60590 ("Maple Tree: add new data structure") > Signed-off-by: Liam R. Howlett > --- > lib/maple_tree.c | 27 +++++++++++++-------------- > 1 file changed, 13 insertions(+), 14 deletions(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index 4df6a0ce1c1b..ed350aa293b2 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -4938,7 +4938,8 @@ static inline void *mas_prev_entry(struct ma_state *mas, unsigned long min) > * Return: True if found in a leaf, false otherwise. > * > */ > -static bool mas_rev_awalk(struct ma_state *mas, unsigned long size) > +static bool mas_rev_awalk(struct ma_state *mas, unsigned long size, > + unsigned long *gap_min, unsigned long *gap_max) > { > enum maple_type type = mte_node_type(mas->node); > struct maple_node *node = mas_mn(mas); > @@ -5003,8 +5004,8 @@ static bool mas_rev_awalk(struct ma_state *mas, unsigned long size) > > if (unlikely(ma_is_leaf(type))) { > mas->offset = offset; > - mas->min = min; > - mas->max = min + gap - 1; > + *gap_min = min; > + *gap_max = min + gap - 1; > return true; > } > > @@ -5280,6 +5281,9 @@ int mas_empty_area(struct ma_state *mas, unsigned long min, > unsigned long *pivots; > enum maple_type mt; > > + if (min >= max) This can lead to errors, min == max is valid. I think it's better to change it to this: if (min > max || size == 0 || max - min < size - 1) > + return -EINVAL; > + > if (mas_is_start(mas)) > mas_start(mas); > else if (mas->offset >= 2) > @@ -5334,6 +5338,9 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min, > { > struct maple_enode *last = mas->node; > > + if (min >= max) ditto. > + return -EINVAL; > + > if (mas_is_start(mas)) { > mas_start(mas); > mas->offset = mas_data_end(mas); > @@ -5353,7 +5360,7 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min, > mas->index = min; > mas->last = max; > > - while (!mas_rev_awalk(mas, size)) { > + while (!mas_rev_awalk(mas, size, &min, &max)) { > if (last == mas->node) { > if (!mas_rewind_node(mas)) > return -EBUSY; > @@ -5368,17 +5375,9 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min, > if (unlikely(mas->offset == MAPLE_NODE_SLOTS)) > return -EBUSY; > > - /* > - * mas_rev_awalk() has set mas->min and mas->max to the gap values. If > - * the maximum is outside the window we are searching, then use the last > - * location in the search. > - * mas->max and mas->min is the range of the gap. > - * mas->index and mas->last are currently set to the search range. > - */ > - > /* Trim the upper limit to the max. */ > - if (mas->max <= mas->last) > - mas->last = mas->max; > + if (max <= mas->last) > + mas->last = max; We can get max as follows, without using pointers to track min, max in mas_rev_awalk(). mt = mte_node_type(mas->node); pivots = ma_pivots(mas_mn(mas), mt); max = mas_logical_pivot(mas, pivots, mas->offset, mt); if (max < mas->last) /* The equal sign here can be removed */ mas->last = max; > > mas->index = mas->last - size + 1; > return 0;