[LLD][ARM] Add support for thunks to undefined non-weak symbols

[peter.smith]

Summary

In a shared library an undefined symbol is implicitly imported. If the symbol is called as a function a PLT entry is generated for it. When the caller is a Thumb b.w a thunk to the PLT entry is needed as all PLT entries are in ARM state.

This change allows undefined symbols to have thunks in the same way that shared symbols may have thunks.

I found this after finding segfaults in the Thumb2 release build of various python C extensions. The extensions are built as shared objects
that call back to the python interpreter. The python interpreter symbols are implicitly imported as undefined symbols. If a tail call from Thumb2 is used b.w then the PLT entry (ARM) was entered in Thumb state causing a segfault.

Adding thunks to undefined symbols is straightforward, although it does have the side-effect of adding a template parameter which requires some unrelated code to be updated. I considered trying to convert the undefined symbol to a shared symbol, but decided against it on the grounds that that this might cause problems later on if the non-existent InputFile was ever accessed.

[ruiu]

The concept of "undefined symbols with thunks" doesn't click in my mind. It feels like a null pointer but with some data. Can we handle such undefined symbols as a different type? For example, what if we promote (or replace) undefined symbols with shared symbols (or defined symbols) after we resolve all symbols if we are creating an DSO?

[peter.smith]

I think it depends on what the precise meaning of Shared and Undefined. At the moment I think the distinction is:
Shared:

• The symbol is defined in a known shared object.
• The symbol details such as type, binding and version are known.
• The shared object has been added as a dependency to the output.
• The shared object defining the symbol can be found from the SymbolBody.

Undefined:

• We have a reference to a symbol but no definition.
• When linking a shared library we assume that the dynamic loader will find a suitable definition from the executable/shared library or error.
• In all other cases (besides relocatable -r) an undefined non-weak symbol is an error.
• There is no input file associated with the symbol.

With those definitions I don't think that there is a problem with Thunks on undefined symbols. There is a call to a symbol that we know nothing about and we are going to rely on the dynamic loader to sort it out for us. As we need the dynamic loader we will necessarily need a PLT entry. The Thunk is from the caller to the PLT entry.

If we make the change to say that in Shared Libraries Undefined symbols become Shared there will be some implications. I think the definition of Shared has to be weakened to something closer to Undefined and any calling code that needs to know about the distinctions will have to do some extra work. For example if we have some diagnostics that print out the shared library name for the Shared symbol will need to test to see if it actually has an associated file.

Other possibilities:

• A SharedUndefined symbol kind that could replace the if (body.isUndefined() && body.isShared()) with body.isUndefinedShared(), that could support a Thunk and we could keep Undefined to mean error if not defined.
• Don't solve this problem right now and start work on range-extension thunks. As there can be more than one Thunk per symbol with range extension thunks we'll need to do something differently anyway.

I'm happy to try out the alternatives. I'm on vacation from Monday till the end of the year so I'll probably only be able to get a small change done by then.

[ruiu]

Thank you for the explanation. I think I'm convinced that undefined symbols with thunks are not really that odd concept.

ELF/Symbols.h

248

Can you also mention that remaining undefined symbols when creating a DSO are resolved by the dynamic linker, and relocation against such undefined symbols need thunk in some architecture such as AArch64?

ELF/Target.cpp

1734

This code is subtle. So, if there is a remaining undefined symbol with a weak linkage when creating a DSO, we'll let the dynamic linker resolve it, instead of handling it as an undefined symbol. Is this consistent with other code in LLD and other linkers? It would be nice to add a comment to clarify.

[peter.smith]

Thanks for the update. I've added the comments.

I've also checked the behaviour of undefined weak references and both gold and lld will create PLT entries for calls to weak references in shared libraries. As a result I've updated the condition and added the behaviour to the test.

[peter.smith]

Rebased patch to account for last couple of weeks changes, no functional changes. Happy New Year!

I don't think that there are any outstanding review comments left to address. Let me know if there is anything else?

[ruiu]

LGTM

[peter.smith]

Thanks for the review, committed revision 290951

ELF/InputFiles.cpp

if (Sym->getType() == STT_FILE)
       SourceFile = check(Sym->getName(this->StringTable));
 
     if (this->StringTable.size() <= Sym->st_name)
       fatal(toString(this) + ": invalid symbol name offset");
 
     StringRefZ Name = this->StringTable.data() + Sym->st_name;
     if (Sym->st_shndx == SHN_UNDEF)
       return new (BAlloc)
