[LLD][ELF] - Linkerscript: add a support for expressions for section's filling

[grimar]

Summary

Imagine the script:

.section: {
...
} = FILL_EXPR

LLD assumes that FILL_EXPR is a number, and does not allow
it to be an expression. Though that is allowed by specification:
https://sourceware.org/binutils/docs-2.32/ld/Output-Section-Fill.html

This patch adds a support for cases when FILL_EXPR is simple math expression.
I am not sure it makes sense to support the case when expression uses symbols,
I hope it is not used in the wild, though we can do that in a follow-up, but that would do
our filling code a bit more complicated.

Fixes https://bugs.llvm.org/show_bug.cgi?id=42482.

[MaskRay]

Though that is allowed by specification: https://access.redhat.com/documentation/en-US/Red_Hat_Enterprise_Linux/4/html/Using_ld_the_GNU_Linker/sections.html#OUTPUT-SECTION-FILL

Looks like you can change it to https://sourceware.org/binutils/docs/ld/Output-Section-Fill.html or https://sourceware.org/binutils/docs-2.32/ld/Output-Section-Fill.html

[grimar]

• A minor simplification.

[peter.smith]

It looks like gold and bfd disagree on whether a symbol is allowed in practice.

foo = 0x12345678;

SECTIONS {
 .text : { *(.text) } = foo
}

With ld.bfd I get an error, even if I use ABSOLUTE(foo)

ld.bfd fill.o -T fill.lds
fill.lds:4: nonconstant expression for fill value

With gold the link succeeds

ld.gold fill.o -T fill.lds

The ld.bfd I used was quite old 2.26.1 so this may have changed in later versions. Trying a later version lead to a ld.bfd segfault in one case.

As I think that this is an improvement and I agree that a symbol is unlikely to be encountered in practice so I think this is worth doing.

ELF/ScriptParser.cpp

884 ↗

