<div dir="ltr">This proposal seems overall legit. It's trickier than the current implementation, but not that much. As long as it is described how it works in the README, it should be fine.<div><br></div><div>This is a divergence from the original design and widen the gap between COFF and ELF. I'd like to keep them consistent as possible so that one can easily understand the COFF linker using the knowledge of the ELF linker (and vice versa.) So we probably want to do the same thing if the experiment is successful.</div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Apr 27, 2016 at 11:49 AM, Peter Collingbourne <span dir="ltr"><<a href="mailto:peter@pcc.me.uk" target="_blank">peter@pcc.me.uk</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Hi all,</div><div><br></div><div>This proposes a redesign of LLD’s symbol table in order to improve memory locality by minimizing indirection when resolving relocations. The key idea is that we perform symbol resolution by overwriting SymbolBodies, rather than by updating pointers. This is based on some ideas mentioned by Rafael on IRC.<br></div><div><br></div><div>Conceptually, we split Symbol into a non-polymorphic part and a polymorphic part (a SymbolBody). The non-polymorphic part contains the flags that are currently stored in Symbol, while the polymorphic part would be a derived class of SymbolBody stored directly in the Symbol object without a level of indirection. The class definitions would roughly look like this:</div><div><br></div><div>struct Symbol {</div><div>  uint8_t Binding;</div><div>  unsigned Visibility : 2;</div><div>  // ...</div><div>  char Body[Max]; // Max is the maximum size of a SymbolBody</div><div>  SymbolBody *body() { return reinterpret_cast<SymbolBody *>(Body); }</div><div>};</div><div><br></div><div>class SymbolBody {</div><div>  const unsigned SymbolKind : 8;</div><div>  // …</div><div><br></div><div>  Symbol &symbol() {</div><div>    return *reinterpret_cast<Symbol *>(reinterpret_cast<char *>(this) - offsetof(Symbol, Body));</div><div>  }</div><div>};</div><div><br></div><div>class Defined : public SymbolBody {</div><div> ... </div><div>};</div><div><br></div><div>As we load symbols from input files, the input file calls methods on the symbol table that add symbols of specific types. These methods would look up the symbol name and make a decision about whether to replace the existing symbol. This would be similar to the decision currently being made by SymbolBody::compare, but it would be made directly using symbol information, without needing to create a SymbolBody for the symbol. If we decide to replace the symbol, we placement-new a SymbolBody for the symbol into Symbol::Body.</div><div><br></div><div>A sketch of how the symbol table might implement adding an undefined symbol:</div><div><br></div><div>Symbol *SymbolTable<ELFT>::addUndefined(StringRef Name, uint8_t Binding, …) {</div><div>  std::pair<Symbol *, bool> P = insert(Name);</div><div>  if (!P.second) { // symbol already in symbol table</div><div>    if (auto *L = dyn_cast<Lazy>(P.first->body()))</div><div>      addFile(L);</div><div>    return P.first;</div><div>  }</div><div>  // symbol previously unseen</div><div>  new (P.first->Body) Undefined(Name, Binding, ...);</div><div>  return P.first;</div><div>}</div><div><br></div><div>Input files would have an associated symbol list for use in resolving relocations. This symbol list would be a std::vector<Symbol *>. Symbols retrieved from the symbol table are added to the symbol list. Relocations would be resolved by following two fewer levels of indirection, from the vector to the Symbol, rather than the current vector -> SymbolBody -> Symbol -> SymbolBody.</div><div><br></div><div>This design has a disadvantage over the current design: input file loading would no longer be thread safe. However, input file loading is already a highly serialized process since the set of files we need to parse is unknown until we have examined all input files, so I think that doesn’t matter.</div><div><br></div><div>Next steps: I intend to implement a prototype of this idea and get benchmark numbers. If the numbers look good, I'll send out a patch.</div><div><br></div><div>Thanks,</div><span class="HOEnZb"><font color="#888888">-- <br><div><div dir="ltr">-- <div>Peter</div></div></div>
</font></span></div>
</blockquote></div><br></div></div>