// -*- 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: Maxim Lifantsev
 */

//
// Background and key design points of MemoryRegionMap.
//
// MemoryRegionMap is a low-level module with quite atypical requirements that
// result in some degree of non-triviality of the implementation and design.
//
// MemoryRegionMap collects info about *all* memory regions created with
// mmap, munmap, mremap, sbrk.
// They key word above is 'all': all that are happening in a process
// during its lifetime frequently starting even before global object
// constructor execution.
//
// This is needed by the primary client of MemoryRegionMap:
// HeapLeakChecker uses the regions and the associated stack traces
// to figure out what part of the memory is the heap:
// if MemoryRegionMap were to miss some (early) regions, leak checking would
// stop working correctly.
//
// To accomplish the goal of functioning before/during global object
// constructor execution MemoryRegionMap is done as a singleton service
// that relies on own on-demand initialized static constructor-less data,
// and only relies on other low-level modules that can also function properly
// even before global object constructors run.
//
// Accomplishing the goal of collecting data about all mmap, munmap, mremap,
// sbrk occurrences is a more involved: conceptually to do this one needs to
// record some bits of data in particular about any mmap or sbrk call,
// but to do that one needs to allocate memory for that data at some point,
// but all memory allocations in the end themselves come from an mmap
// or sbrk call (that's how the address space of the process grows).
//
// Also note that we need to do all the above recording from
// within an mmap/sbrk hook which is sometimes/frequently is made by a memory
// allocator, including the allocator MemoryRegionMap itself must rely on.
// In the case of heap-checker usage this includes even the very first
// mmap/sbrk call happening in the program: heap-checker gets activated due to
// a link-time installed mmap/sbrk hook and it initializes MemoryRegionMap
// and asks it to record info about this very first call right from that
// very first hook invocation.
//
// MemoryRegionMap is doing its memory allocations via LowLevelAlloc:
// unlike more complex standard memory allocator, LowLevelAlloc cooperates with
// MemoryRegionMap by not holding any of its own locks while it calls mmap
// 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 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>

#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif
#ifdef HAVE_INTTYPES_H
#include <inttypes.h>
#endif
#ifdef HAVE_MMAP
#include <sys/mman.h>
#elif !defined(MAP_FAILED)
#define MAP_FAILED -1  // the only thing we need from mman.h
#endif
#ifdef HAVE_PTHREAD
#include <pthread.h>   // for pthread_t, pthread_self()
#endif
#include <stddef.h>

#include <algorithm>
#include <set>

#include "memory_region_map.h"

#include "base/logging.h"
#include "base/low_level_alloc.h"
#include "malloc_hook-inl.h"

#include <gperftools/stacktrace.h>
#include <gperftools/malloc_hook.h>

// MREMAP_FIXED is a linux extension.  How it's used in this file,
// setting it to 0 is equivalent to saying, "This feature isn't
// supported", which is right.
#ifndef MREMAP_FIXED
# define MREMAP_FIXED  0
#endif

using std::max;

// ========================================================================= //

int MemoryRegionMap::client_count_ = 0;
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
  if (!libpthread_initialized) return true;
  // this starts working only sometime well into global constructor execution:
  return pthread_equal(pthread_self(), should_be);
}

// ========================================================================= //

// Constructor-less place-holder to store a RegionSet in.
union MemoryRegionMap::RegionSetRep {
  char rep[sizeof(RegionSet)];
  void* align_it;  // do not need a better alignment for 'rep' than this
  RegionSet* region_set() { return reinterpret_cast<RegionSet*>(rep); }
};

// The bytes where MemoryRegionMap::regions_ will point to.
// 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, 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
    Unlock();
    RAW_VLOG(10, "MemoryRegionMap Init increment done");
    return;
  }
  // Set our hooks and make sure they were installed:
  RAW_CHECK(MallocHook::AddMmapHook(&MmapHook), "");
  RAW_CHECK(MallocHook::AddMremapHook(&MremapHook), "");
  RAW_CHECK(MallocHook::AddSbrkHook(&SbrkHook), "");
  RAW_CHECK(MallocHook::AddMunmapHook(&MunmapHook), "");
  // We need to set recursive_insert since the NewArena call itself
  // will already do some allocations with mmap which our hooks will catch
  // 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.
void MemoryRegionMap::Lock() {
  {
    SpinLockHolder l(&owner_lock_);
    if (recursion_count_ > 0 && current_thread_is(lock_owner_tid_)) {
      RAW_CHECK(lock_.IsHeld(), "Invariants violated");
      recursion_count_++;
      RAW_CHECK(recursion_count_ <= 5,
                "recursive lock nesting unexpectedly deep");
      return;
    }
  }
  lock_.Lock();
  {
    SpinLockHolder l(&owner_lock_);
    RAW_CHECK(recursion_count_ == 0,
              "Last Unlock didn't reset recursion_count_");
    if (libpthread_initialized)
      lock_owner_tid_ = pthread_self();
    recursion_count_ = 1;
  }
}

