blob: e7c0beb566bcdf7593c457c36836e14679fbac39 [file] [log] [blame]
Colin Cross7add50d2016-01-14 15:35:40 -08001/*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <inttypes.h>
18
19#include <functional>
20#include <iomanip>
21#include <mutex>
22#include <string>
23#include <sstream>
Colin Cross7a22e812016-03-04 16:36:12 -080024#include <unordered_map>
Colin Cross7add50d2016-01-14 15:35:40 -080025
26#include <backtrace.h>
27#include <android-base/macros.h>
28
29#include "Allocator.h"
30#include "HeapWalker.h"
Colin Cross7a22e812016-03-04 16:36:12 -080031#include "Leak.h"
Colin Cross8e8f34c2016-03-02 17:53:39 -080032#include "LeakFolding.h"
Colin Cross7add50d2016-01-14 15:35:40 -080033#include "LeakPipe.h"
34#include "ProcessMappings.h"
35#include "PtracerThread.h"
36#include "ScopedDisableMalloc.h"
37#include "Semaphore.h"
38#include "ThreadCapture.h"
39
40#include "memunreachable/memunreachable.h"
41#include "bionic.h"
42#include "log.h"
43
44const size_t Leak::contents_length;
45
46using namespace std::chrono_literals;
47
48class MemUnreachable {
49 public:
50 MemUnreachable(pid_t pid, Allocator<void> allocator) : pid_(pid), allocator_(allocator),
51 heap_walker_(allocator_) {}
52 bool CollectAllocations(const allocator::vector<ThreadInfo>& threads,
53 const allocator::vector<Mapping>& mappings);
54 bool GetUnreachableMemory(allocator::vector<Leak>& leaks, size_t limit,
55 size_t* num_leaks, size_t* leak_bytes);
56 size_t Allocations() { return heap_walker_.Allocations(); }
57 size_t AllocationBytes() { return heap_walker_.AllocationBytes(); }
58 private:
59 bool ClassifyMappings(const allocator::vector<Mapping>& mappings,
60 allocator::vector<Mapping>& heap_mappings,
61 allocator::vector<Mapping>& anon_mappings,
62 allocator::vector<Mapping>& globals_mappings,
63 allocator::vector<Mapping>& stack_mappings);
64 DISALLOW_COPY_AND_ASSIGN(MemUnreachable);
65 pid_t pid_;
66 Allocator<void> allocator_;
67 HeapWalker heap_walker_;
68};
69
70static void HeapIterate(const Mapping& heap_mapping,
71 const std::function<void(uintptr_t, size_t)>& func) {
72 malloc_iterate(heap_mapping.begin, heap_mapping.end - heap_mapping.begin,
73 [](uintptr_t base, size_t size, void* arg) {
74 auto f = reinterpret_cast<const std::function<void(uintptr_t, size_t)>*>(arg);
75 (*f)(base, size);
76 }, const_cast<void*>(reinterpret_cast<const void*>(&func)));
77}
78
79bool MemUnreachable::CollectAllocations(const allocator::vector<ThreadInfo>& threads,
80 const allocator::vector<Mapping>& mappings) {
Christopher Ferris47dea712017-05-03 17:34:29 -070081 MEM_ALOGI("searching process %d for allocations", pid_);
Colin Cross7add50d2016-01-14 15:35:40 -080082 allocator::vector<Mapping> heap_mappings{mappings};
83 allocator::vector<Mapping> anon_mappings{mappings};
84 allocator::vector<Mapping> globals_mappings{mappings};
85 allocator::vector<Mapping> stack_mappings{mappings};
Christopher Ferris47dea712017-05-03 17:34:29 -070086 if (!ClassifyMappings(mappings, heap_mappings, anon_mappings, globals_mappings, stack_mappings)) {
Colin Cross7add50d2016-01-14 15:35:40 -080087 return false;
88 }
89
90 for (auto it = heap_mappings.begin(); it != heap_mappings.end(); it++) {
Christopher Ferris47dea712017-05-03 17:34:29 -070091 MEM_ALOGV("Heap mapping %" PRIxPTR "-%" PRIxPTR " %s", it->begin, it->end, it->name);
92 HeapIterate(*it,
93 [&](uintptr_t base, size_t size) { heap_walker_.Allocation(base, base + size); });
Colin Cross7add50d2016-01-14 15:35:40 -080094 }
95
96 for (auto it = anon_mappings.begin(); it != anon_mappings.end(); it++) {
Christopher Ferris47dea712017-05-03 17:34:29 -070097 MEM_ALOGV("Anon mapping %" PRIxPTR "-%" PRIxPTR " %s", it->begin, it->end, it->name);
Colin Cross7add50d2016-01-14 15:35:40 -080098 heap_walker_.Allocation(it->begin, it->end);
99 }
100
101 for (auto it = globals_mappings.begin(); it != globals_mappings.end(); it++) {
Christopher Ferris47dea712017-05-03 17:34:29 -0700102 MEM_ALOGV("Globals mapping %" PRIxPTR "-%" PRIxPTR " %s", it->begin, it->end, it->name);
Colin Cross7add50d2016-01-14 15:35:40 -0800103 heap_walker_.Root(it->begin, it->end);
104 }
105
106 for (auto thread_it = threads.begin(); thread_it != threads.end(); thread_it++) {
107 for (auto it = stack_mappings.begin(); it != stack_mappings.end(); it++) {
108 if (thread_it->stack.first >= it->begin && thread_it->stack.first <= it->end) {
Christopher Ferris47dea712017-05-03 17:34:29 -0700109 MEM_ALOGV("Stack %" PRIxPTR "-%" PRIxPTR " %s", thread_it->stack.first, it->end, it->name);
Colin Cross7add50d2016-01-14 15:35:40 -0800110 heap_walker_.Root(thread_it->stack.first, it->end);
111 }
112 }
113 heap_walker_.Root(thread_it->regs);
114 }
115
Christopher Ferris47dea712017-05-03 17:34:29 -0700116 MEM_ALOGI("searching done");
Colin Cross7add50d2016-01-14 15:35:40 -0800117
118 return true;
119}
120
Colin Cross7a22e812016-03-04 16:36:12 -0800121bool MemUnreachable::GetUnreachableMemory(allocator::vector<Leak>& leaks,
122 size_t limit, size_t* num_leaks, size_t* leak_bytes) {
Christopher Ferris47dea712017-05-03 17:34:29 -0700123 MEM_ALOGI("sweeping process %d for unreachable memory", pid_);
Colin Cross7add50d2016-01-14 15:35:40 -0800124 leaks.clear();
125
Colin Cross8e8f34c2016-03-02 17:53:39 -0800126 if (!heap_walker_.DetectLeaks()) {
127 return false;
128 }
129
Colin Cross7a22e812016-03-04 16:36:12 -0800130
131 allocator::vector<Range> leaked1{allocator_};
132 heap_walker_.Leaked(leaked1, 0, num_leaks, leak_bytes);
133
Christopher Ferris47dea712017-05-03 17:34:29 -0700134 MEM_ALOGI("sweeping done");
Colin Cross7a22e812016-03-04 16:36:12 -0800135
Christopher Ferris47dea712017-05-03 17:34:29 -0700136 MEM_ALOGI("folding related leaks");
Colin Cross7a22e812016-03-04 16:36:12 -0800137
Colin Cross8e8f34c2016-03-02 17:53:39 -0800138 LeakFolding folding(allocator_, heap_walker_);
139 if (!folding.FoldLeaks()) {
140 return false;
141 }
142
143 allocator::vector<LeakFolding::Leak> leaked{allocator_};
144
Colin Cross7a22e812016-03-04 16:36:12 -0800145 if (!folding.Leaked(leaked, num_leaks, leak_bytes)) {
Colin Cross7add50d2016-01-14 15:35:40 -0800146 return false;
147 }
148
Colin Cross7a22e812016-03-04 16:36:12 -0800149 allocator::unordered_map<Leak::Backtrace, Leak*> backtrace_map{allocator_};
150
151 // Prevent reallocations of backing memory so we can store pointers into it
152 // in backtrace_map.
153 leaks.reserve(leaked.size());
154
155 for (auto& it: leaked) {
156 leaks.emplace_back();
157 Leak* leak = &leaks.back();
158
159 ssize_t num_backtrace_frames = malloc_backtrace(reinterpret_cast<void*>(it.range.begin),
160 leak->backtrace.frames, leak->backtrace.max_frames);
Colin Cross7add50d2016-01-14 15:35:40 -0800161 if (num_backtrace_frames > 0) {
Colin Cross7a22e812016-03-04 16:36:12 -0800162 leak->backtrace.num_frames = num_backtrace_frames;
163
164 auto inserted = backtrace_map.emplace(leak->backtrace, leak);
165 if (!inserted.second) {
166 // Leak with same backtrace already exists, drop this one and
167 // increment similar counts on the existing one.
168 leaks.pop_back();
169 Leak* similar_leak = inserted.first->second;
170 similar_leak->similar_count++;
171 similar_leak->similar_size += it.range.size();
172 similar_leak->similar_referenced_count += it.referenced_count;
173 similar_leak->similar_referenced_size += it.referenced_size;
174 similar_leak->total_size += it.range.size();
175 similar_leak->total_size += it.referenced_size;
176 continue;
177 }
Colin Cross7add50d2016-01-14 15:35:40 -0800178 }
Colin Cross7a22e812016-03-04 16:36:12 -0800179
180 leak->begin = it.range.begin;
181 leak->size = it.range.size();
182 leak->referenced_count = it.referenced_count;
183 leak->referenced_size = it.referenced_size;
184 leak->total_size = leak->size + leak->referenced_size;
185 memcpy(leak->contents, reinterpret_cast<void*>(it.range.begin),
186 std::min(leak->size, Leak::contents_length));
Colin Cross7add50d2016-01-14 15:35:40 -0800187 }
188
Christopher Ferris47dea712017-05-03 17:34:29 -0700189 MEM_ALOGI("folding done");
Colin Cross7a22e812016-03-04 16:36:12 -0800190
191 std::sort(leaks.begin(), leaks.end(), [](const Leak& a, const Leak& b) {
192 return a.total_size > b.total_size;
193 });
194
195 if (leaks.size() > limit) {
196 leaks.resize(limit);
197 }
Colin Cross7add50d2016-01-14 15:35:40 -0800198
199 return true;
200}
201
202static bool has_prefix(const allocator::string& s, const char* prefix) {
203 int ret = s.compare(0, strlen(prefix), prefix);
204 return ret == 0;
205}
206
207bool MemUnreachable::ClassifyMappings(const allocator::vector<Mapping>& mappings,
208 allocator::vector<Mapping>& heap_mappings,
209 allocator::vector<Mapping>& anon_mappings,
210 allocator::vector<Mapping>& globals_mappings,
211 allocator::vector<Mapping>& stack_mappings)
212{
213 heap_mappings.clear();
214 anon_mappings.clear();
215 globals_mappings.clear();
216 stack_mappings.clear();
217
218 allocator::string current_lib{allocator_};
219
220 for (auto it = mappings.begin(); it != mappings.end(); it++) {
221 if (it->execute) {
222 current_lib = it->name;
223 continue;
224 }
225
226 if (!it->read) {
227 continue;
228 }
229
230 const allocator::string mapping_name{it->name, allocator_};
231 if (mapping_name == "[anon:.bss]") {
232 // named .bss section
233 globals_mappings.emplace_back(*it);
234 } else if (mapping_name == current_lib) {
235 // .rodata or .data section
236 globals_mappings.emplace_back(*it);
237 } else if (mapping_name == "[anon:libc_malloc]") {
238 // named malloc mapping
239 heap_mappings.emplace_back(*it);
240 } else if (has_prefix(mapping_name, "/dev/ashmem/dalvik")) {
241 // named dalvik heap mapping
242 globals_mappings.emplace_back(*it);
243 } else if (has_prefix(mapping_name, "[stack")) {
244 // named stack mapping
245 stack_mappings.emplace_back(*it);
246 } else if (mapping_name.size() == 0) {
247 globals_mappings.emplace_back(*it);
248 } else if (has_prefix(mapping_name, "[anon:") && mapping_name != "[anon:leak_detector_malloc]") {
249 // TODO(ccross): it would be nice to treat named anonymous mappings as
250 // possible leaks, but naming something in a .bss or .data section makes
251 // it impossible to distinguish them from mmaped and then named mappings.
252 globals_mappings.emplace_back(*it);
253 }
254 }
255
256 return true;
257}
258
Colin Cross7a22e812016-03-04 16:36:12 -0800259template<typename T>
260static inline const char* plural(T val) {
261 return (val == 1) ? "" : "s";
262}
263
Colin Cross7add50d2016-01-14 15:35:40 -0800264bool GetUnreachableMemory(UnreachableMemoryInfo& info, size_t limit) {
265 int parent_pid = getpid();
266 int parent_tid = gettid();
267
268 Heap heap;
269
270 Semaphore continue_parent_sem;
271 LeakPipe pipe;
272
273 PtracerThread thread{[&]() -> int {
274 /////////////////////////////////////////////
275 // Collection thread
276 /////////////////////////////////////////////
Christopher Ferris47dea712017-05-03 17:34:29 -0700277 MEM_ALOGI("collecting thread info for process %d...", parent_pid);
Colin Cross7add50d2016-01-14 15:35:40 -0800278
279 ThreadCapture thread_capture(parent_pid, heap);
280 allocator::vector<ThreadInfo> thread_info(heap);
281 allocator::vector<Mapping> mappings(heap);
282
283 // ptrace all the threads
284 if (!thread_capture.CaptureThreads()) {
Colin Crossde42af02016-01-14 15:35:40 -0800285 continue_parent_sem.Post();
Colin Cross7add50d2016-01-14 15:35:40 -0800286 return 1;
287 }
288
289 // collect register contents and stacks
290 if (!thread_capture.CapturedThreadInfo(thread_info)) {
Colin Crossde42af02016-01-14 15:35:40 -0800291 continue_parent_sem.Post();
Colin Cross7add50d2016-01-14 15:35:40 -0800292 return 1;
293 }
294
295 // snapshot /proc/pid/maps
296 if (!ProcessMappings(parent_pid, mappings)) {
Colin Crossde42af02016-01-14 15:35:40 -0800297 continue_parent_sem.Post();
Colin Cross7add50d2016-01-14 15:35:40 -0800298 return 1;
299 }
300
301 // malloc must be enabled to call fork, at_fork handlers take the same
302 // locks as ScopedDisableMalloc. All threads are paused in ptrace, so
303 // memory state is still consistent. Unfreeze the original thread so it
304 // can drop the malloc locks, it will block until the collection thread
305 // exits.
306 thread_capture.ReleaseThread(parent_tid);
307 continue_parent_sem.Post();
308
309 // fork a process to do the heap walking
310 int ret = fork();
311 if (ret < 0) {
312 return 1;
313 } else if (ret == 0) {
314 /////////////////////////////////////////////
315 // Heap walker process
316 /////////////////////////////////////////////
317 // Examine memory state in the child using the data collected above and
318 // the CoW snapshot of the process memory contents.
319
320 if (!pipe.OpenSender()) {
321 _exit(1);
322 }
323
324 MemUnreachable unreachable{parent_pid, heap};
325
326 if (!unreachable.CollectAllocations(thread_info, mappings)) {
327 _exit(2);
328 }
329 size_t num_allocations = unreachable.Allocations();
330 size_t allocation_bytes = unreachable.AllocationBytes();
331
332 allocator::vector<Leak> leaks{heap};
333
334 size_t num_leaks = 0;
335 size_t leak_bytes = 0;
336 bool ok = unreachable.GetUnreachableMemory(leaks, limit, &num_leaks, &leak_bytes);
337
338 ok = ok && pipe.Sender().Send(num_allocations);
339 ok = ok && pipe.Sender().Send(allocation_bytes);
340 ok = ok && pipe.Sender().Send(num_leaks);
341 ok = ok && pipe.Sender().Send(leak_bytes);
342 ok = ok && pipe.Sender().SendVector(leaks);
343
344 if (!ok) {
345 _exit(3);
346 }
347
348 _exit(0);
349 } else {
350 // Nothing left to do in the collection thread, return immediately,
351 // releasing all the captured threads.
Christopher Ferris47dea712017-05-03 17:34:29 -0700352 MEM_ALOGI("collection thread done");
Colin Cross7add50d2016-01-14 15:35:40 -0800353 return 0;
354 }
355 }};
356
357 /////////////////////////////////////////////
358 // Original thread
359 /////////////////////////////////////////////
360
361 {
362 // Disable malloc to get a consistent view of memory
363 ScopedDisableMalloc disable_malloc;
364
365 // Start the collection thread
366 thread.Start();
367
368 // Wait for the collection thread to signal that it is ready to fork the
369 // heap walker process.
Colin Crossde42af02016-01-14 15:35:40 -0800370 continue_parent_sem.Wait(30s);
Colin Cross7add50d2016-01-14 15:35:40 -0800371
372 // Re-enable malloc so the collection thread can fork.
373 }
374
375 // Wait for the collection thread to exit
376 int ret = thread.Join();
377 if (ret != 0) {
378 return false;
379 }
380
381 // Get a pipe from the heap walker process. Transferring a new pipe fd
382 // ensures no other forked processes can have it open, so when the heap
383 // walker process dies the remote side of the pipe will close.
384 if (!pipe.OpenReceiver()) {
385 return false;
386 }
387
388 bool ok = true;
389 ok = ok && pipe.Receiver().Receive(&info.num_allocations);
390 ok = ok && pipe.Receiver().Receive(&info.allocation_bytes);
391 ok = ok && pipe.Receiver().Receive(&info.num_leaks);
392 ok = ok && pipe.Receiver().Receive(&info.leak_bytes);
393 ok = ok && pipe.Receiver().ReceiveVector(info.leaks);
394 if (!ok) {
395 return false;
396 }
397
Christopher Ferris47dea712017-05-03 17:34:29 -0700398 MEM_ALOGI("unreachable memory detection done");
399 MEM_ALOGE("%zu bytes in %zu allocation%s unreachable out of %zu bytes in %zu allocation%s",
400 info.leak_bytes, info.num_leaks, plural(info.num_leaks), info.allocation_bytes,
401 info.num_allocations, plural(info.num_allocations));
Colin Cross7add50d2016-01-14 15:35:40 -0800402 return true;
403}
404
405std::string Leak::ToString(bool log_contents) const {
406
407 std::ostringstream oss;
408
409 oss << " " << std::dec << size;
Colin Crossde42af02016-01-14 15:35:40 -0800410 oss << " bytes unreachable at ";
Colin Cross7add50d2016-01-14 15:35:40 -0800411 oss << std::hex << begin;
412 oss << std::endl;
Colin Cross7a22e812016-03-04 16:36:12 -0800413 if (referenced_count > 0) {
414 oss << std::dec;
415 oss << " referencing " << referenced_size << " unreachable bytes";
416 oss << " in " << referenced_count << " allocation" << plural(referenced_count);
417 oss << std::endl;
418 }
419 if (similar_count > 0) {
420 oss << std::dec;
421 oss << " and " << similar_size << " similar unreachable bytes";
422 oss << " in " << similar_count << " allocation" << plural(similar_count);
423 oss << std::endl;
424 if (similar_referenced_count > 0) {
425 oss << " referencing " << similar_referenced_size << " unreachable bytes";
426 oss << " in " << similar_referenced_count << " allocation" << plural(similar_referenced_count);
427 oss << std::endl;
428 }
429 }
Colin Cross7add50d2016-01-14 15:35:40 -0800430
431 if (log_contents) {
432 const int bytes_per_line = 16;
433 const size_t bytes = std::min(size, contents_length);
434
435 if (bytes == size) {
436 oss << " contents:" << std::endl;
437 } else {
Colin Cross7a22e812016-03-04 16:36:12 -0800438 oss << " first " << bytes << " bytes of contents:" << std::endl;
Colin Cross7add50d2016-01-14 15:35:40 -0800439 }
440
441 for (size_t i = 0; i < bytes; i += bytes_per_line) {
442 oss << " " << std::hex << begin + i << ": ";
443 size_t j;
444 oss << std::setfill('0');
445 for (j = i; j < bytes && j < i + bytes_per_line; j++) {
446 oss << std::setw(2) << static_cast<int>(contents[j]) << " ";
447 }
448 oss << std::setfill(' ');
449 for (; j < i + bytes_per_line; j++) {
450 oss << " ";
451 }
452 for (j = i; j < bytes && j < i + bytes_per_line; j++) {
453 char c = contents[j];
454 if (c < ' ' || c >= 0x7f) {
455 c = '.';
456 }
457 oss << c;
458 }
459 oss << std::endl;
460 }
461 }
Colin Cross7a22e812016-03-04 16:36:12 -0800462 if (backtrace.num_frames > 0) {
463 oss << backtrace_string(backtrace.frames, backtrace.num_frames);
Colin Cross7add50d2016-01-14 15:35:40 -0800464 }
465
466 return oss.str();
467}
468
Colin Cross11185af2016-03-04 16:37:02 -0800469// Figure out the abi based on defined macros.
470#if defined(__arm__)
471#define ABI_STRING "arm"
472#elif defined(__aarch64__)
473#define ABI_STRING "arm64"
474#elif defined(__mips__) && !defined(__LP64__)
475#define ABI_STRING "mips"
476#elif defined(__mips__) && defined(__LP64__)
477#define ABI_STRING "mips64"
478#elif defined(__i386__)
479#define ABI_STRING "x86"
480#elif defined(__x86_64__)
481#define ABI_STRING "x86_64"
482#else
483#error "Unsupported ABI"
484#endif
485
Colin Cross7add50d2016-01-14 15:35:40 -0800486std::string UnreachableMemoryInfo::ToString(bool log_contents) const {
487 std::ostringstream oss;
488 oss << " " << leak_bytes << " bytes in ";
Colin Cross7a22e812016-03-04 16:36:12 -0800489 oss << num_leaks << " unreachable allocation" << plural(num_leaks);
Colin Cross7add50d2016-01-14 15:35:40 -0800490 oss << std::endl;
Colin Cross11185af2016-03-04 16:37:02 -0800491 oss << " ABI: '" ABI_STRING "'" << std::endl;
492 oss << std::endl;
Colin Cross7add50d2016-01-14 15:35:40 -0800493
494 for (auto it = leaks.begin(); it != leaks.end(); it++) {
495 oss << it->ToString(log_contents);
Colin Cross7a22e812016-03-04 16:36:12 -0800496 oss << std::endl;
Colin Cross7add50d2016-01-14 15:35:40 -0800497 }
498
499 return oss.str();
500}
501
502std::string GetUnreachableMemoryString(bool log_contents, size_t limit) {
503 UnreachableMemoryInfo info;
504 if (!GetUnreachableMemory(info, limit)) {
Colin Crossde42af02016-01-14 15:35:40 -0800505 return "Failed to get unreachable memory\n";
Colin Cross7add50d2016-01-14 15:35:40 -0800506 }
507
508 return info.ToString(log_contents);
509}
510
511bool LogUnreachableMemory(bool log_contents, size_t limit) {
512 UnreachableMemoryInfo info;
513 if (!GetUnreachableMemory(info, limit)) {
514 return false;
515 }
516
517 for (auto it = info.leaks.begin(); it != info.leaks.end(); it++) {
Christopher Ferris47dea712017-05-03 17:34:29 -0700518 MEM_ALOGE("%s", it->ToString(log_contents).c_str());
Colin Cross7add50d2016-01-14 15:35:40 -0800519 }
520 return true;
521}
522
523
524bool NoLeaks() {
525 UnreachableMemoryInfo info;
526 if (!GetUnreachableMemory(info, 0)) {
527 return false;
528 }
529
530 return info.num_leaks == 0;
531}