[ELF] Fix early overflow check in finalizeAddressDependentContent

[andcarminati]

Summary

LLD terminates with errors when it detects overflows in the
finalizeAddressDependentContent calculation. Although, sometimes, those errors
are not really errors, but an intermediate result of an ongoing address
calculation. If we continue the fixed-point algorithm we can converge to the
correct result.

This patch

• Removes the verification inside the fixed point algorithm.
• Calls checkMemoryRegions at the end.

[peter.smith]

May I suggest an alternative approach? Instead of checking the memory regions when assigning addresses, move the check to its own function, something like verifyMemoryRegions() this could be called once after finalizeAddressDependent Content. It would require fewer changes to the code and would be working on final addresses.

One possible disadvantage of this approach, but I think that they are likely shared with suppressing the errors on the first pass, is that the contents of a memory region could spill into the next one. This could lead to overlapping addresses which may cause a different, more difficult to understand, error message. I don't think that this will be the case today, but is a possibility.

lld/ELF/LinkerScript.h

328

boolean values threaded through the code can make the code difficult to understand when looking at the callsite. True or false implies some change in behaviour but not what it is.

If this has to be threaded through I suggest using an enum with a descriptive name.

lld/ELF/Writer.cpp

1603

This is likely sufficient for most cases, but could there be others that require more than one pass to converge?

lld/test/ELF/linkerscript/end-overflow-check.test

64

Are all of these symbol assignments required to trigger the error? If not, could this be cut down to a minimal set?

[andcarminati]

Comments were addressed.

[andcarminati]

In D152170#4396147, @peter.smith wrote:

May I suggest an alternative approach? Instead of checking the memory regions when assigning addresses, move the check to its own function, something like verifyMemoryRegions() this could be called once after finalizeAddressDependent Content. It would require fewer changes to the code and would be working on final addresses.

One possible disadvantage of this approach, but I think that they are likely shared with suppressing the errors on the first pass, is that the contents of a memory region could spill into the next one. This could lead to overlapping addresses which may cause a different, more difficult to understand, error message. I don't think that this will be the case today, but is a possibility.

Hi Peter, thank you for the comments, I followed your suggestion of one single function at the end.

[andcarminati]

lld/test/ELF/linkerscript/end-overflow-check.test

64

Hi, until this moment I couldn't reduce more than it (it was originally an arm application). The root cause is:

