[JITLink] Fix splitBlock if there are symbols span across the boundary

[steven_wu]

Summary

Fix splitBlock so that it can handle the case when the block being
split has symbols span across the split boundary. This is an error
case in general but for EHFrame splitting on macho platforms, there is an
anonymous symbol that marks the entire block. Current implementation
will leave a symbol that is out of bound of the underlying block. Fix
the problem by dropping such symbols when the block is split.

[dexonsmith]

llvm/lib/ExecutionEngine/JITLink/JITLink.cpp

217–225

This doesn't seem safe in general, since anonymous symbols aren't necessarily safe to split just because they're anonymous.

I wonder if, rather than return Errors, it'd be better to trust the caller and split blocks anyway (as the code was), but truncate Symbol::size() as necessary to avoid it going past the end of the block it points at.

Two other ideas:

• Change the LinkGraph parser to set the symbol size to 0 for symbols that are generated just to allow edges to a block.
• Add a bit to Symbol that says "safe to split", which LinkGraph would set for symbols it generates just to allow edges to a block.

@lhames, WDYT?

[steven_wu]

llvm/lib/ExecutionEngine/JITLink/JITLink.cpp

217–225

So the symbol in question is the one created here:

MachOLinkGraphBuilder::addSectionStartSymAndBlock

I don't know how this one is being used but the one marked eh_frame will become redundant after eh_frame splitting. I guess we can shrink the size of section start sym to have size 0 then we can just always split the block and not worry about that. Then any symbols span across the split boundary will be Error.

[lhames]

I wonder if, rather than return Errors, it'd be better to trust the caller and split blocks anyway (as the code was), but truncate Symbol::size() as necessary to avoid it going past the end of the block it points at.

I like this as a short-term solution.

I think this issue exposes limitations in LinkGraph's current design. I'm not sure that we need/want LLVM-style users-lists for Symbols, but if we just added a ref-count to Symbols we could have a .isUnreferenced method that would be really helpful here: Clients could choose to remove unreferenced anonymous symbols (which should always be safe, since they can be recreated easily), and/or truncate named symbols, and then splitBlock could return an Error for any remaining symbols that extend past a split point.

[steven_wu]

Address review feedback after talking with Lang and Duncan offline.

[steven_wu]

Update the patch to trust user's action and update symbols to fit in the new block

[lhames]

LGTM. Thanks Steven!

llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h

public:
   ///    for re-assigning block ordinals to restore a compatible order if
   ///    needed.
   ///
   /// 3. The cache is not automatically updated if new symbols are introduced
   ///    between calls to splitBlock. Any newly introduced symbols may be
   ///    added to the cache manually (descending offset order must be
   ///    preserved), or the cache can be set to None and rebuilt by
   ///    splitBlock on the next call.
-  Block &splitBlock(Block &B, size_t SplitIndex,
+  Expected<Block &> splitBlock(Block &B, size_t SplitIndex,
                                SplitBlockCache *Cache = nullptr);
 
   /// Add an external symbol.
   /// Some formats (e.g. ELF) allow Symbols to have sizes. For Symbols whose
   /// size is not known, you should substitute '0'.
   /// For external symbols Linkage determines whether the symbol must be
   /// present during lookup: Externals with strong linkage must be found or
   /// an error will be emitted. Externals with weak linkage are permitted to
   /// be undefined, in which case they are assigned a value of 0.

llvm/lib/ExecutionEngine/JITLink/EHFrameSupport.cpp

while (true) {
 
     // If this was the last block then there's nothing to split
     if (BlockReader.empty()) {
       LLVM_DEBUG(dbgs() << "      Extracted " << B << "\n");
       return Error::success();
     }
 
     uint64_t BlockSize = BlockReader.getOffset() - RecordStartOffset;
-    auto &NewBlock = G.splitBlock(B, BlockSize);
-    (void)NewBlock;
-    LLVM_DEBUG(dbgs() << "      Extracted " << NewBlock << "\n");
+    auto NewBlock = G.splitBlock(B, BlockSize);
+    if (!NewBlock)
+      return NewBlock.takeError();
+    LLVM_DEBUG(dbgs() << "      Extracted " << *NewBlock << "\n");
   }
 }
 
 EHFrameEdgeFixer::EHFrameEdgeFixer(StringRef EHFrameSectionName,
                                    unsigned PointerSize, Edge::Kind Delta64,
                                    Edge::Kind Delta32, Edge::Kind NegDelta32)
     : EHFrameSectionName(EHFrameSectionName), PointerSize(PointerSize),
       Delta64(Delta64), Delta32(Delta32), NegDelta32(NegDelta32) {}

llvm/lib/ExecutionEngine/JITLink/JITLink.cpp

 
 Section::~Section() {
   for (auto *Sym : Symbols)
     Sym->~Symbol();
   for (auto *B : Blocks)
     B->~Block();
 }
 
