[PATCH 0/3 V2] powerpc - Make the irq reverse mapping tree lockless

[PATCH 0/3 V2] powerpc - Make the irq reverse mapping tree lockless

[Sebastien Dugue]

  Hi ,

  here is V2 of the patchset posted on July 31st updated from the comments
made by Michael Ellerman.

  V1 -> V2:

  - Initialize the XICS radix tree in xics code and only for that irq_host
    rather than doing it for all the hosts in the powerpc irq generic code
    (although the hosts list only contain one entry at the moment).

  - Add a comment in irq_radix_revmap_lookup() stating why it is safe to
    perform a lookup even if the radix tree has not been initialized yet.


  The goal of this patchset is to simplify the locking constraints on the radix
tree used for IRQ reverse mapping on the pSeries machines and provide lockless
access to this tree.

  This also solves the following BUG under preempt-rt:

BUG: sleeping function called from invalid context swapper(1) at kernel/rtmutex.c:739
in_atomic():1 [00000002], irqs_disabled():1
Call Trace:
[c0000001e20f3340] [c000000000010370] .show_stack+0x70/0x1bc (unreliable)
[c0000001e20f33f0] [c000000000049380] .__might_sleep+0x11c/0x138
[c0000001e20f3470] [c0000000002a2f64] .__rt_spin_lock+0x3c/0x98
[c0000001e20f34f0] [c0000000000c3f20] .kmem_cache_alloc+0x68/0x184
[c0000001e20f3590] [c000000000193f3c] .radix_tree_node_alloc+0xf0/0x144
[c0000001e20f3630] [c000000000195190] .radix_tree_insert+0x18c/0x2fc
[c0000001e20f36f0] [c00000000000c710] .irq_radix_revmap+0x1a4/0x1e4
[c0000001e20f37b0] [c00000000003b3f0] .xics_startup+0x30/0x54
[c0000001e20f3840] [c00000000008b864] .setup_irq+0x26c/0x370
[c0000001e20f38f0] [c00000000008ba68] .request_irq+0x100/0x158
[c0000001e20f39a0] [c0000000001ee9c0] .hvc_open+0xb4/0x148
[c0000001e20f3a40] [c0000000001d72ec] .tty_open+0x200/0x368
[c0000001e20f3af0] [c0000000000ce928] .chrdev_open+0x1f4/0x25c
[c0000001e20f3ba0] [c0000000000c8bf0] .__dentry_open+0x188/0x2c8
[c0000001e20f3c50] [c0000000000c8dec] .do_filp_open+0x50/0x70
[c0000001e20f3d70] [c0000000000c8e8c] .do_sys_open+0x80/0x148
[c0000001e20f3e20] [c00000000000928c] .init_post+0x4c/0x100
[c0000001e20f3ea0] [c0000000003c0e0c] .kernel_init+0x428/0x478
[c0000001e20f3f90] [c000000000027448] .kernel_thread+0x4c/0x68

  The root cause of this bug lies in the fact that the XICS interrupt
controller uses a radix tree for its reverse irq mapping and that we cannot
allocate the tree nodes (even GFP_ATOMIC) with preemption disabled.

  In fact, we have 2 nested preemption disabling when we want to allocate
a new node:

  - setup_irq() does a spin_lock_irqsave() before calling xics_startup() which
    then calls irq_radix_revmap() to insert a new node in the tree

  - irq_radix_revmap() also does a spin_lock_irqsave() (in irq_radix_wrlock())
    before the radix_tree_insert()

  Also, if an IRQ gets registered before the tree is initialized (namely the
IPI), it will be inserted into the tree in interrupt context once the tree
have been initialized, hence the need for a spin_lock_irqsave() in the
insertion path.

  This serie is split into 3 patches:

  - The first patch moves the initialization of the radix tree earlier in the
    boot process before any IRQ gets registered, but after the mm is up.

  - The second patch splits irq_radix_revmap() into its 2 components: one
    for lookup and one for insertion into the radix tree.

  - And finally, the third patch makes the radix tree fully lockless on the 
    lookup side.


  Here is the diffstat for the whole patchset:

 arch/powerpc/include/asm/irq.h        |   19 ++++-
 arch/powerpc/kernel/irq.c             |  130 +++++++--------------------------
 arch/powerpc/platforms/pseries/smp.c  |    1 +
 arch/powerpc/platforms/pseries/xics.c |   17 +++--
 arch/powerpc/platforms/pseries/xics.h |    1 +
 5 files changed, 56 insertions(+), 112 deletions(-)

  Thanks,

  Sebastien.

