[ELF] - Linkerscript: restrict moving location counter backwards.

[grimar]

Summary

According to documentation,
"The location counter may not be moved backwards inside an output section, and may not be moved backwards outside of an output section if so doing creates areas with overlapping LMAs."

Currently we do not perform any overlaping checks and can produce broken binary if location counter was moved backward.
Also probably there is no reasons to support that checks at all. I suggest just to restrict moving location counter backwards in all cases.
Since we did not implement LC inside output sections yet, this patch implements that check for "outside of an output section" case.

[evgeny777]

Does anyone really wants this? There should be huge number of ways to make broken image besides this.
Also AFAIK the code below is valid:

.debug_info     0 : { *(.debug_info .gnu.linkonce.wi.*) }
.debug_abbrev   0 : { *(.debug_abbrev) }

And I wonder if it is different from this one (which, I guess, your patch is making invalid)

. = 0;
.debug_info  : { *(.debug_info .gnu.linkonce.wi.*) }
. = 0;
.debug_abbrev  : { *(.debug_abbrev) }

[grimar]

In D22961#500600, @evgeny777 wrote:

Does anyone really wants this? There should be huge number of ways to make broken image besides this.

Not sure that it is the reason not to try to fix at least something known.

Also AFAIK the code below is valid:

.debug_info     0 : { *(.debug_info .gnu.linkonce.wi.*) }
.debug_abbrev   0 : { *(.debug_abbrev) }

And I wonder if it is different from this one (which, I guess, your patch is making invalid)

. = 0;
.debug_info  : { *(.debug_info .gnu.linkonce.wi.*) }
. = 0;
.debug_abbrev  : { *(.debug_abbrev) }

Sections you mentioned are all non alloc I think. We can make an exception for them.
Interesting that gold ignores [address] for non allocatable sections at all.

[ruiu]

I'm also a bit skeptical if it's that useful. Even if we eventually want it, I think it's too early to add it.

[grimar]

Ok.

[grimar]

I found that it is important one.

