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