[ELF] - Support of compressed input sections implemented.

[grimar]

Summary

Patch implements support of zlib style compressed sections.
SHF_COMPRESSED flag is used to recognize that decompression is required.
After that decompression is performed and flag is removed from output.

[grimar]

test/ELF/compressed-debug.s

37 ↗

(On Diff #57292)

I will update that place with correct constant name as soon as D20273 be landed.

[ruiu]

This patch uncompresses all input sections whether they are going to be added to the output or not. A lot of sections are in fact not going to make it to the output because of comdat deduplication and section gc. So uncompressing all inputs beforehand would be a waste of resource.

Until the content is copied to the output, I think we don't have to uncompress inputs. Do you think you can do it lazily?

[hjl.tools]

Until the content is copied to the output, I think we don't have to uncompress inputs. Do you think you can do it lazily?

It should be done on demand transparently. You only need to decompress input
when getting the input contents.

[ruiu]

Also please try to minimize the number of data copies. In this patch, compressed data is uncompressed to a buffer in memory and then copied to an mmap'ed output file. So the data is copied twice. It can be just once -- you can uncompress data directly to the mmap'ed output.

[ruiu]

It's also worth to mention that you could utilize multiple cores if you uncompress sections in writeTo() since writeTo() is parallelized for each input section when --thread is given. Since uncompressing gzipped data is fairly CPU intensive task, I'd expect it would make the linker noticeable faster when handling compressed sections.

[grimar]

In D20272#430485, @ruiu wrote:

This patch uncompresses all input sections whether they are going to be added to the output or not. A lot of sections are in fact not going to make it to the output because of comdat deduplication and section gc. So uncompressing all inputs beforehand would be a waste of resource.

Until the content is copied to the output, I think we don't have to uncompress inputs. Do you think you can do it lazily?

Thank you for this and other comments about the patch. I want to assure you that this time I was aware about most of details you wrote :)

There were 2 reasons from my side why I implemented it in this way:

1. MergeOutputSection requires early access to uncompressed data. It uses it in constructor, it uses it in InputSectionBase<ELFT>::getOffset() and in other places. I am currently investigating how it is possible to improve that. I am pretty sure we do not want to have different logic for compressed/uncompressed sections, so I hope to refactor how MergeOutputSection works at first then. I mean that we probably want to delay the access to data as much as we can here. That was technical problem I faced, but I was sure it is not a problem for implementation way I used because of next:

2. I was thinking that since compressed sections are used for compressing debug stuff, then nobody really cares about perfomance. That is something I am missing probably, but if we are talking about linkage speed during development process, then I assume that compression probably not involved. Compression-decompression takes time, and hdd space it too much cheap to use that. But when we switch to generating "production" binary using some inputs with debugging sources, then I assumed there is not much sence to save few percents (probably) of final time if we can keep code simple instead. Please point me what I missing here.

Anyways, I am currently investigating the MergeOutputSection logic, I hope to be able to refactor it a bit. I am hard in commenting here, I still need to investigate that.

[ruiu]

Do compressed and mergeable sections exist? If the combination of the two doesn't exist in the real world, we can simply reject that.

I think performance matters even with compressed debug info. For example, if you are doing distributed build, you may want to reduce the network traffic by compressing large debug sections to reduce the overall build time (sending small files is faster than larger ones).

[grimar]

In D20272#430820, @ruiu wrote:

Do compressed and mergeable sections exist?

That was the main case I debugged..

[grimar]

In D20272#430820, @ruiu wrote:

Do compressed and mergeable sections exist?

So I mean that testcase for patch was created from real world code and it has that, unfortunately or not.

[ruiu]

OK, but compressed sections shouldn't be uncompressed until they need to be. At the symbol resolution phase, we don't need any section contents (and at the phase and gc phase, a lot of sections are eliminated.)

[grimar]

In D20272#430837, @ruiu wrote:

OK, but compressed sections shouldn't be uncompressed until they need to be. At the symbol resolution phase, we don't need any section contents (and at the phase and gc phase, a lot of sections are eliminated.)

Right now the first major place I am looking how to avoid is:

