1 /*
2  * Copyright (C) 2013 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 #include "semi_space-inl.h"
18 
19 #include <climits>
20 #include <functional>
21 #include <numeric>
22 #include <sstream>
23 #include <vector>
24 
25 #include "base/logging.h"
26 #include "base/macros.h"
27 #include "base/mutex-inl.h"
28 #include "base/timing_logger.h"
29 #include "gc/accounting/heap_bitmap-inl.h"
30 #include "gc/accounting/mod_union_table.h"
31 #include "gc/accounting/remembered_set.h"
32 #include "gc/accounting/space_bitmap-inl.h"
33 #include "gc/heap.h"
34 #include "gc/reference_processor.h"
35 #include "gc/space/bump_pointer_space.h"
36 #include "gc/space/bump_pointer_space-inl.h"
37 #include "gc/space/image_space.h"
38 #include "gc/space/large_object_space.h"
39 #include "gc/space/space-inl.h"
40 #include "indirect_reference_table.h"
41 #include "intern_table.h"
42 #include "jni_internal.h"
43 #include "mark_sweep-inl.h"
44 #include "monitor.h"
45 #include "mirror/reference-inl.h"
46 #include "mirror/object-inl.h"
47 #include "runtime.h"
48 #include "thread-inl.h"
49 #include "thread_list.h"
50 
51 using ::art::mirror::Object;
52 
53 namespace art {
54 namespace gc {
55 namespace collector {
56 
57 static constexpr bool kProtectFromSpace = true;
58 static constexpr bool kStoreStackTraces = false;
59 static constexpr size_t kBytesPromotedThreshold = 4 * MB;
60 static constexpr size_t kLargeObjectBytesAllocatedThreshold = 16 * MB;
61 
BindBitmaps()62 void SemiSpace::BindBitmaps() {
63   TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
64   WriterMutexLock mu(self_, *Locks::heap_bitmap_lock_);
65   // Mark all of the spaces we never collect as immune.
66   for (const auto& space : GetHeap()->GetContinuousSpaces()) {
67     if (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyNeverCollect ||
68         space->GetGcRetentionPolicy() == space::kGcRetentionPolicyFullCollect) {
69       immune_spaces_.AddSpace(space);
70     } else if (space->GetLiveBitmap() != nullptr) {
71       // TODO: We can probably also add this space to the immune region.
72       if (space == to_space_ || collect_from_space_only_) {
73         if (collect_from_space_only_) {
74           // Bind the bitmaps of the main free list space and the non-moving space we are doing a
75           // bump pointer space only collection.
76           CHECK(space == GetHeap()->GetPrimaryFreeListSpace() ||
77                 space == GetHeap()->GetNonMovingSpace());
78         }
79         CHECK(space->IsContinuousMemMapAllocSpace());
80         space->AsContinuousMemMapAllocSpace()->BindLiveToMarkBitmap();
81       }
82     }
83   }
84   if (collect_from_space_only_) {
85     // We won't collect the large object space if a bump pointer space only collection.
86     is_large_object_space_immune_ = true;
87   }
88 }
89 
SemiSpace(Heap * heap,bool generational,const std::string & name_prefix)90 SemiSpace::SemiSpace(Heap* heap, bool generational, const std::string& name_prefix)
91     : GarbageCollector(heap,
92                        name_prefix + (name_prefix.empty() ? "" : " ") + "marksweep + semispace"),
93       mark_stack_(nullptr),
94       is_large_object_space_immune_(false),
95       to_space_(nullptr),
96       to_space_live_bitmap_(nullptr),
97       from_space_(nullptr),
98       mark_bitmap_(nullptr),
99       self_(nullptr),
100       generational_(generational),
101       last_gc_to_space_end_(nullptr),
102       bytes_promoted_(0),
103       bytes_promoted_since_last_whole_heap_collection_(0),
104       large_object_bytes_allocated_at_last_whole_heap_collection_(0),
105       collect_from_space_only_(generational),
106       promo_dest_space_(nullptr),
107       fallback_space_(nullptr),
108       bytes_moved_(0U),
109       objects_moved_(0U),
110       saved_bytes_(0U),
111       collector_name_(name_),
112       swap_semi_spaces_(true) {
113 }
114 
RunPhases()115 void SemiSpace::RunPhases() {
116   Thread* self = Thread::Current();
117   InitializePhase();
118   // Semi-space collector is special since it is sometimes called with the mutators suspended
119   // during the zygote creation and collector transitions. If we already exclusively hold the
120   // mutator lock, then we can't lock it again since it will cause a deadlock.
121   if (Locks::mutator_lock_->IsExclusiveHeld(self)) {
122     GetHeap()->PreGcVerificationPaused(this);
123     GetHeap()->PrePauseRosAllocVerification(this);
124     MarkingPhase();
125     ReclaimPhase();
126     GetHeap()->PostGcVerificationPaused(this);
127   } else {
128     Locks::mutator_lock_->AssertNotHeld(self);
129     {
130       ScopedPause pause(this);
131       GetHeap()->PreGcVerificationPaused(this);
132       GetHeap()->PrePauseRosAllocVerification(this);
133       MarkingPhase();
134     }
135     {
136       ReaderMutexLock mu(self, *Locks::mutator_lock_);
137       ReclaimPhase();
138     }
139     GetHeap()->PostGcVerification(this);
140   }
141   FinishPhase();
142 }
143 
InitializePhase()144 void SemiSpace::InitializePhase() {
145   TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
146   mark_stack_ = heap_->GetMarkStack();
147   DCHECK(mark_stack_ != nullptr);
148   immune_spaces_.Reset();
149   is_large_object_space_immune_ = false;
150   saved_bytes_ = 0;
151   bytes_moved_ = 0;
152   objects_moved_ = 0;
153   self_ = Thread::Current();
154   CHECK(from_space_->CanMoveObjects()) << "Attempting to move from " << *from_space_;
155   // Set the initial bitmap.
156   to_space_live_bitmap_ = to_space_->GetLiveBitmap();
157   {
158     // TODO: I don't think we should need heap bitmap lock to Get the mark bitmap.
159     ReaderMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_);
160     mark_bitmap_ = heap_->GetMarkBitmap();
161   }
162   if (generational_) {
163     promo_dest_space_ = GetHeap()->GetPrimaryFreeListSpace();
164   }
165   fallback_space_ = GetHeap()->GetNonMovingSpace();
166 }
167 
ProcessReferences(Thread * self)168 void SemiSpace::ProcessReferences(Thread* self) {
169   WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
170   GetHeap()->GetReferenceProcessor()->ProcessReferences(
171       false, GetTimings(), GetCurrentIteration()->GetClearSoftReferences(), this);
172 }
173 
MarkingPhase()174 void SemiSpace::MarkingPhase() {
175   TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
176   CHECK(Locks::mutator_lock_->IsExclusiveHeld(self_));
177   if (kStoreStackTraces) {
178     Locks::mutator_lock_->AssertExclusiveHeld(self_);
179     // Store the stack traces into the runtime fault string in case we Get a heap corruption
180     // related crash later.
181     ThreadState old_state = self_->SetStateUnsafe(kRunnable);
182     std::ostringstream oss;
183     Runtime* runtime = Runtime::Current();
184     runtime->GetThreadList()->DumpForSigQuit(oss);
185     runtime->GetThreadList()->DumpNativeStacks(oss);
186     runtime->SetFaultMessage(oss.str());
187     CHECK_EQ(self_->SetStateUnsafe(old_state), kRunnable);
188   }
189   // Revoke the thread local buffers since the GC may allocate into a RosAllocSpace and this helps
190   // to prevent fragmentation.
191   RevokeAllThreadLocalBuffers();
192   if (generational_) {
193     if (GetCurrentIteration()->GetGcCause() == kGcCauseExplicit ||
194         GetCurrentIteration()->GetGcCause() == kGcCauseForNativeAlloc ||
195         GetCurrentIteration()->GetClearSoftReferences()) {
196       // If an explicit, native allocation-triggered, or last attempt
197       // collection, collect the whole heap.
198       collect_from_space_only_ = false;
199     }
200     if (!collect_from_space_only_) {
201       VLOG(heap) << "Whole heap collection";
202       name_ = collector_name_ + " whole";
203     } else {
204       VLOG(heap) << "Bump pointer space only collection";
205       name_ = collector_name_ + " bps";
206     }
207   }
208 
209   if (!collect_from_space_only_) {
210     // If non-generational, always clear soft references.
211     // If generational, clear soft references if a whole heap collection.
212     GetCurrentIteration()->SetClearSoftReferences(true);
213   }
214   Locks::mutator_lock_->AssertExclusiveHeld(self_);
215   if (generational_) {
216     // If last_gc_to_space_end_ is out of the bounds of the from-space
217     // (the to-space from last GC), then point it to the beginning of
218     // the from-space. For example, the very first GC or the
219     // pre-zygote compaction.
220     if (!from_space_->HasAddress(reinterpret_cast<mirror::Object*>(last_gc_to_space_end_))) {
221       last_gc_to_space_end_ = from_space_->Begin();
222     }
223     // Reset this before the marking starts below.
224     bytes_promoted_ = 0;
225   }
226   // Assume the cleared space is already empty.
227   BindBitmaps();
228   // Process dirty cards and add dirty cards to mod-union tables.
229   heap_->ProcessCards(GetTimings(), kUseRememberedSet && generational_, false, true);
230   // Clear the whole card table since we cannot get any additional dirty cards during the
231   // paused GC. This saves memory but only works for pause the world collectors.
232   t.NewTiming("ClearCardTable");
233   heap_->GetCardTable()->ClearCardTable();
234   // Need to do this before the checkpoint since we don't want any threads to add references to
235   // the live stack during the recursive mark.
236   if (kUseThreadLocalAllocationStack) {
237     TimingLogger::ScopedTiming t2("RevokeAllThreadLocalAllocationStacks", GetTimings());
238     heap_->RevokeAllThreadLocalAllocationStacks(self_);
239   }
240   heap_->SwapStacks();
241   {
242     WriterMutexLock mu(self_, *Locks::heap_bitmap_lock_);
243     MarkRoots();
244     // Recursively mark remaining objects.
245     MarkReachableObjects();
246   }
247   ProcessReferences(self_);
248   {
249     ReaderMutexLock mu(self_, *Locks::heap_bitmap_lock_);
250     SweepSystemWeaks();
251   }
252   Runtime::Current()->GetClassLinker()->CleanupClassLoaders();
253   // Revoke buffers before measuring how many objects were moved since the TLABs need to be revoked
254   // before they are properly counted.
255   RevokeAllThreadLocalBuffers();
256   GetHeap()->RecordFreeRevoke();  // this is for the non-moving rosalloc space used by GSS.
257   // Record freed memory.
258   const int64_t from_bytes = from_space_->GetBytesAllocated();
259   const int64_t to_bytes = bytes_moved_;
260   const uint64_t from_objects = from_space_->GetObjectsAllocated();
261   const uint64_t to_objects = objects_moved_;
262   CHECK_LE(to_objects, from_objects);
263   // Note: Freed bytes can be negative if we copy form a compacted space to a free-list backed
264   // space.
265   RecordFree(ObjectBytePair(from_objects - to_objects, from_bytes - to_bytes));
266   // Clear and protect the from space.
267   from_space_->Clear();
268   if (kProtectFromSpace && !from_space_->IsRosAllocSpace()) {
269     // Protect with PROT_NONE.
270     VLOG(heap) << "Protecting from_space_ : " << *from_space_;
271     from_space_->GetMemMap()->Protect(PROT_NONE);
272   } else {
273     // If RosAllocSpace, we'll leave it as PROT_READ here so the
274     // rosaloc verification can read the metadata magic number and
275     // protect it with PROT_NONE later in FinishPhase().
276     VLOG(heap) << "Protecting from_space_ with PROT_READ : " << *from_space_;
277     from_space_->GetMemMap()->Protect(PROT_READ);
278   }
279   heap_->PreSweepingGcVerification(this);
280   if (swap_semi_spaces_) {
281     heap_->SwapSemiSpaces();
282   }
283 }
284 
285 class SemiSpaceScanObjectVisitor {
286  public:
SemiSpaceScanObjectVisitor(SemiSpace * ss)287   explicit SemiSpaceScanObjectVisitor(SemiSpace* ss) : semi_space_(ss) {}
operator ()(Object * obj) const288   void operator()(Object* obj) const REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_) {
289     DCHECK(obj != nullptr);
290     semi_space_->ScanObject(obj);
291   }
292  private:
293   SemiSpace* const semi_space_;
294 };
295 
296 // Used to verify that there's no references to the from-space.
297 class SemiSpaceVerifyNoFromSpaceReferencesVisitor {
298  public:
SemiSpaceVerifyNoFromSpaceReferencesVisitor(space::ContinuousMemMapAllocSpace * from_space)299   explicit SemiSpaceVerifyNoFromSpaceReferencesVisitor(space::ContinuousMemMapAllocSpace* from_space) :
300       from_space_(from_space) {}
301 
operator ()(Object * obj,MemberOffset offset,bool) const302   void operator()(Object* obj, MemberOffset offset, bool /* is_static */) const
303       SHARED_REQUIRES(Locks::mutator_lock_) ALWAYS_INLINE {
304     mirror::Object* ref = obj->GetFieldObject<mirror::Object>(offset);
305     if (from_space_->HasAddress(ref)) {
306       Runtime::Current()->GetHeap()->DumpObject(LOG(INFO), obj);
307       LOG(FATAL) << ref << " found in from space";
308     }
309   }
310 
311   // TODO: Remove NO_THREAD_SAFETY_ANALYSIS when clang better understands visitors.
VisitRootIfNonNull(mirror::CompressedReference<mirror::Object> * root) const312   void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
313       NO_THREAD_SAFETY_ANALYSIS {
314     if (!root->IsNull()) {
315       VisitRoot(root);
316     }
317   }
318 
VisitRoot(mirror::CompressedReference<mirror::Object> * root) const319   void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
320       NO_THREAD_SAFETY_ANALYSIS {
321     if (kIsDebugBuild) {
322       Locks::mutator_lock_->AssertExclusiveHeld(Thread::Current());
323       Locks::heap_bitmap_lock_->AssertExclusiveHeld(Thread::Current());
324     }
325     CHECK(!from_space_->HasAddress(root->AsMirrorPtr()));
326   }
327 
328  private:
329   space::ContinuousMemMapAllocSpace* const from_space_;
330 };
331 
VerifyNoFromSpaceReferences(Object * obj)332 void SemiSpace::VerifyNoFromSpaceReferences(Object* obj) {
333   DCHECK(!from_space_->HasAddress(obj)) << "Scanning object " << obj << " in from space";
334   SemiSpaceVerifyNoFromSpaceReferencesVisitor visitor(from_space_);
335   obj->VisitReferences(visitor, VoidFunctor());
336 }
337 
338 class SemiSpaceVerifyNoFromSpaceReferencesObjectVisitor {
339  public:
SemiSpaceVerifyNoFromSpaceReferencesObjectVisitor(SemiSpace * ss)340   explicit SemiSpaceVerifyNoFromSpaceReferencesObjectVisitor(SemiSpace* ss) : semi_space_(ss) {}
operator ()(Object * obj) const341   void operator()(Object* obj) const
342       SHARED_REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
343     DCHECK(obj != nullptr);
344     semi_space_->VerifyNoFromSpaceReferences(obj);
345   }
346 
347  private:
348   SemiSpace* const semi_space_;
349 };
350 
MarkReachableObjects()351 void SemiSpace::MarkReachableObjects() {
352   TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
353   {
354     TimingLogger::ScopedTiming t2("MarkStackAsLive", GetTimings());
355     accounting::ObjectStack* live_stack = heap_->GetLiveStack();
356     heap_->MarkAllocStackAsLive(live_stack);
357     live_stack->Reset();
358   }
359   for (auto& space : heap_->GetContinuousSpaces()) {
360     // If the space is immune then we need to mark the references to other spaces.
361     accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space);
362     if (table != nullptr) {
363       // TODO: Improve naming.
364       TimingLogger::ScopedTiming t2(
365           space->IsZygoteSpace() ? "UpdateAndMarkZygoteModUnionTable" :
366                                    "UpdateAndMarkImageModUnionTable",
367                                    GetTimings());
368       table->UpdateAndMarkReferences(this);
369       DCHECK(GetHeap()->FindRememberedSetFromSpace(space) == nullptr);
370     } else if ((space->IsImageSpace() || collect_from_space_only_) &&
371                space->GetLiveBitmap() != nullptr) {
372       // If the space has no mod union table (the non-moving space, app image spaces, main spaces
373       // when the bump pointer space only collection is enabled,) then we need to scan its live
374       // bitmap or dirty cards as roots (including the objects on the live stack which have just
375       // marked in the live bitmap above in MarkAllocStackAsLive().)
376       accounting::RememberedSet* rem_set = GetHeap()->FindRememberedSetFromSpace(space);
377       if (!space->IsImageSpace()) {
378         DCHECK(space == heap_->GetNonMovingSpace() || space == heap_->GetPrimaryFreeListSpace())
379             << "Space " << space->GetName() << " "
380             << "generational_=" << generational_ << " "
381             << "collect_from_space_only_=" << collect_from_space_only_;
382         // App images currently do not have remembered sets.
383         DCHECK_EQ(kUseRememberedSet, rem_set != nullptr);
384       } else {
385         DCHECK(rem_set == nullptr);
386       }
387       if (rem_set != nullptr) {
388         TimingLogger::ScopedTiming t2("UpdateAndMarkRememberedSet", GetTimings());
389         rem_set->UpdateAndMarkReferences(from_space_, this);
390       } else {
391         TimingLogger::ScopedTiming t2("VisitLiveBits", GetTimings());
392         accounting::ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap();
393         SemiSpaceScanObjectVisitor visitor(this);
394         live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()),
395                                       reinterpret_cast<uintptr_t>(space->End()),
396                                       visitor);
397       }
398       if (kIsDebugBuild) {
399         // Verify that there are no from-space references that
400         // remain in the space, that is, the remembered set (and the
401         // card table) didn't miss any from-space references in the
402         // space.
403         accounting::ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap();
404         SemiSpaceVerifyNoFromSpaceReferencesObjectVisitor visitor(this);
405         live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()),
406                                       reinterpret_cast<uintptr_t>(space->End()),
407                                       visitor);
408       }
409     }
410   }
411 
412   CHECK_EQ(is_large_object_space_immune_, collect_from_space_only_);
413   space::LargeObjectSpace* los = GetHeap()->GetLargeObjectsSpace();
414   if (is_large_object_space_immune_ && los != nullptr) {
415     TimingLogger::ScopedTiming t2("VisitLargeObjects", GetTimings());
416     DCHECK(collect_from_space_only_);
417     // Delay copying the live set to the marked set until here from
418     // BindBitmaps() as the large objects on the allocation stack may
419     // be newly added to the live set above in MarkAllocStackAsLive().
420     los->CopyLiveToMarked();
421 
422     // When the large object space is immune, we need to scan the
423     // large object space as roots as they contain references to their
424     // classes (primitive array classes) that could move though they
425     // don't contain any other references.
426     accounting::LargeObjectBitmap* large_live_bitmap = los->GetLiveBitmap();
427     SemiSpaceScanObjectVisitor visitor(this);
428     large_live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(los->Begin()),
429                                         reinterpret_cast<uintptr_t>(los->End()),
430                                         visitor);
431   }
432   // Recursively process the mark stack.
433   ProcessMarkStack();
434 }
435 
ReclaimPhase()436 void SemiSpace::ReclaimPhase() {
437   TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
438   WriterMutexLock mu(self_, *Locks::heap_bitmap_lock_);
439   // Reclaim unmarked objects.
440   Sweep(false);
441   // Swap the live and mark bitmaps for each space which we modified space. This is an
442   // optimization that enables us to not clear live bits inside of the sweep. Only swaps unbound
443   // bitmaps.
444   SwapBitmaps();
445   // Unbind the live and mark bitmaps.
446   GetHeap()->UnBindBitmaps();
447   if (saved_bytes_ > 0) {
448     VLOG(heap) << "Avoided dirtying " << PrettySize(saved_bytes_);
449   }
450   if (generational_) {
451     // Record the end (top) of the to space so we can distinguish
452     // between objects that were allocated since the last GC and the
453     // older objects.
454     last_gc_to_space_end_ = to_space_->End();
455   }
456 }
457 
ResizeMarkStack(size_t new_size)458 void SemiSpace::ResizeMarkStack(size_t new_size) {
459   std::vector<StackReference<Object>> temp(mark_stack_->Begin(), mark_stack_->End());
460   CHECK_LE(mark_stack_->Size(), new_size);
461   mark_stack_->Resize(new_size);
462   for (auto& obj : temp) {
463     mark_stack_->PushBack(obj.AsMirrorPtr());
464   }
465 }
466 
MarkStackPush(Object * obj)467 inline void SemiSpace::MarkStackPush(Object* obj) {
468   if (UNLIKELY(mark_stack_->Size() >= mark_stack_->Capacity())) {
469     ResizeMarkStack(mark_stack_->Capacity() * 2);
470   }
471   // The object must be pushed on to the mark stack.
472   mark_stack_->PushBack(obj);
473 }
474 
CopyAvoidingDirtyingPages(void * dest,const void * src,size_t size)475 static inline size_t CopyAvoidingDirtyingPages(void* dest, const void* src, size_t size) {
476   if (LIKELY(size <= static_cast<size_t>(kPageSize))) {
477     // We will dirty the current page and somewhere in the middle of the next page. This means
478     // that the next object copied will also dirty that page.
479     // TODO: Worth considering the last object copied? We may end up dirtying one page which is
480     // not necessary per GC.
481     memcpy(dest, src, size);
482     return 0;
483   }
484   size_t saved_bytes = 0;
485   uint8_t* byte_dest = reinterpret_cast<uint8_t*>(dest);
486   if (kIsDebugBuild) {
487     for (size_t i = 0; i < size; ++i) {
488       CHECK_EQ(byte_dest[i], 0U);
489     }
490   }
491   // Process the start of the page. The page must already be dirty, don't bother with checking.
492   const uint8_t* byte_src = reinterpret_cast<const uint8_t*>(src);
493   const uint8_t* limit = byte_src + size;
494   size_t page_remain = AlignUp(byte_dest, kPageSize) - byte_dest;
495   // Copy the bytes until the start of the next page.
496   memcpy(dest, src, page_remain);
497   byte_src += page_remain;
498   byte_dest += page_remain;
499   DCHECK_ALIGNED(reinterpret_cast<uintptr_t>(byte_dest), kPageSize);
500   DCHECK_ALIGNED(reinterpret_cast<uintptr_t>(byte_dest), sizeof(uintptr_t));
501   DCHECK_ALIGNED(reinterpret_cast<uintptr_t>(byte_src), sizeof(uintptr_t));
502   while (byte_src + kPageSize < limit) {
503     bool all_zero = true;
504     uintptr_t* word_dest = reinterpret_cast<uintptr_t*>(byte_dest);
505     const uintptr_t* word_src = reinterpret_cast<const uintptr_t*>(byte_src);
506     for (size_t i = 0; i < kPageSize / sizeof(*word_src); ++i) {
507       // Assumes the destination of the copy is all zeros.
508       if (word_src[i] != 0) {
509         all_zero = false;
510         word_dest[i] = word_src[i];
511       }
512     }
513     if (all_zero) {
514       // Avoided copying into the page since it was all zeros.
515       saved_bytes += kPageSize;
516     }
517     byte_src += kPageSize;
518     byte_dest += kPageSize;
519   }
520   // Handle the part of the page at the end.
521   memcpy(byte_dest, byte_src, limit - byte_src);
522   return saved_bytes;
523 }
524 
MarkNonForwardedObject(mirror::Object * obj)525 mirror::Object* SemiSpace::MarkNonForwardedObject(mirror::Object* obj) {
526   const size_t object_size = obj->SizeOf();
527   size_t bytes_allocated, dummy;
528   mirror::Object* forward_address = nullptr;
529   if (generational_ && reinterpret_cast<uint8_t*>(obj) < last_gc_to_space_end_) {
530     // If it's allocated before the last GC (older), move
531     // (pseudo-promote) it to the main free list space (as sort
532     // of an old generation.)
533     forward_address = promo_dest_space_->AllocThreadUnsafe(self_, object_size, &bytes_allocated,
534                                                            nullptr, &dummy);
535     if (UNLIKELY(forward_address == nullptr)) {
536       // If out of space, fall back to the to-space.
537       forward_address = to_space_->AllocThreadUnsafe(self_, object_size, &bytes_allocated, nullptr,
538                                                      &dummy);
539       // No logic for marking the bitmap, so it must be null.
540       DCHECK(to_space_live_bitmap_ == nullptr);
541     } else {
542       bytes_promoted_ += bytes_allocated;
543       // Dirty the card at the destionation as it may contain
544       // references (including the class pointer) to the bump pointer
545       // space.
546       GetHeap()->WriteBarrierEveryFieldOf(forward_address);
547       // Handle the bitmaps marking.
548       accounting::ContinuousSpaceBitmap* live_bitmap = promo_dest_space_->GetLiveBitmap();
549       DCHECK(live_bitmap != nullptr);
550       accounting::ContinuousSpaceBitmap* mark_bitmap = promo_dest_space_->GetMarkBitmap();
551       DCHECK(mark_bitmap != nullptr);
552       DCHECK(!live_bitmap->Test(forward_address));
553       if (collect_from_space_only_) {
554         // If collecting the bump pointer spaces only, live_bitmap == mark_bitmap.
555         DCHECK_EQ(live_bitmap, mark_bitmap);
556 
557         // If a bump pointer space only collection, delay the live
558         // bitmap marking of the promoted object until it's popped off
559         // the mark stack (ProcessMarkStack()). The rationale: we may
560         // be in the middle of scanning the objects in the promo
561         // destination space for
562         // non-moving-space-to-bump-pointer-space references by
563         // iterating over the marked bits of the live bitmap
564         // (MarkReachableObjects()). If we don't delay it (and instead
565         // mark the promoted object here), the above promo destination
566         // space scan could encounter the just-promoted object and
567         // forward the references in the promoted object's fields even
568         // through it is pushed onto the mark stack. If this happens,
569         // the promoted object would be in an inconsistent state, that
570         // is, it's on the mark stack (gray) but its fields are
571         // already forwarded (black), which would cause a
572         // DCHECK(!to_space_->HasAddress(obj)) failure below.
573       } else {
574         // Mark forward_address on the live bit map.
575         live_bitmap->Set(forward_address);
576         // Mark forward_address on the mark bit map.
577         DCHECK(!mark_bitmap->Test(forward_address));
578         mark_bitmap->Set(forward_address);
579       }
580     }
581   } else {
582     // If it's allocated after the last GC (younger), copy it to the to-space.
583     forward_address = to_space_->AllocThreadUnsafe(self_, object_size, &bytes_allocated, nullptr,
584                                                    &dummy);
585     if (forward_address != nullptr && to_space_live_bitmap_ != nullptr) {
586       to_space_live_bitmap_->Set(forward_address);
587     }
588   }
589   // If it's still null, attempt to use the fallback space.
590   if (UNLIKELY(forward_address == nullptr)) {
591     forward_address = fallback_space_->AllocThreadUnsafe(self_, object_size, &bytes_allocated,
592                                                          nullptr, &dummy);
593     CHECK(forward_address != nullptr) << "Out of memory in the to-space and fallback space.";
594     accounting::ContinuousSpaceBitmap* bitmap = fallback_space_->GetLiveBitmap();
595     if (bitmap != nullptr) {
596       bitmap->Set(forward_address);
597     }
598   }
599   ++objects_moved_;
600   bytes_moved_ += bytes_allocated;
601   // Copy over the object and add it to the mark stack since we still need to update its
602   // references.
603   saved_bytes_ +=
604       CopyAvoidingDirtyingPages(reinterpret_cast<void*>(forward_address), obj, object_size);
605   if (kUseBakerOrBrooksReadBarrier) {
606     obj->AssertReadBarrierPointer();
607     if (kUseBrooksReadBarrier) {
608       DCHECK_EQ(forward_address->GetReadBarrierPointer(), obj);
609       forward_address->SetReadBarrierPointer(forward_address);
610     }
611     forward_address->AssertReadBarrierPointer();
612   }
613   DCHECK(to_space_->HasAddress(forward_address) ||
614          fallback_space_->HasAddress(forward_address) ||
615          (generational_ && promo_dest_space_->HasAddress(forward_address)))
616       << forward_address << "\n" << GetHeap()->DumpSpaces();
617   return forward_address;
618 }
619 
MarkObject(mirror::Object * root)620 mirror::Object* SemiSpace::MarkObject(mirror::Object* root) {
621   auto ref = StackReference<mirror::Object>::FromMirrorPtr(root);
622   MarkObjectIfNotInToSpace(&ref);
623   return ref.AsMirrorPtr();
624 }
625 
MarkHeapReference(mirror::HeapReference<mirror::Object> * obj_ptr)626 void SemiSpace::MarkHeapReference(mirror::HeapReference<mirror::Object>* obj_ptr) {
627   MarkObject(obj_ptr);
628 }
629 
VisitRoots(mirror::Object *** roots,size_t count,const RootInfo & info ATTRIBUTE_UNUSED)630 void SemiSpace::VisitRoots(mirror::Object*** roots, size_t count,
631                            const RootInfo& info ATTRIBUTE_UNUSED) {
632   for (size_t i = 0; i < count; ++i) {
633     auto* root = roots[i];
634     auto ref = StackReference<mirror::Object>::FromMirrorPtr(*root);
635     // The root can be in the to-space since we may visit the declaring class of an ArtMethod
636     // multiple times if it is on the call stack.
637     MarkObjectIfNotInToSpace(&ref);
638     if (*root != ref.AsMirrorPtr()) {
639       *root = ref.AsMirrorPtr();
640     }
641   }
642 }
643 
VisitRoots(mirror::CompressedReference<mirror::Object> ** roots,size_t count,const RootInfo & info ATTRIBUTE_UNUSED)644 void SemiSpace::VisitRoots(mirror::CompressedReference<mirror::Object>** roots, size_t count,
645                            const RootInfo& info ATTRIBUTE_UNUSED) {
646   for (size_t i = 0; i < count; ++i) {
647     MarkObjectIfNotInToSpace(roots[i]);
648   }
649 }
650 
651 // Marks all objects in the root set.
MarkRoots()652 void SemiSpace::MarkRoots() {
653   TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
654   Runtime::Current()->VisitRoots(this);
655 }
656 
SweepSystemWeaks()657 void SemiSpace::SweepSystemWeaks() {
658   TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
659   Runtime::Current()->SweepSystemWeaks(this);
660 }
661 
ShouldSweepSpace(space::ContinuousSpace * space) const662 bool SemiSpace::ShouldSweepSpace(space::ContinuousSpace* space) const {
663   return space != from_space_ && space != to_space_;
664 }
665 
Sweep(bool swap_bitmaps)666 void SemiSpace::Sweep(bool swap_bitmaps) {
667   TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
668   DCHECK(mark_stack_->IsEmpty());
669   for (const auto& space : GetHeap()->GetContinuousSpaces()) {
670     if (space->IsContinuousMemMapAllocSpace()) {
671       space::ContinuousMemMapAllocSpace* alloc_space = space->AsContinuousMemMapAllocSpace();
672       if (!ShouldSweepSpace(alloc_space)) {
673         continue;
674       }
675       TimingLogger::ScopedTiming split(
676           alloc_space->IsZygoteSpace() ? "SweepZygoteSpace" : "SweepAllocSpace", GetTimings());
677       RecordFree(alloc_space->Sweep(swap_bitmaps));
678     }
679   }
680   if (!is_large_object_space_immune_) {
681     SweepLargeObjects(swap_bitmaps);
682   }
683 }
684 
SweepLargeObjects(bool swap_bitmaps)685 void SemiSpace::SweepLargeObjects(bool swap_bitmaps) {
686   DCHECK(!is_large_object_space_immune_);
687   space::LargeObjectSpace* los = heap_->GetLargeObjectsSpace();
688   if (los != nullptr) {
689     TimingLogger::ScopedTiming split("SweepLargeObjects", GetTimings());
690     RecordFreeLOS(los->Sweep(swap_bitmaps));
691   }
692 }
693 
694 // Process the "referent" field in a java.lang.ref.Reference.  If the referent has not yet been
695 // marked, put it on the appropriate list in the heap for later processing.
DelayReferenceReferent(mirror::Class * klass,mirror::Reference * reference)696 void SemiSpace::DelayReferenceReferent(mirror::Class* klass, mirror::Reference* reference) {
697   heap_->GetReferenceProcessor()->DelayReferenceReferent(klass, reference, this);
698 }
699 
700 class SemiSpaceMarkObjectVisitor {
701  public:
SemiSpaceMarkObjectVisitor(SemiSpace * collector)702   explicit SemiSpaceMarkObjectVisitor(SemiSpace* collector) : collector_(collector) {
703   }
704 
operator ()(Object * obj,MemberOffset offset,bool) const705   void operator()(Object* obj, MemberOffset offset, bool /* is_static */) const ALWAYS_INLINE
706       REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_) {
707     // Object was already verified when we scanned it.
708     collector_->MarkObject(obj->GetFieldObjectReferenceAddr<kVerifyNone>(offset));
709   }
710 
operator ()(mirror::Class * klass,mirror::Reference * ref) const711   void operator()(mirror::Class* klass, mirror::Reference* ref) const
712       REQUIRES(Locks::mutator_lock_, Locks::heap_bitmap_lock_) {
713     collector_->DelayReferenceReferent(klass, ref);
714   }
715 
716   // TODO: Remove NO_THREAD_SAFETY_ANALYSIS when clang better understands visitors.
VisitRootIfNonNull(mirror::CompressedReference<mirror::Object> * root) const717   void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
718       NO_THREAD_SAFETY_ANALYSIS {
719     if (!root->IsNull()) {
720       VisitRoot(root);
721     }
722   }
723 
VisitRoot(mirror::CompressedReference<mirror::Object> * root) const724   void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
725       NO_THREAD_SAFETY_ANALYSIS {
726     if (kIsDebugBuild) {
727       Locks::mutator_lock_->AssertExclusiveHeld(Thread::Current());
728       Locks::heap_bitmap_lock_->AssertExclusiveHeld(Thread::Current());
729     }
730     // We may visit the same root multiple times, so avoid marking things in the to-space since
731     // this is not handled by the GC.
732     collector_->MarkObjectIfNotInToSpace(root);
733   }
734 
735  private:
736   SemiSpace* const collector_;
737 };
738 
739 // Visit all of the references of an object and update.
ScanObject(Object * obj)740 void SemiSpace::ScanObject(Object* obj) {
741   DCHECK(!from_space_->HasAddress(obj)) << "Scanning object " << obj << " in from space";
742   SemiSpaceMarkObjectVisitor visitor(this);
743   obj->VisitReferences(visitor, visitor);
744 }
745 
746 // Scan anything that's on the mark stack.
ProcessMarkStack()747 void SemiSpace::ProcessMarkStack() {
748   TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
749   accounting::ContinuousSpaceBitmap* live_bitmap = nullptr;
750   if (collect_from_space_only_) {
751     // If a bump pointer space only collection (and the promotion is
752     // enabled,) we delay the live-bitmap marking of promoted objects
753     // from MarkObject() until this function.
754     live_bitmap = promo_dest_space_->GetLiveBitmap();
755     DCHECK(live_bitmap != nullptr);
756     accounting::ContinuousSpaceBitmap* mark_bitmap = promo_dest_space_->GetMarkBitmap();
757     DCHECK(mark_bitmap != nullptr);
758     DCHECK_EQ(live_bitmap, mark_bitmap);
759   }
760   while (!mark_stack_->IsEmpty()) {
761     Object* obj = mark_stack_->PopBack();
762     if (collect_from_space_only_ && promo_dest_space_->HasAddress(obj)) {
763       // obj has just been promoted. Mark the live bitmap for it,
764       // which is delayed from MarkObject().
765       DCHECK(!live_bitmap->Test(obj));
766       live_bitmap->Set(obj);
767     }
768     ScanObject(obj);
769   }
770 }
771 
IsMarked(mirror::Object * obj)772 mirror::Object* SemiSpace::IsMarked(mirror::Object* obj) {
773   // All immune objects are assumed marked.
774   if (from_space_->HasAddress(obj)) {
775     // Returns either the forwarding address or null.
776     return GetForwardingAddressInFromSpace(obj);
777   } else if (collect_from_space_only_ ||
778              immune_spaces_.IsInImmuneRegion(obj) ||
779              to_space_->HasAddress(obj)) {
780     return obj;  // Already forwarded, must be marked.
781   }
782   return mark_bitmap_->Test(obj) ? obj : nullptr;
783 }
784 
IsMarkedHeapReference(mirror::HeapReference<mirror::Object> * object)785 bool SemiSpace::IsMarkedHeapReference(mirror::HeapReference<mirror::Object>* object) {
786   mirror::Object* obj = object->AsMirrorPtr();
787   mirror::Object* new_obj = IsMarked(obj);
788   if (new_obj == nullptr) {
789     return false;
790   }
791   if (new_obj != obj) {
792     // Write barrier is not necessary since it still points to the same object, just at a different
793     // address.
794     object->Assign(new_obj);
795   }
796   return true;
797 }
798 
SetToSpace(space::ContinuousMemMapAllocSpace * to_space)799 void SemiSpace::SetToSpace(space::ContinuousMemMapAllocSpace* to_space) {
800   DCHECK(to_space != nullptr);
801   to_space_ = to_space;
802 }
803 
SetFromSpace(space::ContinuousMemMapAllocSpace * from_space)804 void SemiSpace::SetFromSpace(space::ContinuousMemMapAllocSpace* from_space) {
805   DCHECK(from_space != nullptr);
806   from_space_ = from_space;
807 }
808 
FinishPhase()809 void SemiSpace::FinishPhase() {
810   TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
811   if (kProtectFromSpace && from_space_->IsRosAllocSpace()) {
812     VLOG(heap) << "Protecting from_space_ with PROT_NONE : " << *from_space_;
813     from_space_->GetMemMap()->Protect(PROT_NONE);
814   }
815   // Null the "to" and "from" spaces since compacting from one to the other isn't valid until
816   // further action is done by the heap.
817   to_space_ = nullptr;
818   from_space_ = nullptr;
819   CHECK(mark_stack_->IsEmpty());
820   mark_stack_->Reset();
821   space::LargeObjectSpace* los = GetHeap()->GetLargeObjectsSpace();
822   if (generational_) {
823     // Decide whether to do a whole heap collection or a bump pointer
824     // only space collection at the next collection by updating
825     // collect_from_space_only_.
826     if (collect_from_space_only_) {
827       // Disable collect_from_space_only_ if the bytes promoted since the
828       // last whole heap collection or the large object bytes
829       // allocated exceeds a threshold.
830       bytes_promoted_since_last_whole_heap_collection_ += bytes_promoted_;
831       bool bytes_promoted_threshold_exceeded =
832           bytes_promoted_since_last_whole_heap_collection_ >= kBytesPromotedThreshold;
833       uint64_t current_los_bytes_allocated = los != nullptr ? los->GetBytesAllocated() : 0U;
834       uint64_t last_los_bytes_allocated =
835           large_object_bytes_allocated_at_last_whole_heap_collection_;
836       bool large_object_bytes_threshold_exceeded =
837           current_los_bytes_allocated >=
838           last_los_bytes_allocated + kLargeObjectBytesAllocatedThreshold;
839       if (bytes_promoted_threshold_exceeded || large_object_bytes_threshold_exceeded) {
840         collect_from_space_only_ = false;
841       }
842     } else {
843       // Reset the counters.
844       bytes_promoted_since_last_whole_heap_collection_ = bytes_promoted_;
845       large_object_bytes_allocated_at_last_whole_heap_collection_ =
846           los != nullptr ? los->GetBytesAllocated() : 0U;
847       collect_from_space_only_ = true;
848     }
849   }
850   // Clear all of the spaces' mark bitmaps.
851   WriterMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_);
852   heap_->ClearMarkedObjects();
853 }
854 
RevokeAllThreadLocalBuffers()855 void SemiSpace::RevokeAllThreadLocalBuffers() {
856   TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
857   GetHeap()->RevokeAllThreadLocalBuffers();
858 }
859 
860 }  // namespace collector
861 }  // namespace gc
862 }  // namespace art
863