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