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

 /*
  * Copyright (C) 2008 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-inl.h"

 #include <iomanip>
 #include <sstream>

 #include "android-base/stringprintf.h"

 #include "art_field-inl.h"
 #include "base/mem_map.h"
 #include "dex/dex_file-inl.h"
 #include "mirror/class-inl.h"
 #include "mirror/object-inl.h"
 #include "mirror/object_array.h"

 namespace art {
 namespace gc {
 namespace accounting {

 using android::base::StringPrintf;

 template<size_t kAlignment>
 size_t SpaceBitmap<kAlignment>::ComputeBitmapSize(uint64_t capacity) {
   // Number of space (heap) bytes covered by one bitmap word.
   // (Word size in bytes = `sizeof(intptr_t)`, which is expected to be
   // 4 on a 32-bit architecture and 8 on a 64-bit one.)
   const uint64_t kBytesCoveredPerWord = kAlignment * kBitsPerIntPtrT;
   // Calculate the number of words required to cover a space (heap)
   // having a size of `capacity` bytes.
   return (RoundUp(capacity, kBytesCoveredPerWord) / kBytesCoveredPerWord) * sizeof(intptr_t);
 }

 template<size_t kAlignment>
 size_t SpaceBitmap<kAlignment>::ComputeHeapSize(uint64_t bitmap_bytes) {
   return bitmap_bytes * kBitsPerByte * kAlignment;
 }

 template<size_t kAlignment>
 SpaceBitmap<kAlignment> SpaceBitmap<kAlignment>::CreateFromMemMap(
     const std::string& name, MemMap&& mem_map, uint8_t* heap_begin, size_t heap_capacity) {
   CHECK(mem_map.IsValid());
   uintptr_t* bitmap_begin = reinterpret_cast<uintptr_t*>(mem_map.Begin());
   const size_t bitmap_size = ComputeBitmapSize(heap_capacity);
   return { name, std::move(mem_map), bitmap_begin, bitmap_size, heap_begin, heap_capacity };
 }

 template<size_t kAlignment>
 SpaceBitmap<kAlignment>::SpaceBitmap(const std::string& name,
                                      MemMap&& mem_map,
                                      uintptr_t* bitmap_begin,
                                      size_t bitmap_size,
                                      const void* heap_begin,
                                      size_t heap_capacity)
     : mem_map_(std::move(mem_map)),
       bitmap_begin_(reinterpret_cast<Atomic<uintptr_t>*>(bitmap_begin)),
       bitmap_size_(bitmap_size),
       heap_begin_(reinterpret_cast<uintptr_t>(heap_begin)),
       heap_limit_(reinterpret_cast<uintptr_t>(heap_begin) + heap_capacity),
       name_(name) {
   CHECK(bitmap_begin_ != nullptr);
   CHECK_NE(bitmap_size, 0U);
 }

 template<size_t kAlignment>
 SpaceBitmap<kAlignment>::~SpaceBitmap() {}

 template<size_t kAlignment>
 SpaceBitmap<kAlignment> SpaceBitmap<kAlignment>::Create(
     const std::string& name, uint8_t* heap_begin, size_t heap_capacity) {
   // Round up since `heap_capacity` is not necessarily a multiple of `kAlignment * kBitsPerIntPtrT`
   // (we represent one word as an `intptr_t`).
   const size_t bitmap_size = ComputeBitmapSize(heap_capacity);
   std::string error_msg;
   MemMap mem_map = MemMap::MapAnonymous(name.c_str(),
                                         bitmap_size,
                                         PROT_READ | PROT_WRITE,
                                         /*low_4gb=*/ false,
                                         &error_msg);
   if (UNLIKELY(!mem_map.IsValid())) {
     LOG(ERROR) << "Failed to allocate bitmap " << name << ": " << error_msg;
     return SpaceBitmap<kAlignment>();
   }
   return CreateFromMemMap(name, std::move(mem_map), heap_begin, heap_capacity);
 }

 template<size_t kAlignment>
 void SpaceBitmap<kAlignment>::SetHeapLimit(uintptr_t new_end) {
   DCHECK_ALIGNED(new_end, kBitsPerIntPtrT * kAlignment);
   size_t new_size = OffsetToIndex(new_end - heap_begin_) * sizeof(intptr_t);
   if (new_size < bitmap_size_) {
     bitmap_size_ = new_size;
   }
   heap_limit_ = new_end;
   // Not sure if doing this trim is necessary, since nothing past the end of the heap capacity
   // should be marked.
 }

 template<size_t kAlignment>
 std::string SpaceBitmap<kAlignment>::Dump() const {
   return StringPrintf("%s: %p-%p", name_.c_str(), reinterpret_cast<void*>(HeapBegin()),
                       reinterpret_cast<void*>(HeapLimit()));
 }

 template <size_t kAlignment>
 std::string SpaceBitmap<kAlignment>::DumpMemAround(mirror::Object* obj) const {
   uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
   DCHECK_GE(addr, heap_begin_);
   DCHECK(HasAddress(obj)) << obj;
   const uintptr_t offset = addr - heap_begin_;
   const size_t index = OffsetToIndex(offset);
   const uintptr_t mask = OffsetToMask(offset);
   size_t num_entries = bitmap_size_ / sizeof(uintptr_t);
   DCHECK_LT(index, num_entries) << " bitmap_size_ = " << bitmap_size_;
   Atomic<uintptr_t>* atomic_entry = &bitmap_begin_[index];
   uintptr_t prev = 0;
   uintptr_t next = 0;
   if (index > 0) {
     prev = (atomic_entry - 1)->load(std::memory_order_relaxed);
   }
   uintptr_t curr = atomic_entry->load(std::memory_order_relaxed);
   if (index < num_entries - 1) {
     next = (atomic_entry + 1)->load(std::memory_order_relaxed);
   }
   std::ostringstream oss;
   oss << " offset: " << offset
       << " index: " << index
       << " mask: " << std::hex << std::setfill('0') << std::setw(16) << mask
       << " words {" << std::hex << std::setfill('0') << std::setw(16) << prev
       << ", " << std::hex << std::setfill('0') << std::setw(16) << curr
       << ", " << std::hex <<std::setfill('0') << std::setw(16) << next
       << "}";
   return oss.str();
 }

 template<size_t kAlignment>
 void SpaceBitmap<kAlignment>::Clear() {
   if (bitmap_begin_ != nullptr) {
     mem_map_.MadviseDontNeedAndZero();
   }
 }

 template<size_t kAlignment>
 void SpaceBitmap<kAlignment>::ClearRange(const mirror::Object* begin, const mirror::Object* end) {
   uintptr_t begin_offset = reinterpret_cast<uintptr_t>(begin) - heap_begin_;
   uintptr_t end_offset = reinterpret_cast<uintptr_t>(end) - heap_begin_;
   // Align begin and end to bitmap word boundaries.
   while (begin_offset < end_offset && OffsetBitIndex(begin_offset) != 0) {
     Clear(reinterpret_cast<mirror::Object*>(heap_begin_ + begin_offset));
     begin_offset += kAlignment;
   }
   while (begin_offset < end_offset && OffsetBitIndex(end_offset) != 0) {
     end_offset -= kAlignment;
     Clear(reinterpret_cast<mirror::Object*>(heap_begin_ + end_offset));
   }
   // Bitmap word boundaries.
   const uintptr_t start_index = OffsetToIndex(begin_offset);
   const uintptr_t end_index = OffsetToIndex(end_offset);
   ZeroAndReleasePages(reinterpret_cast<uint8_t*>(&bitmap_begin_[start_index]),
                       (end_index - start_index) * sizeof(*bitmap_begin_));
 }

 template<size_t kAlignment>
 void SpaceBitmap<kAlignment>::CopyFrom(SpaceBitmap* source_bitmap) {
   DCHECK_EQ(Size(), source_bitmap->Size());
   const size_t count = source_bitmap->Size() / sizeof(intptr_t);
   Atomic<uintptr_t>* const src = source_bitmap->Begin();
   Atomic<uintptr_t>* const dest = Begin();
   for (size_t i = 0; i < count; ++i) {
     dest[i].store(src[i].load(std::memory_order_relaxed), std::memory_order_relaxed);
   }
 }

 template<size_t kAlignment>
 void SpaceBitmap<kAlignment>::SweepWalk(const SpaceBitmap<kAlignment>& live_bitmap,
                                         const SpaceBitmap<kAlignment>& mark_bitmap,
                                         uintptr_t sweep_begin, uintptr_t sweep_end,
                                         SpaceBitmap::SweepCallback* callback, void* arg) {
   CHECK(live_bitmap.bitmap_begin_ != nullptr);
   CHECK(mark_bitmap.bitmap_begin_ != nullptr);
   CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_);
   CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_);
   CHECK(callback != nullptr);
   CHECK_LE(sweep_begin, sweep_end);
   CHECK_GE(sweep_begin, live_bitmap.heap_begin_);

   if (sweep_end <= sweep_begin) {
     return;
   }

   size_t buffer_size = sizeof(intptr_t) * kBitsPerIntPtrT;
   Atomic<uintptr_t>* live = live_bitmap.bitmap_begin_;
   Atomic<uintptr_t>* mark = mark_bitmap.bitmap_begin_;
   const size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_);
   const size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_ - 1);
   CHECK_LT(end, live_bitmap.Size() / sizeof(intptr_t));

   if (Runtime::Current()->IsRunningOnMemoryTool()) {
     // For memory tool, make the buffer large enough to hold all allocations. This is done since
     // we get the size of objects (and hence read the class) inside of the freeing logic. This can
     // cause crashes for unloaded classes since the class may get zeroed out before it is read.
     // See b/131542326
     for (size_t i = start; i <= end; i++) {
       uintptr_t garbage =
           live[i].load(std::memory_order_relaxed) & ~mark[i].load(std::memory_order_relaxed);
       buffer_size += POPCOUNT(garbage);
     }
   }
   std::vector<mirror::Object*> pointer_buf(buffer_size);
   mirror::Object** cur_pointer = &pointer_buf[0];
   mirror::Object** pointer_end = cur_pointer + (buffer_size - kBitsPerIntPtrT);

   for (size_t i = start; i <= end; i++) {
     uintptr_t garbage =
         live[i].load(std::memory_order_relaxed) & ~mark[i].load(std::memory_order_relaxed);
     if (UNLIKELY(garbage != 0)) {
       uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_;
       do {
         const size_t shift = CTZ(garbage);
         garbage ^= (static_cast<uintptr_t>(1)) << shift;
         *cur_pointer++ = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
       } while (garbage != 0);
       // Make sure that there are always enough slots available for an
       // entire word of one bits.
       if (cur_pointer >= pointer_end) {
         (*callback)(cur_pointer - &pointer_buf[0], &pointer_buf[0], arg);
         cur_pointer  = &pointer_buf[0];
       }
     }
   }
   if (cur_pointer > &pointer_buf[0]) {
     (*callback)(cur_pointer - &pointer_buf[0], &pointer_buf[0], arg);
   }
 }

 template class SpaceBitmap<kObjectAlignment>;
 template class SpaceBitmap<kPageSize>;

 }  // namespace accounting
 }  // namespace gc
 }  // namespace art
	/*
	* Copyright (C) 2008 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-inl.h"

	#include <iomanip>
	#include <sstream>

	#include "android-base/stringprintf.h"

	#include "art_field-inl.h"
	#include "base/mem_map.h"
	#include "dex/dex_file-inl.h"
	#include "mirror/class-inl.h"
	#include "mirror/object-inl.h"
	#include "mirror/object_array.h"

	namespace art {
	namespace gc {
	namespace accounting {

	using android::base::StringPrintf;

	template<size_t kAlignment>
	size_t SpaceBitmap<kAlignment>::ComputeBitmapSize(uint64_t capacity) {
	// Number of space (heap) bytes covered by one bitmap word.
	// (Word size in bytes = `sizeof(intptr_t)`, which is expected to be
	// 4 on a 32-bit architecture and 8 on a 64-bit one.)
	const uint64_t kBytesCoveredPerWord = kAlignment * kBitsPerIntPtrT;
	// Calculate the number of words required to cover a space (heap)
	// having a size of `capacity` bytes.
	return (RoundUp(capacity, kBytesCoveredPerWord) / kBytesCoveredPerWord) * sizeof(intptr_t);
	}

	template<size_t kAlignment>
	size_t SpaceBitmap<kAlignment>::ComputeHeapSize(uint64_t bitmap_bytes) {
	return bitmap_bytes * kBitsPerByte * kAlignment;
	}

	template<size_t kAlignment>
	SpaceBitmap<kAlignment> SpaceBitmap<kAlignment>::CreateFromMemMap(
	const std::string& name, MemMap&& mem_map, uint8_t* heap_begin, size_t heap_capacity) {
	CHECK(mem_map.IsValid());
	uintptr_t* bitmap_begin = reinterpret_cast<uintptr_t*>(mem_map.Begin());
	const size_t bitmap_size = ComputeBitmapSize(heap_capacity);
	return { name, std::move(mem_map), bitmap_begin, bitmap_size, heap_begin, heap_capacity };
	}

	template<size_t kAlignment>
	SpaceBitmap<kAlignment>::SpaceBitmap(const std::string& name,
	MemMap&& mem_map,
	uintptr_t* bitmap_begin,
	size_t bitmap_size,
	const void* heap_begin,
	size_t heap_capacity)
	: mem_map_(std::move(mem_map)),
	bitmap_begin_(reinterpret_cast<Atomic<uintptr_t>*>(bitmap_begin)),
	bitmap_size_(bitmap_size),
	heap_begin_(reinterpret_cast<uintptr_t>(heap_begin)),
	heap_limit_(reinterpret_cast<uintptr_t>(heap_begin) + heap_capacity),
	name_(name) {
	CHECK(bitmap_begin_ != nullptr);
	CHECK_NE(bitmap_size, 0U);
	}

	template<size_t kAlignment>
	SpaceBitmap<kAlignment>::~SpaceBitmap() {}

	template<size_t kAlignment>
	SpaceBitmap<kAlignment> SpaceBitmap<kAlignment>::Create(
	const std::string& name, uint8_t* heap_begin, size_t heap_capacity) {
	// Round up since `heap_capacity` is not necessarily a multiple of `kAlignment * kBitsPerIntPtrT`
	// (we represent one word as an `intptr_t`).
	const size_t bitmap_size = ComputeBitmapSize(heap_capacity);
	std::string error_msg;
	MemMap mem_map = MemMap::MapAnonymous(name.c_str(),
	bitmap_size,
	PROT_READ \| PROT_WRITE,
	/low_4gb=/ false,
	&error_msg);
	if (UNLIKELY(!mem_map.IsValid())) {
	LOG(ERROR) << "Failed to allocate bitmap " << name << ": " << error_msg;
	return SpaceBitmap<kAlignment>();
	}
	return CreateFromMemMap(name, std::move(mem_map), heap_begin, heap_capacity);
	}

	template<size_t kAlignment>
	void SpaceBitmap<kAlignment>::SetHeapLimit(uintptr_t new_end) {
	DCHECK_ALIGNED(new_end, kBitsPerIntPtrT * kAlignment);
	size_t new_size = OffsetToIndex(new_end - heap_begin_) * sizeof(intptr_t);
	if (new_size < bitmap_size_) {
	bitmap_size_ = new_size;
	}
	heap_limit_ = new_end;
	// Not sure if doing this trim is necessary, since nothing past the end of the heap capacity
	// should be marked.
	}

	template<size_t kAlignment>
	std::string SpaceBitmap<kAlignment>::Dump() const {
	return StringPrintf("%s: %p-%p", name_.c_str(), reinterpret_cast<void*>(HeapBegin()),
	reinterpret_cast<void*>(HeapLimit()));
	}

	template <size_t kAlignment>
	std::string SpaceBitmap<kAlignment>::DumpMemAround(mirror::Object* obj) const {
	uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
	DCHECK_GE(addr, heap_begin_);
	DCHECK(HasAddress(obj)) << obj;
	const uintptr_t offset = addr - heap_begin_;
	const size_t index = OffsetToIndex(offset);
	const uintptr_t mask = OffsetToMask(offset);
	size_t num_entries = bitmap_size_ / sizeof(uintptr_t);
	DCHECK_LT(index, num_entries) << " bitmap_size_ = " << bitmap_size_;
	Atomic<uintptr_t>* atomic_entry = &bitmap_begin_[index];
	uintptr_t prev = 0;
	uintptr_t next = 0;
	if (index > 0) {
	prev = (atomic_entry - 1)->load(std::memory_order_relaxed);
	}
	uintptr_t curr = atomic_entry->load(std::memory_order_relaxed);
	if (index < num_entries - 1) {
	next = (atomic_entry + 1)->load(std::memory_order_relaxed);
	}
	std::ostringstream oss;
	oss << " offset: " << offset
	<< " index: " << index
	<< " mask: " << std::hex << std::setfill('0') << std::setw(16) << mask
	<< " words {" << std::hex << std::setfill('0') << std::setw(16) << prev
	<< ", " << std::hex << std::setfill('0') << std::setw(16) << curr
	<< ", " << std::hex <<std::setfill('0') << std::setw(16) << next
	<< "}";
	return oss.str();
	}

	template<size_t kAlignment>
	void SpaceBitmap<kAlignment>::Clear() {
	if (bitmap_begin_ != nullptr) {
	mem_map_.MadviseDontNeedAndZero();
	}
	}

	template<size_t kAlignment>
	void SpaceBitmap<kAlignment>::ClearRange(const mirror::Object* begin, const mirror::Object* end) {
	uintptr_t begin_offset = reinterpret_cast<uintptr_t>(begin) - heap_begin_;
	uintptr_t end_offset = reinterpret_cast<uintptr_t>(end) - heap_begin_;
	// Align begin and end to bitmap word boundaries.
	while (begin_offset < end_offset && OffsetBitIndex(begin_offset) != 0) {
	Clear(reinterpret_cast<mirror::Object*>(heap_begin_ + begin_offset));
	begin_offset += kAlignment;
	}
	while (begin_offset < end_offset && OffsetBitIndex(end_offset) != 0) {
	end_offset -= kAlignment;
	Clear(reinterpret_cast<mirror::Object*>(heap_begin_ + end_offset));
	}
	// Bitmap word boundaries.
	const uintptr_t start_index = OffsetToIndex(begin_offset);
	const uintptr_t end_index = OffsetToIndex(end_offset);
	ZeroAndReleasePages(reinterpret_cast<uint8_t*>(&bitmap_begin_[start_index]),
	(end_index - start_index) * sizeof(*bitmap_begin_));
	}

	template<size_t kAlignment>
	void SpaceBitmap<kAlignment>::CopyFrom(SpaceBitmap* source_bitmap) {
	DCHECK_EQ(Size(), source_bitmap->Size());
	const size_t count = source_bitmap->Size() / sizeof(intptr_t);
	Atomic<uintptr_t>* const src = source_bitmap->Begin();
	Atomic<uintptr_t>* const dest = Begin();
	for (size_t i = 0; i < count; ++i) {
	dest[i].store(src[i].load(std::memory_order_relaxed), std::memory_order_relaxed);
	}
	}

	template<size_t kAlignment>
	void SpaceBitmap<kAlignment>::SweepWalk(const SpaceBitmap<kAlignment>& live_bitmap,
	const SpaceBitmap<kAlignment>& mark_bitmap,
	uintptr_t sweep_begin, uintptr_t sweep_end,
	SpaceBitmap::SweepCallback* callback, void* arg) {
	CHECK(live_bitmap.bitmap_begin_ != nullptr);
	CHECK(mark_bitmap.bitmap_begin_ != nullptr);
	CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_);
	CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_);
	CHECK(callback != nullptr);
	CHECK_LE(sweep_begin, sweep_end);
	CHECK_GE(sweep_begin, live_bitmap.heap_begin_);

	if (sweep_end <= sweep_begin) {
	return;
	}

	size_t buffer_size = sizeof(intptr_t) * kBitsPerIntPtrT;
	Atomic<uintptr_t>* live = live_bitmap.bitmap_begin_;
	Atomic<uintptr_t>* mark = mark_bitmap.bitmap_begin_;
	const size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_);
	const size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_ - 1);
	CHECK_LT(end, live_bitmap.Size() / sizeof(intptr_t));

	if (Runtime::Current()->IsRunningOnMemoryTool()) {
	// For memory tool, make the buffer large enough to hold all allocations. This is done since
	// we get the size of objects (and hence read the class) inside of the freeing logic. This can
	// cause crashes for unloaded classes since the class may get zeroed out before it is read.
	// See b/131542326
	for (size_t i = start; i <= end; i++) {
	uintptr_t garbage =
	live[i].load(std::memory_order_relaxed) & ~mark[i].load(std::memory_order_relaxed);
	buffer_size += POPCOUNT(garbage);
	}
	}
	std::vector<mirror::Object*> pointer_buf(buffer_size);
	mirror::Object** cur_pointer = &pointer_buf[0];
	mirror::Object** pointer_end = cur_pointer + (buffer_size - kBitsPerIntPtrT);

	for (size_t i = start; i <= end; i++) {
	uintptr_t garbage =
	live[i].load(std::memory_order_relaxed) & ~mark[i].load(std::memory_order_relaxed);
	if (UNLIKELY(garbage != 0)) {
	uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_;
	do {
	const size_t shift = CTZ(garbage);
	garbage ^= (static_cast<uintptr_t>(1)) << shift;
	cur_pointer++ = reinterpret_cast<mirror::Object>(ptr_base + shift * kAlignment);
	} while (garbage != 0);
	// Make sure that there are always enough slots available for an
	// entire word of one bits.
	if (cur_pointer >= pointer_end) {
	(*callback)(cur_pointer - &pointer_buf[0], &pointer_buf[0], arg);
	cur_pointer = &pointer_buf[0];
	}
	}
	}
	if (cur_pointer > &pointer_buf[0]) {
	(*callback)(cur_pointer - &pointer_buf[0], &pointer_buf[0], arg);
	}
	}

	template class SpaceBitmap<kObjectAlignment>;
	template class SpaceBitmap<kPageSize>;

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