[ELF] Fix incorrect deduplication of MergeSyntheticSection's

[andrewng]

Summary

The Data member of MergeSyntheticSection, which is used by ICF to check
equality of section contents, is always empty. This can result in
incorrect and dangerous deduplication when using --icf=all and
--ignore-data-address-equality.

This simple fix populates the Data of MergeSyntheticSection with the
intended contents in finalizeContents and uses Data for writeTo.

Fixes bug PR36910.

[• espindola]

Seems reasonable. I will just do a quick check on the performance impact.

[• espindola]

test/ELF/icf-not-equal-merged-sections.s

7

The test would be a bit more dependable if you checked the content of the output with objdump/readelf/readobj.

As written the test would still pass if we changed the icf message and regressed this fix.

[andrewng]

In D44898#1048263, @espindola wrote:

Seems reasonable. I will just do a quick check on the performance impact.

Yes, that would be my only concern too, but I decided to keep it simple first.

test/ELF/icf-not-equal-merged-sections.s

7

Good point! I will look at adding this.

[andrewng]

Updated test to address review comments.

[• espindola]

ELF/SyntheticSections.cpp

2442

At least clang is not finding an operator new[] to use. I had to manually call the Allocate function for this to build:

new (BAlloc.Allocate<uint8_t>(Size)) uint8_t[Size]

I guess we could also add new[] to Support/Allocator.h

[andrewng]

Updated to fix issue with clang compilation.

[• espindola]

LGTM.

Some tests got a bit faster (clang) and some a bit slower (scylla).

[ruiu]

Doesn't this increase lld's memory usage significantly? Mergeable string table tend to be large, and it seems with this patch you keep a copy of an entire section in memory.

[• espindola]

In D44898#1048634, @ruiu wrote:

Doesn't this increase lld's memory usage significantly? Mergeable string table tend to be large, and it seems with this patch you keep a copy of an entire section in memory.

True. That would be a reasonable explanation for scylla getting slower.

We could inspect the individual buffers in the StringTableBuilders, but it is not clear if it is worth it.

Maybe the best option is just disabling ICF of synthetic sections?

[ruiu]

How much did Scylla get slower?

Maybe the best option is just disabling ICF of synthetic sections?

That sounds like a better way of fixing the issue.

[andrewng]

In D44898#1048688, @ruiu wrote:

How much did Scylla get slower?

Maybe the best option is just disabling ICF of synthetic sections?

That sounds like a better way of fixing the issue.

Yes, for large mergeable sections, this could significantly increase memory usage.

Disabling ICF for synthetic sections would be a way to fix the issue and I don't think it would have much negative impact in practice, i.e. ICF of these sections is not common.

[• espindola]

In D44898#1048688, @ruiu wrote:

How much did Scylla get slower?

2.8%. Somehow clang-fsds got 2.39% faster.

page faults got worse on all test cases, but on scylla they got worse by 15%. That is consistent with the extra allocations being responsible for the slowdown.

[ruiu]

2.8%. Somehow clang-fsds got 2.39% faster.

That speedup is interesting. I don't have a good theory to explain it though.

Even if this patch is somewhat performance-neutral, we still should avoid extra memory allocation if we can. Let's try ignoring synthetic sections in ICF. That's I think better.

[andrewng]

In D44898#1048789, @ruiu wrote:

2.8%. Somehow clang-fsds got 2.39% faster.

That speedup is interesting. I don't have a good theory to explain it though.

Even if this patch is somewhat performance-neutral, we still should avoid extra memory allocation if we can. Let's try ignoring synthetic sections in ICF. That's I think better.

Alternative fix here: D44923.

[• espindola]

We can close this one, right?

[andrewng]

Abandoned in favour of D44923.