-          Undefined(Name, /*IsLocal=*/true, StOther, Type, this);
+          Undefined<ELFT>(Name, /*IsLocal=*/true, StOther, Type, this);
 
     return new (BAlloc) DefinedRegular<ELFT>(Name, /*IsLocal=*/true, StOther,
                                              Type, Value, Size, Sec, this);
   }
 
   StringRef Name = check(Sym->getName(this->StringTable));
 
   switch (Sym->st_shndx) {

ELF/LTO.h

 class BitcodeFile;
 class InputFile;
 
 class BitcodeCompiler {
 public:
   BitcodeCompiler();
   ~BitcodeCompiler();
 
-  void add(BitcodeFile &F);
+  template <class ELFT> void add(BitcodeFile &F);
   std::vector<InputFile *> compile();
 
 private:
   std::unique_ptr<llvm::lto::LTO> LTOObj;
   std::vector<SmallString<0>> Buff;
 };
 }
 }
 
 #endif

ELF/LTO.cpp

static std::unique_ptr<lto::LTO> createLTO() {
   return llvm::make_unique<lto::LTO>(std::move(Conf), Backend,
                                      Config->LTOPartitions);
 }
 
 BitcodeCompiler::BitcodeCompiler() : LTOObj(createLTO()) {}
 
 BitcodeCompiler::~BitcodeCompiler() = default;
 
