Re: [patch] x86, pat: freeing invalid memtype messages

[Venkatesh Pallipadi <venki@google.com>]

On Mon, Jun 21, 2010 at 7:45 PM, Xiaotian Feng <dfeng@redhat.com> wrote:
> On 06/22/2010 01:54 AM, Suresh Siddha wrote:
>>
>> On Mon, 2010-06-21 at 08:41 -0700, Peter Zijlstra wrote:
>>>
>>> On Mon, 2010-06-21 at 17:33 +0200, Marcin Slusarz wrote:
>>>>
>>>> On Mon, Jun 21, 2010 at 07:07:27PM +0800, Xiaotian Feng wrote:
>>>>>
>>>>> On 06/21/2010 07:02 PM, Peter Zijlstra wrote:
>>>>>>
>>>>>> On Mon, 2010-06-21 at 18:56 +0800, Xiaotian Feng wrote:
>>>>>>
>>>>>>> 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 ;-)
>>>>
>>>> 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.
>
> 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().


Nice detective work! Yes. That kind of hints that max_end
initialization is the problem. The patch I pointed to here
http://marc.info/?l=linux-mm-commits&m=127654225011850&w=2
will have a side-effect without Peter's change and make this problem worse.
This minimal patch here
https://bugzilla.kernel.org/show_bug.cgi?id=16092 comment #2
on a kernel without Peter's change should not have this problem with
insert however. As any new node starts at 0 max_end, updates itself to
memtype->end and calls augment on its parent in rb_insert_color
augment callback.

Thanks,
Venki