Cache getSymVA

[• espindola]

Summary

It is common for getSymVA to be called at least twice for each symbol. Once for the symbol table, once for a relocation using it.

The operation is fairly expensive, so it is probably worth caching it (I will attach the benchmark results).

One issue with this is that with thunks getVA is called multiple times and produces different results as thunks are added. It is easy to just disable this for architectures that need thunks, but I am curious if someone more familiar with thunks thinks we can do better.

BTW, we should probably add testcase with thunks to the benchmarks we use. Peter, do you have a chromium build for aarch64 we could use?

[pcc]

BTW, we should probably add testcase with thunks to the benchmarks we use. Peter, do you have a chromium build for aarch64 we could use?

The AArch64 version of chromium isn't large enough to need thunks. The ARM32 version has plenty of thunks, though.

For a build you should be able to follow the instructions here:
https://chromium.googlesource.com/chromium/src/+/master/docs/android_build_instructions.md
If you use the GN flags target_os="android" is_official_build=true and build the target libmonochrome.so that should give you something reasonably close to what we ship.

If that's too much trouble I can try to create a build myself but it will take a while.

[peter.smith]

As well as Thunks and errata patching, I'm guessing that any future generic (not just Android) uses of packed dynamic relocs might also need symbol addresses to be recalculated (https://sourceware.org/ml/gnu-gabi/2017-q2/msg00000.html)

Some thoughts:

• Rather than disabling for the architectures that need thunks, I think it would be better to invalidate the cache after content was changed as this might help prevent bugs if other features are added later that change addresses.
• Adding new content can only change the address of defined non-absolute symbols, it might be possible to cache everything else but these ones. Whether this makes a significant difference in link time or not I don't know.
• assignAddresses() could update the symbol cache instead of invalidating it, there would only be a displacement for defined non-absolute symbols.

I guess we'll need to benchmark to make sure if any of those are worth the additional complexity.

ELF/Symbols.h

public:
   uint32_t GlobalDynIndex = -1;
 
 protected:
   Symbol(Kind K, InputFile *File, StringRefZ Name, uint8_t Binding,
          uint8_t StOther, uint8_t Type)
       : Binding(Binding), File(File), SymbolKind(K), NeedsPltAddr(false),
         IsInGlobalMipsGot(false), Is32BitMipsGot(false), IsInIplt(false),
         IsInIgot(false), IsPreemptible(false), Used(!Config->GcSections),
-        Type(Type), StOther(StOther), Name(Name) {}
+        CachedVA(false), Type(Type), StOther(StOther), Name(Name) {}
 
   const unsigned SymbolKind : 8;
 
 public:
   // True the symbol should point to its PLT entry.
   // For SharedSymbol only.
   unsigned NeedsPltAddr : 1;
   // True if this symbol has an entry in the global part of MIPS GOT.
public:
   unsigned IsInIgot : 1;
 
   // True if this symbol is preemptible at load time.
   unsigned IsPreemptible : 1;
 
   // True if an undefined or shared symbol is used from a live section.
   unsigned Used : 1;
 
+  unsigned CachedVA : 1;
+
   // The following fields have the same meaning as the ELF symbol attributes.
   uint8_t Type;    // symbol type
   uint8_t StOther; // st_other field value
 
   // The Type field may also have this value. It means that we have not yet seen
   // a non-Lazy symbol with this name, so we don't know what its type is. The
   // Type field is normally set to this value for Lazy symbols unless we saw a
   // weak undefined symbol first, in which case we need to remember the original

ELF/Symbols.cpp

 Defined *ElfSym::Edata2;
 Defined *ElfSym::End1;
 Defined *ElfSym::End2;
 Defined *ElfSym::GlobalOffsetTable;
 Defined *ElfSym::MipsGp;
 Defined *ElfSym::MipsGpDisp;
 Defined *ElfSym::MipsLocalGp;
 
