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 2F573C77B61 for ; Fri, 28 Apr 2023 08:27:53 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8E3AB6B0071; Fri, 28 Apr 2023 04:27:52 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 893BE6B0072; Fri, 28 Apr 2023 04:27:52 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 734716B0074; Fri, 28 Apr 2023 04:27:52 -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 67FC36B0071 for ; Fri, 28 Apr 2023 04:27:52 -0400 (EDT) Received: from smtpin14.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 30BCE1A0319 for ; Fri, 28 Apr 2023 08:27:52 +0000 (UTC) X-FDA: 80730121584.14.3F79E5A Received: from mail-pf1-f194.google.com (mail-pf1-f194.google.com [209.85.210.194]) by imf11.hostedemail.com (Postfix) with ESMTP id 36FC540025 for ; Fri, 28 Apr 2023 08:27:49 +0000 (UTC) Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=gmail.com header.s=20221208 header.b=f4CYpi6s; spf=pass (imf11.hostedemail.com: domain of perlyzhang@gmail.com designates 209.85.210.194 as permitted sender) smtp.mailfrom=perlyzhang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1682670470; 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=H18dMVo9qUQadEgoZKjkca+2alYtWvOTeMQpVzEQrQ4=; b=hDOGxHueR3lI3jI5U95hlO0fbiCVLo5KKXUs+9zE6aiVdw37lVDo7zsLMLLqw3zj9MiWkZ h6AtRlymz0tfSRf2RslaePuXJFtIBwNZrAx8zgqle0fLu0k7ou/vtS9NR0J57dgSlLVRpm b0wo/FGMl4viyM7tv55Vv62lV87m5RA= ARC-Authentication-Results: i=1; imf11.hostedemail.com; dkim=pass header.d=gmail.com header.s=20221208 header.b=f4CYpi6s; spf=pass (imf11.hostedemail.com: domain of perlyzhang@gmail.com designates 209.85.210.194 as permitted sender) smtp.mailfrom=perlyzhang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1682670470; a=rsa-sha256; cv=none; b=p0OBGuIIVM4eG9zUSYf4SMSK0aP2WG7lnb1JhG1UauOf1GivgG8O13GXqpsjeqvbJbK+Xu KXJzxq/EJcTKsWJ8b0Af1J/P2lLjOmyj45PjLBZtRciXu4W/E+tBYMmA89mc5io2yGAdLP fExBiRTFQiMx+l12FO+TQdenzmnhhyQ= Received: by mail-pf1-f194.google.com with SMTP id d2e1a72fcca58-63b4e5fdb1eso10962461b3a.1 for ; Fri, 28 Apr 2023 01:27:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1682670469; x=1685262469; 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=H18dMVo9qUQadEgoZKjkca+2alYtWvOTeMQpVzEQrQ4=; b=f4CYpi6sFKm1jS5zAmyNI4iDz5fVbfn4mfmJQzvxjumrF3azU3cQv1jQRRg7MljF4i ySx5EYQBraTWANIvANtB4Y17URlsvGhXCG+0fvGOqmQk6SO5ItzipDM/hXYbtptr6qju nn4cJmRNWGCBbLMIEfNbTGvfMPtw/G/MkFziVdTTgnAAHBn8b3ybSSvV7ii3D4KlqokK avIYONmmVQGC/wEVgwu0C3TakuQINUnl85uvORs8XFp0cjC5QaV/jDqbmD4syG7kvXG2 iM35Btrz964e9gN3nBOA4MQnfZ8rie5nbWKsATLkfZ6t/wkwBiuRiyduqom4OD/m+kWk 6RJA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1682670469; x=1685262469; 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=H18dMVo9qUQadEgoZKjkca+2alYtWvOTeMQpVzEQrQ4=; b=FyQiPNRsaJgpXnQARz9N4u3vPsbLORR6AratMThpTjRyVDsGlZLHOtDXS+eJl1mLCk ArQB4cPFxwcv1IFbVp/Kw9b9XehzU6fOUUOT1ZqCCeP9PXONh2CbsrEBFVXIT6OhijRI YNUIei9RFtiy9El8RGed1NIEuUJiYYCf7tLDZQ0klLcmoaCEBRNlo5aSt03hWcmnmO3G oHDtXGCHwVSYQcGynptpyZaLPHrpQHcUpsb/ThHVjQaoecLmM43//D0BRzpo4myo75Wq hytJbr3Pkmqn9Q3FWUWeUlig15rLD49zGf9tovV88VR8XWbAfvFV3BHHmakxqbSYi3fe M0ng== X-Gm-Message-State: AC+VfDyoME9NT6A2dGb2izVZoz3Mm0hIROMl9lF44U+FXZK8LeK+wP0P lk6jZEeyhO6Gbl1YedtIt9U= X-Google-Smtp-Source: ACHHUZ4DF2Pg2yl4DEAX+uYMHc8dn+00yHnBGDvWbYIQnl37VNIihmznbbNzycrXkSiYiIEtw1Eazw== X-Received: by 2002:a05:6a20:7f92:b0:f0:e3ed:469a with SMTP id d18-20020a056a207f9200b000f0e3ed469amr5297306pzj.55.1682670468641; Fri, 28 Apr 2023 01:27:48 -0700 (PDT) Received: from [10.200.10.82] ([139.177.225.232]) by smtp.gmail.com with ESMTPSA id q10-20020a63d60a000000b0051eff0a70d7sm12310713pgg.94.2023.04.28.01.27.45 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 28 Apr 2023 01:27:48 -0700 (PDT) Message-ID: Date: Fri, 28 Apr 2023 16:27:43 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.10.1 Subject: Re: [PATCH 29/34] maple_tree: Introduce mas_prev_slot() interface To: "Liam R. Howlett" , Andrew Morton Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org, maple-tree@lists.infradead.org References: <20230425140955.3834476-1-Liam.Howlett@oracle.com> <20230425140955.3834476-30-Liam.Howlett@oracle.com> From: Peng Zhang In-Reply-To: <20230425140955.3834476-30-Liam.Howlett@oracle.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 36FC540025 X-Rspam-User: X-Stat-Signature: 43swgoxb4xdxy6mngo6nezfat41mhkn4 X-HE-Tag: 1682670469-401323 X-HE-Meta: U2FsdGVkX1/dla7xepEnu14otF/DZBqFx3KIukTYvRK0bBA9DKHSoMwzqSMXvxYpR/UNB1pLOJAfsWt72dMFHr7TaEGP0PsY0aewT6LsjV5JHlzfIxquu84slSfZyKalILxYNvaYNMVrkIVpn2drTh7+ZN8Zj4hY74QaT7pBxF+elemO61NVcGPuBrW+7netLTL3dNMjbEiTk1qwtGam4uWMGrseFPFOm3qwpcsaJjYwkto9Y78SFux3jvL1ZFZMaHMirM+5LQcfRVNvMRPma+aNXbiveA4gkJj6R4SzSM9m306Z6SnFYBSHs1xkuNJUdxRQrM/M1SYE0JaVn5bDQSvio/OqCZaWHpnaybGiFRL8LHNqvX4i3rBPxhR4xMWxl5zatLzeF/kY/3dMI9fyWITXpmWcsvUoMBbNINg83KWAc7gAqTirZTwW+9TME5ReQGyPZ1eshHlEAC24+sgliN8fQ2iKKsBtePv7mx5h/g+aS9aVYYUPQ2uiB6E6Fzt6uPA0nTwJxNEBVaEvJtbJVq05HZMzwVlhQtDobbXP+XOMe6eBG5cLOFpI9I3Y9XbK5/qYHd0muxT4JlhkBbYW5FLFFOuhhaz1sdsy8sCbU3LT1IWbC2BeU8ICOh6iS+ZDZ5AY0hac9TN4KKZIUTyo+J6lNZEjwj/xen+qri+qkdqvacqBpliewOcLlQ2BDUZQEx6qfbREYLzzaEtE5MueNFrE32u90tU6sES9fXD5+zpfKxgzFFvYmxmxRnKcHOIepjTvNhn/CRGAFEBzMsiJrLEjZ16b9IXbLrTXAwyF5R0uaifbWYQ0xKw1ftcj8z7GTPm/XNs0BK07DbH83YCVtyhs8y2gNUnzrwK97N82xOL2RuD2kR17svjiGNEzmK4ahoLu34JzikYMqA+Q7ATMeR2ffFAwm2lousCAPbtb1J3UoHmUEsgQLWiioEpY6SGBNhKIjKc3zUxX1xnXE+C wvdyNtRC pthKvoDeQTz4cDf4LQI2ZcH8NSqXS48OabCCCPrfHNWJC33UDRXCVRQLuYEMZYykV8unA1mtQ0qZ2sRXoxzLysa6zQf82c622HjKQHn7ZvIE662ObDXJSaGC0tpJQZ1MxFMpfhRIxbJqiE6f3tDAPsENuzEnUj83eyEqWzlE4WAPv5LtINYHGnAI7zM1tE/6nqG/XKizjac/YWZftV9AFDpAe2wxFmvCwbI5GJSudwvdc9h2ujftPa/KDWouYWrTzJVTYgBld3IHmxX+nj1tgAmXiZ8jXkaKwbzmimAeob7Cab5vIJwIfCabZrnlJGjlED/qlEdMX91Q9I/eIMevEl19vTK3hcYNLa72m95QbuSkc6k+pMvydtCSatPmpzKbvaOXEG0y03JHFKvZnc9Au36qJh0CdFXsJaVCjNcTupAHuE5+III912/DlDXCponFWxTEItcnoxXgHL04mVplhzgvz6mbHmyBxBG4/DPNGQzMWNv1Shys3g6E2Vg== 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/25 22:09, Liam R. Howlett 写道: > Sometimes the user needs to revert to the previous slot, regardless of > if it is empty or not. Add an interface to go to the previous slot. > > Since there can't be two consecutive NULLs in the tree, the mas_prev() > function can be implemented by calling mas_prev_slot() a maximum of 2 > times. Change the underlying interface to use mas_prev_slot() to align > the code. > > Signed-off-by: Liam R. Howlett > --- > lib/maple_tree.c | 217 ++++++++++++++++++++--------------------------- > 1 file changed, 90 insertions(+), 127 deletions(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index 7370d7c12fe3b..297d936321347 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -4498,6 +4498,25 @@ static inline void *mas_insert(struct ma_state *mas, void *entry) > > } > > +static inline void mas_rewalk(struct ma_state *mas, unsigned long index) > +{ > +retry: > + mas_set(mas, index); > + mas_state_walk(mas); > + if (mas_is_start(mas)) > + goto retry; > +} > + > +static inline bool mas_rewalk_if_dead(struct ma_state *mas, > + struct maple_node *node, const unsigned long index) > +{ > + if (unlikely(ma_dead_node(node))) { > + mas_rewalk(mas, index); > + return true; > + } > + return false; > +} > + > /* > * mas_prev_node() - Find the prev non-null entry at the same level in the > * tree. The prev value will be mas->node[mas->offset] or MAS_NONE. > @@ -4515,13 +4534,15 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min) > struct maple_node *node; > struct maple_enode *enode; > unsigned long *pivots; > + unsigned long max; > > - if (mas_is_none(mas)) > - return 0; > + node = mas_mn(mas); > + max = mas->min - 1; May underflow. > + if (max < min) > + goto no_entry; > > level = 0; > do { > - node = mas_mn(mas); > if (ma_is_root(node)) > goto no_entry; > > @@ -4530,11 +4551,11 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min) > return 1; > offset = mas->offset; > level++; > + node = mas_mn(mas); > } while (!offset); > > offset--; > mt = mte_node_type(mas->node); > - node = mas_mn(mas); > slots = ma_slots(node, mt); > pivots = ma_pivots(node, mt); > if (unlikely(ma_dead_node(node))) > @@ -4543,12 +4564,10 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min) > mas->max = pivots[offset]; > if (offset) > mas->min = pivots[offset - 1] + 1; > + > if (unlikely(ma_dead_node(node))) > return 1; > > - if (mas->max < min) > - goto no_entry_min; > - > while (level > 1) { > level--; > enode = mas_slot(mas, slots, offset); > @@ -4569,9 +4588,6 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min) > > if (offset < mt_pivots[mt]) > mas->max = pivots[offset]; > - > - if (mas->max < min) > - goto no_entry; > } > > mas->node = mas_slot(mas, slots, offset); > @@ -4584,10 +4600,6 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min) > > return 0; > > -no_entry_min: > - mas->offset = offset; > - if (offset) > - mas->min = pivots[offset - 1] + 1; > no_entry: > if (unlikely(ma_dead_node(node))) > return 1; > @@ -4596,6 +4608,62 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min) > return 0; > } > > +/* > + * mas_prev_slot() - Get the entry in the previous slot > + * > + * @mas: The maple state > + * @max: The minimum starting range > + * > + * Return: The entry in the previous slot which is possibly NULL > + */ > +void *mas_prev_slot(struct ma_state *mas, unsigned long min) > +{ > + void *entry; > + void __rcu **slots; > + unsigned long pivot; > + enum maple_type type; > + unsigned long *pivots; > + struct maple_node *node; > + unsigned long save_point = mas->index; > + > +retry: > + node = mas_mn(mas); > + type = mte_node_type(mas->node); > + pivots = ma_pivots(node, type); > + pivot = mas_safe_min(mas, pivots, mas->offset); > + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) > + goto retry; > + > + if (pivot <= min) > + return NULL; > + > + if (likely(mas->offset)) { > + mas->offset--; > + mas->last = mas->index - 1; > + } else { > + if (mas_prev_node(mas, min)) { > + mas_rewalk(mas, save_point); > + goto retry; > + } > + > + if (mas_is_none(mas)) > + return NULL; > + > + mas->last = mas->max; > + node = mas_mn(mas); > + type = mte_node_type(mas->node); > + pivots = ma_pivots(node, type); > + } > + > + mas->index = mas_safe_min(mas, pivots, mas->offset); > + slots = ma_slots(node, type); > + entry = mas_slot(mas, slots, mas->offset); > + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) > + goto retry; > + > + return entry; > +} > + > /* > * mas_next_node() - Get the next node at the same level in the tree. > * @mas: The maple state > @@ -4680,25 +4748,6 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, > return 0; > } > > -static inline void mas_rewalk(struct ma_state *mas, unsigned long index) > -{ > -retry: > - mas_set(mas, index); > - mas_state_walk(mas); > - if (mas_is_start(mas)) > - goto retry; > -} > - > -static inline bool mas_rewalk_if_dead(struct ma_state *mas, > - struct maple_node *node, const unsigned long index) > -{ > - if (unlikely(ma_dead_node(node))) { > - mas_rewalk(mas, index); > - return true; > - } > - return false; > -} > - > /* > * mas_next_slot() - Get the entry in the next slot > * > @@ -4777,117 +4826,31 @@ static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit) > if (mas->last >= limit) > return NULL; > > - entry = mas_next_slot_limit(mas, limit); > + entry = mas_next_slot(mas, limit); > if (entry) > return entry; > > if (mas_is_none(mas)) > return NULL; > > - return mas_next_slot_limit(mas, limit); > -} > - > -/* > - * mas_prev_nentry() - Get the previous node entry. > - * @mas: The maple state. > - * @limit: The lower limit to check for a value. > - * > - * Return: the entry, %NULL otherwise. > - */ > -static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, > - unsigned long index) > -{ > - unsigned long pivot, min; > - unsigned char offset, count; > - struct maple_node *mn; > - enum maple_type mt; > - unsigned long *pivots; > - void __rcu **slots; > - void *entry; > - > -retry: > - if (!mas->offset) > - return NULL; > - > - mn = mas_mn(mas); > - mt = mte_node_type(mas->node); > - offset = mas->offset - 1; > - slots = ma_slots(mn, mt); > - pivots = ma_pivots(mn, mt); > - count = ma_data_end(mn, mt, pivots, mas->max); > - if (unlikely(mas_rewalk_if_dead(mas, mn, index))) > - goto retry; > - > - offset = mas->offset - 1; > - if (offset >= mt_slots[mt]) > - offset = mt_slots[mt] - 1; > - > - if (offset >= count) { > - pivot = mas->max; > - offset = count; > - } else { > - pivot = pivots[offset]; > - } > - > - if (unlikely(mas_rewalk_if_dead(mas, mn, index))) > - goto retry; > - > - while (offset && !mas_slot(mas, slots, offset)) { > - pivot = pivots[--offset]; > - if (pivot >= limit) > - break; > - } > - > - /* > - * If the slot was null but we've shifted outside the limits, then set > - * the range to the last NULL. > - */ > - if (unlikely((pivot < limit) && (offset < mas->offset))) > - pivot = pivots[++offset]; > - > - min = mas_safe_min(mas, pivots, offset); > - entry = mas_slot(mas, slots, offset); > - if (unlikely(mas_rewalk_if_dead(mas, mn, index))) > - goto retry; > - > - mas->offset = offset; > - mas->last = pivot; > - mas->index = min; > - return entry; > + return mas_next_slot(mas, limit); > } > > static inline void *mas_prev_entry(struct ma_state *mas, unsigned long min) > { > void *entry; > - struct maple_enode *prev_enode; > - unsigned char prev_offset; > > if (mas->index < min) > return NULL; > > -retry: > - prev_enode = mas->node; > - prev_offset = mas->offset; > - while (likely(!mas_is_none(mas))) { > - entry = mas_prev_nentry(mas, min, mas->index); > - > - if (likely(entry)) > - return entry; > - > - if (unlikely(mas->index <= min)) > - return NULL; > - > - if (unlikely(mas_prev_node(mas, min))) { > - mas_rewalk(mas, mas->index); > - goto retry; > - } > + entry = mas_prev_slot(mas, min); > + if (entry) > + return entry; > > - mas->offset++; > - } > + if (mas_is_none(mas)) > + return NULL; > > - mas->node = prev_enode; > - mas->offset = prev_offset; > - return NULL; > + return mas_prev_slot(mas, min); > } > > /*