[TSan] Support `ignore_noninstrumented_modules` on Linux

[yln]

Summary

We implemented the ignore_noninstrumented_modules flag for Darwin [1]
to be able to use TSan on Darwin, where the "re-compile the world"
approach is difficult to follow in practice.

Now we are in the same situation when adding TSan support for Swift on
Linux. The libdispatch library is a source of false positives and
compiling it with TSan (although it is compiled from source on Linux)
proves to be tricky and insufficient. The better path seems to be to
make ignore_noninstrumented_modules work on Linux.

The missing piece with this functionality on Linux is the detection
whether or not a loaded library is instrumented (which is suprisingly
difficult). In this patch we use the ELF segment metadata and symbol
table to check whether any sanitizer symbols are present. [2,3] were
useful resources in the development of this patch (especially,
getSymbolCountFromGnuHash).

Also enable flag for libdispatch tests on Linux to make them pass. The
default value for this flag on Linux remains OFF.

[1]: https://reviews.llvm.org/D28264
[2]: https://chromium.googlesource.com/crashpad/crashpad/+/1f1657d573c789aa36b6022440e34d9ec30d894c%5E%21/
[3]: https://flapenguin.me/2017/05/10/elf-lookup-dt-gnu-hash/

[yln]

compiler-rt/lib/sanitizer_common/sanitizer_linux_libcdep.cc

661

ignore_noninstrumented_modules is only relevant for TSan, but this code is in sanitizer_common. Is this acceptable? How can we make it better?

[kubamracek]

Nice, thanks. I don’t understand the ELF code so someone else should review it, but from my view this LGTM.

[dvyukov]

Evgenii, maybe you can think of some simpler magical way to understand if a module is instrumented or not?

[yln]

Chang symbol name check to require an exact match with the TSan
initializer called from the module ctor. This should avoid
accidental matches, e.g., __tsan_testonly_barrier_wait in tests.
My assumption is that this symbol is present in all modules
instrumented with TSan.

Add non-platform specific test. (I kept the existing test for
Darwin because it tests a specific system API.)

[yln]

Fix linker error in test.

[yln]

*ping*

[dvyukov]

I am still a bit worried by the amount of complex code we have for this. I wonder if there is a simpler way to do this. Have you considered any other alternatives? Could we emit some symbol in the library and then use dlsym on it? Or maybe emit some section and then iterate over section names only?

[yln]

In D61708#1509531, @dvyukov wrote:

I am still a bit worried by the amount of complex code we have for this. I wonder if there is a simpler way to do this. Have you considered any other alternatives?

I agree with you on the complexity here. Alternatives: it's the only thing I was able to come up with without the help of the compiler.

Could we emit some symbol in the library and then use dlsym on it? Or maybe emit some section and then iterate over section names only?

That sounds certainly possible (and less complex). Initially, I wasn't sure if we want to try to avoid requiring compiler, but I can't think of disadvantages that we don't already have (compiler/runtime compatibility).

I will try the emit symbol/dlopen approach you suggested and open a new revision for it. Is it okay if this is TSan-specific?

[dvyukov]

There is also dlinfo which returns some info about a shared object. I don't know if it may help or not, just pointing out. We need just any mark that the compiler can leave in the shared object and runtime then can detect as easily as possible.

What do you mean by tsan-specific?

[dvyukov]

If you mean that it will work only for tsan now, I guess it is fine. Other sanitizers can add it when they need it.

compiler-rt/lib/sanitizer_common/sanitizer_common.h

LoadedModule()
       : full_name_(nullptr),
         base_address_(0),
         max_executable_address_(0),
         arch_(kModuleArchUnknown),
         instrumented_(false) {
     internal_memset(uuid_, 0, kModuleUUIDSize);
     ranges_.clear();
   }
-  void set(const char *module_name, uptr base_address);
+  void set(const char *module_name, uptr base_address,
+           bool instrumented = false);
   void set(const char *module_name, uptr base_address, ModuleArch arch,
            u8 uuid[kModuleUUIDSize], bool instrumented);
   void clear();
   void addAddressRange(uptr beg, uptr end, bool executable, bool writable,
                        const char *name = nullptr);
   bool containsAddress(uptr address) const;
 
   const char *full_name() const { return full_name_; }

