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 #ifndef ART_RUNTIME_BASE_ARENA_ALLOCATOR_H_ 18 #define ART_RUNTIME_BASE_ARENA_ALLOCATOR_H_ 19 20 #include <stddef.h> 21 #include <stdint.h> 22 23 #include "base/bit_utils.h" 24 #include "base/debug_stack.h" 25 #include "base/dchecked_vector.h" 26 #include "base/macros.h" 27 #include "base/memory_tool.h" 28 #include "mutex.h" 29 30 namespace art { 31 32 class Arena; 33 class ArenaPool; 34 class ArenaAllocator; 35 class ArenaStack; 36 class ScopedArenaAllocator; 37 class MemStats; 38 39 template <typename T> 40 class ArenaAllocatorAdapter; 41 42 static constexpr bool kArenaAllocatorCountAllocations = false; 43 44 // Type of allocation for memory tuning. 45 enum ArenaAllocKind { 46 kArenaAllocMisc, 47 kArenaAllocSwitchTable, 48 kArenaAllocSlowPaths, 49 kArenaAllocGrowableBitMap, 50 kArenaAllocSTL, 51 kArenaAllocGraphBuilder, 52 kArenaAllocGraph, 53 kArenaAllocBasicBlock, 54 kArenaAllocBlockList, 55 kArenaAllocReversePostOrder, 56 kArenaAllocLinearOrder, 57 kArenaAllocConstantsMap, 58 kArenaAllocPredecessors, 59 kArenaAllocSuccessors, 60 kArenaAllocDominated, 61 kArenaAllocInstruction, 62 kArenaAllocConstructorFenceInputs, 63 kArenaAllocInvokeInputs, 64 kArenaAllocPhiInputs, 65 kArenaAllocLoopInfo, 66 kArenaAllocLoopInfoBackEdges, 67 kArenaAllocTryCatchInfo, 68 kArenaAllocUseListNode, 69 kArenaAllocEnvironment, 70 kArenaAllocEnvironmentVRegs, 71 kArenaAllocEnvironmentLocations, 72 kArenaAllocLocationSummary, 73 kArenaAllocSsaBuilder, 74 kArenaAllocMoveOperands, 75 kArenaAllocCodeBuffer, 76 kArenaAllocStackMaps, 77 kArenaAllocOptimization, 78 kArenaAllocGvn, 79 kArenaAllocInductionVarAnalysis, 80 kArenaAllocBoundsCheckElimination, 81 kArenaAllocDCE, 82 kArenaAllocLSA, 83 kArenaAllocLSE, 84 kArenaAllocCFRE, 85 kArenaAllocLICM, 86 kArenaAllocLoopOptimization, 87 kArenaAllocSsaLiveness, 88 kArenaAllocSsaPhiElimination, 89 kArenaAllocReferenceTypePropagation, 90 kArenaAllocSideEffectsAnalysis, 91 kArenaAllocRegisterAllocator, 92 kArenaAllocRegisterAllocatorValidate, 93 kArenaAllocStackMapStream, 94 kArenaAllocVectorNode, 95 kArenaAllocCodeGenerator, 96 kArenaAllocAssembler, 97 kArenaAllocParallelMoveResolver, 98 kArenaAllocGraphChecker, 99 kArenaAllocVerifier, 100 kArenaAllocCallingConvention, 101 kArenaAllocCHA, 102 kArenaAllocScheduler, 103 kArenaAllocProfile, 104 kArenaAllocSuperblockCloner, 105 kNumArenaAllocKinds 106 }; 107 108 template <bool kCount> 109 class ArenaAllocatorStatsImpl; 110 111 template <> 112 class ArenaAllocatorStatsImpl<false> { 113 public: 114 ArenaAllocatorStatsImpl() = default; 115 ArenaAllocatorStatsImpl(const ArenaAllocatorStatsImpl& other) = default; 116 ArenaAllocatorStatsImpl& operator = (const ArenaAllocatorStatsImpl& other) = delete; 117 118 void Copy(const ArenaAllocatorStatsImpl& other ATTRIBUTE_UNUSED) {} 119 void RecordAlloc(size_t bytes ATTRIBUTE_UNUSED, ArenaAllocKind kind ATTRIBUTE_UNUSED) {} 120 size_t NumAllocations() const { return 0u; } 121 size_t BytesAllocated() const { return 0u; } 122 void Dump(std::ostream& os ATTRIBUTE_UNUSED, 123 const Arena* first ATTRIBUTE_UNUSED, 124 ssize_t lost_bytes_adjustment ATTRIBUTE_UNUSED) const {} 125 }; 126 127 template <bool kCount> 128 class ArenaAllocatorStatsImpl { 129 public: 130 ArenaAllocatorStatsImpl(); 131 ArenaAllocatorStatsImpl(const ArenaAllocatorStatsImpl& other) = default; 132 ArenaAllocatorStatsImpl& operator = (const ArenaAllocatorStatsImpl& other) = delete; 133 134 void Copy(const ArenaAllocatorStatsImpl& other); 135 void RecordAlloc(size_t bytes, ArenaAllocKind kind); 136 size_t NumAllocations() const; 137 size_t BytesAllocated() const; 138 void Dump(std::ostream& os, const Arena* first, ssize_t lost_bytes_adjustment) const; 139 140 private: 141 size_t num_allocations_; 142 dchecked_vector<size_t> alloc_stats_; // Bytes used by various allocation kinds. 143 144 static const char* const kAllocNames[]; 145 }; 146 147 typedef ArenaAllocatorStatsImpl<kArenaAllocatorCountAllocations> ArenaAllocatorStats; 148 149 template <bool kAvailable, bool kValgrind> 150 class ArenaAllocatorMemoryToolCheckImpl { 151 // This is the generic template but since there is a partial specialization 152 // for kValgrind == false, this can be instantiated only for kValgrind == true. 153 static_assert(kValgrind, "This template can be instantiated only for Valgrind."); 154 static_assert(kAvailable, "Valgrind implies memory tool availability."); 155 156 public: 157 ArenaAllocatorMemoryToolCheckImpl() : is_running_on_valgrind_(RUNNING_ON_MEMORY_TOOL) { } 158 bool IsRunningOnMemoryTool() { return is_running_on_valgrind_; } 159 160 private: 161 const bool is_running_on_valgrind_; 162 }; 163 164 template <bool kAvailable> 165 class ArenaAllocatorMemoryToolCheckImpl<kAvailable, false> { 166 public: 167 ArenaAllocatorMemoryToolCheckImpl() { } 168 bool IsRunningOnMemoryTool() { return kAvailable; } 169 }; 170 171 typedef ArenaAllocatorMemoryToolCheckImpl<kMemoryToolIsAvailable, kMemoryToolIsValgrind> 172 ArenaAllocatorMemoryToolCheck; 173 174 class ArenaAllocatorMemoryTool : private ArenaAllocatorMemoryToolCheck { 175 public: 176 using ArenaAllocatorMemoryToolCheck::IsRunningOnMemoryTool; 177 178 void MakeDefined(void* ptr, size_t size) { 179 if (UNLIKELY(IsRunningOnMemoryTool())) { 180 DoMakeDefined(ptr, size); 181 } 182 } 183 void MakeUndefined(void* ptr, size_t size) { 184 if (UNLIKELY(IsRunningOnMemoryTool())) { 185 DoMakeUndefined(ptr, size); 186 } 187 } 188 void MakeInaccessible(void* ptr, size_t size) { 189 if (UNLIKELY(IsRunningOnMemoryTool())) { 190 DoMakeInaccessible(ptr, size); 191 } 192 } 193 194 private: 195 void DoMakeDefined(void* ptr, size_t size); 196 void DoMakeUndefined(void* ptr, size_t size); 197 void DoMakeInaccessible(void* ptr, size_t size); 198 }; 199 200 class Arena { 201 public: 202 Arena(); 203 virtual ~Arena() { } 204 // Reset is for pre-use and uses memset for performance. 205 void Reset(); 206 // Release is used inbetween uses and uses madvise for memory usage. 207 virtual void Release() { } 208 uint8_t* Begin() { 209 return memory_; 210 } 211 212 uint8_t* End() { 213 return memory_ + size_; 214 } 215 216 size_t Size() const { 217 return size_; 218 } 219 220 size_t RemainingSpace() const { 221 return Size() - bytes_allocated_; 222 } 223 224 size_t GetBytesAllocated() const { 225 return bytes_allocated_; 226 } 227 228 // Return true if ptr is contained in the arena. 229 bool Contains(const void* ptr) const { 230 return memory_ <= ptr && ptr < memory_ + bytes_allocated_; 231 } 232 233 protected: 234 size_t bytes_allocated_; 235 uint8_t* memory_; 236 size_t size_; 237 Arena* next_; 238 friend class ArenaPool; 239 friend class ArenaAllocator; 240 friend class ArenaStack; 241 friend class ScopedArenaAllocator; 242 template <bool kCount> friend class ArenaAllocatorStatsImpl; 243 244 friend class ArenaAllocatorTest; 245 246 private: 247 DISALLOW_COPY_AND_ASSIGN(Arena); 248 }; 249 250 class ArenaPool { 251 public: 252 explicit ArenaPool(bool use_malloc = true, 253 bool low_4gb = false, 254 const char* name = "LinearAlloc"); 255 ~ArenaPool(); 256 Arena* AllocArena(size_t size) REQUIRES(!lock_); 257 void FreeArenaChain(Arena* first) REQUIRES(!lock_); 258 size_t GetBytesAllocated() const REQUIRES(!lock_); 259 void ReclaimMemory() NO_THREAD_SAFETY_ANALYSIS; 260 void LockReclaimMemory() REQUIRES(!lock_); 261 // Trim the maps in arenas by madvising, used by JIT to reduce memory usage. This only works 262 // use_malloc is false. 263 void TrimMaps() REQUIRES(!lock_); 264 265 private: 266 const bool use_malloc_; 267 mutable Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER; 268 Arena* free_arenas_ GUARDED_BY(lock_); 269 const bool low_4gb_; 270 const char* name_; 271 DISALLOW_COPY_AND_ASSIGN(ArenaPool); 272 }; 273 274 // Fast single-threaded allocator for zero-initialized memory chunks. 275 // 276 // Memory is allocated from ArenaPool in large chunks and then rationed through 277 // the ArenaAllocator. It's returned to the ArenaPool only when the ArenaAllocator 278 // is destroyed. 279 class ArenaAllocator 280 : private DebugStackRefCounter, private ArenaAllocatorStats, private ArenaAllocatorMemoryTool { 281 public: 282 explicit ArenaAllocator(ArenaPool* pool); 283 ~ArenaAllocator(); 284 285 using ArenaAllocatorMemoryTool::IsRunningOnMemoryTool; 286 using ArenaAllocatorMemoryTool::MakeDefined; 287 using ArenaAllocatorMemoryTool::MakeUndefined; 288 using ArenaAllocatorMemoryTool::MakeInaccessible; 289 290 // Get adapter for use in STL containers. See arena_containers.h . 291 ArenaAllocatorAdapter<void> Adapter(ArenaAllocKind kind = kArenaAllocSTL); 292 293 // Returns zeroed memory. 294 void* Alloc(size_t bytes, ArenaAllocKind kind = kArenaAllocMisc) ALWAYS_INLINE { 295 if (UNLIKELY(IsRunningOnMemoryTool())) { 296 return AllocWithMemoryTool(bytes, kind); 297 } 298 bytes = RoundUp(bytes, kAlignment); 299 ArenaAllocatorStats::RecordAlloc(bytes, kind); 300 if (UNLIKELY(bytes > static_cast<size_t>(end_ - ptr_))) { 301 return AllocFromNewArena(bytes); 302 } 303 uint8_t* ret = ptr_; 304 DCHECK_ALIGNED(ret, kAlignment); 305 ptr_ += bytes; 306 return ret; 307 } 308 309 // Returns zeroed memory. 310 void* AllocAlign16(size_t bytes, ArenaAllocKind kind = kArenaAllocMisc) ALWAYS_INLINE { 311 // It is an error to request 16-byte aligned allocation of unaligned size. 312 DCHECK_ALIGNED(bytes, 16); 313 if (UNLIKELY(IsRunningOnMemoryTool())) { 314 return AllocWithMemoryToolAlign16(bytes, kind); 315 } 316 uintptr_t padding = 317 ((reinterpret_cast<uintptr_t>(ptr_) + 15u) & 15u) - reinterpret_cast<uintptr_t>(ptr_); 318 ArenaAllocatorStats::RecordAlloc(bytes, kind); 319 if (UNLIKELY(padding + bytes > static_cast<size_t>(end_ - ptr_))) { 320 static_assert(kArenaAlignment >= 16, "Expecting sufficient alignment for new Arena."); 321 return AllocFromNewArena(bytes); 322 } 323 ptr_ += padding; 324 uint8_t* ret = ptr_; 325 DCHECK_ALIGNED(ret, 16); 326 ptr_ += bytes; 327 return ret; 328 } 329 330 // Realloc never frees the input pointer, it is the caller's job to do this if necessary. 331 void* Realloc(void* ptr, 332 size_t ptr_size, 333 size_t new_size, 334 ArenaAllocKind kind = kArenaAllocMisc) ALWAYS_INLINE { 335 DCHECK_GE(new_size, ptr_size); 336 DCHECK_EQ(ptr == nullptr, ptr_size == 0u); 337 // We always allocate aligned. 338 const size_t aligned_ptr_size = RoundUp(ptr_size, kAlignment); 339 auto* end = reinterpret_cast<uint8_t*>(ptr) + aligned_ptr_size; 340 // If we haven't allocated anything else, we can safely extend. 341 if (end == ptr_) { 342 // Red zone prevents end == ptr_ (unless input = allocator state = null). 343 DCHECK(!IsRunningOnMemoryTool() || ptr_ == nullptr); 344 const size_t aligned_new_size = RoundUp(new_size, kAlignment); 345 const size_t size_delta = aligned_new_size - aligned_ptr_size; 346 // Check remain space. 347 const size_t remain = end_ - ptr_; 348 if (remain >= size_delta) { 349 ptr_ += size_delta; 350 ArenaAllocatorStats::RecordAlloc(size_delta, kind); 351 DCHECK_ALIGNED(ptr_, kAlignment); 352 return ptr; 353 } 354 } 355 auto* new_ptr = Alloc(new_size, kind); // Note: Alloc will take care of aligning new_size. 356 memcpy(new_ptr, ptr, ptr_size); 357 // TODO: Call free on ptr if linear alloc supports free. 358 return new_ptr; 359 } 360 361 template <typename T> 362 T* Alloc(ArenaAllocKind kind = kArenaAllocMisc) { 363 return AllocArray<T>(1, kind); 364 } 365 366 template <typename T> 367 T* AllocArray(size_t length, ArenaAllocKind kind = kArenaAllocMisc) { 368 return static_cast<T*>(Alloc(length * sizeof(T), kind)); 369 } 370 371 size_t BytesAllocated() const; 372 373 MemStats GetMemStats() const; 374 375 // The BytesUsed method sums up bytes allocated from arenas in arena_head_ and nodes. 376 // TODO: Change BytesAllocated to this behavior? 377 size_t BytesUsed() const; 378 379 ArenaPool* GetArenaPool() const { 380 return pool_; 381 } 382 383 bool Contains(const void* ptr) const; 384 385 // The alignment guaranteed for individual allocations. 386 static constexpr size_t kAlignment = 8u; 387 388 // The alignment required for the whole Arena rather than individual allocations. 389 static constexpr size_t kArenaAlignment = 16u; 390 391 private: 392 void* AllocWithMemoryTool(size_t bytes, ArenaAllocKind kind); 393 void* AllocWithMemoryToolAlign16(size_t bytes, ArenaAllocKind kind); 394 uint8_t* AllocFromNewArena(size_t bytes); 395 uint8_t* AllocFromNewArenaWithMemoryTool(size_t bytes); 396 397 void UpdateBytesAllocated(); 398 399 ArenaPool* pool_; 400 uint8_t* begin_; 401 uint8_t* end_; 402 uint8_t* ptr_; 403 Arena* arena_head_; 404 405 template <typename U> 406 friend class ArenaAllocatorAdapter; 407 408 friend class ArenaAllocatorTest; 409 410 DISALLOW_COPY_AND_ASSIGN(ArenaAllocator); 411 }; // ArenaAllocator 412 413 class MemStats { 414 public: 415 MemStats(const char* name, 416 const ArenaAllocatorStats* stats, 417 const Arena* first_arena, 418 ssize_t lost_bytes_adjustment = 0); 419 void Dump(std::ostream& os) const; 420 421 private: 422 const char* const name_; 423 const ArenaAllocatorStats* const stats_; 424 const Arena* const first_arena_; 425 const ssize_t lost_bytes_adjustment_; 426 }; // MemStats 427 428 } // namespace art 429 430 #endif // ART_RUNTIME_BASE_ARENA_ALLOCATOR_H_ 431