1 //===- LinkerScript.h -------------------------------------------*- C++ -*-===//
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 #ifndef LLD_ELF_LINKER_SCRIPT_H
11 #define LLD_ELF_LINKER_SCRIPT_H
12 
13 #include "Config.h"
14 #include "Strings.h"
15 #include "Writer.h"
16 #include "lld/Common/LLVM.h"
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/DenseSet.h"
20 #include "llvm/ADT/MapVector.h"
21 #include "llvm/ADT/StringRef.h"
22 #include "llvm/Support/MemoryBuffer.h"
23 #include <cstddef>
24 #include <cstdint>
25 #include <functional>
26 #include <memory>
27 #include <vector>
28 
29 namespace lld {
30 namespace elf {
31 
32 class Defined;
33 class Symbol;
34 class InputSectionBase;
35 class InputSection;
36 class OutputSection;
37 class OutputSectionFactory;
38 class InputSectionBase;
39 class SectionBase;
40 
41 // This represents an r-value in the linker script.
42 struct ExprValue {
43   ExprValue(SectionBase *Sec, bool ForceAbsolute, uint64_t Val,
44             const Twine &Loc)
45       : Sec(Sec), ForceAbsolute(ForceAbsolute), Val(Val), Loc(Loc.str()) {}
46 
47   ExprValue(uint64_t Val) : ExprValue(nullptr, false, Val, "") {}
48 
49   bool isAbsolute() const { return ForceAbsolute || Sec == nullptr; }
50   uint64_t getValue() const;
51   uint64_t getSecAddr() const;
52   uint64_t getSectionOffset() const;
53 
54   // If a value is relative to a section, it has a non-null Sec.
55   SectionBase *Sec;
56 
57   // True if this expression is enclosed in ABSOLUTE().
58   // This flag affects the return value of getValue().
59   bool ForceAbsolute;
60 
61   uint64_t Val;
62   uint64_t Alignment = 1;
63 
64   // Original source location. Used for error messages.
65   std::string Loc;
66 };
67 
68 // This represents an expression in the linker script.
69 // ScriptParser::readExpr reads an expression and returns an Expr.
70 // Later, we evaluate the expression by calling the function.
71 typedef std::function<ExprValue()> Expr;
72 
73 // This enum is used to implement linker script SECTIONS command.
74 // https://sourceware.org/binutils/docs/ld/SECTIONS.html#SECTIONS
75 enum SectionsCommandKind {
76   AssignmentKind, // . = expr or <sym> = expr
77   OutputSectionKind,
78   InputSectionKind,
79   AssertKind, // ASSERT(expr)
80   ByteKind    // BYTE(expr), SHORT(expr), LONG(expr) or QUAD(expr)
81 };
82 
83 struct BaseCommand {
84   BaseCommand(int K) : Kind(K) {}
85   int Kind;
86 };
87 
88 // This represents ". = <expr>" or "<symbol> = <expr>".
89 struct SymbolAssignment : BaseCommand {
90   SymbolAssignment(StringRef Name, Expr E, std::string Loc)
91       : BaseCommand(AssignmentKind), Name(Name), Expression(E), Location(Loc) {}
92 
93   static bool classof(const BaseCommand *C) {
94     return C->Kind == AssignmentKind;
95   }
96 
97   // The LHS of an expression. Name is either a symbol name or ".".
98   StringRef Name;
99   Defined *Sym = nullptr;
100 
101   // The RHS of an expression.
102   Expr Expression;
103 
104   // Command attributes for PROVIDE, HIDDEN and PROVIDE_HIDDEN.
105   bool Provide = false;
106   bool Hidden = false;
107 
108   // Holds file name and line number for error reporting.
109   std::string Location;
110 };
111 
112 // Linker scripts allow additional constraints to be put on ouput sections.
113 // If an output section is marked as ONLY_IF_RO, the section is created
114 // only if its input sections are read-only. Likewise, an output section
115 // with ONLY_IF_RW is created if all input sections are RW.
116 enum class ConstraintKind { NoConstraint, ReadOnly, ReadWrite };
117 
118 // This struct is used to represent the location and size of regions of
119 // target memory. Instances of the struct are created by parsing the
120 // MEMORY command.
121 struct MemoryRegion {
122   std::string Name;
123   uint64_t Origin;
124   uint64_t Length;
125   uint32_t Flags;
126   uint32_t NegFlags;
127 };
128 
129 // This struct represents one section match pattern in SECTIONS() command.
130 // It can optionally have negative match pattern for EXCLUDED_FILE command.
131 // Also it may be surrounded with SORT() command, so contains sorting rules.
132 struct SectionPattern {
133   SectionPattern(StringMatcher &&Pat1, StringMatcher &&Pat2)
134       : ExcludedFilePat(Pat1), SectionPat(Pat2) {}
135 
136   StringMatcher ExcludedFilePat;
137   StringMatcher SectionPat;
138   SortSectionPolicy SortOuter;
139   SortSectionPolicy SortInner;
140 };
141 
142 class ThunkSection;
143 struct InputSectionDescription : BaseCommand {
144   InputSectionDescription(StringRef FilePattern)
145       : BaseCommand(InputSectionKind), FilePat(FilePattern) {}
146 
147   static bool classof(const BaseCommand *C) {
148     return C->Kind == InputSectionKind;
149   }
150 
151   StringMatcher FilePat;
152 
153   // Input sections that matches at least one of SectionPatterns
154   // will be associated with this InputSectionDescription.
155   std::vector<SectionPattern> SectionPatterns;
156 
157   std::vector<InputSection *> Sections;
158 
159   // Temporary record of synthetic ThunkSection instances and the pass that
160   // they were created in. This is used to insert newly created ThunkSections
161   // into Sections at the end of a createThunks() pass.
162   std::vector<std::pair<ThunkSection *, uint32_t>> ThunkSections;
163 };
164 
165 // Represents an ASSERT().
166 struct AssertCommand : BaseCommand {
167   AssertCommand(Expr E) : BaseCommand(AssertKind), Expression(E) {}
168 
169   static bool classof(const BaseCommand *C) { return C->Kind == AssertKind; }
170 
171   Expr Expression;
172 };
173 
174 // Represents BYTE(), SHORT(), LONG(), or QUAD().
175 struct ByteCommand : BaseCommand {
176   ByteCommand(Expr E, unsigned Size)
177       : BaseCommand(ByteKind), Expression(E), Size(Size) {}
178 
179   static bool classof(const BaseCommand *C) { return C->Kind == ByteKind; }
180 
181   Expr Expression;
182   unsigned Offset;
183   unsigned Size;
184 };
185 
186 struct PhdrsCommand {
187   StringRef Name;
188   unsigned Type = llvm::ELF::PT_NULL;
189   bool HasFilehdr = false;
190   bool HasPhdrs = false;
191   llvm::Optional<unsigned> Flags;
192   Expr LMAExpr = nullptr;
193 };
194 
195 class LinkerScript final {
196   // Temporary state used in processSectionCommands() and assignAddresses()
197   // that must be reinitialized for each call to the above functions, and must
198   // not be used outside of the scope of a call to the above functions.
199   struct AddressState {
200     AddressState();
201     uint64_t ThreadBssOffset = 0;
202     OutputSection *OutSec = nullptr;
203     MemoryRegion *MemRegion = nullptr;
204     llvm::DenseMap<const MemoryRegion *, uint64_t> MemRegionOffset;
205     std::function<uint64_t()> LMAOffset;
206   };
207 
208   llvm::DenseMap<StringRef, OutputSection *> NameToOutputSection;
209 
210   void addSymbol(SymbolAssignment *Cmd);
211   void assignSymbol(SymbolAssignment *Cmd, bool InSec);
212   void setDot(Expr E, const Twine &Loc, bool InSec);
213 
214   std::vector<InputSection *>
215   computeInputSections(const InputSectionDescription *,
216                        const llvm::DenseMap<SectionBase *, int> &Order);
217 
218   std::vector<InputSection *>
219   createInputSectionList(OutputSection &Cmd,
220                          const llvm::DenseMap<SectionBase *, int> &Order);
221 
222   std::vector<size_t> getPhdrIndices(OutputSection *Sec);
223 
224   MemoryRegion *findMemoryRegion(OutputSection *Sec);
225 
226   void switchTo(OutputSection *Sec);
227   uint64_t advance(uint64_t Size, unsigned Align);
228   void output(InputSection *Sec);
229 
230   void assignOffsets(OutputSection *Sec);
231 
232   // Ctx captures the local AddressState and makes it accessible
233   // deliberately. This is needed as there are some cases where we cannot just
234   // thread the current state through to a lambda function created by the
235   // script parser.
236   // This should remain a plain pointer as its lifetime is smaller than
237   // LinkerScript.
238   AddressState *Ctx = nullptr;
239 
240   OutputSection *Aether;
241 
242   uint64_t Dot;
243 
244 public:
245   OutputSection *createOutputSection(StringRef Name, StringRef Location);
246   OutputSection *getOrCreateOutputSection(StringRef Name);
247 
248   bool hasPhdrsCommands() { return !PhdrsCommands.empty(); }
249   uint64_t getDot() { return Dot; }
250   void discard(ArrayRef<InputSection *> V);
251 
252   ExprValue getSymbolValue(StringRef Name, const Twine &Loc);
253 
254   void addOrphanSections();
255   void removeEmptyCommands();
256   void adjustSectionsBeforeSorting();
257   void adjustSectionsAfterSorting();
258 
259   std::vector<PhdrEntry *> createPhdrs();
260   bool needsInterpSection();
261 
262   bool shouldKeep(InputSectionBase *S);
263   void assignAddresses();
264   void allocateHeaders(std::vector<PhdrEntry *> &Phdrs);
265   void processSectionCommands();
266 
267   // SECTIONS command list.
268   std::vector<BaseCommand *> SectionCommands;
269 
270   // PHDRS command list.
271   std::vector<PhdrsCommand> PhdrsCommands;
272 
273   bool HasSectionsCommand = false;
274   bool ErrorOnMissingSection = false;
275 
276   // List of section patterns specified with KEEP commands. They will
277   // be kept even if they are unused and --gc-sections is specified.
278   std::vector<InputSectionDescription *> KeptSections;
279 
280   // A map from memory region name to a memory region descriptor.
281   llvm::MapVector<llvm::StringRef, MemoryRegion *> MemoryRegions;
282 
283   // A list of symbols referenced by the script.
284   std::vector<llvm::StringRef> ReferencedSymbols;
285 };
286 
287 extern LinkerScript *Script;
288 
289 } // end namespace elf
290 } // end namespace lld
291 
292 #endif // LLD_ELF_LINKER_SCRIPT_H
293