Fix issue #62423: relaxation region overflow

[korran]

Summary

lld incorrectly emits region overflow errors when linker relaxation
would prevent an overflow. This occurs because the region overflow
errors are emitted before any relaxation passes have been done. This
commit ignores region overflow errors until the final assignAddresses()
pass.

See more information on this bug at
https://github.com/llvm/llvm-project/issues/62423

[asb]

Adding @jrtc27. Also CC @jobnoorman in case this same problem exists in the JITLink relaxation implementation.

lld/ELF/LinkerScript.h

 class InputFile;
 class InputSection;
 class InputSectionBase;
 class OutputSection;
 class SectionBase;
 class ThunkSection;
 struct OutputDesc;
 
+enum AssignFlags {
+  AF_None = 0,
+  // This is the address-assignment final pass; region overflow errors should
+  // only be enforced when this is set.
+  AF_FinalPass = (1 << 0),
+};
+
 // This represents an r-value in the linker script.
 struct ExprValue {
   ExprValue(SectionBase *sec, bool forceAbsolute, uint64_t val,
             const Twine &loc)
       : sec(sec), val(val), forceAbsolute(forceAbsolute), loc(loc.str()) {}
 
   ExprValue(uint64_t val) : ExprValue(nullptr, false, val, "") {}
 
struct AddressState {
     MemoryRegion *lmaRegion = nullptr;
     uint64_t lmaOffset = 0;
     uint64_t tbssAddr = 0;
   };
 
   llvm::DenseMap<llvm::CachedHashStringRef, OutputDesc *> nameToOutputSection;
 
   void addSymbol(SymbolAssignment *cmd);
-  void assignSymbol(SymbolAssignment *cmd, bool inSec);
-  void setDot(Expr e, const Twine &loc, bool inSec);
-  void expandOutputSection(uint64_t size);
-  void expandMemoryRegions(uint64_t size);
+  void assignSymbol(SymbolAssignment *cmd, bool inSec, AssignFlags flags);
+  void setDot(Expr e, const Twine &loc, bool inSec, AssignFlags flags);
+  void expandOutputSection(uint64_t size, AssignFlags flags);
+  void expandMemoryRegions(uint64_t size, AssignFlags flags);
 
   SmallVector<InputSectionBase *, 0>
   computeInputSections(const InputSectionDescription *,
                        ArrayRef<InputSectionBase *>);
 
   SmallVector<InputSectionBase *, 0> createInputSectionList(OutputSection &cmd);
 
   void discardSynthetic(OutputSection &);
 
   SmallVector<size_t, 0> getPhdrIndices(OutputSection *sec);
 
   std::pair<MemoryRegion *, MemoryRegion *>
   findMemoryRegion(OutputSection *sec, MemoryRegion *hint);
 
-  void assignOffsets(OutputSection *sec);
+  void assignOffsets(OutputSection *sec, AssignFlags flags);
 
   // This captures the local AddressState and makes it accessible
   // deliberately. This is needed as there are some cases where we cannot just
   // thread the current state through to a lambda function created by the
   // script parser.
   // This should remain a plain pointer as its lifetime is smaller than
   // LinkerScript.
   AddressState *state = nullptr;
public:
   void diagnoseOrphanHandling() const;
   void adjustOutputSections();
   void adjustSectionsAfterSorting();
 
   SmallVector<PhdrEntry *, 0> createPhdrs();
   bool needsInterpSection();
 
   bool shouldKeep(InputSectionBase *s);
-  const Defined *assignAddresses();
+  const Defined *assignAddresses(AssignFlags flags);
   void allocateHeaders(SmallVector<PhdrEntry *, 0> &phdrs);
   void processSectionCommands();
   void processSymbolAssignments();
   void declareSymbols();
 
   bool isDiscarded(const OutputSection *sec) const;
 
   // Used to handle INSERT AFTER statements.

lld/ELF/LinkerScript.cpp

OutputDesc *LinkerScript::getOrCreateOutputSection(StringRef name) {
   OutputDesc *&cmdRef = nameToOutputSection[CachedHashStringRef(name)];
   if (!cmdRef)
     cmdRef = make<OutputDesc>(name, SHT_PROGBITS, 0);
   return cmdRef;
 }
 
 // Expands the memory region by the specified size.
 static void expandMemoryRegion(MemoryRegion *memRegion, uint64_t size,
-                               StringRef secName) {
+                               StringRef secName, AssignFlags flags) {
   memRegion->curPos += size;
   uint64_t newSize = memRegion->curPos - (memRegion->origin)().getValue();
   uint64_t length = (memRegion->length)().getValue();
-  if (newSize > length)
+  if ((flags & AF_FinalPass) && newSize > length)
     error("section '" + secName + "' will not fit in region '" +
           memRegion->name + "': overflowed by " + Twine(newSize - length) +
           " bytes");
 }
 
-void LinkerScript::expandMemoryRegions(uint64_t size) {
+void LinkerScript::expandMemoryRegions(uint64_t size, AssignFlags flags) {
   if (state->memRegion)
-    expandMemoryRegion(state->memRegion, size, state->outSec->name);
+    expandMemoryRegion(state->memRegion, size, state->outSec->name, flags);
   // Only expand the LMARegion if it is different from memRegion.
   if (state->lmaRegion && state->memRegion != state->lmaRegion)
-    expandMemoryRegion(state->lmaRegion, size, state->outSec->name);
+    expandMemoryRegion(state->lmaRegion, size, state->outSec->name, flags);
 }
 
-void LinkerScript::expandOutputSection(uint64_t size) {
+void LinkerScript::expandOutputSection(uint64_t size, AssignFlags flags) {
   state->outSec->size += size;
-  expandMemoryRegions(size);
+  expandMemoryRegions(size, flags);
 }
 
-void LinkerScript::setDot(Expr e, const Twine &loc, bool inSec) {
+void LinkerScript::setDot(Expr e, const Twine &loc, bool inSec,
+                          AssignFlags flags) {
   uint64_t val = e().getValue();
   if (val < dot && inSec)
     error(loc + ": unable to move location counter backward for: " +
           state->outSec->name);
 
   // Update to location counter means update to section size.
   if (inSec)
-    expandOutputSection(val - dot);
+    expandOutputSection(val - dot, flags);
 
   dot = val;
 }
 
 // Used for handling linker symbol assignments, for both finalizing
 // their values and doing early declarations. Returns true if symbol
 // should be defined from linker script.
 static bool shouldDefineSym(SymbolAssignment *cmd) {
for (SectionCommand *cmd : sec.commands)
       if (auto *assign = dyn_cast<SymbolAssignment>(cmd))
         declareSymbol(assign);
   }
 }
 
 // This function is called from assignAddresses, while we are
 // fixing the output section addresses. This function is supposed
 // to set the final value for a given symbol assignment.
-void LinkerScript::assignSymbol(SymbolAssignment *cmd, bool inSec) {
+void LinkerScript::assignSymbol(SymbolAssignment *cmd, bool inSec,
+                                AssignFlags flags) {
   if (cmd->name == ".") {
-    setDot(cmd->expression, cmd->location, inSec);
+    setDot(cmd->expression, cmd->location, inSec, flags);
     return;
   }
 
   if (!cmd->sym)
     return;
 
   ExprValue v = cmd->expression();
   if (v.isAbsolute()) {
static OutputSection *findFirstSection(PhdrEntry *load) {
   for (OutputSection *sec : outputSections)
     if (sec->ptLoad == load)
       return sec;
   return nullptr;
 }
 
 // This function assigns offsets to input sections and an output section
 // for a single sections command (e.g. ".text { *(.text); }").
-void LinkerScript::assignOffsets(OutputSection *sec) {
+void LinkerScript::assignOffsets(OutputSection *sec, AssignFlags flags) {
   const bool isTbss = (sec->flags & SHF_TLS) && sec->type == SHT_NOBITS;
   const bool sameMemRegion = state->memRegion == sec->memRegion;
   const bool prevLMARegionIsDefault = state->lmaRegion == nullptr;
   const uint64_t savedDot = dot;
   state->memRegion = sec->memRegion;
   state->lmaRegion = sec->lmaRegion;
 
   if (!(sec->flags & SHF_ALLOC)) {
     // Non-SHF_ALLOC sections have zero addresses.
     dot = 0;
   } else if (isTbss) {
     // Allow consecutive SHF_TLS SHT_NOBITS output sections. The address range
     // starts from the end address of the previous tbss section.
     if (state->tbssAddr == 0)
       state->tbssAddr = dot;
     else
       dot = state->tbssAddr;
   } else {
     if (state->memRegion)
       dot = state->memRegion->curPos;
     if (sec->addrExpr)
-      setDot(sec->addrExpr, sec->location, false);
+      setDot(sec->addrExpr, sec->location, false, flags);
 
     // If the address of the section has been moved forward by an explicit
     // expression so that it now starts past the current curPos of the enclosing
     // region, we need to expand the current region to account for the space
     // between the previous section, if any, and the start of this section.
     if (state->memRegion && state->memRegion->curPos < dot)
       expandMemoryRegion(state->memRegion, dot - state->memRegion->curPos,
-                         sec->name);
+                         sec->name, flags);
   }
 
   state->outSec = sec;
   if (sec->addrExpr && script->hasSectionsCommand) {
     // The alignment is ignored.
     sec->addr = dot;
   } else {
     // sec->alignment is the max of ALIGN and the maximum of input
     // section alignments.
     const uint64_t pos = dot;
     dot = alignToPowerOf2(dot, sec->addralign);
     sec->addr = dot;
-    expandMemoryRegions(dot - pos);
+    expandMemoryRegions(dot - pos, flags);
   }
 
   // state->lmaOffset is LMA minus VMA. If LMA is explicitly specified via AT()
   // or AT>, recompute state->lmaOffset; otherwise, if both previous/current LMA
   // region is the default, and the two sections are in the same memory region,
   // reuse previous lmaOffset; otherwise, reset lmaOffset to 0. This emulates
   // heuristics described in
   // https://sourceware.org/binutils/docs/ld/Output-Section-LMA.html
   if (sec->lmaExpr) {
     state->lmaOffset = sec->lmaExpr().getValue() - dot;
   } else if (MemoryRegion *mr = sec->lmaRegion) {
     uint64_t lmaStart = alignToPowerOf2(mr->curPos, sec->addralign);
     if (mr->curPos < lmaStart)
-      expandMemoryRegion(mr, lmaStart - mr->curPos, sec->name);
+      expandMemoryRegion(mr, lmaStart - mr->curPos, sec->name, flags);
     state->lmaOffset = lmaStart - dot;
   } else if (!sameMemRegion || !prevLMARegionIsDefault) {
     state->lmaOffset = 0;
   }
 
   // Propagate state->lmaOffset to the first "non-header" section.
   if (PhdrEntry *l = sec->ptLoad)
     if (sec == findFirstSection(l))
       l->lmaOffset = state->lmaOffset;
 
   // We can call this method multiple times during the creation of
   // thunks and want to start over calculation each time.
   sec->size = 0;
 
   // We visited SectionsCommands from processSectionCommands to
   // layout sections. Now, we visit SectionsCommands again to fix
   // section offsets.
   for (SectionCommand *cmd : sec->commands) {
     // This handles the assignments to symbol or to the dot.
     if (auto *assign = dyn_cast<SymbolAssignment>(cmd)) {
       assign->addr = dot;
-      assignSymbol(assign, true);
+      assignSymbol(assign, true, flags);
       assign->size = dot - assign->addr;
       continue;
     }
 
     // Handle BYTE(), SHORT(), LONG(), or QUAD().
     if (auto *data = dyn_cast<ByteCommand>(cmd)) {
       data->offset = dot - sec->addr;
       dot += data->size;
-      expandOutputSection(data->size);
+      expandOutputSection(data->size, flags);
       continue;
     }
 
     // Handle a single input section description command.
     // It calculates and assigns the offsets for each section and also
     // updates the output section size.
     for (InputSection *isec : cast<InputSectionDescription>(cmd)->sections) {
       assert(isec->getParent() == sec);
       const uint64_t pos = dot;
       dot = alignToPowerOf2(dot, isec->addralign);
       isec->outSecOff = dot - sec->addr;
       dot += isec->getSize();
 
       // Update output section size after adding each section. This is so that
       // SIZEOF works correctly in the case below:
       // .foo { *(.aaa) a = SIZEOF(.foo); *(.bbb) }
-      expandOutputSection(dot - pos);
+      expandOutputSection(dot - pos, flags);
     }
   }
 
   // Non-SHF_ALLOC sections do not affect the addresses of other OutputSections
   // as they are not part of the process image.
   if (!(sec->flags & SHF_ALLOC)) {
     dot = savedDot;
   } else if (isTbss) {
LinkerScript::AddressState::AddressState() {
   }
 }
 
 // Here we assign addresses as instructed by linker script SECTIONS
 // sub-commands. Doing that allows us to use final VA values, so here
 // we also handle rest commands like symbol assignments and ASSERTs.
 // Returns a symbol that has changed its section or value, or nullptr if no
 // symbol has changed.
-const Defined *LinkerScript::assignAddresses() {
+const Defined *LinkerScript::assignAddresses(AssignFlags flags) {
   if (script->hasSectionsCommand) {
     // With a linker script, assignment of addresses to headers is covered by
     // allocateHeaders().
     dot = config->imageBase.value_or(0);
   } else {
     // Assign addresses to headers right now.
     dot = target->getImageBase();
     Out::elfHeader->addr = dot;
     Out::programHeaders->addr = dot + Out::elfHeader->size;
     dot += getHeaderSize();
   }
 
   AddressState st;
   state = &st;
   errorOnMissingSection = true;
   st.outSec = aether;
 
   SymbolAssignmentMap oldValues = getSymbolAssignmentValues(sectionCommands);
   for (SectionCommand *cmd : sectionCommands) {
     if (auto *assign = dyn_cast<SymbolAssignment>(cmd)) {
       assign->addr = dot;
-      assignSymbol(assign, false);
+      assignSymbol(assign, false, flags);
       assign->size = dot - assign->addr;
       continue;
     }
-    assignOffsets(&cast<OutputDesc>(cmd)->osec);
+    assignOffsets(&cast<OutputDesc>(cmd)->osec, flags);
   }
 
   state = nullptr;
   return getChangedSymbolAssignment(oldValues);
 }
 
 // Creates program headers as instructed by PHDRS linker script command.
 SmallVector<PhdrEntry *, 0> LinkerScript::createPhdrs() {

lld/ELF/Writer.cpp

 // InputSections. As the generation of the content may also alter InputSection
 // addresses we must converge to a fixed point. We do that here. See the comment
 // in Writer<ELFT>::finalizeSections().
 template <class ELFT> void Writer<ELFT>::finalizeAddressDependentContent() {
   llvm::TimeTraceScope timeScope("Finalize address dependent content");
   ThunkCreator tc;
   AArch64Err843419Patcher a64p;
   ARMErr657417Patcher a32p;
-  script->assignAddresses();
+  script->assignAddresses(AF_None);
   // .ARM.exidx and SHF_LINK_ORDER do not require precise addresses, but they
   // do require the relative addresses of OutputSections because linker scripts
   // can assign Virtual Addresses to OutputSections that are not monotonically
   // increasing.
   for (Partition &part : partitions)
     finalizeSynthetic(part.armExidx.get());
   resolveShfLinkOrder();
 
for (;;) {
     if (changed && pass >= 30) {
       error(target->needsThunks ? "thunk creation not converged"
                                 : "relaxation not converged");
       break;
     }
 
     if (config->fixCortexA53Errata843419) {
       if (changed)
-        script->assignAddresses();
+        script->assignAddresses(AF_None);
       changed |= a64p.createFixes();
     }
     if (config->fixCortexA8) {
       if (changed)
-        script->assignAddresses();
+        script->assignAddresses(AF_None);
       changed |= a32p.createFixes();
     }
 
     if (in.mipsGot)
       in.mipsGot->updateAllocSize();
 
     for (Partition &part : partitions) {
       changed |= part.relaDyn->updateAllocSize();
       if (part.relrDyn)
         changed |= part.relrDyn->updateAllocSize();
     }
 
-    const Defined *changedSym = script->assignAddresses();
+    const Defined *changedSym = script->assignAddresses(AF_None);
     if (!changed) {
       // Some symbols may be dependent on section addresses. When we break the
       // loop, the symbol values are finalized because a previous
       // assignAddresses() finalized section addresses.
       if (!changedSym)
         break;
       if (++assignPasses == 5) {
         errorOrWarn("assignment to symbol " + toString(*changedSym) +
                     " does not converge");
         break;
       }
     }
   }
+
+  script->assignAddresses(AF_FinalPass);
+
   if (!config->relocatable && config->emachine == EM_RISCV)
     riscvFinalizeRelax(pass);
 
   if (config->relocatable)
     for (OutputSection *sec : outputSections)
       sec->addr = 0;
 
   // If addrExpr is set, the address may not be a multiple of the alignment.

 // If basic block sections exist, there are opportunities to delete fall thru
 // jumps and shrink jump instructions after basic block reordering.  This
 // relaxation pass does that.  It is only enabled when --optimize-bb-jumps
 // option is used.
 template <class ELFT> void Writer<ELFT>::optimizeBasicBlockJumps() {
   assert(config->optimizeBBJumps);
   SmallVector<InputSection *, 0> storage;
 
-  script->assignAddresses();
+  script->assignAddresses(AF_None);
   // For every output section that has executable input sections, this
   // does the following:
   //   1. Deletes all direct jump instructions in input sections that
   //      jump to the following section as it is not required.
   //   2. If there are two consecutive jump instructions, it checks
   //      if they can be flipped and one can be deleted.
   for (OutputSection *osec : outputSections) {
     if (!(osec->flags & SHF_EXECINSTR))
       continue;
     ArrayRef<InputSection *> sections = getInputSections(*osec, storage);
     size_t numDeleted = 0;
     // Delete all fall through jump instructions.  Also, check if two
     // consecutive jump instructions can be flipped so that a fall
     // through jmp instruction can be deleted.
     for (size_t i = 0, e = sections.size(); i != e; ++i) {
       InputSection *next = i + 1 < sections.size() ? sections[i + 1] : nullptr;
       InputSection &sec = *sections[i];
       numDeleted += target->deleteFallThruJmpInsn(sec, sec.file, next);
     }
     if (numDeleted > 0) {
-      script->assignAddresses();
+      script->assignAddresses(AF_None);
       LLVM_DEBUG(llvm::dbgs()
                  << "Removing " << numDeleted << " fall through jumps\n");
     }
   }
 
   fixSymbolsAfterShrinking();
 
   for (OutputSection *osec : outputSections)

lld/test/ELF/riscv-relax-call-region-overflow.s

+# REQUIRES: riscv
+
+# RUN: rm -rf %t && split-file %s %t && cd %t
+
+## Check that relaxation prevents region overflow
+
+# RUN: llvm-mc -filetype=obj -triple=riscv32 -mattr=+c,+relax a.s -o a.32c.o
+# RUN: llvm-mc -filetype=obj -triple=riscv32 -mattr=+c,+relax b.s -o b.32c.o
+# RUN: ld.lld -T lds a.32c.o b.32c.o -o 32c
+# RUN: llvm-objdump --section-headers 32c | FileCheck %s --check-prefixes=RELAX_SECTIONS
+# RELAX_SECTIONS:   1 .text         0000000a 00000000 TEXT
+
+## Check that we still overflow with relaxation disabled
+
+# RUN: not ld.lld -T lds a.32c.o b.32c.o --no-relax -o /dev/null 2>&1 | FileCheck --check-prefix=ERR0 %s
+# ERR0: ld.lld: error: section '.text' will not fit in region 'ROM'
+
+#--- a.s
+.global _start
+_start:
+  # These calls can be relaxed to be much smaller, enough to fit within the
+  # tiny ROM region
+  call bar
+  call bar
+  call bar
+  call bar
+
+#--- b.s
+.global bar
+bar:
+  ret
+
+#--- lds
+MEMORY {
+  ROM (rx) : ORIGIN = 0, LENGTH = 12
+}
+SECTIONS {
+  .text 0x00000 : { *(.text) } > ROM
+}