Each space has its own bitmap(s)
Each alloc space now has One mark+live bitmap. Each image space has only one live bitmap.
Change-Id: I2e919d1bd7d9f4d35d0e95ed83a58df6f754df6e
diff --git a/src/space_bitmap.cc b/src/space_bitmap.cc
new file mode 100644
index 0000000..28dee45
--- /dev/null
+++ b/src/space_bitmap.cc
@@ -0,0 +1,311 @@
+/*
+ * 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 "logging.h"
+#include "UniquePtr.h"
+#include "utils.h"
+
+namespace art {
+
+SpaceBitmap* SpaceBitmap::Create(const std::string& name, byte* heap_begin, size_t heap_capacity) {
+ CHECK(heap_begin != NULL);
+ // Round up since heap_capacity is not necessarily a multiple of kAlignment * kBitsPerWord.
+ size_t bitmap_size = OffsetToIndex(RoundUp(heap_capacity, kAlignment * kBitsPerWord)) * kWordSize;
+ UniquePtr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), NULL, bitmap_size, PROT_READ | PROT_WRITE));
+ if (mem_map.get() == NULL) {
+ LOG(ERROR) << "Failed to allocate bitmap " << name;
+ return NULL;
+ }
+ word* bitmap_begin = reinterpret_cast<word*>(mem_map->Begin());
+ return new SpaceBitmap(name, mem_map.release(), bitmap_begin, bitmap_size, heap_begin);
+}
+
+// Clean up any resources associated with the bitmap.
+SpaceBitmap::~SpaceBitmap() {}
+
+// Fill the bitmap with zeroes. Returns the bitmap's memory to the
+// system as a side-effect.
+void SpaceBitmap::Clear() {
+ if (bitmap_begin_ != NULL) {
+ // This returns the memory to the system. Successive page faults
+ // will return zeroed memory.
+ int result = madvise(bitmap_begin_, bitmap_size_, MADV_DONTNEED);
+ if (result == -1) {
+ PLOG(WARNING) << "madvise failed";
+ }
+ heap_end_ = heap_begin_ - 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 SpaceBitmap::HasAddress(const void* obj) const {
+ // If obj < heap_begin_ then offset underflows to some very large value past the end of the bitmap.
+ const uintptr_t offset = (uintptr_t)obj - heap_begin_;
+ const size_t index = OffsetToIndex(offset);
+ return index < bitmap_size_ / kWordSize;
+}
+
+void SpaceBitmap::VisitRange(uintptr_t visit_begin, uintptr_t visit_end, Callback* visitor, void* arg) const {
+ size_t start = OffsetToIndex(visit_begin - heap_begin_);
+ size_t end = OffsetToIndex(visit_end - heap_begin_ - 1);
+ for (size_t i = start; i <= end; i++) {
+ word w = bitmap_begin_[i];
+ if (w != 0) {
+ word high_bit = 1 << (kBitsPerWord - 1);
+ uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
+ while (w != 0) {
+ const int shift = CLZ(w);
+ Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment);
+ (*visitor)(obj, arg);
+ w &= ~(high_bit >> shift);
+ }
+ }
+ }
+}
+
+// Visits set bits in address order. The callback is not permitted to
+// change the bitmap bits or max during the traversal.
+void SpaceBitmap::Walk(SpaceBitmap::Callback* callback, void* arg) {
+ CHECK(bitmap_begin_ != NULL);
+ CHECK(callback != NULL);
+ if (heap_end_ < heap_begin_) {
+ return; // Bitmap is empty.
+ }
+ uintptr_t end = OffsetToIndex(heap_end_ - heap_begin_);
+ for (uintptr_t i = 0; i <= end; ++i) {
+ word w = bitmap_begin_[i];
+ if (UNLIKELY(w != 0)) {
+ word high_bit = 1 << (kBitsPerWord - 1);
+ uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
+ 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 end 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 (typiscally such an address would be placed on the
+// marking stack).
+void SpaceBitmap::ScanWalk(uintptr_t scan_begin, uintptr_t scan_end, ScanCallback* callback, void* arg) {
+ CHECK(bitmap_begin_ != NULL);
+ CHECK(callback != NULL);
+ CHECK_LE(scan_begin, scan_end);
+ CHECK_GE(scan_begin, heap_begin_);
+ size_t start = OffsetToIndex(scan_begin - heap_begin_);
+ if (scan_end < heap_end_) {
+ // The end of the space we're looking at is before the current maximum bitmap PC, scan to that
+ // and don't recompute end on each iteration
+ size_t end = OffsetToIndex(scan_end - heap_begin_ - 1);
+ for (size_t i = start; i <= end; i++) {
+ word w = bitmap_begin_[i];
+ if (UNLIKELY(w != 0)) {
+ word high_bit = 1 << (kBitsPerWord - 1);
+ uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
+ void* finger = reinterpret_cast<void*>(IndexToOffset(i + 1) + heap_begin_);
+ 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);
+ }
+ }
+ }
+ } else {
+ size_t end = OffsetToIndex(heap_end_ - heap_begin_);
+ for (size_t i = start; i <= end; i++) {
+ word w = bitmap_begin_[i];
+ if (UNLIKELY(w != 0)) {
+ word high_bit = 1 << (kBitsPerWord - 1);
+ uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
+ void* finger = reinterpret_cast<void*>(IndexToOffset(i + 1) + heap_begin_);
+ 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);
+ }
+ }
+ // update 'end' in case callback modified bitmap
+ end = OffsetToIndex(heap_end_ - heap_begin_);
+ }
+ }
+}
+
+// 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 SpaceBitmap::SweepWalk(const SpaceBitmap& live_bitmap,
+ const SpaceBitmap& mark_bitmap,
+ uintptr_t sweep_begin, uintptr_t sweep_end,
+ SpaceBitmap::SweepCallback* callback, void* arg) {
+ CHECK(live_bitmap.bitmap_begin_ != NULL);
+ CHECK(mark_bitmap.bitmap_begin_ != NULL);
+ CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_);
+ CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_);
+ CHECK(callback != NULL);
+ CHECK_LE(sweep_begin, sweep_end);
+ CHECK_GE(sweep_begin, live_bitmap.heap_begin_);
+ sweep_end = std::min(sweep_end - 1, live_bitmap.heap_end_);
+ if (live_bitmap.heap_end_ < live_bitmap.heap_begin_) {
+ // Easy case; both are obviously empty.
+ // TODO: this should never happen
+ return;
+ }
+ // TODO: rewrite the callbacks to accept a std::vector<Object*> rather than a Object**?
+ std::vector<Object*> pointer_buf(4 * kBitsPerWord);
+ Object** pb = &pointer_buf[0];
+ size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_);
+ size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_);
+ word* live = live_bitmap.bitmap_begin_;
+ word* mark = mark_bitmap.bitmap_begin_;
+ 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 = IndexToOffset(i) + live_bitmap.heap_begin_;
+ while (garbage != 0) {
+ int shift = CLZ(garbage);
+ garbage &= ~(high_bit >> shift);
+ *pb++ = reinterpret_cast<Object*>(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
+
+// Support needed for in order traversal
+#include "object.h"
+#include "object_utils.h"
+
+namespace art {
+
+static void WalkFieldsInOrder(SpaceBitmap* visited, SpaceBitmap::Callback* callback, Object* obj,
+ void* arg);
+
+// Walk instance fields of the given Class. Separate function to allow recursion on the super
+// class.
+static void WalkInstanceFields(SpaceBitmap* visited, SpaceBitmap::Callback* callback, Object* obj,
+ Class* klass, void* arg) {
+ // Visit fields of parent classes first.
+ Class* super = klass->GetSuperClass();
+ if (super != NULL) {
+ WalkInstanceFields(visited, callback, obj, super, arg);
+ }
+ // Walk instance fields
+ ObjectArray<Field>* fields = klass->GetIFields();
+ if (fields != NULL) {
+ for (int32_t i = 0; i < fields->GetLength(); i++) {
+ Field* field = fields->Get(i);
+ FieldHelper fh(field);
+ if (!fh.GetType()->IsPrimitive()) {
+ Object* value = field->GetObj(obj);
+ if (value != NULL) {
+ WalkFieldsInOrder(visited, callback, value, arg);
+ }
+ }
+ }
+ }
+}
+
+// For an unvisited object, visit it then all its children found via fields.
+static void WalkFieldsInOrder(SpaceBitmap* visited, SpaceBitmap::Callback* callback, Object* obj,
+ void* arg) {
+ if (visited->Test(obj)) {
+ return;
+ }
+ // visit the object itself
+ (*callback)(obj, arg);
+ visited->Set(obj);
+ // Walk instance fields of all objects
+ Class* klass = obj->GetClass();
+ WalkInstanceFields(visited, callback, obj, klass, arg);
+ // Walk static fields of a Class
+ if (obj->IsClass()) {
+ ObjectArray<Field>* fields = klass->GetSFields();
+ if (fields != NULL) {
+ for (int32_t i = 0; i < fields->GetLength(); i++) {
+ Field* field = fields->Get(i);
+ FieldHelper fh(field);
+ if (!fh.GetType()->IsPrimitive()) {
+ Object* value = field->GetObj(NULL);
+ if (value != NULL) {
+ WalkFieldsInOrder(visited, callback, value, arg);
+ }
+ }
+ }
+ }
+ } else if (obj->IsObjectArray()) {
+ // Walk elements of an object array
+ ObjectArray<Object>* obj_array = obj->AsObjectArray<Object>();
+ int32_t length = obj_array->GetLength();
+ for (int32_t i = 0; i < length; i++) {
+ Object* value = obj_array->Get(i);
+ if (value != NULL) {
+ WalkFieldsInOrder(visited, callback, value, arg);
+ }
+ }
+ }
+}
+
+// Visits set bits with an in order traversal. The callback is not permitted to change the bitmap
+// bits or max during the traversal.
+void SpaceBitmap::InOrderWalk(SpaceBitmap::Callback* callback, void* arg) {
+ UniquePtr<SpaceBitmap> visited(Create("bitmap for in-order walk",
+ reinterpret_cast<byte*>(heap_begin_),
+ IndexToOffset(bitmap_size_ / kWordSize)));
+ CHECK(bitmap_begin_ != NULL);
+ CHECK(callback != NULL);
+ uintptr_t end = OffsetToIndex(heap_end_ - heap_begin_);
+ for (uintptr_t i = 0; i <= end; ++i) {
+ word w = bitmap_begin_[i];
+ if (UNLIKELY(w != 0)) {
+ word high_bit = 1 << (kBitsPerWord - 1);
+ uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
+ while (w != 0) {
+ const int shift = CLZ(w);
+ Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment);
+ WalkFieldsInOrder(visited.get(), callback, obj, arg);
+ w &= ~(high_bit >> shift);
+ }
+ }
+ }
+}
+
+} // namespace art