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;
+int MemoryRegionMap::num_buckets_ = 0;
+int MemoryRegionMap::saved_buckets_count_ = 0;

[willchan no longer on Chromium, 2013/03/13 21:58:48]

Are these variables guarded by any locks? Should we be using the GUARDED_BY
annotation? I think that's common in google3.

[Dai Mikurube (NOT FULLTIME), 2013/03/14 09:33:47]

Yes, they should be accessed between Lock() and Unlock() (the lock variable is
MemoryRegionMap::lock_).

I was not sure of usage of GUARDED_BY in the OSS tcmalloc.  It's defined in
base/thread_annotations.h, but used only in profile-handler.cc.  Many other
existing variables may want GUARDED_BY, but they don't have.  Hmm.  I think
other existing variables should be cared in upstream on the side.

At this time, I added GUARDED_BY(_lock) for new variable declaration in
memory_region_map.h and added comments like MemoryRegionMap::recursion_count_ in
this .cc.  What do you think?

+HeapProfileBucket MemoryRegionMap::saved_buckets_[20];
+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_ = reinterpret_cast<HeapProfileBucket**>(

[willchan no longer on Chromium, 2013/03/13 21:58:48]

static_cast<>?

[Dai Mikurube (NOT FULLTIME), 2013/03/14 09:33:47]

static_cast works here.  Replaced.

Many of existing reinterpret_cast in heap-profile-table may need replacing, but
it should be done on the side if we want.

+        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* x = bucket_table_[i]; x != 0; /**/) {
+        HeapProfileBucket* b = x;

[willchan no longer on Chromium, 2013/03/13 21:58:48]

Commenting generally about this since you brought it up offline earlier.

|i| is commonly used for counters.
|x| is also somewhat commonly used for counters, but this isn't a counter.
|b| is not commonly used.

http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Genera...
says:
"""
Poorly-chosen names use ambiguous abbreviations or arbitrary characters that do
not convey meaning:

int n;                           // Bad - meaningless.
"""

I think |i| as a counter is a fine exception to this rule. |x| also for
counters, or arbitrary math. |b| is not commonly used except for arbitrary math.

Here I'd like to see |b| renamed. |x| is more debatable.

I suggest x=>curr (curr is a common abbreviation for linked list iteration) and
b=>bucket.

[Dai Mikurube (NOT FULLTIME), 2013/03/14 09:33:47]

Sounds reasonable renaming.  Done it (also in some other new functions).

+        x = x->next;
+        MyAllocator::Free(b->stack, 0);
+        MyAllocator::Free(b, 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::IsRecording() {
+  RAW_VLOG(10, "MemoryRegionMap IsRecording");
+  Lock();
+  bool is_working = (client_count_ > 0);
+  Unlock();
+  RAW_VLOG(10, "MemoryRegionMap IsRecording done");
+  return is_working;

[willchan no longer on Chromium, 2013/03/13 21:58:48]

Just doublechecking...this looks like it could be racy. Does it matter?
Obviously after Unlock() is called, |client_count_| can change. Does that
matter?

It looks like Shutdown() deletes the buckets, but after the IsRecording() check,
deep-heap-profile.cc may try to access buckets directly. Can we get use after
frees in races? Does this matter?

[Dai Mikurube (NOT FULLTIME), 2013/03/14 09:33:47]

Ahh, you're right.  It could be a problem.  Changed this function to
"IsRecordingLocked", and it requires a lock before calling this function.

+}
+
 // 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[]) {
+  // Make hash-value
+  uintptr_t h = 0;
+  for (int i = 0; i < depth; i++) {
+    h += reinterpret_cast<uintptr_t>(key[i]);
+    h += h << 10;
+    h ^= h >> 6;
+  }
+  h += h << 3;
+  h ^= h >> 11;
+
+  // Lookup stack trace in table
+  unsigned int buck = ((unsigned int) h) % kHashTableSize;

[willchan no longer on Chromium, 2013/03/13 21:58:48]

Is |buck| short for |bucket|? As the style guide indicated earlier, don't
abbreviate it like that. I know it's debatable, but arguably |buck| is not
common enough for people to understand. Let's call it |index|. Then we can stop
using |b| for HeapProfileBucket* and call it |bucket| instead.

[Dai Mikurube (NOT FULLTIME), 2013/03/14 09:33:47]

It actually comes from heap-profile-table's GetBucket, and I'm not sure what
|buck| means in fact.  I think it should not be a "bucket".  It's just an index
in the hash table.  I kept the original variable names at first not to lose the
context, but I think

h => hash
buck => hash_index
b => bucket

might be reasonable.  What do you think?

+  for (HeapProfileBucket* b = bucket_table_[buck]; b != 0; b = b->next) {
+    if ((b->hash == h) &&
+        (b->depth == depth) &&
+        std::equal(key, key + depth, b->stack)) {
+      return b;
+    }
+  }
+
+  // Create new bucket
+  const size_t key_size = sizeof(key[0]) * depth;
+  HeapProfileBucket* b;
+  if (recursive_insert) {  // recursion: save in saved_buckets_
+    const void** kcopy = saved_buckets_keys_[saved_buckets_count_];
+    std::copy(key, key + depth, kcopy);
+    b = &saved_buckets_[saved_buckets_count_];
+    memset(b, 0, sizeof(*b));
+    ++saved_buckets_count_;
+    b->stack = kcopy;
+    b->next  = NULL;
+  } else {
+    recursive_insert = true;
+    const void** kcopy = reinterpret_cast<const void**>(

[willchan no longer on Chromium, 2013/03/13 21:58:48]

Don't we want static_cast<> here? What does kcopy mean? Does it mean key copy?
Should we name it |key_copy|?

[Dai Mikurube (NOT FULLTIME), 2013/03/14 09:33:47]

Replaced it to static_cast and renamed kcopy to key_copy.

+        MyAllocator::Allocate(key_size));
+    recursive_insert = false;
+    std::copy(key, key + depth, kcopy);
+    recursive_insert = true;
+    b = reinterpret_cast<HeapProfileBucket*>(
+        MyAllocator::Allocate(sizeof(HeapProfileBucket)));
+    recursive_insert = false;
+    memset(b, 0, sizeof(*b));
+    b->stack = kcopy;
+    b->next  = bucket_table_[buck];
+  }
+  b->hash  = h;
+  b->depth = depth;
+  bucket_table_[buck] = b;
+  ++num_buckets_;
+  return b;
+}
+
 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() {
+  while (saved_buckets_count_ > 0) {
+    HeapProfileBucket b = saved_buckets_[--saved_buckets_count_];
+    unsigned int buck = ((unsigned int) b.hash) % kHashTableSize;

[willchan no longer on Chromium, 2013/03/13 21:58:48]

static_cast<>. we discourage c-style casts in the style guide. i know it's done
in some places in google-perftools, but that's primarily because it's very old
code before google got strict about the style guide.

[Dai Mikurube (NOT FULLTIME), 2013/03/14 09:33:47]

Replaced to static_cast (also in GetBucket).
Also renamed many variables in this function.

+    bool is_found = false;
+    for (HeapProfileBucket* found = bucket_table_[buck];
+         found != 0;
+         found = found->next) {
+      if ((found->hash == b.hash) && (found->depth == b.depth) &&
+          std::equal(b.stack, b.stack + b.depth, found->stack)) {
+        found->allocs += b.allocs;
+        found->alloc_size += b.alloc_size;
+        found->frees += b.frees;
+        found->free_size += b.free_size;
+        is_found = true;
+        break;
+      }
+    }
+    if (is_found) continue;
+
+    const size_t key_size = sizeof(b.stack[0]) * b.depth;
+    const void** kcopy = reinterpret_cast<const void**>(

[willchan no longer on Chromium, 2013/03/13 21:58:48]

static_cast

[Dai Mikurube (NOT FULLTIME), 2013/03/14 09:33:47]

Done.

+        MyAllocator::Allocate(key_size));
+    std::copy(b.stack, b.stack + b.depth, kcopy);
+    HeapProfileBucket* new_b = reinterpret_cast<HeapProfileBucket*>(

[willchan no longer on Chromium, 2013/03/13 21:58:48]

s/new_b/new_bucket/

[Dai Mikurube (NOT FULLTIME), 2013/03/14 09:33:47]

Done.

+        MyAllocator::Allocate(sizeof(HeapProfileBucket)));
+    memset(new_b, 0, sizeof(*new_b));
+    new_b->hash = b.hash;
+    new_b->depth = b.depth;
+    new_b->stack = kcopy;
+    new_b->next = bucket_table_[buck];
+    bucket_table_[buck] = new_b;
+    ++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) {
+  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");
 }