[ASAN] fix crash in GetGlobalsForAddress after dlclose

[Lekensteyn]

Summary

Calling __asan_describe_address after unloading any library through
dlclose or FreeLibrary currently results in a crash due to accessing
unmapped memory (the Global structure in list_of_all_globals).

As list_of_all_globals is only accessed under a lock, it is safe to
remove items in UnregisterGlobal.

To prevent a significant slowdown (0.8 secs before this patch, 5.2 secs
for an initial O(n^2) version that naively walks the list), optimize it:

1. Reverse the loop (reduces time to 1.0 sec), 2. Cache the start of the

loop (restores original performance). Both changes make O(n) possible.

The above test was performed on a project that starts with 881337
globals. It would load 24125 additional globals through 14 plugins.
I confirmed through gdb that the size of list_of_all_globals indeed
shrinks (the size at exit matches with the size at startup).

Fixes https://github.com/google/sanitizers/issues/741
Fixes https://github.com/google/sanitizers/issues/963

[Lekensteyn]

Note: the issue was reproduced on both Linux (clang from trunk) and Windows (Clang 6.0.0). The fix was tested for Linux, but not on Windows (if someone has a setup ready, please test!). I also confirmed that the latest patch passes the test on Windows 7 and 10 (x64) and that without the patch, it crashes.

ASAN_OPTIONS=handle_segv=0 is set to avoid a hang due to a recursive invocation on the unfixed library:

AddressSanitizer:DEADLYSIGNAL
#0  __sanitizer::BlockingMutex::Lock () projects/compiler-rt/lib/sanitizer_common/sanitizer_linux.cc:665
#1  0x00000000004f2394 in __sanitizer::ThreadRegistry::Lock () projects/compiler-rt/lib/asan/../sanitizer_common/sanitizer_thread_registry.h:92
#2  __asan::ScopedInErrorReport::ScopedInErrorReport () projects/compiler-rt/lib/asan/asan_report.cc:131
#3  __asan::ReportDeadlySignal () projects/compiler-rt/lib/asan/asan_report.cc:212
#4  0x00000000004f0e25 in __asan::AsanOnDeadlySignal () projects/compiler-rt/lib/asan/asan_posix.cc:38
#5  <signal handler called>
#6  0x0000000000435e99 in __asan::GetGlobalsForAddress () projects/compiler-rt/lib/asan/asan_flags.h:42
#7  0x000000000042c153 in __asan::GetGlobalAddressInformation () projects/compiler-rt/lib/asan/asan_descriptions.cc:307
#8  __asan::PrintAddressDescription () projects/compiler-rt/lib/asan/asan_descriptions.cc:489
#9  0x00000000004f9d96 in __asan_describe_address () projects/compiler-rt/lib/asan/asan_report.cc:486
#10 0x000000000052b649 in main () projects/compiler-rt/test/asan/TestCases/Posix/dlclose-globals.cc:30

I have not done a measurement against projects that have many globals and unload large libraries with many globals. If the most recently loaded library is unloaded first, then performance should not be that bad as the globals are expected to be in the front of the list.

[Lekensteyn]

Since performance was pretty bad at exit (see https://github.com/google/sanitizers/issues/963#issuecomment-396323984), I decided that optimization is mandatory for this version. UnregisterGlobals is apparently not only called for dlclose, but also for other shared libaries.

I have no test for the *order* of UnregisterGlobal, this could potentially result in performance regressions that the optimizations were trying to address.
If necessary, I can check that through ASAN_OPTIONS=report_globals=2. I was however not sure whether the order is deterministic. For example, given extern "C" { const char *a = "foo"; const int b = 3; }, can I be sure that these are always registered as a, then b? (And will it subsequently be unregistered as such)?

[Lekensteyn]

ping

lib/asan/asan_globals.cc

if (!dynamic_init_globals) {
           new (allocator_for_globals) VectorOfGlobals;  // NOLINT
       dynamic_init_globals->reserve(kDynamicInitGlobalsInitialCapacity);
     }
     DynInitGlobal dyn_global = { *g, false };
     dynamic_init_globals->push_back(dyn_global);
   }
 }
 
