Rename object_bitmap to heap_bitmap (since that's what the class is called).
Change-Id: Idce6e9062545eb13b701e6b7e371c262977814d1
diff --git a/src/heap_bitmap.cc b/src/heap_bitmap.cc
new file mode 100644
index 0000000..2c3c436
--- /dev/null
+++ b/src/heap_bitmap.cc
@@ -0,0 +1,185 @@
+// 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 "heap_bitmap.h"
+
+#include <sys/mman.h>
+
+#include "UniquePtr.h"
+#include "logging.h"
+#include "utils.h"
+
+namespace art {
+
+HeapBitmap* HeapBitmap::Create(byte* base, size_t length) {
+ UniquePtr<HeapBitmap> bitmap(new HeapBitmap(base, length));
+ if (!bitmap->Init(base, length)) {
+ return NULL;
+ } else {
+ return bitmap.release();
+ }
+}
+
+// Initialize a HeapBitmap so that it points to a bitmap large enough
+// to cover a heap at <base> of <max_size> bytes, where objects are
+// guaranteed to be kAlignment-aligned.
+bool HeapBitmap::Init(const byte* base, size_t max_size) {
+ CHECK(base != NULL);
+ size_t length = HB_OFFSET_TO_INDEX(max_size) * kWordSize;
+ mem_map_.reset(MemMap::Map(length, PROT_READ | PROT_WRITE));
+ if (mem_map_.get() == NULL) {
+ return false;
+ }
+ words_ = reinterpret_cast<word*>(mem_map_->GetAddress());
+ num_bytes_ = length;
+ base_ = reinterpret_cast<uintptr_t>(base);
+ max_ = base_ - 1;
+ return true;
+}
+
+// Clean up any resources associated with the bitmap.
+HeapBitmap::~HeapBitmap() {}
+
+// Fill the bitmap with zeroes. Returns the bitmap's memory to the
+// system as a side-effect.
+void HeapBitmap::Clear() {
+ if (words_ != NULL) {
+ // This returns the memory to the system. Successive page faults
+ // will return zeroed memory.
+ int result = madvise(words_, num_bytes_, MADV_DONTNEED);
+ if (result == -1) {
+ PLOG(WARNING) << "madvise failed";
+ }
+ max_ = base_ - 1;
+ }
+}
+
+// Return true iff <obj> is within the range of pointers that this
+// bitmap could potentially cover, even if a bit has not been set for
+// it.
+bool HeapBitmap::HasAddress(const void* obj) const {
+ if (obj != NULL) {
+ const uintptr_t offset = (uintptr_t)obj - base_;
+ const size_t index = HB_OFFSET_TO_INDEX(offset);
+ return index < num_bytes_ / kWordSize;
+ }
+ return false;
+}
+
+// Visits set bits in address order. The callback is not permitted to
+// change the bitmap bits or max during the traversal.
+void HeapBitmap::Walk(HeapBitmap::Callback* callback, void* arg) {
+ CHECK(words_ != NULL);
+ CHECK(callback != NULL);
+ uintptr_t end = HB_OFFSET_TO_INDEX(max_ - base_);
+ for (uintptr_t i = 0; i <= end; ++i) {
+ word w = words_[i];
+ if (UNLIKELY(w != 0)) {
+ word high_bit = 1 << (kBitsPerWord - 1);
+ uintptr_t ptr_base = HB_INDEX_TO_OFFSET(i) + base_;
+ while (w != 0) {
+ const int shift = CLZ(w);
+ Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment);
+ (*callback)(obj, arg);
+ w &= ~(high_bit >> shift);
+ }
+ }
+ }
+}
+
+// Similar to Walk but the callback routine is permitted to change the
+// bitmap bits and max during traversal. Used by the the root marking
+// scan exclusively.
+//
+// The callback is invoked with a finger argument. The finger is a
+// pointer to an address not yet visited by the traversal. If the
+// callback sets a bit for an address at or above the finger, this
+// address will be visited by the traversal. If the callback sets a
+// bit for an address below the finger, this address will not be
+// visited.
+void HeapBitmap::ScanWalk(uintptr_t base, ScanCallback* callback, void* arg) {
+ DCHECK(words_ != NULL);
+ DCHECK(callback != NULL);
+ DCHECK_GE(base, base_);
+ uintptr_t end = HB_OFFSET_TO_INDEX(max_ - base);
+ for (uintptr_t i = 0; i <= end; ++i) {
+ word w = words_[i];
+ if (UNLIKELY(w != 0)) {
+ word high_bit = 1 << (kBitsPerWord - 1);
+ uintptr_t ptr_base = HB_INDEX_TO_OFFSET(i) + base_;
+ void* finger = reinterpret_cast<void*>(HB_INDEX_TO_OFFSET(i + 1) + base_);
+ while (w != 0) {
+ const int shift = CLZ(w);
+ Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment);
+ (*callback)(obj, finger, arg);
+ w &= ~(high_bit >> shift);
+ }
+ end = HB_OFFSET_TO_INDEX(max_ - base_);
+ }
+ }
+}
+
+// Walk through the bitmaps in increasing address order, and find the
+// object pointers that correspond to garbage objects. Call
+// <callback> zero or more times with lists of these object pointers.
+//
+// The callback is not permitted to increase the max of either bitmap.
+void HeapBitmap::SweepWalk(const HeapBitmap& live_bitmap,
+ const HeapBitmap& mark_bitmap,
+ uintptr_t base, uintptr_t max,
+ HeapBitmap::SweepCallback* callback, void* arg) {
+ CHECK(live_bitmap.words_ != NULL);
+ CHECK(mark_bitmap.words_ != NULL);
+ CHECK_EQ(live_bitmap.base_, mark_bitmap.base_);
+ CHECK_EQ(live_bitmap.num_bytes_, mark_bitmap.num_bytes_);
+ CHECK(callback != NULL);
+ CHECK_LE(base, max);
+ CHECK_GE(base, live_bitmap.base_);
+ max = std::min(max-1, live_bitmap.max_);
+ if (live_bitmap.max_ < live_bitmap.base_) {
+ // Easy case; both are obviously empty.
+ // TODO: this should never happen
+ return;
+ }
+ // TODO: rewrite the callbacks to accept a std::vector<void*> rather than a void**?
+ std::vector<void*> pointer_buf(4 * kBitsPerWord);
+ void** pb = &pointer_buf[0];
+ size_t start = HB_OFFSET_TO_INDEX(base - live_bitmap.base_);
+ size_t end = HB_OFFSET_TO_INDEX(max - live_bitmap.base_);
+ word* live = live_bitmap.words_;
+ word* mark = mark_bitmap.words_;
+ for (size_t i = start; i <= end; i++) {
+ word garbage = live[i] & ~mark[i];
+ if (UNLIKELY(garbage != 0)) {
+ word high_bit = 1 << (kBitsPerWord - 1);
+ uintptr_t ptr_base = HB_INDEX_TO_OFFSET(i) + live_bitmap.base_;
+ while (garbage != 0) {
+ int shift = CLZ(garbage);
+ garbage &= ~(high_bit >> shift);
+ *pb++ = reinterpret_cast<void*>(ptr_base + shift * kAlignment);
+ }
+ // Make sure that there are always enough slots available for an
+ // entire word of one bits.
+ if (pb >= &pointer_buf[pointer_buf.size() - kBitsPerWord]) {
+ (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg);
+ pb = &pointer_buf[0];
+ }
+ }
+ }
+ if (pb > &pointer_buf[0]) {
+ (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg);
+ }
+}
+
+} // namespace art