Add ModuleInfo to TracePC

[aarongreen]

Summary

This change adds a ModuleInfo struct to fuzzer::TracePC, and functions to populate such structs with details about the currently loaded modules.

It also offsets some of the space increase of storing the hash in the PC tables by removing some unused fields from the Counter regions.

[aarongreen]

Rebase

[morehouse]

compiler-rt/lib/fuzzer/FuzzerDSORelative.h

28 ↗

(On Diff #321772)

Please add comments explaining each struct member.

compiler-rt/lib/fuzzer/FuzzerTracePC.cpp

50

reinterpret_cast

60

reinterpret_cast

62

260

Please add a comment explaining why we calculate LastFeature this way.

[aarongreen]

Addressing morehouse's comments. Also adjusted size and stack depth functions in TracePC to address some concerns that are in the following change (D94514), but are rleated to files and functions being changed here.

compiler-rt/lib/fuzzer/FuzzerTracePC.cpp

50

Used Module::Size() instead.

60

static_cast works, whereas reinterpret_cast does not.

[morehouse]

compiler-rt/lib/fuzzer/FuzzerTracePC.cpp

59

Please fix this lint.

251

[aarongreen]

fyi: I'd like D97992 to land first; and for this change to be rebased on top of that.

[aarongreen]

Changed DsoInfo to ModuleInfo (and changed PrintModuleInfo to PrintModuleSummary). Moved asserts in CollectFeatures to unit tests.

[aarongreen]

Moved the ModuleInfo struct from FuzzerModuleRelative.h to FuzzerTracePC.h and added MoudleInfoByHash. Along with the decision in D94514 to not support relative features when -fork=1, this obviates the need for D94508 and D94509.

[aarongreen]

Multiprocess fuzzing will not be supported by the libFuzzer maintainers. Fuchsia has implemented a new approach with their Component Fuzzing Framework (RFC-117).

compiler-rt/lib/fuzzer/FuzzerLoop.cpp

Fuzzer::Fuzzer(UserCallback CB, InputCorpus &Corpus, MutationDispatcher &MD,
   TPC.ResetMaps();
   IsMyThread = true;
   if (Options.DetectLeaks && EF->__sanitizer_install_malloc_and_free_hooks)
     EF->__sanitizer_install_malloc_and_free_hooks(MallocHook, FreeHook);
   TPC.SetUseCounters(Options.UseCounters);
   TPC.SetUseValueProfileMask(Options.UseValueProfile);
 
   if (Options.Verbosity)
-    TPC.PrintModuleInfo();
+    TPC.PrintModuleSummary();
   if (!Options.OutputCorpus.empty() && Options.ReloadIntervalSec)
     EpochOfLastReadOfOutputCorpus = GetEpoch(Options.OutputCorpus);
   MaxInputLen = MaxMutationLen = Options.MaxLen;
   TmpMaxMutationLen = 0;  // Will be set once we load the corpus.
   AllocateCurrentUnitData();
   CurrentUnitSize = 0;
   memset(BaseSha1, 0, sizeof(BaseSha1));
 }
bool Fuzzer::RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile,
   assert(Size < std::numeric_limits<uint32_t>::max());
 
   ExecuteCallback(Data, Size);
   auto TimeOfUnit = duration_cast<microseconds>(UnitStopTime - UnitStartTime);
 
   UniqFeatureSetTmp.clear();
   size_t FoundUniqFeaturesOfII = 0;
   size_t NumUpdatesBefore = Corpus.NumFeatureUpdates();
-  TPC.CollectFeatures([&](uint32_t Feature) {
+  TPC.CollectFeatures([&](size_t Feature) {
     if (Corpus.AddFeature(Feature, static_cast<uint32_t>(Size), Options.Shrink))
-      UniqFeatureSetTmp.push_back(Feature);
+      UniqFeatureSetTmp.push_back(static_cast<uint32_t>(Feature));
     if (Options.Entropic)
       Corpus.UpdateFeatureFrequency(II, Feature);
     if (Options.ReduceInputs && II && !II->NeverReduce)
       if (std::binary_search(II->UniqFeatureSet.begin(),
                              II->UniqFeatureSet.end(), Feature))
         FoundUniqFeaturesOfII++;
   });
   if (FoundUniqFeatures)

compiler-rt/lib/fuzzer/FuzzerTracePC.h

for (size_t i = 0; i < kSize; i++) {
       const Word &W = MemMemWords[(Idx + i) % kSize];
       if (W.size()) return W;
     }
     EmptyWord.Set(nullptr, 0);
     return EmptyWord;
   }
 };
 
+struct ModuleInfo {
+  // 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 ModuleInfo
+  // struct with an offset greater than the length of the array as
+  // uninitialized.
+  size_t PCTableOffset = std::numeric_limits<size_t>::max();
+};
+
 class TracePC {
- public:
   void 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 <class T> 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();
   template <class Callback> size_t CollectFeatures(Callback CB) const;
 
   void ResetMaps() {
     ValueProfileMap.Reset();
     ClearExtraCounters();
     ClearInlineCounters();
   }
 
   void ClearInlineCounters();
 
   void UpdateFeatureSet(size_t CurrentElementIdx, size_t CurrentElementSize);
   void PrintFeatureSet();
 
-  void PrintModuleInfo();
+  void PrintModuleSummary();
 
   void PrintCoverage(bool PrintAllCounters);
 
   template<class CallBack>
   void IterateCoveredFunctions(CallBack CB);
 
   void AddValueForMemcmp(void *caller_pc, const void *s1, const void *s2,
                          size_t n, bool StopAtZero);
 
   TableOfRecentCompares<uint32_t, 32> TORC4;
   TableOfRecentCompares<uint64_t, 32> TORC8;
   TableOfRecentCompares<Word, 32> TORCW;
   MemMemTable<1024> MMT;
 
   void RecordInitialStack();
   uintptr_t GetMaxStackOffset() const;
 
+  // Step function, grows similar to 8 * Log_2(A).
+  static size_t StackDepthStepFunction(uintptr_t A);
+  static const size_t kMaxStackDepthFeature = 512;
+
   template<class CallBack>
   void ForEachObservedPC(CallBack CB) {
     for (auto PC : ObservedPCs)
       CB(PC);
   }
 
   void SetFocusFunction(const std::string &FuncName);
   bool ObservedFocusFunction();
 
   struct PCTableEntry {
     uintptr_t PC, PCFlags;
   };
 
   uintptr_t PCTableEntryIdx(const PCTableEntry *TE);
   const PCTableEntry *PCTableEntryByIdx(uintptr_t Idx);
+  const PCTableEntry *PCTableEntryByModule(uint64_t Hash, uintptr_t Offset);
   static uintptr_t GetNextInstructionPc(uintptr_t PC);
   bool PcIsFuncEntry(const PCTableEntry *TE) { return TE->PCFlags & 1; }
 
+  bool ModuleInfoByHash(uint64_t Hash, ModuleInfo *Info);
+  bool ModuleInfoByFeature(size_t Feature, ModuleInfo *Info);
+  bool ModuleInfoByIdx(uintptr_t Idx, ModuleInfo *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;
   bool DoPrintNewPCs = false;
   size_t NumPrintNewFuncs = 0;
 
   // Module represents the array of 8-bit counters split into regions
   // such that every region, except maybe the first and the last one, is one
   // full page.
   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();
     }
   };
 
   Module Modules[4096];
   size_t NumModules;  // linker-initialized.
   size_t NumInline8bitCounters;
 
   template <class Callback>
   void IterateCounterRegions(Callback CB) {
     for (size_t m = 0; m < NumModules; m++)
       for (size_t r = 0; r < Modules[m].NumRegions; r++)
         CB(Modules[m].Regions[r]);
   }
 
-  struct { const PCTableEntry *Start, *Stop; } ModulePCTable[4096];
+  // If |Info| represents a module other than the last one in the array, this
+  // method will update |Info| to represent the next module in the array and
+  // return true. Otherwise, if |Info| is the last module or invalid, it will
+  // update |Info| to represent the first module in the array and return false.
+  // A series of calls to |NextModuleInfo| can be used to iterate over the
+  // |Modules| array.
+  bool NextModuleInfo(ModuleInfo *Info);
+
+  struct {
+    const PCTableEntry *Start, *Stop;
+    uint64_t Hash;
+    size_t Size() const { return Stop - Start; }
+  } ModulePCTable[4096];
   size_t NumPCTables;
   size_t NumPCsInPCTables;
 
   Set<const PCTableEntry*> ObservedPCs;
   std::unordered_map<uintptr_t, uintptr_t> ObservedFuncs;  // PC => Counter.
 
   uint8_t *FocusFunctionCounterPtr = nullptr;
 
unsigned CounterToFeature(T Counter) {
     else if (Counter >= 16) Bit = 5;
     else if (Counter >= 8) Bit = 4;
     else if (Counter >= 4) Bit = 3;
     else if (Counter >= 3) Bit = 2;
     else if (Counter >= 2) Bit = 1;
     return Bit;
 }
 
-template <class Callback> // void Callback(uint32_t Feature)
+template <class Callback> // void Callback(size_t Feature)
 ATTRIBUTE_NO_SANITIZE_ADDRESS ATTRIBUTE_NOINLINE size_t
 TracePC::CollectFeatures(Callback HandleFeature) const {
   auto Handle8bitCounter = [&](size_t FirstFeature,
                                size_t Idx, uint8_t Counter) {
     if (UseCounters)
-      HandleFeature(static_cast<uint32_t>(FirstFeature + Idx * 8 +
-                                          CounterToFeature(Counter)));
+      HandleFeature(FirstFeature + Idx * 8 + CounterToFeature(Counter));
     else
-      HandleFeature(static_cast<uint32_t>(FirstFeature + Idx));
+      HandleFeature(FirstFeature + Idx);
   };
 
   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(),
                              FirstFeature, Handle8bitCounter);
 
   if (UseValueProfileMask) {
-    ValueProfileMap.ForEach([&](size_t Idx) {
-      HandleFeature(static_cast<uint32_t>(FirstFeature + Idx));
-    });
+    ValueProfileMap.ForEach(
+        [&](size_t Idx) { HandleFeature(FirstFeature + Idx); });
     FirstFeature += ValueProfileMap.SizeInBits();
   }
 
-  // Step function, grows similar to 8 * Log_2(A).
-  auto StackDepthStepFunction = [](size_t A) -> size_t {
-    if (!A)
-      return A;
-    auto 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(static_cast<uint32_t>(
-        FirstFeature + StackDepthStepFunction(MaxStackOffset / 8)));
-    FirstFeature += StackDepthStepFunction(std::numeric_limits<size_t>::max());
+    HandleFeature(FirstFeature + StackDepthStepFunction(MaxStackOffset / 8));
+    FirstFeature += kMaxStackDepthFeature;
   }
 
   return FirstFeature;
 }
 
 extern TracePC TPC;
 
 }  // namespace fuzzer
 
 #endif  // LLVM_FUZZER_TRACE_PC

