| /* |
| * Copyright (C) 2013 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #ifndef ART_RUNTIME_GC_ALLOCATOR_ROSALLOC_H_ |
| #define ART_RUNTIME_GC_ALLOCATOR_ROSALLOC_H_ |
| |
| #include <stdint.h> |
| #include <stdlib.h> |
| #include <sys/mman.h> |
| #include <memory> |
| #include <set> |
| #include <string> |
| #include <unordered_set> |
| #include <vector> |
| |
| #include <android-base/logging.h> |
| |
| #include "base/allocator.h" |
| #include "base/bit_utils.h" |
| #include "base/globals.h" |
| #include "base/mutex.h" |
| #include "thread.h" |
| |
| namespace art { |
| |
| class MemMap; |
| |
| namespace gc { |
| namespace allocator { |
| |
| // A runs-of-slots memory allocator. |
| class RosAlloc { |
| private: |
| // Represents a run of free pages. |
| class FreePageRun { |
| public: |
| uint8_t magic_num_; // The magic number used for debugging only. |
| |
| bool IsFree() const { |
| return !kIsDebugBuild || magic_num_ == kMagicNumFree; |
| } |
| size_t ByteSize(RosAlloc* rosalloc) const REQUIRES(rosalloc->lock_) { |
| const uint8_t* fpr_base = reinterpret_cast<const uint8_t*>(this); |
| size_t pm_idx = rosalloc->ToPageMapIndex(fpr_base); |
| size_t byte_size = rosalloc->free_page_run_size_map_[pm_idx]; |
| DCHECK_GE(byte_size, static_cast<size_t>(0)); |
| DCHECK_ALIGNED(byte_size, kPageSize); |
| return byte_size; |
| } |
| void SetByteSize(RosAlloc* rosalloc, size_t byte_size) |
| REQUIRES(rosalloc->lock_) { |
| DCHECK_EQ(byte_size % kPageSize, static_cast<size_t>(0)); |
| uint8_t* fpr_base = reinterpret_cast<uint8_t*>(this); |
| size_t pm_idx = rosalloc->ToPageMapIndex(fpr_base); |
| rosalloc->free_page_run_size_map_[pm_idx] = byte_size; |
| } |
| void* Begin() { |
| return reinterpret_cast<void*>(this); |
| } |
| void* End(RosAlloc* rosalloc) REQUIRES(rosalloc->lock_) { |
| uint8_t* fpr_base = reinterpret_cast<uint8_t*>(this); |
| uint8_t* end = fpr_base + ByteSize(rosalloc); |
| return end; |
| } |
| bool IsLargerThanPageReleaseThreshold(RosAlloc* rosalloc) |
| REQUIRES(rosalloc->lock_) { |
| return ByteSize(rosalloc) >= rosalloc->page_release_size_threshold_; |
| } |
| bool IsAtEndOfSpace(RosAlloc* rosalloc) |
| REQUIRES(rosalloc->lock_) { |
| return reinterpret_cast<uint8_t*>(this) + ByteSize(rosalloc) == rosalloc->base_ + rosalloc->footprint_; |
| } |
| bool ShouldReleasePages(RosAlloc* rosalloc) REQUIRES(rosalloc->lock_) { |
| switch (rosalloc->page_release_mode_) { |
| case kPageReleaseModeNone: |
| return false; |
| case kPageReleaseModeEnd: |
| return IsAtEndOfSpace(rosalloc); |
| case kPageReleaseModeSize: |
| return IsLargerThanPageReleaseThreshold(rosalloc); |
| case kPageReleaseModeSizeAndEnd: |
| return IsLargerThanPageReleaseThreshold(rosalloc) && IsAtEndOfSpace(rosalloc); |
| case kPageReleaseModeAll: |
| return true; |
| default: |
| LOG(FATAL) << "Unexpected page release mode "; |
| return false; |
| } |
| } |
| void ReleasePages(RosAlloc* rosalloc) REQUIRES(rosalloc->lock_) { |
| uint8_t* start = reinterpret_cast<uint8_t*>(this); |
| size_t byte_size = ByteSize(rosalloc); |
| DCHECK_EQ(byte_size % kPageSize, static_cast<size_t>(0)); |
| if (ShouldReleasePages(rosalloc)) { |
| rosalloc->ReleasePageRange(start, start + byte_size); |
| } |
| } |
| |
| private: |
| DISALLOW_COPY_AND_ASSIGN(FreePageRun); |
| }; |
| |
| // The slot header. |
| class Slot { |
| public: |
| Slot* Next() const { |
| return next_; |
| } |
| void SetNext(Slot* next) { |
| next_ = next; |
| } |
| // The slot right before this slot in terms of the address. |
| Slot* Left(size_t bracket_size) { |
| return reinterpret_cast<Slot*>(reinterpret_cast<uintptr_t>(this) - bracket_size); |
| } |
| void Clear() { |
| next_ = nullptr; |
| } |
| |
| private: |
| Slot* next_; // Next slot in the list. |
| friend class RosAlloc; |
| }; |
| |
| // We use the tail (kUseTail == true) for the bulk or thread-local free lists to avoid the need to |
| // traverse the list from the head to the tail when merging free lists. |
| // We don't use the tail (kUseTail == false) for the free list to avoid the need to manage the |
| // tail in the allocation fast path for a performance reason. |
| template<bool kUseTail = true> |
| class SlotFreeList { |
| public: |
| SlotFreeList() : head_(0U), tail_(0), size_(0), padding_(0) {} |
| Slot* Head() const { |
| return reinterpret_cast<Slot*>(head_); |
| } |
| Slot* Tail() const { |
| CHECK(kUseTail); |
| return reinterpret_cast<Slot*>(tail_); |
| } |
| size_t Size() const { |
| return size_; |
| } |
| // Removes from the head of the free list. |
| Slot* Remove() { |
| Slot* slot; |
| if (kIsDebugBuild) { |
| Verify(); |
| } |
| Slot** headp = reinterpret_cast<Slot**>(&head_); |
| Slot** tailp = kUseTail ? reinterpret_cast<Slot**>(&tail_) : nullptr; |
| Slot* old_head = *headp; |
| if (old_head == nullptr) { |
| // List was empty. |
| if (kUseTail) { |
| DCHECK(*tailp == nullptr); |
| } |
| return nullptr; |
| } else { |
| // List wasn't empty. |
| if (kUseTail) { |
| DCHECK(*tailp != nullptr); |
| } |
| Slot* old_head_next = old_head->Next(); |
| slot = old_head; |
| *headp = old_head_next; |
| if (kUseTail && old_head_next == nullptr) { |
| // List becomes empty. |
| *tailp = nullptr; |
| } |
| } |
| slot->Clear(); |
| --size_; |
| if (kIsDebugBuild) { |
| Verify(); |
| } |
| return slot; |
| } |
| void Add(Slot* slot) { |
| if (kIsDebugBuild) { |
| Verify(); |
| } |
| DCHECK(slot != nullptr); |
| DCHECK(slot->Next() == nullptr); |
| Slot** headp = reinterpret_cast<Slot**>(&head_); |
| Slot** tailp = kUseTail ? reinterpret_cast<Slot**>(&tail_) : nullptr; |
| Slot* old_head = *headp; |
| if (old_head == nullptr) { |
| // List was empty. |
| if (kUseTail) { |
| DCHECK(*tailp == nullptr); |
| } |
| *headp = slot; |
| if (kUseTail) { |
| *tailp = slot; |
| } |
| } else { |
| // List wasn't empty. |
| if (kUseTail) { |
| DCHECK(*tailp != nullptr); |
| } |
| *headp = slot; |
| slot->SetNext(old_head); |
| } |
| ++size_; |
| if (kIsDebugBuild) { |
| Verify(); |
| } |
| } |
| // Merge the given list into this list. Empty the given list. |
| // Deliberately support only a kUseTail == true SlotFreeList parameter because 1) we don't |
| // currently have a situation where we need a kUseTail == false SlotFreeList parameter, and 2) |
| // supporting the kUseTail == false parameter would require a O(n) linked list traversal to do |
| // the merge if 'this' SlotFreeList has kUseTail == false, which we'd like to avoid. |
| void Merge(SlotFreeList<true>* list) { |
| if (kIsDebugBuild) { |
| Verify(); |
| CHECK(list != nullptr); |
| list->Verify(); |
| } |
| if (list->Size() == 0) { |
| return; |
| } |
| Slot** headp = reinterpret_cast<Slot**>(&head_); |
| Slot** tailp = kUseTail ? reinterpret_cast<Slot**>(&tail_) : nullptr; |
| Slot* old_head = *headp; |
| if (old_head == nullptr) { |
| // List was empty. |
| *headp = list->Head(); |
| if (kUseTail) { |
| *tailp = list->Tail(); |
| } |
| size_ = list->Size(); |
| } else { |
| // List wasn't empty. |
| DCHECK(list->Head() != nullptr); |
| *headp = list->Head(); |
| DCHECK(list->Tail() != nullptr); |
| list->Tail()->SetNext(old_head); |
| // if kUseTail, no change to tailp. |
| size_ += list->Size(); |
| } |
| list->Reset(); |
| if (kIsDebugBuild) { |
| Verify(); |
| } |
| } |
| |
| void Reset() { |
| head_ = 0; |
| if (kUseTail) { |
| tail_ = 0; |
| } |
| size_ = 0; |
| } |
| |
| void Verify() { |
| Slot* head = reinterpret_cast<Slot*>(head_); |
| Slot* tail = kUseTail ? reinterpret_cast<Slot*>(tail_) : nullptr; |
| if (size_ == 0) { |
| CHECK(head == nullptr); |
| if (kUseTail) { |
| CHECK(tail == nullptr); |
| } |
| } else { |
| CHECK(head != nullptr); |
| if (kUseTail) { |
| CHECK(tail != nullptr); |
| } |
| size_t count = 0; |
| for (Slot* slot = head; slot != nullptr; slot = slot->Next()) { |
| ++count; |
| if (kUseTail && slot->Next() == nullptr) { |
| CHECK_EQ(slot, tail); |
| } |
| } |
| CHECK_EQ(size_, count); |
| } |
| } |
| |
| private: |
| // A pointer (Slot*) to the head of the list. Always 8 bytes so that we will have the same |
| // layout between 32 bit and 64 bit, which is not strictly necessary, but we do so for 1) |
| // uniformity, 2) we won't need to change this code if we move to a non-low 4G heap in the |
| // future, and 3) the space savings by using 32 bit fields in 32 bit would be lost in noise |
| // (won't open up enough space to cause an extra slot to be available). |
| uint64_t head_; |
| // A pointer (Slot*) to the tail of the list. Always 8 bytes so that we will have the same |
| // layout between 32 bit and 64 bit. The tail is stored to speed up merging of lists. |
| // Unused if kUseTail is false. |
| uint64_t tail_; |
| // The number of slots in the list. This is used to make it fast to check if a free list is all |
| // free without traversing the whole free list. |
| uint32_t size_; |
| uint32_t padding_ ATTRIBUTE_UNUSED; |
| friend class RosAlloc; |
| }; |
| |
| // Represents a run of memory slots of the same size. |
| // |
| // A run's memory layout: |
| // |
| // +-------------------+ |
| // | magic_num | |
| // +-------------------+ |
| // | size_bracket_idx | |
| // +-------------------+ |
| // | is_thread_local | |
| // +-------------------+ |
| // | to_be_bulk_freed | |
| // +-------------------+ |
| // | | |
| // | free list | |
| // | | |
| // +-------------------+ |
| // | | |
| // | bulk free list | |
| // | | |
| // +-------------------+ |
| // | | |
| // | thread-local free | |
| // | list | |
| // | | |
| // +-------------------+ |
| // | padding due to | |
| // | alignment | |
| // +-------------------+ |
| // | slot 0 | |
| // +-------------------+ |
| // | slot 1 | |
| // +-------------------+ |
| // | slot 2 | |
| // +-------------------+ |
| // ... |
| // +-------------------+ |
| // | last slot | |
| // +-------------------+ |
| // |
| class Run { |
| public: |
| uint8_t magic_num_; // The magic number used for debugging. |
| uint8_t size_bracket_idx_; // The index of the size bracket of this run. |
| uint8_t is_thread_local_; // True if this run is used as a thread-local run. |
| uint8_t to_be_bulk_freed_; // Used within BulkFree() to flag a run that's involved with a bulk free. |
| uint32_t padding_ ATTRIBUTE_UNUSED; |
| // Use a tailless free list for free_list_ so that the alloc fast path does not manage the tail. |
| SlotFreeList<false> free_list_; |
| SlotFreeList<true> bulk_free_list_; |
| SlotFreeList<true> thread_local_free_list_; |
| // Padding due to alignment |
| // Slot 0 |
| // Slot 1 |
| // ... |
| |
| // Returns the byte size of the header. |
| static size_t fixed_header_size() { |
| return sizeof(Run); |
| } |
| Slot* FirstSlot() const { |
| const uint8_t idx = size_bracket_idx_; |
| return reinterpret_cast<Slot*>(reinterpret_cast<uintptr_t>(this) + headerSizes[idx]); |
| } |
| Slot* LastSlot() { |
| const uint8_t idx = size_bracket_idx_; |
| const size_t bracket_size = bracketSizes[idx]; |
| uintptr_t end = reinterpret_cast<uintptr_t>(End()); |
| Slot* last_slot = reinterpret_cast<Slot*>(end - bracket_size); |
| DCHECK_LE(FirstSlot(), last_slot); |
| return last_slot; |
| } |
| SlotFreeList<false>* FreeList() { |
| return &free_list_; |
| } |
| SlotFreeList<true>* BulkFreeList() { |
| return &bulk_free_list_; |
| } |
| SlotFreeList<true>* ThreadLocalFreeList() { |
| return &thread_local_free_list_; |
| } |
| void* End() { |
| return reinterpret_cast<uint8_t*>(this) + kPageSize * numOfPages[size_bracket_idx_]; |
| } |
| void SetIsThreadLocal(bool is_thread_local) { |
| is_thread_local_ = is_thread_local ? 1 : 0; |
| } |
| bool IsThreadLocal() const { |
| return is_thread_local_ != 0; |
| } |
| // Set up the free list for a new/empty run. |
| void InitFreeList() { |
| const uint8_t idx = size_bracket_idx_; |
| const size_t bracket_size = bracketSizes[idx]; |
| Slot* first_slot = FirstSlot(); |
| // Add backwards so the first slot is at the head of the list. |
| for (Slot* slot = LastSlot(); slot >= first_slot; slot = slot->Left(bracket_size)) { |
| free_list_.Add(slot); |
| } |
| } |
| // Merge the thread local free list to the free list. Used when a thread-local run becomes |
| // full. |
| bool MergeThreadLocalFreeListToFreeList(bool* is_all_free_after_out); |
| // Merge the bulk free list to the free list. Used in a bulk free. |
| void MergeBulkFreeListToFreeList(); |
| // Merge the bulk free list to the thread local free list. In a bulk free, as a two-step |
| // process, GC will first record all the slots to free in a run in the bulk free list where it |
| // can write without a lock, and later acquire a lock once per run to merge the bulk free list |
| // to the thread-local free list. |
| void MergeBulkFreeListToThreadLocalFreeList(); |
| // Allocates a slot in a run. |
| ALWAYS_INLINE void* AllocSlot(); |
| // Frees a slot in a run. This is used in a non-bulk free. |
| void FreeSlot(void* ptr); |
| // Add the given slot to the bulk free list. Returns the bracket size. |
| size_t AddToBulkFreeList(void* ptr); |
| // Add the given slot to the thread-local free list. |
| void AddToThreadLocalFreeList(void* ptr); |
| // Returns true if all the slots in the run are not in use. |
| bool IsAllFree() const { |
| return free_list_.Size() == numOfSlots[size_bracket_idx_]; |
| } |
| // Returns the number of free slots. |
| size_t NumberOfFreeSlots() { |
| return free_list_.Size(); |
| } |
| // Returns true if all the slots in the run are in use. |
| ALWAYS_INLINE bool IsFull(); |
| // Returns true if the bulk free list is empty. |
| bool IsBulkFreeListEmpty() const { |
| return bulk_free_list_.Size() == 0; |
| } |
| // Returns true if the thread local free list is empty. |
| bool IsThreadLocalFreeListEmpty() const { |
| return thread_local_free_list_.Size() == 0; |
| } |
| // Zero the run's data. |
| void ZeroData(); |
| // Zero the run's header and the slot headers. |
| void ZeroHeaderAndSlotHeaders(); |
| // Iterate over all the slots and apply the given function. |
| void InspectAllSlots(void (*handler)(void* start, void* end, size_t used_bytes, void* callback_arg), void* arg); |
| // Dump the run metadata for debugging. |
| std::string Dump(); |
| // Verify for debugging. |
| void Verify(Thread* self, RosAlloc* rosalloc, bool running_on_memory_tool) |
| REQUIRES(Locks::mutator_lock_) |
| REQUIRES(Locks::thread_list_lock_); |
| |
| private: |
| // The common part of AddToBulkFreeList() and AddToThreadLocalFreeList(). Returns the bracket |
| // size. |
| size_t AddToFreeListShared(void* ptr, SlotFreeList<true>* free_list, const char* caller_name); |
| // Turns a FreeList into a string for debugging. |
| template<bool kUseTail> |
| std::string FreeListToStr(SlotFreeList<kUseTail>* free_list); |
| // Check a given pointer is a valid slot address and return it as Slot*. |
| Slot* ToSlot(void* ptr) { |
| const uint8_t idx = size_bracket_idx_; |
| const size_t bracket_size = bracketSizes[idx]; |
| const size_t offset_from_slot_base = reinterpret_cast<uint8_t*>(ptr) |
| - reinterpret_cast<uint8_t*>(FirstSlot()); |
| DCHECK_EQ(offset_from_slot_base % bracket_size, static_cast<size_t>(0)); |
| size_t slot_idx = offset_from_slot_base / bracket_size; |
| DCHECK_LT(slot_idx, numOfSlots[idx]); |
| return reinterpret_cast<Slot*>(ptr); |
| } |
| size_t SlotIndex(Slot* slot) const { |
| const uint8_t idx = size_bracket_idx_; |
| const size_t bracket_size = bracketSizes[idx]; |
| const size_t offset_from_slot_base = reinterpret_cast<uint8_t*>(slot) |
| - reinterpret_cast<uint8_t*>(FirstSlot()); |
| DCHECK_EQ(offset_from_slot_base % bracket_size, 0U); |
| size_t slot_idx = offset_from_slot_base / bracket_size; |
| DCHECK_LT(slot_idx, numOfSlots[idx]); |
| return slot_idx; |
| } |
| |
| // TODO: DISALLOW_COPY_AND_ASSIGN(Run); |
| }; |
| |
| // The magic number for a run. |
| static constexpr uint8_t kMagicNum = 42; |
| // The magic number for free pages. |
| static constexpr uint8_t kMagicNumFree = 43; |
| // The number of size brackets. |
| static constexpr size_t kNumOfSizeBrackets = 42; |
| // The sizes (the slot sizes, in bytes) of the size brackets. |
| static size_t bracketSizes[kNumOfSizeBrackets]; |
| // The numbers of pages that are used for runs for each size bracket. |
| static size_t numOfPages[kNumOfSizeBrackets]; |
| // The numbers of slots of the runs for each size bracket. |
| static size_t numOfSlots[kNumOfSizeBrackets]; |
| // The header sizes in bytes of the runs for each size bracket. |
| static size_t headerSizes[kNumOfSizeBrackets]; |
| |
| // Initialize the run specs (the above arrays). |
| static void Initialize(); |
| static bool initialized_; |
| |
| // Returns the byte size of the bracket size from the index. |
| static size_t IndexToBracketSize(size_t idx) { |
| DCHECK_LT(idx, kNumOfSizeBrackets); |
| return bracketSizes[idx]; |
| } |
| // Returns the index of the size bracket from the bracket size. |
| static size_t BracketSizeToIndex(size_t size) { |
| DCHECK(8 <= size && |
| ((size <= kMaxThreadLocalBracketSize && size % kThreadLocalBracketQuantumSize == 0) || |
| (size <= kMaxRegularBracketSize && size % kBracketQuantumSize == 0) || |
| size == 1 * KB || size == 2 * KB)); |
| size_t idx; |
| if (UNLIKELY(size == 1 * KB)) { |
| idx = kNumOfSizeBrackets - 2; |
| } else if (UNLIKELY(size == 2 * KB)) { |
| idx = kNumOfSizeBrackets - 1; |
| } else if (LIKELY(size <= kMaxThreadLocalBracketSize)) { |
| DCHECK_EQ(size % kThreadLocalBracketQuantumSize, 0U); |
| idx = size / kThreadLocalBracketQuantumSize - 1; |
| } else { |
| DCHECK(size <= kMaxRegularBracketSize); |
| DCHECK_EQ((size - kMaxThreadLocalBracketSize) % kBracketQuantumSize, 0U); |
| idx = ((size - kMaxThreadLocalBracketSize) / kBracketQuantumSize - 1) |
| + kNumThreadLocalSizeBrackets; |
| } |
| DCHECK(bracketSizes[idx] == size); |
| return idx; |
| } |
| // Returns true if the given allocation size is for a thread local allocation. |
| static bool IsSizeForThreadLocal(size_t size) { |
| bool is_size_for_thread_local = size <= kMaxThreadLocalBracketSize; |
| DCHECK(size > kLargeSizeThreshold || |
| (is_size_for_thread_local == (SizeToIndex(size) < kNumThreadLocalSizeBrackets))); |
| return is_size_for_thread_local; |
| } |
| // Rounds up the size up the nearest bracket size. |
| static size_t RoundToBracketSize(size_t size) { |
| DCHECK(size <= kLargeSizeThreshold); |
| if (LIKELY(size <= kMaxThreadLocalBracketSize)) { |
| return RoundUp(size, kThreadLocalBracketQuantumSize); |
| } else if (size <= kMaxRegularBracketSize) { |
| return RoundUp(size, kBracketQuantumSize); |
| } else if (UNLIKELY(size <= 1 * KB)) { |
| return 1 * KB; |
| } else { |
| DCHECK_LE(size, 2 * KB); |
| return 2 * KB; |
| } |
| } |
| // Returns the size bracket index from the byte size with rounding. |
| static size_t SizeToIndex(size_t size) { |
| DCHECK(size <= kLargeSizeThreshold); |
| if (LIKELY(size <= kMaxThreadLocalBracketSize)) { |
| return RoundUp(size, kThreadLocalBracketQuantumSize) / kThreadLocalBracketQuantumSize - 1; |
| } else if (size <= kMaxRegularBracketSize) { |
| return (RoundUp(size, kBracketQuantumSize) - kMaxThreadLocalBracketSize) / kBracketQuantumSize |
| - 1 + kNumThreadLocalSizeBrackets; |
| } else if (size <= 1 * KB) { |
| return kNumOfSizeBrackets - 2; |
| } else { |
| DCHECK_LE(size, 2 * KB); |
| return kNumOfSizeBrackets - 1; |
| } |
| } |
| // A combination of SizeToIndex() and RoundToBracketSize(). |
| static size_t SizeToIndexAndBracketSize(size_t size, size_t* bracket_size_out) { |
| DCHECK(size <= kLargeSizeThreshold); |
| size_t idx; |
| size_t bracket_size; |
| if (LIKELY(size <= kMaxThreadLocalBracketSize)) { |
| bracket_size = RoundUp(size, kThreadLocalBracketQuantumSize); |
| idx = bracket_size / kThreadLocalBracketQuantumSize - 1; |
| } else if (size <= kMaxRegularBracketSize) { |
| bracket_size = RoundUp(size, kBracketQuantumSize); |
| idx = ((bracket_size - kMaxThreadLocalBracketSize) / kBracketQuantumSize - 1) |
| + kNumThreadLocalSizeBrackets; |
| } else if (size <= 1 * KB) { |
| bracket_size = 1 * KB; |
| idx = kNumOfSizeBrackets - 2; |
| } else { |
| DCHECK(size <= 2 * KB); |
| bracket_size = 2 * KB; |
| idx = kNumOfSizeBrackets - 1; |
| } |
| DCHECK_EQ(idx, SizeToIndex(size)) << idx; |
| DCHECK_EQ(bracket_size, IndexToBracketSize(idx)) << idx; |
| DCHECK_EQ(bracket_size, bracketSizes[idx]) << idx; |
| DCHECK_LE(size, bracket_size) << idx; |
| DCHECK(size > kMaxRegularBracketSize || |
| (size <= kMaxThreadLocalBracketSize && |
| bracket_size - size < kThreadLocalBracketQuantumSize) || |
| (size <= kMaxRegularBracketSize && bracket_size - size < kBracketQuantumSize)) << idx; |
| *bracket_size_out = bracket_size; |
| return idx; |
| } |
| |
| // Returns the page map index from an address. Requires that the |
| // address is page size aligned. |
| size_t ToPageMapIndex(const void* addr) const { |
| DCHECK_LE(base_, addr); |
| DCHECK_LT(addr, base_ + capacity_); |
| size_t byte_offset = reinterpret_cast<const uint8_t*>(addr) - base_; |
| DCHECK_EQ(byte_offset % static_cast<size_t>(kPageSize), static_cast<size_t>(0)); |
| return byte_offset / kPageSize; |
| } |
| // Returns the page map index from an address with rounding. |
| size_t RoundDownToPageMapIndex(const void* addr) const { |
| DCHECK(base_ <= addr && addr < reinterpret_cast<uint8_t*>(base_) + capacity_); |
| return (reinterpret_cast<uintptr_t>(addr) - reinterpret_cast<uintptr_t>(base_)) / kPageSize; |
| } |
| |
| // A memory allocation request larger than this size is treated as a large object and allocated |
| // at a page-granularity. |
| static const size_t kLargeSizeThreshold = 2048; |
| |
| // If true, check that the returned memory is actually zero. |
| static constexpr bool kCheckZeroMemory = kIsDebugBuild; |
| // Do not check memory when running under a memory tool. In a normal |
| // build with kCheckZeroMemory the whole test should be optimized away. |
| // TODO: Unprotect before checks. |
| ALWAYS_INLINE bool ShouldCheckZeroMemory(); |
| |
| // If true, log verbose details of operations. |
| static constexpr bool kTraceRosAlloc = false; |
| |
| struct hash_run { |
| size_t operator()(const RosAlloc::Run* r) const { |
| return reinterpret_cast<size_t>(r); |
| } |
| }; |
| |
| struct eq_run { |
| bool operator()(const RosAlloc::Run* r1, const RosAlloc::Run* r2) const { |
| return r1 == r2; |
| } |
| }; |
| |
| public: |
| // Different page release modes. |
| enum PageReleaseMode { |
| kPageReleaseModeNone, // Release no empty pages. |
| kPageReleaseModeEnd, // Release empty pages at the end of the space. |
| kPageReleaseModeSize, // Release empty pages that are larger than the threshold. |
| kPageReleaseModeSizeAndEnd, // Release empty pages that are larger than the threshold or |
| // at the end of the space. |
| kPageReleaseModeAll, // Release all empty pages. |
| }; |
| |
| // The default value for page_release_size_threshold_. |
| static constexpr size_t kDefaultPageReleaseSizeThreshold = 4 * MB; |
| |
| // We use thread-local runs for the size brackets whose indexes |
| // are less than this index. We use shared (current) runs for the rest. |
| // Sync this with the length of Thread::rosalloc_runs_. |
| static const size_t kNumThreadLocalSizeBrackets = 16; |
| static_assert(kNumThreadLocalSizeBrackets == kNumRosAllocThreadLocalSizeBracketsInThread, |
| "Mismatch between kNumThreadLocalSizeBrackets and " |
| "kNumRosAllocThreadLocalSizeBracketsInThread"); |
| |
| // The size of the largest bracket we use thread-local runs for. |
| // This should be equal to bracketSizes[kNumThreadLocalSizeBrackets - 1]. |
| static const size_t kMaxThreadLocalBracketSize = 128; |
| |
| // We use regular (8 or 16-bytes increment) runs for the size brackets whose indexes are less than |
| // this index. |
| static const size_t kNumRegularSizeBrackets = 40; |
| |
| // The size of the largest regular (8 or 16-byte increment) bracket. Non-regular brackets are the |
| // 1 KB and the 2 KB brackets. This should be equal to bracketSizes[kNumRegularSizeBrackets - 1]. |
| static const size_t kMaxRegularBracketSize = 512; |
| |
| // The bracket size increment for the thread-local brackets (<= kMaxThreadLocalBracketSize bytes). |
| static constexpr size_t kThreadLocalBracketQuantumSize = 8; |
| |
| // Equal to Log2(kThreadLocalBracketQuantumSize). |
| static constexpr size_t kThreadLocalBracketQuantumSizeShift = 3; |
| |
| // The bracket size increment for the non-thread-local, regular brackets (of size <= |
| // kMaxRegularBracketSize bytes and > kMaxThreadLocalBracketSize bytes). |
| static constexpr size_t kBracketQuantumSize = 16; |
| |
| // Equal to Log2(kBracketQuantumSize). |
| static constexpr size_t kBracketQuantumSizeShift = 4; |
| |
| private: |
| // The base address of the memory region that's managed by this allocator. |
| uint8_t* base_; |
| |
| // The footprint in bytes of the currently allocated portion of the |
| // memory region. |
| size_t footprint_; |
| |
| // The maximum footprint. The address, base_ + capacity_, indicates |
| // the end of the memory region that's currently managed by this allocator. |
| size_t capacity_; |
| |
| // The maximum capacity. The address, base_ + max_capacity_, indicates |
| // the end of the memory region that's ever managed by this allocator. |
| size_t max_capacity_; |
| |
| template<class Key, AllocatorTag kTag, class Compare = std::less<Key>> |
| using AllocationTrackingSet = std::set<Key, Compare, TrackingAllocator<Key, kTag>>; |
| |
| // The run sets that hold the runs whose slots are not all |
| // full. non_full_runs_[i] is guarded by size_bracket_locks_[i]. |
| AllocationTrackingSet<Run*, kAllocatorTagRosAlloc> non_full_runs_[kNumOfSizeBrackets]; |
| // The run sets that hold the runs whose slots are all full. This is |
| // debug only. full_runs_[i] is guarded by size_bracket_locks_[i]. |
| std::unordered_set<Run*, hash_run, eq_run, TrackingAllocator<Run*, kAllocatorTagRosAlloc>> |
| full_runs_[kNumOfSizeBrackets]; |
| // The set of free pages. |
| AllocationTrackingSet<FreePageRun*, kAllocatorTagRosAlloc> free_page_runs_ GUARDED_BY(lock_); |
| // The dedicated full run, it is always full and shared by all threads when revoking happens. |
| // This is an optimization since enables us to avoid a null check for revoked runs. |
| static Run* dedicated_full_run_; |
| // Using size_t to ensure that it is at least word aligned. |
| static size_t dedicated_full_run_storage_[]; |
| // The current runs where the allocations are first attempted for |
| // the size brackes that do not use thread-local |
| // runs. current_runs_[i] is guarded by size_bracket_locks_[i]. |
| Run* current_runs_[kNumOfSizeBrackets]; |
| // The mutexes, one per size bracket. |
| Mutex* size_bracket_locks_[kNumOfSizeBrackets]; |
| // Bracket lock names (since locks only have char* names). |
| std::string size_bracket_lock_names_[kNumOfSizeBrackets]; |
| // The types of page map entries. |
| enum PageMapKind { |
| kPageMapReleased = 0, // Zero and released back to the OS. |
| kPageMapEmpty, // Zero but probably dirty. |
| kPageMapRun, // The beginning of a run. |
| kPageMapRunPart, // The non-beginning part of a run. |
| kPageMapLargeObject, // The beginning of a large object. |
| kPageMapLargeObjectPart, // The non-beginning part of a large object. |
| }; |
| // The table that indicates what pages are currently used for. |
| volatile uint8_t* page_map_; // No GUARDED_BY(lock_) for kReadPageMapEntryWithoutLockInBulkFree. |
| size_t page_map_size_; |
| size_t max_page_map_size_; |
| std::unique_ptr<MemMap> page_map_mem_map_; |
| |
| // The table that indicates the size of free page runs. These sizes |
| // are stored here to avoid storing in the free page header and |
| // release backing pages. |
| std::vector<size_t, TrackingAllocator<size_t, kAllocatorTagRosAlloc>> free_page_run_size_map_ |
| GUARDED_BY(lock_); |
| // The global lock. Used to guard the page map, the free page set, |
| // and the footprint. |
| Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER; |
| // The reader-writer lock to allow one bulk free at a time while |
| // allowing multiple individual frees at the same time. Also, this |
| // is used to avoid race conditions between BulkFree() and |
| // RevokeThreadLocalRuns() on the bulk free list. |
| ReaderWriterMutex bulk_free_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER; |
| |
| // The page release mode. |
| const PageReleaseMode page_release_mode_; |
| // Under kPageReleaseModeSize(AndEnd), if the free page run size is |
| // greater than or equal to this value, release pages. |
| const size_t page_release_size_threshold_; |
| |
| // Whether this allocator is running on a memory tool. |
| bool is_running_on_memory_tool_; |
| |
| // The base address of the memory region that's managed by this allocator. |
| uint8_t* Begin() { return base_; } |
| // The end address of the memory region that's managed by this allocator. |
| uint8_t* End() { return base_ + capacity_; } |
| |
| // Page-granularity alloc/free |
| void* AllocPages(Thread* self, size_t num_pages, uint8_t page_map_type) |
| REQUIRES(lock_); |
| // Returns how many bytes were freed. |
| size_t FreePages(Thread* self, void* ptr, bool already_zero) REQUIRES(lock_); |
| |
| // Allocate/free a run slot. |
| void* AllocFromRun(Thread* self, size_t size, size_t* bytes_allocated, size_t* usable_size, |
| size_t* bytes_tl_bulk_allocated) |
| REQUIRES(!lock_); |
| // Allocate/free a run slot without acquiring locks. |
| // TODO: REQUIRES(Locks::mutator_lock_) |
| void* AllocFromRunThreadUnsafe(Thread* self, size_t size, size_t* bytes_allocated, |
| size_t* usable_size, size_t* bytes_tl_bulk_allocated) |
| REQUIRES(!lock_); |
| void* AllocFromCurrentRunUnlocked(Thread* self, size_t idx) REQUIRES(!lock_); |
| |
| // Returns the bracket size. |
| size_t FreeFromRun(Thread* self, void* ptr, Run* run) |
| REQUIRES(!lock_); |
| |
| // Used to allocate a new thread local run for a size bracket. |
| Run* AllocRun(Thread* self, size_t idx) REQUIRES(!lock_); |
| |
| // Used to acquire a new/reused run for a size bracket. Used when a |
| // thread-local or current run gets full. |
| Run* RefillRun(Thread* self, size_t idx) REQUIRES(!lock_); |
| |
| // The internal of non-bulk Free(). |
| size_t FreeInternal(Thread* self, void* ptr) REQUIRES(!lock_); |
| |
| // Allocates large objects. |
| void* AllocLargeObject(Thread* self, size_t size, size_t* bytes_allocated, |
| size_t* usable_size, size_t* bytes_tl_bulk_allocated) |
| REQUIRES(!lock_); |
| |
| // Revoke a run by adding it to non_full_runs_ or freeing the pages. |
| void RevokeRun(Thread* self, size_t idx, Run* run) REQUIRES(!lock_); |
| |
| // Revoke the current runs which share an index with the thread local runs. |
| void RevokeThreadUnsafeCurrentRuns() REQUIRES(!lock_); |
| |
| // Release a range of pages. |
| size_t ReleasePageRange(uint8_t* start, uint8_t* end) REQUIRES(lock_); |
| |
| // Dumps the page map for debugging. |
| std::string DumpPageMap() REQUIRES(lock_); |
| |
| public: |
| RosAlloc(void* base, size_t capacity, size_t max_capacity, |
| PageReleaseMode page_release_mode, |
| bool running_on_memory_tool, |
| size_t page_release_size_threshold = kDefaultPageReleaseSizeThreshold); |
| ~RosAlloc(); |
| |
| static size_t RunFreeListOffset() { |
| return OFFSETOF_MEMBER(Run, free_list_); |
| } |
| static size_t RunFreeListHeadOffset() { |
| return OFFSETOF_MEMBER(SlotFreeList<false>, head_); |
| } |
| static size_t RunFreeListSizeOffset() { |
| return OFFSETOF_MEMBER(SlotFreeList<false>, size_); |
| } |
| static size_t RunSlotNextOffset() { |
| return OFFSETOF_MEMBER(Slot, next_); |
| } |
| |
| // If kThreadUnsafe is true then the allocator may avoid acquiring some locks as an optimization. |
| // If used, this may cause race conditions if multiple threads are allocating at the same time. |
| template<bool kThreadSafe = true> |
| void* Alloc(Thread* self, size_t size, size_t* bytes_allocated, size_t* usable_size, |
| size_t* bytes_tl_bulk_allocated) |
| REQUIRES(!lock_); |
| size_t Free(Thread* self, void* ptr) |
| REQUIRES(!bulk_free_lock_, !lock_); |
| size_t BulkFree(Thread* self, void** ptrs, size_t num_ptrs) |
| REQUIRES(!bulk_free_lock_, !lock_); |
| |
| // Returns true if the given allocation request can be allocated in |
| // an existing thread local run without allocating a new run. |
| ALWAYS_INLINE bool CanAllocFromThreadLocalRun(Thread* self, size_t size); |
| // Allocate the given allocation request in an existing thread local |
| // run without allocating a new run. |
| ALWAYS_INLINE void* AllocFromThreadLocalRun(Thread* self, size_t size, size_t* bytes_allocated); |
| |
| // Returns the maximum bytes that could be allocated for the given |
| // size in bulk, that is the maximum value for the |
| // bytes_allocated_bulk out param returned by RosAlloc::Alloc(). |
| ALWAYS_INLINE size_t MaxBytesBulkAllocatedFor(size_t size); |
| |
| // Returns the size of the allocated slot for a given allocated memory chunk. |
| size_t UsableSize(const void* ptr) REQUIRES(!lock_); |
| // Returns the size of the allocated slot for a given size. |
| size_t UsableSize(size_t bytes) { |
| if (UNLIKELY(bytes > kLargeSizeThreshold)) { |
| return RoundUp(bytes, kPageSize); |
| } else { |
| return RoundToBracketSize(bytes); |
| } |
| } |
| // Try to reduce the current footprint by releasing the free page |
| // run at the end of the memory region, if any. |
| bool Trim() REQUIRES(!lock_); |
| // Iterates over all the memory slots and apply the given function. |
| void InspectAll(void (*handler)(void* start, void* end, size_t used_bytes, void* callback_arg), |
| void* arg) |
| REQUIRES(!lock_); |
| |
| // Release empty pages. |
| size_t ReleasePages() REQUIRES(!lock_); |
| // Returns the current footprint. |
| size_t Footprint() REQUIRES(!lock_); |
| // Returns the current capacity, maximum footprint. |
| size_t FootprintLimit() REQUIRES(!lock_); |
| // Update the current capacity. |
| void SetFootprintLimit(size_t bytes) REQUIRES(!lock_); |
| |
| // Releases the thread-local runs assigned to the given thread back to the common set of runs. |
| // Returns the total bytes of free slots in the revoked thread local runs. This is to be |
| // subtracted from Heap::num_bytes_allocated_ to cancel out the ahead-of-time counting. |
| size_t RevokeThreadLocalRuns(Thread* thread) REQUIRES(!lock_, !bulk_free_lock_); |
| // Releases the thread-local runs assigned to all the threads back to the common set of runs. |
| // Returns the total bytes of free slots in the revoked thread local runs. This is to be |
| // subtracted from Heap::num_bytes_allocated_ to cancel out the ahead-of-time counting. |
| size_t RevokeAllThreadLocalRuns() REQUIRES(!Locks::thread_list_lock_, !lock_, !bulk_free_lock_); |
| // Assert the thread local runs of a thread are revoked. |
| void AssertThreadLocalRunsAreRevoked(Thread* thread) REQUIRES(!bulk_free_lock_); |
| // Assert all the thread local runs are revoked. |
| void AssertAllThreadLocalRunsAreRevoked() REQUIRES(!Locks::thread_list_lock_, !bulk_free_lock_); |
| |
| static Run* GetDedicatedFullRun() { |
| return dedicated_full_run_; |
| } |
| bool IsFreePage(size_t idx) const { |
| DCHECK_LT(idx, capacity_ / kPageSize); |
| uint8_t pm_type = page_map_[idx]; |
| return pm_type == kPageMapReleased || pm_type == kPageMapEmpty; |
| } |
| |
| // Callbacks for InspectAll that will count the number of bytes |
| // allocated and objects allocated, respectively. |
| static void BytesAllocatedCallback(void* start, void* end, size_t used_bytes, void* arg); |
| static void ObjectsAllocatedCallback(void* start, void* end, size_t used_bytes, void* arg); |
| |
| bool DoesReleaseAllPages() const { |
| return page_release_mode_ == kPageReleaseModeAll; |
| } |
| |
| // Verify for debugging. |
| void Verify() REQUIRES(Locks::mutator_lock_, !Locks::thread_list_lock_, !bulk_free_lock_, |
| !lock_); |
| |
| void LogFragmentationAllocFailure(std::ostream& os, size_t failed_alloc_bytes) |
| REQUIRES(!bulk_free_lock_, !lock_); |
| |
| void DumpStats(std::ostream& os) |
| REQUIRES(Locks::mutator_lock_) REQUIRES(!lock_) REQUIRES(!bulk_free_lock_); |
| |
| private: |
| friend std::ostream& operator<<(std::ostream& os, const RosAlloc::PageMapKind& rhs); |
| |
| DISALLOW_COPY_AND_ASSIGN(RosAlloc); |
| }; |
| std::ostream& operator<<(std::ostream& os, const RosAlloc::PageMapKind& rhs); |
| |
| // Callback from rosalloc when it needs to increase the footprint. Must be implemented somewhere |
| // else (currently rosalloc_space.cc). |
| void* ArtRosAllocMoreCore(allocator::RosAlloc* rosalloc, intptr_t increment); |
| |
| } // namespace allocator |
| } // namespace gc |
| } // namespace art |
| |
| #endif // ART_RUNTIME_GC_ALLOCATOR_ROSALLOC_H_ |