ELF: Do not use -1 to mark pieces of merge sections as being tail merged.

[pcc]

Summary

We were previously using an output offset of -1 for both GC'd and tail
merged pieces. We need to distinguish these two cases in order to filter
GC'd symbols from the symbol table -- we were previously asserting when we
asked for the VA of a symbol pointing into a dead piece, which would end
up asking the tail merging string table for an offset even though we hadn't
initialized it properly.

This patch fixes the bug by using an offset of -1 to exclusively mean GC'd
pieces, using 0 for tail merges, and distinguishing the tail merge case from
an offset of 0 by asking the output section whether it is tail merge.

[ruiu]

ELF/Writer.cpp

1127–1129 ↗

(On Diff #56232)

I may be missing something, but I don't think we gc pieces of mergeable sections. Instead, we gc a mergeable sections as a whole -- all the pieces in a mergeable section are gc'ed or not. So do you need this test?

[pcc]

ELF/Writer.cpp

1127–1129 ↗

(On Diff #56232)

It looks like we're GCing pieces here: http://llvm-cs.pcc.me.uk/tools/lld/ELF/MarkLive.cpp#146

[ruiu]

Ah, ok, it's new code. Uses of 0 and -1 are a bit too mysterious. Please define constants for them. With that, LGTM.

lld/trunk/ELF/InputSection.h

template <class ELFT> class SplitInputSection : public InputSectionBase<ELFT> {
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::uint uintX_t;
 
 public:
   SplitInputSection(ObjectFile<ELFT> *File, const Elf_Shdr *Header,
                     typename InputSectionBase<ELFT>::Kind SectionKind);
 
   // For each piece of data, we maintain the offsets in the input section and
-  // in the output section. The latter may be -1 if it is not assigned yet.
+  // in the output section.
   std::vector<std::pair<uintX_t, uintX_t>> Offsets;
 
+  // Merge input sections may use the following special values as the output
+  // section offset:
+  enum {
+    // The piece is dead.
+    PieceDead = uintX_t(-1),
+    // The piece is live, and an offset has not yet been assigned. After offsets
+    // have been assigned, if the output section uses tail merging, the field
+    // will still have this value and the output section offset is available
+    // from MergeOutputSection<ELFT>::getOffset(). Otherwise, this value has no
+    // special significance, it just means that the offset is 0.
+    PieceLive = uintX_t(0),
+  };
+
   std::pair<std::pair<uintX_t, uintX_t> *, uintX_t>
   getRangeAndSize(uintX_t Offset);
 };
 
 // This corresponds to a SHF_MERGE section of an input file.
 template <class ELFT> class MergeInputSection : public SplitInputSection<ELFT> {
   typedef typename ELFT::uint uintX_t;
   typedef typename ELFT::Sym Elf_Sym;

lld/trunk/ELF/InputSection.cpp

 MergeInputSection<ELFT>::MergeInputSection(elf::ObjectFile<ELFT> *F,
                                            const Elf_Shdr *Header)
     : SplitInputSection<ELFT>(F, Header, InputSectionBase<ELFT>::Merge) {
   uintX_t EntSize = Header->sh_entsize;
   ArrayRef<uint8_t> D = this->getSectionData();
   StringRef Data((const char *)D.data(), D.size());
   std::vector<std::pair<uintX_t, uintX_t>> &Offsets = this->Offsets;
 
-  uintX_t V = Config->GcSections ? -1 : 0;
+  uintX_t V = Config->GcSections ? MergeInputSection<ELFT>::PieceDead
+                                 : MergeInputSection<ELFT>::PieceLive;
   if (Header->sh_flags & SHF_STRINGS) {
     uintX_t Offset = 0;
     while (!Data.empty()) {
       size_t End = findNull(Data, EntSize);
       if (End == StringRef::npos)
         fatal("string is not null terminated");
       Offsets.push_back(std::make_pair(Offset, V));
       uintX_t Size = End + EntSize;
std::pair<std::pair<uintX_t, uintX_t> *, uintX_t> T =
       this->getRangeAndSize(Offset);
   std::pair<uintX_t, uintX_t> *I = T.first;
   uintX_t End = T.second;
   uintX_t Start = I->first;
 
   // Compute the Addend and if the Base is cached, return.
   uintX_t Addend = Offset - Start;
   uintX_t &Base = I->second;
-  if (Base != uintX_t(-1))
+  auto *MOS = static_cast<MergeOutputSection<ELFT> *>(this->OutSec);
+  if (!MOS->shouldTailMerge())
     return Base + Addend;
 
   // Map the base to the offset in the output section and cache it.
   ArrayRef<uint8_t> D = this->getSectionData();
   StringRef Data((const char *)D.data(), D.size());
   StringRef Entry = Data.substr(Start, End - Start);
-  Base =
-      static_cast<MergeOutputSection<ELFT> *>(this->OutSec)->getOffset(Entry);
+  Base = MOS->getOffset(Entry);
   return Base + Addend;
 }
 
 template <class ELFT>
 MipsReginfoInputSection<ELFT>::MipsReginfoInputSection(elf::ObjectFile<ELFT> *F,
                                                        const Elf_Shdr *Hdr)
     : InputSectionBase<ELFT>(F, Hdr, InputSectionBase<ELFT>::MipsReginfo) {
   // Initialize this->Reginfo.

lld/trunk/ELF/MarkLive.cpp

template <class ELFT> void elf::markLive() {
   SmallVector<InputSection<ELFT> *, 256> Q;
 
   auto Enqueue = [&](ResolvedReloc<ELFT> R) {
     if (!R.Sec)
       return;
     if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(R.Sec)) {
       std::pair<std::pair<uintX_t, uintX_t> *, uintX_t> T =
           MS->getRangeAndSize(R.Offset);
-      T.first->second = 0;
+      T.first->second = MergeInputSection<ELFT>::PieceLive;
     }
     if (R.Sec->Live)
       return;
     R.Sec->Live = true;
     if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(R.Sec))
       Q.push_back(S);
   };
 

lld/trunk/ELF/OutputSections.h

public:
   forEachInputSection(std::function<void(InputSectionBase<ELFT> *)> F) override;
   std::vector<InputSection<ELFT> *> Sections;
 };
 
 template <class ELFT>
 class MergeOutputSection final : public OutputSectionBase<ELFT> {
   typedef typename ELFT::uint uintX_t;
 
-  bool shouldTailMerge() const;
-
 public:
   MergeOutputSection(StringRef Name, uint32_t Type, uintX_t Flags,
                      uintX_t Alignment);
   void addSection(InputSectionBase<ELFT> *S) override;
   void writeTo(uint8_t *Buf) override;
   unsigned getOffset(StringRef Val);
   void finalize() override;
+  bool shouldTailMerge() const;
 
 private:
   llvm::StringTableBuilder Builder;
 };
 
 // FDE or CIE
 template <class ELFT> struct EHRegion {
   typedef typename ELFT::uint uintX_t;

lld/trunk/ELF/OutputSections.cpp

void MergeOutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
   uintX_t EntSize = S->getSectionHdr()->sh_entsize;
   this->Header.sh_entsize = EntSize;
   MutableArrayRef<std::pair<uintX_t, uintX_t>> Offsets = S->Offsets;
 
   // If this is of type string, the contents are null-terminated strings.
   if (this->Header.sh_flags & SHF_STRINGS) {
     for (unsigned I = 0, N = Offsets.size(); I != N; ++I) {
       auto &P = Offsets[I];
-      if (P.second == (uintX_t)-1)
+      if (P.second == MergeInputSection<ELFT>::PieceDead)
         continue;
 
       uintX_t Start = P.first;
       uintX_t End = (I == N - 1) ? Data.size() : Offsets[I + 1].first;
       StringRef Entry = Data.substr(Start, End - Start);
       uintX_t OutputOffset = Builder.add(Entry);
       if (shouldTailMerge())
-        OutputOffset = -1;
+        OutputOffset = MergeInputSection<ELFT>::PieceLive;
       P.second = OutputOffset;
     }
     return;
   }
 
   // If this is not of type string, every entry has the same size.
   for (auto &P : Offsets) {
     if (P.second == (uintX_t)-1)

lld/trunk/ELF/Writer.cpp

addOptionalSynthetic(Symtab, S, Out<ELFT>::RelaPlt,
                        DefinedSynthetic<ELFT>::SectionEnd);
 }
 
 template <class ELFT> static bool includeInSymtab(const SymbolBody &B) {
   if (!B.symbol()->IsUsedInRegularObj)
     return false;
 
   if (auto *D = dyn_cast<DefinedRegular<ELFT>>(&B)) {
+    // Always include absolute symbols.
+    if (!D->Section)
+      return true;
     // Exclude symbols pointing to garbage-collected sections.
-    if (D->Section && !D->Section->Live)
+    if (!D->Section->Live)
+      return false;
+    if (auto *S = dyn_cast<MergeInputSection<ELFT>>(D->Section))
+      if (S->getRangeAndSize(D->Value).first->second ==
+          MergeInputSection<ELFT>::PieceDead)
         return false;
   }
   return true;
 }
 
 // This class knows how to create an output section for a given
 // input section. Output section type is determined by various
 // factors, including input section's sh_flags, sh_type and
 // linker scripts.

lld/trunk/test/ELF/string-gc.s

+// RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
+// RUN: ld.lld %t.o -o %t --gc-sections
+// RUN: llvm-readobj -symbols %t | FileCheck %s
+
+// CHECK:      Symbols [
+// CHECK-NEXT:   Symbol {
+// CHECK-NEXT:     Name:  (0)
+// CHECK-NEXT:     Value: 0x0
+// CHECK-NEXT:     Size: 0
+// CHECK-NEXT:     Binding: Local (0x0)
+// CHECK-NEXT:     Type: None (0x0)
+// CHECK-NEXT:     Other: 0
+// CHECK-NEXT:     Section: Undefined (0x0)
+// CHECK-NEXT:   }
+// CHECK-NEXT:   Symbol {
+// CHECK-NEXT:     Name: s1 (8)
+// CHECK-NEXT:     Value: 0x10120
+// CHECK-NEXT:     Size: 0
+// CHECK-NEXT:     Binding: Local (0x0)
+// CHECK-NEXT:     Type: Object (0x1)
+// CHECK-NEXT:     Other [ (0x2)
+// CHECK-NEXT:       STV_HIDDEN (0x2)
+// CHECK-NEXT:     ]
+// CHECK-NEXT:     Section: .rodata (0x1)
+// CHECK-NEXT:   }
+// CHECK-NEXT:   Symbol {
+// CHECK-NEXT:     Name: _start (1)
+// CHECK-NEXT:     Value: 0x11000
+// CHECK-NEXT:     Size: 0
+// CHECK-NEXT:     Binding: Global (0x1)
+// CHECK-NEXT:     Type: Function (0x2)
+// CHECK-NEXT:     Other: 0
+// CHECK-NEXT:     Section: .text (0x2)
+// CHECK-NEXT:   }
+// CHECK-NEXT: ]
+
+.text
+.globl _start
+.type _start,@function
+_start:
+movl $s1, %eax
+
+.hidden s1
+.type s1,@object
+.section .rodata.str1.1,"aMS",@progbits,1
+.globl s1
+s1:
+.asciz "abcd"
+
+.hidden s2
+.type s2,@object
+.globl s2
+s2:
+.asciz "efgh"