[JITLink] Process null symbols

[jobnoorman]

Summary

Some relocations (e.g., R_RISCV_ALIGN) don't have a target symbol and
use a null symbol as a placeholder. These symbols were not processed
before making it impossible to create edges for them.

This patch tries to detect these null symbols and create absolute
symbols for them. Note that technically, these null symbols are UND in
the ELF file, not ABS, so it might make more consistent to create a new
symbol type for this (local undefined or so). However, since these
symbols are only used as placeholders (i.e., their values are never
used), I don't think it's worth the effort of doing this.

Also note that in the binaries that I have inspected, this null symbol
always has index 0. Could it make sense to add that to the test to avoid
accidentally adding unnecessary symbols? The reason I didn't do this
yet, is that I couldn't find any references in the specs that actually
guarantee this.

[lhames]

See naming comment, but otherwise LGTM. Thanks very much @jobnoorman!

llvm/lib/ExecutionEngine/JITLink/ELFLinkGraphBuilder.h

552–553

Let's name these __jitlink_ELF_SYM_UND_<st_value> -- it'll make them easy to spot when debugging, and allow us to keep the invariant that all absolute symbols are named (which means that the change to JITLink.cpp would no longer be needed).

Side note: We should probably change Symbol::hasName so that empty symbols still count as valid names, but that's outside the scope of this patch.

[jobnoorman]

llvm/lib/ExecutionEngine/JITLink/ELFLinkGraphBuilder.h

552–553

Let's name these __jitlink_ELF_SYM_UND_<st_value> -- it'll make them easy to spot when debugging

Should we maybe go for __jitlink_ELF_SYM_UND_<SymIndex> to make sure the name is always unique? st_value will always be 0 in this case.

and allow us to keep the invariant that all absolute symbols are named (which means that the change to JITLink.cpp would no longer be needed).

I might be missing something here but wouldn't this change still be needed? It handles printing edges with targets that are !isDefined() rather than !hasName().

[lhames]

llvm/lib/ExecutionEngine/JITLink/ELFLinkGraphBuilder.h

552–553

Should we maybe go for __jitlink_ELF_SYM_UND_<SymIndex> to make sure the name is always unique? st_value will always be 0 in this case.

Yep -- that sounds good to me.

I might be missing something here but wouldn't this change still be needed? It handles printing edges with targets that are !isDefined() rather than !hasName().

If all absolute symbols are named then they're handled under the if (TargetSym.hasName()) condition, and all symbols are either named or have an associated Block (the else case).

[jobnoorman]

llvm/lib/ExecutionEngine/JITLink/ELFLinkGraphBuilder.h

552–553

Should we maybe go for __jitlink_ELF_SYM_UND_<SymIndex> to make sure the name is always unique? st_value will always be 0 in this case.

Yep -- that sounds good to me.

Just noticed there's a practical issue here: Symbol stores its name as a StringRef so I don't think there's a safe way to construct a name on the fly.

So I see two options:

• Call the symbol __jitlink_ELF_SYM_NULL (or something like that) and assert there is only one;
• Update Symbol to own its name in a std::string.

I might be missing something here but wouldn't this change still be needed? It handles printing edges with targets that are !isDefined() rather than !hasName().

If all absolute symbols are named then they're handled under the if (TargetSym.hasName()) condition, and all symbols are either named or have an associated Block (the else case).

Ah, of course! Will remove these changes in the next update.

[jobnoorman]

• Rename added symbols to __jitlink_ELF_SYM_UND_<SymIndex>
• Remove now unnecessary checks in JITLink.cpp

[jobnoorman]

llvm/lib/ExecutionEngine/JITLink/ELFLinkGraphBuilder.h

552–553

Just noticed there's a practical issue here: Symbol stores its name as a StringRef so I don't think there's a safe way to construct a name on the fly.

I figured out we can use LinkGraph::allocateContent for this so all issues should be resolved now. I'll wait for a final LGTM for these last changes before landing this.

[lhames]

LGTM! Thanks @jobnoorman!

llvm/lib/ExecutionEngine/JITLink/ELFLinkGraphBuilder.h

if (Sym.isDefined() &&
                 Twine(static_cast<int>(Sym.getBinding())) +
                 " for external symbol " + *Name,
             inconvertibleErrorCode());
 
       // If L is Linkage::Weak that means this is a weakly referenced symbol.
       auto &GSym = G->addExternalSymbol(*Name, Sym.st_size,
                                         Sym.getBinding() == ELF::STB_WEAK);
       setGraphSymbol(SymIndex, GSym);
+    } else if (Sym.isUndefined() && Sym.st_value == 0 && Sym.st_size == 0 &&
+               Sym.getType() == ELF::STT_NOTYPE &&
+               Sym.getBinding() == ELF::STB_LOCAL && Name->empty()) {
+      // Some relocations (e.g., R_RISCV_ALIGN) don't have a target symbol and
+      // use this kind of null symbol as a placeholder.
+      LLVM_DEBUG({
+        dbgs() << "      " << SymIndex << ": Creating null graph symbol\n";
+      });
+
+      auto &GSym = G->addAbsoluteSymbol(*Name, orc::ExecutorAddr(0), 0,
+                                        Linkage::Strong, Scope::Local, false);
+      setGraphSymbol(SymIndex, GSym);
     } else {
       LLVM_DEBUG({
         dbgs() << "      " << SymIndex
                << ": Not creating graph symbol for ELF symbol \"" << *Name
                << "\" with unrecognized type\n";
       });
     }
   }

llvm/lib/ExecutionEngine/JITLink/JITLink.cpp

void printEdge(raw_ostream &OS, const Block &B, const Edge &E,
                StringRef EdgeKindName) {
   OS << "edge@" << B.getAddress() + E.getOffset() << ": " << B.getAddress()
      << " + " << formatv("{0:x}", E.getOffset()) << " -- " << EdgeKindName
      << " -> ";
 
   auto &TargetSym = E.getTarget();
   if (TargetSym.hasName())
     OS << TargetSym.getName();
-  else {
+  else if (TargetSym.isDefined()) {
     auto &TargetBlock = TargetSym.getBlock();
     auto &TargetSec = TargetBlock.getSection();
     orc::ExecutorAddr SecAddress(~uint64_t(0));
     for (auto *B : TargetSec.blocks())
       if (B->getAddress() < SecAddress)
         SecAddress = B->getAddress();
 
     orc::ExecutorAddrDiff SecDelta = TargetSym.getAddress() - SecAddress;
     OS << TargetSym.getAddress() << " (section " << TargetSec.getName();
     if (SecDelta)
       OS << " + " << formatv("{0:x}", SecDelta);
     OS << " / block " << TargetBlock.getAddress();
     if (TargetSym.getOffset())
       OS << " + " << formatv("{0:x}", TargetSym.getOffset());
     OS << ")";
-  }
+  } else
+    OS << formatv("{0:x}", TargetSym.getAddress());
 
   if (E.getAddend() != 0)
     OS << " + " << E.getAddend();
 }
 
 Section::~Section() {
   for (auto *Sym : Symbols)
     Sym->~Symbol();