compiler-rt/lib/sanitizer_common/sanitizer_common.cc

while (*s != '\0') {
     z++;
     s++;
   }
 
   // Null terminate the string.
   *z = '\0';
 }
 
-void LoadedModule::set(const char *module_name, uptr base_address) {
+void LoadedModule::set(const char *module_name, uptr base_address,
+                       bool instrumented) {
   clear();
   full_name_ = internal_strdup(module_name);
   base_address_ = base_address;
+  instrumented_ = instrumented;
 }
 
 void LoadedModule::set(const char *module_name, uptr base_address,
                        ModuleArch arch, u8 uuid[kModuleUUIDSize],
                        bool instrumented) {
-  set(module_name, base_address);
+  set(module_name, base_address, instrumented);
   arch_ = arch;
   internal_memcpy(uuid_, uuid, sizeof(uuid_));
-  instrumented_ = instrumented;
 }
 
 void LoadedModule::clear() {
   InternalFree(full_name_);
   base_address_ = 0;
   max_executable_address_ = 0;
   full_name_ = nullptr;
   arch_ = kModuleArchUnknown;

compiler-rt/lib/sanitizer_common/sanitizer_linux_libcdep.cc

 #define dl_iterate_phdr(c, b) xdl_iterate_phdr((c), (b))
 #endif // !SANITIZER_FREEBSD && !SANITIZER_OPENBSD
 
 struct DlIteratePhdrData {
   InternalMmapVectorNoCtor<LoadedModule> *modules;
   bool first;
 };
 
+class DynamicSegment {
+  ElfW(Addr) base_addr;
+  size_t symbol_count;
+  ElfW(Sym *) symbol_table;
+  const char *string_table;
+
+ public:
+  DynamicSegment(ElfW(Addr) base_addr, ElfW(Addr) segment_addr)
+      : base_addr(base_addr),
+        symbol_count(0),
+        symbol_table(nullptr),
+        string_table(nullptr) {
+    initialize(segment_addr);
+    CHECK(symbol_count > 0 && symbol_table && string_table);
+  }
+
+  size_t symbolCount() const { return symbol_count; }
+
+  const char *getSymbolName(size_t index) const {
+    auto str_index = symbol_table[index].st_name;
+    return &string_table[str_index];
+  }
+
+ private:
+  // Elf_Addr -> dereferenceable pointer
+  template <typename Type>
+  Type *toPtr(ElfW(Addr) addr_or_offset) const {
+    bool offset = addr_or_offset < base_addr;
+    ElfW(Addr) ptr = offset ? (base_addr + addr_or_offset) : addr_or_offset;
+    return reinterpret_cast<Type *>(ptr);
+  }
+
+  void initialize(ElfW(Addr) segment_addr) {
+    auto *entry = toPtr<ElfW(Dyn)>(segment_addr);
+    for (; entry->d_tag != DT_NULL; entry++) {
+      auto addr = entry->d_un.d_ptr;
+      switch (entry->d_tag) {
+        case DT_HASH:
+          symbol_count = getSymbolCountFromHash(addr);
+          break;
+        case DT_GNU_HASH:
+          // DT_HASH takes precedence over DT_GNU_HASH
+          if (symbol_count > 0)
+            break;
+          symbol_count = getSymbolCountFromGnuHash(addr);
+          break;
+        case DT_SYMTAB:
+          CHECK_EQ(symbol_table, nullptr);
+          symbol_table = toPtr<ElfW(Sym)>(addr);
+          break;
+        case DT_STRTAB:
+          CHECK_EQ(string_table, nullptr);
+          string_table = toPtr<const char>(addr);
+          break;
+      }
+    }
+  }
+
+  size_t getSymbolCountFromHash(ElfW(Addr) hashtable_addr) const {
+    struct ht_header {
+      uint32_t bucket_count;
+      uint32_t chain_count;
+    };
+    return toPtr<ht_header>(hashtable_addr)->chain_count;
+  }
+
+  size_t getSymbolCountFromGnuHash(ElfW(Addr) hashtable_addr) const {
+    struct ht_header {
+      uint32_t bucket_count;
+      uint32_t symoffset;
+      uint32_t bloom_size;
+      uint32_t bloom_shift;
+    };
+    auto header = toPtr<ht_header>(hashtable_addr);
+    auto word_size = FIRST_32_SECOND_64(sizeof(uint32_t), sizeof(uint64_t));
+    auto buckets_addr =
+        hashtable_addr + sizeof(ht_header) + (word_size * header->bloom_size);
+    auto buckets = toPtr<uint32_t>(buckets_addr);
+    auto chains_addr =
+        buckets_addr + (header->bucket_count * sizeof(buckets[0]));
+    auto chains = toPtr<uint32_t>(chains_addr);
+
+    // Locate the chain that handles the largest index bucket.
+    uint32_t last_symbol = 0;
+    for (uint32_t i = 0; i < header->bucket_count; i++) {
+      last_symbol = Max(buckets[i], last_symbol);
+    }
+
+    if (last_symbol < header->symoffset)
+      return header->symoffset;
+
+    // Walk the bucket's chain to add the chain length to the total.
+    uint32_t chain_entry;
+    do {
+      chain_entry = chains[last_symbol - header->symoffset];
+      last_symbol++;
+    } while ((chain_entry & 1) == 0);
+
+    return last_symbol;
+  }
+};
+
+static bool IsModuleInstrumented(dl_phdr_info *info) {
+  // Iterate all headers of the library.
+  for (size_t header = 0; header < info->dlpi_phnum; header++) {
+    // We are only interested in dynamic segments.
+    if (info->dlpi_phdr[header].p_type != PT_DYNAMIC)
+      continue;
+
+    auto base_addr = info->dlpi_addr;
+    auto segment_addr = info->dlpi_phdr[header].p_vaddr;
+    DynamicSegment segment(base_addr, segment_addr);
+
+    // Iterate symbol table.
+    for (size_t i = 0; i < segment.symbolCount(); i++) {
+      auto *name = segment.getSymbolName(i);
+      // TODO(yln): make this better
+      if (internal_strstr(name, "__tsan_"))
+        return true;
+    }
+  }
+  return false;
+}
+
 static int dl_iterate_phdr_cb(dl_phdr_info *info, size_t size, void *arg) {
   DlIteratePhdrData *data = (DlIteratePhdrData*)arg;
   InternalScopedString module_name(kMaxPathLength);
   if (data->first) {
     data->first = false;
     // First module is the binary itself.
     ReadBinaryNameCached(module_name.data(), module_name.size());
   } else if (info->dlpi_name) {
     module_name.append("%s", info->dlpi_name);
   }
   if (module_name[0] == '\0')
     return 0;
   LoadedModule cur_module;
-  cur_module.set(module_name.data(), info->dlpi_addr);
+  bool instrumented = IsModuleInstrumented(info);
+  cur_module.set(module_name.data(), info->dlpi_addr, instrumented);
   for (int i = 0; i < (int)info->dlpi_phnum; i++) {
     const Elf_Phdr *phdr = &info->dlpi_phdr[i];
     if (phdr->p_type == PT_LOAD) {
       uptr cur_beg = info->dlpi_addr + phdr->p_vaddr;
       uptr cur_end = cur_beg + phdr->p_memsz;
       bool executable = phdr->p_flags & PF_X;
       bool writable = phdr->p_flags & PF_W;
       cur_module.addAddressRange(cur_beg, cur_end, executable,

compiler-rt/test/tsan/libdispatch/lit.local.cfg

 def getRoot(config):
   if not config.parent:
     return config
   return getRoot(config.parent)
 
 root = getRoot(config)
 
 if 'libdispatch' in root.available_features:
   additional_cflags = ' -fblocks '
   for index, (template, replacement) in enumerate(config.substitutions):
     if template in ['%clang_tsan ', '%clangxx_tsan ']:
       config.substitutions[index] = (template, replacement + additional_cflags)
 else:
   config.unsupported = True
 
-if config.host_os == 'Darwin':
-  config.environment['TSAN_OPTIONS'] += ':ignore_noninstrumented_modules=1'