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 132B8C77B60 for ; Fri, 28 Apr 2023 06:48:22 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 7D273900002; Fri, 28 Apr 2023 02:48:21 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 783816B0072; Fri, 28 Apr 2023 02:48:21 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 64BD6900002; Fri, 28 Apr 2023 02:48:21 -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 530C26B0071 for ; Fri, 28 Apr 2023 02:48:21 -0400 (EDT) Received: from smtpin09.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 24A6C160271 for ; Fri, 28 Apr 2023 06:48:21 +0000 (UTC) X-FDA: 80729870802.09.1ABF5DC Received: from mail-pf1-f195.google.com (mail-pf1-f195.google.com [209.85.210.195]) by imf11.hostedemail.com (Postfix) with ESMTP id 3E7874000A for ; Fri, 28 Apr 2023 06:48:19 +0000 (UTC) Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=gmail.com header.s=20221208 header.b=QHafmgIH; spf=pass (imf11.hostedemail.com: domain of perlyzhang@gmail.com designates 209.85.210.195 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=1682664499; 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=uC+tJ4GtJurVwS7BEvK2jrpzffs8Ds1Czvj8O+Xiy4I=; b=NY7dSWAhCYUeut5Nw67ZjMMwFd0pL9KuKiGpSN4/Bris+9GBpZJuhdsSE6ZE1n1bAJKipJ LRRF2NX7+mdedCS/TrUvANoppvuaBsJeA9H8ihPj+9g3yw0PL8dmeQg2DtaT1qMLXivStF rZjqhNts+hbcG/WvZqVKb4DA8uDCOrs= ARC-Authentication-Results: i=1; imf11.hostedemail.com; dkim=pass header.d=gmail.com header.s=20221208 header.b=QHafmgIH; spf=pass (imf11.hostedemail.com: domain of perlyzhang@gmail.com designates 209.85.210.195 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=1682664499; a=rsa-sha256; cv=none; b=7AwP4+zIV+PpVWakWqQw1X/VBGkdc3FlO+6WsnTv0pZuYGoSryxfGcK1BKUaAVtiZ8Ka8p vP4kgUH3/IOWaRpJrxrXO4Aywe7vWwNILJOXB81bIiIIBj1EQyHN/foqp39kjz2YMLY8Z9 HwmhnEkFkTb6S0XUPc8sROQcQtg+uI0= Received: by mail-pf1-f195.google.com with SMTP id d2e1a72fcca58-63b67a26069so11740059b3a.0 for ; Thu, 27 Apr 2023 23:48:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1682664498; x=1685256498; 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=uC+tJ4GtJurVwS7BEvK2jrpzffs8Ds1Czvj8O+Xiy4I=; b=QHafmgIHrEx49yE494LBSgJnwcTuOlNreOBs0nBruW+Cu640UsRueGtf9jZz/3j3DN jD0d7xVbmZ2H4eTVtzkUN+1v3EWPY0kax9t9cQiqDIXsgPFcCwIhMLTXM2Aq7zoO96Di 6Rcpb0Nikg+0xULgGE2ilmhoVUxknmYsCKPWNpVKmyZhglovsXa55XgMnEJr0DcoU51f GvUAq28Aw3aAImSKR2u+FPNWAhhbhcmPThqz7YL+q2BirWobTUzd4/WVQPA+OjTr6KqK V2tP7vnv/VzXTcvGX3FyHdmLn4qKXaCJKDI1ZzeaZ2Oq+axgP3Yc2Z6igffDeO9HEfYR UZsA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1682664498; x=1685256498; 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=uC+tJ4GtJurVwS7BEvK2jrpzffs8Ds1Czvj8O+Xiy4I=; b=UiP2AqgF519YRH4GyC1i/fo91Lqna/Zs5LugCWnVAu37OqxndpOoN0rJYlO1vYkV4c vsAIhLjkqy5yOO/WmaGdKnvZtm2kJ0LpleyMMoc8yh0kG2Zg2TvmXnGyIkfKW6Xw+rw8 qq5Sk8K+6fvrtuNXT2kyoisiC8lbYqS9vM5d5h15TK0Ya5HcnO4+997NSwBfFWkXJXi7 VzIW+oCZ53jlSWjy+4CAq5VhcXPFOC3nGLeAZ5k+hOAcj8UyRi4oo5szb+ESaeBpi3A5 w1SZ5UhpibIl5lS+htG5mF2WtmKfGzJ1308sc7WRFJEc5KYrTfa/hPyRwlugssPjhuNx PZkQ== X-Gm-Message-State: AC+VfDys2ymks2CWkQ5rIszopceTOnbozfg2wLwq17y//Zp8vUHMFDi/ GqG6GBmRFBenV1MTvPbcw18= X-Google-Smtp-Source: ACHHUZ51Qz9nSuXULfBI70vbcVZNidv0XPtJQeTyo0MdxoZJfX8E+6qtYeI6t1MB7lNTD6pb5sscfQ== X-Received: by 2002:aa7:888f:0:b0:63d:254a:3900 with SMTP id z15-20020aa7888f000000b0063d254a3900mr5495826pfe.5.1682664497828; Thu, 27 Apr 2023 23:48:17 -0700 (PDT) Received: from [10.200.10.82] ([139.177.225.232]) by smtp.gmail.com with ESMTPSA id y189-20020a62cec6000000b00640defda6d2sm7682777pfg.207.2023.04.27.23.48.15 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 27 Apr 2023 23:48:17 -0700 (PDT) Message-ID: Date: Fri, 28 Apr 2023 14:48:13 +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 27/34] maple_tree: Introduce mas_next_slot() interface To: "Liam R. Howlett" Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org, maple-tree@lists.infradead.org, Andrew Morton References: <20230425140955.3834476-1-Liam.Howlett@oracle.com> <20230425140955.3834476-28-Liam.Howlett@oracle.com> From: Peng Zhang In-Reply-To: <20230425140955.3834476-28-Liam.Howlett@oracle.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 3E7874000A X-Stat-Signature: s8gc59wwuhubeuo1xfxufyssu5fi4ksw X-Rspam-User: X-Rspamd-Server: rspam08 X-HE-Tag: 1682664499-388775 X-HE-Meta: U2FsdGVkX19yTHhdLk6qVLtNBO2vy3+To1kbP5ZvG4K1FZN6cslClLgmefygT2jIFqXpvqcfFWNVtxXH0a0Jg+1ITNo3FnlzuGIC7WvTV1VJw48NQpTergd0X9fGBAkU0K14jwJg+CtAhKlqNQc2q5XIlRm1X71W1oXhfs45LGxFpPpKDErwzBdcMaWjPE5rorucUaKHTRcoS4xitNKYJ51atH6PA+nZN0YCiIH5zyOCeDtWoxgROlMv3rja3MxhSzLxJo1Xfmi3nSL/tZWOySfk3n6u9R4gJutsxkxJRqPE8BNF4DERfAnQb4CDwWDKqCHmc6hlccmdoYfUhrTjFid5axVMqwcp02OjwnsmKMIT6z/bGUc0+iVSbMMjv4ryfuVRm+cRcjZVVNjttrqtPCn0kJQ2Ci6htTIne6/1VeUWYe4j2sq+y45cHuvD79/clPzJOPsM5Mv3f97UsYMir4MVlvmQFaIN3uqXlJrb1RUTBnV1h5bsNVAu/mnwpMFQIcU8T4EiIxBRkiEEs5J7xQ9c4tlnwZcD74VDWOxcCfHXK4zyTIRF5bhQCsb3Ikp4Tppi3+xFJhJ+P2oXhX81pFX+YOPsZG/3LcjSW48HPsA4+lwpowchFKRdUqfxy7FyOZ2x3XWuGo7bqNgvJGhTLlfNVbuCNJ42NE0h3u5B5ufLuhEvGz262cBbugWoaKoKNRO19fHItU/a7cYcFHxn2GzLuFzHjPZ4Jj2PXCSX/ZCUyGnWEPMHJz1XDFqQa9xSOCfWKVRbBwwsI++KXttB4HoajL7D8i3CAdzf47cmF5aroacNjA6rSEShaG+vXEUyYs9+AcIEjPM/3zaexreMPnPM/G+g/hztdZBLjYhmMlDg93H/lbgEssTppgyfJL8ZWCRZVXNW2mqZ1VaSK+m453rKgWR9ObAVM2XYM2VH/RFSEcmEMBYl3MFiTWO8RyW1btHPuEP0KSUcbvVbT04 5k4UcLdn Ief7BB5p0yFEwXaxapB3mmn2m2Lrg6XfibjQGlONmDTYrLO0eLMgwZTc/DCDwWruybVJzCGqc24RFRbpcimMRbGYxMqzvwn+RgbQEhjeGsWLISO7EgJMadDc4i+PiTJTvKxbU0jYCHVAcKiLdjqzVJk/CSPOJZT+fDOxfpClJspLV9OhANXKaCT0lWHjqg5Q8RTdZ7BzoLZHTGUSXB0pWQ5oYIFfSAkEeIEuZlBDBT7vRaa/7puUQHp/9NBaLyneyoerposdV/Edouw+nU5ipdQVB+90cRdHLAJQ6fKHJRKhpTT9W7XvjiZ5w7lTSCpTwcDFo0kzj993YOBi86a7u9UQzhUOSHLHmqRUXsigD3jLWq8lODK6YJQxEnOOsj4PNlzK6fYG6uq6gmeqLlu/Cdw2BSTavFiTuzacgw6ZFPg4Qwy0tOrNRxcA1WSb1LYFwyPRk73Uvd9xyp/G0j6B5yHgxS+BRBNW9dzK7SxAQPWJ9xAafN7uPMo8NOGoiCzj39CkZ X-Bogosity: Ham, tests=bogofilter, spamicity=0.000110, 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, during a tree walk, the user needs the next slot regardless > of if it is empty or not. Add an interface to get the next slot. > > Since there are no consecutive NULLs allowed in the tree, the mas_next() > function can only advance two slots at most. So use the new > mas_next_slot() interface to align both implementations. > > Signed-off-by: Liam R. Howlett > --- > lib/maple_tree.c | 178 +++++++++++++++++++---------------------------- > 1 file changed, 71 insertions(+), 107 deletions(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index 31cbfd7b44728..fe6c9da6f2bd5 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -4619,15 +4619,16 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, > if (mas->max >= max) > goto no_entry; > > + min = mas->max + 1; > + if (min > max) > + goto no_entry; Unnecessary check due to mas->max < max. > + > level = 0; > do { > if (ma_is_root(node)) > goto no_entry; > > - min = mas->max + 1; > - if (min > max) > - goto no_entry; > - > + /* Walk up. */ > if (unlikely(mas_ascend(mas))) > return 1; > > @@ -4645,13 +4646,12 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, > slots = ma_slots(node, mt); > pivot = mas_safe_pivot(mas, pivots, ++offset, mt); > while (unlikely(level > 1)) { > - /* Descend, if necessary */ > + level--; > enode = mas_slot(mas, slots, offset); > if (unlikely(ma_dead_node(node))) > return 1; > > mas->node = enode; > - level--; > node = mas_mn(mas); > mt = mte_node_type(mas->node); > slots = ma_slots(node, mt); > @@ -4680,85 +4680,84 @@ 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_nentry() - Get the next node entry > - * @mas: The maple state > - * @max: The maximum value to check > - * @*range_start: Pointer to store the start of the range. > + * mas_next_slot() - Get the entry in the next slot > * > - * Sets @mas->offset to the offset of the next node entry, @mas->last to the > - * pivot of the entry. > + * @mas: The maple state > + * @max: The maximum starting range > * > - * Return: The next entry, %NULL otherwise > + * Return: The entry in the next slot which is possibly NULL > */ > -static inline void *mas_next_nentry(struct ma_state *mas, > - struct maple_node *node, unsigned long max, enum maple_type type) > +void *mas_next_slot(struct ma_state *mas, unsigned long max) > { > - unsigned char count; > - unsigned long pivot; > - unsigned long *pivots; > void __rcu **slots; > + unsigned long *pivots; > + unsigned long pivot; > + enum maple_type type; > + struct maple_node *node; > + unsigned char data_end; > + unsigned long save_point = mas->last; > void *entry; > > - if (mas->last == mas->max) { > - mas->index = mas->max; > - return NULL; > - } > - > - slots = ma_slots(node, type); > +retry: > + node = mas_mn(mas); > + type = mte_node_type(mas->node); > pivots = ma_pivots(node, type); > - count = ma_data_end(node, type, pivots, mas->max); > - if (unlikely(ma_dead_node(node))) > - return NULL; > - > - mas->index = mas_safe_min(mas, pivots, mas->offset); > - if (unlikely(ma_dead_node(node))) > - return NULL; > - > - if (mas->index > max) > - return NULL; > + data_end = ma_data_end(node, type, pivots, mas->max); > + pivot = mas_logical_pivot(mas, pivots, mas->offset, type); > + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) > + goto retry; > > - if (mas->offset > count) > + if (pivot >= max) > return NULL; > > - while (mas->offset < count) { > - pivot = pivots[mas->offset]; > - entry = mas_slot(mas, slots, mas->offset); > - if (ma_dead_node(node)) > - return NULL; > - > - mas->last = pivot; > - if (entry) > - return entry; > - > - if (pivot >= max) > - return NULL; > + if (likely(data_end > mas->offset)) { > + mas->offset++; > + mas->index = mas->last + 1; > + } else { > + if (mas_next_node(mas, node, max)) { > + mas_rewalk(mas, save_point); > + goto retry; > + } > > - if (pivot >= mas->max) > + if (mas_is_none(mas)) > return NULL; > > - mas->index = pivot + 1; > - mas->offset++; > + mas->offset = 0; > + mas->index = mas->min; > + node = mas_mn(mas); > + type = mte_node_type(mas->node); > + pivots = ma_pivots(node, type); > } > > - pivot = mas_logical_pivot(mas, pivots, mas->offset, type); > + slots = ma_slots(node, type); > + mas->last = mas_logical_pivot(mas, pivots, mas->offset, type); > entry = mas_slot(mas, slots, mas->offset); > - if (ma_dead_node(node)) > - return NULL; > + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) > + goto retry; > > - mas->last = pivot; > return 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; > -} > - > /* > * mas_next_entry() - Internal function to get the next entry. > * @mas: The maple state > @@ -4774,47 +4773,18 @@ static inline void mas_rewalk(struct ma_state *mas, unsigned long index) > static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit) > { > void *entry = NULL; > - struct maple_node *node; > - unsigned long last; > - enum maple_type mt; > > if (mas->last >= limit) > return NULL; > > - last = mas->last; > -retry: > - node = mas_mn(mas); > - mt = mte_node_type(mas->node); > - mas->offset++; > - if (unlikely(mas->offset >= mt_slots[mt])) { > - mas->offset = mt_slots[mt] - 1; > - goto next_node; > - } > - > - while (!mas_is_none(mas)) { > - entry = mas_next_nentry(mas, node, limit, mt); > - if (unlikely(ma_dead_node(node))) { > - mas_rewalk(mas, last); > - goto retry; > - } > - > - if (likely(entry)) > - return entry; > - > - if (unlikely((mas->last >= limit))) > - return NULL; > + entry = mas_next_slot_limit(mas, limit); > + if (entry) > + return entry; > > -next_node: > - if (unlikely(mas_next_node(mas, node, limit))) { > - mas_rewalk(mas, last); > - goto retry; > - } > - mas->offset = 0; > - node = mas_mn(mas); > - mt = mte_node_type(mas->node); > - } > + if (mas_is_none(mas)) > + return NULL; > > - return NULL; > + return mas_next_slot_limit(mas, limit); > } > > /* > @@ -4845,10 +4815,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, > slots = ma_slots(mn, mt); > pivots = ma_pivots(mn, mt); > count = ma_data_end(mn, mt, pivots, mas->max); > - if (unlikely(ma_dead_node(mn))) { > - mas_rewalk(mas, index); > + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) > goto retry; > - } > > offset = mas->offset - 1; > if (offset >= mt_slots[mt]) > @@ -4861,10 +4829,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, > pivot = pivots[offset]; > } > > - if (unlikely(ma_dead_node(mn))) { > - mas_rewalk(mas, index); > + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) > goto retry; > - } > > while (offset && !mas_slot(mas, slots, offset)) { > pivot = pivots[--offset]; > @@ -4881,10 +4847,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, > > min = mas_safe_min(mas, pivots, offset); > entry = mas_slot(mas, slots, offset); > - if (unlikely(ma_dead_node(mn))) { > - mas_rewalk(mas, index); > + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) > goto retry; > - } > > mas->offset = offset; > mas->last = pivot;