runtime/gc/accounting/space_bitmap-inl.h - platform/art - Git at Google

 /*
  * 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.
  */

 #ifndef ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_
 #define ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_

 #include "space_bitmap.h"

 #include <memory>

 #include <android-base/logging.h>

 #include "base/atomic.h"
 #include "base/bit_utils.h"

 namespace art {
 namespace gc {
 namespace accounting {

 template<size_t kAlignment>
 inline bool SpaceBitmap<kAlignment>::AtomicTestAndSet(const mirror::Object* obj) {
   uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
   DCHECK_GE(addr, heap_begin_);
   const uintptr_t offset = addr - heap_begin_;
   const size_t index = OffsetToIndex(offset);
   const uintptr_t mask = OffsetToMask(offset);
   Atomic<uintptr_t>* atomic_entry = &bitmap_begin_[index];
   DCHECK_LT(index, bitmap_size_ / sizeof(intptr_t)) << " bitmap_size_ = " << bitmap_size_;
   uintptr_t old_word;
   do {
     old_word = atomic_entry->load(std::memory_order_relaxed);
     // Fast path: The bit is already set.
     if ((old_word & mask) != 0) {
       DCHECK(Test(obj));
       return true;
     }
   } while (!atomic_entry->CompareAndSetWeakRelaxed(old_word, old_word | mask));
   DCHECK(Test(obj));
   return false;
 }

 template<size_t kAlignment>
 inline bool SpaceBitmap<kAlignment>::Test(const mirror::Object* obj) const {
   uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
   DCHECK(HasAddress(obj)) << obj;
   DCHECK(bitmap_begin_ != nullptr);
   DCHECK_GE(addr, heap_begin_);
   const uintptr_t offset = addr - heap_begin_;
   size_t index = OffsetToIndex(offset);
   return (bitmap_begin_[index].load(std::memory_order_relaxed) & OffsetToMask(offset)) != 0;
 }

 template<size_t kAlignment>
 inline mirror::Object* SpaceBitmap<kAlignment>::FindPrecedingObject(uintptr_t visit_begin,
                                                                     uintptr_t visit_end) const {
   // Covers [visit_end, visit_begin].
   visit_end = std::max(heap_begin_, visit_end);
   DCHECK_LE(visit_end, visit_begin);
   DCHECK_LT(visit_begin, HeapLimit());

   const uintptr_t offset_start = visit_begin - heap_begin_;
   const uintptr_t offset_end = visit_end - heap_begin_;
   uintptr_t index_start = OffsetToIndex(offset_start);
   const uintptr_t index_end = OffsetToIndex(offset_end);

   // Start with the right edge
   uintptr_t word = bitmap_begin_[index_start].load(std::memory_order_relaxed);
   // visit_begin could be the first word of the object we are looking for.
   const uintptr_t right_edge_mask = OffsetToMask(offset_start);
   word &= right_edge_mask | (right_edge_mask - 1);
   while (index_start > index_end) {
     if (word != 0) {
       const uintptr_t ptr_base = IndexToOffset(index_start) + heap_begin_;
       size_t pos_leading_set_bit = kBitsPerIntPtrT - CLZ(word) - 1;
       return reinterpret_cast<mirror::Object*>(ptr_base + pos_leading_set_bit * kAlignment);
     }
     word = bitmap_begin_[--index_start].load(std::memory_order_relaxed);
   }

   word &= ~(OffsetToMask(offset_end) - 1);
   if (word != 0) {
     const uintptr_t ptr_base = IndexToOffset(index_end) + heap_begin_;
     size_t pos_leading_set_bit = kBitsPerIntPtrT - CLZ(word) - 1;
     return reinterpret_cast<mirror::Object*>(ptr_base + pos_leading_set_bit * kAlignment);
   } else {
     return nullptr;
   }
 }

 template<size_t kAlignment>
 template<bool kVisitOnce, typename Visitor>
 inline void SpaceBitmap<kAlignment>::VisitMarkedRange(uintptr_t visit_begin,
                                                       uintptr_t visit_end,
                                                       Visitor&& visitor) const {
   DCHECK_LE(visit_begin, visit_end);
 #if 0
   for (uintptr_t i = visit_begin; i < visit_end; i += kAlignment) {
     mirror::Object* obj = reinterpret_cast<mirror::Object*>(i);
     if (Test(obj)) {
       visitor(obj);
     }
   }
 #else
   DCHECK_LE(heap_begin_, visit_begin);
   DCHECK_LE(visit_end, HeapLimit());

   const uintptr_t offset_start = visit_begin - heap_begin_;
   const uintptr_t offset_end = visit_end - heap_begin_;

   const uintptr_t index_start = OffsetToIndex(offset_start);
   const uintptr_t index_end = OffsetToIndex(offset_end);

   const size_t bit_start = (offset_start / kAlignment) % kBitsPerIntPtrT;
   const size_t bit_end = (offset_end / kAlignment) % kBitsPerIntPtrT;

   // Index(begin)  ...    Index(end)
   // [xxxxx???][........][????yyyy]
   //      ^                   ^
   //      |                   #---- Bit of visit_end
   //      #---- Bit of visit_begin
   //

   // Left edge.
   uintptr_t left_edge = bitmap_begin_[index_start];
   // Mark of lower bits that are not in range.
   left_edge &= ~((static_cast<uintptr_t>(1) << bit_start) - 1);

   // Right edge. Either unique, or left_edge.
   uintptr_t right_edge;

   if (index_start < index_end) {
     // Left edge != right edge.

     // Traverse left edge.
     if (left_edge != 0) {
       const uintptr_t ptr_base = IndexToOffset(index_start) + heap_begin_;
       do {
         const size_t shift = CTZ(left_edge);
         mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
         visitor(obj);
         if (kVisitOnce) {
           return;
         }
         left_edge ^= (static_cast<uintptr_t>(1)) << shift;
       } while (left_edge != 0);
     }

     // Traverse the middle, full part.
     for (size_t i = index_start + 1; i < index_end; ++i) {
       uintptr_t w = bitmap_begin_[i].load(std::memory_order_relaxed);
       if (w != 0) {
         const uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
         // Iterate on the bits set in word `w`, from the least to the most significant bit.
         do {
           const size_t shift = CTZ(w);
           mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
           visitor(obj);
           if (kVisitOnce) {
             return;
           }
           w ^= (static_cast<uintptr_t>(1)) << shift;
         } while (w != 0);
       }
     }

     // Right edge is unique.
     // But maybe we don't have anything to do: visit_end starts in a new word...
     if (bit_end == 0) {
       // Do not read memory, as it could be after the end of the bitmap.
       right_edge = 0;
     } else {
       right_edge = bitmap_begin_[index_end];
     }
   } else {
     // Right edge = left edge.
     right_edge = left_edge;
   }

   // Right edge handling.
   right_edge &= ((static_cast<uintptr_t>(1) << bit_end) - 1);
   if (right_edge != 0) {
     const uintptr_t ptr_base = IndexToOffset(index_end) + heap_begin_;
     // Iterate on the bits set in word `right_edge`, from the least to the most significant bit.
     do {
       const size_t shift = CTZ(right_edge);
       mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
       visitor(obj);
       if (kVisitOnce) {
         return;
       }
       right_edge ^= (static_cast<uintptr_t>(1)) << shift;
     } while (right_edge != 0);
   }
 #endif
 }

 template<size_t kAlignment>
 template<typename Visitor>
 void SpaceBitmap<kAlignment>::Walk(Visitor&& visitor) {
   CHECK(bitmap_begin_ != nullptr);

   uintptr_t end = OffsetToIndex(HeapLimit() - heap_begin_ - 1);
   Atomic<uintptr_t>* bitmap_begin = bitmap_begin_;
   for (uintptr_t i = 0; i <= end; ++i) {
     uintptr_t w = bitmap_begin[i].load(std::memory_order_relaxed);
     if (w != 0) {
       uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
       do {
         const size_t shift = CTZ(w);
         mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
         visitor(obj);
         w ^= (static_cast<uintptr_t>(1)) << shift;
       } while (w != 0);
     }
   }
 }

 template<size_t kAlignment>
 template<bool kSetBit>
 inline bool SpaceBitmap<kAlignment>::Modify(const mirror::Object* obj) {
   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);
   DCHECK_LT(index, bitmap_size_ / sizeof(intptr_t)) << " bitmap_size_ = " << bitmap_size_;
   Atomic<uintptr_t>* atomic_entry = &bitmap_begin_[index];
   uintptr_t old_word = atomic_entry->load(std::memory_order_relaxed);
   if (kSetBit) {
     // Check the bit before setting the word incase we are trying to mark a read only bitmap
     // like an image space bitmap. This bitmap is mapped as read only and will fault if we
     // attempt to change any words. Since all of the objects are marked, this will never
     // occur if we check before setting the bit. This also prevents dirty pages that would
     // occur if the bitmap was read write and we did not check the bit.
     if ((old_word & mask) == 0) {
       atomic_entry->store(old_word | mask, std::memory_order_relaxed);
     }
   } else {
     atomic_entry->store(old_word & ~mask, std::memory_order_relaxed);
   }
   DCHECK_EQ(Test(obj), kSetBit);
   return (old_word & mask) != 0;
 }

 template<size_t kAlignment>
 inline std::ostream& operator << (std::ostream& stream, const SpaceBitmap<kAlignment>& bitmap) {
   return stream
     << bitmap.GetName() << "["
     << "begin=" << reinterpret_cast<const void*>(bitmap.HeapBegin())
     << ",end=" << reinterpret_cast<const void*>(bitmap.HeapLimit())
     << "]";
 }

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

 #endif  // ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_
	/*
	* 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.
	*/

	#ifndef ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_
	#define ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_

	#include "space_bitmap.h"

	#include <memory>

	#include <android-base/logging.h>

	#include "base/atomic.h"
	#include "base/bit_utils.h"

	namespace art {
	namespace gc {
	namespace accounting {

	template<size_t kAlignment>
	inline bool SpaceBitmap<kAlignment>::AtomicTestAndSet(const mirror::Object* obj) {
	uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
	DCHECK_GE(addr, heap_begin_);
	const uintptr_t offset = addr - heap_begin_;
	const size_t index = OffsetToIndex(offset);
	const uintptr_t mask = OffsetToMask(offset);
	Atomic<uintptr_t>* atomic_entry = &bitmap_begin_[index];
	DCHECK_LT(index, bitmap_size_ / sizeof(intptr_t)) << " bitmap_size_ = " << bitmap_size_;
	uintptr_t old_word;
	do {
	old_word = atomic_entry->load(std::memory_order_relaxed);
	// Fast path: The bit is already set.
	if ((old_word & mask) != 0) {
	DCHECK(Test(obj));
	return true;
	}
	} while (!atomic_entry->CompareAndSetWeakRelaxed(old_word, old_word \| mask));
	DCHECK(Test(obj));
	return false;
	}

	template<size_t kAlignment>
	inline bool SpaceBitmap<kAlignment>::Test(const mirror::Object* obj) const {
	uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
	DCHECK(HasAddress(obj)) << obj;
	DCHECK(bitmap_begin_ != nullptr);
	DCHECK_GE(addr, heap_begin_);
	const uintptr_t offset = addr - heap_begin_;
	size_t index = OffsetToIndex(offset);
	return (bitmap_begin_[index].load(std::memory_order_relaxed) & OffsetToMask(offset)) != 0;
	}

	template<size_t kAlignment>
	inline mirror::Object* SpaceBitmap<kAlignment>::FindPrecedingObject(uintptr_t visit_begin,
	uintptr_t visit_end) const {
	// Covers [visit_end, visit_begin].
	visit_end = std::max(heap_begin_, visit_end);
	DCHECK_LE(visit_end, visit_begin);
	DCHECK_LT(visit_begin, HeapLimit());

	const uintptr_t offset_start = visit_begin - heap_begin_;
	const uintptr_t offset_end = visit_end - heap_begin_;
	uintptr_t index_start = OffsetToIndex(offset_start);
	const uintptr_t index_end = OffsetToIndex(offset_end);

	// Start with the right edge
	uintptr_t word = bitmap_begin_[index_start].load(std::memory_order_relaxed);
	// visit_begin could be the first word of the object we are looking for.
	const uintptr_t right_edge_mask = OffsetToMask(offset_start);
	word &= right_edge_mask \| (right_edge_mask - 1);
	while (index_start > index_end) {
	if (word != 0) {
	const uintptr_t ptr_base = IndexToOffset(index_start) + heap_begin_;
	size_t pos_leading_set_bit = kBitsPerIntPtrT - CLZ(word) - 1;
	return reinterpret_cast<mirror::Object>(ptr_base + pos_leading_set_bit kAlignment);
	}
	word = bitmap_begin_[--index_start].load(std::memory_order_relaxed);
	}

	word &= ~(OffsetToMask(offset_end) - 1);
	if (word != 0) {
	const uintptr_t ptr_base = IndexToOffset(index_end) + heap_begin_;
	size_t pos_leading_set_bit = kBitsPerIntPtrT - CLZ(word) - 1;
	return reinterpret_cast<mirror::Object>(ptr_base + pos_leading_set_bit kAlignment);
	} else {
	return nullptr;
	}
	}

	template<size_t kAlignment>
	template<bool kVisitOnce, typename Visitor>
	inline void SpaceBitmap<kAlignment>::VisitMarkedRange(uintptr_t visit_begin,
	uintptr_t visit_end,
	Visitor&& visitor) const {
	DCHECK_LE(visit_begin, visit_end);
	#if 0
	for (uintptr_t i = visit_begin; i < visit_end; i += kAlignment) {
	mirror::Object* obj = reinterpret_cast<mirror::Object*>(i);
	if (Test(obj)) {
	visitor(obj);
	}
	}
	#else
	DCHECK_LE(heap_begin_, visit_begin);
	DCHECK_LE(visit_end, HeapLimit());

	const uintptr_t offset_start = visit_begin - heap_begin_;
	const uintptr_t offset_end = visit_end - heap_begin_;

	const uintptr_t index_start = OffsetToIndex(offset_start);
	const uintptr_t index_end = OffsetToIndex(offset_end);

	const size_t bit_start = (offset_start / kAlignment) % kBitsPerIntPtrT;
	const size_t bit_end = (offset_end / kAlignment) % kBitsPerIntPtrT;

	// Index(begin) ... Index(end)
	// [xxxxx???][........][????yyyy]
	// ^ ^
	// \| #---- Bit of visit_end
	// #---- Bit of visit_begin
	//

	// Left edge.
	uintptr_t left_edge = bitmap_begin_[index_start];
	// Mark of lower bits that are not in range.
	left_edge &= ~((static_cast<uintptr_t>(1) << bit_start) - 1);

	// Right edge. Either unique, or left_edge.
	uintptr_t right_edge;

	if (index_start < index_end) {
	// Left edge != right edge.

	// Traverse left edge.
	if (left_edge != 0) {
	const uintptr_t ptr_base = IndexToOffset(index_start) + heap_begin_;
	do {
	const size_t shift = CTZ(left_edge);
	mirror::Object* obj = reinterpret_cast<mirror::Object>(ptr_base + shift kAlignment);
	visitor(obj);
	if (kVisitOnce) {
	return;
	}
	left_edge ^= (static_cast<uintptr_t>(1)) << shift;
	} while (left_edge != 0);
	}

	// Traverse the middle, full part.
	for (size_t i = index_start + 1; i < index_end; ++i) {
	uintptr_t w = bitmap_begin_[i].load(std::memory_order_relaxed);
	if (w != 0) {
	const uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
	// Iterate on the bits set in word `w`, from the least to the most significant bit.
	do {
	const size_t shift = CTZ(w);
	mirror::Object* obj = reinterpret_cast<mirror::Object>(ptr_base + shift kAlignment);
	visitor(obj);
	if (kVisitOnce) {
	return;
	}
	w ^= (static_cast<uintptr_t>(1)) << shift;
	} while (w != 0);
	}
	}

	// Right edge is unique.
	// But maybe we don't have anything to do: visit_end starts in a new word...
	if (bit_end == 0) {
	// Do not read memory, as it could be after the end of the bitmap.
	right_edge = 0;
	} else {
	right_edge = bitmap_begin_[index_end];
	}
	} else {
	// Right edge = left edge.
	right_edge = left_edge;
	}

	// Right edge handling.
	right_edge &= ((static_cast<uintptr_t>(1) << bit_end) - 1);
	if (right_edge != 0) {
	const uintptr_t ptr_base = IndexToOffset(index_end) + heap_begin_;
	// Iterate on the bits set in word `right_edge`, from the least to the most significant bit.
	do {
	const size_t shift = CTZ(right_edge);
	mirror::Object* obj = reinterpret_cast<mirror::Object>(ptr_base + shift kAlignment);
	visitor(obj);
	if (kVisitOnce) {
	return;
	}
	right_edge ^= (static_cast<uintptr_t>(1)) << shift;
	} while (right_edge != 0);
	}
	#endif
	}

	template<size_t kAlignment>
	template<typename Visitor>
	void SpaceBitmap<kAlignment>::Walk(Visitor&& visitor) {
	CHECK(bitmap_begin_ != nullptr);

	uintptr_t end = OffsetToIndex(HeapLimit() - heap_begin_ - 1);
	Atomic<uintptr_t>* bitmap_begin = bitmap_begin_;
	for (uintptr_t i = 0; i <= end; ++i) {
	uintptr_t w = bitmap_begin[i].load(std::memory_order_relaxed);
	if (w != 0) {
	uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
	do {
	const size_t shift = CTZ(w);
	mirror::Object* obj = reinterpret_cast<mirror::Object>(ptr_base + shift kAlignment);
	visitor(obj);
	w ^= (static_cast<uintptr_t>(1)) << shift;
	} while (w != 0);
	}
	}
	}

	template<size_t kAlignment>
	template<bool kSetBit>
	inline bool SpaceBitmap<kAlignment>::Modify(const mirror::Object* obj) {
	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);
	DCHECK_LT(index, bitmap_size_ / sizeof(intptr_t)) << " bitmap_size_ = " << bitmap_size_;
	Atomic<uintptr_t>* atomic_entry = &bitmap_begin_[index];
	uintptr_t old_word = atomic_entry->load(std::memory_order_relaxed);
	if (kSetBit) {
	// Check the bit before setting the word incase we are trying to mark a read only bitmap
	// like an image space bitmap. This bitmap is mapped as read only and will fault if we
	// attempt to change any words. Since all of the objects are marked, this will never
	// occur if we check before setting the bit. This also prevents dirty pages that would
	// occur if the bitmap was read write and we did not check the bit.
	if ((old_word & mask) == 0) {
	atomic_entry->store(old_word \| mask, std::memory_order_relaxed);
	}
	} else {
	atomic_entry->store(old_word & ~mask, std::memory_order_relaxed);
	}
	DCHECK_EQ(Test(obj), kSetBit);
	return (old_word & mask) != 0;
	}

	template<size_t kAlignment>
	inline std::ostream& operator << (std::ostream& stream, const SpaceBitmap<kAlignment>& bitmap) {
	return stream
	<< bitmap.GetName() << "["
	<< "begin=" << reinterpret_cast<const void*>(bitmap.HeapBegin())
	<< ",end=" << reinterpret_cast<const void*>(bitmap.HeapLimit())
	<< "]";
	}

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

	#endif // ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_