Index: compiler-rt/lib/fuzzer/FuzzerDSORelative.h =================================================================== --- compiler-rt/lib/fuzzer/FuzzerDSORelative.h +++ compiler-rt/lib/fuzzer/FuzzerDSORelative.h @@ -17,6 +17,17 @@ namespace fuzzer { +// This struct contains bookkepping information for a single DSO. See also the +// DSOInfoBy* methods in TracePC. +struct DSOInfo { + size_t PCTableOffset; + uint64_t Hash; + size_t FirstFeature; + size_t LastFeature; + uintptr_t FirstIdx; + uintptr_t LastIdx; +}; + // This class represents an aggregation of sets of values associated with a DSO. // It provides methods for adding/removing additional DSOs and/or values. class DSORelativeValues final { Index: compiler-rt/lib/fuzzer/FuzzerTracePC.h =================================================================== --- compiler-rt/lib/fuzzer/FuzzerTracePC.h +++ compiler-rt/lib/fuzzer/FuzzerTracePC.h @@ -11,6 +11,7 @@ #ifndef LLVM_FUZZER_TRACE_PC #define LLVM_FUZZER_TRACE_PC +#include "FuzzerDSORelative.h" #include "FuzzerDefs.h" #include "FuzzerDictionary.h" #include "FuzzerValueBitMap.h" @@ -69,13 +70,19 @@ class TracePC { public: - void HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop); - void HandlePCsInit(const uintptr_t *Start, const uintptr_t *Stop); - void HandleCallerCallee(uintptr_t Caller, uintptr_t Callee); - template void HandleCmp(uintptr_t PC, T Arg1, T Arg2); - size_t GetTotalPCCoverage(); - void SetUseCounters(bool UC) { UseCounters = UC; } - void SetUseValueProfileMask(uint32_t VPMask) { UseValueProfileMask = VPMask; } + bool 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(); + void SetUseCounters(bool UC) { UseCounters = UC; } + void SetUseValueProfileMask(uint32_t VPMask) { + UseValueProfileMask = VPMask; } void SetPrintNewPCs(bool P) { DoPrintNewPCs = P; } void SetPrintNewFuncs(size_t P) { NumPrintNewFuncs = P; } void UpdateObservedPCs(); @@ -128,6 +135,13 @@ static uintptr_t GetNextInstructionPc(uintptr_t PC); bool PcIsFuncEntry(const PCTableEntry *TE) { return TE->PCFlags & 1; } + const PCTableEntry *PCTableEntryByDSO(uint64_t DSO, uintptr_t Offset); + void DSOInfoByFeature(size_t Feature, DSOInfo *Info); + void DSOInfoByIdx(uintptr_t Idx, DSOInfo *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,8 +154,6 @@ struct Module { struct Region { uint8_t *Start, *Stop; - bool Enabled; - bool OneFullPage; }; Region *Regions; size_t NumRegions; @@ -165,7 +177,17 @@ CB(Modules[m].Regions[r]); } - struct { const PCTableEntry *Start, *Stop; } ModulePCTable[4096]; + // Given a DSOInfo representing a module, updates it to represent the next + // module. If the current module is the last one, the returned hash will be 0. + // This DSOInfo represents non-PC-related counters, such as stack depth and + // extra counters. Callers iterating over modules should zero-initialize Info + // before the first call. + void NextDSOInfo(DSOInfo *Info); + + struct { + const PCTableEntry *Start, *Stop; + uint64_t Hash; + } ModulePCTable[4096]; size_t NumPCTables; size_t NumPCsInPCTables; @@ -250,7 +272,6 @@ 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; FirstFeature += 8 * ForEachNonZeroByte(Modules[i].Regions[r].Start, Modules[i].Regions[r].Stop, FirstFeature, Handle8bitCounter); Index: compiler-rt/lib/fuzzer/FuzzerTracePC.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerTracePC.cpp +++ compiler-rt/lib/fuzzer/FuzzerTracePC.cpp @@ -35,45 +35,49 @@ return ObservedPCs.size(); } - -void TracePC::HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop) { - if (Start == Stop) return; - if (NumModules && - Modules[NumModules - 1].Start() == Start) - 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); +bool TracePC::HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop) { + if (Start == Stop) + return false; + if (NumModules && Modules[NumModules - 1].Start() == Start) + return false; + assert(NumModules < sizeof(Modules) / sizeof(Modules[0])); + HandleInline8bitCountersInit(Start, Stop, NumModules++); + NumInline8bitCounters += (size_t)(Stop - Start); + return true; +} + +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() == (size_t)(Stop - Start))); + uint8_t *FirstPage = RoundDownByPage(Start); + M.NumRegions = ((Stop + PageSize() - 1) - 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; } @@ -172,7 +176,6 @@ (size_t)(ModulePCTable[i].Stop - ModulePCTable[i].Start)); 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)]); @@ -211,6 +214,65 @@ return nullptr; } +const TracePC::PCTableEntry *TracePC::PCTableEntryByDSO(uint64_t Hash, + uintptr_t Offset) { + for (size_t i = 0; i < NumPCTables; i++) { + auto &M = ModulePCTable[i]; + if (Hash == M.Hash) + 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 = 0; + SimpleFastHash64(&Delta, sizeof(Delta), &Hash); + for (const PCTableEntry *TE = B + 1; TE < E; ++TE) { + Delta = {TE->PC - B->PC, TE->PCFlags}; + SimpleFastHash64(&Delta, sizeof(Delta), &Hash); + } + return Hash; +} + +void TracePC::NextDSOInfo(DSOInfo *Info) { + assert(NumModules == NumPCTables); + // Use Hash == 0 as indicator of the first iteration. + if (Info->Hash) + Info->PCTableOffset++; + Info->FirstFeature = Info->LastFeature; + Info->FirstIdx = Info->LastIdx; + if (NumPCTables != 0 && Info->PCTableOffset < NumPCTables) { + auto &PCTable = ModulePCTable[Info->PCTableOffset]; + auto &Counters = Modules[Info->PCTableOffset]; + Info->Hash = PCTable.Hash; + Info->LastFeature += 8 * (Counters.Stop() - Counters.Start()); + Info->LastIdx += PCTable.Stop - PCTable.Start; + } else { + // Not found; may be ExtraCounters or stack related. + Info->Hash = 0; + Info->LastFeature = std::numeric_limits::max(); + Info->LastIdx = std::numeric_limits::max(); + } +} + +void TracePC::DSOInfoByFeature(size_t Feature, DSOInfo *Info) { + memset(Info, 0, sizeof(*Info)); + do { + NextDSOInfo(Info); + } while (Info->Hash != 0 && Info->LastFeature <= Feature); +} + +void TracePC::DSOInfoByIdx(uintptr_t Idx, DSOInfo *Info) { + memset(Info, 0, sizeof(*Info)); + do { + NextDSOInfo(Info); + } while (Info->Hash != 0 && Info->LastIdx <= Idx); +} + static std::string GetModuleName(uintptr_t PC) { char ModulePathRaw[4096] = ""; // What's PATH_MAX in portable C++? void *OffsetRaw = nullptr; @@ -397,10 +459,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.Stop - R.Start); }); } ATTRIBUTE_NO_SANITIZE_ALL Index: compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp =================================================================== --- compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp +++ compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp @@ -927,7 +927,10 @@ DSO1.Counters[1] = 2; DSO1.Counters[2] = 1; DSO1.Counters[3] = 0; // Not encoded. - EXPECT_NO_FATAL_FAILURE(CheckEncodedFeatures(DSO1, /* UseCounters */ false)); + { + SCOPED_TRACE("DSO2"); + EXPECT_NO_FATAL_FAILURE(CheckEncodedFeatures(DSO1, /*UseCounters*/ false)); + } // Add a second DSO. This time, use counters. TPC.SetUseCounters(1); @@ -941,7 +944,10 @@ DSO2.Counters[6] = 16; DSO2.Counters[7] = 32; DSO2.Counters[8] = 128; - EXPECT_NO_FATAL_FAILURE(CheckEncodedFeatures(DSO2, /* UseCounters */ true)); + { + SCOPED_TRACE("DSO2"); + EXPECT_NO_FATAL_FAILURE(CheckEncodedFeatures(DSO2, /*UseCounters*/ true)); + } } TEST(FuzzerFork, DecodeFeatures) {