GC data structures allocation tracking

Adds a new stl compatible allocator that is used in most GC data
structures. When the data structures allocate and free memory, it
lets the heap know of how much memory was allocated or freed. Using
this info, we dump the approximated stl data structures memory usage
when a sigquit occurs.

The allocation tracking can be disabled with a compile time boolean
flag to remove performance impact.

Change-Id: Idddb6713169e07be913bceeb50f305c8573e4392

14 files changed, 195 insertions, 24 deletions

diff --git a/runtime/Android.mk b/runtime/Android.mk
index ae62d36e0c..4638e78158 100644
--- a/runtime/Android.mk
+++ b/runtime/Android.mk
@@ -47,6 +47,7 @@ LIBART_COMMON_SRC_FILES := \
 	file_output_stream.cc \
 	gc/allocator/dlmalloc.cc \
 	gc/accounting/card_table.cc \
+	gc/accounting/gc_allocator.cc \
 	gc/accounting/heap_bitmap.cc \
 	gc/accounting/mod_union_table.cc \
 	gc/accounting/space_bitmap.cc \
diff --git a/runtime/gc/accounting/gc_allocator.cc b/runtime/gc/accounting/gc_allocator.cc
new file mode 100644
index 0000000000..aff50df7cf
--- /dev/null
+++ b/runtime/gc/accounting/gc_allocator.cc
@@ -0,0 +1,33 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "gc_allocator.h"
+#include "gc/heap.h"
+#include "runtime.h"
+
+namespace art {
+namespace gc {
+namespace accounting {
+  void RegisterGCAllocation(size_t bytes) {
+    Runtime::Current()->GetHeap()->RegisterGCAllocation(bytes);
+  }
+
+  void RegisterGCDeAllocation(size_t bytes) {
+    Runtime::Current()->GetHeap()->RegisterGCDeAllocation(bytes);
+  }
+}
+}
+}
diff --git a/runtime/gc/accounting/gc_allocator.h b/runtime/gc/accounting/gc_allocator.h
new file mode 100644
index 0000000000..12e16b5558
--- /dev/null
+++ b/runtime/gc/accounting/gc_allocator.h
@@ -0,0 +1,87 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_GC_ACCOUNTING_GC_ALLOCATOR_H_
+#define ART_RUNTIME_GC_ACCOUNTING_GC_ALLOCATOR_H_
+
+#include "gc/allocator/dlmalloc.h"
+#include "utils.h"
+
+#include <cstdlib>
+#include <limits>
+#include <memory>
+
+namespace art {
+namespace gc {
+namespace accounting {
+  void RegisterGCAllocation(size_t bytes);
+  void RegisterGCDeAllocation(size_t bytes);
+
+  static const bool kMeasureGCMemoryOverhead = false;
+
+  template <typename T>
+  class GCAllocatorImpl : public std::allocator<T> {
+  public:
+    typedef typename std::allocator<T>::value_type value_type;
+    typedef typename std::allocator<T>::size_type size_type;
+    typedef typename std::allocator<T>::difference_type difference_type;
+    typedef typename std::allocator<T>::pointer pointer;
+    typedef typename std::allocator<T>::const_pointer const_pointer;
+    typedef typename std::allocator<T>::reference reference;
+    typedef typename std::allocator<T>::const_reference const_reference;
+
+    // Used internally by STL data structures.
+    template <class U>
+    GCAllocatorImpl(const GCAllocatorImpl<U>& alloc) throw() {
+
+    }
+
+    // Used internally by STL data structures.
+    GCAllocatorImpl() throw() {
+
+    }
+
+    // Enables an allocator for objects of one type to allocate storage for objects of another type.
+    // Used internally by STL data structures.
+    template <class U>
+    struct rebind {
+        typedef GCAllocatorImpl<U> other;
+    };
+
+    pointer allocate(size_type n, const_pointer hint = 0) {
+      RegisterGCAllocation(n * sizeof(T));
+      return reinterpret_cast<pointer>(malloc(n * sizeof(T)));
+    }
+
+    template <typename PT>
+    void deallocate(PT p, size_type n) {
+      RegisterGCDeAllocation(n * sizeof(T));
+      free(p);
+    }
+  };
+
+  // C++ doesn't allow template typedefs. This is a workaround template typedef which is
+  // GCAllocatorImpl<T> if kMeasureGCMemoryOverhead is true, std::allocator<T> otherwise.
+  template <typename T>
+  class GCAllocator : public TypeStaticIf<kMeasureGCMemoryOverhead,
+                                          GCAllocatorImpl<T>,
+                                          std::allocator<T> >::value {
+  };
+}
+}
+}
+
+#endif  // ART_RUNTIME_GC_ACCOUNTING_GC_ALLOCATOR_H_
diff --git a/runtime/gc/accounting/heap_bitmap-inl.h b/runtime/gc/accounting/heap_bitmap-inl.h
index 5edea95dc3..f6cf2b53ea 100644
--- a/runtime/gc/accounting/heap_bitmap-inl.h
+++ b/runtime/gc/accounting/heap_bitmap-inl.h
@@ -26,14 +26,14 @@ namespace accounting {
 template <typename Visitor>
 inline void HeapBitmap::Visit(const Visitor& visitor) {
   // TODO: C++0x auto
-  typedef std::vector<SpaceBitmap*>::iterator It;
+  typedef SpaceBitmapVector::iterator It;
   for (It it = continuous_space_bitmaps_.begin(), end = continuous_space_bitmaps_.end();
       it != end; ++it) {
     SpaceBitmap* bitmap = *it;
     bitmap->VisitMarkedRange(bitmap->HeapBegin(), bitmap->HeapLimit(), visitor, VoidFunctor());
   }
   // TODO: C++0x auto
-  typedef std::vector<SpaceSetMap*>::iterator It2;
+  typedef SpaceSetMapVector::iterator It2;
   DCHECK(discontinuous_space_sets_.begin() !=  discontinuous_space_sets_.end());
   for (It2 it = discontinuous_space_sets_.begin(), end = discontinuous_space_sets_.end();
       it != end; ++it) {
diff --git a/runtime/gc/accounting/heap_bitmap.cc b/runtime/gc/accounting/heap_bitmap.cc
index 1bdc9783fa..046290513d 100644
--- a/runtime/gc/accounting/heap_bitmap.cc
+++ b/runtime/gc/accounting/heap_bitmap.cc
@@ -24,7 +24,7 @@ namespace accounting {
 
 void HeapBitmap::ReplaceBitmap(SpaceBitmap* old_bitmap, SpaceBitmap* new_bitmap) {
   // TODO: C++0x auto
-  typedef std::vector<SpaceBitmap*>::iterator It;
+  typedef SpaceBitmapVector::iterator It;
   for (It it = continuous_space_bitmaps_.begin(), end = continuous_space_bitmaps_.end();
       it != end; ++it) {
     if (*it == old_bitmap) {
@@ -37,7 +37,7 @@ void HeapBitmap::ReplaceBitmap(SpaceBitmap* old_bitmap, SpaceBitmap* new_bitmap)
 
 void HeapBitmap::ReplaceObjectSet(SpaceSetMap* old_set, SpaceSetMap* new_set) {
   // TODO: C++0x auto
-  typedef std::vector<SpaceSetMap*>::iterator It;
+  typedef SpaceSetMapVector::iterator It;
   for (It it = discontinuous_space_sets_.begin(), end = discontinuous_space_sets_.end();
       it != end; ++it) {
     if (*it == old_set) {
@@ -52,7 +52,7 @@ void HeapBitmap::AddContinuousSpaceBitmap(accounting::SpaceBitmap* bitmap) {
   DCHECK(bitmap != NULL);
 
   // Check for interval overlap.
-  typedef std::vector<SpaceBitmap*>::iterator It;
+  typedef SpaceBitmapVector::iterator It;
   for (It it = continuous_space_bitmaps_.begin(), end = continuous_space_bitmaps_.end();
       it != end; ++it) {
     SpaceBitmap* bitmap = *it;
@@ -71,14 +71,14 @@ void HeapBitmap::AddDiscontinuousObjectSet(SpaceSetMap* set) {
 
 void HeapBitmap::Walk(SpaceBitmap::Callback* callback, void* arg) {
   // TODO: C++0x auto
-  typedef std::vector<SpaceBitmap*>::iterator It;
+  typedef SpaceBitmapVector::iterator It;
   for (It it = continuous_space_bitmaps_.begin(), end = continuous_space_bitmaps_.end();
       it != end; ++it) {
     SpaceBitmap* bitmap = *it;
     bitmap->Walk(callback, arg);
   }
   // TODO: C++0x auto
-  typedef std::vector<SpaceSetMap*>::iterator It2;
+  typedef SpaceSetMapVector::iterator It2;
   DCHECK(discontinuous_space_sets_.begin() !=  discontinuous_space_sets_.end());
   for (It2 it = discontinuous_space_sets_.begin(), end = discontinuous_space_sets_.end();
       it != end; ++it) {
diff --git a/runtime/gc/accounting/heap_bitmap.h b/runtime/gc/accounting/heap_bitmap.h
index 1710579619..ada976fff6 100644
--- a/runtime/gc/accounting/heap_bitmap.h
+++ b/runtime/gc/accounting/heap_bitmap.h
@@ -18,6 +18,7 @@
 #define ART_RUNTIME_GC_ACCOUNTING_HEAP_BITMAP_H_
 
 #include "base/logging.h"
+#include "gc_allocator.h"
 #include "locks.h"
 #include "space_bitmap.h"
 
@@ -30,6 +31,9 @@ namespace accounting {
 
 class HeapBitmap {
  public:
+  typedef std::vector<SpaceBitmap*, GCAllocator<SpaceBitmap*> > SpaceBitmapVector;
+  typedef std::vector<SpaceSetMap*, GCAllocator<SpaceSetMap*> > SpaceSetMapVector;
+
   bool Test(const mirror::Object* obj) SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) {
     SpaceBitmap* bitmap = GetContinuousSpaceBitmap(obj);
     if (LIKELY(bitmap != NULL)) {
@@ -63,7 +67,7 @@ class HeapBitmap {
 
   SpaceBitmap* GetContinuousSpaceBitmap(const mirror::Object* obj) {
     // TODO: C++0x auto
-    typedef std::vector<SpaceBitmap*>::iterator It;
+    typedef SpaceBitmapVector::iterator It;
     for (It it = continuous_space_bitmaps_.begin(), end = continuous_space_bitmaps_.end();
         it != end; ++it) {
       SpaceBitmap* bitmap = *it;
@@ -76,7 +80,7 @@ class HeapBitmap {
 
   SpaceSetMap* GetDiscontinuousSpaceObjectSet(const mirror::Object* obj) {
     // TODO: C++0x auto
-    typedef std::vector<SpaceSetMap*>::iterator It;
+    typedef SpaceSetMapVector::iterator It;
     for (It it = discontinuous_space_sets_.begin(), end = discontinuous_space_sets_.end();
         it != end; ++it) {
       SpaceSetMap* set = *it;
@@ -112,10 +116,10 @@ class HeapBitmap {
   void AddDiscontinuousObjectSet(SpaceSetMap* set);
 
   // Bitmaps covering continuous spaces.
-  std::vector<SpaceBitmap*> continuous_space_bitmaps_;
+  SpaceBitmapVector continuous_space_bitmaps_;
 
   // Sets covering discontinuous spaces.
-  std::vector<SpaceSetMap*> discontinuous_space_sets_;
+  SpaceSetMapVector discontinuous_space_sets_;
 
   friend class art::gc::Heap;
 };
diff --git a/runtime/gc/accounting/mod_union_table.cc b/runtime/gc/accounting/mod_union_table.cc
index b33cbceba1..718dcf0369 100644
--- a/runtime/gc/accounting/mod_union_table.cc
+++ b/runtime/gc/accounting/mod_union_table.cc
@@ -86,7 +86,7 @@ class ModUnionVisitor {
 
 class ModUnionClearCardSetVisitor {
  public:
-  explicit ModUnionClearCardSetVisitor(std::set<byte*>* const cleared_cards)
+  explicit ModUnionClearCardSetVisitor(ModUnionTable::CardSet* const cleared_cards)
     : cleared_cards_(cleared_cards) {
   }
 
@@ -97,7 +97,7 @@ class ModUnionClearCardSetVisitor {
   }
 
  private:
-  std::set<byte*>* const cleared_cards_;
+  ModUnionTable::CardSet* const cleared_cards_;
 };
 
 class ModUnionClearCardVisitor {
diff --git a/runtime/gc/accounting/mod_union_table.h b/runtime/gc/accounting/mod_union_table.h
index d46281c4c1..eb7a754d24 100644
--- a/runtime/gc/accounting/mod_union_table.h
+++ b/runtime/gc/accounting/mod_union_table.h
@@ -17,6 +17,7 @@
 #ifndef ART_RUNTIME_GC_ACCOUNTING_MOD_UNION_TABLE_H_
 #define ART_RUNTIME_GC_ACCOUNTING_MOD_UNION_TABLE_H_
 
+#include "gc_allocator.h"
 #include "globals.h"
 #include "safe_map.h"
 
@@ -49,6 +50,8 @@ class HeapBitmap;
 // cleared between GC phases, reducing the number of dirty cards that need to be scanned.
 class ModUnionTable {
  public:
+  typedef std::set<byte*, std::less<byte*>, GCAllocator<byte*> > CardSet;
+
   explicit ModUnionTable(Heap* heap) : heap_(heap) {}
 
   virtual ~ModUnionTable() {}
@@ -111,10 +114,11 @@ class ModUnionTableReferenceCache : public ModUnionTable {
 
  protected:
   // Cleared card array, used to update the mod-union table.
-  std::set<byte*> cleared_cards_;
+  ModUnionTable::CardSet cleared_cards_;
 
   // Maps from dirty cards to their corresponding alloc space references.
-  SafeMap<const byte*, std::vector<const mirror::Object*> > references_;
+  SafeMap<const byte*, std::vector<const mirror::Object*>, std::less<const byte*>,
+    GCAllocator<std::pair<const byte*, std::vector<const mirror::Object*> > > > references_;
 };
 
 // Card caching implementation. Keeps track of which cards we cleared and only this information.
@@ -141,7 +145,7 @@ class ModUnionTableCardCache : public ModUnionTable {
 
  protected:
   // Cleared card array, used to update the mod-union table.
-  std::set<byte*> cleared_cards_;
+  CardSet cleared_cards_;
 };
 
 }  // namespace accounting
diff --git a/runtime/gc/accounting/space_bitmap.h b/runtime/gc/accounting/space_bitmap.h
index 77f93a266c..674c2621a0 100644
--- a/runtime/gc/accounting/space_bitmap.h
+++ b/runtime/gc/accounting/space_bitmap.h
@@ -18,6 +18,7 @@
 #define ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_H_
 
 #include "locks.h"
+#include "gc_allocator.h"
 #include "globals.h"
 #include "mem_map.h"
 #include "UniquePtr.h"
@@ -205,7 +206,9 @@ class SpaceBitmap {
 // Like a bitmap except it keeps track of objects using sets.
 class SpaceSetMap {
  public:
-  typedef std::set<const mirror::Object*> Objects;
+  typedef std::set<
+      const mirror::Object*, std::less<const mirror::Object*>,
+      GCAllocator<const mirror::Object*> > Objects;
 
   bool IsEmpty() const {
     return contained_.empty();
diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc
index b6cef58fa2..edc5529eec 100644
--- a/runtime/gc/heap.cc
+++ b/runtime/gc/heap.cc
@@ -90,6 +90,7 @@ Heap::Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max
       num_bytes_allocated_(0),
       native_bytes_allocated_(0),
       process_state_(PROCESS_STATE_TOP),
+      gc_memory_overhead_(0),
       verify_missing_card_marks_(false),
       verify_system_weaks_(false),
       verify_pre_gc_heap_(false),
@@ -177,7 +178,7 @@ Heap::Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max
   card_table_.reset(accounting::CardTable::Create(heap_begin, heap_capacity));
   CHECK(card_table_.get() != NULL) << "Failed to create card table";
 
-  image_mod_union_table_.reset(new accounting::ModUnionTableToZygoteAllocspace(this));
+  image_mod_union_table_.reset(new accounting::ModUnionTableCardCache(this));
   CHECK(image_mod_union_table_.get() != NULL) << "Failed to create image mod-union table";
 
   zygote_mod_union_table_.reset(new accounting::ModUnionTableCardCache(this));
@@ -273,6 +274,18 @@ void Heap::AddContinuousSpace(space::ContinuousSpace* space) {
   }
 }
 
+void Heap::RegisterGCAllocation(size_t bytes) {
+  if (this != NULL) {
+    gc_memory_overhead_.fetch_add(bytes);
+  }
+}
+
+void Heap::RegisterGCDeAllocation(size_t bytes) {
+  if (this != NULL) {
+    gc_memory_overhead_.fetch_sub(bytes);
+  }
+}
+
 void Heap::AddDiscontinuousSpace(space::DiscontinuousSpace* space) {
   WriterMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_);
   DCHECK(space != NULL);
@@ -333,6 +346,7 @@ void Heap::DumpGcPerformanceInfo(std::ostream& os) {
   }
   os << "Total mutator paused time: " << PrettyDuration(total_paused_time) << "\n";
   os << "Total time waiting for GC to complete: " << PrettyDuration(total_wait_time_) << "\n";
+  os << "Approximate GC data structures memory overhead: " << gc_memory_overhead_;
 }
 
 Heap::~Heap() {
@@ -1128,6 +1142,7 @@ collector::GcType Heap::CollectGarbageInternal(collector::GcType gc_type, GcCaus
     // Wake anyone who may have been waiting for the GC to complete.
     gc_complete_cond_->Broadcast(self);
   }
+
   // Inform DDMS that a GC completed.
   ATRACE_END();
   Dbg::GcDidFinish();
diff --git a/runtime/gc/heap.h b/runtime/gc/heap.h
index 4a043a7427..853db9324e 100644
--- a/runtime/gc/heap.h
+++ b/runtime/gc/heap.h
@@ -24,6 +24,7 @@
 #include "atomic_integer.h"
 #include "base/timing_logger.h"
 #include "gc/accounting/atomic_stack.h"
+#include "gc/accounting/gc_allocator.h"
 #include "gc/accounting/card_table.h"
 #include "gc/collector/gc_type.h"
 #include "globals.h"
@@ -207,6 +208,10 @@ class Heap {
     return target_utilization_;
   }
 
+  // Data structure memory usage tracking.
+  void RegisterGCAllocation(size_t bytes);
+  void RegisterGCDeAllocation(size_t bytes);
+
   // Set target ideal heap utilization ratio, implements
   // dalvik.system.VMRuntime.setTargetHeapUtilization.
   void SetTargetHeapUtilization(float target);
@@ -556,6 +561,9 @@ class Heap {
   // Current process state, updated by activity manager.
   ProcessState process_state_;
 
+  // Data structure GC overhead.
+  AtomicInteger gc_memory_overhead_;
+
   // Heap verification flags.
   const bool verify_missing_card_marks_;
   const bool verify_system_weaks_;
diff --git a/runtime/gc/space/large_object_space.h b/runtime/gc/space/large_object_space.h
index 09c55ec566..8cd50880db 100644
--- a/runtime/gc/space/large_object_space.h
+++ b/runtime/gc/space/large_object_space.h
@@ -17,7 +17,7 @@
 #ifndef ART_RUNTIME_GC_SPACE_LARGE_OBJECT_SPACE_H_
 #define ART_RUNTIME_GC_SPACE_LARGE_OBJECT_SPACE_H_
 
-
+#include "gc/accounting/gc_allocator.h"
 #include "dlmalloc_space.h"
 #include "safe_map.h"
 #include "space.h"
@@ -95,8 +95,10 @@ class LargeObjectMapSpace : public LargeObjectSpace {
 
   // Used to ensure mutual exclusion when the allocation spaces data structures are being modified.
   mutable Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
-  std::vector<mirror::Object*> large_objects_ GUARDED_BY(lock_);
-  typedef SafeMap<mirror::Object*, MemMap*> MemMaps;
+  std::vector<mirror::Object*,
+      accounting::GCAllocator<mirror::Object*> > large_objects_ GUARDED_BY(lock_);
+  typedef SafeMap<mirror::Object*, MemMap*, std::less<mirror::Object*>,
+      accounting::GCAllocator<std::pair<const mirror::Object*, MemMap*> > > MemMaps;
   MemMaps mem_maps_ GUARDED_BY(lock_);
 };
 
diff --git a/runtime/safe_map.h b/runtime/safe_map.h
index dcc172de01..4b5202ab5c 100644
--- a/runtime/safe_map.h
+++ b/runtime/safe_map.h
@@ -18,6 +18,7 @@
 #define ART_RUNTIME_SAFE_MAP_H_
 
 #include <map>
+#include <memory>
 
 #include "base/logging.h"
 
@@ -25,10 +26,11 @@ namespace art {
 
 // Equivalent to std::map, but without operator[] and its bug-prone semantics (in particular,
 // the implicit insertion of a default-constructed value on failed lookups).
-template <typename K, typename V, typename Comparator = std::less<K> >
+template <typename K, typename V, typename Comparator = std::less<K>,
+          typename Allocator = std::allocator<std::pair<const K, V> > >
 class SafeMap {
  private:
-  typedef SafeMap<K, V, Comparator> Self;
+  typedef SafeMap<K, V, Comparator, Allocator> Self;
 
  public:
   typedef typename ::std::map<K, V, Comparator>::iterator iterator;
@@ -87,7 +89,7 @@ class SafeMap {
   }
 
  private:
-  ::std::map<K, V, Comparator> map_;
+  ::std::map<K, V, Comparator, Allocator> map_;
 };
 
 template <typename K, typename V, typename Comparator>
diff --git a/runtime/utils.h b/runtime/utils.h
index 72597f5ea4..1c45048c13 100644
--- a/runtime/utils.h
+++ b/runtime/utils.h
@@ -107,6 +107,18 @@ static inline uint32_t High32Bits(uint64_t value) {
   return static_cast<uint32_t>(value >> 32);
 }
 
+// A static if which determines whether to return type A or B based on the condition boolean.
+template <const bool condition, typename A, typename B>
+struct TypeStaticIf {
+  typedef A value;
+};
+
+// Specialization to handle the false case.
+template <typename A, typename B>
+struct TypeStaticIf<false, A,  B> {
+  typedef B value;
+};
+
 template<typename T>
 static inline T RoundDown(T x, int n) {
   CHECK(IsPowerOfTwo(n));