HTML parser threading
The HTML parser parses data received from the network off the main thread. (There's currently one parser thread serving all parser instances.) Data received from
document.write() is parsed on the main thread.
nsHtml5Parser contains the code for dealing with data from
document.write(). (For historical reasons, it also contains unrelated fragment parsing code that should be refactored into a separate class in due course.)
nsHtml5StreamParser contains the code for dealing with data from the network.
nsHtml5StreamParser. Script-created parsers (i.e. parsers created using
document.open()) don't have an
nsHtml5Parser has one tokenizer/tree builder pair for parsing data from
document.write(). It also has another lazily initialized tokenizer/tree builder for speculatively scanning the tail of
document.write() data when the parser blocks without parsing the
document.write() data to completion.
nsHtml5StreamParser has one tokenizer/tree builder pair for parsing data from the network.
nsHtml5Parser has an associated
nsHtml5TreeOpExecutor that turns the output (tree operations; discussed later) of the portable parser core into actions performed on the Gecko DOM.
nsHtml5Parser is constructed without an
nsHtml5StreamParser due to legacy code structure around parser creation. If the parser is not script-created,
nsHtml5Parser::MarkAsNotScriptCreated() is called to create an
nsHtml5StreamParser for the
Due to legacy interface design oddities, an
nsHtml5Parser is initialized by calling
nsHtml5Parser::Parse(nsIURI*, nsIRequestObserver*, void*, nsDTDMode). That method call doesn't yet cause anything to be parsed, though. Actual network data is passed to an
nsHtml5StreamParser is the
nsIStreamListener implementation obtained by calling
nsIStreamListener methods (
OnStopRequest) are called on the main thread.
OnStartRequest does all sorts of initialization on the main thread. At that point, nothing has happened on the parser thread yet and the
nsHtml5StreamParser lives fully on the main thread.
nsHtml5StreamParser gets some of its methods called on the main thread and some called on the parser thread. The method implementations assert which thread they are supposed to be called on.
OnStopRequest on the main thread post runnables on to the parser thread. There runnables obtain
mTokenizerMutex and call
DoStopRequest, repectively, on the parser thread. These two methods along with
TimerFlush (discussed later) are the entry points from the parser thread event loop into
The runnables hold
mTokenizerMutex for the entire duration of the
mTokenizerMutex protects most data structures on
nsHtml5StreamParser from concurrent access.
The runnables need to keep the
nsHtml5StreamParser instance alive, so they have to
AddRef it. However, if they
Released on the parser thread,
nsHtml5StreamParser could be
deleted from the parser thread, which would lead to all sorts of badness, because
nsHtml5StreamParser has fields that hold objects that aren't safe to
Release except from the main thread. The runnables use
nsHtml5RefPtr sends runnables back to the main thread to call Release on
nsHtml5StreamParser on the main thread.
DoDataAvailable performs character encoding sniffing on the data if an encoding wasn't declared on the enclosing protocol (HTTP) level. Once a Unicode decoder has been set up,
DoDataAvailable passes the byte data to the decoder whose output is accumulated into a linked list of
nsHtml5OwningUTF16Buffer objects are then passed to the tokenizer in sequence by the
ParseAvailableData() method. The tokenizer calls into the tree builder which outputs
nsHtml5TreeOperation objects (tree ops) into a queue. Each tree op represents a small operation, such as element creation or appending a node into another, that can later be performed on the main thread.
mTokenizerMutex is being held by the parser thread for the entire time that the tokenizer runs.
ParseAvailableData() checks for parser termination or interruption from time to time. The termination and interruption indicators are guarded by a more narrowly scoped
ParseAvailableData() has the opportunity to receive an order to terminate or interrupt even while the parser thread is holding
The tree op queue is flushed to the main thread from time to time. There's a timer that calls
TimerFlush() (which takes
mTokenizerMutex). Tree ops from the queue in the tree builder are moved to a tree op stage (
nsHtml5TreeOpStage). The staging queue is protected by a mutex. This way, the queues into which tree ops are produced and the queues from which they are consumed don't need to involve a mutex on each modification. It's more efficient to obtain a mutex only every once in a while when a whole bunch of tree ops is moved to or from the staging queue.
After some tree ops have been moved to the staging queue, the
nsIRunnable held in
mExecutorFlusher is dispatched to the main thread. (The same runnable is used repeatedly in order to avoid cross-thread refcounting issues.)
The tree ops hold various heap-allocated objects that end up crossing the thread boundary. These objects are memory managed as follows:
Attribute holders (
nsHtml5HtmlAttributes objects) are allocated using
new by the tokenizer. The tree builder either transfers an attribute holder to a tree op whose destructor explicitly
deletes the attribute holder or if the tree builder ends up ignoring an attribute holder, the tree builder
deletes the attribute holder explicitly.
Attribute values, public identifiers (in doctype) and system identifiers (in doctype) are heap-allocated
nsString objects (i.e. pointed to by
nsString*!). Attribute values
nsStrings are deleted by the attribute holder when it gets deleted. Public identifiers and system identifiers are deleted by the tree op or by the portable parser core if they don't make it as far a tree op. The backing
nsStringBuffers are thread-safely refcounted appropriately when the
nsString goes away. (Aside: It would make more sense to make the parser deal with
nsStringBuffers directly without having heap-allocated
Element names, attribute names and the doctype name are represented as
nsIAtoms. Pre-interned attribute and element names hold atoms that are actually app-wide
nsStaticAtoms are valid app-wide, these atoms work right app-wide on the main thread. For other atoms, the parser uses
nsHtml5Atom objects that are atomic only within the scope of an
nsHtml5AtomTable. There is one
nsHtml5AtomTable per each
nsHtml5Parser and one per each
nsHtml5StreamParser. Thus, each tokenizer/tree builder pair sees atoms that are atomic (pointer-comparable) within the tokenizer/tree builder pair. However, when tree ops are executed, every atom has to be tested for being a static atom (using
IsStaticAtom()). If the atom isn't static, a corresponding normal main-thread dynamically-allocated atom has to be obtained for the same string and used instead of the
nsHtml5Atom objects are guaranteed to be immutable and to stay alive for the lifetime of the parser instance, so it's safe for the main thread to call their methods (as is necessary to find the corresponding normal atom).
References to DOM nodes in tree ops are of type
nsIContent** and are called content handles. A handle points to memory allocated by the tree builder and guaranteed to stick around for the life time of the parser. The tree builder never dereferences a content handle. In fact, a content handle won't have an actual node behind it initially. Only when the tree op executor executes a node creation tree op, the
nsIContent* that points to the node gets written to the memory location pointed to by the
nsIContent**. For any given content handle, the node creation tree op is always the first tree op in queue that uses that handle, so subsequent non-creation tree ops can safely dereference the handle to obtain a real node. Nodes created by tree ops are owned by the parser for the lifetime of the parser, so for refcounting purposes, the parser owns each
nsIContent object it creates by one reference no matter how many copies of the content handle for the node exist inside the parser. (This indeed means that removing parser-created nodes from the DOM during parsing doesn't release memory until the parser stops parsing, which is, in theory, a problem for long polling using HTML in an iframe e.g. for a chat app.)
Some tree ops hold
PRUnichar arrays. Those arrays are allocated when creating the tree op and
deleted by the destructor of
nsHtml5TreeOperation. Hence, data gets copied to and from these arrays.
When the executor flushing runnable fires on the main thread, it calls
nsHtml5TreeOpExecutor::RunFlushLoop(). This method returns immediately if another invocation of it is already on the call stack (nested event loop case). The method then enters a loop that has a bunch of return conditions (including parser termination).
The loop first flushes speculative loads (creation discussed later). If the executor is reading from a stage (i.e. the ops are coming from the parser thread), the executor moves the tree ops from the staging queue into its own queue. (Again, here we get to move a bunch of tree ops by obtaining a mutex once instead of having to synchronize thread on a per-tree op basis.) If the executor isn't reading from a stage, it calls
nsHtml5Parser::ParseUntilBlocked() to parse potential
document.write()-generated data into tree ops.
The outer loop then has an inner loop that iterates over the tree ops in the executor's queue and calls Perform on each one. Parser termination is checked before each tree op for an early return, because, unfortunately, Gecko expects parsers to be able to terminate immediately. After each tree op except the last one in the queue, the clock time is checked to see if
RunFlushLoop() has spent too much time without returning to the event loop. If too much time has been spent, a runnable for calling
RunFlushLoop() again is dispatched and an early return made before all tree ops have been executed. (Only the already executed ops are destructed and the rest are left in the queue.)
The last op in the queue may be an op for attempting to execute a script that may block the parser (ops for attempting to execute 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 drive the tokenizer/tree builder pairs guarantee to flush tree ops immediately if a script execution tree op is generated. (The tree builder makes the tokenizer return immediately when such an op is generated.) Thus, a tree op that may cause the parser to block can only occur as the last op in a queue that
When the parser thread sees that it has generated a tree op that attempts to execute a (non-async, non-defer) script, it starts speculating. It acquires
mSpeculationMutex and while holding it, it creates a new speculation and adds it to the queue of speculations, flushes the tree ops to the main thread, marks the
nsHtml5StreamParser as being in a speculating state and sets the newly created speculation object as the tree op sink (instead of the tree op stage described earlier) of the tree builder. The speculation object has a queue of tree ops (into which the tree builder will now flush ops to instead of the tree op stage), an owning reference to the
nsHtml5OwningUTF16Buffer that contains the starting point of the speculation, an index into the
nsHtml5OwningUTF16Buffer defining the exact starting point within the buffer, the line number of the tokenizer at that point and a snapshot of the tree op state. The line number and the snapshot are also added to the tree op that attempts to execute scripts (before flushing it).
The tree builder snapshot contains a copy of the tree builder stack, a copy of the list of open formatting elements and copies of various fields that define the tree builder state. It contains all the information that is necessary to load back into the tree builder to restore it into a behaviorally equivalent state.
The flush timer is disengaged, because it's not useful to make the tree builder flush ops into the queue of the speculation incrementally.
After the speculation has been started and
mSpeculationMutex released, the parser thread will parse incoming data and the tree builder will produce tree ops so that they get flushed into the queue in the speculation object.
If another tree op that attempts to execute a script is generated while speculating, another speculation object is initialized as described above and placed in the queue of speculation objects after the previous one.
It is possible that the parser thread ends up parsing all remaining data into speculations before the main thread is ready to receive more tree ops.
On the main thread, when the tree op executor executes a tree op that attempts to execute a script, the tree op is first checked for a tree builder state snapshot. There will be a snapshot if the tree op came from the parser thread. There won't be one if the tree op came from
document.write() on the main thread (discussed later). If there is a snapshot, the tokenizer used for parsing
document.write()-originating data on the main thread is reset to the data state. There's no need to snapshot the tokenizer state, because the state of the tokenizer is always the same immediately after the tokenizer has emitted a script end tag. Then the tree builder that is used for parsing
document.write()-originating data is initialized from the state snapshot. Now the tokenizer/tree builder pair used for parsing
document.write() data is in the same state that the off-the-main-thread tokenizer/tree builder pair was immediately after processing the script end tag.
The tree op executor then attempts to execute the script. This operation either executes an inline script right away or tells the parser to block (for external scripts). If the parser is told to block, the script loader will unblock the parser before the external script executes. If the script was executed without blocking, the executor dispatches an event to reflush itself. (Remember that reflushing ends up calling
nsHtml5Parser::ParseUntilBlocked(). That method is responsible for moving back to consuming tree ops from the parser thread via the staging area.)
document.write() push data to the tokenizer/tree builder pair that exists on the main thread solely for parsing data from
document.write(). If the parser isn't blocked,
document.write() parses input into tree ops synchronously and flushes the tree ops synchronously by calling
nsHtml5TreeOpExecutor::FlushDocumentWrite() does not sample the clock to return early.
Inline scripts that arrive from
document.write() are executed synchronously (if the parser isn't already blocked). External scripts arriving from
document.write() block the parser.
If there is data in
document.write() input after a an external script (or any data at all if a previous
document.write() call has contained an external script and blocked the parser), the data is left in a linked list of
nsHtml5OwningUTF16Buffer objects. (How exactly data is inserted into the buffer list depends on parser keys when
document.write() is invoked re-entrantly, but that's outside the scope of this document, since this document is about parser threading.)
Whenever the argument of
document.write() isn't tokenized to completion synchronously, the part left unprocessed by the main
document.write() tokenizer/tree builder is processed by the third tokenizer/tree builder pair. The tree ops from that processing are ignored and only speculative loads are used. (Speculative loads are discussed later.) The third tokenizer/tree builder pair is initialized from the state of the main
document.write() tokenizer/tree builder pair but can get into an inconsistent state if
document.write() is invoked re-entrantly. This is OK, because the tree ops aren't used and it's mostly harmless if the speculative loads are wrong.
After an external script finishes executing, it dispatches an event to reflush the tree op executor. The reflush causes a call to
ParseUntilBlocked() parses data left by
document.write() in the linked list of buffers, because the parser was blocked. This might cause more script execution tree ops to be generated and executed and
document.write() to be called more times.
ParseUntilBlocked() exhausts the data available to it, it calls
nsHtml5StreamParser::ContinueAfterScripts to resume the consumption of data from the network.
nsHtml5StreamParser::ContinueAfterScripts runs on the main thread. It acquires
mSpeculationMutex in order to be able to touch the queue of speculations. The mutex acquisition only blocks if the parser thread happens to be setting up a new speculation object at the same moment.
The first speculation in the speculation queue is examined. If the last character seen by the
document.write() tokenizer was not a carriage return, if the
document.write() tokenizer is in the "data" state and if the tree builder state snapshot on the speculation matches the state of the
document.write() tree builder, the speculation has succeeded. Otherwise it has failed.
If there is more than one speculation in the queue and if the speculation is successful, we can dequeue the first speculation while holding
mSpeculationMutex without bothering the parser thread. In this case, the tree ops from the speculation are flushed into the tree op executor and
ContinueAfterScripts() returns early. (
nsHtml5TreeOpExecutor::RunFlushLoop is on the call stack already in this case and will loop around to start flushing the ops right away.)
If there's only one speculation or the speculation failed, it's necessary to bother the parser thread. In that case, the main thread raises an interruption flag on the
nsHtml5StreamParser object to make the parser thread release
mTokenizerMutex earlier. The main thread then attempts to acquire
If the single speculation is successful, the tree ops from the parser-thread tree builder are flushed straight to the tree op executor and the tree op stage is set as the tree op sink for the tree builder. The executor is told that it's reading from the stage again.
If the speculation failed, the first buffer corresponding to the starting point of the speculation gets its start index restored to the index stored on the speculation object. Subsequent buffers get their start index reset back to zero. The tokenizer gets its line number restored from the speculation object. This is equivalent to rewinding the input to where it was when speculation started.
All the speculations in the speculation queue are destroyed. Pending tree ops in the tree builder are cleared.
The tree op stage is set as the tree op sink for the tree builder. The executor is told that it's reading from the stage again.
The state of the main-thread tokenizer is copied to the parser-thread tokenizer. Likewise for the tree builders. The "last was carriage return" flag is copied over also.
A runnable is dispatched to the parser thread to call to mark the parser uninterrupted and to call
nsHtml5StreamParser::ParseAvailableData() on the parser thread.
mTokenizerMutex is released.
When the tree builder on the parser thread encounters HTML
video (with a poster frame),
img or SVG
image elements, preload operations are appended to a speculative load queue. There speculative load operations are flushed to the main thread (via the staging area) whenever tree ops are flushed and also whenever
nsHtml5StreamParser::ParseAvailableData() is about to stop working. That is, when the parser thread is parsing speculatively, speculative loads continue to be flushed to the main thread even though tree ops accumulate into the speculations.
On the main thread, the speculative tokenizer/tree builder pair used for parsing
document.write() input that didn't get parsed by the main
document.write() tokenizer/tree builder synchronously also sends speculative loads to the tree op executor.
The executor acts on the speculative load queue when the runnable dispatched by
nsHtml5StreamParser::ParseAvailableData() fires and right before executing tree ops whenever tree ops are executed.
When the executor acts on speculative loads, it starts speculative HTTP fetches for images (including video poster frames), style sheets and scripts.
Additionally, the speculative load queue is used for transferring information from the parser thread to the main thread when the information needs to arrive before starting any speculative loads and when the information is known not to be speculative. There are two such pieces of information: the manifest URL for an App Cache manifest and the character encoding for the document.