1// Copyright (c) 2010 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4//
5// Parts of this module come from:
6//  http://www.codeproject.com/KB/applications/visualleakdetector.aspx
7//       by Dan Moulding.
8//  http://www.codeproject.com/KB/threads/StackWalker.aspx
9//       by Jochen Kalmbach
10
11#ifndef TOOLS_MEMORY_WATCHER_CALL_STACK_H_
12#define TOOLS_MEMORY_WATCHER_CALL_STACK_H_
13
14#include <windows.h>
15#include <dbghelp.h>
16#include <functional>
17#include <map>
18#include <string>
19
20#include "base/logging.h"
21#include "base/synchronization/lock.h"
22#include "tools/memory_watcher/memory_watcher.h"
23
24// The CallStack Class
25// A stack where memory has been allocated.
26class CallStack {
27 public:
28  // Initialize for tracing CallStacks.
29  static bool Initialize();
30
31  CallStack();
32  virtual ~CallStack() {}
33
34  // Get a hash for this CallStack.
35  // Identical stack traces will have matching hashes.
36  int32 hash() { return hash_; }
37
38  // Get a unique ID for this CallStack.
39  // No two CallStacks will ever have the same ID.  The ID is a monotonically
40  // increasing number.  Newer CallStacks always have larger IDs.
41  int32 id() { return id_; }
42
43  // Retrieves the frame at the specified index.
44  DWORD_PTR frame(int32 index) {
45    DCHECK(index < frame_count_ && index >= 0);
46    return frames_[index];
47  }
48
49  // Compares the CallStack to another CallStack
50  // for equality. Two CallStacks are equal if they are the same size and if
51  // every frame in each is identical to the corresponding frame in the other.
52  bool IsEqual(const CallStack &target);
53
54  typedef std::basic_string<char, std::char_traits<char>,
55                            PrivateHookAllocator<char> > PrivateAllocatorString;
56
57  // Convert the callstack to a string stored in output.
58  void CallStack::ToString(PrivateAllocatorString* output);
59
60  //
61  bool Valid() const { return valid_; }
62
63 private:
64  // The maximum number of frames to trace.
65  static const int kMaxTraceFrames = 32;
66
67  // Pushes a frame's program counter onto the CallStack.
68  void AddFrame(DWORD_PTR programcounter);
69
70  // Traces the stack, starting from this function, up to kMaxTraceFrames
71  // frames.
72  bool GetStackTrace();
73
74  // Functions for manipulating the frame list.
75  void ClearFrames();
76
77  // Dynamically load the DbgHelp library and supporting routines that we
78  // will use.
79  static bool LoadDbgHelp();
80
81  static void LockDbgHelp() {
82    dbghelp_lock_.Acquire();
83    active_thread_id_ = GetCurrentThreadId();
84  }
85
86  static void UnlockDbgHelp() {
87    active_thread_id_ = 0;
88    dbghelp_lock_.Release();
89  }
90
91  class AutoDbgHelpLock {
92  public:
93    AutoDbgHelpLock() {
94      CallStack::LockDbgHelp();
95    }
96    ~AutoDbgHelpLock() {
97      CallStack::UnlockDbgHelp();
98    }
99  };
100
101  // Check to see if this thread is already processing a stack.
102  bool LockedRecursionDetected() const;
103
104  // According to http://msdn2.microsoft.com/en-us/library/ms680650(VS.85).aspx
105  // "All DbgHelp functions, such as this one, are single threaded.  Therefore,
106  // calls from more than one thread to this function will likely result in
107  // unexpected behavior or memory corruption.  To avoid this, you must
108  // synchromize all concurrent calls from one thread to this function."
109  //
110  // dbghelp_lock_ is used to serialize access across all calls to the DbgHelp
111  // library.  This may be overly conservative (serializing them all together),
112  // but does guarantee correctness.
113  static base::Lock dbghelp_lock_;
114
115  // Record the fact that dbghelp has been loaded.
116  // Changes to this variable are protected by dbghelp_lock_.
117  // It will only changes once... from false to true.
118  static bool dbghelp_loaded_;
119
120  // To prevent infinite recursion due to unexpected side effects in libraries,
121  // we track the thread_id of the thread currently holding the dbghelp_lock_.
122  // We avoid re-aquiring said lock and return an !valid_ instance when we
123  // detect recursion.
124  static DWORD active_thread_id_;
125
126  int frame_count_;  // Current size (in frames)
127  DWORD_PTR frames_[kMaxTraceFrames];
128  int32 hash_;
129  int32 id_;
130
131  // Indicate is this is a valid stack.
132  // This is false if recursion precluded a real stack generation.
133  bool valid_;
134
135  // Cache ProgramCounter -> Symbol lookups.
136  // This cache is not thread safe.
137  typedef std::map<int32, PrivateAllocatorString, std::less<int32>,
138                   PrivateHookAllocator<int32> > SymbolCache;
139  static SymbolCache* symbol_cache_;
140
141  DISALLOW_COPY_AND_ASSIGN(CallStack);
142};
143
144// An AllocationStack is a type of CallStack which represents a CallStack where
145// memory has been allocated.  This class is also a list item, so that it can
146// be easilly allocated and deallocated from its static singly-linked-list of
147// free instances.
148class AllocationStack : public CallStack {
149 public:
150  explicit AllocationStack(int32 size)
151      : next_(NULL), size_(size), CallStack() {}
152
153  // We maintain a freelist of the AllocationStacks.
154  void* operator new(size_t s);
155  void operator delete(void*p);
156
157  int32 size() const { return size_; }
158
159 private:
160  AllocationStack* next_;     // Pointer used when on the freelist.
161  int32 size_;                // Size of block allocated.
162  static AllocationStack* freelist_;
163  static base::Lock freelist_lock_;
164
165  DISALLOW_COPY_AND_ASSIGN(AllocationStack);
166};
167
168#endif  // TOOLS_MEMORY_WATCHER_CALL_STACK_H_
169