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 <map> 20 #include <list> 21 #include <sstream> 22 #include <vector> 23 24 #include "android-base/stringprintf.h" 25 26 #include "base/memory_tool.h" 27 #include "base/mutex-inl.h" 28 #include "gc/space/memory_tool_settings.h" 29 #include "mem_map.h" 30 #include "mirror/class-inl.h" 31 #include "mirror/object.h" 32 #include "mirror/object-inl.h" 33 #include "thread-current-inl.h" 34 #include "thread_list.h" 35 36 namespace art { 37 namespace gc { 38 namespace allocator { 39 40 using android::base::StringPrintf; 41 42 static constexpr bool kUsePrefetchDuringAllocRun = false; 43 static constexpr bool kPrefetchNewRunDataByZeroing = false; 44 static constexpr size_t kPrefetchStride = 64; 45 46 size_t RosAlloc::bracketSizes[kNumOfSizeBrackets]; 47 size_t RosAlloc::numOfPages[kNumOfSizeBrackets]; 48 size_t RosAlloc::numOfSlots[kNumOfSizeBrackets]; 49 size_t RosAlloc::headerSizes[kNumOfSizeBrackets]; 50 bool RosAlloc::initialized_ = false; 51 size_t RosAlloc::dedicated_full_run_storage_[kPageSize / sizeof(size_t)] = { 0 }; 52 RosAlloc::Run* RosAlloc::dedicated_full_run_ = 53 reinterpret_cast<RosAlloc::Run*>(dedicated_full_run_storage_); 54 55 RosAlloc::RosAlloc(void* base, size_t capacity, size_t max_capacity, 56 PageReleaseMode page_release_mode, bool running_on_memory_tool, 57 size_t page_release_size_threshold) 58 : base_(reinterpret_cast<uint8_t*>(base)), footprint_(capacity), 59 capacity_(capacity), max_capacity_(max_capacity), 60 lock_("rosalloc global lock", kRosAllocGlobalLock), 61 bulk_free_lock_("rosalloc bulk free lock", kRosAllocBulkFreeLock), 62 page_release_mode_(page_release_mode), 63 page_release_size_threshold_(page_release_size_threshold), 64 is_running_on_memory_tool_(running_on_memory_tool) { 65 DCHECK_ALIGNED(base, kPageSize); 66 DCHECK_EQ(RoundUp(capacity, kPageSize), capacity); 67 DCHECK_EQ(RoundUp(max_capacity, kPageSize), max_capacity); 68 CHECK_LE(capacity, max_capacity); 69 CHECK_ALIGNED(page_release_size_threshold_, kPageSize); 70 // Zero the memory explicitly (don't rely on that the mem map is zero-initialized). 71 if (!kMadviseZeroes) { 72 memset(base_, 0, max_capacity); 73 } 74 CHECK_EQ(madvise(base_, max_capacity, MADV_DONTNEED), 0); 75 if (!initialized_) { 76 Initialize(); 77 } 78 VLOG(heap) << "RosAlloc base=" 79 << std::hex << (intptr_t)base_ << ", end=" 80 << std::hex << (intptr_t)(base_ + capacity_) 81 << ", capacity=" << std::dec << capacity_ 82 << ", max_capacity=" << std::dec << max_capacity_; 83 for (size_t i = 0; i < kNumOfSizeBrackets; i++) { 84 size_bracket_lock_names_[i] = 85 StringPrintf("an rosalloc size bracket %d lock", static_cast<int>(i)); 86 size_bracket_locks_[i] = new Mutex(size_bracket_lock_names_[i].c_str(), kRosAllocBracketLock); 87 current_runs_[i] = dedicated_full_run_; 88 } 89 DCHECK_EQ(footprint_, capacity_); 90 size_t num_of_pages = footprint_ / kPageSize; 91 size_t max_num_of_pages = max_capacity_ / kPageSize; 92 std::string error_msg; 93 page_map_mem_map_.reset(MemMap::MapAnonymous("rosalloc page map", nullptr, 94 RoundUp(max_num_of_pages, kPageSize), 95 PROT_READ | PROT_WRITE, false, false, &error_msg)); 96 CHECK(page_map_mem_map_.get() != nullptr) << "Couldn't allocate the page map : " << error_msg; 97 page_map_ = page_map_mem_map_->Begin(); 98 page_map_size_ = num_of_pages; 99 max_page_map_size_ = max_num_of_pages; 100 free_page_run_size_map_.resize(num_of_pages); 101 FreePageRun* free_pages = reinterpret_cast<FreePageRun*>(base_); 102 if (kIsDebugBuild) { 103 free_pages->magic_num_ = kMagicNumFree; 104 } 105 free_pages->SetByteSize(this, capacity_); 106 DCHECK_EQ(capacity_ % kPageSize, static_cast<size_t>(0)); 107 DCHECK(free_pages->IsFree()); 108 free_pages->ReleasePages(this); 109 DCHECK(free_pages->IsFree()); 110 free_page_runs_.insert(free_pages); 111 if (kTraceRosAlloc) { 112 LOG(INFO) << "RosAlloc::RosAlloc() : Inserted run 0x" << std::hex 113 << reinterpret_cast<intptr_t>(free_pages) 114 << " into free_page_runs_"; 115 } 116 } 117 118 RosAlloc::~RosAlloc() { 119 for (size_t i = 0; i < kNumOfSizeBrackets; i++) { 120 delete size_bracket_locks_[i]; 121 } 122 if (is_running_on_memory_tool_) { 123 MEMORY_TOOL_MAKE_DEFINED(base_, capacity_); 124 } 125 } 126 127 void* RosAlloc::AllocPages(Thread* self, size_t num_pages, uint8_t page_map_type) { 128 lock_.AssertHeld(self); 129 DCHECK(page_map_type == kPageMapRun || page_map_type == kPageMapLargeObject); 130 FreePageRun* res = nullptr; 131 const size_t req_byte_size = num_pages * kPageSize; 132 // Find the lowest address free page run that's large enough. 133 for (auto it = free_page_runs_.begin(); it != free_page_runs_.end(); ) { 134 FreePageRun* fpr = *it; 135 DCHECK(fpr->IsFree()); 136 size_t fpr_byte_size = fpr->ByteSize(this); 137 DCHECK_EQ(fpr_byte_size % kPageSize, static_cast<size_t>(0)); 138 if (req_byte_size <= fpr_byte_size) { 139 // Found one. 140 it = free_page_runs_.erase(it); 141 if (kTraceRosAlloc) { 142 LOG(INFO) << "RosAlloc::AllocPages() : Erased run 0x" 143 << std::hex << reinterpret_cast<intptr_t>(fpr) 144 << " from free_page_runs_"; 145 } 146 if (req_byte_size < fpr_byte_size) { 147 // Split. 148 FreePageRun* remainder = 149 reinterpret_cast<FreePageRun*>(reinterpret_cast<uint8_t*>(fpr) + req_byte_size); 150 if (kIsDebugBuild) { 151 remainder->magic_num_ = kMagicNumFree; 152 } 153 remainder->SetByteSize(this, fpr_byte_size - req_byte_size); 154 DCHECK_EQ(remainder->ByteSize(this) % kPageSize, static_cast<size_t>(0)); 155 // Don't need to call madvise on remainder here. 156 free_page_runs_.insert(remainder); 157 if (kTraceRosAlloc) { 158 LOG(INFO) << "RosAlloc::AllocPages() : Inserted run 0x" << std::hex 159 << reinterpret_cast<intptr_t>(remainder) 160 << " into free_page_runs_"; 161 } 162 fpr->SetByteSize(this, req_byte_size); 163 DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0)); 164 } 165 res = fpr; 166 break; 167 } else { 168 ++it; 169 } 170 } 171 172 // Failed to allocate pages. Grow the footprint, if possible. 173 if (UNLIKELY(res == nullptr && capacity_ > footprint_)) { 174 FreePageRun* last_free_page_run = nullptr; 175 size_t last_free_page_run_size; 176 auto it = free_page_runs_.rbegin(); 177 if (it != free_page_runs_.rend() && (last_free_page_run = *it)->End(this) == base_ + footprint_) { 178 // There is a free page run at the end. 179 DCHECK(last_free_page_run->IsFree()); 180 DCHECK(IsFreePage(ToPageMapIndex(last_free_page_run))); 181 last_free_page_run_size = last_free_page_run->ByteSize(this); 182 } else { 183 // There is no free page run at the end. 184 last_free_page_run_size = 0; 185 } 186 DCHECK_LT(last_free_page_run_size, req_byte_size); 187 if (capacity_ - footprint_ + last_free_page_run_size >= req_byte_size) { 188 // If we grow the heap, we can allocate it. 189 size_t increment = std::min(std::max(2 * MB, req_byte_size - last_free_page_run_size), 190 capacity_ - footprint_); 191 DCHECK_EQ(increment % kPageSize, static_cast<size_t>(0)); 192 size_t new_footprint = footprint_ + increment; 193 size_t new_num_of_pages = new_footprint / kPageSize; 194 DCHECK_LT(page_map_size_, new_num_of_pages); 195 DCHECK_LT(free_page_run_size_map_.size(), new_num_of_pages); 196 page_map_size_ = new_num_of_pages; 197 DCHECK_LE(page_map_size_, max_page_map_size_); 198 free_page_run_size_map_.resize(new_num_of_pages); 199 ArtRosAllocMoreCore(this, increment); 200 if (last_free_page_run_size > 0) { 201 // There was a free page run at the end. Expand its size. 202 DCHECK_EQ(last_free_page_run_size, last_free_page_run->ByteSize(this)); 203 last_free_page_run->SetByteSize(this, last_free_page_run_size + increment); 204 DCHECK_EQ(last_free_page_run->ByteSize(this) % kPageSize, static_cast<size_t>(0)); 205 DCHECK_EQ(last_free_page_run->End(this), base_ + new_footprint); 206 } else { 207 // Otherwise, insert a new free page run at the end. 208 FreePageRun* new_free_page_run = reinterpret_cast<FreePageRun*>(base_ + footprint_); 209 if (kIsDebugBuild) { 210 new_free_page_run->magic_num_ = kMagicNumFree; 211 } 212 new_free_page_run->SetByteSize(this, increment); 213 DCHECK_EQ(new_free_page_run->ByteSize(this) % kPageSize, static_cast<size_t>(0)); 214 free_page_runs_.insert(new_free_page_run); 215 DCHECK_EQ(*free_page_runs_.rbegin(), new_free_page_run); 216 if (kTraceRosAlloc) { 217 LOG(INFO) << "RosAlloc::AlloPages() : Grew the heap by inserting run 0x" 218 << std::hex << reinterpret_cast<intptr_t>(new_free_page_run) 219 << " into free_page_runs_"; 220 } 221 } 222 DCHECK_LE(footprint_ + increment, capacity_); 223 if (kTraceRosAlloc) { 224 LOG(INFO) << "RosAlloc::AllocPages() : increased the footprint from " 225 << footprint_ << " to " << new_footprint; 226 } 227 footprint_ = new_footprint; 228 229 // And retry the last free page run. 230 it = free_page_runs_.rbegin(); 231 DCHECK(it != free_page_runs_.rend()); 232 FreePageRun* fpr = *it; 233 if (kIsDebugBuild && last_free_page_run_size > 0) { 234 DCHECK(last_free_page_run != nullptr); 235 DCHECK_EQ(last_free_page_run, fpr); 236 } 237 size_t fpr_byte_size = fpr->ByteSize(this); 238 DCHECK_EQ(fpr_byte_size % kPageSize, static_cast<size_t>(0)); 239 DCHECK_LE(req_byte_size, fpr_byte_size); 240 free_page_runs_.erase(fpr); 241 if (kTraceRosAlloc) { 242 LOG(INFO) << "RosAlloc::AllocPages() : Erased run 0x" << std::hex << reinterpret_cast<intptr_t>(fpr) 243 << " from free_page_runs_"; 244 } 245 if (req_byte_size < fpr_byte_size) { 246 // Split if there's a remainder. 247 FreePageRun* remainder = reinterpret_cast<FreePageRun*>(reinterpret_cast<uint8_t*>(fpr) + req_byte_size); 248 if (kIsDebugBuild) { 249 remainder->magic_num_ = kMagicNumFree; 250 } 251 remainder->SetByteSize(this, fpr_byte_size - req_byte_size); 252 DCHECK_EQ(remainder->ByteSize(this) % kPageSize, static_cast<size_t>(0)); 253 free_page_runs_.insert(remainder); 254 if (kTraceRosAlloc) { 255 LOG(INFO) << "RosAlloc::AllocPages() : Inserted run 0x" << std::hex 256 << reinterpret_cast<intptr_t>(remainder) 257 << " into free_page_runs_"; 258 } 259 fpr->SetByteSize(this, req_byte_size); 260 DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0)); 261 } 262 res = fpr; 263 } 264 } 265 if (LIKELY(res != nullptr)) { 266 // Update the page map. 267 size_t page_map_idx = ToPageMapIndex(res); 268 for (size_t i = 0; i < num_pages; i++) { 269 DCHECK(IsFreePage(page_map_idx + i)); 270 } 271 switch (page_map_type) { 272 case kPageMapRun: 273 page_map_[page_map_idx] = kPageMapRun; 274 for (size_t i = 1; i < num_pages; i++) { 275 page_map_[page_map_idx + i] = kPageMapRunPart; 276 } 277 break; 278 case kPageMapLargeObject: 279 page_map_[page_map_idx] = kPageMapLargeObject; 280 for (size_t i = 1; i < num_pages; i++) { 281 page_map_[page_map_idx + i] = kPageMapLargeObjectPart; 282 } 283 break; 284 default: 285 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_type); 286 break; 287 } 288 if (kIsDebugBuild) { 289 // Clear the first page since it is not madvised due to the magic number. 290 memset(res, 0, kPageSize); 291 } 292 if (kTraceRosAlloc) { 293 LOG(INFO) << "RosAlloc::AllocPages() : 0x" << std::hex << reinterpret_cast<intptr_t>(res) 294 << "-0x" << (reinterpret_cast<intptr_t>(res) + num_pages * kPageSize) 295 << "(" << std::dec << (num_pages * kPageSize) << ")"; 296 } 297 return res; 298 } 299 300 // Fail. 301 if (kTraceRosAlloc) { 302 LOG(INFO) << "RosAlloc::AllocPages() : nullptr"; 303 } 304 return nullptr; 305 } 306 307 size_t RosAlloc::FreePages(Thread* self, void* ptr, bool already_zero) { 308 lock_.AssertHeld(self); 309 size_t pm_idx = ToPageMapIndex(ptr); 310 DCHECK_LT(pm_idx, page_map_size_); 311 uint8_t pm_type = page_map_[pm_idx]; 312 DCHECK(pm_type == kPageMapRun || pm_type == kPageMapLargeObject); 313 uint8_t pm_part_type; 314 switch (pm_type) { 315 case kPageMapRun: 316 pm_part_type = kPageMapRunPart; 317 break; 318 case kPageMapLargeObject: 319 pm_part_type = kPageMapLargeObjectPart; 320 break; 321 default: 322 LOG(FATAL) << "Unreachable - " << __PRETTY_FUNCTION__ << " : " << "pm_idx=" << pm_idx << ", pm_type=" 323 << static_cast<int>(pm_type) << ", ptr=" << std::hex 324 << reinterpret_cast<intptr_t>(ptr); 325 return 0; 326 } 327 // Update the page map and count the number of pages. 328 size_t num_pages = 1; 329 page_map_[pm_idx] = kPageMapEmpty; 330 size_t idx = pm_idx + 1; 331 size_t end = page_map_size_; 332 while (idx < end && page_map_[idx] == pm_part_type) { 333 page_map_[idx] = kPageMapEmpty; 334 num_pages++; 335 idx++; 336 } 337 const size_t byte_size = num_pages * kPageSize; 338 if (already_zero) { 339 if (ShouldCheckZeroMemory()) { 340 const uintptr_t* word_ptr = reinterpret_cast<uintptr_t*>(ptr); 341 for (size_t i = 0; i < byte_size / sizeof(uintptr_t); ++i) { 342 CHECK_EQ(word_ptr[i], 0U) << "words don't match at index " << i; 343 } 344 } 345 } else if (!DoesReleaseAllPages()) { 346 memset(ptr, 0, byte_size); 347 } 348 349 if (kTraceRosAlloc) { 350 LOG(INFO) << __PRETTY_FUNCTION__ << " : 0x" << std::hex << reinterpret_cast<intptr_t>(ptr) 351 << "-0x" << (reinterpret_cast<intptr_t>(ptr) + byte_size) 352 << "(" << std::dec << (num_pages * kPageSize) << ")"; 353 } 354 355 // Turn it into a free run. 356 FreePageRun* fpr = reinterpret_cast<FreePageRun*>(ptr); 357 if (kIsDebugBuild) { 358 fpr->magic_num_ = kMagicNumFree; 359 } 360 fpr->SetByteSize(this, byte_size); 361 DCHECK_ALIGNED(fpr->ByteSize(this), kPageSize); 362 363 DCHECK(free_page_runs_.find(fpr) == free_page_runs_.end()); 364 if (!free_page_runs_.empty()) { 365 // Try to coalesce in the higher address direction. 366 if (kTraceRosAlloc) { 367 LOG(INFO) << __PRETTY_FUNCTION__ << "RosAlloc::FreePages() : trying to coalesce a free page run 0x" 368 << std::hex << reinterpret_cast<uintptr_t>(fpr) << " [" << std::dec << pm_idx << "] -0x" 369 << std::hex << reinterpret_cast<uintptr_t>(fpr->End(this)) << " [" << std::dec 370 << (fpr->End(this) == End() ? page_map_size_ : ToPageMapIndex(fpr->End(this))) << "]"; 371 } 372 for (auto it = free_page_runs_.upper_bound(fpr); it != free_page_runs_.end(); ) { 373 FreePageRun* h = *it; 374 DCHECK_EQ(h->ByteSize(this) % kPageSize, static_cast<size_t>(0)); 375 if (kTraceRosAlloc) { 376 LOG(INFO) << "RosAlloc::FreePages() : trying to coalesce with a higher free page run 0x" 377 << std::hex << reinterpret_cast<uintptr_t>(h) << " [" << std::dec << ToPageMapIndex(h) << "] -0x" 378 << std::hex << reinterpret_cast<uintptr_t>(h->End(this)) << " [" << std::dec 379 << (h->End(this) == End() ? page_map_size_ : ToPageMapIndex(h->End(this))) << "]"; 380 } 381 if (fpr->End(this) == h->Begin()) { 382 if (kTraceRosAlloc) { 383 LOG(INFO) << "Success"; 384 } 385 // Clear magic num since this is no longer the start of a free page run. 386 if (kIsDebugBuild) { 387 h->magic_num_ = 0; 388 } 389 it = free_page_runs_.erase(it); 390 if (kTraceRosAlloc) { 391 LOG(INFO) << "RosAlloc::FreePages() : (coalesce) Erased run 0x" << std::hex 392 << reinterpret_cast<intptr_t>(h) 393 << " from free_page_runs_"; 394 } 395 fpr->SetByteSize(this, fpr->ByteSize(this) + h->ByteSize(this)); 396 DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0)); 397 } else { 398 // Not adjacent. Stop. 399 if (kTraceRosAlloc) { 400 LOG(INFO) << "Fail"; 401 } 402 break; 403 } 404 } 405 // Try to coalesce in the lower address direction. 406 for (auto it = free_page_runs_.upper_bound(fpr); it != free_page_runs_.begin(); ) { 407 --it; 408 409 FreePageRun* l = *it; 410 DCHECK_EQ(l->ByteSize(this) % kPageSize, static_cast<size_t>(0)); 411 if (kTraceRosAlloc) { 412 LOG(INFO) << "RosAlloc::FreePages() : trying to coalesce with a lower free page run 0x" 413 << std::hex << reinterpret_cast<uintptr_t>(l) << " [" << std::dec << ToPageMapIndex(l) << "] -0x" 414 << std::hex << reinterpret_cast<uintptr_t>(l->End(this)) << " [" << std::dec 415 << (l->End(this) == End() ? page_map_size_ : ToPageMapIndex(l->End(this))) << "]"; 416 } 417 if (l->End(this) == fpr->Begin()) { 418 if (kTraceRosAlloc) { 419 LOG(INFO) << "Success"; 420 } 421 it = free_page_runs_.erase(it); 422 if (kTraceRosAlloc) { 423 LOG(INFO) << "RosAlloc::FreePages() : (coalesce) Erased run 0x" << std::hex 424 << reinterpret_cast<intptr_t>(l) 425 << " from free_page_runs_"; 426 } 427 l->SetByteSize(this, l->ByteSize(this) + fpr->ByteSize(this)); 428 DCHECK_EQ(l->ByteSize(this) % kPageSize, static_cast<size_t>(0)); 429 // Clear magic num since this is no longer the start of a free page run. 430 if (kIsDebugBuild) { 431 fpr->magic_num_ = 0; 432 } 433 fpr = l; 434 } else { 435 // Not adjacent. Stop. 436 if (kTraceRosAlloc) { 437 LOG(INFO) << "Fail"; 438 } 439 break; 440 } 441 } 442 } 443 444 // Insert it. 445 DCHECK_EQ(fpr->ByteSize(this) % kPageSize, static_cast<size_t>(0)); 446 DCHECK(free_page_runs_.find(fpr) == free_page_runs_.end()); 447 DCHECK(fpr->IsFree()); 448 fpr->ReleasePages(this); 449 DCHECK(fpr->IsFree()); 450 free_page_runs_.insert(fpr); 451 DCHECK(free_page_runs_.find(fpr) != free_page_runs_.end()); 452 if (kTraceRosAlloc) { 453 LOG(INFO) << "RosAlloc::FreePages() : Inserted run 0x" << std::hex << reinterpret_cast<intptr_t>(fpr) 454 << " into free_page_runs_"; 455 } 456 return byte_size; 457 } 458 459 void* RosAlloc::AllocLargeObject(Thread* self, size_t size, size_t* bytes_allocated, 460 size_t* usable_size, size_t* bytes_tl_bulk_allocated) { 461 DCHECK(bytes_allocated != nullptr); 462 DCHECK(usable_size != nullptr); 463 DCHECK_GT(size, kLargeSizeThreshold); 464 size_t num_pages = RoundUp(size, kPageSize) / kPageSize; 465 void* r; 466 { 467 MutexLock mu(self, lock_); 468 r = AllocPages(self, num_pages, kPageMapLargeObject); 469 } 470 if (UNLIKELY(r == nullptr)) { 471 if (kTraceRosAlloc) { 472 LOG(INFO) << "RosAlloc::AllocLargeObject() : nullptr"; 473 } 474 return nullptr; 475 } 476 const size_t total_bytes = num_pages * kPageSize; 477 *bytes_allocated = total_bytes; 478 *usable_size = total_bytes; 479 *bytes_tl_bulk_allocated = total_bytes; 480 if (kTraceRosAlloc) { 481 LOG(INFO) << "RosAlloc::AllocLargeObject() : 0x" << std::hex << reinterpret_cast<intptr_t>(r) 482 << "-0x" << (reinterpret_cast<intptr_t>(r) + num_pages * kPageSize) 483 << "(" << std::dec << (num_pages * kPageSize) << ")"; 484 } 485 // Check if the returned memory is really all zero. 486 if (ShouldCheckZeroMemory()) { 487 CHECK_EQ(total_bytes % sizeof(uintptr_t), 0U); 488 const uintptr_t* words = reinterpret_cast<uintptr_t*>(r); 489 for (size_t i = 0; i < total_bytes / sizeof(uintptr_t); ++i) { 490 CHECK_EQ(words[i], 0U); 491 } 492 } 493 return r; 494 } 495 496 size_t RosAlloc::FreeInternal(Thread* self, void* ptr) { 497 DCHECK_LE(base_, ptr); 498 DCHECK_LT(ptr, base_ + footprint_); 499 size_t pm_idx = RoundDownToPageMapIndex(ptr); 500 Run* run = nullptr; 501 { 502 MutexLock mu(self, lock_); 503 DCHECK_LT(pm_idx, page_map_size_); 504 uint8_t page_map_entry = page_map_[pm_idx]; 505 if (kTraceRosAlloc) { 506 LOG(INFO) << "RosAlloc::FreeInternal() : " << std::hex << ptr << ", pm_idx=" << std::dec << pm_idx 507 << ", page_map_entry=" << static_cast<int>(page_map_entry); 508 } 509 switch (page_map_[pm_idx]) { 510 case kPageMapLargeObject: 511 return FreePages(self, ptr, false); 512 case kPageMapLargeObjectPart: 513 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]); 514 return 0; 515 case kPageMapRunPart: { 516 // Find the beginning of the run. 517 do { 518 --pm_idx; 519 DCHECK_LT(pm_idx, capacity_ / kPageSize); 520 } while (page_map_[pm_idx] != kPageMapRun); 521 FALLTHROUGH_INTENDED; 522 case kPageMapRun: 523 run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize); 524 DCHECK_EQ(run->magic_num_, kMagicNum); 525 break; 526 case kPageMapReleased: 527 case kPageMapEmpty: 528 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]); 529 return 0; 530 } 531 default: 532 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(page_map_[pm_idx]); 533 return 0; 534 } 535 } 536 DCHECK(run != nullptr); 537 return FreeFromRun(self, ptr, run); 538 } 539 540 size_t RosAlloc::Free(Thread* self, void* ptr) { 541 ReaderMutexLock rmu(self, bulk_free_lock_); 542 return FreeInternal(self, ptr); 543 } 544 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 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 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 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 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(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 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> 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 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 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 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 bool 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 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 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 913 inline void RosAlloc::Run::AddToThreadLocalFreeList(void* ptr) { 914 DCHECK(IsThreadLocal()); 915 AddToFreeListShared(ptr, &thread_local_free_list_, __FUNCTION__); 916 } 917 918 inline size_t RosAlloc::Run::AddToBulkFreeList(void* ptr) { 919 return AddToFreeListShared(ptr, &bulk_free_list_, __FUNCTION__); 920 } 921 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 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] * kPageSize; 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 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 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] * kPageSize); 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. Disabled for now. 1001 static constexpr bool kReadPageMapEntryWithoutLockInBulkFree = true; 1002 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 * kPageSize); 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, capacity_ / kPageSize); 1044 } while (page_map_[pi] != kPageMapRun); 1045 run = reinterpret_cast<Run*>(base_ + pi * kPageSize); 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 * kPageSize); 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, capacity_ / kPageSize); 1071 } while (page_map_[pi] != kPageMapRun); 1072 run = reinterpret_cast<Run*>(base_ + pi * kPageSize); 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 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 * kPageSize); 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(curr_fpr_size % kPageSize, static_cast<size_t>(0)); 1230 remaining_curr_fpr_size = curr_fpr_size - kPageSize; 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(remaining_curr_fpr_size % kPageSize, static_cast<size_t>(0)); 1246 DCHECK_GE(remaining_curr_fpr_size, static_cast<size_t>(kPageSize)); 1247 remaining_curr_fpr_size -= kPageSize; 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 * kPageSize); 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 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 break; 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 * kPageSize; 1317 } 1318 case kPageMapLargeObjectPart: 1319 LOG(FATAL) << "Unreachable - " << __PRETTY_FUNCTION__ << ": pm_idx=" << pm_idx << ", ptr=" 1320 << std::hex << reinterpret_cast<intptr_t>(ptr); 1321 break; 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, capacity_ / kPageSize); 1328 } 1329 DCHECK_EQ(page_map_[pm_idx], kPageMapRun); 1330 Run* run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize); 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 break; 1341 } 1342 } 1343 return 0; 1344 } 1345 1346 bool RosAlloc::Trim() { 1347 MutexLock mu(Thread::Current(), lock_); 1348 FreePageRun* last_free_page_run; 1349 DCHECK_EQ(footprint_ % kPageSize, static_cast<size_t>(0)); 1350 auto it = free_page_runs_.rbegin(); 1351 if (it != free_page_runs_.rend() && (last_free_page_run = *it)->End(this) == base_ + footprint_) { 1352 // Remove the last free page run, if any. 1353 DCHECK(last_free_page_run->IsFree()); 1354 DCHECK(IsFreePage(ToPageMapIndex(last_free_page_run))); 1355 DCHECK_EQ(last_free_page_run->ByteSize(this) % kPageSize, static_cast<size_t>(0)); 1356 DCHECK_EQ(last_free_page_run->End(this), base_ + footprint_); 1357 free_page_runs_.erase(last_free_page_run); 1358 size_t decrement = last_free_page_run->ByteSize(this); 1359 size_t new_footprint = footprint_ - decrement; 1360 DCHECK_EQ(new_footprint % kPageSize, static_cast<size_t>(0)); 1361 size_t new_num_of_pages = new_footprint / kPageSize; 1362 DCHECK_GE(page_map_size_, new_num_of_pages); 1363 // Zero out the tail of the page map. 1364 uint8_t* zero_begin = const_cast<uint8_t*>(page_map_) + new_num_of_pages; 1365 uint8_t* madvise_begin = AlignUp(zero_begin, kPageSize); 1366 DCHECK_LE(madvise_begin, page_map_mem_map_->End()); 1367 size_t madvise_size = page_map_mem_map_->End() - madvise_begin; 1368 if (madvise_size > 0) { 1369 DCHECK_ALIGNED(madvise_begin, kPageSize); 1370 DCHECK_EQ(RoundUp(madvise_size, kPageSize), madvise_size); 1371 if (!kMadviseZeroes) { 1372 memset(madvise_begin, 0, madvise_size); 1373 } 1374 CHECK_EQ(madvise(madvise_begin, madvise_size, MADV_DONTNEED), 0); 1375 } 1376 if (madvise_begin - zero_begin) { 1377 memset(zero_begin, 0, madvise_begin - zero_begin); 1378 } 1379 page_map_size_ = new_num_of_pages; 1380 free_page_run_size_map_.resize(new_num_of_pages); 1381 DCHECK_EQ(free_page_run_size_map_.size(), new_num_of_pages); 1382 ArtRosAllocMoreCore(this, -(static_cast<intptr_t>(decrement))); 1383 if (kTraceRosAlloc) { 1384 LOG(INFO) << "RosAlloc::Trim() : decreased the footprint from " 1385 << footprint_ << " to " << new_footprint; 1386 } 1387 DCHECK_LT(new_footprint, footprint_); 1388 DCHECK_LT(new_footprint, capacity_); 1389 footprint_ = new_footprint; 1390 return true; 1391 } 1392 return false; 1393 } 1394 1395 void RosAlloc::InspectAll(void (*handler)(void* start, void* end, size_t used_bytes, void* callback_arg), 1396 void* arg) { 1397 // Note: no need to use this to release pages as we already do so in FreePages(). 1398 if (handler == nullptr) { 1399 return; 1400 } 1401 MutexLock mu(Thread::Current(), lock_); 1402 size_t pm_end = page_map_size_; 1403 size_t i = 0; 1404 while (i < pm_end) { 1405 uint8_t pm = page_map_[i]; 1406 switch (pm) { 1407 case kPageMapReleased: 1408 // Fall-through. 1409 case kPageMapEmpty: { 1410 // The start of a free page run. 1411 FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize); 1412 DCHECK(free_page_runs_.find(fpr) != free_page_runs_.end()); 1413 size_t fpr_size = fpr->ByteSize(this); 1414 DCHECK_ALIGNED(fpr_size, kPageSize); 1415 void* start = fpr; 1416 if (kIsDebugBuild) { 1417 // In the debug build, the first page of a free page run 1418 // contains a magic number for debugging. Exclude it. 1419 start = reinterpret_cast<uint8_t*>(fpr) + kPageSize; 1420 } 1421 void* end = reinterpret_cast<uint8_t*>(fpr) + fpr_size; 1422 handler(start, end, 0, arg); 1423 size_t num_pages = fpr_size / kPageSize; 1424 if (kIsDebugBuild) { 1425 for (size_t j = i + 1; j < i + num_pages; ++j) { 1426 DCHECK(IsFreePage(j)); 1427 } 1428 } 1429 i += fpr_size / kPageSize; 1430 DCHECK_LE(i, pm_end); 1431 break; 1432 } 1433 case kPageMapLargeObject: { 1434 // The start of a large object. 1435 size_t num_pages = 1; 1436 size_t idx = i + 1; 1437 while (idx < pm_end && page_map_[idx] == kPageMapLargeObjectPart) { 1438 num_pages++; 1439 idx++; 1440 } 1441 void* start = base_ + i * kPageSize; 1442 void* end = base_ + (i + num_pages) * kPageSize; 1443 size_t used_bytes = num_pages * kPageSize; 1444 handler(start, end, used_bytes, arg); 1445 if (kIsDebugBuild) { 1446 for (size_t j = i + 1; j < i + num_pages; ++j) { 1447 DCHECK_EQ(page_map_[j], kPageMapLargeObjectPart); 1448 } 1449 } 1450 i += num_pages; 1451 DCHECK_LE(i, pm_end); 1452 break; 1453 } 1454 case kPageMapLargeObjectPart: 1455 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm); 1456 break; 1457 case kPageMapRun: { 1458 // The start of a run. 1459 Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize); 1460 DCHECK_EQ(run->magic_num_, kMagicNum); 1461 // The dedicated full run doesn't contain any real allocations, don't visit the slots in 1462 // there. 1463 run->InspectAllSlots(handler, arg); 1464 size_t num_pages = numOfPages[run->size_bracket_idx_]; 1465 if (kIsDebugBuild) { 1466 for (size_t j = i + 1; j < i + num_pages; ++j) { 1467 DCHECK_EQ(page_map_[j], kPageMapRunPart); 1468 } 1469 } 1470 i += num_pages; 1471 DCHECK_LE(i, pm_end); 1472 break; 1473 } 1474 case kPageMapRunPart: 1475 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm); 1476 break; 1477 default: 1478 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm); 1479 break; 1480 } 1481 } 1482 } 1483 1484 size_t RosAlloc::Footprint() { 1485 MutexLock mu(Thread::Current(), lock_); 1486 return footprint_; 1487 } 1488 1489 size_t RosAlloc::FootprintLimit() { 1490 MutexLock mu(Thread::Current(), lock_); 1491 return capacity_; 1492 } 1493 1494 void RosAlloc::SetFootprintLimit(size_t new_capacity) { 1495 MutexLock mu(Thread::Current(), lock_); 1496 DCHECK_EQ(RoundUp(new_capacity, kPageSize), new_capacity); 1497 // Only growing is supported here. But Trim() is supported. 1498 if (capacity_ < new_capacity) { 1499 CHECK_LE(new_capacity, max_capacity_); 1500 capacity_ = new_capacity; 1501 VLOG(heap) << "new capacity=" << capacity_; 1502 } 1503 } 1504 1505 // Below may be called by mutator itself just before thread termination. 1506 size_t RosAlloc::RevokeThreadLocalRuns(Thread* thread) { 1507 Thread* self = Thread::Current(); 1508 size_t free_bytes = 0U; 1509 for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; idx++) { 1510 MutexLock mu(self, *size_bracket_locks_[idx]); 1511 Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(idx)); 1512 CHECK(thread_local_run != nullptr); 1513 // Invalid means already revoked. 1514 DCHECK(thread_local_run->IsThreadLocal()); 1515 if (thread_local_run != dedicated_full_run_) { 1516 // Note the thread local run may not be full here. 1517 thread->SetRosAllocRun(idx, dedicated_full_run_); 1518 DCHECK_EQ(thread_local_run->magic_num_, kMagicNum); 1519 // Count the number of free slots left. 1520 size_t num_free_slots = thread_local_run->NumberOfFreeSlots(); 1521 free_bytes += num_free_slots * bracketSizes[idx]; 1522 // The above bracket index lock guards thread local free list to avoid race condition 1523 // with unioning bulk free list to thread local free list by GC thread in BulkFree. 1524 // If thread local run is true, GC thread will help update thread local free list 1525 // in BulkFree. And the latest thread local free list will be merged to free list 1526 // either when this thread local run is full or when revoking this run here. In this 1527 // case the free list wll be updated. If thread local run is false, GC thread will help 1528 // merge bulk free list in next BulkFree. 1529 // Thus no need to merge bulk free list to free list again here. 1530 bool dont_care; 1531 thread_local_run->MergeThreadLocalFreeListToFreeList(&dont_care); 1532 thread_local_run->SetIsThreadLocal(false); 1533 DCHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end()); 1534 DCHECK(full_runs_[idx].find(thread_local_run) == full_runs_[idx].end()); 1535 RevokeRun(self, idx, thread_local_run); 1536 } 1537 } 1538 return free_bytes; 1539 } 1540 1541 void RosAlloc::RevokeRun(Thread* self, size_t idx, Run* run) { 1542 size_bracket_locks_[idx]->AssertHeld(self); 1543 DCHECK(run != dedicated_full_run_); 1544 if (run->IsFull()) { 1545 if (kIsDebugBuild) { 1546 full_runs_[idx].insert(run); 1547 DCHECK(full_runs_[idx].find(run) != full_runs_[idx].end()); 1548 if (kTraceRosAlloc) { 1549 LOG(INFO) << __PRETTY_FUNCTION__ << " : Inserted run 0x" << std::hex 1550 << reinterpret_cast<intptr_t>(run) 1551 << " into full_runs_[" << std::dec << idx << "]"; 1552 } 1553 } 1554 } else if (run->IsAllFree()) { 1555 run->ZeroHeaderAndSlotHeaders(); 1556 MutexLock mu(self, lock_); 1557 FreePages(self, run, true); 1558 } else { 1559 non_full_runs_[idx].insert(run); 1560 DCHECK(non_full_runs_[idx].find(run) != non_full_runs_[idx].end()); 1561 if (kTraceRosAlloc) { 1562 LOG(INFO) << __PRETTY_FUNCTION__ << " : Inserted run 0x" << std::hex 1563 << reinterpret_cast<intptr_t>(run) 1564 << " into non_full_runs_[" << std::dec << idx << "]"; 1565 } 1566 } 1567 } 1568 1569 void RosAlloc::RevokeThreadUnsafeCurrentRuns() { 1570 // Revoke the current runs which share the same idx as thread local runs. 1571 Thread* self = Thread::Current(); 1572 for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; ++idx) { 1573 MutexLock mu(self, *size_bracket_locks_[idx]); 1574 if (current_runs_[idx] != dedicated_full_run_) { 1575 RevokeRun(self, idx, current_runs_[idx]); 1576 current_runs_[idx] = dedicated_full_run_; 1577 } 1578 } 1579 } 1580 1581 size_t RosAlloc::RevokeAllThreadLocalRuns() { 1582 // This is called when a mutator thread won't allocate such as at 1583 // the Zygote creation time or during the GC pause. 1584 MutexLock mu(Thread::Current(), *Locks::runtime_shutdown_lock_); 1585 MutexLock mu2(Thread::Current(), *Locks::thread_list_lock_); 1586 std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList(); 1587 size_t free_bytes = 0U; 1588 for (Thread* thread : thread_list) { 1589 free_bytes += RevokeThreadLocalRuns(thread); 1590 } 1591 RevokeThreadUnsafeCurrentRuns(); 1592 return free_bytes; 1593 } 1594 1595 void RosAlloc::AssertThreadLocalRunsAreRevoked(Thread* thread) { 1596 if (kIsDebugBuild) { 1597 Thread* self = Thread::Current(); 1598 // Avoid race conditions on the bulk free bit maps with BulkFree() (GC). 1599 ReaderMutexLock wmu(self, bulk_free_lock_); 1600 for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; idx++) { 1601 MutexLock mu(self, *size_bracket_locks_[idx]); 1602 Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(idx)); 1603 DCHECK(thread_local_run == nullptr || thread_local_run == dedicated_full_run_); 1604 } 1605 } 1606 } 1607 1608 void RosAlloc::AssertAllThreadLocalRunsAreRevoked() { 1609 if (kIsDebugBuild) { 1610 Thread* self = Thread::Current(); 1611 MutexLock shutdown_mu(self, *Locks::runtime_shutdown_lock_); 1612 MutexLock thread_list_mu(self, *Locks::thread_list_lock_); 1613 std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList(); 1614 for (Thread* t : thread_list) { 1615 AssertThreadLocalRunsAreRevoked(t); 1616 } 1617 for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; ++idx) { 1618 MutexLock brackets_mu(self, *size_bracket_locks_[idx]); 1619 CHECK_EQ(current_runs_[idx], dedicated_full_run_); 1620 } 1621 } 1622 } 1623 1624 void RosAlloc::Initialize() { 1625 // bracketSizes. 1626 static_assert(kNumRegularSizeBrackets == kNumOfSizeBrackets - 2, 1627 "There should be two non-regular brackets"); 1628 for (size_t i = 0; i < kNumOfSizeBrackets; i++) { 1629 if (i < kNumThreadLocalSizeBrackets) { 1630 bracketSizes[i] = kThreadLocalBracketQuantumSize * (i + 1); 1631 } else if (i < kNumRegularSizeBrackets) { 1632 bracketSizes[i] = kBracketQuantumSize * (i - kNumThreadLocalSizeBrackets + 1) + 1633 (kThreadLocalBracketQuantumSize * kNumThreadLocalSizeBrackets); 1634 } else if (i == kNumOfSizeBrackets - 2) { 1635 bracketSizes[i] = 1 * KB; 1636 } else { 1637 DCHECK_EQ(i, kNumOfSizeBrackets - 1); 1638 bracketSizes[i] = 2 * KB; 1639 } 1640 if (kTraceRosAlloc) { 1641 LOG(INFO) << "bracketSizes[" << i << "]=" << bracketSizes[i]; 1642 } 1643 } 1644 // numOfPages. 1645 for (size_t i = 0; i < kNumOfSizeBrackets; i++) { 1646 if (i < kNumThreadLocalSizeBrackets) { 1647 numOfPages[i] = 1; 1648 } else if (i < (kNumThreadLocalSizeBrackets + kNumRegularSizeBrackets) / 2) { 1649 numOfPages[i] = 1; 1650 } else if (i < kNumRegularSizeBrackets) { 1651 numOfPages[i] = 1; 1652 } else if (i == kNumOfSizeBrackets - 2) { 1653 numOfPages[i] = 2; 1654 } else { 1655 DCHECK_EQ(i, kNumOfSizeBrackets - 1); 1656 numOfPages[i] = 4; 1657 } 1658 if (kTraceRosAlloc) { 1659 LOG(INFO) << "numOfPages[" << i << "]=" << numOfPages[i]; 1660 } 1661 } 1662 // Compute numOfSlots and slotOffsets. 1663 for (size_t i = 0; i < kNumOfSizeBrackets; i++) { 1664 size_t bracket_size = bracketSizes[i]; 1665 size_t run_size = kPageSize * numOfPages[i]; 1666 size_t max_num_of_slots = run_size / bracket_size; 1667 // Compute the actual number of slots by taking the header and 1668 // alignment into account. 1669 size_t fixed_header_size = RoundUp(Run::fixed_header_size(), sizeof(uint64_t)); 1670 DCHECK_EQ(fixed_header_size, 80U); 1671 size_t header_size = 0; 1672 size_t num_of_slots = 0; 1673 // Search for the maximum number of slots that allows enough space 1674 // for the header. 1675 for (int s = max_num_of_slots; s >= 0; s--) { 1676 size_t tmp_slots_size = bracket_size * s; 1677 size_t tmp_unaligned_header_size = fixed_header_size; 1678 // Align up the unaligned header size. bracket_size may not be a power of two. 1679 size_t tmp_header_size = (tmp_unaligned_header_size % bracket_size == 0) ? 1680 tmp_unaligned_header_size : 1681 tmp_unaligned_header_size + (bracket_size - tmp_unaligned_header_size % bracket_size); 1682 DCHECK_EQ(tmp_header_size % bracket_size, 0U); 1683 DCHECK_EQ(tmp_header_size % sizeof(uint64_t), 0U); 1684 if (tmp_slots_size + tmp_header_size <= run_size) { 1685 // Found the right number of slots, that is, there was enough 1686 // space for the header (including the bit maps.) 1687 num_of_slots = s; 1688 header_size = tmp_header_size; 1689 break; 1690 } 1691 } 1692 DCHECK_GT(num_of_slots, 0U) << i; 1693 DCHECK_GT(header_size, 0U) << i; 1694 // Add the padding for the alignment remainder. 1695 header_size += run_size % bracket_size; 1696 DCHECK_EQ(header_size + num_of_slots * bracket_size, run_size); 1697 numOfSlots[i] = num_of_slots; 1698 headerSizes[i] = header_size; 1699 if (kTraceRosAlloc) { 1700 LOG(INFO) << "numOfSlots[" << i << "]=" << numOfSlots[i] 1701 << ", headerSizes[" << i << "]=" << headerSizes[i]; 1702 } 1703 } 1704 // Set up the dedicated full run so that nobody can successfully allocate from it. 1705 if (kIsDebugBuild) { 1706 dedicated_full_run_->magic_num_ = kMagicNum; 1707 } 1708 // It doesn't matter which size bracket we use since the main goal is to have the allocation 1709 // fail 100% of the time you attempt to allocate into the dedicated full run. 1710 dedicated_full_run_->size_bracket_idx_ = 0; 1711 DCHECK_EQ(dedicated_full_run_->FreeList()->Size(), 0U); // It looks full. 1712 dedicated_full_run_->SetIsThreadLocal(true); 1713 1714 // The smallest bracket size must be at least as large as the sizeof(Slot). 1715 DCHECK_LE(sizeof(Slot), bracketSizes[0]) << "sizeof(Slot) <= the smallest bracket size"; 1716 // Check the invariants between the max bracket sizes and the number of brackets. 1717 DCHECK_EQ(kMaxThreadLocalBracketSize, bracketSizes[kNumThreadLocalSizeBrackets - 1]); 1718 DCHECK_EQ(kMaxRegularBracketSize, bracketSizes[kNumRegularSizeBrackets - 1]); 1719 } 1720 1721 void RosAlloc::BytesAllocatedCallback(void* start ATTRIBUTE_UNUSED, void* end ATTRIBUTE_UNUSED, 1722 size_t used_bytes, void* arg) { 1723 if (used_bytes == 0) { 1724 return; 1725 } 1726 size_t* bytes_allocated = reinterpret_cast<size_t*>(arg); 1727 *bytes_allocated += used_bytes; 1728 } 1729 1730 void RosAlloc::ObjectsAllocatedCallback(void* start ATTRIBUTE_UNUSED, void* end ATTRIBUTE_UNUSED, 1731 size_t used_bytes, 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 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 * kPageSize); 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(fpr_size, kPageSize) 1766 << "A free page run size isn't page-aligned : " << fpr_size; 1767 size_t num_pages = fpr_size / kPageSize; 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 * kPageSize; 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, RoundUp(obj_size + memory_tool_modifier, kPageSize) / kPageSize) 1799 << "A rosalloc large object size " << obj_size + memory_tool_modifier 1800 << " does not match the page map table " << (num_pages * kPageSize) 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 break; 1810 case kPageMapRun: { 1811 // The start of a run. 1812 Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize); 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 // Fall-through. 1835 default: 1836 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm) << std::endl << DumpPageMap(); 1837 break; 1838 } 1839 } 1840 } 1841 std::list<Thread*> threads = Runtime::Current()->GetThreadList()->GetList(); 1842 for (Thread* thread : threads) { 1843 for (size_t i = 0; i < kNumThreadLocalSizeBrackets; ++i) { 1844 MutexLock brackets_mu(self, *size_bracket_locks_[i]); 1845 Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(i)); 1846 CHECK(thread_local_run != nullptr); 1847 CHECK(thread_local_run->IsThreadLocal()); 1848 CHECK(thread_local_run == dedicated_full_run_ || 1849 thread_local_run->size_bracket_idx_ == i); 1850 } 1851 } 1852 for (size_t i = 0; i < kNumOfSizeBrackets; i++) { 1853 MutexLock brackets_mu(self, *size_bracket_locks_[i]); 1854 Run* current_run = current_runs_[i]; 1855 CHECK(current_run != nullptr); 1856 if (current_run != dedicated_full_run_) { 1857 // The dedicated full run is currently marked as thread local. 1858 CHECK(!current_run->IsThreadLocal()); 1859 CHECK_EQ(current_run->size_bracket_idx_, i); 1860 } 1861 } 1862 // Call Verify() here for the lock order. 1863 for (auto& run : runs) { 1864 run->Verify(self, this, is_running_on_memory_tool_); 1865 } 1866 } 1867 1868 void RosAlloc::Run::Verify(Thread* self, RosAlloc* rosalloc, bool running_on_memory_tool) { 1869 DCHECK_EQ(magic_num_, kMagicNum) << "Bad magic number : " << Dump(); 1870 const size_t idx = size_bracket_idx_; 1871 CHECK_LT(idx, kNumOfSizeBrackets) << "Out of range size bracket index : " << Dump(); 1872 uint8_t* slot_base = reinterpret_cast<uint8_t*>(this) + headerSizes[idx]; 1873 const size_t num_slots = numOfSlots[idx]; 1874 size_t bracket_size = IndexToBracketSize(idx); 1875 CHECK_EQ(slot_base + num_slots * bracket_size, 1876 reinterpret_cast<uint8_t*>(this) + numOfPages[idx] * kPageSize) 1877 << "Mismatch in the end address of the run " << Dump(); 1878 // Check that the bulk free list is empty. It's only used during BulkFree(). 1879 CHECK(IsBulkFreeListEmpty()) << "The bulk free isn't empty " << Dump(); 1880 // Check the thread local runs, the current runs, and the run sets. 1881 if (IsThreadLocal()) { 1882 // If it's a thread local run, then it must be pointed to by an owner thread. 1883 bool owner_found = false; 1884 std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList(); 1885 for (auto it = thread_list.begin(); it != thread_list.end(); ++it) { 1886 Thread* thread = *it; 1887 for (size_t i = 0; i < kNumThreadLocalSizeBrackets; i++) { 1888 MutexLock mu(self, *rosalloc->size_bracket_locks_[i]); 1889 Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(i)); 1890 if (thread_local_run == this) { 1891 CHECK(!owner_found) 1892 << "A thread local run has more than one owner thread " << Dump(); 1893 CHECK_EQ(i, idx) 1894 << "A mismatching size bracket index in a thread local run " << Dump(); 1895 owner_found = true; 1896 } 1897 } 1898 } 1899 CHECK(owner_found) << "A thread local run has no owner thread " << Dump(); 1900 } else { 1901 // If it's not thread local, check that the thread local free list is empty. 1902 CHECK(IsThreadLocalFreeListEmpty()) 1903 << "A non-thread-local run's thread local free list isn't empty " 1904 << Dump(); 1905 // Check if it's a current run for the size bracket. 1906 bool is_current_run = false; 1907 for (size_t i = 0; i < kNumOfSizeBrackets; i++) { 1908 MutexLock mu(self, *rosalloc->size_bracket_locks_[i]); 1909 Run* current_run = rosalloc->current_runs_[i]; 1910 if (idx == i) { 1911 if (this == current_run) { 1912 is_current_run = true; 1913 } 1914 } else { 1915 // If the size bucket index does not match, then it must not 1916 // be a current run. 1917 CHECK_NE(this, current_run) 1918 << "A current run points to a run with a wrong size bracket index " << Dump(); 1919 } 1920 } 1921 // If it's neither a thread local or current run, then it must be 1922 // in a run set. 1923 if (!is_current_run) { 1924 MutexLock mu(self, rosalloc->lock_); 1925 auto& non_full_runs = rosalloc->non_full_runs_[idx]; 1926 // If it's all free, it must be a free page run rather than a run. 1927 CHECK(!IsAllFree()) << "A free run must be in a free page run set " << Dump(); 1928 if (!IsFull()) { 1929 // If it's not full, it must in the non-full run set. 1930 CHECK(non_full_runs.find(this) != non_full_runs.end()) 1931 << "A non-full run isn't in the non-full run set " << Dump(); 1932 } else { 1933 // If it's full, it must in the full run set (debug build only.) 1934 if (kIsDebugBuild) { 1935 auto& full_runs = rosalloc->full_runs_[idx]; 1936 CHECK(full_runs.find(this) != full_runs.end()) 1937 << " A full run isn't in the full run set " << Dump(); 1938 } 1939 } 1940 } 1941 } 1942 // Check each slot. 1943 size_t memory_tool_modifier = running_on_memory_tool ? 1944 2 * ::art::gc::space::kDefaultMemoryToolRedZoneBytes : 1945 0U; 1946 // TODO: reuse InspectAllSlots(). 1947 std::unique_ptr<bool[]> is_free(new bool[num_slots]()); // zero initialized 1948 // Mark the free slots and the remaining ones are allocated. 1949 for (Slot* slot = free_list_.Head(); slot != nullptr; slot = slot->Next()) { 1950 size_t slot_idx = SlotIndex(slot); 1951 DCHECK_LT(slot_idx, num_slots); 1952 is_free[slot_idx] = true; 1953 } 1954 if (IsThreadLocal()) { 1955 for (Slot* slot = thread_local_free_list_.Head(); slot != nullptr; slot = slot->Next()) { 1956 size_t slot_idx = SlotIndex(slot); 1957 DCHECK_LT(slot_idx, num_slots); 1958 is_free[slot_idx] = true; 1959 } 1960 } 1961 for (size_t slot_idx = 0; slot_idx < num_slots; ++slot_idx) { 1962 uint8_t* slot_addr = slot_base + slot_idx * bracket_size; 1963 if (running_on_memory_tool) { 1964 slot_addr += ::art::gc::space::kDefaultMemoryToolRedZoneBytes; 1965 } 1966 if (!is_free[slot_idx]) { 1967 // The slot is allocated 1968 mirror::Object* obj = reinterpret_cast<mirror::Object*>(slot_addr); 1969 size_t obj_size = obj->SizeOf(); 1970 CHECK_LE(obj_size + memory_tool_modifier, kLargeSizeThreshold) 1971 << "A run slot contains a large object " << Dump(); 1972 CHECK_EQ(SizeToIndex(obj_size + memory_tool_modifier), idx) 1973 << obj->PrettyTypeOf() << " " 1974 << "obj_size=" << obj_size << "(" << obj_size + memory_tool_modifier << "), idx=" << idx 1975 << " A run slot contains an object with wrong size " << Dump(); 1976 } 1977 } 1978 } 1979 1980 size_t RosAlloc::ReleasePages() { 1981 VLOG(heap) << "RosAlloc::ReleasePages()"; 1982 DCHECK(!DoesReleaseAllPages()); 1983 Thread* self = Thread::Current(); 1984 size_t reclaimed_bytes = 0; 1985 size_t i = 0; 1986 // Check the page map size which might have changed due to grow/shrink. 1987 while (i < page_map_size_) { 1988 // Reading the page map without a lock is racy but the race is benign since it should only 1989 // result in occasionally not releasing pages which we could release. 1990 uint8_t pm = page_map_[i]; 1991 switch (pm) { 1992 case kPageMapReleased: 1993 // Fall through. 1994 case kPageMapEmpty: { 1995 // This is currently the start of a free page run. 1996 // Acquire the lock to prevent other threads racing in and modifying the page map. 1997 MutexLock mu(self, lock_); 1998 // Check that it's still empty after we acquired the lock since another thread could have 1999 // raced in and placed an allocation here. 2000 if (IsFreePage(i)) { 2001 // Free page runs can start with a released page if we coalesced a released page free 2002 // page run with an empty page run. 2003 FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize); 2004 // There is a race condition where FreePage can coalesce fpr with the previous 2005 // free page run before we acquire lock_. In that case free_page_runs_.find will not find 2006 // a run starting at fpr. To handle this race, we skip reclaiming the page range and go 2007 // to the next page. 2008 if (free_page_runs_.find(fpr) != free_page_runs_.end()) { 2009 size_t fpr_size = fpr->ByteSize(this); 2010 DCHECK_ALIGNED(fpr_size, kPageSize); 2011 uint8_t* start = reinterpret_cast<uint8_t*>(fpr); 2012 reclaimed_bytes += ReleasePageRange(start, start + fpr_size); 2013 size_t pages = fpr_size / kPageSize; 2014 CHECK_GT(pages, 0U) << "Infinite loop probable"; 2015 i += pages; 2016 DCHECK_LE(i, page_map_size_); 2017 break; 2018 } 2019 } 2020 FALLTHROUGH_INTENDED; 2021 } 2022 case kPageMapLargeObject: // Fall through. 2023 case kPageMapLargeObjectPart: // Fall through. 2024 case kPageMapRun: // Fall through. 2025 case kPageMapRunPart: // Fall through. 2026 ++i; 2027 break; // Skip. 2028 default: 2029 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm); 2030 break; 2031 } 2032 } 2033 return reclaimed_bytes; 2034 } 2035 2036 size_t RosAlloc::ReleasePageRange(uint8_t* start, uint8_t* end) { 2037 DCHECK_ALIGNED(start, kPageSize); 2038 DCHECK_ALIGNED(end, kPageSize); 2039 DCHECK_LT(start, end); 2040 if (kIsDebugBuild) { 2041 // In the debug build, the first page of a free page run 2042 // contains a magic number for debugging. Exclude it. 2043 start += kPageSize; 2044 2045 // Single pages won't be released. 2046 if (start == end) { 2047 return 0; 2048 } 2049 } 2050 if (!kMadviseZeroes) { 2051 // TODO: Do this when we resurrect the page instead. 2052 memset(start, 0, end - start); 2053 } 2054 CHECK_EQ(madvise(start, end - start, MADV_DONTNEED), 0); 2055 size_t pm_idx = ToPageMapIndex(start); 2056 size_t reclaimed_bytes = 0; 2057 // Calculate reclaimed bytes and upate page map. 2058 const size_t max_idx = pm_idx + (end - start) / kPageSize; 2059 for (; pm_idx < max_idx; ++pm_idx) { 2060 DCHECK(IsFreePage(pm_idx)); 2061 if (page_map_[pm_idx] == kPageMapEmpty) { 2062 // Mark the page as released and update how many bytes we released. 2063 reclaimed_bytes += kPageSize; 2064 page_map_[pm_idx] = kPageMapReleased; 2065 } 2066 } 2067 return reclaimed_bytes; 2068 } 2069 2070 void RosAlloc::LogFragmentationAllocFailure(std::ostream& os, size_t failed_alloc_bytes) { 2071 Thread* self = Thread::Current(); 2072 size_t largest_continuous_free_pages = 0; 2073 WriterMutexLock wmu(self, bulk_free_lock_); 2074 MutexLock mu(self, lock_); 2075 uint64_t total_free = 0; 2076 for (FreePageRun* fpr : free_page_runs_) { 2077 largest_continuous_free_pages = std::max(largest_continuous_free_pages, 2078 fpr->ByteSize(this)); 2079 total_free += fpr->ByteSize(this); 2080 } 2081 size_t required_bytes = 0; 2082 const char* new_buffer_msg = ""; 2083 if (failed_alloc_bytes > kLargeSizeThreshold) { 2084 // Large allocation. 2085 required_bytes = RoundUp(failed_alloc_bytes, kPageSize); 2086 } else { 2087 // Non-large allocation. 2088 required_bytes = numOfPages[SizeToIndex(failed_alloc_bytes)] * kPageSize; 2089 new_buffer_msg = " for a new buffer"; 2090 } 2091 if (required_bytes > largest_continuous_free_pages) { 2092 os << "; failed due to fragmentation (" 2093 << "required contiguous free " << required_bytes << " bytes" << new_buffer_msg 2094 << ", largest contiguous free " << largest_continuous_free_pages << " bytes" 2095 << ", total free pages " << total_free << " bytes" 2096 << ", space footprint " << footprint_ << " bytes" 2097 << ", space max capacity " << max_capacity_ << " bytes" 2098 << ")" << std::endl; 2099 } 2100 } 2101 2102 void RosAlloc::DumpStats(std::ostream& os) { 2103 Thread* self = Thread::Current(); 2104 CHECK(Locks::mutator_lock_->IsExclusiveHeld(self)) 2105 << "The mutator locks isn't exclusively locked at " << __PRETTY_FUNCTION__; 2106 size_t num_large_objects = 0; 2107 size_t num_pages_large_objects = 0; 2108 // These arrays are zero initialized. 2109 std::unique_ptr<size_t[]> num_runs(new size_t[kNumOfSizeBrackets]()); 2110 std::unique_ptr<size_t[]> num_pages_runs(new size_t[kNumOfSizeBrackets]()); 2111 std::unique_ptr<size_t[]> num_slots(new size_t[kNumOfSizeBrackets]()); 2112 std::unique_ptr<size_t[]> num_used_slots(new size_t[kNumOfSizeBrackets]()); 2113 std::unique_ptr<size_t[]> num_metadata_bytes(new size_t[kNumOfSizeBrackets]()); 2114 ReaderMutexLock rmu(self, bulk_free_lock_); 2115 MutexLock lock_mu(self, lock_); 2116 for (size_t i = 0; i < page_map_size_; ) { 2117 uint8_t pm = page_map_[i]; 2118 switch (pm) { 2119 case kPageMapReleased: 2120 case kPageMapEmpty: 2121 ++i; 2122 break; 2123 case kPageMapLargeObject: { 2124 size_t num_pages = 1; 2125 size_t idx = i + 1; 2126 while (idx < page_map_size_ && page_map_[idx] == kPageMapLargeObjectPart) { 2127 num_pages++; 2128 idx++; 2129 } 2130 num_large_objects++; 2131 num_pages_large_objects += num_pages; 2132 i += num_pages; 2133 break; 2134 } 2135 case kPageMapLargeObjectPart: 2136 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm) << std::endl 2137 << DumpPageMap(); 2138 break; 2139 case kPageMapRun: { 2140 Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize); 2141 size_t idx = run->size_bracket_idx_; 2142 size_t num_pages = numOfPages[idx]; 2143 num_runs[idx]++; 2144 num_pages_runs[idx] += num_pages; 2145 num_slots[idx] += numOfSlots[idx]; 2146 size_t num_free_slots = run->NumberOfFreeSlots(); 2147 num_used_slots[idx] += numOfSlots[idx] - num_free_slots; 2148 num_metadata_bytes[idx] += headerSizes[idx]; 2149 i += num_pages; 2150 break; 2151 } 2152 case kPageMapRunPart: 2153 // Fall-through. 2154 default: 2155 LOG(FATAL) << "Unreachable - page map type: " << static_cast<int>(pm) << std::endl 2156 << DumpPageMap(); 2157 break; 2158 } 2159 } 2160 os << "RosAlloc stats:\n"; 2161 for (size_t i = 0; i < kNumOfSizeBrackets; ++i) { 2162 os << "Bracket " << i << " (" << bracketSizes[i] << "):" 2163 << " #runs=" << num_runs[i] 2164 << " #pages=" << num_pages_runs[i] 2165 << " (" << PrettySize(num_pages_runs[i] * kPageSize) << ")" 2166 << " #metadata_bytes=" << PrettySize(num_metadata_bytes[i]) 2167 << " #slots=" << num_slots[i] << " (" << PrettySize(num_slots[i] * bracketSizes[i]) << ")" 2168 << " #used_slots=" << num_used_slots[i] 2169 << " (" << PrettySize(num_used_slots[i] * bracketSizes[i]) << ")\n"; 2170 } 2171 os << "Large #allocations=" << num_large_objects 2172 << " #pages=" << num_pages_large_objects 2173 << " (" << PrettySize(num_pages_large_objects * kPageSize) << ")\n"; 2174 size_t total_num_pages = 0; 2175 size_t total_metadata_bytes = 0; 2176 size_t total_allocated_bytes = 0; 2177 for (size_t i = 0; i < kNumOfSizeBrackets; ++i) { 2178 total_num_pages += num_pages_runs[i]; 2179 total_metadata_bytes += num_metadata_bytes[i]; 2180 total_allocated_bytes += num_used_slots[i] * bracketSizes[i]; 2181 } 2182 total_num_pages += num_pages_large_objects; 2183 total_allocated_bytes += num_pages_large_objects * kPageSize; 2184 os << "Total #total_bytes=" << PrettySize(total_num_pages * kPageSize) 2185 << " #metadata_bytes=" << PrettySize(total_metadata_bytes) 2186 << " #used_bytes=" << PrettySize(total_allocated_bytes) << "\n"; 2187 os << "\n"; 2188 } 2189 2190 } // namespace allocator 2191 } // namespace gc 2192 } // namespace art 2193