From 8803ebcf3b562172687321318c423f39f22b2e5b Mon Sep 17 00:00:00 2001 From: Alex Richardson Date: Thu, 6 Aug 2020 08:53:04 +0100 Subject: [PATCH] Fix qsort() interceptor for FreeBSD 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 Reviewed By: eugenis Differential Revision: https://reviews.llvm.org/D84509 --- .../sanitizer_common_interceptors.inc | 42 ++++++++++--- .../TestCases/Posix/recursion-in-qsort.cpp | 73 ++++++++++++++++++++++ 2 files changed, 107 insertions(+), 8 deletions(-) create mode 100644 compiler-rt/test/sanitizer_common/TestCases/Posix/recursion-in-qsort.cpp diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc b/compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc index 974e89a..6fd9ddb 100644 --- a/compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc +++ b/compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc @@ -9855,12 +9855,25 @@ INTERCEPTOR(void, qsort, void *base, SIZE_T nmemb, SIZE_T size, } } qsort_compar_f old_compar = qsort_compar; - qsort_compar = compar; SIZE_T old_size = qsort_size; - qsort_size = 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); - qsort_compar = old_compar; - qsort_size = old_size; + 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) @@ -9893,12 +9906,25 @@ INTERCEPTOR(void, qsort_r, void *base, SIZE_T nmemb, SIZE_T size, } } qsort_r_compar_f old_compar = qsort_r_compar; - qsort_r_compar = compar; SIZE_T old_size = qsort_r_size; - qsort_r_size = 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); - qsort_r_compar = old_compar; - qsort_r_size = old_size; + 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) diff --git a/compiler-rt/test/sanitizer_common/TestCases/Posix/recursion-in-qsort.cpp b/compiler-rt/test/sanitizer_common/TestCases/Posix/recursion-in-qsort.cpp new file mode 100644 index 0000000..0c2b6170 --- /dev/null +++ b/compiler-rt/test/sanitizer_common/TestCases/Posix/recursion-in-qsort.cpp @@ -0,0 +1,73 @@ +// 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 +#include + +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 +} -- 2.7.4