ELF/MarkLive.cpp - lld - Git at Google

 //===- MarkLive.cpp -------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements --gc-sections, which is a feature to remove unused
 // sections from output. Unused sections are sections that are not reachable
 // from known GC-root symbols or sections. Naturally the feature is
 // implemented as a mark-sweep garbage collector.
 //
 // Here's how it works. Each InputSectionBase has a "Live" bit. The bit is off
 // by default. Starting with GC-root symbols or sections, markLive function
 // defined in this file visits all reachable sections to set their Live
 // bits. Writer will then ignore sections whose Live bits are off, so that
 // such sections are not included into output.
 //
 //===----------------------------------------------------------------------===//

 #include "InputSection.h"
 #include "LinkerScript.h"
 #include "Memory.h"
 #include "OutputSections.h"
 #include "Strings.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Target.h"
 #include "Writer.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Object/ELF.h"
 #include <functional>
 #include <vector>

 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::support::endian;

 using namespace lld;
 using namespace lld::elf;

 namespace {
 // A resolved relocation. The Sec and Offset fields are set if the relocation
 // was resolved to an offset within a section.
 struct ResolvedReloc {
   InputSectionBase *Sec;
   uint64_t Offset;
 };
 } // end anonymous namespace

 template <class ELFT>
 static typename ELFT::uint getAddend(InputSectionBase &Sec,
                                      const typename ELFT::Rel &Rel) {
   return Target->getImplicitAddend(Sec.Data.begin() + Rel.r_offset,
                                    Rel.getType(Config->IsMips64EL));
 }

 template <class ELFT>
 static typename ELFT::uint getAddend(InputSectionBase &Sec,
                                      const typename ELFT::Rela &Rel) {
   return Rel.r_addend;
 }

 // There are normally few input sections whose names are valid C
 // identifiers, so we just store a std::vector instead of a multimap.
 static DenseMap<StringRef, std::vector<InputSectionBase *>> CNamedSections;

 template <class ELFT, class RelT>
 static void resolveReloc(InputSectionBase &Sec, RelT &Rel,
                          std::function<void(ResolvedReloc)> Fn) {
   SymbolBody &B = Sec.getFile<ELFT>()->getRelocTargetSym(Rel);
   if (auto *D = dyn_cast<DefinedRegular>(&B)) {
     if (!D->Section)
       return;
     typename ELFT::uint Offset = D->Value;
     if (D->isSection())
       Offset += getAddend<ELFT>(Sec, Rel);
     Fn({cast<InputSectionBase>(D->Section), Offset});
   } else if (auto *U = dyn_cast<Undefined>(&B)) {
     for (InputSectionBase *Sec : CNamedSections.lookup(U->getName()))
       Fn({Sec, 0});
   }
 }

 // Calls Fn for each section that Sec refers to via relocations.
 template <class ELFT>
 static void forEachSuccessor(InputSection &Sec,
                              std::function<void(ResolvedReloc)> Fn) {
   if (Sec.AreRelocsRela) {
     for (const typename ELFT::Rela &Rel : Sec.template relas<ELFT>())
       resolveReloc<ELFT>(Sec, Rel, Fn);
   } else {
     for (const typename ELFT::Rel &Rel : Sec.template rels<ELFT>())
       resolveReloc<ELFT>(Sec, Rel, Fn);
   }
   for (InputSectionBase *IS : Sec.DependentSections)
     Fn({IS, 0});
 }

 // The .eh_frame section is an unfortunate special case.
 // The section is divided in CIEs and FDEs and the relocations it can have are
 // * CIEs can refer to a personality function.
 // * FDEs can refer to a LSDA
 // * FDEs refer to the function they contain information about
 // The last kind of relocation cannot keep the referred section alive, or they
 // would keep everything alive in a common object file. In fact, each FDE is
 // alive if the section it refers to is alive.
 // To keep things simple, in here we just ignore the last relocation kind. The
 // other two keep the referred section alive.
 //
 // A possible improvement would be to fully process .eh_frame in the middle of
 // the gc pass. With that we would be able to also gc some sections holding
 // LSDAs and personality functions if we found that they were unused.
 template <class ELFT, class RelTy>
 static void scanEhFrameSection(EhInputSection &EH, ArrayRef<RelTy> Rels,
                                std::function<void(ResolvedReloc)> Enqueue) {
   const endianness E = ELFT::TargetEndianness;
   for (unsigned I = 0, N = EH.Pieces.size(); I < N; ++I) {
     EhSectionPiece &Piece = EH.Pieces[I];
     unsigned FirstRelI = Piece.FirstRelocation;
     if (FirstRelI == (unsigned)-1)
       continue;
     if (read32<E>(Piece.data().data() + 4) == 0) {
       // This is a CIE, we only need to worry about the first relocation. It is
       // known to point to the personality function.
       resolveReloc<ELFT>(EH, Rels[FirstRelI], Enqueue);
       continue;
     }
     // This is a FDE. The relocations point to the described function or to
     // a LSDA. We only need to keep the LSDA alive, so ignore anything that
     // points to executable sections.
     typename ELFT::uint PieceEnd = Piece.InputOff + Piece.size();
     for (unsigned I2 = FirstRelI, N2 = Rels.size(); I2 < N2; ++I2) {
       const RelTy &Rel = Rels[I2];
       if (Rel.r_offset >= PieceEnd)
         break;
       resolveReloc<ELFT>(EH, Rels[I2], [&](ResolvedReloc R) {
         if (!R.Sec || R.Sec == &InputSection::Discarded)
           return;
         if (R.Sec->Flags & SHF_EXECINSTR)
           return;
         Enqueue({R.Sec, 0});
       });
     }
   }
 }

 template <class ELFT>
 static void scanEhFrameSection(EhInputSection &EH,
                                std::function<void(ResolvedReloc)> Enqueue) {
   if (!EH.NumRelocations)
     return;

   // Unfortunately we need to split .eh_frame early since some relocations in
   // .eh_frame keep other section alive and some don't.
   EH.split<ELFT>();

   if (EH.AreRelocsRela)
     scanEhFrameSection<ELFT>(EH, EH.template relas<ELFT>(), Enqueue);
   else
     scanEhFrameSection<ELFT>(EH, EH.template rels<ELFT>(), Enqueue);
 }

 // We do not garbage-collect two types of sections:
 // 1) Sections used by the loader (.init, .fini, .ctors, .dtors or .jcr)
 // 2) Non-allocatable sections which typically contain debugging information
 template <class ELFT> static bool isReserved(InputSectionBase *Sec) {
   switch (Sec->Type) {
   case SHT_FINI_ARRAY:
   case SHT_INIT_ARRAY:
   case SHT_NOTE:
   case SHT_PREINIT_ARRAY:
     return true;
   default:
     if (!(Sec->Flags & SHF_ALLOC))
       return true;

     StringRef S = Sec->Name;
     return S.startswith(".ctors") || S.startswith(".dtors") ||
            S.startswith(".init") || S.startswith(".fini") ||
            S.startswith(".jcr");
   }
 }

 // This is the main function of the garbage collector.
 // Starting from GC-root sections, this function visits all reachable
 // sections to set their "Live" bits.
 template <class ELFT> void elf::markLive() {
   SmallVector<InputSection *, 256> Q;
   CNamedSections.clear();

   auto Enqueue = [&](ResolvedReloc R) {
     // Skip over discarded sections. This in theory shouldn't happen, because
     // the ELF spec doesn't allow a relocation to point to a deduplicated
     // COMDAT section directly. Unfortunately this happens in practice (e.g.
     // .eh_frame) so we need to add a check.
     if (R.Sec == &InputSection::Discarded)
       return;

     // We don't gc non alloc sections.
     if (!(R.Sec->Flags & SHF_ALLOC))
       return;

     // Usually, a whole section is marked as live or dead, but in mergeable
     // (splittable) sections, each piece of data has independent liveness bit.
     // So we explicitly tell it which offset is in use.
     if (auto *MS = dyn_cast<MergeInputSection>(R.Sec))
       MS->markLiveAt(R.Offset);

     if (R.Sec->Live)
       return;
     R.Sec->Live = true;
     // Add input section to the queue.
     if (InputSection *S = dyn_cast<InputSection>(R.Sec))
       Q.push_back(S);
   };

   auto MarkSymbol = [&](const SymbolBody *Sym) {
     if (auto *D = dyn_cast_or_null<DefinedRegular>(Sym))
       if (auto *IS = cast_or_null<InputSectionBase>(D->Section))
         Enqueue({IS, D->Value});
   };

   // Add GC root symbols.
   MarkSymbol(Symtab<ELFT>::X->find(Config->Entry));
   MarkSymbol(Symtab<ELFT>::X->find(Config->Init));
   MarkSymbol(Symtab<ELFT>::X->find(Config->Fini));
   for (StringRef S : Config->Undefined)
     MarkSymbol(Symtab<ELFT>::X->find(S));
   for (StringRef S : Script->Opt.ReferencedSymbols)
     MarkSymbol(Symtab<ELFT>::X->find(S));

   // Preserve externally-visible symbols if the symbols defined by this
   // file can interrupt other ELF file's symbols at runtime.
   for (const Symbol *S : Symtab<ELFT>::X->getSymbols())
     if (S->includeInDynsym())
       MarkSymbol(S->body());

   // Preserve special sections and those which are specified in linker
   // script KEEP command.
   for (InputSectionBase *Sec : InputSections) {
     // .eh_frame is always marked as live now, but also it can reference to
     // sections that contain personality. We preserve all non-text sections
     // referred by .eh_frame here.
     if (auto *EH = dyn_cast_or_null<EhInputSection>(Sec))
       scanEhFrameSection<ELFT>(*EH, Enqueue);
     if (Sec->Flags & SHF_LINK_ORDER)
       continue;
     if (isReserved<ELFT>(Sec) || Script->shouldKeep(Sec))
       Enqueue({Sec, 0});
     else if (isValidCIdentifier(Sec->Name)) {
       CNamedSections[Saver.save("__start_" + Sec->Name)].push_back(Sec);
       CNamedSections[Saver.save("__end_" + Sec->Name)].push_back(Sec);
     }
   }

   // Mark all reachable sections.
   while (!Q.empty())
     forEachSuccessor<ELFT>(*Q.pop_back_val(), Enqueue);
 }

 template void elf::markLive<ELF32LE>();
 template void elf::markLive<ELF32BE>();
 template void elf::markLive<ELF64LE>();
 template void elf::markLive<ELF64BE>();
	//===- MarkLive.cpp -------------------------------------------------------===//
	//
	// The LLVM Linker
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//
	//
	// This file implements --gc-sections, which is a feature to remove unused
	// sections from output. Unused sections are sections that are not reachable
	// from known GC-root symbols or sections. Naturally the feature is
	// implemented as a mark-sweep garbage collector.
	//
	// Here's how it works. Each InputSectionBase has a "Live" bit. The bit is off
	// by default. Starting with GC-root symbols or sections, markLive function
	// defined in this file visits all reachable sections to set their Live
	// bits. Writer will then ignore sections whose Live bits are off, so that
	// such sections are not included into output.
	//
	//===----------------------------------------------------------------------===//

	#include "InputSection.h"
	#include "LinkerScript.h"
	#include "Memory.h"
	#include "OutputSections.h"
	#include "Strings.h"
	#include "SymbolTable.h"
	#include "Symbols.h"
	#include "Target.h"
	#include "Writer.h"
	#include "llvm/ADT/STLExtras.h"
	#include "llvm/Object/ELF.h"
	#include <functional>
	#include <vector>

	using namespace llvm;
	using namespace llvm::ELF;
	using namespace llvm::object;
	using namespace llvm::support::endian;

	using namespace lld;
	using namespace lld::elf;

	namespace {
	// A resolved relocation. The Sec and Offset fields are set if the relocation
	// was resolved to an offset within a section.
	struct ResolvedReloc {
	InputSectionBase *Sec;
	uint64_t Offset;
	};
	} // end anonymous namespace

	template <class ELFT>
	static typename ELFT::uint getAddend(InputSectionBase &Sec,
	const typename ELFT::Rel &Rel) {
	return Target->getImplicitAddend(Sec.Data.begin() + Rel.r_offset,
	Rel.getType(Config->IsMips64EL));
	}

	template <class ELFT>
	static typename ELFT::uint getAddend(InputSectionBase &Sec,
	const typename ELFT::Rela &Rel) {
	return Rel.r_addend;
	}

	// There are normally few input sections whose names are valid C
	// identifiers, so we just store a std::vector instead of a multimap.
	static DenseMap<StringRef, std::vector<InputSectionBase *>> CNamedSections;

	template <class ELFT, class RelT>
	static void resolveReloc(InputSectionBase &Sec, RelT &Rel,
	std::function<void(ResolvedReloc)> Fn) {
	SymbolBody &B = Sec.getFile<ELFT>()->getRelocTargetSym(Rel);
	if (auto *D = dyn_cast<DefinedRegular>(&B)) {
	if (!D->Section)
	return;
	typename ELFT::uint Offset = D->Value;
	if (D->isSection())
	Offset += getAddend<ELFT>(Sec, Rel);
	Fn({cast<InputSectionBase>(D->Section), Offset});
	} else if (auto *U = dyn_cast<Undefined>(&B)) {
	for (InputSectionBase *Sec : CNamedSections.lookup(U->getName()))
	Fn({Sec, 0});
	}
	}

	// Calls Fn for each section that Sec refers to via relocations.
	template <class ELFT>
	static void forEachSuccessor(InputSection &Sec,
	std::function<void(ResolvedReloc)> Fn) {
	if (Sec.AreRelocsRela) {
	for (const typename ELFT::Rela &Rel : Sec.template relas<ELFT>())
	resolveReloc<ELFT>(Sec, Rel, Fn);
	} else {
	for (const typename ELFT::Rel &Rel : Sec.template rels<ELFT>())
	resolveReloc<ELFT>(Sec, Rel, Fn);
	}
	for (InputSectionBase *IS : Sec.DependentSections)
	Fn({IS, 0});
	}

	// The .eh_frame section is an unfortunate special case.
	// The section is divided in CIEs and FDEs and the relocations it can have are
	// * CIEs can refer to a personality function.
	// * FDEs can refer to a LSDA
	// * FDEs refer to the function they contain information about
	// The last kind of relocation cannot keep the referred section alive, or they
	// would keep everything alive in a common object file. In fact, each FDE is
	// alive if the section it refers to is alive.
	// To keep things simple, in here we just ignore the last relocation kind. The
	// other two keep the referred section alive.
	//
	// A possible improvement would be to fully process .eh_frame in the middle of
	// the gc pass. With that we would be able to also gc some sections holding
	// LSDAs and personality functions if we found that they were unused.
	template <class ELFT, class RelTy>
	static void scanEhFrameSection(EhInputSection &EH, ArrayRef<RelTy> Rels,
	std::function<void(ResolvedReloc)> Enqueue) {
	const endianness E = ELFT::TargetEndianness;
	for (unsigned I = 0, N = EH.Pieces.size(); I < N; ++I) {
	EhSectionPiece &Piece = EH.Pieces[I];
	unsigned FirstRelI = Piece.FirstRelocation;
	if (FirstRelI == (unsigned)-1)
	continue;
	if (read32<E>(Piece.data().data() + 4) == 0) {
	// This is a CIE, we only need to worry about the first relocation. It is
	// known to point to the personality function.
	resolveReloc<ELFT>(EH, Rels[FirstRelI], Enqueue);
	continue;
	}
	// This is a FDE. The relocations point to the described function or to
	// a LSDA. We only need to keep the LSDA alive, so ignore anything that
	// points to executable sections.
	typename ELFT::uint PieceEnd = Piece.InputOff + Piece.size();
	for (unsigned I2 = FirstRelI, N2 = Rels.size(); I2 < N2; ++I2) {
	const RelTy &Rel = Rels[I2];
	if (Rel.r_offset >= PieceEnd)
	break;
	resolveReloc<ELFT>(EH, Rels[I2], [&](ResolvedReloc R) {
	if (!R.Sec \|\| R.Sec == &InputSection::Discarded)
	return;
	if (R.Sec->Flags & SHF_EXECINSTR)
	return;
	Enqueue({R.Sec, 0});
	});
	}
	}
	}

	template <class ELFT>
	static void scanEhFrameSection(EhInputSection &EH,
	std::function<void(ResolvedReloc)> Enqueue) {
	if (!EH.NumRelocations)
	return;

	// Unfortunately we need to split .eh_frame early since some relocations in
	// .eh_frame keep other section alive and some don't.
	EH.split<ELFT>();

	if (EH.AreRelocsRela)
	scanEhFrameSection<ELFT>(EH, EH.template relas<ELFT>(), Enqueue);
	else
	scanEhFrameSection<ELFT>(EH, EH.template rels<ELFT>(), Enqueue);
	}

	// We do not garbage-collect two types of sections:
	// 1) Sections used by the loader (.init, .fini, .ctors, .dtors or .jcr)
	// 2) Non-allocatable sections which typically contain debugging information
	template <class ELFT> static bool isReserved(InputSectionBase *Sec) {
	switch (Sec->Type) {
	case SHT_FINI_ARRAY:
	case SHT_INIT_ARRAY:
	case SHT_NOTE:
	case SHT_PREINIT_ARRAY:
	return true;
	default:
	if (!(Sec->Flags & SHF_ALLOC))
	return true;

	StringRef S = Sec->Name;
	return S.startswith(".ctors") \|\| S.startswith(".dtors") \|\|
	S.startswith(".init") \|\| S.startswith(".fini") \|\|
	S.startswith(".jcr");
	}
	}

	// This is the main function of the garbage collector.
	// Starting from GC-root sections, this function visits all reachable
	// sections to set their "Live" bits.
	template <class ELFT> void elf::markLive() {
	SmallVector<InputSection *, 256> Q;
	CNamedSections.clear();

	auto Enqueue = [&](ResolvedReloc R) {
	// Skip over discarded sections. This in theory shouldn't happen, because
	// the ELF spec doesn't allow a relocation to point to a deduplicated
	// COMDAT section directly. Unfortunately this happens in practice (e.g.
	// .eh_frame) so we need to add a check.
	if (R.Sec == &InputSection::Discarded)
	return;

	// We don't gc non alloc sections.
	if (!(R.Sec->Flags & SHF_ALLOC))
	return;

	// Usually, a whole section is marked as live or dead, but in mergeable
	// (splittable) sections, each piece of data has independent liveness bit.
	// So we explicitly tell it which offset is in use.
	if (auto *MS = dyn_cast<MergeInputSection>(R.Sec))
	MS->markLiveAt(R.Offset);

	if (R.Sec->Live)
	return;
	R.Sec->Live = true;
	// Add input section to the queue.
	if (InputSection *S = dyn_cast<InputSection>(R.Sec))
	Q.push_back(S);
	};

	auto MarkSymbol = [&](const SymbolBody *Sym) {
	if (auto *D = dyn_cast_or_null<DefinedRegular>(Sym))
	if (auto *IS = cast_or_null<InputSectionBase>(D->Section))
	Enqueue({IS, D->Value});
	};

	// Add GC root symbols.
	MarkSymbol(Symtab<ELFT>::X->find(Config->Entry));
	MarkSymbol(Symtab<ELFT>::X->find(Config->Init));
	MarkSymbol(Symtab<ELFT>::X->find(Config->Fini));
	for (StringRef S : Config->Undefined)
	MarkSymbol(Symtab<ELFT>::X->find(S));
	for (StringRef S : Script->Opt.ReferencedSymbols)
	MarkSymbol(Symtab<ELFT>::X->find(S));

	// Preserve externally-visible symbols if the symbols defined by this
	// file can interrupt other ELF file's symbols at runtime.
	for (const Symbol *S : Symtab<ELFT>::X->getSymbols())
	if (S->includeInDynsym())
	MarkSymbol(S->body());

	// Preserve special sections and those which are specified in linker
	// script KEEP command.
	for (InputSectionBase *Sec : InputSections) {
	// .eh_frame is always marked as live now, but also it can reference to
	// sections that contain personality. We preserve all non-text sections
	// referred by .eh_frame here.
	if (auto *EH = dyn_cast_or_null<EhInputSection>(Sec))
	scanEhFrameSection<ELFT>(*EH, Enqueue);
	if (Sec->Flags & SHF_LINK_ORDER)
	continue;
	if (isReserved<ELFT>(Sec) \|\| Script->shouldKeep(Sec))
	Enqueue({Sec, 0});
	else if (isValidCIdentifier(Sec->Name)) {
	CNamedSections[Saver.save("__start_" + Sec->Name)].push_back(Sec);
	CNamedSections[Saver.save("__end_" + Sec->Name)].push_back(Sec);
	}
	}

	// Mark all reachable sections.
	while (!Q.empty())
	forEachSuccessor<ELFT>(*Q.pop_back_val(), Enqueue);
	}

	template void elf::markLive<ELF32LE>();
	template void elf::markLive<ELF32BE>();
	template void elf::markLive<ELF64LE>();
	template void elf::markLive<ELF64BE>();