[ELF] Generate symbol assignments for predefined symbols

[phosek]

Summary

The problem with symbol assignments in implicit linker scripts is that
they can refer synthetic symbols such as _end, _etext or _edata. The
value of these symbols is currently fixed only after all linker script
commands are processed, so these assignments will be using non-final and
hence invalid value.

Rather than fixing the symbol values after all command processing have
finished, we instead change the logic to generate symbol assignment
commands that set the value of these symbols while processing the
commands, this ensures that the value is going to be correct by the time
any reference to these symbol is processed and is equivalent to defining
these symbols explicitly in linker script as BFD ld does.

[ruiu]

ELF/LinkerScript.h

78

I think I'd name this InSections.

But do you actually need this? This is I believe virtually a flag indicating whether an element is a direct child of the top element or not. But we can distinguish BaseCommands enclosed in an OutputSections from BaseCommands that are top-level elements, no?

ELF/Writer.cpp

227

Add a comment.

[phosek]

ELF/LinkerScript.h

78

That's what I tried initially, the problem is that Opt.Commands would also contain synthetic symbol assignments created by fabricateDefaultCommands and those have to be processed in assignAddresses because they modify ., so we would need some way to distinguish those commands from other top level symbol assignments. One option would be to create a new subclass e.g. SyntheticSymbolAssignment or even DotAssignment which would then allow distinguishing the two types of assignments in assignAddresses. The other option would be to just add an attribute to SymbolAssignment. Any opinion/preference?

[phosek]

ELF/LinkerScript.h

78

Turned out it's even more complicated than that, in SECTIONS { .text : { *(.text) } foo = ABSOLUTE(.) + 0x100; .got : { *(.got) } } the foo = ABSOLUTE(.) is still going to end up in Scripts->Opt.Commands, but we have to process it early because it uses ..

I have added the InSections attribute to BaseCommand because in LLD, we allow ASSERT in input linker scripts, which means it can also refer to predefined symbols. However, neither BFD ld nor gold does allow that. If we followed the same model, we could move InSections to SymbolAssignment.

[ruiu]

ELF/LinkerScript.h

78

I'm not very sure, but creating DotAssignment sounds like a good idea, as assignments to . are very different from symbol assignments despite their superficial resemblance. It might be worth a try.

78

We do not aim to extend the linker script that GNU linkers, and we do not guarantee that the current undocumented behavior (lld supports only the documented behavior of GNU linkers). So, I think I'd move InSections to SymbolAssignment.

78

The first comment is a stale comment. I don't know why it is sent out this time, but please ignore that.

[phosek]

I have moved InSections to SymbolAssignment and AssertCommand, is there anything else? I might still try to refactor DotAssignment out from SymbolAssignment, but I'd prefer to do it as a separate change.

[ruiu]

This patch is perhaps ok as-is, but I came up with another idea: we may be able to reorder commands so that all outside-sections commands follow sections commands. Then maybe we can just process them in-order. What do you think?

[phosek]

In D36986#851730, @ruiu wrote:

This patch is perhaps ok as-is, but I came up with another idea: we may be able to reorder commands so that all outside-sections commands follow sections commands. Then maybe we can just process them in-order. What do you think?

When you say process them in-order, do you mean all of them, including the outside-sections one? The problem right now is that if outside-sections one refer to any predefined symbol, those symbols won't have a correct value until fixPredefinedSymbols ran, which can only happen after we processed all sections commands. So we would need some way to stage the processing into sections commands, then fixPredefinedSymbols and then outside-sections commands. I was thinking that maybe even better would be to simply split the sections and outside-sections commands into two different lists rather then keeping them all in Opt.Commands, processing them separately then becomes even easier.

[ruiu]

Ah, you are right that reordering elements won't fix the problem. The idea to have two separate lists sounds like a good idea.

[phosek]

In D36986#852125, @ruiu wrote:

Ah, you are right that reordering elements won't fix the problem. The idea to have two separate lists sounds like a good idea.

