[ELF] - Support of compressed debug sections creation(draft).

[grimar]

Summary

This is a draft patch to support creation of all possible types of compressed debug sections.
Patch does not have testcases yet, I am going to update it soon, tomorrow probably.
Would be happy to hear any suggestions/opinions.

A bit belated question, probably: are we going to support that ? That is relatively
new feature, but both bfd/gold do.

Some info about compressed sections can be found at:
https://docs.oracle.com/cd/E53394_01/html/E54813/section_compression.html#scrolltoc
https://docs.oracle.com/cd/E53394_01/html/E54813/man-cds.html

[ruiu]

Please add tests to verify that you are producing compressed sections that can be read by other tools.

ELF/Options.td

33

This help text is out of context.

ELF/OutputSections.cpp

833–837

Clang-format.

842

Please don't use an unrelated object's members.

859–862

This code creates an uncompressed a debug section in memory and then compress it at once. It consumes as much memory as the total size of the debug section. It is probably unacceptable.

zlib supports "streaming" compression, right? I think you can pass pieces of data to zlib object and let it construct compressed data incrementally. Please do that way so that the maximum memory is bounded to the largest input section size instead of the largest output section size.

869–874

I think we don't have to care about this edge case. Unless you are compressing random bits, it usually shrink.

1014–1025

Why we have two types of headers? If one is obsolete, we probably don't want to implement it.

ELF/Writer.cpp

1161–1163

You can move this to OutputSection class, no?

1172

This condition should be at the beginning of this function.

[emaste]

are we going to support that

I would find it useful.

[ruiu]

Yes, we want it.

[grimar]

ELF/OutputSections.cpp

842

Yep, I know, that is just because it was a draft patch.
I was thinking about it when did that. What is the good way ?
Actually I do not like how it is done now: we have lots of StringSaver instances in many places in lld.
Are there reasons for that instead of having one StringSaver for all with single Alloc and just global reference to it ?

869–874

