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/agent/common/stack_walker_x86.h"
25 : #include "syzygy/common/asan_parameters.h"
26 :
27 : namespace agent {
28 : namespace common {
29 :
30 : // A simple class for holding a stack trace capture.
31 : class StackCapture {
32 : public:
33 : // From http://msdn.microsoft.com/en-us/library/bb204633.aspx,
34 : // The maximum number of frames which CaptureStackBackTrace can be asked
35 : // to traverse must be less than 63, so set it to 62.
36 : static const size_t kMaxNumFrames = 62;
37 :
38 : // The type used for reference counting. We use saturation arithmetic, so it
39 : // will top out at kMaxRefCount.
40 : using RefCount = uint16;
41 : static const RefCount kMaxRefCount = static_cast<RefCount>(-1);
42 :
43 : using StackId = ::common::AsanStackId;
44 :
45 : StackCapture()
46 : : ref_count_(0),
47 : absolute_stack_id_(0),
48 : relative_stack_id_(0),
49 : num_frames_(0),
50 E : max_num_frames_(kMaxNumFrames) {}
51 :
52 : explicit StackCapture(size_t max_num_frames)
53 : : ref_count_(0),
54 : absolute_stack_id_(0),
55 : relative_stack_id_(0),
56 : num_frames_(0),
57 E : max_num_frames_(0) {
58 E : DCHECK_LT(0u, max_num_frames);
59 E : DCHECK_GE(kMaxNumFrames, max_num_frames);
60 E : max_num_frames_ = max_num_frames;
61 E : }
62 :
63 : // Static initialisation of StackCapture context.
64 : static void Init();
65 :
66 : // Calculate the size necessary to store a StackCapture with the given
67 : // number of stack frames.
68 : // @param max_num_frames The maximum number of stack frames the object needs
69 : // to be able to hold.
70 : // @returns the size of a StackCapture object with the given number of frames.
71 : static size_t GetSize(size_t max_num_frames);
72 :
73 : // Calculate the max number of frames that can be fit into a memory region of
74 : // the given size.
75 : // @param bytes The number of bytes to be used.
76 : // @returns the maxmimum number of frames that will fit in the provided number
77 : // of bytes.
78 : static size_t GetMaxNumFrames(size_t bytes);
79 :
80 : // @returns the size of this initialized StackCapture object.
81 E : size_t Size() const { return GetSize(max_num_frames_); }
82 :
83 : // @returns true if this stack trace capture contains valid frame pointers.
84 E : bool IsValid() const { return num_frames_ != 0; }
85 :
86 : // Increments the reference count of this stack capture.
87 : void AddRef();
88 :
89 : // Decrements the reference count of this stack capture.
90 : void RemoveRef();
91 :
92 : // @returns true if the reference count is saturated, false otherwise. A
93 : // saturated reference count means that further calls to AddRef and
94 : // RemoveRef will be nops, and HasNoRefs will always return false.
95 E : bool RefCountIsSaturated() const { return ref_count_ == kMaxRefCount; }
96 :
97 : // @returns true if this stack capture is not referenced, false otherwise.
98 E : bool HasNoRefs() const { return ref_count_ == 0; }
99 :
100 : // @returns the reference count for this stack capture.
101 : RefCount ref_count() const { return ref_count_; }
102 :
103 : // @returns the absolute ID associated with this stack trace.
104 E : StackId absolute_stack_id() const { return absolute_stack_id_; }
105 :
106 : // @returns the relative ID associated with this stack trace.
107 : StackId relative_stack_id() const;
108 :
109 : // @returns the number of valid frame pointers in this stack trace capture.
110 E : size_t num_frames() const { return num_frames_; }
111 :
112 : // @returns the maximum number of valid frame pointers in this stack trace
113 : // capture.
114 E : size_t max_num_frames() const { return max_num_frames_; }
115 :
116 : // @returns a pointer to the stack frames array, or NULL if the array has a
117 : // size of 0.
118 E : const void* const* frames() const {
119 E : return max_num_frames_ != 0 ? frames_ : NULL;
120 E : }
121 :
122 : // Set the number of bottom frames to skip per stack trace. This is needed to
123 : // be able to improve the stack cache compression in Chrome's unittests where
124 : // the bottom of the stack traces is different for each test case.
125 : // @param bottom_frames_to_skip The number of bottom frames to skip.
126 E : static void set_bottom_frames_to_skip(size_t bottom_frames_to_skip) {
127 E : CHECK_LT(bottom_frames_to_skip, kMaxNumFrames);
128 E : bottom_frames_to_skip_ = bottom_frames_to_skip;
129 E : }
130 :
131 : // Get the number of bottom frames to skip per stack trace.
132 E : static size_t bottom_frames_to_skip() { return bottom_frames_to_skip_; }
133 :
134 : // Initializes a stack trace from an array of frame pointers and a count.
135 : // @param frames an array of frame pointers.
136 : // @param num_frames the number of valid frame pointers in @frames. Note
137 : // that at most kMaxNumFrames frame pointers will be copied to this
138 : // stack trace capture.
139 : void InitFromBuffer(const void* const* frames, size_t num_frames);
140 :
141 : // Initializes a stack trace from an existing stack trace.
142 : // @param stack_capture The existing stack trace that will be copied.
143 : void InitFromExistingStack(const StackCapture& stack_capture);
144 :
145 : // Initializes a stack trace from the actual stack. Does not report the
146 : // frame created by 'InitFromStack' itself. This function must not be inlined
147 : // as it assumes that the call to it generates a full stack frame.
148 : void __declspec(noinline) InitFromStack();
149 :
150 : // The hash comparison functor for use with MSDN's stdext::hash_set.
151 : struct HashCompare {
152 : static const size_t bucket_size = 4;
153 : static const size_t min_buckets = 8;
154 : // Calculates a hash value for the given stack_capture.
155 : size_t operator()(const StackCapture* stack_capture) const;
156 : // Value comparison operator.
157 : bool operator()(const StackCapture* stack_capture1,
158 : const StackCapture* stack_capture2) const;
159 : };
160 :
161 : // @name Testing seams.
162 : // @{
163 : // Allows injecting false modules for use in computing the relative stack ID.
164 : // These locations will always be checked first before querying the OS for
165 : // a module address, so can be used to overlay fake modules on top of real
166 : // modules.
167 : // @param name The name of the fake module.
168 : // @param address The address of the fake module.
169 : // @param length The length of the fake module.
170 : static void AddFalseModule(const char* name, void* address, size_t length);
171 : static void ClearFalseModules();
172 : // @}
173 :
174 : // @name Hashing helpers.
175 : // @{
176 : // Uses a simple hash with reasonable properties. This is effectively the same
177 : // as base::SuperFastHash, but we can't use it as there's no API for updating
178 : // an in-progress hash.
179 : static StackId StartStackId();
180 : static StackId UpdateStackId(StackId stack_id, const void* frame);
181 : static StackId FinalizeStackId(StackId stack_id, size_t num_frames);
182 : // @}
183 :
184 : protected:
185 : // The number of bottom frames to skip on the stack traces.
186 : static size_t bottom_frames_to_skip_;
187 :
188 : // The absolute unique ID of this hash. This is used for storing the hash in
189 : // the set.
190 : StackId absolute_stack_id_;
191 :
192 : // The relative unique ID of this hash. This is used when persistence between
193 : // runs is needed. Should be only accessed through relative_stack_id() as it's
194 : // computed on demand and cached (which is why it's declared as mutable).
195 : mutable StackId relative_stack_id_;
196 :
197 : // The number of valid frames in this stack trace capture, and the maximum
198 : // number it can represent. We use uint8s here because we're limited to
199 : // kMaxNumFrames by the OS machinery and want this data structure to be as
200 : // compact as possible.
201 : uint8 num_frames_;
202 : uint8 max_num_frames_;
203 :
204 : // The reference count for this stack capture. We use saturation arithmetic
205 : // and something that is referenced 2^16 - 1 times will stay at that reference
206 : // count and never be removed from the stack cache.
207 : RefCount ref_count_;
208 :
209 : // The array or frame pointers comprising this stack trace capture.
210 : // This is a runtime dynamic array whose actual length is max_num_frames_, but
211 : // we use the maximum length here so that other users of StackCapture can
212 : // capture full stack traces if they so desire.
213 : // NOTE: This must be the last member of the class.
214 : void* frames_[kMaxNumFrames];
215 :
216 : // Computes a simple hash of a given stack trace, referred to as the absolute
217 : // stack id and sets the value in |absolute_stack_id_|.
218 : void ComputeAbsoluteStackId();
219 :
220 : // Computes the hash of a stack trace using relative addresses of each stack
221 : // frame. Declared virtual for unittesting.
222 : virtual void ComputeRelativeStackId() const;
223 :
224 : DISALLOW_COPY_AND_ASSIGN(StackCapture);
225 : };
226 :
227 : // static
228 E : __forceinline StackId StackCapture::StartStackId() {
229 E : return 0x4ADFA3E5;
230 E : }
231 :
232 : // static
233 : __forceinline StackId StackCapture::UpdateStackId(StackId stack_id,
234 E : const void* frame) {
235 E : stack_id += reinterpret_cast<StackId>(frame);
236 E : stack_id += stack_id << 10;
237 E : stack_id ^= stack_id >> 6;
238 E : return stack_id;
239 E : }
240 :
241 : // static
242 : __forceinline StackId StackCapture::FinalizeStackId(StackId stack_id,
243 E : size_t num_frames) {
244 E : stack_id += stack_id << 3;
245 E : stack_id ^= stack_id >> 11;
246 E : stack_id += stack_id << 15;
247 E : stack_id ^= num_frames;
248 E : return stack_id;
249 E : }
250 :
251 : } // namespace common
252 : } // namespace agent
253 :
254 : #endif // SYZYGY_AGENT_COMMON_STACK_CAPTURE_H_
|