1 /*
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 <sys/mman.h>
18 #include <unistd.h>
19
20 #include "HeapWalker.h"
21
22 #include <ScopedDisableMalloc.h>
23 #include <gtest/gtest.h>
24 #include "Allocator.h"
25
26 namespace android {
27
UntagAddress(uintptr_t addr)28 static inline uintptr_t UntagAddress(uintptr_t addr) {
29 #if defined(__aarch64__)
30 constexpr uintptr_t mask = (static_cast<uintptr_t>(1) << 56) - 1;
31 addr = addr & mask;
32 #endif
33 return addr;
34 }
35
36 class HeapWalkerTest : public ::testing::Test {
37 public:
HeapWalkerTest()38 HeapWalkerTest() : disable_malloc_(), heap_() {}
39
TearDown()40 void TearDown() {
41 ASSERT_TRUE(heap_.empty());
42 if (!HasFailure()) {
43 ASSERT_FALSE(disable_malloc_.timed_out());
44 }
45 }
46
47 protected:
48 ScopedDisableMallocTimeout disable_malloc_;
49 Heap heap_;
50 };
51
TEST_F(HeapWalkerTest,allocation)52 TEST_F(HeapWalkerTest, allocation) {
53 HeapWalker heap_walker(heap_);
54 ASSERT_TRUE(heap_walker.Allocation(3, 4));
55 ASSERT_TRUE(heap_walker.Allocation(2, 3));
56 ASSERT_TRUE(heap_walker.Allocation(4, 5));
57 ASSERT_TRUE(heap_walker.Allocation(6, 7));
58 ASSERT_TRUE(heap_walker.Allocation(0, 1));
59 }
60
TEST_F(HeapWalkerTest,overlap)61 TEST_F(HeapWalkerTest, overlap) {
62 HeapWalker heap_walker(heap_);
63 ASSERT_TRUE(heap_walker.Allocation(2, 3));
64 ASSERT_TRUE(heap_walker.Allocation(3, 4));
65 ASSERT_FALSE(heap_walker.Allocation(2, 3));
66 ASSERT_FALSE(heap_walker.Allocation(1, 3));
67 ASSERT_FALSE(heap_walker.Allocation(1, 4));
68 ASSERT_FALSE(heap_walker.Allocation(1, 5));
69 ASSERT_FALSE(heap_walker.Allocation(3, 4));
70 ASSERT_FALSE(heap_walker.Allocation(3, 5));
71 ASSERT_TRUE(heap_walker.Allocation(4, 5));
72 ASSERT_TRUE(heap_walker.Allocation(1, 2));
73 }
74
TEST_F(HeapWalkerTest,zero)75 TEST_F(HeapWalkerTest, zero) {
76 HeapWalker heap_walker(heap_);
77 ASSERT_TRUE(heap_walker.Allocation(2, 2));
78 ASSERT_FALSE(heap_walker.Allocation(2, 2));
79 ASSERT_TRUE(heap_walker.Allocation(3, 3));
80 ASSERT_TRUE(heap_walker.Allocation(1, 1));
81 ASSERT_FALSE(heap_walker.Allocation(2, 3));
82 }
83
TEST_F(HeapWalkerTest,mapping)84 TEST_F(HeapWalkerTest, mapping) {
85 HeapWalker heap_walker(heap_);
86 heap_walker.Mapping(2, 3);
87 heap_walker.Mapping(4, 5);
88 ASSERT_TRUE(heap_walker.Allocation(2, 3));
89 ASSERT_TRUE(heap_walker.Allocation(4, 5));
90 // space between mappings is not checked, but could be in the future
91 ASSERT_TRUE(heap_walker.Allocation(3, 4));
92
93 // re-enable malloc, ASSERT_DEATH may allocate
94 disable_malloc_.Enable();
95 ASSERT_DEATH({ heap_walker.Allocation(1, 2); }, "0x1-0x2.*outside.*0x2-0x5");
96 ASSERT_DEATH({ heap_walker.Allocation(1, 3); }, "0x1-0x3.*outside.*0x2-0x5");
97 ASSERT_DEATH({ heap_walker.Allocation(4, 6); }, "0x4-0x6.*outside.*0x2-0x5");
98 ASSERT_DEATH({ heap_walker.Allocation(5, 6); }, "0x5-0x6.*outside.*0x2-0x5");
99 ASSERT_DEATH({ heap_walker.Allocation(1, 6); }, "0x1-0x6.*outside.*0x2-0x5");
100 }
101
102 #define buffer_begin(buffer) reinterpret_cast<uintptr_t>(buffer)
103 #define buffer_end(buffer) (reinterpret_cast<uintptr_t>(buffer) + sizeof(buffer))
104
TEST_F(HeapWalkerTest,leak)105 TEST_F(HeapWalkerTest, leak) {
106 void* buffer1[16]{};
107 char buffer2[16]{};
108 buffer1[0] = &buffer2[0] - sizeof(void*);
109 buffer1[1] = &buffer2[15] + sizeof(void*);
110
111 HeapWalker heap_walker(heap_);
112 heap_walker.Allocation(buffer_begin(buffer2), buffer_end(buffer2));
113
114 ASSERT_EQ(true, heap_walker.DetectLeaks());
115
116 allocator::vector<Range> leaked(heap_);
117 size_t num_leaks = 0;
118 size_t leaked_bytes = 0;
119 ASSERT_EQ(true, heap_walker.Leaked(leaked, 100, &num_leaks, &leaked_bytes));
120
121 EXPECT_EQ(1U, num_leaks);
122 EXPECT_EQ(16U, leaked_bytes);
123 ASSERT_EQ(1U, leaked.size());
124 EXPECT_EQ(UntagAddress(buffer_begin(buffer2)), leaked[0].begin);
125 EXPECT_EQ(UntagAddress(buffer_end(buffer2)), leaked[0].end);
126 }
127
TEST_F(HeapWalkerTest,live)128 TEST_F(HeapWalkerTest, live) {
129 const int from_buffer_entries = 4;
130 const int to_buffer_bytes = 16;
131
132 for (int i = 0; i < from_buffer_entries; i++) {
133 for (int j = 0; j < to_buffer_bytes; j++) {
134 void* buffer1[from_buffer_entries]{};
135 char buffer2[to_buffer_bytes]{};
136 buffer1[i] = &buffer2[j];
137
138 HeapWalker heap_walker(heap_);
139 heap_walker.Allocation(buffer_begin(buffer2), buffer_end(buffer2));
140 heap_walker.Root(buffer_begin(buffer1), buffer_end(buffer1));
141
142 ASSERT_EQ(true, heap_walker.DetectLeaks());
143
144 allocator::vector<Range> leaked(heap_);
145 size_t num_leaks = SIZE_MAX;
146 size_t leaked_bytes = SIZE_MAX;
147 ASSERT_EQ(true, heap_walker.Leaked(leaked, 100, &num_leaks, &leaked_bytes));
148
149 EXPECT_EQ(0U, num_leaks);
150 EXPECT_EQ(0U, leaked_bytes);
151 EXPECT_EQ(0U, leaked.size());
152 }
153 }
154 }
155
TEST_F(HeapWalkerTest,unaligned)156 TEST_F(HeapWalkerTest, unaligned) {
157 const int from_buffer_entries = 4;
158 const int to_buffer_bytes = 16;
159 void* buffer1[from_buffer_entries]{};
160 char buffer2[to_buffer_bytes]{};
161
162 buffer1[1] = &buffer2;
163
164 for (unsigned int i = 0; i < sizeof(uintptr_t); i++) {
165 for (unsigned int j = 0; j < sizeof(uintptr_t); j++) {
166 HeapWalker heap_walker(heap_);
167 heap_walker.Allocation(buffer_begin(buffer2), buffer_end(buffer2));
168 heap_walker.Root(buffer_begin(buffer1) + i, buffer_end(buffer1) - j);
169
170 ASSERT_EQ(true, heap_walker.DetectLeaks());
171
172 allocator::vector<Range> leaked(heap_);
173 size_t num_leaks = SIZE_MAX;
174 size_t leaked_bytes = SIZE_MAX;
175 ASSERT_EQ(true, heap_walker.Leaked(leaked, 100, &num_leaks, &leaked_bytes));
176
177 EXPECT_EQ(0U, num_leaks);
178 EXPECT_EQ(0U, leaked_bytes);
179 EXPECT_EQ(0U, leaked.size());
180 }
181 }
182 }
183
TEST_F(HeapWalkerTest,cycle)184 TEST_F(HeapWalkerTest, cycle) {
185 void* buffer1;
186 void* buffer2;
187
188 buffer1 = &buffer2;
189 buffer2 = &buffer1;
190
191 HeapWalker heap_walker(heap_);
192 heap_walker.Allocation(buffer_begin(buffer1), buffer_end(buffer1));
193 heap_walker.Allocation(buffer_begin(buffer2), buffer_end(buffer2));
194
195 ASSERT_EQ(true, heap_walker.DetectLeaks());
196
197 allocator::vector<Range> leaked(heap_);
198 size_t num_leaks = 0;
199 size_t leaked_bytes = 0;
200 ASSERT_EQ(true, heap_walker.Leaked(leaked, 100, &num_leaks, &leaked_bytes));
201
202 EXPECT_EQ(2U, num_leaks);
203 EXPECT_EQ(2 * sizeof(uintptr_t), leaked_bytes);
204 ASSERT_EQ(2U, leaked.size());
205 }
206
TEST_F(HeapWalkerTest,segv)207 TEST_F(HeapWalkerTest, segv) {
208 const size_t page_size = sysconf(_SC_PAGE_SIZE);
209 void* buffer1 = mmap(NULL, page_size, PROT_NONE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
210 ASSERT_NE(buffer1, nullptr);
211 void* buffer2;
212
213 buffer2 = &buffer1;
214
215 HeapWalker heap_walker(heap_);
216 heap_walker.Allocation(buffer_begin(buffer1), buffer_begin(buffer1) + page_size);
217 heap_walker.Root(buffer_begin(buffer2), buffer_end(buffer2));
218
219 ASSERT_EQ(true, heap_walker.DetectLeaks());
220
221 allocator::vector<Range> leaked(heap_);
222 size_t num_leaks = 0;
223 size_t leaked_bytes = 0;
224 ASSERT_EQ(true, heap_walker.Leaked(leaked, 100, &num_leaks, &leaked_bytes));
225
226 EXPECT_EQ(0U, num_leaks);
227 EXPECT_EQ(0U, leaked_bytes);
228 ASSERT_EQ(0U, leaked.size());
229 }
230
231 } // namespace android
232