[ELF] - Implemented --compress-debug-sections option.

[grimar]

Summary

Patch implements --compress-debug-sections=zlib.

In compare with D20211 (a year old patch, abandoned), it implementation
uses streaming and fully reimplemented, does not support zlib-gnu for
simplification.

This is PR32308.

[ruiu]

This patch doesn't use multiple cores to compress .debug section contents. In theory, if there are multiple .debug sections, we can compress them separately. Can you do that?

The code that writes section contents into an in-memory buffer looks very similar to code that writes sections to the output file buffer. This needs fixing.

The other approach I can think of is to do everything as a post-process. After writing everything to the output buffer, you scan .debug sections (that are at end of file), compress them in-place, and then shifts them to fill the holes created by data compression. Have you thought about that?

ELF/Driver.cpp

560 ↗

(On Diff #94833)

What is -gabi?

562 ↗

(On Diff #94833)

This is obvious, so remove this comment.

ELF/Options.td

25 ↗

(On Diff #94833)

Why don't you use J?

ELF/OutputSections.cpp

74 ↗

(On Diff #94833)

Why?

110 ↗

(On Diff #94833)

What is 1024?

Is the default compression level the best for us?

[ruiu]

ELF/Driver.cpp

560 ↗

(On Diff #94833)

I don't think zlib and zlib-gabi are the same. What you implemented in this patch is zlib-gabi, so don't handle zlib as a synonym for zlib-gabi.

ELF/OutputSections.cpp

309–315 ↗

(On Diff #94833)

You can do this in finalize(), right?

test/ELF/compress-debug-sections.s

13–15 ↗

(On Diff #94833)

Don't check for the section contents because zlib doesn't really guarantee the output.

27 ↗

(On Diff #94833)

Ditto

29–48 ↗

(On Diff #94833)

Why do you need this?

[grimar]

In D31941#723864, @ruiu wrote:

This patch doesn't use multiple cores to compress .debug section contents. In theory, if there are multiple .debug sections, we can compress them separately. Can you do that?

zlib format specification (http://www.zlib.org/rfc-zlib.html, 2.2. Data format) says that it has header, some data and checksum after, it not just a piece of raw bytes that we can
concatenate and have the same result so simple. At the same time one of zlib authors answered how that can be implemented in short:
http://stackoverflow.com/questions/30794053/how-to-use-multiple-threads-for-zlib-compression-same-input-source
It looks a bit tricky because requires fixups of results (dropping bytes etc), but definetely should be possible.

If so it may be reasonable to implement threading compression API for LLVM and reuse it in LLD.

That probably means we can go with simple streaming imprementation for start and replace code in OutputSection::finalize() with threading solution when it be implemented. What do you think ?

The code that writes section contents into an in-memory buffer looks very similar to code that writes sections to the output file buffer. This needs fixing.

That should be solveable.

The other approach I can think of is to do everything as a post-process. After writing everything to the output buffer, you scan .debug sections (that are at end of file), compress them in-place, and then shifts them to fill the holes created by data compression. Have you thought about that?

I thought about different post-process and droped idea (it was estimate somehow max compressed size and compress in place in writeTo. If estimated size value minus real size value would be something not too large,
it could work. Do not know how it can be possible to do such estimation and anyways output would be larger than possible).

And your suggestion doesn't look too clean either, does it ? That would mean that we do not know final layout even during writing, what a bit wierd. And then either we need to fixup sections headers and write them after other data. Then do shifting and after that all truncate output file, right ? That is a bit too tricky for my eye. That may degradate perfomance either, probably.

ELF/Driver.cpp

560 ↗

(On Diff #94833)

http://man7.org/linux/man-pages/man1/ld.1.html says:
--compress-debug-sections=zlib and
--compress-debug-sections=zlib-gabi compress DWARF debug sections with SHF_COMPRESSED from the ELF ABI. The default behaviour varies depending upon the target involved and the configure options used to build the toolchain.

https://docs.oracle.com/cd/E53394_01/html/E54813/man-cds.html says that there are 3 options: none, zlib, zlib-gnu.
It does not mention what is zlib-gabi.

The only compression flag available now in generic ABI is ELFCOMPRESS_ZLIB:
http://www.sco.com/developers/gabi/latest/ch4.sheader.html

So my conclusion from above:

1. Since oracle does not mention zlib-gabi, I implemented zlib and not zlib-gabi.
2. Since ld manual says both zlib/zlib-gabi compresses sections with SHF_COMPRESSED from ABI and only available type is ELFCOMPRESS_ZLIB, then zlib and zlib-gabi is the same.

ELF/Options.td

25 ↗

(On Diff #94833)

Copypaste from def O: Joined<["-"] will fix.

ELF/OutputSections.cpp

74 ↗

(On Diff #94833)

https://docs.oracle.com/cd/E36784_01/html/E36857/compressed_debug_sections.html
("To be a candidate for compression, a section must be non-allocable, and belong to ....")

https://docs.oracle.com/cd/E53394_01/html/E54813/section_compression.html
("SHF_COMPRESSED applies only to non-allocable sections, and cannot be used in conjunction with SHF_ALLOC. In addition, SHF_COMPRESSED cannot be applied to sections of type SHT_NOBITS.").

110 ↗

(On Diff #94833)

1024 is a size of buffer used for output in zlib::StreamCompression implementation currently. It may be worth to try different values and benchmark LLD separatelly.

Regarding second question, zlib::StreamCompression indeed currently uses default compression level. What is best may probably depend on what we want. Speed or size or something in the middle. That also requires additional benchmarking probably and additional discussion based on benchmarking results. In current implemenation compression class (D31943) does not yet have API for setting level.

309–315 ↗

(On Diff #94833)

Do you mean adding compression header to buffer ? If so, yes, I can.
(Sure I can't write something to output file there, output is not exist at that point).

[ruiu]

What I was saying was that you can compress multiple sections concurrently, right? I didn't say you should try to compress single stream of data using multiple threads. I meant, since we have multiple .debug_ sections, you could compress them separately.

ELF/Driver.cpp

560 ↗

(On Diff #94833)

When I give -compress-debug-sections=zlib and -compress-debug-sections=zlib-gabi, outputs from gold were actually different. But interestingly enough the difference wasn't meaningful. Gold seems to set garbage to ch_reserved members of compressed section headers. (Probably they forgot to initialize the header with zero before setting values to the members.)

So my conclusion is zlib-gabi and zlib are the same. But I don't see a reason to add two identical options at the moment. Please add just "zlib".

ELF/OutputSections.cpp

72–76 ↗

(On Diff #94833)

The way this code is written is confusing. What you should state is that we want to compress .debug sections (which needless to say non-alloc sections).

// If -compress-debug-sections is specified, we compress output debug sections.
if (Config->CompressDebugSections && Name.startswith(".debug_") && !(Flags & SHF_ALLOC))
  this->Flags |= SHF_COMPRESSED;

However, this piece of code should probably be moved to finalize().

[grimar]

• Added multithreaded compression of output sections.
• Removed streaming zlib compression.
• Addressed review comments.

[grimar]

In D31941#725216, @ruiu wrote:

What I was saying was that you can compress multiple sections concurrently, right? I didn't say you should try to compress single stream of data using multiple threads. I meant, since we have multiple .debug_ sections, you could compress them separately.

OK, I understood differently. Thought you're talking about multithreaded compression for input .debug* sections.

ELF/Driver.cpp

560 ↗

(On Diff #94833)

Done.

562 ↗

(On Diff #94833)

Done.

ELF/Options.td

25 ↗

(On Diff #94833)

Fixed.

ELF/OutputSections.cpp

72–76 ↗

(On Diff #94833)

Ok. FWIW spec states that debug sections are ".debug*" and not ".debug_*"
(https://docs.oracle.com/cd/E53394_01/html/E54813/man-cds.html)
Though I think your way should work anyways.

It also mentiones other namings:
Debug sections are identified by having a .compcom, .line, .stab*, .debug*, or .zdebug* section name.

I would start only from .debug ones in this patch.

test/ELF/compress-debug-sections.s

13–15 ↗

(On Diff #94833)

I reimplemented this test in a more smart way.

[ruiu]

ELF/OutputSections.cpp

90 ↗

(On Diff #95114)

I think it is better to template this function with ELFT so that you can access members by name using ELFT::Chdr type.

115 ↗

(On Diff #95114)

Rename this maybeComrpess as it does't always compress contents.

143–147 ↗

(On Diff #95114)

Move this to OutputSection::compress().

ELF/OutputSections.h

92–93 ↗

(On Diff #95114)

CompressedHeader can be part of CompressedData.

95–96 ↗

(On Diff #95114)

You don't need this, I guess?

[ruiu]

ELF/Options.td

26 ↗

(On Diff #95114)

Compresses -> Compress

[grimar]

• Addressed review comments.

ELF/Options.td

26 ↗

(On Diff #95114)

Done.

ELF/OutputSections.cpp

90 ↗

(On Diff #95114)

Done.

115 ↗

(On Diff #95114)

Done.

143–147 ↗

(On Diff #95114)

Done.

ELF/OutputSections.h

92–93 ↗

(On Diff #95114)

That what I wanted to do, but I think there is no way to do that in effective way with current zlib::compress implementation.

It takes buffer for output, resizes and fills on its side. There is no way to say: "I need some room at start".
As a result after doing compression if you want to add some header all section content should be shifted and it can affect perfomance if section is huge.

So I did them as separate fields for now.

95–96 ↗

(On Diff #95114)

Right. Removed.

[ruiu]

LGTM

There is a room for improvements, but I'll do that after you submit this.

ELF/OutputSections.cpp

99–109 ↗

(On Diff #95285)

You are not accessing these members by name.

[ruiu]

ELF/OutputSections.cpp

128 ↗

(On Diff #95285)

I believe this function returns an Error. Make sure you handle an error before submitting.

[grimar]

Thanks for review, Rui !

ELF/OutputSections.cpp

99–109 ↗

(On Diff #95285)

Ah. I misread your comment at first, sorry. Fixed in commit.

128 ↗

(On Diff #95285)

Done.

[grimar]

lld/trunk/ELF/OutputSections.cpp

110

I think we can simplify this to nex one now ?

if (Config->Is64)
  Buf += sizeof(Elf64_Word);
write(Buf, (typename ELFT::uint)Size, E);
Buf += sizeof(ELFT::Chdr::ch_size);
write(Buf, (typename ELFT::uint)Alignment, E);
Buf += sizeof(ELFT::Chdr::ch_addralign);

lld/trunk/ELF/Config.h

struct Configuration {
   std::vector<SymbolVersion> VersionScriptLocals;
   std::vector<uint8_t> BuildIdVector;
   bool AllowMultipleDefinition;
   bool ArchiveWithoutSymbolsSeen = false;
   bool AsNeeded = false;
   bool Bsymbolic;
   bool BsymbolicFunctions;
   bool ColorDiagnostics = false;
+  bool CompressDebugSections;
   bool DefineCommon;
   bool Demangle = true;
   bool DisableVerify;
   bool EhFrameHdr;
   bool EmitRelocs;
   bool EnableNewDtags;
   bool ExportDynamic;
   bool FatalWarnings;

lld/trunk/ELF/Driver.cpp

 #include "Threads.h"
 #include "Writer.h"
 #include "lld/Config/Version.h"
 #include "lld/Driver/Driver.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Object/Decompressor.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Compression.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/TarWriter.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstdlib>
 #include <utility>
 
 using namespace llvm;
static std::vector<StringRef> getLines(MemoryBufferRef MB) {
   for (StringRef S : Arr) {
     S = S.trim();
     if (!S.empty())
       Ret.push_back(S);
   }
   return Ret;
 }
 
+static bool getCompressDebugSections(opt::InputArgList &Args) {
+  if (auto *Arg = Args.getLastArg(OPT_compress_debug_sections)) {
+    StringRef S = Arg->getValue();
+    if (S == "none")
+      return false;
+    if (S == "zlib")
+      return zlib::isAvailable();
+    error("unknown --compress-debug-sections value: " + S);
+  }
+  return false;
+}
+
 // Initializes Config members by the command line options.
 void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   Config->AllowMultipleDefinition = Args.hasArg(OPT_allow_multiple_definition);
   Config->AuxiliaryList = getArgs(Args, OPT_auxiliary);
   Config->Bsymbolic = Args.hasArg(OPT_Bsymbolic);
   Config->BsymbolicFunctions = Args.hasArg(OPT_Bsymbolic_functions);
+  Config->CompressDebugSections = getCompressDebugSections(Args);
   Config->DefineCommon = getArg(Args, OPT_define_common, OPT_no_define_common,
                                 !Args.hasArg(OPT_relocatable));
   Config->Demangle = getArg(Args, OPT_demangle, OPT_no_demangle, true);
   Config->DisableVerify = Args.hasArg(OPT_disable_verify);
   Config->Discard = getDiscard(Args);
   Config->DynamicLinker = getDynamicLinker(Args);
   Config->EhFrameHdr = Args.hasArg(OPT_eh_frame_hdr);
   Config->EmitRelocs = Args.hasArg(OPT_emit_relocs);

lld/trunk/ELF/Options.td

 def Bdynamic: F<"Bdynamic">, HelpText<"Link against shared libraries">;
 
 def Bstatic: F<"Bstatic">, HelpText<"Do not link against shared libraries">;
 
 def build_id: F<"build-id">, HelpText<"Generate build ID note">;
 
 def build_id_eq: J<"build-id=">, HelpText<"Generate build ID note">;
 
+def compress_debug_sections : J<"compress-debug-sections=">,
+  HelpText<"Compress DWARF debug sections">;
+
 def L: JoinedOrSeparate<["-"], "L">, MetaVarName<"<dir>">,
   HelpText<"Add a directory to the library search path">;
 
 def O: Joined<["-"], "O">, HelpText<"Optimize output file size">;
 
 def Tbss: S<"Tbss">, HelpText<"Same as --section-start with .bss as the sectionname">;
 
 def Tdata: S<"Tdata">, HelpText<"Same as --section-start with .data as the sectionname">;

lld/trunk/ELF/OutputSections.h

public:
 
   void addSection(InputSection *S);
   void sort(std::function<int(InputSectionBase *S)> Order);
   void sortInitFini();
   void sortCtorsDtors();
   uint32_t getFiller();
   template <class ELFT> void writeTo(uint8_t *Buf);
   template <class ELFT> void finalize();
+  template <class ELFT> void maybeCompress();
   void assignOffsets();
   std::vector<InputSection *> Sections;
 
+  // Used for implementation of --compress-debug-sections option.
+  llvm::SmallVector<char, 1> CompressedData;
+  std::vector<uint8_t> CompressedHeader;
+
   // Location in the output buffer.
   uint8_t *Loc = nullptr;
 };
 
 // All output sections that are handled by the linker specially are
 // globally accessible. Writer initializes them, so don't use them
 // until Writer is initialized.
 struct Out {

lld/trunk/ELF/OutputSections.cpp

 #include "Config.h"
 #include "LinkerScript.h"
 #include "Memory.h"
 #include "Strings.h"
 #include "SymbolTable.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "Threads.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"
 
 using namespace llvm;
 using namespace llvm::dwarf;
 using namespace llvm::object;
static bool compareByFilePosition(InputSection *A, InputSection *B) {
   auto *LB = cast<InputSection>(B->getLinkOrderDep());
   OutputSection *AOut = LA->OutSec;
   OutputSection *BOut = LB->OutSec;
   if (AOut != BOut)
     return AOut->SectionIndex < BOut->SectionIndex;
   return LA->OutSecOff < LB->OutSecOff;
 }
 
+// Compressed sections has header which we create in this function.
+// Format is explaned here:
+// https://docs.oracle.com/cd/E53394_01/html/E54813/section_compression.html
+template <class ELFT>
+static std::vector<uint8_t> createHeader(size_t Size, uint32_t Alignment) {
+  const endianness E = ELFT::TargetEndianness;
+
+  std::vector<uint8_t> Ret(sizeof(typename ELFT::Chdr));
+  uint8_t *Buf = &Ret[0];
+  write32<E>(Buf, ELFCOMPRESS_ZLIB);
+  Buf += 4;
+
+  if (Config->Is64) {
+    Buf += sizeof(Elf64_Word); // Skip ch_reserved field.
+    write64<E>(Buf, Size);
+    Buf += sizeof(ELFT::Chdr::ch_size);
+    write64<E>(Buf, Alignment);
+    Buf += sizeof(ELFT::Chdr::ch_addralign);
+  } else {
+    write32<E>(Buf, Size);
+    Buf += sizeof(ELFT::Chdr::ch_size);
+    write32<E>(Buf, Alignment);
+    Buf += sizeof(ELFT::Chdr::ch_addralign);
+  }
+
+  return Ret;
+}
+
+template <class ELFT> void OutputSection::maybeCompress() {
+  // If -compress-debug-sections is specified, we compress output debug
+  // sections.
+  if (!Config->CompressDebugSections || !Name.startswith(".debug_") ||
+      (Flags & SHF_ALLOC))
+    return;
+
+  this->Flags |= SHF_COMPRESSED;
+  CompressedHeader = createHeader<ELFT>(this->Size, this->Alignment);
+
+  // Here we write relocated content of sections and compress it.
+  std::vector<uint8_t> Data(this->Size);
+  this->writeTo<ELFT>(&Data[0]);
+
+  if (Error E = zlib::compress(StringRef((char *)Data.data(), Data.size()),
+                               CompressedData))
+    fatal("compress failed: " + llvm::toString(std::move(E)));
+
+  this->Size = this->CompressedHeader.size() + this->CompressedData.size();
+}
+
 template <class ELFT> void OutputSection::finalize() {
   if ((this->Flags & SHF_LINK_ORDER) && !this->Sections.empty()) {
     std::sort(Sections.begin(), Sections.end(), compareByFilePosition);
     assignOffsets();
 
     // We must preserve the link order dependency of sections with the
     // SHF_LINK_ORDER flag. The dependency is indicated by the sh_link field. We
     // need to translate the InputSection sh_link to the OutputSection sh_link,
uint32_t OutputSection::getFiller() {
   if (Flags & SHF_EXECINSTR)
     return Target->TrapInstr;
   return 0;
 }
 
 template <class ELFT> void OutputSection::writeTo(uint8_t *Buf) {
   Loc = Buf;
 
+  // We may have already rendered compressed content when using
+  // -compress-debug-sections option. Write it together with header.
+  if (!CompressedData.empty()) {
+    memcpy(Buf, CompressedHeader.data(), CompressedHeader.size());
+    Buf += CompressedHeader.size();
+    memcpy(Buf, CompressedData.data(), CompressedData.size());
+    return;
+  }
+
   // Write leading padding.
   uint32_t Filler = getFiller();
   if (Filler)
     fill(Buf, Sections.empty() ? Size : Sections[0]->OutSecOff, Filler);
 
   parallelFor(0, Sections.size(), [=](size_t I) {
     InputSection *Sec = Sections[I];
     Sec->writeTo<ELFT>(Buf);

 template void OutputSection::writeHeaderTo<ELF64LE>(ELF64LE::Shdr *Shdr);
 template void OutputSection::writeHeaderTo<ELF64BE>(ELF64BE::Shdr *Shdr);
 
 template void OutputSection::finalize<ELF32LE>();
 template void OutputSection::finalize<ELF32BE>();
 template void OutputSection::finalize<ELF64LE>();
 template void OutputSection::finalize<ELF64BE>();
 
+template void OutputSection::maybeCompress<ELF32LE>();
+template void OutputSection::maybeCompress<ELF32BE>();
+template void OutputSection::maybeCompress<ELF64LE>();
+template void OutputSection::maybeCompress<ELF64BE>();
+
 template void OutputSection::writeTo<ELF32LE>(uint8_t *Buf);
 template void OutputSection::writeTo<ELF32BE>(uint8_t *Buf);
 template void OutputSection::writeTo<ELF64LE>(uint8_t *Buf);
 template void OutputSection::writeTo<ELF64BE>(uint8_t *Buf);

lld/trunk/ELF/Writer.cpp

 #include "MapFile.h"
 #include "Memory.h"
 #include "OutputSections.h"
 #include "Relocations.h"
 #include "Strings.h"
 #include "SymbolTable.h"
 #include "SyntheticSections.h"
 #include "Target.h"
+#include "Threads.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/FileOutputBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 #include <climits>
 
 using namespace llvm;
 using namespace llvm::ELF;
if (TC.createThunks(OutputSections))
                      [](SyntheticSection *SS) { SS->updateAllocSize(); });
   }
   // Fill other section headers. The dynamic table is finalized
   // at the end because some tags like RELSZ depend on result
   // of finalizing other sections.
   for (OutputSection *Sec : OutputSections)
     Sec->finalize<ELFT>();
 
+  // Some sections may require compression. That happens for
+  // debug sections when --compress-debug-sections option used.
+  parallelForEach(OutputSections.begin(), OutputSections.end(),
+                  [](OutputSection *S) { S->maybeCompress<ELFT>(); });
+
   // createThunks may have added local symbols to the static symbol table
   applySynthetic({In<ELFT>::SymTab, In<ELFT>::ShStrTab, In<ELFT>::StrTab},
                  [](SyntheticSection *SS) { SS->postThunkContents(); });
 }
 
 template <class ELFT> void Writer<ELFT>::addPredefinedSections() {
   // ARM ABI requires .ARM.exidx to be terminated by some piece of data.
   // We have the terminater synthetic section class. Add that at the end.

lld/trunk/test/ELF/compress-debug-output.s

+# REQUIRES: x86
+# REQUIRES: zlib
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
+# RUN: ld.lld %t.o -o %t1 --compress-debug-sections=zlib
+
+# RUN: llvm-objdump -s %t1 | FileCheck %s --check-prefix=ZLIBCONTENT
+# ZLIBCONTENT:     Contents of section .debug_str:
+# ZLIBCONTENT-NOT: AAAAAAAAA
+
+# RUN: llvm-readobj -s %t1 | FileCheck %s --check-prefix=ZLIBFLAGS
+# ZLIBFLAGS:       Section {
+# ZLIBFLAGS:         Index:
+# ZLIBFLAGS:         Name: .debug_str
+# ZLIBFLAGS-NEXT:    Type: SHT_PROGBITS
+# ZLIBFLAGS-NEXT:    Flags [
+# ZLIBFLAGS-NEXT:      SHF_COMPRESSED
+
+# RUN: llvm-dwarfdump %t1 -debug-dump=str | \
+# RUN:   FileCheck %s --check-prefix=DEBUGSTR
+# DEBUGSTR:     .debug_str contents:
+# DEBUGSTR-NEXT:  AAAAAAAAAAAAAAAAAAAAAAAAAAA
+# DEBUGSTR-NEXT:  BBBBBBBBBBBBBBBBBBBBBBBBBBB
+
+# RUN: not ld.lld %t.o -o %t1 --compress-debug-sections=zlib-gabi 2>&1 | \
+# RUN:   FileCheck -check-prefix=ERR %s
+# ERR: unknown --compress-debug-sections value: zlib-gabi
+
+.section .debug_str,"MS",@progbits,1
+.Linfo_string0:
+  .asciz "AAAAAAAAAAAAAAAAAAAAAAAAAAA"
+.Linfo_string1:
+  .asciz "BBBBBBBBBBBBBBBBBBBBBBBBBBB"