1 /*
2  * Copyright (C) 2012 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 "large_object_space.h"
18 
19 #include <sys/mman.h>
20 
21 #include <memory>
22 
23 #include <android-base/logging.h>
24 
25 #include "base/macros.h"
26 #include "base/memory_tool.h"
27 #include "base/mutex-inl.h"
28 #include "base/os.h"
29 #include "base/stl_util.h"
30 #include "gc/accounting/heap_bitmap-inl.h"
31 #include "gc/accounting/space_bitmap-inl.h"
32 #include "gc/heap.h"
33 #include "image.h"
34 #include "mirror/object-readbarrier-inl.h"
35 #include "scoped_thread_state_change-inl.h"
36 #include "space-inl.h"
37 #include "thread-current-inl.h"
38 
39 namespace art {
40 namespace gc {
41 namespace space {
42 
43 class MemoryToolLargeObjectMapSpace final : public LargeObjectMapSpace {
44  public:
MemoryToolLargeObjectMapSpace(const std::string & name)45   explicit MemoryToolLargeObjectMapSpace(const std::string& name) : LargeObjectMapSpace(name) {
46   }
47 
~MemoryToolLargeObjectMapSpace()48   ~MemoryToolLargeObjectMapSpace() override {
49     // Historical note: We were deleting large objects to keep Valgrind happy if there were
50     // any large objects such as Dex cache arrays which aren't freed since they are held live
51     // by the class linker.
52   }
53 
Alloc(Thread * self,size_t num_bytes,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)54   mirror::Object* Alloc(Thread* self, size_t num_bytes, size_t* bytes_allocated,
55                         size_t* usable_size, size_t* bytes_tl_bulk_allocated)
56       override {
57     mirror::Object* obj =
58         LargeObjectMapSpace::Alloc(self, num_bytes + kMemoryToolRedZoneBytes * 2, bytes_allocated,
59                                    usable_size, bytes_tl_bulk_allocated);
60     mirror::Object* object_without_rdz = reinterpret_cast<mirror::Object*>(
61         reinterpret_cast<uintptr_t>(obj) + kMemoryToolRedZoneBytes);
62     MEMORY_TOOL_MAKE_NOACCESS(reinterpret_cast<void*>(obj), kMemoryToolRedZoneBytes);
63     MEMORY_TOOL_MAKE_NOACCESS(
64         reinterpret_cast<uint8_t*>(object_without_rdz) + num_bytes,
65         kMemoryToolRedZoneBytes);
66     if (usable_size != nullptr) {
67       *usable_size = num_bytes;  // Since we have redzones, shrink the usable size.
68     }
69     return object_without_rdz;
70   }
71 
AllocationSize(mirror::Object * obj,size_t * usable_size)72   size_t AllocationSize(mirror::Object* obj, size_t* usable_size) override {
73     return LargeObjectMapSpace::AllocationSize(ObjectWithRedzone(obj), usable_size);
74   }
75 
IsZygoteLargeObject(Thread * self,mirror::Object * obj) const76   bool IsZygoteLargeObject(Thread* self, mirror::Object* obj) const override {
77     return LargeObjectMapSpace::IsZygoteLargeObject(self, ObjectWithRedzone(obj));
78   }
79 
Free(Thread * self,mirror::Object * obj)80   size_t Free(Thread* self, mirror::Object* obj) override {
81     mirror::Object* object_with_rdz = ObjectWithRedzone(obj);
82     MEMORY_TOOL_MAKE_UNDEFINED(object_with_rdz, AllocationSize(obj, nullptr));
83     return LargeObjectMapSpace::Free(self, object_with_rdz);
84   }
85 
Contains(const mirror::Object * obj) const86   bool Contains(const mirror::Object* obj) const override {
87     return LargeObjectMapSpace::Contains(ObjectWithRedzone(obj));
88   }
89 
90  private:
ObjectWithRedzone(const mirror::Object * obj)91   static const mirror::Object* ObjectWithRedzone(const mirror::Object* obj) {
92     return reinterpret_cast<const mirror::Object*>(
93         reinterpret_cast<uintptr_t>(obj) - kMemoryToolRedZoneBytes);
94   }
95 
ObjectWithRedzone(mirror::Object * obj)96   static mirror::Object* ObjectWithRedzone(mirror::Object* obj) {
97     return reinterpret_cast<mirror::Object*>(
98         reinterpret_cast<uintptr_t>(obj) - kMemoryToolRedZoneBytes);
99   }
100 
101   static constexpr size_t kMemoryToolRedZoneBytes = kPageSize;
102 };
103 
SwapBitmaps()104 void LargeObjectSpace::SwapBitmaps() {
105   std::swap(live_bitmap_, mark_bitmap_);
106   // Preserve names to get more descriptive diagnostics.
107   std::string temp_name = live_bitmap_.GetName();
108   live_bitmap_.SetName(mark_bitmap_.GetName());
109   mark_bitmap_.SetName(temp_name);
110 }
111 
LargeObjectSpace(const std::string & name,uint8_t * begin,uint8_t * end,const char * lock_name)112 LargeObjectSpace::LargeObjectSpace(const std::string& name, uint8_t* begin, uint8_t* end,
113                                    const char* lock_name)
114     : DiscontinuousSpace(name, kGcRetentionPolicyAlwaysCollect),
115       lock_(lock_name, kAllocSpaceLock),
116       num_bytes_allocated_(0), num_objects_allocated_(0), total_bytes_allocated_(0),
117       total_objects_allocated_(0), begin_(begin), end_(end) {
118 }
119 
120 
CopyLiveToMarked()121 void LargeObjectSpace::CopyLiveToMarked() {
122   mark_bitmap_.CopyFrom(&live_bitmap_);
123 }
124 
LargeObjectMapSpace(const std::string & name)125 LargeObjectMapSpace::LargeObjectMapSpace(const std::string& name)
126     : LargeObjectSpace(name, nullptr, nullptr, "large object map space lock") {}
127 
Create(const std::string & name)128 LargeObjectMapSpace* LargeObjectMapSpace::Create(const std::string& name) {
129   if (Runtime::Current()->IsRunningOnMemoryTool()) {
130     return new MemoryToolLargeObjectMapSpace(name);
131   } else {
132     return new LargeObjectMapSpace(name);
133   }
134 }
135 
Alloc(Thread * self,size_t num_bytes,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)136 mirror::Object* LargeObjectMapSpace::Alloc(Thread* self, size_t num_bytes,
137                                            size_t* bytes_allocated, size_t* usable_size,
138                                            size_t* bytes_tl_bulk_allocated) {
139   std::string error_msg;
140   MemMap mem_map = MemMap::MapAnonymous("large object space allocation",
141                                         num_bytes,
142                                         PROT_READ | PROT_WRITE,
143                                         /*low_4gb=*/ true,
144                                         &error_msg);
145   if (UNLIKELY(!mem_map.IsValid())) {
146     LOG(WARNING) << "Large object allocation failed: " << error_msg;
147     return nullptr;
148   }
149   mirror::Object* const obj = reinterpret_cast<mirror::Object*>(mem_map.Begin());
150   const size_t allocation_size = mem_map.BaseSize();
151   MutexLock mu(self, lock_);
152   large_objects_.Put(obj, LargeObject {std::move(mem_map), false /* not zygote */});
153   DCHECK(bytes_allocated != nullptr);
154 
155   if (begin_ == nullptr || begin_ > reinterpret_cast<uint8_t*>(obj)) {
156     begin_ = reinterpret_cast<uint8_t*>(obj);
157   }
158   end_ = std::max(end_, reinterpret_cast<uint8_t*>(obj) + allocation_size);
159 
160   *bytes_allocated = allocation_size;
161   if (usable_size != nullptr) {
162     *usable_size = allocation_size;
163   }
164   DCHECK(bytes_tl_bulk_allocated != nullptr);
165   *bytes_tl_bulk_allocated = allocation_size;
166   num_bytes_allocated_ += allocation_size;
167   total_bytes_allocated_ += allocation_size;
168   ++num_objects_allocated_;
169   ++total_objects_allocated_;
170   return obj;
171 }
172 
IsZygoteLargeObject(Thread * self,mirror::Object * obj) const173 bool LargeObjectMapSpace::IsZygoteLargeObject(Thread* self, mirror::Object* obj) const {
174   MutexLock mu(self, lock_);
175   auto it = large_objects_.find(obj);
176   CHECK(it != large_objects_.end());
177   return it->second.is_zygote;
178 }
179 
SetAllLargeObjectsAsZygoteObjects(Thread * self,bool set_mark_bit)180 void LargeObjectMapSpace::SetAllLargeObjectsAsZygoteObjects(Thread* self, bool set_mark_bit) {
181   MutexLock mu(self, lock_);
182   for (auto& pair : large_objects_) {
183     pair.second.is_zygote = true;
184     if (set_mark_bit) {
185       bool success = pair.first->AtomicSetMarkBit(0, 1);
186       CHECK(success);
187     }
188   }
189 }
190 
Free(Thread * self,mirror::Object * ptr)191 size_t LargeObjectMapSpace::Free(Thread* self, mirror::Object* ptr) {
192   MutexLock mu(self, lock_);
193   auto it = large_objects_.find(ptr);
194   if (UNLIKELY(it == large_objects_.end())) {
195     ScopedObjectAccess soa(self);
196     Runtime::Current()->GetHeap()->DumpSpaces(LOG_STREAM(FATAL_WITHOUT_ABORT));
197     LOG(FATAL) << "Attempted to free large object " << ptr << " which was not live";
198   }
199   const size_t map_size = it->second.mem_map.BaseSize();
200   DCHECK_GE(num_bytes_allocated_, map_size);
201   size_t allocation_size = map_size;
202   num_bytes_allocated_ -= allocation_size;
203   --num_objects_allocated_;
204   large_objects_.erase(it);
205   return allocation_size;
206 }
207 
AllocationSize(mirror::Object * obj,size_t * usable_size)208 size_t LargeObjectMapSpace::AllocationSize(mirror::Object* obj, size_t* usable_size) {
209   MutexLock mu(Thread::Current(), lock_);
210   auto it = large_objects_.find(obj);
211   CHECK(it != large_objects_.end()) << "Attempted to get size of a large object which is not live";
212   size_t alloc_size = it->second.mem_map.BaseSize();
213   if (usable_size != nullptr) {
214     *usable_size = alloc_size;
215   }
216   return alloc_size;
217 }
218 
FreeList(Thread * self,size_t num_ptrs,mirror::Object ** ptrs)219 size_t LargeObjectSpace::FreeList(Thread* self, size_t num_ptrs, mirror::Object** ptrs) {
220   size_t total = 0;
221   for (size_t i = 0; i < num_ptrs; ++i) {
222     if (kDebugSpaces) {
223       CHECK(Contains(ptrs[i]));
224     }
225     total += Free(self, ptrs[i]);
226   }
227   return total;
228 }
229 
Walk(DlMallocSpace::WalkCallback callback,void * arg)230 void LargeObjectMapSpace::Walk(DlMallocSpace::WalkCallback callback, void* arg) {
231   MutexLock mu(Thread::Current(), lock_);
232   for (auto& pair : large_objects_) {
233     MemMap* mem_map = &pair.second.mem_map;
234     callback(mem_map->Begin(), mem_map->End(), mem_map->Size(), arg);
235     callback(nullptr, nullptr, 0, arg);
236   }
237 }
238 
ForEachMemMap(std::function<void (const MemMap &)> func) const239 void LargeObjectMapSpace::ForEachMemMap(std::function<void(const MemMap&)> func) const {
240   MutexLock mu(Thread::Current(), lock_);
241   for (auto& pair : large_objects_) {
242     func(pair.second.mem_map);
243   }
244 }
245 
Contains(const mirror::Object * obj) const246 bool LargeObjectMapSpace::Contains(const mirror::Object* obj) const {
247   Thread* self = Thread::Current();
248   if (lock_.IsExclusiveHeld(self)) {
249     // We hold lock_ so do the check.
250     return large_objects_.find(const_cast<mirror::Object*>(obj)) != large_objects_.end();
251   } else {
252     MutexLock mu(self, lock_);
253     return large_objects_.find(const_cast<mirror::Object*>(obj)) != large_objects_.end();
254   }
255 }
256 
257 // Keeps track of allocation sizes + whether or not the previous allocation is free.
258 // Used to coalesce free blocks and find the best fit block for an allocation for best fit object
259 // allocation. Each allocation has an AllocationInfo which contains the size of the previous free
260 // block preceding it. Implemented in such a way that we can also find the iterator for any
261 // allocation info pointer.
262 class AllocationInfo {
263  public:
AllocationInfo()264   AllocationInfo() : prev_free_(0), alloc_size_(0) {
265   }
266   // Return the number of pages that the allocation info covers.
AlignSize() const267   size_t AlignSize() const {
268     return alloc_size_ & kFlagsMask;
269   }
270   // Returns the allocation size in bytes.
ByteSize() const271   size_t ByteSize() const {
272     return AlignSize() * FreeListSpace::kAlignment;
273   }
274   // Updates the allocation size and whether or not it is free.
SetByteSize(size_t size,bool free)275   void SetByteSize(size_t size, bool free) {
276     DCHECK_EQ(size & ~kFlagsMask, 0u);
277     DCHECK_ALIGNED(size, FreeListSpace::kAlignment);
278     alloc_size_ = (size / FreeListSpace::kAlignment) | (free ? kFlagFree : 0u);
279   }
280   // Returns true if the block is free.
IsFree() const281   bool IsFree() const {
282     return (alloc_size_ & kFlagFree) != 0;
283   }
284   // Return true if the large object is a zygote object.
IsZygoteObject() const285   bool IsZygoteObject() const {
286     return (alloc_size_ & kFlagZygote) != 0;
287   }
288   // Change the object to be a zygote object.
SetZygoteObject()289   void SetZygoteObject() {
290     alloc_size_ |= kFlagZygote;
291   }
292   // Return true if this is a zygote large object.
293   // Finds and returns the next non free allocation info after ourself.
GetNextInfo()294   AllocationInfo* GetNextInfo() {
295     return this + AlignSize();
296   }
GetNextInfo() const297   const AllocationInfo* GetNextInfo() const {
298     return this + AlignSize();
299   }
300   // Returns the previous free allocation info by using the prev_free_ member to figure out
301   // where it is. This is only used for coalescing so we only need to be able to do it if the
302   // previous allocation info is free.
GetPrevFreeInfo()303   AllocationInfo* GetPrevFreeInfo() {
304     DCHECK_NE(prev_free_, 0U);
305     return this - prev_free_;
306   }
307   // Returns the address of the object associated with this allocation info.
GetObjectAddress()308   mirror::Object* GetObjectAddress() {
309     return reinterpret_cast<mirror::Object*>(reinterpret_cast<uintptr_t>(this) + sizeof(*this));
310   }
311   // Return how many kAlignment units there are before the free block.
GetPrevFree() const312   size_t GetPrevFree() const {
313     return prev_free_;
314   }
315   // Returns how many free bytes there is before the block.
GetPrevFreeBytes() const316   size_t GetPrevFreeBytes() const {
317     return GetPrevFree() * FreeListSpace::kAlignment;
318   }
319   // Update the size of the free block prior to the allocation.
SetPrevFreeBytes(size_t bytes)320   void SetPrevFreeBytes(size_t bytes) {
321     DCHECK_ALIGNED(bytes, FreeListSpace::kAlignment);
322     prev_free_ = bytes / FreeListSpace::kAlignment;
323   }
324 
325  private:
326   static constexpr uint32_t kFlagFree = 0x80000000;  // If block is free.
327   static constexpr uint32_t kFlagZygote = 0x40000000;  // If the large object is a zygote object.
328   static constexpr uint32_t kFlagsMask = ~(kFlagFree | kFlagZygote);  // Combined flags for masking.
329   // Contains the size of the previous free block with kAlignment as the unit. If 0 then the
330   // allocation before us is not free.
331   // These variables are undefined in the middle of allocations / free blocks.
332   uint32_t prev_free_;
333   // Allocation size of this object in kAlignment as the unit.
334   uint32_t alloc_size_;
335 };
336 
GetSlotIndexForAllocationInfo(const AllocationInfo * info) const337 size_t FreeListSpace::GetSlotIndexForAllocationInfo(const AllocationInfo* info) const {
338   DCHECK_GE(info, allocation_info_);
339   DCHECK_LT(info, reinterpret_cast<AllocationInfo*>(allocation_info_map_.End()));
340   return info - allocation_info_;
341 }
342 
GetAllocationInfoForAddress(uintptr_t address)343 AllocationInfo* FreeListSpace::GetAllocationInfoForAddress(uintptr_t address) {
344   return &allocation_info_[GetSlotIndexForAddress(address)];
345 }
346 
GetAllocationInfoForAddress(uintptr_t address) const347 const AllocationInfo* FreeListSpace::GetAllocationInfoForAddress(uintptr_t address) const {
348   return &allocation_info_[GetSlotIndexForAddress(address)];
349 }
350 
operator ()(const AllocationInfo * a,const AllocationInfo * b) const351 inline bool FreeListSpace::SortByPrevFree::operator()(const AllocationInfo* a,
352                                                       const AllocationInfo* b) const {
353   if (a->GetPrevFree() < b->GetPrevFree()) return true;
354   if (a->GetPrevFree() > b->GetPrevFree()) return false;
355   if (a->AlignSize() < b->AlignSize()) return true;
356   if (a->AlignSize() > b->AlignSize()) return false;
357   return reinterpret_cast<uintptr_t>(a) < reinterpret_cast<uintptr_t>(b);
358 }
359 
Create(const std::string & name,size_t size)360 FreeListSpace* FreeListSpace::Create(const std::string& name, size_t size) {
361   CHECK_EQ(size % kAlignment, 0U);
362   std::string error_msg;
363   MemMap mem_map = MemMap::MapAnonymous(name.c_str(),
364                                         size,
365                                         PROT_READ | PROT_WRITE,
366                                         /*low_4gb=*/ true,
367                                         &error_msg);
368   CHECK(mem_map.IsValid()) << "Failed to allocate large object space mem map: " << error_msg;
369   return new FreeListSpace(name, std::move(mem_map), mem_map.Begin(), mem_map.End());
370 }
371 
FreeListSpace(const std::string & name,MemMap && mem_map,uint8_t * begin,uint8_t * end)372 FreeListSpace::FreeListSpace(const std::string& name,
373                              MemMap&& mem_map,
374                              uint8_t* begin,
375                              uint8_t* end)
376     : LargeObjectSpace(name, begin, end, "free list space lock"),
377       mem_map_(std::move(mem_map)) {
378   const size_t space_capacity = end - begin;
379   free_end_ = space_capacity;
380   CHECK_ALIGNED(space_capacity, kAlignment);
381   const size_t alloc_info_size = sizeof(AllocationInfo) * (space_capacity / kAlignment);
382   std::string error_msg;
383   allocation_info_map_ =
384       MemMap::MapAnonymous("large object free list space allocation info map",
385                            alloc_info_size,
386                            PROT_READ | PROT_WRITE,
387                            /*low_4gb=*/ false,
388                            &error_msg);
389   CHECK(allocation_info_map_.IsValid()) << "Failed to allocate allocation info map" << error_msg;
390   allocation_info_ = reinterpret_cast<AllocationInfo*>(allocation_info_map_.Begin());
391 }
392 
~FreeListSpace()393 FreeListSpace::~FreeListSpace() {}
394 
Walk(DlMallocSpace::WalkCallback callback,void * arg)395 void FreeListSpace::Walk(DlMallocSpace::WalkCallback callback, void* arg) {
396   MutexLock mu(Thread::Current(), lock_);
397   const uintptr_t free_end_start = reinterpret_cast<uintptr_t>(end_) - free_end_;
398   AllocationInfo* cur_info = &allocation_info_[0];
399   const AllocationInfo* end_info = GetAllocationInfoForAddress(free_end_start);
400   while (cur_info < end_info) {
401     if (!cur_info->IsFree()) {
402       size_t alloc_size = cur_info->ByteSize();
403       uint8_t* byte_start = reinterpret_cast<uint8_t*>(GetAddressForAllocationInfo(cur_info));
404       uint8_t* byte_end = byte_start + alloc_size;
405       callback(byte_start, byte_end, alloc_size, arg);
406       callback(nullptr, nullptr, 0, arg);
407     }
408     cur_info = cur_info->GetNextInfo();
409   }
410   CHECK_EQ(cur_info, end_info);
411 }
412 
ForEachMemMap(std::function<void (const MemMap &)> func) const413 void FreeListSpace::ForEachMemMap(std::function<void(const MemMap&)> func) const {
414   MutexLock mu(Thread::Current(), lock_);
415   func(allocation_info_map_);
416   func(mem_map_);
417 }
418 
RemoveFreePrev(AllocationInfo * info)419 void FreeListSpace::RemoveFreePrev(AllocationInfo* info) {
420   CHECK_GT(info->GetPrevFree(), 0U);
421   auto it = free_blocks_.lower_bound(info);
422   CHECK(it != free_blocks_.end());
423   CHECK_EQ(*it, info);
424   free_blocks_.erase(it);
425 }
426 
Free(Thread * self,mirror::Object * obj)427 size_t FreeListSpace::Free(Thread* self, mirror::Object* obj) {
428   DCHECK(Contains(obj)) << reinterpret_cast<void*>(Begin()) << " " << obj << " "
429                         << reinterpret_cast<void*>(End());
430   DCHECK_ALIGNED(obj, kAlignment);
431   AllocationInfo* info = GetAllocationInfoForAddress(reinterpret_cast<uintptr_t>(obj));
432   DCHECK(!info->IsFree());
433   const size_t allocation_size = info->ByteSize();
434   DCHECK_GT(allocation_size, 0U);
435   DCHECK_ALIGNED(allocation_size, kAlignment);
436 
437   // madvise the pages without lock
438   madvise(obj, allocation_size, MADV_DONTNEED);
439   if (kIsDebugBuild) {
440     // Can't disallow reads since we use them to find next chunks during coalescing.
441     CheckedCall(mprotect, __FUNCTION__, obj, allocation_size, PROT_READ);
442   }
443 
444   MutexLock mu(self, lock_);
445   info->SetByteSize(allocation_size, true);  // Mark as free.
446   // Look at the next chunk.
447   AllocationInfo* next_info = info->GetNextInfo();
448   // Calculate the start of the end free block.
449   uintptr_t free_end_start = reinterpret_cast<uintptr_t>(end_) - free_end_;
450   size_t prev_free_bytes = info->GetPrevFreeBytes();
451   size_t new_free_size = allocation_size;
452   if (prev_free_bytes != 0) {
453     // Coalesce with previous free chunk.
454     new_free_size += prev_free_bytes;
455     RemoveFreePrev(info);
456     info = info->GetPrevFreeInfo();
457     // The previous allocation info must not be free since we are supposed to always coalesce.
458     DCHECK_EQ(info->GetPrevFreeBytes(), 0U) << "Previous allocation was free";
459   }
460   uintptr_t next_addr = GetAddressForAllocationInfo(next_info);
461   if (next_addr >= free_end_start) {
462     // Easy case, the next chunk is the end free region.
463     CHECK_EQ(next_addr, free_end_start);
464     free_end_ += new_free_size;
465   } else {
466     AllocationInfo* new_free_info;
467     if (next_info->IsFree()) {
468       AllocationInfo* next_next_info = next_info->GetNextInfo();
469       // Next next info can't be free since we always coalesce.
470       DCHECK(!next_next_info->IsFree());
471       DCHECK_ALIGNED(next_next_info->ByteSize(), kAlignment);
472       new_free_info = next_next_info;
473       new_free_size += next_next_info->GetPrevFreeBytes();
474       RemoveFreePrev(next_next_info);
475     } else {
476       new_free_info = next_info;
477     }
478     new_free_info->SetPrevFreeBytes(new_free_size);
479     free_blocks_.insert(new_free_info);
480     info->SetByteSize(new_free_size, true);
481     DCHECK_EQ(info->GetNextInfo(), new_free_info);
482   }
483   --num_objects_allocated_;
484   DCHECK_LE(allocation_size, num_bytes_allocated_);
485   num_bytes_allocated_ -= allocation_size;
486   return allocation_size;
487 }
488 
AllocationSize(mirror::Object * obj,size_t * usable_size)489 size_t FreeListSpace::AllocationSize(mirror::Object* obj, size_t* usable_size) {
490   DCHECK(Contains(obj));
491   AllocationInfo* info = GetAllocationInfoForAddress(reinterpret_cast<uintptr_t>(obj));
492   DCHECK(!info->IsFree());
493   size_t alloc_size = info->ByteSize();
494   if (usable_size != nullptr) {
495     *usable_size = alloc_size;
496   }
497   return alloc_size;
498 }
499 
Alloc(Thread * self,size_t num_bytes,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)500 mirror::Object* FreeListSpace::Alloc(Thread* self, size_t num_bytes, size_t* bytes_allocated,
501                                      size_t* usable_size, size_t* bytes_tl_bulk_allocated) {
502   MutexLock mu(self, lock_);
503   const size_t allocation_size = RoundUp(num_bytes, kAlignment);
504   AllocationInfo temp_info;
505   temp_info.SetPrevFreeBytes(allocation_size);
506   temp_info.SetByteSize(0, false);
507   AllocationInfo* new_info;
508   // Find the smallest chunk at least num_bytes in size.
509   auto it = free_blocks_.lower_bound(&temp_info);
510   if (it != free_blocks_.end()) {
511     AllocationInfo* info = *it;
512     free_blocks_.erase(it);
513     // Fit our object in the previous allocation info free space.
514     new_info = info->GetPrevFreeInfo();
515     // Remove the newly allocated block from the info and update the prev_free_.
516     info->SetPrevFreeBytes(info->GetPrevFreeBytes() - allocation_size);
517     if (info->GetPrevFreeBytes() > 0) {
518       AllocationInfo* new_free = info - info->GetPrevFree();
519       new_free->SetPrevFreeBytes(0);
520       new_free->SetByteSize(info->GetPrevFreeBytes(), true);
521       // If there is remaining space, insert back into the free set.
522       free_blocks_.insert(info);
523     }
524   } else {
525     // Try to steal some memory from the free space at the end of the space.
526     if (LIKELY(free_end_ >= allocation_size)) {
527       // Fit our object at the start of the end free block.
528       new_info = GetAllocationInfoForAddress(reinterpret_cast<uintptr_t>(End()) - free_end_);
529       free_end_ -= allocation_size;
530     } else {
531       return nullptr;
532     }
533   }
534   DCHECK(bytes_allocated != nullptr);
535   *bytes_allocated = allocation_size;
536   if (usable_size != nullptr) {
537     *usable_size = allocation_size;
538   }
539   DCHECK(bytes_tl_bulk_allocated != nullptr);
540   *bytes_tl_bulk_allocated = allocation_size;
541   // Need to do these inside of the lock.
542   ++num_objects_allocated_;
543   ++total_objects_allocated_;
544   num_bytes_allocated_ += allocation_size;
545   total_bytes_allocated_ += allocation_size;
546   mirror::Object* obj = reinterpret_cast<mirror::Object*>(GetAddressForAllocationInfo(new_info));
547   // We always put our object at the start of the free block, there cannot be another free block
548   // before it.
549   if (kIsDebugBuild) {
550     CheckedCall(mprotect, __FUNCTION__, obj, allocation_size, PROT_READ | PROT_WRITE);
551   }
552   new_info->SetPrevFreeBytes(0);
553   new_info->SetByteSize(allocation_size, false);
554   return obj;
555 }
556 
Dump(std::ostream & os) const557 void FreeListSpace::Dump(std::ostream& os) const {
558   MutexLock mu(Thread::Current(), lock_);
559   os << GetName() << " -"
560      << " begin: " << reinterpret_cast<void*>(Begin())
561      << " end: " << reinterpret_cast<void*>(End()) << "\n";
562   uintptr_t free_end_start = reinterpret_cast<uintptr_t>(end_) - free_end_;
563   const AllocationInfo* cur_info =
564       GetAllocationInfoForAddress(reinterpret_cast<uintptr_t>(Begin()));
565   const AllocationInfo* end_info = GetAllocationInfoForAddress(free_end_start);
566   while (cur_info < end_info) {
567     size_t size = cur_info->ByteSize();
568     uintptr_t address = GetAddressForAllocationInfo(cur_info);
569     if (cur_info->IsFree()) {
570       os << "Free block at address: " << reinterpret_cast<const void*>(address)
571          << " of length " << size << " bytes\n";
572     } else {
573       os << "Large object at address: " << reinterpret_cast<const void*>(address)
574          << " of length " << size << " bytes\n";
575     }
576     cur_info = cur_info->GetNextInfo();
577   }
578   if (free_end_) {
579     os << "Free block at address: " << reinterpret_cast<const void*>(free_end_start)
580        << " of length " << free_end_ << " bytes\n";
581   }
582 }
583 
IsZygoteLargeObject(Thread * self ATTRIBUTE_UNUSED,mirror::Object * obj) const584 bool FreeListSpace::IsZygoteLargeObject(Thread* self ATTRIBUTE_UNUSED, mirror::Object* obj) const {
585   const AllocationInfo* info = GetAllocationInfoForAddress(reinterpret_cast<uintptr_t>(obj));
586   DCHECK(info != nullptr);
587   return info->IsZygoteObject();
588 }
589 
SetAllLargeObjectsAsZygoteObjects(Thread * self,bool set_mark_bit)590 void FreeListSpace::SetAllLargeObjectsAsZygoteObjects(Thread* self, bool set_mark_bit) {
591   MutexLock mu(self, lock_);
592   uintptr_t free_end_start = reinterpret_cast<uintptr_t>(end_) - free_end_;
593   for (AllocationInfo* cur_info = GetAllocationInfoForAddress(reinterpret_cast<uintptr_t>(Begin())),
594       *end_info = GetAllocationInfoForAddress(free_end_start); cur_info < end_info;
595       cur_info = cur_info->GetNextInfo()) {
596     if (!cur_info->IsFree()) {
597       cur_info->SetZygoteObject();
598       if (set_mark_bit) {
599         ObjPtr<mirror::Object> obj =
600             reinterpret_cast<mirror::Object*>(GetAddressForAllocationInfo(cur_info));
601         bool success = obj->AtomicSetMarkBit(0, 1);
602         CHECK(success);
603       }
604     }
605   }
606 }
607 
SweepCallback(size_t num_ptrs,mirror::Object ** ptrs,void * arg)608 void LargeObjectSpace::SweepCallback(size_t num_ptrs, mirror::Object** ptrs, void* arg) {
609   SweepCallbackContext* context = static_cast<SweepCallbackContext*>(arg);
610   space::LargeObjectSpace* space = context->space->AsLargeObjectSpace();
611   Thread* self = context->self;
612   Locks::heap_bitmap_lock_->AssertExclusiveHeld(self);
613   // If the bitmaps aren't swapped we need to clear the bits since the GC isn't going to re-swap
614   // the bitmaps as an optimization.
615   if (!context->swap_bitmaps) {
616     accounting::LargeObjectBitmap* bitmap = space->GetLiveBitmap();
617     for (size_t i = 0; i < num_ptrs; ++i) {
618       bitmap->Clear(ptrs[i]);
619     }
620   }
621   context->freed.objects += num_ptrs;
622   context->freed.bytes += space->FreeList(self, num_ptrs, ptrs);
623 }
624 
Sweep(bool swap_bitmaps)625 collector::ObjectBytePair LargeObjectSpace::Sweep(bool swap_bitmaps) {
626   if (Begin() >= End()) {
627     return collector::ObjectBytePair(0, 0);
628   }
629   accounting::LargeObjectBitmap* live_bitmap = GetLiveBitmap();
630   accounting::LargeObjectBitmap* mark_bitmap = GetMarkBitmap();
631   if (swap_bitmaps) {
632     std::swap(live_bitmap, mark_bitmap);
633   }
634   AllocSpace::SweepCallbackContext scc(swap_bitmaps, this);
635   std::pair<uint8_t*, uint8_t*> range = GetBeginEndAtomic();
636   accounting::LargeObjectBitmap::SweepWalk(*live_bitmap, *mark_bitmap,
637                                            reinterpret_cast<uintptr_t>(range.first),
638                                            reinterpret_cast<uintptr_t>(range.second),
639                                            SweepCallback,
640                                            &scc);
641   return scc.freed;
642 }
643 
LogFragmentationAllocFailure(std::ostream &,size_t)644 bool LargeObjectSpace::LogFragmentationAllocFailure(std::ostream& /*os*/,
645                                                     size_t /*failed_alloc_bytes*/) {
646   UNIMPLEMENTED(FATAL);
647   UNREACHABLE();
648 }
649 
GetBeginEndAtomic() const650 std::pair<uint8_t*, uint8_t*> LargeObjectMapSpace::GetBeginEndAtomic() const {
651   MutexLock mu(Thread::Current(), lock_);
652   return std::make_pair(Begin(), End());
653 }
654 
GetBeginEndAtomic() const655 std::pair<uint8_t*, uint8_t*> FreeListSpace::GetBeginEndAtomic() const {
656   MutexLock mu(Thread::Current(), lock_);
657   return std::make_pair(Begin(), End());
658 }
659 
660 }  // namespace space
661 }  // namespace gc
662 }  // namespace art
663