[ELF] Add --compress-debug-sections=zstd

[MaskRay]

Summary

clang -gz=zstd a.o passes this option to the linker. This option compresses output
debug sections with zstd and sets ch_type to ELFCOMPRESS_ZSTD. As of today, very
few DWARF consumers recognize ELFCOMPRESS_ZSTD.

Use the llvm::zstd::compress API with level llvm::zstd::DefaultCompression (5),
which we may tune after we have more experience with zstd output.
zstd has built-in parallel compression support (so we don't need to do D117853
for zlib), which is not leveraged yet.

[MaskRay]

fix size
add link to patch

[peter.smith]

LGTM. I'm taking https://groups.google.com/g/generic-abi/c/satyPkuMisk as an acceptance that ELFCOMPRESS_ZSTD will make into ELF.

[MaskRay]

In D133548#3780223, @peter.smith wrote:

LGTM. I'm taking https://groups.google.com/g/generic-abi/c/satyPkuMisk as an acceptance that ELFCOMPRESS_ZSTD will make into ELF.

Thanks:) The official approval is https://groups.google.com/g/generic-abi/c/satyPkuMisk/m/KwTF_U8rBAAJ "I will add this to the ELF spec, as proposed below:"

lld/ELF/Config.h

 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Support/CachePruning.h"
 #include "llvm/Support/CodeGen.h"
+#include "llvm/Support/Compression.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/GlobPattern.h"
 #include "llvm/Support/PrettyStackTrace.h"
 #include <atomic>
 #include <memory>
 #include <vector>
 
 namespace lld::elf {
struct Configuration {
   bool armHasBlx = false;
   bool armHasMovtMovw = false;
   bool armJ1J2BranchEncoding = false;
   bool asNeeded = false;
   BsymbolicKind bsymbolic = BsymbolicKind::None;
   bool callGraphProfileSort;
   bool checkSections;
   bool checkDynamicRelocs;
-  bool compressDebugSections;
+  llvm::DebugCompressionType compressDebugSections;
   bool cref;
   llvm::SmallVector<std::pair<llvm::GlobPattern, uint64_t>, 0>
       deadRelocInNonAlloc;
   bool demangle = true;
   bool dependentLibraries;
   bool disableVerify;
   bool ehFrameHdr;
   bool emitLLVM;

lld/ELF/Driver.cpp

for (uint32_t i = 0, size = cgProfile.size(); i < size; ++i) {
       auto *from = dyn_cast_or_null<InputSectionBase>(fromSym->section);
       auto *to = dyn_cast_or_null<InputSectionBase>(toSym->section);
       if (from && to)
         config->callGraphProfile[{from, to}] += cgpe.cgp_weight;
     }
   }
 }
 
