[LLD] Check for too large offsets into merge sections earlier to avoid DenseMap tombstone collision

[bd1976llvm]

Summary

This patch moves the checking for too large offsets into merge sections earlier.

Without this change the large offset generated in the added test-case will cause an assert (as it happens to be a value reserved as a "tombstone" in the DenseMap implementation) when OffsetMap is queried in getSectionPiece().

To simplify the code and avoid future mistakes I have refactored so that there is only one function that looks up offsets in the OffsetMap.

[ruiu]

LGTM

[grimar]

LGTM.

ELF/InputSection.cpp

1154 ↗

(On Diff #162251)

I think it could be error, but I see that would require a bit more changes, so I would do that in follow up.

[ruiu]

fatal() should be fine because that line is not unreachable unless you don't pass a corrupted input file.

lld/trunk/ELF/InputSection.cpp

while (Size != 1) {
     size_t H = Size / 2;
     const It MI = First + H;
     Size -= H;
     First = Comp(Value, *MI) ? First : First + H;
   }
   return Comp(Value, *First) ? First : First + 1;
 }
 
-// Do binary search to get a section piece at a given input offset.
-static SectionPiece *findSectionPiece(MergeInputSection *Sec, uint64_t Offset) {
-  if (Sec->Data.size() <= Offset)
-    fatal(toString(Sec) + ": entry is past the end of the section");
-
-  // Find the element this offset points to.
-  auto I = fastUpperBound(
-      Sec->Pieces.begin(), Sec->Pieces.end(), Offset,
-      [](const uint64_t &A, const SectionPiece &B) { return A < B.InputOff; });
-  --I;
-  return &*I;
-}
-
 SectionPiece *MergeInputSection::getSectionPiece(uint64_t Offset) {
+  if (this->Data.size() <= Offset)
+    fatal(toString(this) + ": offset is outside the section");
+
   // Find a piece starting at a given offset.
   auto It = OffsetMap.find(Offset);
   if (It != OffsetMap.end())
     return &Pieces[It->second];
 
   // If Offset is not at beginning of a section piece, it is not in the map.
-  // In that case we need to search from the original section piece vector.
-  return findSectionPiece(this, Offset);
+  // In that case we need to  do a binary search of the original section piece vector.
+  auto I = fastUpperBound(
+      Pieces.begin(), Pieces.end(), Offset,
+      [](const uint64_t &A, const SectionPiece &B) { return A < B.InputOff; });
+  --I;
+  return &*I;
 }
 
 // Returns the offset in an output section for a given input offset.
 // Because contents of a mergeable section is not contiguous in output,
 // it is not just an addition to a base output offset.
 uint64_t MergeInputSection::getParentOffset(uint64_t Offset) const {
-  // Find a string starting at a given offset.
-  auto It = OffsetMap.find(Offset);
-  if (It != OffsetMap.end())
-    return Pieces[It->second].OutputOff;
-
   // If Offset is not at beginning of a section piece, it is not in the map.
   // In that case we need to search from the original section piece vector.
   const SectionPiece &Piece =
-      *findSectionPiece(const_cast<MergeInputSection *>(this), Offset);
+      *(const_cast<MergeInputSection *>(this)->getSectionPiece (Offset));
   uint64_t Addend = Offset - Piece.InputOff;
   return Piece.OutputOff + Addend;
 }
 
 template InputSection::InputSection(ObjFile<ELF32LE> &, const ELF32LE::Shdr &,
                                     StringRef);
 template InputSection::InputSection(ObjFile<ELF32BE> &, const ELF32BE::Shdr &,
                                     StringRef);

lld/trunk/test/ELF/merge-string-error.s

 // REQUIRES: x86
 // RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
 // RUN: not ld.lld %t.o -o /dev/null -shared 2>&1 | FileCheck %s
 
         .section  .rodata.str1.1,"aMS",@progbits,1
   .asciz  "abc"
 
         .data
         .long .rodata.str1.1 + 4
 
-// CHECK: merge-string-error.s.tmp.o:(.rodata.str1.1): entry is past the end of the section
+// CHECK: merge-string-error.s.tmp.o:(.rodata.str1.1): offset is outside the section

lld/trunk/test/ELF/relocation-past-merge-end.s

 // REQUIRES: x86
 // RUN: llvm-mc %s -o %t.o -filetype=obj -triple=x86_64-pc-linux
 // RUN: not ld.lld %t.o -o /dev/null -shared 2>&1 | FileCheck %s
-// CHECK: relocation-past-merge-end.s.tmp.o:(.foo): entry is past the end of the section
+// CHECK: relocation-past-merge-end.s.tmp.o:(.foo): offset is outside the section
 
 .data
 .long .foo + 10
 .section  .foo,"aM",@progbits,4
 .quad 0