[LLD] LLD can report "unable to move location counter backward" error too early

[PiJoules]

I have the following linker script:

MEMORY
{
  ...
  RAM_DATA               (RW)  : ORIGIN = 0x20008000, LENGTH = 0x004F8000
  ...
}

ram_data_end      = ORIGIN(RAM_DATA) + LENGTH(RAM_DATA);

SECTIONS {
  ...  // other output sections like text, rodata, etc
  __etext = .;
  __DATA_ROM = .;
  __end_of_code_in_ram_data =
      ABSOLUTE(__etext - ORIGIN(RAM_CODE) + ORIGIN(RAM_DATA));
  .data __end_of_code_in_ram_data : AT(__DATA_ROM) ALIGN(4) {
    __data_start__ = .;
    *(.data);
    *(.data*);
    ...  // stuff placed here
    __data_end__ = .;        /* define a global symbol at data end */
  } > RAM_DATA

  .shared_ram.unused_space (NOLOAD) : ALIGN(4) {
    . = ABSOLUTE(ram_data_end);
  } >RAM_DATA

  ... // other output sections
}

which would often report this error: unable to move location counter backward for: .shared_ram.unused_space. This is because on the first call to script->assignAddresses(); in finalizeAddressDependentContent, all of the input data sections placed into .data exceeds the remaining space for RAM_DATA, so by the time we reach . = ABSOLUTE(ram_data_end);, DOT is well past the end of RAM_DATA.

However, on subsequent calls to script->assignAddresses() in the fixed-point loop in finalizeAddressDependentContent, the start of .data is changed and a smaller value than the first iteration because something was changed in previous sections. This could be from linker relaxations, sections being removed, allocation sizes changing, etc. Because the starting address of .data is smaller but all the input data sections remain the same, it's possible for subsequent runs of script->assignAddresses() to not throw the same error because it happens to fit.

The issue here is that lld will still throw this error from the first run even though all the sections can fit as expected in the final memory region after the fixed point loop has finished. I think the right approach here is that LLD should only return this error if DOT ends up moving backwards for the final call to this function, similar to how we delay checking of memory region sizes until the very end of linking.

TODO: Come up with a public-facing minimal reproducer. I haven't made one yet because it's too hard.

[PiJoules]

@MaskRay

[MaskRay]

The problem in the linker script is:

  .ARM : {
    __exidx_start = .;
    *(.ARM.exidx*)
    __exidx_end = .;

  } > RAM_CODE

The size of .ARM can shrink after finalizeSynthetic(part.armExidx.get()); in finalizeAddressDependentContent. In the initial assignAddresses (before finalizeSynthetic(part.armExidx.get());) run, addresses are over-estimated so dot can be larger than . = ABSOLUTE(ram_data_end); expects.

I was about to send a similar patch, but I want to construct a minimal test first. Therefore, I suggested

  .shared_ram.unused_space (NOLOAD) : ALIGN(4) {
    . += ram_data_end > . ? ram_data_end - . : 0;
  } >RAM_DATA

as a temporary workaround.

[llvmbot]

@llvm/issue-subscribers-lld-elf

I have the following linker script:

MEMORY
{
  ...
  RAM_DATA               (RW)  : ORIGIN = 0x20008000, LENGTH = 0x004F8000
  ...
}

ram_data_end      = ORIGIN(RAM_DATA) + LENGTH(RAM_DATA);

SECTIONS {
  ...  // other output sections like text, rodata, etc
  __etext = .;
  __DATA_ROM = .;
  __end_of_code_in_ram_data =
      ABSOLUTE(__etext - ORIGIN(RAM_CODE) + ORIGIN(RAM_DATA));
  .data __end_of_code_in_ram_data : AT(__DATA_ROM) ALIGN(4) {
    __data_start__ = .;
    *(.data);
    *(.data*);
    ...  // stuff placed here
    __data_end__ = .;        /* define a global symbol at data end */
  } > RAM_DATA

  .shared_ram.unused_space (NOLOAD) : ALIGN(4) {
    . = ABSOLUTE(ram_data_end);
  } >RAM_DATA

  ... // other output sections
}

which would often report this error: unable to move location counter backward for: .shared_ram.unused_space. This is because on the first call to script->assignAddresses(); in finalizeAddressDependentContent, all of the input data sections placed into .data exceeds the remaining space for RAM_DATA, so by the time we reach . = ABSOLUTE(ram_data_end);, DOT is well past the end of RAM_DATA.

However, on subsequent calls to script->assignAddresses() in the fixed-point loop in finalizeAddressDependentContent, the start of .data is changed and a smaller value than the first iteration because something was changed in previous sections. This could be from linker relaxations, sections being removed, allocation sizes changing, etc. Because the starting address of .data is smaller but all the input data sections remain the same, it's possible for subsequent runs of script->assignAddresses() to not throw the same error because it happens to fit.

The issue here is that lld will still throw this error from the first run even though all the sections can fit as expected in the final memory region after the fixed point loop has finished. I think the right approach here is that LLD should only return this error if DOT ends up moving backwards for the final call to this function, similar to how we delay checking of memory region sizes until the very end of linking.

TODO: Come up with a public-facing minimal reproducer. I haven't made one yet because it's too hard.