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