void MemoryRegionMap::Unlock() {
  SpinLockHolder l(&owner_lock_);
  RAW_CHECK(recursion_count_ >  0, "unlock when not held");
  RAW_CHECK(lock_.IsHeld(),
            "unlock when not held, and recursion_count_ is wrong");
  RAW_CHECK(current_thread_is(lock_owner_tid_), "unlock by non-holder");
  recursion_count_--;
  if (recursion_count_ == 0) {
    lock_.Unlock();
  }
}

bool MemoryRegionMap::LockIsHeld() {
  SpinLockHolder l(&owner_lock_);
  return lock_.IsHeld()  &&  current_thread_is(lock_owner_tid_);
}

const MemoryRegionMap::Region*
MemoryRegionMap::DoFindRegionLocked(uintptr_t addr) {
  RAW_CHECK(LockIsHeld(), "should be held (by this thread)");
  if (regions_ != NULL) {
    Region sample;
    sample.SetRegionSetKey(addr);
    RegionSet::iterator region = regions_->lower_bound(sample);
    if (region != regions_->end()) {
      RAW_CHECK(addr <= region->end_addr, "");
      if (region->start_addr <= addr  &&  addr < region->end_addr) {
        return &(*region);
      }
    }
  }
  return NULL;
}

bool MemoryRegionMap::FindRegion(uintptr_t addr, Region* result) {
  Lock();
  const Region* region = DoFindRegionLocked(addr);
  if (region != NULL) *result = *region;  // create it as an independent copy
  Unlock();
  return region != NULL;
}

bool MemoryRegionMap::FindAndMarkStackRegion(uintptr_t stack_top,
                                             Region* result) {
  Lock();
  const Region* region = DoFindRegionLocked(stack_top);
  if (region != NULL) {
    RAW_VLOG(10, "Stack at %p is inside region %p..%p",
                reinterpret_cast<void*>(stack_top),
                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();
}

inline void MemoryRegionMap::DoInsertRegionLocked(const Region& region) {
  RAW_VLOG(12, "Inserting region %p..%p from %p",
              reinterpret_cast<void*>(region.start_addr),
              reinterpret_cast<void*>(region.end_addr),
              reinterpret_cast<void*>(region.caller()));
  RegionSet::const_iterator i = regions_->lower_bound(region);
  if (i != regions_->end() && i->start_addr <= region.start_addr) {
    RAW_DCHECK(region.end_addr <= i->end_addr, "");  // lower_bound ensures this
    return;  // 'region' is a subset of an already recorded region; do nothing
    // We can be stricter and allow this only when *i has been created via
    // an mmap with MAP_NORESERVE flag set.
  }
  if (DEBUG_MODE) {
    RAW_CHECK(i == regions_->end()  ||  !region.Overlaps(*i),
              "Wow, overlapping memory regions");
    Region sample;
    sample.SetRegionSetKey(region.start_addr);
    i = regions_->lower_bound(sample);
    RAW_CHECK(i == regions_->end()  ||  !region.Overlaps(*i),
              "Wow, overlapping memory regions");
  }
  region.AssertIsConsistent();  // just making sure
  // This inserts and allocates permanent storage for region
  // and its call stack data: it's safe to do it now:
  regions_->insert(region);
  RAW_VLOG(12, "Inserted region %p..%p :",
              reinterpret_cast<void*>(region.start_addr),
              reinterpret_cast<void*>(region.end_addr));
  if (VLOG_IS_ON(12))  LogAllLocked();
}

// These variables are local to MemoryRegionMap::InsertRegionLocked()
// and MemoryRegionMap::HandleSavedRegionsLocked()
// and are file-level to ensure that they are initialized at load time.

// Number of unprocessed region inserts.
static int saved_regions_count = 0;

// Unprocessed inserts (must be big enough to hold all allocations that can
// be caused by a InsertRegionLocked call).
// Region has no constructor, so that c-tor execution does not interfere
// with the any-time use of the static memory behind saved_regions.
static MemoryRegionMap::Region saved_regions[20];

inline void MemoryRegionMap::HandleSavedRegionsLocked(
              void (*insert_func)(const Region& region)) {
  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",
                reinterpret_cast<void*>(region.start_addr),
                reinterpret_cast<void*>(region.end_addr),
                reinterpret_cast<void*>(region.caller()));
    RAW_CHECK(saved_regions_count < arraysize(saved_regions), "");
    // Copy 'region' to saved_regions[saved_regions_count]
    // together with the contents of its call_stack,
    // then increment saved_regions_count.
    saved_regions[saved_regions_count++] = region;
  } else {  // not a recusrive call
    if (regions_ == NULL) {  // init regions_
      RAW_VLOG(12, "Initializing region set");
      regions_ = regions_rep.region_set();
      recursive_insert = true;
      new(regions_) RegionSet();
      HandleSavedRegionsLocked(&DoInsertRegionLocked);
      recursive_insert = false;
    }
    recursive_insert = true;
    // Do the actual insertion work to put new regions into regions_:
    DoInsertRegionLocked(region);
    HandleSavedRegionsLocked(&DoInsertRegionLocked);
    recursive_insert = false;
  }
}

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

