Compare Revisions

HTML parser threading

Revision 345499:

Revision 345499 by Sheppy on

Revision 370897:

Revision 370897 by tklein on

Title:
HTML parser threading
HTML parser threading
Slug:
Mozilla/Gecko/HTML_parser_threading
Mozilla/Gecko/HTML_parser_threading
Tags:
Gecko
"Gecko"
Content:

Revision 345499
Revision 370897
n71      After some tree ops have been move the the staging queue, tn71      After some tree ops have been moved to the staging queue, t
>he <code>nsIRunnable</code> held in <code>mExecutorFlusher</code>>he <code>nsIRunnable</code> held in <code>mExecutorFlusher</code>
> is dispatched to the main thread. (The same runnable is used rep> is dispatched to the main thread. (The same runnable is used rep
>eatedly in order to avoid cross-thread refcounting issues.)>eatedly in order to avoid cross-thread refcounting issues.)
n86      Element names, attribute names and the doctype name are repn86      Element names, attribute names and the doctype name are rep
>resented as <code>nsIAtom</code>s. Pre-interned attribute and ele>resented as <code>nsIAtom</code>s. Pre-interned attribute and ele
>ment names hold atoms that are actually app-wide <code>nsStaticAt>ment names hold atoms that are actually app-wide <code>nsStaticAt
>om</code>s. Since <code>nsStaticAtom</code>s are valid app-wide, >om</code>s. Since <code>nsStaticAtom</code>s are valid app-wide, 
>these atoms work right app-wide on the main thread. For other ato>these atoms work right app-wide on the main thread. For other ato
>ms, the parser use <code>nsHtml5Atom</code> objects that are atom>ms, the parser uses <code>nsHtml5Atom</code> objects that are ato
>ic only within the scope of an <code>nsHtml5AtomTable</code>. The>mic only within the scope of an <code>nsHtml5AtomTable</code>. Th
>re is one <code>nsHtml5AtomTable</code> per each <code>nsHtml5Par>ere is one <code>nsHtml5AtomTable</code> per each <code>nsHtml5Pa
>ser</code> and one per each <code>nsHtml5StreamParser</code>. Thu>rser</code> and one per each <code>nsHtml5StreamParser</code>. Th
>s, each tokenizer/tree builder pair sees atoms that are atomic (p>us, each tokenizer/tree builder pair sees atoms that are atomic (
>ointer-comparable) within the tokenizer/tree builder pair. Howeve>pointer-comparable) within the tokenizer/tree builder pair. Howev
>r, when tree ops are executed, every atom has to be tested for be>er, when tree ops are executed, every atom has to be tested for b
>ing a static atom (using <code>IsStaticAtom()</code>). If the ato>eing a static atom (using <code>IsStaticAtom()</code>). If the at
>m isn't static, a corresponding normal main-thread dynamically-al>om isn't static, a corresponding normal main-thread dynamically-a
>located atom has to be obtained for the same string and used inst>llocated atom has to be obtained for the same string and used ins
>ead of the <code>nsHtml5Atom</code>. <code>nsHtml5Atom</code> obj>tead of the <code>nsHtml5Atom</code>. <code>nsHtml5Atom</code> ob
>ects are guaranteed be immutable and to stay alive for the lifeti>jects are guaranteed to be immutable and to stay alive for the li
>me of the parser instance, so it's safe for the main thread to ca>fetime of the parser instance, so it's safe for the main thread t
>ll their methods (as is necessary to find the corresponding norma>o call their methods (as is necessary to find the corresponding n
>l atom).>ormal atom).
87    </p>
88    <p>87    </p>
88    <p>
89      References to DOM nodes in tree ops are of type <code>nsICo89      References to DOM nodes in tree ops are of type <code>nsICo
>ntent**</code> and are called content handles. A handle points to>ntent**</code> and are called content handles. A handle points to
> memory allocated by the tree builder and guaranteed to stick aro> memory allocated by the tree builder and guaranteed to stick aro
>und for the life time of the parser. The tree builder never deref>und for the life time of the parser. The tree builder never deref
>erences a content handle. In fact, a content handle won't have an>erences a content handle. In fact, a content handle won't have an
> actual node behind it initially. Only when the tree op executor > actual node behind it initially. Only when the tree op executor 
>executes a node creation tree op, the <code>nsIContent*</code> th>executes a node creation tree op, the <code>nsIContent*</code> th
>at points to the node gets written to the memory location pointed>at points to the node gets written to the memory location pointed
> to by the <code>nsIContent**</code>. For any given content handl> to by the <code>nsIContent**</code>. For any given content handl
>e, the node creation tree op is always the first tree op in queue>e, the node creation tree op is always the first tree op in queue
> that uses that handle, so subsequent non-creation tree ops can s> that uses that handle, so subsequent non-creation tree ops can s
>afely dereference the handle to obtain a real node. Nodes created>afely dereference the handle to obtain a real node. Nodes created
> by tree ops owned by the parser for the lifetime of the parser, > by tree ops are owned by the parser for the lifetime of the pars
>so for refcounting purposes, the parser owns each <code>nsIConten>er, so for refcounting purposes, the parser owns each <code>nsICo
>t</code> object it creates by one reference no matter how many co>ntent</code> object it creates by one reference no matter how man
>pies of the content handle for the node exist inside the parser. >y copies of the content handle for the node exist inside the pars
>(This indeed means that removing parser-created nodes from the DO>er. (This indeed means that removing parser-created nodes from th
>M during parsing doesn't release memory until the parser stops pa>e DOM during parsing doesn't release memory until the parser stop
>rsing, which is, in theory, a problem for long polling using HTML>s parsing, which is, in theory, a problem for long polling using 
> in an iframe e.g. for a chat app.)>HTML in an iframe e.g. for a chat app.)
n98      When the executor flushing runnable fires on the main threan98      When the executor flushing runnable fires on the main threa
>d, it calls <code>nsHtml5TreeOpExecutor::RunFlushLoop()</code>. T>d, it calls <code>nsHtml5TreeOpExecutor::RunFlushLoop()</code>. T
>his method returns immediately if another invocation of it is alr>his method returns immediately if another invocation of it is alr
>eady on the call stack (nested event loop case). The method then >eady on the call stack (nested event loop case). The method then 
>enter a loop that has a bunch of return conditions (including par>enters a loop that has a bunch of return conditions (including pa
>ser termination).>rser termination).
n107      The last op in the queue may be an op for attempting to exen107      The last op in the queue may be an op for attempting to exe
>cute a script that may blocks the parser (ops for attempting to e>cute a script that may block the parser (ops for attempting to ex
>xecute async and defer scripts are normal tree ops and don't need>ecute async and defer scripts are normal tree ops and don't need 
> to be the last op in a queue). The parts of the parser that driv>to be the last op in a queue). The parts of the parser that drive
>e the tokenizer/tree builder pairs guarantee to flush tree ops im> the tokenizer/tree builder pairs guarantee to flush tree ops imm
>mediately if a script execution tree op is generated. (The tree b>ediately if a script execution tree op is generated. (The tree bu
>uilder makes the tokenizer return immediately when such an op is >ilder makes the tokenizer return immediately when such an op is g
>generated.) Thus, a tree op that may cause the parser to can only>enerated.) Thus, a tree op that may cause the parser to block can
> occur as the last op a queue that <code>RunFlushLoop</code> sees> only occur as the last op in a queue that <code>RunFlushLoop</co
>.>de> sees.
n113      When the parser thread sees that it has generated a tree opn113      When the parser thread sees that it has generated a tree op
> that attempts to execute a (non-async, non-defer) script, it sta> that attempts to execute a (non-async, non-defer) script, it sta
>rts speculating. It acquires <code>mSpeculationMutex</code> and w>rts speculating. It acquires <code>mSpeculationMutex</code> and w
>hile holding it, it creates a new speculation and adds it to the >hile holding it, it creates a new speculation and adds it to the 
>queue of speculations, flushes the tree ops to the main thread, m>queue of speculations, flushes the tree ops to the main thread, m
>arks the <code>nsHtml5StreamParser</code> as being in a speculati>arks the <code>nsHtml5StreamParser</code> as being in a speculati
>ng state and sets the newly created speculation object as the tre>ng state and sets the newly created speculation object as the tre
>e op sink (instead of the tree op stage described earlier) of the>e op sink (instead of the tree op stage described earlier) of the
> tree builder. The speculation object has a queue of tree ops (in> tree builder. The speculation object has a queue of tree ops (in
>to which the tree builder will now flush ops to instead of the tr>to which the tree builder will now flush ops to instead of the tr
>ee op stage), an owning reference to the <code>nsHtml5OwningUTF16>ee op stage), an owning reference to the <code>nsHtml5OwningUTF16
>Buffer</code> that contains the starting point of the speculation>Buffer</code> that contains the starting point of the speculation
>, an index into the <code>nsHtml5OwningUTF16Buffer</code> definin>, an index into the <code>nsHtml5OwningUTF16Buffer</code> definin
>g the exact starting point within the buffer, the line number of >g the exact starting point within the buffer, the line number of 
>the tokenizer at that point and a snapshop of the tree op state. >the tokenizer at that point and a snapshot of the tree op state. 
>The line number and the snapshop are also added to the tree op th>The line number and the snapshot are also added to the tree op th
>at attempts to execute scripts (before flushing it).>at attempts to execute scripts (before flushing it).
114    </p>
115    <p>114    </p>
115    <p>
116      The tree builder snapshot contain a copy of the tree builde116      The tree builder snapshot contains a copy of the tree build
>r stack, a copy of the list of open formatting elements and copie>er stack, a copy of the list of open formatting elements and copi
>s various fields that define the tree builder state. It contains >es of various fields that define the tree builder state. It conta
>all the information that is necessary to load back into the tree >ins all the information that is necessary to load back into the t
>builder to restore it into a behaviorally equivalent state.>ree builder to restore it into a behaviorally equivalent state.
n149      If there is data in <code>document.write()</code> input aftn149      If there is data in <code>document.write()</code> input aft
>er a an external script (or any data at all if a previous <code>d>er a an external script (or any data at all if a previous <code>d
>ocument.write()</code> call has contained an external script and >ocument.write()</code> call has contained an external script and 
>blocked the parser), the data is left is a linked list of <code>n>blocked the parser), the data is left in a linked list of <code>n
>sHtml5OwningUTF16Buffer</code> objects. (How exactly data is inse>sHtml5OwningUTF16Buffer</code> objects. (How exactly data is inse
>rted into the buffer list depends on parser keys when <code>docum>rted into the buffer list depends on parser keys when <code>docum
>ent.write()</code> is invoked re-entrantly, but that's outside th>ent.write()</code> is invoked re-entrantly, but that's outside th
>e scope of this document, since this document is about parser thr>e scope of this document, since this document is about parser thr
>eading.)>eading.)
n170      If there are more than one speculation in the queue and if n170      If there is more than one speculation in the queue and if t
>the speculation is successful, we can dequeue the first speculati>he speculation is successful, we can dequeue the first speculatio
>on while holding <code>mSpeculationMutex</code> without bothering>n while holding <code>mSpeculationMutex</code> without bothering 
> the parser thread. In this case, the tree ops from the speculati>the parser thread. In this case, the tree ops from the speculatio
>on are flushed into the tree op executor and <code>ContinueAfterS>n are flushed into the tree op executor and <code>ContinueAfterSc
>cripts()</code> return early. (<code>nsHtml5TreeOpExecutor::RunFl>ripts()</code> returns early. (<code>nsHtml5TreeOpExecutor::RunFl
>ushLoop</code> is on the call stack already in this case and will>ushLoop</code> is on the call stack already in this case and will
> loop around to start flushing the ops right away.)> loop around to start flushing the ops right away.)
n179      If the speculation failed, the first buffer corresponding tn179      If the speculation failed, the first buffer corresponding t
>o the starting point of the speculation gets it start index resto>o the starting point of the speculation gets its start index rest
>red to the index stored on the speculation object. Subsequent buf>ored to the index stored on the speculation object. Subsequent bu
>fers get their start index reset back to zero. The tokenizer gets>ffers get their start index reset back to zero. The tokenizer get
> its line number restored from the speculation object. This equiv>s its line number restored from the speculation object. This is e
>alent to rewinding the input to where it was when speculation sta>quivalent to rewinding the input to where it was when speculation
>rted.> started.
n200      When the tree builder on the parser thread encounters HTML n200      When the tree builder on the parser thread encounters HTML 
><code>script</code>, stylesheet <code>link</code>, <code>video</c><code>script</code>, stylesheet <code>link</code>, <code>video</c
>ode> (with a poster frame), <code>base</code> or <code>img</code>>ode> (with a poster frame), <code>base</code> or <code>img</code>
> or SVG <code>script</code>, <code>style</code> or <code>image</c> or SVG <code>script</code>, <code>style</code> or <code>image</c
>ode> elements, preload operations are appended to a speculative l>ode> elements, preload operations are appended to a speculative l
>oad queue. There speculative load operations are flushed to the m>oad queue. There speculative load operations are flushed to the m
>ain thread (via the staging area) whenever tree ops are flushed a>ain thread (via the staging area) whenever tree ops are flushed a
>nd alse whenever <code>nsHtml5StreamParser::ParseAvailableData()<>nd also whenever <code>nsHtml5StreamParser::ParseAvailableData()<
>/code> is about to stop working. That is, when the parser thread >/code> is about to stop working. That is, when the parser thread 
>is parsing speculatively, speculative loads continue to be flushe>is parsing speculatively, speculative loads continue to be flushe
>d to the main thread even though tree ops accumulate into the spe>d to the main thread even though tree ops accumulate into the spe
>culations.>culations.
201    </p>
202    <p>201    </p>
202    <p>
203      On the main thread, the speculative tokenizer/tree builder 203      On the main thread, the speculative tokenizer/tree builder 
>pair used for parsing <code>document.write()</code> input that di>pair used for parsing <code>document.write()</code> input that di
>dn't get parsed by the main <code>document.write()</code> tokeniz>dn't get parsed by the main <code>document.write()</code> tokeniz
>er/tree builder synchronously also send speculative loads to the >er/tree builder synchronously also sends speculative loads to the
>tree op executor.> tree op executor.
t212      Additionally, the speculative load queue is used for transft212      Additionally, the speculative load queue is used for transf
>erring information from the parser thread to the main thread when>erring information from the parser thread to the main thread when
> the information needs to arrive before starting any speculative > the information needs to arrive before starting any speculative 
>loads and when the information in known not to be speculative. Th>loads and when the information is known not to be speculative. Th
>ere are two such pieces of information: the manifest URL for an A>ere are two such pieces of information: the manifest URL for an A
>pp Cache manifest and the character encoding for the document.>pp Cache manifest and the character encoding for the document.

Back to History