runtime/gc/accounting/space_bitmap_test.cc - LeafOS-Project/android_art - Gitiles

 /*
  * Copyright (C) 2012 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include "space_bitmap.h"

 #include <stdint.h>
 #include <memory>

 #include "base/mutex.h"
 #include "common_runtime_test.h"
 #include "gc/space/large_object_space.h"
 #include "runtime_globals.h"
 #include "space_bitmap-inl.h"

 namespace art HIDDEN {
 namespace gc {
 namespace accounting {

 // SpaceBitmapTest is a CommonRuntimeTest as the test requires runtime to be initialized to enable
 // access to space::LargeObjectSpace::ObjectAlignment().
 template <typename T>
 class SpaceBitmapTest : public CommonRuntimeTest {};

 // Main test parameters. For each test case, we pair together a SpaceBitmap
 // implementation with an object alignment. The object alignment may be larger
 // than the underlying SpaceBitmap alignment.
 template <typename T, size_t kAlignment>
 struct SpaceBitmapTestType {
   using SpaceBitmap = T;
   static constexpr size_t GetObjectAlignment() {
     return kAlignment;
   }
 };

 // This is a special case where object alignment is chosen to be the large-object
 // alignment determined at runtime.
 template <typename T>
 struct SpaceBitmapTestPageSizeType {
   using SpaceBitmap = T;
   static size_t GetObjectAlignment() {
     return space::LargeObjectSpace::ObjectAlignment();
   }
 };

 using SpaceBitmapTestTypes =
     ::testing::Types<SpaceBitmapTestType<ContinuousSpaceBitmap, kObjectAlignment>,
                      // Large objects are aligned to the OS page size, try
                      // different supported values, including the current
                      // runtime page size.
                      SpaceBitmapTestType<LargeObjectBitmap, kMinPageSize>,
                      SpaceBitmapTestPageSizeType<LargeObjectBitmap>,
                      SpaceBitmapTestType<LargeObjectBitmap, kMaxPageSize>>;

 TYPED_TEST_CASE(SpaceBitmapTest, SpaceBitmapTestTypes);

 TYPED_TEST(SpaceBitmapTest, Init) {
   uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000);
   size_t heap_capacity = 16 * MB;
   auto space_bitmap(TypeParam::SpaceBitmap::Create("test bitmap", heap_begin, heap_capacity));
   EXPECT_TRUE(space_bitmap.IsValid());
 }

 template <typename SpaceBitmap>
 class BitmapVerify {
  public:
   BitmapVerify(SpaceBitmap* bitmap, const mirror::Object* begin,
                const mirror::Object* end)
     : bitmap_(bitmap),
       begin_(begin),
       end_(end) {}

   void operator()(const mirror::Object* obj) {
     EXPECT_TRUE(obj >= begin_);
     EXPECT_TRUE(obj <= end_);
     EXPECT_EQ(bitmap_->Test(obj), ((reinterpret_cast<uintptr_t>(obj) & 0xF) != 0));
   }

   SpaceBitmap* const bitmap_;
   const mirror::Object* begin_;
   const mirror::Object* end_;
 };

 TYPED_TEST(SpaceBitmapTest, ScanRange) {
   uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000);
   size_t heap_capacity = 16 * MB;
   const size_t gObjectAlignment = TypeParam::GetObjectAlignment();

   auto space_bitmap(TypeParam::SpaceBitmap::Create("test bitmap", heap_begin, heap_capacity));
   EXPECT_TRUE(space_bitmap.IsValid());

   // Set all the odd bits in the first BitsPerIntPtrT * 3 to one.
   for (size_t j = 0; j < kBitsPerIntPtrT * 3; ++j) {
     const mirror::Object* obj =
         reinterpret_cast<mirror::Object*>(heap_begin + j * gObjectAlignment);
     if (reinterpret_cast<uintptr_t>(obj) & 0xF) {
       space_bitmap.Set(obj);
     }
   }
   // Try every possible starting bit in the first word. Then for each starting bit, try each
   // possible length up to a maximum of `kBitsPerIntPtrT * 2 - 1` bits.
   // This handles all the cases, having runs which start and end on the same word, and different
   // words.
   for (size_t i = 0; i < static_cast<size_t>(kBitsPerIntPtrT); ++i) {
     mirror::Object* start =
         reinterpret_cast<mirror::Object*>(heap_begin + i * gObjectAlignment);
     for (size_t j = 0; j < static_cast<size_t>(kBitsPerIntPtrT * 2); ++j) {
       mirror::Object* end =
           reinterpret_cast<mirror::Object*>(heap_begin + (i + j) * gObjectAlignment);
       BitmapVerify(&space_bitmap, start, end);
     }
   }
 }

 TYPED_TEST(SpaceBitmapTest, ClearRange) {
   const size_t page_size = MemMap::GetPageSize();
   uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000);
   size_t heap_capacity = 16 * MB;
   const size_t gObjectAlignment = TypeParam::GetObjectAlignment();

   auto bitmap(TypeParam::SpaceBitmap::Create("test bitmap", heap_begin, heap_capacity));
   EXPECT_TRUE(bitmap.IsValid());

   // Set all of the bits in the bitmap.
   for (size_t j = 0; j < heap_capacity; j += gObjectAlignment) {
     const mirror::Object* obj = reinterpret_cast<mirror::Object*>(heap_begin + j);
     bitmap.Set(obj);
   }

   std::vector<std::pair<uintptr_t, uintptr_t>> ranges = {
       {0, RoundUp(10 * KB, gObjectAlignment) + gObjectAlignment},
       {gObjectAlignment, gObjectAlignment},
       {gObjectAlignment, 2 * gObjectAlignment},
       {gObjectAlignment, 5 * gObjectAlignment},
       {RoundUp(1 * KB, gObjectAlignment) + gObjectAlignment,
        RoundUp(2 * KB, gObjectAlignment) + 5 * gObjectAlignment},
   };
   // Try clearing a few ranges.
   for (const std::pair<uintptr_t, uintptr_t>& range : ranges) {
     const mirror::Object* obj_begin = reinterpret_cast<mirror::Object*>(heap_begin + range.first);
     const mirror::Object* obj_end = reinterpret_cast<mirror::Object*>(heap_begin + range.second);
     bitmap.ClearRange(obj_begin, obj_end);
     // Boundaries should still be marked.
     for (uintptr_t i = 0; i < range.first; i += gObjectAlignment) {
       EXPECT_TRUE(bitmap.Test(reinterpret_cast<mirror::Object*>(heap_begin + i)));
     }
     for (uintptr_t i = range.second; i < range.second + page_size; i += gObjectAlignment) {
       EXPECT_TRUE(bitmap.Test(reinterpret_cast<mirror::Object*>(heap_begin + i)));
     }
     // Everything inside should be cleared.
     for (uintptr_t i = range.first; i < range.second; i += gObjectAlignment) {
       EXPECT_FALSE(bitmap.Test(reinterpret_cast<mirror::Object*>(heap_begin + i)));
       bitmap.Set(reinterpret_cast<mirror::Object*>(heap_begin + i));
     }
   }
 }


 class SimpleCounter {
  public:
   explicit SimpleCounter(size_t* counter) : count_(counter) {}

   void operator()([[maybe_unused]] mirror::Object* obj) const { (*count_)++; }

   size_t* const count_;
 };

 class RandGen {
  public:
   explicit RandGen(uint32_t seed) : val_(seed) {}

   uint32_t next() {
     val_ = val_ * 48271 % 2147483647 + 13;
     return val_;
   }

   uint32_t val_;
 };

 template <typename SpaceBitmap, typename TestFn>
 static void RunTest(size_t alignment, TestFn&& fn) NO_THREAD_SAFETY_ANALYSIS {
   uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000);
   size_t heap_capacity = 16 * MB;

   // Seed with 0x1234 for reproducability.
   RandGen r(0x1234);

   for (int i = 0; i < 5 ; ++i) {
     SpaceBitmap space_bitmap(SpaceBitmap::Create("test bitmap", heap_begin, heap_capacity));

     for (int j = 0; j < 10000; ++j) {
       size_t offset = RoundDown(r.next() % heap_capacity, alignment);
       bool set = r.next() % 2 == 1;

       if (set) {
         space_bitmap.Set(reinterpret_cast<mirror::Object*>(heap_begin + offset));
       } else {
         space_bitmap.Clear(reinterpret_cast<mirror::Object*>(heap_begin + offset));
       }
     }

     for (int j = 0; j < 50; ++j) {
       const size_t offset = RoundDown(r.next() % heap_capacity, alignment);
       const size_t remain = heap_capacity - offset;
       const size_t end = offset + RoundDown(r.next() % (remain + 1), alignment);

       size_t manual = 0;
       for (uintptr_t k = offset; k < end; k += alignment) {
         if (space_bitmap.Test(reinterpret_cast<mirror::Object*>(heap_begin + k))) {
           manual++;
         }
       }

       uintptr_t range_begin = reinterpret_cast<uintptr_t>(heap_begin) + offset;
       uintptr_t range_end = reinterpret_cast<uintptr_t>(heap_begin) + end;

       fn(&space_bitmap, range_begin, range_end, manual);
     }
   }
 }

 TYPED_TEST(SpaceBitmapTest, VisitorAlignment) {
   using SpaceBitmap = typename TypeParam::SpaceBitmap;
   auto count_test_fn = [](SpaceBitmap* space_bitmap,
                           uintptr_t range_begin,
                           uintptr_t range_end,
                           size_t manual_count) {
     size_t count = 0;
     auto count_fn = [&count]([[maybe_unused]] mirror::Object* obj) { count++; };
     space_bitmap->VisitMarkedRange(range_begin, range_end, count_fn);
     EXPECT_EQ(count, manual_count);
   };
   RunTest<SpaceBitmap>(TypeParam::GetObjectAlignment(), count_test_fn);
 }

 TYPED_TEST(SpaceBitmapTest, OrderAlignment) {
   using SpaceBitmap = typename TypeParam::SpaceBitmap;
   auto order_test_fn = [](SpaceBitmap* space_bitmap,
                           uintptr_t range_begin,
                           uintptr_t range_end,
                           size_t manual_count)
       REQUIRES_SHARED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
     mirror::Object* last_ptr = nullptr;
     auto order_check = [&last_ptr](mirror::Object* obj) {
       EXPECT_LT(last_ptr, obj);
       last_ptr = obj;
     };

     // Test complete walk.
     space_bitmap->Walk(order_check);
     if (manual_count > 0) {
       EXPECT_NE(nullptr, last_ptr);
     }

     // Test range.
     last_ptr = nullptr;
     space_bitmap->VisitMarkedRange(range_begin, range_end, order_check);
     if (manual_count > 0) {
       EXPECT_NE(nullptr, last_ptr);
     }
   };
   RunTest<SpaceBitmap>(TypeParam::GetObjectAlignment(), order_test_fn);
 }

 }  // namespace accounting
 }  // namespace gc
 }  // namespace art
	/*
	* Copyright (C) 2012 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include "space_bitmap.h"

	#include <stdint.h>
	#include <memory>

	#include "base/mutex.h"
	#include "common_runtime_test.h"
	#include "gc/space/large_object_space.h"
	#include "runtime_globals.h"
	#include "space_bitmap-inl.h"

	namespace art HIDDEN {
	namespace gc {
	namespace accounting {

	// SpaceBitmapTest is a CommonRuntimeTest as the test requires runtime to be initialized to enable
	// access to space::LargeObjectSpace::ObjectAlignment().
	template <typename T>
	class SpaceBitmapTest : public CommonRuntimeTest {};

	// Main test parameters. For each test case, we pair together a SpaceBitmap
	// implementation with an object alignment. The object alignment may be larger
	// than the underlying SpaceBitmap alignment.
	template <typename T, size_t kAlignment>
	struct SpaceBitmapTestType {
	using SpaceBitmap = T;
	static constexpr size_t GetObjectAlignment() {
	return kAlignment;
	}
	};

	// This is a special case where object alignment is chosen to be the large-object
	// alignment determined at runtime.
	template <typename T>
	struct SpaceBitmapTestPageSizeType {
	using SpaceBitmap = T;
	static size_t GetObjectAlignment() {
	return space::LargeObjectSpace::ObjectAlignment();
	}
	};

	using SpaceBitmapTestTypes =
	::testing::Types<SpaceBitmapTestType<ContinuousSpaceBitmap, kObjectAlignment>,
	// Large objects are aligned to the OS page size, try
	// different supported values, including the current
	// runtime page size.
	SpaceBitmapTestType<LargeObjectBitmap, kMinPageSize>,
	SpaceBitmapTestPageSizeType<LargeObjectBitmap>,
	SpaceBitmapTestType<LargeObjectBitmap, kMaxPageSize>>;

	TYPED_TEST_CASE(SpaceBitmapTest, SpaceBitmapTestTypes);

	TYPED_TEST(SpaceBitmapTest, Init) {
	uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000);
	size_t heap_capacity = 16 * MB;
	auto space_bitmap(TypeParam::SpaceBitmap::Create("test bitmap", heap_begin, heap_capacity));
	EXPECT_TRUE(space_bitmap.IsValid());
	}

	template <typename SpaceBitmap>
	class BitmapVerify {
	public:
	BitmapVerify(SpaceBitmap* bitmap, const mirror::Object* begin,
	const mirror::Object* end)
	: bitmap_(bitmap),
	begin_(begin),
	end_(end) {}

	void operator()(const mirror::Object* obj) {
	EXPECT_TRUE(obj >= begin_);
	EXPECT_TRUE(obj <= end_);
	EXPECT_EQ(bitmap_->Test(obj), ((reinterpret_cast<uintptr_t>(obj) & 0xF) != 0));
	}

	SpaceBitmap* const bitmap_;
	const mirror::Object* begin_;
	const mirror::Object* end_;
	};

	TYPED_TEST(SpaceBitmapTest, ScanRange) {
	uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000);
	size_t heap_capacity = 16 * MB;
	const size_t gObjectAlignment = TypeParam::GetObjectAlignment();

	auto space_bitmap(TypeParam::SpaceBitmap::Create("test bitmap", heap_begin, heap_capacity));
	EXPECT_TRUE(space_bitmap.IsValid());

	// Set all the odd bits in the first BitsPerIntPtrT * 3 to one.
	for (size_t j = 0; j < kBitsPerIntPtrT * 3; ++j) {
	const mirror::Object* obj =
	reinterpret_cast<mirror::Object>(heap_begin + j gObjectAlignment);
	if (reinterpret_cast<uintptr_t>(obj) & 0xF) {
	space_bitmap.Set(obj);
	}
	}
	// Try every possible starting bit in the first word. Then for each starting bit, try each
	// possible length up to a maximum of `kBitsPerIntPtrT * 2 - 1` bits.
	// This handles all the cases, having runs which start and end on the same word, and different
	// words.
	for (size_t i = 0; i < static_cast<size_t>(kBitsPerIntPtrT); ++i) {
	mirror::Object* start =
	reinterpret_cast<mirror::Object>(heap_begin + i gObjectAlignment);
	for (size_t j = 0; j < static_cast<size_t>(kBitsPerIntPtrT * 2); ++j) {
	mirror::Object* end =
	reinterpret_cast<mirror::Object>(heap_begin + (i + j) gObjectAlignment);
	BitmapVerify(&space_bitmap, start, end);
	}
	}
	}

	TYPED_TEST(SpaceBitmapTest, ClearRange) {
	const size_t page_size = MemMap::GetPageSize();
	uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000);
	size_t heap_capacity = 16 * MB;
	const size_t gObjectAlignment = TypeParam::GetObjectAlignment();

	auto bitmap(TypeParam::SpaceBitmap::Create("test bitmap", heap_begin, heap_capacity));
	EXPECT_TRUE(bitmap.IsValid());

	// Set all of the bits in the bitmap.
	for (size_t j = 0; j < heap_capacity; j += gObjectAlignment) {
	const mirror::Object* obj = reinterpret_cast<mirror::Object*>(heap_begin + j);
	bitmap.Set(obj);
	}

	std::vector<std::pair<uintptr_t, uintptr_t>> ranges = {
	{0, RoundUp(10 * KB, gObjectAlignment) + gObjectAlignment},
	{gObjectAlignment, gObjectAlignment},
	{gObjectAlignment, 2 * gObjectAlignment},
	{gObjectAlignment, 5 * gObjectAlignment},
	{RoundUp(1 * KB, gObjectAlignment) + gObjectAlignment,
	RoundUp(2 * KB, gObjectAlignment) + 5 * gObjectAlignment},
	};
	// Try clearing a few ranges.
	for (const std::pair<uintptr_t, uintptr_t>& range : ranges) {
	const mirror::Object* obj_begin = reinterpret_cast<mirror::Object*>(heap_begin + range.first);
	const mirror::Object* obj_end = reinterpret_cast<mirror::Object*>(heap_begin + range.second);
	bitmap.ClearRange(obj_begin, obj_end);
	// Boundaries should still be marked.
	for (uintptr_t i = 0; i < range.first; i += gObjectAlignment) {
	EXPECT_TRUE(bitmap.Test(reinterpret_cast<mirror::Object*>(heap_begin + i)));
	}
	for (uintptr_t i = range.second; i < range.second + page_size; i += gObjectAlignment) {
	EXPECT_TRUE(bitmap.Test(reinterpret_cast<mirror::Object*>(heap_begin + i)));
	}
	// Everything inside should be cleared.
	for (uintptr_t i = range.first; i < range.second; i += gObjectAlignment) {
	EXPECT_FALSE(bitmap.Test(reinterpret_cast<mirror::Object*>(heap_begin + i)));
	bitmap.Set(reinterpret_cast<mirror::Object*>(heap_begin + i));
	}
	}
	}


	class SimpleCounter {
	public:
	explicit SimpleCounter(size_t* counter) : count_(counter) {}

	void operator()([[maybe_unused]] mirror::Object* obj) const { (*count_)++; }

	size_t* const count_;
	};

	class RandGen {
	public:
	explicit RandGen(uint32_t seed) : val_(seed) {}

	uint32_t next() {
	val_ = val_ * 48271 % 2147483647 + 13;
	return val_;
	}

	uint32_t val_;
	};

	template <typename SpaceBitmap, typename TestFn>
	static void RunTest(size_t alignment, TestFn&& fn) NO_THREAD_SAFETY_ANALYSIS {
	uint8_t* heap_begin = reinterpret_cast<uint8_t*>(0x10000000);
	size_t heap_capacity = 16 * MB;

	// Seed with 0x1234 for reproducability.
	RandGen r(0x1234);

	for (int i = 0; i < 5 ; ++i) {
	SpaceBitmap space_bitmap(SpaceBitmap::Create("test bitmap", heap_begin, heap_capacity));

	for (int j = 0; j < 10000; ++j) {
	size_t offset = RoundDown(r.next() % heap_capacity, alignment);
	bool set = r.next() % 2 == 1;

	if (set) {
	space_bitmap.Set(reinterpret_cast<mirror::Object*>(heap_begin + offset));
	} else {
	space_bitmap.Clear(reinterpret_cast<mirror::Object*>(heap_begin + offset));
	}
	}

	for (int j = 0; j < 50; ++j) {
	const size_t offset = RoundDown(r.next() % heap_capacity, alignment);
	const size_t remain = heap_capacity - offset;
	const size_t end = offset + RoundDown(r.next() % (remain + 1), alignment);

	size_t manual = 0;
	for (uintptr_t k = offset; k < end; k += alignment) {
	if (space_bitmap.Test(reinterpret_cast<mirror::Object*>(heap_begin + k))) {
	manual++;
	}
	}

	uintptr_t range_begin = reinterpret_cast<uintptr_t>(heap_begin) + offset;
	uintptr_t range_end = reinterpret_cast<uintptr_t>(heap_begin) + end;

	fn(&space_bitmap, range_begin, range_end, manual);
	}
	}
	}

	TYPED_TEST(SpaceBitmapTest, VisitorAlignment) {
	using SpaceBitmap = typename TypeParam::SpaceBitmap;
	auto count_test_fn = [](SpaceBitmap* space_bitmap,
	uintptr_t range_begin,
	uintptr_t range_end,
	size_t manual_count) {
	size_t count = 0;
	auto count_fn = [&count]([[maybe_unused]] mirror::Object* obj) { count++; };
	space_bitmap->VisitMarkedRange(range_begin, range_end, count_fn);
	EXPECT_EQ(count, manual_count);
	};
	RunTest<SpaceBitmap>(TypeParam::GetObjectAlignment(), count_test_fn);
	}

	TYPED_TEST(SpaceBitmapTest, OrderAlignment) {
	using SpaceBitmap = typename TypeParam::SpaceBitmap;
	auto order_test_fn = [](SpaceBitmap* space_bitmap,
	uintptr_t range_begin,
	uintptr_t range_end,
	size_t manual_count)
	REQUIRES_SHARED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
	mirror::Object* last_ptr = nullptr;
	auto order_check = [&last_ptr](mirror::Object* obj) {
	EXPECT_LT(last_ptr, obj);
	last_ptr = obj;
	};

	// Test complete walk.
	space_bitmap->Walk(order_check);
	if (manual_count > 0) {
	EXPECT_NE(nullptr, last_ptr);
	}

	// Test range.
	last_ptr = nullptr;
	space_bitmap->VisitMarkedRange(range_begin, range_end, order_check);
	if (manual_count > 0) {
	EXPECT_NE(nullptr, last_ptr);
	}
	};
	RunTest<SpaceBitmap>(TypeParam::GetObjectAlignment(), order_test_fn);
	}

	} // namespace accounting
	} // namespace gc
	} // namespace art