compiler-rt/lib/fuzzer/FuzzerTracePC.cpp

 #include "FuzzerValueBitMap.h"
 #include <set>
 
 // Used by -fsanitize-coverage=stack-depth to track stack depth
 ATTRIBUTES_INTERFACE_TLS_INITIAL_EXEC uintptr_t __sancov_lowest_stack;
 
 namespace fuzzer {
 
+const size_t TracePC::kMaxStackDepthFeature;
+
 TracePC TPC;
 
 size_t TracePC::GetTotalPCCoverage() {
   return ObservedPCs.size();
 }
 
-
 void TracePC::HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop) {
-  if (Start == Stop) return;
-  if (NumModules &&
-      Modules[NumModules - 1].Start() == Start)
+  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);
+  assert(NumModules < sizeof(Modules) / sizeof(Modules[0]));
+  HandleInline8bitCountersInit(Start, Stop, NumModules++);
+  NumInline8bitCounters += Modules[NumModules - 1].Size();
+}
+
+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<size_t>(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<const PCTableEntry *>(Start);
   const PCTableEntry *E = reinterpret_cast<const PCTableEntry *>(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;
 }
 
-void TracePC::PrintModuleInfo() {
+void TracePC::PrintModuleSummary() {
   if (NumModules) {
     Printf("INFO: Loaded %zd modules   (%zd inline 8-bit counters): ",
            NumModules, NumInline8bitCounters);
     for (size_t i = 0; i < NumModules; i++)
       Printf("%zd [%p, %p), ", Modules[i].Size(), Modules[i].Start(),
              Modules[i].Stop());
     Printf("\n");
   }
   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) {
       Printf("ERROR: The size of coverage PC tables does not match the\n"
              "number of instrumented PCs. This might be a compiler bug,\n"
              "please contact the libFuzzer developers.\n"
              "Also check https://bugs.llvm.org/show_bug.cgi?id=34636\n"
              "for possible workarounds (tl;dr: don't use the old GNU ld)\n");
       _Exit(1);
     }
   }
-  if (size_t NumExtraCounters = ExtraCountersEnd() - ExtraCountersBegin())
+  size_t NumExtraCounters = ExtraCountersEnd() - ExtraCountersBegin();
+  if (NumExtraCounters)
     Printf("INFO: %zd Extra Counters\n", NumExtraCounters);
 
-  size_t MaxFeatures = CollectFeatures([](uint32_t) {});
+  size_t MaxFeatures = CollectFeatures([](size_t) {});
   if (MaxFeatures > std::numeric_limits<uint32_t>::max())
     Printf("WARNING: The coverage PC tables may produce up to %zu features.\n"
            "This exceeds the maximum 32-bit value. Some features may be\n"
            "ignored, and fuzzing may become less precise. If possible,\n"
            "consider refactoring the fuzzer into several smaller fuzzers\n"
            "linked against only a portion of the current target.\n",
            MaxFeatures);
 }
