Count m(un)map for each stacktrace in MemoryRegionMap instead of HeapProfileTable.

third_party/tcmalloc/chromium/src/memory_region_map.cc

 /* Copyright (c) 2006, Google Inc.
  * All rights reserved.
  * 
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  * 
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 66 matching lines @@
 // to get memory, thus we are able to call LowLevelAlloc from
 // our mmap/sbrk hooks without causing a deadlock in it.
 // For the same reason of deadlock prevention the locking in MemoryRegionMap
 // itself is write-recursive which is an exception to Google's mutex usage.
 //
 // We still need to break the infinite cycle of mmap calling our hook,
 // which asks LowLevelAlloc for memory to record this mmap,
 // which (sometimes) causes mmap, which calls our hook, and so on.
 // We do this as follows: on a recursive call of MemoryRegionMap's
 // mmap/sbrk/mremap hook we record the data about the allocation in a
-// static fixed-sized stack (saved_regions), when the recursion unwinds
-// but before returning from the outer hook call we unwind this stack and
-// move the data from saved_regions to its permanent place in the RegionSet,
+// static fixed-sized stack (saved_regions and saved_buckets), when the
+// recursion unwinds but before returning from the outer hook call we unwind
+// this stack and move the data from saved_regions and saved_buckets to its
+// permanent place in the RegionSet and "bucket_table" respectively,
 // which can cause more allocations and mmap-s and recursion and unwinding,
 // but the whole process ends eventually due to the fact that for the small
 // allocations we are doing LowLevelAlloc reuses one mmap call and parcels out
 // the memory it created to satisfy several of our allocation requests.
 //
 
 // ========================================================================= //
 
 #include <config.h>
 
@@ skipping 40 matching lines @@
 int MemoryRegionMap::max_stack_depth_ = 0;
 MemoryRegionMap::RegionSet* MemoryRegionMap::regions_ = NULL;
 LowLevelAlloc::Arena* MemoryRegionMap::arena_ = NULL;
 SpinLock MemoryRegionMap::lock_(SpinLock::LINKER_INITIALIZED);
 SpinLock MemoryRegionMap::owner_lock_(  // ACQUIRED_AFTER(lock_)
     SpinLock::LINKER_INITIALIZED);
 int MemoryRegionMap::recursion_count_ = 0;  // GUARDED_BY(owner_lock_)
 pthread_t MemoryRegionMap::lock_owner_tid_;  // GUARDED_BY(owner_lock_)
 int64 MemoryRegionMap::map_size_ = 0;
 int64 MemoryRegionMap::unmap_size_ = 0;
+HeapProfileBucket** MemoryRegionMap::bucket_table_ = NULL;  // GUARDED_BY(lock_)
+int MemoryRegionMap::num_buckets_ = 0;  // GUARDED_BY(lock_)
+int MemoryRegionMap::saved_buckets_count_ = 0;  // GUARDED_BY(lock_)
+HeapProfileBucket MemoryRegionMap::saved_buckets_[20];  // GUARDED_BY(lock_)
+
+// GUARDED_BY(lock_)
+const void* MemoryRegionMap::saved_buckets_keys_[20][kMaxStackDepth];
 
 // ========================================================================= //
 
 // Simple hook into execution of global object constructors,
 // so that we do not call pthread_self() when it does not yet work.
 static bool libpthread_initialized = false;
 static bool initializer = (libpthread_initialized = true, true);
 
 static inline bool current_thread_is(pthread_t should_be) {
   // Before main() runs, there's only one thread, so we're always that thread
@@ skipping 15 matching lines @@
 // We use RegionSetRep with noop c-tor so that global construction
 // does not interfere.
 static MemoryRegionMap::RegionSetRep regions_rep;
 
 // ========================================================================= //
 
 // Has InsertRegionLocked been called recursively
 // (or rather should we *not* use regions_ to record a hooked mmap).
 static bool recursive_insert = false;
 
-void MemoryRegionMap::Init(int max_stack_depth) {
+void MemoryRegionMap::Init(int max_stack_depth, bool use_buckets) {
   RAW_VLOG(10, "MemoryRegionMap Init");
   RAW_CHECK(max_stack_depth >= 0, "");
   // Make sure we don't overflow the memory in region stacks:
   RAW_CHECK(max_stack_depth <= kMaxStackDepth,
             "need to increase kMaxStackDepth?");
   Lock();
   client_count_ += 1;
   max_stack_depth_ = max(max_stack_depth_, max_stack_depth);
   if (client_count_ > 1) {
     // not first client: already did initialization-proper
@@ skipping 11 matching lines @@
   // recursive_insert allows us to buffer info about these mmap calls.
   // Note that Init() can be (and is) sometimes called
   // already from within an mmap/sbrk hook.
   recursive_insert = true;
   arena_ = LowLevelAlloc::NewArena(0, LowLevelAlloc::DefaultArena());
   recursive_insert = false;
   HandleSavedRegionsLocked(&InsertRegionLocked);  // flush the buffered ones
     // Can't instead use HandleSavedRegionsLocked(&DoInsertRegionLocked) before
     // recursive_insert = false; as InsertRegionLocked will also construct
     // regions_ on demand for us.
+  if (use_buckets) {
+    const int table_bytes = kHashTableSize * sizeof(*bucket_table_);
+    recursive_insert = true;
+    bucket_table_ = static_cast<HeapProfileBucket**>(
+        MyAllocator::Allocate(table_bytes));
+    recursive_insert = false;
+    memset(bucket_table_, 0, table_bytes);
+    num_buckets_ = 0;
+  }
   Unlock();
   RAW_VLOG(10, "MemoryRegionMap Init done");
 }
 
 bool MemoryRegionMap::Shutdown() {
   RAW_VLOG(10, "MemoryRegionMap Shutdown");
   Lock();
   RAW_CHECK(client_count_ > 0, "");
   client_count_ -= 1;
   if (client_count_ != 0) {  // not last client; need not really shutdown
     Unlock();
     RAW_VLOG(10, "MemoryRegionMap Shutdown decrement done");
     return true;
   }
+  if (bucket_table_ != NULL) {
+    for (int i = 0; i < kHashTableSize; i++) {
+      for (HeapProfileBucket* curr = bucket_table_[i]; curr != 0; /**/) {
+        HeapProfileBucket* bucket = curr;
+        curr = curr->next;
+        MyAllocator::Free(bucket->stack, 0);
+        MyAllocator::Free(bucket, 0);
+      }
+    }
+    MyAllocator::Free(bucket_table_, 0);
+    num_buckets_ = 0;
+    bucket_table_ = NULL;
+  }
   RAW_CHECK(MallocHook::RemoveMmapHook(&MmapHook), "");
   RAW_CHECK(MallocHook::RemoveMremapHook(&MremapHook), "");
   RAW_CHECK(MallocHook::RemoveSbrkHook(&SbrkHook), "");
   RAW_CHECK(MallocHook::RemoveMunmapHook(&MunmapHook), "");
   if (regions_) regions_->~RegionSet();
   regions_ = NULL;
   bool deleted_arena = LowLevelAlloc::DeleteArena(arena_);
   if (deleted_arena) {
     arena_ = 0;
   } else {
     RAW_LOG(WARNING, "Can't delete LowLevelAlloc arena: it's being used");
   }
   Unlock();
   RAW_VLOG(10, "MemoryRegionMap Shutdown done");
   return deleted_arena;
 }
 