-Block &LinkGraph::splitBlock(Block &B, size_t SplitIndex,
+Expected<Block &> LinkGraph::splitBlock(Block &B, size_t SplitIndex,
                                         SplitBlockCache *Cache) {
 
   assert(SplitIndex > 0 && "splitBlock can not be called with SplitIndex == 0");
 
   // If the split point covers all of B then just return B.
   if (SplitIndex == B.getSize())
     return B;
 
   assert(SplitIndex < B.getSize() && "SplitIndex out of range");
if (*Cache == None) {
           (*Cache)->push_back(Sym);
 
       llvm::sort(**Cache, [](const Symbol *LHS, const Symbol *RHS) {
         return LHS->getOffset() > RHS->getOffset();
       });
     }
     auto &BlockSymbols = **Cache;
 
+    SmallVector<Symbol *, 2> SymbolsToRemove;
     // Transfer all symbols with offset less than SplitIndex to NewBlock.
     while (!BlockSymbols.empty() &&
            BlockSymbols.back()->getOffset() < SplitIndex) {
+      auto *Sym = BlockSymbols.back();
+      if (Sym->getOffset() + Sym->getSize() > SplitIndex) {
+        // This is an anonymous symbol extends across the split boundary, remove
+        // it because this is likely a symbol to mark the block.
+        if(Sym->hasName())
+          return make_error<JITLinkError>(
+              "named symbol span across the split boundary");
+        SymbolsToRemove.push_back(Sym);
+      }
       BlockSymbols.back()->setBlock(NewBlock);
       BlockSymbols.pop_back();
     }
+    for (auto *Sym : SymbolsToRemove)
+      removeDefinedSymbol(*Sym);
 
     // Update offsets for all remaining symbols in B.
     for (auto *Sym : BlockSymbols)
       Sym->setOffset(Sym->getOffset() - SplitIndex);
   }
 
   return NewBlock;
 }

llvm/lib/ExecutionEngine/JITLink/MachOLinkGraphBuilder.cpp

if (B->getSize() % CURecordSize)
           formatv("{0:x}", B->getSize()) +
           " (not a multiple of CU record size of " +
           formatv("{0:x}", CURecordSize) + ")");
 
     unsigned NumBlocks = B->getSize() / CURecordSize;
     LinkGraph::SplitBlockCache C;
 
     for (unsigned I = 0; I != NumBlocks; ++I) {
-      auto &CURec = G.splitBlock(*B, CURecordSize, &C);
+      auto CURec = G.splitBlock(*B, CURecordSize, &C);
+      if (!CURec)
+        return CURec.takeError();
       bool AddedKeepAlive = false;
 
-      for (auto &E : CURec.edges()) {
+      for (auto &E : CURec->edges()) {
         if (E.getOffset() == 0) {
           LLVM_DEBUG({
             dbgs() << "    Updating compact unwind record at "
-                   << formatv("{0:x16}", CURec.getAddress()) << " to point to "
+                   << formatv("{0:x16}", CURec->getAddress()) << " to point to "
                    << (E.getTarget().hasName() ? E.getTarget().getName()
                                                : StringRef())
                    << " (at " << formatv("{0:x16}", E.getTarget().getAddress())
                    << ")\n";
           });
 
           if (E.getTarget().isExternal())
             return make_error<JITLinkError>(
                 "Error adding keep-alive edge for compact unwind record at " +
-                formatv("{0:x}", CURec.getAddress()) + ": target " +
+                formatv("{0:x}", CURec->getAddress()) + ": target " +
                 E.getTarget().getName() + " is an external symbol");
           auto &TgtBlock = E.getTarget().getBlock();
           auto &CURecSym =
-              G.addAnonymousSymbol(CURec, 0, CURecordSize, 0, false);
+              G.addAnonymousSymbol(*CURec, 0, CURecordSize, 0, false);
           TgtBlock.addEdge(Edge::KeepAlive, 0, CURecSym, 0);
           AddedKeepAlive = true;
         } else if (E.getOffset() != PersonalityEdgeOffset &&
                    E.getOffset() != LSDAEdgeOffset)
-          return make_error<JITLinkError>("Unexpected edge at offset " +
-                                          formatv("{0:x}", E.getOffset()) +
-                                          " in compact unwind record at " +
-                                          formatv("{0:x}", CURec.getAddress()));
+          return make_error<JITLinkError>(
+              "Unexpected edge at offset " + formatv("{0:x}", E.getOffset()) +
+              formatv("{0:x}", CURec->getAddress()));
       }
 
       if (!AddedKeepAlive)
         return make_error<JITLinkError>(
             "Error adding keep-alive edge for compact unwind record at " +
-            formatv("{0:x}", CURec.getAddress()) +
+            formatv("{0:x}", CURec->getAddress()) +
             ": no outgoing target edge at offset 0");
     }
   }
   return Error::success();
 }
 
 } // end namespace jitlink
 } // end namespace llvm

llvm/unittests/ExecutionEngine/JITLink/LinkGraphTests.cpp

 //===------ LinkGraphTests.cpp - Unit tests for core JITLink classes ------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ExecutionEngine/JITLink/JITLink.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Memory.h"
