[ELF] - Dedupliсate FDEs correctly when two sections are ICFed

[grimar]

Summary

This is PR34518,

Previously when LLD ICFed 2 sections it leaved 2 duplicate entries in .eh_frame
pointing to the same address. After that it "deduplicated" them from .eh_frame_header,
adjusting the amount of valid FDEs in its header.
As a result excessive entries in .eh_frame and excessive dummy data in .eh_frame_header
was emited to output. Patch fixes that.

[ruiu]

ELF/SyntheticSections.cpp

459–460

You are making this attribute-accessing function non-idempotent, which is generally bad. Again, instead of "fixing" a problem, you want to think harder to find out what this function should do. Please implement in a different way.

[grimar]

• Reimplemented according to review comments.

[ruiu]

I don't think this is in the right direction. This seems too slow and too complicated. Why don't you just skip FDEs whose section IS does not satisfy IS == IS->Repl? Usually IS == IS->Repl, but if IS has been merged by ICF, IS != IS->Repl, so you can easily identify if a given section has been merged by ICF.

That said, first of all, do you think you are doing is right? It seems that the current ICF code merges two different functions that are otherwise identical except FDEs. We should take FDEs into account when comparing functions in ICF, shouldn't we? (I'm not saying that you should update this patch, but I want you to think.)

ELF/SyntheticSections.cpp

436

This temporary variable is redundant.

[grimar]

In D37848#874114, @ruiu wrote:

I don't think this is in the right direction. This seems too slow and too complicated. Why don't you just skip FDEs whose section IS does not satisfy IS == IS->Repl? Usually IS == IS->Repl, but if IS has been merged by ICF, IS != IS->Repl, so you can easily identify if a given section has been merged by ICF.

Honestly that was the first I thought of when started to work on the fix. I faced with breakage of eh-frame-hdr-icf.s that time.
Given its code:

.globl _start, f1, f2
_start:
  ret

.section .text.f1, "ax"
f1:
  .cfi_startproc
  ret
  .cfi_endproc

.section .text.f2, "ax"
f2:
  .cfi_startproc
  ret
  .cfi_endproc

ICF merged both .text.f1 and .text.f2 to .text. That way simple checking of IS == IS->Repl would just omit both two FDEs we have here.
I supposed that it is not correct and that we can leave single FDE and use its data then. Since FDE describes
"how to unwind to the caller if the current instruction pointer is in the range covered by the FDE." I supposed it is fine to use it.
I did not think that it can be ICF issue here. ICF stands for "identical code folding", I did not think about we should take FDE data into account
when doing ICF.
Just like we do not support --icf=safe currently (and so far ICF is not safe anyways), I supposed we can assume that FDE data for identical code can be reused.

FWIW I just checked gold's behavior and it seems it is to use FDE of section that is alive after ICF. For case above it just drops both FDEs, but if we have 2
sections with different FDEs it uses the first FDE in order and ICF eliminates the second section. That also makes me think FDEs can be reused.

That said, first of all, do you think you are doing is right? It seems that the current ICF code merges two different functions that are otherwise identical except FDEs.
We should take FDEs into account when comparing functions in ICF, shouldn't we? (I'm not saying that you should update this patch, but I want you to think.)

Given above I am not sure that we should do that. Taking FDEs into account is probably safest possible way to handle things, but I am not sure it is worth that as it may
slow down ICF and make its results to be worse.
If that path be chosen that seems we also need to check that their CIEs are the same as it should be possible to have different personality functions for example.

[ruiu]

You are saying that it is not correct to merge a .text section with other .text section if one has an FDE and the other doesn't. But you are also saying that we should merge two .text sections if both have FDEs even if their FDE contents are different. These two statements does not sound consistent to me. I don't think I'm convinced.

If you are saying that checking existence of FDEs is enough, can you argue why that is enough? If not, you could write code to demonstrate a problem (I guess you could write code that uses exceptions and behaves differently when two sections are merged by ICF) so that we can fix it. I don't think this patch fixes a real problem.

[grimar]

In D37848#875500, @ruiu wrote:

