[ELF] - Linkerscript: fix issue with multiple output sections definitions.

[grimar]

Summary

Currently for following script LLD produce broken output silently:

bar : ONLY_IF_RO { *(no_such_section) }
bar : ONLY_IF_RW { *(foo_aw) }
sym1 = SIZEOF(bar); 
sym2 = ADDR(bar);

Values of sym1 and sym2 are zeroes.

That happens because of NameToOutputSection member which currently is a
mapping from name to OutputSection. Though in case above there are two different
output section commands, so I believe it should be a mapping to vector.

Patch changes implementation of mapping what fixes the issue observed.

[grimar]

• Rebased. Ping.

[peter.smith]

If I understand correctly is that there is no restriction on OutputSection name so something like:

bar : { *.bar.1 }
bar : { *.bar.2 }

Would be legal, but not very sensible and a user could just change the name of the second bar. Whereas the case you describe:

bar : ONLY_IF_RO { *(no_such_section) }
bar : ONLY_IF_RW { *(foo_aw) }
sym1 = SIZEOF(bar); 
sym2 = ADDR(bar);

Is useful as it permits a program to get the [base, limit) of an OutputSection that can contain either RO or RW? This would make the added complexity of the change worthwhile?

If I've understood their purpose correctly; I'm not too sure that the forward declarations are a good idea. Recent ld manuals prohibit forward references for many of the builtin functions.

ELF/ScriptParser.cpp

974

If I understand correctly this might create a forward reference to some OutputSection Name that we've not seen yet? I don't think that this is allowed in this case: https://sourceware.org/binutils/docs/ld/Builtin-Functions.html

Return the address (VMA) of the named section. Your script must previously have defined the location of that section.

999

If this is a forward reference then the manual says we should give an error message:

If the section has not been allocated when this is evaluated, the linker will report an error.

1050

The docs don't say anything about forward references for this particular builtin. I think that there is a possibility in creating a cycle in address allocation though with something like . = LOADADDR(forward)

1073

Another case where we are supposed to give an error if there is a forward reference:

If the section has not been allocated when this is evaluated, the linker will report an error.

[grimar]

ELF/ScriptParser.cpp

974

It is actually what original code did already before my change. getOrCreateOutputSection creates forward reference.
We rely on that in our testcases, for example absolute.s has just:
"PROVIDE(foo = 1 + ABSOLUTE(ADDR(.text)));" and expects we can evaluate that. I believe we have the same
behavior as gnu linkers here.

Below you referenced to spec saying that for ALIGNOF "If the section *has not been allocated* when this is evaluated, the linker will report an error.". I think that is how it should say for all commands you mentioned.
We use checkIfExists to verify that section was allocated at the moment when we call evaluation of ADDR or other commands, and for parsing script we create forward references atm.

[ruiu]

Before getting into details, I'd like to ask if such linker script is valid in GNU linkers. Also I wonder how you noticed this.

[grimar]

In D39489#927076, @ruiu wrote:

Before getting into details, I'd like to ask if such linker script is valid in GNU linkers.

Yes, both gold and bfd accepts this script and produce valid result.

Also I wonder how you noticed this.

Just found during review of code that our logic is probably weak here and tried to break it
with the testcase from this patch.

[ruiu]

If this is hypothetical, I wouldn't work this hard to "fix" it.

[grimar]

In D39489#927124, @ruiu wrote:

If this is hypothetical, I wouldn't work this hard to "fix" it.

Its not only fixes the issue. Our current logic of 'createOutputSection' honestly looks very odd for me.
It can depending on conditions:

1. Create and return new output section and remember it in NameToOutputSection.
2. Create and return new output section and don't remember it.
3. Just declare and return previously defined output section.

And It works with name to ouput sections as 1:1 though we know its 1:many semantically.

I believe new logic and naming introduced in this patch is much more clear.
That is what I tried to improve as well here.

[ruiu]

But with this patch the code is longer than before. If it doesn't have any practical benefits, it is probably not a good idea to add more code.

ELF/LinkerScript.h