I would leave it as is. That is mentioned in docs: "The .debug_line and .debug_pubnames sections would be larger compressed than in their original uncompressed form, and have therefore been left uncompressed." (https://docs.oracle.com/cd/E53394_01/html/E54813/section_compression.html#scrolltoc) and done both by gold/bfd and very transparent in implementation.
In addition I think that if feature is used then motivation and expected result is to consume less space, I do not think it is acceptable to consume more than without it, it is confusing and opposite to its description.

1014–1025

There are 2 different approaches used (https://docs.oracle.com/cd/E53394_01/html/E54813/section_compression.html):

1. gnu-style renames sections to ".z*[NAME]" and do not uses SHF_COMPRESSED.
2. zlib style. Sections have SHF_COMPRESSED flag and are not renamed.

"Unless there is a specific requirement to use the zlib-gnu style, the more general default zlib style is recommended." says https://docs.oracle.com/cd/E53394_01/html/E54813/man-cds.html, but it is not mentioned if that depricated or something.
Not supporting of zlib-gnu style would make implementation a bit cleaner.

It is not hard to support both though.

ELF/Writer.cpp

1172

Actually I assumed that is low user path to have zlib not available.
btw, since I am on windows I had some problems with it, it is well described at https://llvm.org/bugs/show_bug.cgi?id=19403.
So windows users currently will not able to use that feature atm, all *nix ones probably already have zlib installed.

But ok, I`ll move that since it is also logical for me that we first check if feature available at first before any other conditions.

[• rafael]

ruiu wrote:

I think we don't have to care about this edge case. Unless you are compressing random bits, it usually shrink.

I would leave it as is. That is mentioned in docs: "The .debug_line and .debug_pubnames sections would be larger compressed than in their original uncompressed form, and have therefore been left uncompressed." (https://docs.oracle.com/cd/E53394_01/html/E54813/section_compression.html#scrolltoc) and done both by gold/bfd and very transparent in implementation.
In addition I think that if feature is used then motivation and expected result is to consume less space, I do not think it is acceptable to consume more than without it, it is confusing and opposite to its description.

I think we can start without this and see how many case we hit in the
field when it gets bigger.

ruiu wrote:

Why we have two types of headers? If one is obsolete, we probably don't want to implement it.

There are 2 different approaches used (https://docs.oracle.com/cd/E53394_01/html/E54813/section_compression.html):

1. gnu-style renames sections to ".z*[NAME]" and do not uses SHF_COMPRESSED.
2. zlib style. Sections have SHF_COMPRESSED flag and are not renamed.

"Unless there is a specific requirement to use the zlib-gnu style, the more general default zlib style is recommended." says https://docs.oracle.com/cd/E53394_01/html/E54813/man-cds.html, but it is not mentioned if that depricated or something.
Not supporting of zlib-gnu style would make implementation a bit cleaner.

It is not hard to support both though.

Lets please start without support of the gnu style.

Cheers,
Rafael

[grimar]

So, currently we are putting this on hold, right ?

Patch implementing support for compressed input sections is prepared here: D20272

[grimar]

If we do not plan to support compressed output sections, I would abandon this. Should I ? Rafael, Rui ?
Otherwise I can update this one.

[grimar]

Dropping it unless we find someone that is using this.

ELF/Config.h

 
 // This struct contains the global configuration for the linker.
 // Most fields are direct mapping from the command line options
 // and such fields have the same name as the corresponding options.
 // Most fields are initialized by the driver.
 struct Configuration {
   Symbol *EntrySym = nullptr;
   InputFile *FirstElf = nullptr;
+  llvm::StringRef CompressDebugSections;
   llvm::StringRef DynamicLinker;
   llvm::StringRef Entry;
   llvm::StringRef Emulation;
   llvm::StringRef Fini;
   llvm::StringRef Init;
   llvm::StringRef OutputFile;
   llvm::StringRef SoName;
   llvm::StringRef Sysroot;

ELF/Driver.cpp

void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   }
 
   if (Config->EMachine == EM_MIPS && Config->EKind == ELF64LEKind)
     Config->Mips64EL = true;
 
   Config->AllowMultipleDefinition = Args.hasArg(OPT_allow_multiple_definition);
   Config->Bsymbolic = Args.hasArg(OPT_Bsymbolic);
   Config->BsymbolicFunctions = Args.hasArg(OPT_Bsymbolic_functions);
+  Config->CompressDebugSections = getString(Args, OPT_compress_debug_sections, "none");
   Config->Demangle = !Args.hasArg(OPT_no_demangle);
   Config->DisableVerify = Args.hasArg(OPT_disable_verify);
   Config->DiscardAll = Args.hasArg(OPT_discard_all);
   Config->DiscardLocals = Args.hasArg(OPT_discard_locals);
   Config->DiscardNone = Args.hasArg(OPT_discard_none);
   Config->EhFrameHdr = Args.hasArg(OPT_eh_frame_hdr);
   Config->EnableNewDtags = !Args.hasArg(OPT_disable_new_dtags);
   Config->ExportDynamic = Args.hasArg(OPT_export_dynamic);

ELF/Options.td

 
 def allow_multiple_definition: Flag<["--"], "allow-multiple-definition">,
   HelpText<"Allow multiple definitions">;
 
 def allow_shlib_undefined : Flag<["--", "-"], "allow-shlib-undefined">;
 
 def as_needed : Flag<["--"], "as-needed">;
 
+def compress_debug_sections : Joined<["--"], "compress-debug-sections=">,
+  HelpText<"Force undefined symbol during linking">;
+
 def disable_new_dtags : Flag<["--"], "disable-new-dtags">,
   HelpText<"Disable new dynamic tags">;
 
 def discard_all : Flag<["--", "-"], "discard-all">,
   HelpText<"Delete all local symbols">;
 
 def discard_locals : Flag<["--", "-"], "discard-locals">,
   HelpText<"Delete temporary local symbols">;

ELF/OutputSections.h

 template <class ELFT>
 class OutputSection final : public OutputSectionBase<ELFT> {
 public:
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::Rel Elf_Rel;
   typedef typename ELFT::Rela Elf_Rela;
   typedef typename ELFT::uint uintX_t;
-  OutputSection(StringRef Name, uint32_t Type, uintX_t Flags);
+  OutputSection(StringRef Name, uint32_t Type, uintX_t Flags, bool Compress);
   void addSection(InputSectionBase<ELFT> *C) override;
   void sortInitFini();
   void sortCtorsDtors();
   void writeTo(uint8_t *Buf) override;
   void finalize() override;
   void
   forEachInputSection(std::function<void(InputSectionBase<ELFT> *)> F) override;
   std::vector<InputSection<ELFT> *> Sections;
+
+private:
+  void finalizeCompressed();
+  void writeCompressed(uint8_t *Buf);
+
+  bool Compress;
+  SmallVector<char, 0> CompressedData;
+  uint64_t UncompressedSize = 0;
 };
 
 template <class ELFT>
 class MergeOutputSection final : public OutputSectionBase<ELFT> {
   typedef typename ELFT::uint uintX_t;
 
 public:
   MergeOutputSection(StringRef Name, uint32_t Type, uintX_t Flags,

ELF/OutputSections.cpp

 //===- OutputSections.cpp -------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "OutputSections.h"
 #include "Config.h"
 #include "LinkerScript.h"
 #include "SymbolTable.h"
 #include "Target.h"
 #include "lld/Core/Parallel.h"
+#include "llvm/Support/Compression.h"
 #include "llvm/Support/Dwarf.h"
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/SHA1.h"
 #include <map>
 
 using namespace llvm;
 using namespace llvm::dwarf;

 template <class ELFT> void EhFrameHeader<ELFT>::reserveFde() {
   // Each FDE entry is 8 bytes long:
   // The first four bytes are an offset to the initial PC value for the FDE. The
   // last four byte are an offset to the FDE data itself.
   this->Header.sh_size += 8;
 }
 
 template <class ELFT>
-OutputSection<ELFT>::OutputSection(StringRef Name, uint32_t Type, uintX_t Flags)
-    : OutputSectionBase<ELFT>(Name, Type, Flags) {
+OutputSection<ELFT>::OutputSection(StringRef Name, uint32_t Type, uintX_t Flags,
+                                   bool Compress)
+    : OutputSectionBase<ELFT>(Name, Type, Flags), Compress(Compress) {
   if (Type == SHT_RELA)
     this->Header.sh_entsize = sizeof(Elf_Rela);
   else if (Type == SHT_REL)
     this->Header.sh_entsize = sizeof(Elf_Rel);
+
+  if (!Compress)
+    return;
+
+  // Compress candidate sections using ZLIB compression. The resulting output
+  // sections have the SHF_COMPRESSED section flag set to identify the use of
+  // compression.
+  if (Config->CompressDebugSections == "zlib-gabi" ||
+    Config->CompressDebugSections == "zlib") {
+    Header.sh_flags |= SHF_COMPRESSED;
+  }
+  else {
+    // Compress all candidate sections using ZLIB compression, using the GNU
+    // section compression format. This format requires candidate sections to
+    // have a name that begins with.debug. The resulting output sections are
+    // renamed to start with.zdebug to identify the use of compression.
+    StringSaver Saver(ScriptConfig->Alloc);
+    this->Name = Saver.save(Twine(".z") + Name.drop_front(1));
+  }
+}
+
+template <class ELFT> static size_t getCompressionHeaderSize() {
+  if (Config->CompressDebugSections == "none")
+    return 0;
+  // The gnu-style header consist from 'zlib' signature and
+  // 8 bytes length of uncompressed data:
+  // https://docs.oracle.com/cd/E53394_01/html/E54813/section_compression.html
+  if (Config->CompressDebugSections == "zlib-gnu")
+    return 12;
+  return ELFT::Is64Bits ? sizeof(Elf64_Chdr) : sizeof(Elf32_Chdr);
+}
+
+template <class ELFT> void OutputSection<ELFT>::finalizeCompressed() {
+  std::vector<uint8_t> Uncompressed(getSize());
+  uint8_t *Data = Uncompressed.data();
+  for (InputSection<ELFT> *C : Sections)
+    C->writeTo(Data);
+
+  SmallVector<char, 0> Compressed;
+  zlib::Status Success =
+      zlib::compress(StringRef((const char *)Data, getSize()), Compressed,
+                     zlib::BestSizeCompression);
+
+  // If not successfully compressed or total size is greater than
+  // size before applying compression, then cancel compressed output.
+  size_t TotalSize = Compressed.size() + getCompressionHeaderSize<ELFT>();
+  Compress = Success == zlib::Status::StatusOK && TotalSize < getSize();
+  if (!Compress)
+    return;
+
+  CompressedData.swap(Compressed);
+  UncompressedSize = getSize();
+  setSize(TotalSize);
 }
 
 template <class ELFT> void OutputSection<ELFT>::finalize() {
+  if (Compress) {
+    finalizeCompressed();
+    return;
+  }
   uint32_t Type = this->Header.sh_type;
   if (Type != SHT_RELA && Type != SHT_REL)
     return;
   this->Header.sh_link = Out<ELFT>::SymTab->SectionIndex;
   // sh_info for SHT_REL[A] sections should contain the section header index of
   // the section to which the relocation applies.
   InputSectionBase<ELFT> *S = Sections[0]->getRelocatedSection();
   this->Header.sh_info = S->OutSec->SectionIndex;

 
 static void fill(uint8_t *Buf, size_t Size, ArrayRef<uint8_t> A) {
   size_t I = 0;
   for (; I + A.size() < Size; I += A.size())
     memcpy(Buf + I, A.data(), A.size());
   memcpy(Buf + I, A.data(), Size - I);
 }
 
+template <class ELFT> void OutputSection<ELFT>::writeCompressed(uint8_t *Buf) {
+  const endianness E = ELFT::TargetEndianness;
+  if (Config->CompressDebugSections == "zlib-gnu") {
+    // 4 bytes magic + size of uncompressed data in big endian.
+    memcpy(Buf, "ZLIB", 4);
+    write64be(Buf + 4, UncompressedSize);
+  } else {
+    // "zlib-gabi" or "zlib".
+    write32<E>(Buf, ELFCOMPRESS_ZLIB);
+    if (ELFT::Is64Bits)
+      write64<E>(Buf + 2 * sizeof(Elf64_Word), UncompressedSize);
+    else
+      write32<E>(Buf + sizeof(Elf32_Word), UncompressedSize);
+  }
+
+  memcpy(Buf + getCompressionHeaderSize<ELFT>(), CompressedData.data(),
+         CompressedData.size());
+}
+
 template <class ELFT> void OutputSection<ELFT>::writeTo(uint8_t *Buf) {
+  if (Compress) {
+    writeCompressed(Buf);
+    return;
+  }
+
   ArrayRef<uint8_t> Filler = Script<ELFT>::X->getFiller(this->Name);
   if (!Filler.empty())
     fill(Buf, this->getSize(), Filler);
+
   if (Config->Threads) {
     parallel_for_each(Sections.begin(), Sections.end(),
                       [=](InputSection<ELFT> *C) { C->writeTo(Buf); });
   } else {
     for (InputSection<ELFT> *C : Sections)
       C->writeTo(Buf);
   }
 }

ELF/Writer.cpp

 #include "LinkerScript.h"
 #include "OutputSections.h"
 #include "SymbolTable.h"
 #include "Target.h"
 
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringSwitch.h"
+#include "llvm/Support/Compression.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/FileOutputBuffer.h"
 #include "llvm/Support/StringSaver.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
if (!Config->StripAll) {
     SymTabSec.reset(new SymbolTableSection<ELFT>(*Symtab, *StrTab));
   }
   if (Config->EMachine == EM_MIPS && !Config->Shared) {
     // This is a MIPS specific section to hold a space within the data segment
     // of executable file which is pointed to by the DT_MIPS_RLD_MAP entry.
     // See "Dynamic section" in Chapter 5 in the following document:
     // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
     MipsRldMap.reset(new OutputSection<ELFT>(".rld_map", SHT_PROGBITS,
-                                             SHF_ALLOC | SHF_WRITE));
+                                             SHF_ALLOC | SHF_WRITE,
+                                             false /* Compression */));
     MipsRldMap->setSize(sizeof(uintX_t));
     MipsRldMap->updateAlign(sizeof(uintX_t));
   }
 
   Out<ELFT>::BuildId = BuildId.get();
   Out<ELFT>::DynStrTab = &DynStrTab;
   Out<ELFT>::DynSymTab = &DynSymTab;
   Out<ELFT>::Dynamic = &Dynamic;
static bool compareSections(OutputSectionBase<ELFT> *A,
   return false;
 }
 
 // The .bss section does not exist if no input file has a .bss section.
 // This function creates one if that's the case.
 template <class ELFT> void Writer<ELFT>::ensureBss() {
   if (Out<ELFT>::Bss)
     return;
-  Out<ELFT>::Bss =
-      new OutputSection<ELFT>(".bss", SHT_NOBITS, SHF_ALLOC | SHF_WRITE);
+  Out<ELFT>::Bss = new OutputSection<ELFT>(
+      ".bss", SHT_NOBITS, SHF_ALLOC | SHF_WRITE, false /* Compression */);
   OwningSections.emplace_back(Out<ELFT>::Bss);
   OutputSections.push_back(Out<ELFT>::Bss);
 }
 
 // Until this function is called, common symbols do not belong to any section.
 // This function adds them to end of BSS section.
 template <class ELFT>
 void Writer<ELFT>::addCommonSymbols(std::vector<DefinedCommon *> &Syms) {

 private:
   SectionKey<ELFT::Is64Bits> createKey(InputSectionBase<ELFT> *C,
                                        StringRef OutsecName);
 
   SmallDenseMap<SectionKey<ELFT::Is64Bits>, OutputSectionBase<ELFT> *> Map;
 };
 }
 
 template <class ELFT>
+static bool isCompressionCandidate(InputSectionBase<ELFT> *C,
+                                   StringRef OutSecName) {
+  if (Config->CompressDebugSections == "none")
+    return false;
+  // SHF_COMPRESSED applies only to non - allocable sections, and
+  // cannot be used in conjunction with SHF_ALLOC.
+  if (C->getSectionHdr()->sh_flags & SHF_ALLOC)
+    return false;
+  if (!OutSecName.startswith(".debug"))
+    return false;
+  return zlib::isAvailable();
+}
+
+template <class ELFT>
 std::pair<OutputSectionBase<ELFT> *, bool>
 OutputSectionFactory<ELFT>::create(InputSectionBase<ELFT> *C,
                                    StringRef OutsecName) {
   SectionKey<ELFT::Is64Bits> Key = createKey(C, OutsecName);
   OutputSectionBase<ELFT> *&Sec = Map[Key];
   if (Sec)
     return {Sec, false};
 
   switch (C->SectionKind) {
   case InputSectionBase<ELFT>::Regular:
-    Sec = new OutputSection<ELFT>(Key.Name, Key.Type, Key.Flags);
+    Sec = new OutputSection<ELFT>(Key.Name, Key.Type, Key.Flags,
+                                  isCompressionCandidate(C, OutsecName));
     break;
   case InputSectionBase<ELFT>::EHFrame:
     Sec = new EHOutputSection<ELFT>(Key.Name, Key.Type, Key.Flags);
     break;
   case InputSectionBase<ELFT>::Merge:
     Sec = new MergeOutputSection<ELFT>(Key.Name, Key.Type, Key.Flags,
                                        Key.Alignment);
     break;