Fix qsort() interceptor for FreeBSD

[arichardson]

Summary

When the FreeBSD qsort() implementation recurses, it does so using an
interposable function call, so we end up calling the interceptor again
and set the saved comparator to wrapped_qsort_compar. This results in an
infinite loop and a eventually a stack overflow since wrapped_qsort_compar
ends up calling itself. This means that ASAN is completely broken on
FreeBSD for programs that call qsort(). I found this while running
check-all on a FreeBSD system a ASAN-instrumented LLVM.

Fix this by checking whether we are recursing inside qsort before writing
to qsort_compar. The same bug exists in the qsort_r interceptor, so use the
same approach there. I did not test the latter since the qsort_r function
signature does not match and therefore it's not intercepted on FreeBSD/macOS.

Fixes https://llvm.org/PR46832

[eugenis]

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

9864

I think we'd still want to save/restore the size argument, in the likely case when the recursive call is passed a different value.

[arichardson]

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

9864

The size argument is the size of the elements which should not change in recursive calls. I could add an assertion/warning?

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

9864

CHECK_EQ would be nice

[eugenis]

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

9864

Yes, I misunderstood the code.
LGTM with the check.

[arichardson]

• Add CHECK()
• Add new test

[Hang]

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

9866

I think compar != qsort_compar here as compar == wrapped_sort_compar in this situation.

[arichardson]

• Fix inverted condition
• Make arrays in the test case large enough to actually trigger the recursive case

[eugenis]

LGTM

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

