1//===- Layout.h -----------------------------------------------------------===//
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#ifndef MCLD_LD_LAYOUT_H
10#define MCLD_LD_LAYOUT_H
11#ifdef ENABLE_UNITTEST
12#include <gtest.h>
13#endif
14
15#include <map>
16
17#include <llvm/ADT/ilist.h>
18#include <llvm/ADT/ilist_node.h>
19#include <llvm/ADT/DenseMap.h>
20
21#include <mcld/LD/FragmentRef.h>
22#include <mcld/LD/LDSection.h>
23#include <mcld/LD/SectionData.h>
24#include <mcld/MC/MCLDInfo.h>
25#include <mcld/Support/GCFactory.h>
26
27namespace mcld
28{
29class MCLinker;
30class Output;
31class TargetLDBackend;
32
33/** \class Layout
34 *  \brief Layout maintains the mapping between sections and fragments.
35 *
36 *  MCLinker is a fragment-based linker. But readers and target backends
37 *  still need section information. Layout is used to maintain the mapping
38 *  between sections and fragments. Layout helps readers and target backends
39 *  get the input or output section information from a fragment.
40 */
41class Layout
42{
43public:
44  typedef std::vector<LDSection*> SectionOrder;
45  typedef SectionOrder::iterator sect_iterator;
46  typedef SectionOrder::const_iterator const_sect_iterator;
47
48public:
49  /// constructor
50  Layout();
51
52  /// destructor
53  ~Layout();
54
55  /// getInputLDSection - give a Fragment, return the corresponding input
56  /// LDSection*
57  ///
58  /// @return return NULL if the fragment is not found in input
59  LDSection* getInputLDSection(const Fragment& pFrag);
60
61  /// getInputLDSection - give a Fragment, return the corresponding input
62  /// LDSection*
63  ///
64  /// @return return NULL if the fragment is not found in input
65  const LDSection* getInputLDSection(const Fragment& pFrag) const;
66
67  /// getFragmentRef - give a LDSection in input file and an offset, return
68  /// the fragment reference.
69  ///
70  /// @param pInputSection - the given input section
71  /// @param pOffset - the offset, cannot be larger than this input section.
72  /// @return if found, return the fragment. Otherwise, return NULL.
73  FragmentRef*
74  getFragmentRef(const LDSection& pInputSection, uint64_t pOffset);
75
76  /// getFragmentRef - give a fragment and a big offset, return the fragment
77  /// reference in the section data.
78  ///
79  /// @param pFrag - the given fragment
80  /// @param pBigOffset - the offset, can be larger than the fragment, but can
81  ///                     not larger than this input section.
82  /// @return if found, return the fragment. Otherwise, return NULL.
83  FragmentRef* getFragmentRef(const Fragment& pFrag, uint64_t pBigOffset);
84
85  /// getOutputOffset - Get the offset of the given fragment inside the
86  /// the output's SectionData.
87  uint64_t getOutputOffset(const Fragment& pFrag);
88
89  /// getOutputOffset - Get the offset of the given fragment inside the
90  /// the output's SectionData.
91  uint64_t getOutputOffset(const Fragment& pFrag) const;
92
93  /// getOutputOffset - Get the offset of the given fragment inside
94  /// the output's SectionData.
95  ///
96  /// @return return -1 if the fragment is not found in output's SectionData.
97
98  uint64_t getOutputOffset(const FragmentRef& pFragRef);
99  /// getOutputOffset - Get the offset of the given fragment inside
100  /// the output's SectionData.
101  ///
102  /// @return return -1 if the fragment is not found in output's SectionData.
103  uint64_t getOutputOffset(const FragmentRef& pFragRef) const;
104
105  /// getOutputLDSection - give a Fragment, return the corresponding output
106  /// LDSection*
107  ///
108  /// @return return NULL if the fragment is not found in the output
109  LDSection* getOutputLDSection(const Fragment& pFrag);
110
111  /// getOutputLDSection - give a Fragment, return the corresponding output
112  /// LDSection*
113  ///
114  /// @return return NULL if the fragment is not found in the output
115  const LDSection* getOutputLDSection(const Fragment& pFrag) const;
116
117  // -----  modifiers  ----- //
118  bool layout(Output& pOutput,
119              const TargetLDBackend& pBackend, const MCLDInfo& pInfo);
120
121  /// addInputRange
122  void addInputRange(const SectionData& pSD, const LDSection& pInputHdr);
123
124  /// appendFragment - append the given Fragment to the given SectionData,
125  /// and insert a AlignFragment to preserve the required align constraint if
126  /// needed
127  /// @return return the inserted size, i.e., the size of pFrag and alignment
128  /// size if any
129  uint64_t appendFragment(Fragment& pFrag, SectionData& pSD,
130                          uint32_t pAlignConstraint = 1);
131private:
132  /** \class Range
133   *  \brief Range is a <input's LDSection, previous rear fragment> pair
134   */
135  struct Range : public llvm::ilist_node<Range>
136  {
137  public:
138    Range();
139    Range(const LDSection& pHeader);
140    ~Range();
141
142  public:
143    LDSection* header;
144    Fragment* prevRear;
145  };
146
147  typedef llvm::iplist<Range> RangeList;
148
149  typedef std::map<const SectionData*, RangeList*> SDRangeMap;
150
151  typedef GCFactory<FragmentRef, 0> FragRefFactory;
152
153private:
154  inline bool isFirstRange(const Range& pRange) const
155  { return (NULL == pRange.prevRear); }
156
157  inline bool isLastRange(const Range& pRange) const
158  { return (NULL == pRange.getNextNode()); }
159
160  inline bool isEmptyRange(const Range& pRange) const
161  {
162    if (isFirstRange(pRange)) {
163      if (!pRange.header->hasSectionData() ||
164          pRange.header->getSectionData()->getFragmentList().empty())
165        return true;
166      else
167        return false;
168    }
169    return (NULL == pRange.prevRear->getNextNode());
170  }
171
172  // get the front fragment in the range.
173  inline Fragment* getFront(Range& pRange) const
174  {
175    if (!pRange.header->hasSectionData())
176      return NULL;
177    if (pRange.header->getSectionData()->getFragmentList().empty())
178      return NULL;
179
180    if (isFirstRange(pRange))
181      return &pRange.header->getSectionData()->getFragmentList().front();
182
183    if (isEmptyRange(pRange))
184      return NULL;
185
186    return pRange.prevRear->getNextNode();
187  }
188
189  inline const Fragment* getFront(const Range& pRange) const
190  {
191    if (!pRange.header->hasSectionData())
192      return NULL;
193    if (pRange.header->getSectionData()->getFragmentList().empty())
194      return NULL;
195
196    if (isFirstRange(pRange))
197      return &pRange.header->getSectionData()->getFragmentList().front();
198
199    if (isEmptyRange(pRange))
200      return NULL;
201
202    return pRange.prevRear->getNextNode();
203  }
204
205  // get the rear fragment in the range.
206  inline Fragment* getRear(Range& pRange) const
207  {
208    if (!pRange.header->hasSectionData())
209      return NULL;
210    if (pRange.header->getSectionData()->getFragmentList().empty())
211      return NULL;
212
213    if (isLastRange(pRange)) {
214      if (isEmptyRange(pRange))
215        return NULL;
216      return &pRange.header->getSectionData()->getFragmentList().back();
217    }
218    return pRange.getNextNode()->prevRear;
219  }
220
221  inline const Fragment* getRear(const Range& pRange) const
222  {
223    if (!pRange.header->hasSectionData())
224      return NULL;
225    if (pRange.header->getSectionData()->getFragmentList().empty())
226      return NULL;
227
228    if (isLastRange(pRange)) {
229      if (isEmptyRange(pRange))
230        return NULL;
231      return &pRange.header->getSectionData()->getFragmentList().back();
232    }
233    return pRange.getNextNode()->prevRear;
234  }
235
236  FragmentRef* getFragmentRef(Range &pRange, uint64_t pOffset);
237
238  FragmentRef*
239  getFragmentRef(Fragment& pFront, Fragment& pRear, uint64_t pOffset);
240
241  bool hasLayoutOrder(const Fragment& pFragment) const
242  { return (pFragment.getLayoutOrder() != ~(0U)); }
243
244  bool hasLayoutOffset(const Fragment& pFragment) const
245  { return (pFragment.getOffset() != ~UINT64_C(0)); }
246
247  bool isValidOffset(const Fragment& pFrag, uint64_t pTargetOffset) const;
248
249  void setFragmentLayoutOrder(Fragment* pFragment);
250
251  void setFragmentLayoutOffset(Fragment* pFragment);
252
253  /// sortSectionOrder - perform sorting on m_SectionOrder to get final layout
254  /// ordering
255  void sortSectionOrder(const Output& pOutput,
256                        const TargetLDBackend& pBackend,
257                        const MCLDInfo& pInfo);
258
259private:
260  /// a vector to describe the order of sections
261  SectionOrder m_SectionOrder;
262
263  /// the map from SectionData* to its own RangeList.
264  SDRangeMap m_SDRangeMap;
265
266  FragRefFactory m_FragRefFactory;
267};
268
269} // namespace of mcld
270
271#endif
272
273