1 : // Copyright 2013 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 : //
15 : // Declares a utility class for getting and storing quick and dirty stack
16 : // captures.
17 :
18 : #ifndef SYZYGY_AGENT_COMMON_STACK_CAPTURE_H_
19 : #define SYZYGY_AGENT_COMMON_STACK_CAPTURE_H_
20 :
21 : #include <windows.h>
22 :
23 : #include "base/logging.h"
24 : #include "syzygy/common/asan_parameters.h"
25 :
26 : namespace agent {
27 : namespace common {
28 :
29 : // Computes the hash of a given stack trace. The hash function is simply an add
30 : // of all the stack trace pointers.
31 : uint32 ComputeStackTraceHash(void** stack_trace, uint8 stack_depth);
32 :
33 : // A simple class for holding a stack trace capture.
34 : class StackCapture {
35 : public:
36 : // From http://msdn.microsoft.com/en-us/library/bb204633.aspx,
37 : // The maximum number of frames which CaptureStackBackTrace can be asked
38 : // to traverse must be less than 63, so set it to 62.
39 : static const size_t kMaxNumFrames = 62;
40 :
41 : // The type used for reference counting. We use saturation arithmetic, so it
42 : // will top out at kMaxRefCount.
43 : typedef uint16 RefCount;
44 : static const RefCount kMaxRefCount = -1;
45 :
46 : // This corresponds to the the type used by ::CaptureStackBackTrace's hash
47 : // for a stack-trace.
48 : typedef ULONG StackId;
49 : COMPILE_ASSERT(sizeof(StackId) == sizeof(::common::AsanStackId),
50 : stack_id_type_mismatch);
51 :
52 : StackCapture()
53 : : ref_count_(0), stack_id_(0), num_frames_(0),
54 E : max_num_frames_(kMaxNumFrames) {
55 E : }
56 :
57 E : explicit StackCapture(size_t max_num_frames)
58 : : ref_count_(0), stack_id_(0), num_frames_(0), max_num_frames_(0) {
59 E : DCHECK_LT(0u, max_num_frames);
60 E : DCHECK_GE(kMaxNumFrames, max_num_frames);
61 E : max_num_frames_ = max_num_frames;
62 E : }
63 :
64 : // Static initialisation of StackCapture context.
65 : static void Init();
66 :
67 : // Calculate the size necessary to store a StackCapture with the given
68 : // number of stack frames.
69 : // @param max_num_frames The maximum number of stack frames the object needs
70 : // to be able to hold.
71 : // @returns the size of a StackCapture object with the given number of frames.
72 : static size_t GetSize(size_t max_num_frames);
73 :
74 : // Calculate the max number of frames that can be fit into a memory region of
75 : // the given size.
76 : // @param bytes The number of bytes to be used.
77 : // @returns the maxmimum number of frames that will fit in the provided number
78 : // of bytes.
79 : static size_t GetMaxNumFrames(size_t bytes);
80 :
81 : // @returns the size of this initialized StackCapture object.
82 E : size_t Size() const { return GetSize(max_num_frames_); }
83 :
84 : // @returns true if this stack trace capture contains valid frame pointers.
85 E : bool IsValid() const { return num_frames_ != 0; }
86 :
87 : // Increments the reference count of this stack capture.
88 : void AddRef();
89 :
90 : // Decrements the reference count of this stack capture.
91 : void RemoveRef();
92 :
93 : // @returns true if the reference count is saturated, false otherwise. A
94 : // saturated reference count means that further calls to AddRef and
95 : // RemoveRef will be nops, and HasNoRefs will always return false.
96 E : bool RefCountIsSaturated() const { return ref_count_ == kMaxRefCount; }
97 :
98 : // @returns true if this stack capture is not referenced, false otherwise.
99 E : bool HasNoRefs() const { return ref_count_ == 0; }
100 :
101 : // @returns the reference count for this stack capture.
102 : RefCount ref_count() const { return ref_count_; }
103 :
104 : // @returns the ID associated with this stack trace.
105 E : StackId stack_id() const { return stack_id_; }
106 :
107 : // @returns the number of valid frame pointers in this stack trace capture.
108 E : size_t num_frames() const { return num_frames_; }
109 :
110 : // @returns the maximum number of valid frame pointers in this stack trace
111 : // capture.
112 E : size_t max_num_frames() const { return max_num_frames_; }
113 :
114 : // @returns a pointer to the stack frames array, or NULL if the array has a
115 : // size of 0.
116 E : const void* const* frames() const {
117 E : return max_num_frames_ != 0 ? frames_ : NULL;
118 E : }
119 :
120 : // Sets the stack ID for a given trace.
121 : // @param The stack ID to set.
122 E : void set_stack_id(StackId stack_id) { stack_id_ = stack_id; }
123 :
124 : // Set the number of bottom frames to skip per stack trace. This is needed to
125 : // be able to improve the stack cache compression in Chrome's unittests where
126 : // the bottom of the stack traces is different for each test case.
127 : // @param bottom_frames_to_skip The number of bottom frames to skip.
128 E : static void set_bottom_frames_to_skip(size_t bottom_frames_to_skip) {
129 E : CHECK_LT(bottom_frames_to_skip, kMaxNumFrames);
130 E : bottom_frames_to_skip_ = bottom_frames_to_skip;
131 E : }
132 :
133 : // Get the number of bottom frames to skip per stack trace.
134 E : static size_t bottom_frames_to_skip() { return bottom_frames_to_skip_; }
135 :
136 : // Initializes a stack trace from an array of frame pointers, a count and
137 : // a StackId (such as returned by ::CaptureStackBackTrace).
138 : // @param stack_id The ID of the stack back trace.
139 : // @param frames an array of frame pointers.
140 : // @param num_frames the number of valid frame pointers in @frames. Note
141 : // that at most kMaxNumFrames frame pointers will be copied to this
142 : // stack trace capture.
143 : void InitFromBuffer(StackId stack_id,
144 : const void* const* frames,
145 : size_t num_frames);
146 :
147 : // Initializes a stack trace using ::CaptureStackBackTrace. This is inlined so
148 : // that it doesn't further pollute the stack trace, but rather makes it
149 : // reflect the actual point of the call.
150 E : __forceinline void InitFromStack() {
151 : num_frames_ = ::CaptureStackBackTrace(
152 E : 0, max_num_frames_, frames_, NULL);
153 E : if (num_frames_ > bottom_frames_to_skip_)
154 E : num_frames_ -= bottom_frames_to_skip_;
155 E : else
156 i : num_frames_ = 1;
157 E : stack_id_ = ComputeStackTraceHash(frames_, num_frames_);
158 E : }
159 :
160 : // The hash comparison functor for use with MSDN's stdext::hash_set.
161 : struct HashCompare {
162 : static const size_t bucket_size = 4;
163 : static const size_t min_buckets = 8;
164 : // Calculates a hash value for the given stack_capture.
165 : size_t operator()(const StackCapture* stack_capture) const;
166 : // Value comparison operator.
167 : bool operator()(const StackCapture* stack_capture1,
168 : const StackCapture* stack_capture2) const;
169 : };
170 :
171 : // Computes the hash of a stack trace using relative addresses of each stack
172 : // frame.
173 : // @returns the relative hash of this stack trace.
174 : StackId ComputeRelativeStackId();
175 :
176 : protected:
177 : // The number of bottom frames to skip on the stack traces.
178 : static size_t bottom_frames_to_skip_;
179 :
180 : // The unique ID of this hash. This is used for storing the hash in the set.
181 : StackId stack_id_;
182 :
183 : // The number of valid frames in this stack trace capture, and the maximum
184 : // number it can represent. We use uint8s here because we're limited to
185 : // kMaxNumFrames by the OS machinery and want this data structure to be as
186 : // compact as possible.
187 : uint8 num_frames_;
188 : uint8 max_num_frames_;
189 :
190 : // The reference count for this stack capture. We use saturation arithmetic
191 : // and something that is referenced 2^16 - 1 times will stay at that reference
192 : // count and never be removed from the stack cache.
193 : RefCount ref_count_;
194 :
195 : // The array or frame pointers comprising this stack trace capture.
196 : // This is a runtime dynamic array whose actual length is max_num_frames_, but
197 : // we use the maximum length here so that other users of StackCapture can
198 : // capture full stack traces if they so desire.
199 : // NOTE: This must be the last member of the class.
200 : void* frames_[kMaxNumFrames];
201 :
202 : private:
203 : DISALLOW_COPY_AND_ASSIGN(StackCapture);
204 : };
205 :
206 : } // namespace common
207 : } // namespace agent
208 :
209 : #endif // SYZYGY_AGENT_COMMON_STACK_CAPTURE_H_
|