From 5c073a94f9c25e73d78dbeb8eb7b1b3a60d7dd1f Mon Sep 17 00:00:00 2001 From: Rui Ueyama Date: Thu, 16 May 2019 03:29:03 +0000 Subject: [PATCH] Introduce CommonSymbol. Previously, we handled common symbols as a kind of Defined symbol, but what we were doing for common symbols is pretty different from regular defined symbols. Common symbol and defined symbol are probably as different as shared symbol and defined symbols are different. This patch introduces CommonSymbol to represent common symbols. After symbols are resolved, they are converted to Defined symbols residing in a .bss section. Differential Revision: https://reviews.llvm.org/D61895 llvm-svn: 360841 --- lld/ELF/Driver.cpp | 24 ++++++ lld/ELF/InputFiles.cpp | 8 +- lld/ELF/LinkerScript.cpp | 8 +- lld/ELF/SymbolTable.cpp | 196 ++++++++++++++++++++++------------------------- lld/ELF/SymbolTable.h | 8 +- lld/ELF/Symbols.cpp | 4 +- lld/ELF/Symbols.h | 38 +++++++++ lld/ELF/Writer.cpp | 21 ++--- 8 files changed, 183 insertions(+), 124 deletions(-) diff --git a/lld/ELF/Driver.cpp b/lld/ELF/Driver.cpp index 503575a..9a2ecbb 100644 --- a/lld/ELF/Driver.cpp +++ b/lld/ELF/Driver.cpp @@ -1323,6 +1323,27 @@ template static void handleLibcall(StringRef Name) { Symtab->fetchLazy(Sym); } +// Replaces common symbols with defined symbols reside in .bss sections. +// This function is called after all symbol names are resolved. As a +// result, the passes after the symbol resolution won't see any +// symbols of type CommonSymbol. +static void replaceCommonSymbols() { + for (Symbol *Sym : Symtab->getSymbols()) { + auto *S = dyn_cast(Sym); + if (!S) + continue; + + auto *Bss = make("COMMON", S->Size, S->Alignment); + Bss->File = S->File; + Bss->Live = !Config->GcSections; + InputSections.push_back(Bss); + + Defined New(S->File, S->getName(), S->Binding, S->StOther, S->Type, + /*Value=*/0, S->Size, Bss); + replaceSymbol(S, &New); + } +} + // If all references to a DSO happen to be weak, the DSO is not added // to DT_NEEDED. If that happens, we need to eliminate shared symbols // created from the DSO. Otherwise, they become dangling references @@ -1681,6 +1702,9 @@ template void LinkerDriver::link(opt::InputArgList &Args) { if (!Config->Relocatable) InputSections.push_back(createCommentSection()); + // Replace common symbols with regular symbols. + replaceCommonSymbols(); + // Do size optimizations: garbage collection, merging of SHF_MERGE sections // and identical code folding. splitSections(); diff --git a/lld/ELF/InputFiles.cpp b/lld/ELF/InputFiles.cpp index 1420705..17e7dfa 100644 --- a/lld/ELF/InputFiles.cpp +++ b/lld/ELF/InputFiles.cpp @@ -899,7 +899,7 @@ template Symbol *ObjFile::createSymbol(const Elf_Sym *Sym) { fatal(toString(this) + ": common symbol '" + Name + "' has invalid alignment: " + Twine(Value)); return Symtab->addCommon( - Defined{this, Name, Binding, StOther, Type, Value, Size, nullptr}); + CommonSymbol{this, Name, Binding, StOther, Type, Value, Size}); } switch (Binding) { @@ -1266,9 +1266,9 @@ static Symbol *createBitcodeSymbol(const std::vector &KeptComdats, } if (ObjSym.isCommon()) - return Symtab->addCommon(Defined{&F, Name, Binding, Visibility, STT_OBJECT, - ObjSym.getCommonAlignment(), - ObjSym.getCommonSize(), nullptr}); + return Symtab->addCommon( + CommonSymbol{&F, Name, Binding, Visibility, STT_OBJECT, + ObjSym.getCommonAlignment(), ObjSym.getCommonSize()}); Defined New(&F, Name, Binding, Visibility, Type, 0, 0, nullptr); if (CanOmitFromDynSym) diff --git a/lld/ELF/LinkerScript.cpp b/lld/ELF/LinkerScript.cpp index 5d7f2d9..eb70331 100644 --- a/lld/ELF/LinkerScript.cpp +++ b/lld/ELF/LinkerScript.cpp @@ -186,8 +186,8 @@ void LinkerScript::addSymbol(SymbolAssignment *Cmd) { Defined New(nullptr, Cmd->Name, STB_GLOBAL, Visibility, STT_NOTYPE, SymValue, 0, Sec); - Symbol *Sym; - std::tie(Sym, std::ignore) = Symtab->insert(New); + Symbol *Sym = Symtab->insert(New); + Symtab->mergeProperties(Sym, New); replaceSymbol(Sym, &New); Cmd->Sym = cast(Sym); } @@ -203,8 +203,8 @@ static void declareSymbol(SymbolAssignment *Cmd) { nullptr); // We can't calculate final value right now. - Symbol *Sym; - std::tie(Sym, std::ignore) = Symtab->insert(New); + Symbol *Sym = Symtab->insert(New); + Symtab->mergeProperties(Sym, New); replaceSymbol(Sym, &New); Cmd->Sym = cast(Sym); diff --git a/lld/ELF/SymbolTable.cpp b/lld/ELF/SymbolTable.cpp index 9c56178..387e92c 100644 --- a/lld/ELF/SymbolTable.cpp +++ b/lld/ELF/SymbolTable.cpp @@ -86,11 +86,8 @@ static uint8_t getMinVisibility(uint8_t VA, uint8_t VB) { return std::min(VA, VB); } -// Find an existing symbol or create and insert a new one, then apply the given -// attributes. -std::pair SymbolTable::insert(const Symbol &New) { - // Find an existing symbol or create and insert a new one. - +// Find an existing symbol or create and insert a new one. +Symbol *SymbolTable::insert(const Symbol &New) { // @@ means the symbol is the default version. In that // case @@ will be used to resolve references to . // @@ -130,26 +127,36 @@ std::pair SymbolTable::insert(const Symbol &New) { Old = SymVector[SymIndex]; } + return Old; +} + +// Merge symbol properties. +// +// When we have many symbols of the same name, we choose one of them, +// and that's the result of symbol resolution. However, symbols that +// were not chosen still affect some symbol properteis. +void SymbolTable::mergeProperties(Symbol *Old, const Symbol &New) { // Merge symbol properties. Old->ExportDynamic = Old->ExportDynamic || New.ExportDynamic; Old->IsUsedInRegularObj = Old->IsUsedInRegularObj || New.IsUsedInRegularObj; // DSO symbols do not affect visibility in the output. - if (!isa(&New)) + if (!isa(New)) Old->Visibility = getMinVisibility(Old->Visibility, New.Visibility); - - return {Old, IsNew}; } template Symbol *SymbolTable::addUndefined(const Undefined &New) { - Symbol *Old; - bool WasInserted; - std::tie(Old, WasInserted) = insert(New); + Symbol *Old = insert(New); + mergeProperties(Old, New); + + if (Old->isPlaceholder()) { + replaceSymbol(Old, &New); + return Old; + } // An undefined symbol with non default visibility must be satisfied // in the same DSO. - if (WasInserted || - (isa(Old) && New.Visibility != STV_DEFAULT)) { + if (Old->isShared() && New.Visibility != STV_DEFAULT) { replaceSymbol(Old, &New); return Old; } @@ -245,95 +252,80 @@ static int compareVersion(StringRef OldName, StringRef NewName) { return 0; } -// We have a new defined symbol with the specified binding. Return 1 if the new -// symbol should win, -1 if the new symbol should lose, or 0 if both symbols are -// strong defined symbols. -static int compareDefined(const Symbol *Old, const Symbol *New) { - if (!Old->isDefined()) +// Compare two symbols. Return 1 if the new symbol should win, -1 if +// the new symbol should lose, or 0 if there is a conflict. +static int compare(const Symbol *Old, const Symbol *New) { + assert(New->isDefined() || New->isCommon()); + + if (!Old->isDefined() && !Old->isCommon()) return 1; + if (int Cmp = compareVersion(Old->getName(), New->getName())) return Cmp; - if (New->Binding == STB_WEAK) + + if (New->isWeak()) return -1; + if (Old->isWeak()) return 1; - return 0; -} -// We have a new non-common defined symbol with the specified binding. Return 1 -// if the new symbol should win, -1 if the new symbol should lose, or 0 if there -// is a conflict. If the new symbol wins, also update the binding. -static int compareDefinedNonCommon(const Symbol *OldSym, const Defined *New) { - if (int Cmp = compareDefined(OldSym, New)) - return Cmp; - - if (auto *Old = dyn_cast(OldSym)) { - if (Old->Section && isa(Old->Section)) { - // Non-common symbols take precedence over common symbols. - if (Config->WarnCommon) - warn("common " + Old->getName() + " is overridden"); - return 1; - } + if (Old->isCommon() && New->isCommon()) { + if (Config->WarnCommon) + warn("multiple common of " + Old->getName()); + return 0; + } - if (New->File && isa(New->File)) - return 0; + if (Old->isCommon()) { + if (Config->WarnCommon) + warn("common " + Old->getName() + " is overridden"); + return 1; + } - if (Old->Section == nullptr && New->Section == nullptr && - Old->Value == New->Value && New->Binding == STB_GLOBAL) - return -1; + if (New->isCommon()) { + if (Config->WarnCommon) + warn("common " + Old->getName() + " is overridden"); + return -1; } + + auto *OldSym = cast(Old); + auto *NewSym = cast(New); + + if (New->File && isa(New->File)) + return 0; + + if (!OldSym->Section && !NewSym->Section && OldSym->Value == NewSym->Value && + NewSym->Binding == STB_GLOBAL) + return -1; + return 0; } -Symbol *SymbolTable::addCommon(const Defined &New) { - Symbol *Old; - bool WasInserted; - std::tie(Old, WasInserted) = insert(New); - - auto Replace = [&] { - auto *Bss = make("COMMON", New.Size, New.Value); - Bss->File = New.File; - Bss->Live = !Config->GcSections; - InputSections.push_back(Bss); - - Defined Sym = New; - Sym.Value = 0; - Sym.Section = Bss; - replaceSymbol(Old, &Sym); - }; - - if (WasInserted) { - Replace(); +Symbol *SymbolTable::addCommon(const CommonSymbol &New) { + Symbol *Old = insert(New); + mergeProperties(Old, New); + + if (Old->isPlaceholder()) { + replaceSymbol(Old, &New); return Old; } - int Cmp = compareDefined(Old, &New); + int Cmp = compare(Old, &New); if (Cmp < 0) return Old; if (Cmp > 0) { - Replace(); - return Old; - } - - auto *D = cast(Old); - auto *Bss = dyn_cast_or_null(D->Section); - if (!Bss) { - // Non-common symbols take precedence over common symbols. - if (Config->WarnCommon) - warn("common " + Old->getName() + " is overridden"); + replaceSymbol(Old, &New); return Old; } - if (Config->WarnCommon) - warn("multiple common of " + D->getName()); + CommonSymbol *OldSym = cast(Old); - Bss->Alignment = std::max(Bss->Alignment, New.Value); - if (New.Size > Bss->Size) { - D->File = Bss->File = New.File; - D->Size = Bss->Size = New.Size; + OldSym->Alignment = std::max(OldSym->Alignment, New.Alignment); + if (OldSym->Size < New.Size) { + OldSym->File = New.File; + OldSym->Size = New.Size; } - return Old; + return OldSym; } static void reportDuplicate(Symbol *Sym, InputFile *NewFile, @@ -371,38 +363,38 @@ static void reportDuplicate(Symbol *Sym, InputFile *NewFile, error(Msg); } -Defined *SymbolTable::addDefined(const Defined &New) { - Symbol *Old; - bool WasInserted; - std::tie(Old, WasInserted) = insert(New); +Symbol *SymbolTable::addDefined(const Defined &New) { + Symbol *Old = insert(New); + mergeProperties(Old, New); - if (WasInserted) { + if (Old->isPlaceholder()) { replaceSymbol(Old, &New); - return cast(Old); + return Old; } - int Cmp = compareDefinedNonCommon(Old, &New); + int Cmp = compare(Old, &New); if (Cmp > 0) replaceSymbol(Old, &New); else if (Cmp == 0) reportDuplicate(Old, New.File, dyn_cast_or_null(New.Section), New.Value); - return cast(Old); + return Old; } void SymbolTable::addShared(const SharedSymbol &New) { - Symbol *Old; - bool WasInserted; - std::tie(Old, WasInserted) = insert(New); + Symbol *Old = insert(New); + mergeProperties(Old, New); // Make sure we preempt DSO symbols with default visibility. if (New.Visibility == STV_DEFAULT) Old->ExportDynamic = true; - if (WasInserted) { + if (Old->isPlaceholder()) { replaceSymbol(Old, &New); - } else if (Old->Visibility == STV_DEFAULT && - (Old->isUndefined() || Old->isLazy())) { + return; + } + + if (Old->Visibility == STV_DEFAULT && (Old->isUndefined() || Old->isLazy())) { // An undefined symbol with non default visibility must be satisfied // in the same DSO. uint8_t Binding = Old->Binding; @@ -412,16 +404,15 @@ void SymbolTable::addShared(const SharedSymbol &New) { } Symbol *SymbolTable::addBitcode(const Defined &New) { - Symbol *Old; - bool WasInserted; - std::tie(Old, WasInserted) = insert(New); + Symbol *Old = insert(New); + mergeProperties(Old, New); - if (WasInserted) { + if (Old->isPlaceholder()) { replaceSymbol(Old, &New); return Old; } - int Cmp = compareDefinedNonCommon(Old, &New); + int Cmp = compare(Old, &New); if (Cmp > 0) replaceSymbol(Old, &New); else if (Cmp == 0) @@ -439,11 +430,10 @@ Symbol *SymbolTable::find(StringRef Name) { } template void SymbolTable::addLazy(const LazyT &New) { - Symbol *Old; - bool WasInserted; - std::tie(Old, WasInserted) = insert(New); + Symbol *Old = insert(New); + mergeProperties(Old, New); - if (WasInserted) { + if (Old->isPlaceholder()) { replaceSymbol(Old, &New); return; } @@ -502,7 +492,7 @@ StringMap> &SymbolTable::getDemangledSyms() { if (!DemangledSyms) { DemangledSyms.emplace(); for (Symbol *Sym : SymVector) { - if (!Sym->isDefined()) + if (!Sym->isDefined() && !Sym->isCommon()) continue; if (Optional S = demangleItanium(Sym->getName())) (*DemangledSyms)[*S].push_back(Sym); @@ -517,7 +507,7 @@ std::vector SymbolTable::findByVersion(SymbolVersion Ver) { if (Ver.IsExternCpp) return getDemangledSyms().lookup(Ver.Name); if (Symbol *B = find(Ver.Name)) - if (B->isDefined()) + if (B->isDefined() || B->isCommon()) return {B}; return {}; } @@ -534,7 +524,7 @@ std::vector SymbolTable::findAllByVersion(SymbolVersion Ver) { } for (Symbol *Sym : SymVector) - if (Sym->isDefined() && M.match(Sym->getName())) + if ((Sym->isDefined() || Sym->isCommon()) && M.match(Sym->getName())) Res.push_back(Sym); return Res; } diff --git a/lld/ELF/SymbolTable.h b/lld/ELF/SymbolTable.h index 4176f16..ad4329f 100644 --- a/lld/ELF/SymbolTable.h +++ b/lld/ELF/SymbolTable.h @@ -18,6 +18,7 @@ namespace lld { namespace elf { +class CommonSymbol; class Defined; class LazyArchive; class LazyObject; @@ -46,7 +47,7 @@ public: template Symbol *addUndefined(const Undefined &New); - Defined *addDefined(const Defined &New); + Symbol *addDefined(const Defined &New); void addShared(const SharedSymbol &New); @@ -54,9 +55,10 @@ public: template void addLazyObject(const LazyObject &New); Symbol *addBitcode(const Defined &New); - Symbol *addCommon(const Defined &New); + Symbol *addCommon(const CommonSymbol &New); - std::pair insert(const Symbol &New); + Symbol *insert(const Symbol &New); + void mergeProperties(Symbol *Old, const Symbol &New); template void fetchLazy(Symbol *Sym); diff --git a/lld/ELF/Symbols.cpp b/lld/ELF/Symbols.cpp index cabffc8..e1bbb8a 100644 --- a/lld/ELF/Symbols.cpp +++ b/lld/ELF/Symbols.cpp @@ -122,6 +122,8 @@ static uint64_t getSymVA(const Symbol &Sym, int64_t &Addend) { case Symbol::LazyObjectKind: assert(Sym.IsUsedInRegularObj && "lazy symbol reached writer"); return 0; + case Symbol::CommonKind: + llvm_unreachable("common symbol reached writer"); case Symbol::PlaceholderKind: llvm_unreachable("placeholder symbol reached writer"); } @@ -291,7 +293,7 @@ void elf::printTraceSymbol(Symbol *Sym) { S = ": lazy definition of "; else if (Sym->isShared()) S = ": shared definition of "; - else if (dyn_cast_or_null(cast(Sym)->Section)) + else if (Sym->isCommon()) S = ": common definition of "; else S = ": definition of "; diff --git a/lld/ELF/Symbols.h b/lld/ELF/Symbols.h index 0c71bdc..ce61a1e 100644 --- a/lld/ELF/Symbols.h +++ b/lld/ELF/Symbols.h @@ -51,6 +51,7 @@ public: enum Kind { PlaceholderKind, DefinedKind, + CommonKind, SharedKind, UndefinedKind, LazyArchiveKind, @@ -124,8 +125,11 @@ public: bool isWeak() const { return Binding == llvm::ELF::STB_WEAK; } bool isUndefined() const { return SymbolKind == UndefinedKind; } + bool isCommon() const { return SymbolKind == CommonKind; } bool isDefined() const { return SymbolKind == DefinedKind; } bool isShared() const { return SymbolKind == SharedKind; } + bool isPlaceholder() const { return SymbolKind == PlaceholderKind; } + bool isLocal() const { return Binding == llvm::ELF::STB_LOCAL; } bool isLazy() const { @@ -229,6 +233,40 @@ public: SectionBase *Section; }; +// Represents a common symbol. +// +// On Unix, it is traditionally allowed to write variable definitions +// without initialization expressions (such as "int foo;") to header +// files. Such definition is called "tentative definition". +// +// Using tentative definition is usually considered a bad practice +// because you should write only declarations (such as "extern int +// foo;") to header files. Nevertheless, the linker and the compiler +// have to do something to support bad code by allowing duplicate +// definitions for this particular case. +// +// Common symbols represent variable definitions without initializations. +// The compiler creates common symbols when it sees varaible definitions +// without initialization (you can suppress this behavior and let the +// compiler create a regular defined symbol by -fno-common). +// +// The linker allows common symbols to be replaced by regular defined +// symbols. If there are remaining common symbols after name resolution is +// complete, they are converted to regular defined symbols in a .bss +// section. (Therefore, the later passes don't see any CommonSymbols.) +class CommonSymbol : public Symbol { +public: + CommonSymbol(InputFile *File, StringRefZ Name, uint8_t Binding, + uint8_t StOther, uint8_t Type, uint64_t Alignment, uint64_t Size) + : Symbol(CommonKind, File, Name, Binding, StOther, Type), + Alignment(Alignment), Size(Size) {} + + static bool classof(const Symbol *S) { return S->isCommon(); } + + uint32_t Alignment; + uint64_t Size; +}; + class Undefined : public Symbol { public: Undefined(InputFile *File, StringRefZ Name, uint8_t Binding, uint8_t StOther, diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp index 8c97d6d..587e465 100644 --- a/lld/ELF/Writer.cpp +++ b/lld/ELF/Writer.cpp @@ -180,14 +180,17 @@ static Defined *addOptionalRegular(StringRef Name, SectionBase *Sec, if (!S || S->isDefined()) return nullptr; - return Symtab->addDefined(Defined{/*File=*/nullptr, Name, Binding, StOther, - STT_NOTYPE, Val, - /*Size=*/0, Sec}); + return cast(Symtab->addDefined( + Defined{/*File=*/nullptr, Name, Binding, StOther, STT_NOTYPE, Val, + /*Size=*/0, Sec})); } static Defined *addAbsolute(StringRef Name) { - return Symtab->addDefined(Defined{nullptr, Name, STB_GLOBAL, STV_HIDDEN, - STT_NOTYPE, 0, 0, nullptr}); + Defined New(nullptr, Name, STB_GLOBAL, STV_HIDDEN, STT_NOTYPE, 0, 0, nullptr); + Symbol *Sym = Symtab->addDefined(New); + if (!Sym->isDefined()) + error("duplicate symbol: " + toString(*Sym)); + return cast(Sym); } // The linker is expected to define some symbols depending on @@ -236,10 +239,10 @@ void elf::addReservedSymbols() { if (Config->EMachine == EM_PPC || Config->EMachine == EM_PPC64) GotOff = 0x8000; - ElfSym::GlobalOffsetTable = - Symtab->addDefined(Defined{/*File=*/nullptr, GotSymName, STB_GLOBAL, - STV_HIDDEN, STT_NOTYPE, GotOff, - /*Size=*/0, Out::ElfHeader}); + Symtab->addDefined(Defined{/*File=*/nullptr, GotSymName, STB_GLOBAL, + STV_HIDDEN, STT_NOTYPE, GotOff, /*Size=*/0, + Out::ElfHeader}); + ElfSym::GlobalOffsetTable = cast(S); } // __ehdr_start is the location of ELF file headers. Note that we define -- 2.7.4