x86, pat: freeing invalid memtype messages

Commit 20413f27163 "x86, pat: Fix memory leak in free_memtype" added an error message in free_memtype() if rbt_memtype_erase() returns NULL. The problem is that if CONFIG_X86_PAT is enabled, we use a different implimentation of rbt_memtype_erase() that always returns NULL.

I've modified rbt_memtype_erase() to return an ERR_PTR() on errors and made free_memtype() check for that instead.

Addresses: https://bugzilla.kernel.org/show_bug.cgi?id=16205

Signed-off-by Dan Carpenter <[email protected]>

arch/x86/mm/pat.c +2 -2

index acc15b2..81b7735 100644
@@ -359,10 +359,10 @@ int free_memtype(u64 start, u64 end)
 	entry = rbt_memtype_erase(start, end);
 	spin_unlock(&memtype_lock);
 
-	if (!entry) {
+	if (IS_ERR(entry)) {
 		printk(KERN_INFO "%s:%d freeing invalid memtype %Lx-%Lx\n",
 			current->comm, current->pid, start, end);
-		return -EINVAL;
+		return PTR_ERR(entry);
 	}
 
 	kfree(entry);

arch/x86/mm/pat_rbtree.c +3 -1

index f537087..90e5cbe 100644
@@ -236,8 +236,10 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)
 	struct memtype *data;
 
 	data = memtype_rb_exact_match(&memtype_rbroot, start, end);
-	if (!data)
+	if (!data) {
+		data = ERR_PTR(-EINVAL);
 		goto out;
+	}
 
 	rb_erase(&data->rb, &memtype_rbroot);
 out:

Quoted 8 lines · Dan Carpenter

Commit 20413f27163 "x86, pat: Fix memory leak in free_memtype" added an error message in free_memtype() if rbt_memtype_erase() returns NULL. The problem is that if CONFIG_X86_PAT is enabled, we use a different implimentation of rbt_memtype_erase() that always returns NULL.

I've modified rbt_memtype_erase() to return an ERR_PTR() on errors and made free_memtype() check for that instead.

Quoted 3 lines

Addresses: https://bugzilla.kernel.org/show_bug.cgi?id=16205

Signed-off-by Dan Carpenter <[email protected]>

This patch is probably ok, but it does not address my bug.
I have CONFIG_X86_PAT=y, so rbt_memtype_erase does not always return NULL.

Quoted 8 lines · Dan Carpenter

Commit 20413f27163 "x86, pat: Fix memory leak in free_memtype" added an error message in free_memtype() if rbt_memtype_erase() returns NULL. The problem is that if CONFIG_X86_PAT is enabled, we use a different implimentation of rbt_memtype_erase() that always returns NULL.

I've modified rbt_memtype_erase() to return an ERR_PTR() on errors and made free_memtype() check for that instead.

Quoted 3 lines

Addresses: https://bugzilla.kernel.org/show_bug.cgi?id=16205

Signed-off-by Dan Carpenter<[email protected]>

This patch is probably ok, but it does not address my bug.
I have CONFIG_X86_PAT=y, so rbt_memtype_erase does not always return NULL.

Quoted 36 lines

arch/x86/mm/pat.c +2 -2

index acc15b2..81b7735 100644
@@ -359,10 +359,10 @@ int free_memtype(u64 start, u64 end)
  	entry = rbt_memtype_erase(start, end);
  	spin_unlock(&memtype_lock);
 
-	if (!entry) {
+	if (IS_ERR(entry)) {
  		printk(KERN_INFO "%s:%d freeing invalid memtype %Lx-%Lx\n",
  			current->comm, current->pid, start, end);
-		return -EINVAL;
+		return PTR_ERR(entry);
  	}
 
  	kfree(entry);

arch/x86/mm/pat_rbtree.c +3 -1

index f537087..90e5cbe 100644
@@ -236,8 +236,10 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)
  	struct memtype *data;
 
  	data = memtype_rb_exact_match(&memtype_rbroot, start, end);
-	if (!data)
+	if (!data) {
+		data = ERR_PTR(-EINVAL);
  		goto out;
+	}
 
  	rb_erase(&data->rb,&memtype_rbroot);
  out:

