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