lkml.org 
[lkml]   [2010]   [May]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH] idr: fix backtrack logic in idr_remove_all
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


\
 
 \ /
  Last update: 2010-05-18 12:27    [W:0.054 / U:4.312 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site