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