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 <unordered_map>
19 :
20 : #include "base/observer_list.h"
21 : #include "base/synchronization/lock.h"
22 : #include "syzygy/agent/asan/shadow.h"
23 : #include "syzygy/agent/common/stack_capture.h"
24 : #include "syzygy/common/asan_parameters.h"
25 :
26 : namespace agent {
27 : namespace asan {
28 :
29 : // Forward declarations.
30 : class AsanLogger;
31 : class MemoryNotifierInterface;
32 :
33 : // A class which manages a thread-safe cache of unique stack traces, by ID.
34 : class StackCaptureCache {
35 : public:
36 : // The size of a page of stack captures, in bytes. This should be in the
37 : // hundreds of KB or low MBs so that we have an efficient pooled allocator
38 : // that can store hundreds to thousands of stack captures, yet whose
39 : // incremental growth is not too large.
40 : static const size_t kCachePageSize = 1024 * 1024;
41 :
42 : // The type used to uniquely identify a stack.
43 : typedef common::StackCapture::StackId StackId;
44 :
45 : // Forward declaration.
46 : class CachePage;
47 :
48 : // TODO(chrisha): Plumb a command-line parameter through to control the
49 : // max depth of stack traces in the StackCaptureCache. This should get us
50 : // significant memory savings in the stack trace cache.
51 :
52 : // Initializes a new stack capture cache.
53 : // @param logger The logger to use.
54 : // @param memory_notifier The memory notifier to use.
55 : // @param max_num_frames The maximum number of frames to be used by the
56 : // StackCapture objects in this cache.
57 : StackCaptureCache(AsanLogger* logger,
58 : MemoryNotifierInterface* memory_notifier);
59 : StackCaptureCache(AsanLogger* logger,
60 : MemoryNotifierInterface* memory_notifier,
61 : size_t max_num_frames);
62 :
63 : // Destroys a stack capture cache.
64 : ~StackCaptureCache();
65 :
66 : // Static initialisation of StackCaptureCache context.
67 : static void Init();
68 :
69 : // @returns the current maximum number of frames supported by saved stack
70 : // traces.
71 E : size_t max_num_frames() const { return max_num_frames_; }
72 :
73 : // Sets the current maximum number of frames supported by saved stack traces.
74 : // @param max_num_frames The maximum number of frames to set.
75 E : void set_max_num_frames(size_t max_num_frames) {
76 E : max_num_frames_ = max_num_frames;
77 E : }
78 :
79 : // @returns the default compression reporting period value.
80 E : static size_t GetDefaultCompressionReportingPeriod() {
81 E : return ::common::kDefaultReportingPeriod;
82 E : }
83 :
84 : // Sets a new (global) compression reporting period value. Note that this
85 : // method is not thread safe. It is expected to be called once at startup,
86 : // or not at all.
87 E : static void set_compression_reporting_period(size_t period) {
88 E : compression_reporting_period_ = period;
89 E : }
90 :
91 : // @returns the current (global) compression reporting period value. It is
92 : // expected that this value is a constant after initialization.
93 E : static size_t compression_reporting_period() {
94 E : return compression_reporting_period_;
95 E : }
96 :
97 : // Save (or retrieve) the stack capture into the cache using its
98 : // absolute_stack_id as the key.
99 : // @param stack_capture The initialized stack capture to save.
100 : // @returns a pointer to the saved stack capture.
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 : // Observer that is notified when a new stack is saved.
120 : class Observer {
121 : public:
122 : virtual void OnNewStack(common::StackCapture* new_stack) = 0;
123 : };
124 : // Adds an observer for this class. An observer should not be added more
125 : // than once. The caller retains the ownership of the observer object.
126 : // @param obs the observer to add.
127 : void AddObserver(Observer* obs);
128 : // Removes an observer.
129 : // @param obs the observer to remove.
130 : void RemoveObserver(Observer* obs);
131 :
132 : protected:
133 : // The container type in which we store the cached stacks. This enforces
134 : // uniqueness based on their hash value, nothing more.
135 : typedef std::unordered_map<StackId, common::StackCapture*> StackMap;
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_t 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_t allocated;
162 : // The total number of active references to stack captures.
163 : uint64_t 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_t 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_t 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_t 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 maps of known stacks. Accessed under known_stacks_locks_.
225 : StackMap 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_t* 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_t 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_
|