Add native memory accounting through custom allocator.

Added a custom allocator that lets you pass in a special tag which
specifices where the allocation came from. This is used when
dumping. The performance overhead is low since each allocation only
does a atomic add/sub for each allocation/free.

The measurements are dumped to traces.txt during SIGQUIT.

Example output:
I/art     (27274): AllocatorTagHeap active=120 max=120 total=168
I/art     (27274): AllocatorTagMonitorList active=1572 max=6240 total=11724
I/art     (27274): AllocatorTagClassTable active=185208 max=185208 total=268608
I/art     (27274): AllocatorTagInternTable active=430368 max=430368 total=436080
I/art     (27274): AllocatorTagMaps active=5616 max=6168 total=34392
I/art     (27274): AllocatorTagLOS active=1024 max=1536 total=2044
I/art     (27274): AllocatorTagSafeMap active=0 max=51936 total=533688
I/art     (27274): AllocatorTagLOSMaps active=144 max=1248 total=5760
I/art     (27274): AllocatorTagReferenceTable active=10944 max=11840 total=19136
I/art     (27274): AllocatorTagHeapBitmap active=32 max=40 total=56
I/art     (27274): AllocatorTagHeapBitmapLOS active=8 max=8 total=8
I/art     (27274): AllocatorTagVerifier active=0 max=18844 total=1073156
I/art     (27274): AllocatorTagModUnionCardSet active=5300 max=5920 total=56020
I/art     (27274): AllocatorTagModUnionReferenceArray active=24864 max=24864 total=24864
I/art     (27274): AllocatorTagJNILibrarires active=320 max=320 total=320
I/art     (27274): AllocatorTagOatFile active=1400 max=1400 total=5852

Change-Id: Ibb470ef2e9c9a24563bb46422d46a55799704d82

(cherry picked from commit 5369c40f75fdcb1be7a7c06db212ce965c83a164)

1 files changed, 113 insertions, 0 deletions

diff --git a/runtime/base/allocator.h b/runtime/base/allocator.h
index 917bf0b..a7adb02 100644
--- a/runtime/base/allocator.h
+++ b/runtime/base/allocator.h
@@ -17,10 +17,17 @@
 #ifndef ART_RUNTIME_BASE_ALLOCATOR_H_
 #define ART_RUNTIME_BASE_ALLOCATOR_H_
 
+#include <map>
+
+#include "atomic.h"
 #include "base/macros.h"
+#include "base/mutex.h"
+#include "utils.h"
 
 namespace art {
 
+static constexpr bool kEnableTrackingAllocator = false;
+
 class Allocator {
  public:
   static Allocator* GetMallocAllocator();
@@ -36,6 +43,112 @@ class Allocator {
   DISALLOW_COPY_AND_ASSIGN(Allocator);
 };
 
+// Used by TrackedAllocators.
+enum AllocatorTag {
+  kAllocatorTagHeap,
+  kAllocatorTagMonitorList,
+  kAllocatorTagClassTable,
+  kAllocatorTagInternTable,
+  kAllocatorTagMaps,
+  kAllocatorTagLOS,
+  kAllocatorTagSafeMap,
+  kAllocatorTagLOSMaps,
+  kAllocatorTagReferenceTable,
+  kAllocatorTagHeapBitmap,
+  kAllocatorTagHeapBitmapLOS,
+  kAllocatorTagMonitorPool,
+  kAllocatorTagLOSFreeList,
+  kAllocatorTagVerifier,
+  kAllocatorTagRememberedSet,
+  kAllocatorTagModUnionCardSet,
+  kAllocatorTagModUnionReferenceArray,
+  kAllocatorTagJNILibrarires,
+  kAllocatorTagCompileTimeClassPath,
+  kAllocatorTagOatFile,
+  kAllocatorTagDexFileVerifier,
+  kAllocatorTagCount,  // Must always be last element.
+};
+std::ostream& operator<<(std::ostream& os, const AllocatorTag& tag);
+
+class TrackedAllocators {
+ public:
+  static bool Add(uint32_t tag, AtomicInteger* bytes_used);
+  static void Dump(std::ostream& os);
+  static void RegisterAllocation(AllocatorTag tag, uint64_t bytes) {
+    total_bytes_used_[tag].FetchAndAddSequentiallyConsistent(bytes);
+    uint64_t new_bytes = bytes_used_[tag].FetchAndAddSequentiallyConsistent(bytes) + bytes;
+    max_bytes_used_[tag].StoreRelaxed(std::max(max_bytes_used_[tag].LoadRelaxed(), new_bytes));
+  }
+  static void RegisterFree(AllocatorTag tag, uint64_t bytes) {
+    bytes_used_[tag].FetchAndSubSequentiallyConsistent(bytes);
+  }
+
+ private:
+  static Atomic<uint64_t> bytes_used_[kAllocatorTagCount];
+  static Atomic<uint64_t> max_bytes_used_[kAllocatorTagCount];
+  static Atomic<uint64_t> total_bytes_used_[kAllocatorTagCount];
+};
+
+// Tracking allocator, tracks how much memory is used.
+template<class T, AllocatorTag kTag>
+class TrackingAllocatorImpl {
+ 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>
+  TrackingAllocatorImpl(const TrackingAllocatorImpl<U, kTag>& alloc) throw() {
+  }
+
+  // Used internally by STL data structures.
+  TrackingAllocatorImpl() throw() {
+    COMPILE_ASSERT(kTag < kAllocatorTagCount, must_be_less_than_count);
+  }
+
+  // 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 TrackingAllocatorImpl<U, kTag> other;
+  };
+
+  pointer allocate(size_type n, const_pointer hint = 0) {
+    const size_t size = n * sizeof(T);
+    TrackedAllocators::RegisterAllocation(GetTag(), size);
+    return reinterpret_cast<pointer>(malloc(size));
+  }
+
+  template <typename PT>
+  void deallocate(PT p, size_type n) {
+    const size_t size = n * sizeof(T);
+    TrackedAllocators::RegisterFree(GetTag(), size);
+    free(p);
+  }
+
+  static AllocatorTag GetTag() {
+    return kTag;
+  }
+};
+
+template<class T, AllocatorTag kTag>
+// C++ doesn't allow template typedefs. This is a workaround template typedef which is
+// TrackingAllocatorImpl<T> if kEnableTrackingAllocator is true, std::allocator<T> otherwise.
+class TrackingAllocator : public TypeStaticIf<kEnableTrackingAllocator,
+                                              TrackingAllocatorImpl<T, kTag>,
+                                              std::allocator<T>>::type {
+};
+
+template<class Key, class T, AllocatorTag kTag, class Compare = std::less<Key>>
+class AllocationTrackingMultiMap : public std::multimap<
+    Key, T, Compare, TrackingAllocator<std::pair<Key, T>, kTag>> {
+};
+
 }  // namespace art
 
 #endif  // ART_RUNTIME_BASE_ALLOCATOR_H_