Import LLVM 4.0.0 rc1 including clang and lld to help the current

development effort on OpenBSD/arm64.

1 files changed, 339 insertions, 313 deletions

diff --git a/gnu/llvm/lib/Fuzzer/FuzzerLoop.cpp b/gnu/llvm/lib/Fuzzer/FuzzerLoop.cpp
index 89db5e0ac0a..9f49d155799 100644
--- a/gnu/llvm/lib/Fuzzer/FuzzerLoop.cpp
+++ b/gnu/llvm/lib/Fuzzer/FuzzerLoop.cpp
@@ -9,10 +9,16 @@
 // Fuzzer's main loop.
 //===----------------------------------------------------------------------===//
 
+#include "FuzzerCorpus.h"
 #include "FuzzerInternal.h"
+#include "FuzzerIO.h"
+#include "FuzzerMutate.h"
+#include "FuzzerRandom.h"
+#include "FuzzerTracePC.h"
 #include <algorithm>
 #include <cstring>
 #include <memory>
+#include <set>
 
 #if defined(__has_include)
 #if __has_include(<sanitizer / coverage_interface.h>)
@@ -33,7 +39,6 @@
 
 namespace fuzzer {
 static const size_t kMaxUnitSizeToPrint = 256;
-static const size_t TruncateMaxRuns = 1000;
 
 thread_local bool Fuzzer::IsMyThread;
 
@@ -53,112 +58,152 @@ static void MissingExternalApiFunction(const char *FnName) {
 // Only one Fuzzer per process.
 static Fuzzer *F;
 
-struct CoverageController {
-  static void Reset() {
-    CHECK_EXTERNAL_FUNCTION(__sanitizer_reset_coverage);
-    EF->__sanitizer_reset_coverage();
-    PcMapResetCurrent();
-  }
+void Fuzzer::ResetEdgeCoverage() {
+  CHECK_EXTERNAL_FUNCTION(__sanitizer_reset_coverage);
+  EF->__sanitizer_reset_coverage();
+}
 
-  static void ResetCounters(const FuzzingOptions &Options) {
-    if (Options.UseCounters) {
-      EF->__sanitizer_update_counter_bitset_and_clear_counters(0);
-    }
-  }
+void Fuzzer::ResetCounters() {
+  if (Options.UseCounters)
+    EF->__sanitizer_update_counter_bitset_and_clear_counters(0);
+}
 
-  static void Prepare(const FuzzingOptions &Options, Fuzzer::Coverage *C) {
-    if (Options.UseCounters) {
-      size_t NumCounters = EF->__sanitizer_get_number_of_counters();
-      C->CounterBitmap.resize(NumCounters);
-    }
+void Fuzzer::PrepareCounters(Fuzzer::Coverage *C) {
+  if (Options.UseCounters) {
+    size_t NumCounters = EF->__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 FuzzingOptions &Options, Fuzzer::Coverage *C) {
-    bool Res = false;
-
-    uint64_t NewBlockCoverage = EF->__sanitizer_get_total_unique_coverage();
-    if (NewBlockCoverage > C->BlockCoverage) {
-      Res = true;
-      C->BlockCoverage = NewBlockCoverage;
-    }
-
-    if (Options.UseIndirCalls &&
-        EF->__sanitizer_get_total_unique_caller_callee_pairs) {
-      uint64_t NewCallerCalleeCoverage =
-          EF->__sanitizer_get_total_unique_caller_callee_pairs();
-      if (NewCallerCalleeCoverage > C->CallerCalleeCoverage) {
-        Res = true;
-        C->CallerCalleeCoverage = NewCallerCalleeCoverage;
-      }
-    }
+// Records data to a maximum coverage tracker. Returns true if additional
+// coverage was discovered.
+bool Fuzzer::RecordMaxCoverage(Fuzzer::Coverage *C) {
+  bool Res = false;
 
-    if (Options.UseCounters) {
-      uint64_t CounterDelta =
-          EF->__sanitizer_update_counter_bitset_and_clear_counters(
-              C->CounterBitmap.data());
-      if (CounterDelta > 0) {
-        Res = true;
-        C->CounterBitmapBits += CounterDelta;
-      }
-    }
+  uint64_t NewBlockCoverage = EF->__sanitizer_get_total_unique_coverage();
+  if (NewBlockCoverage > C->BlockCoverage) {
+    Res = true;
+    C->BlockCoverage = NewBlockCoverage;
+  }
 
-    uint64_t NewPcMapBits = PcMapMergeInto(&C->PCMap);
-    if (NewPcMapBits > C->PcMapBits) {
+  if (Options.UseIndirCalls &&
+      EF->__sanitizer_get_total_unique_caller_callee_pairs) {
+    uint64_t NewCallerCalleeCoverage =
+        EF->__sanitizer_get_total_unique_caller_callee_pairs();
+    if (NewCallerCalleeCoverage > C->CallerCalleeCoverage) {
       Res = true;
-      C->PcMapBits = NewPcMapBits;
+      C->CallerCalleeCoverage = NewCallerCalleeCoverage;
     }
+  }
 
-    uintptr_t *CoverageBuf;
-    uint64_t NewPcBufferLen =
-        EF->__sanitizer_get_coverage_pc_buffer(&CoverageBuf);
-    if (NewPcBufferLen > C->PcBufferLen) {
+  if (Options.UseCounters) {
+    uint64_t CounterDelta =
+        EF->__sanitizer_update_counter_bitset_and_clear_counters(
+            C->CounterBitmap.data());
+    if (CounterDelta > 0) {
       Res = true;
-      C->PcBufferLen = NewPcBufferLen;
+      C->CounterBitmapBits += CounterDelta;
     }
-
-    return Res;
   }
-};
+
+  return Res;
+}
 
 // Leak detection is expensive, so we first check if there were more mallocs
 // than frees (using the sanitizer malloc hooks) and only then try to call lsan.
 struct MallocFreeTracer {
-  void Start() {
+  void Start(int TraceLevel) {
+    this->TraceLevel = TraceLevel;
+    if (TraceLevel)
+      Printf("MallocFreeTracer: START\n");
     Mallocs = 0;
     Frees = 0;
   }
   // Returns true if there were more mallocs than frees.
-  bool Stop() { return Mallocs > Frees; }
+  bool Stop() {
+    if (TraceLevel)
+      Printf("MallocFreeTracer: STOP %zd %zd (%s)\n", Mallocs.load(),
+             Frees.load(), Mallocs == Frees ? "same" : "DIFFERENT");
+    bool Result = Mallocs > Frees;
+    Mallocs = 0;
+    Frees = 0;
+    TraceLevel = 0;
+    return Result;
+  }
   std::atomic<size_t> Mallocs;
   std::atomic<size_t> Frees;
+  int TraceLevel = 0;
 };
 
 static MallocFreeTracer AllocTracer;
 
+ATTRIBUTE_NO_SANITIZE_MEMORY
 void MallocHook(const volatile void *ptr, size_t size) {
-  AllocTracer.Mallocs++;
+  size_t N = AllocTracer.Mallocs++;
+  F->HandleMalloc(size);
+  if (int TraceLevel = AllocTracer.TraceLevel) {
+    Printf("MALLOC[%zd] %p %zd\n", N, ptr, size);
+    if (TraceLevel >= 2 && EF)
+      EF->__sanitizer_print_stack_trace();
+  }
 }
+
+ATTRIBUTE_NO_SANITIZE_MEMORY
 void FreeHook(const volatile void *ptr) {
-  AllocTracer.Frees++;
+  size_t N = AllocTracer.Frees++;
+  if (int TraceLevel = AllocTracer.TraceLevel) {
+    Printf("FREE[%zd]   %p\n", N, ptr);
+    if (TraceLevel >= 2 && EF)
+      EF->__sanitizer_print_stack_trace();
+  }
+}
+
+// Crash on a single malloc that exceeds the rss limit.
+void Fuzzer::HandleMalloc(size_t Size) {
+  if (!Options.RssLimitMb || (Size >> 20) < (size_t)Options.RssLimitMb)
+    return;
+  Printf("==%d== ERROR: libFuzzer: out-of-memory (malloc(%zd))\n", GetPid(),
+         Size);
+  Printf("   To change the out-of-memory limit use -rss_limit_mb=<N>\n\n");
+  if (EF->__sanitizer_print_stack_trace)
+    EF->__sanitizer_print_stack_trace();
+  DumpCurrentUnit("oom-");
+  Printf("SUMMARY: libFuzzer: out-of-memory\n");
+  PrintFinalStats();
+  _Exit(Options.ErrorExitCode); // Stop right now.
 }
 
-Fuzzer::Fuzzer(UserCallback CB, MutationDispatcher &MD, FuzzingOptions Options)
-    : CB(CB), MD(MD), Options(Options) {
+Fuzzer::Fuzzer(UserCallback CB, InputCorpus &Corpus, MutationDispatcher &MD,
+               FuzzingOptions Options)
+    : CB(CB), Corpus(Corpus), MD(MD), Options(Options) {
   SetDeathCallback();
   InitializeTraceState();
   assert(!F);
   F = this;
+  TPC.ResetMaps();
   ResetCoverage();
   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.SetUseValueProfile(Options.UseValueProfile);
+  TPC.SetPrintNewPCs(Options.PrintNewCovPcs);
+
+  if (Options.Verbosity)
+    TPC.PrintModuleInfo();
+  if (!Options.OutputCorpus.empty() && Options.ReloadIntervalSec)
+    EpochOfLastReadOfOutputCorpus = GetEpoch(Options.OutputCorpus);
+  MaxInputLen = MaxMutationLen = Options.MaxLen;
+  AllocateCurrentUnitData();
+  CurrentUnitSize = 0;
+  memset(BaseSha1, 0, sizeof(BaseSha1));
 }
 
-void Fuzzer::LazyAllocateCurrentUnitData() {
-  if (CurrentUnitData || Options.MaxLen == 0) return;
-  CurrentUnitData = new uint8_t[Options.MaxLen];
+Fuzzer::~Fuzzer() { }
+
+void Fuzzer::AllocateCurrentUnitData() {
+  if (CurrentUnitData || MaxInputLen == 0) return;
+  CurrentUnitData = new uint8_t[MaxInputLen];
 }
 
 void Fuzzer::SetDeathCallback() {
@@ -171,8 +216,26 @@ void Fuzzer::StaticDeathCallback() {
   F->DeathCallback();
 }
 
+static void WarnOnUnsuccessfullMerge(bool DoWarn) {
+  if (!DoWarn) return;
+  Printf(
+   "***\n"
+   "***\n"
+   "***\n"
+   "*** NOTE: merge did not succeed due to a failure on one of the inputs.\n"
+   "*** You will need to filter out crashes from the corpus, e.g. like this:\n"
+   "***   for f in WITH_CRASHES/*; do ./fuzzer $f && cp $f NO_CRASHES; done\n"
+   "*** Future versions may have crash-resistant merge, stay tuned.\n"
+   "***\n"
+   "***\n"
+   "***\n");
+}
+
 void Fuzzer::DumpCurrentUnit(const char *Prefix) {
+  WarnOnUnsuccessfullMerge(InMergeMode);
   if (!CurrentUnitData) return;  // Happens when running individual inputs.
+  MD.PrintMutationSequence();
+  Printf("; base unit: %s\n", Sha1ToString(BaseSha1).c_str());
   size_t UnitSize = CurrentUnitSize;
   if (UnitSize <= kMaxUnitSizeToPrint) {
     PrintHexArray(CurrentUnitData, UnitSize, "\n");
@@ -203,8 +266,13 @@ void Fuzzer::StaticInterruptCallback() {
   F->InterruptCallback();
 }
 
+void Fuzzer::StaticFileSizeExceedCallback() {
+  Printf("==%lu== ERROR: libFuzzer: file size exceeded\n", GetPid());
+  exit(1);
+}
+
 void Fuzzer::CrashCallback() {
-  Printf("==%d== ERROR: libFuzzer: deadly signal\n", GetPid());
+  Printf("==%lu== ERROR: libFuzzer: deadly signal\n", GetPid());
   if (EF->__sanitizer_print_stack_trace)
     EF->__sanitizer_print_stack_trace();
   Printf("NOTE: libFuzzer has rudimentary signal handlers.\n"
@@ -217,7 +285,7 @@ void Fuzzer::CrashCallback() {
 }
 
 void Fuzzer::InterruptCallback() {
-  Printf("==%d== libFuzzer: run interrupted; exiting\n", GetPid());
+  Printf("==%lu== libFuzzer: run interrupted; exiting\n", GetPid());
   PrintFinalStats();
   _Exit(0);  // Stop right now, don't perform any at-exit actions.
 }
@@ -226,7 +294,7 @@ NO_SANITIZE_MEMORY
 void Fuzzer::AlarmCallback() {
   assert(Options.UnitTimeoutSec > 0);
   if (!InFuzzingThread()) return;
-  if (!CurrentUnitSize)
+  if (!RunningCB)
     return; // We have not started running units yet.
   size_t Seconds =
       duration_cast<seconds>(system_clock::now() - UnitStartTime).count();
@@ -239,7 +307,7 @@ void Fuzzer::AlarmCallback() {
     Printf("       and the timeout value is %d (use -timeout=N to change)\n",
            Options.UnitTimeoutSec);
     DumpCurrentUnit("timeout-");
-    Printf("==%d== ERROR: libFuzzer: timeout after %d seconds\n", GetPid(),
+    Printf("==%lu== ERROR: libFuzzer: timeout after %d seconds\n", GetPid(),
            Seconds);
     if (EF->__sanitizer_print_stack_trace)
       EF->__sanitizer_print_stack_trace();
@@ -251,18 +319,18 @@ void Fuzzer::AlarmCallback() {
 
 void Fuzzer::RssLimitCallback() {
   Printf(
-      "==%d== ERROR: libFuzzer: out-of-memory (used: %zdMb; limit: %zdMb)\n",
+      "==%lu== ERROR: libFuzzer: out-of-memory (used: %zdMb; limit: %zdMb)\n",
       GetPid(), GetPeakRSSMb(), Options.RssLimitMb);
   Printf("   To change the out-of-memory limit use -rss_limit_mb=<N>\n\n");
   if (EF->__sanitizer_print_memory_profile)
-    EF->__sanitizer_print_memory_profile(50);
+    EF->__sanitizer_print_memory_profile(95);
   DumpCurrentUnit("oom-");
   Printf("SUMMARY: libFuzzer: out-of-memory\n");
   PrintFinalStats();
   _Exit(Options.ErrorExitCode); // Stop right now.
 }
 
-void Fuzzer::PrintStats(const char *Where, const char *End) {
+void Fuzzer::PrintStats(const char *Where, const char *End, size_t Units) {
   size_t ExecPerSec = execPerSec();
   if (Options.OutputCSV) {
     static bool csvHeaderPrinted = false;
@@ -280,17 +348,42 @@ void Fuzzer::PrintStats(const char *Where, const char *End) {
   Printf("#%zd\t%s", TotalNumberOfRuns, Where);
   if (MaxCoverage.BlockCoverage)
     Printf(" cov: %zd", MaxCoverage.BlockCoverage);
-  if (MaxCoverage.PcMapBits)
-    Printf(" path: %zd", MaxCoverage.PcMapBits);
+  if (size_t N = MaxCoverage.VPMap.GetNumBitsSinceLastMerge())
+    Printf(" vp: %zd", N);
+  if (size_t N = TPC.GetTotalPCCoverage())
+    Printf(" cov: %zd", N);
   if (auto TB = MaxCoverage.CounterBitmapBits)
     Printf(" bits: %zd", TB);
+  if (size_t N = Corpus.NumFeatures())
+    Printf( " ft: %zd", N);
   if (MaxCoverage.CallerCalleeCoverage)
     Printf(" indir: %zd", MaxCoverage.CallerCalleeCoverage);
-  Printf(" units: %zd exec/s: %zd", Corpus.size(), ExecPerSec);
+  if (!Corpus.empty()) {
+    Printf(" corp: %zd", Corpus.NumActiveUnits());
+    if (size_t N = Corpus.SizeInBytes()) {
+      if (N < (1<<14))
+        Printf("/%zdb", N);
+      else if (N < (1 << 24))
+        Printf("/%zdKb", N >> 10);
+      else
+        Printf("/%zdMb", N >> 20);
+    }
+  }
+  if (Units)
+    Printf(" units: %zd", Units);
+
+  Printf(" exec/s: %zd", ExecPerSec);
+  Printf(" rss: %zdMb", GetPeakRSSMb());
   Printf("%s", End);
 }
 
 void Fuzzer::PrintFinalStats() {
+  if (Options.PrintCoverage)
+    TPC.PrintCoverage();
+  if (Options.DumpCoverage)
+    TPC.DumpCoverage();
+  if (Options.PrintCorpusStats)
+    Corpus.PrintStats();
   if (!Options.PrintFinalStats) return;
   size_t ExecPerSec = execPerSec();
   Printf("stat::number_of_executed_units: %zd\n", TotalNumberOfRuns);
@@ -300,46 +393,66 @@ void Fuzzer::PrintFinalStats() {
   Printf("stat::peak_rss_mb:              %zd\n", GetPeakRSSMb());
 }
 
-size_t Fuzzer::MaxUnitSizeInCorpus() const {
-  size_t Res = 0;
-  for (auto &X : Corpus)
-    Res = std::max(Res, X.size());
-  return Res;
-}
-
-void Fuzzer::SetMaxLen(size_t MaxLen) {
-  assert(Options.MaxLen == 0); // Can only reset MaxLen from 0 to non-0.
-  assert(MaxLen);
-  Options.MaxLen = MaxLen;
-  Printf("INFO: -max_len is not provided, using %zd\n", Options.MaxLen);
+void Fuzzer::SetMaxInputLen(size_t MaxInputLen) {
+  assert(this->MaxInputLen == 0); // Can only reset MaxInputLen from 0 to non-0.
+  assert(MaxInputLen);
+  this->MaxInputLen = MaxInputLen;
+  this->MaxMutationLen = MaxInputLen;
+  AllocateCurrentUnitData();
+  Printf("INFO: -max_len is not provided, using %zd\n", MaxInputLen);
+}
+
+void Fuzzer::SetMaxMutationLen(size_t MaxMutationLen) {
+  assert(MaxMutationLen && MaxMutationLen <= MaxInputLen);
+  this->MaxMutationLen = MaxMutationLen;
+}
+
+void Fuzzer::CheckExitOnSrcPosOrItem() {
+  if (!Options.ExitOnSrcPos.empty()) {
+    static auto *PCsSet = new std::set<uintptr_t>;
+    for (size_t i = 1, N = TPC.GetNumPCs(); i < N; i++) {
+      uintptr_t PC = TPC.GetPC(i);
+      if (!PC) continue;
+      if (!PCsSet->insert(PC).second) continue;
+      std::string Descr = DescribePC("%L", PC);
+      if (Descr.find(Options.ExitOnSrcPos) != std::string::npos) {
+        Printf("INFO: found line matching '%s', exiting.\n",
+               Options.ExitOnSrcPos.c_str());
+        _Exit(0);
+      }
+    }
+  }
+  if (!Options.ExitOnItem.empty()) {
+    if (Corpus.HasUnit(Options.ExitOnItem)) {
+      Printf("INFO: found item with checksum '%s', exiting.\n",
+             Options.ExitOnItem.c_str());
+      _Exit(0);
+    }
+  }
 }
 
-
 void Fuzzer::RereadOutputCorpus(size_t MaxSize) {
-  if (Options.OutputCorpus.empty())
-    return;
+  if (Options.OutputCorpus.empty() || !Options.ReloadIntervalSec) return;
   std::vector<Unit> AdditionalCorpus;
   ReadDirToVectorOfUnits(Options.OutputCorpus.c_str(), &AdditionalCorpus,
-                         &EpochOfLastReadOfOutputCorpus, MaxSize);
-  if (Corpus.empty()) {
-    Corpus = AdditionalCorpus;
-    return;
-  }
-  if (!Options.Reload)
-    return;
+                         &EpochOfLastReadOfOutputCorpus, MaxSize,
+                         /*ExitOnError*/ false);
   if (Options.Verbosity >= 2)
     Printf("Reload: read %zd new units.\n", AdditionalCorpus.size());
-  for (auto &X : AdditionalCorpus) {
-    if (X.size() > MaxSize)
-      X.resize(MaxSize);
-    if (UnitHashesAddedToCorpus.insert(Hash(X)).second) {
-      if (RunOne(X)) {
-        Corpus.push_back(X);
-        UpdateCorpusDistribution();
-        PrintStats("RELOAD");
+  bool Reloaded = false;
+  for (auto &U : AdditionalCorpus) {
+    if (U.size() > MaxSize)
+      U.resize(MaxSize);
+    if (!Corpus.HasUnit(U)) {
+      if (size_t NumFeatures = RunOne(U)) {
+        CheckExitOnSrcPosOrItem();
+        Corpus.AddToCorpus(U, NumFeatures);
+        Reloaded = true;
       }
     }
   }
+  if (Reloaded)
+    PrintStats("RELOAD");
 }
 
 void Fuzzer::ShuffleCorpus(UnitVector *V) {
@@ -350,68 +463,25 @@ void Fuzzer::ShuffleCorpus(UnitVector *V) {
     });
 }
 
-// Tries random prefixes of corpus items.
-// Prefix length is chosen according to exponential distribution
-// to sample short lengths much more heavily.
-void Fuzzer::TruncateUnits(std::vector<Unit> *NewCorpus) {
-  size_t MaxCorpusLen = 0;
-  for (const auto &U : Corpus)
-    MaxCorpusLen = std::max(MaxCorpusLen, U.size());
-
-  if (MaxCorpusLen <= 1)
-    return;
-
-  // 50% of exponential distribution is Log[2]/lambda.
-  // Choose lambda so that median is MaxCorpusLen / 2.
-  double Lambda = 2.0 * log(2.0) / static_cast<double>(MaxCorpusLen);
-  std::exponential_distribution<> Dist(Lambda);
-  std::vector<double> Sizes;
-  size_t TruncatePoints = std::max(1ul, TruncateMaxRuns / Corpus.size());
-  Sizes.reserve(TruncatePoints);
-  for (size_t I = 0; I < TruncatePoints; ++I) {
-    Sizes.push_back(Dist(MD.GetRand().Get_mt19937()) + 1);
-  }
-  std::sort(Sizes.begin(), Sizes.end());
-
-  for (size_t S : Sizes) {
-    for (const auto &U : Corpus) {
-      if (S < U.size() && RunOne(U.data(), S)) {
-        Unit U1(U.begin(), U.begin() + S);
-        NewCorpus->push_back(U1);
-        WriteToOutputCorpus(U1);
-        PrintStatusForNewUnit(U1);
-      }
-    }
-  }
-  PrintStats("TRUNC  ");
-}
-
-void Fuzzer::ShuffleAndMinimize() {
-  PrintStats("READ  ");
-  std::vector<Unit> NewCorpus;
+void Fuzzer::ShuffleAndMinimize(UnitVector *InitialCorpus) {
+  Printf("#0\tREAD units: %zd\n", InitialCorpus->size());
   if (Options.ShuffleAtStartUp)
-    ShuffleCorpus(&Corpus);
+    ShuffleCorpus(InitialCorpus);
 
-  if (Options.TruncateUnits) {
-    ResetCoverage();
-    TruncateUnits(&NewCorpus);
-    ResetCoverage();
-  }
+  // Test the callback with empty input and never try it again.
+  uint8_t dummy;
+  ExecuteCallback(&dummy, 0);
 
-  for (const auto &U : Corpus) {
-    bool NewCoverage = RunOne(U);
-    if (!Options.PruneCorpus || NewCoverage) {
-      NewCorpus.push_back(U);
+  for (const auto &U : *InitialCorpus) {
+    if (size_t NumFeatures = RunOne(U)) {
+      CheckExitOnSrcPosOrItem();
+      Corpus.AddToCorpus(U, NumFeatures);
       if (Options.Verbosity >= 2)
         Printf("NEW0: %zd L %zd\n", MaxCoverage.BlockCoverage, U.size());
     }
     TryDetectingAMemoryLeak(U.data(), U.size(),
                             /*DuringInitialCorpusExecution*/ true);
   }
-  Corpus = NewCorpus;
-  UpdateCorpusDistribution();
-  for (auto &X : Corpus)
-    UnitHashesAddedToCorpus.insert(Hash(X));
   PrintStats("INITED");
   if (Corpus.empty()) {
     Printf("ERROR: no interesting inputs were found. "
@@ -420,37 +490,31 @@ void Fuzzer::ShuffleAndMinimize() {
   }
 }
 
-bool Fuzzer::UpdateMaxCoverage() {
-  uintptr_t PrevBufferLen = MaxCoverage.PcBufferLen;
-  bool Res = CoverageController::RecordMax(Options, &MaxCoverage);
-
-  if (Options.PrintNewCovPcs && PrevBufferLen != MaxCoverage.PcBufferLen) {
-    uintptr_t *CoverageBuf;
-    EF->__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) {
+size_t Fuzzer::RunOne(const uint8_t *Data, size_t Size) {
+  if (!Size) return 0;
   TotalNumberOfRuns++;
 
-  // TODO(aizatsky): this Reset call seems to be not needed.
-  CoverageController::ResetCounters(Options);
   ExecuteCallback(Data, Size);
-  bool Res = UpdateMaxCoverage();
 
-  auto UnitStopTime = system_clock::now();
+  size_t Res = 0;
+  if (size_t NumFeatures = TPC.CollectFeatures([&](size_t Feature) -> bool {
+        return Corpus.AddFeature(Feature, Size, Options.Shrink);
+      }))
+    Res = NumFeatures;
+
+  if (!TPC.UsingTracePcGuard()) {
+    if (TPC.UpdateValueProfileMap(&MaxCoverage.VPMap))
+      Res = 1;
+    if (!Res && RecordMaxCoverage(&MaxCoverage))
+      Res = 1;
+  }
+
   auto TimeOfUnit =
       duration_cast<seconds>(UnitStopTime - UnitStartTime).count();
   if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)) &&
       secondsSinceProcessStartUp() >= 2)
     PrintStats("pulse ");
-  if (TimeOfUnit > TimeOfLongestUnitInSeconds &&
+  if (TimeOfUnit > TimeOfLongestUnitInSeconds * 1.1 &&
       TimeOfUnit >= Options.ReportSlowUnits) {
     TimeOfLongestUnitInSeconds = TimeOfUnit;
     Printf("Slowest unit: %zd s:\n", TimeOfLongestUnitInSeconds);
@@ -459,13 +523,6 @@ bool Fuzzer::RunOne(const uint8_t *Data, size_t Size) {
   return Res;
 }
 
-void Fuzzer::RunOneAndUpdateCorpus(const uint8_t *Data, size_t Size) {
-  if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
-    return;
-  if (RunOne(Data, Size))
-    ReportNewCoverage({Data, Data + Size});
-}
-
 size_t Fuzzer::GetCurrentUnitInFuzzingThead(const uint8_t **Data) const {
   assert(InFuzzingThread());
   *Data = CurrentUnitData;
@@ -474,32 +531,26 @@ size_t Fuzzer::GetCurrentUnitInFuzzingThead(const uint8_t **Data) const {
 
 void Fuzzer::ExecuteCallback(const uint8_t *Data, size_t Size) {
   assert(InFuzzingThread());
-  LazyAllocateCurrentUnitData();
-  UnitStartTime = system_clock::now();
   // We copy the contents of Unit into a separate heap buffer
   // so that we reliably find buffer overflows in it.
-  std::unique_ptr<uint8_t[]> DataCopy(new uint8_t[Size]);
-  memcpy(DataCopy.get(), Data, Size);
+  uint8_t *DataCopy = new uint8_t[Size];
+  memcpy(DataCopy, Data, Size);
   if (CurrentUnitData && CurrentUnitData != Data)
     memcpy(CurrentUnitData, Data, Size);
-  AssignTaintLabels(DataCopy.get(), Size);
   CurrentUnitSize = Size;
-  AllocTracer.Start();
-  int Res = CB(DataCopy.get(), Size);
+  AllocTracer.Start(Options.TraceMalloc);
+  UnitStartTime = system_clock::now();
+  ResetCounters();  // Reset coverage right before the callback.
+  TPC.ResetMaps();
+  RunningCB = true;
+  int Res = CB(DataCopy, Size);
+  RunningCB = false;
+  UnitStopTime = system_clock::now();
   (void)Res;
+  assert(Res == 0);
   HasMoreMallocsThanFrees = AllocTracer.Stop();
   CurrentUnitSize = 0;
-  assert(Res == 0);
-}
-
-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;
+  delete[] DataCopy;
 }
 
 void Fuzzer::WriteToOutputCorpus(const Unit &U) {
@@ -526,16 +577,6 @@ void Fuzzer::WriteUnitToFileWithPrefix(const Unit &U, const char *Prefix) {
     Printf("Base64: %s\n", Base64(U).c_str());
 }
 
-void Fuzzer::SaveCorpus() {
-  if (Options.OutputCorpus.empty())
-    return;
-  for (const auto &U : Corpus)
-    WriteToFile(U, DirPlusFile(Options.OutputCorpus, Hash(U)));
-  if (Options.Verbosity)
-    Printf("Written corpus of %zd files to %s\n", Corpus.size(),
-           Options.OutputCorpus.c_str());
-}
-
 void Fuzzer::PrintStatusForNewUnit(const Unit &U) {
   if (!Options.PrintNEW)
     return;
@@ -547,14 +588,13 @@ void Fuzzer::PrintStatusForNewUnit(const Unit &U) {
   }
 }
 
-void Fuzzer::ReportNewCoverage(const Unit &U) {
-  Corpus.push_back(U);
-  UpdateCorpusDistribution();
-  UnitHashesAddedToCorpus.insert(Hash(U));
+void Fuzzer::ReportNewCoverage(InputInfo *II, const Unit &U) {
+  II->NumSuccessfullMutations++;
   MD.RecordSuccessfulMutationSequence();
   PrintStatusForNewUnit(U);
   WriteToOutputCorpus(U);
   NumberOfNewUnitsAdded++;
+  TPC.PrintNewPCs();
 }
 
 // Finds minimal number of units in 'Extra' that add coverage to 'Initial'.
@@ -564,26 +604,33 @@ void Fuzzer::ReportNewCoverage(const Unit &U) {
 UnitVector Fuzzer::FindExtraUnits(const UnitVector &Initial,
                                   const UnitVector &Extra) {
   UnitVector Res = Extra;
+  UnitVector Tmp;
   size_t OldSize = Res.size();
   for (int Iter = 0; Iter < 10; Iter++) {
     ShuffleCorpus(&Res);
+    TPC.ResetMaps();
+    Corpus.ResetFeatureSet();
     ResetCoverage();
 
-    for (auto &U : Initial)
+    for (auto &U : Initial) {
+      TPC.ResetMaps();
       RunOne(U);
+    }
 
-    Corpus.clear();
-    for (auto &U : Res)
+    Tmp.clear();
+    for (auto &U : Res) {
+      TPC.ResetMaps();
       if (RunOne(U))
-        Corpus.push_back(U);
+        Tmp.push_back(U);
+    }
 
     char Stat[7] = "MIN   ";
     Stat[3] = '0' + Iter;
-    PrintStats(Stat);
+    PrintStats(Stat, "\n", Tmp.size());
 
-    size_t NewSize = Corpus.size();
+    size_t NewSize = Tmp.size();
     assert(NewSize <= OldSize);
-    Res.swap(Corpus);
+    Res.swap(Tmp);
 
     if (NewSize + 5 >= OldSize)
       break;
@@ -597,13 +644,15 @@ void Fuzzer::Merge(const std::vector<std::string> &Corpora) {
     Printf("Merge requires two or more corpus dirs\n");
     return;
   }
+  InMergeMode = true;
   std::vector<std::string> ExtraCorpora(Corpora.begin() + 1, Corpora.end());
 
-  assert(Options.MaxLen > 0);
+  assert(MaxInputLen > 0);
   UnitVector Initial, Extra;
-  ReadDirToVectorOfUnits(Corpora[0].c_str(), &Initial, nullptr, Options.MaxLen);
+  ReadDirToVectorOfUnits(Corpora[0].c_str(), &Initial, nullptr, MaxInputLen,
+                         true);
   for (auto &C : ExtraCorpora)
-    ReadDirToVectorOfUnits(C.c_str(), &Extra, nullptr, Options.MaxLen);
+    ReadDirToVectorOfUnits(C.c_str(), &Extra, nullptr, MaxInputLen, true);
 
   if (!Initial.empty()) {
     Printf("=== Minimizing the initial corpus of %zd units\n", Initial.size());
@@ -631,7 +680,7 @@ void Fuzzer::TryDetectingAMemoryLeak(const uint8_t *Data, size_t Size,
   // Run the target once again, but with lsan disabled so that if there is
   // a real leak we do not report it twice.
   EF->__lsan_disable();
-  RunOne(Data, Size);
+  ExecuteCallback(Data, Size);
   EF->__lsan_enable();
   if (!HasMoreMallocsThanFrees) return;  // a leak is unlikely.
   if (NumberOfLeakDetectionAttempts++ > 1000) {
@@ -639,6 +688,8 @@ void Fuzzer::TryDetectingAMemoryLeak(const uint8_t *Data, size_t Size,
     Printf("INFO: libFuzzer disabled leak detection after every mutation.\n"
            "      Most likely the target function accumulates allocated\n"
            "      memory in a global state w/o actually leaking it.\n"
+           "      You may try running this binary with -trace_malloc=[12]"
+           "      to get a trace of mallocs and frees.\n"
            "      If LeakSanitizer is enabled in this process it will still\n"
            "      run on the process shutdown.\n");
     return;
@@ -656,112 +707,82 @@ void Fuzzer::TryDetectingAMemoryLeak(const uint8_t *Data, size_t Size,
   }
 }
 
+static size_t ComputeMutationLen(size_t MaxInputSize, size_t MaxMutationLen,
+                                 Random &Rand) {
+  assert(MaxInputSize <= MaxMutationLen);
+  if (MaxInputSize == MaxMutationLen) return MaxMutationLen;
+  size_t Result = MaxInputSize;
+  size_t R = Rand.Rand();
+  if ((R % (1U << 7)) == 0)
+    Result++;
+  if ((R % (1U << 15)) == 0)
+    Result += 10 + Result / 2;
+  return Min(Result, MaxMutationLen);
+}
+
 void Fuzzer::MutateAndTestOne() {
-  LazyAllocateCurrentUnitData();
   MD.StartMutationSequence();
 
-  auto &U = ChooseUnitToMutate();
+  auto &II = Corpus.ChooseUnitToMutate(MD.GetRand());
+  const auto &U = II.U;
+  memcpy(BaseSha1, II.Sha1, sizeof(BaseSha1));
   assert(CurrentUnitData);
   size_t Size = U.size();
-  assert(Size <= Options.MaxLen && "Oversized Unit");
+  assert(Size <= MaxInputLen && "Oversized Unit");
   memcpy(CurrentUnitData, U.data(), Size);
 
+  assert(MaxMutationLen > 0);
+
+  size_t CurrentMaxMutationLen =
+      Options.ExperimentalLenControl
+          ? ComputeMutationLen(Corpus.MaxInputSize(), MaxMutationLen,
+                               MD.GetRand())
+          : MaxMutationLen;
+
   for (int i = 0; i < Options.MutateDepth; i++) {
+    if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
+      break;
     size_t NewSize = 0;
-    NewSize = MD.Mutate(CurrentUnitData, Size, Options.MaxLen);
+    NewSize = MD.Mutate(CurrentUnitData, Size, CurrentMaxMutationLen);
     assert(NewSize > 0 && "Mutator returned empty unit");
-    assert(NewSize <= Options.MaxLen &&
-           "Mutator return overisized unit");
+    assert(NewSize <= CurrentMaxMutationLen && "Mutator return overisized unit");
     Size = NewSize;
     if (i == 0)
       StartTraceRecording();
-    RunOneAndUpdateCorpus(CurrentUnitData, Size);
+    II.NumExecutedMutations++;
+    if (size_t NumFeatures = RunOne(CurrentUnitData, Size)) {
+      Corpus.AddToCorpus({CurrentUnitData, CurrentUnitData + Size}, NumFeatures,
+                         /*MayDeleteFile=*/true);
+      ReportNewCoverage(&II, {CurrentUnitData, CurrentUnitData + Size});
+      CheckExitOnSrcPosOrItem();
+    }
     StopTraceRecording();
     TryDetectingAMemoryLeak(CurrentUnitData, Size,
                             /*DuringInitialCorpusExecution*/ false);
   }
 }
 
-// Returns an index of random unit from the corpus to mutate.
-// Hypothesis: units added to the corpus last are more likely to be interesting.
-// This function gives more weight to the more recent units.
-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() {
-  CoverageController::Reset();
+  ResetEdgeCoverage();
   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.
-// - Merge the newly created corpus into the original one.
-void Fuzzer::Drill() {
-  // The corpus is already read, shuffled, and minimized.
-  assert(!Corpus.empty());
-  Options.PrintNEW = false; // Don't print NEW status lines when drilling.
-
-  Unit U = ChooseUnitToMutate();
-
-  ResetCoverage();
-
-  std::vector<Unit> SavedCorpus;
-  SavedCorpus.swap(Corpus);
-  Corpus.push_back(U);
-  UpdateCorpusDistribution();
-  assert(Corpus.size() == 1);
-  RunOne(U);
-  PrintStats("DRILL ");
-  std::string SavedOutputCorpusPath; // Don't write new units while drilling.
-  SavedOutputCorpusPath.swap(Options.OutputCorpus);
-  Loop();
-
-  ResetCoverage();
-
-  PrintStats("REINIT");
-  SavedOutputCorpusPath.swap(Options.OutputCorpus);
-  for (auto &U : SavedCorpus)
-    RunOne(U);
-  PrintStats("MERGE ");
-  Options.PrintNEW = true;
-  size_t NumMerged = 0;
-  for (auto &U : Corpus) {
-    if (RunOne(U)) {
-      PrintStatusForNewUnit(U);
-      NumMerged++;
-      WriteToOutputCorpus(U);
-    }
-  }
-  PrintStats("MERGED");
-  if (NumMerged && Options.Verbosity)
-    Printf("Drilling discovered %zd new units\n", NumMerged);
+  PrepareCounters(&MaxCoverage);
 }
 
 void Fuzzer::Loop() {
+  TPC.InitializePrintNewPCs();
   system_clock::time_point LastCorpusReload = system_clock::now();
   if (Options.DoCrossOver)
     MD.SetCorpus(&Corpus);
   while (true) {
     auto Now = system_clock::now();
-    if (duration_cast<seconds>(Now - LastCorpusReload).count()) {
-      RereadOutputCorpus(Options.MaxLen);
-      LastCorpusReload = Now;
+    if (duration_cast<seconds>(Now - LastCorpusReload).count() >=
+        Options.ReloadIntervalSec) {
+      RereadOutputCorpus(MaxInputLen);
+      LastCorpusReload = system_clock::now();
     }
     if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
       break;
-    if (Options.MaxTotalTimeSec > 0 &&
-        secondsSinceProcessStartUp() >
-            static_cast<size_t>(Options.MaxTotalTimeSec))
-      break;
+    if (TimedOut()) break;
     // Perform several mutations and runs.
     MutateAndTestOne();
   }
@@ -770,14 +791,19 @@ void Fuzzer::Loop() {
   MD.PrintRecommendedDictionary();
 }
 
-void Fuzzer::UpdateCorpusDistribution() {
-  size_t N = Corpus.size();
-  std::vector<double> Intervals(N + 1);
-  std::vector<double> Weights(N);
-  std::iota(Intervals.begin(), Intervals.end(), 0);
-  std::iota(Weights.begin(), Weights.end(), 1);
-  CorpusDistribution = std::piecewise_constant_distribution<double>(
-      Intervals.begin(), Intervals.end(), Weights.begin());
+void Fuzzer::MinimizeCrashLoop(const Unit &U) {
+  if (U.size() <= 2) return;
+  while (!TimedOut() && TotalNumberOfRuns < Options.MaxNumberOfRuns) {
+    MD.StartMutationSequence();
+    memcpy(CurrentUnitData, U.data(), U.size());
+    for (int i = 0; i < Options.MutateDepth; i++) {
+      size_t NewSize = MD.Mutate(CurrentUnitData, U.size(), MaxMutationLen);
+      assert(NewSize > 0 && NewSize <= MaxMutationLen);
+      RunOne(CurrentUnitData, NewSize);
+      TryDetectingAMemoryLeak(CurrentUnitData, NewSize,
+                              /*DuringInitialCorpusExecution*/ false);
+    }
+  }
 }
 
 } // namespace fuzzer