powerpc - fix bug in irq reverse mapping radix tree (Resend)

PATCH In review Sebastien Dugue 4 participants 12 messages Jul 24, 2008 – Jul 25, 2008 PowerPC

lore

Share & tools

lore

Sebastien Dugue

author

2008-07-24 10:51 UTC #0 lore raw

cover powerpc - fix bug in irq reverse mapping radix tree (Resend)

(This is resend as vger dropped my previous attempt, sorry for the duplication)

Hi,

here are 2 patches for fixing the following bug occuring on IBM pSeries under
an RT kernel:

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()

The first patch moves the call to irq_radix_revmap() from xics_startup() out to
xics_host_map_direct() and xics_host_map_lpar() which are called with preemption enabled.

The second patch is a little more involved in that it takes advantage of
the concurrent radix tree to simplify the locking requirements and allows to allocate a new node outside a preemption disabled section.

I just hope I've correctly understood the concurrent radix trees semantic
and got the (absence of) locking right.

Sebastien.

Sebastien Dugue

author

2008-07-24 10:51 UTC #1 lore raw

PATCH 1/2 powerpc - XICS: move the call to irq_radix_revmap from xics_startup to xics_host_map

From: Sebastien Dugue <[email protected]>
Date: Tue, 22 Jul 2008 13:05:24 +0200
Subject: [PATCH][RT] powerpc - XICS: move the call to irq_radix_revmap from xics_startup to xics_host_map

This patch moves the insertion of an irq into the reverse mapping radix tree
from xics_startup() into xics_host_map().

The reason for this change is that xics_startup() is called with preemption
disabled (which is not the case for xics_host_map()) which is a problem under a preempt-rt kernel as we cannot even allocate GFP_ATOMIC memory for the radix tree nodes.

Signed-off-by Sebastien Dugue <[email protected]>

Cc Benjamin Herrenschmidt <[email protected]>

Cc Paul Mackerras <[email protected]>

Cc Michael Ellerman <[email protected]>

---
 arch/powerpc/platforms/pseries/xics.c |   18 ++++++++++++------
 1 file changed, 12 insertions(+), 6 deletions(-)

arch/powerpc/platforms/pseries/xics.c +12 -6

