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