summaryrefslogtreecommitdiffstats
path: root/libmemunreachable/HeapWalker.h
blob: b25696fd4c0e56a7ede6e4d95bf326316063d71c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/*
 * Copyright (C) 2016 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef LIBMEMUNREACHABLE_HEAP_WALKER_H_
#define LIBMEMUNREACHABLE_HEAP_WALKER_H_

#include <signal.h>

#include "android-base/macros.h"

#include "Allocator.h"
#include "ScopedSignalHandler.h"
#include "Tarjan.h"

// A range [begin, end)
struct Range {
  uintptr_t begin;
  uintptr_t end;

  size_t size() const { return end - begin; };
  bool operator==(const Range& other) const {
    return this->begin == other.begin && this->end == other.end;
  }
  bool operator!=(const Range& other) const {
    return !(*this == other);
  }
};

// Comparator for Ranges that returns equivalence for overlapping ranges
struct compare_range {
  bool operator()(const Range& a, const Range& b) const {
    return a.end <= b.begin;
  }
};

class HeapWalker {
 public:
  explicit HeapWalker(Allocator<HeapWalker> allocator) : allocator_(allocator),
    allocations_(allocator), allocation_bytes_(0),
	roots_(allocator), root_vals_(allocator),
	segv_handler_(allocator), walking_ptr_(0) {
    valid_allocations_range_.end = 0;
    valid_allocations_range_.begin = ~valid_allocations_range_.end;

    segv_handler_.install(SIGSEGV,
        [=](ScopedSignalHandler& handler, int signal, siginfo_t* siginfo, void* uctx) {
          this->HandleSegFault(handler, signal, siginfo, uctx);
      });
  }

  ~HeapWalker() {}
  bool Allocation(uintptr_t begin, uintptr_t end);
  void Root(uintptr_t begin, uintptr_t end);
  void Root(const allocator::vector<uintptr_t>& vals);

  bool DetectLeaks();

  bool Leaked(allocator::vector<Range>&, size_t limit, size_t* num_leaks,
      size_t* leak_bytes);
  size_t Allocations();
  size_t AllocationBytes();

  template<class F>
  void ForEachPtrInRange(const Range& range, F&& f);

  template<class F>
  void ForEachAllocation(F&& f);

  struct AllocationInfo {
    bool referenced_from_root;
  };

 private:

  void RecurseRoot(const Range& root);
  bool WordContainsAllocationPtr(uintptr_t ptr, Range* range, AllocationInfo** info);
  void HandleSegFault(ScopedSignalHandler&, int, siginfo_t*, void*);

  DISALLOW_COPY_AND_ASSIGN(HeapWalker);
  Allocator<HeapWalker> allocator_;
  using AllocationMap = allocator::map<Range, AllocationInfo, compare_range>;
  AllocationMap allocations_;
  size_t allocation_bytes_;
  Range valid_allocations_range_;

  allocator::vector<Range> roots_;
  allocator::vector<uintptr_t> root_vals_;

  ScopedSignalHandler segv_handler_;
  uintptr_t walking_ptr_;
};

template<class F>
inline void HeapWalker::ForEachPtrInRange(const Range& range, F&& f) {
  uintptr_t begin = (range.begin + (sizeof(uintptr_t) - 1)) & ~(sizeof(uintptr_t) - 1);
  // TODO(ccross): we might need to consider a pointer to the end of a buffer
  // to be inside the buffer, which means the common case of a pointer to the
  // beginning of a buffer may keep two ranges live.
  for (uintptr_t i = begin; i < range.end; i += sizeof(uintptr_t)) {
    Range ref_range;
    AllocationInfo* ref_info;
    if (WordContainsAllocationPtr(i, &ref_range, &ref_info)) {
      f(ref_range, ref_info);
    }
  }
}

template<class F>
inline void HeapWalker::ForEachAllocation(F&& f) {
  for (auto& it : allocations_) {
    const Range& range = it.first;
    HeapWalker::AllocationInfo& allocation = it.second;
    f(range, allocation);
  }
}

#endif