Separate Simple Backend creation from initialization.
[chromium-blink-merge.git] / third_party / tcmalloc / chromium / src / memory_region_map.h
blobbe191a90c168364a19b39ead9495b143420e4c67
1 /* Copyright (c) 2006, Google Inc.
2 * All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
6 * met:
7 *
8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above
11 * copyright notice, this list of conditions and the following disclaimer
12 * in the documentation and/or other materials provided with the
13 * distribution.
14 * * Neither the name of Google Inc. nor the names of its
15 * contributors may be used to endorse or promote products derived from
16 * this software without specific prior written permission.
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 * ---
31 * Author: Maxim Lifantsev
34 #ifndef BASE_MEMORY_REGION_MAP_H_
35 #define BASE_MEMORY_REGION_MAP_H_
37 #include <config.h>
39 #ifdef HAVE_PTHREAD
40 #include <pthread.h>
41 #endif
42 #include <stddef.h>
43 #include <set>
44 #include "base/stl_allocator.h"
45 #include "base/spinlock.h"
46 #include "base/thread_annotations.h"
47 #include "base/low_level_alloc.h"
48 #include "heap-profile-stats.h"
50 // TODO(maxim): add a unittest:
51 // execute a bunch of mmaps and compare memory map what strace logs
52 // execute a bunch of mmap/munmup and compare memory map with
53 // own accounting of what those mmaps generated
55 // Thread-safe class to collect and query the map of all memory regions
56 // in a process that have been created with mmap, munmap, mremap, sbrk.
57 // For each memory region, we keep track of (and provide to users)
58 // the stack trace that allocated that memory region.
59 // The recorded stack trace depth is bounded by
60 // a user-supplied max_stack_depth parameter of Init().
61 // After initialization with Init()
62 // (which can happened even before global object constructor execution)
63 // we collect the map by installing and monitoring MallocHook-s
64 // to mmap, munmap, mremap, sbrk.
65 // At any time one can query this map via provided interface.
66 // For more details on the design of MemoryRegionMap
67 // see the comment at the top of our .cc file.
68 class MemoryRegionMap {
69 private:
70 // Max call stack recording depth supported by Init(). Set it to be
71 // high enough for all our clients. Note: we do not define storage
72 // for this (doing that requires special handling in windows), so
73 // don't take the address of it!
74 static const int kMaxStackDepth = 32;
76 // Size of the hash table of buckets. A structure of the bucket table is
77 // described in heap-profile-stats.h.
78 static const int kHashTableSize = 179999;
80 public:
81 // interface ================================================================
83 // Every client of MemoryRegionMap must call Init() before first use,
84 // and Shutdown() after last use. This allows us to reference count
85 // this (singleton) class properly. MemoryRegionMap assumes it's the
86 // only client of MallocHooks, so a client can only register other
87 // MallocHooks after calling Init() and must unregister them before
88 // calling Shutdown().
90 // Initialize this module to record memory allocation stack traces.
91 // Stack traces that have more than "max_stack_depth" frames
92 // are automatically shrunk to "max_stack_depth" when they are recorded.
93 // Init() can be called more than once w/o harm, largest max_stack_depth
94 // will be the effective one.
95 // When "use_buckets" is true, then counts of mmap and munmap sizes will be
96 // recorded with each stack trace. If Init() is called more than once, then
97 // counting will be effective after any call contained "use_buckets" of true.
98 // It will install mmap, munmap, mremap, sbrk hooks
99 // and initialize arena_ and our hook and locks, hence one can use
100 // MemoryRegionMap::Lock()/Unlock() to manage the locks.
101 // Uses Lock/Unlock inside.
102 static void Init(int max_stack_depth, bool use_buckets);
104 // Try to shutdown this module undoing what Init() did.
105 // Returns true iff could do full shutdown (or it was not attempted).
106 // Full shutdown is attempted when the number of Shutdown() calls equals
107 // the number of Init() calls.
108 static bool Shutdown();
110 // Return true if MemoryRegionMap is initialized and recording, i.e. when
111 // then number of Init() calls are more than the number of Shutdown() calls.
112 static bool IsRecordingLocked();
114 // Locks to protect our internal data structures.
115 // These also protect use of arena_ if our Init() has been done.
116 // The lock is recursive.
117 static void Lock() EXCLUSIVE_LOCK_FUNCTION(lock_);
118 static void Unlock() UNLOCK_FUNCTION(lock_);
120 // Returns true when the lock is held by this thread (for use in RAW_CHECK-s).
121 static bool LockIsHeld();
123 // Locker object that acquires the MemoryRegionMap::Lock
124 // for the duration of its lifetime (a C++ scope).
125 class LockHolder {
126 public:
127 LockHolder() { Lock(); }
128 ~LockHolder() { Unlock(); }
129 private:
130 DISALLOW_COPY_AND_ASSIGN(LockHolder);
133 // A memory region that we know about through malloc_hook-s.
134 // This is essentially an interface through which MemoryRegionMap
135 // exports the collected data to its clients. Thread-compatible.
136 struct Region {
137 uintptr_t start_addr; // region start address
138 uintptr_t end_addr; // region end address
139 int call_stack_depth; // number of caller stack frames that we saved
140 const void* call_stack[kMaxStackDepth]; // caller address stack array
141 // filled to call_stack_depth size
142 bool is_stack; // does this region contain a thread's stack:
143 // a user of MemoryRegionMap supplies this info
145 // Convenience accessor for call_stack[0],
146 // i.e. (the program counter of) the immediate caller
147 // of this region's allocation function,
148 // but it also returns NULL when call_stack_depth is 0,
149 // i.e whe we weren't able to get the call stack.
150 // This usually happens in recursive calls, when the stack-unwinder
151 // calls mmap() which in turn calls the stack-unwinder.
152 uintptr_t caller() const {
153 return reinterpret_cast<uintptr_t>(call_stack_depth >= 1
154 ? call_stack[0] : NULL);
157 // Return true iff this region overlaps region x.
158 bool Overlaps(const Region& x) const {
159 return start_addr < x.end_addr && end_addr > x.start_addr;
162 private: // helpers for MemoryRegionMap
163 friend class MemoryRegionMap;
165 // The ways we create Region-s:
166 void Create(const void* start, size_t size) {
167 start_addr = reinterpret_cast<uintptr_t>(start);
168 end_addr = start_addr + size;
169 is_stack = false; // not a stack till marked such
170 call_stack_depth = 0;
171 AssertIsConsistent();
173 void set_call_stack_depth(int depth) {
174 RAW_DCHECK(call_stack_depth == 0, ""); // only one such set is allowed
175 call_stack_depth = depth;
176 AssertIsConsistent();
179 // The ways we modify Region-s:
180 void set_is_stack() { is_stack = true; }
181 void set_start_addr(uintptr_t addr) {
182 start_addr = addr;
183 AssertIsConsistent();
185 void set_end_addr(uintptr_t addr) {
186 end_addr = addr;
187 AssertIsConsistent();
190 // Verifies that *this contains consistent data, crashes if not the case.
191 void AssertIsConsistent() const {
192 RAW_DCHECK(start_addr < end_addr, "");
193 RAW_DCHECK(call_stack_depth >= 0 &&
194 call_stack_depth <= kMaxStackDepth, "");
197 // Post-default construction helper to make a Region suitable
198 // for searching in RegionSet regions_.
199 void SetRegionSetKey(uintptr_t addr) {
200 // make sure *this has no usable data:
201 if (DEBUG_MODE) memset(this, 0xFF, sizeof(*this));
202 end_addr = addr;
205 // Note: call_stack[kMaxStackDepth] as a member lets us make Region
206 // a simple self-contained struct with correctly behaving bit-vise copying.
207 // This simplifies the code of this module but wastes some memory:
208 // in most-often use case of this module (leak checking)
209 // only one call_stack element out of kMaxStackDepth is actually needed.
210 // Making the storage for call_stack variable-sized,
211 // substantially complicates memory management for the Region-s:
212 // as they need to be created and manipulated for some time
213 // w/o any memory allocations, yet are also given out to the users.
216 // Find the region that covers addr and write its data into *result if found,
217 // in which case *result gets filled so that it stays fully functional
218 // even when the underlying region gets removed from MemoryRegionMap.
219 // Returns success. Uses Lock/Unlock inside.
220 static bool FindRegion(uintptr_t addr, Region* result);
222 // Find the region that contains stack_top, mark that region as
223 // a stack region, and write its data into *result if found,
224 // in which case *result gets filled so that it stays fully functional
225 // even when the underlying region gets removed from MemoryRegionMap.
226 // Returns success. Uses Lock/Unlock inside.
227 static bool FindAndMarkStackRegion(uintptr_t stack_top, Region* result);
229 // Iterate over the buckets which store mmap and munmap counts per stack
230 // trace. It calls "callback" for each bucket, and passes "arg" to it.
231 template<class Type>
232 static void IterateBuckets(void (*callback)(const HeapProfileBucket*, Type),
233 Type arg);
235 // Get the bucket whose caller stack trace is "key". The stack trace is
236 // used to a depth of "depth" at most. The requested bucket is created if
237 // needed.
238 // The bucket table is described in heap-profile-stats.h.
239 static HeapProfileBucket* GetBucket(int depth, const void* const key[]);
241 private: // our internal types ==============================================
243 // Region comparator for sorting with STL
244 struct RegionCmp {
245 bool operator()(const Region& x, const Region& y) const {
246 return x.end_addr < y.end_addr;
250 // We allocate STL objects in our own arena.
251 struct MyAllocator {
252 static void *Allocate(size_t n) {
253 return LowLevelAlloc::AllocWithArena(n, arena_);
255 static void Free(const void *p, size_t /* n */) {
256 LowLevelAlloc::Free(const_cast<void*>(p));
260 // Set of the memory regions
261 typedef std::set<Region, RegionCmp,
262 STL_Allocator<Region, MyAllocator> > RegionSet;
264 public: // more in-depth interface ==========================================
266 // STL iterator with values of Region
267 typedef RegionSet::const_iterator RegionIterator;
269 // Return the begin/end iterators to all the regions.
270 // These need Lock/Unlock protection around their whole usage (loop).
271 // Even when the same thread causes modifications during such a loop
272 // (which are permitted due to recursive locking)
273 // the loop iterator will still be valid as long as its region
274 // has not been deleted, but EndRegionLocked should be
275 // re-evaluated whenever the set of regions has changed.
276 static RegionIterator BeginRegionLocked();
277 static RegionIterator EndRegionLocked();
279 // Return the accumulated sizes of mapped and unmapped regions.
280 static int64 MapSize() { return map_size_; }
281 static int64 UnmapSize() { return unmap_size_; }
283 // Effectively private type from our .cc =================================
284 // public to let us declare global objects:
285 union RegionSetRep;
287 private:
288 // representation ===========================================================
290 // Counter of clients of this module that have called Init().
291 static int client_count_;
293 // Maximal number of caller stack frames to save (>= 0).
294 static int max_stack_depth_;
296 // Arena used for our allocations in regions_.
297 static LowLevelAlloc::Arena* arena_;
299 // Set of the mmap/sbrk/mremap-ed memory regions
300 // To be accessed *only* when Lock() is held.
301 // Hence we protect the non-recursive lock used inside of arena_
302 // with our recursive Lock(). This lets a user prevent deadlocks
303 // when threads are stopped by ListAllProcessThreads at random spots
304 // simply by acquiring our recursive Lock() before that.
305 static RegionSet* regions_;
307 // Lock to protect regions_ and buckets_ variables and the data behind.
308 static SpinLock lock_;
309 // Lock to protect the recursive lock itself.
310 static SpinLock owner_lock_;
312 // Recursion count for the recursive lock.
313 static int recursion_count_;
314 // The thread id of the thread that's inside the recursive lock.
315 static pthread_t lock_owner_tid_;
317 // Total size of all mapped pages so far
318 static int64 map_size_;
319 // Total size of all unmapped pages so far
320 static int64 unmap_size_;
322 // Bucket hash table which is described in heap-profile-stats.h.
323 static HeapProfileBucket** bucket_table_ GUARDED_BY(lock_);
324 static int num_buckets_ GUARDED_BY(lock_);
326 // The following members are local to MemoryRegionMap::GetBucket()
327 // and MemoryRegionMap::HandleSavedBucketsLocked()
328 // and are file-level to ensure that they are initialized at load time.
330 // These are used as temporary storage to break the infinite cycle of mmap
331 // calling our hook which (sometimes) causes mmap. It must be a static
332 // fixed-size array. The size 20 is just an expected value for safety.
333 // The details are described in memory_region_map.cc.
335 // Number of unprocessed bucket inserts.
336 static int saved_buckets_count_ GUARDED_BY(lock_);
338 // Unprocessed inserts (must be big enough to hold all mmaps that can be
339 // caused by a GetBucket call).
340 // Bucket has no constructor, so that c-tor execution does not interfere
341 // with the any-time use of the static memory behind saved_buckets.
342 static HeapProfileBucket saved_buckets_[20] GUARDED_BY(lock_);
344 static const void* saved_buckets_keys_[20][kMaxStackDepth] GUARDED_BY(lock_);
346 // helpers ==================================================================
348 // Helper for FindRegion and FindAndMarkStackRegion:
349 // returns the region covering 'addr' or NULL; assumes our lock_ is held.
350 static const Region* DoFindRegionLocked(uintptr_t addr);
352 // Verifying wrapper around regions_->insert(region)
353 // To be called to do InsertRegionLocked's work only!
354 inline static void DoInsertRegionLocked(const Region& region);
355 // Handle regions saved by InsertRegionLocked into a tmp static array
356 // by calling insert_func on them.
357 inline static void HandleSavedRegionsLocked(
358 void (*insert_func)(const Region& region));
360 // Restore buckets saved in a tmp static array by GetBucket to the bucket
361 // table where all buckets eventually should be.
362 static void RestoreSavedBucketsLocked();
364 // Wrapper around DoInsertRegionLocked
365 // that handles the case of recursive allocator calls.
366 inline static void InsertRegionLocked(const Region& region);
368 // Record addition of a memory region at address "start" of size "size"
369 // (called from our mmap/mremap/sbrk hooks).
370 static void RecordRegionAddition(const void* start, size_t size);
371 // Record deletion of a memory region at address "start" of size "size"
372 // (called from our munmap/mremap/sbrk hooks).
373 static void RecordRegionRemoval(const void* start, size_t size);
375 // Record deletion of a memory region of size "size" in a bucket whose
376 // caller stack trace is "key". The stack trace is used to a depth of
377 // "depth" at most.
378 static void RecordRegionRemovalInBucket(int depth,
379 const void* const key[],
380 size_t size);
382 // Hooks for MallocHook
383 static void MmapHook(const void* result,
384 const void* start, size_t size,
385 int prot, int flags,
386 int fd, off_t offset);
387 static void MunmapHook(const void* ptr, size_t size);
388 static void MremapHook(const void* result, const void* old_addr,
389 size_t old_size, size_t new_size, int flags,
390 const void* new_addr);
391 static void SbrkHook(const void* result, ptrdiff_t increment);
393 // Log all memory regions; Useful for debugging only.
394 // Assumes Lock() is held
395 static void LogAllLocked();
397 DISALLOW_COPY_AND_ASSIGN(MemoryRegionMap);
400 template <class Type>
401 void MemoryRegionMap::IterateBuckets(
402 void (*callback)(const HeapProfileBucket*, Type), Type callback_arg) {
403 for (int index = 0; index < kHashTableSize; index++) {
404 for (HeapProfileBucket* bucket = bucket_table_[index];
405 bucket != NULL;
406 bucket = bucket->next) {
407 callback(bucket, callback_arg);
412 #endif // BASE_MEMORY_REGION_MAP_H_