Re: [PATCH] 1/1: Device-Mapper: Remove 1024 devices limitation

[Jim Houston <jim.houston@comcast.net>]

On Tue, 2004-07-06 at 18:28, Andrew Morton wrote:
> Jim Houston <jim.houston@comcast.net> wrote:
> >
> > On Tue, 2004-07-06 at 17:23, Andrew Morton wrote:
> > > Kevin Corry <kevcorry@us.ibm.com> wrote:
> > > >
> > > > After talking with Alasdair a bit, there might be one bug in the "dm-use-idr"
> > > > patch I submitted before. It seems (based on some comments in lib/idr.c) that
> > > > the idr_find() routine might not return NULL if the desired ID value is not
> > > > in the tree.
> > > 
> > > 
> > > Confused.  idr_find() returns the thing it found, or NULL.  To which
> > > comments do you refer?
> > 
> > Hi Andrew, Kevin,
> > 
> > Kevin is correct.  It's more of the nonsense related to having a counter
> > in the upper bits of the id.  If you call idr_find with an id that is
> > beyond the currently allocated space it ignores the upper bits and
> > returns one of the entries that is in the allocated space.  This
> > aliasing is most annoying.
> 
> erk, OK, we have vestigial bits still.  Note that MAX_ID_SHIFT is now 31 on
> 32-bit, so we're still waggling the top bit.
> 
> > I'm attaching an untested patch which removes the counter in the upper
> > bits of the id and makes idr_find return NULL if the requested id is
> > beyond the allocated space.
> 
> Would you have time to get it tested please?
> 
> >  I suspect that there are problems with
> > id values which are less than zero.
> 
> Me too.  I'd only be confident in the 0..2G range.
> 
> 
> > -#endif
> > +	if (id >= (1 << n))
> > +		return NULL;
> >  	while (n > 0 && p) {
> >  		n -= IDR_BITS;
> >  		p = p->ary[(id >> n) & IDR_MASK];
> > 
> 
> I think the above test is unneeded?

Hi Everyone,

With out the test above an id beyond the allocated space will alias
to one that exists.  Perhaps the highest id currently allocated is 
100, there will be two layers in the radix tree and the while loop
above will only look at the 10 least significant bits.  If you call
idr_find with 1025 it will return the pointer associated with id 1.

The patch I sent was against linux-2.6.7, so I missed the change to
MAX_ID_SHIFT.

Jim Houston - Concurrent Computer Corp.