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