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

437

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

445

Please explain this calculation with a comment.

464

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

501

compiler-rt/lib/fuzzer/FuzzerMerge.cpp

51

Please update this comment.

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

895

Bitmask is superfluous.

923

This only compares Len bytes, not Len uint32_ts.

930

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

1011

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

1056–1057

How are these "unknown markers"?

1067

Please remove.

[aarongreen]

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

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

923

Whoops! Thanks, good catch!

1011

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.

1056–1057

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

437

This is now handled by D97992.

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

930

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

109

I think we can remove the ParseRelative stuff.

204

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

252

Shouldn't UniqFeatures already be sorted?

[aarongreen]

compiler-rt/lib/fuzzer/FuzzerMerge.cpp

109

Whoops!

204

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.

252

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/FuzzerDriver.cpp

void Merge(Fuzzer *F, FuzzingOptions &Options, const Vector<std::string> &Args,
   GetSizedFilesFromDir(Corpora[0], &OldCorpus);
   for (size_t i = 1; i < Corpora.size(); i++)
     GetSizedFilesFromDir(Corpora[i], &NewCorpus);
   std::sort(OldCorpus.begin(), OldCorpus.end());
   std::sort(NewCorpus.begin(), NewCorpus.end());
 
   std::string CFPath = CFPathOrNull ? CFPathOrNull : TempPath("Merge", ".txt");
   Vector<std::string> NewFiles;
-  Set<uint32_t> NewFeatures, NewCov;
+  DSORelativeValues NewFeatures, NewCov;
   CrashResistantMerge(Args, OldCorpus, NewCorpus, &NewFiles, {}, &NewFeatures,
                       {}, &NewCov, CFPath, true);
   for (auto &Path : NewFiles)
     F->WriteToOutputCorpus(FileToVector(Path, Options.MaxLen));
   // We are done, delete the control file if it was a temporary one.
   if (!Flags.merge_control_file)
     RemoveFile(CFPath);
 

compiler-rt/lib/fuzzer/FuzzerFork.h

 //===- FuzzerFork.h - run fuzzing in sub-processes --------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_FUZZER_FORK_H
 #define LLVM_FUZZER_FORK_H
 
+#include "FuzzerDSORelative.h"
 #include "FuzzerDefs.h"
 #include "FuzzerOptions.h"
 #include "FuzzerRandom.h"
 
 #include <string>
 
 namespace fuzzer {
 
 void FuzzWithFork(Random &Rand, const FuzzingOptions &Options,
                   const Vector<std::string> &Args,
                   const Vector<std::string> &CorpusDirs, int NumJobs);
 
+// Feature files encode features in a format that organizes them by DSO.
+// Example:
+// 0x0000002                        # Number of DSOs
+// 0xdeadbeef 0xfeedface 0x00000003 # Hash upper half, lower half, num features
+// 0x00000011 0x00000022 0x00000033 # Sorted DSO-relative features
+// ...                              # Next DSO
+bool DecodeFeatures(const Vector<uint32_t> &Encoded,
+                    DSORelativeValues *Features);
 void EncodeFeatures(const Vector<uint32_t> &Features,
                     Vector<uint32_t> *Encoded);
-bool DecodeFeatures(const Vector<uint32_t> &Encoded,
-                    Vector<uint32_t> *Features);
 
 } // namespace fuzzer
 
 #endif // LLVM_FUZZER_FORK_H

compiler-rt/lib/fuzzer/FuzzerFork.cpp

 
 struct GlobalEnv {
   Vector<std::string> Args;
   Vector<std::string> CorpusDirs;
   std::string MainCorpusDir;
   std::string TempDir;
   std::string DFTDir;
   std::string DataFlowBinary;
-  Set<uint32_t> Features, Cov;
+  DSORelativeValues Features, Cov;
   Set<std::string> FilesWithDFT;
   Vector<std::string> Files;
   Random *Rand;
   std::chrono::system_clock::time_point ProcessStartTime;
   int Verbosity = 0;
 
   size_t NumTimeouts = 0;
   size_t NumOOMs = 0;
FuzzJob *CreateNewJob(size_t JobId) {
     return Job;
   }
 
   void RunOneMergeJob(FuzzJob *Job) {
     auto Stats = ParseFinalStatsFromLog(Job->LogPath);
     NumRuns += Stats.number_of_executed_units;
 
     Vector<SizedFile> TempFiles, MergeCandidates;
+    DSORelativeValues NewFeatures, NewCov;
     // Read all newly created inputs and their feature sets.
     // Choose only those inputs that have new features.
     GetSizedFilesFromDir(Job->CorpusDir, &TempFiles);
     std::sort(TempFiles.begin(), TempFiles.end());
     for (auto &F : TempFiles) {
       auto FeatureFile = F.File;
       FeatureFile.replace(0, Job->CorpusDir.size(), Job->FeaturesDir);
       auto FeatureBytes = FileToVector(FeatureFile, 0, false);
       assert((FeatureBytes.size() % sizeof(uint32_t)) == 0);
       Vector<uint32_t> Encoded(FeatureBytes.size() / sizeof(uint32_t));
       memcpy(Encoded.data(), FeatureBytes.data(), FeatureBytes.size());
-      Vector<uint32_t> NewFeatures;
       if (DecodeFeatures(Encoded, &NewFeatures))
-        if (!std::includes(Features.begin(), Features.end(),
-                           NewFeatures.begin(), NewFeatures.end()))
+        if (!Features.Includes(NewFeatures))
           MergeCandidates.push_back(F);
     }
     // if (!FilesToAdd.empty() || Job->ExitCode != 0)
     Printf("#%zd: cov: %zd ft: %zd corp: %zd exec/s %zd "
            "oom/timeout/crash: %zd/%zd/%zd time: %zds job: %zd dft_time: %d\n",
            NumRuns, Cov.size(), Features.size(), Files.size(),
            Stats.average_exec_per_sec, NumOOMs, NumTimeouts, NumCrashes,
            secondsSinceProcessStartUp(), Job->JobId, Job->DftTimeInSeconds);
 
     if (MergeCandidates.empty()) return;
 
     Vector<std::string> FilesToAdd;
-    Set<uint32_t> NewFeatures, NewCov;
     CrashResistantMerge(Args, {}, MergeCandidates, &FilesToAdd, Features,
                         &NewFeatures, Cov, &NewCov, Job->CFPath, false);
     for (auto &Path : FilesToAdd) {
       auto U = FileToVector(Path);
       auto NewPath = DirPlusFile(MainCorpusDir, Hash(U));
       WriteToFile(U, NewPath);
       Files.push_back(NewPath);
     }
-    Features.insert(NewFeatures.begin(), NewFeatures.end());
-    Cov.insert(NewCov.begin(), NewCov.end());
-    for (auto Idx : NewCov)
-      if (auto *TE = TPC.PCTableEntryByIdx(Idx))
+    Features.Merge(NewFeatures);
+    Cov.Merge(NewCov);
+    NewCov.ForEachValue([](uint64_t DSO, uint32_t Offset) {
+      if (auto *TE = TPC.PCTableEntryByDSO(DSO, Offset))
         if (TPC.PcIsFuncEntry(TE))
           PrintPC("  NEW_FUNC: %p %F %L\n", "",
                   TPC.GetNextInstructionPc(TE->PC));
-
+    });
   }
 
 
   void CollectDFT(const std::string &InputPath) {
     if (DataFlowBinary.empty()) return;
     if (!FilesWithDFT.insert(InputPath).second) return;
     Command Cmd(Args);
     Cmd.removeFlag("fork");
void FuzzWithFork(Random &Rand, const FuzzingOptions &Options,
   else
     Env.MainCorpusDir = CorpusDirs[0];
 
   if (Options.KeepSeed) {
     for (auto &File : SeedFiles)
       Env.Files.push_back(File.File);
   } else {
     auto CFPath = DirPlusFile(Env.TempDir, "merge.txt");
-    Set<uint32_t> NewFeatures, NewCov;
+    DSORelativeValues NewFeatures, NewCov;
     CrashResistantMerge(Env.Args, {}, SeedFiles, &Env.Files, Env.Features,
                         &NewFeatures, Env.Cov, &NewCov, CFPath, false);
-    Env.Features.insert(NewFeatures.begin(), NewFeatures.end());
-    Env.Cov.insert(NewFeatures.begin(), NewFeatures.end());
+    Env.Features.Merge(NewFeatures);
+    Env.Cov.Merge(NewCov);
     RemoveFile(CFPath);
   }
   Printf("INFO: -fork=%d: %zd seed inputs, starting to fuzz in %s\n", NumJobs,
          Env.Files.size(), Env.TempDir.c_str());
 
   int ExitCode = 0;
 
   JobQueue FuzzQ, MergeQ;
void FuzzWithFork(Random &Rand, const FuzzingOptions &Options,
   RmDirRecursive(Env.TempDir);
 
   // Use the exit code from the last child process.
   Printf("INFO: exiting: %d time: %zds\n", ExitCode,
          Env.secondsSinceProcessStartUp());
   exit(ExitCode);
 }
 
+// For the purpose of encoding and decoding features, the encoded vector has the
+// following format (in EBNF):
+//
+//   encoded = num_dso, { hash_upper, hash_lower, num_features, { feature } }
+//
+// where the following fields are uint32_ts with the following meanings:
+//   num_dsos:     The number of DSOs.
+//   hash_upper:   The upper 32 bits of the DSO hash.
+//   hash_lower:   The lower 32 bits of the DSO hash.
+//   num_features: The number of features for a given DSO.
 void EncodeFeatures(const Vector<uint32_t> &Features,
                     Vector<uint32_t> *Encoded) {
   assert(Encoded);
+
+  // Convert Features to be DSO-relative.
+  DSORelativeValues TmpFeatures;
+  DSOInfo Info;
+  Set<uint32_t> Tmp;
+  size_t NumFeatures = 0;
+  bool First = true;
+  for (auto Feature : Features) {
+    // Only look up a new DSO when needed. |CollectFeatures| orders the features
+    // by DSO, so this should be the minimum number of lookups needed.
+    if (Feature < Info.FirstFeature || Info.LastFeature <= Feature || First) {
+      TmpFeatures.Merge(Info.Hash, Tmp);
+      Tmp.clear();
+      TPC.DSOInfoByFeature(Feature, &Info);
+      NumFeatures = 0;
+      First = false;
+    }
+    // Cap the number of features to what can be expressed by Numfeatures.
+    if (NumFeatures < std::numeric_limits<uint32_t>::max())
+      Tmp.insert(Feature - Info.FirstFeature);
+  };
+  TmpFeatures.Merge(Info.Hash, Tmp);
+
+  // Acording to the format given above, the total length of the encoded vector
+  // is the number of features, plus 3 for each DSO (for hash_upper, hash_lower,
+  // num_features), plus 1 more (for num_dsos).
+  uint32_t NumDSOs = TmpFeatures.NumDSOs();
+  size_t NumValues = 1 + (NumDSOs * 3) + TmpFeatures.size();
   Encoded->clear();
-  Encoded->resize(Features.size());
-  std::partial_sort_copy(Features.begin(), Features.end(), Encoded->begin(),
-                         Encoded->end());
+  Encoded->reserve(NumValues);
+  Encoded->push_back(NumDSOs);
+
+  uint64_t Cur = 0;
+  First = true;
+  TmpFeatures.ForEachValue([&](uint64_t Hash, uint32_t Feature) {
+    if (Hash != Cur || First) {
+      // Write DSO metadata: hash upper, hash lower, and num features.
+      Encoded->push_back(static_cast<uint32_t>(Hash >> 32));
+      Encoded->push_back(static_cast<uint32_t>(Hash));
+      Encoded->push_back(TmpFeatures.NumValuesForDSO(Hash));
+      Cur = Hash;
+      First = false;
+    }
+    // Write each feature.
+    Encoded->push_back(Feature);
+  });
 }
 
 bool DecodeFeatures(const Vector<uint32_t> &Encoded,
-                    Vector<uint32_t> *Features) {
-  assert(Features);
-  if (!std::is_sorted(Encoded.begin(), Encoded.end()))
+                    DSORelativeValues *Features) {
+  if (Encoded.empty())
     return false;
   Features->clear();
-  Features->insert(Features->end(), Encoded.begin(), Encoded.end());
-  return true;
+
+  auto *I = &Encoded[0];
+  size_t Remaining = Encoded.size();
+
+  uint32_t RemainingDSOs = *I++;
+  --Remaining;
+
+  // Read the number of expected DSOs.
+  for (; RemainingDSOs; --RemainingDSOs) {
+    if (Remaining < 3)
+      return false;
+
+    // Read DSO metadata: hash upper, hash lower, and num features.
+    uint64_t Hash = *I++;
+    Hash <<= 32;
+    Hash |= *I++;
+    auto NumFeatures = *I++;
+    Remaining -= 3;
+    if (Remaining < NumFeatures)
+      return false;
+
+    // Read each feature. `EncodeFeatures` required that these were sorted,
+    // so they should still be.
+    if (!std::is_sorted(I, I + NumFeatures))
+      return false;
+
+    Set<uint32_t> Values(I, I + NumFeatures);
+    Features->Merge(Hash, Values);
+    I += NumFeatures;
+    Remaining -= NumFeatures;
+  }
+  return Remaining == 0;
 }
 
 } // namespace fuzzer

compiler-rt/lib/fuzzer/FuzzerMerge.h

 //   It uses a single pass greedy algorithm choosing first the smallest inputs
 //   within the same size the inputs that have more new features.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_FUZZER_MERGE_H
 #define LLVM_FUZZER_MERGE_H
 
+#include "FuzzerDSORelative.h"
 #include "FuzzerDefs.h"
+#include "FuzzerIO.h"
 
 #include <istream>
 #include <ostream>
 #include <set>
 #include <vector>
 
 namespace fuzzer {
 
 struct MergeFileInfo {
   std::string Name;
   size_t Size = 0;
-  Vector<uint32_t> Features, Cov;
+  DSORelativeValues Features, Cov;
 };
 
 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);
-  size_t Merge(const Set<uint32_t> &InitialFeatures, Set<uint32_t> *NewFeatures,
-               const Set<uint32_t> &InitialCov, Set<uint32_t> *NewCov,
+  size_t Merge(const DSORelativeValues &InitialFeatures,
+               DSORelativeValues *NewFeatures,
+               const DSORelativeValues &InitialCov, DSORelativeValues *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);
+void CrashResistantMerge(
+    const Vector<std::string> &Args, const Vector<SizedFile> &OldCorpus,
+    const Vector<SizedFile> &NewCorpus, Vector<std::string> *NewFiles,
+    const DSORelativeValues &InitialFeatures, DSORelativeValues *NewFeatures,
+    const DSORelativeValues &InitialCov, DSORelativeValues *NewCov,
+    const std::string &CFPath, bool Verbose);
 
 }  // namespace fuzzer
 
 #endif  // LLVM_FUZZER_MERGE_H

compiler-rt/lib/fuzzer/FuzzerMerge.cpp

 // 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
 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;
bool Merger::Parse(std::istream &IS, bool ParseCoverage) {
   for (size_t i = 0; i < NumFiles; i++)
     if (!std::getline(IS, Files[i].Name, '\n'))
       return false;
 
   // Parse STARTED, FT, and COV lines.
   size_t ExpectedStartMarker = 0;
   const size_t kInvalidStartMarker = -1;
   size_t LastSeenStartMarker = kInvalidStartMarker;
-  Vector<uint32_t> TmpFeatures;
-  Set<uint32_t> PCs;
+  bool HasFeatures = true;
+  uint64_t Hash = 0;
+  Set<uint32_t> Tmp, NewCov;
+  DSORelativeValues AllCov;
   while (std::getline(IS, Line, '\n')) {
     std::istringstream ISS1(Line);
     std::string Marker;
     size_t N;
     ISS1 >> Marker;
     ISS1 >> N;
     if (Marker == "STARTED") {
       // STARTED FILE_ID FILE_SIZE
       if (ExpectedStartMarker != N)
         return false;
       ISS1 >> Files[ExpectedStartMarker].Size;
       LastSeenStartMarker = ExpectedStartMarker;
       assert(ExpectedStartMarker < Files.size());
       ExpectedStartMarker++;
+      HasFeatures = false;
     } else if (Marker == "FT") {
-      // FT FILE_ID COV1 COV2 COV3 ...
+      // FT FILE_ID HASH FT1 FT2 FT3 ...
       size_t CurrentFileIdx = N;
       if (CurrentFileIdx != LastSeenStartMarker)
         return false;
-      LastSeenStartMarker = kInvalidStartMarker;
+      HasFeatures = true;
+      ISS1 >> std::hex >> Hash >> std::dec;
+      if (!ISS1)
+        return false;
       if (ParseCoverage) {
-        TmpFeatures.clear();  // use a vector from outer scope to avoid resizes.
+        Tmp.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;
+          Tmp.insert(N);
+        Files[CurrentFileIdx].Features.Merge(Hash, Tmp);
       }
     } else if (Marker == "COV") {
+      // COV FILE_ID HASH COV1 COV2 COV3 ...
       size_t CurrentFileIdx = N;
-      if (ParseCoverage)
+      if (CurrentFileIdx != LastSeenStartMarker)
+        return false;
+      ISS1 >> std::hex >> Hash >> std::dec;
+      if (!ISS1)
+        return false;
+      if (ParseCoverage) {
+        Tmp.clear();
         while (ISS1 >> N)
-          if (PCs.insert(N).second)
-            Files[CurrentFileIdx].Cov.push_back(N);
+          Tmp.insert(N);
+        AllCov.Merge(Hash, Tmp, &NewCov);
+        Files[CurrentFileIdx].Cov.Merge(Hash, NewCov);
+      }
     } else {
       return false;
     }
   }
-  if (LastSeenStartMarker != kInvalidStartMarker)
+  if (!HasFeatures)
     LastFailure = Files[LastSeenStartMarker].Name;
 
   FirstNotProcessedFile = ExpectedStartMarker;
   return true;
 }
 
 size_t Merger::ApproximateMemoryConsumption() const  {
   size_t Res = 0;
-  for (const auto &F: Files)
-    Res += sizeof(F) + F.Features.size() * sizeof(F.Features[0]);
+  for (const auto &F : Files) {
+    Res += sizeof(F);
+    Res += F.Features.NumDSOs() * sizeof(uint64_t);
+    Res += F.Features.NumValues() * sizeof(uint32_t);
+  }
   return Res;
 }
 
 // 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) {
+size_t Merger::Merge(const DSORelativeValues &InitialFeatures,
+                     DSORelativeValues *NewFeatures,
+                     const DSORelativeValues &InitialCov,
+                     DSORelativeValues *NewCov, Vector<std::string> *NewFiles) {
   NewFiles->clear();
   NewFeatures->clear();
   NewCov->clear();
   assert(NumFilesInFirstCorpus <= Files.size());
-  Set<uint32_t> AllFeatures = InitialFeatures;
+  DSORelativeValues AllFeatures, AllCov;
+  AllFeatures.Merge(InitialFeatures);
+  AllCov.Merge(InitialCov);
 
   // What features 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];
+    AllFeatures.Merge(File.Features);
+    AllCov.Merge(File.Cov);
   }
   // 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);
-  }
+  for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++)
+    Files[i].Features.Deduplicate(AllFeatures);
 
   // 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();
             });
 
   // One greedy pass: add the file's features to AllFeatures.
   // If new features were added, add this file to NewFiles.
   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);
