Bug 132575 – Named element cache can become invalid during HTMLCollection::updateNamedElementCache()

• Component: DOM
• Status: RESOLVED FIXED

[Chris Dumez]

Named element cache can become invalid during HTMLCollection::updateNamedElementCache(). This is because HTMLCollection::updateNamedElementCache() works as follows:
1. Create the named element cache (i.e. hasNamedElementCache() starts returning true)
2. Traverse the HTMLCollection (and thus the DOM tree) to populate the cache

Traversing the DOM tree and looking for matches can cause tree updates (https://code.google.com/p/chromium/issues/detail?id=360474#c6) and thus cache invalidation. Therefore, the named element cache can become invalid while HTMLCollection::updateNamedElementCache() is populating it. When this happens, WebKit crashes:
ASSERTION FAILED: m_namedElementCache
/home/chris/devel/WebKit/Source/WebCore/html/HTMLCollection.cpp(416) : virtual WebCore::Node* WebCore::HTMLCollection::namedItem(const WTF::AtomicString&) const
1   0x7ffff5eb4451 WTFCrash
2   0x7ffff16677c9 WebCore::HTMLCollection::namedItem(WTF::AtomicString const&) const
3   0x7ffff23c5592 WebCore::jsHTMLCollectionPrototypeFunctionNamedItem(JSC::ExecState*)
4   0x7fff9b8980b4

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff5eb4456 in WTFCrash () at /home/chris/devel/WebKit/Source/WTF/wtf/Assertions.cpp:333
333	    *(int *)(uintptr_t)0xbbadbeef = 0;
(gdb) bt
#0  0x00007ffff5eb4456 in WTFCrash () at /home/chris/devel/WebKit/Source/WTF/wtf/Assertions.cpp:333
#1  0x00007ffff16677c9 in WebCore::HTMLCollection::namedItem (this=0x14069c0, name=...) at /home/chris/devel/WebKit/Source/WebCore/html/HTMLCollection.cpp:416
#2  0x00007ffff23c5592 in WebCore::jsHTMLCollectionPrototypeFunctionNamedItem (exec=0x7fffffffa630) at /home/chris/devel/WebKit/WebKitBuild/Debug/DerivedSources/WebCore/JSHTMLCollection.cpp:252



The same issue has been addressed on Blink side:
- https://src.chromium.org/viewvc/blink?view=rev&revision=171062
- https://code.google.com/p/chromium/issues/detail?id=360474

[Chris Dumez]

Created attachment 230849 [details]
Patch

Comment on attachment 230849 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=230849&action=review

> LayoutTests/fast/dom/htmlcollection-selectedOptions-namedItem-crash.html:19
> +

nit. unnecessary empty line

i reviewed the chromium patch so you might want to get a second pair of eyes on this, but otherwise lgtm

[Chris Dumez]

(In reply to comment #3)
> i reviewed the chromium patch so you might want to get a second pair of eyes on this, but otherwise lgtm

Yes, I am going to cc relevant people once the ews has had a chance to chew through it.

[Chris Dumez]

Created attachment 230852 [details]
Patch

[Ryosuke Niwa]

Comment on attachment 230852 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=230852&action=review

> Source/WebCore/ChangeLog:17
> +        The issue is that finding matches in the DOM tree can cause
> +        HTMLCollection::invalidateCache() to be called under certain circumstances and
> +        thus the named element cache object can become invalid while
> +        updateNamedElementCache() is populating it.

What exactly is that circumstance?

[Chris Dumez]

(In reply to comment #6)
> (From update of attachment 230852 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=230852&action=review
> 
> > Source/WebCore/ChangeLog:17
> > +        The issue is that finding matches in the DOM tree can cause
> > +        HTMLCollection::invalidateCache() to be called under certain circumstances and
> > +        thus the named element cache object can become invalid while
> > +        updateNamedElementCache() is populating it.
> 
> What exactly is that circumstance?

This is explained at https://code.google.com/p/chromium/issues/detail?id=360474#c6, basically the stack trace looks like:
HTMLCollection::updateIdNameCache
HTMLCollection::traverseToFirstElement
LiveNodeListBase::firstMatchingElement<WebCore::HTMLCollection>
isMatchingElement<WebCore::HTMLCollection> 
HTMLOptionElement::selected
HTMLSelectElement::updateListItemSelectedStates
HTMLSelectElement::recalcListItems
HTMLOptionElement::setSelectedState
HTMLSelectElement::invalidateSelectedItems
HTMLCollection::invalidateCache
HTMLCollection::invalidateIdNameCacheMaps

So it is for HTMLCollection of selected options (SelectedOptions collection type), we traverse the DOM tree and call the following to see if the Element is a match:
 element.hasTagName(optionTag) && toHTMLOptionElement(element).selected();

The issue is that HTMLOptionElement::selected() can cause HTMLCollection cache invalidation as per above backtrace.

[Ryosuke Niwa]

Comment on attachment 230852 [details]
Patch

Thanks for the clarification.

[Ryosuke Niwa]

Comment on attachment 230852 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=230852&action=review

> LayoutTests/fast/dom/htmlcollection-selectedOptions-namedItem-crash.html:5
> +<head>
> +<script src="../../resources/js-test-pre.js"></script>
> +</head>

We don't need head if we put js-test-pre.js inside body.

[Chris Dumez]

Created attachment 230858 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 230858 [details]
Patch

Clearing flags on attachment: 230858

Committed r168322: <http://trac.webkit.org/changeset/168322>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/16821718>

[Geoffrey Garen]

Comment on attachment 230849 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=230849&action=review

> Source/WebCore/ChangeLog:17
> +        HTMLCollection::invalidateCache() to be called under certain circumstances and
> +        thus the named element cache object can become invalid while
> +        updateNamedElementCache() is populating it.

If the cache becomes invalid during its construction, why is it OK to assign the cache to the collection unconditionally? Wouldn't you end up with an invalid cache? Should there be some kind of check for invalidation inside setNameItemCache?

[Chris Dumez]

(In reply to comment #14)
> (From update of attachment 230849 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=230849&action=review
> 
> > Source/WebCore/ChangeLog:17
> > +        HTMLCollection::invalidateCache() to be called under certain circumstances and
> > +        thus the named element cache object can become invalid while
> > +        updateNamedElementCache() is populating it.
> 
> If the cache becomes invalid during its construction, why is it OK to assign the cache to the collection unconditionally? Wouldn't you end up with an invalid cache? Should there be some kind of check for invalidation inside setNameItemCache?

For this particular case, based on the implementation of HTMLSelectElement::recalcListItems(), I think it is OK. When traversing the DOM tree and reaching the first <option> element in a <select>. We will call HTMLOptionElement::selected() which may result in calling HTMLSelectElement::recalcListItems(). recalcListItems() will make sure:
- Only 1 <option> is selected if m_multiple is false:
  * To do so, it will unselect later <option> elements. This will update only future elements in your traversal so our cache should still be valid.
- If no <option> is selected and m_size is 1 (the <select> only has one <option>), the option will be selected.
  * This will update the 'selected' state of the <option> we are calling HTMLOptionElement::selected() on, so our cache should still be valid.

Basically, HTMLSelectElement::recalcListItems() can only update the selected state of the option we are currently at (while traversing the DOM tree) or the following ones. Since we are doing a forward traversal, what we previous added to the cache should remain valid.

For the record, my patch makes updateNamedElementCache() behave like it used to before this relatively recent change that introduced the regression:
http://trac.webkit.org/changeset/164772

We used to call setHasIdNameCache() at the *end* of the update function, which resulted in the same behavior as with my patch.

[Ryosuke Niwa]

I agree that the fact HTMLSelectElement is implicitly changing the HTML collection's state is really annoying but I can't think of a better way to fix this without pluming through a flag everywhere.