Re: [PATCH] idr: fix backtrack logic in idr_remove_all

[Imre Deak <imre.deak@nokia.com>]

On Tue, May 18, 2010 at 12:24:25PM +0200, ext Tejun Heo wrote:
> Hello,
> 
> On 05/12/2010 01:47 PM, imre.deak@nokia.com wrote:
> > The fix changes how we determine the number of levels to step back.
> > Instead of deducting this merely from the msb of the current ID, we
> > should really check if advancing the ID causes an overflow to a bit
> > position corresponding to a given layer. In the above example overflow
> > from bit 0 to bit 1 should mean stepping back 1 level. Overflow from
> > bit 1 to bit 2 should mean stepping back 2 level and so on.
> > 
> > The fix was tested with elements up to 1 << 20, which corresponds to
> > 4 layers on 32 bit systems.
> > 
> > Signed-off-by: Imre Deak <imre.deak@nokia.com>
> > ---
> >  lib/idr.c |    4 +++-
> >  1 files changed, 3 insertions(+), 1 deletions(-)
> > 
> > diff --git a/lib/idr.c b/lib/idr.c
> > index 9042a56..931d9d0 100644
> > --- a/lib/idr.c
> > +++ b/lib/idr.c
> > @@ -445,6 +445,7 @@ EXPORT_SYMBOL(idr_remove);
> >  void idr_remove_all(struct idr *idp)
> >  {
> >  	int n, id, max;
> > +	int bt_mask;
> >  	struct idr_layer *p;
> >  	struct idr_layer *pa[MAX_LEVEL];
> >  	struct idr_layer **paa = &pa[0];
> > @@ -462,8 +463,9 @@ void idr_remove_all(struct idr *idp)
> >  			p = p->ary[(id >> n) & IDR_MASK];
> >  		}
> >  
> > +		bt_mask = id;
> >  		id += 1 << n;
> > -		while (n < fls(id)) {
> > +		while (n < fls(id & ~bt_mask)) {
> 
> Shouldn't this be id ^ bt_mask?  The above only detects 1 -> 0
> transitions not the other way around.

It works according to the following with n=1:

id            id+2            fls((id+2) & ~id)
0             2               2
2             4               3
4             6               2
6             8               4
8             10              2
10            12              3
12            14              2

I think this should work.

> I don't think it will free all the layers in the middle.  Have you counted
> the number of frees match the number of allocations?

Not that, but I checked with kmemleak for 1 << 20 entries. I haven't got
any leaks.

--Imre