+bool MemoryRegionMap::IsRecordingLocked() {
+  RAW_CHECK(LockIsHeld(), "should be held (by this thread)");
+  return client_count_ > 0;
+}
+
 // Invariants (once libpthread_initialized is true):
 //   * While lock_ is not held, recursion_count_ is 0 (and
 //     lock_owner_tid_ is the previous owner, but we don't rely on
 //     that).
 //   * recursion_count_ and lock_owner_tid_ are only written while
 //     both lock_ and owner_lock_ are held. They may be read under
 //     just owner_lock_.
 //   * At entry and exit of Lock() and Unlock(), the current thread
 //     owns lock_ iff pthread_equal(lock_owner_tid_, pthread_self())
 //     && recursion_count_ > 0.
@@ skipping 71 matching lines @@
                 reinterpret_cast<void*>(region->start_addr),
                 reinterpret_cast<void*>(region->end_addr));
     const_cast<Region*>(region)->set_is_stack();  // now we know
       // cast is safe (set_is_stack does not change the set ordering key)
     *result = *region;  // create *result as an independent copy
   }
   Unlock();
   return region != NULL;
 }
 
+HeapProfileBucket* MemoryRegionMap::GetBucket(int depth,
+                                              const void* const key[]) {
+  RAW_CHECK(LockIsHeld(), "should be held (by this thread)");
+  // Make hash-value
+  uintptr_t hash = 0;
+  for (int i = 0; i < depth; i++) {
+    hash += reinterpret_cast<uintptr_t>(key[i]);
+    hash += hash << 10;
+    hash ^= hash >> 6;
+  }
+  hash += hash << 3;
+  hash ^= hash >> 11;
+
+  // Lookup stack trace in table
+  unsigned int hash_index = (static_cast<unsigned int>(hash)) % kHashTableSize;
+  for (HeapProfileBucket* bucket = bucket_table_[hash_index];
+       bucket != 0;
+       bucket = bucket->next) {
+    if ((bucket->hash == hash) && (bucket->depth == depth) &&
+        std::equal(key, key + depth, bucket->stack)) {
+      return bucket;
+    }
+  }
+
+  // Create new bucket
+  const size_t key_size = sizeof(key[0]) * depth;
+  HeapProfileBucket* bucket;
+  if (recursive_insert) {  // recursion: save in saved_buckets_
+    const void** key_copy = saved_buckets_keys_[saved_buckets_count_];
+    std::copy(key, key + depth, key_copy);
+    bucket = &saved_buckets_[saved_buckets_count_];
+    memset(bucket, 0, sizeof(*bucket));
+    ++saved_buckets_count_;
+    bucket->stack = key_copy;
+    bucket->next  = NULL;
+  } else {
+    recursive_insert = true;
+    const void** key_copy = static_cast<const void**>(
+        MyAllocator::Allocate(key_size));
+    recursive_insert = false;
+    std::copy(key, key + depth, key_copy);
+    recursive_insert = true;
+    bucket = static_cast<HeapProfileBucket*>(
+        MyAllocator::Allocate(sizeof(HeapProfileBucket)));
+    recursive_insert = false;
+    memset(bucket, 0, sizeof(*bucket));
+    bucket->stack = key_copy;
+    bucket->next  = bucket_table_[hash_index];
+  }
+  bucket->hash = hash;
+  bucket->depth = depth;
+  bucket_table_[hash_index] = bucket;
+  ++num_buckets_;
+  return bucket;
+}
+
 MemoryRegionMap::RegionIterator MemoryRegionMap::BeginRegionLocked() {
   RAW_CHECK(LockIsHeld(), "should be held (by this thread)");
   RAW_CHECK(regions_ != NULL, "");
   return regions_->begin();
 }
 
 MemoryRegionMap::RegionIterator MemoryRegionMap::EndRegionLocked() {
   RAW_CHECK(LockIsHeld(), "should be held (by this thread)");
   RAW_CHECK(regions_ != NULL, "");
   return regions_->end();
@@ skipping 48 matching lines @@
   while (saved_regions_count > 0) {
     // Making a local-var copy of the region argument to insert_func
     // including its stack (w/o doing any memory allocations) is important:
     // in many cases the memory in saved_regions
     // will get written-to during the (*insert_func)(r) call below.
     Region r = saved_regions[--saved_regions_count];
     (*insert_func)(r);
   }
 }
 
