[msan] Add bsearch interceptor

[vitalybuka]

Summary

Similar to qsort, bsearch can be called from non-instrumented
code of glibc. When it happends tls for arguments can be in uninitialized
state.

Unlike to qsort, bsearch does not move data, so we don't need to
check or initialize searched memory or key. Intrumented comparator will
do that on it's own.

[vitalybuka]

fix name

[vitalybuka]

clang-format and remove lambda

[morehouse]

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

10047

[vitalybuka]

qsort -> bsearch

[morehouse]

LGTM

compiler-rt/lib/sanitizer_common/sanitizer_common_interceptors.inc

INTERCEPTOR(void, qsort_r, void *base, SIZE_T nmemb, SIZE_T 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_BSEARCH
+typedef int (*bsearch_compar_f)(const void *, const void *);
+static THREADLOCAL bsearch_compar_f bsearch_compar;
+static int wrapped_bsearch_compar(const void *a, const void *b) {
+  COMMON_INTERCEPTOR_UNPOISON_PARAM(2);
+  return bsearch_compar(a, b);
+}
+
+INTERCEPTOR(void *, bsearch, const void *key, const void *base, SIZE_T nmemb,
+            SIZE_T size, bsearch_compar_f compar) {
+  void *ctx;
+  COMMON_INTERCEPTOR_ENTER(ctx, bsearch, key, base, nmemb, size, compar);
+  // Unlike qsort, don't expect recursive implementation of bsearch.
+  CHECK_NE(compar, wrapped_bsearch_compar);
+  Swap(bsearch_compar, compar);
+  void *r = REAL(bsearch)(key, base, nmemb, size, wrapped_bsearch_compar);
+  bsearch_compar = compar;
+  return r;
+}
+#  define INIT_BSEARCH COMMON_INTERCEPT_FUNCTION(bsearch)
+#else
+#  define INIT_BSEARCH
+#endif
+
 #if SANITIZER_INTERCEPT_SIGALTSTACK
 INTERCEPTOR(int, sigaltstack, void *ss, void *oss) {
   void *ctx;
   COMMON_INTERCEPTOR_ENTER(ctx, sigaltstack, ss, oss);
   int r = REAL(sigaltstack)(ss, oss);
   if (r == 0 && oss != nullptr) {
     COMMON_INTERCEPTOR_WRITE_RANGE(ctx, oss, struct_stack_t_sz);
   }
#endif
   INIT_GETUSERSHELL;
   INIT_SL_INIT;
   INIT_GETRANDOM;
   INIT_CRYPT;
   INIT_CRYPT_R;
   INIT_GETENTROPY;
   INIT_QSORT;
   INIT_QSORT_R;
+  INIT_BSEARCH;
   INIT_SIGALTSTACK;
   INIT_UNAME;
   INIT___XUNAME;
 
   INIT___PRINTF_CHK;
 }

compiler-rt/lib/sanitizer_common/sanitizer_platform_interceptors.h

#define SANITIZER_INTERCEPT_GETRANDOM \
   ((SI_LINUX && __GLIBC_PREREQ(2, 25)) || SI_FREEBSD)
 #define SANITIZER_INTERCEPT___CXA_ATEXIT SI_NETBSD
 #define SANITIZER_INTERCEPT_ATEXIT SI_NETBSD
 #define SANITIZER_INTERCEPT_PTHREAD_ATFORK SI_NETBSD
 #define SANITIZER_INTERCEPT_GETENTROPY SI_FREEBSD
 #define SANITIZER_INTERCEPT_QSORT \
   (SI_POSIX && !SI_IOSSIM && !SI_WATCHOS && !SI_TVOS && !SI_ANDROID)
 #define SANITIZER_INTERCEPT_QSORT_R SI_GLIBC
+#define SANITIZER_INTERCEPT_BSEARCH \
+  (SI_POSIX && !SI_IOSSIM && !SI_WATCHOS && !SI_TVOS && !SI_ANDROID)
 // sigaltstack on i386 macOS cannot be intercepted due to setjmp()
 // calling it and assuming that it does not clobber registers.
 #define SANITIZER_INTERCEPT_SIGALTSTACK \
   (SI_POSIX && !(SANITIZER_MAC && SANITIZER_I386))
 #define SANITIZER_INTERCEPT_UNAME (SI_POSIX && !SI_FREEBSD)
 #define SANITIZER_INTERCEPT___XUNAME SI_FREEBSD
 #define SANITIZER_INTERCEPT_FLOPEN SI_FREEBSD
 

compiler-rt/test/msan/bsearch.cpp

+// __NO_INLINE__ is defined so bsearch needs interceptor.
+// RUN: %clangxx_msan -O0 -g %s -o %t && %run %t
+// RUN: %clangxx_msan -DPOISON_DATA -O0 -g %s -o %t && not %run %t 2>&1 | FileCheck %s
+// RUN: %clangxx_msan -DPOISON_KEY -O0 -g %s -o %t && not %run %t 2>&1 | FileCheck %s
+
+// __NO_INLINE__ is undefined so bsearch should be inlined and instrumented and still work as expected.
+// RUN: %clangxx_msan -O2 -g %s -o %t && %run %t
+// RUN: %clangxx_msan -DPOISON_DATA -O2 -g %s -o %t && not %run %t 2>&1 | FileCheck %s
+// RUN: %clangxx_msan -DPOISON_KEY -O2 -g %s -o %t && not %run %t 2>&1 | FileCheck %s
+
+#include <assert.h>
+#include <stdlib.h>
+
+#include <sanitizer/msan_interface.h>
+
+long z;
+
+__attribute__((noinline, optnone)) void
+poison_msan_param_tls(long a, long b, long c, long d, long e, long f) {
+  z = a + b + c + d + e + f;
+}
+
+static int compar(const void *a, const void *b) {
+  int r = *(const long *)a - *(const long *)b;
+  long x;
+  __msan_poison(&x, sizeof(x));
+  poison_msan_param_tls(x, x, x, x, x, x);
+  return r;
+}
+
+int main(int argc, char *argv[]) {
+  constexpr size_t SZ = 27;
+  long p[SZ + 1];
+  for (int i = 0; i < SZ + 1; ++i)
+    p[i] = i;
+  p[SZ] = SZ / 3;
+#if defined(POISON_DATA)
+  __msan_poison(p, sizeof(long) * SZ / 2);
+#elif defined(POISON_KEY)
+  __msan_poison(p + SZ, sizeof(long));
+#endif
+  const long *r = (const long *)bsearch(p + SZ, p, SZ, sizeof(long), compar);
+  // CHECK: MemorySanitizer: use-of-uninitialized-value
+
+  assert(r == p + SZ / 3);
+
+  return 0;
+}

compiler-rt/test/sanitizer_common/TestCases/Posix/bsearch.cpp

+// Check interceptor.
+// RUN: %clangxx -O0 %s -o %t && %run %t 2>&1 | FileCheck %s
+
+// Inlined bsearch works even without interceptors.
+// RUN: %clangxx -O2 %s -o %t && %run %t 2>&1 | FileCheck %s
+
+#include <stdio.h>
+#include <stdlib.h>
+
+static int arr1[] = {8, 7, 6, 5, 4, 3, 2, 1, 0};
+static int arr2[] = {10, 1, 1, 3, 4, 6, 7, 7};
+
+#define array_size(x) (sizeof(x) / sizeof(x[0]))
+
+static int cmp_ints(const void *a, const void *b) {
+  return *(const int *)b - *(const int *)a;
+}
+
+static int cmp_pos(const void *a, const void *b) {
+  const int *ap =
+      (const int *)bsearch(a, arr1, array_size(arr1), sizeof(int), &cmp_ints);
+  if (!ap)
+    ap = arr1 + array_size(arr1);
+  const int *bp =
+      (const int *)bsearch(b, arr1, array_size(arr1), sizeof(int), &cmp_ints);
+  if (!bp)
+    bp = arr1 + array_size(arr1);
+  return bp - ap;
+}
+
+int main() {
+  // Simple bsearch.
+  for (int i = 0; i < 10; ++i) {
+    const void *r =
+        bsearch(&i, arr1, array_size(arr1), sizeof(arr1[0]), &cmp_ints);
+    if (!r)
+      printf(" null");
+    else
+      printf(" %d", *(const int *)r);
+  }
+  printf("\n");
+  // CHECK: 0 1 2 3 4 5 6 7 8 null
+
+  // Nested bsearch.
+  for (int i = 0; i < 10; ++i) {
+    const void *r =
+        bsearch(&i, arr2, array_size(arr2), sizeof(arr2[0]), &cmp_pos);
+    if (!r)
+      printf(" null");
+    else
+      printf(" %d", *(const int *)r);
+  }
+  printf("\n");
+  // CHECK: null 1 null 3 4 null 6 7 null 10
+}