llvm/unittests/ExecutionEngine/JITLink/LinkGraphTests.cpp

   1 //===------ LinkGraphTests.cpp - Unit tests for core JITLink classes ------===//
   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 #include "llvm/ADT/STLExtras.h"
  10 #include "llvm/ExecutionEngine/JITLink/JITLink.h"
  11 #include "llvm/ExecutionEngine/Orc/ObjectFileInterface.h"
  12 #include "llvm/Support/Endian.h"
  13 #include "llvm/Support/Memory.h"
  14
  15 #include "llvm/Testing/Support/Error.h"
  16 #include "gtest/gtest.h"
  17
  18 using namespace llvm;
  19 using namespace llvm::jitlink;
  20
  21 static const char BlockContentBytes[] = {
  22     0x54, 0x68, 0x65, 0x72, 0x65, 0x20, 0x77, 0x61, 0x73, 0x20, 0x6d, 0x6f,
  23     0x76, 0x65, 0x6d, 0x65, 0x6e, 0x74, 0x20, 0x61, 0x74, 0x20, 0x74, 0x68,
  24     0x65, 0x20, 0x73, 0x74, 0x61, 0x74, 0x69, 0x6f, 0x6e, 0x2c, 0x20, 0x66,
  25     0x6f, 0x72, 0x20, 0x74, 0x68, 0x65, 0x20, 0x77, 0x6f, 0x72, 0x64, 0x20,
  26     0x68, 0x61, 0x64, 0x20, 0x70, 0x61, 0x73, 0x73, 0x65, 0x64, 0x20, 0x61,
  27     0x72, 0x6f, 0x75, 0x6e, 0x64, 0x0a, 0x54, 0x68, 0x61, 0x74, 0x20, 0x74,
  28     0x68, 0x65, 0x20, 0x63, 0x6f, 0x6c, 0x74, 0x20, 0x66, 0x72, 0x6f, 0x6d,
  29     0x20, 0x4f, 0x6c, 0x64, 0x20, 0x52, 0x65, 0x67, 0x72, 0x65, 0x74, 0x20,
  30     0x68, 0x61, 0x64, 0x20, 0x67, 0x6f, 0x74, 0x20, 0x61, 0x77, 0x61, 0x79,
  31     0x2c, 0x0a, 0x41, 0x6e, 0x64, 0x20, 0x68, 0x61, 0x64, 0x20, 0x6a, 0x6f,
  32     0x69, 0x6e, 0x65, 0x64, 0x20, 0x74, 0x68, 0x65, 0x20, 0x77, 0x69, 0x6c,
  33     0x64, 0x20, 0x62, 0x75, 0x73, 0x68, 0x20, 0x68, 0x6f, 0x72, 0x73, 0x65,
  34     0x73, 0x20, 0x2d, 0x2d, 0x20, 0x68, 0x65, 0x20, 0x77, 0x61, 0x73, 0x20,
  35     0x77, 0x6f, 0x72, 0x74, 0x68, 0x20, 0x61, 0x20, 0x74, 0x68, 0x6f, 0x75,
  36     0x73, 0x61, 0x6e, 0x64, 0x20, 0x70, 0x6f, 0x75, 0x6e, 0x64, 0x2c, 0x0a,
  37     0x53, 0x6f, 0x20, 0x61, 0x6c, 0x6c, 0x20, 0x74, 0x68, 0x65, 0x20, 0x63,
  38     0x72, 0x61, 0x63, 0x6b, 0x73, 0x20, 0x68, 0x61, 0x64, 0x20, 0x67, 0x61,
  39     0x74, 0x68, 0x65, 0x72, 0x65, 0x64, 0x20, 0x74, 0x6f, 0x20, 0x74, 0x68,
  40     0x65, 0x20, 0x66, 0x72, 0x61, 0x79, 0x2e, 0x0a, 0x41, 0x6c, 0x6c, 0x20,
  41     0x74, 0x68, 0x65, 0x20, 0x74, 0x72, 0x69, 0x65, 0x64, 0x20, 0x61, 0x6e,
  42     0x64, 0x20, 0x6e, 0x6f, 0x74, 0x65, 0x64, 0x20, 0x72, 0x69, 0x64, 0x65,
  43     0x72, 0x73, 0x20, 0x66, 0x72, 0x6f, 0x6d, 0x20, 0x74, 0x68, 0x65, 0x20,
  44     0x73, 0x74, 0x61, 0x74, 0x69, 0x6f, 0x6e, 0x73, 0x20, 0x6e, 0x65, 0x61,
  45     0x72, 0x20, 0x61, 0x6e, 0x64, 0x20, 0x66, 0x61, 0x72, 0x0a, 0x48, 0x61,
  46     0x64, 0x20, 0x6d, 0x75, 0x73, 0x74, 0x65, 0x72, 0x65, 0x64, 0x20, 0x61,
  47     0x74, 0x20, 0x74, 0x68, 0x65, 0x20, 0x68, 0x6f, 0x6d, 0x65, 0x73, 0x74,
  48     0x65, 0x61, 0x64, 0x20, 0x6f, 0x76, 0x65, 0x72, 0x6e, 0x69, 0x67, 0x68,
  49     0x74, 0x2c, 0x0a, 0x46, 0x6f, 0x72, 0x20, 0x74, 0x68, 0x65, 0x20, 0x62,
  50     0x75, 0x73, 0x68, 0x6d, 0x65, 0x6e, 0x20, 0x6c, 0x6f, 0x76, 0x65, 0x20,
  51     0x68, 0x61, 0x72, 0x64, 0x20, 0x72, 0x69, 0x64, 0x69, 0x6e, 0x67, 0x20,
  52     0x77, 0x68, 0x65, 0x72, 0x65, 0x20, 0x74, 0x68, 0x65, 0x20, 0x77, 0x69,
  53     0x6c, 0x64, 0x20, 0x62, 0x75, 0x73, 0x68, 0x20, 0x68, 0x6f, 0x72, 0x73,
  54     0x65, 0x73, 0x20, 0x61, 0x72, 0x65, 0x2c, 0x0a, 0x41, 0x6e, 0x64, 0x20,
  55     0x74, 0x68, 0x65, 0x20, 0x73, 0x74, 0x6f, 0x63, 0x6b, 0x2d, 0x68, 0x6f,
  56     0x72, 0x73, 0x65, 0x20, 0x73, 0x6e, 0x75, 0x66, 0x66, 0x73, 0x20, 0x74,
  57     0x68, 0x65, 0x20, 0x62, 0x61, 0x74, 0x74, 0x6c, 0x65, 0x20, 0x77, 0x69,
  58     0x74, 0x68, 0x20, 0x64, 0x65, 0x6c, 0x69, 0x67, 0x68, 0x74, 0x2e, 0x00};
  59
  60 static ArrayRef<char> BlockContent(BlockContentBytes);
  61
  62 TEST(LinkGraphTest, Construction) {
  63   // Check that LinkGraph construction works as expected.
  64   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
  65               getGenericEdgeKindName);
  66   EXPECT_EQ(G.getName(), "foo");
  67   EXPECT_EQ(G.getTargetTriple().str(), "x86_64-apple-darwin");
  68   EXPECT_EQ(G.getPointerSize(), 8U);
  69   EXPECT_EQ(G.getEndianness(), llvm::endianness::little);
  70   EXPECT_TRUE(G.external_symbols().empty());
  71   EXPECT_TRUE(G.absolute_symbols().empty());
  72   EXPECT_TRUE(G.defined_symbols().empty());
  73   EXPECT_TRUE(G.blocks().empty());
  74 }
  75
  76 TEST(LinkGraphTest, AddressAccess) {
  77   // Check that we can get addresses for blocks, symbols, and edges.
  78   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
  79               getGenericEdgeKindName);
  80
  81   auto &Sec1 =
  82       G.createSection("__data.1", orc::MemProt::Read | orc::MemProt::Write);
  83   orc::ExecutorAddr B1Addr(0x1000);
  84   auto &B1 = G.createContentBlock(Sec1, BlockContent, B1Addr, 8, 0);
  85   auto &S1 = G.addDefinedSymbol(B1, 4, "S1", 4, Linkage::Strong, Scope::Default,
  86                                 false, false);
  87   B1.addEdge(Edge::FirstRelocation, 8, S1, 0);
  88   auto &E1 = *B1.edges().begin();
  89
  90   EXPECT_EQ(B1.getAddress(), B1Addr) << "Incorrect block address";
  91   EXPECT_EQ(S1.getAddress(), B1Addr + 4) << "Incorrect symbol address";
  92   EXPECT_EQ(B1.getFixupAddress(E1), B1Addr + 8) << "Incorrect fixup address";
  93 }
  94
  95 TEST(LinkGraphTest, SectionEmpty) {
  96   // Check that Section::empty behaves as expected.
  97   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
  98               getGenericEdgeKindName);
  99   auto &Sec1 =
 100       G.createSection("__data.1", orc::MemProt::Read | orc::MemProt::Write);
 101   auto &B =
 102       G.createContentBlock(Sec1, BlockContent, orc::ExecutorAddr(0x1000), 8, 0);
 103   G.addDefinedSymbol(B, 0, "S", 4, Linkage::Strong, Scope::Default, false,
 104                      false);
 105
 106   auto &Sec2 =
 107       G.createSection("__data.2", orc::MemProt::Read | orc::MemProt::Write);
 108
 109   EXPECT_FALSE(Sec1.empty());
 110   EXPECT_TRUE(Sec2.empty());
 111 }
 112
 113 TEST(LinkGraphTest, BlockAndSymbolIteration) {
 114   // Check that we can iterate over blocks within Sections and across sections.
 115   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
 116               getGenericEdgeKindName);
 117   auto &Sec1 =
 118       G.createSection("__data.1", orc::MemProt::Read | orc::MemProt::Write);
 119   orc::ExecutorAddr B1Addr(0x1000);
 120   auto &B1 = G.createContentBlock(Sec1, BlockContent, B1Addr, 8, 0);
 121   orc::ExecutorAddr B2Addr(0x2000);
 122   auto &B2 = G.createContentBlock(Sec1, BlockContent, B2Addr, 8, 0);
 123   auto &S1 = G.addDefinedSymbol(B1, 0, "S1", 4, Linkage::Strong, Scope::Default,
 124                                 false, false);
 125   auto &S2 = G.addDefinedSymbol(B2, 4, "S2", 4, Linkage::Strong, Scope::Default,
 126                                 false, false);
 127
 128   auto &Sec2 =
 129       G.createSection("__data.2", orc::MemProt::Read | orc::MemProt::Write);
 130   orc::ExecutorAddr B3Addr(0x3000);
 131   auto &B3 = G.createContentBlock(Sec2, BlockContent, B3Addr, 8, 0);
 132   orc::ExecutorAddr B4Addr(0x4000);
 133   auto &B4 = G.createContentBlock(Sec2, BlockContent, B4Addr, 8, 0);
 134   auto &S3 = G.addDefinedSymbol(B3, 0, "S3", 4, Linkage::Strong, Scope::Default,
 135                                 false, false);
 136   auto &S4 = G.addDefinedSymbol(B4, 4, "S4", 4, Linkage::Strong, Scope::Default,
 137                                 false, false);
 138
 139   // Check that iteration of blocks within a section behaves as expected.
 140   EXPECT_EQ(std::distance(Sec1.blocks().begin(), Sec1.blocks().end()), 2);
 141   EXPECT_TRUE(llvm::count(Sec1.blocks(), &B1));
 142   EXPECT_TRUE(llvm::count(Sec1.blocks(), &B2));
 143
 144   // Check that iteration of symbols within a section behaves as expected.
 145   EXPECT_EQ(std::distance(Sec1.symbols().begin(), Sec1.symbols().end()), 2);
 146   EXPECT_TRUE(llvm::count(Sec1.symbols(), &S1));
 147   EXPECT_TRUE(llvm::count(Sec1.symbols(), &S2));
 148
 149   // Check that iteration of blocks across sections behaves as expected.
 150   EXPECT_EQ(std::distance(G.blocks().begin(), G.blocks().end()), 4);
 151   EXPECT_TRUE(llvm::count(G.blocks(), &B1));
 152   EXPECT_TRUE(llvm::count(G.blocks(), &B2));
 153   EXPECT_TRUE(llvm::count(G.blocks(), &B3));
 154   EXPECT_TRUE(llvm::count(G.blocks(), &B4));
 155
 156   // Check that iteration of defined symbols across sections behaves as
 157   // expected.
 158   EXPECT_EQ(
 159       std::distance(G.defined_symbols().begin(), G.defined_symbols().end()), 4);
 160   EXPECT_TRUE(llvm::count(G.defined_symbols(), &S1));
 161   EXPECT_TRUE(llvm::count(G.defined_symbols(), &S2));
 162   EXPECT_TRUE(llvm::count(G.defined_symbols(), &S3));
 163   EXPECT_TRUE(llvm::count(G.defined_symbols(), &S4));
 164 }
 165
 166 TEST(LinkGraphTest, ContentAccessAndUpdate) {
 167   // Check that we can make a defined symbol external.
 168   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
 169               getGenericEdgeKindName);
 170   auto &Sec =
 171       G.createSection("__data", orc::MemProt::Read | orc::MemProt::Write);
 172
 173   // Create an initial block.
 174   orc::ExecutorAddr BAddr(0x1000);
 175   auto &B = G.createContentBlock(Sec, BlockContent, BAddr, 8, 0);
 176
 177   EXPECT_FALSE(B.isContentMutable()) << "Content unexpectedly mutable";
 178   EXPECT_EQ(B.getContent().data(), BlockContent.data())
 179       << "Unexpected block content data pointer";
 180   EXPECT_EQ(B.getContent().size(), BlockContent.size())
 181       << "Unexpected block content size";
 182
 183   // Expect that attempting to get already-mutable content fails if the
 184   // content is not yet mutable (debug builds only).
 185 #ifndef NDEBUG
 186   EXPECT_DEATH({ (void)B.getAlreadyMutableContent(); },
 187                "Content is not mutable")
 188       << "Unexpected mutable access allowed to immutable data";
 189 #endif
 190
 191   // Check that mutable content is copied on request as expected.
 192   auto MutableContent = B.getMutableContent(G);
 193   EXPECT_TRUE(B.isContentMutable()) << "Content unexpectedly immutable";
 194   EXPECT_NE(MutableContent.data(), BlockContent.data())
 195       << "Unexpected mutable content data pointer";
 196   EXPECT_EQ(MutableContent.size(), BlockContent.size())
 197       << "Unexpected mutable content size";
 198   EXPECT_TRUE(std::equal(MutableContent.begin(), MutableContent.end(),
 199                          BlockContent.begin()))
 200       << "Unexpected mutable content value";
 201
 202   // Check that already-mutable content behaves as expected, with no
 203   // further copies.
 204   auto MutableContent2 = B.getMutableContent(G);
 205   EXPECT_TRUE(B.isContentMutable()) << "Content unexpectedly immutable";
 206   EXPECT_EQ(MutableContent2.data(), MutableContent.data())
 207       << "Unexpected mutable content 2 data pointer";
 208   EXPECT_EQ(MutableContent2.size(), MutableContent.size())
 209       << "Unexpected mutable content 2 size";
 210
 211   // Check that getAlreadyMutableContent behaves as expected, with no
 212   // further copies.
 213   auto MutableContent3 = B.getMutableContent(G);
 214   EXPECT_TRUE(B.isContentMutable()) << "Content unexpectedly immutable";
 215   EXPECT_EQ(MutableContent3.data(), MutableContent.data())
 216       << "Unexpected mutable content 2 data pointer";
 217   EXPECT_EQ(MutableContent3.size(), MutableContent.size())
 218       << "Unexpected mutable content 2 size";
 219
 220   // Check that we can obtain a writer and reader over the content.
 221   // Check that we can get a BinaryStreamReader for B.
 222   auto Writer = G.getBlockContentWriter(B);
 223   EXPECT_THAT_ERROR(Writer.writeInteger((uint32_t)0xcafef00d), Succeeded());
 224
 225   auto Reader = G.getBlockContentReader(B);
 226   uint32_t Initial32Bits = 0;
 227   EXPECT_THAT_ERROR(Reader.readInteger(Initial32Bits), Succeeded());
 228   EXPECT_EQ(Initial32Bits, (uint32_t)0xcafef00d);
 229
 230   // Set content back to immutable and check that everything behaves as
 231   // expected again.
 232   B.setContent(BlockContent);
 233   EXPECT_FALSE(B.isContentMutable()) << "Content unexpectedly mutable";
 234   EXPECT_EQ(B.getContent().data(), BlockContent.data())
 235       << "Unexpected block content data pointer";
 236   EXPECT_EQ(B.getContent().size(), BlockContent.size())
 237       << "Unexpected block content size";
 238
 239   // Create an initially mutable block.
 240   auto &B2 = G.createMutableContentBlock(Sec, MutableContent,
 241                                          orc::ExecutorAddr(0x10000), 8, 0);
 242
 243   EXPECT_TRUE(B2.isContentMutable()) << "Expected B2 content to be mutable";
 244   EXPECT_EQ(B2.getSize(), MutableContent.size());
 245
 246   // Create a mutable content block with initial zero-fill.
 247   auto &B3 =
 248       G.createMutableContentBlock(Sec, 16, orc::ExecutorAddr(0x2000), 8, 0);
 249   EXPECT_TRUE(B3.isContentMutable()) << "Expected B2 content to be mutable";
 250   EXPECT_EQ(B3.getSize(), 16U);
 251   EXPECT_TRUE(llvm::all_of(B3.getAlreadyMutableContent(),
 252                            [](char C) { return C == 0; }));
 253 }
 254
 255 TEST(LinkGraphTest, MakeExternal) {
 256   // Check that we can make defined and absolute symbols external.
 257   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
 258               getGenericEdgeKindName);
 259   auto &Sec =
 260       G.createSection("__data", orc::MemProt::Read | orc::MemProt::Write);
 261
 262   // Create an initial block.
 263   auto &B1 =
 264       G.createContentBlock(Sec, BlockContent, orc::ExecutorAddr(0x1000), 8, 0);
 265
 266   // Add a symbol to the block.
 267   auto &S1 = G.addDefinedSymbol(B1, 0, "S1", 4, Linkage::Strong, Scope::Default,
 268                                 false, false);
 269
 270   EXPECT_TRUE(S1.isDefined()) << "Symbol should be defined";
 271   EXPECT_FALSE(S1.isExternal()) << "Symbol should not be external";
 272   EXPECT_FALSE(S1.isAbsolute()) << "Symbol should not be absolute";
 273   EXPECT_TRUE(&S1.getBlock()) << "Symbol should have a non-null block";
 274   EXPECT_EQ(S1.getAddress(), orc::ExecutorAddr(0x1000))
 275       << "Unexpected symbol address";
 276
 277   EXPECT_EQ(
 278       std::distance(G.defined_symbols().begin(), G.defined_symbols().end()), 1U)
 279       << "Unexpected number of defined symbols";
 280   EXPECT_EQ(
 281       std::distance(G.external_symbols().begin(), G.external_symbols().end()),
 282       0U)
 283       << "Unexpected number of external symbols";
 284
 285   // Add an absolute symbol.
 286   auto &S2 = G.addAbsoluteSymbol("S2", orc::ExecutorAddr(0x2000), 0,
 287                                  Linkage::Strong, Scope::Default, true);
 288
 289   EXPECT_TRUE(S2.isAbsolute()) << "Symbol should be absolute";
 290   EXPECT_EQ(
 291       std::distance(G.absolute_symbols().begin(), G.absolute_symbols().end()),
 292       1U)
 293       << "Unexpected number of symbols";
 294
 295   // Make S1 and S2 external, confirm that the its flags are updated and that it
 296   // is moved from the defined/absolute symbols lists to the externals list.
 297   G.makeExternal(S1);
 298   G.makeExternal(S2);
 299
 300   EXPECT_FALSE(S1.isDefined()) << "Symbol should not be defined";
 301   EXPECT_TRUE(S1.isExternal()) << "Symbol should be external";
 302   EXPECT_FALSE(S1.isAbsolute()) << "Symbol should not be absolute";
 303   EXPECT_FALSE(S2.isDefined()) << "Symbol should not be defined";
 304   EXPECT_TRUE(S2.isExternal()) << "Symbol should be external";
 305   EXPECT_FALSE(S2.isAbsolute()) << "Symbol should not be absolute";
 306
 307   EXPECT_EQ(S1.getAddress(), orc::ExecutorAddr())
 308       << "Unexpected symbol address";
 309   EXPECT_EQ(S2.getAddress(), orc::ExecutorAddr())
 310       << "Unexpected symbol address";
 311
 312   EXPECT_EQ(
 313       std::distance(G.defined_symbols().begin(), G.defined_symbols().end()), 0U)
 314       << "Unexpected number of defined symbols";
 315   EXPECT_EQ(
 316       std::distance(G.external_symbols().begin(), G.external_symbols().end()),
 317       2U)
 318       << "Unexpected number of external symbols";
 319   EXPECT_EQ(
 320       std::distance(G.absolute_symbols().begin(), G.absolute_symbols().end()),
 321       0U)
 322       << "Unexpected number of external symbols";
 323 }
 324
 325 TEST(LinkGraphTest, MakeAbsolute) {
 326   // Check that we can make defined and external symbols absolute.
 327   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
 328               getGenericEdgeKindName);
 329   auto &Sec =
 330       G.createSection("__data", orc::MemProt::Read | orc::MemProt::Write);
 331
 332   // Create an initial block.
 333   auto &B1 =
 334       G.createContentBlock(Sec, BlockContent, orc::ExecutorAddr(0x1000), 8, 0);
 335
 336   // Add a symbol to the block.
 337   auto &S1 = G.addDefinedSymbol(B1, 0, "S1", 4, Linkage::Strong, Scope::Default,
 338                                 false, false);
 339
 340   EXPECT_TRUE(S1.isDefined()) << "Symbol should be defined";
 341   EXPECT_FALSE(S1.isExternal()) << "Symbol should not be external";
 342   EXPECT_FALSE(S1.isAbsolute()) << "Symbol should not be absolute";
 343   EXPECT_TRUE(&S1.getBlock()) << "Symbol should have a non-null block";
 344   EXPECT_EQ(S1.getAddress(), orc::ExecutorAddr(0x1000))
 345       << "Unexpected symbol address";
 346
 347   EXPECT_EQ(
 348       std::distance(G.defined_symbols().begin(), G.defined_symbols().end()), 1U)
 349       << "Unexpected number of defined symbols";
 350   EXPECT_EQ(
 351       std::distance(G.external_symbols().begin(), G.external_symbols().end()),
 352       0U)
 353       << "Unexpected number of external symbols";
 354
 355   // Add an external symbol.
 356   auto &S2 = G.addExternalSymbol("S2", 0, true);
 357
 358   EXPECT_TRUE(S2.isExternal()) << "Symbol should be external";
 359   EXPECT_EQ(
 360       std::distance(G.external_symbols().begin(), G.external_symbols().end()),
 361       1U)
 362       << "Unexpected number of symbols";
 363
 364   // Make S1 and S2 absolute, confirm that the its flags are updated and that it
 365   // is moved from the defined/external symbols lists to the absolutes list.
 366   orc::ExecutorAddr S1AbsAddr(0xA000);
 367   orc::ExecutorAddr S2AbsAddr(0xB000);
 368   G.makeAbsolute(S1, S1AbsAddr);
 369   G.makeAbsolute(S2, S2AbsAddr);
 370
 371   EXPECT_FALSE(S1.isDefined()) << "Symbol should not be defined";
 372   EXPECT_FALSE(S1.isExternal()) << "Symbol should not be external";
 373   EXPECT_TRUE(S1.isAbsolute()) << "Symbol should be absolute";
 374   EXPECT_FALSE(S2.isDefined()) << "Symbol should not be defined";
 375   EXPECT_FALSE(S2.isExternal()) << "Symbol should not be absolute";
 376   EXPECT_TRUE(S2.isAbsolute()) << "Symbol should be absolute";
 377
 378   EXPECT_EQ(S1.getAddress(), S1AbsAddr) << "Unexpected symbol address";
 379   EXPECT_EQ(S2.getAddress(), S2AbsAddr) << "Unexpected symbol address";
 380
 381   EXPECT_EQ(
 382       std::distance(G.defined_symbols().begin(), G.defined_symbols().end()), 0U)
 383       << "Unexpected number of defined symbols";
 384   EXPECT_EQ(
 385       std::distance(G.external_symbols().begin(), G.external_symbols().end()),
 386       0U)
 387       << "Unexpected number of external symbols";
 388   EXPECT_EQ(
 389       std::distance(G.absolute_symbols().begin(), G.absolute_symbols().end()),
 390       2U)
 391       << "Unexpected number of external symbols";
 392 }
 393
 394 TEST(LinkGraphTest, MakeDefined) {
 395   // Check that we can make an external symbol defined.
 396   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
 397               getGenericEdgeKindName);
 398   auto &Sec =
 399       G.createSection("__data", orc::MemProt::Read | orc::MemProt::Write);
 400
 401   // Create an initial block.
 402   orc::ExecutorAddr B1Addr(0x1000);
 403   auto &B1 = G.createContentBlock(Sec, BlockContent, B1Addr, 8, 0);
 404
 405   // Add an external symbol.
 406   auto &S1 = G.addExternalSymbol("S1", 4, true);
 407
 408   EXPECT_FALSE(S1.isDefined()) << "Symbol should not be defined";
 409   EXPECT_TRUE(S1.isExternal()) << "Symbol should be external";
 410   EXPECT_FALSE(S1.isAbsolute()) << "Symbol should not be absolute";
 411   EXPECT_EQ(S1.getAddress(), orc::ExecutorAddr())
 412       << "Unexpected symbol address";
 413
 414   EXPECT_EQ(
 415       std::distance(G.defined_symbols().begin(), G.defined_symbols().end()), 0U)
 416       << "Unexpected number of defined symbols";
 417   EXPECT_EQ(
 418       std::distance(G.external_symbols().begin(), G.external_symbols().end()),
 419       1U)
 420       << "Unexpected number of external symbols";
 421
 422   // Make S1 defined, confirm that its flags are updated and that it is
 423   // moved from the defined symbols to the externals list.
 424   G.makeDefined(S1, B1, 0, 4, Linkage::Strong, Scope::Default, false);
 425
 426   EXPECT_TRUE(S1.isDefined()) << "Symbol should be defined";
 427   EXPECT_FALSE(S1.isExternal()) << "Symbol should not be external";
 428   EXPECT_FALSE(S1.isAbsolute()) << "Symbol should not be absolute";
 429   EXPECT_TRUE(&S1.getBlock()) << "Symbol should have a non-null block";
 430   EXPECT_EQ(S1.getAddress(), orc::ExecutorAddr(0x1000U))
 431       << "Unexpected symbol address";
 432
 433   EXPECT_EQ(
 434       std::distance(G.defined_symbols().begin(), G.defined_symbols().end()), 1U)
 435       << "Unexpected number of defined symbols";
 436   EXPECT_EQ(
 437       std::distance(G.external_symbols().begin(), G.external_symbols().end()),
 438       0U)
 439       << "Unexpected number of external symbols";
 440 }
 441
 442 TEST(LinkGraphTest, TransferDefinedSymbol) {
 443   // Check that we can transfer a defined symbol from one block to another.
 444   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
 445               getGenericEdgeKindName);
 446   auto &Sec =
 447       G.createSection("__data", orc::MemProt::Read | orc::MemProt::Write);
 448
 449   // Create initial blocks.
 450   orc::ExecutorAddr B1Addr(0x1000);
 451   auto &B1 = G.createContentBlock(Sec, BlockContent, B1Addr, 8, 0);
 452   orc::ExecutorAddr B2Addr(0x2000);
 453   auto &B2 = G.createContentBlock(Sec, BlockContent, B2Addr, 8, 0);
 454   orc::ExecutorAddr B3Addr(0x3000);
 455   auto &B3 = G.createContentBlock(Sec, BlockContent.slice(0, 32), B3Addr, 8, 0);
 456
 457   // Add a symbol.
 458   auto &S1 = G.addDefinedSymbol(B1, 0, "S1", B1.getSize(), Linkage::Strong,
 459                                 Scope::Default, false, false);
 460
 461   // Transfer with zero offset, explicit size.
 462   G.transferDefinedSymbol(S1, B2, 0, 64);
 463
 464   EXPECT_EQ(&S1.getBlock(), &B2) << "Block was not updated";
 465   EXPECT_EQ(S1.getOffset(), 0U) << "Unexpected offset";
 466   EXPECT_EQ(S1.getSize(), 64U) << "Size was not updated";
 467
 468   // Transfer with non-zero offset, implicit truncation.
 469   G.transferDefinedSymbol(S1, B3, 16, std::nullopt);
 470
 471   EXPECT_EQ(&S1.getBlock(), &B3) << "Block was not updated";
 472   EXPECT_EQ(S1.getOffset(), 16U) << "Offset was not updated";
 473   EXPECT_EQ(S1.getSize(), 16U) << "Size was not updated";
 474 }
 475
 476 TEST(LinkGraphTest, TransferDefinedSymbolAcrossSections) {
 477   // Check that we can transfer a defined symbol from an existing block in one
 478   // section to another.
 479   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
 480               getGenericEdgeKindName);
 481   auto &Sec1 =
 482       G.createSection("__data.1", orc::MemProt::Read | orc::MemProt::Write);
 483   auto &Sec2 =
 484       G.createSection("__data.2", orc::MemProt::Read | orc::MemProt::Write);
 485
 486   // Create blocks in each section.
 487   orc::ExecutorAddr B1Addr(0x1000);
 488   auto &B1 = G.createContentBlock(Sec1, BlockContent, B1Addr, 8, 0);
 489   orc::ExecutorAddr B2Addr(0x2000);
 490   auto &B2 = G.createContentBlock(Sec2, BlockContent, B2Addr, 8, 0);
 491
 492   // Add a symbol to section 1.
 493   auto &S1 = G.addDefinedSymbol(B1, 0, "S1", B1.getSize(), Linkage::Strong,
 494                                 Scope::Default, false, false);
 495
 496   // Transfer with zero offset, explicit size to section 2.
 497   G.transferDefinedSymbol(S1, B2, 0, 64);
 498
 499   EXPECT_EQ(&S1.getBlock(), &B2) << "Block was not updated";
 500   EXPECT_EQ(S1.getOffset(), 0U) << "Unexpected offset";
 501   EXPECT_EQ(S1.getSize(), 64U) << "Size was not updated";
 502
 503   EXPECT_EQ(Sec1.symbols_size(), 0u) << "Symbol was not removed from Sec1";
 504   EXPECT_EQ(Sec2.symbols_size(), 1u) << "Symbol was not added to Sec2";
 505   if (Sec2.symbols_size() == 1) {
 506     EXPECT_EQ(*Sec2.symbols().begin(), &S1) << "Unexpected symbol";
 507   }
 508 }
 509
 510 TEST(LinkGraphTest, TransferBlock) {
 511   // Check that we can transfer a block (and all associated symbols) from one
 512   // section to another.
 513   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
 514               getGenericEdgeKindName);
 515   auto &Sec1 =
 516       G.createSection("__data.1", orc::MemProt::Read | orc::MemProt::Write);
 517   auto &Sec2 =
 518       G.createSection("__data.2", orc::MemProt::Read | orc::MemProt::Write);
 519
 520   // Create an initial block.
 521   orc::ExecutorAddr B1Addr(0x1000);
 522   auto &B1 = G.createContentBlock(Sec1, BlockContent, B1Addr, 8, 0);
 523   orc::ExecutorAddr B2Addr(0x2000);
 524   auto &B2 = G.createContentBlock(Sec1, BlockContent, B2Addr, 8, 0);
 525
 526   // Add some symbols on B1...
 527   G.addDefinedSymbol(B1, 0, "S1", B1.getSize(), Linkage::Strong, Scope::Default,
 528                      false, false);
 529   G.addDefinedSymbol(B1, 1, "S2", B1.getSize() - 1, Linkage::Strong,
 530                      Scope::Default, false, false);
 531
 532   // ... and on B2.
 533   G.addDefinedSymbol(B2, 0, "S3", B2.getSize(), Linkage::Strong, Scope::Default,
 534                      false, false);
 535   G.addDefinedSymbol(B2, 1, "S4", B2.getSize() - 1, Linkage::Strong,
 536                      Scope::Default, false, false);
 537
 538   EXPECT_EQ(Sec1.blocks_size(), 2U) << "Expected two blocks in Sec1 initially";
 539   EXPECT_EQ(Sec1.symbols_size(), 4U)
 540       << "Expected four symbols in Sec1 initially";
 541   EXPECT_EQ(Sec2.blocks_size(), 0U) << "Expected zero blocks in Sec2 initially";
 542   EXPECT_EQ(Sec2.symbols_size(), 0U)
 543       << "Expected zero symbols in Sec2 initially";
 544
 545   // Transfer with zero offset, explicit size.
 546   G.transferBlock(B1, Sec2);
 547
 548   EXPECT_EQ(Sec1.blocks_size(), 1U)
 549       << "Expected one blocks in Sec1 after transfer";
 550   EXPECT_EQ(Sec1.symbols_size(), 2U)
 551       << "Expected two symbols in Sec1 after transfer";
 552   EXPECT_EQ(Sec2.blocks_size(), 1U)
 553       << "Expected one blocks in Sec2 after transfer";
 554   EXPECT_EQ(Sec2.symbols_size(), 2U)
 555       << "Expected two symbols in Sec2 after transfer";
 556 }
 557
 558 TEST(LinkGraphTest, MergeSections) {
 559   // Check that we can transfer a block (and all associated symbols) from one
 560   // section to another.
 561   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
 562               getGenericEdgeKindName);
 563   auto &Sec1 =
 564       G.createSection("__data.1", orc::MemProt::Read | orc::MemProt::Write);
 565   auto &Sec2 =
 566       G.createSection("__data.2", orc::MemProt::Read | orc::MemProt::Write);
 567   auto &Sec3 =
 568       G.createSection("__data.3", orc::MemProt::Read | orc::MemProt::Write);
 569
 570   // Create an initial block.
 571   orc::ExecutorAddr B1Addr(0x1000);
 572   auto &B1 = G.createContentBlock(Sec1, BlockContent, B1Addr, 8, 0);
 573   orc::ExecutorAddr B2Addr(0x2000);
 574   auto &B2 = G.createContentBlock(Sec2, BlockContent, B2Addr, 8, 0);
 575   orc::ExecutorAddr B3Addr(0x3000);
 576   auto &B3 = G.createContentBlock(Sec3, BlockContent, B3Addr, 8, 0);
 577
 578   // Add a symbols for each block.
 579   G.addDefinedSymbol(B1, 0, "S1", B1.getSize(), Linkage::Strong, Scope::Default,
 580                      false, false);
 581   G.addDefinedSymbol(B2, 0, "S2", B2.getSize(), Linkage::Strong, Scope::Default,
 582                      false, false);
 583   G.addDefinedSymbol(B3, 0, "S3", B2.getSize(), Linkage::Strong, Scope::Default,
 584                      false, false);
 585
 586   EXPECT_EQ(&B1.getSection(), &Sec1);
 587   EXPECT_EQ(&B2.getSection(), &Sec2);
 588   EXPECT_EQ(G.sections_size(), 3U) << "Expected three sections initially";
 589   EXPECT_EQ(Sec1.blocks_size(), 1U) << "Expected one block in Sec1 initially";
 590   EXPECT_EQ(Sec1.symbols_size(), 1U) << "Expected one symbol in Sec1 initially";
 591   EXPECT_EQ(Sec2.blocks_size(), 1U) << "Expected one block in Sec2 initially";
 592   EXPECT_EQ(Sec2.symbols_size(), 1U) << "Expected one symbol in Sec2 initially";
 593   EXPECT_EQ(Sec3.blocks_size(), 1U) << "Expected one block in Sec3 initially";
 594   EXPECT_EQ(Sec3.symbols_size(), 1U) << "Expected one symbol in Sec3 initially";
 595
 596   // Check that self-merge is a no-op.
 597   G.mergeSections(Sec1, Sec1);
 598
 599   EXPECT_EQ(&B1.getSection(), &Sec1)
 600       << "Expected B1.getSection() to remain unchanged";
 601   EXPECT_EQ(G.sections_size(), 3U)
 602       << "Expected three sections after first merge";
 603   EXPECT_EQ(Sec1.blocks_size(), 1U)
 604       << "Expected one block in Sec1 after first merge";
 605   EXPECT_EQ(Sec1.symbols_size(), 1U)
 606       << "Expected one symbol in Sec1 after first merge";
 607   EXPECT_EQ(Sec2.blocks_size(), 1U)
 608       << "Expected one block in Sec2 after first merge";
 609   EXPECT_EQ(Sec2.symbols_size(), 1U)
 610       << "Expected one symbol in Sec2 after first merge";
 611   EXPECT_EQ(Sec3.blocks_size(), 1U)
 612       << "Expected one block in Sec3 after first merge";
 613   EXPECT_EQ(Sec3.symbols_size(), 1U)
 614       << "Expected one symbol in Sec3 after first merge";
 615
 616   // Merge Sec2 into Sec1, removing Sec2.
 617   G.mergeSections(Sec1, Sec2);
 618
 619   EXPECT_EQ(&B2.getSection(), &Sec1)
 620       << "Expected B2.getSection() to have been changed to &Sec1";
 621   EXPECT_EQ(G.sections_size(), 2U)
 622       << "Expected two sections after section merge";
 623   EXPECT_EQ(Sec1.blocks_size(), 2U)
 624       << "Expected two blocks in Sec1 after section merge";
 625   EXPECT_EQ(Sec1.symbols_size(), 2U)
 626       << "Expected two symbols in Sec1 after section merge";
 627   EXPECT_EQ(Sec3.blocks_size(), 1U)
 628       << "Expected one block in Sec3 after section merge";
 629   EXPECT_EQ(Sec3.symbols_size(), 1U)
 630       << "Expected one symbol in Sec3 after section merge";
 631
 632   G.mergeSections(Sec1, Sec3, true);
 633
 634   EXPECT_EQ(G.sections_size(), 2U) << "Expected two sections after third merge";
 635   EXPECT_EQ(Sec1.blocks_size(), 3U)
 636       << "Expected three blocks in Sec1 after third merge";
 637   EXPECT_EQ(Sec1.symbols_size(), 3U)
 638       << "Expected three symbols in Sec1 after third merge";
 639   EXPECT_EQ(Sec3.blocks_size(), 0U)
 640       << "Expected one block in Sec3 after third merge";
 641   EXPECT_EQ(Sec3.symbols_size(), 0U)
 642       << "Expected one symbol in Sec3 after third merge";
 643 }
 644
 645 TEST(LinkGraphTest, SplitBlock) {
 646   // Check that the LinkGraph::splitBlock test works as expected.
 647   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
 648               getGenericEdgeKindName);
 649   auto &Sec =
 650       G.createSection("__data", orc::MemProt::Read | orc::MemProt::Write);
 651
 652   // Create the block to split.
 653   orc::ExecutorAddr B1Addr(0x1000);
 654   auto &B1 = G.createContentBlock(Sec, BlockContent, B1Addr, 8, 0);
 655
 656   // Add some symbols to the block.
 657   auto &S1 = G.addDefinedSymbol(B1, 0, "S1", 4, Linkage::Strong, Scope::Default,
 658                                 false, false);
 659   auto &S2 = G.addDefinedSymbol(B1, 4, "S2", 4, Linkage::Strong, Scope::Default,
 660                                 false, false);
 661   auto &S3 = G.addDefinedSymbol(B1, 8, "S3", 4, Linkage::Strong, Scope::Default,
 662                                 false, false);
 663   auto &S4 = G.addDefinedSymbol(B1, 12, "S4", 4, Linkage::Strong,
 664                                 Scope::Default, false, false);
 665   // Add a symbol that extends beyond the split.
 666   auto &S5 = G.addDefinedSymbol(B1, 0, "S5", 16, Linkage::Strong,
 667                                 Scope::Default, false, false);
 668
 669   // Add an extra block, EB, and target symbols, and use these to add edges
 670   // from B1 to EB.
 671   orc::ExecutorAddr EBAddr(0x2000);
 672   auto &EB = G.createContentBlock(Sec, BlockContent, EBAddr, 8, 0);
 673   auto &ES1 = G.addDefinedSymbol(EB, 0, "TS1", 4, Linkage::Strong,
 674                                  Scope::Default, false, false);
 675   auto &ES2 = G.addDefinedSymbol(EB, 4, "TS2", 4, Linkage::Strong,
 676                                  Scope::Default, false, false);
 677   auto &ES3 = G.addDefinedSymbol(EB, 8, "TS3", 4, Linkage::Strong,
 678                                  Scope::Default, false, false);
 679   auto &ES4 = G.addDefinedSymbol(EB, 12, "TS4", 4, Linkage::Strong,
 680                                  Scope::Default, false, false);
 681
 682   // Add edges from B1 to EB.
 683   B1.addEdge(Edge::FirstRelocation, 0, ES1, 0);
 684   B1.addEdge(Edge::FirstRelocation, 4, ES2, 0);
 685   B1.addEdge(Edge::FirstRelocation, 8, ES3, 0);
 686   B1.addEdge(Edge::FirstRelocation, 12, ES4, 0);
 687
 688   // Split B1.
 689   auto &B2 = G.splitBlock(B1, 8);
 690
 691   // Check that the block addresses and content matches what we would expect.
 692   EXPECT_EQ(B1.getAddress(), B1Addr + 8);
 693   EXPECT_EQ(B1.getContent(), BlockContent.slice(8));
 694
 695   EXPECT_EQ(B2.getAddress(), B1Addr);
 696   EXPECT_EQ(B2.getContent(), BlockContent.slice(0, 8));
 697
 698   // Check that symbols in B1 were transferred as expected:
 699   // We expect S1 and S2 to have been transferred to B2, and S3 and S4 to have
 700   // remained attached to B1. Symbols S3 and S4 should have had their offsets
 701   // slid to account for the change in address of B2.
 702   EXPECT_EQ(&S1.getBlock(), &B2);
 703   EXPECT_EQ(S1.getOffset(), 0U);
 704
 705   EXPECT_EQ(&S2.getBlock(), &B2);
 706   EXPECT_EQ(S2.getOffset(), 4U);
 707
 708   EXPECT_EQ(&S3.getBlock(), &B1);
 709   EXPECT_EQ(S3.getOffset(), 0U);
 710
 711   EXPECT_EQ(&S4.getBlock(), &B1);
 712   EXPECT_EQ(S4.getOffset(), 4U);
 713
 714   EXPECT_EQ(&S5.getBlock(), &B2);
 715   EXPECT_EQ(S5.getOffset(), 0U);
 716   // Size shrinks to fit.
 717   EXPECT_EQ(S5.getSize(), 8U);
 718
 719   // Check that edges in B1 have been transferred as expected:
 720   // Both blocks should now have two edges each at offsets 0 and 4.
 721   EXPECT_EQ(llvm::size(B1.edges()), 2);
 722   if (size(B1.edges()) == 2) {
 723     auto *E1 = &*B1.edges().begin();
 724     auto *E2 = &*(B1.edges().begin() + 1);
 725     if (E2->getOffset() < E1->getOffset())
 726       std::swap(E1, E2);
 727     EXPECT_EQ(E1->getOffset(), 0U);
 728     EXPECT_EQ(E2->getOffset(), 4U);
 729   }
 730
 731   EXPECT_EQ(llvm::size(B2.edges()), 2);
 732   if (size(B2.edges()) == 2) {
 733     auto *E1 = &*B2.edges().begin();
 734     auto *E2 = &*(B2.edges().begin() + 1);
 735     if (E2->getOffset() < E1->getOffset())
 736       std::swap(E1, E2);
 737     EXPECT_EQ(E1->getOffset(), 0U);
 738     EXPECT_EQ(E2->getOffset(), 4U);
 739   }
 740 }
 741
 742 TEST(LinkGraphTest, GraphAllocationMethods) {
 743   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
 744               getGenericEdgeKindName);
 745
 746   // Test allocation of sized, uninitialized buffer.
 747   auto Buf1 = G.allocateBuffer(10);
 748   EXPECT_EQ(Buf1.size(), 10U);
 749
 750   // Test allocation of content-backed buffer.
 751   char Buf2Src[] = {1, static_cast<char>(-1), 0, 42};
 752   auto Buf2 = G.allocateContent(ArrayRef<char>(Buf2Src));
 753   EXPECT_EQ(Buf2, ArrayRef<char>(Buf2Src));
 754
 755   // Test c-string allocation from StringRef.
 756   StringRef Buf3Src = "hello";
 757   auto Buf3 = G.allocateCString(Buf3Src);
 758   EXPECT_TRUE(llvm::equal(Buf3.drop_back(1), Buf3Src));
 759   EXPECT_EQ(Buf3.back(), '\0');
 760 }
 761
 762 TEST(LinkGraphTest, IsCStringBlockTest) {
 763   // Check that the LinkGraph::splitBlock test works as expected.
 764   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
 765               getGenericEdgeKindName);
 766   auto &Sec =
 767       G.createSection("__data", orc::MemProt::Read | orc::MemProt::Write);
 768
 769   char CString[] = "hello, world!";
 770   char NotACString[] = {0, 1, 0, 1, 0};
 771
 772   auto &CStringBlock =
 773       G.createContentBlock(Sec, CString, orc::ExecutorAddr(), 1, 0);
 774   auto &NotACStringBlock =
 775       G.createContentBlock(Sec, NotACString, orc::ExecutorAddr(), 1, 0);
 776   auto &SizeOneZeroFillBlock =
 777       G.createZeroFillBlock(Sec, 1, orc::ExecutorAddr(), 1, 0);
 778   auto &LargerZeroFillBlock =
 779       G.createZeroFillBlock(Sec, 2, orc::ExecutorAddr(), 1, 0);
 780
 781   EXPECT_TRUE(isCStringBlock(CStringBlock));
 782   EXPECT_FALSE(isCStringBlock(NotACStringBlock));
 783   EXPECT_TRUE(isCStringBlock(SizeOneZeroFillBlock));
 784   EXPECT_FALSE(isCStringBlock(LargerZeroFillBlock));
 785 }
 786
 787 TEST(LinkGraphTest, BasicLayoutHonorsNoAlloc) {
 788   // Check that BasicLayout honors NoAlloc.
 789   LinkGraph G("foo", Triple("x86_64-apple-darwin"), 8, llvm::endianness::little,
 790               getGenericEdgeKindName);
 791
 792   // Create a regular section and block.
 793   auto &Sec1 =
 794       G.createSection("__data", orc::MemProt::Read | orc::MemProt::Write);
 795   G.createContentBlock(Sec1, BlockContent.slice(0, 8), orc::ExecutorAddr(), 8,
 796                        0);
 797
 798   // Create a NoAlloc section and block.
 799   auto &Sec2 =
 800       G.createSection("__metadata", orc::MemProt::Read | orc::MemProt::Write);
 801   Sec2.setMemLifetime(orc::MemLifetime::NoAlloc);
 802   G.createContentBlock(Sec2, BlockContent.slice(0, 8), orc::ExecutorAddr(), 8,
 803                        0);
 804
 805   BasicLayout BL(G);
 806
 807   EXPECT_EQ(std::distance(BL.segments().begin(), BL.segments().end()), 1U);
 808   EXPECT_EQ(BL.segments().begin()->first,
 809             orc::MemProt::Read | orc::MemProt::Write);
 810   auto &SegInfo = BL.segments().begin()->second;
 811   EXPECT_EQ(SegInfo.Alignment, 8U);
 812   EXPECT_EQ(SegInfo.ContentSize, 8U);
 813 }