third_party/tcmalloc/chromium/src/stack_trace_table.cc

   1 // Copyright (c) 2009, Google Inc.
   2 // All rights reserved.
   3 //
   4 // Redistribution and use in source and binary forms, with or without
   5 // modification, are permitted provided that the following conditions are
   6 // met:
   7 //
   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
  13 // distribution.
  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.
  17 //
  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.
  29
  30 // ---
  31 // Author: Andrew Fikes
  32
  33 #include <config.h>
  34 #include "stack_trace_table.h"
  35 #include <string.h>                     // for NULL, memset
  36 #include "base/spinlock.h"              // for SpinLockHolder
  37 #include "common.h"            // for StackTrace
  38 #include "internal_logging.h"  // for ASSERT, Log
  39 #include "page_heap_allocator.h"  // for PageHeapAllocator
  40 #include "static_vars.h"       // for Static
  41
  42 namespace tcmalloc {
  43
  44 bool StackTraceTable::Bucket::KeyEqual(uintptr_t h,
  45                                        const StackTrace& t) const {
  46   const bool eq = (this->hash == h && this->trace.depth == t.depth);
  47   for (int i = 0; eq && i < t.depth; ++i) {
  48     if (this->trace.stack[i] != t.stack[i]) {
  49       return false;
  50     }
  51   }
  52   return eq;
  53 }
  54
  55 StackTraceTable::StackTraceTable()
  56     : error_(false),
  57       depth_total_(0),
  58       bucket_total_(0),
  59       table_(new Bucket*[kHashTableSize]()) {
  60   memset(table_, 0, kHashTableSize * sizeof(Bucket*));
  61 }
  62
  63 StackTraceTable::~StackTraceTable() {
  64   delete[] table_;
  65 }
  66
  67 void StackTraceTable::AddTrace(const StackTrace& t) {
  68   if (error_) {
  69     return;
  70   }
  71
  72   // Hash function borrowed from base/heap-profile-table.cc
  73   uintptr_t h = 0;
  74   for (int i = 0; i < t.depth; ++i) {
  75     h += reinterpret_cast<uintptr_t>(t.stack[i]);
  76     h += h << 10;
  77     h ^= h >> 6;
  78   }
  79   h += h << 3;
  80   h ^= h >> 11;
  81
  82   const int idx = h % kHashTableSize;
  83
  84   Bucket* b = table_[idx];
  85   while (b != NULL && !b->KeyEqual(h, t)) {
  86     b = b->next;
  87   }
  88   if (b != NULL) {
  89     b->count++;
  90     b->trace.size += t.size;  // keep cumulative size
  91   } else {
  92     depth_total_ += t.depth;
  93     bucket_total_++;
  94     b = Static::bucket_allocator()->New();
  95     if (b == NULL) {
  96       Log(kLog, __FILE__, __LINE__,
  97           "tcmalloc: could not allocate bucket", sizeof(*b));
  98       error_ = true;
  99     } else {
 100       b->hash = h;
 101       b->trace = t;
 102       b->count = 1;
 103       b->next = table_[idx];
 104       table_[idx] = b;
 105     }
 106   }
 107 }
 108
 109 void** StackTraceTable::ReadStackTracesAndClear() {
 110   if (error_) {
 111     return NULL;
 112   }
 113
 114   // Allocate output array
 115   const int out_len = bucket_total_ * 3 + depth_total_ + 1;
 116   void** out = new void*[out_len];
 117   if (out == NULL) {
 118     Log(kLog, __FILE__, __LINE__,
 119         "tcmalloc: allocation failed for stack traces",
 120         out_len * sizeof(*out));
 121     return NULL;
 122   }
 123
 124   // Fill output array
 125   int idx = 0;
 126   for (int i = 0; i < kHashTableSize; ++i) {
 127     Bucket* b = table_[i];
 128     while (b != NULL) {
 129       out[idx++] = reinterpret_cast<void*>(static_cast<uintptr_t>(b->count));
 130       out[idx++] = reinterpret_cast<void*>(b->trace.size);  // cumulative size
 131       out[idx++] = reinterpret_cast<void*>(b->trace.depth);
 132       for (int d = 0; d < b->trace.depth; ++d) {
 133         out[idx++] = b->trace.stack[d];
 134       }
 135       b = b->next;
 136     }
 137   }
 138   out[idx++] = static_cast<uintptr_t>(0);
 139   ASSERT(idx == out_len);
 140
 141   // Clear state
 142   error_ = false;
 143   depth_total_ = 0;
 144   bucket_total_ = 0;
 145   SpinLockHolder h(Static::pageheap_lock());
 146   for (int i = 0; i < kHashTableSize; ++i) {
 147     Bucket* b = table_[i];
 148     while (b != NULL) {
 149       Bucket* next = b->next;
 150       Static::bucket_allocator()->Delete(b);
 151       b = next;
 152     }
 153     table_[i] = NULL;
 154   }
 155
 156   return out;
 157 }
 158
 159 }  // namespace tcmalloc