Gitiles
Code Review Sign In
LeafOS / LeafOS-Project / android_art / 7c107e133f6d3ee33543891b69c1c4c911a66359 / . / runtime / gc / collector / mark_compact.h
blob: 1ecb49ae52e527578b018917991de23fd7bc20fe [file] [log] [blame]
/*
* 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 {
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 < kPageSize);
// 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 kPageSize live bytes starting from 'offset' (within the moving space),
// which must be within 'obj', into the kPageSize 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 kPageSize 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_