void MemoryRegionMap::RecordRegionAddition(const void* start, size_t size) {
  // Record start/end info about this memory acquisition call in a new region:
  Region region;
  region.Create(start, size);
  // First get the call stack info into the local varible 'region':
  int depth = 0;
  // NOTE: libunwind also does mmap and very much likely while holding
  // it's own lock(s). So some threads may first take libunwind lock,
  // and then take region map lock (necessary to record mmap done from
  // inside libunwind). On the other hand other thread(s) may do
  // normal mmap. Which would call this method to record it. Which
  // would then proceed with installing that record to region map
  // while holding region map lock. That may cause mmap from our own
  // internal allocators, so attempt to unwind in this case may cause
  // reverse order of taking libuwind and region map locks. Which is
  // obvious deadlock.
  //
  // Thankfully, we can easily detect if we're holding region map lock
  // and avoid recording backtrace in this (rare and largely
  // irrelevant) case. By doing this we "declare" that thread needing
  // both locks must take region map lock last. In other words we do
  // not allow taking libuwind lock when we already have region map
  // lock. Note, this is generally impossible when somebody tries to
  // mix cpu profiling and heap checking/profiling, because cpu
  // profiler grabs backtraces at arbitrary places. But at least such
  // combination is rarer and less relevant.
  if (max_stack_depth_ > 0 && !LockIsHeld()) {
    depth = MallocHook::GetCallerStackTrace(const_cast<void**>(region.call_stack),
                                            max_stack_depth_, kStripFrames + 1);
  }
  region.set_call_stack_depth(depth);  // record stack info fully
  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];
        }
      }
    }
  }
  if (regions_ == NULL) {  // We must have just unset the hooks,
                           // but this thread was already inside the hook.
    Unlock();
    return;
  }
  if (!recursive_insert) {
    HandleSavedRegionsLocked(&InsertRegionLocked);
  }
    // first handle adding saved regions if any
  uintptr_t start_addr = reinterpret_cast<uintptr_t>(start);
  uintptr_t end_addr = start_addr + size;
  // subtract start_addr, end_addr from all the regions
  RAW_VLOG(10, "Removing global region %p..%p; have %" PRIuS " regions",
              reinterpret_cast<void*>(start_addr),
              reinterpret_cast<void*>(end_addr),
              regions_->size());
  Region sample;
  sample.SetRegionSetKey(start_addr);
  // Only iterate over the regions that might overlap start_addr..end_addr:
  for (RegionSet::iterator region = regions_->lower_bound(sample);
       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,
              static_cast<int64>(offset));
  if (result != reinterpret_cast<void*>(MAP_FAILED)  &&  size != 0) {
    RecordRegionAddition(result, size);
  }
}

void MemoryRegionMap::MunmapHook(const void* ptr, size_t size) {
  RAW_VLOG(10, "MUnmap of %p %" PRIuS "", ptr, size);
  if (size != 0) {
    RecordRegionRemoval(ptr, size);
  }
}

void MemoryRegionMap::MremapHook(const void* result,
                                 const void* old_addr, size_t old_size,
                                 size_t new_size, int flags,
                                 const void* new_addr) {
  RAW_VLOG(10, "MRemap = 0x%" PRIxPTR " of 0x%" PRIxPTR " %" PRIuS " "
              "to %" PRIuS " flags %d new_addr=0x%" PRIxPTR,
              (uintptr_t)result, (uintptr_t)old_addr,
               old_size, new_size, flags,
               flags & MREMAP_FIXED ? (uintptr_t)new_addr : 0);
  if (result != reinterpret_cast<void*>(-1)) {
    RecordRegionRemoval(old_addr, old_size);
    RecordRegionAddition(result, new_size);
  }
}

void MemoryRegionMap::SbrkHook(const void* result, ptrdiff_t increment) {
  RAW_VLOG(10, "Sbrk = 0x%" PRIxPTR " of %" PRIdS "", (uintptr_t)result, increment);
  if (result != reinterpret_cast<void*>(-1)) {
    if (increment > 0) {
      void* new_end = sbrk(0);
      RecordRegionAddition(result, reinterpret_cast<uintptr_t>(new_end) -
                                   reinterpret_cast<uintptr_t>(result));
    } else if (increment < 0) {
      void* new_end = sbrk(0);
      RecordRegionRemoval(new_end, reinterpret_cast<uintptr_t>(result) -
                                   reinterpret_cast<uintptr_t>(new_end));
    }
  }
}

void MemoryRegionMap::LogAllLocked() {
  RAW_CHECK(LockIsHeld(), "should be held (by this thread)");
  RAW_LOG(INFO, "List of regions:");
  uintptr_t previous = 0;
  for (RegionSet::const_iterator r = regions_->begin();
       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");
}