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 "base/logging.h"
18 : #include "base/stringprintf.h"
19 : #include "syzygy/agent/asan/asan_logger.h"
20 : #include "syzygy/agent/asan/stack_capture.h"
21 :
22 : namespace agent {
23 : namespace asan {
24 :
25 : namespace {
26 :
27 : // Gives us access to the first frame of a stack capture as link-list pointer.
28 E : StackCapture** GetFirstFrameAsLink(StackCapture* stack_capture) {
29 E : DCHECK(stack_capture != NULL);
30 : StackCapture** link = reinterpret_cast<StackCapture**>(
31 E : const_cast<void**>(stack_capture->frames()));
32 E : DCHECK(link != NULL);
33 E : return link;
34 E : }
35 :
36 : } // namespace
37 :
38 : size_t StackCaptureCache::compression_reporting_period_ =
39 : StackCaptureCache::kDefaultCompressionReportingPeriod;
40 :
41 E : StackCaptureCache::CachePage::~CachePage() {
42 E : if (next_page_ != NULL)
43 i : delete next_page_;
44 E : }
45 :
46 : StackCapture* StackCaptureCache::CachePage::GetNextStackCapture(
47 E : size_t max_num_frames) {
48 E : size_t size = StackCapture::GetSize(max_num_frames);
49 E : if (bytes_used_ + size > kDataSize)
50 E : return NULL;
51 :
52 : // Use placement new.
53 E : StackCapture* stack = new(data_ + bytes_used_) StackCapture(max_num_frames);
54 E : bytes_used_ += size;
55 :
56 E : return stack;
57 E : }
58 :
59 : bool StackCaptureCache::CachePage::ReturnStackCapture(
60 E : StackCapture* stack_capture) {
61 E : DCHECK(stack_capture != NULL);
62 :
63 E : uint8* stack = reinterpret_cast<uint8*>(stack_capture);
64 E : size_t size = stack_capture->Size();
65 :
66 : // If this was the last stack capture provided by this page then the end of
67 : // it must align with our current data pointer.
68 E : if (data_ + bytes_used_ != stack + size)
69 E : return false;
70 :
71 E : bytes_used_ -= size;
72 E : return true;
73 E : }
74 :
75 : StackCaptureCache::StackCaptureCache(AsanLogger* logger)
76 : : logger_(logger),
77 : max_num_frames_(StackCapture::kMaxNumFrames),
78 E : current_page_(new CachePage(NULL)) {
79 E : CHECK(current_page_ != NULL);
80 E : DCHECK(logger_ != NULL);
81 E : ::memset(&statistics_, 0, sizeof(statistics_));
82 E : ::memset(reclaimed_, 0, sizeof(reclaimed_));
83 E : statistics_.size = sizeof(CachePage);
84 E : }
85 :
86 : StackCaptureCache::StackCaptureCache(AsanLogger* logger, size_t max_num_frames)
87 : : logger_(logger),
88 : max_num_frames_(0),
89 E : current_page_(new CachePage(NULL)) {
90 E : CHECK(current_page_ != NULL);
91 E : DCHECK(logger_ != NULL);
92 E : DCHECK_LT(0u, max_num_frames);
93 : max_num_frames_ = static_cast<uint8>(
94 E : std::min(max_num_frames, StackCapture::kMaxNumFrames));
95 E : ::memset(&statistics_, 0, sizeof(statistics_));
96 E : ::memset(reclaimed_, 0, sizeof(reclaimed_));
97 E : statistics_.size = sizeof(CachePage);
98 E : }
99 :
100 E : StackCaptureCache::~StackCaptureCache() {
101 E : if (current_page_ != NULL)
102 E : delete current_page_;
103 E : }
104 :
105 E : void StackCaptureCache::Init() {
106 E : compression_reporting_period_ = kDefaultCompressionReportingPeriod;
107 E : }
108 :
109 : const StackCapture* StackCaptureCache::SaveStackTrace(
110 E : StackId stack_id, const void* const* frames, size_t num_frames) {
111 E : DCHECK(frames != NULL);
112 E : DCHECK(num_frames != 0);
113 E : DCHECK(current_page_ != NULL);
114 :
115 E : bool must_log = false;
116 E : Statistics statistics = {};
117 E : StackCapture* stack_trace = NULL;
118 :
119 : {
120 : // Get or insert the current stack trace while under the lock.
121 E : base::AutoLock auto_lock(lock_);
122 :
123 : // Get a stack capture to use.
124 E : StackCapture* unused_trace = GetStackCapture(num_frames);
125 E : DCHECK(unused_trace != NULL);
126 :
127 : // Attempt to insert it into the known stacks map.
128 E : unused_trace->set_stack_id(stack_id);
129 : std::pair<StackSet::iterator, bool> result = known_stacks_.insert(
130 E : unused_trace);
131 E : ++statistics_.requested;
132 E : stack_trace = *result.first;
133 :
134 : // If the insertion was successful, then this capture has not already been
135 : // cached and we have to initialize the data.
136 E : if (result.second) {
137 E : DCHECK_EQ(unused_trace, stack_trace);
138 E : unused_trace->InitFromBuffer(stack_id, frames, num_frames);
139 E : ++statistics_.allocated;
140 E : statistics_.frames_alive += num_frames;
141 E : DCHECK(stack_trace->HasNoRefs());
142 E : } else {
143 : // If we didn't need the stack capture then return it.
144 E : ReturnStackCapture(unused_trace);
145 E : unused_trace = NULL;
146 :
147 : // If the existing stack capture is previously unreferenced and becoming
148 : // referenced again, then decrement the unreferenced counter.
149 E : if (stack_trace->HasNoRefs()) {
150 i : DCHECK_LT(0u, statistics_.unreferenced);
151 i : --statistics_.unreferenced;
152 : }
153 : }
154 :
155 : // Increment the reference count for this stack trace, and the active number
156 : // of stored frames.
157 E : if (!stack_trace->RefCountIsSaturated()) {
158 E : stack_trace->AddRef();
159 E : if (stack_trace->RefCountIsSaturated())
160 E : ++statistics_.saturated;
161 : }
162 E : ++statistics_.references;
163 E : statistics_.frames_stored += num_frames;
164 :
165 : if (compression_reporting_period_ != 0 &&
166 E : statistics_.requested % compression_reporting_period_ == 0) {
167 i : must_log = true;
168 i : GetStatisticsUnlocked(&statistics);
169 : }
170 E : }
171 :
172 E : DCHECK(stack_trace != NULL);
173 :
174 E : if (must_log)
175 i : LogStatisticsImpl(statistics);
176 :
177 : // Return the stack trace pointer that is now in the cache.
178 E : return stack_trace;
179 E : }
180 :
181 : const StackCapture* StackCaptureCache::SaveStackTrace(
182 E : const StackCapture& stack_capture) {
183 : return SaveStackTrace(stack_capture.stack_id(),
184 : stack_capture.frames(),
185 E : stack_capture.num_frames());
186 E : }
187 :
188 E : void StackCaptureCache::ReleaseStackTrace(const StackCapture* stack_capture) {
189 E : DCHECK(stack_capture != NULL);
190 :
191 E : base::AutoLock auto_lock(lock_);
192 :
193 : // We own the stack so its fine to remove the const. We double check this is
194 : // the case in debug builds with the DCHECK.
195 E : StackCapture* stack = const_cast<StackCapture*>(stack_capture);
196 E : DCHECK(known_stacks_.find(stack) != known_stacks_.end());
197 :
198 E : stack->RemoveRef();
199 E : DCHECK_LT(0u, statistics_.references);
200 E : --statistics_.references;
201 E : statistics_.frames_stored -= stack->num_frames();
202 :
203 E : if (stack->HasNoRefs()) {
204 E : ++statistics_.unreferenced;
205 :
206 : // The frames in this stack capture are no longer alive.
207 E : statistics_.frames_alive -= stack->num_frames();
208 :
209 : // Remove this from the known stacks as we're going to reclaim it and
210 : // overwrite part of its data as we insert into the reclaimed_ list.
211 E : StackSet::iterator it = known_stacks_.find(stack);
212 E : DCHECK(it != known_stacks_.end());
213 E : known_stacks_.erase(it);
214 :
215 : // Link this stack capture into the list of reclaimed stacks.
216 E : AddStackCaptureToReclaimedList(stack);
217 : }
218 E : }
219 :
220 E : void StackCaptureCache::LogStatistics() const {
221 E : Statistics statistics = {};
222 :
223 : {
224 E : base::AutoLock auto_lock(lock_);
225 E : GetStatisticsUnlocked(&statistics);
226 E : }
227 :
228 E : LogStatisticsImpl(statistics);
229 E : }
230 :
231 E : void StackCaptureCache::GetStatisticsUnlocked(Statistics* statistics) const {
232 : #ifndef NDEBUG
233 E : lock_.AssertAcquired();
234 : #endif
235 :
236 E : DCHECK(statistics != NULL);
237 E : *statistics = statistics_;
238 E : statistics->cached = known_stacks_.size();
239 E : }
240 :
241 E : void StackCaptureCache::LogStatisticsImpl(const Statistics& statistics) const {
242 : // The cache has 3 categories of storage.
243 : // alive frames: these are actively participating in storing a stack trace.
244 : // dead frames: these are unreferenced stack traces that are eligible for
245 : // reuse, but are currently dormant.
246 : // overhead: frames in a stack-capture that aren't used, padding at the end
247 : // cache pages, cache page metadata, stack capture metadata, etc.
248 :
249 : // These are all in bytes.
250 E : double cache_size = statistics.size;
251 E : double alive_size = statistics.frames_alive * 4;
252 E : double dead_size = statistics.frames_dead * 4;
253 E : double stored_size = statistics.frames_stored * 4;
254 :
255 : // The |cache_size| is the actual size of storage taken, while |stored_size|
256 : // is the conceptual amount of frame data that is stored in the cache.
257 E : double compression = 100.0 * (1.0 - (cache_size / stored_size));
258 E : double alive = 100.0 * alive_size / cache_size;
259 E : double dead = 100.0 * dead_size / cache_size;
260 E : double overhead = 100.0 - alive - dead;
261 :
262 : logger_->Write(base::StringPrintf(
263 : "PID=%d; Stack cache size=%.2f MB; Compression=%.2f%%; "
264 : "Alive=%.2f%%; Dead=%.2f%%; Overhead=%.2f%%; Saturated=%d; Entries=%d",
265 : ::GetCurrentProcessId(),
266 : cache_size / 1024.0 / 1024.0,
267 : compression,
268 : alive,
269 : dead,
270 : overhead,
271 : statistics.saturated,
272 E : statistics.cached));
273 E : }
274 :
275 :
276 E : StackCapture* StackCaptureCache::GetStackCapture(size_t num_frames) {
277 : #ifndef NDEBUG
278 E : lock_.AssertAcquired();
279 : #endif
280 : // First look to the reclaimed stacks and try to use one of those. We'll use
281 : // the first one that's big enough.
282 E : for (size_t n = num_frames; n <= max_num_frames_; ++n) {
283 E : if (reclaimed_[n] != NULL) {
284 E : StackCapture* stack_capture = reclaimed_[n];
285 E : StackCapture** link = GetFirstFrameAsLink(stack_capture);
286 E : reclaimed_[n] = *link;
287 :
288 : // These frames are no longer dead, but in limbo. If the stack capture
289 : // is used they'll be added to frames_alive and frames_stored.
290 E : statistics_.frames_dead -= stack_capture->max_num_frames();
291 :
292 E : return stack_capture;
293 : }
294 E : }
295 :
296 : // We didn't find a reusable stack capture. Go to the cache page.
297 E : StackCapture* stack_capture = current_page_->GetNextStackCapture(num_frames);
298 :
299 : // If the allocation failed we don't have enough room on the current page.
300 E : if (stack_capture == NULL) {
301 : // Use the remaining bytes to create one more maximally sized stack capture.
302 : // We immediately stuff this in to the reclaimed_ structure for later use.
303 i : size_t bytes_left = current_page_->bytes_left();
304 i : size_t max_num_frames = StackCapture::GetMaxNumFrames(bytes_left);
305 i : if (max_num_frames > 0) {
306 i : DCHECK_LT(max_num_frames, num_frames);
307 i : DCHECK_LE(StackCapture::GetSize(max_num_frames), bytes_left);
308 i : stack_capture = current_page_->GetNextStackCapture(max_num_frames);
309 i : DCHECK(stack_capture != NULL);
310 :
311 : // The stack capture needs to be valid for us to be able to dereference
312 : // its frames. This is needed for splicing it into our reclaimed list.
313 : // We populate it with a single garbage stack frame.
314 : stack_capture->InitFromBuffer(
315 i : 0, reinterpret_cast<void**>(&stack_capture), 1);
316 :
317 : // We're creating an unreferenced stack capture.
318 i : ++statistics_.unreferenced;
319 i : AddStackCaptureToReclaimedList(stack_capture);
320 : }
321 :
322 : // Allocate a new page (that links to the current page) and use it to
323 : // allocate a new stack capture.
324 i : current_page_ = new CachePage(current_page_);
325 i : CHECK(current_page_ != NULL);
326 i : statistics_.size += sizeof(CachePage);
327 i : stack_capture = current_page_->GetNextStackCapture(num_frames);
328 : }
329 E : DCHECK(stack_capture != NULL);
330 E : return stack_capture;
331 E : }
332 :
333 E : void StackCaptureCache::ReturnStackCapture(StackCapture* stack_capture) {
334 : #ifndef NDEBUG
335 E : lock_.AssertAcquired();
336 : #endif
337 E : DCHECK(stack_capture != NULL);
338 :
339 : // First try to return it to the active cache page.
340 E : if (current_page_->ReturnStackCapture(stack_capture))
341 E : return;
342 :
343 : // If this fails we want to reclaim it.
344 E : AddStackCaptureToReclaimedList(stack_capture);
345 E : }
346 :
347 : void StackCaptureCache::AddStackCaptureToReclaimedList(
348 E : StackCapture* stack_capture) {
349 : #ifndef NDEBUG
350 E : lock_.AssertAcquired();
351 : #endif
352 E : DCHECK(stack_capture != NULL);
353 :
354 E : StackCapture** link = GetFirstFrameAsLink(stack_capture);
355 E : size_t num_frames = stack_capture->max_num_frames();
356 E : *link = reclaimed_[num_frames];
357 E : reclaimed_[num_frames] = stack_capture;
358 E : statistics_.frames_dead += stack_capture->max_num_frames();
359 E : }
360 :
361 : } // namespace asan
362 : } // namespace agent
|