[PATCH 2/2] powerpc - Make the irq reverse mapping radix tree lockless

[Benjamin Herrenschmidt]

On Wed, 2008-08-06 at 15:30 +0200, Sebastien Dugue wrote:
> The radix trees used by interrupt controllers for their irq reverse mapping
> (currently only the XICS found on pSeries) have a complex locking scheme
> dating back to before the advent of the lockless radix tree.
> 
>   Take advantage of this and of the fact that the items of the tree are
> pointers to a static array (irq_map) elements which can never go under us
> to simplify the locking.
> 
>   Concurrency between readers and writers is handled by the intrinsic
> properties of the lockless radix tree. Concurrency between writers is handled
> with a spinlock added to the irq_host structure.

No need for a spinlock in the irq_host. Make it one global lock, it's
not like scalability of irq_create_mapping() was a big deal and there's
usually only one of those type of hosts anyway.

> 
> Signed-off-by: Sebastien Dugue <sebastien.dugue at bull.net>
> Cc: Paul Mackerras <paulus at samba.org>
> Cc: Benjamin Herrenschmidt <benh at kernel.crashing.org>
> Cc: Michael Ellerman <michael at ellerman.id.au>
> ---
>  arch/powerpc/include/asm/irq.h |    1 +
>  arch/powerpc/kernel/irq.c      |   74 ++++++----------------------------------
>  2 files changed, 12 insertions(+), 63 deletions(-)
> 
> diff --git a/arch/powerpc/include/asm/irq.h b/arch/powerpc/include/asm/irq.h
> index 0a51376..72fd036 100644
> --- a/arch/powerpc/include/asm/irq.h
> +++ b/arch/powerpc/include/asm/irq.h
> @@ -119,6 +119,7 @@ struct irq_host {
>  		} linear;
>  		struct radix_tree_root tree;
>  	} revmap_data;
> +	spinlock_t		tree_lock;
>  	struct irq_host_ops	*ops;
>  	void			*host_data;
>  	irq_hw_number_t		inval_irq;
> diff --git a/arch/powerpc/kernel/irq.c b/arch/powerpc/kernel/irq.c
> index dc8663a..7a19103 100644
> --- a/arch/powerpc/kernel/irq.c
> +++ b/arch/powerpc/kernel/irq.c
> @@ -439,8 +439,6 @@ void do_softirq(void)
>  
>  static LIST_HEAD(irq_hosts);
>  static DEFINE_SPINLOCK(irq_big_lock);
> -static DEFINE_PER_CPU(unsigned int, irq_radix_reader);
> -static unsigned int irq_radix_writer;
>  static atomic_t revmap_trees_allocated = ATOMIC_INIT(0);
>  struct irq_map_entry irq_map[NR_IRQS];
>  static unsigned int irq_virq_count = NR_IRQS;
> @@ -584,57 +582,6 @@ void irq_set_virq_count(unsigned int count)
>  		irq_virq_count = count;
>  }
>  
> -/* radix tree not lockless safe ! we use a brlock-type mecanism
> - * for now, until we can use a lockless radix tree
> - */
> -static void irq_radix_wrlock(unsigned long *flags)
> -{
> -	unsigned int cpu, ok;
> -
> -	spin_lock_irqsave(&irq_big_lock, *flags);
> -	irq_radix_writer = 1;
> -	smp_mb();
> -	do {
> -		barrier();
> -		ok = 1;
> -		for_each_possible_cpu(cpu) {
> -			if (per_cpu(irq_radix_reader, cpu)) {
> -				ok = 0;
> -				break;
> -			}
> -		}
> -		if (!ok)
> -			cpu_relax();
> -	} while(!ok);
> -}
> -
> -static void irq_radix_wrunlock(unsigned long flags)
> -{
> -	smp_wmb();
> -	irq_radix_writer = 0;
> -	spin_unlock_irqrestore(&irq_big_lock, flags);
> -}
> -
> -static void irq_radix_rdlock(unsigned long *flags)
> -{
> -	local_irq_save(*flags);
> -	__get_cpu_var(irq_radix_reader) = 1;
> -	smp_mb();
> -	if (likely(irq_radix_writer == 0))
> -		return;
> -	__get_cpu_var(irq_radix_reader) = 0;
> -	smp_wmb();
> -	spin_lock(&irq_big_lock);
> -	__get_cpu_var(irq_radix_reader) = 1;
> -	spin_unlock(&irq_big_lock);
> -}
> -
> -static void irq_radix_rdunlock(unsigned long flags)
> -{
> -	__get_cpu_var(irq_radix_reader) = 0;
> -	local_irq_restore(flags);
> -}
> -
>  static int irq_setup_virq(struct irq_host *host, unsigned int virq,
>  			    irq_hw_number_t hwirq)
>  {
> @@ -789,7 +736,6 @@ void irq_dispose_mapping(unsigned int virq)
>  {
>  	struct irq_host *host;
>  	irq_hw_number_t hwirq;
> -	unsigned long flags;
>  
>  	if (virq == NO_IRQ)
>  		return;
> @@ -825,9 +771,9 @@ void irq_dispose_mapping(unsigned int virq)
>  		/* Check if radix tree allocated yet */
>  		if (atomic_read(&revmap_trees_allocated) == 0)
>  			break;
> -		irq_radix_wrlock(&flags);
> +		spin_lock(&host->tree_lock);
>  		radix_tree_delete(&host->revmap_data.tree, hwirq);
> -		irq_radix_wrunlock(flags);
> +		spin_unlock(&host->tree_lock);
>  		break;
>  	}
>  
> @@ -881,7 +827,6 @@ unsigned int irq_radix_revmap_lookup(struct irq_host *host,
>  {
>  	struct irq_map_entry *ptr;
>  	unsigned int virq = NO_IRQ;
> -	unsigned long flags;
>  
>  	WARN_ON(host->revmap_type != IRQ_HOST_MAP_TREE);
>  
> @@ -893,9 +838,11 @@ unsigned int irq_radix_revmap_lookup(struct irq_host *host,
>  		return irq_find_mapping(host, hwirq);
>  
>  	/* Now try to resolve */
> -	irq_radix_rdlock(&flags);
> +	/*
> +	 * No rcu_read_lock(ing) needed, the ptr returned can't go under us
> +	 * as it's referencing an entry in the static irq_map table.
> +	 */
>  	ptr = radix_tree_lookup(&host->revmap_data.tree, hwirq);
> -	irq_radix_rdunlock(flags);
>  
>  	/* Found it, return */
>  	if (ptr)
> @@ -907,7 +854,6 @@ unsigned int irq_radix_revmap_lookup(struct irq_host *host,
>  void irq_radix_revmap_insert(struct irq_host *host, unsigned int virq,
>  			     irq_hw_number_t hwirq)
>  {
> -	unsigned long flags;
>  
>  	WARN_ON(host->revmap_type != IRQ_HOST_MAP_TREE);
>  
> @@ -920,10 +866,10 @@ void irq_radix_revmap_insert(struct irq_host *host, unsigned int virq,
>  		return;
>  
>  	if (virq != NO_IRQ) {
> -		irq_radix_wrlock(&flags);
> +		spin_lock(&host->tree_lock);
>  		radix_tree_insert(&host->revmap_data.tree, hwirq,
>  				  &irq_map[virq]);
> -		irq_radix_wrunlock(flags);
> +		spin_unlock(&host->tree_lock);
>  	}
>  }
>  
> @@ -1041,8 +987,10 @@ static int irq_late_init(void)
>  	 * revmap_trees_allocated.
>  	 */
>  	list_for_each_entry(h, &irq_hosts, link) {
> -		if (h->revmap_type == IRQ_HOST_MAP_TREE)
> +		if (h->revmap_type == IRQ_HOST_MAP_TREE) {
>  			INIT_RADIX_TREE(&h->revmap_data.tree, GFP_ATOMIC);
> +			spin_lock_init(&h->tree_lock);
> +		}
>  	}
>  
>  	/*