[sanitizer] Avoid THREADLOCAL in qsort

[vitalybuka]

Summary

With additional memory it and indirection it can be implemented
without THREADLOCAL.

Depends on D108751.

[vitalybuka]

update

[vitalybuka]

rebase

[morehouse]

What's the motivation for this change? It complicates our implementation quite a bit.

compiler-rt/lib/sanitizer_common/sanitizer_common.h

constexpr 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;
 }
 
+template <class T>
+void SwapArray(T *a, T *b, uptr size) {
+  for (uptr i = 0; i < size; ++i) Swap(a[i], b[i]);
+}
+
 // Char handling
 inline bool IsSpace(int c) {
   return (c == ' ') || (c == '\n') || (c == '\t') ||
          (c == '\f') || (c == '\r') || (c == '\v');
 }
 inline bool IsDigit(int c) {
   return (c >= '0') && (c <= '9');
 }

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

 // 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;
+struct qsort_compar_param {
+  const char *base;
+  SIZE_T size;
+  qsort_compar_f compar;
+};
+struct qsort_compar_item {
+  const qsort_compar_param *common;
+  SIZE_T from;
+  SIZE_T to;
+};
 static int wrapped_qsort_compar(const void *a, const void *b) {
+  const qsort_compar_item *param_a = (const qsort_compar_item *)a;
+  const qsort_compar_item *param_b = (const qsort_compar_item *)b;
+  DCHECK_EQ(param_a->common, param_b->common);
+  const qsort_compar_param *common = param_a->common;
   COMMON_INTERCEPTOR_UNPOISON_PARAM(2);
-  COMMON_INTERCEPTOR_INITIALIZE_RANGE(a, qsort_size);
-  COMMON_INTERCEPTOR_INITIALIZE_RANGE(b, qsort_size);
-  return qsort_compar(a, b);
+  const char *a_real = common->base + param_a->from * common->size;
+  const char *b_real = common->base + param_b->from * common->size;
+  COMMON_INTERCEPTOR_INITIALIZE_RANGE(a_real, common->size);
+  COMMON_INTERCEPTOR_INITIALIZE_RANGE(b_real, common->size);
+  return common->compar(a_real, b_real);
 }
 
 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.
   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;
-  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;
+
+  qsort_compar_param common_param = {(const char *)base, size, compar};
+  qsort_compar_item *params =
+      (qsort_compar_item *)WRAP(malloc)(nmemb * sizeof(qsort_compar_item));
+
+  for (SIZE_T i = 0; i < nmemb; ++i) params[i] = {&common_param, i, 0};
+
+  REAL(qsort)(params, nmemb, sizeof(qsort_compar_param), wrapped_qsort_compar);
+
+  // Assign new index.
+  for (SIZE_T i = 0; i < nmemb; ++i) params[i].to = i;
+
+  // Move all items back to original location to match input order.
+  for (SIZE_T i = 0; i < nmemb; ++i) {
+    while (params[i].from != i) Swap(params[i], params[params[i].from]);
   }
-  REAL(qsort)(base, nmemb, size, wrapped_qsort_compar);
-  if (!already_wrapped) {
-    qsort_compar = old_compar;
-    qsort_size = old_size;
+
+  // To the same according sorted index "to" also moving input data.
+  for (SIZE_T i = 0; i < nmemb; ++i) {
+    while (params[i].to != i) {
+      SIZE_T dst = params[i].to;
+      Swap(params[i], params[dst]);
+      char *p = (char *)base + i * size;
+      char *p_dst = (char *)base + dst * size;
+      SwapArray(p, p_dst, size);
     }
+  }
+
+  WRAP(free)(params);
+
   COMMON_INTERCEPTOR_WRITE_RANGE(ctx, base, nmemb * size);
 }
 #    define INIT_QSORT COMMON_INTERCEPT_FUNCTION(qsort)
 #  else
 #    define INIT_QSORT
 #  endif
 
 #endif  // SANITIZER_INTERCEPT_QSORT_R