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

[Tejun Heo <tj@kernel.org>]

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

Thanks.

-- 
tejun