-      }
-    }
-    if (FoundNewFeatures)
-      NewFiles->push_back(Files[i].Name);
-    for (auto Cov : Files[i].Cov)
-      if (InitialCov.find(Cov) == InitialCov.end())
-        NewCov->insert(Cov);
+    auto &File = Files[i];
+    if (AllFeatures.Merge(File.Features, NewFeatures))
+      NewFiles->push_back(File.Name);
+    AllCov.Merge(File.Cov, NewCov);
   }
   return NewFeatures->size();
 }
 
-Set<uint32_t> Merger::AllFeatures() const {
-  Set<uint32_t> S;
-  for (auto &File : Files)
-    S.insert(File.Features.begin(), File.Features.end());
-  return S;
-}
-
 // Inner process. May crash if the target crashes.
 void Fuzzer::CrashResistantMergeInternalStep(const std::string &CFPath) {
   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;
+  DSORelativeValues AllFeatures;
   auto PrintStatsWrapper = [this, &AllFeatures](const char* Where) {
     this->PrintStats(Where, "\n", 0, AllFeatures.size());
   };
-  Set<const TracePC::PCTableEntry *> AllPCs;
+  DSORelativeValues AllCov;
   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;
+    DSOInfo Info;
+    Set<uint32_t> Tmp;
+    DSORelativeValues Features, UniqFeatures;
     TPC.CollectFeatures([&](size_t Feature) {
-      if (AllFeatures.insert(Feature).second)
-        UniqFeatures.insert(Feature);
+      if (Feature < Info.FirstFeature || Info.LastFeature <= Feature) {
+        Features.Merge(Info.Hash, Tmp);
+        TPC.DSOInfoByFeature(Feature, &Info);
+      }
+      Tmp.insert(Feature - Info.FirstFeature);
     });
+    Features.Merge(Info.Hash, Tmp);
+    AllFeatures.Merge(Features, &UniqFeatures);
+
+    Tmp.clear();
+    DSORelativeValues Cov, UniqCov;
     TPC.UpdateObservedPCs();
+    TPC.ForEachObservedPC([&](const TracePC::PCTableEntry *TE) {
+      uintptr_t Idx = TPC.PCTableEntryIdx(TE);
+      if (Idx < Info.FirstIdx || Info.LastIdx <= Idx) {
+        Cov.Merge(Info.Hash, Tmp);
+        TPC.DSOInfoByIdx(Idx, &Info);
+      }
+      Tmp.insert(Idx - Info.FirstIdx);
+    });
+    Cov.Merge(Info.Hash, Tmp);
+    AllCov.Merge(Cov, &UniqCov);
+
     // Show stats.
     if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)))
       PrintStatsWrapper("pulse ");
     if (TotalNumberOfRuns == M.NumFilesInFirstCorpus)
       PrintStatsWrapper("LOADED");