struct AddressState {
     AddressState();
     uint64_t ThreadBssOffset = 0;
     OutputSection *OutSec = nullptr;
     MemoryRegion *MemRegion = nullptr;
     llvm::DenseMap<const MemoryRegion *, uint64_t> MemRegionOffset;
     std::function<uint64_t()> LMAOffset;
   };
 
-  llvm::DenseMap<StringRef, OutputSection *> NameToOutputSection;
+  llvm::DenseMap<StringRef, std::vector<OutputSection *>> NameToOutputSection;
 
   void addSymbol(SymbolAssignment *Cmd);
   void assignSymbol(SymbolAssignment *Cmd, bool InSec);
   void setDot(Expr E, const Twine &Loc, bool InSec);
 
   std::vector<InputSection *>
   computeInputSections(const InputSectionDescription *,
                        const llvm::DenseMap<SectionBase *, int> &Order);
class LinkerScript final {
   // LinkerScript.
   AddressState *Ctx = nullptr;
 
   OutputSection *Aether;
 
   uint64_t Dot;
 
 public:
-  OutputSection *createOutputSection(StringRef Name, StringRef Location);
-  OutputSection *getOrCreateOutputSection(StringRef Name);
+  void declareOutputSection(StringRef Name);
+  OutputSection *defineOutputSection(StringRef Name, StringRef Location);
+  OutputSection *getOutputSection(StringRef Name);
 
   bool hasPhdrsCommands() { return !PhdrsCommands.empty(); }
   uint64_t getDot() { return Dot; }
   void discard(ArrayRef<InputSection *> V);
 
   ExprValue getSymbolValue(StringRef Name, const Twine &Loc);
 
