[ELF] Support .rela.eh_frame with unordered r_offset values

[MaskRay]

Summary

GNU ld -r can create .rela.eh_frame with unordered r_offset values.
(With LLD, we can craft such a case by reordering sections in .eh_frame.)
This is currently unsupported and will trigger
assert(pieces[i].inputOff <= off ... in OffsetGetter::get
(the content is corrupted in a -DLLVM_ENABLE_ASSERTIONS=off build).
This patch supports this case.

[MaskRay]

lld/ELF/InputSection.cpp

1329

It is unfortunate that there are two pieces of code.
RelTy is parametric so we cannot add a member in EhInputSection caching the input relocations.

[jhenderson]

Can (and if so should - perhaps not) we avoid this patch by fixing the input in the first place? Under what circumstances can the relocations appear out of order?

lld/ELF/InputSection.cpp

1329

I might be missing something, but surely you could have some templated function that would allow you to avoid the code duplication at least?

1335

This sounds like this check could cost quite a bit in a large link. Have you done any performance comparisons of before and after of such a link? Given that the normal case is that things are sorted, I think we need to be somewhat careful here. Same goes below.

[peter.smith]

My understanding is that there is no requirement in ELF for relocations being in r_offset order even if that is how must object producers naturally generate them. This would make the inputs legal if unconventional. Although I have no numbers I'd expect a linear scan of the relocations for just EHInputSection with little computation to be small, but of course every linear scan costs. It may be possible to set a flag in EHInputSection after the first llvm::is_sorted so that only one test for the relocations being sorted is necessary.

One possible alternative, although I have little confidence it would be a better solution, is to effectively run something like a cut down scanRelocs() early for EHInputSections only. This would need to be done prior to split(). This could by construction ensure the relocations in EHInputSection were added in r_offset order and split() could use these relocations.

[MaskRay]

In D101116#2711479, @jhenderson wrote:

Can (and if so should - perhaps not) we avoid this patch by fixing the input in the first place? Under what circumstances can the relocations appear out of order?

GNU ld -r can create out of order .rela.eh_frame, even if I *don't* use a construct like .eh_frame : { *b.o(.eh_frame) *a.o(.eh_frame) }.

This sounds like this check could cost quite a bit in a large link.

I cannot observe any performance difference adding a linear scan.

lld/ELF/InputSection.cpp

1329

Not clear the trade-off is worthwhile. The template function needs to live in one header (our usage are in two .cpp files). On the other hand, there are only few lines and allocating a SmallVector and rels = sorted; cannot be dropped with a common function.

[jhenderson]

lld/ELF/InputSection.cpp

1329

The assignment can be folded in with the function call easily enough, I think. The advantage is that we don't have two places doing the same thing, potentially resulting in the code diverging in future patches. It also allows for future code reuse, and it seems not implausible we'll need this sorting elsewhere in the future.

template <typename RelTy>
ArrayRef<RelTy> sortRels(ArrayRef<RelTy> rels, ArrayRef<RelTy> storage) {
  auto cmp = [](const RelTy &a, const RelTy &b) {
    return a.r_offset < b.r_offset;
  };
  if (!llvm::is_sorted(rels, cmp)) {
    sorted.assign(rels.begin(), rels.end());
    llvm::stable_sort(storage, cmp);
    rels = sorted;
  }
  return rels;
}

template <class ELFT, class RelTy>
void EhInputSection::split(ArrayRef<RelTy> rels) {
  SmallVector<RelTy, 0> sorted;
  rels = sortRels(rels, sorted);
  ...
}

[MaskRay]

add a template helper

[jhenderson]

LGTM!

lld/ELF/InputSection.cpp

template <class ELFT> void EhInputSection::split() {
   if (areRelocsRela)
     split<ELFT>(relas<ELFT>());
   else
     split<ELFT>(rels<ELFT>());
 }
 
 template <class ELFT, class RelTy>
 void EhInputSection::split(ArrayRef<RelTy> rels) {
+  // getReloc expects the relocations to be sorted by r_offset. See the comment
+  // in scanRelocs.
+  SmallVector<RelTy, 0> storage;
+  rels = sortRels(rels, storage);
+
   unsigned relI = 0;
   for (size_t off = 0, end = data().size(); off != end;) {
     size_t size = readEhRecordSize(this, off);
     pieces.emplace_back(off, this, size, getReloc(off, size, rels, relI));
     // The empty record is the end marker.
     if (size == 4)
       break;
     off += size;
   }
 }

lld/ELF/Relocations.h

 template <class ELFT>
 static inline int64_t getAddend(const typename ELFT::Rel &rel) {
   return 0;
 }
 template <class ELFT>
 static inline int64_t getAddend(const typename ELFT::Rela &rel) {
   return rel.r_addend;
 }
+
+template <typename RelTy>
+ArrayRef<RelTy> sortRels(ArrayRef<RelTy> rels, SmallVector<RelTy, 0> &storage) {
+  auto cmp = [](const RelTy &a, const RelTy &b) {
+    return a.r_offset < b.r_offset;
+  };
+  if (!llvm::is_sorted(rels, cmp)) {
+    storage.assign(rels.begin(), rels.end());
+    llvm::stable_sort(storage, cmp);
+    rels = storage;
+  }
+  return rels;
+}
 } // namespace elf
 } // namespace lld
 
 #endif

