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 2DF4AC77B75 for ; Mon, 8 May 2023 13:27:01 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 49A5B6B0078; Mon, 8 May 2023 09:27:00 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 449E06B007D; Mon, 8 May 2023 09:27:00 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2EA236B007E; Mon, 8 May 2023 09:27:00 -0400 (EDT) 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 1A8B26B0078 for ; Mon, 8 May 2023 09:27:00 -0400 (EDT) Received: from smtpin18.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id C2AAB1A0156 for ; Mon, 8 May 2023 13:26:59 +0000 (UTC) X-FDA: 80767163358.18.C6E400F Received: from mail-pf1-f179.google.com (mail-pf1-f179.google.com [209.85.210.179]) by imf17.hostedemail.com (Postfix) with ESMTP id BDA0140004 for ; Mon, 8 May 2023 13:26:57 +0000 (UTC) Authentication-Results: imf17.hostedemail.com; dkim=pass header.d=gmail.com header.s=20221208 header.b=KlZIFceK; spf=pass (imf17.hostedemail.com: domain of vernon2gm@gmail.com designates 209.85.210.179 as permitted sender) smtp.mailfrom=vernon2gm@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=1683552417; 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: in-reply-to:in-reply-to:references:references:dkim-signature; bh=fQCOJg3W+uzuBK1RqiTQ11fYeTUuvn8Ma1oUc2qRxTs=; b=QnRHkMHdbFT+2LjVTNW+LPNDgtjUvBaKYmU8vMBRi/G9jRgc8DxVdV6F/hBUweAcuIGB8M UweFHlbvjaeJNtKqCJdCmIVgBbccwXzCw/mqjrBBuIEusaH2ui522zUTCvRyRy0HVfBIe9 u2FBYRmGIxsVSS88E7VDJ6ykpybdqBw= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1683552417; a=rsa-sha256; cv=none; b=nnvtjyedyh3r+5y7Gjx53xbIjfCh22HbnHapOFWPFZzP97sblseVwzX6QIWZbEx4rtQxJW BRsT0AaqW1SpE4Y1h0Vp43hN5+OaWTv1GgTypmPMh5pXquCnV41e8ymkjh4EY830xXzkVq FA+1S9t+LKcYGIDFXGnAvcpUBC2zP2A= ARC-Authentication-Results: i=1; imf17.hostedemail.com; dkim=pass header.d=gmail.com header.s=20221208 header.b=KlZIFceK; spf=pass (imf17.hostedemail.com: domain of vernon2gm@gmail.com designates 209.85.210.179 as permitted sender) smtp.mailfrom=vernon2gm@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-pf1-f179.google.com with SMTP id d2e1a72fcca58-64115eef620so34393934b3a.1 for ; Mon, 08 May 2023 06:26:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1683552416; x=1686144416; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=fQCOJg3W+uzuBK1RqiTQ11fYeTUuvn8Ma1oUc2qRxTs=; b=KlZIFceKK/yUt1yZ2w8IWHrzddZd+q+0DLvinVyhw10Yvr8b7ShPD9U6KEoq2V08tJ sPUraAFwu4rVe1UwQ5Gi1dDzz6Gu4u0lyW3yhoeDm5oef5WNSzB8oPaRqiDAoITsQsP/ C+fXcpwGtzl55NZ1QFpnviufpFnguPyo/eMm41aVCaWOhGivGXrv7unxCZjTxV3YKVDx 7+ZUqtxEuOZAq51FH55m1OIA66WyVoj5pSuoeiQfVg2MLtpLCaMHx9zxN1q9Bu6r3Oo2 aFpWcncg95OfCZ/wdF59c1giSsDwfsNaoOEqgGK+GstMDgV3sEuTwGuI/4lHih/mu4lo +6kw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1683552416; x=1686144416; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=fQCOJg3W+uzuBK1RqiTQ11fYeTUuvn8Ma1oUc2qRxTs=; b=Ki6q6tOz6iSFOa9JwOC0dcqkLHd3wSpTPkyFQ9wciGhhm7OKDwvghC0BjOkM9TanfZ 67MqzCJ3zv5UxxiEusohYIG7H7lLZjqKq5EIko59iV12DLqGZzs3f9gwsd7S9Jmp4Q87 ZJrYSWGR6JmT86OlJpufaG7qklSLyBm7gcAfYSUyVhr1WV/akH4YRX8I6UsX8D5UgHLi Zcr7q3Wj5kTtazpsfBmE2yQmcV1PNSAyyI4Rx0zZJ73CSp7/10TqgFG6phOjOmhjVpla oVvL6icvn+pyHXlDXJTR9aePABWZQxmix5K391K08VMkjJPQtMAZ+wyN71AFAISEzXE8 jGqA== X-Gm-Message-State: AC+VfDwsds5AMsgRXT0MGWRTJNDT1Qklt0VjzSAHcG8AuEENJQ6Hvxrv +M24krPg8Mx2JuUSbabeOX8= X-Google-Smtp-Source: ACHHUZ5HnOLRskG7NnYBLe2nfjDvZBhtYYyvcvVtwlX0yOcrRs3/2qwK+Rp5IYRwTRqFZxOInp5+Ng== X-Received: by 2002:a17:902:c409:b0:1a9:778b:c1a8 with SMTP id k9-20020a170902c40900b001a9778bc1a8mr22710917plk.12.1683552416296; Mon, 08 May 2023 06:26:56 -0700 (PDT) Received: from vernon-pc ([49.67.182.217]) by smtp.gmail.com with ESMTPSA id o9-20020a170902d4c900b001a98f844e60sm3209582plg.263.2023.05.08.06.26.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 08 May 2023 06:26:55 -0700 (PDT) Date: Mon, 8 May 2023 21:26:44 +0800 From: Vernon Yang To: "Liam R. Howlett" Cc: Andrew Morton , maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: Re: [PATCH v2 31/36] maple_tree: Add mas_prev_range() and mas_find_range_rev interface Message-ID: References: <20230505174204.2665599-1-Liam.Howlett@oracle.com> <20230505174204.2665599-32-Liam.Howlett@oracle.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20230505174204.2665599-32-Liam.Howlett@oracle.com> X-Stat-Signature: yr8puhsx7h64hnpgstpepb5fnnom7gfh X-Rspamd-Server: rspam03 X-Rspam-User: X-Rspamd-Queue-Id: BDA0140004 X-HE-Tag: 1683552417-726409 X-HE-Meta: U2FsdGVkX19ydsX7lItYqdviozo/N3sgmmfzcZbApeZeb4/0fWDQ+CguPfb2qOmi9I/h7D6KzrEGghrI6xoQ8QEUZ+gqEfwXKKbWIuaBrAS/lPT91ZM7uskK4tWT6f/VDtPsXlnETXeb/pLXA5EGM357PW5czZ4Wg5waZnfBsSohFIl/ZdRHGEy6pU2Vzhrkapri92ruc+KUA/hDJVG0uq8Oykonb4wpapPQoX1gjkiLSADMMLhFYrmzyvgvuMnoqYg3Wi3h02wLKE5eKl30/lZCiQPi1H3zq+nNVTBJrCyL1IpnxFEW1kkPVyek/NUk7sPpQUhpJL6aDwqu4budfCfJkQr2gdJhIkPDm1gYKYY6GW7CevbNO993UqkmlFxmr/HNIUSlxX9G82iVtNHCY4JXzlMf6P0yETkTLS47l5oS2I+ppewIYebChlExsjtyTu8OQvAybT8H2PagOWBa5z3aMLgS5OeZGeIogv78FgaIa/y2PoAylb7/u4IL8/OxMfbNa3+cBpKziQz2WV8kAxhoZ1sWMZzsTGSEvlk5bqxQiyx0pvzenNQFimdWilMDw352nRemgdxX1vquGHZ+Stv+/Y6awNK4VYIjJONqMIQneS+VUFUvXVZ+1mMypXTBBus3bJVUeRbm01ptbahNmoSZUTxY2j/quVnwJDJxdrsBCF9NziQRI/Jpc9vByirAhzq59c5YssMpo5dNKHV9civpHcZIelcb4hhU2eaEhBYJiCK2ycgcScC/xzcjiEuuI+w3txpb5qQ5+GQu5Dul9puHOHdiGfrOa+ipql5BSYHadFT+qARNQvjjcxSpHyKSxGu7IwE8giUxXqx4c8Kxi7Dsx96N3E0fWQWwVOxjFolVzW7jpxeRTtUaM1uT33EFjhZYCk6G1uB70qJUpC9hXSEW1mNMb7xcDtaPIj374srTw2vQ6YUPoLb3uE10ql+5Dfq2afFxJskXglEmpie mqpmTam6 KEAMQlgyubsQN2RSBZODun9w5tO3Eug91BSi5VDwHq/iTBAfRJGXfFBBuQgUTCO+cda4rmA/iQghOn+IVaMwi3bV+Q4/QxcWIYgVDCIfVdCu6OUEgnd0DkZNBB99PirodFO8dSPNNFG8DvJFqcRREa/vyejV4KlEOhdA6JHkfYWJDYVl0iSXEGz5Ebyt/5+DS8DyCigYk/xcV3oNa6WGb8aW5JmHTHzWDgMCeHg6DTereNem5jHK6kMYXQnMG58P4nwYSLwcyH+HKshCcn5iysEE0ffhxYmGl3f/xY0jATBpmZHIr9fX2S+AFhHyTsGNWr4CTRmPT2IlXyK+32sMzfy7ee38cf92xMb4ZCmlXJkFStXDNHEeol62puaK8bwQQCY1aVYd32bgldGoI7COLlfzd3pXz1xADfELHA8nswx7Ca4gtQP3l0D25+aGDL9doqfZFNhWNREUeIV6ohb/UOWF5zR14SUqk9qH2044HVd10v94S/VWpV5uJig== 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: On Fri, May 05, 2023 at 01:41:59PM -0400, Liam R. Howlett wrote: > Some users of the maple tree may want to move to the previous range > regardless of the value stored there. Add this interface as well as the > 'find' variant to support walking to the first value, then iterating > over the previous ranges. > > Signed-off-by: Liam R. Howlett > --- > include/linux/maple_tree.h | 1 + > lib/maple_tree.c | 160 +++++++++++++++++++++++++++---------- > 2 files changed, 121 insertions(+), 40 deletions(-) > > diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h > index a4cd8f891a090..542b09118a09f 100644 > --- a/include/linux/maple_tree.h > +++ b/include/linux/maple_tree.h > @@ -467,6 +467,7 @@ void mas_destroy(struct ma_state *mas); > int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries); > > void *mas_prev(struct ma_state *mas, unsigned long min); > +void *mas_prev_range(struct ma_state *mas, unsigned long max); > void *mas_next(struct ma_state *mas, unsigned long max); > void *mas_next_range(struct ma_state *mas, unsigned long max); > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index e050fd1f7cce8..f060c71965c0d 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -5924,18 +5924,8 @@ void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max) > } > EXPORT_SYMBOL_GPL(mt_next); > > -/** > - * mas_prev() - Get the previous entry > - * @mas: The maple state > - * @min: The minimum value to check. > - * > - * Must hold rcu_read_lock or the write lock. > - * Will reset mas to MAS_START if the node is MAS_NONE. Will stop on not > - * searchable nodes. > - * > - * Return: the previous value or %NULL. > - */ > -void *mas_prev(struct ma_state *mas, unsigned long min) > +static inline bool mas_prev_setup(struct ma_state *mas, unsigned long min, > + void **entry) > { > if (mas->index <= min) > goto none; > @@ -5953,7 +5943,8 @@ void *mas_prev(struct ma_state *mas, unsigned long min) > if (!mas->index) > goto none; > mas->index = mas->last = 0; > - return mas_root(mas); > + *entry = mas_root(mas); > + return true; > } > > if (mas_is_none(mas)) { > @@ -5961,18 +5952,64 @@ void *mas_prev(struct ma_state *mas, unsigned long min) > /* Walked to out-of-range pointer? */ > mas->index = mas->last = 0; > mas->node = MAS_ROOT; > - return mas_root(mas); > + *entry = mas_root(mas); > + return true; > } > - return NULL; > + return true; > } > - return mas_prev_slot(mas, min, false); > + > + return false; > > none: > mas->node = MAS_NONE; > - return NULL; > + return true; > +} > + > +/** > + * mas_prev() - Get the previous entry > + * @mas: The maple state > + * @min: The minimum value to check. > + * > + * Must hold rcu_read_lock or the write lock. > + * Will reset mas to MAS_START if the node is MAS_NONE. Will stop on not > + * searchable nodes. > + * > + * Return: the previous value or %NULL. > + */ > +void *mas_prev(struct ma_state *mas, unsigned long min) > +{ > + void *entry = NULL; > + > + if (mas_prev_setup(mas, min, &entry)) > + return entry; > + > + return mas_prev_slot(mas, min, false); > } > EXPORT_SYMBOL_GPL(mas_prev); > > +/** > + * mas_prev_range() - Advance to the previous range > + * @mas: The maple state > + * @min: The minimum value to check. > + * > + * Sets @mas->index and @mas->last to the range. > + * Must hold rcu_read_lock or the write lock. > + * Will reset mas to MAS_START if the node is MAS_NONE. Will stop on not > + * searchable nodes. > + * > + * Return: the previous value or %NULL. > + */ > +void *mas_prev_range(struct ma_state *mas, unsigned long min) > +{ > + void *entry = NULL; > + > + if (mas_prev_setup(mas, min, &entry)) > + return entry; > + > + return mas_prev_slot(mas, min, true); > +} > +EXPORT_SYMBOL_GPL(mas_prev_slot); Hi Liam, I guess you want to export mas_prev_range symbol instead of mas_prev_slot. > + > /** > * mt_prev() - get the previous value in the maple tree > * @mt: The maple tree > @@ -6116,20 +6153,15 @@ void *mas_find_range(struct ma_state *mas, unsigned long max) > EXPORT_SYMBOL_GPL(mas_find_range); > > /** > - * mas_find_rev: On the first call, find the first non-null entry at or below > - * mas->index down to %min. Otherwise find the first non-null entry below > - * mas->index down to %min. > - * @mas: The maple state > - * @min: The minimum value to check. > + * mas_find_rev_setup() - Internal function to set up mas_find_*_rev() > * > - * Must hold rcu_read_lock or the write lock. > - * If an entry exists, last and index are updated accordingly. > - * May set @mas->node to MAS_NONE. > - * > - * Return: The entry or %NULL. > + * Returns: True if entry is the answer, false otherwise. > */ > -void *mas_find_rev(struct ma_state *mas, unsigned long min) > +static inline bool mas_find_rev_setup(struct ma_state *mas, unsigned long min, > + void **entry) > { > + *entry = NULL; > + > if (unlikely(mas_is_none(mas))) { > if (mas->index <= min) > goto none; > @@ -6141,7 +6173,7 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min) > if (unlikely(mas_is_paused(mas))) { > if (unlikely(mas->index <= min)) { > mas->node = MAS_NONE; > - return NULL; > + return true; > } > mas->node = MAS_START; > mas->last = --mas->index; > @@ -6149,14 +6181,12 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min) > > if (unlikely(mas_is_start(mas))) { > /* First run or continue */ > - void *entry; > - > if (mas->index < min) > - return NULL; > + return true; > > - entry = mas_walk(mas); > - if (entry) > - return entry; > + *entry = mas_walk(mas); > + if (*entry) > + return true; > } > > if (unlikely(!mas_searchable(mas))) { > @@ -6170,22 +6200,72 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min) > */ > mas->last = mas->index = 0; > mas->node = MAS_ROOT; > - return mas_root(mas); > + *entry = mas_root(mas); > + return true; > } > } > > if (mas->index < min) > - return NULL; > + return true; > > - /* Retries on dead nodes handled by mas_prev_slot */ > - return mas_prev_slot(mas, min, false); > + return false; > > none: > mas->node = MAS_NONE; > - return NULL; > + return true; > +} > + > +/** > + * mas_find_rev: On the first call, find the first non-null entry at or below > + * mas->index down to %min. Otherwise find the first non-null entry below > + * mas->index down to %min. > + * @mas: The maple state > + * @min: The minimum value to check. > + * > + * Must hold rcu_read_lock or the write lock. > + * If an entry exists, last and index are updated accordingly. > + * May set @mas->node to MAS_NONE. > + * > + * Return: The entry or %NULL. > + */ > +void *mas_find_rev(struct ma_state *mas, unsigned long min) > +{ > + void *entry; > + > + if (mas_find_rev_setup(mas, min, &entry)) > + return entry; > + > + /* Retries on dead nodes handled by mas_prev_slot */ > + return mas_prev_slot(mas, min, false); > + > } > EXPORT_SYMBOL_GPL(mas_find_rev); > > +/** > + * mas_find_range_rev: On the first call, find the first non-null entry at or > + * below mas->index down to %min. Otherwise advance to the previous slot after > + * mas->index down to %min. > + * @mas: The maple state > + * @min: The minimum value to check. > + * > + * Must hold rcu_read_lock or the write lock. > + * If an entry exists, last and index are updated accordingly. > + * May set @mas->node to MAS_NONE. > + * > + * Return: The entry or %NULL. > + */ > +void *mas_find_range_rev(struct ma_state *mas, unsigned long min) > +{ > + void *entry; > + > + if (mas_find_rev_setup(mas, min, &entry)) > + return entry; > + > + /* Retries on dead nodes handled by mas_prev_slot */ > + return mas_prev_slot(mas, min, true); > +} > +EXPORT_SYMBOL_GPL(mas_find_range_rev); > + > /** > * mas_erase() - Find the range in which index resides and erase the entire > * range. > > -- > 2.39.2 >