   void addOrphanSections();

ELF/LinkerScript.cpp

uint64_t ExprValue::getSectionOffset() const {
   // If the alignment is trivial, we don't have to compute the full
   // value to know the offset. This allows this function to succeed in
   // cases where the output section is not yet known.
   if (Alignment == 1)
     return Val;
   return getValue() - getSecAddr();
 }
 
-OutputSection *LinkerScript::createOutputSection(StringRef Name,
+OutputSection *LinkerScript::defineOutputSection(StringRef Name,
                                                  StringRef Location) {
-  OutputSection *&SecRef = NameToOutputSection[Name];
-  OutputSection *Sec;
-  if (SecRef && SecRef->Location.empty()) {
-    // There was a forward reference.
-    Sec = SecRef;
-  } else {
-    Sec = make<OutputSection>(Name, SHT_PROGBITS, 0);
-    if (!SecRef)
-      SecRef = Sec;
+  std::vector<OutputSection *> &V = NameToOutputSection[Name];
+  // If we have no output sections with Name or all sections are already defined,
+  // we should create new section definition. This is used to handle
+  // multiple output section definitions when constraints are used, for example:
+  // bar : ONLY_IF_RO { *(...) }
+  // bar : ONLY_IF_RW { *(...) }
+  if (V.empty() || V.back()->isDefined()) {
+    OutputSection *Sec = make<OutputSection>(Name, SHT_PROGBITS, 0);
+    Sec->Location = Location;
+    V.push_back(Sec);
+    return Sec;
   }
+
+  // When we have forward declaration we should define it and return.
+  OutputSection *Sec = V.back();
   Sec->Location = Location;
   return Sec;
 }
 
-OutputSection *LinkerScript::getOrCreateOutputSection(StringRef Name) {
-  OutputSection *&CmdRef = NameToOutputSection[Name];
-  if (!CmdRef)
-    CmdRef = make<OutputSection>(Name, SHT_PROGBITS, 0);
-  return CmdRef;
+// Returns first live section by Name. Normally only one section should be live.
+// Otherwise commands like SIZEOF(section) will use first alive output section
+// for calculation. Ideally we would like to report an error then, but GNU
+// linkers allow that and we just follow for simplicity.
+OutputSection *LinkerScript::getOutputSection(StringRef Name) {
+  std::vector<OutputSection *> &V = NameToOutputSection[Name];
+  for (OutputSection *Sec : V)
+    if (Sec->Live)
+      return Sec;
+  return V.front();
+}
+
+// Used for creating forward references to output section.
+void LinkerScript::declareOutputSection(StringRef Name) {
+  std::vector<OutputSection *> &V = NameToOutputSection[Name];
+  if (!V.empty())
+    return;
+  V.push_back(make<OutputSection>(Name, SHT_PROGBITS, 0));
 }
 
 void LinkerScript::setDot(Expr E, const Twine &Loc, bool InSec) {
   uint64_t Val = E().getValue();
   if (Val < Dot && InSec)
     error(Loc + ": unable to move location counter backward for: " +
           Ctx->OutSec->Name);
   Dot = Val;
for (BaseCommand *Base : Vec)
     if (auto *Sec = dyn_cast<OutputSection>(Base))
       if (Sec->Name == Name)
         return Sec;
   return nullptr;
 }
 
 static OutputSection *createSection(InputSectionBase *IS,
                                     StringRef OutsecName) {
-  OutputSection *Sec = Script->createOutputSection(OutsecName, "<internal>");
+  OutputSection *Sec = Script->defineOutputSection(OutsecName, "<internal>");
   Sec->addSection(cast<InputSection>(IS));
   return Sec;
 }
 
 static OutputSection *addInputSec(StringMap<OutputSection *> &Map,
                                   InputSectionBase *IS, StringRef OutsecName) {
   // Sections with SHT_GROUP or SHF_GROUP attributes reach here only when the -r
   // option is given. A section with SHT_GROUP defines a "section group", and

ELF/OutputSections.h

static bool classof(const SectionBase *S) {
     return S->kind() == SectionBase::Output;
   }
 
   static bool classof(const BaseCommand *C);
 
   uint64_t getLMA() const { return Addr + LMAOffset; }
   template <typename ELFT> void writeHeaderTo(typename ELFT::Shdr *SHdr);
 
+  // Linker script might create forward declarations for output sections.
+  // This method returns true if section known to have definition.
+  bool isDefined() { return !Location.empty(); }
+
   unsigned SectionIndex;
   unsigned SortRank;
 
   uint32_t getPhdrFlags() const;
 
   // Pointer to the PT_LOAD segment, which this section resides in. This field
   // is used to correctly compute file offset of a section. When two sections
   // share the same load segment, difference between their file offsets should

ELF/ScriptParser.cpp

if (!isPowerOf2_64(Alignment)) {
       return (uint64_t)1; // Return a dummy value.
     }
     return Alignment;
   };
 }
 
 OutputSection *ScriptParser::readOutputSectionDescription(StringRef OutSec) {
   OutputSection *Cmd =
-      Script->createOutputSection(OutSec, getCurrentLocation());
+      Script->defineOutputSection(OutSec, getCurrentLocation());
 
   if (peek() != ":")
     readSectionAddressType(Cmd);
   expect(":");
 
   std::string Location = getCurrentLocation();
   if (consume("AT"))
     Cmd->LMAExpr = readParenExpr();
if (Tok == "ABSOLUTE") {
     return [=] {
       ExprValue I = Inner();
       I.ForceAbsolute = true;
       return I;
     };
   }
   if (Tok == "ADDR") {
     StringRef Name = readParenLiteral();
-    OutputSection *Sec = Script->getOrCreateOutputSection(Name);
+    Script->declareOutputSection(Name);
     return [=]() -> ExprValue {
+      OutputSection *Sec = Script->getOutputSection(Name);
       checkIfExists(Sec, Location);
       return {Sec, false, 0, Location};
     };
   }
   if (Tok == "ALIGN") {
     expect("(");
     Expr E = readExpr();
     if (consume(")")) {
       E = checkAlignment(E, Location);
       return [=] { return alignTo(Script->getDot(), E().getValue()); };
     }
     expect(",");
     Expr E2 = checkAlignment(readExpr(), Location);
     expect(")");
     return [=] {
       ExprValue V = E();
       V.Alignment = E2().getValue();
       return V;
     };
   }
   if (Tok == "ALIGNOF") {
     StringRef Name = readParenLiteral();
-    OutputSection *Cmd = Script->getOrCreateOutputSection(Name);
+    Script->declareOutputSection(Name);
     return [=] {
-      checkIfExists(Cmd, Location);
-      return Cmd->Alignment;
+      OutputSection *Sec = Script->getOutputSection(Name);
+      checkIfExists(Sec, Location);
+      return Sec->Alignment;
     };
   }
   if (Tok == "ASSERT")
     return readAssertExpr();
   if (Tok == "CONSTANT")
     return readConstant();
   if (Tok == "DATA_SEGMENT_ALIGN") {
     expect("(");
Expr ScriptParser::readPrimary() {
   if (Tok == "LENGTH") {
     StringRef Name = readParenLiteral();
     if (Script->MemoryRegions.count(Name) == 0)
       setError("memory region not defined: " + Name);
     return [=] { return Script->MemoryRegions[Name]->Length; };
   }
   if (Tok == "LOADADDR") {
     StringRef Name = readParenLiteral();
-    OutputSection *Cmd = Script->getOrCreateOutputSection(Name);
+    Script->declareOutputSection(Name);
     return [=] {
-      checkIfExists(Cmd, Location);
-      return Cmd->getLMA();
+      OutputSection *Sec = Script->getOutputSection(Name);
+      checkIfExists(Sec, Location);
+      return Sec->getLMA();
     };
   }
   if (Tok == "ORIGIN") {
     StringRef Name = readParenLiteral();
     if (Script->MemoryRegions.count(Name) == 0)
       setError("memory region not defined: " + Name);
     return [=] { return Script->MemoryRegions[Name]->Origin; };
   }
   if (Tok == "SEGMENT_START") {
     expect("(");
     skip();
     expect(",");
     Expr E = readExpr();
     expect(")");
     return [=] { return E(); };
   }
   if (Tok == "SIZEOF") {
     StringRef Name = readParenLiteral();
-    OutputSection *Cmd = Script->getOrCreateOutputSection(Name);
+    Script->declareOutputSection(Name);
     // Linker script does not create an output section if its content is empty.
     // We want to allow SIZEOF(.foo) where .foo is a section which happened to
     // be empty.
-    return [=] { return Cmd->Size; };
+    return [=] {
+      OutputSection *Sec = Script->getOutputSection(Name);
+      return Sec->Size;
+    };
   }
   if (Tok == "SIZEOF_HEADERS")
     return [=] { return elf::getHeaderSize(); };
 
   // Tok is the dot.
   if (Tok == ".")
     return [=] { return Script->getSymbolValue(Tok, Location); };
 

test/ELF/linkerscript/sections-constraint6.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
+# RUN: echo "SECTIONS { . = 0x10000;                         \
+# RUN:         symSize1 = SIZEOF(bar); symAddr1 = ADDR(bar); \
+# RUN:         bar : ONLY_IF_RO { *(unknown) }               \
+# RUN:         bar : ONLY_IF_RW { *(foo_aw) }                \
+# RUN:         symSize2 = SIZEOF(bar); symAddr2 = ADDR(bar); \
+# RUN:       }" > %t.script
+# RUN: ld.lld -o %t -T %t.script %t.o
+# RUN: llvm-readobj -s -t %t | FileCheck %s
+
+## Check values of symbols are (1) not zeroes and (2) corresponds to
+## size and address of bar that contains foo_aw input section.
+# CHECK: Sections [
+# CHECK:      Name: bar
+# CHECK-NEXT: Type: SHT_PROGBITS
+# CHECK-NEXT: Flags [
+# CHECK-NEXT:   SHF_ALLOC
+# CHECK-NEXT:   SHF_WRITE
+# CHECK-NEXT: ]
+# CHECK-NEXT: Address: 0x10001
+# CHECK-NEXT: Offset:
+# CHECK-NEXT: Size: 8
+# CHECK:      Name: symSize1
+# CHECK-NEXT:  Value: 0x8
+# CHECK:      Name: symAddr1
+# CHECK-NEXT:  Value: 0x10001
+# CHECK:      Name: symSize2
+# CHECK-NEXT:  Value: 0x8
+# CHECK:      Name: symAddr2
+# CHECK-NEXT:  Value: 0x10001
+
+.section foo_a,"a"
+.byte 0
+
+.section foo_aw,"aw"
+.quad 0