Possibly bug in radix_tree_delete, and fix.

Possibly bug in radix_tree_delete, and fix.

[Neil Brown]

Hi Nick,
 I believe there is a bug in radix_tree_delete introduced by:

http://www.kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=d5274261ea46f0aae93820fe36628249120d2f75

The nature of the bug is that if a tag is set on a node that is being
deleted, then that tag is unconditionally cleared in the parent of the
node, even if the deleted node has siblings with the tag still set.

I don't know what the large-scale consequences of this bug might be,
but I'm kinda hoping fixing it will fix a nasty NFS client related
oops we are seeing in radix_tree_tag_set ....

My suggested patch is below.

Please review, confirm, and Ack:

Thanks,
NeilBrown


Fix over-zealous clearing of tags in radix_tree_delete.

Signed-off-by: Neil Brown <neilb@suse.de>

### Diffstat output
 ./lib/radix-tree.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff ./lib/radix-tree.c~current~ ./lib/radix-tree.c
--- ./lib/radix-tree.c~current~	2006-02-16 13:22:28.000000000 +1100
+++ ./lib/radix-tree.c	2006-02-16 13:23:19.000000000 +1100
@@ -755,7 +755,7 @@ void *radix_tree_delete(struct radix_tre
 	for (tag = 0; tag < RADIX_TREE_TAGS; tag++) {
 		if (tag_get(pathp->node, tag, pathp->offset)) {
 			tag_clear(pathp->node, tag, pathp->offset);
-			tags[tag] = 0;
+			tags[tag] = any_tag_set(pathp->node, tag);
 			nr_cleared_tags++;
 		} else
 			tags[tag] = 1;

Re: Possibly bug in radix_tree_delete, and fix.

[Nick Piggin]

Neil Brown wrote:
> Hi Nick,
>  I believe there is a bug in radix_tree_delete introduced by:
> 
> http://www.kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=d5274261ea46f0aae93820fe36628249120d2f75
> 
> The nature of the bug is that if a tag is set on a node that is being
> deleted, then that tag is unconditionally cleared in the parent of the
> node, even if the deleted node has siblings with the tag still set.
> 
> I don't know what the large-scale consequences of this bug might be,
> but I'm kinda hoping fixing it will fix a nasty NFS client related
> oops we are seeing in radix_tree_tag_set ....
> 

I think you're right. I was kind of suspecting I might have introduced
a silly bug somewhere after a couple of radix tree oopses popped up.

Not sure why it didn't trigger Andrew's test suite, but I guess that's
something to add.

> My suggested patch is below.
> 
> Please review, confirm, and Ack:
> 

It should be basically an identical block to the one below in the main
loop, yeah? You're missing the nr_cleared_tags bit.

Something like:

    tags[tag] = 1;
    if (tag_get(pathp->node, tag, pathp->offset)) {
       tag_clear(pathp->node, tag, pathp->offset);
       if (!any_tag_set(pathp->node, tag)) {
          tags[tag] = 0;
          nr_cleared_tags++;
       }
    }

And you can add an
Acked-by: Nick Piggin <npiggin@suse.de>

Thanks,
Nick

> Thanks,
> NeilBrown
> 
> 
> Fix over-zealous clearing of tags in radix_tree_delete.
> 
> Signed-off-by: Neil Brown <neilb@suse.de>
> 
> ### Diffstat output
>  ./lib/radix-tree.c |    2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff ./lib/radix-tree.c~current~ ./lib/radix-tree.c
> --- ./lib/radix-tree.c~current~	2006-02-16 13:22:28.000000000 +1100
> +++ ./lib/radix-tree.c	2006-02-16 13:23:19.000000000 +1100
> @@ -755,7 +755,7 @@ void *radix_tree_delete(struct radix_tre
>  	for (tag = 0; tag < RADIX_TREE_TAGS; tag++) {
>  		if (tag_get(pathp->node, tag, pathp->offset)) {
>  			tag_clear(pathp->node, tag, pathp->offset);
> -			tags[tag] = 0;
> +			tags[tag] = any_tag_set(pathp->node, tag);
>  			nr_cleared_tags++;
>  		} else
>  			tags[tag] = 1;
> 


-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: Possibly bug in radix_tree_delete, and fix.

[Neil Brown]

On Thursday February 16, nickpiggin@yahoo.com.au wrote:
> 
> It should be basically an identical block to the one below in the main
> loop, yeah? You're missing the nr_cleared_tags bit.
> 
> Something like:
> 
>     tags[tag] = 1;
>     if (tag_get(pathp->node, tag, pathp->offset)) {
>        tag_clear(pathp->node, tag, pathp->offset);
>        if (!any_tag_set(pathp->node, tag)) {
>           tags[tag] = 0;
>           nr_cleared_tags++;
>        }
>     }
> 
> And you can add an
> Acked-by: Nick Piggin <npiggin@suse.de>

Yes, that's clearly better.  I've sent the revised patch out.

Thanks,
NeilBrown

Re: Possibly bug in radix_tree_delete, and fix.

[Andrew Morton]

Nick Piggin <nickpiggin@yahoo.com.au> wrote:
>
> Neil Brown wrote:
> > Hi Nick,
> >  I believe there is a bug in radix_tree_delete introduced by:
> > 
> > http://www.kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=d5274261ea46f0aae93820fe36628249120d2f75
> > 
> > The nature of the bug is that if a tag is set on a node that is being
> > deleted, then that tag is unconditionally cleared in the parent of the
> > node, even if the deleted node has siblings with the tag still set.
> > 
> > I don't know what the large-scale consequences of this bug might be,
> > but I'm kinda hoping fixing it will fix a nasty NFS client related
> > oops we are seeing in radix_tree_tag_set ....
> > 
> 
> I think you're right. I was kind of suspecting I might have introduced
> a silly bug somewhere after a couple of radix tree oopses popped up.

Oh fantastic - a filesystem corrupting bug.

> Not sure why it didn't trigger Andrew's test suite, but I guess that's
> something to add.

Could you please do so?  And add in the previous enhancements you made?  I
was never able to sort out the patches you sent.  And test Neil's later
patch (which looks OK to me)?

Re: Possibly bug in radix_tree_delete, and fix.

[Nick Piggin]

Andrew Morton wrote:
> Nick Piggin <nickpiggin@yahoo.com.au> wrote:

>>Not sure why it didn't trigger Andrew's test suite, but I guess that's
>>something to add.
> 
> 
> Could you please do so?  And add in the previous enhancements you made?  I
> was never able to sort out the patches you sent.  And test Neil's later
> patch (which looks OK to me)?
> 

I will do so, give me a few minutes.

I don't think the patches I sent before would look any different now
(actually I'm quite sure I haven't made any new changes), so I'm not
sure if there would be any point, would there?

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com