buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 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 | |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 17 | #include <algorithm> |
Ian Rogers | 6f3dbba | 2014-10-14 17:41:57 -0700 | [diff] [blame] | 18 | #include <iomanip> |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 19 | #include <numeric> |
| 20 | |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 21 | #include "arena_allocator.h" |
Mathieu Chartier | b666f48 | 2015-02-18 14:33:14 -0800 | [diff] [blame] | 22 | #include "logging.h" |
| 23 | #include "mutex.h" |
Ian Rogers | 02ed4c0 | 2013-09-06 13:10:04 -0700 | [diff] [blame] | 24 | #include "thread-inl.h" |
Mathieu Chartier | 75165d0 | 2013-09-12 14:00:31 -0700 | [diff] [blame] | 25 | #include <memcheck/memcheck.h> |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 26 | |
| 27 | namespace art { |
| 28 | |
Mathieu Chartier | 75165d0 | 2013-09-12 14:00:31 -0700 | [diff] [blame] | 29 | static constexpr size_t kValgrindRedZoneBytes = 8; |
Mark Mendell | 45c1165 | 2013-12-11 12:27:35 -0800 | [diff] [blame] | 30 | constexpr size_t Arena::kDefaultSize; |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 31 | |
Vladimir Marko | bd9e9db | 2014-03-07 19:41:05 +0000 | [diff] [blame] | 32 | template <bool kCount> |
Vladimir Marko | 8dea81c | 2014-06-06 14:50:36 +0100 | [diff] [blame] | 33 | const char* const ArenaAllocatorStatsImpl<kCount>::kAllocNames[] = { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 34 | "Misc ", |
| 35 | "BasicBlock ", |
Vladimir Marko | 850cd16 | 2015-03-17 11:05:20 +0000 | [diff] [blame] | 36 | "BBList ", |
Vladimir Marko | e39c54e | 2014-09-22 14:50:02 +0100 | [diff] [blame] | 37 | "BBPreds ", |
| 38 | "DfsPreOrd ", |
| 39 | "DfsPostOrd ", |
| 40 | "DomPostOrd ", |
| 41 | "TopoOrd ", |
| 42 | "Lowering ", |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 43 | "LIR ", |
Vladimir Marko | 8dea81c | 2014-06-06 14:50:36 +0100 | [diff] [blame] | 44 | "LIR masks ", |
Vladimir Marko | e39c54e | 2014-09-22 14:50:02 +0100 | [diff] [blame] | 45 | "SwitchTbl ", |
| 46 | "FillArray ", |
| 47 | "SlowPaths ", |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 48 | "MIR ", |
| 49 | "DataFlow ", |
| 50 | "GrowList ", |
| 51 | "GrowBitMap ", |
Vladimir Marko | e39c54e | 2014-09-22 14:50:02 +0100 | [diff] [blame] | 52 | "SSA2Dalvik ", |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 53 | "Dalvik2SSA ", |
| 54 | "DebugInfo ", |
| 55 | "Successor ", |
| 56 | "RegAlloc ", |
| 57 | "Data ", |
| 58 | "Preds ", |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 59 | "STL ", |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 60 | }; |
| 61 | |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 62 | template <bool kCount> |
| 63 | ArenaAllocatorStatsImpl<kCount>::ArenaAllocatorStatsImpl() |
| 64 | : num_allocations_(0u) { |
| 65 | std::fill_n(alloc_stats_, arraysize(alloc_stats_), 0u); |
| 66 | } |
| 67 | |
| 68 | template <bool kCount> |
| 69 | void ArenaAllocatorStatsImpl<kCount>::Copy(const ArenaAllocatorStatsImpl& other) { |
| 70 | num_allocations_ = other.num_allocations_; |
| 71 | std::copy(other.alloc_stats_, other.alloc_stats_ + arraysize(alloc_stats_), alloc_stats_); |
| 72 | } |
| 73 | |
| 74 | template <bool kCount> |
| 75 | void ArenaAllocatorStatsImpl<kCount>::RecordAlloc(size_t bytes, ArenaAllocKind kind) { |
| 76 | alloc_stats_[kind] += bytes; |
| 77 | ++num_allocations_; |
| 78 | } |
| 79 | |
| 80 | template <bool kCount> |
| 81 | size_t ArenaAllocatorStatsImpl<kCount>::NumAllocations() const { |
| 82 | return num_allocations_; |
| 83 | } |
| 84 | |
| 85 | template <bool kCount> |
| 86 | size_t ArenaAllocatorStatsImpl<kCount>::BytesAllocated() const { |
| 87 | const size_t init = 0u; // Initial value of the correct type. |
| 88 | return std::accumulate(alloc_stats_, alloc_stats_ + arraysize(alloc_stats_), init); |
| 89 | } |
| 90 | |
| 91 | template <bool kCount> |
| 92 | void ArenaAllocatorStatsImpl<kCount>::Dump(std::ostream& os, const Arena* first, |
| 93 | ssize_t lost_bytes_adjustment) const { |
| 94 | size_t malloc_bytes = 0u; |
| 95 | size_t lost_bytes = 0u; |
| 96 | size_t num_arenas = 0u; |
| 97 | for (const Arena* arena = first; arena != nullptr; arena = arena->next_) { |
| 98 | malloc_bytes += arena->Size(); |
| 99 | lost_bytes += arena->RemainingSpace(); |
| 100 | ++num_arenas; |
| 101 | } |
| 102 | // The lost_bytes_adjustment is used to make up for the fact that the current arena |
| 103 | // may not have the bytes_allocated_ updated correctly. |
| 104 | lost_bytes += lost_bytes_adjustment; |
| 105 | const size_t bytes_allocated = BytesAllocated(); |
| 106 | os << " MEM: used: " << bytes_allocated << ", allocated: " << malloc_bytes |
| 107 | << ", lost: " << lost_bytes << "\n"; |
Vladimir Marko | bd9e9db | 2014-03-07 19:41:05 +0000 | [diff] [blame] | 108 | size_t num_allocations = NumAllocations(); |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 109 | if (num_allocations != 0) { |
| 110 | os << "Number of arenas allocated: " << num_arenas << ", Number of allocations: " |
| 111 | << num_allocations << ", avg size: " << bytes_allocated / num_allocations << "\n"; |
| 112 | } |
| 113 | os << "===== Allocation by kind\n"; |
Andreas Gampe | 785d2f2 | 2014-11-03 22:57:30 -0800 | [diff] [blame] | 114 | static_assert(arraysize(kAllocNames) == kNumArenaAllocKinds, "arraysize of kAllocNames"); |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 115 | for (int i = 0; i < kNumArenaAllocKinds; i++) { |
Vladimir Marko | bd9e9db | 2014-03-07 19:41:05 +0000 | [diff] [blame] | 116 | os << kAllocNames[i] << std::setw(10) << alloc_stats_[i] << "\n"; |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 117 | } |
| 118 | } |
| 119 | |
| 120 | // Explicitly instantiate the used implementation. |
| 121 | template class ArenaAllocatorStatsImpl<kArenaAllocatorCountAllocations>; |
| 122 | |
Mathieu Chartier | c6201fa | 2015-03-12 10:06:33 -0700 | [diff] [blame] | 123 | Arena::Arena() : bytes_allocated_(0), next_(nullptr) { |
Ian Rogers | e7a5b7d | 2013-04-18 20:09:02 -0700 | [diff] [blame] | 124 | } |
| 125 | |
Mathieu Chartier | c6201fa | 2015-03-12 10:06:33 -0700 | [diff] [blame] | 126 | MallocArena::MallocArena(size_t size) { |
| 127 | memory_ = reinterpret_cast<uint8_t*>(calloc(1, size)); |
| 128 | size_ = size; |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 129 | } |
| 130 | |
Mathieu Chartier | c6201fa | 2015-03-12 10:06:33 -0700 | [diff] [blame] | 131 | MallocArena::~MallocArena() { |
| 132 | free(reinterpret_cast<void*>(memory_)); |
| 133 | } |
| 134 | |
| 135 | MemMapArena::MemMapArena(size_t size) { |
| 136 | std::string error_msg; |
| 137 | map_.reset( |
| 138 | MemMap::MapAnonymous("dalvik-LinearAlloc", nullptr, size, PROT_READ | PROT_WRITE, false, |
| 139 | false, &error_msg)); |
| 140 | CHECK(map_.get() != nullptr) << error_msg; |
| 141 | memory_ = map_->Begin(); |
| 142 | size_ = map_->Size(); |
| 143 | } |
| 144 | |
| 145 | void MemMapArena::Release() { |
| 146 | if (bytes_allocated_ > 0) { |
Mathieu Chartier | 9b34b24 | 2015-03-09 11:30:17 -0700 | [diff] [blame] | 147 | map_->MadviseDontNeedAndZero(); |
| 148 | bytes_allocated_ = 0; |
| 149 | } |
| 150 | } |
| 151 | |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 152 | void Arena::Reset() { |
Mathieu Chartier | 9b34b24 | 2015-03-09 11:30:17 -0700 | [diff] [blame] | 153 | if (bytes_allocated_ > 0) { |
Mathieu Chartier | c6201fa | 2015-03-12 10:06:33 -0700 | [diff] [blame] | 154 | memset(Begin(), 0, bytes_allocated_); |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 155 | bytes_allocated_ = 0; |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 156 | } |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 157 | } |
| 158 | |
Mathieu Chartier | c6201fa | 2015-03-12 10:06:33 -0700 | [diff] [blame] | 159 | ArenaPool::ArenaPool(bool use_malloc) |
| 160 | : use_malloc_(use_malloc), lock_("Arena pool lock"), free_arenas_(nullptr) { |
| 161 | if (!use_malloc) { |
Mathieu Chartier | 9b34b24 | 2015-03-09 11:30:17 -0700 | [diff] [blame] | 162 | MemMap::Init(); |
| 163 | } |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 164 | } |
| 165 | |
| 166 | ArenaPool::~ArenaPool() { |
| 167 | while (free_arenas_ != nullptr) { |
| 168 | auto* arena = free_arenas_; |
| 169 | free_arenas_ = free_arenas_->next_; |
| 170 | delete arena; |
| 171 | } |
| 172 | } |
| 173 | |
| 174 | Arena* ArenaPool::AllocArena(size_t size) { |
| 175 | Thread* self = Thread::Current(); |
| 176 | Arena* ret = nullptr; |
| 177 | { |
| 178 | MutexLock lock(self, lock_); |
| 179 | if (free_arenas_ != nullptr && LIKELY(free_arenas_->Size() >= size)) { |
| 180 | ret = free_arenas_; |
| 181 | free_arenas_ = free_arenas_->next_; |
| 182 | } |
| 183 | } |
| 184 | if (ret == nullptr) { |
Mathieu Chartier | c6201fa | 2015-03-12 10:06:33 -0700 | [diff] [blame] | 185 | ret = use_malloc_ ? static_cast<Arena*>(new MallocArena(size)) : new MemMapArena(size); |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 186 | } |
| 187 | ret->Reset(); |
| 188 | return ret; |
| 189 | } |
| 190 | |
Mathieu Chartier | 9b34b24 | 2015-03-09 11:30:17 -0700 | [diff] [blame] | 191 | void ArenaPool::TrimMaps() { |
Mathieu Chartier | c6201fa | 2015-03-12 10:06:33 -0700 | [diff] [blame] | 192 | if (!use_malloc_) { |
| 193 | // Doesn't work for malloc. |
| 194 | MutexLock lock(Thread::Current(), lock_); |
| 195 | for (auto* arena = free_arenas_; arena != nullptr; arena = arena->next_) { |
| 196 | arena->Release(); |
| 197 | } |
Mathieu Chartier | 9b34b24 | 2015-03-09 11:30:17 -0700 | [diff] [blame] | 198 | } |
| 199 | } |
| 200 | |
Mathieu Chartier | 49285c5 | 2014-12-02 15:43:48 -0800 | [diff] [blame] | 201 | size_t ArenaPool::GetBytesAllocated() const { |
| 202 | size_t total = 0; |
| 203 | MutexLock lock(Thread::Current(), lock_); |
| 204 | for (Arena* arena = free_arenas_; arena != nullptr; arena = arena->next_) { |
| 205 | total += arena->GetBytesAllocated(); |
| 206 | } |
| 207 | return total; |
| 208 | } |
| 209 | |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 210 | void ArenaPool::FreeArenaChain(Arena* first) { |
Mathieu Chartier | 661974a | 2014-01-09 11:23:53 -0800 | [diff] [blame] | 211 | if (UNLIKELY(RUNNING_ON_VALGRIND > 0)) { |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 212 | for (Arena* arena = first; arena != nullptr; arena = arena->next_) { |
| 213 | VALGRIND_MAKE_MEM_UNDEFINED(arena->memory_, arena->bytes_allocated_); |
| 214 | } |
Mathieu Chartier | 75165d0 | 2013-09-12 14:00:31 -0700 | [diff] [blame] | 215 | } |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 216 | if (first != nullptr) { |
| 217 | Arena* last = first; |
| 218 | while (last->next_ != nullptr) { |
| 219 | last = last->next_; |
| 220 | } |
| 221 | Thread* self = Thread::Current(); |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 222 | MutexLock lock(self, lock_); |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 223 | last->next_ = free_arenas_; |
| 224 | free_arenas_ = first; |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 225 | } |
| 226 | } |
| 227 | |
| 228 | size_t ArenaAllocator::BytesAllocated() const { |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 229 | return ArenaAllocatorStats::BytesAllocated(); |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 230 | } |
| 231 | |
| 232 | ArenaAllocator::ArenaAllocator(ArenaPool* pool) |
| 233 | : pool_(pool), |
| 234 | begin_(nullptr), |
| 235 | end_(nullptr), |
| 236 | ptr_(nullptr), |
| 237 | arena_head_(nullptr), |
Mathieu Chartier | 661974a | 2014-01-09 11:23:53 -0800 | [diff] [blame] | 238 | running_on_valgrind_(RUNNING_ON_VALGRIND > 0) { |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 239 | } |
| 240 | |
| 241 | void ArenaAllocator::UpdateBytesAllocated() { |
| 242 | if (arena_head_ != nullptr) { |
| 243 | // Update how many bytes we have allocated into the arena so that the arena pool knows how |
| 244 | // much memory to zero out. |
| 245 | arena_head_->bytes_allocated_ = ptr_ - begin_; |
| 246 | } |
| 247 | } |
| 248 | |
Mathieu Chartier | 75165d0 | 2013-09-12 14:00:31 -0700 | [diff] [blame] | 249 | void* ArenaAllocator::AllocValgrind(size_t bytes, ArenaAllocKind kind) { |
Vladimir Marko | 22a0ef8 | 2014-06-10 14:47:51 +0100 | [diff] [blame] | 250 | size_t rounded_bytes = RoundUp(bytes + kValgrindRedZoneBytes, 8); |
Mathieu Chartier | 75165d0 | 2013-09-12 14:00:31 -0700 | [diff] [blame] | 251 | if (UNLIKELY(ptr_ + rounded_bytes > end_)) { |
| 252 | // Obtain a new block. |
| 253 | ObtainNewArenaForAllocation(rounded_bytes); |
| 254 | if (UNLIKELY(ptr_ == nullptr)) { |
| 255 | return nullptr; |
| 256 | } |
| 257 | } |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 258 | ArenaAllocatorStats::RecordAlloc(rounded_bytes, kind); |
Mathieu Chartier | 75165d0 | 2013-09-12 14:00:31 -0700 | [diff] [blame] | 259 | uint8_t* ret = ptr_; |
| 260 | ptr_ += rounded_bytes; |
| 261 | // Check that the memory is already zeroed out. |
| 262 | for (uint8_t* ptr = ret; ptr < ptr_; ++ptr) { |
| 263 | CHECK_EQ(*ptr, 0U); |
| 264 | } |
| 265 | VALGRIND_MAKE_MEM_NOACCESS(ret + bytes, rounded_bytes - bytes); |
| 266 | return ret; |
| 267 | } |
| 268 | |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 269 | ArenaAllocator::~ArenaAllocator() { |
| 270 | // Reclaim all the arenas by giving them back to the thread pool. |
| 271 | UpdateBytesAllocated(); |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 272 | pool_->FreeArenaChain(arena_head_); |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 273 | } |
| 274 | |
| 275 | void ArenaAllocator::ObtainNewArenaForAllocation(size_t allocation_size) { |
| 276 | UpdateBytesAllocated(); |
| 277 | Arena* new_arena = pool_->AllocArena(std::max(Arena::kDefaultSize, allocation_size)); |
| 278 | new_arena->next_ = arena_head_; |
| 279 | arena_head_ = new_arena; |
| 280 | // Update our internal data structures. |
| 281 | ptr_ = begin_ = new_arena->Begin(); |
| 282 | end_ = new_arena->End(); |
| 283 | } |
| 284 | |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 285 | MemStats::MemStats(const char* name, const ArenaAllocatorStats* stats, const Arena* first_arena, |
| 286 | ssize_t lost_bytes_adjustment) |
| 287 | : name_(name), |
| 288 | stats_(stats), |
| 289 | first_arena_(first_arena), |
| 290 | lost_bytes_adjustment_(lost_bytes_adjustment) { |
| 291 | } |
| 292 | |
| 293 | void MemStats::Dump(std::ostream& os) const { |
| 294 | os << name_ << " stats:\n"; |
| 295 | stats_->Dump(os, first_arena_, lost_bytes_adjustment_); |
| 296 | } |
| 297 | |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 298 | // Dump memory usage stats. |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 299 | MemStats ArenaAllocator::GetMemStats() const { |
| 300 | ssize_t lost_bytes_adjustment = |
| 301 | (arena_head_ == nullptr) ? 0 : (end_ - ptr_) - arena_head_->RemainingSpace(); |
| 302 | return MemStats("ArenaAllocator", this, arena_head_, lost_bytes_adjustment); |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 303 | } |
| 304 | |
| 305 | } // namespace art |