1//===- ObjectLinker.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#include "mcld/Object/ObjectLinker.h"
10
11#include "mcld/InputTree.h"
12#include "mcld/IRBuilder.h"
13#include "mcld/LinkerConfig.h"
14#include "mcld/LinkerScript.h"
15#include "mcld/Module.h"
16#include "mcld/Fragment/Relocation.h"
17#include "mcld/LD/Archive.h"
18#include "mcld/LD/ArchiveReader.h"
19#include "mcld/LD/BinaryReader.h"
20#include "mcld/LD/BranchIslandFactory.h"
21#include "mcld/LD/DebugString.h"
22#include "mcld/LD/DynObjReader.h"
23#include "mcld/LD/GarbageCollection.h"
24#include "mcld/LD/GroupReader.h"
25#include "mcld/LD/IdenticalCodeFolding.h"
26#include "mcld/LD/LDContext.h"
27#include "mcld/LD/LDSection.h"
28#include "mcld/LD/ObjectReader.h"
29#include "mcld/LD/ObjectWriter.h"
30#include "mcld/LD/Relocator.h"
31#include "mcld/LD/RelocData.h"
32#include "mcld/LD/ResolveInfo.h"
33#include "mcld/LD/SectionData.h"
34#include "mcld/Object/ObjectBuilder.h"
35#include "mcld/Script/Assignment.h"
36#include "mcld/Script/Operand.h"
37#include "mcld/Script/RpnEvaluator.h"
38#include "mcld/Script/ScriptFile.h"
39#include "mcld/Script/ScriptReader.h"
40#include "mcld/Support/FileOutputBuffer.h"
41#include "mcld/Support/MsgHandling.h"
42#include "mcld/Support/RealPath.h"
43#include "mcld/Target/TargetLDBackend.h"
44
45#include <llvm/Support/Casting.h>
46#include <llvm/Support/Host.h>
47
48#include <system_error>
49
50namespace mcld {
51
52//===----------------------------------------------------------------------===//
53// ObjectLinker
54//===----------------------------------------------------------------------===//
55ObjectLinker::ObjectLinker(const LinkerConfig& pConfig,
56                           TargetLDBackend& pLDBackend)
57    : m_Config(pConfig),
58      m_pModule(NULL),
59      m_pBuilder(NULL),
60      m_LDBackend(pLDBackend),
61      m_pObjectReader(NULL),
62      m_pDynObjReader(NULL),
63      m_pArchiveReader(NULL),
64      m_pGroupReader(NULL),
65      m_pBinaryReader(NULL),
66      m_pScriptReader(NULL),
67      m_pWriter(NULL) {
68}
69
70ObjectLinker::~ObjectLinker() {
71  delete m_pObjectReader;
72  delete m_pDynObjReader;
73  delete m_pArchiveReader;
74  delete m_pGroupReader;
75  delete m_pBinaryReader;
76  delete m_pScriptReader;
77  delete m_pWriter;
78}
79
80bool ObjectLinker::initialize(Module& pModule, IRBuilder& pBuilder) {
81  m_pModule = &pModule;
82  m_pBuilder = &pBuilder;
83
84  // initialize the readers and writers
85  m_pObjectReader = m_LDBackend.createObjectReader(*m_pBuilder);
86  m_pArchiveReader = m_LDBackend.createArchiveReader(*m_pModule);
87  m_pDynObjReader = m_LDBackend.createDynObjReader(*m_pBuilder);
88  m_pBinaryReader = m_LDBackend.createBinaryReader(*m_pBuilder);
89  m_pGroupReader = new GroupReader(*m_pModule,
90                                   *m_pObjectReader,
91                                   *m_pDynObjReader,
92                                   *m_pArchiveReader,
93                                   *m_pBinaryReader);
94  m_pScriptReader = new ScriptReader(
95      *m_pObjectReader, *m_pArchiveReader, *m_pDynObjReader, *m_pGroupReader);
96  m_pWriter = m_LDBackend.createWriter();
97
98  // initialize Relocator
99  m_LDBackend.initRelocator();
100
101  return true;
102}
103
104/// initStdSections - initialize standard sections
105bool ObjectLinker::initStdSections() {
106  ObjectBuilder builder(*m_pModule);
107
108  // initialize standard sections
109  if (!m_LDBackend.initStdSections(builder))
110    return false;
111
112  // initialize target-dependent sections
113  m_LDBackend.initTargetSections(*m_pModule, builder);
114
115  return true;
116}
117
118void ObjectLinker::addUndefinedSymbols() {
119  // Add the symbol set by -u as an undefind global symbol into symbol pool
120  GeneralOptions::const_undef_sym_iterator usym;
121  GeneralOptions::const_undef_sym_iterator usymEnd =
122      m_Config.options().undef_sym_end();
123  for (usym = m_Config.options().undef_sym_begin(); usym != usymEnd; ++usym) {
124    Resolver::Result result;
125    m_pModule->getNamePool().insertSymbol(*usym,  // name
126                                          false,  // isDyn
127                                          ResolveInfo::NoType,
128                                          ResolveInfo::Undefined,
129                                          ResolveInfo::Global,
130                                          0x0,  // size
131                                          0x0,  // value
132                                          ResolveInfo::Default,
133                                          NULL,
134                                          result);
135
136    LDSymbol* output_sym = result.info->outSymbol();
137    // create the output symbol if it dose not have one
138    if (!result.existent || (output_sym != NULL)) {
139      output_sym = LDSymbol::Create(*result.info);
140      result.info->setSymPtr(output_sym);
141      output_sym->setFragmentRef(FragmentRef::Null());
142    }
143  }
144}
145
146void ObjectLinker::normalize() {
147  // -----  set up inputs  ----- //
148  Module::input_iterator input, inEnd = m_pModule->input_end();
149  for (input = m_pModule->input_begin(); input != inEnd; ++input) {
150    // is a group node
151    if (isGroup(input)) {
152      getGroupReader()->readGroup(
153          input, inEnd, m_pBuilder->getInputBuilder(), m_Config);
154      continue;
155    }
156
157    // already got type - for example, bitcode or external OIR (object
158    // intermediate representation)
159    if ((*input)->type() == Input::Script ||
160        (*input)->type() == Input::Archive ||
161        (*input)->type() == Input::External)
162      continue;
163
164    if (Input::Object == (*input)->type()) {
165      m_pModule->getObjectList().push_back(*input);
166      continue;
167    }
168
169    if (Input::DynObj == (*input)->type()) {
170      m_pModule->getLibraryList().push_back(*input);
171      continue;
172    }
173
174    bool doContinue = false;
175    // read input as a binary file
176    if (getBinaryReader()->isMyFormat(**input, doContinue)) {
177      (*input)->setType(Input::Object);
178      getBinaryReader()->readBinary(**input);
179      m_pModule->getObjectList().push_back(*input);
180    } else if (doContinue &&
181               getObjectReader()->isMyFormat(**input, doContinue)) {
182      // is a relocatable object file
183      (*input)->setType(Input::Object);
184      getObjectReader()->readHeader(**input);
185      getObjectReader()->readSections(**input);
186      getObjectReader()->readSymbols(**input);
187      m_pModule->getObjectList().push_back(*input);
188    } else if (doContinue &&
189               getDynObjReader()->isMyFormat(**input, doContinue)) {
190      // is a shared object file
191      (*input)->setType(Input::DynObj);
192      getDynObjReader()->readHeader(**input);
193      getDynObjReader()->readSymbols(**input);
194      m_pModule->getLibraryList().push_back(*input);
195    } else if (doContinue &&
196               getArchiveReader()->isMyFormat(**input, doContinue)) {
197      // is an archive
198      (*input)->setType(Input::Archive);
199      if (m_Config.options().isInExcludeLIBS(**input)) {
200        (*input)->setNoExport();
201      }
202      Archive archive(**input, m_pBuilder->getInputBuilder());
203      getArchiveReader()->readArchive(m_Config, archive);
204      if (archive.numOfObjectMember() > 0) {
205        m_pModule->getInputTree().merge<InputTree::Inclusive>(input,
206                                                              archive.inputs());
207      }
208    } else if (doContinue &&
209               getScriptReader()->isMyFormat(**input, doContinue)) {
210      // try to parse input as a linker script
211      ScriptFile script(
212          ScriptFile::LDScript, **input, m_pBuilder->getInputBuilder());
213      if (getScriptReader()->readScript(m_Config, script)) {
214        (*input)->setType(Input::Script);
215        script.activate(*m_pModule);
216        if (script.inputs().size() > 0) {
217          m_pModule->getInputTree().merge<InputTree::Inclusive>(
218              input, script.inputs());
219        }
220      }
221    } else {
222      if (m_Config.options().warnMismatch())
223        warning(diag::warn_unrecognized_input_file)
224            << (*input)->path() << m_Config.targets().triple().str();
225    }
226  }  // end of for
227}
228
229bool ObjectLinker::linkable() const {
230  // check we have input and output files
231  if (m_pModule->getInputTree().empty()) {
232    error(diag::err_no_inputs);
233    return false;
234  }
235
236  // can not mix -static with shared objects
237  Module::const_lib_iterator lib, libEnd = m_pModule->lib_end();
238  for (lib = m_pModule->lib_begin(); lib != libEnd; ++lib) {
239    if ((*lib)->attribute()->isStatic()) {
240      error(diag::err_mixed_shared_static_objects) << (*lib)->name()
241                                                   << (*lib)->path();
242      return false;
243    }
244  }
245
246  // --nmagic and --omagic options lead to static executable program.
247  // These options turn off page alignment of sections. Because the
248  // sections are not aligned to pages, these sections can not contain any
249  // exported functions. Also, because the two options disable linking
250  // against shared libraries, the output absolutely does not call outside
251  // functions.
252  if (m_Config.options().nmagic() && !m_Config.isCodeStatic()) {
253    error(diag::err_nmagic_not_static);
254    return false;
255  }
256  if (m_Config.options().omagic() && !m_Config.isCodeStatic()) {
257    error(diag::err_omagic_not_static);
258    return false;
259  }
260
261  return true;
262}
263
264void ObjectLinker::dataStrippingOpt() {
265  if (m_Config.codeGenType() == LinkerConfig::Object) {
266    return;
267  }
268
269  // Garbege collection
270  if (m_Config.options().GCSections()) {
271    GarbageCollection GC(m_Config, m_LDBackend, *m_pModule);
272    GC.run();
273  }
274
275  // Identical code folding
276  if (m_Config.options().getICFMode() != GeneralOptions::ICF::None) {
277    IdenticalCodeFolding icf(m_Config, m_LDBackend, *m_pModule);
278    icf.foldIdenticalCode();
279  }
280  return;
281}
282
283/// readRelocations - read all relocation entries
284///
285/// All symbols should be read and resolved before this function.
286bool ObjectLinker::readRelocations() {
287  // Bitcode is read by the other path. This function reads relocation sections
288  // in object files.
289  mcld::InputTree::bfs_iterator input,
290      inEnd = m_pModule->getInputTree().bfs_end();
291  for (input = m_pModule->getInputTree().bfs_begin(); input != inEnd; ++input) {
292    if ((*input)->type() == Input::Object && (*input)->hasMemArea()) {
293      if (!getObjectReader()->readRelocations(**input))
294        return false;
295    }
296    // ignore the other kinds of files.
297  }
298  return true;
299}
300
301/// mergeSections - put allinput sections into output sections
302bool ObjectLinker::mergeSections() {
303  // run the target-dependent hooks before merging sections
304  m_LDBackend.preMergeSections(*m_pModule);
305
306  // Set up input/output from ldscript requirement if any
307  {
308    RpnEvaluator evaluator(*m_pModule, m_LDBackend);
309    SectionMap::iterator out, outBegin, outEnd;
310    outBegin = m_pModule->getScript().sectionMap().begin();
311    outEnd = m_pModule->getScript().sectionMap().end();
312    for (out = outBegin; out != outEnd; ++out) {
313      uint64_t out_align = 0x0, in_align = 0x0;
314      LDSection* out_sect = (*out)->getSection();
315      SectionMap::Output::iterator in, inBegin, inEnd;
316      inBegin = (*out)->begin();
317      inEnd = (*out)->end();
318
319      // force input alignment from ldscript if any
320      if ((*out)->prolog().hasSubAlign()) {
321        evaluator.eval((*out)->prolog().subAlign(), in_align);
322      }
323
324      for (in = inBegin; in != inEnd; ++in) {
325        LDSection* in_sect = (*in)->getSection();
326        if ((*out)->prolog().hasSubAlign())
327          in_sect->setAlign(in_align);
328      }  // for each input section description
329
330      // force output alignment from ldscript if any
331      if ((*out)->prolog().hasAlign()) {
332        evaluator.eval((*out)->prolog().align(), out_align);
333        out_sect->setAlign(out_align);
334      }
335    }  // for each output section description
336  }
337
338  ObjectBuilder builder(*m_pModule);
339  Module::obj_iterator obj, objEnd = m_pModule->obj_end();
340  for (obj = m_pModule->obj_begin(); obj != objEnd; ++obj) {
341    LDContext::sect_iterator sect, sectEnd = (*obj)->context()->sectEnd();
342    for (sect = (*obj)->context()->sectBegin(); sect != sectEnd; ++sect) {
343      switch ((*sect)->kind()) {
344        // Some *INPUT sections should not be merged.
345        case LDFileFormat::Folded:
346        case LDFileFormat::Ignore:
347        case LDFileFormat::Null:
348        case LDFileFormat::NamePool:
349        case LDFileFormat::Group:
350        case LDFileFormat::StackNote:
351          // skip
352          continue;
353        case LDFileFormat::Relocation:
354          if (!(*sect)->hasRelocData())
355            continue;  // skip
356
357          if ((*sect)->getLink()->kind() == LDFileFormat::Ignore ||
358              (*sect)->getLink()->kind() == LDFileFormat::Folded)
359            (*sect)->setKind(LDFileFormat::Ignore);
360          break;
361        case LDFileFormat::Target:
362          if (!m_LDBackend.mergeSection(*m_pModule, **obj, **sect)) {
363            error(diag::err_cannot_merge_section) << (*sect)->name()
364                                                  << (*obj)->name();
365            return false;
366          }
367          break;
368        case LDFileFormat::EhFrame: {
369          if (!(*sect)->hasEhFrame())
370            continue;  // skip
371
372          LDSection* out_sect = NULL;
373          if ((out_sect = builder.MergeSection(**obj, **sect)) != NULL) {
374            if (!m_LDBackend.updateSectionFlags(*out_sect, **sect)) {
375              error(diag::err_cannot_merge_section) << (*sect)->name()
376                                                    << (*obj)->name();
377              return false;
378            }
379          }
380          break;
381        }
382        case LDFileFormat::DebugString: {
383          // FIXME: disable debug string merge when doing partial link.
384          if (LinkerConfig::Object == m_Config.codeGenType())
385            (*sect)->setKind(LDFileFormat::Debug);
386        }
387        // Fall through
388        default: {
389          if (!(*sect)->hasSectionData())
390            continue;  // skip
391
392          LDSection* out_sect = NULL;
393          if ((out_sect = builder.MergeSection(**obj, **sect)) != NULL) {
394            if (!m_LDBackend.updateSectionFlags(*out_sect, **sect)) {
395              error(diag::err_cannot_merge_section) << (*sect)->name()
396                                                    << (*obj)->name();
397              return false;
398            }
399          }
400          break;
401        }
402      }  // end of switch
403    }    // for each section
404  }      // for each obj
405
406  {
407    SectionMap::iterator out, outBegin, outEnd;
408    outBegin = m_pModule->getScript().sectionMap().begin();
409    outEnd = m_pModule->getScript().sectionMap().end();
410    for (out = outBegin; out != outEnd; ++out) {
411      LDSection* out_sect = (*out)->getSection();
412      SectionMap::Output::iterator in, inBegin, inEnd;
413      inBegin = (*out)->begin();
414      inEnd = (*out)->end();
415
416      for (in = inBegin; in != inEnd; ++in) {
417        LDSection* in_sect = (*in)->getSection();
418        if (builder.MoveSectionData(*in_sect->getSectionData(),
419                                    *out_sect->getSectionData())) {
420          builder.UpdateSectionAlign(*out_sect, *in_sect);
421          m_LDBackend.updateSectionFlags(*out_sect, *in_sect);
422        }
423      }  // for each input section description
424
425      if ((*out)->hasContent()) {
426        LDSection* target = m_pModule->getSection((*out)->name());
427        assert(target != NULL && target->hasSectionData());
428        if (builder.MoveSectionData(*out_sect->getSectionData(),
429                                    *target->getSectionData())) {
430          builder.UpdateSectionAlign(*target, *out_sect);
431          m_LDBackend.updateSectionFlags(*target, *out_sect);
432        }
433      }
434    }  // for each output section description
435  }
436
437  // run the target-dependent hooks after merging sections
438  m_LDBackend.postMergeSections(*m_pModule);
439
440  return true;
441}
442
443void ObjectLinker::addSymbolToOutput(ResolveInfo& pInfo, Module& pModule) {
444  // section symbols will be defined by linker later, we should not add section
445  // symbols to output here
446  if (ResolveInfo::Section == pInfo.type() || pInfo.outSymbol() == NULL)
447    return;
448
449  // if the symbols defined in the Ignore sections (e.g. discared by GC), then
450  // not to put them to output
451  // make sure that symbols defined in .debug_str won't add into output
452  // symbol table. Since these symbols has fragRef to input fragments, which
453  // will refer to input LDSection and has bad result when emitting their
454  // section index. However, .debug_str actually does not need symobl in
455  // shrad/executable objects, so it's fine to do so.
456  if (pInfo.outSymbol()->hasFragRef() &&
457      (LDFileFormat::Ignore ==
458           pInfo.outSymbol()
459               ->fragRef()
460               ->frag()
461               ->getParent()
462               ->getSection()
463               .kind() ||
464       LDFileFormat::DebugString ==
465           pInfo.outSymbol()
466               ->fragRef()
467               ->frag()
468               ->getParent()
469               ->getSection()
470               .kind()))
471    return;
472
473  if (pInfo.shouldForceLocal(m_Config))
474    pModule.getSymbolTable().forceLocal(*pInfo.outSymbol());
475  else
476    pModule.getSymbolTable().add(*pInfo.outSymbol());
477}
478
479void ObjectLinker::addSymbolsToOutput(Module& pModule) {
480  // Traverse all the free ResolveInfo and add the output symobols to output
481  NamePool::freeinfo_iterator free_it,
482      free_end = pModule.getNamePool().freeinfo_end();
483  for (free_it = pModule.getNamePool().freeinfo_begin(); free_it != free_end;
484       ++free_it)
485    addSymbolToOutput(**free_it, pModule);
486
487  // Traverse all the resolveInfo and add the output symbol to output
488  NamePool::syminfo_iterator info_it,
489      info_end = pModule.getNamePool().syminfo_end();
490  for (info_it = pModule.getNamePool().syminfo_begin(); info_it != info_end;
491       ++info_it)
492    addSymbolToOutput(*info_it.getEntry(), pModule);
493}
494
495/// addStandardSymbols - shared object and executable files need some
496/// standard symbols
497///   @return if there are some input symbols with the same name to the
498///   standard symbols, return false
499bool ObjectLinker::addStandardSymbols() {
500  // create and add section symbols for each output section
501  Module::iterator iter, iterEnd = m_pModule->end();
502  for (iter = m_pModule->begin(); iter != iterEnd; ++iter) {
503    m_pModule->getSectionSymbolSet().add(**iter, m_pModule->getNamePool());
504  }
505
506  return m_LDBackend.initStandardSymbols(*m_pBuilder, *m_pModule);
507}
508
509/// addTargetSymbols - some targets, such as MIPS and ARM, need some
510/// target-dependent symbols
511///   @return if there are some input symbols with the same name to the
512///   target symbols, return false
513bool ObjectLinker::addTargetSymbols() {
514  m_LDBackend.initTargetSymbols(*m_pBuilder, *m_pModule);
515  return true;
516}
517
518/// addScriptSymbols - define symbols from the command line option or linker
519/// scripts.
520bool ObjectLinker::addScriptSymbols() {
521  LinkerScript& script = m_pModule->getScript();
522  LinkerScript::Assignments::iterator it, ie = script.assignments().end();
523  // go through the entire symbol assignments
524  for (it = script.assignments().begin(); it != ie; ++it) {
525    LDSymbol* symbol = NULL;
526    assert((*it).second.symbol().type() == Operand::SYMBOL);
527    const llvm::StringRef symName = (*it).second.symbol().name();
528    ResolveInfo::Type type = ResolveInfo::NoType;
529    ResolveInfo::Visibility vis = ResolveInfo::Default;
530    size_t size = 0;
531    ResolveInfo* old_info = m_pModule->getNamePool().findInfo(symName);
532    // if the symbol does not exist, we can set type to NOTYPE
533    // else we retain its type, same goes for size - 0 or retain old value
534    // and visibility - Default or retain
535    if (old_info != NULL) {
536      type = static_cast<ResolveInfo::Type>(old_info->type());
537      vis = old_info->visibility();
538      size = old_info->size();
539    }
540
541    // Add symbol and refine the visibility if needed
542    // FIXME: bfd linker would change the binding instead, but currently
543    //        ABS is also a kind of Binding in ResolveInfo.
544    switch ((*it).second.type()) {
545      case Assignment::HIDDEN:
546        vis = ResolveInfo::Hidden;
547      // Fall through
548      case Assignment::DEFAULT:
549        symbol = m_pBuilder->AddSymbol<IRBuilder::Force, IRBuilder::Unresolve>(
550            symName,
551            type,
552            ResolveInfo::Define,
553            ResolveInfo::Absolute,
554            size,
555            0x0,
556            FragmentRef::Null(),
557            vis);
558        break;
559      case Assignment::PROVIDE_HIDDEN:
560        vis = ResolveInfo::Hidden;
561      // Fall through
562      case Assignment::PROVIDE:
563        symbol =
564            m_pBuilder->AddSymbol<IRBuilder::AsReferred, IRBuilder::Unresolve>(
565                symName,
566                type,
567                ResolveInfo::Define,
568                ResolveInfo::Absolute,
569                size,
570                0x0,
571                FragmentRef::Null(),
572                vis);
573        break;
574    }
575    // Set symbol of this assignment.
576    (*it).first = symbol;
577  }
578  return true;
579}
580
581bool ObjectLinker::scanRelocations() {
582  // apply all relocations of all inputs
583  Module::obj_iterator input, inEnd = m_pModule->obj_end();
584  for (input = m_pModule->obj_begin(); input != inEnd; ++input) {
585    m_LDBackend.getRelocator()->initializeScan(**input);
586    LDContext::sect_iterator rs, rsEnd = (*input)->context()->relocSectEnd();
587    for (rs = (*input)->context()->relocSectBegin(); rs != rsEnd; ++rs) {
588      // bypass the reloc section if
589      // 1. its section kind is changed to Ignore. (The target section is a
590      // discarded group section.)
591      // 2. it has no reloc data. (All symbols in the input relocs are in the
592      // discarded group sections)
593      if (LDFileFormat::Ignore == (*rs)->kind() || !(*rs)->hasRelocData())
594        continue;
595      RelocData::iterator reloc, rEnd = (*rs)->getRelocData()->end();
596      for (reloc = (*rs)->getRelocData()->begin(); reloc != rEnd; ++reloc) {
597        Relocation* relocation = llvm::cast<Relocation>(reloc);
598
599        // bypass the reloc if the symbol is in the discarded input section
600        ResolveInfo* info = relocation->symInfo();
601        if (!info->outSymbol()->hasFragRef() &&
602            ResolveInfo::Section == info->type() &&
603            ResolveInfo::Undefined == info->desc())
604          continue;
605
606        // scan relocation
607        if (LinkerConfig::Object != m_Config.codeGenType()) {
608          m_LDBackend.getRelocator()->scanRelocation(
609              *relocation, *m_pBuilder, *m_pModule, **rs, **input);
610        } else {
611          m_LDBackend.getRelocator()->partialScanRelocation(
612              *relocation, *m_pModule);
613        }
614      }  // for all relocations
615    }    // for all relocation section
616    m_LDBackend.getRelocator()->finalizeScan(**input);
617  }  // for all inputs
618  return true;
619}
620
621/// initStubs - initialize stub-related stuff.
622bool ObjectLinker::initStubs() {
623  // initialize BranchIslandFactory
624  m_LDBackend.initBRIslandFactory();
625
626  // initialize StubFactory
627  m_LDBackend.initStubFactory();
628
629  // initialize target stubs
630  m_LDBackend.initTargetStubs();
631  return true;
632}
633
634/// allocateCommonSymobols - allocate fragments for common symbols to the
635/// corresponding sections
636bool ObjectLinker::allocateCommonSymbols() {
637  if (LinkerConfig::Object != m_Config.codeGenType() ||
638      m_Config.options().isDefineCommon())
639    return m_LDBackend.allocateCommonSymbols(*m_pModule);
640  return true;
641}
642
643/// prelayout - help backend to do some modification before layout
644bool ObjectLinker::prelayout() {
645  // finalize the section symbols, set their fragment reference and push them
646  // into output symbol table
647  Module::iterator sect, sEnd = m_pModule->end();
648  for (sect = m_pModule->begin(); sect != sEnd; ++sect) {
649    m_pModule->getSectionSymbolSet().finalize(
650        **sect,
651        m_pModule->getSymbolTable(),
652        m_Config.codeGenType() == LinkerConfig::Object);
653  }
654
655  m_LDBackend.preLayout(*m_pModule, *m_pBuilder);
656
657  /// check program interpreter - computer the name size of the runtime dyld
658  if (!m_Config.isCodeStatic() &&
659      (LinkerConfig::Exec == m_Config.codeGenType() ||
660       m_Config.options().isPIE() || m_Config.options().hasDyld()))
661    m_LDBackend.sizeInterp();
662
663  /// measure NamePools - compute the size of name pool sections
664  /// In ELF, will compute  the size of.symtab, .strtab, .dynsym, .dynstr,
665  /// .hash and .shstrtab sections.
666  ///
667  /// dump all symbols and strings from ObjectLinker and build the
668  /// format-dependent
669  /// hash table.
670  /// @note sizeNamePools replies on LinkerConfig::CodePosition. Must determine
671  /// code position model before calling GNULDBackend::sizeNamePools()
672  m_LDBackend.sizeNamePools(*m_pModule);
673
674  // Do this after backend prelayout since it may add eh_frame entries.
675  LDSection* eh_frame_sect = m_pModule->getSection(".eh_frame");
676  if (eh_frame_sect && eh_frame_sect->hasEhFrame())
677    eh_frame_sect->getEhFrame()->computeOffsetSize();
678  m_LDBackend.createAndSizeEhFrameHdr(*m_pModule);
679
680  // size debug string table and set up the debug string offset
681  // we set the .debug_str size here so that there won't be a section symbol for
682  // .debug_str. While actually it doesn't matter that .debug_str has section
683  // symbol or not.
684  // FIXME: disable debug string merge when doing partial link.
685  if (LinkerConfig::Object != m_Config.codeGenType()) {
686    LDSection* debug_str_sect = m_pModule->getSection(".debug_str");
687    if (debug_str_sect && debug_str_sect->hasDebugString())
688      debug_str_sect->getDebugString()->computeOffsetSize();
689  }
690  return true;
691}
692
693/// layout - linearly layout all output sections and reserve some space
694/// for GOT/PLT
695///   Because we do not support instruction relaxing in this early version,
696///   if there is a branch can not jump to its target, we return false
697///   directly
698bool ObjectLinker::layout() {
699  m_LDBackend.layout(*m_pModule);
700  return true;
701}
702
703/// prelayout - help backend to do some modification after layout
704bool ObjectLinker::postlayout() {
705  m_LDBackend.postLayout(*m_pModule, *m_pBuilder);
706  return true;
707}
708
709/// finalizeSymbolValue - finalize the resolved symbol value.
710///   Before relocate(), after layout(), ObjectLinker should correct value of
711///   all
712///   symbol.
713bool ObjectLinker::finalizeSymbolValue() {
714  Module::sym_iterator symbol, symEnd = m_pModule->sym_end();
715  for (symbol = m_pModule->sym_begin(); symbol != symEnd; ++symbol) {
716    if ((*symbol)->resolveInfo()->isAbsolute() ||
717        (*symbol)->resolveInfo()->type() == ResolveInfo::File) {
718      // absolute symbols should just use its value directly (i.e., the result
719      // of symbol resolution)
720      continue;
721    }
722
723    if ((*symbol)->resolveInfo()->type() == ResolveInfo::ThreadLocal) {
724      m_LDBackend.finalizeTLSSymbol(**symbol);
725      continue;
726    }
727
728    if ((*symbol)->hasFragRef()) {
729      // set the virtual address of the symbol. If the output file is
730      // relocatable object file, the section's virtual address becomes zero.
731      // And the symbol's value become section relative offset.
732      uint64_t value = (*symbol)->fragRef()->getOutputOffset();
733      assert((*symbol)->fragRef()->frag() != NULL);
734      uint64_t addr =
735          (*symbol)->fragRef()->frag()->getParent()->getSection().addr();
736      (*symbol)->setValue(value + addr);
737      continue;
738    }
739  }
740
741  RpnEvaluator evaluator(*m_pModule, m_LDBackend);
742  bool finalized = m_LDBackend.finalizeSymbols();
743  bool scriptSymsFinalized = true;
744  LinkerScript& script = m_pModule->getScript();
745  LinkerScript::Assignments::iterator assign, assignEnd;
746  assignEnd = script.assignments().end();
747  for (assign = script.assignments().begin(); assign != assignEnd; ++assign) {
748    LDSymbol* symbol = (*assign).first;
749    Assignment& assignment = (*assign).second;
750
751    if (symbol == NULL)
752      continue;
753
754    scriptSymsFinalized &= assignment.assign(evaluator);
755    if (!scriptSymsFinalized)
756      break;
757
758    symbol->setValue(assignment.symbol().value());
759  }  // for each script symbol assignment
760
761  bool assertionsPassed = true;
762  LinkerScript::Assertions::iterator assert, assertEnd;
763  assertEnd = script.assertions().end();
764  for (assert = script.assertions().begin(); assert != assertEnd; ++assert) {
765    uint64_t res = 0x0;
766    evaluator.eval((*assert).getRpnExpr(), res);
767    if (res == 0x0)
768      fatal(diag::err_assert_failed) << (*assert).message();
769  }  // for each assertion in ldscript
770
771  return finalized && scriptSymsFinalized && assertionsPassed;
772}
773
774/// relocate - applying relocation entries and create relocation
775/// section in the output files
776/// Create relocation section, asking TargetLDBackend to
777/// read the relocation information into RelocationEntry
778/// and push_back into the relocation section
779bool ObjectLinker::relocation() {
780  // when producing relocatables, no need to apply relocation
781  if (LinkerConfig::Object == m_Config.codeGenType())
782    return true;
783
784  LDSection* debug_str_sect = m_pModule->getSection(".debug_str");
785
786  // apply all relocations of all inputs
787  Module::obj_iterator input, inEnd = m_pModule->obj_end();
788  for (input = m_pModule->obj_begin(); input != inEnd; ++input) {
789    m_LDBackend.getRelocator()->initializeApply(**input);
790    LDContext::sect_iterator rs, rsEnd = (*input)->context()->relocSectEnd();
791    for (rs = (*input)->context()->relocSectBegin(); rs != rsEnd; ++rs) {
792      // bypass the reloc section if
793      // 1. its section kind is changed to Ignore. (The target section is a
794      // discarded group section.)
795      // 2. it has no reloc data. (All symbols in the input relocs are in the
796      // discarded group sections)
797      if (LDFileFormat::Ignore == (*rs)->kind() || !(*rs)->hasRelocData())
798        continue;
799      RelocData::iterator reloc, rEnd = (*rs)->getRelocData()->end();
800      for (reloc = (*rs)->getRelocData()->begin(); reloc != rEnd; ++reloc) {
801        Relocation* relocation = llvm::cast<Relocation>(reloc);
802
803        // bypass the reloc if the symbol is in the discarded input section
804        ResolveInfo* info = relocation->symInfo();
805        if (!info->outSymbol()->hasFragRef() &&
806            ResolveInfo::Section == info->type() &&
807            ResolveInfo::Undefined == info->desc())
808          continue;
809
810        // apply the relocation aginst symbol on DebugString
811        if (info->outSymbol()->hasFragRef() &&
812            info->outSymbol()->fragRef()->frag()->getKind()
813                == Fragment::Region &&
814            info->outSymbol()->fragRef()->frag()->getParent()->getSection()
815                .kind() == LDFileFormat::DebugString) {
816          assert(debug_str_sect != NULL);
817          assert(debug_str_sect->hasDebugString());
818          debug_str_sect->getDebugString()->applyOffset(*relocation,
819                                                        m_LDBackend);
820          continue;
821        }
822
823        relocation->apply(*m_LDBackend.getRelocator());
824      }  // for all relocations
825    }    // for all relocation section
826    m_LDBackend.getRelocator()->finalizeApply(**input);
827  }  // for all inputs
828
829  // apply relocations created by relaxation
830  BranchIslandFactory* br_factory = m_LDBackend.getBRIslandFactory();
831  BranchIslandFactory::iterator facIter, facEnd = br_factory->end();
832  for (facIter = br_factory->begin(); facIter != facEnd; ++facIter) {
833    BranchIsland& island = *facIter;
834    BranchIsland::reloc_iterator iter, iterEnd = island.reloc_end();
835    for (iter = island.reloc_begin(); iter != iterEnd; ++iter)
836      (*iter)->apply(*m_LDBackend.getRelocator());
837  }
838
839  // apply relocations created by LD backend
840  for (TargetLDBackend::extra_reloc_iterator
841       iter = m_LDBackend.extra_reloc_begin(),
842       end = m_LDBackend.extra_reloc_end(); iter != end; ++iter) {
843    iter->apply(*m_LDBackend.getRelocator());
844  }
845
846  return true;
847}
848
849/// emitOutput - emit the output file.
850bool ObjectLinker::emitOutput(FileOutputBuffer& pOutput) {
851  return std::error_code() == getWriter()->writeObject(*m_pModule, pOutput);
852}
853
854/// postProcessing - do modification after all processes
855bool ObjectLinker::postProcessing(FileOutputBuffer& pOutput) {
856  if (LinkerConfig::Object != m_Config.codeGenType())
857    normalSyncRelocationResult(pOutput);
858  else
859    partialSyncRelocationResult(pOutput);
860
861  // emit .eh_frame_hdr
862  // eh_frame_hdr should be emitted after syncRelocation, because eh_frame_hdr
863  // needs FDE PC value, which will be corrected at syncRelocation
864  m_LDBackend.postProcessing(pOutput);
865  return true;
866}
867
868void ObjectLinker::normalSyncRelocationResult(FileOutputBuffer& pOutput) {
869  uint8_t* data = pOutput.getBufferStart();
870
871  // sync all relocations of all inputs
872  Module::obj_iterator input, inEnd = m_pModule->obj_end();
873  for (input = m_pModule->obj_begin(); input != inEnd; ++input) {
874    LDContext::sect_iterator rs, rsEnd = (*input)->context()->relocSectEnd();
875    for (rs = (*input)->context()->relocSectBegin(); rs != rsEnd; ++rs) {
876      // bypass the reloc section if
877      // 1. its section kind is changed to Ignore. (The target section is a
878      // discarded group section.)
879      // 2. it has no reloc data. (All symbols in the input relocs are in the
880      // discarded group sections)
881      if (LDFileFormat::Ignore == (*rs)->kind() || !(*rs)->hasRelocData())
882        continue;
883      RelocData::iterator reloc, rEnd = (*rs)->getRelocData()->end();
884      for (reloc = (*rs)->getRelocData()->begin(); reloc != rEnd; ++reloc) {
885        Relocation* relocation = llvm::cast<Relocation>(reloc);
886
887        // bypass the reloc if the symbol is in the discarded input section
888        ResolveInfo* info = relocation->symInfo();
889        if (!info->outSymbol()->hasFragRef() &&
890            ResolveInfo::Section == info->type() &&
891            ResolveInfo::Undefined == info->desc())
892          continue;
893
894        // bypass the relocation with NONE type. This is to avoid overwrite the
895        // target result by NONE type relocation if there is a place which has
896        // two relocations to apply to, and one of it is NONE type. The result
897        // we want is the value of the other relocation result. For example,
898        // in .exidx, there are usually an R_ARM_NONE and R_ARM_PREL31 apply to
899        // the same place
900        if (relocation->type() == 0x0)
901          continue;
902        writeRelocationResult(*relocation, data);
903      }  // for all relocations
904    }    // for all relocation section
905  }      // for all inputs
906
907  // sync relocations created by relaxation
908  BranchIslandFactory* br_factory = m_LDBackend.getBRIslandFactory();
909  BranchIslandFactory::iterator facIter, facEnd = br_factory->end();
910  for (facIter = br_factory->begin(); facIter != facEnd; ++facIter) {
911    BranchIsland& island = *facIter;
912    BranchIsland::reloc_iterator iter, iterEnd = island.reloc_end();
913    for (iter = island.reloc_begin(); iter != iterEnd; ++iter) {
914      Relocation* reloc = *iter;
915      writeRelocationResult(*reloc, data);
916    }
917  }
918
919  // sync relocations created by LD backend
920  for (TargetLDBackend::extra_reloc_iterator
921       iter = m_LDBackend.extra_reloc_begin(),
922       end = m_LDBackend.extra_reloc_end(); iter != end; ++iter) {
923    writeRelocationResult(*iter, data);
924  }
925}
926
927void ObjectLinker::partialSyncRelocationResult(FileOutputBuffer& pOutput) {
928  uint8_t* data = pOutput.getBufferStart();
929
930  // traverse outputs' LDSection to get RelocData
931  Module::iterator sectIter, sectEnd = m_pModule->end();
932  for (sectIter = m_pModule->begin(); sectIter != sectEnd; ++sectIter) {
933    if (LDFileFormat::Relocation != (*sectIter)->kind())
934      continue;
935
936    RelocData* reloc_data = (*sectIter)->getRelocData();
937    RelocData::iterator relocIter, relocEnd = reloc_data->end();
938    for (relocIter = reloc_data->begin(); relocIter != relocEnd; ++relocIter) {
939      Relocation* reloc = llvm::cast<Relocation>(relocIter);
940
941      // bypass the relocation with NONE type. This is to avoid overwrite the
942      // target result by NONE type relocation if there is a place which has
943      // two relocations to apply to, and one of it is NONE type. The result
944      // we want is the value of the other relocation result. For example,
945      // in .exidx, there are usually an R_ARM_NONE and R_ARM_PREL31 apply to
946      // the same place
947      if (reloc->type() == 0x0)
948        continue;
949      writeRelocationResult(*reloc, data);
950    }
951  }
952}
953
954void ObjectLinker::writeRelocationResult(Relocation& pReloc, uint8_t* pOutput) {
955  // get output file offset
956  size_t out_offset =
957      pReloc.targetRef().frag()->getParent()->getSection().offset() +
958      pReloc.targetRef().getOutputOffset();
959
960  uint8_t* target_addr = pOutput + out_offset;
961  // byte swapping if target and host has different endian, and then write back
962  if (llvm::sys::IsLittleEndianHost != m_Config.targets().isLittleEndian()) {
963    uint64_t tmp_data = 0;
964
965    switch (pReloc.size(*m_LDBackend.getRelocator())) {
966      case 8u:
967        std::memcpy(target_addr, &pReloc.target(), 1);
968        break;
969
970      case 16u:
971        tmp_data = mcld::bswap16(pReloc.target());
972        std::memcpy(target_addr, &tmp_data, 2);
973        break;
974
975      case 32u:
976        tmp_data = mcld::bswap32(pReloc.target());
977        std::memcpy(target_addr, &tmp_data, 4);
978        break;
979
980      case 64u:
981        tmp_data = mcld::bswap64(pReloc.target());
982        std::memcpy(target_addr, &tmp_data, 8);
983        break;
984
985      default:
986        break;
987    }
988  } else {
989    std::memcpy(target_addr, &pReloc.target(),
990                (pReloc.size(*m_LDBackend.getRelocator()) + 7) / 8);
991  }
992}
993
994}  // namespace mcld
995