Quoted 8 lines · Dan Carpenter

Commit 20413f27163 "x86, pat: Fix memory leak in free_memtype" added an error message in free_memtype() if rbt_memtype_erase() returns NULL. The problem is that if CONFIG_X86_PAT is enabled, we use a different implimentation of rbt_memtype_erase() that always returns NULL.

I've modified rbt_memtype_erase() to return an ERR_PTR() on errors and made free_memtype() check for that instead.

Quoted 3 lines

Addresses: https://bugzilla.kernel.org/show_bug.cgi?id=16205

Signed-off-by Dan Carpenter<[email protected]>

This patch is probably ok, but it does not address my bug.
I have CONFIG_X86_PAT=y, so rbt_memtype_erase does not always return NULL.

Quoted 36 lines

arch/x86/mm/pat.c +2 -2

index acc15b2..81b7735 100644
@@ -359,10 +359,10 @@ int free_memtype(u64 start, u64 end)
  	entry = rbt_memtype_erase(start, end);
  	spin_unlock(&memtype_lock);
 
-	if (!entry) {
+	if (IS_ERR(entry)) {
  		printk(KERN_INFO "%s:%d freeing invalid memtype %Lx-%Lx\n",
  			current->comm, current->pid, start, end);
-		return -EINVAL;
+		return PTR_ERR(entry);
  	}
 
  	kfree(entry);

arch/x86/mm/pat_rbtree.c +3 -1

index f537087..90e5cbe 100644
@@ -236,8 +236,10 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)
  	struct memtype *data;
 
  	data = memtype_rb_exact_match(&memtype_rbroot, start, end);
-	if (!data)
+	if (!data) {
+		data = ERR_PTR(-EINVAL);
  		goto out;
+	}
 
  	rb_erase(&data->rb,&memtype_rbroot);
  out:

Quoted 11 lines · Marcin Slusarz

Quoted 10 lines · Dan Carpenter

Commit 20413f27163 "x86, pat: Fix memory leak in free_memtype" added an error message in free_memtype() if rbt_memtype_erase() returns NULL. The problem is that if CONFIG_X86_PAT is enabled, we use a different implimentation of rbt_memtype_erase() that always returns NULL.

I've modified rbt_memtype_erase() to return an ERR_PTR() on errors and made free_memtype() check for that instead.

Addresses: https://bugzilla.kernel.org/show_bug.cgi?id=16205

Quoted 4 lines

Quoted 1 line

Signed-off-by Dan Carpenter<[email protected]>

This patch is probably ok, but it does not address my bug.
I have CONFIG_X86_PAT=y, so rbt_memtype_erase does not always return NULL.

Could you please try boot with kernel parameter "debugpat", and show me the output of reserve_memtype/free_memtype ?

Quoted 17 lines · Xiaotian Feng

Quoted 15 lines · Marcin Slusarz

Quoted 11 lines · Dan Carpenter

Commit 20413f27163 "x86, pat: Fix memory leak in free_memtype" added an error message in free_memtype() if rbt_memtype_erase() returns NULL. The problem is that if CONFIG_X86_PAT is enabled, we use a different implimentation of rbt_memtype_erase() that always returns NULL.

I've modified rbt_memtype_erase() to return an ERR_PTR() on errors and made free_memtype() check for that instead.

Addresses: https://bugzilla.kernel.org/show_bug.cgi?id=16205

Signed-off-by Dan Carpenter<[email protected]>

This patch is probably ok, but it does not address my bug.
I have CONFIG_X86_PAT=y, so rbt_memtype_erase does not always return NULL.

Quoted 4 lines

Could you please try boot with kernel parameter "debugpat", and show me the output of reserve_memtype/free_memtype ?

http://kadu.net/~joi/kernel/2010.06.09/2.6.35-rc3-debugpat.txt

Marcin

I guess there might be something wrong between the augmented rbtree insert/remove ..

Quoted 1 line · Xiaotian Feng

I guess there might be something wrong between the augmented rbtree insert/remove ..

The easiest thing is to revert that change and try again, the next step would be to print the full RB tree on each modification and look where it goes wrong.

