Index: lld/ELF/Config.h =================================================================== --- lld/ELF/Config.h +++ lld/ELF/Config.h @@ -37,6 +37,9 @@ // For --build-id. enum class BuildIdKind { None, Fast, Md5, Sha1, Hexstring, Uuid }; +// For --pack-dyn-relocs. +enum class PackDynRelocsFormat { None, Android }; + // For --discard-{all,locals,none}. enum class DiscardPolicy { Default, All, Locals, None }; @@ -163,6 +166,7 @@ Target2Policy Target2; BuildIdKind BuildId = BuildIdKind::None; ELFKind EKind = ELFNoneKind; + PackDynRelocsFormat PackDynRelocs = PackDynRelocsFormat::None; uint16_t DefaultSymbolVersion = llvm::ELF::VER_NDX_GLOBAL; uint16_t EMachine = llvm::ELF::EM_NONE; uint64_t ErrorLimit = 20; Index: lld/ELF/Driver.cpp =================================================================== --- lld/ELF/Driver.cpp +++ lld/ELF/Driver.cpp @@ -764,6 +764,16 @@ std::tie(Config->BuildId, Config->BuildIdVector) = getBuildId(Args); + if (auto *Arg = Args.getLastArg(OPT_pack_dyn_relocs_eq)) { + StringRef S = Arg->getValue(); + if (S == "none") + Config->PackDynRelocs = PackDynRelocsFormat::None; + else if (S == "android") + Config->PackDynRelocs = PackDynRelocsFormat::Android; + else + error("unknown -pack-dyn-relocs format: " + S); + } + if (auto *Arg = Args.getLastArg(OPT_symbol_ordering_file)) if (Optional Buffer = readFile(Arg->getValue())) Config->SymbolOrderingFile = getLines(*Buffer); Index: lld/ELF/Options.td =================================================================== --- lld/ELF/Options.td +++ lld/ELF/Options.td @@ -220,6 +220,9 @@ def omagic: Flag<["--"], "omagic">, MetaVarName<"">, HelpText<"Set the text and data sections to be readable and writable">; +def pack_dyn_relocs_eq: J<"pack-dyn-relocs=">, MetaVarName<"">, + HelpText<"Pack dynamic relocations in the given format (none or android)">; + def pie: F<"pie">, HelpText<"Create a position independent executable">; def print_gc_sections: F<"print-gc-sections">, Index: lld/ELF/SyntheticSections.h =================================================================== --- lld/ELF/SyntheticSections.h +++ lld/ELF/SyntheticSections.h @@ -45,7 +45,7 @@ virtual void finalizeContents() {} // If the section has the SHF_ALLOC flag and the size may be changed if // thunks are added, update the section size. - virtual void updateAllocSize() {} + virtual bool updateAllocSize() { return false; } // If any additional finalization of contents are needed post thunk creation. virtual void postThunkContents() {} virtual bool empty() const { return false; } @@ -166,7 +166,7 @@ MipsGotSection(); void writeTo(uint8_t *Buf) override; size_t getSize() const override { return Size; } - void updateAllocSize() override; + bool updateAllocSize() override; void finalizeContents() override; bool empty() const override; void addEntry(SymbolBody &Sym, int64_t Addend, RelExpr Expr); @@ -371,24 +371,52 @@ uint64_t Size = 0; }; -template class RelocationSection final : public SyntheticSection { +class RelocationBaseSection : public SyntheticSection { +public: + RelocationBaseSection(StringRef Name, uint32_t Type, int32_t DynamicTag, + int32_t SizeDynamicTag); + void addReloc(const DynamicReloc &Reloc); + bool empty() const override { return Relocs.empty(); } + size_t getSize() const override { return Relocs.size() * this->Entsize; } + size_t getRelativeRelocCount() const { return NumRelativeRelocs; } + int32_t DynamicTag, SizeDynamicTag; + +protected: + std::vector Relocs; + size_t NumRelativeRelocs = 0; +}; + +template +class RelocationSection final : public RelocationBaseSection { typedef typename ELFT::Rel Elf_Rel; typedef typename ELFT::Rela Elf_Rela; public: RelocationSection(StringRef Name, bool Sort); - void addReloc(const DynamicReloc &Reloc); unsigned getRelocOffset(); void finalizeContents() override; void writeTo(uint8_t *Buf) override; - bool empty() const override { return Relocs.empty(); } - size_t getSize() const override { return Relocs.size() * this->Entsize; } - size_t getRelativeRelocCount() const { return NumRelativeRelocs; } private: bool Sort; - size_t NumRelativeRelocs = 0; - std::vector Relocs; +}; + +template +class AndroidPackedRelocationSection final : public RelocationBaseSection { + typedef typename ELFT::Rel Elf_Rel; + typedef typename ELFT::Rela Elf_Rela; + +public: + AndroidPackedRelocationSection(StringRef Name); + + bool updateAllocSize() override; + size_t getSize() const override { return RelocData.size(); } + void writeTo(uint8_t *Buf) override { + std::copy(RelocData.begin(), RelocData.end(), Buf); + } + +private: + SmallVector RelocData; }; struct SymbolTableEntry { @@ -838,7 +866,7 @@ template struct In : public InX { static EhFrameHeader *EhFrameHdr; static EhFrameSection *EhFrame; - static RelocationSection *RelaDyn; + static RelocationBaseSection *RelaDyn; static RelocationSection *RelaPlt; static RelocationSection *RelaIplt; static VersionDefinitionSection *VerDef; @@ -848,7 +876,7 @@ template EhFrameHeader *In::EhFrameHdr; template EhFrameSection *In::EhFrame; -template RelocationSection *In::RelaDyn; +template RelocationBaseSection *In::RelaDyn; template RelocationSection *In::RelaPlt; template RelocationSection *In::RelaIplt; template VersionDefinitionSection *In::VerDef; Index: lld/ELF/SyntheticSections.cpp =================================================================== --- lld/ELF/SyntheticSections.cpp +++ lld/ELF/SyntheticSections.cpp @@ -32,6 +32,7 @@ #include "llvm/Object/Decompressor.h" #include "llvm/Object/ELFObjectFile.h" #include "llvm/Support/Endian.h" +#include "llvm/Support/LEB128.h" #include "llvm/Support/MD5.h" #include "llvm/Support/RandomNumberGenerator.h" #include "llvm/Support/SHA1.h" @@ -828,7 +829,7 @@ void MipsGotSection::finalizeContents() { updateAllocSize(); } -void MipsGotSection::updateAllocSize() { +bool MipsGotSection::updateAllocSize() { PageEntriesNum = 0; for (std::pair &P : PageIndexMap) { // For each output section referenced by GOT page relocations calculate @@ -842,6 +843,7 @@ } Size = (getLocalEntriesNum() + GlobalEntries.size() + TlsEntries.size()) * Config->Wordsize; + return false; } bool MipsGotSection::empty() const { @@ -1087,10 +1089,11 @@ this->Link = InX::DynStrTab->getParent()->SectionIndex; if (In::RelaDyn->getParent() && !In::RelaDyn->empty()) { - bool IsRela = Config->IsRela; - add({IsRela ? DT_RELA : DT_REL, In::RelaDyn}); - add({IsRela ? DT_RELASZ : DT_RELSZ, In::RelaDyn->getParent(), + add({In::RelaDyn->DynamicTag, In::RelaDyn}); + add({In::RelaDyn->SizeDynamicTag, In::RelaDyn->getParent(), Entry::SecSize}); + + bool IsRela = Config->IsRela; add({IsRela ? DT_RELAENT : DT_RELENT, uint64_t(IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel))}); @@ -1226,21 +1229,47 @@ return 0; } -template -RelocationSection::RelocationSection(StringRef Name, bool Sort) - : SyntheticSection(SHF_ALLOC, Config->IsRela ? SHT_RELA : SHT_REL, - Config->Wordsize, Name), - Sort(Sort) { - this->Entsize = Config->IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel); -} +RelocationBaseSection::RelocationBaseSection(StringRef Name, uint32_t Type, + int32_t DynamicTag, + int32_t SizeDynamicTag) + : SyntheticSection(SHF_ALLOC, Type, Config->Wordsize, Name), + DynamicTag(DynamicTag), SizeDynamicTag(SizeDynamicTag) {} -template -void RelocationSection::addReloc(const DynamicReloc &Reloc) { +void RelocationBaseSection::addReloc(const DynamicReloc &Reloc) { if (Reloc.Type == Target->RelativeRel) ++NumRelativeRelocs; Relocs.push_back(Reloc); } +template +static void encodeDynamicReloc(typename ELFT::Rela *P, + const DynamicReloc &Rel) { + if (Config->IsRela) + P->r_addend = Rel.getAddend(); + P->r_offset = Rel.getOffset(); + if (Config->EMachine == EM_MIPS && Rel.getInputSec() == InX::MipsGot) + // The MIPS GOT section contains dynamic relocations that correspond to TLS + // entries. These entries are placed after the global and local sections of + // the GOT. At the point when we create these relocations, the size of the + // global and local sections is unknown, so the offset that we store in the + // TLS entry's DynamicReloc is relative to the start of the TLS section of + // the GOT, rather than being relative to the start of the GOT. This line of + // code adds the size of the global and local sections to the virtual + // address computed by getOffset() in order to adjust it into the TLS + // section. + P->r_offset += InX::MipsGot->getTlsOffset(); + P->setSymbolAndType(Rel.getSymIndex(), Rel.Type, Config->IsMips64EL); +} + +template +RelocationSection::RelocationSection(StringRef Name, bool Sort) + : RelocationBaseSection(Name, Config->IsRela ? SHT_RELA : SHT_REL, + Config->IsRela ? DT_RELA : DT_REL, + Config->IsRela ? DT_RELASZ : DT_RELSZ), + Sort(Sort) { + this->Entsize = Config->IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel); +} + template static bool compRelocations(const RelTy &A, const RelTy &B) { bool AIsRel = A.getType(Config->IsMips64EL) == Target->RelativeRel; @@ -1254,18 +1283,8 @@ template void RelocationSection::writeTo(uint8_t *Buf) { uint8_t *BufBegin = Buf; for (const DynamicReloc &Rel : Relocs) { - auto *P = reinterpret_cast(Buf); + encodeDynamicReloc(reinterpret_cast(Buf), Rel); Buf += Config->IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel); - - if (Config->IsRela) - P->r_addend = Rel.getAddend(); - P->r_offset = Rel.getOffset(); - if (Config->EMachine == EM_MIPS && Rel.getInputSec() == InX::MipsGot) - // Dynamic relocation against MIPS GOT section make deal TLS entries - // allocated in the end of the GOT. We need to adjust the offset to take - // in account 'local' and 'global' GOT entries. - P->r_offset += InX::MipsGot->getTlsOffset(); - P->setSymbolAndType(Rel.getSymIndex(), Rel.Type, Config->IsMips64EL); } if (Sort) { @@ -1291,6 +1310,168 @@ getParent()->Link = this->Link; } +template +AndroidPackedRelocationSection::AndroidPackedRelocationSection( + StringRef Name) + : RelocationBaseSection( + Name, Config->IsRela ? SHT_ANDROID_RELA : SHT_ANDROID_REL, + Config->IsRela ? DT_ANDROID_RELA : DT_ANDROID_REL, + Config->IsRela ? DT_ANDROID_RELASZ : DT_ANDROID_RELSZ) { + this->Entsize = 1; +} + +template +bool AndroidPackedRelocationSection::updateAllocSize() { + // This function computes the contents of an Android-format packed relocation + // section. + // + // A relocation section consists of a header containing the literal bytes + // 'APS2' followed by a sequence of SLEB128-encoded integers. The first two + // elements are the total number of relocations in the section and an initial + // r_offset value. The remaining elements define a sequence of relocation + // groups. Each relocation group starts with a header consisting of the + // following elements: + // + // - the number of relocations in the relocation group + // - flags for the relocation group: + enum { + RELOCATION_GROUPED_BY_INFO_FLAG = 1, + RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG = 2, + RELOCATION_GROUPED_BY_ADDEND_FLAG = 4, + RELOCATION_GROUP_HAS_ADDEND_FLAG = 8, + }; + // - (if RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG is set) the r_offset delta + // for each relocation in the group. + // - (if RELOCATION_GROUPED_BY_INFO_FLAG is set) the value of the r_info + // field for each relocation in the group. + // - (if RELOCATION_GROUP_HAS_ADDEND_FLAG and + // RELOCATION_GROUPED_BY_ADDEND_FLAG are set) the r_addend delta for + // each relocation in the group. + // + // Following the relocation group header are descriptions of each of the + // relocations in the group. They consist of the following elements: + // + // - (if RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG is not set) the r_offset + // delta for this relocation. + // - (if RELOCATION_GROUPED_BY_INFO_FLAG is not set) the value of the r_info + // field for this relocation. + // - (if RELOCATION_GROUP_HAS_ADDEND_FLAG is set and + // RELOCATION_GROUPED_BY_ADDEND_FLAG is not set) the r_addend delta for + // this relocation. + + size_t OldSize = RelocData.size(); + + RelocData.clear(); + RelocData.push_back('A'); + RelocData.push_back('P'); + RelocData.push_back('S'); + RelocData.push_back('2'); + raw_svector_ostream OS(RelocData); + + if (Config->IsRela) { + assert(0); + } else { + std::vector Relatives; + std::vector NonRelatives; + + for (const DynamicReloc &Rel : Relocs) { + Elf_Rela R; + encodeDynamicReloc(&R, Rel); + + if (R.getType(Config->IsMips64EL) == Target->RelativeRel) + Relatives.push_back(R.r_offset); + else + NonRelatives.push_back(R); + } + + std::sort(Relatives.begin(), Relatives.end()); + + // Try to find groups of relative relocations which are spaced one word + // apart from one another. These generally correspond to vtable entries. The + // format allows these groups to be encoded using a sort of run-length + // encoding, but each group will cost 7 bytes in addition to the offset from + // the previous group, so it is only profitable to do this for groups of + // size 8 or larger. + std::vector UngroupedRelatives; + std::vector> RelativeGroups; + for (auto I = Relatives.begin(), E = Relatives.end(); I != E;) { + size_t GroupStart = *I++; + size_t GroupSize = 1; + while (I != E && *(I - 1) + Config->Wordsize == *I) { + ++I; + ++GroupSize; + } + + if (GroupSize < 8) { + for (unsigned J = 0; J != GroupSize; ++J) + UngroupedRelatives.push_back(GroupStart + J * Config->Wordsize); + } else { + RelativeGroups.push_back({GroupStart, GroupSize}); + } + } + + // The format header includes the number of relocations and the initial + // offset (we set this to zero because the first relocation group will + // perform the initial adjustment). + encodeSLEB128(Relocs.size(), OS); + encodeSLEB128(0, OS); + + uint64_t Offset = 0; + // Emit the run-length encoding for the groups of adjacent relative + // relocations. Each group is represented using two groups in the packed + // format. The first is used to set the current offset to the start of the + // group (and also encodes the first relocation), and the second encodes the + // remaining relocations. + for (auto &P : RelativeGroups) { + // The first relocation in the group. + encodeSLEB128(1, OS); + encodeSLEB128(RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG | + RELOCATION_GROUPED_BY_INFO_FLAG, + OS); + encodeSLEB128(P.first - Offset, OS); + encodeSLEB128(Target->RelativeRel, OS); + + // The remaining relocations. + encodeSLEB128(P.second - 1, OS); + encodeSLEB128(RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG | + RELOCATION_GROUPED_BY_INFO_FLAG, + OS); + encodeSLEB128(Config->Wordsize, OS); + encodeSLEB128(Target->RelativeRel, OS); + + Offset = P.first + (P.second - 1) * Config->Wordsize; + } + + // Now the ungrouped relatives. + if (!UngroupedRelatives.empty()) { + encodeSLEB128(UngroupedRelatives.size(), OS); + encodeSLEB128(RELOCATION_GROUPED_BY_INFO_FLAG, OS); + encodeSLEB128(Target->RelativeRel, OS); + for (uint64_t R : UngroupedRelatives) { + encodeSLEB128(R - Offset, OS); + Offset = R; + } + } + + // Finally the non-relative relocations. + std::sort(NonRelatives.begin(), NonRelatives.end(), + [](const Elf_Rel &A, const Elf_Rel &B) { + return A.r_offset < B.r_offset; + }); + if (!NonRelatives.empty()) { + encodeSLEB128(NonRelatives.size(), OS); + encodeSLEB128(0, OS); + for (Elf_Rel &R : NonRelatives) { + encodeSLEB128(R.r_offset - Offset, OS); + Offset = R.r_offset; + encodeSLEB128(R.r_info, OS); + } + } + } + + return RelocData.size() != OldSize; +} + SymbolTableBaseSection::SymbolTableBaseSection(StringTableSection &StrTabSec) : SyntheticSection(StrTabSec.isDynamic() ? (uint64_t)SHF_ALLOC : 0, StrTabSec.isDynamic() ? SHT_DYNSYM : SHT_SYMTAB, @@ -2485,6 +2666,11 @@ template class elf::RelocationSection; template class elf::RelocationSection; +template class elf::AndroidPackedRelocationSection; +template class elf::AndroidPackedRelocationSection; +template class elf::AndroidPackedRelocationSection; +template class elf::AndroidPackedRelocationSection; + template class elf::SymbolTableSection; template class elf::SymbolTableSection; template class elf::SymbolTableSection; Index: lld/ELF/Writer.cpp =================================================================== --- lld/ELF/Writer.cpp +++ lld/ELF/Writer.cpp @@ -258,8 +258,16 @@ InX::DynStrTab = make(".dynstr", true); InX::Dynamic = make>(); - In::RelaDyn = make>( - Config->IsRela ? ".rela.dyn" : ".rel.dyn", Config->ZCombreloc); + switch (Config->PackDynRelocs) { + case PackDynRelocsFormat::None: + In::RelaDyn = make>( + Config->IsRela ? ".rela.dyn" : ".rel.dyn", Config->ZCombreloc); + break; + case PackDynRelocsFormat::Android: + In::RelaDyn = make>( + Config->IsRela ? ".rela.dyn" : ".rel.dyn"); + break; + } InX::ShStrTab = make(".shstrtab", false); Out::ElfHeader = make("", 0, SHF_ALLOC); @@ -362,7 +370,10 @@ // The RelaIplt immediately follows .rel.plt (.rel.dyn for ARM) to ensure // that the IRelative relocations are processed last by the dynamic loader In::RelaIplt = make>( - (Config->EMachine == EM_ARM) ? ".rel.dyn" : In::RelaPlt->Name, + (Config->EMachine == EM_ARM && + Config->PackDynRelocs == PackDynRelocsFormat::None) + ? ".rel.dyn" + : In::RelaPlt->Name, false /*Sort*/); Add(In::RelaIplt); @@ -1362,14 +1373,19 @@ // Some architectures use small displacements for jump instructions. // It is linker's responsibility to create thunks containing long // jump instructions if jump targets are too far. Create thunks. - if (Target->NeedsThunks) { + if (Target->NeedsThunks || + Config->PackDynRelocs == PackDynRelocsFormat::Android) { ThunkCreator TC; - Script->assignAddresses(); - while (TC.createThunks(OutputSections)) { - applySynthetic({InX::MipsGot}, - [](SyntheticSection *SS) { SS->updateAllocSize(); }); + bool Changed; + do { Script->assignAddresses(); - } + Changed = false; + if (Target->NeedsThunks) + Changed |= TC.createThunks(OutputSections); + if (InX::MipsGot) + InX::MipsGot->updateAllocSize(); + Changed |= In::RelaDyn->updateAllocSize(); + } while (Changed); } // Fill other section headers. The dynamic table is finalized Index: llvm/include/llvm/BinaryFormat/ELF.h =================================================================== --- llvm/include/llvm/BinaryFormat/ELF.h +++ llvm/include/llvm/BinaryFormat/ELF.h @@ -730,6 +730,10 @@ SHT_GROUP = 17, // Section group. SHT_SYMTAB_SHNDX = 18, // Indices for SHN_XINDEX entries. SHT_LOOS = 0x60000000, // Lowest operating system-specific type. + // Android packed relocation section types. + // https://android.googlesource.com/platform/bionic/+/6f12bfece5dcc01325e0abba56a46b1bcf991c69/tools/relocation_packer/src/elf_file.cc#37 + SHT_ANDROID_REL = 0x60000001, + SHT_ANDROID_RELA = 0x60000002, SHT_LLVM_ODRTAB = 0x6fff4c00, // LLVM ODR table. SHT_GNU_ATTRIBUTES = 0x6ffffff5, // Object attributes. SHT_GNU_HASH = 0x6ffffff6, // GNU-style hash table. @@ -1166,6 +1170,13 @@ DT_LOPROC = 0x70000000, // Start of processor specific tags. DT_HIPROC = 0x7FFFFFFF, // End of processor specific tags. + // Android packed relocation section tags. + // https://android.googlesource.com/platform/bionic/+/6f12bfece5dcc01325e0abba56a46b1bcf991c69/tools/relocation_packer/src/elf_file.cc#31 + DT_ANDROID_REL = 0x6000000F, + DT_ANDROID_RELSZ = 0x60000010, + DT_ANDROID_RELA = 0x60000011, + DT_ANDROID_RELASZ = 0x60000012, + DT_GNU_HASH = 0x6FFFFEF5, // Reference to the GNU hash table. DT_TLSDESC_PLT = 0x6FFFFEF6, // Location of PLT entry for TLS descriptor resolver calls.