Bug 30651 – Crash when lot of nested tables are loaded

• Status: RESOLVED
• Resolution: FIXED
• Component: DOM

[Rahul Kuchhal]

This is from http://code.google.com/p/chromium/issues/detail?id=20311

Safari also suffers a crash just like Chromium.

chrome_602e0000!WTF::HashTable<WebCore::AtomicStringImpl *,WebCore::AtomicStringImpl *,WTF::IdentityExtractor<WebCore::AtomicStringImpl *>,WTF::PtrHash<WebCore::AtomicStringImpl *>,WTF::HashTraits<WebCore::AtomicStringImpl *>,WTF::HashTraits<WebCore::AtomicStringImpl *> >::contains<WebCore::AtomicStringImpl *,WTF::IdentityHashTranslator<WebCore::AtomicStringImpl *,WebCore::AtomicStringImpl *,WTF::PtrHash<WebCore::AtomicStringImpl *> > >(class WebCore::AtomicStringImpl ** key = 0x00493034)+0x3
chrome_602e0000!WTF::HashTable<WebCore::AtomicStringImpl *,WebCore::AtomicStringImpl *,WTF::IdentityExtractor<WebCore::AtomicStringImpl *>,WTF::PtrHash<WebCore::AtomicStringImpl *>,WTF::HashTraits<WebCore::AtomicStringImpl *>,WTF::HashTraits<WebCore::AtomicStringImpl *> >::contains(class WebCore::AtomicStringImpl ** key = 0x00493034)+0x1a
chrome_602e0000!WTF::HashSet<WebCore::AtomicStringImpl *,WTF::PtrHash<WebCore::AtomicStringImpl *>,WTF::HashTraits<WebCore::AtomicStringImpl *> >::contains(class WebCore::AtomicStringImpl ** value = 0x00493034)+0x1a
chrome_602e0000!WebCore::HTMLParser::isAffectedByResidualStyle(class WebCore::AtomicString * tagName = 0x04489e20)+0x459
chrome_602e0000!WebCore::HTMLParser::popBlock(class WebCore::AtomicString * tagName = 0x04489e20, bool reportErrors = false)+0x118
chrome_602e0000!WebCore::HTMLParser::insertNode(class WebCore::Node * n = 0x0448fdc0, bool flat = false)+0xd1
chrome_602e0000!WebCore::HTMLParser::handleError(class WebCore::Node * n = 0x0448fdc0, bool flat = false, class WebCore::AtomicString * localName = 0x00f2306c, int tagPriority = 7)+0x1371
chrome_602e0000!WebCore::HTMLParser::insertNode(class WebCore::Node * n = 0x0448fdc0, bool flat = false)+0x173
chrome_602e0000!WebCore::HTMLParser::handleError(class WebCore::Node * n = 0x0448fdc0, bool flat = false, class WebCore::AtomicString * localName = 0x00f2306c, int tagPriority = 7)+0x1371
chrome_602e0000!WebCore::HTMLParser::insertNode(class WebCore::Node * n = 0x0448fdc0, bool flat = false)+0x173
chrome_602e0000!WebCore::HTMLParser::handleError(class WebCore::Node * n = 0x0448fdc0, bool flat = false, class WebCore::AtomicString * localName = 0x00f2306c, int tagPriority = 7)+0x1371
chrome_602e0000!WebCore::HTMLParser::insertNode(class WebCore::Node * n = 0x0448fdc0, bool flat = false)+0x173
chrome_602e0000!WebCore::HTMLParser::handleError(class WebCore::Node * n = 0x0448fdc0, bool flat = false, class WebCore::AtomicString * localName = 0x00f2306c, int tagPriority = 7)+0x1371
chrome_602e0000!WebCore::HTMLParser::insertNode(class WebCore::Node * n = 0x0448fdc0, bool flat = false)+0x173
chrome_602e0000!WebCore::HTMLParser::handleError(class WebCore::Node * n = 0x0448fdc0, bool flat = false, class WebCore::AtomicString * localName = 0x00f2306c, int tagPriority = 7)+0x1371
chrome_602e0000!WebCore::HTMLParser::insertNode(class WebCore::Node * n = 0x0448fdc0, bool flat = false)+0x173
chrome_602e0000!WebCore::HTMLParser::handleError(class WebCore::Node * n = 0x0448fdc0, bool flat = false, class WebCore::AtomicString * localName = 0x00f2306c, int tagPriority = 7)+0x1371
chrome_602e0000!WebCore::HTMLParser::insertNode(class WebCore::Node * n = 0x0448fdc0, bool flat = false)+0x173
chrome_602e0000!WebCore::HTMLParser::handleError(class WebCore::Node * n = 0x0448fdc0, bool flat = false, class WebCore::AtomicString * localName = 0x00f2306c, int tagPriority = 7)+0x1371
chrome_602e0000!WebCore::HTMLParser::insertNode(class WebCore::Node * n = 0x0448fdc0, bool flat = false)+0x173
chrome_602e0000!WebCore::HTMLParser::handleError(class WebCore::Node * n = 0x0448fdc0, bool flat = false, class WebCore::AtomicString * localName = 0x00f2306c, int tagPriority = 7)+0x1371
chrome_602e0000!WebCore::HTMLParser::insertNode(class WebCore::Node * n = 0x0448fdc0, bool flat = false)+0x173
chrome_602e0000!WebCore::HTMLParser::handleError(class WebCore::Node * n = 0x0448fdc0, bool flat = false, class WebCore::AtomicString * localName = 0x00f2306c, int tagPriority = 7)+0x1371
chrome_602e0000!WebCore::HTMLParser::insertNode(class WebCore::Node * n = 0x0448fdc0, bool flat = false)+0x173
chrome_602e0000!WebCore::HTMLParser::handleError(class WebCore::Node * n = 0x0448fdc0, bool flat = false, class WebCore::AtomicString * localName = 0x00f2306c, int tagPriority = 7)+0x1371
chrome_602e0000!WebCore::HTMLParser::insertNode(class WebCore::Node * n = 0x0448fdc0, bool flat = false)+0x173
chrome_602e0000!WebCore::HTMLParser::handleError(class WebCore::Node * n = 0x0448fdc0, bool flat = false, class WebCore::AtomicString * localName = 0x00f2306c, int tagPriority = 7)+0x1371
chrome_602e0000!WebCore::HTMLParser::insertNode(class WebCore::Node * n = 0x0448fdc0, bool flat = false)+0x173
chrome_602e0000!WebCore::HTMLParser::handleError(class WebCore::Node * n = 0x0448fdc0, bool flat = false, class WebCore::AtomicString * localName = 0x00f2306c, int tagPriority = 7)+0x1371
chrome_602e0000!WebCore::HTMLParser::insertNode(class WebCore::Node * n = 0x0448fdc0, bool flat = false)+0x173

