lsan_common.cc revision 969b529914f5bc17e4810076dccbaadf563d584c 
1//=-- lsan_common.cc ------------------------------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file is a part of LeakSanitizer.
11// Implementation of common leak checking functionality.
12//
13//===----------------------------------------------------------------------===//
14
15#include "lsan_common.h"
16
17#include "sanitizer_common/sanitizer_common.h"
18#include "sanitizer_common/sanitizer_flags.h"
19#include "sanitizer_common/sanitizer_stackdepot.h"
20#include "sanitizer_common/sanitizer_stacktrace.h"
21#include "sanitizer_common/sanitizer_stoptheworld.h"
22
23#if CAN_SANITIZE_LEAKS
24namespace __lsan {
25
26Flags lsan_flags;
27
28static void InitializeFlags() {
29  Flags *f = flags();
30  // Default values.
31  f->sources = kSourceAllAligned;
32  f->report_blocks = false;
33  f->resolution = 0;
34  f->max_leaks = 0;
35  f->exitcode = 23;
36  f->log_pointers = false;
37  f->log_threads = false;
38
39  const char *options = GetEnv("LSAN_OPTIONS");
40  if (options) {
41    bool aligned = true;
42    ParseFlag(options, &aligned, "aligned");
43    if (!aligned) f->sources |= kSourceUnaligned;
44    ParseFlag(options, &f->report_blocks, "report_blocks");
45    ParseFlag(options, &f->resolution, "resolution");
46    CHECK_GE(&f->resolution, 0);
47    ParseFlag(options, &f->max_leaks, "max_leaks");
48    CHECK_GE(&f->max_leaks, 0);
49    ParseFlag(options, &f->log_pointers, "log_pointers");
50    ParseFlag(options, &f->log_threads, "log_threads");
51    ParseFlag(options, &f->exitcode, "exitcode");
52  }
53}
54
55void InitCommonLsan() {
56  InitializeFlags();
57  InitializePlatformSpecificModules();
58}
59
60static inline bool CanBeAHeapPointer(uptr p) {
61  // Since our heap is located in mmap-ed memory, we can assume a sensible lower
62  // boundary on heap addresses.
63  const uptr kMinAddress = 4 * 4096;
64  if (p < kMinAddress) return false;
65#ifdef __x86_64__
66  // Accept only canonical form user-space addresses.
67  return ((p >> 47) == 0);
68#else
69  return true;
70#endif
71}
72
73// Scan the memory range, looking for byte patterns that point into allocator
74// chunks. Mark those chunks with tag and add them to the frontier.
75// There are two usage modes for this function: finding non-leaked chunks
76// (tag = kReachable) and finding indirectly leaked chunks
77// (tag = kIndirectlyLeaked). In the second case, there's no flood fill,
78// so frontier = 0.
79void ScanRangeForPointers(uptr begin, uptr end, InternalVector<uptr> *frontier,
80                          const char *region_type, ChunkTag tag) {
81  const uptr alignment = flags()->pointer_alignment();
82  if (flags()->log_pointers)
83    Report("Scanning %s range %p-%p.\n", region_type, begin, end);
84  uptr pp = begin;
85  if (pp % alignment)
86    pp = pp + alignment - pp % alignment;
87  for (; pp + sizeof(uptr) <= end; pp += alignment) {
88    void *p = *reinterpret_cast<void**>(pp);
89    if (!CanBeAHeapPointer(reinterpret_cast<uptr>(p))) continue;
90    // FIXME: PointsIntoChunk is SLOW because GetBlockBegin() in
91    // LargeMmapAllocator involves a lock and a linear search.
92    void *chunk = PointsIntoChunk(p);
93    if (!chunk) continue;
94    LsanMetadata m(chunk);
95    if (m.tag() == kReachable) continue;
96    m.set_tag(tag);
97    if (flags()->log_pointers)
98      Report("%p: found %p pointing into chunk %p-%p of size %llu.\n", pp, p,
99             chunk, reinterpret_cast<uptr>(chunk) + m.requested_size(),
100             m.requested_size());
101    if (frontier)
102      frontier->push_back(reinterpret_cast<uptr>(chunk));
103  }
104}
105
106// Scan thread data (stacks and TLS) for heap pointers.
107static void ProcessThreads(SuspendedThreadsList const &suspended_threads,
108                           InternalVector<uptr> *frontier) {
109  InternalScopedBuffer<uptr> registers(SuspendedThreadsList::RegisterCount());
110  uptr registers_begin = reinterpret_cast<uptr>(registers.data());
111  uptr registers_end = registers_begin + registers.size();
112  for (uptr i = 0; i < suspended_threads.thread_count(); i++) {
113    uptr os_id = static_cast<uptr>(suspended_threads.GetThreadID(i));
114    if (flags()->log_threads) Report("Processing thread %d.\n", os_id);
115    uptr stack_begin, stack_end, tls_begin, tls_end, cache_begin, cache_end;
116    bool thread_found = GetThreadRangesLocked(os_id, &stack_begin, &stack_end,
117                                              &tls_begin, &tls_end,
118                                              &cache_begin, &cache_end);
119    if (!thread_found) {
120      // If a thread can't be found in the thread registry, it's probably in the
121      // process of destruction. Log this event and move on.
122      if (flags()->log_threads)
123        Report("Thread %d not found in registry.\n", os_id);
124      continue;
125    }
126    uptr sp;
127    bool have_registers =
128        (suspended_threads.GetRegistersAndSP(i, registers.data(), &sp) == 0);
129    if (!have_registers) {
130      Report("Unable to get registers from thread %d.\n");
131      // If unable to get SP, consider the entire stack to be reachable.
132      sp = stack_begin;
133    }
134
135    if (flags()->use_registers() && have_registers)
136      ScanRangeForPointers(registers_begin, registers_end, frontier,
137                           "REGISTERS", kReachable);
138
139    if (flags()->use_stacks()) {
140      if (flags()->log_threads)
141        Report("Stack at %p-%p, SP = %p.\n", stack_begin, stack_end, sp);
142      if (sp < stack_begin || sp >= stack_end) {
143        // SP is outside the recorded stack range (e.g. the thread is running a
144        // signal handler on alternate stack). Again, consider the entire stack
145        // range to be reachable.
146        if (flags()->log_threads)
147          Report("WARNING: stack_pointer not in stack_range.\n");
148      } else {
149        // Shrink the stack range to ignore out-of-scope values.
150        stack_begin = sp;
151      }
152      ScanRangeForPointers(stack_begin, stack_end, frontier, "STACK",
153                           kReachable);
154    }
155
156    if (flags()->use_tls()) {
157      if (flags()->log_threads) Report("TLS at %p-%p.\n", tls_begin, tls_end);
158      // Because LSan should not be loaded with dlopen(), we can assume
159      // that allocator cache will be part of static TLS image.
160      CHECK_LE(tls_begin, cache_begin);
161      CHECK_GE(tls_end, cache_end);
162      if (tls_begin < cache_begin)
163        ScanRangeForPointers(tls_begin, cache_begin, frontier, "TLS",
164                             kReachable);
165      if (tls_end > cache_end)
166        ScanRangeForPointers(cache_end, tls_end, frontier, "TLS", kReachable);
167    }
168  }
169}
170
171static void FloodFillReachable(InternalVector<uptr> *frontier) {
172  while (frontier->size()) {
173    uptr next_chunk = frontier->back();
174    frontier->pop_back();
175    LsanMetadata m(reinterpret_cast<void *>(next_chunk));
176    ScanRangeForPointers(next_chunk, next_chunk + m.requested_size(), frontier,
177                         "HEAP", kReachable);
178  }
179}
180
181// Mark leaked chunks which are reachable from other leaked chunks.
182void MarkIndirectlyLeakedCb::operator()(void *p) const {
183  p = GetUserBegin(p);
184  LsanMetadata m(p);
185  if (m.allocated() && m.tag() != kReachable) {
186    ScanRangeForPointers(reinterpret_cast<uptr>(p),
187                         reinterpret_cast<uptr>(p) + m.requested_size(),
188                         /* frontier */ 0, "HEAP", kIndirectlyLeaked);
189  }
190}
191
192// Set the appropriate tag on each chunk.
193static void ClassifyAllChunks(SuspendedThreadsList const &suspended_threads) {
194  // Holds the flood fill frontier.
195  InternalVector<uptr> frontier(GetPageSizeCached());
196
197  if (flags()->use_globals())
198    ProcessGlobalRegions(&frontier);
199  ProcessThreads(suspended_threads, &frontier);
200  FloodFillReachable(&frontier);
201  ProcessPlatformSpecificAllocations(&frontier);
202  FloodFillReachable(&frontier);
203
204  // Now all reachable chunks are marked. Iterate over leaked chunks and mark
205  // those that are reachable from other leaked chunks.
206  if (flags()->log_pointers)
207    Report("Now scanning leaked blocks for pointers.\n");
208  ForEachChunk(MarkIndirectlyLeakedCb());
209}
210
211void ClearTagCb::operator()(void *p) const {
212  p = GetUserBegin(p);
213  LsanMetadata m(p);
214  m.set_tag(kDirectlyLeaked);
215}
216
217static void PrintStackTraceById(u32 stack_trace_id) {
218  CHECK(stack_trace_id);
219  uptr size = 0;
220  const uptr *trace = StackDepotGet(stack_trace_id, &size);
221  StackTrace::PrintStack(trace, size, common_flags()->symbolize,
222                         common_flags()->strip_path_prefix, 0);
223}
224
225static void LockAndSuspendThreads(StopTheWorldCallback callback, void *arg) {
226  LockThreadRegistry();
227  LockAllocator();
228  StopTheWorld(callback, arg);
229  // Allocator must be unlocked by the callback.
230  UnlockThreadRegistry();
231}
232
233///// Normal leak checking. /////
234
235void CollectLeaksCb::operator()(void *p) const {
236  p = GetUserBegin(p);
237  LsanMetadata m(p);
238  if (!m.allocated()) return;
239  if (m.tag() != kReachable) {
240    uptr resolution = flags()->resolution;
241    if (resolution > 0) {
242      uptr size = 0;
243      const uptr *trace = StackDepotGet(m.stack_trace_id(), &size);
244      size = Min(size, resolution);
245      leak_report_->Add(StackDepotPut(trace, size), m.requested_size(),
246                        m.tag());
247    } else {
248      leak_report_->Add(m.stack_trace_id(), m.requested_size(), m.tag());
249    }
250  }
251}
252
253static void CollectLeaks(LeakReport *leak_report) {
254  ForEachChunk(CollectLeaksCb(leak_report));
255}
256
257void PrintLeakedCb::operator()(void *p) const {
258  p = GetUserBegin(p);
259  LsanMetadata m(p);
260  if (!m.allocated()) return;
261  if (m.tag() != kReachable) {
262    CHECK(m.tag() == kDirectlyLeaked || m.tag() == kIndirectlyLeaked);
263    Printf("%s leaked %llu byte block at %p\n",
264           m.tag() == kDirectlyLeaked ? "Directly" : "Indirectly",
265           m.requested_size(), p);
266  }
267}
268
269static void PrintLeaked() {
270  Printf("\nReporting individual blocks:\n");
271  ForEachChunk(PrintLeakedCb());
272}
273
274enum LeakCheckResult {
275  kFatalError,
276  kLeaksFound,
277  kNoLeaks
278};
279
280static void DoLeakCheckCallback(const SuspendedThreadsList &suspended_threads,
281                                void *arg) {
282  LeakCheckResult *result = reinterpret_cast<LeakCheckResult *>(arg);
283  CHECK_EQ(*result, kFatalError);
284  // Allocator must not be locked when we call GetRegionBegin().
285  UnlockAllocator();
286  ClassifyAllChunks(suspended_threads);
287  LeakReport leak_report;
288  CollectLeaks(&leak_report);
289  if (leak_report.IsEmpty()) {
290    *result = kNoLeaks;
291    return;
292  }
293  leak_report.PrintLargest(flags()->max_leaks);
294  if (flags()->report_blocks)
295    PrintLeaked();
296  ForEachChunk(ClearTagCb());
297  *result = kLeaksFound;
298}
299
300void DoLeakCheck() {
301  LeakCheckResult result = kFatalError;
302  LockAndSuspendThreads(DoLeakCheckCallback, &result);
303  if (result == kFatalError) {
304    Report("LeakSanitizer has encountered a fatal error.\n");
305    Die();
306  } else if (result == kLeaksFound) {
307    if (flags()->exitcode)
308      internal__exit(flags()->exitcode);
309  }
310}
311
312///// Reporting of leaked blocks' addresses (for testing). /////
313
314void ReportLeakedCb::operator()(void *p) const {
315  p = GetUserBegin(p);
316  LsanMetadata m(p);
317  if (m.allocated() && m.tag() != kReachable)
318    leaked_->push_back(p);
319}
320
321struct ReportLeakedParam {
322  InternalVector<void *> *leaked;
323  uptr sources;
324  bool success;
325};
326
327static void ReportLeakedCallback(const SuspendedThreadsList &suspended_threads,
328                                 void *arg) {
329  // Allocator must not be locked when we call GetRegionBegin().
330  UnlockAllocator();
331  ReportLeakedParam *param = reinterpret_cast<ReportLeakedParam *>(arg);
332  flags()->sources = param->sources;
333  ClassifyAllChunks(suspended_threads);
334  ForEachChunk(ReportLeakedCb(param->leaked));
335  ForEachChunk(ClearTagCb());
336  param->success = true;
337}
338
339void ReportLeaked(InternalVector<void *> *leaked, uptr sources) {
340  CHECK_EQ(0, leaked->size());
341  ReportLeakedParam param;
342  param.leaked = leaked;
343  param.success = false;
344  param.sources = sources;
345  LockAndSuspendThreads(ReportLeakedCallback, &param);
346  CHECK(param.success);
347}
348
349///// LeakReport implementation. /////
350
351// A hard limit on the number of distinct leaks, to avoid quadratic complexity
352// in LeakReport::Add(). We don't expect to ever see this many leaks in
353// real-world applications.
354// FIXME: Get rid of this limit by changing the implementation of LeakReport to
355// use a hash table.
356const uptr kMaxLeaksConsidered = 1000;
357
358void LeakReport::Add(u32 stack_trace_id, uptr leaked_size, ChunkTag tag) {
359  CHECK(tag == kDirectlyLeaked || tag == kIndirectlyLeaked);
360  bool is_directly_leaked = (tag == kDirectlyLeaked);
361  for (uptr i = 0; i < leaks_.size(); i++)
362    if (leaks_[i].stack_trace_id == stack_trace_id &&
363        leaks_[i].is_directly_leaked == is_directly_leaked) {
364      leaks_[i].hit_count++;
365      leaks_[i].total_size += leaked_size;
366      return;
367    }
368  if (leaks_.size() == kMaxLeaksConsidered) return;
369  Leak leak = { /* hit_count */ 1, leaked_size, stack_trace_id,
370                is_directly_leaked };
371  leaks_.push_back(leak);
372}
373
374static bool IsLarger(const Leak &leak1, const Leak &leak2) {
375  return leak1.total_size > leak2.total_size;
376}
377
378void LeakReport::PrintLargest(uptr max_leaks) {
379  CHECK(leaks_.size() <= kMaxLeaksConsidered);
380  Printf("\n");
381  if (leaks_.size() == kMaxLeaksConsidered)
382    Printf("Too many leaks! Only the first %llu leaks encountered will be "
383           "reported.\n",
384           kMaxLeaksConsidered);
385  if (max_leaks > 0 && max_leaks < leaks_.size())
386    Printf("The %llu largest leak%s:\n", max_leaks, max_leaks > 1 ? "s" : "");
387  InternalSort(&leaks_, leaks_.size(), IsLarger);
388  max_leaks = max_leaks > 0 ? Min(max_leaks, leaks_.size()) : leaks_.size();
389  for (uptr i = 0; i < max_leaks; i++) {
390    Printf("\n%s leak of %llu bytes in %llu objects allocated from:\n",
391           leaks_[i].is_directly_leaked ? "Direct" : "Indirect",
392           leaks_[i].total_size, leaks_[i].hit_count);
393    PrintStackTraceById(leaks_[i].stack_trace_id);
394  }
395  if (max_leaks < leaks_.size()) {
396    uptr remaining = leaks_.size() - max_leaks;
397    Printf("\nOmitting %llu more leak%s.\n", remaining,
398           remaining > 1 ? "s" : "");
399  }
400}
401
402}  // namespace __lsan
403#endif  // CAN_SANITIZE_LEAKS
404