diff options
Diffstat (limited to 'trunk/src/heap-profile-table.h')
| -rw-r--r-- | trunk/src/heap-profile-table.h | 384 |
1 files changed, 384 insertions, 0 deletions
diff --git a/trunk/src/heap-profile-table.h b/trunk/src/heap-profile-table.h new file mode 100644 index 0000000..5403257 --- /dev/null +++ b/trunk/src/heap-profile-table.h @@ -0,0 +1,384 @@ +// 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. Defined in the .cc file. + static const int kMaxStackDepth; + + // 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(); + + // Record an allocation at 'ptr' of 'bytes' bytes. + // skip_count gives the number of stack frames between this call + // and the memory allocation function that was asked to do the allocation. + void RecordAlloc(const void* ptr, size_t bytes, int skip_count); + + // Direct version of RecordAlloc when the caller stack to use + // is already known: call_stack of depth stack_depth. + void RecordAllocWithStack(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. + 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 { + allocation_->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); + + 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); + + // Get the bucket for the caller stack trace 'key' of depth 'depth' + // creating the bucket if needed. + Bucket* GetBucket(int depth, const void* const key[]); + + // 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 IterateOrderedAllocContexts and FillOrderedProfile. + // Creates a sorted list of Buckets whose length is num_buckets_. + // The caller is responsible for dellocating 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. + Bucket total_; + + // Bucket hash table. + // 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** table_; + int num_buckets_; + + // Map of all currently allocated objects we know about. + AllocationMap* allocation_; + + 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_ |