You are saying that it is not correct to merge a .text section with other .text section if one has an FDE and the other doesn't.

No I did not :) What I was trying to say is that it is seems to me strange that we can merge such sections and lose valid FDE in result.
And so I *supposed* we should merge them but keep and use valid FDE. That is actually what code currently do. If we have 3 identical code sections,
and one of them does not have FDE, then all 3 be merged, and both 2 FDEs be placed to .eh_frame and one of FDEs will be filtered out
from .eh_frame_hdr finally.

But you are also saying that we should merge two .text sections if both have FDEs even if their FDE contents are different. These two statements does not sound consistent to me. I don't think I'm convinced.

That is what we already do and it works. I can make synthetic testcase which will break it (can corrupt one of FDEs for example),
but synthetic case is probably not the good reason to change current behavior. Especially when we know that gold also just uses one of FDEs,
so behavior is probably acceptable.

If you are saying that checking existence of FDEs is enough, can you argue why that is enough? If not, you could write code to demonstrate a problem (I guess you could write code that uses exceptions and behaves differently when two sections are merged by ICF) so that we can fix it. I don't think this patch fixes a real problem.

Patch fixes the real problem which is about redundant FDE entries LLD currently emits. We emit redundant duplicate entries in .eh_frame and have to adjust .eh_frame_hdr which also contains garbage data at its end.
So we have output larger it can be currently.

As mentioned earlier in previous comments, simpler approach can be used: just skip FDEs whose section IS does not satisfy IS == IS->Repl,
but I can prepare the sample to demonstrate the possible problem that can happen then.
It is also unfortunately a bit synthetic.
I tried to use -fno-asynchronous-unwind-tables flag to omit .eh_frame from output (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=43232),
but it does not omit it for me. So what can be used to demonstrate the difference is next code:

int test() {
  try {
    throw 1;
  }catch(...){}
 return 0;
}

If I compile 2 files with the same test() and test1() to asm and drop .eh_frame from one of them manually. Then ICF will combine test() and test1().
Then depending on order of objects in inputs there will be either zero FDEs or single one in ouput I believe.

So my question is then - since testcase is synthetic, should we care about it ?
If no then I think I agree we can just check IS == IS->Repl for now.

[ruiu]

That is what we already do and it works. I can make synthetic testcase which will break it (can corrupt one of FDEs for example),
but synthetic case is probably not the good reason to change current behavior. Especially when we know that gold also just uses one of FDEs,
so behavior is probably acceptable.

It may not work, and that's what we are talking about. What gold or other linkers do don't really matter when we are talking about what is the correct behavior.

First of all, no optimization should change any program's defined behavior. Non-safe ICF does not really satisfy as it could break pointer equality, but it is described. It's akin to -ffast-math flag that allows compilers to do unsafe optimizations. But still, it shouldn't break any assumption that is not described. Naturally, it shouldn't change exception handler's behavior, for example.

I wonder if you really understood my point. What I was saying that, if two functions have different FDEs, we probably shouldn't merge these functions because merging them could change their behavior when exception is thrown. We are not talking about the current lld's or gold's behavior but what it should be. Are we on the same page?

[grimar]

In D37848#878146, @ruiu wrote:

I wonder if you really understood my point. What I was saying that, if two functions have different FDEs, we probably shouldn't merge these functions because merging them could change their behavior when exception is thrown. We are not talking about the current lld's or gold's behavior but what it should be. Are we on the same page?

Now - yes.
I'll be happy to try to reimplement this patch to change how ICF handles sections with/without FDEs to most correct way then.

[grimar]

Abandoning. Will try to reimplement in according to discussed way.

ELF/SyntheticSections.cpp

CieRecord *EhFrameSection<ELFT>::addCie(EhSectionPiece &Piece,
   // If not found, create a new one.
   if (Cie->Piece == nullptr) {
     Cie->Piece = &Piece;
     Cies.push_back(Cie);
   }
   return Cie;
 }
 
