[ELF] PR30221 - linker script expression parser does not accept '~'

[atanasyan]

Summary

The patch adds support for both '-' and '~' unary expressions. Also it brings support for signed numbers is expressions.

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

[grimar]

ELF/LinkerScript.cpp

1231

Do you need that cast ?
Looks both branches do the same ?

[grimar]

ELF/LinkerScript.cpp

1231

Ah I see, it is int, not uint.

[grimar]

This looks fine for me. The only note I have is that gold/ld does not
support ~ without () it seems. So the only form that works is:

~(...)

So you could write:

if (Tok == "~") {
  Expr E = readParenExpr();
  return [=](uint64_t Dot) { return ~E(Dot); };
}

I don't know what is more correct though and why gnu linkers does
not allow to write just ~XXX.

[atanasyan]

In D24128#531431, @grimar wrote:

This looks fine for me. The only note I have is that gold/ld does not
support ~ without () it seems. So the only form that works is:

Let's be consistent with gold/ld.

[atanasyan]

• Allow "~" operator if operand is surrounded by "()" to be consistent with gold/ld.

[ruiu]

ELF/LinkerScript.cpp

1230

I think you want to fix the tokenizer (tokenize in ScritpParser.cpp) instead of handling -<number> in this file. Currently, - is allowed to be part of a token, but it is not correct. For example, with that tokenizer, an expression 3-1 is tokenized as 3-1 instead of 3, - and 1.

I think the only token that can contain - as part of it is -=. In all other cases, - shouldn't stick with adjacent characters.

Because we do not support -= yet, we don't care about that. So why don't you remove - from tokenize()?

1266