-static void undefine(Symbol *S) {
-  replaceBody<Undefined>(S, S->body()->getName(), /*IsLocal=*/false,
+template <class ELFT> static void undefine(Symbol *S) {
+  replaceBody<Undefined<ELFT>>(S, S->body()->getName(), /*IsLocal=*/false,
                                STV_DEFAULT, S->body()->Type, nullptr);
 }
 
-void BitcodeCompiler::add(BitcodeFile &F) {
+template <class ELFT> void BitcodeCompiler::add(BitcodeFile &F) {
   lto::InputFile &Obj = *F.Obj;
   unsigned SymNum = 0;
   std::vector<Symbol *> Syms = F.getSymbols();
   std::vector<lto::SymbolResolution> Resols(Syms.size());
 
   // Provide a resolution to the LTO API for each symbol.
   for (const lto::InputFile::Symbol &ObjSym : Obj.symbols()) {
     Symbol *Sym = Syms[SymNum];
     lto::SymbolResolution &R = Resols[SymNum];
     ++SymNum;
     SymbolBody *B = Sym->body();
 
     // Ideally we shouldn't check for SF_Undefined but currently IRObjectFile
     // reports two symbols for module ASM defined. Without this check, lld
     // flags an undefined in IR with a definition in ASM as prevailing.
     // Once IRObjectFile is fixed to report only one symbol this hack can
     // be removed.
     R.Prevailing =
         !(ObjSym.getFlags() & object::BasicSymbolRef::SF_Undefined) &&
         B->File == &F;
 
     R.VisibleToRegularObj =
         Sym->IsUsedInRegularObj || (R.Prevailing && Sym->includeInDynsym());
     if (R.Prevailing)
-      undefine(Sym);
+      undefine<ELFT>(Sym);
   }
   checkError(LTOObj->add(std::move(F.Obj), Resols));
 }
 
 // Merge all the bitcode files we have seen, codegen the result
 // and return the resulting ObjectFile(s).
 std::vector<InputFile *> BitcodeCompiler::compile() {
   std::vector<InputFile *> Ret;
if (Config->SaveTemps) {
       else
         saveBuffer(Buff[I], Config->OutputFile + Twine(I) + ".lto.o");
     }
     InputFile *Obj = createObjectFile(MemoryBufferRef(Buff[I], "lto.tmp"));
     Ret.push_back(Obj);
   }
   return Ret;
 }
+
+template void BitcodeCompiler::template add<ELF32LE>(BitcodeFile &);
+template void BitcodeCompiler::template add<ELF32BE>(BitcodeFile &);
+template void BitcodeCompiler::template add<ELF64LE>(BitcodeFile &);
+template void BitcodeCompiler::template add<ELF64BE>(BitcodeFile &);

ELF/SymbolTable.cpp

 // to the compiler at once, it can do whole-program optimization.
 template <class ELFT> void SymbolTable<ELFT>::addCombinedLTOObject() {
   if (BitcodeFiles.empty())
     return;
 
   // Compile bitcode files and replace bitcode symbols.
   LTO.reset(new BitcodeCompiler);
   for (BitcodeFile *F : BitcodeFiles)
-    LTO->add(*F);
+    LTO->add<ELFT>(*F);
 
   for (InputFile *File : LTO->compile()) {
     ObjectFile<ELFT> *Obj = cast<ObjectFile<ELFT>>(File);
     DenseSet<CachedHashStringRef> DummyGroups;
     Obj->parse(DummyGroups);
     ObjectFiles.push_back(Obj);
   }
 }
Symbol *SymbolTable<ELFT>::addUndefined(StringRef Name, bool IsLocal,
                                         uint8_t Type, bool CanOmitFromDynSym,
                                         InputFile *File) {
   Symbol *S;
   bool WasInserted;
   std::tie(S, WasInserted) =
       insert(Name, Type, getVisibility(StOther), CanOmitFromDynSym, File);
   if (WasInserted) {
     S->Binding = Binding;
-    replaceBody<Undefined>(S, Name, IsLocal, StOther, Type, File);
+    replaceBody<Undefined<ELFT>>(S, Name, IsLocal, StOther, Type, File);
     return S;
   }
   if (Binding != STB_WEAK) {
     if (S->body()->isShared() || S->body()->isLazy())
       S->Binding = Binding;
     if (auto *SS = dyn_cast<SharedSymbol<ELFT>>(S->body()))
       SS->file()->IsUsed = true;
   }
std::tie(S, WasInserted) =
       insert(Name, Sym.getType(), STV_DEFAULT, /*CanOmitFromDynSym*/ true, F);
   // Make sure we preempt DSO symbols with default visibility.
   if (Sym.getVisibility() == STV_DEFAULT) {
     S->ExportDynamic = true;
     // Exporting preempting symbols takes precedence over linker scripts.
     if (S->VersionId == VER_NDX_LOCAL)
       S->VersionId = VER_NDX_GLOBAL;
   }
-  if (WasInserted || isa<Undefined>(S->body())) {
+  if (WasInserted || isa<Undefined<ELFT>>(S->body())) {
     replaceBody<SharedSymbol<ELFT>>(S, F, Name, Sym, Verdef);
     if (!S->isWeak())
       F->IsUsed = true;
   }
 }
 
 template <class ELFT>
 Symbol *SymbolTable<ELFT>::addBitcode(StringRef Name, uint8_t Binding,

ELF/Symbols.h

public:
   static bool classof(const SymbolBody *S) {
     return S->kind() == SymbolBody::DefinedSyntheticKind;
   }
 
   uint64_t Value;
   const OutputSectionBase *Section;
 };
 
-class Undefined : public SymbolBody {
+template <class ELFT> class Undefined : public SymbolBody {
 public:
   Undefined(StringRefZ Name, bool IsLocal, uint8_t StOther, uint8_t Type,
             InputFile *F);
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == UndefinedKind;
   }
 
+  // If non-null the symbol has a Thunk that may be used as an alternative
+  // destination for callers of this Symbol. When linking a DSO undefined
+  // symbols are implicitly imported, the symbol lookup will be performed by
+  // the dynamic loader. A call to an undefined symbol will be given a PLT
+  // entry and on ARM this may need a Thunk if the caller is in Thumb state.
+  Thunk<ELFT> *ThunkData = nullptr;
   InputFile *file() { return this->File; }
 };
 
 template <class ELFT> class SharedSymbol : public Defined {
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::Verdef Elf_Verdef;
   typedef typename ELFT::uint uintX_t;
 
struct Symbol {
 
   // This field is used to store the Symbol's SymbolBody. This instantiation of
   // AlignedCharArrayUnion gives us a struct with a char array field that is
   // large and aligned enough to store any derived class of SymbolBody. We
   // assume that the size and alignment of ELF64LE symbols is sufficient for any
   // ELFT, and we verify this with the static_asserts in replaceBody.
   llvm::AlignedCharArrayUnion<
       DefinedCommon, DefinedRegular<llvm::object::ELF64LE>, DefinedSynthetic,
-      Undefined, SharedSymbol<llvm::object::ELF64LE>, LazyArchive, LazyObject>
+      Undefined<llvm::object::ELF64LE>, SharedSymbol<llvm::object::ELF64LE>,
+      LazyArchive, LazyObject>
       Body;
 
   SymbolBody *body() { return reinterpret_cast<SymbolBody *>(Body.buffer); }
   const SymbolBody *body() const { return const_cast<Symbol *>(this)->body(); }
 };
 
 void printTraceSymbol(Symbol *Sym);
 

ELF/Symbols.cpp

return In<ELFT>::Plt->getVA() + Target->PltHeaderSize +
          PltIndex * Target->PltEntrySize;
 }
 
 template <class ELFT> typename ELFT::uint SymbolBody::getThunkVA() const {
   if (const auto *DR = dyn_cast<DefinedRegular<ELFT>>(this))
     return DR->ThunkData->getVA();
   if (const auto *S = dyn_cast<SharedSymbol<ELFT>>(this))
     return S->ThunkData->getVA();
+  if (const auto *S = dyn_cast<Undefined<ELFT>>(this))
+    return S->ThunkData->getVA();
   fatal("getThunkVA() not supported for Symbol class\n");
 }
 
 template <class ELFT> typename ELFT::uint SymbolBody::getSize() const {
   if (const auto *C = dyn_cast<DefinedCommon>(this))
     return C->Size;
   if (const auto *DR = dyn_cast<DefinedRegular<ELFT>>(this))
     return DR->Size;

 
 template <class ELFT> bool DefinedRegular<ELFT>::isMipsPIC() const {
   if (!Section || !isFunc())
     return false;
   return (this->StOther & STO_MIPS_MIPS16) == STO_MIPS_PIC ||
          (Section->getFile()->getObj().getHeader()->e_flags & EF_MIPS_PIC);
 }
 
-Undefined::Undefined(StringRefZ Name, bool IsLocal, uint8_t StOther,
+template <typename ELFT>
+Undefined<ELFT>::Undefined(StringRefZ Name, bool IsLocal, uint8_t StOther,
                            uint8_t Type, InputFile *File)
     : SymbolBody(SymbolBody::UndefinedKind, Name, IsLocal, StOther, Type) {
   this->File = File;
 }
 
 DefinedCommon::DefinedCommon(StringRef Name, uint64_t Size, uint64_t Alignment,
                              uint8_t StOther, uint8_t Type, InputFile *File)
     : Defined(SymbolBody::DefinedCommonKind, Name, /*IsLocal=*/false, StOther,
               Type),

 template uint64_t SymbolBody::template getPltVA<ELF64LE>() const;
 template uint64_t SymbolBody::template getPltVA<ELF64BE>() const;
 
 template uint32_t SymbolBody::template getSize<ELF32LE>() const;
 template uint32_t SymbolBody::template getSize<ELF32BE>() const;
 template uint64_t SymbolBody::template getSize<ELF64LE>() const;
 template uint64_t SymbolBody::template getSize<ELF64BE>() const;
 
+template class elf::Undefined<ELF32LE>;
+template class elf::Undefined<ELF32BE>;
+template class elf::Undefined<ELF64LE>;
+template class elf::Undefined<ELF64BE>;
+
 template class elf::DefinedRegular<ELF32LE>;
 template class elf::DefinedRegular<ELF32BE>;
 template class elf::DefinedRegular<ELF64LE>;
 template class elf::DefinedRegular<ELF64BE>;

ELF/Target.cpp

void ARMTargetInfo::writePlt(uint8_t *Buf, uint64_t GotEntryAddr,
   memcpy(Buf, PltData, sizeof(PltData));
   uint64_t L1 = PltEntryAddr + 4;
   write32le(Buf + 12, GotEntryAddr - L1 - 8);
 }
 
 RelExpr ARMTargetInfo::getThunkExpr(RelExpr Expr, uint32_t RelocType,
                                     const InputFile &File,
                                     const SymbolBody &S) const {
-  // If S is an undefined weak symbol we don't need a Thunk
-  if (S.isUndefined())
+  // If S is an undefined weak symbol in an executable we don't need a Thunk.
+  // In a DSO calls to undefined symbols, including weak ones get PLT entries
+  // which may need a thunk.
+  if (S.isUndefined() && !S.isLocal() && S.symbol()->isWeak()
+      && !Config->Shared)
     return Expr;
   // A state change from ARM to Thumb and vice versa must go through an
   // interworking thunk if the relocation type is not R_ARM_CALL or
   // R_ARM_THM_CALL.
   switch (RelocType) {
   case R_ARM_PC24:
   case R_ARM_PLT32:
   case R_ARM_JUMP24:

ELF/Thunks.cpp

static void addThunkARM(uint32_t Reloc, SymbolBody &S, InputSection<ELFT> &IS) {
   // isn't strictly necessary but it makes it more likely that a limited range
   // branch can reach the Thunk, and it makes Thunks to the PLT section easier
   Thunk<ELFT> *T = createThunkArm(Reloc, S, IS);
   IS.addThunk(T);
   if (auto *Sym = dyn_cast<DefinedRegular<ELFT>>(&S))
     Sym->ThunkData = T;
   else if (auto *Sym = dyn_cast<SharedSymbol<ELFT>>(&S))
     Sym->ThunkData = T;
+  else if (auto *Sym = dyn_cast<Undefined<ELFT>>(&S))
+    Sym->ThunkData = T;
   else
     fatal("symbol not DefinedRegular or Shared");
 }
 
 template <class ELFT>
 static void addThunkMips(uint32_t RelocType, SymbolBody &S,
                          InputSection<ELFT> &IS) {
   // Only one Thunk supported per symbol.

test/ELF/arm-thumb-interwork-shared.s

+// RUN: llvm-mc -filetype=obj -triple=thumbv7a-none-linux-gnueabi %s -o %t
+// RUN: ld.lld %t --shared -o %t.so
+// RUN: llvm-objdump -d -triple=thumbv7a-none-linux-gnueabi %t.so | FileCheck %s
+// RUN: llvm-objdump -d -triple=armv7a-none-linux-gnueabi %t.so | FileCheck %s -check-prefix=PLT
+// REQUIRES: arm
+ .syntax unified
+ .global sym1
+ .global elsewhere
+ .weak weakref
+sym1:
+ b.w elsewhere
+ b.w weakref
+
+// Check that we generate a thunk for an undefined symbol called via a plt
+// entry.
+
+// CHECK: Disassembly of section .text:
+// CHECK-NEXT: sym1:
+// CHECK:          1000:       00 f0 02 b8     b.w     #4
+// CHECK-NEXT:     1004:       00 f0 06 b8     b.w     #12
+// CHECK-NEXT:     1008:       40 f2 20 0c     movw    r12, #32
+// CHECK-NEXT:     100c:       c0 f2 00 0c     movt    r12, #0
+// CHECK-NEXT:     1010:       fc 44   add     r12, pc
+// CHECK-NEXT:     1012:       60 47   bx      r12
+// CHECK-NEXT:     1014:       40 f2 24 0c     movw    r12, #36
+// CHECK-NEXT:     1018:       c0 f2 00 0c     movt    r12, #0
+// CHECK-NEXT:     101c:       fc 44   add     r12, pc
+// CHECK-NEXT:     101e:       60 47   bx      r12
+
+// PLT: Disassembly of section .plt:
+// PLT-NEXT: .plt:
+// PLT:          1020:       04 e0 2d e5     str     lr, [sp, #-4]!
+// PLT-NEXT:     1024:       04 e0 9f e5     ldr     lr, [pc, #4]
+// PLT-NEXT:     1028:       0e e0 8f e0     add     lr, pc, lr
+// PLT-NEXT:     102c:       08 f0 be e5     ldr     pc, [lr, #8]!
+// PLT-NEXT:     1030:       d0 1f 00 00
+// PLT-NEXT:     1034:       04 c0 9f e5     ldr     r12, [pc, #4]
+// PLT-NEXT:     1038:       0f c0 8c e0     add     r12, r12, pc
+// PLT-NEXT:     103c:       00 f0 9c e5     ldr     pc, [r12]
+// PLT-NEXT:     1040:       cc 1f 00 00
+// PLT-NEXT:     1044:       04 c0 9f e5     ldr     r12, [pc, #4]
+// PLT-NEXT:     1048:       0f c0 8c e0     add     r12, r12, pc
+// PLT-NEXT:     104c:       00 f0 9c e5     ldr     pc, [r12]
+// PLT-NEXT:     1050:       c0 1f 00 00