diff options
| -rw-r--r-- | runtime/gc/heap.cc | 7 | ||||
| -rw-r--r-- | runtime/gc/heap.h | 1 | ||||
| -rw-r--r-- | runtime/gc/space/large_object_space.cc | 308 | ||||
| -rw-r--r-- | runtime/gc/space/large_object_space.h | 153 | ||||
| -rw-r--r-- | runtime/gc/space/large_object_space_test.cc | 2 |
5 files changed, 244 insertions, 227 deletions
diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc index 2048160378..bb7da0d13d 100644 --- a/runtime/gc/heap.cc +++ b/runtime/gc/heap.cc @@ -83,8 +83,13 @@ static constexpr size_t kMaxConcurrentRemainingBytes = 512 * KB; // relative to partial/full GC. This may be desirable since sticky GCs interfere less with mutator // threads (lower pauses, use less memory bandwidth). static constexpr double kStickyGcThroughputAdjustment = 1.0; -// Whether or not we use the free list large object space. +// Whether or not we use the free list large object space. Only use it if USE_ART_LOW_4G_ALLOCATOR +// since this means that we have to use the slow msync loop in MemMap::MapAnonymous. +#if USE_ART_LOW_4G_ALLOCATOR +static constexpr bool kUseFreeListSpaceForLOS = true; +#else static constexpr bool kUseFreeListSpaceForLOS = false; +#endif // Whether or not we compact the zygote in PreZygoteFork. static constexpr bool kCompactZygote = kMovingCollector; // How many reserve entries are at the end of the allocation stack, these are only needed if the diff --git a/runtime/gc/heap.h b/runtime/gc/heap.h index 9742277b26..e775965f06 100644 --- a/runtime/gc/heap.h +++ b/runtime/gc/heap.h @@ -131,7 +131,6 @@ class Heap { static constexpr bool kMeasureAllocationTime = false; // Primitive arrays larger than this size are put in the large object space. static constexpr size_t kDefaultLargeObjectThreshold = 3 * kPageSize; - static constexpr size_t kDefaultStartingSize = kPageSize; static constexpr size_t kDefaultInitialSize = 2 * MB; static constexpr size_t kDefaultMaximumSize = 256 * MB; diff --git a/runtime/gc/space/large_object_space.cc b/runtime/gc/space/large_object_space.cc index d5a03c66ec..2a4371290f 100644 --- a/runtime/gc/space/large_object_space.cc +++ b/runtime/gc/space/large_object_space.cc @@ -192,6 +192,96 @@ bool LargeObjectMapSpace::Contains(const mirror::Object* obj) const { } } +// Keeps track of allocation sizes + whether or not the previous allocation is free. +// Used to coalesce free blocks and find the best fit block for an allocation. +class AllocationInfo { + public: + AllocationInfo() : prev_free_(0), alloc_size_(0) { + } + // Return the number of pages that the allocation info covers. + size_t AlignSize() const { + return alloc_size_ & ~kFlagFree; + } + // Returns the allocation size in bytes. + size_t ByteSize() const { + return AlignSize() * FreeListSpace::kAlignment; + } + // Updates the allocation size and whether or not it is free. + void SetByteSize(size_t size, bool free) { + DCHECK_ALIGNED(size, FreeListSpace::kAlignment); + alloc_size_ = (size / FreeListSpace::kAlignment) | (free ? kFlagFree : 0U); + } + bool IsFree() const { + return (alloc_size_ & kFlagFree) != 0; + } + // Finds and returns the next non free allocation info after ourself. + AllocationInfo* GetNextInfo() { + return this + AlignSize(); + } + const AllocationInfo* GetNextInfo() const { + return this + AlignSize(); + } + // Returns the previous free allocation info by using the prev_free_ member to figure out + // where it is. This is only used for coalescing so we only need to be able to do it if the + // previous allocation info is free. + AllocationInfo* GetPrevFreeInfo() { + DCHECK_NE(prev_free_, 0U); + return this - prev_free_; + } + // Returns the address of the object associated with this allocation info. + mirror::Object* GetObjectAddress() { + return reinterpret_cast<mirror::Object*>(reinterpret_cast<uintptr_t>(this) + sizeof(*this)); + } + // Return how many kAlignment units there are before the free block. + size_t GetPrevFree() const { + return prev_free_; + } + // Returns how many free bytes there is before the block. + size_t GetPrevFreeBytes() const { + return GetPrevFree() * FreeListSpace::kAlignment; + } + // Update the size of the free block prior to the allocation. + void SetPrevFreeBytes(size_t bytes) { + DCHECK_ALIGNED(bytes, FreeListSpace::kAlignment); + prev_free_ = bytes / FreeListSpace::kAlignment; + } + + private: + // Used to implement best fit object allocation. Each allocation has an AllocationInfo which + // contains the size of the previous free block preceding it. Implemented in such a way that we + // can also find the iterator for any allocation info pointer. + static constexpr uint32_t kFlagFree = 0x8000000; + // Contains the size of the previous free block with kAlignment as the unit. If 0 then the + // allocation before us is not free. + // These variables are undefined in the middle of allocations / free blocks. + uint32_t prev_free_; + // Allocation size of this object in kAlignment as the unit. + uint32_t alloc_size_; +}; + +size_t FreeListSpace::GetSlotIndexForAllocationInfo(const AllocationInfo* info) const { + DCHECK_GE(info, allocation_info_); + DCHECK_LT(info, reinterpret_cast<AllocationInfo*>(allocation_info_map_->End())); + return info - allocation_info_; +} + +AllocationInfo* FreeListSpace::GetAllocationInfoForAddress(uintptr_t address) { + return &allocation_info_[GetSlotIndexForAddress(address)]; +} + +const AllocationInfo* FreeListSpace::GetAllocationInfoForAddress(uintptr_t address) const { + return &allocation_info_[GetSlotIndexForAddress(address)]; +} + +inline bool FreeListSpace::SortByPrevFree::operator()(const AllocationInfo* a, + const AllocationInfo* b) const { + if (a->GetPrevFree() < b->GetPrevFree()) return true; + if (a->GetPrevFree() > b->GetPrevFree()) return false; + if (a->AlignSize() < b->AlignSize()) return true; + if (a->AlignSize() > b->AlignSize()) return false; + return reinterpret_cast<uintptr_t>(a) < reinterpret_cast<uintptr_t>(b); +} + FreeListSpace* FreeListSpace::Create(const std::string& name, byte* requested_begin, size_t size) { CHECK_EQ(size % kAlignment, 0U); std::string error_msg; @@ -205,112 +295,113 @@ FreeListSpace::FreeListSpace(const std::string& name, MemMap* mem_map, byte* beg : LargeObjectSpace(name, begin, end), mem_map_(mem_map), lock_("free list space lock", kAllocSpaceLock) { - free_end_ = end - begin; + const size_t space_capacity = end - begin; + free_end_ = space_capacity; + CHECK_ALIGNED(space_capacity, kAlignment); + const size_t alloc_info_size = sizeof(AllocationInfo) * (space_capacity / kAlignment); + std::string error_msg; + allocation_info_map_.reset(MemMap::MapAnonymous("large object free list space allocation info map", + nullptr, alloc_info_size, PROT_READ | PROT_WRITE, + false, &error_msg)); + CHECK(allocation_info_map_.get() != nullptr) << "Failed to allocate allocation info map" + << error_msg; + allocation_info_ = reinterpret_cast<AllocationInfo*>(allocation_info_map_->Begin()); } FreeListSpace::~FreeListSpace() {} void FreeListSpace::Walk(DlMallocSpace::WalkCallback callback, void* arg) { MutexLock mu(Thread::Current(), lock_); - uintptr_t free_end_start = reinterpret_cast<uintptr_t>(end_) - free_end_; - AllocationHeader* cur_header = reinterpret_cast<AllocationHeader*>(Begin()); - while (reinterpret_cast<uintptr_t>(cur_header) < free_end_start) { - cur_header = cur_header->GetNextNonFree(); - size_t alloc_size = cur_header->AllocationSize(); - byte* byte_start = reinterpret_cast<byte*>(cur_header->GetObjectAddress()); - byte* byte_end = byte_start + alloc_size - sizeof(AllocationHeader); - callback(byte_start, byte_end, alloc_size, arg); - callback(NULL, NULL, 0, arg); - cur_header = reinterpret_cast<AllocationHeader*>(byte_end); + const uintptr_t free_end_start = reinterpret_cast<uintptr_t>(end_) - free_end_; + AllocationInfo* cur_info = &allocation_info_[0]; + const AllocationInfo* end_info = GetAllocationInfoForAddress(free_end_start); + while (cur_info < end_info) { + if (!cur_info->IsFree()) { + size_t alloc_size = cur_info->ByteSize(); + byte* byte_start = reinterpret_cast<byte*>(GetAddressForAllocationInfo(cur_info)); + byte* byte_end = byte_start + alloc_size; + callback(byte_start, byte_end, alloc_size, arg); + callback(nullptr, nullptr, 0, arg); + } + cur_info = cur_info->GetNextInfo(); } + CHECK_EQ(cur_info, end_info); } -void FreeListSpace::RemoveFreePrev(AllocationHeader* header) { - CHECK(!header->IsFree()); - CHECK_GT(header->GetPrevFree(), size_t(0)); - FreeBlocks::iterator found = free_blocks_.lower_bound(header); - CHECK(found != free_blocks_.end()); - CHECK_EQ(*found, header); - free_blocks_.erase(found); -} - -FreeListSpace::AllocationHeader* FreeListSpace::GetAllocationHeader(const mirror::Object* obj) { - DCHECK(Contains(obj)); - return reinterpret_cast<AllocationHeader*>(reinterpret_cast<uintptr_t>(obj) - - sizeof(AllocationHeader)); -} - -FreeListSpace::AllocationHeader* FreeListSpace::AllocationHeader::GetNextNonFree() { - // We know that there has to be at least one object after us or else we would have - // coalesced with the free end region. May be worth investigating a better way to do this - // as it may be expensive for large allocations. - for (uintptr_t pos = reinterpret_cast<uintptr_t>(this);; pos += kAlignment) { - AllocationHeader* cur = reinterpret_cast<AllocationHeader*>(pos); - if (!cur->IsFree()) return cur; - } +void FreeListSpace::RemoveFreePrev(AllocationInfo* info) { + CHECK_GT(info->GetPrevFree(), 0U); + auto it = free_blocks_.lower_bound(info); + CHECK(it != free_blocks_.end()); + CHECK_EQ(*it, info); + free_blocks_.erase(it); } size_t FreeListSpace::Free(Thread* self, mirror::Object* obj) { MutexLock mu(self, lock_); - DCHECK(Contains(obj)); - AllocationHeader* header = GetAllocationHeader(obj); - CHECK(IsAligned<kAlignment>(header)); - size_t allocation_size = header->AllocationSize(); - DCHECK_GT(allocation_size, size_t(0)); - DCHECK(IsAligned<kAlignment>(allocation_size)); + DCHECK(Contains(obj)) << reinterpret_cast<void*>(Begin()) << " " << obj << " " + << reinterpret_cast<void*>(End()); + DCHECK_ALIGNED(obj, kAlignment); + AllocationInfo* info = GetAllocationInfoForAddress(reinterpret_cast<uintptr_t>(obj)); + DCHECK(!info->IsFree()); + const size_t allocation_size = info->ByteSize(); + DCHECK_GT(allocation_size, 0U); + DCHECK_ALIGNED(allocation_size, kAlignment); + info->SetByteSize(allocation_size, true); // Mark as free. // Look at the next chunk. - AllocationHeader* next_header = header->GetNextAllocationHeader(); + AllocationInfo* next_info = info->GetNextInfo(); // Calculate the start of the end free block. uintptr_t free_end_start = reinterpret_cast<uintptr_t>(end_) - free_end_; - size_t header_prev_free = header->GetPrevFree(); + size_t prev_free_bytes = info->GetPrevFreeBytes(); size_t new_free_size = allocation_size; - if (header_prev_free) { - new_free_size += header_prev_free; - RemoveFreePrev(header); + if (prev_free_bytes != 0) { + // Coalesce with previous free chunk. + new_free_size += prev_free_bytes; + RemoveFreePrev(info); + info = info->GetPrevFreeInfo(); + // The previous allocation info must not be free since we are supposed to always coalesce. + DCHECK_EQ(info->GetPrevFreeBytes(), 0U) << "Previous allocation was free"; } - if (reinterpret_cast<uintptr_t>(next_header) >= free_end_start) { + uintptr_t next_addr = GetAddressForAllocationInfo(next_info); + if (next_addr >= free_end_start) { // Easy case, the next chunk is the end free region. - CHECK_EQ(reinterpret_cast<uintptr_t>(next_header), free_end_start); + CHECK_EQ(next_addr, free_end_start); free_end_ += new_free_size; } else { - AllocationHeader* new_free_header; - DCHECK(IsAligned<kAlignment>(next_header)); - if (next_header->IsFree()) { - // Find the next chunk by reading each page until we hit one with non-zero chunk. - AllocationHeader* next_next_header = next_header->GetNextNonFree(); - DCHECK(IsAligned<kAlignment>(next_next_header)); - DCHECK(IsAligned<kAlignment>(next_next_header->AllocationSize())); - RemoveFreePrev(next_next_header); - new_free_header = next_next_header; - new_free_size += next_next_header->GetPrevFree(); + AllocationInfo* new_free_info; + if (next_info->IsFree()) { + AllocationInfo* next_next_info = next_info->GetNextInfo(); + // Next next info can't be free since we always coalesce. + DCHECK(!next_next_info->IsFree()); + DCHECK(IsAligned<kAlignment>(next_next_info->ByteSize())); + new_free_info = next_next_info; + new_free_size += next_next_info->GetPrevFreeBytes(); + RemoveFreePrev(next_next_info); } else { - new_free_header = next_header; + new_free_info = next_info; } - new_free_header->prev_free_ = new_free_size; - free_blocks_.insert(new_free_header); + new_free_info->SetPrevFreeBytes(new_free_size); + free_blocks_.insert(new_free_info); + info->SetByteSize(new_free_size, true); + DCHECK_EQ(info->GetNextInfo(), new_free_info); } --num_objects_allocated_; DCHECK_LE(allocation_size, num_bytes_allocated_); num_bytes_allocated_ -= allocation_size; - madvise(header, allocation_size, MADV_DONTNEED); + madvise(obj, allocation_size, MADV_DONTNEED); if (kIsDebugBuild) { // Can't disallow reads since we use them to find next chunks during coalescing. - mprotect(header, allocation_size, PROT_READ); + mprotect(obj, allocation_size, PROT_READ); } return allocation_size; } -bool FreeListSpace::Contains(const mirror::Object* obj) const { - return mem_map_->HasAddress(obj); -} - size_t FreeListSpace::AllocationSize(mirror::Object* obj, size_t* usable_size) { - AllocationHeader* header = GetAllocationHeader(obj); DCHECK(Contains(obj)); - DCHECK(!header->IsFree()); - size_t alloc_size = header->AllocationSize(); + AllocationInfo* info = GetAllocationInfoForAddress(reinterpret_cast<uintptr_t>(obj)); + DCHECK(!info->IsFree()); + size_t alloc_size = info->ByteSize(); if (usable_size != nullptr) { - *usable_size = alloc_size - sizeof(AllocationHeader); + *usable_size = alloc_size; } return alloc_size; } @@ -318,56 +409,56 @@ size_t FreeListSpace::AllocationSize(mirror::Object* obj, size_t* usable_size) { mirror::Object* FreeListSpace::Alloc(Thread* self, size_t num_bytes, size_t* bytes_allocated, size_t* usable_size) { MutexLock mu(self, lock_); - size_t allocation_size = RoundUp(num_bytes + sizeof(AllocationHeader), kAlignment); - AllocationHeader temp; - temp.SetPrevFree(allocation_size); - temp.SetAllocationSize(0); - AllocationHeader* new_header; + const size_t allocation_size = RoundUp(num_bytes, kAlignment); + AllocationInfo temp_info; + temp_info.SetPrevFreeBytes(allocation_size); + temp_info.SetByteSize(0, false); + AllocationInfo* new_info; // Find the smallest chunk at least num_bytes in size. - FreeBlocks::iterator found = free_blocks_.lower_bound(&temp); - if (found != free_blocks_.end()) { - AllocationHeader* header = *found; - free_blocks_.erase(found); - - // Fit our object in the previous free header space. - new_header = header->GetPrevFreeAllocationHeader(); - - // Remove the newly allocated block from the header and update the prev_free_. - header->prev_free_ -= allocation_size; - if (header->prev_free_ > 0) { + auto it = free_blocks_.lower_bound(&temp_info); + if (it != free_blocks_.end()) { + AllocationInfo* info = *it; + free_blocks_.erase(it); + // Fit our object in the previous allocation info free space. + new_info = info->GetPrevFreeInfo(); + // Remove the newly allocated block from the info and update the prev_free_. + info->SetPrevFreeBytes(info->GetPrevFreeBytes() - allocation_size); + if (info->GetPrevFreeBytes() > 0) { + AllocationInfo* new_free = info - info->GetPrevFree(); + new_free->SetPrevFreeBytes(0); + new_free->SetByteSize(info->GetPrevFreeBytes(), true); // If there is remaining space, insert back into the free set. - free_blocks_.insert(header); + free_blocks_.insert(info); } } else { // Try to steal some memory from the free space at the end of the space. if (LIKELY(free_end_ >= allocation_size)) { // Fit our object at the start of the end free block. - new_header = reinterpret_cast<AllocationHeader*>(end_ - free_end_); + new_info = GetAllocationInfoForAddress(reinterpret_cast<uintptr_t>(End()) - free_end_); free_end_ -= allocation_size; } else { return nullptr; } } - DCHECK(bytes_allocated != nullptr); *bytes_allocated = allocation_size; if (usable_size != nullptr) { - *usable_size = allocation_size - sizeof(AllocationHeader); + *usable_size = allocation_size; } // Need to do these inside of the lock. ++num_objects_allocated_; ++total_objects_allocated_; num_bytes_allocated_ += allocation_size; total_bytes_allocated_ += allocation_size; - + mirror::Object* obj = reinterpret_cast<mirror::Object*>(GetAddressForAllocationInfo(new_info)); // We always put our object at the start of the free block, there can not be another free block // before it. if (kIsDebugBuild) { - mprotect(new_header, allocation_size, PROT_READ | PROT_WRITE); + mprotect(obj, allocation_size, PROT_READ | PROT_WRITE); } - new_header->SetPrevFree(0); - new_header->SetAllocationSize(allocation_size); - return new_header->GetObjectAddress(); + new_info->SetPrevFreeBytes(0); + new_info->SetByteSize(allocation_size, false); + return obj; } void FreeListSpace::Dump(std::ostream& os) const { @@ -376,21 +467,20 @@ void FreeListSpace::Dump(std::ostream& os) const { << " begin: " << reinterpret_cast<void*>(Begin()) << " end: " << reinterpret_cast<void*>(End()) << "\n"; uintptr_t free_end_start = reinterpret_cast<uintptr_t>(end_) - free_end_; - AllocationHeader* cur_header = reinterpret_cast<AllocationHeader*>(Begin()); - while (reinterpret_cast<uintptr_t>(cur_header) < free_end_start) { - byte* free_start = reinterpret_cast<byte*>(cur_header); - cur_header = cur_header->GetNextNonFree(); - byte* free_end = reinterpret_cast<byte*>(cur_header); - if (free_start != free_end) { - os << "Free block at address: " << reinterpret_cast<const void*>(free_start) - << " of length " << free_end - free_start << " bytes\n"; + const AllocationInfo* cur_info = + GetAllocationInfoForAddress(reinterpret_cast<uintptr_t>(Begin())); + const AllocationInfo* end_info = GetAllocationInfoForAddress(free_end_start); + while (cur_info < end_info) { + size_t size = cur_info->ByteSize(); + uintptr_t address = GetAddressForAllocationInfo(cur_info); + if (cur_info->IsFree()) { + os << "Free block at address: " << reinterpret_cast<const void*>(address) + << " of length " << size << " bytes\n"; + } else { + os << "Large object at address: " << reinterpret_cast<const void*>(address) + << " of length " << size << " bytes\n"; } - size_t alloc_size = cur_header->AllocationSize(); - byte* byte_start = reinterpret_cast<byte*>(cur_header->GetObjectAddress()); - byte* byte_end = byte_start + alloc_size - sizeof(AllocationHeader); - os << "Large object at address: " << reinterpret_cast<const void*>(free_start) - << " of length " << byte_end - byte_start << " bytes\n"; - cur_header = reinterpret_cast<AllocationHeader*>(byte_end); + cur_info = cur_info->GetNextInfo(); } if (free_end_) { os << "Free block at address: " << reinterpret_cast<const void*>(free_end_start) diff --git a/runtime/gc/space/large_object_space.h b/runtime/gc/space/large_object_space.h index 09a09198b6..9d5e090a29 100644 --- a/runtime/gc/space/large_object_space.h +++ b/runtime/gc/space/large_object_space.h @@ -29,13 +29,14 @@ namespace art { namespace gc { namespace space { +class AllocationInfo; + // Abstraction implemented by all large object spaces. class LargeObjectSpace : public DiscontinuousSpace, public AllocSpace { public: SpaceType GetType() const OVERRIDE { return kSpaceTypeLargeObjectSpace; } - void SwapBitmaps(); void CopyLiveToMarked(); virtual void Walk(DlMallocSpace::WalkCallback, void* arg) = 0; @@ -44,57 +45,53 @@ class LargeObjectSpace : public DiscontinuousSpace, public AllocSpace { uint64_t GetBytesAllocated() OVERRIDE { return num_bytes_allocated_; } - uint64_t GetObjectsAllocated() OVERRIDE { return num_objects_allocated_; } - uint64_t GetTotalBytesAllocated() const { return total_bytes_allocated_; } - uint64_t GetTotalObjectsAllocated() const { return total_objects_allocated_; } - size_t FreeList(Thread* self, size_t num_ptrs, mirror::Object** ptrs) OVERRIDE; - // LargeObjectSpaces don't have thread local state. void RevokeThreadLocalBuffers(art::Thread*) OVERRIDE { } void RevokeAllThreadLocalBuffers() OVERRIDE { } - bool IsAllocSpace() const OVERRIDE { return true; } - AllocSpace* AsAllocSpace() OVERRIDE { return this; } - collector::ObjectBytePair Sweep(bool swap_bitmaps); - virtual bool CanMoveObjects() const OVERRIDE { return false; } - // Current address at which the space begins, which may vary as the space is filled. byte* Begin() const { return begin_; } - // Current address at which the space ends, which may vary as the space is filled. byte* End() const { return end_; } - + // Current size of space + size_t Size() const { + return End() - Begin(); + } + // Return true if we contain the specified address. + bool Contains(const mirror::Object* obj) const { + const byte* byte_obj = reinterpret_cast<const byte*>(obj); + return Begin() <= byte_obj && byte_obj < End(); + } void LogFragmentationAllocFailure(std::ostream& os, size_t failed_alloc_bytes) OVERRIDE SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); protected: explicit LargeObjectSpace(const std::string& name, byte* begin, byte* end); - static void SweepCallback(size_t num_ptrs, mirror::Object** ptrs, void* arg); // Approximate number of bytes which have been allocated into the space. @@ -102,7 +99,6 @@ class LargeObjectSpace : public DiscontinuousSpace, public AllocSpace { uint64_t num_objects_allocated_; uint64_t total_bytes_allocated_; uint64_t total_objects_allocated_; - // Begin and end, may change as more large objects are allocated. byte* begin_; byte* end_; @@ -119,7 +115,6 @@ class LargeObjectMapSpace : public LargeObjectSpace { // Creates a large object space. Allocations into the large object space use memory maps instead // of malloc. static LargeObjectMapSpace* Create(const std::string& name); - // Return the storage space required by obj. size_t AllocationSize(mirror::Object* obj, size_t* usable_size); mirror::Object* Alloc(Thread* self, size_t num_bytes, size_t* bytes_allocated, @@ -145,126 +140,52 @@ class LargeObjectMapSpace : public LargeObjectSpace { // A continuous large object space with a free-list to handle holes. class FreeListSpace FINAL : public LargeObjectSpace { public: + static constexpr size_t kAlignment = kPageSize; + virtual ~FreeListSpace(); static FreeListSpace* Create(const std::string& name, byte* requested_begin, size_t capacity); - size_t AllocationSize(mirror::Object* obj, size_t* usable_size) OVERRIDE EXCLUSIVE_LOCKS_REQUIRED(lock_); mirror::Object* Alloc(Thread* self, size_t num_bytes, size_t* bytes_allocated, size_t* usable_size) OVERRIDE; size_t Free(Thread* self, mirror::Object* obj) OVERRIDE; - bool Contains(const mirror::Object* obj) const OVERRIDE; void Walk(DlMallocSpace::WalkCallback callback, void* arg) OVERRIDE LOCKS_EXCLUDED(lock_); + void Dump(std::ostream& os) const; - // Address at which the space begins. - byte* Begin() const { - return begin_; + protected: + FreeListSpace(const std::string& name, MemMap* mem_map, byte* begin, byte* end); + size_t GetSlotIndexForAddress(uintptr_t address) const { + DCHECK(Contains(reinterpret_cast<mirror::Object*>(address))); + return (address - reinterpret_cast<uintptr_t>(Begin())) / kAlignment; } - - // Address at which the space ends, which may vary as the space is filled. - byte* End() const { - return end_; + size_t GetSlotIndexForAllocationInfo(const AllocationInfo* info) const; + AllocationInfo* GetAllocationInfoForAddress(uintptr_t address); + const AllocationInfo* GetAllocationInfoForAddress(uintptr_t address) const; + uintptr_t GetAllocationAddressForSlot(size_t slot) const { + return reinterpret_cast<uintptr_t>(Begin()) + slot * kAlignment; } - - // Current size of space - size_t Size() const { - return End() - Begin(); + uintptr_t GetAddressForAllocationInfo(const AllocationInfo* info) const { + return GetAllocationAddressForSlot(GetSlotIndexForAllocationInfo(info)); } + // Removes header from the free blocks set by finding the corresponding iterator and erasing it. + void RemoveFreePrev(AllocationInfo* info) EXCLUSIVE_LOCKS_REQUIRED(lock_); - void Dump(std::ostream& os) const; - - protected: - static const size_t kAlignment = kPageSize; - - class AllocationHeader { + class SortByPrevFree { public: - // Returns the allocation size, includes the header. - size_t AllocationSize() const { - return alloc_size_; - } - - // Updates the allocation size in the header, the allocation size includes the header itself. - void SetAllocationSize(size_t size) { - DCHECK(IsAligned<kPageSize>(size)); - alloc_size_ = size; - } - - bool IsFree() const { - return AllocationSize() == 0; - } - - // Returns the previous free allocation header by using the prev_free_ member to figure out - // where it is. If prev free is 0 then we just return ourself. - AllocationHeader* GetPrevFreeAllocationHeader() { - return reinterpret_cast<AllocationHeader*>(reinterpret_cast<uintptr_t>(this) - prev_free_); - } - - // Returns the address of the object associated with this allocation header. - mirror::Object* GetObjectAddress() { - return reinterpret_cast<mirror::Object*>(reinterpret_cast<uintptr_t>(this) + sizeof(*this)); - } - - // Returns the next allocation header after the object associated with this allocation header. - AllocationHeader* GetNextAllocationHeader() { - DCHECK_NE(alloc_size_, 0U); - return reinterpret_cast<AllocationHeader*>(reinterpret_cast<uintptr_t>(this) + alloc_size_); - } - - // Returns how many free bytes there is before the block. - size_t GetPrevFree() const { - return prev_free_; - } - - // Update the size of the free block prior to the allocation. - void SetPrevFree(size_t prev_free) { - DCHECK(IsAligned<kPageSize>(prev_free)); - prev_free_ = prev_free; - } - - // Finds and returns the next non free allocation header after ourself. - // TODO: Optimize, currently O(n) for n free following pages. - AllocationHeader* GetNextNonFree(); - - // Used to implement best fit object allocation. Each allocation has an AllocationHeader which - // contains the size of the previous free block preceding it. Implemented in such a way that we - // can also find the iterator for any allocation header pointer. - class SortByPrevFree { - public: - bool operator()(const AllocationHeader* a, const AllocationHeader* b) const { - if (a->GetPrevFree() < b->GetPrevFree()) return true; - if (a->GetPrevFree() > b->GetPrevFree()) return false; - if (a->AllocationSize() < b->AllocationSize()) return true; - if (a->AllocationSize() > b->AllocationSize()) return false; - return reinterpret_cast<uintptr_t>(a) < reinterpret_cast<uintptr_t>(b); - } - }; - - private: - // Contains the size of the previous free block, if 0 then the memory preceding us is an - // allocation. - size_t prev_free_; - - // Allocation size of this object, 0 means that the allocation header is free memory. - size_t alloc_size_; - - friend class FreeListSpace; + bool operator()(const AllocationInfo* a, const AllocationInfo* b) const; }; - - FreeListSpace(const std::string& name, MemMap* mem_map, byte* begin, byte* end); - - // Removes header from the free blocks set by finding the corresponding iterator and erasing it. - void RemoveFreePrev(AllocationHeader* header) EXCLUSIVE_LOCKS_REQUIRED(lock_); - - // Finds the allocation header corresponding to obj. - AllocationHeader* GetAllocationHeader(const mirror::Object* obj); - - typedef std::set<AllocationHeader*, AllocationHeader::SortByPrevFree, - TrackingAllocator<AllocationHeader*, kAllocatorTagLOSFreeList>> FreeBlocks; + typedef std::set<AllocationInfo*, SortByPrevFree, + TrackingAllocator<AllocationInfo*, kAllocatorTagLOSFreeList>> FreeBlocks; // There is not footer for any allocations at the end of the space, so we keep track of how much // free space there is at the end manually. std::unique_ptr<MemMap> mem_map_; + // Side table for allocation info, one per page. + std::unique_ptr<MemMap> allocation_info_map_; + AllocationInfo* allocation_info_; + Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER; + // Free bytes at the end of the space. size_t free_end_ GUARDED_BY(lock_); FreeBlocks free_blocks_ GUARDED_BY(lock_); }; diff --git a/runtime/gc/space/large_object_space_test.cc b/runtime/gc/space/large_object_space_test.cc index f733584549..c5d8abca40 100644 --- a/runtime/gc/space/large_object_space_test.cc +++ b/runtime/gc/space/large_object_space_test.cc @@ -80,6 +80,8 @@ void LargeObjectSpaceTest::LargeObjectTest() { ASSERT_GE(los->Free(Thread::Current(), obj), request_size); } } + // Test that dump doesn't crash. + los->Dump(LOG(INFO)); size_t bytes_allocated = 0; // Checks that the coalescing works. |