Use std::piecewise_constant_distribution instead of ad-hoc binary search.
Summary:
Fix the issue with the most recently discovered unit receiving much less attention.
Note: I had to change the seed for one test to make it pass. Alternatively,
the number of runs could be increased. I believe that the average time of
'foo' discovery is not increased, just seed=1 was particularly convenient
for the previous PRNG scheme used.
Reviewers: aizatsky, kcc
Subscribers: llvm-commits, kcc
Differential Revision: http://reviews.llvm.org/D16419
llvm-svn: 258473
diff --git a/llvm/lib/Fuzzer/FuzzerLoop.cpp b/llvm/lib/Fuzzer/FuzzerLoop.cpp
index 7f3b0f5..a7e743e 100644
--- a/llvm/lib/Fuzzer/FuzzerLoop.cpp
+++ b/llvm/lib/Fuzzer/FuzzerLoop.cpp
@@ -163,6 +163,7 @@
if (UnitHashesAddedToCorpus.insert(Hash(X)).second) {
if (RunOne(X)) {
Corpus.push_back(X);
+ UpdateCorpusDistribution();
PrintStats("RELOAD");
}
}
@@ -200,6 +201,7 @@
}
}
Corpus = NewCorpus;
+ UpdateCorpusDistribution();
for (auto &X : Corpus)
UnitHashesAddedToCorpus.insert(Hash(X));
PrintStats("INITED");
@@ -347,6 +349,7 @@
void Fuzzer::ReportNewCoverage(const Unit &U) {
Corpus.push_back(U);
+ UpdateCorpusDistribution();
UnitHashesAddedToCorpus.insert(Hash(U));
USF.GetMD().RecordSuccessfulMutationSequence();
PrintStatusForNewUnit(U);
@@ -409,22 +412,11 @@
// 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 wieght to the more recent units.
+// This function gives more weight to the more recent units.
size_t Fuzzer::ChooseUnitIdxToMutate() {
- size_t N = Corpus.size();
- size_t Total = (N + 1) * N / 2;
- size_t R = USF.GetRand()(Total);
- size_t IdxBeg = 0, IdxEnd = N;
- // Binary search.
- while (IdxEnd - IdxBeg >= 2) {
- size_t Idx = IdxBeg + (IdxEnd - IdxBeg) / 2;
- if (R > (Idx + 1) * Idx / 2)
- IdxBeg = Idx;
- else
- IdxEnd = Idx;
- }
- assert(IdxBeg < N);
- return IdxBeg;
+ size_t Idx = static_cast<size_t>(CorpusDistribution(USF.GetRand()));
+ assert(Idx < Corpus.size());
+ return Idx;
}
// Experimental search heuristic: drilling.
@@ -447,6 +439,7 @@
std::vector<Unit> SavedCorpus;
SavedCorpus.swap(Corpus);
Corpus.push_back(U);
+ UpdateCorpusDistribution();
assert(Corpus.size() == 1);
RunOne(U);
PrintStats("DRILL ");
@@ -510,4 +503,14 @@
ExecuteCommand(Options.SyncCommand + " " + Options.OutputCorpus);
}
+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());
+}
+
} // namespace fuzzer