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