[compiler-rt] Change std::sort to llvm::sort in response to r327219

[mgrang]

Summary

r327219 added wrappers to std::sort which randomly shuffle the container before sorting.
This will help in uncovering non-determinism caused due to undefined sorting
order of objects having the same key.

To make use of that infrastructure we need to invoke llvm::sort instead of std::sort.

[mgrang]

Fixed indentation.

[RKSimon]

Please regenerate the diffs with context

[mgrang]

Reproduced patch with more context.

[RKSimon]

lib/asan/tests/asan_mem_test.cc

85

Is there any point to checking integer type sorts like this and some of the others in this patch?

[efriedma]

lib/asan/tests/asan_mem_test.cc

85

"<" for integers forms a strict weak ordering, so yes, it'll always return the same result... but it's simpler to just uniformly use llvm::sort everywhere, rather than forcing developers to consider for each call to sort() whether the element type has a user-defined "operator<".

[mgrang]

I agree with @efriedma on this. It's better to uniformly use llvm::sort rather than assuming that developers will always use the "correct" sort.

[RKSimon]

In D44360#1041020, @mgrang wrote:

I agree with @efriedma on this. It's better to uniformly use llvm::sort rather than assuming that developers will always use the "correct" sort.

Thanks, just wanted to make sure - LGTM.

[george.karpenkov]

@kcc @mgrang I'm almost certain this needs to be rolled back: it is breaking the build, and libFuzzer by design can not have LLVM dependencies.

[eugenis]

Definitely. Compiler-rt can be built standalone, outside of llvm source tree.
Please revert.

[mgrang]

In D44360#1042749, @eugenis wrote:

Definitely. Compiler-rt can be built standalone, outside of llvm source tree.
Please revert.

Thanks! r327936 reverts the patch.

[kcc]

Also: this change has been committed w/o an approval from any of the
owners.
please try to avoid this in future.

--kcc

[mgrang]

In D44360#1042816, @kcc wrote:

Also: this change has been committed w/o an approval from any of the
owners.
please try to avoid this in future.

--kcc

Sure. I would keep that in mind. Thanks!

Also, since compiler-rt can be built outside of the llvm tree, I guess we cannot depend on the invocation of llvm::sort. So I guess compiler-rt cannot use the "shuffle before sort" infrastructure of llvm? Could you please comment on whether this is correct? Is there any way we can use llvm::sort for compiler-rt?

[mgrang]

Need to abandon this since compiler-rt cannot depend on llvm includes.

lib/asan/tests/asan_mem_test.cc

 // Strictly speaking we are not guaranteed to find such two pointers,
 // but given the structure of asan's allocator we will.
 static bool AllocateTwoAdjacentArrays(char **x1, char **x2, size_t size) {
   std::vector<uintptr_t> v;
   bool res = false;
   for (size_t i = 0; i < 1000U && !res; i++) {
     v.push_back(reinterpret_cast<uintptr_t>(new char[size]));
     if (i == 0) continue;
-    sort(v.begin(), v.end());
+    llvm::sort(v.begin(), v.end());
     for (size_t j = 1; j < v.size(); j++) {
       assert(v[j] > v[j-1]);
       if ((size_t)(v[j] - v[j-1]) < size * 2) {
         *x2 = reinterpret_cast<char*>(v[j]);
         *x1 = reinterpret_cast<char*>(v[j-1]);
         res = true;
         break;
       }

lib/fuzzer/FuzzerCorpus.h

void AddToCorpus(const Unit &U, size_t NumFeatures, bool MayDeleteFile,
     if (FeatureDebug)
       Printf("ADD_TO_CORPUS %zd NF %zd\n", Inputs.size(), NumFeatures);
     Inputs.push_back(new InputInfo());
     InputInfo &II = *Inputs.back();
     II.U = U;
     II.NumFeatures = NumFeatures;
     II.MayDeleteFile = MayDeleteFile;
     II.UniqFeatureSet = FeatureSet;
-    std::sort(II.UniqFeatureSet.begin(), II.UniqFeatureSet.end());
+    llvm::sort(II.UniqFeatureSet.begin(), II.UniqFeatureSet.end());
     ComputeSHA1(U.data(), U.size(), II.Sha1);
     Hashes.insert(Sha1ToString(II.Sha1));
     UpdateCorpusDistribution();
     PrintCorpus();
     // ValidateFeatureSet();
   }
 
   // Debug-only

lib/fuzzer/FuzzerMerge.cpp

if (Marker == "STARTED") {
       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 >> std::hex >> N)
           TmpFeatures.push_back(N);
-        std::sort(TmpFeatures.begin(), TmpFeatures.end());
+        llvm::sort(TmpFeatures.begin(), TmpFeatures.end());
         Files[CurrentFileIdx].Features = TmpFeatures;
       }
     } else {
       return false;
     }
   }
   if (LastSeenStartMarker != kInvalidStartMarker)
     LastFailure = Files[LastSeenStartMarker].Name;
