[ELF] Check the Elf_Rel addends for dynamic relocations

[arichardson]

Summary

There used to be many cases where addends for Elf_Rel were not emitted in
the final object file (mostly when building for MIPS64 since the input .o
files use RELA but the output uses REL). These cases have been fixed since,
but this patch adds a check to ensure that the written values are correct.
It is based on a previous patch that I added to the CHERI fork of LLD since
we were using MIPS64 as a baseline. The work has now almost entirely
shifted to RISC-V and Arm Morello (which use Elf_Rela), but I thought
it would be useful to upstream our local changes anyway.

This patch adds a (hidden) command line flag --check-dynamic-relocations
that can be used to enable these checks. It is also on by default in
assertions builds for targets that handle all dynamic relocations kinds
that LLD can emit in Target::getImplicitAddend(). Currently this is
enabled for ARM, MIPS, and I386.

Depends on D100490

[peter.smith]

Thanks for splitting out. I'm happy with this. Will be good to wait for MaskRay to have a look.

[MaskRay]

lld/ELF/Arch/ARM.cpp

842

The value is not used.

ld.so implementations don't use addend for JUMP_SLOT/GLOB_DAT.

lld/ELF/OutputSections.cpp

571

perhaps use

dynamic relocation XXX at offset YYY[ against symbol ZZZ]

[arichardson]

lld/ELF/Arch/ARM.cpp

842

I agree that the value at that location is not really an addend since Elf_Rela also uses the in-memory value instead of of the r_addend field (FreeBSD does *where += (Elf_Addr)obj->relocbase; for all JUMP_SLOT values).
Maybe // These relocations do not have an implicit addend?

[arichardson]

Improve comments

[arichardson]

Add XFAIL to two tests that need a follow-up patch

[MaskRay]

Thanks!

lld/ELF/Arch/ARM.cpp

default:
     error(getErrorLocation(loc) + "unrecognized relocation " +
           toString(rel.type));
   }
 }
 
 int64_t ARM::getImplicitAddend(const uint8_t *buf, RelType type) const {
   switch (type) {
   default:
+    internalLinkerError(getErrorLocation(buf),
+                        "cannot read addend for relocation " + toString(type));
     return 0;
   case R_ARM_ABS32:
   case R_ARM_BASE_PREL:
+  case R_ARM_GLOB_DAT:
   case R_ARM_GOTOFF32:
   case R_ARM_GOT_BREL:
   case R_ARM_GOT_PREL:
+  case R_ARM_IRELATIVE:
   case R_ARM_REL32:
+  case R_ARM_RELATIVE:
+  case R_ARM_SBREL32:
   case R_ARM_TARGET1:
   case R_ARM_TARGET2:
+  case R_ARM_TLS_DTPMOD32:
+  case R_ARM_TLS_DTPOFF32:
   case R_ARM_TLS_GD32:
-  case R_ARM_TLS_LDM32:
-  case R_ARM_TLS_LDO32:
   case R_ARM_TLS_IE32:
+  case R_ARM_TLS_LDM32:
   case R_ARM_TLS_LE32:
+  case R_ARM_TLS_LDO32:
+  case R_ARM_TLS_TPOFF32:
     return SignExtend64<32>(read32le(buf));
   case R_ARM_PREL31:
     return SignExtend64<31>(read32le(buf));
   case R_ARM_CALL:
   case R_ARM_JUMP24:
   case R_ARM_PC24:
   case R_ARM_PLT32:
     return SignExtend64<26>(read32le(buf) << 2);
case R_ARM_THM_PC8:
     // this trick permits the PC bias of -4 to be encoded using imm8 = 0xff
     return ((((read16le(buf) & 0xff) << 2) + 4) & 0x3ff) - 4;
   case R_ARM_THM_PC12: {
     // LDR (literal) encoding T2, add = (U == '1') imm12
     bool u = read16le(buf) & 0x0080;
     uint64_t imm12 = read16le(buf + 2) & 0x0fff;
     return u ? imm12 : -imm12;
   }
+  case R_ARM_NONE:
+  case R_ARM_JUMP_SLOT:
+    return 0; // The stored value at this location is not the addend.
   }
 }
 
 TargetInfo *elf::getARMTargetInfo() {
   static ARM target;
   return &target;
 }

