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>) + 88,
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   auto *nextSym = llvm::upper_bound(
62       symbols, off, [](uint64_t a, const Defined *b) { return a < b->value; });
63   if (nextSym != symbols.begin()) {
64     auto &sym = *std::prev(nextSym);
65     return (toString(getFile()) + ":(symbol " + sym->getName() + "+0x" +
66             Twine::utohexstr(off - sym->value) + ")")
67         .str();
68   }
69 
70   // If that fails, use the section itself as a reference point.
71   for (const Subsection &subsec : section.subsections) {
72     if (subsec.isec == this) {
73       off += subsec.offset;
74       break;
75     }
76   }
77   return (toString(getFile()) + ":(" + getName() + "+0x" +
78           Twine::utohexstr(off) + ")")
79       .str();
80 }
81 
82 void ConcatInputSection::foldIdentical(ConcatInputSection *copy) {
83   align = std::max(align, copy->align);
84   copy->live = false;
85   copy->wasCoalesced = true;
86   copy->replacement = this;
87   for (auto &copySym : copy->symbols)
88     copySym->wasIdenticalCodeFolded = true;
89 
90   // Merge the sorted vectors of symbols together.
91   auto it = symbols.begin();
92   for (auto copyIt = copy->symbols.begin(); copyIt != copy->symbols.end();) {
93     if (it == symbols.end()) {
94       symbols.push_back(*copyIt++);
95       it = symbols.end();
96     } else if ((*it)->value > (*copyIt)->value) {
97       std::swap(*it++, *copyIt);
98     } else {
99       ++it;
100     }
101   }
102   copy->symbols.clear();
103 
104   // Remove duplicate compact unwind info for symbols at the same address.
105   if (symbols.empty())
106     return;
107   it = symbols.begin();
108   uint64_t v = (*it)->value;
109   for (++it; it != symbols.end(); ++it) {
110     Defined *d = *it;
111     if (d->value == v)
112       d->unwindEntry = nullptr;
113     else
114       v = d->value;
115   }
116 }
117 
118 void ConcatInputSection::writeTo(uint8_t *buf) {
119   assert(!shouldOmitFromOutput());
120 
121   if (getFileSize() == 0)
122     return;
123 
124   memcpy(buf, data.data(), data.size());
125 
126   for (size_t i = 0; i < relocs.size(); i++) {
127     const Reloc &r = relocs[i];
128     uint8_t *loc = buf + r.offset;
129     uint64_t referentVA = 0;
130     if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
131       const Symbol *fromSym = r.referent.get<Symbol *>();
132       const Reloc &minuend = relocs[++i];
133       uint64_t minuendVA;
134       if (const Symbol *toSym = minuend.referent.dyn_cast<Symbol *>())
135         minuendVA = toSym->getVA() + minuend.addend;
136       else {
137         auto *referentIsec = minuend.referent.get<InputSection *>();
138         assert(!::shouldOmitFromOutput(referentIsec));
139         minuendVA = referentIsec->getVA(minuend.addend);
140       }
141       referentVA = minuendVA - fromSym->getVA();
142     } else if (auto *referentSym = r.referent.dyn_cast<Symbol *>()) {
143       if (target->hasAttr(r.type, RelocAttrBits::LOAD) &&
144           !referentSym->isInGot())
145         target->relaxGotLoad(loc, r.type);
146       referentVA = resolveSymbolVA(referentSym, r.type) + r.addend;
147 
148       if (isThreadLocalVariables(getFlags())) {
149         // References from thread-local variable sections are treated as offsets
150         // relative to the start of the thread-local data memory area, which
151         // is initialized via copying all the TLV data sections (which are all
152         // contiguous).
153         if (isa<Defined>(referentSym))
154           referentVA -= firstTLVDataSection->addr;
155       }
156     } else if (auto *referentIsec = r.referent.dyn_cast<InputSection *>()) {
157       assert(!::shouldOmitFromOutput(referentIsec));
158       referentVA = referentIsec->getVA(r.addend);
159     }
160     target->relocateOne(loc, r, referentVA, getVA() + r.offset);
161   }
162 }
163 
164 ConcatInputSection *macho::makeSyntheticInputSection(StringRef segName,
165                                                      StringRef sectName,
166                                                      uint32_t flags,
167                                                      ArrayRef<uint8_t> data,
168                                                      uint32_t align) {
169   Section &section =
170       *make<Section>(/*file=*/nullptr, segName, sectName, flags, /*addr=*/0);
171   auto isec = make<ConcatInputSection>(section, data, align);
172   section.subsections.push_back({0, isec});
173   return isec;
174 }
175 
176 void CStringInputSection::splitIntoPieces() {
177   size_t off = 0;
178   StringRef s = toStringRef(data);
179   while (!s.empty()) {
180     size_t end = s.find(0);
181     if (end == StringRef::npos)
182       fatal(getLocation(off) + ": string is not null terminated");
183     size_t size = end + 1;
184     uint32_t hash = config->dedupLiterals ? xxHash64(s.substr(0, size)) : 0;
185     pieces.emplace_back(off, hash);
186     s = s.substr(size);
187     off += size;
188   }
189 }
190 
191 StringPiece &CStringInputSection::getStringPiece(uint64_t off) {
192   if (off >= data.size())
193     fatal(toString(this) + ": offset is outside the section");
194 
195   auto it =
196       partition_point(pieces, [=](StringPiece p) { return p.inSecOff <= off; });
197   return it[-1];
198 }
199 
200 const StringPiece &CStringInputSection::getStringPiece(uint64_t off) const {
201   return const_cast<CStringInputSection *>(this)->getStringPiece(off);
202 }
203 
204 uint64_t CStringInputSection::getOffset(uint64_t off) const {
205   const StringPiece &piece = getStringPiece(off);
206   uint64_t addend = off - piece.inSecOff;
207   return piece.outSecOff + addend;
208 }
209 
210 WordLiteralInputSection::WordLiteralInputSection(const Section &section,
211                                                  ArrayRef<uint8_t> data,
212                                                  uint32_t align)
213     : InputSection(WordLiteralKind, section, data, align) {
214   switch (sectionType(getFlags())) {
215   case S_4BYTE_LITERALS:
216     power2LiteralSize = 2;
217     break;
218   case S_8BYTE_LITERALS:
219     power2LiteralSize = 3;
220     break;
221   case S_16BYTE_LITERALS:
222     power2LiteralSize = 4;
223     break;
224   default:
225     llvm_unreachable("invalid literal section type");
226   }
227 
228   live.resize(data.size() >> power2LiteralSize, !config->deadStrip);
229 }
230 
231 uint64_t WordLiteralInputSection::getOffset(uint64_t off) const {
232   auto *osec = cast<WordLiteralSection>(parent);
233   const uintptr_t buf = reinterpret_cast<uintptr_t>(data.data());
234   switch (sectionType(getFlags())) {
235   case S_4BYTE_LITERALS:
236     return osec->getLiteral4Offset(buf + (off & ~3LLU)) | (off & 3);
237   case S_8BYTE_LITERALS:
238     return osec->getLiteral8Offset(buf + (off & ~7LLU)) | (off & 7);
239   case S_16BYTE_LITERALS:
240     return osec->getLiteral16Offset(buf + (off & ~15LLU)) | (off & 15);
241   default:
242     llvm_unreachable("invalid literal section type");
243   }
244 }
245 
246 bool macho::isCodeSection(const InputSection *isec) {
247   uint32_t type = sectionType(isec->getFlags());
248   if (type != S_REGULAR && type != S_COALESCED)
249     return false;
250 
251   uint32_t attr = isec->getFlags() & SECTION_ATTRIBUTES_USR;
252   if (attr == S_ATTR_PURE_INSTRUCTIONS)
253     return true;
254 
255   if (isec->getSegName() == segment_names::text)
256     return StringSwitch<bool>(isec->getName())
257         .Cases(section_names::textCoalNt, section_names::staticInit, true)
258         .Default(false);
259 
260   return false;
261 }
262 
263 bool macho::isCfStringSection(const InputSection *isec) {
264   return isec->getName() == section_names::cfString &&
265          isec->getSegName() == segment_names::data;
266 }
267 
268 bool macho::isClassRefsSection(const InputSection *isec) {
269   return isec->getName() == section_names::objcClassRefs &&
270          isec->getSegName() == segment_names::data;
271 }
272 
273 bool macho::isEhFrameSection(const InputSection *isec) {
274   return isec->getName() == section_names::ehFrame &&
275          isec->getSegName() == segment_names::text;
276 }
277 
278 std::string lld::toString(const InputSection *isec) {
279   return (toString(isec->getFile()) + ":(" + isec->getName() + ")").str();
280 }
281