| // Copyright (c) 2009, 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: Andrew Fikes |
| |
| #include <config.h> |
| #include "stack_trace_table.h" |
| #include <string.h> // for NULL, memset |
| #include "base/spinlock.h" // for SpinLockHolder |
| #include "common.h" // for StackTrace |
| #include "internal_logging.h" // for ASSERT, Log |
| #include "page_heap_allocator.h" // for PageHeapAllocator |
| #include "static_vars.h" // for Static |
| |
| namespace tcmalloc { |
| |
| bool StackTraceTable::Bucket::KeyEqual(uintptr_t h, |
| const StackTrace& t) const { |
| const bool eq = (this->hash == h && this->trace.depth == t.depth); |
| for (int i = 0; eq && i < t.depth; ++i) { |
| if (this->trace.stack[i] != t.stack[i]) { |
| return false; |
| } |
| } |
| return eq; |
| } |
| |
| StackTraceTable::StackTraceTable() |
| : error_(false), |
| depth_total_(0), |
| bucket_total_(0), |
| table_(new Bucket*[kHashTableSize]()) { |
| memset(table_, 0, kHashTableSize * sizeof(Bucket*)); |
| } |
| |
| StackTraceTable::~StackTraceTable() { |
| delete[] table_; |
| } |
| |
| void StackTraceTable::AddTrace(const StackTrace& t) { |
| if (error_) { |
| return; |
| } |
| |
| // Hash function borrowed from base/heap-profile-table.cc |
| uintptr_t h = 0; |
| for (int i = 0; i < t.depth; ++i) { |
| h += reinterpret_cast<uintptr_t>(t.stack[i]); |
| h += h << 10; |
| h ^= h >> 6; |
| } |
| h += h << 3; |
| h ^= h >> 11; |
| |
| const int idx = h % kHashTableSize; |
| |
| Bucket* b = table_[idx]; |
| while (b != NULL && !b->KeyEqual(h, t)) { |
| b = b->next; |
| } |
| if (b != NULL) { |
| b->count++; |
| b->trace.size += t.size; // keep cumulative size |
| } else { |
| depth_total_ += t.depth; |
| bucket_total_++; |
| b = Static::bucket_allocator()->New(); |
| if (b == NULL) { |
| Log(kLog, __FILE__, __LINE__, |
| "tcmalloc: could not allocate bucket", sizeof(*b)); |
| error_ = true; |
| } else { |
| b->hash = h; |
| b->trace = t; |
| b->count = 1; |
| b->next = table_[idx]; |
| table_[idx] = b; |
| } |
| } |
| } |
| |
| void** StackTraceTable::ReadStackTracesAndClear() { |
| if (error_) { |
| return NULL; |
| } |
| |
| // Allocate output array |
| const int out_len = bucket_total_ * 3 + depth_total_ + 1; |
| void** out = new void*[out_len]; |
| if (out == NULL) { |
| Log(kLog, __FILE__, __LINE__, |
| "tcmalloc: allocation failed for stack traces", |
| out_len * sizeof(*out)); |
| return NULL; |
| } |
| |
| // Fill output array |
| int idx = 0; |
| for (int i = 0; i < kHashTableSize; ++i) { |
| Bucket* b = table_[i]; |
| while (b != NULL) { |
| out[idx++] = reinterpret_cast<void*>(static_cast<uintptr_t>(b->count)); |
| out[idx++] = reinterpret_cast<void*>(b->trace.size); // cumulative size |
| out[idx++] = reinterpret_cast<void*>(b->trace.depth); |
| for (int d = 0; d < b->trace.depth; ++d) { |
| out[idx++] = b->trace.stack[d]; |
| } |
| b = b->next; |
| } |
| } |
| out[idx++] = static_cast<uintptr_t>(0); |
| ASSERT(idx == out_len); |
| |
| // Clear state |
| error_ = false; |
| depth_total_ = 0; |
| bucket_total_ = 0; |
| SpinLockHolder h(Static::pageheap_lock()); |
| for (int i = 0; i < kHashTableSize; ++i) { |
| Bucket* b = table_[i]; |
| while (b != NULL) { |
| Bucket* next = b->next; |
| Static::bucket_allocator()->Delete(b); |
| b = next; |
| } |
| table_[i] = NULL; |
| } |
| |
| return out; |
| } |
| |
| } // namespace tcmalloc |