From patchwork Wed Dec 6 00:41:00 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Matthew Wilcox X-Patchwork-Id: 10094683 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 9DAB260329 for ; Wed, 6 Dec 2017 01:04:54 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 8E6D3287A9 for ; Wed, 6 Dec 2017 01:04:54 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 82AFF2898B; Wed, 6 Dec 2017 01:04:54 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=unavailable version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id E0EEA28914 for ; Wed, 6 Dec 2017 01:04:53 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754233AbdLFBBJ (ORCPT ); Tue, 5 Dec 2017 20:01:09 -0500 Received: from bombadil.infradead.org ([65.50.211.133]:38478 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753312AbdLFAmK (ORCPT ); Tue, 5 Dec 2017 19:42:10 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20170209; h=References:In-Reply-To:Message-Id: Date:Subject:Cc:To:From:Sender:Reply-To:MIME-Version:Content-Type: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=AXXTTHvRGS+LGwjVBrjg6HZTR67CKbeYW/Kx0n2iUCM=; b=YYFvu1X51lVv0owzA8mQ/1Sjr oPeVrdUJQ1KLNE5l22leGWsZ4st/aRPnRM4vWzHowCQ4jlGeXXG7ETMfcuVq8QwzHILSYxdbK9k+G c/Ke3fULIC49bkzCuBuN6E/jf0D3JuJ+N3Bcglt//yjEzkxROdvUXqgFpx8jyrz31Dmxgrqs9fOfz 3r7mqFagJemt9g93Q7gVdd8PmHSoNYt+ceWBa/YGd6dx9wrb8HvH83hCM7PMNIxsYwSI5ZlClexpc lvjcmLirvyH+A/iS3nRTGbnZ/sCDTlDDCrH/urQFcJoJUJHf7vwcekv5n7zUywWP8K+J2q5GqXqwU U0280TqxA==; Received: from willy by bombadil.infradead.org with local (Exim 4.87 #1 (Red Hat Linux)) id 1eMNmo-000120-WE; Wed, 06 Dec 2017 00:42:07 +0000 From: Matthew Wilcox Cc: Matthew Wilcox , Ross Zwisler , Jens Axboe , Rehas Sachdeva , linux-mm@kvack.org, linux-fsdevel@vger.kernel.org, linux-f2fs-devel@lists.sourceforge.net, linux-nilfs@vger.kernel.org, linux-btrfs@vger.kernel.org, linux-xfs@vger.kernel.org, linux-usb@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [PATCH v4 14/73] xarray: Add xas_for_each_tag Date: Tue, 5 Dec 2017 16:41:00 -0800 Message-Id: <20171206004159.3755-15-willy@infradead.org> X-Mailer: git-send-email 2.9.5 In-Reply-To: <20171206004159.3755-1-willy@infradead.org> References: <20171206004159.3755-1-willy@infradead.org> To: unlisted-recipients:; (no To-header on input) Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Matthew Wilcox This iterator operates across each tagged entry in the specified range. We do not yet have a user for an xa_for_each_tag iterator, but it would be straight-forward to add one if needed. This commit also includes xas_find_tag() and xas_next_tag(). Signed-off-by: Matthew Wilcox --- include/linux/xarray.h | 68 +++++++++++++++++++++++++++++++++++++++++++ lib/xarray.c | 78 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 146 insertions(+) diff --git a/include/linux/xarray.h b/include/linux/xarray.h index a62baf6f1a28..4e61ebd406f5 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -554,6 +554,7 @@ void *xas_find(struct xa_state *, unsigned long max); bool xas_get_tag(const struct xa_state *, xa_tag_t); void xas_set_tag(const struct xa_state *, xa_tag_t); void xas_clear_tag(const struct xa_state *, xa_tag_t); +void *xas_find_tag(struct xa_state *, unsigned long max, xa_tag_t); void xas_init_tags(const struct xa_state *); bool xas_nomem(struct xa_state *, gfp_t); @@ -676,6 +677,55 @@ static inline void *xas_next_entry(struct xa_state *xas, unsigned long max) return entry; } +/* Private */ +static inline unsigned int xas_find_chunk(struct xa_state *xas, bool advance, + xa_tag_t tag) +{ + unsigned long *addr = xas->xa_node->tags[(__force unsigned)tag]; + unsigned int offset = xas->xa_offset; + + if (advance) + offset++; + if (XA_CHUNK_SIZE == BITS_PER_LONG) { + unsigned long data = *addr & (~0UL << offset); + if (data) + return __ffs(data); + return XA_CHUNK_SIZE; + } + + return find_next_bit(addr, XA_CHUNK_SIZE, offset); +} + +/** + * xas_next_tag() - Advance iterator to next tagged entry. + * @xas: XArray operation state. + * @max: Highest index to return. + * @tag: Tag to search for. + * + * xas_next_tag() is an inline function to optimise xarray traversal for + * speed. It is equivalent to calling xas_find_tag(), and will call + * xas_find_tag() for all the hard cases. + * + * Return: The next tagged entry after the one currently referred to by @xas. + */ +static inline void *xas_next_tag(struct xa_state *xas, unsigned long max, + xa_tag_t tag) +{ + struct xa_node *node = xas->xa_node; + unsigned int offset; + + if (unlikely(xas_not_node(node) || xa_node_shift(node))) + return xas_find_tag(xas, max, tag); + offset = xas_find_chunk(xas, true, tag); + xas->xa_offset = offset; + xas->xa_index = (xas->xa_index & ~XA_CHUNK_MASK) + offset; + if (xas->xa_index > max) + return NULL; + if (offset == XA_CHUNK_SIZE) + return xas_find_tag(xas, max, tag); + return xa_entry(xas->xa, node, offset); +} + /* * If iterating while holding a lock, drop the lock and reschedule * every %XA_CHECK_SCHED loops. @@ -701,6 +751,24 @@ enum { for (entry = xas_find(xas, max); entry; \ entry = xas_next_entry(xas, max)) +/** + * xas_for_each_tag() - Iterate over a range of an XArray + * @xas: XArray operation state. + * @entry: Entry retrieved from array. + * @max: Maximum index to retrieve from array. + * @tag: Tag to search for. + * + * The loop body will be executed for each tagged entry in the xarray + * between the current xas position and @max. @entry will be set to + * the entry retrieved from the xarray. It is safe to delete entries + * from the array in the loop body. You should hold either the RCU lock + * or the xa_lock while iterating. If you need to drop the lock, call + * xas_pause() first. + */ +#define xas_for_each_tag(xas, entry, max, tag) \ + for (entry = xas_find_tag(xas, max, tag); entry; \ + entry = xas_next_tag(xas, max, tag)) + /* Internal functions, mostly shared between radix-tree.c, xarray.c and idr.c */ void xas_destroy(struct xa_state *); diff --git a/lib/xarray.c b/lib/xarray.c index ac4ff3daf476..f9eaac2d85f9 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -858,6 +858,84 @@ void *xas_find(struct xa_state *xas, unsigned long max) } EXPORT_SYMBOL_GPL(xas_find); +/** + * xas_find_tag() - Find the next tagged entry in the XArray. + * @xas: XArray operation state. + * @max: Highest index to return. + * @tag: Tag number to search for. + * + * If the xas has not yet been walked to an entry, return the tagged entry + * which has an index >= xas.xa_index. If it has been walked, the entry + * currently being pointed at has been processed, and so we move to the + * next tagged entry. + * + * If no tagged entry is found and the array is smaller than @max, @xas is + * set to the restart state and xas->xa_index is set to the smallest index + * not yet in the array. This allows @xas to be immediately passed to + * xas_create(). + * + * Return: The entry, if found, otherwise NULL. + */ +void *xas_find_tag(struct xa_state *xas, unsigned long max, xa_tag_t tag) +{ + bool advance = true; + unsigned int offset; + void *entry; + + if (xas_error(xas)) + return NULL; + + if (!xas->xa_node) { + xas->xa_index = 1; + goto out; + } else if (xas_top(xas->xa_node)) { + advance = false; + entry = xa_head(xas->xa); + if (xas->xa_index > max_index(entry)) + goto out; + if (!xa_is_node(entry)) { + if (xa_tagged(xas->xa, tag)) { + xas->xa_node = NULL; + return entry; + } + xas->xa_index = 1; + goto out; + } + xas->xa_node = xa_to_node(entry); + xas->xa_offset = xas->xa_index >> xas->xa_node->shift; + } + + while (xas->xa_index <= max) { + if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) { + xas->xa_offset = xas->xa_node->offset + 1; + xas->xa_node = xa_parent(xas->xa, xas->xa_node); + if (!xas->xa_node) + break; + advance = false; + continue; + } + + offset = xas_find_chunk(xas, advance, tag); + xas_add(xas, offset - xas->xa_offset); + if (offset == XA_CHUNK_SIZE) { + advance = false; + continue; + } + + entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); + if (!xa_is_node(entry)) + return entry; + xas->xa_node = xa_to_node(entry); + xas->xa_offset = get_offset(xas->xa_index, xas->xa_node); + } + + out: + if (!xas->xa_node) + xas->xa_node = XAS_BOUNDS; + return NULL; +} +EXPORT_SYMBOL_GPL(xas_find_tag); + /** * __xa_init() - Initialise an empty XArray. * @xa: XArray.