1 /*
2  * Copyright (C) 2012 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 "space_bitmap.h"
18 
19 #include <stdint.h>
20 #include <memory>
21 
22 #include "base/mutex.h"
23 #include "common_runtime_test.h"
24 #include "runtime_globals.h"
25 #include "space_bitmap-inl.h"
26 
27 namespace art {
28 namespace gc {
29 namespace accounting {
30 
31 class SpaceBitmapTest : public CommonRuntimeTest {};
32 
TEST_F(SpaceBitmapTest,Init)33 TEST_F(SpaceBitmapTest, Init) {
34   uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000);
35   size_t heap_capacity = 16 * MB;
36   ContinuousSpaceBitmap space_bitmap(
37       ContinuousSpaceBitmap::Create("test bitmap", heap_begin, heap_capacity));
38   EXPECT_TRUE(space_bitmap.IsValid());
39 }
40 
41 class BitmapVerify {
42  public:
BitmapVerify(ContinuousSpaceBitmap * bitmap,const mirror::Object * begin,const mirror::Object * end)43   BitmapVerify(ContinuousSpaceBitmap* bitmap, const mirror::Object* begin,
44                const mirror::Object* end)
45     : bitmap_(bitmap),
46       begin_(begin),
47       end_(end) {}
48 
operator ()(const mirror::Object * obj)49   void operator()(const mirror::Object* obj) {
50     EXPECT_TRUE(obj >= begin_);
51     EXPECT_TRUE(obj <= end_);
52     EXPECT_EQ(bitmap_->Test(obj), ((reinterpret_cast<uintptr_t>(obj) & 0xF) != 0));
53   }
54 
55   ContinuousSpaceBitmap* const bitmap_;
56   const mirror::Object* begin_;
57   const mirror::Object* end_;
58 };
59 
TEST_F(SpaceBitmapTest,ScanRange)60 TEST_F(SpaceBitmapTest, ScanRange) {
61   uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000);
62   size_t heap_capacity = 16 * MB;
63 
64   ContinuousSpaceBitmap space_bitmap(
65       ContinuousSpaceBitmap::Create("test bitmap", heap_begin, heap_capacity));
66   EXPECT_TRUE(space_bitmap.IsValid());
67 
68   // Set all the odd bits in the first BitsPerIntPtrT * 3 to one.
69   for (size_t j = 0; j < kBitsPerIntPtrT * 3; ++j) {
70     const mirror::Object* obj =
71         reinterpret_cast<mirror::Object*>(heap_begin + j * kObjectAlignment);
72     if (reinterpret_cast<uintptr_t>(obj) & 0xF) {
73       space_bitmap.Set(obj);
74     }
75   }
76   // Try every possible starting bit in the first word. Then for each starting bit, try each
77   // possible length up to a maximum of `kBitsPerIntPtrT * 2 - 1` bits.
78   // This handles all the cases, having runs which start and end on the same word, and different
79   // words.
80   for (size_t i = 0; i < static_cast<size_t>(kBitsPerIntPtrT); ++i) {
81     mirror::Object* start =
82         reinterpret_cast<mirror::Object*>(heap_begin + i * kObjectAlignment);
83     for (size_t j = 0; j < static_cast<size_t>(kBitsPerIntPtrT * 2); ++j) {
84       mirror::Object* end =
85           reinterpret_cast<mirror::Object*>(heap_begin + (i + j) * kObjectAlignment);
86       BitmapVerify(&space_bitmap, start, end);
87     }
88   }
89 }
90 
TEST_F(SpaceBitmapTest,ClearRange)91 TEST_F(SpaceBitmapTest, ClearRange) {
92   uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000);
93   size_t heap_capacity = 16 * MB;
94 
95   ContinuousSpaceBitmap bitmap(
96       ContinuousSpaceBitmap::Create("test bitmap", heap_begin, heap_capacity));
97   EXPECT_TRUE(bitmap.IsValid());
98 
99   // Set all of the bits in the bitmap.
100   for (size_t j = 0; j < heap_capacity; j += kObjectAlignment) {
101     const mirror::Object* obj = reinterpret_cast<mirror::Object*>(heap_begin + j);
102     bitmap.Set(obj);
103   }
104 
105   std::vector<std::pair<uintptr_t, uintptr_t>> ranges = {
106       {0, 10 * KB + kObjectAlignment},
107       {kObjectAlignment, kObjectAlignment},
108       {kObjectAlignment, 2 * kObjectAlignment},
109       {kObjectAlignment, 5 * kObjectAlignment},
110       {1 * KB + kObjectAlignment, 2 * KB + 5 * kObjectAlignment},
111   };
112   // Try clearing a few ranges.
113   for (const std::pair<uintptr_t, uintptr_t>& range : ranges) {
114     const mirror::Object* obj_begin = reinterpret_cast<mirror::Object*>(heap_begin + range.first);
115     const mirror::Object* obj_end = reinterpret_cast<mirror::Object*>(heap_begin + range.second);
116     bitmap.ClearRange(obj_begin, obj_end);
117     // Boundaries should still be marked.
118     for (uintptr_t i = 0; i < range.first; i += kObjectAlignment) {
119       EXPECT_TRUE(bitmap.Test(reinterpret_cast<mirror::Object*>(heap_begin + i)));
120     }
121     for (uintptr_t i = range.second; i < range.second + kPageSize; i += kObjectAlignment) {
122       EXPECT_TRUE(bitmap.Test(reinterpret_cast<mirror::Object*>(heap_begin + i)));
123     }
124     // Everything inside should be cleared.
125     for (uintptr_t i = range.first; i < range.second; i += kObjectAlignment) {
126       EXPECT_FALSE(bitmap.Test(reinterpret_cast<mirror::Object*>(heap_begin + i)));
127       bitmap.Set(reinterpret_cast<mirror::Object*>(heap_begin + i));
128     }
129   }
130 }
131 
132 
133 class SimpleCounter {
134  public:
SimpleCounter(size_t * counter)135   explicit SimpleCounter(size_t* counter) : count_(counter) {}
136 
operator ()(mirror::Object * obj ATTRIBUTE_UNUSED) const137   void operator()(mirror::Object* obj ATTRIBUTE_UNUSED) const {
138     (*count_)++;
139   }
140 
141   size_t* const count_;
142 };
143 
144 class RandGen {
145  public:
RandGen(uint32_t seed)146   explicit RandGen(uint32_t seed) : val_(seed) {}
147 
next()148   uint32_t next() {
149     val_ = val_ * 48271 % 2147483647 + 13;
150     return val_;
151   }
152 
153   uint32_t val_;
154 };
155 
156 template <size_t kAlignment, typename TestFn>
RunTest(TestFn && fn)157 static void RunTest(TestFn&& fn) NO_THREAD_SAFETY_ANALYSIS {
158   uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000);
159   size_t heap_capacity = 16 * MB;
160 
161   // Seed with 0x1234 for reproducability.
162   RandGen r(0x1234);
163 
164   for (int i = 0; i < 5 ; ++i) {
165     ContinuousSpaceBitmap space_bitmap(
166         ContinuousSpaceBitmap::Create("test bitmap", heap_begin, heap_capacity));
167 
168     for (int j = 0; j < 10000; ++j) {
169       size_t offset = RoundDown(r.next() % heap_capacity, kAlignment);
170       bool set = r.next() % 2 == 1;
171 
172       if (set) {
173         space_bitmap.Set(reinterpret_cast<mirror::Object*>(heap_begin + offset));
174       } else {
175         space_bitmap.Clear(reinterpret_cast<mirror::Object*>(heap_begin + offset));
176       }
177     }
178 
179     for (int j = 0; j < 50; ++j) {
180       const size_t offset = RoundDown(r.next() % heap_capacity, kAlignment);
181       const size_t remain = heap_capacity - offset;
182       const size_t end = offset + RoundDown(r.next() % (remain + 1), kAlignment);
183 
184       size_t manual = 0;
185       for (uintptr_t k = offset; k < end; k += kAlignment) {
186         if (space_bitmap.Test(reinterpret_cast<mirror::Object*>(heap_begin + k))) {
187           manual++;
188         }
189       }
190 
191       uintptr_t range_begin = reinterpret_cast<uintptr_t>(heap_begin) + offset;
192       uintptr_t range_end = reinterpret_cast<uintptr_t>(heap_begin) + end;
193 
194       fn(&space_bitmap, range_begin, range_end, manual);
195     }
196   }
197 }
198 
199 template <size_t kAlignment>
RunTestCount()200 static void RunTestCount() {
201   auto count_test_fn = [](ContinuousSpaceBitmap* space_bitmap,
202                           uintptr_t range_begin,
203                           uintptr_t range_end,
204                           size_t manual_count) {
205     size_t count = 0;
206     auto count_fn = [&count](mirror::Object* obj ATTRIBUTE_UNUSED) {
207       count++;
208     };
209     space_bitmap->VisitMarkedRange(range_begin, range_end, count_fn);
210     EXPECT_EQ(count, manual_count);
211   };
212   RunTest<kAlignment>(count_test_fn);
213 }
214 
TEST_F(SpaceBitmapTest,VisitorObjectAlignment)215 TEST_F(SpaceBitmapTest, VisitorObjectAlignment) {
216   RunTestCount<kObjectAlignment>();
217 }
218 
TEST_F(SpaceBitmapTest,VisitorPageAlignment)219 TEST_F(SpaceBitmapTest, VisitorPageAlignment) {
220   RunTestCount<kPageSize>();
221 }
222 
223 template <size_t kAlignment>
RunTestOrder()224 void RunTestOrder() {
225   auto order_test_fn = [](ContinuousSpaceBitmap* space_bitmap,
226                           uintptr_t range_begin,
227                           uintptr_t range_end,
228                           size_t manual_count)
229       REQUIRES_SHARED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
230     mirror::Object* last_ptr = nullptr;
231     auto order_check = [&last_ptr](mirror::Object* obj) {
232       EXPECT_LT(last_ptr, obj);
233       last_ptr = obj;
234     };
235 
236     // Test complete walk.
237     space_bitmap->Walk(order_check);
238     if (manual_count > 0) {
239       EXPECT_NE(nullptr, last_ptr);
240     }
241 
242     // Test range.
243     last_ptr = nullptr;
244     space_bitmap->VisitMarkedRange(range_begin, range_end, order_check);
245     if (manual_count > 0) {
246       EXPECT_NE(nullptr, last_ptr);
247     }
248   };
249   RunTest<kAlignment>(order_test_fn);
250 }
251 
TEST_F(SpaceBitmapTest,OrderObjectAlignment)252 TEST_F(SpaceBitmapTest, OrderObjectAlignment) {
253   RunTestOrder<kObjectAlignment>();
254 }
255 
TEST_F(SpaceBitmapTest,OrderPageAlignment)256 TEST_F(SpaceBitmapTest, OrderPageAlignment) {
257   RunTestOrder<kPageSize>();
258 }
259 
260 }  // namespace accounting
261 }  // namespace gc
262 }  // namespace art
263