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 #ifndef ART_RUNTIME_GC_HEAP_INL_H_
18 #define ART_RUNTIME_GC_HEAP_INL_H_
19 
20 #include "heap.h"
21 
22 #include "base/time_utils.h"
23 #include "debugger.h"
24 #include "gc/accounting/card_table-inl.h"
25 #include "gc/collector/semi_space.h"
26 #include "gc/space/bump_pointer_space-inl.h"
27 #include "gc/space/dlmalloc_space-inl.h"
28 #include "gc/space/large_object_space.h"
29 #include "gc/space/region_space-inl.h"
30 #include "gc/space/rosalloc_space-inl.h"
31 #include "runtime.h"
32 #include "handle_scope-inl.h"
33 #include "thread-inl.h"
34 #include "utils.h"
35 #include "verify_object-inl.h"
36 
37 namespace art {
38 namespace gc {
39 
40 template <bool kInstrumented, bool kCheckLargeObject, typename PreFenceVisitor>
AllocObjectWithAllocator(Thread * self,mirror::Class * klass,size_t byte_count,AllocatorType allocator,const PreFenceVisitor & pre_fence_visitor)41 inline mirror::Object* Heap::AllocObjectWithAllocator(Thread* self, mirror::Class* klass,
42                                                       size_t byte_count, AllocatorType allocator,
43                                                       const PreFenceVisitor& pre_fence_visitor) {
44   if (kIsDebugBuild) {
45     CheckPreconditionsForAllocObject(klass, byte_count);
46     // Since allocation can cause a GC which will need to SuspendAll, make sure all allocations are
47     // done in the runnable state where suspension is expected.
48     CHECK_EQ(self->GetState(), kRunnable);
49     self->AssertThreadSuspensionIsAllowable();
50   }
51   // Need to check that we arent the large object allocator since the large object allocation code
52   // path this function. If we didn't check we would have an infinite loop.
53   mirror::Object* obj;
54   if (kCheckLargeObject && UNLIKELY(ShouldAllocLargeObject(klass, byte_count))) {
55     obj = AllocLargeObject<kInstrumented, PreFenceVisitor>(self, &klass, byte_count,
56                                                            pre_fence_visitor);
57     if (obj != nullptr) {
58       return obj;
59     } else {
60       // There should be an OOM exception, since we are retrying, clear it.
61       self->ClearException();
62     }
63     // If the large object allocation failed, try to use the normal spaces (main space,
64     // non moving space). This can happen if there is significant virtual address space
65     // fragmentation.
66   }
67   AllocationTimer alloc_timer(this, &obj);
68   // bytes allocated for the (individual) object.
69   size_t bytes_allocated;
70   size_t usable_size;
71   size_t new_num_bytes_allocated = 0;
72   if (allocator == kAllocatorTypeTLAB || allocator == kAllocatorTypeRegionTLAB) {
73     byte_count = RoundUp(byte_count, space::BumpPointerSpace::kAlignment);
74   }
75   // If we have a thread local allocation we don't need to update bytes allocated.
76   if ((allocator == kAllocatorTypeTLAB || allocator == kAllocatorTypeRegionTLAB) &&
77       byte_count <= self->TlabSize()) {
78     obj = self->AllocTlab(byte_count);
79     DCHECK(obj != nullptr) << "AllocTlab can't fail";
80     obj->SetClass(klass);
81     if (kUseBakerOrBrooksReadBarrier) {
82       if (kUseBrooksReadBarrier) {
83         obj->SetReadBarrierPointer(obj);
84       }
85       obj->AssertReadBarrierPointer();
86     }
87     bytes_allocated = byte_count;
88     usable_size = bytes_allocated;
89     pre_fence_visitor(obj, usable_size);
90     QuasiAtomic::ThreadFenceForConstructor();
91   } else if (!kInstrumented && allocator == kAllocatorTypeRosAlloc &&
92              (obj = rosalloc_space_->AllocThreadLocal(self, byte_count, &bytes_allocated)) &&
93              LIKELY(obj != nullptr)) {
94     DCHECK(!running_on_valgrind_);
95     obj->SetClass(klass);
96     if (kUseBakerOrBrooksReadBarrier) {
97       if (kUseBrooksReadBarrier) {
98         obj->SetReadBarrierPointer(obj);
99       }
100       obj->AssertReadBarrierPointer();
101     }
102     usable_size = bytes_allocated;
103     pre_fence_visitor(obj, usable_size);
104     QuasiAtomic::ThreadFenceForConstructor();
105   } else {
106     // bytes allocated that takes bulk thread-local buffer allocations into account.
107     size_t bytes_tl_bulk_allocated = 0;
108     obj = TryToAllocate<kInstrumented, false>(self, allocator, byte_count, &bytes_allocated,
109                                               &usable_size, &bytes_tl_bulk_allocated);
110     if (UNLIKELY(obj == nullptr)) {
111       bool is_current_allocator = allocator == GetCurrentAllocator();
112       obj = AllocateInternalWithGc(self, allocator, byte_count, &bytes_allocated, &usable_size,
113                                    &bytes_tl_bulk_allocated, &klass);
114       if (obj == nullptr) {
115         bool after_is_current_allocator = allocator == GetCurrentAllocator();
116         // If there is a pending exception, fail the allocation right away since the next one
117         // could cause OOM and abort the runtime.
118         if (!self->IsExceptionPending() && is_current_allocator && !after_is_current_allocator) {
119           // If the allocator changed, we need to restart the allocation.
120           return AllocObject<kInstrumented>(self, klass, byte_count, pre_fence_visitor);
121         }
122         return nullptr;
123       }
124     }
125     DCHECK_GT(bytes_allocated, 0u);
126     DCHECK_GT(usable_size, 0u);
127     obj->SetClass(klass);
128     if (kUseBakerOrBrooksReadBarrier) {
129       if (kUseBrooksReadBarrier) {
130         obj->SetReadBarrierPointer(obj);
131       }
132       obj->AssertReadBarrierPointer();
133     }
134     if (collector::SemiSpace::kUseRememberedSet && UNLIKELY(allocator == kAllocatorTypeNonMoving)) {
135       // (Note this if statement will be constant folded away for the
136       // fast-path quick entry points.) Because SetClass() has no write
137       // barrier, if a non-moving space allocation, we need a write
138       // barrier as the class pointer may point to the bump pointer
139       // space (where the class pointer is an "old-to-young" reference,
140       // though rare) under the GSS collector with the remembered set
141       // enabled. We don't need this for kAllocatorTypeRosAlloc/DlMalloc
142       // cases because we don't directly allocate into the main alloc
143       // space (besides promotions) under the SS/GSS collector.
144       WriteBarrierField(obj, mirror::Object::ClassOffset(), klass);
145     }
146     pre_fence_visitor(obj, usable_size);
147     new_num_bytes_allocated = static_cast<size_t>(
148         num_bytes_allocated_.FetchAndAddSequentiallyConsistent(bytes_tl_bulk_allocated))
149         + bytes_tl_bulk_allocated;
150   }
151   if (kIsDebugBuild && Runtime::Current()->IsStarted()) {
152     CHECK_LE(obj->SizeOf(), usable_size);
153   }
154   // TODO: Deprecate.
155   if (kInstrumented) {
156     if (Runtime::Current()->HasStatsEnabled()) {
157       RuntimeStats* thread_stats = self->GetStats();
158       ++thread_stats->allocated_objects;
159       thread_stats->allocated_bytes += bytes_allocated;
160       RuntimeStats* global_stats = Runtime::Current()->GetStats();
161       ++global_stats->allocated_objects;
162       global_stats->allocated_bytes += bytes_allocated;
163     }
164   } else {
165     DCHECK(!Runtime::Current()->HasStatsEnabled());
166   }
167   if (AllocatorHasAllocationStack(allocator)) {
168     PushOnAllocationStack(self, &obj);
169   }
170   if (kInstrumented) {
171     if (Dbg::IsAllocTrackingEnabled()) {
172       Dbg::RecordAllocation(self, klass, bytes_allocated);
173     }
174   } else {
175     DCHECK(!Dbg::IsAllocTrackingEnabled());
176   }
177   if (kInstrumented) {
178     if (gc_stress_mode_) {
179       CheckGcStressMode(self, &obj);
180     }
181   } else {
182     DCHECK(!gc_stress_mode_);
183   }
184   // IsConcurrentGc() isn't known at compile time so we can optimize by not checking it for
185   // the BumpPointer or TLAB allocators. This is nice since it allows the entire if statement to be
186   // optimized out. And for the other allocators, AllocatorMayHaveConcurrentGC is a constant since
187   // the allocator_type should be constant propagated.
188   if (AllocatorMayHaveConcurrentGC(allocator) && IsGcConcurrent()) {
189     CheckConcurrentGC(self, new_num_bytes_allocated, &obj);
190   }
191   VerifyObject(obj);
192   self->VerifyStack();
193   return obj;
194 }
195 
196 // The size of a thread-local allocation stack in the number of references.
197 static constexpr size_t kThreadLocalAllocationStackSize = 128;
198 
PushOnAllocationStack(Thread * self,mirror::Object ** obj)199 inline void Heap::PushOnAllocationStack(Thread* self, mirror::Object** obj) {
200   if (kUseThreadLocalAllocationStack) {
201     if (UNLIKELY(!self->PushOnThreadLocalAllocationStack(*obj))) {
202       PushOnThreadLocalAllocationStackWithInternalGC(self, obj);
203     }
204   } else if (UNLIKELY(!allocation_stack_->AtomicPushBack(*obj))) {
205     PushOnAllocationStackWithInternalGC(self, obj);
206   }
207 }
208 
209 template <bool kInstrumented, typename PreFenceVisitor>
AllocLargeObject(Thread * self,mirror::Class ** klass,size_t byte_count,const PreFenceVisitor & pre_fence_visitor)210 inline mirror::Object* Heap::AllocLargeObject(Thread* self, mirror::Class** klass,
211                                               size_t byte_count,
212                                               const PreFenceVisitor& pre_fence_visitor) {
213   // Save and restore the class in case it moves.
214   StackHandleScope<1> hs(self);
215   auto klass_wrapper = hs.NewHandleWrapper(klass);
216   return AllocObjectWithAllocator<kInstrumented, false, PreFenceVisitor>(self, *klass, byte_count,
217                                                                          kAllocatorTypeLOS,
218                                                                          pre_fence_visitor);
219 }
220 
221 template <const bool kInstrumented, const bool kGrow>
TryToAllocate(Thread * self,AllocatorType allocator_type,size_t alloc_size,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)222 inline mirror::Object* Heap::TryToAllocate(Thread* self, AllocatorType allocator_type,
223                                            size_t alloc_size, size_t* bytes_allocated,
224                                            size_t* usable_size,
225                                            size_t* bytes_tl_bulk_allocated) {
226   if (allocator_type != kAllocatorTypeTLAB && allocator_type != kAllocatorTypeRegionTLAB &&
227       allocator_type != kAllocatorTypeRosAlloc &&
228       UNLIKELY(IsOutOfMemoryOnAllocation<kGrow>(allocator_type, alloc_size))) {
229     return nullptr;
230   }
231   mirror::Object* ret;
232   switch (allocator_type) {
233     case kAllocatorTypeBumpPointer: {
234       DCHECK(bump_pointer_space_ != nullptr);
235       alloc_size = RoundUp(alloc_size, space::BumpPointerSpace::kAlignment);
236       ret = bump_pointer_space_->AllocNonvirtual(alloc_size);
237       if (LIKELY(ret != nullptr)) {
238         *bytes_allocated = alloc_size;
239         *usable_size = alloc_size;
240         *bytes_tl_bulk_allocated = alloc_size;
241       }
242       break;
243     }
244     case kAllocatorTypeRosAlloc: {
245       if (kInstrumented && UNLIKELY(running_on_valgrind_)) {
246         // If running on valgrind, we should be using the instrumented path.
247         size_t max_bytes_tl_bulk_allocated = rosalloc_space_->MaxBytesBulkAllocatedFor(alloc_size);
248         if (UNLIKELY(IsOutOfMemoryOnAllocation<kGrow>(allocator_type,
249                                                       max_bytes_tl_bulk_allocated))) {
250           return nullptr;
251         }
252         ret = rosalloc_space_->Alloc(self, alloc_size, bytes_allocated, usable_size,
253                                      bytes_tl_bulk_allocated);
254       } else {
255         DCHECK(!running_on_valgrind_);
256         size_t max_bytes_tl_bulk_allocated =
257             rosalloc_space_->MaxBytesBulkAllocatedForNonvirtual(alloc_size);
258         if (UNLIKELY(IsOutOfMemoryOnAllocation<kGrow>(allocator_type,
259                                                       max_bytes_tl_bulk_allocated))) {
260           return nullptr;
261         }
262         if (!kInstrumented) {
263           DCHECK(!rosalloc_space_->CanAllocThreadLocal(self, alloc_size));
264         }
265         ret = rosalloc_space_->AllocNonvirtual(self, alloc_size, bytes_allocated, usable_size,
266                                                bytes_tl_bulk_allocated);
267       }
268       break;
269     }
270     case kAllocatorTypeDlMalloc: {
271       if (kInstrumented && UNLIKELY(running_on_valgrind_)) {
272         // If running on valgrind, we should be using the instrumented path.
273         ret = dlmalloc_space_->Alloc(self, alloc_size, bytes_allocated, usable_size,
274                                      bytes_tl_bulk_allocated);
275       } else {
276         DCHECK(!running_on_valgrind_);
277         ret = dlmalloc_space_->AllocNonvirtual(self, alloc_size, bytes_allocated, usable_size,
278                                                bytes_tl_bulk_allocated);
279       }
280       break;
281     }
282     case kAllocatorTypeNonMoving: {
283       ret = non_moving_space_->Alloc(self, alloc_size, bytes_allocated, usable_size,
284                                      bytes_tl_bulk_allocated);
285       break;
286     }
287     case kAllocatorTypeLOS: {
288       ret = large_object_space_->Alloc(self, alloc_size, bytes_allocated, usable_size,
289                                        bytes_tl_bulk_allocated);
290       // Note that the bump pointer spaces aren't necessarily next to
291       // the other continuous spaces like the non-moving alloc space or
292       // the zygote space.
293       DCHECK(ret == nullptr || large_object_space_->Contains(ret));
294       break;
295     }
296     case kAllocatorTypeTLAB: {
297       DCHECK_ALIGNED(alloc_size, space::BumpPointerSpace::kAlignment);
298       if (UNLIKELY(self->TlabSize() < alloc_size)) {
299         const size_t new_tlab_size = alloc_size + kDefaultTLABSize;
300         if (UNLIKELY(IsOutOfMemoryOnAllocation<kGrow>(allocator_type, new_tlab_size))) {
301           return nullptr;
302         }
303         // Try allocating a new thread local buffer, if the allocaiton fails the space must be
304         // full so return null.
305         if (!bump_pointer_space_->AllocNewTlab(self, new_tlab_size)) {
306           return nullptr;
307         }
308         *bytes_tl_bulk_allocated = new_tlab_size;
309       } else {
310         *bytes_tl_bulk_allocated = 0;
311       }
312       // The allocation can't fail.
313       ret = self->AllocTlab(alloc_size);
314       DCHECK(ret != nullptr);
315       *bytes_allocated = alloc_size;
316       *usable_size = alloc_size;
317       break;
318     }
319     case kAllocatorTypeRegion: {
320       DCHECK(region_space_ != nullptr);
321       alloc_size = RoundUp(alloc_size, space::RegionSpace::kAlignment);
322       ret = region_space_->AllocNonvirtual<false>(alloc_size, bytes_allocated, usable_size,
323                                                   bytes_tl_bulk_allocated);
324       break;
325     }
326     case kAllocatorTypeRegionTLAB: {
327       DCHECK(region_space_ != nullptr);
328       DCHECK_ALIGNED(alloc_size, space::RegionSpace::kAlignment);
329       if (UNLIKELY(self->TlabSize() < alloc_size)) {
330         if (space::RegionSpace::kRegionSize >= alloc_size) {
331           // Non-large. Check OOME for a tlab.
332           if (LIKELY(!IsOutOfMemoryOnAllocation<kGrow>(allocator_type, space::RegionSpace::kRegionSize))) {
333             // Try to allocate a tlab.
334             if (!region_space_->AllocNewTlab(self)) {
335               // Failed to allocate a tlab. Try non-tlab.
336               ret = region_space_->AllocNonvirtual<false>(alloc_size, bytes_allocated, usable_size,
337                                                           bytes_tl_bulk_allocated);
338               return ret;
339             }
340             *bytes_tl_bulk_allocated = space::RegionSpace::kRegionSize;
341             // Fall-through.
342           } else {
343             // Check OOME for a non-tlab allocation.
344             if (!IsOutOfMemoryOnAllocation<kGrow>(allocator_type, alloc_size)) {
345               ret = region_space_->AllocNonvirtual<false>(alloc_size, bytes_allocated, usable_size,
346                                                           bytes_tl_bulk_allocated);
347               return ret;
348             } else {
349               // Neither tlab or non-tlab works. Give up.
350               return nullptr;
351             }
352           }
353         } else {
354           // Large. Check OOME.
355           if (LIKELY(!IsOutOfMemoryOnAllocation<kGrow>(allocator_type, alloc_size))) {
356             ret = region_space_->AllocNonvirtual<false>(alloc_size, bytes_allocated, usable_size,
357                                                         bytes_tl_bulk_allocated);
358             return ret;
359           } else {
360             return nullptr;
361           }
362         }
363       } else {
364         *bytes_tl_bulk_allocated = 0;  // Allocated in an existing buffer.
365       }
366       // The allocation can't fail.
367       ret = self->AllocTlab(alloc_size);
368       DCHECK(ret != nullptr);
369       *bytes_allocated = alloc_size;
370       *usable_size = alloc_size;
371       break;
372     }
373     default: {
374       LOG(FATAL) << "Invalid allocator type";
375       ret = nullptr;
376     }
377   }
378   return ret;
379 }
380 
AllocationTimer(Heap * heap,mirror::Object ** allocated_obj_ptr)381 inline Heap::AllocationTimer::AllocationTimer(Heap* heap, mirror::Object** allocated_obj_ptr)
382     : heap_(heap), allocated_obj_ptr_(allocated_obj_ptr),
383       allocation_start_time_(kMeasureAllocationTime ? NanoTime() / kTimeAdjust : 0u) { }
384 
~AllocationTimer()385 inline Heap::AllocationTimer::~AllocationTimer() {
386   if (kMeasureAllocationTime) {
387     mirror::Object* allocated_obj = *allocated_obj_ptr_;
388     // Only if the allocation succeeded, record the time.
389     if (allocated_obj != nullptr) {
390       uint64_t allocation_end_time = NanoTime() / kTimeAdjust;
391       heap_->total_allocation_time_.FetchAndAddSequentiallyConsistent(allocation_end_time - allocation_start_time_);
392     }
393   }
394 }
395 
ShouldAllocLargeObject(mirror::Class * c,size_t byte_count)396 inline bool Heap::ShouldAllocLargeObject(mirror::Class* c, size_t byte_count) const {
397   // We need to have a zygote space or else our newly allocated large object can end up in the
398   // Zygote resulting in it being prematurely freed.
399   // We can only do this for primitive objects since large objects will not be within the card table
400   // range. This also means that we rely on SetClass not dirtying the object's card.
401   return byte_count >= large_object_threshold_ && (c->IsPrimitiveArray() || c->IsStringClass());
402 }
403 
404 template <bool kGrow>
IsOutOfMemoryOnAllocation(AllocatorType allocator_type,size_t alloc_size)405 inline bool Heap::IsOutOfMemoryOnAllocation(AllocatorType allocator_type, size_t alloc_size) {
406   size_t new_footprint = num_bytes_allocated_.LoadSequentiallyConsistent() + alloc_size;
407   if (UNLIKELY(new_footprint > max_allowed_footprint_)) {
408     if (UNLIKELY(new_footprint > growth_limit_)) {
409       return true;
410     }
411     if (!AllocatorMayHaveConcurrentGC(allocator_type) || !IsGcConcurrent()) {
412       if (!kGrow) {
413         return true;
414       }
415       // TODO: Grow for allocation is racy, fix it.
416       VLOG(heap) << "Growing heap from " << PrettySize(max_allowed_footprint_) << " to "
417           << PrettySize(new_footprint) << " for a " << PrettySize(alloc_size) << " allocation";
418       max_allowed_footprint_ = new_footprint;
419     }
420   }
421   return false;
422 }
423 
CheckConcurrentGC(Thread * self,size_t new_num_bytes_allocated,mirror::Object ** obj)424 inline void Heap::CheckConcurrentGC(Thread* self, size_t new_num_bytes_allocated,
425                                     mirror::Object** obj) {
426   if (UNLIKELY(new_num_bytes_allocated >= concurrent_start_bytes_)) {
427     RequestConcurrentGCAndSaveObject(self, false, obj);
428   }
429 }
430 
431 }  // namespace gc
432 }  // namespace art
433 
434 #endif  // ART_RUNTIME_GC_HEAP_INL_H_
435