[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

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
 

 // 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 *data;
+  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->data + param_a->from * common->size;
+  const char *b_real = common->data + 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);
+
+  char *data = (char *)base;
   // 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);
+      char *p = data + i * size;
       COMMON_INTERCEPTOR_UNPOISON_PARAM(2);
-      compar(p, q);
+      compar(p, p + size);
     }
   }
-  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 = {data, 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(params[0]), 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]);
+  }
+
+  // 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]);
+      SwapArray(data + i * size, data + dst * size, size);
     }
-  REAL(qsort)(base, nmemb, size, wrapped_qsort_compar);
-  if (!already_wrapped) {
-    qsort_compar = old_compar;
-    qsort_size = old_size;
   }
+
+  WRAP(free)(params);
+
   COMMON_INTERCEPTOR_WRITE_RANGE(ctx, base, nmemb * size);
 }
 #  define INIT_QSORT COMMON_INTERCEPT_FUNCTION(qsort)
 #else
 #  define INIT_QSORT
 #endif
 
 #if SANITIZER_INTERCEPT_BSEARCH