diff --git a/lld/ELF/Driver.cpp b/lld/ELF/Driver.cpp --- a/lld/ELF/Driver.cpp +++ b/lld/ELF/Driver.cpp @@ -1319,6 +1319,23 @@ Symtab->fetchLazy(Sym); } +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 @@ -1677,6 +1694,9 @@ 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 --- a/lld/ELF/InputFiles.cpp +++ b/lld/ELF/InputFiles.cpp @@ -901,7 +901,7 @@ if (Value == 0 || Value >= UINT32_MAX) fatal(toString(this) + ": common symbol '" + Name + "' has invalid alignment: " + Twine(Value)); - Defined New(this, Name, Binding, StOther, Type, Value, Size, nullptr); + CommonSymbol New(this, Name, Binding, StOther, Type, Value, Size); return Symtab->addCommon(&New); } @@ -1275,8 +1275,8 @@ } if (ObjSym.isCommon()) { - Defined New(&F, Name, Binding, Visibility, STT_OBJECT, - ObjSym.getCommonAlignment(), ObjSym.getCommonSize(), nullptr); + CommonSymbol New(&F, Name, Binding, Visibility, STT_OBJECT, + ObjSym.getCommonAlignment(), ObjSym.getCommonSize()); return Symtab->addCommon(&New); } diff --git a/lld/ELF/LinkerScript.cpp b/lld/ELF/LinkerScript.cpp --- a/lld/ELF/LinkerScript.cpp +++ b/lld/ELF/LinkerScript.cpp @@ -186,8 +186,8 @@ 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 @@ 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.h b/lld/ELF/SymbolTable.h --- 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 @@ template Symbol *addUndefined(Undefined *New); - Defined *addDefined(Defined *New); + Symbol *addDefined(Defined *New); void addShared(SharedSymbol *New); @@ -54,9 +55,10 @@ template void addLazyObject(LazyObject *New); Symbol *addBitcode(Defined *New); - Symbol *addCommon(Defined *New); + Symbol *addCommon(CommonSymbol *New); - std::pair insert(Symbol *New); + Symbol *insert(Symbol *New); + void mergeProperties(Symbol *Old, Symbol *New); template void fetchLazy(Symbol *Sym); diff --git a/lld/ELF/SymbolTable.cpp b/lld/ELF/SymbolTable.cpp --- a/lld/ELF/SymbolTable.cpp +++ b/lld/ELF/SymbolTable.cpp @@ -88,7 +88,7 @@ // Find an existing symbol or create and insert a new one, then apply the given // attributes. -std::pair SymbolTable::insert(Symbol *New) { +Symbol *SymbolTable::insert(Symbol *New) { // Find an existing symbol or create and insert a new one. // @@ means the symbol is the default version. In that @@ -130,6 +130,11 @@ Old = SymVector[SymIndex]; } + return Old; +} + +// +void SymbolTable::mergeProperties(Symbol *Old, Symbol *New) { // Merge symbol properties. Old->ExportDynamic = Old->ExportDynamic || New->ExportDynamic; Old->IsUsedInRegularObj = Old->IsUsedInRegularObj || New->IsUsedInRegularObj; @@ -137,19 +142,20 @@ // DSO symbols do not affect visibility in the output. if (!isa(New)) Old->Visibility = getMinVisibility(Old->Visibility, New->Visibility); - - return {Old, IsNew}; } template Symbol *SymbolTable::addUndefined(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 (isa(Old) && New->Visibility != STV_DEFAULT) { replaceSymbol(Old, New); return Old; } @@ -245,94 +251,80 @@ 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(Symbol *Old, 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(Symbol *Old, 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(Symbol *OldSym, 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 == nullptr && NewSym->Section == nullptr && + OldSym->Value == NewSym->Value && NewSym->Binding == STB_GLOBAL) + return -1; + return 0; } -Symbol *SymbolTable::addCommon(Defined *New) { - Symbol *Old; - bool WasInserted; - std::tie(Old, WasInserted) = insert(New); +Symbol *SymbolTable::addCommon(CommonSymbol *New) { + Symbol *Old = insert(New); + mergeProperties(Old, New); - auto Replace = [&] { - auto *Bss = make("COMMON", New->Size, New->Value); - Bss->File = New->File; - Bss->Live = !Config->GcSections; - InputSections.push_back(Bss); - - New->Value = 0; - New->Section = Bss; + if (Old->isPlaceholder()) { replaceSymbol(Old, New); - }; - - if (WasInserted) { - Replace(); 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()); + auto *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, @@ -370,39 +362,40 @@ error(Msg); } -Defined *SymbolTable::addDefined(Defined *New) { - Symbol *Old; - bool WasInserted; - std::tie(Old, WasInserted) = insert(New); +Symbol *SymbolTable::addDefined(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(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 +405,15 @@ } Symbol *SymbolTable::addBitcode(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 +431,10 @@ } template void SymbolTable::addLazy(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; } diff --git a/lld/ELF/Symbols.h b/lld/ELF/Symbols.h --- a/lld/ELF/Symbols.h +++ b/lld/ELF/Symbols.h @@ -51,6 +51,7 @@ enum Kind { PlaceholderKind, DefinedKind, + CommonKind, SharedKind, UndefinedKind, LazyArchiveKind, @@ -124,8 +125,11 @@ 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,37 @@ 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. This is a bad practice because you should write only +// delcarations (such as "extern int foo;") to header files. Neverthless, +// linker and the compiler have to do something to support bad code by +// allowing duplicate definitions for this particular case. +// +// Common symbols represent varaible 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/Symbols.cpp b/lld/ELF/Symbols.cpp --- a/lld/ELF/Symbols.cpp +++ b/lld/ELF/Symbols.cpp @@ -122,6 +122,8 @@ 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"); } @@ -287,7 +289,7 @@ 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/Writer.cpp b/lld/ELF/Writer.cpp --- a/lld/ELF/Writer.cpp +++ b/lld/ELF/Writer.cpp @@ -182,12 +182,15 @@ Defined New(/*File=*/nullptr, Name, Binding, StOther, STT_NOTYPE, Val, /*Size=*/0, Sec); - return Symtab->addDefined(&New); + return cast(Symtab->addDefined(&New)); } static Defined *addAbsolute(StringRef Name) { Defined New(nullptr, Name, STB_GLOBAL, STV_HIDDEN, STT_NOTYPE, 0, 0, nullptr); - return Symtab->addDefined(&New); + 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 @@ -237,9 +240,9 @@ GotOff = 0x8000; Defined New(/*File=*/nullptr, GotSymName, STB_GLOBAL, STV_HIDDEN, - STT_NOTYPE, GotOff, - /*Size=*/0, Out::ElfHeader); - ElfSym::GlobalOffsetTable = Symtab->addDefined(&New); + STT_NOTYPE, GotOff, /*Size=*/0, Out::ElfHeader); + Symtab->addDefined(&New); + ElfSym::GlobalOffsetTable = cast(S); } // __ehdr_start is the location of ELF file headers. Note that we define