Open the attached html to see the crash.

[Rahul Kuchhal]

Created attachment 41616 [details]
html to reproduce crash

[Hayato Ito]

Created attachment 42735 [details]
Fix infinite mutual recursion

[Hayato Ito]

I figured out why this happens:

The root cause is infinite mutual recursive in HTMLParser.

1. Suppose HTMLParser's m_blockStack is in the following state:

   4095   tbody
   4094   table
   4093   td
   4092   tr
   4091   tbody
   4091   table
   ...

   And a next token to be processed is |tr|.

2. HTMLParser:insertNode(|tr|) is called.

   Before trying to insert |tr|, HTML:insertNode method checks whether m_blocksInStack reaches cMaxBlockDepth (=4096) or not.
   Because it reaches cMaxBlockDepth, the top emlement, |tbody|, is popped from the m_blockStack.

   m_blockStack is now in the following state:

   4095
   4094   table
   4093   td
   4092   tr
   4091   tbody
   4091   table
   ...

3. Try to insert |tr| element, but |tr| element must be a child of |tbody|. m_current->addChild(n) failed and handleError is called.

4. In HTML:handleError, a parent element of |tr| is deduced and |tbody| is pushed to m_blockStack.

  4095   tbody
  4094   table
  4093   td
  4092   tr
  4091   tbody
  4091   table
  ...


  Because the error is handled, insertNode(|tr|) is called *again* at the end of handleError.

5. Back to 1, causing infinite mutually recursive call between HTMLParser::insertNode and HTMLParser::handleErrors.


I've created a patch to avoid the infinite mutual recursive.

[Darin Adler]

Comment on attachment 42735 [details]
Fix infinite mutual recursion

This will probably cause performance regression if it's not inlined. The insertNode function is quite hot, and calling a function for tagPriorityOfNode is probably going to make it too slow.

I'm just going to say review- because it seems easy to mark it inline.

I think all three of these functions should be marked inline and put at the top of the file before calls to them.

[Hayato Ito]

Created attachment 42817 [details]
Make three functions inline

[Hayato Ito]

Thank you for the review.
I made three functions inline.

[Hayato Ito]

Hi, darin

Could you review this?

[Darin Adler]

Comment on attachment 42817 [details]
Make three functions inline

r=me

The key here is performance. We'll need to carefully test to see this has not made parsing slower.

[Eric Seidel (no email)]

Comment on attachment 42817 [details]
Make three functions inline

Chromium performance bots should notice a perf change.

[Kent Tamura]

Comment on attachment 42817 [details]
Make three functions inline

I'm landing this patch manually.

[Kent Tamura]

Committed r51101: <http://trac.webkit.org/changeset/51101>