if (PcIsFuncEntry(TE))
         CoveredFuncs.push_back(TE->PC);
     ObservePC(TE);
   };
 
   if (NumPCsInPCTables) {
     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)]);
         }
       }
     }
   }
 
   for (size_t i = 0, N = Min(CoveredFuncs.size(), NumPrintNewFuncs); i < N;
        i++) {
     Printf("\tNEW_FUNC[%zd/%zd]: ", i + 1, CoveredFuncs.size());
     PrintPC("%p %F %L", "%p", GetNextInstructionPc(CoveredFuncs[i]));
     Printf("\n");
   }
 }
 
 uintptr_t TracePC::PCTableEntryIdx(const PCTableEntry *TE) {
   size_t TotalTEs = 0;
   for (size_t i = 0; i < NumPCTables; i++) {
     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;
 }
 
 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::PCTableEntryByModule(uint64_t Hash,
+                                                           uintptr_t Offset) {
+  for (size_t i = 0; i < NumPCTables; i++) {
+    auto &M = ModulePCTable[i];
+    if (Hash == M.Hash && Offset < M.Size())
+      return &M.Start[Offset];
+  }
+  return nullptr;
+}
+
+uint64_t TracePC::HashPCs(const uintptr_t *Start, const uintptr_t *End) {
+  const PCTableEntry *B = reinterpret_cast<const PCTableEntry *>(Start);
+  const PCTableEntry *E = reinterpret_cast<const PCTableEntry *>(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;
+}
+
+bool TracePC::NextModuleInfo(ModuleInfo *Info) {
+  assert(NumModules == NumPCTables);
+  // Use an invalid offset 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) {
+    Info->Hash = 0;
+    Info->LastFeature = std::numeric_limits<size_t>::max();
+    Info->LastIdx = std::numeric_limits<uintptr_t>::max();
+    return false;
+  }
+  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 = Info->FirstIdx + PCTable.Size();
+  return true;
+}
+
+bool TracePC::ModuleInfoByHash(uint64_t Hash, ModuleInfo *Info) {
+  Info->PCTableOffset = NumPCTables;
+  while (NextModuleInfo(Info))
+    if (Hash == Info->Hash)
+      return true;
+  return false;
+}
+
+bool TracePC::ModuleInfoByFeature(size_t Feature, ModuleInfo *Info) {
+  Info->PCTableOffset = NumPCTables;
+  while (NextModuleInfo(Info))
+    if (Feature < Info->LastFeature)
+      return true;
+  return false;
+}
+
+bool TracePC::ModuleInfoByIdx(uintptr_t Idx, ModuleInfo *Info) {
+  Info->PCTableOffset = NumPCTables;
+  while (NextModuleInfo(Info))
+    if (Idx < Info->LastIdx)
+      return true;
+  return false;
+}
+
 static std::string GetModuleName(uintptr_t PC) {
   char ModulePathRaw[4096] = "";  // What's PATH_MAX in portable C++?
   void *OffsetRaw = nullptr;
   if (!EF->__sanitizer_get_module_and_offset_for_pc(
       reinterpret_cast<void *>(PC), ModulePathRaw,
       sizeof(ModulePathRaw), &OffsetRaw))
     return "";
   return ModulePathRaw;
void TracePC::SetFocusFunction(const std::string &FuncName) {
   // This function should be called once.
   assert(!FocusFunctionCounterPtr);
   // "auto" is not a valid function name. If this function is called with "auto"
   // that means the auto focus functionality failed.
   if (FuncName.empty() || FuncName == "auto")
     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));
       if (Name[0] == 'i' && Name[1] == 'n' && Name[2] == ' ')
         Name = Name.substr(3, std::string::npos);
       if (FuncName != Name) continue;
       Printf("INFO: Focus function is set to '%s'\n", Name.c_str());
       FocusFunctionCounterPtr = Modules[M].Start() + I;

 // Needed bacause one of these strings may actually be non-zero terminated.
 static size_t InternalStrnlen2(const char *S1, const char *S2) {
   size_t Len = 0;
   for (; S1[Len] && S2[Len]; Len++)  {}
   return Len;
 }
 
 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
 void TracePC::RecordInitialStack() {
   int stack;
   __sancov_lowest_stack = InitialStack = reinterpret_cast<uintptr_t>(&stack);
 }
 
 uintptr_t TracePC::GetMaxStackOffset() const {
   return InitialStack - __sancov_lowest_stack;  // Stack grows down
 }
 
+size_t TracePC::StackDepthStepFunction(uintptr_t A) {
+  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.
   RawPrint(flag);
   RawPrint(
       " is no longer supported by libFuzzer.\n"
       "Please either migrate to a compiler that supports -fsanitize=fuzzer\n"
       "or use an older version of libFuzzer\n");

compiler-rt/lib/fuzzer/tests/CMakeLists.txt

if(CMAKE_SYSTEM_NAME STREQUAL "Linux" AND
     set(LIBFUZZER_TEST_RUNTIME_LINK_FLAGS ${LIBCXX_${arch}_PREFIX}/lib/libc++.a)
   endif()
 
   set(FuzzerTestObjects)
   generate_compiler_rt_tests(FuzzerTestObjects
     FuzzerUnitTests "Fuzzer-${arch}-Test" ${arch}
     SOURCES FuzzerUnittest.cpp ${COMPILER_RT_GTEST_SOURCE}
     RUNTIME ${LIBFUZZER_TEST_RUNTIME}
-    DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS} 
+    DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS} FuzzerTestUtil.h
     CFLAGS ${LIBFUZZER_UNITTEST_CFLAGS} ${LIBFUZZER_TEST_RUNTIME_CFLAGS}
     LINK_FLAGS ${LIBFUZZER_UNITTEST_LINK_FLAGS} ${LIBFUZZER_TEST_RUNTIME_LINK_FLAGS})
   set_target_properties(FuzzerUnitTests PROPERTIES
     RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
 
   set(FuzzedDataProviderTestObjects)
   generate_compiler_rt_tests(FuzzedDataProviderTestObjects
     FuzzedDataProviderUnitTests "FuzzerUtils-${arch}-Test" ${arch}
     SOURCES FuzzedDataProviderUnittest.cpp ${COMPILER_RT_GTEST_SOURCE}
     DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS} ${COMPILER_RT_SOURCE_DIR}/include/fuzzer/FuzzedDataProvider.h
     CFLAGS ${LIBFUZZER_UNITTEST_CFLAGS} ${LIBFUZZER_TEST_RUNTIME_CFLAGS}
     LINK_FLAGS ${LIBFUZZER_UNITTEST_LINK_FLAGS} ${LIBFUZZER_TEST_RUNTIME_LINK_FLAGS})
   set_target_properties(FuzzedDataProviderUnitTests PROPERTIES
     RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
 endif()

compiler-rt/lib/fuzzer/tests/FuzzerTestUtil.h

+//===- FuzzerTestUtil.h -----------------------------------------*- C++ -* ===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Test support shared between unit tests.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_FUZZER_TEST_UTIL_H
+#define LLVM_FUZZER_TEST_UTIL_H
+
+#include "FuzzerTracePC.h"
+#include "gtest/gtest.h"
+#include <cstddef>
+#include <cstdint>
+#include <initializer_list>
+#include <memory>
+#include <vector>
+
+namespace fuzzer {
+
+// Helper environment to ensure that:
+// * The PRNG is seeded deterministically.
+class TestEnvironment : public testing::Environment {
+public:
+  void SetUp() override { srand(0); }
+};
+
+// Test utilities for picking repeatable psuedorandom numbers.
+template <typename T>
+typename std::enable_if<std::is_integral<T>::value, T>::type Pick() {
+  return static_cast<T>(rand() & std::numeric_limits<T>::max());
+}
+
+template <typename T>
+typename std::enable_if<std::is_floating_point<T>::value, T>::type Pick() {
+  auto AbsVal = static_cast<T>(rand()) / static_cast<T>(RAND_MAX);
+  return rand() % 2 ? -AbsVal : AbsVal;
+}
+
+// Helper struct for creating coverage data for unit tests. Note that once
+// memory is added to the |fuzzer::TracePC| singleton, that object will assume
+// it is valid for its lifetime, i.e. the remainder of the process. This can
+// cause issues if unit tests are repeated, i.e. -gtest_repeat=<n>. Avoid this
+// by declaring the FakeModule static within the test that adds it to the
+// coverage.
+template <size_t N> struct FakeModule final {
+public:
+  uint8_t Counters[N];
+  uintptr_t PCs[N * 2];
+  const size_t NumPCs = N;
+
+  FakeModule() {
+    memset(Counters, 0, sizeof(Counters));
+    auto *TE = GetPCTableEntries();
+    uintptr_t PC = Pick<uintptr_t>() & ((1ULL << 48) - 1);
+    for (size_t i = 0; i < N; ++i) {
+      TE[i].PC = PC;
+      TE[i].PCFlags = i == 0 || (rand() % 16) == 0;
+      PC += Pick<uint16_t>();
+    }
+  }
+
+  uint8_t *CountersEnd() { return Counters + N; }
+  uintptr_t *PCsEnd() { return PCs + (N * 2); }
+
+  TracePC::PCTableEntry *GetPCTableEntries() {
+    return reinterpret_cast<TracePC::PCTableEntry *>(PCs);
+  }
+
+  uint64_t Hash() { return TracePC::HashPCs(PCs, PCsEnd()); }
+
+  // Adds the Module to the |fuzzer::TracePC| if not already added. Returns the
+  // the index of the first PC for the module.
+  uintptr_t AddToTPC() {
+    auto *B = reinterpret_cast<const TracePC::PCTableEntry *>(PCs);
+    uintptr_t Idx = 0;
+    for (auto *T = TPC.PCTableEntryByIdx(Idx); T;
+         T = TPC.PCTableEntryByIdx(++Idx))
+      if (T == B)
+        return Idx;
+    TPC.HandlePCsInit(PCs, PCsEnd());
+    TPC.HandleInline8bitCountersInit(Counters, CountersEnd());
+    return Idx;
+  }
+};
+
+} // namespace fuzzer
+
+#endif // LLVM_FUZZER_TEST_UTIL_H

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

 
 #include "FuzzerCorpus.h"
 #include "FuzzerDictionary.h"
 #include "FuzzerInternal.h"
 #include "FuzzerMerge.h"
 #include "FuzzerMutate.h"
 #include "FuzzerRandom.h"
 #include "FuzzerTracePC.h"
+#include "tests/FuzzerTestUtil.h"
 #include "gtest/gtest.h"
 #include <memory>
 #include <set>
 #include <sstream>
 
 using namespace fuzzer;
 
 // For now, have LLVMFuzzerTestOneInput just to make it link.
for (size_t i = 0; i < N * TriesPerUnit; i++) {
     Hist[C->ChooseUnitIdxToMutate(Rand)]++;
   }
   for (size_t i = 0; i < N; i++) {
     // A weak sanity check that every unit gets invoked.
     EXPECT_GT(Hist[i], TriesPerUnit / N / 3);
   }
 }
 
+TEST(TracePC, StackDepthFunction) {
+  EXPECT_EQ(TracePC::StackDepthStepFunction(1024), 64U);
+  EXPECT_EQ(TracePC::StackDepthStepFunction(1024 * 4), 80U);
+  EXPECT_EQ(TracePC::StackDepthStepFunction(1024 * 1024), 144U);
+  EXPECT_LT(TracePC::StackDepthStepFunction(
+                std::numeric_limits<uintptr_t>::max() / 8),
+            TracePC::kMaxStackDepthFeature);
+}
+
 template <typename T> void EQ(const Vector<T> &A, const Vector<T> &B) {
   EXPECT_EQ(A, B);
 }
 
 template <typename T> void EQ(const Set<T> &A, const Vector<T> &B) {
   EXPECT_EQ(A, Set<T>(B.begin(), B.end()));
 }
 
 void EQ(const Vector<MergeFileInfo> &A, const Vector<std::string> &B) {
   Set<std::string> a;
   for (const auto &File : A)
     a.insert(File.Name);
   Set<std::string> b(B.begin(), B.end());
   EXPECT_EQ(a, b);
 }
 
 #define TRACED_EQ(A, ...)                                                      \
   {                                                                            \
     SCOPED_TRACE(#A);                                                          \
     EQ(A, __VA_ARGS__);                                                        \
   }
 
+// Helper functions to test TracePC's module functions using FakeModules of
+// various sizes.
+template <size_t N> void VerifyFeatures(FakeModule<N> &M, bool UseCounters) {
+  ModuleInfo Info;
+
+  // Each of the given features should appear in sorted order and map back to
+  // this module...
+  Vector<uint32_t> AllFeatures;
+  uint32_t Last = 0;
+  TPC.CollectFeatures([&](size_t Feature) {
+    if (Last)
+      EXPECT_LT(Last, Feature);
+    AllFeatures.push_back(static_cast<uint32_t>(Feature));
+    Last = Feature;
+  });
+
+  auto Hash = M.Hash();
+  EXPECT_TRUE(TPC.ModuleInfoByHash(Hash, &Info));
+
+  Vector<uint32_t> Features;
+  for (auto F : AllFeatures)
+    if (Info.FirstFeature <= F && F < Info.LastFeature)
+      Features.push_back(F);
+  EXPECT_EQ(Features.size(), N);
+
+  for (auto F : Features) {
+    EXPECT_TRUE(TPC.ModuleInfoByFeature(F, &Info));
+    EXPECT_EQ(Hash, Info.Hash);
+  }
+}
+
+template <size_t N> void VerifyPCs(FakeModule<N> &M) {
+  ModuleInfo Info;
+
+  // The given module's PCTableEntries should to an index, which in turn should
+  // correspond to ModuleInfo that represents the module.
+  const auto *TE = M.GetPCTableEntries();
+  auto Hash = M.Hash();
+  for (size_t i = 0; i < M.NumPCs; ++i) {
+    auto Idx = TPC.PCTableEntryIdx(&TE[i]);
+    EXPECT_TRUE(TPC.ModuleInfoByIdx(Idx, &Info));
+    EXPECT_EQ(Hash, Info.Hash);
+    EXPECT_LT(Idx, Info.LastIdx);
+    EXPECT_GE(Idx, Info.FirstIdx);
+  }
+
+  // For the given module's hash, |PCTableEntryByModule| with an offset in
+  // [0, NumPCs) should yield a valid PCTableEntry...
+  TE = TPC.PCTableEntryByModule(Hash, 0);
+  ASSERT_NE(TE, nullptr);
+  EXPECT_EQ(TPC.PCTableEntryIdx(TE), Info.FirstIdx);
+
+  TE = TPC.PCTableEntryByModule(Hash, M.NumPCs - 1);
+  ASSERT_NE(TE, nullptr);
+  EXPECT_EQ(TPC.PCTableEntryIdx(TE), Info.LastIdx - 1);
+
+  // ...but a bad hash or offset that should return null.
+  EXPECT_EQ(TPC.PCTableEntryByModule(~Hash, 0), nullptr);
+  EXPECT_EQ(TPC.PCTableEntryByModule(Hash, M.NumPCs), nullptr);
+}
+
+TEST(TracePC, ModuleInfo) {
+  TPC.ResetMaps();
+
+  // Add modules. They will be added to TPC, so make them static to allow the
+  // test to be run multiple times.
+  static FakeModule<64> M1;
+  M1.AddToTPC();
+  static FakeModule<512> M2;
+  M2.AddToTPC();
+  static FakeModule<4096> M3;
+  M3.AddToTPC();
+
+  for (size_t i = 0; i < 2; ++i) {
+    bool UseCounters = i == 1;
+    TPC.SetUseCounters(UseCounters);
+    TPC.ResetMaps();
+    memset(M1.Counters, 1, M1.NumPCs * sizeof(uint8_t));
+    memset(M2.Counters, 8, M2.NumPCs * sizeof(uint8_t));
+    memset(M3.Counters, 0x80, M3.NumPCs * sizeof(uint8_t));
+    VerifyFeatures(M1, UseCounters);
+    VerifyFeatures(M2, UseCounters);
+    VerifyFeatures(M3, UseCounters);
+  }
+
+  VerifyPCs(M1);
+  VerifyPCs(M2);
+  VerifyPCs(M3);
+}
+
 TEST(Merger, Parse) {
   Merger M;
 
   const char *kInvalidInputs[] = {
       // Bad file numbers
       "",
       "x",
       "0\n0",