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 "malloc_space.h"
18 
19 #include <ostream>
20 
21 #include "android-base/stringprintf.h"
22 
23 #include "base/logging.h"  // For VLOG
24 #include "base/mutex-inl.h"
25 #include "base/utils.h"
26 #include "gc/accounting/card_table-inl.h"
27 #include "gc/accounting/space_bitmap-inl.h"
28 #include "gc/heap.h"
29 #include "gc/space/space-inl.h"
30 #include "gc/space/zygote_space.h"
31 #include "handle_scope-inl.h"
32 #include "mirror/class-inl.h"
33 #include "mirror/object-inl.h"
34 #include "runtime.h"
35 #include "thread.h"
36 #include "thread_list.h"
37 
38 namespace art {
39 namespace gc {
40 namespace space {
41 
42 using android::base::StringPrintf;
43 
44 size_t MallocSpace::bitmap_index_ = 0;
45 
MallocSpace(const std::string & name,MemMap && mem_map,uint8_t * begin,uint8_t * end,uint8_t * limit,size_t growth_limit,bool create_bitmaps,bool can_move_objects,size_t starting_size,size_t initial_size)46 MallocSpace::MallocSpace(const std::string& name,
47                          MemMap&& mem_map,
48                          uint8_t* begin,
49                          uint8_t* end,
50                          uint8_t* limit,
51                          size_t growth_limit,
52                          bool create_bitmaps,
53                          bool can_move_objects,
54                          size_t starting_size,
55                          size_t initial_size)
56     : ContinuousMemMapAllocSpace(
57         name, std::move(mem_map), begin, end, limit, kGcRetentionPolicyAlwaysCollect),
58       recent_free_pos_(0), lock_("allocation space lock", kAllocSpaceLock),
59       growth_limit_(growth_limit), can_move_objects_(can_move_objects),
60       starting_size_(starting_size), initial_size_(initial_size) {
61   if (create_bitmaps) {
62     size_t bitmap_index = bitmap_index_++;
63     static const uintptr_t kGcCardSize = static_cast<uintptr_t>(accounting::CardTable::kCardSize);
64     CHECK_ALIGNED(reinterpret_cast<uintptr_t>(mem_map_.Begin()), kGcCardSize);
65     CHECK_ALIGNED(reinterpret_cast<uintptr_t>(mem_map_.End()), kGcCardSize);
66     live_bitmap_.reset(accounting::ContinuousSpaceBitmap::Create(
67         StringPrintf("allocspace %s live-bitmap %d", name.c_str(), static_cast<int>(bitmap_index)),
68         Begin(), NonGrowthLimitCapacity()));
69     CHECK(live_bitmap_.get() != nullptr) << "could not create allocspace live bitmap #"
70         << bitmap_index;
71     mark_bitmap_.reset(accounting::ContinuousSpaceBitmap::Create(
72         StringPrintf("allocspace %s mark-bitmap %d", name.c_str(), static_cast<int>(bitmap_index)),
73         Begin(), NonGrowthLimitCapacity()));
74     CHECK(mark_bitmap_.get() != nullptr) << "could not create allocspace mark bitmap #"
75         << bitmap_index;
76   }
77   for (auto& freed : recent_freed_objects_) {
78     freed.first = nullptr;
79     freed.second = nullptr;
80   }
81 }
82 
CreateMemMap(const std::string & name,size_t starting_size,size_t * initial_size,size_t * growth_limit,size_t * capacity)83 MemMap MallocSpace::CreateMemMap(const std::string& name,
84                                  size_t starting_size,
85                                  size_t* initial_size,
86                                  size_t* growth_limit,
87                                  size_t* capacity) {
88   // Sanity check arguments
89   if (starting_size > *initial_size) {
90     *initial_size = starting_size;
91   }
92   if (*initial_size > *growth_limit) {
93     LOG(ERROR) << "Failed to create alloc space (" << name << ") where the initial size ("
94         << PrettySize(*initial_size) << ") is larger than its capacity ("
95         << PrettySize(*growth_limit) << ")";
96     return MemMap::Invalid();
97   }
98   if (*growth_limit > *capacity) {
99     LOG(ERROR) << "Failed to create alloc space (" << name << ") where the growth limit capacity ("
100         << PrettySize(*growth_limit) << ") is larger than the capacity ("
101         << PrettySize(*capacity) << ")";
102     return MemMap::Invalid();
103   }
104 
105   // Page align growth limit and capacity which will be used to manage mmapped storage
106   *growth_limit = RoundUp(*growth_limit, kPageSize);
107   *capacity = RoundUp(*capacity, kPageSize);
108 
109   std::string error_msg;
110   MemMap mem_map = MemMap::MapAnonymous(name.c_str(),
111                                         *capacity,
112                                         PROT_READ | PROT_WRITE,
113                                         /*low_4gb=*/ true,
114                                         &error_msg);
115   if (!mem_map.IsValid()) {
116     LOG(ERROR) << "Failed to allocate pages for alloc space (" << name << ") of size "
117                << PrettySize(*capacity) << ": " << error_msg;
118   }
119   return mem_map;
120 }
121 
FindRecentFreedObject(const mirror::Object * obj)122 mirror::Class* MallocSpace::FindRecentFreedObject(const mirror::Object* obj) {
123   size_t pos = recent_free_pos_;
124   // Start at the most recently freed object and work our way back since there may be duplicates
125   // caused by dlmalloc reusing memory.
126   if (kRecentFreeCount > 0) {
127     for (size_t i = 0; i + 1 < kRecentFreeCount + 1; ++i) {
128       pos = pos != 0 ? pos - 1 : kRecentFreeMask;
129       if (recent_freed_objects_[pos].first == obj) {
130         return recent_freed_objects_[pos].second;
131       }
132     }
133   }
134   return nullptr;
135 }
136 
RegisterRecentFree(mirror::Object * ptr)137 void MallocSpace::RegisterRecentFree(mirror::Object* ptr) {
138   // No verification since the object is dead.
139   recent_freed_objects_[recent_free_pos_] = std::make_pair(ptr, ptr->GetClass<kVerifyNone>());
140   recent_free_pos_ = (recent_free_pos_ + 1) & kRecentFreeMask;
141 }
142 
SetGrowthLimit(size_t growth_limit)143 void MallocSpace::SetGrowthLimit(size_t growth_limit) {
144   growth_limit = RoundUp(growth_limit, kPageSize);
145   growth_limit_ = growth_limit;
146   if (Size() > growth_limit_) {
147     SetEnd(begin_ + growth_limit);
148   }
149 }
150 
MoreCore(intptr_t increment)151 void* MallocSpace::MoreCore(intptr_t increment) {
152   CheckMoreCoreForPrecondition();
153   uint8_t* original_end = End();
154   if (increment != 0) {
155     VLOG(heap) << "MallocSpace::MoreCore " << PrettySize(increment);
156     uint8_t* new_end = original_end + increment;
157     if (increment > 0) {
158       // Should never be asked to increase the allocation beyond the capacity of the space. Enforced
159       // by mspace_set_footprint_limit.
160       CHECK_LE(new_end, Begin() + Capacity());
161       CheckedCall(mprotect, GetName(), original_end, increment, PROT_READ | PROT_WRITE);
162     } else {
163       // Should never be asked for negative footprint (ie before begin). Zero footprint is ok.
164       CHECK_GE(original_end + increment, Begin());
165       // Advise we don't need the pages and protect them
166       // TODO: by removing permissions to the pages we may be causing TLB shoot-down which can be
167       // expensive (note the same isn't true for giving permissions to a page as the protected
168       // page shouldn't be in a TLB). We should investigate performance impact of just
169       // removing ignoring the memory protection change here and in Space::CreateAllocSpace. It's
170       // likely just a useful debug feature.
171       size_t size = -increment;
172       CheckedCall(madvise, GetName(), new_end, size, MADV_DONTNEED);
173       CheckedCall(mprotect, GetName(), new_end, size, PROT_NONE);
174     }
175     // Update end_.
176     SetEnd(new_end);
177   }
178   return original_end;
179 }
180 
CreateZygoteSpace(const char * alloc_space_name,bool low_memory_mode,MallocSpace ** out_malloc_space)181 ZygoteSpace* MallocSpace::CreateZygoteSpace(const char* alloc_space_name, bool low_memory_mode,
182                                             MallocSpace** out_malloc_space) {
183   // For RosAlloc, revoke thread local runs before creating a new
184   // alloc space so that we won't mix thread local runs from different
185   // alloc spaces.
186   RevokeAllThreadLocalBuffers();
187   SetEnd(reinterpret_cast<uint8_t*>(RoundUp(reinterpret_cast<uintptr_t>(End()), kPageSize)));
188   DCHECK_ALIGNED(begin_, accounting::CardTable::kCardSize);
189   DCHECK_ALIGNED(End(), accounting::CardTable::kCardSize);
190   DCHECK_ALIGNED(begin_, kPageSize);
191   DCHECK_ALIGNED(End(), kPageSize);
192   size_t size = RoundUp(Size(), kPageSize);
193   // Trimming the heap should be done by the caller since we may have invalidated the accounting
194   // stored in between objects.
195   // Remaining size is for the new alloc space.
196   const size_t growth_limit = growth_limit_ - size;
197   // Use mem map limit in case error for clear growth limit.
198   const size_t capacity = NonGrowthLimitCapacity() - size;
199   VLOG(heap) << "Begin " << reinterpret_cast<const void*>(begin_) << "\n"
200              << "End " << reinterpret_cast<const void*>(End()) << "\n"
201              << "Size " << size << "\n"
202              << "GrowthLimit " << growth_limit_ << "\n"
203              << "Capacity " << Capacity();
204   SetGrowthLimit(RoundUp(size, kPageSize));
205   // FIXME: Do we need reference counted pointers here?
206   // Make the two spaces share the same mark bitmaps since the bitmaps span both of the spaces.
207   VLOG(heap) << "Creating new AllocSpace: ";
208   VLOG(heap) << "Size " << GetMemMap()->Size();
209   VLOG(heap) << "GrowthLimit " << PrettySize(growth_limit);
210   VLOG(heap) << "Capacity " << PrettySize(capacity);
211   // Remap the tail.
212   std::string error_msg;
213   MemMap mem_map = GetMemMap()->RemapAtEnd(
214       End(), alloc_space_name, PROT_READ | PROT_WRITE, &error_msg);
215   CHECK(mem_map.IsValid()) << error_msg;
216   void* allocator =
217       CreateAllocator(End(), starting_size_, initial_size_, capacity, low_memory_mode);
218   // Protect memory beyond the initial size.
219   uint8_t* end = mem_map.Begin() + starting_size_;
220   if (capacity > initial_size_) {
221     CheckedCall(mprotect, alloc_space_name, end, capacity - initial_size_, PROT_NONE);
222   }
223   *out_malloc_space = CreateInstance(std::move(mem_map),
224                                      alloc_space_name,
225                                      allocator,
226                                      End(),
227                                      end,
228                                      limit_,
229                                      growth_limit,
230                                      CanMoveObjects());
231   SetLimit(End());
232   live_bitmap_->SetHeapLimit(reinterpret_cast<uintptr_t>(End()));
233   CHECK_EQ(live_bitmap_->HeapLimit(), reinterpret_cast<uintptr_t>(End()));
234   mark_bitmap_->SetHeapLimit(reinterpret_cast<uintptr_t>(End()));
235   CHECK_EQ(mark_bitmap_->HeapLimit(), reinterpret_cast<uintptr_t>(End()));
236 
237   // Create the actual zygote space.
238   ZygoteSpace* zygote_space = ZygoteSpace::Create("Zygote space", ReleaseMemMap(),
239                                                   live_bitmap_.release(), mark_bitmap_.release());
240   if (UNLIKELY(zygote_space == nullptr)) {
241     VLOG(heap) << "Failed creating zygote space from space " << GetName();
242   } else {
243     VLOG(heap) << "zygote space creation done";
244   }
245   return zygote_space;
246 }
247 
Dump(std::ostream & os) const248 void MallocSpace::Dump(std::ostream& os) const {
249   os << GetType()
250      << " begin=" << reinterpret_cast<void*>(Begin())
251      << ",end=" << reinterpret_cast<void*>(End())
252      << ",limit=" << reinterpret_cast<void*>(Limit())
253      << ",size=" << PrettySize(Size()) << ",capacity=" << PrettySize(Capacity())
254      << ",non_growth_limit_capacity=" << PrettySize(NonGrowthLimitCapacity())
255      << ",name=\"" << GetName() << "\"]";
256 }
257 
SweepCallback(size_t num_ptrs,mirror::Object ** ptrs,void * arg)258 void MallocSpace::SweepCallback(size_t num_ptrs, mirror::Object** ptrs, void* arg) {
259   SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg);
260   space::MallocSpace* space = context->space->AsMallocSpace();
261   Thread* self = context->self;
262   Locks::heap_bitmap_lock_->AssertExclusiveHeld(self);
263   // If the bitmaps aren't swapped we need to clear the bits since the GC isn't going to re-swap
264   // the bitmaps as an optimization.
265   if (!context->swap_bitmaps) {
266     accounting::ContinuousSpaceBitmap* bitmap = space->GetLiveBitmap();
267     for (size_t i = 0; i < num_ptrs; ++i) {
268       bitmap->Clear(ptrs[i]);
269     }
270   }
271   // Use a bulk free, that merges consecutive objects before freeing or free per object?
272   // Documentation suggests better free performance with merging, but this may be at the expense
273   // of allocation.
274   context->freed.objects += num_ptrs;
275   context->freed.bytes += space->FreeList(self, num_ptrs, ptrs);
276 }
277 
ClampGrowthLimit()278 void MallocSpace::ClampGrowthLimit() {
279   size_t new_capacity = Capacity();
280   CHECK_LE(new_capacity, NonGrowthLimitCapacity());
281   GetLiveBitmap()->SetHeapSize(new_capacity);
282   GetMarkBitmap()->SetHeapSize(new_capacity);
283   if (temp_bitmap_.get() != nullptr) {
284     // If the bitmaps are clamped, then the temp bitmap is actually the mark bitmap.
285     temp_bitmap_->SetHeapSize(new_capacity);
286   }
287   GetMemMap()->SetSize(new_capacity);
288   limit_ = Begin() + new_capacity;
289 }
290 
291 }  // namespace space
292 }  // namespace gc
293 }  // namespace art
294