[PATCH 1/3] powerpc - Initialize the irq radix tree earlier

[Sebastien Dugue]

  The radix tree used for fast irq reverse mapping by the XICS is initialized
late in the boot process, after the first interrupt (IPI) gets registered
and after the first IPI is received.

  This patch moves the initialization of the XICS radix tree earlier into
the boot process in smp_xics_probe() (the mm is already up but no interrupts
have been registered at that point) to avoid having to insert a mapping into
the tree in interrupt context. This will help in simplifying the locking
constraints and move to a lockless radix tree in subsequent patches.


Signed-off-by: Sebastien Dugue <sebastien.dugue@bull.net>
Cc: Paul Mackerras <paulus@samba.org>
Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
Cc: Michael Ellerman <michael@ellerman.id.au>
---
 arch/powerpc/kernel/irq.c             |   17 -----------------
 arch/powerpc/platforms/pseries/smp.c  |    1 +
 arch/powerpc/platforms/pseries/xics.c |    5 +++++
 arch/powerpc/platforms/pseries/xics.h |    1 +
 4 files changed, 7 insertions(+), 17 deletions(-)

diff --git a/arch/powerpc/kernel/irq.c b/arch/powerpc/kernel/irq.c
index d972dec..9bef9f3 100644
--- a/arch/powerpc/kernel/irq.c
+++ b/arch/powerpc/kernel/irq.c
@@ -1016,23 +1016,6 @@ void irq_early_init(void)
 		get_irq_desc(i)->status |= IRQ_NOREQUEST;
 }
 
