[ELF] Postpone evaluation of ORIGIN/LENGTH in a MEMORY command

[MaskRay]

Summary

createFiles(args)
 readDefsym
 readerLinkerScript(*mb)
  ...
   readMemory
    readMemoryAssignment("ORIGIN", "org", "o") // eagerly evaluated
target = getTarget();
link(args)
 writeResult<ELFT>()
  ...
   finalizeSections()
    script->processSymbolAssignments()
     addSymbol(cmd) // with this patch, evaluated here

readMemoryAssignment eagerly evaluates ORIGIN/LENGTH and returns an uint64_t.
This patch postpones the evaluation to make

• --defsym and symbol assignments
• CONSTANT(COMMONPAGESIZE) (requires a non-null lld::elf::target)

work. If the expression somehow requires interaction with memory
regions, the circular dependency may cause the expression to evaluate to
a strange value. See the new test added to memory-err.s

[MaskRay]

Add tests

[grimar]

LGTM with 2 comments addressed.

lld/ELF/ScriptParser.cpp

1526

It calls std::function(nullptr_t) constructor.
Such Expr will fail during evaluation (exception: std::bad_function_call).

You should probably use return [] { return 0; };

lld/test/ELF/linkerscript/memory.s

49

I'd probably add a short description comment here and for the test below.

[MaskRay]

Address comments

lld/ELF/ScriptParser.cpp

1526

Thanks for this tip!

return 0 does not crash (not testable) because:

createFiles(args);  // parse linker scripts
if (errorCount())
  return;

Anyway, return [] { return 0; }; removes dependency on errorCount() check.

[aykevl]

Adding myself as reviewer so I don't lose this patch. I hope to test this out soon.

[MaskRay]

Add documentation docs/ELF/linker_script.rst

[MaskRay]

Restore the previous Diff. Added docs/ELF/linker_script.rst to the wrong Differential.