>template <class ELFT> void Writer<ELFT>::run() {
>  copyLocalSymbols();
>> includeInSymtab()
....

  if (auto *S = dyn_cast<MergeInputSection<ELFT>>(D->Section))
    if (S->getRangeAndSize(D->Value).first->second ==
        MergeInputSection<ELFT>::PieceDead)
      return false;
}

I probably do not want to comment it because still investigating it, I just have a guess that we can avoid uncompression here and just check if whole section is dead or not instead of if checking if PieceDead. I am not ready to continue that thoughts now, still looking at, I am not familar with that code yet :)

[grimar]

So just please let me to spend some time on this, I am sure will able to suggest something to improve this patch.

[grimar]

I`ll update this right after relanding D20331 (which is currently reverted and waits for D20466, which is under review).

[grimar]

• Reworked testcase.
• Rebased patch to support latest changes about mergable sections.

[grimar]

llvm-mc changes required for testcase of this were reverted in r270638. I am looking into it, will ping/update this one after resolving that.

[grimar]

• Updated testcase after r270987, which updated llvm-mc to work with both zlib, zlib-gnu. Now I think this patch is ready to commit.

[grimar]

Ping.

[grimar]

Ping.

[ruiu]

ELF/InputSection.cpp

95 ↗

(On Diff #58779)

UncompressedSize

96–97 ↗

(On Diff #58779)

Cast to Elf{32,64}_Chdr and access ch_size member instead of hard-coding the offsets.

ELF/InputSection.h

44 ↗

(On Diff #58779)

I'd name this Uncompressed.

It needs a comment.

// If a section is compressed, this vector has uncompressed section data.

ELF/Writer.cpp

622 ↗

(On Diff #58779)

H->sh_flags & ~SHF_GROUP & ~SHF_COMPRESSED

[grimar]

• Addressed review comments.

ELF/InputSection.cpp

95 ↗

(On Diff #58779)

Done.

96–97 ↗

(On Diff #58779)

Done.

ELF/InputSection.h

44 ↗

(On Diff #58779)

Done.

ELF/Writer.cpp

622 ↗

(On Diff #58779)

Done.

[ruiu]

I think this patch is nice and clean. LGTM with a few nits.

ELF/InputSection.cpp

88 ↗

(On Diff #61764)

Let's name this Elf_Chdr for consistency with other Elf_ types.

test/ELF/compressed-debug-input.s

6 ↗

(On Diff #61764)

Please s/PACK/COMPRESS/g this file.

lld/trunk/ELF/Driver.cpp

if (Config->GcSections)
     markLive<ELFT>();
   if (Config->ICF)
     doIcf<ELFT>();
 
   // MergeInputSection::splitIntoPieces needs to be called before
   // any call of MergeInputSection::getOffset. Do that.
   for (const std::unique_ptr<elf::ObjectFile<ELFT>> &F :
        Symtab.getObjectFiles())
-    for (InputSectionBase<ELFT> *S : F->getSections())
-      if (S && S != &InputSection<ELFT>::Discarded && S->Live)
-        if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(S))
-          MS->splitIntoPieces();
+    for (InputSectionBase<ELFT> *S : F->getSections()) {
+      if (!S || S == &InputSection<ELFT>::Discarded || !S->Live)
+        continue;
+      if (S->Compressed)
+        S->uncompress();
+    }
 
   writeResult<ELFT>(&Symtab);
 }

lld/trunk/ELF/InputSection.h

protected:
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::uint uintX_t;
   const Elf_Shdr *Header;
 
   // The file this section is from.
   ObjectFile<ELFT> *File;
 
+  // If a section is compressed, this vector has uncompressed section data.
+  SmallVector<char, 0> Uncompressed;
+
 public:
   enum Kind { Regular, EHFrame, Merge, MipsReginfo, MipsOptions };
   Kind SectionKind;
 
   InputSectionBase() : Repl(this) {}
 
   InputSectionBase(ObjectFile<ELFT> *File, const Elf_Shdr *Header,
                    Kind SectionKind);
public:
   uintX_t getOffset(const DefinedRegular<ELFT> &Sym) const;
 
   // Translate an offset in the input section to an offset in the output
   // section.
   uintX_t getOffset(uintX_t Offset) const;
 
   ArrayRef<uint8_t> getSectionData() const;
 
+  void uncompress();
+
   void relocate(uint8_t *Buf, uint8_t *BufEnd);
   std::vector<Relocation<ELFT>> Relocations;
+
+  bool Compressed;
 };
 
 template <class ELFT> InputSectionBase<ELFT> InputSectionBase<ELFT>::Discarded;
 
 // SectionPiece represents a piece of splittable section contents.
 struct SectionPiece {
   SectionPiece(size_t Off, ArrayRef<uint8_t> Data)
       : InputOff(Off), Data((const uint8_t *)Data.data()), Size(Data.size()),

lld/trunk/ELF/InputSection.cpp

 #include "InputSection.h"
 #include "Config.h"
 #include "EhFrame.h"
 #include "Error.h"
 #include "InputFiles.h"
 #include "OutputSections.h"
 #include "Target.h"
 
+#include "llvm/Support/Compression.h"
 #include "llvm/Support/Endian.h"
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::support::endian;
 
 using namespace lld;
 using namespace lld::elf;
 
 template <class ELFT>
 InputSectionBase<ELFT>::InputSectionBase(elf::ObjectFile<ELFT> *File,
                                          const Elf_Shdr *Header,
                                          Kind SectionKind)
-    : Header(Header), File(File), SectionKind(SectionKind), Repl(this) {
+    : Header(Header), File(File), SectionKind(SectionKind), Repl(this),
+      Compressed(Header->sh_flags & SHF_COMPRESSED) {
   // The garbage collector sets sections' Live bits.
   // If GC is disabled, all sections are considered live by default.
   Live = !Config->GcSections;
 
   // The ELF spec states that a value of 0 means the section has
   // no alignment constraits.
   Alignment = std::max<uintX_t>(Header->sh_addralign, 1);
 }
 
 template <class ELFT> size_t InputSectionBase<ELFT>::getSize() const {
   if (auto *D = dyn_cast<InputSection<ELFT>>(this))
     if (D->getThunksSize() > 0)
       return D->getThunkOff() + D->getThunksSize();
   return Header->sh_size;
 }
 
 template <class ELFT> StringRef InputSectionBase<ELFT>::getSectionName() const {
   return check(File->getObj().getSectionName(this->Header));
 }
 
 template <class ELFT>
 ArrayRef<uint8_t> InputSectionBase<ELFT>::getSectionData() const {
+  if (Compressed)
+    return ArrayRef<uint8_t>((const uint8_t *)Uncompressed.data(),
+                             Uncompressed.size());
   return check(this->File->getObj().getSectionContents(this->Header));
 }
 
 template <class ELFT>
 typename ELFT::uint InputSectionBase<ELFT>::getOffset(uintX_t Offset) const {
   switch (SectionKind) {
   case Regular:
     return cast<InputSection<ELFT>>(this)->OutSecOff + Offset;
case MipsOptions:
     if (Offset != 0)
       fatal("Unsupported reference to the middle of '" + getSectionName() +
             "' section");
     return this->OutSec->getVA();
   }
   llvm_unreachable("invalid section kind");
 }
 
+template <class ELFT> void InputSectionBase<ELFT>::uncompress() {
+  typedef typename std::conditional<ELFT::Is64Bits, Elf64_Chdr,
+                                    Elf32_Chdr>::type Elf_Chdr;
+  const endianness E = ELFT::TargetEndianness;
+
+  if (!zlib::isAvailable())
+    fatal("build lld with zlib to enable compressed sections support");
+
+  ArrayRef<uint8_t> Data =
+      check(this->File->getObj().getSectionContents(this->Header));
+  if (read32<E>(Data.data()) != ELFCOMPRESS_ZLIB)
+    fatal("unsupported elf compression type");
+
+  size_t UncompressedSize =
+      reinterpret_cast<const Elf_Chdr *>(Data.data())->ch_size;
+  size_t HdrSize = sizeof(Elf_Chdr);
+  StringRef Buf((const char *)Data.data() + HdrSize, Data.size() - HdrSize);
+  if (zlib::uncompress(Buf, Uncompressed, UncompressedSize) != zlib::StatusOK)
+    fatal("error uncompressing section");
+}
+
 template <class ELFT>
 typename ELFT::uint
 InputSectionBase<ELFT>::getOffset(const DefinedRegular<ELFT> &Sym) const {
   return getOffset(Sym.Value);
 }
 
 template <class ELFT>
 InputSection<ELFT>::InputSection(elf::ObjectFile<ELFT> *F,

lld/trunk/ELF/Writer.cpp

OutputSectionFactory<ELFT>::create(InputSectionBase<ELFT> *C,
   return {Sec, true};
 }
 
 template <class ELFT>
 SectionKey<ELFT::Is64Bits>
 OutputSectionFactory<ELFT>::createKey(InputSectionBase<ELFT> *C,
                                       StringRef OutsecName) {
   const Elf_Shdr *H = C->getSectionHdr();
-  uintX_t Flags = H->sh_flags & ~SHF_GROUP;
+  uintX_t Flags = H->sh_flags & ~SHF_GROUP & ~SHF_COMPRESSED;
 
   // For SHF_MERGE we create different output sections for each alignment.
   // This makes each output section simple and keeps a single level mapping from
   // input to output.
   uintX_t Alignment = 0;
   if (isa<MergeInputSection<ELFT>>(C))
     Alignment = std::max(H->sh_addralign, H->sh_entsize);
 

lld/trunk/test/ELF/compressed-debug-input.s

+# REQUIRES: zlib
+
+# RUN: llvm-mc -compress-debug-sections=zlib -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: llvm-readobj -sections %t | FileCheck -check-prefix=COMPRESSED %s
+
+# COMPRESSED:      Section {
+# COMPRESSED:        Index: 2
+# COMPRESSED:        Name: .debug_str
+# COMPRESSED-NEXT:   Type: SHT_PROGBITS
+# COMPRESSED-NEXT:   Flags [
+# COMPRESSED-NEXT:     SHF_COMPRESSED (0x800)
+# COMPRESSED-NEXT:     SHF_MERGE (0x10)
+# COMPRESSED-NEXT:     SHF_STRINGS (0x20)
+# COMPRESSED-NEXT:   ]
+# COMPRESSED-NEXT:   Address:
+# COMPRESSED-NEXT:   Offset:
+# COMPRESSED-NEXT:   Size: 66
+# COMPRESSED-NEXT:   Link:
+# COMPRESSED-NEXT:   Info:
+# COMPRESSED-NEXT:   AddressAlignment: 1
+# COMPRESSED-NEXT:   EntrySize: 1
+# COMPRESSED-NEXT: }
+
+# RUN: ld.lld %t -o %t.so -shared
+# RUN: llvm-readobj -sections %t.so | FileCheck -check-prefix=UNCOMPRESSED %s
+
+## Check that section is decompressed and compression flag is removed.
+# UNCOMPRESSED:      Section {
+# UNCOMPRESSED:        Index: 6
+# UNCOMPRESSED:        Name: .debug_str
+# UNCOMPRESSED-NEXT:   Type: SHT_PROGBITS
+# UNCOMPRESSED-NEXT:   Flags [
+# UNCOMPRESSED-NEXT:     SHF_MERGE (0x10)
+# UNCOMPRESSED-NEXT:     SHF_STRINGS (0x20)
+# UNCOMPRESSED-NEXT:   ]
+# UNCOMPRESSED-NEXT:   Address: 0x0
+# UNCOMPRESSED-NEXT:   Offset: 0x1060
+# UNCOMPRESSED-NEXT:   Size: 69
+# UNCOMPRESSED-NEXT:   Link: 0
+# UNCOMPRESSED-NEXT:   Info: 0
+# UNCOMPRESSED-NEXT:   AddressAlignment: 1
+# UNCOMPRESSED-NEXT:   EntrySize: 1
+# UNCOMPRESSED-NEXT: }
+
+.section .debug_str,"MS",@progbits,1
+.LASF2:
+ .string "short unsigned int"
+.LASF3:
+ .string "unsigned int"
+.LASF0:
+ .string "long unsigned int"
+.LASF8:
+ .string "char"
+.LASF1:
+ .string "unsigned char"