Support module-relative values in FuzzerMerge

[aarongreen]

Summary

This change allows FuzzerMerge to process additional "FT_REL" and "COV_REL" markers for module-relative features and coverage. This allows merging even if the module load order may change between runs.

[aarongreen]

Rebase

[morehouse]

Does this patch affect performance noticeably?

compiler-rt/lib/fuzzer/FuzzerFork.cpp

427 ↗

(On Diff #321773)

How confident are we that features won't overflow uint32_t and wraparound?

435 ↗

(On Diff #321773)

Please explain this calculation with a comment.

446 ↗

(On Diff #321773)

I think the bitmask is superfluous, since the cast will drop the top 32 bits anyway

483 ↗

(On Diff #321773)

compiler-rt/lib/fuzzer/FuzzerMerge.cpp

87–89

Please update this comment.

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

681

Bitmask is superfluous.

701

This only compares Len bytes, not Len uint32_ts.

708

The parsing here is confusing/tricky. Please add comments to clarify what's happening.

724

Aren't both of these cases also "too short"?

756–757

How are these "unknown markers"?

766

Please remove.

[aarongreen]

Addressed (most of) morehouse's comments. I still need to measure performance impact.

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

701

Whoops! Thanks, good catch!

724

I think Past Me was looking at it as "the header says it's longer than it is", but that's confusing. I've changed it to "Incomplete DSO section" and "DSO length mismatch" and added tests to the latter for both too many and too few features.

756–757

Distinguished between unexpected and unknown.

[aarongreen]

Regarding performance: I added some microbenchmarks in Merger::Parse and Fuzzer::CrashResistantMergeInternalStep around the parts that use ModuleRelativeValues objects. I then ran 1000 iterations of a test based on the first non-empty merge in compiler-rt/test/fuzzer/merge.test.

Roughly speaking, this change did increase the time spent in those loops by around 2x: from an average of 18.2 microseconds to 37.8 for merging, and from 20.9 to 45.7 microseconds for parsing. This seems intuitively right, as this change is adding a map lookup to each set insertion. Overall, for the whole -merge=1 command I measured a slowdown of approximately 7.3%, although I'm less confident of my methodology there. I ran time on a whole for i in $(seq 1000); do ... done kind of thing, and the standard deviation was higher than I'd like. Based on the microbenchmarks, I would have expected something closer to 3% (based on the 166.7 extra microseconds from 6 merges and two parses performed in the test).

All in all, it's a bit higher than I had hoped. Let me know if you feel this is getting to be too expensive. I think the module-relative values are definitely needed (since multiple remote processes may be started and have their module load order interleaved), but maybe it's worth only using them for remote fuzzers, and keep using the current approach for normal fuzzers. Supporting two different formats has some obvious maintenance drawbacks, but I could understand if it were necessary.

[morehouse]

In D94514#2642909, @aarongreen wrote:

Regarding performance: I added some microbenchmarks in Merger::Parse and Fuzzer::CrashResistantMergeInternalStep around the parts that use ModuleRelativeValues objects. I then ran 1000 iterations of a test based on the first non-empty merge in compiler-rt/test/fuzzer/merge.test.

Roughly speaking, this change did increase the time spent in those loops by around 2x: from an average of 18.2 microseconds to 37.8 for merging, and from 20.9 to 45.7 microseconds for parsing. This seems intuitively right, as this change is adding a map lookup to each set insertion. Overall, for the whole -merge=1 command I measured a slowdown of approximately 7.3%, although I'm less confident of my methodology there. I ran time on a whole for i in $(seq 1000); do ... done kind of thing, and the standard deviation was higher than I'd like. Based on the microbenchmarks, I would have expected something closer to 3% (based on the 166.7 extra microseconds from 6 merges and two parses performed in the test).

All in all, it's a bit higher than I had hoped. Let me know if you feel this is getting to be too expensive. I think the module-relative values are definitely needed (since multiple remote processes may be started and have their module load order interleaved), but maybe it's worth only using them for remote fuzzers, and keep using the current approach for normal fuzzers. Supporting two different formats has some obvious maintenance drawbacks, but I could understand if it were necessary.

The merge overhead isn't great, but might be acceptable since merges are relatively infrequent. Is there measurable overall overhead on fuzzing in -fork mode?

[aarongreen]

I'm playing a bit with a version that introduces new markers: "FT_REL" and "COV_REL". I'll finish that up soon, post it, and collect some more perf numbers.

As for Fork; I'm *really* tempted to simply drop the fork-related changes, and say -fork=1 doesn't work with -remote=1, which would be enforced in D94522. WDYT?

compiler-rt/lib/fuzzer/FuzzerFork.cpp

427 ↗

(On Diff #321773)

This is now handled by D97992.

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

708

I've tried to rewrite these checks using more of C++ style than C. Let me know if it's still confusing.

[morehouse]

In D94514#2657261, @aarongreen wrote:

I'm playing a bit with a version that introduces new markers: "FT_REL" and "COV_REL". I'll finish that up soon, post it, and collect some more perf numbers.

As for Fork; I'm *really* tempted to simply drop the fork-related changes, and say -fork=1 doesn't work with -remote=1, which would be enforced in D94522. WDYT?

Fine with me if it reduces performance issues.

[aarongreen]

Fine with me if it reduces performance issues.

Okay; I've reworked this. It doesn't have any dependency on FuzzerModuleRelative now, and distinguishes between "FT/COV" and "FT_REL/COV_REL". It also doesn't touch FuzzerFork, as discussed.

In terms of performance, the smallest of microbenchmarks are kinda of apples-to-oranges due to various loop refactors, etc. Still most steps are +/- 10 microseconds. All told, it adds up to about 199 microseconds added to the average 27 *milliseconds* spent in CrashResistantMerge over 10k iterations (excluding measurements more than 10x the stdev; the outer loop's syscalls led to some aggressive outliers both before and after the change). This represents a performance increase of about 0.7%. I have a few ideas how to possibly squeeze even more; but I suspect we're in the realm of good enough.

[morehouse]

In D94514#2660252, @aarongreen wrote:

Fine with me if it reduces performance issues.

Okay; I've reworked this. It doesn't have any dependency on FuzzerModuleRelative now, and distinguishes between "FT/COV" and "FT_REL/COV_REL". It also doesn't touch FuzzerFork, as discussed.

In terms of performance, the smallest of microbenchmarks are kinda of apples-to-oranges due to various loop refactors, etc. Still most steps are +/- 10 microseconds. All told, it adds up to about 199 microseconds added to the average 27 *milliseconds* spent in CrashResistantMerge over 10k iterations (excluding measurements more than 10x the stdev; the outer loop's syscalls led to some aggressive outliers both before and after the change). This represents a performance increase of about 0.7%. I have a few ideas how to possibly squeeze even more; but I suspect we're in the realm of good enough.

Great, thanks for doing this!

compiler-rt/lib/fuzzer/FuzzerMerge.cpp

151

I think we can remove the ParseRelative stuff.

277

The if-else block is confusing to me. Could you add some comments clarifying what's going on?

377

Shouldn't UniqFeatures already be sorted?

[aarongreen]

compiler-rt/lib/fuzzer/FuzzerMerge.cpp

151

Whoops!

277

Actually, this is wrong: I can't look up a module by a relative feature! I'll upload a new diff to D94512 that includes a ModuleInfoByHash and use that here. I'll also add a comment, and more importantly, add the tests that would have caught this.

377

Yes, and I'm already guaranteeing that in the unit tests. Thanks. +1

[morehouse]

Please remove fuzzer-test and libFuzzer.a from the diff.

[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/FuzzerInternal.h

public:
   void ExecuteCallback(const uint8_t *Data, size_t Size);
   bool RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile = false,
               InputInfo *II = nullptr, bool ForceAddToCorpus = false,
               bool *FoundUniqFeatures = nullptr);
   void TPCUpdateObservedPCs();
 
   // Merge Corpora[1:] into Corpora[0].
   void Merge(const Vector<std::string> &Corpora);
-  void CrashResistantMergeInternalStep(const std::string &ControlFilePath);
+  void CrashResistantMergeInternalStep(const std::string &ControlFilePath,
+                                       bool UseRelative = false);
   MutationDispatcher &GetMD() { return MD; }
   void PrintFinalStats();
   void SetMaxInputLen(size_t MaxInputLen);
   void SetMaxMutationLen(size_t MaxMutationLen);
   void RssLimitCallback();
 
   bool InFuzzingThread() const { return IsMyThread; }
   size_t GetCurrentUnitInFuzzingThead(const uint8_t **Data) const;

compiler-rt/lib/fuzzer/FuzzerMerge.h

 #ifndef LLVM_FUZZER_MERGE_H
 #define LLVM_FUZZER_MERGE_H
 
 #include "FuzzerDefs.h"
 
 #include <istream>
 #include <ostream>
 #include <set>
+#include <unordered_map>
 #include <vector>
 
 namespace fuzzer {
 
 struct MergeFileInfo {
   std::string Name;
   size_t Size = 0;
   Vector<uint32_t> Features, Cov;
+  std::unordered_map<uint64_t, Vector<uint32_t>> FeaturesByHash, CovByHash;
 };
 
 struct Merger {
   Vector<MergeFileInfo> Files;
   size_t NumFilesInFirstCorpus = 0;
   size_t FirstNotProcessedFile = 0;
   std::string LastFailure;
 
   bool Parse(std::istream &IS, bool ParseCoverage);
   bool Parse(const std::string &Str, bool ParseCoverage);
   void ParseOrExit(std::istream &IS, bool ParseCoverage);
+
+  void MergeValuesInto(const Vector<uint32_t> &Values,
+                       Vector<uint32_t> &AllValues);
+  void DedupValuesFrom(Vector<uint32_t> &Values,
+                       const Vector<uint32_t> &AllValues);
+  bool AddNewValues(const Vector<uint32_t> &Values, Vector<uint32_t> &AllValues,
+                    Vector<uint32_t> &NewValues);
+
   size_t Merge(const Set<uint32_t> &InitialFeatures, Set<uint32_t> *NewFeatures,
                const Set<uint32_t> &InitialCov, Set<uint32_t> *NewCov,
                Vector<std::string> *NewFiles);
   size_t ApproximateMemoryConsumption() const;
-  Set<uint32_t> AllFeatures() const;
 };
 
 void CrashResistantMerge(const Vector<std::string> &Args,
                          const Vector<SizedFile> &OldCorpus,
                          const Vector<SizedFile> &NewCorpus,
                          Vector<std::string> *NewFiles,
                          const Set<uint32_t> &InitialFeatures,
                          Set<uint32_t> *NewFeatures,
                          const Set<uint32_t> &InitialCov,
                          Set<uint32_t> *NewCov,
                          const std::string &CFPath,
                          bool Verbose);
 
 }  // namespace fuzzer
 
 #endif  // LLVM_FUZZER_MERGE_H

compiler-rt/lib/fuzzer/FuzzerMerge.cpp

 //===- FuzzerMerge.cpp - merging corpora ----------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 // Merging corpora.
 //===----------------------------------------------------------------------===//
 
 #include "FuzzerCommand.h"
 #include "FuzzerMerge.h"
 #include "FuzzerIO.h"
 #include "FuzzerInternal.h"
 #include "FuzzerTracePC.h"
 #include "FuzzerUtil.h"
-
 #include <fstream>
 #include <iterator>
 #include <set>
 #include <sstream>
 #include <unordered_set>
 
 namespace fuzzer {
 
 bool Merger::Parse(const std::string &Str, bool ParseCoverage) {
   std::istringstream SS(Str);
   return Parse(SS, ParseCoverage);
 }
 
 void Merger::ParseOrExit(std::istream &IS, bool ParseCoverage) {
   if (!Parse(IS, ParseCoverage)) {
     Printf("MERGE: failed to parse the control file (unexpected error)\n");
     exit(1);
   }
 }
 
+void Merger::MergeValuesInto(const Vector<uint32_t> &Values,
+                             Vector<uint32_t> &Into) {
+  Vector<uint32_t> Out;
+  Out.reserve(Values.size() + Into.size());
+  std::set_union(Values.begin(), Values.end(), Into.begin(), Into.end(),
+                 std::back_inserter(Out));
+  if (Into.size() == Out.size())
+    return;
+  Out.shrink_to_fit();
+  Into.swap(Out);
+}
+
+void Merger::DedupValuesFrom(Vector<uint32_t> &Values,
+                             const Vector<uint32_t> &From) {
+  Vector<uint32_t> Out;
+  Out.reserve(Values.size());
+  std::set_difference(Values.begin(), Values.end(), From.begin(), From.end(),
+                      std::back_inserter(Out));
+  if (Out.size() == Values.size())
+    return;
+  Out.shrink_to_fit();
+  Values.swap(Out);
+}
+
+bool Merger::AddNewValues(const Vector<uint32_t> &Values, Vector<uint32_t> &All,
+                          Vector<uint32_t> &New) {
+  Vector<uint32_t> Diff;
+  Diff.reserve(Values.size());
+  std::set_difference(Values.begin(), Values.end(), All.begin(), All.end(),
+                      std::back_inserter(Diff));
+  if (Diff.empty())
+    return false;
+  MergeValuesInto(Diff, All);
+  MergeValuesInto(Diff, New);
+  return true;
+}
+
 // The control file example:
 //
 // 3 # The number of inputs
 // 1 # The number of inputs in the first corpus, <= the previous number
 // file0
 // file1
 // file2  # One file name per line.
 // STARTED 0 123  # FileID, file size
 // FT 0 1 4 6 8  # FileID COV1 COV2 ...
 // COV 0 7 8 9 # FileID COV1 COV1
 // STARTED 1 456  # If FT is missing, the input crashed while processing.
 // STARTED 2 567
 // FT 2 8 9
 // COV 2 11 12
+// FT_REL 0xdead 3 5 8 # *_REL indicates module-relative values.
+// COV_REL 0xbeef 13 21 34
 bool Merger::Parse(std::istream &IS, bool ParseCoverage) {
+  Files.clear();
   LastFailure.clear();
   std::string Line;
 
   // Parse NumFiles.
   if (!std::getline(IS, Line, '\n')) return false;
   std::istringstream L1(Line);
   size_t NumFiles = 0;
   L1 >> NumFiles;
   if (NumFiles == 0 || NumFiles > 10000000) return false;
 
   // Parse NumFilesInFirstCorpus.
   if (!std::getline(IS, Line, '\n')) return false;
   std::istringstream L2(Line);
   NumFilesInFirstCorpus = NumFiles + 1;
   L2 >> NumFilesInFirstCorpus;
   if (NumFilesInFirstCorpus > NumFiles) return false;
 
   // Parse file names.
   Files.resize(NumFiles);
-  for (size_t i = 0; i < NumFiles; i++)
-    if (!std::getline(IS, Files[i].Name, '\n'))
+  for (auto &File : Files) {
+    if (!std::getline(IS, File.Name, '\n'))
       return false;
+    File.Features.clear();
+    File.Cov.clear();
+  }
 
   // Parse STARTED, FT, and COV lines.
   size_t ExpectedStartMarker = 0;
   const size_t kInvalidStartMarker = -1;
   size_t LastSeenStartMarker = kInvalidStartMarker;
-  Vector<uint32_t> TmpFeatures;
+
+  bool Succeeded = true;
+  uint64_t Hash = 0;
+  Vector<uint32_t> Tmp;
   Set<uint32_t> PCs;
+
+  Vector<uint32_t> AllFeatures, AllPCs;
+  std::unordered_map<uint64_t, Vector<uint32_t>> AllFeaturesByHash,
+      AllPCsByHash;
   while (std::getline(IS, Line, '\n')) {
     std::istringstream ISS1(Line);
     std::string Marker;
     uint32_t N;
     if (!(ISS1 >> Marker) || !(ISS1 >> N))
       return false;
     if (Marker == "STARTED") {
       // STARTED FILE_ID FILE_SIZE
       if (ExpectedStartMarker != N)
         return false;
       ISS1 >> Files[ExpectedStartMarker].Size;
       LastSeenStartMarker = ExpectedStartMarker;
       assert(ExpectedStartMarker < Files.size());
       ExpectedStartMarker++;
-    } else if (Marker == "FT") {
-      // FT FILE_ID COV1 COV2 COV3 ...
-      size_t CurrentFileIdx = N;
-      if (CurrentFileIdx != LastSeenStartMarker)
-        return false;
-      LastSeenStartMarker = kInvalidStartMarker;
-      if (ParseCoverage) {
-        TmpFeatures.clear();  // use a vector from outer scope to avoid resizes.
-        while (ISS1 >> N)
-          TmpFeatures.push_back(N);
-        std::sort(TmpFeatures.begin(), TmpFeatures.end());
-        Files[CurrentFileIdx].Features = TmpFeatures;
-      }
-    } else if (Marker == "COV") {
-      size_t CurrentFileIdx = N;
-      if (ParseCoverage)
-        while (ISS1 >> N)
-          if (PCs.insert(N).second)
-            Files[CurrentFileIdx].Cov.push_back(N);
-    } else {
+      Succeeded = false;
+      continue;
+    }
+
+    // MARKER FILE_ID [HASH] VAL1 VAL2 VAL3
+    Succeeded = true;
+    if (!ParseCoverage)
+      continue;
+    if (Marker == "FT_REL" || Marker == "COV_REL")
+      if (!(ISS1 >> std::hex >> Hash >> std::dec))
+        return false;
+
+    // Use a vector from the outer scope to reduce resizes.
+    Tmp.clear();
+      Tmp.push_back(N);
+    std::sort(Tmp.begin(), Tmp.end());
+    auto &File = Files[CurrentFileIdx];
+
+    if (Marker == "FT")
+      MergeValuesInto(Tmp, File.Features);
+    else if (Marker == "COV")
+      AddNewValues(Tmp, AllPCs, File.Cov);
+    else if (Marker == "FT_REL")
+      MergeValuesInto(Tmp, File.FeaturesByHash[Hash]);
+    else if (Marker == "COV_REL")
+      AddNewValues(Tmp, AllPCsByHash[Hash], File.CovByHash[Hash]);
+    else
       return false;
-    }
-  }
-  if (LastSeenStartMarker != kInvalidStartMarker)
+  if (!Succeeded)
     LastFailure = Files[LastSeenStartMarker].Name;
 
   FirstNotProcessedFile = ExpectedStartMarker;
   return true;
 }
 
+static size_t GetNumFeatures(const MergeFileInfo &File) {
+  auto N = File.Features.size();
+  for (auto F : File.FeaturesByHash)
+    N += F.second.size();
+  return N;
+};
+
+static size_t GetNumPCs(const MergeFileInfo &File) {
+  auto N = File.Cov.size();
+  for (auto C : File.CovByHash)
+    N += C.second.size();
+  return N;
+};
+
 size_t Merger::ApproximateMemoryConsumption() const  {
-  size_t Res = 0;
-  for (const auto &F: Files)
-    Res += sizeof(F) + F.Features.size() * sizeof(F.Features[0]);
-  return Res;
+  size_t NumFeatures = 0;
+  size_t NumPCs = 0;
+  size_t NumHashes = 0;
+  for (const auto &File : Files) {
+    NumFeatures += GetNumFeatures(File);
+    NumPCs += GetNumPCs(File);
+    NumHashes += File.FeaturesByHash.size() + File.CovByHash.size();
+  }
+  return (Files.size() * sizeof(Files[0])) + (NumFeatures * sizeof(uint32_t)) +
+         (NumPCs * sizeof(uint32_t)) + (NumHashes * sizeof(uint64_t));
 }
 
-// Decides which files need to be merged (add those to NewFiles).
-// Returns the number of new features added.
 size_t Merger::Merge(const Set<uint32_t> &InitialFeatures,
                      Set<uint32_t> *NewFeatures,
                      const Set<uint32_t> &InitialCov, Set<uint32_t> *NewCov,
                      Vector<std::string> *NewFiles) {
-  NewFiles->clear();
-  NewFeatures->clear();
-  NewCov->clear();
   assert(NumFilesInFirstCorpus <= Files.size());
-  Set<uint32_t> AllFeatures = InitialFeatures;
 
-  // What features are in the initial corpus?
+  Vector<uint32_t> AllFeatures, AddedFeatures, TmpFeatures;
+  std::unordered_map<uint64_t, Vector<uint32_t>> AllFeaturesByHash;
+  std::copy(InitialFeatures.begin(), InitialFeatures.end(),
+            std::back_inserter(AllFeatures));
+
+  Vector<uint32_t> AllCov, AddedCov;
+  std::copy(InitialCov.begin(), InitialCov.end(), std::back_inserter(AllCov));
+
+  Vector<std::string> AddedFiles;
+
+  // What features and coverage are in the initial corpus?
   for (size_t i = 0; i < NumFilesInFirstCorpus; i++) {
-    auto &Cur = Files[i].Features;
-    AllFeatures.insert(Cur.begin(), Cur.end());
+    auto &File = Files[i];
+    MergeValuesInto(File.Features, AllFeatures);
+    for (auto F : File.FeaturesByHash)
+      MergeValuesInto(F.second, AllFeaturesByHash[F.first]);
+    MergeValuesInto(File.Cov, AllCov);
   }
+
   // Remove all features that we already know from all other inputs.
   for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++) {
-    auto &Cur = Files[i].Features;
-    Vector<uint32_t> Tmp;
-    std::set_difference(Cur.begin(), Cur.end(), AllFeatures.begin(),
-                        AllFeatures.end(), std::inserter(Tmp, Tmp.begin()));
-    Cur.swap(Tmp);
+    auto &File = Files[i];
+    DedupValuesFrom(File.Features, AllFeatures);
+    for (auto F : File.FeaturesByHash)
+      DedupValuesFrom(F.second, AllFeaturesByHash[F.first]);
   }
 
   // Sort. Give preference to
   //   * smaller files
   //   * files with more features.
   std::sort(Files.begin() + NumFilesInFirstCorpus, Files.end(),
-            [&](const MergeFileInfo &a, const MergeFileInfo &b) -> bool {
-              if (a.Size != b.Size)
-                return a.Size < b.Size;
-              return a.Features.size() > b.Features.size();
+            [&](const MergeFileInfo &A, const MergeFileInfo &B) -> bool {
+              if (A.Size != B.Size)
+                return A.Size < B.Size;
+              return GetNumFeatures(A) > GetNumFeatures(B);
             });
 
   // One greedy pass: add the file's features to AllFeatures.
   // If new features were added, add this file to NewFiles.
+  ModuleInfo Info;
+  size_t NumNewFeaturesByHash = 0;
   for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++) {
-    auto &Cur = Files[i].Features;
-    // Printf("%s -> sz %zd ft %zd\n", Files[i].Name.c_str(),
-    //       Files[i].Size, Cur.size());
-    bool FoundNewFeatures = false;
-    for (auto Fe: Cur) {
-      if (AllFeatures.insert(Fe).second) {
-        FoundNewFeatures = true;
-        NewFeatures->insert(Fe);
+    auto &File = Files[i];
+
+    bool FoundNewFeatures =
+        AddNewValues(File.Features, AllFeatures, AddedFeatures);
+    for (auto F : File.FeaturesByHash) {
+      auto Hash = F.first;
+      auto &Features = F.second;
+      // Look up the corresponding module by hash. The module may or may not be
+      // present; e.g. it may only be loaded as a result of executing a specifc
+      // input. If it is present, convert any new relative features to absolute.
+      // Otherwise, simply record the number of new features.
+      if (TPC.ModuleInfoByHash(Hash, &Info)) {
+        std::transform(Features.begin(), Features.end(), Features.begin(),
+                       [&Info](uint32_t Feature) -> uint32_t {
+                         return static_cast<uint32_t>(Info.FirstFeature +
+                                                      Feature);
+                       });
+        FoundNewFeatures |= AddNewValues(Features, AllFeatures, AddedFeatures);
+      } else {
+        FoundNewFeatures |=
+            AddNewValues(Features, AllFeaturesByHash[Hash], TmpFeatures);
+        NumNewFeaturesByHash += TmpFeatures.size();
+        TmpFeatures.clear();
       }
     }
+
+    AddNewValues(File.Cov, AllCov, AddedCov);
+    for (auto C : File.CovByHash) {
+      auto Hash = C.first;
+      auto &Cov = C.second;
+
+      if (TPC.ModuleInfoByHash(Hash, &Info)) {
+        std::transform(Cov.begin(), Cov.end(), Cov.begin(),
+                       [&Info](uint32_t Idx) -> uint32_t {
+                         return static_cast<uint32_t>(Info.FirstIdx + Idx);
+                       });
+        AddNewValues(Cov, AllCov, AddedCov);
+      }
+    }
+
     if (FoundNewFeatures)
-      NewFiles->push_back(Files[i].Name);
-    for (auto Cov : Files[i].Cov)
-      if (InitialCov.find(Cov) == InitialCov.end())
-        NewCov->insert(Cov);
-  }
-  return NewFeatures->size();
+      AddedFiles.push_back(File.Name);
   }
 
-Set<uint32_t> Merger::AllFeatures() const {
-  Set<uint32_t> S;
-  for (auto &File : Files)
-    S.insert(File.Features.begin(), File.Features.end());
-  return S;
+  if (NewFeatures) {
+    NewFeatures->clear();
+    NewFeatures->insert(AddedFeatures.begin(), AddedFeatures.end());
+  }
+  if (NewCov) {
+    NewCov->clear();
+    NewCov->insert(AddedCov.begin(), AddedCov.end());
+  }
+  if (NewFiles)
+    NewFiles->swap(AddedFiles);
+
+  return AddedFeatures.size() + NumNewFeaturesByHash;
 }
 
 // Inner process. May crash if the target crashes.
-void Fuzzer::CrashResistantMergeInternalStep(const std::string &CFPath) {
+void Fuzzer::CrashResistantMergeInternalStep(const std::string &CFPath,
+                                             bool UseRelative) {
   Printf("MERGE-INNER: using the control file '%s'\n", CFPath.c_str());
   Merger M;
   std::ifstream IF(CFPath);
   M.ParseOrExit(IF, false);
   IF.close();
   if (!M.LastFailure.empty())
     Printf("MERGE-INNER: '%s' caused a failure at the previous merge step\n",
            M.LastFailure.c_str());
 
   Printf("MERGE-INNER: %zd total files;"
          " %zd processed earlier; will process %zd files now\n",
          M.Files.size(), M.FirstNotProcessedFile,
          M.Files.size() - M.FirstNotProcessedFile);
 
-  std::ofstream OF(CFPath, std::ofstream::out | std::ofstream::app);
-  Set<size_t> AllFeatures;
-  auto PrintStatsWrapper = [this, &AllFeatures](const char* Where) {
-    this->PrintStats(Where, "\n", 0, AllFeatures.size());
-  };
+  // Use vectors in the outer scope to reduce reallocations.
+  Vector<uint32_t> Features, AllFeatures, UniqFeatures;
   Set<const TracePC::PCTableEntry *> AllPCs;
+  Vector<uint32_t> UniqCov;
+
+  auto PrintStatsWrapper = [&](const char *Where) {
+    PrintStats(Where, "\n", 0, AllFeatures.size());
+  };
+
+  std::ofstream OF(CFPath, std::ofstream::out | std::ofstream::app);
+  ModuleInfo Info;
+  bool First;
+
+  // |Merge| guarantees that this will iterate over files in this order:
+  // * First, files in the initial corpus ordered by size, smallest first.
+  // * Then, all other files, smallest first.
   for (size_t i = M.FirstNotProcessedFile; i < M.Files.size(); i++) {
     Fuzzer::MaybeExitGracefully();
     auto U = FileToVector(M.Files[i].Name);
     if (U.size() > MaxInputLen) {
       U.resize(MaxInputLen);
       U.shrink_to_fit();
     }
 
     // Write the pre-run marker.
     OF << "STARTED " << i << " " << U.size() << "\n";
     OF.flush();  // Flush is important since Command::Execute may crash.
+
     // Run.
     TPC.ResetMaps();
     ExecuteCallback(U.data(), U.size());
-    // Collect coverage. We are iterating over the files in this order:
-    // * First, files in the initial corpus ordered by size, smallest first.
-    // * Then, all other files, smallest first.
-    // So it makes no sense to record all features for all files, instead we
-    // only record features that were not seen before.
-    Set<size_t> UniqFeatures;
+
+    // Only record features that were not seen before.
+    Features.clear();
     TPC.CollectFeatures([&](size_t Feature) {
-      if (AllFeatures.insert(Feature).second)
-        UniqFeatures.insert(Feature);
+      Features.push_back(static_cast<uint32_t>(Feature));
     });
+    UniqFeatures.clear();
+    M.AddNewValues(Features, AllFeatures, UniqFeatures);
+
     TPC.UpdateObservedPCs();
+    TPC.ForEachObservedPC([&](const TracePC::PCTableEntry *TE) {
+      if (AllPCs.insert(TE).second)
+        UniqCov.push_back(static_cast<uint32_t>(TPC.PCTableEntryIdx(TE)));
+    });
+    std::sort(UniqCov.begin(), UniqCov.end());
+
     // Show stats.
     if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)))
       PrintStatsWrapper("pulse ");
     if (TotalNumberOfRuns == M.NumFilesInFirstCorpus)
       PrintStatsWrapper("LOADED");
-    // Write the post-run marker and the coverage.
+
+    // Write the post-run markers and the coverage.
+    if (UseRelative) {
+      First = true;
+      for (auto Feature : UniqFeatures) {
+        if (Feature < Info.FirstFeature || Info.LastFeature <= Feature) {
+          if (First)
+            First = false;
+          else
+            OF << "\n";
+          TPC.ModuleInfoByFeature(Feature, &Info);
+          OF << "FT_REL " << i << " " << std::hex << Info.Hash << std::dec;
+        }
+        OF << " " << (Feature - Info.FirstFeature);
+      }
+      OF << "\n";
+
+      First = true;
+      for (auto Idx : UniqFeatures) {
+        if (Idx < Info.FirstIdx || Info.LastIdx <= Idx) {
+          if (First)
+            First = false;
+          else
+            OF << "\n";
+          TPC.ModuleInfoByIdx(Idx, &Info);
+          OF << "COV_REL " << i << " " << std::hex << Info.Hash << std::dec;
+        }
+        OF << " " << (Idx - Info.FirstIdx);
+      }
+      OF << "\n";
+
+    } else {
       OF << "FT " << i;
-    for (size_t F : UniqFeatures)
-      OF << " " << F;
+      for (auto Feature : UniqFeatures)
+        OF << " " << Feature;
       OF << "\n";
       OF << "COV " << i;
-    TPC.ForEachObservedPC([&](const TracePC::PCTableEntry *TE) {
-      if (AllPCs.insert(TE).second)
-        OF << " " << TPC.PCTableEntryIdx(TE);
-    });
+      for (auto Idx : UniqCov)
+        OF << " " << Idx;
       OF << "\n";
+    }
     OF.flush();
   }
   PrintStatsWrapper("DONE  ");
 }
 
 static size_t WriteNewControlFile(const std::string &CFPath,
                                   const Vector<SizedFile> &OldCorpus,
                                   const Vector<SizedFile> &NewCorpus,

compiler-rt/lib/fuzzer/FuzzerTracePC.cpp

 
 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);
+  auto 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

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

#define TRACED_EQ(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...
+  // Features must always be returned sorted.
   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;
   });
template <size_t N> void VerifyFeatures(FakeModule<N> &M, bool UseCounters) {
   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",
+      "BAD",
       "0\n0",
-      "3\nx",
+      "3\nBAD",
       "2\n3",
       "2\n2",
       // Bad file names
       "2\n2\nA\n",
       "2\n2\nA\nB\nC\n",
+      // Unexpected markers
+      "1\n1\nA\nFT 0",
+      "1\n1\nA\nCOV 0",
       // Unknown markers
-      "2\n1\nA\nSTARTED 0\nBAD 0 0x0",
+      "1\n1\nA\nBAD 0",
+      "2\n1\nA\nB\nSTARTED 0\nBAD 0",
       // Bad file IDs
       "1\n1\nA\nSTARTED 1",
       "2\n1\nA\nSTARTED 0\nFT 1 0x0",
+      // Missing Hash
+      "2\n1\nA\nB\nSTARTED 0\nFT_REL 0\n",
+      "2\n1\nA\nB\nSTARTED 0\nCOV_REL 0\n",
   };
   for (auto S : kInvalidInputs) {
     SCOPED_TRACE(S);
-    EXPECT_FALSE(M.Parse(S, false));
+    EXPECT_FALSE(M.Parse(S, true));
   }
 
   // Parse initial control file
   EXPECT_TRUE(M.Parse("1\n0\nAA\n", false));
   ASSERT_EQ(M.Files.size(), 1U);
   EXPECT_EQ(M.NumFilesInFirstCorpus, 0U);
   EXPECT_EQ(M.Files[0].Name, "AA");
   EXPECT_TRUE(M.LastFailure.empty());
   EXPECT_EQ(M.FirstNotProcessedFile, 0U);
 
   // Parse control file that failed on first attempt
   EXPECT_TRUE(M.Parse("2\n1\nAA\nBB\nSTARTED 0 42\n", false));
   ASSERT_EQ(M.Files.size(), 2U);
   EXPECT_EQ(M.NumFilesInFirstCorpus, 1U);
   EXPECT_EQ(M.Files[0].Name, "AA");
   EXPECT_EQ(M.Files[1].Name, "BB");
   EXPECT_EQ(M.LastFailure, "AA");
   EXPECT_EQ(M.FirstNotProcessedFile, 1U);
 
   // Parse control file that failed on later attempt
   EXPECT_TRUE(M.Parse("3\n1\nAA\nBB\nC\n"
                       "STARTED 0 1000\n"
                       "FT 0 1 2 3\n"
                       "STARTED 1 1001\n"
-                      "FT 1 4 5 6 \n"
+                      "FT_REL 1 0xbeef 4 5 6 \n"
                       "STARTED 2 1002\n"
                       "",
                       true));
   ASSERT_EQ(M.Files.size(), 3U);
   EXPECT_EQ(M.NumFilesInFirstCorpus, 1U);
   EXPECT_EQ(M.Files[0].Name, "AA");
   EXPECT_EQ(M.Files[0].Size, 1000U);
   EXPECT_EQ(M.Files[1].Name, "BB");
   EXPECT_EQ(M.Files[1].Size, 1001U);
   EXPECT_EQ(M.Files[2].Name, "C");
   EXPECT_EQ(M.Files[2].Size, 1002U);
   EXPECT_EQ(M.LastFailure, "C");
   EXPECT_EQ(M.FirstNotProcessedFile, 3U);
   TRACED_EQ(M.Files[0].Features, {1, 2, 3});
-  TRACED_EQ(M.Files[1].Features, {4, 5, 6});
+  TRACED_EQ(M.Files[0].FeaturesByHash[0xbeef], {});
+  TRACED_EQ(M.Files[1].Features, {});
+  TRACED_EQ(M.Files[1].FeaturesByHash[0xbeef], {4, 5, 6});
 
   // Parse control file without features or PCs
   EXPECT_TRUE(M.Parse("2\n0\nAA\nBB\n"
                       "STARTED 0 1000\n"
                       "FT 0\n"
                       "COV 0\n"
                       "STARTED 1 1001\n"
-                      "FT 1\n"
-                      "COV 1\n"
+                      "FT_REL 1 0xcafe\n"
+                      "COV_REL 1 0xcafe\n"
                       "",
                       true));
   ASSERT_EQ(M.Files.size(), 2U);
   EXPECT_EQ(M.NumFilesInFirstCorpus, 0U);
   EXPECT_TRUE(M.LastFailure.empty());
   EXPECT_EQ(M.FirstNotProcessedFile, 2U);
   EXPECT_TRUE(M.Files[0].Features.empty());
   EXPECT_TRUE(M.Files[0].Cov.empty());
   EXPECT_TRUE(M.Files[1].Features.empty());
   EXPECT_TRUE(M.Files[1].Cov.empty());
 
   // Parse features and PCs
   EXPECT_TRUE(M.Parse("3\n2\nAA\nBB\nC\n"
                       "STARTED 0 1000\n"
                       "FT 0 1 2 3\n"
                       "COV 0 11 12 13\n"
                       "STARTED 1 1001\n"
                       "FT 1 4 5 6\n"
                       "COV 1 7 8 9\n"
+                      "FT_REL 1 0xcafe 14 15 16\n"
+                      "COV_REL 1 0xcafe 17 18 19\n"
                       "STARTED 2 1002\n"
-                      "FT 2 6 1 3\n"
-                      "COV 2 16 11 13\n"
+                      "FT_REL 2 0xcafe 6 1 3\n"
+                      "COV_REL 2 0xcafe 16 11 13\n"
                       "",
                       true));
   ASSERT_EQ(M.Files.size(), 3U);
   EXPECT_EQ(M.NumFilesInFirstCorpus, 2U);
   EXPECT_TRUE(M.LastFailure.empty());
   EXPECT_EQ(M.FirstNotProcessedFile, 3U);
   TRACED_EQ(M.Files[0].Features, {1, 2, 3});
   TRACED_EQ(M.Files[0].Cov, {11, 12, 13});
   TRACED_EQ(M.Files[1].Features, {4, 5, 6});
+  TRACED_EQ(M.Files[1].FeaturesByHash[0xcafe], {14, 15, 16});
   TRACED_EQ(M.Files[1].Cov, {7, 8, 9});
-  TRACED_EQ(M.Files[2].Features, {1, 3, 6});
-  TRACED_EQ(M.Files[2].Cov, {16});
+  TRACED_EQ(M.Files[1].CovByHash[0xcafe], {17, 18, 19});
+  TRACED_EQ(M.Files[2].FeaturesByHash[0xcafe], {1, 3, 6});
+  TRACED_EQ(M.Files[2].CovByHash[0xcafe], {11, 13, 16});
 }
 
 TEST(Merger, Merge) {
   Merger M;
   Set<uint32_t> Features, NewFeatures;
   Set<uint32_t> Cov, NewCov;
   Vector<std::string> NewFiles;
 
EXPECT_TRUE(M.Parse("3\n2\nA\nB\nC\n"
                       "FT 1 4 5 6 \n"
                       "STARTED 2 1002\n"
                       "FT 2 6 1 3\n"
                       "",
                       true));
   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 0U);
   TRACED_EQ(M.Files, {"A", "B", "C"});
   TRACED_EQ(NewFiles, {});
-  TRACED_EQ(NewFeatures, {});
+  EXPECT_TRUE(NewFeatures.empty());
 
   // Can pass initial features and coverage.
-  Features = {1, 2, 3};
+  Features.insert(1);
+  Features.insert(2);
+  Features.insert(3);
   Cov = {};
   EXPECT_TRUE(M.Parse("2\n0\nA\nB\n"
                       "STARTED 0 1000\n"
                       "FT 0 1 2 3\n"
                       "STARTED 1 1001\n"
                       "FT 1 4 5 6\n"
                       "",
                       true));
EXPECT_TRUE(M.Parse("4\n1\nA\nB\nC\nD\n"
                       "STARTED 3 1000\n"
                       "FT 3 1  \n"
                       "",
                       true));
   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 3U);
   TRACED_EQ(M.Files, {"A", "B", "C", "D"});
   TRACED_EQ(NewFiles, {"D", "B"});
   TRACED_EQ(NewFeatures, {1, 2, 3});
+
+  // Relative features for unknown modules are counted and used for determining
+  // file order, but are not returned.
+  static FakeModule<512> Module;
+  ModuleInfo Info;
+  EXPECT_FALSE(TPC.ModuleInfoByHash(Module.Hash(), &Info));
+  std::ostringstream OSS;
+  OSS << "4\n1\nA\nB\nC\nD\n";
+  OSS << "STARTED 0 2000\n";
+  OSS << "FT 0 4 5 6 7 8\n";
+  OSS << "STARTED 1 1100\n";
+  OSS << "FT_REL 1 " << std::hex << Module.Hash() << std::dec << " 11 12 13 \n";
+  OSS << "STARTED 2 1100\n";
+  OSS << "FT_REL 2 " << std::hex << Module.Hash() << std::dec << " 12 13 \n";
+  OSS << "STARTED 3 1000\n";
+  OSS << "FT 3 1  \n";
+  auto MCF = OSS.str();
+  EXPECT_TRUE(M.Parse(MCF, true));
+  EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 4U);
+  TRACED_EQ(M.Files, {"A", "B", "C", "D"});
+  TRACED_EQ(NewFiles, {"D", "B"});
+  TRACED_EQ(NewFeatures, {1});
+
+  // Relative features for known modules are translated to absolute. The dummy
+  // module is used to ensure that the first feature is non-zero regardless of
+  // whether the tests are built with instrumentation of not.
+  static FakeModule<64> Dummy;
+  Dummy.AddToTPC();
+
+  Module.AddToTPC();
+  EXPECT_TRUE(TPC.ModuleInfoByHash(Module.Hash(), &Info));
+  EXPECT_NE(Info.FirstFeature, 0U);
+
+  EXPECT_TRUE(M.Parse(MCF, true));
+  EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 4U);
+  TRACED_EQ(M.Files, {"A", "B", "C", "D"});
+  TRACED_EQ(NewFiles, {"D", "B"});
+  Vector<uint32_t> Expected({1});
+  Expected.push_back(static_cast<uint32_t>(Info.FirstFeature + 11));
+  Expected.push_back(static_cast<uint32_t>(Info.FirstFeature + 12));
+  Expected.push_back(static_cast<uint32_t>(Info.FirstFeature + 13));
+  TRACED_EQ(NewFeatures, Expected);
 }
 
 #undef TRACED_EQ
 
 TEST(DFT, BlockCoverage) {
   BlockCoverage Cov;
   // Assuming C0 has 5 instrumented blocks,
   // C1: 7 blocks, C2: 4, C3: 9, C4 never covered, C5: 15,

compiler-rt/test/fuzzer/merge-control-file.test

 RUN: echo 3 > %t/MCF; echo 0 >> %t/MCF; echo %t/T1/1 >> %t/MCF; echo %t/T1/2 >> %t/MCF; echo %t/T1/3 >> %t/MCF
 RUN: %run %t/T.exe -merge=1 %t/T1 %t/T2 -merge_control_file=%t/MCF 2>&1 | FileCheck %s --check-prefix=OK_0
 OK_0: MERGE-OUTER: control file ok, 3 files total, first not processed file 0
 OK_0: MERGE-OUTER: 3 new files with {{.*}} new features added
 
 RUN: rm -f %t/T1/*; cp %t/T0/* %t/T1
 RUN: echo 3 > %t/MCF; echo 0 >> %t/MCF; echo %t/T1/1 >> %t/MCF; echo %t/T1/2 >> %t/MCF; echo %t/T1/3 >> %t/MCF
 RUN: echo STARTED 0 1 >> %t/MCF
-RUN: echo FT 0 11 >> %t/MCF
+RUN: echo FT 0 0xdeadbeef 11 >> %t/MCF
 RUN: echo STARTED 1 2 >> %t/MCF
-RUN: echo FT 1 12 >> %t/MCF
+RUN: echo FT 1 0xcafef00d 12 >> %t/MCF
 RUN: %run %t/T.exe -merge=1 %t/T1 %t/T2 -merge_control_file=%t/MCF 2>&1 | FileCheck %s --check-prefix=OK_2
 OK_2: MERGE-OUTER: control file ok, 3 files total, first not processed file 2
 OK_2: MERGE-OUTER: 3 new files with {{.*}} new features added
 
 RUN: rm -f %t/T1/*; cp %t/T0/* %t/T1
 RUN: echo 3 > %t/MCF; echo 0 >> %t/MCF; echo %t/T1/1 >> %t/MCF; echo %t/T1/2 >> %t/MCF; echo %t/T1/3 >> %t/MCF
 RUN: echo STARTED 0 1 >> %t/MCF
-RUN: echo FT 0 11 >> %t/MCF
+RUN: echo FT 0 0xdeadbeef 11 >> %t/MCF
 RUN: echo STARTED 1 2 >> %t/MCF
-RUN: echo FT 1 12 >> %t/MCF
+RUN: echo FT 1 0xcafef00d 12 >> %t/MCF
 RUN: echo STARTED 2 2 >> %t/MCF
-RUN: echo FT 2 13 >> %t/MCF
+RUN: echo FT 2 0x12345678 13 >> %t/MCF
 RUN: %run %t/T.exe -merge=1 %t/T1 %t/T2 -merge_control_file=%t/MCF 2>&1 | FileCheck %s --check-prefix=OK_3
 OK_3: MERGE-OUTER: nothing to do, merge has been completed before

compiler-rt/test/fuzzer/merge.test

 MCF: MERGE-OUTER: 3 new files
 
 
 # Check that merge tolerates failures.
 RUN: rm %t/T1/*
 RUN: cp %t/T0/* %t/T1/
 RUN: echo 'FUZZER' > %t/T2/FUZZER
 RUN: %run %t-FullCoverageSetTest -merge=1 %t/T1 %t/T2 2>&1 | FileCheck %s --check-prefix=MERGE_WITH_CRASH
-MERGE_WITH_CRASH: MERGE-OUTER: succesfull in 2 attempt(s)
+MERGE_WITH_CRASH: MERGE-OUTER: successful in 2 attempt(s)
 MERGE_WITH_CRASH: MERGE-OUTER: 3 new files
 
 # Check that we actually limit the size with max_len
 RUN: rm %t/T1/* %t/T2/*
 RUN: echo 'FUZZER' > %t/T2/FUZZER
 RUN: %run %t-FullCoverageSetTest -merge=1 %t/T1 %t/T2  -max_len=5 2>&1 | FileCheck %s --check-prefix=MERGE_LEN5
 RUN: not grep FUZZER %t/T1/*
 RUN: grep FUZZE %t/T1/*
-MERGE_LEN5: MERGE-OUTER: succesfull in 1 attempt(s)
+MERGE_LEN5: MERGE-OUTER: successful in 1 attempt(s)