ALLOCATION.rst

   1 Object allocation and lifetime in ICE
   2 =====================================
   3
   4 This document discusses object lifetime and scoping issues, starting with
   5 bitcode parsing and ending with ELF file emission.
   6
   7 Multithreaded translation model
   8 -------------------------------
   9
  10 A single thread is responsible for parsing PNaCl bitcode (possibly concurrently
  11 with downloading the bitcode file) and constructing the initial high-level ICE.
  12 The result is a queue of Cfg pointers.  The parser thread incrementally adds a
  13 Cfg pointer to the queue after the Cfg is created, and then moves on to parse
  14 the next function.
  15
  16 Multiple translation worker threads draw from the queue of Cfg pointers as they
  17 are added to the queue, such that several functions can be translated in parallel.
  18 The result is a queue of assembler buffers, each of which consists of machine code
  19 plus fixups.
  20
  21 A single thread is responsible for writing the assembler buffers to an ELF file.
  22 It consumes the assembler buffers from the queue that the translation threads
  23 write to.
  24
  25 This means that Cfgs are created by the parser thread and destroyed by the
  26 translation thread (including Cfg nodes, instructions, and most kinds of
  27 operands), and assembler buffers are created by the translation thread and
  28 destroyed by the writer thread.
  29
  30 Deterministic execution
  31 ^^^^^^^^^^^^^^^^^^^^^^^
  32
  33 Although code randomization is a key aspect of security, deterministic and
  34 repeatable translation is sometimes needed, e.g. for regression testing.
  35 Multithreaded translation introduces potential for randomness that may need to
  36 be made deterministic.
  37
  38 * Bitcode parsing is sequential, so it's easy to use a FIFO queue to keep the
  39   translation queue in deterministic order.  But since translation is
  40   multithreaded, FIFO order for the assembler buffer queue may not be
  41   deterministic.  The writer thread would be responsible for reordering the
  42   buffers, potentially waiting for slower translations to complete even if other
  43   assembler buffers are available.
  44
  45 * Different translation threads may add new constant pool entries at different
  46   times.  Some constant pool entries are emitted as read-only data.  This
  47   includes floating-point constants for x86, as well as integer immediate
  48   randomization through constant pooling.  These constant pool entries are
  49   emitted after all assembler buffers have been written.  The writer needs to be
  50   able to sort them deterministically before emitting them.
  51
  52 Object lifetimes
  53 ----------------
  54
  55 Objects of type Constant, or a subclass of Constant, are pooled globally.  The
  56 pooling is managed by the GlobalContext class.  Since Constants are added or
  57 looked up by translation threads and the parser thread, access to the constant
  58 pools, as well as GlobalContext in general, need to be arbitrated by locks.
  59 (It's possible that if there's too much contention, we can maintain a
  60 thread-local cache for Constant pool lookups.)  Constants live across all
  61 function translations, and are destroyed only at the end.
  62
  63 Several object types are scoped within the lifetime of the Cfg.  These include
  64 CfgNode, Inst, Variable, and any target-specific subclasses of Inst and Operand.
  65 When the Cfg is destroyed, these scoped objects are destroyed as well.  To keep
  66 this cheap, the Cfg includes a slab allocator from which these objects are
  67 allocated, and the objects should not contain fields with non-trivial
  68 destructors.  Most of these fields are POD, but in a couple of cases these
  69 fields are STL containers.  We deal with this, and avoid leaking memory, by
  70 providing the container with an allocator that uses the Cfg-local slab
  71 allocator.  Since the container allocator generally needs to be stateless, we
  72 store a pointer to the slab allocator in thread-local storage (TLS).  This is
  73 straightforward since on any of the threads, only one Cfg is active at a time,
  74 and a given Cfg is only active in one thread at a time (either the parser
  75 thread, or at most one translation thread, or the writer thread).
  76
  77 Even though there is a one-to-one correspondence between Cfgs and assembler
  78 buffers, they need to use different allocators.  This is because the translation
  79 thread wants to destroy the Cfg and reclaim all its memory after translation
  80 completes, but possibly before the assembly buffer is written to the ELF file.
  81 Ownership of the assembler buffer and its allocator are transferred to the
  82 writer thread after translation completes, similar to the way ownership of the
  83 Cfg and its allocator are transferred to the translation thread after parsing
  84 completes.
  85
  86 Allocators and TLS
  87 ------------------
  88
  89 Part of the Cfg building, and transformations on the Cfg, include STL container
  90 operations which may need to allocate additional memory in a stateless fashion.
  91 This requires maintaining the proper slab allocator pointer in TLS.
  92
  93 When the parser thread creates a new Cfg object, it puts a pointer to the Cfg's
  94 slab allocator into its own TLS.  This is used as the Cfg is built within the
  95 parser thread.  After the Cfg is built, the parser thread clears its allocator
  96 pointer, adds the new Cfg pointer to the translation queue, continues with the
  97 next function.
  98
  99 When the translation thread grabs a new Cfg pointer, it installs the Cfg's slab
 100 allocator into its TLS and translates the function.  When generating the
 101 assembly buffer, it must take care not to use the Cfg's slab allocator.  If
 102 there is a slab allocator for the assembler buffer, a pointer to it can also be
 103 installed in TLS if needed.
 104
 105 The translation thread destroys the Cfg when it is done translating, including
 106 the Cfg's slab allocator, and clears the allocator pointer from its TLS.
 107 Likewise, the writer thread destroys the assembler buffer when it is finished
 108 with it.
 109
 110 Thread safety
 111 -------------
 112
 113 The parse/translate/write stages of the translation pipeline are fairly
 114 independent, with little opportunity for threads to interfere.  The Subzero
 115 design calls for all shared accesses to go through the GlobalContext, which adds
 116 locking as appropriate.  This includes the coarse-grain work queues for Cfgs and
 117 assembler buffers.  It also includes finer-grain access to constant pool
 118 entries, as well as output streams for verbose debugging output.
 119
 120 If locked access to constant pools becomes a bottleneck, we can investigate
 121 thread-local caches of constants (as mentioned earlier).  Also, it should be
 122 safe though slightly less efficient to allow duplicate copies of constants
 123 across threads (which could be de-dupped by the writer at the end).
 124
 125 We will use ThreadSanitizer as a way to detect potential data races in the
 126 implementation.