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