+template <class ELFT, class RelTy>
+static InputSectionBase *getRelocTarget(InputSectionBase *Sec, RelTy &Rel) {
+  SymbolBody &B = Sec->template getFile<ELFT>()->getRelocTargetSym(Rel);
+  auto *D = dyn_cast<DefinedRegular>(&B);
+  if (!D || !D->Section)
+    return nullptr;
+  auto *Target =
+      cast<InputSectionBase>(cast<InputSectionBase>(D->Section)->Repl);
+  return Target;
+}
+
 // There is one FDE per function. Returns true if a given FDE
 // points to a live function.
 template <class ELFT>
 template <class RelTy>
 bool EhFrameSection<ELFT>::isFdeLive(EhSectionPiece &Piece,
                                      ArrayRef<RelTy> Rels) {
   auto *Sec = cast<EhInputSection>(Piece.ID);
   unsigned FirstRelI = Piece.FirstRelocation;
 
   // An FDE should point to some function because FDEs are to describe
   // functions. That's however not always the case due to an issue of
   // ld.gold with -r. ld.gold may discard only functions and leave their
   // corresponding FDEs, which results in creating bad .eh_frame sections.
   // To deal with that, we ignore such FDEs.
   if (FirstRelI == (unsigned)-1)
     return false;
 
-  const RelTy &Rel = Rels[FirstRelI];
-  SymbolBody &B = Sec->template getFile<ELFT>()->getRelocTargetSym(Rel);
-  auto *D = dyn_cast<DefinedRegular>(&B);
-  if (!D || !D->Section)
-    return false;
-  auto *Target =
-      cast<InputSectionBase>(cast<InputSectionBase>(D->Section)->Repl);
+  InputSectionBase *Target = getRelocTarget<ELFT>(Sec, Rels[FirstRelI]);
   return Target && Target->Live;
 }
 
 // .eh_frame is a sequence of CIE or FDE records. In general, there
 // is one CIE record per input object file which is followed by
 // a list of FDEs. This function searches an existing CIE or create a new
 // one and associates FDEs to the CIE.
 template <class ELFT>
 template <class RelTy>
 void EhFrameSection<ELFT>::addSectionAux(EhInputSection *Sec,
for (EhSectionPiece &Piece : Sec->Pieces) {
     uint32_t CieOffset = Offset + 4 - ID;
     CieRecord *Cie = OffsetToCie[CieOffset];
     if (!Cie)
       fatal(toString(Sec) + ": invalid CIE reference");
 
     if (!isFdeLive(Piece, Rels))
       continue;
     Cie->FdePieces.push_back(&Piece);
-    NumFdes++;
   }
 }
 
 template <class ELFT>
 void EhFrameSection<ELFT>::addSection(InputSectionBase *C) {
   auto *Sec = cast<EhInputSection>(C);
   Sec->Parent = this;
   updateAlignment(Sec->Alignment);
static void writeCieFde(uint8_t *Buf, ArrayRef<uint8_t> D) {
   const endianness E = ELFT::TargetEndianness;
   write32<E>(Buf, Aligned - 4);
 }
 
 template <class ELFT> void EhFrameSection<ELFT>::finalizeContents() {
   if (this->Size)
     return; // Already finalized.
 
+  llvm::DenseSet<std::pair<InputSectionBase *, int64_t>> UniqueFdeMap;
   size_t Off = 0;
   for (CieRecord *Cie : Cies) {
     Cie->Piece->OutputOff = Off;
     Off += alignTo(Cie->Piece->size(), Config->Wordsize);
 
-    for (EhSectionPiece *Fde : Cie->FdePieces) {
+    // DIE entries are uniquified by address this FDE applies. We uniquify pairs
+    // of sections where FDE function resides in and appropriate relocation
+    // addends. That allows to filter out excessive duplicate FDE entries.
+    for (EhSectionPiece *&Fde : Cie->FdePieces) {
+      InputSectionBase *Sec = Fde->ID;
+      std::pair<InputSectionBase *, int64_t> P;
+      if (Sec->AreRelocsRela) {
+        auto &Rel = Sec->template relas<ELFT>()[Fde->FirstRelocation];
+        P = {getRelocTarget<ELFT>(Sec, Rel), getAddend<ELFT>(Rel)};
+      } else {
+        auto &Rel = Sec->template rels<ELFT>()[Fde->FirstRelocation];
+        P = {getRelocTarget<ELFT>(Sec, Rel), getAddend<ELFT>(Rel)};
+      }
+
+      if (UniqueFdeMap.insert(P).second) {
         Fde->OutputOff = Off;
         Off += alignTo(Fde->size(), Config->Wordsize);
+        continue;
       }
+      Fde = nullptr;
+    }
+
+    llvm::erase_if(Cie->FdePieces, [](EhSectionPiece *P) { return !P; });
+    NumFdes += Cie->FdePieces.size();
   }
 
   // The LSB standard does not allow a .eh_frame section with zero
   // Call Frame Information records. Therefore add a CIE record length
   // 0 as a terminator if this .eh_frame section is empty.
   if (Off == 0)
     Off = 4;
 

 
 // .eh_frame_hdr contains a binary search table of pointers to FDEs.
 // Each entry of the search table consists of two values,
 // the starting PC from where FDEs covers, and the FDE's address.
 // It is sorted by PC.
 template <class ELFT> void EhFrameHeader<ELFT>::writeTo(uint8_t *Buf) {
   const endianness E = ELFT::TargetEndianness;
 
-  // Sort the FDE list by their PC and uniqueify. Usually there is only
-  // one FDE for a PC (i.e. function), but if ICF merges two functions
-  // into one, there can be more than one FDEs pointing to the address.
+  // Sort the FDE list by their PC.
   auto Less = [](const FdeData &A, const FdeData &B) { return A.Pc < B.Pc; };
   std::stable_sort(Fdes.begin(), Fdes.end(), Less);
-  auto Eq = [](const FdeData &A, const FdeData &B) { return A.Pc == B.Pc; };
-  Fdes.erase(std::unique(Fdes.begin(), Fdes.end(), Eq), Fdes.end());
+  assert(std::unique(Fdes.begin(), Fdes.end(),
+                     [](const FdeData &A, const FdeData &B) {
+                       return A.Pc == B.Pc;
+                     }) == Fdes.end());
 
   Buf[0] = 1;
   Buf[1] = DW_EH_PE_pcrel | DW_EH_PE_sdata4;
   Buf[2] = DW_EH_PE_udata4;
   Buf[3] = DW_EH_PE_datarel | DW_EH_PE_sdata4;
   write32<E>(Buf + 4, In<ELFT>::EhFrame->getParent()->Addr - this->getVA() - 4);
   write32<E>(Buf + 8, Fdes.size());
   Buf += 12;

test/ELF/eh-frame-hdr-icf-fde.s

+# REQUIRES: x86
+
+## Testcase checks that we correctly deduplicate FDEs when ICF
+## merges two sections.
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t2 --icf=all --eh-frame-hdr
+# RUN: llvm-readobj -r %t | FileCheck %s --check-prefix=OBJ
+# RUN: llvm-readobj -s -section-data %t2 | FileCheck %s
+
+# OBJ:      Relocations [
+# OBJ-NEXT:   Section {{.*}} .rela.eh_frame {
+# OBJ-NEXT:     0x20 R_X86_64_PC32 .text.f1 0x0
+# OBJ-NEXT:     0x34 R_X86_64_PC32 .text.f1 0x2
+# OBJ-NEXT:     0x48 R_X86_64_PC32 .text.f2 0x0
+# OBJ-NEXT:     0x5C R_X86_64_PC32 .text.f2 0x2
+# OBJ-NEXT:   }
+# OBJ-NEXT: ]
+
+# CHECK:      Section {
+# CHECK:        Index: 1
+# CHECK:        Name: .eh_frame_hdr
+# CHECK-NEXT:   Type: SHT_PROGBITS
+# CHECK-NEXT:   Flags [
+# CHECK-NEXT:     SHF_ALLOC
+# CHECK-NEXT:   ]
+# CHECK-NEXT:   Address: 0x200158
+# CHECK-NEXT:   Offset: 0x158
+# CHECK-NEXT:   Size: 28
+# CHECK-NEXT:   Link: 0
+# CHECK-NEXT:   Info: 0
+# CHECK-NEXT:   AddressAlignment:
+# CHECK-NEXT:   EntrySize: 0
+# CHECK-NEXT:   SectionData (
+# CHECK-NEXT:     0000: 011B033B 1C000000 02000000 A80E0000
+##                               ^        ^-- FDE(1) PC
+##                               ^-- Number of FDEs
+# CHECK-NEXT:     0010: 38000000 AA0E0000 50000000
+##                               ^-- FDE(2) PC
+# CHECK-NEXT:   )
+# CHECK-NEXT: }
+## FDE(1) == 0x201000 - .eh_frame_hdr(0x200158) = 0xEA8
+## FDE(2) == 0x201000 - .eh_frame_hdr(0x200158) + 2(relocation addend) = 0xEAA
+
+## Check .eh_frame contains CIE and two FDEs remaining after ICF.
+# CHECK-NEXT: Section {
+# CHECK-NEXT:   Index: 2
+# CHECK-NEXT:   Name: .eh_frame
+# CHECK-NEXT:   Type: SHT_PROGBITS
+# CHECK-NEXT:   Flags [
+# CHECK-NEXT:     SHF_ALLOC
+# CHECK-NEXT:   ]
+# CHECK-NEXT:   Address: 0x200178
+# CHECK-NEXT:   Offset: 0x178
+# CHECK-NEXT:   Size: 72
+# CHECK-NEXT:   Link: 0
+# CHECK-NEXT:   Info: 0
+# CHECK-NEXT:   AddressAlignment: 8
+# CHECK-NEXT:   EntrySize: 0
+# CHECK-NEXT:   SectionData (
+# CHECK-NEXT:     0000: 14000000 00000000 017A5200 01781001
+# CHECK-NEXT:     0010: 1B0C0708 90010000 14000000 1C000000
+# CHECK-NEXT:     0020: 680E0000 01000000 00000000 00000000
+# CHECK-NEXT:     0030: 14000000 34000000 520E0000 01000000
+# CHECK-NEXT:     0040: 00000000 00000000
+# CHECK-NEXT:   )
+# CHECK-NEXT: }
+
+# CHECK:     Section {
+# CHECK:       Index:
+# CHECK:       Name: .text
+# CHECK-NEXT:  Type: SHT_PROGBITS
+# CHECK-NEXT:  Flags [
+# CHECK-NEXT:    SHF_ALLOC
+# CHECK-NEXT:    SHF_EXECINSTR
+# CHECK-NEXT:  ]
+# CHECK-NEXT:  Address: 0x201000
+
+.section .text.f1, "ax"
+.cfi_startproc
+nop
+.cfi_endproc
+nop
+.cfi_startproc
+ret
+.cfi_endproc
+
+.section .text.f2, "ax"
+.cfi_startproc
+nop
+.cfi_endproc
+nop
+.cfi_startproc
+ret
+.cfi_endproc

test/ELF/eh-frame-hdr-icf.s

 # REQUIRES: x86
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 # RUN: ld.lld %t -o %t2 --icf=all --eh-frame-hdr
-# RUN: llvm-objdump -s %t2 | FileCheck %s
+# RUN: llvm-objdump -s -section-headers %t2 | FileCheck %s
+
+## Check there is a only one FDE in .eh_frame_hdr and no any dummy data.
+##        Name          Size
+# CHECK: .eh_frame_hdr 00000014
 
 # CHECK: Contents of section .eh_frame_hdr:
-# CHECK-NEXT: 200158 011b033b 1c000000 01000000 a80e0000
+# CHECK-NEXT: 200158 011b033b 14000000 01000000
 #                                      ^ FDE count
-# CHECK-NEXT: 200168 38000000 00000000 00000000
-#                    ^ FDE for f2
 
 .globl _start, f1, f2
 _start:
   ret
 
 .section .text.f1, "ax"
 f1:
   .cfi_startproc
   ret
   .cfi_endproc
 
 .section .text.f2, "ax"
 f2:
   .cfi_startproc
   ret
   .cfi_endproc