[msan] Check qsort input.

[eugenis]

Summary

Qsort interceptor suppresses all checks by unpoisoning the data in the
wrapper of a comparator function, and then unpoisoning the output array
as well.

This change adds an explicit run of the comparator on all elements of
the input array to catch any sanitizer bugs.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

[vitalybuka]

nice

[eugenis]

This change actually broke llvm bootstrap and had to be reverted.
A stateful comparator? Investigating...

[eugenis]

CompareOptionRecords checks that there are no duplicate options in the sorting comparator function.
I believe this is wrong, because I could not find a promise in POSIX nor in linux manpages that the comparator would never be called with the same object on both left and right hand side.

Nevertheless, I don't want sanitizers to enforce this peculiarity in the standard.

[eugenis]

avoid comparing an element to itself

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

9678

maybe just:

compar(p, q);
compar(q, p);

[eugenis]

removed the (i % 2) thing. Comparators should not be sensitive to the argument order.

[eugenis]

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

9678

A sensible comparator should do the same work no matter what the order of arguments is. Just compar(p, q) should suffice.

[merge_guards_bot]

Unit tests: pass. 61127 tests passed, 0 failed and 728 were skipped.

clang-tidy: pass.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[merge_guards_bot]

Unit tests: pass. 61127 tests passed, 0 failed and 728 were skipped.

clang-tidy: pass.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[eugenis]

ping

[vitalybuka]

what is about clang-format?

[eugenis]

In D71780#1806823, @vitalybuka wrote:

what is about clang-format?

it's nonsense

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

int wrapped_qsort_compar(const void *a, const void *b) {
   COMMON_INTERCEPTOR_INITIALIZE_RANGE(b, qsort_size);
   return qsort_compar(a, b);
 }
 
 INTERCEPTOR(void, qsort, void *base, SIZE_T nmemb, SIZE_T size,
             qsort_compar_f compar) {
   void *ctx;
   COMMON_INTERCEPTOR_ENTER(ctx, qsort, base, nmemb, size, compar);
+  // Run the comparator over all array elements to detect any memory issues.
+  for (SIZE_T i = 0; i < nmemb - 1; ++i) {
+    void *p = (void *)((char *)base + i * size);
+    void *q = (void *)((char *)base + (i + 1) * size);
+    COMMON_INTERCEPTOR_UNPOISON_PARAM(2);
+    compar(p, q);
+  }
   qsort_compar_f old_compar = qsort_compar;
   qsort_compar = compar;
   SIZE_T old_size = qsort_size;
   qsort_size = size;
   REAL(qsort)(base, nmemb, size, wrapped_qsort_compar);
   qsort_compar = old_compar;
   qsort_size = old_size;
   COMMON_INTERCEPTOR_WRITE_RANGE(ctx, base, nmemb * size);
int wrapped_qsort_r_compar(const void *a, const void *b, void *arg) {
   COMMON_INTERCEPTOR_INITIALIZE_RANGE(b, qsort_r_size);
   return qsort_r_compar(a, b, arg);
 }
 
 INTERCEPTOR(void, qsort_r, void *base, SIZE_T nmemb, SIZE_T size,
             qsort_r_compar_f compar, void *arg) {
   void *ctx;
   COMMON_INTERCEPTOR_ENTER(ctx, qsort_r, base, nmemb, size, compar, arg);
+  // Run the comparator over all array elements to detect any memory issues.
+  for (SIZE_T i = 0; i < nmemb - 1; ++i) {
+    void *p = (void *)((char *)base + i * size);
+    void *q = (void *)((char *)base + (i + 1) * size);
+    COMMON_INTERCEPTOR_UNPOISON_PARAM(3);
+    compar(p, q, arg);
+  }
   qsort_r_compar_f old_compar = qsort_r_compar;
   qsort_r_compar = compar;
   SIZE_T old_size = qsort_r_size;
   qsort_r_size = size;
   REAL(qsort_r)(base, nmemb, size, wrapped_qsort_r_compar, arg);
   qsort_r_compar = old_compar;
   qsort_r_size = old_size;
   COMMON_INTERCEPTOR_WRITE_RANGE(ctx, base, nmemb * size);

compiler-rt/test/msan/qsort.cpp

 // RUN: %clangxx_msan -O0 -g %s -o %t && %run %t
+// RUN: %clangxx_msan -DPOISON -O0 -g %s -o %t && not %run %t 2>&1 | FileCheck %s
 
 #include <assert.h>
 #include <errno.h>
 #include <glob.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 

 }
 
 int main(int argc, char *argv[]) {
   long *p = new long[kSize1];
   // kind of random
   for (int i = 0; i < kSize1; ++i)
     p[i] = i * 2 + (i % 3 - 1) * 3;
   poison_stack_and_param();
+#ifdef POISON
+  __msan_poison(p + 1, sizeof(long));
+  // CHECK: Uninitialized bytes in __msan_check_mem_is_initialized at offset 0 inside [{{.*}}, 8)
+#endif
   qsort(p, kSize1, sizeof(long), compar1);
   __msan_check_mem_is_initialized(p, sizeof(long) * kSize1);
   assert(seen2);
   delete[] p;
   return 0;
 }