Home | History | Annotate | Download | only in src 
      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++] = NULL;
    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
    160