GNULDBackend.cpp revision cfcb22478ca64c308df58f9abe6fa2dedb213c16 
1//===- GNULDBackend.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/Target/GNULDBackend.h"
10
11#include "mcld/IRBuilder.h"
12#include "mcld/InputTree.h"
13#include "mcld/LinkerConfig.h"
14#include "mcld/LinkerScript.h"
15#include "mcld/Module.h"
16#include "mcld/ADT/SizeTraits.h"
17#include "mcld/Config/Config.h"
18#include "mcld/Fragment/FillFragment.h"
19#include "mcld/LD/BranchIslandFactory.h"
20#include "mcld/LD/EhFrame.h"
21#include "mcld/LD/EhFrameHdr.h"
22#include "mcld/LD/ELFDynObjFileFormat.h"
23#include "mcld/LD/ELFExecFileFormat.h"
24#include "mcld/LD/ELFFileFormat.h"
25#include "mcld/LD/ELFObjectFileFormat.h"
26#include "mcld/LD/ELFSegment.h"
27#include "mcld/LD/ELFSegmentFactory.h"
28#include "mcld/LD/LDContext.h"
29#include "mcld/LD/LDSymbol.h"
30#include "mcld/LD/RelocData.h"
31#include "mcld/LD/RelocationFactory.h"
32#include "mcld/LD/StubFactory.h"
33#include "mcld/MC/Attribute.h"
34#include "mcld/Object/ObjectBuilder.h"
35#include "mcld/Object/SectionMap.h"
36#include "mcld/Script/Operand.h"
37#include "mcld/Script/OutputSectDesc.h"
38#include "mcld/Script/RpnEvaluator.h"
39#include "mcld/Support/FileOutputBuffer.h"
40#include "mcld/Support/MsgHandling.h"
41#include "mcld/Target/ELFAttribute.h"
42#include "mcld/Target/ELFDynamic.h"
43#include "mcld/Target/GNUInfo.h"
44
45#include <llvm/ADT/StringRef.h>
46#include <llvm/Support/Host.h>
47
48#include <algorithm>
49#include <cstring>
50#include <cassert>
51#include <map>
52#include <string>
53#include <vector>
54
55namespace {
56
57//===----------------------------------------------------------------------===//
58// non-member functions
59//===----------------------------------------------------------------------===//
60static const std::string simple_c_identifier_allowed_chars =
61    "0123456789"
62    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
63    "abcdefghijklmnopqrstuvwxyz"
64    "_";
65
66/// isCIdentifier - return if the pName is a valid C identifier
67static bool isCIdentifier(const std::string& pName) {
68  return (pName.find_first_not_of(simple_c_identifier_allowed_chars) ==
69          std::string::npos);
70}
71
72}  // anonymous namespace
73
74namespace mcld {
75
76//===----------------------------------------------------------------------===//
77// GNULDBackend
78//===----------------------------------------------------------------------===//
79GNULDBackend::GNULDBackend(const LinkerConfig& pConfig, GNUInfo* pInfo)
80    : TargetLDBackend(pConfig),
81      m_pObjectReader(NULL),
82      m_pDynObjFileFormat(NULL),
83      m_pExecFileFormat(NULL),
84      m_pObjectFileFormat(NULL),
85      m_pInfo(pInfo),
86      m_pELFSegmentTable(NULL),
87      m_pBRIslandFactory(NULL),
88      m_pStubFactory(NULL),
89      m_pEhFrameHdr(NULL),
90      m_pAttribute(NULL),
91      m_bHasTextRel(false),
92      m_bHasStaticTLS(false),
93      f_pPreInitArrayStart(NULL),
94      f_pPreInitArrayEnd(NULL),
95      f_pInitArrayStart(NULL),
96      f_pInitArrayEnd(NULL),
97      f_pFiniArrayStart(NULL),
98      f_pFiniArrayEnd(NULL),
99      f_pStack(NULL),
100      f_pDynamic(NULL),
101      f_pTDATA(NULL),
102      f_pTBSS(NULL),
103      f_pExecutableStart(NULL),
104      f_pEText(NULL),
105      f_p_EText(NULL),
106      f_p__EText(NULL),
107      f_pEData(NULL),
108      f_p_EData(NULL),
109      f_pBSSStart(NULL),
110      f_pEnd(NULL),
111      f_p_End(NULL) {
112  m_pELFSegmentTable = new ELFSegmentFactory();
113  m_pSymIndexMap = new HashTableType(1024);
114  m_pAttribute = new ELFAttribute(*this, pConfig);
115}
116
117GNULDBackend::~GNULDBackend() {
118  delete m_pELFSegmentTable;
119  delete m_pInfo;
120  delete m_pDynObjFileFormat;
121  delete m_pExecFileFormat;
122  delete m_pObjectFileFormat;
123  delete m_pSymIndexMap;
124  delete m_pEhFrameHdr;
125  delete m_pAttribute;
126  delete m_pBRIslandFactory;
127  delete m_pStubFactory;
128}
129
130size_t GNULDBackend::sectionStartOffset() const {
131  if (LinkerConfig::Binary == config().codeGenType())
132    return 0x0;
133
134  switch (config().targets().bitclass()) {
135    case 32u:
136      return sizeof(llvm::ELF::Elf32_Ehdr) +
137             elfSegmentTable().size() * sizeof(llvm::ELF::Elf32_Phdr);
138    case 64u:
139      return sizeof(llvm::ELF::Elf64_Ehdr) +
140             elfSegmentTable().size() * sizeof(llvm::ELF::Elf64_Phdr);
141    default:
142      fatal(diag::unsupported_bitclass) << config().targets().triple().str()
143                                        << config().targets().bitclass();
144      return 0;
145  }
146}
147
148uint64_t GNULDBackend::getSegmentStartAddr(const LinkerScript& pScript) const {
149  LinkerScript::AddressMap::const_iterator mapping =
150      pScript.addressMap().find(".text");
151  if (pScript.addressMap().end() != mapping)
152    return mapping.getEntry()->value();
153  else if (config().isCodeIndep())
154    return 0x0;
155  else
156    return m_pInfo->defaultTextSegmentAddr();
157}
158
159GNUArchiveReader* GNULDBackend::createArchiveReader(Module& pModule) {
160  assert(m_pObjectReader != NULL);
161  return new GNUArchiveReader(pModule, *m_pObjectReader);
162}
163
164ELFObjectReader* GNULDBackend::createObjectReader(IRBuilder& pBuilder) {
165  m_pObjectReader = new ELFObjectReader(*this, pBuilder, config());
166  return m_pObjectReader;
167}
168
169ELFDynObjReader* GNULDBackend::createDynObjReader(IRBuilder& pBuilder) {
170  return new ELFDynObjReader(*this, pBuilder, config());
171}
172
173ELFBinaryReader* GNULDBackend::createBinaryReader(IRBuilder& pBuilder) {
174  return new ELFBinaryReader(pBuilder, config());
175}
176
177ELFObjectWriter* GNULDBackend::createWriter() {
178  return new ELFObjectWriter(*this, config());
179}
180
181bool GNULDBackend::initStdSections(ObjectBuilder& pBuilder) {
182  switch (config().codeGenType()) {
183    case LinkerConfig::DynObj: {
184      if (m_pDynObjFileFormat == NULL)
185        m_pDynObjFileFormat = new ELFDynObjFileFormat();
186      m_pDynObjFileFormat->initStdSections(pBuilder,
187                                           config().targets().bitclass());
188      return true;
189    }
190    case LinkerConfig::Exec:
191    case LinkerConfig::Binary: {
192      if (m_pExecFileFormat == NULL)
193        m_pExecFileFormat = new ELFExecFileFormat();
194      m_pExecFileFormat->initStdSections(pBuilder,
195                                         config().targets().bitclass());
196      return true;
197    }
198    case LinkerConfig::Object: {
199      if (m_pObjectFileFormat == NULL)
200        m_pObjectFileFormat = new ELFObjectFileFormat();
201      m_pObjectFileFormat->initStdSections(pBuilder,
202                                           config().targets().bitclass());
203      return true;
204    }
205    default:
206      fatal(diag::unrecognized_output_file) << config().codeGenType();
207      return false;
208  }
209}
210
211/// initStandardSymbols - define and initialize standard symbols.
212/// This function is called after section merging but before read relocations.
213bool GNULDBackend::initStandardSymbols(IRBuilder& pBuilder, Module& pModule) {
214  if (LinkerConfig::Object == config().codeGenType())
215    return true;
216
217  // GNU extension: define __start and __stop symbols for the sections whose
218  // name can be presented as C symbol
219  Module::iterator iter, iterEnd = pModule.end();
220  for (iter = pModule.begin(); iter != iterEnd; ++iter) {
221    LDSection* section = *iter;
222
223    switch (section->kind()) {
224      case LDFileFormat::Relocation:
225        continue;
226      case LDFileFormat::EhFrame:
227        if (!section->hasEhFrame())
228          continue;
229        break;
230      default:
231        if (!section->hasSectionData())
232          continue;
233        break;
234    }  // end of switch
235
236    if (isCIdentifier(section->name())) {
237      std::string start_name = "__start_" + section->name();
238      FragmentRef* start_fragref =
239          FragmentRef::Create(section->getSectionData()->front(), 0x0);
240
241      pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
242          start_name,
243          ResolveInfo::NoType,
244          ResolveInfo::Define,
245          ResolveInfo::Global,
246          0x0,            // size
247          0x0,            // value
248          start_fragref,  // FragRef
249          ResolveInfo::Default);
250
251      std::string stop_name = "__stop_" + section->name();
252      FragmentRef* stop_fragref = FragmentRef::Create(
253          section->getSectionData()->front(), section->size());
254      pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
255          stop_name,
256          ResolveInfo::NoType,
257          ResolveInfo::Define,
258          ResolveInfo::Global,
259          0x0,           // size
260          0x0,           // value
261          stop_fragref,  // FragRef
262          ResolveInfo::Default);
263    }
264  }
265
266  ELFFileFormat* file_format = getOutputFormat();
267
268  // -----  section symbols  ----- //
269  // .preinit_array
270  FragmentRef* preinit_array = NULL;
271  if (file_format->hasPreInitArray()) {
272    preinit_array = FragmentRef::Create(
273        file_format->getPreInitArray().getSectionData()->front(), 0x0);
274  } else {
275    preinit_array = FragmentRef::Null();
276  }
277
278  f_pPreInitArrayStart =
279      pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
280          "__preinit_array_start",
281          ResolveInfo::NoType,
282          ResolveInfo::Define,
283          ResolveInfo::Global,
284          0x0,            // size
285          0x0,            // value
286          preinit_array,  // FragRef
287          ResolveInfo::Hidden);
288
289  f_pPreInitArrayEnd =
290      pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
291          "__preinit_array_end",
292          ResolveInfo::NoType,
293          ResolveInfo::Define,
294          ResolveInfo::Global,
295          0x0,                  // size
296          0x0,                  // value
297          FragmentRef::Null(),  // FragRef
298          ResolveInfo::Hidden);
299
300  // .init_array
301  FragmentRef* init_array = NULL;
302  if (file_format->hasInitArray()) {
303    init_array = FragmentRef::Create(
304        file_format->getInitArray().getSectionData()->front(), 0x0);
305  } else {
306    init_array = FragmentRef::Null();
307  }
308
309  f_pInitArrayStart =
310      pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
311          "__init_array_start",
312          ResolveInfo::NoType,
313          ResolveInfo::Define,
314          ResolveInfo::Global,
315          0x0,         // size
316          0x0,         // value
317          init_array,  // FragRef
318          ResolveInfo::Hidden);
319
320  f_pInitArrayEnd =
321      pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
322          "__init_array_end",
323          ResolveInfo::NoType,
324          ResolveInfo::Define,
325          ResolveInfo::Global,
326          0x0,         // size
327          0x0,         // value
328          init_array,  // FragRef
329          ResolveInfo::Hidden);
330
331  // .fini_array
332  FragmentRef* fini_array = NULL;
333  if (file_format->hasFiniArray()) {
334    fini_array = FragmentRef::Create(
335        file_format->getFiniArray().getSectionData()->front(), 0x0);
336  } else {
337    fini_array = FragmentRef::Null();
338  }
339
340  f_pFiniArrayStart =
341      pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
342          "__fini_array_start",
343          ResolveInfo::NoType,
344          ResolveInfo::Define,
345          ResolveInfo::Global,
346          0x0,         // size
347          0x0,         // value
348          fini_array,  // FragRef
349          ResolveInfo::Hidden);
350
351  f_pFiniArrayEnd =
352      pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
353          "__fini_array_end",
354          ResolveInfo::NoType,
355          ResolveInfo::Define,
356          ResolveInfo::Global,
357          0x0,         // size
358          0x0,         // value
359          fini_array,  // FragRef
360          ResolveInfo::Hidden);
361
362  // .stack
363  FragmentRef* stack = NULL;
364  if (file_format->hasStack()) {
365    stack = FragmentRef::Create(
366        file_format->getStack().getSectionData()->front(), 0x0);
367  } else {
368    stack = FragmentRef::Null();
369  }
370
371  f_pStack = pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
372      "__stack",
373      ResolveInfo::NoType,
374      ResolveInfo::Define,
375      ResolveInfo::Global,
376      0x0,    // size
377      0x0,    // value
378      stack,  // FragRef
379      ResolveInfo::Hidden);
380
381  // _DYNAMIC
382  // TODO: add SectionData for .dynamic section, and then we can get the correct
383  // symbol section index for _DYNAMIC. Now it will be ABS.
384  f_pDynamic = pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
385      "_DYNAMIC",
386      ResolveInfo::Object,
387      ResolveInfo::Define,
388      ResolveInfo::Local,
389      0x0,                  // size
390      0x0,                  // value
391      FragmentRef::Null(),  // FragRef
392      ResolveInfo::Hidden);
393
394  // -----  segment symbols  ----- //
395  f_pExecutableStart =
396      pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
397          "__executable_start",
398          ResolveInfo::NoType,
399          ResolveInfo::Define,
400          ResolveInfo::Absolute,
401          0x0,                  // size
402          0x0,                  // value
403          FragmentRef::Null(),  // FragRef
404          ResolveInfo::Default);
405
406  f_pEText = pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
407      "etext",
408      ResolveInfo::NoType,
409      ResolveInfo::Define,
410      ResolveInfo::Absolute,
411      0x0,                  // size
412      0x0,                  // value
413      FragmentRef::Null(),  // FragRef
414      ResolveInfo::Default);
415
416  f_p_EText = pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
417      "_etext",
418      ResolveInfo::NoType,
419      ResolveInfo::Define,
420      ResolveInfo::Absolute,
421      0x0,                  // size
422      0x0,                  // value
423      FragmentRef::Null(),  // FragRef
424      ResolveInfo::Default);
425  f_p__EText = pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
426      "__etext",
427      ResolveInfo::NoType,
428      ResolveInfo::Define,
429      ResolveInfo::Absolute,
430      0x0,                  // size
431      0x0,                  // value
432      FragmentRef::Null(),  // FragRef
433      ResolveInfo::Default);
434  f_pEData = pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
435      "edata",
436      ResolveInfo::NoType,
437      ResolveInfo::Define,
438      ResolveInfo::Absolute,
439      0x0,                  // size
440      0x0,                  // value
441      FragmentRef::Null(),  // FragRef
442      ResolveInfo::Default);
443
444  f_pEnd = pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
445      "end",
446      ResolveInfo::NoType,
447      ResolveInfo::Define,
448      ResolveInfo::Absolute,
449      0x0,                  // size
450      0x0,                  // value
451      FragmentRef::Null(),  // FragRef
452      ResolveInfo::Default);
453
454  // _edata is defined forcefully.
455  f_p_EData = pBuilder.AddSymbol<IRBuilder::Force, IRBuilder::Resolve>(
456      "_edata",
457      ResolveInfo::NoType,
458      ResolveInfo::Define,
459      ResolveInfo::Absolute,
460      0x0,                  // size
461      0x0,                  // value
462      FragmentRef::Null(),  // FragRef
463      ResolveInfo::Default);
464
465  // __bss_start is defined forcefully.
466  f_pBSSStart = pBuilder.AddSymbol<IRBuilder::Force, IRBuilder::Resolve>(
467      "__bss_start",
468      ResolveInfo::NoType,
469      ResolveInfo::Define,
470      ResolveInfo::Absolute,
471      0x0,                  // size
472      0x0,                  // value
473      FragmentRef::Null(),  // FragRef
474      ResolveInfo::Default);
475
476  // _end is defined forcefully.
477  f_p_End = pBuilder.AddSymbol<IRBuilder::Force, IRBuilder::Resolve>(
478      "_end",
479      ResolveInfo::NoType,
480      ResolveInfo::Define,
481      ResolveInfo::Absolute,
482      0x0,                  // size
483      0x0,                  // value
484      FragmentRef::Null(),  // FragRef
485      ResolveInfo::Default);
486
487  return true;
488}
489
490bool GNULDBackend::finalizeStandardSymbols() {
491  if (LinkerConfig::Object == config().codeGenType())
492    return true;
493
494  ELFFileFormat* file_format = getOutputFormat();
495
496  // -----  section symbols  ----- //
497  if (f_pPreInitArrayStart != NULL) {
498    if (!f_pPreInitArrayStart->hasFragRef()) {
499      f_pPreInitArrayStart->resolveInfo()->setBinding(ResolveInfo::Absolute);
500      f_pPreInitArrayStart->setValue(0x0);
501    }
502  }
503
504  if (f_pPreInitArrayEnd != NULL) {
505    if (f_pPreInitArrayEnd->hasFragRef()) {
506      f_pPreInitArrayEnd->setValue(f_pPreInitArrayEnd->value() +
507                                   file_format->getPreInitArray().size());
508    } else {
509      f_pPreInitArrayEnd->resolveInfo()->setBinding(ResolveInfo::Absolute);
510      f_pPreInitArrayEnd->setValue(0x0);
511    }
512  }
513
514  if (f_pInitArrayStart != NULL) {
515    if (!f_pInitArrayStart->hasFragRef()) {
516      f_pInitArrayStart->resolveInfo()->setBinding(ResolveInfo::Absolute);
517      f_pInitArrayStart->setValue(0x0);
518    }
519  }
520
521  if (f_pInitArrayEnd != NULL) {
522    if (f_pInitArrayEnd->hasFragRef()) {
523      f_pInitArrayEnd->setValue(f_pInitArrayEnd->value() +
524                                file_format->getInitArray().size());
525    } else {
526      f_pInitArrayEnd->resolveInfo()->setBinding(ResolveInfo::Absolute);
527      f_pInitArrayEnd->setValue(0x0);
528    }
529  }
530
531  if (f_pFiniArrayStart != NULL) {
532    if (!f_pFiniArrayStart->hasFragRef()) {
533      f_pFiniArrayStart->resolveInfo()->setBinding(ResolveInfo::Absolute);
534      f_pFiniArrayStart->setValue(0x0);
535    }
536  }
537
538  if (f_pFiniArrayEnd != NULL) {
539    if (f_pFiniArrayEnd->hasFragRef()) {
540      f_pFiniArrayEnd->setValue(f_pFiniArrayEnd->value() +
541                                file_format->getFiniArray().size());
542    } else {
543      f_pFiniArrayEnd->resolveInfo()->setBinding(ResolveInfo::Absolute);
544      f_pFiniArrayEnd->setValue(0x0);
545    }
546  }
547
548  if (f_pStack != NULL) {
549    if (!f_pStack->hasFragRef()) {
550      f_pStack->resolveInfo()->setBinding(ResolveInfo::Absolute);
551      f_pStack->setValue(0x0);
552    }
553  }
554
555  if (f_pDynamic != NULL) {
556    f_pDynamic->resolveInfo()->setBinding(ResolveInfo::Local);
557    f_pDynamic->setValue(file_format->getDynamic().addr());
558    f_pDynamic->setSize(file_format->getDynamic().size());
559  }
560
561  // -----  segment symbols  ----- //
562  if (f_pExecutableStart != NULL) {
563    ELFSegmentFactory::const_iterator exec_start =
564        elfSegmentTable().find(llvm::ELF::PT_LOAD, 0x0, 0x0);
565    if (elfSegmentTable().end() != exec_start) {
566      if (ResolveInfo::ThreadLocal != f_pExecutableStart->type()) {
567        f_pExecutableStart->setValue(f_pExecutableStart->value() +
568                                     (*exec_start)->vaddr());
569      }
570    } else {
571      f_pExecutableStart->setValue(0x0);
572    }
573  }
574
575  if (f_pEText != NULL || f_p_EText != NULL || f_p__EText != NULL) {
576    ELFSegmentFactory::const_iterator etext = elfSegmentTable().find(
577        llvm::ELF::PT_LOAD, llvm::ELF::PF_X, llvm::ELF::PF_W);
578    if (elfSegmentTable().end() != etext) {
579      if (f_pEText != NULL && ResolveInfo::ThreadLocal != f_pEText->type()) {
580        f_pEText->setValue(f_pEText->value() + (*etext)->vaddr() +
581                           (*etext)->memsz());
582      }
583      if (f_p_EText != NULL && ResolveInfo::ThreadLocal != f_p_EText->type()) {
584        f_p_EText->setValue(f_p_EText->value() + (*etext)->vaddr() +
585                            (*etext)->memsz());
586      }
587      if (f_p__EText != NULL &&
588          ResolveInfo::ThreadLocal != f_p__EText->type()) {
589        f_p__EText->setValue(f_p__EText->value() + (*etext)->vaddr() +
590                             (*etext)->memsz());
591      }
592    } else {
593      if (f_pEText != NULL)
594        f_pEText->setValue(0x0);
595      if (f_p_EText != NULL)
596        f_p_EText->setValue(0x0);
597      if (f_p__EText != NULL)
598        f_p__EText->setValue(0x0);
599    }
600  }
601
602  if (f_pEData != NULL || f_p_EData != NULL || f_pBSSStart != NULL ||
603      f_pEnd != NULL || f_p_End != NULL) {
604    ELFSegmentFactory::const_iterator edata =
605        elfSegmentTable().find(llvm::ELF::PT_LOAD, llvm::ELF::PF_W, 0x0);
606    if (elfSegmentTable().end() != edata) {
607      if (f_pEData != NULL && ResolveInfo::ThreadLocal != f_pEData->type()) {
608        f_pEData->setValue(f_pEData->value() + (*edata)->vaddr() +
609                           (*edata)->filesz());
610      }
611      if (f_p_EData != NULL && ResolveInfo::ThreadLocal != f_p_EData->type()) {
612        f_p_EData->setValue(f_p_EData->value() + (*edata)->vaddr() +
613                            (*edata)->filesz());
614      }
615      if (f_pBSSStart != NULL &&
616          ResolveInfo::ThreadLocal != f_pBSSStart->type()) {
617        f_pBSSStart->setValue(f_pBSSStart->value() + (*edata)->vaddr() +
618                              (*edata)->filesz());
619      }
620
621      if (f_pEnd != NULL && ResolveInfo::ThreadLocal != f_pEnd->type()) {
622        f_pEnd->setValue(f_pEnd->value() + (*edata)->vaddr() +
623                         (*edata)->memsz());
624      }
625      if (f_p_End != NULL && ResolveInfo::ThreadLocal != f_p_End->type()) {
626        f_p_End->setValue(f_p_End->value() + (*edata)->vaddr() +
627                          (*edata)->memsz());
628      }
629    } else {
630      if (f_pEData != NULL)
631        f_pEData->setValue(0x0);
632      if (f_p_EData != NULL)
633        f_p_EData->setValue(0x0);
634      if (f_pBSSStart != NULL)
635        f_pBSSStart->setValue(0x0);
636
637      if (f_pEnd != NULL)
638        f_pEnd->setValue(0x0);
639      if (f_p_End != NULL)
640        f_p_End->setValue(0x0);
641    }
642  }
643
644  return true;
645}
646
647bool GNULDBackend::finalizeTLSSymbol(LDSymbol& pSymbol) {
648  // ignore if symbol has no fragRef
649  if (!pSymbol.hasFragRef())
650    return true;
651
652  // the value of a TLS symbol is the offset to the TLS segment
653  ELFSegmentFactory::iterator tls_seg =
654      elfSegmentTable().find(llvm::ELF::PT_TLS, llvm::ELF::PF_R, 0x0);
655  assert(tls_seg != elfSegmentTable().end());
656  uint64_t value = pSymbol.fragRef()->getOutputOffset();
657  uint64_t addr = pSymbol.fragRef()->frag()->getParent()->getSection().addr();
658  pSymbol.setValue(value + addr - (*tls_seg)->vaddr());
659  return true;
660}
661
662ELFFileFormat* GNULDBackend::getOutputFormat() {
663  switch (config().codeGenType()) {
664    case LinkerConfig::DynObj:
665      assert(m_pDynObjFileFormat != NULL);
666      return m_pDynObjFileFormat;
667    case LinkerConfig::Exec:
668    case LinkerConfig::Binary:
669      assert(m_pExecFileFormat != NULL);
670      return m_pExecFileFormat;
671    case LinkerConfig::Object:
672      assert(m_pObjectFileFormat != NULL);
673      return m_pObjectFileFormat;
674    default:
675      fatal(diag::unrecognized_output_file) << config().codeGenType();
676      return NULL;
677  }
678}
679
680const ELFFileFormat* GNULDBackend::getOutputFormat() const {
681  switch (config().codeGenType()) {
682    case LinkerConfig::DynObj:
683      assert(m_pDynObjFileFormat != NULL);
684      return m_pDynObjFileFormat;
685    case LinkerConfig::Exec:
686    case LinkerConfig::Binary:
687      assert(m_pExecFileFormat != NULL);
688      return m_pExecFileFormat;
689    case LinkerConfig::Object:
690      assert(m_pObjectFileFormat != NULL);
691      return m_pObjectFileFormat;
692    default:
693      fatal(diag::unrecognized_output_file) << config().codeGenType();
694      return NULL;
695  }
696}
697
698/// sizeShstrtab - compute the size of .shstrtab
699void GNULDBackend::sizeShstrtab(Module& pModule) {
700  size_t shstrtab = 0;
701  // compute the size of .shstrtab section.
702  Module::const_iterator sect, sectEnd = pModule.end();
703  for (sect = pModule.begin(); sect != sectEnd; ++sect) {
704    shstrtab += (*sect)->name().size() + 1;
705  }  // end of for
706  getOutputFormat()->getShStrTab().setSize(shstrtab);
707}
708
709/// sizeNamePools - compute the size of regular name pools
710/// In ELF executable files, regular name pools are .symtab, .strtab,
711/// .dynsym, .dynstr, .hash and .shstrtab.
712void GNULDBackend::sizeNamePools(Module& pModule) {
713  assert(LinkerConfig::Unset != config().codePosition());
714
715  // number of entries in symbol tables starts from 1 to hold the special entry
716  // at index 0 (STN_UNDEF). See ELF Spec Book I, p1-21.
717  size_t symtab = 1;
718  size_t dynsym = config().isCodeStatic() ? 0 : 1;
719
720  // size of string tables starts from 1 to hold the null character in their
721  // first byte
722  size_t strtab = 1;
723  size_t dynstr = config().isCodeStatic() ? 0 : 1;
724  size_t hash = 0;
725  size_t gnuhash = 0;
726
727  // number of local symbol in the .symtab and .dynsym
728  size_t symtab_local_cnt = 0;
729  size_t dynsym_local_cnt = 0;
730
731  Module::SymbolTable& symbols = pModule.getSymbolTable();
732  Module::const_sym_iterator symbol, symEnd;
733  /// Compute the size of .symtab, .strtab, and symtab_local_cnt
734  /// @{
735  /* TODO:
736       1. discard locals and temporary locals
737       2. check whether the symbol is used
738   */
739  switch (config().options().getStripSymbolMode()) {
740    case GeneralOptions::StripSymbolMode::StripAllSymbols: {
741      symtab = strtab = 0;
742      break;
743    }
744    default: {
745      symEnd = symbols.end();
746      for (symbol = symbols.begin(); symbol != symEnd; ++symbol) {
747        ++symtab;
748        if (hasEntryInStrTab(**symbol))
749          strtab += (*symbol)->nameSize() + 1;
750      }
751      symtab_local_cnt = 1 + symbols.numOfFiles() + symbols.numOfLocals() +
752                         symbols.numOfLocalDyns();
753      break;
754    }
755  }  // end of switch
756
757  ELFFileFormat* file_format = getOutputFormat();
758
759  switch (config().codeGenType()) {
760    case LinkerConfig::DynObj: {
761      // soname
762      dynstr += config().options().soname().size() + 1;
763    }
764    /** fall through **/
765    case LinkerConfig::Exec:
766    case LinkerConfig::Binary: {
767      if (!config().isCodeStatic()) {
768        /// Compute the size of .dynsym, .dynstr, and dynsym_local_cnt
769        symEnd = symbols.dynamicEnd();
770        for (symbol = symbols.localDynBegin(); symbol != symEnd; ++symbol) {
771          ++dynsym;
772          if (hasEntryInStrTab(**symbol))
773            dynstr += (*symbol)->nameSize() + 1;
774        }
775        dynsym_local_cnt = 1 + symbols.numOfLocalDyns();
776
777        // compute .gnu.hash
778        if (config().options().hasGNUHash()) {
779          // count the number of dynsym to hash
780          size_t hashed_sym_cnt = 0;
781          symEnd = symbols.dynamicEnd();
782          for (symbol = symbols.dynamicBegin(); symbol != symEnd; ++symbol) {
783            if (DynsymCompare().needGNUHash(**symbol))
784              ++hashed_sym_cnt;
785          }
786          // Special case for empty .dynsym
787          if (hashed_sym_cnt == 0)
788            gnuhash = 5 * 4 + config().targets().bitclass() / 8;
789          else {
790            size_t nbucket = getHashBucketCount(hashed_sym_cnt, true);
791            gnuhash = (4 + nbucket + hashed_sym_cnt) * 4;
792            gnuhash += (1U << getGNUHashMaskbitslog2(hashed_sym_cnt)) / 8;
793          }
794        }
795
796        // compute .hash
797        if (config().options().hasSysVHash()) {
798          // Both Elf32_Word and Elf64_Word are 4 bytes
799          hash = (2 + getHashBucketCount(dynsym, false) + dynsym) *
800                 sizeof(llvm::ELF::Elf32_Word);
801        }
802
803        // add DT_NEEDED
804        Module::const_lib_iterator lib, libEnd = pModule.lib_end();
805        for (lib = pModule.lib_begin(); lib != libEnd; ++lib) {
806          if (!(*lib)->attribute()->isAsNeeded() || (*lib)->isNeeded()) {
807            dynstr += (*lib)->name().size() + 1;
808            dynamic().reserveNeedEntry();
809          }
810        }
811
812        // add DT_RPATH
813        if (!config().options().getRpathList().empty()) {
814          dynamic().reserveNeedEntry();
815          GeneralOptions::const_rpath_iterator rpath,
816              rpathEnd = config().options().rpath_end();
817          for (rpath = config().options().rpath_begin(); rpath != rpathEnd;
818               ++rpath)
819            dynstr += (*rpath).size() + 1;
820        }
821
822        // set size
823        if (config().targets().is32Bits()) {
824          file_format->getDynSymTab().setSize(dynsym *
825                                              sizeof(llvm::ELF::Elf32_Sym));
826        } else {
827          file_format->getDynSymTab().setSize(dynsym *
828                                              sizeof(llvm::ELF::Elf64_Sym));
829        }
830        file_format->getDynStrTab().setSize(dynstr);
831        file_format->getHashTab().setSize(hash);
832        file_format->getGNUHashTab().setSize(gnuhash);
833
834        // set .dynsym sh_info to one greater than the symbol table
835        // index of the last local symbol
836        file_format->getDynSymTab().setInfo(dynsym_local_cnt);
837
838        // Because some entries in .dynamic section need information of .dynsym,
839        // .dynstr, .symtab, .strtab and .hash, we can not reserve non-DT_NEEDED
840        // entries until we get the size of the sections mentioned above
841        dynamic().reserveEntries(*file_format);
842        file_format->getDynamic().setSize(dynamic().numOfBytes());
843      }
844    }
845    /* fall through */
846    case LinkerConfig::Object: {
847      if (config().targets().is32Bits())
848        file_format->getSymTab().setSize(symtab * sizeof(llvm::ELF::Elf32_Sym));
849      else
850        file_format->getSymTab().setSize(symtab * sizeof(llvm::ELF::Elf64_Sym));
851      file_format->getStrTab().setSize(strtab);
852
853      // set .symtab sh_info to one greater than the symbol table
854      // index of the last local symbol
855      file_format->getSymTab().setInfo(symtab_local_cnt);
856
857      // The size of .shstrtab should be decided after output sections are all
858      // set, so we just set it to 1 here.
859      file_format->getShStrTab().setSize(0x1);
860      break;
861    }
862    default:
863      fatal(diag::fatal_illegal_codegen_type) << pModule.name();
864      break;
865  }  // end of switch
866}
867
868/// emitSymbol32 - emit an ELF32 symbol
869void GNULDBackend::emitSymbol32(llvm::ELF::Elf32_Sym& pSym,
870                                LDSymbol& pSymbol,
871                                char* pStrtab,
872                                size_t pStrtabsize,
873                                size_t pSymtabIdx) {
874  // FIXME: check the endian between host and target
875  // write out symbol
876  if (hasEntryInStrTab(pSymbol)) {
877    pSym.st_name = pStrtabsize;
878    ::memcpy((pStrtab + pStrtabsize), pSymbol.name(), pSymbol.nameSize());
879  } else {
880    pSym.st_name = 0;
881  }
882  pSym.st_value = pSymbol.value();
883  pSym.st_size = getSymbolSize(pSymbol);
884  pSym.st_info = getSymbolInfo(pSymbol);
885  pSym.st_other = pSymbol.visibility();
886  pSym.st_shndx = getSymbolShndx(pSymbol);
887}
888
889/// emitSymbol64 - emit an ELF64 symbol
890void GNULDBackend::emitSymbol64(llvm::ELF::Elf64_Sym& pSym,
891                                LDSymbol& pSymbol,
892                                char* pStrtab,
893                                size_t pStrtabsize,
894                                size_t pSymtabIdx) {
895  // FIXME: check the endian between host and target
896  // write out symbol
897  if (hasEntryInStrTab(pSymbol)) {
898    pSym.st_name = pStrtabsize;
899    ::memcpy((pStrtab + pStrtabsize), pSymbol.name(), pSymbol.nameSize());
900  } else {
901    pSym.st_name = 0;
902  }
903  pSym.st_value = pSymbol.value();
904  pSym.st_size = getSymbolSize(pSymbol);
905  pSym.st_info = getSymbolInfo(pSymbol);
906  pSym.st_other = pSymbol.visibility();
907  pSym.st_shndx = getSymbolShndx(pSymbol);
908}
909
910/// emitRegNamePools - emit regular name pools - .symtab, .strtab
911///
912/// the size of these tables should be computed before layout
913/// layout should computes the start offset of these tables
914void GNULDBackend::emitRegNamePools(const Module& pModule,
915                                    FileOutputBuffer& pOutput) {
916  ELFFileFormat* file_format = getOutputFormat();
917  if (!file_format->hasSymTab())
918    return;
919
920  LDSection& symtab_sect = file_format->getSymTab();
921  LDSection& strtab_sect = file_format->getStrTab();
922
923  MemoryRegion symtab_region =
924      pOutput.request(symtab_sect.offset(), symtab_sect.size());
925  MemoryRegion strtab_region =
926      pOutput.request(strtab_sect.offset(), strtab_sect.size());
927
928  // set up symtab_region
929  llvm::ELF::Elf32_Sym* symtab32 = NULL;
930  llvm::ELF::Elf64_Sym* symtab64 = NULL;
931  if (config().targets().is32Bits())
932    symtab32 = (llvm::ELF::Elf32_Sym*)symtab_region.begin();
933  else if (config().targets().is64Bits())
934    symtab64 = (llvm::ELF::Elf64_Sym*)symtab_region.begin();
935  else {
936    fatal(diag::unsupported_bitclass) << config().targets().triple().str()
937                                      << config().targets().bitclass();
938  }
939
940  // set up strtab_region
941  char* strtab = reinterpret_cast<char*>(strtab_region.begin());
942
943  // emit the first ELF symbol
944  if (config().targets().is32Bits())
945    emitSymbol32(symtab32[0], *LDSymbol::Null(), strtab, 0, 0);
946  else
947    emitSymbol64(symtab64[0], *LDSymbol::Null(), strtab, 0, 0);
948
949  bool sym_exist = false;
950  HashTableType::entry_type* entry = NULL;
951  if (LinkerConfig::Object == config().codeGenType()) {
952    entry = m_pSymIndexMap->insert(LDSymbol::Null(), sym_exist);
953    entry->setValue(0);
954  }
955
956  size_t symIdx = 1;
957  size_t strtabsize = 1;
958
959  const Module::SymbolTable& symbols = pModule.getSymbolTable();
960  Module::const_sym_iterator symbol, symEnd;
961
962  symEnd = symbols.end();
963  for (symbol = symbols.begin(); symbol != symEnd; ++symbol) {
964    if (LinkerConfig::Object == config().codeGenType()) {
965      entry = m_pSymIndexMap->insert(*symbol, sym_exist);
966      entry->setValue(symIdx);
967    }
968    if (config().targets().is32Bits())
969      emitSymbol32(symtab32[symIdx], **symbol, strtab, strtabsize, symIdx);
970    else
971      emitSymbol64(symtab64[symIdx], **symbol, strtab, strtabsize, symIdx);
972    ++symIdx;
973    if (hasEntryInStrTab(**symbol))
974      strtabsize += (*symbol)->nameSize() + 1;
975  }
976}
977
978/// emitDynNamePools - emit dynamic name pools - .dyntab, .dynstr, .hash
979///
980/// the size of these tables should be computed before layout
981/// layout should computes the start offset of these tables
982void GNULDBackend::emitDynNamePools(Module& pModule,
983                                    FileOutputBuffer& pOutput) {
984  ELFFileFormat* file_format = getOutputFormat();
985  if (!file_format->hasDynSymTab() || !file_format->hasDynStrTab() ||
986      !file_format->hasDynamic())
987    return;
988
989  bool sym_exist = false;
990  HashTableType::entry_type* entry = 0;
991
992  LDSection& symtab_sect = file_format->getDynSymTab();
993  LDSection& strtab_sect = file_format->getDynStrTab();
994  LDSection& dyn_sect = file_format->getDynamic();
995
996  MemoryRegion symtab_region =
997      pOutput.request(symtab_sect.offset(), symtab_sect.size());
998  MemoryRegion strtab_region =
999      pOutput.request(strtab_sect.offset(), strtab_sect.size());
1000  MemoryRegion dyn_region = pOutput.request(dyn_sect.offset(), dyn_sect.size());
1001  // set up symtab_region
1002  llvm::ELF::Elf32_Sym* symtab32 = NULL;
1003  llvm::ELF::Elf64_Sym* symtab64 = NULL;
1004  if (config().targets().is32Bits())
1005    symtab32 = (llvm::ELF::Elf32_Sym*)symtab_region.begin();
1006  else if (config().targets().is64Bits())
1007    symtab64 = (llvm::ELF::Elf64_Sym*)symtab_region.begin();
1008  else {
1009    fatal(diag::unsupported_bitclass) << config().targets().triple().str()
1010                                      << config().targets().bitclass();
1011  }
1012
1013  // set up strtab_region
1014  char* strtab = reinterpret_cast<char*>(strtab_region.begin());
1015
1016  // emit the first ELF symbol
1017  if (config().targets().is32Bits())
1018    emitSymbol32(symtab32[0], *LDSymbol::Null(), strtab, 0, 0);
1019  else
1020    emitSymbol64(symtab64[0], *LDSymbol::Null(), strtab, 0, 0);
1021
1022  size_t symIdx = 1;
1023  size_t strtabsize = 1;
1024
1025  Module::SymbolTable& symbols = pModule.getSymbolTable();
1026  // emit .gnu.hash
1027  if (config().options().hasGNUHash())
1028    emitGNUHashTab(symbols, pOutput);
1029
1030  // emit .hash
1031  if (config().options().hasSysVHash())
1032    emitELFHashTab(symbols, pOutput);
1033
1034  // emit .dynsym, and .dynstr (emit LocalDyn and Dynamic category)
1035  Module::const_sym_iterator symbol, symEnd = symbols.dynamicEnd();
1036  for (symbol = symbols.localDynBegin(); symbol != symEnd; ++symbol) {
1037    if (config().targets().is32Bits())
1038      emitSymbol32(symtab32[symIdx], **symbol, strtab, strtabsize, symIdx);
1039    else
1040      emitSymbol64(symtab64[symIdx], **symbol, strtab, strtabsize, symIdx);
1041    // maintain output's symbol and index map
1042    entry = m_pSymIndexMap->insert(*symbol, sym_exist);
1043    entry->setValue(symIdx);
1044    // sum up counters
1045    ++symIdx;
1046    if (hasEntryInStrTab(**symbol))
1047      strtabsize += (*symbol)->nameSize() + 1;
1048  }
1049
1050  // emit DT_NEED
1051  // add DT_NEED strings into .dynstr
1052  ELFDynamic::iterator dt_need = dynamic().needBegin();
1053  Module::const_lib_iterator lib, libEnd = pModule.lib_end();
1054  for (lib = pModule.lib_begin(); lib != libEnd; ++lib) {
1055    if (!(*lib)->attribute()->isAsNeeded() || (*lib)->isNeeded()) {
1056      ::memcpy((strtab + strtabsize),
1057               (*lib)->name().c_str(),
1058               (*lib)->name().size());
1059      (*dt_need)->setValue(llvm::ELF::DT_NEEDED, strtabsize);
1060      strtabsize += (*lib)->name().size() + 1;
1061      ++dt_need;
1062    }
1063  }
1064
1065  if (!config().options().getRpathList().empty()) {
1066    if (!config().options().hasNewDTags())
1067      (*dt_need)->setValue(llvm::ELF::DT_RPATH, strtabsize);
1068    else
1069      (*dt_need)->setValue(llvm::ELF::DT_RUNPATH, strtabsize);
1070    ++dt_need;
1071
1072    GeneralOptions::const_rpath_iterator rpath,
1073        rpathEnd = config().options().rpath_end();
1074    for (rpath = config().options().rpath_begin(); rpath != rpathEnd; ++rpath) {
1075      memcpy((strtab + strtabsize), (*rpath).data(), (*rpath).size());
1076      strtabsize += (*rpath).size();
1077      strtab[strtabsize++] = (rpath + 1 == rpathEnd ? '\0' : ':');
1078    }
1079  }
1080
1081  // initialize value of ELF .dynamic section
1082  if (LinkerConfig::DynObj == config().codeGenType()) {
1083    // set pointer to SONAME entry in dynamic string table.
1084    dynamic().applySoname(strtabsize);
1085  }
1086  dynamic().applyEntries(*file_format);
1087  dynamic().emit(dyn_sect, dyn_region);
1088
1089  // emit soname
1090  if (LinkerConfig::DynObj == config().codeGenType()) {
1091    ::memcpy((strtab + strtabsize),
1092             config().options().soname().c_str(),
1093             config().options().soname().size());
1094    strtabsize += config().options().soname().size() + 1;
1095  }
1096}
1097
1098/// emitELFHashTab - emit .hash
1099void GNULDBackend::emitELFHashTab(const Module::SymbolTable& pSymtab,
1100                                  FileOutputBuffer& pOutput) {
1101  ELFFileFormat* file_format = getOutputFormat();
1102  if (!file_format->hasHashTab())
1103    return;
1104  LDSection& hash_sect = file_format->getHashTab();
1105  MemoryRegion hash_region =
1106      pOutput.request(hash_sect.offset(), hash_sect.size());
1107  // both 32 and 64 bits hash table use 32-bit entry
1108  // set up hash_region
1109  uint32_t* word_array = reinterpret_cast<uint32_t*>(hash_region.begin());
1110  uint32_t& nbucket = word_array[0];
1111  uint32_t& nchain = word_array[1];
1112
1113  size_t dynsymSize = 1 + pSymtab.numOfLocalDyns() + pSymtab.numOfDynamics();
1114  nbucket = getHashBucketCount(dynsymSize, false);
1115  nchain = dynsymSize;
1116
1117  uint32_t* bucket = (word_array + 2);
1118  uint32_t* chain = (bucket + nbucket);
1119
1120  // initialize bucket
1121  memset(reinterpret_cast<void*>(bucket), 0, nbucket);
1122
1123  hash::StringHash<hash::ELF> hash_func;
1124
1125  size_t idx = 1;
1126  Module::const_sym_iterator symbol, symEnd = pSymtab.dynamicEnd();
1127  for (symbol = pSymtab.localDynBegin(); symbol != symEnd; ++symbol) {
1128    llvm::StringRef name((*symbol)->name());
1129    size_t bucket_pos = hash_func(name) % nbucket;
1130    chain[idx] = bucket[bucket_pos];
1131    bucket[bucket_pos] = idx;
1132    ++idx;
1133  }
1134}
1135
1136/// emitGNUHashTab - emit .gnu.hash
1137void GNULDBackend::emitGNUHashTab(Module::SymbolTable& pSymtab,
1138                                  FileOutputBuffer& pOutput) {
1139  ELFFileFormat* file_format = getOutputFormat();
1140  if (!file_format->hasGNUHashTab())
1141    return;
1142
1143  MemoryRegion gnuhash_region =
1144      pOutput.request(file_format->getGNUHashTab().offset(),
1145                      file_format->getGNUHashTab().size());
1146
1147  uint32_t* word_array = reinterpret_cast<uint32_t*>(gnuhash_region.begin());
1148  // fixed-length fields
1149  uint32_t& nbucket = word_array[0];
1150  uint32_t& symidx = word_array[1];
1151  uint32_t& maskwords = word_array[2];
1152  uint32_t& shift2 = word_array[3];
1153  // variable-length fields
1154  uint8_t* bitmask = reinterpret_cast<uint8_t*>(word_array + 4);
1155  uint32_t* bucket = NULL;
1156  uint32_t* chain = NULL;
1157
1158  // count the number of dynsym to hash
1159  size_t unhashed_sym_cnt = pSymtab.numOfLocalDyns();
1160  size_t hashed_sym_cnt = pSymtab.numOfDynamics();
1161  Module::const_sym_iterator symbol, symEnd = pSymtab.dynamicEnd();
1162  for (symbol = pSymtab.dynamicBegin(); symbol != symEnd; ++symbol) {
1163    if (DynsymCompare().needGNUHash(**symbol))
1164      break;
1165    ++unhashed_sym_cnt;
1166    --hashed_sym_cnt;
1167  }
1168
1169  // special case for the empty hash table
1170  if (hashed_sym_cnt == 0) {
1171    nbucket = 1;                    // one empty bucket
1172    symidx = 1 + unhashed_sym_cnt;  // symidx above unhashed symbols
1173    maskwords = 1;                  // bitmask length
1174    shift2 = 0;                     // bloom filter
1175
1176    if (config().targets().is32Bits()) {
1177      uint32_t* maskval = reinterpret_cast<uint32_t*>(bitmask);
1178      *maskval = 0;  // no valid hashes
1179    } else {
1180      // must be 64
1181      uint64_t* maskval = reinterpret_cast<uint64_t*>(bitmask);
1182      *maskval = 0;  // no valid hashes
1183    }
1184    bucket = reinterpret_cast<uint32_t*>(bitmask +
1185                                         config().targets().bitclass() / 8);
1186    *bucket = 0;  // no hash in the only bucket
1187    return;
1188  }
1189
1190  uint32_t maskbitslog2 = getGNUHashMaskbitslog2(hashed_sym_cnt);
1191  uint32_t maskbits = 1u << maskbitslog2;
1192  uint32_t shift1 = config().targets().is32Bits() ? 5 : 6;
1193  uint32_t mask = (1u << shift1) - 1;
1194
1195  nbucket = getHashBucketCount(hashed_sym_cnt, true);
1196  symidx = 1 + unhashed_sym_cnt;
1197  maskwords = 1 << (maskbitslog2 - shift1);
1198  shift2 = maskbitslog2;
1199
1200  // setup bucket and chain
1201  bucket = reinterpret_cast<uint32_t*>(bitmask + maskbits / 8);
1202  chain = (bucket + nbucket);
1203
1204  // build the gnu style hash table
1205  typedef std::multimap<uint32_t, std::pair<LDSymbol*, uint32_t> > SymMapType;
1206  SymMapType symmap;
1207  symEnd = pSymtab.dynamicEnd();
1208  for (symbol = pSymtab.localDynBegin() + symidx - 1; symbol != symEnd;
1209       ++symbol) {
1210    hash::StringHash<hash::DJB> hasher;
1211    uint32_t djbhash = hasher((*symbol)->name());
1212    uint32_t hash = djbhash % nbucket;
1213    symmap.insert(std::make_pair(hash, std::make_pair(*symbol, djbhash)));
1214  }
1215
1216  // compute bucket, chain, and bitmask
1217  std::vector<uint64_t> bitmasks(maskwords);
1218  size_t hashedidx = symidx;
1219  for (size_t idx = 0; idx < nbucket; ++idx) {
1220    size_t count = 0;
1221    std::pair<SymMapType::iterator, SymMapType::iterator> ret;
1222    ret = symmap.equal_range(idx);
1223    for (SymMapType::iterator it = ret.first; it != ret.second;) {
1224      // rearrange the hashed symbol ordering
1225      *(pSymtab.localDynBegin() + hashedidx - 1) = it->second.first;
1226      uint32_t djbhash = it->second.second;
1227      uint32_t val = ((djbhash >> shift1) & ((maskbits >> shift1) - 1));
1228      bitmasks[val] |= 1u << (djbhash & mask);
1229      bitmasks[val] |= 1u << ((djbhash >> shift2) & mask);
1230      val = djbhash & ~1u;
1231      // advance the iterator and check if we're dealing w/ the last elment
1232      if (++it == ret.second) {
1233        // last element terminates the chain
1234        val |= 1;
1235      }
1236      chain[hashedidx - symidx] = val;
1237
1238      ++hashedidx;
1239      ++count;
1240    }
1241
1242    if (count == 0)
1243      bucket[idx] = 0;
1244    else
1245      bucket[idx] = hashedidx - count;
1246  }
1247
1248  // write the bitmasks
1249  if (config().targets().is32Bits()) {
1250    uint32_t* maskval = reinterpret_cast<uint32_t*>(bitmask);
1251    for (size_t i = 0; i < maskwords; ++i)
1252      std::memcpy(maskval + i, &bitmasks[i], 4);
1253  } else {
1254    // must be 64
1255    uint64_t* maskval = reinterpret_cast<uint64_t*>(bitmask);
1256    for (size_t i = 0; i < maskwords; ++i)
1257      std::memcpy(maskval + i, &bitmasks[i], 8);
1258  }
1259}
1260
1261/// sizeInterp - compute the size of the .interp section
1262void GNULDBackend::sizeInterp() {
1263  const char* dyld_name;
1264  if (config().options().hasDyld())
1265    dyld_name = config().options().dyld().c_str();
1266  else
1267    dyld_name = m_pInfo->dyld();
1268
1269  LDSection& interp = getOutputFormat()->getInterp();
1270  interp.setSize(std::strlen(dyld_name) + 1);
1271}
1272
1273/// emitInterp - emit the .interp
1274void GNULDBackend::emitInterp(FileOutputBuffer& pOutput) {
1275  if (getOutputFormat()->hasInterp()) {
1276    const LDSection& interp = getOutputFormat()->getInterp();
1277    MemoryRegion region = pOutput.request(interp.offset(), interp.size());
1278    const char* dyld_name;
1279    if (config().options().hasDyld())
1280      dyld_name = config().options().dyld().c_str();
1281    else
1282      dyld_name = m_pInfo->dyld();
1283
1284    std::memcpy(region.begin(), dyld_name, interp.size());
1285  }
1286}
1287
1288bool GNULDBackend::hasEntryInStrTab(const LDSymbol& pSym) const {
1289  return ResolveInfo::Section != pSym.type();
1290}
1291
1292void GNULDBackend::orderSymbolTable(Module& pModule) {
1293  Module::SymbolTable& symbols = pModule.getSymbolTable();
1294
1295  if (config().options().hasGNUHash()) {
1296    // Currently we may add output symbols after sizeNamePools(), and a
1297    // non-stable sort is used in SymbolCategory::arrange(), so we just
1298    // sort .dynsym right before emitting .gnu.hash
1299    std::stable_sort(
1300        symbols.dynamicBegin(), symbols.dynamicEnd(), DynsymCompare());
1301  }
1302}
1303
1304/// getSectionOrder
1305unsigned int GNULDBackend::getSectionOrder(const LDSection& pSectHdr) const {
1306  const ELFFileFormat* file_format = getOutputFormat();
1307
1308  // NULL section should be the "1st" section
1309  if (LDFileFormat::Null == pSectHdr.kind())
1310    return SHO_NULL;
1311
1312  if (&pSectHdr == &file_format->getStrTab())
1313    return SHO_STRTAB;
1314
1315  // if the section is not ALLOC, lay it out until the last possible moment
1316  if (0 == (pSectHdr.flag() & llvm::ELF::SHF_ALLOC))
1317    return SHO_UNDEFINED;
1318
1319  bool is_write = (pSectHdr.flag() & llvm::ELF::SHF_WRITE) != 0;
1320  bool is_exec = (pSectHdr.flag() & llvm::ELF::SHF_EXECINSTR) != 0;
1321  // TODO: need to take care other possible output sections
1322  switch (pSectHdr.kind()) {
1323    case LDFileFormat::TEXT:
1324    case LDFileFormat::DATA:
1325      if (is_exec) {
1326        if (&pSectHdr == &file_format->getInit())
1327          return SHO_INIT;
1328        if (&pSectHdr == &file_format->getFini())
1329          return SHO_FINI;
1330        return SHO_TEXT;
1331      } else if (!is_write) {
1332        return SHO_RO;
1333      } else {
1334        if (config().options().hasRelro()) {
1335          if (&pSectHdr == &file_format->getPreInitArray() ||
1336              &pSectHdr == &file_format->getInitArray() ||
1337              &pSectHdr == &file_format->getFiniArray() ||
1338              &pSectHdr == &file_format->getCtors() ||
1339              &pSectHdr == &file_format->getDtors() ||
1340              &pSectHdr == &file_format->getJCR() ||
1341              &pSectHdr == &file_format->getDataRelRo())
1342            return SHO_RELRO;
1343
1344          if (&pSectHdr == &file_format->getDataRelRoLocal())
1345            return SHO_RELRO_LOCAL;
1346
1347          // Make special sections that end with .rel.ro suffix as RELRO.
1348          llvm::StringRef name(pSectHdr.name());
1349          if (name.endswith(".rel.ro")) {
1350            return SHO_RELRO;
1351          }
1352        }
1353        if ((pSectHdr.flag() & llvm::ELF::SHF_TLS) != 0x0) {
1354          return SHO_TLS_DATA;
1355        }
1356        return SHO_DATA;
1357      }
1358
1359    case LDFileFormat::BSS:
1360      if ((pSectHdr.flag() & llvm::ELF::SHF_TLS) != 0x0)
1361        return SHO_TLS_BSS;
1362      return SHO_BSS;
1363
1364    case LDFileFormat::NamePool: {
1365      if (&pSectHdr == &file_format->getDynamic())
1366        return SHO_RELRO;
1367      return SHO_NAMEPOOL;
1368    }
1369    case LDFileFormat::Relocation:
1370      if (&pSectHdr == &file_format->getRelPlt() ||
1371          &pSectHdr == &file_format->getRelaPlt())
1372        return SHO_REL_PLT;
1373      return SHO_RELOCATION;
1374
1375    // get the order from target for target specific sections
1376    case LDFileFormat::Target:
1377      return getTargetSectionOrder(pSectHdr);
1378
1379    // handle .interp and .note.* sections
1380    case LDFileFormat::Note:
1381      if (file_format->hasInterp() && (&pSectHdr == &file_format->getInterp()))
1382        return SHO_INTERP;
1383      else if (is_write)
1384        return SHO_RW_NOTE;
1385      else
1386        return SHO_RO_NOTE;
1387
1388    case LDFileFormat::EhFrame:
1389      // set writable .eh_frame as relro
1390      if (is_write)
1391        return SHO_RELRO;
1392    case LDFileFormat::EhFrameHdr:
1393    case LDFileFormat::GCCExceptTable:
1394      return SHO_EXCEPTION;
1395
1396    case LDFileFormat::MetaData:
1397    case LDFileFormat::Debug:
1398    case LDFileFormat::DebugString:
1399    default:
1400      return SHO_UNDEFINED;
1401  }
1402}
1403
1404/// getSymbolSize
1405uint64_t GNULDBackend::getSymbolSize(const LDSymbol& pSymbol) const {
1406  // undefined and dynamic symbols should have zero size.
1407  if (pSymbol.isDyn() || pSymbol.desc() == ResolveInfo::Undefined)
1408    return 0x0;
1409  return pSymbol.resolveInfo()->size();
1410}
1411
1412/// getSymbolInfo
1413uint64_t GNULDBackend::getSymbolInfo(const LDSymbol& pSymbol) const {
1414  // set binding
1415  uint8_t bind = 0x0;
1416  if (pSymbol.resolveInfo()->isLocal())
1417    bind = llvm::ELF::STB_LOCAL;
1418  else if (pSymbol.resolveInfo()->isGlobal())
1419    bind = llvm::ELF::STB_GLOBAL;
1420  else if (pSymbol.resolveInfo()->isWeak())
1421    bind = llvm::ELF::STB_WEAK;
1422  else if (pSymbol.resolveInfo()->isAbsolute()) {
1423    // (Luba) Is a absolute but not global (weak or local) symbol meaningful?
1424    bind = llvm::ELF::STB_GLOBAL;
1425  }
1426
1427  if (config().codeGenType() != LinkerConfig::Object &&
1428      (pSymbol.visibility() == llvm::ELF::STV_INTERNAL ||
1429       pSymbol.visibility() == llvm::ELF::STV_HIDDEN))
1430    bind = llvm::ELF::STB_LOCAL;
1431
1432  uint32_t type = pSymbol.resolveInfo()->type();
1433  // if the IndirectFunc symbol (i.e., STT_GNU_IFUNC) is from dynobj, change
1434  // its type to Function
1435  if (type == ResolveInfo::IndirectFunc && pSymbol.isDyn())
1436    type = ResolveInfo::Function;
1437  return (type | (bind << 4));
1438}
1439
1440/// getSymbolValue - this function is called after layout()
1441uint64_t GNULDBackend::getSymbolValue(const LDSymbol& pSymbol) const {
1442  if (pSymbol.isDyn())
1443    return 0x0;
1444
1445  return pSymbol.value();
1446}
1447
1448/// getSymbolShndx - this function is called after layout()
1449uint64_t GNULDBackend::getSymbolShndx(const LDSymbol& pSymbol) const {
1450  if (pSymbol.resolveInfo()->isAbsolute())
1451    return llvm::ELF::SHN_ABS;
1452  if (pSymbol.resolveInfo()->isCommon())
1453    return llvm::ELF::SHN_COMMON;
1454  if (pSymbol.resolveInfo()->isUndef() || pSymbol.isDyn())
1455    return llvm::ELF::SHN_UNDEF;
1456
1457  if (pSymbol.resolveInfo()->isDefine() && !pSymbol.hasFragRef())
1458    return llvm::ELF::SHN_ABS;
1459
1460  assert(pSymbol.hasFragRef() &&
1461         "symbols must have fragment reference to get its index");
1462  return pSymbol.fragRef()->frag()->getParent()->getSection().index();
1463}
1464
1465/// getSymbolIdx - called by emitRelocation to get the ouput symbol table index
1466size_t GNULDBackend::getSymbolIdx(const LDSymbol* pSymbol) const {
1467  HashTableType::iterator entry =
1468      m_pSymIndexMap->find(const_cast<LDSymbol*>(pSymbol));
1469  assert(entry != m_pSymIndexMap->end() &&
1470         "symbol not found in the symbol table");
1471  return entry.getEntry()->value();
1472}
1473
1474/// isTemporary - Whether pSymbol is a local label.
1475bool GNULDBackend::isTemporary(const LDSymbol& pSymbol) const {
1476  if (ResolveInfo::Local != pSymbol.binding())
1477    return false;
1478
1479  if (pSymbol.nameSize() < 2)
1480    return false;
1481
1482  const char* name = pSymbol.name();
1483  if ('.' == name[0] && 'L' == name[1])
1484    return true;
1485
1486  // UnixWare 2.1 cc generate DWARF debugging symbols with `..' prefix.
1487  if (name[0] == '.' && name[1] == '.')
1488    return true;
1489
1490  // Work arround for gcc's bug
1491  // gcc sometimes generate symbols with '_.L_' prefix.
1492  if (pSymbol.nameSize() < 4)
1493    return false;
1494
1495  if (name[0] == '_' && name[1] == '.' && name[2] == 'L' && name[3] == '_')
1496    return true;
1497
1498  return false;
1499}
1500
1501/// allocateCommonSymbols - allocate common symbols in the corresponding
1502/// sections. This is executed at pre-layout stage.
1503bool GNULDBackend::allocateCommonSymbols(Module& pModule) {
1504  SymbolCategory& symbol_list = pModule.getSymbolTable();
1505
1506  if (symbol_list.emptyCommons() && symbol_list.emptyFiles() &&
1507      symbol_list.emptyLocals() && symbol_list.emptyLocalDyns())
1508    return true;
1509
1510  SymbolCategory::iterator com_sym, com_end;
1511
1512  // FIXME: If the order of common symbols is defined, then sort common symbols
1513  // std::sort(com_sym, com_end, some kind of order);
1514
1515  // get corresponding BSS LDSection
1516  ELFFileFormat* file_format = getOutputFormat();
1517  LDSection& bss_sect = file_format->getBSS();
1518  LDSection& tbss_sect = file_format->getTBSS();
1519
1520  // get or create corresponding BSS SectionData
1521  SectionData* bss_sect_data = NULL;
1522  if (bss_sect.hasSectionData())
1523    bss_sect_data = bss_sect.getSectionData();
1524  else
1525    bss_sect_data = IRBuilder::CreateSectionData(bss_sect);
1526
1527  SectionData* tbss_sect_data = NULL;
1528  if (tbss_sect.hasSectionData())
1529    tbss_sect_data = tbss_sect.getSectionData();
1530  else
1531    tbss_sect_data = IRBuilder::CreateSectionData(tbss_sect);
1532
1533  // remember original BSS size
1534  uint64_t bss_offset = bss_sect.size();
1535  uint64_t tbss_offset = tbss_sect.size();
1536
1537  // allocate all local common symbols
1538  com_end = symbol_list.localEnd();
1539
1540  for (com_sym = symbol_list.localBegin(); com_sym != com_end; ++com_sym) {
1541    if (ResolveInfo::Common == (*com_sym)->desc()) {
1542      // We have to reset the description of the symbol here. When doing
1543      // incremental linking, the output relocatable object may have common
1544      // symbols. Therefore, we can not treat common symbols as normal symbols
1545      // when emitting the regular name pools. We must change the symbols'
1546      // description here.
1547      (*com_sym)->resolveInfo()->setDesc(ResolveInfo::Define);
1548      Fragment* frag = new FillFragment(0x0, 1, (*com_sym)->size());
1549
1550      if (ResolveInfo::ThreadLocal == (*com_sym)->type()) {
1551        // allocate TLS common symbol in tbss section
1552        tbss_offset += ObjectBuilder::AppendFragment(
1553            *frag, *tbss_sect_data, (*com_sym)->value());
1554        ObjectBuilder::UpdateSectionAlign(tbss_sect, (*com_sym)->value());
1555        (*com_sym)->setFragmentRef(FragmentRef::Create(*frag, 0));
1556      } else {
1557        bss_offset += ObjectBuilder::AppendFragment(
1558            *frag, *bss_sect_data, (*com_sym)->value());
1559        ObjectBuilder::UpdateSectionAlign(bss_sect, (*com_sym)->value());
1560        (*com_sym)->setFragmentRef(FragmentRef::Create(*frag, 0));
1561      }
1562    }
1563  }
1564
1565  // allocate all global common symbols
1566  com_end = symbol_list.commonEnd();
1567  for (com_sym = symbol_list.commonBegin(); com_sym != com_end; ++com_sym) {
1568    // We have to reset the description of the symbol here. When doing
1569    // incremental linking, the output relocatable object may have common
1570    // symbols. Therefore, we can not treat common symbols as normal symbols
1571    // when emitting the regular name pools. We must change the symbols'
1572    // description here.
1573    (*com_sym)->resolveInfo()->setDesc(ResolveInfo::Define);
1574    Fragment* frag = new FillFragment(0x0, 1, (*com_sym)->size());
1575
1576    if (ResolveInfo::ThreadLocal == (*com_sym)->type()) {
1577      // allocate TLS common symbol in tbss section
1578      tbss_offset += ObjectBuilder::AppendFragment(
1579          *frag, *tbss_sect_data, (*com_sym)->value());
1580      ObjectBuilder::UpdateSectionAlign(tbss_sect, (*com_sym)->value());
1581      (*com_sym)->setFragmentRef(FragmentRef::Create(*frag, 0));
1582    } else {
1583      bss_offset += ObjectBuilder::AppendFragment(
1584          *frag, *bss_sect_data, (*com_sym)->value());
1585      ObjectBuilder::UpdateSectionAlign(bss_sect, (*com_sym)->value());
1586      (*com_sym)->setFragmentRef(FragmentRef::Create(*frag, 0));
1587    }
1588  }
1589
1590  bss_sect.setSize(bss_offset);
1591  tbss_sect.setSize(tbss_offset);
1592  symbol_list.changeCommonsToGlobal();
1593  return true;
1594}
1595
1596/// updateSectionFlags - update pTo's flags when merging pFrom
1597/// update the output section flags based on input section flags.
1598bool GNULDBackend::updateSectionFlags(LDSection& pTo, const LDSection& pFrom) {
1599  // union the flags from input
1600  uint32_t flags = pTo.flag();
1601  flags |= (pFrom.flag() & (llvm::ELF::SHF_WRITE | llvm::ELF::SHF_ALLOC |
1602                            llvm::ELF::SHF_EXECINSTR));
1603
1604  // if there is an input section is not SHF_MERGE, clean this flag
1605  if (0 == (pFrom.flag() & llvm::ELF::SHF_MERGE))
1606    flags &= ~llvm::ELF::SHF_MERGE;
1607
1608  // if there is an input section is not SHF_STRINGS, clean this flag
1609  if (0 == (pFrom.flag() & llvm::ELF::SHF_STRINGS))
1610    flags &= ~llvm::ELF::SHF_STRINGS;
1611
1612  pTo.setFlag(flags);
1613  return true;
1614}
1615
1616/// readRelocation - read ELF32_Rel entry
1617bool GNULDBackend::readRelocation(const llvm::ELF::Elf32_Rel& pRel,
1618                                  Relocation::Type& pType,
1619                                  uint32_t& pSymIdx,
1620                                  uint32_t& pOffset) const {
1621  uint32_t r_info = 0x0;
1622  if (llvm::sys::IsLittleEndianHost) {
1623    pOffset = pRel.r_offset;
1624    r_info = pRel.r_info;
1625  } else {
1626    pOffset = mcld::bswap32(pRel.r_offset);
1627    r_info = mcld::bswap32(pRel.r_info);
1628  }
1629
1630  pType = static_cast<unsigned char>(r_info);
1631  pSymIdx = (r_info >> 8);
1632  return true;
1633}
1634
1635/// readRelocation - read ELF32_Rela entry
1636bool GNULDBackend::readRelocation(const llvm::ELF::Elf32_Rela& pRel,
1637                                  Relocation::Type& pType,
1638                                  uint32_t& pSymIdx,
1639                                  uint32_t& pOffset,
1640                                  int32_t& pAddend) const {
1641  uint32_t r_info = 0x0;
1642  if (llvm::sys::IsLittleEndianHost) {
1643    pOffset = pRel.r_offset;
1644    r_info = pRel.r_info;
1645    pAddend = pRel.r_addend;
1646  } else {
1647    pOffset = mcld::bswap32(pRel.r_offset);
1648    r_info = mcld::bswap32(pRel.r_info);
1649    pAddend = mcld::bswap32(pRel.r_addend);
1650  }
1651
1652  pType = static_cast<unsigned char>(r_info);
1653  pSymIdx = (r_info >> 8);
1654  return true;
1655}
1656
1657/// readRelocation - read ELF64_Rel entry
1658bool GNULDBackend::readRelocation(const llvm::ELF::Elf64_Rel& pRel,
1659                                  Relocation::Type& pType,
1660                                  uint32_t& pSymIdx,
1661                                  uint64_t& pOffset) const {
1662  uint64_t r_info = 0x0;
1663  if (llvm::sys::IsLittleEndianHost) {
1664    pOffset = pRel.r_offset;
1665    r_info = pRel.r_info;
1666  } else {
1667    pOffset = mcld::bswap64(pRel.r_offset);
1668    r_info = mcld::bswap64(pRel.r_info);
1669  }
1670
1671  pType = static_cast<uint32_t>(r_info);
1672  pSymIdx = (r_info >> 32);
1673  return true;
1674}
1675
1676/// readRel - read ELF64_Rela entry
1677bool GNULDBackend::readRelocation(const llvm::ELF::Elf64_Rela& pRel,
1678                                  Relocation::Type& pType,
1679                                  uint32_t& pSymIdx,
1680                                  uint64_t& pOffset,
1681                                  int64_t& pAddend) const {
1682  uint64_t r_info = 0x0;
1683  if (llvm::sys::IsLittleEndianHost) {
1684    pOffset = pRel.r_offset;
1685    r_info = pRel.r_info;
1686    pAddend = pRel.r_addend;
1687  } else {
1688    pOffset = mcld::bswap64(pRel.r_offset);
1689    r_info = mcld::bswap64(pRel.r_info);
1690    pAddend = mcld::bswap64(pRel.r_addend);
1691  }
1692
1693  pType = static_cast<uint32_t>(r_info);
1694  pSymIdx = (r_info >> 32);
1695  return true;
1696}
1697
1698/// emitRelocation - write data to the ELF32_Rel entry
1699void GNULDBackend::emitRelocation(llvm::ELF::Elf32_Rel& pRel,
1700                                  Relocation::Type pType,
1701                                  uint32_t pSymIdx,
1702                                  uint32_t pOffset) const {
1703  pRel.r_offset = pOffset;
1704  pRel.setSymbolAndType(pSymIdx, pType);
1705}
1706
1707/// emitRelocation - write data to the ELF32_Rela entry
1708void GNULDBackend::emitRelocation(llvm::ELF::Elf32_Rela& pRel,
1709                                  Relocation::Type pType,
1710                                  uint32_t pSymIdx,
1711                                  uint32_t pOffset,
1712                                  int32_t pAddend) const {
1713  pRel.r_offset = pOffset;
1714  pRel.r_addend = pAddend;
1715  pRel.setSymbolAndType(pSymIdx, pType);
1716}
1717
1718/// emitRelocation - write data to the ELF64_Rel entry
1719void GNULDBackend::emitRelocation(llvm::ELF::Elf64_Rel& pRel,
1720                                  Relocation::Type pType,
1721                                  uint32_t pSymIdx,
1722                                  uint64_t pOffset) const {
1723  pRel.r_offset = pOffset;
1724  pRel.setSymbolAndType(pSymIdx, pType);
1725}
1726
1727/// emitRelocation - write data to the ELF64_Rela entry
1728void GNULDBackend::emitRelocation(llvm::ELF::Elf64_Rela& pRel,
1729                                  Relocation::Type pType,
1730                                  uint32_t pSymIdx,
1731                                  uint64_t pOffset,
1732                                  int64_t pAddend) const {
1733  pRel.r_offset = pOffset;
1734  pRel.r_addend = pAddend;
1735  pRel.setSymbolAndType(pSymIdx, pType);
1736}
1737
1738/// createProgramHdrs - base on output sections to create the program headers
1739void GNULDBackend::createProgramHdrs(Module& pModule) {
1740  ELFFileFormat* file_format = getOutputFormat();
1741
1742  // make PT_INTERP
1743  if (file_format->hasInterp()) {
1744    // make PT_PHDR
1745    elfSegmentTable().produce(llvm::ELF::PT_PHDR);
1746
1747    ELFSegment* interp_seg = elfSegmentTable().produce(llvm::ELF::PT_INTERP);
1748    interp_seg->append(&file_format->getInterp());
1749  }
1750
1751  uint32_t cur_flag, prev_flag = 0x0;
1752  ELFSegment* load_seg = NULL;
1753  // make possible PT_LOAD segments
1754  LinkerScript& ldscript = pModule.getScript();
1755  LinkerScript::AddressMap::iterator addrEnd = ldscript.addressMap().end();
1756  SectionMap::iterator out, prev, outBegin, outEnd;
1757  outBegin = ldscript.sectionMap().begin();
1758  outEnd = ldscript.sectionMap().end();
1759  for (out = outBegin, prev = outEnd; out != outEnd; prev = out, ++out) {
1760    LDSection* sect = (*out)->getSection();
1761
1762    if (0 == (sect->flag() & llvm::ELF::SHF_ALLOC) &&
1763        LDFileFormat::Null != sect->kind())
1764      break;
1765
1766    // bypass empty sections
1767    if (!(*out)->hasContent() &&
1768        (*out)->getSection()->kind() != LDFileFormat::Null)
1769      continue;
1770
1771    cur_flag = getSegmentFlag(sect->flag());
1772    bool createPT_LOAD = false;
1773    if (LDFileFormat::Null == sect->kind()) {
1774      // 1. create text segment
1775      createPT_LOAD = true;
1776    } else if (!config().options().omagic() &&
1777               (prev_flag & llvm::ELF::PF_W) ^ (cur_flag & llvm::ELF::PF_W)) {
1778      // 2. create data segment if w/o omagic set
1779      createPT_LOAD = true;
1780    } else if (sect->kind() == LDFileFormat::BSS && load_seg->isDataSegment() &&
1781               addrEnd != ldscript.addressMap().find(".bss")) {
1782      // 3. create bss segment if w/ -Tbss and there is a data segment
1783      createPT_LOAD = true;
1784    } else if ((sect != &(file_format->getText())) &&
1785               (sect != &(file_format->getData())) &&
1786               (sect != &(file_format->getBSS())) &&
1787               (addrEnd != ldscript.addressMap().find(sect->name()))) {
1788      // 4. create PT_LOAD for sections in address map except for text, data,
1789      // and bss
1790      createPT_LOAD = true;
1791    } else if (LDFileFormat::Null == (*prev)->getSection()->kind() &&
1792               !config().options().getScriptList().empty()) {
1793      // 5. create PT_LOAD to hold NULL section if there is a default ldscript
1794      createPT_LOAD = true;
1795    }
1796
1797    if (createPT_LOAD) {
1798      // create new PT_LOAD segment
1799      load_seg = elfSegmentTable().produce(llvm::ELF::PT_LOAD, cur_flag);
1800      if (!config().options().nmagic() && !config().options().omagic())
1801        load_seg->setAlign(abiPageSize());
1802    }
1803
1804    assert(load_seg != NULL);
1805    load_seg->append(sect);
1806    if (cur_flag != prev_flag)
1807      load_seg->updateFlag(cur_flag);
1808
1809    prev_flag = cur_flag;
1810  }
1811
1812  // make PT_DYNAMIC
1813  if (file_format->hasDynamic()) {
1814    ELFSegment* dyn_seg = elfSegmentTable().produce(
1815        llvm::ELF::PT_DYNAMIC, llvm::ELF::PF_R | llvm::ELF::PF_W);
1816    dyn_seg->append(&file_format->getDynamic());
1817  }
1818
1819  if (config().options().hasRelro()) {
1820    // make PT_GNU_RELRO
1821    ELFSegment* relro_seg = elfSegmentTable().produce(llvm::ELF::PT_GNU_RELRO);
1822    for (ELFSegmentFactory::iterator seg = elfSegmentTable().begin(),
1823                                     segEnd = elfSegmentTable().end();
1824         seg != segEnd;
1825         ++seg) {
1826      if (llvm::ELF::PT_LOAD != (*seg)->type())
1827        continue;
1828
1829      for (ELFSegment::iterator sect = (*seg)->begin(), sectEnd = (*seg)->end();
1830           sect != sectEnd;
1831           ++sect) {
1832        unsigned int order = getSectionOrder(**sect);
1833        if (SHO_RELRO_LOCAL == order || SHO_RELRO == order ||
1834            SHO_RELRO_LAST == order) {
1835          relro_seg->append(*sect);
1836        }
1837      }
1838    }
1839  }
1840
1841  // make PT_GNU_EH_FRAME
1842  if (file_format->hasEhFrameHdr()) {
1843    ELFSegment* eh_seg = elfSegmentTable().produce(llvm::ELF::PT_GNU_EH_FRAME);
1844    eh_seg->append(&file_format->getEhFrameHdr());
1845  }
1846
1847  // make PT_TLS
1848  if (file_format->hasTData() || file_format->hasTBSS()) {
1849    ELFSegment* tls_seg = elfSegmentTable().produce(llvm::ELF::PT_TLS);
1850    if (file_format->hasTData())
1851      tls_seg->append(&file_format->getTData());
1852    if (file_format->hasTBSS())
1853      tls_seg->append(&file_format->getTBSS());
1854  }
1855
1856  // make PT_GNU_STACK
1857  if (file_format->hasStackNote()) {
1858    uint32_t flag = getSegmentFlag(file_format->getStackNote().flag());
1859    elfSegmentTable().produce(llvm::ELF::PT_GNU_STACK,
1860                              llvm::ELF::PF_R | llvm::ELF::PF_W | flag);
1861  }
1862
1863  // make PT_NOTE
1864  ELFSegment* note_seg = NULL;
1865  prev_flag = 0x0;
1866  Module::iterator sect, sectBegin, sectEnd;
1867  sectBegin = pModule.begin();
1868  sectEnd = pModule.end();
1869  for (sect = sectBegin; sect != sectEnd; ++sect) {
1870    if ((*sect)->type() != llvm::ELF::SHT_NOTE ||
1871        ((*sect)->flag() & llvm::ELF::SHF_ALLOC) == 0)
1872      continue;
1873
1874    cur_flag = getSegmentFlag((*sect)->flag());
1875    // we have different section orders for read-only and writable notes, so
1876    // create 2 segments if needed.
1877    if (note_seg == NULL ||
1878        (cur_flag & llvm::ELF::PF_W) != (prev_flag & llvm::ELF::PF_W))
1879      note_seg = elfSegmentTable().produce(llvm::ELF::PT_NOTE, cur_flag);
1880
1881    note_seg->append(*sect);
1882    prev_flag = cur_flag;
1883  }
1884
1885  // create target dependent segments
1886  doCreateProgramHdrs(pModule);
1887}
1888
1889/// setupProgramHdrs - set up the attributes of segments
1890void GNULDBackend::setupProgramHdrs(const LinkerScript& pScript) {
1891  // update segment info
1892  for (ELFSegmentFactory::iterator seg = elfSegmentTable().begin(),
1893                                   segEnd = elfSegmentTable().end();
1894       seg != segEnd;
1895       ++seg) {
1896    // bypass if there is no section in this segment (e.g., PT_GNU_STACK)
1897    if ((*seg)->size() == 0)
1898      continue;
1899
1900    // bypass the PT_LOAD that only has NULL section now
1901    if ((*seg)->type() == llvm::ELF::PT_LOAD &&
1902        (*seg)->front()->kind() == LDFileFormat::Null && (*seg)->size() == 1)
1903      continue;
1904
1905    (*seg)->setOffset((*seg)->front()->offset());
1906    if ((*seg)->type() == llvm::ELF::PT_LOAD &&
1907        (*seg)->front()->kind() == LDFileFormat::Null) {
1908      const LDSection* second = *((*seg)->begin() + 1);
1909      assert(second != NULL);
1910      (*seg)->setVaddr(second->addr() - second->offset());
1911    } else {
1912      (*seg)->setVaddr((*seg)->front()->addr());
1913    }
1914    (*seg)->setPaddr((*seg)->vaddr());
1915
1916    ELFSegment::reverse_iterator sect, sectREnd = (*seg)->rend();
1917    for (sect = (*seg)->rbegin(); sect != sectREnd; ++sect) {
1918      if ((*sect)->kind() != LDFileFormat::BSS)
1919        break;
1920    }
1921    if (sect != sectREnd) {
1922      (*seg)->setFilesz((*sect)->offset() + (*sect)->size() - (*seg)->offset());
1923    } else {
1924      (*seg)->setFilesz(0x0);
1925    }
1926
1927    (*seg)->setMemsz((*seg)->back()->addr() + (*seg)->back()->size() -
1928                     (*seg)->vaddr());
1929  }  // end of for
1930
1931  // handle the case if text segment only has NULL section
1932  LDSection* null_sect = &getOutputFormat()->getNULLSection();
1933  ELFSegmentFactory::iterator null_seg =
1934      elfSegmentTable().find(llvm::ELF::PT_LOAD, null_sect);
1935
1936  if ((*null_seg)->size() == 1) {
1937    // find 2nd PT_LOAD
1938    ELFSegmentFactory::iterator seg, segEnd = elfSegmentTable().end();
1939    for (seg = null_seg + 1; seg != segEnd; ++seg) {
1940      if ((*seg)->type() == llvm::ELF::PT_LOAD)
1941        break;
1942    }
1943    if (seg != segEnd) {
1944      uint64_t addr = (*seg)->front()->addr() - (*seg)->front()->offset();
1945      uint64_t size = sectionStartOffset();
1946      if (addr + size == (*seg)->front()->addr()) {
1947        // if there is no space between the 2 segments, we can merge them.
1948        (*seg)->setOffset(0x0);
1949        (*seg)->setVaddr(addr);
1950        (*seg)->setPaddr(addr);
1951
1952        ELFSegment::iterator sect, sectEnd = (*seg)->end();
1953        for (sect = (*seg)->begin(); sect != sectEnd; ++sect) {
1954          if ((*sect)->kind() == LDFileFormat::BSS) {
1955            --sect;
1956            break;
1957          }
1958        }
1959        if (sect == sectEnd) {
1960          (*seg)->setFilesz((*seg)->back()->offset() + (*seg)->back()->size() -
1961                            (*seg)->offset());
1962        } else if (*sect != (*seg)->front()) {
1963          --sect;
1964          (*seg)->setFilesz((*sect)->offset() + (*sect)->size() -
1965                            (*seg)->offset());
1966        } else {
1967          (*seg)->setFilesz(0x0);
1968        }
1969
1970        (*seg)->setMemsz((*seg)->back()->addr() + (*seg)->back()->size() -
1971                         (*seg)->vaddr());
1972
1973        (*seg)->insert((*seg)->begin(), null_sect);
1974        elfSegmentTable().erase(null_seg);
1975
1976      } else if (addr + size < (*seg)->vaddr()) {
1977        (*null_seg)->setOffset(0x0);
1978        (*null_seg)->setVaddr(addr);
1979        (*null_seg)->setPaddr(addr);
1980        (*null_seg)->setFilesz(size);
1981        (*null_seg)->setMemsz(size);
1982      } else {
1983        // erase the non valid segment contains NULL.
1984        elfSegmentTable().erase(null_seg);
1985      }
1986    }
1987  }
1988
1989  // set up PT_PHDR
1990  ELFSegmentFactory::iterator phdr =
1991      elfSegmentTable().find(llvm::ELF::PT_PHDR, llvm::ELF::PF_R, 0x0);
1992
1993  if (phdr != elfSegmentTable().end()) {
1994    ELFSegmentFactory::iterator null_seg =
1995        elfSegmentTable().find(llvm::ELF::PT_LOAD, null_sect);
1996    if (null_seg != elfSegmentTable().end()) {
1997      uint64_t offset = 0x0, phdr_size = 0x0;
1998      if (config().targets().is32Bits()) {
1999        offset = sizeof(llvm::ELF::Elf32_Ehdr);
2000        phdr_size = sizeof(llvm::ELF::Elf32_Phdr);
2001      } else {
2002        offset = sizeof(llvm::ELF::Elf64_Ehdr);
2003        phdr_size = sizeof(llvm::ELF::Elf64_Phdr);
2004      }
2005      (*phdr)->setOffset(offset);
2006      (*phdr)->setVaddr((*null_seg)->vaddr() + offset);
2007      (*phdr)->setPaddr((*phdr)->vaddr());
2008      (*phdr)->setFilesz(elfSegmentTable().size() * phdr_size);
2009      (*phdr)->setMemsz(elfSegmentTable().size() * phdr_size);
2010      (*phdr)->setAlign(config().targets().bitclass() / 8);
2011    } else {
2012      elfSegmentTable().erase(phdr);
2013    }
2014  }
2015}
2016
2017/// getSegmentFlag - give a section flag and return the corresponding segment
2018/// flag
2019uint32_t GNULDBackend::getSegmentFlag(const uint32_t pSectionFlag) {
2020  uint32_t flag = 0x0;
2021  if ((pSectionFlag & llvm::ELF::SHF_ALLOC) != 0x0)
2022    flag |= llvm::ELF::PF_R;
2023  if ((pSectionFlag & llvm::ELF::SHF_WRITE) != 0x0)
2024    flag |= llvm::ELF::PF_W;
2025  if ((pSectionFlag & llvm::ELF::SHF_EXECINSTR) != 0x0)
2026    flag |= llvm::ELF::PF_X;
2027  return flag;
2028}
2029
2030/// setupGNUStackInfo - setup the section flag of .note.GNU-stack in output
2031void GNULDBackend::setupGNUStackInfo(Module& pModule) {
2032  uint32_t flag = 0x0;
2033  if (config().options().hasStackSet()) {
2034    // 1. check the command line option (-z execstack or -z noexecstack)
2035    if (config().options().hasExecStack())
2036      flag = llvm::ELF::SHF_EXECINSTR;
2037  } else {
2038    // 2. check the stack info from the input objects
2039    // FIXME: since we alway emit .note.GNU-stack in output now, we may be able
2040    // to check this from the output .note.GNU-stack directly after section
2041    // merging is done
2042    size_t object_count = 0, stack_note_count = 0;
2043    Module::const_obj_iterator obj, objEnd = pModule.obj_end();
2044    for (obj = pModule.obj_begin(); obj != objEnd; ++obj) {
2045      ++object_count;
2046      const LDSection* sect = (*obj)->context()->getSection(".note.GNU-stack");
2047      if (sect != NULL) {
2048        ++stack_note_count;
2049        // 2.1 found a stack note that is set as executable
2050        if (0 != (llvm::ELF::SHF_EXECINSTR & sect->flag())) {
2051          flag = llvm::ELF::SHF_EXECINSTR;
2052          break;
2053        }
2054      }
2055    }
2056
2057    // 2.2 there are no stack note sections in all input objects
2058    if (0 == stack_note_count)
2059      return;
2060
2061    // 2.3 a special case. Use the target default to decide if the stack should
2062    //     be executable
2063    if (llvm::ELF::SHF_EXECINSTR != flag && object_count != stack_note_count)
2064      if (m_pInfo->isDefaultExecStack())
2065        flag = llvm::ELF::SHF_EXECINSTR;
2066  }
2067
2068  if (getOutputFormat()->hasStackNote()) {
2069    getOutputFormat()->getStackNote().setFlag(flag);
2070  }
2071}
2072
2073/// setOutputSectionOffset - helper function to set output sections' offset.
2074void GNULDBackend::setOutputSectionOffset(Module& pModule) {
2075  LinkerScript& script = pModule.getScript();
2076  uint64_t offset = 0x0;
2077  LDSection* cur = NULL;
2078  LDSection* prev = NULL;
2079  SectionMap::iterator out, outBegin, outEnd;
2080  outBegin = script.sectionMap().begin();
2081  outEnd = script.sectionMap().end();
2082  for (out = outBegin; out != outEnd; ++out, prev = cur) {
2083    cur = (*out)->getSection();
2084    if (cur->kind() == LDFileFormat::Null) {
2085      cur->setOffset(0x0);
2086      continue;
2087    }
2088
2089    switch (prev->kind()) {
2090      case LDFileFormat::Null:
2091        offset = sectionStartOffset();
2092        break;
2093      case LDFileFormat::BSS:
2094        offset = prev->offset();
2095        break;
2096      default:
2097        offset = prev->offset() + prev->size();
2098        break;
2099    }
2100    alignAddress(offset, cur->align());
2101    cur->setOffset(offset);
2102  }
2103}
2104
2105/// setOutputSectionAddress - helper function to set output sections' address.
2106void GNULDBackend::setOutputSectionAddress(Module& pModule) {
2107  RpnEvaluator evaluator(pModule, *this);
2108  LinkerScript& script = pModule.getScript();
2109  uint64_t vma = 0x0, offset = 0x0;
2110  LDSection* cur = NULL;
2111  LDSection* prev = NULL;
2112  LinkerScript::AddressMap::iterator addr, addrEnd = script.addressMap().end();
2113  ELFSegmentFactory::iterator seg, segEnd = elfSegmentTable().end();
2114  SectionMap::Output::dot_iterator dot;
2115  SectionMap::iterator out, outBegin, outEnd;
2116  outBegin = script.sectionMap().begin();
2117  outEnd = script.sectionMap().end();
2118  for (out = outBegin; out != outEnd; prev = cur, ++out) {
2119    cur = (*out)->getSection();
2120
2121    if (cur->kind() == LDFileFormat::Null) {
2122      cur->setOffset(0x0);
2123      continue;
2124    }
2125
2126    // process dot assignments between 2 output sections
2127    for (SectionMap::Output::dot_iterator it = (*out)->dot_begin(),
2128                                          ie = (*out)->dot_end();
2129         it != ie;
2130         ++it) {
2131      (*it).assign(evaluator);
2132    }
2133
2134    seg = elfSegmentTable().find(llvm::ELF::PT_LOAD, cur);
2135    if (seg != segEnd && cur == (*seg)->front()) {
2136      if ((*seg)->isBssSegment())
2137        addr = script.addressMap().find(".bss");
2138      else if ((*seg)->isDataSegment())
2139        addr = script.addressMap().find(".data");
2140      else
2141        addr = script.addressMap().find(cur->name());
2142    } else
2143      addr = addrEnd;
2144
2145    if (addr != addrEnd) {
2146      // use address mapping in script options
2147      vma = addr.getEntry()->value();
2148    } else if ((*out)->prolog().hasVMA()) {
2149      // use address from output section description
2150      evaluator.eval((*out)->prolog().vma(), vma);
2151    } else if ((dot = (*out)->find_last_explicit_dot()) != (*out)->dot_end()) {
2152      // assign address based on `.' symbol in ldscript
2153      vma = (*dot).symbol().value();
2154      alignAddress(vma, cur->align());
2155    } else {
2156      if ((*out)->prolog().type() == OutputSectDesc::NOLOAD) {
2157        vma = prev->addr() + prev->size();
2158      } else if ((cur->flag() & llvm::ELF::SHF_ALLOC) != 0) {
2159        if (prev->kind() == LDFileFormat::Null) {
2160          // Let SECTIONS starts at 0 if we have a default ldscript but don't
2161          // have any initial value (VMA or `.').
2162          if (!config().options().getScriptList().empty())
2163            vma = 0x0;
2164          else
2165            vma = getSegmentStartAddr(script) + sectionStartOffset();
2166        } else {
2167          if ((prev->kind() == LDFileFormat::BSS))
2168            vma = prev->addr();
2169          else
2170            vma = prev->addr() + prev->size();
2171        }
2172        alignAddress(vma, cur->align());
2173        if (config().options().getScriptList().empty()) {
2174          if (seg != segEnd && cur == (*seg)->front()) {
2175            // Try to align p_vaddr at page boundary if not in script options.
2176            // To do so will add more padding in file, but can save one page
2177            // at runtime.
2178            // Avoid doing this optimization if -z relro is given, because there
2179            // seems to be too many padding.
2180            if (!config().options().hasRelro()) {
2181              alignAddress(vma, (*seg)->align());
2182            } else {
2183              vma += abiPageSize();
2184            }
2185          }
2186        }
2187      } else {
2188        vma = 0x0;
2189      }
2190    }
2191
2192    if (config().options().hasRelro()) {
2193      // if -z relro is given, we need to adjust sections' offset again, and
2194      // let PT_GNU_RELRO end on a abi page boundary
2195
2196      // check if current is the first non-relro section
2197      SectionMap::iterator relro_last = out - 1;
2198      if (relro_last != outEnd && (*relro_last)->order() <= SHO_RELRO_LAST &&
2199          (*out)->order() > SHO_RELRO_LAST) {
2200        // align the first non-relro section to page boundary
2201        alignAddress(vma, abiPageSize());
2202
2203        // It seems that compiler think .got and .got.plt are continuous (w/o
2204        // any padding between). If .got is the last section in PT_RELRO and
2205        // it's not continuous to its next section (i.e. .got.plt), we need to
2206        // add padding in front of .got instead.
2207        // FIXME: Maybe we can handle this in a more general way.
2208        LDSection& got = getOutputFormat()->getGOT();
2209        if ((getSectionOrder(got) == SHO_RELRO_LAST) &&
2210            (got.addr() + got.size() < vma)) {
2211          uint64_t diff = vma - got.addr() - got.size();
2212          got.setAddr(vma - got.size());
2213          got.setOffset(got.offset() + diff);
2214        }
2215      }
2216    }  // end of if - for relro processing
2217
2218    cur->setAddr(vma);
2219
2220    switch (prev->kind()) {
2221      case LDFileFormat::Null:
2222        offset = sectionStartOffset();
2223        break;
2224      case LDFileFormat::BSS:
2225        offset = prev->offset();
2226        break;
2227      default:
2228        offset = prev->offset() + prev->size();
2229        break;
2230    }
2231    alignAddress(offset, cur->align());
2232    // in p75, http://www.sco.com/developers/devspecs/gabi41.pdf
2233    // p_align: As "Program Loading" describes in this chapter of the
2234    // processor supplement, loadable process segments must have congruent
2235    // values for p_vaddr and p_offset, modulo the page size.
2236    // FIXME: Now make all sh_addr and sh_offset are congruent, modulo the page
2237    // size. Otherwise, old objcopy (e.g., binutils 2.17) may fail with our
2238    // output!
2239    if ((cur->flag() & llvm::ELF::SHF_ALLOC) != 0 &&
2240        (vma & (abiPageSize() - 1)) != (offset & (abiPageSize() - 1))) {
2241      uint64_t padding = abiPageSize() + (vma & (abiPageSize() - 1)) -
2242                         (offset & (abiPageSize() - 1));
2243      offset += padding;
2244    }
2245
2246    cur->setOffset(offset);
2247
2248    // process dot assignments in the output section
2249    bool changed = false;
2250    Fragment* invalid = NULL;
2251    for (SectionMap::Output::iterator in = (*out)->begin(),
2252                                      inEnd = (*out)->end();
2253         in != inEnd;
2254         ++in) {
2255      if (invalid != NULL && !(*in)->dotAssignments().empty()) {
2256        while (invalid != (*in)->dotAssignments().front().first) {
2257          Fragment* prev = invalid->getPrevNode();
2258          invalid->setOffset(prev->getOffset() + prev->size());
2259          invalid = invalid->getNextNode();
2260        }
2261        invalid = NULL;
2262      }
2263
2264      for (SectionMap::Input::dot_iterator it = (*in)->dot_begin(),
2265                                           ie = (*in)->dot_end();
2266           it != ie;
2267           ++it) {
2268        (*it).second.assign(evaluator);
2269        if ((*it).first != NULL) {
2270          uint64_t new_offset = (*it).second.symbol().value() - vma;
2271          if (new_offset != (*it).first->getOffset()) {
2272            (*it).first->setOffset(new_offset);
2273            invalid = (*it).first->getNextNode();
2274            changed = true;
2275          }
2276        }
2277      }  // for each dot assignment
2278    }    // for each input description
2279
2280    if (changed) {
2281      while (invalid != NULL) {
2282        Fragment* prev = invalid->getPrevNode();
2283        invalid->setOffset(prev->getOffset() + prev->size());
2284        invalid = invalid->getNextNode();
2285      }
2286
2287      cur->setSize(cur->getSectionData()->back().getOffset() +
2288                   cur->getSectionData()->back().size());
2289    }
2290  }  // for each output section description
2291}
2292
2293/// placeOutputSections - place output sections based on SectionMap
2294void GNULDBackend::placeOutputSections(Module& pModule) {
2295  typedef std::vector<LDSection*> Orphans;
2296  Orphans orphans;
2297  SectionMap& sectionMap = pModule.getScript().sectionMap();
2298
2299  for (Module::iterator it = pModule.begin(), ie = pModule.end(); it != ie;
2300       ++it) {
2301    bool wanted = false;
2302
2303    switch ((*it)->kind()) {
2304      // take NULL and StackNote directly
2305      case LDFileFormat::Null:
2306      case LDFileFormat::StackNote:
2307        wanted = true;
2308        break;
2309      // ignore if section size is 0
2310      case LDFileFormat::EhFrame:
2311        if (((*it)->size() != 0) ||
2312            ((*it)->hasEhFrame() &&
2313             config().codeGenType() == LinkerConfig::Object))
2314          wanted = true;
2315        break;
2316      case LDFileFormat::Relocation:
2317        if (((*it)->size() != 0) ||
2318            ((*it)->hasRelocData() &&
2319             config().codeGenType() == LinkerConfig::Object))
2320          wanted = true;
2321        break;
2322      case LDFileFormat::TEXT:
2323      case LDFileFormat::DATA:
2324      case LDFileFormat::Target:
2325      case LDFileFormat::MetaData:
2326      case LDFileFormat::BSS:
2327      case LDFileFormat::Debug:
2328      case LDFileFormat::DebugString:
2329      case LDFileFormat::GCCExceptTable:
2330      case LDFileFormat::Note:
2331      case LDFileFormat::NamePool:
2332      case LDFileFormat::EhFrameHdr:
2333        if (((*it)->size() != 0) ||
2334            ((*it)->hasSectionData() &&
2335             config().codeGenType() == LinkerConfig::Object))
2336          wanted = true;
2337        break;
2338      case LDFileFormat::Group:
2339        if (LinkerConfig::Object == config().codeGenType()) {
2340          // TODO: support incremental linking
2341        }
2342        break;
2343      case LDFileFormat::Version:
2344        if ((*it)->size() != 0) {
2345          wanted = true;
2346          warning(diag::warn_unsupported_symbolic_versioning) << (*it)->name();
2347        }
2348        break;
2349      default:
2350        if ((*it)->size() != 0) {
2351          error(diag::err_unsupported_section) << (*it)->name()
2352                                               << (*it)->kind();
2353        }
2354        break;
2355    }  // end of switch
2356
2357    if (wanted) {
2358      SectionMap::iterator out, outBegin, outEnd;
2359      outBegin = sectionMap.begin();
2360      outEnd = sectionMap.end();
2361      for (out = outBegin; out != outEnd; ++out) {
2362        bool matched = false;
2363        if ((*it)->name().compare((*out)->name()) == 0) {
2364          switch ((*out)->prolog().constraint()) {
2365            case OutputSectDesc::NO_CONSTRAINT:
2366              matched = true;
2367              break;
2368            case OutputSectDesc::ONLY_IF_RO:
2369              matched = ((*it)->flag() & llvm::ELF::SHF_WRITE) == 0;
2370              break;
2371            case OutputSectDesc::ONLY_IF_RW:
2372              matched = ((*it)->flag() & llvm::ELF::SHF_WRITE) != 0;
2373              break;
2374          }  // end of switch
2375
2376          if (matched)
2377            break;
2378        }
2379      }  // for each output section description
2380
2381      if (out != outEnd) {
2382        // set up the section
2383        (*out)->setSection(*it);
2384        (*out)->setOrder(getSectionOrder(**it));
2385      } else {
2386        orphans.push_back(*it);
2387      }
2388    }
2389  }  // for each section in Module
2390
2391  // set up sections in SectionMap but do not exist at all.
2392  uint32_t flag = 0x0;
2393  unsigned int order = SHO_UNDEFINED;
2394  OutputSectDesc::Type type = OutputSectDesc::LOAD;
2395  for (SectionMap::reverse_iterator out = sectionMap.rbegin(),
2396                                    outEnd = sectionMap.rend();
2397       out != outEnd;
2398       ++out) {
2399    if ((*out)->hasContent() ||
2400        (*out)->getSection()->kind() == LDFileFormat::Null ||
2401        (*out)->getSection()->kind() == LDFileFormat::StackNote) {
2402      flag = (*out)->getSection()->flag();
2403      order = (*out)->order();
2404      type = (*out)->prolog().type();
2405    } else {
2406      (*out)->getSection()->setFlag(flag);
2407      (*out)->setOrder(order);
2408      (*out)->prolog().setType(type);
2409    }
2410  }  // for each output section description
2411
2412  // place orphan sections
2413  for (Orphans::iterator it = orphans.begin(), ie = orphans.end(); it != ie;
2414       ++it) {
2415    size_t order = getSectionOrder(**it);
2416    SectionMap::iterator out, outBegin, outEnd;
2417    outBegin = sectionMap.begin();
2418    outEnd = sectionMap.end();
2419
2420    if ((*it)->kind() == LDFileFormat::Null)
2421      out = sectionMap.insert(outBegin, *it);
2422    else {
2423      for (out = outBegin; out != outEnd; ++out) {
2424        if ((*out)->order() > order)
2425          break;
2426      }
2427      out = sectionMap.insert(out, *it);
2428    }
2429    (*out)->setOrder(order);
2430  }  // for each orphan section
2431
2432  // sort output section orders if there is no default ldscript
2433  if (config().options().getScriptList().empty()) {
2434    std::stable_sort(
2435        sectionMap.begin(), sectionMap.end(), SectionMap::SHOCompare());
2436  }
2437
2438  // when section ordering is fixed, now we can make sure dot assignments are
2439  // all set appropriately
2440  sectionMap.fixupDotSymbols();
2441}
2442
2443/// layout - layout method
2444void GNULDBackend::layout(Module& pModule) {
2445  // 1. place output sections based on SectionMap from SECTIONS command
2446  placeOutputSections(pModule);
2447
2448  // 2. update output sections in Module
2449  SectionMap& sectionMap = pModule.getScript().sectionMap();
2450  pModule.getSectionTable().clear();
2451  for (SectionMap::iterator out = sectionMap.begin(), outEnd = sectionMap.end();
2452       out != outEnd;
2453       ++out) {
2454    if ((*out)->hasContent() ||
2455        (*out)->getSection()->kind() == LDFileFormat::Null ||
2456        (*out)->getSection()->kind() == LDFileFormat::StackNote ||
2457        config().codeGenType() == LinkerConfig::Object) {
2458      (*out)->getSection()->setIndex(pModule.size());
2459      pModule.getSectionTable().push_back((*out)->getSection());
2460    }
2461  }  // for each output section description
2462
2463  // 3. update the size of .shstrtab
2464  sizeShstrtab(pModule);
2465
2466  // 4. create program headers
2467  if (LinkerConfig::Object != config().codeGenType()) {
2468    createProgramHdrs(pModule);
2469  }
2470
2471  // 5. set output section address/offset
2472  if (LinkerConfig::Object != config().codeGenType())
2473    setOutputSectionAddress(pModule);
2474  else
2475    setOutputSectionOffset(pModule);
2476}
2477
2478void GNULDBackend::createAndSizeEhFrameHdr(Module& pModule) {
2479  if (LinkerConfig::Object != config().codeGenType() &&
2480      config().options().hasEhFrameHdr() && getOutputFormat()->hasEhFrame()) {
2481    // init EhFrameHdr and size the output section
2482    ELFFileFormat* format = getOutputFormat();
2483    m_pEhFrameHdr =
2484        new EhFrameHdr(format->getEhFrameHdr(), format->getEhFrame());
2485    m_pEhFrameHdr->sizeOutput();
2486  }
2487}
2488
2489/// mayHaveUnsafeFunctionPointerAccess - check if the section may have unsafe
2490/// function pointer access
2491bool GNULDBackend::mayHaveUnsafeFunctionPointerAccess(
2492    const LDSection& pSection) const {
2493  llvm::StringRef name(pSection.name());
2494  return !name.startswith(".rodata._ZTV") &&
2495         !name.startswith(".data.rel.ro._ZTV") &&
2496         !name.startswith(".rodata._ZTC") &&
2497         !name.startswith(".data.rel.ro._ZTC") && !name.startswith(".eh_frame");
2498}
2499
2500/// preLayout - Backend can do any needed modification before layout
2501void GNULDBackend::preLayout(Module& pModule, IRBuilder& pBuilder) {
2502  // prelayout target first
2503  doPreLayout(pBuilder);
2504
2505  // change .tbss and .tdata section symbol from Local to LocalDyn category
2506  if (f_pTDATA != NULL)
2507    pModule.getSymbolTable().changeToDynamic(*f_pTDATA);
2508
2509  if (f_pTBSS != NULL)
2510    pModule.getSymbolTable().changeToDynamic(*f_pTBSS);
2511
2512  // To merge input's relocation sections into output's relocation sections.
2513  //
2514  // If we are generating relocatables (-r), move input relocation sections
2515  // to corresponding output relocation sections.
2516  if (LinkerConfig::Object == config().codeGenType()) {
2517    Module::obj_iterator input, inEnd = pModule.obj_end();
2518    for (input = pModule.obj_begin(); input != inEnd; ++input) {
2519      LDContext::sect_iterator rs, rsEnd = (*input)->context()->relocSectEnd();
2520      for (rs = (*input)->context()->relocSectBegin(); rs != rsEnd; ++rs) {
2521        // get the output relocation LDSection with identical name.
2522        LDSection* output_sect = pModule.getSection((*rs)->name());
2523        if (output_sect == NULL) {
2524          output_sect = LDSection::Create(
2525              (*rs)->name(), (*rs)->kind(), (*rs)->type(), (*rs)->flag());
2526
2527          output_sect->setAlign((*rs)->align());
2528          pModule.getSectionTable().push_back(output_sect);
2529        }
2530
2531        // set output relocation section link
2532        const LDSection* input_link = (*rs)->getLink();
2533        assert(input_link != NULL && "Illegal input relocation section.");
2534
2535        // get the linked output section
2536        LDSection* output_link = pModule.getSection(input_link->name());
2537        assert(output_link != NULL);
2538
2539        output_sect->setLink(output_link);
2540
2541        // get output relcoationData, create one if not exist
2542        if (!output_sect->hasRelocData())
2543          IRBuilder::CreateRelocData(*output_sect);
2544
2545        RelocData* out_reloc_data = output_sect->getRelocData();
2546
2547        // move relocations from input's to output's RelcoationData
2548        RelocData::RelocationListType& out_list =
2549            out_reloc_data->getRelocationList();
2550        RelocData::RelocationListType& in_list =
2551            (*rs)->getRelocData()->getRelocationList();
2552        out_list.splice(out_list.end(), in_list);
2553
2554        // size output
2555        if (llvm::ELF::SHT_REL == output_sect->type())
2556          output_sect->setSize(out_reloc_data->size() * getRelEntrySize());
2557        else if (llvm::ELF::SHT_RELA == output_sect->type())
2558          output_sect->setSize(out_reloc_data->size() * getRelaEntrySize());
2559        else {
2560          fatal(diag::unknown_reloc_section_type) << output_sect->type()
2561                                                  << output_sect->name();
2562        }
2563      }  // end of for each relocation section
2564    }    // end of for each input
2565  }      // end of if
2566
2567  // set up the section flag of .note.GNU-stack section
2568  setupGNUStackInfo(pModule);
2569}
2570
2571/// postLayout - Backend can do any needed modification after layout
2572void GNULDBackend::postLayout(Module& pModule, IRBuilder& pBuilder) {
2573  if (LinkerConfig::Object != config().codeGenType()) {
2574    // do relaxation
2575    relax(pModule, pBuilder);
2576    // set up the attributes of program headers
2577    setupProgramHdrs(pModule.getScript());
2578  }
2579
2580  doPostLayout(pModule, pBuilder);
2581}
2582
2583void GNULDBackend::postProcessing(FileOutputBuffer& pOutput) {
2584  if (LinkerConfig::Object != config().codeGenType() &&
2585      config().options().hasEhFrameHdr() && getOutputFormat()->hasEhFrame()) {
2586    // emit eh_frame_hdr
2587    m_pEhFrameHdr->emitOutput<32>(pOutput);
2588  }
2589}
2590
2591/// getHashBucketCount - calculate hash bucket count.
2592unsigned GNULDBackend::getHashBucketCount(unsigned pNumOfSymbols,
2593                                          bool pIsGNUStyle) {
2594  static const unsigned int buckets[] = {
2595      1, 3, 17, 37, 67, 97, 131, 197, 263, 521, 1031, 2053, 4099, 8209, 16411,
2596      32771, 65537, 131101, 262147
2597  };
2598  const unsigned buckets_count = sizeof buckets / sizeof buckets[0];
2599
2600  unsigned int result = 1;
2601  for (unsigned i = 0; i < buckets_count; ++i) {
2602    if (pNumOfSymbols < buckets[i])
2603      break;
2604    result = buckets[i];
2605  }
2606
2607  if (pIsGNUStyle && result < 2)
2608    result = 2;
2609
2610  return result;
2611}
2612
2613/// getGNUHashMaskbitslog2 - calculate the number of mask bits in log2
2614unsigned GNULDBackend::getGNUHashMaskbitslog2(unsigned pNumOfSymbols) const {
2615  uint32_t maskbitslog2 = 1;
2616  for (uint32_t x = pNumOfSymbols >> 1; x != 0; x >>= 1)
2617    ++maskbitslog2;
2618
2619  if (maskbitslog2 < 3)
2620    maskbitslog2 = 5;
2621  else if (((1U << (maskbitslog2 - 2)) & pNumOfSymbols) != 0)
2622    maskbitslog2 += 3;
2623  else
2624    maskbitslog2 += 2;
2625
2626  if (config().targets().bitclass() == 64 && maskbitslog2 == 5)
2627    maskbitslog2 = 6;
2628
2629  return maskbitslog2;
2630}
2631
2632/// isDynamicSymbol
2633bool GNULDBackend::isDynamicSymbol(const LDSymbol& pSymbol) const {
2634  // If a local symbol is in the LDContext's symbol table, it's a real local
2635  // symbol. We should not add it
2636  if (pSymbol.binding() == ResolveInfo::Local)
2637    return false;
2638
2639  // If we are building shared object, and the visibility is external, we
2640  // need to add it.
2641  if (LinkerConfig::DynObj == config().codeGenType() ||
2642      LinkerConfig::Exec == config().codeGenType() ||
2643      LinkerConfig::Binary == config().codeGenType()) {
2644    if (pSymbol.resolveInfo()->visibility() == ResolveInfo::Default ||
2645        pSymbol.resolveInfo()->visibility() == ResolveInfo::Protected)
2646      return true;
2647  }
2648  return false;
2649}
2650
2651/// isDynamicSymbol
2652bool GNULDBackend::isDynamicSymbol(const ResolveInfo& pResolveInfo) const {
2653  // If a local symbol is in the LDContext's symbol table, it's a real local
2654  // symbol. We should not add it
2655  if (pResolveInfo.binding() == ResolveInfo::Local)
2656    return false;
2657
2658  // If we are building shared object, and the visibility is external, we
2659  // need to add it.
2660  if (LinkerConfig::DynObj == config().codeGenType() ||
2661      LinkerConfig::Exec == config().codeGenType() ||
2662      LinkerConfig::Binary == config().codeGenType()) {
2663    if (pResolveInfo.visibility() == ResolveInfo::Default ||
2664        pResolveInfo.visibility() == ResolveInfo::Protected)
2665      return true;
2666  }
2667  return false;
2668}
2669
2670/// elfSegmentTable - return the reference of the elf segment table
2671ELFSegmentFactory& GNULDBackend::elfSegmentTable() {
2672  assert(m_pELFSegmentTable != NULL && "Do not create ELFSegmentTable!");
2673  return *m_pELFSegmentTable;
2674}
2675
2676/// elfSegmentTable - return the reference of the elf segment table
2677const ELFSegmentFactory& GNULDBackend::elfSegmentTable() const {
2678  assert(m_pELFSegmentTable != NULL && "Do not create ELFSegmentTable!");
2679  return *m_pELFSegmentTable;
2680}
2681
2682/// commonPageSize - the common page size of the target machine.
2683uint64_t GNULDBackend::commonPageSize() const {
2684  if (config().options().commPageSize() > 0)
2685    return std::min(config().options().commPageSize(), abiPageSize());
2686  else
2687    return std::min(m_pInfo->commonPageSize(), abiPageSize());
2688}
2689
2690/// abiPageSize - the abi page size of the target machine.
2691uint64_t GNULDBackend::abiPageSize() const {
2692  if (config().options().maxPageSize() > 0)
2693    return config().options().maxPageSize();
2694  else
2695    return m_pInfo->abiPageSize();
2696}
2697
2698/// isSymbolPreemtible - whether the symbol can be preemted by other
2699/// link unit
2700bool GNULDBackend::isSymbolPreemptible(const ResolveInfo& pSym) const {
2701  if (pSym.other() != ResolveInfo::Default)
2702    return false;
2703
2704  // This is because the codeGenType of pie is DynObj. And gold linker check
2705  // the "shared" option instead.
2706  if (config().options().isPIE())
2707    return false;
2708
2709  if (LinkerConfig::DynObj != config().codeGenType())
2710    return false;
2711
2712  if (config().options().Bsymbolic())
2713    return false;
2714
2715  // A local defined symbol should be non-preemptible.
2716  // This issue is found when linking libstdc++ on freebsd. A R_386_GOT32
2717  // relocation refers to a local defined symbol, and we should generate a
2718  // relative dynamic relocation when applying the relocation.
2719  if (pSym.isDefine() && pSym.binding() == ResolveInfo::Local)
2720    return false;
2721
2722  return true;
2723}
2724
2725/// symbolNeedsDynRel - return whether the symbol needs a dynamic relocation
2726bool GNULDBackend::symbolNeedsDynRel(const ResolveInfo& pSym,
2727                                     bool pSymHasPLT,
2728                                     bool isAbsReloc) const {
2729  // an undefined reference in the executables should be statically
2730  // resolved to 0 and no need a dynamic relocation
2731  if (pSym.isUndef() && !pSym.isDyn() &&
2732      (LinkerConfig::Exec == config().codeGenType() ||
2733       LinkerConfig::Binary == config().codeGenType()))
2734    return false;
2735
2736  // An absolute symbol can be resolved directly if it is either local
2737  // or we are linking statically. Otherwise it can still be overridden
2738  // at runtime.
2739  if (pSym.isAbsolute() &&
2740      (pSym.binding() == ResolveInfo::Local || config().isCodeStatic()))
2741    return false;
2742  if (config().isCodeIndep() && isAbsReloc)
2743    return true;
2744  if (pSymHasPLT && ResolveInfo::Function == pSym.type())
2745    return false;
2746  if (!config().isCodeIndep() && pSymHasPLT)
2747    return false;
2748  if (pSym.isDyn() || pSym.isUndef() || isSymbolPreemptible(pSym))
2749    return true;
2750
2751  return false;
2752}
2753
2754/// symbolNeedsPLT - return whether the symbol needs a PLT entry
2755bool GNULDBackend::symbolNeedsPLT(const ResolveInfo& pSym) const {
2756  if (pSym.isUndef() && !pSym.isDyn() &&
2757      LinkerConfig::DynObj != config().codeGenType())
2758    return false;
2759
2760  // An IndirectFunc symbol (i.e., STT_GNU_IFUNC) always needs a plt entry
2761  if (pSym.type() == ResolveInfo::IndirectFunc)
2762    return true;
2763
2764  if (pSym.type() != ResolveInfo::Function)
2765    return false;
2766
2767  if (config().isCodeStatic())
2768    return false;
2769
2770  if (config().options().isPIE())
2771    return false;
2772
2773  return (pSym.isDyn() || pSym.isUndef() || isSymbolPreemptible(pSym));
2774}
2775
2776/// symbolHasFinalValue - return true if the symbol's value can be decided at
2777/// link time
2778bool GNULDBackend::symbolFinalValueIsKnown(const ResolveInfo& pSym) const {
2779  // if the output is pic code or if not executables, symbols' value may change
2780  // at runtime
2781  // FIXME: CodeIndep() || LinkerConfig::Relocatable == CodeGenType
2782  if (config().isCodeIndep() ||
2783      (LinkerConfig::Exec != config().codeGenType() &&
2784       LinkerConfig::Binary != config().codeGenType()))
2785    return false;
2786
2787  // if the symbol is from dynamic object, then its value is unknown
2788  if (pSym.isDyn())
2789    return false;
2790
2791  // if the symbol is not in dynamic object and is not undefined, then its value
2792  // is known
2793  if (!pSym.isUndef())
2794    return true;
2795
2796  // if the symbol is undefined and not in dynamic objects, for example, a weak
2797  // undefined symbol, then whether the symbol's final value can be known
2798  // depends on whrther we're doing static link
2799  return config().isCodeStatic();
2800}
2801
2802/// symbolNeedsCopyReloc - return whether the symbol needs a copy relocation
2803bool GNULDBackend::symbolNeedsCopyReloc(const Relocation& pReloc,
2804                                        const ResolveInfo& pSym) const {
2805  // only the reference from dynamic executable to non-function symbol in
2806  // the dynamic objects may need copy relocation
2807  if (config().isCodeIndep() || !pSym.isDyn() ||
2808      pSym.type() == ResolveInfo::Function || pSym.size() == 0)
2809    return false;
2810
2811  // check if the option -z nocopyreloc is given
2812  if (config().options().hasNoCopyReloc())
2813    return false;
2814
2815  // TODO: Is this check necessary?
2816  // if relocation target place is readonly, a copy relocation is needed
2817  uint32_t flag = pReloc.targetRef().frag()->getParent()->getSection().flag();
2818  if (0 == (flag & llvm::ELF::SHF_WRITE))
2819    return true;
2820
2821  return false;
2822}
2823
2824LDSymbol& GNULDBackend::getTDATASymbol() {
2825  assert(f_pTDATA != NULL);
2826  return *f_pTDATA;
2827}
2828
2829const LDSymbol& GNULDBackend::getTDATASymbol() const {
2830  assert(f_pTDATA != NULL);
2831  return *f_pTDATA;
2832}
2833
2834LDSymbol& GNULDBackend::getTBSSSymbol() {
2835  assert(f_pTBSS != NULL);
2836  return *f_pTBSS;
2837}
2838
2839const LDSymbol& GNULDBackend::getTBSSSymbol() const {
2840  assert(f_pTBSS != NULL);
2841  return *f_pTBSS;
2842}
2843
2844llvm::StringRef GNULDBackend::getEntry(const Module& pModule) const {
2845  if (pModule.getScript().hasEntry())
2846    return pModule.getScript().entry();
2847  else
2848    return getInfo().entry();
2849}
2850
2851void GNULDBackend::checkAndSetHasTextRel(const LDSection& pSection) {
2852  if (m_bHasTextRel)
2853    return;
2854
2855  // if the target section of the dynamic relocation is ALLOCATE but is not
2856  // writable, than we should set DF_TEXTREL
2857  const uint32_t flag = pSection.flag();
2858  if (0 == (flag & llvm::ELF::SHF_WRITE) && (flag & llvm::ELF::SHF_ALLOC))
2859    m_bHasTextRel = true;
2860
2861  return;
2862}
2863
2864/// sortRelocation - sort the dynamic relocations to let dynamic linker
2865/// process relocations more efficiently
2866void GNULDBackend::sortRelocation(LDSection& pSection) {
2867  if (!config().options().hasCombReloc())
2868    return;
2869
2870  assert(pSection.kind() == LDFileFormat::Relocation);
2871
2872  switch (config().codeGenType()) {
2873    case LinkerConfig::DynObj:
2874    case LinkerConfig::Exec:
2875      if (&pSection == &getOutputFormat()->getRelDyn() ||
2876          &pSection == &getOutputFormat()->getRelaDyn()) {
2877        if (pSection.hasRelocData())
2878          pSection.getRelocData()->sort(RelocCompare(*this));
2879      }
2880    default:
2881      return;
2882  }
2883}
2884
2885unsigned GNULDBackend::stubGroupSize() const {
2886  const unsigned group_size = config().targets().getStubGroupSize();
2887  if (group_size == 0) {
2888    return m_pInfo->stubGroupSize();
2889  } else {
2890    return group_size;
2891  }
2892}
2893
2894/// initBRIslandFactory - initialize the branch island factory for relaxation
2895bool GNULDBackend::initBRIslandFactory() {
2896  if (m_pBRIslandFactory == NULL) {
2897    m_pBRIslandFactory = new BranchIslandFactory(maxFwdBranchOffset(),
2898                                                 maxBwdBranchOffset(),
2899                                                 stubGroupSize());
2900  }
2901  return true;
2902}
2903
2904/// initStubFactory - initialize the stub factory for relaxation
2905bool GNULDBackend::initStubFactory() {
2906  if (m_pStubFactory == NULL) {
2907    m_pStubFactory = new StubFactory();
2908  }
2909  return true;
2910}
2911
2912bool GNULDBackend::relax(Module& pModule, IRBuilder& pBuilder) {
2913  if (!mayRelax())
2914    return true;
2915
2916  getBRIslandFactory()->group(pModule);
2917
2918  bool finished = true;
2919  do {
2920    if (doRelax(pModule, pBuilder, finished)) {
2921      setOutputSectionAddress(pModule);
2922    }
2923  } while (!finished);
2924
2925  return true;
2926}
2927
2928bool GNULDBackend::DynsymCompare::needGNUHash(const LDSymbol& X) const {
2929  // FIXME: in bfd and gold linker, an undefined symbol might be hashed
2930  // when the ouput is not PIC, if the symbol is referred by a non pc-relative
2931  // reloc, and its value is set to the addr of the plt entry.
2932  return !X.resolveInfo()->isUndef() && !X.isDyn();
2933}
2934
2935bool GNULDBackend::DynsymCompare::operator()(const LDSymbol* X,
2936                                             const LDSymbol* Y) const {
2937  return !needGNUHash(*X) && needGNUHash(*Y);
2938}
2939
2940bool GNULDBackend::RelocCompare::operator()(const Relocation& X,
2941                                            const Relocation& Y) const {
2942  // 1. compare if relocation is relative
2943  if (X.symInfo() == NULL) {
2944    if (Y.symInfo() != NULL)
2945      return true;
2946  } else if (Y.symInfo() == NULL) {
2947    return false;
2948  } else {
2949    // 2. compare the symbol index
2950    size_t symIdxX = m_Backend.getSymbolIdx(X.symInfo()->outSymbol());
2951    size_t symIdxY = m_Backend.getSymbolIdx(Y.symInfo()->outSymbol());
2952    if (symIdxX < symIdxY)
2953      return true;
2954    if (symIdxX > symIdxY)
2955      return false;
2956  }
2957
2958  // 3. compare the relocation address
2959  if (X.place() < Y.place())
2960    return true;
2961  if (X.place() > Y.place())
2962    return false;
2963
2964  // 4. compare the relocation type
2965  if (X.type() < Y.type())
2966    return true;
2967  if (X.type() > Y.type())
2968    return false;
2969
2970  // 5. compare the addend
2971  if (X.addend() < Y.addend())
2972    return true;
2973  if (X.addend() > Y.addend())
2974    return false;
2975
2976  return false;
2977}
2978
2979}  // namespace mcld
2980