for (size_t i = NumFilesInFirstCorpus; i < Files.size(); i++) {
     std::set_difference(Cur.begin(), Cur.end(), AllFeatures.begin(),
                         AllFeatures.end(), std::inserter(Tmp, Tmp.begin()));
     Cur.swap(Tmp);
   }
 
   // Sort. Give preference to
   //   * smaller files
   //   * files with more features.
-  std::sort(Files.begin() + NumFilesInFirstCorpus, Files.end(),
+  llvm::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());
     size_t OldSize = AllFeatures.size();
if (MergeControlFilePathOrNull && FileSize(MergeControlFilePathOrNull)) {
     }
   }
 
   if (!NumAttempts) {
     // The supplied control file is empty or bad, create a fresh one.
     Vector<SizedFile> AllFiles;
     GetSizedFilesFromDir(Corpora[0], &AllFiles);
     size_t NumFilesInFirstCorpus = AllFiles.size();
-    std::sort(AllFiles.begin(), AllFiles.end());
+    llvm::sort(AllFiles.begin(), AllFiles.end());
     for (size_t i = 1; i < Corpora.size(); i++)
       GetSizedFilesFromDir(Corpora[i], &AllFiles);
-    std::sort(AllFiles.begin() + NumFilesInFirstCorpus, AllFiles.end());
+    llvm::sort(AllFiles.begin() + NumFilesInFirstCorpus, AllFiles.end());
     Printf("MERGE-OUTER: %zd files, %zd in the initial corpus\n",
            AllFiles.size(), NumFilesInFirstCorpus);
     WriteNewControlFile(CFPath, AllFiles, NumFilesInFirstCorpus);
     NumAttempts = AllFiles.size();
   }
 
   // Execute the inner process until it passes.
   // Every inner process should execute at least one input.

lib/sanitizer_common/tests/sanitizer_common_test.cc

auto create_item = [] (size_t i, size_t j) {
     return ((v << 6) + (v >> 6) + 0x9e3779b9) % 100;
   };
   for (size_t i = 0; i < 1000; ++i) {
     data.resize(i);
     for (size_t j = 0; j < i; ++j) {
       data[j] = create_item(i, j);
     }
 
-    std::sort(data.begin(), data.end());
+    llvm::sort(data.begin(), data.end());
 
     for (size_t j = 0; j < i; ++j) {
       int val = create_item(i, j);
       for (auto to_find : {val - 1, val, val + 1}) {
         uptr expected =
             std::lower_bound(data.begin(), data.end(), to_find) - data.begin();
         EXPECT_EQ(expected, InternalLowerBound(data.data(), 0, data.size(),
                                                to_find, std::less<int>()));

lib/sanitizer_common/tests/sanitizer_linux_test.cc

static std::vector<pid_t> ReadTidsToVector(ThreadLister *thread_lister) {
   pid_t tid;
   while ((tid = thread_lister->GetNextTID()) >= 0)
     listed_tids.push_back(tid);
   EXPECT_FALSE(thread_lister->error());
   return listed_tids;
 }
 
 static bool Includes(std::vector<pid_t> first, std::vector<pid_t> second) {
-  std::sort(first.begin(), first.end());
-  std::sort(second.begin(), second.end());
+  llvm::sort(first.begin(), first.end());
+  llvm::sort(second.begin(), second.end());
   return std::includes(first.begin(), first.end(),
                        second.begin(), second.end());
 }
 
 static bool HasElement(std::vector<pid_t> vector, pid_t element) {
   return std::find(vector.begin(), vector.end(), element) != vector.end();
 }