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
42namespace tcmalloc {
43
44bool 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
55StackTraceTable::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
63StackTraceTable::~StackTraceTable() {
64  delete[] table_;
65}
66
67void 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
109void** 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
160