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