1 //===- InputSection.cpp ---------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "InputSection.h"
10 #include "ConcatOutputSection.h"
11 #include "Config.h"
12 #include "InputFiles.h"
13 #include "OutputSegment.h"
14 #include "Symbols.h"
15 #include "SyntheticSections.h"
16 #include "Target.h"
17 #include "UnwindInfoSection.h"
18 #include "Writer.h"
19 #include "lld/Common/Memory.h"
20 #include "llvm/Support/Endian.h"
21 #include "llvm/Support/xxhash.h"
22 
23 using namespace llvm;
24 using namespace llvm::MachO;
25 using namespace llvm::support;
26 using namespace lld;
27 using namespace lld::macho;
28 
29 // Verify ConcatInputSection's size on 64-bit builds. The size of std::vector
30 // can differ based on STL debug levels (e.g. iterator debugging on MSVC's STL),
31 // so account for that.
32 static_assert(sizeof(void *) != 8 ||
33                   sizeof(ConcatInputSection) == sizeof(std::vector<Reloc>) + 96,
34               "Try to minimize ConcatInputSection's size, we create many "
35               "instances of it");
36 
37 std::vector<ConcatInputSection *> macho::inputSections;
38 
39 uint64_t InputSection::getFileSize() const {
40   return isZeroFill(getFlags()) ? 0 : getSize();
41 }
42 
43 uint64_t InputSection::getVA(uint64_t off) const {
44   return parent->addr + getOffset(off);
45 }
46 
47 static uint64_t resolveSymbolVA(const Symbol *sym, uint8_t type) {
48   const RelocAttrs &relocAttrs = target->getRelocAttrs(type);
49   if (relocAttrs.hasAttr(RelocAttrBits::BRANCH))
50     return sym->resolveBranchVA();
51   if (relocAttrs.hasAttr(RelocAttrBits::GOT))
52     return sym->resolveGotVA();
53   if (relocAttrs.hasAttr(RelocAttrBits::TLV))
54     return sym->resolveTlvVA();
55   return sym->getVA();
56 }
57 
58 std::string InputSection::getLocation(uint64_t off) const {
59   // First, try to find a symbol that's near the offset. Use it as a reference
60   // point.
61   for (size_t i = 0; i < symbols.size(); ++i)
62     if (symbols[i]->value <= off &&
63         (i + 1 == symbols.size() || symbols[i + 1]->value > off))
64       return (toString(getFile()) + ":(symbol " + symbols.front()->getName() +
65               "+0x" + Twine::utohexstr(off - symbols[i]->value) + ")")
66           .str();
67 
68   // If that fails, use the section itself as a reference point.
69   for (const Subsection &subsec : section.subsections) {
70     if (subsec.isec == this) {
71       off += subsec.offset;
72       break;
73     }
74   }
75   return (toString(getFile()) + ":(" + getName() + "+0x" +
76           Twine::utohexstr(off) + ")")
77       .str();
78 }
79 
80 // ICF needs to hash any section that might potentially be duplicated so
81 // that it can match on content rather than identity.
82 bool ConcatInputSection::isHashableForICF() const {
83   switch (sectionType(getFlags())) {
84   case S_REGULAR:
85     return true;
86   case S_CSTRING_LITERALS:
87   case S_4BYTE_LITERALS:
88   case S_8BYTE_LITERALS:
89   case S_16BYTE_LITERALS:
90   case S_LITERAL_POINTERS:
91     llvm_unreachable("found unexpected literal type in ConcatInputSection");
92   case S_ZEROFILL:
93   case S_GB_ZEROFILL:
94   case S_NON_LAZY_SYMBOL_POINTERS:
95   case S_LAZY_SYMBOL_POINTERS:
96   case S_SYMBOL_STUBS:
97   case S_MOD_INIT_FUNC_POINTERS:
98   case S_MOD_TERM_FUNC_POINTERS:
99   case S_COALESCED:
100   case S_INTERPOSING:
101   case S_DTRACE_DOF:
102   case S_LAZY_DYLIB_SYMBOL_POINTERS:
103   case S_THREAD_LOCAL_REGULAR:
104   case S_THREAD_LOCAL_ZEROFILL:
105   case S_THREAD_LOCAL_VARIABLES:
106   case S_THREAD_LOCAL_VARIABLE_POINTERS:
107   case S_THREAD_LOCAL_INIT_FUNCTION_POINTERS:
108     return false;
109   default:
110     llvm_unreachable("Section type");
111   }
112 }
113 
114 void ConcatInputSection::hashForICF() {
115   assert(data.data()); // zeroFill section data has nullptr with non-zero size
116   assert(icfEqClass[0] == 0); // don't overwrite a unique ID!
117   // Turn-on the top bit to guarantee that valid hashes have no collisions
118   // with the small-integer unique IDs for ICF-ineligible sections
119   icfEqClass[0] = xxHash64(data) | (1ull << 63);
120 }
121 
122 void ConcatInputSection::foldIdentical(ConcatInputSection *copy) {
123   align = std::max(align, copy->align);
124   copy->live = false;
125   copy->wasCoalesced = true;
126   copy->replacement = this;
127 
128   // Merge the sorted vectors of symbols together.
129   auto it = symbols.begin();
130   for (auto copyIt = copy->symbols.begin(); copyIt != copy->symbols.end();) {
131     if (it == symbols.end()) {
132       symbols.push_back(*copyIt++);
133       it = symbols.end();
134     } else if ((*it)->value > (*copyIt)->value) {
135       std::swap(*it++, *copyIt);
136     } else {
137       ++it;
138     }
139   }
140   copy->symbols.clear();
141 
142   // Remove duplicate compact unwind info for symbols at the same address.
143   if (symbols.empty())
144     return;
145   it = symbols.begin();
146   uint64_t v = (*it)->value;
147   for (++it; it != symbols.end(); ++it) {
148     Defined *d = *it;
149     if (d->value == v)
150       d->unwindEntry = nullptr;
151     else
152       v = d->value;
153   }
154 }
155 
156 void ConcatInputSection::writeTo(uint8_t *buf) {
157   assert(!shouldOmitFromOutput());
158 
159   if (getFileSize() == 0)
160     return;
161 
162   memcpy(buf, data.data(), data.size());
163 
164   for (size_t i = 0; i < relocs.size(); i++) {
165     const Reloc &r = relocs[i];
166     uint8_t *loc = buf + r.offset;
167     uint64_t referentVA = 0;
168     if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
169       const Symbol *fromSym = r.referent.get<Symbol *>();
170       const Reloc &minuend = relocs[++i];
171       uint64_t minuendVA;
172       if (const Symbol *toSym = minuend.referent.dyn_cast<Symbol *>())
173         minuendVA = toSym->getVA() + minuend.addend;
174       else {
175         auto *referentIsec = minuend.referent.get<InputSection *>();
176         assert(!::shouldOmitFromOutput(referentIsec));
177         minuendVA = referentIsec->getVA(minuend.addend);
178       }
179       referentVA = minuendVA - fromSym->getVA();
180     } else if (auto *referentSym = r.referent.dyn_cast<Symbol *>()) {
181       if (target->hasAttr(r.type, RelocAttrBits::LOAD) &&
182           !referentSym->isInGot())
183         target->relaxGotLoad(loc, r.type);
184       referentVA = resolveSymbolVA(referentSym, r.type) + r.addend;
185 
186       if (isThreadLocalVariables(getFlags())) {
187         // References from thread-local variable sections are treated as offsets
188         // relative to the start of the thread-local data memory area, which
189         // is initialized via copying all the TLV data sections (which are all
190         // contiguous).
191         if (isa<Defined>(referentSym))
192           referentVA -= firstTLVDataSection->addr;
193       }
194     } else if (auto *referentIsec = r.referent.dyn_cast<InputSection *>()) {
195       assert(!::shouldOmitFromOutput(referentIsec));
196       referentVA = referentIsec->getVA(r.addend);
197     }
198     target->relocateOne(loc, r, referentVA, getVA() + r.offset);
199   }
200 }
201 
202 ConcatInputSection *macho::makeSyntheticInputSection(StringRef segName,
203                                                      StringRef sectName,
204                                                      uint32_t flags,
205                                                      ArrayRef<uint8_t> data,
206                                                      uint32_t align) {
207   Section &section =
208       *make<Section>(/*file=*/nullptr, segName, sectName, flags, /*addr=*/0);
209   auto isec = make<ConcatInputSection>(section, data, align);
210   section.subsections.push_back({0, isec});
211   return isec;
212 }
213 
214 void CStringInputSection::splitIntoPieces() {
215   size_t off = 0;
216   StringRef s = toStringRef(data);
217   while (!s.empty()) {
218     size_t end = s.find(0);
219     if (end == StringRef::npos)
220       fatal(getLocation(off) + ": string is not null terminated");
221     size_t size = end + 1;
222     uint32_t hash = config->dedupLiterals ? xxHash64(s.substr(0, size)) : 0;
223     pieces.emplace_back(off, hash);
224     s = s.substr(size);
225     off += size;
226   }
227 }
228 
229 StringPiece &CStringInputSection::getStringPiece(uint64_t off) {
230   if (off >= data.size())
231     fatal(toString(this) + ": offset is outside the section");
232 
233   auto it =
234       partition_point(pieces, [=](StringPiece p) { return p.inSecOff <= off; });
235   return it[-1];
236 }
237 
238 const StringPiece &CStringInputSection::getStringPiece(uint64_t off) const {
239   return const_cast<CStringInputSection *>(this)->getStringPiece(off);
240 }
241 
242 uint64_t CStringInputSection::getOffset(uint64_t off) const {
243   const StringPiece &piece = getStringPiece(off);
244   uint64_t addend = off - piece.inSecOff;
245   return piece.outSecOff + addend;
246 }
247 
248 WordLiteralInputSection::WordLiteralInputSection(const Section &section,
249                                                  ArrayRef<uint8_t> data,
250                                                  uint32_t align)
251     : InputSection(WordLiteralKind, section, data, align) {
252   switch (sectionType(getFlags())) {
253   case S_4BYTE_LITERALS:
254     power2LiteralSize = 2;
255     break;
256   case S_8BYTE_LITERALS:
257     power2LiteralSize = 3;
258     break;
259   case S_16BYTE_LITERALS:
260     power2LiteralSize = 4;
261     break;
262   default:
263     llvm_unreachable("invalid literal section type");
264   }
265 
266   live.resize(data.size() >> power2LiteralSize, !config->deadStrip);
267 }
268 
269 uint64_t WordLiteralInputSection::getOffset(uint64_t off) const {
270   auto *osec = cast<WordLiteralSection>(parent);
271   const uintptr_t buf = reinterpret_cast<uintptr_t>(data.data());
272   switch (sectionType(getFlags())) {
273   case S_4BYTE_LITERALS:
274     return osec->getLiteral4Offset(buf + (off & ~3LLU)) | (off & 3);
275   case S_8BYTE_LITERALS:
276     return osec->getLiteral8Offset(buf + (off & ~7LLU)) | (off & 7);
277   case S_16BYTE_LITERALS:
278     return osec->getLiteral16Offset(buf + (off & ~15LLU)) | (off & 15);
279   default:
280     llvm_unreachable("invalid literal section type");
281   }
282 }
283 
284 bool macho::isCodeSection(const InputSection *isec) {
285   uint32_t type = sectionType(isec->getFlags());
286   if (type != S_REGULAR && type != S_COALESCED)
287     return false;
288 
289   uint32_t attr = isec->getFlags() & SECTION_ATTRIBUTES_USR;
290   if (attr == S_ATTR_PURE_INSTRUCTIONS)
291     return true;
292 
293   if (isec->getSegName() == segment_names::text)
294     return StringSwitch<bool>(isec->getName())
295         .Cases(section_names::textCoalNt, section_names::staticInit, true)
296         .Default(false);
297 
298   return false;
299 }
300 
301 bool macho::isCfStringSection(const InputSection *isec) {
302   return isec->getName() == section_names::cfString &&
303          isec->getSegName() == segment_names::data;
304 }
305 
306 std::string lld::toString(const InputSection *isec) {
307   return (toString(isec->getFile()) + ":(" + isec->getName() + ")").str();
308 }
309