-static void UnregisterGlobal(const Global *g) {
+static void UnregisterGlobal(const Global *g, ListOfGlobals **prev_list) {
   CHECK(asan_inited);
   if (flags()->report_globals >= 2)
     ReportGlobal(*g, "Removed");
   CHECK(flags()->report_globals);
   CHECK(AddrIsInMem(g->beg));
   CHECK(AddrIsAlignedByGranularity(g->beg));
   CHECK(AddrIsAlignedByGranularity(g->size_with_redzone));
   if (CanPoisonMemory())
     PoisonShadowForGlobal(g, 0);
-  // We unpoison the shadow memory for the global but we do not remove it from
-  // the list because that would require O(n^2) time with the current list
-  // implementation. It might not be worth doing anyway.
+
+  // We unpoisoned the shadow memory for the global and remove it from the list
+  // of globals to prevent GetGlobalsForAddress from accessing unmapped memory.
+  ListOfGlobals *l;
+  if (*prev_list && (l = (*prev_list)->next) && l->g == g) {
+    // Optimization: when an array of globals is unregistered, the items to be
+    // removed succeed each other so take advantage of that.
+    (*prev_list)->next = l->next;
+  } else {
+    // The start node in the list is initially unknown, so try to find it.
+    ListOfGlobals *last_l = nullptr;
+    for (ListOfGlobals *l = list_of_all_globals; l; l = l->next) {
+      if (l->g == g) {
+        // Found the global, now unlink it from the list and remember the
+        // position for the next UnregisterGlobal call.
+        if (last_l) {
+          last_l->next = l->next;
+          *prev_list = last_l;
+        } else {
+          list_of_all_globals = l->next;
+          *prev_list = nullptr;
+        }
+        // Allocator for 'l' does not have a delete operator, just leak it.
+        break;
+      } else {
+        last_l = l;
+      }
+    }
+  }
 
   // Release ODR indicator.
   if (UseODRIndicator(g)) {
     u8 *odr_indicator = reinterpret_cast<u8 *>(g->odr_indicator);
     *odr_indicator = UNREGISTERED;
   }
 }
 
PoisonShadow(reinterpret_cast<uptr>(globals), n * sizeof(__asan_global),
                kAsanGlobalRedzoneMagic);
 }
 
 // Unregister an array of globals.
 // We must do this when a shared objects gets dlclosed.
 void __asan_unregister_globals(__asan_global *globals, uptr n) {
   if (!flags()->report_globals) return;
   BlockingMutexLock lock(&mu_for_globals);
-  for (uptr i = 0; i < n; i++) {
+  // Cache the offset within the globals list and walk backwards the globals
+  // array to have O(n) time for removing items from the globals list (where n
+  // is the globals list size). Without this cache it could become O(n^2).
+  ListOfGlobals *prev_list = nullptr;
+  for (uptr i = n; i-- > 0; ) {
     if (SANITIZER_WINDOWS && globals[i].beg == 0) {
       // Skip globals that look like padding from the MSVC incremental linker.
       // See comment in __asan_register_globals.
       continue;
     }
-    UnregisterGlobal(&globals[i]);
+    UnregisterGlobal(&globals[i], &prev_list);
   }
 
   // Unpoison the metadata.
   PoisonShadow(reinterpret_cast<uptr>(globals), n * sizeof(__asan_global), 0);
 }
 
 // This method runs immediately prior to dynamic initialization in each TU,
 // when all dynamically initialized globals are unpoisoned.  This method

test/asan/TestCases/Posix/dlclose-globals.cc

+// RUN: %clangxx_asan -O0 -DSHARED_LIB %s -fPIC -shared -o %t-so.so
+// RUN: %clangxx_asan -O0 %s %libdl -o %t
+// RUN: %env_asan_opts=handle_segv=0 %run %t %t-so.so 2>&1 | FileCheck %s
+
+#include <dlfcn.h>
+#include <sanitizer/asan_interface.h>
+#include <stdio.h>
+
+#ifndef SHARED_LIB
+int main(int argc, char **argv) {
+  if (argc != 2) {
+    printf("Usage: %s test.so\n", argv[0]);
+    return 1;
+  }
+  const char *libname = argv[1];
+  void *handle = dlopen(argv[1], RTLD_NOW | RTLD_LOCAL);
+  if (!handle) {
+    printf("dlopen failed: %s\n", dlerror());
+    return 2;
+  }
+  char *ver = (char *)dlsym(handle, "VERSION");
+  if (!ver) {
+    printf("dlsym(VERSION) failed: %s\n", dlerror());
+    return 3;
+  }
+
+  // CHECK: VERSION: dummy 1.0
+  printf("VERSION: %s\n", ver);
+  fflush(stdout);
+  dlclose(handle);
+
+  // CHECK: AddressSanitizer can not describe address in more detail (wild memory access suspected).
+  __asan_describe_address(0);
+  return 0;
+}
+#else  // SHARED_LIB
+extern "C" const char VERSION[] = "dummy 1.0";
+#endif // SHARED_LIB

test/asan/TestCases/Windows/freelibrary-globals.cc

+// RUN: %clang_cl_asan -LD -O0 -DSHARED_LIB %s -Fe%t.dll
+// RUN: %clang_cl_asan -O0 %s -Fe%te.exe
+// RUN: %env_asan_opts=handle_segv=0 %run %te.exe %t.dll 2>&1 | FileCheck %s
+
+#include <sanitizer/asan_interface.h>
+#include <stdio.h>
+#include <windows.h>
+
+#ifndef SHARED_LIB
+int main(int argc, char **argv) {
+  if (argc != 2) {
+    printf("Usage: %s test.dll\n", argv[0]);
+    return 1;
+  }
+  const char *libname = argv[1];
+  HMODULE handle = LoadLibrary(libname);
+  if (!handle)
+    return 2;
+
+  char *ver = (char *)GetProcAddress(handle, "VERSION");
+  if (!ver)
+    return 3;
+
+  // CHECK: VERSION: dummy 1.0
+  printf("VERSION: %s\n", ver);
+  fflush(stdout);
+  FreeLibrary(handle);
+
+  // CHECK: AddressSanitizer can not describe address in more detail (wild memory access suspected).
+  __asan_describe_address(0);
+  return 0;
+}
+#else  // SHARED_LIB
+extern "C" __declspec(dllexport) const char VERSION[] = "dummy 1.0";
+#endif // SHARED_LIB