1cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier/* 2cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier * Copyright (C) 2012 The Android Open Source Project 3cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier * 4cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier * Licensed under the Apache License, Version 2.0 (the "License"); 5cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier * you may not use this file except in compliance with the License. 6cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier * You may obtain a copy of the License at 7cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier * 8cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier * http://www.apache.org/licenses/LICENSE-2.0 9cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier * 10cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier * Unless required by applicable law or agreed to in writing, software 11cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier * distributed under the License is distributed on an "AS IS" BASIS, 12cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier * See the License for the specific language governing permissions and 14cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier * limitations under the License. 15cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier */ 16cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 17cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier#include "space_bitmap.h" 18cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 19a1ce1fef2d49d1d537776a5308ace7102a815fe5Brian Carlstrom#include <stdint.h> 20700a402244a1a423da4f3ba8032459f4b65fa18fIan Rogers#include <memory> 21a1ce1fef2d49d1d537776a5308ace7102a815fe5Brian Carlstrom 22a1ce1fef2d49d1d537776a5308ace7102a815fe5Brian Carlstrom#include "common_runtime_test.h" 23cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier#include "globals.h" 242dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers#include "space_bitmap-inl.h" 25cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 26cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartiernamespace art { 271d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace gc { 281d54e73444e017d3a65234e0f193846f3e27472bIan Rogersnamespace accounting { 29cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 30a1ce1fef2d49d1d537776a5308ace7102a815fe5Brian Carlstromclass SpaceBitmapTest : public CommonRuntimeTest {}; 31cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 32cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu ChartierTEST_F(SpaceBitmapTest, Init) { 33cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier byte* heap_begin = reinterpret_cast<byte*>(0x10000000); 34cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier size_t heap_capacity = 16 * MB; 35700a402244a1a423da4f3ba8032459f4b65fa18fIan Rogers std::unique_ptr<ContinuousSpaceBitmap> space_bitmap( 36a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier ContinuousSpaceBitmap::Create("test bitmap", heap_begin, heap_capacity)); 37cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier EXPECT_TRUE(space_bitmap.get() != NULL); 38cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier} 39cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 40cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartierclass BitmapVerify { 41cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier public: 42a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier BitmapVerify(ContinuousSpaceBitmap* bitmap, const mirror::Object* begin, 43a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier const mirror::Object* end) 44cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier : bitmap_(bitmap), 45cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier begin_(begin), 46cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier end_(end) {} 47cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 48df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom void operator()(const mirror::Object* obj) { 49cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier EXPECT_TRUE(obj >= begin_); 50cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier EXPECT_TRUE(obj <= end_); 514274889d48ef82369bf2c1ca70d84689b4f9e93aBrian Carlstrom EXPECT_EQ(bitmap_->Test(obj), ((reinterpret_cast<uintptr_t>(obj) & 0xF) != 0)); 52cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 53cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 54a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier ContinuousSpaceBitmap* bitmap_; 552dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const mirror::Object* begin_; 562dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const mirror::Object* end_; 57cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier}; 58cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 59cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu ChartierTEST_F(SpaceBitmapTest, ScanRange) { 60cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier byte* heap_begin = reinterpret_cast<byte*>(0x10000000); 61cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier size_t heap_capacity = 16 * MB; 62cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 63700a402244a1a423da4f3ba8032459f4b65fa18fIan Rogers std::unique_ptr<ContinuousSpaceBitmap> space_bitmap( 64a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier ContinuousSpaceBitmap::Create("test bitmap", heap_begin, heap_capacity)); 65cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier EXPECT_TRUE(space_bitmap.get() != NULL); 66cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 67cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // Set all the odd bits in the first BitsPerWord * 3 to one. 6802c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom for (size_t j = 0; j < kBitsPerWord * 3; ++j) { 692dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers const mirror::Object* obj = 70a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier reinterpret_cast<mirror::Object*>(heap_begin + j * kObjectAlignment); 71cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier if (reinterpret_cast<uintptr_t>(obj) & 0xF) { 72cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier space_bitmap->Set(obj); 73cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 74cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 75cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // Try every possible starting bit in the first word. Then for each starting bit, try each 76cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // possible length up to a maximum of kBitsPerWord * 2 - 1 bits. 77cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // This handles all the cases, having runs which start and end on the same word, and different 78cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier // words. 79cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier for (size_t i = 0; i < static_cast<size_t>(kBitsPerWord); ++i) { 802dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* start = 81a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier reinterpret_cast<mirror::Object*>(heap_begin + i * kObjectAlignment); 82cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier for (size_t j = 0; j < static_cast<size_t>(kBitsPerWord * 2); ++j) { 832dd0e2cea360bc9206eb88ecc40d259e796c239dIan Rogers mirror::Object* end = 84a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier reinterpret_cast<mirror::Object*>(heap_begin + (i + j) * kObjectAlignment); 85cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier BitmapVerify(space_bitmap.get(), start, end); 86cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 87cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier } 88cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier} 89cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier 90be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampeclass SimpleCounter { 91be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe public: 92be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe explicit SimpleCounter(size_t* counter) : count_(counter) {} 93be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 94be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe void operator()(mirror::Object* obj) const { 95be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe (*count_)++; 96be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe } 97be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 98be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe size_t* count_; 99be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe}; 100be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 101be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampeclass RandGen { 102be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe public: 103be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe explicit RandGen(uint32_t seed) : val_(seed) {} 104be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 105be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe uint32_t next() { 106be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe val_ = val_ * 48271 % 2147483647; 107be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe return val_; 108be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe } 109be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 110be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe uint32_t val_; 111be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe}; 112be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 113bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartiertemplate <size_t kAlignment> 114bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartiervoid RunTest() NO_THREAD_SAFETY_ANALYSIS { 115be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe byte* heap_begin = reinterpret_cast<byte*>(0x10000000); 116be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe size_t heap_capacity = 16 * MB; 117be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 118be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe // Seed with 0x1234 for reproducability. 119be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe RandGen r(0x1234); 120be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 121be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 122be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe for (int i = 0; i < 5 ; ++i) { 123700a402244a1a423da4f3ba8032459f4b65fa18fIan Rogers std::unique_ptr<ContinuousSpaceBitmap> space_bitmap( 124a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier ContinuousSpaceBitmap::Create("test bitmap", heap_begin, heap_capacity)); 125be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 126be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe for (int j = 0; j < 10000; ++j) { 127bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier size_t offset = RoundDown(r.next() % heap_capacity, kAlignment); 128be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe bool set = r.next() % 2 == 1; 129be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 130be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe if (set) { 131be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe space_bitmap->Set(reinterpret_cast<mirror::Object*>(heap_begin + offset)); 132be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe } else { 133be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe space_bitmap->Clear(reinterpret_cast<mirror::Object*>(heap_begin + offset)); 134be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe } 135be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe } 136be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 137be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe for (int j = 0; j < 50; ++j) { 138be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe size_t count = 0; 139be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe SimpleCounter c(&count); 140be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 141bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier size_t offset = RoundDown(r.next() % heap_capacity, kAlignment); 142be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe size_t remain = heap_capacity - offset; 143bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier size_t end = offset + RoundDown(r.next() % (remain + 1), kAlignment); 144be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 145be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe space_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(heap_begin) + offset, 146be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe reinterpret_cast<uintptr_t>(heap_begin) + end, c); 147be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 148be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe size_t manual = 0; 149bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier for (uintptr_t k = offset; k < end; k += kAlignment) { 150be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe if (space_bitmap->Test(reinterpret_cast<mirror::Object*>(heap_begin + k))) { 151be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe manual++; 152be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe } 153be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe } 154be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 155be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe EXPECT_EQ(count, manual); 156be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe } 157be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe } 158be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe} 159be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 160bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu ChartierTEST_F(SpaceBitmapTest, VisitorObjectAlignment) { 161bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier RunTest<kObjectAlignment>(); 162bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier} 163bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier 164bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu ChartierTEST_F(SpaceBitmapTest, VisitorPageAlignment) { 165bbd695c71e0bf518f582e84524e1cdeb3de3896cMathieu Chartier RunTest<kPageSize>(); 166be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe} 167be73e57308680382efd1e60fa03ac1eb5abcc9c7Andreas Gampe 1681d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace accounting 1691d54e73444e017d3a65234e0f193846f3e27472bIan Rogers} // namespace gc 170cc236d74772dda5a4161d9bc5f497fd3d956eb87Mathieu Chartier} // namespace art 171