1 /*
2 * Copyright (C) 2014 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_REGION_SPACE_INL_H_
18 #define ART_RUNTIME_GC_SPACE_REGION_SPACE_INL_H_
19
20 #include "region_space.h"
21 #include "thread-current-inl.h"
22
23 namespace art {
24 namespace gc {
25 namespace space {
26
Alloc(Thread * self ATTRIBUTE_UNUSED,size_t num_bytes,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)27 inline mirror::Object* RegionSpace::Alloc(Thread* self ATTRIBUTE_UNUSED,
28 size_t num_bytes,
29 /* out */ size_t* bytes_allocated,
30 /* out */ size_t* usable_size,
31 /* out */ size_t* bytes_tl_bulk_allocated) {
32 num_bytes = RoundUp(num_bytes, kAlignment);
33 return AllocNonvirtual<false>(num_bytes, bytes_allocated, usable_size,
34 bytes_tl_bulk_allocated);
35 }
36
AllocThreadUnsafe(Thread * self,size_t num_bytes,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)37 inline mirror::Object* RegionSpace::AllocThreadUnsafe(Thread* self,
38 size_t num_bytes,
39 /* out */ size_t* bytes_allocated,
40 /* out */ size_t* usable_size,
41 /* out */ size_t* bytes_tl_bulk_allocated) {
42 Locks::mutator_lock_->AssertExclusiveHeld(self);
43 return Alloc(self, num_bytes, bytes_allocated, usable_size, bytes_tl_bulk_allocated);
44 }
45
46 template<bool kForEvac>
AllocNonvirtual(size_t num_bytes,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)47 inline mirror::Object* RegionSpace::AllocNonvirtual(size_t num_bytes,
48 /* out */ size_t* bytes_allocated,
49 /* out */ size_t* usable_size,
50 /* out */ size_t* bytes_tl_bulk_allocated) {
51 DCHECK_ALIGNED(num_bytes, kAlignment);
52 mirror::Object* obj;
53 if (LIKELY(num_bytes <= kRegionSize)) {
54 // Non-large object.
55 obj = (kForEvac ? evac_region_ : current_region_)->Alloc(num_bytes,
56 bytes_allocated,
57 usable_size,
58 bytes_tl_bulk_allocated);
59 if (LIKELY(obj != nullptr)) {
60 return obj;
61 }
62 MutexLock mu(Thread::Current(), region_lock_);
63 // Retry with current region since another thread may have updated it.
64 obj = (kForEvac ? evac_region_ : current_region_)->Alloc(num_bytes,
65 bytes_allocated,
66 usable_size,
67 bytes_tl_bulk_allocated);
68 if (LIKELY(obj != nullptr)) {
69 return obj;
70 }
71 Region* r = AllocateRegion(kForEvac);
72 if (LIKELY(r != nullptr)) {
73 obj = r->Alloc(num_bytes, bytes_allocated, usable_size, bytes_tl_bulk_allocated);
74 CHECK(obj != nullptr);
75 // Do our allocation before setting the region, this makes sure no threads race ahead
76 // and fill in the region before we allocate the object. b/63153464
77 if (kForEvac) {
78 evac_region_ = r;
79 } else {
80 current_region_ = r;
81 }
82 return obj;
83 }
84 } else {
85 // Large object.
86 obj = AllocLarge<kForEvac>(num_bytes, bytes_allocated, usable_size, bytes_tl_bulk_allocated);
87 if (LIKELY(obj != nullptr)) {
88 return obj;
89 }
90 }
91 return nullptr;
92 }
93
Alloc(size_t num_bytes,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)94 inline mirror::Object* RegionSpace::Region::Alloc(size_t num_bytes,
95 /* out */ size_t* bytes_allocated,
96 /* out */ size_t* usable_size,
97 /* out */ size_t* bytes_tl_bulk_allocated) {
98 DCHECK(IsAllocated() && IsInToSpace());
99 DCHECK_ALIGNED(num_bytes, kAlignment);
100 uint8_t* old_top;
101 uint8_t* new_top;
102 do {
103 old_top = top_.LoadRelaxed();
104 new_top = old_top + num_bytes;
105 if (UNLIKELY(new_top > end_)) {
106 return nullptr;
107 }
108 } while (!top_.CompareAndSetWeakRelaxed(old_top, new_top));
109 objects_allocated_.FetchAndAddRelaxed(1);
110 DCHECK_LE(Top(), end_);
111 DCHECK_LT(old_top, end_);
112 DCHECK_LE(new_top, end_);
113 *bytes_allocated = num_bytes;
114 if (usable_size != nullptr) {
115 *usable_size = num_bytes;
116 }
117 *bytes_tl_bulk_allocated = num_bytes;
118 return reinterpret_cast<mirror::Object*>(old_top);
119 }
120
121 template<RegionSpace::RegionType kRegionType>
GetBytesAllocatedInternal()122 inline uint64_t RegionSpace::GetBytesAllocatedInternal() {
123 uint64_t bytes = 0;
124 MutexLock mu(Thread::Current(), region_lock_);
125 for (size_t i = 0; i < num_regions_; ++i) {
126 Region* r = ®ions_[i];
127 if (r->IsFree()) {
128 continue;
129 }
130 switch (kRegionType) {
131 case RegionType::kRegionTypeAll:
132 bytes += r->BytesAllocated();
133 break;
134 case RegionType::kRegionTypeFromSpace:
135 if (r->IsInFromSpace()) {
136 bytes += r->BytesAllocated();
137 }
138 break;
139 case RegionType::kRegionTypeUnevacFromSpace:
140 if (r->IsInUnevacFromSpace()) {
141 bytes += r->BytesAllocated();
142 }
143 break;
144 case RegionType::kRegionTypeToSpace:
145 if (r->IsInToSpace()) {
146 bytes += r->BytesAllocated();
147 }
148 break;
149 default:
150 LOG(FATAL) << "Unexpected space type : " << kRegionType;
151 }
152 }
153 return bytes;
154 }
155
156 template<RegionSpace::RegionType kRegionType>
GetObjectsAllocatedInternal()157 inline uint64_t RegionSpace::GetObjectsAllocatedInternal() {
158 uint64_t bytes = 0;
159 MutexLock mu(Thread::Current(), region_lock_);
160 for (size_t i = 0; i < num_regions_; ++i) {
161 Region* r = ®ions_[i];
162 if (r->IsFree()) {
163 continue;
164 }
165 switch (kRegionType) {
166 case RegionType::kRegionTypeAll:
167 bytes += r->ObjectsAllocated();
168 break;
169 case RegionType::kRegionTypeFromSpace:
170 if (r->IsInFromSpace()) {
171 bytes += r->ObjectsAllocated();
172 }
173 break;
174 case RegionType::kRegionTypeUnevacFromSpace:
175 if (r->IsInUnevacFromSpace()) {
176 bytes += r->ObjectsAllocated();
177 }
178 break;
179 case RegionType::kRegionTypeToSpace:
180 if (r->IsInToSpace()) {
181 bytes += r->ObjectsAllocated();
182 }
183 break;
184 default:
185 LOG(FATAL) << "Unexpected space type : " << kRegionType;
186 }
187 }
188 return bytes;
189 }
190
191 template<bool kToSpaceOnly, typename Visitor>
WalkInternal(Visitor && visitor)192 inline void RegionSpace::WalkInternal(Visitor&& visitor) {
193 // TODO: MutexLock on region_lock_ won't work due to lock order
194 // issues (the classloader classes lock and the monitor lock). We
195 // call this with threads suspended.
196 Locks::mutator_lock_->AssertExclusiveHeld(Thread::Current());
197 for (size_t i = 0; i < num_regions_; ++i) {
198 Region* r = ®ions_[i];
199 if (r->IsFree() || (kToSpaceOnly && !r->IsInToSpace())) {
200 continue;
201 }
202 if (r->IsLarge()) {
203 // Avoid visiting dead large objects since they may contain dangling pointers to the
204 // from-space.
205 DCHECK_GT(r->LiveBytes(), 0u) << "Visiting dead large object";
206 mirror::Object* obj = reinterpret_cast<mirror::Object*>(r->Begin());
207 DCHECK(obj->GetClass() != nullptr);
208 visitor(obj);
209 } else if (r->IsLargeTail()) {
210 // Do nothing.
211 } else {
212 // For newly allocated and evacuated regions, live bytes will be -1.
213 uint8_t* pos = r->Begin();
214 uint8_t* top = r->Top();
215 const bool need_bitmap =
216 r->LiveBytes() != static_cast<size_t>(-1) &&
217 r->LiveBytes() != static_cast<size_t>(top - pos);
218 if (need_bitmap) {
219 GetLiveBitmap()->VisitMarkedRange(
220 reinterpret_cast<uintptr_t>(pos),
221 reinterpret_cast<uintptr_t>(top),
222 visitor);
223 } else {
224 while (pos < top) {
225 mirror::Object* obj = reinterpret_cast<mirror::Object*>(pos);
226 if (obj->GetClass<kDefaultVerifyFlags, kWithoutReadBarrier>() != nullptr) {
227 visitor(obj);
228 pos = reinterpret_cast<uint8_t*>(GetNextObject(obj));
229 } else {
230 break;
231 }
232 }
233 }
234 }
235 }
236 }
237
GetNextObject(mirror::Object * obj)238 inline mirror::Object* RegionSpace::GetNextObject(mirror::Object* obj) {
239 const uintptr_t position = reinterpret_cast<uintptr_t>(obj) + obj->SizeOf();
240 return reinterpret_cast<mirror::Object*>(RoundUp(position, kAlignment));
241 }
242
243 template<bool kForEvac>
AllocLarge(size_t num_bytes,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)244 inline mirror::Object* RegionSpace::AllocLarge(size_t num_bytes,
245 /* out */ size_t* bytes_allocated,
246 /* out */ size_t* usable_size,
247 /* out */ size_t* bytes_tl_bulk_allocated) {
248 DCHECK_ALIGNED(num_bytes, kAlignment);
249 DCHECK_GT(num_bytes, kRegionSize);
250 size_t num_regs = RoundUp(num_bytes, kRegionSize) / kRegionSize;
251 DCHECK_GT(num_regs, 0U);
252 DCHECK_LT((num_regs - 1) * kRegionSize, num_bytes);
253 DCHECK_LE(num_bytes, num_regs * kRegionSize);
254 MutexLock mu(Thread::Current(), region_lock_);
255 if (!kForEvac) {
256 // Retain sufficient free regions for full evacuation.
257 if ((num_non_free_regions_ + num_regs) * 2 > num_regions_) {
258 return nullptr;
259 }
260 }
261 // Find a large enough set of contiguous free regions.
262 size_t left = 0;
263 while (left + num_regs - 1 < num_regions_) {
264 bool found = true;
265 size_t right = left;
266 DCHECK_LT(right, left + num_regs)
267 << "The inner loop Should iterate at least once";
268 while (right < left + num_regs) {
269 if (regions_[right].IsFree()) {
270 ++right;
271 } else {
272 found = false;
273 break;
274 }
275 }
276 if (found) {
277 // `right` points to the one region past the last free region.
278 DCHECK_EQ(left + num_regs, right);
279 Region* first_reg = ®ions_[left];
280 DCHECK(first_reg->IsFree());
281 first_reg->UnfreeLarge(this, time_);
282 if (kForEvac) {
283 ++num_evac_regions_;
284 } else {
285 ++num_non_free_regions_;
286 }
287 size_t allocated = num_regs * kRegionSize;
288 // We make 'top' all usable bytes, as the caller of this
289 // allocation may use all of 'usable_size' (see mirror::Array::Alloc).
290 first_reg->SetTop(first_reg->Begin() + allocated);
291 for (size_t p = left + 1; p < right; ++p) {
292 DCHECK_LT(p, num_regions_);
293 DCHECK(regions_[p].IsFree());
294 regions_[p].UnfreeLargeTail(this, time_);
295 if (kForEvac) {
296 ++num_evac_regions_;
297 } else {
298 ++num_non_free_regions_;
299 }
300 }
301 *bytes_allocated = allocated;
302 if (usable_size != nullptr) {
303 *usable_size = allocated;
304 }
305 *bytes_tl_bulk_allocated = allocated;
306 return reinterpret_cast<mirror::Object*>(first_reg->Begin());
307 } else {
308 // right points to the non-free region. Start with the one after it.
309 left = right + 1;
310 }
311 }
312 return nullptr;
313 }
314
315 template<bool kForEvac>
FreeLarge(mirror::Object * large_obj,size_t bytes_allocated)316 inline void RegionSpace::FreeLarge(mirror::Object* large_obj, size_t bytes_allocated) {
317 DCHECK(Contains(large_obj));
318 DCHECK_ALIGNED(large_obj, kRegionSize);
319 MutexLock mu(Thread::Current(), region_lock_);
320 uint8_t* begin_addr = reinterpret_cast<uint8_t*>(large_obj);
321 uint8_t* end_addr = AlignUp(reinterpret_cast<uint8_t*>(large_obj) + bytes_allocated, kRegionSize);
322 CHECK_LT(begin_addr, end_addr);
323 for (uint8_t* addr = begin_addr; addr < end_addr; addr += kRegionSize) {
324 Region* reg = RefToRegionLocked(reinterpret_cast<mirror::Object*>(addr));
325 if (addr == begin_addr) {
326 DCHECK(reg->IsLarge());
327 } else {
328 DCHECK(reg->IsLargeTail());
329 }
330 reg->Clear(/*zero_and_release_pages*/true);
331 if (kForEvac) {
332 --num_evac_regions_;
333 } else {
334 --num_non_free_regions_;
335 }
336 }
337 if (end_addr < Limit()) {
338 // If we aren't at the end of the space, check that the next region is not a large tail.
339 Region* following_reg = RefToRegionLocked(reinterpret_cast<mirror::Object*>(end_addr));
340 DCHECK(!following_reg->IsLargeTail());
341 }
342 }
343
BytesAllocated()344 inline size_t RegionSpace::Region::BytesAllocated() const {
345 if (IsLarge()) {
346 DCHECK_LT(begin_ + kRegionSize, Top());
347 return static_cast<size_t>(Top() - begin_);
348 } else if (IsLargeTail()) {
349 DCHECK_EQ(begin_, Top());
350 return 0;
351 } else {
352 DCHECK(IsAllocated()) << "state=" << state_;
353 DCHECK_LE(begin_, Top());
354 size_t bytes;
355 if (is_a_tlab_) {
356 bytes = thread_->GetThreadLocalBytesAllocated();
357 } else {
358 bytes = static_cast<size_t>(Top() - begin_);
359 }
360 DCHECK_LE(bytes, kRegionSize);
361 return bytes;
362 }
363 }
364
ObjectsAllocated()365 inline size_t RegionSpace::Region::ObjectsAllocated() const {
366 if (IsLarge()) {
367 DCHECK_LT(begin_ + kRegionSize, Top());
368 DCHECK_EQ(objects_allocated_.LoadRelaxed(), 0U);
369 return 1;
370 } else if (IsLargeTail()) {
371 DCHECK_EQ(begin_, Top());
372 DCHECK_EQ(objects_allocated_.LoadRelaxed(), 0U);
373 return 0;
374 } else {
375 DCHECK(IsAllocated()) << "state=" << state_;
376 return objects_allocated_;
377 }
378 }
379
380 } // namespace space
381 } // namespace gc
382 } // namespace art
383
384 #endif // ART_RUNTIME_GC_SPACE_REGION_SPACE_INL_H_
385