[lld][WebAssembly] Retain data segments referenced via __start/__stop

[kateinoigakukun]

Summary

As well as ELF linker does, retain all data segments named X referenced
through __start_X or __stop_X.

For example, FOO_MD should not be stripped in the below case, but it's currently mis-stripped

llvm
@FOO_MD  = global [4 x i8] c"bar\00", section "foo_md", align 1
@__start_foo_md = external constant i8*
@__stop_foo_md = external constant i8*
@llvm.used = appending global [1 x i8*] [i8* bitcast (i32 ()* @foo_md_size to i8*)], section "llvm.metadata"

define i32 @foo_md_size()  {
entry:
  ret i32 sub (
    i32 ptrtoint (i8** @__stop_foo_md to i32),
    i32 ptrtoint (i8** @__start_foo_md to i32)
  )
}

This fixes https://github.com/llvm/llvm-project/issues/55839

[sbc100]

lld/test/wasm/gc-sections-metadata-startstop.ll

1 ↗

(On Diff #433970)

We are trying to move away from .ll tests and stick to use .s tests as they tend to be easier to read/faster/fewer dependencies.

Would you mind converting this test to .s?

lld/wasm/InputChunks.cpp

531

I don't think you need the this-> qualifiers here .

lld/wasm/MarkLive.cpp

89

Just enqueueChunk seems descriptive enough, or maybe even just overload enqueue?

121

So, does this mean that if I reference the symbol __start_data, then all the normal data segment in my whole program will be included (non will be GC'd)?

Is this how ELF works? It seems like a shame to loose the ability to GC data segments just because i want to know where my data starts and/or stops. I suppose we have other symbols such as _edata which can be used to get the start/end of the static data region without disabling GC?

[kateinoigakukun]

addressed review comments

[kateinoigakukun]

lld/wasm/MarkLive.cpp

121

So, does this mean that if I reference the symbol __start_data, then all the normal data segment in my whole program will be included (non will be GC'd)?

Yes, I agree that's unfortunate situation...

Is this how ELF works?

To be precise, according to https://lld.llvm.org/ELF/start-stop-gc, whether __start/__stop symbols retain all input data segments is controlled by -z start-stop-gc / -z nostart-stop-gc.

The latest ELF lld defaults to -z start-stop-gc, but GNU ld defaults to -z nostart-stop-gc to be conservative.

So, how about adding the option in wasm-ld also? If it's reasonable, which behavior should be defaulted?

[sbc100]

lld/wasm/MarkLive.cpp

121

Yes, adding start-stop-gc as part of this change makes sense to me.

So simplify this you could split out of the moving of the getOutputDataSegmentName function amd land that first? It seems like a good refactoring anyway.

[sbc100]

lld/test/wasm/gc-sections-metadata-startstop.s

2

--gc-sections is the default under wasm so you don't need that here.

90

I think you can drop the .globl for everything but _start without effecting the test.

[sbc100]

I'm also fine with start-stop-gc being added a followup.

[kateinoigakukun]

In D126950#3556306, @sbc100 wrote:

I'm also fine with start-stop-gc being added a followup.

OK, let me do it in a follow-up patch 🙏

lld/test/wasm/gc-sections-metadata-startstop.s

2

Ah, I've intentionally added the option to indicate the main testing target is the option, but it's ok to remove indeed.

lld/wasm/MarkLive.cpp

121

OK, I'll make a separate patch for the refactoring first 👍

[kateinoigakukun]

addressed review comments, and simplify by separating NFC patch

[sbc100]

lld/test/wasm/gc-sections-metadata-startstop.s

2

Why not just call this gc-sections-startstop.s.. what is the metadata part referring too?

lld/wasm/MarkLive.cpp

117

I think you can just use segment->name here. That is what ELF seems to do

[kateinoigakukun]

lld/test/wasm/gc-sections-metadata-startstop.s

2

startstop feature is often used as metadata mechanism, so some other test cases have the metadata part as well, but it's fine to remove that part since it's descriptive enough.

[kateinoigakukun]

addressed review comments

[kateinoigakukun]

Thank you for your review @sbc100 !
I'll make a follow-up patch for start-stop-gc option next.

[MaskRay]

As well as ELF linker does, retain all data segments named X referenced through start_X or stop_X.

lld doesn't do this by default. This behavior requires -z nostart-stop-gc.

Not force retaining X allows fine-grained GC of metadata sections: https://maskray.me/blog/2021-01-31-metadata-sections-comdat-and-shf-link-order

[kateinoigakukun]

In D126950#3558023, @MaskRay wrote:

As well as ELF linker does, retain all data segments named X referenced through start_X or stop_X.

lld doesn't do this by default. This behavior requires -z nostart-stop-gc.

Not force retaining X allows fine-grained GC of metadata sections: https://maskray.me/blog/2021-01-31-metadata-sections-comdat-and-shf-link-order

Ah right, so my description is valid with GNU ld sorry. I'm going to add the option and make it default in wasm-ld.

[MaskRay]

In D126950#3558024, @kateinoigakukun wrote:

In D126950#3558023, @MaskRay wrote:

As well as ELF linker does, retain all data segments named X referenced through start_X or stop_X.

lld doesn't do this by default. This behavior requires -z nostart-stop-gc.

Not force retaining X allows fine-grained GC of metadata sections: https://maskray.me/blog/2021-01-31-metadata-sections-comdat-and-shf-link-order

Ah right, so my description is valid with GNU ld sorry. I'm going to add the option and make it default in wasm-ld.

-z start-stop-gc is the ideal behavior. I am concerned the behavior as defaulted by this patch will make incur unnecessary size costs to metadata sections.

[kateinoigakukun]

In D126950#3558031, @MaskRay wrote:

In D126950#3558024, @kateinoigakukun wrote:

In D126950#3558023, @MaskRay wrote:

As well as ELF linker does, retain all data segments named X referenced through start_X or stop_X.

lld doesn't do this by default. This behavior requires -z nostart-stop-gc.

Not force retaining X allows fine-grained GC of metadata sections: https://maskray.me/blog/2021-01-31-metadata-sections-comdat-and-shf-link-order

Ah right, so my description is valid with GNU ld sorry. I'm going to add the option and make it default in wasm-ld.

-z start-stop-gc is the ideal behavior. I am concerned the behavior as defaulted by this patch will make incur unnecessary size costs to metadata sections.

So should we revert this patch ASAP and reland with hiding it behind -z nostart-stop-gc? Or is it fine to wait for my upcoming follow-up patch?

[MaskRay]

I'd suggest a revert. Note that Mach-O ld64 matches the ld.lld behavior, too.

I think it needs justification to add a new option. If you want to retain a section, consider implementing something similar to SHF_GNU_RETAIN in ELF, instead of changing the linker GC to force retain sections.

lld/test/wasm/gc-sections-metadata-startstop.s

+# RUN: llvm-mc -triple=wasm32-unknown-unknown -filetype=obj -o %t.o %s
+# RUN: wasm-ld %t.o --gc-sections -o %t.wasm
+# RUN: llvm-objdump -d --no-show-raw-insn %t.wasm | FileCheck %s
+
+# FOO_MD symbol is not used directly, but is referenced through __start/__stop_foo_md
+  .globl  foo_md_size
+foo_md_size:
+  .functype foo_md_size () -> (i32)
+  i32.const __stop_foo_md
+  i32.const __start_foo_md
+  i32.sub 
+  end_function
+
+# CHECK: <foo_md_size>:
+# CHECK-EMPTY:
+# CHECK-NEXT: i32.const [[#STOP_ADDR:]]
+# CHECK-NEXT: i32.const [[#STOP_ADDR - 4]]
+# CHECK-NEXT: i32.sub 
+
+# All segments in concat_section section are marked as live.
+  .globl  concat_section_size
+concat_section_size:
+  .functype concat_section_size () -> (i32)
+  i32.const __stop_concat_section
+  i32.const __start_concat_section
+  i32.sub 
+  end_function
+
+# CHECK: <concat_section_size>:
+# CHECK-EMPTY:
+# CHECK-NEXT: i32.const [[#STOP_ADDR:]]
+# CHECK-NEXT: i32.const [[#STOP_ADDR - 8]]
+# CHECK-NEXT: i32.sub
+
+
+# __start/__stop symbols don't retain invalid C name sections
+  .globl  invalid_name_section_size
+invalid_name_section_size:
+  .functype invalid_name_section_size () -> (i32)
+  i32.const __stop_invalid.dot.name
+  i32.const __start_invalid.dot.name
+  i32.sub 
+  end_function
+
+# CHECK: <invalid_name_section_size>:
+# CHECK-EMPTY:
+# CHECK-NEXT: i32.const 0
+# CHECK-NEXT: i32.const 0
+# CHECK-NEXT: i32.sub
+
+
+  .globl  _start
+_start:
+  .functype _start () -> ()
+  call  foo_md_size
+  drop
+  call  concat_section_size
+  drop
+  call  invalid_name_section_size
+  drop
+  end_function
+
+
+  .section  foo_md,"",@
+  .globl  FOO_MD
+FOO_MD:
+  .asciz  "bar"
+  .size FOO_MD, 4
+
+  .size __start_foo_md, 4
+  .size __stop_foo_md, 4
+
+
+  .section  concat_section,"",@
+  .globl  concat_segment_1
+concat_segment_1:
+  .asciz  "xxx"
+  .size concat_segment_1, 4
+
+  .globl  concat_segment_2
+concat_segment_2:
+  .asciz  "yyy"
+  .size concat_segment_2, 4
+
+  .size __start_concat_section, 4
+  .size __stop_concat_section, 4
+
+
+  .section  invalid.dot.name,"",@
+  .globl  invalid_name_section
+invalid_name_section:
+  .asciz  "fizz"
+  .size invalid_name_section, 5
+
+  .weak __start_invalid.dot.name
+  .weak __stop_invalid.dot.name

lld/wasm/InputChunks.h

public:
   // the parent merged chunk.  For other chunk types this is no-op and we just
   // return unmodified offset.
   uint64_t getChunkOffset(uint64_t offset) const;
   uint64_t getVA(uint64_t offset = 0) const;
 
   uint32_t getComdat() const { return comdat; }
   StringRef getComdatName() const;
   uint32_t getInputSectionOffset() const { return inputSectionOffset; }
+  StringRef getOutputSegmentName() const;
 
   size_t getNumRelocations() const { return relocations.size(); }
   void writeRelocations(llvm::raw_ostream &os) const;
   void generateRelocationCode(raw_ostream &os) const;
 
   bool isTLS() const { return flags & llvm::wasm::WASM_SEG_FLAG_TLS; }
 
   ObjFile *file;

lld/wasm/InputChunks.cpp

uint64_t InputSection::getTombstoneForSection(StringRef name) {
   // will just use the addend.
   if (!name.startswith(".debug_"))
     return 0;
   if (name.equals(".debug_ranges") || name.equals(".debug_loc"))
     return UINT64_C(-2);
   return UINT64_C(-1);
 }
 
+StringRef InputChunk::getOutputSegmentName() const {
+  // We always merge .tbss and .tdata into a single TLS segment so all TLS
+  // symbols are be relative to single __tls_base.
+  if (isTLS())
+    return ".tdata";
+  StringRef name = getName();
+  if (!config->mergeDataSegments)
+    return name;
+  if (name.startswith(".text."))
+    return ".text";
+  if (name.startswith(".data."))
+    return ".data";
+  if (name.startswith(".bss."))
+    return ".bss";
+  if (name.startswith(".rodata."))
+    return ".rodata";
+  return name;
+}
+
 } // namespace wasm
 } // namespace lld

lld/wasm/MarkLive.cpp

 //===----------------------------------------------------------------------===//
 
 #include "MarkLive.h"
 #include "Config.h"
 #include "InputChunks.h"
 #include "InputElement.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
+#include "lld/Common/Strings.h"
 
 #define DEBUG_TYPE "lld"
 
 using namespace llvm;
 using namespace llvm::wasm;
 
 namespace lld {
 namespace wasm {
 
 namespace {
 
 class MarkLive {
 public:
   void run();
 
 private:
   void enqueue(Symbol *sym);
+  void enqueue(InputChunk *chunk);
   void enqueueInitFunctions(const ObjFile *sym);
   void mark();
   bool isCallCtorsLive();
 
   // A list of chunks to visit.
   SmallVector<InputChunk *, 256> queue;
 };
 
void MarkLive::enqueueInitFunctions(const ObjFile *obj) {
   const WasmLinkingData &l = obj->getWasmObj()->linkingData();
   for (const WasmInitFunc &f : l.InitFunctions) {
     auto *initSym = obj->getFunctionSymbol(f.Symbol);
     if (!initSym->isDiscarded())
       enqueue(initSym);
   }
 }
 
+void MarkLive::enqueue(InputChunk *chunk) {
+  LLVM_DEBUG(dbgs() << "markLive: " << chunk->getName() << "\n");
+  chunk->live = true;
+  queue.push_back(chunk);
+}
+
 void MarkLive::run() {
   // Add GC root symbols.
   if (!config->entry.empty())
     enqueue(symtab->find(config->entry));
 
   // We need to preserve any no-strip or exported symbol
   for (Symbol *sym : symtab->getSymbols())
     if (sym->isNoStrip() || sym->isExported())
       enqueue(sym);
 
   if (WasmSym::callDtors)
     enqueue(WasmSym::callDtors);
 
+  for (const ObjFile *obj : symtab->objectFiles) {
+    if (!obj->isLive()) {
+      continue;
+    }
     // Enqueue constructors in objects explicitly live from the command-line.
-  for (const ObjFile *obj : symtab->objectFiles)
-    if (obj->isLive())
-      enqueueInitFunctions(obj);
 
+    // Enqueue data segments referenced through __start/__stop symbols.
+    for (InputChunk *segment : obj->segments) {
+      auto name = segment->getOutputSegmentName();
+      if (!isValidCIdentifier(name))
+        continue;
+      if (symtab->find(("__start_" + name).str()) ||
+          symtab->find(("__stop_" + name).str())) {
+        enqueue(segment);
+      }
+    }
+  }
+
   mark();
 
   // If we have any non-discarded init functions, mark `__wasm_call_ctors` as
   // live so that we assign it an index and call it.
   if (isCallCtorsLive())
     WasmSym::callCtors->markLive();
 }
 

lld/wasm/Writer.cpp

void Writer::assignIndexes() {
 
   for (InputTable *table : symtab->syntheticTables)
     out.tableSec->addTable(table);
 
   out.globalSec->assignIndexes();
   out.tableSec->assignIndexes();
 }
 
-static StringRef getOutputDataSegmentName(const InputChunk &seg) {
-  // We always merge .tbss and .tdata into a single TLS segment so all TLS
-  // symbols are be relative to single __tls_base.
-  if (seg.isTLS())
-    return ".tdata";
-  StringRef name = seg.getName();
-  if (!config->mergeDataSegments)
-    return name;
-  if (name.startswith(".text."))
-    return ".text";
-  if (name.startswith(".data."))
-    return ".data";
-  if (name.startswith(".bss."))
-    return ".bss";
-  if (name.startswith(".rodata."))
-    return ".rodata";
-  return name;
-}
-
 OutputSegment *Writer::createOutputSegment(StringRef name) {
   LLVM_DEBUG(dbgs() << "new segment: " << name << "\n");
   OutputSegment *s = make<OutputSegment>(name);
   if (config->sharedMemory)
     s->initFlags = WASM_DATA_SEGMENT_IS_PASSIVE;
   if (!config->relocatable && name.startswith(".bss"))
     s->isBss = true;
   segments.push_back(s);
   return s;
 }
 
 void Writer::createOutputSegments() {
   for (ObjFile *file : symtab->objectFiles) {
     for (InputChunk *segment : file->segments) {
       if (!segment->live)
         continue;
-      StringRef name = getOutputDataSegmentName(*segment);
+      StringRef name = segment->getOutputSegmentName();
       OutputSegment *s = nullptr;
       // When running in relocatable mode we can't merge segments that are part
       // of comdat groups since the ultimate linker needs to be able exclude or
       // include them individually.
       if (config->relocatable && !segment->getComdatName().empty()) {
         s = createOutputSegment(name);
       } else {
         if (segmentMap.count(name) == 0)