[LLD][ELF] - Disambiguate "=fillexp" with a primary expression to allow =0x90 /DISCARD/

[grimar]

Summary

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

It is about the following case:

SECTIONS {
  .foo : { *(.foo) } =0x90909090
  /DISCARD/ : { *(.bar) }
}

Here while parsing the fill expression we treated the
"/" of "/DISCARD/" as operator.

With this change, suggested by Fangrui Song, we do
not allow expressions with operators (e.g. "0x1100 + 0x22")
that are not wrapped into round brackets. It should not
be an issue for users, but helps to resolve parsing ambiguity.

[MaskRay]

Documentation: https://sourceware.org/binutils/docs-2.33.1/ld/Output-Section-Fill.html

https://bugs.llvm.org/show_bug.cgi?id=44903 is related to D64130 . The problem is parsing ambiguity.

llvm-mc -filetype=obj linkerscript/sections-padding.s -o a.o

GNU ld's behavior is strange:

% ld.bfd -T =(printf 'SECTIONS { .mysec : { *(.mysec*) } =0x1100 }') a.o -o a
% readelf -Wx .mysec a

Hex dump of section '.mysec':
  0x00000000 66110011 00110011 00110011 00110011 f...............
  0x00000010 6690                                f.

% ld.bfd -T =(printf 'SECTIONS { .mysec : { *(.mysec*) } =0x1100+2+3 }') a.o -o a
% readelf -Wx .mysec a

Hex dump of section '.mysec':
  0x00000000 66000011 05000011 05000011 05000011 f...............
  0x00000010 6690                                f.

Do we have a more elegant fix:) ?

lld/test/ELF/linkerscript/fill-with-discard.test

3 ↗

(On Diff #244863)

-o /dev/null

Consider merging this test into sections-padding.s

[grimar]

In D74687#1878409, @MaskRay wrote:

Do we have a more elegant fix:) ?

Do you have something particular in mind? The only thing I can think of is to treat '\n' as an expression terminator.
I am not sure it is a right thing to do. I think that tokenizeExpr used in this diff is a correct place for such fix.
It has elegant name FWIW..

[MaskRay]

In D74687#1880546, @grimar wrote:

In D74687#1878409, @MaskRay wrote:

Do we have a more elegant fix:) ?

Do you have something particular in mind? The only thing I can think of is to treat '\n' as an expression terminator.
I am not sure it is a right thing to do. I think that tokenizeExpr used in this diff is a correct place for such fix.
It has elegant name FWIW..

Treating \n as an expression terminator should work. For the following example, we will accept a but not b (GNU ld accepts both):

a = (3
  +4);
b = 3
  +4;

I prefer an alternative: limit = to accept readPrimary instead of readFill:

if (peek() == "=" || peek().startswith("=")) {
  inExpr = true;
  consume("=");
  cmd->filler = readFill();
  inExpr = false;
}

As you can see, GNU ld's = syntax is weird...

[grimar]

In D74687#1880879, @MaskRay wrote:

I prefer an alternative: limit = to accept readPrimary instead of readFill:

if (peek() == "=" || peek().startswith("=")) {
  inExpr = true;
  consume("=");
  cmd->filler = readFill();
  inExpr = false;
}

Honestly I just do not feel comfortable to do this change.
If I currectly understood, you're suggesting something like:

if (peek() == "=" || peek().startswith("=")) {
  inExpr = true;
  consume("=");
  uint64_t value = readPrimary()().val;
  std::array<uint8_t, 4> buf;
  write32be(buf.data(), (uint32_t)value);

  cmd->filler = buf;
  inExpr = false;
}

With it we stop supporting syntax like SECTIONS { .mysec : { *(.mysec*) } =0x11223300+0x44 }.
It is a deviation from the specification which says that "fillexp is an expression" and mentions a unary +.

As you can see, GNU ld's = syntax is weird...

Yes, but it the current state LLD seems to have a reasonable behavior.
I am not sure we should intentionally ignore specification and remove this already supported feature just because of a specific issue
with "/DISCARD/".

[psmith]

Would it make sense to make /DISCARD/ its own token recognised by the Lexer? I believe that is what BFD does. It would prevent it from being recognised as "/" "DISCARD" "/". Apologies if this is not appropriate, I'm not too familiar with this part of the code.

[grimar]

In D74687#1893064, @psmith wrote:

Would it make sense to make /DISCARD/ its own token recognised by the Lexer? I believe that is what BFD does. It would prevent it from being recognised as "/" "DISCARD" "/". Apologies if this is not appropriate, I'm not too familiar with this part of the code.

It is what my patch does :) "/DISCARD/" is a single token initially, but during parsing of the FILL expression,
we call tokenizeExpr to return "3", "*" and "5" tokens for "3*5", for example.

I.e. tokenizeExpr should probably ignore and don't split the "/DISCARD/", and that is what I do.

[MaskRay]

In D74687#1893041, @grimar wrote:

In D74687#1880879, @MaskRay wrote:

I prefer an alternative: limit = to accept readPrimary instead of readFill:

