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