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 : #include "syzygy/agent/asan/stack_capture_cache.h"
16 :
17 : #include <algorithm>
18 :
19 : #include "base/logging.h"
20 : #include "base/strings/stringprintf.h"
21 : #include "syzygy/agent/asan/logger.h"
22 : #include "syzygy/agent/asan/memory_notifier.h"
23 : #include "syzygy/agent/common/stack_capture.h"
24 : #include "syzygy/common/align.h"
25 :
26 : namespace agent {
27 : namespace asan {
28 :
29 : namespace {
30 :
31 : // Gives us access to the first frame of a stack capture as link-list pointer.
32 : common::StackCapture** GetFirstFrameAsLink(
33 E : common::StackCapture* stack_capture) {
34 E : DCHECK_NE(static_cast<common::StackCapture*>(nullptr), stack_capture);
35 : common::StackCapture** link = reinterpret_cast<common::StackCapture**>(
36 E : const_cast<void**>(stack_capture->frames()));
37 E : DCHECK_NE(static_cast<common::StackCapture**>(nullptr), link);
38 E : return link;
39 E : }
40 :
41 : } // namespace
42 :
43 : size_t StackCaptureCache::compression_reporting_period_ =
44 E : ::common::kDefaultReportingPeriod;
45 :
46 : StackCaptureCache::CachePage::~CachePage() {
47 : }
48 :
49 : // static
50 : StackCaptureCache::CachePage* StackCaptureCache::CachePage::CreateInPlace(
51 E : void* alloc, CachePage* link) {
52 : // Use a placement new.
53 E : return new(alloc) CachePage(link);
54 E : }
55 :
56 : common::StackCapture* StackCaptureCache::CachePage::GetNextStackCapture(
57 E : size_t max_num_frames, size_t metadata_size) {
58 E : metadata_size = ::common::AlignUp(metadata_size, sizeof(void*));
59 :
60 E : size_t stack_size = common::StackCapture::GetSize(max_num_frames);
61 E : size_t size = stack_size + metadata_size;
62 E : if (bytes_used_ + size > kDataSize)
63 E : return nullptr;
64 :
65 : // Use placement new for the StackCapture and zero initialize the metadata.
66 : common::StackCapture* stack =
67 E : new(data_ + bytes_used_) common::StackCapture(max_num_frames);
68 E : ::memset(data_ + bytes_used_ + stack_size, 0, metadata_size);
69 :
70 : // Update the allocation cursor.
71 E : bytes_used_ += size;
72 :
73 E : return stack;
74 E : }
75 :
76 : common::StackCapture* StackCaptureCache::CachePage::GetNextStackCapture(
77 E : size_t max_num_frames) {
78 E : return GetNextStackCapture(max_num_frames, 0);
79 E : }
80 :
81 : bool StackCaptureCache::CachePage::ReturnStackCapture(
82 E : common::StackCapture* stack_capture, size_t metadata_size) {
83 E : DCHECK_NE(static_cast<common::StackCapture*>(nullptr), stack_capture);
84 :
85 E : metadata_size = ::common::AlignUp(metadata_size, sizeof(void*));
86 :
87 E : uint8* stack = reinterpret_cast<uint8*>(stack_capture);
88 E : size_t size = stack_capture->Size() + metadata_size;
89 :
90 : // If this was the last stack capture provided by this page then the end of
91 : // it must align with our current data pointer.
92 E : if (data_ + bytes_used_ != stack + size)
93 i : return false;
94 :
95 E : bytes_used_ -= size;
96 E : return true;
97 E : }
98 :
99 : bool StackCaptureCache::CachePage::ReturnStackCapture(
100 E : common::StackCapture* stack_capture) {
101 E : return ReturnStackCapture(stack_capture, 0);
102 E : }
103 :
104 : StackCaptureCache::StackCaptureCache(
105 : AsanLogger* logger, MemoryNotifierInterface* memory_notifier)
106 : : logger_(logger),
107 : memory_notifier_(memory_notifier),
108 : max_num_frames_(common::StackCapture::kMaxNumFrames),
109 E : current_page_(nullptr) {
110 E : DCHECK_NE(static_cast<AsanLogger*>(nullptr), logger);
111 E : DCHECK_NE(static_cast<MemoryNotifierInterface*>(nullptr), memory_notifier);
112 :
113 E : AllocateCachePage();
114 :
115 E : ::memset(&statistics_, 0, sizeof(statistics_));
116 E : ::memset(reclaimed_, 0, sizeof(reclaimed_));
117 E : statistics_.size = sizeof(CachePage);
118 E : }
119 :
120 : StackCaptureCache::StackCaptureCache(
121 : AsanLogger* logger, MemoryNotifierInterface* memory_notifier,
122 : size_t max_num_frames)
123 : : logger_(logger),
124 : memory_notifier_(memory_notifier),
125 : max_num_frames_(0),
126 E : current_page_(nullptr) {
127 E : DCHECK_NE(static_cast<AsanLogger*>(nullptr), logger);
128 E : DCHECK_NE(static_cast<MemoryNotifierInterface*>(nullptr), memory_notifier);
129 E : DCHECK_LT(0u, max_num_frames);
130 : max_num_frames_ = static_cast<uint8>(
131 E : std::min(max_num_frames, common::StackCapture::kMaxNumFrames));
132 :
133 E : AllocateCachePage();
134 E : ::memset(&statistics_, 0, sizeof(statistics_));
135 E : ::memset(reclaimed_, 0, sizeof(reclaimed_));
136 E : statistics_.size = sizeof(CachePage);
137 E : }
138 :
139 E : StackCaptureCache::~StackCaptureCache() {
140 : // Clean up the linked list of cache pages.
141 E : while (current_page_ != nullptr) {
142 E : CachePage* page = current_page_;
143 E : current_page_ = page->next_page_;
144 E : page->next_page_ = nullptr;
145 :
146 E : memory_notifier_->NotifyReturnedToOS(page, sizeof(*page));
147 :
148 : // This should have been allocated by VirtuaAlloc, so should be aligned.
149 E : DCHECK(::common::IsAligned(page, GetPageSize()));
150 E : CHECK_EQ(TRUE, ::VirtualFree(page, 0, MEM_RELEASE));
151 E : }
152 E : }
153 :
154 E : void StackCaptureCache::Init() {
155 E : compression_reporting_period_ = ::common::kDefaultReportingPeriod;
156 E : }
157 :
158 : const common::StackCapture* StackCaptureCache::SaveStackTrace(
159 E : const common::StackCapture& stack_capture) {
160 E : auto frames = stack_capture.frames();
161 E : auto num_frames = stack_capture.num_frames();
162 E : auto absolute_stack_id = stack_capture.absolute_stack_id();
163 E : DCHECK_NE(static_cast<void**>(nullptr), frames);
164 E : DCHECK_NE(num_frames, 0U);
165 E : DCHECK_NE(static_cast<CachePage*>(nullptr), current_page_);
166 :
167 E : bool already_cached = false;
168 E : common::StackCapture* stack_trace = nullptr;
169 E : bool saturated = false;
170 :
171 : {
172 E : size_t known_stack_shard = absolute_stack_id % kKnownStacksSharding;
173 : // Get or insert the current stack trace while under the lock for this
174 : // bucket.
175 E : base::AutoLock auto_lock(known_stacks_locks_[known_stack_shard]);
176 :
177 : // Check if the stack capture is already in the cache map. It's fine to
178 : // remove the const as this call will not modify |stack_capture|.
179 : StackSet::iterator result = known_stacks_[known_stack_shard].find(
180 E : const_cast<common::StackCapture*>(&stack_capture));
181 :
182 : // If this capture has not already been cached then we have to initialize
183 : // the data.
184 E : if (result == known_stacks_[known_stack_shard].end()) {
185 E : stack_trace = GetStackCapture(num_frames);
186 E : DCHECK_NE(static_cast<common::StackCapture*>(nullptr), stack_trace);
187 E : stack_trace->InitFromExistingStack(stack_capture);
188 E : auto result = known_stacks_[known_stack_shard].insert(stack_trace);
189 E : DCHECK(result.second);
190 E : DCHECK(stack_trace->HasNoRefs());
191 E : FOR_EACH_OBSERVER(Observer, observer_list_, OnNewStack(stack_trace));
192 E : } else {
193 E : already_cached = true;
194 E : stack_trace = *result;
195 : }
196 : // Increment the reference count for this stack trace.
197 E : if (!stack_trace->RefCountIsSaturated()) {
198 E : stack_trace->AddRef();
199 E : } else {
200 E : saturated = true;
201 : }
202 E : }
203 E : DCHECK_NE(static_cast<common::StackCapture*>(nullptr), stack_trace);
204 :
205 E : bool must_log = false;
206 E : Statistics statistics = {};
207 : // Update the statistics.
208 E : if (compression_reporting_period_ != 0) {
209 E : base::AutoLock stats_lock(stats_lock_);
210 E : if (already_cached) {
211 : // If the existing stack capture is previously unreferenced and becoming
212 : // referenced again, then decrement the unreferenced counter.
213 E : if (stack_trace->HasNoRefs()) {
214 i : DCHECK_LT(0u, statistics_.unreferenced);
215 i : --statistics_.unreferenced;
216 : }
217 E : } else {
218 E : ++statistics_.cached;
219 E : statistics_.frames_alive += num_frames;
220 E : ++statistics_.allocated;
221 : }
222 E : if (!saturated && stack_trace->RefCountIsSaturated()) {
223 E : saturated = true;
224 E : ++statistics_.saturated;
225 : }
226 E : ++statistics_.requested;
227 E : ++statistics_.references;
228 E : statistics_.frames_stored += num_frames;
229 E : if (statistics_.requested % compression_reporting_period_ == 0) {
230 E : must_log = true;
231 E : GetStatisticsUnlocked(&statistics);
232 : }
233 E : }
234 :
235 E : if (must_log)
236 E : LogStatisticsImpl(statistics);
237 :
238 : // Return the stack trace pointer that is now in the cache.
239 E : return stack_trace;
240 E : }
241 :
242 : void StackCaptureCache::ReleaseStackTrace(
243 E : const common::StackCapture* stack_capture) {
244 E : DCHECK_NE(static_cast<common::StackCapture*>(nullptr), stack_capture);
245 :
246 : size_t known_stack_shard =
247 E : stack_capture->absolute_stack_id() % kKnownStacksSharding;
248 E : bool add_to_reclaimed_list = false;
249 E : common::StackCapture* stack = nullptr;
250 : {
251 E : base::AutoLock auto_lock(known_stacks_locks_[known_stack_shard]);
252 :
253 : // We own the stack so its fine to remove the const. We double check this
254 : // is the case in debug builds with the DCHECK.
255 E : stack = const_cast<common::StackCapture*>(stack_capture);
256 : DCHECK(known_stacks_[known_stack_shard].find(stack) !=
257 E : known_stacks_[known_stack_shard].end());
258 :
259 E : stack->RemoveRef();
260 :
261 E : if (stack->HasNoRefs()) {
262 E : add_to_reclaimed_list = true;
263 : // Remove this from the known stacks as we're going to reclaim it and
264 : // overwrite part of its data as we insert into the reclaimed_ list.
265 E : size_t num_erased = known_stacks_[known_stack_shard].erase(stack);
266 E : DCHECK_EQ(num_erased, 1u);
267 : }
268 E : }
269 :
270 : // Update the statistics.
271 E : if (compression_reporting_period_ != 0) {
272 E : base::AutoLock stats_lock(stats_lock_);
273 E : DCHECK_LT(0u, statistics_.references);
274 E : --statistics_.references;
275 E : statistics_.frames_stored -= stack->num_frames();
276 E : if (add_to_reclaimed_list) {
277 E : --statistics_.cached;
278 E : ++statistics_.unreferenced;
279 : // The frames in this stack capture are no longer alive.
280 E : statistics_.frames_alive -= stack->num_frames();
281 : }
282 E : }
283 :
284 : // Link this stack capture into the list of reclaimed stacks. This
285 : // must come after the statistics updating, as we modify the |num_frames|
286 : // parameter in place.
287 E : if (add_to_reclaimed_list)
288 E : AddStackCaptureToReclaimedList(stack);
289 E : }
290 :
291 : bool StackCaptureCache::StackCapturePointerIsValid(
292 E : const common::StackCapture* stack_capture) {
293 : // All stack captures must have pointer alignment at least.
294 E : if (!::common::IsAligned(stack_capture, sizeof(uintptr_t)))
295 E : return false;
296 :
297 : const uint8* stack_capture_addr =
298 E : reinterpret_cast<const uint8*>(stack_capture);
299 :
300 : // Walk over the allocated pages and see if it lands within any of them.
301 E : base::AutoLock lock(current_page_lock_);
302 E : CachePage* page = current_page_;
303 E : while (page != nullptr) {
304 E : const uint8* page_end = page->data() + page->bytes_used();
305 :
306 : // If the proposed stack capture lands within a page we then check to
307 : // ensure that it is also internally consistent. This can still fail
308 : // but is somewhat unlikely.
309 E : static const size_t kMinSize = common::StackCapture::GetSize(1);
310 : if (stack_capture_addr >= page->data() &&
311 : stack_capture_addr + kMinSize <= page_end &&
312 : stack_capture_addr + stack_capture->Size() <= page_end &&
313 : stack_capture->num_frames() <= stack_capture->max_num_frames() &&
314 : stack_capture->max_num_frames() <=
315 E : common::StackCapture::kMaxNumFrames) {
316 E : return true;
317 : }
318 E : page = page->next_page_;
319 E : }
320 E : return false;
321 E : }
322 :
323 E : void StackCaptureCache::AddObserver(Observer* obs) {
324 E : observer_list_.AddObserver(obs);
325 E : }
326 :
327 : void StackCaptureCache::RemoveObserver(Observer* obs) {
328 : observer_list_.RemoveObserver(obs);
329 : }
330 :
331 E : void StackCaptureCache::LogStatistics() {
332 E : Statistics statistics = {};
333 :
334 : {
335 E : base::AutoLock auto_lock(stats_lock_);
336 E : GetStatisticsUnlocked(&statistics);
337 E : }
338 :
339 E : LogStatisticsImpl(statistics);
340 E : }
341 :
342 E : void StackCaptureCache::AllocateCachePage() {
343 : static_assert(sizeof(CachePage) % (64 * 1024) == 0,
344 : "kCachePageSize should be a multiple of the system allocation "
345 : "granularity.");
346 :
347 : void* new_page = ::VirtualAlloc(nullptr, sizeof(CachePage), MEM_COMMIT,
348 E : PAGE_READWRITE);
349 E : CHECK_NE(static_cast<void*>(nullptr), new_page);
350 :
351 : // Use a placement new and notify the shadow memory.
352 E : current_page_ = CachePage::CreateInPlace(new_page, current_page_);
353 E : memory_notifier_->NotifyInternalUse(new_page, sizeof(CachePage));
354 E : }
355 :
356 E : void StackCaptureCache::GetStatisticsUnlocked(Statistics* statistics) const {
357 : #ifndef NDEBUG
358 E : stats_lock_.AssertAcquired();
359 : #endif
360 :
361 E : DCHECK_NE(static_cast<Statistics*>(nullptr), statistics);
362 E : *statistics = statistics_;
363 E : }
364 :
365 E : void StackCaptureCache::LogStatisticsImpl(const Statistics& statistics) const {
366 : // The cache has 3 categories of storage.
367 : // alive frames: these are actively participating in storing a stack trace.
368 : // dead frames: these are unreferenced stack traces that are eligible for
369 : // reuse, but are currently dormant.
370 : // overhead: frames in a stack-capture that aren't used, padding at the end
371 : // cache pages, cache page metadata, stack capture metadata, etc.
372 :
373 : // These are all in bytes.
374 E : double cache_size = statistics.size;
375 E : double alive_size = statistics.frames_alive * 4;
376 E : double dead_size = statistics.frames_dead * 4;
377 E : double stored_size = statistics.frames_stored * 4;
378 :
379 : // The |cache_size| is the actual size of storage taken, while |stored_size|
380 : // is the conceptual amount of frame data that is stored in the cache.
381 E : double compression = 100.0 * (1.0 - (cache_size / stored_size));
382 E : double alive = 100.0 * alive_size / cache_size;
383 E : double dead = 100.0 * dead_size / cache_size;
384 E : double overhead = 100.0 - alive - dead;
385 :
386 : logger_->Write(base::StringPrintf(
387 : "PID=%d; Stack cache size=%.2f MB; Compression=%.2f%%; "
388 : "Alive=%.2f%%; Dead=%.2f%%; Overhead=%.2f%%; Saturated=%d; Entries=%d",
389 : ::GetCurrentProcessId(),
390 : cache_size / 1024.0 / 1024.0,
391 : compression,
392 : alive,
393 : dead,
394 : overhead,
395 : statistics.saturated,
396 E : statistics.cached));
397 E : }
398 :
399 E : common::StackCapture* StackCaptureCache::GetStackCapture(size_t num_frames) {
400 E : common::StackCapture* stack_capture = nullptr;
401 :
402 : // First look to the reclaimed stacks and try to use one of those. We'll use
403 : // the first one that's big enough.
404 E : for (size_t n = num_frames; n <= max_num_frames_; ++n) {
405 E : base::AutoLock lock(reclaimed_locks_[n]);
406 E : if (reclaimed_[n] != nullptr) {
407 E : common::StackCapture* reclaimed_stack_capture = reclaimed_[n];
408 : common::StackCapture** link =
409 E : GetFirstFrameAsLink(reclaimed_stack_capture);
410 E : reclaimed_[n] = *link;
411 E : stack_capture = reclaimed_stack_capture;
412 E : break;
413 : }
414 E : }
415 :
416 E : if (stack_capture != nullptr) {
417 E : if (compression_reporting_period_ != 0) {
418 i : base::AutoLock stats_lock(stats_lock_);
419 : // These frames are no longer dead, but in limbo. If the stack capture
420 : // is used they'll be added to frames_alive and frames_stored.
421 i : statistics_.frames_dead -= stack_capture->max_num_frames();
422 i : }
423 E : return stack_capture;
424 : }
425 :
426 E : common::StackCapture* unused_stack_capture = nullptr;
427 : {
428 E : base::AutoLock current_page_lock(current_page_lock_);
429 :
430 : // We didn't find a reusable stack capture. Go to the cache page.
431 E : stack_capture = current_page_->GetNextStackCapture(num_frames);
432 :
433 E : if (stack_capture != nullptr)
434 E : return stack_capture;
435 :
436 : // If the allocation failed we don't have enough room on the current page.
437 :
438 : // Use the remaining bytes to create one more maximally sized stack
439 : // capture. We will stuff this into the reclaimed_ structure for later
440 : // use.
441 E : size_t bytes_left = current_page_->bytes_left();
442 E : size_t max_num_frames = common::StackCapture::GetMaxNumFrames(bytes_left);
443 E : if (max_num_frames > 0) {
444 i : DCHECK_LT(max_num_frames, num_frames);
445 i : DCHECK_LE(common::StackCapture::GetSize(max_num_frames), bytes_left);
446 : unused_stack_capture =
447 i : current_page_->GetNextStackCapture(max_num_frames);
448 : DCHECK_NE(static_cast<common::StackCapture*>(nullptr),
449 i : unused_stack_capture);
450 : }
451 :
452 : // Allocate a new page (that links to the current page) and use it to
453 : // allocate a new stack capture.
454 E : AllocateCachePage();
455 E : CHECK_NE(static_cast<CachePage*>(nullptr), current_page_);
456 E : statistics_.size += sizeof(CachePage);
457 E : stack_capture = current_page_->GetNextStackCapture(num_frames);
458 E : }
459 :
460 E : if (unused_stack_capture != nullptr) {
461 : // We're creating an unreferenced stack capture.
462 i : AddStackCaptureToReclaimedList(unused_stack_capture);
463 : }
464 :
465 : // Update the statistics.
466 E : if (compression_reporting_period_ != 0) {
467 i : base::AutoLock stats_lock(stats_lock_);
468 i : ++statistics_.unreferenced;
469 i : }
470 :
471 E : DCHECK_NE(static_cast<common::StackCapture*>(nullptr), stack_capture);
472 E : return stack_capture;
473 E : }
474 :
475 : namespace {
476 :
477 : class PrivateStackCapture : public common::StackCapture {
478 : public:
479 : // Expose the actual number of frames. We use this to make reclaimed
480 : // stack captures look invalid when they're in a free list.
481 : using common::StackCapture::num_frames_;
482 : };
483 :
484 : }
485 :
486 : void StackCaptureCache::AddStackCaptureToReclaimedList(
487 E : common::StackCapture* stack_capture) {
488 E : DCHECK_NE(static_cast<common::StackCapture*>(nullptr), stack_capture);
489 :
490 : // Make the stack capture internally inconsistent so that it can't be
491 : // interpreted as being valid. This is rewritten upon reuse so not
492 : // dangerous.
493 : reinterpret_cast<PrivateStackCapture*>(stack_capture)->num_frames_ =
494 E : UINT8_MAX;
495 :
496 : {
497 E : base::AutoLock lock(reclaimed_locks_[stack_capture->max_num_frames()]);
498 :
499 E : common::StackCapture** link = GetFirstFrameAsLink(stack_capture);
500 E : size_t num_frames = stack_capture->max_num_frames();
501 E : *link = reclaimed_[num_frames];
502 E : reclaimed_[num_frames] = stack_capture;
503 E : }
504 :
505 : // Update the statistics.
506 E : if (compression_reporting_period_ != 0) {
507 E : base::AutoLock stats_lock(stats_lock_);
508 E : statistics_.frames_dead += stack_capture->max_num_frames();
509 E : }
510 E : }
511 :
512 : } // namespace asan
513 : } // namespace agent
|