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