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.
30 static_assert(sizeof(void *) != 8 || sizeof(ConcatInputSection) == 120,
31               "Try to minimize ConcatInputSection's size, we create many "
32               "instances of it");
33 
34 std::vector<ConcatInputSection *> macho::inputSections;
35 
36 uint64_t InputSection::getFileSize() const {
37   return isZeroFill(getFlags()) ? 0 : getSize();
38 }
39 
40 uint64_t InputSection::getVA(uint64_t off) const {
41   return parent->addr + getOffset(off);
42 }
43 
44 static uint64_t resolveSymbolVA(const Symbol *sym, uint8_t type) {
45   const RelocAttrs &relocAttrs = target->getRelocAttrs(type);
46   if (relocAttrs.hasAttr(RelocAttrBits::BRANCH))
47     return sym->resolveBranchVA();
48   if (relocAttrs.hasAttr(RelocAttrBits::GOT))
49     return sym->resolveGotVA();
50   if (relocAttrs.hasAttr(RelocAttrBits::TLV))
51     return sym->resolveTlvVA();
52   return sym->getVA();
53 }
54 
55 // ICF needs to hash any section that might potentially be duplicated so
56 // that it can match on content rather than identity.
57 bool ConcatInputSection::isHashableForICF() const {
58   switch (sectionType(getFlags())) {
59   case S_REGULAR:
60     return true;
61   case S_CSTRING_LITERALS:
62   case S_4BYTE_LITERALS:
63   case S_8BYTE_LITERALS:
64   case S_16BYTE_LITERALS:
65   case S_LITERAL_POINTERS:
66     llvm_unreachable("found unexpected literal type in ConcatInputSection");
67   case S_ZEROFILL:
68   case S_GB_ZEROFILL:
69   case S_NON_LAZY_SYMBOL_POINTERS:
70   case S_LAZY_SYMBOL_POINTERS:
71   case S_SYMBOL_STUBS:
72   case S_MOD_INIT_FUNC_POINTERS:
73   case S_MOD_TERM_FUNC_POINTERS:
74   case S_COALESCED:
75   case S_INTERPOSING:
76   case S_DTRACE_DOF:
77   case S_LAZY_DYLIB_SYMBOL_POINTERS:
78   case S_THREAD_LOCAL_REGULAR:
79   case S_THREAD_LOCAL_ZEROFILL:
80   case S_THREAD_LOCAL_VARIABLES:
81   case S_THREAD_LOCAL_VARIABLE_POINTERS:
82   case S_THREAD_LOCAL_INIT_FUNCTION_POINTERS:
83     return false;
84   default:
85     llvm_unreachable("Section type");
86   }
87 }
88 
89 void ConcatInputSection::hashForICF() {
90   assert(data.data()); // zeroFill section data has nullptr with non-zero size
91   assert(icfEqClass[0] == 0); // don't overwrite a unique ID!
92   // Turn-on the top bit to guarantee that valid hashes have no collisions
93   // with the small-integer unique IDs for ICF-ineligible sections
94   icfEqClass[0] = xxHash64(data) | (1ull << 63);
95 }
96 
97 void ConcatInputSection::foldIdentical(ConcatInputSection *copy) {
98   align = std::max(align, copy->align);
99   copy->live = false;
100   copy->wasCoalesced = true;
101   copy->replacement = this;
102 
103   // Merge the sorted vectors of symbols together.
104   auto it = symbols.begin();
105   for (auto copyIt = copy->symbols.begin(); copyIt != copy->symbols.end();) {
106     if (it == symbols.end()) {
107       symbols.push_back(*copyIt++);
108       it = symbols.end();
109     } else if ((*it)->value > (*copyIt)->value) {
110       std::swap(*it++, *copyIt);
111     } else {
112       ++it;
113     }
114   }
115   copy->symbols.clear();
116 
117   // Remove duplicate compact unwind info for symbols at the same address.
118   if (symbols.empty())
119     return;
120   it = symbols.begin();
121   uint64_t v = (*it)->value;
122   for (++it; it != symbols.end(); ++it) {
123     Defined *d = *it;
124     if (d->value == v)
125       d->unwindEntry = nullptr;
126     else
127       v = d->value;
128   }
129 }
130 
131 void ConcatInputSection::writeTo(uint8_t *buf) {
132   assert(!shouldOmitFromOutput());
133 
134   if (getFileSize() == 0)
135     return;
136 
137   memcpy(buf, data.data(), data.size());
138 
139   for (size_t i = 0; i < relocs.size(); i++) {
140     const Reloc &r = relocs[i];
141     uint8_t *loc = buf + r.offset;
142     uint64_t referentVA = 0;
143     if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
144       const Symbol *fromSym = r.referent.get<Symbol *>();
145       const Reloc &minuend = relocs[++i];
146       uint64_t minuendVA;
147       if (const Symbol *toSym = minuend.referent.dyn_cast<Symbol *>())
148         minuendVA = toSym->getVA() + minuend.addend;
149       else {
150         auto *referentIsec = minuend.referent.get<InputSection *>();
151         assert(!::shouldOmitFromOutput(referentIsec));
152         minuendVA = referentIsec->getVA(minuend.addend);
153       }
154       referentVA = minuendVA - fromSym->getVA();
155     } else if (auto *referentSym = r.referent.dyn_cast<Symbol *>()) {
156       if (target->hasAttr(r.type, RelocAttrBits::LOAD) &&
157           !referentSym->isInGot())
158         target->relaxGotLoad(loc, r.type);
159       referentVA = resolveSymbolVA(referentSym, r.type) + r.addend;
160 
161       if (isThreadLocalVariables(getFlags())) {
162         // References from thread-local variable sections are treated as offsets
163         // relative to the start of the thread-local data memory area, which
164         // is initialized via copying all the TLV data sections (which are all
165         // contiguous).
166         if (isa<Defined>(referentSym))
167           referentVA -= firstTLVDataSection->addr;
168       }
169     } else if (auto *referentIsec = r.referent.dyn_cast<InputSection *>()) {
170       assert(!::shouldOmitFromOutput(referentIsec));
171       referentVA = referentIsec->getVA(r.addend);
172     }
173     target->relocateOne(loc, r, referentVA, getVA() + r.offset);
174   }
175 }
176 
177 void CStringInputSection::splitIntoPieces() {
178   size_t off = 0;
179   StringRef s = toStringRef(data);
180   while (!s.empty()) {
181     size_t end = s.find(0);
182     if (end == StringRef::npos)
183       fatal(toString(this) + ": string is not null terminated");
184     size_t size = end + 1;
185     uint32_t hash = config->dedupLiterals ? xxHash64(s.substr(0, size)) : 0;
186     pieces.emplace_back(off, hash);
187     s = s.substr(size);
188     off += size;
189   }
190 }
191 
192 StringPiece &CStringInputSection::getStringPiece(uint64_t off) {
193   if (off >= data.size())
194     fatal(toString(this) + ": offset is outside the section");
195 
196   auto it =
197       partition_point(pieces, [=](StringPiece p) { return p.inSecOff <= off; });
198   return it[-1];
199 }
200 
201 const StringPiece &CStringInputSection::getStringPiece(uint64_t off) const {
202   return const_cast<CStringInputSection *>(this)->getStringPiece(off);
203 }
204 
205 uint64_t CStringInputSection::getOffset(uint64_t off) const {
206   const StringPiece &piece = getStringPiece(off);
207   uint64_t addend = off - piece.inSecOff;
208   return piece.outSecOff + addend;
209 }
210 
211 WordLiteralInputSection::WordLiteralInputSection(StringRef segname,
212                                                  StringRef name,
213                                                  InputFile *file,
214                                                  ArrayRef<uint8_t> data,
215                                                  uint32_t align, uint32_t flags)
216     : InputSection(WordLiteralKind, segname, name, file, data, align, flags) {
217   switch (sectionType(flags)) {
218   case S_4BYTE_LITERALS:
219     power2LiteralSize = 2;
220     break;
221   case S_8BYTE_LITERALS:
222     power2LiteralSize = 3;
223     break;
224   case S_16BYTE_LITERALS:
225     power2LiteralSize = 4;
226     break;
227   default:
228     llvm_unreachable("invalid literal section type");
229   }
230 
231   live.resize(data.size() >> power2LiteralSize, !config->deadStrip);
232 }
233 
234 uint64_t WordLiteralInputSection::getOffset(uint64_t off) const {
235   auto *osec = cast<WordLiteralSection>(parent);
236   const uintptr_t buf = reinterpret_cast<uintptr_t>(data.data());
237   switch (sectionType(getFlags())) {
238   case S_4BYTE_LITERALS:
239     return osec->getLiteral4Offset(buf + (off & ~3LLU)) | (off & 3);
240   case S_8BYTE_LITERALS:
241     return osec->getLiteral8Offset(buf + (off & ~7LLU)) | (off & 7);
242   case S_16BYTE_LITERALS:
243     return osec->getLiteral16Offset(buf + (off & ~15LLU)) | (off & 15);
244   default:
245     llvm_unreachable("invalid literal section type");
246   }
247 }
248 
249 bool macho::isCodeSection(const InputSection *isec) {
250   uint32_t type = sectionType(isec->getFlags());
251   if (type != S_REGULAR && type != S_COALESCED)
252     return false;
253 
254   uint32_t attr = isec->getFlags() & SECTION_ATTRIBUTES_USR;
255   if (attr == S_ATTR_PURE_INSTRUCTIONS)
256     return true;
257 
258   if (isec->getSegName() == segment_names::text)
259     return StringSwitch<bool>(isec->getName())
260         .Cases(section_names::textCoalNt, section_names::staticInit, true)
261         .Default(false);
262 
263   return false;
264 }
265 
266 bool macho::isCfStringSection(const InputSection *isec) {
267   return isec->getName() == section_names::cfString &&
268          isec->getSegName() == segment_names::data;
269 }
270 
271 std::string lld::toString(const InputSection *isec) {
272   return (toString(isec->getFile()) + ":(" + isec->getName() + ")").str();
273 }
274