// Copyright 2015 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "base/trace_event/heap_profiler_allocation_register.h"

#include <algorithm>
#include <limits>

#include "base/trace_event/trace_event_memory_overhead.h"

namespace base {
namespace trace_event {

AllocationRegister::ConstIterator::ConstIterator(
    const AllocationRegister& alloc_register,
    AllocationIndex index)
    : register_(alloc_register), index_(index) {}

void AllocationRegister::ConstIterator::operator++() {
  index_ = register_.allocations_.Next(index_ + 1);
}

bool AllocationRegister::ConstIterator::operator!=(
    const ConstIterator& other) const {
  return index_ != other.index_;
}

AllocationRegister::Allocation AllocationRegister::ConstIterator::operator*()
    const {
  return register_.GetAllocation(index_);
}

size_t AllocationRegister::BacktraceHasher::operator()(
    const Backtrace& backtrace) const {
  const size_t kSampleLength = 10;

  uintptr_t total_value = 0;

  size_t head_end = std::min(backtrace.frame_count, kSampleLength);
  for (size_t i = 0; i != head_end; ++i) {
    total_value += reinterpret_cast<uintptr_t>(backtrace.frames[i].value);
  }

  size_t tail_start = backtrace.frame_count -
                      std::min(backtrace.frame_count - head_end, kSampleLength);
  for (size_t i = tail_start; i != backtrace.frame_count; ++i) {
    total_value += reinterpret_cast<uintptr_t>(backtrace.frames[i].value);
  }

  total_value += backtrace.frame_count;

  // These magic constants give best results in terms of average collisions
  // per backtrace. They were found by replaying real backtraces from Linux
  // and Android against different hash functions.
  return (total_value * 131101) >> 14;
}

size_t AllocationRegister::AddressHasher::operator()(
    const void* address) const {
  // The multiplicative hashing scheme from [Knuth 1998]. The value of |a| has
  // been chosen carefully based on measurements with real-word data (addresses
  // recorded from a Chrome trace run). It is the first prime after 2^17. For
  // |shift|, 15 yield good results for both 2^18 and 2^19 bucket sizes.
  // Microbenchmarks show that this simple scheme outperforms fancy hashes like
  // Murmur3 by 20 to 40 percent.
  const uintptr_t key = reinterpret_cast<uintptr_t>(address);
  const uintptr_t a = 131101;
  const uintptr_t shift = 15;
  const uintptr_t h = (key * a) >> shift;
  return h;
}

AllocationRegister::AllocationRegister()
    : AllocationRegister(kAllocationCapacity, kBacktraceCapacity) {}

AllocationRegister::AllocationRegister(size_t allocation_capacity,
                                       size_t backtrace_capacity)
    : allocations_(allocation_capacity), backtraces_(backtrace_capacity) {
  Backtrace sentinel = {};
  sentinel.frames[0] = StackFrame::FromThreadName("[out of heap profiler mem]");
  sentinel.frame_count = 1;

  // Rationale for max / 2: in theory we could just start the sentinel with a
  // refcount == 0. However, using max / 2 allows short circuiting of the
  // conditional in RemoveBacktrace() keeping the sentinel logic out of the fast
  // path. From a functional viewpoint, the sentinel is safe even if we wrap
  // over refcount because .
  BacktraceMap::KVPair::second_type sentinel_refcount =
      std::numeric_limits<BacktraceMap::KVPair::second_type>::max() / 2;
  auto index_and_flag = backtraces_.Insert(sentinel, sentinel_refcount);
  DCHECK(index_and_flag.second);
  DCHECK_EQ(index_and_flag.first, kOutOfStorageBacktraceIndex);
}

AllocationRegister::~AllocationRegister() {}

bool AllocationRegister::Insert(const void* address,
                                size_t size,
                                const AllocationContext& context) {
  DCHECK(address != nullptr);
  if (size == 0) {
    return false;
  }

  AllocationInfo info = {size, context.type_name,
                         InsertBacktrace(context.backtrace)};

  // Try to insert the allocation.
  auto index_and_flag = allocations_.Insert(address, info);
  if (!index_and_flag.second &&
      index_and_flag.first != AllocationMap::kInvalidKVIndex) {
    // |address| is already there - overwrite the allocation info.
    auto& old_info = allocations_.Get(index_and_flag.first).second;
    RemoveBacktrace(old_info.backtrace_index);
    old_info = info;
    return true;
  }

  return index_and_flag.second;
}

void AllocationRegister::Remove(const void* address) {
  auto index = allocations_.Find(address);
  if (index == AllocationMap::kInvalidKVIndex) {
    return;
  }

  const AllocationInfo& info = allocations_.Get(index).second;
  RemoveBacktrace(info.backtrace_index);
  allocations_.Remove(index);
}

bool AllocationRegister::Get(const void* address,
                             Allocation* out_allocation) const {
  auto index = allocations_.Find(address);
  if (index == AllocationMap::kInvalidKVIndex) {
    return false;
  }

  if (out_allocation) {
    *out_allocation = GetAllocation(index);
  }
  return true;
}

AllocationRegister::ConstIterator AllocationRegister::begin() const {
  return ConstIterator(*this, allocations_.Next(0));
}

AllocationRegister::ConstIterator AllocationRegister::end() const {
  return ConstIterator(*this, AllocationMap::kInvalidKVIndex);
}

void AllocationRegister::EstimateTraceMemoryOverhead(
    TraceEventMemoryOverhead* overhead) const {
  size_t allocated = sizeof(AllocationRegister);
  size_t resident = sizeof(AllocationRegister) +
                    allocations_.EstimateUsedMemory() +
                    backtraces_.EstimateUsedMemory();
  overhead->Add("AllocationRegister", allocated, resident);
}

AllocationRegister::BacktraceMap::KVIndex AllocationRegister::InsertBacktrace(
    const Backtrace& backtrace) {
  auto index = backtraces_.Insert(backtrace, 0).first;
  if (index == BacktraceMap::kInvalidKVIndex)
    return kOutOfStorageBacktraceIndex;
  auto& backtrace_and_count = backtraces_.Get(index);
  backtrace_and_count.second++;
  return index;
}

void AllocationRegister::RemoveBacktrace(BacktraceMap::KVIndex index) {
  auto& backtrace_and_count = backtraces_.Get(index);
  if (--backtrace_and_count.second == 0 &&
      index != kOutOfStorageBacktraceIndex) {
    // Backtrace is not referenced anymore - remove it.
    backtraces_.Remove(index);
  }
}

AllocationRegister::Allocation AllocationRegister::GetAllocation(
    AllocationMap::KVIndex index) const {
  const auto& address_and_info = allocations_.Get(index);
  const auto& backtrace_and_count =
      backtraces_.Get(address_and_info.second.backtrace_index);
  return {address_and_info.first, address_and_info.second.size,
          AllocationContext(backtrace_and_count.first,
                            address_and_info.second.type_name)};
}

}  // namespace trace_event
}  // namespace base