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 |