[ELF] - Assign absolute values in linkerscript correctly #2.

[grimar]

Summary

This is PR32664. Current LLD behavior - segfault.

I found 2 ways of solving the issue.
One of them is this patch, second is D32173.

Problem itself is next. Imagine next script and code:
SECTIONS { . = 0x1000; aaa = ABSOLUTE(foo - 1); .text : { *(.text*) } };

.section .text
.globl foo
foo:
nop

At the moment of assignment to aaa we do not know the address of output section .text.
We are unable to evaluate the absolute value aaa properly therefore.

This patch suggests to add CanCalculateAbs field to expression class and AddrSet flag
to OutputSection. Then when expression evaluated we find if it can be evaluated or not.
When not (section address was not yet assigned), symbol assignment operation is delayed
and pushed to queue. Each time script produces new output section, delayed operations are proccessed.

[grimar]

• Rebased.

[grimar]

D32793 was landed instead.

ELF/LinkerScript.h

 class OutputSectionFactory;
 class InputSectionBase;
 class SectionBase;
 
 struct ExprValue {
   SectionBase *Sec;
   uint64_t Val;
   bool ForceAbsolute;
+  bool CanCalculateAbs = true;
 
   ExprValue(SectionBase *Sec, bool ForceAbsolute, uint64_t Val)
       : Sec(Sec), Val(Val), ForceAbsolute(ForceAbsolute) {}
   ExprValue(SectionBase *Sec, uint64_t Val) : ExprValue(Sec, false, Val) {}
   ExprValue(uint64_t Val) : ExprValue(nullptr, Val) {}
   bool isAbsolute() const { return ForceAbsolute || Sec == nullptr; }
   uint64_t getValue() const;
   uint64_t getSecAddr() const;
struct ScriptConfiguration {
   llvm::DenseMap<llvm::StringRef, MemoryRegion> MemoryRegions;
 
   // A list of symbols referenced by the script.
   std::vector<llvm::StringRef> ReferencedSymbols;
 };
 
 class LinkerScript {
 protected:
-  void assignSymbol(SymbolAssignment *Cmd, bool InSec);
+  bool assignSymbol(SymbolAssignment *Cmd, bool InSec);
   void setDot(Expr E, const Twine &Loc, bool InSec);
 
   std::vector<InputSectionBase *>
   computeInputSections(const InputSectionDescription *);
 
   std::vector<InputSectionBase *>
   createInputSectionList(OutputSectionCommand &Cmd);
 
   std::vector<size_t> getPhdrIndices(StringRef SectionName);
   size_t getPhdrIndex(const Twine &Loc, StringRef PhdrName);
 
   MemoryRegion *findMemoryRegion(OutputSectionCommand *Cmd);
 
   void switchTo(OutputSection *Sec);
   void flush();
   void output(InputSection *Sec);
   void process(BaseCommand &Base);
 
+  void assignDelayedSymbols();
+
   OutputSection *Aether;
   bool ErrorOnMissingSection = false;
 
   uint64_t Dot;
   uint64_t ThreadBssOffset = 0;
 
   std::function<uint64_t()> LMAOffset;
   OutputSection *CurOutSec = nullptr;
   MemoryRegion *CurMemRegion = nullptr;
 
   llvm::DenseSet<OutputSection *> AlreadyOutputOS;
   llvm::DenseSet<InputSectionBase *> AlreadyOutputIS;
 
+  std::vector<SymbolAssignment *> DelayedAssignments;
+
 public:
   bool hasPhdrsCommands() { return !Opt.PhdrsCommands.empty(); }
   uint64_t getDot() { return Dot; }
   OutputSection *getOutputSection(const Twine &Loc, StringRef S);
   uint64_t getOutputSectionSize(StringRef S);
   void discard(ArrayRef<InputSectionBase *> V);
 
   ExprValue getSymbolValue(const Twine &Loc, StringRef S);

ELF/LinkerScript.cpp

std::tie(Sym, std::ignore) = Symtab<ELFT>::X->insert(
       /*File*/ nullptr);
   Sym->Binding = STB_GLOBAL;
   ExprValue Value = Cmd->Expression();
   SectionBase *Sec = Value.isAbsolute() ? nullptr : Value.Sec;
 
   // We want to set symbol values early if we can. This allows us to use symbols
   // as variables in linker scripts. Doing so allows us to write expressions
   // like this: `alignment = 16; . = ALIGN(., alignment)`
-  uint64_t SymValue = Value.isAbsolute() ? Value.getValue() : 0;
+  uint64_t SymValue = Value.isAbsolute() ? Value.Val : 0;
   replaceBody<DefinedRegular>(Sym, Cmd->Name, /*IsLocal=*/false, Visibility,
                               STT_NOTYPE, SymValue, 0, Sec, nullptr);
   return Sym->body();
 }
 
 OutputSection *LinkerScript::getOutputSection(const Twine &Loc,
                                               StringRef Name) {
   for (OutputSection *Sec : *OutputSections)
void LinkerScript::setDot(Expr E, const Twine &Loc, bool InSec) {
   // Update to location counter means update to section size.
   if (InSec)
     CurOutSec->Size = Dot - CurOutSec->Addr;
 }
 
 // Sets value of a symbol. Two kinds of symbols are processed: synthetic
 // symbols, whose value is an offset from beginning of section and regular
 // symbols whose value is absolute.
-void LinkerScript::assignSymbol(SymbolAssignment *Cmd, bool InSec) {
+bool LinkerScript::assignSymbol(SymbolAssignment *Cmd, bool InSec) {
   if (Cmd->Name == ".") {
     setDot(Cmd->Expression, Cmd->Location, InSec);
-    return;
+    return true;
   }
 
   if (!Cmd->Sym)
-    return;
+    return true;
 
   auto *Sym = cast<DefinedRegular>(Cmd->Sym);
   ExprValue V = Cmd->Expression();
+
   if (V.isAbsolute()) {
+    if (!V.CanCalculateAbs)
+      return false;
     Sym->Value = V.getValue();
   } else {
     Sym->Section = V.Sec;
     if (Sym->Section->Flags & SHF_ALLOC)
       Sym->Value = V.Val;
     else
       Sym->Value = V.getValue();
   }
+  return true;
 }
 
 static SymbolBody *findSymbol(StringRef S) {
   switch (Config->EKind) {
   case ELF32LEKind:
     return Symtab<ELF32LE>::X->find(S);
   case ELF32BEKind:
     return Symtab<ELF32BE>::X->find(S);
if (CurOutSec == Sec)
     return;
   if (AlreadyOutputOS.count(Sec))
     return;
 
   CurOutSec = Sec;
 
   Dot = alignTo(Dot, CurOutSec->Alignment);
   CurOutSec->Addr = isTbss(CurOutSec) ? Dot + ThreadBssOffset : Dot;
+  CurOutSec->AddrSet = true;
 
   // If neither AT nor AT> is specified for an allocatable section, the linker
   // will set the LMA such that the difference between VMA and LMA for the
   // section is the same as the preceding output section in the same region
   // https://sourceware.org/binutils/docs-2.20/ld/Output-Section-LMA.html
   if (LMAOffset)
     CurOutSec->LMAOffset = LMAOffset();
 }
void LinkerScript::processNonSectionCommands() {
   for (BaseCommand *Base : Opt.Commands) {
     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base))
       assignSymbol(Cmd, false);
     else if (auto *Cmd = dyn_cast<AssertCommand>(Base))
       Cmd->Expression();
   }
 }
 
+void LinkerScript::assignDelayedSymbols() {
+  std::vector<SymbolAssignment *> V;
+  for (SymbolAssignment *Cmd : DelayedAssignments)
+    if (!assignSymbol(Cmd, false))
+      V.push_back(Cmd);
+  DelayedAssignments.swap(V);
+}
+
 void LinkerScript::assignAddresses(std::vector<PhdrEntry> &Phdrs) {
   // Assign addresses as instructed by linker script SECTIONS sub-commands.
   Dot = 0;
   ErrorOnMissingSection = true;
   switchTo(Aether);
 
   for (BaseCommand *Base : Opt.Commands) {
     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
-      assignSymbol(Cmd, false);
+      if (!assignSymbol(Cmd, false))
+        DelayedAssignments.push_back(Cmd);
       continue;
     }
 
     if (auto *Cmd = dyn_cast<AssertCommand>(Base)) {
       Cmd->Expression();
       continue;
     }
 
     auto *Cmd = cast<OutputSectionCommand>(Base);
     assignOffsets(Cmd);
+
+    assignDelayedSymbols();
   }
 
   uint64_t MinVA = std::numeric_limits<uint64_t>::max();
   for (OutputSection *Sec : *OutputSections) {
     if (Sec->Flags & SHF_ALLOC)
       MinVA = std::min<uint64_t>(MinVA, Sec->Addr);
     else
       Sec->Addr = 0;

 int LinkerScript::getSectionIndex(StringRef Name) {
   for (int I = 0, E = Opt.Commands.size(); I != E; ++I)
     if (auto *Cmd = dyn_cast<OutputSectionCommand>(Opt.Commands[I]))
       if (Cmd->Name == Name)
         return I;
   return INT_MAX;
 }
 
+// Sometimes expression can not be calculated. For example absolute expressions
+// that depends on address of output section which was not assigned yet.
+// Function helps find if we can evaluate absolute expression value or not.
+static bool canCalcSymValue(DefinedRegular *D,
+                            ArrayRef<SymbolAssignment *> Delayed) {
+  // If symbol evaluation was delayed previously, we are unable to
+  // calculate expression that depends on not yet evaluated symbol value.
+  for (SymbolAssignment *Cmd : Delayed)
+    if (Cmd->Sym == D)
+      return false;
+
+  // Absolute expressions are always calculatable.
+  if (!D->Section)
+    return true;
+
+  // We can calculate symbol absolute value if it's input section attached
+  // to output section and output section has address assigned.
+  OutputSection *OutSec = D->Section->getOutputSection();
+  return OutSec && OutSec->AddrSet;
+}
+
 ExprValue LinkerScript::getSymbolValue(const Twine &Loc, StringRef S) {
   if (S == ".")
     return {CurOutSec, Dot - CurOutSec->Addr};
   if (SymbolBody *B = findSymbol(S)) {
-    if (auto *D = dyn_cast<DefinedRegular>(B))
-      return {D->Section, D->Value};
+    if (auto *D = dyn_cast<DefinedRegular>(B)) {
+      ExprValue E = {D->Section, D->Value};
+      E.CanCalculateAbs = canCalcSymValue(D, DelayedAssignments);
+      return E;
+    }
     if (auto *C = dyn_cast<DefinedCommon>(B))
       return {InX::Common, C->Offset};
   }
   error(Loc + ": symbol not found: " + S);
   return 0;
 }
 
 bool LinkerScript::isDefined(StringRef S) { return findSymbol(S) != nullptr; }

ELF/OutputSections.h

public:
 
   // The following fields correspond to Elf_Shdr members.
   uint64_t Size = 0;
   uint64_t Offset = 0;
   uint64_t LMAOffset = 0;
   uint64_t Addr = 0;
   uint32_t ShName = 0;
 
+  // Makes sense when linkerscript is envolved. Flag is set to true when
+  // script assigns Addr field of section. And that means we can use section
+  // address in expressions.
+  bool AddrSet = false;
+
   void addSection(InputSection *S);
   void sort(std::function<int(InputSectionBase *S)> Order);
   void sortInitFini();
   void sortCtorsDtors();
   uint32_t getFiller();
   template <class ELFT> void writeTo(uint8_t *Buf);
   template <class ELFT> void finalize();
   template <class ELFT> void maybeCompress();

ELF/ScriptParser.cpp

static void moveAbsRight(ExprValue &A, ExprValue &B) {
   if (A.isAbsolute())
     std::swap(A, B);
   if (!B.isAbsolute())
     error("At least one side of the expression must be absolute");
 }
 
 static ExprValue add(ExprValue A, ExprValue B) {
   moveAbsRight(A, B);
-  return {A.Sec, A.ForceAbsolute, A.Val + B.getValue()};
+  ExprValue E = {A.Sec, A.ForceAbsolute, A.Val + B.getValue()};
+  E.CanCalculateAbs = A.CanCalculateAbs && B.CanCalculateAbs;
+  return E;
 }
 
 static ExprValue sub(ExprValue A, ExprValue B) {
-  return {A.Sec, A.Val - B.getValue()};
+  ExprValue E = {A.Sec, A.Val - B.getValue()};
+  E.CanCalculateAbs = A.CanCalculateAbs && B.CanCalculateAbs;
+  return E;
 }
 
 static ExprValue mul(ExprValue A, ExprValue B) {
   return A.getValue() * B.getValue();
 }
 
 static ExprValue div(ExprValue A, ExprValue B) {
   if (uint64_t BV = B.getValue())

ELF/Writer.cpp

if (HeaderSize > Min) {
     return false;
   }
   Min = alignDown(Min - HeaderSize, Config->MaxPageSize);
 
   if (!Script->Opt.HasSections)
     Config->ImageBase = Min = std::min(Min, Config->ImageBase);
 
   Out::ElfHeader->Addr = Min;
+  Out::ElfHeader->AddrSet = true;
   Out::ProgramHeaders->Addr = Min + Out::ElfHeader->Size;
+  Out::ProgramHeaders->AddrSet = true;
 
   if (Script->hasPhdrsCommands())
     return true;
 
   if (FirstPTLoad->First)
     for (OutputSection *Sec : OutputSections)
       if (Sec->FirstInPtLoad == FirstPTLoad->First)
         Sec->FirstInPtLoad = Out::ElfHeader;
if (needsPtLoad(Sec)) {
       Sec->Addr = VA;
       VA += Sec->Size;
     } else if (Sec->Flags & SHF_TLS && Sec->Type == SHT_NOBITS) {
       uint64_t TVA = VA + ThreadBssOffset;
       TVA = alignTo(TVA, Alignment);
       Sec->Addr = TVA;
       ThreadBssOffset = TVA - VA + Sec->Size;
     }
+
+    Sec->AddrSet = true;
   }
 }
 
 // Adjusts the file alignment for a given output section and returns
 // its new file offset. The file offset must be the same with its
 // virtual address (modulo the page size) so that the loader can load
 // executables without any address adjustment.
 static uint64_t getFileAlignment(uint64_t Off, OutputSection *Sec) {

test/ELF/linkerscript/early-assign-symbol.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
+# RUN: echo "SECTIONS { . = 0x1000;                               \
+# RUN:                  aaa = ABSOLUTE(foo - 1);                  \
+# RUN:                  bbb = aaa + 2;                            \
+# RUN:                  .text : { *(.text*) } };                  \
+# RUN:                  ccc = ABSOLUTE(foo - 1);                  \
+# RUN:                  ddd = ccc + 2;" > %t.script
+# RUN: ld.lld -o %t --script %t.script %t.o
+# RUN: llvm-objdump -t %t | FileCheck %s
+
+# CHECK: SYMBOL TABLE:
+# CHECK: 0000000000000000 *UND* 00000000
+# CHECK: 0000000000001000 .text 00000000 foo
+# CHECK: 0000000000000fff *ABS* 00000000 aaa
+# CHECK: 0000000000000fff *ABS* 00000000 ccc
+# CHECK: 0000000000001001 *ABS* 00000000 bbb
+# CHECK: 0000000000001001 *ABS* 00000000 ddd
+
+.section .text
+.globl foo
+foo:
+ nop