[PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[Luben Tuikov]

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.

Signed-off-by: Luben Tuikov <luben_tuikov@adaptec.com>

--- linux-2.6.12.5/lib/idr.c.old	2005-08-16 17:20:08.000000000 -0400
+++ linux-2.6.12.5/lib/idr.c	2005-08-16 17:22:16.000000000 -0400
@@ -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 majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[Jim Houston]

On Tue, 2005-08-16 at 18:03, Luben Tuikov wrote:

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

Hi Everyone,

Luben's changes make sense please merge them.

Jim Houston - Concurrent Computer Corp.

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[Andrew Morton]

Jim Houston <jim.houston@ccur.com> wrote:
>
> On Tue, 2005-08-16 at 18:03, Luben Tuikov wrote:
> 
> > 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.
> 
> Hi Everyone,
> 
> Luben's changes make sense please merge them.
> 

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.

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[Luben Tuikov]

--- Andrew Morton <akpm@osdl.org> wrote:

> Jim Houston <jim.houston@ccur.com> wrote:
> >
> > On Tue, 2005-08-16 at 18:03, Luben Tuikov wrote:
> > 
> > > 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.
> > 
> > Hi Everyone,
> > 
> > Luben's changes make sense please merge them.
> > 
> 
> 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

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[James Bottomley]

On Sun, 2005-08-21 at 08:49 -0700, Luben Tuikov wrote:
> 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.

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

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[Luben Tuikov]

--- James Bottomley <James.Bottomley@SteelEye.com> wrote:
> On Sun, 2005-08-21 at 08:49 -0700, Luben Tuikov wrote:
> > 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.
> 
> 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.

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.

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

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[Luben Tuikov]

--- Luben Tuikov <luben_tuikov@adaptec.com> wrote:
> --- James Bottomley <James.Bottomley@SteelEye.com> wrote:
> > 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, 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.

Another thing very important to mention is that the layering
infrastructure should _not_ be broken, whereby LLDD are required
to use block layer tags.

First, there may not be one to one correspondence accross layers.

Second, a tag on a layer identifies that particular _layer_ object.
It should not be used across layers or across several layers:
Block->Scsi Core->LLDD.

Third, although SCSI task tags are a SAM concept, they are defined
by the protocol in use and generated and assigned by the Initiator
port.  The block layer is _not_ an Initiator port.  SCSI Core is
also _not_ an Initiator port.

SCSI Core should be impervious to task tags, i.e. to the Q in
I_T_L_Q nexus.  The Q is never visible to it.

      Luben

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[James Bottomley]

On Sun, 2005-08-21 at 10:27 -0700, Luben Tuikov wrote:
> 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? :-)

And Dicto Simpliciter to you too.

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

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.

> > 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, 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?

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

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[Luben Tuikov]

--- James Bottomley <James.Bottomley@SteelEye.com> wrote:
> On Sun, 2005-08-21 at 10:27 -0700, Luben Tuikov wrote:
> > 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? :-)
> 
> And Dicto Simpliciter to you too.
> 
> > It was designed as a general purpose id to pointer translation
> > service, just as the comment in it says.
> 
> 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.

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.

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

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.

> > > 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, 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?
> 
> 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.

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.

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

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

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[James Bottomley]

On Sun, 2005-08-21 at 17:33 -0700, Luben Tuikov wrote:
> 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.

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

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[Andrew Morton]

James Bottomley <James.Bottomley@SteelEye.com> wrote:
>
> 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?

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.

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[Luben Tuikov]

--- James Bottomley <James.Bottomley@SteelEye.com> wrote:
> On Sun, 2005-08-21 at 08:49 -0700, Luben Tuikov wrote:
> > 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.
> 
> 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.

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.

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

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[James Bottomley]

On Sun, 2005-08-21 at 20:52 -0700, Andrew Morton wrote:
> erp.  posix_timers has its own irq-safe lock, so we're doing extra,
> unneeded locking in that code path.

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

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

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

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[Luben Tuikov]

On 08/21/05 23:52, Andrew Morton wrote:
> James Bottomley <James.Bottomley@SteelEye.com> wrote:
> 
>>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?
> 
> 
> 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.

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

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[Luben Tuikov]

On 08/22/05 10:28, James Bottomley wrote:
> On Sun, 2005-08-21 at 20:52 -0700, Andrew Morton wrote:
> 
>>erp.  posix_timers has its own irq-safe lock, so we're doing extra,
>>unneeded locking in that code path.
> 
> 
> Possibly, the posix timer code is rather convoluted in this area so I'm
> not entirely sure my analysis is correct.

Then _please_ drop this thread.

>>I think providing locking inside idr.c was always a mistake - generally we
>>rely on caller-provided locking for such things.
> 
> 
> 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.

James, please drop this thread and let's concentrate on SCSI.
 
> 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.

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

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[James Bottomley]

On Mon, 2005-08-22 at 09:28 -0500, James Bottomley wrote:
> > I think providing locking inside idr.c was always a mistake - generally we
> > rely on caller-provided locking for such things.
> 
> 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.

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

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[Andrew Morton]

James Bottomley <James.Bottomley@SteelEye.com> wrote:
>
> 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 ... ?

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.

Re: [PATCH 2.6.12.5 1/2] lib: allow idr to be used in irq context

[James Bottomley]

On Mon, 2005-08-22 at 15:09 -0700, Andrew Morton wrote:
> James Bottomley <James.Bottomley@SteelEye.com> wrote:
> >
> > 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 ... ?
> 
> Yes, we could probably have gone that way.  radix-tree would need some
> enhancements for the find-next-above thing.

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

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

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

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

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

James

diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -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 */
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -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.