lld/ELF/LinkerScript.h

 // only if its input sections are read-only. Likewise, an output section
 // with ONLY_IF_RW is created if all input sections are RW.
 enum class ConstraintKind { NoConstraint, ReadOnly, ReadWrite };
 
 // This struct is used to represent the location and size of regions of
 // target memory. Instances of the struct are created by parsing the
 // MEMORY command.
 struct MemoryRegion {
-  MemoryRegion(StringRef name, uint64_t origin, uint64_t length, uint32_t flags,
+  MemoryRegion(StringRef name, Expr origin, Expr length, uint32_t flags,
                uint32_t negFlags)
       : name(std::string(name)), origin(origin), length(length), flags(flags),
         negFlags(negFlags) {}
 
   std::string name;
-  uint64_t origin;
-  uint64_t length;
+  Expr origin;
+  Expr length;
   uint32_t flags;
   uint32_t negFlags;
   uint64_t curPos = 0;
 };
 
 // This struct represents one section match pattern in SECTIONS() command.
 // It can optionally have negative match pattern for EXCLUDED_FILE command.
 // Also it may be surrounded with SORT() command, so contains sorting rules.

lld/ELF/LinkerScript.cpp

if (!cmdRef)
     cmdRef = make<OutputSection>(name, SHT_PROGBITS, 0);
   return cmdRef;
 }
 
 // Expands the memory region by the specified size.
 static void expandMemoryRegion(MemoryRegion *memRegion, uint64_t size,
                                StringRef regionName, StringRef secName) {
   memRegion->curPos += size;
-  uint64_t newSize = memRegion->curPos - memRegion->origin;
-  if (newSize > memRegion->length)
+  uint64_t newSize = memRegion->curPos - (memRegion->origin)().getValue();
+  uint64_t length = (memRegion->length)().getValue();
+  if (newSize > length)
     error("section '" + secName + "' will not fit in region '" + regionName +
-          "': overflowed by " + Twine(newSize - memRegion->length) + " bytes");
+          "': overflowed by " + Twine(newSize - length) + " bytes");
 }
 
 void LinkerScript::expandMemoryRegions(uint64_t size) {
   if (ctx->memRegion)
     expandMemoryRegion(ctx->memRegion, size, ctx->memRegion->name,
                        ctx->outSec->name);
   // Only expand the LMARegion if it is different from memRegion.
   if (ctx->lmaRegion && ctx->memRegion != ctx->lmaRegion)
void LinkerScript::allocateHeaders(std::vector<PhdrEntry *> &phdrs) {
 
   llvm::erase_if(phdrs,
                  [](const PhdrEntry *e) { return e->p_type == PT_PHDR; });
 }
 
 LinkerScript::AddressState::AddressState() {
   for (auto &mri : script->memoryRegions) {
     MemoryRegion *mr = mri.second;
-    mr->curPos = mr->origin;
+    mr->curPos = (mr->origin)().getValue();
   }
 }
 
 // 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.
 // Returns a symbol that has changed its section or value, or nullptr if no
 // symbol has changed.

lld/ELF/ScriptParser.cpp

private:
   SortSectionPolicy readSortKind();
   SymbolAssignment *readProvideHidden(bool provide, bool hidden);
   SymbolAssignment *readAssignment(StringRef tok);
   void readSort();
   Expr readAssert();
   Expr readConstant();
   Expr getPageSize();
 
-  uint64_t readMemoryAssignment(StringRef, StringRef, StringRef);
+  Expr readMemoryAssignment(StringRef, StringRef, StringRef);
   std::pair<uint32_t, uint32_t> readMemoryAttributes();
 
   Expr combine(StringRef op, Expr l, Expr r);
   Expr readExpr();
   Expr readExpr1(Expr lhs, int minPrec);
   StringRef readParenLiteral();
   Expr readPrimary();
   Expr readTernary(Expr cond);
if (tok == "DEFINED") {
     return [=] { return symtab->find(name) ? 1 : 0; };
   }
   if (tok == "LENGTH") {
     StringRef name = readParenLiteral();
     if (script->memoryRegions.count(name) == 0) {
       setError("memory region not defined: " + name);
       return [] { return 0; };
     }
-    return [=] { return script->memoryRegions[name]->length; };
+    return script->memoryRegions[name]->length;
   }
   if (tok == "LOADADDR") {
     StringRef name = readParenLiteral();
     OutputSection *cmd = script->getOrCreateOutputSection(name);
     cmd->usedInExpression = true;
     return [=] {
       checkIfExists(cmd, location);
       return cmd->getLMA();
if (tok == "MAX" || tok == "MIN") {
     return [=] { return std::max(a().getValue(), b().getValue()); };
   }
   if (tok == "ORIGIN") {
     StringRef name = readParenLiteral();
     if (script->memoryRegions.count(name) == 0) {
       setError("memory region not defined: " + name);
       return [] { return 0; };
     }
-    return [=] { return script->memoryRegions[name]->origin; };
+    return script->memoryRegions[name]->origin;
   }
   if (tok == "SEGMENT_START") {
     expect("(");
     skip();
     expect(",");
     Expr e = readExpr();
     expect(")");
     return [=] { return e(); };
if (consume("}"))
       return ret;
     expect(";");
   }
 
   expect("}");
   return ret;
 }
 
-uint64_t ScriptParser::readMemoryAssignment(StringRef s1, StringRef s2,
-                                            StringRef s3) {
+Expr ScriptParser::readMemoryAssignment(StringRef s1, StringRef s2,
   if (!consume(s1) && !consume(s2) && !consume(s3)) {
     setError("expected one of: " + s1 + ", " + s2 + ", or " + s3);
-    return 0;
+    return [] { return 0; };
   }
   expect("=");
-  return readExpr()().getValue();
+  return readExpr();
 }
 
 // Parse the MEMORY command as specified in:
 // https://sourceware.org/binutils/docs/ld/MEMORY.html
 //
 // MEMORY { name [(attr)] : ORIGIN = origin, LENGTH = len ... }
 void ScriptParser::readMemory() {
   expect("{");
   while (!errorCount() && !consume("}")) {
     StringRef tok = next();
     if (tok == "INCLUDE") {
       readInclude();
       continue;
     }
 
     uint32_t flags = 0;
     uint32_t negFlags = 0;
     if (consume("(")) {
       std::tie(flags, negFlags) = readMemoryAttributes();
       expect(")");
     }
     expect(":");
 
-    uint64_t origin = readMemoryAssignment("ORIGIN", "org", "o");
+    Expr origin = readMemoryAssignment("ORIGIN", "org", "o");
     expect(",");
-    uint64_t length = readMemoryAssignment("LENGTH", "len", "l");
+    Expr length = readMemoryAssignment("LENGTH", "len", "l");
 
     // Add the memory region to the region map.
     MemoryRegion *mr = make<MemoryRegion>(tok, origin, length, flags, negFlags);
     if (!script->memoryRegions.insert({tok, mr}).second)
       setError("region '" + tok + "' already defined");
   }
 }
 

lld/docs/ELF/linker_script.rst

+Output section description
+==========================
+
+The description of an output section looks like:
+
+::
+
+  section [address] [(type)] : [AT(lma)] [ALIGN(section_align)] [SUBALIGN](subsection_align)] {
+    output-section-command
+    ...
+  } [>region] [AT>lma_region] [:phdr ...] [=fillexp] [,]
+
+Output section address
+======================
+
+When an *OutputSection* *S* has ``address``, LLD will set sh_addr to ``address``.
+
+The ELF specification says:
+
+> The value of sh_addr must be congruent to 0, modulo the value of sh_addralign.
+
+The presence of ``address`` can cause the condition unsatisfied. LLD will warn.
+GNU ld from Binutils 2.35 onwards will reduce sh_addralign so that
+sh_addr=0 (modulo sh_addralign).
+
+Output section alignment
+========================
+
+sh_addralign of an *OutputSection* *S* is the maximum of
+``ALIGN(section_align)`` and the maximum alignment of the input sections in
+*S*.
+
+When an *OutputSection* *S* has both ``address`` and ``ALIGN(section_align)``,
+GNU ld will set sh_addralign to ``ALIGN(section_align)``.

lld/test/ELF/linkerscript/memory-err.s

 
 ## Check invalid region attributes.
 
 # RUN: echo "MEMORY { ram (abc) : ORIGIN = 8000, LENGTH = 256K } }" > %t.script
 # RUN: not ld.lld -o /dev/null -T %t.script %t.o 2>&1 | FileCheck --check-prefix=ERR7 %s
 # ERR7: {{.*}}.script:1: invalid memory region attribute
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
-# RUN: echo "MEMORY { name : ORIGIN = DATA_SEGMENT_RELRO_END; }" > %t.script
-# RUN: not ld.lld -shared -o /dev/null -T %t.script %t.o 2>&1 | FileCheck %s
-# CHECK: error: {{.*}}.script:1: unable to calculate page size
-
-# RUN: echo 'MEMORY { name : ORIGIN = CONSTANT(COMMONPAGESIZE); }' > %t.script
-# RUN: not ld.lld -shared -o /dev/null -T %t.script %t.o 2>&1 | FileCheck --check-prefix=ERR_PAGESIZE %s
-# ERR_PAGESIZE: error: {{.*}}.script:1: unable to calculate page size
-
-# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
-# RUN: echo 'MEMORY { name : ORIGIN = .; }' > %t.script
+# RUN: echo 'MEMORY { name : ORIGIN = ., LENGTH = 1 }' > %t.script
 # RUN: not ld.lld -shared -o /dev/null -T %t.script %t.o 2>&1 | FileCheck --check-prefix=ERR_DOT %s
 # ERR_DOT: error: {{.*}}.script:1: unable to get location counter value
 
+## ORIGIN/LENGTH can be simple symbolic expressions. If the expression
+## requires interaction with memory regions, it may fail.
+
+# RUN: echo 'MEMORY { ram : ORIGIN = symbol, LENGTH = 4097 } \
+# RUN: SECTIONS { \
+# RUN:   .text : { *(.text) } > ram \
+# RUN:   symbol = .; \
+# RUN:   .data : { *(.data) } > ram \
+# RUN: }' > %t.script
+# RUN: not ld.lld -T %t.script %t.o -o /dev/null 2>&1 | FileCheck --check-prefix=ERR_OVERFLOW %s
+# ERR_OVERFLOW: error: section '.text' will not fit in region 'ram': overflowed by 18446744073709547518 bytes
+
 nop
 
 .data
 .zero 4096

lld/test/ELF/linkerscript/memory.s

 # RUN:   .data : { *(.data) } > ram \
 # RUN: }" > %t.script
 # RUN: ld.lld -o %t1 --script %t.script %t
 # RUN: llvm-readelf -S %t1 | FileCheck --check-prefix=ATTRS %s
 
 # ATTRS:      [ 1] .text PROGBITS 0000000080000000 001000 000001
 # ATTRS-NEXT: [ 2] .data PROGBITS 0000000000000000 002000 001000
 
+## ORIGIN/LENGTH support expressions with symbol assignments.
+# RUN: echo 'MEMORY { ram : ORIGIN = symbol, LENGTH = 4097 } \
+# RUN: SECTIONS { \
+# RUN:   .text : { *(.text) } > ram \
+# RUN:   .data : { *(.data) } > ram \
+# RUN: }' > %t.script
+# RUN: ld.lld -T %t.script %t --defsym symbol=0x5000 -o %t.relro
+# RUN: llvm-readelf -S %t.relro | FileCheck --check-prefix=RELRO %s
+# RUN: echo 'symbol = 0x5000;' > %t1.script
+# RUN: ld.lld -T %t.script -T %t1.script %t -o %t.relro2
+# RUN: llvm-readelf -S %t.relro2 | FileCheck --check-prefix=RELRO %s
+
+# RELRO:      [ 1] .text PROGBITS 0000000000005000 001000 000001
+# RELRO-NEXT: [ 2] .data PROGBITS 0000000000005001 001001 001000
+
+# RUN: echo 'MEMORY { ram : ORIGIN = CONSTANT(COMMONPAGESIZE), LENGTH = CONSTANT(COMMONPAGESIZE)+1 } \
+# RUN: SECTIONS { \
+# RUN:   .text : { *(.text) } > ram \
+# RUN:   .data : { *(.data) } > ram \
+# RUN: }' > %t.script
+# RUN: ld.lld -T %t.script %t -o %t.pagesize
+# RUN: llvm-readelf -S %t.pagesize | FileCheck --check-prefix=PAGESIZE %s
+
+# PAGESIZE:      [ 1] .text PROGBITS 0000000000001000 001000 000001
+# PAGESIZE-NEXT: [ 2] .data PROGBITS 0000000000001001 001001 001000
+
 .text
 .global _start
 _start:
   nop
 
 .data
 b:
   .long 1
   .zero 4092