| /* |
| * Copyright 2021 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_COLLECTOR_MARK_COMPACT_H_ |
| #define ART_RUNTIME_GC_COLLECTOR_MARK_COMPACT_H_ |
| |
| #include <signal.h> |
| |
| #include <map> |
| #include <memory> |
| #include <unordered_map> |
| #include <unordered_set> |
| |
| #include "barrier.h" |
| #include "base/atomic.h" |
| #include "base/gc_visited_arena_pool.h" |
| #include "base/macros.h" |
| #include "base/mutex.h" |
| #include "garbage_collector.h" |
| #include "gc/accounting/atomic_stack.h" |
| #include "gc/accounting/bitmap-inl.h" |
| #include "gc/accounting/heap_bitmap.h" |
| #include "gc_root.h" |
| #include "immune_spaces.h" |
| #include "offsets.h" |
| |
| namespace art HIDDEN { |
| |
| EXPORT bool KernelSupportsUffd(); |
| |
| namespace mirror { |
| class DexCache; |
| } // namespace mirror |
| |
| namespace gc { |
| |
| class Heap; |
| |
| namespace space { |
| class BumpPointerSpace; |
| } // namespace space |
| |
| namespace collector { |
| class MarkCompact final : public GarbageCollector { |
| public: |
| using SigbusCounterType = uint32_t; |
| |
| static constexpr size_t kAlignment = kObjectAlignment; |
| static constexpr int kCopyMode = -1; |
| static constexpr int kMinorFaultMode = -2; |
| // Fake file descriptor for fall back mode (when uffd isn't available) |
| static constexpr int kFallbackMode = -3; |
| static constexpr int kFdSharedAnon = -1; |
| static constexpr int kFdUnused = -2; |
| |
| // Bitmask for the compaction-done bit in the sigbus_in_progress_count_. |
| static constexpr SigbusCounterType kSigbusCounterCompactionDoneMask = |
| 1u << (BitSizeOf<SigbusCounterType>() - 1); |
| |
| explicit MarkCompact(Heap* heap); |
| |
| ~MarkCompact() {} |
| |
| void RunPhases() override REQUIRES(!Locks::mutator_lock_, !lock_); |
| |
| void ClampGrowthLimit(size_t new_capacity) REQUIRES(Locks::heap_bitmap_lock_); |
| // Updated before (or in) pre-compaction pause and is accessed only in the |
| // pause or during concurrent compaction. The flag is reset in next GC cycle's |
| // InitializePhase(). Therefore, it's safe to update without any memory ordering. |
| bool IsCompacting() const { return compacting_; } |
| |
| bool IsUsingSigbusFeature() const { return use_uffd_sigbus_; } |
| |
| // Called by SIGBUS handler. NO_THREAD_SAFETY_ANALYSIS for mutator-lock, which |
| // is asserted in the function. |
| bool SigbusHandler(siginfo_t* info) REQUIRES(!lock_) NO_THREAD_SAFETY_ANALYSIS; |
| |
| GcType GetGcType() const override { |
| return kGcTypeFull; |
| } |
| |
| CollectorType GetCollectorType() const override { |
| return kCollectorTypeCMC; |
| } |
| |
| Barrier& GetBarrier() { |
| return gc_barrier_; |
| } |
| |
| mirror::Object* MarkObject(mirror::Object* obj) override |
| REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| |
| void MarkHeapReference(mirror::HeapReference<mirror::Object>* obj, |
| bool do_atomic_update) override |
| REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| |
| void VisitRoots(mirror::Object*** roots, |
| size_t count, |
| const RootInfo& info) override |
| REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| void VisitRoots(mirror::CompressedReference<mirror::Object>** roots, |
| size_t count, |
| const RootInfo& info) override |
| REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| |
| bool IsNullOrMarkedHeapReference(mirror::HeapReference<mirror::Object>* obj, |
| bool do_atomic_update) override |
| REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| |
| void RevokeAllThreadLocalBuffers() override; |
| |
| void DelayReferenceReferent(ObjPtr<mirror::Class> klass, |
| ObjPtr<mirror::Reference> reference) override |
| REQUIRES_SHARED(Locks::mutator_lock_, Locks::heap_bitmap_lock_); |
| |
| mirror::Object* IsMarked(mirror::Object* obj) override |
| REQUIRES_SHARED(Locks::mutator_lock_, Locks::heap_bitmap_lock_); |
| |
| mirror::Object* GetFromSpaceAddrFromBarrier(mirror::Object* old_ref) { |
| CHECK(compacting_); |
| if (HasAddress(old_ref)) { |
| return GetFromSpaceAddr(old_ref); |
| } |
| return old_ref; |
| } |
| // Called from Heap::PostForkChildAction() for non-zygote processes and from |
| // PrepareForCompaction() for zygote processes. Returns true if uffd was |
| // created or was already done. |
| bool CreateUserfaultfd(bool post_fork); |
| |
| // Returns a pair indicating if userfaultfd itself is available (first) and if |
| // so then whether its minor-fault feature is available or not (second). |
| static std::pair<bool, bool> GetUffdAndMinorFault(); |
| |
| // Add linear-alloc space data when a new space is added to |
| // GcVisitedArenaPool, which mostly happens only once. |
| void AddLinearAllocSpaceData(uint8_t* begin, size_t len); |
| |
| // In copy-mode of userfaultfd, we don't need to reach a 'processed' state as |
| // it's given that processing thread also copies the page, thereby mapping it. |
| // The order is important as we may treat them as integers. |
| enum class PageState : uint8_t { |
| kUnprocessed = 0, // Not processed yet |
| kProcessing = 1, // Being processed by GC thread and will not be mapped |
| kProcessed = 2, // Processed but not mapped |
| kProcessingAndMapping = 3, // Being processed by GC or mutator and will be mapped |
| kMutatorProcessing = 4, // Being processed by mutator thread |
| kProcessedAndMapping = 5, // Processed and will be mapped |
| kProcessedAndMapped = 6 // Processed and mapped. For SIGBUS. |
| }; |
| |
| // Different heap clamping states. |
| enum class ClampInfoStatus : uint8_t { |
| kClampInfoNotDone, |
| kClampInfoPending, |
| kClampInfoFinished |
| }; |
| |
| private: |
| using ObjReference = mirror::CompressedReference<mirror::Object>; |
| // Number of bits (live-words) covered by a single chunk-info (below) |
| // entry/word. |
| // TODO: Since popcount is performed usomg SIMD instructions, we should |
| // consider using 128-bit in order to halve the chunk-info size. |
| static constexpr uint32_t kBitsPerVectorWord = kBitsPerIntPtrT; |
| static constexpr uint32_t kOffsetChunkSize = kBitsPerVectorWord * kAlignment; |
| static_assert(kOffsetChunkSize < kMinPageSize); |
| // Bitmap with bits corresponding to every live word set. For an object |
| // which is 4 words in size will have the corresponding 4 bits set. This is |
| // required for efficient computation of new-address (post-compaction) from |
| // the given old-address (pre-compaction). |
| template <size_t kAlignment> |
| class LiveWordsBitmap : private accounting::MemoryRangeBitmap<kAlignment> { |
| using Bitmap = accounting::Bitmap; |
| using MemRangeBitmap = accounting::MemoryRangeBitmap<kAlignment>; |
| |
| public: |
| static_assert(IsPowerOfTwo(kBitsPerVectorWord)); |
| static_assert(IsPowerOfTwo(Bitmap::kBitsPerBitmapWord)); |
| static_assert(kBitsPerVectorWord >= Bitmap::kBitsPerBitmapWord); |
| static constexpr uint32_t kBitmapWordsPerVectorWord = |
| kBitsPerVectorWord / Bitmap::kBitsPerBitmapWord; |
| static_assert(IsPowerOfTwo(kBitmapWordsPerVectorWord)); |
| using MemRangeBitmap::SetBitmapSize; |
| static LiveWordsBitmap* Create(uintptr_t begin, uintptr_t end); |
| |
| // Return offset (within the indexed chunk-info) of the nth live word. |
| uint32_t FindNthLiveWordOffset(size_t chunk_idx, uint32_t n) const; |
| // Sets all bits in the bitmap corresponding to the given range. Also |
| // returns the bit-index of the first word. |
| ALWAYS_INLINE uintptr_t SetLiveWords(uintptr_t begin, size_t size); |
| // Count number of live words upto the given bit-index. This is to be used |
| // to compute the post-compact address of an old reference. |
| ALWAYS_INLINE size_t CountLiveWordsUpto(size_t bit_idx) const; |
| // Call 'visitor' for every stride of contiguous marked bits in the live-words |
| // bitmap, starting from begin_bit_idx. Only visit 'bytes' live bytes or |
| // until 'end', whichever comes first. |
| // Visitor is called with index of the first marked bit in the stride, |
| // stride size and whether it's the last stride in the given range or not. |
| template <typename Visitor> |
| ALWAYS_INLINE void VisitLiveStrides(uintptr_t begin_bit_idx, |
| uint8_t* end, |
| const size_t bytes, |
| Visitor&& visitor) const |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| // Count the number of live bytes in the given vector entry. |
| size_t LiveBytesInBitmapWord(size_t chunk_idx) const; |
| void ClearBitmap() { Bitmap::Clear(); } |
| ALWAYS_INLINE uintptr_t Begin() const { return MemRangeBitmap::CoverBegin(); } |
| ALWAYS_INLINE bool HasAddress(mirror::Object* obj) const { |
| return MemRangeBitmap::HasAddress(reinterpret_cast<uintptr_t>(obj)); |
| } |
| ALWAYS_INLINE bool Test(uintptr_t bit_index) const { |
| return Bitmap::TestBit(bit_index); |
| } |
| ALWAYS_INLINE bool Test(mirror::Object* obj) const { |
| return MemRangeBitmap::Test(reinterpret_cast<uintptr_t>(obj)); |
| } |
| ALWAYS_INLINE uintptr_t GetWord(size_t index) const { |
| static_assert(kBitmapWordsPerVectorWord == 1); |
| return Bitmap::Begin()[index * kBitmapWordsPerVectorWord]; |
| } |
| }; |
| |
| static bool HasAddress(mirror::Object* obj, uint8_t* begin, uint8_t* end) { |
| uint8_t* ptr = reinterpret_cast<uint8_t*>(obj); |
| return ptr >= begin && ptr < end; |
| } |
| |
| bool HasAddress(mirror::Object* obj) const { |
| return HasAddress(obj, moving_space_begin_, moving_space_end_); |
| } |
| // For a given object address in pre-compact space, return the corresponding |
| // address in the from-space, where heap pages are relocated in the compaction |
| // pause. |
| mirror::Object* GetFromSpaceAddr(mirror::Object* obj) const { |
| DCHECK(HasAddress(obj)) << " obj=" << obj; |
| return reinterpret_cast<mirror::Object*>(reinterpret_cast<uintptr_t>(obj) |
| + from_space_slide_diff_); |
| } |
| |
| // Verifies that that given object reference refers to a valid object. |
| // Otherwise fataly dumps logs, including those from callback. |
| template <typename Callback> |
| void VerifyObject(mirror::Object* ref, Callback& callback) const |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| // Check if the obj is within heap and has a klass which is likely to be valid |
| // mirror::Class. |
| bool IsValidObject(mirror::Object* obj) const REQUIRES_SHARED(Locks::mutator_lock_); |
| void InitializePhase(); |
| void FinishPhase() REQUIRES(!Locks::mutator_lock_, !Locks::heap_bitmap_lock_, !lock_); |
| void MarkingPhase() REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::heap_bitmap_lock_); |
| void CompactionPhase() REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| void SweepSystemWeaks(Thread* self, Runtime* runtime, const bool paused) |
| REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(!Locks::heap_bitmap_lock_); |
| // Update the reference at given offset in the given object with post-compact |
| // address. [begin, end) is moving-space range. |
| ALWAYS_INLINE void UpdateRef(mirror::Object* obj, |
| MemberOffset offset, |
| uint8_t* begin, |
| uint8_t* end) REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| // Verify that the gc-root is updated only once. Returns false if the update |
| // shouldn't be done. |
| ALWAYS_INLINE bool VerifyRootSingleUpdate(void* root, |
| mirror::Object* old_ref, |
| const RootInfo& info) |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| // Update the given root with post-compact address. [begin, end) is |
| // moving-space range. |
| ALWAYS_INLINE void UpdateRoot(mirror::CompressedReference<mirror::Object>* root, |
| uint8_t* begin, |
| uint8_t* end, |
| const RootInfo& info = RootInfo(RootType::kRootUnknown)) |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| ALWAYS_INLINE void UpdateRoot(mirror::Object** root, |
| uint8_t* begin, |
| uint8_t* end, |
| const RootInfo& info = RootInfo(RootType::kRootUnknown)) |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| // Given the pre-compact address, the function returns the post-compact |
| // address of the given object. [begin, end) is moving-space range. |
| ALWAYS_INLINE mirror::Object* PostCompactAddress(mirror::Object* old_ref, |
| uint8_t* begin, |
| uint8_t* end) const |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| // Compute post-compact address of an object in moving space. This function |
| // assumes that old_ref is in moving space. |
| ALWAYS_INLINE mirror::Object* PostCompactAddressUnchecked(mirror::Object* old_ref) const |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| // Compute the new address for an object which was allocated prior to starting |
| // this GC cycle. |
| ALWAYS_INLINE mirror::Object* PostCompactOldObjAddr(mirror::Object* old_ref) const |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| // Compute the new address for an object which was black allocated during this |
| // GC cycle. |
| ALWAYS_INLINE mirror::Object* PostCompactBlackObjAddr(mirror::Object* old_ref) const |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| // Clears (for alloc spaces in the beginning of marking phase) or ages the |
| // card table. Also, identifies immune spaces and mark bitmap. |
| void PrepareCardTableForMarking(bool clear_alloc_space_cards) |
| REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_); |
| |
| // Perform one last round of marking, identifying roots from dirty cards |
| // during a stop-the-world (STW) pause. |
| void MarkingPause() REQUIRES(Locks::mutator_lock_, !Locks::heap_bitmap_lock_); |
| // Perform stop-the-world pause prior to concurrent compaction. |
| // Updates GC-roots and protects heap so that during the concurrent |
| // compaction phase we can receive faults and compact the corresponding pages |
| // on the fly. |
| void CompactionPause() REQUIRES(Locks::mutator_lock_); |
| // Compute offsets (in chunk_info_vec_) and other data structures required |
| // during concurrent compaction. |
| void PrepareForCompaction() REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| // Copy gPageSize live bytes starting from 'offset' (within the moving space), |
| // which must be within 'obj', into the gPageSize sized memory pointed by 'addr'. |
| // Then update the references within the copied objects. The boundary objects are |
| // partially updated such that only the references that lie in the page are updated. |
| // This is necessary to avoid cascading userfaults. |
| void CompactPage(mirror::Object* obj, uint32_t offset, uint8_t* addr, bool needs_memset_zero) |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| // Compact the bump-pointer space. Pass page that should be used as buffer for |
| // userfaultfd. |
| template <int kMode> |
| void CompactMovingSpace(uint8_t* page) REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| // Compact the given page as per func and change its state. Also map/copy the |
| // page, if required. |
| template <int kMode, typename CompactionFn> |
| ALWAYS_INLINE void DoPageCompactionWithStateChange(size_t page_idx, |
| size_t status_arr_len, |
| uint8_t* to_space_page, |
| uint8_t* page, |
| CompactionFn func) |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| // Update all the objects in the given non-moving space page. 'first' object |
| // could have started in some preceding page. |
| void UpdateNonMovingPage(mirror::Object* first, uint8_t* page) |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| // Update all the references in the non-moving space. |
| void UpdateNonMovingSpace() REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| // For all the pages in non-moving space, find the first object that overlaps |
| // with the pages' start address, and store in first_objs_non_moving_space_ array. |
| void InitNonMovingSpaceFirstObjects() REQUIRES_SHARED(Locks::mutator_lock_); |
| // In addition to the first-objects for every post-compact moving space page, |
| // also find offsets within those objects from where the contents should be |
| // copied to the page. The offsets are relative to the moving-space's |
| // beginning. Store the computed first-object and offset in first_objs_moving_space_ |
| // and pre_compact_offset_moving_space_ respectively. |
| void InitMovingSpaceFirstObjects(const size_t vec_len) REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| // Gather the info related to black allocations from bump-pointer space to |
| // enable concurrent sliding of these pages. |
| void UpdateMovingSpaceBlackAllocations() REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_); |
| // Update first-object info from allocation-stack for non-moving space black |
| // allocations. |
| void UpdateNonMovingSpaceBlackAllocations() REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_); |
| |
| // Slides (retain the empty holes, which are usually part of some in-use TLAB) |
| // black page in the moving space. 'first_obj' is the object that overlaps with |
| // the first byte of the page being slid. pre_compact_page is the pre-compact |
| // address of the page being slid. 'dest' is the gPageSize sized memory where |
| // the contents would be copied. |
| void SlideBlackPage(mirror::Object* first_obj, |
| mirror::Object* next_page_first_obj, |
| uint32_t first_chunk_size, |
| uint8_t* const pre_compact_page, |
| uint8_t* dest, |
| bool needs_memset_zero) REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| // Perform reference-processing and the likes before sweeping the non-movable |
| // spaces. |
| void ReclaimPhase() REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::heap_bitmap_lock_); |
| |
| // Mark GC-roots (except from immune spaces and thread-stacks) during a STW pause. |
| void ReMarkRoots(Runtime* runtime) REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_); |
| // Concurrently mark GC-roots, except from immune spaces. |
| void MarkRoots(VisitRootFlags flags) REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| // Collect thread stack roots via a checkpoint. |
| void MarkRootsCheckpoint(Thread* self, Runtime* runtime) REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| // Second round of concurrent marking. Mark all gray objects that got dirtied |
| // since the first round. |
| void PreCleanCards() REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_); |
| |
| void MarkNonThreadRoots(Runtime* runtime) REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| void MarkConcurrentRoots(VisitRootFlags flags, Runtime* runtime) |
| REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_); |
| |
| // Traverse through the reachable objects and mark them. |
| void MarkReachableObjects() REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| // Scan (only) immune spaces looking for references into the garbage collected |
| // spaces. |
| void UpdateAndMarkModUnion() REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| // Scan mod-union and card tables, covering all the spaces, to identify dirty objects. |
| // These are in 'minimum age' cards, which is 'kCardAged' in case of concurrent (second round) |
| // marking and kCardDirty during the STW pause. |
| void ScanDirtyObjects(bool paused, uint8_t minimum_age) REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| // Recursively mark dirty objects. Invoked both concurrently as well in a STW |
| // pause in PausePhase(). |
| void RecursiveMarkDirtyObjects(bool paused, uint8_t minimum_age) |
| REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| // Go through all the objects in the mark-stack until it's empty. |
| void ProcessMarkStack() override REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| void ExpandMarkStack() REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| |
| // Scan object for references. If kUpdateLivewords is true then set bits in |
| // the live-words bitmap and add size to chunk-info. |
| template <bool kUpdateLiveWords> |
| void ScanObject(mirror::Object* obj) REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| // Push objects to the mark-stack right after successfully marking objects. |
| void PushOnMarkStack(mirror::Object* obj) |
| REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| |
| // Update the live-words bitmap as well as add the object size to the |
| // chunk-info vector. Both are required for computation of post-compact addresses. |
| // Also updates freed_objects_ counter. |
| void UpdateLivenessInfo(mirror::Object* obj, size_t obj_size) |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| void ProcessReferences(Thread* self) |
| REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(!Locks::heap_bitmap_lock_); |
| |
| void MarkObjectNonNull(mirror::Object* obj, |
| mirror::Object* holder = nullptr, |
| MemberOffset offset = MemberOffset(0)) |
| REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| |
| void MarkObject(mirror::Object* obj, mirror::Object* holder, MemberOffset offset) |
| REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| |
| template <bool kParallel> |
| bool MarkObjectNonNullNoPush(mirror::Object* obj, |
| mirror::Object* holder = nullptr, |
| MemberOffset offset = MemberOffset(0)) |
| REQUIRES(Locks::heap_bitmap_lock_) |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| void Sweep(bool swap_bitmaps) REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| void SweepLargeObjects(bool swap_bitmaps) REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| |
| // Perform all kernel operations required for concurrent compaction. Includes |
| // mremap to move pre-compact pages to from-space, followed by userfaultfd |
| // registration on the moving space and linear-alloc. |
| void KernelPreparation(); |
| // Called by KernelPreparation() for every memory range being prepared for |
| // userfaultfd registration. |
| void KernelPrepareRangeForUffd(uint8_t* to_addr, |
| uint8_t* from_addr, |
| size_t map_size, |
| int fd, |
| uint8_t* shadow_addr = nullptr); |
| |
| void RegisterUffd(void* addr, size_t size, int mode); |
| void UnregisterUffd(uint8_t* start, size_t len); |
| |
| // Called by thread-pool workers to read uffd_ and process fault events. |
| template <int kMode> |
| void ConcurrentCompaction(uint8_t* buf) REQUIRES_SHARED(Locks::mutator_lock_); |
| // Called by thread-pool workers to compact and copy/map the fault page in |
| // moving space. |
| template <int kMode> |
| void ConcurrentlyProcessMovingPage(uint8_t* fault_page, |
| uint8_t* buf, |
| size_t nr_moving_space_used_pages) |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| // Called by thread-pool workers to process and copy/map the fault page in |
| // linear-alloc. |
| template <int kMode> |
| void ConcurrentlyProcessLinearAllocPage(uint8_t* fault_page, bool is_minor_fault) |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| // Process concurrently all the pages in linear-alloc. Called by gc-thread. |
| void ProcessLinearAlloc() REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| // Returns true if the moving space can be compacted using uffd's minor-fault |
| // feature. |
| bool CanCompactMovingSpaceWithMinorFault(); |
| |
| void FreeFromSpacePages(size_t cur_page_idx, int mode) REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| // Maps processed pages (from moving space and linear-alloc) for uffd's |
| // minor-fault feature. We try to 'claim' all processed (and unmapped) pages |
| // contiguous to 'to_space_start'. |
| // kFirstPageMapping indicates if the first page is already claimed or not. It |
| // also indicates that the ioctl must succeed in mapping the first page. |
| template <bool kFirstPageMapping> |
| void MapProcessedPages(uint8_t* to_space_start, |
| Atomic<PageState>* state_arr, |
| size_t arr_idx, |
| size_t arr_len) REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| bool IsValidFd(int fd) const { return fd >= 0; } |
| // Add/update <class, obj> pair if class > obj and obj is the lowest address |
| // object of class. |
| ALWAYS_INLINE void UpdateClassAfterObjectMap(mirror::Object* obj) |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| // Updates 'class_after_obj_map_' map by updating the keys (class) with its |
| // highest-address super-class (obtained from 'super_class_after_class_map_'), |
| // if there is any. This is to ensure we don't free from-space pages before |
| // the lowest-address obj is compacted. |
| void UpdateClassAfterObjMap(); |
| |
| void MarkZygoteLargeObjects() REQUIRES_SHARED(Locks::mutator_lock_) |
| REQUIRES(Locks::heap_bitmap_lock_); |
| |
| void ZeropageIoctl(void* addr, bool tolerate_eexist, bool tolerate_enoent); |
| void CopyIoctl(void* dst, void* buffer); |
| // Called after updating a linear-alloc page to either map a zero-page if the |
| // page wasn't touched during updation, or map the page via copy-ioctl. And |
| // then updates the page's state to indicate the page is mapped. |
| void MapUpdatedLinearAllocPage(uint8_t* page, |
| uint8_t* shadow_page, |
| Atomic<PageState>& state, |
| bool page_touched); |
| // Called for clamping of 'info_map_' and other GC data structures, which are |
| // small and/or in >4GB address space. There is no real benefit of clamping |
| // them synchronously during app forking. It clamps only if clamp_info_map_status_ |
| // is set to kClampInfoPending, which is done by ClampGrowthLimit(). |
| void MaybeClampGcStructures() REQUIRES(Locks::heap_bitmap_lock_); |
| // Initialize all the info-map related fields of this GC. Returns total size |
| // of all the structures in info-map. |
| size_t InitializeInfoMap(uint8_t* p, size_t moving_space_sz); |
| // Update class-table classes in compaction pause if we are running in debuggable |
| // mode. Only visit class-table in image spaces if 'immune_class_table_only' |
| // is true. |
| void UpdateClassTableClasses(Runtime* runtime, bool immune_class_table_only) |
| REQUIRES_SHARED(Locks::mutator_lock_); |
| |
| // For checkpoints |
| Barrier gc_barrier_; |
| // Every object inside the immune spaces is assumed to be marked. |
| ImmuneSpaces immune_spaces_; |
| // Required only when mark-stack is accessed in shared mode, which happens |
| // when collecting thread-stack roots using checkpoint. Otherwise, we use it |
| // to synchronize on updated_roots_ in debug-builds. |
| Mutex lock_; |
| accounting::ObjectStack* mark_stack_; |
| // Special bitmap wherein all the bits corresponding to an object are set. |
| // TODO: make LiveWordsBitmap encapsulated in this class rather than a |
| // pointer. We tend to access its members in performance-sensitive |
| // code-path. Also, use a single MemMap for all the GC's data structures, |
| // which we will clear in the end. This would help in limiting the number of |
| // VMAs that get created in the kernel. |
| std::unique_ptr<LiveWordsBitmap<kAlignment>> live_words_bitmap_; |
| // Track GC-roots updated so far in a GC-cycle. This is to confirm that no |
| // GC-root is updated twice. |
| // TODO: Must be replaced with an efficient mechanism eventually. Or ensure |
| // that double updation doesn't happen in the first place. |
| std::unique_ptr<std::unordered_set<void*>> updated_roots_ GUARDED_BY(lock_); |
| MemMap from_space_map_; |
| MemMap shadow_to_space_map_; |
| // Any array of live-bytes in logical chunks of kOffsetChunkSize size |
| // in the 'to-be-compacted' space. |
| MemMap info_map_; |
| // Set of page-sized buffers used for compaction. The first page is used by |
| // the GC thread. Subdequent pages are used by mutator threads in case of |
| // SIGBUS feature, and by uffd-worker threads otherwise. In the latter case |
| // the first page is also used for termination of concurrent compaction by |
| // making worker threads terminate the userfaultfd read loop. |
| MemMap compaction_buffers_map_; |
| |
| class LessByArenaAddr { |
| public: |
| bool operator()(const TrackedArena* a, const TrackedArena* b) const { |
| return std::less<uint8_t*>{}(a->Begin(), b->Begin()); |
| } |
| }; |
| |
| // Map of arenas allocated in LinearAlloc arena-pool and last non-zero page, |
| // captured during compaction pause for concurrent updates. |
| std::map<const TrackedArena*, uint8_t*, LessByArenaAddr> linear_alloc_arenas_; |
| // Set of PageStatus arrays, one per arena-pool space. It's extremely rare to |
| // have more than one, but this is to be ready for the worst case. |
| class LinearAllocSpaceData { |
| public: |
| LinearAllocSpaceData(MemMap&& shadow, |
| MemMap&& page_status_map, |
| uint8_t* begin, |
| uint8_t* end, |
| bool already_shared) |
| : shadow_(std::move(shadow)), |
| page_status_map_(std::move(page_status_map)), |
| begin_(begin), |
| end_(end), |
| already_shared_(already_shared) {} |
| |
| MemMap shadow_; |
| MemMap page_status_map_; |
| uint8_t* begin_; |
| uint8_t* end_; |
| // Indicates if the linear-alloc is already MAP_SHARED. |
| bool already_shared_; |
| }; |
| |
| std::vector<LinearAllocSpaceData> linear_alloc_spaces_data_; |
| |
| class ObjReferenceHash { |
| public: |
| uint32_t operator()(const ObjReference& ref) const { |
| return ref.AsVRegValue() >> kObjectAlignmentShift; |
| } |
| }; |
| |
| class ObjReferenceEqualFn { |
| public: |
| bool operator()(const ObjReference& a, const ObjReference& b) const { |
| return a.AsMirrorPtr() == b.AsMirrorPtr(); |
| } |
| }; |
| |
| class LessByObjReference { |
| public: |
| bool operator()(const ObjReference& a, const ObjReference& b) const { |
| return std::less<mirror::Object*>{}(a.AsMirrorPtr(), b.AsMirrorPtr()); |
| } |
| }; |
| |
| // Data structures used to track objects whose layout information is stored in later |
| // allocated classes (at higher addresses). We must be careful not to free the |
| // corresponding from-space pages prematurely. |
| using ObjObjOrderedMap = std::map<ObjReference, ObjReference, LessByObjReference>; |
| using ObjObjUnorderedMap = |
| std::unordered_map<ObjReference, ObjReference, ObjReferenceHash, ObjReferenceEqualFn>; |
| // Unordered map of <K, S> such that the class K (in moving space) has kClassWalkSuper |
| // in reference bitmap and S is its highest address super class. |
| ObjObjUnorderedMap super_class_after_class_hash_map_; |
| // Unordered map of <K, V> such that the class K (in moving space) is after its objects |
| // or would require iterating super-class hierarchy when visiting references. And V is |
| // its lowest address object (in moving space). |
| ObjObjUnorderedMap class_after_obj_hash_map_; |
| // Ordered map constructed before starting compaction using the above two maps. Key is a |
| // class (or super-class) which is higher in address order than some of its object(s) and |
| // value is the corresponding object with lowest address. |
| ObjObjOrderedMap class_after_obj_ordered_map_; |
| // Since the compaction is done in reverse, we use a reverse iterator. It is maintained |
| // either at the pair whose class is lower than the first page to be freed, or at the |
| // pair whose object is not yet compacted. |
| ObjObjOrderedMap::const_reverse_iterator class_after_obj_iter_; |
| // Cached reference to the last class which has kClassWalkSuper in reference |
| // bitmap but has all its super classes lower address order than itself. |
| mirror::Class* walk_super_class_cache_; |
| // Used by FreeFromSpacePages() for maintaining markers in the moving space for |
| // how far the pages have been reclaimed/checked. |
| size_t last_checked_reclaim_page_idx_; |
| uint8_t* last_reclaimed_page_; |
| |
| space::ContinuousSpace* non_moving_space_; |
| space::BumpPointerSpace* const bump_pointer_space_; |
| // The main space bitmap |
| accounting::ContinuousSpaceBitmap* const moving_space_bitmap_; |
| accounting::ContinuousSpaceBitmap* non_moving_space_bitmap_; |
| Thread* thread_running_gc_; |
| // Array of moving-space's pages' compaction status. |
| Atomic<PageState>* moving_pages_status_; |
| size_t vector_length_; |
| size_t live_stack_freeze_size_; |
| |
| uint64_t bytes_scanned_; |
| |
| // For every page in the to-space (post-compact heap) we need to know the |
| // first object from which we must compact and/or update references. This is |
| // for both non-moving and moving space. Additionally, for the moving-space, |
| // we also need the offset within the object from where we need to start |
| // copying. |
| // chunk_info_vec_ holds live bytes for chunks during marking phase. After |
| // marking we perform an exclusive scan to compute offset for every chunk. |
| uint32_t* chunk_info_vec_; |
| // For pages before black allocations, pre_compact_offset_moving_space_[i] |
| // holds offset within the space from where the objects need to be copied in |
| // the ith post-compact page. |
| // Otherwise, black_alloc_pages_first_chunk_size_[i] holds the size of first |
| // non-empty chunk in the ith black-allocations page. |
| union { |
| uint32_t* pre_compact_offset_moving_space_; |
| uint32_t* black_alloc_pages_first_chunk_size_; |
| }; |
| // first_objs_moving_space_[i] is the pre-compact address of the object which |
| // would overlap with the starting boundary of the ith post-compact page. |
| ObjReference* first_objs_moving_space_; |
| // First object for every page. It could be greater than the page's start |
| // address, or null if the page is empty. |
| ObjReference* first_objs_non_moving_space_; |
| size_t non_moving_first_objs_count_; |
| // Length of first_objs_moving_space_ and pre_compact_offset_moving_space_ |
| // arrays. Also the number of pages which are to be compacted. |
| size_t moving_first_objs_count_; |
| // Number of pages containing black-allocated objects, indicating number of |
| // pages to be slid. |
| size_t black_page_count_; |
| |
| uint8_t* from_space_begin_; |
| // Cached values of moving-space range to optimize checking if reference |
| // belongs to moving-space or not. May get updated if and when heap is |
| // clamped. |
| uint8_t* const moving_space_begin_; |
| uint8_t* moving_space_end_; |
| // moving-space's end pointer at the marking pause. All allocations beyond |
| // this will be considered black in the current GC cycle. Aligned up to page |
| // size. |
| uint8_t* black_allocations_begin_; |
| // End of compacted space. Use for computing post-compact addr of black |
| // allocated objects. Aligned up to page size. |
| uint8_t* post_compact_end_; |
| // Cache (black_allocations_begin_ - post_compact_end_) for post-compact |
| // address computations. |
| ptrdiff_t black_objs_slide_diff_; |
| // Cache (from_space_begin_ - bump_pointer_space_->Begin()) so that we can |
| // compute from-space address of a given pre-comapct addr efficiently. |
| ptrdiff_t from_space_slide_diff_; |
| |
| // TODO: Remove once an efficient mechanism to deal with double root updation |
| // is incorporated. |
| void* stack_high_addr_; |
| void* stack_low_addr_; |
| |
| uint8_t* conc_compaction_termination_page_; |
| |
| PointerSize pointer_size_; |
| // Number of objects freed during this GC in moving space. It is decremented |
| // every time an object is discovered. And total-object count is added to it |
| // in MarkingPause(). It reaches the correct count only once the marking phase |
| // is completed. |
| int32_t freed_objects_; |
| // memfds for moving space for using userfaultfd's minor-fault feature. |
| // Initialized to kFdUnused to indicate that mmap should be MAP_PRIVATE in |
| // KernelPrepareRange(). |
| int moving_to_space_fd_; |
| int moving_from_space_fd_; |
| // Userfault file descriptor, accessed only by the GC itself. |
| // kFallbackMode value indicates that we are in the fallback mode. |
| int uffd_; |
| // Number of mutator-threads currently executing SIGBUS handler. When the |
| // GC-thread is done with compaction, it set the most significant bit to |
| // indicate that. Mutator threads check for the flag when incrementing in the |
| // handler. |
| std::atomic<SigbusCounterType> sigbus_in_progress_count_; |
| // Number of mutator-threads/uffd-workers working on moving-space page. It |
| // must be 0 before gc-thread can unregister the space after it's done |
| // sequentially compacting all pages of the space. |
| std::atomic<uint16_t> compaction_in_progress_count_; |
| // When using SIGBUS feature, this counter is used by mutators to claim a page |
| // out of compaction buffers to be used for the entire compaction cycle. |
| std::atomic<uint16_t> compaction_buffer_counter_; |
| // Used to exit from compaction loop at the end of concurrent compaction |
| uint8_t thread_pool_counter_; |
| // True while compacting. |
| bool compacting_; |
| // Flag indicating whether one-time uffd initialization has been done. It will |
| // be false on the first GC for non-zygote processes, and always for zygote. |
| // Its purpose is to minimize the userfaultfd overhead to the minimal in |
| // Heap::PostForkChildAction() as it's invoked in app startup path. With |
| // this, we register the compaction-termination page on the first GC. |
| bool uffd_initialized_; |
| // Flag indicating if userfaultfd supports minor-faults. Set appropriately in |
| // CreateUserfaultfd(), where we get this information from the kernel. |
| const bool uffd_minor_fault_supported_; |
| // Flag indicating if we should use sigbus signals instead of threads to |
| // handle userfaults. |
| const bool use_uffd_sigbus_; |
| // For non-zygote processes this flag indicates if the spaces are ready to |
| // start using userfaultfd's minor-fault feature. This initialization involves |
| // starting to use shmem (memfd_create) for the userfaultfd protected spaces. |
| bool minor_fault_initialized_; |
| // Set to true when linear-alloc can start mapping with MAP_SHARED. Set on |
| // non-zygote processes during first GC, which sets up everyting for using |
| // minor-fault from next GC. |
| bool map_linear_alloc_shared_; |
| // Clamping statue of `info_map_`. Initialized with 'NotDone'. Once heap is |
| // clamped but info_map_ is delayed, we set it to 'Pending'. Once 'info_map_' |
| // is also clamped, then we set it to 'Finished'. |
| ClampInfoStatus clamp_info_map_status_; |
| |
| class FlipCallback; |
| class ThreadFlipVisitor; |
| class VerifyRootMarkedVisitor; |
| class ScanObjectVisitor; |
| class CheckpointMarkThreadRoots; |
| template <size_t kBufferSize> |
| class ThreadRootsVisitor; |
| class RefFieldsVisitor; |
| template <bool kCheckBegin, bool kCheckEnd> class RefsUpdateVisitor; |
| class ArenaPoolPageUpdater; |
| class ClassLoaderRootsUpdater; |
| class LinearAllocPageUpdater; |
| class ImmuneSpaceUpdateObjVisitor; |
| class ConcurrentCompactionGcTask; |
| |
| DISALLOW_IMPLICIT_CONSTRUCTORS(MarkCompact); |
| }; |
| |
| std::ostream& operator<<(std::ostream& os, MarkCompact::PageState value); |
| std::ostream& operator<<(std::ostream& os, MarkCompact::ClampInfoStatus value); |
| |
| } // namespace collector |
| } // namespace gc |
| } // namespace art |
| |
| #endif // ART_RUNTIME_GC_COLLECTOR_MARK_COMPACT_H_ |