1 //===- lld/Core/Simple.h - Simple implementations of Atom and File --------===//
2 //
3 //                             The LLVM Linker
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// Provide simple implementations for Atoms and File.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLD_CORE_SIMPLE_H
16 #define LLD_CORE_SIMPLE_H
17 
18 #include "lld/Core/AbsoluteAtom.h"
19 #include "lld/Core/Atom.h"
20 #include "lld/Core/DefinedAtom.h"
21 #include "lld/Core/File.h"
22 #include "lld/Core/Reference.h"
23 #include "lld/Core/SharedLibraryAtom.h"
24 #include "lld/Core/UndefinedAtom.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/StringRef.h"
27 #include "llvm/ADT/ilist.h"
28 #include "llvm/ADT/ilist_node.h"
29 #include "llvm/Support/Allocator.h"
30 #include "llvm/Support/Casting.h"
31 #include "llvm/Support/ErrorHandling.h"
32 #include <algorithm>
33 #include <cassert>
34 #include <cstdint>
35 #include <functional>
36 
37 namespace lld {
38 
39 class SimpleFile : public File {
40 public:
SimpleFile(StringRef path,File::Kind kind)41   SimpleFile(StringRef path, File::Kind kind)
42     : File(path, kind) {}
43 
~SimpleFile()44   ~SimpleFile() override {
45     _defined.clear();
46     _undefined.clear();
47     _shared.clear();
48     _absolute.clear();
49   }
50 
addAtom(DefinedAtom & a)51   void addAtom(DefinedAtom &a) {
52     _defined.push_back(OwningAtomPtr<DefinedAtom>(&a));
53   }
addAtom(UndefinedAtom & a)54   void addAtom(UndefinedAtom &a) {
55     _undefined.push_back(OwningAtomPtr<UndefinedAtom>(&a));
56   }
addAtom(SharedLibraryAtom & a)57   void addAtom(SharedLibraryAtom &a) {
58     _shared.push_back(OwningAtomPtr<SharedLibraryAtom>(&a));
59   }
addAtom(AbsoluteAtom & a)60   void addAtom(AbsoluteAtom &a) {
61     _absolute.push_back(OwningAtomPtr<AbsoluteAtom>(&a));
62   }
63 
addAtom(const Atom & atom)64   void addAtom(const Atom &atom) {
65     if (auto *p = dyn_cast<DefinedAtom>(&atom)) {
66       addAtom(const_cast<DefinedAtom &>(*p));
67     } else if (auto *p = dyn_cast<UndefinedAtom>(&atom)) {
68       addAtom(const_cast<UndefinedAtom &>(*p));
69     } else if (auto *p = dyn_cast<SharedLibraryAtom>(&atom)) {
70       addAtom(const_cast<SharedLibraryAtom &>(*p));
71     } else if (auto *p = dyn_cast<AbsoluteAtom>(&atom)) {
72       addAtom(const_cast<AbsoluteAtom &>(*p));
73     } else {
74       llvm_unreachable("atom has unknown definition kind");
75     }
76   }
77 
removeDefinedAtomsIf(std::function<bool (const DefinedAtom *)> pred)78   void removeDefinedAtomsIf(std::function<bool(const DefinedAtom *)> pred) {
79     auto &atoms = _defined;
80     auto newEnd = std::remove_if(atoms.begin(), atoms.end(),
81                                  [&pred](OwningAtomPtr<DefinedAtom> &p) {
82                                    return pred(p.get());
83                                  });
84     atoms.erase(newEnd, atoms.end());
85   }
86 
defined()87   const AtomRange<DefinedAtom> defined() const override { return _defined; }
88 
undefined()89   const AtomRange<UndefinedAtom> undefined() const override {
90     return _undefined;
91   }
92 
sharedLibrary()93   const AtomRange<SharedLibraryAtom> sharedLibrary() const override {
94     return _shared;
95   }
96 
absolute()97   const AtomRange<AbsoluteAtom> absolute() const override {
98     return _absolute;
99   }
100 
clearAtoms()101   void clearAtoms() override {
102     _defined.clear();
103     _undefined.clear();
104     _shared.clear();
105     _absolute.clear();
106   }
107 
108 private:
109   AtomVector<DefinedAtom> _defined;
110   AtomVector<UndefinedAtom> _undefined;
111   AtomVector<SharedLibraryAtom> _shared;
112   AtomVector<AbsoluteAtom> _absolute;
113 };
114 
115 class SimpleReference : public Reference,
116                         public llvm::ilist_node<SimpleReference> {
117 public:
SimpleReference(Reference::KindNamespace ns,Reference::KindArch arch,Reference::KindValue value,uint64_t off,const Atom * t,Reference::Addend a)118   SimpleReference(Reference::KindNamespace ns, Reference::KindArch arch,
119                   Reference::KindValue value, uint64_t off, const Atom *t,
120                   Reference::Addend a)
121       : Reference(ns, arch, value), _target(t), _offsetInAtom(off), _addend(a) {
122   }
SimpleReference()123   SimpleReference()
124       : Reference(Reference::KindNamespace::all, Reference::KindArch::all, 0),
125         _target(nullptr), _offsetInAtom(0), _addend(0) {}
126 
offsetInAtom()127   uint64_t offsetInAtom() const override { return _offsetInAtom; }
128 
target()129   const Atom *target() const override {
130     assert(_target);
131     return _target;
132   }
133 
addend()134   Addend addend() const override { return _addend; }
setAddend(Addend a)135   void setAddend(Addend a) override { _addend = a; }
setTarget(const Atom * newAtom)136   void setTarget(const Atom *newAtom) override { _target = newAtom; }
137 
138 private:
139   const Atom *_target;
140   uint64_t _offsetInAtom;
141   Addend _addend;
142 };
143 
144 class SimpleDefinedAtom : public DefinedAtom {
145 public:
SimpleDefinedAtom(const File & f)146   explicit SimpleDefinedAtom(const File &f)
147       : _file(f), _ordinal(f.getNextAtomOrdinalAndIncrement()) {}
148 
~SimpleDefinedAtom()149   ~SimpleDefinedAtom() override {
150     _references.clearAndLeakNodesUnsafely();
151   }
152 
file()153   const File &file() const override { return _file; }
154 
name()155   StringRef name() const override { return StringRef(); }
156 
ordinal()157   uint64_t ordinal() const override { return _ordinal; }
158 
scope()159   Scope scope() const override { return DefinedAtom::scopeLinkageUnit; }
160 
interposable()161   Interposable interposable() const override {
162     return DefinedAtom::interposeNo;
163   }
164 
merge()165   Merge merge() const override { return DefinedAtom::mergeNo; }
166 
alignment()167   Alignment alignment() const override { return 1; }
168 
sectionChoice()169   SectionChoice sectionChoice() const override {
170     return DefinedAtom::sectionBasedOnContent;
171   }
172 
customSectionName()173   StringRef customSectionName() const override { return StringRef(); }
deadStrip()174   DeadStripKind deadStrip() const override {
175     return DefinedAtom::deadStripNormal;
176   }
177 
begin()178   DefinedAtom::reference_iterator begin() const override {
179     const void *it =
180         reinterpret_cast<const void *>(_references.begin().getNodePtr());
181     return reference_iterator(*this, it);
182   }
183 
end()184   DefinedAtom::reference_iterator end() const override {
185     const void *it =
186         reinterpret_cast<const void *>(_references.end().getNodePtr());
187     return reference_iterator(*this, it);
188   }
189 
derefIterator(const void * it)190   const Reference *derefIterator(const void *it) const override {
191     return &*RefList::const_iterator(
192         *reinterpret_cast<const llvm::ilist_node<SimpleReference> *>(it));
193   }
194 
incrementIterator(const void * & it)195   void incrementIterator(const void *&it) const override {
196     RefList::const_iterator ref(
197         *reinterpret_cast<const llvm::ilist_node<SimpleReference> *>(it));
198     it = reinterpret_cast<const void *>(std::next(ref).getNodePtr());
199   }
200 
addReference(Reference::KindNamespace ns,Reference::KindArch arch,Reference::KindValue kindValue,uint64_t off,const Atom * target,Reference::Addend a)201   void addReference(Reference::KindNamespace ns,
202                     Reference::KindArch arch,
203                     Reference::KindValue kindValue, uint64_t off,
204                     const Atom *target, Reference::Addend a) override {
205     assert(target && "trying to create reference to nothing");
206     auto node = new (_file.allocator())
207         SimpleReference(ns, arch, kindValue, off, target, a);
208     _references.push_back(node);
209   }
210 
211   /// Sort references in a canonical order (by offset, then by kind).
sortReferences()212   void sortReferences() const {
213     // Cannot sort a linked  list, so move elements into a temporary vector,
214     // sort the vector, then reconstruct the list.
215     llvm::SmallVector<SimpleReference *, 16> elements;
216     for (SimpleReference &node : _references) {
217       elements.push_back(&node);
218     }
219     std::sort(elements.begin(), elements.end(),
220         [] (const SimpleReference *lhs, const SimpleReference *rhs) -> bool {
221           uint64_t lhsOffset = lhs->offsetInAtom();
222           uint64_t rhsOffset = rhs->offsetInAtom();
223           if (rhsOffset != lhsOffset)
224             return (lhsOffset < rhsOffset);
225           if (rhs->kindNamespace() != lhs->kindNamespace())
226             return (lhs->kindNamespace() < rhs->kindNamespace());
227           if (rhs->kindArch() != lhs->kindArch())
228             return (lhs->kindArch() < rhs->kindArch());
229           return (lhs->kindValue() < rhs->kindValue());
230         });
231     _references.clearAndLeakNodesUnsafely();
232     for (SimpleReference *node : elements) {
233       _references.push_back(node);
234     }
235   }
236 
setOrdinal(uint64_t ord)237   void setOrdinal(uint64_t ord) { _ordinal = ord; }
238 
239 private:
240   typedef llvm::ilist<SimpleReference> RefList;
241 
242   const File &_file;
243   uint64_t _ordinal;
244   mutable RefList _references;
245 };
246 
247 class SimpleUndefinedAtom : public UndefinedAtom {
248 public:
SimpleUndefinedAtom(const File & f,StringRef name)249   SimpleUndefinedAtom(const File &f, StringRef name) : _file(f), _name(name) {
250     assert(!name.empty() && "UndefinedAtoms must have a name");
251   }
252 
253   ~SimpleUndefinedAtom() override = default;
254 
255   /// file - returns the File that produced/owns this Atom
file()256   const File &file() const override { return _file; }
257 
258   /// name - The name of the atom. For a function atom, it is the (mangled)
259   /// name of the function.
name()260   StringRef name() const override { return _name; }
261 
canBeNull()262   CanBeNull canBeNull() const override { return UndefinedAtom::canBeNullNever; }
263 
264 private:
265   const File &_file;
266   StringRef _name;
267 };
268 
269 } // end namespace lld
270 
271 #endif // LLD_CORE_SIMPLE_H
272