enum {
     CIMT_FILE
   } type;
   union {
     FileMetadata file;
   };
 };
 
 #if SI_POSIX
 typedef AddrHashMap<CommonInterceptorMetadata, 31051> MetadataHashMap;
 
 static MetadataHashMap *interceptor_metadata_map;
 
 UNUSED static void SetInterceptorMetadata(__sanitizer_FILE *addr,
                                           const FileMetadata &file) {
   MetadataHashMap::Handle h(interceptor_metadata_map, (uptr)addr);
   CHECK(h.created());
   h->type = CommonInterceptorMetadata::CIMT_FILE;
   h->file = file;
 }
 
 UNUSED static const FileMetadata *GetInterceptorMetadata(
     __sanitizer_FILE *addr) {

 
 UNUSED static void DeleteInterceptorMetadata(void *addr) {
   MetadataHashMap::Handle h(interceptor_metadata_map, (uptr)addr, true);
   CHECK(h.exists());
 }
 #endif  // SI_POSIX
 
 #if SANITIZER_INTERCEPT_STRLEN
 INTERCEPTOR(SIZE_T, strlen, const char *s) {
   // Sometimes strlen is called prior to InitializeCommonInterceptors,
   // in which case the REAL(strlen) typically used in
   // COMMON_INTERCEPTOR_ENTER will fail.  We use internal_strlen here
   // to handle that.
   if (COMMON_INTERCEPTOR_NOTHING_IS_INITIALIZED)
     return internal_strlen(s);
   void *ctx;
   COMMON_INTERCEPTOR_ENTER(ctx, strlen, s);
   SIZE_T result = REAL(strlen)(s);
   if (common_flags()->intercept_strlen)
     COMMON_INTERCEPTOR_READ_RANGE(ctx, s, result + 1);
   return result;
 }
 #define INIT_STRLEN COMMON_INTERCEPT_FUNCTION(strlen)
 #else
 #define INIT_STRLEN
 #endif
 
 #if SANITIZER_INTERCEPT_STRNLEN
 INTERCEPTOR(SIZE_T, strnlen, const char *s, SIZE_T maxlen) {
   void *ctx;
   COMMON_INTERCEPTOR_ENTER(ctx, strnlen, s, maxlen);
   SIZE_T length = REAL(strnlen)(s, maxlen);
   if (common_flags()->intercept_strlen)
     COMMON_INTERCEPTOR_READ_RANGE(ctx, s, Min(length + 1, maxlen));
   return length;
 }
 #define INIT_STRNLEN COMMON_INTERCEPT_FUNCTION(strnlen)
 #else
 #define INIT_STRNLEN
 #endif
 
 #if SANITIZER_INTERCEPT_STRNDUP
 INTERCEPTOR(char*, strndup, const char *s, uptr size) {
   void *ctx;
   COMMON_INTERCEPTOR_STRNDUP_IMPL(ctx, s, size);
 }
 #define INIT_STRNDUP COMMON_INTERCEPT_FUNCTION(strndup)
 #else
 #define INIT_STRNDUP
 #endif // SANITIZER_INTERCEPT_STRNDUP
 
if (nmemb > 1) {
     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;
+  // Handle qsort() implementations that recurse using an
+  // interposable function call:
+  bool already_wrapped = compar == wrapped_qsort_compar;
+  if (already_wrapped) {
+    // This case should only happen if the qsort() implementation calls itself
+    // using a preemptible function call (e.g. the FreeBSD libc version).
+    // Check that the size and comparator arguments are as expected.
+    CHECK_NE(compar, qsort_compar);
+    CHECK_EQ(qsort_size, size);
+  } else {
+    qsort_compar = compar;
     qsort_size = size;
+  }
   REAL(qsort)(base, nmemb, size, wrapped_qsort_compar);
+  if (!already_wrapped) {
     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
if (nmemb > 1) {
     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;
+  // Handle qsort_r() implementations that recurse using an
+  // interposable function call:
+  bool already_wrapped = compar == wrapped_qsort_r_compar;
+  if (already_wrapped) {
+    // This case should only happen if the qsort() implementation calls itself
+    // using a preemptible function call (e.g. the FreeBSD libc version).
+    // Check that the size and comparator arguments are as expected.
+    CHECK_NE(compar, qsort_r_compar);
+    CHECK_EQ(qsort_r_size, size);
+  } else {
+    qsort_r_compar = compar;
     qsort_r_size = size;
+  }
   REAL(qsort_r)(base, nmemb, size, wrapped_qsort_r_compar, arg);
+  if (!already_wrapped) {
     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
 
 #if SANITIZER_INTERCEPT_SIGALTSTACK

compiler-rt/test/sanitizer_common/TestCases/Posix/recursion-in-qsort.cpp

+// Check that a qsort() comparator that calls qsort() works as expected
+// RUN: %clangxx -O2 %s -o %t
+// RUN: %run %t 2>&1 | FileCheck %s
+
+#include <stdio.h>
+#include <stdlib.h>
+
+struct Foo {
+  int array[2];
+};
+int global_array[12] = {7, 11, 9, 10, 1, 2, 4, 3, 6, 5, 8, 12};
+
+#define array_size(x) (sizeof(x) / sizeof(x[0]))
+
+int ascending_compare_ints(const void *a, const void *b) {
+  return *(const int *)a - *(const int *)b;
+}
+
+int descending_compare_ints(const void *a, const void *b) {
+  // Add another qsort() call to check more than one level of recursion
+  qsort(global_array, array_size(global_array), sizeof(int), &ascending_compare_ints);
+  return *(const int *)b - *(const int *)a;
+}
+
+int sort_and_compare(const void *a, const void *b) {
+  struct Foo *f1 = (struct Foo *)a;
+  struct Foo *f2 = (struct Foo *)b;
+  printf("sort_and_compare({%d, %d}, {%d, %d})\n", f1->array[0], f1->array[1],
+         f2->array[0], f2->array[1]);
+  // Call qsort from within qsort() to check that interceptors handle this case:
+  qsort(&f1->array, array_size(f1->array), sizeof(int), &descending_compare_ints);
+  qsort(&f2->array, array_size(f2->array), sizeof(int), &descending_compare_ints);
+  // Sort by second array element:
+  return f1->array[1] - f2->array[1];
+}
+
+int main() {
+  // Note: 16 elements should be large enough to trigger a recursive qsort() call.
+  struct Foo qsortArg[16] = {
+      {1, 99},
+      {2, 3},
+      {17, 5},
+      {8, 6},
+      {11, 4},
+      {3, 3},
+      {16, 17},
+      {7, 9},
+      {21, 12},
+      {32, 23},
+      {13, 8},
+      {99, 98},
+      {41, 42},
+      {42, 43},
+      {44, 45},
+      {0, 1},
+  };
+  // Sort the individual arrays in descending order and the over all struct
+  // Foo array in ascending order of the second array element.
+  qsort(qsortArg, array_size(qsortArg), sizeof(qsortArg[0]), &sort_and_compare);
+
+  printf("Sorted result:");
+  for (const auto &f : qsortArg) {
+    printf(" {%d,%d}", f.array[0], f.array[1]);
+  }
+  printf("\n");
+  // CHECK: Sorted result: {1,0} {99,1} {3,2} {3,3} {11,4} {17,5} {8,6} {9,7} {13,8} {21,12} {17,16} {32,23} {42,41} {43,42} {45,44} {99,98}
+  printf("Sorted global_array:");
+  for (int i : global_array) {
+    printf(" %d", i);
+  }
+  printf("\n");
+  // CHECK: Sorted global_array: 1 2 3 4 5 6 7 8 9 10 11 12
+}