// 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.

#ifndef COMPONENTS_METRICS_LEAK_DETECTOR_LEAK_DETECTOR_IMPL_H_
#define COMPONENTS_METRICS_LEAK_DETECTOR_LEAK_DETECTOR_IMPL_H_

#include <stddef.h>
#include <stdint.h>

#include <list>
#include <vector>

#include "base/containers/hash_tables.h"
#include "base/macros.h"
#include "components/metrics/leak_detector/call_stack_manager.h"
#include "components/metrics/leak_detector/custom_allocator.h"
#include "components/metrics/leak_detector/leak_analyzer.h"
#include "components/metrics/leak_detector/stl_allocator.h"

namespace metrics {
namespace leak_detector {

class CallStackTable;

// Class that contains the actual leak detection mechanism.
// Not thread-safe.
class LeakDetectorImpl {
 public:
  // STL types that are safe to use within the memory leak detector. They use
  // CustomAllocator to avoid recursive malloc hook invocation when analyzing
  // allocs and frees.
  template <typename T>
  using InternalList = std::list<T, STLAllocator<T, CustomAllocator>>;
  template <typename T>
  using InternalVector = std::vector<T, STLAllocator<T, CustomAllocator>>;

  // Leak report generated by LeakDetectorImpl.
  class LeakReport {
   public:
    // Stores a record of the allocation bookkeeping taken at a single moment in
    // time.
    struct AllocationBreakdown {
      AllocationBreakdown();
      AllocationBreakdown(const AllocationBreakdown& other);
      ~AllocationBreakdown();

      // The contents of |LeakDetectorImpl::size_breakdown_history_| when this
      // report was generated. See comment description of that variable.
      InternalVector<uint32_t> counts_by_size;

      // The net number of allocations with alloc size of
      // |Leakreport::alloc_size_bytes_| allocated from |call_stack_|, at the
      // time this record was generated.
      uint32_t count_for_call_stack;
    };

    LeakReport();
    LeakReport(const LeakReport& other);
    ~LeakReport();

    size_t alloc_size_bytes() const { return alloc_size_bytes_; }

    const InternalVector<uintptr_t>& call_stack() const { return call_stack_; }

    const InternalVector<AllocationBreakdown>& alloc_breakdown_history() const {
      return alloc_breakdown_history_;
    }

    size_t num_rising_intervals() const { return num_rising_intervals_; }

    uint32_t num_allocs_increase() const { return num_allocs_increase_; }

    void set_num_rising_intervals(size_t num_rising_intervals) {
      num_rising_intervals_ = num_rising_intervals;
    }

    // Used to compare the contents of two leak reports.
    bool operator<(const LeakReport& other) const;

   private:
    // LeakDetectorImpl needs access to class members when creating a new leak
    // report.
    friend class LeakDetectorImpl;

    // Number of bytes allocated by the leak site during each allocation.
    size_t alloc_size_bytes_;

    // Number of intervals in the last uptrend.
    size_t num_rising_intervals_;

    // Net number of bytes allocated in the last uptrend.
    uint32_t num_allocs_increase_;

    // Unlike the CallStack struct, which consists of addresses, this call stack
    // will contain offsets in the executable binary.
    InternalVector<uintptr_t> call_stack_;

    // Records of allocation bookkeeping over time. The first element is the
    // oldest entry and the last element is the newest.
    InternalVector<AllocationBreakdown> alloc_breakdown_history_;
  };

  LeakDetectorImpl(uintptr_t mapping_addr,
                   size_t mapping_size,
                   int size_suspicion_threshold,
                   int call_stack_suspicion_threshold);
  ~LeakDetectorImpl();

  // Indicates whether the given allocation size has an associated call stack
  // table, and thus requires a stack unwind.
  bool ShouldGetStackTraceForSize(size_t size) const;

  // Record allocs and frees.
  void RecordAlloc(const void* ptr,
                   size_t size,
                   int stack_depth,
                   const void* const call_stack[]);
  void RecordFree(const void* ptr);

  // Run check for possible leaks based on the current profiling data.
  void TestForLeaks(InternalVector<LeakReport>* reports, size_t timestamp);

 private:
  // A record of allocations for a particular size.
  struct AllocSizeEntry {
    // Number of allocations and frees for this size.
    uint32_t num_allocs;
    uint32_t num_frees;

    // A stack table, if this size is being profiled for stack as well.
    CallStackTable* stack_table;

    // Historical records of allocation breakdown by call site, for a particular
    // allocation size. Each entry in the list is a RankedSet containing the top
    // call sites ordered by most number of call sites, collected during a leak
    // analysis. The oldest record is at the head and the newest record is at
    // the tail.
    InternalList<RankedSet> call_site_breakdown_history;

