diff options
Diffstat (limited to 'base/trace_event/heap_profiler_allocation_register.h')
| -rw-r--r-- | base/trace_event/heap_profiler_allocation_register.h | 385 |
1 files changed, 0 insertions, 385 deletions
diff --git a/base/trace_event/heap_profiler_allocation_register.h b/base/trace_event/heap_profiler_allocation_register.h deleted file mode 100644 index ac9872f001..0000000000 --- a/base/trace_event/heap_profiler_allocation_register.h +++ /dev/null @@ -1,385 +0,0 @@ -// 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 BASE_TRACE_EVENT_HEAP_PROFILER_ALLOCATION_REGISTER_H_ -#define BASE_TRACE_EVENT_HEAP_PROFILER_ALLOCATION_REGISTER_H_ - -#include <stddef.h> -#include <stdint.h> - -#include <utility> - -#include "base/bits.h" -#include "base/logging.h" -#include "base/macros.h" -#include "base/process/process_metrics.h" -#include "base/template_util.h" -#include "base/trace_event/heap_profiler_allocation_context.h" -#include "build/build_config.h" - -namespace base { -namespace trace_event { - -class AllocationRegisterTest; - -namespace internal { - -// Allocates a region of virtual address space of |size| rounded up to the -// system page size. The memory is zeroed by the system. A guard page is -// added after the end. -void* AllocateGuardedVirtualMemory(size_t size); - -// Frees a region of virtual address space allocated by a call to -// |AllocateVirtualMemory|. -void FreeGuardedVirtualMemory(void* address, size_t allocated_size); - -// Hash map that mmaps memory only once in the constructor. Its API is -// similar to std::unordered_map, only index (KVIndex) is used to address -template <size_t NumBuckets, class Key, class Value, class KeyHasher> -class FixedHashMap { - // To keep things simple we don't call destructors. - static_assert(is_trivially_destructible<Key>::value && - is_trivially_destructible<Value>::value, - "Key and Value shouldn't have destructors"); - public: - using KVPair = std::pair<const Key, Value>; - - // For implementation simplicity API uses integer index instead - // of iterators. Most operations (except Find) on KVIndex are O(1). - using KVIndex = size_t; - enum : KVIndex { kInvalidKVIndex = static_cast<KVIndex>(-1) }; - - // Capacity controls how many items this hash map can hold, and largely - // affects memory footprint. - explicit FixedHashMap(size_t capacity) - : num_cells_(capacity), - num_inserts_dropped_(0), - cells_(static_cast<Cell*>( - AllocateGuardedVirtualMemory(num_cells_ * sizeof(Cell)))), - buckets_(static_cast<Bucket*>( - AllocateGuardedVirtualMemory(NumBuckets * sizeof(Bucket)))), - free_list_(nullptr), - next_unused_cell_(0) {} - - ~FixedHashMap() { - FreeGuardedVirtualMemory(cells_, num_cells_ * sizeof(Cell)); - FreeGuardedVirtualMemory(buckets_, NumBuckets * sizeof(Bucket)); - } - - // Returns {kInvalidKVIndex, false} if the table is full. - std::pair<KVIndex, bool> Insert(const Key& key, const Value& value) { - Cell** p_cell = Lookup(key); - Cell* cell = *p_cell; - if (cell) { - return {static_cast<KVIndex>(cell - cells_), false}; // not inserted - } - - // Get a free cell and link it. - cell = GetFreeCell(); - if (!cell) { - if (num_inserts_dropped_ < - std::numeric_limits<decltype(num_inserts_dropped_)>::max()) { - ++num_inserts_dropped_; - } - return {kInvalidKVIndex, false}; - } - *p_cell = cell; - cell->p_prev = p_cell; - cell->next = nullptr; - - // Initialize key/value pair. Since key is 'const Key' this is the - // only way to initialize it. - new (&cell->kv) KVPair(key, value); - - return {static_cast<KVIndex>(cell - cells_), true}; // inserted - } - - void Remove(KVIndex index) { - DCHECK_LT(index, next_unused_cell_); - - Cell* cell = &cells_[index]; - - // Unlink the cell. - *cell->p_prev = cell->next; - if (cell->next) { - cell->next->p_prev = cell->p_prev; - } - cell->p_prev = nullptr; // mark as free - - // Add it to the free list. - cell->next = free_list_; - free_list_ = cell; - } - - KVIndex Find(const Key& key) const { - Cell* cell = *Lookup(key); - return cell ? static_cast<KVIndex>(cell - cells_) : kInvalidKVIndex; - } - - KVPair& Get(KVIndex index) { - return cells_[index].kv; - } - - const KVPair& Get(KVIndex index) const { - return cells_[index].kv; - } - - // Finds next index that has a KVPair associated with it. Search starts - // with the specified index. Returns kInvalidKVIndex if nothing was found. - // To find the first valid index, call this function with 0. Continue - // calling with the last_index + 1 until kInvalidKVIndex is returned. - KVIndex Next(KVIndex index) const { - for (;index < next_unused_cell_; ++index) { - if (cells_[index].p_prev) { - return index; - } - } - return kInvalidKVIndex; - } - - // Estimates number of bytes used in allocated memory regions. - size_t EstimateUsedMemory() const { - size_t page_size = base::GetPageSize(); - // |next_unused_cell_| is the first cell that wasn't touched, i.e. - // it's the number of touched cells. - return bits::Align(sizeof(Cell) * next_unused_cell_, page_size) + - bits::Align(sizeof(Bucket) * NumBuckets, page_size); - } - - size_t num_inserts_dropped() const { return num_inserts_dropped_; } - - private: - friend base::trace_event::AllocationRegisterTest; - - struct Cell { - KVPair kv; - Cell* next; - - // Conceptually this is |prev| in a doubly linked list. However, buckets - // also participate in the bucket's cell list - they point to the list's - // head and also need to be linked / unlinked properly. To treat these two - // cases uniformly, instead of |prev| we're storing "pointer to a Cell* - // that points to this Cell" kind of thing. So |p_prev| points to a bucket - // for the first cell in a list, and points to |next| of the previous cell - // for any other cell. With that Lookup() is the only function that handles - // buckets / cells differently. - // If |p_prev| is nullptr, the cell is in the free list. - Cell** p_prev; - }; - - using Bucket = Cell*; - - // Returns a pointer to the cell that contains or should contain the entry - // for |key|. The pointer may point at an element of |buckets_| or at the - // |next| member of an element of |cells_|. - Cell** Lookup(const Key& key) const { - // The list head is in |buckets_| at the hash offset. - Cell** p_cell = &buckets_[Hash(key)]; - - // Chase down the list until the cell that holds |key| is found, - // or until the list ends. - while (*p_cell && (*p_cell)->kv.first != key) { - p_cell = &(*p_cell)->next; - } - - return p_cell; - } - - // Returns a cell that is not being used to store an entry (either by - // recycling from the free list or by taking a fresh cell). May return - // nullptr if the hash table has run out of memory. - Cell* GetFreeCell() { - // First try to re-use a cell from the free list. - if (free_list_) { - Cell* cell = free_list_; - free_list_ = cell->next; - return cell; - } - - // If the hash table has too little capacity (when too little address space - // was reserved for |cells_|), return nullptr. - if (next_unused_cell_ >= num_cells_) { - return nullptr; - } - - // Otherwise pick the next cell that has not been touched before. - return &cells_[next_unused_cell_++]; - } - - // Returns a value in the range [0, NumBuckets - 1] (inclusive). - size_t Hash(const Key& key) const { - if (NumBuckets == (NumBuckets & ~(NumBuckets - 1))) { - // NumBuckets is a power of 2. - return KeyHasher()(key) & (NumBuckets - 1); - } else { - return KeyHasher()(key) % NumBuckets; - } - } - - // Number of cells. - size_t const num_cells_; - - // Number of calls to Insert() that were lost because the hashtable was full. - size_t num_inserts_dropped_; - - // The array of cells. This array is backed by mmapped memory. Lower indices - // are accessed first, higher indices are accessed only when the |free_list_| - // is empty. This is to minimize the amount of resident memory used. - Cell* const cells_; - - // The array of buckets (pointers into |cells_|). |buckets_[Hash(key)]| will - // contain the pointer to the linked list of cells for |Hash(key)|. - // This array is backed by mmapped memory. - mutable Bucket* buckets_; - - // The head of the free list. - Cell* free_list_; - - // The index of the first element of |cells_| that has not been used before. - // If the free list is empty and a new cell is needed, the cell at this index - // is used. This is the high water mark for the number of entries stored. - size_t next_unused_cell_; - - DISALLOW_COPY_AND_ASSIGN(FixedHashMap); -}; - -} // namespace internal - -class TraceEventMemoryOverhead; - -// The allocation register keeps track of all allocations that have not been -// freed. Internally it has two hashtables: one for Backtraces and one for -// actual allocations. Sizes of both hashtables are fixed, and this class -// allocates (mmaps) only in its constructor. -// -// When either hash table hits max size, new inserts are dropped. -class BASE_EXPORT AllocationRegister { - public: - // Details about an allocation. - struct Allocation { - const void* address; - size_t size; - AllocationContext context; - }; - - // An iterator that iterates entries in no particular order. - class BASE_EXPORT ConstIterator { - public: - void operator++(); - bool operator!=(const ConstIterator& other) const; - Allocation operator*() const; - - private: - friend class AllocationRegister; - using AllocationIndex = size_t; - - ConstIterator(const AllocationRegister& alloc_register, - AllocationIndex index); - - const AllocationRegister& register_; - AllocationIndex index_; - }; - - AllocationRegister(); - AllocationRegister(size_t allocation_capacity, size_t backtrace_capacity); - - ~AllocationRegister(); - - // Inserts allocation details into the table. If the address was present - // already, its details are updated. |address| must not be null. - // - // Returns true if an insert occurred. Inserts may fail because the table - // is full. - bool Insert(const void* address, - size_t size, - const AllocationContext& context); - - // Removes the address from the table if it is present. It is ok to call this - // with a null pointer. - void Remove(const void* address); - - // Finds allocation for the address and fills |out_allocation|. - bool Get(const void* address, Allocation* out_allocation) const; - - ConstIterator begin() const; - ConstIterator end() const; - - // Estimates memory overhead including |sizeof(AllocationRegister)|. - void EstimateTraceMemoryOverhead(TraceEventMemoryOverhead* overhead) const; - - private: - friend AllocationRegisterTest; - -// Expect lower number of allocations from mobile platforms. Load factor -// (capacity / bucket count) is kept less than 10 for optimal hashing. The -// number of buckets should be changed together with AddressHasher. -#if defined(OS_ANDROID) || defined(OS_IOS) - static const size_t kAllocationBuckets = 1 << 18; - static const size_t kAllocationCapacity = 1500000; -#else - static const size_t kAllocationBuckets = 1 << 19; - static const size_t kAllocationCapacity = 5000000; -#endif - - // 2^16 works well with BacktraceHasher. When increasing this number make - // sure BacktraceHasher still produces low number of collisions. - static const size_t kBacktraceBuckets = 1 << 16; -#if defined(OS_ANDROID) - static const size_t kBacktraceCapacity = 32000; // 22K was observed -#else - static const size_t kBacktraceCapacity = 55000; // 45K was observed on Linux -#endif - - struct BacktraceHasher { - size_t operator () (const Backtrace& backtrace) const; - }; - - using BacktraceMap = internal::FixedHashMap< - kBacktraceBuckets, - Backtrace, - size_t, // Number of references to the backtrace (the key). Incremented - // when an allocation that references the backtrace is inserted, - // and decremented when the allocation is removed. When the - // number drops to zero, the backtrace is removed from the map. - BacktraceHasher>; - - struct AllocationInfo { - size_t size; - const char* type_name; - BacktraceMap::KVIndex backtrace_index; - }; - - struct AddressHasher { - size_t operator () (const void* address) const; - }; - - using AllocationMap = internal::FixedHashMap< - kAllocationBuckets, - const void*, - AllocationInfo, - AddressHasher>; - - BacktraceMap::KVIndex InsertBacktrace(const Backtrace& backtrace); - void RemoveBacktrace(BacktraceMap::KVIndex index); - - Allocation GetAllocation(AllocationMap::KVIndex) const; - - AllocationMap allocations_; - BacktraceMap backtraces_; - - // Sentinel used when the |backtraces_| table is full. - // - // This is a slightly abstraction to allow for constant propagation. It - // knows that the sentinel will be the first item inserted into the table - // and that the first index retuned will be 0. The constructor DCHECKs - // this assumption. - enum : BacktraceMap::KVIndex { kOutOfStorageBacktraceIndex = 0 }; - - DISALLOW_COPY_AND_ASSIGN(AllocationRegister); -}; - -} // namespace trace_event -} // namespace base - -#endif // BASE_TRACE_EVENT_HEAP_PROFILER_ALLOCATION_REGISTER_H_ |