(On Diff #207785)

It is worth a comment or FIXME: saying we don't support symbols in fill expressions?

[grimar]

• Addressed review comments.

ELF/ScriptParser.cpp

884 ↗

(On Diff #207785)

Done. I also added a test case to demonstrate the current behavior. It shows "symbol not found: foo" currently,
because tries to find a symbol during evaluating the expression. And at this moment no symbols are added
to a sym table.

In theory we can change the message to be more meaningful in case we read an expression
that should not use any symbols, but since it would be used only for fillexpr, I am not sure it worth doing.

[grimar]

ELF/ScriptParser.cpp

884 ↗

(On Diff #207785)

I.e. I mean we could add a flag like DontAllowSymbols and return a different error message when reading an expression which has a reference to a symbol. But, as I said, It looks a bit too much for this feature.

[peter.smith]

Thanks for the update. Looks ok to me, will be worth seeing what the others say.

[arichardson]

ELF/ScriptLexer.cpp

195 ↗

(On Diff #207807)

This seems unrelated, maybe split it out into a separate patch?

[MaskRay]

Looks good to me.

ELF/ScriptLexer.cpp

195 ↗

(On Diff #207807)

I think tokenizeExpr() did not have to be precise before because readOutputSectionDescription() did not consume tokens that can be prefixed of ==, <<, <=, >= and >> (i.e. =, <, >). Now it did so a preciser tokenizeExpr is needed.

I think keeping the change here is probably fine.

test/ELF/linkerscript/sections-padding.s

45 ↗

(On Diff #207807)

You can delete the spaces around << to check tokens are correctly split.

[grimar]

• Addressed comments.

ELF/ScriptLexer.cpp

195 ↗

(On Diff #207807)

Yes, this is needed for this patch to work (after adding only = a few of our other test start failing).

[ruiu]

LGTM

[andrewng]

This change breaks if you add FILL(0x10101010) before *(.aaa) in fill.test:

# REQUIRES: x86
# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/fill.s -o %t.o
# RUN: ld.lld -o %t --script %s %t.o
# RUN: llvm-objdump -s %t | FileCheck %s

SECTIONS {
  .out : {
   FILL(0x11111111)
   . += 2;
   FILL(0x10101010)
   *(.aaa)
   . += 4;
   *(.bbb)
   . += 4;
   FILL(0x22220000 + 0x2222);
   . += 4;
  }
}

# CHECK:      Contents of section .out:
# CHECK-NEXT: 2222aa22 222222bb 22222222 22222222

That's because the expression for the FILL command should be contained within the parentheses.

[grimar]

In D64130#1571560, @andrewng wrote:

This change breaks if you add FILL(0x10101010) before *(.aaa) in fill.test:

# REQUIRES: x86
# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/fill.s -o %t.o
# RUN: ld.lld -o %t --script %s %t.o
# RUN: llvm-objdump -s %t | FileCheck %s

SECTIONS {
  .out : {
   FILL(0x11111111)
   . += 2;
   FILL(0x10101010)
   *(.aaa)
   . += 4;
   *(.bbb)
   . += 4;
   FILL(0x22220000 + 0x2222);
   . += 4;
  }
}

# CHECK:      Contents of section .out:
# CHECK-NEXT: 2222aa22 222222bb 22222222 22222222

That's because the expression for the FILL command should be contained within the parentheses.

I posted D64476 to fix.

lld/trunk/ELF/ScriptLexer.cpp

 }
 
 // An erroneous token is handled as if it were the last token before EOF.
 bool ScriptLexer::atEOF() { return errorCount() || Tokens.size() == Pos; }
 
 // Split a given string as an expression.
 // This function returns "3", "*" and "5" for "3*5" for example.
 static std::vector<StringRef> tokenizeExpr(StringRef S) {
-  StringRef Ops = "+-*/:!~"; // List of operators
+  StringRef Ops = "+-*/:!~=<>"; // List of operators
 
   // Quoted strings are literal strings, so we don't want to split it.
   if (S.startswith("\""))
     return {S};
 
   // Split S with operators as separators.
   std::vector<StringRef> Ret;
   while (!S.empty()) {
     size_t E = S.find_first_of(Ops);
 
     // No need to split if there is no operator.
     if (E == StringRef::npos) {
       Ret.push_back(S);
       break;
     }
 
     // Get a token before the opreator.
     if (E != 0)
       Ret.push_back(S.substr(0, E));
 
-    // Get the operator as a token. Keep != as one token.
-    if (S.substr(E).startswith("!=")) {
+    // Get the operator as a token.
+    // Keep !=, ==, >=, <=, << and >> operators as a single tokens.
+    if (S.substr(E).startswith("!=") || S.substr(E).startswith("==") ||
+        S.substr(E).startswith(">=") || S.substr(E).startswith("<=") ||
+        S.substr(E).startswith("<<") || S.substr(E).startswith(">>")) {
       Ret.push_back(S.substr(E, 2));
       S = S.substr(E + 2);
     } else {
       Ret.push_back(S.substr(E, 1));
       S = S.substr(E + 1);
     }
   }
   return Ret;

lld/trunk/ELF/ScriptParser.cpp

private:
   void readSections();
   void readTarget();
   void readVersion();
   void readVersionScriptCommand();
 
   SymbolAssignment *readSymbolAssignment(StringRef Name);
   ByteCommand *readByteCommand(StringRef Tok);
   std::array<uint8_t, 4> readFill();
-  std::array<uint8_t, 4> parseFill(StringRef Tok);
   bool readSectionDirective(OutputSection *Cmd, StringRef Tok1, StringRef Tok2);
   void readSectionAddressType(OutputSection *Cmd);
   OutputSection *readOverlaySectionDescription();
   OutputSection *readOutputSectionDescription(StringRef OutSec);
   std::vector<BaseCommand *> readOverlay();
   std::vector<StringRef> readOutputSectionPhdrs();
   InputSectionDescription *readInputSectionDescription(StringRef Tok);
   StringMatcher readFilePatterns();
Expr ScriptParser::readAssert() {
 
   return [=] {
     if (!E().getValue())
       error(Msg);
     return Script->getDot();
   };
 }
 
-// Reads a FILL(expr) command. We handle the FILL command as an
-// alias for =fillexp section attribute, which is different from
-// what GNU linkers do.
-// https://sourceware.org/binutils/docs/ld/Output-Section-Data.html
-std::array<uint8_t, 4> ScriptParser::readFill() {
-  expect("(");
-  std::array<uint8_t, 4> V = parseFill(next());
-  expect(")");
-  return V;
-}
-
 // Tries to read the special directive for an output section definition which
 // can be one of following: "(NOLOAD)", "(COPY)", "(INFO)" or "(OVERLAY)".
 // Tok1 and Tok2 are next 2 tokens peeked. See comment for readSectionAddressType below.
 bool ScriptParser::readSectionDirective(OutputSection *Cmd, StringRef Tok1, StringRef Tok2) {
   if (Tok1 != "(")
     return false;
   if (Tok2 != "NOLOAD" && Tok2 != "COPY" && Tok2 != "INFO" && Tok2 != "OVERLAY")
     return false;
if (Tok == ";") {
       Cmd->SectionCommands.push_back(Assign);
     } else if (ByteCommand *Data = readByteCommand(Tok)) {
       Cmd->SectionCommands.push_back(Data);
     } else if (Tok == "CONSTRUCTORS") {
       // CONSTRUCTORS is a keyword to make the linker recognize C++ ctors/dtors
       // by name. This is for very old file formats such as ECOFF/XCOFF.
       // For ELF, we should ignore.
     } else if (Tok == "FILL") {
+      // We handle the FILL command as an alias for =fillexp section attribute,
+      // which is different from what GNU linkers do.
+      // https://sourceware.org/binutils/docs/ld/Output-Section-Data.html
       Cmd->Filler = readFill();
     } else if (Tok == "SORT") {
       readSort();
     } else if (Tok == "INCLUDE") {
       readInclude();
     } else if (peek() == "(") {
       Cmd->SectionCommands.push_back(readInputSectionDescription(Tok));
     } else {
if (consume("AT")) {
     Cmd->LMARegionName = next();
   }
 
   if (Cmd->LMAExpr && !Cmd->LMARegionName.empty())
     error("section can't have both LMA and a load region");
 
   Cmd->Phdrs = readOutputSectionPhdrs();
 
-  if (consume("="))
-    Cmd->Filler = parseFill(next());
-  else if (peek().startswith("="))
-    Cmd->Filler = parseFill(next().drop_front());
+  if (peek() == "=" || peek().startswith("=")) {
+    InExpr = true;
+    consume("=");
+    Cmd->Filler = readFill();
+    InExpr = false;
+  }
 
   // Consume optional comma following output section command.
   consume(",");
 
   if (Script->ReferencedSymbols.size() > SymbolsReferenced)
     Cmd->ExpressionsUseSymbols = true;
   return Cmd;
 }
 
-// Parses a given string as a octal/decimal/hexadecimal number and
-// returns it as a big-endian number. Used for `=<fillexp>`.
+// Reads a `=<fillexp>` expression and returns its value as a big-endian number.
 // https://sourceware.org/binutils/docs/ld/Output-Section-Fill.html
+// We do not support using symbols in such expressions.
 //
 // When reading a hexstring, ld.bfd handles it as a blob of arbitrary
 // size, while ld.gold always handles it as a 32-bit big-endian number.
 // We are compatible with ld.gold because it's easier to implement.
-std::array<uint8_t, 4> ScriptParser::parseFill(StringRef Tok) {
-  uint32_t V = 0;
-  if (!to_integer(Tok, V))
-    setError("invalid filler expression: " + Tok);
+std::array<uint8_t, 4> ScriptParser::readFill() {
+  uint64_t Value = readExpr()().Val;
+  if (Value > UINT32_MAX)
+    setError("filler expression result does not fit 32-bit: 0x" +
+             Twine::utohexstr(Value));
 
   std::array<uint8_t, 4> Buf;
-  write32be(Buf.data(), V);
+  write32be(Buf.data(), (uint32_t)Value);
   return Buf;
 }
 
 SymbolAssignment *ScriptParser::readProvideHidden(bool Provide, bool Hidden) {
   expect("(");
   SymbolAssignment *Cmd = readSymbolAssignment(next());
   Cmd->Provide = Provide;
   Cmd->Hidden = Hidden;

lld/trunk/test/ELF/linkerscript/fill.test

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/fill.s -o %t.o
 # RUN: ld.lld -o %t --script %s %t.o
 # RUN: llvm-objdump -s %t | FileCheck %s
 
 SECTIONS {
   .out : {
    FILL(0x11111111)
    . += 2;
    *(.aaa)
    . += 4;
    *(.bbb)
    . += 4;
-   FILL(0x22222222);
+   FILL(0x22220000 + 0x2222);
    . += 4;
   }
 }
 
 # CHECK:      Contents of section .out:
 # CHECK-NEXT: 2222aa22 222222bb 22222222 22222222

lld/trunk/test/ELF/linkerscript/sections-padding.s

 # RUN: ld.lld -o %t.out --script %t.script %t
 # RUN: llvm-objdump -s %t.out | FileCheck -check-prefix=DEC %s
 # DEC: 66000003 09000003 09000003 09000003
 
 ## Invalid hex value:
 # RUN: echo "SECTIONS { .mysec : { *(.mysec*) } =0x99XX }" > %t.script
 # RUN: not ld.lld -o %t.out --script %t.script %t 2>&1 \
 # RUN:   | FileCheck --check-prefix=ERR2 %s
-# ERR2: invalid filler expression: 0x99XX
+# ERR2: malformed number: 0x99XX
 
-## Check case with space between '=' and expression:
+## Check case with space between '=' and a value:
 # RUN: echo "SECTIONS { .mysec : { *(.mysec*) } = 0x1122 }" > %t.script
 # RUN: ld.lld -o %t.out --script %t.script %t
 # RUN: llvm-objdump -s %t.out | FileCheck -check-prefix=YES %s
 
 ## Check case with optional comma following output section command:
 # RUN: echo "SECTIONS { .mysec : { *(.mysec*) } =0x1122, .a : { *(.a*) } }" > %t.script
 # RUN: ld.lld -o %t.out --script %t.script %t
 # RUN: llvm-objdump -s %t.out | FileCheck -check-prefix=YES %s
 
+## Check we can use an artbitrary expression as a filler.
+# RUN: echo "SECTIONS { .mysec : { *(.mysec*) } = ((0x11<<8) | 0x22) }" > %t.script
+# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: llvm-objdump -s %t.out | FileCheck -check-prefix=YES %s
+
+## Check case with space between '=' and expression:
+# RUN: echo "SECTIONS { .mysec : { *(.mysec*) } =((0x11 << 8) | 0x22) }" > %t.script
+# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: llvm-objdump -s %t.out | FileCheck -check-prefix=YES %s
+
+## Check we report an error if expression value is larger that 32-bits.
+# RUN: echo "SECTIONS { .mysec : { *(.mysec*) } =(0x11 << 32) }" > %t.script
+# RUN: not ld.lld -o %t.out --script %t.script %t 2>&1 | FileCheck --check-prefix=ERR3 %s
+# ERR3: filler expression result does not fit 32-bit: 0x1100000000
+
+## Check we report an error if an expression use a symbol.
+# RUN: echo "SECTIONS { foo = 0x11; .mysec : { *(.mysec*) } = foo }" > %t.script
+# RUN: not ld.lld -o %t.out %t --script %t.script 2>&1 | FileCheck --check-prefix=ERR4 %s
+# ERR4: symbol not found: foo
+
 .section        .mysec.1,"a"
 .align  16
 .byte   0x66
 
 .section        .mysec.2,"a"
 .align  16
 .byte   0x66
 
 .globl _start
 _start:
  nop