    AllocSizeEntry();
    ~AllocSizeEntry();

    // Returns net number of allocs.
    uint32_t GetNetAllocs() const { return num_allocs - num_frees; }
  };

  // Info for a single allocation.
  struct AllocInfo {
    AllocInfo() : call_stack(nullptr) {}

    // Number of bytes in this allocation.
    size_t size;

    // Points to a unique call stack.
    const CallStack* call_stack;
  };

  // Allocator class for allocation entry map. Maps allocated addresses to
  // AllocInfo objects.
  using AllocationEntryAllocator =
      STLAllocator<std::pair<const uintptr_t, AllocInfo>, CustomAllocator>;

  // Hash class for addresses.
  struct AddressHash {
    size_t operator()(uintptr_t addr) const;
  };

  // Returns the offset of |ptr| within the current binary. If it is not in the
  // current binary, return |UINTPTR_MAX|.
  uintptr_t GetOffset(const void* ptr) const;

  // Record some of the current allocation bookkeeping. The net number of allocs
  // per size is recorded in |size_breakdown_history_|. The net number of allocs
  // per call site for each size is recorded in
  // |AllocSizeEntry::call_site_breakdown_history|.
  // Argument |timestamp| is used to update information about drops in
  // allocation number for each stored call stack.
  //
  // Not all the net alloc counts are recorded. And the number of historical
  // records kept is capped. If adding a new record exceeds that limit, the
  // oldest record is discarded. See the function definition for more details.
  void RecordCurrentAllocationDataInHistory(size_t timestamp);

  // Store the data collected by RecordCurrentAllocationDataInHistory() in
  // |*report|. Not all net alloc counts per call site will be stored, only the
  // count for size=|size| and made from |call_site|. Also information
  // about the last uptrend in net allocations for |size| and |call_site|
  // is recorded with help of |timestamp|.
  void StoreHistoricalDataInReport(size_t size, const CallStack* call_site,
                                   LeakReport* report, size_t timestamp);

  // Decrements the cooldown counter (value) for each entry in
  // |cooldowns_per_leak_|. If the cooldown counter reaches 0, the entry is
  // removed. Thus, all extantentries in |cooldowns_per_leak_| maintain a
  // positive count.
  void UpdateLeakCooldowns();

  // Returns true if a particular leak signature (alloc size + call site) does
  // not have an active cooldown counter (i.e. does not have an entry in
  // |cooldowns_per_leak_|.
  bool ReadyToGenerateReport(size_t size, const CallStack* call_stack) const;

  // Resets the counter for a leak signature (alloc size + call site) in
  // |cooldowns_per_leak_| to the max cooldown value. Creates a new entry in the
  // container if none exists for this leak signature.
  void ResetLeakCooldown(size_t size, const CallStack* call_stack);

  // Owns all unique call stack objects, which are allocated on the heap. Any
  // other class or function that references a call stack must get it from here,
  // but may not take ownership of the call stack object.
  CallStackManager call_stack_manager_;

  // Allocation stats.
  uint64_t num_allocs_;
  uint64_t num_frees_;
  uint64_t alloc_size_;
  uint64_t free_size_;

  uint32_t num_allocs_with_call_stack_;
  uint32_t num_stack_tables_;

  // Stores all individual recorded allocations.
  base::hash_map<uintptr_t,
                 AllocInfo,
                 AddressHash,
                 std::equal_to<uintptr_t>,
                 AllocationEntryAllocator> address_map_;

  // Used to analyze potential leak patterns in the allocation sizes.
  LeakAnalyzer size_leak_analyzer_;

  // Allocation stats for each size.
  InternalVector<AllocSizeEntry> size_entries_;

  // Tracks the net number of allocations per size over time. Each list item is
  // a vector containing the allocation counts for each size. The vector element
  // with index i corresponds to sizes |i * 4| to |i * 4 + 3|. The oldest size
  // breakdowns is at the head of the list, and new size breakdowns should be
  // added to the tail of the list.
  InternalList<InternalVector<uint32_t>> size_breakdown_history_;

  // Key: leak signature (alloc size + call site)
  // Value: number of leak analyses before another leak report can be generated
  //        for that leak.
  std::map<std::pair<size_t, const CallStack*>, size_t> cooldowns_per_leak_;

  // Address mapping info of the current binary.
  uintptr_t mapping_addr_;
  size_t mapping_size_;

  // Number of consecutive times a call stack must trigger suspicion to be
  // considered a leak suspect.
  int call_stack_suspicion_threshold_;

  DISALLOW_COPY_AND_ASSIGN(LeakDetectorImpl);
};

}  // namespace leak_detector
}  // namespace metrics

#endif  // COMPONENTS_METRICS_LEAK_DETECTOR_LEAK_DETECTOR_IMPL_H_