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 27 namespace mcld 28 { 29 class MCLinker; 30 class Output; 31 class 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 */ 41 class Layout 42 { 43 public: 44 typedef std::vector<LDSection*> SectionOrder; 45 typedef SectionOrder::iterator sect_iterator; 46 typedef SectionOrder::const_iterator const_sect_iterator; 47 48 public: 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); 131 private: 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 153 private: isFirstRange(const Range & pRange)154 inline bool isFirstRange(const Range& pRange) const 155 { return (NULL == pRange.prevRear); } 156 isLastRange(const Range & pRange)157 inline bool isLastRange(const Range& pRange) const 158 { return (NULL == pRange.getNextNode()); } 159 isEmptyRange(const Range & pRange)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. getFront(Range & pRange)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 getFront(const Range & pRange)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. getRear(Range & pRange)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 getRear(const Range & pRange)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 hasLayoutOrder(const Fragment & pFragment)241 bool hasLayoutOrder(const Fragment& pFragment) const 242 { return (pFragment.getLayoutOrder() != ~(0U)); } 243 hasLayoutOffset(const Fragment & pFragment)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 259 private: 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