Index: linux-2.6.25.8-rt7/arch/powerpc/platforms/pseries/xics.c
===================================================================
@@ -311,12 +311,6 @@ static void xics_mask_irq(unsigned int v
 
 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;

@@ -529,8 +523,14 @@ static int xics_host_match(struct irq_ho
 static int xics_host_map_direct(struct irq_host *h, unsigned int virq,
 				irq_hw_number_t hw)
 {
+	unsigned int irq;
+
 	pr_debug("xics: map_direct virq %d, hwirq 0x%lx\n", virq, hw);
 
+	/* 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);
+
 	get_irq_desc(virq)->status |= IRQ_LEVEL;
 	set_irq_chip_and_handler(virq, &xics_pic_direct, handle_fasteoi_irq);
 	return 0;

@@ -539,8 +539,14 @@ static int xics_host_map_direct(struct i
 static int xics_host_map_lpar(struct irq_host *h, unsigned int virq,
 			      irq_hw_number_t hw)
 {
+	unsigned int irq;
+
 	pr_debug("xics: map_direct virq %d, hwirq 0x%lx\n", virq, hw);
 
+	/* 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);
+
 	get_irq_desc(virq)->status |= IRQ_LEVEL;
 	set_irq_chip_and_handler(virq, &xics_pic_lpar, handle_fasteoi_irq);
 	return 0;

Sebastien Dugue

author

2008-07-24 10:51 UTC #2 lore raw

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

In reply to Sebastien Dugue

From: Sebastien Dugue <[email protected]>
Date: Tue, 22 Jul 2008 11:56:41 +0200
Subject: [PATCH][RT] powerpc - Make the irq reverse mapping radix tree lockless

The radix tree 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 concurrent radix tree on preempt-rt.

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 are handled by the intrinsic
properties of the concurrent radix tree. Concurrency between the tree initialization which is done asynchronously with readers and writers access is handled via an atomic variable (revmap_trees_allocated) set when the tree has been initialized and checked before any reader or writer access just like we used to check for tree.gfp_mask != 0 before.

Signed-off-by Sebastien Dugue <[email protected]>

Cc Benjamin Herrenschmidt <[email protected]>

Cc Paul Mackerras <[email protected]>

---
 arch/powerpc/kernel/irq.c |  102 ++++++++++++----------------------------------
 1 file changed, 27 insertions(+), 75 deletions(-)

arch/powerpc/kernel/irq.c +27 ~~-75~~

Index: linux-2.6.25.8-rt7/arch/powerpc/kernel/irq.c
===================================================================
@@ -403,8 +403,7 @@ void do_softirq(void)
 
 static LIST_HEAD(irq_hosts);
 static DEFINE_RAW_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;
 static struct irq_host *irq_default_host;

@@ -547,57 +546,6 @@ void irq_set_virq_count(unsigned int cou
 		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)
 {

@@ -752,7 +700,6 @@ void irq_dispose_mapping(unsigned int vi
 {
 	struct irq_host *host;
 	irq_hw_number_t hwirq;
-	unsigned long flags;
 
 	if (virq == NO_IRQ)
 		return;

@@ -784,15 +731,20 @@ void irq_dispose_mapping(unsigned int vi
 		if (hwirq < host->revmap_data.linear.size)
 			host->revmap_data.linear.revmap[hwirq] = NO_IRQ;
 		break;
-	case IRQ_HOST_MAP_TREE:
+	case IRQ_HOST_MAP_TREE: {
+		DEFINE_RADIX_TREE_CONTEXT(ctx, &host->revmap_data.tree);
+
 		/* Check if radix tree allocated yet */
-		if (host->revmap_data.tree.gfp_mask == 0)
+		if (atomic_read(&revmap_trees_allocated) == 0)
 			break;
-		irq_radix_wrlock(&flags);
-		radix_tree_delete(&host->revmap_data.tree, hwirq);
-		irq_radix_wrunlock(flags);
+
+		radix_tree_lock(&ctx);
+		radix_tree_delete(ctx.tree, hwirq);
+		radix_tree_unlock(&ctx);
+
 		break;
 	}
+	}
 
 	/* Destroy map */
 	smp_mb();

@@ -845,22 +797,20 @@ unsigned int irq_radix_revmap(struct irq
 	struct radix_tree_root *tree;
 	struct irq_map_entry *ptr;
 	unsigned int virq;
-	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
-	 */
-	tree = &host->revmap_data.tree;
-	if (tree->gfp_mask == 0)
+	/* Check if the radix tree exist yet. */
+	if (atomic_read(&revmap_trees_allocated) == 0)
 		return irq_find_mapping(host, hwirq);
 
-	/* Now try to resolve */
-	irq_radix_rdlock(&flags);
+	/*
+	 * Now try to resolve
+	 * 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.
+	 */
+	tree = &host->revmap_data.tree;
 	ptr = radix_tree_lookup(tree, hwirq);
-	irq_radix_rdunlock(flags);
 
 	/* Found it, return */
 	if (ptr) {

@@ -871,9 +821,10 @@ unsigned int irq_radix_revmap(struct irq
 	/* If not there, try to insert it */
 	virq = irq_find_mapping(host, hwirq);
 	if (virq != NO_IRQ) {
-		irq_radix_wrlock(&flags);
-		radix_tree_insert(tree, hwirq, &irq_map[virq]);
-		irq_radix_wrunlock(flags);
+		DEFINE_RADIX_TREE_CONTEXT(ctx, tree);
+		radix_tree_lock(&ctx);
+		radix_tree_insert(ctx.tree, hwirq, &irq_map[virq]);
+		radix_tree_unlock(&ctx);
 	}
 	return virq;
 }

@@ -984,14 +935,15 @@ void irq_early_init(void)
 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);
+
+	/* Make sure the radix trees inits are visible before setting the flag */
+	smp_mb();
+	atomic_set(&revmap_trees_allocated, 1);
 
 	return 0;
 }

Nick Piggin

2008-07-24 11:11 UTC #3 lore raw

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

Quoted 14 lines · Sebastien Dugue

From: Sebastien Dugue <[email protected]>
Date: Tue, 22 Jul 2008 11:56:41 +0200
Subject: [PATCH][RT] powerpc - Make the irq reverse mapping radix tree lockless
The radix tree 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 concurrent radix tree on preempt-rt.
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.

Quoted 6 lines

Concurrency between readers and writers are handled by the intrinsic
properties of the concurrent radix tree. Concurrency between the tree initialization which is done asynchronously with readers and writers access is handled via an atomic variable (revmap_trees_allocated) set when the tree has been initialized and checked before any reader or writer access just like we used to check for tree.gfp_mask != 0 before.

Hmm, RCU radix tree is in mainline too for quite a while. I thought Ben had already converted this code over ages ago...

Nothing against the -rt patch, but mainline should probably be updated to use RCU as well?

Sebastien Dugue

author

2008-07-24 12:18 UTC #4 lore raw

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

Quoted 22 lines · On Thu, 24 Jul 2008 21:11:34 +1000 Nick Piggin <[email protected]> wrote:

Quoted 14 lines · Sebastien Dugue
From: Sebastien Dugue <[email protected]>
Date: Tue, 22 Jul 2008 11:56:41 +0200
Subject: [PATCH][RT] powerpc - Make the irq reverse mapping radix tree lockless
The radix tree 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 concurrent radix tree on preempt-rt.
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.
Quoted 6 lines
Concurrency between readers and writers are handled by the intrinsic
properties of the concurrent radix tree. Concurrency between the tree initialization which is done asynchronously with readers and writers access is handled via an atomic variable (revmap_trees_allocated) set when the tree has been initialized and checked before any reader or writer access just like we used to check for tree.gfp_mask != 0 before.

Quoted 2 lines

Hmm, RCU radix tree is in mainline too for quite a while. I thought Ben had already converted this code over ages ago...

Mainline does not have the concurrent radix tree which this patch
is based on, but maybe it's overkill and the RCU radix tree is enough. Not sure, will have to think about it a bit more.

Quoted 4 lines

Nothing against the -rt patch, but mainline should probably be updated to use RCU as well?

If rcu radix tree is enough, then definitely yes.

Sebastien.

Peter Zijlstra

2008-07-25 07:49 UTC #5 lore raw

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

Quoted 24 lines · Sebastien Dugue

Quoted 22 lines · On Thu, 24 Jul 2008 21:11:34 +1000 Nick Piggin <[email protected]> wrote:
Quoted 20 lines · Sebastien Dugue
From: Sebastien Dugue <[email protected]>
Date: Tue, 22 Jul 2008 11:56:41 +0200
Subject: [PATCH][RT] powerpc - Make the irq reverse mapping radix tree lockless
The radix tree 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 concurrent radix tree on preempt-rt.
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 are handled by the intrinsic
properties of the concurrent radix tree. Concurrency between the tree initialization which is done asynchronously with readers and writers access is handled via an atomic variable (revmap_trees_allocated) set when the tree has been initialized and checked before any reader or writer access just like we used to check for tree.gfp_mask != 0 before.

Quoted 6 lines

Quoted 2 lines
Hmm, RCU radix tree is in mainline too for quite a while. I thought Ben had already converted this code over ages ago...
Mainline does not have the concurrent radix tree which this patch
is based on, but maybe it's overkill and the RCU radix tree is enough. Not sure, will have to think about it a bit more.

Should be. The model of the concurrent radix tree can be mapped to spinlock + rcu radix tree.

So instead of:

arch/powerpc/kernel/irq.c unsigned int irq_radix_revmap(struct irq · line 827

Quoted 4 lines

+ DEFINE_RADIX_TREE_CONTEXT(ctx, tree);

arch/powerpc/kernel/irq.c +3 -0

+               radix_tree_lock(&ctx);
+               radix_tree_insert(ctx.tree, hwirq, &irq_map[virq]);
+               radix_tree_unlock(&ctx);

you then write:

	spin_lock(&host->revmap_data.tree_lock);
	radix_tree_insert(&host->revmap_data.tree, hwirq, &irq_map[virq]);
	spin_unlock(&host->revmap_data.tree_lock);

The only advantage of the concurrent radix tree over this model is that it can potentially do multiple modification operations at the same time.

Still, cool that you used it ;-)

--
To unsubscribe from this list: send the line "unsubscribe linux-rt-users" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Benjamin Herrenschmidt

2008-07-25 08:27 UTC #6 lore raw

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

Quoted 4 lines · Peter Zijlstra

The only advantage of the concurrent radix tree over this model is that it can potentially do multiple modification operations at the same time.

Yup, we do not need that for the irq revmap... concurrent lookup is all we need.

Cheers,
Ben.

Sebastien Dugue

author

2008-07-25 08:35 UTC #7 lore raw

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

Quoted 8 lines · On Fri, 25 Jul 2008 18:27:20 +1000 Benjamin Herrenschmidt…

Quoted 4 lines · Peter Zijlstra
The only advantage of the concurrent radix tree over this model is that it can potentially do multiple modification operations at the same time.
Yup, we do not need that for the irq revmap... concurrent lookup is all we need.

Shouldn't we care about concurrent insertion and deletion in the tree? I agree
that concern might be a bit artificial but in theory that can happen.

Sebastien.

Benjamin Herrenschmidt

2008-07-25 08:40 UTC #8 lore raw

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

Quoted 5 lines · Sebastien Dugue

Quoted 3 lines · On Fri, 25 Jul 2008 18:27:20 +1000 Benjamin Herrenschmidt…
Quoted 2 lines · Peter Zijlstra

Quoted 8 lines

Quoted 5 lines
Quoted 2 lines
The only advantage of the concurrent radix tree over this model is that it can potentially do multiple modification operations at the same time.
Yup, we do not need that for the irq revmap... concurrent lookup is all we need.
Shouldn't we care about concurrent insertion and deletion in the tree? I agree
that concern might be a bit artificial but in theory that can happen.

Yes, we just need to protect it with a big hammer, like a spinlock, it's not a performance critical code path.

Ben.

Sebastien Dugue

author

2008-07-25 08:47 UTC #9 lore raw

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

Quoted 9 lines · On Fri, 25 Jul 2008 18:40:21 +1000 Benjamin Herrenschmidt…

Quoted 8 lines · Sebastien Dugue
Quoted 6 lines · On Fri, 25 Jul 2008 18:27:20 +1000 Benjamin Herrenschmidt…
Quoted 4 lines · Peter Zijlstra
The only advantage of the concurrent radix tree over this model is that it can potentially do multiple modification operations at the same time.

Quoted 8 lines

Quoted 5 lines
Quoted 2 lines
Yup, we do not need that for the irq revmap... concurrent lookup is all we need.
Shouldn't we care about concurrent insertion and deletion in the tree? I agree
that concern might be a bit artificial but in theory that can happen.
Yes, we just need to protect it with a big hammer, like a spinlock, it's not a performance critical code path.

Agreed. Will look into this in the next few days.

Thanks,

Sebastien.

Sebastien Dugue

author

2008-07-25 08:33 UTC #10 lore raw

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

In reply to Peter Zijlstra

Hi Peter,

On Fri, 25 Jul 2008 09:49:37 +0200 Peter Zijlstra <[email protected]> wr= ote:

Quoted 8 lines · Sebastien Dugue

Quoted 1 line
On Thu, 24 Jul 2008 21:11:34 +1000 Nick Piggin <[email protected]=
Quoted 5 lines · wrote:
=20
Quoted 4 lines · Sebastien Dugue
Quoted 3 lines
From: Sebastien Dugue <[email protected]>
Date: Tue, 22 Jul 2008 11:56:41 +0200
Subject: [PATCH][RT] powerpc - Make the irq reverse mapping radix t=

ree

Quoted 4 lines

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines
lockless
The radix tree used by interrupt controllers for their irq reverse
mapping (currently only the XICS found on pSeries) have a complex l=

ocking

Quoted 1 line

Quoted 1 line
Quoted 1 line
Quoted 1 line
scheme dating back to before the advent of the concurrent radix tre=

e on

Quoted 3 lines

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
preempt-rt.
Take advantage of this and of the fact that the items of the tree=

are

Quoted 1 line

Quoted 1 line
Quoted 1 line
Quoted 1 line
pointers to a static array (irq_map) elements which can never go un=

der us

Quoted 3 lines

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
to simplify the locking.
Concurrency between readers and writers are handled by the intrin=

sic

Quoted 1 line

Quoted 1 line
Quoted 1 line
Quoted 1 line
properties of the concurrent radix tree. Concurrency between the tr=

Quoted 1 line

Quoted 1 line
Quoted 1 line
Quoted 1 line
initialization which is done asynchronously with readers and writer=

s access

Quoted 1 line

Quoted 1 line
Quoted 1 line
Quoted 1 line
is handled via an atomic variable (revmap_trees_allocated) set when=

the

Quoted 1 line

Quoted 1 line
Quoted 1 line
Quoted 1 line
tree has been initialized and checked before any reader or writer a=

ccess

Quoted 18 lines

Quoted 8 lines
Quoted 4 lines
Quoted 1 line
just like we used to check for tree.gfp_mask !=3D 0 before.
=20
Hmm, RCU radix tree is in mainline too for quite a while. I thought Ben had already converted this code over ages ago...
=20
Mainline does not have the concurrent radix tree which this patch
is based on, but maybe it's overkill and the RCU radix tree is enough. Not sure, will have to think about it a bit more.
=20
Should be. The model of the concurrent radix tree can be mapped to spinlock + rcu radix tree.
=20
So instead of:
=20
arch/powerpc/kernel/irq.c unsigned int irq_radix_revmap(struct irq · line 827
Quoted 4 lines
=EF=BB=BF+ DEFINE_RADIX_TREE_CONTEXT(ctx, tree);
arch/powerpc/kernel/irq.c +3 -0
+               radix_tree_lock(&ctx);
+               radix_tree_insert(ctx.tree, hwirq, &irq_map[virq]);
+               radix_tree_unlock(&ctx);

Quoted 8 lines

=20
=20
you then write:
=20

	spin_lock(&host->revmap_data.tree_lock);
	radix_tree_insert(&host->revmap_data.tree, hwirq, &irq_map[virq]);
	spin_unlock(&host->revmap_data.tree_lock);

=20

Cool, that will indeed makes it much easier to have something applicable
to mainline which works with preempt-rt.

Quoted 3 lines

=20
The only advantage of the concurrent radix tree over this model is that it can potentially do multiple modification operations at the same time.

Well in theory that can happen if a module is loaded which creates a mapp=
ing
while another one is unloaded at the same time. The time window is pretty n= arrow,
but still present nonetheless. That's why I chose to use the concurrent ver= sion.

Quoted 2 lines

=20
Still, cool that you used it ;-)

Yep, looked like what was needed until I realized it was not available in
mainline. Nice work though and good paper for explaining it all.

Sebastien.

Benjamin Herrenschmidt

2008-07-25 05:14 UTC #11 lore raw

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

In reply to Nick Piggin

Quoted 8 lines

Quoted 7 lines
Concurrency between readers and writers are handled by the intrinsic
properties of the concurrent radix tree. Concurrency between the tree initialization which is done asynchronously with readers and writers access is handled via an atomic variable (revmap_trees_allocated) set when the tree has been initialized and checked before any reader or writer access just like we used to check for tree.gfp_mask != 0 before.

Quoted 5 lines

Hmm, RCU radix tree is in mainline too for quite a while. I thought Ben had already converted this code over ages ago...
Nothing against the -rt patch, but mainline should probably be updated to use RCU as well?

No, I haven't updated that code yet, and yes, we should do it :-)

Cheers,
Ben.