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 #include <deque>
17 
18 #include "bump_pointer_space-inl.h"
19 #include "bump_pointer_space.h"
20 #include "base/dumpable.h"
21 #include "base/logging.h"
22 #include "gc/accounting/read_barrier_table.h"
23 #include "mirror/class-inl.h"
24 #include "mirror/object-inl.h"
25 #include "thread_list.h"
26 
27 namespace art {
28 namespace gc {
29 namespace space {
30 
31 // If a region has live objects whose size is less than this percent
32 // value of the region size, evaculate the region.
33 static constexpr uint kEvacuateLivePercentThreshold = 75U;
34 
35 // Whether we protect the unused and cleared regions.
36 static constexpr bool kProtectClearedRegions = kIsDebugBuild;
37 
38 // Wether we poison memory areas occupied by dead objects in unevacuated regions.
39 static constexpr bool kPoisonDeadObjectsInUnevacuatedRegions = true;
40 
41 // Special 32-bit value used to poison memory areas occupied by dead
42 // objects in unevacuated regions. Dereferencing this value is expected
43 // to trigger a memory protection fault, as it is unlikely that it
44 // points to a valid, non-protected memory area.
45 static constexpr uint32_t kPoisonDeadObject = 0xBADDB01D;  // "BADDROID"
46 
47 // Whether we check a region's live bytes count against the region bitmap.
48 static constexpr bool kCheckLiveBytesAgainstRegionBitmap = kIsDebugBuild;
49 
CreateMemMap(const std::string & name,size_t capacity,uint8_t * requested_begin)50 MemMap RegionSpace::CreateMemMap(const std::string& name,
51                                  size_t capacity,
52                                  uint8_t* requested_begin) {
53   CHECK_ALIGNED(capacity, kRegionSize);
54   std::string error_msg;
55   // Ask for the capacity of an additional kRegionSize so that we can align the map by kRegionSize
56   // even if we get unaligned base address. This is necessary for the ReadBarrierTable to work.
57   MemMap mem_map;
58   while (true) {
59     mem_map = MemMap::MapAnonymous(name.c_str(),
60                                    requested_begin,
61                                    capacity + kRegionSize,
62                                    PROT_READ | PROT_WRITE,
63                                    /*low_4gb=*/ true,
64                                    /*reuse=*/ false,
65                                    /*reservation=*/ nullptr,
66                                    &error_msg);
67     if (mem_map.IsValid() || requested_begin == nullptr) {
68       break;
69     }
70     // Retry with no specified request begin.
71     requested_begin = nullptr;
72   }
73   if (!mem_map.IsValid()) {
74     LOG(ERROR) << "Failed to allocate pages for alloc space (" << name << ") of size "
75         << PrettySize(capacity) << " with message " << error_msg;
76     PrintFileToLog("/proc/self/maps", LogSeverity::ERROR);
77     MemMap::DumpMaps(LOG_STREAM(ERROR));
78     return MemMap::Invalid();
79   }
80   CHECK_EQ(mem_map.Size(), capacity + kRegionSize);
81   CHECK_EQ(mem_map.Begin(), mem_map.BaseBegin());
82   CHECK_EQ(mem_map.Size(), mem_map.BaseSize());
83   if (IsAlignedParam(mem_map.Begin(), kRegionSize)) {
84     // Got an aligned map. Since we requested a map that's kRegionSize larger. Shrink by
85     // kRegionSize at the end.
86     mem_map.SetSize(capacity);
87   } else {
88     // Got an unaligned map. Align the both ends.
89     mem_map.AlignBy(kRegionSize);
90   }
91   CHECK_ALIGNED(mem_map.Begin(), kRegionSize);
92   CHECK_ALIGNED(mem_map.End(), kRegionSize);
93   CHECK_EQ(mem_map.Size(), capacity);
94   return mem_map;
95 }
96 
Create(const std::string & name,MemMap && mem_map,bool use_generational_cc)97 RegionSpace* RegionSpace::Create(
98     const std::string& name, MemMap&& mem_map, bool use_generational_cc) {
99   return new RegionSpace(name, std::move(mem_map), use_generational_cc);
100 }
101 
RegionSpace(const std::string & name,MemMap && mem_map,bool use_generational_cc)102 RegionSpace::RegionSpace(const std::string& name, MemMap&& mem_map, bool use_generational_cc)
103     : ContinuousMemMapAllocSpace(name,
104                                  std::move(mem_map),
105                                  mem_map.Begin(),
106                                  mem_map.End(),
107                                  mem_map.End(),
108                                  kGcRetentionPolicyAlwaysCollect),
109       region_lock_("Region lock", kRegionSpaceRegionLock),
110       use_generational_cc_(use_generational_cc),
111       time_(1U),
112       num_regions_(mem_map_.Size() / kRegionSize),
113       madvise_time_(0U),
114       num_non_free_regions_(0U),
115       num_evac_regions_(0U),
116       max_peak_num_non_free_regions_(0U),
117       non_free_region_index_limit_(0U),
118       current_region_(&full_region_),
119       evac_region_(nullptr),
120       cyclic_alloc_region_index_(0U) {
121   CHECK_ALIGNED(mem_map_.Size(), kRegionSize);
122   CHECK_ALIGNED(mem_map_.Begin(), kRegionSize);
123   DCHECK_GT(num_regions_, 0U);
124   regions_.reset(new Region[num_regions_]);
125   uint8_t* region_addr = mem_map_.Begin();
126   for (size_t i = 0; i < num_regions_; ++i, region_addr += kRegionSize) {
127     regions_[i].Init(i, region_addr, region_addr + kRegionSize);
128   }
129   mark_bitmap_ =
130       accounting::ContinuousSpaceBitmap::Create("region space live bitmap", Begin(), Capacity());
131   if (kIsDebugBuild) {
132     CHECK_EQ(regions_[0].Begin(), Begin());
133     for (size_t i = 0; i < num_regions_; ++i) {
134       CHECK(regions_[i].IsFree());
135       CHECK_EQ(static_cast<size_t>(regions_[i].End() - regions_[i].Begin()), kRegionSize);
136       if (i + 1 < num_regions_) {
137         CHECK_EQ(regions_[i].End(), regions_[i + 1].Begin());
138       }
139     }
140     CHECK_EQ(regions_[num_regions_ - 1].End(), Limit());
141   }
142   DCHECK(!full_region_.IsFree());
143   DCHECK(full_region_.IsAllocated());
144   size_t ignored;
145   DCHECK(full_region_.Alloc(kAlignment, &ignored, nullptr, &ignored) == nullptr);
146   // Protect the whole region space from the start.
147   Protect();
148 }
149 
FromSpaceSize()150 size_t RegionSpace::FromSpaceSize() {
151   uint64_t num_regions = 0;
152   MutexLock mu(Thread::Current(), region_lock_);
153   for (size_t i = 0; i < num_regions_; ++i) {
154     Region* r = &regions_[i];
155     if (r->IsInFromSpace()) {
156       ++num_regions;
157     }
158   }
159   return num_regions * kRegionSize;
160 }
161 
UnevacFromSpaceSize()162 size_t RegionSpace::UnevacFromSpaceSize() {
163   uint64_t num_regions = 0;
164   MutexLock mu(Thread::Current(), region_lock_);
165   for (size_t i = 0; i < num_regions_; ++i) {
166     Region* r = &regions_[i];
167     if (r->IsInUnevacFromSpace()) {
168       ++num_regions;
169     }
170   }
171   return num_regions * kRegionSize;
172 }
173 
ToSpaceSize()174 size_t RegionSpace::ToSpaceSize() {
175   uint64_t num_regions = 0;
176   MutexLock mu(Thread::Current(), region_lock_);
177   for (size_t i = 0; i < num_regions_; ++i) {
178     Region* r = &regions_[i];
179     if (r->IsInToSpace()) {
180       ++num_regions;
181     }
182   }
183   return num_regions * kRegionSize;
184 }
185 
SetAsUnevacFromSpace(bool clear_live_bytes)186 void RegionSpace::Region::SetAsUnevacFromSpace(bool clear_live_bytes) {
187   // Live bytes are only preserved (i.e. not cleared) during sticky-bit CC collections.
188   DCHECK(GetUseGenerationalCC() || clear_live_bytes);
189   DCHECK(!IsFree() && IsInToSpace());
190   type_ = RegionType::kRegionTypeUnevacFromSpace;
191   if (IsNewlyAllocated()) {
192     // A newly allocated region set as unevac from-space must be
193     // a large or large tail region.
194     DCHECK(IsLarge() || IsLargeTail()) << static_cast<uint>(state_);
195     // Always clear the live bytes of a newly allocated (large or
196     // large tail) region.
197     clear_live_bytes = true;
198     // Clear the "newly allocated" status here, as we do not want the
199     // GC to see it when encountering (and processing) references in the
200     // from-space.
201     //
202     // Invariant: There should be no newly-allocated region in the
203     // from-space (when the from-space exists, which is between the calls
204     // to RegionSpace::SetFromSpace and RegionSpace::ClearFromSpace).
205     is_newly_allocated_ = false;
206   }
207   if (clear_live_bytes) {
208     // Reset the live bytes, as we have made a non-evacuation
209     // decision (possibly based on the percentage of live bytes).
210     live_bytes_ = 0;
211   }
212 }
213 
GetUseGenerationalCC()214 bool RegionSpace::Region::GetUseGenerationalCC() {
215   // We are retrieving the info from Heap, instead of the cached version in
216   // RegionSpace, because accessing the Heap from a Region object is easier
217   // than accessing the RegionSpace.
218   return art::Runtime::Current()->GetHeap()->GetUseGenerationalCC();
219 }
220 
ShouldBeEvacuated(EvacMode evac_mode)221 inline bool RegionSpace::Region::ShouldBeEvacuated(EvacMode evac_mode) {
222   // Evacuation mode `kEvacModeNewlyAllocated` is only used during sticky-bit CC collections.
223   DCHECK(GetUseGenerationalCC() || (evac_mode != kEvacModeNewlyAllocated));
224   DCHECK((IsAllocated() || IsLarge()) && IsInToSpace());
225   // The region should be evacuated if:
226   // - the evacuation is forced (`evac_mode == kEvacModeForceAll`); or
227   // - the region was allocated after the start of the previous GC (newly allocated region); or
228   // - the live ratio is below threshold (`kEvacuateLivePercentThreshold`).
229   if (UNLIKELY(evac_mode == kEvacModeForceAll)) {
230     return true;
231   }
232   bool result = false;
233   if (is_newly_allocated_) {
234     // Invariant: newly allocated regions have an undefined live bytes count.
235     DCHECK_EQ(live_bytes_, static_cast<size_t>(-1));
236     if (IsAllocated()) {
237       // We always evacuate newly-allocated non-large regions as we
238       // believe they contain many dead objects (a very simple form of
239       // the generational hypothesis, even before the Sticky-Bit CC
240       // approach).
241       //
242       // TODO: Verify that assertion by collecting statistics on the
243       // number/proportion of live objects in newly allocated regions
244       // in RegionSpace::ClearFromSpace.
245       //
246       // Note that a side effect of evacuating a newly-allocated
247       // non-large region is that the "newly allocated" status will
248       // later be removed, as its live objects will be copied to an
249       // evacuation region, which won't be marked as "newly
250       // allocated" (see RegionSpace::AllocateRegion).
251       result = true;
252     } else {
253       DCHECK(IsLarge());
254       // We never want to evacuate a large region (and the associated
255       // tail regions), except if:
256       // - we are forced to do so (see the `kEvacModeForceAll` case
257       //   above); or
258       // - we know that the (sole) object contained in this region is
259       //   dead (see the corresponding logic below, in the
260       //   `kEvacModeLivePercentNewlyAllocated` case).
261       // For a newly allocated region (i.e. allocated since the
262       // previous GC started), we don't have any liveness information
263       // (the live bytes count is -1 -- also note this region has been
264       // a to-space one between the time of its allocation and now),
265       // so we prefer not to evacuate it.
266       result = false;
267     }
268   } else if (evac_mode == kEvacModeLivePercentNewlyAllocated) {
269     bool is_live_percent_valid = (live_bytes_ != static_cast<size_t>(-1));
270     if (is_live_percent_valid) {
271       DCHECK(IsInToSpace());
272       DCHECK(!IsLargeTail());
273       DCHECK_NE(live_bytes_, static_cast<size_t>(-1));
274       DCHECK_LE(live_bytes_, BytesAllocated());
275       const size_t bytes_allocated = RoundUp(BytesAllocated(), kRegionSize);
276       DCHECK_LE(live_bytes_, bytes_allocated);
277       if (IsAllocated()) {
278         // Side node: live_percent == 0 does not necessarily mean
279         // there's no live objects due to rounding (there may be a
280         // few).
281         result = (live_bytes_ * 100U < kEvacuateLivePercentThreshold * bytes_allocated);
282       } else {
283         DCHECK(IsLarge());
284         result = (live_bytes_ == 0U);
285       }
286     } else {
287       result = false;
288     }
289   }
290   return result;
291 }
292 
ZeroLiveBytesForLargeObject(mirror::Object * obj)293 void RegionSpace::ZeroLiveBytesForLargeObject(mirror::Object* obj) {
294   // This method is only used when Generational CC collection is enabled.
295   DCHECK(use_generational_cc_);
296 
297   // This code uses a logic similar to the one used in RegionSpace::FreeLarge
298   // to traverse the regions supporting `obj`.
299   // TODO: Refactor.
300   DCHECK(IsLargeObject(obj));
301   DCHECK_ALIGNED(obj, kRegionSize);
302   size_t obj_size = obj->SizeOf<kDefaultVerifyFlags>();
303   DCHECK_GT(obj_size, space::RegionSpace::kRegionSize);
304   // Size of the memory area allocated for `obj`.
305   size_t obj_alloc_size = RoundUp(obj_size, space::RegionSpace::kRegionSize);
306   uint8_t* begin_addr = reinterpret_cast<uint8_t*>(obj);
307   uint8_t* end_addr = begin_addr + obj_alloc_size;
308   DCHECK_ALIGNED(end_addr, kRegionSize);
309 
310   // Zero the live bytes of the large region and large tail regions containing the object.
311   MutexLock mu(Thread::Current(), region_lock_);
312   for (uint8_t* addr = begin_addr; addr < end_addr; addr += kRegionSize) {
313     Region* region = RefToRegionLocked(reinterpret_cast<mirror::Object*>(addr));
314     if (addr == begin_addr) {
315       DCHECK(region->IsLarge());
316     } else {
317       DCHECK(region->IsLargeTail());
318     }
319     region->ZeroLiveBytes();
320   }
321   if (kIsDebugBuild && end_addr < Limit()) {
322     // If we aren't at the end of the space, check that the next region is not a large tail.
323     Region* following_region = RefToRegionLocked(reinterpret_cast<mirror::Object*>(end_addr));
324     DCHECK(!following_region->IsLargeTail());
325   }
326 }
327 
328 // Determine which regions to evacuate and mark them as
329 // from-space. Mark the rest as unevacuated from-space.
SetFromSpace(accounting::ReadBarrierTable * rb_table,EvacMode evac_mode,bool clear_live_bytes)330 void RegionSpace::SetFromSpace(accounting::ReadBarrierTable* rb_table,
331                                EvacMode evac_mode,
332                                bool clear_live_bytes) {
333   // Live bytes are only preserved (i.e. not cleared) during sticky-bit CC collections.
334   DCHECK(use_generational_cc_ || clear_live_bytes);
335   ++time_;
336   if (kUseTableLookupReadBarrier) {
337     DCHECK(rb_table->IsAllCleared());
338     rb_table->SetAll();
339   }
340   MutexLock mu(Thread::Current(), region_lock_);
341   // We cannot use the partially utilized TLABs across a GC. Therefore, revoke
342   // them during the thread-flip.
343   partial_tlabs_.clear();
344 
345   // Counter for the number of expected large tail regions following a large region.
346   size_t num_expected_large_tails = 0U;
347   // Flag to store whether the previously seen large region has been evacuated.
348   // This is used to apply the same evacuation policy to related large tail regions.
349   bool prev_large_evacuated = false;
350   VerifyNonFreeRegionLimit();
351   const size_t iter_limit = kUseTableLookupReadBarrier
352       ? num_regions_
353       : std::min(num_regions_, non_free_region_index_limit_);
354   for (size_t i = 0; i < iter_limit; ++i) {
355     Region* r = &regions_[i];
356     RegionState state = r->State();
357     RegionType type = r->Type();
358     if (!r->IsFree()) {
359       DCHECK(r->IsInToSpace());
360       if (LIKELY(num_expected_large_tails == 0U)) {
361         DCHECK((state == RegionState::kRegionStateAllocated ||
362                 state == RegionState::kRegionStateLarge) &&
363                type == RegionType::kRegionTypeToSpace);
364         bool should_evacuate = r->ShouldBeEvacuated(evac_mode);
365         bool is_newly_allocated = r->IsNewlyAllocated();
366         if (should_evacuate) {
367           r->SetAsFromSpace();
368           DCHECK(r->IsInFromSpace());
369         } else {
370           r->SetAsUnevacFromSpace(clear_live_bytes);
371           DCHECK(r->IsInUnevacFromSpace());
372         }
373         if (UNLIKELY(state == RegionState::kRegionStateLarge &&
374                      type == RegionType::kRegionTypeToSpace)) {
375           prev_large_evacuated = should_evacuate;
376           // In 2-phase full heap GC, this function is called after marking is
377           // done. So, it is possible that some newly allocated large object is
378           // marked but its live_bytes is still -1. We need to clear the
379           // mark-bit otherwise the live_bytes will not be updated in
380           // ConcurrentCopying::ProcessMarkStackRef() and hence will break the
381           // logic.
382           if (use_generational_cc_ && !should_evacuate && is_newly_allocated) {
383             GetMarkBitmap()->Clear(reinterpret_cast<mirror::Object*>(r->Begin()));
384           }
385           num_expected_large_tails = RoundUp(r->BytesAllocated(), kRegionSize) / kRegionSize - 1;
386           DCHECK_GT(num_expected_large_tails, 0U);
387         }
388       } else {
389         DCHECK(state == RegionState::kRegionStateLargeTail &&
390                type == RegionType::kRegionTypeToSpace);
391         if (prev_large_evacuated) {
392           r->SetAsFromSpace();
393           DCHECK(r->IsInFromSpace());
394         } else {
395           r->SetAsUnevacFromSpace(clear_live_bytes);
396           DCHECK(r->IsInUnevacFromSpace());
397         }
398         --num_expected_large_tails;
399       }
400     } else {
401       DCHECK_EQ(num_expected_large_tails, 0U);
402       if (kUseTableLookupReadBarrier) {
403         // Clear the rb table for to-space regions.
404         rb_table->Clear(r->Begin(), r->End());
405       }
406     }
407     // Invariant: There should be no newly-allocated region in the from-space.
408     DCHECK(!r->is_newly_allocated_);
409   }
410   DCHECK_EQ(num_expected_large_tails, 0U);
411   current_region_ = &full_region_;
412   evac_region_ = &full_region_;
413 }
414 
ZeroAndProtectRegion(uint8_t * begin,uint8_t * end)415 static void ZeroAndProtectRegion(uint8_t* begin, uint8_t* end) {
416   ZeroAndReleasePages(begin, end - begin);
417   if (kProtectClearedRegions) {
418     CheckedCall(mprotect, __FUNCTION__, begin, end - begin, PROT_NONE);
419   }
420 }
421 
ClearFromSpace(uint64_t * cleared_bytes,uint64_t * cleared_objects,const bool clear_bitmap)422 void RegionSpace::ClearFromSpace(/* out */ uint64_t* cleared_bytes,
423                                  /* out */ uint64_t* cleared_objects,
424                                  const bool clear_bitmap) {
425   DCHECK(cleared_bytes != nullptr);
426   DCHECK(cleared_objects != nullptr);
427   *cleared_bytes = 0;
428   *cleared_objects = 0;
429   size_t new_non_free_region_index_limit = 0;
430   // We should avoid calling madvise syscalls while holding region_lock_.
431   // Therefore, we split the working of this function into 2 loops. The first
432   // loop gathers memory ranges that must be madvised. Then we release the lock
433   // and perform madvise on the gathered memory ranges. Finally, we reacquire
434   // the lock and loop over the regions to clear the from-space regions and make
435   // them availabe for allocation.
436   std::deque<std::pair<uint8_t*, uint8_t*>> madvise_list;
437   // Gather memory ranges that need to be madvised.
438   {
439     MutexLock mu(Thread::Current(), region_lock_);
440     // Lambda expression `expand_madvise_range` adds a region to the "clear block".
441     //
442     // As we iterate over from-space regions, we maintain a "clear block", composed of
443     // adjacent to-be-cleared regions and whose bounds are `clear_block_begin` and
444     // `clear_block_end`. When processing a new region which is not adjacent to
445     // the clear block (discontinuity in cleared regions), the clear block
446     // is added to madvise_list and the clear block is reset (to the most recent
447     // to-be-cleared region).
448     //
449     // This is done in order to combine zeroing and releasing pages to reduce how
450     // often madvise is called. This helps reduce contention on the mmap semaphore
451     // (see b/62194020).
452     uint8_t* clear_block_begin = nullptr;
453     uint8_t* clear_block_end = nullptr;
454     auto expand_madvise_range = [&madvise_list, &clear_block_begin, &clear_block_end] (Region* r) {
455       if (clear_block_end != r->Begin()) {
456         if (clear_block_begin != nullptr) {
457           DCHECK(clear_block_end != nullptr);
458           madvise_list.push_back(std::pair(clear_block_begin, clear_block_end));
459         }
460         clear_block_begin = r->Begin();
461       }
462       clear_block_end = r->End();
463     };
464     for (size_t i = 0; i < std::min(num_regions_, non_free_region_index_limit_); ++i) {
465       Region* r = &regions_[i];
466       // The following check goes through objects in the region, therefore it
467       // must be performed before madvising the region. Therefore, it can't be
468       // executed in the following loop.
469       if (kCheckLiveBytesAgainstRegionBitmap) {
470         CheckLiveBytesAgainstRegionBitmap(r);
471       }
472       if (r->IsInFromSpace()) {
473         expand_madvise_range(r);
474       } else if (r->IsInUnevacFromSpace()) {
475         // We must skip tails of live large objects.
476         if (r->LiveBytes() == 0 && !r->IsLargeTail()) {
477           // Special case for 0 live bytes, this means all of the objects in the region are
478           // dead and we can to clear it. This is important for large objects since we must
479           // not visit dead ones in RegionSpace::Walk because they may contain dangling
480           // references to invalid objects. It is also better to clear these regions now
481           // instead of at the end of the next GC to save RAM. If we don't clear the regions
482           // here, they will be cleared in next GC by the normal live percent evacuation logic.
483           expand_madvise_range(r);
484           // Also release RAM for large tails.
485           while (i + 1 < num_regions_ && regions_[i + 1].IsLargeTail()) {
486             expand_madvise_range(&regions_[i + 1]);
487             i++;
488           }
489         }
490       }
491     }
492     // There is a small probability that we may reach here with
493     // clear_block_{begin, end} = nullptr. If all the regions allocated since
494     // last GC have been for large objects and all of them survive till this GC
495     // cycle, then there will be no regions in from-space.
496     if (LIKELY(clear_block_begin != nullptr)) {
497       DCHECK(clear_block_end != nullptr);
498       madvise_list.push_back(std::pair(clear_block_begin, clear_block_end));
499     }
500   }
501 
502   // Madvise the memory ranges.
503   uint64_t start_time = NanoTime();
504   for (const auto &iter : madvise_list) {
505     ZeroAndProtectRegion(iter.first, iter.second);
506   }
507   madvise_time_ += NanoTime() - start_time;
508 
509   for (const auto &iter : madvise_list) {
510     if (clear_bitmap) {
511       GetLiveBitmap()->ClearRange(
512           reinterpret_cast<mirror::Object*>(iter.first),
513           reinterpret_cast<mirror::Object*>(iter.second));
514     }
515   }
516   madvise_list.clear();
517 
518   // Iterate over regions again and actually make the from space regions
519   // available for allocation.
520   MutexLock mu(Thread::Current(), region_lock_);
521   VerifyNonFreeRegionLimit();
522 
523   // Update max of peak non free region count before reclaiming evacuated regions.
524   max_peak_num_non_free_regions_ = std::max(max_peak_num_non_free_regions_,
525                                             num_non_free_regions_);
526 
527   for (size_t i = 0; i < std::min(num_regions_, non_free_region_index_limit_); ++i) {
528     Region* r = &regions_[i];
529     if (r->IsInFromSpace()) {
530       DCHECK(!r->IsTlab());
531       *cleared_bytes += r->BytesAllocated();
532       *cleared_objects += r->ObjectsAllocated();
533       --num_non_free_regions_;
534       r->Clear(/*zero_and_release_pages=*/false);
535     } else if (r->IsInUnevacFromSpace()) {
536       if (r->LiveBytes() == 0) {
537         DCHECK(!r->IsLargeTail());
538         *cleared_bytes += r->BytesAllocated();
539         *cleared_objects += r->ObjectsAllocated();
540         r->Clear(/*zero_and_release_pages=*/false);
541         size_t free_regions = 1;
542         // Also release RAM for large tails.
543         while (i + free_regions < num_regions_ && regions_[i + free_regions].IsLargeTail()) {
544           regions_[i + free_regions].Clear(/*zero_and_release_pages=*/false);
545           ++free_regions;
546         }
547         num_non_free_regions_ -= free_regions;
548         // When clear_bitmap is true, this clearing of bitmap is taken care in
549         // clear_region().
550         if (!clear_bitmap) {
551           GetLiveBitmap()->ClearRange(
552               reinterpret_cast<mirror::Object*>(r->Begin()),
553               reinterpret_cast<mirror::Object*>(r->Begin() + free_regions * kRegionSize));
554         }
555         continue;
556       }
557       r->SetUnevacFromSpaceAsToSpace();
558       if (r->AllAllocatedBytesAreLive()) {
559         // Try to optimize the number of ClearRange calls by checking whether the next regions
560         // can also be cleared.
561         size_t regions_to_clear_bitmap = 1;
562         while (i + regions_to_clear_bitmap < num_regions_) {
563           Region* const cur = &regions_[i + regions_to_clear_bitmap];
564           if (!cur->AllAllocatedBytesAreLive()) {
565             DCHECK(!cur->IsLargeTail());
566             break;
567           }
568           CHECK(cur->IsInUnevacFromSpace());
569           cur->SetUnevacFromSpaceAsToSpace();
570           ++regions_to_clear_bitmap;
571         }
572 
573         // Optimization (for full CC only): If the live bytes are *all* live
574         // in a region then the live-bit information for these objects is
575         // superfluous:
576         // - We can determine that these objects are all live by using
577         //   Region::AllAllocatedBytesAreLive (which just checks whether
578         //   `LiveBytes() == static_cast<size_t>(Top() - Begin())`.
579         // - We can visit the objects in this region using
580         //   RegionSpace::GetNextObject, i.e. without resorting to the
581         //   live bits (see RegionSpace::WalkInternal).
582         // Therefore, we can clear the bits for these objects in the
583         // (live) region space bitmap (and release the corresponding pages).
584         //
585         // This optimization is incompatible with Generational CC, because:
586         // - minor (young-generation) collections need to know which objects
587         //   where marked during the previous GC cycle, meaning all mark bitmaps
588         //   (this includes the region space bitmap) need to be preserved
589         //   between a (minor or major) collection N and a following minor
590         //   collection N+1;
591         // - at this stage (in the current GC cycle), we cannot determine
592         //   whether the next collection will be a minor or a major one;
593         // This means that we need to be conservative and always preserve the
594         // region space bitmap when using Generational CC.
595         // Note that major collections do not require the previous mark bitmaps
596         // to be preserved, and as matter of fact they do clear the region space
597         // bitmap. But they cannot do so before we know the next GC cycle will
598         // be a major one, so this operation happens at the beginning of such a
599         // major collection, before marking starts.
600         if (!use_generational_cc_) {
601           GetLiveBitmap()->ClearRange(
602               reinterpret_cast<mirror::Object*>(r->Begin()),
603               reinterpret_cast<mirror::Object*>(r->Begin()
604                                                 + regions_to_clear_bitmap * kRegionSize));
605         }
606         // Skip over extra regions for which we cleared the bitmaps: we shall not clear them,
607         // as they are unevac regions that are live.
608         // Subtract one for the for-loop.
609         i += regions_to_clear_bitmap - 1;
610       } else {
611         // TODO: Explain why we do not poison dead objects in region
612         // `r` when it has an undefined live bytes count (i.e. when
613         // `r->LiveBytes() == static_cast<size_t>(-1)`) with
614         // Generational CC.
615         if (!use_generational_cc_ || (r->LiveBytes() != static_cast<size_t>(-1))) {
616           // Only some allocated bytes are live in this unevac region.
617           // This should only happen for an allocated non-large region.
618           DCHECK(r->IsAllocated()) << r->State();
619           if (kPoisonDeadObjectsInUnevacuatedRegions) {
620             PoisonDeadObjectsInUnevacuatedRegion(r);
621           }
622         }
623       }
624     }
625     // Note r != last_checked_region if r->IsInUnevacFromSpace() was true above.
626     Region* last_checked_region = &regions_[i];
627     if (!last_checked_region->IsFree()) {
628       new_non_free_region_index_limit = std::max(new_non_free_region_index_limit,
629                                                  last_checked_region->Idx() + 1);
630     }
631   }
632   // Update non_free_region_index_limit_.
633   SetNonFreeRegionLimit(new_non_free_region_index_limit);
634   evac_region_ = nullptr;
635   num_non_free_regions_ += num_evac_regions_;
636   num_evac_regions_ = 0;
637 }
638 
CheckLiveBytesAgainstRegionBitmap(Region * r)639 void RegionSpace::CheckLiveBytesAgainstRegionBitmap(Region* r) {
640   if (r->LiveBytes() == static_cast<size_t>(-1)) {
641     // Live bytes count is undefined for `r`; nothing to check here.
642     return;
643   }
644 
645   // Functor walking the region space bitmap for the range corresponding
646   // to region `r` and calculating the sum of live bytes.
647   size_t live_bytes_recount = 0u;
648   auto recount_live_bytes =
649       [&r, &live_bytes_recount](mirror::Object* obj) REQUIRES_SHARED(Locks::mutator_lock_) {
650     DCHECK_ALIGNED(obj, kAlignment);
651     if (r->IsLarge()) {
652       // If `r` is a large region, then it contains at most one
653       // object, which must start at the beginning of the
654       // region. The live byte count in that case is equal to the
655       // allocated regions (large region + large tails regions).
656       DCHECK_EQ(reinterpret_cast<uint8_t*>(obj), r->Begin());
657       DCHECK_EQ(live_bytes_recount, 0u);
658       live_bytes_recount = r->Top() - r->Begin();
659     } else {
660       DCHECK(r->IsAllocated())
661           << "r->State()=" << r->State() << " r->LiveBytes()=" << r->LiveBytes();
662       size_t obj_size = obj->SizeOf<kDefaultVerifyFlags>();
663       size_t alloc_size = RoundUp(obj_size, space::RegionSpace::kAlignment);
664       live_bytes_recount += alloc_size;
665     }
666   };
667   // Visit live objects in `r` and recount the live bytes.
668   GetLiveBitmap()->VisitMarkedRange(reinterpret_cast<uintptr_t>(r->Begin()),
669                                     reinterpret_cast<uintptr_t>(r->Top()),
670                                     recount_live_bytes);
671   // Check that this recount matches the region's current live bytes count.
672   DCHECK_EQ(live_bytes_recount, r->LiveBytes());
673 }
674 
675 // Poison the memory area in range [`begin`, `end`) with value `kPoisonDeadObject`.
PoisonUnevacuatedRange(uint8_t * begin,uint8_t * end)676 static void PoisonUnevacuatedRange(uint8_t* begin, uint8_t* end) {
677   static constexpr size_t kPoisonDeadObjectSize = sizeof(kPoisonDeadObject);
678   static_assert(IsPowerOfTwo(kPoisonDeadObjectSize) &&
679                 IsPowerOfTwo(RegionSpace::kAlignment) &&
680                 (kPoisonDeadObjectSize < RegionSpace::kAlignment),
681                 "RegionSpace::kAlignment should be a multiple of kPoisonDeadObjectSize"
682                 " and both should be powers of 2");
683   DCHECK_ALIGNED(begin, kPoisonDeadObjectSize);
684   DCHECK_ALIGNED(end, kPoisonDeadObjectSize);
685   uint32_t* begin_addr = reinterpret_cast<uint32_t*>(begin);
686   uint32_t* end_addr = reinterpret_cast<uint32_t*>(end);
687   std::fill(begin_addr, end_addr, kPoisonDeadObject);
688 }
689 
PoisonDeadObjectsInUnevacuatedRegion(Region * r)690 void RegionSpace::PoisonDeadObjectsInUnevacuatedRegion(Region* r) {
691   // The live byte count of `r` should be different from -1, as this
692   // region should neither be a newly allocated region nor an
693   // evacuated region.
694   DCHECK_NE(r->LiveBytes(), static_cast<size_t>(-1))
695       << "Unexpected live bytes count of -1 in " << Dumpable<Region>(*r);
696 
697   // Past-the-end address of the previously visited (live) object (or
698   // the beginning of the region, if `maybe_poison` has not run yet).
699   uint8_t* prev_obj_end = reinterpret_cast<uint8_t*>(r->Begin());
700 
701   // Functor poisoning the space between `obj` and the previously
702   // visited (live) object (or the beginng of the region), if any.
703   auto maybe_poison = [&prev_obj_end](mirror::Object* obj) REQUIRES(Locks::mutator_lock_) {
704     DCHECK_ALIGNED(obj, kAlignment);
705     uint8_t* cur_obj_begin = reinterpret_cast<uint8_t*>(obj);
706     if (cur_obj_begin != prev_obj_end) {
707       // There is a gap (dead object(s)) between the previously
708       // visited (live) object (or the beginning of the region) and
709       // `obj`; poison that space.
710       PoisonUnevacuatedRange(prev_obj_end, cur_obj_begin);
711     }
712     prev_obj_end = reinterpret_cast<uint8_t*>(GetNextObject(obj));
713   };
714 
715   // Visit live objects in `r` and poison gaps (dead objects) between them.
716   GetLiveBitmap()->VisitMarkedRange(reinterpret_cast<uintptr_t>(r->Begin()),
717                                     reinterpret_cast<uintptr_t>(r->Top()),
718                                     maybe_poison);
719   // Poison memory between the last live object and the end of the region, if any.
720   if (prev_obj_end < r->Top()) {
721     PoisonUnevacuatedRange(prev_obj_end, r->Top());
722   }
723 }
724 
LogFragmentationAllocFailure(std::ostream & os,size_t failed_alloc_bytes)725 bool RegionSpace::LogFragmentationAllocFailure(std::ostream& os,
726                                                size_t failed_alloc_bytes) {
727   size_t max_contiguous_allocation = 0;
728   MutexLock mu(Thread::Current(), region_lock_);
729 
730   if (current_region_->End() - current_region_->Top() > 0) {
731     max_contiguous_allocation = current_region_->End() - current_region_->Top();
732   }
733 
734   size_t max_contiguous_free_regions = 0;
735   size_t num_contiguous_free_regions = 0;
736   bool prev_free_region = false;
737   for (size_t i = 0; i < num_regions_; ++i) {
738     Region* r = &regions_[i];
739     if (r->IsFree()) {
740       if (!prev_free_region) {
741         CHECK_EQ(num_contiguous_free_regions, 0U);
742         prev_free_region = true;
743       }
744       ++num_contiguous_free_regions;
745     } else if (prev_free_region) {
746       CHECK_NE(num_contiguous_free_regions, 0U);
747       max_contiguous_free_regions = std::max(max_contiguous_free_regions,
748                                              num_contiguous_free_regions);
749       num_contiguous_free_regions = 0U;
750       prev_free_region = false;
751     }
752   }
753   max_contiguous_allocation = std::max(max_contiguous_allocation,
754                                        max_contiguous_free_regions * kRegionSize);
755 
756   // Calculate how many regions are available for allocations as we have to ensure
757   // that enough regions are left for evacuation.
758   size_t regions_free_for_alloc = num_regions_ / 2 - num_non_free_regions_;
759 
760   max_contiguous_allocation = std::min(max_contiguous_allocation,
761                                        regions_free_for_alloc * kRegionSize);
762   if (failed_alloc_bytes > max_contiguous_allocation) {
763     os << "; failed due to fragmentation (largest possible contiguous allocation "
764        <<  max_contiguous_allocation << " bytes). Number of "
765        << PrettySize(kRegionSize)
766        << " sized free regions are: " << regions_free_for_alloc;
767     return true;
768   }
769   // Caller's job to print failed_alloc_bytes.
770   return false;
771 }
772 
Clear()773 void RegionSpace::Clear() {
774   MutexLock mu(Thread::Current(), region_lock_);
775   for (size_t i = 0; i < num_regions_; ++i) {
776     Region* r = &regions_[i];
777     if (!r->IsFree()) {
778       --num_non_free_regions_;
779     }
780     r->Clear(/*zero_and_release_pages=*/true);
781   }
782   SetNonFreeRegionLimit(0);
783   DCHECK_EQ(num_non_free_regions_, 0u);
784   current_region_ = &full_region_;
785   evac_region_ = &full_region_;
786 }
787 
Protect()788 void RegionSpace::Protect() {
789   if (kProtectClearedRegions) {
790     CheckedCall(mprotect, __FUNCTION__, Begin(), Size(), PROT_NONE);
791   }
792 }
793 
Unprotect()794 void RegionSpace::Unprotect() {
795   if (kProtectClearedRegions) {
796     CheckedCall(mprotect, __FUNCTION__, Begin(), Size(), PROT_READ | PROT_WRITE);
797   }
798 }
799 
ClampGrowthLimit(size_t new_capacity)800 void RegionSpace::ClampGrowthLimit(size_t new_capacity) {
801   MutexLock mu(Thread::Current(), region_lock_);
802   CHECK_LE(new_capacity, NonGrowthLimitCapacity());
803   size_t new_num_regions = new_capacity / kRegionSize;
804   if (non_free_region_index_limit_ > new_num_regions) {
805     LOG(WARNING) << "Couldn't clamp region space as there are regions in use beyond growth limit.";
806     return;
807   }
808   num_regions_ = new_num_regions;
809   if (kCyclicRegionAllocation && cyclic_alloc_region_index_ >= num_regions_) {
810     cyclic_alloc_region_index_ = 0u;
811   }
812   SetLimit(Begin() + new_capacity);
813   if (Size() > new_capacity) {
814     SetEnd(Limit());
815   }
816   GetMarkBitmap()->SetHeapSize(new_capacity);
817   GetMemMap()->SetSize(new_capacity);
818 }
819 
Dump(std::ostream & os) const820 void RegionSpace::Dump(std::ostream& os) const {
821   os << GetName() << " "
822      << reinterpret_cast<void*>(Begin()) << "-" << reinterpret_cast<void*>(Limit());
823 }
824 
DumpRegionForObject(std::ostream & os,mirror::Object * obj)825 void RegionSpace::DumpRegionForObject(std::ostream& os, mirror::Object* obj) {
826   CHECK(HasAddress(obj));
827   MutexLock mu(Thread::Current(), region_lock_);
828   RefToRegionUnlocked(obj)->Dump(os);
829 }
830 
DumpRegions(std::ostream & os)831 void RegionSpace::DumpRegions(std::ostream& os) {
832   MutexLock mu(Thread::Current(), region_lock_);
833   for (size_t i = 0; i < num_regions_; ++i) {
834     regions_[i].Dump(os);
835   }
836 }
837 
DumpNonFreeRegions(std::ostream & os)838 void RegionSpace::DumpNonFreeRegions(std::ostream& os) {
839   MutexLock mu(Thread::Current(), region_lock_);
840   for (size_t i = 0; i < num_regions_; ++i) {
841     Region* reg = &regions_[i];
842     if (!reg->IsFree()) {
843       reg->Dump(os);
844     }
845   }
846 }
847 
RecordAlloc(mirror::Object * ref)848 void RegionSpace::RecordAlloc(mirror::Object* ref) {
849   CHECK(ref != nullptr);
850   Region* r = RefToRegion(ref);
851   r->objects_allocated_.fetch_add(1, std::memory_order_relaxed);
852 }
853 
AllocNewTlab(Thread * self,const size_t tlab_size,size_t * bytes_tl_bulk_allocated)854 bool RegionSpace::AllocNewTlab(Thread* self,
855                                const size_t tlab_size,
856                                size_t* bytes_tl_bulk_allocated) {
857   MutexLock mu(self, region_lock_);
858   RevokeThreadLocalBuffersLocked(self, /*reuse=*/ gc::Heap::kUsePartialTlabs);
859   Region* r = nullptr;
860   uint8_t* pos = nullptr;
861   *bytes_tl_bulk_allocated = tlab_size;
862   // First attempt to get a partially used TLAB, if available.
863   if (tlab_size < kRegionSize) {
864     // Fetch the largest partial TLAB. The multimap is ordered in decreasing
865     // size.
866     auto largest_partial_tlab = partial_tlabs_.begin();
867     if (largest_partial_tlab != partial_tlabs_.end() && largest_partial_tlab->first >= tlab_size) {
868       r = largest_partial_tlab->second;
869       pos = r->End() - largest_partial_tlab->first;
870       partial_tlabs_.erase(largest_partial_tlab);
871       DCHECK_GT(r->End(), pos);
872       DCHECK_LE(r->Begin(), pos);
873       DCHECK_GE(r->Top(), pos);
874       *bytes_tl_bulk_allocated -= r->Top() - pos;
875     }
876   }
877   if (r == nullptr) {
878     // Fallback to allocating an entire region as TLAB.
879     r = AllocateRegion(/*for_evac=*/ false);
880   }
881   if (r != nullptr) {
882     uint8_t* start = pos != nullptr ? pos : r->Begin();
883     DCHECK_ALIGNED(start, kObjectAlignment);
884     r->is_a_tlab_ = true;
885     r->thread_ = self;
886     r->SetTop(r->End());
887     self->SetTlab(start, start + tlab_size, r->End());
888     return true;
889   }
890   return false;
891 }
892 
RevokeThreadLocalBuffers(Thread * thread)893 size_t RegionSpace::RevokeThreadLocalBuffers(Thread* thread) {
894   MutexLock mu(Thread::Current(), region_lock_);
895   RevokeThreadLocalBuffersLocked(thread, /*reuse=*/ gc::Heap::kUsePartialTlabs);
896   return 0U;
897 }
898 
RevokeThreadLocalBuffers(Thread * thread,const bool reuse)899 size_t RegionSpace::RevokeThreadLocalBuffers(Thread* thread, const bool reuse) {
900   MutexLock mu(Thread::Current(), region_lock_);
901   RevokeThreadLocalBuffersLocked(thread, reuse);
902   return 0U;
903 }
904 
RevokeThreadLocalBuffersLocked(Thread * thread,bool reuse)905 void RegionSpace::RevokeThreadLocalBuffersLocked(Thread* thread, bool reuse) {
906   uint8_t* tlab_start = thread->GetTlabStart();
907   DCHECK_EQ(thread->HasTlab(), tlab_start != nullptr);
908   if (tlab_start != nullptr) {
909     Region* r = RefToRegionLocked(reinterpret_cast<mirror::Object*>(tlab_start));
910     r->is_a_tlab_ = false;
911     r->thread_ = nullptr;
912     DCHECK(r->IsAllocated());
913     DCHECK_LE(thread->GetThreadLocalBytesAllocated(), kRegionSize);
914     r->RecordThreadLocalAllocations(thread->GetThreadLocalObjectsAllocated(),
915                                     thread->GetTlabEnd() - r->Begin());
916     DCHECK_GE(r->End(), thread->GetTlabPos());
917     DCHECK_LE(r->Begin(), thread->GetTlabPos());
918     size_t remaining_bytes = r->End() - thread->GetTlabPos();
919     if (reuse && remaining_bytes >= gc::Heap::kPartialTlabSize) {
920       partial_tlabs_.insert(std::make_pair(remaining_bytes, r));
921     }
922   }
923   thread->ResetTlab();
924 }
925 
RevokeAllThreadLocalBuffers()926 size_t RegionSpace::RevokeAllThreadLocalBuffers() {
927   Thread* self = Thread::Current();
928   MutexLock mu(self, *Locks::runtime_shutdown_lock_);
929   MutexLock mu2(self, *Locks::thread_list_lock_);
930   std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
931   for (Thread* thread : thread_list) {
932     RevokeThreadLocalBuffers(thread);
933   }
934   return 0U;
935 }
936 
AssertThreadLocalBuffersAreRevoked(Thread * thread)937 void RegionSpace::AssertThreadLocalBuffersAreRevoked(Thread* thread) {
938   if (kIsDebugBuild) {
939     DCHECK(!thread->HasTlab());
940   }
941 }
942 
AssertAllThreadLocalBuffersAreRevoked()943 void RegionSpace::AssertAllThreadLocalBuffersAreRevoked() {
944   if (kIsDebugBuild) {
945     Thread* self = Thread::Current();
946     MutexLock mu(self, *Locks::runtime_shutdown_lock_);
947     MutexLock mu2(self, *Locks::thread_list_lock_);
948     std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
949     for (Thread* thread : thread_list) {
950       AssertThreadLocalBuffersAreRevoked(thread);
951     }
952   }
953 }
954 
Dump(std::ostream & os) const955 void RegionSpace::Region::Dump(std::ostream& os) const {
956   os << "Region[" << idx_ << "]="
957      << reinterpret_cast<void*>(begin_)
958      << "-" << reinterpret_cast<void*>(Top())
959      << "-" << reinterpret_cast<void*>(end_)
960      << " state=" << state_
961      << " type=" << type_
962      << " objects_allocated=" << objects_allocated_
963      << " alloc_time=" << alloc_time_
964      << " live_bytes=" << live_bytes_;
965 
966   if (live_bytes_ != static_cast<size_t>(-1)) {
967     os << " ratio over allocated bytes="
968        << (static_cast<float>(live_bytes_) / RoundUp(BytesAllocated(), kRegionSize));
969     uint64_t longest_consecutive_free_bytes = GetLongestConsecutiveFreeBytes();
970     os << " longest_consecutive_free_bytes=" << longest_consecutive_free_bytes
971        << " (" << PrettySize(longest_consecutive_free_bytes) << ")";
972   }
973 
974   os << " is_newly_allocated=" << std::boolalpha << is_newly_allocated_ << std::noboolalpha
975      << " is_a_tlab=" << std::boolalpha << is_a_tlab_ << std::noboolalpha
976      << " thread=" << thread_ << '\n';
977 }
978 
GetLongestConsecutiveFreeBytes() const979 uint64_t RegionSpace::Region::GetLongestConsecutiveFreeBytes() const {
980   if (IsFree()) {
981     return kRegionSize;
982   }
983   if (IsLarge() || IsLargeTail()) {
984     return 0u;
985   }
986   uintptr_t max_gap = 0u;
987   uintptr_t prev_object_end = reinterpret_cast<uintptr_t>(Begin());
988   // Iterate through all live objects and find the largest free gap.
989   auto visitor = [&max_gap, &prev_object_end](mirror::Object* obj)
990     REQUIRES_SHARED(Locks::mutator_lock_) {
991     uintptr_t current = reinterpret_cast<uintptr_t>(obj);
992     uintptr_t diff = current - prev_object_end;
993     max_gap = std::max(diff, max_gap);
994     uintptr_t object_end = reinterpret_cast<uintptr_t>(obj) + obj->SizeOf();
995     prev_object_end = RoundUp(object_end, kAlignment);
996   };
997   space::RegionSpace* region_space = art::Runtime::Current()->GetHeap()->GetRegionSpace();
998   region_space->WalkNonLargeRegion(visitor, this);
999   return static_cast<uint64_t>(max_gap);
1000 }
1001 
1002 
AllocationSizeNonvirtual(mirror::Object * obj,size_t * usable_size)1003 size_t RegionSpace::AllocationSizeNonvirtual(mirror::Object* obj, size_t* usable_size) {
1004   size_t num_bytes = obj->SizeOf();
1005   if (usable_size != nullptr) {
1006     if (LIKELY(num_bytes <= kRegionSize)) {
1007       DCHECK(RefToRegion(obj)->IsAllocated());
1008       *usable_size = RoundUp(num_bytes, kAlignment);
1009     } else {
1010       DCHECK(RefToRegion(obj)->IsLarge());
1011       *usable_size = RoundUp(num_bytes, kRegionSize);
1012     }
1013   }
1014   return num_bytes;
1015 }
1016 
Clear(bool zero_and_release_pages)1017 void RegionSpace::Region::Clear(bool zero_and_release_pages) {
1018   top_.store(begin_, std::memory_order_relaxed);
1019   state_ = RegionState::kRegionStateFree;
1020   type_ = RegionType::kRegionTypeNone;
1021   objects_allocated_.store(0, std::memory_order_relaxed);
1022   alloc_time_ = 0;
1023   live_bytes_ = static_cast<size_t>(-1);
1024   if (zero_and_release_pages) {
1025     ZeroAndProtectRegion(begin_, end_);
1026   }
1027   is_newly_allocated_ = false;
1028   is_a_tlab_ = false;
1029   thread_ = nullptr;
1030 }
1031 
TraceHeapSize()1032 void RegionSpace::TraceHeapSize() {
1033   Heap* heap = Runtime::Current()->GetHeap();
1034   heap->TraceHeapSize(heap->GetBytesAllocated() + EvacBytes());
1035 }
1036 
AllocateRegion(bool for_evac)1037 RegionSpace::Region* RegionSpace::AllocateRegion(bool for_evac) {
1038   if (!for_evac && (num_non_free_regions_ + 1) * 2 > num_regions_) {
1039     return nullptr;
1040   }
1041   for (size_t i = 0; i < num_regions_; ++i) {
1042     // When using the cyclic region allocation strategy, try to
1043     // allocate a region starting from the last cyclic allocated
1044     // region marker. Otherwise, try to allocate a region starting
1045     // from the beginning of the region space.
1046     size_t region_index = kCyclicRegionAllocation
1047         ? ((cyclic_alloc_region_index_ + i) % num_regions_)
1048         : i;
1049     Region* r = &regions_[region_index];
1050     if (r->IsFree()) {
1051       r->Unfree(this, time_);
1052       if (use_generational_cc_) {
1053         // TODO: Add an explanation for this assertion.
1054         DCHECK(!for_evac || !r->is_newly_allocated_);
1055       }
1056       if (for_evac) {
1057         ++num_evac_regions_;
1058         TraceHeapSize();
1059         // Evac doesn't count as newly allocated.
1060       } else {
1061         r->SetNewlyAllocated();
1062         ++num_non_free_regions_;
1063       }
1064       if (kCyclicRegionAllocation) {
1065         // Move the cyclic allocation region marker to the region
1066         // following the one that was just allocated.
1067         cyclic_alloc_region_index_ = (region_index + 1) % num_regions_;
1068       }
1069       return r;
1070     }
1071   }
1072   return nullptr;
1073 }
1074 
MarkAsAllocated(RegionSpace * region_space,uint32_t alloc_time)1075 void RegionSpace::Region::MarkAsAllocated(RegionSpace* region_space, uint32_t alloc_time) {
1076   DCHECK(IsFree());
1077   alloc_time_ = alloc_time;
1078   region_space->AdjustNonFreeRegionLimit(idx_);
1079   type_ = RegionType::kRegionTypeToSpace;
1080   if (kProtectClearedRegions) {
1081     CheckedCall(mprotect, __FUNCTION__, Begin(), kRegionSize, PROT_READ | PROT_WRITE);
1082   }
1083 }
1084 
Unfree(RegionSpace * region_space,uint32_t alloc_time)1085 void RegionSpace::Region::Unfree(RegionSpace* region_space, uint32_t alloc_time) {
1086   MarkAsAllocated(region_space, alloc_time);
1087   state_ = RegionState::kRegionStateAllocated;
1088 }
1089 
UnfreeLarge(RegionSpace * region_space,uint32_t alloc_time)1090 void RegionSpace::Region::UnfreeLarge(RegionSpace* region_space, uint32_t alloc_time) {
1091   MarkAsAllocated(region_space, alloc_time);
1092   state_ = RegionState::kRegionStateLarge;
1093 }
1094 
UnfreeLargeTail(RegionSpace * region_space,uint32_t alloc_time)1095 void RegionSpace::Region::UnfreeLargeTail(RegionSpace* region_space, uint32_t alloc_time) {
1096   MarkAsAllocated(region_space, alloc_time);
1097   state_ = RegionState::kRegionStateLargeTail;
1098 }
1099 
1100 }  // namespace space
1101 }  // namespace gc
1102 }  // namespace art
1103