[ELF] Make LinkerScript::assignAddresses iterative

[MaskRay]

Summary

PR42990. For SECTIONS { b = a; . = 0xff00 + (a >> 8); a = .; },
we currently set st_value(a)=0xff00 while st_value(b)=0xffff.

The following call tree demonstrates the problem:

link<ELF64LE>(Args);
  Script->declareSymbols(); // insert a and b as absolute Defined
  Writer<ELFT>().run();
    Script->processSectionCommands();
      addSymbol(cmd);       // a and b are re-inserted. LinkerScript::getSymbolValue
                            // is lazily called by subsequent evaluation
    finalizeSections();
      forEachRelSec(scanRelocations<ELFT>);
        processRelocAux     // another problem PR42506, not affected by this patch
      finalizeAddressDependentContent(); // loop executed once
        script->assignAddresses(); // a = 0, b = 0xff00
    script->assignAddresses(); // a = 0xff00, _end = 0xffff

We need another assignAddresses() to finalize the value of a.

This patch

1. modifies assignAddress() to track the original section/value of each symbol and return a symbol whose section/value has changed.
2. moves the post-finalizeSections assignAddress() inside the loop of finalizeAddressDependentContent() and makes it iterative. Symbol assignment may not converge so we make a few attempts before bailing out.

Note, assignAddresses() must be called at least twice. The penultimate
call finalized section addresses while the last finalized symbol values.
It is somewhat obscure because there was no comment.
linkerscript/addr-zero.test tests this.

[peter.smith]

I think that this is close. I've got some concerns about the interaction of convergence limits, and it may be worth investigating if it is possible to make a separate symbol update pass that runs after addresses have stabilized.

I think it will be worth adding a test to make sure that the bail out does indeed occur. Something like:

sym1 = sym2
sym2 = sym3
sym3 = sym4
sym4 = sym5
sym6 = sym7
sym8 = .

I'm happy to work on a thunk creation test that takes quite a few iterations to converge.

ELF/Writer.cpp

1571 ↗

