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       auto *WeakExternal = Sym->getAux<object::coff_aux_weak_external>();
240       COFFSymbolIndex TagIndex = WeakExternal->TagIndex;
241       uint32_t Characteristics = WeakExternal->Characteristics;
242       WeakExternalRequests.push_back(
243           {SymIndex, TagIndex, Characteristics, SymbolName});
244     } else {
245       Expected<jitlink::Symbol *> NewGSym =
246           createDefinedSymbol(SymIndex, SymbolName, *Sym, Sec);
247       if (!NewGSym)
248         return NewGSym.takeError();
249       GSym = *NewGSym;
250       if (GSym) {
251         LLVM_DEBUG({
252           dbgs() << "    " << SymIndex
253                  << ": Creating defined graph symbol for COFF symbol \""
254                  << SymbolName << "\" in "
255                  << getCOFFSectionName(SectionIndex, Sec, *Sym)
256                  << " (index: " << SectionIndex << ") \n";
257           dbgs() << "      " << *GSym << "\n";
258         });
259       }
260     }
261 
262     // Register the symbol
263     if (GSym)
264       setGraphSymbol(SectionIndex, SymIndex, *GSym);
265     SymIndex += Sym->getNumberOfAuxSymbols();
266   }
267 
268   if (auto Err = flushWeakAliasRequests())
269     return Err;
270 
271   if (auto Err = calculateImplicitSizeOfSymbols())
272     return Err;
273 
274   return Error::success();
275 }
276 
277 Error COFFLinkGraphBuilder::flushWeakAliasRequests() {
278   // Export the weak external symbols and alias it
279   for (auto &WeakExternal : WeakExternalRequests) {
280     if (auto *Target = getGraphSymbol(WeakExternal.Target)) {
281       Expected<object::COFFSymbolRef> AliasSymbol =
282           Obj.getSymbol(WeakExternal.Alias);
283       if (!AliasSymbol)
284         return AliasSymbol.takeError();
285 
286       // FIXME: IMAGE_WEAK_EXTERN_SEARCH_NOLIBRARY and
287       // IMAGE_WEAK_EXTERN_SEARCH_LIBRARY are handled in the same way.
288       Scope S =
289           WeakExternal.Characteristics == COFF::IMAGE_WEAK_EXTERN_SEARCH_ALIAS
290               ? Scope::Default
291               : Scope::Local;
292 
293       // FIXME: Support this when there's a way to handle this.
294       if (!Target->isDefined())
295         return make_error<JITLinkError>("Weak external symbol with external "
296                                         "symbol as alternative not supported.");
297 
298       jitlink::Symbol *NewSymbol = &G->addDefinedSymbol(
299           Target->getBlock(), Target->getOffset(), WeakExternal.SymbolName,
300           Target->getSize(), Linkage::Weak, S, Target->isCallable(), false);
301       setGraphSymbol(AliasSymbol->getSectionNumber(), WeakExternal.Alias,
302                      *NewSymbol);
303       LLVM_DEBUG({
304         dbgs() << "    " << WeakExternal.Alias
305                << ": Creating weak external symbol for COFF symbol \""
306                << WeakExternal.SymbolName << "\" in section "
307                << AliasSymbol->getSectionNumber() << "\n";
308         dbgs() << "      " << *NewSymbol << "\n";
309       });
310     } else
311       return make_error<JITLinkError>("Weak symbol alias requested but actual "
312                                       "symbol not found for symbol " +
313                                       formatv("{0:d}", WeakExternal.Alias));
314   }
315   return Error::success();
316 }
317 
318 // In COFF, most of the defined symbols don't contain the size information.
319 // Hence, we calculate the "implicit" size of symbol by taking the delta of
320 // offsets of consecutive symbols within a block. We maintain a balanced tree
321 // set of symbols sorted by offset per each block in order to achieve
322 // logarithmic time complexity of sorted symbol insertion. Symbol is inserted to
323 // the set once it's processed in graphifySymbols. In this function, we iterate
324 // each collected symbol in sorted order and calculate the implicit size.
325 Error COFFLinkGraphBuilder::calculateImplicitSizeOfSymbols() {
326   for (COFFSectionIndex SecIndex = 1;
327        SecIndex <= static_cast<COFFSectionIndex>(Obj.getNumberOfSections());
328        SecIndex++) {
329     auto &SymbolSet = SymbolSets[SecIndex];
330     if (SymbolSet.empty())
331       continue;
332     jitlink::Block *B = getGraphBlock(SecIndex);
333     orc::ExecutorAddrDiff LastOffset = B->getSize();
334     orc::ExecutorAddrDiff LastDifferentOffset = B->getSize();
335     orc::ExecutorAddrDiff LastSize = 0;
336     for (auto It = SymbolSet.rbegin(); It != SymbolSet.rend(); It++) {
337       orc::ExecutorAddrDiff Offset = It->first;
338       jitlink::Symbol *Symbol = It->second;
339       orc::ExecutorAddrDiff CandSize;
340       // Last offset can be same when aliasing happened
341       if (Symbol->getOffset() == LastOffset)
342         CandSize = LastSize;
343       else
344         CandSize = LastOffset - Offset;
345 
346       LLVM_DEBUG({
347         if (Offset + Symbol->getSize() > LastDifferentOffset)
348           dbgs() << "  Overlapping symbol range generated for the following "
349                     "symbol:"
350                  << "\n"
351                  << "    " << *Symbol << "\n";
352       });
353       (void)LastDifferentOffset;
354       if (LastOffset != Offset)
355         LastDifferentOffset = Offset;
356       LastSize = CandSize;
357       LastOffset = Offset;
358       if (Symbol->getSize()) {
359         // Non empty symbol can happen in COMDAT symbol.
360         // We don't consider the possibility of overlapping symbol range that
361         // could be introduced by disparity between inferred symbol size and
362         // defined symbol size because symbol size information is currently only
363         // used by jitlink-check where we have control to not make overlapping
364         // ranges.
365         continue;
366       }
367 
368       LLVM_DEBUG({
369         if (!CandSize)
370           dbgs() << "  Empty implicit symbol size generated for the following "
371                     "symbol:"
372                  << "\n"
373                  << "    " << *Symbol << "\n";
374       });
375 
376       Symbol->setSize(CandSize);
377     }
378   }
379   return Error::success();
380 }
381 
382 Expected<Symbol *> COFFLinkGraphBuilder::createDefinedSymbol(
383     COFFSymbolIndex SymIndex, StringRef SymbolName,
384     object::COFFSymbolRef Symbol, const object::coff_section *Section) {
385   if (Symbol.isCommon()) {
386     // FIXME: correct alignment
387     return &G->addCommonSymbol(SymbolName, Scope::Default, getCommonSection(),
388                                orc::ExecutorAddr(), Symbol.getValue(),
389                                Symbol.getValue(), false);
390   }
391   if (Symbol.isAbsolute())
392     return &G->addAbsoluteSymbol(SymbolName,
393                                  orc::ExecutorAddr(Symbol.getValue()), 0,
394                                  Linkage::Strong, Scope::Local, false);
395 
396   if (llvm::COFF::isReservedSectionNumber(Symbol.getSectionNumber()))
397     return make_error<JITLinkError>(
398         "Reserved section number used in regular symbol " +
399         formatv("{0:d}", SymIndex));
400 
401   Block *B = getGraphBlock(Symbol.getSectionNumber());
402   if (!B) {
403     LLVM_DEBUG({
404       dbgs() << "    " << SymIndex
405              << ": Skipping graph symbol since section was not created for "
406                 "COFF symbol \""
407              << SymbolName << "\" in section " << Symbol.getSectionNumber()
408              << "\n";
409     });
410     return nullptr;
411   }
412 
413   if (Symbol.isExternal()) {
414     // This is not a comdat sequence, export the symbol as it is
415     if (!isComdatSection(Section)) {
416 
417       return &G->addDefinedSymbol(
418           *B, Symbol.getValue(), SymbolName, 0, Linkage::Strong, Scope::Default,
419           Symbol.getComplexType() == COFF::IMAGE_SYM_DTYPE_FUNCTION, false);
420     } else {
421       if (!PendingComdatExports[Symbol.getSectionNumber()])
422         return make_error<JITLinkError>("No pending COMDAT export for symbol " +
423                                         formatv("{0:d}", SymIndex));
424 
425       return exportCOMDATSymbol(SymIndex, SymbolName, Symbol);
426     }
427   }
428 
429   if (Symbol.getStorageClass() == COFF::IMAGE_SYM_CLASS_STATIC ||
430       Symbol.getStorageClass() == COFF::IMAGE_SYM_CLASS_LABEL) {
431     const object::coff_aux_section_definition *Definition =
432         Symbol.getSectionDefinition();
433     if (!Definition || !isComdatSection(Section)) {
434       // Handle typical static symbol
435       return &G->addDefinedSymbol(
436           *B, Symbol.getValue(), SymbolName, 0, Linkage::Strong, Scope::Local,
437           Symbol.getComplexType() == COFF::IMAGE_SYM_DTYPE_FUNCTION, false);
438     }
439     if (Definition->Selection == COFF::IMAGE_COMDAT_SELECT_ASSOCIATIVE) {
440       auto Target = Definition->getNumber(Symbol.isBigObj());
441       auto GSym = &G->addDefinedSymbol(
442           *B, Symbol.getValue(), SymbolName, 0, Linkage::Strong, Scope::Local,
443           Symbol.getComplexType() == COFF::IMAGE_SYM_DTYPE_FUNCTION, false);
444       getGraphBlock(Target)->addEdge(Edge::KeepAlive, 0, *GSym, 0);
445       return GSym;
446     }
447     if (PendingComdatExports[Symbol.getSectionNumber()])
448       return make_error<JITLinkError>(
449           "COMDAT export request already exists before symbol " +
450           formatv("{0:d}", SymIndex));
451     return createCOMDATExportRequest(SymIndex, Symbol, Definition);
452   }
453   return make_error<JITLinkError>("Unsupported storage class " +
454                                   formatv("{0:d}", Symbol.getStorageClass()) +
455                                   " in symbol " + formatv("{0:d}", SymIndex));
456 }
457 
458 // COMDAT handling:
459 // When IMAGE_SCN_LNK_COMDAT flag is set in the flags of a section,
460 // the section is called a COMDAT section. It contains two symbols
461 // in a sequence that specifes the behavior. First symbol is the section
462 // symbol which contains the size and name of the section. It also contains
463 // selection type that specifies how duplicate of the symbol is handled.
464 // Second symbol is COMDAT symbol which usually defines the external name and
465 // data type.
466 //
467 // Since two symbols always come in a specific order, we initiate pending COMDAT
468 // export request when we encounter the first symbol and actually exports it
469 // when we process the second symbol.
470 //
471 // Process the first symbol of COMDAT sequence.
472 Expected<Symbol *> COFFLinkGraphBuilder::createCOMDATExportRequest(
473     COFFSymbolIndex SymIndex, object::COFFSymbolRef Symbol,
474     const object::coff_aux_section_definition *Definition) {
475   Block *B = getGraphBlock(Symbol.getSectionNumber());
476   Linkage L = Linkage::Strong;
477   switch (Definition->Selection) {
478   case COFF::IMAGE_COMDAT_SELECT_NODUPLICATES: {
479     L = Linkage::Strong;
480     break;
481   }
482   case COFF::IMAGE_COMDAT_SELECT_ANY: {
483     L = Linkage::Weak;
484     break;
485   }
486   case COFF::IMAGE_COMDAT_SELECT_EXACT_MATCH:
487   case COFF::IMAGE_COMDAT_SELECT_SAME_SIZE: {
488     // FIXME: Implement size/content validation when LinkGraph is able to
489     // handle this.
490     L = Linkage::Weak;
491     break;
492   }
493   case COFF::IMAGE_COMDAT_SELECT_LARGEST: {
494     // FIXME: Support IMAGE_COMDAT_SELECT_LARGEST properly when LinkGraph is
495     // able to handle this.
496     LLVM_DEBUG({
497       dbgs() << "    " << SymIndex
498              << ": Partially supported IMAGE_COMDAT_SELECT_LARGEST was used"
499                 " in section "
500              << Symbol.getSectionNumber() << "\n";
501     });
502     L = Linkage::Weak;
503     break;
504   }
505   case COFF::IMAGE_COMDAT_SELECT_NEWEST: {
506     // Even link.exe doesn't support this selection properly.
507     return make_error<JITLinkError>(
508         "IMAGE_COMDAT_SELECT_NEWEST is not supported.");
509   }
510   default: {
511     return make_error<JITLinkError>("Invalid comdat selection type: " +
512                                     formatv("{0:d}", Definition->Selection));
513   }
514   }
515   PendingComdatExports[Symbol.getSectionNumber()] = {SymIndex, L};
516   return &G->addAnonymousSymbol(*B, Symbol.getValue(), Definition->Length,
517                                 false, false);
518 }
519 
520 // Process the second symbol of COMDAT sequence.
521 Expected<Symbol *>
522 COFFLinkGraphBuilder::exportCOMDATSymbol(COFFSymbolIndex SymIndex,
523                                          StringRef SymbolName,
524                                          object::COFFSymbolRef Symbol) {
525   auto &PendingComdatExport = PendingComdatExports[Symbol.getSectionNumber()];
526   COFFSymbolIndex TargetIndex = PendingComdatExport->SymbolIndex;
527   Linkage L = PendingComdatExport->Linkage;
528   jitlink::Symbol *Target = getGraphSymbol(TargetIndex);
529   assert(Target && "COMDAT leaader is invalid.");
530   assert((llvm::count_if(G->defined_symbols(),
531                          [&](const jitlink::Symbol *Sym) {
532                            return Sym->getName() == SymbolName;
533                          }) == 0) &&
534          "Duplicate defined symbol");
535   Target->setName(SymbolName);
536   Target->setLinkage(L);
537   Target->setCallable(Symbol.getComplexType() ==
538                       COFF::IMAGE_SYM_DTYPE_FUNCTION);
539   Target->setScope(Scope::Default);
540   LLVM_DEBUG({
541     dbgs() << "    " << SymIndex
542            << ": Exporting COMDAT graph symbol for COFF symbol \"" << SymbolName
543            << "\" in section " << Symbol.getSectionNumber() << "\n";
544     dbgs() << "      " << *Target << "\n";
545   });
546   PendingComdatExport = None;
547   return Target;
548 }
549 
550 } // namespace jitlink
551 } // namespace llvm
552