REGION1__SR_SHIFT = REGION1__REGION_SHIFT_WITH_SR - 3;
`

[peter.smith]

Thanks for the update. The code changes look reasonable to me. I'd ideally like to give a suggestion on how to simplify the test but I'm a bit short on time at the moment. Will try to come back soon. With luck one of the other reviewers will have a suggestion.

lld/test/ELF/linkerscript/end-overflow-check.test

64

That's unfortunate, at a cursory glance it looked like some of these wouldn't be needed.

It looks like the key symbols are REGION1PRE_ALIGNMENT and REGION1POST_ALIGNMENT is it possible to make an example that still tests the change in behaviour but is much simpler, even if the example is contrived?

The example as it stands is difficult to follow and I'm not sure what the answer is supposed to be without tracing it through to make sure I understand it.

[andcarminati]

*The code was improved.
*The test was simplified.

[andcarminati]

In D152170#4399685, @peter.smith wrote:

Thanks for the update. The code changes look reasonable to me. I'd ideally like to give a suggestion on how to simplify the test but I'm a bit short on time at the moment. Will try to come back soon. With luck one of the other reviewers will have a suggestion.

Hi @peter.smith, you are right. I reduced by half the expressions by removing everything that converged in the first round. What do you think?

[peter.smith]

Thanks for the updates. I've made a small suggestion to simplify the code.

lld/ELF/LinkerScript.cpp

1454

A suggestion that simplifies the code a little bit:

static void verifyMemoryRegion(const MemoryRegion *memoryRegion,
                               const OutputSection *osec, uint64_t addr) {
  uint64_t osecEnd = addr + osec->size;
  uint64_t regionEnd = memoryRegion->getOrigin() + memoryRegion->getLength();

  if (osecEnd > regionEnd) {
    error("section '" + osec->name + "' will not fit in region '" +
          memoryRegion->name + "': overflowed by " +
          Twine(osecEnd - regionEnd) + " bytes");
  }
}

void LinkerScript::verifyMemoryRegions() const {
  for (const OutputSection *sec : outputSections) {
    if (const MemoryRegion *memoryRegion = sec->memRegion)
      verifyMemoryRegion(memoryRegion, sec, sec->addr);
    if (const MemoryRegion *lmaRegion = sec->lmaRegion)
      verifyMemoryRegion(lmaRegion, sec, sec->getLMA());
  }
}

[andcarminati]

All comments were addressed.

[andcarminati]

In D152170#4403739, @peter.smith wrote:

Thanks for the updates. I've made a small suggestion to simplify the code.

Hi @peter.smith, thank you for this suggestion, it looks better now.

[peter.smith]

Looks good to me, thanks for the update. Will be worth waiting to see if MaskRay has any comments.

[MaskRay]

Thanks. The code looks good but the test needs simplification.

lld/ELF/LinkerScript.cpp

1456

delete the blank line after function argument list.

1459

delete this blank line as well.

lld/test/ELF/linkerscript/end-overflow-check.test

3

%ts is uncommon. rm -rf %t && split-file %s %t with optional && cd %t.

11

Omit ld.lld: for error messages.

47

Seems unused?

68

delete this blank line

84

Assigning to . with . = in an output section description has different semantics in ld.lld (and IMO GNU ld's semantics are inconsistent in some cases). Better to avoid the case. Use _abss ALIGN(...) :

[andcarminati]

All MaskRay's comments were addressed.

[MaskRay]

Some nits

lld/ELF/LinkerScript.cpp

1454

Just name the parameter region.

lld/ELF/LinkerScript.h

342

I think this is "Verify" instead of "Verify for". Actually, checkMemoryRegions is better as we have checkSections.

lld/test/ELF/linkerscript/end-overflow-check.test

7

75

I want to request further cleanup, but having some moderately complex tests in the testsuite seems fine as well to ensure that we can parse these constructs.

[andcarminati]

All MaskRay's comments were addressed.

[andcarminati]

If there are no more comments, can you kindly commit this change, when you have time @MaskRay ?

Author's detail:

git commit --amend --author='Andreu Carminati <[e-mail]>'

Thank you!

[andcarminati]

run git-clang-format

[MaskRay]

format summary

[kstoimenov]

Looks like this or D151802 broke the ubsan ARM bot: https://lab.llvm.org/buildbot/#/builders/238/builds/3938. Could you please revert or fix?

Thanks!

[peter.smith]

In D152170#4425256, @kstoimenov wrote:

Looks like this or D151802 broke the ubsan ARM bot: https://lab.llvm.org/buildbot/#/builders/238/builds/3938. Could you please revert or fix?

Thanks!

It would be this one. I suspect that it is the test rather than the code change:

REGION1__PADDED_SR_SIZE = MAX(1 << REGION1__PADDED_SR_SHIFT, 32);

Where REGION1_PADDED_SR_SIZE isn't known till the second pass.

I think in the short term the test could be modified to clamp REGION1__PADDED_SR_SHIFT to an in range value. More thought would need to be given to whether LLD can protect itself against out of range shifts coming from scripts. I expect this could get fixed within a day assuming the author or MaskRay is around, it is the end of the day here and I need to leave in 5 minutes so I'm not in a good place to take action myself.

[MaskRay]

In D152170#4425336, @peter.smith wrote:

In D152170#4425256, @kstoimenov wrote:

Looks like this or D151802 broke the ubsan ARM bot: https://lab.llvm.org/buildbot/#/builders/238/builds/3938. Could you please revert or fix?

Thanks!

It would be this one. I suspect that it is the test rather than the code change:

REGION1__PADDED_SR_SIZE = MAX(1 << REGION1__PADDED_SR_SHIFT, 32);

Where REGION1_PADDED_SR_SIZE isn't known till the second pass.

I think in the short term the test could be modified to clamp REGION1__PADDED_SR_SHIFT to an in range value. More thought would need to be given to whether LLD can protect itself against out of range shifts coming from scripts. I expect this could get fixed within a day assuming the author or MaskRay is around, it is the end of the day here and I need to leave in 5 minutes so I'm not in a good place to take action myself.

Thanks to both for the report and analysis. I pushed daba24ee7bd3d80f085e2e5f057af6b873a78a24 to fix the test.

[andcarminati]

In D152170#4425336, @peter.smith wrote:

In D152170#4425256, @kstoimenov wrote:

Looks like this or D151802 broke the ubsan ARM bot: https://lab.llvm.org/buildbot/#/builders/238/builds/3938. Could you please revert or fix?

Thanks!

It would be this one. I suspect that it is the test rather than the code change:

REGION1__PADDED_SR_SIZE = MAX(1 << REGION1__PADDED_SR_SHIFT, 32);

Where REGION1_PADDED_SR_SIZE isn't known till the second pass.

I think in the short term the test could be modified to clamp REGION1__PADDED_SR_SHIFT to an in range value. More thought would need to be given to whether LLD can protect itself against out of range shifts coming from scripts. I expect this could get fixed within a day assuming the author or MaskRay is around, it is the end of the day here and I need to leave in 5 minutes so I'm not in a good place to take action myself.

Thank you for the analysis @peter.smith.

[kstoimenov]

Build is green now. Thanks everyone!

lld/ELF/LinkerScript.h

public:
   void diagnoseOrphanHandling() const;
   void adjustOutputSections();
   void adjustSectionsAfterSorting();
 
   SmallVector<PhdrEntry *, 0> createPhdrs();
   bool needsInterpSection();
 
   bool shouldKeep(InputSectionBase *s);
   const Defined *assignAddresses();
   void allocateHeaders(SmallVector<PhdrEntry *, 0> &phdrs);
   void processSectionCommands();
   void processSymbolAssignments();
   void declareSymbols();
 
   bool isDiscarded(const OutputSection *sec) const;
 
   // Used to handle INSERT AFTER statements.
   void processInsertCommands();
 
   // Describe memory region usage.
   void printMemoryUsage(raw_ostream &os);
 
+  // Verify for memory/lma overflows.
+  void verifyMemoryRegions() const;
+
   // SECTIONS command list.
   SmallVector<SectionCommand *, 0> sectionCommands;
 
   // PHDRS command list.
   SmallVector<PhdrsCommand, 0> phdrsCommands;
 
   bool hasSectionsCommand = false;
   bool errorOnMissingSection = false;

lld/ELF/LinkerScript.cpp

if (!cmdRef)
     cmdRef = make<OutputDesc>(name, SHT_PROGBITS, 0);
   return cmdRef;
 }
 
 // Expands the memory region by the specified size.
 static void expandMemoryRegion(MemoryRegion *memRegion, uint64_t size,
                                StringRef secName) {
   memRegion->curPos += size;
-  uint64_t newSize = memRegion->curPos - memRegion->getOrigin();
-  uint64_t length = memRegion->getLength();
-  if (newSize > length)
-    error("section '" + secName + "' will not fit in region '" +
-          memRegion->name + "': overflowed by " + Twine(newSize - length) +
-          " bytes");
 }
 
 void LinkerScript::expandMemoryRegions(uint64_t size) {
   if (state->memRegion)
     expandMemoryRegion(state->memRegion, size, state->outSec->name);
   // Only expand the LMARegion if it is different from memRegion.
   if (state->lmaRegion && state->memRegion != state->lmaRegion)
     expandMemoryRegion(state->lmaRegion, size, state->outSec->name);
for (auto &pair : memoryRegions) {
     if (length != 0) {
       printSize(length);
       double percent = usedLength * 100.0 / length;
       os << "    " << format("%6.2f%%", percent);
     }
     os << '\n';
   }
 }
+
+static void verifyMemoryRegion(const MemoryRegion *memoryRegion,
+                               const OutputSection *osec, uint64_t addr) {
+
+  uint64_t osecEnd = addr + osec->size;
+  uint64_t regionEnd = memoryRegion->getOrigin() + memoryRegion->getLength();
+
+  if (osecEnd > regionEnd) {
+    error("section '" + osec->name + "' will not fit in region '" +
+          memoryRegion->name + "': overflowed by " +
+          Twine(osecEnd - regionEnd) + " bytes");
+  }
+}
+
+void LinkerScript::verifyMemoryRegions() const {
+  for (const OutputSection *sec : outputSections) {
+    if (const MemoryRegion *memoryRegion = sec->memRegion)
+      verifyMemoryRegion(memoryRegion, sec, sec->addr);
+    if (const MemoryRegion *lmaRegion = sec->lmaRegion)
+      verifyMemoryRegion(lmaRegion, sec, sec->getLMA());
+  }
+}

lld/ELF/Writer.cpp

 // addresses we must converge to a fixed point. We do that here. See the comment
 // in Writer<ELFT>::finalizeSections().
 template <class ELFT> void Writer<ELFT>::finalizeAddressDependentContent() {
   llvm::TimeTraceScope timeScope("Finalize address dependent content");
   ThunkCreator tc;
   AArch64Err843419Patcher a64p;
   ARMErr657417Patcher a32p;
   script->assignAddresses();
   // .ARM.exidx and SHF_LINK_ORDER do not require precise addresses, but they
   // do require the relative addresses of OutputSections because linker scripts
   // can assign Virtual Addresses to OutputSections that are not monotonically
   // increasing.
   for (Partition &part : partitions)
     finalizeSynthetic(part.armExidx.get());
   resolveShfLinkOrder();
 
   // Converts call x@GDPLT to call __tls_get_addr
template <class ELFT> void Writer<ELFT>::finalizeSections() {
   if (config->optimizeBBJumps)
     optimizeBasicBlockJumps();
 
   // Fill other section headers. The dynamic table is finalized
   // at the end because some tags like RELSZ depend on result
   // of finalizing other sections.
   for (OutputSection *sec : outputSections)
     sec->finalize();
+
+  script->verifyMemoryRegions();
 }
 
 // Ensure data sections are not mixed with executable sections when
 // --execute-only is used. --execute-only make pages executable but not
 // readable.
 template <class ELFT> void Writer<ELFT>::checkExecuteOnly() {
   if (!config->executeOnly)
     return;

lld/test/ELF/linkerscript/end-overflow-check.test

+REQUIRES: x86
+
+# RUN: split-file %s %ts
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %ts/a.s -o %ts/a.o
+
+# The error should be triggered only for the second test where the overflow really exists.
+
+RUN: ld.lld %ts/a.o -T %ts/b.lds -o /dev/null 2>&1
+RUN: not ld.lld %ts/a.o -T %ts/c.lds -o /dev/null 2>&1 | FileCheck --check-prefix=ERROR %s
+
+# ERROR: ld.lld: error: section '_abss' will not fit in region 'SRAM0': overflowed by 512 bytes
+# ERROR: ld.lld: error: section '.c.bss' will not fit in region 'SRAM0': overflowed by 512 bytes
+# ERROR: ld.lld: error: section '.text' will not fit in region 'SRAM0': overflowed by 513 bytes
+
+#--- a.s
+.section .a.bss, "aw", %nobits
+.globl abss
+abss:
+.zero 0xDF0
+.size abss, 0xDF0
+
+.section .b.bss, "aw", %nobits
+.globl abss
+bbss:
+.zero 16
+.size bbss, 16
+
+.section .c.bss, "aw", %nobits
+.globl cbss
+
+.text
+.globl _start
+_start:
+nop
+
+#--- b.lds
+
+MEMORY
+{
+    SRAM0 (rw) : ORIGIN = 0x20000400, LENGTH = 20K
+}
+
+SECTIONS
+{
+    _bbss 0x20001D60 :
+    {
+        REGION2_BEGIN = .;
+        *(.b.bss)
+        REGION2_END = .;
+    } > SRAM0
+    _abss :
+    {
+        REGION1__BEGIN = .; . = ALIGN(REGION1__PRE_ALIGNMENT); REGION1__ALIGNED_BEGIN = .; REGION1_ALIGNED_BEGIN = .;
+        *(.a.bss)
+        REGION1__END = .; . = ALIGN(REGION1__POST_ALIGNMENT); REGION1_ALIGNED_END = .;
+    } > SRAM0
+}
+
+
+REGION1__PRE_ALIGNMENT = 0x00000800;
+REGION1__PADDED_XOR = ((ABSOLUTE(REGION1__ALIGNED_BEGIN) | (ABSOLUTE(REGION1__END) - 1)) & ~(ABSOLUTE(REGION1__ALIGNED_BEGIN) & (ABSOLUTE(REGION1__END) - 1)));
+REGION1__PADDED_REGION_SHIFT = LOG2CEIL(REGION1__PADDED_XOR);
+REGION1__PADDED_SR_SHIFT = REGION1__PADDED_REGION_SHIFT - 3;
+REGION1__PADDED_SR_SIZE = MAX(1 << REGION1__PADDED_SR_SHIFT, 32);
+REGION1__POST_ALIGNMENT = REGION1__PADDED_SR_SIZE;
+
+#--- c.lds
+
+MEMORY
+{
+    SRAM0 (rw) : ORIGIN = 0x20000400, LENGTH = 10K
+}
+
+SECTIONS
+{
+    _bbss 0x20001D60 :
+    {
+        REGION2_BEGIN = .;
+        *(.b.bss)
+        REGION2_END = .;
+    } > SRAM0
+    _abss :
+    {
+        REGION1__BEGIN = .; . = ALIGN(REGION1__PRE_ALIGNMENT); REGION1__ALIGNED_BEGIN = .; REGION1_ALIGNED_BEGIN = .;
+        *(.a.bss)
+        REGION1__END = .; . = ALIGN(REGION1__POST_ALIGNMENT); REGION1_ALIGNED_END = .;
+    } > SRAM0
+}
+
+
+REGION1__PRE_ALIGNMENT = 0x00000800;
+REGION1__PADDED_XOR = ((ABSOLUTE(REGION1__ALIGNED_BEGIN) | (ABSOLUTE(REGION1__END) - 1)) & ~(ABSOLUTE(REGION1__ALIGNED_BEGIN) & (ABSOLUTE(REGION1__END) - 1)));
+REGION1__PADDED_REGION_SHIFT = LOG2CEIL(REGION1__PADDED_XOR);
+REGION1__PADDED_SR_SHIFT = REGION1__PADDED_REGION_SHIFT - 3;
+REGION1__PADDED_SR_SIZE = MAX(1 << REGION1__PADDED_SR_SHIFT, 32);
+REGION1__POST_ALIGNMENT = REGION1__PADDED_SR_SIZE;

lld/test/ELF/linkerscript/memory-err.s

 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 # RUN: echo 'MEMORY { name : ORIGIN = ., LENGTH = 1 }' > %t.script
 # RUN: not ld.lld -shared -o /dev/null -T %t.script %t.o 2>&1 | FileCheck --check-prefix=ERR_DOT %s
 # ERR_DOT: error: {{.*}}.script:1: unable to get location counter value
 
 ## ORIGIN/LENGTH can be simple symbolic expressions. If the expression
 ## requires interaction with memory regions, it may fail.
 
-# RUN: echo 'MEMORY { ram : ORIGIN = symbol, LENGTH = 4097 } \
+# RUN: echo 'MEMORY { ram : ORIGIN = symbol, LENGTH = 4094 } \
 # RUN: SECTIONS { \
 # RUN:   .text : { *(.text) } > ram \
 # RUN:   symbol = .; \
 # RUN:   .data : { *(.data) } > ram \
 # RUN: }' > %t.script
 # RUN: not ld.lld -T %t.script %t.o -o /dev/null 2>&1 | FileCheck --check-prefix=ERR_OVERFLOW %s
-# ERR_OVERFLOW: error: section '.text' will not fit in region 'ram': overflowed by 18446744073709547518 bytes
+# ERR_OVERFLOW: error: section '.data' will not fit in region 'ram': overflowed by 2 bytes
 
 nop
 
 .data
 .zero 4096