1 //===- MCLinker.cpp -----------------------------------------------------===// 2 // 3 // The MCLinker Project 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the MCLinker class 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include <mcld/MC/MCLinker.h> 15 #include <mcld/MC/MCLDInput.h> 16 #include <mcld/MC/MCLDInfo.h> 17 #include <mcld/LD/Resolver.h> 18 #include <mcld/LD/LDContext.h> 19 #include <mcld/LD/LDSymbol.h> 20 #include <mcld/LD/LDSectionFactory.h> 21 #include <mcld/LD/SectionMap.h> 22 #include <mcld/LD/RelocationFactory.h> 23 #include <mcld/Support/MemoryRegion.h> 24 #include <mcld/Target/TargetLDBackend.h> 25 #include <llvm/Support/Host.h> 26 #include <llvm/Support/raw_ostream.h> 27 28 using namespace mcld; 29 30 /// Constructor 31 MCLinker::MCLinker(TargetLDBackend& pBackend, 32 MCLDInfo& pInfo, 33 LDContext& pContext, 34 SectionMap& pSectionMap, 35 const Resolver& pResolver) 36 : m_Backend(pBackend), 37 m_Info(pInfo), 38 m_Output(pContext), 39 m_SectionMap(pSectionMap), 40 m_LDSymbolFactory(128), 41 m_LDSectHdrFactory(10), // the average number of sections. (assuming 10.) 42 m_LDSectDataFactory(10), 43 m_SectionMerger(pSectionMap, pContext), 44 m_StrSymPool(pResolver, 128) 45 { 46 m_Info.setNamePool(m_StrSymPool); 47 } 48 49 /// Destructor 50 MCLinker::~MCLinker() 51 { 52 } 53 54 /// addSymbolFromObject - add a symbol from object file and resolve it 55 /// immediately 56 LDSymbol* MCLinker::addSymbolFromObject(const llvm::StringRef& pName, 57 ResolveInfo::Type pType, 58 ResolveInfo::Desc pDesc, 59 ResolveInfo::Binding pBinding, 60 ResolveInfo::SizeType pSize, 61 LDSymbol::ValueType pValue, 62 MCFragmentRef* pFragmentRef, 63 ResolveInfo::Visibility pVisibility) 64 { 65 66 // resolved_result is a triple <resolved_info, existent, override> 67 Resolver::Result resolved_result; 68 ResolveInfo old_info; // used for arrange output symbols 69 70 if (pBinding == ResolveInfo::Local) { 71 // if the symbol is a local symbol, create a LDSymbol for input, but do not 72 // resolve them. 73 resolved_result.info = m_StrSymPool.createSymbol(pName, 74 false, 75 pType, 76 pDesc, 77 pBinding, 78 pSize, 79 pVisibility); 80 81 // No matter if there is a symbol with the same name, insert the symbol 82 // into output symbol table. So, we let the existent false. 83 resolved_result.existent = false; 84 resolved_result.overriden = true; 85 } 86 else { 87 // if the symbol is not local, insert and resolve it immediately 88 m_StrSymPool.insertSymbol(pName, false, pType, pDesc, pBinding, pSize, 89 pVisibility, &old_info, resolved_result); 90 } 91 92 // the return ResolveInfo should not NULL 93 assert(NULL != resolved_result.info); 94 95 // create a LDSymbol for the input file. 96 LDSymbol* input_sym = m_LDSymbolFactory.allocate(); 97 new (input_sym) LDSymbol(); 98 99 // set the relation between input LDSymbol and its ResolveInfo 100 input_sym->setResolveInfo(*resolved_result.info); 101 102 // set up input LDSymbol 103 input_sym->setFragmentRef(pFragmentRef); 104 input_sym->setValue(pValue); 105 106 LDSymbol* output_sym = resolved_result.info->outSymbol(); 107 bool has_output_sym = (NULL != output_sym); 108 if (!resolved_result.existent || !has_output_sym) { 109 // it is a new symbol, the output_sym should be NULL. 110 assert(NULL == output_sym); 111 112 // if it is a new symbol, create a LDSymbol for the output 113 output_sym = m_LDSymbolFactory.allocate(); 114 new (output_sym) LDSymbol(); 115 116 // set up the relation between output LDSymbol and its ResolveInfo 117 output_sym->setResolveInfo(*resolved_result.info); 118 resolved_result.info->setSymPtr(output_sym); 119 } 120 121 if (resolved_result.overriden || !has_output_sym) { 122 // symbol can be overriden only if it exists. 123 assert(output_sym != NULL); 124 125 // should override output LDSymbol 126 output_sym->setFragmentRef(pFragmentRef); 127 output_sym->setValue(pValue); 128 } 129 130 // After symbol resolution, visibility is changed to the most restrict one. 131 // we need to arrange its position in the output symbol . 132 if (pType != ResolveInfo::Section) { 133 if (!has_output_sym) { 134 // We merge sections when reading them. So we do not need to output symbols 135 // with section type 136 137 // No matter the symbol is already in the output or not, add it if it 138 // should be forcefully set local. 139 if (shouldForceLocal(*resolved_result.info)) 140 m_OutputSymbols.forceLocal(*output_sym); 141 else { 142 // the symbol should not be forcefully local. 143 m_OutputSymbols.add(*output_sym); 144 } 145 } 146 else if (resolved_result.overriden) { 147 if (!shouldForceLocal(old_info) || 148 !shouldForceLocal(*resolved_result.info)) { 149 // If the old info and the new info are both forcefully local, then 150 // we should keep the output_sym in forcefully local category. Else, 151 // we should re-sort the output_sym 152 m_OutputSymbols.arrange(*output_sym, old_info); 153 } 154 } 155 } 156 157 return input_sym; 158 } 159 160 /// addSymbolFromDynObj - add a symbol from object file and resolve it 161 /// immediately 162 LDSymbol* MCLinker::addSymbolFromDynObj(const llvm::StringRef& pName, 163 ResolveInfo::Type pType, 164 ResolveInfo::Desc pDesc, 165 ResolveInfo::Binding pBinding, 166 ResolveInfo::SizeType pSize, 167 LDSymbol::ValueType pValue, 168 MCFragmentRef* pFragmentRef, 169 ResolveInfo::Visibility pVisibility) 170 { 171 // We merge sections when reading them. So we do not need symbols with 172 // section type 173 if (pType == ResolveInfo::Section) 174 return NULL; 175 176 // ignore symbols with local binding or that have internal or hidden 177 // visibility 178 if (pBinding == ResolveInfo::Local || 179 pVisibility == ResolveInfo::Internal || 180 pVisibility == ResolveInfo::Hidden) 181 return NULL; 182 183 // A protected symbol in a shared library must be treated as a 184 // normal symbol when viewed from outside the shared library. 185 if (pVisibility == ResolveInfo::Protected) 186 pVisibility = ResolveInfo::Default; 187 188 // insert symbol and resolve it immediately 189 // resolved_result is a triple <resolved_info, existent, override> 190 Resolver::Result resolved_result; 191 m_StrSymPool.insertSymbol(pName, true, pType, pDesc, pBinding, pSize, pVisibility, 192 NULL, resolved_result); 193 194 // the return ResolveInfo should not NULL 195 assert(NULL != resolved_result.info); 196 197 // create a LDSymbol for the input file. 198 LDSymbol* input_sym = m_LDSymbolFactory.allocate(); 199 new (input_sym) LDSymbol(); 200 201 // set up the relation between input LDSymbol and its ResolveInfo 202 input_sym->setResolveInfo(*resolved_result.info); 203 204 // set up input LDSymbol 205 input_sym->setFragmentRef(pFragmentRef); 206 input_sym->setValue(pValue); 207 208 LDSymbol* output_sym = NULL; 209 if (!resolved_result.existent) { 210 // we get a new symbol, leave it as NULL 211 resolved_result.info->setSymPtr(NULL); 212 } 213 else { 214 // we saw the symbol before, but the output_sym still may be NULL. 215 output_sym = resolved_result.info->outSymbol(); 216 } 217 218 if (output_sym != NULL) { 219 // After symbol resolution, visibility is changed to the most restrict one. 220 // If we are not doing incremental linking, then any symbol with hidden 221 // or internal visibility is forcefully set as a local symbol. 222 if (shouldForceLocal(*resolved_result.info)) { 223 m_OutputSymbols.forceLocal(*output_sym); 224 } 225 } 226 227 return input_sym; 228 } 229 230 /// defineSymbolForcefully - define an output symbol and override it immediately 231 LDSymbol* MCLinker::defineSymbolForcefully(const llvm::StringRef& pName, 232 bool pIsDyn, 233 ResolveInfo::Type pType, 234 ResolveInfo::Desc pDesc, 235 ResolveInfo::Binding pBinding, 236 ResolveInfo::SizeType pSize, 237 LDSymbol::ValueType pValue, 238 MCFragmentRef* pFragmentRef, 239 ResolveInfo::Visibility pVisibility) 240 { 241 ResolveInfo* info = m_StrSymPool.findInfo(pName); 242 LDSymbol* output_sym = NULL; 243 if (NULL == info) { 244 // the symbol is not in the pool, create a new one. 245 // create a ResolveInfo 246 Resolver::Result result; 247 m_StrSymPool.insertSymbol(pName, pIsDyn, pType, pDesc, pBinding, pSize, pVisibility, 248 NULL, result); 249 assert(!result.existent); 250 251 // create a output LDSymbol 252 output_sym = m_LDSymbolFactory.allocate(); 253 new (output_sym) LDSymbol(); 254 255 output_sym->setResolveInfo(*result.info); 256 result.info->setSymPtr(output_sym); 257 258 if (shouldForceLocal(*result.info)) 259 m_OutputSymbols.forceLocal(*output_sym); 260 else 261 m_OutputSymbols.add(*output_sym); 262 } 263 else { 264 // the symbol is already in the pool, override it 265 ResolveInfo old_info; 266 old_info.override(*info); 267 268 info->setSource(pIsDyn); 269 info->setType(pType); 270 info->setDesc(pDesc); 271 info->setBinding(pBinding); 272 info->setVisibility(pVisibility); 273 info->setIsSymbol(true); 274 info->setSize(pSize); 275 276 output_sym = info->outSymbol(); 277 if (NULL != output_sym) 278 m_OutputSymbols.arrange(*output_sym, old_info); 279 else { 280 // create a output LDSymbol 281 output_sym = m_LDSymbolFactory.allocate(); 282 new (output_sym) LDSymbol(); 283 284 output_sym->setResolveInfo(*info); 285 info->setSymPtr(output_sym); 286 287 m_OutputSymbols.add(*output_sym); 288 } 289 } 290 291 if (NULL != output_sym) { 292 output_sym->setFragmentRef(pFragmentRef); 293 output_sym->setValue(pValue); 294 } 295 296 return output_sym; 297 } 298 299 /// defineSymbolAsRefered - define an output symbol and override it immediately 300 LDSymbol* MCLinker::defineSymbolAsRefered(const llvm::StringRef& pName, 301 bool pIsDyn, 302 ResolveInfo::Type pType, 303 ResolveInfo::Desc pDesc, 304 ResolveInfo::Binding pBinding, 305 ResolveInfo::SizeType pSize, 306 LDSymbol::ValueType pValue, 307 MCFragmentRef* pFragmentRef, 308 ResolveInfo::Visibility pVisibility) 309 { 310 ResolveInfo* info = m_StrSymPool.findInfo(pName); 311 312 if (NULL == info || !info->isUndef()) { 313 // only undefined symbol can make a reference. 314 return NULL; 315 } 316 317 // the symbol is already in the pool, override it 318 ResolveInfo old_info; 319 old_info.override(*info); 320 321 info->setSource(pIsDyn); 322 info->setType(pType); 323 info->setDesc(pDesc); 324 info->setBinding(pBinding); 325 info->setVisibility(pVisibility); 326 info->setIsSymbol(true); 327 info->setSize(pSize); 328 329 LDSymbol* output_sym = info->outSymbol(); 330 if (NULL != output_sym) { 331 output_sym->setFragmentRef(pFragmentRef); 332 output_sym->setValue(pValue); 333 m_OutputSymbols.arrange(*output_sym, old_info); 334 } 335 else { 336 // create a output LDSymbol 337 output_sym = m_LDSymbolFactory.allocate(); 338 new (output_sym) LDSymbol(); 339 340 output_sym->setResolveInfo(*info); 341 info->setSymPtr(output_sym); 342 343 m_OutputSymbols.add(*output_sym); 344 } 345 346 return output_sym; 347 } 348 349 /// defineAndResolveSymbolForcefully - define an output symbol and resolve it 350 /// immediately 351 LDSymbol* MCLinker::defineAndResolveSymbolForcefully(const llvm::StringRef& pName, 352 bool pIsDyn, 353 ResolveInfo::Type pType, 354 ResolveInfo::Desc pDesc, 355 ResolveInfo::Binding pBinding, 356 ResolveInfo::SizeType pSize, 357 LDSymbol::ValueType pValue, 358 MCFragmentRef* pFragmentRef, 359 ResolveInfo::Visibility pVisibility) 360 { 361 // Result is <info, existent, override> 362 Resolver::Result result; 363 ResolveInfo old_info; 364 m_StrSymPool.insertSymbol(pName, pIsDyn, pType, pDesc, pBinding, pSize, pVisibility, 365 &old_info, result); 366 367 LDSymbol* output_sym = result.info->outSymbol(); 368 bool has_output_sym = (NULL != output_sym); 369 370 if (!result.existent || !has_output_sym) { 371 output_sym = m_LDSymbolFactory.allocate(); 372 new (output_sym) LDSymbol(); 373 output_sym->setResolveInfo(*result.info); 374 result.info->setSymPtr(output_sym); 375 } 376 377 if (result.overriden || !has_output_sym) { 378 output_sym->setFragmentRef(pFragmentRef); 379 output_sym->setValue(pValue); 380 } 381 382 // After symbol resolution, the visibility is changed to the most restrict. 383 // arrange the output position 384 if (shouldForceLocal(*result.info)) 385 m_OutputSymbols.forceLocal(*output_sym); 386 else if (has_output_sym) 387 m_OutputSymbols.arrange(*output_sym, old_info); 388 else 389 m_OutputSymbols.add(*output_sym); 390 391 return output_sym; 392 } 393 394 /// defineAndResolveSymbolAsRefered - define an output symbol and resolve it 395 /// immediately. 396 LDSymbol* MCLinker::defineAndResolveSymbolAsRefered(const llvm::StringRef& pName, 397 bool pIsDyn, 398 ResolveInfo::Type pType, 399 ResolveInfo::Desc pDesc, 400 ResolveInfo::Binding pBinding, 401 ResolveInfo::SizeType pSize, 402 LDSymbol::ValueType pValue, 403 MCFragmentRef* pFragmentRef, 404 ResolveInfo::Visibility pVisibility) 405 { 406 ResolveInfo* info = m_StrSymPool.findInfo(pName); 407 408 if (NULL == info || !info->isUndef()) { 409 // only undefined symbol can make a reference 410 return NULL; 411 } 412 413 return defineAndResolveSymbolForcefully(pName, 414 pIsDyn, 415 pType, 416 pDesc, 417 pBinding, 418 pSize, 419 pValue, 420 pFragmentRef, 421 pVisibility); 422 } 423 424 /// createSectHdr - create the input section header 425 LDSection& MCLinker::createSectHdr(const std::string& pName, 426 LDFileFormat::Kind pKind, 427 uint32_t pType, 428 uint32_t pFlag) 429 { 430 // for user such as reader, standard/target fromat 431 LDSection* result = 432 m_LDSectHdrFactory.produce(pName, pKind, pType, pFlag); 433 434 // check if we need to create a output section for output LDContext 435 std::string sect_name = m_SectionMap.getOutputSectName(pName); 436 LDSection* output_sect = m_Output.getSection(sect_name); 437 438 if (NULL == output_sect) { 439 // create a output section and push it into output LDContext 440 output_sect = 441 m_LDSectHdrFactory.produce(sect_name, pKind, pType, pFlag); 442 m_Output.getSectionTable().push_back(output_sect); 443 m_SectionMerger.addMapping(pName, output_sect); 444 } 445 return *result; 446 } 447 448 /// getOrCreateOutputSectHdr - for reader and standard/target format to get 449 /// or create the output's section header 450 LDSection& MCLinker::getOrCreateOutputSectHdr(const std::string& pName, 451 LDFileFormat::Kind pKind, 452 uint32_t pType, 453 uint32_t pFlag, 454 uint32_t pAlign) 455 { 456 // check if we need to create a output section for output LDContext 457 std::string sect_name = m_SectionMap.getOutputSectName(pName); 458 LDSection* output_sect = m_Output.getSection(sect_name); 459 460 if (NULL == output_sect) { 461 // create a output section and push it into output LDContext 462 output_sect = 463 m_LDSectHdrFactory.produce(sect_name, pKind, pType, pFlag); 464 output_sect->setAlign(pAlign); 465 m_Output.getSectionTable().push_back(output_sect); 466 m_SectionMerger.addMapping(pName, output_sect); 467 } 468 return *output_sect; 469 } 470 471 /// getOrCreateSectData - get or create MCSectionData 472 /// pSection is input LDSection 473 llvm::MCSectionData& MCLinker::getOrCreateSectData(LDSection& pSection) 474 { 475 // if there is already a section data pointed by section, return it. 476 llvm::MCSectionData* sect_data = pSection.getSectionData(); 477 if (NULL != sect_data) { 478 m_Layout.addInputRange(*sect_data, pSection); 479 return *sect_data; 480 } 481 482 // try to get one from output LDSection 483 LDSection* output_sect = 484 m_SectionMerger.getOutputSectHdr(pSection.name()); 485 486 assert(NULL != output_sect); 487 488 sect_data = output_sect->getSectionData(); 489 490 if (NULL != sect_data) { 491 pSection.setSectionData(sect_data); 492 m_Layout.addInputRange(*sect_data, pSection); 493 return *sect_data; 494 } 495 496 // if the output LDSection also has no MCSectionData, then create one. 497 sect_data = m_LDSectDataFactory.allocate(); 498 new (sect_data) llvm::MCSectionData(*output_sect); 499 pSection.setSectionData(sect_data); 500 output_sect->setSectionData(sect_data); 501 m_Layout.addInputRange(*sect_data, pSection); 502 return *sect_data; 503 } 504 505 /// addRelocation - add a relocation entry in MCLinker (only for object file) 506 /// 507 /// All symbols should be read and resolved before calling this function. 508 Relocation* MCLinker::addRelocation(Relocation::Type pType, 509 const LDSymbol& pSym, 510 ResolveInfo& pResolveInfo, 511 MCFragmentRef& pFragmentRef, 512 Relocation::Address pAddend) 513 { 514 Relocation* relocation = m_Backend.getRelocFactory()->produce(pType, 515 pFragmentRef, 516 pAddend); 517 518 relocation->setSymInfo(&pResolveInfo); 519 520 m_RelocationList.push_back(relocation); 521 522 m_Backend.scanRelocation(*relocation, pSym, *this, m_Info, 523 m_Info.output()); 524 525 return relocation; 526 } 527 528 bool MCLinker::applyRelocations() 529 { 530 RelocationListType::iterator relocIter, relocEnd = m_RelocationList.end(); 531 532 for (relocIter = m_RelocationList.begin(); relocIter != relocEnd; ++relocIter) { 533 llvm::MCFragment* frag = (llvm::MCFragment*)relocIter; 534 static_cast<Relocation*>(frag)->apply(*m_Backend.getRelocFactory(), m_Info); 535 } 536 return true; 537 } 538 539 void MCLinker::syncRelocationResult() 540 { 541 542 m_Info.output().memArea()->clean(); 543 MemoryRegion* region = m_Info.output().memArea()->request(0, 544 m_Info.output().memArea()->size()); 545 546 uint8_t* data = region->getBuffer(); 547 548 RelocationListType::iterator relocIter, relocEnd = m_RelocationList.end(); 549 for (relocIter = m_RelocationList.begin(); relocIter != relocEnd; ++relocIter) { 550 551 llvm::MCFragment* frag = (llvm::MCFragment*)relocIter; 552 Relocation* reloc = static_cast<Relocation*>(frag); 553 554 // get output file offset 555 size_t out_offset = m_Layout.getOutputLDSection(*reloc->targetRef().frag())->offset() + 556 m_Layout.getOutputOffset(reloc->targetRef()); 557 558 uint8_t* target_addr = data + out_offset; 559 // byte swapping if target and host has different endian, and then write back 560 if(llvm::sys::isLittleEndianHost() != m_Backend.isLittleEndian()) { 561 uint64_t tmp_data = 0; 562 563 switch(m_Backend.bitclass()) { 564 case 32u: 565 tmp_data = bswap32(reloc->target()); 566 std::memcpy(target_addr, &tmp_data, 4); 567 break; 568 569 case 64u: 570 tmp_data = bswap64(reloc->target()); 571 std::memcpy(target_addr, &tmp_data, 8); 572 break; 573 574 default: 575 break; 576 } 577 } 578 else { 579 std::memcpy(target_addr, &reloc->target(), m_Backend.bitclass()/8); 580 } 581 } // end of for 582 583 m_Info.output().memArea()->sync(); 584 } 585 586 587 bool MCLinker::layout() 588 { 589 return m_Layout.layout(m_Info.output(), m_Backend); 590 } 591 592 bool MCLinker::finalizeSymbols() 593 { 594 SymbolCategory::iterator symbol, symEnd = m_OutputSymbols.end(); 595 for (symbol = m_OutputSymbols.begin(); symbol != symEnd; ++symbol) { 596 597 if (0x0 != (*symbol)->resolveInfo()->reserved()) { 598 // if the symbol is target reserved, target backend is responsible 599 // for finalizing the value. 600 // if target backend does not know this symbol, it will return false 601 // and we have to take over the symbol. 602 if (m_Backend.finalizeSymbol(**symbol)) 603 continue; 604 } 605 606 if ((*symbol)->resolveInfo()->isAbsolute() || 607 (*symbol)->resolveInfo()->type() == ResolveInfo::File) { 608 // absolute symbols and symbols with function type should have 609 // zero value 610 (*symbol)->setValue(0x0); 611 continue; 612 } 613 614 if ((*symbol)->hasFragRef()) { 615 // set the virtual address of the symbol. If the output file is 616 // relocatable object file, the section's virtual address becomes zero. 617 // And the symbol's value become section relative offset. 618 uint64_t value = getLayout().getOutputOffset(*(*symbol)->fragRef()); 619 assert(NULL != (*symbol)->fragRef()->frag()); 620 uint64_t addr = getLayout().getOutputLDSection(*(*symbol)->fragRef()->frag())->addr(); 621 (*symbol)->setValue(value + addr); 622 continue; 623 } 624 } 625 626 return true; 627 } 628 629 bool MCLinker::shouldForceLocal(const ResolveInfo& pInfo) const 630 { 631 // forced local symbol matches all rules: 632 // 1. We are not doing incremental linking. 633 // 2. The symbol is with Hidden or Internal visibility. 634 // 3. The symbol should be global or weak. Otherwise, local symbol is local. 635 // 4. The symbol is defined or common 636 if (m_Info.output().type() != Output::Object && 637 (pInfo.visibility() == ResolveInfo::Hidden || 638 pInfo.visibility() == ResolveInfo::Internal) && 639 (pInfo.isGlobal() || pInfo.isWeak()) && 640 (pInfo.isDefine() || pInfo.isCommon())) 641 return true; 642 return false; 643 } 644 645