+
     // Write the post-run marker and the coverage.
-    OF << "FT " << i;
-    for (size_t F : UniqFeatures)
-      OF << " " << F;
+    uintptr_t FirstIdx = 0;
+    while (true) {
+      TPC.DSOInfoByIdx(FirstIdx, &Info);
+      if (!Info.Hash)
+        break;
+      auto *UF = UniqFeatures.get(Info.Hash);
+      if (UF) {
+        OF << "FT " << i << " 0x" << std::hex << Info.Hash << std::dec;
+        for (uint32_t Feature : *UF)
+          OF << " " << Feature;
         OF << "\n";
-    OF << "COV " << i;
-    TPC.ForEachObservedPC([&](const TracePC::PCTableEntry *TE) {
-      if (AllPCs.insert(TE).second)
-        OF << " " << TPC.PCTableEntryIdx(TE);
-    });
+      }
+      auto *UC = UniqCov.get(Info.Hash);
+      if (UC) {
+        OF << "COV " << i << " 0x" << std::hex << Info.Hash << std::dec;
+        for (uint32_t Idx : *UC)
+          OF << " " << Idx;
         OF << "\n";
+      }
+      FirstIdx = Info.LastIdx;
+    }
     OF.flush();
   }
   PrintStatsWrapper("DONE  ");
 }
 
 static size_t WriteNewControlFile(const std::string &CFPath,
                                   const Vector<SizedFile> &OldCorpus,
                                   const Vector<SizedFile> &NewCorpus,
Printf("MERGE-OUTER: failed to write to the control file: %s\n",
            CFPath.c_str());
     exit(1);
   }
 
   return FilesToUse.size();
 }
 
 // Outer process. Does not call the target code and thus should not fail.
