lib/ExecutionEngine/RuntimeDyld/RuntimeDyld.cpp

   1 //===-- RuntimeDyld.h - Run-time dynamic linker for MC-JIT ------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Implementation of the MC-JIT runtime dynamic linker.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "dyld"
  15 #include "llvm/ADT/OwningPtr.h"
  16 #include "llvm/ADT/SmallVector.h"
  17 #include "llvm/ADT/StringMap.h"
  18 #include "llvm/ADT/StringRef.h"
  19 #include "llvm/ADT/STLExtras.h"
  20 #include "llvm/ADT/Twine.h"
  21 #include "llvm/ExecutionEngine/RuntimeDyld.h"
  22 #include "llvm/Object/MachOObject.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/ErrorHandling.h"
  25 #include "llvm/Support/Format.h"
  26 #include "llvm/Support/Memory.h"
  27 #include "llvm/Support/MemoryBuffer.h"
  28 #include "llvm/Support/system_error.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 using namespace llvm;
  31 using namespace llvm::object;
  32
  33 // Empty out-of-line virtual destructor as the key function.
  34 RTDyldMemoryManager::~RTDyldMemoryManager() {}
  35
  36 namespace llvm {
  37 class RuntimeDyldImpl {
  38   unsigned CPUType;
  39   unsigned CPUSubtype;
  40
  41   // The MemoryManager to load objects into.
  42   RTDyldMemoryManager *MemMgr;
  43
  44
  45   // For each function, we have a MemoryBlock of it's instruction data.
  46   StringMap<sys::MemoryBlock> Functions;
  47
  48   // Master symbol table. As modules are loaded and external symbols are
  49   // resolved, their addresses are stored here.
  50   StringMap<uint64_t> SymbolTable;
  51
  52   // FIXME: Should have multiple data blocks, one for each loaded chunk of
  53   //        compiled code.
  54   sys::MemoryBlock Data;
  55
  56   bool HasError;
  57   std::string ErrorStr;
  58
  59   // Set the error state and record an error string.
  60   bool Error(const Twine &Msg) {
  61     ErrorStr = Msg.str();
  62     HasError = true;
  63     return true;
  64   }
  65
  66   void extractFunction(StringRef Name, uint8_t *StartAddress,
  67                        uint8_t *EndAddress);
  68   bool resolveRelocation(uint32_t BaseSection, macho::RelocationEntry RE,
  69                          SmallVectorImpl<void *> &SectionBases,
  70                          SmallVectorImpl<StringRef> &SymbolNames);
  71   bool resolveX86_64Relocation(intptr_t Address, intptr_t Value, bool isPCRel,
  72                                unsigned Type, unsigned Size);
  73   bool resolveARMRelocation(intptr_t Address, intptr_t Value, bool isPCRel,
  74                             unsigned Type, unsigned Size);
  75
  76   bool loadSegment32(const MachOObject *Obj,
  77                      const MachOObject::LoadCommandInfo *SegmentLCI,
  78                      const InMemoryStruct<macho::SymtabLoadCommand> &SymtabLC);
  79   bool loadSegment64(const MachOObject *Obj,
  80                      const MachOObject::LoadCommandInfo *SegmentLCI,
  81                      const InMemoryStruct<macho::SymtabLoadCommand> &SymtabLC);
  82
  83 public:
  84   RuntimeDyldImpl(RTDyldMemoryManager *mm) : MemMgr(mm), HasError(false) {}
  85
  86   bool loadObject(MemoryBuffer *InputBuffer);
  87
  88   void *getSymbolAddress(StringRef Name) {
  89     // FIXME: Just look up as a function for now. Overly simple of course.
  90     // Work in progress.
  91     return Functions.lookup(Name).base();
  92   }
  93
  94   sys::MemoryBlock getMemoryBlock() { return Data; }
  95
  96   // Is the linker in an error state?
  97   bool hasError() { return HasError; }
  98
  99   // Mark the error condition as handled and continue.
 100   void clearError() { HasError = false; }
 101
 102   // Get the error message.
 103   StringRef getErrorString() { return ErrorStr; }
 104 };
 105
 106 void RuntimeDyldImpl::extractFunction(StringRef Name, uint8_t *StartAddress,
 107                                       uint8_t *EndAddress) {
 108   // Allocate memory for the function via the memory manager.
 109   uintptr_t Size = EndAddress - StartAddress + 1;
 110   uint8_t *Mem = MemMgr->startFunctionBody(Name.data(), Size);
 111   assert(Size >= (uint64_t)(EndAddress - StartAddress + 1) &&
 112          "Memory manager failed to allocate enough memory!");
 113   // Copy the function payload into the memory block.
 114   memcpy(Mem, StartAddress, EndAddress - StartAddress + 1);
 115   MemMgr->endFunctionBody(Name.data(), Mem, Mem + Size);
 116   // Remember where we put it.
 117   Functions[Name] = sys::MemoryBlock(Mem, Size);
 118   DEBUG(dbgs() << "    allocated to " << Mem << "\n");
 119 }
 120
 121 bool RuntimeDyldImpl::
 122 resolveRelocation(uint32_t BaseSection, macho::RelocationEntry RE,
 123                   SmallVectorImpl<void *> &SectionBases,
 124                   SmallVectorImpl<StringRef> &SymbolNames) {
 125   // struct relocation_info {
 126   //   int32_t r_address;
 127   //   uint32_t r_symbolnum:24,
 128   //            r_pcrel:1,
 129   //            r_length:2,
 130   //            r_extern:1,
 131   //            r_type:4;
 132   // };
 133   uint32_t SymbolNum = RE.Word1 & 0xffffff; // 24-bit value
 134   bool isPCRel = (RE.Word1 >> 24) & 1;
 135   unsigned Log2Size = (RE.Word1 >> 25) & 3;
 136   bool isExtern = (RE.Word1 >> 27) & 1;
 137   unsigned Type = (RE.Word1 >> 28) & 0xf;
 138   if (RE.Word0 & macho::RF_Scattered)
 139     return Error("NOT YET IMPLEMENTED: scattered relocations.");
 140
 141   // The address requiring a relocation.
 142   intptr_t Address = (intptr_t)SectionBases[BaseSection] + RE.Word0;
 143
 144   // Figure out the target address of the relocation. If isExtern is true,
 145   // this relocation references the symbol table, otherwise it references
 146   // a section in the same object, numbered from 1 through NumSections
 147   // (SectionBases is [0, NumSections-1]).
 148   intptr_t Value;
 149   if (isExtern) {
 150     StringRef Name = SymbolNames[SymbolNum];
 151     if (SymbolTable.lookup(Name)) {
 152       // The symbol is in our symbol table, so we can resolve it directly.
 153       Value = (intptr_t)SymbolTable[Name];
 154     } else {
 155       return Error("NOT YET IMPLEMENTED: relocations to pre-compiled code.");
 156     }
 157     DEBUG(dbgs() << "Resolve relocation(" << Type << ") from '" << Name
 158                  << "' to " << format("0x%x", Address) << ".\n");
 159   } else {
 160     // For non-external relocations, the SymbolNum is actual a section number
 161     // as described above.
 162     Value = (intptr_t)SectionBases[SymbolNum - 1];
 163   }
 164
 165   unsigned Size = 1 << Log2Size;
 166   switch (CPUType) {
 167   default: assert(0 && "Unsupported CPU type!");
 168   case mach::CTM_x86_64:
 169     return resolveX86_64Relocation(Address, Value, isPCRel, Type, Size);
 170   case mach::CTM_ARM:
 171     return resolveARMRelocation(Address, Value, isPCRel, Type, Size);
 172   }
 173   llvm_unreachable("");
 174 }
 175
 176 bool RuntimeDyldImpl::resolveX86_64Relocation(intptr_t Address, intptr_t Value,
 177                                               bool isPCRel, unsigned Type,
 178                                               unsigned Size) {
 179   // If the relocation is PC-relative, the value to be encoded is the
 180   // pointer difference.
 181   if (isPCRel)
 182     // FIXME: It seems this value needs to be adjusted by 4 for an effective PC
 183     // address. Is that expected? Only for branches, perhaps?
 184     Value -= Address + 4;
 185
 186   switch(Type) {
 187   default:
 188     llvm_unreachable("Invalid relocation type!");
 189   case macho::RIT_X86_64_Unsigned:
 190   case macho::RIT_X86_64_Branch: {
 191     // Mask in the target value a byte at a time (we don't have an alignment
 192     // guarantee for the target address, so this is safest).
 193     uint8_t *p = (uint8_t*)Address;
 194     for (unsigned i = 0; i < Size; ++i) {
 195       *p++ = (uint8_t)Value;
 196       Value >>= 8;
 197     }
 198     return false;
 199   }
 200   case macho::RIT_X86_64_Signed:
 201   case macho::RIT_X86_64_GOTLoad:
 202   case macho::RIT_X86_64_GOT:
 203   case macho::RIT_X86_64_Subtractor:
 204   case macho::RIT_X86_64_Signed1:
 205   case macho::RIT_X86_64_Signed2:
 206   case macho::RIT_X86_64_Signed4:
 207   case macho::RIT_X86_64_TLV:
 208     return Error("Relocation type not implemented yet!");
 209   }
 210   return false;
 211 }
 212
 213 bool RuntimeDyldImpl::resolveARMRelocation(intptr_t Address, intptr_t Value,
 214                                            bool isPCRel, unsigned Type,
 215                                            unsigned Size) {
 216   // If the relocation is PC-relative, the value to be encoded is the
 217   // pointer difference.
 218   if (isPCRel) {
 219     Value -= Address;
 220     // ARM PCRel relocations have an effective-PC offset of two instructions
 221     // (four bytes in Thumb mode, 8 bytes in ARM mode).
 222     // FIXME: For now, assume ARM mode.
 223     Value -= 8;
 224   }
 225
 226   switch(Type) {
 227   default:
 228   case macho::RIT_Vanilla: {
 229     llvm_unreachable("Invalid relocation type!");
 230     // Mask in the target value a byte at a time (we don't have an alignment
 231     // guarantee for the target address, so this is safest).
 232     uint8_t *p = (uint8_t*)Address;
 233     for (unsigned i = 0; i < Size; ++i) {
 234       *p++ = (uint8_t)Value;
 235       Value >>= 8;
 236     }
 237     break;
 238   }
 239   case macho::RIT_Pair:
 240   case macho::RIT_Difference:
 241   case macho::RIT_ARM_LocalDifference:
 242   case macho::RIT_ARM_PreboundLazyPointer:
 243   case macho::RIT_ARM_Branch24Bit: {
 244     // Mask the value into the target address. We know instructions are
 245     // 32-bit aligned, so we can do it all at once.
 246     uint32_t *p = (uint32_t*)Address;
 247     // The low two bits of the value are not encoded.
 248     Value >>= 2;
 249     // Mask the value to 24 bits.
 250     Value &= 0xffffff;
 251     // FIXME: If the destination is a Thumb function (and the instruction
 252     // is a non-predicated BL instruction), we need to change it to a BLX
 253     // instruction instead.
 254
 255     // Insert the value into the instruction.
 256     *p = (*p & ~0xffffff) | Value;
 257     break;
 258   }
 259   case macho::RIT_ARM_ThumbBranch22Bit:
 260   case macho::RIT_ARM_ThumbBranch32Bit:
 261   case macho::RIT_ARM_Half:
 262   case macho::RIT_ARM_HalfDifference:
 263     return Error("Relocation type not implemented yet!");
 264   }
 265   return false;
 266 }
 267
 268 bool RuntimeDyldImpl::
 269 loadSegment32(const MachOObject *Obj,
 270               const MachOObject::LoadCommandInfo *SegmentLCI,
 271               const InMemoryStruct<macho::SymtabLoadCommand> &SymtabLC) {
 272   InMemoryStruct<macho::SegmentLoadCommand> Segment32LC;
 273   Obj->ReadSegmentLoadCommand(*SegmentLCI, Segment32LC);
 274   if (!Segment32LC)
 275     return Error("unable to load segment load command");
 276
 277   for (unsigned SectNum = 0; SectNum != Segment32LC->NumSections; ++SectNum) {
 278     InMemoryStruct<macho::Section> Sect;
 279     Obj->ReadSection(*SegmentLCI, SectNum, Sect);
 280     if (!Sect)
 281       return Error("unable to load section: '" + Twine(SectNum) + "'");
 282
 283     // FIXME: Improve check.
 284     if (Sect->Flags != 0x80000400)
 285       return Error("unsupported section type!");
 286
 287     // Address and names of symbols in the section.
 288     typedef std::pair<uint64_t, StringRef> SymbolEntry;
 289     SmallVector<SymbolEntry, 32> Symbols;
 290     for (unsigned i = 0; i != SymtabLC->NumSymbolTableEntries; ++i) {
 291       InMemoryStruct<macho::SymbolTableEntry> STE;
 292       Obj->ReadSymbolTableEntry(SymtabLC->SymbolTableOffset, i, STE);
 293       if (!STE)
 294         return Error("unable to read symbol: '" + Twine(i) + "'");
 295       if (STE->SectionIndex > Segment32LC->NumSections)
 296         return Error("invalid section index for symbol: '" + Twine(i) + "'");
 297
 298       // Just skip symbols not defined in this section.
 299       if ((unsigned)STE->SectionIndex - 1 != SectNum)
 300         continue;
 301
 302       // Get the symbol name.
 303       StringRef Name = Obj->getStringAtIndex(STE->StringIndex);
 304
 305       // FIXME: Check the symbol type and flags.
 306       if (STE->Type != 0xF)  // external, defined in this section.
 307         return Error("unexpected symbol type!");
 308       if (STE->Flags != 0x0)
 309         return Error("unexpected symbol type!");
 310
 311       uint64_t BaseAddress = Sect->Address;
 312       uint64_t Address = BaseAddress + STE->Value;
 313
 314       // Remember the symbol.
 315       Symbols.push_back(SymbolEntry(Address, Name));
 316
 317       DEBUG(dbgs() << "Function sym: '" << Name << "' @ " << Address << "\n");
 318     }
 319     // Sort the symbols by address, just in case they didn't come in that
 320     // way.
 321     array_pod_sort(Symbols.begin(), Symbols.end());
 322
 323     // Extract the function data.
 324     uint8_t *Base = (uint8_t*)Obj->getData(Segment32LC->FileOffset,
 325                                            Segment32LC->FileSize).data();
 326     for (unsigned i = 0, e = Symbols.size() - 1; i != e; ++i) {
 327       uint64_t StartOffset = Symbols[i].first;
 328       uint64_t EndOffset = Symbols[i + 1].first - 1;
 329       DEBUG(dbgs() << "Extracting function: " << Symbols[i].second
 330                    << " from [" << StartOffset << ", " << EndOffset << "]\n");
 331       extractFunction(Symbols[i].second, Base + StartOffset, Base + EndOffset);
 332     }
 333     // The last symbol we do after since the end address is calculated
 334     // differently because there is no next symbol to reference.
 335     uint64_t StartOffset = Symbols[Symbols.size() - 1].first;
 336     uint64_t EndOffset = Sect->Size - 1;
 337     DEBUG(dbgs() << "Extracting function: " << Symbols[Symbols.size()-1].second
 338                  << " from [" << StartOffset << ", " << EndOffset << "]\n");
 339     extractFunction(Symbols[Symbols.size()-1].second,
 340                     Base + StartOffset, Base + EndOffset);
 341   }
 342
 343   return false;
 344 }
 345
 346
 347 bool RuntimeDyldImpl::
 348 loadSegment64(const MachOObject *Obj,
 349               const MachOObject::LoadCommandInfo *SegmentLCI,
 350               const InMemoryStruct<macho::SymtabLoadCommand> &SymtabLC) {
 351   InMemoryStruct<macho::Segment64LoadCommand> Segment64LC;
 352   Obj->ReadSegment64LoadCommand(*SegmentLCI, Segment64LC);
 353   if (!Segment64LC)
 354     return Error("unable to load segment load command");
 355
 356   for (unsigned SectNum = 0; SectNum != Segment64LC->NumSections; ++SectNum) {
 357     InMemoryStruct<macho::Section64> Sect;
 358     Obj->ReadSection64(*SegmentLCI, SectNum, Sect);
 359     if (!Sect)
 360       return Error("unable to load section: '" + Twine(SectNum) + "'");
 361
 362     // FIXME: Improve check.
 363     if (Sect->Flags != 0x80000400)
 364       return Error("unsupported section type!");
 365
 366     // Address and names of symbols in the section.
 367     typedef std::pair<uint64_t, StringRef> SymbolEntry;
 368     SmallVector<SymbolEntry, 64> Symbols;
 369     for (unsigned i = 0; i != SymtabLC->NumSymbolTableEntries; ++i) {
 370       InMemoryStruct<macho::Symbol64TableEntry> STE;
 371       Obj->ReadSymbol64TableEntry(SymtabLC->SymbolTableOffset, i, STE);
 372       if (!STE)
 373         return Error("unable to read symbol: '" + Twine(i) + "'");
 374       if (STE->SectionIndex > Segment64LC->NumSections)
 375         return Error("invalid section index for symbol: '" + Twine(i) + "'");
 376
 377       // Just skip symbols not defined in this section.
 378       if ((unsigned)STE->SectionIndex - 1 != SectNum)
 379         continue;
 380
 381       // Get the symbol name.
 382       StringRef Name = Obj->getStringAtIndex(STE->StringIndex);
 383
 384       // FIXME: Check the symbol type and flags.
 385       if (STE->Type != 0xF)  // external, defined in this section.
 386         return Error("unexpected symbol type!");
 387       if (STE->Flags != 0x0)
 388         return Error("unexpected symbol type!");
 389
 390       uint64_t BaseAddress = Sect->Address;
 391       uint64_t Address = BaseAddress + STE->Value;
 392
 393       // Remember the symbol.
 394       Symbols.push_back(SymbolEntry(Address, Name));
 395
 396       DEBUG(dbgs() << "Function sym: '" << Name << "' @ " << Address << "\n");
 397     }
 398     // Sort the symbols by address, just in case they didn't come in that
 399     // way.
 400     array_pod_sort(Symbols.begin(), Symbols.end());
 401
 402     // Extract the function data.
 403     uint8_t *Base = (uint8_t*)Obj->getData(Segment64LC->FileOffset,
 404                                            Segment64LC->FileSize).data();
 405     for (unsigned i = 0, e = Symbols.size() - 1; i != e; ++i) {
 406       uint64_t StartOffset = Symbols[i].first;
 407       uint64_t EndOffset = Symbols[i + 1].first - 1;
 408       DEBUG(dbgs() << "Extracting function: " << Symbols[i].second
 409                    << " from [" << StartOffset << ", " << EndOffset << "]\n");
 410       extractFunction(Symbols[i].second, Base + StartOffset, Base + EndOffset);
 411     }
 412     // The last symbol we do after since the end address is calculated
 413     // differently because there is no next symbol to reference.
 414     uint64_t StartOffset = Symbols[Symbols.size() - 1].first;
 415     uint64_t EndOffset = Sect->Size - 1;
 416     DEBUG(dbgs() << "Extracting function: " << Symbols[Symbols.size()-1].second
 417                  << " from [" << StartOffset << ", " << EndOffset << "]\n");
 418     extractFunction(Symbols[Symbols.size()-1].second,
 419                     Base + StartOffset, Base + EndOffset);
 420   }
 421
 422   return false;
 423 }
 424
 425 bool RuntimeDyldImpl::loadObject(MemoryBuffer *InputBuffer) {
 426   // If the linker is in an error state, don't do anything.
 427   if (hasError())
 428     return true;
 429   // Load the Mach-O wrapper object.
 430   std::string ErrorStr;
 431   OwningPtr<MachOObject> Obj(
 432     MachOObject::LoadFromBuffer(InputBuffer, &ErrorStr));
 433   if (!Obj)
 434     return Error("unable to load object: '" + ErrorStr + "'");
 435
 436   // Get the CPU type information from the header.
 437   const macho::Header &Header = Obj->getHeader();
 438
 439   // FIXME: Error checking that the loaded object is compatible with
 440   //        the system we're running on.
 441   CPUType = Header.CPUType;
 442   CPUSubtype = Header.CPUSubtype;
 443
 444   // Validate that the load commands match what we expect.
 445   const MachOObject::LoadCommandInfo *SegmentLCI = 0, *SymtabLCI = 0,
 446     *DysymtabLCI = 0;
 447   for (unsigned i = 0; i != Header.NumLoadCommands; ++i) {
 448     const MachOObject::LoadCommandInfo &LCI = Obj->getLoadCommandInfo(i);
 449     switch (LCI.Command.Type) {
 450     case macho::LCT_Segment:
 451     case macho::LCT_Segment64:
 452       if (SegmentLCI)
 453         return Error("unexpected input object (multiple segments)");
 454       SegmentLCI = &LCI;
 455       break;
 456     case macho::LCT_Symtab:
 457       if (SymtabLCI)
 458         return Error("unexpected input object (multiple symbol tables)");
 459       SymtabLCI = &LCI;
 460       break;
 461     case macho::LCT_Dysymtab:
 462       if (DysymtabLCI)
 463         return Error("unexpected input object (multiple symbol tables)");
 464       DysymtabLCI = &LCI;
 465       break;
 466     default:
 467       return Error("unexpected input object (unexpected load command");
 468     }
 469   }
 470
 471   if (!SymtabLCI)
 472     return Error("no symbol table found in object");
 473   if (!SegmentLCI)
 474     return Error("no symbol table found in object");
 475
 476   // Read and register the symbol table data.
 477   InMemoryStruct<macho::SymtabLoadCommand> SymtabLC;
 478   Obj->ReadSymtabLoadCommand(*SymtabLCI, SymtabLC);
 479   if (!SymtabLC)
 480     return Error("unable to load symbol table load command");
 481   Obj->RegisterStringTable(*SymtabLC);
 482
 483   // Read the dynamic link-edit information, if present (not present in static
 484   // objects).
 485   if (DysymtabLCI) {
 486     InMemoryStruct<macho::DysymtabLoadCommand> DysymtabLC;
 487     Obj->ReadDysymtabLoadCommand(*DysymtabLCI, DysymtabLC);
 488     if (!DysymtabLC)
 489       return Error("unable to load dynamic link-exit load command");
 490
 491     // FIXME: We don't support anything interesting yet.
 492 //    if (DysymtabLC->LocalSymbolsIndex != 0)
 493 //      return Error("NOT YET IMPLEMENTED: local symbol entries");
 494 //    if (DysymtabLC->ExternalSymbolsIndex != 0)
 495 //      return Error("NOT YET IMPLEMENTED: non-external symbol entries");
 496 //    if (DysymtabLC->UndefinedSymbolsIndex != SymtabLC->NumSymbolTableEntries)
 497 //      return Error("NOT YET IMPLEMENTED: undefined symbol entries");
 498   }
 499
 500   // Load the segment load command.
 501   if (SegmentLCI->Command.Type == macho::LCT_Segment) {
 502     if (loadSegment32(Obj.get(), SegmentLCI, SymtabLC))
 503       return true;
 504   } else {
 505     if (loadSegment64(Obj.get(), SegmentLCI, SymtabLC))
 506       return true;
 507   }
 508
 509   return false;
 510 }
 511
 512
 513 //===----------------------------------------------------------------------===//
 514 // RuntimeDyld class implementation
 515 RuntimeDyld::RuntimeDyld(RTDyldMemoryManager *MM) {
 516   Dyld = new RuntimeDyldImpl(MM);
 517 }
 518
 519 RuntimeDyld::~RuntimeDyld() {
 520   delete Dyld;
 521 }
 522
 523 bool RuntimeDyld::loadObject(MemoryBuffer *InputBuffer) {
 524   return Dyld->loadObject(InputBuffer);
 525 }
 526
 527 void *RuntimeDyld::getSymbolAddress(StringRef Name) {
 528   return Dyld->getSymbolAddress(Name);
 529 }
 530
 531 sys::MemoryBlock RuntimeDyld::getMemoryBlock() {
 532   return Dyld->getMemoryBlock();
 533 }
 534
 535 StringRef RuntimeDyld::getErrorString() {
 536   return Dyld->getErrorString();
 537 }
 538
 539 } // end namespace llvm