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

[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 D32174.

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 handle forced absolute symbols like regular symbols until we assign
all output sections addresses. After that it converts them into absolute.

[ruiu]

Is your example linker script valid for GNU linkers? I'm curious why you noticed this in the first place.

[grimar]

In D32173#730327, @ruiu wrote:

Is your example linker script valid for GNU linkers? I'm curious why you noticed this in the first place.

I noticed that when tried to link linux kernel. It has next script at start:

SECTIONS
{
 . = (0xffffffff80000000 + ALIGN(0x1000000, 0x200000));
 phys_startup_64 = ABSOLUTE(startup_64 - 0xffffffff80000000);
 /* Text and read-only data */
 .text : AT(ADDR(.text) - 0xffffffff80000000) {
.....
  /* bootstrapping code */
  *(.head.text)

Where startup_64 is in .head.text. Currently we segfault, but even with change at LinkerScript.cpp::75 which fixes crash we do
produce wrong symbol value for phys_startup_64.
(we produce 0 - 0xffffffff80000000 == 0x0000000080000000 instead of 0xffffffff81000000 - 0xffffffff80000000 == 0x0000000001000000).

And this patch fixes that I believe.

Linux kernel script for this place is: https://github.com/torvalds/linux/blob/master/arch/x86/kernel/vmlinux.lds.S#L88

[ruiu]

Sorry for the delay. I was on vacation last week.

So, this patch allows you compute absolute symbols addresses lazily. With that, you can create cycles like this.

foo = ABSOLUTE(bar - 0xff);
bar = ABSOLUTE(foo - 0xff);

What do you think it should be handled?

Also, you can create not a cycle but a series of expressions that should be calculated backwards, like this.

foo = ABSOLUTE(bar);
bar = ABSOLUTE(baz);
baz = 0xff;

What do you think about this?

[grimar]

In D32173#736295, @ruiu wrote:

Sorry for the delay. I was on vacation last week.

So, this patch allows you compute absolute symbols addresses lazily. With that, you can create cycles like this.

foo = ABSOLUTE(bar - 0xff);
bar = ABSOLUTE(foo - 0xff);

What do you think it should be handled?

Also, you can create not a cycle but a series of expressions that should be calculated backwards, like this.

foo = ABSOLUTE(bar);
bar = ABSOLUTE(baz);
baz = 0xff;

What do you think about this?

Honestly I think I do not like idea to calculate something absolute for symbol which section did not
get VA assigned yet at all. And I dont like idea to evaluate something lazily too.
I just don't sure how to handle such situations properly, thats why prepared 2 different patches
with approaches I can imagine.

May be we just should produce an error in such cases ? That will be inconsistent behavior
with GNU linkers, but simplifies things.

[grimar]

Comment above should be: "Honestly I think I do not like idea to calculate something..."

[ruiu]

Since this patch doesn't handle the issue in general but just fixes one specific error, I'm inclined to just not to crash when the linker sees this pattern.

[grimar]

In D32173#736989, @ruiu wrote:

Since this patch doesn't handle the issue in general but just fixes one specific error, I'm inclined to just not to crash when the linker sees this pattern.

Sometimes I think its better to crash than produce broken output silently. For this case it would be much harder to find what is wrong with linux kernel if LLD would not crash.
I think it does not make much sense fix crash and keep producing wrong symbol address silently. I would suggest at least to error out in addition.

But what about solution used in D32174 ? I just rebased it and it is free from cycles problems you mentioned and looks solves issue in general.

[ruiu]

What I was trying to say is to make LLD not segfault but fail with an error message.

[grimar]

D32793 was landed instead.

ELF/LinkerScript.h

 #include <functional>
 #include <memory>
 #include <vector>
 
 namespace lld {
 namespace elf {
 
 class DefinedCommon;
+class DefinedRegular;
 class SymbolBody;
 class InputSectionBase;
 class InputSection;
 class OutputSection;
 class OutputSectionFactory;
 class InputSectionBase;
 class SectionBase;
 
protected:
 
   MemoryRegion *findMemoryRegion(OutputSectionCommand *Cmd);
 
   void switchTo(OutputSection *Sec);
   void flush();
   void output(InputSection *Sec);
   void process(BaseCommand &Base);
 
+  void convertForcedAbsoluteSymbols();
+
   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<DefinedRegular *> ForcedAbsoluteSyms;
+
 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::assignSymbol(SymbolAssignment *Cmd, bool InSec) {
   }
 
   if (!Cmd->Sym)
     return;
 
   auto *Sym = cast<DefinedRegular>(Cmd->Sym);
   ExprValue V = Cmd->Expression();
   if (V.isAbsolute()) {
+    // We handle forced absolute symbols as regular until we assign all
+    // output sections addresses. Then we convert such symbols to absolutes.
+    // That is done because some scripts may assign absolute values
+    // earlier than value can be calculated, like:
+    //   aaa = ABSOLUTE(foo - 1);
+    //   .text : { *(.text*) } };
+    // where 'foo' is a symbol in .text and it's absolute value depends
+    // on output section address which is not known during assignment.
+    if (V.ForceAbsolute && V.Sec) {
+      Sym->Section = V.Sec;
+      Sym->Value = V.Val;
+      ForcedAbsoluteSyms.push_back(Sym);
+      return;
+    }
     Sym->Value = V.getValue();
   } else {
     Sym->Section = V.Sec;
     if (Sym->Section->Flags & SHF_ALLOC)
       Sym->Value = V.Val;
     else
       Sym->Value = V.getValue();
   }

 
 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();
   }
+  convertForcedAbsoluteSymbols();
+}
+
+void LinkerScript::convertForcedAbsoluteSymbols() {
+  for (DefinedRegular *DR : ForcedAbsoluteSyms) {
+    DR->Value = DR->Section->getOffset(DR->Value) +
+                DR->Section->getOutputSection()->Addr;
+    DR->Section = nullptr;
+  }
 }
 
 void LinkerScript::assignAddresses(std::vector<PhdrEntry> &Phdrs) {
   // Assign addresses as instructed by linker script SECTIONS sub-commands.
   Dot = 0;
   ErrorOnMissingSection = true;
   switchTo(Aether);
 
void LinkerScript::assignAddresses(std::vector<PhdrEntry> &Phdrs) {
   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;
   }
 
+  convertForcedAbsoluteSymbols();
+
   allocateHeaders(Phdrs, *OutputSections, MinVA);
 }
 
 // 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
int LinkerScript::getSectionIndex(StringRef Name) {
   return INT_MAX;
 }
 
 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};
+      return {D->Section,
+              llvm::find(ForcedAbsoluteSyms, D) != ForcedAbsoluteSyms.end(),
+              D->Value};
     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/ScriptParser.cpp

for (; !Path.empty(); Path = sys::path::parent_path(Path))
     if (sys::fs::equivalent(Config->Sysroot, Path))
       return true;
   return false;
 }
 
 // Some operations only support one non absolute value. Move the
 // absolute one to the right hand side for convenience.
 static void moveAbsRight(ExprValue &A, ExprValue &B) {
-  if (A.isAbsolute())
+  if (A.Sec == nullptr)
     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()};

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