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