ELF/SyntheticSections.h

 
 // MergeSyntheticSection is a class that allows us to put mergeable sections
 // with different attributes in a single output sections. To do that
 // we put them into MergeSyntheticSection synthetic input sections which are
 // attached to regular output sections.
 class MergeSyntheticSection : public SyntheticSection {
 public:
   void addSection(MergeInputSection *MS);
+  void writeTo(uint8_t *Buf) override;
 
 protected:
   MergeSyntheticSection(StringRef Name, uint32_t Type, uint64_t Flags,
                         uint32_t Alignment)
       : SyntheticSection(Flags, Type, Alignment, Name) {}
 
   std::vector<MergeInputSection *> Sections;
 };
 
 class MergeTailSection final : public MergeSyntheticSection {
 public:
   MergeTailSection(StringRef Name, uint32_t Type, uint64_t Flags,
                    uint32_t Alignment);
 
   size_t getSize() const override;
-  void writeTo(uint8_t *Buf) override;
   void finalizeContents() override;
 
 private:
   llvm::StringTableBuilder Builder;
 };
 
 class MergeNoTailSection final : public MergeSyntheticSection {
 public:
   MergeNoTailSection(StringRef Name, uint32_t Type, uint64_t Flags,
                      uint32_t Alignment)
       : MergeSyntheticSection(Name, Type, Flags, Alignment) {}
 
   size_t getSize() const override { return Size; }
-  void writeTo(uint8_t *Buf) override;
   void finalizeContents() override;
 
 private:
   // We use the most significant bits of a hash as a shard ID.
   // The reason why we don't want to use the least significant bits is
   // because DenseMap also uses lower bits to determine a bucket ID.
   // If we use lower bits, it significantly increases the probability of
   // hash collisons.

ELF/SyntheticSections.cpp

template <class ELFT> bool VersionNeedSection<ELFT>::empty() const {
   return getNeedNum() == 0;
 }
 
 void MergeSyntheticSection::addSection(MergeInputSection *MS) {
   MS->Parent = this;
   Sections.push_back(MS);
 }
 
+void MergeSyntheticSection::writeTo(uint8_t *Buf) {
+  memcpy(Buf, Data.data(), Data.size());
+}
+
 MergeTailSection::MergeTailSection(StringRef Name, uint32_t Type,
                                    uint64_t Flags, uint32_t Alignment)
     : MergeSyntheticSection(Name, Type, Flags, Alignment),
       Builder(StringTableBuilder::RAW, Alignment) {}
 
 size_t MergeTailSection::getSize() const { return Builder.getSize(); }
 
-void MergeTailSection::writeTo(uint8_t *Buf) { Builder.write(Buf); }
-
 void MergeTailSection::finalizeContents() {
   // Add all string pieces to the string table builder to create section
   // contents.
   for (MergeInputSection *Sec : Sections)
     for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I)
       if (Sec->Pieces[I].Live)
         Builder.add(Sec->getData(I));
 
   // Fix the string table content. After this, the contents will never change.
   Builder.finalize();
 
   // finalize() fixed tail-optimized strings, so we can now get
   // offsets of strings. Get an offset for each string and save it
   // to a corresponding StringPiece for easy access.
   for (MergeInputSection *Sec : Sections)
     for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I)
       if (Sec->Pieces[I].Live)
         Sec->Pieces[I].OutputOff = Builder.getOffset(Sec->getData(I));
-}
 
-void MergeNoTailSection::writeTo(uint8_t *Buf) {
-  for (size_t I = 0; I < NumShards; ++I)
-    Shards[I].write(Buf + ShardOffsets[I]);
+  // Populate data.
+  size_t Size = Builder.getSize();
+  uint8_t *Buf = BAlloc.Allocate<uint8_t>(Size);
+  Data = ArrayRef<uint8_t>(Buf, Size);
+  memset(Buf, 0, Size);
+  Builder.write(Buf);
 }
 
 // This function is very hot (i.e. it can take several seconds to finish)
 // because sometimes the number of inputs is in an order of magnitude of
 // millions. So, we use multi-threading.
 //
 // For any strings S and T, we know S is not mergeable with T if S's hash
 // value is different from T's. If that's the case, we can safely put S and
void MergeNoTailSection::finalizeContents() {
   // So far, section pieces have offsets from beginning of shards, but
   // we want offsets from beginning of the whole section. Fix them.
   parallelForEach(Sections, [&](MergeInputSection *Sec) {
     for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I)
       if (Sec->Pieces[I].Live)
         Sec->Pieces[I].OutputOff +=
             ShardOffsets[getShardId(Sec->Pieces[I].Hash)];
   });
+
+  // Populate data.
+  uint8_t *Buf = BAlloc.Allocate<uint8_t>(Size);
+  Data = ArrayRef<uint8_t>(Buf, Size);
+  memset(Buf, 0, Size);
+  for (size_t I = 0; I < NumShards; ++I)
+    Shards[I].write(Buf + ShardOffsets[I]);
 }
 
 static MergeSyntheticSection *createMergeSynthetic(StringRef Name,
                                                    uint32_t Type,
                                                    uint64_t Flags,
                                                    uint32_t Alignment) {
   bool ShouldTailMerge = (Flags & SHF_STRINGS) && Config->Optimize >= 2;
   if (ShouldTailMerge)

test/ELF/icf-not-equal-merged-sections.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
+# RUN: ld.lld %t.o -o %t --icf=all --ignore-data-address-equality --print-icf-sections | FileCheck -allow-empty %s
+# RUN: llvm-readobj -s -section-data %t | FileCheck --check-prefix=NODEDUP %s
+
+# CHECK-NOT: selected section <internal>:(.rodata)
+
+# NODEDUP:      Name: .rodata
+# NODEDUP-NEXT: Type: SHT_PROGBITS
+# NODEDUP-NEXT: Flags [
+# NODEDUP-NEXT:   SHF_ALLOC
+# NODEDUP-NEXT:   SHF_MERGE
+# NODEDUP-NEXT: ]
+# NODEDUP-NEXT: Address:
+# NODEDUP-NEXT: Offset:
+# NODEDUP-NEXT: Size: 16
+# NODEDUP-NEXT: Link:
+# NODEDUP-NEXT: Info:
+# NODEDUP-NEXT: AddressAlignment: 8
+# NODEDUP-NEXT: EntrySize: 0
+# NODEDUP-NEXT: SectionData (
+# NODEDUP-NEXT:   0000: 77665544 33221100 67452301 10325476
+# NODEDUP-NEXT: )
+
+.section .rodata.cst4,"aM",@progbits,4
+rodata4:
+  .long 0x00112233
+  .long 0x44556677
+  .long 0x00112233
+  .long 0x44556677
+
+.section .rodata.cst8,"aM",@progbits,8
+rodata8:
+  .long 0x01234567
+  .long 0x76543210