[PATCH] idr: fix backtrack logic in idr_remove_all

[PATCH] idr: fix backtrack logic in idr_remove_all

[imre.deak]

From: Imre Deak <imre.deak@nokia.com>

Currently idr_remove_all will fail with a use after free error if
idr::layers is bigger than 2, which on 32 bit systems corresponds to
items more than 1024. This is due to stepping back too many levels
during backtracking. For simplicity let's assume that IDR_SIZE=1 -> we
have 2 nodes at each level below the root node and each leaf node stores
two IDs. (In reality for 32 bit systems IDR_SIZE=5, with 32 nodes at
each sub-root level and 32 IDs in each leaf node). The sequence of
freeing the nodes at the moment is as follows:

layer
1 ->                       a(7)
2 ->            b(3)                  c(5)
3 ->        d(1)   e(2)           f(4)    g(6)

Until step 4 things go fine, but then node c is freed, whereas node g
should be freed first. Since node c contains the pointer to node g we'll
have a use after free error at step 6.

How many levels we step back after visiting the leaf nodes is currently
determined by the msb of the id we are currently visiting:

Step
1.          node d with IDs 0,1 is freed, current ID is advanced to 2.
            msb of the current ID bit 1. This means we need to step back
            1 level to node b and take the next sibling, node e.
2-3.        node e with IDs 2,3 is freed, current ID is 4, msb is bit 2.
            This means we need to step back 2 levels to node a, freeing
            node b on the way.
4-5.        node f with IDs 4,5 is freed, current ID is 6, msb is still
            bit 2. This means we again need to step back 2 levels to node
            a and free c on the way.
6.          We should visit node g, but its pointer is not available as
            node c was freed.

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)) {
 			if (p)
 				free_layer(p);
 			n += IDR_BITS;
-- 
1.7.0.2

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

[Tejun Heo]

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

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

[Imre Deak]

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

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

[Tejun Heo]

On 05/18/2010 01:18 PM, Imre Deak wrote:
>> 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.

Ah, I thought you were doing fls(id & ~(id + 2)) and thus looking at 1
-> 0 transitions.  It's the other way and you're looking for the
highest 0 -> 1 transition which should be the same to the highest bit
changing if you aren't overflowing.  The patch looks good then.  I
still think ^ test would be clearer tho.  Hmmm... Can you please add
little comment there stating that you're looking for the highest bit
flipping?

Reviewed-by: Tejun Heo <tj@kernel.org>

Thanks.

-- 
tejun

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

[Imre Deak]

On Tue, May 18, 2010 at 05:23:20PM +0200, ext Tejun Heo wrote:
> On 05/18/2010 01:18 PM, Imre Deak wrote:
> >> 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.
> 
> Ah, I thought you were doing fls(id & ~(id + 2)) and thus looking at 1
> -> 0 transitions.  It's the other way and you're looking for the
> highest 0 -> 1 transition which should be the same to the highest bit
> changing if you aren't overflowing.

Yes, both ways you get the same result and in case of overflow neither
will work.

> The patch looks good then.  I still think ^ test would be clearer tho.
> Hmmm...

Well xor results in one instruction less on machines without a nand
instruction, so I'll change that.

> Can you please add little comment there stating that you're
> looking for the highest bit flipping?

Yes, I'll re-test and follow up with an updated patch.

Thanks for the review,
Imre

> 
> Reviewed-by: Tejun Heo <tj@kernel.org>
> 
> Thanks.
> 

[PATCH v2] idr: fix backtrack logic in idr_remove_all

[imre.deak]

From: Imre Deak <imre.deak@nokia.com>

Currently idr_remove_all will fail with a use after free error if
idr::layers is bigger than 2, which on 32 bit systems corresponds to
items more than 1024. This is due to stepping back too many levels
during backtracking. For simplicity let's assume that IDR_BITS=1 -> we
have 2 nodes at each level below the root node and each leaf node stores
two IDs. (In reality for 32 bit systems IDR_BITS=5, with 32 nodes at
each sub-root level and 32 IDs in each leaf node). The sequence of
freeing the nodes at the moment is as follows:

layer
1 ->                       a(7)
2 ->            b(3)                  c(5)
3 ->        d(1)   e(2)           f(4)    g(6)

Until step 4 things go fine, but then node c is freed, whereas node g
should be freed first. Since node c contains the pointer to node g we'll
have a use after free error at step 6.

How many levels we step back after visiting the leaf nodes is currently
determined by the msb of the id we are currently visiting:

Step
1.          node d with IDs 0,1 is freed, current ID is advanced to 2.
            msb of the current ID bit 1. This means we need to step back
            1 level to node b and take the next sibling, node e.
2-3.        node e with IDs 2,3 is freed, current ID is 4, msb is bit 2.
            This means we need to step back 2 levels to node a, freeing
            node b on the way.
4-5.        node f with IDs 4,5 is freed, current ID is 6, msb is still
            bit 2. This means we again need to step back 2 levels to node
            a and free c on the way.
6.          We should visit node g, but its pointer is not available as
            node c was freed.

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 levels and so on.

The fix was tested with IDs up to 1 << 20, which corresponds to 4
layers on 32 bit systems.

Signed-off-by: Imre Deak <imre.deak@nokia.com>
Reviewed-by: Tejun Heo <tj@kernel.org>

---
 lib/idr.c |    5 ++++-
 1 files changed, 4 insertions(+), 1 deletions(-)

Changes since v1:
- changed nand to xor to save an instruction
- add note on how we calculate the backtrack level

diff --git a/lib/idr.c b/lib/idr.c
index 2eb1dca..dc847c5 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,10 @@ void idr_remove_all(struct idr *idp)
 			p = p->ary[(id >> n) & IDR_MASK];
 		}
 
+		bt_mask = id;
 		id += 1 << n;
-		while (n < fls(id)) {
+		/* Get the highest bit that the above add changed from 0->1. */
+		while (n < fls(id ^ bt_mask)) {
 			if (p)
 				free_layer(p);
 			n += IDR_BITS;
-- 
1.7.0.2