linux-kernel - Re: [PATCH] idr: fix backtrack logic in idr_remove

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <4BF26AD9.5070601@kernel.org>
Date:	Tue, 18 May 2010 12:24:25 +0200
From:	Tejun Heo <tj@...nel.org>
To:	imre.deak@...ia.com
CC:	Andrew Morton <akpm@...ux-foundation.org>,
	Eric Paris <eparis@...hat.com>,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
	LKML <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] idr: fix backtrack logic in idr_remove_all

Hello,

On 05/12/2010 01:47 PM, imre.deak@...ia.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@...ia.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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/