That said, I did print my fair share of (augmented) RB trees while playing with scheduler patches and I can't remember it ever having messed up like that.

Quoted 8 lines · Peter Zijlstra

Quoted 1 line · Xiaotian Feng

I guess there might be something wrong between the augmented rbtree insert/remove ..

The easiest thing is to revert that change and try again, the next step would be to print the full RB tree on each modification and look where it goes wrong.

Quoted 3 lines

That said, I did print my fair share of (augmented) RB trees while playing with scheduler patches and I can't remember it ever having messed up like that.

He's using 2.6.35-rc2+, without your "rbtree: Undo augmented trees performance damage" patch ;-)

Quoted 12 lines · Xiaotian Feng

Quoted 11 lines · Peter Zijlstra

Quoted 1 line · Xiaotian Feng

I guess there might be something wrong between the augmented rbtree insert/remove ..

The easiest thing is to revert that change and try again, the next step would be to print the full RB tree on each modification and look where it goes wrong.

That said, I did print my fair share of (augmented) RB trees while playing with scheduler patches and I can't remember it ever having messed up like that.

Quoted 2 lines

He's using 2.6.35-rc2+, without your "rbtree: Undo augmented trees performance damage" patch ;-)

I applied it manually (commit 2463eb8b3093995e09a0d41b3d78ee0cf5fb4249 from -tip) to 2.6.35-rc3 and it fixed both acpi's and nouveau's "invalid memtype" messages. Thanks.

Quoted 16 lines · Marcin Slusarz

Quoted 14 lines · Xiaotian Feng

Quoted 11 lines · Peter Zijlstra

Quoted 1 line · Xiaotian Feng

I guess there might be something wrong between the augmented rbtree insert/remove ..

The easiest thing is to revert that change and try again, the next step would be to print the full RB tree on each modification and look where it goes wrong.

That said, I did print my fair share of (augmented) RB trees while playing with scheduler patches and I can't remember it ever having messed up like that.

He's using 2.6.35-rc2+, without your "rbtree: Undo augmented trees performance damage" patch ;-)

Quoted 3 lines

I applied it manually (commit 2463eb8b3093995e09a0d41b3d78ee0cf5fb4249 from -tip) to 2.6.35-rc3 and it fixed both acpi's and nouveau's "invalid memtype" messages. Thanks.

Oh neat, so it actually fixes a bug in the previous augmented rb-tree implementation?

Quoted 17 lines · Peter Zijlstra

Quoted 16 lines · Marcin Slusarz

Quoted 14 lines · Xiaotian Feng

Quoted 11 lines · Peter Zijlstra

Quoted 1 line · Xiaotian Feng

I guess there might be something wrong between the augmented rbtree insert/remove ..

The easiest thing is to revert that change and try again, the next step would be to print the full RB tree on each modification and look where it goes wrong.

That said, I did print my fair share of (augmented) RB trees while playing with scheduler patches and I can't remember it ever having messed up like that.

He's using 2.6.35-rc2+, without your "rbtree: Undo augmented trees performance damage" patch ;-)

Quoted 6 lines

Quoted 3 lines

I applied it manually (commit 2463eb8b3093995e09a0d41b3d78ee0cf5fb4249 from -tip) to 2.6.35-rc3 and it fixed both acpi's and nouveau's "invalid memtype" messages. Thanks.

Oh neat, so it actually fixes a bug in the previous augmented rb-tree implementation?

When I was reviewing your fix, it looked like that prior to your fix we were re-augmenting only at points where we do the tree rotations/color change and at the points of node insertion/removal. I don't think we were re-augmenting all the parent nodes in the path of the selected-node that is going to replace the deleted node.

Perhaps we were hitting this issue here.

Quoted 31 lines · Suresh Siddha

Quoted 17 lines · Peter Zijlstra

Quoted 16 lines · Marcin Slusarz

Quoted 14 lines · Xiaotian Feng

Quoted 11 lines · Peter Zijlstra

Quoted 1 line · Xiaotian Feng

I guess there might be something wrong between the augmented rbtree insert/remove ..

The easiest thing is to revert that change and try again, the next step would be to print the full RB tree on each modification and look where it goes wrong.