lld/ELF/Relocations.cpp

static void scanRelocs(InputSectionBase &sec, ArrayRef<RelTy> rels) {
   OffsetGetter getOffset(sec);
 
   // Not all relocations end up in Sec.Relocations, but a lot do.
   sec.relocations.reserve(rels.size());
 
   if (config->emachine == EM_PPC64)
     checkPPC64TLSRelax<RelTy>(sec, rels);
 
+  // For EhInputSection, OffsetGetter expects the relocations to be sorted by
+  // r_offset. In rare cases (.eh_frame pieces are reordered by a linker
+  // script), the relocations may be unordered.
+  SmallVector<RelTy, 0> storage;
+  if (isa<EhInputSection>(sec))
+    rels = sortRels(rels, storage);
+
   for (auto i = rels.begin(), end = rels.end(); i != end;)
     scanReloc<ELFT>(sec, getOffset, i, rels.begin(), end);
 
   // Sort relocations by offset for more efficient searching for
   // R_RISCV_PCREL_HI20 and R_PPC64_ADDR64.
   if (config->emachine == EM_RISCV ||
       (config->emachine == EM_PPC64 && sec.name == ".toc"))
     llvm::stable_sort(sec.relocations,

lld/test/ELF/eh-frame-unordered-r_offset.s

+# REQUIRES: x86
+# RUN: split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %t/a.s -o %t/a.o
+# RUN: cp %t/a.o %t/b.o
+# RUN: ld.lld -r -T %t/lds %t/a.o %t/b.o -o %t/c.o
+# RUN: llvm-readelf -r %t/c.o | FileCheck %s --check-prefix=REL
+
+## If we swap two input .eh_frame, the r_offset values in relocations will be
+## unordered.
+# REL:          Offset
+# REL-NEXT: 0000000000000050
+# REL-NEXT: 0000000000000020
+
+## Test we can handle the rare case.
+# RUN: ld.lld %t/c.o -o %t/c
+# RUN: llvm-dwarfdump --eh-frame %t/c | FileCheck %s
+
+# CHECK: 00000000 00000014 00000000 CIE
+# CHECK: 00000018 00000014 0000001c FDE cie=00000000
+# CHECK: 00000030 00000014 00000034 FDE cie=00000000
+
+#--- a.s
+.cfi_startproc
+nop
+.cfi_endproc
+
+#--- lds
+SECTIONS {
+  .eh_frame : { *b.o(.eh_frame) *a.o(.eh_frame) }
+}