1 : // Copyright 2012 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 : #ifndef SYZYGY_AGENT_ASAN_STACK_CAPTURE_CACHE_H_
16 : #define SYZYGY_AGENT_ASAN_STACK_CAPTURE_CACHE_H_
17 :
18 : #include "base/synchronization/lock.h"
19 : #include "syzygy/agent/asan/shadow.h"
20 : #include "syzygy/agent/common/stack_capture.h"
21 : #include "syzygy/common/asan_parameters.h"
22 :
23 : namespace agent {
24 : namespace asan {
25 :
26 : // Forward declaration.
27 : class AsanLogger;
28 :
29 : // A class which manages a thread-safe cache of unique stack traces, by ID.
30 : class StackCaptureCache {
31 : public:
32 : // The size of a page of stack captures, in bytes. This should be in the
33 : // hundreds of KB or low MBs so that we have an efficient pooled allocator
34 : // that can store hundreds to thousands of stack captures, yet whose
35 : // incremental growth is not too large.
36 : static const size_t kCachePageSize = 1024 * 1024;
37 :
38 : // The type used to uniquely identify a stack.
39 : typedef common::StackCapture::StackId StackId;
40 :
41 : // Forward declaration.
42 : class CachePage;
43 :
44 : // TODO(chrisha): Plumb a command-line parameter through to control the
45 : // max depth of stack traces in the StackCaptureCache. This should get us
46 : // significant memory savings in the stack trace cache.
47 :
48 : // Initializes a new stack capture cache.
49 : // @param logger The logger to use.
50 : // @param max_num_frames The maximum number of frames to be used by the
51 : // StackCapture objects in this cache.
52 : explicit StackCaptureCache(AsanLogger* logger);
53 : StackCaptureCache(AsanLogger* logger, size_t max_num_frames);
54 :
55 : // Destroys a stack capture cache.
56 : ~StackCaptureCache();
57 :
58 : // Static initialisation of StackCaptureCache context.
59 : static void Init();
60 :
61 : // @returns the current maximum number of frames supported by saved stack
62 : // traces.
63 E : size_t max_num_frames() const { return max_num_frames_; }
64 :
65 : // Sets the current maximum number of frames supported by saved stack traces.
66 : // @param max_num_frames The maximum number of frames to set.
67 E : void set_max_num_frames(size_t max_num_frames) {
68 E : max_num_frames_ = max_num_frames;
69 E : }
70 :
71 : // @returns the default compression reporting period value.
72 E : static size_t GetDefaultCompressionReportingPeriod() {
73 E : return ::common::kDefaultReportingPeriod;
74 E : }
75 :
76 : // Sets a new (global) compression reporting period value. Note that this
77 : // method is not thread safe. It is expected to be called once at startup,
78 : // or not at all.
79 E : static void set_compression_reporting_period(size_t period) {
80 E : compression_reporting_period_ = period;
81 E : }
82 :
83 : // @returns the current (global) compression reporting period value. It is
84 : // expected that this value is a constant after initialization.
85 E : static size_t compression_reporting_period() {
86 E : return compression_reporting_period_;
87 E : }
88 :
89 : // Save (or retrieve) the stack capture (the first @p num_frames elements
90 : // from @p frames) into the cache using @p stack_id as the key.
91 : // @param stack_id a unique identifier for this stack trace. It is expected
92 : // that identical stack traces will have the same @p stack_id.
93 : // @param frames an array of stack frame pointers.
94 : // @param num_frames the number of valid elements in @p frames. Note that
95 : // at most StackCapture::kMaxNumFrames will be saved.
96 : // @param stack_capture The initialized stack capture to save.
97 : // @returns a pointer to the saved stack capture.
98 : const common::StackCapture* SaveStackTrace(StackId stack_id,
99 : const void* const* frames,
100 : size_t num_frames);
101 : const common::StackCapture* SaveStackTrace(
102 : const common::StackCapture& stack_capture);
103 :
104 : // Releases a previously referenced stack trace. This decrements the reference
105 : // count and potentially cleans up the stack trace.
106 : // @param stack_capture The stack capture to be released.
107 : void ReleaseStackTrace(const common::StackCapture* stack_capture);
108 :
109 : // Logs the current stack capture cache statistics. This method is thread
110 : // safe.
111 : void LogStatistics();
112 :
113 : // Checks if a StackCapture pointer seems to be valid. This only ensure that
114 : // it point into a CachePage.
115 : // @param stack_capture The pointer that we want to check.
116 : // @returns true if the pointer is valid, false otherwise.
117 : bool StackCapturePointerIsValid(const common::StackCapture* stack_capture);
118 :
119 : protected:
120 : // The container type in which we store the cached stacks. This enforces
121 : // uniqueness based on their hash value, nothing more.
122 : typedef base::hash_set<common::StackCapture*,
123 : common::StackCapture::HashCompare> StackSet;
124 :
125 : // Used for shuttling around statistics about this cache.
126 : struct Statistics {
127 : // The total number of stacks currently in the cache.
128 : size_t cached;
129 : // The current total size of the stack cache, in bytes.
130 : size_t size;
131 : // The total number of reference-saturated stack captures. These will never
132 : // be able to be removed from the cache.
133 : size_t saturated;
134 : // The number of currently unreferenced stack captures. These are pending
135 : // cleanup.
136 : size_t unreferenced;
137 :
138 : // We use 64-bit integers for the following because they can overflow a
139 : // 32-bit value for long running processes.
140 :
141 : // These count information about stack captures.
142 : // @{
143 : // The total number of stacks requested over the lifetime of the stack
144 : // cache.
145 : uint64 requested;
146 : // The total number of stacks that have had to be allocated. This is not
147 : // necessarily the same as |cached| as the stack cache can reclaim
148 : // unreferenced stacks.
149 : uint64 allocated;
150 : // The total number of active references to stack captures.
151 : uint64 references;
152 : // @}
153 :
154 : // These count information about individual frames.
155 : // @{
156 : // The total number of frames across all active stack captures. This is used
157 : // for calculating our compression ratio. This double counts actually stored
158 : // frames by the number of times they are referenced.
159 : uint64 frames_stored;
160 : // The total number of frames that are physically stored across all active
161 : // stack captures. This does not double count multiply-referenced captures.
162 : uint64 frames_alive;
163 : // The total number of frames in unreferenced stack captures. This is used
164 : // to figure out how much of our cache is actually dead.
165 : uint64 frames_dead;
166 : // @}
167 : };
168 :
169 : // Gets the current cache statistics. This must be called under lock_.
170 : // @param statistics Will be populated with current cache statistics.
171 : void GetStatisticsUnlocked(Statistics* statistics) const;
172 :
173 : // Implementation function for logging statistics.
174 : // @param report The statistics to be reported.
175 : void LogStatisticsImpl(const Statistics& statistics) const;
176 :
177 : // Grabs a temporary StackCapture from reclaimed_ or the current CachePage.
178 : // Must be called under lock_. Takes care of updating frames_dead.
179 : // @param num_frames The minimum number of frames that are required.
180 : common::StackCapture* GetStackCapture(size_t num_frames);
181 :
182 : // Links a stack capture into the reclaimed_ list. Meant to be called by
183 : // ReturnStackCapture only. Must be called under lock_. Takes care of
184 : // updating frames_dead (on behalf of ReturnStackCapture).
185 : // @param stack_capture The stack capture to be linked into reclaimed_.
186 : void AddStackCaptureToReclaimedList(common::StackCapture* stack_capture);
187 :
188 : // The default number of known stacks sets that we keep.
189 : static const size_t kKnownStacksSharding = 16;
190 :
191 : // The number of allocations between reports of the stack trace cache
192 : // compression ratio. Zero (0) means do not report. Values like 1 million
193 : // seem to be pretty good with Chrome.
194 : static size_t compression_reporting_period_;
195 :
196 : // Logger instance to which to report the compression ratio.
197 : AsanLogger* const logger_;
198 :
199 : // Locks to protect the known stacks sets from concurrent access.
200 : mutable base::Lock known_stacks_locks_[kKnownStacksSharding];
201 :
202 : // The max depth of the stack traces to allocate. This can change, but it
203 : // doesn't really make sense to do so.
204 : size_t max_num_frames_;
205 :
206 : // The sets of known stacks. Accessed under known_stacks_locks_.
207 : StackSet known_stacks_[kKnownStacksSharding];
208 :
209 : // A lock protecting access to current_page_.
210 : base::Lock current_page_lock_;
211 :
212 : // The current page from which new stack captures are allocated.
213 : // Accessed under current_page_lock_.
214 : CachePage* current_page_;
215 :
216 : // A lock protecting access to statistics_.
217 : mutable base::Lock stats_lock_;
218 :
219 : // Aggregate statistics about the cache. Accessed under stats_lock_.
220 : Statistics statistics_;
221 :
222 : // Locks to protect each reclaimed list from concurrent access.
223 : base::Lock reclaimed_locks_[common::StackCapture::kMaxNumFrames + 1];
224 :
225 : // StackCaptures that have been reclaimed for reuse are stored in a link list
226 : // according to their length. We reuse the first frame in the stack capture
227 : // as a pointer to the next StackCapture of that size, if there is one.
228 : // Accessed under reclaimed_locks_.
229 : common::StackCapture* reclaimed_[common::StackCapture::kMaxNumFrames + 1];
230 :
231 : private:
232 : DISALLOW_COPY_AND_ASSIGN(StackCaptureCache);
233 : };
234 :
235 : // A page of preallocated stack trace capture objects to be populated
236 : // and stored in the known stacks cache set.
237 : class StackCaptureCache::CachePage {
238 : public:
239 E : explicit CachePage(CachePage* link) : next_page_(link), bytes_used_(0) {
240 E : Shadow::Poison(this, sizeof(CachePage), kAsanMemoryMarker);
241 E : }
242 :
243 : ~CachePage();
244 :
245 : // Allocates a stack capture from this cache page if possible.
246 : // @param max_num_frames The maximum number of frames the object needs to be
247 : // able to store.
248 : // @returns a new StackCapture, or NULL if the page is full.
249 : common::StackCapture* GetNextStackCapture(size_t max_num_frames);
250 :
251 : // Returns the most recently allocated stack capture back to the page.
252 : // @param stack_capture The stack capture to return.
253 : // @returns false if the provided stack capture was not the most recently
254 : // allocated one, true otherwise.
255 : bool ReturnStackCapture(common::StackCapture* stack_capture);
256 :
257 : // @returns the number of bytes used in this page. This is mainly a hook
258 : // for unittesting.
259 E : size_t bytes_used() const { return bytes_used_; }
260 :
261 : // @returns the number of bytes left in this page.
262 E : size_t bytes_left() const { return kDataSize - bytes_used_; }
263 :
264 : // @returns a pointer to the beginning of the stack captures.
265 E : uint8* data() { return data_; }
266 :
267 : // @returns the size of the data.
268 E : size_t data_size() { return kDataSize; }
269 :
270 : protected:
271 : // The parent StackCaptureCache is responsible for cleaning up the linked list
272 : // of cache pages, thus needs access to our internals.
273 : friend StackCaptureCache;
274 :
275 : // The cache pages from a linked list, which allows for easy cleanup
276 : // when the cache is destroyed.
277 : CachePage* next_page_;
278 :
279 : // The number of bytes used, also equal to the byte offset of the next
280 : // StackCapture object to be allocated.
281 : size_t bytes_used_;
282 :
283 : // A page's worth of data, which will be allocated as StackCapture objects.
284 : // NOTE: Using offsetof would be ideal, but we can't do that on an incomplete
285 : // type. Thus, this needs to be maintained.
286 : static const size_t kDataSize = kCachePageSize - sizeof(CachePage*)
287 : - sizeof(size_t);
288 : COMPILE_ASSERT(kDataSize < kCachePageSize,
289 : kCachePageSize_must_be_big_enough_for_CachePage_header);
290 : uint8 data_[kDataSize];
291 :
292 : private:
293 : DISALLOW_COPY_AND_ASSIGN(CachePage);
294 : };
295 : COMPILE_ASSERT(sizeof(StackCaptureCache::CachePage) ==
296 : StackCaptureCache::kCachePageSize,
297 : kDataSize_calculation_needs_to_be_updated);
298 : COMPILE_ASSERT(StackCaptureCache::kCachePageSize % 4096 == 0,
299 : kCachePageSize_should_be_a_multiple_of_the_page_size);
300 :
301 : } // namespace asan
302 : } // namespace agent
303 :
304 : #endif // SYZYGY_AGENT_ASAN_STACK_CAPTURE_CACHE_H_
|