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