Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Phabricator shutdown timeline

Differential D37626 Diff 490051 lld/ELF/MarkLive.cpp

Changeset View

Standalone View

View Options

lld/ELF/MarkLive.cpp

Show First 20 Lines • Show All 42 Lines • ▼ Show 20 Lines
namespace { namespace {
template <class ELFT> class MarkLive { template <class ELFT> class MarkLive {
public: public:
MarkLive(unsigned partition) : partition(partition) {} MarkLive(unsigned partition) : partition(partition) {}
void run(); void run();
void moveToMain(); void moveToMain();
// Scan .eh_frame sections and mark live FDEs and CIEs as well as all other
// sections referenced by them. This helps collecting sections which are
// referenced only by dead FDEs/CIEs.
// This should be called for the main partition, after processing all parts.
void processEhFrameSections();
private: private:
void enqueue(InputSectionBase *sec, uint64_t offset); void enqueue(InputSectionBase *sec, uint64_t offset);
void markSymbol(Symbol *sym); void markSymbol(Symbol *sym);
void mark(); void mark();
template <class RelTy> template <class RelTy>
void resolveReloc(InputSectionBase &sec, RelTy &rel, bool fromFDE); void resolveReloc(InputSectionBase &sec, RelTy &rel, bool fromFDE);
template <class RelTy> template <class RelTy>
void scanEhFrameSection(EhInputSection &eh, ArrayRef<RelTy> rels); void scanEhFrameSection(EhInputSection &eh, ArrayRef<RelTy> rels);
template <class RelTy>
void scanFde(EhInputSection &EH, ArrayRef<RelTy> Rels,
const EhSectionPiece &Fde);
template <class RelTy>
void scanCie(EhInputSection &EH, ArrayRef<RelTy> Rels,
const EhSectionPiece &Cie);
// The index of the partition that we are currently processing. // The index of the partition that we are currently processing.
unsigned partition; unsigned partition;
// A list of sections to visit. // A list of sections to visit.
SmallVector<InputSection *, 0> queue; SmallVector<InputSection *, 0> queue;
// There are normally few input sections whose names are valid C // There are normally few input sections whose names are valid C
// identifiers, so we just store a SmallVector instead of a multimap. // identifiers, so we just store a SmallVector instead of a multimap.
DenseMap<StringRef, SmallVector<InputSectionBase *, 0>> cNamedSections; DenseMap<StringRef, SmallVector<InputSectionBase *, 0>> cNamedSections;
}; };
} // namespace } // namespace
// Return a CIE referenced by a given FDE or nullptr if CIE could not be found.
template <class ELFT>
static EhSectionPiece *getCieForFde(const EhSectionPiece &fde,
SmallVectorImpl<EhSectionPiece> &cies) {
if (cies.empty())
return nullptr;
const uint32_t id = read32<ELFT::TargetEndianness>(fde.data().data() + 4);
uint32_t cieOffset = fde.inputOff + 4 - id;
// In most cases, an FDE refers to the most recent CIE.
if (cies.back().inputOff == cieOffset)
return &cies.back();
auto it = llvm::lower_bound(cies, cieOffset,
[](EhSectionPiece &cie, uint32_t offset) {
return cie.inputOff < offset;
});
if (it != cies.end() && (*it).inputOff == cieOffset)
return &*it;
return nullptr;
}
template <class ELFT> template <class ELFT>
static uint64_t getAddend(InputSectionBase &sec, static uint64_t getAddend(InputSectionBase &sec,
const typename ELFT::Rel &rel) { const typename ELFT::Rel &rel) {
return target->getImplicitAddend(sec.content().begin() + rel.r_offset, return target->getImplicitAddend(sec.content().begin() + rel.r_offset,
rel.getType(config->isMips64EL)); rel.getType(config->isMips64EL));
} }
template <class ELFT> template <class ELFT>
▲ Show 20 Lines • Show All 42 Lines • ▼ Show 20 Lines for (InputSectionBase *sec : cNamedSections.lookup(sym.getName()))
enqueue(sec, 0); enqueue(sec, 0);
} }
// The .eh_frame section is an unfortunate special case. // The .eh_frame section is an unfortunate special case.
// The section is divided in CIEs and FDEs and the relocations it can have are // The section is divided in CIEs and FDEs and the relocations it can have are
// * CIEs can refer to a personality function. // * CIEs can refer to a personality function.
// * FDEs can refer to a LSDA // * FDEs can refer to a LSDA
// * FDEs refer to the function they contain information about // * FDEs refer to the function they contain information about
// The last kind of relocation cannot keep the referred section alive, or they // The last kind of relocation is used to keep a FDE alive if the section
// would keep everything alive in a common object file. In fact, each FDE is // it refers to is alive. In that case, everything which is referenced from
// alive if the section it refers to is alive. // that FDE should be marked, including a LSDA, a CIE and a personality
// To keep things simple, in here we just ignore the last relocation kind. The // function. These sections might reference to other sections, so they
// other two keep the referred section alive. // are added to the GC queue.
//
// 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> template <class ELFT>
template <class RelTy> template <class RelTy>
void MarkLive<ELFT>::scanEhFrameSection(EhInputSection &eh, void MarkLive<ELFT>::scanEhFrameSection(EhInputSection &eh,
ArrayRef<RelTy> rels) { ArrayRef<RelTy> rels) {
for (const EhSectionPiece &cie : eh.cies) for (EhSectionPiece &fde : eh.fdes) {
if (cie.firstRelocation != unsigned(-1)) if (fde.live // This FDE is already fully processed.
resolveReloc(eh, rels[cie.firstRelocation], false); || !elf::isFdeLive<ELFT>(fde, rels))
for (const EhSectionPiece &fde : eh.fdes) {
size_t firstRelI = fde.firstRelocation;
if (firstRelI == (unsigned)-1)
continue; continue;
uint64_t pieceEnd = fde.inputOff + fde.size; fde.live = true;
for (size_t j = firstRelI, end2 = rels.size(); scanFde(eh, rels, fde);
j < end2 && rels[j].r_offset < pieceEnd; ++j)
resolveReloc(eh, rels[j], true); // Find the corresponding CIE.
EhSectionPiece *cie = getCieForFde<ELFT>(fde, eh.cies);
if (!cie)
fatal(toString(&eh) + ": invalid CIE reference");
if (cie->live) // Already processed.
continue;
cie->live = true;
scanCie(eh, rels, *cie);
}
}
template <class ELFT>
template <class RelTy>
void MarkLive<ELFT>::scanFde(EhInputSection &eh, ArrayRef<RelTy> rels,
const EhSectionPiece &fde) {
uint64_t fdeEnd = fde.inputOff + fde.size;
// The first relocation is known to point to the described function,
// so it is safe to skip it when looking for LSDAs.
for (unsigned i = fde.firstRelocation + 1, end = rels.size();
i < end && rels[i].r_offset < fdeEnd; ++i)
// In an FDE, the relocations point to the described function or to a LSDA.
// The described function is already marked and calling Fn for it is safe.
// Although the main intent here is to mark LSDAs, we do not need to
// recognize them especially and can process all references the same way.
resolveReloc(eh, rels[i], true);
} }
template <class ELFT>
template <class RelTy>
void MarkLive<ELFT>::scanCie(EhInputSection &eh, ArrayRef<RelTy> rels,
const EhSectionPiece &cie) {
if (cie.firstRelocation == (unsigned)-1)
return;
// In a CIE, we only need to worry about the first relocation.
// It is known to point to the personality function.
resolveReloc(eh, rels[cie.firstRelocation], false);
} }
// Some sections are used directly by the loader, so they should never be // Some sections are used directly by the loader, so they should never be
// garbage-collected. This function returns true if a given section is such // garbage-collected. This function returns true if a given section is such
// section. // section.
static bool isReserved(InputSectionBase *sec) { static bool isReserved(InputSectionBase *sec) {
switch (sec->type) { switch (sec->type) {
case SHT_FINI_ARRAY: case SHT_FINI_ARRAY:
▲ Show 20 Lines • Show All 60 Lines • ▼ Show 20 Linestemplate <class ELFT> void MarkLive<ELFT>::run() {
markSymbol(symtab.find(config->entry)); markSymbol(symtab.find(config->entry));
markSymbol(symtab.find(config->init)); markSymbol(symtab.find(config->init));
markSymbol(symtab.find(config->fini)); markSymbol(symtab.find(config->fini));
for (StringRef s : config->undefined) for (StringRef s : config->undefined)
markSymbol(symtab.find(s)); markSymbol(symtab.find(s));
for (StringRef s : script->referencedSymbols) for (StringRef s : script->referencedSymbols)
markSymbol(symtab.find(s)); markSymbol(symtab.find(s));
// Mark .eh_frame sections as live because there are usually no relocations
// that point to .eh_frames. Otherwise, the garbage collector would drop
// all of them. We also want to preserve personality routines and LSDA
// referenced by .eh_frame sections, so we scan them for that here.
for (EhInputSection *eh : ctx.ehInputSections) {
const RelsOrRelas<ELFT> rels = eh->template relsOrRelas<ELFT>();
if (rels.areRelocsRel())
scanEhFrameSection(*eh, rels.rels);
else if (rels.relas.size())
scanEhFrameSection(*eh, rels.relas);
}
for (InputSectionBase *sec : ctx.inputSections) { for (InputSectionBase *sec : ctx.inputSections) {
if (sec->flags & SHF_GNU_RETAIN) { if (sec->flags & SHF_GNU_RETAIN) {
enqueue(sec, 0); enqueue(sec, 0);
continue; continue;
} }
if (sec->flags & SHF_LINK_ORDER) if (sec->flags & SHF_LINK_ORDER)
continue; continue;
Show All 40 Lines if (isReserved(sec) || script->shouldKeep(sec)) {
cNamedSections[saver().save("__start_" + sec->name)].push_back(sec); cNamedSections[saver().save("__start_" + sec->name)].push_back(sec);
cNamedSections[saver().save("__stop_" + sec->name)].push_back(sec); cNamedSections[saver().save("__stop_" + sec->name)].push_back(sec);
} }
} }
mark(); mark();
} }
template <class ELFT> void MarkLive<ELFT>::processEhFrameSections() {
for (;;) {
for (EhInputSection *eh : ctx.ehInputSections) {
assert(eh->isLive() &&
"The section is expected to be marked in MarkLive<ELFT>::run()");
const RelsOrRelas<ELFT> rels = eh->template relsOrRelas<ELFT>();
if (rels.areRelocsRel())
scanEhFrameSection(*eh, rels.rels);
else if (rels.relas.size())
scanEhFrameSection(*eh, rels.relas);
}
if (queue.empty())
return;
mark();
}
}
template <class ELFT> void MarkLive<ELFT>::mark() { template <class ELFT> void MarkLive<ELFT>::mark() {
// Mark all reachable sections. // Mark all reachable sections.
while (!queue.empty()) { while (!queue.empty()) {
InputSectionBase &sec = *queue.pop_back_val(); InputSectionBase &sec = *queue.pop_back_val();
const RelsOrRelas<ELFT> rels = sec.template relsOrRelas<ELFT>(); const RelsOrRelas<ELFT> rels = sec.template relsOrRelas<ELFT>();
for (const typename ELFT::Rel &rel : rels.rels) for (const typename ELFT::Rel &rel : rels.rels)
resolveReloc(sec, rel, false); resolveReloc(sec, rel, false);
▲ Show 20 Lines • Show All 60 Lines • ▼ Show 20 Lines for (unsigned curPart = 1; curPart <= partitions.size(); ++curPart)
MarkLive<ELFT>(curPart).run(); MarkLive<ELFT>(curPart).run();
// If we have multiple partitions, some sections need to live in the main // If we have multiple partitions, some sections need to live in the main
// partition even if they were allocated to a loadable partition. Move them // partition even if they were allocated to a loadable partition. Move them
// there now. // there now.
if (partitions.size() != 1) if (partitions.size() != 1)
MarkLive<ELFT>(1).moveToMain(); MarkLive<ELFT>(1).moveToMain();
MarkLive<ELFT>(1).processEhFrameSections();
// Report garbage-collected sections. // Report garbage-collected sections.
if (config->printGcSections) if (config->printGcSections)
for (InputSectionBase *sec : ctx.inputSections) for (InputSectionBase *sec : ctx.inputSections)
if (!sec->isLive()) if (!sec->isLive())
message("removing unused section " + toString(sec)); message("removing unused section " + toString(sec));
} }
template void elf::markLive<ELF32LE>(); template void elf::markLive<ELF32LE>();
template void elf::markLive<ELF32BE>(); template void elf::markLive<ELF32BE>();
template void elf::markLive<ELF64LE>(); template void elf::markLive<ELF64LE>();
template void elf::markLive<ELF64BE>(); template void elf::markLive<ELF64BE>();