1 /*
2 * Copyright (C) 2013 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 "rosalloc-inl.h"
18
19 #include <list>
20 #include <map>
21 #include <sstream>
22 #include <vector>
23
24 #include "android-base/stringprintf.h"
25
26 #include "base/logging.h" // For VLOG
27 #include "base/memory_tool.h"
28 #include "base/mem_map.h"
29 #include "base/mutex-inl.h"
30 #include "gc/space/memory_tool_settings.h"
31 #include "mirror/class-inl.h"
32 #include "mirror/object-inl.h"
33 #include "mirror/object.h"
34 #include "thread-current-inl.h"
35 #include "thread_list.h"
36
37 namespace art {
38 namespace gc {
39 namespace allocator {
40
41 using android::base::StringPrintf;
42
43 static constexpr bool kUsePrefetchDuringAllocRun = false;
44 static constexpr bool kPrefetchNewRunDataByZeroing = false;
45 static constexpr size_t kPrefetchStride = 64;
46
47 size_t RosAlloc::bracketSizes[kNumOfSizeBrackets];
48 size_t RosAlloc::numOfPages[kNumOfSizeBrackets];
49 size_t RosAlloc::numOfSlots[kNumOfSizeBrackets];
50 size_t RosAlloc::headerSizes[kNumOfSizeBrackets];
51 bool RosAlloc::initialized_ = false;
52 size_t RosAlloc::dedicated_full_run_storage_[kPageSize / sizeof(size_t)] = { 0 };
53 RosAlloc::Run* RosAlloc::dedicated_full_run_ =
54 reinterpret_cast<RosAlloc::Run*>(dedicated_full_run_storage_);
55
RosAlloc(void * base,size_t capacity,size_t max_capacity,PageReleaseMode page_release_mode,bool running_on_memory_tool,size_t page_release_size_threshold)56 RosAlloc::RosAlloc(void* base, size_t capacity, size_t max_capacity,
57 PageReleaseMode page_release_mode, bool running_on_memory_tool,
58 size_t page_release_size_threshold)
59 : base_(reinterpret_cast<uint8_t*>(base)), footprint_(capacity),
60 capacity_(capacity), max_capacity_(max_capacity),
61 lock_("rosalloc global lock", kRosAllocGlobalLock),
62 bulk_free_lock_("rosalloc bulk free lock", kRosAllocBulkFreeLock),
63 page_release_mode_(page_release_mode),
64 page_release_size_threshold_(page_release_size_threshold),
65 is_running_on_memory_tool_(running_on_memory_tool) {
66 DCHECK_ALIGNED(base, kPageSize);
67 DCHECK_EQ(RoundUp(capacity, kPageSize), capacity);
68 DCHECK_EQ(RoundUp(max_capacity, kPageSize), max_capacity);
69 CHECK_LE(capacity, max_capacity);
70 CHECK_ALIGNED(page_release_size_threshold_, kPageSize);
71 // Zero the memory explicitly (don't rely on that the mem map is zero-initialized).
72 if (!kMadviseZeroes) {
73 memset(base_, 0, max_capacity);
74 }
75 CHECK_EQ(madvise(base_, max_capacity, MADV_DONTNEED), 0);
76 if (!initialized_) {
77 Initialize();
78 }
79 VLOG(heap) << "RosAlloc base="
80 << std::hex << (intptr_t)base_ << ", end="
81 << std::hex << (intptr_t)(base_ + capacity_)
82 << ", capacity=" << std::dec << capacity_
83 << ", max_capacity=" << std::dec << max_capacity_;
84 for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
85 size_bracket_lock_names_[i] =
86 StringPrintf("an rosalloc size bracket %d lock", static_cast<int>(i));
87 size_bracket_locks_[i] = new Mutex(size_bracket_lock_names_[i].c_str(), kRosAllocBracketLock);
88 current_runs_[i] = dedicated_full_run_;
89 }
90 DCHECK_EQ(footprint_, capacity_);
91 size_t num_of_pages = footprint_ / kPageSize;
92 size_t max_num_of_pages = max_capacity_ / kPageSize;
93 std::string error_msg;
94 page_map_mem_map_ = MemMap::MapAnonymous("rosalloc page map",
95 RoundUp(max_num_of_pages, kPageSize),
96 PROT_READ | PROT_WRITE,
97 /*low_4gb=*/ false,
98 &error_msg);
99 CHECK(page_map_mem_map_.IsValid()) << "Couldn't allocate the page map : " << error_msg;
100 page_map_ = page_map_mem_map_.Begin();
101 page_map_size_ = num_of_pages;
102 max_page_map_size_ = max_num_of_pages;
103 free_page_run_size_map_.resize(num_of_pages);
104 FreePageRun* free_pages = reinterpret_cast<FreePageRun*>(base_);
105 if (kIsDebugBuild) {
106 free_pages->magic_num_ = kMagicNumFree;
107 }
108 free_pages->SetByteSize(this, capacity_);
109 DCHECK_EQ(capacity_ % kPageSize, static_cast<size_t>(0));
110 DCHECK(free_pages->IsFree());
111 free_pages->ReleasePages(this);
112 DCHECK(free_pages->IsFree());
113 free_page_runs_.insert(free_pages);
114 if (kTraceRosAlloc) {
115 LOG(INFO) << "RosAlloc::RosAlloc() : Inserted run 0x" << std::hex
116 << reinterpret_cast<intptr_t>(free_pages)
117 << " into free_page_runs_";
118 }
119 }
120
~RosAlloc()121 RosAlloc::~RosAlloc() {
122 for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
123 delete size_bracket_locks_[i];
124 }
125 if (is_running_on_memory_tool_) {
126 MEMORY_TOOL_MAKE_DEFINED(base_, capacity_);
127 }
128 }
129
AllocPages(Thread * self,size_t num_pages,uint8_t page_map_type)130 void* RosAlloc::AllocPages(Thread* self, size_t num_pages, uint8_t page_map_type) {
131 lock_.AssertHeld(self);
132 DCHECK(page_map_type == kPageMapRun || page_map_type == kPageMapLargeObject);
133 FreePageRun* res = nullptr;
134 const size_t req_byte_size = num_pages * kPageSize;
135 // Find the lowest address free page run that's large enough.
136 for (auto it = free_page_runs_.begin(); it != free_page_runs_.end(); ) {
137 FreePageRun* fpr = *it;
138 DCHECK(fpr->IsFree());
139 size_t fpr_byte_size = fpr->ByteSize(this);
140 DCHECK_EQ(fpr_byte_size % kPageSize, static_cast<size_t>(0));
141 if (req_byte_size <= fpr_byte_size) {
142 // Found one.
143 it = free_page_runs_.erase(it);
144 if (kTraceRosAlloc) {
145 LOG(INFO) << "RosAlloc::AllocPages() : Erased run 0x"
146 << std::hex << reinterpret_cast<intptr_t>(fpr)
147 << " from free_page_runs_";
148 }
149 if (req_byte_size < fpr_byte_size) {
150 // Split.
151 FreePageRun* remainder =
152 reinterpret_cast<FreePageRun*>(reinterpret_cast<uint8_t*>(fpr) + req_byte_size);
153 if (kIsDebugBuild) {
154 remainder->magic_num_ = kMagicNumFree;
155 }
156 remainder->SetByteSize(this, fpr_byte_size - req_byte_size);
157 DCHECK_EQ(remainder->ByteSize(this) % kPageSize, static_cast<size_t>(0));
158 // Don't need to call madvise on remainder here.
159 free_page_runs_.insert(remainder);
160 if (kTraceRosAlloc) {
161 LOG(INFO) << "RosAlloc::AllocPages() : Inserted run 0x" << std::hex
162 << reinterpret_cast<intptr_t>(remainder)
163 << " into free_page_runs_";
164 }
165 fpr->SetByteSize(this, req_byte_size);
166 DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0));
167 }
168 res = fpr;
169 break;
170 } else {
171 ++it;
172 }
173 }
174
175 // Failed to allocate pages. Grow the footprint, if possible.
176 if (UNLIKELY(res == nullptr && capacity_ > footprint_)) {
177 FreePageRun* last_free_page_run = nullptr;
178 size_t last_free_page_run_size;
179 auto it = free_page_runs_.rbegin();
180 if (it != free_page_runs_.rend() && (last_free_page_run = *it)->End(this) == base_ + footprint_) {
181 // There is a free page run at the end.
182 DCHECK(last_free_page_run->IsFree());
183 DCHECK(IsFreePage(ToPageMapIndex(last_free_page_run)));
184 last_free_page_run_size = last_free_page_run->ByteSize(this);
185 } else {
186 // There is no free page run at the end.
187 last_free_page_run_size = 0;
188 }
189 DCHECK_LT(last_free_page_run_size, req_byte_size);
190 if (capacity_ - footprint_ + last_free_page_run_size >= req_byte_size) {
191 // If we grow the heap, we can allocate it.
192 size_t increment = std::min(std::max(2 * MB, req_byte_size - last_free_page_run_size),
193 capacity_ - footprint_);
194 DCHECK_EQ(increment % kPageSize, static_cast<size_t>(0));
195 size_t new_footprint = footprint_ + increment;
196 size_t new_num_of_pages = new_footprint / kPageSize;
197 DCHECK_LT(page_map_size_, new_num_of_pages);
198 DCHECK_LT(free_page_run_size_map_.size(), new_num_of_pages);
199 page_map_size_ = new_num_of_pages;
200 DCHECK_LE(page_map_size_, max_page_map_size_);
201 free_page_run_size_map_.resize(new_num_of_pages);
202 ArtRosAllocMoreCore(this, increment);
203 if (last_free_page_run_size > 0) {
204 // There was a free page run at the end. Expand its size.
205 DCHECK_EQ(last_free_page_run_size, last_free_page_run->ByteSize(this));
206 last_free_page_run->SetByteSize(this, last_free_page_run_size + increment);
207 DCHECK_EQ(last_free_page_run->ByteSize(this) % kPageSize, static_cast<size_t>(0));
208 DCHECK_EQ(last_free_page_run->End(this), base_ + new_footprint);
209 } else {
210 // Otherwise, insert a new free page run at the end.
211 FreePageRun* new_free_page_run = reinterpret_cast<FreePageRun*>(base_ + footprint_);
212 if (kIsDebugBuild) {
213 new_free_page_run->magic_num_ = kMagicNumFree;
214 }
215 new_free_page_run->SetByteSize(this, increment);
216 DCHECK_EQ(new_free_page_run->ByteSize(this) % kPageSize, static_cast<size_t>(0));
217 free_page_runs_.insert(new_free_page_run);
218 DCHECK_EQ(*free_page_runs_.rbegin(), new_free_page_run);
219 if (kTraceRosAlloc) {
220 LOG(INFO) << "RosAlloc::AlloPages() : Grew the heap by inserting run 0x"
221 << std::hex << reinterpret_cast<intptr_t>(new_free_page_run)
222 << " into free_page_runs_";
223 }
224 }
225 DCHECK_LE(footprint_ + increment, capacity_);
226 if (kTraceRosAlloc) {
227 LOG(INFO) << "RosAlloc::AllocPages() : increased the footprint from "
228 << footprint_ << " to " << new_footprint;
229 }
230 footprint_ = new_footprint;
231
232 // And retry the last free page run.
233 it = free_page_runs_.rbegin();
234 DCHECK(it != free_page_runs_.rend());
235 FreePageRun* fpr = *it;
236 if (kIsDebugBuild && last_free_page_run_size > 0) {
237 DCHECK(last_free_page_run != nullptr);
238 DCHECK_EQ(last_free_page_run, fpr);
239 }
240 size_t fpr_byte_size = fpr->ByteSize(this);
241 DCHECK_EQ(fpr_byte_size % kPageSize, static_cast<size_t>(0));
242 DCHECK_LE(req_byte_size, fpr_byte_size);
243 free_page_runs_.erase(fpr);
244 if (kTraceRosAlloc) {
245 LOG(INFO) << "RosAlloc::AllocPages() : Erased run 0x" << std::hex << reinterpret_cast<intptr_t>(fpr)
246 << " from free_page_runs_";
247 }
248 if (req_byte_size < fpr_byte_size) {
249 // Split if there's a remainder.
250 FreePageRun* remainder = reinterpret_cast<FreePageRun*>(reinterpret_cast<uint8_t*>(fpr) + req_byte_size);
251 if (kIsDebugBuild) {
252 remainder->magic_num_ = kMagicNumFree;
253 }
254 remainder->SetByteSize(this, fpr_byte_size - req_byte_size);
255 DCHECK_EQ(remainder->ByteSize(this) % kPageSize, static_cast<size_t>(0));
256 free_page_runs_.insert(remainder);
257 if (kTraceRosAlloc) {
258 LOG(INFO) << "RosAlloc::AllocPages() : Inserted run 0x" << std::hex
259 << reinterpret_cast<intptr_t>(remainder)
260 << " into free_page_runs_";
261 }
262 fpr->SetByteSize(this, req_byte_size);
263 DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0));
264 }
265 res = fpr;
266 }
267 }
268 if (LIKELY(res != nullptr)) {
269 // Update the page map.
270 size_t page_map_idx = ToPageMapIndex(res);
271 for (size_t i = 0; i < num_pages; i++) {
272 DCHECK(IsFreePage(page_map_idx + i));
273 }
274 switch (page_map_type) {
275 case kPageMapRun:
276 page_map_[page_map_idx] = kPageMapRun;
277 for (size_t i = 1; i < num_pages; i++) {
278 page_map_[page_map_idx + i] = kPageMapRunPart;
279 }
280 break;
281 case kPageMapLargeObject:
282 page_map_[page_map_idx] = kPageMapLargeObject;
283 for (size_t i = 1; i < num_pages; i++) {
284 page_map_[page_map_idx + i] = kPageMapLargeObjectPart;
285 }
286 break;
287 default:
288 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_type);
289 UNREACHABLE();
290 }
291 if (kIsDebugBuild) {
292 // Clear the first page since it is not madvised due to the magic number.
293 memset(res, 0, kPageSize);
294 }
295 if (kTraceRosAlloc) {
296 LOG(INFO) << "RosAlloc::AllocPages() : 0x" << std::hex << reinterpret_cast<intptr_t>(res)
297 << "-0x" << (reinterpret_cast<intptr_t>(res) + num_pages * kPageSize)
298 << "(" << std::dec << (num_pages * kPageSize) << ")";
299 }
300 return res;
301 }
302
303 // Fail.
304 if (kTraceRosAlloc) {
305 LOG(INFO) << "RosAlloc::AllocPages() : nullptr";
306 }
307 return nullptr;
308 }
309
FreePages(Thread * self,void * ptr,bool already_zero)310 size_t RosAlloc::FreePages(Thread* self, void* ptr, bool already_zero) {
311 lock_.AssertHeld(self);
312 size_t pm_idx = ToPageMapIndex(ptr);
313 DCHECK_LT(pm_idx, page_map_size_);
314 uint8_t pm_type = page_map_[pm_idx];
315 DCHECK(pm_type == kPageMapRun || pm_type == kPageMapLargeObject);
316 uint8_t pm_part_type;
317 switch (pm_type) {
318 case kPageMapRun:
319 pm_part_type = kPageMapRunPart;
320 break;
321 case kPageMapLargeObject:
322 pm_part_type = kPageMapLargeObjectPart;
323 break;
324 default:
325 LOG(FATAL) << "Unreachable - " << __PRETTY_FUNCTION__ << " : " << "pm_idx=" << pm_idx << ", pm_type="
326 << static_cast<int>(pm_type) << ", ptr=" << std::hex
327 << reinterpret_cast<intptr_t>(ptr);
328 UNREACHABLE();
329 }
330 // Update the page map and count the number of pages.
331 size_t num_pages = 1;
332 page_map_[pm_idx] = kPageMapEmpty;
333 size_t idx = pm_idx + 1;
334 size_t end = page_map_size_;
335 while (idx < end && page_map_[idx] == pm_part_type) {
336 page_map_[idx] = kPageMapEmpty;
337 num_pages++;
338 idx++;
339 }
340 const size_t byte_size = num_pages * kPageSize;
341 if (already_zero) {
342 if (ShouldCheckZeroMemory()) {
343 const uintptr_t* word_ptr = reinterpret_cast<uintptr_t*>(ptr);
344 for (size_t i = 0; i < byte_size / sizeof(uintptr_t); ++i) {
345 CHECK_EQ(word_ptr[i], 0U) << "words don't match at index " << i;
346 }
347 }
348 } else if (!DoesReleaseAllPages()) {
349 memset(ptr, 0, byte_size);
350 }
351
352 if (kTraceRosAlloc) {
353 LOG(INFO) << __PRETTY_FUNCTION__ << " : 0x" << std::hex << reinterpret_cast<intptr_t>(ptr)
354 << "-0x" << (reinterpret_cast<intptr_t>(ptr) + byte_size)
355 << "(" << std::dec << (num_pages * kPageSize) << ")";
356 }
357
358 // Turn it into a free run.
359 FreePageRun* fpr = reinterpret_cast<FreePageRun*>(ptr);
360 if (kIsDebugBuild) {
361 fpr->magic_num_ = kMagicNumFree;
362 }
363 fpr->SetByteSize(this, byte_size);
364 DCHECK_ALIGNED(fpr->ByteSize(this), kPageSize);
365
366 DCHECK(free_page_runs_.find(fpr) == free_page_runs_.end());
367 if (!free_page_runs_.empty()) {
368 // Try to coalesce in the higher address direction.
369 if (kTraceRosAlloc) {
370 LOG(INFO) << __PRETTY_FUNCTION__ << "RosAlloc::FreePages() : trying to coalesce a free page run 0x"
371 << std::hex << reinterpret_cast<uintptr_t>(fpr) << " [" << std::dec << pm_idx << "] -0x"
372 << std::hex << reinterpret_cast<uintptr_t>(fpr->End(this)) << " [" << std::dec
373 << (fpr->End(this) == End() ? page_map_size_ : ToPageMapIndex(fpr->End(this))) << "]";
374 }
375 for (auto it = free_page_runs_.upper_bound(fpr); it != free_page_runs_.end(); ) {
376 FreePageRun* h = *it;
377 DCHECK_EQ(h->ByteSize(this) % kPageSize, static_cast<size_t>(0));
378 if (kTraceRosAlloc) {
379 LOG(INFO) << "RosAlloc::FreePages() : trying to coalesce with a higher free page run 0x"
380 << std::hex << reinterpret_cast<uintptr_t>(h) << " [" << std::dec << ToPageMapIndex(h) << "] -0x"
381 << std::hex << reinterpret_cast<uintptr_t>(h->End(this)) << " [" << std::dec
382 << (h->End(this) == End() ? page_map_size_ : ToPageMapIndex(h->End(this))) << "]";
383 }
384 if (fpr->End(this) == h->Begin()) {
385 if (kTraceRosAlloc) {
386 LOG(INFO) << "Success";
387 }
388 // Clear magic num since this is no longer the start of a free page run.
389 if (kIsDebugBuild) {
390 h->magic_num_ = 0;
391 }
392 it = free_page_runs_.erase(it);
393 if (kTraceRosAlloc) {
394 LOG(INFO) << "RosAlloc::FreePages() : (coalesce) Erased run 0x" << std::hex
395 << reinterpret_cast<intptr_t>(h)
396 << " from free_page_runs_";
397 }
398 fpr->SetByteSize(this, fpr->ByteSize(this) + h->ByteSize(this));
399 DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0));
400 } else {
401 // Not adjacent. Stop.
402 if (kTraceRosAlloc) {
403 LOG(INFO) << "Fail";
404 }
405 break;
406 }
407 }
408 // Try to coalesce in the lower address direction.
409 for (auto it = free_page_runs_.upper_bound(fpr); it != free_page_runs_.begin(); ) {
410 --it;
411
412 FreePageRun* l = *it;
413 DCHECK_EQ(l->ByteSize(this) % kPageSize, static_cast<size_t>(0));
414 if (kTraceRosAlloc) {
415 LOG(INFO) << "RosAlloc::FreePages() : trying to coalesce with a lower free page run 0x"
416 << std::hex << reinterpret_cast<uintptr_t>(l) << " [" << std::dec << ToPageMapIndex(l) << "] -0x"
417 << std::hex << reinterpret_cast<uintptr_t>(l->End(this)) << " [" << std::dec
418 << (l->End(this) == End() ? page_map_size_ : ToPageMapIndex(l->End(this))) << "]";
419 }
420 if (l->End(this) == fpr->Begin()) {
421 if (kTraceRosAlloc) {
422 LOG(INFO) << "Success";
423 }
424 it = free_page_runs_.erase(it);
425 if (kTraceRosAlloc) {
426 LOG(INFO) << "RosAlloc::FreePages() : (coalesce) Erased run 0x" << std::hex
427 << reinterpret_cast<intptr_t>(l)
428 << " from free_page_runs_";
429 }
430 l->SetByteSize(this, l->ByteSize(this) + fpr->ByteSize(this));
431 DCHECK_EQ(l->ByteSize(this) % kPageSize, static_cast<size_t>(0));
432 // Clear magic num since this is no longer the start of a free page run.
433 if (kIsDebugBuild) {
434 fpr->magic_num_ = 0;
435 }
436 fpr = l;
437 } else {
438 // Not adjacent. Stop.
439 if (kTraceRosAlloc) {
440 LOG(INFO) << "Fail";
441 }
442 break;
443 }
444 }
445 }
446
447 // Insert it.
448 DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0));
449 DCHECK(free_page_runs_.find(fpr) == free_page_runs_.end());
450 DCHECK(fpr->IsFree());
451 fpr->ReleasePages(this);
452 DCHECK(fpr->IsFree());
453 free_page_runs_.insert(fpr);
454 DCHECK(free_page_runs_.find(fpr) != free_page_runs_.end());
455 if (kTraceRosAlloc) {
456 LOG(INFO) << "RosAlloc::FreePages() : Inserted run 0x" << std::hex << reinterpret_cast<intptr_t>(fpr)
457 << " into free_page_runs_";
458 }
459 return byte_size;
460 }
461
AllocLargeObject(Thread * self,size_t size,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)462 void* RosAlloc::AllocLargeObject(Thread* self, size_t size, size_t* bytes_allocated,
463 size_t* usable_size, size_t* bytes_tl_bulk_allocated) {
464 DCHECK(bytes_allocated != nullptr);
465 DCHECK(usable_size != nullptr);
466 DCHECK_GT(size, kLargeSizeThreshold);
467 size_t num_pages = RoundUp(size, kPageSize) / kPageSize;
468 void* r;
469 {
470 MutexLock mu(self, lock_);
471 r = AllocPages(self, num_pages, kPageMapLargeObject);
472 }
473 if (UNLIKELY(r == nullptr)) {
474 if (kTraceRosAlloc) {
475 LOG(INFO) << "RosAlloc::AllocLargeObject() : nullptr";
476 }
477 return nullptr;
478 }
479 const size_t total_bytes = num_pages * kPageSize;
480 *bytes_allocated = total_bytes;
481 *usable_size = total_bytes;
482 *bytes_tl_bulk_allocated = total_bytes;
483 if (kTraceRosAlloc) {
484 LOG(INFO) << "RosAlloc::AllocLargeObject() : 0x" << std::hex << reinterpret_cast<intptr_t>(r)
485 << "-0x" << (reinterpret_cast<intptr_t>(r) + num_pages * kPageSize)
486 << "(" << std::dec << (num_pages * kPageSize) << ")";
487 }
488 // Check if the returned memory is really all zero.
489 if (ShouldCheckZeroMemory()) {
490 CHECK_EQ(total_bytes % sizeof(uintptr_t), 0U);
491 const uintptr_t* words = reinterpret_cast<uintptr_t*>(r);
492 for (size_t i = 0; i < total_bytes / sizeof(uintptr_t); ++i) {
493 CHECK_EQ(words[i], 0U);
494 }
495 }
496 return r;
497 }
498
FreeInternal(Thread * self,void * ptr)499 size_t RosAlloc::FreeInternal(Thread* self, void* ptr) {
500 DCHECK_LE(base_, ptr);
501 DCHECK_LT(ptr, base_ + footprint_);
502 size_t pm_idx = RoundDownToPageMapIndex(ptr);
503 Run* run = nullptr;
504 {
505 MutexLock mu(self, lock_);
506 DCHECK_LT(pm_idx, page_map_size_);
507 uint8_t page_map_entry = page_map_[pm_idx];
508 if (kTraceRosAlloc) {
509 LOG(INFO) << "RosAlloc::FreeInternal() : " << std::hex << ptr << ", pm_idx=" << std::dec << pm_idx
510 << ", page_map_entry=" << static_cast<int>(page_map_entry);
511 }
512 switch (page_map_[pm_idx]) {
513 case kPageMapLargeObject:
514 return FreePages(self, ptr, false);
515 case kPageMapLargeObjectPart:
516 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]);
517 UNREACHABLE();
518 case kPageMapRunPart: {
519 // Find the beginning of the run.
520 do {
521 --pm_idx;
522 DCHECK_LT(pm_idx, capacity_ / kPageSize);
523 } while (page_map_[pm_idx] != kPageMapRun);
524 FALLTHROUGH_INTENDED;
525 case kPageMapRun:
526 run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize);
527 DCHECK_EQ(run->magic_num_, kMagicNum);
528 break;
529 case kPageMapReleased:
530 case kPageMapEmpty:
531 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]);
532 UNREACHABLE();
533 }
534 default:
535 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]);
536 UNREACHABLE();
537 }
538 }
539 DCHECK(run != nullptr);
540 return FreeFromRun(self, ptr, run);
541 }
542
Free(Thread * self,void * ptr)543 size_t RosAlloc::Free(Thread* self, void* ptr) {
544 ReaderMutexLock rmu(self, bulk_free_lock_);
545 return FreeInternal(self, ptr);
546 }
547
AllocRun(Thread * self,size_t idx)548 RosAlloc::Run* RosAlloc::AllocRun(Thread* self, size_t idx) {
549 RosAlloc::Run* new_run = nullptr;
550 {
551 MutexLock mu(self, lock_);
552 new_run = reinterpret_cast<Run*>(AllocPages(self, numOfPages[idx], kPageMapRun));
553 }
554 if (LIKELY(new_run != nullptr)) {
555 if (kIsDebugBuild) {
556 new_run->magic_num_ = kMagicNum;
557 }
558 new_run->size_bracket_idx_ = idx;
559 DCHECK(!new_run->IsThreadLocal());
560 DCHECK(!new_run->to_be_bulk_freed_);
561 if (kUsePrefetchDuringAllocRun && idx < kNumThreadLocalSizeBrackets) {
562 // Take ownership of the cache lines if we are likely to be thread local run.
563 if (kPrefetchNewRunDataByZeroing) {
564 // Zeroing the data is sometimes faster than prefetching but it increases memory usage
565 // since we end up dirtying zero pages which may have been madvised.
566 new_run->ZeroData();
567 } else {
568 const size_t num_of_slots = numOfSlots[idx];
569 const size_t bracket_size = bracketSizes[idx];
570 const size_t num_of_bytes = num_of_slots * bracket_size;
571 uint8_t* begin = reinterpret_cast<uint8_t*>(new_run) + headerSizes[idx];
572 for (size_t i = 0; i < num_of_bytes; i += kPrefetchStride) {
573 __builtin_prefetch(begin + i);
574 }
575 }
576 }
577 new_run->InitFreeList();
578 }
579 return new_run;
580 }
581
RefillRun(Thread * self,size_t idx)582 RosAlloc::Run* RosAlloc::RefillRun(Thread* self, size_t idx) {
583 // Get the lowest address non-full run from the binary tree.
584 auto* const bt = &non_full_runs_[idx];
585 if (!bt->empty()) {
586 // If there's one, use it as the current run.
587 auto it = bt->begin();
588 Run* non_full_run = *it;
589 DCHECK(non_full_run != nullptr);
590 DCHECK(!non_full_run->IsThreadLocal());
591 bt->erase(it);
592 return non_full_run;
593 }
594 // If there's none, allocate a new run and use it as the current run.
595 return AllocRun(self, idx);
596 }
597
AllocFromCurrentRunUnlocked(Thread * self,size_t idx)598 inline void* RosAlloc::AllocFromCurrentRunUnlocked(Thread* self, size_t idx) {
599 Run* current_run = current_runs_[idx];
600 DCHECK(current_run != nullptr);
601 void* slot_addr = current_run->AllocSlot();
602 if (UNLIKELY(slot_addr == nullptr)) {
603 // The current run got full. Try to refill it.
604 DCHECK(current_run->IsFull());
605 if (kIsDebugBuild && current_run != dedicated_full_run_) {
606 full_runs_[idx].insert(current_run);
607 if (kTraceRosAlloc) {
608 LOG(INFO) << __PRETTY_FUNCTION__ << " : Inserted run 0x" << std::hex
609 << reinterpret_cast<intptr_t>(current_run)
610 << " into full_runs_[" << std::dec << idx << "]";
611 }
612 DCHECK(non_full_runs_[idx].find(current_run) == non_full_runs_[idx].end());
613 DCHECK(full_runs_[idx].find(current_run) != full_runs_[idx].end());
614 }
615 current_run = RefillRun(self, idx);
616 if (UNLIKELY(current_run == nullptr)) {
617 // Failed to allocate a new run, make sure that it is the dedicated full run.
618 current_runs_[idx] = dedicated_full_run_;
619 return nullptr;
620 }
621 DCHECK(current_run != nullptr);
622 DCHECK(non_full_runs_[idx].find(current_run) == non_full_runs_[idx].end());
623 DCHECK(full_runs_[idx].find(current_run) == full_runs_[idx].end());
624 current_run->SetIsThreadLocal(false);
625 current_runs_[idx] = current_run;
626 DCHECK(!current_run->IsFull());
627 slot_addr = current_run->AllocSlot();
628 // Must succeed now with a new run.
629 DCHECK(slot_addr != nullptr);
630 }
631 return slot_addr;
632 }
633
AllocFromRunThreadUnsafe(Thread * self,size_t size,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)634 void* RosAlloc::AllocFromRunThreadUnsafe(Thread* self, size_t size, size_t* bytes_allocated,
635 size_t* usable_size,
636 size_t* bytes_tl_bulk_allocated) {
637 DCHECK(bytes_allocated != nullptr);
638 DCHECK(usable_size != nullptr);
639 DCHECK(bytes_tl_bulk_allocated != nullptr);
640 DCHECK_LE(size, kLargeSizeThreshold);
641 size_t bracket_size;
642 size_t idx = SizeToIndexAndBracketSize(size, &bracket_size);
643 Locks::mutator_lock_->AssertExclusiveHeld(self);
644 void* slot_addr = AllocFromCurrentRunUnlocked(self, idx);
645 if (LIKELY(slot_addr != nullptr)) {
646 *bytes_allocated = bracket_size;
647 *usable_size = bracket_size;
648 *bytes_tl_bulk_allocated = bracket_size;
649 }
650 // Caller verifies that it is all 0.
651 return slot_addr;
652 }
653
AllocFromRun(Thread * self,size_t size,size_t * bytes_allocated,size_t * usable_size,size_t * bytes_tl_bulk_allocated)654 void* RosAlloc::AllocFromRun(Thread* self, size_t size, size_t* bytes_allocated,
655 size_t* usable_size, size_t* bytes_tl_bulk_allocated) {
656 DCHECK(bytes_allocated != nullptr);
657 DCHECK(usable_size != nullptr);
658 DCHECK(bytes_tl_bulk_allocated != nullptr);
659 DCHECK_LE(size, kLargeSizeThreshold);
660 size_t bracket_size;
661 size_t idx = SizeToIndexAndBracketSize(size, &bracket_size);
662 void* slot_addr;
663 if (LIKELY(idx < kNumThreadLocalSizeBrackets)) {
664 // Use a thread-local run.
665 Run* thread_local_run = reinterpret_cast<Run*>(self->GetRosAllocRun(idx));
666 // Allow invalid since this will always fail the allocation.
667 if (kIsDebugBuild) {
668 // Need the lock to prevent race conditions.
669 MutexLock mu(self, *size_bracket_locks_[idx]);
670 CHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end());
671 CHECK(full_runs_[idx].find(thread_local_run) == full_runs_[idx].end());
672 }
673 DCHECK(thread_local_run != nullptr);
674 DCHECK(thread_local_run->IsThreadLocal() || thread_local_run == dedicated_full_run_);
675 slot_addr = thread_local_run->AllocSlot();
676 // The allocation must fail if the run is invalid.
677 DCHECK(thread_local_run != dedicated_full_run_ || slot_addr == nullptr)
678 << "allocated from an invalid run";
679 if (UNLIKELY(slot_addr == nullptr)) {
680 // The run got full. Try to free slots.
681 DCHECK(thread_local_run->IsFull());
682 MutexLock mu(self, *size_bracket_locks_[idx]);
683 bool is_all_free_after_merge;
684 // This is safe to do for the dedicated_full_run_ since the bitmaps are empty.
685 if (thread_local_run->MergeThreadLocalFreeListToFreeList(&is_all_free_after_merge)) {
686 DCHECK_NE(thread_local_run, dedicated_full_run_);
687 // Some slot got freed. Keep it.
688 DCHECK(!thread_local_run->IsFull());
689 DCHECK_EQ(is_all_free_after_merge, thread_local_run->IsAllFree());
690 } else {
691 // No slots got freed. Try to refill the thread-local run.
692 DCHECK(thread_local_run->IsFull());
693 if (thread_local_run != dedicated_full_run_) {
694 thread_local_run->SetIsThreadLocal(false);
695 if (kIsDebugBuild) {
696 full_runs_[idx].insert(thread_local_run);
697 if (kTraceRosAlloc) {
698 LOG(INFO) << "RosAlloc::AllocFromRun() : Inserted run 0x" << std::hex
699 << reinterpret_cast<intptr_t>(thread_local_run)
700 << " into full_runs_[" << std::dec << idx << "]";
701 }
702 }
703 DCHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end());
704 DCHECK(full_runs_[idx].find(thread_local_run) != full_runs_[idx].end());
705 }
706
707 thread_local_run = RefillRun(self, idx);
708 if (UNLIKELY(thread_local_run == nullptr)) {
709 self->SetRosAllocRun(idx, dedicated_full_run_);
710 return nullptr;
711 }
712 DCHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end());
713 DCHECK(full_runs_[idx].find(thread_local_run) == full_runs_[idx].end());
714 thread_local_run->SetIsThreadLocal(true);
715 self->SetRosAllocRun(idx, thread_local_run);
716 DCHECK(!thread_local_run->IsFull());
717 }
718 DCHECK(thread_local_run != nullptr);
719 DCHECK(!thread_local_run->IsFull());
720 DCHECK(thread_local_run->IsThreadLocal());
721 // Account for all the free slots in the new or refreshed thread local run.
722 *bytes_tl_bulk_allocated = thread_local_run->NumberOfFreeSlots() * bracket_size;
723 slot_addr = thread_local_run->AllocSlot();
724 // Must succeed now with a new run.
725 DCHECK(slot_addr != nullptr);
726 } else {
727 // The slot is already counted. Leave it as is.
728 *bytes_tl_bulk_allocated = 0;
729 }
730 DCHECK(slot_addr != nullptr);
731 if (kTraceRosAlloc) {
732 LOG(INFO) << "RosAlloc::AllocFromRun() thread-local : 0x" << std::hex
733 << reinterpret_cast<intptr_t>(slot_addr)
734 << "-0x" << (reinterpret_cast<intptr_t>(slot_addr) + bracket_size)
735 << "(" << std::dec << (bracket_size) << ")";
736 }
737 *bytes_allocated = bracket_size;
738 *usable_size = bracket_size;
739 } else {
740 // Use the (shared) current run.
741 MutexLock mu(self, *size_bracket_locks_[idx]);
742 slot_addr = AllocFromCurrentRunUnlocked(self, idx);
743 if (kTraceRosAlloc) {
744 LOG(INFO) << "RosAlloc::AllocFromRun() : 0x" << std::hex
745 << reinterpret_cast<intptr_t>(slot_addr)
746 << "-0x" << (reinterpret_cast<intptr_t>(slot_addr) + bracket_size)
747 << "(" << std::dec << (bracket_size) << ")";
748 }
749 if (LIKELY(slot_addr != nullptr)) {
750 *bytes_allocated = bracket_size;
751 *usable_size = bracket_size;
752 *bytes_tl_bulk_allocated = bracket_size;
753 }
754 }
755 // Caller verifies that it is all 0.
756 return slot_addr;
757 }
758
FreeFromRun(Thread * self,void * ptr,Run * run)759 size_t RosAlloc::FreeFromRun(Thread* self, void* ptr, Run* run) {
760 DCHECK_EQ(run->magic_num_, kMagicNum);
761 DCHECK_LT(run, ptr);
762 DCHECK_LT(ptr, run->End());
763 const size_t idx = run->size_bracket_idx_;
764 const size_t bracket_size = bracketSizes[idx];
765 bool run_was_full = false;
766 MutexLock brackets_mu(self, *size_bracket_locks_[idx]);
767 if (kIsDebugBuild) {
768 run_was_full = run->IsFull();
769 }
770 if (kTraceRosAlloc) {
771 LOG(INFO) << "RosAlloc::FreeFromRun() : 0x" << std::hex << reinterpret_cast<intptr_t>(ptr);
772 }
773 if (LIKELY(run->IsThreadLocal())) {
774 // It's a thread-local run. Just mark the thread-local free bit map and return.
775 DCHECK_LT(run->size_bracket_idx_, kNumThreadLocalSizeBrackets);
776 DCHECK(non_full_runs_[idx].find(run) == non_full_runs_[idx].end());
777 DCHECK(full_runs_[idx].find(run) == full_runs_[idx].end());
778 run->AddToThreadLocalFreeList(ptr);
779 if (kTraceRosAlloc) {
780 LOG(INFO) << "RosAlloc::FreeFromRun() : Freed a slot in a thread local run 0x" << std::hex
781 << reinterpret_cast<intptr_t>(run);
782 }
783 // A thread local run will be kept as a thread local even if it's become all free.
784 return bracket_size;
785 }
786 // Free the slot in the run.
787 run->FreeSlot(ptr);
788 auto* non_full_runs = &non_full_runs_[idx];
789 if (run->IsAllFree()) {
790 // It has just become completely free. Free the pages of this run.
791 std::set<Run*>::iterator pos = non_full_runs->find(run);
792 if (pos != non_full_runs->end()) {
793 non_full_runs->erase(pos);
794 if (kTraceRosAlloc) {
795 LOG(INFO) << "RosAlloc::FreeFromRun() : Erased run 0x" << std::hex
796 << reinterpret_cast<intptr_t>(run) << " from non_full_runs_";
797 }
798 }
799 if (run == current_runs_[idx]) {
800 current_runs_[idx] = dedicated_full_run_;
801 }
802 DCHECK(non_full_runs_[idx].find(run) == non_full_runs_[idx].end());
803 DCHECK(full_runs_[idx].find(run) == full_runs_[idx].end());
804 run->ZeroHeaderAndSlotHeaders();
805 {
806 MutexLock lock_mu(self, lock_);
807 FreePages(self, run, true);
808 }
809 } else {
810 // It is not completely free. If it wasn't the current run or
811 // already in the non-full run set (i.e., it was full) insert it
812 // into the non-full run set.
813 if (run != current_runs_[idx]) {
814 auto* full_runs = kIsDebugBuild ? &full_runs_[idx] : nullptr;
815 auto pos = non_full_runs->find(run);
816 if (pos == non_full_runs->end()) {
817 DCHECK(run_was_full);
818 DCHECK(full_runs->find(run) != full_runs->end());
819 if (kIsDebugBuild) {
820 full_runs->erase(run);
821 if (kTraceRosAlloc) {
822 LOG(INFO) << "RosAlloc::FreeFromRun() : Erased run 0x" << std::hex
823 << reinterpret_cast<intptr_t>(run) << " from full_runs_";
824 }
825 }
826 non_full_runs->insert(run);
827 DCHECK(!run->IsFull());
828 if (kTraceRosAlloc) {
829 LOG(INFO) << "RosAlloc::FreeFromRun() : Inserted run 0x" << std::hex
830 << reinterpret_cast<intptr_t>(run)
831 << " into non_full_runs_[" << std::dec << idx << "]";
832 }
833 }
834 }
835 }
836 return bracket_size;
837 }
838
839 template<bool kUseTail>
FreeListToStr(SlotFreeList<kUseTail> * free_list)840 std::string RosAlloc::Run::FreeListToStr(SlotFreeList<kUseTail>* free_list) {
841 std::string free_list_str;
842 const uint8_t idx = size_bracket_idx_;
843 const size_t bracket_size = bracketSizes[idx];
844 for (Slot* slot = free_list->Head(); slot != nullptr; slot = slot->Next()) {
845 bool is_last = slot->Next() == nullptr;
846 uintptr_t slot_offset = reinterpret_cast<uintptr_t>(slot) -
847 reinterpret_cast<uintptr_t>(FirstSlot());
848 DCHECK_EQ(slot_offset % bracket_size, 0U);
849 uintptr_t slot_idx = slot_offset / bracket_size;
850 if (!is_last) {
851 free_list_str.append(StringPrintf("%u-", static_cast<uint32_t>(slot_idx)));
852 } else {
853 free_list_str.append(StringPrintf("%u", static_cast<uint32_t>(slot_idx)));
854 }
855 }
856 return free_list_str;
857 }
858
Dump()859 std::string RosAlloc::Run::Dump() {
860 size_t idx = size_bracket_idx_;
861 std::ostringstream stream;
862 stream << "RosAlloc Run = " << reinterpret_cast<void*>(this)
863 << "{ magic_num=" << static_cast<int>(magic_num_)
864 << " size_bracket_idx=" << idx
865 << " is_thread_local=" << static_cast<int>(is_thread_local_)
866 << " to_be_bulk_freed=" << static_cast<int>(to_be_bulk_freed_)
867 << " free_list=" << FreeListToStr(&free_list_)
868 << " bulk_free_list=" << FreeListToStr(&bulk_free_list_)
869 << " thread_local_list=" << FreeListToStr(&thread_local_free_list_)
870 << " }" << std::endl;
871 return stream.str();
872 }
873
FreeSlot(void * ptr)874 void RosAlloc::Run::FreeSlot(void* ptr) {
875 DCHECK(!IsThreadLocal());
876 const uint8_t idx = size_bracket_idx_;
877 const size_t bracket_size = bracketSizes[idx];
878 Slot* slot = ToSlot(ptr);
879 // Zero out the memory.
880 // TODO: Investigate alternate memset since ptr is guaranteed to be aligned to 16.
881 memset(slot, 0, bracket_size);
882 free_list_.Add(slot);
883 if (kTraceRosAlloc) {
884 LOG(INFO) << "RosAlloc::Run::FreeSlot() : " << slot
885 << ", bracket_size=" << std::dec << bracket_size << ", slot_idx=" << SlotIndex(slot);
886 }
887 }
888
MergeThreadLocalFreeListToFreeList(bool * is_all_free_after_out)889 inline bool RosAlloc::Run::MergeThreadLocalFreeListToFreeList(bool* is_all_free_after_out) {
890 DCHECK(IsThreadLocal());
891 // Merge the thread local free list into the free list and clear the thread local free list.
892 const uint8_t idx = size_bracket_idx_;
893 bool thread_local_free_list_size = thread_local_free_list_.Size();
894 const size_t size_before = free_list_.Size();
895 free_list_.Merge(&thread_local_free_list_);
896 const size_t size_after = free_list_.Size();
897 DCHECK_EQ(size_before < size_after, thread_local_free_list_size > 0);
898 DCHECK_LE(size_before, size_after);
899 *is_all_free_after_out = free_list_.Size() == numOfSlots[idx];
900 // Return true at least one slot was added to the free list.
901 return size_before < size_after;
902 }
903
MergeBulkFreeListToFreeList()904 inline void RosAlloc::Run::MergeBulkFreeListToFreeList() {
905 DCHECK(!IsThreadLocal());
906 // Merge the bulk free list into the free list and clear the bulk free list.
907 free_list_.Merge(&bulk_free_list_);
908 }
909
MergeBulkFreeListToThreadLocalFreeList()910 inline void RosAlloc::Run::MergeBulkFreeListToThreadLocalFreeList() {
911 DCHECK(IsThreadLocal());
912 // Merge the bulk free list into the thread local free list and clear the bulk free list.
913 thread_local_free_list_.Merge(&bulk_free_list_);
914 }
915
AddToThreadLocalFreeList(void * ptr)916 inline void RosAlloc::Run::AddToThreadLocalFreeList(void* ptr) {
917 DCHECK(IsThreadLocal());
918 AddToFreeListShared(ptr, &thread_local_free_list_, __FUNCTION__);
919 }
920
AddToBulkFreeList(void * ptr)921 inline size_t RosAlloc::Run::AddToBulkFreeList(void* ptr) {
922 return AddToFreeListShared(ptr, &bulk_free_list_, __FUNCTION__);
923 }
924
AddToFreeListShared(void * ptr,SlotFreeList<true> * free_list,const char * caller_name)925 inline size_t RosAlloc::Run::AddToFreeListShared(void* ptr,
926 SlotFreeList<true>* free_list,
927 const char* caller_name) {
928 const uint8_t idx = size_bracket_idx_;
929 const size_t bracket_size = bracketSizes[idx];
930 Slot* slot = ToSlot(ptr);
931 memset(slot, 0, bracket_size);
932 free_list->Add(slot);
933 if (kTraceRosAlloc) {
934 LOG(INFO) << "RosAlloc::Run::" << caller_name << "() : " << ptr
935 << ", bracket_size=" << std::dec << bracket_size << ", slot_idx=" << SlotIndex(slot);
936 }
937 return bracket_size;
938 }
939
ZeroHeaderAndSlotHeaders()940 inline void RosAlloc::Run::ZeroHeaderAndSlotHeaders() {
941 DCHECK(IsAllFree());
942 const uint8_t idx = size_bracket_idx_;
943 // Zero the slot header (next pointers).
944 for (Slot* slot = free_list_.Head(); slot != nullptr; ) {
945 Slot* next_slot = slot->Next();
946 slot->Clear();
947 slot = next_slot;
948 }
949 // Zero the header.
950 memset(this, 0, headerSizes[idx]);
951 // Check that the entire run is all zero.
952 if (kIsDebugBuild) {
953 const size_t size = numOfPages[idx] * kPageSize;
954 const uintptr_t* word_ptr = reinterpret_cast<uintptr_t*>(this);
955 for (size_t i = 0; i < size / sizeof(uintptr_t); ++i) {
956 CHECK_EQ(word_ptr[i], 0U) << "words don't match at index " << i;
957 }
958 }
959 }
960
ZeroData()961 inline void RosAlloc::Run::ZeroData() {
962 const uint8_t idx = size_bracket_idx_;
963 uint8_t* slot_begin = reinterpret_cast<uint8_t*>(FirstSlot());
964 memset(slot_begin, 0, numOfSlots[idx] * bracketSizes[idx]);
965 }
966
InspectAllSlots(void (* handler)(void * start,void * end,size_t used_bytes,void * callback_arg),void * arg)967 void RosAlloc::Run::InspectAllSlots(void (*handler)(void* start, void* end, size_t used_bytes, void* callback_arg),
968 void* arg) {
969 size_t idx = size_bracket_idx_;
970 uint8_t* slot_base = reinterpret_cast<uint8_t*>(this) + headerSizes[idx];
971 size_t num_slots = numOfSlots[idx];
972 size_t bracket_size = IndexToBracketSize(idx);
973 DCHECK_EQ(slot_base + num_slots * bracket_size,
974 reinterpret_cast<uint8_t*>(this) + numOfPages[idx] * kPageSize);
975 // Free slots are on the free list and the allocated/used slots are not. We traverse the free list
976 // to find out and record which slots are free in the is_free array.
977 std::unique_ptr<bool[]> is_free(new bool[num_slots]()); // zero initialized
978 for (Slot* slot = free_list_.Head(); slot != nullptr; slot = slot->Next()) {
979 size_t slot_idx = SlotIndex(slot);
980 DCHECK_LT(slot_idx, num_slots);
981 is_free[slot_idx] = true;
982 }
983 if (IsThreadLocal()) {
984 for (Slot* slot = thread_local_free_list_.Head(); slot != nullptr; slot = slot->Next()) {
985 size_t slot_idx = SlotIndex(slot);
986 DCHECK_LT(slot_idx, num_slots);
987 is_free[slot_idx] = true;
988 }
989 }
990 for (size_t slot_idx = 0; slot_idx < num_slots; ++slot_idx) {
991 uint8_t* slot_addr = slot_base + slot_idx * bracket_size;
992 if (!is_free[slot_idx]) {
993 handler(slot_addr, slot_addr + bracket_size, bracket_size, arg);
994 } else {
995 handler(slot_addr, slot_addr + bracket_size, 0, arg);
996 }
997 }
998 }
999
1000 // If true, read the page map entries in BulkFree() without using the
1001 // lock for better performance, assuming that the existence of an
1002 // allocated chunk/pointer being freed in BulkFree() guarantees that
1003 // the page map entry won't change.
1004 static constexpr bool kReadPageMapEntryWithoutLockInBulkFree = true;
1005
BulkFree(Thread * self,void ** ptrs,size_t num_ptrs)1006 size_t RosAlloc::BulkFree(Thread* self, void** ptrs, size_t num_ptrs) {
1007 size_t freed_bytes = 0;
1008 if ((false)) {
1009 // Used only to test Free() as GC uses only BulkFree().
1010 for (size_t i = 0; i < num_ptrs; ++i) {
1011 freed_bytes += FreeInternal(self, ptrs[i]);
1012 }
1013 return freed_bytes;
1014 }
1015
1016 WriterMutexLock wmu(self, bulk_free_lock_);
1017
1018 // First mark slots to free in the bulk free bit map without locking the
1019 // size bracket locks. On host, unordered_set is faster than vector + flag.
1020 #ifdef ART_TARGET_ANDROID
1021 std::vector<Run*> runs;
1022 #else
1023 std::unordered_set<Run*, hash_run, eq_run> runs;
1024 #endif
1025 for (size_t i = 0; i < num_ptrs; i++) {
1026 void* ptr = ptrs[i];
1027 DCHECK_LE(base_, ptr);
1028 DCHECK_LT(ptr, base_ + footprint_);
1029 size_t pm_idx = RoundDownToPageMapIndex(ptr);
1030 Run* run = nullptr;
1031 if (kReadPageMapEntryWithoutLockInBulkFree) {
1032 // Read the page map entries without locking the lock.
1033 uint8_t page_map_entry = page_map_[pm_idx];
1034 if (kTraceRosAlloc) {
1035 LOG(INFO) << "RosAlloc::BulkFree() : " << std::hex << ptr << ", pm_idx="
1036 << std::dec << pm_idx
1037 << ", page_map_entry=" << static_cast<int>(page_map_entry);
1038 }
1039 if (LIKELY(page_map_entry == kPageMapRun)) {
1040 run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize);
1041 } else if (LIKELY(page_map_entry == kPageMapRunPart)) {
1042 size_t pi = pm_idx;
1043 // Find the beginning of the run.
1044 do {
1045 --pi;
1046 DCHECK_LT(pi, capacity_ / kPageSize);
1047 } while (page_map_[pi] != kPageMapRun);
1048 run = reinterpret_cast<Run*>(base_ + pi * kPageSize);
1049 } else if (page_map_entry == kPageMapLargeObject) {
1050 MutexLock mu(self, lock_);
1051 freed_bytes += FreePages(self, ptr, false);
1052 continue;
1053 } else {
1054 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_entry);
1055 }
1056 } else {
1057 // Read the page map entries with a lock.
1058 MutexLock mu(self, lock_);
1059 DCHECK_LT(pm_idx, page_map_size_);
1060 uint8_t page_map_entry = page_map_[pm_idx];
1061 if (kTraceRosAlloc) {
1062 LOG(INFO) << "RosAlloc::BulkFree() : " << std::hex << ptr << ", pm_idx="
1063 << std::dec << pm_idx
1064 << ", page_map_entry=" << static_cast<int>(page_map_entry);
1065 }
1066 if (LIKELY(page_map_entry == kPageMapRun)) {
1067 run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize);
1068 } else if (LIKELY(page_map_entry == kPageMapRunPart)) {
1069 size_t pi = pm_idx;
1070 // Find the beginning of the run.
1071 do {
1072 --pi;
1073 DCHECK_LT(pi, capacity_ / kPageSize);
1074 } while (page_map_[pi] != kPageMapRun);
1075 run = reinterpret_cast<Run*>(base_ + pi * kPageSize);
1076 } else if (page_map_entry == kPageMapLargeObject) {
1077 freed_bytes += FreePages(self, ptr, false);
1078 continue;
1079 } else {
1080 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_entry);
1081 }
1082 }
1083 DCHECK(run != nullptr);
1084 DCHECK_EQ(run->magic_num_, kMagicNum);
1085 // Set the bit in the bulk free bit map.
1086 freed_bytes += run->AddToBulkFreeList(ptr);
1087 #ifdef ART_TARGET_ANDROID
1088 if (!run->to_be_bulk_freed_) {
1089 run->to_be_bulk_freed_ = true;
1090 runs.push_back(run);
1091 }
1092 #else
1093 runs.insert(run);
1094 #endif
1095 }
1096
1097 // Now, iterate over the affected runs and update the alloc bit map
1098 // based on the bulk free bit map (for non-thread-local runs) and
1099 // union the bulk free bit map into the thread-local free bit map
1100 // (for thread-local runs.)
1101 for (Run* run : runs) {
1102 #ifdef ART_TARGET_ANDROID
1103 DCHECK(run->to_be_bulk_freed_);
1104 run->to_be_bulk_freed_ = false;
1105 #endif
1106 size_t idx = run->size_bracket_idx_;
1107 MutexLock brackets_mu(self, *size_bracket_locks_[idx]);
1108 if (run->IsThreadLocal()) {
1109 DCHECK_LT(run->size_bracket_idx_, kNumThreadLocalSizeBrackets);
1110 DCHECK(non_full_runs_[idx].find(run) == non_full_runs_[idx].end());
1111 DCHECK(full_runs_[idx].find(run) == full_runs_[idx].end());
1112 run->MergeBulkFreeListToThreadLocalFreeList();
1113 if (kTraceRosAlloc) {
1114 LOG(INFO) << "RosAlloc::BulkFree() : Freed slot(s) in a thread local run 0x"
1115 << std::hex << reinterpret_cast<intptr_t>(run);
1116 }
1117 DCHECK(run->IsThreadLocal());
1118 // A thread local run will be kept as a thread local even if
1119 // it's become all free.
1120 } else {
1121 bool run_was_full = run->IsFull();
1122 run->MergeBulkFreeListToFreeList();
1123 if (kTraceRosAlloc) {
1124 LOG(INFO) << "RosAlloc::BulkFree() : Freed slot(s) in a run 0x" << std::hex
1125 << reinterpret_cast<intptr_t>(run);
1126 }
1127 // Check if the run should be moved to non_full_runs_ or
1128 // free_page_runs_.
1129 auto* non_full_runs = &non_full_runs_[idx];
1130 auto* full_runs = kIsDebugBuild ? &full_runs_[idx] : nullptr;
1131 if (run->IsAllFree()) {
1132 // It has just become completely free. Free the pages of the
1133 // run.
1134 bool run_was_current = run == current_runs_[idx];
1135 if (run_was_current) {
1136 DCHECK(full_runs->find(run) == full_runs->end());
1137 DCHECK(non_full_runs->find(run) == non_full_runs->end());
1138 // If it was a current run, reuse it.
1139 } else if (run_was_full) {
1140 // If it was full, remove it from the full run set (debug
1141 // only.)
1142 if (kIsDebugBuild) {
1143 std::unordered_set<Run*, hash_run, eq_run>::iterator pos = full_runs->find(run);
1144 DCHECK(pos != full_runs->end());
1145 full_runs->erase(pos);
1146 if (kTraceRosAlloc) {
1147 LOG(INFO) << "RosAlloc::BulkFree() : Erased run 0x" << std::hex
1148 << reinterpret_cast<intptr_t>(run)
1149 << " from full_runs_";
1150 }
1151 DCHECK(full_runs->find(run) == full_runs->end());
1152 }
1153 } else {
1154 // If it was in a non full run set, remove it from the set.
1155 DCHECK(full_runs->find(run) == full_runs->end());
1156 DCHECK(non_full_runs->find(run) != non_full_runs->end());
1157 non_full_runs->erase(run);
1158 if (kTraceRosAlloc) {
1159 LOG(INFO) << "RosAlloc::BulkFree() : Erased run 0x" << std::hex
1160 << reinterpret_cast<intptr_t>(run)
1161 << " from non_full_runs_";
1162 }
1163 DCHECK(non_full_runs->find(run) == non_full_runs->end());
1164 }
1165 if (!run_was_current) {
1166 run->ZeroHeaderAndSlotHeaders();
1167 MutexLock lock_mu(self, lock_);
1168 FreePages(self, run, true);
1169 }
1170 } else {
1171 // It is not completely free. If it wasn't the current run or
1172 // already in the non-full run set (i.e., it was full) insert
1173 // it into the non-full run set.
1174 if (run == current_runs_[idx]) {
1175 DCHECK(non_full_runs->find(run) == non_full_runs->end());
1176 DCHECK(full_runs->find(run) == full_runs->end());
1177 // If it was a current run, keep it.
1178 } else if (run_was_full) {
1179 // If it was full, remove it from the full run set (debug
1180 // only) and insert into the non-full run set.
1181 DCHECK(full_runs->find(run) != full_runs->end());
1182 DCHECK(non_full_runs->find(run) == non_full_runs->end());
1183 if (kIsDebugBuild) {
1184 full_runs->erase(run);
1185 if (kTraceRosAlloc) {
1186 LOG(INFO) << "RosAlloc::BulkFree() : Erased run 0x" << std::hex
1187 << reinterpret_cast<intptr_t>(run)
1188 << " from full_runs_";
1189 }
1190 }
1191 non_full_runs->insert(run);
1192 if (kTraceRosAlloc) {
1193 LOG(INFO) << "RosAlloc::BulkFree() : Inserted run 0x" << std::hex
1194 << reinterpret_cast<intptr_t>(run)
1195 << " into non_full_runs_[" << std::dec << idx;
1196 }
1197 } else {
1198 // If it was not full, so leave it in the non full run set.
1199 DCHECK(full_runs->find(run) == full_runs->end());
1200 DCHECK(non_full_runs->find(run) != non_full_runs->end());
1201 }
1202 }
1203 }
1204 }
1205 return freed_bytes;
1206 }
1207
DumpPageMap()1208 std::string RosAlloc::DumpPageMap() {
1209 std::ostringstream stream;
1210 stream << "RosAlloc PageMap: " << std::endl;
1211 lock_.AssertHeld(Thread::Current());
1212 size_t end = page_map_size_;
1213 FreePageRun* curr_fpr = nullptr;
1214 size_t curr_fpr_size = 0;
1215 size_t remaining_curr_fpr_size = 0;
1216 size_t num_running_empty_pages = 0;
1217 for (size_t i = 0; i < end; ++i) {
1218 uint8_t pm = page_map_[i];
1219 switch (pm) {
1220 case kPageMapReleased:
1221 // Fall-through.
1222 case kPageMapEmpty: {
1223 FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize);
1224 if (free_page_runs_.find(fpr) != free_page_runs_.end()) {
1225 // Encountered a fresh free page run.
1226 DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
1227 DCHECK(fpr->IsFree());
1228 DCHECK(curr_fpr == nullptr);
1229 DCHECK_EQ(curr_fpr_size, static_cast<size_t>(0));
1230 curr_fpr = fpr;
1231 curr_fpr_size = fpr->ByteSize(this);
1232 DCHECK_EQ(curr_fpr_size % kPageSize, static_cast<size_t>(0));
1233 remaining_curr_fpr_size = curr_fpr_size - kPageSize;
1234 stream << "[" << i << "]=" << (pm == kPageMapReleased ? "Released" : "Empty")
1235 << " (FPR start) fpr_size=" << curr_fpr_size
1236 << " remaining_fpr_size=" << remaining_curr_fpr_size << std::endl;
1237 if (remaining_curr_fpr_size == 0) {
1238 // Reset at the end of the current free page run.
1239 curr_fpr = nullptr;
1240 curr_fpr_size = 0;
1241 }
1242 stream << "curr_fpr=0x" << std::hex << reinterpret_cast<intptr_t>(curr_fpr) << std::endl;
1243 DCHECK_EQ(num_running_empty_pages, static_cast<size_t>(0));
1244 } else {
1245 // Still part of the current free page run.
1246 DCHECK_NE(num_running_empty_pages, static_cast<size_t>(0));
1247 DCHECK(curr_fpr != nullptr && curr_fpr_size > 0 && remaining_curr_fpr_size > 0);
1248 DCHECK_EQ(remaining_curr_fpr_size % kPageSize, static_cast<size_t>(0));
1249 DCHECK_GE(remaining_curr_fpr_size, static_cast<size_t>(kPageSize));
1250 remaining_curr_fpr_size -= kPageSize;
1251 stream << "[" << i << "]=Empty (FPR part)"
1252 << " remaining_fpr_size=" << remaining_curr_fpr_size << std::endl;
1253 if (remaining_curr_fpr_size == 0) {
1254 // Reset at the end of the current free page run.
1255 curr_fpr = nullptr;
1256 curr_fpr_size = 0;
1257 }
1258 }
1259 num_running_empty_pages++;
1260 break;
1261 }
1262 case kPageMapLargeObject: {
1263 DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
1264 num_running_empty_pages = 0;
1265 stream << "[" << i << "]=Large (start)" << std::endl;
1266 break;
1267 }
1268 case kPageMapLargeObjectPart:
1269 DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
1270 num_running_empty_pages = 0;
1271 stream << "[" << i << "]=Large (part)" << std::endl;
1272 break;
1273 case kPageMapRun: {
1274 DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
1275 num_running_empty_pages = 0;
1276 Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize);
1277 size_t idx = run->size_bracket_idx_;
1278 stream << "[" << i << "]=Run (start)"
1279 << " idx=" << idx
1280 << " numOfPages=" << numOfPages[idx]
1281 << " is_thread_local=" << run->is_thread_local_
1282 << " is_all_free=" << (run->IsAllFree() ? 1 : 0)
1283 << std::endl;
1284 break;
1285 }
1286 case kPageMapRunPart:
1287 DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0));
1288 num_running_empty_pages = 0;
1289 stream << "[" << i << "]=Run (part)" << std::endl;
1290 break;
1291 default:
1292 stream << "[" << i << "]=Unrecognizable page map type: " << pm;
1293 break;
1294 }
1295 }
1296 return stream.str();
1297 }
1298
UsableSize(const void * ptr)1299 size_t RosAlloc::UsableSize(const void* ptr) {
1300 DCHECK_LE(base_, ptr);
1301 DCHECK_LT(ptr, base_ + footprint_);
1302 size_t pm_idx = RoundDownToPageMapIndex(ptr);
1303 MutexLock mu(Thread::Current(), lock_);
1304 switch (page_map_[pm_idx]) {
1305 case kPageMapReleased:
1306 // Fall-through.
1307 case kPageMapEmpty:
1308 LOG(FATAL) << "Unreachable - " << __PRETTY_FUNCTION__ << ": pm_idx=" << pm_idx << ", ptr="
1309 << std::hex << reinterpret_cast<intptr_t>(ptr);
1310 UNREACHABLE();
1311 case kPageMapLargeObject: {
1312 size_t num_pages = 1;
1313 size_t idx = pm_idx + 1;
1314 size_t end = page_map_size_;
1315 while (idx < end && page_map_[idx] == kPageMapLargeObjectPart) {
1316 num_pages++;
1317 idx++;
1318 }
1319 return num_pages * kPageSize;
1320 }
1321 case kPageMapLargeObjectPart:
1322 LOG(FATAL) << "Unreachable - " << __PRETTY_FUNCTION__ << ": pm_idx=" << pm_idx << ", ptr="
1323 << std::hex << reinterpret_cast<intptr_t>(ptr);
1324 UNREACHABLE();
1325 case kPageMapRun:
1326 case kPageMapRunPart: {
1327 // Find the beginning of the run.
1328 while (page_map_[pm_idx] != kPageMapRun) {
1329 pm_idx--;
1330 DCHECK_LT(pm_idx, capacity_ / kPageSize);
1331 }
1332 DCHECK_EQ(page_map_[pm_idx], kPageMapRun);
1333 Run* run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize);
1334 DCHECK_EQ(run->magic_num_, kMagicNum);
1335 size_t idx = run->size_bracket_idx_;
1336 size_t offset_from_slot_base = reinterpret_cast<const uint8_t*>(ptr)
1337 - (reinterpret_cast<uint8_t*>(run) + headerSizes[idx]);
1338 DCHECK_EQ(offset_from_slot_base % bracketSizes[idx], static_cast<size_t>(0));
1339 return IndexToBracketSize(idx);
1340 }
1341 default: {
1342 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]);
1343 UNREACHABLE();
1344 }
1345 }
1346 }
1347
Trim()1348 bool RosAlloc::Trim() {
1349 MutexLock mu(Thread::Current(), lock_);
1350 FreePageRun* last_free_page_run;
1351 DCHECK_EQ(footprint_ % kPageSize, static_cast<size_t>(0));
1352 auto it = free_page_runs_.rbegin();
1353 if (it != free_page_runs_.rend() && (last_free_page_run = *it)->End(this) == base_ + footprint_) {
1354 // Remove the last free page run, if any.
1355 DCHECK(last_free_page_run->IsFree());
1356 DCHECK(IsFreePage(ToPageMapIndex(last_free_page_run)));
1357 DCHECK_EQ(last_free_page_run->ByteSize(this) % kPageSize, static_cast<size_t>(0));
1358 DCHECK_EQ(last_free_page_run->End(this), base_ + footprint_);
1359 free_page_runs_.erase(last_free_page_run);
1360 size_t decrement = last_free_page_run->ByteSize(this);
1361 size_t new_footprint = footprint_ - decrement;
1362 DCHECK_EQ(new_footprint % kPageSize, static_cast<size_t>(0));
1363 size_t new_num_of_pages = new_footprint / kPageSize;
1364 DCHECK_GE(page_map_size_, new_num_of_pages);
1365 // Zero out the tail of the page map.
1366 uint8_t* zero_begin = const_cast<uint8_t*>(page_map_) + new_num_of_pages;
1367 uint8_t* madvise_begin = AlignUp(zero_begin, kPageSize);
1368 DCHECK_LE(madvise_begin, page_map_mem_map_.End());
1369 size_t madvise_size = page_map_mem_map_.End() - madvise_begin;
1370 if (madvise_size > 0) {
1371 DCHECK_ALIGNED(madvise_begin, kPageSize);
1372 DCHECK_EQ(RoundUp(madvise_size, kPageSize), madvise_size);
1373 if (!kMadviseZeroes) {
1374 memset(madvise_begin, 0, madvise_size);
1375 }
1376 CHECK_EQ(madvise(madvise_begin, madvise_size, MADV_DONTNEED), 0);
1377 }
1378 if (madvise_begin - zero_begin) {
1379 memset(zero_begin, 0, madvise_begin - zero_begin);
1380 }
1381 page_map_size_ = new_num_of_pages;
1382 free_page_run_size_map_.resize(new_num_of_pages);
1383 DCHECK_EQ(free_page_run_size_map_.size(), new_num_of_pages);
1384 ArtRosAllocMoreCore(this, -(static_cast<intptr_t>(decrement)));
1385 if (kTraceRosAlloc) {
1386 LOG(INFO) << "RosAlloc::Trim() : decreased the footprint from "
1387 << footprint_ << " to " << new_footprint;
1388 }
1389 DCHECK_LT(new_footprint, footprint_);
1390 DCHECK_LT(new_footprint, capacity_);
1391 footprint_ = new_footprint;
1392 return true;
1393 }
1394 return false;
1395 }
1396
InspectAll(void (* handler)(void * start,void * end,size_t used_bytes,void * callback_arg),void * arg)1397 void RosAlloc::InspectAll(void (*handler)(void* start, void* end, size_t used_bytes, void* callback_arg),
1398 void* arg) {
1399 // Note: no need to use this to release pages as we already do so in FreePages().
1400 if (handler == nullptr) {
1401 return;
1402 }
1403 MutexLock mu(Thread::Current(), lock_);
1404 size_t pm_end = page_map_size_;
1405 size_t i = 0;
1406 while (i < pm_end) {
1407 uint8_t pm = page_map_[i];
1408 switch (pm) {
1409 case kPageMapReleased:
1410 // Fall-through.
1411 case kPageMapEmpty: {
1412 // The start of a free page run.
1413 FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize);
1414 DCHECK(free_page_runs_.find(fpr) != free_page_runs_.end());
1415 size_t fpr_size = fpr->ByteSize(this);
1416 DCHECK_ALIGNED(fpr_size, kPageSize);
1417 void* start = fpr;
1418 if (kIsDebugBuild) {
1419 // In the debug build, the first page of a free page run
1420 // contains a magic number for debugging. Exclude it.
1421 start = reinterpret_cast<uint8_t*>(fpr) + kPageSize;
1422 }
1423 void* end = reinterpret_cast<uint8_t*>(fpr) + fpr_size;
1424 handler(start, end, 0, arg);
1425 size_t num_pages = fpr_size / kPageSize;
1426 if (kIsDebugBuild) {
1427 for (size_t j = i + 1; j < i + num_pages; ++j) {
1428 DCHECK(IsFreePage(j));
1429 }
1430 }
1431 i += fpr_size / kPageSize;
1432 DCHECK_LE(i, pm_end);
1433 break;
1434 }
1435 case kPageMapLargeObject: {
1436 // The start of a large object.
1437 size_t num_pages = 1;
1438 size_t idx = i + 1;
1439 while (idx < pm_end && page_map_[idx] == kPageMapLargeObjectPart) {
1440 num_pages++;
1441 idx++;
1442 }
1443 void* start = base_ + i * kPageSize;
1444 void* end = base_ + (i + num_pages) * kPageSize;
1445 size_t used_bytes = num_pages * kPageSize;
1446 handler(start, end, used_bytes, arg);
1447 if (kIsDebugBuild) {
1448 for (size_t j = i + 1; j < i + num_pages; ++j) {
1449 DCHECK_EQ(page_map_[j], kPageMapLargeObjectPart);
1450 }
1451 }
1452 i += num_pages;
1453 DCHECK_LE(i, pm_end);
1454 break;
1455 }
1456 case kPageMapLargeObjectPart:
1457 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm);
1458 UNREACHABLE();
1459 case kPageMapRun: {
1460 // The start of a run.
1461 Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize);
1462 DCHECK_EQ(run->magic_num_, kMagicNum);
1463 // The dedicated full run doesn't contain any real allocations, don't visit the slots in
1464 // there.
1465 run->InspectAllSlots(handler, arg);
1466 size_t num_pages = numOfPages[run->size_bracket_idx_];
1467 if (kIsDebugBuild) {
1468 for (size_t j = i + 1; j < i + num_pages; ++j) {
1469 DCHECK_EQ(page_map_[j], kPageMapRunPart);
1470 }
1471 }
1472 i += num_pages;
1473 DCHECK_LE(i, pm_end);
1474 break;
1475 }
1476 case kPageMapRunPart:
1477 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm);
1478 UNREACHABLE();
1479 default:
1480 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm);
1481 UNREACHABLE();
1482 }
1483 }
1484 }
1485
Footprint()1486 size_t RosAlloc::Footprint() {
1487 MutexLock mu(Thread::Current(), lock_);
1488 return footprint_;
1489 }
1490
FootprintLimit()1491 size_t RosAlloc::FootprintLimit() {
1492 MutexLock mu(Thread::Current(), lock_);
1493 return capacity_;
1494 }
1495
SetFootprintLimit(size_t new_capacity)1496 void RosAlloc::SetFootprintLimit(size_t new_capacity) {
1497 MutexLock mu(Thread::Current(), lock_);
1498 DCHECK_EQ(RoundUp(new_capacity, kPageSize), new_capacity);
1499 // Only growing is supported here. But Trim() is supported.
1500 if (capacity_ < new_capacity) {
1501 CHECK_LE(new_capacity, max_capacity_);
1502 capacity_ = new_capacity;
1503 VLOG(heap) << "new capacity=" << capacity_;
1504 }
1505 }
1506
1507 // Below may be called by mutator itself just before thread termination.
RevokeThreadLocalRuns(Thread * thread)1508 size_t RosAlloc::RevokeThreadLocalRuns(Thread* thread) {
1509 Thread* self = Thread::Current();
1510 size_t free_bytes = 0U;
1511 for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; idx++) {
1512 MutexLock mu(self, *size_bracket_locks_[idx]);
1513 Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(idx));
1514 CHECK(thread_local_run != nullptr);
1515 // Invalid means already revoked.
1516 DCHECK(thread_local_run->IsThreadLocal());
1517 if (thread_local_run != dedicated_full_run_) {
1518 // Note the thread local run may not be full here.
1519 thread->SetRosAllocRun(idx, dedicated_full_run_);
1520 DCHECK_EQ(thread_local_run->magic_num_, kMagicNum);
1521 // Count the number of free slots left.
1522 size_t num_free_slots = thread_local_run->NumberOfFreeSlots();
1523 free_bytes += num_free_slots * bracketSizes[idx];
1524 // The above bracket index lock guards thread local free list to avoid race condition
1525 // with unioning bulk free list to thread local free list by GC thread in BulkFree.
1526 // If thread local run is true, GC thread will help update thread local free list
1527 // in BulkFree. And the latest thread local free list will be merged to free list
1528 // either when this thread local run is full or when revoking this run here. In this
1529 // case the free list wll be updated. If thread local run is false, GC thread will help
1530 // merge bulk free list in next BulkFree.
1531 // Thus no need to merge bulk free list to free list again here.
1532 bool dont_care;
1533 thread_local_run->MergeThreadLocalFreeListToFreeList(&dont_care);
1534 thread_local_run->SetIsThreadLocal(false);
1535 DCHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end());
1536 DCHECK(full_runs_[idx].find(thread_local_run) == full_runs_[idx].end());
1537 RevokeRun(self, idx, thread_local_run);
1538 }
1539 }
1540 return free_bytes;
1541 }
1542
RevokeRun(Thread * self,size_t idx,Run * run)1543 void RosAlloc::RevokeRun(Thread* self, size_t idx, Run* run) {
1544 size_bracket_locks_[idx]->AssertHeld(self);
1545 DCHECK(run != dedicated_full_run_);
1546 if (run->IsFull()) {
1547 if (kIsDebugBuild) {
1548 full_runs_[idx].insert(run);
1549 DCHECK(full_runs_[idx].find(run) != full_runs_[idx].end());
1550 if (kTraceRosAlloc) {
1551 LOG(INFO) << __PRETTY_FUNCTION__ << " : Inserted run 0x" << std::hex
1552 << reinterpret_cast<intptr_t>(run)
1553 << " into full_runs_[" << std::dec << idx << "]";
1554 }
1555 }
1556 } else if (run->IsAllFree()) {
1557 run->ZeroHeaderAndSlotHeaders();
1558 MutexLock mu(self, lock_);
1559 FreePages(self, run, true);
1560 } else {
1561 non_full_runs_[idx].insert(run);
1562 DCHECK(non_full_runs_[idx].find(run) != non_full_runs_[idx].end());
1563 if (kTraceRosAlloc) {
1564 LOG(INFO) << __PRETTY_FUNCTION__ << " : Inserted run 0x" << std::hex
1565 << reinterpret_cast<intptr_t>(run)
1566 << " into non_full_runs_[" << std::dec << idx << "]";
1567 }
1568 }
1569 }
1570
RevokeThreadUnsafeCurrentRuns()1571 void RosAlloc::RevokeThreadUnsafeCurrentRuns() {
1572 // Revoke the current runs which share the same idx as thread local runs.
1573 Thread* self = Thread::Current();
1574 for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; ++idx) {
1575 MutexLock mu(self, *size_bracket_locks_[idx]);
1576 if (current_runs_[idx] != dedicated_full_run_) {
1577 RevokeRun(self, idx, current_runs_[idx]);
1578 current_runs_[idx] = dedicated_full_run_;
1579 }
1580 }
1581 }
1582
RevokeAllThreadLocalRuns()1583 size_t RosAlloc::RevokeAllThreadLocalRuns() {
1584 // This is called when a mutator thread won't allocate such as at
1585 // the Zygote creation time or during the GC pause.
1586 MutexLock mu(Thread::Current(), *Locks::runtime_shutdown_lock_);
1587 MutexLock mu2(Thread::Current(), *Locks::thread_list_lock_);
1588 std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
1589 size_t free_bytes = 0U;
1590 for (Thread* thread : thread_list) {
1591 free_bytes += RevokeThreadLocalRuns(thread);
1592 }
1593 RevokeThreadUnsafeCurrentRuns();
1594 return free_bytes;
1595 }
1596
AssertThreadLocalRunsAreRevoked(Thread * thread)1597 void RosAlloc::AssertThreadLocalRunsAreRevoked(Thread* thread) {
1598 if (kIsDebugBuild) {
1599 Thread* self = Thread::Current();
1600 // Avoid race conditions on the bulk free bit maps with BulkFree() (GC).
1601 ReaderMutexLock wmu(self, bulk_free_lock_);
1602 for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; idx++) {
1603 MutexLock mu(self, *size_bracket_locks_[idx]);
1604 Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(idx));
1605 DCHECK(thread_local_run == nullptr || thread_local_run == dedicated_full_run_);
1606 }
1607 }
1608 }
1609
AssertAllThreadLocalRunsAreRevoked()1610 void RosAlloc::AssertAllThreadLocalRunsAreRevoked() {
1611 if (kIsDebugBuild) {
1612 Thread* self = Thread::Current();
1613 MutexLock shutdown_mu(self, *Locks::runtime_shutdown_lock_);
1614 MutexLock thread_list_mu(self, *Locks::thread_list_lock_);
1615 std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
1616 for (Thread* t : thread_list) {
1617 AssertThreadLocalRunsAreRevoked(t);
1618 }
1619 for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; ++idx) {
1620 MutexLock brackets_mu(self, *size_bracket_locks_[idx]);
1621 CHECK_EQ(current_runs_[idx], dedicated_full_run_);
1622 }
1623 }
1624 }
1625
Initialize()1626 void RosAlloc::Initialize() {
1627 // bracketSizes.
1628 static_assert(kNumRegularSizeBrackets == kNumOfSizeBrackets - 2,
1629 "There should be two non-regular brackets");
1630 for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
1631 if (i < kNumThreadLocalSizeBrackets) {
1632 bracketSizes[i] = kThreadLocalBracketQuantumSize * (i + 1);
1633 } else if (i < kNumRegularSizeBrackets) {
1634 bracketSizes[i] = kBracketQuantumSize * (i - kNumThreadLocalSizeBrackets + 1) +
1635 (kThreadLocalBracketQuantumSize * kNumThreadLocalSizeBrackets);
1636 } else if (i == kNumOfSizeBrackets - 2) {
1637 bracketSizes[i] = 1 * KB;
1638 } else {
1639 DCHECK_EQ(i, kNumOfSizeBrackets - 1);
1640 bracketSizes[i] = 2 * KB;
1641 }
1642 if (kTraceRosAlloc) {
1643 LOG(INFO) << "bracketSizes[" << i << "]=" << bracketSizes[i];
1644 }
1645 }
1646 // numOfPages.
1647 for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
1648 if (i < kNumThreadLocalSizeBrackets) {
1649 numOfPages[i] = 1;
1650 } else if (i < (kNumThreadLocalSizeBrackets + kNumRegularSizeBrackets) / 2) {
1651 numOfPages[i] = 1;
1652 } else if (i < kNumRegularSizeBrackets) {
1653 numOfPages[i] = 1;
1654 } else if (i == kNumOfSizeBrackets - 2) {
1655 numOfPages[i] = 2;
1656 } else {
1657 DCHECK_EQ(i, kNumOfSizeBrackets - 1);
1658 numOfPages[i] = 4;
1659 }
1660 if (kTraceRosAlloc) {
1661 LOG(INFO) << "numOfPages[" << i << "]=" << numOfPages[i];
1662 }
1663 }
1664 // Compute numOfSlots and slotOffsets.
1665 for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
1666 size_t bracket_size = bracketSizes[i];
1667 size_t run_size = kPageSize * numOfPages[i];
1668 size_t max_num_of_slots = run_size / bracket_size;
1669 // Compute the actual number of slots by taking the header and
1670 // alignment into account.
1671 size_t fixed_header_size = RoundUp(Run::fixed_header_size(), sizeof(uint64_t));
1672 DCHECK_EQ(fixed_header_size, 80U);
1673 size_t header_size = 0;
1674 size_t num_of_slots = 0;
1675 // Search for the maximum number of slots that allows enough space
1676 // for the header.
1677 for (int s = max_num_of_slots; s >= 0; s--) {
1678 size_t tmp_slots_size = bracket_size * s;
1679 size_t tmp_unaligned_header_size = fixed_header_size;
1680 // Align up the unaligned header size. bracket_size may not be a power of two.
1681 size_t tmp_header_size = (tmp_unaligned_header_size % bracket_size == 0) ?
1682 tmp_unaligned_header_size :
1683 tmp_unaligned_header_size + (bracket_size - tmp_unaligned_header_size % bracket_size);
1684 DCHECK_EQ(tmp_header_size % bracket_size, 0U);
1685 DCHECK_EQ(tmp_header_size % sizeof(uint64_t), 0U);
1686 if (tmp_slots_size + tmp_header_size <= run_size) {
1687 // Found the right number of slots, that is, there was enough
1688 // space for the header (including the bit maps.)
1689 num_of_slots = s;
1690 header_size = tmp_header_size;
1691 break;
1692 }
1693 }
1694 DCHECK_GT(num_of_slots, 0U) << i;
1695 DCHECK_GT(header_size, 0U) << i;
1696 // Add the padding for the alignment remainder.
1697 header_size += run_size % bracket_size;
1698 DCHECK_EQ(header_size + num_of_slots * bracket_size, run_size);
1699 numOfSlots[i] = num_of_slots;
1700 headerSizes[i] = header_size;
1701 if (kTraceRosAlloc) {
1702 LOG(INFO) << "numOfSlots[" << i << "]=" << numOfSlots[i]
1703 << ", headerSizes[" << i << "]=" << headerSizes[i];
1704 }
1705 }
1706 // Set up the dedicated full run so that nobody can successfully allocate from it.
1707 if (kIsDebugBuild) {
1708 dedicated_full_run_->magic_num_ = kMagicNum;
1709 }
1710 // It doesn't matter which size bracket we use since the main goal is to have the allocation
1711 // fail 100% of the time you attempt to allocate into the dedicated full run.
1712 dedicated_full_run_->size_bracket_idx_ = 0;
1713 DCHECK_EQ(dedicated_full_run_->FreeList()->Size(), 0U); // It looks full.
1714 dedicated_full_run_->SetIsThreadLocal(true);
1715
1716 // The smallest bracket size must be at least as large as the sizeof(Slot).
1717 DCHECK_LE(sizeof(Slot), bracketSizes[0]) << "sizeof(Slot) <= the smallest bracket size";
1718 // Check the invariants between the max bracket sizes and the number of brackets.
1719 DCHECK_EQ(kMaxThreadLocalBracketSize, bracketSizes[kNumThreadLocalSizeBrackets - 1]);
1720 DCHECK_EQ(kMaxRegularBracketSize, bracketSizes[kNumRegularSizeBrackets - 1]);
1721 }
1722
BytesAllocatedCallback(void * start ATTRIBUTE_UNUSED,void * end ATTRIBUTE_UNUSED,size_t used_bytes,void * arg)1723 void RosAlloc::BytesAllocatedCallback(void* start ATTRIBUTE_UNUSED, void* end ATTRIBUTE_UNUSED,
1724 size_t used_bytes, void* arg) {
1725 if (used_bytes == 0) {
1726 return;
1727 }
1728 size_t* bytes_allocated = reinterpret_cast<size_t*>(arg);
1729 *bytes_allocated += used_bytes;
1730 }
1731
ObjectsAllocatedCallback(void * start ATTRIBUTE_UNUSED,void * end ATTRIBUTE_UNUSED,size_t used_bytes,void * arg)1732 void RosAlloc::ObjectsAllocatedCallback(void* start ATTRIBUTE_UNUSED, void* end ATTRIBUTE_UNUSED,
1733 size_t used_bytes, void* arg) {
1734 if (used_bytes == 0) {
1735 return;
1736 }
1737 size_t* objects_allocated = reinterpret_cast<size_t*>(arg);
1738 ++(*objects_allocated);
1739 }
1740
Verify()1741 void RosAlloc::Verify() {
1742 Thread* self = Thread::Current();
1743 CHECK(Locks::mutator_lock_->IsExclusiveHeld(self))
1744 << "The mutator locks isn't exclusively locked at " << __PRETTY_FUNCTION__;
1745 MutexLock thread_list_mu(self, *Locks::thread_list_lock_);
1746 ReaderMutexLock wmu(self, bulk_free_lock_);
1747 std::vector<Run*> runs;
1748 {
1749 MutexLock lock_mu(self, lock_);
1750 size_t pm_end = page_map_size_;
1751 size_t i = 0;
1752 size_t memory_tool_modifier = is_running_on_memory_tool_ ?
1753 2 * ::art::gc::space::kDefaultMemoryToolRedZoneBytes : // Redzones before and after.
1754 0;
1755 while (i < pm_end) {
1756 uint8_t pm = page_map_[i];
1757 switch (pm) {
1758 case kPageMapReleased:
1759 // Fall-through.
1760 case kPageMapEmpty: {
1761 // The start of a free page run.
1762 FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize);
1763 DCHECK_EQ(fpr->magic_num_, kMagicNumFree);
1764 CHECK(free_page_runs_.find(fpr) != free_page_runs_.end())
1765 << "An empty page must belong to the free page run set";
1766 size_t fpr_size = fpr->ByteSize(this);
1767 CHECK_ALIGNED(fpr_size, kPageSize)
1768 << "A free page run size isn't page-aligned : " << fpr_size;
1769 size_t num_pages = fpr_size / kPageSize;
1770 CHECK_GT(num_pages, static_cast<uintptr_t>(0))
1771 << "A free page run size must be > 0 : " << fpr_size;
1772 for (size_t j = i + 1; j < i + num_pages; ++j) {
1773 CHECK(IsFreePage(j))
1774 << "A mismatch between the page map table for kPageMapEmpty "
1775 << " at page index " << j
1776 << " and the free page run size : page index range : "
1777 << i << " to " << (i + num_pages) << std::endl << DumpPageMap();
1778 }
1779 i += num_pages;
1780 CHECK_LE(i, pm_end) << "Page map index " << i << " out of range < " << pm_end
1781 << std::endl << DumpPageMap();
1782 break;
1783 }
1784 case kPageMapLargeObject: {
1785 // The start of a large object.
1786 size_t num_pages = 1;
1787 size_t idx = i + 1;
1788 while (idx < pm_end && page_map_[idx] == kPageMapLargeObjectPart) {
1789 num_pages++;
1790 idx++;
1791 }
1792 uint8_t* start = base_ + i * kPageSize;
1793 if (is_running_on_memory_tool_) {
1794 start += ::art::gc::space::kDefaultMemoryToolRedZoneBytes;
1795 }
1796 mirror::Object* obj = reinterpret_cast<mirror::Object*>(start);
1797 size_t obj_size = obj->SizeOf();
1798 CHECK_GT(obj_size + memory_tool_modifier, kLargeSizeThreshold)
1799 << "A rosalloc large object size must be > " << kLargeSizeThreshold;
1800 CHECK_EQ(num_pages, RoundUp(obj_size + memory_tool_modifier, kPageSize) / kPageSize)
1801 << "A rosalloc large object size " << obj_size + memory_tool_modifier
1802 << " does not match the page map table " << (num_pages * kPageSize)
1803 << std::endl << DumpPageMap();
1804 i += num_pages;
1805 CHECK_LE(i, pm_end) << "Page map index " << i << " out of range < " << pm_end
1806 << std::endl << DumpPageMap();
1807 break;
1808 }
1809 case kPageMapLargeObjectPart:
1810 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm) << std::endl << DumpPageMap();
1811 UNREACHABLE();
1812 case kPageMapRun: {
1813 // The start of a run.
1814 Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize);
1815 DCHECK_EQ(run->magic_num_, kMagicNum);
1816 size_t idx = run->size_bracket_idx_;
1817 CHECK_LT(idx, kNumOfSizeBrackets) << "Out of range size bracket index : " << idx;
1818 size_t num_pages = numOfPages[idx];
1819 CHECK_GT(num_pages, static_cast<uintptr_t>(0))
1820 << "Run size must be > 0 : " << num_pages;
1821 for (size_t j = i + 1; j < i + num_pages; ++j) {
1822 CHECK_EQ(page_map_[j], kPageMapRunPart)
1823 << "A mismatch between the page map table for kPageMapRunPart "
1824 << " at page index " << j
1825 << " and the run size : page index range " << i << " to " << (i + num_pages)
1826 << std::endl << DumpPageMap();
1827 }
1828 // Don't verify the dedicated_full_run_ since it doesn't have any real allocations.
1829 runs.push_back(run);
1830 i += num_pages;
1831 CHECK_LE(i, pm_end) << "Page map index " << i << " out of range < " << pm_end
1832 << std::endl << DumpPageMap();
1833 break;
1834 }
1835 case kPageMapRunPart:
1836 // Fall-through.
1837 default:
1838 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm) << std::endl << DumpPageMap();
1839 UNREACHABLE();
1840 }
1841 }
1842 }
1843 std::list<Thread*> threads = Runtime::Current()->GetThreadList()->GetList();
1844 for (Thread* thread : threads) {
1845 for (size_t i = 0; i < kNumThreadLocalSizeBrackets; ++i) {
1846 MutexLock brackets_mu(self, *size_bracket_locks_[i]);
1847 Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(i));
1848 CHECK(thread_local_run != nullptr);
1849 CHECK(thread_local_run->IsThreadLocal());
1850 CHECK(thread_local_run == dedicated_full_run_ ||
1851 thread_local_run->size_bracket_idx_ == i);
1852 }
1853 }
1854 for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
1855 MutexLock brackets_mu(self, *size_bracket_locks_[i]);
1856 Run* current_run = current_runs_[i];
1857 CHECK(current_run != nullptr);
1858 if (current_run != dedicated_full_run_) {
1859 // The dedicated full run is currently marked as thread local.
1860 CHECK(!current_run->IsThreadLocal());
1861 CHECK_EQ(current_run->size_bracket_idx_, i);
1862 }
1863 }
1864 // Call Verify() here for the lock order.
1865 for (auto& run : runs) {
1866 run->Verify(self, this, is_running_on_memory_tool_);
1867 }
1868 }
1869
Verify(Thread * self,RosAlloc * rosalloc,bool running_on_memory_tool)1870 void RosAlloc::Run::Verify(Thread* self, RosAlloc* rosalloc, bool running_on_memory_tool) {
1871 DCHECK_EQ(magic_num_, kMagicNum) << "Bad magic number : " << Dump();
1872 const size_t idx = size_bracket_idx_;
1873 CHECK_LT(idx, kNumOfSizeBrackets) << "Out of range size bracket index : " << Dump();
1874 uint8_t* slot_base = reinterpret_cast<uint8_t*>(this) + headerSizes[idx];
1875 const size_t num_slots = numOfSlots[idx];
1876 size_t bracket_size = IndexToBracketSize(idx);
1877 CHECK_EQ(slot_base + num_slots * bracket_size,
1878 reinterpret_cast<uint8_t*>(this) + numOfPages[idx] * kPageSize)
1879 << "Mismatch in the end address of the run " << Dump();
1880 // Check that the bulk free list is empty. It's only used during BulkFree().
1881 CHECK(IsBulkFreeListEmpty()) << "The bulk free isn't empty " << Dump();
1882 // Check the thread local runs, the current runs, and the run sets.
1883 if (IsThreadLocal()) {
1884 // If it's a thread local run, then it must be pointed to by an owner thread.
1885 bool owner_found = false;
1886 std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
1887 for (auto it = thread_list.begin(); it != thread_list.end(); ++it) {
1888 Thread* thread = *it;
1889 for (size_t i = 0; i < kNumThreadLocalSizeBrackets; i++) {
1890 MutexLock mu(self, *rosalloc->size_bracket_locks_[i]);
1891 Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(i));
1892 if (thread_local_run == this) {
1893 CHECK(!owner_found)
1894 << "A thread local run has more than one owner thread " << Dump();
1895 CHECK_EQ(i, idx)
1896 << "A mismatching size bracket index in a thread local run " << Dump();
1897 owner_found = true;
1898 }
1899 }
1900 }
1901 CHECK(owner_found) << "A thread local run has no owner thread " << Dump();
1902 } else {
1903 // If it's not thread local, check that the thread local free list is empty.
1904 CHECK(IsThreadLocalFreeListEmpty())
1905 << "A non-thread-local run's thread local free list isn't empty "
1906 << Dump();
1907 // Check if it's a current run for the size bracket.
1908 bool is_current_run = false;
1909 for (size_t i = 0; i < kNumOfSizeBrackets; i++) {
1910 MutexLock mu(self, *rosalloc->size_bracket_locks_[i]);
1911 Run* current_run = rosalloc->current_runs_[i];
1912 if (idx == i) {
1913 if (this == current_run) {
1914 is_current_run = true;
1915 }
1916 } else {
1917 // If the size bucket index does not match, then it must not
1918 // be a current run.
1919 CHECK_NE(this, current_run)
1920 << "A current run points to a run with a wrong size bracket index " << Dump();
1921 }
1922 }
1923 // If it's neither a thread local or current run, then it must be
1924 // in a run set.
1925 if (!is_current_run) {
1926 MutexLock mu(self, rosalloc->lock_);
1927 auto& non_full_runs = rosalloc->non_full_runs_[idx];
1928 // If it's all free, it must be a free page run rather than a run.
1929 CHECK(!IsAllFree()) << "A free run must be in a free page run set " << Dump();
1930 if (!IsFull()) {
1931 // If it's not full, it must in the non-full run set.
1932 CHECK(non_full_runs.find(this) != non_full_runs.end())
1933 << "A non-full run isn't in the non-full run set " << Dump();
1934 } else {
1935 // If it's full, it must in the full run set (debug build only.)
1936 if (kIsDebugBuild) {
1937 auto& full_runs = rosalloc->full_runs_[idx];
1938 CHECK(full_runs.find(this) != full_runs.end())
1939 << " A full run isn't in the full run set " << Dump();
1940 }
1941 }
1942 }
1943 }
1944 // Check each slot.
1945 size_t memory_tool_modifier = running_on_memory_tool ?
1946 2 * ::art::gc::space::kDefaultMemoryToolRedZoneBytes :
1947 0U;
1948 // TODO: reuse InspectAllSlots().
1949 std::unique_ptr<bool[]> is_free(new bool[num_slots]()); // zero initialized
1950 // Mark the free slots and the remaining ones are allocated.
1951 for (Slot* slot = free_list_.Head(); slot != nullptr; slot = slot->Next()) {
1952 size_t slot_idx = SlotIndex(slot);
1953 DCHECK_LT(slot_idx, num_slots);
1954 is_free[slot_idx] = true;
1955 }
1956 if (IsThreadLocal()) {
1957 for (Slot* slot = thread_local_free_list_.Head(); slot != nullptr; slot = slot->Next()) {
1958 size_t slot_idx = SlotIndex(slot);
1959 DCHECK_LT(slot_idx, num_slots);
1960 is_free[slot_idx] = true;
1961 }
1962 }
1963 for (size_t slot_idx = 0; slot_idx < num_slots; ++slot_idx) {
1964 uint8_t* slot_addr = slot_base + slot_idx * bracket_size;
1965 if (running_on_memory_tool) {
1966 slot_addr += ::art::gc::space::kDefaultMemoryToolRedZoneBytes;
1967 }
1968 if (!is_free[slot_idx]) {
1969 // The slot is allocated
1970 mirror::Object* obj = reinterpret_cast<mirror::Object*>(slot_addr);
1971 size_t obj_size = obj->SizeOf();
1972 CHECK_LE(obj_size + memory_tool_modifier, kLargeSizeThreshold)
1973 << "A run slot contains a large object " << Dump();
1974 CHECK_EQ(SizeToIndex(obj_size + memory_tool_modifier), idx)
1975 << obj->PrettyTypeOf() << " "
1976 << "obj_size=" << obj_size << "(" << obj_size + memory_tool_modifier << "), idx=" << idx
1977 << " A run slot contains an object with wrong size " << Dump();
1978 }
1979 }
1980 }
1981
ReleasePages()1982 size_t RosAlloc::ReleasePages() {
1983 VLOG(heap) << "RosAlloc::ReleasePages()";
1984 DCHECK(!DoesReleaseAllPages());
1985 Thread* self = Thread::Current();
1986 size_t reclaimed_bytes = 0;
1987 size_t i = 0;
1988 // Check the page map size which might have changed due to grow/shrink.
1989 while (i < page_map_size_) {
1990 // Reading the page map without a lock is racy but the race is benign since it should only
1991 // result in occasionally not releasing pages which we could release.
1992 uint8_t pm = page_map_[i];
1993 switch (pm) {
1994 case kPageMapReleased:
1995 // Fall through.
1996 case kPageMapEmpty: {
1997 // This is currently the start of a free page run.
1998 // Acquire the lock to prevent other threads racing in and modifying the page map.
1999 MutexLock mu(self, lock_);
2000 // Check that it's still empty after we acquired the lock since another thread could have
2001 // raced in and placed an allocation here.
2002 if (IsFreePage(i)) {
2003 // Free page runs can start with a released page if we coalesced a released page free
2004 // page run with an empty page run.
2005 FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize);
2006 // There is a race condition where FreePage can coalesce fpr with the previous
2007 // free page run before we acquire lock_. In that case free_page_runs_.find will not find
2008 // a run starting at fpr. To handle this race, we skip reclaiming the page range and go
2009 // to the next page.
2010 if (free_page_runs_.find(fpr) != free_page_runs_.end()) {
2011 size_t fpr_size = fpr->ByteSize(this);
2012 DCHECK_ALIGNED(fpr_size, kPageSize);
2013 uint8_t* start = reinterpret_cast<uint8_t*>(fpr);
2014 reclaimed_bytes += ReleasePageRange(start, start + fpr_size);
2015 size_t pages = fpr_size / kPageSize;
2016 CHECK_GT(pages, 0U) << "Infinite loop probable";
2017 i += pages;
2018 DCHECK_LE(i, page_map_size_);
2019 break;
2020 }
2021 }
2022 FALLTHROUGH_INTENDED;
2023 }
2024 case kPageMapLargeObject: // Fall through.
2025 case kPageMapLargeObjectPart: // Fall through.
2026 case kPageMapRun: // Fall through.
2027 case kPageMapRunPart: // Fall through.
2028 ++i;
2029 break; // Skip.
2030 default:
2031 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm);
2032 UNREACHABLE();
2033 }
2034 }
2035 return reclaimed_bytes;
2036 }
2037
ReleasePageRange(uint8_t * start,uint8_t * end)2038 size_t RosAlloc::ReleasePageRange(uint8_t* start, uint8_t* end) {
2039 DCHECK_ALIGNED(start, kPageSize);
2040 DCHECK_ALIGNED(end, kPageSize);
2041 DCHECK_LT(start, end);
2042 if (kIsDebugBuild) {
2043 // In the debug build, the first page of a free page run
2044 // contains a magic number for debugging. Exclude it.
2045 start += kPageSize;
2046
2047 // Single pages won't be released.
2048 if (start == end) {
2049 return 0;
2050 }
2051 }
2052 if (!kMadviseZeroes) {
2053 // TODO: Do this when we resurrect the page instead.
2054 memset(start, 0, end - start);
2055 }
2056 CHECK_EQ(madvise(start, end - start, MADV_DONTNEED), 0);
2057 size_t pm_idx = ToPageMapIndex(start);
2058 size_t reclaimed_bytes = 0;
2059 // Calculate reclaimed bytes and upate page map.
2060 const size_t max_idx = pm_idx + (end - start) / kPageSize;
2061 for (; pm_idx < max_idx; ++pm_idx) {
2062 DCHECK(IsFreePage(pm_idx));
2063 if (page_map_[pm_idx] == kPageMapEmpty) {
2064 // Mark the page as released and update how many bytes we released.
2065 reclaimed_bytes += kPageSize;
2066 page_map_[pm_idx] = kPageMapReleased;
2067 }
2068 }
2069 return reclaimed_bytes;
2070 }
2071
LogFragmentationAllocFailure(std::ostream & os,size_t failed_alloc_bytes)2072 void RosAlloc::LogFragmentationAllocFailure(std::ostream& os, size_t failed_alloc_bytes) {
2073 Thread* self = Thread::Current();
2074 size_t largest_continuous_free_pages = 0;
2075 WriterMutexLock wmu(self, bulk_free_lock_);
2076 MutexLock mu(self, lock_);
2077 uint64_t total_free = 0;
2078 for (FreePageRun* fpr : free_page_runs_) {
2079 largest_continuous_free_pages = std::max(largest_continuous_free_pages,
2080 fpr->ByteSize(this));
2081 total_free += fpr->ByteSize(this);
2082 }
2083 size_t required_bytes = 0;
2084 const char* new_buffer_msg = "";
2085 if (failed_alloc_bytes > kLargeSizeThreshold) {
2086 // Large allocation.
2087 required_bytes = RoundUp(failed_alloc_bytes, kPageSize);
2088 } else {
2089 // Non-large allocation.
2090 required_bytes = numOfPages[SizeToIndex(failed_alloc_bytes)] * kPageSize;
2091 new_buffer_msg = " for a new buffer";
2092 }
2093 if (required_bytes > largest_continuous_free_pages) {
2094 os << "; failed due to fragmentation ("
2095 << "required contiguous free " << required_bytes << " bytes" << new_buffer_msg
2096 << ", largest contiguous free " << largest_continuous_free_pages << " bytes"
2097 << ", total free pages " << total_free << " bytes"
2098 << ", space footprint " << footprint_ << " bytes"
2099 << ", space max capacity " << max_capacity_ << " bytes"
2100 << ")" << std::endl;
2101 }
2102 }
2103
DumpStats(std::ostream & os)2104 void RosAlloc::DumpStats(std::ostream& os) {
2105 Thread* self = Thread::Current();
2106 CHECK(Locks::mutator_lock_->IsExclusiveHeld(self))
2107 << "The mutator locks isn't exclusively locked at " << __PRETTY_FUNCTION__;
2108 size_t num_large_objects = 0;
2109 size_t num_pages_large_objects = 0;
2110 // These arrays are zero initialized.
2111 std::unique_ptr<size_t[]> num_runs(new size_t[kNumOfSizeBrackets]());
2112 std::unique_ptr<size_t[]> num_pages_runs(new size_t[kNumOfSizeBrackets]());
2113 std::unique_ptr<size_t[]> num_slots(new size_t[kNumOfSizeBrackets]());
2114 std::unique_ptr<size_t[]> num_used_slots(new size_t[kNumOfSizeBrackets]());
2115 std::unique_ptr<size_t[]> num_metadata_bytes(new size_t[kNumOfSizeBrackets]());
2116 ReaderMutexLock rmu(self, bulk_free_lock_);
2117 MutexLock lock_mu(self, lock_);
2118 for (size_t i = 0; i < page_map_size_; ) {
2119 uint8_t pm = page_map_[i];
2120 switch (pm) {
2121 case kPageMapReleased:
2122 case kPageMapEmpty:
2123 ++i;
2124 break;
2125 case kPageMapLargeObject: {
2126 size_t num_pages = 1;
2127 size_t idx = i + 1;
2128 while (idx < page_map_size_ && page_map_[idx] == kPageMapLargeObjectPart) {
2129 num_pages++;
2130 idx++;
2131 }
2132 num_large_objects++;
2133 num_pages_large_objects += num_pages;
2134 i += num_pages;
2135 break;
2136 }
2137 case kPageMapLargeObjectPart:
2138 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm) << std::endl
2139 << DumpPageMap();
2140 UNREACHABLE();
2141 case kPageMapRun: {
2142 Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize);
2143 size_t idx = run->size_bracket_idx_;
2144 size_t num_pages = numOfPages[idx];
2145 num_runs[idx]++;
2146 num_pages_runs[idx] += num_pages;
2147 num_slots[idx] += numOfSlots[idx];
2148 size_t num_free_slots = run->NumberOfFreeSlots();
2149 num_used_slots[idx] += numOfSlots[idx] - num_free_slots;
2150 num_metadata_bytes[idx] += headerSizes[idx];
2151 i += num_pages;
2152 break;
2153 }
2154 case kPageMapRunPart:
2155 // Fall-through.
2156 default:
2157 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm) << std::endl
2158 << DumpPageMap();
2159 UNREACHABLE();
2160 }
2161 }
2162 os << "RosAlloc stats:\n";
2163 for (size_t i = 0; i < kNumOfSizeBrackets; ++i) {
2164 os << "Bracket " << i << " (" << bracketSizes[i] << "):"
2165 << " #runs=" << num_runs[i]
2166 << " #pages=" << num_pages_runs[i]
2167 << " (" << PrettySize(num_pages_runs[i] * kPageSize) << ")"
2168 << " #metadata_bytes=" << PrettySize(num_metadata_bytes[i])
2169 << " #slots=" << num_slots[i] << " (" << PrettySize(num_slots[i] * bracketSizes[i]) << ")"
2170 << " #used_slots=" << num_used_slots[i]
2171 << " (" << PrettySize(num_used_slots[i] * bracketSizes[i]) << ")\n";
2172 }
2173 os << "Large #allocations=" << num_large_objects
2174 << " #pages=" << num_pages_large_objects
2175 << " (" << PrettySize(num_pages_large_objects * kPageSize) << ")\n";
2176 size_t total_num_pages = 0;
2177 size_t total_metadata_bytes = 0;
2178 size_t total_allocated_bytes = 0;
2179 for (size_t i = 0; i < kNumOfSizeBrackets; ++i) {
2180 total_num_pages += num_pages_runs[i];
2181 total_metadata_bytes += num_metadata_bytes[i];
2182 total_allocated_bytes += num_used_slots[i] * bracketSizes[i];
2183 }
2184 total_num_pages += num_pages_large_objects;
2185 total_allocated_bytes += num_pages_large_objects * kPageSize;
2186 os << "Total #total_bytes=" << PrettySize(total_num_pages * kPageSize)
2187 << " #metadata_bytes=" << PrettySize(total_metadata_bytes)
2188 << " #used_bytes=" << PrettySize(total_allocated_bytes) << "\n";
2189 os << "\n";
2190 }
2191
2192 } // namespace allocator
2193 } // namespace gc
2194 } // namespace art
2195