llvm/unittests/ProfileData/MemProfTest.cpp

   1 //===- unittests/Support/MemProfTest.cpp ----------------------------------===//
   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/ProfileData/MemProf.h"
  10 #include "llvm/ADT/DenseMap.h"
  11 #include "llvm/ADT/MapVector.h"
  12 #include "llvm/ADT/STLForwardCompat.h"
  13 #include "llvm/DebugInfo/DIContext.h"
  14 #include "llvm/DebugInfo/Symbolize/SymbolizableModule.h"
  15 #include "llvm/IR/Value.h"
  16 #include "llvm/Object/ObjectFile.h"
  17 #include "llvm/ProfileData/MemProfData.inc"
  18 #include "llvm/ProfileData/MemProfReader.h"
  19 #include "llvm/Support/raw_ostream.h"
  20 #include "gmock/gmock.h"
  21 #include "gtest/gtest.h"
  22
  23 #include <initializer_list>
  24
  25 namespace {
  26
  27 using ::llvm::DIGlobal;
  28 using ::llvm::DIInliningInfo;
  29 using ::llvm::DILineInfo;
  30 using ::llvm::DILineInfoSpecifier;
  31 using ::llvm::DILocal;
  32 using ::llvm::StringRef;
  33 using ::llvm::memprof::CallStackId;
  34 using ::llvm::memprof::CallStackMap;
  35 using ::llvm::memprof::Frame;
  36 using ::llvm::memprof::FrameId;
  37 using ::llvm::memprof::IndexedAllocationInfo;
  38 using ::llvm::memprof::IndexedMemProfRecord;
  39 using ::llvm::memprof::MemInfoBlock;
  40 using ::llvm::memprof::MemProfReader;
  41 using ::llvm::memprof::MemProfRecord;
  42 using ::llvm::memprof::MemProfSchema;
  43 using ::llvm::memprof::Meta;
  44 using ::llvm::memprof::PortableMemInfoBlock;
  45 using ::llvm::memprof::RawMemProfReader;
  46 using ::llvm::memprof::SegmentEntry;
  47 using ::llvm::object::SectionedAddress;
  48 using ::llvm::symbolize::SymbolizableModule;
  49 using ::testing::Return;
  50 using ::testing::SizeIs;
  51
  52 class MockSymbolizer : public SymbolizableModule {
  53 public:
  54   MOCK_CONST_METHOD3(symbolizeInlinedCode,
  55                      DIInliningInfo(SectionedAddress, DILineInfoSpecifier,
  56                                     bool));
  57   // Most of the methods in the interface are unused. We only mock the
  58   // method that we expect to be called from the memprof reader.
  59   virtual DILineInfo symbolizeCode(SectionedAddress, DILineInfoSpecifier,
  60                                    bool) const {
  61     llvm_unreachable("unused");
  62   }
  63   virtual DIGlobal symbolizeData(SectionedAddress) const {
  64     llvm_unreachable("unused");
  65   }
  66   virtual std::vector<DILocal> symbolizeFrame(SectionedAddress) const {
  67     llvm_unreachable("unused");
  68   }
  69   virtual std::vector<SectionedAddress> findSymbol(StringRef Symbol,
  70                                                    uint64_t Offset) const {
  71     llvm_unreachable("unused");
  72   }
  73   virtual bool isWin32Module() const { llvm_unreachable("unused"); }
  74   virtual uint64_t getModulePreferredBase() const {
  75     llvm_unreachable("unused");
  76   }
  77 };
  78
  79 struct MockInfo {
  80   std::string FunctionName;
  81   uint32_t Line;
  82   uint32_t StartLine;
  83   uint32_t Column;
  84   std::string FileName = "valid/path.cc";
  85 };
  86 DIInliningInfo makeInliningInfo(std::initializer_list<MockInfo> MockFrames) {
  87   DIInliningInfo Result;
  88   for (const auto &Item : MockFrames) {
  89     DILineInfo Frame;
  90     Frame.FunctionName = Item.FunctionName;
  91     Frame.Line = Item.Line;
  92     Frame.StartLine = Item.StartLine;
  93     Frame.Column = Item.Column;
  94     Frame.FileName = Item.FileName;
  95     Result.addFrame(Frame);
  96   }
  97   return Result;
  98 }
  99
 100 llvm::SmallVector<SegmentEntry, 4> makeSegments() {
 101   llvm::SmallVector<SegmentEntry, 4> Result;
 102   // Mimic an entry for a non position independent executable.
 103   Result.emplace_back(0x0, 0x40000, 0x0);
 104   return Result;
 105 }
 106
 107 const DILineInfoSpecifier specifier() {
 108   return DILineInfoSpecifier(
 109       DILineInfoSpecifier::FileLineInfoKind::RawValue,
 110       DILineInfoSpecifier::FunctionNameKind::LinkageName);
 111 }
 112
 113 MATCHER_P4(FrameContains, FunctionName, LineOffset, Column, Inline, "") {
 114   const Frame &F = arg;
 115
 116   const uint64_t ExpectedHash = IndexedMemProfRecord::getGUID(FunctionName);
 117   if (F.Function != ExpectedHash) {
 118     *result_listener << "Hash mismatch";
 119     return false;
 120   }
 121   if (F.SymbolName && *F.SymbolName != FunctionName) {
 122     *result_listener << "SymbolName mismatch\nWant: " << FunctionName
 123                      << "\nGot: " << *F.SymbolName;
 124     return false;
 125   }
 126   if (F.LineOffset == LineOffset && F.Column == Column &&
 127       F.IsInlineFrame == Inline) {
 128     return true;
 129   }
 130   *result_listener << "LineOffset, Column or Inline mismatch";
 131   return false;
 132 }
 133
 134 TEST(MemProf, FillsValue) {
 135   std::unique_ptr<MockSymbolizer> Symbolizer(new MockSymbolizer());
 136
 137   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x1000},
 138                                                 specifier(), false))
 139       .Times(1) // Only once since we remember invalid PCs.
 140       .WillRepeatedly(Return(makeInliningInfo({
 141           {"new", 70, 57, 3, "memprof/memprof_new_delete.cpp"},
 142       })));
 143
 144   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x2000},
 145                                                 specifier(), false))
 146       .Times(1) // Only once since we cache the result for future lookups.
 147       .WillRepeatedly(Return(makeInliningInfo({
 148           {"foo", 10, 5, 30},
 149           {"bar", 201, 150, 20},
 150       })));
 151
 152   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x3000},
 153                                                 specifier(), false))
 154       .Times(1)
 155       .WillRepeatedly(Return(makeInliningInfo({
 156           {"xyz.llvm.123", 10, 5, 30},
 157           {"abc", 10, 5, 30},
 158       })));
 159
 160   CallStackMap CSM;
 161   CSM[0x1] = {0x1000, 0x2000, 0x3000};
 162
 163   llvm::MapVector<uint64_t, MemInfoBlock> Prof;
 164   Prof[0x1].AllocCount = 1;
 165
 166   auto Seg = makeSegments();
 167
 168   RawMemProfReader Reader(std::move(Symbolizer), Seg, Prof, CSM,
 169                           /*KeepName=*/true);
 170
 171   llvm::DenseMap<llvm::GlobalValue::GUID, MemProfRecord> Records;
 172   for (const auto &Pair : Reader) {
 173     Records.insert({Pair.first, Pair.second});
 174   }
 175
 176   // Mock program pseudocode and expected memprof record contents.
 177   //
 178   //                              AllocSite       CallSite
 179   // inline foo() { new(); }         Y               N
 180   // bar() { foo(); }                Y               Y
 181   // inline xyz() { bar(); }         N               Y
 182   // abc() { xyz(); }                N               Y
 183
 184   // We expect 4 records. We attach alloc site data to foo and bar, i.e.
 185   // all frames bottom up until we find a non-inline frame. We attach call site
 186   // data to bar, xyz and abc.
 187   ASSERT_THAT(Records, SizeIs(4));
 188
 189   // Check the memprof record for foo.
 190   const llvm::GlobalValue::GUID FooId = IndexedMemProfRecord::getGUID("foo");
 191   ASSERT_TRUE(Records.contains(FooId));
 192   const MemProfRecord &Foo = Records[FooId];
 193   ASSERT_THAT(Foo.AllocSites, SizeIs(1));
 194   EXPECT_EQ(Foo.AllocSites[0].Info.getAllocCount(), 1U);
 195   EXPECT_THAT(Foo.AllocSites[0].CallStack[0],
 196               FrameContains("foo", 5U, 30U, true));
 197   EXPECT_THAT(Foo.AllocSites[0].CallStack[1],
 198               FrameContains("bar", 51U, 20U, false));
 199   EXPECT_THAT(Foo.AllocSites[0].CallStack[2],
 200               FrameContains("xyz", 5U, 30U, true));
 201   EXPECT_THAT(Foo.AllocSites[0].CallStack[3],
 202               FrameContains("abc", 5U, 30U, false));
 203   EXPECT_TRUE(Foo.CallSites.empty());
 204
 205   // Check the memprof record for bar.
 206   const llvm::GlobalValue::GUID BarId = IndexedMemProfRecord::getGUID("bar");
 207   ASSERT_TRUE(Records.contains(BarId));
 208   const MemProfRecord &Bar = Records[BarId];
 209   ASSERT_THAT(Bar.AllocSites, SizeIs(1));
 210   EXPECT_EQ(Bar.AllocSites[0].Info.getAllocCount(), 1U);
 211   EXPECT_THAT(Bar.AllocSites[0].CallStack[0],
 212               FrameContains("foo", 5U, 30U, true));
 213   EXPECT_THAT(Bar.AllocSites[0].CallStack[1],
 214               FrameContains("bar", 51U, 20U, false));
 215   EXPECT_THAT(Bar.AllocSites[0].CallStack[2],
 216               FrameContains("xyz", 5U, 30U, true));
 217   EXPECT_THAT(Bar.AllocSites[0].CallStack[3],
 218               FrameContains("abc", 5U, 30U, false));
 219
 220   ASSERT_THAT(Bar.CallSites, SizeIs(1));
 221   ASSERT_THAT(Bar.CallSites[0], SizeIs(2));
 222   EXPECT_THAT(Bar.CallSites[0][0], FrameContains("foo", 5U, 30U, true));
 223   EXPECT_THAT(Bar.CallSites[0][1], FrameContains("bar", 51U, 20U, false));
 224
 225   // Check the memprof record for xyz.
 226   const llvm::GlobalValue::GUID XyzId = IndexedMemProfRecord::getGUID("xyz");
 227   ASSERT_TRUE(Records.contains(XyzId));
 228   const MemProfRecord &Xyz = Records[XyzId];
 229   ASSERT_THAT(Xyz.CallSites, SizeIs(1));
 230   ASSERT_THAT(Xyz.CallSites[0], SizeIs(2));
 231   // Expect the entire frame even though in practice we only need the first
 232   // entry here.
 233   EXPECT_THAT(Xyz.CallSites[0][0], FrameContains("xyz", 5U, 30U, true));
 234   EXPECT_THAT(Xyz.CallSites[0][1], FrameContains("abc", 5U, 30U, false));
 235
 236   // Check the memprof record for abc.
 237   const llvm::GlobalValue::GUID AbcId = IndexedMemProfRecord::getGUID("abc");
 238   ASSERT_TRUE(Records.contains(AbcId));
 239   const MemProfRecord &Abc = Records[AbcId];
 240   EXPECT_TRUE(Abc.AllocSites.empty());
 241   ASSERT_THAT(Abc.CallSites, SizeIs(1));
 242   ASSERT_THAT(Abc.CallSites[0], SizeIs(2));
 243   EXPECT_THAT(Abc.CallSites[0][0], FrameContains("xyz", 5U, 30U, true));
 244   EXPECT_THAT(Abc.CallSites[0][1], FrameContains("abc", 5U, 30U, false));
 245 }
 246
 247 TEST(MemProf, PortableWrapper) {
 248   MemInfoBlock Info(/*size=*/16, /*access_count=*/7, /*alloc_timestamp=*/1000,
 249                     /*dealloc_timestamp=*/2000, /*alloc_cpu=*/3,
 250                     /*dealloc_cpu=*/4, /*Histogram=*/0, /*HistogramSize=*/0);
 251
 252   const auto Schema = llvm::memprof::getFullSchema();
 253   PortableMemInfoBlock WriteBlock(Info, Schema);
 254
 255   std::string Buffer;
 256   llvm::raw_string_ostream OS(Buffer);
 257   WriteBlock.serialize(Schema, OS);
 258
 259   PortableMemInfoBlock ReadBlock(
 260       Schema, reinterpret_cast<const unsigned char *>(Buffer.data()));
 261
 262   EXPECT_EQ(ReadBlock, WriteBlock);
 263   // Here we compare directly with the actual counts instead of MemInfoBlock
 264   // members. Since the MemInfoBlock struct is packed and the EXPECT_EQ macros
 265   // take a reference to the params, this results in unaligned accesses.
 266   EXPECT_EQ(1UL, ReadBlock.getAllocCount());
 267   EXPECT_EQ(7ULL, ReadBlock.getTotalAccessCount());
 268   EXPECT_EQ(3UL, ReadBlock.getAllocCpuId());
 269 }
 270
 271 TEST(MemProf, RecordSerializationRoundTripVersion1) {
 272   const auto Schema = llvm::memprof::getFullSchema();
 273
 274   MemInfoBlock Info(/*size=*/16, /*access_count=*/7, /*alloc_timestamp=*/1000,
 275                     /*dealloc_timestamp=*/2000, /*alloc_cpu=*/3,
 276                     /*dealloc_cpu=*/4, /*Histogram=*/0, /*HistogramSize=*/0);
 277
 278   llvm::SmallVector<llvm::SmallVector<FrameId>> AllocCallStacks = {
 279       {0x123, 0x345}, {0x123, 0x567}};
 280
 281   llvm::SmallVector<llvm::SmallVector<FrameId>> CallSites = {{0x333, 0x777}};
 282
 283   IndexedMemProfRecord Record;
 284   for (const auto &ACS : AllocCallStacks) {
 285     // Use the same info block for both allocation sites.
 286     Record.AllocSites.emplace_back(ACS, llvm::memprof::hashCallStack(ACS),
 287                                    Info);
 288   }
 289   Record.CallSites.assign(CallSites);
 290   for (const auto &CS : CallSites)
 291     Record.CallSiteIds.push_back(llvm::memprof::hashCallStack(CS));
 292
 293   std::string Buffer;
 294   llvm::raw_string_ostream OS(Buffer);
 295   Record.serialize(Schema, OS, llvm::memprof::Version1);
 296
 297   const IndexedMemProfRecord GotRecord = IndexedMemProfRecord::deserialize(
 298       Schema, reinterpret_cast<const unsigned char *>(Buffer.data()),
 299       llvm::memprof::Version1);
 300
 301   EXPECT_EQ(Record, GotRecord);
 302 }
 303
 304 TEST(MemProf, RecordSerializationRoundTripVerion2) {
 305   const auto Schema = llvm::memprof::getFullSchema();
 306
 307   MemInfoBlock Info(/*size=*/16, /*access_count=*/7, /*alloc_timestamp=*/1000,
 308                     /*dealloc_timestamp=*/2000, /*alloc_cpu=*/3,
 309                     /*dealloc_cpu=*/4, /*Histogram=*/0, /*HistogramSize=*/0);
 310
 311   llvm::SmallVector<llvm::memprof::CallStackId> CallStackIds = {0x123, 0x456};
 312
 313   llvm::SmallVector<llvm::memprof::CallStackId> CallSiteIds = {0x333, 0x444};
 314
 315   IndexedMemProfRecord Record;
 316   for (const auto &CSId : CallStackIds) {
 317     // Use the same info block for both allocation sites.
 318     Record.AllocSites.emplace_back(CSId, Info);
 319   }
 320   Record.CallSiteIds.assign(CallSiteIds);
 321
 322   std::string Buffer;
 323   llvm::raw_string_ostream OS(Buffer);
 324   Record.serialize(Schema, OS, llvm::memprof::Version2);
 325
 326   const IndexedMemProfRecord GotRecord = IndexedMemProfRecord::deserialize(
 327       Schema, reinterpret_cast<const unsigned char *>(Buffer.data()),
 328       llvm::memprof::Version2);
 329
 330   EXPECT_EQ(Record, GotRecord);
 331 }
 332
 333 TEST(MemProf, RecordSerializationRoundTripVersion2HotColdSchema) {
 334   const auto Schema = llvm::memprof::getHotColdSchema();
 335
 336   MemInfoBlock Info;
 337   Info.AllocCount = 11;
 338   Info.TotalSize = 22;
 339   Info.TotalLifetime = 33;
 340   Info.TotalLifetimeAccessDensity = 44;
 341
 342   llvm::SmallVector<llvm::memprof::CallStackId> CallStackIds = {0x123, 0x456};
 343
 344   llvm::SmallVector<llvm::memprof::CallStackId> CallSiteIds = {0x333, 0x444};
 345
 346   IndexedMemProfRecord Record;
 347   for (const auto &CSId : CallStackIds) {
 348     // Use the same info block for both allocation sites.
 349     Record.AllocSites.emplace_back(CSId, Info, Schema);
 350   }
 351   Record.CallSiteIds.assign(CallSiteIds);
 352
 353   std::bitset<llvm::to_underlying(Meta::Size)> SchemaBitSet;
 354   for (auto Id : Schema)
 355     SchemaBitSet.set(llvm::to_underlying(Id));
 356
 357   // Verify that SchemaBitSet has the fields we expect and nothing else, which
 358   // we check with count().
 359   EXPECT_EQ(SchemaBitSet.count(), 4U);
 360   EXPECT_TRUE(SchemaBitSet[llvm::to_underlying(Meta::AllocCount)]);
 361   EXPECT_TRUE(SchemaBitSet[llvm::to_underlying(Meta::TotalSize)]);
 362   EXPECT_TRUE(SchemaBitSet[llvm::to_underlying(Meta::TotalLifetime)]);
 363   EXPECT_TRUE(
 364       SchemaBitSet[llvm::to_underlying(Meta::TotalLifetimeAccessDensity)]);
 365
 366   // Verify that Schema has propagated all the way to the Info field in each
 367   // IndexedAllocationInfo.
 368   ASSERT_THAT(Record.AllocSites, ::SizeIs(2));
 369   EXPECT_EQ(Record.AllocSites[0].Info.getSchema(), SchemaBitSet);
 370   EXPECT_EQ(Record.AllocSites[1].Info.getSchema(), SchemaBitSet);
 371
 372   std::string Buffer;
 373   llvm::raw_string_ostream OS(Buffer);
 374   Record.serialize(Schema, OS, llvm::memprof::Version2);
 375
 376   const IndexedMemProfRecord GotRecord = IndexedMemProfRecord::deserialize(
 377       Schema, reinterpret_cast<const unsigned char *>(Buffer.data()),
 378       llvm::memprof::Version2);
 379
 380   // Verify that Schema comes back correctly after deserialization. Technically,
 381   // the comparison between Record and GotRecord below includes the comparison
 382   // of their Schemas, but we'll verify the Schemas on our own.
 383   ASSERT_THAT(GotRecord.AllocSites, ::SizeIs(2));
 384   EXPECT_EQ(GotRecord.AllocSites[0].Info.getSchema(), SchemaBitSet);
 385   EXPECT_EQ(GotRecord.AllocSites[1].Info.getSchema(), SchemaBitSet);
 386
 387   EXPECT_EQ(Record, GotRecord);
 388 }
 389
 390 TEST(MemProf, SymbolizationFilter) {
 391   std::unique_ptr<MockSymbolizer> Symbolizer(new MockSymbolizer());
 392
 393   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x1000},
 394                                                 specifier(), false))
 395       .Times(1) // once since we don't lookup invalid PCs repeatedly.
 396       .WillRepeatedly(Return(makeInliningInfo({
 397           {"malloc", 70, 57, 3, "memprof/memprof_malloc_linux.cpp"},
 398       })));
 399
 400   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x2000},
 401                                                 specifier(), false))
 402       .Times(1) // once since we don't lookup invalid PCs repeatedly.
 403       .WillRepeatedly(Return(makeInliningInfo({
 404           {"new", 70, 57, 3, "memprof/memprof_new_delete.cpp"},
 405       })));
 406
 407   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x3000},
 408                                                 specifier(), false))
 409       .Times(1) // once since we don't lookup invalid PCs repeatedly.
 410       .WillRepeatedly(Return(makeInliningInfo({
 411           {DILineInfo::BadString, 0, 0, 0},
 412       })));
 413
 414   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x4000},
 415                                                 specifier(), false))
 416       .Times(1)
 417       .WillRepeatedly(Return(makeInliningInfo({
 418           {"foo", 10, 5, 30, "memprof/memprof_test_file.cpp"},
 419       })));
 420
 421   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x5000},
 422                                                 specifier(), false))
 423       .Times(1)
 424       .WillRepeatedly(Return(makeInliningInfo({
 425           // Depending on how the runtime was compiled, only the filename
 426           // may be present in the debug information.
 427           {"malloc", 70, 57, 3, "memprof_malloc_linux.cpp"},
 428       })));
 429
 430   CallStackMap CSM;
 431   CSM[0x1] = {0x1000, 0x2000, 0x3000, 0x4000};
 432   // This entry should be dropped since all PCs are either not
 433   // symbolizable or belong to the runtime.
 434   CSM[0x2] = {0x1000, 0x2000, 0x5000};
 435
 436   llvm::MapVector<uint64_t, MemInfoBlock> Prof;
 437   Prof[0x1].AllocCount = 1;
 438   Prof[0x2].AllocCount = 1;
 439
 440   auto Seg = makeSegments();
 441
 442   RawMemProfReader Reader(std::move(Symbolizer), Seg, Prof, CSM);
 443
 444   llvm::SmallVector<MemProfRecord, 1> Records;
 445   for (const auto &KeyRecordPair : Reader) {
 446     Records.push_back(KeyRecordPair.second);
 447   }
 448
 449   ASSERT_THAT(Records, SizeIs(1));
 450   ASSERT_THAT(Records[0].AllocSites, SizeIs(1));
 451   ASSERT_THAT(Records[0].AllocSites[0].CallStack, SizeIs(1));
 452   EXPECT_THAT(Records[0].AllocSites[0].CallStack[0],
 453               FrameContains("foo", 5U, 30U, false));
 454 }
 455
 456 TEST(MemProf, BaseMemProfReader) {
 457   llvm::DenseMap<FrameId, Frame> FrameIdMap;
 458   Frame F1(/*Hash=*/IndexedMemProfRecord::getGUID("foo"), /*LineOffset=*/20,
 459            /*Column=*/5, /*IsInlineFrame=*/true);
 460   Frame F2(/*Hash=*/IndexedMemProfRecord::getGUID("bar"), /*LineOffset=*/10,
 461            /*Column=*/2, /*IsInlineFrame=*/false);
 462   FrameIdMap.insert({F1.hash(), F1});
 463   FrameIdMap.insert({F2.hash(), F2});
 464
 465   llvm::MapVector<llvm::GlobalValue::GUID, IndexedMemProfRecord> ProfData;
 466   IndexedMemProfRecord FakeRecord;
 467   MemInfoBlock Block;
 468   Block.AllocCount = 1U, Block.TotalAccessDensity = 4,
 469   Block.TotalLifetime = 200001;
 470   std::array<FrameId, 2> CallStack{F1.hash(), F2.hash()};
 471   FakeRecord.AllocSites.emplace_back(
 472       /*CS=*/CallStack, /*CSId=*/llvm::memprof::hashCallStack(CallStack),
 473       /*MB=*/Block);
 474   ProfData.insert({F1.hash(), FakeRecord});
 475
 476   MemProfReader Reader(FrameIdMap, ProfData);
 477
 478   llvm::SmallVector<MemProfRecord, 1> Records;
 479   for (const auto &KeyRecordPair : Reader) {
 480     Records.push_back(KeyRecordPair.second);
 481   }
 482
 483   ASSERT_THAT(Records, SizeIs(1));
 484   ASSERT_THAT(Records[0].AllocSites, SizeIs(1));
 485   ASSERT_THAT(Records[0].AllocSites[0].CallStack, SizeIs(2));
 486   EXPECT_THAT(Records[0].AllocSites[0].CallStack[0],
 487               FrameContains("foo", 20U, 5U, true));
 488   EXPECT_THAT(Records[0].AllocSites[0].CallStack[1],
 489               FrameContains("bar", 10U, 2U, false));
 490 }
 491
 492 TEST(MemProf, BaseMemProfReaderWithCSIdMap) {
 493   llvm::memprof::IndexedMemProfData MemProfData;
 494   Frame F1(/*Hash=*/IndexedMemProfRecord::getGUID("foo"), /*LineOffset=*/20,
 495            /*Column=*/5, /*IsInlineFrame=*/true);
 496   Frame F2(/*Hash=*/IndexedMemProfRecord::getGUID("bar"), /*LineOffset=*/10,
 497            /*Column=*/2, /*IsInlineFrame=*/false);
 498   MemProfData.Frames.insert({F1.hash(), F1});
 499   MemProfData.Frames.insert({F2.hash(), F2});
 500
 501   llvm::SmallVector<FrameId> CallStack = {F1.hash(), F2.hash()};
 502   CallStackId CSId = llvm::memprof::hashCallStack(CallStack);
 503   MemProfData.CallStacks.insert({CSId, CallStack});
 504
 505   IndexedMemProfRecord FakeRecord;
 506   MemInfoBlock Block;
 507   Block.AllocCount = 1U, Block.TotalAccessDensity = 4,
 508   Block.TotalLifetime = 200001;
 509   FakeRecord.AllocSites.emplace_back(
 510       /*CSId=*/llvm::memprof::hashCallStack(CallStack),
 511       /*MB=*/Block);
 512   MemProfData.Records.insert({F1.hash(), FakeRecord});
 513
 514   MemProfReader Reader(MemProfData);
 515
 516   llvm::SmallVector<MemProfRecord, 1> Records;
 517   for (const auto &KeyRecordPair : Reader) {
 518     Records.push_back(KeyRecordPair.second);
 519   }
 520
 521   ASSERT_THAT(Records, SizeIs(1));
 522   ASSERT_THAT(Records[0].AllocSites, SizeIs(1));
 523   ASSERT_THAT(Records[0].AllocSites[0].CallStack, SizeIs(2));
 524   EXPECT_THAT(Records[0].AllocSites[0].CallStack[0],
 525               FrameContains("foo", 20U, 5U, true));
 526   EXPECT_THAT(Records[0].AllocSites[0].CallStack[1],
 527               FrameContains("bar", 10U, 2U, false));
 528 }
 529
 530 TEST(MemProf, IndexedMemProfRecordToMemProfRecord) {
 531   // Verify that MemProfRecord can be constructed from IndexedMemProfRecord with
 532   // CallStackIds only.
 533
 534   llvm::DenseMap<FrameId, Frame> FrameIdMap;
 535   Frame F1(1, 0, 0, false);
 536   Frame F2(2, 0, 0, false);
 537   Frame F3(3, 0, 0, false);
 538   Frame F4(4, 0, 0, false);
 539   FrameIdMap.insert({F1.hash(), F1});
 540   FrameIdMap.insert({F2.hash(), F2});
 541   FrameIdMap.insert({F3.hash(), F3});
 542   FrameIdMap.insert({F4.hash(), F4});
 543
 544   llvm::DenseMap<CallStackId, llvm::SmallVector<FrameId>> CallStackIdMap;
 545   llvm::SmallVector<FrameId> CS1 = {F1.hash(), F2.hash()};
 546   llvm::SmallVector<FrameId> CS2 = {F1.hash(), F3.hash()};
 547   llvm::SmallVector<FrameId> CS3 = {F2.hash(), F3.hash()};
 548   llvm::SmallVector<FrameId> CS4 = {F2.hash(), F4.hash()};
 549   CallStackIdMap.insert({llvm::memprof::hashCallStack(CS1), CS1});
 550   CallStackIdMap.insert({llvm::memprof::hashCallStack(CS2), CS2});
 551   CallStackIdMap.insert({llvm::memprof::hashCallStack(CS3), CS3});
 552   CallStackIdMap.insert({llvm::memprof::hashCallStack(CS4), CS4});
 553
 554   IndexedMemProfRecord IndexedRecord;
 555   IndexedAllocationInfo AI;
 556   AI.CSId = llvm::memprof::hashCallStack(CS1);
 557   IndexedRecord.AllocSites.push_back(AI);
 558   AI.CSId = llvm::memprof::hashCallStack(CS2);
 559   IndexedRecord.AllocSites.push_back(AI);
 560   IndexedRecord.CallSiteIds.push_back(llvm::memprof::hashCallStack(CS3));
 561   IndexedRecord.CallSiteIds.push_back(llvm::memprof::hashCallStack(CS4));
 562
 563   llvm::memprof::FrameIdConverter<decltype(FrameIdMap)> FrameIdConv(FrameIdMap);
 564   llvm::memprof::CallStackIdConverter<decltype(CallStackIdMap)> CSIdConv(
 565       CallStackIdMap, FrameIdConv);
 566
 567   MemProfRecord Record = IndexedRecord.toMemProfRecord(CSIdConv);
 568
 569   // Make sure that all lookups are successful.
 570   ASSERT_EQ(FrameIdConv.LastUnmappedId, std::nullopt);
 571   ASSERT_EQ(CSIdConv.LastUnmappedId, std::nullopt);
 572
 573   // Verify the contents of Record.
 574   ASSERT_THAT(Record.AllocSites, SizeIs(2));
 575   ASSERT_THAT(Record.AllocSites[0].CallStack, SizeIs(2));
 576   EXPECT_EQ(Record.AllocSites[0].CallStack[0].hash(), F1.hash());
 577   EXPECT_EQ(Record.AllocSites[0].CallStack[1].hash(), F2.hash());
 578   ASSERT_THAT(Record.AllocSites[1].CallStack, SizeIs(2));
 579   EXPECT_EQ(Record.AllocSites[1].CallStack[0].hash(), F1.hash());
 580   EXPECT_EQ(Record.AllocSites[1].CallStack[1].hash(), F3.hash());
 581   ASSERT_THAT(Record.CallSites, SizeIs(2));
 582   ASSERT_THAT(Record.CallSites[0], SizeIs(2));
 583   EXPECT_EQ(Record.CallSites[0][0].hash(), F2.hash());
 584   EXPECT_EQ(Record.CallSites[0][1].hash(), F3.hash());
 585   ASSERT_THAT(Record.CallSites[1], SizeIs(2));
 586   EXPECT_EQ(Record.CallSites[1][0].hash(), F2.hash());
 587   EXPECT_EQ(Record.CallSites[1][1].hash(), F4.hash());
 588 }
 589
 590 using FrameIdMapTy =
 591     llvm::DenseMap<::llvm::memprof::FrameId, ::llvm::memprof::Frame>;
 592 using CallStackIdMapTy =
 593     llvm::DenseMap<::llvm::memprof::CallStackId,
 594                    ::llvm::SmallVector<::llvm::memprof::FrameId>>;
 595
 596 // Populate those fields returned by getHotColdSchema.
 597 MemInfoBlock makePartialMIB() {
 598   MemInfoBlock MIB;
 599   MIB.AllocCount = 1;
 600   MIB.TotalSize = 5;
 601   MIB.TotalLifetime = 10;
 602   MIB.TotalLifetimeAccessDensity = 23;
 603   return MIB;
 604 }
 605
 606 TEST(MemProf, MissingCallStackId) {
 607   // Use a non-existent CallStackId to trigger a mapping error in
 608   // toMemProfRecord.
 609   llvm::memprof::IndexedAllocationInfo AI(0xdeadbeefU, makePartialMIB(),
 610                                           llvm::memprof::getHotColdSchema());
 611
 612   IndexedMemProfRecord IndexedMR;
 613   IndexedMR.AllocSites.push_back(AI);
 614
 615   // Create empty maps.
 616   const FrameIdMapTy IdToFrameMap;
 617   const CallStackIdMapTy CSIdToCallStackMap;
 618   llvm::memprof::FrameIdConverter<decltype(IdToFrameMap)> FrameIdConv(
 619       IdToFrameMap);
 620   llvm::memprof::CallStackIdConverter<decltype(CSIdToCallStackMap)> CSIdConv(
 621       CSIdToCallStackMap, FrameIdConv);
 622
 623   // We are only interested in errors, not the return value.
 624   (void)IndexedMR.toMemProfRecord(CSIdConv);
 625
 626   ASSERT_TRUE(CSIdConv.LastUnmappedId.has_value());
 627   EXPECT_EQ(*CSIdConv.LastUnmappedId, 0xdeadbeefU);
 628   EXPECT_EQ(FrameIdConv.LastUnmappedId, std::nullopt);
 629 }
 630
 631 TEST(MemProf, MissingFrameId) {
 632   llvm::memprof::IndexedAllocationInfo AI(0x222, makePartialMIB(),
 633                                           llvm::memprof::getHotColdSchema());
 634
 635   IndexedMemProfRecord IndexedMR;
 636   IndexedMR.AllocSites.push_back(AI);
 637
 638   // An empty map to trigger a mapping error.
 639   const FrameIdMapTy IdToFrameMap;
 640   CallStackIdMapTy CSIdToCallStackMap;
 641   CSIdToCallStackMap.insert({0x222, {2, 3}});
 642
 643   llvm::memprof::FrameIdConverter<decltype(IdToFrameMap)> FrameIdConv(
 644       IdToFrameMap);
 645   llvm::memprof::CallStackIdConverter<decltype(CSIdToCallStackMap)> CSIdConv(
 646       CSIdToCallStackMap, FrameIdConv);
 647
 648   // We are only interested in errors, not the return value.
 649   (void)IndexedMR.toMemProfRecord(CSIdConv);
 650
 651   EXPECT_EQ(CSIdConv.LastUnmappedId, std::nullopt);
 652   ASSERT_TRUE(FrameIdConv.LastUnmappedId.has_value());
 653   EXPECT_EQ(*FrameIdConv.LastUnmappedId, 3U);
 654 }
 655
 656 // Verify CallStackRadixTreeBuilder can handle empty inputs.
 657 TEST(MemProf, RadixTreeBuilderEmpty) {
 658   llvm::DenseMap<FrameId, llvm::memprof::LinearFrameId> MemProfFrameIndexes;
 659   llvm::MapVector<CallStackId, llvm::SmallVector<FrameId>> MemProfCallStackData;
 660   llvm::DenseMap<llvm::memprof::FrameId, llvm::memprof::FrameStat>
 661       FrameHistogram =
 662           llvm::memprof::computeFrameHistogram(MemProfCallStackData);
 663   llvm::memprof::CallStackRadixTreeBuilder Builder;
 664   Builder.build(std::move(MemProfCallStackData), MemProfFrameIndexes,
 665                 FrameHistogram);
 666   ASSERT_THAT(Builder.getRadixArray(), testing::IsEmpty());
 667   const auto Mappings = Builder.takeCallStackPos();
 668   ASSERT_THAT(Mappings, testing::IsEmpty());
 669 }
 670
 671 // Verify CallStackRadixTreeBuilder can handle one trivial call stack.
 672 TEST(MemProf, RadixTreeBuilderOne) {
 673   llvm::DenseMap<FrameId, llvm::memprof::LinearFrameId> MemProfFrameIndexes = {
 674       {11, 1}, {12, 2}, {13, 3}};
 675   llvm::SmallVector<llvm::memprof::FrameId> CS1 = {13, 12, 11};
 676   llvm::MapVector<CallStackId, llvm::SmallVector<FrameId>> MemProfCallStackData;
 677   MemProfCallStackData.insert({llvm::memprof::hashCallStack(CS1), CS1});
 678   llvm::DenseMap<llvm::memprof::FrameId, llvm::memprof::FrameStat>
 679       FrameHistogram =
 680           llvm::memprof::computeFrameHistogram(MemProfCallStackData);
 681   llvm::memprof::CallStackRadixTreeBuilder Builder;
 682   Builder.build(std::move(MemProfCallStackData), MemProfFrameIndexes,
 683                 FrameHistogram);
 684   EXPECT_THAT(Builder.getRadixArray(), testing::ElementsAreArray({
 685                                            3U, // Size of CS1,
 686                                            3U, // MemProfFrameIndexes[13]
 687                                            2U, // MemProfFrameIndexes[12]
 688                                            1U  // MemProfFrameIndexes[11]
 689                                        }));
 690   const auto Mappings = Builder.takeCallStackPos();
 691   ASSERT_THAT(Mappings, SizeIs(1));
 692   EXPECT_THAT(Mappings, testing::Contains(testing::Pair(
 693                             llvm::memprof::hashCallStack(CS1), 0U)));
 694 }
 695
 696 // Verify CallStackRadixTreeBuilder can form a link between two call stacks.
 697 TEST(MemProf, RadixTreeBuilderTwo) {
 698   llvm::DenseMap<FrameId, llvm::memprof::LinearFrameId> MemProfFrameIndexes = {
 699       {11, 1}, {12, 2}, {13, 3}};
 700   llvm::SmallVector<llvm::memprof::FrameId> CS1 = {12, 11};
 701   llvm::SmallVector<llvm::memprof::FrameId> CS2 = {13, 12, 11};
 702   llvm::MapVector<CallStackId, llvm::SmallVector<FrameId>> MemProfCallStackData;
 703   MemProfCallStackData.insert({llvm::memprof::hashCallStack(CS1), CS1});
 704   MemProfCallStackData.insert({llvm::memprof::hashCallStack(CS2), CS2});
 705   llvm::DenseMap<llvm::memprof::FrameId, llvm::memprof::FrameStat>
 706       FrameHistogram =
 707           llvm::memprof::computeFrameHistogram(MemProfCallStackData);
 708   llvm::memprof::CallStackRadixTreeBuilder Builder;
 709   Builder.build(std::move(MemProfCallStackData), MemProfFrameIndexes,
 710                 FrameHistogram);
 711   EXPECT_THAT(Builder.getRadixArray(),
 712               testing::ElementsAreArray({
 713                   2U,                        // Size of CS1
 714                   static_cast<uint32_t>(-3), // Jump 3 steps
 715                   3U,                        // Size of CS2
 716                   3U,                        // MemProfFrameIndexes[13]
 717                   2U,                        // MemProfFrameIndexes[12]
 718                   1U                         // MemProfFrameIndexes[11]
 719               }));
 720   const auto Mappings = Builder.takeCallStackPos();
 721   ASSERT_THAT(Mappings, SizeIs(2));
 722   EXPECT_THAT(Mappings, testing::Contains(testing::Pair(
 723                             llvm::memprof::hashCallStack(CS1), 0U)));
 724   EXPECT_THAT(Mappings, testing::Contains(testing::Pair(
 725                             llvm::memprof::hashCallStack(CS2), 2U)));
 726 }
 727
 728 // Verify CallStackRadixTreeBuilder can form a jump to a prefix that itself has
 729 // another jump to another prefix.
 730 TEST(MemProf, RadixTreeBuilderSuccessiveJumps) {
 731   llvm::DenseMap<FrameId, llvm::memprof::LinearFrameId> MemProfFrameIndexes = {
 732       {11, 1}, {12, 2}, {13, 3}, {14, 4}, {15, 5}, {16, 6}, {17, 7}, {18, 8},
 733   };
 734   llvm::SmallVector<llvm::memprof::FrameId> CS1 = {14, 13, 12, 11};
 735   llvm::SmallVector<llvm::memprof::FrameId> CS2 = {15, 13, 12, 11};
 736   llvm::SmallVector<llvm::memprof::FrameId> CS3 = {17, 16, 12, 11};
 737   llvm::SmallVector<llvm::memprof::FrameId> CS4 = {18, 16, 12, 11};
 738   llvm::MapVector<CallStackId, llvm::SmallVector<FrameId>> MemProfCallStackData;
 739   MemProfCallStackData.insert({llvm::memprof::hashCallStack(CS1), CS1});
 740   MemProfCallStackData.insert({llvm::memprof::hashCallStack(CS2), CS2});
 741   MemProfCallStackData.insert({llvm::memprof::hashCallStack(CS3), CS3});
 742   MemProfCallStackData.insert({llvm::memprof::hashCallStack(CS4), CS4});
 743   llvm::DenseMap<llvm::memprof::FrameId, llvm::memprof::FrameStat>
 744       FrameHistogram =
 745           llvm::memprof::computeFrameHistogram(MemProfCallStackData);
 746   llvm::memprof::CallStackRadixTreeBuilder Builder;
 747   Builder.build(std::move(MemProfCallStackData), MemProfFrameIndexes,
 748                 FrameHistogram);
 749   EXPECT_THAT(Builder.getRadixArray(),
 750               testing::ElementsAreArray({
 751                   4U,                        // Size of CS1
 752                   4U,                        // MemProfFrameIndexes[14]
 753                   static_cast<uint32_t>(-3), // Jump 3 steps
 754                   4U,                        // Size of CS2
 755                   5U,                        // MemProfFrameIndexes[15]
 756                   3U,                        // MemProfFrameIndexes[13]
 757                   static_cast<uint32_t>(-7), // Jump 7 steps
 758                   4U,                        // Size of CS3
 759                   7U,                        // MemProfFrameIndexes[17]
 760                   static_cast<uint32_t>(-3), // Jump 3 steps
 761                   4U,                        // Size of CS4
 762                   8U,                        // MemProfFrameIndexes[18]
 763                   6U,                        // MemProfFrameIndexes[16]
 764                   2U,                        // MemProfFrameIndexes[12]
 765                   1U                         // MemProfFrameIndexes[11]
 766               }));
 767   const auto Mappings = Builder.takeCallStackPos();
 768   ASSERT_THAT(Mappings, SizeIs(4));
 769   EXPECT_THAT(Mappings, testing::Contains(testing::Pair(
 770                             llvm::memprof::hashCallStack(CS1), 0U)));
 771   EXPECT_THAT(Mappings, testing::Contains(testing::Pair(
 772                             llvm::memprof::hashCallStack(CS2), 3U)));
 773   EXPECT_THAT(Mappings, testing::Contains(testing::Pair(
 774                             llvm::memprof::hashCallStack(CS3), 7U)));
 775   EXPECT_THAT(Mappings, testing::Contains(testing::Pair(
 776                             llvm::memprof::hashCallStack(CS4), 10U)));
 777 }
 778 } // namespace