Index: llvm/trunk/lib/Fuzzer/FuzzerInternal.h =================================================================== --- llvm/trunk/lib/Fuzzer/FuzzerInternal.h +++ llvm/trunk/lib/Fuzzer/FuzzerInternal.h @@ -25,6 +25,7 @@ #include #include "FuzzerInterface.h" +#include "FuzzerTracePC.h" namespace fuzzer { using namespace std::chrono; @@ -112,13 +113,6 @@ int SignalToMainThread(); void SleepSeconds(int Seconds); -// Clears the current PC Map. -void PcMapResetCurrent(); -// Merges the current PC Map into the combined one, and clears the former. -void PcMapMergeCurrentToCombined(); -// Returns the size of the combined PC Map. -size_t PcMapCombinedSize(); - class Random { public: Random(unsigned int seed) : R(seed) {} @@ -309,6 +303,35 @@ bool PrintFinalStats = false; bool DetectLeaks = true; }; + + // Aggregates all available coverage measurements. + struct Coverage { + Coverage() { Reset(); } + + void Reset() { + BlockCoverage = 0; + CallerCalleeCoverage = 0; + PcMapBits = 0; + CounterBitmapBits = 0; + PcBufferLen = 0; + CounterBitmap.clear(); + PCMap.Reset(); + } + + std::string DebugString() const; + + size_t BlockCoverage; + size_t CallerCalleeCoverage; + + size_t PcBufferLen; + // Precalculated number of bits in CounterBitmap. + size_t CounterBitmapBits; + std::vector CounterBitmap; + // Precalculated number of bits in PCMap. + size_t PcMapBits; + PcCoverageMap PCMap; + }; + Fuzzer(UserCallback CB, MutationDispatcher &MD, FuzzingOptions Options); void AddToCorpus(const Unit &U) { Corpus.push_back(U); @@ -378,11 +401,8 @@ // Must be called whenever the corpus or unit weights are changed. void UpdateCorpusDistribution(); - size_t RecordBlockCoverage(); - size_t RecordCallerCalleeCoverage(); - void PrepareCoverageBeforeRun(); - bool CheckCoverageAfterRun(); void ResetCoverage(); + bool UpdateMaxCoverage(); // Trace-based fuzzing: we run a unit with some kind of tracing // enabled and record potentially useful mutations. Then @@ -410,16 +430,6 @@ std::vector Corpus; std::unordered_set UnitHashesAddedToCorpus; - - // For UseCounters - std::vector CounterBitmap; - size_t TotalBits() { // Slow. Call it only for printing stats. - size_t Res = 0; - for (auto x : CounterBitmap) - Res += __builtin_popcount(x); - return Res; - } - std::vector MutateInPlaceHere; std::piecewise_constant_distribution CorpusDistribution; @@ -430,10 +440,9 @@ system_clock::time_point UnitStartTime; long TimeOfLongestUnitInSeconds = 0; long EpochOfLastReadOfOutputCorpus = 0; - size_t LastRecordedBlockCoverage = 0; - size_t LastRecordedPcMapSize = 0; - size_t LastRecordedCallerCalleeCoverage = 0; - size_t LastCoveragePcBufferLen = 0; + + // Maximum recorded coverage. + Coverage MaxCoverage; }; }; // namespace fuzzer Index: llvm/trunk/lib/Fuzzer/FuzzerLoop.cpp =================================================================== --- llvm/trunk/lib/Fuzzer/FuzzerLoop.cpp +++ llvm/trunk/lib/Fuzzer/FuzzerLoop.cpp @@ -81,12 +81,83 @@ return F->GetMD().Mutate(Data, Size, MaxSize); } +struct CoverageController { + static void Reset() { + CHECK_WEAK_API_FUNCTION(__sanitizer_reset_coverage); + __sanitizer_reset_coverage(); + PcMapResetCurrent(); + } + + static void ResetCounters(const Fuzzer::FuzzingOptions &Options) { + if (Options.UseCounters) { + __sanitizer_update_counter_bitset_and_clear_counters(0); + } + } + + static void Prepare(const Fuzzer::FuzzingOptions &Options, + Fuzzer::Coverage *C) { + if (Options.UseCounters) { + size_t NumCounters = __sanitizer_get_number_of_counters(); + C->CounterBitmap.resize(NumCounters); + } + } + + // Records data to a maximum coverage tracker. Returns true if additional + // coverage was discovered. + static bool RecordMax(const Fuzzer::FuzzingOptions &Options, + Fuzzer::Coverage *C) { + bool Res = false; + + uint64_t NewBlockCoverage = __sanitizer_get_total_unique_coverage(); + if (NewBlockCoverage > C->BlockCoverage) { + Res = true; + C->BlockCoverage = NewBlockCoverage; + } + + if (Options.UseIndirCalls && + __sanitizer_get_total_unique_caller_callee_pairs) { + uint64_t NewCallerCalleeCoverage = + __sanitizer_get_total_unique_caller_callee_pairs(); + if (NewCallerCalleeCoverage > C->CallerCalleeCoverage) { + Res = true; + C->CallerCalleeCoverage = NewCallerCalleeCoverage; + } + } + + if (Options.UseCounters) { + uint64_t CounterDelta = + __sanitizer_update_counter_bitset_and_clear_counters( + C->CounterBitmap.data()); + if (CounterDelta > 0) { + Res = true; + C->CounterBitmapBits += CounterDelta; + } + } + + uint64_t NewPcMapBits = PcMapMergeInto(&C->PCMap); + if (NewPcMapBits > C->PcMapBits) { + Res = true; + C->PcMapBits = NewPcMapBits; + } + + uintptr_t *CoverageBuf; + uint64_t NewPcBufferLen = __sanitizer_get_coverage_pc_buffer(&CoverageBuf); + if (NewPcBufferLen > C->PcBufferLen) { + Res = true; + C->PcBufferLen = NewPcBufferLen; + } + + return Res; + } +}; + Fuzzer::Fuzzer(UserCallback CB, MutationDispatcher &MD, FuzzingOptions Options) : CB(CB), MD(MD), Options(Options) { SetDeathCallback(); InitializeTraceState(); assert(!F); F = this; + ResetCoverage(); } void Fuzzer::SetDeathCallback() { @@ -208,22 +279,21 @@ Printf("runs,block_cov,bits,cc_cov,corpus,execs_per_sec,tbms,reason\n"); } Printf("%zd,%zd,%zd,%zd,%zd,%zd,%s\n", TotalNumberOfRuns, - LastRecordedBlockCoverage, TotalBits(), - LastRecordedCallerCalleeCoverage, Corpus.size(), ExecPerSec, - Where); + MaxCoverage.BlockCoverage, MaxCoverage.CounterBitmapBits, + MaxCoverage.CallerCalleeCoverage, Corpus.size(), ExecPerSec, Where); } if (!Options.Verbosity) return; Printf("#%zd\t%s", TotalNumberOfRuns, Where); - if (LastRecordedBlockCoverage) - Printf(" cov: %zd", LastRecordedBlockCoverage); - if (LastRecordedPcMapSize) - Printf(" path: %zd", LastRecordedPcMapSize); - if (auto TB = TotalBits()) + if (MaxCoverage.BlockCoverage) + Printf(" cov: %zd", MaxCoverage.BlockCoverage); + if (MaxCoverage.PcMapBits) + Printf(" path: %zd", MaxCoverage.PcMapBits); + if (auto TB = MaxCoverage.CounterBitmapBits) Printf(" bits: %zd", TB); - if (LastRecordedCallerCalleeCoverage) - Printf(" indir: %zd", LastRecordedCallerCalleeCoverage); + if (MaxCoverage.CallerCalleeCoverage) + Printf(" indir: %zd", MaxCoverage.CallerCalleeCoverage); Printf(" units: %zd exec/s: %zd", Corpus.size(), ExecPerSec); Printf("%s", End); } @@ -298,7 +368,7 @@ if (RunOne(U)) { NewCorpus.push_back(U); if (Options.Verbosity >= 2) - Printf("NEW0: %zd L %zd\n", LastRecordedBlockCoverage, U.size()); + Printf("NEW0: %zd L %zd\n", MaxCoverage.BlockCoverage, U.size()); } } Corpus = NewCorpus; @@ -309,12 +379,29 @@ CheckForMemoryLeaks(); } +bool Fuzzer::UpdateMaxCoverage() { + uintptr_t PrevBufferLen = MaxCoverage.PcBufferLen; + bool Res = CoverageController::RecordMax(Options, &MaxCoverage); + + if (Options.PrintNewCovPcs && PrevBufferLen != MaxCoverage.PcBufferLen) { + uintptr_t *CoverageBuf; + __sanitizer_get_coverage_pc_buffer(&CoverageBuf); + assert(CoverageBuf); + for (size_t I = PrevBufferLen; I < MaxCoverage.PcBufferLen; ++I) { + Printf("%p\n", CoverageBuf[I]); + } + } + + return Res; +} + bool Fuzzer::RunOne(const uint8_t *Data, size_t Size) { TotalNumberOfRuns++; - PrepareCoverageBeforeRun(); + // TODO(aizatsky): this Reset call seems to be not needed. + CoverageController::ResetCounters(Options); ExecuteCallback(Data, Size); - bool Res = CheckCoverageAfterRun(); + bool Res = UpdateMaxCoverage(); auto UnitStopTime = system_clock::now(); auto TimeOfUnit = @@ -378,61 +465,14 @@ assert(Res == 0); } -size_t Fuzzer::RecordBlockCoverage() { - CHECK_WEAK_API_FUNCTION(__sanitizer_get_total_unique_coverage); - uintptr_t PrevCoverage = LastRecordedBlockCoverage; - LastRecordedBlockCoverage = __sanitizer_get_total_unique_coverage(); - - if (PrevCoverage == LastRecordedBlockCoverage || !Options.PrintNewCovPcs) - return LastRecordedBlockCoverage; - - uintptr_t PrevBufferLen = LastCoveragePcBufferLen; - uintptr_t *CoverageBuf; - LastCoveragePcBufferLen = __sanitizer_get_coverage_pc_buffer(&CoverageBuf); - assert(CoverageBuf); - for (size_t i = PrevBufferLen; i < LastCoveragePcBufferLen; ++i) { - Printf("%p\n", CoverageBuf[i]); - } - - return LastRecordedBlockCoverage; -} - -size_t Fuzzer::RecordCallerCalleeCoverage() { - if (!Options.UseIndirCalls) - return 0; - if (!__sanitizer_get_total_unique_caller_callee_pairs) - return 0; - return LastRecordedCallerCalleeCoverage = - __sanitizer_get_total_unique_caller_callee_pairs(); -} - -void Fuzzer::PrepareCoverageBeforeRun() { - if (Options.UseCounters) { - size_t NumCounters = __sanitizer_get_number_of_counters(); - CounterBitmap.resize(NumCounters); - __sanitizer_update_counter_bitset_and_clear_counters(0); - } - RecordBlockCoverage(); - RecordCallerCalleeCoverage(); -} - -bool Fuzzer::CheckCoverageAfterRun() { - size_t OldCoverage = LastRecordedBlockCoverage; - size_t NewCoverage = RecordBlockCoverage(); - size_t OldCallerCalleeCoverage = LastRecordedCallerCalleeCoverage; - size_t NewCallerCalleeCoverage = RecordCallerCalleeCoverage(); - size_t NumNewBits = 0; - size_t OldPcMapSize = LastRecordedPcMapSize; - PcMapMergeCurrentToCombined(); - size_t NewPcMapSize = PcMapCombinedSize(); - LastRecordedPcMapSize = NewPcMapSize; - if (NewPcMapSize > OldPcMapSize) - return true; - if (Options.UseCounters) - NumNewBits = __sanitizer_update_counter_bitset_and_clear_counters( - CounterBitmap.data()); - return NewCoverage > OldCoverage || - NewCallerCalleeCoverage > OldCallerCalleeCoverage || NumNewBits; +std::string Fuzzer::Coverage::DebugString() const { + std::string Result = + std::string("Coverage{") + "BlockCoverage=" + + std::to_string(BlockCoverage) + " CallerCalleeCoverage=" + + std::to_string(CallerCalleeCoverage) + " CounterBitmapBits=" + + std::to_string(CounterBitmapBits) + " PcMapBits=" + + std::to_string(PcMapBits) + "}"; + return Result; } void Fuzzer::WriteToOutputCorpus(const Unit &U) { @@ -639,9 +679,9 @@ } void Fuzzer::ResetCoverage() { - CHECK_WEAK_API_FUNCTION(__sanitizer_reset_coverage); - __sanitizer_reset_coverage(); - CounterBitmap.clear(); + CoverageController::Reset(); + MaxCoverage.Reset(); + CoverageController::Prepare(Options, &MaxCoverage); } // Experimental search heuristic: drilling. Index: llvm/trunk/lib/Fuzzer/FuzzerTracePC.h =================================================================== --- llvm/trunk/lib/Fuzzer/FuzzerTracePC.h +++ llvm/trunk/lib/Fuzzer/FuzzerTracePC.h @@ -0,0 +1,37 @@ +//===- FuzzerTracePC.h - INTERNAL - Path tracer. --------*- C++ -* ===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// Trace PCs. +// This module implements __sanitizer_cov_trace_pc, a callback required +// for -fsanitize-coverage=trace-pc instrumentation. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_FUZZER_TRACE_PC_H +#define LLVM_FUZZER_TRACE_PC_H + +namespace fuzzer { +struct PcCoverageMap { + static const size_t kMapSizeInBits = 65371; // Prime. + static const size_t kMapSizeInBitsAligned = 65536; // 2^16 + static const size_t kBitsInWord = (sizeof(uintptr_t) * 8); + static const size_t kMapSizeInWords = kMapSizeInBitsAligned / kBitsInWord; + + void Reset(); + inline void Update(uintptr_t Addr); + size_t MergeFrom(const PcCoverageMap &Other); + + uintptr_t Map[kMapSizeInWords] __attribute__((aligned(512))); +}; + +// Clears the current PC Map. +void PcMapResetCurrent(); +// Merges the current PC Map into the combined one, and clears the former. +size_t PcMapMergeInto(PcCoverageMap *Map); +} + +#endif Index: llvm/trunk/lib/Fuzzer/FuzzerTracePC.cpp =================================================================== --- llvm/trunk/lib/Fuzzer/FuzzerTracePC.cpp +++ llvm/trunk/lib/Fuzzer/FuzzerTracePC.cpp @@ -15,39 +15,43 @@ #include "FuzzerInternal.h" namespace fuzzer { -static const size_t kMapSizeInBits = 65371; // Prime. -static const size_t kMapSizeInBitsAligned = 65536; // 2^16 -static const size_t kBitsInWord =(sizeof(uintptr_t) * 8); -static const size_t kMapSizeInWords = kMapSizeInBitsAligned / kBitsInWord; -static uintptr_t CurrentMap[kMapSizeInWords] __attribute__((aligned(512))); -static uintptr_t CombinedMap[kMapSizeInWords] __attribute__((aligned(512))); -static size_t CombinedMapSize; + +void PcCoverageMap::Reset() { memset(Map, 0, sizeof(Map)); } + +void PcCoverageMap::Update(uintptr_t Addr) { + uintptr_t Idx = Addr % kMapSizeInBits; + uintptr_t WordIdx = Idx / kBitsInWord; + uintptr_t BitIdx = Idx % kBitsInWord; + Map[WordIdx] |= 1UL << BitIdx; +} + +size_t PcCoverageMap::MergeFrom(const PcCoverageMap &Other) { + uintptr_t Res = 0; + for (size_t i = 0; i < kMapSizeInWords; i++) + Res += __builtin_popcountl(Map[i] |= Other.Map[i]); + return Res; +} + +static PcCoverageMap CurrentMap; static thread_local uintptr_t Prev; void PcMapResetCurrent() { if (Prev) { Prev = 0; - memset(CurrentMap, 0, sizeof(CurrentMap)); + CurrentMap.Reset(); } } -void PcMapMergeCurrentToCombined() { - if (!Prev) return; - uintptr_t Res = 0; - for (size_t i = 0; i < kMapSizeInWords; i++) - Res += __builtin_popcountl(CombinedMap[i] |= CurrentMap[i]); - CombinedMapSize = Res; +size_t PcMapMergeInto(PcCoverageMap *Map) { + if (!Prev) + return 0; + return Map->MergeFrom(CurrentMap); } -size_t PcMapCombinedSize() { return CombinedMapSize; } - static void HandlePC(uint32_t PC) { // We take 12 bits of PC and mix it with the previous PCs. uintptr_t Next = (Prev << 5) ^ (PC & 4095); - uintptr_t Idx = Next % kMapSizeInBits; - uintptr_t WordIdx = Idx / kBitsInWord; - uintptr_t BitIdx = Idx % kBitsInWord; - CurrentMap[WordIdx] |= 1UL << BitIdx; + CurrentMap.Update(Next); Prev = Next; }