[Sanitizer] implement straightforward nlogn sorting, as qsort() may call malloc, which leads to deadlock in ASan allocator

llvm-svn: 160262

3 files changed, 111 insertions, 14 deletions

diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_common.cc b/compiler-rt/lib/sanitizer_common/sanitizer_common.cc
index b3e16b43bf5..6dd1ff91726 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_common.cc
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_common.cc
@@ -13,7 +13,6 @@
 
 #include "sanitizer_common.h"
 #include "sanitizer_libc.h"
-#include <stdlib.h>
 
 namespace __sanitizer {
 
@@ -57,19 +56,45 @@ uptr ReadFileToBuffer(const char *file_name, char **buff,
   return read_len;
 }
 
-static int comp(const void *p1, const void *p2) {
-  uptr v1 = *(uptr*)p1;
-  uptr v2 = *(uptr*)p2;
-  if (v1 < v2)
-    return -1;
-  else if (v1 > v2)
-    return 1;
-  else
-    return 0;
-}
-
+// We don't want to use std::sort to avoid including <algorithm>, as
+// we may end up with two implementation of std::sort - one in instrumented
+// code, and the other in runtime.
+// qsort() from stdlib won't work as it calls malloc(), which results
+// in deadlock in ASan allocator.
+// We re-implement in-place sorting w/o recursion as straightforward heapsort.
 void SortArray(uptr *array, uptr size) {
-  qsort(array, size, sizeof(array[0]), &comp);
+  if (size < 2)
+    return;
+  // Stage 1: insert elements to the heap.
+  for (uptr i = 1; i < size; i++) {
+    uptr j, p;
+    for (j = i; j > 0; j = p) {
+      p = (j - 1) / 2;
+      if (array[j] > array[p])
+        Swap(array[j], array[p]);
+      else
+        break;
+    }
+  }
+  // Stage 2: swap largest element with the last one,
+  // and sink the new top.
+  for (uptr i = size - 1; i > 0; i--) {
+    Swap(array[0], array[i]);
+    uptr j, max_ind;
+    for (j = 0; j < i; j = max_ind) {
+      uptr left = 2 * j + 1;
+      uptr right = 2 * j + 2;
+      max_ind = j;
+      if (left < i && array[left] > array[max_ind])
+        max_ind = left;
+      if (right < i && array[right] > array[max_ind])
+        max_ind = right;
+      if (max_ind != j)
+        Swap(array[j], array[max_ind]);
+      else
+        break;
+    }
+  }
 }
 
 }  // namespace __sanitizer
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_common.h b/compiler-rt/lib/sanitizer_common/sanitizer_common.h
index a6a40cb1672..4c7c1e9d86e 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_common.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_common.h
@@ -90,9 +90,15 @@ INLINE uptr RoundUpTo(uptr size, uptr boundary) {
   CHECK(IsPowerOfTwo(boundary));
   return (size + boundary - 1) & ~(boundary - 1);
 }
-// Don't use std::min and std::max, to minimize dependency on libstdc++.
+// Don't use std::min, std::max or std::swap, to minimize dependency
+// on libstdc++.
 template<class T> T Min(T a, T b) { return a < b ? a : b; }
 template<class T> T Max(T a, T b) { return a > b ? a : b; }
+template<class T> void Swap(T& a, T& b) {
+  T tmp = a;
+  a = b;
+  b = tmp;
+}
 
 // Char handling
 INLINE bool IsSpace(int c) {
diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_common_test.cc b/compiler-rt/lib/sanitizer_common/tests/sanitizer_common_test.cc
new file mode 100644
index 00000000000..91570dcc99e
--- /dev/null
+++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_common_test.cc
@@ -0,0 +1,66 @@
+//===-- sanitizer_common_test.cc ------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of ThreadSanitizer/AddressSanitizer runtime.
+//
+//===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_common.h"
+#include "gtest/gtest.h"
+
+namespace __sanitizer {
+
+static bool IsSorted(const uptr *array, uptr n) {
+  for (uptr i = 1; i < n; i++) {
+    if (array[i] < array[i - 1]) return false;
+  }
+  return true;
+}
+
+TEST(SanitizerCommon, SortTest) {
+  uptr array[100];
+  uptr n = 100;
+  // Already sorted.
+  for (uptr i = 0; i < n; i++) {
+    array[i] = i;
+  }
+  SortArray(array, n);
+  EXPECT_TRUE(IsSorted(array, n));
+  // Reverse order.
+  for (uptr i = 0; i < n; i++) {
+    array[i] = n - 1 - i;
+  }
+  SortArray(array, n);
+  EXPECT_TRUE(IsSorted(array, n));
+  // Mixed order.
+  for (uptr i = 0; i < n; i++) {
+    array[i] = (i % 2 == 0) ? i : n - 1 - i;
+  }
+  SortArray(array, n);
+  EXPECT_TRUE(IsSorted(array, n));
+  // All equal.
+  for (uptr i = 0; i < n; i++) {
+    array[i] = 42;
+  }
+  SortArray(array, n);
+  EXPECT_TRUE(IsSorted(array, n));
+  // All but one sorted.
+  for (uptr i = 0; i < n - 1; i++) {
+    array[i] = i;
+  }
+  array[n - 1] = 42;
+  SortArray(array, n);
+  EXPECT_TRUE(IsSorted(array, n));
+  // Minimal case - sort three elements.
+  array[0] = 1;
+  array[1] = 0;
+  SortArray(array, 2);
+  EXPECT_TRUE(IsSorted(array, 2));
+}
+
+}  // namespace sanitizer