For example FreeBSD scriopt ends with few debug sections which has 0 VA:
(https://svnweb.freebsd.org/base/head/sys/conf/ldscript.amd64?revision=284870&view=markup#l189)

.debug          0 : { *(.debug) }
.line           0 : { *(.line) }
...

Problem here that BSD script is not full, there are orphan sections. gold and ld use heuristic to place orphan sections
somewhere in the middle. LLD does not do that and we produce broken output here:

(sample)
[21] .debug_info       PROGBITS         0000000000000000  0125aada
       000000000229bf19  0000000000000000           0     0     1
  [22] .debug_abbrev     PROGBITS         0000000000000000  034f69f3
       000000000010e86f  0000000000000000           0     0     1
  [23] .debug_line       PROGBITS         0000000000000000  03605262
       0000000000320ce2  0000000000000000           0     0     1
  [24] .debug_frame      PROGBITS         0000000000000000  03925f48
       000000000010d2c0  0000000000000000           0     0     8
  [25] .debug_str        PROGBITS         0000000000000000  03a33208
       0000000000271f6f  0000000000000001  MS       0     0     1
  [26] .debug_loc        PROGBITS         0000000000000000  03ca5177
       0000000000e4b2a6  0000000000000000           0     0     1
  [27] .debug_macinfo    PROGBITS         0000000000000000  04af041d
       0000000000000000  0000000000000000           0     0     1
  [28] .debug_pubtypes   PROGBITS         0000000000000000  04af041d
       00000000003f4f2f  0000000000000000           0     0     1
  [29] .debug_ranges     PROGBITS         0000000000000000  04ee534c
       0000000000337490  0000000000000000           0     0     1
  [30] set_sysctl_set    PROGBITS         0000000000000000  0521d000
       0000000000003d40  0000000000000000   A       0     0     8
  [31] set_sysinit_set   PROGBITS         0000000000003d40  05220d40
       0000000000003448  0000000000000000   A       0     0     8
  [32] set_sysuninit_set PROGBITS         0000000000007188  05224188
       0000000000000f90  0000000000000000   A       0     0     8
  [33] set_modmetadata_s PROGBITS         0000000000008118  05225118
       0000000000002ee8  0000000000000000   A       0     0     8
  [34] set_ah_chips      PROGBITS         000000000000b000  05228000
       0000000000000048  0000000000000000   A       0     0     8
  [35] set_ah_rfs        PROGBITS         000000000000b048  05228048
       0000000000000050  0000000000000000   A       0     0     8
  [36] set_kbddriver_set PROGBITS         000000000000b098  05228098
       0000000000000018  0000000000000000   A       0     0     8
  [37] set_cons_set      PROGBITS         000000000000b0b0  052280b0
       0000000000000020  0000000000000000   A       0     0     8
  [38] usb_host_id       PROGBITS         000000000000b0e0  052280e0
       0000000000000040  0000000000000000   A       0     0     32
  [39] set_vt_drv_set    PROGBITS         000000000000b120  05228120
       0000000000000018  0000000000000000   A       0     0     8
  [40] set_sdt_providers PROGBITS         000000000000b138  05228138
       0000000000000080  0000000000000000   A       0     0     8
  [41] set_sdt_probes_se PROGBITS         000000000000b1b8  052281b8
       0000000000000f48  0000000000000000   A       0     0     8
...

So if we do not want to implement heursistics for orphans, I think we at least should implement
this check to prevent such situations and/or force users to provide full script in such cases.

[emaste]

Problem here that BSD script is not full, there are orphan sections. gold and ld use heuristic to place orphan sections
somewhere in the middle. LLD does not do that and we produce broken output here:

We'll want to address this in FreeBSD's linker script in general so that we don't have the orphan sections. I agree that a warning/error would be desirable here to aid in identifying and correcting these cases. I'm not sure off hand how to handle the __start_<section> symbol generation when including these sections in the linker script though.

[grimar]

In D22961#508415, @emaste wrote:

Problem here that BSD script is not full, there are orphan sections. gold and ld use heuristic to place orphan sections
somewhere in the middle. LLD does not do that and we produce broken output here:

We'll want to address this in FreeBSD's linker script in general so that we don't have the orphan sections. I agree that a warning/error would be desirable here to aid in identifying and correcting these cases. I'm not sure off hand how to handle the __start_<section> symbol generation when including these sections in the linker script though.

Just in case - I had to add next sections explicitly to BSD script.

set_sysctl_set             : { *(set_sysctl_set) }
set_sysinit_set            : { *(set_sysinit_set) }
set_sysuninit_set          : { *(set_sysuninit_set) }
set_modmetadata_set        : { *(set_modmetadata_set) } 
set_ah_chips               : { *(set_ah_chips) } 
set_ah_rfs                 : { *(set_ah_rfs) } 
set_kbddriver_set          : { *(set_kbddriver_set) } 
set_cons_set               : { *(set_cons_set) }   
usb_host_id                : { *(usb_host_id) }
set_vt_drv_set             : { *(set_vt_drv_set) } 
set_sdt_providers_set      : { *(set_sdt_providers_set) }   
set_sdt_probes_set         : { *(set_sdt_probes_set) } 
set_sdt_argtypes_set       : { *(set_sdt_argtypes_set) } 
set_kdb_dbbe_set           : { *(set_kdb_dbbe_set) } 
set_ratectl_set            : { *(set_ratectl_set) } 
set_crypto_set             : { *(set_crypto_set) } 
set_ieee80211_ioctl_getset : { *(set_ieee80211_ioctl_getset) } 
set_ieee80211_ioctl_setset : { *(set_ieee80211_ioctl_setset) } 
set_scanner_set            : { *(set_scanner_set) } 
set_videodriver_set        : { *(set_videodriver_set) } 
set_scterm_set             : { *(set_scterm_set) } 
set_scrndr_set             : { *(set_scrndr_set) } 
set_vga_set                : { *(set_vga_set) } 
kern_conf                  : { *(kern_conf) } 
set_pcpu                   : { *(set_pcpu) }

+ Also there one more unprocessed: .SUNW_ctf but it is not allocatable so I am fine it is added as orphan for me now. Generally for non allocatable sections it is probably ok to be orphans I think.

[davide]

In D22961#508592, @grimar wrote:

In D22961#508415, @emaste wrote:

Problem here that BSD script is not full, there are orphan sections. gold and ld use heuristic to place orphan sections
somewhere in the middle. LLD does not do that and we produce broken output here:

We'll want to address this in FreeBSD's linker script in general so that we don't have the orphan sections. I agree that a warning/error would be desirable here to aid in identifying and correcting these cases. I'm not sure off hand how to handle the __start_<section> symbol generation when including these sections in the linker script though.

Just in case - I had to add next sections explicitly to BSD script.

set_sysctl_set             : { *(set_sysctl_set) }
set_sysinit_set            : { *(set_sysinit_set) }
set_sysuninit_set          : { *(set_sysuninit_set) }
set_modmetadata_set        : { *(set_modmetadata_set) } 
set_ah_chips               : { *(set_ah_chips) } 
set_ah_rfs                 : { *(set_ah_rfs) } 
set_kbddriver_set          : { *(set_kbddriver_set) } 
set_cons_set               : { *(set_cons_set) }   
usb_host_id                : { *(usb_host_id) }
set_vt_drv_set             : { *(set_vt_drv_set) } 
set_sdt_providers_set      : { *(set_sdt_providers_set) }   
set_sdt_probes_set         : { *(set_sdt_probes_set) } 
set_sdt_argtypes_set       : { *(set_sdt_argtypes_set) } 
set_kdb_dbbe_set           : { *(set_kdb_dbbe_set) } 
set_ratectl_set            : { *(set_ratectl_set) } 
set_crypto_set             : { *(set_crypto_set) } 
set_ieee80211_ioctl_getset : { *(set_ieee80211_ioctl_getset) } 
set_ieee80211_ioctl_setset : { *(set_ieee80211_ioctl_setset) } 
set_scanner_set            : { *(set_scanner_set) } 
set_videodriver_set        : { *(set_videodriver_set) } 
set_scterm_set             : { *(set_scterm_set) } 
set_scrndr_set             : { *(set_scrndr_set) } 
set_vga_set                : { *(set_vga_set) } 
kern_conf                  : { *(kern_conf) } 
set_pcpu                   : { *(set_pcpu) }

+ Also there one more unprocessed: .SUNW_ctf but it is not allocatable so I am fine it is added as orphan for me now. Generally for non allocatable sections it is probably ok to be orphans I think.

I hit the same problem internally, on a codebase I don't own but I have to support. Sorry, I can't share it, but it's a kernel and it's very similar to the linker script provided by FreeBSD.
Setting the wrong VA causes the loader to be very confused. I think we should support this particular feature of ld.bfd in a bug-by-bug compatible fashion.
If FreeBSD can change his linker script, fine, great for them. But not everybody has the same luxury.

ELF/LinkerScript.cpp

for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
     bool RW = (Cmd->Constraint == ConstraintKind::ReadWrite);
 
     if ((RO && Writable) || (RW && !Writable))
       Sections.erase(It);
   }
   return Sections;
 }
 
