irq: radix_tree_insert can fail

Allow the option to specify an upper limit to the irq numbers for each allocation. The limit is non-inclusive, and 0 means no limit needed by caller.

Some irq chips can support a relative large and arbitrary range, but not infinite. For example, they may use the linux irq number as the msi desciptor data, which for msi is 16 bits.

Since e7bcecb7b1 (genirq: Make nr_irqs runtime expandable), checking NR_IRQS or even nr_irqs is not sufficient to enforce such requirements when sparse irqs are configured.

The radix-tree code uses call_rcu to delay freeing internal data elements when removing when deleting an entry. We must protect against the elements being freed while we traverse the tree.

While preparing a patch to expand the contexts in which the radix tree optionally used by powerpc for mapping hardware irq numbers to linux numbers would be called, I realized that the radix tree was not locked when radix_tree_lookup was called. I then realized the same issue applies to the generic irq code when sparse irqs are in use.

While the powerpc radix tree was only referenced from one callsite that was irqs_disabled and irq_enter, irq_to_desc is called from many more contexts including threaded irq handlers and other process contexts.

This does not show up in the rcu lockdep because in 2.6.34 commit 2676a58c98 (radix-tree: Disable RCU lockdep checking in radix tree) deemed it too hard to pass the condition of the protecting lock to the library.

Signed-off-by Milton Miller <[email protected]>

Cc <[email protected]>

---
I expect the relatively infrequent calls to irq_free_descs, combined with most calls to irq_to_desc being irqs_disabled and the fact merged to mainline implemntations of call_rcu requiring a cpu to respond to a hard irq or schedule has hidden this error to date.

Index: work.git/kernel/irq/irqdesc.c
===================================================================

kernel/irq/irqdesc.c +0 -0

