1 /* 2 * Copyright (C) 2014 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_SPACE_REGION_SPACE_H_ 18 #define ART_RUNTIME_GC_SPACE_REGION_SPACE_H_ 19 20 #include "base/macros.h" 21 #include "base/mutex.h" 22 #include "space.h" 23 #include "thread.h" 24 25 #include <functional> 26 #include <map> 27 28 namespace art { 29 namespace gc { 30 31 namespace accounting { 32 class ReadBarrierTable; 33 } // namespace accounting 34 35 namespace space { 36 37 // Cyclic region allocation strategy. If `true`, region allocation 38 // will not try to allocate a new region from the beginning of the 39 // region space, but from the last allocated region. This allocation 40 // strategy reduces region reuse and should help catch some GC bugs 41 // earlier. However, cyclic region allocation can also create memory 42 // fragmentation at the region level (see b/33795328); therefore, we 43 // only enable it in debug mode. 44 static constexpr bool kCyclicRegionAllocation = kIsDebugBuild; 45 46 // A space that consists of equal-sized regions. 47 class RegionSpace final : public ContinuousMemMapAllocSpace { 48 public: 49 typedef void(*WalkCallback)(void *start, void *end, size_t num_bytes, void* callback_arg); 50 51 enum EvacMode { 52 kEvacModeNewlyAllocated, 53 kEvacModeLivePercentNewlyAllocated, 54 kEvacModeForceAll, 55 }; 56 GetType()57 SpaceType GetType() const override { 58 return kSpaceTypeRegionSpace; 59 } 60 61 // Create a region space mem map with the requested sizes. The requested base address is not 62 // guaranteed to be granted, if it is required, the caller should call Begin on the returned 63 // space to confirm the request was granted. 64 static MemMap CreateMemMap(const std::string& name, size_t capacity, uint8_t* requested_begin); 65 static RegionSpace* Create(const std::string& name, MemMap&& mem_map, bool use_generational_cc); 66 67 // Allocate `num_bytes`, returns null if the space is full. 68 mirror::Object* Alloc(Thread* self, 69 size_t num_bytes, 70 /* out */ size_t* bytes_allocated, 71 /* out */ size_t* usable_size, 72 /* out */ size_t* bytes_tl_bulk_allocated) 73 override REQUIRES(!region_lock_); 74 // Thread-unsafe allocation for when mutators are suspended, used by the semispace collector. 75 mirror::Object* AllocThreadUnsafe(Thread* self, 76 size_t num_bytes, 77 /* out */ size_t* bytes_allocated, 78 /* out */ size_t* usable_size, 79 /* out */ size_t* bytes_tl_bulk_allocated) 80 override REQUIRES(Locks::mutator_lock_) REQUIRES(!region_lock_); 81 // The main allocation routine. 82 template<bool kForEvac> 83 ALWAYS_INLINE mirror::Object* AllocNonvirtual(size_t num_bytes, 84 /* out */ size_t* bytes_allocated, 85 /* out */ size_t* usable_size, 86 /* out */ size_t* bytes_tl_bulk_allocated) 87 REQUIRES(!region_lock_); 88 // Allocate/free large objects (objects that are larger than the region size). 89 template<bool kForEvac> 90 mirror::Object* AllocLarge(size_t num_bytes, 91 /* out */ size_t* bytes_allocated, 92 /* out */ size_t* usable_size, 93 /* out */ size_t* bytes_tl_bulk_allocated) REQUIRES(!region_lock_); 94 template<bool kForEvac> 95 void FreeLarge(mirror::Object* large_obj, size_t bytes_allocated) REQUIRES(!region_lock_); 96 97 // Return the storage space required by obj. AllocationSize(mirror::Object * obj,size_t * usable_size)98 size_t AllocationSize(mirror::Object* obj, size_t* usable_size) override 99 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!region_lock_) { 100 return AllocationSizeNonvirtual(obj, usable_size); 101 } 102 size_t AllocationSizeNonvirtual(mirror::Object* obj, size_t* usable_size) 103 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!region_lock_); 104 Free(Thread *,mirror::Object *)105 size_t Free(Thread*, mirror::Object*) override { 106 UNIMPLEMENTED(FATAL); 107 return 0; 108 } FreeList(Thread *,size_t,mirror::Object **)109 size_t FreeList(Thread*, size_t, mirror::Object**) override { 110 UNIMPLEMENTED(FATAL); 111 return 0; 112 } GetLiveBitmap()113 accounting::ContinuousSpaceBitmap* GetLiveBitmap() override { 114 return &mark_bitmap_; 115 } GetMarkBitmap()116 accounting::ContinuousSpaceBitmap* GetMarkBitmap() override { 117 return &mark_bitmap_; 118 } 119 120 void Clear() override REQUIRES(!region_lock_); 121 122 // Remove read and write memory protection from the whole region space, 123 // i.e. make memory pages backing the region area not readable and not 124 // writable. 125 void Protect(); 126 127 // Remove memory protection from the whole region space, i.e. make memory 128 // pages backing the region area readable and writable. This method is useful 129 // to avoid page protection faults when dumping information about an invalid 130 // reference. 131 void Unprotect(); 132 133 // Change the non growth limit capacity to new capacity by shrinking or expanding the map. 134 // Currently, only shrinking is supported. 135 // Unlike implementations of this function in other spaces, we need to pass 136 // new capacity as argument here as region space doesn't have any notion of 137 // growth limit. 138 void ClampGrowthLimit(size_t new_capacity) REQUIRES(!region_lock_); 139 140 void Dump(std::ostream& os) const override; 141 void DumpRegions(std::ostream& os) REQUIRES(!region_lock_); 142 // Dump region containing object `obj`. Precondition: `obj` is in the region space. 143 void DumpRegionForObject(std::ostream& os, mirror::Object* obj) REQUIRES(!region_lock_); 144 void DumpNonFreeRegions(std::ostream& os) REQUIRES(!region_lock_); 145 146 size_t RevokeThreadLocalBuffers(Thread* thread) override REQUIRES(!region_lock_); 147 size_t RevokeThreadLocalBuffers(Thread* thread, const bool reuse) REQUIRES(!region_lock_); 148 size_t RevokeAllThreadLocalBuffers() override 149 REQUIRES(!Locks::runtime_shutdown_lock_, !Locks::thread_list_lock_, !region_lock_); 150 void AssertThreadLocalBuffersAreRevoked(Thread* thread) REQUIRES(!region_lock_); 151 void AssertAllThreadLocalBuffersAreRevoked() 152 REQUIRES(!Locks::runtime_shutdown_lock_, !Locks::thread_list_lock_, !region_lock_); 153 154 enum class RegionType : uint8_t { 155 kRegionTypeAll, // All types. 156 kRegionTypeFromSpace, // From-space. To be evacuated. 157 kRegionTypeUnevacFromSpace, // Unevacuated from-space. Not to be evacuated. 158 kRegionTypeToSpace, // To-space. 159 kRegionTypeNone, // None. 160 }; 161 162 enum class RegionState : uint8_t { 163 kRegionStateFree, // Free region. 164 kRegionStateAllocated, // Allocated region. 165 kRegionStateLarge, // Large allocated (allocation larger than the region size). 166 kRegionStateLargeTail, // Large tail (non-first regions of a large allocation). 167 }; 168 169 template<RegionType kRegionType> uint64_t GetBytesAllocatedInternal() REQUIRES(!region_lock_); 170 template<RegionType kRegionType> uint64_t GetObjectsAllocatedInternal() REQUIRES(!region_lock_); GetBytesAllocated()171 uint64_t GetBytesAllocated() override REQUIRES(!region_lock_) { 172 return GetBytesAllocatedInternal<RegionType::kRegionTypeAll>(); 173 } GetObjectsAllocated()174 uint64_t GetObjectsAllocated() override REQUIRES(!region_lock_) { 175 return GetObjectsAllocatedInternal<RegionType::kRegionTypeAll>(); 176 } GetBytesAllocatedInFromSpace()177 uint64_t GetBytesAllocatedInFromSpace() REQUIRES(!region_lock_) { 178 return GetBytesAllocatedInternal<RegionType::kRegionTypeFromSpace>(); 179 } GetObjectsAllocatedInFromSpace()180 uint64_t GetObjectsAllocatedInFromSpace() REQUIRES(!region_lock_) { 181 return GetObjectsAllocatedInternal<RegionType::kRegionTypeFromSpace>(); 182 } GetBytesAllocatedInUnevacFromSpace()183 uint64_t GetBytesAllocatedInUnevacFromSpace() REQUIRES(!region_lock_) { 184 return GetBytesAllocatedInternal<RegionType::kRegionTypeUnevacFromSpace>(); 185 } GetObjectsAllocatedInUnevacFromSpace()186 uint64_t GetObjectsAllocatedInUnevacFromSpace() REQUIRES(!region_lock_) { 187 return GetObjectsAllocatedInternal<RegionType::kRegionTypeUnevacFromSpace>(); 188 } GetMaxPeakNumNonFreeRegions()189 size_t GetMaxPeakNumNonFreeRegions() const { 190 return max_peak_num_non_free_regions_; 191 } GetNumRegions()192 size_t GetNumRegions() const { 193 return num_regions_; 194 } GetNumNonFreeRegions()195 size_t GetNumNonFreeRegions() const NO_THREAD_SAFETY_ANALYSIS { 196 return num_non_free_regions_; 197 } 198 CanMoveObjects()199 bool CanMoveObjects() const override { 200 return true; 201 } 202 Contains(const mirror::Object * obj)203 bool Contains(const mirror::Object* obj) const override { 204 const uint8_t* byte_obj = reinterpret_cast<const uint8_t*>(obj); 205 return byte_obj >= Begin() && byte_obj < Limit(); 206 } 207 AsRegionSpace()208 RegionSpace* AsRegionSpace() override { 209 return this; 210 } 211 212 // Go through all of the blocks and visit the continuous objects. 213 template <typename Visitor> 214 ALWAYS_INLINE void Walk(Visitor&& visitor) REQUIRES(Locks::mutator_lock_); 215 template <typename Visitor> 216 ALWAYS_INLINE void WalkToSpace(Visitor&& visitor) REQUIRES(Locks::mutator_lock_); 217 218 // Scans regions and calls visitor for objects in unevac-space corresponding 219 // to the bits set in 'bitmap'. 220 // Cannot acquire region_lock_ as visitor may need to acquire it for allocation. 221 // Should not be called concurrently with functions (like SetFromSpace()) which 222 // change regions' type. 223 template <typename Visitor> 224 ALWAYS_INLINE void ScanUnevacFromSpace(accounting::ContinuousSpaceBitmap* bitmap, 225 Visitor&& visitor) NO_THREAD_SAFETY_ANALYSIS; 226 GetSweepCallback()227 accounting::ContinuousSpaceBitmap::SweepCallback* GetSweepCallback() override { 228 return nullptr; 229 } 230 bool LogFragmentationAllocFailure(std::ostream& os, size_t failed_alloc_bytes) override 231 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!region_lock_); 232 233 // Object alignment within the space. 234 static constexpr size_t kAlignment = kObjectAlignment; 235 // The region size. 236 static constexpr size_t kRegionSize = 256 * KB; 237 IsInFromSpace(mirror::Object * ref)238 bool IsInFromSpace(mirror::Object* ref) { 239 if (HasAddress(ref)) { 240 Region* r = RefToRegionUnlocked(ref); 241 return r->IsInFromSpace(); 242 } 243 return false; 244 } 245 IsRegionNewlyAllocated(size_t idx)246 bool IsRegionNewlyAllocated(size_t idx) const NO_THREAD_SAFETY_ANALYSIS { 247 DCHECK_LT(idx, num_regions_); 248 return regions_[idx].IsNewlyAllocated(); 249 } 250 IsInNewlyAllocatedRegion(mirror::Object * ref)251 bool IsInNewlyAllocatedRegion(mirror::Object* ref) { 252 if (HasAddress(ref)) { 253 Region* r = RefToRegionUnlocked(ref); 254 return r->IsNewlyAllocated(); 255 } 256 return false; 257 } 258 IsInUnevacFromSpace(mirror::Object * ref)259 bool IsInUnevacFromSpace(mirror::Object* ref) { 260 if (HasAddress(ref)) { 261 Region* r = RefToRegionUnlocked(ref); 262 return r->IsInUnevacFromSpace(); 263 } 264 return false; 265 } 266 IsLargeObject(mirror::Object * ref)267 bool IsLargeObject(mirror::Object* ref) { 268 if (HasAddress(ref)) { 269 Region* r = RefToRegionUnlocked(ref); 270 return r->IsLarge(); 271 } 272 return false; 273 } 274 IsInToSpace(mirror::Object * ref)275 bool IsInToSpace(mirror::Object* ref) { 276 if (HasAddress(ref)) { 277 Region* r = RefToRegionUnlocked(ref); 278 return r->IsInToSpace(); 279 } 280 return false; 281 } 282 283 // If `ref` is in the region space, return the type of its region; 284 // otherwise, return `RegionType::kRegionTypeNone`. GetRegionType(mirror::Object * ref)285 RegionType GetRegionType(mirror::Object* ref) { 286 if (HasAddress(ref)) { 287 return GetRegionTypeUnsafe(ref); 288 } 289 return RegionType::kRegionTypeNone; 290 } 291 292 // Unsafe version of RegionSpace::GetRegionType. 293 // Precondition: `ref` is in the region space. GetRegionTypeUnsafe(mirror::Object * ref)294 RegionType GetRegionTypeUnsafe(mirror::Object* ref) { 295 DCHECK(HasAddress(ref)) << ref; 296 Region* r = RefToRegionUnlocked(ref); 297 return r->Type(); 298 } 299 300 // Zero live bytes for a large object, used by young gen CC for marking newly allocated large 301 // objects. 302 void ZeroLiveBytesForLargeObject(mirror::Object* obj) REQUIRES_SHARED(Locks::mutator_lock_); 303 304 // Determine which regions to evacuate and tag them as 305 // from-space. Tag the rest as unevacuated from-space. 306 void SetFromSpace(accounting::ReadBarrierTable* rb_table, 307 EvacMode evac_mode, 308 bool clear_live_bytes) 309 REQUIRES(!region_lock_); 310 311 size_t FromSpaceSize() REQUIRES(!region_lock_); 312 size_t UnevacFromSpaceSize() REQUIRES(!region_lock_); 313 size_t ToSpaceSize() REQUIRES(!region_lock_); 314 void ClearFromSpace(/* out */ uint64_t* cleared_bytes, 315 /* out */ uint64_t* cleared_objects, 316 const bool clear_bitmap) 317 REQUIRES(!region_lock_); 318 AddLiveBytes(mirror::Object * ref,size_t alloc_size)319 void AddLiveBytes(mirror::Object* ref, size_t alloc_size) { 320 Region* reg = RefToRegionUnlocked(ref); 321 reg->AddLiveBytes(alloc_size); 322 } 323 AssertAllRegionLiveBytesZeroOrCleared()324 void AssertAllRegionLiveBytesZeroOrCleared() REQUIRES(!region_lock_) { 325 if (kIsDebugBuild) { 326 MutexLock mu(Thread::Current(), region_lock_); 327 for (size_t i = 0; i < num_regions_; ++i) { 328 Region* r = ®ions_[i]; 329 size_t live_bytes = r->LiveBytes(); 330 CHECK(live_bytes == 0U || live_bytes == static_cast<size_t>(-1)) << live_bytes; 331 } 332 } 333 } 334 SetAllRegionLiveBytesZero()335 void SetAllRegionLiveBytesZero() REQUIRES(!region_lock_) { 336 MutexLock mu(Thread::Current(), region_lock_); 337 const size_t iter_limit = kUseTableLookupReadBarrier 338 ? num_regions_ 339 : std::min(num_regions_, non_free_region_index_limit_); 340 for (size_t i = 0; i < iter_limit; ++i) { 341 Region* r = ®ions_[i]; 342 // Newly allocated regions don't need up-to-date live_bytes_ for deciding 343 // whether to be evacuated or not. See Region::ShouldBeEvacuated(). 344 if (!r->IsFree() && !r->IsNewlyAllocated()) { 345 r->ZeroLiveBytes(); 346 } 347 } 348 } 349 RegionIdxForRefUnchecked(mirror::Object * ref)350 size_t RegionIdxForRefUnchecked(mirror::Object* ref) const NO_THREAD_SAFETY_ANALYSIS { 351 DCHECK(HasAddress(ref)); 352 uintptr_t offset = reinterpret_cast<uintptr_t>(ref) - reinterpret_cast<uintptr_t>(Begin()); 353 size_t reg_idx = offset / kRegionSize; 354 DCHECK_LT(reg_idx, num_regions_); 355 Region* reg = ®ions_[reg_idx]; 356 DCHECK_EQ(reg->Idx(), reg_idx); 357 DCHECK(reg->Contains(ref)); 358 return reg_idx; 359 } 360 // Return -1 as region index for references outside this region space. RegionIdxForRef(mirror::Object * ref)361 size_t RegionIdxForRef(mirror::Object* ref) const NO_THREAD_SAFETY_ANALYSIS { 362 if (HasAddress(ref)) { 363 return RegionIdxForRefUnchecked(ref); 364 } else { 365 return static_cast<size_t>(-1); 366 } 367 } 368 369 // Increment object allocation count for region containing ref. 370 void RecordAlloc(mirror::Object* ref) REQUIRES(!region_lock_); 371 372 bool AllocNewTlab(Thread* self, const size_t tlab_size, size_t* bytes_tl_bulk_allocated) 373 REQUIRES(!region_lock_); 374 Time()375 uint32_t Time() { 376 return time_; 377 } 378 EvacBytes()379 size_t EvacBytes() const NO_THREAD_SAFETY_ANALYSIS { 380 return num_evac_regions_ * kRegionSize; 381 } 382 GetMadviseTime()383 uint64_t GetMadviseTime() const { 384 return madvise_time_; 385 } 386 387 private: 388 RegionSpace(const std::string& name, MemMap&& mem_map, bool use_generational_cc); 389 390 class Region { 391 public: Region()392 Region() 393 : idx_(static_cast<size_t>(-1)), 394 live_bytes_(static_cast<size_t>(-1)), 395 begin_(nullptr), 396 thread_(nullptr), 397 top_(nullptr), 398 end_(nullptr), 399 objects_allocated_(0), 400 alloc_time_(0), 401 is_newly_allocated_(false), 402 is_a_tlab_(false), 403 state_(RegionState::kRegionStateAllocated), 404 type_(RegionType::kRegionTypeToSpace) {} 405 Init(size_t idx,uint8_t * begin,uint8_t * end)406 void Init(size_t idx, uint8_t* begin, uint8_t* end) { 407 idx_ = idx; 408 begin_ = begin; 409 top_.store(begin, std::memory_order_relaxed); 410 end_ = end; 411 state_ = RegionState::kRegionStateFree; 412 type_ = RegionType::kRegionTypeNone; 413 objects_allocated_.store(0, std::memory_order_relaxed); 414 alloc_time_ = 0; 415 live_bytes_ = static_cast<size_t>(-1); 416 is_newly_allocated_ = false; 417 is_a_tlab_ = false; 418 thread_ = nullptr; 419 DCHECK_LT(begin, end); 420 DCHECK_EQ(static_cast<size_t>(end - begin), kRegionSize); 421 } 422 State()423 RegionState State() const { 424 return state_; 425 } 426 Type()427 RegionType Type() const { 428 return type_; 429 } 430 431 void Clear(bool zero_and_release_pages); 432 433 ALWAYS_INLINE mirror::Object* Alloc(size_t num_bytes, 434 /* out */ size_t* bytes_allocated, 435 /* out */ size_t* usable_size, 436 /* out */ size_t* bytes_tl_bulk_allocated); 437 IsFree()438 bool IsFree() const { 439 bool is_free = (state_ == RegionState::kRegionStateFree); 440 if (is_free) { 441 DCHECK(IsInNoSpace()); 442 DCHECK_EQ(begin_, Top()); 443 DCHECK_EQ(objects_allocated_.load(std::memory_order_relaxed), 0U); 444 } 445 return is_free; 446 } 447 448 // Given a free region, declare it non-free (allocated). 449 void Unfree(RegionSpace* region_space, uint32_t alloc_time) 450 REQUIRES(region_space->region_lock_); 451 452 // Given a free region, declare it non-free (allocated) and large. 453 void UnfreeLarge(RegionSpace* region_space, uint32_t alloc_time) 454 REQUIRES(region_space->region_lock_); 455 456 // Given a free region, declare it non-free (allocated) and large tail. 457 void UnfreeLargeTail(RegionSpace* region_space, uint32_t alloc_time) 458 REQUIRES(region_space->region_lock_); 459 460 void MarkAsAllocated(RegionSpace* region_space, uint32_t alloc_time) 461 REQUIRES(region_space->region_lock_); 462 SetNewlyAllocated()463 void SetNewlyAllocated() { 464 is_newly_allocated_ = true; 465 } 466 467 // Non-large, non-large-tail allocated. IsAllocated()468 bool IsAllocated() const { 469 return state_ == RegionState::kRegionStateAllocated; 470 } 471 472 // Large allocated. IsLarge()473 bool IsLarge() const { 474 bool is_large = (state_ == RegionState::kRegionStateLarge); 475 if (is_large) { 476 DCHECK_LT(begin_ + kRegionSize, Top()); 477 } 478 return is_large; 479 } 480 ZeroLiveBytes()481 void ZeroLiveBytes() { 482 live_bytes_ = 0; 483 } 484 485 // Large-tail allocated. IsLargeTail()486 bool IsLargeTail() const { 487 bool is_large_tail = (state_ == RegionState::kRegionStateLargeTail); 488 if (is_large_tail) { 489 DCHECK_EQ(begin_, Top()); 490 } 491 return is_large_tail; 492 } 493 Idx()494 size_t Idx() const { 495 return idx_; 496 } 497 IsNewlyAllocated()498 bool IsNewlyAllocated() const { 499 return is_newly_allocated_; 500 } 501 IsTlab()502 bool IsTlab() const { 503 return is_a_tlab_; 504 } 505 IsInFromSpace()506 bool IsInFromSpace() const { 507 return type_ == RegionType::kRegionTypeFromSpace; 508 } 509 IsInToSpace()510 bool IsInToSpace() const { 511 return type_ == RegionType::kRegionTypeToSpace; 512 } 513 IsInUnevacFromSpace()514 bool IsInUnevacFromSpace() const { 515 return type_ == RegionType::kRegionTypeUnevacFromSpace; 516 } 517 IsInNoSpace()518 bool IsInNoSpace() const { 519 return type_ == RegionType::kRegionTypeNone; 520 } 521 522 // Set this region as evacuated from-space. At the end of the 523 // collection, RegionSpace::ClearFromSpace will clear and reclaim 524 // the space used by this region, and tag it as unallocated/free. SetAsFromSpace()525 void SetAsFromSpace() { 526 DCHECK(!IsFree() && IsInToSpace()); 527 type_ = RegionType::kRegionTypeFromSpace; 528 if (IsNewlyAllocated()) { 529 // Clear the "newly allocated" status here, as we do not want the 530 // GC to see it when encountering references in the from-space. 531 // 532 // Invariant: There should be no newly-allocated region in the 533 // from-space (when the from-space exists, which is between the calls 534 // to RegionSpace::SetFromSpace and RegionSpace::ClearFromSpace). 535 is_newly_allocated_ = false; 536 } 537 // Set live bytes to an invalid value, as we have made an 538 // evacuation decision (possibly based on the percentage of live 539 // bytes). 540 live_bytes_ = static_cast<size_t>(-1); 541 } 542 543 // Set this region as unevacuated from-space. At the end of the 544 // collection, RegionSpace::ClearFromSpace will preserve the space 545 // used by this region, and tag it as to-space (see 546 // Region::SetUnevacFromSpaceAsToSpace below). 547 void SetAsUnevacFromSpace(bool clear_live_bytes); 548 549 // Set this region as to-space. Used by RegionSpace::ClearFromSpace. 550 // This is only valid if it is currently an unevac from-space region. SetUnevacFromSpaceAsToSpace()551 void SetUnevacFromSpaceAsToSpace() { 552 DCHECK(!IsFree() && IsInUnevacFromSpace()); 553 type_ = RegionType::kRegionTypeToSpace; 554 } 555 556 // Return whether this region should be evacuated. Used by RegionSpace::SetFromSpace. 557 ALWAYS_INLINE bool ShouldBeEvacuated(EvacMode evac_mode); 558 AddLiveBytes(size_t live_bytes)559 void AddLiveBytes(size_t live_bytes) { 560 DCHECK(GetUseGenerationalCC() || IsInUnevacFromSpace()); 561 DCHECK(!IsLargeTail()); 562 DCHECK_NE(live_bytes_, static_cast<size_t>(-1)); 563 // For large allocations, we always consider all bytes in the regions live. 564 live_bytes_ += IsLarge() ? Top() - begin_ : live_bytes; 565 DCHECK_LE(live_bytes_, BytesAllocated()); 566 } 567 AllAllocatedBytesAreLive()568 bool AllAllocatedBytesAreLive() const { 569 return LiveBytes() == static_cast<size_t>(Top() - Begin()); 570 } 571 LiveBytes()572 size_t LiveBytes() const { 573 return live_bytes_; 574 } 575 576 // Returns the number of allocated bytes. "Bulk allocated" bytes in active TLABs are excluded. 577 size_t BytesAllocated() const; 578 579 size_t ObjectsAllocated() const; 580 Begin()581 uint8_t* Begin() const { 582 return begin_; 583 } 584 Top()585 ALWAYS_INLINE uint8_t* Top() const { 586 return top_.load(std::memory_order_relaxed); 587 } 588 SetTop(uint8_t * new_top)589 void SetTop(uint8_t* new_top) { 590 top_.store(new_top, std::memory_order_relaxed); 591 } 592 End()593 uint8_t* End() const { 594 return end_; 595 } 596 Contains(mirror::Object * ref)597 bool Contains(mirror::Object* ref) const { 598 return begin_ <= reinterpret_cast<uint8_t*>(ref) && reinterpret_cast<uint8_t*>(ref) < end_; 599 } 600 601 void Dump(std::ostream& os) const; 602 RecordThreadLocalAllocations(size_t num_objects,size_t num_bytes)603 void RecordThreadLocalAllocations(size_t num_objects, size_t num_bytes) { 604 DCHECK(IsAllocated()); 605 DCHECK_EQ(Top(), end_); 606 objects_allocated_.fetch_add(num_objects, std::memory_order_relaxed); 607 top_.store(begin_ + num_bytes, std::memory_order_relaxed); 608 DCHECK_LE(Top(), end_); 609 } 610 611 uint64_t GetLongestConsecutiveFreeBytes() const; 612 613 private: 614 static bool GetUseGenerationalCC(); 615 616 size_t idx_; // The region's index in the region space. 617 // Number of bytes in live objects, or -1 for newly allocated regions. Used to compute 618 // percent live for region evacuation decisions, and to determine whether an unevacuated 619 // region is completely empty, and thus can be reclaimed. Reset to zero either at the 620 // beginning of MarkingPhase(), or during the flip for a nongenerational GC, where we 621 // don't have a separate mark phase. It is then incremented whenever a mark bit in that 622 // region is set. 623 size_t live_bytes_; // The live bytes. Used to compute the live percent. 624 uint8_t* begin_; // The begin address of the region. 625 Thread* thread_; // The owning thread if it's a tlab. 626 // Note that `top_` can be higher than `end_` in the case of a 627 // large region, where an allocated object spans multiple regions 628 // (large region + one or more large tail regions). 629 Atomic<uint8_t*> top_; // The current position of the allocation. 630 uint8_t* end_; // The end address of the region. 631 // objects_allocated_ is accessed using memory_order_relaxed. Treat as approximate when there 632 // are concurrent updates. 633 Atomic<size_t> objects_allocated_; // The number of objects allocated. 634 uint32_t alloc_time_; // The allocation time of the region. 635 // Note that newly allocated and evacuated regions use -1 as 636 // special value for `live_bytes_`. 637 bool is_newly_allocated_; // True if it's allocated after the last collection. 638 bool is_a_tlab_; // True if it's a tlab. 639 RegionState state_; // The region state (see RegionState). 640 RegionType type_; // The region type (see RegionType). 641 642 friend class RegionSpace; 643 }; 644 645 template<bool kToSpaceOnly, typename Visitor> 646 ALWAYS_INLINE void WalkInternal(Visitor&& visitor) NO_THREAD_SAFETY_ANALYSIS; 647 648 // Visitor will be iterating on objects in increasing address order. 649 template<typename Visitor> 650 ALWAYS_INLINE void WalkNonLargeRegion(Visitor&& visitor, const Region* r) 651 NO_THREAD_SAFETY_ANALYSIS; 652 RefToRegion(mirror::Object * ref)653 Region* RefToRegion(mirror::Object* ref) REQUIRES(!region_lock_) { 654 MutexLock mu(Thread::Current(), region_lock_); 655 return RefToRegionLocked(ref); 656 } 657 658 void TraceHeapSize() REQUIRES(region_lock_); 659 RefToRegionUnlocked(mirror::Object * ref)660 Region* RefToRegionUnlocked(mirror::Object* ref) NO_THREAD_SAFETY_ANALYSIS { 661 // For a performance reason (this is frequently called via 662 // RegionSpace::IsInFromSpace, etc.) we avoid taking a lock here. 663 // Note that since we only change a region from to-space to (evac) 664 // from-space during a pause (in RegionSpace::SetFromSpace) and 665 // from (evac) from-space to free (after GC is done), as long as 666 // `ref` is a valid reference into an allocated region, it's safe 667 // to access the region state without the lock. 668 return RefToRegionLocked(ref); 669 } 670 RefToRegionLocked(mirror::Object * ref)671 Region* RefToRegionLocked(mirror::Object* ref) REQUIRES(region_lock_) { 672 DCHECK(HasAddress(ref)); 673 uintptr_t offset = reinterpret_cast<uintptr_t>(ref) - reinterpret_cast<uintptr_t>(Begin()); 674 size_t reg_idx = offset / kRegionSize; 675 DCHECK_LT(reg_idx, num_regions_); 676 Region* reg = ®ions_[reg_idx]; 677 DCHECK_EQ(reg->Idx(), reg_idx); 678 DCHECK(reg->Contains(ref)); 679 return reg; 680 } 681 682 // Return the object location following `obj` in the region space 683 // (i.e., the object location at `obj + obj->SizeOf()`). 684 // 685 // Note that unless 686 // - the region containing `obj` is fully used; and 687 // - `obj` is not the last object of that region; 688 // the returned location is not guaranteed to be a valid object. 689 static mirror::Object* GetNextObject(mirror::Object* obj) 690 REQUIRES_SHARED(Locks::mutator_lock_); 691 AdjustNonFreeRegionLimit(size_t new_non_free_region_index)692 void AdjustNonFreeRegionLimit(size_t new_non_free_region_index) REQUIRES(region_lock_) { 693 DCHECK_LT(new_non_free_region_index, num_regions_); 694 non_free_region_index_limit_ = std::max(non_free_region_index_limit_, 695 new_non_free_region_index + 1); 696 VerifyNonFreeRegionLimit(); 697 } 698 SetNonFreeRegionLimit(size_t new_non_free_region_index_limit)699 void SetNonFreeRegionLimit(size_t new_non_free_region_index_limit) REQUIRES(region_lock_) { 700 DCHECK_LE(new_non_free_region_index_limit, num_regions_); 701 non_free_region_index_limit_ = new_non_free_region_index_limit; 702 VerifyNonFreeRegionLimit(); 703 } 704 705 // Implementation of this invariant: 706 // for all `i >= non_free_region_index_limit_`, `regions_[i].IsFree()` is true. VerifyNonFreeRegionLimit()707 void VerifyNonFreeRegionLimit() REQUIRES(region_lock_) { 708 if (kIsDebugBuild && non_free_region_index_limit_ < num_regions_) { 709 for (size_t i = non_free_region_index_limit_; i < num_regions_; ++i) { 710 CHECK(regions_[i].IsFree()); 711 } 712 } 713 } 714 715 Region* AllocateRegion(bool for_evac) REQUIRES(region_lock_); 716 void RevokeThreadLocalBuffersLocked(Thread* thread, bool reuse) REQUIRES(region_lock_); 717 718 // Scan region range [`begin`, `end`) in increasing order to try to 719 // allocate a large region having a size of `num_regs_in_large_region` 720 // regions. If there is no space in the region space to allocate this 721 // large region, return null. 722 // 723 // If argument `next_region` is not null, use `*next_region` to 724 // return the index to the region next to the allocated large region 725 // returned by this method. 726 template<bool kForEvac> 727 mirror::Object* AllocLargeInRange(size_t begin, 728 size_t end, 729 size_t num_regs_in_large_region, 730 /* out */ size_t* bytes_allocated, 731 /* out */ size_t* usable_size, 732 /* out */ size_t* bytes_tl_bulk_allocated, 733 /* out */ size_t* next_region = nullptr) REQUIRES(region_lock_); 734 735 // Check that the value of `r->LiveBytes()` matches the number of 736 // (allocated) bytes used by live objects according to the live bits 737 // in the region space bitmap range corresponding to region `r`. 738 void CheckLiveBytesAgainstRegionBitmap(Region* r); 739 740 // Poison memory areas used by dead objects within unevacuated 741 // region `r`. This is meant to detect dangling references to dead 742 // objects earlier in debug mode. 743 void PoisonDeadObjectsInUnevacuatedRegion(Region* r); 744 745 Mutex region_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER; 746 747 // Cached version of Heap::use_generational_cc_. 748 const bool use_generational_cc_; 749 uint32_t time_; // The time as the number of collections since the startup. 750 size_t num_regions_; // The number of regions in this space. 751 uint64_t madvise_time_; // The amount of time spent in madvise for purging pages. 752 // The number of non-free regions in this space. 753 size_t num_non_free_regions_ GUARDED_BY(region_lock_); 754 755 // The number of evac regions allocated during collection. 0 when GC not running. 756 size_t num_evac_regions_ GUARDED_BY(region_lock_); 757 758 // Maintain the maximum of number of non-free regions collected just before 759 // reclaim in each GC cycle. At this moment in cycle, highest number of 760 // regions are in non-free. 761 size_t max_peak_num_non_free_regions_; 762 763 // The pointer to the region array. 764 std::unique_ptr<Region[]> regions_ GUARDED_BY(region_lock_); 765 766 // To hold partially used TLABs which can be reassigned to threads later for 767 // utilizing the un-used portion. 768 std::multimap<size_t, Region*, std::greater<size_t>> partial_tlabs_ GUARDED_BY(region_lock_); 769 // The upper-bound index of the non-free regions. Used to avoid scanning all regions in 770 // RegionSpace::SetFromSpace and RegionSpace::ClearFromSpace. 771 // 772 // Invariant (verified by RegionSpace::VerifyNonFreeRegionLimit): 773 // for all `i >= non_free_region_index_limit_`, `regions_[i].IsFree()` is true. 774 size_t non_free_region_index_limit_ GUARDED_BY(region_lock_); 775 776 Region* current_region_; // The region currently used for allocation. 777 Region* evac_region_; // The region currently used for evacuation. 778 Region full_region_; // The fake/sentinel region that looks full. 779 780 // Index into the region array pointing to the starting region when 781 // trying to allocate a new region. Only used when 782 // `kCyclicRegionAllocation` is true. 783 size_t cyclic_alloc_region_index_ GUARDED_BY(region_lock_); 784 785 // Mark bitmap used by the GC. 786 accounting::ContinuousSpaceBitmap mark_bitmap_; 787 788 DISALLOW_COPY_AND_ASSIGN(RegionSpace); 789 }; 790 791 std::ostream& operator<<(std::ostream& os, RegionSpace::RegionState value); 792 std::ostream& operator<<(std::ostream& os, RegionSpace::RegionType value); 793 794 } // namespace space 795 } // namespace gc 796 } // namespace art 797 798 #endif // ART_RUNTIME_GC_SPACE_REGION_SPACE_H_ 799