GNULDBackend.cpp revision 37b74a387bb3993387029859c2d9d051c41c724e 
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    "ABCDEFGHIJKLMNOPWRSTUVWXYZ"
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::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 (GeneralOptions::GNU == config().options().getHashStyle() ||
779            GeneralOptions::Both == config().options().getHashStyle()) {
780          // count the number of dynsym to hash
781          size_t hashed_sym_cnt = 0;
782          symEnd = symbols.dynamicEnd();
783          for (symbol = symbols.dynamicBegin(); symbol != symEnd; ++symbol) {
784            if (DynsymCompare().needGNUHash(**symbol))
785              ++hashed_sym_cnt;
786          }
787          // Special case for empty .dynsym
788          if (hashed_sym_cnt == 0)
789            gnuhash = 5 * 4 + config().targets().bitclass() / 8;
790          else {
791            size_t nbucket = getHashBucketCount(hashed_sym_cnt, true);
792            gnuhash = (4 + nbucket + hashed_sym_cnt) * 4;
793            gnuhash += (1U << getGNUHashMaskbitslog2(hashed_sym_cnt)) / 8;
794          }
795        }
796
797        // compute .hash
798        if (GeneralOptions::SystemV == config().options().getHashStyle() ||
799            GeneralOptions::Both == config().options().getHashStyle()) {
800          // Both Elf32_Word and Elf64_Word are 4 bytes
801          hash = (2 + getHashBucketCount(dynsym, false) + dynsym) *
802                 sizeof(llvm::ELF::Elf32_Word);
803        }
804
805        // add DT_NEEDED
806        Module::const_lib_iterator lib, libEnd = pModule.lib_end();
807        for (lib = pModule.lib_begin(); lib != libEnd; ++lib) {
808          if (!(*lib)->attribute()->isAsNeeded() || (*lib)->isNeeded()) {
809            dynstr += (*lib)->name().size() + 1;
810            dynamic().reserveNeedEntry();
811          }
812        }
813
814        // add DT_RPATH
815        if (!config().options().getRpathList().empty()) {
816          dynamic().reserveNeedEntry();
817          GeneralOptions::const_rpath_iterator rpath,
818              rpathEnd = config().options().rpath_end();
819          for (rpath = config().options().rpath_begin(); rpath != rpathEnd;
820               ++rpath)
821            dynstr += (*rpath).size() + 1;
822        }
823
824        // set size
825        if (config().targets().is32Bits()) {
826          file_format->getDynSymTab().setSize(dynsym *
827                                              sizeof(llvm::ELF::Elf32_Sym));
828        } else {
829          file_format->getDynSymTab().setSize(dynsym *
830                                              sizeof(llvm::ELF::Elf64_Sym));
831        }
832        file_format->getDynStrTab().setSize(dynstr);
833        file_format->getHashTab().setSize(hash);
834        file_format->getGNUHashTab().setSize(gnuhash);
835
836        // set .dynsym sh_info to one greater than the symbol table
837        // index of the last local symbol
838        file_format->getDynSymTab().setInfo(dynsym_local_cnt);
839
840        // Because some entries in .dynamic section need information of .dynsym,
841        // .dynstr, .symtab, .strtab and .hash, we can not reserve non-DT_NEEDED
842        // entries until we get the size of the sections mentioned above
843        dynamic().reserveEntries(*file_format);
844        file_format->getDynamic().setSize(dynamic().numOfBytes());
845      }
846    }
847    /* fall through */
848    case LinkerConfig::Object: {
849      if (config().targets().is32Bits())
850        file_format->getSymTab().setSize(symtab * sizeof(llvm::ELF::Elf32_Sym));
851      else
852        file_format->getSymTab().setSize(symtab * sizeof(llvm::ELF::Elf64_Sym));
853      file_format->getStrTab().setSize(strtab);
854
855      // set .symtab sh_info to one greater than the symbol table
856      // index of the last local symbol
857      file_format->getSymTab().setInfo(symtab_local_cnt);
858
859      // The size of .shstrtab should be decided after output sections are all
860      // set, so we just set it to 1 here.
861      file_format->getShStrTab().setSize(0x1);
862      break;
863    }
864    default:
865      fatal(diag::fatal_illegal_codegen_type) << pModule.name();
866      break;
867  }  // end of switch
868}
869
870/// emitSymbol32 - emit an ELF32 symbol
871void GNULDBackend::emitSymbol32(llvm::ELF::Elf32_Sym& pSym,
872                                LDSymbol& pSymbol,
873                                char* pStrtab,
874                                size_t pStrtabsize,
875                                size_t pSymtabIdx) {
876  // FIXME: check the endian between host and target
877  // write out symbol
878  if (hasEntryInStrTab(pSymbol)) {
879    pSym.st_name = pStrtabsize;
880    ::memcpy((pStrtab + pStrtabsize), pSymbol.name(), pSymbol.nameSize());
881  } else {
882    pSym.st_name = 0;
883  }
884  pSym.st_value = pSymbol.value();
885  pSym.st_size = getSymbolSize(pSymbol);
886  pSym.st_info = getSymbolInfo(pSymbol);
887  pSym.st_other = pSymbol.visibility();
888  pSym.st_shndx = getSymbolShndx(pSymbol);
889}
890
891/// emitSymbol64 - emit an ELF64 symbol
892void GNULDBackend::emitSymbol64(llvm::ELF::Elf64_Sym& pSym,
893                                LDSymbol& pSymbol,
894                                char* pStrtab,
895                                size_t pStrtabsize,
896                                size_t pSymtabIdx) {
897  // FIXME: check the endian between host and target
898  // write out symbol
899  if (hasEntryInStrTab(pSymbol)) {
900    pSym.st_name = pStrtabsize;
901    ::memcpy((pStrtab + pStrtabsize), pSymbol.name(), pSymbol.nameSize());
902  } else {
903    pSym.st_name = 0;
904  }
905  pSym.st_value = pSymbol.value();
906  pSym.st_size = getSymbolSize(pSymbol);
907  pSym.st_info = getSymbolInfo(pSymbol);
908  pSym.st_other = pSymbol.visibility();
909  pSym.st_shndx = getSymbolShndx(pSymbol);
910}
911
912/// emitRegNamePools - emit regular name pools - .symtab, .strtab
913///
914/// the size of these tables should be computed before layout
915/// layout should computes the start offset of these tables
916void GNULDBackend::emitRegNamePools(const Module& pModule,
917                                    FileOutputBuffer& pOutput) {
918  ELFFileFormat* file_format = getOutputFormat();
919  if (!file_format->hasSymTab())
920    return;
921
922  LDSection& symtab_sect = file_format->getSymTab();
923  LDSection& strtab_sect = file_format->getStrTab();
924
925  MemoryRegion symtab_region =
926      pOutput.request(symtab_sect.offset(), symtab_sect.size());
927  MemoryRegion strtab_region =
928      pOutput.request(strtab_sect.offset(), strtab_sect.size());
929
930  // set up symtab_region
931  llvm::ELF::Elf32_Sym* symtab32 = NULL;
932  llvm::ELF::Elf64_Sym* symtab64 = NULL;
933  if (config().targets().is32Bits())
934    symtab32 = (llvm::ELF::Elf32_Sym*)symtab_region.begin();
935  else if (config().targets().is64Bits())
936    symtab64 = (llvm::ELF::Elf64_Sym*)symtab_region.begin();
937  else {
938    fatal(diag::unsupported_bitclass) << config().targets().triple().str()
939                                      << config().targets().bitclass();
940  }
941
942  // set up strtab_region
943  char* strtab = reinterpret_cast<char*>(strtab_region.begin());
944
945  // emit the first ELF symbol
946  if (config().targets().is32Bits())
947    emitSymbol32(symtab32[0], *LDSymbol::Null(), strtab, 0, 0);
948  else
949    emitSymbol64(symtab64[0], *LDSymbol::Null(), strtab, 0, 0);
950
951  bool sym_exist = false;
952  HashTableType::entry_type* entry = NULL;
953  if (LinkerConfig::Object == config().codeGenType()) {
954    entry = m_pSymIndexMap->insert(LDSymbol::Null(), sym_exist);
955    entry->setValue(0);
956  }
957
958  size_t symIdx = 1;
959  size_t strtabsize = 1;
960
961  const Module::SymbolTable& symbols = pModule.getSymbolTable();
962  Module::const_sym_iterator symbol, symEnd;
963
964  symEnd = symbols.end();
965  for (symbol = symbols.begin(); symbol != symEnd; ++symbol) {
966    if (LinkerConfig::Object == config().codeGenType()) {
967      entry = m_pSymIndexMap->insert(*symbol, sym_exist);
968      entry->setValue(symIdx);
969    }
970    if (config().targets().is32Bits())
971      emitSymbol32(symtab32[symIdx], **symbol, strtab, strtabsize, symIdx);
972    else
973      emitSymbol64(symtab64[symIdx], **symbol, strtab, strtabsize, symIdx);
974    ++symIdx;
975    if (hasEntryInStrTab(**symbol))
976      strtabsize += (*symbol)->nameSize() + 1;
977  }
978}
979
980/// emitDynNamePools - emit dynamic name pools - .dyntab, .dynstr, .hash
981///
982/// the size of these tables should be computed before layout
983/// layout should computes the start offset of these tables
984void GNULDBackend::emitDynNamePools(Module& pModule,
985                                    FileOutputBuffer& pOutput) {
986  ELFFileFormat* file_format = getOutputFormat();
987  if (!file_format->hasDynSymTab() || !file_format->hasDynStrTab() ||
988      !file_format->hasDynamic())
989    return;
990
991  bool sym_exist = false;
992  HashTableType::entry_type* entry = 0;
993
994  LDSection& symtab_sect = file_format->getDynSymTab();
995  LDSection& strtab_sect = file_format->getDynStrTab();
996  LDSection& dyn_sect = file_format->getDynamic();
997
998  MemoryRegion symtab_region =
999      pOutput.request(symtab_sect.offset(), symtab_sect.size());
1000  MemoryRegion strtab_region =
1001      pOutput.request(strtab_sect.offset(), strtab_sect.size());
1002  MemoryRegion dyn_region = pOutput.request(dyn_sect.offset(), dyn_sect.size());
1003  // set up symtab_region
1004  llvm::ELF::Elf32_Sym* symtab32 = NULL;
1005  llvm::ELF::Elf64_Sym* symtab64 = NULL;
1006  if (config().targets().is32Bits())
1007    symtab32 = (llvm::ELF::Elf32_Sym*)symtab_region.begin();
1008  else if (config().targets().is64Bits())
1009    symtab64 = (llvm::ELF::Elf64_Sym*)symtab_region.begin();
1010  else {
1011    fatal(diag::unsupported_bitclass) << config().targets().triple().str()
1012                                      << config().targets().bitclass();
1013  }
1014
1015  // set up strtab_region
1016  char* strtab = reinterpret_cast<char*>(strtab_region.begin());
1017
1018  // emit the first ELF symbol
1019  if (config().targets().is32Bits())
1020    emitSymbol32(symtab32[0], *LDSymbol::Null(), strtab, 0, 0);
1021  else
1022    emitSymbol64(symtab64[0], *LDSymbol::Null(), strtab, 0, 0);
1023
1024  size_t symIdx = 1;
1025  size_t strtabsize = 1;
1026
1027  Module::SymbolTable& symbols = pModule.getSymbolTable();
1028  // emit .gnu.hash
1029  if (GeneralOptions::GNU == config().options().getHashStyle() ||
1030      GeneralOptions::Both == config().options().getHashStyle())
1031    emitGNUHashTab(symbols, pOutput);
1032
1033  // emit .hash
1034  if (GeneralOptions::SystemV == config().options().getHashStyle() ||
1035      GeneralOptions::Both == config().options().getHashStyle())
1036    emitELFHashTab(symbols, pOutput);
1037
1038  // emit .dynsym, and .dynstr (emit LocalDyn and Dynamic category)
1039  Module::const_sym_iterator symbol, symEnd = symbols.dynamicEnd();
1040  for (symbol = symbols.localDynBegin(); symbol != symEnd; ++symbol) {
1041    if (config().targets().is32Bits())
1042      emitSymbol32(symtab32[symIdx], **symbol, strtab, strtabsize, symIdx);
1043    else
1044      emitSymbol64(symtab64[symIdx], **symbol, strtab, strtabsize, symIdx);
1045    // maintain output's symbol and index map
1046    entry = m_pSymIndexMap->insert(*symbol, sym_exist);
1047    entry->setValue(symIdx);
1048    // sum up counters
1049    ++symIdx;
1050    if (hasEntryInStrTab(**symbol))
1051      strtabsize += (*symbol)->nameSize() + 1;
1052  }
1053
1054  // emit DT_NEED
1055  // add DT_NEED strings into .dynstr
1056  ELFDynamic::iterator dt_need = dynamic().needBegin();
1057  Module::const_lib_iterator lib, libEnd = pModule.lib_end();
1058  for (lib = pModule.lib_begin(); lib != libEnd; ++lib) {
1059    if (!(*lib)->attribute()->isAsNeeded() || (*lib)->isNeeded()) {
1060      ::memcpy((strtab + strtabsize),
1061               (*lib)->name().c_str(),
1062               (*lib)->name().size());
1063      (*dt_need)->setValue(llvm::ELF::DT_NEEDED, strtabsize);
1064      strtabsize += (*lib)->name().size() + 1;
1065      ++dt_need;
1066    }
1067  }
1068
1069  if (!config().options().getRpathList().empty()) {
1070    if (!config().options().hasNewDTags())
1071      (*dt_need)->setValue(llvm::ELF::DT_RPATH, strtabsize);
1072    else
1073      (*dt_need)->setValue(llvm::ELF::DT_RUNPATH, strtabsize);
1074    ++dt_need;
1075
1076    GeneralOptions::const_rpath_iterator rpath,
1077        rpathEnd = config().options().rpath_end();
1078    for (rpath = config().options().rpath_begin(); rpath != rpathEnd; ++rpath) {
1079      memcpy((strtab + strtabsize), (*rpath).data(), (*rpath).size());
1080      strtabsize += (*rpath).size();
1081      strtab[strtabsize++] = (rpath + 1 == rpathEnd ? '\0' : ':');
1082    }
1083  }
1084
1085  // initialize value of ELF .dynamic section
1086  if (LinkerConfig::DynObj == config().codeGenType()) {
1087    // set pointer to SONAME entry in dynamic string table.
1088    dynamic().applySoname(strtabsize);
1089  }
1090  dynamic().applyEntries(*file_format);
1091  dynamic().emit(dyn_sect, dyn_region);
1092
1093  // emit soname
1094  if (LinkerConfig::DynObj == config().codeGenType()) {
1095    ::memcpy((strtab + strtabsize),
1096             config().options().soname().c_str(),
1097             config().options().soname().size());
1098    strtabsize += config().options().soname().size() + 1;
1099  }
1100}
1101
1102/// emitELFHashTab - emit .hash
1103void GNULDBackend::emitELFHashTab(const Module::SymbolTable& pSymtab,
1104                                  FileOutputBuffer& pOutput) {
1105  ELFFileFormat* file_format = getOutputFormat();
1106  if (!file_format->hasHashTab())
1107    return;
1108  LDSection& hash_sect = file_format->getHashTab();
1109  MemoryRegion hash_region =
1110      pOutput.request(hash_sect.offset(), hash_sect.size());
1111  // both 32 and 64 bits hash table use 32-bit entry
1112  // set up hash_region
1113  uint32_t* word_array = reinterpret_cast<uint32_t*>(hash_region.begin());
1114  uint32_t& nbucket = word_array[0];
1115  uint32_t& nchain = word_array[1];
1116
1117  size_t dynsymSize = 1 + pSymtab.numOfLocalDyns() + pSymtab.numOfDynamics();
1118  nbucket = getHashBucketCount(dynsymSize, false);
1119  nchain = dynsymSize;
1120
1121  uint32_t* bucket = (word_array + 2);
1122  uint32_t* chain = (bucket + nbucket);
1123
1124  // initialize bucket
1125  memset(reinterpret_cast<void*>(bucket), 0, nbucket);
1126
1127  hash::StringHash<hash::ELF> hash_func;
1128
1129  size_t idx = 1;
1130  Module::const_sym_iterator symbol, symEnd = pSymtab.dynamicEnd();
1131  for (symbol = pSymtab.localDynBegin(); symbol != symEnd; ++symbol) {
1132    llvm::StringRef name((*symbol)->name());
1133    size_t bucket_pos = hash_func(name) % nbucket;
1134    chain[idx] = bucket[bucket_pos];
1135    bucket[bucket_pos] = idx;
1136    ++idx;
1137  }
1138}
1139
1140/// emitGNUHashTab - emit .gnu.hash
1141void GNULDBackend::emitGNUHashTab(Module::SymbolTable& pSymtab,
1142                                  FileOutputBuffer& pOutput) {
1143  ELFFileFormat* file_format = getOutputFormat();
1144  if (!file_format->hasGNUHashTab())
1145    return;
1146
1147  MemoryRegion gnuhash_region =
1148      pOutput.request(file_format->getGNUHashTab().offset(),
1149                      file_format->getGNUHashTab().size());
1150
1151  uint32_t* word_array = reinterpret_cast<uint32_t*>(gnuhash_region.begin());
1152  // fixed-length fields
1153  uint32_t& nbucket = word_array[0];
1154  uint32_t& symidx = word_array[1];
1155  uint32_t& maskwords = word_array[2];
1156  uint32_t& shift2 = word_array[3];
1157  // variable-length fields
1158  uint8_t* bitmask = reinterpret_cast<uint8_t*>(word_array + 4);
1159  uint32_t* bucket = NULL;
1160  uint32_t* chain = NULL;
1161
1162  // count the number of dynsym to hash
1163  size_t unhashed_sym_cnt = pSymtab.numOfLocalDyns();
1164  size_t hashed_sym_cnt = pSymtab.numOfDynamics();
1165  Module::const_sym_iterator symbol, symEnd = pSymtab.dynamicEnd();
1166  for (symbol = pSymtab.dynamicBegin(); symbol != symEnd; ++symbol) {
1167    if (DynsymCompare().needGNUHash(**symbol))
1168      break;
1169    ++unhashed_sym_cnt;
1170    --hashed_sym_cnt;
1171  }
1172
1173  // special case for the empty hash table
1174  if (hashed_sym_cnt == 0) {
1175    nbucket = 1;                    // one empty bucket
1176    symidx = 1 + unhashed_sym_cnt;  // symidx above unhashed symbols
1177    maskwords = 1;                  // bitmask length
1178    shift2 = 0;                     // bloom filter
1179
1180    if (config().targets().is32Bits()) {
1181      uint32_t* maskval = reinterpret_cast<uint32_t*>(bitmask);
1182      *maskval = 0;  // no valid hashes
1183    } else {
1184      // must be 64
1185      uint64_t* maskval = reinterpret_cast<uint64_t*>(bitmask);
1186      *maskval = 0;  // no valid hashes
1187    }
1188    bucket = reinterpret_cast<uint32_t*>(bitmask +
1189                                         config().targets().bitclass() / 8);
1190    *bucket = 0;  // no hash in the only bucket
1191    return;
1192  }
1193
1194  uint32_t maskbitslog2 = getGNUHashMaskbitslog2(hashed_sym_cnt);
1195  uint32_t maskbits = 1u << maskbitslog2;
1196  uint32_t shift1 = config().targets().is32Bits() ? 5 : 6;
1197  uint32_t mask = (1u << shift1) - 1;
1198
1199  nbucket = getHashBucketCount(hashed_sym_cnt, true);
1200  symidx = 1 + unhashed_sym_cnt;
1201  maskwords = 1 << (maskbitslog2 - shift1);
1202  shift2 = maskbitslog2;
1203
1204  // setup bucket and chain
1205  bucket = reinterpret_cast<uint32_t*>(bitmask + maskbits / 8);
1206  chain = (bucket + nbucket);
1207
1208  // build the gnu style hash table
1209  typedef std::multimap<uint32_t, std::pair<LDSymbol*, uint32_t> > SymMapType;
1210  SymMapType symmap;
1211  symEnd = pSymtab.dynamicEnd();
1212  for (symbol = pSymtab.localDynBegin() + symidx - 1; symbol != symEnd;
1213       ++symbol) {
1214    hash::StringHash<hash::DJB> hasher;
1215    uint32_t djbhash = hasher((*symbol)->name());
1216    uint32_t hash = djbhash % nbucket;
1217    symmap.insert(std::make_pair(hash, std::make_pair(*symbol, djbhash)));
1218  }
1219
1220  // compute bucket, chain, and bitmask
1221  std::vector<uint64_t> bitmasks(maskwords);
1222  size_t hashedidx = symidx;
1223  for (size_t idx = 0; idx < nbucket; ++idx) {
1224    size_t count = 0;
1225    std::pair<SymMapType::iterator, SymMapType::iterator> ret;
1226    ret = symmap.equal_range(idx);
1227    for (SymMapType::iterator it = ret.first; it != ret.second;) {
1228      // rearrange the hashed symbol ordering
1229      *(pSymtab.localDynBegin() + hashedidx - 1) = it->second.first;
1230      uint32_t djbhash = it->second.second;
1231      uint32_t val = ((djbhash >> shift1) & ((maskbits >> shift1) - 1));
1232      bitmasks[val] |= 1u << (djbhash & mask);
1233      bitmasks[val] |= 1u << ((djbhash >> shift2) & mask);
1234      val = djbhash & ~1u;
1235      // advance the iterator and check if we're dealing w/ the last elment
1236      if (++it == ret.second) {
1237        // last element terminates the chain
1238        val |= 1;
1239      }
1240      chain[hashedidx - symidx] = val;
1241
1242      ++hashedidx;
1243      ++count;
1244    }
1245
1246    if (count == 0)
1247      bucket[idx] = 0;
1248    else
1249      bucket[idx] = hashedidx - count;
1250  }
1251
1252  // write the bitmasks
1253  if (config().targets().is32Bits()) {
1254    uint32_t* maskval = reinterpret_cast<uint32_t*>(bitmask);
1255    for (size_t i = 0; i < maskwords; ++i)
1256      std::memcpy(maskval + i, &bitmasks[i], 4);
1257  } else {
1258    // must be 64
1259    uint64_t* maskval = reinterpret_cast<uint64_t*>(bitmask);
1260    for (size_t i = 0; i < maskwords; ++i)
1261      std::memcpy(maskval + i, &bitmasks[i], 8);
1262  }
1263}
1264
1265/// sizeInterp - compute the size of the .interp section
1266void GNULDBackend::sizeInterp() {
1267  const char* dyld_name;
1268  if (config().options().hasDyld())
1269    dyld_name = config().options().dyld().c_str();
1270  else
1271    dyld_name = m_pInfo->dyld();
1272
1273  LDSection& interp = getOutputFormat()->getInterp();
1274  interp.setSize(std::strlen(dyld_name) + 1);
1275}
1276
1277/// emitInterp - emit the .interp
1278void GNULDBackend::emitInterp(FileOutputBuffer& pOutput) {
1279  if (getOutputFormat()->hasInterp()) {
1280    const LDSection& interp = getOutputFormat()->getInterp();
1281    MemoryRegion region = pOutput.request(interp.offset(), interp.size());
1282    const char* dyld_name;
1283    if (config().options().hasDyld())
1284      dyld_name = config().options().dyld().c_str();
1285    else
1286      dyld_name = m_pInfo->dyld();
1287
1288    std::memcpy(region.begin(), dyld_name, interp.size());
1289  }
1290}
1291
1292bool GNULDBackend::hasEntryInStrTab(const LDSymbol& pSym) const {
1293  return ResolveInfo::Section != pSym.type();
1294}
1295
1296void GNULDBackend::orderSymbolTable(Module& pModule) {
1297  Module::SymbolTable& symbols = pModule.getSymbolTable();
1298
1299  if (GeneralOptions::GNU == config().options().getHashStyle() ||
1300      GeneralOptions::Both == config().options().getHashStyle())
1301    // Currently we may add output symbols after sizeNamePools(), and a
1302    // non-stable sort is used in SymbolCategory::arrange(), so we just
1303    // sort .dynsym right before emitting .gnu.hash
1304    std::stable_sort(
1305        symbols.dynamicBegin(), symbols.dynamicEnd(), DynsymCompare());
1306}
1307
1308/// getSectionOrder
1309unsigned int GNULDBackend::getSectionOrder(const LDSection& pSectHdr) const {
1310  const ELFFileFormat* file_format = getOutputFormat();
1311
1312  // NULL section should be the "1st" section
1313  if (LDFileFormat::Null == pSectHdr.kind())
1314    return SHO_NULL;
1315
1316  if (&pSectHdr == &file_format->getStrTab())
1317    return SHO_STRTAB;
1318
1319  // if the section is not ALLOC, lay it out until the last possible moment
1320  if (0 == (pSectHdr.flag() & llvm::ELF::SHF_ALLOC))
1321    return SHO_UNDEFINED;
1322
1323  bool is_write = (pSectHdr.flag() & llvm::ELF::SHF_WRITE) != 0;
1324  bool is_exec = (pSectHdr.flag() & llvm::ELF::SHF_EXECINSTR) != 0;
1325  // TODO: need to take care other possible output sections
1326  switch (pSectHdr.kind()) {
1327    case LDFileFormat::TEXT:
1328    case LDFileFormat::DATA:
1329      if (is_exec) {
1330        if (&pSectHdr == &file_format->getInit())
1331          return SHO_INIT;
1332        if (&pSectHdr == &file_format->getFini())
1333          return SHO_FINI;
1334        return SHO_TEXT;
1335      } else if (!is_write) {
1336        return SHO_RO;
1337      } else {
1338        if (config().options().hasRelro()) {
1339          if (&pSectHdr == &file_format->getPreInitArray() ||
1340              &pSectHdr == &file_format->getInitArray() ||
1341              &pSectHdr == &file_format->getFiniArray() ||
1342              &pSectHdr == &file_format->getCtors() ||
1343              &pSectHdr == &file_format->getDtors() ||
1344              &pSectHdr == &file_format->getJCR() ||
1345              &pSectHdr == &file_format->getDataRelRo())
1346            return SHO_RELRO;
1347
1348          if (&pSectHdr == &file_format->getDataRelRoLocal())
1349            return SHO_RELRO_LOCAL;
1350
1351          // Make special sections that end with .rel.ro suffix as RELRO.
1352          llvm::StringRef name(pSectHdr.name());
1353          if (name.endswith(".rel.ro")) {
1354            return SHO_RELRO;
1355          }
1356        }
1357        if ((pSectHdr.flag() & llvm::ELF::SHF_TLS) != 0x0) {
1358          return SHO_TLS_DATA;
1359        }
1360        return SHO_DATA;
1361      }
1362
1363    case LDFileFormat::BSS:
1364      if ((pSectHdr.flag() & llvm::ELF::SHF_TLS) != 0x0)
1365        return SHO_TLS_BSS;
1366      return SHO_BSS;
1367
1368    case LDFileFormat::NamePool: {
1369      if (&pSectHdr == &file_format->getDynamic())
1370        return SHO_RELRO;
1371      return SHO_NAMEPOOL;
1372    }
1373    case LDFileFormat::Relocation:
1374      if (&pSectHdr == &file_format->getRelPlt() ||
1375          &pSectHdr == &file_format->getRelaPlt())
1376        return SHO_REL_PLT;
1377      return SHO_RELOCATION;
1378
1379    // get the order from target for target specific sections
1380    case LDFileFormat::Target:
1381      return getTargetSectionOrder(pSectHdr);
1382
1383    // handle .interp and .note.* sections
1384    case LDFileFormat::Note:
1385      if (file_format->hasInterp() && (&pSectHdr == &file_format->getInterp()))
1386        return SHO_INTERP;
1387      else if (is_write)
1388        return SHO_RW_NOTE;
1389      else
1390        return SHO_RO_NOTE;
1391
1392    case LDFileFormat::EhFrame:
1393      // set writable .eh_frame as relro
1394      if (is_write)
1395        return SHO_RELRO;
1396    case LDFileFormat::EhFrameHdr:
1397    case LDFileFormat::GCCExceptTable:
1398      return SHO_EXCEPTION;
1399
1400    case LDFileFormat::MetaData:
1401    case LDFileFormat::Debug:
1402    case LDFileFormat::DebugString:
1403    default:
1404      return SHO_UNDEFINED;
1405  }
1406}
1407
1408/// getSymbolSize
1409uint64_t GNULDBackend::getSymbolSize(const LDSymbol& pSymbol) const {
1410  // undefined and dynamic symbols should have zero size.
1411  if (pSymbol.isDyn() || pSymbol.desc() == ResolveInfo::Undefined)
1412    return 0x0;
1413  return pSymbol.resolveInfo()->size();
1414}
1415
1416/// getSymbolInfo
1417uint64_t GNULDBackend::getSymbolInfo(const LDSymbol& pSymbol) const {
1418  // set binding
1419  uint8_t bind = 0x0;
1420  if (pSymbol.resolveInfo()->isLocal())
1421    bind = llvm::ELF::STB_LOCAL;
1422  else if (pSymbol.resolveInfo()->isGlobal())
1423    bind = llvm::ELF::STB_GLOBAL;
1424  else if (pSymbol.resolveInfo()->isWeak())
1425    bind = llvm::ELF::STB_WEAK;
1426  else if (pSymbol.resolveInfo()->isAbsolute()) {
1427    // (Luba) Is a absolute but not global (weak or local) symbol meaningful?
1428    bind = llvm::ELF::STB_GLOBAL;
1429  }
1430
1431  if (config().codeGenType() != LinkerConfig::Object &&
1432      (pSymbol.visibility() == llvm::ELF::STV_INTERNAL ||
1433       pSymbol.visibility() == llvm::ELF::STV_HIDDEN))
1434    bind = llvm::ELF::STB_LOCAL;
1435
1436  uint32_t type = pSymbol.resolveInfo()->type();
1437  // if the IndirectFunc symbol (i.e., STT_GNU_IFUNC) is from dynobj, change
1438  // its type to Function
1439  if (type == ResolveInfo::IndirectFunc && pSymbol.isDyn())
1440    type = ResolveInfo::Function;
1441  return (type | (bind << 4));
1442}
1443
1444/// getSymbolValue - this function is called after layout()
1445uint64_t GNULDBackend::getSymbolValue(const LDSymbol& pSymbol) const {
1446  if (pSymbol.isDyn())
1447    return 0x0;
1448
1449  return pSymbol.value();
1450}
1451
1452/// getSymbolShndx - this function is called after layout()
1453uint64_t GNULDBackend::getSymbolShndx(const LDSymbol& pSymbol) const {
1454  if (pSymbol.resolveInfo()->isAbsolute())
1455    return llvm::ELF::SHN_ABS;
1456  if (pSymbol.resolveInfo()->isCommon())
1457    return llvm::ELF::SHN_COMMON;
1458  if (pSymbol.resolveInfo()->isUndef() || pSymbol.isDyn())
1459    return llvm::ELF::SHN_UNDEF;
1460
1461  if (pSymbol.resolveInfo()->isDefine() && !pSymbol.hasFragRef())
1462    return llvm::ELF::SHN_ABS;
1463
1464  assert(pSymbol.hasFragRef() &&
1465         "symbols must have fragment reference to get its index");
1466  return pSymbol.fragRef()->frag()->getParent()->getSection().index();
1467}
1468
1469/// getSymbolIdx - called by emitRelocation to get the ouput symbol table index
1470size_t GNULDBackend::getSymbolIdx(const LDSymbol* pSymbol) const {
1471  HashTableType::iterator entry =
1472      m_pSymIndexMap->find(const_cast<LDSymbol*>(pSymbol));
1473  assert(entry != m_pSymIndexMap->end() &&
1474         "symbol not found in the symbol table");
1475  return entry.getEntry()->value();
1476}
1477
1478/// isTemporary - Whether pSymbol is a local label.
1479bool GNULDBackend::isTemporary(const LDSymbol& pSymbol) const {
1480  if (ResolveInfo::Local != pSymbol.binding())
1481    return false;
1482
1483  if (pSymbol.nameSize() < 2)
1484    return false;
1485
1486  const char* name = pSymbol.name();
1487  if ('.' == name[0] && 'L' == name[1])
1488    return true;
1489
1490  // UnixWare 2.1 cc generate DWARF debugging symbols with `..' prefix.
1491  if (name[0] == '.' && name[1] == '.')
1492    return true;
1493
1494  // Work arround for gcc's bug
1495  // gcc sometimes generate symbols with '_.L_' prefix.
1496  if (pSymbol.nameSize() < 4)
1497    return false;
1498
1499  if (name[0] == '_' && name[1] == '.' && name[2] == 'L' && name[3] == '_')
1500    return true;
1501
1502  return false;
1503}
1504
1505/// allocateCommonSymbols - allocate common symbols in the corresponding
1506/// sections. This is executed at pre-layout stage.
1507bool GNULDBackend::allocateCommonSymbols(Module& pModule) {
1508  SymbolCategory& symbol_list = pModule.getSymbolTable();
1509
1510  if (symbol_list.emptyCommons() && symbol_list.emptyFiles() &&
1511      symbol_list.emptyLocals() && symbol_list.emptyLocalDyns())
1512    return true;
1513
1514  SymbolCategory::iterator com_sym, com_end;
1515
1516  // FIXME: If the order of common symbols is defined, then sort common symbols
1517  // std::sort(com_sym, com_end, some kind of order);
1518
1519  // get corresponding BSS LDSection
1520  ELFFileFormat* file_format = getOutputFormat();
1521  LDSection& bss_sect = file_format->getBSS();
1522  LDSection& tbss_sect = file_format->getTBSS();
1523
1524  // get or create corresponding BSS SectionData
1525  SectionData* bss_sect_data = NULL;
1526  if (bss_sect.hasSectionData())
1527    bss_sect_data = bss_sect.getSectionData();
1528  else
1529    bss_sect_data = IRBuilder::CreateSectionData(bss_sect);
1530
1531  SectionData* tbss_sect_data = NULL;
1532  if (tbss_sect.hasSectionData())
1533    tbss_sect_data = tbss_sect.getSectionData();
1534  else
1535    tbss_sect_data = IRBuilder::CreateSectionData(tbss_sect);
1536
1537  // remember original BSS size
1538  uint64_t bss_offset = bss_sect.size();
1539  uint64_t tbss_offset = tbss_sect.size();
1540
1541  // allocate all local common symbols
1542  com_end = symbol_list.localEnd();
1543
1544  for (com_sym = symbol_list.localBegin(); com_sym != com_end; ++com_sym) {
1545    if (ResolveInfo::Common == (*com_sym)->desc()) {
1546      // We have to reset the description of the symbol here. When doing
1547      // incremental linking, the output relocatable object may have common
1548      // symbols. Therefore, we can not treat common symbols as normal symbols
1549      // when emitting the regular name pools. We must change the symbols'
1550      // description here.
1551      (*com_sym)->resolveInfo()->setDesc(ResolveInfo::Define);
1552      Fragment* frag = new FillFragment(0x0, 1, (*com_sym)->size());
1553
1554      if (ResolveInfo::ThreadLocal == (*com_sym)->type()) {
1555        // allocate TLS common symbol in tbss section
1556        tbss_offset += ObjectBuilder::AppendFragment(
1557            *frag, *tbss_sect_data, (*com_sym)->value());
1558        ObjectBuilder::UpdateSectionAlign(tbss_sect, (*com_sym)->value());
1559        (*com_sym)->setFragmentRef(FragmentRef::Create(*frag, 0));
1560      } else {
1561        bss_offset += ObjectBuilder::AppendFragment(
1562            *frag, *bss_sect_data, (*com_sym)->value());
1563        ObjectBuilder::UpdateSectionAlign(bss_sect, (*com_sym)->value());
1564        (*com_sym)->setFragmentRef(FragmentRef::Create(*frag, 0));
1565      }
1566    }
1567  }
1568
1569  // allocate all global common symbols
1570  com_end = symbol_list.commonEnd();
1571  for (com_sym = symbol_list.commonBegin(); com_sym != com_end; ++com_sym) {
1572    // We have to reset the description of the symbol here. When doing
1573    // incremental linking, the output relocatable object may have common
1574    // symbols. Therefore, we can not treat common symbols as normal symbols
1575    // when emitting the regular name pools. We must change the symbols'
1576    // description here.
1577    (*com_sym)->resolveInfo()->setDesc(ResolveInfo::Define);
1578    Fragment* frag = new FillFragment(0x0, 1, (*com_sym)->size());
1579
1580    if (ResolveInfo::ThreadLocal == (*com_sym)->type()) {
1581      // allocate TLS common symbol in tbss section
1582      tbss_offset += ObjectBuilder::AppendFragment(
1583          *frag, *tbss_sect_data, (*com_sym)->value());
1584      ObjectBuilder::UpdateSectionAlign(tbss_sect, (*com_sym)->value());
1585      (*com_sym)->setFragmentRef(FragmentRef::Create(*frag, 0));
1586    } else {
1587      bss_offset += ObjectBuilder::AppendFragment(
1588          *frag, *bss_sect_data, (*com_sym)->value());
1589      ObjectBuilder::UpdateSectionAlign(bss_sect, (*com_sym)->value());
1590      (*com_sym)->setFragmentRef(FragmentRef::Create(*frag, 0));
1591    }
1592  }
1593
1594  bss_sect.setSize(bss_offset);
1595  tbss_sect.setSize(tbss_offset);
1596  symbol_list.changeCommonsToGlobal();
1597  return true;
1598}
1599
1600/// updateSectionFlags - update pTo's flags when merging pFrom
1601/// update the output section flags based on input section flags.
1602bool GNULDBackend::updateSectionFlags(LDSection& pTo, const LDSection& pFrom) {
1603  // union the flags from input
1604  uint32_t flags = pTo.flag();
1605  flags |= (pFrom.flag() & (llvm::ELF::SHF_WRITE | llvm::ELF::SHF_ALLOC |
1606                            llvm::ELF::SHF_EXECINSTR));
1607
1608  // if there is an input section is not SHF_MERGE, clean this flag
1609  if (0 == (pFrom.flag() & llvm::ELF::SHF_MERGE))
1610    flags &= ~llvm::ELF::SHF_MERGE;
1611
1612  // if there is an input section is not SHF_STRINGS, clean this flag
1613  if (0 == (pFrom.flag() & llvm::ELF::SHF_STRINGS))
1614    flags &= ~llvm::ELF::SHF_STRINGS;
1615
1616  pTo.setFlag(flags);
1617  return true;
1618}
1619
1620/// readRelocation - read ELF32_Rel entry
1621bool GNULDBackend::readRelocation(const llvm::ELF::Elf32_Rel& pRel,
1622                                  Relocation::Type& pType,
1623                                  uint32_t& pSymIdx,
1624                                  uint32_t& pOffset) const {
1625  uint32_t r_info = 0x0;
1626  if (llvm::sys::IsLittleEndianHost) {
1627    pOffset = pRel.r_offset;
1628    r_info = pRel.r_info;
1629  } else {
1630    pOffset = mcld::bswap32(pRel.r_offset);
1631    r_info = mcld::bswap32(pRel.r_info);
1632  }
1633
1634  pType = static_cast<unsigned char>(r_info);
1635  pSymIdx = (r_info >> 8);
1636  return true;
1637}
1638
1639/// readRelocation - read ELF32_Rela entry
1640bool GNULDBackend::readRelocation(const llvm::ELF::Elf32_Rela& pRel,
1641                                  Relocation::Type& pType,
1642                                  uint32_t& pSymIdx,
1643                                  uint32_t& pOffset,
1644                                  int32_t& pAddend) const {
1645  uint32_t r_info = 0x0;
1646  if (llvm::sys::IsLittleEndianHost) {
1647    pOffset = pRel.r_offset;
1648    r_info = pRel.r_info;
1649    pAddend = pRel.r_addend;
1650  } else {
1651    pOffset = mcld::bswap32(pRel.r_offset);
1652    r_info = mcld::bswap32(pRel.r_info);
1653    pAddend = mcld::bswap32(pRel.r_addend);
1654  }
1655
1656  pType = static_cast<unsigned char>(r_info);
1657  pSymIdx = (r_info >> 8);
1658  return true;
1659}
1660
1661/// readRelocation - read ELF64_Rel entry
1662bool GNULDBackend::readRelocation(const llvm::ELF::Elf64_Rel& pRel,
1663                                  Relocation::Type& pType,
1664                                  uint32_t& pSymIdx,
1665                                  uint64_t& pOffset) const {
1666  uint64_t r_info = 0x0;
1667  if (llvm::sys::IsLittleEndianHost) {
1668    pOffset = pRel.r_offset;
1669    r_info = pRel.r_info;
1670  } else {
1671    pOffset = mcld::bswap64(pRel.r_offset);
1672    r_info = mcld::bswap64(pRel.r_info);
1673  }
1674
1675  pType = static_cast<uint32_t>(r_info);
1676  pSymIdx = (r_info >> 32);
1677  return true;
1678}
1679
1680/// readRel - read ELF64_Rela entry
1681bool GNULDBackend::readRelocation(const llvm::ELF::Elf64_Rela& pRel,
1682                                  Relocation::Type& pType,
1683                                  uint32_t& pSymIdx,
1684                                  uint64_t& pOffset,
1685                                  int64_t& pAddend) const {
1686  uint64_t r_info = 0x0;
1687  if (llvm::sys::IsLittleEndianHost) {
1688    pOffset = pRel.r_offset;
1689    r_info = pRel.r_info;
1690    pAddend = pRel.r_addend;
1691  } else {
1692    pOffset = mcld::bswap64(pRel.r_offset);
1693    r_info = mcld::bswap64(pRel.r_info);
1694    pAddend = mcld::bswap64(pRel.r_addend);
1695  }
1696
1697  pType = static_cast<uint32_t>(r_info);
1698  pSymIdx = (r_info >> 32);
1699  return true;
1700}
1701
1702/// emitRelocation - write data to the ELF32_Rel entry
1703void GNULDBackend::emitRelocation(llvm::ELF::Elf32_Rel& pRel,
1704                                  Relocation::Type pType,
1705                                  uint32_t pSymIdx,
1706                                  uint32_t pOffset) const {
1707  pRel.r_offset = pOffset;
1708  pRel.setSymbolAndType(pSymIdx, pType);
1709}
1710
1711/// emitRelocation - write data to the ELF32_Rela entry
1712void GNULDBackend::emitRelocation(llvm::ELF::Elf32_Rela& pRel,
1713                                  Relocation::Type pType,
1714                                  uint32_t pSymIdx,
1715                                  uint32_t pOffset,
1716                                  int32_t pAddend) const {
1717  pRel.r_offset = pOffset;
1718  pRel.r_addend = pAddend;
1719  pRel.setSymbolAndType(pSymIdx, pType);
1720}
1721
1722/// emitRelocation - write data to the ELF64_Rel entry
1723void GNULDBackend::emitRelocation(llvm::ELF::Elf64_Rel& pRel,
1724                                  Relocation::Type pType,
1725                                  uint32_t pSymIdx,
1726                                  uint64_t pOffset) const {
1727  pRel.r_offset = pOffset;
1728  pRel.setSymbolAndType(pSymIdx, pType);
1729}
1730
1731/// emitRelocation - write data to the ELF64_Rela entry
1732void GNULDBackend::emitRelocation(llvm::ELF::Elf64_Rela& pRel,
1733                                  Relocation::Type pType,
1734                                  uint32_t pSymIdx,
1735                                  uint64_t pOffset,
1736                                  int64_t pAddend) const {
1737  pRel.r_offset = pOffset;
1738  pRel.r_addend = pAddend;
1739  pRel.setSymbolAndType(pSymIdx, pType);
1740}
1741
1742/// createProgramHdrs - base on output sections to create the program headers
1743void GNULDBackend::createProgramHdrs(Module& pModule) {
1744  ELFFileFormat* file_format = getOutputFormat();
1745
1746  // make PT_INTERP
1747  if (file_format->hasInterp()) {
1748    // make PT_PHDR
1749    elfSegmentTable().produce(llvm::ELF::PT_PHDR);
1750
1751    ELFSegment* interp_seg = elfSegmentTable().produce(llvm::ELF::PT_INTERP);
1752    interp_seg->append(&file_format->getInterp());
1753  }
1754
1755  uint32_t cur_flag, prev_flag = 0x0;
1756  ELFSegment* load_seg = NULL;
1757  // make possible PT_LOAD segments
1758  LinkerScript& ldscript = pModule.getScript();
1759  LinkerScript::AddressMap::iterator addrEnd = ldscript.addressMap().end();
1760  SectionMap::iterator out, prev, outBegin, outEnd;
1761  outBegin = ldscript.sectionMap().begin();
1762  outEnd = ldscript.sectionMap().end();
1763  for (out = outBegin, prev = outEnd; out != outEnd; prev = out, ++out) {
1764    LDSection* sect = (*out)->getSection();
1765
1766    if (0 == (sect->flag() & llvm::ELF::SHF_ALLOC) &&
1767        LDFileFormat::Null != sect->kind())
1768      break;
1769
1770    // bypass empty sections
1771    if (!(*out)->hasContent() &&
1772        (*out)->getSection()->kind() != LDFileFormat::Null)
1773      continue;
1774
1775    cur_flag = getSegmentFlag(sect->flag());
1776    bool createPT_LOAD = false;
1777    if (LDFileFormat::Null == sect->kind()) {
1778      // 1. create text segment
1779      createPT_LOAD = true;
1780    } else if (!config().options().omagic() &&
1781               (prev_flag & llvm::ELF::PF_W) ^ (cur_flag & llvm::ELF::PF_W)) {
1782      // 2. create data segment if w/o omagic set
1783      createPT_LOAD = true;
1784    } else if (sect->kind() == LDFileFormat::BSS && load_seg->isDataSegment() &&
1785               addrEnd != ldscript.addressMap().find(".bss")) {
1786      // 3. create bss segment if w/ -Tbss and there is a data segment
1787      createPT_LOAD = true;
1788    } else if ((sect != &(file_format->getText())) &&
1789               (sect != &(file_format->getData())) &&
1790               (sect != &(file_format->getBSS())) &&
1791               (addrEnd != ldscript.addressMap().find(sect->name()))) {
1792      // 4. create PT_LOAD for sections in address map except for text, data,
1793      // and bss
1794      createPT_LOAD = true;
1795    } else if (LDFileFormat::Null == (*prev)->getSection()->kind() &&
1796               !config().options().getScriptList().empty()) {
1797      // 5. create PT_LOAD to hold NULL section if there is a default ldscript
1798      createPT_LOAD = true;
1799    }
1800
1801    if (createPT_LOAD) {
1802      // create new PT_LOAD segment
1803      load_seg = elfSegmentTable().produce(llvm::ELF::PT_LOAD, cur_flag);
1804      if (!config().options().nmagic() && !config().options().omagic())
1805        load_seg->setAlign(abiPageSize());
1806    }
1807
1808    assert(load_seg != NULL);
1809    load_seg->append(sect);
1810    if (cur_flag != prev_flag)
1811      load_seg->updateFlag(cur_flag);
1812
1813    prev_flag = cur_flag;
1814  }
1815
1816  // make PT_DYNAMIC
1817  if (file_format->hasDynamic()) {
1818    ELFSegment* dyn_seg = elfSegmentTable().produce(
1819        llvm::ELF::PT_DYNAMIC, llvm::ELF::PF_R | llvm::ELF::PF_W);
1820    dyn_seg->append(&file_format->getDynamic());
1821  }
1822
1823  if (config().options().hasRelro()) {
1824    // make PT_GNU_RELRO
1825    ELFSegment* relro_seg = elfSegmentTable().produce(llvm::ELF::PT_GNU_RELRO);
1826    for (ELFSegmentFactory::iterator seg = elfSegmentTable().begin(),
1827                                     segEnd = elfSegmentTable().end();
1828         seg != segEnd;
1829         ++seg) {
1830      if (llvm::ELF::PT_LOAD != (*seg)->type())
1831        continue;
1832
1833      for (ELFSegment::iterator sect = (*seg)->begin(), sectEnd = (*seg)->end();
1834           sect != sectEnd;
1835           ++sect) {
1836        unsigned int order = getSectionOrder(**sect);
1837        if (SHO_RELRO_LOCAL == order || SHO_RELRO == order ||
1838            SHO_RELRO_LAST == order) {
1839          relro_seg->append(*sect);
1840        }
1841      }
1842    }
1843  }
1844
1845  // make PT_GNU_EH_FRAME
1846  if (file_format->hasEhFrameHdr()) {
1847    ELFSegment* eh_seg = elfSegmentTable().produce(llvm::ELF::PT_GNU_EH_FRAME);
1848    eh_seg->append(&file_format->getEhFrameHdr());
1849  }
1850
1851  // make PT_TLS
1852  if (file_format->hasTData() || file_format->hasTBSS()) {
1853    ELFSegment* tls_seg = elfSegmentTable().produce(llvm::ELF::PT_TLS);
1854    if (file_format->hasTData())
1855      tls_seg->append(&file_format->getTData());
1856    if (file_format->hasTBSS())
1857      tls_seg->append(&file_format->getTBSS());
1858  }
1859
1860  // make PT_GNU_STACK
1861  if (file_format->hasStackNote()) {
1862    uint32_t flag = getSegmentFlag(file_format->getStackNote().flag());
1863    elfSegmentTable().produce(llvm::ELF::PT_GNU_STACK,
1864                              llvm::ELF::PF_R | llvm::ELF::PF_W | flag);
1865  }
1866
1867  // make PT_NOTE
1868  ELFSegment* note_seg = NULL;
1869  prev_flag = 0x0;
1870  Module::iterator sect, sectBegin, sectEnd;
1871  sectBegin = pModule.begin();
1872  sectEnd = pModule.end();
1873  for (sect = sectBegin; sect != sectEnd; ++sect) {
1874    if ((*sect)->type() != llvm::ELF::SHT_NOTE ||
1875        ((*sect)->flag() & llvm::ELF::SHF_ALLOC) == 0)
1876      continue;
1877
1878    cur_flag = getSegmentFlag((*sect)->flag());
1879    // we have different section orders for read-only and writable notes, so
1880    // create 2 segments if needed.
1881    if (note_seg == NULL ||
1882        (cur_flag & llvm::ELF::PF_W) != (prev_flag & llvm::ELF::PF_W))
1883      note_seg = elfSegmentTable().produce(llvm::ELF::PT_NOTE, cur_flag);
1884
1885    note_seg->append(*sect);
1886    prev_flag = cur_flag;
1887  }
1888
1889  // create target dependent segments
1890  doCreateProgramHdrs(pModule);
1891}
1892
1893/// setupProgramHdrs - set up the attributes of segments
1894void GNULDBackend::setupProgramHdrs(const LinkerScript& pScript) {
1895  // update segment info
1896  for (ELFSegmentFactory::iterator seg = elfSegmentTable().begin(),
1897                                   segEnd = elfSegmentTable().end();
1898       seg != segEnd;
1899       ++seg) {
1900    // bypass if there is no section in this segment (e.g., PT_GNU_STACK)
1901    if ((*seg)->size() == 0)
1902      continue;
1903
1904    // bypass the PT_LOAD that only has NULL section now
1905    if ((*seg)->type() == llvm::ELF::PT_LOAD &&
1906        (*seg)->front()->kind() == LDFileFormat::Null && (*seg)->size() == 1)
1907      continue;
1908
1909    (*seg)->setOffset((*seg)->front()->offset());
1910    if ((*seg)->type() == llvm::ELF::PT_LOAD &&
1911        (*seg)->front()->kind() == LDFileFormat::Null) {
1912      const LDSection* second = *((*seg)->begin() + 1);
1913      assert(second != NULL);
1914      (*seg)->setVaddr(second->addr() - second->offset());
1915    } else {
1916      (*seg)->setVaddr((*seg)->front()->addr());
1917    }
1918    (*seg)->setPaddr((*seg)->vaddr());
1919
1920    ELFSegment::reverse_iterator sect, sectREnd = (*seg)->rend();
1921    for (sect = (*seg)->rbegin(); sect != sectREnd; ++sect) {
1922      if ((*sect)->kind() != LDFileFormat::BSS)
1923        break;
1924    }
1925    if (sect != sectREnd) {
1926      (*seg)->setFilesz((*sect)->offset() + (*sect)->size() - (*seg)->offset());
1927    } else {
1928      (*seg)->setFilesz(0x0);
1929    }
1930
1931    (*seg)->setMemsz((*seg)->back()->addr() + (*seg)->back()->size() -
1932                     (*seg)->vaddr());
1933  }  // end of for
1934
1935  // handle the case if text segment only has NULL section
1936  LDSection* null_sect = &getOutputFormat()->getNULLSection();
1937  ELFSegmentFactory::iterator null_seg =
1938      elfSegmentTable().find(llvm::ELF::PT_LOAD, null_sect);
1939
1940  if ((*null_seg)->size() == 1) {
1941    // find 2nd PT_LOAD
1942    ELFSegmentFactory::iterator seg, segEnd = elfSegmentTable().end();
1943    for (seg = null_seg + 1; seg != segEnd; ++seg) {
1944      if ((*seg)->type() == llvm::ELF::PT_LOAD)
1945        break;
1946    }
1947    if (seg != segEnd) {
1948      uint64_t addr = (*seg)->front()->addr() - (*seg)->front()->offset();
1949      uint64_t size = sectionStartOffset();
1950      if (addr + size == (*seg)->front()->addr()) {
1951        // if there is no space between the 2 segments, we can merge them.
1952        (*seg)->setOffset(0x0);
1953        (*seg)->setVaddr(addr);
1954        (*seg)->setPaddr(addr);
1955
1956        ELFSegment::iterator sect, sectEnd = (*seg)->end();
1957        for (sect = (*seg)->begin(); sect != sectEnd; ++sect) {
1958          if ((*sect)->kind() == LDFileFormat::BSS) {
1959            --sect;
1960            break;
1961          }
1962        }
1963        if (sect == sectEnd) {
1964          (*seg)->setFilesz((*seg)->back()->offset() + (*seg)->back()->size() -
1965                            (*seg)->offset());
1966        } else if (*sect != (*seg)->front()) {
1967          --sect;
1968          (*seg)->setFilesz((*sect)->offset() + (*sect)->size() -
1969                            (*seg)->offset());
1970        } else {
1971          (*seg)->setFilesz(0x0);
1972        }
1973
1974        (*seg)->setMemsz((*seg)->back()->addr() + (*seg)->back()->size() -
1975                         (*seg)->vaddr());
1976
1977        (*seg)->insert((*seg)->begin(), null_sect);
1978        elfSegmentTable().erase(null_seg);
1979
1980      } else if (addr + size < (*seg)->vaddr()) {
1981        (*null_seg)->setOffset(0x0);
1982        (*null_seg)->setVaddr(addr);
1983        (*null_seg)->setPaddr(addr);
1984        (*null_seg)->setFilesz(size);
1985        (*null_seg)->setMemsz(size);
1986      } else {
1987        // erase the non valid segment contains NULL.
1988        elfSegmentTable().erase(null_seg);
1989      }
1990    }
1991  }
1992
1993  // set up PT_PHDR
1994  ELFSegmentFactory::iterator phdr =
1995      elfSegmentTable().find(llvm::ELF::PT_PHDR, llvm::ELF::PF_R, 0x0);
1996
1997  if (phdr != elfSegmentTable().end()) {
1998    ELFSegmentFactory::iterator null_seg =
1999        elfSegmentTable().find(llvm::ELF::PT_LOAD, null_sect);
2000    if (null_seg != elfSegmentTable().end()) {
2001      uint64_t offset = 0x0, phdr_size = 0x0;
2002      if (config().targets().is32Bits()) {
2003        offset = sizeof(llvm::ELF::Elf32_Ehdr);
2004        phdr_size = sizeof(llvm::ELF::Elf32_Phdr);
2005      } else {
2006        offset = sizeof(llvm::ELF::Elf64_Ehdr);
2007        phdr_size = sizeof(llvm::ELF::Elf64_Phdr);
2008      }
2009      (*phdr)->setOffset(offset);
2010      (*phdr)->setVaddr((*null_seg)->vaddr() + offset);
2011      (*phdr)->setPaddr((*phdr)->vaddr());
2012      (*phdr)->setFilesz(elfSegmentTable().size() * phdr_size);
2013      (*phdr)->setMemsz(elfSegmentTable().size() * phdr_size);
2014      (*phdr)->setAlign(config().targets().bitclass() / 8);
2015    } else {
2016      elfSegmentTable().erase(phdr);
2017    }
2018  }
2019}
2020
2021/// getSegmentFlag - give a section flag and return the corresponding segment
2022/// flag
2023uint32_t GNULDBackend::getSegmentFlag(const uint32_t pSectionFlag) {
2024  uint32_t flag = 0x0;
2025  if ((pSectionFlag & llvm::ELF::SHF_ALLOC) != 0x0)
2026    flag |= llvm::ELF::PF_R;
2027  if ((pSectionFlag & llvm::ELF::SHF_WRITE) != 0x0)
2028    flag |= llvm::ELF::PF_W;
2029  if ((pSectionFlag & llvm::ELF::SHF_EXECINSTR) != 0x0)
2030    flag |= llvm::ELF::PF_X;
2031  return flag;
2032}
2033
2034/// setupGNUStackInfo - setup the section flag of .note.GNU-stack in output
2035void GNULDBackend::setupGNUStackInfo(Module& pModule) {
2036  uint32_t flag = 0x0;
2037  if (config().options().hasStackSet()) {
2038    // 1. check the command line option (-z execstack or -z noexecstack)
2039    if (config().options().hasExecStack())
2040      flag = llvm::ELF::SHF_EXECINSTR;
2041  } else {
2042    // 2. check the stack info from the input objects
2043    // FIXME: since we alway emit .note.GNU-stack in output now, we may be able
2044    // to check this from the output .note.GNU-stack directly after section
2045    // merging is done
2046    size_t object_count = 0, stack_note_count = 0;
2047    Module::const_obj_iterator obj, objEnd = pModule.obj_end();
2048    for (obj = pModule.obj_begin(); obj != objEnd; ++obj) {
2049      ++object_count;
2050      const LDSection* sect = (*obj)->context()->getSection(".note.GNU-stack");
2051      if (sect != NULL) {
2052        ++stack_note_count;
2053        // 2.1 found a stack note that is set as executable
2054        if (0 != (llvm::ELF::SHF_EXECINSTR & sect->flag())) {
2055          flag = llvm::ELF::SHF_EXECINSTR;
2056          break;
2057        }
2058      }
2059    }
2060
2061    // 2.2 there are no stack note sections in all input objects
2062    if (0 == stack_note_count)
2063      return;
2064
2065    // 2.3 a special case. Use the target default to decide if the stack should
2066    //     be executable
2067    if (llvm::ELF::SHF_EXECINSTR != flag && object_count != stack_note_count)
2068      if (m_pInfo->isDefaultExecStack())
2069        flag = llvm::ELF::SHF_EXECINSTR;
2070  }
2071
2072  if (getOutputFormat()->hasStackNote()) {
2073    getOutputFormat()->getStackNote().setFlag(flag);
2074  }
2075}
2076
2077/// setOutputSectionOffset - helper function to set output sections' offset.
2078void GNULDBackend::setOutputSectionOffset(Module& pModule) {
2079  LinkerScript& script = pModule.getScript();
2080  uint64_t offset = 0x0;
2081  LDSection* cur = NULL;
2082  LDSection* prev = NULL;
2083  SectionMap::iterator out, outBegin, outEnd;
2084  outBegin = script.sectionMap().begin();
2085  outEnd = script.sectionMap().end();
2086  for (out = outBegin; out != outEnd; ++out, prev = cur) {
2087    cur = (*out)->getSection();
2088    if (cur->kind() == LDFileFormat::Null) {
2089      cur->setOffset(0x0);
2090      continue;
2091    }
2092
2093    switch (prev->kind()) {
2094      case LDFileFormat::Null:
2095        offset = sectionStartOffset();
2096        break;
2097      case LDFileFormat::BSS:
2098        offset = prev->offset();
2099        break;
2100      default:
2101        offset = prev->offset() + prev->size();
2102        break;
2103    }
2104    alignAddress(offset, cur->align());
2105    cur->setOffset(offset);
2106  }
2107}
2108
2109/// setOutputSectionAddress - helper function to set output sections' address.
2110void GNULDBackend::setOutputSectionAddress(Module& pModule) {
2111  RpnEvaluator evaluator(pModule, *this);
2112  LinkerScript& script = pModule.getScript();
2113  uint64_t vma = 0x0, offset = 0x0;
2114  LDSection* cur = NULL;
2115  LDSection* prev = NULL;
2116  LinkerScript::AddressMap::iterator addr, addrEnd = script.addressMap().end();
2117  ELFSegmentFactory::iterator seg, segEnd = elfSegmentTable().end();
2118  SectionMap::Output::dot_iterator dot;
2119  SectionMap::iterator out, outBegin, outEnd;
2120  outBegin = script.sectionMap().begin();
2121  outEnd = script.sectionMap().end();
2122  for (out = outBegin; out != outEnd; prev = cur, ++out) {
2123    cur = (*out)->getSection();
2124
2125    if (cur->kind() == LDFileFormat::Null) {
2126      cur->setOffset(0x0);
2127      continue;
2128    }
2129
2130    // process dot assignments between 2 output sections
2131    for (SectionMap::Output::dot_iterator it = (*out)->dot_begin(),
2132                                          ie = (*out)->dot_end();
2133         it != ie;
2134         ++it) {
2135      (*it).assign(evaluator);
2136    }
2137
2138    seg = elfSegmentTable().find(llvm::ELF::PT_LOAD, cur);
2139    if (seg != segEnd && cur == (*seg)->front()) {
2140      if ((*seg)->isBssSegment())
2141        addr = script.addressMap().find(".bss");
2142      else if ((*seg)->isDataSegment())
2143        addr = script.addressMap().find(".data");
2144      else
2145        addr = script.addressMap().find(cur->name());
2146    } else
2147      addr = addrEnd;
2148
2149    if (addr != addrEnd) {
2150      // use address mapping in script options
2151      vma = addr.getEntry()->value();
2152    } else if ((*out)->prolog().hasVMA()) {
2153      // use address from output section description
2154      evaluator.eval((*out)->prolog().vma(), vma);
2155    } else if ((dot = (*out)->find_last_explicit_dot()) != (*out)->dot_end()) {
2156      // assign address based on `.' symbol in ldscript
2157      vma = (*dot).symbol().value();
2158      alignAddress(vma, cur->align());
2159    } else {
2160      if ((*out)->prolog().type() == OutputSectDesc::NOLOAD) {
2161        vma = prev->addr() + prev->size();
2162      } else if ((cur->flag() & llvm::ELF::SHF_ALLOC) != 0) {
2163        if (prev->kind() == LDFileFormat::Null) {
2164          // Let SECTIONS starts at 0 if we have a default ldscript but don't
2165          // have any initial value (VMA or `.').
2166          if (!config().options().getScriptList().empty())
2167            vma = 0x0;
2168          else
2169            vma = getSegmentStartAddr(script) + sectionStartOffset();
2170        } else {
2171          if ((prev->kind() == LDFileFormat::BSS))
2172            vma = prev->addr();
2173          else
2174            vma = prev->addr() + prev->size();
2175        }
2176        alignAddress(vma, cur->align());
2177        if (config().options().getScriptList().empty()) {
2178          if (seg != segEnd && cur == (*seg)->front()) {
2179            // Try to align p_vaddr at page boundary if not in script options.
2180            // To do so will add more padding in file, but can save one page
2181            // at runtime.
2182            alignAddress(vma, (*seg)->align());
2183          }
2184        }
2185      } else {
2186        vma = 0x0;
2187      }
2188    }
2189
2190    if (config().options().hasRelro()) {
2191      // if -z relro is given, we need to adjust sections' offset again, and
2192      // let PT_GNU_RELRO end on a abi page boundary
2193
2194      // check if current is the first non-relro section
2195      SectionMap::iterator relro_last = out - 1;
2196      if (relro_last != outEnd && (*relro_last)->order() <= SHO_RELRO_LAST &&
2197          (*out)->order() > SHO_RELRO_LAST) {
2198        // align the first non-relro section to page boundary
2199        alignAddress(vma, abiPageSize());
2200
2201        // It seems that compiler think .got and .got.plt are continuous (w/o
2202        // any padding between). If .got is the last section in PT_RELRO and
2203        // it's not continuous to its next section (i.e. .got.plt), we need to
2204        // add padding in front of .got instead.
2205        // FIXME: Maybe we can handle this in a more general way.
2206        LDSection& got = getOutputFormat()->getGOT();
2207        if ((getSectionOrder(got) == SHO_RELRO_LAST) &&
2208            (got.addr() + got.size() < vma)) {
2209          uint64_t diff = vma - got.addr() - got.size();
2210          got.setAddr(vma - got.size());
2211          got.setOffset(got.offset() + diff);
2212        }
2213      }
2214    }  // end of if - for relro processing
2215
2216    cur->setAddr(vma);
2217
2218    switch (prev->kind()) {
2219      case LDFileFormat::Null:
2220        offset = sectionStartOffset();
2221        break;
2222      case LDFileFormat::BSS:
2223        offset = prev->offset();
2224        break;
2225      default:
2226        offset = prev->offset() + prev->size();
2227        break;
2228    }
2229    alignAddress(offset, cur->align());
2230    // in p75, http://www.sco.com/developers/devspecs/gabi41.pdf
2231    // p_align: As "Program Loading" describes in this chapter of the
2232    // processor supplement, loadable process segments must have congruent
2233    // values for p_vaddr and p_offset, modulo the page size.
2234    // FIXME: Now make all sh_addr and sh_offset are congruent, modulo the page
2235    // size. Otherwise, old objcopy (e.g., binutils 2.17) may fail with our
2236    // output!
2237    if ((cur->flag() & llvm::ELF::SHF_ALLOC) != 0 &&
2238        (vma & (abiPageSize() - 1)) != (offset & (abiPageSize() - 1))) {
2239      uint64_t padding = abiPageSize() + (vma & (abiPageSize() - 1)) -
2240                         (offset & (abiPageSize() - 1));
2241      offset += padding;
2242    }
2243
2244    cur->setOffset(offset);
2245
2246    // process dot assignments in the output section
2247    bool changed = false;
2248    Fragment* invalid = NULL;
2249    for (SectionMap::Output::iterator in = (*out)->begin(),
2250                                      inEnd = (*out)->end();
2251         in != inEnd;
2252         ++in) {
2253      if (invalid != NULL && !(*in)->dotAssignments().empty()) {
2254        while (invalid != (*in)->dotAssignments().front().first) {
2255          Fragment* prev = invalid->getPrevNode();
2256          invalid->setOffset(prev->getOffset() + prev->size());
2257          invalid = invalid->getNextNode();
2258        }
2259        invalid = NULL;
2260      }
2261
2262      for (SectionMap::Input::dot_iterator it = (*in)->dot_begin(),
2263                                           ie = (*in)->dot_end();
2264           it != ie;
2265           ++it) {
2266        (*it).second.assign(evaluator);
2267        if ((*it).first != NULL) {
2268          uint64_t new_offset = (*it).second.symbol().value() - vma;
2269          if (new_offset != (*it).first->getOffset()) {
2270            (*it).first->setOffset(new_offset);
2271            invalid = (*it).first->getNextNode();
2272            changed = true;
2273          }
2274        }
2275      }  // for each dot assignment
2276    }    // for each input description
2277
2278    if (changed) {
2279      while (invalid != NULL) {
2280        Fragment* prev = invalid->getPrevNode();
2281        invalid->setOffset(prev->getOffset() + prev->size());
2282        invalid = invalid->getNextNode();
2283      }
2284
2285      cur->setSize(cur->getSectionData()->back().getOffset() +
2286                   cur->getSectionData()->back().size());
2287    }
2288  }  // for each output section description
2289}
2290
2291/// placeOutputSections - place output sections based on SectionMap
2292void GNULDBackend::placeOutputSections(Module& pModule) {
2293  typedef std::vector<LDSection*> Orphans;
2294  Orphans orphans;
2295  SectionMap& sectionMap = pModule.getScript().sectionMap();
2296
2297  for (Module::iterator it = pModule.begin(), ie = pModule.end(); it != ie;
2298       ++it) {
2299    bool wanted = false;
2300
2301    switch ((*it)->kind()) {
2302      // take NULL and StackNote directly
2303      case LDFileFormat::Null:
2304      case LDFileFormat::StackNote:
2305        wanted = true;
2306        break;
2307      // ignore if section size is 0
2308      case LDFileFormat::EhFrame:
2309        if (((*it)->size() != 0) ||
2310            ((*it)->hasEhFrame() &&
2311             config().codeGenType() == LinkerConfig::Object))
2312          wanted = true;
2313        break;
2314      case LDFileFormat::Relocation:
2315        if (((*it)->size() != 0) ||
2316            ((*it)->hasRelocData() &&
2317             config().codeGenType() == LinkerConfig::Object))
2318          wanted = true;
2319        break;
2320      case LDFileFormat::TEXT:
2321      case LDFileFormat::DATA:
2322      case LDFileFormat::Target:
2323      case LDFileFormat::MetaData:
2324      case LDFileFormat::BSS:
2325      case LDFileFormat::Debug:
2326      case LDFileFormat::DebugString:
2327      case LDFileFormat::GCCExceptTable:
2328      case LDFileFormat::Note:
2329      case LDFileFormat::NamePool:
2330      case LDFileFormat::EhFrameHdr:
2331        if (((*it)->size() != 0) ||
2332            ((*it)->hasSectionData() &&
2333             config().codeGenType() == LinkerConfig::Object))
2334          wanted = true;
2335        break;
2336      case LDFileFormat::Group:
2337        if (LinkerConfig::Object == config().codeGenType()) {
2338          // TODO: support incremental linking
2339        }
2340        break;
2341      case LDFileFormat::Version:
2342        if ((*it)->size() != 0) {
2343          wanted = true;
2344          warning(diag::warn_unsupported_symbolic_versioning) << (*it)->name();
2345        }
2346        break;
2347      default:
2348        if ((*it)->size() != 0) {
2349          error(diag::err_unsupported_section) << (*it)->name()
2350                                               << (*it)->kind();
2351        }
2352        break;
2353    }  // end of switch
2354
2355    if (wanted) {
2356      SectionMap::iterator out, outBegin, outEnd;
2357      outBegin = sectionMap.begin();
2358      outEnd = sectionMap.end();
2359      for (out = outBegin; out != outEnd; ++out) {
2360        bool matched = false;
2361        if ((*it)->name().compare((*out)->name()) == 0) {
2362          switch ((*out)->prolog().constraint()) {
2363            case OutputSectDesc::NO_CONSTRAINT:
2364              matched = true;
2365              break;
2366            case OutputSectDesc::ONLY_IF_RO:
2367              matched = ((*it)->flag() & llvm::ELF::SHF_WRITE) == 0;
2368              break;
2369            case OutputSectDesc::ONLY_IF_RW:
2370              matched = ((*it)->flag() & llvm::ELF::SHF_WRITE) != 0;
2371              break;
2372          }  // end of switch
2373
2374          if (matched)
2375            break;
2376        }
2377      }  // for each output section description
2378
2379      if (out != outEnd) {
2380        // set up the section
2381        (*out)->setSection(*it);
2382        (*out)->setOrder(getSectionOrder(**it));
2383      } else {
2384        orphans.push_back(*it);
2385      }
2386    }
2387  }  // for each section in Module
2388
2389  // set up sections in SectionMap but do not exist at all.
2390  uint32_t flag = 0x0;
2391  unsigned int order = SHO_UNDEFINED;
2392  OutputSectDesc::Type type = OutputSectDesc::LOAD;
2393  for (SectionMap::reverse_iterator out = sectionMap.rbegin(),
2394                                    outEnd = sectionMap.rend();
2395       out != outEnd;
2396       ++out) {
2397    if ((*out)->hasContent() ||
2398        (*out)->getSection()->kind() == LDFileFormat::Null ||
2399        (*out)->getSection()->kind() == LDFileFormat::StackNote) {
2400      flag = (*out)->getSection()->flag();
2401      order = (*out)->order();
2402      type = (*out)->prolog().type();
2403    } else {
2404      (*out)->getSection()->setFlag(flag);
2405      (*out)->setOrder(order);
2406      (*out)->prolog().setType(type);
2407    }
2408  }  // for each output section description
2409
2410  // place orphan sections
2411  for (Orphans::iterator it = orphans.begin(), ie = orphans.end(); it != ie;
2412       ++it) {
2413    size_t order = getSectionOrder(**it);
2414    SectionMap::iterator out, outBegin, outEnd;
2415    outBegin = sectionMap.begin();
2416    outEnd = sectionMap.end();
2417
2418    if ((*it)->kind() == LDFileFormat::Null)
2419      out = sectionMap.insert(outBegin, *it);
2420    else {
2421      for (out = outBegin; out != outEnd; ++out) {
2422        if ((*out)->order() > order)
2423          break;
2424      }
2425      out = sectionMap.insert(out, *it);
2426    }
2427    (*out)->setOrder(order);
2428  }  // for each orphan section
2429
2430  // sort output section orders if there is no default ldscript
2431  if (config().options().getScriptList().empty()) {
2432    std::stable_sort(
2433        sectionMap.begin(), sectionMap.end(), SectionMap::SHOCompare());
2434  }
2435
2436  // when section ordering is fixed, now we can make sure dot assignments are
2437  // all set appropriately
2438  sectionMap.fixupDotSymbols();
2439}
2440
2441/// layout - layout method
2442void GNULDBackend::layout(Module& pModule) {
2443  // 1. place output sections based on SectionMap from SECTIONS command
2444  placeOutputSections(pModule);
2445
2446  // 2. update output sections in Module
2447  SectionMap& sectionMap = pModule.getScript().sectionMap();
2448  pModule.getSectionTable().clear();
2449  for (SectionMap::iterator out = sectionMap.begin(), outEnd = sectionMap.end();
2450       out != outEnd;
2451       ++out) {
2452    if ((*out)->hasContent() ||
2453        (*out)->getSection()->kind() == LDFileFormat::Null ||
2454        (*out)->getSection()->kind() == LDFileFormat::StackNote ||
2455        config().codeGenType() == LinkerConfig::Object) {
2456      (*out)->getSection()->setIndex(pModule.size());
2457      pModule.getSectionTable().push_back((*out)->getSection());
2458    }
2459  }  // for each output section description
2460
2461  // 3. update the size of .shstrtab
2462  sizeShstrtab(pModule);
2463
2464  // 4. create program headers
2465  if (LinkerConfig::Object != config().codeGenType()) {
2466    createProgramHdrs(pModule);
2467  }
2468
2469  // 5. set output section address/offset
2470  if (LinkerConfig::Object != config().codeGenType())
2471    setOutputSectionAddress(pModule);
2472  else
2473    setOutputSectionOffset(pModule);
2474}
2475
2476void GNULDBackend::createAndSizeEhFrameHdr(Module& pModule) {
2477  if (LinkerConfig::Object != config().codeGenType() &&
2478      config().options().hasEhFrameHdr() && getOutputFormat()->hasEhFrame()) {
2479    // init EhFrameHdr and size the output section
2480    ELFFileFormat* format = getOutputFormat();
2481    m_pEhFrameHdr =
2482        new EhFrameHdr(format->getEhFrameHdr(), format->getEhFrame());
2483    m_pEhFrameHdr->sizeOutput();
2484  }
2485}
2486
2487/// mayHaveUnsafeFunctionPointerAccess - check if the section may have unsafe
2488/// function pointer access
2489bool GNULDBackend::mayHaveUnsafeFunctionPointerAccess(
2490    const LDSection& pSection) const {
2491  llvm::StringRef name(pSection.name());
2492  return !name.startswith(".rodata._ZTV") &&
2493         !name.startswith(".data.rel.ro._ZTV") &&
2494         !name.startswith(".rodata._ZTC") &&
2495         !name.startswith(".data.rel.ro._ZTC") && !name.startswith(".eh_frame");
2496}
2497
2498/// preLayout - Backend can do any needed modification before layout
2499void GNULDBackend::preLayout(Module& pModule, IRBuilder& pBuilder) {
2500  // prelayout target first
2501  doPreLayout(pBuilder);
2502
2503  // change .tbss and .tdata section symbol from Local to LocalDyn category
2504  if (f_pTDATA != NULL)
2505    pModule.getSymbolTable().changeToDynamic(*f_pTDATA);
2506
2507  if (f_pTBSS != NULL)
2508    pModule.getSymbolTable().changeToDynamic(*f_pTBSS);
2509
2510  // To merge input's relocation sections into output's relocation sections.
2511  //
2512  // If we are generating relocatables (-r), move input relocation sections
2513  // to corresponding output relocation sections.
2514  if (LinkerConfig::Object == config().codeGenType()) {
2515    Module::obj_iterator input, inEnd = pModule.obj_end();
2516    for (input = pModule.obj_begin(); input != inEnd; ++input) {
2517      LDContext::sect_iterator rs, rsEnd = (*input)->context()->relocSectEnd();
2518      for (rs = (*input)->context()->relocSectBegin(); rs != rsEnd; ++rs) {
2519        // get the output relocation LDSection with identical name.
2520        LDSection* output_sect = pModule.getSection((*rs)->name());
2521        if (output_sect == NULL) {
2522          output_sect = LDSection::Create(
2523              (*rs)->name(), (*rs)->kind(), (*rs)->type(), (*rs)->flag());
2524
2525          output_sect->setAlign((*rs)->align());
2526          pModule.getSectionTable().push_back(output_sect);
2527        }
2528
2529        // set output relocation section link
2530        const LDSection* input_link = (*rs)->getLink();
2531        assert(input_link != NULL && "Illegal input relocation section.");
2532
2533        // get the linked output section
2534        LDSection* output_link = pModule.getSection(input_link->name());
2535        assert(output_link != NULL);
2536
2537        output_sect->setLink(output_link);
2538
2539        // get output relcoationData, create one if not exist
2540        if (!output_sect->hasRelocData())
2541          IRBuilder::CreateRelocData(*output_sect);
2542
2543        RelocData* out_reloc_data = output_sect->getRelocData();
2544
2545        // move relocations from input's to output's RelcoationData
2546        RelocData::RelocationListType& out_list =
2547            out_reloc_data->getRelocationList();
2548        RelocData::RelocationListType& in_list =
2549            (*rs)->getRelocData()->getRelocationList();
2550        out_list.splice(out_list.end(), in_list);
2551
2552        // size output
2553        if (llvm::ELF::SHT_REL == output_sect->type())
2554          output_sect->setSize(out_reloc_data->size() * getRelEntrySize());
2555        else if (llvm::ELF::SHT_RELA == output_sect->type())
2556          output_sect->setSize(out_reloc_data->size() * getRelaEntrySize());
2557        else {
2558          fatal(diag::unknown_reloc_section_type) << output_sect->type()
2559                                                  << output_sect->name();
2560        }
2561      }  // end of for each relocation section
2562    }    // end of for each input
2563  }      // end of if
2564
2565  // set up the section flag of .note.GNU-stack section
2566  setupGNUStackInfo(pModule);
2567}
2568
2569/// postLayout - Backend can do any needed modification after layout
2570void GNULDBackend::postLayout(Module& pModule, IRBuilder& pBuilder) {
2571  if (LinkerConfig::Object != config().codeGenType()) {
2572    // do relaxation
2573    relax(pModule, pBuilder);
2574    // set up the attributes of program headers
2575    setupProgramHdrs(pModule.getScript());
2576  }
2577
2578  doPostLayout(pModule, pBuilder);
2579}
2580
2581void GNULDBackend::postProcessing(FileOutputBuffer& pOutput) {
2582  if (LinkerConfig::Object != config().codeGenType() &&
2583      config().options().hasEhFrameHdr() && getOutputFormat()->hasEhFrame()) {
2584    // emit eh_frame_hdr
2585    m_pEhFrameHdr->emitOutput<32>(pOutput);
2586  }
2587}
2588
2589/// getHashBucketCount - calculate hash bucket count.
2590unsigned GNULDBackend::getHashBucketCount(unsigned pNumOfSymbols,
2591                                          bool pIsGNUStyle) {
2592  static const unsigned int buckets[] = {
2593      1, 3, 17, 37, 67, 97, 131, 197, 263, 521, 1031, 2053, 4099, 8209, 16411,
2594      32771, 65537, 131101, 262147
2595  };
2596  const unsigned buckets_count = sizeof buckets / sizeof buckets[0];
2597
2598  unsigned int result = 1;
2599  for (unsigned i = 0; i < buckets_count; ++i) {
2600    if (pNumOfSymbols < buckets[i])
2601      break;
2602    result = buckets[i];
2603  }
2604
2605  if (pIsGNUStyle && result < 2)
2606    result = 2;
2607
2608  return result;
2609}
2610
2611/// getGNUHashMaskbitslog2 - calculate the number of mask bits in log2
2612unsigned GNULDBackend::getGNUHashMaskbitslog2(unsigned pNumOfSymbols) const {
2613  uint32_t maskbitslog2 = 1;
2614  for (uint32_t x = pNumOfSymbols >> 1; x != 0; x >>= 1)
2615    ++maskbitslog2;
2616
2617  if (maskbitslog2 < 3)
2618    maskbitslog2 = 5;
2619  else if (((1U << (maskbitslog2 - 2)) & pNumOfSymbols) != 0)
2620    maskbitslog2 += 3;
2621  else
2622    maskbitslog2 += 2;
2623
2624  if (config().targets().bitclass() == 64 && maskbitslog2 == 5)
2625    maskbitslog2 = 6;
2626
2627  return maskbitslog2;
2628}
2629
2630/// isDynamicSymbol
2631bool GNULDBackend::isDynamicSymbol(const LDSymbol& pSymbol) const {
2632  // If a local symbol is in the LDContext's symbol table, it's a real local
2633  // symbol. We should not add it
2634  if (pSymbol.binding() == ResolveInfo::Local)
2635    return false;
2636
2637  // If we are building shared object, and the visibility is external, we
2638  // need to add it.
2639  if (LinkerConfig::DynObj == config().codeGenType() ||
2640      LinkerConfig::Exec == config().codeGenType() ||
2641      LinkerConfig::Binary == config().codeGenType()) {
2642    if (pSymbol.resolveInfo()->visibility() == ResolveInfo::Default ||
2643        pSymbol.resolveInfo()->visibility() == ResolveInfo::Protected)
2644      return true;
2645  }
2646  return false;
2647}
2648
2649/// isDynamicSymbol
2650bool GNULDBackend::isDynamicSymbol(const ResolveInfo& pResolveInfo) const {
2651  // If a local symbol is in the LDContext's symbol table, it's a real local
2652  // symbol. We should not add it
2653  if (pResolveInfo.binding() == ResolveInfo::Local)
2654    return false;
2655
2656  // If we are building shared object, and the visibility is external, we
2657  // need to add it.
2658  if (LinkerConfig::DynObj == config().codeGenType() ||
2659      LinkerConfig::Exec == config().codeGenType() ||
2660      LinkerConfig::Binary == config().codeGenType()) {
2661    if (pResolveInfo.visibility() == ResolveInfo::Default ||
2662        pResolveInfo.visibility() == ResolveInfo::Protected)
2663      return true;
2664  }
2665  return false;
2666}
2667
2668/// elfSegmentTable - return the reference of the elf segment table
2669ELFSegmentFactory& GNULDBackend::elfSegmentTable() {
2670  assert(m_pELFSegmentTable != NULL && "Do not create ELFSegmentTable!");
2671  return *m_pELFSegmentTable;
2672}
2673
2674/// elfSegmentTable - return the reference of the elf segment table
2675const ELFSegmentFactory& GNULDBackend::elfSegmentTable() const {
2676  assert(m_pELFSegmentTable != NULL && "Do not create ELFSegmentTable!");
2677  return *m_pELFSegmentTable;
2678}
2679
2680/// commonPageSize - the common page size of the target machine.
2681uint64_t GNULDBackend::commonPageSize() const {
2682  if (config().options().commPageSize() > 0)
2683    return std::min(config().options().commPageSize(), abiPageSize());
2684  else
2685    return std::min(m_pInfo->commonPageSize(), abiPageSize());
2686}
2687
2688/// abiPageSize - the abi page size of the target machine.
2689uint64_t GNULDBackend::abiPageSize() const {
2690  if (config().options().maxPageSize() > 0)
2691    return config().options().maxPageSize();
2692  else
2693    return m_pInfo->abiPageSize();
2694}
2695
2696/// isSymbolPreemtible - whether the symbol can be preemted by other
2697/// link unit
2698bool GNULDBackend::isSymbolPreemptible(const ResolveInfo& pSym) const {
2699  if (pSym.other() != ResolveInfo::Default)
2700    return false;
2701
2702  // This is because the codeGenType of pie is DynObj. And gold linker check
2703  // the "shared" option instead.
2704  if (config().options().isPIE())
2705    return false;
2706
2707  if (LinkerConfig::DynObj != config().codeGenType())
2708    return false;
2709
2710  if (config().options().Bsymbolic())
2711    return false;
2712
2713  // A local defined symbol should be non-preemptible.
2714  // This issue is found when linking libstdc++ on freebsd. A R_386_GOT32
2715  // relocation refers to a local defined symbol, and we should generate a
2716  // relative dynamic relocation when applying the relocation.
2717  if (pSym.isDefine() && pSym.binding() == ResolveInfo::Local)
2718    return false;
2719
2720  return true;
2721}
2722
2723/// symbolNeedsDynRel - return whether the symbol needs a dynamic relocation
2724bool GNULDBackend::symbolNeedsDynRel(const ResolveInfo& pSym,
2725                                     bool pSymHasPLT,
2726                                     bool isAbsReloc) const {
2727  // an undefined reference in the executables should be statically
2728  // resolved to 0 and no need a dynamic relocation
2729  if (pSym.isUndef() && !pSym.isDyn() &&
2730      (LinkerConfig::Exec == config().codeGenType() ||
2731       LinkerConfig::Binary == config().codeGenType()))
2732    return false;
2733
2734  // An absolute symbol can be resolved directly if it is either local
2735  // or we are linking statically. Otherwise it can still be overridden
2736  // at runtime.
2737  if (pSym.isAbsolute() &&
2738      (pSym.binding() == ResolveInfo::Local || config().isCodeStatic()))
2739    return false;
2740  if (config().isCodeIndep() && isAbsReloc)
2741    return true;
2742  if (pSymHasPLT && ResolveInfo::Function == pSym.type())
2743    return false;
2744  if (!config().isCodeIndep() && pSymHasPLT)
2745    return false;
2746  if (pSym.isDyn() || pSym.isUndef() || isSymbolPreemptible(pSym))
2747    return true;
2748
2749  return false;
2750}
2751
2752/// symbolNeedsPLT - return whether the symbol needs a PLT entry
2753bool GNULDBackend::symbolNeedsPLT(const ResolveInfo& pSym) const {
2754  if (pSym.isUndef() && !pSym.isDyn() &&
2755      LinkerConfig::DynObj != config().codeGenType())
2756    return false;
2757
2758  // An IndirectFunc symbol (i.e., STT_GNU_IFUNC) always needs a plt entry
2759  if (pSym.type() == ResolveInfo::IndirectFunc)
2760    return true;
2761
2762  if (pSym.type() != ResolveInfo::Function)
2763    return false;
2764
2765  if (config().isCodeStatic())
2766    return false;
2767
2768  if (config().options().isPIE())
2769    return false;
2770
2771  return (pSym.isDyn() || pSym.isUndef() || isSymbolPreemptible(pSym));
2772}
2773
2774/// symbolHasFinalValue - return true if the symbol's value can be decided at
2775/// link time
2776bool GNULDBackend::symbolFinalValueIsKnown(const ResolveInfo& pSym) const {
2777  // if the output is pic code or if not executables, symbols' value may change
2778  // at runtime
2779  // FIXME: CodeIndep() || LinkerConfig::Relocatable == CodeGenType
2780  if (config().isCodeIndep() ||
2781      (LinkerConfig::Exec != config().codeGenType() &&
2782       LinkerConfig::Binary != config().codeGenType()))
2783    return false;
2784
2785  // if the symbol is from dynamic object, then its value is unknown
2786  if (pSym.isDyn())
2787    return false;
2788
2789  // if the symbol is not in dynamic object and is not undefined, then its value
2790  // is known
2791  if (!pSym.isUndef())
2792    return true;
2793
2794  // if the symbol is undefined and not in dynamic objects, for example, a weak
2795  // undefined symbol, then whether the symbol's final value can be known
2796  // depends on whrther we're doing static link
2797  return config().isCodeStatic();
2798}
2799
2800/// symbolNeedsCopyReloc - return whether the symbol needs a copy relocation
2801bool GNULDBackend::symbolNeedsCopyReloc(const Relocation& pReloc,
2802                                        const ResolveInfo& pSym) const {
2803  // only the reference from dynamic executable to non-function symbol in
2804  // the dynamic objects may need copy relocation
2805  if (config().isCodeIndep() || !pSym.isDyn() ||
2806      pSym.type() == ResolveInfo::Function || pSym.size() == 0)
2807    return false;
2808
2809  // check if the option -z nocopyreloc is given
2810  if (config().options().hasNoCopyReloc())
2811    return false;
2812
2813  // TODO: Is this check necessary?
2814  // if relocation target place is readonly, a copy relocation is needed
2815  uint32_t flag = pReloc.targetRef().frag()->getParent()->getSection().flag();
2816  if (0 == (flag & llvm::ELF::SHF_WRITE))
2817    return true;
2818
2819  return false;
2820}
2821
2822LDSymbol& GNULDBackend::getTDATASymbol() {
2823  assert(f_pTDATA != NULL);
2824  return *f_pTDATA;
2825}
2826
2827const LDSymbol& GNULDBackend::getTDATASymbol() const {
2828  assert(f_pTDATA != NULL);
2829  return *f_pTDATA;
2830}
2831
2832LDSymbol& GNULDBackend::getTBSSSymbol() {
2833  assert(f_pTBSS != NULL);
2834  return *f_pTBSS;
2835}
2836
2837const LDSymbol& GNULDBackend::getTBSSSymbol() const {
2838  assert(f_pTBSS != NULL);
2839  return *f_pTBSS;
2840}
2841
2842llvm::StringRef GNULDBackend::getEntry(const Module& pModule) const {
2843  if (pModule.getScript().hasEntry())
2844    return pModule.getScript().entry();
2845  else
2846    return getInfo().entry();
2847}
2848
2849void GNULDBackend::checkAndSetHasTextRel(const LDSection& pSection) {
2850  if (m_bHasTextRel)
2851    return;
2852
2853  // if the target section of the dynamic relocation is ALLOCATE but is not
2854  // writable, than we should set DF_TEXTREL
2855  const uint32_t flag = pSection.flag();
2856  if (0 == (flag & llvm::ELF::SHF_WRITE) && (flag & llvm::ELF::SHF_ALLOC))
2857    m_bHasTextRel = true;
2858
2859  return;
2860}
2861
2862/// sortRelocation - sort the dynamic relocations to let dynamic linker
2863/// process relocations more efficiently
2864void GNULDBackend::sortRelocation(LDSection& pSection) {
2865  if (!config().options().hasCombReloc())
2866    return;
2867
2868  assert(pSection.kind() == LDFileFormat::Relocation);
2869
2870  switch (config().codeGenType()) {
2871    case LinkerConfig::DynObj:
2872    case LinkerConfig::Exec:
2873      if (&pSection == &getOutputFormat()->getRelDyn() ||
2874          &pSection == &getOutputFormat()->getRelaDyn()) {
2875        if (pSection.hasRelocData())
2876          pSection.getRelocData()->sort(RelocCompare(*this));
2877      }
2878    default:
2879      return;
2880  }
2881}
2882
2883/// initBRIslandFactory - initialize the branch island factory for relaxation
2884bool GNULDBackend::initBRIslandFactory() {
2885  if (m_pBRIslandFactory == NULL) {
2886    m_pBRIslandFactory =
2887        new BranchIslandFactory(maxFwdBranchOffset(), maxBwdBranchOffset());
2888  }
2889  return true;
2890}
2891
2892/// initStubFactory - initialize the stub factory for relaxation
2893bool GNULDBackend::initStubFactory() {
2894  if (m_pStubFactory == NULL) {
2895    m_pStubFactory = new StubFactory();
2896  }
2897  return true;
2898}
2899
2900bool GNULDBackend::relax(Module& pModule, IRBuilder& pBuilder) {
2901  if (!mayRelax())
2902    return true;
2903
2904  getBRIslandFactory()->group(pModule);
2905
2906  bool finished = true;
2907  do {
2908    if (doRelax(pModule, pBuilder, finished)) {
2909      setOutputSectionAddress(pModule);
2910    }
2911  } while (!finished);
2912
2913  return true;
2914}
2915
2916bool GNULDBackend::DynsymCompare::needGNUHash(const LDSymbol& X) const {
2917  // FIXME: in bfd and gold linker, an undefined symbol might be hashed
2918  // when the ouput is not PIC, if the symbol is referred by a non pc-relative
2919  // reloc, and its value is set to the addr of the plt entry.
2920  return !X.resolveInfo()->isUndef() && !X.isDyn();
2921}
2922
2923bool GNULDBackend::DynsymCompare::operator()(const LDSymbol* X,
2924                                             const LDSymbol* Y) const {
2925  return !needGNUHash(*X) && needGNUHash(*Y);
2926}
2927
2928bool GNULDBackend::RelocCompare::operator()(const Relocation* X,
2929                                            const Relocation* Y) const {
2930  // 1. compare if relocation is relative
2931  if (X->symInfo() == NULL) {
2932    if (Y->symInfo() != NULL)
2933      return true;
2934  } else if (Y->symInfo() == NULL) {
2935    return false;
2936  } else {
2937    // 2. compare the symbol index
2938    size_t symIdxX = m_Backend.getSymbolIdx(X->symInfo()->outSymbol());
2939    size_t symIdxY = m_Backend.getSymbolIdx(Y->symInfo()->outSymbol());
2940    if (symIdxX < symIdxY)
2941      return true;
2942    if (symIdxX > symIdxY)
2943      return false;
2944  }
2945
2946  // 3. compare the relocation address
2947  if (X->place() < Y->place())
2948    return true;
2949  if (X->place() > Y->place())
2950    return false;
2951
2952  // 4. compare the relocation type
2953  if (X->type() < Y->type())
2954    return true;
2955  if (X->type() > Y->type())
2956    return false;
2957
2958  // 5. compare the addend
2959  if (X->addend() < Y->addend())
2960    return true;
2961  if (X->addend() > Y->addend())
2962    return false;
2963
2964  return false;
2965}
2966
2967}  // namespace mcld
2968