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
28namespace art {
29namespace gc {
30namespace space {
31
32class AllocationInfo;
33
34enum class LargeObjectSpaceType {
35  kDisabled,
36  kMap,
37  kFreeList,
38};
39
40// Abstraction implemented by all large object spaces.
41class LargeObjectSpace : public DiscontinuousSpace, public AllocSpace {
42 public:
43  SpaceType GetType() const OVERRIDE {
44    return kSpaceTypeLargeObjectSpace;
45  }
46  void SwapBitmaps();
47  void CopyLiveToMarked();
48  virtual void Walk(DlMallocSpace::WalkCallback, void* arg) = 0;
49  virtual ~LargeObjectSpace() {}
50
51  uint64_t GetBytesAllocated() OVERRIDE {
52    return num_bytes_allocated_;
53  }
54  uint64_t GetObjectsAllocated() OVERRIDE {
55    return num_objects_allocated_;
56  }
57  uint64_t GetTotalBytesAllocated() const {
58    return total_bytes_allocated_;
59  }
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.
65  size_t RevokeThreadLocalBuffers(art::Thread*) OVERRIDE {
66    return 0U;
67  }
68  size_t RevokeAllThreadLocalBuffers() OVERRIDE {
69    return 0U;
70  }
71  bool IsAllocSpace() const OVERRIDE {
72    return true;
73  }
74  AllocSpace* AsAllocSpace() OVERRIDE {
75    return this;
76  }
77  collector::ObjectBytePair Sweep(bool swap_bitmaps);
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.
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.
86  uint8_t* End() const {
87    return end_;
88  }
89  // Current size of space
90  size_t Size() const {
91    return End() - Begin();
92  }
93  // Return true if we contain the specified address.
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.
127class 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);
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.
160class 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);
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;
184  uintptr_t GetAllocationAddressForSlot(size_t slot) const {
185    return reinterpret_cast<uintptr_t>(Begin()) + slot * kAlignment;
186  }
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