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 "arena_allocator-inl.h" 18 19 #include <sys/mman.h> 20 21 #include <algorithm> 22 #include <cstddef> 23 #include <iomanip> 24 #include <numeric> 25 26 #include <android-base/logging.h> 27 28 #include "base/systrace.h" 29 #include "mem_map.h" 30 #include "mutex.h" 31 #include "thread-current-inl.h" 32 33 namespace art { 34 35 constexpr size_t kMemoryToolRedZoneBytes = 8; 36 37 template <bool kCount> 38 const char* const ArenaAllocatorStatsImpl<kCount>::kAllocNames[] = { 39 // Every name should have the same width and end with a space. Abbreviate if necessary: 40 "Misc ", 41 "SwitchTbl ", 42 "SlowPaths ", 43 "GrowBitMap ", 44 "STL ", 45 "GraphBuilder ", 46 "Graph ", 47 "BasicBlock ", 48 "BlockList ", 49 "RevPostOrder ", 50 "LinearOrder ", 51 "ConstantsMap ", 52 "Predecessors ", 53 "Successors ", 54 "Dominated ", 55 "Instruction ", 56 "CtorFenceIns ", 57 "InvokeInputs ", 58 "PhiInputs ", 59 "LoopInfo ", 60 "LIBackEdges ", 61 "TryCatchInf ", 62 "UseListNode ", 63 "Environment ", 64 "EnvVRegs ", 65 "EnvLocations ", 66 "LocSummary ", 67 "SsaBuilder ", 68 "MoveOperands ", 69 "CodeBuffer ", 70 "StackMaps ", 71 "Optimization ", 72 "GVN ", 73 "InductionVar ", 74 "BCE ", 75 "DCE ", 76 "LSA ", 77 "LSE ", 78 "CFRE ", 79 "LICM ", 80 "LoopOpt ", 81 "SsaLiveness ", 82 "SsaPhiElim ", 83 "RefTypeProp ", 84 "SideEffects ", 85 "RegAllocator ", 86 "RegAllocVldt ", 87 "StackMapStm ", 88 "VectorNode ", 89 "CodeGen ", 90 "Assembler ", 91 "ParallelMove ", 92 "GraphChecker ", 93 "Verifier ", 94 "CallingConv ", 95 "CHA ", 96 "Scheduler ", 97 "Profile ", 98 "SBCloner ", 99 }; 100 101 template <bool kCount> 102 ArenaAllocatorStatsImpl<kCount>::ArenaAllocatorStatsImpl() 103 : num_allocations_(0u), 104 alloc_stats_(kNumArenaAllocKinds, 0u) { 105 } 106 107 template <bool kCount> 108 void ArenaAllocatorStatsImpl<kCount>::Copy(const ArenaAllocatorStatsImpl& other) { 109 num_allocations_ = other.num_allocations_; 110 std::copy_n(other.alloc_stats_.begin(), kNumArenaAllocKinds, alloc_stats_.begin()); 111 } 112 113 template <bool kCount> 114 void ArenaAllocatorStatsImpl<kCount>::RecordAlloc(size_t bytes, ArenaAllocKind kind) { 115 alloc_stats_[kind] += bytes; 116 ++num_allocations_; 117 } 118 119 template <bool kCount> 120 size_t ArenaAllocatorStatsImpl<kCount>::NumAllocations() const { 121 return num_allocations_; 122 } 123 124 template <bool kCount> 125 size_t ArenaAllocatorStatsImpl<kCount>::BytesAllocated() const { 126 const size_t init = 0u; // Initial value of the correct type. 127 return std::accumulate(alloc_stats_.begin(), alloc_stats_.end(), init); 128 } 129 130 template <bool kCount> 131 void ArenaAllocatorStatsImpl<kCount>::Dump(std::ostream& os, const Arena* first, 132 ssize_t lost_bytes_adjustment) const { 133 size_t malloc_bytes = 0u; 134 size_t lost_bytes = 0u; 135 size_t num_arenas = 0u; 136 for (const Arena* arena = first; arena != nullptr; arena = arena->next_) { 137 malloc_bytes += arena->Size(); 138 lost_bytes += arena->RemainingSpace(); 139 ++num_arenas; 140 } 141 // The lost_bytes_adjustment is used to make up for the fact that the current arena 142 // may not have the bytes_allocated_ updated correctly. 143 lost_bytes += lost_bytes_adjustment; 144 const size_t bytes_allocated = BytesAllocated(); 145 os << " MEM: used: " << bytes_allocated << ", allocated: " << malloc_bytes 146 << ", lost: " << lost_bytes << "\n"; 147 size_t num_allocations = NumAllocations(); 148 if (num_allocations != 0) { 149 os << "Number of arenas allocated: " << num_arenas << ", Number of allocations: " 150 << num_allocations << ", avg size: " << bytes_allocated / num_allocations << "\n"; 151 } 152 os << "===== Allocation by kind\n"; 153 static_assert(arraysize(kAllocNames) == kNumArenaAllocKinds, "arraysize of kAllocNames"); 154 for (int i = 0; i < kNumArenaAllocKinds; i++) { 155 // Reduce output by listing only allocation kinds that actually have allocations. 156 if (alloc_stats_[i] != 0u) { 157 os << kAllocNames[i] << std::setw(10) << alloc_stats_[i] << "\n"; 158 } 159 } 160 } 161 162 #pragma GCC diagnostic push 163 #if __clang_major__ >= 4 164 #pragma GCC diagnostic ignored "-Winstantiation-after-specialization" 165 #endif 166 // We're going to use ArenaAllocatorStatsImpl<kArenaAllocatorCountAllocations> which needs 167 // to be explicitly instantiated if kArenaAllocatorCountAllocations is true. Explicit 168 // instantiation of the specialization ArenaAllocatorStatsImpl<false> does not do anything 169 // but requires the warning "-Winstantiation-after-specialization" to be turned off. 170 // 171 // To avoid bit-rot of the ArenaAllocatorStatsImpl<true>, instantiate it also in debug builds 172 // (but keep the unnecessary code out of release builds) as we do not usually compile with 173 // kArenaAllocatorCountAllocations set to true. 174 template class ArenaAllocatorStatsImpl<kArenaAllocatorCountAllocations || kIsDebugBuild>; 175 #pragma GCC diagnostic pop 176 177 void ArenaAllocatorMemoryTool::DoMakeDefined(void* ptr, size_t size) { 178 MEMORY_TOOL_MAKE_DEFINED(ptr, size); 179 } 180 181 void ArenaAllocatorMemoryTool::DoMakeUndefined(void* ptr, size_t size) { 182 MEMORY_TOOL_MAKE_UNDEFINED(ptr, size); 183 } 184 185 void ArenaAllocatorMemoryTool::DoMakeInaccessible(void* ptr, size_t size) { 186 MEMORY_TOOL_MAKE_NOACCESS(ptr, size); 187 } 188 189 Arena::Arena() : bytes_allocated_(0), memory_(nullptr), size_(0), next_(nullptr) { 190 } 191 192 class MallocArena FINAL : public Arena { 193 public: 194 explicit MallocArena(size_t size = arena_allocator::kArenaDefaultSize); 195 virtual ~MallocArena(); 196 private: 197 static constexpr size_t RequiredOverallocation() { 198 return (alignof(std::max_align_t) < ArenaAllocator::kArenaAlignment) 199 ? ArenaAllocator::kArenaAlignment - alignof(std::max_align_t) 200 : 0u; 201 } 202 203 uint8_t* unaligned_memory_; 204 }; 205 206 MallocArena::MallocArena(size_t size) { 207 // We need to guarantee kArenaAlignment aligned allocation for the new arena. 208 // TODO: Use std::aligned_alloc() when it becomes available with C++17. 209 constexpr size_t overallocation = RequiredOverallocation(); 210 unaligned_memory_ = reinterpret_cast<uint8_t*>(calloc(1, size + overallocation)); 211 CHECK(unaligned_memory_ != nullptr); // Abort on OOM. 212 DCHECK_ALIGNED(unaligned_memory_, alignof(std::max_align_t)); 213 if (overallocation == 0u) { 214 memory_ = unaligned_memory_; 215 } else { 216 memory_ = AlignUp(unaligned_memory_, ArenaAllocator::kArenaAlignment); 217 if (UNLIKELY(RUNNING_ON_MEMORY_TOOL > 0)) { 218 size_t head = memory_ - unaligned_memory_; 219 size_t tail = overallocation - head; 220 MEMORY_TOOL_MAKE_NOACCESS(unaligned_memory_, head); 221 MEMORY_TOOL_MAKE_NOACCESS(memory_ + size, tail); 222 } 223 } 224 DCHECK_ALIGNED(memory_, ArenaAllocator::kArenaAlignment); 225 size_ = size; 226 } 227 228 MallocArena::~MallocArena() { 229 constexpr size_t overallocation = RequiredOverallocation(); 230 if (overallocation != 0u && UNLIKELY(RUNNING_ON_MEMORY_TOOL > 0)) { 231 size_t head = memory_ - unaligned_memory_; 232 size_t tail = overallocation - head; 233 MEMORY_TOOL_MAKE_UNDEFINED(unaligned_memory_, head); 234 MEMORY_TOOL_MAKE_UNDEFINED(memory_ + size_, tail); 235 } 236 free(reinterpret_cast<void*>(unaligned_memory_)); 237 } 238 239 class MemMapArena FINAL : public Arena { 240 public: 241 MemMapArena(size_t size, bool low_4gb, const char* name); 242 virtual ~MemMapArena(); 243 void Release() OVERRIDE; 244 245 private: 246 std::unique_ptr<MemMap> map_; 247 }; 248 249 MemMapArena::MemMapArena(size_t size, bool low_4gb, const char* name) { 250 // Round up to a full page as that's the smallest unit of allocation for mmap() 251 // and we want to be able to use all memory that we actually allocate. 252 size = RoundUp(size, kPageSize); 253 std::string error_msg; 254 map_.reset(MemMap::MapAnonymous( 255 name, nullptr, size, PROT_READ | PROT_WRITE, low_4gb, false, &error_msg)); 256 CHECK(map_.get() != nullptr) << error_msg; 257 memory_ = map_->Begin(); 258 static_assert(ArenaAllocator::kArenaAlignment <= kPageSize, 259 "Arena should not need stronger alignment than kPageSize."); 260 DCHECK_ALIGNED(memory_, ArenaAllocator::kArenaAlignment); 261 size_ = map_->Size(); 262 } 263 264 MemMapArena::~MemMapArena() { 265 // Destroys MemMap via std::unique_ptr<>. 266 } 267 268 void MemMapArena::Release() { 269 if (bytes_allocated_ > 0) { 270 map_->MadviseDontNeedAndZero(); 271 bytes_allocated_ = 0; 272 } 273 } 274 275 void Arena::Reset() { 276 if (bytes_allocated_ > 0) { 277 memset(Begin(), 0, bytes_allocated_); 278 bytes_allocated_ = 0; 279 } 280 } 281 282 ArenaPool::ArenaPool(bool use_malloc, bool low_4gb, const char* name) 283 : use_malloc_(use_malloc), 284 lock_("Arena pool lock", kArenaPoolLock), 285 free_arenas_(nullptr), 286 low_4gb_(low_4gb), 287 name_(name) { 288 if (low_4gb) { 289 CHECK(!use_malloc) << "low4gb must use map implementation"; 290 } 291 if (!use_malloc) { 292 MemMap::Init(); 293 } 294 } 295 296 ArenaPool::~ArenaPool() { 297 ReclaimMemory(); 298 } 299 300 void ArenaPool::ReclaimMemory() { 301 while (free_arenas_ != nullptr) { 302 Arena* arena = free_arenas_; 303 free_arenas_ = free_arenas_->next_; 304 delete arena; 305 } 306 } 307 308 void ArenaPool::LockReclaimMemory() { 309 MutexLock lock(Thread::Current(), lock_); 310 ReclaimMemory(); 311 } 312 313 Arena* ArenaPool::AllocArena(size_t size) { 314 Thread* self = Thread::Current(); 315 Arena* ret = nullptr; 316 { 317 MutexLock lock(self, lock_); 318 if (free_arenas_ != nullptr && LIKELY(free_arenas_->Size() >= size)) { 319 ret = free_arenas_; 320 free_arenas_ = free_arenas_->next_; 321 } 322 } 323 if (ret == nullptr) { 324 ret = use_malloc_ ? static_cast<Arena*>(new MallocArena(size)) : 325 new MemMapArena(size, low_4gb_, name_); 326 } 327 ret->Reset(); 328 return ret; 329 } 330 331 void ArenaPool::TrimMaps() { 332 if (!use_malloc_) { 333 ScopedTrace trace(__PRETTY_FUNCTION__); 334 // Doesn't work for malloc. 335 MutexLock lock(Thread::Current(), lock_); 336 for (Arena* arena = free_arenas_; arena != nullptr; arena = arena->next_) { 337 arena->Release(); 338 } 339 } 340 } 341 342 size_t ArenaPool::GetBytesAllocated() const { 343 size_t total = 0; 344 MutexLock lock(Thread::Current(), lock_); 345 for (Arena* arena = free_arenas_; arena != nullptr; arena = arena->next_) { 346 total += arena->GetBytesAllocated(); 347 } 348 return total; 349 } 350 351 void ArenaPool::FreeArenaChain(Arena* first) { 352 if (UNLIKELY(RUNNING_ON_MEMORY_TOOL > 0)) { 353 for (Arena* arena = first; arena != nullptr; arena = arena->next_) { 354 MEMORY_TOOL_MAKE_UNDEFINED(arena->memory_, arena->bytes_allocated_); 355 } 356 } 357 358 if (arena_allocator::kArenaAllocatorPreciseTracking) { 359 // Do not reuse arenas when tracking. 360 while (first != nullptr) { 361 Arena* next = first->next_; 362 delete first; 363 first = next; 364 } 365 return; 366 } 367 368 if (first != nullptr) { 369 Arena* last = first; 370 while (last->next_ != nullptr) { 371 last = last->next_; 372 } 373 Thread* self = Thread::Current(); 374 MutexLock lock(self, lock_); 375 last->next_ = free_arenas_; 376 free_arenas_ = first; 377 } 378 } 379 380 size_t ArenaAllocator::BytesAllocated() const { 381 return ArenaAllocatorStats::BytesAllocated(); 382 } 383 384 size_t ArenaAllocator::BytesUsed() const { 385 size_t total = ptr_ - begin_; 386 if (arena_head_ != nullptr) { 387 for (Arena* cur_arena = arena_head_->next_; cur_arena != nullptr; 388 cur_arena = cur_arena->next_) { 389 total += cur_arena->GetBytesAllocated(); 390 } 391 } 392 return total; 393 } 394 395 ArenaAllocator::ArenaAllocator(ArenaPool* pool) 396 : pool_(pool), 397 begin_(nullptr), 398 end_(nullptr), 399 ptr_(nullptr), 400 arena_head_(nullptr) { 401 } 402 403 void ArenaAllocator::UpdateBytesAllocated() { 404 if (arena_head_ != nullptr) { 405 // Update how many bytes we have allocated into the arena so that the arena pool knows how 406 // much memory to zero out. 407 arena_head_->bytes_allocated_ = ptr_ - begin_; 408 } 409 } 410 411 void* ArenaAllocator::AllocWithMemoryTool(size_t bytes, ArenaAllocKind kind) { 412 // We mark all memory for a newly retrieved arena as inaccessible and then 413 // mark only the actually allocated memory as defined. That leaves red zones 414 // and padding between allocations marked as inaccessible. 415 size_t rounded_bytes = RoundUp(bytes + kMemoryToolRedZoneBytes, 8); 416 ArenaAllocatorStats::RecordAlloc(rounded_bytes, kind); 417 uint8_t* ret; 418 if (UNLIKELY(rounded_bytes > static_cast<size_t>(end_ - ptr_))) { 419 ret = AllocFromNewArenaWithMemoryTool(rounded_bytes); 420 } else { 421 ret = ptr_; 422 ptr_ += rounded_bytes; 423 } 424 MEMORY_TOOL_MAKE_DEFINED(ret, bytes); 425 // Check that the memory is already zeroed out. 426 DCHECK(std::all_of(ret, ret + bytes, [](uint8_t val) { return val == 0u; })); 427 return ret; 428 } 429 430 void* ArenaAllocator::AllocWithMemoryToolAlign16(size_t bytes, ArenaAllocKind kind) { 431 // We mark all memory for a newly retrieved arena as inaccessible and then 432 // mark only the actually allocated memory as defined. That leaves red zones 433 // and padding between allocations marked as inaccessible. 434 size_t rounded_bytes = bytes + kMemoryToolRedZoneBytes; 435 DCHECK_ALIGNED(rounded_bytes, 8); // `bytes` is 16-byte aligned, red zone is 8-byte aligned. 436 uintptr_t padding = 437 ((reinterpret_cast<uintptr_t>(ptr_) + 15u) & 15u) - reinterpret_cast<uintptr_t>(ptr_); 438 ArenaAllocatorStats::RecordAlloc(rounded_bytes, kind); 439 uint8_t* ret; 440 if (UNLIKELY(padding + rounded_bytes > static_cast<size_t>(end_ - ptr_))) { 441 static_assert(kArenaAlignment >= 16, "Expecting sufficient alignment for new Arena."); 442 ret = AllocFromNewArenaWithMemoryTool(rounded_bytes); 443 } else { 444 ptr_ += padding; // Leave padding inaccessible. 445 ret = ptr_; 446 ptr_ += rounded_bytes; 447 } 448 MEMORY_TOOL_MAKE_DEFINED(ret, bytes); 449 // Check that the memory is already zeroed out. 450 DCHECK(std::all_of(ret, ret + bytes, [](uint8_t val) { return val == 0u; })); 451 return ret; 452 } 453 454 ArenaAllocator::~ArenaAllocator() { 455 // Reclaim all the arenas by giving them back to the thread pool. 456 UpdateBytesAllocated(); 457 pool_->FreeArenaChain(arena_head_); 458 } 459 460 uint8_t* ArenaAllocator::AllocFromNewArena(size_t bytes) { 461 Arena* new_arena = pool_->AllocArena(std::max(arena_allocator::kArenaDefaultSize, bytes)); 462 DCHECK(new_arena != nullptr); 463 DCHECK_LE(bytes, new_arena->Size()); 464 if (static_cast<size_t>(end_ - ptr_) > new_arena->Size() - bytes) { 465 // The old arena has more space remaining than the new one, so keep using it. 466 // This can happen when the requested size is over half of the default size. 467 DCHECK(arena_head_ != nullptr); 468 new_arena->bytes_allocated_ = bytes; // UpdateBytesAllocated() on the new_arena. 469 new_arena->next_ = arena_head_->next_; 470 arena_head_->next_ = new_arena; 471 } else { 472 UpdateBytesAllocated(); 473 new_arena->next_ = arena_head_; 474 arena_head_ = new_arena; 475 // Update our internal data structures. 476 begin_ = new_arena->Begin(); 477 DCHECK_ALIGNED(begin_, kAlignment); 478 ptr_ = begin_ + bytes; 479 end_ = new_arena->End(); 480 } 481 return new_arena->Begin(); 482 } 483 484 uint8_t* ArenaAllocator::AllocFromNewArenaWithMemoryTool(size_t bytes) { 485 uint8_t* ret = AllocFromNewArena(bytes); 486 uint8_t* noaccess_begin = ret + bytes; 487 uint8_t* noaccess_end; 488 if (ret == arena_head_->Begin()) { 489 DCHECK(ptr_ - bytes == ret); 490 noaccess_end = end_; 491 } else { 492 // We're still using the old arena but `ret` comes from a new one just after it. 493 DCHECK(arena_head_->next_ != nullptr); 494 DCHECK(ret == arena_head_->next_->Begin()); 495 DCHECK_EQ(bytes, arena_head_->next_->GetBytesAllocated()); 496 noaccess_end = arena_head_->next_->End(); 497 } 498 MEMORY_TOOL_MAKE_NOACCESS(noaccess_begin, noaccess_end - noaccess_begin); 499 return ret; 500 } 501 502 bool ArenaAllocator::Contains(const void* ptr) const { 503 if (ptr >= begin_ && ptr < end_) { 504 return true; 505 } 506 for (const Arena* cur_arena = arena_head_; cur_arena != nullptr; cur_arena = cur_arena->next_) { 507 if (cur_arena->Contains(ptr)) { 508 return true; 509 } 510 } 511 return false; 512 } 513 514 MemStats::MemStats(const char* name, 515 const ArenaAllocatorStats* stats, 516 const Arena* first_arena, 517 ssize_t lost_bytes_adjustment) 518 : name_(name), 519 stats_(stats), 520 first_arena_(first_arena), 521 lost_bytes_adjustment_(lost_bytes_adjustment) { 522 } 523 524 void MemStats::Dump(std::ostream& os) const { 525 os << name_ << " stats:\n"; 526 stats_->Dump(os, first_arena_, lost_bytes_adjustment_); 527 } 528 529 // Dump memory usage stats. 530 MemStats ArenaAllocator::GetMemStats() const { 531 ssize_t lost_bytes_adjustment = 532 (arena_head_ == nullptr) ? 0 : (end_ - ptr_) - arena_head_->RemainingSpace(); 533 return MemStats("ArenaAllocator", this, arena_head_, lost_bytes_adjustment); 534 } 535 536 } // namespace art 537