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

[Venkatesh Pallipadi]

On Mon, Jun 21, 2010 at 11:08 AM, Venkatesh Pallipadi <venki@xxxxxxxxxx> wrote:
> On Mon, Jun 21, 2010 at 10:54 AM, Suresh Siddha
> <suresh.b.siddha@xxxxxxxxx> 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.
>>
>
> 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.

Thanks,
Venki
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/