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 <gtest/gtest.h>
23 #include <ScopedDisableMalloc.h>
24 #include "Allocator.h"
25 
26 class HeapWalkerTest : public ::testing::Test {
27  public:
HeapWalkerTest()28   HeapWalkerTest() : disable_malloc_(), heap_() {}
29 
TearDown()30   void TearDown() {
31     ASSERT_TRUE(heap_.empty());
32     if (!HasFailure()) {
33       ASSERT_FALSE(disable_malloc_.timed_out());
34     }
35   }
36 
37  protected:
38   ScopedDisableMallocTimeout disable_malloc_;
39   Heap heap_;
40 };
41 
TEST_F(HeapWalkerTest,allocation)42 TEST_F(HeapWalkerTest, allocation) {
43   HeapWalker heap_walker(heap_);
44   ASSERT_TRUE(heap_walker.Allocation(3, 4));
45   ASSERT_TRUE(heap_walker.Allocation(2, 3));
46   ASSERT_TRUE(heap_walker.Allocation(4, 5));
47   ASSERT_TRUE(heap_walker.Allocation(6, 7));
48   ASSERT_TRUE(heap_walker.Allocation(0, 1));
49 }
50 
TEST_F(HeapWalkerTest,overlap)51 TEST_F(HeapWalkerTest, overlap) {
52   HeapWalker heap_walker(heap_);
53   ASSERT_TRUE(heap_walker.Allocation(2, 3));
54   ASSERT_TRUE(heap_walker.Allocation(3, 4));
55   ASSERT_FALSE(heap_walker.Allocation(2, 3));
56   ASSERT_FALSE(heap_walker.Allocation(1, 3));
57   ASSERT_FALSE(heap_walker.Allocation(1, 4));
58   ASSERT_FALSE(heap_walker.Allocation(1, 5));
59   ASSERT_FALSE(heap_walker.Allocation(3, 4));
60   ASSERT_FALSE(heap_walker.Allocation(3, 5));
61   ASSERT_TRUE(heap_walker.Allocation(4, 5));
62   ASSERT_TRUE(heap_walker.Allocation(1, 2));
63 }
64 
TEST_F(HeapWalkerTest,zero)65 TEST_F(HeapWalkerTest, zero) {
66   HeapWalker heap_walker(heap_);
67   ASSERT_TRUE(heap_walker.Allocation(2, 2));
68   ASSERT_FALSE(heap_walker.Allocation(2, 2));
69   ASSERT_TRUE(heap_walker.Allocation(3, 3));
70   ASSERT_TRUE(heap_walker.Allocation(1, 1));
71   ASSERT_FALSE(heap_walker.Allocation(2, 3));
72 }
73 
74 #define buffer_begin(buffer) reinterpret_cast<uintptr_t>(buffer)
75 #define buffer_end(buffer) (reinterpret_cast<uintptr_t>(buffer) + sizeof(buffer))
76 
TEST_F(HeapWalkerTest,leak)77 TEST_F(HeapWalkerTest, leak) {
78   void* buffer1[16]{};
79   char buffer2[16]{};
80   buffer1[0] = &buffer2[0] - sizeof(void*);
81   buffer1[1] = &buffer2[15] + sizeof(void*);
82 
83   HeapWalker heap_walker(heap_);
84   heap_walker.Allocation(buffer_begin(buffer2), buffer_end(buffer2));
85 
86   ASSERT_EQ(true, heap_walker.DetectLeaks());
87 
88   allocator::vector<Range> leaked(heap_);
89   size_t num_leaks = 0;
90   size_t leaked_bytes = 0;
91   ASSERT_EQ(true, heap_walker.Leaked(leaked, 100, &num_leaks, &leaked_bytes));
92 
93   EXPECT_EQ(1U, num_leaks);
94   EXPECT_EQ(16U, leaked_bytes);
95   ASSERT_EQ(1U, leaked.size());
96   EXPECT_EQ(buffer_begin(buffer2), leaked[0].begin);
97   EXPECT_EQ(buffer_end(buffer2), leaked[0].end);
98 }
99 
TEST_F(HeapWalkerTest,live)100 TEST_F(HeapWalkerTest, live) {
101   const int from_buffer_entries = 4;
102   const int to_buffer_bytes = 16;
103 
104   for (int i = 0; i < from_buffer_entries; i++) {
105     for (int j = 0; j < to_buffer_bytes; j++) {
106       void* buffer1[from_buffer_entries]{};
107       char buffer2[to_buffer_bytes]{};
108       buffer1[i] = &buffer2[j];
109 
110       HeapWalker heap_walker(heap_);
111       heap_walker.Allocation(buffer_begin(buffer2), buffer_end(buffer2));
112       heap_walker.Root(buffer_begin(buffer1), buffer_end(buffer1));
113 
114       ASSERT_EQ(true, heap_walker.DetectLeaks());
115 
116       allocator::vector<Range> leaked(heap_);
117       size_t num_leaks = SIZE_MAX;
118       size_t leaked_bytes = SIZE_MAX;
119       ASSERT_EQ(true, heap_walker.Leaked(leaked, 100, &num_leaks, &leaked_bytes));
120 
121       EXPECT_EQ(0U, num_leaks);
122       EXPECT_EQ(0U, leaked_bytes);
123       EXPECT_EQ(0U, leaked.size());
124     }
125   }
126 }
127 
TEST_F(HeapWalkerTest,unaligned)128 TEST_F(HeapWalkerTest, unaligned) {
129   const int from_buffer_entries = 4;
130   const int to_buffer_bytes = 16;
131   void* buffer1[from_buffer_entries]{};
132   char buffer2[to_buffer_bytes]{};
133 
134   buffer1[1] = &buffer2;
135 
136   for (unsigned int i = 0; i < sizeof(uintptr_t); i++) {
137     for (unsigned int j = 0; j < sizeof(uintptr_t); j++) {
138       HeapWalker heap_walker(heap_);
139       heap_walker.Allocation(buffer_begin(buffer2), buffer_end(buffer2));
140       heap_walker.Root(buffer_begin(buffer1) + i, buffer_end(buffer1) - j);
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,cycle)156 TEST_F(HeapWalkerTest, cycle) {
157   void* buffer1;
158   void* buffer2;
159 
160   buffer1 = &buffer2;
161   buffer2 = &buffer1;
162 
163   HeapWalker heap_walker(heap_);
164   heap_walker.Allocation(buffer_begin(buffer1), buffer_end(buffer1));
165   heap_walker.Allocation(buffer_begin(buffer2), buffer_end(buffer2));
166 
167   ASSERT_EQ(true, heap_walker.DetectLeaks());
168 
169   allocator::vector<Range> leaked(heap_);
170   size_t num_leaks = 0;
171   size_t leaked_bytes = 0;
172   ASSERT_EQ(true, heap_walker.Leaked(leaked, 100, &num_leaks, &leaked_bytes));
173 
174   EXPECT_EQ(2U, num_leaks);
175   EXPECT_EQ(2*sizeof(uintptr_t), leaked_bytes);
176   ASSERT_EQ(2U, leaked.size());
177 }
178 
TEST_F(HeapWalkerTest,segv)179 TEST_F(HeapWalkerTest, segv) {
180   const size_t page_size = sysconf(_SC_PAGE_SIZE);
181   void* buffer1 = mmap(NULL, page_size, PROT_NONE, MAP_ANONYMOUS|MAP_PRIVATE, -1, 0);
182   ASSERT_NE(buffer1, nullptr);
183   void* buffer2;
184 
185   buffer2 = &buffer1;
186 
187   HeapWalker heap_walker(heap_);
188   heap_walker.Allocation(buffer_begin(buffer1), buffer_begin(buffer1)+page_size);
189   heap_walker.Root(buffer_begin(buffer2), buffer_end(buffer2));
190 
191   ASSERT_EQ(true, heap_walker.DetectLeaks());
192 
193   allocator::vector<Range> leaked(heap_);
194   size_t num_leaks = 0;
195   size_t leaked_bytes = 0;
196   ASSERT_EQ(true, heap_walker.Leaked(leaked, 100, &num_leaks, &leaked_bytes));
197 
198   EXPECT_EQ(0U, num_leaks);
199   EXPECT_EQ(0U, leaked_bytes);
200   ASSERT_EQ(0U, leaked.size());
201 }
202