107600 - mCachedIndex is uninitialized in nsContentSubtreeIterator

Status: RESOLVED FIXED

(SeaMonkey :: UI Design, defect)

Description

[Randell Jesup [:jesup] (needinfo me)]

In nsContentSubtreeIterator::Init(), mCachedIndex is uninitialized.  On the
first call to Next, it so happens that the value is usually out-of-bounds and so
a null entry is returned by ChildAt, and we regenerate the index.  If it's
in-bounds (but not correct), or if (as we are) we change nsVoidArray to not
bounds-check all accesses, this will cause a crash.

I'll check in this fix after r=/sr=.

Right before the end of ::Init(), we need this:


+  // we need a valid mCachedIndex for the first call to Next, etc
+  nsCOMPtr<nsIContent> parent;
+  if (NS_FAILED(mCurNode->GetParent(*getter_AddRefs(parent))) || !parent ||
+      NS_FAILED(parent->IndexOf(mCurNode,mCachedIndex)))
+  {
+      return NS_ERROR_FAILURE;
+  }
+
  return NS_OK;
}

Comment 1

[Randell Jesup [:jesup] (needinfo me)]

My apologies.  On further inspection, it's worse than that.  The subtree
iterator calls GetNext/PrevSibling in Init before everything is set up.  A
simpler solution is to set mCachedIndex to -1, and check for that in
GetNextSibling/etc.  In the process of doing that, I found that in two cases in
the NextNode (post-order) and PrevNode (pre-order) it wasn't checking for a
changed index and regenerating as it does in GetNextSibling.  This could cause
it to use bad indexes if the content tree were modified as in
search-and-replace.

This bug was introduced as part of jfrancis' refactoring back into the old-style
code flow late in the 31770 process and I didn't catch it on review (the danger
of looking at diffs instead of code).

Patch to be attached.

Comment 2

[Randell Jesup [:jesup] (needinfo me)]

Attachment: Complete patch for review

Comment 3

[Randell Jesup [:jesup] (needinfo me)]

Need r/sr to checkin

Comment 4

[Chris Waterson]

Comment on attachment 55790 [details] [diff] [review]
Complete patch for review

sr=waterson

Comment 5

[Joe Francis]

Randell, I have some serious reservations about this.  Do not check this in
until I comment further here.  I need to get some questions answered about the
voidArray work that triggered this before I can comment further.

mCachedIndex is not used with any VoidArray calls.  I can only assume you are
referring to VoidArray calls under the hood of nsIContent::ChildAt(), which is
where the mCachedIndex value gets used.

Am I to understand the nsIContent::ChildAt() will now crash if you ask for a
child that is out of range?  If so, that sounds like quite the change.  What
about ChildAt(0)?  Will that always succeed, even if there are no children?

Comment 6

[Randell Jesup [:jesup] (needinfo me)]

nsGenericElement::ChildAt() _is_ protected again past-end references (including
0 for an empty array); we looked at not protecting it, but it just wasn't
possible at this time.  nsVoidArray (when used directly) will not be.  Currently
the code in Mozilla is split - lots of it assumes nsVoidArray (etc) works like
C++ arrays (no checking), and a fair bit assumes that checking is done.

We could add a FastChildAt call, which would actually be a noticable win for
heavy-iterator-users like Find.

I didn't touch ContentIterator until one of my asserts fired on a ChildAt(about
-600 million) reference.  Once I went into the code, in addition to fixing the
unitialized indexes, I also discovered that 2 spots were missing checks for
modification of the content tree and fixed those.

The ChildAt() changes (if you look at them) are all oriented to avoiding using
negative indexes.

Comment 7

[Joe Francis]

If ChildAt is not going to crash (for any value, including negative), we have no
bug here.  If it will crash for negative values only then the only change needed
is to initialize mCachedIndex with zero.

Stylistically mCachedIndex should be initialized to zero anyway, and it is even
a tiny performance win.  This is because it's first value constitutes a free
guess at what it's value should be, and zero will be right more often than a
random value will be right.

Comment 8

[Joe Francis]

Attachment: revised patch

Comment 9

[Joe Francis]

I'm paying too much attention to the description of this bug, and not enough to
the patch.  From the description, initializing mCachedIndex is all we need.  

But given RJ's changes to ChildAt(), we also need the fist hunk of his proposed
patch (which has nothing to do with mCachedIndex).  And the hunks at lines 712
and  769 are useful although unrelated to this bug.

posting a new patch shortly...

Comment 10

[Joe Francis]

uhh, fist hunk = *first* hunk

Comment 11

[Joe Francis]

Attachment: YARP (Yet Another Revised Patch)

Comment 12

[Randell Jesup [:jesup] (needinfo me)]

>If ChildAt is not going to crash (for any value, including negative),

	It will crash for negative values.

>Stylistically mCachedIndex should be initialized to zero anyway, and it is even
>a tiny performance win.  This is because it's first value constitutes a free
>guess at what it's value should be, and zero will be right more often than a
>random value will be right.

	Actually ChildAt(0) and IndexOf(element in index 0) are basically the same
cost.  If we init to 0 and it's not the right value however, then we have to
make both calls.  Still, it's a trivial difference, and only on the first
iteration.  Also, the regular iterator doesn't normally use mCachedIndex - only
the SubtreeIterator needs it inited (again a trivial difference though).

Since my nits are totally trivial performance issues, r=[e-mail] on
YARP.

waterson or kin, could you re-sr the revised patch in
http://bugzilla.mozilla.org/attachment.cgi?id=56338&action=view
?

Comment 13

[Chris Waterson]

sr=waterson on YARP!

Comment 14

[Randell Jesup [:jesup] (needinfo me)]

Fix checked in.  Note: jfrancis' line numbers messed with patch's mind, so I
applied by hand.  Also reordered the initializers for
nsContentIterator::nsContentIterator to remove a compiler warning.