+void MemoryRegionMap::RestoreSavedBucketsLocked() {
+  RAW_CHECK(LockIsHeld(), "should be held (by this thread)");
+  while (saved_buckets_count_ > 0) {
+    HeapProfileBucket bucket = saved_buckets_[--saved_buckets_count_];
+    unsigned int hash_index =
+        static_cast<unsigned int>(bucket.hash) % kHashTableSize;
+    bool is_found = false;
+    for (HeapProfileBucket* curr = bucket_table_[hash_index];
+         curr != 0;
+         curr = curr->next) {
+      if ((curr->hash == bucket.hash) && (curr->depth == bucket.depth) &&
+          std::equal(bucket.stack, bucket.stack + bucket.depth, curr->stack)) {
+        curr->allocs += bucket.allocs;
+        curr->alloc_size += bucket.alloc_size;
+        curr->frees += bucket.frees;
+        curr->free_size += bucket.free_size;
+        is_found = true;
+        break;
+      }
+    }
+    if (is_found) continue;
+
+    const size_t key_size = sizeof(bucket.stack[0]) * bucket.depth;
+    const void** key_copy = static_cast<const void**>(
+        MyAllocator::Allocate(key_size));
+    std::copy(bucket.stack, bucket.stack + bucket.depth, key_copy);
+    HeapProfileBucket* new_bucket = static_cast<HeapProfileBucket*>(
+        MyAllocator::Allocate(sizeof(HeapProfileBucket)));
+    memset(new_bucket, 0, sizeof(*new_bucket));
+    new_bucket->hash = bucket.hash;
+    new_bucket->depth = bucket.depth;
+    new_bucket->stack = key_copy;
+    new_bucket->next = bucket_table_[hash_index];
+    bucket_table_[hash_index] = new_bucket;
+    ++num_buckets_;
+  }
+}
+
 inline void MemoryRegionMap::InsertRegionLocked(const Region& region) {
   RAW_CHECK(LockIsHeld(), "should be held (by this thread)");
   // We can be called recursively, because RegionSet constructor
   // and DoInsertRegionLocked() (called below) can call the allocator.
   // recursive_insert tells us if that's the case. When this happens,
   // region insertion information is recorded in saved_regions[],
   // and taken into account when the recursion unwinds.
   // Do the insert:
   if (recursive_insert) {  // recursion: save in saved_regions
     RAW_VLOG(12, "Saving recursive insert of region %p..%p from %p",
@@ skipping 44 matching lines @@
   RAW_VLOG(10, "New global region %p..%p from %p",
               reinterpret_cast<void*>(region.start_addr),
               reinterpret_cast<void*>(region.end_addr),
               reinterpret_cast<void*>(region.caller()));
   // Note: none of the above allocates memory.
   Lock();  // recursively lock
   map_size_ += size;
   InsertRegionLocked(region);
     // This will (eventually) allocate storage for and copy over the stack data
     // from region.call_stack_data_ that is pointed by region.call_stack().
+  if (bucket_table_ != NULL) {
+    HeapProfileBucket* b = GetBucket(depth, region.call_stack);
+    ++b->allocs;
+    b->alloc_size += size;
+    if (!recursive_insert) {
+      recursive_insert = true;
+      RestoreSavedBucketsLocked();
+      recursive_insert = false;
+    }
+  }
   Unlock();
 }
 
 void MemoryRegionMap::RecordRegionRemoval(const void* start, size_t size) {
   Lock();
   if (recursive_insert) {
     // First remove the removed region from saved_regions, if it's
     // there, to prevent overrunning saved_regions in recursive
     // map/unmap call sequences, and also from later inserting regions
     // which have already been unmapped.
     uintptr_t start_addr = reinterpret_cast<uintptr_t>(start);
     uintptr_t end_addr = start_addr + size;
     int put_pos = 0;
     int old_count = saved_regions_count;
     for (int i = 0; i < old_count; ++i, ++put_pos) {
       Region& r = saved_regions[i];
       if (r.start_addr == start_addr && r.end_addr == end_addr) {
         // An exact match, so it's safe to remove.
+        RecordRegionRemovalInBucket(r.call_stack_depth, r.call_stack, size);
         --saved_regions_count;
         --put_pos;
         RAW_VLOG(10, ("Insta-Removing saved region %p..%p; "
                      "now have %d saved regions"),
                  reinterpret_cast<void*>(start_addr),
                  reinterpret_cast<void*>(end_addr),
                  saved_regions_count);
       } else {
         if (put_pos < i) {
           saved_regions[put_pos] = saved_regions[i];
@@ skipping 24 matching lines @@
        region != regions_->end()  &&  region->start_addr < end_addr;
        /*noop*/) {
     RAW_VLOG(13, "Looking at region %p..%p",
                 reinterpret_cast<void*>(region->start_addr),
                 reinterpret_cast<void*>(region->end_addr));
     if (start_addr <= region->start_addr  &&
         region->end_addr <= end_addr) {  // full deletion
       RAW_VLOG(12, "Deleting region %p..%p",
                   reinterpret_cast<void*>(region->start_addr),
                   reinterpret_cast<void*>(region->end_addr));
+      RecordRegionRemovalInBucket(region->call_stack_depth, region->call_stack,
+                                  region->end_addr - region->start_addr);
       RegionSet::iterator d = region;
       ++region;
       regions_->erase(d);
       continue;
     } else if (region->start_addr < start_addr  &&
                end_addr < region->end_addr) {  // cutting-out split
       RAW_VLOG(12, "Splitting region %p..%p in two",
                   reinterpret_cast<void*>(region->start_addr),
                   reinterpret_cast<void*>(region->end_addr));
+      RecordRegionRemovalInBucket(region->call_stack_depth, region->call_stack,
+                                  end_addr - start_addr);
       // Make another region for the start portion:
       // The new region has to be the start portion because we can't
       // just modify region->end_addr as it's the sorting key.
       Region r = *region;
       r.set_end_addr(start_addr);
       InsertRegionLocked(r);
       // cut *region from start:
       const_cast<Region&>(*region).set_start_addr(end_addr);
     } else if (end_addr > region->start_addr  &&
                start_addr <= region->start_addr) {  // cut from start
       RAW_VLOG(12, "Start-chopping region %p..%p",
                   reinterpret_cast<void*>(region->start_addr),
                   reinterpret_cast<void*>(region->end_addr));
+      RecordRegionRemovalInBucket(region->call_stack_depth, region->call_stack,
+                                  end_addr - region->start_addr);
       const_cast<Region&>(*region).set_start_addr(end_addr);
     } else if (start_addr > region->start_addr  &&
                start_addr < region->end_addr) {  // cut from end
       RAW_VLOG(12, "End-chopping region %p..%p",
                   reinterpret_cast<void*>(region->start_addr),
                   reinterpret_cast<void*>(region->end_addr));
+      RecordRegionRemovalInBucket(region->call_stack_depth, region->call_stack,
+                                  region->end_addr - start_addr);
       // Can't just modify region->end_addr (it's the sorting key):
       Region r = *region;
       r.set_end_addr(start_addr);
       RegionSet::iterator d = region;
       ++region;
       // It's safe to erase before inserting since r is independent of *d:
       // r contains an own copy of the call stack:
       regions_->erase(d);
       InsertRegionLocked(r);
       continue;
     }
     ++region;
   }
   RAW_VLOG(12, "Removed region %p..%p; have %"PRIuS" regions",
               reinterpret_cast<void*>(start_addr),
               reinterpret_cast<void*>(end_addr),
               regions_->size());
   if (VLOG_IS_ON(12))  LogAllLocked();
   unmap_size_ += size;
   Unlock();
 }
 
+void MemoryRegionMap::RecordRegionRemovalInBucket(int depth,
+                                                  const void* const stack[],
+                                                  size_t size) {
+  RAW_CHECK(LockIsHeld(), "should be held (by this thread)");
+  if (bucket_table_ == NULL) return;
+  HeapProfileBucket* b = GetBucket(depth, stack);
+  ++b->frees;
+  b->free_size += size;
+}
+
 void MemoryRegionMap::MmapHook(const void* result,
                                const void* start, size_t size,
                                int prot, int flags,
                                int fd, off_t offset) {
   // TODO(maxim): replace all 0x%"PRIxS" by %p when RAW_VLOG uses a safe
   // snprintf reimplementation that does not malloc to pretty-print NULL
   RAW_VLOG(10, "MMap = 0x%"PRIxPTR" of %"PRIuS" at %"PRIu64" "
               "prot %d flags %d fd %d offs %"PRId64,
               reinterpret_cast<uintptr_t>(result), size,
               reinterpret_cast<uint64>(start), prot, flags, fd,
@@ skipping 50 matching lines @@
        r != regions_->end(); ++r) {
     RAW_LOG(INFO, "Memory region 0x%"PRIxPTR"..0x%"PRIxPTR" "
                   "from 0x%"PRIxPTR" stack=%d",
                   r->start_addr, r->end_addr, r->caller(), r->is_stack);
     RAW_CHECK(previous < r->end_addr, "wow, we messed up the set order");
       // this must be caused by uncontrolled recursive operations on regions_
     previous = r->end_addr;
   }
   RAW_LOG(INFO, "End of regions list");
 }