I tried to separate the lists, but that also turned out to be tricky because of ordering, e.g. in foo = 0x1 SECTIONS { bar = foo } baz = bar the symbols outside and inside SECTIONS have to be added to the symbol table in that particular order which is difficult when they're in separate lists. Given that, I think the current solution albeit not pretty is still the simplest one.

[phosek]

I take my last comment back, I think I came up with a much better solution, I'll send a patch as soon as I clean it up a bit.

[phosek]

Done, let me know if the new implementation makes sense. I can probably cleanup the code a bit more (possible combine the two Set* lambdas into one).

[ruiu]

ELF/Writer.cpp

205

Can you briefly mention as a comment about what this function is supposed to do?

927

Can you add a comment to explain what this function is supposed to do?

[phosek]

ping

[ruiu]

LGTM

I have a little concern about this patch because this patch makes lld a bit more interpret-y. GNU bfd linker has a notion of "internal" linker script which drives the entire linking process, and I don't like the idea because that's too abstract to my taste. In lld, we take more direct approach to create a result: everything is directly driven by code and the flow of control is basically not controlled by scripts. This patch seems like a deviation from that design.

That being said, this patch looks what it should do in a simplest possible way, so I think I'm fine with this. I'm just expressing my thought.

ELF/Writer.cpp

205

I'd explain what is "predefined" a bit more, as this comment is essentially the same as the function name.

927

predefined symbols (e.g. _end or _etext)

[phosek]

Thanks! I understand your concern but I think this change is in line with what LLD already does e.g. for output sections which are also converted to commands. The main difference between BFD ld and LLD is that in BFD ld, even the default behavior is driven by the linker script while in LLD we only construct the internal representation that is equivalent to some imaginary linker script... in a way, the BaseCommand hierarchy is becoming LLD's IR.

ELF/LinkerScript.h

enum SectionsCommandKind {
   InputSectionKind,
   AssertKind,   // ASSERT(expr)
   BytesDataKind // BYTE(expr), SHORT(expr), LONG(expr) or QUAD(expr)
 };
 
 struct BaseCommand {
   BaseCommand(int K) : Kind(K) {}
   int Kind;
+
+  // Whether the command is within SECTIONS command.
+  bool Sections = true;
 };
 
 // This represents ". = <expr>" or "<symbol> = <expr>".
 struct SymbolAssignment : BaseCommand {
   SymbolAssignment(StringRef Name, Expr E, std::string Loc)
       : BaseCommand(AssignmentKind), Name(Name), Expression(E), Location(Loc) {}
 
   static bool classof(const BaseCommand *C);

 // ScriptConfiguration holds linker script parse results.
 struct ScriptConfiguration {
   // Used to assign addresses to sections.
   std::vector<BaseCommand *> Commands;
 
   // Used to assign sections to headers.
   std::vector<PhdrsCommand> PhdrsCommands;
 
+  // Used to assign symbols outside the SECTIONS command.
+  std::vector<BaseCommand *> SymbolAssignments;
+
   bool HasSections = false;
 
   // List of section patterns specified with KEEP commands. They will
   // be kept even if they are unused and --gc-sections is specified.
   std::vector<InputSectionDescription *> KeptSections;
 
   // A map from memory region name to a memory region descriptor.
   llvm::DenseMap<llvm::StringRef, MemoryRegion> MemoryRegions;
public:
   bool ignoreInterpSection();
 
   bool shouldKeep(InputSectionBase *S);
   void assignOffsets(OutputSection *Sec);
   void assignAddresses();
   void allocateHeaders(std::vector<PhdrEntry *> &Phdrs);
   void addSymbol(SymbolAssignment *Cmd);
   void processCommands(OutputSectionFactory &Factory);
+  void processOutsideSectionsCommands();
 
   // Parsed linker script configurations are set to this struct.
   ScriptConfiguration Opt;
 };
 
 extern LinkerScript *Script;
 
 } // end namespace elf
 } // end namespace lld
 
 #endif // LLD_ELF_LINKER_SCRIPT_H