That said, I did print my fair share of (augmented) RB trees while playing with scheduler patches and I can't remember it ever having messed up like that.

He's using 2.6.35-rc2+, without your "rbtree: Undo augmented trees performance damage" patch ;-)

Quoted 6 lines

Quoted 3 lines

I applied it manually (commit 2463eb8b3093995e09a0d41b3d78ee0cf5fb4249 from -tip) to 2.6.35-rc3 and it fixed both acpi's and nouveau's "invalid memtype" messages. Thanks.

Oh neat, so it actually fixes a bug in the previous augmented rb-tree implementation?

When I was reviewing your fix, it looked like that prior to your fix we were re-augmenting only at points where we do the tree rotations/color change and at the points of node insertion/removal. I don't think we were re-augmenting all the parent nodes in the path of the selected-node that is going to replace the deleted node.

Quoted 2 lines

Perhaps we were hitting this issue here.

rb_erase was calling the augment callback with successor_parent_cb. That should be doing proper re-augmenting on delete.

May be we are hitting the problem with not-initializing subtree_max_end on insert? That was fixed in a later patch.

Quoted 33 lines · Venkatesh Pallipadi

Quoted 31 lines · Suresh Siddha

Quoted 17 lines · Peter Zijlstra

Quoted 16 lines · Marcin Slusarz

Quoted 14 lines · Xiaotian Feng

Quoted 11 lines · Peter Zijlstra

Quoted 1 line · Xiaotian Feng

I guess there might be something wrong between the augmented rbtree insert/remove ..

The easiest thing is to revert that change and try again, the next step would be to print the full RB tree on each modification and look where it goes wrong.

That said, I did print my fair share of (augmented) RB trees while playing with scheduler patches and I can't remember it ever having messed up like that.

He's using 2.6.35-rc2+, without your "rbtree: Undo augmented trees performance damage" patch ;-)

Quoted 6 lines

Quoted 3 lines

I applied it manually (commit 2463eb8b3093995e09a0d41b3d78ee0cf5fb4249 from -tip) to 2.6.35-rc3 and it fixed both acpi's and nouveau's "invalid memtype" messages. Thanks.

Oh neat, so it actually fixes a bug in the previous augmented rb-tree implementation?

When I was reviewing your fix, it looked like that prior to your fix we were re-augmenting only at points where we do the tree rotations/color change and at the points of node insertion/removal. I don't think we were re-augmenting all the parent nodes in the path of the selected-node that is going to replace the deleted node.

Quoted 8 lines

Quoted 2 lines

Perhaps we were hitting this issue here.

rb_erase was calling the augment callback with successor_parent_cb. That should be doing proper re-augmenting on delete.

May be we are hitting the problem with not-initializing subtree_max_end on insert? That was fixed in a later patch.

Here's the patch I was referring to
http://marc.info/?l=linux-mm-commits&m=127654225011850&w=2

Marcin: Can you try this patch without Peter's patch and see whether there are any issues with that. Just to make sure we don't have issues wuth underlying augmented rbtree algorithm that somehow got fixed or masked for the time being with Peter's change.

Quoted 46 lines · Venkatesh Pallipadi

Quoted 33 lines · Venkatesh Pallipadi

Quoted 31 lines · Suresh Siddha

Quoted 17 lines · Peter Zijlstra

Quoted 16 lines · Marcin Slusarz

Quoted 14 lines · Xiaotian Feng

Quoted 11 lines · Peter Zijlstra

Quoted 1 line · Xiaotian Feng

I guess there might be something wrong between the augmented rbtree insert/remove ..

The easiest thing is to revert that change and try again, the next step would be to print the full RB tree on each modification and look where it goes wrong.

That said, I did print my fair share of (augmented) RB trees while playing with scheduler patches and I can't remember it ever having messed up like that.

He's using 2.6.35-rc2+, without your "rbtree: Undo augmented trees performance damage" patch ;-)

Quoted 6 lines

Quoted 3 lines

I applied it manually (commit 2463eb8b3093995e09a0d41b3d78ee0cf5fb4249 from -tip) to 2.6.35-rc3 and it fixed both acpi's and nouveau's "invalid memtype" messages. Thanks.

