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_REQUIRES(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) REQUIRES(!lock_);
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       REQUIRES(!lock_);
137   size_t Free(Thread* self, mirror::Object* ptr) REQUIRES(!lock_);
138   void Walk(DlMallocSpace::WalkCallback, void* arg) OVERRIDE REQUIRES(!lock_);
139   // TODO: disabling thread safety analysis as this may be called when we already hold lock_.
140   bool Contains(const mirror::Object* obj) const NO_THREAD_SAFETY_ANALYSIS;
141 
142  protected:
143   struct LargeObject {
144     MemMap* mem_map;
145     bool is_zygote;
146   };
147   explicit LargeObjectMapSpace(const std::string& name);
~LargeObjectMapSpace()148   virtual ~LargeObjectMapSpace() {}
149 
150   bool IsZygoteLargeObject(Thread* self, mirror::Object* obj) const OVERRIDE REQUIRES(!lock_);
151   void SetAllLargeObjectsAsZygoteObjects(Thread* self) OVERRIDE REQUIRES(!lock_);
152 
153   // Used to ensure mutual exclusion when the allocation spaces data structures are being modified.
154   mutable Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
155   AllocationTrackingSafeMap<mirror::Object*, LargeObject, kAllocatorTagLOSMaps> large_objects_
156       GUARDED_BY(lock_);
157 };
158 
159 // A continuous large object space with a free-list to handle holes.
160 class FreeListSpace FINAL : public LargeObjectSpace {
161  public:
162   static constexpr size_t kAlignment = kPageSize;
163 
164   virtual ~FreeListSpace();
165   static FreeListSpace* Create(const std::string& name, uint8_t* requested_begin, size_t capacity);
166   size_t AllocationSize(mirror::Object* obj, size_t* usable_size) OVERRIDE
167       REQUIRES(lock_);
168   mirror::Object* Alloc(Thread* self, size_t num_bytes, size_t* bytes_allocated,
169                         size_t* usable_size, size_t* bytes_tl_bulk_allocated)
170       OVERRIDE REQUIRES(!lock_);
171   size_t Free(Thread* self, mirror::Object* obj) OVERRIDE REQUIRES(!lock_);
172   void Walk(DlMallocSpace::WalkCallback callback, void* arg) OVERRIDE REQUIRES(!lock_);
173   void Dump(std::ostream& os) const REQUIRES(!lock_);
174 
175  protected:
176   FreeListSpace(const std::string& name, MemMap* mem_map, uint8_t* begin, uint8_t* end);
GetSlotIndexForAddress(uintptr_t address)177   size_t GetSlotIndexForAddress(uintptr_t address) const {
178     DCHECK(Contains(reinterpret_cast<mirror::Object*>(address)));
179     return (address - reinterpret_cast<uintptr_t>(Begin())) / kAlignment;
180   }
181   size_t GetSlotIndexForAllocationInfo(const AllocationInfo* info) const;
182   AllocationInfo* GetAllocationInfoForAddress(uintptr_t address);
183   const AllocationInfo* GetAllocationInfoForAddress(uintptr_t address) const;
GetAllocationAddressForSlot(size_t slot)184   uintptr_t GetAllocationAddressForSlot(size_t slot) const {
185     return reinterpret_cast<uintptr_t>(Begin()) + slot * kAlignment;
186   }
GetAddressForAllocationInfo(const AllocationInfo * info)187   uintptr_t GetAddressForAllocationInfo(const AllocationInfo* info) const {
188     return GetAllocationAddressForSlot(GetSlotIndexForAllocationInfo(info));
189   }
190   // Removes header from the free blocks set by finding the corresponding iterator and erasing it.
191   void RemoveFreePrev(AllocationInfo* info) REQUIRES(lock_);
192   bool IsZygoteLargeObject(Thread* self, mirror::Object* obj) const OVERRIDE;
193   void SetAllLargeObjectsAsZygoteObjects(Thread* self) OVERRIDE REQUIRES(!lock_);
194 
195   class SortByPrevFree {
196    public:
197     bool operator()(const AllocationInfo* a, const AllocationInfo* b) const;
198   };
199   typedef std::set<AllocationInfo*, SortByPrevFree,
200                    TrackingAllocator<AllocationInfo*, kAllocatorTagLOSFreeList>> FreeBlocks;
201 
202   // There is not footer for any allocations at the end of the space, so we keep track of how much
203   // free space there is at the end manually.
204   std::unique_ptr<MemMap> mem_map_;
205   // Side table for allocation info, one per page.
206   std::unique_ptr<MemMap> allocation_info_map_;
207   AllocationInfo* allocation_info_;
208 
209   mutable Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
210   // Free bytes at the end of the space.
211   size_t free_end_ GUARDED_BY(lock_);
212   FreeBlocks free_blocks_ GUARDED_BY(lock_);
213 };
214 
215 }  // namespace space
216 }  // namespace gc
217 }  // namespace art
218 
219 #endif  // ART_RUNTIME_GC_SPACE_LARGE_OBJECT_SPACE_H_
220