OLD | NEW |
(Empty) | |
| 1 // Copyright 2015 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. |
| 4 |
| 5 #ifndef BASE_TRACE_EVENT_MEMORY_PROFILER_ALLOCATION_REGISTER_H_ |
| 6 #define BASE_TRACE_EVENT_MEMORY_PROFILER_ALLOCATION_REGISTER_H_ |
| 7 |
| 8 #include <stdint.h> |
| 9 |
| 10 #include "base/logging.h" |
| 11 #include "base/trace_event/memory_profiler_allocation_context.h" |
| 12 |
| 13 namespace base { |
| 14 namespace trace_event { |
| 15 |
| 16 // The allocation register keeps track of all allocations that have not been |
| 17 // freed. It is a memory map-backed hash table that stores size and context |
| 18 // indexed by address. The hash table is tailored specifically for this use |
| 19 // case. The common case is that an entry is inserted and removed after a |
| 20 // while, lookup without modifying the table is not an intended use case. The |
| 21 // hash table is implemented as an array of linked lists. The size of this |
| 22 // array is fixed, but it does not limit the amount of entries that can be |
| 23 // stored. |
| 24 // |
| 25 // Replaying a recording of Chrome's allocations and frees against this hash |
| 26 // table takes about 15% of the time that it takes to replay them against |
| 27 // |std::map|. |
| 28 class BASE_EXPORT AllocationRegister { |
| 29 public: |
| 30 // The data stored in the hash table; |
| 31 // contains the details about an allocation. |
| 32 struct Allocation { |
| 33 void* address; |
| 34 size_t size; |
| 35 AllocationContext context; |
| 36 }; |
| 37 |
| 38 // An iterator that iterates entries in the hash table efficiently, but in no |
| 39 // particular order. It can do this by iterating the cells and ignoring the |
| 40 // linked lists altogether. Instead of checking whether a cell is in the free |
| 41 // list to see if it should be skipped, a null address is used to indicate |
| 42 // that a cell is free. |
| 43 class BASE_EXPORT ConstIterator { |
| 44 public: |
| 45 void operator++(); |
| 46 bool operator!=(const ConstIterator& other) const; |
| 47 const Allocation& operator*() const; |
| 48 |
| 49 private: |
| 50 friend class AllocationRegister; |
| 51 using CellIndex = uint32_t; |
| 52 |
| 53 ConstIterator(const AllocationRegister& alloc_register, CellIndex index); |
| 54 |
| 55 const AllocationRegister& register_; |
| 56 CellIndex index_; |
| 57 }; |
| 58 |
| 59 AllocationRegister(); |
| 60 ~AllocationRegister(); |
| 61 |
| 62 // Inserts allocation details into the table. If the address was present |
| 63 // already, its details are updated. |address| must not be null. (This is |
| 64 // because null is used to mark free cells, to allow efficient iteration of |
| 65 // the hash table.) |
| 66 void Insert(void* address, size_t size, AllocationContext context); |
| 67 |
| 68 // Removes the address from the table if it is present. It is ok to call this |
| 69 // with a null pointer. |
| 70 void Remove(void* address); |
| 71 |
| 72 ConstIterator begin() const; |
| 73 ConstIterator end() const; |
| 74 |
| 75 private: |
| 76 friend class AllocationRegisterTest; |
| 77 using CellIndex = uint32_t; |
| 78 |
| 79 // A cell can store allocation details (size and context) by address. Cells |
| 80 // are part of a linked list via the |next| member. This list is either the |
| 81 // list for a particular hash, or the free list. All cells are contiguous in |
| 82 // memory in one big array. Therefore, on 64-bit systems, space can be saved |
| 83 // by storing 32-bit indices instead of pointers as links. Index 0 is used as |
| 84 // the list terminator. |
| 85 struct Cell { |
| 86 CellIndex next; |
| 87 Allocation allocation; |
| 88 }; |
| 89 |
| 90 // The number of buckets, 2^18, approximately 260 000, has been tuned for |
| 91 // Chrome's typical number of outstanding allocations. (This number varies |
| 92 // between processes. Most processes have a sustained load of ~30k unfreed |
| 93 // allocations, but some processes have peeks around 100k-400k allocations.) |
| 94 // Because of the size of the table, it is likely that every |buckets_| |
| 95 // access and every |cells_| access will incur a cache miss. Microbenchmarks |
| 96 // suggest that it is worthwile to use more memory for the table to avoid |
| 97 // chasing down the linked list, until the size is 2^18. The number of buckets |
| 98 // is a power of two so modular indexing can be done with bitwise and. |
| 99 static const uint32_t kNumBuckets = 0x40000; |
| 100 static const uint32_t kNumBucketsMask = kNumBuckets - 1; |
| 101 |
| 102 // Reserve address space to store at most this number of entries. High |
| 103 // capacity does not imply high memory usage due to the access pattern. The |
| 104 // only constraint on the number of cells is that on 32-bit systems address |
| 105 // space is scarce (i.e. reserving 2GiB of address space for the entries is |
| 106 // not an option). A value of ~3M entries is large enough to handle spikes in |
| 107 // the number of allocations, and modest enough to require no more than a few |
| 108 // dozens of MiB of address space. |
| 109 static const uint32_t kNumCells = kNumBuckets * 10; |
| 110 |
| 111 // Returns a value in the range [0, kNumBuckets - 1] (inclusive). |
| 112 static uint32_t Hash(void* address); |
| 113 |
| 114 // Allocates a region of virtual address space of |min_size| rounded up to the |
| 115 // system page size. The memory is zeroed by the system. A guard page is added |
| 116 // after the end. |
| 117 static void* AllocateVirtualMemory(size_t size); |
| 118 |
| 119 // Frees a region of virtual address space allocated by a call to |
| 120 // |AllocateVirtualMemory|. |
| 121 static void FreeVirtualMemory(void* address, size_t allocated_size); |
| 122 |
| 123 // Returns a pointer to the variable that contains or should contain the |
| 124 // index of the cell that stores the entry for |address|. The pointer may |
| 125 // point at an element of |buckets_| or at the |next| member of an element of |
| 126 // |cells_|. If the value pointed at is 0, |address| is not in the table. |
| 127 CellIndex* Lookup(void* address); |
| 128 |
| 129 // Takes a cell that is not being used to store an entry (either by recycling |
| 130 // from the free list or by taking a fresh cell) and returns its index. |
| 131 CellIndex GetFreeCell(); |
| 132 |
| 133 // The array of cells. This array is backed by mmapped memory. Lower indices |
| 134 // are accessed first, higher indices are only accessed when required. In |
| 135 // this way, even if a huge amount of address space has been mmapped, only |
| 136 // the cells that are actually used will be backed by physical memory. |
| 137 Cell* const cells_; |
| 138 |
| 139 // The array of indices into |cells_|. |buckets_[Hash(address)]| will contain |
| 140 // the index of the head of the linked list for |Hash(key)|. A value of 0 |
| 141 // indicates an empty list. This array is backed by mmapped memory. |
| 142 CellIndex* const buckets_; |
| 143 |
| 144 // The head of the free list. This is the index of the cell. A value of 0 |
| 145 // means that the free list is empty. |
| 146 CellIndex free_list_; |
| 147 |
| 148 // The index of the first element of |cells_| that has not been used before. |
| 149 // If the free list is empty and a new cell is needed, the cell at this index |
| 150 // is used. This is the high water mark for the number of entries stored. |
| 151 CellIndex next_unused_cell_; |
| 152 |
| 153 DISALLOW_COPY_AND_ASSIGN(AllocationRegister); |
| 154 }; |
| 155 |
| 156 } // namespace trace_event |
| 157 } // namespace base |
| 158 |
| 159 #endif // BASE_TRACE_EVENT_MEMORY_PROFILER_ALLOCATION_REGISTER_H_ |
OLD | NEW |