lib: allow idr to be used in irq context

Hi,

This patch allows idr to be used in irq context.

idr_pre_get() is necessary to be called before idr_get_new() is called. No locking is necessary when calling idr_pre_get().

But idr_get_new(), idr_find() and idr_remove() must be serialized with respect to each other.

All of the aforementioned, may end up in alloc_layer() or free_layer() which grabs the idp lock using spin_lock.

If idr_get_new() or idr_remove() is used in IRQ context, then we may get a lockup when idr_pre_get was called in process context and an IRQ interrupted while it held the idp lock.

This patch changes the spin_lock to spin_lock_irqsave, and spin_unlock to spin_unlock_irqrestore, to allow idr_get_new(), idr_find() and idr_remove() to be called from IRQ context, while idr_pre_get() to be called in process context.

@@ -37,27 +37,29 @@
 static struct idr_layer *alloc_layer(struct idr *idp)
 {
 	struct idr_layer *p;
+	unsigned long flags;
 
-	spin_lock(&idp->lock);
+	spin_lock_irqsave(&idp->lock, flags);
 	if ((p = idp->id_free)) {
 		idp->id_free = p->ary[0];
 		idp->id_free_cnt--;
 		p->ary[0] = NULL;
 	}
-	spin_unlock(&idp->lock);
+	spin_unlock_irqrestore(&idp->lock, flags);
 	return(p);
 }
 
 static void free_layer(struct idr *idp, struct idr_layer *p)
 {
+	unsigned long flags;
 	/*
 	 * Depends on the return element being zeroed.
 	 */
-	spin_lock(&idp->lock);
+	spin_lock_irqsave(&idp->lock, flags);
 	p->ary[0] = idp->id_free;
 	idp->id_free = p;
 	idp->id_free_cnt++;
-	spin_unlock(&idp->lock);
+	spin_unlock_irqrestore(&idp->lock, flags);
 }
 
 /**

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

Hi Everyone,

Luben's changes make sense please merge them.

Jim Houston - Concurrent Computer Corp.

Well yes, the change makes sense if there's actually a caller which needs it.

If there is such a caller then Luben should identify it, please.

Hi Andrew,

The caller is the aic94xx SAS LLDD. It uses IDR to generate unique task tag for each SCSI task being submitted. It is then used to lookup the task given the task tag, in effect using IDR as a fast lookup table.

Yes, I'm also not aware of any other users of IDR from mixed process/IRQ context or for SCSI Task tag purposes.

Luben

Just a minute, that's not what idr was designed for. It was really designed for enumerations (like disk) presented to the user. That's why using it in IRQ context hasn't been considered.

However, there is an infrastructure in the block layer called the generic tag infrastructure which was designed precisely for this purpose and which is designed to operate in IRQ context.

James

Hi James, how are you?

Is this the only use _you_ could find for a *radix tree*? ;-) Since of course sd.c uses it just as an enumeration, according to you this must be the only use? :-)

It was designed as a general purpose id to pointer translation service, just as the comment in it says.

James, I'm sure you're well aware that,
- a request_queue is LU-bound,
- a SCSI _transport_ (*ANY*) can _only_ address domain devices, but _not_ LUs. LUs are *not* seen on the domain.

See the different associations? Then why are you posting such emails?

Andrew, please apply this patch.

Thanks,
Luben

And Dicto Simpliciter to you too.

idr was specifically designed with unlocked pre-allocation in mind. The change you're proposing wants to allow pre allocation from irq context. This really doesn't look like a good change because the whole point of pre allocation is to do it at a point in time when the system can sleep if it has to.

What I don't understand is why you need to pre allocate this tag from irq context. Best practise is to allocate when you have user context but make use of it in IRQ context.

So you're planning to do some type of tag command queueing outside of the block framework? Could you just look at what it would take to do it within the existing framework first? I seem to have wasted quite a bit of time recently pulling spurious queueing code out of Adaptec drivers.

Remember that the code is adaptable ... we have non-block devices that use block queues for instance.

James

No preallocation is done from IRQ context. Do not spread FUD. It seems to me that you're unaware how IDR works and unaware how the driver works.

See the original patch submission -- I do explain why it is needed, and show exactly how it breaks. You may also want to look at the idr.c code. There is no reason not to promote the lock to an irq spinlock, again, since it protects only data manipulation, as it should.

In fact, when you start writing code and actually face problems, and start looking for the right tools, then you'll see it. Right now this is a useless argument and you should drop it.

No preallocation is done in IRQ context. See above.

Furthermore, you should know that a slab cache *settles* very quickly, especially for IO. You should've learned this when I posted my results of SCSI Core using the slab cache for commands 5 years ago, before that code was in SCSI Core.

James, is this the most important thing for SCSI Core for the maintaner of SCSI Core to discuss?

IDR's use? A general library utility's use in a driver? Is this what the SCSI Core maintainer will use to reject a driver's acceptance?

When so many things have been said in the last week on this mailing list, being in direct importance to SCSI Core: error handling being one of them, another is HCIL usage, and other vendor provided labels for LUs, native target support, etc.

No one is implementing tag command queueing. Why are you spreading FUD into making people think that if you use tags, you must be doing tagged command _queueing_?

Here:
Tags do _not_ imply TCQ.
TCQ does imply Tags.

Completely irrelevant for a transport driver. Stop throwing red-herring.

Instead let's start discussing matters SCSI, which have been due for the last 5 years, which I had hoped you'd _lead_ or at least *listen and take paches* into SCSI Core, you know, like other maintainers do. Those are:
- 8 byte LUNs, opaque to SCSI Core,
- native target (domain device) support,
- native LU discovery,
- HCIL becoming just one of _many_ possible labels for an LU, whereby vendors provide them.

*This* is what is important and relevant to SCSI Core. Not to mention, error handling, etc.

Now let's drop this and start discussing things which have been a pain for the last 5 years, since the first SAM LLDD (iSCSI) was introduced to SCSI Core (at least not publicly).

Let's take SCSI Core into the 21st century, shall we? Please?

Luben

Argumentum ad Hominem now ... we'll get them all eventually.

Since you won't post the usage code, just answer this: how does what you're doing with idr differ from its originally designed consumer: the posix timers which also do the idr_remove() in IRQ context?

To me it seems your argument applies to this case as well, but you didn't quote it when asked for an example, so I assume there's some difference that I don't understand.

James

erp. posix_timers has its own irq-safe lock, so we're doing extra, unneeded locking in that code path.

I think providing locking inside idr.c was always a mistake - generally we rely on caller-provided locking for such things.

Possibly, the posix timer code is rather convoluted in this area so I'm not entirely sure my analysis is correct.

Well, the reason is because they wanted lockless pre-alloc. If you do it locked, you can't use GFP_KERNEL for the memory allocation flag which rather defeats its purpose.

Perhaps the bug is in the API. We have pre-allocate, new, find and remove. Perhaps what we're missing is a reuse all of which could then rely on caller provided locking, with pre-alloc and remove requiring user context but new, find and reuse being happy in irq context.

James

Then _please_ drop this thread.

James, please drop this thread and let's concentrate on SCSI.

No, the bug is _not_ in the API.

*IDR is perfect as it is.* It gives the caller a lot of freedom, without internal restrictions (other than the provided by this patch).

Now please let's go back to SCSI and leave other people's code and API alone. Shall we James?

SCSI Core needs enough work to have SCSI people worry about other people's code and design... or is this the modus operandi of the SCSI Core maintainer...? "Documentation/ManagementStyle", please?

Thank you,
Luben

It looks to be feasible to implement this locklessly the same way as the radix-tree does (with a per_cpu list), except that you still need a start/end API for the pre allocation to do the initial disable of pre- emption.

Then the remove should simply then free the entry (again like radix- tree) and let the slab take care of necessary locking.

Of course, if we're going to go to all this trouble, the next question that arises naturally is why not just reuse the radix-tree code to implement idr anyway ... ?

James

Yes, we could probably have gone that way. radix-tree would need some enhancements for the find-next-above thing.

radix-tree has some features (tags, gang-lookup, gang-lookup-by-tag) which idr doesn't. Fitting them all into the one storage API would be nice, I guess. radix-tree does potentially use more memory, although that'll only be significant for collections which are both large and sparse.

Still, people can use either facility at present. The person who does any such consolidation would do the kernel-wide migration at the same time.

Yes, that's particularly simple (example patch below). However, radix- tree needs to grow a bitmap index for whether its slots are occupied for this to be made efficient (it would also help with the gang lookups too)---at the moment it's O(N); it could be made O(log(N)).

And by definition, idr is trying to discourage sparsity in the collections.

True. We only seem to have 8 in tree users ... that's not a huge number to convert.

James

@@ -62,10 +62,20 @@ unsigned int
 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
 		unsigned long first_index, unsigned int max_items, int tag);
 int radix_tree_tagged(struct radix_tree_root *root, int tag);
+int radix_tree_get_new_above(struct radix_tree_root *root, void *item,
+			     unsigned long starting_index,
+			     unsigned long *index);
 
 static inline void radix_tree_preload_end(void)
 {
 	preempt_enable();
 }
 
+static inline int radix_tree_get_new(struct radix_tree_root *root, void *item,
+				     unsigned long *index)
+{
+	return radix_tree_get_new_above(root, item, 0, index);
+}
+
+
 #endif /* _LINUX_RADIX_TREE_H */

