SectionMap.cpp revision 37b74a387bb3993387029859c2d9d051c41c724e 
1//===- SectionMap.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/Object/SectionMap.h"
10
11#include "mcld/Fragment/NullFragment.h"
12#include "mcld/LD/LDSection.h"
13#include "mcld/LD/SectionData.h"
14#include "mcld/Script/Assignment.h"
15#include "mcld/Script/Operand.h"
16#include "mcld/Script/Operator.h"
17#include "mcld/Script/RpnExpr.h"
18#include "mcld/Script/StringList.h"
19#include "mcld/Script/WildcardPattern.h"
20
21#include <llvm/Support/Casting.h>
22
23#include <cassert>
24#include <cstring>
25#include <climits>
26#if !defined(MCLD_ON_WIN32)
27#include <fnmatch.h>
28#define fnmatch0(pattern, string) (fnmatch(pattern, string, 0) == 0)
29#else
30#include <windows.h>
31#include <shlwapi.h>
32#define fnmatch0(pattern, string) (PathMatchSpec(string, pattern) == true)
33#endif
34
35namespace mcld {
36
37//===----------------------------------------------------------------------===//
38// SectionMap::Input
39//===----------------------------------------------------------------------===//
40SectionMap::Input::Input(const std::string& pName,
41                         InputSectDesc::KeepPolicy pPolicy)
42    : m_Policy(pPolicy) {
43  m_Spec.m_pWildcardFile =
44      WildcardPattern::create("*", WildcardPattern::SORT_NONE);
45  m_Spec.m_pExcludeFiles = NULL;
46
47  StringList* sections = StringList::create();
48  sections->push_back(
49      WildcardPattern::create(pName, WildcardPattern::SORT_NONE));
50  m_Spec.m_pWildcardSections = sections;
51
52  m_pSection = LDSection::Create(pName, LDFileFormat::TEXT, 0, 0);
53  SectionData* sd = SectionData::Create(*m_pSection);
54  m_pSection->setSectionData(sd);
55  new NullFragment(sd);
56  new NullFragment(sd);
57}
58
59SectionMap::Input::Input(const InputSectDesc& pInputDesc)
60    : m_Policy(pInputDesc.policy()) {
61  m_Spec.m_pWildcardFile = pInputDesc.spec().m_pWildcardFile;
62  m_Spec.m_pExcludeFiles = pInputDesc.spec().m_pExcludeFiles;
63  m_Spec.m_pWildcardSections = pInputDesc.spec().m_pWildcardSections;
64  m_pSection = LDSection::Create("", LDFileFormat::TEXT, 0, 0);
65  SectionData* sd = SectionData::Create(*m_pSection);
66  m_pSection->setSectionData(sd);
67  new NullFragment(sd);
68  new NullFragment(sd);
69}
70
71//===----------------------------------------------------------------------===//
72// SectionMap::Output
73//===----------------------------------------------------------------------===//
74SectionMap::Output::Output(const std::string& pName)
75    : m_Name(pName), m_Order(UINT_MAX) {
76  m_Prolog.m_pVMA = NULL;
77  m_Prolog.m_Type = OutputSectDesc::LOAD;
78  m_Prolog.m_pLMA = NULL;
79  m_Prolog.m_pAlign = NULL;
80  m_Prolog.m_pSubAlign = NULL;
81  m_Prolog.m_Constraint = OutputSectDesc::NO_CONSTRAINT;
82
83  m_Epilog.m_pRegion = NULL;
84  m_Epilog.m_pLMARegion = NULL;
85  m_Epilog.m_pPhdrs = NULL;
86  m_Epilog.m_pFillExp = NULL;
87
88  m_pSection = LDSection::Create(pName, LDFileFormat::TEXT, 0, 0);
89  SectionData* sd = SectionData::Create(*m_pSection);
90  m_pSection->setSectionData(sd);
91
92  m_bIsDiscard = pName.compare("/DISCARD/") == 0;
93}
94
95SectionMap::Output::Output(const OutputSectDesc& pOutputDesc)
96    : m_Name(pOutputDesc.name()),
97      m_Prolog(pOutputDesc.prolog()),
98      m_Epilog(pOutputDesc.epilog()),
99      m_Order(UINT_MAX) {
100  m_pSection = LDSection::Create(m_Name, LDFileFormat::TEXT, 0, 0);
101  SectionData* sd = SectionData::Create(*m_pSection);
102  m_pSection->setSectionData(sd);
103
104  m_bIsDiscard = m_Name.compare("/DISCARD/") == 0;
105}
106
107bool SectionMap::Output::hasContent() const {
108  return m_pSection != NULL && m_pSection->size() != 0;
109}
110
111SectionMap::Output::const_dot_iterator
112SectionMap::Output::find_first_explicit_dot() const {
113  for (const_dot_iterator it = dot_begin(), ie = dot_end(); it != ie; ++it) {
114    if ((*it).type() == Assignment::DEFAULT)
115      return it;
116  }
117  return dot_end();
118}
119
120SectionMap::Output::dot_iterator SectionMap::Output::find_first_explicit_dot() {
121  for (dot_iterator it = dot_begin(), ie = dot_end(); it != ie; ++it) {
122    if ((*it).type() == Assignment::DEFAULT)
123      return it;
124  }
125  return dot_end();
126}
127
128SectionMap::Output::const_dot_iterator
129SectionMap::Output::find_last_explicit_dot() const {
130  typedef DotAssignments::const_reverse_iterator CONST_RIT;
131  for (CONST_RIT rit = dotAssignments().rbegin(), rie = dotAssignments().rend();
132       rit != rie;
133       ++rit) {
134    if ((*rit).type() == Assignment::DEFAULT) {
135      return dot_begin() +
136             (dotAssignments().size() - (rit - dotAssignments().rbegin()) - 1);
137    }
138  }
139  return dot_end();
140}
141
142SectionMap::Output::dot_iterator SectionMap::Output::find_last_explicit_dot() {
143  typedef DotAssignments::reverse_iterator RIT;
144  for (RIT rit = dotAssignments().rbegin(), rie = dotAssignments().rend();
145       rit != rie;
146       ++rit) {
147    if ((*rit).type() == Assignment::DEFAULT) {
148      return dot_begin() +
149             (dotAssignments().size() - (rit - dotAssignments().rbegin()) - 1);
150    }
151  }
152  return dot_end();
153}
154
155//===----------------------------------------------------------------------===//
156// SectionMap
157//===----------------------------------------------------------------------===//
158SectionMap::~SectionMap() {
159  iterator out, outBegin = begin(), outEnd = end();
160  for (out = outBegin; out != outEnd; ++out) {
161    if (*out != NULL) {
162      Output::iterator in, inBegin = (*out)->begin(), inEnd = (*out)->end();
163      for (in = inBegin; in != inEnd; ++in) {
164        if (*in != NULL)
165          delete *in;
166      }
167      delete *out;
168    }
169  }
170}
171
172SectionMap::const_mapping SectionMap::find(
173    const std::string& pInputFile,
174    const std::string& pInputSection) const {
175  const_iterator out, outBegin = begin(), outEnd = end();
176  for (out = outBegin; out != outEnd; ++out) {
177    Output::const_iterator in, inBegin = (*out)->begin(), inEnd = (*out)->end();
178    for (in = inBegin; in != inEnd; ++in) {
179      if (matched(**in, pInputFile, pInputSection))
180        return std::make_pair(*out, *in);
181    }
182  }
183  return std::make_pair((const Output*)NULL, (const Input*)NULL);
184}
185
186SectionMap::mapping SectionMap::find(const std::string& pInputFile,
187                                     const std::string& pInputSection) {
188  iterator out, outBegin = begin(), outEnd = end();
189  for (out = outBegin; out != outEnd; ++out) {
190    Output::iterator in, inBegin = (*out)->begin(), inEnd = (*out)->end();
191    for (in = inBegin; in != inEnd; ++in) {
192      if (matched(**in, pInputFile, pInputSection))
193        return std::make_pair(*out, *in);
194    }
195  }
196  return std::make_pair(reinterpret_cast<Output*>(NULL),
197                        reinterpret_cast<Input*>(NULL));
198}
199
200SectionMap::const_iterator SectionMap::find(
201    const std::string& pOutputSection) const {
202  const_iterator out, outBegin = begin(), outEnd = end();
203  for (out = outBegin; out != outEnd; ++out) {
204    if ((*out)->name().compare(pOutputSection) == 0)
205      return out;
206  }
207  return outEnd;
208}
209
210SectionMap::iterator SectionMap::find(const std::string& pOutputSection) {
211  iterator out, outBegin = begin(), outEnd = end();
212  for (out = outBegin; out != outEnd; ++out) {
213    if ((*out)->name().compare(pOutputSection) == 0)
214      return out;
215  }
216  return outEnd;
217}
218
219std::pair<SectionMap::mapping, bool> SectionMap::insert(
220    const std::string& pInputSection,
221    const std::string& pOutputSection,
222    InputSectDesc::KeepPolicy pPolicy) {
223  iterator out, outBegin = begin(), outEnd = end();
224  for (out = outBegin; out != outEnd; ++out) {
225    if ((*out)->name().compare(pOutputSection) == 0)
226      break;
227  }
228  if (out != end()) {
229    Output::iterator in, inBegin = (*out)->begin(), inEnd = (*out)->end();
230    for (in = inBegin; in != inEnd; ++in) {
231      if ((*in)->getSection()->name().compare(pInputSection) == 0)
232        break;
233    }
234
235    if (in != (*out)->end()) {
236      return std::make_pair(std::make_pair(*out, *in), false);
237    } else {
238      Input* input = new Input(pInputSection, pPolicy);
239      (*out)->append(input);
240      return std::make_pair(std::make_pair(*out, input), true);
241    }
242  }
243
244  Output* output = new Output(pOutputSection);
245  m_OutputDescList.push_back(output);
246  Input* input = new Input(pInputSection, pPolicy);
247  output->append(input);
248
249  return std::make_pair(std::make_pair(output, input), true);
250}
251
252std::pair<SectionMap::mapping, bool> SectionMap::insert(
253    const InputSectDesc& pInputDesc,
254    const OutputSectDesc& pOutputDesc) {
255  iterator out, outBegin = begin(), outEnd = end();
256  for (out = outBegin; out != outEnd; ++out) {
257    if ((*out)->name().compare(pOutputDesc.name()) == 0 &&
258        (*out)->prolog() == pOutputDesc.prolog() &&
259        (*out)->epilog() == pOutputDesc.epilog())
260      break;
261  }
262
263  if (out != end()) {
264    Output::iterator in, inBegin = (*out)->begin(), inEnd = (*out)->end();
265    for (in = inBegin; in != inEnd; ++in) {
266      if ((*in)->policy() == pInputDesc.policy() &&
267          (*in)->spec() == pInputDesc.spec())
268        break;
269    }
270
271    if (in != (*out)->end()) {
272      return std::make_pair(std::make_pair(*out, *in), false);
273    } else {
274      Input* input = new Input(pInputDesc);
275      (*out)->append(input);
276      return std::make_pair(std::make_pair(*out, input), true);
277    }
278  }
279
280  Output* output = new Output(pOutputDesc);
281  m_OutputDescList.push_back(output);
282  Input* input = new Input(pInputDesc);
283  output->append(input);
284
285  return std::make_pair(std::make_pair(output, input), true);
286}
287
288SectionMap::iterator SectionMap::insert(iterator pPosition,
289                                        LDSection* pSection) {
290  Output* output = new Output(pSection->name());
291  output->append(new Input(pSection->name(), InputSectDesc::NoKeep));
292  output->setSection(pSection);
293  return m_OutputDescList.insert(pPosition, output);
294}
295
296bool SectionMap::matched(const SectionMap::Input& pInput,
297                         const std::string& pInputFile,
298                         const std::string& pInputSection) const {
299  if (pInput.spec().hasFile() && !matched(pInput.spec().file(), pInputFile))
300    return false;
301
302  if (pInput.spec().hasExcludeFiles()) {
303    StringList::const_iterator file, fileEnd;
304    fileEnd = pInput.spec().excludeFiles().end();
305    for (file = pInput.spec().excludeFiles().begin(); file != fileEnd; ++file) {
306      if (matched(llvm::cast<WildcardPattern>(**file), pInputFile)) {
307        return false;
308      }
309    }
310  }
311
312  if (pInput.spec().hasSections()) {
313    StringList::const_iterator sect, sectEnd = pInput.spec().sections().end();
314    for (sect = pInput.spec().sections().begin(); sect != sectEnd; ++sect) {
315      if (matched(llvm::cast<WildcardPattern>(**sect), pInputSection)) {
316        return true;
317      }
318    }
319  }
320
321  return false;
322}
323
324bool SectionMap::matched(const WildcardPattern& pPattern,
325                         const std::string& pName) const {
326  if (pPattern.isPrefix()) {
327    llvm::StringRef name(pName);
328    return name.startswith(pPattern.prefix());
329  } else {
330    return fnmatch0(pPattern.name().c_str(), pName.c_str());
331  }
332}
333
334// fixupDotSymbols - ensure the dot symbols are valid
335void SectionMap::fixupDotSymbols() {
336  for (iterator it = begin() + 1, ie = end(); it != ie; ++it) {
337    // fixup the 1st explicit dot assignment if needed
338    if (!(*it)->dotAssignments().empty()) {
339      Output::dot_iterator dot = (*it)->find_first_explicit_dot();
340      if (dot != (*it)->dot_end() && (*dot).symbol().isDot() &&
341          (*dot).getRpnExpr().hasDot()) {
342        Assignment assign(Assignment::OUTPUT_SECTION,
343                          Assignment::DEFAULT,
344                          *SymOperand::create("."),
345                          *RpnExpr::buildHelperExpr(it - 1));
346        Output::dot_iterator ref = (*it)->dotAssignments().insert(dot, assign);
347        for (RpnExpr::iterator tok = (*dot).getRpnExpr().begin(),
348                               tokEnd = (*dot).getRpnExpr().end();
349             tok != tokEnd;
350             ++tok) {
351          if ((*tok)->kind() == ExprToken::OPERAND &&
352              llvm::cast<Operand>(*tok)->isDot())
353            *tok = &((*ref).symbol());
354        }  // for each token in the RHS expr of the dot assignment
355      }
356    }
357
358    // fixup dot in output VMA if needed
359    if ((*it)->prolog().hasVMA() && (*it)->prolog().vma().hasDot()) {
360      Output::dot_iterator dot = (*it)->find_last_explicit_dot();
361      if (dot == (*it)->dot_end()) {
362        Assignment assign(Assignment::OUTPUT_SECTION,
363                          Assignment::DEFAULT,
364                          *SymOperand::create("."),
365                          *RpnExpr::buildHelperExpr(it - 1));
366        dot = (*it)->dotAssignments().insert(dot, assign);
367      }
368      for (RpnExpr::iterator tok = (*it)->prolog().vma().begin(),
369                             tokEnd = (*it)->prolog().vma().end();
370           tok != tokEnd;
371           ++tok) {
372        if ((*tok)->kind() == ExprToken::OPERAND &&
373            llvm::cast<Operand>(*tok)->isDot())
374          *tok = &((*dot).symbol());
375      }  // for each token in the RHS expr of the dot assignment
376    }
377  }  // for each output section
378}
379
380}  // namespace mcld
381