1 /* Copyright (c) 2006, Google Inc.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
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
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.
31 * Author: Maxim Lifantsev
34 #ifndef BASE_MEMORY_REGION_MAP_H_
35 #define BASE_MEMORY_REGION_MAP_H_
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
{
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;
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).
127 LockHolder() { Lock(); }
128 ~LockHolder() { Unlock(); }
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.
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
) {
183 AssertIsConsistent();
185 void set_end_addr(uintptr_t 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));
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.
232 static void IterateBuckets(void (*callback
)(const HeapProfileBucket
*, Type
),
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
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
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.
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:
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
378 static void RecordRegionRemovalInBucket(int depth
,
379 const void* const key
[],
382 // Hooks for MallocHook
383 static void MmapHook(const void* result
,
384 const void* start
, size_t size
,
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
];
406 bucket
= bucket
->next
) {
407 callback(bucket
, callback_arg
);
412 #endif // BASE_MEMORY_REGION_MAP_H_