@@ -108,7 +108,13 @@ static void irq_insert_desc(unsigned int
 

Check the insert, and if it fails cleanup and free all partial work.

Sparse irq was not checking the return code from radix_tree_insert, but it may need to allocate memory and can fail. If it failed, it still claimed success to the caller but the affected irq(s) are unavailable and the reference to the affected descriptors is leaked.

Signed-off-by Milton Miller <[email protected]>

---
I started by tring to change free_desc to take the descriptor pointer and pushing that down, but that soon ran into conflicts between the array and sparse implementations, and/or the old dynamic irq cleanup function that is still used by some architectures. This version is targeted, and also protects against scribbles to irq_data.irq.

+int irq_alloc_descs(int irq, unsigned int from, unsigned int cnt, int node)

include/linux/irq.h +3 -0

+	return irq_alloc_descs_range(from, from + cnt, cnt, node);
+}
+
 static inline int irq_alloc_desc(int node)
 {
 	return irq_alloc_descs(-1, 0, 1, node);

Index: work.git/kernel/irq/irqdesc.c
===================================================================

kernel/irq/irqdesc.c +2 -3

@@ -343,27 +343,37 @@ void irq_free_descs(unsigned int from, u
 EXPORT_SYMBOL_GPL(irq_free_descs);
 
 /**
- * irq_alloc_descs - allocate and initialize a range of irq descriptors
- * @irq:	Allocate for specific irq number if irq >= 0
+ * irq_alloc_descs_range - allocate and initialize a range of irq descriptors
  * @from:	Start the search from this irq number
+ * @limit:	Unless zero, all irq numbers must be less than this value
  * @cnt:	Number of consecutive irqs to allocate.
  * @node:	Preferred node on which the irq descriptor should be allocated
  *
  * Returns the first irq number or error code
  */
-int irq_alloc_descs(int irq, unsigned int from, unsigned int cnt, int node)

kernel/irq/irqdesc.c +8 -0

+		if (cnt > limit)
+			return -ENOMEM;
+		if (from > limit - cnt)
+			return -EINVAL;
+		end = min_t(unsigned int, limit, IRQ_BITMAP_BITS);
+	} else {
+		end = IRQ_BITMAP_BITS;
+	}

Quoted 7 lines · Milton Miller

Check the insert, and if it fails cleanup and free all partial work.

Sparse irq was not checking the return code from radix_tree_insert, but it may need to allocate memory and can fail. If it failed, it still claimed success to the caller but the affected irq(s) are unavailable and the reference to the affected descriptors is leaked.

Quoted 7 lines

Signed-off-by Milton Miller <[email protected]>

---
I started by tring to change free_desc to take the descriptor pointer and pushing that down, but that soon ran into conflicts between the array and sparse implementations, and/or the old dynamic irq cleanup function that is still used by some architectures. This version is targeted, and also protects against scribbles to irq_data.irq.

The simpler solution is to move irq_insert_desc() into alloc_desc() and deal with the error case there.

Quoted 4 lines · Thomas Gleixner

The reason why nobody ever noticed is that the free happens in the teardown path of PCI devices and at this point nothing accesses that irq anymore.

I'm not talking about the irq_desc that is being removed from the tree, instead I'm talking about the internal elements in the radix tree that are used to find the pointers at the bottom of the tree (that in turn point to the irq_desc in the irq tree case).

Quoted 20 lines · Milton Miller

The radix-tree code uses call_rcu to delay freeing internal data elements when removing when deleting an entry. We must protect against the elements being freed while we traverse the tree.

While preparing a patch to expand the contexts in which the radix tree optionally used by powerpc for mapping hardware irq numbers to linux numbers would be called, I realized that the radix tree was not locked when radix_tree_lookup was called. I then realized the same issue applies to the generic irq code when sparse irqs are in use.

While the powerpc radix tree was only referenced from one callsite that was irqs_disabled and irq_enter, irq_to_desc is called from many more contexts including threaded irq handlers and other process contexts.

This does not show up in the rcu lockdep because in 2.6.34 commit 2676a58c98 (radix-tree: Disable RCU lockdep checking in radix tree) deemed it too hard to pass the condition of the protecting lock to the library.

Quoted 7 lines

Signed-off-by Milton Miller <[email protected]>

Cc <[email protected]>

---
I expect the relatively infrequent calls to irq_free_descs, combined with most calls to irq_to_desc being irqs_disabled and the fact merged to mainline implemntations of call_rcu requiring a cpu to respond to a hard irq or schedule has hidden this error to date.

The reason why nobody ever noticed is that the free happens in the teardown path of PCI devices and at this point nothing accesses that irq anymore.

Quoted 8 lines

Index: work.git/kernel/irq/irqdesc.c
===================================================================

kernel/irq/irqdesc.c +0 -0

@@ -108,7 +108,13 @@ static void irq_insert_desc(unsigned int
 

kernel/irq/irqdesc.c static void irq_insert_desc(unsigned int · line 117

Quoted 10 lines

kernel/irq/irqdesc.c +7 -1

 struct irq_desc *irq_to_desc(unsigned int irq)
 {
-	return radix_tree_lookup(&irq_desc_tree, irq);
+	struct irq_desc *desc;
+
+	rcu_read_lock();
+	desc = radix_tree_lookup(&irq_desc_tree, irq);
+	rcu_read_unlock();
+
+	return desc

That does not really compile :)

And it does not help at all because we unconditionally free the irq descriptor and do not use rcu based kfree. Further you protect only

the lookup and not the complete section which uses the descriptor, so it could go away after the rcu_read_unlock() in theory.

Allow the option to specify an upper limit to the irq numbers for each allocation. The limit is non-inclusive, and 0 means no limit needed by caller.

Some irq chips can support a relative large and arbitrary range, but not infinite. For example, they may use the linux irq number as the msi desciptor data, which for msi is 16 bits.

Since e7bcecb7b1 (genirq: Make nr_irqs runtime expandable), checking NR_IRQS or even nr_irqs is not sufficient to enforce such requirements when sparse irqs are configured.

Based on an irc discussion, make the limit per call instead of an arch callback or global setting.

If the requested count is above the limit, return -ENOMEM as if nr_irqs could not be expanded, assuming the limit was specified at a different layer than the count.

This code does not try to keep the prior semantics of irq_alloc_descs when irq was non-negative but not equal to from. I believe it was an implementation artifact instead of a designed feature that one could specify search starting from 4 and fail if the allocated irq was not exactly 6, confirming that the intervening irqs were reserved.

Suggested-by Thomas Gleixner <[email protected]>

Signed-off-by Milton Miller <[email protected]>