-static uint64_t getSymVA(const Symbol &Sym, int64_t &Addend) {
+static uint64_t getSymVA(const Symbol &Sym) {
   switch (Sym.kind()) {
   case Symbol::DefinedKind: {
     auto &D = cast<Defined>(Sym);
     SectionBase *IS = D.Section;
 
     // According to the ELF spec reference to a local symbol from outside
     // the group are not allowed. Unfortunately .eh_frame breaks that rule
     // and must be treated specially. For now we just replace the symbol with
     // 0.
     if (IS == &InputSection::Discarded)
       return 0;
 
     // This is an absolute symbol.
     if (!IS)
       return D.Value;
 
-    uint64_t Offset = D.Value;
-
-    // An object in an SHF_MERGE section might be referenced via a
-    // section symbol (as a hack for reducing the number of local
-    // symbols).
-    // Depending on the addend, the reference via a section symbol
-    // refers to a different object in the merge section.
-    // Since the objects in the merge section are not necessarily
-    // contiguous in the output, the addend can thus affect the final
-    // VA in a non-linear way.
-    // To make this work, we incorporate the addend into the section
-    // offset (and zero out the addend for later processing) so that
-    // we find the right object in the section.
-    if (D.isSection()) {
-      Offset += Addend;
-      Addend = 0;
-    }
-
     // In the typical case, this is actually very simple and boils
     // down to adding together 3 numbers:
     // 1. The address of the output section.
     // 2. The offset of the input section within the output section.
     // 3. The offset within the input section (this addition happens
     //    inside InputSection::getOffset).
     //
     // If you understand the data structures involved with this next
     // line (and how they get built), then you have a pretty good
     // understanding of the linker.
-    uint64_t VA = IS->getVA(Offset);
+    uint64_t VA = IS->getVA(D.Value);
 
     if (D.isTls() && !Config->Relocatable) {
       if (!Out::TlsPhdr)
         fatal(toString(D.File) +
               " has an STT_TLS symbol but doesn't have an SHF_TLS section");
       return VA - Out::TlsPhdr->p_vaddr;
     }
     return VA;
static uint64_t getSymVA(const Symbol &Sym) {
   case Symbol::LazyObjectKind:
     assert(Sym.IsUsedInRegularObj && "lazy symbol reached writer");
     return 0;
   }
   llvm_unreachable("invalid symbol kind");
 }
 
 uint64_t Symbol::getVA(int64_t Addend) const {
-  uint64_t OutVA = getSymVA(*this, Addend);
+  if (CachedVA)
+    return cast<Defined>(this)->Value + Addend;
+
+  // An object in an SHF_MERGE section might be referenced via a
+  // section symbol (as a hack for reducing the number of local
+  // symbols).
+  // Depending on the addend, the reference via a section symbol
+  // refers to a different object in the merge section.
+  // Since the objects in the merge section are not necessarily
+  // contiguous in the output, the addend can thus affect the final
+  // VA in a non-linear way.
+  // To make this work, we incorporate the addend into the section
+  // offset (and zero out the addend for later processing) so that
+  // we find the right object in the section.
+  if (isSection()) {
+    if (auto *Sec = dyn_cast<MergeInputSection>(cast<Defined>(this)->Section)) {
+      if (SyntheticSection *SS = Sec->getParent())
+        return SS->getParent()->Addr + SS->OutSecOff + Sec->getOffset(Addend);
+      return Sec->getOffset(Addend);
+    }
+  }
+
+  uint64_t OutVA = getSymVA(*this);
+  if (auto *D = dyn_cast<Defined>(this)) {
+    const_cast<Defined*>(D)->Value = OutVA;
+    const_cast<Defined *>(D)->CachedVA = true;
+  }
   return OutVA + Addend;
 }
 
 uint64_t Symbol::getGotVA() const { return InX::Got->getVA() + getGotOffset(); }
 
 uint64_t Symbol::getGotOffset() const {
   return GotIndex * Target->GotEntrySize;
 }