diff --git a/libc/malloc_debug/MapData.cpp b/libc/malloc_debug/MapData.cpp
index c38362b..8e9c806 100644
--- a/libc/malloc_debug/MapData.cpp
+++ b/libc/malloc_debug/MapData.cpp
@@ -110,7 +110,7 @@
   }
 }
 
-bool MapData::Initialize() {
+bool MapData::ReadMaps() {
   FILE* fp = fopen("/proc/self/maps", "re");
   if (fp == nullptr) {
     return false;
@@ -120,23 +120,21 @@
   while (fgets(buffer.data(), buffer.size(), fp) != nullptr) {
     MapEntry* entry = parse_line(buffer.data());
     if (entry == nullptr) {
+      fclose(fp);
       return false;
     }
-    entries_.push_back(entry);
+
+    auto it = entries_.find(entry);
+    if (it == entries_.end()) {
+      entries_.insert(entry);
+    } else {
+      delete entry;
+    }
   }
   fclose(fp);
   return true;
 }
 
-MapData* MapData::Create() {
-  MapData* maps = new MapData();
-  if (!maps->Initialize()) {
-    delete maps;
-    return nullptr;
-  }
-  return maps;
-}
-
 MapData::~MapData() {
   for (auto* entry : entries_) {
     delete entry;
@@ -146,19 +144,25 @@
 
 // Find the containing map info for the PC.
 const MapEntry* MapData::find(uintptr_t pc, uintptr_t* rel_pc) {
-  for (auto* entry : entries_) {
-    if ((pc >= entry->start) && (pc < entry->end)) {
-      if (!entry->load_base_read) {
-        read_loadbase(entry);
-      }
-      if (rel_pc) {
-        *rel_pc = pc - entry->start + entry->load_base;
-      }
-      return entry;
-    }
+  MapEntry pc_entry(pc);
+
+  std::lock_guard<std::mutex> lock(m_);
+
+  auto it = entries_.find(&pc_entry);
+  if (it == entries_.end()) {
+    ReadMaps();
+  }
+  it = entries_.find(&pc_entry);
+  if (it == entries_.end()) {
+    return nullptr;
+  }
+
+  MapEntry *entry = *it;
+  if (!entry->load_base_read) {
+    read_loadbase(entry);
   }
   if (rel_pc) {
-    *rel_pc = pc;
+    *rel_pc = pc - entry->start + entry->load_base;
   }
-  return nullptr;
+  return entry;
 }
diff --git a/libc/malloc_debug/MapData.h b/libc/malloc_debug/MapData.h
index d5f315ab..0238139 100644
--- a/libc/malloc_debug/MapData.h
+++ b/libc/malloc_debug/MapData.h
@@ -31,8 +31,9 @@
 
 #include <sys/cdefs.h>
 
+#include <mutex>
 #include <string>
-#include <vector>
+#include <set>
 
 #include <private/bionic_macros.h>
 
@@ -40,6 +41,8 @@
   MapEntry(uintptr_t start, uintptr_t end, uintptr_t offset, const char* name, size_t name_len)
       : start(start), end(end), offset(offset), name(name, name_len) {}
 
+  MapEntry(uintptr_t pc) : start(pc), end(pc) {}
+
   uintptr_t start;
   uintptr_t end;
   uintptr_t offset;
@@ -48,18 +51,26 @@
   std::string name;
 };
 
+
+// Ordering comparator that returns equivalence for overlapping entries
+struct compare_entries {
+  bool operator()(const MapEntry* a, const MapEntry* b) const {
+    return a->end <= b->start;
+  }
+};
+
 class MapData {
  public:
-  static MapData* Create();
+  MapData() = default;
   ~MapData();
 
   const MapEntry* find(uintptr_t pc, uintptr_t* rel_pc = nullptr);
 
  private:
-  MapData() = default;
-  bool Initialize();
+  bool ReadMaps();
 
-  std::vector<MapEntry*> entries_;
+  std::mutex m_;
+  std::set<MapEntry*, compare_entries> entries_;
 
   DISALLOW_COPY_AND_ASSIGN(MapData);
 };
diff --git a/libc/malloc_debug/backtrace.cpp b/libc/malloc_debug/backtrace.cpp
index 716e672..18ce8b8 100644
--- a/libc/malloc_debug/backtrace.cpp
+++ b/libc/malloc_debug/backtrace.cpp
@@ -50,7 +50,7 @@
 
 extern "C" char* __cxa_demangle(const char*, char*, size_t*, int*);
 
-static MapData* g_map_data = nullptr;
+static MapData g_map_data;
 static const MapEntry* g_current_code_map = nullptr;
 
 static _Unwind_Reason_Code find_current_map(__unwind_context* context, void*) {
@@ -59,20 +59,15 @@
   if (ip == 0) {
     return _URC_END_OF_STACK;
   }
-  g_current_code_map = g_map_data->find(ip);
+  g_current_code_map = g_map_data.find(ip);
   return _URC_END_OF_STACK;
 }
 
 void backtrace_startup() {
-  g_map_data = MapData::Create();
-  if (g_map_data) {
-    _Unwind_Backtrace(find_current_map, nullptr);
-  }
+  _Unwind_Backtrace(find_current_map, nullptr);
 }
 
 void backtrace_shutdown() {
-  delete g_map_data;
-  g_map_data = nullptr;
 }
 
 struct stack_crawl_state_t {
@@ -150,10 +145,8 @@
     }
 
     uintptr_t rel_pc = offset;
-    const MapEntry* entry = nullptr;
-    if (g_map_data) {
-      entry = g_map_data->find(frames[frame_num], &rel_pc);
-    }
+    const MapEntry* entry = g_map_data.find(frames[frame_num], &rel_pc);
+
     const char* soname = (entry != nullptr) ? entry->name.c_str() : info.dli_fname;
     if (soname == nullptr) {
       soname = "<unknown>";