[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

401

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

lib/Fuzzer/FuzzerTracePC.h

2

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

2

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

401

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

321

is this used?

lib/Fuzzer/FuzzerLoop.cpp

401

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

lib/Fuzzer/FuzzerTracePC.h

2

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

9

Fix the comment (move from the cpp file)

25

move the code to cpp file

32

ditto

[aizatsky]

review

[aizatsky]

All Done. PTAL.

lib/Fuzzer/FuzzerInternal.h

321

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

lib/Fuzzer/FuzzerLoop.cpp

401

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

 #include <cstdlib>
 #include <random>
 #include <string.h>
 #include <string>
 #include <unordered_set>
 #include <vector>
 
 #include "FuzzerInterface.h"
+#include "FuzzerTracePC.h"
 
 namespace fuzzer {
 using namespace std::chrono;
 typedef std::vector<uint8_t> Unit;
 typedef std::vector<Unit> UnitVector;
 
 // A simple POD sized array of bytes.
 template <size_t kMaxSize> class FixedWord {

 bool ToASCII(uint8_t *Data, size_t Size);
 bool IsASCII(const Unit &U);
 
 int NumberOfCpuCores();
 int GetPid();
 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) {}
   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; }
  private:
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;
   };
+
+  // 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<uint8_t> 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);
     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();
+  bool UpdateMaxCoverage();
 
   // 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();
   // Stop tracing.
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;
+
+  // Maximum recorded coverage.
+  Coverage 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 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() {
   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,
-           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);
 }
 
 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::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();
+  CoverageController::ResetCounters(Options);
   ExecuteCallback(Data, Size);
-  bool Res = CheckCoverageAfterRun();
+  bool Res = UpdateMaxCoverage();
 
   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();
-
-  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) {
   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();
+  CoverageController::Prepare(Options, &MaxCoverage);
 }
 
 // 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/FuzzerTracePC.h

+//===- FuzzerTracePC.h - INTERNAL - Path tracer i-face. --------*- C++ -* ===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Define the main class fuzzer::Fuzzer and most functions.
+//===----------------------------------------------------------------------===//
+
+#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() { 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;
+  }
+
+  inline 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.
+size_t PcMapMergeInto(PcCoverageMap *Map);
+}
+
+#endif

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))));
 }