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