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 #ifndef ART_RUNTIME_GC_SPACE_LARGE_OBJECT_SPACE_H_
18 #define ART_RUNTIME_GC_SPACE_LARGE_OBJECT_SPACE_H_
19 
20 #include "base/allocator.h"
21 #include "dlmalloc_space.h"
22 #include "safe_map.h"
23 #include "space.h"
24 
25 #include <set>
26 #include <vector>
27 
28 namespace art {
29 namespace gc {
30 namespace space {
31 
32 class AllocationInfo;
33 
34 enum class LargeObjectSpaceType {
35   kDisabled,
36   kMap,
37   kFreeList,
38 };
39 
40 // Abstraction implemented by all large object spaces.
41 class LargeObjectSpace : public DiscontinuousSpace, public AllocSpace {
42  public:
GetType()43   SpaceType GetType() const OVERRIDE {
44     return kSpaceTypeLargeObjectSpace;
45   }
46   void SwapBitmaps();
47   void CopyLiveToMarked();
48   virtual void Walk(DlMallocSpace::WalkCallback, void* arg) = 0;
~LargeObjectSpace()49   virtual ~LargeObjectSpace() {}
50 
GetBytesAllocated()51   uint64_t GetBytesAllocated() OVERRIDE {
52     return num_bytes_allocated_;
53   }
GetObjectsAllocated()54   uint64_t GetObjectsAllocated() OVERRIDE {
55     return num_objects_allocated_;
56   }
GetTotalBytesAllocated()57   uint64_t GetTotalBytesAllocated() const {
58     return total_bytes_allocated_;
59   }
GetTotalObjectsAllocated()60   uint64_t GetTotalObjectsAllocated() const {
61     return total_objects_allocated_;
62   }
63   size_t FreeList(Thread* self, size_t num_ptrs, mirror::Object** ptrs) OVERRIDE;
64   // LargeObjectSpaces don't have thread local state.
RevokeThreadLocalBuffers(art::Thread *)65   size_t RevokeThreadLocalBuffers(art::Thread*) OVERRIDE {
66     return 0U;
67   }
RevokeAllThreadLocalBuffers()68   size_t RevokeAllThreadLocalBuffers() OVERRIDE {
69     return 0U;
70   }
IsAllocSpace()71   bool IsAllocSpace() const OVERRIDE {
72     return true;
73   }
AsAllocSpace()74   AllocSpace* AsAllocSpace() OVERRIDE {
75     return this;
76   }
77   collector::ObjectBytePair Sweep(bool swap_bitmaps);
CanMoveObjects()78   virtual bool CanMoveObjects() const OVERRIDE {
79     return false;
80   }
81   // Current address at which the space begins, which may vary as the space is filled.
Begin()82   uint8_t* Begin() const {
83     return begin_;
84   }
85   // Current address at which the space ends, which may vary as the space is filled.
End()86   uint8_t* End() const {
87     return end_;
88   }
89   // Current size of space
Size()90   size_t Size() const {
91     return End() - Begin();
92   }
93   // Return true if we contain the specified address.
Contains(const mirror::Object * obj)94   bool Contains(const mirror::Object* obj) const {
95     const uint8_t* byte_obj = reinterpret_cast<const uint8_t*>(obj);
96     return Begin() <= byte_obj && byte_obj < End();
97   }
98   void LogFragmentationAllocFailure(std::ostream& os, size_t failed_alloc_bytes) OVERRIDE
99       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
100 
101   // Return true if the large object is a zygote large object. Potentially slow.
102   virtual bool IsZygoteLargeObject(Thread* self, mirror::Object* obj) const = 0;
103   // Called when we create the zygote space, mark all existing large objects as zygote large
104   // objects.
105   virtual void SetAllLargeObjectsAsZygoteObjects(Thread* self) = 0;
106 
107  protected:
108   explicit LargeObjectSpace(const std::string& name, uint8_t* begin, uint8_t* end);
109   static void SweepCallback(size_t num_ptrs, mirror::Object** ptrs, void* arg);
110 
111   // Approximate number of bytes which have been allocated into the space.
112   uint64_t num_bytes_allocated_;
113   uint64_t num_objects_allocated_;
114   uint64_t total_bytes_allocated_;
115   uint64_t total_objects_allocated_;
116   // Begin and end, may change as more large objects are allocated.
117   uint8_t* begin_;
118   uint8_t* end_;
119 
120   friend class Space;
121 
122  private:
123   DISALLOW_COPY_AND_ASSIGN(LargeObjectSpace);
124 };
125 
126 // A discontinuous large object space implemented by individual mmap/munmap calls.
127 class LargeObjectMapSpace : public LargeObjectSpace {
128  public:
129   // Creates a large object space. Allocations into the large object space use memory maps instead
130   // of malloc.
131   static LargeObjectMapSpace* Create(const std::string& name);
132   // Return the storage space required by obj.
133   size_t AllocationSize(mirror::Object* obj, size_t* usable_size);
134   mirror::Object* Alloc(Thread* self, size_t num_bytes, size_t* bytes_allocated,
135                         size_t* usable_size, size_t* bytes_tl_bulk_allocated);
136   size_t Free(Thread* self, mirror::Object* ptr);
137   void Walk(DlMallocSpace::WalkCallback, void* arg) OVERRIDE LOCKS_EXCLUDED(lock_);
138   // TODO: disabling thread safety analysis as this may be called when we already hold lock_.
139   bool Contains(const mirror::Object* obj) const NO_THREAD_SAFETY_ANALYSIS;
140 
141  protected:
142   struct LargeObject {
143     MemMap* mem_map;
144     bool is_zygote;
145   };
146   explicit LargeObjectMapSpace(const std::string& name);
~LargeObjectMapSpace()147   virtual ~LargeObjectMapSpace() {}
148 
149   bool IsZygoteLargeObject(Thread* self, mirror::Object* obj) const OVERRIDE LOCKS_EXCLUDED(lock_);
150   void SetAllLargeObjectsAsZygoteObjects(Thread* self) OVERRIDE LOCKS_EXCLUDED(lock_);
151 
152   // Used to ensure mutual exclusion when the allocation spaces data structures are being modified.
153   mutable Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
154   AllocationTrackingSafeMap<mirror::Object*, LargeObject, kAllocatorTagLOSMaps> large_objects_
155       GUARDED_BY(lock_);
156 };
157 
158 // A continuous large object space with a free-list to handle holes.
159 class FreeListSpace FINAL : public LargeObjectSpace {
160  public:
161   static constexpr size_t kAlignment = kPageSize;
162 
163   virtual ~FreeListSpace();
164   static FreeListSpace* Create(const std::string& name, uint8_t* requested_begin, size_t capacity);
165   size_t AllocationSize(mirror::Object* obj, size_t* usable_size) OVERRIDE
166       EXCLUSIVE_LOCKS_REQUIRED(lock_);
167   mirror::Object* Alloc(Thread* self, size_t num_bytes, size_t* bytes_allocated,
168                         size_t* usable_size, size_t* bytes_tl_bulk_allocated) OVERRIDE;
169   size_t Free(Thread* self, mirror::Object* obj) OVERRIDE;
170   void Walk(DlMallocSpace::WalkCallback callback, void* arg) OVERRIDE LOCKS_EXCLUDED(lock_);
171   void Dump(std::ostream& os) const;
172 
173  protected:
174   FreeListSpace(const std::string& name, MemMap* mem_map, uint8_t* begin, uint8_t* end);
GetSlotIndexForAddress(uintptr_t address)175   size_t GetSlotIndexForAddress(uintptr_t address) const {
176     DCHECK(Contains(reinterpret_cast<mirror::Object*>(address)));
177     return (address - reinterpret_cast<uintptr_t>(Begin())) / kAlignment;
178   }
179   size_t GetSlotIndexForAllocationInfo(const AllocationInfo* info) const;
180   AllocationInfo* GetAllocationInfoForAddress(uintptr_t address);
181   const AllocationInfo* GetAllocationInfoForAddress(uintptr_t address) const;
GetAllocationAddressForSlot(size_t slot)182   uintptr_t GetAllocationAddressForSlot(size_t slot) const {
183     return reinterpret_cast<uintptr_t>(Begin()) + slot * kAlignment;
184   }
GetAddressForAllocationInfo(const AllocationInfo * info)185   uintptr_t GetAddressForAllocationInfo(const AllocationInfo* info) const {
186     return GetAllocationAddressForSlot(GetSlotIndexForAllocationInfo(info));
187   }
188   // Removes header from the free blocks set by finding the corresponding iterator and erasing it.
189   void RemoveFreePrev(AllocationInfo* info) EXCLUSIVE_LOCKS_REQUIRED(lock_);
190   bool IsZygoteLargeObject(Thread* self, mirror::Object* obj) const OVERRIDE;
191   void SetAllLargeObjectsAsZygoteObjects(Thread* self) OVERRIDE;
192 
193   class SortByPrevFree {
194    public:
195     bool operator()(const AllocationInfo* a, const AllocationInfo* b) const;
196   };
197   typedef std::set<AllocationInfo*, SortByPrevFree,
198                    TrackingAllocator<AllocationInfo*, kAllocatorTagLOSFreeList>> FreeBlocks;
199 
200   // There is not footer for any allocations at the end of the space, so we keep track of how much
201   // free space there is at the end manually.
202   std::unique_ptr<MemMap> mem_map_;
203   // Side table for allocation info, one per page.
204   std::unique_ptr<MemMap> allocation_info_map_;
205   AllocationInfo* allocation_info_;
206 
207   mutable Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
208   // Free bytes at the end of the space.
209   size_t free_end_ GUARDED_BY(lock_);
210   FreeBlocks free_blocks_ GUARDED_BY(lock_);
211 };
212 
213 }  // namespace space
214 }  // namespace gc
215 }  // namespace art
216 
217 #endif  // ART_RUNTIME_GC_SPACE_LARGE_OBJECT_SPACE_H_
218