15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2009, Google Inc. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// All rights reserved. 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Redistribution and use in source and binary forms, with or without 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// modification, are permitted provided that the following conditions are 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// met: 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions of source code must retain the above copyright 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// notice, this list of conditions and the following disclaimer. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions in binary form must reproduce the above 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// copyright notice, this list of conditions and the following disclaimer 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the documentation and/or other materials provided with the 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// distribution. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Neither the name of Google Inc. nor the names of its 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// contributors may be used to endorse or promote products derived from 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// this software without specific prior written permission. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// --- 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Author: Andrew Fikes 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <config.h> 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "stack_trace_table.h" 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string.h> // for NULL, memset 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/spinlock.h" // for SpinLockHolder 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "common.h" // for StackTrace 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "internal_logging.h" // for ASSERT, Log 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "page_heap_allocator.h" // for PageHeapAllocator 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "static_vars.h" // for Static 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace tcmalloc { 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool StackTraceTable::Bucket::KeyEqual(uintptr_t h, 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StackTrace& t) const { 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const bool eq = (this->hash == h && this->trace.depth == t.depth); 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; eq && i < t.depth; ++i) { 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (this->trace.stack[i] != t.stack[i]) { 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return eq; 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)StackTraceTable::StackTraceTable() 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : error_(false), 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) depth_total_(0), 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bucket_total_(0), 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) table_(new Bucket*[kHashTableSize]()) { 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(table_, 0, kHashTableSize * sizeof(Bucket*)); 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)StackTraceTable::~StackTraceTable() { 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delete[] table_; 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void StackTraceTable::AddTrace(const StackTrace& t) { 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (error_) { 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Hash function borrowed from base/heap-profile-table.cc 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uintptr_t h = 0; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < t.depth; ++i) { 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h += reinterpret_cast<uintptr_t>(t.stack[i]); 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h += h << 10; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h ^= h >> 6; 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h += h << 3; 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h ^= h >> 11; 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int idx = h % kHashTableSize; 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bucket* b = table_[idx]; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (b != NULL && !b->KeyEqual(h, t)) { 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) b = b->next; 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (b != NULL) { 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) b->count++; 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) b->trace.size += t.size; // keep cumulative size 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) depth_total_ += t.depth; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bucket_total_++; 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) b = Static::bucket_allocator()->New(); 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (b == NULL) { 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Log(kLog, __FILE__, __LINE__, 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "tcmalloc: could not allocate bucket", sizeof(*b)); 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) error_ = true; 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) b->hash = h; 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) b->trace = t; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) b->count = 1; 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) b->next = table_[idx]; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) table_[idx] = b; 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void** StackTraceTable::ReadStackTracesAndClear() { 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (error_) { 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Allocate output array 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int out_len = bucket_total_ * 3 + depth_total_ + 1; 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void** out = new void*[out_len]; 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (out == NULL) { 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Log(kLog, __FILE__, __LINE__, 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "tcmalloc: allocation failed for stack traces", 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out_len * sizeof(*out)); 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Fill output array 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int idx = 0; 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < kHashTableSize; ++i) { 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bucket* b = table_[i]; 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (b != NULL) { 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out[idx++] = reinterpret_cast<void*>(static_cast<uintptr_t>(b->count)); 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out[idx++] = reinterpret_cast<void*>(b->trace.size); // cumulative size 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out[idx++] = reinterpret_cast<void*>(b->trace.depth); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int d = 0; d < b->trace.depth; ++d) { 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out[idx++] = b->trace.stack[d]; 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) b = b->next; 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 138eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch out[idx++] = NULL; 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(idx == out_len); 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Clear state 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) error_ = false; 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) depth_total_ = 0; 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bucket_total_ = 0; 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpinLockHolder h(Static::pageheap_lock()); 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < kHashTableSize; ++i) { 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bucket* b = table_[i]; 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (b != NULL) { 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bucket* next = b->next; 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Static::bucket_allocator()->Delete(b); 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) b = next; 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) table_[i] = NULL; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return out; 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace tcmalloc 160