1 /* 2 * Copyright 2021 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_RUNTIME_GC_COLLECTOR_MARK_COMPACT_H_ 18 #define ART_RUNTIME_GC_COLLECTOR_MARK_COMPACT_H_ 19 20 #include <signal.h> 21 22 #include <map> 23 #include <memory> 24 #include <unordered_set> 25 26 #include "barrier.h" 27 #include "base/atomic.h" 28 #include "base/gc_visited_arena_pool.h" 29 #include "base/macros.h" 30 #include "base/mutex.h" 31 #include "garbage_collector.h" 32 #include "gc/accounting/atomic_stack.h" 33 #include "gc/accounting/bitmap-inl.h" 34 #include "gc/accounting/heap_bitmap.h" 35 #include "gc_root.h" 36 #include "immune_spaces.h" 37 #include "offsets.h" 38 39 namespace art HIDDEN { 40 41 EXPORT bool KernelSupportsUffd(); 42 43 namespace mirror { 44 class DexCache; 45 } // namespace mirror 46 47 namespace gc { 48 49 class Heap; 50 51 namespace space { 52 class BumpPointerSpace; 53 } // namespace space 54 55 namespace collector { 56 class MarkCompact final : public GarbageCollector { 57 public: 58 using SigbusCounterType = uint32_t; 59 60 static constexpr size_t kAlignment = kObjectAlignment; 61 static constexpr int kCopyMode = -1; 62 // Fake file descriptor for fall back mode (when uffd isn't available) 63 static constexpr int kFallbackMode = -3; 64 static constexpr int kFdUnused = -2; 65 66 // Bitmask for the compaction-done bit in the sigbus_in_progress_count_. 67 static constexpr SigbusCounterType kSigbusCounterCompactionDoneMask = 68 1u << (BitSizeOf<SigbusCounterType>() - 1); 69 70 explicit MarkCompact(Heap* heap); 71 ~MarkCompact()72 ~MarkCompact() {} 73 74 void RunPhases() override REQUIRES(!Locks::mutator_lock_, !lock_); 75 76 void ClampGrowthLimit(size_t new_capacity) REQUIRES(Locks::heap_bitmap_lock_); 77 // Updated before (or in) pre-compaction pause and is accessed only in the 78 // pause or during concurrent compaction. The flag is reset in next GC cycle's 79 // InitializePhase(). Therefore, it's safe to update without any memory ordering. IsCompacting()80 bool IsCompacting() const { return compacting_; } 81 82 // Called by SIGBUS handler. NO_THREAD_SAFETY_ANALYSIS for mutator-lock, which 83 // is asserted in the function. 84 bool SigbusHandler(siginfo_t* info) REQUIRES(!lock_) NO_THREAD_SAFETY_ANALYSIS; 85 GetGcType()86 GcType GetGcType() const override { 87 return kGcTypeFull; 88 } 89 GetCollectorType()90 CollectorType GetCollectorType() const override { 91 return kCollectorTypeCMC; 92 } 93 GetBarrier()94 Barrier& GetBarrier() { 95 return gc_barrier_; 96 } 97 98 mirror::Object* MarkObject(mirror::Object* obj) override 99 REQUIRES_SHARED(Locks::mutator_lock_) 100 REQUIRES(Locks::heap_bitmap_lock_); 101 102 void MarkHeapReference(mirror::HeapReference<mirror::Object>* obj, 103 bool do_atomic_update) override 104 REQUIRES_SHARED(Locks::mutator_lock_) 105 REQUIRES(Locks::heap_bitmap_lock_); 106 107 void VisitRoots(mirror::Object*** roots, 108 size_t count, 109 const RootInfo& info) override 110 REQUIRES_SHARED(Locks::mutator_lock_) 111 REQUIRES(Locks::heap_bitmap_lock_); 112 void VisitRoots(mirror::CompressedReference<mirror::Object>** roots, 113 size_t count, 114 const RootInfo& info) override 115 REQUIRES_SHARED(Locks::mutator_lock_) 116 REQUIRES(Locks::heap_bitmap_lock_); 117 118 bool IsNullOrMarkedHeapReference(mirror::HeapReference<mirror::Object>* obj, 119 bool do_atomic_update) override 120 REQUIRES_SHARED(Locks::mutator_lock_) 121 REQUIRES(Locks::heap_bitmap_lock_); 122 123 void RevokeAllThreadLocalBuffers() override; 124 125 void DelayReferenceReferent(ObjPtr<mirror::Class> klass, 126 ObjPtr<mirror::Reference> reference) override 127 REQUIRES_SHARED(Locks::mutator_lock_, Locks::heap_bitmap_lock_); 128 129 mirror::Object* IsMarked(mirror::Object* obj) override 130 REQUIRES_SHARED(Locks::mutator_lock_, Locks::heap_bitmap_lock_); 131 GetFromSpaceAddrFromBarrier(mirror::Object * old_ref)132 mirror::Object* GetFromSpaceAddrFromBarrier(mirror::Object* old_ref) { 133 CHECK(compacting_); 134 if (HasAddress(old_ref)) { 135 return GetFromSpaceAddr(old_ref); 136 } 137 return old_ref; 138 } 139 // Called from Heap::PostForkChildAction() for non-zygote processes and from 140 // PrepareForCompaction() for zygote processes. Returns true if uffd was 141 // created or was already done. 142 bool CreateUserfaultfd(bool post_fork); 143 144 // Returns a pair indicating if userfaultfd itself is available (first) and if 145 // so then whether its minor-fault feature is available or not (second). 146 static std::pair<bool, bool> GetUffdAndMinorFault(); 147 148 // Add linear-alloc space data when a new space is added to 149 // GcVisitedArenaPool, which mostly happens only once. 150 void AddLinearAllocSpaceData(uint8_t* begin, size_t len); 151 152 // In copy-mode of userfaultfd, we don't need to reach a 'processed' state as 153 // it's given that processing thread also copies the page, thereby mapping it. 154 // The order is important as we may treat them as integers. Also 155 // 'kUnprocessed' should be set to 0 as we rely on madvise(dontneed) to return 156 // us zero'ed pages, which implicitly makes page-status initialized to 'kUnprocessed'. 157 enum class PageState : uint8_t { 158 kUnprocessed = 0, // Not processed yet. 159 kProcessing = 1, // Being processed by GC thread and will not be mapped 160 kProcessed = 2, // Processed but not mapped 161 kProcessingAndMapping = 3, // Being processed by GC or mutator and will be mapped 162 kMutatorProcessing = 4, // Being processed by mutator thread 163 kProcessedAndMapping = 5, // Processed and will be mapped 164 kProcessedAndMapped = 6 // Processed and mapped. For SIGBUS. 165 }; 166 167 // Different heap clamping states. 168 enum class ClampInfoStatus : uint8_t { 169 kClampInfoNotDone, 170 kClampInfoPending, 171 kClampInfoFinished 172 }; 173 174 private: 175 using ObjReference = mirror::CompressedReference<mirror::Object>; 176 static constexpr uint32_t kPageStateMask = (1 << BitSizeOf<uint8_t>()) - 1; 177 // Number of bits (live-words) covered by a single chunk-info (below) 178 // entry/word. 179 // TODO: Since popcount is performed usomg SIMD instructions, we should 180 // consider using 128-bit in order to halve the chunk-info size. 181 static constexpr uint32_t kBitsPerVectorWord = kBitsPerIntPtrT; 182 static constexpr uint32_t kOffsetChunkSize = kBitsPerVectorWord * kAlignment; 183 static_assert(kOffsetChunkSize < kMinPageSize); 184 // Bitmap with bits corresponding to every live word set. For an object 185 // which is 4 words in size will have the corresponding 4 bits set. This is 186 // required for efficient computation of new-address (post-compaction) from 187 // the given old-address (pre-compaction). 188 template <size_t kAlignment> 189 class LiveWordsBitmap : private accounting::MemoryRangeBitmap<kAlignment> { 190 using Bitmap = accounting::Bitmap; 191 using MemRangeBitmap = accounting::MemoryRangeBitmap<kAlignment>; 192 193 public: 194 static_assert(IsPowerOfTwo(kBitsPerVectorWord)); 195 static_assert(IsPowerOfTwo(Bitmap::kBitsPerBitmapWord)); 196 static_assert(kBitsPerVectorWord >= Bitmap::kBitsPerBitmapWord); 197 static constexpr uint32_t kBitmapWordsPerVectorWord = 198 kBitsPerVectorWord / Bitmap::kBitsPerBitmapWord; 199 static_assert(IsPowerOfTwo(kBitmapWordsPerVectorWord)); 200 using MemRangeBitmap::SetBitmapSize; 201 static LiveWordsBitmap* Create(uintptr_t begin, uintptr_t end); 202 203 // Return offset (within the indexed chunk-info) of the nth live word. 204 uint32_t FindNthLiveWordOffset(size_t chunk_idx, uint32_t n) const; 205 // Sets all bits in the bitmap corresponding to the given range. Also 206 // returns the bit-index of the first word. 207 ALWAYS_INLINE uintptr_t SetLiveWords(uintptr_t begin, size_t size); 208 // Count number of live words upto the given bit-index. This is to be used 209 // to compute the post-compact address of an old reference. 210 ALWAYS_INLINE size_t CountLiveWordsUpto(size_t bit_idx) const; 211 // Call 'visitor' for every stride of contiguous marked bits in the live-words 212 // bitmap, starting from begin_bit_idx. Only visit 'bytes' live bytes or 213 // until 'end', whichever comes first. 214 // Visitor is called with index of the first marked bit in the stride, 215 // stride size and whether it's the last stride in the given range or not. 216 template <typename Visitor> 217 ALWAYS_INLINE void VisitLiveStrides(uintptr_t begin_bit_idx, 218 uint8_t* end, 219 const size_t bytes, 220 Visitor&& visitor) const 221 REQUIRES_SHARED(Locks::mutator_lock_); 222 // Count the number of live bytes in the given vector entry. 223 size_t LiveBytesInBitmapWord(size_t chunk_idx) const; ClearBitmap()224 void ClearBitmap() { Bitmap::Clear(); } Begin()225 ALWAYS_INLINE uintptr_t Begin() const { return MemRangeBitmap::CoverBegin(); } HasAddress(mirror::Object * obj)226 ALWAYS_INLINE bool HasAddress(mirror::Object* obj) const { 227 return MemRangeBitmap::HasAddress(reinterpret_cast<uintptr_t>(obj)); 228 } Test(uintptr_t bit_index)229 ALWAYS_INLINE bool Test(uintptr_t bit_index) const { 230 return Bitmap::TestBit(bit_index); 231 } Test(mirror::Object * obj)232 ALWAYS_INLINE bool Test(mirror::Object* obj) const { 233 return MemRangeBitmap::Test(reinterpret_cast<uintptr_t>(obj)); 234 } GetWord(size_t index)235 ALWAYS_INLINE uintptr_t GetWord(size_t index) const { 236 static_assert(kBitmapWordsPerVectorWord == 1); 237 return Bitmap::Begin()[index * kBitmapWordsPerVectorWord]; 238 } 239 }; 240 HasAddress(mirror::Object * obj,uint8_t * begin,uint8_t * end)241 static bool HasAddress(mirror::Object* obj, uint8_t* begin, uint8_t* end) { 242 uint8_t* ptr = reinterpret_cast<uint8_t*>(obj); 243 return ptr >= begin && ptr < end; 244 } 245 HasAddress(mirror::Object * obj)246 bool HasAddress(mirror::Object* obj) const { 247 return HasAddress(obj, moving_space_begin_, moving_space_end_); 248 } 249 // For a given object address in pre-compact space, return the corresponding 250 // address in the from-space, where heap pages are relocated in the compaction 251 // pause. GetFromSpaceAddr(mirror::Object * obj)252 mirror::Object* GetFromSpaceAddr(mirror::Object* obj) const { 253 DCHECK(HasAddress(obj)) << " obj=" << obj; 254 return reinterpret_cast<mirror::Object*>(reinterpret_cast<uintptr_t>(obj) 255 + from_space_slide_diff_); 256 } 257 258 inline bool IsOnAllocStack(mirror::Object* ref) 259 REQUIRES_SHARED(Locks::mutator_lock_, Locks::heap_bitmap_lock_); 260 // Verifies that that given object reference refers to a valid object. 261 // Otherwise fataly dumps logs, including those from callback. 262 template <typename Callback> 263 void VerifyObject(mirror::Object* ref, Callback& callback) const 264 REQUIRES_SHARED(Locks::mutator_lock_); 265 // Check if the obj is within heap and has a klass which is likely to be valid 266 // mirror::Class. 267 bool IsValidObject(mirror::Object* obj) const REQUIRES_SHARED(Locks::mutator_lock_); 268 void InitializePhase(); 269 void FinishPhase() REQUIRES(!Locks::mutator_lock_, !Locks::heap_bitmap_lock_, !lock_); 270 void MarkingPhase() REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::heap_bitmap_lock_); 271 void CompactionPhase() REQUIRES_SHARED(Locks::mutator_lock_); 272 273 void SweepSystemWeaks(Thread* self, Runtime* runtime, const bool paused) 274 REQUIRES_SHARED(Locks::mutator_lock_) 275 REQUIRES(!Locks::heap_bitmap_lock_); 276 // Update the reference at given offset in the given object with post-compact 277 // address. [begin, end) is moving-space range. 278 ALWAYS_INLINE void UpdateRef(mirror::Object* obj, 279 MemberOffset offset, 280 uint8_t* begin, 281 uint8_t* end) REQUIRES_SHARED(Locks::mutator_lock_); 282 283 // Verify that the gc-root is updated only once. Returns false if the update 284 // shouldn't be done. 285 ALWAYS_INLINE bool VerifyRootSingleUpdate(void* root, 286 mirror::Object* old_ref, 287 const RootInfo& info) 288 REQUIRES_SHARED(Locks::mutator_lock_); 289 // Update the given root with post-compact address. [begin, end) is 290 // moving-space range. 291 ALWAYS_INLINE void UpdateRoot(mirror::CompressedReference<mirror::Object>* root, 292 uint8_t* begin, 293 uint8_t* end, 294 const RootInfo& info = RootInfo(RootType::kRootUnknown)) 295 REQUIRES_SHARED(Locks::mutator_lock_); 296 ALWAYS_INLINE void UpdateRoot(mirror::Object** root, 297 uint8_t* begin, 298 uint8_t* end, 299 const RootInfo& info = RootInfo(RootType::kRootUnknown)) 300 REQUIRES_SHARED(Locks::mutator_lock_); 301 // Given the pre-compact address, the function returns the post-compact 302 // address of the given object. [begin, end) is moving-space range. 303 ALWAYS_INLINE mirror::Object* PostCompactAddress(mirror::Object* old_ref, 304 uint8_t* begin, 305 uint8_t* end) const 306 REQUIRES_SHARED(Locks::mutator_lock_); 307 // Compute post-compact address of an object in moving space. This function 308 // assumes that old_ref is in moving space. 309 ALWAYS_INLINE mirror::Object* PostCompactAddressUnchecked(mirror::Object* old_ref) const 310 REQUIRES_SHARED(Locks::mutator_lock_); 311 // Compute the new address for an object which was allocated prior to starting 312 // this GC cycle. 313 ALWAYS_INLINE mirror::Object* PostCompactOldObjAddr(mirror::Object* old_ref) const 314 REQUIRES_SHARED(Locks::mutator_lock_); 315 // Compute the new address for an object which was black allocated during this 316 // GC cycle. 317 ALWAYS_INLINE mirror::Object* PostCompactBlackObjAddr(mirror::Object* old_ref) const 318 REQUIRES_SHARED(Locks::mutator_lock_); 319 // Clears (for alloc spaces in the beginning of marking phase) or ages the 320 // card table. Also, identifies immune spaces and mark bitmap. 321 void PrepareCardTableForMarking(bool clear_alloc_space_cards) 322 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_); 323 324 // Perform one last round of marking, identifying roots from dirty cards 325 // during a stop-the-world (STW) pause. 326 void MarkingPause() REQUIRES(Locks::mutator_lock_, !Locks::heap_bitmap_lock_); 327 // Perform stop-the-world pause prior to concurrent compaction. 328 // Updates GC-roots and protects heap so that during the concurrent 329 // compaction phase we can receive faults and compact the corresponding pages 330 // on the fly. 331 void CompactionPause() REQUIRES(Locks::mutator_lock_); 332 // Compute offsets (in chunk_info_vec_) and other data structures required 333 // during concurrent compaction. Also determines a black-dense region at the 334 // beginning of the moving space which is not compacted. Returns false if 335 // performing compaction isn't required. 336 bool PrepareForCompaction() REQUIRES_SHARED(Locks::mutator_lock_); 337 338 // Copy gPageSize live bytes starting from 'offset' (within the moving space), 339 // which must be within 'obj', into the gPageSize sized memory pointed by 'addr'. 340 // Then update the references within the copied objects. The boundary objects are 341 // partially updated such that only the references that lie in the page are updated. 342 // This is necessary to avoid cascading userfaults. 343 void CompactPage(mirror::Object* obj, uint32_t offset, uint8_t* addr, bool needs_memset_zero) 344 REQUIRES_SHARED(Locks::mutator_lock_); 345 // Compact the bump-pointer space. Pass page that should be used as buffer for 346 // userfaultfd. 347 template <int kMode> 348 void CompactMovingSpace(uint8_t* page) REQUIRES_SHARED(Locks::mutator_lock_); 349 350 // Compact the given page as per func and change its state. Also map/copy the 351 // page, if required. Returns true if the page was compacted, else false. 352 template <int kMode, typename CompactionFn> 353 ALWAYS_INLINE bool DoPageCompactionWithStateChange(size_t page_idx, 354 uint8_t* to_space_page, 355 uint8_t* page, 356 bool map_immediately, 357 CompactionFn func) 358 REQUIRES_SHARED(Locks::mutator_lock_); 359 360 // Update all the objects in the given non-moving page. 'first' object 361 // could have started in some preceding page. 362 void UpdateNonMovingPage(mirror::Object* first, 363 uint8_t* page, 364 ptrdiff_t from_space_diff, 365 accounting::ContinuousSpaceBitmap* bitmap) 366 REQUIRES_SHARED(Locks::mutator_lock_); 367 // Update all the references in the non-moving space. 368 void UpdateNonMovingSpace() REQUIRES_SHARED(Locks::mutator_lock_); 369 370 // For all the pages in non-moving space, find the first object that overlaps 371 // with the pages' start address, and store in first_objs_non_moving_space_ array. 372 size_t InitNonMovingFirstObjects(uintptr_t begin, 373 uintptr_t end, 374 accounting::ContinuousSpaceBitmap* bitmap, 375 ObjReference* first_objs_arr) 376 REQUIRES_SHARED(Locks::mutator_lock_); 377 // In addition to the first-objects for every post-compact moving space page, 378 // also find offsets within those objects from where the contents should be 379 // copied to the page. The offsets are relative to the moving-space's 380 // beginning. Store the computed first-object and offset in first_objs_moving_space_ 381 // and pre_compact_offset_moving_space_ respectively. 382 void InitMovingSpaceFirstObjects(size_t vec_len, size_t to_space_page_idx) 383 REQUIRES_SHARED(Locks::mutator_lock_); 384 385 // Gather the info related to black allocations from bump-pointer space to 386 // enable concurrent sliding of these pages. 387 void UpdateMovingSpaceBlackAllocations() REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_); 388 // Update first-object info from allocation-stack for non-moving space black 389 // allocations. 390 void UpdateNonMovingSpaceBlackAllocations() REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_); 391 392 // Slides (retain the empty holes, which are usually part of some in-use TLAB) 393 // black page in the moving space. 'first_obj' is the object that overlaps with 394 // the first byte of the page being slid. pre_compact_page is the pre-compact 395 // address of the page being slid. 'dest' is the gPageSize sized memory where 396 // the contents would be copied. 397 void SlideBlackPage(mirror::Object* first_obj, 398 mirror::Object* next_page_first_obj, 399 uint32_t first_chunk_size, 400 uint8_t* const pre_compact_page, 401 uint8_t* dest, 402 bool needs_memset_zero) REQUIRES_SHARED(Locks::mutator_lock_); 403 404 // Perform reference-processing and the likes before sweeping the non-movable 405 // spaces. 406 void ReclaimPhase() REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::heap_bitmap_lock_); 407 408 // Mark GC-roots (except from immune spaces and thread-stacks) during a STW pause. 409 void ReMarkRoots(Runtime* runtime) REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_); 410 // Concurrently mark GC-roots, except from immune spaces. 411 void MarkRoots(VisitRootFlags flags) REQUIRES_SHARED(Locks::mutator_lock_) 412 REQUIRES(Locks::heap_bitmap_lock_); 413 // Collect thread stack roots via a checkpoint. 414 void MarkRootsCheckpoint(Thread* self, Runtime* runtime) REQUIRES_SHARED(Locks::mutator_lock_) 415 REQUIRES(Locks::heap_bitmap_lock_); 416 // Second round of concurrent marking. Mark all gray objects that got dirtied 417 // since the first round. 418 void PreCleanCards() REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_); 419 420 void MarkNonThreadRoots(Runtime* runtime) REQUIRES_SHARED(Locks::mutator_lock_) 421 REQUIRES(Locks::heap_bitmap_lock_); 422 void MarkConcurrentRoots(VisitRootFlags flags, Runtime* runtime) 423 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_); 424 425 // Traverse through the reachable objects and mark them. 426 void MarkReachableObjects() REQUIRES_SHARED(Locks::mutator_lock_) 427 REQUIRES(Locks::heap_bitmap_lock_); 428 // Scan (only) immune spaces looking for references into the garbage collected 429 // spaces. 430 void UpdateAndMarkModUnion() REQUIRES_SHARED(Locks::mutator_lock_) 431 REQUIRES(Locks::heap_bitmap_lock_); 432 // Scan mod-union and card tables, covering all the spaces, to identify dirty objects. 433 // These are in 'minimum age' cards, which is 'kCardAged' in case of concurrent (second round) 434 // marking and kCardDirty during the STW pause. 435 void ScanDirtyObjects(bool paused, uint8_t minimum_age) REQUIRES_SHARED(Locks::mutator_lock_) 436 REQUIRES(Locks::heap_bitmap_lock_); 437 // Recursively mark dirty objects. Invoked both concurrently as well in a STW 438 // pause in PausePhase(). 439 void RecursiveMarkDirtyObjects(bool paused, uint8_t minimum_age) 440 REQUIRES_SHARED(Locks::mutator_lock_) 441 REQUIRES(Locks::heap_bitmap_lock_); 442 // Go through all the objects in the mark-stack until it's empty. 443 void ProcessMarkStack() override REQUIRES_SHARED(Locks::mutator_lock_) 444 REQUIRES(Locks::heap_bitmap_lock_); 445 void ExpandMarkStack() REQUIRES_SHARED(Locks::mutator_lock_) 446 REQUIRES(Locks::heap_bitmap_lock_); 447 448 // Scan object for references. If kUpdateLivewords is true then set bits in 449 // the live-words bitmap and add size to chunk-info. 450 template <bool kUpdateLiveWords> 451 void ScanObject(mirror::Object* obj) REQUIRES_SHARED(Locks::mutator_lock_) 452 REQUIRES(Locks::heap_bitmap_lock_); 453 // Push objects to the mark-stack right after successfully marking objects. 454 void PushOnMarkStack(mirror::Object* obj) 455 REQUIRES_SHARED(Locks::mutator_lock_) 456 REQUIRES(Locks::heap_bitmap_lock_); 457 458 // Update the live-words bitmap as well as add the object size to the 459 // chunk-info vector. Both are required for computation of post-compact addresses. 460 // Also updates freed_objects_ counter. 461 void UpdateLivenessInfo(mirror::Object* obj, size_t obj_size) 462 REQUIRES_SHARED(Locks::mutator_lock_); 463 464 void ProcessReferences(Thread* self) 465 REQUIRES_SHARED(Locks::mutator_lock_) 466 REQUIRES(!Locks::heap_bitmap_lock_); 467 468 void MarkObjectNonNull(mirror::Object* obj, 469 mirror::Object* holder = nullptr, 470 MemberOffset offset = MemberOffset(0)) 471 REQUIRES_SHARED(Locks::mutator_lock_) 472 REQUIRES(Locks::heap_bitmap_lock_); 473 474 void MarkObject(mirror::Object* obj, mirror::Object* holder, MemberOffset offset) 475 REQUIRES_SHARED(Locks::mutator_lock_) 476 REQUIRES(Locks::heap_bitmap_lock_); 477 478 template <bool kParallel> 479 bool MarkObjectNonNullNoPush(mirror::Object* obj, 480 mirror::Object* holder = nullptr, 481 MemberOffset offset = MemberOffset(0)) 482 REQUIRES(Locks::heap_bitmap_lock_) 483 REQUIRES_SHARED(Locks::mutator_lock_); 484 485 void Sweep(bool swap_bitmaps) REQUIRES_SHARED(Locks::mutator_lock_) 486 REQUIRES(Locks::heap_bitmap_lock_); 487 void SweepLargeObjects(bool swap_bitmaps) REQUIRES_SHARED(Locks::mutator_lock_) 488 REQUIRES(Locks::heap_bitmap_lock_); 489 490 // Perform all kernel operations required for concurrent compaction. Includes 491 // mremap to move pre-compact pages to from-space, followed by userfaultfd 492 // registration on the moving space and linear-alloc. 493 void KernelPreparation(); 494 // Called by KernelPreparation() for every memory range being prepared for 495 // userfaultfd registration. 496 void KernelPrepareRangeForUffd(uint8_t* to_addr, uint8_t* from_addr, size_t map_size); 497 498 void RegisterUffd(void* addr, size_t size); 499 void UnregisterUffd(uint8_t* start, size_t len); 500 501 // Called by SIGBUS handler to compact and copy/map the fault page in moving space. 502 void ConcurrentlyProcessMovingPage(uint8_t* fault_page, 503 uint8_t* buf, 504 size_t nr_moving_space_used_pages, 505 bool tolerate_enoent) REQUIRES_SHARED(Locks::mutator_lock_); 506 // Called by SIGBUS handler to process and copy/map the fault page in linear-alloc. 507 void ConcurrentlyProcessLinearAllocPage(uint8_t* fault_page, bool tolerate_enoent) 508 REQUIRES_SHARED(Locks::mutator_lock_); 509 510 // Process concurrently all the pages in linear-alloc. Called by gc-thread. 511 void ProcessLinearAlloc() REQUIRES_SHARED(Locks::mutator_lock_); 512 513 // Does the following: 514 // 1. Checks the status of to-space pages in [cur_page_idx, 515 // last_checked_reclaim_page_idx_) range to see whether the corresponding 516 // from-space pages can be reused. 517 // 2. Taking into consideration classes which are allocated after their 518 // objects (in address order), computes the page (in from-space) from which 519 // actual reclamation can be done. 520 // 3. Map the pages in [cur_page_idx, end_idx_for_mapping) range. 521 // 4. Madvise the pages in [page from (2), last_reclaimed_page_) 522 bool FreeFromSpacePages(size_t cur_page_idx, int mode, size_t end_idx_for_mapping) 523 REQUIRES_SHARED(Locks::mutator_lock_); 524 525 // Maps moving space pages in [start_idx, arr_len) range. It fetches the page 526 // address containing the compacted content from moving_pages_status_ array. 527 // 'from_fault' is true when called from userfault (sigbus handler). 528 // 'return_on_contention' is set to true by gc-thread while it is compacting 529 // pages. In the end it calls the function with `return_on_contention=false` 530 // to ensure all pages are mapped. Returns number of pages that are mapped. 531 size_t MapMovingSpacePages(size_t start_idx, 532 size_t arr_len, 533 bool from_fault, 534 bool return_on_contention, 535 bool tolerate_enoent) REQUIRES_SHARED(Locks::mutator_lock_); 536 IsValidFd(int fd)537 bool IsValidFd(int fd) const { return fd >= 0; } 538 GetPageStateFromWord(uint32_t page_word)539 PageState GetPageStateFromWord(uint32_t page_word) { 540 return static_cast<PageState>(static_cast<uint8_t>(page_word)); 541 } 542 GetMovingPageState(size_t idx)543 PageState GetMovingPageState(size_t idx) { 544 return GetPageStateFromWord(moving_pages_status_[idx].load(std::memory_order_acquire)); 545 } 546 547 // Add/update <class, obj> pair if class > obj and obj is the lowest address 548 // object of class. 549 ALWAYS_INLINE void UpdateClassAfterObjectMap(mirror::Object* obj) 550 REQUIRES_SHARED(Locks::mutator_lock_); 551 552 void MarkZygoteLargeObjects() REQUIRES_SHARED(Locks::mutator_lock_) 553 REQUIRES(Locks::heap_bitmap_lock_); 554 555 // Map zero-pages in the given range. 'tolerate_eexist' and 'tolerate_enoent' 556 // help us decide if we should expect EEXIST or ENOENT back from the ioctl 557 // respectively. It may return after mapping fewer pages than requested. 558 // found to be contended, then we delay the operations based on thread's 559 // Returns number of bytes (multiple of page-size) now known to be mapped. 560 size_t ZeropageIoctl(void* addr, size_t length, bool tolerate_eexist, bool tolerate_enoent); 561 // Map 'buffer' to 'dst', both being 'length' bytes using at most one ioctl 562 // call. 'return_on_contention' indicates that the function should return 563 // as soon as mmap_lock contention is detected. Like ZeropageIoctl(), this 564 // function also uses thread's priority to decide how long we delay before 565 // forcing the ioctl operation. If ioctl returns EEXIST, then also function 566 // returns. Returns number of bytes (multiple of page-size) mapped. 567 size_t CopyIoctl( 568 void* dst, void* buffer, size_t length, bool return_on_contention, bool tolerate_enoent); 569 570 // Called after updating linear-alloc page(s) to map the page. It first 571 // updates the state of the pages to kProcessedAndMapping and after ioctl to 572 // kProcessedAndMapped. Returns true if at least the first page is now mapped. 573 // If 'free_pages' is true then also frees shadow pages. If 'single_ioctl' 574 // is true, then stops after first ioctl. 575 bool MapUpdatedLinearAllocPages(uint8_t* start_page, 576 uint8_t* start_shadow_page, 577 Atomic<PageState>* state, 578 size_t length, 579 bool free_pages, 580 bool single_ioctl, 581 bool tolerate_enoent); 582 // Called for clamping of 'info_map_' and other GC data structures, which are 583 // small and/or in >4GB address space. There is no real benefit of clamping 584 // them synchronously during app forking. It clamps only if clamp_info_map_status_ 585 // is set to kClampInfoPending, which is done by ClampGrowthLimit(). 586 void MaybeClampGcStructures() REQUIRES(Locks::heap_bitmap_lock_); 587 588 size_t ComputeInfoMapSize(); 589 // Initialize all the info-map related fields of this GC. Returns total size 590 // of all the structures in info-map. 591 size_t InitializeInfoMap(uint8_t* p, size_t moving_space_sz); 592 // Update class-table classes in compaction pause if we are running in debuggable 593 // mode. Only visit class-table in image spaces if 'immune_class_table_only' 594 // is true. 595 void UpdateClassTableClasses(Runtime* runtime, bool immune_class_table_only) 596 REQUIRES_SHARED(Locks::mutator_lock_); 597 598 // For checkpoints 599 Barrier gc_barrier_; 600 // Every object inside the immune spaces is assumed to be marked. 601 ImmuneSpaces immune_spaces_; 602 // Required only when mark-stack is accessed in shared mode, which happens 603 // when collecting thread-stack roots using checkpoint. Otherwise, we use it 604 // to synchronize on updated_roots_ in debug-builds. 605 Mutex lock_; 606 accounting::ObjectStack* mark_stack_; 607 // Special bitmap wherein all the bits corresponding to an object are set. 608 // TODO: make LiveWordsBitmap encapsulated in this class rather than a 609 // pointer. We tend to access its members in performance-sensitive 610 // code-path. Also, use a single MemMap for all the GC's data structures, 611 // which we will clear in the end. This would help in limiting the number of 612 // VMAs that get created in the kernel. 613 std::unique_ptr<LiveWordsBitmap<kAlignment>> live_words_bitmap_; 614 // Track GC-roots updated so far in a GC-cycle. This is to confirm that no 615 // GC-root is updated twice. 616 // TODO: Must be replaced with an efficient mechanism eventually. Or ensure 617 // that double updation doesn't happen in the first place. 618 std::unique_ptr<std::unordered_set<void*>> updated_roots_ GUARDED_BY(lock_); 619 MemMap from_space_map_; 620 // Any array of live-bytes in logical chunks of kOffsetChunkSize size 621 // in the 'to-be-compacted' space. 622 MemMap info_map_; 623 // Set of page-sized buffers used for compaction. The first page is used by 624 // the GC thread. Subdequent pages are used by mutator threads in case of 625 // SIGBUS feature, and by uffd-worker threads otherwise. In the latter case 626 // the first page is also used for termination of concurrent compaction by 627 // making worker threads terminate the userfaultfd read loop. 628 MemMap compaction_buffers_map_; 629 630 class LessByArenaAddr { 631 public: operator()632 bool operator()(const TrackedArena* a, const TrackedArena* b) const { 633 return std::less<uint8_t*>{}(a->Begin(), b->Begin()); 634 } 635 }; 636 637 // Map of arenas allocated in LinearAlloc arena-pool and last non-zero page, 638 // captured during compaction pause for concurrent updates. 639 std::map<const TrackedArena*, uint8_t*, LessByArenaAddr> linear_alloc_arenas_; 640 // Set of PageStatus arrays, one per arena-pool space. It's extremely rare to 641 // have more than one, but this is to be ready for the worst case. 642 class LinearAllocSpaceData { 643 public: LinearAllocSpaceData(MemMap && shadow,MemMap && page_status_map,uint8_t * begin,uint8_t * end)644 LinearAllocSpaceData(MemMap&& shadow, MemMap&& page_status_map, uint8_t* begin, uint8_t* end) 645 : shadow_(std::move(shadow)), 646 page_status_map_(std::move(page_status_map)), 647 begin_(begin), 648 end_(end) {} 649 650 MemMap shadow_; 651 MemMap page_status_map_; 652 uint8_t* begin_; 653 uint8_t* end_; 654 }; 655 std::vector<LinearAllocSpaceData> linear_alloc_spaces_data_; 656 657 class LessByObjReference { 658 public: operator()659 bool operator()(const ObjReference& a, const ObjReference& b) const { 660 return std::less<mirror::Object*>{}(a.AsMirrorPtr(), b.AsMirrorPtr()); 661 } 662 }; 663 using ClassAfterObjectMap = std::map<ObjReference, ObjReference, LessByObjReference>; 664 // map of <K, V> such that the class K (in moving space) is after its 665 // objects, and its object V is the lowest object (in moving space). 666 ClassAfterObjectMap class_after_obj_map_; 667 // Since the compaction is done in reverse, we use a reverse iterator. It is maintained 668 // either at the pair whose class is lower than the first page to be freed, or at the 669 // pair whose object is not yet compacted. 670 ClassAfterObjectMap::const_reverse_iterator class_after_obj_iter_; 671 // Used by FreeFromSpacePages() for maintaining markers in the moving space for 672 // how far the pages have been reclaimed (madvised) and checked. 673 // 674 // Pages from this index to the end of to-space have been checked (via page_status) 675 // and their corresponding from-space pages are reclaimable. 676 size_t last_checked_reclaim_page_idx_; 677 // All from-space pages in [last_reclaimed_page_, from_space->End()) are 678 // reclaimed (madvised). Pages in [from-space page corresponding to 679 // last_checked_reclaim_page_idx_, last_reclaimed_page_) are not reclaimed as 680 // they may contain classes required for class hierarchy traversal for 681 // visiting references during compaction. 682 uint8_t* last_reclaimed_page_; 683 // All the pages in [last_reclaimable_page_, last_reclaimed_page_) in 684 // from-space are available to store compacted contents for batching until the 685 // next time madvise is called. 686 uint8_t* last_reclaimable_page_; 687 // [cur_reclaimable_page_, last_reclaimed_page_) have been used to store 688 // compacted contents for batching. 689 uint8_t* cur_reclaimable_page_; 690 691 space::ContinuousSpace* non_moving_space_; 692 space::BumpPointerSpace* const bump_pointer_space_; 693 // The main space bitmap 694 accounting::ContinuousSpaceBitmap* const moving_space_bitmap_; 695 accounting::ContinuousSpaceBitmap* non_moving_space_bitmap_; 696 Thread* thread_running_gc_; 697 // Array of moving-space's pages' compaction status, which is stored in the 698 // least-significant byte. kProcessed entries also contain the from-space 699 // offset of the page which contains the compacted contents of the ith 700 // to-space page. 701 Atomic<uint32_t>* moving_pages_status_; 702 size_t vector_length_; 703 size_t live_stack_freeze_size_; 704 705 uint64_t bytes_scanned_; 706 707 // For every page in the to-space (post-compact heap) we need to know the 708 // first object from which we must compact and/or update references. This is 709 // for both non-moving and moving space. Additionally, for the moving-space, 710 // we also need the offset within the object from where we need to start 711 // copying. 712 // chunk_info_vec_ holds live bytes for chunks during marking phase. After 713 // marking we perform an exclusive scan to compute offset for every chunk. 714 uint32_t* chunk_info_vec_; 715 // For pages before black allocations, pre_compact_offset_moving_space_[i] 716 // holds offset within the space from where the objects need to be copied in 717 // the ith post-compact page. 718 // Otherwise, black_alloc_pages_first_chunk_size_[i] holds the size of first 719 // non-empty chunk in the ith black-allocations page. 720 union { 721 uint32_t* pre_compact_offset_moving_space_; 722 uint32_t* black_alloc_pages_first_chunk_size_; 723 }; 724 // first_objs_moving_space_[i] is the pre-compact address of the object which 725 // would overlap with the starting boundary of the ith post-compact page. 726 ObjReference* first_objs_moving_space_; 727 // First object for every page. It could be greater than the page's start 728 // address, or null if the page is empty. 729 ObjReference* first_objs_non_moving_space_; 730 size_t non_moving_first_objs_count_; 731 // Length of first_objs_moving_space_ and pre_compact_offset_moving_space_ 732 // arrays. Also the number of pages which are to be compacted. 733 size_t moving_first_objs_count_; 734 // Number of pages containing black-allocated objects, indicating number of 735 // pages to be slid. 736 size_t black_page_count_; 737 738 uint8_t* from_space_begin_; 739 // Cached values of moving-space range to optimize checking if reference 740 // belongs to moving-space or not. May get updated if and when heap is 741 // clamped. 742 uint8_t* const moving_space_begin_; 743 uint8_t* moving_space_end_; 744 // Set to moving_space_begin_ if compacting the entire moving space. 745 // Otherwise, set to a page-aligned address such that [moving_space_begin_, 746 // black_dense_end_) is considered to be densely populated with reachable 747 // objects and hence is not compacted. 748 uint8_t* black_dense_end_; 749 // moving-space's end pointer at the marking pause. All allocations beyond 750 // this will be considered black in the current GC cycle. Aligned up to page 751 // size. 752 uint8_t* black_allocations_begin_; 753 // End of compacted space. Use for computing post-compact addr of black 754 // allocated objects. Aligned up to page size. 755 uint8_t* post_compact_end_; 756 // Cache (black_allocations_begin_ - post_compact_end_) for post-compact 757 // address computations. 758 ptrdiff_t black_objs_slide_diff_; 759 // Cache (from_space_begin_ - bump_pointer_space_->Begin()) so that we can 760 // compute from-space address of a given pre-comapct addr efficiently. 761 ptrdiff_t from_space_slide_diff_; 762 763 // TODO: Remove once an efficient mechanism to deal with double root updation 764 // is incorporated. 765 void* stack_high_addr_; 766 void* stack_low_addr_; 767 768 uint8_t* conc_compaction_termination_page_; 769 770 PointerSize pointer_size_; 771 // Number of objects freed during this GC in moving space. It is decremented 772 // every time an object is discovered. And total-object count is added to it 773 // in MarkingPause(). It reaches the correct count only once the marking phase 774 // is completed. 775 int32_t freed_objects_; 776 // Userfault file descriptor, accessed only by the GC itself. 777 // kFallbackMode value indicates that we are in the fallback mode. 778 int uffd_; 779 // Counters to synchronize mutator threads and gc-thread at the end of 780 // compaction. Counter 0 represents the number of mutators still working on 781 // moving space pages which started before gc-thread finished compacting pages, 782 // whereas the counter 1 represents those which started afterwards but 783 // before unregistering the space from uffd. Once counter 1 reaches 0, the 784 // gc-thread madvises spaces and data structures like page-status array. 785 // Both the counters are set to 0 before compaction begins. They are or'ed 786 // with kSigbusCounterCompactionDoneMask one-by-one by gc-thread after 787 // compaction to communicate the status to future mutators. 788 std::atomic<SigbusCounterType> sigbus_in_progress_count_[2]; 789 // When using SIGBUS feature, this counter is used by mutators to claim a page 790 // out of compaction buffers to be used for the entire compaction cycle. 791 std::atomic<uint16_t> compaction_buffer_counter_; 792 // True while compacting. 793 bool compacting_; 794 // Set to true in MarkingPause() to indicate when allocation_stack_ should be 795 // checked in IsMarked() for black allocations. 796 bool marking_done_; 797 // Flag indicating whether one-time uffd initialization has been done. It will 798 // be false on the first GC for non-zygote processes, and always for zygote. 799 // Its purpose is to minimize the userfaultfd overhead to the minimal in 800 // Heap::PostForkChildAction() as it's invoked in app startup path. With 801 // this, we register the compaction-termination page on the first GC. 802 bool uffd_initialized_; 803 // Clamping statue of `info_map_`. Initialized with 'NotDone'. Once heap is 804 // clamped but info_map_ is delayed, we set it to 'Pending'. Once 'info_map_' 805 // is also clamped, then we set it to 'Finished'. 806 ClampInfoStatus clamp_info_map_status_; 807 808 class FlipCallback; 809 class ThreadFlipVisitor; 810 class VerifyRootMarkedVisitor; 811 class ScanObjectVisitor; 812 class CheckpointMarkThreadRoots; 813 template <size_t kBufferSize> 814 class ThreadRootsVisitor; 815 class RefFieldsVisitor; 816 template <bool kCheckBegin, bool kCheckEnd> class RefsUpdateVisitor; 817 class ArenaPoolPageUpdater; 818 class ClassLoaderRootsUpdater; 819 class LinearAllocPageUpdater; 820 class ImmuneSpaceUpdateObjVisitor; 821 822 DISALLOW_IMPLICIT_CONSTRUCTORS(MarkCompact); 823 }; 824 825 std::ostream& operator<<(std::ostream& os, MarkCompact::PageState value); 826 std::ostream& operator<<(std::ostream& os, MarkCompact::ClampInfoStatus value); 827 828 } // namespace collector 829 } // namespace gc 830 } // namespace art 831 832 #endif // ART_RUNTIME_GC_COLLECTOR_MARK_COMPACT_H_ 833