-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 V /*Verbose*/) {
+void CrashResistantMerge(
+    const Vector<std::string> &Args, const Vector<SizedFile> &OldCorpus,
+    const Vector<SizedFile> &NewCorpus, Vector<std::string> *NewFiles,
+    const DSORelativeValues &InitialFeatures, DSORelativeValues *NewFeatures,
+    const DSORelativeValues &InitialCov, DSORelativeValues *NewCov,
+    const std::string &CFPath, bool V /*Verbose*/) {
   if (NewCorpus.empty() && OldCorpus.empty()) return;  // Nothing to merge.
   size_t NumAttempts = 0;
   Vector<MergeFileInfo> KnownFiles;
   if (FileSize(CFPath)) {
     VPrintf(V, "MERGE-OUTER: non-empty control file provided: '%s'\n",
            CFPath.c_str());
     Merger M;
     std::ifstream IF(CFPath);
for (size_t Attempt = 1; Attempt <= NumAttempts; Attempt++) {
     Cmd.addFlag("merge_control_file", CFPath);
     Cmd.addFlag("merge_inner", "1");
     if (!V) {
       Cmd.setOutputFile(getDevNull());
       Cmd.combineOutAndErr();
     }
     auto ExitCode = ExecuteCommand(Cmd);
     if (!ExitCode) {
-      VPrintf(V, "MERGE-OUTER: succesfull in %zd attempt(s)\n", Attempt);
+      VPrintf(V, "MERGE-OUTER: successful in %zd attempt(s)\n", Attempt);
       break;
     }
   }
   // Read the control file and do the merge.
   Merger M;
   std::ifstream IF(CFPath);
   IF.seekg(0, IF.end);
   VPrintf(V, "MERGE-OUTER: the control file has %zd bytes\n",

compiler-rt/lib/fuzzer/FuzzerTracePC.cpp

if (NumExtraCounters)
     Printf("INFO: %zd Extra Counters\n", NumExtraCounters);
 
   // See TracePC::CollectCoverage. Features are converted from inline 8-bit
   // counters, extra counters, the value profile map, and the stack depth.
   size_t MaxFeatures = NumPCsInPCTables * 8;
   MaxFeatures += NumExtraCounters * 8;
   MaxFeatures += ValueProfileMap.SizeInBits();
   MaxFeatures += StackDepthStepFunction(std::numeric_limits<uintptr_t>::max());
-  if (MaxFeatures > static_cast<size_t>(std::numeric_limits<uint32_t>::max()))
+  if (MaxFeatures > std::numeric_limits<uint32_t>::max())
     Printf("WARNING: The number of features cannot be expressed in 32 bits.\n"
            "This may reduce the precision of corpus merging.\n");
 }
 
 ATTRIBUTE_NO_SANITIZE_ALL
 void TracePC::HandleCallerCallee(uintptr_t Caller, uintptr_t Callee) {
   const uintptr_t kBits = 12;
   const uintptr_t kMask = (1 << kBits) - 1;

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

 }
 
 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 covergae data for unit tests. Note that once
+// 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 FakeDSO static within the test that adds it to the coverage.
 template <size_t N> struct FakeDSO final {
 public:
   uint8_t Counters[N];
   uintptr_t PCs[N * 2];

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

TPC.CollectFeatures(
       [&](size_t F) { Features.push_back(static_cast<uint32_t>(F)); });
   EncodeFeatures(Features, Encoded);
 }
 
 template <size_t N>
 void CheckEncodedFeatures(FakeDSO<N> &DSO, bool UseCounters) {
   // Ensure the DSO has been added to the TracePC
   auto *B = reinterpret_cast<const TracePC::PCTableEntry *>(DSO.PCs);
-  uintptr_t Idx = 0;
-  while (true) {
+  for (uintptr_t Idx = 0;; ++Idx) {
     auto *TE = TPC.PCTableEntryByIdx(Idx);
     if (!TE) {
       TPC.HandlePCsInit(DSO.PCs, DSO.PCsEnd());
       TPC.HandleInline8bitCountersInit(DSO.Counters, DSO.CountersEnd());
       break;
     }
     if (TE == B)
       break;
-    ++Idx;
   }
 
   // Generate the sequence of relative encoded features for the given DSO.
-  Vector<uint32_t> Expected;
+  auto Hash = TracePC::HashPCs(DSO.PCs, DSO.PCsEnd());
+  Vector<uint32_t> Expected = {
+      static_cast<uint32_t>(Hash >> 32), static_cast<uint32_t>(Hash),
+      0, // NumFeatures; fill in below.
+  };
+  uint32_t NumFeatures = 0;
   for (size_t i = 0; i < DSO.NumPCs; ++i) {
-    if (DSO.Counters[i]) {
-      if (UseCounters)
-        Expected.push_back(Idx * 8 + CounterToFeature(DSO.Counters[i]));
-      else
-        Expected.push_back(Idx);
-    }
-    ++Idx;
+    if (!DSO.Counters[i])
+      continue;
+      Expected.push_back(i * 8 + CounterToFeature(DSO.Counters[i]));
+      Expected.push_back(i);
+    ++NumFeatures;
   }
+  Expected[2] = NumFeatures;
+  uint32_t *E = &Expected[0];
+  size_t Len = Expected.size();
 
   // Now get the actual encoded features, and look for the expected ones.
+  bool Found = false;
   Vector<uint32_t> Actual;
   CollectEncodedFeatures(&Actual);
-  auto I = std::search(Actual.begin(), Actual.end(), Expected.begin(),
-                       Expected.end());
-  EXPECT_NE(I, Actual.end());
+  size_t Left = Actual.size();
+  // Get the number of DSOs, then advance to the first DSO header.
+  ASSERT_GE(Left, 1U);
+  uint32_t *A = &Actual[0];
+  uint32_t NumDSOs = A[0];
+  A += 1;
+  Left -= 1;
+  // Loop through all the DSOs and validate their headers.
+  for (size_t i = 0; i < NumDSOs; ++i) {
+    if (!Found && Left >= Len)
+      Found = memcmp(E, A, Len * sizeof(uint32_t)) == 0;
+    // Advance to the next DSO: get the number of features from the header and
+    // then advance past it.
+    ASSERT_GE(Left, 3U);
+    NumFeatures = A[2];
+    A += 3;
+    Left -= 3;
+    // Now make sure the number of features makes sense, then advance past them.
+    ASSERT_GE(Left, NumFeatures);
+    A += NumFeatures;
+    Left -= NumFeatures;
+  }
+  EXPECT_TRUE(Found);
 }
 
 TEST(FuzzerFork, EncodeFeatures) {
   // No counters, values, or stack should result in an empty set of features.
   Vector<uint32_t> Previous, Encoded;
   TPC.SetUseCounters(0);
   TPC.SetUseValueProfileMask(0);
   TPC.RecordInitialStack();
   TPC.ResetMaps();
   CollectEncodedFeatures(&Encoded);
-  TRACED_EQ(Encoded, {});
+  TRACED_EQ(Encoded, {0});
 
   // Add a DSO. It will be added to TPC, so make it static to allow the test to
   // be run multiple times.
   static FakeDSO<4> DSO1;
   DSO1.Counters[0] = 3;
   DSO1.Counters[1] = 2;
   DSO1.Counters[2] = 1;
   DSO1.Counters[3] = 0; // Not encoded.
-  CheckEncodedFeatures(DSO1, /* UseCounters */ false);
+  {
+    SCOPED_TRACE("DSO1");
+    EXPECT_NO_FATAL_FAILURE(CheckEncodedFeatures(DSO1, /*UseCounters*/ false));
+  }
 
   //  Add a second DSO. This time, use counters.
   TPC.SetUseCounters(1);
   static FakeDSO<9> DSO2;
   DSO2.Counters[0] = 0; // Not encoded.
   DSO2.Counters[1] = 1;
   DSO2.Counters[2] = 2;
   DSO2.Counters[3] = 3;
   DSO2.Counters[4] = 4;
   DSO2.Counters[5] = 8;
   DSO2.Counters[6] = 16;
   DSO2.Counters[7] = 32;
   DSO2.Counters[8] = 128;
-  CheckEncodedFeatures(DSO2, /* UseCounters */ true);
+  {
+    SCOPED_TRACE("DSO2");
+    EXPECT_NO_FATAL_FAILURE(CheckEncodedFeatures(DSO2, /*UseCounters*/ true));
+  }
+
+  // The extra counters, value profile bits, and stack depth emit features that
+  // do not correspond to a DSO. These are associated with a hash of zero and
+  // always appear first.
+  TPC.SetUseValueProfileMask(1);
+  TPC.AddValueForMemcmp(this, DSO1.Counters, DSO2.Counters,
+                        std::min(DSO1.NumPCs, DSO2.NumPCs),
+                        /* StopAtZero */ false);
+  CollectEncodedFeatures(&Encoded);
+
+  ASSERT_GE(Encoded.size(), 4U);
+  EXPECT_EQ(Encoded[1], 0U);
+  EXPECT_EQ(Encoded[2], 0U);
+  EXPECT_EQ(Encoded[3], 1U);
 }
 
 TEST(FuzzerFork, DecodeFeatures) {
-  Vector<uint32_t> A;
+  DSORelativeValues A;
 
   // Empty input
-  EXPECT_TRUE(DecodeFeatures({}, &A));
-  TRACED_EQ(A, {});
+  EXPECT_FALSE(DecodeFeatures({}, &A));
+
+  // No DSOs
+  EXPECT_TRUE(DecodeFeatures({0}, &A));
+  EXPECT_EQ(A.size(), 0U);
 
-  // Not sorted
-  EXPECT_FALSE(DecodeFeatures({3, 2}, &A));
-  TRACED_EQ(A, {});
-
-  // Valid
-  EXPECT_TRUE(DecodeFeatures({2, 3}, &A));
-  TRACED_EQ(A, {2, 3});
+  // Incomplete DSO section
+  EXPECT_FALSE(DecodeFeatures({1}, &A));
+  EXPECT_FALSE(DecodeFeatures({1, 0xde}, &A));
+  EXPECT_FALSE(DecodeFeatures({1, 0xde, 0xad}, &A));
+
+  // DSO section length mismatch
+  EXPECT_FALSE(DecodeFeatures({1, 0xde, 0xad, 1}, &A));
+  EXPECT_FALSE(DecodeFeatures({1, 0xde, 0xad, 2, 2}, &A));
+  EXPECT_FALSE(DecodeFeatures({1, 0xde, 0xad, 1, 1, 2}, &A));
+  EXPECT_FALSE(DecodeFeatures({1, 0xde, 0xad, 2, 2, 3, 4}, &A));
+
+  // DSO section not sorted
+  EXPECT_FALSE(DecodeFeatures({1, 0xde, 0xad, 2, 3, 2}, &A));
+
+  // One valid DSO section
+  EXPECT_TRUE(DecodeFeatures({1, 0xde, 0xad, 2, 2, 3}, &A));
+  EXPECT_EQ(A.size(), 2U);
+  TRACED_EQ(A.get(0xde000000adULL), {2, 3});
+
+  // Missing DSO section
+  EXPECT_FALSE(DecodeFeatures({2, 0xde, 0xad, 2, 2, 3}, &A));
+
+  // Extra DSO section
+  EXPECT_FALSE(
+      DecodeFeatures({1, 0xde, 0xad, 2, 2, 3, 0xbe, 0xef, 3, 4, 5, 6}, &A));
 
   // Mutliple valid DSO section
-  EXPECT_TRUE(DecodeFeatures({2, 3, 4, 5, 6}, &A));
-  TRACED_EQ(A, {2, 3, 4, 5, 6});
+  EXPECT_TRUE(
+      DecodeFeatures({2, 0xde, 0xad, 2, 2, 3, 0xbe, 0xef, 3, 4, 5, 6}, &A));
+  EXPECT_EQ(A.size(), 5U);
+  TRACED_EQ(A.get(0xde000000adULL), {2, 3});
+  TRACED_EQ(A.get(0xbe000000efULL), {4, 5, 6});
 }
 
 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
+      "1\n1\nA\nBAD 0",
       "2\n1\nA\nSTARTED 0\nBAD 0 0x0",
+      "2\n1\nA\nSTARTED 0\nFT 0 BAD",
       // Bad file IDs
       "1\n1\nA\nSTARTED 1",
       "2\n1\nA\nSTARTED 0\nFT 1 0x0",
+      // Missing Hash
+      "2\n1\nA\nSTARTED 0\nFT 1\n",
+      "2\n1\nA\nSTARTED 0\nCOV 1\n",
   };
   for (auto S : kInvalidInputs) {
     SCOPED_TRACE(S);
     EXPECT_FALSE(M.Parse(S, false));
   }
 
   // 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"
+                      "FT 0 0xbeef 1 2 3\n"
                       "STARTED 1 1001\n"
-                      "FT 1 4 5 6 \n"
+                      "FT 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].Features.get(0xbeef), {1, 2, 3});
+  TRACED_EQ(M.Files[1].Features.get(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"
+                      "FT 0 0xbeef\n"
+                      "COV 0 0xbeef\n"
                       "STARTED 1 1001\n"
-                      "FT 1\n"
-                      "COV 1\n"
+                      "FT 1 0xcafe\n"
+                      "COV 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"
+                      "FT 0 0xbeef 1 2 3\n"
+                      "COV 0 0xbeef 11 12 13\n"
                       "STARTED 1 1001\n"
-                      "FT 1 4 5 6\n"
-                      "COV 1 7 8 9\n"
+                      "FT 1 0xbeef 4 5 6\n"
+                      "COV 1 0xbeef 7 8 9\n"
+                      "FT 1 0xcafe 14 15 16\n"
+                      "COV 1 0xcafe 17 18 19\n"
                       "STARTED 2 1002\n"
-                      "FT 2 6 1 3\n"
-                      "COV 2 16 11 13\n"
+                      "FT 2 0xcafe 6 1 3\n"
+                      "COV 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].Cov, {7, 8, 9});
-  TRACED_EQ(M.Files[2].Features, {1, 3, 6});
-  TRACED_EQ(M.Files[2].Cov, {16});
+  TRACED_EQ(M.Files[0].Features.get(0xbeef), {1, 2, 3});
+  TRACED_EQ(M.Files[0].Cov.get(0xbeef), {11, 12, 13});
+  TRACED_EQ(M.Files[1].Features.get(0xbeef), {4, 5, 6});
+  TRACED_EQ(M.Files[1].Features.get(0xcafe), {14, 15, 16});
+  TRACED_EQ(M.Files[1].Cov.get(0xbeef), {7, 8, 9});
+  TRACED_EQ(M.Files[1].Cov.get(0xcafe), {17, 18, 19});
+  TRACED_EQ(M.Files[2].Features.get(0xcafe), {1, 3, 6});
+  TRACED_EQ(M.Files[2].Cov.get(0xcafe), {11, 13, 16});
 }
 
 TEST(Merger, Merge) {
   Merger M;
-  Set<uint32_t> Features, NewFeatures;
-  Set<uint32_t> Cov, NewCov;
+  DSORelativeValues Features, NewFeatures;
+  DSORelativeValues Cov, NewCov;
   Vector<std::string> NewFiles;
 
   // Adds new files and features
   EXPECT_TRUE(M.Parse("3\n0\nA\nB\nC\n"
                       "STARTED 0 1000\n"
-                      "FT 0 1 2 3\n"
+                      "FT 0 0xbeef 1 2 3\n"
                       "STARTED 1 1001\n"
-                      "FT 1 4 5 6 \n"
+                      "FT 1 0xbeef 4 5 6 \n"
                       "STARTED 2 1002\n"
-                      "FT 2 6 1 3\n"
+                      "FT 2 0xbeef 6 1 3\n"
                       "",
                       true));
   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 6U);
   TRACED_EQ(M.Files, {"A", "B", "C"});
   TRACED_EQ(NewFiles, {"A", "B"});
-  TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6});
+  TRACED_EQ(NewFeatures.get(0xbeef), {1, 2, 3, 4, 5, 6});
 
   // Doesn't return features or files in the initial corpus.
   EXPECT_TRUE(M.Parse("3\n1\nA\nB\nC\n"
                       "STARTED 0 1000\n"
-                      "FT 0 1 2 3\n"
+                      "FT 0 0xbeef 1 2 3\n"
                       "STARTED 1 1001\n"
-                      "FT 1 4 5 6 \n"
+                      "FT 1 0xbeef 4 5 6 \n"
                       "STARTED 2 1002\n"
-                      "FT 2 6 1 3\n"
+                      "FT 2 0xbeef 6 1 3\n"
                       "",
                       true));
   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 3U);
   TRACED_EQ(M.Files, {"A", "B", "C"});
   TRACED_EQ(NewFiles, {"B"});
-  TRACED_EQ(NewFeatures, {4, 5, 6});
+  TRACED_EQ(NewFeatures.get(0xbeef), {4, 5, 6});
 
   // No new features, so no new files
   EXPECT_TRUE(M.Parse("3\n2\nA\nB\nC\n"
                       "STARTED 0 1000\n"
-                      "FT 0 1 2 3\n"
+                      "FT 0 0xbeef 1 2 3\n"
                       "STARTED 1 1001\n"
-                      "FT 1 4 5 6 \n"
+                      "FT 1 0xbeef 4 5 6 \n"
                       "STARTED 2 1002\n"
-                      "FT 2 6 1 3\n"
+                      "FT 2 0xbeef 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_EQ(NewFeatures.get(0xbeef), nullptr);
 
   // Can pass initial features and coverage.
-  Features = {1, 2, 3};
+  Features.Merge(0xbeef, {1, 2, 3});
   Cov = {};
   EXPECT_TRUE(M.Parse("2\n0\nA\nB\n"
                       "STARTED 0 1000\n"
-                      "FT 0 1 2 3\n"
+                      "FT 0 0xbeef 1 2 3\n"
                       "STARTED 1 1001\n"
-                      "FT 1 4 5 6\n"
+                      "FT 1 0xbeef 4 5 6\n"
                       "",
                       true));
   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 3U);
   TRACED_EQ(M.Files, {"A", "B"});
   TRACED_EQ(NewFiles, {"B"});
-  TRACED_EQ(NewFeatures, {4, 5, 6});
+  TRACED_EQ(NewFeatures.get(0xbeef), {4, 5, 6});
   Features.clear();
   Cov.clear();
 
   // Parse smaller files first
   EXPECT_TRUE(M.Parse("3\n0\nA\nB\nC\n"
                       "STARTED 0 2000\n"
-                      "FT 0 1 2 3\n"
+                      "FT 0 0xbeef 1 2 3\n"
                       "STARTED 1 1001\n"
-                      "FT 1 4 5 6 \n"
+                      "FT 1 0xbeef 4 5 6 \n"
                       "STARTED 2 1002\n"
-                      "FT 2 6 1 3 \n"
+                      "FT 2 0xbeef 6 1 3 \n"
                       "",
                       true));
   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 6U);
   TRACED_EQ(M.Files, {"B", "C", "A"});
   TRACED_EQ(NewFiles, {"B", "C", "A"});
-  TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6});
+  TRACED_EQ(NewFeatures.get(0xbeef), {1, 2, 3, 4, 5, 6});
 
   EXPECT_TRUE(M.Parse("4\n0\nA\nB\nC\nD\n"
                       "STARTED 0 2000\n"
-                      "FT 0 1 2 3\n"
+                      "FT 0 0xbeef 1 2 3\n"
                       "STARTED 1 1101\n"
-                      "FT 1 4 5 6 \n"
+                      "FT 1 0xbeef 4 5 6 \n"
                       "STARTED 2 1102\n"
-                      "FT 2 6 1 3 100 \n"
+                      "FT 2 0xbeef 6 1 3 100 \n"
                       "STARTED 3 1000\n"
-                      "FT 3 1  \n"
+                      "FT 3 0xbeef 1  \n"
                       "",
                       true));
   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 7U);
   TRACED_EQ(M.Files, {"A", "B", "C", "D"});
   TRACED_EQ(NewFiles, {"D", "B", "C", "A"});
-  TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6, 100});
+  TRACED_EQ(NewFeatures.get(0xbeef), {1, 2, 3, 4, 5, 6, 100});
 
   // For same sized file, parse more features first
   EXPECT_TRUE(M.Parse("4\n1\nA\nB\nC\nD\n"
                       "STARTED 0 2000\n"
-                      "FT 0 4 5 6 7 8\n"
+                      "FT 0 0xbeef 4 5 6 7 8\n"
                       "STARTED 1 1100\n"
-                      "FT 1 1 2 3 \n"
+                      "FT 1 0xbeef 1 2 3 \n"
                       "STARTED 2 1100\n"
-                      "FT 2 2 3 \n"
+                      "FT 2 0xbeef 2 3 \n"
                       "STARTED 3 1000\n"
-                      "FT 3 1  \n"
+                      "FT 3 0xbeef 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});
+  TRACED_EQ(NewFeatures.get(0xbeef), {1, 2, 3});
 }
 
 #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)