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/Core/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 ScriptParser;
33 class SymbolBody;
34 class InputSectionBase;
35 class InputSection;
36 class OutputSectionBase;
37 template <class ELFT> class OutputSectionFactory;
38 class InputSectionBase;
39 
40 // This represents an expression in the linker script.
41 // ScriptParser::readExpr reads an expression and returns an Expr.
42 // Later, we evaluate the expression by calling the function
43 // with the value of special context variable ".".
44 struct Expr {
45   std::function<uint64_t(uint64_t)> Val;
46   std::function<bool()> IsAbsolute;
47 
48   // If expression is section-relative the function below is used
49   // to get the output section pointer.
50   std::function<const OutputSectionBase *()> Section;
51 
52   uint64_t operator()(uint64_t Dot) const { return Val(Dot); }
53   operator bool() const { return (bool)Val; }
54 
55   Expr(std::function<uint64_t(uint64_t)> Val, std::function<bool()> IsAbsolute,
56        std::function<const OutputSectionBase *()> Section)
57       : Val(Val), IsAbsolute(IsAbsolute), Section(Section) {}
58   template <typename T>
59   Expr(T V) : Expr(V, [] { return true; }, [] { return nullptr; }) {}
60   Expr() : Expr(nullptr) {}
61 };
62 
63 // Parses a linker script. Calling this function updates
64 // Config and ScriptConfig.
65 void readLinkerScript(MemoryBufferRef MB);
66 
67 // Parses a version script.
68 void readVersionScript(MemoryBufferRef MB);
69 
70 void readDynamicList(MemoryBufferRef MB);
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   BytesDataKind // BYTE(expr), SHORT(expr), LONG(expr) or QUAD(expr)
80 };
81 
82 struct BaseCommand {
83   BaseCommand(int K) : Kind(K) {}
84 
85   virtual ~BaseCommand() = default;
86 
87   int Kind;
88 };
89 
90 // This represents ". = <expr>" or "<symbol> = <expr>".
91 struct SymbolAssignment : BaseCommand {
92   SymbolAssignment(StringRef Name, Expr E, std::string Loc)
93       : BaseCommand(AssignmentKind), Name(Name), Expression(E), Location(Loc) {}
94 
95   static bool classof(const BaseCommand *C);
96 
97   // The LHS of an expression. Name is either a symbol name or ".".
98   StringRef Name;
99   SymbolBody *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 struct OutputSectionCommand : BaseCommand {
119   OutputSectionCommand(StringRef Name)
120       : BaseCommand(OutputSectionKind), Name(Name) {}
121 
122   static bool classof(const BaseCommand *C);
123 
124   StringRef Name;
125   Expr AddrExpr;
126   Expr AlignExpr;
127   Expr LMAExpr;
128   Expr SubalignExpr;
129   std::vector<std::unique_ptr<BaseCommand>> Commands;
130   std::vector<StringRef> Phdrs;
131   uint32_t Filler = 0;
132   ConstraintKind Constraint = ConstraintKind::NoConstraint;
133   std::string Location;
134   std::string MemoryRegionName;
135 };
136 
137 // This struct represents one section match pattern in SECTIONS() command.
138 // It can optionally have negative match pattern for EXCLUDED_FILE command.
139 // Also it may be surrounded with SORT() command, so contains sorting rules.
140 struct SectionPattern {
141   SectionPattern(StringMatcher &&Pat1, StringMatcher &&Pat2)
142       : ExcludedFilePat(Pat1), SectionPat(Pat2) {}
143 
144   StringMatcher ExcludedFilePat;
145   StringMatcher SectionPat;
146   SortSectionPolicy SortOuter;
147   SortSectionPolicy SortInner;
148 };
149 
150 struct InputSectionDescription : BaseCommand {
151   InputSectionDescription(StringRef FilePattern)
152       : BaseCommand(InputSectionKind), FilePat(FilePattern) {}
153 
154   static bool classof(const BaseCommand *C);
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<InputSectionBase *> Sections;
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);
170 
171   Expr Expression;
172 };
173 
174 // Represents BYTE(), SHORT(), LONG(), or QUAD().
175 struct BytesDataCommand : BaseCommand {
176   BytesDataCommand(Expr E, unsigned Size)
177       : BaseCommand(BytesDataKind), Expression(E), Size(Size) {}
178 
179   static bool classof(const BaseCommand *C);
180 
181   Expr Expression;
182   unsigned Offset;
183   unsigned Size;
184 };
185 
186 struct PhdrsCommand {
187   StringRef Name;
188   unsigned Type;
189   bool HasFilehdr;
190   bool HasPhdrs;
191   unsigned Flags;
192   Expr LMAExpr;
193 };
194 
195 // This struct is used to represent the location and size of regions of
196 // target memory. Instances of the struct are created by parsing the
197 // MEMORY command.
198 struct MemoryRegion {
199   std::string Name;
200   uint64_t Origin;
201   uint64_t Length;
202   uint64_t Offset;
203   uint32_t Flags;
204   uint32_t NegFlags;
205 };
206 
207 class LinkerScriptBase {
208 protected:
209   ~LinkerScriptBase() = default;
210 
211 public:
212   virtual uint64_t getHeaderSize() = 0;
213   virtual uint64_t getSymbolValue(const Twine &Loc, StringRef S) = 0;
214   virtual bool isDefined(StringRef S) = 0;
215   virtual bool isAbsolute(StringRef S) = 0;
216   virtual const OutputSectionBase *getSymbolSection(StringRef S) = 0;
217   virtual const OutputSectionBase *getOutputSection(const Twine &Loc,
218                                                     StringRef S) = 0;
219   virtual uint64_t getOutputSectionSize(StringRef S) = 0;
220 };
221 
222 // ScriptConfiguration holds linker script parse results.
223 struct ScriptConfiguration {
224   // Used to assign addresses to sections.
225   std::vector<std::unique_ptr<BaseCommand>> Commands;
226 
227   // Used to assign sections to headers.
228   std::vector<PhdrsCommand> PhdrsCommands;
229 
230   bool HasSections = false;
231 
232   // List of section patterns specified with KEEP commands. They will
233   // be kept even if they are unused and --gc-sections is specified.
234   std::vector<InputSectionDescription *> KeptSections;
235 
236   // A map from memory region name to a memory region descriptor.
237   llvm::DenseMap<llvm::StringRef, MemoryRegion> MemoryRegions;
238 };
239 
240 extern ScriptConfiguration *ScriptConfig;
241 
242 // This is a runner of the linker script.
243 template <class ELFT> class LinkerScript final : public LinkerScriptBase {
244   typedef typename ELFT::uint uintX_t;
245 
246 public:
247   LinkerScript();
248   ~LinkerScript();
249 
250   void processCommands(OutputSectionFactory<ELFT> &Factory);
251   void addOrphanSections(OutputSectionFactory<ELFT> &Factory);
252   void removeEmptyCommands();
253   void adjustSectionsBeforeSorting();
254   void adjustSectionsAfterSorting();
255 
256   std::vector<PhdrEntry> createPhdrs();
257   bool ignoreInterpSection();
258 
259   uint32_t getFiller(StringRef Name);
260   void writeDataBytes(StringRef Name, uint8_t *Buf);
261   bool hasLMA(StringRef Name);
262   bool shouldKeep(InputSectionBase *S);
263   void assignOffsets(OutputSectionCommand *Cmd);
264   void placeOrphanSections();
265   void assignAddresses(std::vector<PhdrEntry> &Phdrs);
266   bool hasPhdrsCommands();
267   uint64_t getHeaderSize() override;
268   uint64_t getSymbolValue(const Twine &Loc, StringRef S) override;
269   bool isDefined(StringRef S) override;
270   bool isAbsolute(StringRef S) override;
271   const OutputSectionBase *getSymbolSection(StringRef S) override;
272   const OutputSectionBase *getOutputSection(const Twine &Loc,
273                                             StringRef S) override;
274   uint64_t getOutputSectionSize(StringRef S) override;
275 
276   std::vector<OutputSectionBase *> *OutputSections;
277 
278   int getSectionIndex(StringRef Name);
279 
280 private:
281   void assignSymbol(SymbolAssignment *Cmd, bool InSec = false);
282   void addSymbol(SymbolAssignment *Cmd);
283   void computeInputSections(InputSectionDescription *);
284   void setDot(Expr E, const Twine &Loc, bool InSec = false);
285 
286   void discard(ArrayRef<InputSectionBase *> V);
287 
288   std::vector<InputSectionBase *>
289   createInputSectionList(OutputSectionCommand &Cmd);
290 
291   // "ScriptConfig" is a bit too long, so define a short name for it.
292   ScriptConfiguration &Opt = *ScriptConfig;
293 
294   std::vector<size_t> getPhdrIndices(StringRef SectionName);
295   size_t getPhdrIndex(const Twine &Loc, StringRef PhdrName);
296 
297   MemoryRegion *findMemoryRegion(OutputSectionCommand *Cmd,
298                                  OutputSectionBase *Sec);
299 
300   uintX_t Dot;
301   std::function<uint64_t()> LMAOffset;
302   OutputSectionBase *CurOutSec = nullptr;
303   MemoryRegion *CurMemRegion = nullptr;
304   uintX_t ThreadBssOffset = 0;
305   void switchTo(OutputSectionBase *Sec);
306   void flush();
307   void output(InputSection *Sec);
308   void process(BaseCommand &Base);
309   llvm::DenseSet<OutputSectionBase *> AlreadyOutputOS;
310   llvm::DenseSet<InputSectionBase *> AlreadyOutputIS;
311 };
312 
313 // Variable template is a C++14 feature, so we can't template
314 // a global variable. Use a struct to workaround.
315 template <class ELFT> struct Script { static LinkerScript<ELFT> *X; };
316 template <class ELFT> LinkerScript<ELFT> *Script<ELFT>::X;
317 
318 extern LinkerScriptBase *ScriptBase;
319 
320 } // end namespace elf
321 } // end namespace lld
322 
323 #endif // LLD_ELF_LINKER_SCRIPT_H
324