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