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