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/build/Android.common.mk b/build/Android.common.mk
index 74bc4a9..c6682ca 100644
--- a/build/Android.common.mk
+++ b/build/Android.common.mk
@@ -215,6 +215,7 @@
src/scoped_thread_list_lock_releaser.cc \
src/signal_catcher.cc \
src/space.cc \
+ src/space_bitmap.cc \
src/stack.cc \
src/stringpiece.cc \
src/stringprintf.cc \
diff --git a/src/card_table.cc b/src/card_table.cc
index 0f295b2..758a889 100644
--- a/src/card_table.cc
+++ b/src/card_table.cc
@@ -117,9 +117,11 @@
}
}
-void CardTable::Scan(HeapBitmap* bitmap, byte* heap_begin, byte* heap_end, Callback* visitor, void* arg) const {
- byte* card_cur = CardFromAddr(heap_begin);
- byte* card_end = CardFromAddr(heap_end);
+void CardTable::Scan(SpaceBitmap* bitmap, byte* scan_begin, byte* scan_end, Callback* visitor, void* arg) const {
+ DCHECK(bitmap->HasAddress(scan_begin));
+ DCHECK(bitmap->HasAddress(scan_end - 1)); // scan_end is the byte after the last byte we scan.
+ byte* card_cur = CardFromAddr(scan_begin);
+ byte* card_end = CardFromAddr(scan_end);
while (card_cur < card_end) {
while (card_cur < card_end && *card_cur == GC_CARD_CLEAN) {
card_cur++;
diff --git a/src/card_table.h b/src/card_table.h
index 8fde9fe..ea46cfe 100644
--- a/src/card_table.h
+++ b/src/card_table.h
@@ -25,7 +25,7 @@
namespace art {
class Heap;
-class HeapBitmap;
+class SpaceBitmap;
class Object;
#define GC_CARD_SHIFT 7
@@ -72,7 +72,7 @@
// For every dirty card between begin and end invoke the visitor with the specified argument
typedef void Callback(Object* obj, void* arg);
- void Scan(HeapBitmap* bitmap, byte* begin, byte* end, Callback* visitor, void* arg) const;
+ void Scan(SpaceBitmap* bitmap, byte* begin, byte* end, Callback* visitor, void* arg) const;
// Assertion used to check the given address is covered by the card table
void CheckAddrIsInCardTable(const byte* addr) const;
diff --git a/src/class_linker.cc b/src/class_linker.cc
index 2b20aff..dfed6f7 100644
--- a/src/class_linker.cc
+++ b/src/class_linker.cc
@@ -48,6 +48,7 @@
#include "scoped_jni_thread_state.h"
#include "ScopedLocalRef.h"
#include "space.h"
+#include "space_bitmap.h"
#include "stack_indirect_reference_table.h"
#include "stl_util.h"
#include "thread.h"
@@ -916,11 +917,11 @@
AppendToBootClassPath(*dex_file, dex_cache);
}
- HeapBitmap* heap_bitmap = heap->GetLiveBits();
- DCHECK(heap_bitmap != NULL);
-
// reinit clases_ table
- heap_bitmap->Walk(InitFromImageCallback, this);
+ const Spaces& vec = heap->GetSpaces();
+ for (Spaces::const_iterator cur = vec.begin(); cur != vec.end(); ++cur) {
+ (*cur)->GetLiveBitmap()->Walk(InitFromImageCallback, this);
+ }
// reinit class_roots_
Object* class_roots_object =
diff --git a/src/compiler.cc b/src/compiler.cc
index aad6ad3..ceb9d11 100644
--- a/src/compiler.cc
+++ b/src/compiler.cc
@@ -783,7 +783,7 @@
}
}
} else {
- if (Runtime::Current()->GetHeap()->GetImageSpace()->Contains(method)) {
+ if (Runtime::Current()->GetHeap()->FindSpaceFromObject(method)->IsImageSpace()) {
direct_method = reinterpret_cast<uintptr_t>(method);
}
direct_code = reinterpret_cast<uintptr_t>(method->GetCode());
diff --git a/src/debugger.cc b/src/debugger.cc
index e5d3780..cd52f82 100644
--- a/src/debugger.cc
+++ b/src/debugger.cc
@@ -2909,7 +2909,13 @@
UNIMPLEMENTED(WARNING) << "Native heap send heap segments";
} else {
Heap* heap = Runtime::Current()->GetHeap();
- heap->GetAllocSpace()->Walk(HeapChunkContext::HeapChunkCallback, &context);
+ typedef std::vector<Space*> SpaceVec;
+ const SpaceVec& spaces = heap->GetSpaces();
+ for (SpaceVec::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
+ if ((*cur)->IsAllocSpace()) {
+ (*cur)->AsAllocSpace()->Walk(HeapChunkContext::HeapChunkCallback, &context);
+ }
+ }
}
// Finally, send a heap end chunk.
diff --git a/src/heap.cc b/src/heap.cc
index c6dfdf7..acb80e7 100644
--- a/src/heap.cc
+++ b/src/heap.cc
@@ -137,10 +137,7 @@
Heap::Heap(size_t initial_size, size_t growth_limit, size_t capacity,
const std::string& original_image_file_name)
: lock_(NULL),
- image_space_(NULL),
alloc_space_(NULL),
- mark_bitmap_(NULL),
- live_bitmap_(NULL),
card_table_(NULL),
card_marking_disabled_(false),
is_gc_running_(false),
@@ -167,74 +164,69 @@
Space* first_space = NULL;
Space* last_space = NULL;
+ live_bitmap_.reset(new HeapBitmap);
+ mark_bitmap_.reset(new HeapBitmap);
+
// Requested begin for the alloc space, to follow the mapped image and oat files
byte* requested_begin = NULL;
std::string image_file_name(original_image_file_name);
if (!image_file_name.empty()) {
+ Space* image_space = NULL;
+
if (OS::FileExists(image_file_name.c_str())) {
// If the /system file exists, it should be up-to-date, don't try to generate
- image_space_ = Space::CreateImageSpace(image_file_name);
+ image_space = Space::CreateImageSpace(image_file_name);
} else {
// If the /system file didn't exist, we need to use one from the art-cache.
// If the cache file exists, try to open, but if it fails, regenerate.
// If it does not exist, generate.
image_file_name = GetArtCacheFilenameOrDie(image_file_name);
if (OS::FileExists(image_file_name.c_str())) {
- image_space_ = Space::CreateImageSpace(image_file_name);
+ image_space = Space::CreateImageSpace(image_file_name);
}
- if (image_space_ == NULL) {
+ if (image_space == NULL) {
if (!GenerateImage(image_file_name)) {
LOG(FATAL) << "Failed to generate image: " << image_file_name;
}
- image_space_ = Space::CreateImageSpace(image_file_name);
+ image_space = Space::CreateImageSpace(image_file_name);
}
}
- if (image_space_ == NULL) {
+ if (image_space == NULL) {
LOG(FATAL) << "Failed to create space from " << image_file_name;
}
- AddSpace(image_space_);
- UpdateFirstAndLastSpace(&first_space, &last_space, image_space_);
+ AddSpace(image_space);
+ UpdateFirstAndLastSpace(&first_space, &last_space, image_space);
// Oat files referenced by image files immediately follow them in memory, ensure alloc space
// isn't going to get in the middle
- byte* oat_end_addr = image_space_->GetImageHeader().GetOatEnd();
- CHECK(oat_end_addr > image_space_->End());
+ byte* oat_end_addr = GetImageSpace()->GetImageHeader().GetOatEnd();
+ CHECK(oat_end_addr > GetImageSpace()->End());
if (oat_end_addr > requested_begin) {
requested_begin = reinterpret_cast<byte*>(RoundUp(reinterpret_cast<uintptr_t>(oat_end_addr),
kPageSize));
}
}
- alloc_space_ = Space::CreateAllocSpace("alloc space", initial_size, growth_limit, capacity,
- requested_begin);
+ UniquePtr<AllocSpace> alloc_space(Space::CreateAllocSpace(
+ "alloc space", initial_size, growth_limit, capacity, requested_begin));
+ alloc_space_ = alloc_space.release();
+ AddSpace(alloc_space_);
if (alloc_space_ == NULL) {
LOG(FATAL) << "Failed to create alloc space";
}
- AddSpace(alloc_space_);
+
UpdateFirstAndLastSpace(&first_space, &last_space, alloc_space_);
byte* heap_begin = first_space->Begin();
size_t heap_capacity = (last_space->Begin() - first_space->Begin()) + last_space->NonGrowthLimitCapacity();
- // Allocate the initial live bitmap.
- UniquePtr<HeapBitmap> live_bitmap(HeapBitmap::Create("dalvik-bitmap-1", heap_begin, heap_capacity));
- if (live_bitmap.get() == NULL) {
- LOG(FATAL) << "Failed to create live bitmap";
- }
-
// Mark image objects in the live bitmap
for (size_t i = 0; i < spaces_.size(); ++i) {
Space* space = spaces_[i];
if (space->IsImageSpace()) {
- space->AsImageSpace()->RecordImageAllocations(live_bitmap.get());
+ space->AsImageSpace()->RecordImageAllocations(space->GetLiveBitmap());
}
}
- // Allocate the initial mark bitmap.
- UniquePtr<HeapBitmap> mark_bitmap(HeapBitmap::Create("dalvik-bitmap-2", heap_begin, heap_capacity));
- if (mark_bitmap.get() == NULL) {
- LOG(FATAL) << "Failed to create mark bitmap";
- }
-
// Allocate the card table.
UniquePtr<CardTable> card_table(CardTable::Create(heap_begin, heap_capacity));
if (card_table.get() == NULL) {
@@ -246,8 +238,6 @@
mod_union_table->Init();
mod_union_table_ = mod_union_table;
- live_bitmap_ = live_bitmap.release();
- mark_bitmap_ = mark_bitmap.release();
card_table_ = card_table.release();
num_bytes_allocated_ = 0;
@@ -269,6 +259,12 @@
}
void Heap::AddSpace(Space* space) {
+ DCHECK(space->GetLiveBitmap() != NULL);
+ live_bitmap_->AddSpaceBitmap(space->GetLiveBitmap());
+
+ DCHECK(space->GetMarkBitmap() != NULL);
+ mark_bitmap_->AddSpaceBitmap(space->GetMarkBitmap());
+
spaces_.push_back(space);
}
@@ -279,8 +275,6 @@
// all daemon threads are suspended, and we also know that the threads list have been deleted, so
// those threads can't resume. We're the only running thread, and we can do whatever we like...
STLDeleteElements(&spaces_);
- delete mark_bitmap_;
- delete live_bitmap_;
delete card_table_;
delete mod_union_table_;
delete mark_stack_;
@@ -288,6 +282,31 @@
delete lock_;
}
+Space* Heap::FindSpaceFromObject(const Object* obj) const {
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces_.begin(); cur != spaces_.end(); ++cur) {
+ if ((*cur)->Contains(obj)) {
+ return *cur;
+ }
+ }
+ LOG(FATAL) << "object " << reinterpret_cast<const void*>(obj) << " not inside any spaces!";
+ return NULL;
+}
+
+ImageSpace* Heap::GetImageSpace() {
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces_.begin(); cur != spaces_.end(); ++cur) {
+ if ((*cur)->IsImageSpace()) {
+ return (*cur)->AsImageSpace();
+ }
+ }
+ return NULL;
+}
+
+AllocSpace* Heap::GetAllocSpace() {
+ return alloc_space_;
+}
+
static void MSpaceChunkCallback(void* start, void* end, size_t used_bytes, void* arg) {
size_t& max_contiguous_allocation = *reinterpret_cast<size_t*>(arg);
@@ -321,8 +340,7 @@
}
if (!is_gc_running_ && num_bytes_allocated_ >= concurrent_start_bytes_) {
- // The SirtRef is necessary since the calls in RequestConcurrentGC
- // are a safepoint.
+ // The SirtRef is necessary since the calls in RequestConcurrentGC are a safepoint.
SirtRef<Object> ref(obj);
RequestConcurrentGC();
}
@@ -331,7 +349,12 @@
}
total_bytes_free = GetFreeMemory();
max_contiguous_allocation = 0;
- GetAllocSpace()->Walk(MSpaceChunkCallback, &max_contiguous_allocation);
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces_.begin(); cur != spaces_.end(); ++cur) {
+ if ((*cur)->IsAllocSpace()) {
+ (*cur)->AsAllocSpace()->Walk(MSpaceChunkCallback, &max_contiguous_allocation);
+ }
+ }
}
std::string msg(StringPrintf("Failed to allocate a %zd-byte %s (%lld total bytes free; largest possible contiguous allocation %zd bytes)",
@@ -361,7 +384,7 @@
bool Heap::IsLiveObjectLocked(const Object* obj) {
lock_->AssertHeld();
- return IsHeapAddress(obj) && live_bitmap_->Test(obj);
+ return IsHeapAddress(obj) && GetLiveBitmap()->Test(obj);
}
#if VERIFY_OBJECT_ENABLED
@@ -381,7 +404,7 @@
if (obj != NULL) {
if (!IsAligned<kObjectAlignment>(obj)) {
LOG(FATAL) << "Object isn't aligned: " << obj;
- } else if (!live_bitmap_->Test(obj)) {
+ } else if (!GetLiveBitmap()->Test(obj)) {
LOG(FATAL) << "Object is dead: " << obj;
}
// Ignore early dawn of the universe verifications
@@ -393,7 +416,7 @@
LOG(FATAL) << "Null class in object: " << obj;
} else if (!IsAligned<kObjectAlignment>(c)) {
LOG(FATAL) << "Class isn't aligned: " << c << " in object: " << obj;
- } else if (!live_bitmap_->Test(c)) {
+ } else if (!GetLiveBitmap()->Test(c)) {
LOG(FATAL) << "Class of object is dead: " << c << " in object: " << obj;
}
// Check obj.getClass().getClass() == obj.getClass().getClass().getClass()
@@ -415,7 +438,7 @@
void Heap::VerifyHeap() {
ScopedHeapLock heap_lock;
- live_bitmap_->Walk(Heap::VerificationCallback, this);
+ GetLiveBitmap()->Walk(Heap::VerificationCallback, this);
}
void Heap::RecordAllocationLocked(AllocSpace* space, const Object* obj) {
@@ -467,13 +490,28 @@
Object* Heap::AllocateLocked(size_t size) {
lock_->AssertHeld();
- DCHECK(alloc_space_ != NULL);
- AllocSpace* space = alloc_space_;
- Object* obj = AllocateLocked(space, size);
+
+ // Try the default alloc space first.
+ Object* obj = AllocateLocked(alloc_space_, size);
if (obj != NULL) {
- RecordAllocationLocked(space, obj);
+ RecordAllocationLocked(alloc_space_, obj);
+ return obj;
}
- return obj;
+
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces_.begin(); cur != spaces_.end(); ++cur) {
+ if ((*cur)->IsAllocSpace() && *cur != alloc_space_) {
+ AllocSpace* space = (*cur)->AsAllocSpace();
+ Object* obj = AllocateLocked(space, size);
+ if (obj != NULL) {
+ RecordAllocationLocked(space, obj);
+ // Switch to this alloc space since the old one did not have enough storage.
+ alloc_space_ = space;
+ return obj;
+ }
+ }
+ }
+ return NULL;
}
Object* Heap::AllocateLocked(AllocSpace* space, size_t alloc_size) {
@@ -553,15 +591,22 @@
}
int64_t Heap::GetMaxMemory() {
- return alloc_space_->Capacity();
+ size_t total = 0;
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces_.begin(); cur != spaces_.end(); ++cur) {
+ if ((*cur)->IsAllocSpace()) {
+ total += (*cur)->AsAllocSpace()->Capacity();
+ }
+ }
+ return total;
}
int64_t Heap::GetTotalMemory() {
- return alloc_space_->Capacity();
+ return GetMaxMemory();
}
int64_t Heap::GetFreeMemory() {
- return alloc_space_->Capacity() - num_bytes_allocated_;
+ return GetMaxMemory() - num_bytes_allocated_;
}
class InstanceCounter {
@@ -600,7 +645,7 @@
int64_t Heap::CountInstances(Class* c, bool count_assignable) {
ScopedHeapLock heap_lock;
InstanceCounter counter(c, count_assignable);
- live_bitmap_->Walk(InstanceCounter::Callback, &counter);
+ GetLiveBitmap()->Walk(InstanceCounter::Callback, &counter);
return counter.GetCount();
}
@@ -794,13 +839,20 @@
}
void Heap::SetIdealFootprint(size_t max_allowed_footprint) {
- size_t alloc_space_capacity = alloc_space_->Capacity();
- if (max_allowed_footprint > alloc_space_capacity) {
- VLOG(gc) << "Clamp target GC heap from " << PrettySize(max_allowed_footprint)
- << " to " << PrettySize(alloc_space_capacity);
- max_allowed_footprint = alloc_space_capacity;
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces_.begin(); cur != spaces_.end(); ++cur) {
+ if ((*cur)->IsAllocSpace()) {
+ AllocSpace* alloc_space = (*cur)->AsAllocSpace();
+ // TODO: Behavior for multiple alloc spaces?
+ size_t alloc_space_capacity = alloc_space->Capacity();
+ if (max_allowed_footprint > alloc_space_capacity) {
+ VLOG(gc) << "Clamp target GC heap from " << PrettySize(max_allowed_footprint)
+ << " to " << PrettySize(alloc_space_capacity);
+ max_allowed_footprint = alloc_space_capacity;
+ }
+ alloc_space->SetFootprintLimit(max_allowed_footprint);
+ }
}
- alloc_space_->SetFootprintLimit(max_allowed_footprint);
}
// kHeapIdealFree is the ideal maximum free size, when we grow the heap for utilization.
@@ -985,10 +1037,10 @@
CollectGarbageInternal(true, false);
}
-void Heap::Trim() {
+void Heap::Trim(AllocSpace* alloc_space) {
lock_->AssertHeld();
WaitForConcurrentGcToComplete();
- GetAllocSpace()->Trim();
+ alloc_space->Trim();
}
void Heap::RequestHeapTrim() {
diff --git a/src/heap.h b/src/heap.h
index 75362ce..132d5e5 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -27,6 +27,7 @@
#include "heap_bitmap.h"
#include "mutex.h"
#include "offsets.h"
+#include "safe_map.h"
#define VERIFY_OBJECT_ENABLED 0
@@ -44,6 +45,8 @@
class SpaceTest;
class Thread;
+typedef std::vector<Space*> Spaces;
+
class LOCKABLE Heap {
public:
static const size_t kInitialSize = 2 * MB;
@@ -137,14 +140,6 @@
return spaces_;
}
- HeapBitmap* GetLiveBits() {
- return live_bitmap_;
- }
-
- HeapBitmap* GetMarkBits() {
- return mark_bitmap_;
- }
-
void SetReferenceOffsets(MemberOffset reference_referent_offset,
MemberOffset reference_queue_offset,
MemberOffset reference_queueNext_offset,
@@ -213,16 +208,6 @@
size_t GetBytesAllocated() { return num_bytes_allocated_; }
size_t GetObjectsAllocated() { return num_objects_allocated_; }
- ImageSpace* GetImageSpace() {
- CHECK(image_space_ != NULL);
- return image_space_;
- }
-
- AllocSpace* GetAllocSpace() {
- CHECK(alloc_space_ != NULL);
- return alloc_space_;
- }
-
size_t GetConcurrentStartSize() const { return concurrent_start_size_; }
void SetConcurrentStartSize(size_t size) {
@@ -235,9 +220,26 @@
concurrent_min_free_ = size;
}
+ // Functions for getting the bitmap which corresponds to an object's address.
+ // This is probably slow, TODO: use better data structure like binary tree .
+ Space* FindSpaceFromObject(const Object*) const;
+
void DumpForSigQuit(std::ostream& os);
- void Trim();
+ void Trim(AllocSpace* alloc_space);
+
+ HeapBitmap* GetLiveBitmap() {
+ return live_bitmap_.get();
+ }
+
+ HeapBitmap* GetMarkBitmap() {
+ return mark_bitmap_.get();
+ }
+
+ // Assumes there is only one image space.
+ // DEPRECATED: Should remove in "near" future when support for multiple image spaces is added.
+ ImageSpace* GetImageSpace();
+ AllocSpace* GetAllocSpace();
private:
// Allocates uninitialized storage.
@@ -276,17 +278,11 @@
Mutex* lock_;
ConditionVariable* condition_;
- std::vector<Space*> spaces_;
+ Spaces spaces_;
- ImageSpace* image_space_;
-
- // default Space for allocations
+ // The alloc space which we are currently allocating into.
AllocSpace* alloc_space_;
- HeapBitmap* mark_bitmap_;
-
- HeapBitmap* live_bitmap_;
-
// TODO: Reduce memory usage, this bitmap currently takes 1 bit per 8 bytes
// of image space.
ModUnionTable* mod_union_table_;
@@ -300,11 +296,14 @@
// True while the garbage collector is running.
volatile bool is_gc_running_;
- // Bytes until concurrent GC
+ // Bytes until concurrent GC starts.
size_t concurrent_start_bytes_;
size_t concurrent_start_size_;
size_t concurrent_min_free_;
+ UniquePtr<HeapBitmap> live_bitmap_;
+ UniquePtr<HeapBitmap> mark_bitmap_;
+
// True while the garbage collector is trying to signal the GC daemon thread.
// This flag is needed to prevent recursion from occurring when the JNI calls
// allocate memory and request another GC.
diff --git a/src/heap_bitmap.cc b/src/heap_bitmap.cc
index fc722f5..c7b2f6c 100644
--- a/src/heap_bitmap.cc
+++ b/src/heap_bitmap.cc
@@ -1,313 +1,2 @@
-/*
- * 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 {
-
-HeapBitmap* HeapBitmap::Create(const char* 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 = HB_OFFSET_TO_INDEX(RoundUp(heap_capacity, kAlignment * kBitsPerWord)) * kWordSize;
- UniquePtr<MemMap> mem_map(MemMap::MapAnonymous(name, 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 HeapBitmap(name, mem_map.release(), bitmap_begin, bitmap_size, heap_begin);
-}
-
-// 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 (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 HeapBitmap::HasAddress(const void* obj) const {
- if (obj != NULL) {
- const uintptr_t offset = (uintptr_t)obj - heap_begin_;
- const size_t index = HB_OFFSET_TO_INDEX(offset);
- return index < bitmap_size_ / kWordSize;
- }
- return false;
-}
-
-void HeapBitmap::VisitRange(uintptr_t visit_begin, uintptr_t visit_end, Callback* visitor, void* arg) const {
- size_t start = HB_OFFSET_TO_INDEX(visit_begin - heap_begin_);
- size_t end = HB_OFFSET_TO_INDEX(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 = HB_INDEX_TO_OFFSET(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 HeapBitmap::Walk(HeapBitmap::Callback* callback, void* arg) {
- CHECK(bitmap_begin_ != NULL);
- CHECK(callback != NULL);
- if (heap_end_ < heap_begin_) {
- return; // Bitmap is empty.
- }
- uintptr_t end = HB_OFFSET_TO_INDEX(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 = HB_INDEX_TO_OFFSET(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 HeapBitmap::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 = HB_OFFSET_TO_INDEX(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 = HB_OFFSET_TO_INDEX(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 = HB_INDEX_TO_OFFSET(i) + heap_begin_;
- void* finger = reinterpret_cast<void*>(HB_INDEX_TO_OFFSET(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 = HB_OFFSET_TO_INDEX(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 = HB_INDEX_TO_OFFSET(i) + heap_begin_;
- void* finger = reinterpret_cast<void*>(HB_INDEX_TO_OFFSET(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 = HB_OFFSET_TO_INDEX(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 HeapBitmap::SweepWalk(const HeapBitmap& live_bitmap,
- const HeapBitmap& mark_bitmap,
- uintptr_t sweep_begin, uintptr_t sweep_end,
- HeapBitmap::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 = HB_OFFSET_TO_INDEX(sweep_begin - live_bitmap.heap_begin_);
- size_t end = HB_OFFSET_TO_INDEX(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 = HB_INDEX_TO_OFFSET(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(HeapBitmap* visited, HeapBitmap::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(HeapBitmap* visited, HeapBitmap::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(HeapBitmap* visited, HeapBitmap::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 HeapBitmap::InOrderWalk(HeapBitmap::Callback* callback, void* arg) {
- UniquePtr<HeapBitmap> visited(Create("bitmap for in-order walk",
- reinterpret_cast<byte*>(heap_begin_),
- HB_INDEX_TO_OFFSET(bitmap_size_ / kWordSize)));
- CHECK(bitmap_begin_ != NULL);
- CHECK(callback != NULL);
- uintptr_t end = HB_OFFSET_TO_INDEX(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 = HB_INDEX_TO_OFFSET(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
diff --git a/src/heap_bitmap.h b/src/heap_bitmap.h
index 34c11b9..e2109d6 100644
--- a/src/heap_bitmap.h
+++ b/src/heap_bitmap.h
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2008 The Android Open Source Project
+ * 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.
@@ -17,175 +17,65 @@
#ifndef ART_SRC_HEAP_BITMAP_H_
#define ART_SRC_HEAP_BITMAP_H_
-#include <limits.h>
-#include <stdint.h>
-
-#include "UniquePtr.h"
-#include "globals.h"
-#include "logging.h"
-#include "mem_map.h"
-#include "utils.h"
+#include "space_bitmap.h"
namespace art {
+ class Heap;
+ class SpaceBitmap;
-class Object;
-
-// <offset> is the difference from .base to a pointer address.
-// <index> is the index of .bits that contains the bit representing
-// <offset>.
-#define HB_OFFSET_TO_INDEX(offset_) \
- ((offset_) / kAlignment / kBitsPerWord)
-#define HB_INDEX_TO_OFFSET(index_) \
- ((index_) * kAlignment * kBitsPerWord)
-
-#define HB_OFFSET_TO_BYTE_INDEX(offset_) \
- (HB_OFFSET_TO_INDEX(offset_) * sizeof(*(reinterpret_cast<HeapBitmap*>(0))->words_))
-
-// Pack the bits in backwards so they come out in address order
-// when using CLZ.
-#define HB_OFFSET_TO_MASK(offset_) \
- (1 << (31-(((uintptr_t)(offset_) / kAlignment) % kBitsPerWord)))
-
-class HeapBitmap {
- public:
- static const size_t kAlignment = 8;
-
- typedef void Callback(Object* obj, void* arg);
-
- typedef void ScanCallback(Object* obj, void* finger, void* arg);
-
- typedef void SweepCallback(size_t ptr_count, Object** ptrs, void* arg);
-
- // Initialize a HeapBitmap so that it points to a bitmap large enough to cover a heap at
- // heap_begin of heap_capacity bytes, where objects are guaranteed to be kAlignment-aligned.
- static HeapBitmap* Create(const char* name, byte* heap_begin, size_t heap_capacity);
-
- ~HeapBitmap();
-
- inline void Set(const Object* obj) {
- Modify(obj, true);
- }
-
- inline void Clear(const Object* obj) {
- Modify(obj, false);
- }
-
- void Clear();
-
- inline bool Test(const Object* obj) {
- uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
- DCHECK(HasAddress(obj)) << obj;
- DCHECK(bitmap_begin_ != NULL);
- DCHECK_GE(addr, heap_begin_);
- if (addr <= heap_end_) {
- const uintptr_t offset = addr - heap_begin_;
- return (bitmap_begin_[HB_OFFSET_TO_INDEX(offset)] & HB_OFFSET_TO_MASK(offset)) != 0;
- } else {
- return false;
- }
- }
-
- bool HasAddress(const void* addr) const;
-
- void VisitRange(uintptr_t base, uintptr_t max, Callback* visitor, void* arg) const;
-
- class ClearVisitor {
+ class HeapBitmap {
public:
- explicit ClearVisitor(HeapBitmap* const bitmap)
- : bitmap_(bitmap) {
+ bool Test(const Object* obj) {
+ SpaceBitmap* bitmap = GetSpaceBitmap(obj);
+ DCHECK(bitmap != NULL);
+ return bitmap->Test(obj);
}
- void operator ()(Object* obj) const {
- bitmap_->Clear(obj);
+ void Clear(const Object* obj) {
+ SpaceBitmap* bitmap = GetSpaceBitmap(obj);
+ DCHECK(bitmap != NULL)
+ << "tried to clear object "
+ << reinterpret_cast<const void*>(obj)
+ << " which did not belong to any bitmaps";
+ return bitmap->Clear(obj);
}
+
+ void Set(const Object* obj) {
+ SpaceBitmap* bitmap = GetSpaceBitmap(obj);
+ DCHECK(bitmap != NULL)
+ << "tried to mark object "
+ << reinterpret_cast<const void*>(obj)
+ << " which did not belong to any bitmaps";
+ bitmap->Set(obj);
+ }
+
+ SpaceBitmap* GetSpaceBitmap(const Object* obj) {
+ // TODO: C++0x auto
+ for (BitmapVec::iterator cur = bitmaps_.begin(); cur != bitmaps_.end(); ++cur) {
+ if ((*cur)->HasAddress(obj)) {
+ return *cur;
+ }
+ }
+ return NULL;
+ }
+
+ void Walk(SpaceBitmap::Callback* callback, void* arg) {
+ // TODO: C++0x auto
+ for (BitmapVec::iterator cur = bitmaps_.begin(); cur != bitmaps_.end(); ++cur) {
+ (*cur)->Walk(callback, arg);
+ }
+ }
+
private:
- HeapBitmap* const bitmap_;
+ void AddSpaceBitmap(SpaceBitmap* space) {
+ bitmaps_.push_back(space);
+ }
+
+ typedef std::vector<SpaceBitmap*> BitmapVec;
+ BitmapVec bitmaps_;
+
+ friend class Heap;
};
-
- template <typename Visitor>
- void VisitRange(uintptr_t visit_begin, uintptr_t visit_end, const Visitor& visitor) const {
- for (; visit_begin < visit_end; visit_begin += kAlignment ) {
- visitor(reinterpret_cast<Object*>(visit_begin));
- }
- }
-
- template <typename Visitor>
- void VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end, const Visitor& visitor) const {
- size_t start = HB_OFFSET_TO_INDEX(visit_begin - heap_begin_);
- size_t end = HB_OFFSET_TO_INDEX(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 = HB_INDEX_TO_OFFSET(i) + heap_begin_;
- do {
- const int shift = CLZ(w);
- Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment);
- visitor(obj);
- w &= ~(high_bit >> shift);
- } while (w != 0);
- }
- }
- }
-
- void Walk(Callback* callback, void* arg);
-
- void InOrderWalk(HeapBitmap::Callback* callback, void* arg);
-
- void ScanWalk(uintptr_t base, uintptr_t max, ScanCallback* thunk, void* arg);
-
- static void SweepWalk(const HeapBitmap& live,
- const HeapBitmap& mark,
- uintptr_t base, uintptr_t max,
- SweepCallback* thunk, void* arg);
-
- private:
- // TODO: heap_end_ is initialized so that the heap bitmap is empty, this doesn't require the -1,
- // however, we document that this is expected on heap_end_
- HeapBitmap(const char* name, MemMap* mem_map, word* bitmap_begin, size_t bitmap_size, const void* heap_begin)
- : mem_map_(mem_map), bitmap_begin_(bitmap_begin), bitmap_size_(bitmap_size),
- heap_begin_(reinterpret_cast<uintptr_t>(heap_begin)), heap_end_(heap_begin_ - 1),
- name_(name) {}
-
- inline void Modify(const Object* obj, bool do_set) {
- uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
- DCHECK_GE(addr, heap_begin_);
- const uintptr_t offset = addr - heap_begin_;
- const size_t index = HB_OFFSET_TO_INDEX(offset);
- const word mask = HB_OFFSET_TO_MASK(offset);
- DCHECK_LT(index, bitmap_size_ / kWordSize);
- if (do_set) {
- if (addr > heap_end_) {
- heap_end_ = addr;
- }
- bitmap_begin_[index] |= mask;
- } else {
- bitmap_begin_[index] &= ~mask;
- }
- }
-
- // Backing storage for bitmap.
- UniquePtr<MemMap> mem_map_;
-
- // This bitmap itself, word sized for efficiency in scanning.
- word* const bitmap_begin_;
-
- // Size of this bitmap.
- const size_t bitmap_size_;
-
- // The base address of the heap, which corresponds to the word containing the first bit in the
- // bitmap.
- const uintptr_t heap_begin_;
-
- // The highest pointer value ever returned by an allocation from
- // this heap. I.e., the highest address that may correspond to a
- // set bit. If there are no bits set, (heap_end_ < heap_begin_).
- uintptr_t heap_end_;
-
- // Name of this bitmap.
- const char* const name_;
-};
-
} // namespace art
#endif // ART_SRC_HEAP_BITMAP_H_
diff --git a/src/heap_test.cc b/src/heap_test.cc
index d5c07da..48aa425 100644
--- a/src/heap_test.cc
+++ b/src/heap_test.cc
@@ -47,9 +47,9 @@
TEST_F(HeapTest, HeapBitmapCapacityTest) {
byte* heap_begin = reinterpret_cast<byte*>(0x1000);
- const size_t heap_capacity = HeapBitmap::kAlignment * (sizeof(intptr_t) * 8 + 1);
- UniquePtr<HeapBitmap> bitmap(HeapBitmap::Create("test-bitmap", heap_begin, heap_capacity));
- bitmap->Set(reinterpret_cast<const Object*>(&heap_begin[heap_capacity - HeapBitmap::kAlignment]));
+ const size_t heap_capacity = SpaceBitmap::kAlignment * (sizeof(intptr_t) * 8 + 1);
+ UniquePtr<SpaceBitmap> bitmap(SpaceBitmap::Create("test-bitmap", heap_begin, heap_capacity));
+ bitmap->Set(reinterpret_cast<const Object*>(&heap_begin[heap_capacity - SpaceBitmap::kAlignment]));
}
} // namespace art
diff --git a/src/hprof/hprof.cc b/src/hprof/hprof.cc
index 3e976ad..d806d71 100644
--- a/src/hprof/hprof.cc
+++ b/src/hprof/hprof.cc
@@ -48,6 +48,7 @@
#include "os.h"
#include "safe_map.h"
#include "scoped_heap_lock.h"
+#include "space.h"
#include "stringprintf.h"
#include "thread_list.h"
@@ -404,7 +405,7 @@
// Walk the roots and the heap.
current_record_.StartNewRecord(body_fp_, HPROF_TAG_HEAP_DUMP_SEGMENT, HPROF_TIME);
Runtime::Current()->VisitRoots(RootVisitor, this);
- Runtime::Current()->GetHeap()->GetLiveBits()->Walk(HeapBitmapCallback, this);
+ Runtime::Current()->GetHeap()->GetLiveBitmap()->Walk(HeapBitmapCallback, this);
current_record_.StartNewRecord(body_fp_, HPROF_TAG_HEAP_DUMP_END, HPROF_TIME);
current_record_.Flush();
fflush(body_fp_);
diff --git a/src/image_test.cc b/src/image_test.cc
index 5662239..f9c2d1c 100644
--- a/src/image_test.cc
+++ b/src/image_test.cc
@@ -65,7 +65,7 @@
Space* space = heap->GetSpaces()[0];
ASSERT_FALSE(space->IsImageSpace());
ASSERT_TRUE(space != NULL);
- ASSERT_EQ(space, heap->GetAllocSpace());
+ ASSERT_TRUE(space->IsAllocSpace());
ASSERT_GE(sizeof(image_header) + space->Size(), static_cast<size_t>(file->Length()));
}
@@ -93,8 +93,6 @@
ASSERT_FALSE(heap->GetSpaces()[0]->IsAllocSpace());
ASSERT_FALSE(heap->GetSpaces()[1]->IsImageSpace());
ASSERT_TRUE(heap->GetSpaces()[1]->IsAllocSpace());
- ASSERT_TRUE(heap->GetImageSpace() != NULL);
- ASSERT_TRUE(heap->GetAllocSpace() != NULL);
ImageSpace* image_space = heap->GetImageSpace();
byte* image_begin = image_space->Begin();
diff --git a/src/image_writer.cc b/src/image_writer.cc
index 589d3d7..59b7e80 100644
--- a/src/image_writer.cc
+++ b/src/image_writer.cc
@@ -52,7 +52,7 @@
image_begin_ = reinterpret_cast<byte*>(image_begin);
Heap* heap = Runtime::Current()->GetHeap();
- source_space_ = heap->GetAllocSpace();
+ const Spaces& spaces = heap->GetSpaces();
ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
const std::vector<DexCache*>& all_dex_caches = class_linker->GetDexCaches();
@@ -75,7 +75,14 @@
ComputeLazyFieldsForImageClasses(); // Add useful information
ComputeEagerResolvedStrings();
heap->CollectGarbage(false); // Remove garbage
- heap->GetAllocSpace()->Trim(); // Trim size of source_space
+ // Trim size of alloc spaces
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
+ if ((*cur)->IsAllocSpace()) {
+ (*cur)->AsAllocSpace()->Trim();
+ }
+ }
+
if (!AllocMemory()) {
return false;
}
@@ -104,8 +111,27 @@
return true;
}
+bool ImageWriter::InSourceSpace(const Object* object) const {
+ const Spaces& spaces = Runtime::Current()->GetHeap()->GetSpaces();
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
+ if ((*cur)->IsAllocSpace() && (*cur)->Contains(object)) {
+ return true;
+ }
+ }
+ return false;
+}
+
bool ImageWriter::AllocMemory() {
- size_t size = source_space_->Size();
+ typedef std::vector<Space*> SpaceVec;
+ const SpaceVec& spaces = Runtime::Current()->GetHeap()->GetSpaces();
+ size_t size = 0;
+ for (SpaceVec::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
+ if ((*cur)->IsAllocSpace()) {
+ size += (*cur)->Size();
+ }
+ }
+
int prot = PROT_READ | PROT_WRITE;
size_t length = RoundUp(size, kPageSize);
image_.reset(MemMap::MapAnonymous("image-writer-image", NULL, length, prot));
@@ -151,9 +177,8 @@
}
void ImageWriter::ComputeEagerResolvedStrings() {
- HeapBitmap* heap_bitmap = Runtime::Current()->GetHeap()->GetLiveBits();
- DCHECK(heap_bitmap != NULL);
- heap_bitmap->Walk(ComputeEagerResolvedStringsCallback, this); // TODO: add Space-limited Walk
+ // TODO: Check image spaces only?
+ Runtime::Current()->GetHeap()->GetLiveBitmap()->Walk(ComputeEagerResolvedStringsCallback, this);
}
bool ImageWriter::IsImageClass(const Class* klass) {
@@ -232,7 +257,8 @@
if (image_classes_ == NULL) {
return;
}
- Runtime::Current()->GetHeap()->GetLiveBits()->Walk(CheckNonImageClassesRemovedCallback, this);
+
+ Runtime::Current()->GetHeap()->GetLiveBitmap()->Walk(CheckNonImageClassesRemovedCallback, this);
}
void ImageWriter::CheckNonImageClassesRemovedCallback(Object* obj, void* arg) {
@@ -332,16 +358,21 @@
void ImageWriter::CalculateNewObjectOffsets() {
SirtRef<ObjectArray<Object> > image_roots(CreateImageRoots());
- HeapBitmap* heap_bitmap = Runtime::Current()->GetHeap()->GetLiveBits();
- DCHECK(heap_bitmap != NULL);
+ Heap* heap = Runtime::Current()->GetHeap();
+ typedef std::vector<Space*> SpaceVec;
+ const SpaceVec& spaces = heap->GetSpaces();
+ DCHECK(!spaces.empty());
DCHECK_EQ(0U, image_end_);
// leave space for the header, but do not write it yet, we need to
// know where image_roots is going to end up
image_end_ += RoundUp(sizeof(ImageHeader), 8); // 64-bit-alignment
- heap_bitmap->InOrderWalk(CalculateNewObjectOffsetsCallback, this); // TODO: add Space-limited Walk
- DCHECK_LT(image_end_, image_->Size());
+ // TODO: Image spaces only?
+ for (SpaceVec::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
+ (*cur)->GetLiveBitmap()->InOrderWalk(CalculateNewObjectOffsetsCallback, this);
+ DCHECK_LT(image_end_, image_->Size());
+ }
// Note that image_top_ is left at end of used space
oat_begin_ = image_begin_ + RoundUp(image_end_, kPageSize);
@@ -358,11 +389,10 @@
void ImageWriter::CopyAndFixupObjects() {
Heap* heap = Runtime::Current()->GetHeap();
- HeapBitmap* heap_bitmap = heap->GetLiveBits();
- DCHECK(heap_bitmap != NULL);
// TODO: heap validation can't handle this fix up pass
heap->DisableObjectValidation();
- heap_bitmap->Walk(CopyAndFixupObjectsCallback, this); // TODO: add Space-limited Walk
+ // TODO: Image spaces only?
+ heap->GetLiveBitmap()->Walk(CopyAndFixupObjectsCallback, this);
}
void ImageWriter::CopyAndFixupObjectsCallback(Object* object, void* arg) {
diff --git a/src/image_writer.h b/src/image_writer.h
index 1dc5b66..07d55dc 100644
--- a/src/image_writer.h
+++ b/src/image_writer.h
@@ -39,8 +39,7 @@
class ImageWriter {
public:
explicit ImageWriter(const std::set<std::string>* image_classes)
- : source_space_(NULL), image_end_(0), image_begin_(NULL), image_classes_(image_classes),
- oat_begin_(NULL) {}
+ : image_end_(0), image_begin_(NULL), image_classes_(image_classes), oat_begin_(NULL) {}
~ImageWriter() {}
@@ -79,10 +78,7 @@
return offsets_.find(object)->second;
}
- bool InSourceSpace(const Object* object) const {
- DCHECK(source_space_ != NULL);
- return source_space_->Contains(object);
- }
+ bool InSourceSpace(const Object* object) const;
Object* GetImageAddress(const Object* object) const {
if (object == NULL) {
@@ -147,9 +143,6 @@
// oat file with code for this image
OatFile* oat_file_;
- // Space we are writing objects from
- const Space* source_space_;
-
// memory mapped for generating the image
UniquePtr<MemMap> image_;
diff --git a/src/mark_sweep.cc b/src/mark_sweep.cc
index 63801a1..1a7bc83 100644
--- a/src/mark_sweep.cc
+++ b/src/mark_sweep.cc
@@ -37,10 +37,9 @@
namespace art {
MarkSweep::MarkSweep(MarkStack* mark_stack)
- : mark_stack_(mark_stack),
+ : current_mark_bitmap_(NULL),
+ mark_stack_(mark_stack),
heap_(NULL),
- mark_bitmap_(NULL),
- live_bitmap_(NULL),
finger_(NULL),
condemned_(NULL),
soft_reference_list_(NULL),
@@ -54,25 +53,40 @@
void MarkSweep::Init() {
heap_ = Runtime::Current()->GetHeap();
- mark_bitmap_ = heap_->GetMarkBits();
- live_bitmap_ = heap_->GetLiveBits();
mark_stack_->Reset();
+ const Spaces& spaces = heap_->GetSpaces();
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
+ if ((*cur)->IsAllocSpace()) {
+ current_mark_bitmap_ = (*cur)->GetMarkBitmap();
+ break;
+ }
+ }
// TODO: if concurrent, enable card marking in compiler
-
// TODO: check that the mark bitmap is entirely clear.
}
void MarkSweep::MarkObject0(const Object* obj, bool check_finger) {
DCHECK(obj != NULL);
+
+ SpaceBitmap* space_bitmap = NULL;
+ // Try to take advantage of locality of references within a space, failing this find the space
+ // the hard way.
+ if (current_mark_bitmap_->HasAddress(obj)) {
+ space_bitmap = current_mark_bitmap_;
+ } else {
+ space_bitmap = heap_->GetMarkBitmap()->GetSpaceBitmap(obj);
+ }
+
if (obj < condemned_) {
DCHECK(IsMarked(obj));
return;
}
- bool is_marked = mark_bitmap_->Test(obj);
+ bool is_marked = space_bitmap->Test(obj);
// This object was not previously marked.
if (!is_marked) {
- mark_bitmap_->Set(obj);
+ space_bitmap->Set(obj);
if (check_finger && obj < finger_) {
// The object must be pushed on to the mark stack.
mark_stack_->Push(obj);
@@ -115,9 +129,7 @@
DCHECK(root != NULL);
DCHECK(arg != NULL);
MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
- // Sanity tests
- DCHECK(mark_sweep->live_bitmap_->Test(root));
- mark_sweep->MarkObject0(root, false);
+ // We do not need to mark since live == marked for image spaces.
mark_sweep->ScanObject(root);
}
@@ -146,7 +158,7 @@
DCHECK(root != NULL);
DCHECK(arg != NULL);
MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg);
- DCHECK(mark_sweep->IsMarked(root));
+ DCHECK(mark_sweep->heap_->GetMarkBitmap()->Test(root));
mark_sweep->CheckObject(root);
}
@@ -158,7 +170,7 @@
if (spaces[i]->IsImageSpace()) {
byte* begin = spaces[i]->Begin();
byte* end = spaces[i]->End();
- card_table->Scan(heap_->GetLiveBits(), begin, end, ScanImageRootVisitor, this);
+ card_table->Scan(spaces[i]->GetLiveBitmap(), begin, end, ScanImageRootVisitor, this);
}
}
}
@@ -191,16 +203,8 @@
for (size_t i = 0; i < spaces.size(); ++i) {
byte* begin = spaces[i]->Begin();
byte* end = spaces[i]->End();
- // Normally, we only need to scan the black dirty objects
- // But for image spaces, the roots will not be black objects.
- // To address this we just scan the live bits instead of the mark bits.
- if (spaces[i]->IsImageSpace()) {
- // Image roots may not be marked so we may need to mark them.
- // TODO: optimize this by offsetting some of the work to init.
- card_table->Scan(heap_->GetLiveBits(), begin, end, ScanImageRootVisitor, this);
- } else {
- card_table->Scan(heap_->GetMarkBits(), begin, end, ScanDirtyCardCallback, this);
- }
+ // Image spaces are handled properly since live == marked for them.
+ card_table->Scan(spaces[i]->GetMarkBitmap(), begin, end, ScanImageRootVisitor, this);
}
}
@@ -215,7 +219,9 @@
if (spaces[i]->IsImageSpace()) {
uintptr_t begin = reinterpret_cast<uintptr_t>(spaces[i]->Begin());
uintptr_t end = reinterpret_cast<uintptr_t>(spaces[i]->End());
- live_bitmap_->ScanWalk(begin, end, &MarkSweep::CheckBitmapCallback, arg);
+ SpaceBitmap* live_bitmap = spaces[i]->GetLiveBitmap();
+ DCHECK(live_bitmap != NULL);
+ live_bitmap->ScanWalk(begin, end, CheckBitmapCallback, arg);
}
}
finger_ = reinterpret_cast<Object*>(~0);
@@ -236,10 +242,11 @@
void* arg = reinterpret_cast<void*>(this);
const std::vector<Space*>& spaces = heap_->GetSpaces();
for (size_t i = 0; i < spaces.size(); ++i) {
- if (!spaces[i]->IsImageSpace()) {
+ if (spaces[i]->IsAllocSpace()) {
uintptr_t begin = reinterpret_cast<uintptr_t>(spaces[i]->Begin());
uintptr_t end = reinterpret_cast<uintptr_t>(spaces[i]->End());
- mark_bitmap_->ScanWalk(begin, end, &MarkSweep::ScanBitmapCallback, arg);
+ current_mark_bitmap_ = spaces[i]->GetMarkBitmap();
+ current_mark_bitmap_->ScanWalk(begin, end, &ScanBitmapCallback, arg);
}
}
finger_ = reinterpret_cast<Object*>(~0);
@@ -263,7 +270,7 @@
typedef IndirectReferenceTable::iterator It; // TODO: C++0x auto
for (It it = table->begin(), end = table->end(); it != end; ++it) {
const Object** entry = *it;
- if (!IsMarked(*entry)) {
+ if (!heap_->GetMarkBitmap()->Test(*entry)) {
*entry = kClearedJniWeakGlobal;
}
}
@@ -296,7 +303,7 @@
for (size_t i = 0; i < num_ptrs; ++i) {
Object* obj = static_cast<Object*>(ptrs[i]);
freed_bytes += space->AllocationSize(obj);
- heap->GetLiveBits()->Clear(obj);
+ heap->GetLiveBitmap()->Clear(obj);
}
// AllocSpace::FreeList clears the value in ptrs, so perform after clearing the live bit
space->FreeList(num_ptrs, ptrs);
@@ -304,7 +311,7 @@
for (size_t i = 0; i < num_ptrs; ++i) {
Object* obj = static_cast<Object*>(ptrs[i]);
freed_bytes += space->AllocationSize(obj);
- heap->GetLiveBits()->Clear(obj);
+ heap->GetLiveBitmap()->Clear(obj);
space->Free(obj);
}
}
@@ -325,7 +332,9 @@
uintptr_t begin = reinterpret_cast<uintptr_t>(spaces[i]->Begin());
uintptr_t end = reinterpret_cast<uintptr_t>(spaces[i]->End());
scc.space = spaces[i]->AsAllocSpace();
- HeapBitmap::SweepWalk(*live_bitmap_, *mark_bitmap_, begin, end,
+ SpaceBitmap* live_bitmap = scc.space->GetLiveBitmap();
+ SpaceBitmap* mark_bitmap = scc.space->GetMarkBitmap();
+ SpaceBitmap::SweepWalk(*live_bitmap, *mark_bitmap, begin, end,
&MarkSweep::SweepCallback, reinterpret_cast<void*>(&scc));
}
}
@@ -379,43 +388,46 @@
}
void MarkSweep::CheckReference(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) {
- AllocSpace* alloc_space = heap_->GetAllocSpace();
- if (alloc_space->Contains(ref)) {
- DCHECK(IsMarked(obj));
+ const Spaces& spaces = heap_->GetSpaces();
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
+ if ((*cur)->IsAllocSpace() && (*cur)->Contains(ref)) {
+ DCHECK(IsMarked(obj));
- bool is_marked = mark_bitmap_->Test(ref);
+ bool is_marked = IsMarked(ref);
+ if (!is_marked) {
+ LOG(INFO) << **cur;
+ LOG(WARNING) << (is_static ? "Static ref'" : "Instance ref'") << PrettyTypeOf(ref)
+ << "' (" << reinterpret_cast<const void*>(ref) << ") in '" << PrettyTypeOf(obj)
+ << "' (" << reinterpret_cast<const void*>(obj) << ") at offset "
+ << reinterpret_cast<void*>(offset.Int32Value()) << " wasn't marked";
- if (!is_marked) {
- LOG(INFO) << *alloc_space;
- LOG(WARNING) << (is_static ? "Static ref'" : "Instance ref'") << PrettyTypeOf(ref)
- << "' (" << reinterpret_cast<const void*>(ref) << ") in '" << PrettyTypeOf(obj)
- << "' (" << reinterpret_cast<const void*>(obj) << ") at offset "
- << reinterpret_cast<void*>(offset.Int32Value()) << " wasn't marked";
+ const Class* klass = is_static ? obj->AsClass() : obj->GetClass();
+ DCHECK(klass != NULL);
+ const ObjectArray<Field>* fields = is_static ? klass->GetSFields() : klass->GetIFields();
+ DCHECK(fields != NULL);
+ bool found = false;
+ for (int32_t i = 0; i < fields->GetLength(); ++i) {
+ const Field* cur = fields->Get(i);
+ if (cur->GetOffset().Int32Value() == offset.Int32Value()) {
+ LOG(WARNING) << "Field referencing the alloc space was " << PrettyField(cur);
+ found = true;
+ break;
+ }
+ }
+ if (!found) {
+ LOG(WARNING) << "Could not find field in object alloc space with offset " << offset.Int32Value();
+ }
- const Class* klass = is_static ? obj->AsClass() : obj->GetClass();
- DCHECK(klass != NULL);
- const ObjectArray<Field>* fields = is_static ? klass->GetSFields() : klass->GetIFields();
- DCHECK(fields != NULL);
- bool found = false;
- for (int32_t i = 0; i < fields->GetLength(); ++i) {
- const Field* cur = fields->Get(i);
- if (cur->GetOffset().Int32Value() == offset.Int32Value()) {
- LOG(WARNING) << "Field referencing the alloc space was " << PrettyField(cur);
- found = true;
- break;
+ bool obj_marked = heap_->GetCardTable()->IsDirty(obj);
+ if (!obj_marked) {
+ LOG(WARNING) << "Object '" << PrettyTypeOf(obj) << "' "
+ << "(" << reinterpret_cast<const void*>(obj) << ") contains references to "
+ << "the alloc space, but wasn't card marked";
}
}
- if (!found) {
- LOG(WARNING) << "Could not find field in object alloc space with offset " << offset.Int32Value();
- }
-
- bool obj_marked = heap_->GetCardTable()->IsDirty(obj);
- if (!obj_marked) {
- LOG(WARNING) << "Object '" << PrettyTypeOf(obj) << "' "
- << "(" << reinterpret_cast<const void*>(obj) << ") contains references to "
- << "the alloc space, but wasn't card marked";
- }
}
+ break;
}
}
@@ -489,7 +501,7 @@
inline void MarkSweep::ScanObject(const Object* obj) {
DCHECK(obj != NULL);
DCHECK(obj->GetClass() != NULL);
- DCHECK(IsMarked(obj));
+ DCHECK(heap_->GetMarkBitmap()->Test(obj));
if (obj->IsClass()) {
ScanClass(obj);
} else if (obj->IsArrayInstance()) {
@@ -501,12 +513,9 @@
// Scan anything that's on the mark stack.
void MarkSweep::ProcessMarkStack() {
- Space* alloc_space = heap_->GetAllocSpace();
while (!mark_stack_->IsEmpty()) {
const Object* obj = mark_stack_->Pop();
- if (alloc_space->Contains(obj)) {
- ScanObject(obj);
- }
+ ScanObject(obj);
}
}
@@ -634,7 +643,14 @@
#ifndef NDEBUG
VLOG(heap) << "MarkSweep scanned classes=" << class_count_ << " arrays=" << array_count_ << " other=" << other_count_;
#endif
- mark_bitmap_->Clear();
+ // Clear all of the alloc spaces' mark bitmaps.
+ const Spaces& spaces = heap_->GetSpaces();
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
+ if ((*cur)->IsAllocSpace()) {
+ (*cur)->GetMarkBitmap()->Clear();
+ }
+ }
mark_stack_->Reset();
}
diff --git a/src/mark_sweep.h b/src/mark_sweep.h
index 00fdcfb..28a5523 100644
--- a/src/mark_sweep.h
+++ b/src/mark_sweep.h
@@ -83,7 +83,10 @@
private:
// Returns true if the object has its bit set in the mark bitmap.
bool IsMarked(const Object* object) const {
- return mark_bitmap_->Test(object);
+ if (current_mark_bitmap_->HasAddress(object)) {
+ return current_mark_bitmap_->Test(object);
+ }
+ return heap_->GetMarkBitmap()->Test(object);
}
static bool IsMarked(const Object* object, void* arg) {
@@ -246,11 +249,12 @@
void SweepSystemWeaks();
void SweepJniWeakGlobals();
+ // Current space, we check this space first to avoid searching for the appropriate space for an object.
+ SpaceBitmap* current_mark_bitmap_;
+
MarkStack* mark_stack_;
Heap* heap_;
- HeapBitmap* mark_bitmap_;
- HeapBitmap* live_bitmap_;
Object* finger_;
diff --git a/src/mod_union_table.cc b/src/mod_union_table.cc
index c73dd6b..58b6a18 100644
--- a/src/mod_union_table.cc
+++ b/src/mod_union_table.cc
@@ -26,29 +26,34 @@
class MarkIfReachesAllocspaceVisitor {
public:
- explicit MarkIfReachesAllocspaceVisitor(MarkSweep* const mark_sweep, HeapBitmap* bitmap)
+ explicit MarkIfReachesAllocspaceVisitor(MarkSweep* const mark_sweep, SpaceBitmap* bitmap)
: mark_sweep_(mark_sweep),
bitmap_(bitmap) {
}
// Extra parameters are required since we use this same visitor signature for checking objects.
void operator ()(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) const {
- if (mark_sweep_->heap_->GetAllocSpace()->Contains(ref)) {
- // This can mark the same object multiple times, but is unlikely to be a performance problem.
- bitmap_->Set(obj);
+ // TODO: Optimize?
+ // TODO: C++0x auto
+ const Spaces& spaces = mark_sweep_->heap_->GetSpaces();
+ for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
+ if ((*cur)->IsAllocSpace() && (*cur)->Contains(ref)) {
+ bitmap_->Set(obj);
+ }
}
+
// Avoid warnings.
(void)obj;(void)offset;(void)is_static;
}
private:
MarkSweep* const mark_sweep_;
- HeapBitmap* bitmap_;
+ SpaceBitmap* bitmap_;
};
class ModUnionVisitor {
public:
- explicit ModUnionVisitor(MarkSweep* const mark_sweep, HeapBitmap* bitmap)
+ explicit ModUnionVisitor(MarkSweep* const mark_sweep, SpaceBitmap* bitmap)
: mark_sweep_(mark_sweep),
bitmap_(bitmap) {
}
@@ -62,7 +67,7 @@
}
private:
MarkSweep* const mark_sweep_;
- HeapBitmap* bitmap_;
+ SpaceBitmap* bitmap_;
};
class ModUnionClearCardVisitor {
@@ -96,7 +101,7 @@
if (spaces[i]->IsImageSpace()) {
// Allocate the mod-union table
// The mod-union table is only needed when we have an image space since it's purpose is to cache image roots.
- UniquePtr<HeapBitmap> bitmap(HeapBitmap::Create("mod-union table bitmap", spaces[i]->Begin(), spaces[i]->Capacity()));
+ UniquePtr<SpaceBitmap> bitmap(SpaceBitmap::Create("mod-union table bitmap", spaces[i]->Begin(), spaces[i]->Capacity()));
if (bitmap.get() == NULL) {
LOG(FATAL) << "Failed to create mod-union bitmap";
}
@@ -124,9 +129,11 @@
cleared_cards_.pop_back();
// Find out which bitmap the card maps to.
- HeapBitmap* bitmap = 0;
+ SpaceBitmap* bitmap = 0;
+ const Space* space = 0;
for (BitmapMap::iterator cur = bitmaps_.begin(); cur != bitmaps_.end(); ++cur) {
- if (cur->first->Contains(reinterpret_cast<Object*>(card_table->AddrFromCard(card)))) {
+ space = cur->first;
+ if (space->Contains(reinterpret_cast<Object*>(card_table->AddrFromCard(card)))) {
bitmap = cur->second;
break;
}
@@ -138,12 +145,12 @@
// Clear the mod-union bitmap range corresponding to this card so that we
// don't have any objects marked which do not reach the alloc space.
- bitmap->VisitRange(start, end, HeapBitmap::ClearVisitor(bitmap));
+ bitmap->VisitRange(start, end, SpaceBitmap::ClearVisitor(bitmap));
// At this point we need to update the mod-union bitmap to contain all the
// objects which reach the alloc space.
ModUnionVisitor visitor(mark_sweep, bitmap);
- heap_->GetLiveBits()->VisitMarkedRange(start, end, visitor);
+ space->GetLiveBitmap()->VisitMarkedRange(start, end, visitor);
}
}
diff --git a/src/mod_union_table.h b/src/mod_union_table.h
index 2f4ca5f..2d75a01 100644
--- a/src/mod_union_table.h
+++ b/src/mod_union_table.h
@@ -63,7 +63,7 @@
// One bitmap per image space.
// TODO: Add support for zygote spaces?
- typedef SafeMap<const Space*, HeapBitmap*> BitmapMap;
+ typedef SafeMap<Space*, SpaceBitmap*> BitmapMap;
BitmapMap bitmaps_;
Heap* heap_;
diff --git a/src/native/dalvik_system_DexFile.cc b/src/native/dalvik_system_DexFile.cc
index ef38f00..3e749e5 100644
--- a/src/native/dalvik_system_DexFile.cc
+++ b/src/native/dalvik_system_DexFile.cc
@@ -224,12 +224,20 @@
return JNI_TRUE;
}
- const ImageHeader& image_header = runtime->GetHeap()->GetImageSpace()->GetImageHeader();
- if (oat_file->GetOatHeader().GetImageFileLocationChecksum() != image_header.GetOatChecksum()) {
- LOG(INFO) << "DexFile_isDexOptNeeded cache file " << cache_location
- << " has out-of-date checksum compared to "
- << image_header.GetImageRoot(ImageHeader::kOatLocation)->AsString()->ToModifiedUtf8();
- return JNI_TRUE;
+ Heap* heap = runtime->GetHeap();
+ const Spaces& spaces = heap->GetSpaces();
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
+ if ((*cur)->IsImageSpace()) {
+ // TODO: Ensure this works with multiple image spaces.
+ const ImageHeader& image_header = (*cur)->AsImageSpace()->GetImageHeader();
+ if (oat_file->GetOatHeader().GetImageFileLocationChecksum() != image_header.GetOatChecksum()) {
+ LOG(INFO) << "DexFile_isDexOptNeeded cache file " << cache_location
+ << " has out-of-date checksum compared to "
+ << image_header.GetImageRoot(ImageHeader::kOatLocation)->AsString()->ToModifiedUtf8();
+ return JNI_TRUE;
+ }
+ }
}
uint32_t location_checksum;
diff --git a/src/native/dalvik_system_VMRuntime.cc b/src/native/dalvik_system_VMRuntime.cc
index 417ae5b..4ec1b92 100644
--- a/src/native/dalvik_system_VMRuntime.cc
+++ b/src/native/dalvik_system_VMRuntime.cc
@@ -164,23 +164,27 @@
// Trim the managed heap.
Heap* heap = Runtime::Current()->GetHeap();
- size_t alloc_space_size = heap->GetAllocSpace()->Size();
- float utilization = static_cast<float>(heap->GetBytesAllocated()) / alloc_space_size;
- uint64_t start_ns = NanoTime();
-
- heap->Trim();
-
- // Trim the native heap.
- dlmalloc_trim(0);
+ const Spaces& spaces = heap->GetSpaces();
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
+ if ((*cur)->IsAllocSpace()) {
+ uint64_t start_ns = NanoTime();
+ AllocSpace* alloc_space = (*cur)->AsAllocSpace();
+ size_t alloc_space_size = alloc_space->Size();
+ float utilization = static_cast<float>(heap->GetBytesAllocated()) / alloc_space_size;
+ heap->Trim(alloc_space);
+ // Trim the native heap.
+ dlmalloc_trim(0);
#if 0 // TODO: switch over to this when bionic has moved to dlmalloc 2.8.5
- dlmalloc_inspect_all(MspaceMadviseCallback, NULL);
+ dlmalloc_inspect_all(MspaceMadviseCallback, NULL);
#else
- dlmalloc_walk_free_pages(MspaceMadviseCallback, NULL);
+ dlmalloc_walk_free_pages(MspaceMadviseCallback, NULL);
#endif
-
- LOG(INFO) << "Parallel heap trimming took " << PrettyDuration(NanoTime() - start_ns)
- << " on a " << PrettySize(alloc_space_size)
- << " heap with " << static_cast<int>(100 * utilization) << "% utilization";
+ LOG(INFO) << "Parallel heap trimming took " << PrettyDuration(NanoTime() - start_ns)
+ << " on a " << PrettySize(alloc_space_size)
+ << " alloc space with " << static_cast<int>(100 * utilization) << "% utilization";
+ }
+ }
}
static void VMRuntime_concurrentGC(JNIEnv*, jobject) {
diff --git a/src/oatdump.cc b/src/oatdump.cc
index 9bae0d9..b1aa47e 100644
--- a/src/oatdump.cc
+++ b/src/oatdump.cc
@@ -552,10 +552,15 @@
oat_dumper_.reset(new OatDumper(host_prefix_, *oat_file));
os_ << "OBJECTS:\n" << std::flush;
- HeapBitmap* heap_bitmap = Runtime::Current()->GetHeap()->GetLiveBits();
- DCHECK(heap_bitmap != NULL);
- heap_bitmap->Walk(ImageDumper::Callback, this);
- os_ << "\n";
+
+ // Loop through all the image spaces and dump their objects.
+ Heap* heap = Runtime::Current()->GetHeap();
+ const Spaces& spaces = heap->GetSpaces();
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
+ (*cur)->GetLiveBitmap()->Walk(ImageDumper::Callback, this);
+ os_ << "\n";
+ }
os_ << "STATS:\n" << std::flush;
UniquePtr<File> file(OS::OpenFile(image_filename_.c_str(), false));
diff --git a/src/space.cc b/src/space.cc
index 4600443..569a0c9 100644
--- a/src/space.cc
+++ b/src/space.cc
@@ -22,6 +22,7 @@
#include "image.h"
#include "logging.h"
#include "os.h"
+#include "stl_util.h"
#include "utils.h"
namespace art {
@@ -39,6 +40,26 @@
} \
} while (false)
+size_t AllocSpace::bitmap_index_ = 0;
+
+AllocSpace::AllocSpace(const std::string& name, MemMap* mem_map, void* mspace, byte* end,
+ size_t growth_limit)
+ : Space(name, mem_map, end), mspace_(mspace), growth_limit_(growth_limit) {
+ CHECK(mspace != NULL);
+
+ size_t bitmap_index = bitmap_index_++;
+
+ live_bitmap_.reset(SpaceBitmap::Create(
+ StringPrintf("allocspace-%s-live-bitmap-%d", name.c_str(), static_cast<int>(bitmap_index)),
+ Begin(), Capacity()));
+ DCHECK(live_bitmap_.get() != NULL) << "could not create allocspace live bitmap #" << bitmap_index;
+
+ mark_bitmap_.reset(SpaceBitmap::Create(
+ StringPrintf("allocspace-%s-mark-bitmap-%d", name.c_str(), static_cast<int>(bitmap_index)),
+ Begin(), Capacity()));
+ DCHECK(live_bitmap_.get() != NULL) << "could not create allocspace mark bitmap #" << bitmap_index;
+}
+
AllocSpace* Space::CreateAllocSpace(const std::string& name, size_t initial_size,
size_t growth_limit, size_t capacity,
byte* requested_begin) {
@@ -175,24 +196,25 @@
// Callback from dlmalloc when it needs to increase the footprint
extern "C" void* art_heap_morecore(void* mspace, intptr_t increment) {
Heap* heap = Runtime::Current()->GetHeap();
- AllocSpace* space = heap->GetAllocSpace();
- if (LIKELY(space->GetMspace() == mspace)) {
- return space->MoreCore(increment);
+ if (heap->GetAllocSpace()->GetMspace() == mspace) {
+ return heap->GetAllocSpace()->MoreCore(increment);
} else {
- // Exhaustively search alloc spaces
- const std::vector<Space*>& spaces = heap->GetSpaces();
- for (size_t i = 0; i < spaces.size(); ++i) {
- if (spaces[i]->IsAllocSpace()) {
- AllocSpace* space = spaces[i]->AsAllocSpace();
+ // Exhaustively search alloc spaces.
+ const Spaces& spaces = heap->GetSpaces();
+ // TODO: C++0x auto
+ for (Spaces::const_iterator cur = spaces.begin(); cur != spaces.end(); ++cur) {
+ if ((*cur)->IsAllocSpace()) {
+ AllocSpace* space = (*cur)->AsAllocSpace();
if (mspace == space->GetMspace()) {
return space->MoreCore(increment);
}
}
}
- LOG(FATAL) << "Unexpected call to art_heap_morecore. mspace: " << mspace
- << " increment: " << increment;
- return NULL;
}
+
+ LOG(FATAL) << "Unexpected call to art_heap_morecore. mspace: " << mspace
+ << " increment: " << increment;
+ return NULL;
}
void* AllocSpace::MoreCore(intptr_t increment) {
@@ -278,6 +300,17 @@
mspace_set_footprint_limit(mspace_, new_size);
}
+size_t ImageSpace::bitmap_index_ = 0;
+
+ImageSpace::ImageSpace(const std::string& name, MemMap* mem_map)
+ : Space(name, mem_map, mem_map->End()) {
+ const size_t bitmap_index = bitmap_index_++;
+ live_bitmap_.reset(SpaceBitmap::Create(
+ StringPrintf("imagespace-%s-live-bitmap-%d", name.c_str(), static_cast<int>(bitmap_index)),
+ Begin(), Capacity()));
+ DCHECK(live_bitmap_.get() != NULL) << "could not create imagespace live bitmap #" << bitmap_index;
+}
+
ImageSpace* Space::CreateImageSpace(const std::string& image_file_name) {
CHECK(!image_file_name.empty());
@@ -345,7 +378,7 @@
return space;
}
-void ImageSpace::RecordImageAllocations(HeapBitmap* live_bitmap) const {
+void ImageSpace::RecordImageAllocations(SpaceBitmap* live_bitmap) const {
uint64_t start_time = 0;
if (VLOG_IS_ON(heap) || VLOG_IS_ON(startup)) {
LOG(INFO) << "ImageSpace::RecordImageAllocations entering";
diff --git a/src/space.h b/src/space.h
index 76d4817..ff16a51 100644
--- a/src/space.h
+++ b/src/space.h
@@ -31,6 +31,7 @@
class AllocSpace;
class ImageSpace;
class Object;
+class SpaceBitmap;
// A space contains memory allocated for managed objects.
class Space {
@@ -97,11 +98,19 @@
virtual bool IsAllocSpace() const = 0;
virtual bool IsImageSpace() const = 0;
+ virtual SpaceBitmap* GetLiveBitmap() const = 0;
+ virtual SpaceBitmap* GetMarkBitmap() const = 0;
+
+ const std::string GetName() const {
+ return name_;
+ }
+
protected:
Space(const std::string& name, MemMap* mem_map, byte* end)
: name_(name), mem_map_(mem_map), begin_(mem_map->Begin()), end_(end) {}
std::string name_;
+
// Underlying storage of the space
UniquePtr<MemMap> mem_map_;
@@ -178,14 +187,23 @@
return false;
}
+ virtual SpaceBitmap* GetLiveBitmap() const {
+ return live_bitmap_.get();
+ }
+
+ virtual SpaceBitmap* GetMarkBitmap() const {
+ return mark_bitmap_.get();
+ }
+
private:
friend class Space;
+ UniquePtr<SpaceBitmap> live_bitmap_;
+ UniquePtr<SpaceBitmap> mark_bitmap_;
+ static size_t bitmap_index_;
+
AllocSpace(const std::string& name, MemMap* mem_map, void* mspace, byte* end,
- size_t growth_limit)
- : Space(name, mem_map, end), mspace_(mspace), growth_limit_(growth_limit) {
- CHECK(mspace != NULL);
- }
+ size_t growth_limit);
bool Init(size_t initial_size, size_t maximum_size, size_t growth_size, byte* requested_base);
@@ -221,7 +239,7 @@
}
// Mark the objects defined in this space in the given live bitmap
- void RecordImageAllocations(HeapBitmap* live_bitmap) const;
+ void RecordImageAllocations(SpaceBitmap* live_bitmap) const;
virtual bool IsAllocSpace() const {
return false;
@@ -231,11 +249,20 @@
return true;
}
+ virtual SpaceBitmap* GetLiveBitmap() const {
+ return live_bitmap_.get();
+ }
+
+ virtual SpaceBitmap* GetMarkBitmap() const {
+ return live_bitmap_.get();
+ }
private:
friend class Space;
- ImageSpace(const std::string& name, MemMap* mem_map)
- : Space(name, mem_map, mem_map->End()) {}
+ UniquePtr<SpaceBitmap> live_bitmap_;
+ static size_t bitmap_index_;
+
+ ImageSpace(const std::string& name, MemMap* mem_map);
DISALLOW_COPY_AND_ASSIGN(ImageSpace);
};
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
diff --git a/src/space_bitmap.h b/src/space_bitmap.h
new file mode 100644
index 0000000..fa79d5d
--- /dev/null
+++ b/src/space_bitmap.h
@@ -0,0 +1,192 @@
+/*
+ * 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_SRC_SPACE_BITMAP_H_
+#define ART_SRC_SPACE_BITMAP_H_
+
+#include <limits.h>
+#include <stdint.h>
+#include <vector>
+
+#include "UniquePtr.h"
+#include "globals.h"
+#include "logging.h"
+#include "mem_map.h"
+#include "utils.h"
+
+namespace art {
+
+class Object;
+
+class SpaceBitmap {
+ public:
+ static const size_t kAlignment = 8;
+
+ typedef void Callback(Object* obj, void* arg);
+
+ typedef void ScanCallback(Object* obj, void* finger, void* arg);
+
+ typedef void SweepCallback(size_t ptr_count, Object** ptrs, void* arg);
+
+ // Initialize a HeapBitmap so that it points to a bitmap large enough to cover a heap at
+ // heap_begin of heap_capacity bytes, where objects are guaranteed to be kAlignment-aligned.
+ static SpaceBitmap* Create(const std::string& name, byte* heap_begin, size_t heap_capacity);
+
+ ~SpaceBitmap();
+
+ // <offset> is the difference from .base to a pointer address.
+ // <index> is the index of .bits that contains the bit representing
+ // <offset>.
+ static size_t OffsetToIndex(size_t offset) {
+ return offset / kAlignment / kBitsPerWord;
+ }
+
+ static uintptr_t IndexToOffset(size_t index) {
+ return static_cast<uintptr_t>(index * kAlignment * kBitsPerWord);
+ }
+
+ // Pack the bits in backwards so they come out in address order when using CLZ.
+ static word OffsetToMask(uintptr_t offset_) {
+ return 1 << (sizeof(word) * 8 - 1 - (offset_ / kAlignment) % kBitsPerWord);
+ }
+
+ inline void Set(const Object* obj) {
+ Modify(obj, true);
+ }
+
+ inline void Clear(const Object* obj) {
+ Modify(obj, false);
+ }
+
+ void Clear();
+
+ inline bool Test(const Object* obj) const {
+ uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
+ DCHECK(HasAddress(obj)) << obj;
+ DCHECK(bitmap_begin_ != NULL);
+ DCHECK_GE(addr, heap_begin_);
+ if (addr <= heap_end_) {
+ const uintptr_t offset = addr - heap_begin_;
+ return (bitmap_begin_[OffsetToIndex(offset)] & OffsetToMask(offset)) != 0;
+ } else {
+ return false;
+ }
+ }
+
+ bool HasAddress(const void* addr) const;
+
+ void VisitRange(uintptr_t base, uintptr_t max, Callback* visitor, void* arg) const;
+
+ class ClearVisitor {
+ public:
+ explicit ClearVisitor(SpaceBitmap* const bitmap)
+ : bitmap_(bitmap) {
+ }
+
+ void operator ()(Object* obj) const {
+ bitmap_->Clear(obj);
+ }
+ private:
+ SpaceBitmap* const bitmap_;
+ };
+
+ template <typename Visitor>
+ void VisitRange(uintptr_t visit_begin, uintptr_t visit_end, const Visitor& visitor) const {
+ for (; visit_begin < visit_end; visit_begin += kAlignment ) {
+ visitor(reinterpret_cast<Object*>(visit_begin));
+ }
+ }
+
+ template <typename Visitor>
+ void VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end, const Visitor& visitor) 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_;
+ do {
+ const int shift = CLZ(w);
+ Object* obj = reinterpret_cast<Object*>(ptr_base + shift * kAlignment);
+ visitor(obj);
+ w &= ~(high_bit >> shift);
+ } while (w != 0);
+ }
+ }
+ }
+
+ void Walk(Callback* callback, void* arg);
+
+ void InOrderWalk(Callback* callback, void* arg);
+
+ void ScanWalk(uintptr_t base, uintptr_t max, ScanCallback* thunk, void* arg);
+
+ static void SweepWalk(const SpaceBitmap& live,
+ const SpaceBitmap& mark,
+ uintptr_t base, uintptr_t max,
+ SweepCallback* thunk, void* arg);
+
+ private:
+ // TODO: heap_end_ is initialized so that the heap bitmap is empty, this doesn't require the -1,
+ // however, we document that this is expected on heap_end_
+ SpaceBitmap(const std::string& name, MemMap* mem_map, word* bitmap_begin, size_t bitmap_size, const void* heap_begin)
+ : mem_map_(mem_map), bitmap_begin_(bitmap_begin), bitmap_size_(bitmap_size),
+ heap_begin_(reinterpret_cast<uintptr_t>(heap_begin)), heap_end_(heap_begin_ - 1),
+ name_(name) {}
+
+ inline void Modify(const Object* obj, bool do_set) {
+ 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 word mask = OffsetToMask(offset);
+ DCHECK_LT(index, bitmap_size_ / kWordSize) << " bitmap_size_ = " << bitmap_size_;
+ if (do_set) {
+ if (addr > heap_end_) {
+ heap_end_ = addr;
+ }
+ bitmap_begin_[index] |= mask;
+ } else {
+ bitmap_begin_[index] &= ~mask;
+ }
+ }
+
+ // Backing storage for bitmap.
+ UniquePtr<MemMap> mem_map_;
+
+ // This bitmap itself, word sized for efficiency in scanning.
+ word* const bitmap_begin_;
+
+ // Size of this bitmap.
+ const size_t bitmap_size_;
+
+ // The base address of the heap, which corresponds to the word containing the first bit in the
+ // bitmap.
+ const uintptr_t heap_begin_;
+
+ // The highest pointer value ever returned by an allocation from
+ // this heap. I.e., the highest address that may correspond to a
+ // set bit. If there are no bits set, (heap_end_ < heap_begin_).
+ uintptr_t heap_end_;
+
+ // Name of this bitmap.
+ std::string name_;
+};
+
+} // namespace art
+
+#endif // ART_SRC_SPACE_BITMAP_H_
