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