rosalloc.cc revision 73d1e17b3afc7d5e56184f90bf819dc64956448a
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 memset(current_runs_, 0, sizeof(current_runs_)); 71 for (size_t i = 0; i < kNumOfSizeBrackets; i++) { 72 size_bracket_lock_names[i] = 73 StringPrintf("an rosalloc size bracket %d lock", static_cast<int>(i)); 74 size_bracket_locks_[i] = new Mutex(size_bracket_lock_names[i].c_str(), kRosAllocBracketLock); 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 <= kMaxThreadLocalSizeBracketIdx) { 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 587void* RosAlloc::AllocFromRun(Thread* self, size_t size, size_t* bytes_allocated) { 588 DCHECK_LE(size, kLargeSizeThreshold); 589 size_t bracket_size; 590 size_t idx = SizeToIndexAndBracketSize(size, &bracket_size); 591 DCHECK_EQ(idx, SizeToIndex(size)); 592 DCHECK_EQ(bracket_size, IndexToBracketSize(idx)); 593 DCHECK_EQ(bracket_size, bracketSizes[idx]); 594 DCHECK_LE(size, bracket_size); 595 DCHECK(size > 512 || bracket_size - size < 16); 596 597 void* slot_addr; 598 599 if (LIKELY(idx <= kMaxThreadLocalSizeBracketIdx)) { 600 // Use a thread-local run. 601 Run* thread_local_run = reinterpret_cast<Run*>(self->GetRosAllocRun(idx)); 602 // Allow invalid since this will always fail the allocation. 603 DCHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end()); 604 DCHECK(full_runs_[idx].find(thread_local_run) == full_runs_[idx].end()); 605 DCHECK(thread_local_run != nullptr); 606 DCHECK(thread_local_run->IsThreadLocal() || thread_local_run == dedicated_full_run_); 607 slot_addr = thread_local_run->AllocSlot(); 608 // The allocation must fail if the run is invalid. 609 DCHECK(thread_local_run != dedicated_full_run_ || slot_addr == nullptr) 610 << "allocated from an invalid run"; 611 if (UNLIKELY(slot_addr == nullptr)) { 612 // The run got full. Try to free slots. 613 DCHECK(thread_local_run->IsFull()); 614 MutexLock mu(self, *size_bracket_locks_[idx]); 615 bool is_all_free_after_merge; 616 // This is safe to do for the dedicated_full_run_ since the bitmaps are empty. 617 if (thread_local_run->MergeThreadLocalFreeBitMapToAllocBitMap(&is_all_free_after_merge)) { 618 DCHECK_NE(thread_local_run, dedicated_full_run_); 619 // Some slot got freed. Keep it. 620 DCHECK(!thread_local_run->IsFull()); 621 DCHECK_EQ(is_all_free_after_merge, thread_local_run->IsAllFree()); 622 if (is_all_free_after_merge) { 623 // Check that the bitmap idx is back at 0 if it's all free. 624 DCHECK_EQ(thread_local_run->first_search_vec_idx_, 0U); 625 } 626 } else { 627 // No slots got freed. Try to refill the thread-local run. 628 DCHECK(thread_local_run->IsFull()); 629 if (thread_local_run != dedicated_full_run_) { 630 self->SetRosAllocRun(idx, dedicated_full_run_); 631 thread_local_run->SetIsThreadLocal(false); 632 if (kIsDebugBuild) { 633 full_runs_[idx].insert(thread_local_run); 634 if (kTraceRosAlloc) { 635 LOG(INFO) << "RosAlloc::AllocFromRun() : Inserted run 0x" << std::hex 636 << reinterpret_cast<intptr_t>(thread_local_run) 637 << " into full_runs_[" << std::dec << idx << "]"; 638 } 639 } 640 DCHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end()); 641 DCHECK(full_runs_[idx].find(thread_local_run) != full_runs_[idx].end()); 642 } 643 644 thread_local_run = RefillRun(self, idx); 645 if (UNLIKELY(thread_local_run == NULL)) { 646 return NULL; 647 } 648 DCHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end()); 649 DCHECK(full_runs_[idx].find(thread_local_run) == full_runs_[idx].end()); 650 thread_local_run->SetIsThreadLocal(true); 651 self->SetRosAllocRun(idx, thread_local_run); 652 DCHECK(!thread_local_run->IsFull()); 653 } 654 655 DCHECK(thread_local_run != NULL); 656 DCHECK(!thread_local_run->IsFull()); 657 DCHECK(thread_local_run->IsThreadLocal()); 658 slot_addr = thread_local_run->AllocSlot(); 659 // Must succeed now with a new run. 660 DCHECK(slot_addr != NULL); 661 } 662 if (kTraceRosAlloc) { 663 LOG(INFO) << "RosAlloc::AllocFromRun() thread-local : 0x" << std::hex << reinterpret_cast<intptr_t>(slot_addr) 664 << "-0x" << (reinterpret_cast<intptr_t>(slot_addr) + bracket_size) 665 << "(" << std::dec << (bracket_size) << ")"; 666 } 667 } else { 668 // Use the (shared) current run. 669 MutexLock mu(self, *size_bracket_locks_[idx]); 670 Run* current_run = current_runs_[idx]; 671 if (UNLIKELY(current_run == NULL)) { 672 current_run = RefillRun(self, idx); 673 if (UNLIKELY(current_run == NULL)) { 674 return NULL; 675 } 676 DCHECK(non_full_runs_[idx].find(current_run) == non_full_runs_[idx].end()); 677 DCHECK(full_runs_[idx].find(current_run) == full_runs_[idx].end()); 678 current_run->SetIsThreadLocal(false); 679 current_runs_[idx] = current_run; 680 DCHECK(!current_run->IsFull()); 681 } 682 DCHECK(current_run != NULL); 683 slot_addr = current_run->AllocSlot(); 684 if (UNLIKELY(slot_addr == NULL)) { 685 // The current run got full. Try to refill it. 686 DCHECK(current_run->IsFull()); 687 current_runs_[idx] = NULL; 688 if (kIsDebugBuild) { 689 // Insert it into full_runs and set the current run to NULL. 690 full_runs_[idx].insert(current_run); 691 if (kTraceRosAlloc) { 692 LOG(INFO) << "RosAlloc::AllocFromRun() : Inserted run 0x" << std::hex << reinterpret_cast<intptr_t>(current_run) 693 << " into full_runs_[" << std::dec << idx << "]"; 694 } 695 } 696 DCHECK(non_full_runs_[idx].find(current_run) == non_full_runs_[idx].end()); 697 DCHECK(full_runs_[idx].find(current_run) != full_runs_[idx].end()); 698 current_run = RefillRun(self, idx); 699 if (UNLIKELY(current_run == NULL)) { 700 return NULL; 701 } 702 DCHECK(current_run != NULL); 703 DCHECK(non_full_runs_[idx].find(current_run) == non_full_runs_[idx].end()); 704 DCHECK(full_runs_[idx].find(current_run) == full_runs_[idx].end()); 705 current_run->SetIsThreadLocal(false); 706 current_runs_[idx] = current_run; 707 DCHECK(!current_run->IsFull()); 708 slot_addr = current_run->AllocSlot(); 709 // Must succeed now with a new run. 710 DCHECK(slot_addr != NULL); 711 } 712 if (kTraceRosAlloc) { 713 LOG(INFO) << "RosAlloc::AllocFromRun() : 0x" << std::hex << reinterpret_cast<intptr_t>(slot_addr) 714 << "-0x" << (reinterpret_cast<intptr_t>(slot_addr) + bracket_size) 715 << "(" << std::dec << (bracket_size) << ")"; 716 } 717 } 718 DCHECK(bytes_allocated != nullptr); 719 *bytes_allocated = bracket_size; 720 // Caller verifies that it is all 0. 721 return slot_addr; 722} 723 724size_t RosAlloc::FreeFromRun(Thread* self, void* ptr, Run* run) { 725 DCHECK_EQ(run->magic_num_, kMagicNum); 726 DCHECK_LT(run, ptr); 727 DCHECK_LT(ptr, run->End()); 728 const size_t idx = run->size_bracket_idx_; 729 const size_t bracket_size = bracketSizes[idx]; 730 bool run_was_full = false; 731 MutexLock mu(self, *size_bracket_locks_[idx]); 732 if (kIsDebugBuild) { 733 run_was_full = run->IsFull(); 734 } 735 if (kTraceRosAlloc) { 736 LOG(INFO) << "RosAlloc::FreeFromRun() : 0x" << std::hex << reinterpret_cast<intptr_t>(ptr); 737 } 738 if (LIKELY(run->IsThreadLocal())) { 739 // It's a thread-local run. Just mark the thread-local free bit map and return. 740 DCHECK_LE(run->size_bracket_idx_, kMaxThreadLocalSizeBracketIdx); 741 DCHECK(non_full_runs_[idx].find(run) == non_full_runs_[idx].end()); 742 DCHECK(full_runs_[idx].find(run) == full_runs_[idx].end()); 743 run->MarkThreadLocalFreeBitMap(ptr); 744 if (kTraceRosAlloc) { 745 LOG(INFO) << "RosAlloc::FreeFromRun() : Freed a slot in a thread local run 0x" << std::hex 746 << reinterpret_cast<intptr_t>(run); 747 } 748 // A thread local run will be kept as a thread local even if it's become all free. 749 return bracket_size; 750 } 751 // Free the slot in the run. 752 run->FreeSlot(ptr); 753 std::set<Run*>* non_full_runs = &non_full_runs_[idx]; 754 if (run->IsAllFree()) { 755 // It has just become completely free. Free the pages of this run. 756 std::set<Run*>::iterator pos = non_full_runs->find(run); 757 if (pos != non_full_runs->end()) { 758 non_full_runs->erase(pos); 759 if (kTraceRosAlloc) { 760 LOG(INFO) << "RosAlloc::FreeFromRun() : Erased run 0x" << std::hex 761 << reinterpret_cast<intptr_t>(run) << " from non_full_runs_"; 762 } 763 } 764 if (run == current_runs_[idx]) { 765 current_runs_[idx] = NULL; 766 } 767 DCHECK(non_full_runs_[idx].find(run) == non_full_runs_[idx].end()); 768 DCHECK(full_runs_[idx].find(run) == full_runs_[idx].end()); 769 run->ZeroHeader(); 770 { 771 MutexLock mu(self, lock_); 772 FreePages(self, run, true); 773 } 774 } else { 775 // It is not completely free. If it wasn't the current run or 776 // already in the non-full run set (i.e., it was full) insert it 777 // into the non-full run set. 778 if (run != current_runs_[idx]) { 779 hash_set<Run*, hash_run, eq_run>* full_runs = 780 kIsDebugBuild ? &full_runs_[idx] : NULL; 781 std::set<Run*>::iterator pos = non_full_runs->find(run); 782 if (pos == non_full_runs->end()) { 783 DCHECK(run_was_full); 784 DCHECK(full_runs->find(run) != full_runs->end()); 785 if (kIsDebugBuild) { 786 full_runs->erase(run); 787 if (kTraceRosAlloc) { 788 LOG(INFO) << "RosAlloc::FreeFromRun() : Erased run 0x" << std::hex 789 << reinterpret_cast<intptr_t>(run) << " from full_runs_"; 790 } 791 } 792 non_full_runs->insert(run); 793 DCHECK(!run->IsFull()); 794 if (kTraceRosAlloc) { 795 LOG(INFO) << "RosAlloc::FreeFromRun() : Inserted run 0x" << std::hex 796 << reinterpret_cast<intptr_t>(run) 797 << " into non_full_runs_[" << std::dec << idx << "]"; 798 } 799 } 800 } 801 } 802 return bracket_size; 803} 804 805std::string RosAlloc::Run::BitMapToStr(uint32_t* bit_map_base, size_t num_vec) { 806 std::string bit_map_str; 807 for (size_t v = 0; v < num_vec; v++) { 808 uint32_t vec = bit_map_base[v]; 809 if (v != num_vec - 1) { 810 bit_map_str.append(StringPrintf("%x-", vec)); 811 } else { 812 bit_map_str.append(StringPrintf("%x", vec)); 813 } 814 } 815 return bit_map_str.c_str(); 816} 817 818std::string RosAlloc::Run::Dump() { 819 size_t idx = size_bracket_idx_; 820 size_t num_slots = numOfSlots[idx]; 821 size_t num_vec = RoundUp(num_slots, 32) / 32; 822 std::ostringstream stream; 823 stream << "RosAlloc Run = " << reinterpret_cast<void*>(this) 824 << "{ magic_num=" << static_cast<int>(magic_num_) 825 << " size_bracket_idx=" << idx 826 << " is_thread_local=" << static_cast<int>(is_thread_local_) 827 << " to_be_bulk_freed=" << static_cast<int>(to_be_bulk_freed_) 828 << " first_search_vec_idx=" << first_search_vec_idx_ 829 << " alloc_bit_map=" << BitMapToStr(alloc_bit_map_, num_vec) 830 << " bulk_free_bit_map=" << BitMapToStr(BulkFreeBitMap(), num_vec) 831 << " thread_local_bit_map=" << BitMapToStr(ThreadLocalFreeBitMap(), num_vec) 832 << " }" << std::endl; 833 return stream.str(); 834} 835 836inline void* RosAlloc::Run::AllocSlot() { 837 const size_t idx = size_bracket_idx_; 838 while (true) { 839 if (kIsDebugBuild) { 840 // Make sure that no slots leaked, the bitmap should be full for all previous vectors. 841 for (size_t i = 0; i < first_search_vec_idx_; ++i) { 842 CHECK_EQ(~alloc_bit_map_[i], 0U); 843 } 844 } 845 uint32_t* const alloc_bitmap_ptr = &alloc_bit_map_[first_search_vec_idx_]; 846 uint32_t ffz1 = __builtin_ffs(~*alloc_bitmap_ptr); 847 if (LIKELY(ffz1 != 0)) { 848 const uint32_t ffz = ffz1 - 1; 849 const uint32_t slot_idx = ffz + first_search_vec_idx_ * sizeof(*alloc_bitmap_ptr) * kBitsPerByte; 850 const uint32_t mask = 1U << ffz; 851 DCHECK_LT(slot_idx, numOfSlots[idx]) << "out of range"; 852 // Found an empty slot. Set the bit. 853 DCHECK_EQ(*alloc_bitmap_ptr & mask, 0U); 854 *alloc_bitmap_ptr |= mask; 855 DCHECK_NE(*alloc_bitmap_ptr & mask, 0U); 856 byte* slot_addr = reinterpret_cast<byte*>(this) + headerSizes[idx] + slot_idx * bracketSizes[idx]; 857 if (kTraceRosAlloc) { 858 LOG(INFO) << "RosAlloc::Run::AllocSlot() : 0x" << std::hex << reinterpret_cast<intptr_t>(slot_addr) 859 << ", bracket_size=" << std::dec << bracketSizes[idx] << ", slot_idx=" << slot_idx; 860 } 861 return slot_addr; 862 } 863 const size_t num_words = RoundUp(numOfSlots[idx], 32) / 32; 864 if (first_search_vec_idx_ + 1 >= num_words) { 865 DCHECK(IsFull()); 866 // Already at the last word, return null. 867 return nullptr; 868 } 869 // Increase the index to the next word and try again. 870 ++first_search_vec_idx_; 871 } 872} 873 874void RosAlloc::Run::FreeSlot(void* ptr) { 875 DCHECK(!IsThreadLocal()); 876 const byte idx = size_bracket_idx_; 877 const size_t bracket_size = bracketSizes[idx]; 878 const size_t offset_from_slot_base = reinterpret_cast<byte*>(ptr) 879 - (reinterpret_cast<byte*>(this) + headerSizes[idx]); 880 DCHECK_EQ(offset_from_slot_base % bracket_size, static_cast<size_t>(0)); 881 size_t slot_idx = offset_from_slot_base / bracket_size; 882 DCHECK_LT(slot_idx, numOfSlots[idx]); 883 size_t vec_idx = slot_idx / 32; 884 if (kIsDebugBuild) { 885 size_t num_vec = RoundUp(numOfSlots[idx], 32) / 32; 886 DCHECK_LT(vec_idx, num_vec); 887 } 888 size_t vec_off = slot_idx % 32; 889 uint32_t* vec = &alloc_bit_map_[vec_idx]; 890 first_search_vec_idx_ = std::min(first_search_vec_idx_, static_cast<uint32_t>(vec_idx)); 891 const uint32_t mask = 1U << vec_off; 892 DCHECK_NE(*vec & mask, 0U); 893 *vec &= ~mask; 894 DCHECK_EQ(*vec & mask, 0U); 895 // Zero out the memory. 896 // TODO: Investigate alternate memset since ptr is guaranteed to be aligned to 16. 897 memset(ptr, 0, bracket_size); 898 if (kTraceRosAlloc) { 899 LOG(INFO) << "RosAlloc::Run::FreeSlot() : 0x" << std::hex << reinterpret_cast<intptr_t>(ptr) 900 << ", bracket_size=" << std::dec << bracketSizes[idx] << ", slot_idx=" << slot_idx; 901 } 902} 903 904inline bool RosAlloc::Run::MergeThreadLocalFreeBitMapToAllocBitMap(bool* is_all_free_after_out) { 905 DCHECK(IsThreadLocal()); 906 // Free slots in the alloc bit map based on the thread local free bit map. 907 const size_t idx = size_bracket_idx_; 908 const size_t num_of_slots = numOfSlots[idx]; 909 const size_t num_vec = RoundUp(num_of_slots, 32) / 32; 910 bool changed = false; 911 uint32_t* vecp = &alloc_bit_map_[0]; 912 uint32_t* tl_free_vecp = &ThreadLocalFreeBitMap()[0]; 913 bool is_all_free_after = true; 914 for (size_t v = 0; v < num_vec; v++, vecp++, tl_free_vecp++) { 915 uint32_t tl_free_vec = *tl_free_vecp; 916 uint32_t vec_before = *vecp; 917 uint32_t vec_after; 918 if (tl_free_vec != 0) { 919 first_search_vec_idx_ = std::min(first_search_vec_idx_, static_cast<uint32_t>(v)); 920 vec_after = vec_before & ~tl_free_vec; 921 *vecp = vec_after; 922 changed = true; 923 *tl_free_vecp = 0; // clear the thread local free bit map. 924 } else { 925 vec_after = vec_before; 926 } 927 if (vec_after != 0) { 928 if (v == num_vec - 1) { 929 // Only not all free if a bit other than the mask bits are set. 930 is_all_free_after = 931 is_all_free_after && GetBitmapLastVectorMask(num_of_slots, num_vec) == vec_after; 932 } else { 933 is_all_free_after = false; 934 } 935 } 936 DCHECK_EQ(*tl_free_vecp, static_cast<uint32_t>(0)); 937 } 938 *is_all_free_after_out = is_all_free_after; 939 // Return true if there was at least a bit set in the thread-local 940 // free bit map and at least a bit in the alloc bit map changed. 941 return changed; 942} 943 944inline void RosAlloc::Run::MergeBulkFreeBitMapIntoAllocBitMap() { 945 DCHECK(!IsThreadLocal()); 946 // Free slots in the alloc bit map based on the bulk free bit map. 947 const size_t num_vec = NumberOfBitmapVectors(); 948 uint32_t* vecp = &alloc_bit_map_[0]; 949 uint32_t* free_vecp = &BulkFreeBitMap()[0]; 950 for (size_t v = 0; v < num_vec; v++, vecp++, free_vecp++) { 951 uint32_t free_vec = *free_vecp; 952 if (free_vec != 0) { 953 first_search_vec_idx_ = std::min(first_search_vec_idx_, static_cast<uint32_t>(v)); 954 *vecp &= ~free_vec; 955 *free_vecp = 0; // clear the bulk free bit map. 956 } 957 DCHECK_EQ(*free_vecp, static_cast<uint32_t>(0)); 958 } 959} 960 961inline void RosAlloc::Run::UnionBulkFreeBitMapToThreadLocalFreeBitMap() { 962 DCHECK(IsThreadLocal()); 963 // Union the thread local bit map with the bulk free bit map. 964 size_t num_vec = NumberOfBitmapVectors(); 965 uint32_t* to_vecp = &ThreadLocalFreeBitMap()[0]; 966 uint32_t* from_vecp = &BulkFreeBitMap()[0]; 967 for (size_t v = 0; v < num_vec; v++, to_vecp++, from_vecp++) { 968 uint32_t from_vec = *from_vecp; 969 if (from_vec != 0) { 970 *to_vecp |= from_vec; 971 *from_vecp = 0; // clear the bulk free bit map. 972 } 973 DCHECK_EQ(*from_vecp, static_cast<uint32_t>(0)); 974 } 975} 976 977inline void RosAlloc::Run::MarkThreadLocalFreeBitMap(void* ptr) { 978 DCHECK(IsThreadLocal()); 979 MarkFreeBitMapShared(ptr, ThreadLocalFreeBitMap(), "MarkThreadLocalFreeBitMap"); 980} 981 982inline size_t RosAlloc::Run::MarkBulkFreeBitMap(void* ptr) { 983 return MarkFreeBitMapShared(ptr, BulkFreeBitMap(), "MarkFreeBitMap"); 984} 985 986inline size_t RosAlloc::Run::MarkFreeBitMapShared(void* ptr, uint32_t* free_bit_map_base, 987 const char* caller_name) { 988 const byte idx = size_bracket_idx_; 989 const size_t offset_from_slot_base = reinterpret_cast<byte*>(ptr) 990 - (reinterpret_cast<byte*>(this) + headerSizes[idx]); 991 const size_t bracket_size = bracketSizes[idx]; 992 memset(ptr, 0, bracket_size); 993 DCHECK_EQ(offset_from_slot_base % bracket_size, static_cast<size_t>(0)); 994 size_t slot_idx = offset_from_slot_base / bracket_size; 995 DCHECK_LT(slot_idx, numOfSlots[idx]); 996 size_t vec_idx = slot_idx / 32; 997 if (kIsDebugBuild) { 998 size_t num_vec = NumberOfBitmapVectors(); 999 DCHECK_LT(vec_idx, num_vec); 1000 } 1001 size_t vec_off = slot_idx % 32; 1002 uint32_t* vec = &free_bit_map_base[vec_idx]; 1003 const uint32_t mask = 1U << vec_off; 1004 DCHECK_EQ(*vec & mask, 0U); 1005 *vec |= mask; 1006 DCHECK_NE(*vec & mask, 0U); 1007 if (kTraceRosAlloc) { 1008 LOG(INFO) << "RosAlloc::Run::" << caller_name << "() : 0x" << std::hex 1009 << reinterpret_cast<intptr_t>(ptr) 1010 << ", bracket_size=" << std::dec << bracketSizes[idx] << ", slot_idx=" << slot_idx; 1011 } 1012 return bracket_size; 1013} 1014 1015inline uint32_t RosAlloc::Run::GetBitmapLastVectorMask(size_t num_slots, size_t num_vec) { 1016 const size_t kBitsPerVec = 32; 1017 DCHECK_GE(num_slots * kBitsPerVec, num_vec); 1018 size_t remain = num_vec * kBitsPerVec - num_slots; 1019 DCHECK_NE(remain, kBitsPerVec); 1020 return ((1U << remain) - 1) << (kBitsPerVec - remain); 1021} 1022 1023inline bool RosAlloc::Run::IsAllFree() { 1024 const byte idx = size_bracket_idx_; 1025 const size_t num_slots = numOfSlots[idx]; 1026 const size_t num_vec = NumberOfBitmapVectors(); 1027 DCHECK_NE(num_vec, 0U); 1028 // Check the last vector after the loop since it uses a special case for the masked bits. 1029 for (size_t v = 0; v < num_vec - 1; v++) { 1030 uint32_t vec = alloc_bit_map_[v]; 1031 if (vec != 0) { 1032 return false; 1033 } 1034 } 1035 // Make sure the last word is equal to the mask, all other bits must be 0. 1036 return alloc_bit_map_[num_vec - 1] == GetBitmapLastVectorMask(num_slots, num_vec); 1037} 1038 1039inline bool RosAlloc::Run::IsFull() { 1040 const size_t num_vec = NumberOfBitmapVectors(); 1041 for (size_t v = 0; v < num_vec; ++v) { 1042 if (~alloc_bit_map_[v] != 0) { 1043 return false; 1044 } 1045 } 1046 return true; 1047} 1048 1049inline bool RosAlloc::Run::IsBulkFreeBitmapClean() { 1050 const size_t num_vec = NumberOfBitmapVectors(); 1051 for (size_t v = 0; v < num_vec; v++) { 1052 uint32_t vec = BulkFreeBitMap()[v]; 1053 if (vec != 0) { 1054 return false; 1055 } 1056 } 1057 return true; 1058} 1059 1060inline bool RosAlloc::Run::IsThreadLocalFreeBitmapClean() { 1061 const size_t num_vec = NumberOfBitmapVectors(); 1062 for (size_t v = 0; v < num_vec; v++) { 1063 uint32_t vec = ThreadLocalFreeBitMap()[v]; 1064 if (vec != 0) { 1065 return false; 1066 } 1067 } 1068 return true; 1069} 1070 1071inline void RosAlloc::Run::SetAllocBitMapBitsForInvalidSlots() { 1072 const size_t idx = size_bracket_idx_; 1073 const size_t num_slots = numOfSlots[idx]; 1074 const size_t num_vec = RoundUp(num_slots, 32) / 32; 1075 DCHECK_NE(num_vec, 0U); 1076 // Make sure to set the bits at the end of the bitmap so that we don't allocate there since they 1077 // don't represent valid slots. 1078 alloc_bit_map_[num_vec - 1] |= GetBitmapLastVectorMask(num_slots, num_vec); 1079} 1080 1081inline void RosAlloc::Run::ZeroHeader() { 1082 const byte idx = size_bracket_idx_; 1083 memset(this, 0, headerSizes[idx]); 1084} 1085 1086inline void RosAlloc::Run::ZeroData() { 1087 const byte idx = size_bracket_idx_; 1088 byte* slot_begin = reinterpret_cast<byte*>(this) + headerSizes[idx]; 1089 memset(slot_begin, 0, numOfSlots[idx] * bracketSizes[idx]); 1090} 1091 1092inline void RosAlloc::Run::FillAllocBitMap() { 1093 size_t num_vec = NumberOfBitmapVectors(); 1094 memset(alloc_bit_map_, 0xFF, sizeof(uint32_t) * num_vec); 1095 first_search_vec_idx_ = num_vec - 1; // No free bits in any of the bitmap words. 1096} 1097 1098void RosAlloc::Run::InspectAllSlots(void (*handler)(void* start, void* end, size_t used_bytes, void* callback_arg), 1099 void* arg) { 1100 size_t idx = size_bracket_idx_; 1101 byte* slot_base = reinterpret_cast<byte*>(this) + headerSizes[idx]; 1102 size_t num_slots = numOfSlots[idx]; 1103 size_t bracket_size = IndexToBracketSize(idx); 1104 DCHECK_EQ(slot_base + num_slots * bracket_size, reinterpret_cast<byte*>(this) + numOfPages[idx] * kPageSize); 1105 size_t num_vec = RoundUp(num_slots, 32) / 32; 1106 size_t slots = 0; 1107 for (size_t v = 0; v < num_vec; v++, slots += 32) { 1108 DCHECK_GE(num_slots, slots); 1109 uint32_t vec = alloc_bit_map_[v]; 1110 size_t end = std::min(num_slots - slots, static_cast<size_t>(32)); 1111 for (size_t i = 0; i < end; ++i) { 1112 bool is_allocated = ((vec >> i) & 0x1) != 0; 1113 byte* slot_addr = slot_base + (slots + i) * bracket_size; 1114 if (is_allocated) { 1115 handler(slot_addr, slot_addr + bracket_size, bracket_size, arg); 1116 } else { 1117 handler(slot_addr, slot_addr + bracket_size, 0, arg); 1118 } 1119 } 1120 } 1121} 1122 1123// If true, read the page map entries in BulkFree() without using the 1124// lock for better performance, assuming that the existence of an 1125// allocated chunk/pointer being freed in BulkFree() guarantees that 1126// the page map entry won't change. Disabled for now. 1127static constexpr bool kReadPageMapEntryWithoutLockInBulkFree = true; 1128 1129size_t RosAlloc::BulkFree(Thread* self, void** ptrs, size_t num_ptrs) { 1130 size_t freed_bytes = 0; 1131 if (false) { 1132 // Used only to test Free() as GC uses only BulkFree(). 1133 for (size_t i = 0; i < num_ptrs; ++i) { 1134 freed_bytes += FreeInternal(self, ptrs[i]); 1135 } 1136 return freed_bytes; 1137 } 1138 1139 WriterMutexLock wmu(self, bulk_free_lock_); 1140 1141 // First mark slots to free in the bulk free bit map without locking the 1142 // size bracket locks. On host, hash_set is faster than vector + flag. 1143#ifdef HAVE_ANDROID_OS 1144 std::vector<Run*> runs; 1145#else 1146 hash_set<Run*, hash_run, eq_run> runs; 1147#endif 1148 for (size_t i = 0; i < num_ptrs; i++) { 1149 void* ptr = ptrs[i]; 1150 DCHECK_LE(base_, ptr); 1151 DCHECK_LT(ptr, base_ + footprint_); 1152 size_t pm_idx = RoundDownToPageMapIndex(ptr); 1153 Run* run = nullptr; 1154 if (kReadPageMapEntryWithoutLockInBulkFree) { 1155 // Read the page map entries without locking the lock. 1156 byte page_map_entry = page_map_[pm_idx]; 1157 if (kTraceRosAlloc) { 1158 LOG(INFO) << "RosAlloc::BulkFree() : " << std::hex << ptr << ", pm_idx=" 1159 << std::dec << pm_idx 1160 << ", page_map_entry=" << static_cast<int>(page_map_entry); 1161 } 1162 if (LIKELY(page_map_entry == kPageMapRun)) { 1163 run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize); 1164 } else if (LIKELY(page_map_entry == kPageMapRunPart)) { 1165 size_t pi = pm_idx; 1166 // Find the beginning of the run. 1167 do { 1168 --pi; 1169 DCHECK_LT(pi, capacity_ / kPageSize); 1170 } while (page_map_[pi] != kPageMapRun); 1171 run = reinterpret_cast<Run*>(base_ + pi * kPageSize); 1172 } else if (page_map_entry == kPageMapLargeObject) { 1173 MutexLock mu(self, lock_); 1174 freed_bytes += FreePages(self, ptr, false); 1175 continue; 1176 } else { 1177 LOG(FATAL) << "Unreachable - page map type: " << page_map_entry; 1178 } 1179 } else { 1180 // Read the page map entries with a lock. 1181 MutexLock mu(self, lock_); 1182 DCHECK_LT(pm_idx, page_map_size_); 1183 byte page_map_entry = page_map_[pm_idx]; 1184 if (kTraceRosAlloc) { 1185 LOG(INFO) << "RosAlloc::BulkFree() : " << std::hex << ptr << ", pm_idx=" 1186 << std::dec << pm_idx 1187 << ", page_map_entry=" << static_cast<int>(page_map_entry); 1188 } 1189 if (LIKELY(page_map_entry == kPageMapRun)) { 1190 run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize); 1191 } else if (LIKELY(page_map_entry == kPageMapRunPart)) { 1192 size_t pi = pm_idx; 1193 // Find the beginning of the run. 1194 do { 1195 --pi; 1196 DCHECK_LT(pi, capacity_ / kPageSize); 1197 } while (page_map_[pi] != kPageMapRun); 1198 run = reinterpret_cast<Run*>(base_ + pi * kPageSize); 1199 } else if (page_map_entry == kPageMapLargeObject) { 1200 freed_bytes += FreePages(self, ptr, false); 1201 continue; 1202 } else { 1203 LOG(FATAL) << "Unreachable - page map type: " << page_map_entry; 1204 } 1205 } 1206 DCHECK(run != nullptr); 1207 DCHECK_EQ(run->magic_num_, kMagicNum); 1208 // Set the bit in the bulk free bit map. 1209 freed_bytes += run->MarkBulkFreeBitMap(ptr); 1210#ifdef HAVE_ANDROID_OS 1211 if (!run->to_be_bulk_freed_) { 1212 run->to_be_bulk_freed_ = true; 1213 runs.push_back(run); 1214 } 1215#else 1216 runs.insert(run); 1217#endif 1218 } 1219 1220 // Now, iterate over the affected runs and update the alloc bit map 1221 // based on the bulk free bit map (for non-thread-local runs) and 1222 // union the bulk free bit map into the thread-local free bit map 1223 // (for thread-local runs.) 1224 for (Run* run : runs) { 1225#ifdef HAVE_ANDROID_OS 1226 DCHECK(run->to_be_bulk_freed_); 1227 run->to_be_bulk_freed_ = false; 1228#endif 1229 size_t idx = run->size_bracket_idx_; 1230 MutexLock mu(self, *size_bracket_locks_[idx]); 1231 if (run->IsThreadLocal()) { 1232 DCHECK_LE(run->size_bracket_idx_, kMaxThreadLocalSizeBracketIdx); 1233 DCHECK(non_full_runs_[idx].find(run) == non_full_runs_[idx].end()); 1234 DCHECK(full_runs_[idx].find(run) == full_runs_[idx].end()); 1235 run->UnionBulkFreeBitMapToThreadLocalFreeBitMap(); 1236 if (kTraceRosAlloc) { 1237 LOG(INFO) << "RosAlloc::BulkFree() : Freed slot(s) in a thread local run 0x" 1238 << std::hex << reinterpret_cast<intptr_t>(run); 1239 } 1240 DCHECK(run->IsThreadLocal()); 1241 // A thread local run will be kept as a thread local even if 1242 // it's become all free. 1243 } else { 1244 bool run_was_full = run->IsFull(); 1245 run->MergeBulkFreeBitMapIntoAllocBitMap(); 1246 if (kTraceRosAlloc) { 1247 LOG(INFO) << "RosAlloc::BulkFree() : Freed slot(s) in a run 0x" << std::hex 1248 << reinterpret_cast<intptr_t>(run); 1249 } 1250 // Check if the run should be moved to non_full_runs_ or 1251 // free_page_runs_. 1252 std::set<Run*>* non_full_runs = &non_full_runs_[idx]; 1253 hash_set<Run*, hash_run, eq_run>* full_runs = 1254 kIsDebugBuild ? &full_runs_[idx] : NULL; 1255 if (run->IsAllFree()) { 1256 // It has just become completely free. Free the pages of the 1257 // run. 1258 bool run_was_current = run == current_runs_[idx]; 1259 if (run_was_current) { 1260 DCHECK(full_runs->find(run) == full_runs->end()); 1261 DCHECK(non_full_runs->find(run) == non_full_runs->end()); 1262 // If it was a current run, reuse it. 1263 } else if (run_was_full) { 1264 // If it was full, remove it from the full run set (debug 1265 // only.) 1266 if (kIsDebugBuild) { 1267 hash_set<Run*, hash_run, eq_run>::iterator pos = full_runs->find(run); 1268 DCHECK(pos != full_runs->end()); 1269 full_runs->erase(pos); 1270 if (kTraceRosAlloc) { 1271 LOG(INFO) << "RosAlloc::BulkFree() : Erased run 0x" << std::hex 1272 << reinterpret_cast<intptr_t>(run) 1273 << " from full_runs_"; 1274 } 1275 DCHECK(full_runs->find(run) == full_runs->end()); 1276 } 1277 } else { 1278 // If it was in a non full run set, remove it from the set. 1279 DCHECK(full_runs->find(run) == full_runs->end()); 1280 DCHECK(non_full_runs->find(run) != non_full_runs->end()); 1281 non_full_runs->erase(run); 1282 if (kTraceRosAlloc) { 1283 LOG(INFO) << "RosAlloc::BulkFree() : Erased run 0x" << std::hex 1284 << reinterpret_cast<intptr_t>(run) 1285 << " from non_full_runs_"; 1286 } 1287 DCHECK(non_full_runs->find(run) == non_full_runs->end()); 1288 } 1289 if (!run_was_current) { 1290 run->ZeroHeader(); 1291 MutexLock mu(self, lock_); 1292 FreePages(self, run, true); 1293 } 1294 } else { 1295 // It is not completely free. If it wasn't the current run or 1296 // already in the non-full run set (i.e., it was full) insert 1297 // it into the non-full run set. 1298 if (run == current_runs_[idx]) { 1299 DCHECK(non_full_runs->find(run) == non_full_runs->end()); 1300 DCHECK(full_runs->find(run) == full_runs->end()); 1301 // If it was a current run, keep it. 1302 } else if (run_was_full) { 1303 // If it was full, remove it from the full run set (debug 1304 // only) and insert into the non-full run set. 1305 DCHECK(full_runs->find(run) != full_runs->end()); 1306 DCHECK(non_full_runs->find(run) == non_full_runs->end()); 1307 if (kIsDebugBuild) { 1308 full_runs->erase(run); 1309 if (kTraceRosAlloc) { 1310 LOG(INFO) << "RosAlloc::BulkFree() : Erased run 0x" << std::hex 1311 << reinterpret_cast<intptr_t>(run) 1312 << " from full_runs_"; 1313 } 1314 } 1315 non_full_runs->insert(run); 1316 if (kTraceRosAlloc) { 1317 LOG(INFO) << "RosAlloc::BulkFree() : Inserted run 0x" << std::hex 1318 << reinterpret_cast<intptr_t>(run) 1319 << " into non_full_runs_[" << std::dec << idx; 1320 } 1321 } else { 1322 // If it was not full, so leave it in the non full run set. 1323 DCHECK(full_runs->find(run) == full_runs->end()); 1324 DCHECK(non_full_runs->find(run) != non_full_runs->end()); 1325 } 1326 } 1327 } 1328 } 1329 return freed_bytes; 1330} 1331 1332std::string RosAlloc::DumpPageMap() { 1333 std::ostringstream stream; 1334 stream << "RosAlloc PageMap: " << std::endl; 1335 lock_.AssertHeld(Thread::Current()); 1336 size_t end = page_map_size_; 1337 FreePageRun* curr_fpr = NULL; 1338 size_t curr_fpr_size = 0; 1339 size_t remaining_curr_fpr_size = 0; 1340 size_t num_running_empty_pages = 0; 1341 for (size_t i = 0; i < end; ++i) { 1342 byte pm = page_map_[i]; 1343 switch (pm) { 1344 case kPageMapEmpty: { 1345 FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize); 1346 if (free_page_runs_.find(fpr) != free_page_runs_.end()) { 1347 // Encountered a fresh free page run. 1348 DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0)); 1349 DCHECK(fpr->IsFree()); 1350 DCHECK(curr_fpr == NULL); 1351 DCHECK_EQ(curr_fpr_size, static_cast<size_t>(0)); 1352 curr_fpr = fpr; 1353 curr_fpr_size = fpr->ByteSize(this); 1354 DCHECK_EQ(curr_fpr_size % kPageSize, static_cast<size_t>(0)); 1355 remaining_curr_fpr_size = curr_fpr_size - kPageSize; 1356 stream << "[" << i << "]=Empty (FPR start)" 1357 << " fpr_size=" << curr_fpr_size 1358 << " remaining_fpr_size=" << remaining_curr_fpr_size << std::endl; 1359 if (remaining_curr_fpr_size == 0) { 1360 // Reset at the end of the current free page run. 1361 curr_fpr = NULL; 1362 curr_fpr_size = 0; 1363 } 1364 stream << "curr_fpr=0x" << std::hex << reinterpret_cast<intptr_t>(curr_fpr) << std::endl; 1365 DCHECK_EQ(num_running_empty_pages, static_cast<size_t>(0)); 1366 } else { 1367 // Still part of the current free page run. 1368 DCHECK_NE(num_running_empty_pages, static_cast<size_t>(0)); 1369 DCHECK(curr_fpr != NULL && curr_fpr_size > 0 && remaining_curr_fpr_size > 0); 1370 DCHECK_EQ(remaining_curr_fpr_size % kPageSize, static_cast<size_t>(0)); 1371 DCHECK_GE(remaining_curr_fpr_size, static_cast<size_t>(kPageSize)); 1372 remaining_curr_fpr_size -= kPageSize; 1373 stream << "[" << i << "]=Empty (FPR part)" 1374 << " remaining_fpr_size=" << remaining_curr_fpr_size << std::endl; 1375 if (remaining_curr_fpr_size == 0) { 1376 // Reset at the end of the current free page run. 1377 curr_fpr = NULL; 1378 curr_fpr_size = 0; 1379 } 1380 } 1381 num_running_empty_pages++; 1382 break; 1383 } 1384 case kPageMapLargeObject: { 1385 DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0)); 1386 num_running_empty_pages = 0; 1387 stream << "[" << i << "]=Large (start)" << std::endl; 1388 break; 1389 } 1390 case kPageMapLargeObjectPart: 1391 DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0)); 1392 num_running_empty_pages = 0; 1393 stream << "[" << i << "]=Large (part)" << std::endl; 1394 break; 1395 case kPageMapRun: { 1396 DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0)); 1397 num_running_empty_pages = 0; 1398 Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize); 1399 size_t idx = run->size_bracket_idx_; 1400 stream << "[" << i << "]=Run (start)" 1401 << " idx=" << idx 1402 << " numOfPages=" << numOfPages[idx] 1403 << " is_thread_local=" << run->is_thread_local_ 1404 << " is_all_free=" << (run->IsAllFree() ? 1 : 0) 1405 << std::endl; 1406 break; 1407 } 1408 case kPageMapRunPart: 1409 DCHECK_EQ(remaining_curr_fpr_size, static_cast<size_t>(0)); 1410 num_running_empty_pages = 0; 1411 stream << "[" << i << "]=Run (part)" << std::endl; 1412 break; 1413 default: 1414 stream << "[" << i << "]=Unrecognizable page map type: " << pm; 1415 break; 1416 } 1417 } 1418 return stream.str(); 1419} 1420 1421size_t RosAlloc::UsableSize(void* ptr) { 1422 DCHECK_LE(base_, ptr); 1423 DCHECK_LT(ptr, base_ + footprint_); 1424 size_t pm_idx = RoundDownToPageMapIndex(ptr); 1425 MutexLock mu(Thread::Current(), lock_); 1426 switch (page_map_[pm_idx]) { 1427 case kPageMapEmpty: 1428 LOG(FATAL) << "Unreachable - RosAlloc::UsableSize(): pm_idx=" << pm_idx << ", ptr=" << std::hex 1429 << reinterpret_cast<intptr_t>(ptr); 1430 break; 1431 case kPageMapLargeObject: { 1432 size_t num_pages = 1; 1433 size_t idx = pm_idx + 1; 1434 size_t end = page_map_size_; 1435 while (idx < end && page_map_[idx] == kPageMapLargeObjectPart) { 1436 num_pages++; 1437 idx++; 1438 } 1439 return num_pages * kPageSize; 1440 } 1441 case kPageMapLargeObjectPart: 1442 LOG(FATAL) << "Unreachable - RosAlloc::UsableSize(): pm_idx=" << pm_idx << ", ptr=" << std::hex 1443 << reinterpret_cast<intptr_t>(ptr); 1444 break; 1445 case kPageMapRun: 1446 case kPageMapRunPart: { 1447 // Find the beginning of the run. 1448 while (page_map_[pm_idx] != kPageMapRun) { 1449 pm_idx--; 1450 DCHECK_LT(pm_idx, capacity_ / kPageSize); 1451 } 1452 DCHECK_EQ(page_map_[pm_idx], kPageMapRun); 1453 Run* run = reinterpret_cast<Run*>(base_ + pm_idx * kPageSize); 1454 DCHECK_EQ(run->magic_num_, kMagicNum); 1455 size_t idx = run->size_bracket_idx_; 1456 size_t offset_from_slot_base = reinterpret_cast<byte*>(ptr) 1457 - (reinterpret_cast<byte*>(run) + headerSizes[idx]); 1458 DCHECK_EQ(offset_from_slot_base % bracketSizes[idx], static_cast<size_t>(0)); 1459 return IndexToBracketSize(idx); 1460 } 1461 default: 1462 LOG(FATAL) << "Unreachable - page map type: " << page_map_[pm_idx]; 1463 break; 1464 } 1465 return 0; 1466} 1467 1468bool RosAlloc::Trim() { 1469 MutexLock mu(Thread::Current(), lock_); 1470 FreePageRun* last_free_page_run; 1471 DCHECK_EQ(footprint_ % kPageSize, static_cast<size_t>(0)); 1472 auto it = free_page_runs_.rbegin(); 1473 if (it != free_page_runs_.rend() && (last_free_page_run = *it)->End(this) == base_ + footprint_) { 1474 // Remove the last free page run, if any. 1475 DCHECK(last_free_page_run->IsFree()); 1476 DCHECK_EQ(page_map_[ToPageMapIndex(last_free_page_run)], kPageMapEmpty); 1477 DCHECK_EQ(last_free_page_run->ByteSize(this) % kPageSize, static_cast<size_t>(0)); 1478 DCHECK_EQ(last_free_page_run->End(this), base_ + footprint_); 1479 free_page_runs_.erase(last_free_page_run); 1480 size_t decrement = last_free_page_run->ByteSize(this); 1481 size_t new_footprint = footprint_ - decrement; 1482 DCHECK_EQ(new_footprint % kPageSize, static_cast<size_t>(0)); 1483 size_t new_num_of_pages = new_footprint / kPageSize; 1484 DCHECK_GE(page_map_size_, new_num_of_pages); 1485 // Zero out the tail of the page map. 1486 byte* zero_begin = page_map_ + new_num_of_pages; 1487 byte* madvise_begin = AlignUp(zero_begin, kPageSize); 1488 DCHECK_LE(madvise_begin, page_map_mem_map_->End()); 1489 size_t madvise_size = page_map_mem_map_->End() - madvise_begin; 1490 if (madvise_size > 0) { 1491 DCHECK_ALIGNED(madvise_begin, kPageSize); 1492 DCHECK_EQ(RoundUp(madvise_size, kPageSize), madvise_size); 1493 CHECK_EQ(madvise(madvise_begin, madvise_size, MADV_DONTNEED), 0); 1494 } 1495 if (madvise_begin - zero_begin) { 1496 memset(zero_begin, 0, madvise_begin - zero_begin); 1497 } 1498 page_map_size_ = new_num_of_pages; 1499 free_page_run_size_map_.resize(new_num_of_pages); 1500 DCHECK_EQ(free_page_run_size_map_.size(), new_num_of_pages); 1501 art_heap_rosalloc_morecore(this, -(static_cast<intptr_t>(decrement))); 1502 if (kTraceRosAlloc) { 1503 LOG(INFO) << "RosAlloc::Trim() : decreased the footprint from " 1504 << footprint_ << " to " << new_footprint; 1505 } 1506 DCHECK_LT(new_footprint, footprint_); 1507 DCHECK_LT(new_footprint, capacity_); 1508 footprint_ = new_footprint; 1509 return true; 1510 } 1511 return false; 1512} 1513 1514void RosAlloc::InspectAll(void (*handler)(void* start, void* end, size_t used_bytes, void* callback_arg), 1515 void* arg) { 1516 // Note: no need to use this to release pages as we already do so in FreePages(). 1517 if (handler == NULL) { 1518 return; 1519 } 1520 MutexLock mu(Thread::Current(), lock_); 1521 size_t pm_end = page_map_size_; 1522 size_t i = 0; 1523 while (i < pm_end) { 1524 byte pm = page_map_[i]; 1525 switch (pm) { 1526 case kPageMapEmpty: { 1527 // The start of a free page run. 1528 FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize); 1529 DCHECK(free_page_runs_.find(fpr) != free_page_runs_.end()); 1530 size_t fpr_size = fpr->ByteSize(this); 1531 DCHECK(IsAligned<kPageSize>(fpr_size)); 1532 void* start = fpr; 1533 if (kIsDebugBuild) { 1534 // In the debug build, the first page of a free page run 1535 // contains a magic number for debugging. Exclude it. 1536 start = reinterpret_cast<byte*>(fpr) + kPageSize; 1537 } 1538 void* end = reinterpret_cast<byte*>(fpr) + fpr_size; 1539 handler(start, end, 0, arg); 1540 size_t num_pages = fpr_size / kPageSize; 1541 if (kIsDebugBuild) { 1542 for (size_t j = i + 1; j < i + num_pages; ++j) { 1543 DCHECK_EQ(page_map_[j], kPageMapEmpty); 1544 } 1545 } 1546 i += fpr_size / kPageSize; 1547 DCHECK_LE(i, pm_end); 1548 break; 1549 } 1550 case kPageMapLargeObject: { 1551 // The start of a large object. 1552 size_t num_pages = 1; 1553 size_t idx = i + 1; 1554 while (idx < pm_end && page_map_[idx] == kPageMapLargeObjectPart) { 1555 num_pages++; 1556 idx++; 1557 } 1558 void* start = base_ + i * kPageSize; 1559 void* end = base_ + (i + num_pages) * kPageSize; 1560 size_t used_bytes = num_pages * kPageSize; 1561 handler(start, end, used_bytes, arg); 1562 if (kIsDebugBuild) { 1563 for (size_t j = i + 1; j < i + num_pages; ++j) { 1564 DCHECK_EQ(page_map_[j], kPageMapLargeObjectPart); 1565 } 1566 } 1567 i += num_pages; 1568 DCHECK_LE(i, pm_end); 1569 break; 1570 } 1571 case kPageMapLargeObjectPart: 1572 LOG(FATAL) << "Unreachable - page map type: " << pm; 1573 break; 1574 case kPageMapRun: { 1575 // The start of a run. 1576 Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize); 1577 DCHECK_EQ(run->magic_num_, kMagicNum); 1578 // The dedicated full run doesn't contain any real allocations, don't visit the slots in 1579 // there. 1580 run->InspectAllSlots(handler, arg); 1581 size_t num_pages = numOfPages[run->size_bracket_idx_]; 1582 if (kIsDebugBuild) { 1583 for (size_t j = i + 1; j < i + num_pages; ++j) { 1584 DCHECK_EQ(page_map_[j], kPageMapRunPart); 1585 } 1586 } 1587 i += num_pages; 1588 DCHECK_LE(i, pm_end); 1589 break; 1590 } 1591 case kPageMapRunPart: 1592 LOG(FATAL) << "Unreachable - page map type: " << pm; 1593 break; 1594 default: 1595 LOG(FATAL) << "Unreachable - page map type: " << pm; 1596 break; 1597 } 1598 } 1599} 1600 1601size_t RosAlloc::Footprint() { 1602 MutexLock mu(Thread::Current(), lock_); 1603 return footprint_; 1604} 1605 1606size_t RosAlloc::FootprintLimit() { 1607 MutexLock mu(Thread::Current(), lock_); 1608 return capacity_; 1609} 1610 1611void RosAlloc::SetFootprintLimit(size_t new_capacity) { 1612 MutexLock mu(Thread::Current(), lock_); 1613 DCHECK_EQ(RoundUp(new_capacity, kPageSize), new_capacity); 1614 // Only growing is supported here. But Trim() is supported. 1615 if (capacity_ < new_capacity) { 1616 CHECK_LE(new_capacity, max_capacity_); 1617 capacity_ = new_capacity; 1618 VLOG(heap) << "new capacity=" << capacity_; 1619 } 1620} 1621 1622void RosAlloc::RevokeThreadLocalRuns(Thread* thread) { 1623 Thread* self = Thread::Current(); 1624 // Avoid race conditions on the bulk free bit maps with BulkFree() (GC). 1625 WriterMutexLock wmu(self, bulk_free_lock_); 1626 for (size_t idx = 0; idx < kNumOfSizeBrackets; idx++) { 1627 MutexLock mu(self, *size_bracket_locks_[idx]); 1628 Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(idx)); 1629 CHECK(thread_local_run != nullptr); 1630 // Invalid means already revoked. 1631 DCHECK(thread_local_run->IsThreadLocal()); 1632 if (thread_local_run != dedicated_full_run_) { 1633 thread->SetRosAllocRun(idx, dedicated_full_run_); 1634 DCHECK_EQ(thread_local_run->magic_num_, kMagicNum); 1635 // Note the thread local run may not be full here. 1636 bool dont_care; 1637 thread_local_run->MergeThreadLocalFreeBitMapToAllocBitMap(&dont_care); 1638 thread_local_run->SetIsThreadLocal(false); 1639 thread_local_run->MergeBulkFreeBitMapIntoAllocBitMap(); 1640 DCHECK(non_full_runs_[idx].find(thread_local_run) == non_full_runs_[idx].end()); 1641 DCHECK(full_runs_[idx].find(thread_local_run) == full_runs_[idx].end()); 1642 if (thread_local_run->IsFull()) { 1643 if (kIsDebugBuild) { 1644 full_runs_[idx].insert(thread_local_run); 1645 DCHECK(full_runs_[idx].find(thread_local_run) != full_runs_[idx].end()); 1646 if (kTraceRosAlloc) { 1647 LOG(INFO) << "RosAlloc::RevokeThreadLocalRuns() : Inserted run 0x" << std::hex 1648 << reinterpret_cast<intptr_t>(thread_local_run) 1649 << " into full_runs_[" << std::dec << idx << "]"; 1650 } 1651 } 1652 } else if (thread_local_run->IsAllFree()) { 1653 MutexLock mu(self, lock_); 1654 thread_local_run->ZeroHeader(); 1655 FreePages(self, thread_local_run, true); 1656 } else { 1657 non_full_runs_[idx].insert(thread_local_run); 1658 DCHECK(non_full_runs_[idx].find(thread_local_run) != non_full_runs_[idx].end()); 1659 if (kTraceRosAlloc) { 1660 LOG(INFO) << "RosAlloc::RevokeThreadLocalRuns() : Inserted run 0x" << std::hex 1661 << reinterpret_cast<intptr_t>(thread_local_run) 1662 << " into non_full_runs_[" << std::dec << idx << "]"; 1663 } 1664 } 1665 } 1666 } 1667} 1668 1669void RosAlloc::RevokeAllThreadLocalRuns() { 1670 // This is called when a mutator thread won't allocate such as at 1671 // the Zygote creation time or during the GC pause. 1672 MutexLock mu(Thread::Current(), *Locks::runtime_shutdown_lock_); 1673 MutexLock mu2(Thread::Current(), *Locks::thread_list_lock_); 1674 std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList(); 1675 for (Thread* thread : thread_list) { 1676 RevokeThreadLocalRuns(thread); 1677 } 1678} 1679 1680void RosAlloc::AssertThreadLocalRunsAreRevoked(Thread* thread) { 1681 if (kIsDebugBuild) { 1682 Thread* self = Thread::Current(); 1683 // Avoid race conditions on the bulk free bit maps with BulkFree() (GC). 1684 WriterMutexLock wmu(self, bulk_free_lock_); 1685 for (size_t idx = 0; idx < kNumOfSizeBrackets; idx++) { 1686 MutexLock mu(self, *size_bracket_locks_[idx]); 1687 Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(idx)); 1688 DCHECK(thread_local_run == nullptr || thread_local_run == dedicated_full_run_); 1689 } 1690 } 1691} 1692 1693void RosAlloc::AssertAllThreadLocalRunsAreRevoked() { 1694 if (kIsDebugBuild) { 1695 MutexLock mu(Thread::Current(), *Locks::runtime_shutdown_lock_); 1696 MutexLock mu2(Thread::Current(), *Locks::thread_list_lock_); 1697 std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList(); 1698 for (Thread* t : thread_list) { 1699 AssertThreadLocalRunsAreRevoked(t); 1700 } 1701 } 1702} 1703 1704void RosAlloc::Initialize() { 1705 // Check the consistency of the number of size brackets. 1706 DCHECK_EQ(Thread::kRosAllocNumOfSizeBrackets, kNumOfSizeBrackets); 1707 // bracketSizes. 1708 for (size_t i = 0; i < kNumOfSizeBrackets; i++) { 1709 if (i < kNumOfSizeBrackets - 2) { 1710 bracketSizes[i] = 16 * (i + 1); 1711 } else if (i == kNumOfSizeBrackets - 2) { 1712 bracketSizes[i] = 1 * KB; 1713 } else { 1714 DCHECK_EQ(i, kNumOfSizeBrackets - 1); 1715 bracketSizes[i] = 2 * KB; 1716 } 1717 if (kTraceRosAlloc) { 1718 LOG(INFO) << "bracketSizes[" << i << "]=" << bracketSizes[i]; 1719 } 1720 } 1721 // numOfPages. 1722 for (size_t i = 0; i < kNumOfSizeBrackets; i++) { 1723 if (i < 4) { 1724 numOfPages[i] = 1; 1725 } else if (i < 8) { 1726 numOfPages[i] = 2; 1727 } else if (i < 16) { 1728 numOfPages[i] = 4; 1729 } else if (i < 32) { 1730 numOfPages[i] = 8; 1731 } else if (i == 32) { 1732 DCHECK_EQ(i, kNumOfSizeBrackets - 2); 1733 numOfPages[i] = 16; 1734 } else { 1735 DCHECK_EQ(i, kNumOfSizeBrackets - 1); 1736 numOfPages[i] = 32; 1737 } 1738 if (kTraceRosAlloc) { 1739 LOG(INFO) << "numOfPages[" << i << "]=" << numOfPages[i]; 1740 } 1741 } 1742 // Compute numOfSlots and slotOffsets. 1743 for (size_t i = 0; i < kNumOfSizeBrackets; i++) { 1744 size_t bracket_size = bracketSizes[i]; 1745 size_t run_size = kPageSize * numOfPages[i]; 1746 size_t max_num_of_slots = run_size / bracket_size; 1747 // Compute the actual number of slots by taking the header and 1748 // alignment into account. 1749 size_t fixed_header_size = RoundUp(Run::fixed_header_size(), sizeof(uint32_t)); 1750 DCHECK_EQ(fixed_header_size, static_cast<size_t>(8)); 1751 size_t header_size = 0; 1752 size_t bulk_free_bit_map_offset = 0; 1753 size_t thread_local_free_bit_map_offset = 0; 1754 size_t num_of_slots = 0; 1755 // Search for the maximum number of slots that allows enough space 1756 // for the header (including the bit maps.) 1757 for (int s = max_num_of_slots; s >= 0; s--) { 1758 size_t tmp_slots_size = bracket_size * s; 1759 size_t tmp_bit_map_size = RoundUp(s, sizeof(uint32_t) * kBitsPerByte) / kBitsPerByte; 1760 size_t tmp_bulk_free_bit_map_size = tmp_bit_map_size; 1761 size_t tmp_bulk_free_bit_map_off = fixed_header_size + tmp_bit_map_size; 1762 size_t tmp_thread_local_free_bit_map_size = tmp_bit_map_size; 1763 size_t tmp_thread_local_free_bit_map_off = tmp_bulk_free_bit_map_off + tmp_bulk_free_bit_map_size; 1764 size_t tmp_unaligned_header_size = tmp_thread_local_free_bit_map_off + tmp_thread_local_free_bit_map_size; 1765 // Align up the unaligned header size. bracket_size may not be a power of two. 1766 size_t tmp_header_size = (tmp_unaligned_header_size % bracket_size == 0) ? 1767 tmp_unaligned_header_size : 1768 tmp_unaligned_header_size + (bracket_size - tmp_unaligned_header_size % bracket_size); 1769 DCHECK_EQ(tmp_header_size % bracket_size, static_cast<size_t>(0)); 1770 DCHECK_EQ(tmp_header_size % 8, static_cast<size_t>(0)); 1771 if (tmp_slots_size + tmp_header_size <= run_size) { 1772 // Found the right number of slots, that is, there was enough 1773 // space for the header (including the bit maps.) 1774 num_of_slots = s; 1775 header_size = tmp_header_size; 1776 bulk_free_bit_map_offset = tmp_bulk_free_bit_map_off; 1777 thread_local_free_bit_map_offset = tmp_thread_local_free_bit_map_off; 1778 break; 1779 } 1780 } 1781 DCHECK(num_of_slots > 0 && header_size > 0 && bulk_free_bit_map_offset > 0); 1782 // Add the padding for the alignment remainder. 1783 header_size += run_size % bracket_size; 1784 DCHECK_EQ(header_size + num_of_slots * bracket_size, run_size); 1785 numOfSlots[i] = num_of_slots; 1786 headerSizes[i] = header_size; 1787 bulkFreeBitMapOffsets[i] = bulk_free_bit_map_offset; 1788 threadLocalFreeBitMapOffsets[i] = thread_local_free_bit_map_offset; 1789 if (kTraceRosAlloc) { 1790 LOG(INFO) << "numOfSlots[" << i << "]=" << numOfSlots[i] 1791 << ", headerSizes[" << i << "]=" << headerSizes[i] 1792 << ", bulkFreeBitMapOffsets[" << i << "]=" << bulkFreeBitMapOffsets[i] 1793 << ", threadLocalFreeBitMapOffsets[" << i << "]=" << threadLocalFreeBitMapOffsets[i];; 1794 } 1795 } 1796 // Fill the alloc bitmap so nobody can successfully allocate from it. 1797 if (kIsDebugBuild) { 1798 dedicated_full_run_->magic_num_ = kMagicNum; 1799 } 1800 // It doesn't matter which size bracket we use since the main goal is to have the allocation 1801 // fail 100% of the time you attempt to allocate into the dedicated full run. 1802 dedicated_full_run_->size_bracket_idx_ = 0; 1803 dedicated_full_run_->FillAllocBitMap(); 1804 dedicated_full_run_->SetIsThreadLocal(true); 1805} 1806 1807void RosAlloc::BytesAllocatedCallback(void* start, void* end, size_t used_bytes, void* arg) { 1808 if (used_bytes == 0) { 1809 return; 1810 } 1811 size_t* bytes_allocated = reinterpret_cast<size_t*>(arg); 1812 *bytes_allocated += used_bytes; 1813} 1814 1815void RosAlloc::ObjectsAllocatedCallback(void* start, void* end, size_t used_bytes, void* arg) { 1816 if (used_bytes == 0) { 1817 return; 1818 } 1819 size_t* objects_allocated = reinterpret_cast<size_t*>(arg); 1820 ++(*objects_allocated); 1821} 1822 1823void RosAlloc::Verify() { 1824 Thread* self = Thread::Current(); 1825 CHECK(Locks::mutator_lock_->IsExclusiveHeld(self)) 1826 << "The mutator locks isn't exclusively locked at RosAlloc::Verify()"; 1827 MutexLock mu(self, *Locks::thread_list_lock_); 1828 WriterMutexLock wmu(self, bulk_free_lock_); 1829 std::vector<Run*> runs; 1830 { 1831 MutexLock mu(self, lock_); 1832 size_t pm_end = page_map_size_; 1833 size_t i = 0; 1834 while (i < pm_end) { 1835 byte pm = page_map_[i]; 1836 switch (pm) { 1837 case kPageMapEmpty: { 1838 // The start of a free page run. 1839 FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize); 1840 DCHECK_EQ(fpr->magic_num_, kMagicNumFree); 1841 CHECK(free_page_runs_.find(fpr) != free_page_runs_.end()) 1842 << "An empty page must belong to the free page run set"; 1843 size_t fpr_size = fpr->ByteSize(this); 1844 CHECK(IsAligned<kPageSize>(fpr_size)) 1845 << "A free page run size isn't page-aligned : " << fpr_size; 1846 size_t num_pages = fpr_size / kPageSize; 1847 CHECK_GT(num_pages, static_cast<uintptr_t>(0)) 1848 << "A free page run size must be > 0 : " << fpr_size; 1849 for (size_t j = i + 1; j < i + num_pages; ++j) { 1850 CHECK_EQ(page_map_[j], kPageMapEmpty) 1851 << "A mismatch between the page map table for kPageMapEmpty " 1852 << " at page index " << j 1853 << " and the free page run size : page index range : " 1854 << i << " to " << (i + num_pages) << std::endl << DumpPageMap(); 1855 } 1856 i += num_pages; 1857 CHECK_LE(i, pm_end) << "Page map index " << i << " out of range < " << pm_end 1858 << std::endl << DumpPageMap(); 1859 break; 1860 } 1861 case kPageMapLargeObject: { 1862 // The start of a large object. 1863 size_t num_pages = 1; 1864 size_t idx = i + 1; 1865 while (idx < pm_end && page_map_[idx] == kPageMapLargeObjectPart) { 1866 num_pages++; 1867 idx++; 1868 } 1869 void* start = base_ + i * kPageSize; 1870 mirror::Object* obj = reinterpret_cast<mirror::Object*>(start); 1871 size_t obj_size = obj->SizeOf(); 1872 CHECK_GT(obj_size, kLargeSizeThreshold) 1873 << "A rosalloc large object size must be > " << kLargeSizeThreshold; 1874 CHECK_EQ(num_pages, RoundUp(obj_size, kPageSize) / kPageSize) 1875 << "A rosalloc large object size " << obj_size 1876 << " does not match the page map table " << (num_pages * kPageSize) 1877 << std::endl << DumpPageMap(); 1878 i += num_pages; 1879 CHECK_LE(i, pm_end) << "Page map index " << i << " out of range < " << pm_end 1880 << std::endl << DumpPageMap(); 1881 break; 1882 } 1883 case kPageMapLargeObjectPart: 1884 LOG(FATAL) << "Unreachable - page map type: " << pm << std::endl << DumpPageMap(); 1885 break; 1886 case kPageMapRun: { 1887 // The start of a run. 1888 Run* run = reinterpret_cast<Run*>(base_ + i * kPageSize); 1889 DCHECK_EQ(run->magic_num_, kMagicNum); 1890 size_t idx = run->size_bracket_idx_; 1891 CHECK_LT(idx, kNumOfSizeBrackets) << "Out of range size bracket index : " << idx; 1892 size_t num_pages = numOfPages[idx]; 1893 CHECK_GT(num_pages, static_cast<uintptr_t>(0)) 1894 << "Run size must be > 0 : " << num_pages; 1895 for (size_t j = i + 1; j < i + num_pages; ++j) { 1896 CHECK_EQ(page_map_[j], kPageMapRunPart) 1897 << "A mismatch between the page map table for kPageMapRunPart " 1898 << " at page index " << j 1899 << " and the run size : page index range " << i << " to " << (i + num_pages) 1900 << std::endl << DumpPageMap(); 1901 } 1902 // Don't verify the dedicated_full_run_ since it doesn't have any real allocations. 1903 runs.push_back(run); 1904 i += num_pages; 1905 CHECK_LE(i, pm_end) << "Page map index " << i << " out of range < " << pm_end 1906 << std::endl << DumpPageMap(); 1907 break; 1908 } 1909 case kPageMapRunPart: 1910 LOG(FATAL) << "Unreachable - page map type: " << pm << std::endl << DumpPageMap(); 1911 break; 1912 default: 1913 LOG(FATAL) << "Unreachable - page map type: " << pm << std::endl << DumpPageMap(); 1914 break; 1915 } 1916 } 1917 } 1918 1919 // Call Verify() here for the lock order. 1920 for (auto& run : runs) { 1921 run->Verify(self, this); 1922 } 1923} 1924 1925void RosAlloc::Run::Verify(Thread* self, RosAlloc* rosalloc) { 1926 DCHECK_EQ(magic_num_, kMagicNum) << "Bad magic number : " << Dump(); 1927 const size_t idx = size_bracket_idx_; 1928 CHECK_LT(idx, kNumOfSizeBrackets) << "Out of range size bracket index : " << Dump(); 1929 byte* slot_base = reinterpret_cast<byte*>(this) + headerSizes[idx]; 1930 const size_t num_slots = numOfSlots[idx]; 1931 const size_t num_vec = RoundUp(num_slots, 32) / 32; 1932 CHECK_GT(num_vec, 0U); 1933 size_t bracket_size = IndexToBracketSize(idx); 1934 CHECK_EQ(slot_base + num_slots * bracket_size, 1935 reinterpret_cast<byte*>(this) + numOfPages[idx] * kPageSize) 1936 << "Mismatch in the end address of the run " << Dump(); 1937 // Check that the bulk free bitmap is clean. It's only used during BulkFree(). 1938 CHECK(IsBulkFreeBitmapClean()) << "The bulk free bit map isn't clean " << Dump(); 1939 uint32_t last_word_mask = GetBitmapLastVectorMask(num_slots, num_vec); 1940 // Make sure all the bits at the end of the run are set so that we don't allocate there. 1941 CHECK_EQ(alloc_bit_map_[num_vec - 1] & last_word_mask, last_word_mask); 1942 // Ensure that the first bitmap index is valid. 1943 CHECK_LT(first_search_vec_idx_, num_vec); 1944 // Check the thread local runs, the current runs, and the run sets. 1945 if (IsThreadLocal()) { 1946 // If it's a thread local run, then it must be pointed to by an owner thread. 1947 bool owner_found = false; 1948 std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList(); 1949 for (auto it = thread_list.begin(); it != thread_list.end(); ++it) { 1950 Thread* thread = *it; 1951 for (size_t i = 0; i < kNumOfSizeBrackets; i++) { 1952 MutexLock mu(self, *rosalloc->size_bracket_locks_[i]); 1953 Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(i)); 1954 if (thread_local_run == this) { 1955 CHECK(!owner_found) 1956 << "A thread local run has more than one owner thread " << Dump(); 1957 CHECK_EQ(i, idx) 1958 << "A mismatching size bracket index in a thread local run " << Dump(); 1959 owner_found = true; 1960 } 1961 } 1962 } 1963 CHECK(owner_found) << "A thread local run has no owner thread " << Dump(); 1964 } else { 1965 // If it's not thread local, check that the thread local free bitmap is clean. 1966 CHECK(IsThreadLocalFreeBitmapClean()) 1967 << "A non-thread-local run's thread local free bitmap isn't clean " 1968 << Dump(); 1969 // Check if it's a current run for the size bucket. 1970 bool is_current_run = false; 1971 for (size_t i = 0; i < kNumOfSizeBrackets; i++) { 1972 MutexLock mu(self, *rosalloc->size_bracket_locks_[i]); 1973 Run* current_run = rosalloc->current_runs_[i]; 1974 if (idx == i) { 1975 if (this == current_run) { 1976 is_current_run = true; 1977 } 1978 } else { 1979 // If the size bucket index does not match, then it must not 1980 // be a current run. 1981 CHECK_NE(this, current_run) 1982 << "A current run points to a run with a wrong size bracket index " << Dump(); 1983 } 1984 } 1985 // If it's neither a thread local or current run, then it must be 1986 // in a run set. 1987 if (!is_current_run) { 1988 MutexLock mu(self, rosalloc->lock_); 1989 std::set<Run*>& non_full_runs = rosalloc->non_full_runs_[idx]; 1990 // If it's all free, it must be a free page run rather than a run. 1991 CHECK(!IsAllFree()) << "A free run must be in a free page run set " << Dump(); 1992 if (!IsFull()) { 1993 // If it's not full, it must in the non-full run set. 1994 CHECK(non_full_runs.find(this) != non_full_runs.end()) 1995 << "A non-full run isn't in the non-full run set " << Dump(); 1996 } else { 1997 // If it's full, it must in the full run set (debug build only.) 1998 if (kIsDebugBuild) { 1999 hash_set<Run*, hash_run, eq_run>& full_runs = rosalloc->full_runs_[idx]; 2000 CHECK(full_runs.find(this) != full_runs.end()) 2001 << " A full run isn't in the full run set " << Dump(); 2002 } 2003 } 2004 } 2005 } 2006 // Check each slot. 2007 size_t slots = 0; 2008 for (size_t v = 0; v < num_vec; v++, slots += 32) { 2009 DCHECK_GE(num_slots, slots) << "Out of bounds"; 2010 uint32_t vec = alloc_bit_map_[v]; 2011 uint32_t thread_local_free_vec = ThreadLocalFreeBitMap()[v]; 2012 size_t end = std::min(num_slots - slots, static_cast<size_t>(32)); 2013 for (size_t i = 0; i < end; ++i) { 2014 bool is_allocated = ((vec >> i) & 0x1) != 0; 2015 // If a thread local run, slots may be marked freed in the 2016 // thread local free bitmap. 2017 bool is_thread_local_freed = IsThreadLocal() && ((thread_local_free_vec >> i) & 0x1) != 0; 2018 if (is_allocated && !is_thread_local_freed) { 2019 byte* slot_addr = slot_base + (slots + i) * bracket_size; 2020 mirror::Object* obj = reinterpret_cast<mirror::Object*>(slot_addr); 2021 size_t obj_size = obj->SizeOf(); 2022 CHECK_LE(obj_size, kLargeSizeThreshold) 2023 << "A run slot contains a large object " << Dump(); 2024 CHECK_EQ(SizeToIndex(obj_size), idx) 2025 << PrettyTypeOf(obj) << " " 2026 << "obj_size=" << obj_size << ", idx=" << idx << " " 2027 << "A run slot contains an object with wrong size " << Dump(); 2028 } 2029 } 2030 } 2031} 2032 2033size_t RosAlloc::ReleasePages() { 2034 VLOG(heap) << "RosAlloc::ReleasePages()"; 2035 DCHECK(!DoesReleaseAllPages()); 2036 Thread* self = Thread::Current(); 2037 size_t reclaimed_bytes = 0; 2038 size_t i = 0; 2039 while (true) { 2040 MutexLock mu(self, lock_); 2041 // Check the page map size which might have changed due to grow/shrink. 2042 size_t pm_end = page_map_size_; 2043 if (i >= pm_end) { 2044 // Reached the end. 2045 break; 2046 } 2047 byte pm = page_map_[i]; 2048 switch (pm) { 2049 case kPageMapEmpty: { 2050 // The start of a free page run. Release pages. 2051 FreePageRun* fpr = reinterpret_cast<FreePageRun*>(base_ + i * kPageSize); 2052 DCHECK(free_page_runs_.find(fpr) != free_page_runs_.end()); 2053 size_t fpr_size = fpr->ByteSize(this); 2054 DCHECK(IsAligned<kPageSize>(fpr_size)); 2055 byte* start = reinterpret_cast<byte*>(fpr); 2056 if (kIsDebugBuild) { 2057 // In the debug build, the first page of a free page run 2058 // contains a magic number for debugging. Exclude it. 2059 start = reinterpret_cast<byte*>(fpr) + kPageSize; 2060 } 2061 byte* end = reinterpret_cast<byte*>(fpr) + fpr_size; 2062 CHECK_EQ(madvise(start, end - start, MADV_DONTNEED), 0); 2063 reclaimed_bytes += fpr_size; 2064 size_t num_pages = fpr_size / kPageSize; 2065 if (kIsDebugBuild) { 2066 for (size_t j = i + 1; j < i + num_pages; ++j) { 2067 DCHECK_EQ(page_map_[j], kPageMapEmpty); 2068 } 2069 } 2070 i += num_pages; 2071 DCHECK_LE(i, pm_end); 2072 break; 2073 } 2074 case kPageMapLargeObject: // Fall through. 2075 case kPageMapLargeObjectPart: // Fall through. 2076 case kPageMapRun: // Fall through. 2077 case kPageMapRunPart: // Fall through. 2078 ++i; 2079 break; // Skip. 2080 default: 2081 LOG(FATAL) << "Unreachable - page map type: " << pm; 2082 break; 2083 } 2084 } 2085 return reclaimed_bytes; 2086} 2087 2088} // namespace allocator 2089} // namespace gc 2090} // namespace art 2091