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 || sizeof(ConcatInputSection) ==
33                                          sizeof(std::vector<Reloc>) + 104,
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 const Defined *InputSection::getContainingSymbol(uint64_t off) const {
59   auto *nextSym = llvm::upper_bound(
60       symbols, off, [](uint64_t a, const Defined *b) { return a < b->value; });
61   if (nextSym == symbols.begin())
62     return nullptr;
63   return *std::prev(nextSym);
64 }
65 
66 std::string InputSection::getLocation(uint64_t off) const {
67   // First, try to find a symbol that's near the offset. Use it as a reference
68   // point.
69   if (auto *sym = getContainingSymbol(off))
70     return (toString(getFile()) + ":(symbol " + sym->getName() + "+0x" +
71             Twine::utohexstr(off - sym->value) + ")")
72         .str();
73 
74   // If that fails, use the section itself as a reference point.
75   for (const Subsection &subsec : section.subsections) {
76     if (subsec.isec == this) {
77       off += subsec.offset;
78       break;
79     }
80   }
81 
82   return (toString(getFile()) + ":(" + getName() + "+0x" +
83           Twine::utohexstr(off) + ")")
84       .str();
85 }
86 
87 std::string InputSection::getSourceLocation(uint64_t off) const {
88   auto *obj = dyn_cast_or_null<ObjFile>(getFile());
89   if (!obj)
90     return {};
91 
92   DWARFCache *dwarf = obj->getDwarf();
93   if (!dwarf)
94     return std::string();
95 
96   for (const Subsection &subsec : section.subsections) {
97     if (subsec.isec == this) {
98       off += subsec.offset;
99       break;
100     }
101   }
102 
103   auto createMsg = [&](StringRef path, unsigned line) {
104     std::string filename = sys::path::filename(path).str();
105     std::string lineStr = (":" + Twine(line)).str();
106     if (filename == path)
107       return filename + lineStr;
108     return (filename + lineStr + " (" + path + lineStr + ")").str();
109   };
110 
111   // First, look up a function for a given offset.
112   if (Optional<DILineInfo> li = dwarf->getDILineInfo(
113           section.addr + off, object::SectionedAddress::UndefSection))
114     return createMsg(li->FileName, li->Line);
115 
116   // If it failed, look up again as a variable.
117   if (const Defined *sym = getContainingSymbol(off)) {
118     // Symbols are generally prefixed with an underscore, which is not included
119     // in the debug information.
120     StringRef symName = sym->getName();
121     if (!symName.empty() && symName[0] == '_')
122       symName = symName.substr(1);
123 
124     if (Optional<std::pair<std::string, unsigned>> fileLine =
125             dwarf->getVariableLoc(symName))
126       return createMsg(fileLine->first, fileLine->second);
127   }
128 
129   // Try to get the source file's name from the DWARF information.
130   if (obj->compileUnit)
131     return obj->sourceFile();
132 
133   return {};
134 }
135 
136 void ConcatInputSection::foldIdentical(ConcatInputSection *copy) {
137   align = std::max(align, copy->align);
138   copy->live = false;
139   copy->wasCoalesced = true;
140   copy->replacement = this;
141   for (auto &copySym : copy->symbols)
142     copySym->wasIdenticalCodeFolded = true;
143 
144   // Merge the sorted vectors of symbols together.
145   auto it = symbols.begin();
146   for (auto copyIt = copy->symbols.begin(); copyIt != copy->symbols.end();) {
147     if (it == symbols.end()) {
148       symbols.push_back(*copyIt++);
149       it = symbols.end();
150     } else if ((*it)->value > (*copyIt)->value) {
151       std::swap(*it++, *copyIt);
152     } else {
153       ++it;
154     }
155   }
156   copy->symbols.clear();
157 
158   // Remove duplicate compact unwind info for symbols at the same address.
159   if (symbols.empty())
160     return;
161   it = symbols.begin();
162   uint64_t v = (*it)->value;
163   for (++it; it != symbols.end(); ++it) {
164     Defined *d = *it;
165     if (d->value == v)
166       d->unwindEntry = nullptr;
167     else
168       v = d->value;
169   }
170 }
171 
172 void ConcatInputSection::writeTo(uint8_t *buf) {
173   assert(!shouldOmitFromOutput());
174 
175   if (getFileSize() == 0)
176     return;
177 
178   memcpy(buf, data.data(), data.size());
179 
180   std::vector<uint64_t> relocTargets;
181   if (!optimizationHints.empty())
182     relocTargets.reserve(relocs.size());
183 
184   for (size_t i = 0; i < relocs.size(); i++) {
185     const Reloc &r = relocs[i];
186     uint8_t *loc = buf + r.offset;
187     uint64_t referentVA = 0;
188     if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
189       const Symbol *fromSym = r.referent.get<Symbol *>();
190       const Reloc &minuend = relocs[++i];
191       uint64_t minuendVA;
192       if (const Symbol *toSym = minuend.referent.dyn_cast<Symbol *>())
193         minuendVA = toSym->getVA() + minuend.addend;
194       else {
195         auto *referentIsec = minuend.referent.get<InputSection *>();
196         assert(!::shouldOmitFromOutput(referentIsec));
197         minuendVA = referentIsec->getVA(minuend.addend);
198       }
199       referentVA = minuendVA - fromSym->getVA();
200     } else if (auto *referentSym = r.referent.dyn_cast<Symbol *>()) {
201       if (target->hasAttr(r.type, RelocAttrBits::LOAD) &&
202           !referentSym->isInGot())
203         target->relaxGotLoad(loc, r.type);
204       referentVA = resolveSymbolVA(referentSym, r.type) + r.addend;
205 
206       if (isThreadLocalVariables(getFlags())) {
207         // References from thread-local variable sections are treated as offsets
208         // relative to the start of the thread-local data memory area, which
209         // is initialized via copying all the TLV data sections (which are all
210         // contiguous).
211         if (isa<Defined>(referentSym))
212           referentVA -= firstTLVDataSection->addr;
213       }
214     } else if (auto *referentIsec = r.referent.dyn_cast<InputSection *>()) {
215       assert(!::shouldOmitFromOutput(referentIsec));
216       referentVA = referentIsec->getVA(r.addend);
217     }
218     target->relocateOne(loc, r, referentVA, getVA() + r.offset);
219 
220     if (!optimizationHints.empty())
221       relocTargets.push_back(referentVA);
222   }
223 
224   if (!optimizationHints.empty())
225     target->applyOptimizationHints(buf, this, relocTargets);
226 }
227 
228 ConcatInputSection *macho::makeSyntheticInputSection(StringRef segName,
229                                                      StringRef sectName,
230                                                      uint32_t flags,
231                                                      ArrayRef<uint8_t> data,
232                                                      uint32_t align) {
233   Section &section =
234       *make<Section>(/*file=*/nullptr, segName, sectName, flags, /*addr=*/0);
235   auto isec = make<ConcatInputSection>(section, data, align);
236   section.subsections.push_back({0, isec});
237   return isec;
238 }
239 
240 void CStringInputSection::splitIntoPieces() {
241   size_t off = 0;
242   StringRef s = toStringRef(data);
243   while (!s.empty()) {
244     size_t end = s.find(0);
245     if (end == StringRef::npos)
246       fatal(getLocation(off) + ": string is not null terminated");
247     size_t size = end + 1;
248     uint32_t hash = config->dedupLiterals ? xxHash64(s.substr(0, size)) : 0;
249     pieces.emplace_back(off, hash);
250     s = s.substr(size);
251     off += size;
252   }
253 }
254 
255 StringPiece &CStringInputSection::getStringPiece(uint64_t off) {
256   if (off >= data.size())
257     fatal(toString(this) + ": offset is outside the section");
258 
259   auto it =
260       partition_point(pieces, [=](StringPiece p) { return p.inSecOff <= off; });
261   return it[-1];
262 }
263 
264 const StringPiece &CStringInputSection::getStringPiece(uint64_t off) const {
265   return const_cast<CStringInputSection *>(this)->getStringPiece(off);
266 }
267 
268 uint64_t CStringInputSection::getOffset(uint64_t off) const {
269   const StringPiece &piece = getStringPiece(off);
270   uint64_t addend = off - piece.inSecOff;
271   return piece.outSecOff + addend;
272 }
273 
274 WordLiteralInputSection::WordLiteralInputSection(const Section &section,
275                                                  ArrayRef<uint8_t> data,
276                                                  uint32_t align)
277     : InputSection(WordLiteralKind, section, data, align) {
278   switch (sectionType(getFlags())) {
279   case S_4BYTE_LITERALS:
280     power2LiteralSize = 2;
281     break;
282   case S_8BYTE_LITERALS:
283     power2LiteralSize = 3;
284     break;
285   case S_16BYTE_LITERALS:
286     power2LiteralSize = 4;
287     break;
288   default:
289     llvm_unreachable("invalid literal section type");
290   }
291 
292   live.resize(data.size() >> power2LiteralSize, !config->deadStrip);
293 }
294 
295 uint64_t WordLiteralInputSection::getOffset(uint64_t off) const {
296   auto *osec = cast<WordLiteralSection>(parent);
297   const uintptr_t buf = reinterpret_cast<uintptr_t>(data.data());
298   switch (sectionType(getFlags())) {
299   case S_4BYTE_LITERALS:
300     return osec->getLiteral4Offset(buf + (off & ~3LLU)) | (off & 3);
301   case S_8BYTE_LITERALS:
302     return osec->getLiteral8Offset(buf + (off & ~7LLU)) | (off & 7);
303   case S_16BYTE_LITERALS:
304     return osec->getLiteral16Offset(buf + (off & ~15LLU)) | (off & 15);
305   default:
306     llvm_unreachable("invalid literal section type");
307   }
308 }
309 
310 bool macho::isCodeSection(const InputSection *isec) {
311   uint32_t type = sectionType(isec->getFlags());
312   if (type != S_REGULAR && type != S_COALESCED)
313     return false;
314 
315   uint32_t attr = isec->getFlags() & SECTION_ATTRIBUTES_USR;
316   if (attr == S_ATTR_PURE_INSTRUCTIONS)
317     return true;
318 
319   if (isec->getSegName() == segment_names::text)
320     return StringSwitch<bool>(isec->getName())
321         .Cases(section_names::textCoalNt, section_names::staticInit, true)
322         .Default(false);
323 
324   return false;
325 }
326 
327 bool macho::isCfStringSection(const InputSection *isec) {
328   return isec->getName() == section_names::cfString &&
329          isec->getSegName() == segment_names::data;
330 }
331 
332 bool macho::isClassRefsSection(const InputSection *isec) {
333   return isec->getName() == section_names::objcClassRefs &&
334          isec->getSegName() == segment_names::data;
335 }
336 
337 bool macho::isEhFrameSection(const InputSection *isec) {
338   return isec->getName() == section_names::ehFrame &&
339          isec->getSegName() == segment_names::text;
340 }
341 
342 std::string lld::toString(const InputSection *isec) {
343   return (toString(isec->getFile()) + ":(" + isec->getName() + ")").str();
344 }
345