// Copyright (c) 2006, Google Inc. // All rights reserved. // // Redistribution and use in source and binary forms, with or without // modification, are permitted provided that the following conditions are // met: // // * Redistributions of source code must retain the above copyright // notice, this list of conditions and the following disclaimer. // * Redistributions in binary form must reproduce the above // copyright notice, this list of conditions and the following disclaimer // in the documentation and/or other materials provided with the // distribution. // * Neither the name of Google Inc. nor the names of its // contributors may be used to endorse or promote products derived from // this software without specific prior written permission. // // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. // --- // Author: Sanjay Ghemawat // Maxim Lifantsev (refactoring) // #ifndef BASE_HEAP_PROFILE_TABLE_H_ #define BASE_HEAP_PROFILE_TABLE_H_ #include "addressmap-inl.h" #include "base/basictypes.h" #include "base/logging.h" // for RawFD // Table to maintain a heap profile data inside, // i.e. the set of currently active heap memory allocations. // thread-unsafe and non-reentrant code: // each instance object must be used by one thread // at a time w/o self-recursion. // // TODO(maxim): add a unittest for this class. class HeapProfileTable { public: // Extension to be used for heap pforile files. static const char kFileExt[]; // Longest stack trace we record. static const int kMaxStackDepth = 32; // data types ---------------------------- // Profile stats. struct Stats { int32 allocs; // Number of allocation calls int32 frees; // Number of free calls int64 alloc_size; // Total size of all allocated objects so far int64 free_size; // Total size of all freed objects so far // semantic equality bool Equivalent(const Stats& x) const { return allocs - frees == x.allocs - x.frees && alloc_size - free_size == x.alloc_size - x.free_size; } }; // Info we can return about an allocation. struct AllocInfo { size_t object_size; // size of the allocation const void* const* call_stack; // call stack that made the allocation call int stack_depth; // depth of call_stack bool live; bool ignored; }; // Info we return about an allocation context. // An allocation context is a unique caller stack trace // of an allocation operation. struct AllocContextInfo : public Stats { int stack_depth; // Depth of stack trace const void* const* call_stack; // Stack trace }; // Memory (de)allocator interface we'll use. typedef void* (*Allocator)(size_t size); typedef void (*DeAllocator)(void* ptr); // interface --------------------------- HeapProfileTable(Allocator alloc, DeAllocator dealloc); ~HeapProfileTable(); // Collect the stack trace for the function that asked to do the // allocation for passing to RecordAlloc() below. // // The stack trace is stored in 'stack'. The stack depth is returned. // // 'skip_count' gives the number of stack frames between this call // and the memory allocation function. static int GetCallerStackTrace(int skip_count, void* stack[kMaxStackDepth]); // Record an allocation at 'ptr' of 'bytes' bytes. 'stack_depth' // and 'call_stack' identifying the function that requested the // allocation. They can be generated using GetCallerStackTrace() above. void RecordAlloc(const void* ptr, size_t bytes, int stack_depth, const void* const call_stack[]); // Record the deallocation of memory at 'ptr'. void RecordFree(const void* ptr); // Return true iff we have recorded an allocation at 'ptr'. // If yes, fill *object_size with the allocation byte size. bool FindAlloc(const void* ptr, size_t* object_size) const; // Same as FindAlloc, but fills all of *info. bool FindAllocDetails(const void* ptr, AllocInfo* info) const; // Return true iff "ptr" points into a recorded allocation // If yes, fill *object_ptr with the actual allocation address // and *object_size with the allocation byte size. // max_size specifies largest currently possible allocation size. bool FindInsideAlloc(const void* ptr, size_t max_size, const void** object_ptr, size_t* object_size) const; // If "ptr" points to a recorded allocation and it's not marked as live // mark it as live and return true. Else return false. // All allocations start as non-live. bool MarkAsLive(const void* ptr); // If "ptr" points to a recorded allocation, mark it as "ignored". // Ignored objects are treated like other objects, except that they // are skipped in heap checking reports. void MarkAsIgnored(const void* ptr); // Return current total (de)allocation statistics. It doesn't contain // mmap'ed regions. const Stats& total() const { return total_; } // Allocation data iteration callback: gets passed object pointer and // fully-filled AllocInfo. typedef void (*AllocIterator)(const void* ptr, const AllocInfo& info); // Iterate over the allocation profile data calling "callback" // for every allocation. void IterateAllocs(AllocIterator callback) const { alloc_address_map_->Iterate(MapArgsAllocIterator, callback); } // Allocation context profile data iteration callback typedef void (*AllocContextIterator)(const AllocContextInfo& info); // Iterate over the allocation context profile data calling "callback" // for every allocation context. Allocation contexts are ordered by the // size of allocated space. void IterateOrderedAllocContexts(AllocContextIterator callback) const; // Fill profile data into buffer 'buf' of size 'size' // and return the actual size occupied by the dump in 'buf'. // The profile buckets are dumped in the decreasing order // of currently allocated bytes. // We do not provision for 0-terminating 'buf'. int FillOrderedProfile(char buf[], int size) const; // Cleanup any old profile files matching prefix + ".*" + kFileExt. static void CleanupOldProfiles(const char* prefix); // Return a snapshot of the current contents of *this. // Caller must call ReleaseSnapshot() on result when no longer needed. // The result is only valid while this exists and until // the snapshot is discarded by calling ReleaseSnapshot(). class Snapshot; Snapshot* TakeSnapshot(); // Release a previously taken snapshot. snapshot must not // be used after this call. void ReleaseSnapshot(Snapshot* snapshot); // Return a snapshot of every non-live, non-ignored object in *this. // If "base" is non-NULL, skip any objects present in "base". // As a side-effect, clears the "live" bit on every live object in *this. // Caller must call ReleaseSnapshot() on result when no longer needed. Snapshot* NonLiveSnapshot(Snapshot* base); // Refresh the internal mmap information from MemoryRegionMap. Results of // FillOrderedProfile and IterateOrderedAllocContexts will contain mmap'ed // memory regions as at calling RefreshMMapData. void RefreshMMapData(); // Clear the internal mmap information. Results of FillOrderedProfile and // IterateOrderedAllocContexts won't contain mmap'ed memory regions after // calling ClearMMapData. void ClearMMapData(); private: // data types ---------------------------- // Hash table bucket to hold (de)allocation stats // for a given allocation call stack trace. struct Bucket : public Stats { uintptr_t hash; // Hash value of the stack trace int depth; // Depth of stack trace const void** stack; // Stack trace Bucket* next; // Next entry in hash-table }; // Info stored in the address map struct AllocValue { // Access to the stack-trace bucket Bucket* bucket() const { return reinterpret_cast<Bucket*>(bucket_rep & ~uintptr_t(kMask)); } // This also does set_live(false). void set_bucket(Bucket* b) { bucket_rep = reinterpret_cast<uintptr_t>(b); } size_t bytes; // Number of bytes in this allocation // Access to the allocation liveness flag (for leak checking) bool live() const { return bucket_rep & kLive; } void set_live(bool l) { bucket_rep = (bucket_rep & ~uintptr_t(kLive)) | (l ? kLive : 0); } // Should this allocation be ignored if it looks like a leak? bool ignore() const { return bucket_rep & kIgnore; } void set_ignore(bool r) { bucket_rep = (bucket_rep & ~uintptr_t(kIgnore)) | (r ? kIgnore : 0); } private: // We store a few bits in the bottom bits of bucket_rep. // (Alignment is at least four, so we have at least two bits.) static const int kLive = 1; static const int kIgnore = 2; static const int kMask = kLive | kIgnore; uintptr_t bucket_rep; }; // helper for FindInsideAlloc static size_t AllocValueSize(const AllocValue& v) { return v.bytes; } typedef AddressMap<AllocValue> AllocationMap; // Arguments that need to be passed DumpNonLiveIterator callback below. struct DumpArgs { RawFD fd; // file to write to Stats* profile_stats; // stats to update (may be NULL) DumpArgs(RawFD a, Stats* d) : fd(a), profile_stats(d) { } }; // helpers ---------------------------- // Unparse bucket b and print its portion of profile dump into buf. // We return the amount of space in buf that we use. We start printing // at buf + buflen, and promise not to go beyond buf + bufsize. // We do not provision for 0-terminating 'buf'. // // If profile_stats is non-NULL, we update *profile_stats by // counting bucket b. // // "extra" is appended to the unparsed bucket. Typically it is empty, // but may be set to something like " heapprofile" for the total // bucket to indicate the type of the profile. static int UnparseBucket(const Bucket& b, char* buf, int buflen, int bufsize, const char* extra, Stats* profile_stats); // Deallocate a given allocation map. void DeallocateAllocationMap(AllocationMap* allocation); // Deallocate a given bucket table. void DeallocateBucketTable(Bucket** table); // Get the bucket for the caller stack trace 'key' of depth 'depth' from a // bucket hash map 'table' creating the bucket if needed. '*bucket_count' // is incremented both when 'bucket_count' is not NULL and when a new // bucket object is created. Bucket* GetBucket(int depth, const void* const key[], Bucket** table, int* bucket_count); // Helper for IterateAllocs to do callback signature conversion // from AllocationMap::Iterate to AllocIterator. static void MapArgsAllocIterator(const void* ptr, AllocValue* v, AllocIterator callback) { AllocInfo info; info.object_size = v->bytes; info.call_stack = v->bucket()->stack; info.stack_depth = v->bucket()->depth; info.live = v->live(); info.ignored = v->ignore(); callback(ptr, info); } // Helper for DumpNonLiveProfile to do object-granularity // heap profile dumping. It gets passed to AllocationMap::Iterate. inline static void DumpNonLiveIterator(const void* ptr, AllocValue* v, const DumpArgs& args); // Helper for filling size variables in buckets by zero. inline static void ZeroBucketCountsIterator( const void* ptr, AllocValue* v, HeapProfileTable* heap_profile); // Helper for IterateOrderedAllocContexts and FillOrderedProfile. // Creates a sorted list of Buckets whose length is num_alloc_buckets_ + // num_avaliable_mmap_buckets_. // The caller is responsible for deallocating the returned list. Bucket** MakeSortedBucketList() const; // Helper for TakeSnapshot. Saves object to snapshot. static void AddToSnapshot(const void* ptr, AllocValue* v, Snapshot* s); // Arguments passed to AddIfNonLive struct AddNonLiveArgs { Snapshot* dest; Snapshot* base; }; // Helper for NonLiveSnapshot. Adds the object to the destination // snapshot if it is non-live. static void AddIfNonLive(const void* ptr, AllocValue* v, AddNonLiveArgs* arg); // Write contents of "*allocations" as a heap profile to // "file_name". "total" must contain the total of all entries in // "*allocations". static bool WriteProfile(const char* file_name, const Bucket& total, AllocationMap* allocations); // data ---------------------------- // Memory (de)allocator that we use. Allocator alloc_; DeAllocator dealloc_; // Overall profile stats; we use only the Stats part, // but make it a Bucket to pass to UnparseBucket. // It doesn't contain mmap'ed regions. Bucket total_; // Bucket hash table for malloc. // We hand-craft one instead of using one of the pre-written // ones because we do not want to use malloc when operating on the table. // It is only few lines of code, so no big deal. Bucket** alloc_table_; int num_alloc_buckets_; // Bucket hash table for mmap. // This table is filled with the information from MemoryRegionMap by calling // RefreshMMapData. Bucket** mmap_table_; int num_available_mmap_buckets_; // Map of all currently allocated objects and mapped regions we know about. AllocationMap* alloc_address_map_; AllocationMap* mmap_address_map_; DISALLOW_COPY_AND_ASSIGN(HeapProfileTable); }; class HeapProfileTable::Snapshot { public: const Stats& total() const { return total_; } // Report anything in this snapshot as a leak. // May use new/delete for temporary storage. // If should_symbolize is true, will fork (which is not threadsafe) // to turn addresses into symbol names. Set to false for maximum safety. // Also writes a heap profile to "filename" that contains // all of the objects in this snapshot. void ReportLeaks(const char* checker_name, const char* filename, bool should_symbolize); // Report the addresses of all leaked objects. // May use new/delete for temporary storage. void ReportIndividualObjects(); bool Empty() const { return (total_.allocs == 0) && (total_.alloc_size == 0); } private: friend class HeapProfileTable; // Total count/size are stored in a Bucket so we can reuse UnparseBucket Bucket total_; // We share the Buckets managed by the parent table, but have our // own object->bucket map. AllocationMap map_; Snapshot(Allocator alloc, DeAllocator dealloc) : map_(alloc, dealloc) { memset(&total_, 0, sizeof(total_)); } // Callback used to populate a Snapshot object with entries found // in another allocation map. inline void Add(const void* ptr, const AllocValue& v) { map_.Insert(ptr, v); total_.allocs++; total_.alloc_size += v.bytes; } // Helpers for sorting and generating leak reports struct Entry; struct ReportState; static void ReportCallback(const void* ptr, AllocValue* v, ReportState*); static void ReportObject(const void* ptr, AllocValue* v, char*); DISALLOW_COPY_AND_ASSIGN(Snapshot); }; #endif // BASE_HEAP_PROFILE_TABLE_H_