[msan] Intercept qsort, qsort_r.

[eugenis]

Summary

This fixes qsort-related false positives with glibc-2.27.
I'm not entirely sure why they did not show up with the earlier
versions; the code seems similar enough.

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

9686

you can wrap <qsort_r_size, qsort_r_compar, arg> and pass as arg

[merge_guards_bot]

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

clang-tidy: fail. Please fix clang-tidy findings.

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]

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

9686

Yes, but I can not do the same in qsort(). I kind of prefer the two interceptors to do the same thing to avoid introducing new, unique bugs in qsort_r, but I don't have a strong feeling about it.

I could not use qsort_r to implement the interceptor for qsort, because it does not exist on the same set of platforms.

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

9659

do we need COMMON_INTERCEPTOR_READ_RANGE(ctx, src, size); for a and b?
or we going to assume that compar is instrumented?

9661

Problem here that if array has uninitialized fields they are going to be unpoisoned by compar
maybe before calling actual qsort we can call
compar(base[0], base[1])
compar(base[1], base[2])
compar(base[3], base[4])
...
just to trigger report of a bug is there?

9686

this way you can't call qsort from qsort_compar recursively :)

[vitalybuka]

compiler-rt/test/msan/qsort.cpp

4

looks like we need .clang-tidy

[eugenis]

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

9659

compar is typically instrumented.
We don't want to check the shadow here. We want to clear it.

9661

This is a great idea. Ill run compar(x, x) for each node to trigger a check for equality which usually needs to exercise as much of the comparison logic as possible.

But I think I'll do it in a separate change for easier bisection and reverting in case something goes wrong somewhere.

9686

I can. See old_compar and old_size.

compiler-rt/test/msan/qsort.cpp

4

yeah... not in this change

[eugenis]

addressed comments

[krytarowski]

If possible, it would be nice to follow up with heapsort(3) and mergesort(3).

[merge_guards_bot]

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

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

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

[eugenis]

In D71740#1793281, @krytarowski wrote:

If possible, it would be nice to follow up with heapsort(3) and mergesort(3).

Would be nice, but on gnu/linux these functions are in libbsd.so; if we provide an interceptor then we must link the implementation as well to not confuse configure-style checks. This would make all sanitized binaries on linux link libbsd.so even if they don't use it... I'm not sure that's OK.

[JDevlieghere]

I've reverted this commit because our bots have been broken since this landed. Can you please keep an eye on these bots when you re-land this? Thanks!

Revert "[msan] Check qsort input." and "[msan] Intercept qsort, qsort_r."

Temporarily revert the qsort changes because they fail to build on bots
that build with modules:

error: thread-local storage is not supported for the current
target (iossim)

http://green.lab.llvm.org/green/job/clang-stage2-Rthinlto/1820/console
http://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/4983/console

This reverts commit ddf897fc80499ece298bc33201db6b697d2af50e.
This reverts commit 07861e955d0095f25639d84c5726c73b528567cb.

[eugenis]

Sorry about that! I have not received a mail notification about this - apparently, there was another build break at the same time.
I'll disable the new interceptors on ios and reland the changes.

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

INTERCEPTOR(int, getentropy, void *buf, SIZE_T buflen) {
   }
   return r;
 }
 #define INIT_GETENTROPY COMMON_INTERCEPT_FUNCTION(getentropy)
 #else
 #define INIT_GETENTROPY
 #endif
 
