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 
Copy(const ArenaAllocatorStatsImpl & other ATTRIBUTE_UNUSED)118   void Copy(const ArenaAllocatorStatsImpl& other ATTRIBUTE_UNUSED) {}
RecordAlloc(size_t bytes ATTRIBUTE_UNUSED,ArenaAllocKind kind ATTRIBUTE_UNUSED)119   void RecordAlloc(size_t bytes ATTRIBUTE_UNUSED, ArenaAllocKind kind ATTRIBUTE_UNUSED) {}
NumAllocations()120   size_t NumAllocations() const { return 0u; }
BytesAllocated()121   size_t BytesAllocated() const { return 0u; }
Dump(std::ostream & os ATTRIBUTE_UNUSED,const Arena * first ATTRIBUTE_UNUSED,ssize_t lost_bytes_adjustment ATTRIBUTE_UNUSED)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:
ArenaAllocatorMemoryToolCheckImpl()157   ArenaAllocatorMemoryToolCheckImpl() : is_running_on_valgrind_(RUNNING_ON_MEMORY_TOOL) { }
IsRunningOnMemoryTool()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:
ArenaAllocatorMemoryToolCheckImpl()167   ArenaAllocatorMemoryToolCheckImpl() { }
IsRunningOnMemoryTool()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 
MakeDefined(void * ptr,size_t size)178   void MakeDefined(void* ptr, size_t size) {
179     if (UNLIKELY(IsRunningOnMemoryTool())) {
180       DoMakeDefined(ptr, size);
181     }
182   }
MakeUndefined(void * ptr,size_t size)183   void MakeUndefined(void* ptr, size_t size) {
184     if (UNLIKELY(IsRunningOnMemoryTool())) {
185       DoMakeUndefined(ptr, size);
186     }
187   }
MakeInaccessible(void * ptr,size_t size)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();
~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.
Release()207   virtual void Release() { }
Begin()208   uint8_t* Begin() {
209     return memory_;
210   }
211 
End()212   uint8_t* End() {
213     return memory_ + size_;
214   }
215 
Size()216   size_t Size() const {
217     return size_;
218   }
219 
RemainingSpace()220   size_t RemainingSpace() const {
221     return Size() - bytes_allocated_;
222   }
223 
GetBytesAllocated()224   size_t GetBytesAllocated() const {
225     return bytes_allocated_;
226   }
227 
228   // Return true if ptr is contained in the arena.
Contains(const void * ptr)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 
GetArenaPool()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