(On Diff #215346)

The thunks code already has a converge limit of 10, I think it would be possible to create a test case that had a single assignment say sym = . that was after a code section that would vary in size due to Thunk creation. If the code section converged within 10 but not within 5 then we'd get an error. I think if the symbol convergence test is within this loop then we should probably extract the convergence test out of ThunkCreation, or at least have some way of synchronizing all the convergence limits.

Writing a thunk test that doesn't converge isn't difficult, writing one that takes many iterations to convergence is somewhat tedious. I can help write one as I've done a few before.

1595 ↗

(On Diff #215346)

To follow on from the previous comment about convergence errors in Thunks, if we choose to keep the convergence tests separate so we know which part isn't converging (if that is even possible) then it might be worth moving the tries and error message into script and assignAddresses() to keep this loop clean.

1602 ↗

(On Diff #215346)

An argument could be made that testing for convergence of symbols could/should be done after the final addresses have stabilised. I don't think that there is a legal linker script that could be made where assigning to symbols in a linker script should affect the convergence of thunks, patches and partitions. Doing the symbol assignment with stable addresses would avoid the clashing convergence limit problem.

My initial thought was to see if just a symbol assignment update could be run here, without going through the complexity of assignAddresses() but that would definitely need some thought.

[MaskRay]

ELF/Writer.cpp

1571 ↗

(On Diff #215346)

This is a bit different. The return value of script->assignAddresses(); does not affect changed, i.e. before thunks converge (changed becomes false) tries should not decrease.

script->assignAddresses is executed at least twice, without or with this patch. This is a bit awkward, but if I change the logic here to:

for (;;)
  assignAddresses();
  createThunks();
  if (!changed) break;

test/ELF/linkerscript/addr-zero.test added by @grimar's D55550 will break.

foo = ADDR(.text) - ABSOLUTE(ADDR(.text));

Ideally we don't have to call assignAddresses twice.

Writing a thunk test that doesn't converge isn't difficult, writing one that takes many iterations to convergence is somewhat tedious.

Yes, a test involving both non-trivial symbol assignment and non-trivial thunk will be very useful... Thanks in advance.

[MaskRay]

Add a non-convergence test expr-converge2.test and improve expr-converge.test

[MaskRay]

Improve test
Add a comment why the two calls of assignAddresses() are written this way.

[MaskRay]

bug fix: return sym; -> changed = sym;

[MaskRay]

Investigated a bit how ld.bfd works.

SECTIONS {
  . = 0x1000;
  a = b + 1; b = c + 1; c = d + 1; d = e + 1; e = f + 1; f = g + 1; g = h + 1; h = .;
}
// ld/ld-new -T a.lds a.o -o a
// undefined symbol `b' referenced in expression

SECTIONS {
  . = 0x1000;
  a = b + 1; b = c + 1; c = d + 1; d = e + 1; e = f + 1; f = g + 1; g = .;
}
// st_value(a) is incorrect 6, not 0x1006.

// st_value(a) is correct (0x1005) with one less variable.

In either case, lang_do_assignments ran at least 3 times.

• lang_do_assignments (lang_mark_phase_enum); // in ld/ldlang.c:lang_process
• lang_do_assignments (lang_assigning_phase_enum); // in ld/ldlang.c:lang_relax_sections
• lang_do_assignments (lang_final_phase_enum); // in ld/ldlang.c:lang_process

The initial 3 calls allow it to compute a slightly longer chain, though a new lang_do_assignments (lang_assigning_phase_enum); only allows it to compute the case with one more variable. I observe that the aarch64 port calls lang_do_assignments 4 times. This is because ld/emultempl/elf-generic.em:gld${EMULATION_NAME}_map_segments (bfd_boolean need_layout) calls lang_relax_sections (need_layout); twice.

In lang_relax_sections, the symbol assignment phase is followed by lang_size_sections. Our script->assignAddresses() should match its behavior well.

void
lang_relax_sections (bfd_boolean need_layout)
{
...
  if (need_layout)
    {
      /* Final extra sizing to report errors.  */
      lang_do_assignments (lang_assigning_phase_enum);
      lang_reset_memory_regions ();
      lang_size_sections (NULL, TRUE);
    }
}

In finalizeAddressDependentContent(), we could extract the symbol assignment iteration and do it separately after the layout is fixed, but that would require more code.

[peter.smith]

I've created D66346 which maxes out the permitted Thunk convergence limit. I've done it as Arm rather than AArch64 as the range limits are lower on Arm. This should be sufficient to test that if there is any interaction between convergence limits. Apologies for the delay in putting it together.

[MaskRay]

Change tests to adapt D66346

[ruiu]

ELF/Writer.cpp

1578 ↗

(On Diff #215626)

I believe this line is executed only when you give pathetic object files to the linker, but we still probably have to use error to make it work better for the embedding use case.

[MaskRay]

• fatal("thunk creation not converged");

+ error("thunk creation not converged");
+ break;

[peter.smith]

Thanks for the update. Have been thinking in the back of my mind if there were any other way of solving the problem without needing to iterate. The only thing I can think of right now is some kind of analysis that, for want of a better word, topologically sorts expressions so that there are no forward references, with an error message if this isn't possible. This could get complicated as there is limited scope to move or reorder assignments in OutputSections. Other than that I've not got any more comments at the moment.

ELF/LinkerScript.cpp

1065 ↗

(On Diff #215830)

It might be worth extracting this and the check below into functions. Something like:

oldValues = getSymbolAssignmentValues(sectionCommands);
...
return findChangedSymbol(oldValues);

Not a strong opinion though.

ELF/Writer.cpp

1570 ↗

(On Diff #215830)

This comment won't be true anymore, depending on linker scripts.

[MaskRay]

Delete a stale comment
Extract out getSymbolAssignmentValues

[MaskRay]

In D66279#1634954, @peter.smith wrote:

Thanks for the update. Have been thinking in the back of my mind if there were any other way of solving the problem without needing to iterate. The only thing I can think of right now is some kind of analysis that, for want of a better word, topologically sorts expressions so that there are no forward references, with an error message if this isn't possible. This could get complicated as there is limited scope to move or reorder assignments in OutputSections. Other than that I've not got any more comments at the moment.

Unfortunately linker scripts are not in a single static assignment form... = and += can appear multiple times. Such analysis will be difficult. According to my experiments (see prior comments), ld.bfd's evaluation strategy is quite similar to: run assignment statements one by one, but repeat a few times, where the repetition count depends on layout convergence. It doesn't wait for symbol assignments to converge, but it evaluates the assignment statements more than we current do. Thus it can correctly evaluate some simple forward declaration forms. I think the approach we use in this patch should capture its strategy quite well. This is probably sufficient for most forward declarations we may encounter in practice.

ELF/LinkerScript.cpp

1065 ↗

(On Diff #215830)

I'll do:

oldValues = getSymbolAssignmentValues(sectionCommands);
...
for (auto &it : oldValues) { /// this part is not too complex now, so i'll inline it
  ...
}
return changed;

[MaskRay]

🎡Ready to roll!

[peter.smith]

I'm happy with this as it stands. It should help prevent problems coming from alterations to the linux kernel's linker script and also help others migrating from ld.bfd. With luck we'll be able to build on this to fix the symbol type problem in https://bugs.llvm.org/show_bug.cgi?id=42506

[MaskRay]

@ruiu 🎡

[MaskRay]

🤔

[ruiu]

LGTM

ELF/LinkerScript.cpp

1052 ↗

(On Diff #215853)

This needs a function comment.

[MaskRay]

Move getSymbolAssignmentValues above because it might be used by processSymbolAssignments in the future.

add a function-level comment

Add getChangedSymbolAssignment

[MaskRay]

vector -> const vector &

lld/trunk/ELF/LinkerScript.h

public:
   void addOrphanSections();
   void adjustSectionsBeforeSorting();
   void adjustSectionsAfterSorting();
 
   std::vector<PhdrEntry *> createPhdrs();
   bool needsInterpSection();
 
   bool shouldKeep(InputSectionBase *s);
-  void assignAddresses();
+  const Defined *assignAddresses();
   void allocateHeaders(std::vector<PhdrEntry *> &phdrs);
   void processSectionCommands();
   void declareSymbols();
 
   // Used to handle INSERT AFTER statements.
   void processInsertCommands();
 
   // SECTIONS command list.

lld/trunk/ELF/LinkerScript.cpp

static void declareSymbol(SymbolAssignment *cmd) {
   sym->mergeProperties(newSym);
   sym->replace(newSym);
 
   cmd->sym = cast<Defined>(sym);
   cmd->provide = false;
   sym->scriptDefined = true;
 }
 
+using SymbolAssignmentMap =
+    DenseMap<const Defined *, std::pair<SectionBase *, uint64_t>>;
+
+// Collect section/value pairs of linker-script-defined symbols. This is used to
+// check whether symbol values converge.
+static SymbolAssignmentMap
+getSymbolAssignmentValues(const std::vector<BaseCommand *> &sectionCommands) {
+  SymbolAssignmentMap ret;
+  for (BaseCommand *base : sectionCommands) {
+    if (auto *cmd = dyn_cast<SymbolAssignment>(base)) {
+      if (cmd->sym) // sym is nullptr for dot.
+        ret.try_emplace(cmd->sym,
+                        std::make_pair(cmd->sym->section, cmd->sym->value));
+      continue;
+    }
+    for (BaseCommand *sub_base : cast<OutputSection>(base)->sectionCommands)
+      if (auto *cmd = dyn_cast<SymbolAssignment>(sub_base))
+        if (cmd->sym)
+          ret.try_emplace(cmd->sym,
+                          std::make_pair(cmd->sym->section, cmd->sym->value));
+  }
+  return ret;
+}
+
+// Returns the lexicographical smallest (for determinism) Defined whose
+// section/value has changed.
+static const Defined *
+getChangedSymbolAssignment(const SymbolAssignmentMap &oldValues) {
+  const Defined *changed = nullptr;
+  for (auto &it : oldValues) {
+    const Defined *sym = it.first;
+    if (std::make_pair(sym->section, sym->value) != it.second &&
+        (!changed || sym->getName() < changed->getName()))
+      changed = sym;
+  }
+  return changed;
+}
+
 // This method is used to handle INSERT AFTER statement. Here we rebuild
 // the list of script commands to mix sections inserted into.
 void LinkerScript::processInsertCommands() {
   std::vector<BaseCommand *> v;
   auto insert = [&](std::vector<BaseCommand *> &from) {
     v.insert(v.end(), from.begin(), from.end());
     from.clear();
   };
static uint64_t getInitialDot() {
   for (auto &kv : config->sectionStartMap)
     startAddr = std::min(startAddr, kv.second);
   return std::min(startAddr, target->getImageBase() + elf::getHeaderSize());
 }
 
 // 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.
-void LinkerScript::assignAddresses() {
+// Returns a symbol that has changed its section or value, or nullptr if no
+// symbol has changed.
+const Defined *LinkerScript::assignAddresses() {
   dot = getInitialDot();
 
   auto deleter = std::make_unique<AddressState>();
   ctx = deleter.get();
   errorOnMissingSection = true;
   switchTo(aether);
 
+  SymbolAssignmentMap oldValues = getSymbolAssignmentValues(sectionCommands);
   for (BaseCommand *base : sectionCommands) {
     if (auto *cmd = dyn_cast<SymbolAssignment>(base)) {
       cmd->addr = dot;
       assignSymbol(cmd, false);
       cmd->size = dot - cmd->addr;
       continue;
     }
     assignOffsets(cast<OutputSection>(base));
   }
+
   ctx = nullptr;
+  return getChangedSymbolAssignment(oldValues);
 }
 
 // Creates program headers as instructed by PHDRS linker script command.
 std::vector<PhdrEntry *> LinkerScript::createPhdrs() {
   std::vector<PhdrEntry *> ret;
 
   // Process PHDRS and FILEHDR keywords because they are not
   // real output sections and cannot be added in the following loop.

lld/trunk/ELF/Relocations.cpp

 // ARM, then any future change in offset between caller and callee risks a
 // relocation out of range error.
 bool ThunkCreator::createThunks(ArrayRef<OutputSection *> outputSections) {
   bool addressesChanged = false;
 
   if (pass == 0 && target->getThunkSectionSpacing())
     createInitialThunkSections(outputSections);
 
-  // With Thunk Size much smaller than branch range we expect to
-  // converge quickly; if we get to 10 something has gone wrong.
-  if (pass == 10)
-    fatal("thunk creation not converged");
-
   // Create all the Thunks and insert them into synthetic ThunkSections. The
   // ThunkSections are later inserted back into InputSectionDescriptions.
   // We separate the creation of ThunkSections from the insertion of the
   // ThunkSections as ThunkSections are not always inserted into the same
   // InputSectionDescription as the caller.
   forEachInputSectionDescription(
       outputSections, [&](OutputSection *os, InputSectionDescription *isd) {
         for (InputSection *isec : isd->sections)

lld/trunk/ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::run() {
   // completes section contents. For example, we need to add strings
   // to the string table, and add entries to .got and .plt.
   // finalizeSections does that.
   finalizeSections();
   checkExecuteOnly();
   if (errorCount())
     return;
 
-  script->assignAddresses();
-
   // If -compressed-debug-sections is specified, we need to compress
   // .debug_* sections. Do it right now because it changes the size of
   // output sections.
   for (OutputSection *sec : outputSections)
     sec->maybeCompress<ELFT>();
 
   script->allocateHeaders(mainPart->phdrs);
 

 
 // We need to generate and finalize the content that depends on the address of
 // 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() {
   ThunkCreator tc;
   AArch64Err843419Patcher a64p;
+  script->assignAddresses();
 
-  // For some targets, like x86, this loop iterates only once.
+  int assignPasses = 0;
   for (;;) {
-    bool changed = false;
+    bool changed = target->needsThunks && tc.createThunks(outputSections);
 
-    script->assignAddresses();
-
-    if (target->needsThunks)
-      changed |= tc.createThunks(outputSections);
+    // With Thunk Size much smaller than branch range we expect to
+    // converge quickly; if we get to 10 something has gone wrong.
+    if (changed && tc.pass >= 10) {
+      error("thunk creation not converged");
+      break;
+    }
 
     if (config->fixCortexA53Errata843419) {
       if (changed)
         script->assignAddresses();
       changed |= a64p.createFixes();
     }
 
     if (in.mipsGot)
       in.mipsGot->updateAllocSize();
 
     for (Partition &part : partitions) {
       changed |= part.relaDyn->updateAllocSize();
       if (part.relrDyn)
         changed |= part.relrDyn->updateAllocSize();
     }
 
-    if (!changed)
-      return;
+    const Defined *changedSym = script->assignAddresses();
+    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;
+      }
+    }
   }
 }
 
 static void finalizeSynthetic(SyntheticSection *sec) {
   if (sec && sec->isNeeded() && sec->getParent())
     sec->finalizeContents();
 }
 

lld/trunk/test/ELF/linkerscript/symbol-assign-many-passes.test

+# REQUIRES: aarch64, x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64 /dev/null -o %t.o
+# RUN: ld.lld %t.o -T %s -o %t
+# RUN: llvm-nm %t | FileCheck %s
+
+## AArch64 needs thunks and has different address finalization process, so test
+## it as well.
+# RUN: llvm-mc -filetype=obj -triple=aarch64 /dev/null -o %t.o
+# RUN: ld.lld %t.o -T %s -o %t
+# RUN: llvm-nm %t | FileCheck %s
+
+# CHECK: 0000000000001004 T a
+# CHECK: 0000000000001003 T b
+# CHECK: 0000000000001002 T c
+# CHECK: 0000000000001001 T d
+# CHECK: 0000000000001000 T e
+
+SECTIONS {
+  . = 0x1000;
+  a = b + 1;
+  b = c + 1;
+  c = d + 1;
+  d = e + 1;
+  e = .;
+}

lld/trunk/test/ELF/linkerscript/symbol-assign-many-passes2.test

+# REQUIRES: arm
+# RUN: llvm-mc -arm-add-build-attributes -filetype=obj -triple=armv7a-linux-gnueabihf %S/../arm-thunk-many-passes.s -o %t.o
+# RUN: ld.lld %t.o -T %s -o %t
+# RUN: llvm-nm %t | FileCheck %s
+
+## arm-thunk-many-passes.s is worst case case of thunk generation that takes 9
+## passes to converge. It takes a few more passes to make symbol assignment
+## converge. Test that
+## 1. we don't error that "thunk creation not converged".
+## 2. we check convergence of symbols defined in an output section descriptor.
+
+# CHECK: 01011050 T a
+# CHECK: 0101104f T b
+# CHECK: 0101104e T c
+# CHECK: 0101104d T d
+# CHECK: 0101104c T e
+
+SECTIONS {
+  . = SIZEOF_HEADERS;
+  .text 0x00011000 : {
+    a = b + 1;
+    b = c + 1;
+    c = d + 1;
+    d = e + 1;
+    *(.text);
+  }
+  e = .;
+}

lld/trunk/test/ELF/linkerscript/symbol-assign-not-converge.test

+# REQUIRES: aarch64, x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64 /dev/null -o %t.o
+# RUN: not ld.lld %t.o -T %s -o /dev/null 2>&1 | FileCheck %s
+
+## AArch64 needs thunks and has different address finalization process, so test
+## it as well.
+# RUN: llvm-mc -filetype=obj -triple=aarch64 /dev/null -o %t.o
+# RUN: not ld.lld %t.o -T %s -o /dev/null 2>&1 | FileCheck %s
+
+# CHECK: error: assignment to symbol a does not converge
+
+SECTIONS {
+  . = 0x1000;
+  a = b;
+  b = c;
+  c = d;
+  d = e;
+  e = f;
+  f = .;
+}