Even if this is what gold does (I didn't test it myself), this looks very weird. If it's true, it seems a gold's bug. I think any primary expression should be allowed after ~.

[ruiu]

ELF/LinkerScript.cpp

1230

I was wrong. - is allowed to be in a filename as well as -l<library> notation. So - can be part of a token. I think I'm fine with this new function.

[grimar]

ELF/LinkerScript.cpp

1266

My consern about gold/ld is that users of lld can write some script using our syntax and have a problems if they decide to switch to gold/ld for some reason. I think it is always better to have script files fully compatible if it is possible.
Though it is always more convinent to write ~XXX then ~(XXX), therefore my position here is wonky.

[ruiu]

ELF/LinkerScript.cpp

1266

I tried

echo 'SECTIONS { foo = ~0; }' > x
echo 'int main() {}' | /ssd/clang/bin/clang -xc - -o /dev/null -fuse-ld=gold -Wl,--script=./x

and gold didn't complain the absence of () after ~. I believe you made a mistake.

~ operator is defined in gold's yyscript.y as follows.

exp:
        '(' exp ')'
          { $$ = $2; }
      | '-' exp %prec UNARY
          { $$ = script_exp_unary_minus($2); }
      | '!' exp %prec UNARY
          { $$ = script_exp_unary_logical_not($2); }
      | '~' exp %prec UNARY
          { $$ = script_exp_unary_bitwise_not($2); }
      | '+' exp %prec UNARY
          { $$ = $2; }
      | exp '*' exp
          { $$ = script_exp_binary_mult($1, $3); }
      | ...

As you can see, exp is expected after ~.

Finally, it just doesn't make sense to require ( only after ~ unary operator while any expression is allowed for other unary operators. If you design a language, you'd never do that.

[grimar]

ELF/LinkerScript.cpp

1266

Probably I made mistake that it was gold. But ld definetely does not like it:

. = 0x10000 + ~4;

test.script:3: undefined symbol `~4' referenced in expression

[grimar]

Though as I mentioned earlier, it is always more convinent to write ~XXX. And if gold is fine with that, we can choose either way I think. I just was really sure that both gold and ld rejectes that for some reason.

[ruiu]

ELF/LinkerScript.cpp

1266

That's a problem of the ld's tokenizer. The grammar still allows any expression after ~. Insert a space after ~, then you'll find that () is not actually required after ~.

[grimar]

ELF/LinkerScript.cpp

1266

I see. Interesting :)

[atanasyan]

• Move recognition of negative number to the readInteger routine
• Revert support of '~' operator without '()'

[ruiu]

LGTM

ELF/LinkerScript.cpp

if (S == "COMMONPAGESIZE")
     return Target->PageSize;
   if (S == "MAXPAGESIZE")
     return Target->MaxPageSize;
   error("unknown constant: " + S);
   return 0;
 }
 
 // Parses Tok as an integer. Returns true if successful.
 // It recognizes hexadecimal (prefixed with "0x" or suffixed with "H")
 // and decimal numbers. Decimal numbers may have "K" (kilo) or
 // "M" (mega) prefixes.
 static bool readInteger(StringRef Tok, uint64_t &Result) {
+  if (Tok.startswith("-")) {
+    if (!readInteger(Tok.substr(1), Result))
+      return false;
+    Result = -Result;
+    return true;
+  }
   if (Tok.startswith_lower("0x"))
     return !Tok.substr(2).getAsInteger(16, Result);
   if (Tok.endswith_lower("H"))
     return !Tok.drop_back().getAsInteger(16, Result);
 
   int Suffix = 1;
   if (Tok.endswith_lower("K")) {
     Suffix = 1024;

 }
 
 Expr ScriptParser::readPrimary() {
   if (peek() == "(")
     return readParenExpr();
 
   StringRef Tok = next();
 
+  if (Tok == "~") {
+    Expr E = readPrimary();
+    return [=](uint64_t Dot) { return ~E(Dot); };
+  }
+  if (Tok == "-") {
+    Expr E = readPrimary();
+    return [=](uint64_t Dot) { return -E(Dot); };
+  }
+
   // Built-in functions are parsed here.
   // https://sourceware.org/binutils/docs/ld/Builtin-Functions.html.
   if (Tok == "ADDR") {
     expect("(");
     StringRef Name = next();
     expect(")");
     return [=](uint64_t Dot) { return getSectionAddress(Name); };
   }

test/ELF/linkerscript/locationcounter.s

 # RUN:  . = CONSTANT (COMMONPAGESIZE) * 0x25; \
 # RUN:  .commonpagesize : { *(.commonpagesize) } \
 # RUN:  . = DATA_SEGMENT_ALIGN (CONSTANT (MAXPAGESIZE), CONSTANT (COMMONPAGESIZE)); \
 # RUN:  .datasegmentalign : { *(.datasegmentalign) } \
 # RUN:  . = DATA_SEGMENT_END (.); \
 # RUN:  . = 0x27000; \
 # RUN:  . += 0x1000; \
 # RUN:  .plusassign : { *(.plusassign) } \
+# RUN:  . = ((. + 0x1fff) & ~(0x1000 + -1)); \
+# RUN:  .unary : { *(.unary) } \
 # RUN: }" > %t.script
 # RUN: ld.lld %t --script %t.script -o %t2
 # RUN: llvm-readobj -s %t2 | FileCheck %s
 
 # CHECK: Section {
 # CHECK:   Index: 1
 # CHECK:   Name: .plus
 # CHECK-NEXT:   Type: SHT_PROGBITS

 # CHECK-NEXT:   Address: 0x28000
 # CHECK-NEXT:   Offset:
 # CHECK-NEXT:   Size:
 # CHECK-NEXT:   Link:
 # CHECK-NEXT:   Info:
 # CHECK-NEXT:   AddressAlignment:
 # CHECK-NEXT:   EntrySize:
 # CHECK-NEXT: }
+# CHECK-NEXT: Section {
+# CHECK-NEXT:   Index:
+# CHECK-NEXT:   Name: .unary
+# CHECK-NEXT:   Type: SHT_PROGBITS
+# CHECK-NEXT:   Flags [
+# CHECK-NEXT:     SHF_ALLOC
+# CHECK-NEXT:   ]
+# CHECK-NEXT:   Address: 0x2A000
+# CHECK-NEXT:   Offset:
+# CHECK-NEXT:   Size:
+# CHECK-NEXT:   Link:
+# CHECK-NEXT:   Info:
+# CHECK-NEXT:   AddressAlignment:
+# CHECK-NEXT:   EntrySize:
+# CHECK-NEXT: }
 
 ## Mailformed number error.
 # RUN: echo "SECTIONS { \
 # RUN:  . = 0x12Q41; \
 # RUN: }" > %t.script
 # RUN: not ld.lld %t --script %t.script -o %t2 2>&1 | \
 # RUN:  FileCheck --check-prefix=NUMERR %s
 # NUMERR: malformed number: 0x12Q41

 .section .commonpagesize, "a"
 .quad 0
 
 .section .datasegmentalign, "a"
 .quad 0
 
 .section .plusassign, "a"
 .quad 0
+
+.section .unary, "a"
+.quad 0

test/ELF/linkerscript/symbol-assignexpr.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 
 # RUN: echo "SECTIONS { \
 # RUN:         symbol = CONSTANT(MAXPAGESIZE); \
 # RUN:         symbol2 = symbol + 0x1234; \
 # RUN:         symbol3 = symbol2; \
+# RUN:         symbol4 = symbol + -4; \
+# RUN:         symbol5 = symbol - ~ 0xfffb; \
+# RUN:         symbol6 = symbol - ~(0xfff0 + 0xb); \
+# RUN:         symbol7 = symbol - ~ 0xfffb + 4; \
+# RUN:         symbol8 = ~ 0xffff + 4; \
+# RUN:         symbol9 = - 4; \
+# RUN:         symbol10 = 0xfedcba9876543210; \
+# RUN:         symbol11 = ((0x28000 + 0x1fff) & ~(0x1000 + -1)); \
 # RUN:       }" > %t.script
 # RUN: ld.lld -o %t1 --script %t.script %t
 # RUN: llvm-objdump -t %t1 | FileCheck %s
 
 # CHECK:      SYMBOL TABLE:
 # CHECK-NEXT: 0000000000000000 *UND* 00000000
 # CHECK-NEXT: 0000000000000120 .text 00000000 _start
 # CHECK-NEXT: 0000000000000121 .text 00000000 foo
 # CHECK-NEXT: 0000000000200000 *ABS* 00000000 symbol
 # CHECK-NEXT: 0000000000201234 *ABS* 00000000 symbol2
 # CHECK-NEXT: 0000000000201234 *ABS* 00000000 symbol3
+# CHECK-NEXT: 00000000001ffffc *ABS* 00000000 symbol4
+# CHECK-NEXT: 000000000020fffc *ABS* 00000000 symbol5
+# CHECK-NEXT: 000000000020fffc *ABS* 00000000 symbol6
+# CHECK-NEXT: 0000000000210000 *ABS* 00000000 symbol7
+# CHECK-NEXT: ffffffffffff0004 *ABS* 00000000 symbol8
+# CHECK-NEXT: fffffffffffffffc *ABS* 00000000 symbol9
+# CHECK-NEXT: fedcba9876543210 *ABS* 00000000 symbol10
+# CHECK-NEXT: 0000000000029000 *ABS* 00000000 symbol11
 
 # RUN: echo "SECTIONS { \
 # RUN:         symbol2 = symbol; \
 # RUN:       }" > %t2.script
 # RUN: not ld.lld -o %t2 --script %t2.script %t 2>&1 \
 # RUN:  | FileCheck -check-prefix=ERR %s
 # ERR: symbol not found: symbol
 
 .global _start
 _start:
  nop
 
 .global foo
 foo: