diff --git a/runtime/debugger.cc b/runtime/debugger.cc
index 109e03d..d832552 100644
--- a/runtime/debugger.cc
+++ b/runtime/debugger.cc
@@ -4818,7 +4818,7 @@
   LOG(INFO) << "Tracked allocations, (count=" << count << ")";
   for (auto it = records->RBegin(), end = records->REnd();
       count > 0 && it != end; count--, it++) {
-    const gc::AllocRecord* record = it->second;
+    const gc::AllocRecord* record = &it->second;
 
     LOG(INFO) << StringPrintf(" Thread %-2d %6zd bytes ", record->GetTid(), record->ByteCount())
               << PrettyClass(record->GetClass());
@@ -4957,7 +4957,7 @@
     uint16_t count = capped_count;
     for (auto it = records->RBegin(), end = records->REnd();
          count > 0 && it != end; count--, it++) {
-      const gc::AllocRecord* record = it->second;
+      const gc::AllocRecord* record = &it->second;
       std::string temp;
       class_names.Add(record->GetClassDescriptor(&temp));
       for (size_t i = 0, depth = record->GetDepth(); i < depth; i++) {
@@ -5008,7 +5008,7 @@
       // (2b) thread id
       // (2b) allocated object's class name index
       // (1b) stack depth
-      const gc::AllocRecord* record = it->second;
+      const gc::AllocRecord* record = &it->second;
       size_t stack_depth = record->GetDepth();
       size_t allocated_object_class_name_index =
           class_names.IndexOf(record->GetClassDescriptor(&temp));
diff --git a/runtime/gc/allocation_record.cc b/runtime/gc/allocation_record.cc
index e3714bb..44059b1 100644
--- a/runtime/gc/allocation_record.cc
+++ b/runtime/gc/allocation_record.cc
@@ -102,15 +102,15 @@
   // Only visit the last recent_record_max_ number of allocation records in entries_ and mark the
   // klass_ fields as strong roots.
   for (auto it = entries_.rbegin(), end = entries_.rend(); it != end; ++it) {
-    AllocRecord* record = it->second;
+    AllocRecord& record = it->second;
     if (count > 0) {
-      buffered_visitor.VisitRootIfNonNull(record->GetClassGcRoot());
+      buffered_visitor.VisitRootIfNonNull(record.GetClassGcRoot());
       --count;
     }
     // Visit all of the stack frames to make sure no methods in the stack traces get unloaded by
     // class unloading.
-    for (size_t i = 0, depth = record->GetDepth(); i < depth; ++i) {
-      const AllocRecordStackTraceElement& element = record->StackElement(i);
+    for (size_t i = 0, depth = record.GetDepth(); i < depth; ++i) {
+      const AllocRecordStackTraceElement& element = record.StackElement(i);
       DCHECK(element.GetMethod() != nullptr);
       element.GetMethod()->VisitRoots(buffered_visitor, sizeof(void*));
     }
@@ -143,15 +143,14 @@
     ++count;
     // This does not need a read barrier because this is called by GC.
     mirror::Object* old_object = it->first.Read<kWithoutReadBarrier>();
-    AllocRecord* record = it->second;
+    AllocRecord& record = it->second;
     mirror::Object* new_object = old_object == nullptr ? nullptr : visitor->IsMarked(old_object);
     if (new_object == nullptr) {
       if (count > delete_bound) {
         it->first = GcRoot<mirror::Object>(nullptr);
-        SweepClassObject(record, visitor);
+        SweepClassObject(&record, visitor);
         ++it;
       } else {
-        delete record;
         it = entries_.erase(it);
         ++count_deleted;
       }
@@ -160,7 +159,7 @@
         it->first = GcRoot<mirror::Object>(new_object);
         ++count_moved;
       }
-      SweepClassObject(record, visitor);
+      SweepClassObject(&record, visitor);
       ++it;
     }
   }
@@ -184,34 +183,31 @@
   new_record_condition_.Broadcast(Thread::Current());
 }
 
-struct AllocRecordStackVisitor : public StackVisitor {
-  AllocRecordStackVisitor(Thread* thread, AllocRecordStackTrace* trace_in, size_t max)
+class AllocRecordStackVisitor : public StackVisitor {
+ public:
+  AllocRecordStackVisitor(Thread* thread, size_t max_depth, AllocRecordStackTrace* trace_out)
       SHARED_REQUIRES(Locks::mutator_lock_)
       : StackVisitor(thread, nullptr, StackVisitor::StackWalkKind::kIncludeInlinedFrames),
-        trace(trace_in),
-        max_depth(max) {}
+        max_depth_(max_depth),
+        trace_(trace_out) {}
 
   // TODO: Enable annotalysis. We know lock is held in constructor, but abstraction confuses
   // annotalysis.
   bool VisitFrame() OVERRIDE NO_THREAD_SAFETY_ANALYSIS {
-    if (depth >= max_depth) {
+    if (trace_->GetDepth() >= max_depth_) {
       return false;
     }
     ArtMethod* m = GetMethod();
     if (!m->IsRuntimeMethod()) {
-      trace->SetStackElementAt(depth, m, GetDexPc());
-      ++depth;
+      m = m->GetInterfaceMethodIfProxy(sizeof(void*));
+      trace_->AddStackElement(AllocRecordStackTraceElement(m, GetDexPc()));
     }
     return true;
   }
 
-  ~AllocRecordStackVisitor() {
-    trace->SetDepth(depth);
-  }
-
-  AllocRecordStackTrace* trace;
-  size_t depth = 0u;
-  const size_t max_depth;
+ private:
+  const size_t max_depth_;
+  AllocRecordStackTrace* const trace_;
 };
 
 void AllocRecordObjectMap::SetAllocTrackingEnabled(bool enable) {
@@ -235,7 +231,6 @@
       if (self_name == "JDWP") {
         records->alloc_ddm_thread_id_ = self->GetTid();
       }
-      records->scratch_trace_.SetDepth(records->max_stack_depth_);
       size_t sz = sizeof(AllocRecordStackTraceElement) * records->max_stack_depth_ +
                   sizeof(AllocRecord) + sizeof(AllocRecordStackTrace);
       LOG(INFO) << "Enabling alloc tracker (" << records->alloc_record_max_ << " entries of "
@@ -265,27 +260,35 @@
   }
 }
 
-void AllocRecordObjectMap::RecordAllocation(Thread* self, mirror::Object* obj, mirror::Class* klass,
+void AllocRecordObjectMap::RecordAllocation(Thread* self,
+                                            mirror::Object** obj,
                                             size_t byte_count) {
+  // Get stack trace outside of lock in case there are allocations during the stack walk.
+  // b/27858645.
+  AllocRecordStackTrace trace;
+  AllocRecordStackVisitor visitor(self, max_stack_depth_, /*out*/ &trace);
+  {
+    StackHandleScope<1> hs(self);
+    auto obj_wrapper = hs.NewHandleWrapper(obj);
+    visitor.WalkStack();
+  }
+
   MutexLock mu(self, *Locks::alloc_tracker_lock_);
-  Heap* heap = Runtime::Current()->GetHeap();
+  Heap* const heap = Runtime::Current()->GetHeap();
   if (!heap->IsAllocTrackingEnabled()) {
     // In the process of shutting down recording, bail.
     return;
   }
 
-  AllocRecordObjectMap* records = heap->GetAllocationRecords();
-  DCHECK(records != nullptr);
-
-  // Do not record for DDM thread
-  if (records->alloc_ddm_thread_id_ == self->GetTid()) {
+  // Do not record for DDM thread.
+  if (alloc_ddm_thread_id_ == self->GetTid()) {
     return;
   }
 
   // Wait for GC's sweeping to complete and allow new records
-  while (UNLIKELY((!kUseReadBarrier && !records->allow_new_record_) ||
+  while (UNLIKELY((!kUseReadBarrier && !allow_new_record_) ||
                   (kUseReadBarrier && !self->GetWeakRefAccessEnabled()))) {
-    records->new_record_condition_.WaitHoldingLocks(self);
+    new_record_condition_.WaitHoldingLocks(self);
   }
 
   if (!heap->IsAllocTrackingEnabled()) {
@@ -294,28 +297,22 @@
     return;
   }
 
-  DCHECK_LE(records->Size(), records->alloc_record_max_);
+  DCHECK_LE(Size(), alloc_record_max_);
 
-  // Get stack trace.
-  // add scope to make "visitor" destroyed promptly, in order to set the scratch_trace_->depth_
-  {
-    AllocRecordStackVisitor visitor(self, &records->scratch_trace_, records->max_stack_depth_);
-    visitor.WalkStack();
-  }
-  records->scratch_trace_.SetTid(self->GetTid());
-  AllocRecordStackTrace* trace = new AllocRecordStackTrace(records->scratch_trace_);
+  // Erase extra unfilled elements.
+  trace.SetTid(self->GetTid());
 
-  // Fill in the basics.
-  AllocRecord* record = new AllocRecord(byte_count, klass, trace);
-
-  records->Put(obj, record);
-  DCHECK_LE(records->Size(), records->alloc_record_max_);
+  // Add the record.
+  Put(*obj, AllocRecord(byte_count, (*obj)->GetClass(), std::move(trace)));
+  DCHECK_LE(Size(), alloc_record_max_);
 }
 
 void AllocRecordObjectMap::Clear() {
-  STLDeleteValues(&entries_);
   entries_.clear();
 }
 
+AllocRecordObjectMap::AllocRecordObjectMap()
+    : new_record_condition_("New allocation record condition", *Locks::alloc_tracker_lock_) {}
+
 }  // namespace gc
 }  // namespace art
diff --git a/runtime/gc/allocation_record.h b/runtime/gc/allocation_record.h
index 18cce4d..a2d86cc 100644
--- a/runtime/gc/allocation_record.h
+++ b/runtime/gc/allocation_record.h
@@ -18,6 +18,7 @@
 #define ART_RUNTIME_GC_ALLOCATION_RECORD_H_
 
 #include <list>
+#include <memory>
 
 #include "base/mutex.h"
 #include "object_callbacks.h"
@@ -37,10 +38,13 @@
 
 class AllocRecordStackTraceElement {
  public:
-  AllocRecordStackTraceElement() : method_(nullptr), dex_pc_(0) {}
-
   int32_t ComputeLineNumber() const SHARED_REQUIRES(Locks::mutator_lock_);
 
+  AllocRecordStackTraceElement() = default;
+  AllocRecordStackTraceElement(ArtMethod* method, uint32_t dex_pc)
+      : method_(method),
+        dex_pc_(dex_pc) {}
+
   ArtMethod* GetMethod() const {
     return method_;
   }
@@ -58,32 +62,27 @@
   }
 
   bool operator==(const AllocRecordStackTraceElement& other) const {
-    if (this == &other) return true;
     return method_ == other.method_ && dex_pc_ == other.dex_pc_;
   }
 
  private:
-  ArtMethod* method_;
-  uint32_t dex_pc_;
+  ArtMethod* method_ = nullptr;
+  uint32_t dex_pc_ = 0;
 };
 
 class AllocRecordStackTrace {
  public:
   static constexpr size_t kHashMultiplier = 17;
 
-  explicit AllocRecordStackTrace(size_t max_depth)
-      : tid_(0), depth_(0), stack_(new AllocRecordStackTraceElement[max_depth]) {}
+  AllocRecordStackTrace() = default;
+
+  AllocRecordStackTrace(AllocRecordStackTrace&& r)
+      : tid_(r.tid_),
+        stack_(std::move(r.stack_)) {}
 
   AllocRecordStackTrace(const AllocRecordStackTrace& r)
-      : tid_(r.tid_), depth_(r.depth_), stack_(new AllocRecordStackTraceElement[r.depth_]) {
-    for (size_t i = 0; i < depth_; ++i) {
-      stack_[i] = r.stack_[i];
-    }
-  }
-
-  ~AllocRecordStackTrace() {
-    delete[] stack_;
-  }
+      : tid_(r.tid_),
+        stack_(r.stack_) {}
 
   pid_t GetTid() const {
     return tid_;
@@ -94,37 +93,32 @@
   }
 
   size_t GetDepth() const {
-    return depth_;
-  }
-
-  void SetDepth(size_t depth) {
-    depth_ = depth;
+    return stack_.size();
   }
 
   const AllocRecordStackTraceElement& GetStackElement(size_t index) const {
-    DCHECK_LT(index, depth_);
+    DCHECK_LT(index, GetDepth());
     return stack_[index];
   }
 
+  void AddStackElement(const AllocRecordStackTraceElement& element) {
+    stack_.push_back(element);
+  }
+
   void SetStackElementAt(size_t index, ArtMethod* m, uint32_t dex_pc) {
+    DCHECK_LT(index, stack_.size());
     stack_[index].SetMethod(m);
     stack_[index].SetDexPc(dex_pc);
   }
 
   bool operator==(const AllocRecordStackTrace& other) const {
     if (this == &other) return true;
-    if (tid_ != other.tid_) return false;
-    if (depth_ != other.depth_) return false;
-    for (size_t i = 0; i < depth_; ++i) {
-      if (!(stack_[i] == other.stack_[i])) return false;
-    }
-    return true;
+    return tid_ == other.tid_ && stack_ == other.stack_;
   }
 
  private:
-  pid_t tid_;
-  size_t depth_;
-  AllocRecordStackTraceElement* const stack_;
+  pid_t tid_ = 0;
+  std::vector<AllocRecordStackTraceElement> stack_;
 };
 
 struct HashAllocRecordTypes {
@@ -161,19 +155,15 @@
 class AllocRecord {
  public:
   // All instances of AllocRecord should be managed by an instance of AllocRecordObjectMap.
-  AllocRecord(size_t count, mirror::Class* klass, AllocRecordStackTrace* trace)
-      : byte_count_(count), klass_(klass), trace_(trace) {}
-
-  ~AllocRecord() {
-    delete trace_;
-  }
+  AllocRecord(size_t count, mirror::Class* klass, AllocRecordStackTrace&& trace)
+      : byte_count_(count), klass_(klass), trace_(std::move(trace)) {}
 
   size_t GetDepth() const {
-    return trace_->GetDepth();
+    return trace_.GetDepth();
   }
 
   const AllocRecordStackTrace* GetStackTrace() const {
-    return trace_;
+    return &trace_;
   }
 
   size_t ByteCount() const {
@@ -181,7 +171,7 @@
   }
 
   pid_t GetTid() const {
-    return trace_->GetTid();
+    return trace_.GetTid();
   }
 
   mirror::Class* GetClass() const SHARED_REQUIRES(Locks::mutator_lock_) {
@@ -196,16 +186,15 @@
   }
 
   const AllocRecordStackTraceElement& StackElement(size_t index) const {
-    return trace_->GetStackElement(index);
+    return trace_.GetStackElement(index);
   }
 
  private:
   const size_t byte_count_;
   // The klass_ could be a strong or weak root for GC
   GcRoot<mirror::Class> klass_;
-  // TODO: Currently trace_ is like a std::unique_ptr,
-  // but in future with deduplication it could be a std::shared_ptr.
-  const AllocRecordStackTrace* const trace_;
+  // TODO: Share between alloc records with identical stack traces.
+  AllocRecordStackTrace trace_;
 };
 
 class AllocRecordObjectMap {
@@ -215,36 +204,29 @@
   // weak roots). The last recent_record_max_ number of pairs in the list are always kept for DDMS's
   // recent allocation tracking, but GcRoot<mirror::Object> pointers in these pairs can become null.
   // Both types of pointers need read barriers, do not directly access them.
-  typedef std::list<std::pair<GcRoot<mirror::Object>, AllocRecord*>> EntryList;
+  using EntryPair = std::pair<GcRoot<mirror::Object>, AllocRecord>;
+  typedef std::list<EntryPair> EntryList;
 
-  // "static" because it is part of double-checked locking. It needs to check a bool first,
-  // in order to make sure the AllocRecordObjectMap object is not null.
-  static void RecordAllocation(Thread* self, mirror::Object* obj, mirror::Class* klass,
-                               size_t byte_count)
+  // Caller needs to check that it is enabled before calling since we read the stack trace before
+  // checking the enabled boolean.
+  void RecordAllocation(Thread* self,
+                        mirror::Object** obj,
+                        size_t byte_count)
       REQUIRES(!Locks::alloc_tracker_lock_)
       SHARED_REQUIRES(Locks::mutator_lock_);
 
   static void SetAllocTrackingEnabled(bool enabled) REQUIRES(!Locks::alloc_tracker_lock_);
 
-  AllocRecordObjectMap() REQUIRES(Locks::alloc_tracker_lock_)
-      : alloc_record_max_(kDefaultNumAllocRecords),
-        recent_record_max_(kDefaultNumRecentRecords),
-        max_stack_depth_(kDefaultAllocStackDepth),
-        scratch_trace_(kMaxSupportedStackDepth),
-        alloc_ddm_thread_id_(0),
-        allow_new_record_(true),
-        new_record_condition_("New allocation record condition", *Locks::alloc_tracker_lock_) {}
-
+  AllocRecordObjectMap() REQUIRES(Locks::alloc_tracker_lock_);
   ~AllocRecordObjectMap();
 
-  void Put(mirror::Object* obj, AllocRecord* record)
+  void Put(mirror::Object* obj, AllocRecord&& record)
       SHARED_REQUIRES(Locks::mutator_lock_)
       REQUIRES(Locks::alloc_tracker_lock_) {
     if (entries_.size() == alloc_record_max_) {
-      delete entries_.front().second;
       entries_.pop_front();
     }
-    entries_.emplace_back(GcRoot<mirror::Object>(obj), record);
+    entries_.push_back(EntryPair(GcRoot<mirror::Object>(obj), std::move(record)));
   }
 
   size_t Size() const SHARED_REQUIRES(Locks::alloc_tracker_lock_) {
@@ -313,12 +295,11 @@
   static constexpr size_t kDefaultNumRecentRecords = 64 * 1024 - 1;
   static constexpr size_t kDefaultAllocStackDepth = 16;
   static constexpr size_t kMaxSupportedStackDepth = 128;
-  size_t alloc_record_max_ GUARDED_BY(Locks::alloc_tracker_lock_);
-  size_t recent_record_max_ GUARDED_BY(Locks::alloc_tracker_lock_);
-  size_t max_stack_depth_ GUARDED_BY(Locks::alloc_tracker_lock_);
-  AllocRecordStackTrace scratch_trace_ GUARDED_BY(Locks::alloc_tracker_lock_);
-  pid_t alloc_ddm_thread_id_ GUARDED_BY(Locks::alloc_tracker_lock_);
-  bool allow_new_record_ GUARDED_BY(Locks::alloc_tracker_lock_);
+  size_t alloc_record_max_ GUARDED_BY(Locks::alloc_tracker_lock_) = kDefaultNumAllocRecords;
+  size_t recent_record_max_ GUARDED_BY(Locks::alloc_tracker_lock_) = kDefaultNumRecentRecords;
+  size_t max_stack_depth_ = kDefaultAllocStackDepth;
+  pid_t alloc_ddm_thread_id_  GUARDED_BY(Locks::alloc_tracker_lock_) = 0;
+  bool allow_new_record_ GUARDED_BY(Locks::alloc_tracker_lock_) = true;
   ConditionVariable new_record_condition_ GUARDED_BY(Locks::alloc_tracker_lock_);
   // see the comment in typedef of EntryList
   EntryList entries_ GUARDED_BY(Locks::alloc_tracker_lock_);
diff --git a/runtime/gc/heap-inl.h b/runtime/gc/heap-inl.h
index 59fd4a6..6aed61a 100644
--- a/runtime/gc/heap-inl.h
+++ b/runtime/gc/heap-inl.h
@@ -176,8 +176,10 @@
   }
   if (kInstrumented) {
     if (IsAllocTrackingEnabled()) {
-      // Use obj->GetClass() instead of klass, because PushOnAllocationStack() could move klass
-      AllocRecordObjectMap::RecordAllocation(self, obj, obj->GetClass(), bytes_allocated);
+      // allocation_records_ is not null since it never becomes null after allocation tracking is
+      // enabled.
+      DCHECK(allocation_records_ != nullptr);
+      allocation_records_->RecordAllocation(self, &obj, bytes_allocated);
     }
   } else {
     DCHECK(!IsAllocTrackingEnabled());
diff --git a/runtime/gc/heap.h b/runtime/gc/heap.h
index 2925591..fada1a2 100644
--- a/runtime/gc/heap.h
+++ b/runtime/gc/heap.h
@@ -1326,8 +1326,7 @@
 
   // Allocation tracking support
   Atomic<bool> alloc_tracking_enabled_;
-  std::unique_ptr<AllocRecordObjectMap> allocation_records_
-      GUARDED_BY(Locks::alloc_tracker_lock_);
+  std::unique_ptr<AllocRecordObjectMap> allocation_records_;
 
   // GC stress related data structures.
   Mutex* backtrace_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
diff --git a/runtime/hprof/hprof.cc b/runtime/hprof/hprof.cc
index bb35ec7..3885c60 100644
--- a/runtime/hprof/hprof.cc
+++ b/runtime/hprof/hprof.cc
@@ -828,7 +828,7 @@
         continue;
       }
       ++count;
-      const gc::AllocRecordStackTrace* trace = it->second->GetStackTrace();
+      const gc::AllocRecordStackTrace* trace = it->second.GetStackTrace();
 
       // Copy the pair into a real hash map to speed up look up.
       auto records_result = allocation_records_.emplace(obj, trace);