+#if SANITIZER_INTERCEPT_QSORT
+// Glibc qsort uses a temporary buffer allocated either on stack or on heap.
+// Poisoned memory from there may get copied into the comparator arguments,
+// where it needs to be dealt with. But even that is not enough - the results of
+// the sort may be copied into the input/output array based on the results of
+// the comparator calls, but directly from the temp memory, bypassing the
+// unpoisoning done in wrapped_qsort_compar. We deal with this by, again,
+// unpoisoning the entire array after the sort is done.
+//
+// We can not check that the entire array is initialized at the beginning. IMHO,
+// it's fine for parts of the sorted objects to contain uninitialized memory,
+// ex. as padding in structs.
+typedef int (*qsort_compar_f)(const void *, const void *);
+static THREADLOCAL qsort_compar_f qsort_compar;
+static THREADLOCAL SIZE_T qsort_size;
+int wrapped_qsort_compar(const void *a, const void *b) {
+  COMMON_INTERCEPTOR_UNPOISON_PARAM(2);
+  COMMON_INTERCEPTOR_INITIALIZE_RANGE(a, qsort_size);
+  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);
+  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);
+}
+#define INIT_QSORT COMMON_INTERCEPT_FUNCTION(qsort)
+#else
+#define INIT_QSORT
+#endif
+
+#if SANITIZER_INTERCEPT_QSORT_R
+typedef int (*qsort_r_compar_f)(const void *, const void *, void *);
+static THREADLOCAL qsort_r_compar_f qsort_r_compar;
+static THREADLOCAL SIZE_T qsort_r_size;
+int wrapped_qsort_r_compar(const void *a, const void *b, void *arg) {
+  COMMON_INTERCEPTOR_UNPOISON_PARAM(3);
+  COMMON_INTERCEPTOR_INITIALIZE_RANGE(a, qsort_r_size);
+  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);
+  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);
+}
+#define INIT_QSORT_R COMMON_INTERCEPT_FUNCTION(qsort_r)
+#else
+#define INIT_QSORT_R
+#endif
+
 static void InitializeCommonInterceptors() {
 #if SI_POSIX
   static u64 metadata_mem[sizeof(MetadataHashMap) / sizeof(u64) + 1];
   interceptor_metadata_map = new ((void *)&metadata_mem) MetadataHashMap();
 #endif
 
   INIT_MMAP;
   INIT_MMAP64;
#endif
   INIT_FUNOPEN2;
   INIT_FDEVNAME;
   INIT_GETUSERSHELL;
   INIT_SL_INIT;
   INIT_GETRANDOM;
   INIT_CRYPT;
   INIT_CRYPT_R;
   INIT_GETENTROPY;
+  INIT_QSORT;
+  INIT_QSORT_R;
 
   INIT___PRINTF_CHK;
 }

compiler-rt/lib/sanitizer_common/sanitizer_platform_interceptors.h

 #define SANITIZER_INTERCEPT_CRYPT_R (SI_LINUX && !SI_ANDROID)
 
 #define SANITIZER_INTERCEPT_GETRANDOM \
   ((SI_LINUX && __GLIBC_PREREQ(2, 25)) || SI_FREEBSD)
 #define SANITIZER_INTERCEPT___CXA_ATEXIT SI_NETBSD
 #define SANITIZER_INTERCEPT_ATEXIT SI_NETBSD
 #define SANITIZER_INTERCEPT_PTHREAD_ATFORK SI_NETBSD
 #define SANITIZER_INTERCEPT_GETENTROPY SI_FREEBSD
+#define SANITIZER_INTERCEPT_QSORT SI_POSIX
+#define SANITIZER_INTERCEPT_QSORT_R (SI_LINUX && !SI_ANDROID)
 
 #endif  // #ifndef SANITIZER_PLATFORM_INTERCEPTORS_H

compiler-rt/test/msan/qsort.cpp

+// RUN: %clangxx_msan -O0 -g %s -o %t && %run %t
+
+#include <assert.h>
+#include <errno.h>
+#include <glob.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <sanitizer/msan_interface.h>
+
+constexpr size_t kSize1 = 27;
+constexpr size_t kSize2 = 7;
+
+bool seen2;
+
+void dummy(long a, long b, long c, long d, long e) {}
+
+void poison_stack_and_param() {
+  char x[10000];
+  int y;
+  dummy(y, y, y, y, y);
+}
+
+__attribute__((always_inline)) int cmp(long a, long b) {
+  if (a < b)
+    return -1;
+  else if (a > b)
+    return 1;
+  else
+    return 0;
+}
+
+int compar2(const void *a, const void *b) {
+  assert(a);
+  assert(b);
+  __msan_check_mem_is_initialized(a, sizeof(long));
+  __msan_check_mem_is_initialized(b, sizeof(long));
+  seen2 = true;
+  poison_stack_and_param();
+  return cmp(*(long *)a, *(long *)b);
+}
+
+int compar1(const void *a, const void *b) {
+  assert(a);
+  assert(b);
+  __msan_check_mem_is_initialized(a, sizeof(long));
+  __msan_check_mem_is_initialized(b, sizeof(long));
+
+  long *p = new long[kSize2];
+  // kind of random
+  for (int i = 0; i < kSize2; ++i)
+    p[i] = i * 2 + (i % 3 - 1) * 3;
+  qsort(p, kSize1, sizeof(long), compar2);
+  __msan_check_mem_is_initialized(p, sizeof(long) * kSize2);
+  delete[] p;
+
+  poison_stack_and_param();
+  return cmp(*(long *)a, *(long *)b);
+}
+
+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();
+  qsort(p, kSize1, sizeof(long), compar1);
+  __msan_check_mem_is_initialized(p, sizeof(long) * kSize1);
+  assert(seen2);
+  delete[] p;
+  return 0;
+}