1 /*
2  * Copyright (C) 2011 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 "dlmalloc_space-inl.h"
18 
19 #include "base/logging.h"  // For VLOG.
20 #include "base/time_utils.h"
21 #include "base/utils.h"
22 #include "gc/accounting/card_table.h"
23 #include "gc/accounting/space_bitmap-inl.h"
24 #include "gc/heap.h"
25 #include "jit/jit.h"
26 #include "jit/jit_code_cache.h"
27 #include "memory_tool_malloc_space-inl.h"
28 #include "mirror/class-inl.h"
29 #include "mirror/object-inl.h"
30 #include "runtime.h"
31 #include "scoped_thread_state_change-inl.h"
32 #include "thread.h"
33 #include "thread_list.h"
34 
35 namespace art {
36 namespace gc {
37 namespace space {
38 
39 static constexpr bool kPrefetchDuringDlMallocFreeList = true;
40 
DlMallocSpace(MemMap && mem_map,size_t initial_size,const std::string & name,void * mspace,uint8_t * begin,uint8_t * end,uint8_t * limit,size_t growth_limit,bool can_move_objects,size_t starting_size)41 DlMallocSpace::DlMallocSpace(MemMap&& mem_map,
42                              size_t initial_size,
43                              const std::string& name,
44                              void* mspace,
45                              uint8_t* begin,
46                              uint8_t* end,
47                              uint8_t* limit,
48                              size_t growth_limit,
49                              bool can_move_objects,
50                              size_t starting_size)
51     : MallocSpace(name,
52                   std::move(mem_map),
53                   begin,
54                   end,
55                   limit,
56                   growth_limit,
57                   /* create_bitmaps= */ true,
58                   can_move_objects,
59                   starting_size, initial_size),
60       mspace_(mspace) {
61   CHECK(mspace != nullptr);
62 }
63 
CreateFromMemMap(MemMap && mem_map,const std::string & name,size_t starting_size,size_t initial_size,size_t growth_limit,size_t capacity,bool can_move_objects)64 DlMallocSpace* DlMallocSpace::CreateFromMemMap(MemMap&& mem_map,
65                                                const std::string& name,
66                                                size_t starting_size,
67                                                size_t initial_size,
68                                                size_t growth_limit,
69                                                size_t capacity,
70                                                bool can_move_objects) {
71   DCHECK(mem_map.IsValid());
72   void* mspace = CreateMspace(mem_map.Begin(), starting_size, initial_size);
73   if (mspace == nullptr) {
74     LOG(ERROR) << "Failed to initialize mspace for alloc space (" << name << ")";
75     return nullptr;
76   }
77 
78   // Protect memory beyond the starting size. morecore will add r/w permissions when necessory
79   uint8_t* end = mem_map.Begin() + starting_size;
80   if (capacity - starting_size > 0) {
81     CheckedCall(mprotect, name.c_str(), end, capacity - starting_size, PROT_NONE);
82   }
83 
84   // Everything is set so record in immutable structure and leave
85   uint8_t* begin = mem_map.Begin();
86   if (Runtime::Current()->IsRunningOnMemoryTool()) {
87     return new MemoryToolMallocSpace<DlMallocSpace, kDefaultMemoryToolRedZoneBytes, true, false>(
88         std::move(mem_map),
89         initial_size,
90         name,
91         mspace,
92         begin,
93         end,
94         begin + capacity, growth_limit,
95         can_move_objects,
96         starting_size);
97   } else {
98     return new DlMallocSpace(std::move(mem_map),
99                              initial_size,
100                              name,
101                              mspace,
102                              begin,
103                              end,
104                              begin + capacity,
105                              growth_limit,
106                              can_move_objects,
107                              starting_size);
108   }
109 }
110 
Create(const std::string & name,size_t initial_size,size_t growth_limit,size_t capacity,bool can_move_objects)111 DlMallocSpace* DlMallocSpace::Create(const std::string& name,
112                                      size_t initial_size,
113                                      size_t growth_limit,
114                                      size_t capacity,
115                                      bool can_move_objects) {
116   uint64_t start_time = 0;
117   if (VLOG_IS_ON(heap) || VLOG_IS_ON(startup)) {
118     start_time = NanoTime();
119     LOG(INFO) << "DlMallocSpace::Create entering " << name
120         << " initial_size=" << PrettySize(initial_size)
121         << " growth_limit=" << PrettySize(growth_limit)
122         << " capacity=" << PrettySize(capacity);
123   }
124 
125   // Memory we promise to dlmalloc before it asks for morecore.
126   // Note: making this value large means that large allocations are unlikely to succeed as dlmalloc
127   // will ask for this memory from sys_alloc which will fail as the footprint (this value plus the
128   // size of the large allocation) will be greater than the footprint limit.
129   size_t starting_size = kPageSize;
130   MemMap mem_map = CreateMemMap(name, starting_size, &initial_size, &growth_limit, &capacity);
131   if (!mem_map.IsValid()) {
132     LOG(ERROR) << "Failed to create mem map for alloc space (" << name << ") of size "
133                << PrettySize(capacity);
134     return nullptr;
135   }
136   DlMallocSpace* space = CreateFromMemMap(std::move(mem_map),
137                                           name,
138                                           starting_size,
139                                           initial_size,
140                                           growth_limit,
141                                           capacity,
142                                           can_move_objects);
143   // We start out with only the initial size possibly containing objects.
144   if (VLOG_IS_ON(heap) || VLOG_IS_ON(startup)) {
145     LOG(INFO) << "DlMallocSpace::Create exiting (" << PrettyDuration(NanoTime() - start_time)
146         << " ) " << *space;
147   }
148   return space;
149 }
150 
CreateMspace(void * begin,size_t morecore_start,size_t initial_size)151 void* DlMallocSpace::CreateMspace(void* begin, size_t morecore_start, size_t initial_size) {
152   // clear errno to allow PLOG on error
153   errno = 0;
154   // create mspace using our backing storage starting at begin and with a footprint of
155   // morecore_start. Don't use an internal dlmalloc lock (as we already hold heap lock). When
156   // morecore_start bytes of memory is exhaused morecore will be called.
157   void* msp = create_mspace_with_base(begin, morecore_start, 0 /*locked*/);
158   if (msp != nullptr) {
159     // Do not allow morecore requests to succeed beyond the initial size of the heap
160     mspace_set_footprint_limit(msp, initial_size);
161   } else {
162     PLOG(ERROR) << "create_mspace_with_base failed";
163   }
164   return msp;
165 }
166 
AllocWithGrowth(Thread * self,size_t num_bytes,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)167 mirror::Object* DlMallocSpace::AllocWithGrowth(Thread* self, size_t num_bytes,
168                                                size_t* bytes_allocated, size_t* usable_size,
169                                                size_t* bytes_tl_bulk_allocated) {
170   mirror::Object* result;
171   {
172     MutexLock mu(self, lock_);
173     // Grow as much as possible within the space.
174     size_t max_allowed = Capacity();
175     mspace_set_footprint_limit(mspace_, max_allowed);
176     // Try the allocation.
177     result = AllocWithoutGrowthLocked(self, num_bytes, bytes_allocated, usable_size,
178                                       bytes_tl_bulk_allocated);
179     // Shrink back down as small as possible.
180     size_t footprint = mspace_footprint(mspace_);
181     mspace_set_footprint_limit(mspace_, footprint);
182   }
183   if (result != nullptr) {
184     // Zero freshly allocated memory, done while not holding the space's lock.
185     memset(result, 0, num_bytes);
186     // Check that the result is contained in the space.
187     CHECK(!kDebugSpaces || Contains(result));
188   }
189   return result;
190 }
191 
CreateInstance(MemMap && mem_map,const std::string & name,void * allocator,uint8_t * begin,uint8_t * end,uint8_t * limit,size_t growth_limit,bool can_move_objects)192 MallocSpace* DlMallocSpace::CreateInstance(MemMap&& mem_map,
193                                            const std::string& name,
194                                            void* allocator,
195                                            uint8_t* begin,
196                                            uint8_t* end,
197                                            uint8_t* limit,
198                                            size_t growth_limit,
199                                            bool can_move_objects) {
200   if (Runtime::Current()->IsRunningOnMemoryTool()) {
201     return new MemoryToolMallocSpace<DlMallocSpace, kDefaultMemoryToolRedZoneBytes, true, false>(
202         std::move(mem_map),
203         initial_size_,
204         name,
205         allocator,
206         begin,
207         end,
208         limit,
209         growth_limit,
210         can_move_objects,
211         starting_size_);
212   } else {
213     return new DlMallocSpace(std::move(mem_map),
214                              initial_size_,
215                              name,
216                              allocator,
217                              begin,
218                              end,
219                              limit,
220                              growth_limit,
221                              can_move_objects,
222                              starting_size_);
223   }
224 }
225 
Free(Thread * self,mirror::Object * ptr)226 size_t DlMallocSpace::Free(Thread* self, mirror::Object* ptr) {
227   MutexLock mu(self, lock_);
228   if (kDebugSpaces) {
229     CHECK(ptr != nullptr);
230     CHECK(Contains(ptr)) << "Free (" << ptr << ") not in bounds of heap " << *this;
231   }
232   const size_t bytes_freed = AllocationSizeNonvirtual(ptr, nullptr);
233   if (kRecentFreeCount > 0) {
234     RegisterRecentFree(ptr);
235   }
236   mspace_free(mspace_, ptr);
237   return bytes_freed;
238 }
239 
FreeList(Thread * self,size_t num_ptrs,mirror::Object ** ptrs)240 size_t DlMallocSpace::FreeList(Thread* self, size_t num_ptrs, mirror::Object** ptrs) {
241   DCHECK(ptrs != nullptr);
242 
243   // Don't need the lock to calculate the size of the freed pointers.
244   size_t bytes_freed = 0;
245   for (size_t i = 0; i < num_ptrs; i++) {
246     mirror::Object* ptr = ptrs[i];
247     const size_t look_ahead = 8;
248     if (kPrefetchDuringDlMallocFreeList && i + look_ahead < num_ptrs) {
249       // The head of chunk for the allocation is sizeof(size_t) behind the allocation.
250       __builtin_prefetch(reinterpret_cast<char*>(ptrs[i + look_ahead]) - sizeof(size_t));
251     }
252     bytes_freed += AllocationSizeNonvirtual(ptr, nullptr);
253   }
254 
255   if (kRecentFreeCount > 0) {
256     MutexLock mu(self, lock_);
257     for (size_t i = 0; i < num_ptrs; i++) {
258       RegisterRecentFree(ptrs[i]);
259     }
260   }
261 
262   if (kDebugSpaces) {
263     size_t num_broken_ptrs = 0;
264     for (size_t i = 0; i < num_ptrs; i++) {
265       if (!Contains(ptrs[i])) {
266         num_broken_ptrs++;
267         LOG(ERROR) << "FreeList[" << i << "] (" << ptrs[i] << ") not in bounds of heap " << *this;
268       } else {
269         size_t size = mspace_usable_size(ptrs[i]);
270         memset(ptrs[i], 0xEF, size);
271       }
272     }
273     CHECK_EQ(num_broken_ptrs, 0u);
274   }
275 
276   {
277     MutexLock mu(self, lock_);
278     mspace_bulk_free(mspace_, reinterpret_cast<void**>(ptrs), num_ptrs);
279     return bytes_freed;
280   }
281 }
282 
Trim()283 size_t DlMallocSpace::Trim() {
284   MutexLock mu(Thread::Current(), lock_);
285   // Trim to release memory at the end of the space.
286   mspace_trim(mspace_, 0);
287   // Visit space looking for page-sized holes to advise the kernel we don't need.
288   size_t reclaimed = 0;
289   mspace_inspect_all(mspace_, DlmallocMadviseCallback, &reclaimed);
290   return reclaimed;
291 }
292 
Walk(void (* callback)(void * start,void * end,size_t num_bytes,void * callback_arg),void * arg)293 void DlMallocSpace::Walk(void(*callback)(void *start, void *end, size_t num_bytes, void* callback_arg),
294                       void* arg) {
295   MutexLock mu(Thread::Current(), lock_);
296   mspace_inspect_all(mspace_, callback, arg);
297   callback(nullptr, nullptr, 0, arg);  // Indicate end of a space.
298 }
299 
GetFootprint()300 size_t DlMallocSpace::GetFootprint() {
301   MutexLock mu(Thread::Current(), lock_);
302   return mspace_footprint(mspace_);
303 }
304 
GetFootprintLimit()305 size_t DlMallocSpace::GetFootprintLimit() {
306   MutexLock mu(Thread::Current(), lock_);
307   return mspace_footprint_limit(mspace_);
308 }
309 
SetFootprintLimit(size_t new_size)310 void DlMallocSpace::SetFootprintLimit(size_t new_size) {
311   MutexLock mu(Thread::Current(), lock_);
312   VLOG(heap) << "DlMallocSpace::SetFootprintLimit " << PrettySize(new_size);
313   // Compare against the actual footprint, rather than the Size(), because the heap may not have
314   // grown all the way to the allowed size yet.
315   size_t current_space_size = mspace_footprint(mspace_);
316   if (new_size < current_space_size) {
317     // Don't let the space grow any more.
318     new_size = current_space_size;
319   }
320   mspace_set_footprint_limit(mspace_, new_size);
321 }
322 
GetBytesAllocated()323 uint64_t DlMallocSpace::GetBytesAllocated() {
324   MutexLock mu(Thread::Current(), lock_);
325   size_t bytes_allocated = 0;
326   mspace_inspect_all(mspace_, DlmallocBytesAllocatedCallback, &bytes_allocated);
327   return bytes_allocated;
328 }
329 
GetObjectsAllocated()330 uint64_t DlMallocSpace::GetObjectsAllocated() {
331   MutexLock mu(Thread::Current(), lock_);
332   size_t objects_allocated = 0;
333   mspace_inspect_all(mspace_, DlmallocObjectsAllocatedCallback, &objects_allocated);
334   return objects_allocated;
335 }
336 
Clear()337 void DlMallocSpace::Clear() {
338   size_t footprint_limit = GetFootprintLimit();
339   madvise(GetMemMap()->Begin(), GetMemMap()->Size(), MADV_DONTNEED);
340   live_bitmap_.Clear();
341   mark_bitmap_.Clear();
342   SetEnd(Begin() + starting_size_);
343   mspace_ = CreateMspace(mem_map_.Begin(), starting_size_, initial_size_);
344   SetFootprintLimit(footprint_limit);
345 }
346 
347 #ifndef NDEBUG
CheckMoreCoreForPrecondition()348 void DlMallocSpace::CheckMoreCoreForPrecondition() {
349   lock_.AssertHeld(Thread::Current());
350 }
351 #endif
352 
MSpaceChunkCallback(void * start,void * end,size_t used_bytes,void * arg)353 static void MSpaceChunkCallback(void* start, void* end, size_t used_bytes, void* arg) {
354   size_t chunk_size = reinterpret_cast<uint8_t*>(end) - reinterpret_cast<uint8_t*>(start);
355   if (used_bytes < chunk_size) {
356     size_t chunk_free_bytes = chunk_size - used_bytes;
357     size_t& max_contiguous_allocation = *reinterpret_cast<size_t*>(arg);
358     max_contiguous_allocation = std::max(max_contiguous_allocation, chunk_free_bytes);
359   }
360 }
361 
LogFragmentationAllocFailure(std::ostream & os,size_t failed_alloc_bytes)362 bool DlMallocSpace::LogFragmentationAllocFailure(std::ostream& os,
363                                                  size_t failed_alloc_bytes) {
364   Thread* const self = Thread::Current();
365   size_t max_contiguous_allocation = 0;
366   // To allow the Walk/InspectAll() to exclusively-lock the mutator
367   // lock, temporarily release the shared access to the mutator
368   // lock here by transitioning to the suspended state.
369   Locks::mutator_lock_->AssertSharedHeld(self);
370   ScopedThreadSuspension sts(self, kSuspended);
371   Walk(MSpaceChunkCallback, &max_contiguous_allocation);
372   if (failed_alloc_bytes > max_contiguous_allocation) {
373     os << "; failed due to fragmentation (largest possible contiguous allocation "
374        <<  max_contiguous_allocation << " bytes)";
375     return true;
376   }
377   return false;
378 }
379 
380 }  // namespace space
381 
382 namespace allocator {
383 
384 // Implement the dlmalloc morecore callback.
ArtDlMallocMoreCore(void * mspace,intptr_t increment)385 void* ArtDlMallocMoreCore(void* mspace, intptr_t increment) REQUIRES_SHARED(Locks::mutator_lock_) {
386   Runtime* runtime = Runtime::Current();
387   Heap* heap = runtime->GetHeap();
388   ::art::gc::space::DlMallocSpace* dlmalloc_space = heap->GetDlMallocSpace();
389   // Support for multiple DlMalloc provided by a slow path.
390   if (UNLIKELY(dlmalloc_space == nullptr || dlmalloc_space->GetMspace() != mspace)) {
391     if (LIKELY(runtime->GetJitCodeCache() != nullptr)) {
392       jit::JitCodeCache* code_cache = runtime->GetJitCodeCache();
393       if (code_cache->OwnsSpace(mspace)) {
394         return code_cache->MoreCore(mspace, increment);
395       }
396     }
397     dlmalloc_space = nullptr;
398     for (space::ContinuousSpace* space : heap->GetContinuousSpaces()) {
399       if (space->IsDlMallocSpace()) {
400         ::art::gc::space::DlMallocSpace* cur_dlmalloc_space = space->AsDlMallocSpace();
401         if (cur_dlmalloc_space->GetMspace() == mspace) {
402           dlmalloc_space = cur_dlmalloc_space;
403           break;
404         }
405       }
406     }
407     CHECK(dlmalloc_space != nullptr) << "Couldn't find DlmMallocSpace with mspace=" << mspace;
408   }
409   return dlmalloc_space->MoreCore(increment);
410 }
411 
412 }  // namespace allocator
413 
414 }  // namespace gc
415 }  // namespace art
416