Subzero: Use CFG-local arena allocation for relevant containers.

ALLOCATION.rst

Index: ALLOCATION.rst
diff --git a/ALLOCATION.rst b/ALLOCATION.rst
new file mode 100644
index 0000000000000000000000000000000000000000..d5b5d495358c4e0f5c4f84be53037b8662ee4007
--- /dev/null
+++ b/ALLOCATION.rst
@@ -0,0 +1,126 @@
+Object allocation and lifetime in ICE
+=====================================
+
+This document discusses object lifetime and scoping issues, starting with
+bitcode parsing and ending with ELF file emission.
+
+Multithreaded translation model
+-------------------------------
+
+A single thread is responsible for parsing PNaCl bitcode (possibly concurrently
+with downloading the bitcode file) and constructing the initial high-level ICE.
+The result is a queue of Cfg pointers.  The parser thread incrementally adds a
+Cfg pointer to the queue after the Cfg is created, and then moves on to parse
+the next function.
+
+Multiple translation worker threads draw from the queue of Cfg pointers as they
+are added to the queue, such that several functions can be translated in parallel.
+The result is a queue of assembler buffers, each of which consists of machine code
+plus fixups.
+
+A single thread is responsible for writing the assembler buffers to an ELF file.
+It consumes the assembler buffers from the queue that the translation threads
+write to.
+
+This means that Cfgs are created by the parser thread and destroyed by the
+translation thread (including Cfg nodes, instructions, and most kinds of
+operands), and assembler buffers are created by the translation thread and
+destroyed by the writer thread.
+
+Deterministic execution
+^^^^^^^^^^^^^^^^^^^^^^^
+
+Although code randomization is a key aspect of security, deterministic and
+repeatable translation is sometimes needed, e.g. for regression testing.
+Multithreaded translation introduces potential for randomness that may need to
+be made deterministic.
+
+* Bitcode parsing is sequential, so it's easy to use a FIFO queue to keep the
+  translation queue in deterministic order.  But since translation is
+  multithreaded, FIFO order for the assembler buffer queue may not be
+  deterministic.  The writer thread would be responsible for reordering the
+  buffers, potentially waiting for slower translations to complete even if other
+  assembler buffers are available.
+
+* Different translation threads may add new constant pool entries at different
+  times.  Some constant pool entries are emitted as read-only data.  This
+  includes floating-point constants for x86, as well as integer immediate
+  randomization through constant pooling.  These constant pool entries are
+  emitted after all assembler buffers have been written.  The writer needs to be
+  able to sort them deterministically before emitting them.
+
+Object lifetimes
+----------------
+
+Objects of type Constant, or a subclass of Constant, are pooled globally.  The
+pooling is managed by the GlobalContext class.  Since Constants are added or
+lookup up by translation threads and the parser thread, access to the constant

[jvoung (off chromium), 2014/12/19 17:42:23]

"lookup up by" -> "looked up by" ?

[Jim Stichnoth, 2014/12/19 20:51:25]

Done.

+pools, as well as GlobalContext in general, need to be arbitrated by locks.
+(It's possible that if there's too much contention, we can maintain a
+thread-local cache for Constant pool lookups.)  Constants live across all
+function translations, and are destroyed only at the end.
+
+Several object types are scoped within the lifetime of the Cfg.  These include
+CfgNode, Inst, Variable, and any target-specific subclasses of Inst and Operand.
+When the Cfg is destroyed, these scoped objects are destroyed as well.  To keep
+this cheap, the Cfg includes a slab allocator from which these objects are
+allocated, and the objects should not contain fields with non-trivial
+destructors.  Most of these fields are POD, but in a couple of cases these
+fields are STL containers.  We deal with this, and avoid leaking memory, by
+providing the container with an allocator that uses the Cfg-local slab
+allocator.  Since the container allocator generally needs to be stateless, we
+store a pointer to the slab allocator in thread-local storage (TLS).  This is
+straightforward since on any of the threads, only one Cfg is active at a time,
+and a given Cfg is only active in one thread at a time (either the parser
+thread, or at most one translation thread, or the writer thread).
+
+Even though there is a one-to-one correspondence between Cfgs and assembler
+buffers, they need to use different allocators.  This is because the translation
+thread wants to destroy the Cfg and reclaim all its memory after translation
+completes, but possibly before the assembly buffer is written to the ELF file.
+Ownership of the assembler buffer and its allocator are transferred to the
+writer thread after translation completes, similar to the way ownership of the
+Cfg and its allocator are transferred to the translation thread after parsing
+completes.
+
+Allocators and TLS
+------------------
+
+Part of the Cfg building, and transformations on the Cfg, include STL container
+operations which may need to allocate additional memory in a stateless fashion.
+This requires maintaining the proper slab allocator pointer in TLS.
+
+When the parser thread creates a new Cfg object, it puts a pointer to the Cfg's
+slab allocator into its own TLS.  This is used as the Cfg is built within the
+parser thread.  After the Cfg is built, the parser thread clears its allocator
+pointer, adds the new Cfg pointer to the translation queue, continues with the
+next function.
+
+When the translation thread grabs a new Cfg pointer, it installs the Cfg's slab
+allocator into its TLS and translates the function.  When generating the
+assembly buffer, it must take care not to use the Cfg's slab allocator.  If
+there is a slab allocator for the assembler buffer, a pointer to it can also be

[jvoung (off chromium), 2014/12/19 17:42:23]

re: "If there is a slab allocator for the assembler buffer...", there is a slab
allocator for the assembler buffer? I guess currently a pointer to it isn't
installed in TLS, but can be if needed. Then that would need the same care when
transferring ownership between one of the translation threads and the writer
thread.

[Jim Stichnoth, 2014/12/19 20:51:25]

Right, I think that's where we'll need to go when we rearrange things to
implement parallel translation.

+installed in TLS if needed.
+
+The translation thread destroys the Cfg when it is done translating, including
+the Cfg's slab allocator, and clears the allocator pointer from its TLS.
+Likewise, the writer thread destroys the assembler buffer when it is finished
+with it.
+
+Thread safety
+-------------
+
+The parse/translate/write stages of the translation pipeline are fairly
+independent, with little opportunity for threads to interfere.  The Subzero
+design calls for all shared accesses to go through the GlobalContext, which adds
+locking as appropriate.  This includes the coarse-grain work queues for Cfgs and
+assembler buffers.  It also includes finer-grain access to constant pool
+entries, as well as output streams for verbose debugging output.
+
+If locked access to constant pools becomes a bottleneck, we can investigate
+thread-local caches of constants (as mentioned earlier).  Also, it should be
+safe though slightly less efficient to allow duplicate copies of constants
+across threads (which could be de-dupped by the writer at the end).
+
+We will use ThreadSanitizer as a way to detect potential data races in the
+implementation.