-/* We need to create the radix trees late */
-static int irq_late_init(void)
-{
-	struct irq_host *h;
-	unsigned long flags;
-
-	irq_radix_wrlock(&flags);
-	list_for_each_entry(h, &irq_hosts, link) {
-		if (h->revmap_type == IRQ_HOST_MAP_TREE)
-			INIT_RADIX_TREE(&h->revmap_data.tree, GFP_ATOMIC);
-	}
-	irq_radix_wrunlock(flags);
-
-	return 0;
-}
-arch_initcall(irq_late_init);
-
 #ifdef CONFIG_VIRQ_DEBUG
 static int virq_debug_show(struct seq_file *m, void *private)
 {
diff --git a/arch/powerpc/platforms/pseries/smp.c b/arch/powerpc/platforms/pseries/smp.c
index 9d8f8c8..3d4429a 100644
--- a/arch/powerpc/platforms/pseries/smp.c
+++ b/arch/powerpc/platforms/pseries/smp.c
@@ -130,6 +130,7 @@ static void smp_xics_message_pass(int target, int msg)
 
 static int __init smp_xics_probe(void)
 {
+	xics_radix_revmap_init();
 	xics_request_IPIs();
 
 	return cpus_weight(cpu_possible_map);
diff --git a/arch/powerpc/platforms/pseries/xics.c b/arch/powerpc/platforms/pseries/xics.c
index 0fc830f..d6e28f9 100644
--- a/arch/powerpc/platforms/pseries/xics.c
+++ b/arch/powerpc/platforms/pseries/xics.c
@@ -556,6 +556,11 @@ static struct irq_host_ops xics_host_ops = {
 	.xlate = xics_host_xlate,
 };
 
+void __init xics_radix_revmap_init(void)
+{
+	INIT_RADIX_TREE(&xics_host->revmap_data.tree, GFP_ATOMIC);
+}
+
 static void __init xics_init_host(void)
 {
 	if (firmware_has_feature(FW_FEATURE_LPAR))
diff --git a/arch/powerpc/platforms/pseries/xics.h b/arch/powerpc/platforms/pseries/xics.h
index 1c5321a..11490be 100644
--- a/arch/powerpc/platforms/pseries/xics.h
+++ b/arch/powerpc/platforms/pseries/xics.h
@@ -19,6 +19,7 @@ extern void xics_setup_cpu(void);
 extern void xics_teardown_cpu(void);
 extern void xics_kexec_teardown_cpu(int secondary);
 extern void xics_cause_IPI(int cpu);
+extern void xics_radix_revmap_init(void);
 extern  void xics_request_IPIs(void);
 extern void xics_migrate_irqs_away(void);
 
-- 
1.5.5.1

Re: [PATCH 1/3] powerpc - Initialize the irq radix tree earlier

[Benjamin Herrenschmidt]

On Mon, 2008-08-04 at 13:08 +0200, Sebastien Dugue wrote:
> The radix tree used for fast irq reverse mapping by the XICS is initialized
> late in the boot process, after the first interrupt (IPI) gets registered
> and after the first IPI is received.
> 
>   This patch moves the initialization of the XICS radix tree earlier into
> the boot process in smp_xics_probe() (the mm is already up but no interrupts
> have been registered at that point) to avoid having to insert a mapping into
> the tree in interrupt context. This will help in simplifying the locking
> constraints and move to a lockless radix tree in subsequent patches.

I'm not too happy with the moving of the radix tree init to platform
code.

The fact that the revmap code uses a radix tree should be mostly
transparent to the XICS code. I don't like adding this explicit code
from xics to initialize it.

I think the tree should still be initialized from generic code and it
can be done as late as we want as interrupts work without the tree being
there, they are just a bit slower.

I believe the right approach is:

 - Remove the populating of the tree from the revmap function as
   you already do
 - Move it to irq_create_mapping() for the normal case
 - For pre-existing interrupt, have the generic code that initializes
   the radix tree walk through all interrupts and setup the revmap for
   them. If that needs locking vs. concurrent irq_create_mapping, it's
   easy to use one of the available spinlocks for that.

Cheers,
Ben.


> Signed-off-by: Sebastien Dugue <sebastien.dugue@bull.net>
> Cc: Paul Mackerras <paulus@samba.org>
> Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
> Cc: Michael Ellerman <michael@ellerman.id.au>
> ---
>  arch/powerpc/kernel/irq.c             |   17 -----------------
>  arch/powerpc/platforms/pseries/smp.c  |    1 +
>  arch/powerpc/platforms/pseries/xics.c |    5 +++++
>  arch/powerpc/platforms/pseries/xics.h |    1 +
>  4 files changed, 7 insertions(+), 17 deletions(-)
> 
> diff --git a/arch/powerpc/kernel/irq.c b/arch/powerpc/kernel/irq.c
> index d972dec..9bef9f3 100644
> --- a/arch/powerpc/kernel/irq.c
> +++ b/arch/powerpc/kernel/irq.c
> @@ -1016,23 +1016,6 @@ void irq_early_init(void)
>  		get_irq_desc(i)->status |= IRQ_NOREQUEST;
>  }
>  
> -/* We need to create the radix trees late */
> -static int irq_late_init(void)
> -{
> -	struct irq_host *h;
> -	unsigned long flags;
> -
> -	irq_radix_wrlock(&flags);
> -	list_for_each_entry(h, &irq_hosts, link) {
> -		if (h->revmap_type == IRQ_HOST_MAP_TREE)
> -			INIT_RADIX_TREE(&h->revmap_data.tree, GFP_ATOMIC);
> -	}
> -	irq_radix_wrunlock(flags);
> -
> -	return 0;
> -}
> -arch_initcall(irq_late_init);
> -
>  #ifdef CONFIG_VIRQ_DEBUG
>  static int virq_debug_show(struct seq_file *m, void *private)
>  {
> diff --git a/arch/powerpc/platforms/pseries/smp.c b/arch/powerpc/platforms/pseries/smp.c
> index 9d8f8c8..3d4429a 100644
> --- a/arch/powerpc/platforms/pseries/smp.c
> +++ b/arch/powerpc/platforms/pseries/smp.c
> @@ -130,6 +130,7 @@ static void smp_xics_message_pass(int target, int msg)
>  
>  static int __init smp_xics_probe(void)
>  {
> +	xics_radix_revmap_init();
>  	xics_request_IPIs();
>  
>  	return cpus_weight(cpu_possible_map);
> diff --git a/arch/powerpc/platforms/pseries/xics.c b/arch/powerpc/platforms/pseries/xics.c
> index 0fc830f..d6e28f9 100644
> --- a/arch/powerpc/platforms/pseries/xics.c
> +++ b/arch/powerpc/platforms/pseries/xics.c
> @@ -556,6 +556,11 @@ static struct irq_host_ops xics_host_ops = {
>  	.xlate = xics_host_xlate,
>  };
>  
> +void __init xics_radix_revmap_init(void)
> +{
> +	INIT_RADIX_TREE(&xics_host->revmap_data.tree, GFP_ATOMIC);
> +}
> +
>  static void __init xics_init_host(void)
>  {
>  	if (firmware_has_feature(FW_FEATURE_LPAR))
> diff --git a/arch/powerpc/platforms/pseries/xics.h b/arch/powerpc/platforms/pseries/xics.h
> index 1c5321a..11490be 100644
> --- a/arch/powerpc/platforms/pseries/xics.h
> +++ b/arch/powerpc/platforms/pseries/xics.h
> @@ -19,6 +19,7 @@ extern void xics_setup_cpu(void);
>  extern void xics_teardown_cpu(void);
>  extern void xics_kexec_teardown_cpu(int secondary);
>  extern void xics_cause_IPI(int cpu);
> +extern void xics_radix_revmap_init(void);
>  extern  void xics_request_IPIs(void);
>  extern void xics_migrate_irqs_away(void);
>  

Re: [PATCH 1/3] powerpc - Initialize the irq radix tree earlier

[Benjamin Herrenschmidt]

>  - Remove the populating of the tree from the revmap function as
>    you already do
>  - Move it to irq_create_mapping() for the normal case
>  - For pre-existing interrupt, have the generic code that initializes
>    the radix tree walk through all interrupts and setup the revmap for
>    them. If that needs locking vs. concurrent irq_create_mapping, it's
>    easy to use one of the available spinlocks for that.

And in fact, you may even be able to avoid GFP_ATOMIC completely here
and switch it to GFP_KERNEL since irq_create_mapping() can sleep afaik,
provided that you avoid the spinlocking.

Ben.

Re: [PATCH 1/3] powerpc - Initialize the irq radix tree earlier

[Sebastien Dugue]

On Tue, 05 Aug 2008 11:05:03 +1000 Benjamin Herrenschmidt <benh@kernel.crashing.org> wrote:

> 
> >  - Remove the populating of the tree from the revmap function as
> >    you already do
> >  - Move it to irq_create_mapping() for the normal case
> >  - For pre-existing interrupt, have the generic code that initializes
> >    the radix tree walk through all interrupts and setup the revmap for
> >    them. If that needs locking vs. concurrent irq_create_mapping, it's
> >    easy to use one of the available spinlocks for that.
> 
> And in fact, you may even be able to avoid GFP_ATOMIC completely here
> and switch it to GFP_KERNEL since irq_create_mapping() can sleep afaik,
> provided that you avoid the spinlocking.

  Well, maybe, will have to look into this in details.

  Thanks,

  Sebastien.

> 
> Ben.
> 
> 
> 

Re: [PATCH 1/3] powerpc - Initialize the irq radix tree earlier

[Sebastien Dugue]

  Hi Benjamin,

On Tue, 05 Aug 2008 11:03:46 +1000 Benjamin Herrenschmidt <benh@kernel.crashing.org> wrote:

> On Mon, 2008-08-04 at 13:08 +0200, Sebastien Dugue wrote:
> > The radix tree used for fast irq reverse mapping by the XICS is initialized
> > late in the boot process, after the first interrupt (IPI) gets registered
> > and after the first IPI is received.
> > 
> >   This patch moves the initialization of the XICS radix tree earlier into
> > the boot process in smp_xics_probe() (the mm is already up but no interrupts
> > have been registered at that point) to avoid having to insert a mapping into
> > the tree in interrupt context. This will help in simplifying the locking
> > constraints and move to a lockless radix tree in subsequent patches.
> 
> I'm not too happy with the moving of the radix tree init to platform
> code.
> 
> The fact that the revmap code uses a radix tree should be mostly
> transparent to the XICS code. I don't like adding this explicit code
> from xics to initialize it.

  OK, I'm fine with that.

> 
> I think the tree should still be initialized from generic code and it
> can be done as late as we want as interrupts work without the tree being
> there, they are just a bit slower.
> 
> I believe the right approach is:
> 
>  - Remove the populating of the tree from the revmap function as
>    you already do
>  - Move it to irq_create_mapping() for the normal case

  Agreed.

>  - For pre-existing interrupt, have the generic code that initializes
>    the radix tree walk through all interrupts and setup the revmap for
>    them. If that needs locking vs. concurrent irq_create_mapping, it's
>    easy to use one of the available spinlocks for that.

  That's what I wanted to avoid to not add some new complexity, but I can
see that my approach makes some assumptions about initializations order
that I'm no longer comfortable with. Will do as you suggest as it's
way more explicit.

  Thanks a lot for your comments.

  Sebastien.

> 
> Cheers,
> Ben.
> 
> 
> > Signed-off-by: Sebastien Dugue <sebastien.dugue@bull.net>
> > Cc: Paul Mackerras <paulus@samba.org>
> > Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
> > Cc: Michael Ellerman <michael@ellerman.id.au>
> > ---
> >  arch/powerpc/kernel/irq.c             |   17 -----------------
> >  arch/powerpc/platforms/pseries/smp.c  |    1 +
> >  arch/powerpc/platforms/pseries/xics.c |    5 +++++
> >  arch/powerpc/platforms/pseries/xics.h |    1 +
> >  4 files changed, 7 insertions(+), 17 deletions(-)
> > 
> > diff --git a/arch/powerpc/kernel/irq.c b/arch/powerpc/kernel/irq.c
> > index d972dec..9bef9f3 100644
> > --- a/arch/powerpc/kernel/irq.c
> > +++ b/arch/powerpc/kernel/irq.c
> > @@ -1016,23 +1016,6 @@ void irq_early_init(void)
> >  		get_irq_desc(i)->status |= IRQ_NOREQUEST;
> >  }
> >  
> > -/* We need to create the radix trees late */
> > -static int irq_late_init(void)
> > -{
> > -	struct irq_host *h;
> > -	unsigned long flags;
> > -
> > -	irq_radix_wrlock(&flags);
> > -	list_for_each_entry(h, &irq_hosts, link) {
> > -		if (h->revmap_type == IRQ_HOST_MAP_TREE)
> > -			INIT_RADIX_TREE(&h->revmap_data.tree, GFP_ATOMIC);
> > -	}
> > -	irq_radix_wrunlock(flags);
> > -
> > -	return 0;
> > -}
> > -arch_initcall(irq_late_init);
> > -
> >  #ifdef CONFIG_VIRQ_DEBUG
> >  static int virq_debug_show(struct seq_file *m, void *private)
> >  {
> > diff --git a/arch/powerpc/platforms/pseries/smp.c b/arch/powerpc/platforms/pseries/smp.c
> > index 9d8f8c8..3d4429a 100644
> > --- a/arch/powerpc/platforms/pseries/smp.c
> > +++ b/arch/powerpc/platforms/pseries/smp.c
> > @@ -130,6 +130,7 @@ static void smp_xics_message_pass(int target, int msg)
> >  
> >  static int __init smp_xics_probe(void)
> >  {
> > +	xics_radix_revmap_init();
> >  	xics_request_IPIs();
> >  
> >  	return cpus_weight(cpu_possible_map);
> > diff --git a/arch/powerpc/platforms/pseries/xics.c b/arch/powerpc/platforms/pseries/xics.c
> > index 0fc830f..d6e28f9 100644
> > --- a/arch/powerpc/platforms/pseries/xics.c
> > +++ b/arch/powerpc/platforms/pseries/xics.c
> > @@ -556,6 +556,11 @@ static struct irq_host_ops xics_host_ops = {
> >  	.xlate = xics_host_xlate,
> >  };
> >  
> > +void __init xics_radix_revmap_init(void)
> > +{
> > +	INIT_RADIX_TREE(&xics_host->revmap_data.tree, GFP_ATOMIC);
> > +}
> > +
> >  static void __init xics_init_host(void)
> >  {
> >  	if (firmware_has_feature(FW_FEATURE_LPAR))
> > diff --git a/arch/powerpc/platforms/pseries/xics.h b/arch/powerpc/platforms/pseries/xics.h
> > index 1c5321a..11490be 100644
> > --- a/arch/powerpc/platforms/pseries/xics.h
> > +++ b/arch/powerpc/platforms/pseries/xics.h
> > @@ -19,6 +19,7 @@ extern void xics_setup_cpu(void);
> >  extern void xics_teardown_cpu(void);
> >  extern void xics_kexec_teardown_cpu(int secondary);
> >  extern void xics_cause_IPI(int cpu);
> > +extern void xics_radix_revmap_init(void);
> >  extern  void xics_request_IPIs(void);
> >  extern void xics_migrate_irqs_away(void);
> >  
> 
> 

[PATCH 2/3] powerpc - Separate the irq radix tree insertion and lookup

[Sebastien Dugue]

  irq_radix_revmap() currently serves 2 purposes, irq mapping lookup
and insertion which happen in interrupt and process context respectively.

  Separate the function into its 2 components, one for lookup only and one
for insertion only.


Signed-off-by: Sebastien Dugue <sebastien.dugue@bull.net>
Cc: Paul Mackerras <paulus@samba.org>
Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
Cc: Michael Ellerman <michael@ellerman.id.au>
---
 arch/powerpc/include/asm/irq.h        |   18 ++++++++++--
 arch/powerpc/kernel/irq.c             |   46 +++++++++++++++-----------------
 arch/powerpc/platforms/pseries/xics.c |   11 +++-----
 3 files changed, 41 insertions(+), 34 deletions(-)

diff --git a/arch/powerpc/include/asm/irq.h b/arch/powerpc/include/asm/irq.h
index a372f76..0a51376 100644
--- a/arch/powerpc/include/asm/irq.h
+++ b/arch/powerpc/include/asm/irq.h
@@ -236,15 +236,27 @@ extern unsigned int irq_find_mapping(struct irq_host *host,
 extern unsigned int irq_create_direct_mapping(struct irq_host *host);
 
 /**
- * irq_radix_revmap - Find a linux virq from a hw irq number.
+ * irq_radix_revmap_insert - Insert a hw irq to linux virq number mapping.
+ * @host: host owning this hardware interrupt
+ * @virq: linux irq number
+ * @hwirq: hardware irq number in that host space
+ *
+ * This is for use by irq controllers that use a radix tree reverse
+ * mapping for fast lookup.
+ */
+extern void irq_radix_revmap_insert(struct irq_host *host, unsigned int virq,
+				    irq_hw_number_t hwirq);
+
+/**
+ * irq_radix_revmap_lookup - Find a linux virq from a hw irq number.
  * @host: host owning this hardware interrupt
  * @hwirq: hardware irq number in that host space
  *
  * This is a fast path, for use by irq controller code that uses radix tree
  * revmaps
  */
-extern unsigned int irq_radix_revmap(struct irq_host *host,
-				     irq_hw_number_t hwirq);
+extern unsigned int irq_radix_revmap_lookup(struct irq_host *host,
+					    irq_hw_number_t hwirq);
 
 /**
  * irq_linear_revmap - Find a linux virq from a hw irq number.
diff --git a/arch/powerpc/kernel/irq.c b/arch/powerpc/kernel/irq.c
index 9bef9f3..ba24efd 100644
--- a/arch/powerpc/kernel/irq.c
+++ b/arch/powerpc/kernel/irq.c
@@ -821,9 +821,6 @@ void irq_dispose_mapping(unsigned int virq)
 			host->revmap_data.linear.revmap[hwirq] = NO_IRQ;
 		break;
 	case IRQ_HOST_MAP_TREE:
-		/* Check if radix tree allocated yet */
-		if (host->revmap_data.tree.gfp_mask == 0)
-			break;
 		irq_radix_wrlock(&flags);
 		radix_tree_delete(&host->revmap_data.tree, hwirq);
 		irq_radix_wrunlock(flags);
@@ -875,43 +872,44 @@ unsigned int irq_find_mapping(struct irq_host *host,
 EXPORT_SYMBOL_GPL(irq_find_mapping);
 
 
-unsigned int irq_radix_revmap(struct irq_host *host,
-			      irq_hw_number_t hwirq)
+unsigned int irq_radix_revmap_lookup(struct irq_host *host,
+				     irq_hw_number_t hwirq)
 {
-	struct radix_tree_root *tree;
 	struct irq_map_entry *ptr;
-	unsigned int virq;
+	unsigned int virq = NO_IRQ;
 	unsigned long flags;
 
 	WARN_ON(host->revmap_type != IRQ_HOST_MAP_TREE);
 
-	/* Check if the radix tree exist yet. We test the value of
-	 * the gfp_mask for that. Sneaky but saves another int in the
-	 * structure. If not, we fallback to slow mode
+	/* Note: It is safe to call radix_tree_lookup() here, even before the
+	 * tree gets initialized because the struct irq_host is zallocated
+	 * and radix_tree_lookup() returns NULL when root->rnode is found
+	 * to be NULL.
+	 * IOW, for any interrupt taken before the tree is initialized, we
+	 * return NO_IRQ.
 	 */
-	tree = &host->revmap_data.tree;
-	if (tree->gfp_mask == 0)
-		return irq_find_mapping(host, hwirq);
-
-	/* Now try to resolve */
 	irq_radix_rdlock(&flags);
-	ptr = radix_tree_lookup(tree, hwirq);
+	ptr = radix_tree_lookup(&host->revmap_data.tree, hwirq);
 	irq_radix_rdunlock(flags);
 
-	/* Found it, return */
-	if (ptr) {
+	if (ptr)
 		virq = ptr - irq_map;
-		return virq;
-	}
 
-	/* If not there, try to insert it */
-	virq = irq_find_mapping(host, hwirq);
+	return virq;
+}
+
+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);
+
 	if (virq != NO_IRQ) {
 		irq_radix_wrlock(&flags);
-		radix_tree_insert(tree, hwirq, &irq_map[virq]);
+		radix_tree_insert(&host->revmap_data.tree, hwirq, &irq_map[virq]);
 		irq_radix_wrunlock(flags);
 	}
-	return virq;
 }
 
 unsigned int irq_linear_revmap(struct irq_host *host,
diff --git a/arch/powerpc/platforms/pseries/xics.c b/arch/powerpc/platforms/pseries/xics.c
index d6e28f9..8c7f058 100644
--- a/arch/powerpc/platforms/pseries/xics.c
+++ b/arch/powerpc/platforms/pseries/xics.c
@@ -310,12 +310,6 @@ static void xics_mask_irq(unsigned int virq)
 
 static unsigned int xics_startup(unsigned int virq)
 {
-	unsigned int irq;
-
-	/* force a reverse mapping of the interrupt so it gets in the cache */
-	irq = (unsigned int)irq_map[virq].hwirq;
-	irq_radix_revmap(xics_host, irq);
-
 	/* unmask it */
 	xics_unmask_irq(virq);
 	return 0;
@@ -346,7 +340,7 @@ static inline unsigned int xics_remap_irq(unsigned int vec)
 
 	if (vec == XICS_IRQ_SPURIOUS)
 		return NO_IRQ;
-	irq = irq_radix_revmap(xics_host, vec);
+	irq = irq_radix_revmap_lookup(xics_host, vec);
 	if (likely(irq != NO_IRQ))
 		return irq;
 
@@ -530,6 +524,9 @@ static int xics_host_map(struct irq_host *h, unsigned int virq,
 {
 	pr_debug("xics: map virq %d, hwirq 0x%lx\n", virq, hw);
 
+	/* Insert the interrupt mapping into the radix tree for fast lookup */
+	irq_radix_revmap_insert(xics_host, virq, hw);
+
 	get_irq_desc(virq)->status |= IRQ_LEVEL;
 	set_irq_chip_and_handler(virq, xics_irq_chip, handle_fasteoi_irq);
 	return 0;
-- 
1.5.5.1

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

[Sebastien Dugue]

  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.


Signed-off-by: Sebastien Dugue <sebastien.dugue@bull.net>
Cc: Paul Mackerras <paulus@samba.org>
Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
Cc: Michael Ellerman <michael@ellerman.id.au>
---
 arch/powerpc/include/asm/irq.h        |    1 +
 arch/powerpc/kernel/irq.c             |   71 ++++-----------------------------
 arch/powerpc/platforms/pseries/xics.c |    1 +
 3 files changed, 10 insertions(+), 63 deletions(-)

diff --git a/arch/powerpc/include/asm/irq.h b/arch/powerpc/include/asm/irq.h
index 0a51376..43b6062 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 ba24efd..5d63255 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;
 struct irq_map_entry irq_map[NR_IRQS];
 static unsigned int irq_virq_count = NR_IRQS;
 static struct irq_host *irq_default_host;
@@ -583,57 +581,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)
 {
@@ -788,7 +735,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;
@@ -821,9 +767,9 @@ void irq_dispose_mapping(unsigned int virq)
 			host->revmap_data.linear.revmap[hwirq] = NO_IRQ;
 		break;
 	case IRQ_HOST_MAP_TREE:
-		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;
 	}
 
@@ -877,7 +823,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);
 
@@ -888,9 +833,11 @@ unsigned int irq_radix_revmap_lookup(struct irq_host *host,
 	 * IOW, for any interrupt taken before the tree is initialized, we
 	 * return NO_IRQ.
 	 */
-	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);
 
 	if (ptr)
 		virq = ptr - irq_map;
@@ -901,14 +848,12 @@ 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);
 
 	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);
 	}
 }
 
diff --git a/arch/powerpc/platforms/pseries/xics.c b/arch/powerpc/platforms/pseries/xics.c
index 8c7f058..014439f 100644
--- a/arch/powerpc/platforms/pseries/xics.c
+++ b/arch/powerpc/platforms/pseries/xics.c
@@ -556,6 +556,7 @@ static struct irq_host_ops xics_host_ops = {
 void __init xics_radix_revmap_init(void)
 {
 	INIT_RADIX_TREE(&xics_host->revmap_data.tree, GFP_ATOMIC);
+	spin_lock_init(&xics_host->tree_lock);
 }
 
 static void __init xics_init_host(void)
-- 
1.5.5.1

Re: [PATCH 3/3] powerpc - Make the irq reverse mapping radix tree lockless

[Daniel Walker]

On Mon, 2008-08-04 at 13:08 +0200, Sebastien Dugue wrote:

> --- 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;

You have a tabbing issue above..

Daniel

Re: [PATCH 3/3] powerpc - Make the irq reverse mapping radix tree lockless

[Sebastien Dugue]

On Mon, 04 Aug 2008 09:31:36 -0700 Daniel Walker <dwalker@mvista.com> wrote:

> On Mon, 2008-08-04 at 13:08 +0200, Sebastien Dugue wrote:
> 
> > --- 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;
> 
> You have a tabbing issue above..

  Yuck, right.

  Thanks,

  Sebastien.