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