GarbageCollection.cpp revision 87f34658dec9097d987d254a990ea7f311bfc95f 
1//===- GarbageCollection.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/Fragment.h>
10#include <mcld/Fragment/Relocation.h>
11#include <mcld/LD/GarbageCollection.h>
12#include <mcld/LD/LDContext.h>
13#include <mcld/LD/LDFileFormat.h>
14#include <mcld/LD/LDSection.h>
15#include <mcld/LD/LDSymbol.h>
16#include <mcld/LD/SectionData.h>
17#include <mcld/LD/RelocData.h>
18#include <mcld/LinkerConfig.h>
19#include <mcld/LinkerScript.h>
20#include <mcld/Module.h>
21#include <mcld/Target/TargetLDBackend.h>
22
23#include <llvm/Support/Casting.h>
24
25#include <queue>
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
35using namespace mcld;
36
37//===----------------------------------------------------------------------===//
38// Non-member functions
39//===----------------------------------------------------------------------===//
40// FIXME: these rules should be added into SectionMap, while currently adding to
41// SectionMap will cause the output order change in .text section and leads to
42// the .ARM.exidx order incorrect. We should sort the .ARM.exidx.
43static const char* pattern_to_keep[] =
44{
45  ".text*personality*",
46  ".data*personality*",
47  ".gnu.linkonce.d*personality*",
48  ".sdata*personality*"
49};
50
51/// shouldKeep - check the section name for the keep sections
52static bool shouldKeep(const std::string& pName)
53{
54  static const unsigned int pattern_size =
55                           sizeof(pattern_to_keep) / sizeof(pattern_to_keep[0]);
56  for (unsigned int i=0; i < pattern_size; ++i) {
57    if (fnmatch0(pattern_to_keep[i], pName.c_str()))
58      return true;
59  }
60  return false;
61}
62
63/// shouldProcessGC - check if the section kind is handled in GC
64static bool mayProcessGC(const LDSection& pSection)
65{
66  if (pSection.kind() == LDFileFormat::Regular ||
67      pSection.kind() == LDFileFormat::BSS ||
68      pSection.kind() == LDFileFormat::GCCExceptTable)
69    return true;
70  return false;
71}
72
73//===----------------------------------------------------------------------===//
74// GarbageCollection::SectionReachedListMap
75//===----------------------------------------------------------------------===//
76void
77GarbageCollection::SectionReachedListMap::addReference(const LDSection& pFrom,
78                                                       const LDSection& pTo)
79{
80  m_ReachedSections[&pFrom].insert(&pTo);
81}
82
83GarbageCollection::SectionListTy&
84GarbageCollection::SectionReachedListMap::getReachedList(
85                                                      const LDSection& pSection)
86{
87  return m_ReachedSections[&pSection];
88}
89
90GarbageCollection::SectionListTy*
91GarbageCollection::SectionReachedListMap::findReachedList(
92                                                      const LDSection& pSection)
93{
94  ReachedSectionsTy::iterator it = m_ReachedSections.find(&pSection);
95  if (it == m_ReachedSections.end())
96    return NULL;
97  return &it->second;
98}
99
100//===----------------------------------------------------------------------===//
101// GarbageCollection
102//===----------------------------------------------------------------------===//
103GarbageCollection::GarbageCollection(const LinkerConfig& pConfig,
104                                     const TargetLDBackend& pBackend,
105                                     Module& pModule)
106  : m_Config(pConfig), m_Backend(pBackend), m_Module(pModule)
107{
108}
109
110GarbageCollection::~GarbageCollection()
111{
112}
113
114bool GarbageCollection::run()
115{
116  // 1. traverse all the relocations to set up the reached sections of each
117  // section
118  setUpReachedSections();
119  m_Backend.setUpReachedSectionsForGC(m_Module, m_SectionReachedListMap);
120
121  // 2. get all sections defined the entry point
122  SectionVecTy entry;
123  getEntrySections(entry);
124
125  // 3. find all the referenced sections those can be reached by entry
126  findReferencedSections(entry);
127
128  // 4. stripSections - set the unreached sections to Ignore
129  stripSections();
130  return true;
131}
132
133void GarbageCollection::setUpReachedSections()
134{
135  // traverse all the input relocations to setup the reached sections
136  Module::obj_iterator input, inEnd = m_Module.obj_end();
137  for (input = m_Module.obj_begin(); input != inEnd; ++input) {
138    LDContext::sect_iterator rs, rsEnd = (*input)->context()->relocSectEnd();
139    for (rs = (*input)->context()->relocSectBegin(); rs != rsEnd; ++rs) {
140      // bypass the discarded relocation section
141      // 1. its section kind is changed to Ignore. (The target section is a
142      // discarded group section.)
143      // 2. it has no reloc data. (All symbols in the input relocs are in the
144      // discarded group sections)
145      LDSection* reloc_sect = *rs;
146      LDSection* apply_sect = reloc_sect->getLink();
147      if ((LDFileFormat::Ignore == reloc_sect->kind()) ||
148          (!reloc_sect->hasRelocData()))
149        continue;
150
151      // bypass the apply target sections which are not handled by gc
152      if (!mayProcessGC(*apply_sect))
153        continue;
154
155      bool add_first = false;
156      SectionListTy* reached_sects = NULL;
157      RelocData::iterator reloc_it, rEnd = reloc_sect->getRelocData()->end();
158      for (reloc_it = reloc_sect->getRelocData()->begin(); reloc_it != rEnd;
159                                                                   ++reloc_it) {
160        Relocation* reloc = llvm::cast<Relocation>(reloc_it);
161        ResolveInfo* sym = reloc->symInfo();
162        // only the target symbols defined in the input fragments can make the
163        // reference
164        if (NULL == sym)
165          continue;
166        if (!sym->isDefine() || !sym->outSymbol()->hasFragRef())
167          continue;
168
169        // only the target symbols defined in the concerned sections can make
170        // the reference
171        const LDSection* target_sect =
172                &sym->outSymbol()->fragRef()->frag()->getParent()->getSection();
173        if (!mayProcessGC(*target_sect))
174          continue;
175
176        // setup the reached list, if we first add the element to reached list
177        // of this section, create an entry in ReachedSections map
178        if (!add_first) {
179          reached_sects = &m_SectionReachedListMap.getReachedList(*apply_sect);
180          add_first = true;
181        }
182        reached_sects->insert(target_sect);
183      }
184      reached_sects = NULL;
185      add_first = false;
186    }
187  }
188}
189
190void GarbageCollection::getEntrySections(SectionVecTy& pEntry)
191{
192  // all the KEEP sections defined in ldscript are entries, traverse all the
193  // input sections and check the SectionMap to find the KEEP sections
194  Module::obj_iterator obj, objEnd = m_Module.obj_end();
195  SectionMap& sect_map = m_Module.getScript().sectionMap();
196  for (obj = m_Module.obj_begin(); obj != objEnd; ++obj) {
197    const std::string input_name = (*obj)->name();
198    LDContext::sect_iterator sect, sectEnd = (*obj)->context()->sectEnd();
199    for (sect = (*obj)->context()->sectBegin(); sect != sectEnd; ++sect) {
200      LDSection* section = *sect;
201      if (!mayProcessGC(*section))
202        continue;
203
204      SectionMap::Input* sm_input =
205                              sect_map.find(input_name, section->name()).second;
206      if (((sm_input != NULL) && (InputSectDesc::Keep == sm_input->policy())) ||
207          shouldKeep(section->name()))
208        pEntry.push_back(section);
209    }
210  }
211
212  // get the sections those the entry symbols defined in
213  if (LinkerConfig::Exec == m_Config.codeGenType() ||
214                                                   m_Config.options().isPIE()) {
215    // when building executable
216    // 1. the entry symbol is the entry
217    LDSymbol* entry_sym =
218                m_Module.getNamePool().findSymbol(m_Backend.getEntry(m_Module));
219    assert(NULL != entry_sym);
220    pEntry.push_back(&entry_sym->fragRef()->frag()->getParent()->getSection());
221
222    // 2. the symbols have been seen in dynamice objects are entries
223    NamePool::syminfo_iterator info_it,
224                                info_end = m_Module.getNamePool().syminfo_end();
225    for (info_it = m_Module.getNamePool().syminfo_begin(); info_it != info_end;
226                                                                    ++info_it) {
227      ResolveInfo* info = info_it.getEntry();
228      if (!info->isDefine() || info->isLocal())
229        continue;
230
231      if (!info->isInDyn())
232        continue;
233
234      LDSymbol* sym = info->outSymbol();
235      if (NULL == sym || !sym->hasFragRef())
236        continue;
237
238      // only the target symbols defined in the concerned sections can be
239      // entries
240      const LDSection* sect =
241                             &sym->fragRef()->frag()->getParent()->getSection();
242      if (!mayProcessGC(*sect))
243        continue;
244
245      pEntry.push_back(sect);
246    }
247  }
248
249  else {
250    // when building shared objects, the global define symbols are entries
251    NamePool::syminfo_iterator info_it,
252                                info_end = m_Module.getNamePool().syminfo_end();
253    for (info_it = m_Module.getNamePool().syminfo_begin(); info_it != info_end;
254                                                                    ++info_it) {
255      ResolveInfo* info = info_it.getEntry();
256      if (!info->isDefine() ||
257          info->isLocal()   ||
258          info->shouldForceLocal(m_Config))
259        continue;
260      LDSymbol* sym = info->outSymbol();
261      if (NULL == sym || !sym->hasFragRef())
262        continue;
263
264      // only the target symbols defined in the concerned sections can be
265      // entries
266      const LDSection* sect =
267                             &sym->fragRef()->frag()->getParent()->getSection();
268      if (!mayProcessGC(*sect))
269        continue;
270      pEntry.push_back(sect);
271    }
272  }
273}
274
275void GarbageCollection::findReferencedSections(SectionVecTy& pEntry)
276{
277  // list of sections waiting to be processed
278  typedef std::queue<const LDSection*> WorkListTy;
279  WorkListTy work_list;
280  // start from each entry, resolve the transitive closure
281  SectionVecTy::iterator entry_it, entry_end = pEntry.end();
282  for (entry_it = pEntry.begin(); entry_it != entry_end; ++entry_it) {
283    // add entry point to work list
284    work_list.push(*entry_it);
285
286    // add section from the work_list to the referencedSections until every
287    // reached sections are added
288    while (!work_list.empty()) {
289      const LDSection* sect = work_list.front();
290      work_list.pop();
291      // add section to the ReferencedSections, if the section has been put into
292      // referencedSections, skip this section
293      if (!m_ReferencedSections.insert(sect).second)
294        continue;
295
296      // get the section reached list, if the section do not has one, which
297      // means no referenced between it and other sections, then skip it
298      SectionListTy* reach_list =
299                                 m_SectionReachedListMap.findReachedList(*sect);
300      if (NULL == reach_list)
301        continue;
302
303      // put the reached sections to work list, skip the one already be in
304      // referencedSections
305      SectionListTy::iterator it, end = reach_list->end();
306      for (it = reach_list->begin(); it != end; ++it) {
307        if (m_ReferencedSections.find(*it) == m_ReferencedSections.end())
308          work_list.push(*it);
309      }
310    }
311  }
312}
313
314void GarbageCollection::stripSections()
315{
316  // Traverse all the input Regular and BSS sections, if a section is not found
317  // in the ReferencedSections, then it should be garbage collected
318  Module::obj_iterator obj, objEnd = m_Module.obj_end();
319  for (obj = m_Module.obj_begin(); obj != objEnd; ++obj) {
320    LDContext::sect_iterator sect, sectEnd = (*obj)->context()->sectEnd();
321    for (sect = (*obj)->context()->sectBegin(); sect != sectEnd; ++sect) {
322      LDSection* section = *sect;
323      if (!mayProcessGC(*section))
324        continue;
325
326      if (m_ReferencedSections.find(section) == m_ReferencedSections.end())
327        section->setKind(LDFileFormat::Ignore);
328    }
329  }
330
331  // Traverse all the relocation sections, if its target section is set to
332  // Ignore, then set the relocation section to Ignore as well
333  Module::obj_iterator input, inEnd = m_Module.obj_end();
334  for (input = m_Module.obj_begin(); input != inEnd; ++input) {
335    LDContext::sect_iterator rs, rsEnd = (*input)->context()->relocSectEnd();
336    for (rs = (*input)->context()->relocSectBegin(); rs != rsEnd; ++rs) {
337      LDSection* reloc_sect = *rs;
338      if (LDFileFormat::Ignore == reloc_sect->getLink()->kind())
339        reloc_sect->setKind(LDFileFormat::Ignore);
340    }
341  }
342}
343
344