+#include "llvm/Testing/Support/Error.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 using namespace llvm::jitlink;
 
 static const char BlockContentBytes[] = {
     0x54, 0x68, 0x65, 0x72, 0x65, 0x20, 0x77, 0x61, 0x73, 0x20, 0x6d, 0x6f,
     0x76, 0x65, 0x6d, 0x65, 0x6e, 0x74, 0x20, 0x61, 0x74, 0x20, 0x74, 0x68,
TEST(LinkGraphTest, SplitBlock) {
 
   // Add edges from B1 to EB.
   B1.addEdge(Edge::FirstRelocation, 0, ES1, 0);
   B1.addEdge(Edge::FirstRelocation, 4, ES2, 0);
   B1.addEdge(Edge::FirstRelocation, 8, ES3, 0);
   B1.addEdge(Edge::FirstRelocation, 12, ES4, 0);
 
   // Split B1.
-  auto &B2 = G.splitBlock(B1, 8);
+  auto B2 = G.splitBlock(B1, 8);
+  EXPECT_THAT_EXPECTED(B2, Succeeded());
 
   // Check that the block addresses and content matches what we would expect.
   EXPECT_EQ(B1.getAddress(), 0x1008U);
   EXPECT_EQ(B1.getContent(), BlockContent.slice(8));
 
-  EXPECT_EQ(B2.getAddress(), 0x1000U);
-  EXPECT_EQ(B2.getContent(), BlockContent.slice(0, 8));
+  EXPECT_EQ(B2->getAddress(), 0x1000U);
+  EXPECT_EQ(B2->getContent(), BlockContent.slice(0, 8));
 
   // Check that symbols in B1 were transferred as expected:
   // We expect S1 and S2 to have been transferred to B2, and S3 and S4 to have
   // remained attached to B1. Symbols S3 and S4 should have had their offsets
   // slid to account for the change in address of B2.
-  EXPECT_EQ(&S1.getBlock(), &B2);
+  EXPECT_EQ(&S1.getBlock(), &B2.get());
   EXPECT_EQ(S1.getOffset(), 0U);
 
-  EXPECT_EQ(&S2.getBlock(), &B2);
+  EXPECT_EQ(&S2.getBlock(), &B2.get());
   EXPECT_EQ(S2.getOffset(), 4U);
 
   EXPECT_EQ(&S3.getBlock(), &B1);
   EXPECT_EQ(S3.getOffset(), 0U);
 
   EXPECT_EQ(&S4.getBlock(), &B1);
   EXPECT_EQ(S4.getOffset(), 4U);
 
   // Check that edges in B1 have been transferred as expected:
   // Both blocks should now have two edges each at offsets 0 and 4.
   EXPECT_EQ(llvm::size(B1.edges()), 2);
   if (size(B1.edges()) == 2) {
     auto *E1 = &*B1.edges().begin();
     auto *E2 = &*(B1.edges().begin() + 1);
     if (E2->getOffset() < E1->getOffset())
       std::swap(E1, E2);
     EXPECT_EQ(E1->getOffset(), 0U);
     EXPECT_EQ(E2->getOffset(), 4U);
   }
 
-  EXPECT_EQ(llvm::size(B2.edges()), 2);
-  if (size(B2.edges()) == 2) {
-    auto *E1 = &*B2.edges().begin();
-    auto *E2 = &*(B2.edges().begin() + 1);
+  EXPECT_EQ(llvm::size(B2->edges()), 2);
+  if (size(B2->edges()) == 2) {
+    auto *E1 = &*B2->edges().begin();
+    auto *E2 = &*(B2->edges().begin() + 1);
     if (E2->getOffset() < E1->getOffset())
       std::swap(E1, E2);
     EXPECT_EQ(E1->getOffset(), 0U);
     EXPECT_EQ(E2->getOffset(), 4U);
   }
 }
+
+TEST(LinkGraphTest, SplitBlockAnonymousSymbol) {
+  LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little,
+              getGenericEdgeKindName);
+  auto &Sec = G.createSection("__data", MemProt::Read | MemProt::Write);
+
+  // Create the block to split.
+  auto &B1 = G.createContentBlock(Sec, BlockContent, 0x1000, 8, 0);
+
+  // Add anonymous symbol to the block that mark the entire block.
+  G.addAnonymousSymbol(B1, 0, BlockContent.size(), false, false);
+  auto B2 = G.splitBlock(B1, 8);
+  EXPECT_THAT_EXPECTED(B2, Succeeded());
+
+  // There should be no more symbols from the new block.
+  EXPECT_EQ((int)Sec.symbols_size(), 0)
+      << "anonymous symbols should be removed";
+}
+
+TEST(LinkGraphTest, SplitBlockNameSymbolError) {
+  LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, support::little,
+              getGenericEdgeKindName);
+  auto &Sec = G.createSection("__data", MemProt::Read | MemProt::Write);
+
+  // Create the block to split.
+  auto &B1 = G.createContentBlock(Sec, BlockContent, 0x1000, 8, 0);
+
+  // Add anonymous symbol to the block that mark the entire block.
+  G.addDefinedSymbol(B1, 0, "Sym", BlockContent.size(), Linkage::Strong,
+                     Scope::Default, false, false);
+  auto B2 = G.splitBlock(B1, 8);
+  EXPECT_THAT_EXPECTED(B2, Failed());
+}