src/heap-profile-table.cc - external/github.com/gperftools/gperftools - Git at Google

 // -*- Mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*-
 // 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
 // copyright notice, this list of conditions and the following disclaimer
 // in the documentation and/or other materials provided with the
 // distribution.
 //     * Neither the name of Google Inc. nor the names of its
 // contributors may be used to endorse or promote products derived from
 // this software without specific prior written permission.
 //
 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 // ---
 // Author: Sanjay Ghemawat
 //         Maxim Lifantsev (refactoring)
 //

 #include <config.h>

 #ifdef HAVE_UNISTD_H
 #include <unistd.h>   // for write()
 #endif
 #include <fcntl.h>    // for open()
 #ifdef HAVE_GLOB_H
 #include <glob.h>
 #ifndef GLOB_NOMATCH  // true on some old cygwins
 # define GLOB_NOMATCH 0
 #endif
 #endif
 #include <inttypes.h> // for PRIxPTR
 #ifdef HAVE_POLL_H
 #include <poll.h>
 #endif
 #include <errno.h>
 #include <stdarg.h>

 #include <algorithm>  // for sort(), equal(), and copy()
 #include <map>
 #include <memory>
 #include <string>

 #include "heap-profile-table.h"

 #include "base/commandlineflags.h"
 #include "base/logging.h"
 #include "base/proc_maps_iterator.h"
 #include "base/sysinfo.h"
 #include "gperftools/malloc_hook.h"
 #include "gperftools/stacktrace.h"
 #include "memory_region_map.h"
 #include "symbolize.h"

 using std::sort;
 using std::equal;
 using std::copy;
 using std::string;
 using std::map;

 //----------------------------------------------------------------------

 DEFINE_bool(cleanup_old_heap_profiles,
             EnvToBool("HEAP_PROFILE_CLEANUP", true),
             "At initialization time, delete old heap profiles.");

 DEFINE_int32(heap_check_max_leaks,
              EnvToInt("HEAP_CHECK_MAX_LEAKS", 20),
              "The maximum number of leak reports to print.");

 //----------------------------------------------------------------------

 // header of the dumped heap profile
 static const char kProfileHeader[] = "heap profile: ";
 static const char kProcSelfMapsHeader[] = "\nMAPPED_LIBRARIES:\n";

 //----------------------------------------------------------------------

 const char HeapProfileTable::kFileExt[] = ".heap";

 //----------------------------------------------------------------------

 static const int kHashTableSize = 179999;   // Size for bucket_table_.
 /*static*/ const int HeapProfileTable::kMaxStackDepth;

 //----------------------------------------------------------------------

 // We strip out different number of stack frames in debug mode
 // because less inlining happens in that case
 #ifdef NDEBUG
 static const int kStripFrames = 2;
 #else
 static const int kStripFrames = 3;
 #endif

 //----------------------------------------------------------------------

 HeapProfileTable::HeapProfileTable(Allocator alloc,
                                    DeAllocator dealloc,
                                    bool profile_mmap)
     : alloc_(alloc),
       dealloc_(dealloc),
       profile_mmap_(profile_mmap),
       bucket_table_(NULL),
       num_buckets_(0),
       address_map_(NULL) {
   // Make a hash table for buckets.
   const int table_bytes = kHashTableSize * sizeof(*bucket_table_);
   bucket_table_ = static_cast<Bucket**>(alloc_(table_bytes));
   memset(bucket_table_, 0, table_bytes);

   // Make an allocation map.
   address_map_ =
       new(alloc_(sizeof(AllocationMap))) AllocationMap(alloc_, dealloc_);

   // Initialize.
   memset(&total_, 0, sizeof(total_));
   num_buckets_ = 0;
 }

 HeapProfileTable::~HeapProfileTable() {
   // Free the allocation map.
   address_map_->~AllocationMap();
   dealloc_(address_map_);
   address_map_ = NULL;

   // Free the hash table.
   for (int i = 0; i < kHashTableSize; i++) {
     for (Bucket* curr = bucket_table_[i]; curr != 0; /**/) {
       Bucket* bucket = curr;
       curr = curr->next;
       dealloc_(bucket->stack);
       dealloc_(bucket);
     }
   }
   dealloc_(bucket_table_);
   bucket_table_ = NULL;
 }

 HeapProfileTable::Bucket* HeapProfileTable::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;
   for (Bucket* b = bucket_table_[buck]; b != 0; b = b->next) {
     if ((b->hash == h) &&
         (b->depth == depth) &&
         equal(key, key + depth, b->stack)) {
       return b;
     }
   }

   // Create new bucket
   const size_t key_size = sizeof(key[0]) * depth;
   const void** kcopy = reinterpret_cast<const void**>(alloc_(key_size));
   copy(key, key + depth, kcopy);
   Bucket* b = reinterpret_cast<Bucket*>(alloc_(sizeof(Bucket)));
   memset(b, 0, sizeof(*b));
   b->hash  = h;
   b->depth = depth;
   b->stack = kcopy;
   b->next  = bucket_table_[buck];
   bucket_table_[buck] = b;
   num_buckets_++;
   return b;
 }

 int HeapProfileTable::GetCallerStackTrace(
     int skip_count, void* stack[kMaxStackDepth]) {
   return MallocHook::GetCallerStackTrace(
       stack, kMaxStackDepth, kStripFrames + skip_count + 1);
 }

 void HeapProfileTable::RecordAlloc(
     const void* ptr, size_t bytes, int stack_depth,
     const void* const call_stack[]) {
   Bucket* b = GetBucket(stack_depth, call_stack);
   b->allocs++;
   b->alloc_size += bytes;
   total_.allocs++;
   total_.alloc_size += bytes;

   AllocValue v;
   v.set_bucket(b);  // also did set_live(false); set_ignore(false)
   v.bytes = bytes;
   address_map_->Insert(ptr, v);
 }

 void HeapProfileTable::RecordFree(const void* ptr) {
   AllocValue v;
   if (address_map_->FindAndRemove(ptr, &v)) {
     Bucket* b = v.bucket();
     b->frees++;
     b->free_size += v.bytes;
     total_.frees++;
     total_.free_size += v.bytes;
   }
 }

 bool HeapProfileTable::FindAlloc(const void* ptr, size_t* object_size) const {
   const AllocValue* alloc_value = address_map_->Find(ptr);
   if (alloc_value != NULL) *object_size = alloc_value->bytes;
   return alloc_value != NULL;
 }

 bool HeapProfileTable::FindAllocDetails(const void* ptr,
                                         AllocInfo* info) const {
   const AllocValue* alloc_value = address_map_->Find(ptr);
   if (alloc_value != NULL) {
     info->object_size = alloc_value->bytes;
     info->call_stack = alloc_value->bucket()->stack;
     info->stack_depth = alloc_value->bucket()->depth;
   }
   return alloc_value != NULL;
 }

 bool HeapProfileTable::FindInsideAlloc(const void* ptr,
                                        size_t max_size,
                                        const void** object_ptr,
                                        size_t* object_size) const {
   const AllocValue* alloc_value =
     address_map_->FindInside(&AllocValueSize, max_size, ptr, object_ptr);
   if (alloc_value != NULL) *object_size = alloc_value->bytes;
   return alloc_value != NULL;
 }

 bool HeapProfileTable::MarkAsLive(const void* ptr) {
   AllocValue* alloc = address_map_->FindMutable(ptr);
   if (alloc && !alloc->live()) {
     alloc->set_live(true);
     return true;
   }
   return false;
 }

 void HeapProfileTable::MarkAsIgnored(const void* ptr) {
   AllocValue* alloc = address_map_->FindMutable(ptr);
   if (alloc) {
     alloc->set_ignore(true);
   }
 }

 void HeapProfileTable::UnparseBucket(const Bucket& b,
                                      tcmalloc::GenericWriter* writer,
                                      const char* extra) {
   writer->AppendF("%6" PRId64 ": %8" PRId64 " [%6" PRId64 ": %8" PRId64 "] @",
                   b.allocs - b.frees,
                   b.alloc_size - b.free_size,
                   b.allocs,
                   b.alloc_size);
   writer->AppendStr(extra);

   for (int d = 0; d < b.depth; d++) {
     writer->AppendF(" 0x%08" PRIxPTR,
                     reinterpret_cast<uintptr_t>(b.stack[d]));
   }
   writer->AppendStr("\n");
 }

 void HeapProfileTable::SaveProfile(tcmalloc::GenericWriter* writer) const {
   writer->AppendStr(kProfileHeader);
   UnparseBucket(total_, writer, " heapprofile");

   // Dump the mmap list first.
   if (profile_mmap_) {
     MemoryRegionMap::LockHolder holder{};
     MemoryRegionMap::IterateBuckets([writer] (const Bucket* bucket) {
       UnparseBucket(*bucket, writer, "");
     });
   }

   int bucket_count = 0;
   for (int i = 0; i < kHashTableSize; i++) {
     for (Bucket* curr = bucket_table_[i]; curr != nullptr; curr = curr->next) {
       UnparseBucket(*curr, writer, "");
       bucket_count++;
     }
   }
   RAW_DCHECK(bucket_count == num_buckets_, "");
   (void)bucket_count;

   writer->AppendStr(kProcSelfMapsHeader);
   tcmalloc::SaveProcSelfMaps(writer);
 }

 bool HeapProfileTable::WriteProfile(const char* file_name,
                                     const Bucket& total,
                                     AllocationMap* allocations) {
   RAW_VLOG(1, "Dumping non-live heap profile to %s", file_name);
   RawFD fd = RawOpenForWriting(file_name);
   if (fd == kIllegalRawFD) {
     RAW_LOG(ERROR, "Failed dumping filtered heap profile to %s", file_name);
     return false;
   }

   tcmalloc::RawFDGenericWriter<> writer{fd};

   writer.AppendStr(kProfileHeader);

   UnparseBucket(total, &writer, " heapprofile");

   allocations->Iterate([&writer] (const void* ptr, AllocValue* v) {
     if (v->live()) {
       v->set_live(false);
       return;
     }
     if (v->ignore()) {
       return;
     }
     Bucket b;
     memset(&b, 0, sizeof(b));
     b.allocs = 1;
     b.alloc_size = v->bytes;
     b.depth = v->bucket()->depth;
     b.stack = v->bucket()->stack;
     UnparseBucket(b, &writer, "");
   });

   RawWrite(fd, kProcSelfMapsHeader, strlen(kProcSelfMapsHeader));
   tcmalloc::SaveProcSelfMapsToRawFD(fd);

   RawClose(fd);
   return true;
 }

 void HeapProfileTable::CleanupOldProfiles(const char* prefix) {
   if (!FLAGS_cleanup_old_heap_profiles)
     return;
   string pattern = string(prefix) + ".*" + kFileExt;
 #if defined(HAVE_GLOB_H)
   glob_t g;
   const int r = glob(pattern.c_str(), GLOB_ERR, NULL, &g);
   if (r == 0 || r == GLOB_NOMATCH) {
     const int prefix_length = strlen(prefix);
     for (int i = 0; i < g.gl_pathc; i++) {
       const char* fname = g.gl_pathv[i];
       if ((strlen(fname) >= prefix_length) &&
           (memcmp(fname, prefix, prefix_length) == 0)) {
         RAW_VLOG(1, "Removing old heap profile %s", fname);
         unlink(fname);
       }
     }
   }
   globfree(&g);
 #else   /* HAVE_GLOB_H */
   RAW_LOG(WARNING, "Unable to remove old heap profiles (can't run glob())");
 #endif
 }

 HeapProfileTable::Snapshot* HeapProfileTable::TakeSnapshot() {
   Snapshot* s = new (alloc_(sizeof(Snapshot))) Snapshot(alloc_, dealloc_);
   address_map_->Iterate([s] (const void* ptr, AllocValue* v) {
     s->Add(ptr, *v);
   });
   return s;
 }

 void HeapProfileTable::ReleaseSnapshot(Snapshot* s) {
   s->~Snapshot();
   dealloc_(s);
 }

 HeapProfileTable::Snapshot* HeapProfileTable::NonLiveSnapshot(
     Snapshot* base) {
   RAW_VLOG(2, "NonLiveSnapshot input: %" PRId64 " %" PRId64 "\n",
            total_.allocs - total_.frees,
            total_.alloc_size - total_.free_size);

   Snapshot* s = new (alloc_(sizeof(Snapshot))) Snapshot(alloc_, dealloc_);
   address_map_->Iterate([&] (const void* ptr, AllocValue* v) {
     if (v->live()) {
       v->set_live(false);
     } else {
       if (base != nullptr && base->map_.Find(ptr) != nullptr) {
         // Present in arg->base, so do not save
       } else {
         s->Add(ptr, *v);
       }
     }
   });
   RAW_VLOG(2, "NonLiveSnapshot output: %" PRId64 " %" PRId64 "\n",
            s->total_.allocs - s->total_.frees,
            s->total_.alloc_size - s->total_.free_size);
   return s;
 }

 // Information kept per unique bucket seen
 struct HeapProfileTable::Snapshot::Entry {
   int count;
   size_t bytes;
   Bucket* bucket;
   Entry() : count(0), bytes(0) { }

   // Order by decreasing bytes
   bool operator<(const Entry& x) const {
     return this->bytes > x.bytes;
   }
 };

 void HeapProfileTable::Snapshot::ReportLeaks(const char* checker_name,
                                              const char* filename,
                                              bool should_symbolize) {
   // This is only used by the heap leak checker, but is intimately
   // tied to the allocation map that belongs in this module and is
   // therefore placed here.
   RAW_LOG(ERROR, "Leak check %s detected leaks of %zu bytes "
           "in %zu objects",
           checker_name,
           size_t(total_.alloc_size),
           size_t(total_.allocs));

   // Group objects by Bucket
   std::map<Bucket*, Entry> buckets;
   map_.Iterate([&] (const void* ptr, AllocValue* v) {
     Entry* e = &buckets[v->bucket()]; // Creates empty Entry first time
     e->bucket = v->bucket();
     e->count++;
     e->bytes += v->bytes;
   });

   // Sort buckets by decreasing leaked size
   const int n = buckets.size();
   Entry* entries = new Entry[n];
   int dst = 0;
   for (map<Bucket*,Entry>::const_iterator iter = buckets.begin();
        iter != buckets.end();
        ++iter) {
     entries[dst++] = iter->second;
   }
   std::sort(entries, entries + n);

   // Report a bounded number of leaks to keep the leak report from
   // growing too long.
   const int to_report =
       (FLAGS_heap_check_max_leaks > 0 &&
        n > FLAGS_heap_check_max_leaks) ? FLAGS_heap_check_max_leaks : n;
   RAW_LOG(ERROR, "The %d largest leaks:", to_report);

   // Print
   SymbolTable symbolization_table;
   for (int i = 0; i < to_report; i++) {
     const Entry& e = entries[i];
     for (int j = 0; j < e.bucket->depth; j++) {
       symbolization_table.Add(e.bucket->stack[j]);
     }
   }
   if (should_symbolize)
     symbolization_table.Symbolize();

   {
     auto do_log = +[] (const char* buf, size_t amt) {
       RAW_LOG(ERROR, "%.*s", amt, buf);
     };
     constexpr int kBufSize = 2<<10;
     tcmalloc::WriteFnWriter<decltype(do_log), kBufSize> printer{do_log};

     for (int i = 0; i < to_report; i++) {
       const Entry& e = entries[i];
       printer.AppendF("Leak of %zu bytes in %d objects allocated from:\n",
                       e.bytes, e.count);
       for (int j = 0; j < e.bucket->depth; j++) {
         const void* pc = e.bucket->stack[j];
         printer.AppendF("\t@ %" PRIxPTR " %s\n",
                         reinterpret_cast<uintptr_t>(pc), symbolization_table.GetSymbol(pc));
       }
     }
   }

   if (to_report < n) {
     RAW_LOG(ERROR, "Skipping leaks numbered %d..%d",
             to_report, n-1);
   }
   delete[] entries;

   if (!HeapProfileTable::WriteProfile(filename, total_, &map_)) {
     RAW_LOG(ERROR, "Could not write pprof profile to %s", filename);
   }
 }

 void HeapProfileTable::Snapshot::ReportIndividualObjects() {
   map_.Iterate([] (const void* ptr, AllocValue* v) {
     // Perhaps also log the allocation stack trace (unsymbolized)
     // on this line in case somebody finds it useful.
     RAW_LOG(ERROR, "leaked %zu byte object %p", v->bytes, ptr);
   });
 }
	// -- Mode: C++; c-basic-offset: 2; indent-tabs-mode: nil --
	// 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
	// copyright notice, this list of conditions and the following disclaimer
	// in the documentation and/or other materials provided with the
	// distribution.
	// * Neither the name of Google Inc. nor the names of its
	// contributors may be used to endorse or promote products derived from
	// this software without specific prior written permission.
	//
	// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
	// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
	// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

	// ---
	// Author: Sanjay Ghemawat
	// Maxim Lifantsev (refactoring)
	//

	#include <config.h>

	#ifdef HAVE_UNISTD_H
	#include <unistd.h> // for write()
	#endif
	#include <fcntl.h> // for open()
	#ifdef HAVE_GLOB_H
	#include <glob.h>
	#ifndef GLOB_NOMATCH // true on some old cygwins
	# define GLOB_NOMATCH 0
	#endif
	#endif
	#include <inttypes.h> // for PRIxPTR
	#ifdef HAVE_POLL_H
	#include <poll.h>
	#endif
	#include <errno.h>
	#include <stdarg.h>

	#include <algorithm> // for sort(), equal(), and copy()
	#include <map>
	#include <memory>
	#include <string>

	#include "heap-profile-table.h"

	#include "base/commandlineflags.h"
	#include "base/logging.h"
	#include "base/proc_maps_iterator.h"
	#include "base/sysinfo.h"
	#include "gperftools/malloc_hook.h"
	#include "gperftools/stacktrace.h"
	#include "memory_region_map.h"
	#include "symbolize.h"

	using std::sort;
	using std::equal;
	using std::copy;
	using std::string;
	using std::map;

	//----------------------------------------------------------------------

	DEFINE_bool(cleanup_old_heap_profiles,
	EnvToBool("HEAP_PROFILE_CLEANUP", true),
	"At initialization time, delete old heap profiles.");

	DEFINE_int32(heap_check_max_leaks,
	EnvToInt("HEAP_CHECK_MAX_LEAKS", 20),
	"The maximum number of leak reports to print.");

	//----------------------------------------------------------------------

	// header of the dumped heap profile
	static const char kProfileHeader[] = "heap profile: ";
	static const char kProcSelfMapsHeader[] = "\nMAPPED_LIBRARIES:\n";

	//----------------------------------------------------------------------

	const char HeapProfileTable::kFileExt[] = ".heap";

	//----------------------------------------------------------------------

	static const int kHashTableSize = 179999; // Size for bucket_table_.
	/static/ const int HeapProfileTable::kMaxStackDepth;

	//----------------------------------------------------------------------

	// We strip out different number of stack frames in debug mode
	// because less inlining happens in that case
	#ifdef NDEBUG
	static const int kStripFrames = 2;
	#else
	static const int kStripFrames = 3;
	#endif

	//----------------------------------------------------------------------

	HeapProfileTable::HeapProfileTable(Allocator alloc,
	DeAllocator dealloc,
	bool profile_mmap)
	: alloc_(alloc),
	dealloc_(dealloc),
	profile_mmap_(profile_mmap),
	bucket_table_(NULL),
	num_buckets_(0),
	address_map_(NULL) {
	// Make a hash table for buckets.
	const int table_bytes = kHashTableSize * sizeof(*bucket_table_);
	bucket_table_ = static_cast<Bucket**>(alloc_(table_bytes));
	memset(bucket_table_, 0, table_bytes);

	// Make an allocation map.
	address_map_ =
	new(alloc_(sizeof(AllocationMap))) AllocationMap(alloc_, dealloc_);

	// Initialize.
	memset(&total_, 0, sizeof(total_));
	num_buckets_ = 0;
	}

	HeapProfileTable::~HeapProfileTable() {
	// Free the allocation map.
	address_map_->~AllocationMap();
	dealloc_(address_map_);
	address_map_ = NULL;

	// Free the hash table.
	for (int i = 0; i < kHashTableSize; i++) {
	for (Bucket* curr = bucket_table_[i]; curr != 0; /**/) {
	Bucket* bucket = curr;
	curr = curr->next;
	dealloc_(bucket->stack);
	dealloc_(bucket);
	}
	}
	dealloc_(bucket_table_);
	bucket_table_ = NULL;
	}

	HeapProfileTable::Bucket* HeapProfileTable::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;
	for (Bucket* b = bucket_table_[buck]; b != 0; b = b->next) {
	if ((b->hash == h) &&
	(b->depth == depth) &&
	equal(key, key + depth, b->stack)) {
	return b;
	}
	}

	// Create new bucket
	const size_t key_size = sizeof(key[0]) * depth;
	const void kcopy = reinterpret_cast<const void>(alloc_(key_size));
	copy(key, key + depth, kcopy);
	Bucket* b = reinterpret_cast<Bucket*>(alloc_(sizeof(Bucket)));
	memset(b, 0, sizeof(*b));
	b->hash = h;
	b->depth = depth;
	b->stack = kcopy;
	b->next = bucket_table_[buck];
	bucket_table_[buck] = b;
	num_buckets_++;
	return b;
	}

	int HeapProfileTable::GetCallerStackTrace(
	int skip_count, void* stack[kMaxStackDepth]) {
	return MallocHook::GetCallerStackTrace(
	stack, kMaxStackDepth, kStripFrames + skip_count + 1);
	}

	void HeapProfileTable::RecordAlloc(
	const void* ptr, size_t bytes, int stack_depth,
	const void* const call_stack[]) {
	Bucket* b = GetBucket(stack_depth, call_stack);
	b->allocs++;
	b->alloc_size += bytes;
	total_.allocs++;
	total_.alloc_size += bytes;

	AllocValue v;
	v.set_bucket(b); // also did set_live(false); set_ignore(false)
	v.bytes = bytes;
	address_map_->Insert(ptr, v);
	}

	void HeapProfileTable::RecordFree(const void* ptr) {
	AllocValue v;
	if (address_map_->FindAndRemove(ptr, &v)) {
	Bucket* b = v.bucket();
	b->frees++;
	b->free_size += v.bytes;
	total_.frees++;
	total_.free_size += v.bytes;
	}
	}

	bool HeapProfileTable::FindAlloc(const void* ptr, size_t* object_size) const {
	const AllocValue* alloc_value = address_map_->Find(ptr);
	if (alloc_value != NULL) *object_size = alloc_value->bytes;
	return alloc_value != NULL;
	}

	bool HeapProfileTable::FindAllocDetails(const void* ptr,
	AllocInfo* info) const {
	const AllocValue* alloc_value = address_map_->Find(ptr);
	if (alloc_value != NULL) {
	info->object_size = alloc_value->bytes;
	info->call_stack = alloc_value->bucket()->stack;
	info->stack_depth = alloc_value->bucket()->depth;
	}
	return alloc_value != NULL;
	}

	bool HeapProfileTable::FindInsideAlloc(const void* ptr,
	size_t max_size,
	const void** object_ptr,
	size_t* object_size) const {
	const AllocValue* alloc_value =
	address_map_->FindInside(&AllocValueSize, max_size, ptr, object_ptr);
	if (alloc_value != NULL) *object_size = alloc_value->bytes;
	return alloc_value != NULL;
	}

	bool HeapProfileTable::MarkAsLive(const void* ptr) {
	AllocValue* alloc = address_map_->FindMutable(ptr);
	if (alloc && !alloc->live()) {
	alloc->set_live(true);
	return true;
	}
	return false;
	}

	void HeapProfileTable::MarkAsIgnored(const void* ptr) {
	AllocValue* alloc = address_map_->FindMutable(ptr);
	if (alloc) {
	alloc->set_ignore(true);
	}
	}

	void HeapProfileTable::UnparseBucket(const Bucket& b,
	tcmalloc::GenericWriter* writer,
	const char* extra) {
	writer->AppendF("%6" PRId64 ": %8" PRId64 " [%6" PRId64 ": %8" PRId64 "] @",
	b.allocs - b.frees,
	b.alloc_size - b.free_size,
	b.allocs,
	b.alloc_size);
	writer->AppendStr(extra);

	for (int d = 0; d < b.depth; d++) {
	writer->AppendF(" 0x%08" PRIxPTR,
	reinterpret_cast<uintptr_t>(b.stack[d]));
	}
	writer->AppendStr("\n");
	}

	void HeapProfileTable::SaveProfile(tcmalloc::GenericWriter* writer) const {
	writer->AppendStr(kProfileHeader);
	UnparseBucket(total_, writer, " heapprofile");

	// Dump the mmap list first.
	if (profile_mmap_) {
	MemoryRegionMap::LockHolder holder{};
	MemoryRegionMap::IterateBuckets([writer] (const Bucket* bucket) {
	UnparseBucket(*bucket, writer, "");
	});
	}

	int bucket_count = 0;
	for (int i = 0; i < kHashTableSize; i++) {
	for (Bucket* curr = bucket_table_[i]; curr != nullptr; curr = curr->next) {
	UnparseBucket(*curr, writer, "");
	bucket_count++;
	}
	}
	RAW_DCHECK(bucket_count == num_buckets_, "");
	(void)bucket_count;

	writer->AppendStr(kProcSelfMapsHeader);
	tcmalloc::SaveProcSelfMaps(writer);
	}

	bool HeapProfileTable::WriteProfile(const char* file_name,
	const Bucket& total,
	AllocationMap* allocations) {
	RAW_VLOG(1, "Dumping non-live heap profile to %s", file_name);
	RawFD fd = RawOpenForWriting(file_name);
	if (fd == kIllegalRawFD) {
	RAW_LOG(ERROR, "Failed dumping filtered heap profile to %s", file_name);
	return false;
	}

	tcmalloc::RawFDGenericWriter<> writer{fd};

	writer.AppendStr(kProfileHeader);

	UnparseBucket(total, &writer, " heapprofile");

	allocations->Iterate([&writer] (const void* ptr, AllocValue* v) {
	if (v->live()) {
	v->set_live(false);
	return;
	}
	if (v->ignore()) {
	return;
	}
	Bucket b;
	memset(&b, 0, sizeof(b));
	b.allocs = 1;
	b.alloc_size = v->bytes;
	b.depth = v->bucket()->depth;
	b.stack = v->bucket()->stack;
	UnparseBucket(b, &writer, "");
	});

	RawWrite(fd, kProcSelfMapsHeader, strlen(kProcSelfMapsHeader));
	tcmalloc::SaveProcSelfMapsToRawFD(fd);

	RawClose(fd);
	return true;
	}

	void HeapProfileTable::CleanupOldProfiles(const char* prefix) {
	if (!FLAGS_cleanup_old_heap_profiles)
	return;
	string pattern = string(prefix) + ".*" + kFileExt;
	#if defined(HAVE_GLOB_H)
	glob_t g;
	const int r = glob(pattern.c_str(), GLOB_ERR, NULL, &g);
	if (r == 0 \|\| r == GLOB_NOMATCH) {
	const int prefix_length = strlen(prefix);
	for (int i = 0; i < g.gl_pathc; i++) {
	const char* fname = g.gl_pathv[i];
	if ((strlen(fname) >= prefix_length) &&
	(memcmp(fname, prefix, prefix_length) == 0)) {
	RAW_VLOG(1, "Removing old heap profile %s", fname);
	unlink(fname);
	}
	}
	}
	globfree(&g);
	#else /* HAVE_GLOB_H */
	RAW_LOG(WARNING, "Unable to remove old heap profiles (can't run glob())");
	#endif
	}

	HeapProfileTable::Snapshot* HeapProfileTable::TakeSnapshot() {
	Snapshot* s = new (alloc_(sizeof(Snapshot))) Snapshot(alloc_, dealloc_);
	address_map_->Iterate([s] (const void* ptr, AllocValue* v) {
	s->Add(ptr, *v);
	});
	return s;
	}

	void HeapProfileTable::ReleaseSnapshot(Snapshot* s) {
	s->~Snapshot();
	dealloc_(s);
	}

	HeapProfileTable::Snapshot* HeapProfileTable::NonLiveSnapshot(
	Snapshot* base) {
	RAW_VLOG(2, "NonLiveSnapshot input: %" PRId64 " %" PRId64 "\n",
	total_.allocs - total_.frees,
	total_.alloc_size - total_.free_size);

	Snapshot* s = new (alloc_(sizeof(Snapshot))) Snapshot(alloc_, dealloc_);
	address_map_->Iterate([&] (const void* ptr, AllocValue* v) {
	if (v->live()) {
	v->set_live(false);
	} else {
	if (base != nullptr && base->map_.Find(ptr) != nullptr) {
	// Present in arg->base, so do not save
	} else {
	s->Add(ptr, *v);
	}
	}
	});
	RAW_VLOG(2, "NonLiveSnapshot output: %" PRId64 " %" PRId64 "\n",
	s->total_.allocs - s->total_.frees,
	s->total_.alloc_size - s->total_.free_size);
	return s;
	}

	// Information kept per unique bucket seen
	struct HeapProfileTable::Snapshot::Entry {
	int count;
	size_t bytes;
	Bucket* bucket;
	Entry() : count(0), bytes(0) { }

	// Order by decreasing bytes
	bool operator<(const Entry& x) const {
	return this->bytes > x.bytes;
	}
	};

	void HeapProfileTable::Snapshot::ReportLeaks(const char* checker_name,
	const char* filename,
	bool should_symbolize) {
	// This is only used by the heap leak checker, but is intimately
	// tied to the allocation map that belongs in this module and is
	// therefore placed here.
	RAW_LOG(ERROR, "Leak check %s detected leaks of %zu bytes "
	"in %zu objects",
	checker_name,
	size_t(total_.alloc_size),
	size_t(total_.allocs));

	// Group objects by Bucket
	std::map<Bucket*, Entry> buckets;
	map_.Iterate([&] (const void* ptr, AllocValue* v) {
	Entry* e = &buckets[v->bucket()]; // Creates empty Entry first time
	e->bucket = v->bucket();
	e->count++;
	e->bytes += v->bytes;
	});

	// Sort buckets by decreasing leaked size
	const int n = buckets.size();
	Entry* entries = new Entry[n];
	int dst = 0;
	for (map<Bucket*,Entry>::const_iterator iter = buckets.begin();
	iter != buckets.end();
	++iter) {
	entries[dst++] = iter->second;
	}
	std::sort(entries, entries + n);

	// Report a bounded number of leaks to keep the leak report from
	// growing too long.
	const int to_report =
	(FLAGS_heap_check_max_leaks > 0 &&
	n > FLAGS_heap_check_max_leaks) ? FLAGS_heap_check_max_leaks : n;
	RAW_LOG(ERROR, "The %d largest leaks:", to_report);

	// Print
	SymbolTable symbolization_table;
	for (int i = 0; i < to_report; i++) {
	const Entry& e = entries[i];
	for (int j = 0; j < e.bucket->depth; j++) {
	symbolization_table.Add(e.bucket->stack[j]);
	}
	}
	if (should_symbolize)
	symbolization_table.Symbolize();

	{
	auto do_log = +[] (const char* buf, size_t amt) {
	RAW_LOG(ERROR, "%.*s", amt, buf);
	};
	constexpr int kBufSize = 2<<10;
	tcmalloc::WriteFnWriter<decltype(do_log), kBufSize> printer{do_log};

	for (int i = 0; i < to_report; i++) {
	const Entry& e = entries[i];
	printer.AppendF("Leak of %zu bytes in %d objects allocated from:\n",
	e.bytes, e.count);
	for (int j = 0; j < e.bucket->depth; j++) {
	const void* pc = e.bucket->stack[j];
	printer.AppendF("\t@ %" PRIxPTR " %s\n",
	reinterpret_cast<uintptr_t>(pc), symbolization_table.GetSymbol(pc));
	}
	}
	}

	if (to_report < n) {
	RAW_LOG(ERROR, "Skipping leaks numbered %d..%d",
	to_report, n-1);
	}
	delete[] entries;

	if (!HeapProfileTable::WriteProfile(filename, total_, &map_)) {
	RAW_LOG(ERROR, "Could not write pprof profile to %s", filename);
	}
	}

	void HeapProfileTable::Snapshot::ReportIndividualObjects() {
	map_.Iterate([] (const void* ptr, AllocValue* v) {
	// Perhaps also log the allocation stack trace (unsymbolized)
	// on this line in case somebody finds it useful.
	RAW_LOG(ERROR, "leaked %zu byte object %p", v->bytes, ptr);
	});
	}