-static bool getCompressDebugSections(opt::InputArgList &args) {
+static DebugCompressionType getCompressDebugSections(opt::InputArgList &args) {
   StringRef s = args.getLastArgValue(OPT_compress_debug_sections, "none");
-  if (s == "none")
-    return false;
-  if (s != "zlib")
-    error("unknown --compress-debug-sections value: " + s);
+  if (s == "zlib") {
     if (!compression::zlib::isAvailable())
       error("--compress-debug-sections: zlib is not available");
-  return true;
+    return DebugCompressionType::Zlib;
+  }
+  if (s == "zstd") {
+    if (!compression::zstd::isAvailable())
+      error("--compress-debug-sections: zstd is not available");
+    return DebugCompressionType::Zstd;
+  }
+  if (s != "none")
+    error("unknown --compress-debug-sections value: " + s);
+  return DebugCompressionType::None;
 }
 
 static StringRef getAliasSpelling(opt::Arg *arg) {
   if (const opt::Arg *alias = arg->getAlias())
     return alias->getSpelling();
   return arg->getSpelling();
 }
 

lld/ELF/Options.td

 def : F<"build-id">, Alias<build_id>, AliasArgs<["fast"]>, HelpText<"Alias for --build-id=fast">;
 
 defm check_sections: B<"check-sections",
     "Check section addresses for overlaps (default)",
     "Do not check section addresses for overlaps">;
 
 defm compress_debug_sections:
   Eq<"compress-debug-sections", "Compress DWARF debug sections">,
-  MetaVarName<"[none,zlib]">;
+  MetaVarName<"[none,zlib,zstd]">;
 
 defm defsym: Eq<"defsym", "Define a symbol alias">, MetaVarName<"<symbol>=<value>">;
 
 defm optimize_bb_jumps: BB<"optimize-bb-jumps",
     "Remove direct jumps at the end to the next basic block",
     "Do not remove any direct jumps at the end to the next basic block (default)">;
 
 defm fortran_common : BB<"fortran-common",

lld/ELF/OutputSections.cpp

 #include "LinkerScript.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "lld/Common/Arrays.h"
 #include "lld/Common/Memory.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/Config/llvm-config.h" // LLVM_ENABLE_ZLIB
+#include "llvm/Support/Compression.h"
 #include "llvm/Support/Parallel.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/TimeProfiler.h"
 #if LLVM_ENABLE_ZLIB
 #include <zlib.h>
 #endif
 
 using namespace llvm;
static SmallVector<uint8_t, 0> deflateShard(ArrayRef<uint8_t> in, int level,
   out.truncate(pos);
   deflateEnd(&s);
   return out;
 }
 #endif
 
 // Compress section contents if this section contains debug info.
 template <class ELFT> void OutputSection::maybeCompress() {
-#if LLVM_ENABLE_ZLIB
   using Elf_Chdr = typename ELFT::Chdr;
 
   // Compress only DWARF debug sections.
-  if (!config->compressDebugSections || (flags & SHF_ALLOC) ||
-      !name.startswith(".debug_") || size == 0)
+  if (config->compressDebugSections == DebugCompressionType::None ||
+      (flags & SHF_ALLOC) || !name.startswith(".debug_") || size == 0)
     return;
 
   llvm::TimeTraceScope timeScope("Compress debug sections");
+  compressed.uncompressedSize = size;
+  auto buf = std::make_unique<uint8_t[]>(size);
+  if (config->compressDebugSections == DebugCompressionType::Zstd) {
+    {
+      parallel::TaskGroup tg;
+      writeTo<ELFT>(buf.get(), tg);
+    }
+    compressed.shards = std::make_unique<SmallVector<uint8_t, 0>[]>(1);
+    compression::zstd::compress(makeArrayRef(buf.get(), size),
+                                compressed.shards[0]);
+    size = sizeof(Elf_Chdr) + compressed.shards[0].size();
+    flags |= SHF_COMPRESSED;
+    return;
+  }
 
+#if LLVM_ENABLE_ZLIB
   // Write uncompressed data to a temporary zero-initialized buffer.
-  auto buf = std::make_unique<uint8_t[]>(size);
   {
     parallel::TaskGroup tg;
     writeTo<ELFT>(buf.get(), tg);
   }
   // We chose 1 (Z_BEST_SPEED) as the default compression level because it is
   // the fastest. If -O2 is given, we use level 6 to compress debug info more by
   // ~15%. We found that level 7 to 9 doesn't make much difference (~1% more
   // compression) while they take significant amount of time (~2x), so level 6
#if LLVM_ENABLE_ZLIB
   parallelFor(0, numShards, [&](size_t i) {
     shardsOut[i] = deflateShard(shardsIn[i], level,
                                 i != numShards - 1 ? Z_SYNC_FLUSH : Z_FINISH);
     shardsAdler[i] = adler32(1, shardsIn[i].data(), shardsIn[i].size());
   });
 
   // Update section size and combine Alder-32 checksums.
   uint32_t checksum = 1;       // Initial Adler-32 value
-  compressed.uncompressedSize = size;
   size = sizeof(Elf_Chdr) + 2; // Elf_Chdir and zlib header
   for (size_t i = 0; i != numShards; ++i) {
     size += shardsOut[i].size();
     checksum = adler32_combine(checksum, shardsAdler[i], shardsIn[i].size());
   }
   size += 4; // checksum
 
   compressed.shards = std::move(shardsOut);
void OutputSection::writeTo(uint8_t *buf, parallel::TaskGroup &tg) {
   if (type == SHT_NOBITS)
     return;
 
   // If --compress-debug-section is specified and if this is a debug section,
   // we've already compressed section contents. If that's the case,
   // just write it down.
   if (compressed.shards) {
     auto *chdr = reinterpret_cast<typename ELFT::Chdr *>(buf);
-    chdr->ch_type = ELFCOMPRESS_ZLIB;
     chdr->ch_size = compressed.uncompressedSize;
     chdr->ch_addralign = alignment;
     buf += sizeof(*chdr);
+    if (config->compressDebugSections == DebugCompressionType::Zstd) {
+      chdr->ch_type = ELFCOMPRESS_ZSTD;
+      memcpy(buf, compressed.shards[0].data(), compressed.shards[0].size());
+      return;
+    }
+    chdr->ch_type = ELFCOMPRESS_ZLIB;
 
     // Compute shard offsets.
     auto offsets = std::make_unique<size_t[]>(compressed.numShards);
     offsets[0] = 2; // zlib header
     for (size_t i = 1; i != compressed.numShards; ++i)
       offsets[i] = offsets[i - 1] + compressed.shards[i - 1].size();
 
     buf[0] = 0x78; // CMF

lld/docs/ReleaseNotes.rst

 Non-comprehensive list of changes in this release
 =================================================
 
 ELF Improvements
 ----------------
 
 * ``ELFCOMPRESS_ZSTD`` compressed input sections are now supported.
   (`D129406 <https://reviews.llvm.org/D129406>`_)
+* ``--compress-debug-sections=zstd`` is now available to compress debug
+  sections with zstd (``ELFCOMPRESS_ZSTD``).
+  (`D133548 <https://reviews.llvm.org/D133548>`_)
 
 Breaking changes
 ----------------
 
 COFF Improvements
 -----------------
 
 * ...

lld/docs/ld.lld.1

 .Cm never .
 .Cm auto
 enables color if and only if output is to a terminal.
 .It Fl -color-diagnostics
 Alias for
 .Fl -color-diagnostics Ns = Ns Cm auto .
 .It Fl -compress-debug-sections Ns = Ns Ar value
 Compress DWARF debug sections.
-.Ar value
+.Cm value
 may be
-.Cm none
-or
-.Cm zlib .
+.Pp
+.Bl -tag -width 2n -compact
+.It Cm none
+No compression.
+.It Cm zlib
 The default compression level is 1 (fastest) as the debug info usually
-compresses well at that level, but if you want to compress it more,
+compresses well at that level. If you want to compress it more,
 you can specify
 .Fl O2
 to set the compression level to 6.
+.It Cm zstd
+The compression level is 5.
+.El
+.Pp
 .It Fl -cref
 Output cross reference table. If
 .Fl Map
 is specified, print to the map file.
 .It Fl -defsym Ns = Ns Ar symbol Ns = Ns Ar expression
 Define a symbol alias.
 .Ar expression
 may be another symbol or a linker script expression.

lld/test/ELF/compress-debug-sections-zstd.s

 # REQUIRES: x86, zstd
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64 --compress-debug-sections=zstd %s -o %t.o
 
 # RUN: ld.lld %t.o -o %t.so -shared
 # RUN: llvm-readelf -S -x .debug_str %t.so | FileCheck %s
 
 # CHECK:      .debug_str    PROGBITS [[#%x,]] [[#%x,]] [[#%x,]] 01 MS  0 0  1
 # CHECK:      Hex dump of section '.debug_str':
 # CHECK-NEXT: 0x00000000 756e7369 676e6564 20696e74 00636861 unsigned int.cha
 # CHECK-NEXT: 0x00000010 7200756e 7369676e 65642063 68617200 r.unsigned char.
 # CHECK-NEXT: 0x00000020 73686f72 7420756e 7369676e 65642069 short unsigned i
 # CHECK-NEXT: 0x00000030 6e74006c 6f6e6720 756e7369 676e6564 nt.long unsigned
 # CHECK-NEXT: 0x00000040 20696e74 00                          int.
 
+# RUN: ld.lld %t.o -o %t.so -shared --compress-debug-sections=zstd
+# RUN: llvm-readelf -S %t.so | FileCheck %s --check-prefix=OUTPUT-SEC
+# RUN: llvm-objcopy --decompress-debug-sections %t.so
+# RUN: llvm-readelf -S -x .debug_str %t.so | FileCheck %s
+
+# OUTPUT-SEC: .debug_str    PROGBITS [[#%x,]] [[#%x,]] [[#%x,]] 01 MSC 0 0  1
+
 .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"