Index: compiler-rt/lib/fuzzer/FuzzerLoop.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerLoop.cpp +++ compiler-rt/lib/fuzzer/FuzzerLoop.cpp @@ -150,7 +150,7 @@ TPC.SetUseValueProfileMask(Options.UseValueProfile); if (Options.Verbosity) - TPC.PrintModuleInfo(); + TPC.PrintModuleSummary(); if (!Options.OutputCorpus.empty() && Options.ReloadIntervalSec) EpochOfLastReadOfOutputCorpus = GetEpoch(Options.OutputCorpus); MaxInputLen = MaxMutationLen = Options.MaxLen; @@ -511,9 +511,9 @@ UniqFeatureSetTmp.clear(); size_t FoundUniqFeaturesOfII = 0; size_t NumUpdatesBefore = Corpus.NumFeatureUpdates(); - TPC.CollectFeatures([&](uint32_t Feature) { + TPC.CollectFeatures([&](size_t Feature) { if (Corpus.AddFeature(Feature, static_cast(Size), Options.Shrink)) - UniqFeatureSetTmp.push_back(Feature); + UniqFeatureSetTmp.push_back(static_cast(Feature)); if (Options.Entropic) Corpus.UpdateFeatureFrequency(II, Feature); if (Options.ReduceInputs && II && !II->NeverReduce) Index: compiler-rt/lib/fuzzer/FuzzerTracePC.h =================================================================== --- compiler-rt/lib/fuzzer/FuzzerTracePC.h +++ compiler-rt/lib/fuzzer/FuzzerTracePC.h @@ -67,10 +67,38 @@ } }; +struct ModuleInfo { + // SimpleHash of the relative PCs offsets and flags. For a PC table like + // `TracePC::PCTableEntry PCs[]`, the relative offset of `PCs[i]` is + // `PCs[i] - PCs[0]`. The hash for a particular module is position- + // independent, but is not collision-resistant. + uint64_t Hash = 0; + + // [FirstFeature, LastFeature) is the range of features as converted from the + // associated module's counters by TracePC. See also TracePC::CollectFeatures. + size_t FirstFeature = 0; + size_t LastFeature = 0; + + // [FirstIdx, LastIdx) is the range of indices into the PC tables for the + // associated module. + uintptr_t FirstIdx = 0; + uintptr_t LastIdx = 0; + + // Index into TracePC's ModulePCTable array. TracePC treats a ModuleInfo + // struct with an offset greater than the length of the array as + // uninitialized. + size_t PCTableOffset = std::numeric_limits::max(); +}; + class TracePC { - public: +public: void HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop); + void HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop, + size_t ModuleOffset); void HandlePCsInit(const uintptr_t *Start, const uintptr_t *Stop); + void HandlePCsInit(const uintptr_t *Start, const uintptr_t *Stop, + uint64_t Hash); + void HandleCallerCallee(uintptr_t Caller, uintptr_t Callee); template void HandleCmp(uintptr_t PC, T Arg1, T Arg2); size_t GetTotalPCCoverage(); @@ -92,7 +120,7 @@ void UpdateFeatureSet(size_t CurrentElementIdx, size_t CurrentElementSize); void PrintFeatureSet(); - void PrintModuleInfo(); + void PrintModuleSummary(); void PrintCoverage(bool PrintAllCounters); @@ -110,6 +138,10 @@ void RecordInitialStack(); uintptr_t GetMaxStackOffset() const; + // Step function, grows similar to 8 * Log_2(A). + static size_t StackDepthStepFunction(uintptr_t A); + static const size_t kMaxStackDepthFeature = 512; + template void ForEachObservedPC(CallBack CB) { for (auto PC : ObservedPCs) @@ -125,9 +157,17 @@ uintptr_t PCTableEntryIdx(const PCTableEntry *TE); const PCTableEntry *PCTableEntryByIdx(uintptr_t Idx); + const PCTableEntry *PCTableEntryByModule(uint64_t Hash, uintptr_t Offset); static uintptr_t GetNextInstructionPc(uintptr_t PC); bool PcIsFuncEntry(const PCTableEntry *TE) { return TE->PCFlags & 1; } + bool ModuleInfoByHash(uint64_t Hash, ModuleInfo *Info); + bool ModuleInfoByFeature(size_t Feature, ModuleInfo *Info); + bool ModuleInfoByIdx(uintptr_t Idx, ModuleInfo *Info); + + // Calculate hash of the relative PC offsets and flags. + static uint64_t HashPCs(const uintptr_t *Start, const uintptr_t *End); + private: bool UseCounters = false; uint32_t UseValueProfileMask = false; @@ -140,14 +180,13 @@ struct Module { struct Region { uint8_t *Start, *Stop; - bool Enabled; - bool OneFullPage; + size_t Size() const { return Stop - Start; } }; Region *Regions; size_t NumRegions; - uint8_t *Start() { return Regions[0].Start; } - uint8_t *Stop() { return Regions[NumRegions - 1].Stop; } - size_t Size() { return Stop() - Start(); } + uint8_t *Start() const { return Regions[0].Start; } + uint8_t *Stop() const { return Regions[NumRegions - 1].Stop; } + size_t Size() const { return Stop() - Start(); } size_t Idx(uint8_t *P) { assert(P >= Start() && P < Stop()); return P - Start(); @@ -165,7 +204,19 @@ CB(Modules[m].Regions[r]); } - struct { const PCTableEntry *Start, *Stop; } ModulePCTable[4096]; + // If |Info| represents a module other than the last one in the array, this + // method will update |Info| to represent the next module in the array and + // return true. Otherwise, if |Info| is the last module or invalid, it will + // update |Info| to represent the first module in the array and return false. + // A series of calls to |NextModuleInfo| can be used to iterate over the + // |Modules| array. + bool NextModuleInfo(ModuleInfo *Info); + + struct { + const PCTableEntry *Start, *Stop; + uint64_t Hash; + size_t Size() const { return Stop - Start; } + } ModulePCTable[4096]; size_t NumPCTables; size_t NumPCsInPCTables; @@ -234,58 +285,37 @@ return Bit; } -template // void Callback(uint32_t Feature) +template // void Callback(size_t Feature) ATTRIBUTE_NO_SANITIZE_ADDRESS ATTRIBUTE_NOINLINE size_t TracePC::CollectFeatures(Callback HandleFeature) const { auto Handle8bitCounter = [&](size_t FirstFeature, size_t Idx, uint8_t Counter) { if (UseCounters) - HandleFeature(static_cast(FirstFeature + Idx * 8 + - CounterToFeature(Counter))); + HandleFeature(FirstFeature + Idx * 8 + CounterToFeature(Counter)); else - HandleFeature(static_cast(FirstFeature + Idx)); + HandleFeature(FirstFeature + Idx); }; size_t FirstFeature = 0; - - for (size_t i = 0; i < NumModules; i++) { - for (size_t r = 0; r < Modules[i].NumRegions; r++) { - if (!Modules[i].Regions[r].Enabled) continue; + for (size_t i = 0; i < NumModules; i++) + for (size_t r = 0; r < Modules[i].NumRegions; r++) FirstFeature += 8 * ForEachNonZeroByte(Modules[i].Regions[r].Start, Modules[i].Regions[r].Stop, FirstFeature, Handle8bitCounter); - } - } FirstFeature += 8 * ForEachNonZeroByte(ExtraCountersBegin(), ExtraCountersEnd(), FirstFeature, Handle8bitCounter); if (UseValueProfileMask) { - ValueProfileMap.ForEach([&](size_t Idx) { - HandleFeature(static_cast(FirstFeature + Idx)); - }); + ValueProfileMap.ForEach( + [&](size_t Idx) { HandleFeature(FirstFeature + Idx); }); FirstFeature += ValueProfileMap.SizeInBits(); } - // Step function, grows similar to 8 * Log_2(A). - auto StackDepthStepFunction = [](size_t A) -> size_t { - if (!A) - return A; - auto Log2 = Log(A); - if (Log2 < 3) - return A; - Log2 -= 3; - return (Log2 + 1) * 8 + ((A >> Log2) & 7); - }; - assert(StackDepthStepFunction(1024) == 64); - assert(StackDepthStepFunction(1024 * 4) == 80); - assert(StackDepthStepFunction(1024 * 1024) == 144); - if (auto MaxStackOffset = GetMaxStackOffset()) { - HandleFeature(static_cast( - FirstFeature + StackDepthStepFunction(MaxStackOffset / 8))); - FirstFeature += StackDepthStepFunction(std::numeric_limits::max()); + HandleFeature(FirstFeature + StackDepthStepFunction(MaxStackOffset / 8)); + FirstFeature += kMaxStackDepthFeature; } return FirstFeature; Index: compiler-rt/lib/fuzzer/FuzzerTracePC.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerTracePC.cpp +++ compiler-rt/lib/fuzzer/FuzzerTracePC.cpp @@ -29,55 +29,60 @@ namespace fuzzer { +const size_t TracePC::kMaxStackDepthFeature; + TracePC TPC; size_t TracePC::GetTotalPCCoverage() { return ObservedPCs.size(); } - void TracePC::HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop) { - if (Start == Stop) return; - if (NumModules && - Modules[NumModules - 1].Start() == Start) + if (Start == Stop) return; - assert(NumModules < - sizeof(Modules) / sizeof(Modules[0])); - auto &M = Modules[NumModules++]; - uint8_t *AlignedStart = RoundUpByPage(Start); - uint8_t *AlignedStop = RoundDownByPage(Stop); - size_t NumFullPages = AlignedStop > AlignedStart ? - (AlignedStop - AlignedStart) / PageSize() : 0; - bool NeedFirst = Start < AlignedStart || !NumFullPages; - bool NeedLast = Stop > AlignedStop && AlignedStop >= AlignedStart; - M.NumRegions = NumFullPages + NeedFirst + NeedLast;; - assert(M.NumRegions > 0); + if (NumModules && Modules[NumModules - 1].Start() == Start) + return; + assert(NumModules < sizeof(Modules) / sizeof(Modules[0])); + HandleInline8bitCountersInit(Start, Stop, NumModules++); + NumInline8bitCounters += Modules[NumModules - 1].Size(); +} + +void TracePC::HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop, + size_t ModuleOffset) { + assert(Start < Stop); + assert(ModuleOffset < NumModules); + auto &M = Modules[ModuleOffset]; + assert(ModuleOffset == NumModules - 1 || + (M.Size() == static_cast(Stop - Start))); + uint8_t *FirstPage = RoundDownByPage(Start); + M.NumRegions = (RoundUpByPage(Stop) - FirstPage) / PageSize(); M.Regions = new Module::Region[M.NumRegions]; - assert(M.Regions); - size_t R = 0; - if (NeedFirst) - M.Regions[R++] = {Start, std::min(Stop, AlignedStart), true, false}; - for (uint8_t *P = AlignedStart; P < AlignedStop; P += PageSize()) - M.Regions[R++] = {P, P + PageSize(), true, true}; - if (NeedLast) - M.Regions[R++] = {AlignedStop, Stop, true, false}; - assert(R == M.NumRegions); - assert(M.Size() == (size_t)(Stop - Start)); - assert(M.Stop() == Stop); - assert(M.Start() == Start); - NumInline8bitCounters += M.Size(); + uint8_t *Curr = Start; + uint8_t *Next = FirstPage + PageSize(); + for (size_t R = 0; R < M.NumRegions - 1; ++R) { + M.Regions[R] = {Curr, Next}; + Curr = Next; + Next += PageSize(); + } + M.Regions[M.NumRegions - 1] = {Curr, Stop}; } void TracePC::HandlePCsInit(const uintptr_t *Start, const uintptr_t *Stop) { + uint64_t Hash = TracePC::HashPCs(Start, Stop); + HandlePCsInit(Start, Stop, Hash); +} + +void TracePC::HandlePCsInit(const uintptr_t *Start, const uintptr_t *Stop, + uint64_t Hash) { const PCTableEntry *B = reinterpret_cast(Start); const PCTableEntry *E = reinterpret_cast(Stop); if (NumPCTables && ModulePCTable[NumPCTables - 1].Start == B) return; assert(NumPCTables < sizeof(ModulePCTable) / sizeof(ModulePCTable[0])); - ModulePCTable[NumPCTables++] = {B, E}; + ModulePCTable[NumPCTables++] = {B, E, Hash}; NumPCsInPCTables += E - B; } -void TracePC::PrintModuleInfo() { +void TracePC::PrintModuleSummary() { if (NumModules) { Printf("INFO: Loaded %zd modules (%zd inline 8-bit counters): ", NumModules, NumInline8bitCounters); @@ -89,10 +94,9 @@ if (NumPCTables) { Printf("INFO: Loaded %zd PC tables (%zd PCs): ", NumPCTables, NumPCsInPCTables); - for (size_t i = 0; i < NumPCTables; i++) { - Printf("%zd [%p,%p), ", ModulePCTable[i].Stop - ModulePCTable[i].Start, - ModulePCTable[i].Start, ModulePCTable[i].Stop); - } + for (size_t i = 0; i < NumPCTables; i++) + Printf("%zd [%p,%p), ", ModulePCTable[i].Size(), ModulePCTable[i].Start, + ModulePCTable[i].Stop); Printf("\n"); if (NumInline8bitCounters && NumInline8bitCounters != NumPCsInPCTables) { @@ -104,10 +108,11 @@ _Exit(1); } } - if (size_t NumExtraCounters = ExtraCountersEnd() - ExtraCountersBegin()) + size_t NumExtraCounters = ExtraCountersEnd() - ExtraCountersBegin(); + if (NumExtraCounters) Printf("INFO: %zd Extra Counters\n", NumExtraCounters); - size_t MaxFeatures = CollectFeatures([](uint32_t) {}); + size_t MaxFeatures = CollectFeatures([](size_t) {}); if (MaxFeatures > std::numeric_limits::max()) Printf("WARNING: The coverage PC tables may produce up to %zu features.\n" "This exceeds the maximum 32-bit value. Some features may be\n" @@ -177,11 +182,9 @@ if (NumInline8bitCounters == NumPCsInPCTables) { for (size_t i = 0; i < NumModules; i++) { auto &M = Modules[i]; - assert(M.Size() == - (size_t)(ModulePCTable[i].Stop - ModulePCTable[i].Start)); + assert(M.Size() == ModulePCTable[i].Size()); for (size_t r = 0; r < M.NumRegions; r++) { auto &R = M.Regions[r]; - if (!R.Enabled) continue; for (uint8_t *P = R.Start; P < R.Stop; P++) if (*P) Observe(&ModulePCTable[i].Start[M.Idx(P)]); @@ -204,7 +207,7 @@ auto &M = ModulePCTable[i]; if (TE >= M.Start && TE < M.Stop) return TotalTEs + TE - M.Start; - TotalTEs += M.Stop - M.Start; + TotalTEs += M.Size(); } assert(0); return 0; @@ -213,13 +216,87 @@ const TracePC::PCTableEntry *TracePC::PCTableEntryByIdx(uintptr_t Idx) { for (size_t i = 0; i < NumPCTables; i++) { auto &M = ModulePCTable[i]; - size_t Size = M.Stop - M.Start; + size_t Size = M.Size(); if (Idx < Size) return &M.Start[Idx]; Idx -= Size; } return nullptr; } +const TracePC::PCTableEntry *TracePC::PCTableEntryByModule(uint64_t Hash, + uintptr_t Offset) { + for (size_t i = 0; i < NumPCTables; i++) { + auto &M = ModulePCTable[i]; + if (Hash == M.Hash && Offset < M.Size()) + return &M.Start[Offset]; + } + return nullptr; +} + +uint64_t TracePC::HashPCs(const uintptr_t *Start, const uintptr_t *End) { + const PCTableEntry *B = reinterpret_cast(Start); + const PCTableEntry *E = reinterpret_cast(End); + assert(B < E); + PCTableEntry Delta = {0, B->PCFlags}; + uint64_t Hash = SimpleFastHash(&Delta, sizeof(Delta)); + for (const PCTableEntry *TE = B + 1; TE < E; ++TE) { + Delta = {TE->PC - B->PC, TE->PCFlags}; + Hash = SimpleFastHash(&Delta, sizeof(Delta), Hash); + } + return Hash; +} + +bool TracePC::NextModuleInfo(ModuleInfo *Info) { + assert(NumModules == NumPCTables); + // Use an invalid offset as an indicator of the first iteration. + if (Info->PCTableOffset < NumPCTables) { + Info->FirstFeature = Info->LastFeature; + Info->FirstIdx = Info->LastIdx; + Info->PCTableOffset++; + } else { + Info->FirstFeature = 0; + Info->FirstIdx = 0; + Info->PCTableOffset = 0; + } + if (Info->PCTableOffset >= NumPCTables) { + Info->Hash = 0; + Info->LastFeature = std::numeric_limits::max(); + Info->LastIdx = std::numeric_limits::max(); + return false; + } + const auto &PCTable = ModulePCTable[Info->PCTableOffset]; + const auto &Counters = Modules[Info->PCTableOffset]; + Info->Hash = PCTable.Hash; + // See CollectCoverage; there are up to 8 features per counter. + Info->LastFeature = Info->FirstFeature + (Counters.Size() * 8); + Info->LastIdx = Info->FirstIdx + PCTable.Size(); + return true; +} + +bool TracePC::ModuleInfoByHash(uint64_t Hash, ModuleInfo *Info) { + Info->PCTableOffset = NumPCTables; + while (NextModuleInfo(Info)) + if (Hash == Info->Hash) + return true; + return false; +} + +bool TracePC::ModuleInfoByFeature(size_t Feature, ModuleInfo *Info) { + Info->PCTableOffset = NumPCTables; + while (NextModuleInfo(Info)) + if (Feature < Info->LastFeature) + return true; + return false; +} + +bool TracePC::ModuleInfoByIdx(uintptr_t Idx, ModuleInfo *Info) { + Info->PCTableOffset = NumPCTables; + while (NextModuleInfo(Info)) + if (Idx < Info->LastIdx) + return true; + return false; +} + static std::string GetModuleName(uintptr_t PC) { char ModulePathRaw[4096] = ""; // What's PATH_MAX in portable C++? void *OffsetRaw = nullptr; @@ -256,7 +333,7 @@ return; for (size_t M = 0; M < NumModules; M++) { auto &PCTE = ModulePCTable[M]; - size_t N = PCTE.Stop - PCTE.Start; + size_t N = PCTE.Size(); for (size_t I = 0; I < N; I++) { if (!(PcIsFuncEntry(&PCTE.Start[I]))) continue; // not a function entry. auto Name = DescribePC("%F", GetNextInstructionPc(PCTE.Start[I].PC)); @@ -406,10 +483,8 @@ } void TracePC::ClearInlineCounters() { - IterateCounterRegions([](const Module::Region &R){ - if (R.Enabled) - memset(R.Start, 0, R.Stop - R.Start); - }); + IterateCounterRegions( + [](const Module::Region &R) { memset(R.Start, 0, R.Size()); }); } ATTRIBUTE_NO_SANITIZE_ALL @@ -422,6 +497,16 @@ return InitialStack - __sancov_lowest_stack; // Stack grows down } +size_t TracePC::StackDepthStepFunction(uintptr_t A) { + if (!A) + return A; + uint32_t Log2 = Log(A); + if (Log2 < 3) + return A; + Log2 -= 3; + return (Log2 + 1) * 8 + ((A >> Log2) & 7); +} + void WarnAboutDeprecatedInstrumentation(const char *flag) { // Use RawPrint because Printf cannot be used on Windows before OutputFile is // initialized. Index: compiler-rt/lib/fuzzer/tests/CMakeLists.txt =================================================================== --- compiler-rt/lib/fuzzer/tests/CMakeLists.txt +++ compiler-rt/lib/fuzzer/tests/CMakeLists.txt @@ -73,7 +73,7 @@ FuzzerUnitTests "Fuzzer-${arch}-Test" ${arch} SOURCES FuzzerUnittest.cpp ${COMPILER_RT_GTEST_SOURCE} RUNTIME ${LIBFUZZER_TEST_RUNTIME} - DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS} + DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS} FuzzerTestUtil.h CFLAGS ${LIBFUZZER_UNITTEST_CFLAGS} ${LIBFUZZER_TEST_RUNTIME_CFLAGS} LINK_FLAGS ${LIBFUZZER_UNITTEST_LINK_FLAGS} ${LIBFUZZER_TEST_RUNTIME_LINK_FLAGS}) set_target_properties(FuzzerUnitTests PROPERTIES Index: compiler-rt/lib/fuzzer/tests/FuzzerTestUtil.h =================================================================== --- /dev/null +++ compiler-rt/lib/fuzzer/tests/FuzzerTestUtil.h @@ -0,0 +1,92 @@ +//===- FuzzerTestUtil.h -----------------------------------------*- C++ -* ===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// Test support shared between unit tests. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_FUZZER_TEST_UTIL_H +#define LLVM_FUZZER_TEST_UTIL_H + +#include "FuzzerTracePC.h" +#include "gtest/gtest.h" +#include +#include +#include +#include +#include + +namespace fuzzer { + +// Helper environment to ensure that: +// * The PRNG is seeded deterministically. +class TestEnvironment : public testing::Environment { +public: + void SetUp() override { srand(0); } +}; + +// Test utilities for picking repeatable psuedorandom numbers. +template +typename std::enable_if::value, T>::type Pick() { + return static_cast(rand() & std::numeric_limits::max()); +} + +template +typename std::enable_if::value, T>::type Pick() { + auto AbsVal = static_cast(rand()) / static_cast(RAND_MAX); + return rand() % 2 ? -AbsVal : AbsVal; +} + +// Helper struct for creating coverage data for unit tests. Note that once +// memory is added to the |fuzzer::TracePC| singleton, that object will assume +// it is valid for its lifetime, i.e. the remainder of the process. This can +// cause issues if unit tests are repeated, i.e. -gtest_repeat=. Avoid this +// by declaring the FakeModule static within the test that adds it to the +// coverage. +template struct FakeModule final { +public: + uint8_t Counters[N]; + uintptr_t PCs[N * 2]; + const size_t NumPCs = N; + + FakeModule() { + memset(Counters, 0, sizeof(Counters)); + auto *TE = GetPCTableEntries(); + uintptr_t PC = Pick() & ((1ULL << 48) - 1); + for (size_t i = 0; i < N; ++i) { + TE[i].PC = PC; + TE[i].PCFlags = i == 0 || (rand() % 16) == 0; + PC += Pick(); + } + } + + uint8_t *CountersEnd() { return Counters + N; } + uintptr_t *PCsEnd() { return PCs + (N * 2); } + + TracePC::PCTableEntry *GetPCTableEntries() { + return reinterpret_cast(PCs); + } + + uint64_t Hash() { return TracePC::HashPCs(PCs, PCsEnd()); } + + // Adds the Module to the |fuzzer::TracePC| if not already added. Returns the + // the index of the first PC for the module. + uintptr_t AddToTPC() { + auto *B = reinterpret_cast(PCs); + uintptr_t Idx = 0; + for (auto *T = TPC.PCTableEntryByIdx(Idx); T; + T = TPC.PCTableEntryByIdx(++Idx)) + if (T == B) + return Idx; + TPC.HandlePCsInit(PCs, PCsEnd()); + TPC.HandleInline8bitCountersInit(Counters, CountersEnd()); + return Idx; + } +}; + +} // namespace fuzzer + +#endif // LLVM_FUZZER_TEST_UTIL_H Index: compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp =================================================================== --- compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp +++ compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp @@ -16,6 +16,7 @@ #include "FuzzerMutate.h" #include "FuzzerRandom.h" #include "FuzzerTracePC.h" +#include "tests/FuzzerTestUtil.h" #include "gtest/gtest.h" #include #include @@ -614,6 +615,15 @@ } } +TEST(TracePC, StackDepthFunction) { + EXPECT_EQ(TracePC::StackDepthStepFunction(1024), 64U); + EXPECT_EQ(TracePC::StackDepthStepFunction(1024 * 4), 80U); + EXPECT_EQ(TracePC::StackDepthStepFunction(1024 * 1024), 144U); + EXPECT_LT(TracePC::StackDepthStepFunction( + std::numeric_limits::max() / 8), + TracePC::kMaxStackDepthFeature); +} + template void EQ(const Vector &A, const Vector &B) { EXPECT_EQ(A, B); } @@ -636,6 +646,96 @@ EQ(A, __VA_ARGS__); \ } +// Helper functions to test TracePC's module functions using FakeModules of +// various sizes. +template void VerifyFeatures(FakeModule &M, bool UseCounters) { + ModuleInfo Info; + + // Each of the given features should appear in sorted order and map back to + // this module... + Vector AllFeatures; + uint32_t Last = 0; + TPC.CollectFeatures([&](size_t Feature) { + if (Last) + EXPECT_LT(Last, Feature); + AllFeatures.push_back(static_cast(Feature)); + Last = Feature; + }); + + auto Hash = M.Hash(); + EXPECT_TRUE(TPC.ModuleInfoByHash(Hash, &Info)); + + Vector Features; + for (auto F : AllFeatures) + if (Info.FirstFeature <= F && F < Info.LastFeature) + Features.push_back(F); + EXPECT_EQ(Features.size(), N); + + for (auto F : Features) { + EXPECT_TRUE(TPC.ModuleInfoByFeature(F, &Info)); + EXPECT_EQ(Hash, Info.Hash); + } +} + +template void VerifyPCs(FakeModule &M) { + ModuleInfo Info; + + // The given module's PCTableEntries should to an index, which in turn should + // correspond to ModuleInfo that represents the module. + const auto *TE = M.GetPCTableEntries(); + auto Hash = M.Hash(); + for (size_t i = 0; i < M.NumPCs; ++i) { + auto Idx = TPC.PCTableEntryIdx(&TE[i]); + EXPECT_TRUE(TPC.ModuleInfoByIdx(Idx, &Info)); + EXPECT_EQ(Hash, Info.Hash); + EXPECT_LT(Idx, Info.LastIdx); + EXPECT_GE(Idx, Info.FirstIdx); + } + + // For the given module's hash, |PCTableEntryByModule| with an offset in + // [0, NumPCs) should yield a valid PCTableEntry... + TE = TPC.PCTableEntryByModule(Hash, 0); + ASSERT_NE(TE, nullptr); + EXPECT_EQ(TPC.PCTableEntryIdx(TE), Info.FirstIdx); + + TE = TPC.PCTableEntryByModule(Hash, M.NumPCs - 1); + ASSERT_NE(TE, nullptr); + EXPECT_EQ(TPC.PCTableEntryIdx(TE), Info.LastIdx - 1); + + // ...but a bad hash or offset that should return null. + EXPECT_EQ(TPC.PCTableEntryByModule(~Hash, 0), nullptr); + EXPECT_EQ(TPC.PCTableEntryByModule(Hash, M.NumPCs), nullptr); +} + +TEST(TracePC, ModuleInfo) { + TPC.ResetMaps(); + + // Add modules. They will be added to TPC, so make them static to allow the + // test to be run multiple times. + static FakeModule<64> M1; + M1.AddToTPC(); + static FakeModule<512> M2; + M2.AddToTPC(); + static FakeModule<4096> M3; + M3.AddToTPC(); + + for (size_t i = 0; i < 2; ++i) { + bool UseCounters = i == 1; + TPC.SetUseCounters(UseCounters); + TPC.ResetMaps(); + memset(M1.Counters, 1, M1.NumPCs * sizeof(uint8_t)); + memset(M2.Counters, 8, M2.NumPCs * sizeof(uint8_t)); + memset(M3.Counters, 0x80, M3.NumPCs * sizeof(uint8_t)); + VerifyFeatures(M1, UseCounters); + VerifyFeatures(M2, UseCounters); + VerifyFeatures(M3, UseCounters); + } + + VerifyPCs(M1); + VerifyPCs(M2); + VerifyPCs(M3); +} + TEST(Merger, Parse) { Merger M;