@@ -133,6 +133,7 @@ int radix_tree_preload(int gfp_mask)
 out:
 	return ret;
 }
+EXPORT_SYMBOL(radix_tree_preload);
 
 static inline void tag_set(struct radix_tree_node *node, int tag, int offset)
 {

@@ -483,7 +484,9 @@ __lookup(struct radix_tree_root *root, v
 		unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;
 
 		for ( ; i < RADIX_TREE_MAP_SIZE; i++) {
-			if (slot->slots[i] != NULL)
+			if (max_items == 0 && slot->slots[i] == NULL)
+				goto out;
+			else if (max_items != 0 && slot->slots[i] != NULL)
 				break;
 			index &= ~((1UL << shift) - 1);
 			index += 1UL << shift;

@@ -498,7 +501,9 @@ __lookup(struct radix_tree_root *root, v
 
 			for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
 				index++;
-				if (slot->slots[j]) {
+				if (max_items == 0 && slot->slots[j] == NULL)
+					goto out;
+				if (max_items != 0 && slot->slots[j]) {
 					results[nr_found++] = slot->slots[j];
 					if (nr_found == max_items)
 						goto out;

@@ -551,6 +556,28 @@ radix_tree_gang_lookup(struct radix_tree
 }
 EXPORT_SYMBOL(radix_tree_gang_lookup);
 
+/**
+ * radix_tree_get_new_above - insert item into first available slot
+ *
+ * @root:	radix tree root
+ * @item:	item to insert
+ * @starting_index: index to begin the search for a new slot from
+ * @index:	actual index found for inserting the item
+ *
+ * Performs an index-ascending scan of the tree for an empty slot.  Places
+ * @item in the first empty slot and sets @index to its position.
+ */
+int radix_tree_get_new_above(struct radix_tree_root *root, void *item,
+			     unsigned long starting_index,
+			     unsigned long *index)
+{
+	if (item == NULL)
+		item = (void *)1UL;
+	__lookup(root, NULL, starting_index, 0, index);
+	return radix_tree_insert(root, *index, item);
+}
+EXPORT_SYMBOL(radix_tree_get_new_above);
+
 /*
  * FIXME: the two tag_get()s here should use find_next_bit() instead of
  * open-coding the search.

Ahhh, *THANK YOU* Andrew for your common sense!

Yes, James is unaware that 3 out of the 4 major entrances into IDR _must_ be synchronized with respect to each other, depending on your context (irq or not) *and* that that synchronization is external. If *one* of those 3 is done in IRQ context, then all three should be, since they should be synchnornized wrt each other.

Only idr_pre_get() should not be called from IRQ context.

*BUT* since idr_pre_get() and those other 3 may end up
in the same _internally_ locked region, _that_ internally locked region should have the lowest common denominator lock, _because_ of the other 3 which have to be syncrhonised wrt each other.

It is _this_ reason that the internal locking of IDR should use use the lowest common denominator because of the context of those other 3 which the _caller_ is responsible for synchronizing depending on the caller's context.

Now James can we move on, please.

Andrew, please integrate this patch.

Thanks,
Luben

Hi James, how are you?

Is this the only use _you_ could find for a *radix tree*? ;-) Since of course sd.c uses it just as an enumeration, according to you this must be the only use? :-)

It was designed as a general purpose id to pointer translation service, just as the comment in it says.

James, I'm sure you're well aware that,
- a request_queue is LU-bound,
- a SCSI _transport_ (*ANY*) can _only_ address domain devices, but _not_ LUs. LUs are *not* seen on the domain.

See the different associations? Then why are you posting such emails?

Andrew, please apply this patch.

Thanks,
Luben