ELF/LinkerScript.cpp

 
 LinkerScript::AddressState::AddressState(const ScriptConfiguration &Opt) {
   for (auto &MRI : Opt.MemoryRegions) {
     const MemoryRegion *MR = &MRI.second;
     MemRegionOffset[MR] = MR->Origin;
   }
 }
 
+void LinkerScript::processOutsideSectionsCommands() {
+  for (BaseCommand *Base : Opt.Commands) {
+    if (Base->Sections)
+      continue;
+
+    if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
+      assignSymbol(Cmd, false);
+      continue;
+    }
+
+    if (auto *Cmd = dyn_cast<AssertCommand>(Base)) {
+      Cmd->Expression();
+      continue;
+    }
+  }
+}
+
 void LinkerScript::assignAddresses() {
   // Assign addresses as instructed by linker script SECTIONS sub-commands.
   Dot = 0;
   auto State = make_unique<AddressState>(Opt);
   // CurAddressState 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.
   CurAddressState = State.get();
   ErrorOnMissingSection = true;
   switchTo(Aether);
 
   for (BaseCommand *Base : Opt.Commands) {
+    if (!Base->Sections)
+      continue;
+
     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
       assignSymbol(Cmd, false);
       continue;
     }
 
     if (auto *Cmd = dyn_cast<AssertCommand>(Base)) {
       Cmd->Expression();
       continue;

ELF/ScriptParser.cpp

private:
   InputSectionDescription *readInputSectionDescription(StringRef Tok);
   StringMatcher readFilePatterns();
   std::vector<SectionPattern> readInputSectionsList();
   InputSectionDescription *readInputSectionRules(StringRef FilePattern);
   unsigned readPhdrType();
   SortSectionPolicy readSortKind();
   SymbolAssignment *readProvideHidden(bool Provide, bool Hidden);
   SymbolAssignment *readProvideOrAssignment(StringRef Tok);
+
   void readSort();
   AssertCommand *readAssert();
   Expr readAssertExpr();
   Expr readConstant();
   Expr getPageSize();
 
   uint64_t readMemoryAssignment(StringRef, StringRef, StringRef);
   std::pair<uint32_t, uint32_t> readMemoryAttributes();

 
 void ScriptParser::readLinkerScript() {
   while (!atEOF()) {
     StringRef Tok = next();
     if (Tok == ";")
       continue;
 
     if (Tok == "ASSERT") {
-      Script->Opt.Commands.push_back(readAssert());
+      BaseCommand *Cmd = readAssert();
+      Cmd->Sections = false;
+      Script->Opt.Commands.push_back(Cmd);
     } else if (Tok == "ENTRY") {
       readEntry();
     } else if (Tok == "EXTERN") {
       readExtern();
     } else if (Tok == "GROUP" || Tok == "INPUT") {
       readGroup();
     } else if (Tok == "INCLUDE") {
       readInclude();
if (Tok == "ASSERT") {
       readPhdrs();
     } else if (Tok == "SEARCH_DIR") {
       readSearchDir();
     } else if (Tok == "SECTIONS") {
       readSections();
     } else if (Tok == "VERSION") {
       readVersion();
     } else if (SymbolAssignment *Cmd = readProvideOrAssignment(Tok)) {
+      Cmd->Sections = false;
       Script->Opt.Commands.push_back(Cmd);
     } else {
       setError("unknown directive: " + Tok);
     }
   }
 }
 
 void ScriptParser::addFile(StringRef S) {

ELF/Writer.cpp

if (!Script->Opt.HasSections && !Config->Relocatable)
     fixSectionAlignments();
 
   // If -compressed-debug-sections is specified, we need to compress
   // .debug_* sections. Do it right now because it changes the size of
   // output sections.
   parallelForEach(OutputSections,
                   [](OutputSection *Sec) { Sec->maybeCompress<ELFT>(); });
 
   Script->assignAddresses();
   Script->allocateHeaders(Phdrs);
 
   // Remove empty PT_LOAD to avoid causing the dynamic linker to try to mmap a
   // 0 sized region. This has to be done late since only after assignAddresses
   // we know the size of the sections.
   removeEmptyPTLoad();
 
   if (!Config->OFormatBinary)
     assignFileOffsets();
   else
     assignFileOffsetsBinary();
 
   setPhdrs();
 
   if (Config->Relocatable) {
     for (OutputSection *Sec : OutputSections)
       Sec->Addr = 0;
   } else {
     fixPredefinedSymbols();
   }
 
+  Script->processOutsideSectionsCommands();
+
   // It does not make sense try to open the file if we have error already.
   if (ErrorCount)
     return;
   // Write the result down to a file.
   openFile();
   if (ErrorCount)
     return;
 
template <class ELFT> void Writer<ELFT>::createSections() {
   Script->fabricateDefaultCommands();
   sortBySymbolsOrder<ELFT>();
   sortInitFini(findSection(".init_array"));
   sortInitFini(findSection(".fini_array"));
   sortCtorsDtors(findSection(".ctors"));
   sortCtorsDtors(findSection(".dtors"));
 }
 
 // We want to find how similar two ranks are.
 // The more branches in getSectionRank that match, the more similar they are.
 // Since each branch corresponds to a bit flag, we can just use
 // countLeadingZeros.
 static int getRankProximityAux(OutputSection *A, OutputSection *B) {
   return countLeadingZeros(A->SortRank ^ B->SortRank);
 }
 
 static int getRankProximity(OutputSection *A, BaseCommand *B) {

test/ELF/linkerscript/symbol-reserved.s

 # ALIGN-ADD: 0000000000000012 *ABS* 00000000 .hidden newsym
 
 # RUN: echo "PROVIDE_HIDDEN(newsym = ALIGN(11, 8) - 10);" > %t.script
 # RUN: ld.lld -o %t1 %t.script %t
 # RUN: llvm-objdump -t %t1 | FileCheck --check-prefix=ALIGN-SUB %s
 # ALIGN-SUB: 0000000000000006 *ABS* 00000000 .hidden newsym
 
 # RUN: echo "PROVIDE_HIDDEN(newsym = ALIGN(_end, CONSTANT(MAXPAGESIZE)) + 5);" > %t.script
+# RUN: ld.lld -o %t1 %t %t.script
+# RUN: llvm-objdump -t %t1 | FileCheck --check-prefix=RELATIVE %s
+# RELATIVE: 0000000000202005 .text 00000000 .hidden newsym
+# RELATIVE: 0000000000201007 .text 00000000 _end
+
+# RUN: echo "PROVIDE_HIDDEN(newsym = ALIGN(_end, CONSTANT(MAXPAGESIZE)) + 5);" > %t.script
 # RUN: ld.lld -o %t1 --script %p/Inputs/symbol-reserved.script %t %t.script
 # RUN: llvm-objdump -t %t1 | FileCheck --check-prefix=RELATIVE-ADD %s
 # RELATIVE-ADD: 0000000000001005 .text 00000000 .hidden newsym
 # RELATIVE-ADD: 0000000000000007 .text 00000000 .hidden _end
 
 # RUN: echo "PROVIDE_HIDDEN(newsym = ALIGN(_end, CONSTANT(MAXPAGESIZE)) - 5);" > %t.script
 # RUN: ld.lld -o %t1 --script %p/Inputs/symbol-reserved.script %t %t.script
 # RUN: llvm-objdump -t %t1 | FileCheck --check-prefix=RELATIVE-SUB %s
 # RELATIVE-SUB: 0000000000000ffb .text 00000000 .hidden newsym
 # RELATIVE-SUB: 0000000000000007 .text 00000000 .hidden _end
 
 .global _start
 _start:
   lea newsym(%rip),%rax