Re: [PATCH v1 1/6] idr: introduce idr_alloc_cyclic

[Jeff Layton <jlayton@redhat.com>]

On Wed, 27 Mar 2013 10:01:35 -0700
Tejun Heo <tj@kernel.org> wrote:

> Hello,
> 
> On Wed, Mar 27, 2013 at 12:48:04PM -0400, Jeff Layton wrote:
> > > > + * Note that people using cyclic allocation to avoid premature reuse of an
> > > > + * already-used ID may be in for a nasty surprise after idr->cur wraps. The
> > > > + * IDR code is designed to avoid unnecessary allocations. If there is space
> > > > + * in an existing layer that holds high IDs then it will return one of those
> > > > + * instead of allocating a new layer at the bottom of the range.
> > > 
> > > Ooh, does it?  Where?
> > > 
> > 
> > That's what I gathered from looking at idr_get_empty_slot. I could be
> > wrong here, so please correct me if I am. The IDR internals are really
> > hard to follow...
> 
> Amen, it's horrible.
> 
> > In any case, it looks like it only tries to allocate a new layer if:
> > 
> > idr->top is empty
> > 
> > ...or...
> > 
> > while (id > idr_max(layers)) {
> > ...
> > }
> >
> > After the wrap, idr->top won't be empty if we have at least one layer
> > still in use. We start with id = starting_id, which after wrap will be
> > much lower than idr_max() at that point (right?).
> > 
> > So we'll skip the while loop and fall right into sub_alloc and will
> > quite possibly end up allocating a slot out of the current layer, which
> > is almost certainly not near the bottom of the range.
> > 
> > Again, I'm far from sure of my understanding of the internals here, so
> > please do correct me if that's not right...
> 
> So, there are two paths which do layer allocation.
> idr_get_empty_slot() does bottom -> top expansion.  ie. it grows the
> tree if the current position can't be covered by the current tree.
> Note that the tree can always point to zero.  That is, the first slot
> of the top layer always includes zero.
> 
> The other part - building tree top -> bottom - happens in sub_alloc()
> which traverses the tree downwards for the current position and
> creates new idr_layer if it doesn't exist.
> 
> So, after wrap, the tree is already tall enough so
> idr_get_empty_slot() will just call into sub_alloc() which will build
> the tree downwards.  AFAICS, it does guarantee lowest-packing.
> 

Ok, that's good to know, and I'll remove the comment for the v2 patch.
I'm glad to be wrong in this case :)

-- 
Jeff Layton <jlayton@redhat.com>