+static uint64_t safeAssign(Expr Expr, uint64_t Dot) {
+  uint64_t Val = Expr(Dot);
+  if (Val < Dot)
+    error("location counter may not be moved backwards");
+  return Val;
+}
+
 template <class ELFT>
 void LinkerScript<ELFT>::assignAddresses(
     ArrayRef<OutputSectionBase<ELFT> *> Sections) {
   // Orphan sections are sections present in the input files which
   // are not explicitly placed into the output file by the linker script.
   // We place orphan sections at end of file.
   // Other linkers places them using some heuristics as described in
   // https://sourceware.org/binutils/docs/ld/Orphan-Sections.html#Orphan-Sections.
   for (OutputSectionBase<ELFT> *Sec : Sections) {
     StringRef Name = Sec->getName();
     if (getSectionIndex(Name) == INT_MAX)
       Opt.Commands.push_back(llvm::make_unique<OutputSectionCommand>(Name));
   }
 
   // Assign addresses as instructed by linker script SECTIONS sub-commands.
   Dot = Out<ELFT>::ElfHeader->getSize() + Out<ELFT>::ProgramHeaders->getSize();
   uintX_t MinVA = std::numeric_limits<uintX_t>::max();
   uintX_t ThreadBssOffset = 0;
 
   for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base.get())) {
-      if (Cmd->Name == ".") {
-        Dot = Cmd->Expression(Dot);
-      } else if (Cmd->Sym) {
+      if (Cmd->Name == ".")
+        Dot = safeAssign(Cmd->Expression, Dot);
+      else if (Cmd->Sym)
         cast<DefinedRegular<ELFT>>(Cmd->Sym)->Value = Cmd->Expression(Dot);
-      }
       continue;
     }
 
     // Find all the sections with required name. There can be more than
     // one section with such name, if the alignment, flags or type
     // attribute differs.
     auto *Cmd = cast<OutputSectionCommand>(Base.get());
     for (OutputSectionBase<ELFT> *Sec : Sections) {
       if (Sec->getName() != Cmd->Name)
         continue;
 
       if (Cmd->AddrExpr)
-        Dot = Cmd->AddrExpr(Dot);
+        Dot = safeAssign(Cmd->AddrExpr, Dot);
 
       if (Cmd->AlignExpr)
         Sec->updateAlignment(Cmd->AlignExpr(Dot));
 
       if ((Sec->getFlags() & SHF_TLS) && Sec->getType() == SHT_NOBITS) {
         uintX_t TVA = Dot + ThreadBssOffset;
         TVA = alignTo(TVA, Sec->getAlignment());
         Sec->setVA(TVA);

test/ELF/linkerscript/linkerscript-locationcounter-backward.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+
+# RUN: echo "SECTIONS { \
+# RUN:  . = 0x10000; \
+# RUN:  . = . - 1; \
+# RUN: }" > %t.script
+# RUN: not ld.lld -shared %t --script %t.script -o %t2 2>&1 | \
+# RUN:  FileCheck --check-prefix=ERR %s
+# ERR: location counter may not be moved backwards
+