lld/ELF/Arch/Mips.cpp

bool MIPS<ELFT>::needsThunk(RelExpr expr, RelType type, const InputFile *file,
   return d && isMipsPIC<ELFT>(d);
 }
 
 template <class ELFT>
 int64_t MIPS<ELFT>::getImplicitAddend(const uint8_t *buf, RelType type) const {
   const endianness e = ELFT::TargetEndianness;
   switch (type) {
   case R_MIPS_32:
+  case R_MIPS_REL32:
   case R_MIPS_GPREL32:
   case R_MIPS_TLS_DTPREL32:
+  case R_MIPS_TLS_DTPMOD32:
   case R_MIPS_TLS_TPREL32:
     return SignExtend64<32>(read32(buf));
   case R_MIPS_26:
     // FIXME (simon): If the relocation target symbol is not a PLT entry
     // we should use another expression for calculation:
     // ((A << 2) | (P & 0xf0000000)) >> 2
     return SignExtend64<28>(read32(buf) << 2);
+  case R_MIPS_CALL_HI16:
   case R_MIPS_GOT16:
+  case R_MIPS_GOT_HI16:
   case R_MIPS_HI16:
   case R_MIPS_PCHI16:
     return SignExtend64<16>(read32(buf)) << 16;
+  case R_MIPS_CALL16:
+  case R_MIPS_CALL_LO16:
+  case R_MIPS_GOT_LO16:
   case R_MIPS_GPREL16:
   case R_MIPS_LO16:
   case R_MIPS_PCLO16:
   case R_MIPS_TLS_DTPREL_HI16:
   case R_MIPS_TLS_DTPREL_LO16:
+  case R_MIPS_TLS_GD:
+  case R_MIPS_TLS_GOTTPREL:
+  case R_MIPS_TLS_LDM:
   case R_MIPS_TLS_TPREL_HI16:
   case R_MIPS_TLS_TPREL_LO16:
     return SignExtend64<16>(read32(buf));
   case R_MICROMIPS_GOT16:
   case R_MICROMIPS_HI16:
     return SignExtend64<16>(readShuffle<e>(buf)) << 16;
+  case R_MICROMIPS_CALL16:
   case R_MICROMIPS_GPREL16:
   case R_MICROMIPS_LO16:
   case R_MICROMIPS_TLS_DTPREL_HI16:
   case R_MICROMIPS_TLS_DTPREL_LO16:
+  case R_MICROMIPS_TLS_GD:
+  case R_MICROMIPS_TLS_GOTTPREL:
+  case R_MICROMIPS_TLS_LDM:
   case R_MICROMIPS_TLS_TPREL_HI16:
   case R_MICROMIPS_TLS_TPREL_LO16:
     return SignExtend64<16>(readShuffle<e>(buf));
   case R_MICROMIPS_GPREL7_S2:
     return SignExtend64<9>(readShuffle<e>(buf) << 2);
   case R_MIPS_PC16:
     return SignExtend64<18>(read32(buf) << 2);
   case R_MIPS_PC19_S2:
int64_t MIPS<ELFT>::getImplicitAddend(const uint8_t *buf, RelType type) const {
   case R_MICROMIPS_PC19_S2:
     return SignExtend64<21>(readShuffle<e>(buf) << 2);
   case R_MICROMIPS_PC21_S1:
     return SignExtend64<22>(readShuffle<e>(buf) << 1);
   case R_MICROMIPS_PC23_S2:
     return SignExtend64<25>(readShuffle<e>(buf) << 2);
   case R_MICROMIPS_PC26_S1:
     return SignExtend64<27>(readShuffle<e>(buf) << 1);
+  case R_MIPS_64:
+  case R_MIPS_TLS_DTPMOD64:
+  case R_MIPS_TLS_DTPREL64:
+  case R_MIPS_TLS_TPREL64:
+  case (R_MIPS_64 << 8) | R_MIPS_REL32:
+    return read64(buf);
+  case R_MIPS_COPY:
+    return config->is64 ? read64(buf) : read32(buf);
+  case R_MIPS_NONE:
+  case R_MIPS_JUMP_SLOT:
+  case R_MIPS_JALR:
+    return 0; // The stored value at this location is not the addend.
   default:
+    internalLinkerError(getErrorLocation(buf),
+                        "cannot read addend for relocation " + toString(type));
     return 0;
   }
 }
 
 static std::pair<uint32_t, uint64_t>
 calculateMipsRelChain(uint8_t *loc, RelType type, uint64_t val) {
   // MIPS N64 ABI packs multiple relocations into the single relocation
   // record. In general, all up to three relocations can have arbitrary

lld/ELF/Arch/X86.cpp

int64_t X86::getImplicitAddend(const uint8_t *buf, RelType type) const {
   switch (type) {
   case R_386_8:
   case R_386_PC8:
     return SignExtend64<8>(*buf);
   case R_386_16:
   case R_386_PC16:
     return SignExtend64<16>(read16le(buf));
   case R_386_32:
+  case R_386_GLOB_DAT:
   case R_386_GOT32:
   case R_386_GOT32X:
   case R_386_GOTOFF:
   case R_386_GOTPC:
+  case R_386_IRELATIVE:
   case R_386_PC32:
   case R_386_PLT32:
+  case R_386_RELATIVE:
+  case R_386_TLS_DTPMOD32:
+  case R_386_TLS_DTPOFF32:
   case R_386_TLS_LDO_32:
+  case R_386_TLS_LDM:
+  case R_386_TLS_IE:
+  case R_386_TLS_IE_32:
   case R_386_TLS_LE:
+  case R_386_TLS_LE_32:
+  case R_386_TLS_GD:
+  case R_386_TLS_GD_32:
+  case R_386_TLS_GOTIE:
+  case R_386_TLS_TPOFF:
+  case R_386_TLS_TPOFF32:
     return SignExtend64<32>(read32le(buf));
+  case R_386_NONE:
+  case R_386_JUMP_SLOT:
+    return 0; // The stored value at this location is not the addend.
   default:
+    internalLinkerError(getErrorLocation(buf),
+                        "cannot read addend for relocation " + toString(type));
     return 0;
   }
 }
 
 void X86::relocate(uint8_t *loc, const Relocation &rel, uint64_t val) const {
   switch (rel.type) {
   case R_386_8:
     // R_386_{PC,}{8,16} are not part of the i386 psABI, but they are

lld/ELF/Config.h

 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Support/CachePruning.h"
 #include "llvm/Support/CodeGen.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/GlobPattern.h"
+#include "llvm/Support/PrettyStackTrace.h"
 #include <atomic>
 #include <vector>
 
 namespace lld {
 namespace elf {
 
 class InputFile;
 class InputSectionBase;
struct Configuration {
   bool armHasBlx = false;
   bool armHasMovtMovw = false;
   bool armJ1J2BranchEncoding = false;
   bool asNeeded = false;
   bool bsymbolic;
   bool bsymbolicFunctions;
   bool callGraphProfileSort;
   bool checkSections;
+  bool checkDynamicRelocs;
   bool compressDebugSections;
   bool cref;
   std::vector<std::pair<llvm::GlobPattern, uint64_t>> deadRelocInNonAlloc;
   bool defineCommon;
   bool demangle = true;
   bool dependentLibraries;
   bool disableVerify;
   bool ehFrameHdr;

 }
 
 static inline void errorOrWarn(const Twine &msg) {
   if (!config->noinhibitExec)
     error(msg);
   else
     warn(msg);
 }
+
+static inline void internalLinkerError(StringRef loc, const Twine &msg) {
+  errorOrWarn(loc + "internal linker error: " + msg + "\n" +
+              llvm::getBugReportMsg());
+}
+
 } // namespace elf
 } // namespace lld
 
 #endif

lld/ELF/Driver.cpp

static void setConfigs(opt::InputArgList &args) {
   // If the output uses REL relocations we must store the dynamic relocation
   // addends to the output sections. We also store addends for RELA relocations
   // if --apply-dynamic-relocs is used.
   // We default to not writing the addends when using RELA relocations since
   // any standard conforming tool can find it in r_addend.
   config->writeAddends = args.hasFlag(OPT_apply_dynamic_relocs,
                                       OPT_no_apply_dynamic_relocs, false) ||
                          !config->isRela;
-
+  // Validation of dynamic relocation addends is on by default for assertions
+  // builds (for supported targets) and disabled otherwise. Ideally we would
+  // enable the debug checks for all targets, but currently not all targets
+  // have support for reading Elf_Rel addends, so we only enable for a subset.
+#ifndef NDEBUG
+  bool checkDynamicRelocsDefault = m == EM_ARM || m == EM_386 || m == EM_MIPS;
+#else
+  bool checkDynamicRelocsDefault = false;
+#endif
+  config->checkDynamicRelocs =
+      args.hasFlag(OPT_check_dynamic_relocations,
+                   OPT_no_check_dynamic_relocations, checkDynamicRelocsDefault);
   config->tocOptimize =
       args.hasFlag(OPT_toc_optimize, OPT_no_toc_optimize, m == EM_PPC64);
   config->pcRelOptimize =
       args.hasFlag(OPT_pcrel_optimize, OPT_no_pcrel_optimize, m == EM_PPC64);
 }
 
 // Returns a value of "-format" option.
 static bool isFormatBinary(StringRef s) {

lld/ELF/Options.td

 def: F<"warn-shared-textrel">;
 def: JoinedOrSeparate<["-"], "G">;
 def: F<"Qy">;
 
 // Hidden option used for testing MIPS multi-GOT implementation.
 defm mips_got_size:
   Eq<"mips-got-size", "Max size of a single MIPS GOT. 0x10000 by default.">,
   Flags<[HelpHidden]>;
+
+// Hidden option used to opt-in to additional output checks.
+defm check_dynamic_relocations: BB<"check-dynamic-relocations",
+    "Perform additional validation of the written dynamic relocations",
+    "Do not perform additional validation of the written dynamic relocations">,
+  Flags<[HelpHidden]>;

lld/ELF/OutputSections.h

public:
 
   // Tracks whether the section has ever had an input section added to it, even
   // if the section was later removed (e.g. because it is a synthetic section
   // that wasn't needed). This is needed for orphan placement.
   bool hasInputSections = false;
 
   void finalize();
   template <class ELFT> void writeTo(uint8_t *buf);
+  // Check that the addends for dynamic relocations were written correctly.
+  void checkDynRelAddends(const uint8_t *bufStart);
   template <class ELFT> void maybeCompress();
 
   void sort(llvm::function_ref<int(InputSectionBase *s)> order);
   void sortInitFini();
   void sortCtorsDtors();
 
 private:
   // Used for implementation of --compress-debug-sections option.

lld/ELF/OutputSections.cpp

 std::array<uint8_t, 4> OutputSection::getFiller() {
   if (filler)
     return *filler;
   if (flags & SHF_EXECINSTR)
     return target->trapInstr;
   return {0, 0, 0, 0};
 }
 
+void OutputSection::checkDynRelAddends(const uint8_t *bufStart) {
+  assert(config->writeAddends && config->checkDynamicRelocs);
+  assert(type == SHT_REL || type == SHT_RELA);
+  std::vector<InputSection *> sections = getInputSections(this);
+  parallelForEachN(0, sections.size(), [&](size_t i) {
+    // When linking with -r or --emit-relocs we might also call this function
+    // for input .rel[a].<sec> sections which we simply pass through to the
+    // output. We skip over those and only look at the synthetic relocation
+    // sections created during linking.
+    const auto *sec = dyn_cast<RelocationBaseSection>(sections[i]);
+    if (!sec)
+      return;
+    for (const DynamicReloc &rel : sec->relocs) {
+      int64_t addend = rel.computeAddend();
+      const OutputSection *relOsec = rel.inputSec->getOutputSection();
+      assert(relOsec != nullptr && "missing output section for relocation");
+      const uint8_t *relocTarget =
+          bufStart + relOsec->offset + rel.inputSec->getOffset(rel.offsetInSec);
+      // For SHT_NOBITS the written addend is always zero.
+      int64_t writtenAddend =
+          relOsec->type == SHT_NOBITS
+              ? 0
+              : target->getImplicitAddend(relocTarget, rel.type);
+      if (addend != writtenAddend)
+        internalLinkerError(
+            getErrorLocation(relocTarget),
+            "wrote incorrect addend value 0x" + utohexstr(writtenAddend) +
+                " instead of 0x" + utohexstr(addend) + " for dynamic " +
+                toString(rel.type) + " relocation against " +
+                (rel.sym ? toString(*rel.sym) : "load address") +
+                " at offset 0x" + utohexstr(rel.getOffset()));
+    }
+  });
+}
+
 template void OutputSection::writeHeaderTo<ELF32LE>(ELF32LE::Shdr *Shdr);
 template void OutputSection::writeHeaderTo<ELF32BE>(ELF32BE::Shdr *Shdr);
 template void OutputSection::writeHeaderTo<ELF64LE>(ELF64LE::Shdr *Shdr);
 template void OutputSection::writeHeaderTo<ELF64BE>(ELF64BE::Shdr *Shdr);
 
 template void OutputSection::writeTo<ELF32LE>(uint8_t *Buf);
 template void OutputSection::writeTo<ELF32BE>(uint8_t *Buf);
 template void OutputSection::writeTo<ELF64LE>(uint8_t *Buf);
 template void OutputSection::writeTo<ELF64BE>(uint8_t *Buf);
 
 template void OutputSection::maybeCompress<ELF32LE>();
 template void OutputSection::maybeCompress<ELF32BE>();
 template void OutputSection::maybeCompress<ELF64LE>();
 template void OutputSection::maybeCompress<ELF64BE>();

lld/ELF/SyntheticSections.h

void addRelativeReloc(RelType dynType, InputSectionBase *isec,
                         RelType addendRelType, RelExpr expr);
   void addReloc(DynamicReloc::Kind kind, RelType dynType,
                 InputSectionBase *inputSec, uint64_t offsetInSec, Symbol &sym,
                 int64_t addend, RelExpr expr, RelType addendRelType);
   bool isNeeded() const override { return !relocs.empty(); }
   size_t getSize() const override { return relocs.size() * this->entsize; }
   size_t getRelativeRelocCount() const { return numRelativeRelocs; }
   void finalizeContents() override;
+  static bool classof(const SectionBase *d) {
+    return SyntheticSection::classof(d) &&
+           (d->type == llvm::ELF::SHT_RELA || d->type == llvm::ELF::SHT_REL ||
+            d->type == llvm::ELF::SHT_RELR);
+  }
   int32_t dynamicTag, sizeDynamicTag;
   std::vector<DynamicReloc> relocs;
 
 protected:
   size_t numRelativeRelocs = 0;
 };
 
 template <class ELFT>

lld/ELF/Target.cpp

ErrorPlace elf::getErrorPlace(const uint8_t *loc) {
   default:
     llvm_unreachable("unknown ELF type");
   }
 }
 
 TargetInfo::~TargetInfo() {}
 
 int64_t TargetInfo::getImplicitAddend(const uint8_t *buf, RelType type) const {
+  internalLinkerError(getErrorLocation(buf),
+                      "cannot read addend for relocation " + toString(type));
   return 0;
 }
 
 bool TargetInfo::usesOnlyLowPageBits(RelType type) const { return false; }
 
 bool TargetInfo::needsThunk(RelExpr expr, RelType type, const InputFile *file,
                             uint64_t branchAddr, const Symbol &s,
                             int64_t a) const {

lld/ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::writeSections() {
   // section while doing it.
   for (OutputSection *sec : outputSections)
     if (sec->type == SHT_REL || sec->type == SHT_RELA)
       sec->writeTo<ELFT>(Out::bufferStart + sec->offset);
 
   for (OutputSection *sec : outputSections)
     if (sec->type != SHT_REL && sec->type != SHT_RELA)
       sec->writeTo<ELFT>(Out::bufferStart + sec->offset);
+
+  // Finally, check that all dynamic relocation addends were written correctly.
+  if (config->checkDynamicRelocs && config->writeAddends) {
+    for (OutputSection *sec : outputSections)
+      if (sec->type == SHT_REL || sec->type == SHT_RELA)
+        sec->checkDynRelAddends(Out::bufferStart);
+  }
 }
 
 // Computes a hash value of Data using a given hash function.
 // In order to utilize multiple cores, we first split data into 1MB
 // chunks, compute a hash for each chunk, and then compute a hash value
 // of the hash values.
 static void
 computeHash(llvm::MutableArrayRef<uint8_t> hashBuf,