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