arena_allocator.cc revision f44d36c8423f81cbb5e9f55d8813e26ffa1a7f3b 
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#include <algorithm>
18#include <cstddef>
19#include <iomanip>
20#include <numeric>
21
22#include "arena_allocator.h"
23#include "logging.h"
24#include "mem_map.h"
25#include "mutex.h"
26#include "thread-inl.h"
27#include "systrace.h"
28
29namespace art {
30
31constexpr size_t kMemoryToolRedZoneBytes = 8;
32constexpr size_t Arena::kDefaultSize;
33
34template <bool kCount>
35const char* const ArenaAllocatorStatsImpl<kCount>::kAllocNames[] = {
36  "Misc         ",
37  "SwitchTbl    ",
38  "SlowPaths    ",
39  "GrowBitMap   ",
40  "STL          ",
41  "GraphBuilder ",
42  "Graph        ",
43  "BasicBlock   ",
44  "BlockList    ",
45  "RevPostOrder ",
46  "LinearOrder  ",
47  "ConstantsMap ",
48  "Predecessors ",
49  "Successors   ",
50  "Dominated    ",
51  "Instruction  ",
52  "InvokeInputs ",
53  "PhiInputs    ",
54  "LoopInfo     ",
55  "LIBackEdges  ",
56  "TryCatchInf  ",
57  "UseListNode  ",
58  "Environment  ",
59  "EnvVRegs     ",
60  "EnvLocations ",
61  "LocSummary   ",
62  "SsaBuilder   ",
63  "MoveOperands ",
64  "CodeBuffer   ",
65  "StackMaps    ",
66  "Optimization ",
67  "GVN          ",
68  "InductionVar ",
69  "BCE          ",
70  "DCE          ",
71  "LSE          ",
72  "LICM         ",
73  "LoopOpt      ",
74  "SsaLiveness  ",
75  "SsaPhiElim   ",
76  "RefTypeProp  ",
77  "SideEffects  ",
78  "RegAllocator ",
79  "RegAllocVldt ",
80  "StackMapStm  ",
81  "CodeGen      ",
82  "Assembler    ",
83  "ParallelMove ",
84  "GraphChecker ",
85  "Verifier     ",
86  "CallingConv  ",
87  "CHA          ",
88  "Scheduler    ",
89};
90
91template <bool kCount>
92ArenaAllocatorStatsImpl<kCount>::ArenaAllocatorStatsImpl()
93    : num_allocations_(0u),
94      alloc_stats_(kNumArenaAllocKinds, 0u) {
95}
96
97template <bool kCount>
98void ArenaAllocatorStatsImpl<kCount>::Copy(const ArenaAllocatorStatsImpl& other) {
99  num_allocations_ = other.num_allocations_;
100  std::copy_n(other.alloc_stats_.begin(), kNumArenaAllocKinds, alloc_stats_.begin());
101}
102
103template <bool kCount>
104void ArenaAllocatorStatsImpl<kCount>::RecordAlloc(size_t bytes, ArenaAllocKind kind) {
105  alloc_stats_[kind] += bytes;
106  ++num_allocations_;
107}
108
109template <bool kCount>
110size_t ArenaAllocatorStatsImpl<kCount>::NumAllocations() const {
111  return num_allocations_;
112}
113
114template <bool kCount>
115size_t ArenaAllocatorStatsImpl<kCount>::BytesAllocated() const {
116  const size_t init = 0u;  // Initial value of the correct type.
117  return std::accumulate(alloc_stats_.begin(), alloc_stats_.end(), init);
118}
119
120template <bool kCount>
121void ArenaAllocatorStatsImpl<kCount>::Dump(std::ostream& os, const Arena* first,
122                                           ssize_t lost_bytes_adjustment) const {
123  size_t malloc_bytes = 0u;
124  size_t lost_bytes = 0u;
125  size_t num_arenas = 0u;
126  for (const Arena* arena = first; arena != nullptr; arena = arena->next_) {
127    malloc_bytes += arena->Size();
128    lost_bytes += arena->RemainingSpace();
129    ++num_arenas;
130  }
131  // The lost_bytes_adjustment is used to make up for the fact that the current arena
132  // may not have the bytes_allocated_ updated correctly.
133  lost_bytes += lost_bytes_adjustment;
134  const size_t bytes_allocated = BytesAllocated();
135  os << " MEM: used: " << bytes_allocated << ", allocated: " << malloc_bytes
136     << ", lost: " << lost_bytes << "\n";
137  size_t num_allocations = NumAllocations();
138  if (num_allocations != 0) {
139    os << "Number of arenas allocated: " << num_arenas << ", Number of allocations: "
140       << num_allocations << ", avg size: " << bytes_allocated / num_allocations << "\n";
141  }
142  os << "===== Allocation by kind\n";
143  static_assert(arraysize(kAllocNames) == kNumArenaAllocKinds, "arraysize of kAllocNames");
144  for (int i = 0; i < kNumArenaAllocKinds; i++) {
145      os << kAllocNames[i] << std::setw(10) << alloc_stats_[i] << "\n";
146  }
147}
148
149#pragma GCC diagnostic push
150#if __clang_major__ >= 4
151#pragma GCC diagnostic ignored "-Winstantiation-after-specialization"
152#endif
153// Explicitly instantiate the used implementation.
154template class ArenaAllocatorStatsImpl<kArenaAllocatorCountAllocations>;
155#pragma GCC diagnostic pop
156
157void ArenaAllocatorMemoryTool::DoMakeDefined(void* ptr, size_t size) {
158  MEMORY_TOOL_MAKE_DEFINED(ptr, size);
159}
160
161void ArenaAllocatorMemoryTool::DoMakeUndefined(void* ptr, size_t size) {
162  MEMORY_TOOL_MAKE_UNDEFINED(ptr, size);
163}
164
165void ArenaAllocatorMemoryTool::DoMakeInaccessible(void* ptr, size_t size) {
166  MEMORY_TOOL_MAKE_NOACCESS(ptr, size);
167}
168
169Arena::Arena() : bytes_allocated_(0), next_(nullptr) {
170}
171
172class MallocArena FINAL : public Arena {
173 public:
174  explicit MallocArena(size_t size = Arena::kDefaultSize);
175  virtual ~MallocArena();
176 private:
177  static constexpr size_t RequiredOverallocation() {
178    return (alignof(std::max_align_t) < ArenaAllocator::kArenaAlignment)
179        ? ArenaAllocator::kArenaAlignment - alignof(std::max_align_t)
180        : 0u;
181  }
182
183  uint8_t* unaligned_memory_;
184};
185
186MallocArena::MallocArena(size_t size) {
187  // We need to guarantee kArenaAlignment aligned allocation for the new arena.
188  // TODO: Use std::aligned_alloc() when it becomes available with C++17.
189  constexpr size_t overallocation = RequiredOverallocation();
190  unaligned_memory_ = reinterpret_cast<uint8_t*>(calloc(1, size + overallocation));
191  CHECK(unaligned_memory_ != nullptr);  // Abort on OOM.
192  DCHECK_ALIGNED(unaligned_memory_, alignof(std::max_align_t));
193  if (overallocation == 0u) {
194    memory_ = unaligned_memory_;
195  } else {
196    memory_ = AlignUp(unaligned_memory_, ArenaAllocator::kArenaAlignment);
197    if (UNLIKELY(RUNNING_ON_MEMORY_TOOL > 0)) {
198      size_t head = memory_ - unaligned_memory_;
199      size_t tail = overallocation - head;
200      MEMORY_TOOL_MAKE_NOACCESS(unaligned_memory_, head);
201      MEMORY_TOOL_MAKE_NOACCESS(memory_ + size, tail);
202    }
203  }
204  DCHECK_ALIGNED(memory_, ArenaAllocator::kArenaAlignment);
205  size_ = size;
206}
207
208MallocArena::~MallocArena() {
209  constexpr size_t overallocation = RequiredOverallocation();
210  if (overallocation != 0u && UNLIKELY(RUNNING_ON_MEMORY_TOOL > 0)) {
211    size_t head = memory_ - unaligned_memory_;
212    size_t tail = overallocation - head;
213    MEMORY_TOOL_MAKE_UNDEFINED(unaligned_memory_, head);
214    MEMORY_TOOL_MAKE_UNDEFINED(memory_ + size_, tail);
215  }
216  free(reinterpret_cast<void*>(unaligned_memory_));
217}
218
219class MemMapArena FINAL : public Arena {
220 public:
221  MemMapArena(size_t size, bool low_4gb, const char* name);
222  virtual ~MemMapArena();
223  void Release() OVERRIDE;
224
225 private:
226  std::unique_ptr<MemMap> map_;
227};
228
229MemMapArena::MemMapArena(size_t size, bool low_4gb, const char* name) {
230  // Round up to a full page as that's the smallest unit of allocation for mmap()
231  // and we want to be able to use all memory that we actually allocate.
232  size = RoundUp(size, kPageSize);
233  std::string error_msg;
234  map_.reset(MemMap::MapAnonymous(
235      name, nullptr, size, PROT_READ | PROT_WRITE, low_4gb, false, &error_msg));
236  CHECK(map_.get() != nullptr) << error_msg;
237  memory_ = map_->Begin();
238  static_assert(ArenaAllocator::kArenaAlignment <= kPageSize,
239                "Arena should not need stronger alignment than kPageSize.");
240  DCHECK_ALIGNED(memory_, ArenaAllocator::kArenaAlignment);
241  size_ = map_->Size();
242}
243
244MemMapArena::~MemMapArena() {
245  // Destroys MemMap via std::unique_ptr<>.
246}
247
248void MemMapArena::Release() {
249  if (bytes_allocated_ > 0) {
250    map_->MadviseDontNeedAndZero();
251    bytes_allocated_ = 0;
252  }
253}
254
255void Arena::Reset() {
256  if (bytes_allocated_ > 0) {
257    memset(Begin(), 0, bytes_allocated_);
258    bytes_allocated_ = 0;
259  }
260}
261
262ArenaPool::ArenaPool(bool use_malloc, bool low_4gb, const char* name)
263    : use_malloc_(use_malloc),
264      lock_("Arena pool lock", kArenaPoolLock),
265      free_arenas_(nullptr),
266      low_4gb_(low_4gb),
267      name_(name) {
268  if (low_4gb) {
269    CHECK(!use_malloc) << "low4gb must use map implementation";
270  }
271  if (!use_malloc) {
272    MemMap::Init();
273  }
274}
275
276ArenaPool::~ArenaPool() {
277  ReclaimMemory();
278}
279
280void ArenaPool::ReclaimMemory() {
281  while (free_arenas_ != nullptr) {
282    auto* arena = free_arenas_;
283    free_arenas_ = free_arenas_->next_;
284    delete arena;
285  }
286}
287
288void ArenaPool::LockReclaimMemory() {
289  MutexLock lock(Thread::Current(), lock_);
290  ReclaimMemory();
291}
292
293Arena* ArenaPool::AllocArena(size_t size) {
294  Thread* self = Thread::Current();
295  Arena* ret = nullptr;
296  {
297    MutexLock lock(self, lock_);
298    if (free_arenas_ != nullptr && LIKELY(free_arenas_->Size() >= size)) {
299      ret = free_arenas_;
300      free_arenas_ = free_arenas_->next_;
301    }
302  }
303  if (ret == nullptr) {
304    ret = use_malloc_ ? static_cast<Arena*>(new MallocArena(size)) :
305        new MemMapArena(size, low_4gb_, name_);
306  }
307  ret->Reset();
308  return ret;
309}
310
311void ArenaPool::TrimMaps() {
312  if (!use_malloc_) {
313    ScopedTrace trace(__PRETTY_FUNCTION__);
314    // Doesn't work for malloc.
315    MutexLock lock(Thread::Current(), lock_);
316    for (auto* arena = free_arenas_; arena != nullptr; arena = arena->next_) {
317      arena->Release();
318    }
319  }
320}
321
322size_t ArenaPool::GetBytesAllocated() const {
323  size_t total = 0;
324  MutexLock lock(Thread::Current(), lock_);
325  for (Arena* arena = free_arenas_; arena != nullptr; arena = arena->next_) {
326    total += arena->GetBytesAllocated();
327  }
328  return total;
329}
330
331void ArenaPool::FreeArenaChain(Arena* first) {
332  if (UNLIKELY(RUNNING_ON_MEMORY_TOOL > 0)) {
333    for (Arena* arena = first; arena != nullptr; arena = arena->next_) {
334      MEMORY_TOOL_MAKE_UNDEFINED(arena->memory_, arena->bytes_allocated_);
335    }
336  }
337  if (first != nullptr) {
338    Arena* last = first;
339    while (last->next_ != nullptr) {
340      last = last->next_;
341    }
342    Thread* self = Thread::Current();
343    MutexLock lock(self, lock_);
344    last->next_ = free_arenas_;
345    free_arenas_ = first;
346  }
347}
348
349size_t ArenaAllocator::BytesAllocated() const {
350  return ArenaAllocatorStats::BytesAllocated();
351}
352
353size_t ArenaAllocator::BytesUsed() const {
354  size_t total = ptr_ - begin_;
355  if (arena_head_ != nullptr) {
356    for (Arena* cur_arena = arena_head_->next_; cur_arena != nullptr;
357         cur_arena = cur_arena->next_) {
358     total += cur_arena->GetBytesAllocated();
359    }
360  }
361  return total;
362}
363
364ArenaAllocator::ArenaAllocator(ArenaPool* pool)
365  : pool_(pool),
366    begin_(nullptr),
367    end_(nullptr),
368    ptr_(nullptr),
369    arena_head_(nullptr) {
370}
371
372void ArenaAllocator::UpdateBytesAllocated() {
373  if (arena_head_ != nullptr) {
374    // Update how many bytes we have allocated into the arena so that the arena pool knows how
375    // much memory to zero out.
376    arena_head_->bytes_allocated_ = ptr_ - begin_;
377  }
378}
379
380void* ArenaAllocator::AllocWithMemoryTool(size_t bytes, ArenaAllocKind kind) {
381  // We mark all memory for a newly retrieved arena as inaccessible and then
382  // mark only the actually allocated memory as defined. That leaves red zones
383  // and padding between allocations marked as inaccessible.
384  size_t rounded_bytes = RoundUp(bytes + kMemoryToolRedZoneBytes, 8);
385  ArenaAllocatorStats::RecordAlloc(rounded_bytes, kind);
386  uint8_t* ret;
387  if (UNLIKELY(rounded_bytes > static_cast<size_t>(end_ - ptr_))) {
388    ret = AllocFromNewArenaWithMemoryTool(rounded_bytes);
389  } else {
390    ret = ptr_;
391    ptr_ += rounded_bytes;
392  }
393  MEMORY_TOOL_MAKE_DEFINED(ret, bytes);
394  // Check that the memory is already zeroed out.
395  DCHECK(std::all_of(ret, ret + bytes, [](uint8_t val) { return val == 0u; }));
396  return ret;
397}
398
399void* ArenaAllocator::AllocWithMemoryToolAlign16(size_t bytes, ArenaAllocKind kind) {
400  // We mark all memory for a newly retrieved arena as inaccessible and then
401  // mark only the actually allocated memory as defined. That leaves red zones
402  // and padding between allocations marked as inaccessible.
403  size_t rounded_bytes = bytes + kMemoryToolRedZoneBytes;
404  DCHECK_ALIGNED(rounded_bytes, 8);  // `bytes` is 16-byte aligned, red zone is 8-byte aligned.
405  uintptr_t padding =
406      ((reinterpret_cast<uintptr_t>(ptr_) + 15u) & 15u) - reinterpret_cast<uintptr_t>(ptr_);
407  ArenaAllocatorStats::RecordAlloc(rounded_bytes, kind);
408  uint8_t* ret;
409  if (UNLIKELY(padding + rounded_bytes > static_cast<size_t>(end_ - ptr_))) {
410    static_assert(kArenaAlignment >= 16, "Expecting sufficient alignment for new Arena.");
411    ret = AllocFromNewArenaWithMemoryTool(rounded_bytes);
412  } else {
413    ptr_ += padding;  // Leave padding inaccessible.
414    ret = ptr_;
415    ptr_ += rounded_bytes;
416  }
417  MEMORY_TOOL_MAKE_DEFINED(ret, bytes);
418  // Check that the memory is already zeroed out.
419  DCHECK(std::all_of(ret, ret + bytes, [](uint8_t val) { return val == 0u; }));
420  return ret;
421}
422
423ArenaAllocator::~ArenaAllocator() {
424  // Reclaim all the arenas by giving them back to the thread pool.
425  UpdateBytesAllocated();
426  pool_->FreeArenaChain(arena_head_);
427}
428
429uint8_t* ArenaAllocator::AllocFromNewArena(size_t bytes) {
430  Arena* new_arena = pool_->AllocArena(std::max(Arena::kDefaultSize, bytes));
431  DCHECK(new_arena != nullptr);
432  DCHECK_LE(bytes, new_arena->Size());
433  if (static_cast<size_t>(end_ - ptr_) > new_arena->Size() - bytes) {
434    // The old arena has more space remaining than the new one, so keep using it.
435    // This can happen when the requested size is over half of the default size.
436    DCHECK(arena_head_ != nullptr);
437    new_arena->bytes_allocated_ = bytes;  // UpdateBytesAllocated() on the new_arena.
438    new_arena->next_ = arena_head_->next_;
439    arena_head_->next_ = new_arena;
440  } else {
441    UpdateBytesAllocated();
442    new_arena->next_ = arena_head_;
443    arena_head_ = new_arena;
444    // Update our internal data structures.
445    begin_ = new_arena->Begin();
446    DCHECK_ALIGNED(begin_, kAlignment);
447    ptr_ = begin_ + bytes;
448    end_ = new_arena->End();
449  }
450  return new_arena->Begin();
451}
452
453uint8_t* ArenaAllocator::AllocFromNewArenaWithMemoryTool(size_t bytes) {
454  uint8_t* ret = AllocFromNewArena(bytes);
455  uint8_t* noaccess_begin = ret + bytes;
456  uint8_t* noaccess_end;
457  if (ret == arena_head_->Begin()) {
458    DCHECK(ptr_ - bytes == ret);
459    noaccess_end = end_;
460  } else {
461    // We're still using the old arena but `ret` comes from a new one just after it.
462    DCHECK(arena_head_->next_ != nullptr);
463    DCHECK(ret == arena_head_->next_->Begin());
464    DCHECK_EQ(bytes, arena_head_->next_->GetBytesAllocated());
465    noaccess_end = arena_head_->next_->End();
466  }
467  MEMORY_TOOL_MAKE_NOACCESS(noaccess_begin, noaccess_end - noaccess_begin);
468  return ret;
469}
470
471bool ArenaAllocator::Contains(const void* ptr) const {
472  if (ptr >= begin_ && ptr < end_) {
473    return true;
474  }
475  for (const Arena* cur_arena = arena_head_; cur_arena != nullptr; cur_arena = cur_arena->next_) {
476    if (cur_arena->Contains(ptr)) {
477      return true;
478    }
479  }
480  return false;
481}
482
483MemStats::MemStats(const char* name,
484                   const ArenaAllocatorStats* stats,
485                   const Arena* first_arena,
486                   ssize_t lost_bytes_adjustment)
487    : name_(name),
488      stats_(stats),
489      first_arena_(first_arena),
490      lost_bytes_adjustment_(lost_bytes_adjustment) {
491}
492
493void MemStats::Dump(std::ostream& os) const {
494  os << name_ << " stats:\n";
495  stats_->Dump(os, first_arena_, lost_bytes_adjustment_);
496}
497
498// Dump memory usage stats.
499MemStats ArenaAllocator::GetMemStats() const {
500  ssize_t lost_bytes_adjustment =
501      (arena_head_ == nullptr) ? 0 : (end_ - ptr_) - arena_head_->RemainingSpace();
502  return MemStats("ArenaAllocator", this, arena_head_, lost_bytes_adjustment);
503}
504
505}  // namespace art
506