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