1//===- EhFrame.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/LD/EhFrame.h"
10
11#include "mcld/Fragment/Relocation.h"
12#include "mcld/LD/LDContext.h"
13#include "mcld/LD/LDSection.h"
14#include "mcld/LD/LDSymbol.h"
15#include "mcld/LD/RelocData.h"
16#include "mcld/LD/ResolveInfo.h"
17#include "mcld/LD/SectionData.h"
18#include "mcld/MC/Input.h"
19#include "mcld/Object/ObjectBuilder.h"
20#include "mcld/Support/GCFactory.h"
21
22#include <llvm/Support/ManagedStatic.h>
23
24namespace mcld {
25
26typedef GCFactory<EhFrame, MCLD_SECTIONS_PER_INPUT> EhFrameFactory;
27
28static llvm::ManagedStatic<EhFrameFactory> g_EhFrameFactory;
29
30//===----------------------------------------------------------------------===//
31// EhFrame::Record
32//===----------------------------------------------------------------------===//
33EhFrame::Record::Record(llvm::StringRef pRegion) : RegionFragment(pRegion) {
34}
35
36EhFrame::Record::~Record() {
37  // llvm::iplist will manage and delete the fragments
38}
39
40//===----------------------------------------------------------------------===//
41// EhFrame::CIE
42//===----------------------------------------------------------------------===//
43EhFrame::CIE::CIE(llvm::StringRef pRegion)
44    : EhFrame::Record(pRegion),
45      m_FDEEncode(0u),
46      m_Mergeable(false),
47      m_pReloc(0),
48      m_PersonalityOffset(0) {
49}
50
51EhFrame::CIE::~CIE() {
52}
53
54//===----------------------------------------------------------------------===//
55// EhFrame::FDE
56//===----------------------------------------------------------------------===//
57EhFrame::FDE::FDE(llvm::StringRef pRegion, EhFrame::CIE& pCIE)
58    : EhFrame::Record(pRegion), m_pCIE(&pCIE) {
59}
60
61EhFrame::FDE::~FDE() {
62}
63
64void EhFrame::FDE::setCIE(EhFrame::CIE& pCIE) {
65  m_pCIE = &pCIE;
66  m_pCIE->add(*this);
67}
68
69//===----------------------------------------------------------------------===//
70// EhFrame::GeneratedCIE
71//===----------------------------------------------------------------------===//
72EhFrame::GeneratedCIE::GeneratedCIE(llvm::StringRef pRegion)
73    : EhFrame::CIE(pRegion) {
74}
75
76EhFrame::GeneratedCIE::~GeneratedCIE() {
77}
78
79//===----------------------------------------------------------------------===//
80// EhFrame::GeneratedFDE
81//===----------------------------------------------------------------------===//
82EhFrame::GeneratedFDE::GeneratedFDE(llvm::StringRef pRegion, CIE& pCIE)
83    : EhFrame::FDE(pRegion, pCIE) {
84}
85
86EhFrame::GeneratedFDE::~GeneratedFDE() {
87}
88
89//===----------------------------------------------------------------------===//
90// EhFrame
91//===----------------------------------------------------------------------===//
92EhFrame::EhFrame() : m_pSection(NULL), m_pSectionData(NULL) {
93}
94
95EhFrame::EhFrame(LDSection& pSection)
96    : m_pSection(&pSection), m_pSectionData(NULL) {
97  m_pSectionData = SectionData::Create(pSection);
98}
99
100EhFrame::~EhFrame() {
101}
102
103EhFrame* EhFrame::Create(LDSection& pSection) {
104  EhFrame* result = g_EhFrameFactory->allocate();
105  new (result) EhFrame(pSection);
106  return result;
107}
108
109void EhFrame::Destroy(EhFrame*& pSection) {
110  pSection->~EhFrame();
111  g_EhFrameFactory->deallocate(pSection);
112  pSection = NULL;
113}
114
115void EhFrame::Clear() {
116  g_EhFrameFactory->clear();
117}
118
119const LDSection& EhFrame::getSection() const {
120  assert(m_pSection != NULL);
121  return *m_pSection;
122}
123
124LDSection& EhFrame::getSection() {
125  assert(m_pSection != NULL);
126  return *m_pSection;
127}
128
129void EhFrame::addFragment(Fragment& pFrag) {
130  uint32_t offset = 0;
131  if (!m_pSectionData->empty())
132    offset = m_pSectionData->back().getOffset() + m_pSectionData->back().size();
133
134  m_pSectionData->getFragmentList().push_back(&pFrag);
135  pFrag.setParent(m_pSectionData);
136  pFrag.setOffset(offset);
137}
138
139void EhFrame::addCIE(EhFrame::CIE& pCIE, bool pAlsoAddFragment) {
140  m_CIEs.push_back(&pCIE);
141  if (pAlsoAddFragment)
142    addFragment(pCIE);
143}
144
145void EhFrame::addFDE(EhFrame::FDE& pFDE, bool pAlsoAddFragment) {
146  pFDE.getCIE().add(pFDE);
147  if (pAlsoAddFragment)
148    addFragment(pFDE);
149}
150
151size_t EhFrame::numOfFDEs() const {
152  // FDE number only used by .eh_frame_hdr computation, and the number of CIE
153  // is usually not too many. It is worthy to compromise space by time
154  size_t size = 0u;
155  for (const_cie_iterator i = cie_begin(), e = cie_end(); i != e; ++i)
156    size += (*i)->numOfFDEs();
157  return size;
158}
159
160EhFrame& EhFrame::merge(const Input& pInput, EhFrame& pFrame) {
161  assert(this != &pFrame);
162  if (pFrame.emptyCIEs()) {
163    // May be a partial linking, or the eh_frame has no data.
164    // Just append the fragments.
165    moveInputFragments(pFrame);
166    return *this;
167  }
168
169  const LDContext& ctx = *pInput.context();
170  const LDSection* rel_sec = 0;
171  for (LDContext::const_sect_iterator ri = ctx.relocSectBegin(),
172                                      re = ctx.relocSectEnd();
173       ri != re;
174       ++ri) {
175    if ((*ri)->getLink() == &pFrame.getSection()) {
176      rel_sec = *ri;
177      break;
178    }
179  }
180  pFrame.setupAttributes(rel_sec);
181
182  // Most CIE will be merged, so we don't reserve space first.
183  for (cie_iterator i = pFrame.cie_begin(), e = pFrame.cie_end(); i != e; ++i) {
184    CIE& input_cie = **i;
185    // CIE number is usually very few, so we just use vector sequential search.
186    if (!input_cie.getMergeable()) {
187      moveInputFragments(pFrame, input_cie);
188      addCIE(input_cie, /*AlsoAddFragment=*/false);
189      continue;
190    }
191
192    cie_iterator out_i = cie_begin();
193    for (cie_iterator out_e = cie_end(); out_i != out_e; ++out_i) {
194      CIE& output_cie = **out_i;
195      if (output_cie == input_cie) {
196        // This input CIE can be merged
197        moveInputFragments(pFrame, input_cie, &output_cie);
198        removeAndUpdateCIEForFDE(pFrame, input_cie, output_cie, rel_sec);
199        break;
200      }
201    }
202    if (out_i == cie_end()) {
203      moveInputFragments(pFrame, input_cie);
204      addCIE(input_cie, /*AlsoAddFragment=*/false);
205    }
206  }
207  return *this;
208}
209
210void EhFrame::setupAttributes(const LDSection* rel_sec) {
211  for (cie_iterator i = cie_begin(), e = cie_end(); i != e; ++i) {
212    CIE* cie = *i;
213    removeDiscardedFDE(*cie, rel_sec);
214
215    if (cie->getPersonalityName().size() == 0) {
216      // There's no personality data encoding inside augmentation string.
217      cie->setMergeable();
218    } else {
219      if (!rel_sec) {
220        // No relocation to eh_frame section
221        assert(cie->getPersonalityName() != "" &&
222               "PR name should be a symbol address or offset");
223        continue;
224      }
225      const RelocData* reloc_data = rel_sec->getRelocData();
226      for (RelocData::const_iterator ri = reloc_data->begin(),
227                                     re = reloc_data->end();
228           ri != re;
229           ++ri) {
230        const Relocation& rel = *ri;
231        if (rel.targetRef().getOutputOffset() ==
232            cie->getOffset() + cie->getPersonalityOffset()) {
233          cie->setMergeable();
234          cie->setPersonalityName(rel.symInfo()->outSymbol()->name());
235          cie->setRelocation(rel);
236          break;
237        }
238      }
239
240      assert(cie->getPersonalityName() != "" &&
241             "PR name should be a symbol address or offset");
242    }
243  }
244}
245
246void EhFrame::removeDiscardedFDE(CIE& pCIE, const LDSection* pRelocSect) {
247  if (!pRelocSect)
248    return;
249
250  typedef std::vector<FDE*> FDERemoveList;
251  FDERemoveList to_be_removed_fdes;
252  const RelocData* reloc_data = pRelocSect->getRelocData();
253  for (fde_iterator i = pCIE.begin(), e = pCIE.end(); i != e; ++i) {
254    FDE& fde = **i;
255    for (RelocData::const_iterator ri = reloc_data->begin(),
256                                   re = reloc_data->end();
257         ri != re;
258         ++ri) {
259      const Relocation& rel = *ri;
260      if (rel.targetRef().getOutputOffset() ==
261          fde.getOffset() + getDataStartOffset<32>()) {
262        bool has_section = rel.symInfo()->outSymbol()->hasFragRef();
263        if (!has_section)
264          // The section was discarded, just ignore this FDE.
265          // This may happen when redundant group section was read.
266          to_be_removed_fdes.push_back(&fde);
267        break;
268      }
269    }
270  }
271
272  for (FDERemoveList::iterator i = to_be_removed_fdes.begin(),
273                               e = to_be_removed_fdes.end();
274       i != e;
275       ++i) {
276    FDE& fde = **i;
277    fde.getCIE().remove(fde);
278
279    // FIXME: This traverses relocations from the beginning on each FDE, which
280    // may cause performance degration. Actually relocations will be sequential
281    // order, so we can bookkeep the previously found relocation for next use.
282    // Note: We must ensure FDE order is ordered.
283    for (RelocData::const_iterator ri = reloc_data->begin(),
284                                   re = reloc_data->end();
285         ri != re;) {
286      Relocation& rel = const_cast<Relocation&>(*ri++);
287      if (rel.targetRef().getOutputOffset() >= fde.getOffset() &&
288          rel.targetRef().getOutputOffset() < fde.getOffset() + fde.size()) {
289        const_cast<RelocData*>(reloc_data)->remove(rel);
290      }
291    }
292  }
293}
294
295void EhFrame::removeAndUpdateCIEForFDE(EhFrame& pInFrame,
296                                       CIE& pInCIE,
297                                       CIE& pOutCIE,
298                                       const LDSection* rel_sect) {
299  // Make this relocation to be ignored.
300  Relocation* rel = const_cast<Relocation*>(pInCIE.getRelocation());
301  if (rel && rel_sect)
302    const_cast<RelocData*>(rel_sect->getRelocData())->remove(*rel);
303
304  // Update the CIE-pointed FDEs
305  for (fde_iterator i = pInCIE.begin(), e = pInCIE.end(); i != e; ++i)
306    (*i)->setCIE(pOutCIE);
307
308  // We cannot know whether there are references to this fragment, so just
309  // keep it in input fragment list instead of memory deallocation
310  pInCIE.clearFDEs();
311}
312
313void EhFrame::moveInputFragments(EhFrame& pInFrame) {
314  SectionData& in_sd = *pInFrame.getSectionData();
315  SectionData::FragmentListType& in_frag_list = in_sd.getFragmentList();
316  SectionData& out_sd = *getSectionData();
317  SectionData::FragmentListType& out_frag_list = out_sd.getFragmentList();
318
319  while (!in_frag_list.empty()) {
320    Fragment* frag = in_frag_list.remove(in_frag_list.begin());
321    out_frag_list.push_back(frag);
322    frag->setParent(&out_sd);
323  }
324}
325
326void EhFrame::moveInputFragments(EhFrame& pInFrame, CIE& pInCIE, CIE* pOutCIE) {
327  SectionData& in_sd = *pInFrame.getSectionData();
328  SectionData::FragmentListType& in_frag_list = in_sd.getFragmentList();
329  SectionData& out_sd = *getSectionData();
330  SectionData::FragmentListType& out_frag_list = out_sd.getFragmentList();
331
332  if (!pOutCIE) {
333    // Newly inserted
334    Fragment* frag = in_frag_list.remove(SectionData::iterator(pInCIE));
335    out_frag_list.push_back(frag);
336    frag->setParent(&out_sd);
337    for (fde_iterator i = pInCIE.begin(), e = pInCIE.end(); i != e; ++i) {
338      frag = in_frag_list.remove(SectionData::iterator(**i));
339      out_frag_list.push_back(frag);
340      frag->setParent(&out_sd);
341    }
342    return;
343  }
344
345  SectionData::iterator cur_iter(*pOutCIE);
346  assert(cur_iter != out_frag_list.end());
347  for (fde_iterator i = pInCIE.begin(), e = pInCIE.end(); i != e; ++i) {
348    Fragment* frag = in_frag_list.remove(SectionData::iterator(**i));
349    cur_iter = out_frag_list.insertAfter(cur_iter, frag);
350    frag->setParent(&out_sd);
351  }
352}
353
354size_t EhFrame::computeOffsetSize() {
355  size_t offset = 0u;
356  SectionData::FragmentListType& frag_list =
357      getSectionData()->getFragmentList();
358  for (SectionData::iterator i = frag_list.begin(), e = frag_list.end(); i != e;
359       ++i) {
360    Fragment& frag = *i;
361    frag.setOffset(offset);
362    offset += frag.size();
363  }
364  getSection().setSize(offset);
365  return offset;
366}
367
368bool operator==(const EhFrame::CIE& p1, const EhFrame::CIE& p2) {
369  return p1.getPersonalityName() == p2.getPersonalityName() &&
370         p1.getAugmentationData() == p2.getAugmentationData();
371}
372
373}  // namespace mcld
374