[libfuzzer] Refactoring coverage state-management code..

[aizatsky]

Summary

It is now less state-dependent and will allow easier comparing of
coverages of different units.

[aizatsky]

updates

[aizatsky]

ready for review.

[kcc]

Correct me if I am wrong, but this change seems to add extra malloc call for every unit.
Don't do that.
Instead of creating a scratch copy on every execution we may want to have two copies: current and maximal.
But no mallocs, please.

lib/Fuzzer/FuzzerLoop.cpp

355–357

Will this cause extra memory allocations to happen for every execution of RunOne()?

lib/Fuzzer/FuzzerTracePC.h

1 ↗

(On Diff #56769)

i-face? really?

I don't want to expose this in a header file.
I see why you did this (to have mergeable objects), but that might be a bad idea because of extra memory allocations.

[aizatsky]

no additional malloc

[aizatsky]

Made sure that no additional allocations happen. PTAL.

lib/Fuzzer/FuzzerTracePC.h

1 ↗

(On Diff #56769)

Trying to stay within 80 chars.

I don't really need this header. I had this in FuzzerInternal.h first. I'm happy to move this definition back. I simply presumed that you'd like to keep it separate.

[aizatsky]

lib/Fuzzer/FuzzerLoop.cpp

355–357

BTW all tests pass without this call, but you used to have it before. Do you want me to keep it?

[kcc]

lib/Fuzzer/FuzzerInternal.h

353

is this used?

lib/Fuzzer/FuzzerLoop.cpp

355–357

let's not make too many changes at the same time, leave it for now.

lib/Fuzzer/FuzzerTracePC.h

2 ↗

(On Diff #56823)

No, this header is fine, I just don't like i-face. Just leave "Path tracer"

9 ↗

(On Diff #56823)

Fix the comment (move from the cpp file)

25 ↗

(On Diff #56823)

move the code to cpp file

32 ↗

(On Diff #56823)

ditto

[aizatsky]

review

[aizatsky]

All Done. PTAL.

lib/Fuzzer/FuzzerInternal.h

353

Not right now, but I used it several times for debugging. I'd like to keep it.

lib/Fuzzer/FuzzerLoop.cpp

355–357

Added comment.

[kcc]

LGTM, but please test on at least one non-trivial target (other than tests) that is large and fast, to ensure we haven't missed any perf degradation.

Also, consider moving all coverage stuff from FuzzerLoop into a separate file (FuzzerCoverage) in a separate change.

[aizatsky]

I don't see any performance difference. Tested on chromium's mp4_box_reader_fuzzer (166M binary).

Before:

$ ./out/fuzzer/mp4_box_reader_fuzzer -seed=1 -runs=1000000 ~/tmp/fuzzers/mp4_box_reader_fuzzer
INFO: Seed: 1
INFO: -max_len is not provided, using 500
#0 READ units: 429 exec/s: 0
#429 INITED cov: 517 bits: 686 indir: 23 units: 120 exec/s: 0
#16384 pulse cov: 547 bits: 686 indir: 25 units: 120 exec/s: 5461
#32768 pulse cov: 547 bits: 686 indir: 25 units: 120 exec/s: 5461
#65536 pulse cov: 547 bits: 686 indir: 25 units: 120 exec/s: 5041
#131072 pulse cov: 547 bits: 686 indir: 25 units: 120 exec/s: 5041
#262144 pulse cov: 547 bits: 686 indir: 25 units: 120 exec/s: 4681
^C==32409== libFuzzer: run interrupted; exiting
./out/fuzzer/mp4_box_reader_fuzzer -seed=1 -runs=1000000 63.74s user 2.01s system 99% cpu 1:05.82 total

After:

$ ./out/fuzzer/mp4_box_reader_fuzzer -seed=1 -runs=1000000 ~/tmp/fuzzers/mp4_box_reader_fuzzer
INFO: Seed: 1
INFO: -max_len is not provided, using 500
#0 READ units: 425 exec/s: 0
#425 INITED cov: 381 bits: 686 indir: 23 units: 120 exec/s: 0
#426 NEW cov: 411 bits: 686 indir: 25 units: 121 exec/s: 0 L: 157 MS: 1 InsertByte-
#4002 NEW cov: 411 bits: 686 indir: 25 units: 122 exec/s: 4002 L: 453 MS: 2 EraseByte-ShuffleBytes-
#4003 NEW cov: 412 bits: 686 indir: 25 units: 123 exec/s: 4003 L: 453 MS: 3 EraseByte-ShuffleBytes-ShuffleBytes-
#16384 pulse cov: 412 bits: 686 indir: 25 units: 123 exec/s: 5461
#30789 NEW cov: 412 bits: 688 indir: 25 units: 124 exec/s: 4398 L: 187 MS: 3 ChangeByte-ChangeBit-EraseByte-
#32768 pulse cov: 412 bits: 688 indir: 25 units: 124 exec/s: 4681
#65536 pulse cov: 412 bits: 688 indir: 25 units: 124 exec/s: 4681
#131072 pulse cov: 412 bits: 688 indir: 25 units: 124 exec/s: 5041
#262144 pulse cov: 412 bits: 688 indir: 25 units: 124 exec/s: 5041
^C==29836== libFuzzer: run interrupted; exiting
./out/fuzzer/mp4_box_reader_fuzzer -seed=1 -runs=1000000 99.80s user 0.61s system 99% cpu 1:40.48 total

lib/Fuzzer/FuzzerInternal.h

 bool ToASCII(uint8_t *Data, size_t Size);
 bool IsASCII(const Unit &U);
 
 int NumberOfCpuCores();
 int GetPid();
 int SignalToMainThread();
 void SleepSeconds(int Seconds);
 
+
+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() {
+    memset(Map, 0, sizeof(Map));
+  }
+
+  size_t 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;
+  }
+
+  void Update(uintptr_t Addr) {
+    uintptr_t Idx = Addr % kMapSizeInBits;
+    uintptr_t WordIdx = Idx / kBitsInWord;
+    uintptr_t BitIdx  = Idx % kBitsInWord;
+    Map[WordIdx] |= 1UL << BitIdx;
+  }
+
+  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.
-void PcMapMergeCurrentToCombined();
-// Returns the size of the combined PC Map.
-size_t PcMapCombinedSize();
+size_t PcMapMergeInto(PcCoverageMap* Map);
 
 class Random {
  public:
   Random(unsigned int seed) : R(seed) {}
   size_t Rand() { return R(); }
   size_t RandBool() { return Rand() % 2; }
   size_t operator()(size_t n) { return n ? Rand() % n : 0; }
   std::mt19937 &Get_mt19937() { return R; }
struct FuzzingOptions {
     std::string ExactArtifactPath;
     bool SaveArtifacts = true;
     bool PrintNEW = true; // Print a status line when new units are found;
     bool OutputCSV = false;
     bool PrintNewCovPcs = false;
     bool PrintFinalStats = false;
     bool DetectLeaks = true;
   };
+
+  struct CoverageStats {
+    CoverageStats() { Reset(); }
+
+    void Reset() {
+      Generation = -1;
+      BlockCoverage = 0;
+      CallerCalleeCoverage = 0;
+      PcMapBits = 0;
+      CounterBitmapBits = 0;
+      PcBufferLen = 0;
+      CounterBitmap.clear();
+      PCMap.Reset();
+    }
+
+    bool MergeFrom(const CoverageStats& Other);
+    std::string DebugString() const;
+
+    size_t TotalBits() { // Slow. Call it only for printing stats.
+      size_t Res = 0;
+      for (auto x : CounterBitmap)
+        Res += __builtin_popcount(x);
+      return Res;
+    }
+
+    int64_t Generation;
+    size_t BlockCoverage;
+    size_t CallerCalleeCoverage;
+
+    size_t PcBufferLen;
+    size_t CounterBitmapBits;
+    size_t PcMapBits;
+    PcCoverageMap PCMap;
+    std::vector<uint8_t> CounterBitmap;
+  };
+
   Fuzzer(UserCallback CB, MutationDispatcher &MD, FuzzingOptions Options);
   void AddToCorpus(const Unit &U) {
     Corpus.push_back(U);
     UpdateCorpusDistribution();
   }
   size_t ChooseUnitIdxToMutate();
   const Unit &ChooseUnitToMutate() { return Corpus[ChooseUnitIdxToMutate()]; };
   void Loop();
private:
   void ShuffleCorpus(UnitVector *V);
   void TryDetectingAMemoryLeak(uint8_t *Data, size_t Size);
   void CheckForMemoryLeaks();
 
   // Updates the probability distribution for the units in the corpus.
   // 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();
 
   // Trace-based fuzzing: we run a unit with some kind of tracing
   // enabled and record potentially useful mutations. Then
   // We apply these mutations one by one to the unit and run it again.
 
   // Start tracing; forget all previously proposed mutations.
   void StartTraceRecording();
private:
   size_t TotalNumberOfRuns = 0;
   size_t NumberOfNewUnitsAdded = 0;
 
   bool HasMoreMallocsThanFrees = false;
   size_t NumberOfLeakDetectionAttempts = 0;
 
   std::vector<Unit> Corpus;
   std::unordered_set<std::string> UnitHashesAddedToCorpus;
-
-  // For UseCounters
-  std::vector<uint8_t> 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<uint8_t> MutateInPlaceHere;
 
   std::piecewise_constant_distribution<double> CorpusDistribution;
   UserCallback CB;
   MutationDispatcher &MD;
   FuzzingOptions Options;
   system_clock::time_point ProcessStartTime = system_clock::now();
   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;
+
+  CoverageStats MaxCoverage;
 };
 
 }; // namespace fuzzer
 
 #endif // LLVM_FUZZER_INTERNAL_H

lib/Fuzzer/FuzzerLoop.cpp

 // Only one Fuzzer per process.
 static Fuzzer *F;
 
 size_t Mutate(uint8_t *Data, size_t Size, size_t MaxSize) {
   assert(F);
   return F->GetMD().Mutate(Data, Size, MaxSize);
 }
 
+struct CoverageController {
+  static void Init() {
+    Generation = 0;
+    Reset();
+  }
+
+  static void Reset() {
+    CHECK_WEAK_API_FUNCTION(__sanitizer_reset_coverage);
+    __sanitizer_reset_coverage();
+    PcMapResetCurrent();
+    Generation++;
+  }
+
+  static void Prepare(const Fuzzer::FuzzingOptions& Options, 
+      Fuzzer::CoverageStats* Stats) {
+    if (Options.UseCounters) {
+      size_t NumCounters = __sanitizer_get_number_of_counters();
+      Stats->CounterBitmap.resize(NumCounters);
+      __sanitizer_update_counter_bitset_and_clear_counters(0);
+    }
+  }
+
+  static void Record(const Fuzzer::FuzzingOptions& Options, Fuzzer::CoverageStats* Stats) {
+    Stats->BlockCoverage = __sanitizer_get_total_unique_coverage();
+    if (Options.UseIndirCalls && __sanitizer_get_total_unique_caller_callee_pairs)
+      Stats->CallerCalleeCoverage = __sanitizer_get_total_unique_caller_callee_pairs();
+    if (Options.UseCounters)
+      Stats->CounterBitmapBits += __sanitizer_update_counter_bitset_and_clear_counters(Stats->CounterBitmap.data());
+    Stats->PcMapBits = PcMapMergeInto(&Stats->PCMap);
+    Stats->Generation = Generation;
+    uintptr_t *CoverageBuf;
+    Stats->PcBufferLen = __sanitizer_get_coverage_pc_buffer(&CoverageBuf);
+  }
+
+  static int64_t Generation;
+};
+
+int64_t CoverageController::Generation;
+
 Fuzzer::Fuzzer(UserCallback CB, MutationDispatcher &MD, FuzzingOptions Options)
     : CB(CB), MD(MD), Options(Options) {
   SetDeathCallback();
   InitializeTraceState();
   assert(!F);
   F = this;
+  CoverageController::Init();
 }
 
 void Fuzzer::SetDeathCallback() {
   CHECK_WEAK_API_FUNCTION(__sanitizer_set_death_callback);
   __sanitizer_set_death_callback(StaticDeathCallback);
 }
 
 void Fuzzer::StaticDeathCallback() {
void Fuzzer::PrintStats(const char *Where, const char *End) {
   size_t ExecPerSec = execPerSec();
   if (Options.OutputCSV) {
     static bool csvHeaderPrinted = false;
     if (!csvHeaderPrinted) {
       csvHeaderPrinted = true;
       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,
+           MaxCoverage.BlockCoverage, MaxCoverage.TotalBits(),
+           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.TotalBits())
     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);
 }
 
 void Fuzzer::PrintFinalStats() {
   if (!Options.PrintFinalStats) return;
   size_t ExecPerSec = execPerSec();
   Printf("stat::number_of_executed_units: %zd\n", TotalNumberOfRuns);
void Fuzzer::ShuffleAndMinimize() {
   std::vector<Unit> NewCorpus;
   if (Options.ShuffleAtStartUp)
     ShuffleCorpus(&Corpus);
 
   for (const auto &U : Corpus) {
     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;
   UpdateCorpusDistribution();
   for (auto &X : Corpus)
     UnitHashesAddedToCorpus.insert(Hash(X));
   PrintStats("INITED");
   CheckForMemoryLeaks();
 }
 
 bool Fuzzer::RunOne(const uint8_t *Data, size_t Size) {
   TotalNumberOfRuns++;
 
-  PrepareCoverageBeforeRun();
+  CoverageStats Stats;
+
+  CoverageController::Prepare(Options, &Stats);
   ExecuteCallback(Data, Size);
-  bool Res = CheckCoverageAfterRun();
+  CoverageController::Record(Options, &Stats);
+
+  uintptr_t PrevBufferLen = MaxCoverage.PcBufferLen;
+  bool Res = MaxCoverage.MergeFrom(Stats);
+
+  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]);
+    }
+  }
 
   auto UnitStopTime = system_clock::now();
   auto TimeOfUnit =
       duration_cast<seconds>(UnitStopTime - UnitStartTime).count();
   if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) &&
       secondsSinceProcessStartUp() >= 2)
     PrintStats("pulse ");
   if (TimeOfUnit > TimeOfLongestUnitInSeconds &&
void Fuzzer::ExecuteCallback(const uint8_t *Data, size_t Size) {
   int Res = CB(DataCopy.get(), Size);
   (void)Res;
   HasMoreMallocsThanFrees = AllocTracer.Stop();
   CurrentUnitSize = 0;
   CurrentUnitData = nullptr;
   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();
+bool Fuzzer::CoverageStats::MergeFrom(const CoverageStats& Other) {
+  assert(Other.Generation >= 0);
+  if (Generation < 0) 
+    Generation = Other.Generation;
+  // All coverage data has to come from a single generation.
+  assert(Generation == Other.Generation);
 
-  if (PrevCoverage == LastRecordedBlockCoverage || !Options.PrintNewCovPcs)
-    return LastRecordedBlockCoverage;
+  bool Res = false;
 
-  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]);
+  if (Other.BlockCoverage > BlockCoverage) {
+    Res = true;
+    BlockCoverage = Other.BlockCoverage;
   }
 
-  return LastRecordedBlockCoverage;
+  if (Other.CallerCalleeCoverage > CallerCalleeCoverage) {
+    Res = true;
+    CallerCalleeCoverage = Other.CallerCalleeCoverage;
   }
 
-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();
+  if (Other.PcBufferLen > PcBufferLen) {
+    Res = true;
+    PcBufferLen = Other.PcBufferLen;
   }
 
-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);
+  if (CounterBitmap.size() != 0) {
+    assert(CounterBitmap.size() == Other.CounterBitmap.size());
+    size_t NewCounterBitmapBits = 0;
+
+    for (size_t i = 0; i < CounterBitmap.size(); ++i) {
+      NewCounterBitmapBits += __builtin_popcount(CounterBitmap[i] |= Other.CounterBitmap[i]);
+    }
+
+    if (NewCounterBitmapBits != CounterBitmapBits) {
+      Res = true;
+      CounterBitmapBits = NewCounterBitmapBits;
     }
-  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;
+  size_t NewPcMapBits = PCMap.MergeFrom(Other.PCMap);
+  if (NewPcMapBits > PcMapBits) {
+    Res = true;
+    PcMapBits = NewPcMapBits;
+  }
+
+  return Res;
+}
+
+std::string Fuzzer::CoverageStats::DebugString() const {
+  std::string Result = std::string("CoverageStats{") +
+    "BlockCoverage=" + std::to_string(BlockCoverage) + 
+    " CallerCalleeCoverage=" + std::to_string(CallerCalleeCoverage) +
+    " PcMapSize=" + std::to_string(PcMapBits) +
+    "}";
+  return Result;
 }
 
 void Fuzzer::WriteToOutputCorpus(const Unit &U) {
   if (Options.OutputCorpus.empty())
     return;
   std::string Path = DirPlusFile(Options.OutputCorpus, Hash(U));
   WriteToFile(U, Path);
   if (Options.Verbosity >= 2)

 size_t Fuzzer::ChooseUnitIdxToMutate() {
   size_t Idx =
       static_cast<size_t>(CorpusDistribution(MD.GetRand().Get_mt19937()));
   assert(Idx < Corpus.size());
   return Idx;
 }
 
 void Fuzzer::ResetCoverage() {
-  CHECK_WEAK_API_FUNCTION(__sanitizer_reset_coverage);
-  __sanitizer_reset_coverage();
-  CounterBitmap.clear();
+  CoverageController::Reset();
+  MaxCoverage.Reset();
 }
 
 // Experimental search heuristic: drilling.
 // - Read, shuffle, execute and minimize the corpus.
 // - Choose one random unit.
 // - Reset the coverage.
 // - Start fuzzing as if the chosen unit was the only element of the corpus.
 // - When done, reset the coverage again.

lib/Fuzzer/FuzzerMutate.cpp

size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary(
   return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize);
 }
 
 size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data,
                                                  size_t Size, size_t MaxSize) {
   if (D.empty()) return 0;
   DictionaryEntry &DE = D[Rand(D.size())];
   const Word &W = DE.GetW();
+//  Printf("UseWord:");
+//  PrintASCII(W);
+//  Printf(" (%zd)\n", D.size());
   bool UsePositionHint = DE.HasPositionHint() &&
                          DE.GetPositionHint() + W.size() < Size && Rand.RandBool();
   if (Rand.RandBool()) {  // Insert W.
     if (Size + W.size() > MaxSize) return 0;
     size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1);
     memmove(Data + Idx + W.size(), Data + Idx, Size - Idx);
     memcpy(Data + Idx, W.data(), W.size());
     Size += W.size();

lib/Fuzzer/FuzzerTracePC.cpp

 // This module implements __sanitizer_cov_trace_pc, a callback required
 // for -fsanitize-coverage=trace-pc instrumentation.
 //
 //===----------------------------------------------------------------------===//
 
 #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;
+
+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;
 }
 
 } // namespace fuzzer
 
 extern "C" void __sanitizer_cov_trace_pc() {
   fuzzer::HandlePC(static_cast<uint32_t>(
       reinterpret_cast<uintptr_t>(__builtin_return_address(0))));
 }