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 "common_runtime_test.h" 23 #include "globals.h" 24 #include "space_bitmap-inl.h" 25 26 namespace art { 27 namespace gc { 28 namespace accounting { 29 30 class SpaceBitmapTest : public CommonRuntimeTest {}; 31 32 TEST_F(SpaceBitmapTest, Init) { 33 uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000); 34 size_t heap_capacity = 16 * MB; 35 std::unique_ptr<ContinuousSpaceBitmap> space_bitmap( 36 ContinuousSpaceBitmap::Create("test bitmap", heap_begin, heap_capacity)); 37 EXPECT_TRUE(space_bitmap.get() != nullptr); 38 } 39 40 class BitmapVerify { 41 public: 42 BitmapVerify(ContinuousSpaceBitmap* bitmap, const mirror::Object* begin, 43 const mirror::Object* end) 44 : bitmap_(bitmap), 45 begin_(begin), 46 end_(end) {} 47 48 void operator()(const mirror::Object* obj) { 49 EXPECT_TRUE(obj >= begin_); 50 EXPECT_TRUE(obj <= end_); 51 EXPECT_EQ(bitmap_->Test(obj), ((reinterpret_cast<uintptr_t>(obj) & 0xF) != 0)); 52 } 53 54 ContinuousSpaceBitmap* const bitmap_; 55 const mirror::Object* begin_; 56 const mirror::Object* end_; 57 }; 58 59 TEST_F(SpaceBitmapTest, ScanRange) { 60 uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000); 61 size_t heap_capacity = 16 * MB; 62 63 std::unique_ptr<ContinuousSpaceBitmap> space_bitmap( 64 ContinuousSpaceBitmap::Create("test bitmap", heap_begin, heap_capacity)); 65 EXPECT_TRUE(space_bitmap != nullptr); 66 67 // Set all the odd bits in the first BitsPerIntPtrT * 3 to one. 68 for (size_t j = 0; j < kBitsPerIntPtrT * 3; ++j) { 69 const mirror::Object* obj = 70 reinterpret_cast<mirror::Object*>(heap_begin + j * kObjectAlignment); 71 if (reinterpret_cast<uintptr_t>(obj) & 0xF) { 72 space_bitmap->Set(obj); 73 } 74 } 75 // Try every possible starting bit in the first word. Then for each starting bit, try each 76 // possible length up to a maximum of kBitsPerWord * 2 - 1 bits. 77 // This handles all the cases, having runs which start and end on the same word, and different 78 // words. 79 for (size_t i = 0; i < static_cast<size_t>(kBitsPerIntPtrT); ++i) { 80 mirror::Object* start = 81 reinterpret_cast<mirror::Object*>(heap_begin + i * kObjectAlignment); 82 for (size_t j = 0; j < static_cast<size_t>(kBitsPerIntPtrT * 2); ++j) { 83 mirror::Object* end = 84 reinterpret_cast<mirror::Object*>(heap_begin + (i + j) * kObjectAlignment); 85 BitmapVerify(space_bitmap.get(), start, end); 86 } 87 } 88 } 89 90 TEST_F(SpaceBitmapTest, ClearRange) { 91 uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000); 92 size_t heap_capacity = 16 * MB; 93 94 std::unique_ptr<ContinuousSpaceBitmap> bitmap( 95 ContinuousSpaceBitmap::Create("test bitmap", heap_begin, heap_capacity)); 96 EXPECT_TRUE(bitmap != nullptr); 97 98 // Set all of the bits in the bitmap. 99 for (size_t j = 0; j < heap_capacity; j += kObjectAlignment) { 100 const mirror::Object* obj = reinterpret_cast<mirror::Object*>(heap_begin + j); 101 bitmap->Set(obj); 102 } 103 104 std::vector<std::pair<uintptr_t, uintptr_t>> ranges = { 105 {0, 10 * KB + kObjectAlignment}, 106 {kObjectAlignment, kObjectAlignment}, 107 {kObjectAlignment, 2 * kObjectAlignment}, 108 {kObjectAlignment, 5 * kObjectAlignment}, 109 {1 * KB + kObjectAlignment, 2 * KB + 5 * kObjectAlignment}, 110 }; 111 // Try clearing a few ranges. 112 for (const std::pair<uintptr_t, uintptr_t>& range : ranges) { 113 const mirror::Object* obj_begin = reinterpret_cast<mirror::Object*>(heap_begin + range.first); 114 const mirror::Object* obj_end = reinterpret_cast<mirror::Object*>(heap_begin + range.second); 115 bitmap->ClearRange(obj_begin, obj_end); 116 // Boundaries should still be marked. 117 for (uintptr_t i = 0; i < range.first; i += kObjectAlignment) { 118 EXPECT_TRUE(bitmap->Test(reinterpret_cast<mirror::Object*>(heap_begin + i))); 119 } 120 for (uintptr_t i = range.second; i < range.second + kPageSize; i += kObjectAlignment) { 121 EXPECT_TRUE(bitmap->Test(reinterpret_cast<mirror::Object*>(heap_begin + i))); 122 } 123 // Everything inside should be cleared. 124 for (uintptr_t i = range.first; i < range.second; i += kObjectAlignment) { 125 EXPECT_FALSE(bitmap->Test(reinterpret_cast<mirror::Object*>(heap_begin + i))); 126 bitmap->Set(reinterpret_cast<mirror::Object*>(heap_begin + i)); 127 } 128 } 129 } 130 131 132 class SimpleCounter { 133 public: 134 explicit SimpleCounter(size_t* counter) : count_(counter) {} 135 136 void operator()(mirror::Object* obj ATTRIBUTE_UNUSED) const { 137 (*count_)++; 138 } 139 140 size_t* const count_; 141 }; 142 143 class RandGen { 144 public: 145 explicit RandGen(uint32_t seed) : val_(seed) {} 146 147 uint32_t next() { 148 val_ = val_ * 48271 % 2147483647; 149 return val_; 150 } 151 152 uint32_t val_; 153 }; 154 155 template <size_t kAlignment> 156 void RunTest() NO_THREAD_SAFETY_ANALYSIS { 157 uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000); 158 size_t heap_capacity = 16 * MB; 159 160 // Seed with 0x1234 for reproducability. 161 RandGen r(0x1234); 162 163 164 for (int i = 0; i < 5 ; ++i) { 165 std::unique_ptr<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 size_t count = 0; 181 SimpleCounter c(&count); 182 183 size_t offset = RoundDown(r.next() % heap_capacity, kAlignment); 184 size_t remain = heap_capacity - offset; 185 size_t end = offset + RoundDown(r.next() % (remain + 1), kAlignment); 186 187 space_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(heap_begin) + offset, 188 reinterpret_cast<uintptr_t>(heap_begin) + end, c); 189 190 size_t manual = 0; 191 for (uintptr_t k = offset; k < end; k += kAlignment) { 192 if (space_bitmap->Test(reinterpret_cast<mirror::Object*>(heap_begin + k))) { 193 manual++; 194 } 195 } 196 197 EXPECT_EQ(count, manual); 198 } 199 } 200 } 201 202 TEST_F(SpaceBitmapTest, VisitorObjectAlignment) { 203 RunTest<kObjectAlignment>(); 204 } 205 206 TEST_F(SpaceBitmapTest, VisitorPageAlignment) { 207 RunTest<kPageSize>(); 208 } 209 210 } // namespace accounting 211 } // namespace gc 212 } // namespace art 213