diff --git a/runtime/mem_map.cc b/runtime/mem_map.cc
index 39e838f..97b34ef 100644
--- a/runtime/mem_map.cc
+++ b/runtime/mem_map.cc
@@ -16,7 +16,7 @@
 
 #include "mem_map.h"
 
-#include <backtrace/backtrace.h>
+#include <backtrace/BacktraceMap.h>
 
 #include "base/stringprintf.h"
 #include "ScopedFd.h"
@@ -32,12 +32,16 @@
 
 #if !defined(NDEBUG)
 
-static std::ostream& operator<<(std::ostream& os, backtrace_map_info_t* rhs) {
-  for (backtrace_map_info_t* m = rhs; m != NULL; m = m->next) {
-    os << StringPrintf("0x%08x-0x%08x %c%c %s\n",
-                       static_cast<uint32_t>(m->start),
-                       static_cast<uint32_t>(m->end),
-                       m->is_readable ? 'r' : '-', m->is_executable ? 'x' : '-', m->name);
+static std::ostream& operator<<(
+    std::ostream& os,
+    std::pair<BacktraceMap::const_iterator, BacktraceMap::const_iterator> iters) {
+  for (BacktraceMap::const_iterator it = iters.first; it != iters.second; ++it) {
+    os << StringPrintf("0x%08x-0x%08x %c%c%c %s\n",
+                       static_cast<uint32_t>(it->start),
+                       static_cast<uint32_t>(it->end),
+                       (it->flags & PROT_READ) ? 'r' : '-',
+                       (it->flags & PROT_WRITE) ? 'w' : '-',
+                       (it->flags & PROT_EXEC) ? 'x' : '-', it->name.c_str());
   }
   return os;
 }
@@ -47,20 +51,24 @@
     return;
   }
 
-  uint32_t base = reinterpret_cast<size_t>(addr);
-  uint32_t limit = base + byte_count;
+  uintptr_t base = reinterpret_cast<uintptr_t>(addr);
+  uintptr_t limit = base + byte_count;
 
-  backtrace_map_info_t* map_info_list = backtrace_create_map_info_list(getpid());
-  for (backtrace_map_info_t* m = map_info_list; m != NULL; m = m->next) {
-    CHECK(!(base >= m->start && base < m->end)     // start of new within old
-        && !(limit > m->start && limit < m->end)   // end of new within old
-        && !(base <= m->start && limit > m->end))  // start/end of new includes all of old
+  BacktraceMap map(getpid());
+  if (!map.Build()) {
+    PLOG(WARNING) << "Failed to build process map";
+    return;
+  }
+  for (BacktraceMap::const_iterator it = map.begin(); it != map.end(); ++it) {
+    CHECK(!(base >= it->start && base < it->end)     // start of new within old
+        && !(limit > it->start && limit < it->end)   // end of new within old
+        && !(base <= it->start && limit > it->end))  // start/end of new includes all of old
         << StringPrintf("Requested region 0x%08x-0x%08x overlaps with existing map 0x%08x-0x%08x (%s)\n",
                         base, limit,
-                        static_cast<uint32_t>(m->start), static_cast<uint32_t>(m->end), m->name)
-        << map_info_list;
+                        static_cast<uint32_t>(it->start), static_cast<uint32_t>(it->end),
+                        it->name.c_str())
+        << std::make_pair(it, map.end());
   }
-  backtrace_destroy_map_info_list(map_info_list);
 }
 
 #else
diff --git a/runtime/utils.cc b/runtime/utils.cc
index 2ad4c4a..a293043 100644
--- a/runtime/utils.cc
+++ b/runtime/utils.cc
@@ -16,6 +16,7 @@
 
 #include "utils.h"
 
+#include <inttypes.h>
 #include <pthread.h>
 #include <sys/stat.h>
 #include <sys/syscall.h>
@@ -1035,17 +1036,17 @@
   return "";
 }
 
-static const char* CleanMapName(const char* map_name) {
-  if (map_name == NULL) {
+static std::string CleanMapName(const backtrace_map_t* map) {
+  if (map == NULL || map->name.empty()) {
     return "???";
   }
   // Turn "/usr/local/google/home/enh/clean-dalvik-dev/out/host/linux-x86/lib/libartd.so"
   // into "libartd.so".
-  const char* last_slash = strrchr(map_name, '/');
-  if (last_slash != NULL) {
-    map_name = last_slash + 1;
+  size_t last_slash = map->name.rfind('/');
+  if (last_slash == std::string::npos) {
+    return map->name;
   }
-  return map_name;
+  return map->name.substr(last_slash);
 }
 
 void DumpNativeStack(std::ostream& os, pid_t tid, const char* prefix, bool include_count) {
@@ -1058,25 +1059,24 @@
     return;
   }
 
-  for (size_t i = 0; i < backtrace->NumFrames(); ++i) {
+  for (Backtrace::const_iterator it = backtrace->begin();
+       it != backtrace->end(); ++it) {
     // We produce output like this:
     // ]    #00 unwind_backtrace_thread+536 [0x55d75bb8] (libbacktrace.so)
-    const backtrace_frame_data_t* frame = backtrace->GetFrame(i);
-
     os << prefix;
     if (include_count) {
-      os << StringPrintf("#%02zu ", i);
+      os << StringPrintf("#%02zu ", it->num);
     }
-    if (frame->func_name) {
-      os << frame->func_name;
+    if (!it->func_name.empty()) {
+      os << it->func_name;
     } else {
       os << "???";
     }
-    if (frame->func_offset != 0) {
-      os << "+" << frame->func_offset;
+    if (it->func_offset != 0) {
+      os << "+" << it->func_offset;
     }
-    os << StringPrintf(" [%p]", reinterpret_cast<void*>(frame->pc));
-    os << " (" << CleanMapName(frame->map_name) << ")\n";
+    os << StringPrintf(" [%p]", reinterpret_cast<void*>(it->pc));
+    os << " (" << CleanMapName(it->map) << ")\n";
   }
 }