if (peek() == "=" || peek().startswith("=")) {
  inExpr = true;
  consume("=");
  cmd->filler = readFill();
  inExpr = false;
}

Honestly I just do not feel comfortable to do this change.
If I currectly understood, you're suggesting something like:

if (peek() == "=" || peek().startswith("=")) {
  inExpr = true;
  consume("=");
  uint64_t value = readPrimary()().val;
  std::array<uint8_t, 4> buf;
  write32be(buf.data(), (uint32_t)value);

  cmd->filler = buf;
  inExpr = false;
}

With it we stop supporting syntax like SECTIONS { .mysec : { *(.mysec*) } =0x11223300+0x44 }.
It is a deviation from the specification which says that "fillexp is an expression" and mentions a unary +.

As you can see, GNU ld's = syntax is weird...

Yes, but it the current state LLD seems to have a reasonable behavior.
I am not sure we should intentionally ignore specification and remove this already supported feature just because of a specific issue
with "/DISCARD/".

See my example in https://reviews.llvm.org/D74687#1878409 I suspect =0x10+2+3 never works properly in GNU ld.
If we disallow that in lld, a user can easily work around the limitation by using =(0x10+2+3).

In D74687#1893065, @grimar wrote:

In D74687#1893064, @psmith wrote:

Would it make sense to make /DISCARD/ its own token recognised by the Lexer? I believe that is what BFD does. It would prevent it from being recognised as "/" "DISCARD" "/". Apologies if this is not appropriate, I'm not too familiar with this part of the code.

It is what my patch does :) "/DISCARD/" is a single token initially, but during parsing of the FILL expression,
we call tokenizeExpr to return "3", "*" and "5" tokens for "3*5", for example.

I.e. tokenizeExpr should probably ignore and don't split the "/DISCARD/", and that is what I do.

The trailing tokens of one output section description can cause other ambiguity when parsing the next output section description:

SECTIONS {
  .foo : { } =3
  /a : { }
}

I think it is just not necessary to support a syntax that will inherently cause problems, especially when there is no functionality loss.

[grimar]

I've revisited this patch, investigated possible use cases and reviewed our bugs history related.
I think Fangrui is right and I am going to update this diff very soon using his suggestion.

[grimar]

• Reimplemented.

[MaskRay]

The title can probably be improved.

For do not fail parsing when "/DISCARD/" follows the fill expression., I've got one suggestion.

• Disambiguate =fillexp with a primary expression to allow =0x90 /DISCARD/

A native speaker can suggest a better one:)

lld/ELF/ScriptParser.cpp

while (!errorCount() && !consume("}")) {
     } 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
-      expect("(");
+      if (peek() != "(")
+        setError("( expected, but got " + peek());
       cmd->filler = readFill();
-      expect(")");
     } else if (tok == "SORT") {
       readSort();
     } else if (tok == "INCLUDE") {
       readInclude();
     } else if (peek() == "(") {
       cmd->sectionCommands.push_back(readInputSectionDescription(tok));
     } else {
       // We have a file name and no input sections description. It is not a

 
 // 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.
+// Also, we require that expressions with operators must be wrapped into
+// round brackets. We did it to resolve the ambiguity when parsing scripts like:
+// SECTIONS { .foo : { ... } =120+3 /DISCARD/ : { ... } }
 std::array<uint8_t, 4> ScriptParser::readFill() {
-  uint64_t value = readExpr()().val;
+  uint64_t value = readPrimary()().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(), (uint32_t)value);
   return buf;
 }

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

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 
 ## Check that padding value works:
 # 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
 # YES: 66000011 22000011 22000011 22000011
 
-# RUN: echo "SECTIONS { .mysec : { *(.mysec*) } =0x1100+0x22 }" > %t.script
+# RUN: echo "SECTIONS { .mysec : { *(.mysec*) } =(0x1100+0x22) }" > %t.script
 # RUN: ld.lld -o %t.out --script %t.script %t
 # RUN: llvm-objdump -s %t.out | FileCheck --check-prefix=YES2 %s
 # YES2: 66000011 22000011 22000011 22000011
 
 ## Confirming that address was correct:
 # RUN: echo "SECTIONS { .mysec : { *(.mysec*) } =0x99887766 }" > %t.script
 # RUN: ld.lld -o %t.out --script %t.script %t
 # RUN: llvm-objdump -s %t.out | FileCheck --check-prefix=YES3 %s

 # RUN: not ld.lld -o /dev/null --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 /dev/null %t --script %t.script 2>&1 | FileCheck --check-prefix=ERR4 %s
 # ERR4: symbol not found: foo
 
+## Check we are able to parse scripts where "/DISCARD/" follows a section fill expression.
+# RUN: echo "SECTIONS { .mysec : { *(.mysec*) } =0x1122 /DISCARD/ : { *(.text) } }" > %t.script
+# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: llvm-objdump -s %t.out | FileCheck --check-prefix=YES %s
+
 .section        .mysec.1,"a"
 .align  16
 .byte   0x66
 
 .section        .mysec.2,"a"
 .align  16
 .byte   0x66
 
 .globl _start
 _start:
  nop