Oh neat, so it actually fixes a bug in the previous augmented rb-tree implementation?

When I was reviewing your fix, it looked like that prior to your fix we were re-augmenting only at points where we do the tree rotations/color change and at the points of node insertion/removal. I don't think we were re-augmenting all the parent nodes in the path of the selected-node that is going to replace the deleted node.

Quoted 8 lines

Quoted 2 lines

Perhaps we were hitting this issue here.

rb_erase was calling the augment callback with successor_parent_cb. That should be doing proper re-augmenting on delete.

May be we are hitting the problem with not-initializing subtree_max_end on insert? That was fixed in a later patch.

Here's the patch I was referring to
http://marc.info/?l=linux-mm-commits&m=127654225011850&w=2

Quoted 4 lines

Marcin: Can you try this patch without Peter's patch and see whether there are any issues with that. Just to make sure we don't have issues wuth underlying augmented rbtree algorithm that somehow got fixed or masked for the time being with Peter's change.

I tested this patch few days ago and it produced even more "invalid memtype" messages...

Quoted 17 lines · Peter Zijlstra

Quoted 16 lines · Marcin Slusarz

Quoted 14 lines · Xiaotian Feng

Quoted 11 lines · Peter Zijlstra

Quoted 1 line · Xiaotian Feng

I guess there might be something wrong between the augmented rbtree insert/remove ..

The easiest thing is to revert that change and try again, the next step would be to print the full RB tree on each modification and look where it goes wrong.

That said, I did print my fair share of (augmented) RB trees while playing with scheduler patches and I can't remember it ever having messed up like that.

He's using 2.6.35-rc2+, without your "rbtree: Undo augmented trees performance damage" patch ;-)

Quoted 6 lines

Quoted 3 lines

I applied it manually (commit 2463eb8b3093995e09a0d41b3d78ee0cf5fb4249 from -tip) to 2.6.35-rc3 and it fixed both acpi's and nouveau's "invalid memtype" messages. Thanks.

Oh neat, so it actually fixes a bug in the previous augmented rb-tree implementation?

When I was reviewing your fix, it looked like that prior to your fix we were re-augmenting only at points where we do the tree rotations/color change and at the points of node insertion/removal. I don't think we were re-augmenting all the parent nodes in the path of the selected-node that is going to replace the deleted node.

Perhaps we were hitting this issue here.

thanks,
suresh

Quoted 35 lines · Suresh Siddha

Quoted 24 lines · Peter Zijlstra

Quoted 22 lines · Marcin Slusarz

Quoted 19 lines · Xiaotian Feng

Quoted 6 lines · Peter Zijlstra

Quoted 2 lines · Xiaotian Feng

I guess there might be something wrong between the augmented rbtree insert/remove ..

Quoted 8 lines

The easiest thing is to revert that change and try again, the next step
would be to print the full RB tree on each modification and look where it goes wrong.

That said, I did print my fair share of (augmented) RB trees while playing with scheduler patches and I can't remember it ever having messed up like that.

He's using 2.6.35-rc2+, without your "rbtree: Undo augmented trees performance damage" patch ;-)

Quoted 8 lines

Quoted 5 lines

I applied it manually (commit 2463eb8b3093995e09a0d41b3d78ee0cf5fb4249 from -tip)
to 2.6.35-rc3 and it fixed both acpi's and nouveau's "invalid memtype" messages.
Thanks.

Oh neat, so it actually fixes a bug in the previous augmented rb-tree implementation?

Quoted 7 lines

When I was reviewing your fix, it looked like that prior to your fix we were re-augmenting only at points where we do the tree rotations/color change and at the points of node insertion/removal. I don't think we were re-augmenting all the parent nodes in the path of the selected-node that is going to replace the deleted node.

Perhaps we were hitting this issue here.

Were it from a insert without any rotations/color changes?

This case is performing insert A/remove A/ 2nd insert A/ 2nd remove A/3rd insert A. And the 2nd remove
shows us the invalid memtype.  3rd insert shows us it is in the rbtree. All I can image is that get_subtree_max_end
in memtype_rb_lowest_match returned stale value.

It looks like we don't re-augment the parent nodes if there aren't any rotations/color changes
in the rb_insert_color().