[ELF] Complete implementation of -fix-cortex-a53-843419linaro-local/peter.smith/errata-section

This patch provides the mechanism to fix instances of the instruction
sequence that may trigger the cortex-a53 843419 erratum. The fix is
provided by an alternative instruction sequence to remove one of the
erratum conditions. To reach this alternative instruction sequence we
replace the original instruction with a branch to the alternative
sequence. The alternative sequence is responsible for branching back to
the original.

As there is only erratum to fix the implementation is specific to
AArch64 and the specific erratum conditions. It should be generalizable
to other targets and erratum if needed.

Differential Revision: https://reviews.llvm.org/D36749

3 files changed, 223 insertions, 67 deletions

diff --git a/ELF/SectionPatcher.cpp b/ELF/SectionPatcher.cpp
index 4782e6713..ba80a55b5 100644
--- a/ELF/SectionPatcher.cpp
+++ b/ELF/SectionPatcher.cpp
@@ -46,9 +46,6 @@ using namespace lld::elf;
 // - We can place the replacement sequence within range of the branch.
 
 // FIXME:
-// - At this stage the implementation only supports detection and not fixing,
-// this is sufficient to test the decode and recognition of the erratum
-// sequence.
 // - The implementation here only supports one patch, the AArch64 Cortex-53
 // errata 843419 that affects r0p0, r0p1, r0p2 and r0p4 versions of the core.
 // To keep the initial version simple there is no support for multiple
@@ -338,13 +335,6 @@ static bool is843419ErratumSequence(uint32_t Adrp, uint32_t Instr2,
          A64::isLoadStoreRegisterUnsigned(Instr4) && A64::getRn(Instr4) == Rn;
 }
 
-static void report843419Fix(uint64_t AdrpAddr) {
-  if (!Config->Verbose)
-    return;
-  message("detected cortex-a53-843419 erratum sequence starting at " +
-          utohexstr(AdrpAddr) + " in unpatched output.");
-}
-
 // Scan the instruction sequence starting at Offset Off from the base of
 // InputSection IS. We update Off in this function rather than in the caller as
 // we can skip ahead much further into the section when we know how many
@@ -392,16 +382,66 @@ static uint64_t scanCortexA53Errata843419(InputSection *IS, uint64_t &Off,
   return PatchOff;
 }
 
-// The AArch64 ABI permits data in executable sections. We must avoid scanning
-// this data as if it were instructions to avoid false matches.
-// The ABI Section 4.5.4 Mapping symbols; defines local symbols that describe
-// half open intervals [Symbol Value, Next Symbol Value) of code and data
-// within sections. If there is no next symbol then the half open interval is
-// [Symbol Value, End of section). The type, code or data, is determined by the
-// mapping symbol name, $x for code, $d for data.
-std::map<InputSection *,
-         std::vector<const DefinedRegular *>> static makeAArch64SectionMap() {
-  std::map<InputSection *, std::vector<const DefinedRegular *>> SectionMap;
+class lld::elf::Patch843419Section : public SyntheticSection {
+public:
+  Patch843419Section(InputSection *P, uint64_t Off);
+
+  void writeTo(uint8_t *Buf) override;
+
+  size_t getSize() const override { return 8; }
+
+  uint64_t getLDSTAddr() const;
+
+  // The Section we are patching.
+  const InputSection *Patchee;
+  // The offset of the instruction in the Patchee section we are patching.
+  uint64_t PatcheeOffset;
+  // A label for the start of the Patch that we can use as a relocation target.
+  SymbolBody *PatchSym;
+};
+
+lld::elf::Patch843419Section::Patch843419Section(InputSection *P, uint64_t Off)
+    : SyntheticSection(SHF_ALLOC | SHF_EXECINSTR, SHT_PROGBITS, 4,
+                       ".text.patch"),
+      Patchee(P), PatcheeOffset(Off) {
+  this->Parent = P->getParent();
+  PatchSym = addSyntheticLocal(
+      Saver.save("__CortexA53843419_" + utohexstr(getLDSTAddr())), STT_FUNC, 0,
+      getSize(), this);
+  addSyntheticLocal(Saver.save("$x"), STT_NOTYPE, 0, 0, this);
+}
+
+uint64_t lld::elf::Patch843419Section::getLDSTAddr() const {
+  return Patchee->getParent()->Addr + Patchee->OutSecOff + PatcheeOffset;
+}
+
+void lld::elf::Patch843419Section::writeTo(uint8_t *Buf) {
+  // Copy the instruction that we will be replacing with a branch in the
+  // Patchee Section.
+  write32le(Buf, read32le(Patchee->Data.begin() + PatcheeOffset));
+
+  // Apply any relocation transferred from the original PatcheeSection.
+  // For a SyntheticSection Buf already has OutSecOff added, but relocateAlloc
+  // also adds OutSecOff so we need to subtract to avoid double counting.
+  this->relocateAlloc(Buf - OutSecOff, Buf - OutSecOff + getSize());
+
+  // Return address is the next instruction after the one we have just copied.
+  uint64_t S = getLDSTAddr() + 4;
+  uint64_t P = PatchSym->getVA() + 4;
+  Target->relocateOne(Buf + 4, R_AARCH64_JUMP26, S - P);
+}
+
+SectionPatcher::SectionPatcher() {
+  // The AArch64 ABI permits data in executable sections. We must avoid scanning
+  // this data as if it were instructions to avoid false matches. We use the
+  // mapping symbols in the InputObjects to identify this data, caching the
+  // results in SectionMap so we don't have to recalculate it each pass.
+
+  // The ABI Section 4.5.4 Mapping symbols; defines local symbols that describe
+  // half open intervals [Symbol Value, Next Symbol Value) of code and data
+  // within sections. If there is no next symbol then the half open interval is
+  // [Symbol Value, End of section). The type, code or data, is determined by
+  // the mapping symbol name, $x for code, $d for data.
   auto IsCodeMapSymbol = [](const SymbolBody *B) {
     return B->getName() == "$x" || B->getName().startswith("$x.");
   };
@@ -444,54 +484,141 @@ std::map<InputSection *,
           MapSyms.end());
     }
   }
