Index: COFF/Chunks.h =================================================================== --- COFF/Chunks.h +++ COFF/Chunks.h @@ -64,6 +64,13 @@ // before calling this function. virtual void writeTo(uint8_t *Buf) const {} + // Called by the writer once before assigning addresses and writing + // the output. + virtual void readRelocTargets() {} + + // Called if restarting thunk addition. + virtual void resetRelocTargets() {} + // Called by the writer after an RVA is assigned, but before calling // getSize(). virtual void finalizeContents() {} @@ -145,6 +152,8 @@ SectionChunk(ObjFile *File, const coff_section *Header); static bool classof(const Chunk *C) { return C->kind() == SectionKind; } + void readRelocTargets() override; + void resetRelocTargets() override; size_t getSize() const override { return Header->SizeOfRawData; } ArrayRef getContents() const; void writeTo(uint8_t *Buf) const override; @@ -217,6 +226,10 @@ // Used by the garbage collector. bool Live; + // When inserting a thunk, we need to adjust a relocation to point to + // the thunk instead of the actual original target Symbol. + std::vector RelocTargets; + private: StringRef SectionName; std::vector AssocChildren; @@ -251,6 +264,7 @@ private: llvm::StringTableBuilder Builder; + bool Finalized = false; }; // A chunk for common symbols. Common chunks don't have actual data. @@ -338,6 +352,15 @@ Defined *ImpSymbol; }; +class RangeExtensionThunk : public Chunk { +public: + explicit RangeExtensionThunk(Defined *T) : Target(T) {} + size_t getSize() const override; + void writeTo(uint8_t *Buf) const override; + + Defined *Target; +}; + // Windows-specific. // See comments for DefinedLocalImport class. class LocalImportChunk : public Chunk { Index: COFF/Chunks.cpp =================================================================== --- COFF/Chunks.cpp +++ COFF/Chunks.cpp @@ -44,6 +44,22 @@ Live = !Config->DoGC || !isCOMDAT(); } +// Initialize the RelocTargets vector, to allow redirecting certain relocations +// to a thunk instead of the actual symbol the relocation's symbol table index +// indicates. +void SectionChunk::readRelocTargets() { + assert(RelocTargets.empty()); + RelocTargets.reserve(Relocs.size()); + for (const coff_relocation &Rel : Relocs) + RelocTargets.push_back(File->getSymbol(Rel.SymbolTableIndex)); +} + +// Reset RelocTargets to their original targets before thunks were added. +void SectionChunk::resetRelocTargets() { + for (size_t I = 0, E = Relocs.size(); I < E; ++I) + RelocTargets[I] = File->getSymbol(Relocs[I].SymbolTableIndex); +} + static void add16(uint8_t *P, int16_t V) { write16le(P, read16le(P) + V); } static void add32(uint8_t *P, int32_t V) { write32le(P, read32le(P) + V); } static void add64(uint8_t *P, int64_t V) { write64le(P, read64le(P) + V); } @@ -309,7 +325,9 @@ // Apply relocations. size_t InputSize = getSize(); - for (const coff_relocation &Rel : Relocs) { + for (size_t I = 0, E = Relocs.size(); I < E; I++) { + const coff_relocation &Rel = Relocs[I]; + // Check for an invalid relocation offset. This check isn't perfect, because // we don't have the relocation size, which is only known after checking the // machine and relocation type. As a result, a relocation may overwrite the @@ -321,8 +339,9 @@ uint8_t *Off = Buf + OutputSectionOff + Rel.VirtualAddress; - auto *Sym = - dyn_cast_or_null(File->getSymbol(Rel.SymbolTableIndex)); + // Use the potentially remapped Symbol instead of the one that the + // relocation points to. + auto *Sym = dyn_cast_or_null(RelocTargets[I]); if (!Sym) { if (isCodeView() || isDWARF()) continue; @@ -410,11 +429,14 @@ // fixed by the loader if load-time relocation is needed. // Only called when base relocation is enabled. void SectionChunk::getBaserels(std::vector *Res) { - for (const coff_relocation &Rel : Relocs) { + for (size_t I = 0, E = Relocs.size(); I < E; I++) { + const coff_relocation &Rel = Relocs[I]; uint8_t Ty = getBaserelType(Rel); if (Ty == IMAGE_REL_BASED_ABSOLUTE) continue; - Symbol *Target = File->getSymbol(Rel.SymbolTableIndex); + // Use the potentially remapped Symbol instead of the one that the + // relocation points to. + Symbol *Target = RelocTargets[I]; if (!Target || isa(Target)) continue; Res->emplace_back(RVA + Rel.VirtualAddress, Ty); @@ -618,6 +640,25 @@ applyArm64Ldr(Buf + OutputSectionOff + 4, Off); } +// A Thumb2, PIC, non-interworking range extension thunk. +const uint8_t ArmThunk[] = { + 0x40, 0xf2, 0x00, 0x0c, // P: movw ip,:lower16:S - (P + (L1-P) + 4) + 0xc0, 0xf2, 0x00, 0x0c, // movt ip,:upper16:S - (P + (L1-P) + 4) + 0xe7, 0x44, // L1: add pc, ip +}; + +size_t RangeExtensionThunk::getSize() const { + assert(Config->Machine == ARMNT); + return sizeof(ArmThunk); +} + +void RangeExtensionThunk::writeTo(uint8_t *Buf) const { + assert(Config->Machine == ARMNT); + uint64_t Offset = Target->getRVA() - RVA - 12; + memcpy(Buf + OutputSectionOff, ArmThunk, sizeof(ArmThunk)); + applyMOV32T(Buf + OutputSectionOff, uint32_t(Offset)); +} + void LocalImportChunk::getBaserels(std::vector *Res) { Res->emplace_back(getRVA()); } @@ -757,10 +798,13 @@ } void MergeChunk::finalizeContents() { - for (SectionChunk *C : Sections) - if (C->Live) - Builder.add(toStringRef(C->getContents())); - Builder.finalize(); + if (!Finalized) { + for (SectionChunk *C : Sections) + if (C->Live) + Builder.add(toStringRef(C->getContents())); + Builder.finalize(); + Finalized = true; + } for (SectionChunk *C : Sections) { if (!C->Live) Index: COFF/MapFile.cpp =================================================================== --- COFF/MapFile.cpp +++ COFF/MapFile.cpp @@ -110,7 +110,7 @@ writeHeader(OS, Sec->getRVA(), Sec->getVirtualSize(), /*Align=*/PageSize); OS << Sec->Name << '\n'; - for (Chunk *C : Sec->getChunks()) { + for (Chunk *C : Sec->Chunks) { auto *SC = dyn_cast(C); if (!SC) continue; Index: COFF/PDB.cpp =================================================================== --- COFF/PDB.cpp +++ COFF/PDB.cpp @@ -839,6 +839,7 @@ uint8_t *Buffer = Alloc.Allocate(DebugChunk.getSize()); assert(DebugChunk.OutputSectionOff == 0 && "debug sections should not be in output sections"); + DebugChunk.readRelocTargets(); DebugChunk.writeTo(Buffer); return makeArrayRef(Buffer, DebugChunk.getSize()); } @@ -1286,7 +1287,7 @@ // Add section contributions. They must be ordered by ascending RVA. for (OutputSection *OS : OutputSections) { addLinkerModuleSectionSymbol(LinkerModule, *OS, Alloc); - for (Chunk *C : OS->getChunks()) { + for (Chunk *C : OS->Chunks) { pdb::SectionContrib SC = createSectionContrib(C, LinkerModule.getModuleIndex()); Builder.getDbiBuilder().addSectionContrib(SC); Index: COFF/Writer.h =================================================================== --- COFF/Writer.h +++ COFF/Writer.h @@ -36,12 +36,12 @@ void addChunk(Chunk *C); void insertChunkAtStart(Chunk *C); void merge(OutputSection *Other); - ArrayRef getChunks() { return Chunks; } void addPermissions(uint32_t C); void setPermissions(uint32_t C); uint64_t getRVA() { return Header.VirtualAddress; } uint64_t getFileOff() { return Header.PointerToRawData; } void writeHeaderTo(uint8_t *Buf); + bool createThunks(int Margin); // Returns the size of this section in an executable memory image. // This may be smaller than the raw size (the raw size is multiple @@ -63,9 +63,11 @@ llvm::StringRef Name; llvm::object::coff_section Header = {}; + std::vector Chunks; + std::vector OrigChunks; + private: uint32_t StringTableOff = 0; - std::vector Chunks; }; } Index: COFF/Writer.cpp =================================================================== --- COFF/Writer.cpp +++ COFF/Writer.cpp @@ -169,7 +169,9 @@ void createImportTables(); void createExportTable(); void mergeSections(); + void readRelocTargets(); void assignAddresses(); + void finalizeAddresses(); void removeEmptySections(); void createSymbolAndStringTable(); void openFile(StringRef OutputPath); @@ -354,6 +356,185 @@ return None; } +static bool machineRequiresThunks() { + // Only ARMNT requires range extension thunks out of the currently supported + // architectures. + return Config->Machine == ARMNT; +} + +// Check whether the target address S is in range from a relocation +// of type RelType at address P. +static bool isInRange(uint16_t RelType, uint64_t S, uint64_t P, int Margin) { + assert(Config->Machine == ARMNT); + int64_t Diff = S - P - 4; + Diff = abs(Diff); + Diff += Margin; + switch (RelType) { + case IMAGE_REL_ARM_BRANCH20T: + return isInt<21>(Diff); + case IMAGE_REL_ARM_BRANCH24T: + case IMAGE_REL_ARM_BLX23T: + return isInt<25>(Diff); + default: + return true; + } +} + +// Return an existing thunk which is in range, or create a new one. +static std::pair +getThunk(DenseMap &LastThunks, Defined *Target, uint64_t P, + uint16_t Type, int Margin) { + Defined *&LastThunk = LastThunks[Target->getRVA()]; + if (LastThunk && isInRange(Type, LastThunk->getRVA(), P, Margin)) + return {LastThunk, false}; + RangeExtensionThunk *C = make(Target); + Defined *D = make("", C); + LastThunk = D; + return {D, true}; +} + +bool OutputSection::createThunks(int Margin) { + bool AddressesChanged = false; + DenseMap LastThunks; + size_t ThunksSize = 0; + // Recheck Chunks.size() each iteration, since we can insert more + // elements into it. + for (size_t I = 0; I != Chunks.size(); ++I) { + SectionChunk *SC = dyn_cast_or_null(Chunks[I]); + if (!SC) + continue; + size_t ThunkInsertionSpot = I + 1; + + // Try to get a good enough estimate of where new thunks will be placed. + // Offset this by the size of the new thunks added so far, to make the + // estimate slightly better. + size_t ThunkInsertionRVA = SC->getRVA() + SC->getSize() + ThunksSize; + for (size_t J = 0, E = SC->Relocs.size(); J < E; ++J) { + const coff_relocation &Rel = SC->Relocs[J]; + Symbol *&RelocTarget = SC->RelocTargets[J]; + + // The estimate of the source address P should be pretty accurate, + // but we don't know whether the target Symbol address should be + // offset by ThunkSize or not (or by some of ThunksSize but not all of + // it), giving us some uncertainty once we have added one thunk. + uint64_t P = SC->getRVA() + Rel.VirtualAddress + ThunksSize; + + Defined *Sym = dyn_cast_or_null(RelocTarget); + if (!Sym) + continue; + + uint64_t S = Sym->getRVA(); + + // For the first pass, create thunks for anything that almost is + // out of range, since other new thunks may make it easily go out + // of range. For later passes, accept anything which strictly is in + // range. + if (isInRange(Rel.Type, S, P, Margin)) + continue; + + // If the target isn't in range, hook it up to an existing or new + // thunk. + Defined *Thunk; + bool WasNew; + std::tie(Thunk, WasNew) = getThunk(LastThunks, Sym, P, Rel.Type, Margin); + if (WasNew) { + Chunk *ThunkChunk = Thunk->getChunk(); + ThunkChunk->setRVA( + ThunkInsertionRVA); // Estimate of where it will be located. + Chunks.insert(Chunks.begin() + ThunkInsertionSpot, ThunkChunk); + ThunkInsertionSpot++; + ThunksSize += ThunkChunk->getSize(); + ThunkInsertionRVA += ThunkChunk->getSize(); + AddressesChanged = true; + } + RelocTarget = Thunk; + } + } + return AddressesChanged; +} + +static bool verifyRanges(const std::vector Chunks) { + for (Chunk *C : Chunks) { + SectionChunk *SC = dyn_cast_or_null(C); + if (!SC) + continue; + + for (size_t J = 0, E = SC->Relocs.size(); J < E; ++J) { + const coff_relocation &Rel = SC->Relocs[J]; + Symbol *RelocTarget = SC->RelocTargets[J]; + + Defined *Sym = dyn_cast_or_null(RelocTarget); + if (!Sym) + continue; + + uint64_t P = SC->getRVA() + Rel.VirtualAddress; + uint64_t S = Sym->getRVA(); + + if (!isInRange(Rel.Type, S, P, 0)) + return false; + } + } + return true; +} + +// Assign addresses and add thunks if necessary. +void Writer::finalizeAddresses() { + assignAddresses(); + if (!machineRequiresThunks()) + return; + size_t OrigNumChunks = 0, NumChunks = 0; + for (OutputSection *Sec : OutputSections) { + Sec->OrigChunks = Sec->Chunks; + OrigNumChunks += Sec->Chunks.size(); + } + int ThunkPass = 0; + bool AddressesChanged; + int Margin = 1024 * 100; + while (true) { + if (ThunkPass >= 10) + fatal("adding thunks hasn't converged after " + Twine(ThunkPass) + + " passes"); + + // Try adding thunks everywhere where it is needed, with a margin + // to avoid things going out of range due to the added thunks. + AddressesChanged = false; + for (OutputSection *Sec : OutputSections) + AddressesChanged |= Sec->createThunks(Margin); + ThunkPass++; + if (!AddressesChanged) { + NumChunks = OrigNumChunks; + break; + } + + // Check that after adding thunks, everything is now within an + // acceptable range. + assignAddresses(); + bool RangesOk = true; + NumChunks = 0; + for (OutputSection *Sec : OutputSections) { + if (!verifyRanges(Sec->Chunks)) { + RangesOk = false; + break; + } + NumChunks += Sec->Chunks.size(); + } + if (RangesOk) + break; + + // If something still was out of range, reset everything back to the + // original conditions and retry with a wider margin. This should + // ideally never happen under real circumstances. + for (OutputSection *Sec : OutputSections) { + Sec->Chunks = Sec->OrigChunks; + for (Chunk *C : Sec->Chunks) + C->resetRelocTargets(); + } + Margin *= 2; + } + log("Added " + Twine(NumChunks - OrigNumChunks) + " thunks with margin " + + Twine(Margin) + " in " + Twine(ThunkPass) + " passes"); +} + // The main function of the writer. void Writer::run() { ScopedTimer T1(CodeLayoutTimer); @@ -363,7 +544,8 @@ createImportTables(); createExportTable(); mergeSections(); - assignAddresses(); + readRelocTargets(); + finalizeAddresses(); removeEmptySections(); setSectionPermissions(); createSymbolAndStringTable(); @@ -733,9 +915,9 @@ } void Writer::mergeSections() { - if (!PdataSec->getChunks().empty()) { - FirstPdata = PdataSec->getChunks().front(); - LastPdata = PdataSec->getChunks().back(); + if (!PdataSec->Chunks.empty()) { + FirstPdata = PdataSec->Chunks.front(); + LastPdata = PdataSec->Chunks.back(); } for (auto &P : Config->Merge) { @@ -763,6 +945,13 @@ } } +// Visits all sections to initialize their relocation targets. +void Writer::readRelocTargets() { + for (OutputSection *Sec : OutputSections) + for_each(parallel::par, Sec->Chunks.begin(), Sec->Chunks.end(), + [&](Chunk *C) { C->readRelocTargets(); }); +} + // Visits all sections to assign incremental, non-overlapping RVAs and // file offsets. void Writer::assignAddresses() { @@ -780,7 +969,7 @@ addBaserels(); uint64_t RawSize = 0, VirtualSize = 0; Sec->Header.VirtualAddress = RVA; - for (Chunk *C : Sec->getChunks()) { + for (Chunk *C : Sec->Chunks) { VirtualSize = alignTo(VirtualSize, C->Alignment); C->setRVA(RVA + VirtualSize); C->OutputSectionOff = VirtualSize; @@ -1250,7 +1439,7 @@ // ADD instructions). if (Sec->Header.Characteristics & IMAGE_SCN_CNT_CODE) memset(SecBuf, 0xCC, Sec->getRawSize()); - for_each(parallel::par, Sec->getChunks().begin(), Sec->getChunks().end(), + for_each(parallel::par, Sec->Chunks.begin(), Sec->Chunks.end(), [&](Chunk *C) { C->writeTo(SecBuf); }); } } @@ -1349,12 +1538,13 @@ void Writer::addBaserels() { if (!Config->Relocatable) return; + RelocSec->Chunks.clear(); std::vector V; for (OutputSection *Sec : OutputSections) { if (Sec->Header.Characteristics & IMAGE_SCN_MEM_DISCARDABLE) continue; // Collect all locations for base relocations. - for (Chunk *C : Sec->getChunks()) + for (Chunk *C : Sec->Chunks) C->getBaserels(&V); // Add the addresses to .reloc section. if (!V.empty()) Index: test/COFF/Inputs/far-arm-thumb-abs.s =================================================================== --- test/COFF/Inputs/far-arm-thumb-abs.s +++ /dev/null @@ -1,2 +0,0 @@ -.global too_far1 -too_far1 = 0x1401004 Index: test/COFF/Inputs/far-arm-thumb-abs20.s =================================================================== --- test/COFF/Inputs/far-arm-thumb-abs20.s +++ /dev/null @@ -1,2 +0,0 @@ -.global too_far20 -too_far20 = 0x501004 Index: test/COFF/arm-thumb-branch-error.s =================================================================== --- test/COFF/arm-thumb-branch-error.s +++ /dev/null @@ -1,10 +0,0 @@ -// RUN: llvm-mc -filetype=obj -triple=thumbv7a-windows-gnu %s -o %t -// RUN: llvm-mc -filetype=obj -triple=thumbv7a-windows-gnu %S/Inputs/far-arm-thumb-abs.s -o %tfar -// RUN: not lld-link -entry:_start -subsystem:console %t %tfar -out:%t2 2>&1 | FileCheck %s -// REQUIRES: arm - .syntax unified - .globl _start -_start: - bl too_far1 - -// CHECK: relocation out of range Index: test/COFF/arm-thumb-branch20-error.s =================================================================== --- test/COFF/arm-thumb-branch20-error.s +++ test/COFF/arm-thumb-branch20-error.s @@ -1,10 +1,16 @@ // REQUIRES: arm // RUN: llvm-mc -filetype=obj -triple=thumbv7a-windows-gnu %s -o %t.obj -// RUN: llvm-mc -filetype=obj -triple=thumbv7a-windows-gnu %S/Inputs/far-arm-thumb-abs20.s -o %t.far.obj -// RUN: not lld-link -entry:_start -subsystem:console %t.obj %t.far.obj -out:%t.exe 2>&1 | FileCheck %s +// RUN: not lld-link -entry:_start -subsystem:console %t.obj -out:%t.exe 2>&1 | FileCheck %s .syntax unified .globl _start _start: bne too_far20 + .space 0x100000 + .section .text$a, "xr" +too_far20: + bx lr -// CHECK: relocation out of range +// When trying to add a thunk at the end of the section, the thunk itself +// will be too far away, so this won't converge. + +// CHECK: adding thunks hasn't converged