1 //=--------- COFFLinkGraphBuilder.cpp - COFF LinkGraph builder ----------===//
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 // Generic COFF LinkGraph buliding code.
10 //
11 //===----------------------------------------------------------------------===//
12 #include "COFFLinkGraphBuilder.h"
13 
14 #define DEBUG_TYPE "jitlink"
15 
16 static const char *CommonSectionName = "__common";
17 
18 namespace llvm {
19 namespace jitlink {
20 
21 static Triple createTripleWithCOFFFormat(Triple T) {
22   T.setObjectFormat(Triple::COFF);
23   return T;
24 }
25 
26 COFFLinkGraphBuilder::COFFLinkGraphBuilder(
27     const object::COFFObjectFile &Obj, Triple TT,
28     LinkGraph::GetEdgeKindNameFunction GetEdgeKindName)
29     : Obj(Obj),
30       G(std::make_unique<LinkGraph>(Obj.getFileName().str(),
31                                     createTripleWithCOFFFormat(TT),
32                                     getPointerSize(Obj), getEndianness(Obj),
33                                     std::move(GetEdgeKindName))) {
34   LLVM_DEBUG({
35     dbgs() << "Created COFFLinkGraphBuilder for \"" << Obj.getFileName()
36            << "\"\n";
37   });
38 }
39 
40 COFFLinkGraphBuilder::~COFFLinkGraphBuilder() = default;
41 
42 unsigned
43 COFFLinkGraphBuilder::getPointerSize(const object::COFFObjectFile &Obj) {
44   return Obj.getBytesInAddress();
45 }
46 
47 support::endianness
48 COFFLinkGraphBuilder::getEndianness(const object::COFFObjectFile &Obj) {
49   return Obj.isLittleEndian() ? support::little : support::big;
50 }
51 
52 uint64_t COFFLinkGraphBuilder::getSectionSize(const object::COFFObjectFile &Obj,
53                                               const object::coff_section *Sec) {
54   // Consider the difference between executable form and object form.
55   // More information is inside COFFObjectFile::getSectionSize
56   if (Obj.getDOSHeader())
57     return std::min(Sec->VirtualSize, Sec->SizeOfRawData);
58   return Sec->SizeOfRawData;
59 }
60 
61 uint64_t
62 COFFLinkGraphBuilder::getSectionAddress(const object::COFFObjectFile &Obj,
63                                         const object::coff_section *Section) {
64   return Section->VirtualAddress + Obj.getImageBase();
65 }
66 
67 bool COFFLinkGraphBuilder::isComdatSection(
68     const object::coff_section *Section) {
69   return Section->Characteristics & COFF::IMAGE_SCN_LNK_COMDAT;
70 }
71 
72 Section &COFFLinkGraphBuilder::getCommonSection() {
73   if (!CommonSection)
74     CommonSection =
75         &G->createSection(CommonSectionName, MemProt::Read | MemProt::Write);
76   return *CommonSection;
77 }
78 
79 Expected<std::unique_ptr<LinkGraph>> COFFLinkGraphBuilder::buildGraph() {
80   if (!Obj.isRelocatableObject())
81     return make_error<JITLinkError>("Object is not a relocatable COFF file");
82 
83   if (auto Err = graphifySections())
84     return std::move(Err);
85 
86   if (auto Err = graphifySymbols())
87     return std::move(Err);
88 
89   if (auto Err = addRelocations())
90     return std::move(Err);
91 
92   return std::move(G);
93 }
94 
95 StringRef
96 COFFLinkGraphBuilder::getCOFFSectionName(COFFSectionIndex SectionIndex,
97                                          const object::coff_section *Sec,
98                                          object::COFFSymbolRef Sym) {
99   switch (SectionIndex) {
100   case COFF::IMAGE_SYM_UNDEFINED: {
101     if (Sym.getValue())
102       return "(common)";
103     else
104       return "(external)";
105   }
106   case COFF::IMAGE_SYM_ABSOLUTE:
107     return "(absolute)";
108   case COFF::IMAGE_SYM_DEBUG: {
109     // Used with .file symbol
110     return "(debug)";
111   }
112   default: {
113     // Non reserved regular section numbers
114     if (Expected<StringRef> SecNameOrErr = Obj.getSectionName(Sec))
115       return *SecNameOrErr;
116   }
117   }
118   return "";
119 }
120 
121 Error COFFLinkGraphBuilder::graphifySections() {
122   LLVM_DEBUG(dbgs() << "  Creating graph sections...\n");
123 
124   GraphBlocks.resize(Obj.getNumberOfSections() + 1);
125   // For each section...
126   for (COFFSectionIndex SecIndex = 1;
127        SecIndex <= static_cast<COFFSectionIndex>(Obj.getNumberOfSections());
128        SecIndex++) {
129     Expected<const object::coff_section *> Sec = Obj.getSection(SecIndex);
130     if (!Sec)
131       return Sec.takeError();
132 
133     StringRef SectionName;
134     if (Expected<StringRef> SecNameOrErr = Obj.getSectionName(*Sec))
135       SectionName = *SecNameOrErr;
136 
137     // FIXME: Skip debug info sections
138 
139     LLVM_DEBUG({
140       dbgs() << "    "
141              << "Creating section for \"" << SectionName << "\"\n";
142     });
143 
144     // FIXME: Revisit crash when dropping IMAGE_SCN_MEM_DISCARDABLE sections
145 
146     // Get the section's memory protection flags.
147     MemProt Prot = MemProt::None;
148     if ((*Sec)->Characteristics & COFF::IMAGE_SCN_MEM_EXECUTE)
149       Prot |= MemProt::Exec;
150     if ((*Sec)->Characteristics & COFF::IMAGE_SCN_MEM_READ)
151       Prot |= MemProt::Read;
152     if ((*Sec)->Characteristics & COFF::IMAGE_SCN_MEM_WRITE)
153       Prot |= MemProt::Write;
154 
155     // Look for existing sections first.
156     auto *GraphSec = G->findSectionByName(SectionName);
157     if (!GraphSec)
158       GraphSec = &G->createSection(SectionName, Prot);
159     if (GraphSec->getMemProt() != Prot)
160       return make_error<JITLinkError>("MemProt should match");
161 
162     Block *B = nullptr;
163     if ((*Sec)->Characteristics & COFF::IMAGE_SCN_CNT_UNINITIALIZED_DATA)
164       B = &G->createZeroFillBlock(
165           *GraphSec, getSectionSize(Obj, *Sec),
166           orc::ExecutorAddr(getSectionAddress(Obj, *Sec)),
167           (*Sec)->getAlignment(), 0);
168     else {
169       ArrayRef<uint8_t> Data;
170       if (auto Err = Obj.getSectionContents(*Sec, Data))
171         return Err;
172 
173       B = &G->createContentBlock(
174           *GraphSec,
175           ArrayRef<char>(reinterpret_cast<const char *>(Data.data()),
176                          Data.size()),
177           orc::ExecutorAddr(getSectionAddress(Obj, *Sec)),
178           (*Sec)->getAlignment(), 0);
179     }
180 
181     setGraphBlock(SecIndex, B);
182   }
183 
184   return Error::success();
185 }
186 
187 Error COFFLinkGraphBuilder::graphifySymbols() {
188   LLVM_DEBUG(dbgs() << "  Creating graph symbols...\n");
189 
190   SymbolSets.resize(Obj.getNumberOfSections() + 1);
191   PendingComdatExports.resize(Obj.getNumberOfSections() + 1);
192   GraphSymbols.resize(Obj.getNumberOfSymbols());
193 
194   for (COFFSymbolIndex SymIndex = 0;
195        SymIndex < static_cast<COFFSymbolIndex>(Obj.getNumberOfSymbols());
196        SymIndex++) {
197     Expected<object::COFFSymbolRef> Sym = Obj.getSymbol(SymIndex);
198     if (!Sym)
199       return Sym.takeError();
200 
201     StringRef SymbolName;
202     if (Expected<StringRef> SymNameOrErr = Obj.getSymbolName(*Sym))
203       SymbolName = *SymNameOrErr;
204 
205     COFFSectionIndex SectionIndex = Sym->getSectionNumber();
206     const object::coff_section *Sec = nullptr;
207 
208     if (!COFF::isReservedSectionNumber(SectionIndex)) {
209       auto SecOrErr = Obj.getSection(SectionIndex);
210       if (!SecOrErr)
211         return make_error<JITLinkError>(
212             "Invalid COFF section number:" + formatv("{0:d}: ", SectionIndex) +
213             " (" + toString(SecOrErr.takeError()) + ")");
214       Sec = *SecOrErr;
215     }
216 
217     // Create jitlink symbol
218     jitlink::Symbol *GSym = nullptr;
219     if (Sym->isFileRecord())
220       LLVM_DEBUG({
221         dbgs() << "    " << SymIndex << ": Skipping FileRecord symbol \""
222                << SymbolName << "\" in "
223                << getCOFFSectionName(SectionIndex, Sec, *Sym)
224                << " (index: " << SectionIndex << ") \n";
225       });
226     else if (Sym->isUndefined()) {
227       LLVM_DEBUG({
228         dbgs() << "    " << SymIndex
229                << ": Creating external graph symbol for COFF symbol \""
230                << SymbolName << "\" in "
231                << getCOFFSectionName(SectionIndex, Sec, *Sym)
232                << " (index: " << SectionIndex << ") \n";
233       });
234       if (!ExternalSymbols.count(SymbolName))
235         ExternalSymbols[SymbolName] =
236             &G->addExternalSymbol(SymbolName, Sym->getValue(), Linkage::Strong);
237       GSym = ExternalSymbols[SymbolName];
238     } else if (Sym->isWeakExternal()) {
239       COFFSymbolIndex TagIndex =
240           Sym->getAux<object::coff_aux_weak_external>()->TagIndex;
241       assert(Sym->getAux<object::coff_aux_weak_external>()->Characteristics !=
242                  COFF::IMAGE_WEAK_EXTERN_SEARCH_NOLIBRARY &&
243              "IMAGE_WEAK_EXTERN_SEARCH_NOLIBRARY is not supported.");
244       assert(Sym->getAux<object::coff_aux_weak_external>()->Characteristics !=
245                  COFF::IMAGE_WEAK_EXTERN_SEARCH_LIBRARY &&
246              "IMAGE_WEAK_EXTERN_SEARCH_LIBRARY is not supported.");
247       WeakAliasRequests.push_back({SymIndex, TagIndex, SymbolName});
248     } else {
249       Expected<jitlink::Symbol *> NewGSym =
250           createDefinedSymbol(SymIndex, SymbolName, *Sym, Sec);
251       if (!NewGSym)
252         return NewGSym.takeError();
253       GSym = *NewGSym;
254       if (GSym) {
255         LLVM_DEBUG({
256           dbgs() << "    " << SymIndex
257                  << ": Creating defined graph symbol for COFF symbol \""
258                  << SymbolName << "\" in "
259                  << getCOFFSectionName(SectionIndex, Sec, *Sym)
260                  << " (index: " << SectionIndex << ") \n";
261           dbgs() << "      " << *GSym << "\n";
262         });
263       }
264     }
265 
266     // Register the symbol
267     if (GSym)
268       setGraphSymbol(SectionIndex, SymIndex, *GSym);
269     SymIndex += Sym->getNumberOfAuxSymbols();
270   }
271 
272   if (auto Err = flushWeakAliasRequests())
273     return Err;
274 
275   if (auto Err = calculateImplicitSizeOfSymbols())
276     return Err;
277 
278   return Error::success();
279 }
280 
281 Error COFFLinkGraphBuilder::flushWeakAliasRequests() {
282   // Export the weak external symbols and alias it
283   for (auto &WeakAlias : WeakAliasRequests) {
284     if (auto *Target = getGraphSymbol(WeakAlias.Target)) {
285       Expected<object::COFFSymbolRef> AliasSymbol =
286           Obj.getSymbol(WeakAlias.Alias);
287       if (!AliasSymbol)
288         return AliasSymbol.takeError();
289 
290       // FIXME: Support this when there's a way to handle this.
291       if (!Target->isDefined())
292         return make_error<JITLinkError>("Weak external symbol with external "
293                                         "symbol as alternative not supported.");
294 
295       jitlink::Symbol *NewSymbol = &G->addDefinedSymbol(
296           Target->getBlock(), Target->getOffset(), WeakAlias.SymbolName,
297           Target->getSize(), Linkage::Weak, Scope::Default,
298           Target->isCallable(), false);
299       setGraphSymbol(AliasSymbol->getSectionNumber(), WeakAlias.Alias,
300                      *NewSymbol);
301       LLVM_DEBUG({
302         dbgs() << "    " << WeakAlias.Alias
303                << ": Creating weak external symbol for COFF symbol \""
304                << WeakAlias.SymbolName << "\" in section "
305                << AliasSymbol->getSectionNumber() << "\n";
306         dbgs() << "      " << *NewSymbol << "\n";
307       });
308     } else
309       return make_error<JITLinkError>("Weak symbol alias requested but actual "
310                                       "symbol not found for symbol " +
311                                       formatv("{0:d}", WeakAlias.Alias));
312   }
313   return Error::success();
314 }
315 
316 // In COFF, most of the defined symbols don't contain the size information.
317 // Hence, we calculate the "implicit" size of symbol by taking the delta of
318 // offsets of consecutive symbols within a block. We maintain a balanced tree
319 // set of symbols sorted by offset per each block in order to achieve
320 // logarithmic time complexity of sorted symbol insertion. Symbol is inserted to
321 // the set once it's processed in graphifySymbols. In this function, we iterate
322 // each collected symbol in sorted order and calculate the implicit size.
323 Error COFFLinkGraphBuilder::calculateImplicitSizeOfSymbols() {
324   for (COFFSectionIndex SecIndex = 1;
325        SecIndex <= static_cast<COFFSectionIndex>(Obj.getNumberOfSections());
326        SecIndex++) {
327     auto &SymbolSet = SymbolSets[SecIndex];
328     if (SymbolSet.empty())
329       continue;
330     jitlink::Block *B = getGraphBlock(SecIndex);
331     orc::ExecutorAddrDiff LastOffset = B->getSize();
332     orc::ExecutorAddrDiff LastDifferentOffset = B->getSize();
333     orc::ExecutorAddrDiff LastSize = 0;
334     for (auto It = SymbolSet.rbegin(); It != SymbolSet.rend(); It++) {
335       orc::ExecutorAddrDiff Offset = It->first;
336       jitlink::Symbol *Symbol = It->second;
337       orc::ExecutorAddrDiff CandSize;
338       // Last offset can be same when aliasing happened
339       if (Symbol->getOffset() == LastOffset)
340         CandSize = LastSize;
341       else
342         CandSize = LastOffset - Offset;
343 
344       LLVM_DEBUG({
345         if (Offset + Symbol->getSize() > LastDifferentOffset)
346           dbgs() << "  Overlapping symbol range generated for the following "
347                     "symbol:"
348                  << "\n"
349                  << "    " << *Symbol << "\n";
350       });
351       (void)LastDifferentOffset;
352       if (LastOffset != Offset)
353         LastDifferentOffset = Offset;
354       LastSize = CandSize;
355       LastOffset = Offset;
356       if (Symbol->getSize()) {
357         // Non empty symbol can happen in COMDAT symbol.
358         // We don't consider the possibility of overlapping symbol range that
359         // could be introduced by disparity between inferred symbol size and
360         // defined symbol size because symbol size information is currently only
361         // used by jitlink-check where we have control to not make overlapping
362         // ranges.
363         continue;
364       }
365 
366       LLVM_DEBUG({
367         if (!CandSize)
368           dbgs() << "  Empty implicit symbol size generated for the following "
369                     "symbol:"
370                  << "\n"
371                  << "    " << *Symbol << "\n";
372       });
373 
374       Symbol->setSize(CandSize);
375     }
376   }
377   return Error::success();
378 }
379 
380 Expected<Symbol *> COFFLinkGraphBuilder::createDefinedSymbol(
381     COFFSymbolIndex SymIndex, StringRef SymbolName,
382     object::COFFSymbolRef Symbol, const object::coff_section *Section) {
383   if (Symbol.isCommon()) {
384     // FIXME: correct alignment
385     return &G->addCommonSymbol(SymbolName, Scope::Default, getCommonSection(),
386                                orc::ExecutorAddr(), Symbol.getValue(),
387                                Symbol.getValue(), false);
388   }
389   if (Symbol.isAbsolute())
390     return &G->addAbsoluteSymbol(SymbolName,
391                                  orc::ExecutorAddr(Symbol.getValue()), 0,
392                                  Linkage::Strong, Scope::Local, false);
393 
394   if (llvm::COFF::isReservedSectionNumber(Symbol.getSectionNumber()))
395     return make_error<JITLinkError>(
396         "Reserved section number used in regular symbol " +
397         formatv("{0:d}", SymIndex));
398 
399   Block *B = getGraphBlock(Symbol.getSectionNumber());
400   if (!B) {
401     LLVM_DEBUG({
402       dbgs() << "    " << SymIndex
403              << ": Skipping graph symbol since section was not created for "
404                 "COFF symbol \""
405              << SymbolName << "\" in section " << Symbol.getSectionNumber()
406              << "\n";
407     });
408     return nullptr;
409   }
410 
411   if (Symbol.isExternal()) {
412     // This is not a comdat sequence, export the symbol as it is
413     if (!isComdatSection(Section)) {
414 
415       return &G->addDefinedSymbol(
416           *B, Symbol.getValue(), SymbolName, 0, Linkage::Strong, Scope::Default,
417           Symbol.getComplexType() == COFF::IMAGE_SYM_DTYPE_FUNCTION, false);
418     } else {
419       if (!PendingComdatExports[Symbol.getSectionNumber()])
420         return make_error<JITLinkError>("No pending COMDAT export for symbol " +
421                                         formatv("{0:d}", SymIndex));
422 
423       return exportCOMDATSymbol(SymIndex, SymbolName, Symbol);
424     }
425   }
426 
427   if (Symbol.getStorageClass() == COFF::IMAGE_SYM_CLASS_STATIC ||
428       Symbol.getStorageClass() == COFF::IMAGE_SYM_CLASS_LABEL) {
429     const object::coff_aux_section_definition *Definition =
430         Symbol.getSectionDefinition();
431     if (!Definition || !isComdatSection(Section)) {
432       // Handle typical static symbol
433       return &G->addDefinedSymbol(
434           *B, Symbol.getValue(), SymbolName, 0, Linkage::Strong, Scope::Local,
435           Symbol.getComplexType() == COFF::IMAGE_SYM_DTYPE_FUNCTION, false);
436     }
437     if (Definition->Selection == COFF::IMAGE_COMDAT_SELECT_ASSOCIATIVE) {
438       auto Target = Definition->getNumber(Symbol.isBigObj());
439       auto GSym = &G->addDefinedSymbol(
440           *B, Symbol.getValue(), SymbolName, 0, Linkage::Strong, Scope::Local,
441           Symbol.getComplexType() == COFF::IMAGE_SYM_DTYPE_FUNCTION, false);
442       getGraphBlock(Target)->addEdge(Edge::KeepAlive, 0, *GSym, 0);
443       return GSym;
444     }
445     if (PendingComdatExports[Symbol.getSectionNumber()])
446       return make_error<JITLinkError>(
447           "COMDAT export request already exists before symbol " +
448           formatv("{0:d}", SymIndex));
449     return createCOMDATExportRequest(SymIndex, Symbol, Definition);
450   }
451   return make_error<JITLinkError>("Unsupported storage class " +
452                                   formatv("{0:d}", Symbol.getStorageClass()) +
453                                   " in symbol " + formatv("{0:d}", SymIndex));
454 }
455 
456 // COMDAT handling:
457 // When IMAGE_SCN_LNK_COMDAT flag is set in the flags of a section,
458 // the section is called a COMDAT section. It contains two symbols
459 // in a sequence that specifes the behavior. First symbol is the section
460 // symbol which contains the size and name of the section. It also contains
461 // selection type that specifies how duplicate of the symbol is handled.
462 // Second symbol is COMDAT symbol which usually defines the external name and
463 // data type.
464 //
465 // Since two symbols always come in a specific order, we initiate pending COMDAT
466 // export request when we encounter the first symbol and actually exports it
467 // when we process the second symbol.
468 //
469 // Process the first symbol of COMDAT sequence.
470 Expected<Symbol *> COFFLinkGraphBuilder::createCOMDATExportRequest(
471     COFFSymbolIndex SymIndex, object::COFFSymbolRef Symbol,
472     const object::coff_aux_section_definition *Definition) {
473   Block *B = getGraphBlock(Symbol.getSectionNumber());
474   Linkage L = Linkage::Strong;
475   switch (Definition->Selection) {
476   case COFF::IMAGE_COMDAT_SELECT_NODUPLICATES: {
477     L = Linkage::Strong;
478     break;
479   }
480   case COFF::IMAGE_COMDAT_SELECT_ANY: {
481     L = Linkage::Weak;
482     break;
483   }
484   case COFF::IMAGE_COMDAT_SELECT_EXACT_MATCH:
485   case COFF::IMAGE_COMDAT_SELECT_SAME_SIZE: {
486     // FIXME: Implement size/content validation when LinkGraph is able to
487     // handle this.
488     L = Linkage::Weak;
489     break;
490   }
491   case COFF::IMAGE_COMDAT_SELECT_LARGEST: {
492     // FIXME: Support IMAGE_COMDAT_SELECT_LARGEST when LinkGraph is able to
493     // handle this.
494     return make_error<JITLinkError>(
495         "IMAGE_COMDAT_SELECT_LARGEST is not supported.");
496   }
497   case COFF::IMAGE_COMDAT_SELECT_NEWEST: {
498     // Even link.exe doesn't support this selection properly.
499     return make_error<JITLinkError>(
500         "IMAGE_COMDAT_SELECT_NEWEST is not supported.");
501   }
502   default: {
503     return make_error<JITLinkError>("Invalid comdat selection type: " +
504                                     formatv("{0:d}", Definition->Selection));
505   }
506   }
507   PendingComdatExports[Symbol.getSectionNumber()] = {SymIndex, L};
508   return &G->addAnonymousSymbol(*B, Symbol.getValue(), Definition->Length,
509                                 false, false);
510 }
511 
512 // Process the second symbol of COMDAT sequence.
513 Expected<Symbol *>
514 COFFLinkGraphBuilder::exportCOMDATSymbol(COFFSymbolIndex SymIndex,
515                                          StringRef SymbolName,
516                                          object::COFFSymbolRef Symbol) {
517   auto &PendingComdatExport = PendingComdatExports[Symbol.getSectionNumber()];
518   COFFSymbolIndex TargetIndex = PendingComdatExport->SymbolIndex;
519   Linkage L = PendingComdatExport->Linkage;
520   jitlink::Symbol *Target = getGraphSymbol(TargetIndex);
521   assert(Target && "COMDAT leaader is invalid.");
522   assert((llvm::count_if(G->defined_symbols(),
523                          [&](const jitlink::Symbol *Sym) {
524                            return Sym->getName() == SymbolName;
525                          }) == 0) &&
526          "Duplicate defined symbol");
527   Target->setName(SymbolName);
528   Target->setLinkage(L);
529   Target->setCallable(Symbol.getComplexType() ==
530                       COFF::IMAGE_SYM_DTYPE_FUNCTION);
531   Target->setScope(Scope::Default);
532   LLVM_DEBUG({
533     dbgs() << "    " << SymIndex
534            << ": Exporting COMDAT graph symbol for COFF symbol \"" << SymbolName
535            << "\" in section " << Symbol.getSectionNumber() << "\n";
536     dbgs() << "      " << *Target << "\n";
537   });
538   PendingComdatExport = None;
539   return Target;
540 }
541 
542 } // namespace jitlink
543 } // namespace llvm
544