From patchwork Fri Dec 15 22:04:49 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Matthew Wilcox X-Patchwork-Id: 10116635 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 8083F60231 for ; Fri, 15 Dec 2017 22:37:54 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 7158529F43 for ; Fri, 15 Dec 2017 22:37:54 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 657362A121; Fri, 15 Dec 2017 22:37: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 C363429F43 for ; Fri, 15 Dec 2017 22:37:53 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1757093AbdLOWgU (ORCPT ); Fri, 15 Dec 2017 17:36:20 -0500 Received: from bombadil.infradead.org ([65.50.211.133]:34124 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756330AbdLOWFU (ORCPT ); Fri, 15 Dec 2017 17:05:20 -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=joz6O4iTbA73WPIU53loS2w/oWzPGfu2gWXm9JHApzY=; b=B6/NOIg2pi/GVlhiZXQ6s3Enz a2JLz4JhLbnEXijP9QlcruQK5fb/UsRK0byCPCQTVLGfQyo723MnZa1J6olt2hk9vWYcjTkLqMRl/ JP5gfChOfV2g4ypkfb5AW18t+zc9KFLyadtE3FZ0amy2yQ6ehVWCqVVMlTptvD/AM8SGp4a/74pce y5J7bGZhLD83soZPFa+RpE/NiN6aQk6YYZ5K8sfoRA9L5oCvrGE50N/TRjbJgQdAtv03IN198KCVR Ob+WHCgP42aegjoEkSPVru6HEbDzGQ6Og9f9UqW1IrLIQcQNNyN7YQ3dr44IwXpplqNT650M+gSWR jkflC3Udw==; Received: from willy by bombadil.infradead.org with local (Exim 4.87 #1 (Red Hat Linux)) id 1ePy6J-0002O6-Tj; Fri, 15 Dec 2017 22:05:03 +0000 From: Matthew Wilcox To: linux-kernel@vger.kernel.org Cc: Matthew Wilcox , Ross Zwisler , David Howells , Shaohua Li , Jens Axboe , Rehas Sachdeva , Marc Zyngier , 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-raid@vger.kernel.org Subject: [PATCH v5 77/78] irqdomain: Convert to XArray Date: Fri, 15 Dec 2017 14:04:49 -0800 Message-Id: <20171215220450.7899-78-willy@infradead.org> X-Mailer: git-send-email 2.9.5 In-Reply-To: <20171215220450.7899-1-willy@infradead.org> References: <20171215220450.7899-1-willy@infradead.org> Sender: linux-fsdevel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-fsdevel@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Matthew Wilcox In a non-critical path, irqdomain wants to know how many entries are stored in the xarray, so add xa_count(). This is a pretty straightforward conversion; mostly just removing now-redundant locking. The only thing of note is just how much simpler irq_domain_fix_revmap() becomes. Signed-off-by: Matthew Wilcox Acked-by: Marc Zyngier --- include/linux/irqdomain.h | 10 ++++------ include/linux/xarray.h | 1 + kernel/irq/irqdomain.c | 39 ++++++++++----------------------------- lib/xarray.c | 25 +++++++++++++++++++++++++ 4 files changed, 40 insertions(+), 35 deletions(-) diff --git a/include/linux/irqdomain.h b/include/linux/irqdomain.h index a34355d19546..0efccfb9e9f1 100644 --- a/include/linux/irqdomain.h +++ b/include/linux/irqdomain.h @@ -33,8 +33,7 @@ #include #include #include -#include -#include +#include struct device_node; struct irq_domain; @@ -151,7 +150,7 @@ struct irq_domain_chip_generic; * @revmap_direct_max_irq: The largest hwirq that can be set for controllers that * support direct mapping * @revmap_size: Size of the linear map table @linear_revmap[] - * @revmap_tree: Radix map tree for hwirqs that don't fit in the linear map + * @revmap_array: hwirqs that don't fit in the linear map * @linear_revmap: Linear table of hwirq->virq reverse mappings */ struct irq_domain { @@ -177,8 +176,7 @@ struct irq_domain { irq_hw_number_t hwirq_max; unsigned int revmap_direct_max_irq; unsigned int revmap_size; - struct radix_tree_root revmap_tree; - struct mutex revmap_tree_mutex; + struct xarray revmap_array; unsigned int linear_revmap[]; }; @@ -378,7 +376,7 @@ extern void irq_dispose_mapping(unsigned int virq); * This is a fast path alternative to irq_find_mapping() that can be * called directly by irq controller code to save a handful of * instructions. It is always safe to call, but won't find irqs mapped - * using the radix tree. + * using the xarray. */ static inline unsigned int irq_linear_revmap(struct irq_domain *domain, irq_hw_number_t hwirq) diff --git a/include/linux/xarray.h b/include/linux/xarray.h index eba544f26b70..6af8b30a9310 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -145,6 +145,7 @@ int xa_get_entries(struct xarray *, void **dst, unsigned long start, unsigned long max, unsigned int n); int xa_get_tagged(struct xarray *, void **dst, unsigned long start, unsigned long max, unsigned int n, xa_tag_t); +unsigned long xa_count(struct xarray *); /** * xa_get_maybe_tag() - Copy entries from the XArray into a normal array. diff --git a/kernel/irq/irqdomain.c b/kernel/irq/irqdomain.c index 4f4f60015e8a..8225fe042f8a 100644 --- a/kernel/irq/irqdomain.c +++ b/kernel/irq/irqdomain.c @@ -114,7 +114,7 @@ EXPORT_SYMBOL_GPL(irq_domain_free_fwnode); /** * __irq_domain_add() - Allocate a new irq_domain data structure * @fwnode: firmware node for the interrupt controller - * @size: Size of linear map; 0 for radix mapping only + * @size: Size of linear map; 0 for xarray mapping only * @hwirq_max: Maximum number of interrupts supported by controller * @direct_max: Maximum value of direct maps; Use ~0 for no limit; 0 for no * direct mapping @@ -209,8 +209,7 @@ struct irq_domain *__irq_domain_add(struct fwnode_handle *fwnode, int size, of_node_get(of_node); /* Fill structure */ - INIT_RADIX_TREE(&domain->revmap_tree, GFP_KERNEL); - mutex_init(&domain->revmap_tree_mutex); + xa_init(&domain->revmap_array); domain->ops = ops; domain->host_data = host_data; domain->hwirq_max = hwirq_max; @@ -241,7 +240,7 @@ void irq_domain_remove(struct irq_domain *domain) mutex_lock(&irq_domain_mutex); debugfs_remove_domain_dir(domain); - WARN_ON(!radix_tree_empty(&domain->revmap_tree)); + WARN_ON(!xa_empty(&domain->revmap_array)); list_del(&domain->link); @@ -462,9 +461,7 @@ static void irq_domain_clear_mapping(struct irq_domain *domain, if (hwirq < domain->revmap_size) { domain->linear_revmap[hwirq] = 0; } else { - mutex_lock(&domain->revmap_tree_mutex); - radix_tree_delete(&domain->revmap_tree, hwirq); - mutex_unlock(&domain->revmap_tree_mutex); + xa_erase(&domain->revmap_array, hwirq); } } @@ -475,9 +472,7 @@ static void irq_domain_set_mapping(struct irq_domain *domain, if (hwirq < domain->revmap_size) { domain->linear_revmap[hwirq] = irq_data->irq; } else { - mutex_lock(&domain->revmap_tree_mutex); - radix_tree_insert(&domain->revmap_tree, hwirq, irq_data); - mutex_unlock(&domain->revmap_tree_mutex); + xa_store(&domain->revmap_array, hwirq, irq_data, GFP_KERNEL); } } @@ -585,7 +580,7 @@ EXPORT_SYMBOL_GPL(irq_domain_associate_many); * This routine is used for irq controllers which can choose the hardware * interrupt numbers they generate. In such a case it's simplest to use * the linux irq as the hardware interrupt number. It still uses the linear - * or radix tree to store the mapping, but the irq controller can optimize + * or xarray to store the mapping, but the irq controller can optimize * the revmap path by using the hwirq directly. */ unsigned int irq_create_direct_mapping(struct irq_domain *domain) @@ -890,9 +885,7 @@ unsigned int irq_find_mapping(struct irq_domain *domain, if (hwirq < domain->revmap_size) return domain->linear_revmap[hwirq]; - rcu_read_lock(); - data = radix_tree_lookup(&domain->revmap_tree, hwirq); - rcu_read_unlock(); + data = xa_load(&domain->revmap_array, hwirq); return data ? data->irq : 0; } EXPORT_SYMBOL_GPL(irq_find_mapping); @@ -943,8 +936,6 @@ static int virq_debug_show(struct seq_file *m, void *private) unsigned long flags; struct irq_desc *desc; struct irq_domain *domain; - struct radix_tree_iter iter; - void __rcu **slot; int i; seq_printf(m, " %-16s %-6s %-10s %-10s %s\n", @@ -953,7 +944,6 @@ static int virq_debug_show(struct seq_file *m, void *private) list_for_each_entry(domain, &irq_domain_list, link) { struct device_node *of_node; const char *name; - int count = 0; of_node = irq_domain_get_of_node(domain); @@ -965,8 +955,7 @@ static int virq_debug_show(struct seq_file *m, void *private) else name = ""; - radix_tree_for_each_slot(slot, &domain->revmap_tree, &iter, 0) - count++; + count = xa_count(&domain->revmap_array); seq_printf(m, "%c%-16s %6u %10u %10u %s\n", domain == irq_default_domain ? '*' : ' ', domain->name, domain->revmap_size + count, domain->revmap_size, @@ -1452,17 +1441,9 @@ int __irq_domain_alloc_irqs(struct irq_domain *domain, int irq_base, /* The irq_data was moved, fix the revmap to refer to the new location */ static void irq_domain_fix_revmap(struct irq_data *d) { - void __rcu **slot; - if (d->hwirq < d->domain->revmap_size) - return; /* Not using radix tree. */ - - /* Fix up the revmap. */ - mutex_lock(&d->domain->revmap_tree_mutex); - slot = radix_tree_lookup_slot(&d->domain->revmap_tree, d->hwirq); - if (slot) - radix_tree_replace_slot(&d->domain->revmap_tree, slot, d); - mutex_unlock(&d->domain->revmap_tree_mutex); + return; + xa_store(&d->domain->revmap_array, d->hwirq, d, GFP_KERNEL); } /** diff --git a/lib/xarray.c b/lib/xarray.c index 013e81281465..b94f71e30007 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1518,6 +1518,31 @@ int xa_get_tagged(struct xarray *xa, void **dst, unsigned long start, } EXPORT_SYMBOL(xa_get_tagged); +/** + * xa_count() - Count the number of present entries in the XArray + * @xa: XArray. + * + * This function walks the XArray counting how many entries are present. + * If every entry in the XArray is full, this function will return 0. If + * this is a theoretical possibility, check xa_empty() first. + * + * This is a naive implementation; faster implementations are possible. + * If speed is important, consider maintaining a count variable in your + * own data structure. + */ +unsigned long xa_count(struct xarray *xa) +{ + XA_STATE(xas, xa, 0); + void *p; + unsigned long count = 0; + + xas_for_each(&xas, p, ULONG_MAX) + count++; + + return count; +} +EXPORT_SYMBOL(xa_count); + /** * xa_destroy() - Free all internal data structures. * @xa: XArray.