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() const;
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. This isn't actually
122 : // updated in realtime, as this is the same as known_stacks_.size(). It is
123 : // populated when we take a snapshot of the statistics with GetStatistics.
124 : size_t cached;
125 : // The current total size of the stack cache, in bytes.
126 : size_t size;
127 : // The total number of reference-saturated stack captures. These will never
128 : // be able to be removed from the cache.
129 : size_t saturated;
130 : // The number of currently unreferenced stack captures. These are pending
131 : // cleanup.
132 : size_t unreferenced;
133 :
134 : // We use 64-bit integers for the following because they can overflow a
135 : // 32-bit value for long running processes.
136 :
137 : // These count information about stack captures.
138 : // @{
139 : // The total number of stacks requested over the lifetime of the stack
140 : // cache.
141 : uint64 requested;
142 : // The total number of stacks that have had to be allocated. This is not
143 : // necessarily the same as |cached| as the stack cache can reclaim
144 : // unreferenced stacks.
145 : uint64 allocated;
146 : // The total number of active references to stack captures.
147 : uint64 references;
148 : // @}
149 :
150 : // These count information about individual frames.
151 : // @{
152 : // The total number of frames across all active stack captures. This is used
153 : // for calculating our compression ratio. This double counts actually stored
154 : // frames by the number of times they are referenced.
155 : uint64 frames_stored;
156 : // The total number of frames that are physically stored across all active
157 : // stack captures. This does not double count multiply-referenced captures.
158 : uint64 frames_alive;
159 : // The total number of frames in unreferenced stack captures. This is used
160 : // to figure out how much of our cache is actually dead.
161 : uint64 frames_dead;
162 : // @}
163 : };
164 :
165 : // Gets the current cache statistics. This must be called under lock_.
166 : // @param statistics Will be populated with current cache statistics.
167 : void GetStatisticsUnlocked(Statistics* statistics) const;
168 :
169 : // Implementation function for logging statistics.
170 : // @param report The statistics to be reported.
171 : void LogStatisticsImpl(const Statistics& statistics) const;
172 :
173 : // Grabs a temporary StackCapture from reclaimed_ or the current CachePage.
174 : // Must be called under lock_. Takes care of updating frames_dead.
175 : // @param num_frames The minimum number of frames that are required.
176 : StackCapture* GetStackCapture(size_t num_frames);
177 :
178 : // Returns a StackCapture to reclaimed_ or the current CachePage.
179 : // Must be called under lock_. Takes care of updating frames_dead.
180 : // @param stack_capture The stack to be returned either to the active cache
181 : // page or to the reclaimed_ array.
182 : void ReturnStackCapture(StackCapture* stack_capture);
183 :
184 : // Links a stack capture into the reclaimed_ list. Meant to be called by
185 : // ReturnStackCapture only. Must be called under lock_. Takes care of updating
186 : // frames_dead (on behalf of ReturnStackCapture).
187 : // @param stack_capture The stack capture to be linked into reclaimed_.
188 : void AddStackCaptureToReclaimedList(StackCapture* stack_capture);
189 :
190 : // The default number of iterations between each compression ratio report.
191 : // Zero (0) means do not report.
192 : static const size_t kDefaultCompressionReportingPeriod = 0;
193 :
194 : // The number of allocations between reports of the stack trace cache
195 : // compression ratio. Zero (0) means do not report. Values like 1 million
196 : // seem to be pretty good with Chrome.
197 : static size_t compression_reporting_period_;
198 :
199 : // Logger instance to which to report the compression ratio.
200 : AsanLogger* const logger_;
201 :
202 : // A lock to protect the known stacks set from concurrent access.
203 : mutable base::Lock lock_;
204 :
205 : // The max depth of the stack traces to allocate. This can change, but it
206 : // doesn't really make sense to do so.
207 : size_t max_num_frames_;
208 :
209 : // The set of known stacks. Accessed under lock_.
210 : StackSet known_stacks_;
211 :
212 : // The current page from which new stack captures are allocated.
213 : // Accessed under lock_.
214 : CachePage* current_page_;
215 :
216 : // Aggregate statistics about the cache. Accessed under lock_.
217 : Statistics statistics_;
218 :
219 : // StackCaptures that have been reclaimed for reuse are stored in a link list
220 : // according to their length. We reuse the first frame in the stack capture
221 : // as a pointer to the next StackCapture of that size, if there is one.
222 : StackCapture* reclaimed_[StackCapture::kMaxNumFrames + 1];
223 :
224 : private:
225 : DISALLOW_COPY_AND_ASSIGN(StackCaptureCache);
226 : };
227 :
228 : // A page of preallocated stack trace capture objects to be populated
229 : // and stored in the known stacks cache set.
230 : class StackCaptureCache::CachePage {
231 : public:
232 E : explicit CachePage(CachePage* link) : next_page_(link), bytes_used_(0) {
233 E : Shadow::Poison(this, sizeof(CachePage), Shadow::kAsanMemoryByte);
234 E : }
235 :
236 : ~CachePage();
237 :
238 : // Allocates a stack capture from this cache page if possible.
239 : // @param max_num_frames The maximum number of frames the object needs to be
240 : // able to store.
241 : // @returns a new StackCapture, or NULL if the page is full.
242 : StackCapture* GetNextStackCapture(size_t max_num_frames);
243 :
244 : // Returns the most recently allocated stack capture back to the page.
245 : // @param stack_capture The stack capture to return.
246 : // @returns false if the provided stack capture was not the most recently
247 : // allocated one, true otherwise.
248 : bool ReturnStackCapture(StackCapture* stack_capture);
249 :
250 : // @returns the number of bytes used in this page. This is mainly a hook
251 : // for unittesting.
252 E : size_t bytes_used() const { return bytes_used_; }
253 :
254 : // @returns the number of bytes left in this page.
255 E : size_t bytes_left() const { return kDataSize - bytes_used_; }
256 :
257 : protected:
258 : // The cache pages from a linked list, which allows for easy cleanup
259 : // when the cache is destroyed.
260 : CachePage* next_page_;
261 :
262 : // The number of bytes used, also equal to the byte offset of the next
263 : // StackCapture object to be allocated.
264 : size_t bytes_used_;
265 :
266 : // A page's worth of data, which will be allocated as StackCapture objects.
267 : // NOTE: Using offsetof would be ideal, but we can't do that on an incomplete
268 : // type. Thus, this needs to be maintained.
269 : static const size_t kDataSize = kCachePageSize - sizeof(CachePage*)
270 : - sizeof(size_t);
271 : COMPILE_ASSERT(kDataSize < kCachePageSize,
272 : kCachePageSize_must_be_big_enough_for_CachePage_header);
273 : uint8 data_[kDataSize];
274 :
275 : private:
276 : DISALLOW_COPY_AND_ASSIGN(CachePage);
277 : };
278 : COMPILE_ASSERT(sizeof(StackCaptureCache::CachePage) ==
279 : StackCaptureCache::kCachePageSize,
280 : kDataSize_calculation_needs_to_be_updated);
281 : COMPILE_ASSERT(StackCaptureCache::kCachePageSize % 4096 == 0,
282 : kCachePageSize_should_be_a_multiple_of_the_page_size);
283 :
284 : } // namespace asan
285 : } // namespace agent
286 :
287 : #endif // SYZYGY_AGENT_ASAN_STACK_CAPTURE_CACHE_H_
|