Index: compiler-rt/lib/fuzzer/FuzzerDSORelative.h =================================================================== --- compiler-rt/lib/fuzzer/FuzzerDSORelative.h +++ compiler-rt/lib/fuzzer/FuzzerDSORelative.h @@ -13,10 +13,35 @@ #include "FuzzerDefs.h" +#include #include namespace fuzzer { +// This struct contains bookkepping information for a single DSO. See also the +// DSOInfoBy* methods in TracePC. +struct DSOInfo { + // 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 DSOInfo struct + // with an offset greater than the length of the array as uninitialized. + size_t PCTableOffset = std::numeric_limits::max(); +}; + // 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,20 @@ 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 +136,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,14 +155,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 +179,21 @@ CB(Modules[m].Regions[r]); } - struct { const PCTableEntry *Start, *Stop; } ModulePCTable[4096]; + // Step function, grows similar to 8 * Log_2(A). + size_t StackDepthStepFunction(uintptr_t A) const; + + // 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; + size_t Size() const { return Stop - Start; } + } ModulePCTable[4096]; size_t NumPCTables; size_t NumPCsInPCTables; @@ -248,14 +276,11 @@ 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(), @@ -268,18 +293,6 @@ FirstFeature += ValueProfileMap.SizeInBits(); } - // Step function, grows similar to 8 * Log_2(A). - auto StackDepthStepFunction = [](uint32_t A) -> uint32_t { - if (!A) return A; - uint32_t 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(FirstFeature + StackDepthStepFunction(MaxStackOffset / 8)); } Index: compiler-rt/lib/fuzzer/FuzzerTracePC.cpp =================================================================== --- compiler-rt/lib/fuzzer/FuzzerTracePC.cpp +++ compiler-rt/lib/fuzzer/FuzzerTracePC.cpp @@ -35,45 +35,48 @@ 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 += Modules[NumModules - 1].Size(); + 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() == 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; } @@ -89,10 +92,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,8 +106,19 @@ _Exit(1); } } - if (size_t NumExtraCounters = ExtraCountersEnd() - ExtraCountersBegin()) + size_t NumExtraCounters = ExtraCountersEnd() - ExtraCountersBegin(); + if (NumExtraCounters) Printf("INFO: %zd Extra Counters\n", NumExtraCounters); + + // See TracePC::CollectCoverage. Features are converted from inline 8-bit + // counters, extra counters, the value profile map, and the stack depth. + size_t MaxFeatures = NumPCsInPCTables * 8; + MaxFeatures += NumExtraCounters * 8; + MaxFeatures += ValueProfileMap.SizeInBits(); + MaxFeatures += StackDepthStepFunction(std::numeric_limits::max()); + if (MaxFeatures > static_cast(std::numeric_limits::max())) + Printf("WARNING: The number of features cannot be expressed in 32 bits.\n" + "This may reduce the precision of corpus merging.\n"); } ATTRIBUTE_NO_SANITIZE_ALL @@ -168,11 +181,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)]); @@ -195,7 +206,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; @@ -204,13 +215,76 @@ 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::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 = 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; +} + +void TracePC::NextDSOInfo(DSOInfo *Info) { + assert(NumModules == NumPCTables); + // Use an invalid oofset 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) { + 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 += PCTable.Size(); + } else { + Info->Hash = 0; + Info->LastFeature = std::numeric_limits::max(); + Info->LastIdx = std::numeric_limits::max(); + } +} + +void TracePC::DSOInfoByFeature(size_t Feature, DSOInfo *Info) { + Info->PCTableOffset = NumPCTables; + do { + NextDSOInfo(Info); + } while (Info->LastFeature <= Feature); +} + +void TracePC::DSOInfoByIdx(uintptr_t Idx, DSOInfo *Info) { + Info->PCTableOffset = NumPCTables; + do { + NextDSOInfo(Info); + } while (Info->LastIdx <= Idx); +} + static std::string GetModuleName(uintptr_t PC) { char ModulePathRaw[4096] = ""; // What's PATH_MAX in portable C++? void *OffsetRaw = nullptr; @@ -247,7 +321,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)); @@ -397,10 +471,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 @@ -413,6 +485,16 @@ return InitialStack - __sancov_lowest_stack; // Stack grows down } +size_t TracePC::StackDepthStepFunction(uintptr_t A) const { + 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.