-  return SectionMap;
 }
 
-// Scan all the executable code in an AArch64 link to detect the Cortex-A53
-// erratum 843419.
-// FIXME: The current implementation only scans for the erratum sequence, it
-// does not attempt to fix it.
-void lld::elf::createA53Errata843419Fixes(
-    ArrayRef<OutputSection *> OutputSections) {
-  std::map<InputSection *, std::vector<const DefinedRegular *>> SectionMap =
-      makeAArch64SectionMap();
+// Insert the PatchSections we have created back into the
+// InputSectionDescription. We choose to insert after the last executable
+// InputSection so we don't alter the address of the execuable InputSections in
+// this InputSectionDescription.
+// FIXME: We make the assumption that the size of the InputSectionDescription
+// does not exceed the AArch64 branch range of 128MiB.
+void SectionPatcher::insertPatches(InputSectionDescription &ISD,
+                                   std::vector<Patch843419Section *> &Patches) {
+  uint64_t Off = 0;
+  for (const InputSection *IS : ISD.Sections) {
+    if ((IS->Flags & SHF_EXECINSTR) == 0)
+      break;
+    Off = IS->OutSecOff + IS->getSize();
+  }
+  for (Patch843419Section *P : Patches)
+    P->OutSecOff = Off;
+
+  ISD.Sections.insert(
+      std::upper_bound(ISD.Sections.begin(), ISD.Sections.end(),
+                       Patches.front(),
+                       [&](const InputSection *A, const InputSection *B) {
+                         return A->OutSecOff < B->OutSecOff;
+                       }),
+      Patches.begin(), Patches.end());
+}
+
+// Given an erratum sequence that starts at address AdrpAddr, with an
+// instruction that we need to patch at PatcheeOffset from the start of
+// InputSection IS, create a Patch843419 Section and add it to the
+// Patches that we need to insert.
+static void implementPatch(uint64_t AdrpAddr, uint64_t PatcheeOffset,
+                           InputSection *IS,
+                           std::vector<Patch843419Section *> &Patches) {
+  // There may be a relocation at the same offset that we are patching. There
+  // are three cases that we need to consider.
+  // Case 1: R_AARCH64_JUMP26 branch relocation. We have already patched this
+  // instance of the erratum on a previous patch and altered the relocation. We
+  // have nothing more to do.
+  // Case 2: A load/store register (unsigned immediate) class relocation. There
+  // are two of these R_AARCH_LD64_ABS_LO12_NC and R_AARCH_LD64_GOT_LO12_NC and
+  // they are both absolute. We need to add the same relocation to the patch,
+  // and replace the relocation with a R_AARCH_JUMP26 branch relocation.
+  // Case 3: No relocation. We must create a new R_AARCH64_JUMP26 branch
+  // relocation at the offset.
+  auto RelIt = std::find_if(
+      IS->Relocations.begin(), IS->Relocations.end(),
+      [=](const Relocation &R) { return R.Offset == PatcheeOffset; });
+  if (RelIt != IS->Relocations.end() && RelIt->Type == R_AARCH64_JUMP26)
+    return;
+
+  if (Config->Verbose)
+    message("detected cortex-a53-843419 erratum sequence starting at " +
+            utohexstr(AdrpAddr) + " in unpatched output.");
+
+  auto *PS = make<Patch843419Section>(IS, PatcheeOffset);
+  Patches.push_back(PS);
+
+  auto MakeRelToPatch = [](uint64_t Offset, SymbolBody *PatchSym) {
+    return Relocation{R_PC, R_AARCH64_JUMP26, Offset, 0, PatchSym};
+  };
+
+  if (RelIt != IS->Relocations.end()) {
+    PS->Relocations.push_back(
+        {RelIt->Expr, RelIt->Type, 0, RelIt->Addend, RelIt->Sym});
+    *RelIt = MakeRelToPatch(PatcheeOffset, PS->PatchSym);
+  } else
+    IS->Relocations.push_back(MakeRelToPatch(PatcheeOffset, PS->PatchSym));
+}
 
+// Scan all the instructions in InputSectionDescription, recording all the
+// Patch843419Sections to insert in Patches.
+void SectionPatcher::patchInputSectionDescription(
+    InputSectionDescription &ISD, std::vector<Patch843419Section *> &Patches) {
+  for (InputSection *IS : ISD.Sections) {
+    //  LLD doesn't use the erratum sequence in SyntheticSections.
+    if (isa<SyntheticSection>(IS))
+      continue;
+    // Use SectionMap to make sure we only scan code and not inline data.
+    // We have already sorted MapSyms in ascending order and removed consecutive
+    // mapping symbols of the same type. Our range of executable instructions to
+    // scan is therefore [CodeSym->Value, DataSym->Value) or [CodeSym->Value,
+    // section size).
+    std::vector<const DefinedRegular *> &MapSyms = SectionMap[IS];
+
+    auto CodeSym = llvm::find_if(MapSyms, [&](const DefinedRegular *MS) {
+      return MS->getName().startswith("$x");
+    });
+
+    while (CodeSym != MapSyms.end()) {
+      auto DataSym = std::next(CodeSym);
+      uint64_t Off = (*CodeSym)->Value;
+      uint64_t Limit =
+          (DataSym == MapSyms.end()) ? IS->Data.size() : (*DataSym)->Value;
+
+      while (Off < Limit) {
+        uint64_t StartAddr = IS->getParent()->Addr + IS->OutSecOff + Off;
+        if (uint64_t PatcheeOffset = scanCortexA53Errata843419(IS, Off, Limit))
+          implementPatch(StartAddr, PatcheeOffset, IS, Patches);
+      }
+      if (DataSym == MapSyms.end())
+        break;
+      CodeSym = std::next(DataSym);
+    }
+  }
+}
+
+// For each InputSectionDescription make one pass over the executable sections
+// looking for the erratum sequence; creating a synthetic Patch843419Section
+// for each instance found. We insert these synthetic patch sections after the
+// executable code in each InputSectionDescription.
+//
+// PreConditions:
+// The Output and Input Sections have had their final addresses assigned.
+//
+// PostConditions:
+// Returns true if at least one patch was added. The addresses of the
+// Ouptut and Input Sections may have been changed.
+// Returns false if no patches were required and no changes were made.
+bool SectionPatcher::create843419Fixes(
+    ArrayRef<OutputSection *> OutputSections) {
+  bool AddressesChanged = false;
   for (OutputSection *OS : OutputSections) {
     if (!(OS->Flags & SHF_ALLOC) || !(OS->Flags & SHF_EXECINSTR))
       continue;
     for (BaseCommand *BC : OS->Commands)
       if (auto *ISD = dyn_cast<InputSectionDescription>(BC)) {
-        for (InputSection *IS : ISD->Sections) {
-          //  LLD doesn't use the erratum sequence in SyntheticSections.
-          if (isa<SyntheticSection>(IS))
-            continue;
-          // Use SectionMap to make sure we only scan code and not inline data.
-          // We have already sorted MapSyms in ascending order and removed
-          // consecutive mapping symbols of the same type. Our range of
-          // executable instructions to scan is therefore [CodeSym->Value,
-          // DataSym->Value) or [CodeSym->Value, section size).
-          std::vector<const DefinedRegular *> &MapSyms = SectionMap[IS];
-
-          auto CodeSym = llvm::find_if(MapSyms, [&](const DefinedRegular *MS) {
-            return MS->getName().startswith("$x");
-          });
-
-          while (CodeSym != MapSyms.end()) {
-            auto DataSym = std::next(CodeSym);
-            uint64_t Off = (*CodeSym)->Value;
-            uint64_t Limit = (DataSym == MapSyms.end()) ? IS->Data.size()
-                                                        : (*DataSym)->Value;
-
-            while (Off < Limit) {
-              uint64_t StartAddr = IS->getParent()->Addr + IS->OutSecOff + Off;
-              if (scanCortexA53Errata843419(IS, Off, Limit))
-                report843419Fix(StartAddr);
-            }
-            if (DataSym == MapSyms.end())
-              break;
-            CodeSym = std::next(DataSym);
-          }
+        std::vector<Patch843419Section *> Patches;
+        patchInputSectionDescription(*ISD, Patches);
+        if (!Patches.empty()) {
+          insertPatches(*ISD, Patches);
+          AddressesChanged = true;
         }
       }
   }
+  return AddressesChanged;
 }
diff --git a/ELF/SectionPatcher.h b/ELF/SectionPatcher.h
index a6b067054..1439880b6 100644
--- a/ELF/SectionPatcher.h
+++ b/ELF/SectionPatcher.h
@@ -12,17 +12,45 @@
 
 #include "lld/Common/LLVM.h"
 
+#include <map>
+#include <vector>
+
 namespace lld {
 namespace elf {
 
+class DefinedRegular;
+class InputSection;
+class InputSectionDescription;
 class OutputSection;
+class Patch843419Section;
 
 // Implementation of the -fix-cortex-a53-843419 which affects early revisions
-// of the cortex-a53 when running in the AArch64 execution state.
-
-// FIXME: Only detects and reports the presence of the instruction sequence that
-// can trigger the erratum 843419.
-void createA53Errata843419Fixes(ArrayRef<OutputSection *> OutputSections);
+// of the cortex-a53 when running in the AArch64 execution state. The erratum
+// occurs when a certain sequence of instructions occur on a 4k page boundary.
+// To workaround this problem the linker will scan for these sequences and will
+// replace one of the instructions with a branch to a thunk called a patch that
+// will execute the instruction and return to the instruction after the branch
+// to the patch. The replacement of the instruction with a branch is
+// sufficient to prevent the erratum.
+class SectionPatcher {
+public:
+  SectionPatcher();
+
+  // return true if Patches have been added to the OutputSections.
+  bool create843419Fixes(ArrayRef<OutputSection *> OutputSections);
+
+private:
+  void patchInputSectionDescription(InputSectionDescription &ISD,
+                                    std::vector<Patch843419Section *> &Patches);
+
+  void insertPatches(InputSectionDescription &ISD,
+                     std::vector<Patch843419Section *> &Patches);
+
+  // A cache of the mapping symbols defined by the InputSecion sorted in order
+  // of ascending value with redundant symbols removed. These describe
+  // the ranges of code and data in an executable InputSection.
+  std::map<InputSection *, std::vector<const DefinedRegular *>> SectionMap;
+};
 
 } // namespace elf
 } // namespace lld
diff --git a/ELF/Writer.cpp b/ELF/Writer.cpp
index d8bcd60e5..c30ec7043 100644
--- a/ELF/Writer.cpp
+++ b/ELF/Writer.cpp
@@ -1389,10 +1389,11 @@ template <class ELFT> void Writer<ELFT>::finalizeSections() {
     }
   }
   if (Config->EMachine == EM_AARCH64 && Config->FixCortexA53Errata843419) {
-    Script->assignAddresses();
-    createA53Errata843419Fixes(OutputSections);
+    SectionPatcher SP;
+    do
+      Script->assignAddresses();
+    while (SP.create843419Fixes(OutputSections));
   }
-
   // Fill other section headers. The dynamic table is finalized
   // at the end because some tags like RELSZ depend on result
   // of finalizing other sections.